「上と左の合計」をErlangで(横へな22) ref: http://qiita.com/pazworld/items/ccc5e9c4d8bda7675a8c

irrpas.dot

digraph irrpas {
start -> tokens [ label="Data" ];
subgraph cluster_solve {
label="solve";
tokens [ label="string:tokens\n':'で分ける", fontname="IPAexGothic" ];
tokens -> parse_size [ label="SizeStr" ];
tokens -> parse_concat_list [ label="ConcatListStr" ];
parse_size [ label="parse_size\n文字列→サイズ", fontname="IPAexGothic" ];
parse_size -> init_dep_map [ label="Size" ];
parse_size -> get_renum_map [ label="Size" ];
parse_concat_list [ label="parse_concat_list\n文字列→連結セル", fontname="IPAexGothic" ];
parse_concat_list -> get_renum_map [ label="ConcatList" ];
init_dep_map [ label="init_dep_map\nセル依存関係取得", fontname="IPAexGothic" ];
init_dep_map -> mix [ label="InitDepMap" ];
get_renum_map [ label="get_renum_map\n連結セル情報取得", fontname="IPAexGothic" ];
get_renum_map -> mix [ label="RenumMap" ];
parse_size -> last_cell [ label="Size" ];
last_cell [ label="last_cell\n最終セル取得", fontname="IPAexGothic" ];
last_cell -> renum_cell [ label="LastCell" ];
renum_cell2 [ label="renum_cell\n先頭セル番号変換", fontname="IPAexGothic" ];
get_renum_map -> renum_cell2 [ label="RenumMap" ];
mix [ label="mix\nセル依存関係に連結セル情報を追加", fontname="IPAexGothic" ];
cell_value [ label="cell_value\nセル値の計算", fontname="IPAexGothic" ];
mix -> cell_value [ label="DepMap" ];
renum_cell2 -> cell_value [ label="FirstCellValue" ];
renum_cell [ label="renum_cell\n最終セル番号変換", fontname="IPAexGothic" ];
renum_cell -> cell_value [ label="TargetCell" ];
to_s [ label="to_s\n数値→文字列", fontname="IPAexGothic" ];
cell_value -> to_s [ label="Value" ];
}
to_s -> end;
}

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 ).