"1時間以内に解けなければプログラマ失格となってしまう5つの問題"をElixirで解く

[1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に](http://www.softantenna.com/wp/software/5-programming-problems/)をElixirで解いたよ．

[2015/05/30/話題の5つの問題をElixirで解く - ヽ（´・肉・｀）ノログ](http://niku.name/articles/2015/05/30/%E8%A9%B1%E9%A1%8C%E3%81%AE5%E3%81%A4%E3%81%AE%E5%95%8F%E9%A1%8C%E3%82%92Elixir%E3%81%A7%E8%A7%A3%E3%81%8F) から回答だけ転載

[宣伝] [オープンソースカンファレンス2015Hokkaido](http://www.ospn.jp/osc2015-do/) で [Elixir のセミナー](https://www.ospn.jp/osc2015-do/modules/eguide/event.php?eid=37)やるので，興味をもった人は遊びに来てね．[ブース](https://www.ospn.jp/osc2015-do/modules/article/article.php?articleid=1)の Sapporo.beam というところにもほとんどいるつもりだよ．

# forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ

`[h|t]` でパターンマッチすると

- h にはリストの 1 つめ
- t にはリストの残りがリスト

で取得できるよ．再帰で使いやすい．

例: 

```ex
[h|t] = [1,2,3,4]
h # => 1
t # => [2,3,4]
```

```ex
defmodule M1 do
  def sum([]), do: 0
  def sum([h|t]), do: h + sum(t)
end

M1.sum([])          # => 0
M1.sum([1,2,3,4])   # => 10

Enum.sum([1,2,3,4]) # => 10
```

# 交互に要素を取ることで、2つのリストを結合する関数を記述せよ

```ex
defmodule M2 do
  def zip([], []), do: []
  def zip([h|t], []), do: [h | zip(t, [])]
  def zip([], [h|t]), do: [h | zip(t, [])]
  def zip([h1|t1], [h2|t2]) do
    [h1, h2 | zip(t1, t2)]
  end
end

M2.zip(["a", "b", "c"], [1, 2, 3])           # => ["a", 1, "b", 2, "c", 3]
M2.zip(["a", "b", "c", "d", "e"], [1, 2, 3]) # => ["a", 1, "b", 2, "c", 3, "d", "e"]

Enum.zip(["a", "b", "c"], [1, 2, 3]) |> Enum.flat_map(&Tuple.to_list/1) # => ["a", 1, "b", 2, "c", 3]
```

# 最初の100個のフィボナッチ数のリストを計算する関数を記述せよ

副作用がない関数(同じ内容を渡すと，何度やっても同じ内容が返ってくる)多い Elixir でも，ErlangVM に普通にある仕組みを使うとメモ化できるよ．

すこし不思議だ！

```ex
defmodule M3 do
  def list(n) do
    for x <- (0..n-1), do: get(x)
  end

  def get(n) do
    case Agent.get(__MODULE__, &Map.get(&1, n)) do
      nil ->
        result = calc(n)
        Agent.update(__MODULE__, &Map.put(&1, n, result))
        result
      x -> x
    end
  end

  defp calc(0), do: 0
  defp calc(1), do: 1
  defp calc(n), do: get(n-2) + get(n-1)

  def start_link, do: Agent.start_link(fn -> Map.new end, name: __MODULE__)
end

M3.start_link
M3.list(100) # => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, ...]
```

# 正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ

文字列も `<<h, t::binary>>` の形でパターンマッチングできるよ．

```ex
defmodule M4 do
  def calc(list) do
    list
    |> Enum.map(&to_string/1)
    |> Enum.sort(&sorter/2)
    |> Enum.reverse
    |> Enum.join
  end

  defp sorter(<<>>, <<>>),             do: false
  defp sorter(<<_, _::binary>>, <<>>), do: false
  defp sorter(<<>>, <<_, _::binary>>), do: true
  defp sorter(<<h1, t1::binary>>, <<h2, t2::binary>>) do
    if h1 === h2 do
      sorter(t1, t2)
    else
      h1 < h2
    end
  end
end

M4.calc([50, 2, 1, 9])       # => "95021"
M4.calc([50, 2, 1, 9, 2, 5]) # => "9505221"
```

# 1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ

Elixir には式を AST に変換してくれる `quote`，AST を評価する関数 `Code.eval_quoted` というものと， AST をコードにしてくれる `Macro.to_string` という関数があるよ．

今回は

- 「+, -, 数値を文字列化してつなげたもの」という 3 つの候補についての全ての AST を生成
- その中で「AST を評価すると 100 になる AST を集める」
- その AST を文字列化する

という 3 手順で結果を求めたよ．

```iex
iex(1)> quote do: 1+2
{:+, [context: Elixir, import: Kernel], [1, 2]}
iex(2)> Code.eval_quoted({:+, [], [1, 2]})
{3, []}
iex(3)> Macro.to_string({:+, [], [1, 2]})  
"1 + 2"
```

```ex
# 「+, -, 数値を文字列化してつなげたもの」という 3 つの候補についての全ての AST を生成
candidate_asts = Enum.reduce(1..9, fn(x, acc) ->
  case acc do
    y when is_number(y) ->
      [
        quote(do: unquote(y) + unquote(x)),
        quote(do: unquote(y) - unquote(x)),
        quote do
          unquote((to_string(y) <> to_string(x)) |> String.to_integer)
        end
      ]
    y when is_list(y) ->
      Enum.flat_map(y, fn(z) ->
        [
          quote(do: unquote(z) + unquote(x)),
          quote(do: unquote(z) - unquote(x)),
          case z do
            {op, _, args} ->
              last_arg = (to_string(List.last(args)) <> to_string(x)) |> String.to_integer
              {op, [], List.replace_at(args, -1, last_arg)}
            a when is_number(a) ->
              (to_string(a) <> to_string(x)) |> String.to_integer
          end
        ]
      end)
  end
end)

# AST を評価すると 100 になる AST を集める
sum_100_asts = for ast <- candidate_asts,
                   {v, _} = Code.eval_quoted(ast),
                   v === 100
               do
                 ast
               end

Enum.each(sum_100_asts, fn (ast) ->
  # AST を文字列化する
  IO.puts(Macro.to_string(ast))
end)
# => 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
# => 1 + 2 + 34 - 5 + 67 - 8 + 9
# => 1 + 23 - 4 + 5 + 6 + 78 - 9
# => 1 + 23 - 4 + 56 + 7 + 8 + 9
# => 12 + 3 + 4 + 5 - 6 - 7 + 89
# => 12 + 3 - 4 + 5 + 67 + 8 + 9
# => 12 - 3 - 4 + 5 - 6 + 7 + 89
# => 123 + 4 - 5 + 67 - 89
# => 123 + 45 - 67 + 8 - 9
# => 123 - 4 - 5 - 6 - 7 + 8 - 9
# => 123 - 45 - 67 + 89
```