Tower of Hanoi

[A.J]

I was thinking of holding a contest to see the most efficient tower of hanoi solver program (that outputs every move and states the number of moves)
I finished it in turing in 13 lines, but I am pretty sure there are shorter and better ways to do it than what I did

[MichaelM]

Well theres always wikipedia for an answer: http://en.wikipedia.org/wiki/Tower_of_Hanoi

[zylum]

code:

var i := 1 proc hanoi (n, f, t, u : int)     if n > 0 then         hanoi (n - 1, f, u, t)         put "move ", i, ": ", f, " to ", t         i += 1         hanoi (n - 1, u, t, f)     end if end hanoi hanoi (6, 1, 3, 2)

Straight from the wiki page..

[A.J]

OOps!!
i completely forgot about wikipedia

thanks for reminding me guys!!!

how about a sliding puzzle program puzzle???

I am currently trying to learn the heuristic method of solving it
if anyone who is reading this right now is able to help me, please write out an example in turing (i also have a topic on the turing help forum about this)

thanks a LOT

[klopyrev]

Are you talking about the 15 puzzle?

[A.J]

yes, but in this case it can be any defined size (hence the name n-puzzle)
if you can help me with the heuristic part, I'll be thankful (check out the turing help forum, 'Help neede regarding heuristic algorithms', or something like that)

[klopyrev]

The 8 puzzle can be solved without using heuristics. However, the 15 puzzle can't. There are too many states. One of the heuristics I know of and have successfully used to solve the problem is sum of the distances of each of the pieces to their needed positions. If you need help with the actual algorithm, consider this:

http://en.wikipedia.org/wiki/A%2A

[A.J]

how do you assign each node the g(n) without visiting it ? (since it is the distance from the beginning node to that node)

[Sane]

You guys might be interested to hear that this was the S5 question in Hong Kong's CCC for 2008:
http://www.cs.hku.hk/ccc2008/questions/Senior08.pdf

The only difference is it uses 4 polls instead of 3, which turns it into a very different problem. This problem is sometimes called "Reve's puzzle".

The official solution offered by Hong Kong's CCC is here:
http://www.cs.hku.hk/ccc2008/questions/Senior08_sol.zip

The funny thing is, according to Wikipedia, the CCC's official solution has not yet been proven to be optimal.

Quote:

A solution for four (or more) pegs, which has not been proved to be optimal, is described below:

...

For some 1 <= k < n, transfer the top k disks to a single other peg, taking T(k,r) moves.
Without disturbing the peg that now contains the top k disks, transfer the remaining n − k disks to the destination peg, using only the remaining r − 1 pegs, taking T(n − k,r − 1) moves.
Finally, transfer the top k disks to the destination peg, taking T(k,r) moves.

...

2T(k,r) + T(n − k,r − 1), Minimize k

http://en.wikipedia.org/wiki/Tower_of_Hanoi

And from the official solution:

Quote:

g(n) = min{ 2 * g(k) + f(n - k), 1 <= k < n }

Tsk tsk on CCC for putting such a difficult (not to mention open) problem on the CCC.
But at least their solution achieves the correct output, despite it not yet being proven.

[A.J]

I did that about a week back........yeah I remember their solution being not proven yet........

[Sane]

Here's the official solution:

CPP:

#include <iostream> #include <fstream> #include <vector> using namespace std; int f(int i){   return (1 << i) - 1; } int main(){   ifstream ifile("s5.in", ios::in);   ofstream ofile("s5.out", ios::out);   vector<int> g;   // g(n) = min{ 2 * g(k) + f(n - k), 1 <= k < n }   //         k   g.push_back(0);   g.push_back(1);   for (int i = 2; i < 359; ++i){     int j;     int t = 2 * g[i - 1] + f(1);     for (j = 2; j < i; ++j){       int u = 2 * g[i - j] + f(j);       if (u < t)         t = u;       else         break;     }     g.push_back(t);     //    ofile << i << ',' << j - 1 << ':' << t << endl;   }     int k;   ifile >> k;   while (k--){     int n;     ifile >> n;     ofile << g[n] << endl;   }   }

And here's my solution. I feel it's more intuitive, better commented, and more consistent with the recursive algorithm and definition.

The hint in the problem statement specifies to use k discs for the four pole swaps, and n-k disks for the three pole swap. Then minimize k. However, the official solution, for whatever reason, decided to reverse this. It's a little confusing at first, but you get the same answer of course.

The official solution also does not explain why they can break while minimizing k. I assumed varying k's get pseudo-random values of moves. But it is actually a bimodal distribution with consistently increasing values to both sides of the minimum value k. Thus, you can exit the loop as soon as you don't find any smaller k. In fact, if you don't quit early, your algorithm fails as soon as it tries to left shift 32. That's one part that makes this question one of the toughest I've seen. You have to realize that you don't need to test every possible value of k.

Their solution also does some other silly things. But it's not worth getting into. I hope this benefits someone:

C:

#include <stdio.h> #include <stdlib.h> #define threepoles(n) ((1 << (n)) - 1) unsigned long cache[301] = {0}; unsigned long fourpoles(n) {     unsigned long k, r, moves;     if(cache[n]) return cache[n];     r = 1;     for(k=n-1; k>=1; k--) { // Start k large, so that threepoles(n-k) is small             // Move k pieces on 4 poles, n-k pieces on 3 poles, then k pieces on 4 poles         moves = 2 * fourpoles(k) + threepoles(n-k);                 // As k changes, the # of moves decreases then increases in a bimodal distribution         // We want the first value that has no smaller value proceeding it (the smallest k)         if(r==1 || moves < r) r = moves;         else break; // Stop once we've found the smallest k value                     // That optimization is necessary or else the program will fail when it 2^n-1 ifies large values of n     }     return cache[n] = r; } int main() {     int n, t;         freopen("s5.in", "rt", stdin);     freopen("s5.out", "wt", stdout);         scanf("%d\n", &t);     while(t--) {         scanf("%d\n", &n);         printf("%d\n", fourpoles(n));     }         return 0; }

[A.J]

thats pretty cool.....wait....aren't you Aaron Voelker from the MMHS page?
I'm Amlesh Jayakumar from MMHS too

[Sane]

Yes, sir. Cool stuff.

I'm so anxious for the CCC results. Just one more day!

Do you think you made it?

[A.J]

I don't think so, since I only started programming this November (I'm in Gr.10) and I did everything right except for forgetting to save #4 and forgetting to check #2........................it was a bad day for me .......

[Sane]

Yikes. At least you're in grade 10. My first shot at the CCC was this year in grade 12. No second tries for me.

Just think of it as experience. If you live up to the potential you seem to have, you could nail perfect next year or the year after no problem.