問題はこちら: http://mtsmfm.github.io/2017/06/03/doukaku-e14.html
みなさんの回答はこちらから: http://qiita.com/mtsmfm/items/89b6634f363bbf5b47f5
いつものように Prolog で書いてみました。
今回の問題は、入力が与えられてそれが受理されるか否か(true
が返るか false
が返るか)という内容で、実は Prolog で解きやすい問題だったということに後から気づきました。
解法は 鍋谷さんのアイディア を拝借しています。中段 4 面、上下に 1 面ずつのケースで、1 面の位置が端か否かでわけて 5 つに場合わけしていますが内容は同じです。
Prolog ではパタンを羅列していずれかのパタンが受理されればよいので、ロジック上の分岐やループが不要になります。split
と transpose
で再帰を使っていますが、問題を解く部分では再帰も不要になっています。
GNU-Prolog で動作確認をしています。次のように入力すると実行できます。
$ gprolog --consult-file orde14.pro --entry-goal 'main, halt'
orde14.pro
% $ gprolog --consult-file orde14.pro --entry-goal 'main, halt'
% 文字列を ',' で分ける
split(Input, [Row|Rows]) :- append(Row, [0',|Rest], Input), split(Rest, Rows), !.
split(Row, [Row]).
% transpose の補助:先頭の要素と後続の要素に分ける
list_first_rest([First|Rest], First, Rest).
% リストのリストを転置する。リストの長さは揃っているが前提
transpose([[]|_], []).
transpose(L, [F|FS]) :- maplist(list_first_rest, L, F, R), transpose(R, FS).
% 反転する。上下反転、左右反転、対角反転を 0〜1 回の回数で組み合わせる。すべて 0 回(反転しない)も含む
flip(A, A).
flip(A, B) :- reverse(A, B).
flip(A, B) :- maplist(reverse, A, B).
flip(A, B) :- maplist(reverse, A, C), reverse(C, B).
flip(A, B) :- transpose(A, B).
flip(A, B) :- transpose(A, C), reverse(C, B).
flip(A, B) :- transpose(A, C), maplist(reverse, C, B).
flip(A, B) :- transpose(A, C), maplist(reverse, C, D), reverse(D, B).
% Offset の位置から Length 分の要素を Source のリストから取り出したものが Extract になる
extract(Offset, Length, Source, Extract) :-
append(Left, MidRight, Source),
append(Extract, _Right, MidRight),
length(Left, Offset),
length(Extract, Length).
% 幅 Width 、高さ Height の範囲を Rectangle から取り出したものが SubRectangle になる
subrectangle(Width, Height, Rectangle, SubRectangle) :-
extract(_, Height, Rectangle, Rows),
maplist(extract(_, Width), Rows, SubRectangle).
% 幅 5 、高さ 2 あるいは 幅 4 、高さ 3 の範囲を Rectangle から取り出したものが SubRectangle になる
subrectangle(Rectangle, SubRectangle) :- subrectangle(5, 2, Rectangle, SubRectangle).
subrectangle(Rectangle, SubRectangle) :- subrectangle(4, 3, Rectangle, SubRectangle).
% 6 面の内容がサイコロとして成立するばあいに受理される
dice_faces(A1, A2, B1, B2, C1, C2) :-
sort([A1, A2, B1, B2, C1, C2], "123456"),
forall(member(Pair, [[A1, A2], [B1, B2], [C1, C2]]), member(Pair, ["16", "25", "34", "43", "52", "61"])).
% 展開図として成立するばあいに受理される
% 1) 3 段で、面の数が 1:4:1 のケース(上段の 1 が端のケース)
development([[A1|_], [B1, C1, B2, C2], A2S]) :- member(A2, A2S), dice_faces(A1, A2, B1, B2, C1, C2).
% 2) 3 段で、面の数が 1:4:1 のケース(上段の 1 が端にないケース)
development([[_, A1|_], [B1, C1, B2, C2], [_, A21, A22, _]]) :- member(A2, [A21, A22]), dice_faces(A1, A2, B1, B2, C1, C2).
% 3) 3 段で、面の数が 2:3:1 のケース
development([[A1, B1|_], [_, C1, A2, C2], [_|B2S]]) :- member(B2, B2S), dice_faces(A1, A2, B1, B2, C1, C2).
% 4) 3 段で、面の数が 2:2:2 のケース
development([[A1, B1|_], [_, C1, A2, _], [_, _, B2, C2]]) :- dice_faces(A1, A2, B1, B2, C1, C2).
% 2) 2 段で、面の数が 3:3 のケース
development([[A1, B1, A2|_], [_, _, C1, B2, C2]]) :- dice_faces(A1, A2, B1, B2, C1, C2).
% サイコロできるばあいに受理される
makeable(Input) :- % サイコロできると受理されるには、
split(Input, Paper), % 入力をコンマで分割して、
flip(Paper, Variation), % 向きを変えたりひっくり返したりして、
subrectangle(Variation, Subrectangle), % 展開図が収まる範囲を取り出して、
development(Subrectangle). % 展開図として受理されればよい。
% サイコロできるばあいは "true" 、そうでないばあいは "false"
solve(Input, "true") :- makeable(Input), !.
solve(_, "false").
% 以下、テスト用コード
% 判定結果表示
judge(_, Expected, Expected) :-
format("\x1b\[32m~s\x1b\[0m~n", ["passed"]),
!.
judge(Input, Expected, Actual) :-
format("\x1b\[31mfailed input: ~s, expected: ~s, actual: ~s\x1b\[0m~n", [Input, Expected, Actual]),
!.
% テスト実行
test(Input, Expected) :-
solve(Input, Actual),
judge(Input, Expected, Actual).
% エントリポイントおよびテストパタン(追加分含む)
main :-
test("44165,44516", "false"),
test("26265,31436", "true"),
test("46345,54215", "true"),
test("62143,11152", "false"),
test("4242,4314,1562", "false"),
test("5612,3656,4523", "false"),
test("5514,1311,5252", "false"),
test("5262,4631,2644", "true"),
test("6626,3324,2644", "false"),
test("4645,6314,2564", "true"),
test("54,65,23,21,14", "true"),
test("5325,3641,1335", "true"),
test("4163,2156,2553", "true"),
test("3126,6543,4352", "false"),
test("4464,5423,5216", "true"),
test("3564,3634,5631", "false"),
test("4363,3454,2126", "true"),
test("25,25,33,12,52", "false"),
test("1551,4542,3624", "true"),
test("6623,4126,6331", "false"),
test("2432,6215,1623", "true"),
test("1151,6555,3616", "false"),
test("2466,1242,4444", "false"),
test("5646,1463,4244", "true"),
test("1255,6413,4534", "true"),
test("1325,2312,2425", "false"),
test("2544,6413,4656", "true"),
test("1656,4131,3235", "true"),
test("6332,3631,4113", "false"),
test("4525,2151,2336", "true"),
test("1645,2356,4314", "true"),
test("3334,6215,1553", "true"),
test("2622,5251,5165", "false"),
test("1111,5613,3451", "false"),
test("6146,4512,6353", "true"),
test("2455,3312,6461", "false"),
test("1221,1325,1422", "false"),
test("1562,2236,5212", "false"),
test("6622,3324,5155", "true"),
test("2352,4631,1236", "true"),
test("4645,2252,6554", "false"),
test("3542,6515,1231", "true"),
test("12,61,56,45,23", "false"),
test("4643,6522,3625", "false"),
test("1151,1642,4512", "false"),
test("5423,5146,2212", "false"),
test("6224,3412,5653", "true"),
test("3122,5423,6231", "true"),
test("5421,2351,6513", "false"),
test("5652,3542,3313", "true"),
test("5524,3335,1146", "false"),
test("5311,4126,6425", "true"),
test("15,43,62,42,14", "true"),
test("3631,3542,3265", "true"),
test("1232,5364,6135", "true"),
test("2441,4644,5433", "false"),
test("2213,5621,3412", "true"),
test("6644,1264,1235", "true"),
test("5613,1423,6315", "true"),
test("6552,1546,2141", "false"),
test("5623,1461,5645", "true"),
test("1442,1436,6362", "false"),
test("3443,5145,4546", "false"),
test("1244,1313,2316", "false"),
test("2152,1463,2114", "true"),
test("1211,6234,5561", "false"),
test("4152,1252,3142", "false"),
test("6645,1231,6122", "false"),
test("353,241,121,536", "true"),
test("224,444,651,234", "true"),
test("643,214,244,343", "false"),
test("624,542,214,333", "true"),
test("441,426,536,656", "true"),
test("564,642,513,364", "true"),
test("422,136,414,416", "false"),
test("463,356,113,662", "true"),
test("464,515,435,462", "true"),
test("531,145,364,525", "false"),
test("623,564,153,633", "false"),
test("335,462,531,424", "false"),
test("131,111,535,436", "false"),
test("435,414,423,365", "true"),
test("144,512,332,346", "true"),
test("342,246,342,634", "false"),
test("246,566,431,415", "true"),
test("444,554,234,621", "true"),
test("313,624,165,652", "true"),
test("563,262,545,315", "true"),
test("213,264,154,264", "false"),
test("364,434,246,113", "false"),
test("411,656,325,225", "false"),
test("624,234,115,443", "true"),
test("252,214,635,154", "false"),
test("146,213,525,164", "false"),
test("456,423,112,352", "true"),
test("253,156,111,355", "false"),
test("252,161,562,365", "false"),
test("136,553,544,524", "true"),
test("414,351,161,525", "true"),
test("261,442,111,531", "true"),
test("323,664,454,133", "true"),
test("213,415,225,165", "false"),
test("363,162,165,533", "false"),
test("346,441,315,241", "false"),
test("121,312,155,164", "true"),
test("123,311,452,365", "true"),
test("361,145,212,431", "true"),
test("451,264,412,513", "false"),
test("311,456,263,226", "true"),
test("343,442,624,635", "false"),
test("534,644,234,251", "false"),
test("515,346,462,435", "true"),
test("445,126,165,636", "false"),
test("343,355,126,353", "false"),
test("623,533,256,144", "true"),
test("125,341,566,416", "false"),
test("354,434,621,411", "true"),
test("356,435,253,114", "false"),
test("141,265,533,514", "true"),
test("613,426,142,535", "true"),
test("366,322,413,325", "true"),
test("331,542,343,545", "false"),
test("261,512,563,123", "false"),
test("242,132,656,164", "true"),
test("133,545,441,665", "false"),
test("111,151,621,545", "false"),
test("132,154,234,653", "false"),
test("114,455,635,511", "false"),
test("14366,64254,66664,42611,41245", "false"),
test("41114,53116,13122,66613,35111", "false"),
test("22146,34244,16154,62531,51426", "true"),
test("464316,136563,136326,535655,641161,252655", "true"),
test("166255,615452,261224,533566,323335,556213", "false"),
test("126665,245653,343553,254661,365415,361154", "false"),
test("1512663,1525531,5456426,6336325,4324465,6512242,4112466", "true"),
test("2236563,6644542,4425515,6641142,4214543,1156426,3225413", "false"),
test("5545354,6566343,3525411,5356165,4625265,1535435,5522665", "false"),
test("16161,61616,16161", "false"),
test("2431,6354,2341", "false").