AOJ 0595 Schedule

何を今更と思う方もいると思いますが、AOJ0595をErlangで解いた（未確認）ので記事を書くことにしました。

追記(4:35) JOI 2013-2014 予選 問題文・採点用入出力・解説の入出力例に対してすべて正解していました。

Erlangを書くのが非常に久しぶりだったのですがとても楽しくかけました。

問題概要に関してはAOJを見てください。

以下コードです。ぶっちゃけ普段からErlangを書かないのでErlangとして良いコードかはわかりません。

-module(aoj0595).
-export([main/0]).

main() ->
  _ = io:get_line(""),
  S = string:strip(io:get_line(""), right, $\n),
  io:format("~p~n", [schedule(S, true, false, false)]),
  init:stop().

schedule(S, J, O, I) ->
  (
   schedule(S, true, true, true, J, O, I) +
   schedule(S, true, true, false, J, O, I) +
   schedule(S, true, false, true, J, O, I) +
   schedule(S, true, false, false, J, O, I) +
   schedule(S, false, true, true, J, O, I) +
   schedule(S, false, true, false, J, O, I) +
   schedule(S, false, false, true, J, O, I) +
   schedule(S, false, false, false, J, O, I)
  ) rem 10007.
schedule([$J|_], false, _, _, _, _, _) -> 0;
schedule([$O|_], _, false, _, _, _, _) -> 0;
schedule([$I|_], _, _, false, _, _, _) -> 0;
schedule(_, J, O, I, PJ, PO, PI) when not ((J and PJ) or (O and PO) or (I and PI)) -> 0;
schedule([_], _, _, _, _, _, _) -> 1;
schedule([_|L], J, O, I, _, _, _) ->
  LL = length(L),
  case get({LL, J, O, I}) of
    undefined ->
      Ret = schedule(L, J, O, I),
      put({LL, J, O, I}, Ret),
      Ret;
    Memo -> Memo
  end.

再帰はパターンマッチとか使えるととても書きやすいですね。
Erlangにはプロセス辞書という仕組みがあってメモ化するのも非常に簡単です。
プロセス辞書にキャッシュを入れるのは正しいことなんでしょうかね。。。

追記(3:14):
公開してすぐにもっとシンプルに書けることに気が付きました。Blogに公開することは偉大ですね。

-module(aoj0595).
-export([main/0]).

main() ->
  _ = io:get_line(""),
  S = string:strip(io:get_line(""), right, $\n),
  io:format("~p~n", [schedule(S, {true, false, false})]),
  init:stop().

schedule(S, State) ->
  Bool = [true, false],
  Cand = [{J, O, I} || J <- Bool, O <- Bool, I <- Bool],
  lists:foldl(fun(X,Acc) -> Acc + schedule(S, X, State) end, 0, Cand) rem 10007.

schedule([$J|_], {false, _, _}, _) -> 0;
schedule([$O|_], {_, false, _}, _) -> 0;
schedule([$I|_], {_, _, false}, _) -> 0;
schedule(_, {J, O, I}, {PJ, PO, PI}) when not ((J and PJ) or (O and PO) or (I and PI)) -> 0;
schedule([_], _, _) -> 1;
schedule([_|L], State, _) ->
  LL = length(L),
  case get({LL, State}) of
    undefined ->
      Ret = schedule(L, State),
      put({LL, State}, Ret),
      Ret;
    Memo -> Memo
  end.

コードの概要

書いていることは至ってシンプルでJ君,O君,I君の今日と前の日の状態を持って,
それをパターンマッチによって遷移できない状態を除外しているだけです。
あり得る組み合わせだった場合、次の状態に遷移します。
遷移できる次の状態がたかだか8通りなのですべての遷移を試すコードになっています。
あとは引数によって状態が変わらないのでメモ化することができます。

終わりに

Erlangっぽいコードが書きたいなら競プロするな👊って感じですね。