[Prolog]各部分の和が等しいように輪を分割するパズル | 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
append([], List, List).
append([Head|Tail], List, [Head|TailR]) :- append(Tail, List, TailR).
部分リスト(List, (I, I), []).
部分リスト(List, (0, End), SubList) :-
    number(End), End > 0, 部分リスト_(List, End, SubList).
部分リスト([Head|Tail], (Bgn, End), SubList) :-
    number(Bgn), Bgn > 0, Bgn1 is Bgn - 1,
    number(End), End > 0, End1 is End - 1,
    部分リスト(Tail, (Bgn1, End1), SubList).
部分リスト_(_, 0, []).
部分リスト_([Head|Tail], Cnt, [Head|TailAcc]) :-
    Cnt > 0, Cnt1 is Cnt - 1, 部分リスト_(Tail, Cnt1, TailAcc).
整数閉区間(L, L, R) :- L =< R.
整数閉区間(N, L, R) :- L =< R, L1 is L + 1, 整数閉区間(N, L1, R).
和([Head|Tail], Sum) :- 和_acc(Tail, Sum, Head).
和_acc([], Sum, SumAcc) :- Sum is SumAcc.
和_acc([Head|Tail], Sum, SumAcc) :- 和_acc(Tail, Sum, Head + SumAcc).
弧(List, (I, I), []).
弧(List, (0, End), Arc) :- 部分リスト(List, (0, End), Arc).
弧(List, (Bgn, 0), Arc) :- length(List, N), 部分リスト(List, (Bgn, N), Arc).
弧(List, (Bgn_, End_), Arc) :-
    number(Bgn_), number(End_), Bgn_ =\= 0, End_ =\= 0,
    length(List, N),
    Bgn is ((Bgn_ mod N) + N) mod N,    % 非負最小剰余
    End is ((End_ mod N) + N) mod N,
    ( Bgn < End
        ->  部分リスト(List, (Bgn, End), Arc)
        ;   弧(List, (Bgn, 0), ArcLead), 部分リスト(List, (0, End), ArcTrail),
            append(ArcLead, ArcTrail, Arc)
    ).
    
輪の等和分割(List, [X|Answer], Div) :-
    和(List, ListSum), ArcSum is ListSum / Div,
    length(List, N),
    整数閉区間(X, 0, N),    % 第一の切断点(の右)
    輪の等和分割(List, [X|Cut], Div, ArcSum, N, N),
    append(Answer, [X], Cut).
    
輪の等和分割(_, [_], 0, _, _, 0).
輪の等和分割(List, [Bgn, End|Cut], Div, Sum, LenFull, LenRemain) :-
    整数閉区間(Len, 1, LenRemain), End is (Bgn + Len) mod LenFull,
    弧(List, (Bgn, End), Arc),
    和(Arc, Sum),
    Div1 is Div - 1, LenRemain1 is LenRemain - Len,
    輪の等和分割(List, [End|Cut], Div1, Sum, LenFull, LenRemain1).
% 例題
    ?- 輪の等和分割( [1, 12, 5, 8, 10, 3, 11, 9, 6, 7, 4, 2], Answer, 3 ).
/*
Answer = [2,6,9].   % つまり 5, 11, 7 の左側 B, F, I で切断する
*/
% ---------------------
% おまけ：特殊バージョン (3分割、数値に重複がないことが条件)
between(L, L, R) :- L < R.
between(N, L, R) :- L < R, L1 is L + 1, between(N, L1, R).
 
隣接(1, 12). 隣接(12, 5). 隣接(5, 8). 隣接(8, 10). 隣接(10, 3). 隣接(3, 11).
隣接(11, 9). 隣接(9, 6). 隣接(6, 7). 隣接(7, 4). 隣接(4, 2). 隣接(2, 1).
 
区間(X, R) :- 隣接(X, R) ; (X \== R, 隣接(R1, R), 区間(X, R1)).
 
弧和(X, R, Sum) :- 区間(X, R), 弧和_acc(X, R, Sum, 0).
弧和_acc(X, X, Sum, SumAcc) :- !, Sum is SumAcc.
弧和_acc(X, R, Sum, SumAcc) :- 隣接(X, X1), 弧和_acc(X1, R, Sum, SumAcc + X).
 
３分割( [X, Y, Z], Sum ) :-
    between(X, 1, 13),
    弧和(X, Y, Sum), 弧和(Y, Z, Sum), 弧和(Z, X, Sum).
 
?- Sum is ((12*(12 + 1))/2) / 3, ３分割(A, Sum).
% A = [5,11,7]  % B, F, I
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX