「上と左の合計」をErlangでやってみました。
前回、「上と左の合計」をErlangで(横へな22)で一応の解答を書いたのですが、納得いかなかったため、第22回オフラインリアルタイムどう書くの問題にある皆様の解答を参考に書き直してみました。
コード
irrpas2.erl
-module ( irrpas2 ).
-compile ( export_all ).
solve ( DataString ) ->
[ { Width, Height } | ConcatCells ] = parse_input_string ( DataString ),
TargetCellValueWithMemo = get_value ( Width - 1, Height - 1, ConcatCells, [] ),
get_right_two_digit ( element ( 1, TargetCellValueWithMemo ) ).
parse_input_string ( InputString ) ->
NumberStrings = string:tokens ( lists:delete ( $x, InputString ), ":," ),
[ list_to_tuple ( [ N - $0 || N <- M ] ) || M <- NumberStrings ].
get_right_two_digit ( X ) -> string:right ( "0" ++ integer_to_list ( X ), 2 ).
get_value ( 0, 0, _ConcatCells, ValueMemo ) -> { 1, ValueMemo };
get_value ( X, Y, _ConcatCells, ValueMemo ) when X < 0 orelse Y < 0 -> { 0, ValueMemo };
get_value ( X, Y, ConcatCells, ValueMemo ) ->
{ NX, NY } = normalize_position ( X, Y, ConcatCells ),
case lists:keyfind ( { NX, NY }, 1, ValueMemo ) of
{ _XY, Value } -> { Value, ValueMemo };
_Otherwise ->
LeftAndUpperCells = get_left_and_upper_cells ( NX, NY, ConcatCells ),
UniqueLeftAndUpperCells = lists:usort (
[ normalize_position ( CX, CY, ConcatCells ) || { CX, CY } <- LeftAndUpperCells ] ),
SumCellValueFunction = get_sum_cell_value_function ( ConcatCells ),
lists:foldl ( SumCellValueFunction, { 0, ValueMemo }, UniqueLeftAndUpperCells )
end.
get_sum_cell_value_function ( ConcatCells ) ->
fun ( { X, Y }, { SumValue, ValueMemo } ) ->
{ CellValue, ValueMemo2 } = get_value ( X, Y, ConcatCells, ValueMemo ),
{ SumValue + CellValue, [ { { X, Y }, CellValue } | ValueMemo2 ] }
end.
get_left_and_upper_cells ( X, Y, ConcatCells ) ->
IsInsideFunction = get_is_inside_function ( X, Y ),
case lists:filter ( IsInsideFunction, ConcatCells ) of
[ { _X, _Y, Width, Height } ] -> get_left_and_upper_cells ( X, Y, Width, Height );
_Otherwise -> get_left_and_upper_cells ( X, Y, 1, 1 )
end.
get_left_and_upper_cells ( X, Y, Width, Height ) ->
[ { X - 1, LeftCellY } || LeftCellY <- lists:seq ( Y, Y + Height - 1 )] ++
[ { UpperCellX, Y - 1 } || UpperCellX <- lists:seq ( X, X + Width - 1 ) ].
normalize_position ( X, Y, ConcatCells ) ->
IsInsideFunction = get_is_inside_function ( X, Y ),
case lists:filter ( IsInsideFunction, ConcatCells ) of
[ { FoundRangeX, FoundRangeY, _Width, _Height } ] -> { FoundRangeX, FoundRangeY };
_Otherwise -> { X, Y }
end.
get_is_inside_function ( X, Y ) ->
fun ( { RangeX, RangeY, RangeWidth, RangeHeight } ) ->
RangeX =< X andalso X < RangeX + RangeWidth andalso
RangeY =< Y andalso Y < RangeY + RangeHeight
end.
irrpas2:solve ( "8x6:6214,3024,5213,5022,0223,7115" ). を実行すると、結果の "32" が返ってきます。
説明
前回は関数型言語らしく「リストを変形する」という方針で書きましたが、コードが複雑になってしまったため、今回は皆様の解答を参考にしてシンプルに「メモ化付き再帰」で書きました。
変数の書き換えを許すプログラミング言語ならメモ化は簡単ですし、Haskellならcall by needなのでメモ化しなくても速いですが、Erlangはcall by valueなのに変数の書き換えを許さないためメモ化しにくいです。メモを更新しながら関数の呼び出し方向(引数)にも、戻り方向(戻り値)にも渡す必要があります。
その他
割とすっきり書くことができました。しかしこれを1時間で書くことはできないです。
きれいなソースコードを書くために必要な、たったひとつの単純な事を読んで、変数名や関数名を「そのスコープにおいて内容を正しく表している名前」にすることを心がけました。
正しい名前にすることで、後から読んでもプログラムの意味がわかりやすくなっていると思います。しかしその分、変数名や関数名が長くなりました。
そこで私がいままで持っていた「1行80文字まで」というポリシーを捨て、1行が長くなってもそのまま書いてみました。「1行ならすっきり書けるのに82文字になっちゃったから途中で改行」のような不自然な改行がなくなりました。