Created
April 10, 2020 18:27
-
-
Save olivia-banks/7ff6708b4a2ecb58515ca01cd8f63cdc to your computer and use it in GitHub Desktop.
Generalized tower of hanoi in Prolog!
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* README! | |
| * The below prolog code (commented) is the original prolog code before I remembered | |
| * that I had to make it work with six pillars, so I just spent a small bit of time | |
| * (~1.5 hours) making the uncommented code accept any number of pillars. | |
| * | |
| * move(1, X, _, Z, [[X, Z]]). % Base case | |
| * move(N, X, Y, Z, P) :- % To move N disks from X to Z | |
| * M is (N - 1), % we first must move the smaller N-1 disks | |
| * move(M, X, Z, Y, P1), % from X to Y | |
| * move(1, X, Y, Z, P2), % then move the largest disk from X to Z | |
| * move(M, Y, X, Z, P3), % then move the smaller N-1 disks form Y to Z | |
| * append(P1, P2, Q), % we get the corresponding solution | |
| * append(Q, P3, P). % by appding all the steps. | |
| * | |
| */ | |
| /* Here is the actual logic. */ | |
| move(1, A, _, Z, [[A, Z]]). | |
| move(N, A, [H|T], Z, P) :- | |
| M1 is (N - floor(sqrt(2*N + 1)) + 1), | |
| M2 is (N - M1), | |
| move(M1, A, [Z|T], H, P1), | |
| move(M2, A, T , Z, P2), | |
| move(M1, H, [A|T], Z, P3), | |
| append(P1, P2, Q), | |
| append(Q, P3, P). |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I really hope old gists don't get taken down. This one means a lot to me now.