「折って切る」をErlangとRubyで(横へな17)

「折って切る」をErlangとRubyでやってみました。他の皆様による実装は 第17回オフラインリアルタイムどう書くの問題 から辿れます。

foldcut.rb

def solve(data)
  d = data.upcase.split("-")
  [/T|B/, /L|R/].zip(d[1].split(//)).inject(1) { | acc, rc | acc *
    holenum(d[0].split(//).select { |c| c.match(rc[0]) }.join, rc[1]) }
end

def holenum(s, c)
  (s == "") ? 0 : 2 ** (s.length - 1) - (s[-1] == c ? 0 : 1)
end

foldcut.erl

-module(foldcut).
-compile(export_all).

solve(Data) ->
  integer_to_list(solve2(string:tokens(string:to_upper(Data), "-"))).

solve2([S, [AY, AX]]) ->
  trunc(holenum(filter("LR", S), AX) * holenum(filter("TB", S), AY)).

filter([C1, C2], L) -> lists:filter(fun(X) -> (X =:= C1) or (X =:= C2) end, L).

holenum("", _) -> 0;
holenum(S, C) -> case lists:last(S) of
  C -> math:pow(2, length(S) - 1);
  _ -> math:pow(2, length(S) - 1) - 1
end.

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

tests() ->
  test("RRTRB-bl", "6"), %0
  test("R-tr", "0"), %1
  test("L-br", "0"), %2
  test("T-tl", "0"), %3
  test("B-tl", "0"), %4
  test("BL-br", "0"), %5
  test("LB-tl", "0"), %6
  test("RL-tl", "0"), %7
  test("BL-tl", "0"), %8
  test("TL-bl", "0"), %9
  test("RT-tr", "1"), %10
  test("TRB-tl", "0"), %11
  test("TRL-bl", "0"), %12
  test("TRB-br", "2"), %13
  test("LLB-bl", "2"), %14
  test("RTL-tr", "1"), %15
  test("LBB-tr", "0"), %16
  test("TLL-tl", "2"), %17
  test("RLRR-tr", "0"), %18
  test("BBTL-tl", "4"), %19
  test("TBBT-tr", "0"), %20
  test("LLBR-tl", "0"), %21
  test("LBRT-tl", "2"), %22
  test("RLBL-bl", "4"), %23
  test("BRRL-br", "3"), %24
  test("TBBTL-tl", "8"), %25
  test("TLBBT-br", "0"), %26
  test("LRBLL-br", "7"), %27
  test("TRRTT-br", "6"), %28
  test("BBBLB-br", "0"), %29
  test("RTTTR-tl", "4"), %30
  test("BBLLL-br", "6"), %31
  test("RRLLTR-tr", "16"), %32
  test("TTRBLB-br", "8"), %33
  test("LRBRBR-bl", "14"), %34
  test("RBBLRL-tl", "8"), %35
  test("RTRLTB-tl", "12"), %36
  test("LBLRTR-tl", "14"), %37
  test("RRLTRL-tl", "16"), %38
  test("TBLTRR-br", "12"), %39
  test("TTTRLTT-bl", "30"), %40
  test("TBBRTBL-tr", "15"), %41
  test("TRTRTLL-tr", "28"), %42
  test("TLLRTRB-tr", "24"), %43
  test("RLLBRLB-tr", "15"), %44
  test("LTLRRBT-tr", "32"), %45
  test("RBBRBLT-br", "21"), %46
  test("LLRLRLR-tr", "0"). %47

Rubyの方はテストケースを割愛しています。

次のような考え方でプログラミングしました。

1. 特定の方向にN回折ったとき、折り線は2^N-1本になる。
2. 切ったときの穴は、隣り合う折り線のどちらか一方にしか開かない。(互い違いに穴が開く。)
3. N回折って切ったとき、穴の数は次のどちらかである。
   1. 紙の中心にある折り線に穴がない場合 … 2^(N-1)
   2. 紙の中心にある折り線に穴がある場合 … 2^(N-1)-1
4. 紙の中心にある折り線の位置は、最後に折った方向の反対側になる (！)
5. 折り線の数と、最後に折った方向、切る方向から穴の数が求まる。