Slashdot Mirror
108 Ways To Do The Towers of Hanoi
hlarwood74 writes "While it is common to program in a few different languages, somebody has written "towers of hanoi" in 108 different ways, most of them in different programming languages. It's not just the number of languages though ... there are many neat implementations and in some cases he's come up with some strange ways of solving hanoi such as this: "you ping the hanoi machine with the number of disks encoded in the type of service field, and you get response packets whose sequence numbers represent the disk moves need to solve the puzzle". I wanted to ask "why" but the title of the page (hanoimania) explains a few things :)"
nt
Is this truly the only Earth I can live on?
When someone works out every single way to solve the problem, the towers will crumble to dust and the world will vanish
"you ping the hanoi machine with the number of disks encoded in the type of service field, and you get response packets whose sequence numbers represent the disk moves need to solve the puzzle"
ping HanoiServer -tos=128
Send one packet, get a hundred thousand (I'm sure I lost count somewhere) in return?
Visit CryptoGnome in his home.
Hmm, not all the important languages are represented in the list. I didn't see e.g. whitespace implementation.
Here it is coded in Whitespace:
If I seem short sighted, it is because I stand on the shoulders of midgets
...Brainfuck?
Converting the Towers of Hanoi syntax into 108 different languages?
Visual Studio.NET includes a standard wizard for that.
I hope you and your piece of overpriced proprietary slow-as-molasses crap will be happy together.
http://www2.latech.edu/~acm/HelloWorld.shtml
The Hello World page.
The difference? The examples on the Hello World page all have source code. Hanoimania... Not so.
But.... solving the Towers of Hanoi shows a lot more of the programming environment than Hello World does... Conditionals, branching, recursion, function calls...
So which one of these should I run if I want to view it animated in X11?
No language comparison is complete without Intercal.
Actually, as a geek I agree with this post.
If we banded our collective talents together we could produce things much more useful than Hanio ICMP servers and blue LED case mods. Such as world peace or cost-effective nuclear fission.
After all, geeks are more intelligent than other people. Our failing is our inability to socialise coherently.
Try Austria in Vienna. That is, without a doubt, the gay capital of Europe.
to the joy of millions of 1st year Computer Science students.
Sig it.
This is useful to him, RTFA.
In fact, while this has gone to an extream, a many developers have a pet progam they implement anytime they run across a new language/platform. This give the programmer a familiar program to implement in an unfamiliar environment. A great way to get your feet wet with something new. Whenever I start working with a new language or on a new platform, I have a game I implement that covers many of the basic program constructs. By the time I have finished the game I have a good enough working knowledge of teh new language and/or platform to begin some real work.
Here is the same basic explination from the web page (I am assuming it will get slashdotted soon):
I am often asked that since I do all this, whether I have a lot of free time on my hands. Between my work and my interests (both of which overlap to a great extent), I actually have no free time. As an aside, I would not (and should not) be expected to "know" so many programming languages, and I don't think I do! However, I do believe that knowing a computer language is a rather fuzzy idea. If one could write a useful (loosely speaking, again) program in a given language, it is instructive to question whether one knows it. It is ironical (yes, there is such a word) that the bigger challenge, at least in my opinion, lies not in writing programs in all these different languages and ways, but in rapidly setting up the respective compiler systems and/or development environments on an appropriate platform/operating system. Sometimes compilers, interpreters and other such software for a particular language may be readily available, and run "out of the box", but many times this is not the case. Sometimes it turns out to be a non-trivial problem to get a compiler to function (pun unintended). Of course, once you get past this, you do have to understand some subset of the language!
...when the C version is so simple? He could have used the C version for both. Even if he was trying to show off the features of the
language the C++ version is still way overkill.
Is it just me or does the Haskell one seem to have inverted parameters wrt the vanilla Perl one? Not that I know Haskell.. I was hoping to see some lexical wierdness in Perl and some lambdas and arrows all hanging out for the Haskell one. And wha-hey no smalltalk? well the world goes on..
Neat idea, I like to see how things are done in other languages. It would be an interesting and intuitive way to show people what other languages are like, a list of programs the same in each language, plus commentary about the highlights of the language that are used.
...he said in a posting on slashdot.
I think we have recursion going on here.
The path I walk alone is endlessly long.
30 minutes by bike, 15 by bus.
You can program anything in RLL. Not that you'd want to--but your Client probably wants you to.
"Reality is that which, when you stop believing in it, it doesn't go away." - Philip K. Dick
Our failing is our inability to socialise coherently
Which would be a large part of what makes us geeks.
-
"Vengeance is fine," sayeth the Lord.
I did this in MetaPost a few months ago. Check out my posting in comp.text.tex.
I once did a 3D-visualized Prolog implementation of the towers of Hanoi for a course assignment. It used the VR system DIVE for visualization, the Hanoi implementation was a simple proof of concept of the rudimentary Prolog interface to DIVE that was the actual assignment... Sweet memories :)
(Un?)fortunately, the code is not publicly available.
I've solved the towers of hanoi with 8 disks.. Curious if anyone has solved a more insane number without computer assistance.
Though it seems pretty pointless and boring to solve for a high number of disks as the learning curve drops sharply after you figure out how to solve for the basic three disks.
A witty saying proves you are wittier than the next guy.
max = 1 no_of_discs;
for (x = 1; x max; x++)
printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);
where is the quakec implementation? This would make quite the interesting demonstration.
http://www.towersofhanoi.org
A musician without the RIAA, is like a fish without a bicycle.
A musician without the RIAA, is like a fish without a bicycle.
Try this...A musician without the RIAA is like a fish without a hook.
The RIAA is actually harmful. The original quote suggested simply that women didn't need men. (Also that women were slimy scaly smelly creatures and men were carefully engineered tools of great craftsmanship, but I digress...)
Yeah, God forbid that a geek ever try to have fun.
One neat thing I discovered about the towers of hanoi is that the sequence of disks to move for a solution
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5...
is the exact same sequence that you get when you look at the number of bits flipped between consecutive binary numbers (i.e.
00000->00001 (1 flip),
00001->00010 (2 flips),
00010->00011 (1 flip),
00011->00100 (3 flips),
00100->00101 (1 flip),
00101->00110 (2 flips)
etc... (1,2,1,3,1,2,...)
The reason it works is because just like the towers of hanoi algorithm, when the general solution to move n disks is:
Recursively solve the puzzle for n-1 disks
Take the nth disk and move it to the goal
Recursively solve the puzzle for n-1 disks.
The bit flipping goes like this:
While the nth bit is 0, the solution works for the n-1 disk solution
When we go from 011111 (n-1 1's) to 10000000 (n-1 0's) we flip n bits
Then the nth bit stays 1 and we repeat the solution for the n-1 disks.
Rhymes that keep their secrets will unfold behind the clouds.There upon the rainbow is the answer to a neverending story
Do you think that this problem is representative of the language? e.g. Perl is more efficient than PHP. Or is this going about it all wrong because of the specialisation of programming? Perhaps a series of tests consisting of different types of problems would be possible?
This is my digital signature. 10011011001
As an XSL guy, I felt left out. So, given this xml:
<?xml version="1.0"?>
<hanoi>
<arg n="3"/>
</hanoi>
you can transform with this:
<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:template match="/">
<xsl:variable name="n">
<xsl:value-of select="//arg/@n"/>
</xsl:variable>
<xsl:element name="hanoi-solve">
<xsl:call-template name="dohanoi">
<xsl:with-param name="n" select="number($n)"/>
<xsl:with-param name="to" select="3"/>
<xsl:with-param name="from" select="1"/>
<xsl:with-param name="using" select="2"/>
</xsl:call-template>
</xsl:element>
</xsl:template>
<xsl:template name="dohanoi">
<xsl:param name="n"/>
<xsl:param name="to"/>
<xsl:param name="from"/>
<xsl:param name="using"/>
<xsl:if test="number($n) > 0">
<xsl:call-template name="dohanoi">
<xsl:with-param name="n" select="number($n) - 1"/>
<xsl:with-param name="to" select="$using"/>
<xsl:with-param name="from" select="$from"/>
<xsl:with-param name="using" select="$to"/>
</xsl:call-template>
<xsl:element name="move">
<xsl:attribute name="from">
<xsl:value-of select="$from"/>
</xsl:attribute>
<xsl:attribute name="to">
<xsl:value-of select="$to"/>
</xsl:attribute>
</xsl:element>
<xsl:call-template name="dohanoi">
<xsl:with-param name="n" select="number($n) - 1"/>
<xsl:with-param name="to" select="$to"/>
<xsl:with-param name="from" select="$using"/>
<xsl:with-param name="using" select="$from"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
</xsl:stylesheet>
I remember decades ago coming across the towers of Hanoi built with wooden dowels and hardwood disks with holes in them. This was late one evening when everyone else had retired.
After playing around with it for a few minutes, my mind just naturally got into the algorithm. The disks were flying around with hardly any conscious thought required on my part.
Just one of those cool game zombie states...
Probably because I'm prone to addictive behaviors I tend to avoid getting involved too closely with games; but I still remember the great buzz of doing Towers of Hanoi the first time.
[There's another hardware puzzle, like a Chinese lock with multiple loops, that's similarly fun for the recursively minded.]
"Provided by the management for your protection."
The person that wrote it sure did not have a firm grasp of Lisp. The use of eval was completely bogus. In any case, eval takes one argument, not three.
This is a better one that actually works. I would have posted it here in the comment, but you can't format code in slashdot.
Imagine the disk are in a cricle. Repeat:
- move the smallest disk one step clockwise
- do the only legal move not involving the smallest disk
Much easier to remember and perform by hand than the various iterative C programs posted. The proof that it works is left as an exercise to the reader...The guy's Resume says that he works on Linux on the Desktop at IBM's research lab.
Interesting to see IBM working with Linux on the Desktop at all.
Gravatite and I like to code Combsort when we're learning a new language. Combsort a very simple modification to bubblesort that makes it competative with Quicksort but without quite as much complexity -- it's good for those rare occasions where you have to hand-code a sort and don't need all the fuss of quicksort.
I've done combsort in about a dozen dozen languages, and Gravatite has done it in a few more languages, including postscript.
His page also contains the best review of a PowerBook 17" that I've ever read.
"I tend to think of OS X as Linux with QA and Taste", James Gosling, creator of Java
Malbolge, Programming From Hell
That's the worst C++ feature-masturbation I've ever seen.
Here's a version using C++ template metaprogramming I just whipped up:
#include <iostream>
template <int N, int From, int To, int Using>
class HanoiSolver
{
public:
static void solve()
{
HanoiSolver<N-1, From, Using, To>::solve();
std::cout << "Move " << From << " to " << To << std::endl;
HanoiSolver<N-1, Using, To, From>::solve();
}
};
template <int From, int To, int Using>
class HanoiSolver<0, From, To, Using>
{
public:
static void solve()
{
}
};
int main()
{
HanoiSolver<10, 1, 2, 3>::solve();
}
I thought of 108 Ways To Do The Girls of Hanoi.
Much more, uh, arousing.
at one moment of the game, you have to resolve this kind of problem in Black & White.
Back in the late '70s, me and some friends came up with a solution that is more honestly non-recursive:
Move the smallest disk to the right (cyclically). If the other two stacks are empty, you're done, else move the smallest top disk of the two stacks to the other stack (the only move you can make if you're not moving disk 1 again).
(note: The above solution only works for an even number of disks... For an odd number of disks, disk 1 moves to the LEFT.)
Oh, sigh... The perl implementation of this is on my website.
Yes, the solution is provably correct, but I don't have the time to write it up right now... Just consider the fact that you can never move disk1 twice in a row, (or you're wasting a move), and if you're not moving disk1, there's only one move, then you have to move disk1 again (or you're wasting a move). All you have to do then is prove that disk1 always moves in the same direction.
Sometimes boldness is in fashion. Sometimes only the brave will be bold.
Ok, I know its slightly offtopic...
Its true, the towers of Hanoi puzzle is actually present in the Star Wars: Knights of the Old Republic game. Its the 4 disk version.
Always fun to see classic puzzles show up in computer games under a different guise.
// harborpirate
// Slashbots off the starboard bow!
Not to sound trollish but, this guy has way too much time on his hands and needs to get a life, or find something interesting to program.
Maybe its just me but I get nightmares from Tower of Hanio programs.
Its what made me decided that Biology and not CS is where I belonged.
Shudder.
http://saveie6.com/
Using other computers to solve NP-hard problems without their knowledge is called Parasitic Computing. It involves using the normal IP-checksum feature to encode the problem as the data part and the solution as the checksum, with the property that the checksum matches only if it is the correct solution to the problem. An article appeared in Nature about this sometime back and it can be found here:
http://www.nd.edu/~parasite/
Comment removed based on user account deletion
Laszlo LZX wasn't on the list so I fixed that... :)
;)
Here is an LZX version
Laszlo Systems INC
You'll have to be patient for the XAML (Longhorn) or Macromedia Flex versions since they're a ways off
As seen on Wired: Get a free desktop PC
Austria has only a tiny section in Spartacus (the gay travel guide). The biggest section there is for London (over 100 pubs/clubs). But Vienna does have some good pubs and nice food.
Either this is quadratic time not exponential, or else I'm bigger trouble with this "Analysis of algos." exam I have tommorrow :)
O(2^N) is exponential.
Based on upvotes, Ageism is the only "-ism" Slashdotters care about and think isn't SJW
See the Brainfuck solution here.
It begins like (lameness filter prevents a longer excerpt, just click the link):
The first stack frame (0 0 0 0 0 0 0 0)
is used to abort the recursion
>>>>>>>>
These are the parameters for the program
(1 4 1 0 'a 'b 'c 3)
+>++++>+>>
>>>>++++++++[-]+>+>-]++>+++>+++>
And so on.
It's neither. n^log(2)n grows faster than any polynomial, but more slowly than 2^cn for any c>0.
An interesting coincidence (?) is that 108 is a special number for Hinduism, Yoga, and other traditions from Indian roots (and other ancient cultures too). The number itself is related to some astronomical relations (http://www.yrec.org/108.html) that Hindus (quite amazingly) should have known before ~4000BC. The author says (in other page) he was "born a Hindu" and although non-religious, likes to explore Hinduism, so he's most certainly aware of this stuff. I wonder if implementing 108 Hanoi programs produces similar effects to, say, vocalizing "OM" 108 times ;-)
Bart: Isn't that the wrong way?
Homer(Max): Yeah, but faster!
His solution isn't really non-recursive.. I actually replied to this point in another comment (that I thought was a reply to this) which includes a more honestly non-recursive solution (and a pointer to an implentation of it even).
Sometimes boldness is in fashion. Sometimes only the brave will be bold.
To quote:
"Lemme guess, you're going to come over to beat me up, but you can't read the road signs to find the way to my house."
Seriously, I don't care how tough you are--do you realize the percentage of geeks who are angry firearms owners? =P
"America has done some terrible things. But I know that Americans don't cheer when innocents die." -Dave Barry
had a Towers of Hanoi problem in it, with three towers. My non-math-inclined XBOX owning friend invited me over to do it for him. After doing that for him and doing it myself on the game a couple of times, it's 1 min... pretty neat, though.
I'm on a road shaped like a figure eight; I'm going nowhere but I'm guaranteed to be late.
YHBT
And to those of us who are able to socialize coherently? What would we be called?
>_
The best one still have to be the version implemented in the C preprocesser.
http://www0.us.ioccc.org/years.html#1995_vanschnit z
But I was meta-trolling, so YBHT as well. =P
Sucka.
"America has done some terrible things. But I know that Americans don't cheer when innocents die." -Dave Barry
If we banded our collective talents together we could produce things much more useful than Hanio ICMP servers and blue LED case mods. Such as world peace or cost-effective nuclear fission.
;)
After all, geeks are more intelligent than other people. Our failing is our inability to socialise coherently.
That was a Simpson's episode and I think the show demonstrated that such a plan will fail horribly
No solution in Emacs?
Not geeks?
-
"Vengeance is fine," sayeth the Lord.
Nah...what if you were social with only geeks? That would still make you a geek. Or would all of those geeks be negated to not being a geek? To geek or not to geek, that is the question.
>_
Actually, he does seem to have a life, and he does seem to have done a lot of interesting and useful programming. Read some of the other stuff on the website.
I wanted to ask "why"
Never ask a geek "why". Just nod slowly as you back away.
David Gould
main(i){putchar(340056100>>(i-1)*5&31|!!(i<6)<< 6)&&main(++i);}
The operating systems the guy uses ...
The operating systems he runs on his apple notebook ...
The guy's projects - particularly the Sun Solaris Virutalization ...
The art stuff... the comic etc. ...
WOW!
Somebody *does* have a lot of time, not to say talent!!!
http://jpbrown.i8.com/hanoisolver.html
Hey look, one of the moderators never played KOTOR and decided they are a valid judge of a post regaurding it! Fucking morons.
Here is a hint: If you are not familiar with the subject being discussed, do not decide that it is off-topic.
-- 'The' Lord and Master Bitman On High, Master Of All
This guy missed an old one. google in 1991 groups
for Greg McFarlane hanoi vi macros for the
source.
Now there was someone with too much time on
his hands.
Everyone agrees that arguments about Languages are Religious, right?
Well, maybe not. Just have a look at these samplings of code. Now you can argue that some implementations are un-neccessarily complex, and others inefficient. Fair enough. But apart from such deliberately obfuscated grotesques such as the sed implementation, you can get a "within an order of magnitude" estimate of how simple/powerful/readable a language is by looking at the sources.
For example, contrast the PERL implementation with the C implementation.
Now look at the Java vs the Ada implementations.
The similarities, and differences, are instructional.
Parenthetically, with the forthcoming release of Java 1.5, which has Ada facilities such as strong typing of enumerations and generics, the architectural similarities between Ada and Java will become even more pronounced. IMHO Java has a far neater notation of Object-Oriented features than Ada-95's, but in all other respects suffers from C's over-terse syntax. But that's just my opinion. Look at the examples and form your own.
What is not a matter of opinion is that readability helps improve code quality. And wonder why "everyone knows" Ada is over-complicated, too difficult to implement, and too costly - especially when open-source free compilers have been around for nearly a decade now.
Zoe Brain - Rocket Scientist
``=I=`` I I
`==I==` I I
===I=== I I
Your move.
(You wouldn't believe how long it took to get this to display correctly and get past the lameness filter)
It seems the author of the page has put up a faq since he was slashdotte.d Funny!
My second year as a CS major, one of my profs offered extra credit for a Hanoi tower solution that didn't use recursion in any way. I solved it, but it was much harder than I thought it was going to be. (I think it was coded in Turbo Pascal 5.5. I bet that wasn't one of the 108 implementations.)
A friend in the same class actually implemented pictures of of discs moving from one tower to another. He got extra-extra credit.
Steve
$7.95/mo, 200 GB disk, 2TBxfer, MySQL, PHP, RoR.
create or replace package hanoi
:= 1; := 3; := 2;
is
/* towers of hanoi, PL/SQL implementation, by Mark J. Bobak, 12-08-2003 */
from_peg constant number
to_peg constant number
using_peg constant number
procedure play(n number);
end hanoi;
/
create or replace package body hanoi
is
procedure do_hanoi(n number, from_peg number, to_peg number, using_peg number)
is
begin
if(n > 0) then
do_hanoi(n-1,from_peg, using_peg, to_peg);
dbms_output.put_line('move '||from_peg||' --> '||to_peg);
do_hanoi(n-1, using_peg, to_peg, from_peg);
end if;
end;
procedure play(n number)
is
begin
do_hanoi(n, from_peg, to_peg, using_peg);
end;
end;
/
Maxima 5.9.0.1cvs http://maxima.sourceforge.net
Using Lisp CLISP 2.31 (2003-09-01)
(C1) 2^64-1;
(D1) 18446744073709551615
Its said that in a very old temple in the hindu city of benares there is an old preist moving 64 rings.When they finish the world ends.
Reminds me of the arthur clarke story 'the nine billion names of god'........
Wanted : A Signature.
When we get to MSW QZ we will know who wrote it in 108 Crash Programmer +.
It's a bih O of 2^N morron
First I wanted to be a chef. Then I wanted to be Napoleon. My ambitions have continued to grow ever since.