Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Tower of Hanoi
Index -> Contests
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
A.J




PostPosted: Tue Jan 29, 2008 4:32 pm   Post subject: Tower of Hanoi

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
Sponsor
Sponsor
Sponsor
sponsor
MichaelM




PostPosted: Tue Jan 29, 2008 4:43 pm   Post subject: Re: Tower of Hanoi

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




PostPosted: Tue Jan 29, 2008 5:27 pm   Post subject: RE:Tower of Hanoi

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




PostPosted: Wed Jan 30, 2008 6:52 pm   Post subject: Re: Tower of Hanoi

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




PostPosted: Fri Feb 01, 2008 4:43 pm   Post subject: Re: Tower of Hanoi

Are you talking about the 15 puzzle?
A.J




PostPosted: Fri Feb 01, 2008 5:10 pm   Post subject: Re: Tower of Hanoi

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




PostPosted: Fri Feb 01, 2008 6:11 pm   Post subject: Re: Tower of Hanoi

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




PostPosted: Sat Feb 02, 2008 10:41 am   Post subject: Re: Tower of Hanoi

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




PostPosted: Mon Mar 31, 2008 5:25 pm   Post subject: Re: Tower of Hanoi

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




PostPosted: Mon Mar 31, 2008 6:44 pm   Post subject: Re: Tower of Hanoi

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




PostPosted: Tue Apr 01, 2008 4:38 pm   Post subject: Re: Tower of Hanoi

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




PostPosted: Tue Apr 01, 2008 5:45 pm   Post subject: Re: Tower of Hanoi

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




PostPosted: Tue Apr 01, 2008 5:54 pm   Post subject: RE:Tower of Hanoi

Yes, sir. Cool stuff.

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

Do you think you made it?
A.J




PostPosted: Tue Apr 01, 2008 5:56 pm   Post subject: Re: Tower of Hanoi

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 ....... Sad
Sane




PostPosted: Tue Apr 01, 2008 6:12 pm   Post subject: RE:Tower of Hanoi

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.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 18 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: