エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

「どう書く」を最初から解こうとして1問目で脳ミソが煮えそうになった件

Prolog

Prologのトレーニングのために「どう書く」を最初から解いてみようと考えたまではよかったのですが。

1問目で頭から湯気が出そうになりました。


いま使っているPrologの処理系SWI-Prologのライブラリでは、リストをsortすると重複する要素がまとめられてしまいます（Prolog標準ライブラリの仕様なんでしょうか？）。

?- sort([5,4,4,3,3,3,2,2,2,2,1,1,1,1,1], X).
X = [1, 2, 3, 4, 5].


これでは目的とした動作ができないので「M.Hiroi's Home Page / Prolog Programming」からクイックソートを拝借してどうにかこうにか1問を書き下したところ。少し頭冷やさないと次に進める気がしません。ぷしゅぅうう…。

% クイックソートのコード（ qsort/2 および partition/4 )は、
% 下記の「お気楽 Prolog プログラミング入門」から拝借致しました
% http://www.geocities.jp/m_hiroi/prolog/prolog04.html#chap19

partition([X|Xs], Y, [X|Ls], Bs    ) :- X =< Y, partition(Xs, Y, Ls, Bs).
partition([X|Xs], Y, Ls,     [X|Bs]) :- X >  Y, partition(Xs, Y, Ls, Bs).
partition([], _, [], []).

qsort([X|Xs], Ys) :-
        partition(Xs, X, Littles, Bigs),
        qsort(Littles, Ls),
        qsort(Bigs, Bs),
        append(Ls, [X | Bs], Ys).
qsort([], []).

split([], []).
split([_,49,48|Xs], [10|Ys]) :- split(Xs, Ys), !.
split([_,X|Xs],     [Y|Ys])  :- Y is X - 48, split(Xs, Ys), !.

unique([X], [[1,X]]).
unique([X|Xs], [[N,X]|Ys]) :- unique(Xs, [[N1,X]|Ys]), N is N1 + 1.
unique([X|Xs], [[1,X]|Ys]) :- unique(Xs, Ys).

hand([ [1,_], [1,_], [1,_], [2,_] ], "1P") :- !.
hand([ [1,_], [1,_], [3,_] ],        "3K") :- !.
hand([ [1,_], [2,_], [2,_] ],        "2P") :- !.
hand([ [1,_], [4,_] ],               "4K") :- !.
hand([ [2,_], [3,_] ],               "FH") :- !.
hand(_,                              "--") :- !.

solve(X, Y) :- split(X, A), qsort(A, B), unique(B, C), sort(C, D), hand(D, Y), !.

test(X, F, E) :- call(F, X, A), format("expected = ~s, actual = ~s~n", [E, A]), E == A.

sample1 :-
    test("D3C3C10D10S3",  solve, "FH"),
    test("DASAD10CAHA",   solve, "4K"),
    test("S10HAD10DAC10", solve, "FH"),
    test("S3S4H3D3DA",    solve, "3K"),
    test("SASJDACJS10",   solve, "2P"),
    test("H10D10H3HJCK",  solve, "1P"),
    test("S3SJDAC10SQ",   solve, "--").


実行結果。

$ swipl -s sample1.pl -g sample1 -t halt
expected = FH, actual = FH
expected = 4K, actual = 4K
expected = FH, actual = FH
expected = 3K, actual = 3K
expected = 2P, actual = 2P
expected = 1P, actual = 1P
expected = --, actual = --