「積み木の水槽」をErlangで(横へな13)

第13回オフラインリアルタイムどう書くの問題
積み木の水槽 ～ 横へな 2013.9.6
「積み木の水槽」をErlangでやってみました。

穴(ブロックのない所)からヘリウムガスが吹き出すことを考えました。ガスは横または上に広がります。ガスのない場所＝窪んでいる場所＝水がたまる場所なので、その個数を数えています。

blocktub.erl

-module(blocktub).
-compile(export_all).

%% 問題を解く
solve(Data) ->
  integer_to_list(pit_count([Digit - $0 || Digit <- Data])).

%% 窪みの数を計算する
pit_count(Data) ->
  Max = lists:max(Data),                    % 壁の最大高さ
  Walled = [Max, 0] ++ Data ++ [0, Max],    % 左右に穴と壁を追加
  lists:foldl(fun(Height, Count) ->
    pit_count(Walled, Height) + Count end, 0, lists:seq(1, Max)).

%% 指定された高さにある窪みの数を計算する
pit_count(Data, Height) ->
  Drain = [Idx || {Idx, Num} <- with_index(Data), Num =:= 0], % 穴
  Block = [Idx || {Idx, Num} <- with_index(Data), Num >= Height], % ブロック
  Gas = lists:usort([{                       % ガス範囲を求める
    lists:max([B + 1 || B <- Block, B < D]), % ガスの左端
    lists:min([B - 1 || B <- Block, B > D])  % ガスの右端
    } || D <- Drain]),
  GasCount = lists:foldl(                    % ガスの数を求める
    fun({L, R}, Count) -> Count + R - L + 1 end, 0, Gas),
  length(Data) - length(Block) - GasCount.   % 窪みの数 (=幅-ブロック-ガス)

%% インデックスを追加する [a,b,c] -> [{1,a},{2,b},{3,c}]
with_index(Data) -> lists:zip(lists:seq(1, length(Data)), Data).

test(Data, Expected) ->
  Result = solve(Data),
  OkNg = case Result =:= Expected of true -> ok; false -> ng end,
  io:fwrite("~s: ~s -> ~s~n", [OkNg, Data, Result]).

tests() ->
  test("83141310145169154671122", "24"), %0
  test("923111128", "45"), %1
  test("923101128", "1"), %2
  test("903111128", "9"), %3
  test("3", "0"), %4
  test("31", "0"), %5
  test("412", "1"), %6
  test("3124", "3"), %7
  test("11111", "0"), %8
  test("222111", "0"), %9
  test("335544", "0"), %10
  test("1223455321", "0"), %11
  test("000", "0"), %12
  test("000100020003121", "1"), %13
  test("1213141516171819181716151413121", "56"), %14
  test("712131415161718191817161514131216", "117"), %15
  test("712131405161718191817161514031216", "64"), %16
  test("03205301204342100", "1"), %17
  test("0912830485711120342", "18"), %18
  test("1113241120998943327631001", "20"), %19
  test("7688167781598943035023813337019904732", "41"), %20
  test("2032075902729233234129146823006063388", "79"), %21
  test("8323636570846582397534533", "44"), %22
  test("2142555257761672319599209190604843", "41"), %23
  test("06424633785085474133925235", "51"), %24
  test("503144400846933212134", "21"), %25
  test("1204706243676306476295999864", "21"), %26
  test("050527640248767717738306306596466224", "29"), %27
  test("5926294098216193922825", "65"), %28
  test("655589141599534035", "29"), %29
  test("7411279689677738", "34"), %30
  test("268131111165754619136819109839402", "102"). %31

結果の一部:

ok: 83141310145169154671122 -> 24
ok: 923111128 -> 45
ok: 923101128 -> 1
ok: 903111128 -> 9
...