「上と左の合計」をErlangでやってみました。他の皆様による実装は第22回オフラインリアルタイムどう書くの問題から辿れます。
コードを書き直したものを「上と左の合計」をErlangで(横へな22) その2としてポストしました。
コード
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)の勉強を始めたので、作ってみました。
説明
先にセルの依存関係 (どのセルはどのセルとどのセルの値の合計か) を求め、目的セルから再帰的に依存関係を辿りながら値を求めています。
連結セルは「元のセル番号→連結セル番号」への置き換えマップを作成し、依存関係や先頭・最終セルを置き換えてから計算しています。
その他
今回のお題は、自分の頭には素晴らしく難しかったです。最初Factorで書こうとして挫折しました。
コード中の括弧の前後を空けてみました。詰めて書くよりコードが読みやすくなったと思います。
いままで関数型言語で書くときは、なるべく変数を使わず、変数が必要な場合は関数に独立させるように書いてきました。しかし、それではプログラムの流れが分散してしまい、わかりにくいコードになっていたと思います。今回は、ある関数から別の関数に流すデーターを一旦変数に入れる方針で書いてみました。以前よりわかりやすくなったと思います。
関数の引数の順序は (配列, インデックス) のようになっています。この順はFactorでプログラミングした経験によって決まりました。Factorではスタックに最後に積んだ値が一番操作しやすいため、引数は自然と配列→インデックスのような順序になります。Factorを使ってから、引数の順序に迷いがなくなりました (笑)