「折って切る」を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の方はテストケースを割愛しています。
次のような考え方でプログラミングしました。
- 特定の方向にN回折ったとき、折り線は2^N-1本になる。
- 切ったときの穴は、隣り合う折り線のどちらか一方にしか開かない。(互い違いに穴が開く。)
- N回折って切ったとき、穴の数は次のどちらかである。
- 紙の中心にある折り線に穴がない場合 … 2^(N-1)
- 紙の中心にある折り線に穴がある場合 … 2^(N-1)-1
- 紙の中心にある折り線の位置は、最後に折った方向の反対側になる (!)
- 折り線の数と、最後に折った方向、切る方向から穴の数が求まる。