「上と左の合計」をErlangで(横へな22)

「[上と左の合計](http://nabetani.sakura.ne.jp/hena/ord22irrpas/)」をErlangでやってみました。他の皆様による実装は[第22回オフラインリアルタイムどう書くの問題](http://qiita.com/Nabetani/items/34bf2a05099a47e193b6)から辿れます。

コードを書き直したものを[「上と左の合計」をErlangで(横へな22) その2](http://qiita.com/pazworld/items/03a9d342025961e6e9ff)としてポストしました。

### コード

```erlang:irrpas.erl
-module( irrpas ).
-compile( export_all ).

solve ( Data ) ->
  [ SizeStr, ConcatListStr | _ ] = string:tokens ( Data, ":" ) ++ [ "" ],
  Size = parse_size ( SizeStr ),
  ConcatList = parse_concat_list ( ConcatListStr ),
  InitDepMap = init_dep_map ( Size ),
  RenumMap = get_renum_map ( Size, ConcatList ),
  DepMap = mix ( InitDepMap, RenumMap ),
  TargetCell = renum_cell ( RenumMap, last_cell ( Size ) ),
  FirstCellValue = [ { renum_cell ( RenumMap, 0 ), 1 } ],
  { _, Value } = cell_value ( DepMap, FirstCellValue, TargetCell ),
  to_s ( Value ).

parse_size ( SizeStr ) ->
  Digits = lists:delete ( $x, SizeStr ),
  string_to_digit_tuple ( Digits ).

parse_concat_list ( ConcatListStr ) ->
  ConcatStrs = string:tokens ( ConcatListStr, "," ),
  [ string_to_digit_tuple ( Str ) || Str <- ConcatStrs ].

string_to_digit_tuple ( Str ) ->
  list_to_tuple ( [ X - $0 || X <- Str ] ).

init_dep_map ( Size ) ->
  depend_upper ( Size ) ++ depend_left ( Size ).

depend_upper ( { W, H } ) ->
  DependUpperCell = [ { X, Y } || X <- lists:seq ( 0, W - 1 ),
                                  Y <- lists:seq ( 1, H - 1 ) ],
  CellPairFun = fun ( X, Y ) ->
    { cell ( W, X, Y ), cell ( W, X, Y - 1 ) } end,
  [ CellPairFun ( X, Y ) || { X, Y } <- DependUpperCell ].

depend_left ( { W, H } ) ->
  DependLeftCell = [ { X, Y } || X <- lists:seq ( 1, W - 1 ),
                                 Y <- lists:seq ( 0, H - 1 ) ],
  CellPairFun = fun ( X, Y ) ->
    { cell ( W, X, Y ), cell ( W, X - 1, Y ) } end,
  [ CellPairFun ( X, Y ) || { X, Y } <- DependLeftCell ].

get_renum_map ( { W, H }, ConcatList ) ->
  StartID = cell ( W, W - 1, H - 1 ) + 1,
  AreaFun = fun ( Area, { NewID, Acc } ) ->
    { NewID + 1, Acc ++ expand_concat ( W, Area, NewID ) } end,
  element(2, lists:foldl ( AreaFun, { StartID, [ ] }, ConcatList )).

expand_concat ( W, { AX, AY, AW, AH }, ID ) ->
  [ { cell ( W, X, Y ), ID } || X <- lists:seq ( AX, AX + AW - 1 ),
                                Y <- lists:seq ( AY, AY + AH - 1 ) ].

mix ( InitDepMap, RenumMap ) ->
  ReplacedMap = replace_map ( InitDepMap, RenumMap ),
  UniqMap = lists:usort ( ReplacedMap ),
  OmitSameCellFun = fun ( { A, B } ) -> A =/= B end,
  NormalizedMap = lists:filter ( OmitSameCellFun, UniqMap ),
  collect_dep_map ( NormalizedMap ).

replace_map ( InitDepMap, RenumMap ) ->
  ReplaceFun = fun ( { A, B } ) ->
    A2 = renum_cell ( RenumMap, A ),
    B2 = renum_cell ( RenumMap, B ),
    { A2, B2 } end,
  lists:map ( ReplaceFun, InitDepMap ).

collect_dep_map ( Map ) ->
  Cells = lists:usort ( [ Cell || { Cell, _Dep } <- Map ] ),
  [ { Cell, dep_map ( Map, Cell ) } || Cell <- Cells ].

dep_map ( Map, Cell ) ->
  lists:filtermap ( fun ( { C, Dep } ) -> case C of
    Cell       -> { true, Dep };
    _Otherwise -> false
  end end, Map ).

renum_cell ( RenumMap, Cell ) ->
  case lists:keyfind ( Cell, 1, RenumMap ) of
    { _Found, NewCell } -> NewCell;
    _Otherwise          -> Cell
  end.

last_cell ( { W, H } ) ->
  cell ( W, W - 1, H - 1 ).

cell_value ( DepMap, Calculated, Cell ) ->
  case lists:keyfind ( Cell, 1, Calculated ) of
    { _Found, Value } -> { Calculated, Value };
    false             -> calc_cell_value ( DepMap, Calculated, Cell )
  end.

calc_cell_value ( DepMap, Calculated, Cell ) ->
  { _Found, DependCell } = lists:keyfind ( Cell, 1, DepMap ),
  SumFun = fun ( C, { Calc, Sum } ) ->
    { Calc2, Value } = cell_value ( DepMap, Calc, C ),
    { Calc2, Sum + Value } end,
  lists:foldl ( SumFun, { Calculated, 0 }, DependCell ).

cell ( W, X, Y ) ->
  Y * W + X.

to_s ( Value ) ->
  string:right ( "0" ++ integer_to_list ( Value ), 2 ).
```

`irrpas:solve ( "8x6:6214,3024,5213,5022,0223,7115" ).` を実行すると、結果の `"32"` が返ってきます。

### データーの流れ

solve関数内のデーターの流れを図にしてみました。最近DOT言語([Wikipedia](http://ja.wikipedia.org/wiki/DOT%E8%A8%80%E8%AA%9E))の勉強を始めたので、作ってみました。

![irrpas.png](https://qiita-image-store.s3.amazonaws.com/0/25938/9ecb0b6b-c2ec-34da-349e-7f9fc4d969cc.png)

### 説明

先にセルの依存関係 (どのセルはどのセルとどのセルの値の合計か) を求め、目的セルから再帰的に依存関係を辿りながら値を求めています。

連結セルは「元のセル番号→連結セル番号」への置き換えマップを作成し、依存関係や先頭・最終セルを置き換えてから計算しています。

### その他

1. 今回のお題は、自分の頭には素晴らしく難しかったです。最初Factorで書こうとして挫折しました。

1. コード中の括弧の前後を空けてみました。詰めて書くよりコードが読みやすくなったと思います。

1. いままで関数型言語で書くときは、なるべく変数を使わず、変数が必要な場合は関数に独立させるように書いてきました。しかし、それではプログラムの流れが分散してしまい、わかりにくいコードになっていたと思います。今回は、ある関数から別の関数に流すデーターを一旦変数に入れる方針で書いてみました。以前よりわかりやすくなったと思います。

1. 関数の引数の順序は (配列, インデックス) のようになっています。この順はFactorでプログラミングした経験によって決まりました。Factorではスタックに最後に積んだ値が一番操作しやすいため、引数は自然と配列→インデックスのような順序になります。Factorを使ってから、引数の順序に迷いがなくなりました (笑)