Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

108 Ways To Do The Towers of Hanoi

Hemos posted more than 10 years ago | from the and-50-ways-to-leave-your-jacob's-ladder dept.

PC Games (Games) 192

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 :)"

cancel ×

192 comments

Sorry! There are no comments related to the filter you selected.

.| First musical post! .|^ (-1)

Mr F J Musical-Troll (582606) | more than 10 years ago | (#7658579)

First musical [warprecords.com] post!

Re:.| First musical post! .|^ (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658633)

Nice sounds. Finally, a useful first post troll.

Somebody (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658589)

Somebody [kerneltrap.org] has no sex life...

Re:Somebody (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658594)

I meant to link to http://www.kernelthread.com/ [kernelthread.com]

Although I guess I wasn't wrong anyway.

a href="http://slashdot.org/~BladeMelbourne

Next up: 108 ways to post the same story on /. (5, Funny)

corebreech (469871) | more than 10 years ago | (#7658590)

nt

Isn't there a legend involved? (5, Funny)

91degrees (207121) | more than 10 years ago | (#7658593)

When someone works out every single way to solve the problem, the towers will crumble to dust and the world will vanish

Re:Isn't there a legend involved? (5, Informative)

Bagels (676159) | more than 10 years ago | (#7658665)

No, when somebody completes the problem with 64 disks, the world will end. It's an exponential-time function (big O of N^2), so doing that would take an insanely long time. I once calculated this out - assuming you could move 1 disk per second, it would take about 5 billion years, which is very roughly the predicted remaining lifespan of the sun.

Re:Isn't there a legend involved? (1)

koali (175176) | more than 10 years ago | (#7658684)

I'm just experiencing a pretty hangover, so I could be wrong here, but N^2 is not exponential with regards to N...

Re:Isn't there a legend involved? (0)

Anonymous Coward | more than 10 years ago | (#7658690)

64 disks, the world will end. It's an exponential-time function (big O of N^2)

Even if you run it on a 64-bit processor? Dammit. And I was going to buy that Opteron for solving the 64-disk problems.

Re:Isn't there a legend involved? (4, Informative)

ianezz (31449) | more than 10 years ago | (#7658700)

It's an exponential-time function (big O of N^2).

With 3 poles, you need (2 ^ discs)-1 moves to solve the problem. With 64 disks, and one move per second it's more like 584 billion years.

Re:Isn't there a legend involved? (1)

Bagels (676159) | more than 10 years ago | (#7658743)

Heh. I stand corrected - when I worked it out on my calculator, it came out to 5.849424174*10^11 years.

Re:Isn't there a legend involved? (1, Informative)

Anonymous Coward | more than 10 years ago | (#7659257)

Which is 584x10^9, in other words 584 billion... Learn to read standard form!

Re:Isn't there a legend involved? (2, Interesting)

Colonel Cholling (715787) | more than 10 years ago | (#7658739)

Besides, if I remember the legend correctly, the disks were supposed to be moved at the rate of one per year. (They're heavy, ok?)

Re:Isn't there a legend involved? (2, Informative)

Artraze (600366) | more than 10 years ago | (#7658769)

True-ish, as that may be (64 disks with a move per second takes 585 billion years), computers can solve the puzzle much faster. A nanosecond per move is not entirely unreasonible, and a computer at that speed would have it solved in 585 years (namely, a billionth of the time ;).

Re:Isn't there a legend involved? (5, Insightful)

ComaVN (325750) | more than 10 years ago | (#7658801)

Of course, a mathematician can solve the puzzle in 5 minutes. He proves the algorithm will solve the puzzle in the end, and leaves the actual moving of the stones as an exercise for his readers.

He then goes on to generalize the algorithm to support n-dimensional stacks.

Re:Isn't there a legend involved? (5, Informative)

daveq (645397) | more than 10 years ago | (#7658928)

n^2 is quadratic, not exponential ;)

When n is the number of disks:

The recurrence is T(n) = 2*T(n-1) + 1. (No, there isn't a faster way)
The function is T(n) = 2^n - 1

I can't quote the exact value of 2^64-1 offhand, but the maximum value of an unsigned 64-bit integer is definately pretty huge.

Re:Isn't there a legend involved? (1)

Alsee (515537) | more than 10 years ago | (#7659718)

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

Uhhh huh. And I'd like to see how that machine responds to a 255 in the type of service header. The response packets would Shashdot the entire universe till the end of time.

-

As I learned in my College CS diploma, (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658595)

It is official; UN Statistics now confirms: the USA is dying.

One more crippling bombshell hit the already beleaguered USA when president Bush confirmed that their markets have dropped yet again, now down to less than a fraction their value when he began his term. Coming on the heels of a recent UN survey which plainly states that America has lost its way, this news serves to reinforce what we've known all along. America is collapsing in complete disarray, as fittingly exemplified by being the most hated nation in the world.

You don't need to be a foreigner to predict America's future. The hand writing is on the wall: America faces a bleak future. In fact there won't be any future at all for Americans because the USA is dying. Things are looking very bad for America. As many of us are already aware, as the American economy continues to collapse.

Red ink flows like a river of blood. For all practical purposes, all Americans are dead, or at least should be.

My right-hand side kidneys hurt (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658628)

Goddammit.

My kidney hurts. I should stop drinking coffee like my doctor told me.

Now, back to stuff that matters. Does anyone know where I can find crippleporn on the net?

Re:My right-hand side kidneys hurt (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658753)

Try this [cripplexxx.com] and this [nastynickelodeon.com] . Hope this helps!

Re:My right-hand side kidneys hurt (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658764)

This [sakura.ne.jp] is also pretty good, though perhaps not quite what you're looking for.

Reverse DOS? (3, Interesting)

Crypto Gnome (651401) | more than 10 years ago | (#7658600)

"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?

Re:Reverse DOS? (1, Funny)

Crypto Gnome (651401) | more than 10 years ago | (#7658612)

Yea Yeah Yeah, I know the TOS field isn't big enough to show 128.

It's a joke, so laugh.

Re:Reverse DOS? (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#7658622)

Jokes are meant to be funny, dickhead.

Re:Reverse DOS? (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#7658713)

I'm not laughing. Mainly because your 'joke' WASN'T FUCKING FUNNY. I bet you get a barrel of laughs out of 'duct tape' humour too, you hopeless shitstain of a geek.

Re:Reverse DOS? (0)

Anonymous Coward | more than 10 years ago | (#7658814)

fear not for your hanoi ping server, for tos must be between 1 and 10 for it to respond with a solution.

Whitespace? (5, Interesting)

hkroger (666340) | more than 10 years ago | (#7658604)

Hmm, not all the important languages are represented in the list. I didn't see e.g. whitespace [dur.ac.uk] implementation.

Re:Whitespace? (-1, Redundant)

KillerHamster (645942) | more than 10 years ago | (#7658672)

They don't have Brainfuck [muppetlabs.com] either. How could you leave that one out?

Re:Whitespace? (5, Funny)

FrostedWheat (172733) | more than 10 years ago | (#7658712)

Maybe they did, but you just didn't see it?

Re:Whitespace? (2, Funny)

ObviousGuy (578567) | more than 10 years ago | (#7659044)

I have discovered a truly marvelous demonstration of this proposition and have encoded it here in Whitespace.

I am so happy! (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658608)

I am so happy!

My Sun Ultra 80 arrived today!

I'm going to skip work today, brew some great coffee and just play with this lovely machine all day!!!

Overpriced, proprietary crap (0)

Anonymous Coward | more than 10 years ago | (#7658644)

I hope you and your piece of overpriced proprietary slow-as-molasses crap will be happy together.

Teh BUTTSECHS (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658609)

Is on teH SpOKe !1!!!1one

Dip my nuts in it, bitches!

Re:Teh BUTTSECHS (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658618)

Dip my nuts in it, bitches!

you know, i've been thinking about experimenting with man-sex for a long time and now i think i am ready for it. so, where can a first-timer get some hot man meat? i live in europe.

Re:Teh BUTTSECHS (0)

Anonymous Coward | more than 10 years ago | (#7658704)

Try Austria in Vienna. That is, without a doubt, the gay capital of Europe.

Re:Teh BUTTSECHS (-1)

Anonymous Coward | more than 10 years ago | (#7658728)

Vienna in Austria? Really?

I would have guessed Berlin in Germany.

Re:Teh BUTTSECHS (-1)

Anonymous Coward | more than 10 years ago | (#7658746)

Nein, Herr Arschfotze.

Picky (-1, Offtopic)

SimianOverlord (727643) | more than 10 years ago | (#7658614)

Hands up who else was annoyed by the constant and unnecessary use of italics that the writer uses in his introduction.

Jackass.

Hanoi Rocks (-1, Offtopic)

millwall (622730) | more than 10 years ago | (#7658621)

I'm disappointed you didn't get Hanoi Rocks [hanoirocks.com] as background music when loading the webpage :(

My addition (5, Funny)

kinnell (607819) | more than 10 years ago | (#7658625)

Here it is coded in Whitespace [dur.ac.uk] :





Re:My addition (5, Funny)

ShootThemLater (5074) | more than 10 years ago | (#7659690)

Hmmm, looks like slashcode's added a couple of extra whitespaces in there. Won't compile.

But what about... (3, Funny)

Mr. Mosty-Toasty (449993) | more than 10 years ago | (#7658627)

...Brainfuck [muppetlabs.com] ?

Re:But what about... (-1, Offtopic)

edalytical (671270) | more than 10 years ago | (#7658691)

Here is Hello World! [latech.edu] in Brainfuck.

Question for the homosexuals in the room: (-1, Troll)

Anonymous Coward | more than 10 years ago | (#7658638)

WHO THE FUCK CARES!?

He he, he said 'buttsechs'

pfff ... Big deal ... (5, Funny)

cablepokerface (718716) | more than 10 years ago | (#7658642)

Converting the Towers of Hanoi syntax into 108 different languages?

Visual Studio.NET includes a standard wizard for that.

Die nerds die! (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7658658)

I'd just like to tell everyone that, as I'm typing this, I'm fucking this girl I just met (you can imagine the position). Now, this girl is beeeeeaaautiful, and she and I would just like to express our disdain at this time for you pathetic slashdotters who couldn't get laid if you were eggs in a hen's distended uterus.

Well, since her back is to the screen, I'd just like to tell everyone how I'm going to treat her like shit, so that she can go to some guy like most of you, who she'll talk to platonically about how bad I treat her, while all the while the guy she's talking to is desiring her madly, but, being the sensitive slashdot type he is, is afraid to say anything. Then, having worked out her frustrations talking to the poor, sensitive slashdot type, she'll come back to me for some more good sex, and I'll treat her like shit again.

Life's good.

Love,
-Brad Baillod

Re:Die nerds die! (-1, Troll)

Anonymous Coward | more than 10 years ago | (#7658678)

What you don't realise is that in a few years' time, when she's sick of being treated like shit by a bastard like you, she's going to realise that life isn't all about hot sex and orgasms, and end up going steady with one of us nerds. While you remain unloved by anyone due to your abysmal attitude towards people. So fuck you.

Re:Die nerds die! (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#7658716)

Shut your fucking mouth pencilneck, before I come over and trash you for good.

Love,
-Brad Baillod

Re:Die nerds die! (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#7658738)

Threaten me would you, you fucking gorilla? Man, your computer is going to get so owned once I'm done with you.

When your lady sees the Goatse man as your homepage and subscriptions to alt.binaries.erotica.small-girls in your Outlook Express folders she'll come running straight into my arms, and won't give you a second glance.

Re:Die nerds die! (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#7658767)

Scared already, eh? You should be 'cause I can bench press 220 lbs any day. If you as much as touch my interweb you know what will happen: total annihilation, I tell you. You'll be like a stain on the floor of your mom's basement.

So if you want to see who's the real man, come over and meet me. I don't know who "the Goatse man" is but hell you can bring him along. I'll trash him too.

Love
-Brad Baillod

Re:Die nerds die! (-1)

terriblekarmanow tm (592883) | more than 10 years ago | (#7658778)

Of course, by then, she's old, fat and ugly, and he will start over on a fresh 18-year old.

Oh yes, I envy him.

Reminds me of... (4, Insightful)

zhenlin (722930) | more than 10 years ago | (#7658659)

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

Re:Reminds me of... (3, Informative)

edalytical (671270) | more than 10 years ago | (#7658719)

You can view the source code if you click on the name of the language in the section of the page labeled: "The Implementations"

Or you can download the archive [kernelthread.com]

Re:Reminds me of... (1)

zhenlin (722930) | more than 10 years ago | (#7659137)

The keyword here is all.

The page clearly states that there are 4 for which there is no source code.They are:

* Hanoi OS for SPARC
* Sun Solaris /proc
* Sun Solaris STREAMS
* Sun Solaris kernel module

Curious, isn't it, that they are all related to Sun?

Re:Reminds me of... (2, Interesting)

edalytical (671270) | more than 10 years ago | (#7659374)

The keyword here is
all.
Indeed, the keyword is all.

http://www2.latech.edu/~acm/HelloWorld.shtml

Is missing:

BLISS
Cecil
Demeter
Elf
Escher
Hope
Infer
NESL
Obliq
Proteus
SGML
Sisal
Theta
Tycoon
emacs
Lotus 1,2,3
Unisys' WFL
OWL
MFC
ZApp
Zinc

And those are just the languages listed that don't have a link at the Hello World! page http://www2.latech.edu/~acm/HelloWorld.shtml [latech.edu]

Re:Reminds me of... (5, Interesting)

Gorobei (127755) | more than 10 years ago | (#7659360)

The first one I checked (Common Lisp,) was just wrong:

(defun dohanoi(n to from u)
(if (> n 0)
(eval
(dohanoi (- n 1) u from to)
(format t "move ~D --> ~D~&" from to)
(dohanoi (- n 1) to u from)
)
)
)

(defun hanoi(n)
(eval
(dohanoi n 3 1 2)
)
)

eval is not what we want here (it evaluates a single form in the current dynamic environment.) Also, we can use 1- and indent trailing parens correctly. For extra credit, we could make dohanoi local to hanoi.

(defun dohanoi(n to from u)
(when (> n 0)
(dohanoi (1- n) u from to)
(format t "move ~D --> ~D~&" from to)
(dohanoi (1- n) to u from)))

Re:Reminds me of... (0)

Anonymous Coward | more than 10 years ago | (#7659001)

> The examples on the Hello World page all have source code. Hanoimania... Not so.

Which languages are missing the source code then?

what if he had spent his time on something useful? (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#7658669)

fuck these geek pastimes. be productive for a change.

Re:what if he had spent his time on something usef (0)

Anonymous Coward | more than 10 years ago | (#7658693)

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.

Re:what if he had spent his time on something usef (1)

princewally (699307) | more than 10 years ago | (#7658866)

Our failing is our inability to socialise coherently

Which would be a large part of what makes us geeks.

Re:what if he had spent his time on something usef (0)

Anonymous Coward | more than 10 years ago | (#7659507)

Yeah, God forbid that a geek ever try to have fun.

Re:what if he had spent his time on something usef (5, Insightful)

mo26101 (518770) | more than 10 years ago | (#7658750)

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!

Re:what if he had spent his time on something usef (4, Funny)

johannesg (664142) | more than 10 years ago | (#7658775)

...he said in a posting on slashdot.

Re:what if he had spent his time on something usef (1)

MooCows (718367) | more than 10 years ago | (#7658808)

I think we have recursion going on here.

X11? (1)

mr100percent (57156) | more than 10 years ago | (#7658686)

So which one of these should I run if I want to view it animated in X11?

Re:X11? (1)

Takara (711260) | more than 10 years ago | (#7658911)

That would be the Hanoi Xlib [kernelthread.com] version.

What? No Intercal? (0, Funny)

dm(Hannu) (649585) | more than 10 years ago | (#7658688)

No language comparison is complete without Intercal [catb.org] .

Re:What? No Intercal? (1)

edalytical (671270) | more than 10 years ago | (#7658765)

PLEASE GIVE UP [latech.edu] No one said it was complete.

Re:What? No Intercal? (-1)

Anonymous Coward | more than 10 years ago | (#7658841)

Yeah - he's a chicken.

yeah... (5, Funny)

AbbyNormal (216235) | more than 10 years ago | (#7658727)

to the joy of millions of 1st year Computer Science students.

Re:yeah... (3, Funny)

cdrudge (68377) | more than 10 years ago | (#7658757)

And much to the chagrin of thousands of CS profs.

Re:yeah... (1)

paul248 (536459) | more than 10 years ago | (#7659767)

IAAFYCSS, and that happened to be my favorite lab :-)

KOTOR (-1, Offtopic)

Lord Bitman (95493) | more than 10 years ago | (#7658737)

Anyone else play "Knights of the Old Republic"?
Seriously, what is up with that?

Why is the C++ version so complex... (4, Interesting)

Viol8 (599362) | more than 10 years ago | (#7658756)

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

Re:Why is the C++ version so complex... (2, Informative)

oe1kenobi (601951) | more than 10 years ago | (#7658885)

Because the C++ version is non-recursive.

I'm glad he did it this way. I had heard of a previous student that programmed it non-recursively. Now I have an example to look at.

Re:Why is the C++ version so complex... (0)

Anonymous Coward | more than 10 years ago | (#7658898)

Because he wrote his own stack class. He could have used std::stack and saved himself a fair bit of work.

Re:Why is the C++ version so complex... (0)

Anonymous Coward | more than 10 years ago | (#7658914)

It's not complex until it's implemented in templates and with the solution calculated at compile-time.

Re:Why is the C++ version so complex... (1)

musikit (716987) | more than 10 years ago | (#7658923)

my question is why he made his own stack object. i could have sworn the STL has a stack object included.

Re:Why is the C++ version so complex... (2, Interesting)

fnj (64210) | more than 10 years ago | (#7659434)

my question is why he made his own stack object. i could have sworn the STL has a stack object included.

Er, just a guess, but maybe the original concept of his code predated the wide availability of STL. Or quite likely, as a tutorial, he just wanted to depend on nothing beyond iostreams.

I'm more concerned with some other points:

Why "#define STYPE int" instead of "typedef int stype"?

Why the #defines for EMPTY, FULL, and PUSH_OK instead of an enum?

Why the "Stack::Stack(void)" instead of just "Stack::Stack()" (the former is a C anachronism)?

Then, of course, to get really nitpicky, he doesn't need his destructor at all (one will be generated by the compiler).

Re:Why is the C++ version so complex... (2, Interesting)

musikit (716987) | more than 10 years ago | (#7659500)

very true. i guess it goes to another comment that someone else had about writing code in C and it being compilable in C++. while true there are different ways your suppose to write C++ code vs. C code. however it seems a large amount of people use a mix. Or maybe no one is teaching people to program in C++ but in C with C++ constructs.

Haskell? (3, Insightful)

mattr (78516) | more than 10 years ago | (#7658761)

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.

Re:Haskell? (1)

twoshortplanks (124523) | more than 10 years ago | (#7658902)

The Perl one's really weird
($#ARGV == 0) or die "usage: $0 N\n";
Wow, that's really confusing. It's trying to say unless we've got arguments, we need to die with an error message. Which can be witten as
unless (@ARGV)
{ die "usage: $0 N\n"; }
That's not the only other thing that's odd too. Using local instead of my is odd - though both will work. my will do proper lexical variables, whereas local is using main variables in the stash and creating temp copies each itteration of the subroutine.

Oh, and wrapping the whole thing in a if statement is odd. You should just return if you're the base case (just like you do with tail recursion in Haskell)

Here's a cleaned up version with comments

#!/usr/bin/perl

# turn on perl's safety features
use strict;
use warnings;

# check we got some arguments
unless (@ARGV)
{ die "usage: $0 N\n" };

# get the number of disks
my $N = int($ARGV[0]);
unless ($N > 0)
{ die "$0: illegal value for number of disks\n";}

# run the main routine
hanoi($N, 3, 1, 2);

sub hanoi
{
my ($num_disks, $to_peg, $from_peg, $using_peg) = @_;

# are we done? (i.e. is this the basecase)
return unless $num_disks;

# move the stack covering the 'bottom' disk to the
# spare peg
hanoi($num_disks-1, $using_peg, $from_peg, $to_peg);

# move the 'bottom' disk to the other stack
print "move $from --> $to\n";

# move the stack we moved to the spare peg ontop
# of the disk we just moved.
hanoi($num_disks-1, $to_peg, $using_peg, $from_peg);
}
Note that one of the first things I did was turn strict and warnings on, thus meaning it's easier to catch mistakes.

Wow, ECODE doens't let you space things in properly. That's terrible.

Re:Haskell? (1)

twoshortplanks (124523) | more than 10 years ago | (#7658975)

whoops, the $from and $to should be $from_peg and $to_peg, obviously.

d'oh.

Yes, if I'd run that perl would have complained at me because use strict was on.

Re:Haskell? (4, Informative)

Anonymous Coward | more than 10 years ago | (#7659265)

"(condition) or die" is perfectly good, non-confusing Perl. It's the way you're told to do it in the Camel book, for God's sake.

Re:Haskell? (0)

Anonymous Coward | more than 10 years ago | (#7659035)

Here's a program using more orthodox Haskell. The functions are
uncurried, it has static function types and it uses an accumulating
parameter instead of the (++) operator for efficiency ((++) is linear
in its left argument - although since Hanoi is an exponential
algorithm, this streamlining makes next to no difference!).

> dohanoi :: Int -> Int -> Int -> Int -> [(Int,Int)] -> [(Int,Int)]
> dohanoi 0 _ _ _ accum = accum
> dohanoi n from to using accum =
> dohanoi (n-1) from using to
> ((from, to):(dohanoi (n-1) using to from accum))

> hanoi :: Int -> [(Int,Int)]
> hanoi n = dohanoi n 1 3 2 []

Compare to the original:

> dohanoi(0, _, _, _) = []
> dohanoi(n, from, to, using) = dohanoi(n - 1, from, using, to)
> ++ [(from, to)] ++
> dohanoi(n - 1, using, to, from)

> hanoi(n) = dohanoi(n, 1, 3, 2)

Re:Haskell? (0)

Anonymous Coward | more than 10 years ago | (#7659491)

The functions are uncurried

Er, no, the functions in your version are curried. It's his version that uses uncurried functions, which is an abomination in FP, since it prevents partial application.

Missed a language (1)

karlandtanya (601084) | more than 10 years ago | (#7658852)

Relay Ladder Logic


You can program anything in RLL. Not that you'd want to--but your Client probably wants you to.

Re:Missed a language (1)

tzanger (1575) | more than 10 years ago | (#7659733)

You can program anything in RLL. Not that you'd want to--but your Client probably wants you to.

Amen to that... How I loathe PLCs... ugh.

Do not forget MetaPost (0)

Anonymous Coward | more than 10 years ago | (#7659010)

I did this in MetaPost a few months ago. Check out my posting in comp.text.tex [google.com] .

Multi-user 3D (1)

mst (30456) | more than 10 years ago | (#7659184)

I once did a 3D-visualized Prolog implementation [it.kth.se] 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.

What is the most disks you have solved for? (2, Interesting)

fliptout (9217) | more than 10 years ago | (#7659230)

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.

not that you need recursion for this... (2, Interesting)

johntromp (565732) | more than 10 years ago | (#7659280)

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);

Re:not that you need recursion for this... (1)

johntromp (565732) | more than 10 years ago | (#7659321)

/* oops, forgot to format as code.
it should've looked like:
*/

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);

yet another missing language (1)

Savatte (111615) | more than 10 years ago | (#7659286)

where is the quakec implementation? This would make quite the interesting demonstration.

And the 109th way... with a guitar (1)

Hornsby (63501) | more than 10 years ago | (#7659296)

http://www.towersofhanoi.org

Re: your sig (0, Offtopic)

dillon_rinker (17944) | more than 10 years ago | (#7659496)

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...)

My favourite (5, Interesting)

vorwerk (543034) | more than 10 years ago | (#7659486)

A quick scan of the listing didn't show my favourite one -- a non-recursive implementation.
#include <stdio.h>

#define NO_OF_DISKS 4

void main()
{
int max, x;

max = 1 << NO_OF_DISKS;
for (x = 1; x < max; x++) {
printf("Move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);
}
}

Towers of hanoi and bit flip correlation (5, Interesting)

nebaz (453974) | more than 10 years ago | (#7659770)

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.

Representative? (1)

lpret (570480) | more than 10 years ago | (#7659772)

Now here's a question:

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?

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>