Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

第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
...
pazworld
ヘボプログラマです。Erlangがマイブームです。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away