Commits

Seth Hobson committed e44dccc

Added Towers of Hanoi and max element of list in Prolog

Comments (0)

Files changed (3)

+
+%hanoi(N)- N indicates the number of disks
+hanoi(N) :- buildIntList(N, L), 
+            Start = [left(L), right([]), center([])],
+            End = [_, _, _],
+            SI = [Start],
+            move(N, Start, End, SI, SO), printStates(SO). 
+
+%build a list of N integers
+buildIntList(0, []).
+buildIntList(N, L) :- N > 0, M is N - 1, buildIntList(M, L1), 
+                      append(L1, [N], L).
+
+printStates([]) :- write('solved!').
+printStates([L|Llst]) :- write(L), nl, printStates(Llst).
+
+%move N disks
+%starting configuration of disks: [A, B, C]
+%ending configuration of disks: [AO, BO, CO]
+%starting list of states before move: SI
+%ending list of states after move: SO
+move(N,[A, B, C], [AO, BO, CO], SI, SO ) :- 
+    N > 1, M is N - 1,
+    move(M, [A, C, B], [A1, C1, B1], SI, SO1),
+    move(1, [A1, B1, C1], [A2, B2, C2], SO1, SO2),
+    move(M, [C2, B2, A2], [CO, BO, AO], SO2, SO).
+
+move(1, [A, B, C], [AO, BO, CO], SI, SO) :-
+    A =.. L1, B =.. L2,
+    [A1, [A2|Alst]] = L1, [B1, [B2|Blst]] = L2,
+    XL = [A1, Alst], YL = [B1, [A2, B2|Blst]],
+    AO =.. XL, BO =.. YL, CO = C,
+    append(SI, [[AO, BO, CO]], SO).
+
+move(1, [A, B, C], [AO, BO, CO], SI, SO) :-
+    A =.. L1, B =.. L2,
+    [A1, [A2|Alst]] = L1, [B1, []] = L2,
+    XL = [A1, Alst], YL = [B1, [A2]],
+    AO =.. XL, BO =.. YL, CO = C,
+    append(SI, [[AO, BO, CO]], SO).
+

Prolog/hanoiBrute.pl

+
+%brute force solution constrained by the solution length
+hanoi(N) :- M is round(2**N), buildIntList(N, L), 
+            length(State, M), 
+            move([left(L), center([]), right([])], State), printStates(State). 
+
+buildIntList(0, []).
+buildIntList(N, L) :- N > 0, M is N - 1, buildIntList(M, L1), 
+                      append(L1, [N], L).
+
+printStates([]) :- write('solved').
+printStates([L|Llst]) :- write(L), nl, printStates(Llst).
+
+%everything is on the right
+move([left([]), center([]), right(R)], S) :- S = [[left([]), center([]), right(R)]]. 
+
+%center is empty, left to center
+move([left([L|Llst]), center([]), right(R)], [S|Slst]) :- 
+     S = [left([L|Llst]), center([]), right(R)], 
+     move([left(Llst), center([L]), right(R)], Slst).
+
+%right is empty, left to right
+move([left([L|Llst]), center(C), right([])], [S|Slst]) :- 
+     S = [left([L|Llst]), center(C), right([])], 
+     move([left(Llst), center(C), right([L])], Slst).
+
+%left < center, left to center
+move([left([L|Llst]), center([C|Clst]), right(R)], [S|Slst]) :- 
+     L < C,  S = [left([L|Llst]), center([C|Clst]), right(R)],
+     move([left(Llst), center([L, C|Clst]), right(R)], Slst).
+
+%left < right, left to right
+move([left([L|Llst]), center(C), right([R|Rlst])], [S|Slst]) :- 
+     L < R,  S = [left([L|Llst]), center(C), right([R|Rlst])],
+     move([left(Llst), center(C), right([L,R|Rlst])], Slst).
+
+
+%left is empty, center to left
+move([left([]), center([C|Clst]), right(R)], [S|Slst]) :- 
+     S = [left([]), center([C|Clst]), right(R)], 
+     move([left([C]), center(Clst), right(R)], Slst).
+
+%right is empty, center to right
+move([left(L), center([C|Clst]), right([])], [S|Slst]) :- 
+     S = [left(L), center([C|Clst]), right([])], 
+     move([left(L), center(Clst), right([C])], Slst).
+
+%center < left, center to left
+move([left([L|Llst]), center([C|Clst]), right(R)], [S|Slst]) :- 
+     C < L,  S = [left([L|Llst]), center([C|Clst]), right(R)],
+     move([left([C, L|Llst]), center(Clst), right(R)], Slst).
+
+%center < right, center to right
+move([left(L), center([C|Clst]), right([R|Rlst])], [S|Slst]) :- 
+     C < R,  S = [left(L), center([C|Clst]), right([R|Rlst])],
+     move([left(L), center(Clst), right([C,R|Rlst])], Slst).
+
+
+%left is empty, right to left
+move([left([]), center(C), right([R|Rlst])], [S|Slst]) :- 
+     S = [left([]), center(C), right([R|Rlst])], 
+     move([left([R]), center(C), right(Rlst)], Slst).
+
+%center is empty, right to center
+move([left(L), center([]), right([R|Rlst])], [S|Slst]) :- 
+     S = [left(L), center([]), right([R|Rlst])], 
+     move([left(L), center([R]), right(Rlst)], Slst).
+
+%right < left, right to left
+move([left([L|Llst]), center(C), right([R|Rlst])], [S|Slst]) :- 
+     R < L,  S = [left([L|Llst]), center(C), right([R|Rlst])],
+     move([left([R, L|Llst]), center(C), right(Rlst)], Slst).
+
+%right < center, right to center 
+move([left(L), center([C|Clst]), right([R|Rlst])], [S|Slst]) :- 
+     R < C,  S = [left(L), center([C|Clst]), right([R|Rlst])],
+     move([left(L), center([R, C|Clst]), right(Rlst)], Slst).
+
+
+max([X],X).
+max([H|T],Mt) :- max(T,Mt), Mt > H.
+max([H|T],H) :- max(T,Mt), H >= Mt.