マッチ棒を動かして10を3つ作るパズル | Codetter（こーどったー）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
一要素置換([Bef|Tail], [Aft|Tail], (Bef, Aft)).
一要素置換([X|BefTail], [X|AftTail], Replace) :-
    一要素置換(BefTail, AftTail, Replace).
% デジタル文字の定義
デジタル文字(X) :- デジタル文字(X, _).
デジタル文字((number, Ptn),   Char) :- デジタル数字((number, Ptn), Char).
デジタル文字((operator, Ptn), Char) :- デジタル演算子((operator, Ptn), Char).
デジタル数字((number, [1, 1, 1, 1, 0, 1, 1]), 0).       % 8 の各所に対応するマッチ棒の有無を表すリスト
デジタル数字((number, [0, 0, 1, 0, 0, 1, 0]), 1).
デジタル数字((number, [0, 1, 1, 1, 1, 0, 1]), 2).
デジタル数字((number, [0, 1, 1, 0, 1, 1, 1]), 3).
デジタル数字((number, [1, 0, 1, 0, 1, 1, 0]), 4).
デジタル数字((number, [1, 1, 0, 0, 1, 1, 1]), 5).
デジタル数字((number, [1, 1, 0, 1, 1, 1, 1]), 6).
デジタル数字((number, [1, 1, 1, 0, 0, 1, 0]), 7).       % “ワ”型
デジタル数字((number, [1, 1, 1, 1, 1, 1, 1]), 8).
デジタル数字((number, [1, 1, 1, 0, 1, 1, 1]), 9).
デジタル演算子((operator, [1, 1, 0, 0]), '+').
デジタル演算子((operator, [0, 1, 0, 0]), '-').
デジタル演算子((operator, [0, 0, 1, 1]), '*').      % ×
%デジタル演算子((operator, [0, 0, 0, 1]), '/').     % ／
デジタル文字列([]).
デジタル文字列([Head|Tail]) :- デジタル文字(Head), デジタル文字列(Tail).
デジタル文字列([], []).
デジタル文字列([DH|DigitString], [H|String]) :-
    デジタル文字(DH, H), デジタル文字列(DigitString, String).
棒を1本加える((Type, Ptn), (Type, PtnAfter)) :- % 入出力がデジタル文字かは無視
    一要素置換(Ptn, PtnAfter, (0, 1)).
棒を1本減らす((Type, Ptn), (Type, PtnAfter)) :-
    一要素置換(Ptn, PtnAfter, (1, 0)).
棒を1本動かす(Chars, CharsAfter) :-
    棒を1本減らす(Chars, CharsTmp1),
    棒を1本加える(CharsTmp1, CharsAfter),
    Chars \== CharsAfter.
棒を1本加える([Char|Tail], [CharAfter|Tail]) :-
    棒を1本加える(Char, CharAfter).
棒を1本加える([X|CharsTail], [X|CharsAfterTail]) :-
    棒を1本加える(CharsTail, CharsAfterTail).
棒を1本減らす([Char|Tail], [CharAfter|Tail]) :-
    棒を1本減らす(Char, CharAfter).
棒を1本減らす([X|CharsTail], [X|CharsAfterTail]) :-
    棒を1本減らす(CharsTail, CharsAfterTail).
% 数式化 (ただし加減乗除 + - * / のみ)
数式化([X, Op1, Y, Op2, Z], Expr) :-
    current_op(Op1Priority, _, Op1),
    current_op(Op2Priority, _, Op2),
    Op1Priority =< Op2Priority
        -> ( Expr1 =.. [Op1, X, Y], Expr =.. [Op2, Expr1, Z] )
        ;  ( Expr1 =.. [Op2, Y, Z], Expr =.. [Op1, X, Expr1] ).
        
%   ?- 数式化([1, '+', 2, '+', 3], X).
%   ?- 数式化([1, '*', 2, '+', 3], X).
%   ?- 数式化([1, '+', 2, '*', 3], X).
%   ?- 数式化([1, '*', 2, '*', 3], X).
% 長さからリストを単一化できる述語 (AZ-Prolog の length にはその機能がない故)
mylen([], 0).
mylen([_|Tail], N) :- N > 0, N1 is N - 1, mylen(Tail, N1).
append([], L, L).
append([H|T1], L, [H|T2]) :- append(T1, L, T2).
append_fold([], []).
append_fold([H|Tail], Sum) :- append_fold(Tail, TailSum), append(H, TailSum, Sum).
% 例題
?-  Q = [
        5, '-', 1, '+', 4,
        4, '*', 7, '-', 5,
        6, '-', 4, '+', 8
    ],
    % A は、Q のデジタル文字列の棒を3本動かしてできるデジタル文字列で表現できる
    デジタル文字列(Enc0, Q),
    棒を1本動かす(Enc0,  Enc1),
    棒を1本動かす(Enc1, Enc2), Enc0 \== Enc2,
    棒を1本動かす(Enc2, Enc3), Enc0 \== Enc3, Enc1 \== Enc3,
    デジタル文字列(Enc3, A),
%   write(A), nl,
    
    % 3つの式の答えがすべて10である
    mylen(A1, 5), mylen(A2, 5), mylen(A3, 5),
    append_fold([A1, A2, A3], A),
    数式化(A1, E1), 10 is E1,   % E1 is 10 ではない
    数式化(A2, E2), 10 is E2,
    数式化(A3, E3), 10 is E3.
% 答えはおそらくこの2通り
% A = [7,-,1,+,4,4,*,4,-,6,6,-,4,+,8]
% A = [5,+,1,+,4,1,*,7,+,3,6,-,4,+,8]
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX