※この記事はElixir Advent Calendar 2018の9日目です
8日目は yujikawaさんの【入門】FlutterとElixir/PhoenixのGraphQLでTODOアプリを作る（Elixir編）です！
こちらも是非！
Elixirで競プロ解けるかって？・・・できらぁ！！
競技プログラミングの代表的なサービスであるAtCoderには過去問精選問題というものがあり、C++をはじめ様々な言語で解かれています
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
筆者も以前Goで解きました
AtCoder 過去問精選 10 問 をGoでやってみた
そしてfukuoka.exキャストとして最近ハマって勉強している**Elixir**という言語
・・・えっ？知らない？それでは以下を読んでみてください笑
【fukuoka.ex】学生エンジニアがElixirに興味を持ったきっかけと初心者にオススメの勉強法
ザっと調べたところElixirで解かれている問題はなさそう（まぁAtCoder対応してないんですが笑）
ということでやってみよ～
doctest使ってみる
とはいえAtCoderが対応していないのでテスト結果は自分で考えないといけないです
まぁそれはサンプル入力や他の方のを見ればいいんですが、いちいち打つのはめんどう・・・
しかし！！Elixirにはdoctestというものが標準装備されています！！
百聞は一見に如かずということで以下をどうぞ
defmodule Sample do
@doc """
## Examples
iex> Sample.hello()
:world
"""
def hello do
:world
end
end
defmodule SampleTest do
use ExUnit.Case
doctest Sample
end
めっちゃ簡単！！！
ちなみにiexは、RubyでいうirbやPythonでいうipythonのように、コマンドライン上でElixirを実行するツールで、Elixirに標準装備されています
mixで準備
Elixirにはmixというパッケージ管理やらディレクトリ生成やらを行ってくれるツールが標準装備されています
rubyでいうgemとか、PHPでいうcomposerみたいなの
標準でdoctestできるようになっているので、これを活用していきましょう
mix new atcoder_practiceとしてディレクトリの生成を行います
atcoder_practice/
├── README.md
├── _build
│ └── test
│ └── lib
│ └── atcoder_practice
│ ├── consolidated
│ │ ├── Elixir.Collectable.beam
│ │ ├── Elixir.Enumerable.beam
│ │ ├── Elixir.IEx.Info.beam
│ │ ├── Elixir.Inspect.beam
│ │ ├── Elixir.List.Chars.beam
│ │ └── Elixir.String.Chars.beam
│ └── ebin
│ ├── Elixir.AtcoderPractice.beam
│ └── atcoder_practice.app
├── config
│ └── config.exs
├── lib
│ └── atcoder_practice.ex
├── mix.exs
└── test
├── atcoder_practice_test.exs
└── test_helper.exs
9 directories, 14 files
今回はdoctestしか使わないのでtest/atcoder_practice_test.exsを以下のように書き換えます
defmodule AtcoderPracticeTest do
use ExUnit.Case
doctest AtcoderPractice
# test "greets the world" do
# assert AtcoderPractice.hello() == :world
# end
end
※elixirで標準入力を受け取るには以下の記事のようにIO.getsを使うとかすればいいんですが、①テストしにくい、②関数型であるElixir的には副作用のある関数はあまり望ましくない、という点から標準入力はすでに行われているものとし、解答に含めないことにします
気になる方は以下の記事が詳しいです
yukicoder（競プロ）でElixirの修行をする
【fukuoka.ex】学生エンジニアがElixirに興味を持ったきっかけと初心者にオススメの勉強法
簡単なサンプルも以下に貼っておきますね
defmodule Solution do
a = IO.gets("") |> String.trim() |> String.to_integer
b = IO.gets("") |> String.trim() |> String.to_integer
IO.puts(a+b)
end
それでは解答しましょ～
第 1 問: ABC 086 A - Product (100 点)
Elixirで余りを計算するときは%ではなくrem/2を使うみたい
%はハッシュ（連想配列）で使うから区別するためですかね
（remは関数名で/2は引数の数です。Elixirでは同名の関数でも引数の数が異なると機能も異なるように実装可能なのでこのような表記をします）
あとreturn使うとエラーになるので注意
Elixirは条件分岐の方法としてifの他にcase, withなどが存在します
パターンマッチという機能が強力なのでcaseで書くことが多いかも
@doc """
## Examples
iex> AtcoderPractice.product(3,4)
'Even'
iex> AtcoderPractice.product(1,21)
'Odd'
"""
def product(a, b) do
case rem(a * b, 2) do
0 ->
'Even'
1 ->
'Odd'
end
end
mix test してみよう（ ＾ω＾）・・・
ドキドキ・・・
よっしゃ！できてる！！
第 2 問: ABC 081 A - Placing Marbles (100 点)
問題に準拠したいため入力は文字列としました
String.codepoints()を使って1文字ずつのlistにしてEnum系の関数を使えるようにしたあと、Enum.countで条件に合う要素の数をカウントしています
関数型でない言語だとcountというローカル変数を定義してループしていくと思いますが、Elixirなら1行で書けます（すごい！）
@doc """
## Examples
iex> AtcoderPractice.placing_marbles("101")
2
iex> AtcoderPractice.placing_marbles("000")
0
iex> AtcoderPractice.placing_marbles("100")
1
iex> AtcoderPractice.placing_marbles("111")
3
iex> AtcoderPractice.placing_marbles("010")
1
"""
def placing_marbles(s) do
s |> String.codepoints() |> Enum.count(fn x -> x == "1" end)
end
ちなみにドキュメントによるとiex>の行を改行せずに続けると一続きのテストとして実行されます
改行するとそれぞれ別のテストとみなされるようです
ExUnit.DocTest – ExUnit v1.7.4
第 3 問: ABC 081 B - Shift Only (200 点)
再帰使うとこんな感じでしょうか
Elixirにはループのためのforが存在しないので、繰り返し処理は少し頭使いますね
ElixirにはEnumという便利なモジュールがあるので、それを使えばスッキリ書けます！
ちなみにEnum.allはリストの全要素が条件を満たすかどうかを判定する関数です
@doc """
## Examples
iex> AtcoderPractice.shift_only("8 12 40")
2
iex> AtcoderPractice.shift_only("5 6 8 10")
0
iex> AtcoderPractice.shift_only("382253568 723152896 37802240 379425024 404894720 471526144")
8
iex> AtcoderPractice.shift_only("4 4")
2
iex> AtcoderPractice.shift_only("2 2")
1
"""
def shift_only(s) do
list = s |> String.split() |> Enum.map(&String.to_integer/1)
shift_only_count(list, 0)
end
defp shift_only_count(list, count) do
if Enum.all?(list, &(rem(&1, 2) == 0)) do
shift_only_count(Enum.map(list, &div(&1, 2)), count + 1)
else
count
end
end
ちなみにElixirでは関数は**「関数名」と「引数の数（アリティ）」**で区別されます
つまり同じ関数名でも引数の数が異なれば別の関数として扱われます
https://elixirschool.com/ja/lessons/basics/functions/
上記では再帰用の関数をshift_only_countとして別名に分けていましたが、実は同じ名前でもOKです
def shift_only(s) do
list = s |> String.split() |> Enum.map(&String.to_integer/1)
shift_only(list, 0)
end
defp shift_only(list, count) do
if Enum.all?(list, &(rem(&1, 2) == 0)) do
shift_only(Enum.map(list, &div(&1, 2)), count + 1)
else
count
end
end
再帰を使わない解法やスッキリ書ける方法分かる方いればご教授お願いしたいです笑
第 4 問: ABC 087 B - Coins (200 点)
関数型でない言語で解く場合は素直に3重ループする問題ですが、Elixirは関数型
つまりforがありません
すべてのパターンを列挙したリストを作成し、条件に一致するものをカウントするという方針でやってみます
実装すると以下のようになります
@doc """
## Examples
iex> AtcoderPractice.coins(2,2,2,100)
2
iex> AtcoderPractice.coins(5,1,0,150)
0
iex> AtcoderPractice.coins(30,40,50,6000)
213
"""
def coins(n500, n100, n50, total) do
0..n50
|> Enum.map(fn i ->
0..n100
|> Enum.map(fn j ->
0..n500
|> Enum.map(fn k ->
i * 50 + j * 100 + k * 500
end)
end)
end)
|> List.flatten()
|> Enum.count(&(&1 == total))
end
Enum.mapを複数適用した結果はリストが入れ子になってしまうので、List.flatten/1により1次元に変換してEnum.countしています
しかしちょっと可読性悪いっすね（ ＾ω＾）・・・
もうちょっといい書き方ないかな～と思って調べてみると、以下のようにスッキリ書けることを発見！
def coins(n500, n100, n50, total) do
for i <- 0..n50,
j <- 0..n100,
k <- 0..n500 do
i * 50 + j * 100 + k * 500
end
|> Enum.count(&(&1 == total))
end
ちなみにElixirではforはループではなくてリストのジェネレータです（内包表記）
Elixirの"for"はリストのジェネレータ - Qiita
forはこのように複数のenumerableな要素を指定できるので、これを使ってリストを生成すると簡潔に書けますね
内包表記 · Elixir School
第 5 問: ABC 083 B - Some Sums (200 点)
各桁の和を計算する関数digit_sumを定義して、それを使ってEnum.filterするのがポイントです
各桁の和を計算する際は、いったん一文字ずつのリストに変換して総和を取ると簡単に計算できます
@doc """
## Examples
iex> AtcoderPractice.some_sums(20,2,5)
84
iex> AtcoderPractice.some_sums(10,1,2)
13
iex> AtcoderPractice.some_sums(100,4,16)
4554
"""
def some_sums(n, a, b) do
1..n
|> Enum.filter(&(a <= digit_sum(&1) and digit_sum(&1) <= b))
|> Enum.sum()
end
defp digit_sum(n) do
Integer.to_string(n)
|> String.codepoints() # 1文字ずつのリストへ
|> Enum.map(&String.to_integer/1)
|> Enum.sum()
end
第 6 問: ABC 088 B - Card Game for Two (200 点)
①card_listを降順ソート
②それを使ってAliceとBobが取るカードのリストをそれぞれ生成
③和をとる
という流れで解くとスッキリしますね！
Enum.take_every(2)はリストの先頭からスタートして2つ飛ばしで要素を取ったリストを返す関数
Enum.drop_every(2)はリストの先頭からスタートして2つ飛ばしで要素をスキップしたリストを返す関数
です
公式ドキュメントが充実しているので、何かやりたいことがある場合には調べてみるといいと思います
https://hexdocs.pm/elixir/Enum.html#content
@doc """
## Examples
iex> AtcoderPractice.card_game_for_two([3,1])
2
iex> AtcoderPractice.card_game_for_two([2,7,4])
5
iex> AtcoderPractice.card_game_for_two([20,18,2,18])
18
"""
def card_game_for_two(card_list) do
sorted_card_dsc = card_list |> Enum.sort(&(&1 >= &2))
alice_sum = sorted_card_dsc |> Enum.take_every(2) |> Enum.sum()
bob_sum = sorted_card_dsc |> Enum.drop_every(2) |> Enum.sum()
alice_sum - bob_sum
end
第 7 問: ABC 085 B - Kagami Mochi (200 点)
問題文をよく読むと、単純に同じ大きさの餅を排除すればいいだけだと分かります
Enum.uniqをしてlengthで長さを求めるだけですね！スッキリ！
@doc """
## Examples
iex> AtcoderPractice.kagami_mochi([10,8,8,6])
3
iex> AtcoderPractice.kagami_mochi([15,15,15])
1
iex> AtcoderPractice.kagami_mochi([50,30,50,100,50,80,30])
4
"""
def kagami_mochi(mochi_list) do
mochi_list
|> Enum.uniq()
|> length
end
第 8 問: ABC 085 C - Otoshidama (300 点)
こういう出力が一意でない関数のテストはdoctest向いてないですね・・・
doctestに対応させるため、暗黙の制約として「同じ出力が複数存在する場合は10000円が最も少なくなるものを採用する」ことにします
回答の方針として
①全通りの{10000円枚数,5000円枚数,1000円枚数}のリストを生成
②Enum.filterにて合計が条件に合うものだけを抽出
③Enum.atにて取り出す。ただし条件に合うものがなくて取り出せない場合のデフォルト値は{-1,-1,-1}とする
という方針です
Enum.atは地味に「値が取り出せない場合のデフォルト値」を設定できるので、これを活用するとifを使わずにスッキリ書けます！
https://hexdocs.pm/elixir/Enum.html#at/3
@doc """
## Examples
iex> AtcoderPractice.otoshidama(9,45000)
{0,9,0}
iex> AtcoderPractice.otoshidama(20,196000)
{-1,-1,-1}
iex> AtcoderPractice.otoshidama(1000,1234000)
{2,54,944}
iex> AtcoderPractice.otoshidama(2000,20000000)
{2000,0,0}
"""
def otoshidama(n, total) do
for i <- 0..n,
j <- 0..(n - i) do
{i, j, n - i - j}
end
|> Enum.filter(fn {i, j, k} -> i * 10000 + j * 5000 + k * 1000 == total end)
|> Enum.at(0, {-1, -1, -1})
end
第 9 問: ABC 049 C - Daydream (300 点)
単純に解くと候補となる文字列を全通り列挙すればいいんじゃないかという気もしますが、これは指数関数的に増えていきます
文字列の長さは100000まで考えられるので、下記のように解くとメモリが速攻で死にます笑
（実行するとPCフリーズしかねないので注意）
@doc """
## Examples
iex> AtcoderPractice.day_dream("erasedream")
:YES
iex> AtcoderPractice.day_dream("dreameraser")
:YES
iex> AtcoderPractice.day_dream("dreamerer")
:NO
"""
def day_dream(s) do
sub_strings = ["dream", "dreamer", "erase", "eraser"]
strings = generate_strings([""], sub_strings, div(String.length(s), 5))
if Enum.any?(strings, &(&1 == s)) do
:YES
else
:NO
end
end
defp generate_strings(strings, sub_strings, count) do
new_strings = for s <- strings, ss <- sub_strings, do: s <> ss
if count > 0 do
generate_strings(strings ++ new_strings, sub_strings, count - 1)
else
new_strings
end
end
ここは発想を変えて「チェックしたい文字列集合のどれかに一致するかどうか」を「文字列の先頭から」チェックするとどうでしょう？
しかし、先頭からチェックする場合にdreamが出てきた場合、これが「dreamerの先頭5文字目まで」なのか「dream」なのかが区別できません
同様にdreamerが出てきた場合、「[dream]と[eraseもしくはeraserの2文字目まで]」なのか「dreamer」なのか区別できません
詳しくは元記事の説明をどうぞ
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ 第-9-問--abc-049-c---daydream-300-点
一方で「文字列の後ろからチェック」する場合はこのような問題が発生しません
反転させて調べてもいいのですが、Elixirにはcondがあるので、正規表現で条件書き並べてもスッキリ解けそうです
@doc """
## Examples
iex> AtcoderPractice.day_dream("erasedream")
:YES
iex> AtcoderPractice.day_dream("dreameraser")
:YES
iex> AtcoderPractice.day_dream("dreamerasererasedreamereraser")
:YES
iex> AtcoderPractice.day_dream("dreamerer")
:NO
"""
def day_dream(s) do
cond do
Regex.match?(~r/dream$/, s) -> day_dream(String.slice(s, 0..-6))
Regex.match?(~r/dreamer$/, s) -> day_dream(String.slice(s, 0..-8))
Regex.match?(~r/erase$/, s) -> day_dream(String.slice(s, 0..-6))
Regex.match?(~r/eraser$/, s) -> day_dream(String.slice(s, 0..-7))
s == "" -> :YES
true -> :NO
end
end
もっといい解き方ありそう（ ＾ω＾）・・・
第 10 問: ABC 086 C - Traveling (300 点)
これは満たすべき条件は
$dt = t_{i+1} - t_{i}$, $dist = {\rm abs}(x_{i+1} - x_{i}) + {\rm abs}(y_{i+1} - y_{i})$ と定義したとき
①dt >= dist であること
②dtとdistの偶奇が一致すること
となります
元記事の説明にもっと詳しく書いています
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ 第-10-問--abc-086-c---traveling-300-点
これをElixirで書くと本当にスッキリ書けます
筆者も結構試行錯誤しましたが、最終的なコードの美しさに感動しました笑
方針はこんな感じ
①[[t1,x1,y1], [t2,x2,y2], ...]のリストから[[dt1, dist1], [dt2, dist2], ...] のリストを作る
②条件判定する
@doc """
## Examples
iex> AtcoderPractice.traveling([[3,1,2], [6,1,1]])
:Yes
iex> AtcoderPractice.traveling([[2,100,100]])
:No
iex> AtcoderPractice.traveling([[5,1,1], [100,1,1]])
:No
iex> AtcoderPractice.traveling([[100,100,0], [102,0,0]])
:No
"""
def traveling(list) do
# [[dt1, dist1], [dt2, dist2], ...] リストを作る
Enum.map_reduce(list, [0, 0, 0], fn [t2, x2, y2], [t1, x1, y1] ->
{[t2 - t1, abs(x2 - x1) + abs(y2 - y1)], [t2, x2, y2]}
end)
|> elem(0)
|> Enum.all?(fn [dt, dist] -> dt >= dist and rem(dist, 2) == rem(dt, 2) end)
|> case do
true -> :Yes
_ -> :No
end
end
ポイントはEnum.map_reduce/3になります
今回はリストの各要素に対して計算を行うのではなく「現在の要素とその前の要素」を使って（distとdtの）計算を行う必要があります
map_reduce/3は第一引数に現在の要素、第二引数に前の要素を取ることが出来るので、これを使えば「現在の要素と前の要素」を使って計算を行うことができます
map_reduce/3の返り値は{リスト、最後の要素}のタプルになっているので、タプルから要素を取り出すelemを使用して取り出しています
※map_reduce使わずに、前（もしくは後）の要素を参照する方法あったら教えていただけると幸いです笑
まとめ
以前Goでもやったのですが、Elixirでやってみたところ、「慣れ親しんだforが使えなくて悩む」一方で「最終的なコードは尋常じゃなくスッキリ」しますね
AtCoder 過去問精選 10 問 をGoでやってみた
RubyやPythonなどでforを使った命令型のプログラミングをする場合、forやifを起点にした制御構文を前提にアルゴリズムを組み立てます
一方で（関数型の）Elixirでやってみた結果、（問題を）いかにリストなどのenumerable（反復可能）なデータ構造に落とし込むかがコツだと感じました
つまり、データに対して何か処理/加工するというのがElixirの最も得意とする領域なのかもしれません
今後巨大データを扱う場面も増えてきますし、Elixirなら耐障害性を高く保ちつつ、並列/高速にデータ処理できます
さらにPhoenixというRailsライクなフレームワークを使えばWebアプリもサクッと実装出来ますね
まだまだElixir慣れないので、もっといいやり方あるよ！って方いればコメント欄などで教えていただけると幸いですｂ
次回はYoosukeさんの記事です！