「円周上のCrossing」をErlangで(横へな14参考)

「円周上のCrossing」をErlangでやってみました。他の実装は 第14回オフラインリアルタイムどう書くの参考問題 から辿れます。

与えられた文字を階段状に配置し、水平・垂直線で下にある同じ文字まで辿ります。水平線が垂直線を横切った数を数えればそれが答えになります。

crosscircle.erl

-module(crosscircle).
-compile(export_all).

%% 解く
solve(Data) ->
  integer_to_list(solve([{X, 0} || X <- Data], 0)).

solve([], Total) ->
  Total;
solve([{FirstChar, _} | Rest], Total) ->
  WithDistance = line_to_distance(Rest),            % 線の本数→距離
  Distance = sum_distance(FirstChar, WithDistance), % 距離を合計
  LineAdded = add_line(FirstChar, Rest),            % 新たに線を引く
  solve(LineAdded, Total + Distance).               % 次の文字へ

%% 先頭から各文字までの距離(交差する線の数)を計算する
%% {文字, 線の数}のリストを受け取り{文字, 距離}のリストを返す
line_to_distance(L) ->
  F = fun({Char, Line}, {Distance, Ret}) ->
    {Distance + Line, [{Char, Distance} | Ret]} end,
  lists:reverse(element(2, lists:foldl(F, {0, []}, L))).

%% リストの先頭の文字から後続の同じ文字までの間に交差する線の数を返す
sum_distance(FirstChar, Rest) ->
  lists:sum([Distance || {Char, Distance} <- Rest, Char =:= FirstChar]).

%% リストの先頭の文字から後続の同じ文字へ線を引く
add_line(FirstChar, Rest) ->
  Same = fun(Char) -> % 同じ文字なら1、違う文字なら0を返す関数
    case Char of FirstChar -> 1; _ -> 0 end end,
  [{Char, Line + Same(Char)} || {Char, Line} <- Rest].

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("aabbca1bcb", "14"), %0
  test("111ZZZ", "0"), %1
  test("v", "0"), %2
  test("ww", "0"), %3
  test("xxx", "0"), %4
  test("yyyy", "1"), %5
  test("zzzzz", "5"), %6
  test("abcdef", "0"), %7
  test("abcaef", "0"), %8
  test("abbaee", "0"), %9
  test("abcacb", "2"), %10
  test("abcabc", "3"), %11
  test("abcdabcd", "6"), %12
  test("abcadeabcade", "23"), %13
  test("abcdeedcba", "0"), %14
  test("abcdeaedcba", "8"), %15
  test("abcdeaedcbad", "16"), %16
  test("QQQQXXXX", "2"), %17
  test("QwQQmQXmXXwX", "14"), %18
  test("111222333", "0"), %19
  test("aaAAaA", "4"), %20
  test("121232313", "12"), %21
  test("1ab1b", "1"), %22
  test("abcdefbadcfe", "12"), %23
  test("abxcdefbadcfex", "14"), %24
  test("dtnwtkt", "0"), %25
  test("mvubvpp", "0"), %26
  test("moggscd", "0"), %27
  test("kzkjzpkw", "2"), %28
  test("fbifybre", "1"), %29
  test("rrrfjryki", "1"), %30
  test("wrbbdwsdwtx", "2"), %31
  test("vvucugvxbvgx", "9"), %32
  test("ojkjzyasjwbfjj", "5"), %33
  test("ggffyuxnkyypifff", "5"), %34
  test("vcgtcqlwrepwvkkogl", "4"), %35
  test("xeqtmmgppwcjpcisogxbs", "4"), %36
  test("lukltpeucrqfvcupnpxwmoj", "6"), %37
  test("zpzswlkkoqwwndwpfdpkhtzgtn", "31"), %38
  test("bkfeflagfvluelududqjcvfyvytfw", "45"), %39
  test("rvqbhfmcjjqlpqzulzerxgyowiwrfkmhw", "26"), %40
  test("qyxvpdtoeexbqsethwjwmqszcxxjnsdoeaet", "144"), %41
  test("rjmsgmswhcolmpbhmpncziymydyalrcnevsrespj", "133"), %42
  test("oxetnyjzjbysnwktfwzndlejfndsqeetsnjvsicyjehd", "395"), %43
  test("wzvddnddzogywcqxbyvagbzmsmtcmrrlbnebmvhaemjouaqim", "219"), %44
  test("karhphxcxqgsyorhusbumbqzocuzvnwzwcpxgsksrviihxrgsrhji", "461"), %45
  test("oxgbononhqdxzmkysgijwvxljpaazmgkurkpffeuwywwuyxhyfkicgyzyc", "441"), %46
  test("sdgsrddwsrwqthhdvhrjhgtxwgurgyiygtktgtughtogzaqmcafkljgpniddsvb", "1077"), %47
  test("qemhecchkgzhxmdcsltwhpoyhkapckkkzosmklcvzkiiucrvzzznmhjfcdumuflavxik", "1711"), %48
  test("ffqmsirwpxrzfkbvmmfeptkbhnrvfcywthkwkbycmayhhkgvuyecbwwofwthlmzruphrcujwhr", "2440"). %49

結果の一部:

ok: aabbca1bcb -> 14
ok: 111ZZZ -> 0
ok: v -> 0
...