10 ms·

Technical interviews and the Towers of Hanoi

35 points by mrry 12y ago

analognoise 12y ago
The tail call optimization IS a conversion to an iterative format. I'm leery of speedup claims without seeing the code that produced them.
- ch4s3 12y ago
  Yeah, that read like hand waving by someone who doesn't understand what tco actually does. And on top of that, recursive solutions aren't always easy to reason about later on when someone has to maintain it.
typicalrunt 12y ago
There's a bias that interviewers need to watch for when they interview candidates. People who write interview questions often find the answers easy, and for the obvious reason that they are the ones that have spent the most time with it. From a candidate's point of view, the question is new and every solution must be thought through, lest the interviewer thinks that the candidate isn't very smart.
peterwwillis 12y ago
I never understood how interviewers let these kinds of arbitrary details influence their consideration of the candidate. If the interviewer had explicitly requested an iterative function, they probably would have gotten one. You can't fault someone for doing what they feel like doing within the [lack of] parameters you assign. That said, holy shit is it scary when you open up a framework or library and see a mess of recursive functions. Pity the poor soul who has to troubleshoot their app when it ends up a long trail of performance issues in someone else's library.
dreaminvm 12y ago
I don't agree with the author that iterative code is bad (within a certain context). In fact, I tend to write iterative solutions first when I am just testing something out and develop more elegant, recursive solutions when I have a better understanding of the problem (which might not be possible when you are dealing with interview anxiety and an interviewer breathing down your neck).
- ojbyrne 12y ago
  I didn't get the impression he was saying that. Quote: "The truth is that in most embedded/real-time/kernel work, we almost never see actual recursion. When there are strict bounds on stack sizes, recursive algorithms can be downright dangerous, especially when operating on user-supplied data."
  - dreaminvm 12y ago
    He set the tone at the beginning of the article with the following: "There’s a particular sinking feeling that comes when the candidate starts on one of these problems and immediately writes a for loop"
andrewstuart 12y ago
This guy is looking to employ himself, not someone who'll write good software. This comes up again and again in developer recruiting. "Gasp! I CANNOT believe you call yourself a developer when you haven't mastered hoogleflatz! ANY REAL software engineer (like me) has a total grasp of hoogleflatz. Hoogleflatz is ESSENTIAL to all software development. When you go to work you must arrive at 9:00AM and leave at the end of the day with zero result because you don't know Hoogleflatz. Why are we having so much trouble recruiting awesome engineers? There must be a skills shortage."
- Peroni 12y ago
  >This guy is looking to employ himself This is the key shortfall in interviews across all skills, not just tech. Most people tend to gravitate towards the familiar and naturally nothing is more familiar than yourself. This also affects bias towards gender, race, etc.
  - mattxxx 12y ago
    Agreed
  - jnbiche 12y ago
    >This is the key shortfall in interviews across all skills, Sorry, but as someone who changed professions after 10 years in another profession (which was pretty universally viewed as a "brainy" type of work), I strongly disagree. My interviews (of which I had several over 10 years) were always done respectfully, and first and foremost were interested in teamwork skills, personality, and work habits. But when subject matter expertise was examined, my interviewers probed exclusively for knowledge we used in our everyday work. My former colleagues are uniformly appalled to hear what tech interviews are like. Likewise my wife, who works in yet another profession. Edit: Downvote away. I love working in software development, but until software developers face up to the fact that their interview process is actively discouraging more people from entering the profession, there will continue to be a "skill shortage" (a term that is also bandied about for political reasons, but that's another story). It's not management that conducts these kinds of interviews, it's fellow devs. Edit 2: And just to clarify, I'm not talking about knowing time/space complexity and common data structures and algorithms, all of which are important. I'm talking about asking puzzle problems like Tower of Hanoi and then marking people down for using an iterative instead of recursive solution.
Justsignedup 12y ago
Funny, about 13 years ago, someone told me about this exact problem / solution. His professor said that it was impossible to solve the problem without recursion. He solved it with the exact solution given, and basically got an A in his class for it (a bet with the professor). Oh well. moving on.
nbevans 12y ago
This is one of the worst articles I've ever read.
- mattxxx 12y ago
  It's disappointing to see someone talk so smugly about a bad opinion.
jnbiche 12y ago
So... you (the writer) have noticed that the more experienced a candidate is, the less likely they are to get your interview question "right" (i.e., done the way you want). And...you haven't questioned this process? Sometimes, I think half the reason developers stay in unsatisfactory jobs is that they don't want to go through interviews led by interviewers like this guy. Who I think is probably similar to the majority of interviewers, based on my experience.
- na85 12y ago
  Agree. I also note without surprise that there's no qualification as to why the recursive solution is "better". Indeed I think the author does a great job explaining why the recursive solution is usually worse, namely: harder to maintain, less intuitive, and only marginally faster.
  - troels 12y ago
    Also, depending on the language you work in, a function call may be quite expensive, compared to a straight loop.
- nilkn 12y ago
  > Sometimes, I think half the reason developers stay in unsatisfactory jobs is that they don't want to go through interviews led by interviewers like this guy. There's really no doubt about it. I myself have refrained to apply or turned down a number of recruiters at various places that I'd otherwise be interested in because I know what the interview process is going to be like and whatever respectable pay raise they might offer isn't worth the trouble. Interviewing really takes a chunk out of you sometimes. That said, I'd gladly take a booming industry with incredibly annoying interviews over a dead or dying industry.
  - jnbiche 12y ago
    >That said, I'd gladly take a booming industry with incredibly annoying interviews over a dead or dying industry. Absolutely. Other than the interviews and the occasional death march, it's a great profession (I mean that seriously).
bkeroack 12y ago
This is a way to optimize hiring towards those who are good at whiteboarding code under pressure. In other words, a task that is not at all related to the vast majority--if not any--software development roles.
- onezeno 12y ago
  Instead we should give them boring tedious problems in a code base with no documentation and an incomplete buggy spec, and grade their solution in a couple weeks?
ryandvm 12y ago
Funny. I'm always leery of the developer that instinctively reaches for the recursive solution. Unless your data or algorithm is recursive in nature (e.g. trees, nested data, QuickSort, etc.), than a recursive solution is going to be less intuitive and more difficult for the next guy to maintain. Ideally, you match your implementation with the data structure and/or algorithm you'll be dealing with.
- pacofvf 12y ago
  I never go for the recursive solution rightaway, if I'm the interviewer and the developer goes for the iterative solution then it means that he/she didn't memorized(or googled) a few lines of code, instead he/she is actually trying to solve the problem, even if the developer doesn't succeed it's more valuable than the developer that got the recursive solution at the first attempt, sadly most interviewers think that if you can solve puzzles with the "right" solution in the minimum time, then you are the best candidate for the job.
  - baddox 12y ago
    It's certainly possible to learn to "think recursively," and thus be able to work out recursive solutions to new problems in the same way that other people work out iterative solutions to new problems. The book The Little Schemer is a great way to learn to think recursively. It has been 5 years since I read it, and I haven't kept the skill fresh, so I've probably lost most of it. http://www.amazon.com/The-Little-Schemer-4th-Edition/dp/0262560992 http://www.amazon.com/The-Little-Schemer-4th-Edition/dp/0262...
- baddox 12y ago
  I'm not sure how you can call any specific data structure or algorithm "recursive in nature." Trees can be defined and operated on iteratively. Likewise, lists can be define and operated on recursively.
tbrock 12y ago
Is this a racist question to be asking in an interview? I seem to remember some back story about people being imprisoned and forced to solve this problem during the Vietnam war (possibly in a tower -- for extra meta level punishment).
sago 12y ago
> There’s a particular sinking feeling that comes when the candidate starts on one of these problems and immediately writes a for loop. > in most embedded/real-time/kernel work, ... When there are strict bounds on stack sizes, recursive algorithms can be downright dangerous, especially when operating on user-supplied data. Seems like an excellent interview question. Certainly from the first three paragraphs, I can tell that this is a company that recruits mediocre graduates because they don't pay attention to real-world constraints. A company I definitely shouldn't be working for.
dominotw 12y ago
I was asked this question in an interview and the only reason I was able to come up with a solution was that I had taken Spivak's calculus previous semester and the proof was one the exercise questions for a chapter on induction.
zak_mc_kracken 12y ago
> I always ask people to write code in a technical interview, and I usually start with a fairly easy warm-up question — some sort of a toy problem like an operation on lists or trees, often the kind of thing that has a neat recursive solution. Interview questions that have a "neat" solution are usually bad interview questions and more a reflection on the fact that the interviewer is trying to feel smarter than the interviewee. On top of that, if the interviewee writes the neat solution right away, what have you learned exactly? Either she's very good or she already knew the neat solution, so you're going to have to ask additional questions to clarify. Why not skip the gimmick question and get to the real interview part?
- zck 12y ago
  One big thing that this does is mentioned in the problem: warming up. When you're under pressure, you don't want to just step off the street and start talking about some super-hard problem. But if you don't warm up at all, this is exactly what happens. And that's just the candidate! This also lets the interviewer get into interviewing mode. An interview is basically a type of performance. And what performer steps on stage without warming up?
  - sigsergv 12y ago
    Usually you have just one hour, there is literally no time for warm ups.
nwyouth 12y ago
And the funny part of it all is that most times the job being interviewed for is simply maintaining/building a web or mobile app for which the candidate will never in the history of their entire career need to think about solving any problem even remotely close to this one. Just end up hiring lots of "experts" capable of creating complex solutions for simple problems.
thaumaturgy 12y ago
HN, you really need to stop dismissing out-of-hand anything you read that doesn't match your expectations. It's embarrassing. 1. The author is Tim Deegan, who's a former Xen maintainer and currently does low-level work in a data storage startup. He holds a PhD from a reputable university (Cambridge...) and has published several papers (http://www.tjd.phlegethon.org/ http://www.tjd.phlegethon.org/). This doesn't immediately make him right of course, but it does mean he's probably not an idiot and his statements merit a little consideration. 2. The bottom paragraph of the article explains his reasoning behind hoping for a recursive version in interviews: "When I actually implemented this in C, the iterative version was not only messier, but also nearly four times slower than the recursive one. ... a modern CPU will predict all the return addresses correctly. And the work of figuring out which of the two candidate disks to move next and where to is quite a bit more than just finding the spare peg. Since any Towers of Hanoi problem that will complete in less than a day should fit entirely in L1 cache, the extra instructions and (potentially mispredicted) branches to find the next move are worse than the extra memory operations for the recursion." It's not clear from some of the comments in this thread that many people read all the way down to that paragraph. 3. His test case is here: http://tjd.phlegethon.org/blog/hanoi.c http://tjd.phlegethon.org/blog/hanoi.c ... if he has done something wrong, this would be the place to go looking for it. I don't see anything obviously wrong with his iterative version, although I'm getting a double-free error after compiling and running his code. I've believed for years that iterative approaches gave better performance than recursive versions. This probably goes all the way back to working in 68k assembly. I'm pretty sure there's a chapter in Beautiful Code that suggests iterative is better than recursive, performance-wise. But if Tim's right, then I've learned something valuable today. edit: I'm busy today and my C is suuuuper rusty; I think there might be something in that for loop in finish() that's screwing up the pegs[2] that's being passed to free() a couple of lines later, but I don't really have the time to debug it. Hopefully someone else is willing to try, I'd like to see what the actual results turn out to be in different environments.
- anindyabd 12y ago
  Thank you. It seems that people read the title of the post, skimmed through half of it, then rushed to post their opinion. Reminds me of an Ars Technica experiment I read about in Jeff Atwood's blog [1]: "Ars Technica ran a little experiment in 2011. When they posted Guns at home more likely to be used stupidly than in self defense, embedded in the last sentence of the seventh paragraph of the article was this text: If you have read this far, please mention Bananas in your comment below. We're pretty sure 90% of the respondants to this story won't even read it first. The first person to do this is on page 3 of the resulting discussion, comment number 93." [1] http://blog.codinghorror.com/because-reading-is-fundamental-2/ http://blog.codinghorror.com/because-reading-is-fundamental-...
pieguy 12y ago
Here's an iterative solution which is shorter and 3 times as fast: void iterative(int n) { int from[2][3] = {{0,1,2},{0,2,1}}; int to[2][3] = {{1,2,0},{2,1,0}}; for(int i=1; i<1<<n; i++) { int disk = __builtin_ctz(i); int count = (i>>(1+disk))%3; int parity = (disk^n)&1; move(from[parity][count], to[parity][count]); } }
- thaumaturgy 12y ago
  Neat. Were you able to get his code to run? What did you change / what compiler flags did you use?
  - pieguy 12y ago
    I removed the free() call because it was crashing. I also added a cast to the malloc() because I was compiling in C++. Compiled with g++ -o hanoi hanoi.cpp -O2 -lrt
    - thaumaturgy 12y ago
      Thanks. I had also cast malloc() but didn't think to just comment out free(). So I'm seeing similar results as you. Your iterative implementation is about 3x faster than the author's, but still not as fast as the recursive version. I'm surprised!

35 points by mrry 12y ago

The tail call optimization IS a conversion to an iterative format. I'm leery of speedup claims without seeing the code that produced them.

ch4s3 12y ago
Yeah, that read like hand waving by someone who doesn't understand what tco actually does. And on top of that, recursive solutions aren't always easy to reason about later on when someone has to maintain it.

typicalrunt 12y ago

There's a bias that interviewers need to watch for when they interview candidates. People who write interview questions often find the answers easy, and for the obvious reason that they are the ones that have spent the most time with it. From a candidate's point of view, the question is new and every solution must be thought through, lest the interviewer thinks that the candidate isn't very smart.

peterwwillis 12y ago

I never understood how interviewers let these kinds of arbitrary details influence their consideration of the candidate. If the interviewer had explicitly requested an iterative function, they probably would have gotten one. You can't fault someone for doing what they feel like doing within the [lack of] parameters you assign. That said, holy shit is it scary when you open up a framework or library and see a mess of recursive functions. Pity the poor soul who has to troubleshoot their app when it ends up a long trail of performance issues in someone else's library.

dreaminvm 12y ago

I don't agree with the author that iterative code is bad (within a certain context). In fact, I tend to write iterative solutions first when I am just testing something out and develop more elegant, recursive solutions when I have a better understanding of the problem (which might not be possible when you are dealing with interview anxiety and an interviewer breathing down your neck).

ojbyrne 12y ago
I didn't get the impression he was saying that. Quote: "The truth is that in most embedded/real-time/kernel work, we almost never see actual recursion. When there are strict bounds on stack sizes, recursive algorithms can be downright dangerous, especially when operating on user-supplied data."
- dreaminvm 12y ago
  He set the tone at the beginning of the article with the following: "There’s a particular sinking feeling that comes when the candidate starts on one of these problems and immediately writes a for loop"

andrewstuart 12y ago

This guy is looking to employ himself, not someone who'll write good software. This comes up again and again in developer recruiting. "Gasp! I CANNOT believe you call yourself a developer when you haven't mastered hoogleflatz! ANY REAL software engineer (like me) has a total grasp of hoogleflatz. Hoogleflatz is ESSENTIAL to all software development. When you go to work you must arrive at 9:00AM and leave at the end of the day with zero result because you don't know Hoogleflatz. Why are we having so much trouble recruiting awesome engineers? There must be a skills shortage."

Peroni 12y ago
>This guy is looking to employ himself This is the key shortfall in interviews across all skills, not just tech. Most people tend to gravitate towards the familiar and naturally nothing is more familiar than yourself. This also affects bias towards gender, race, etc.
- mattxxx 12y ago
  Agreed
- jnbiche 12y ago
  >This is the key shortfall in interviews across all skills, Sorry, but as someone who changed professions after 10 years in another profession (which was pretty universally viewed as a "brainy" type of work), I strongly disagree. My interviews (of which I had several over 10 years) were always done respectfully, and first and foremost were interested in teamwork skills, personality, and work habits. But when subject matter expertise was examined, my interviewers probed exclusively for knowledge we used in our everyday work. My former colleagues are uniformly appalled to hear what tech interviews are like. Likewise my wife, who works in yet another profession. Edit: Downvote away. I love working in software development, but until software developers face up to the fact that their interview process is actively discouraging more people from entering the profession, there will continue to be a "skill shortage" (a term that is also bandied about for political reasons, but that's another story). It's not management that conducts these kinds of interviews, it's fellow devs. Edit 2: And just to clarify, I'm not talking about knowing time/space complexity and common data structures and algorithms, all of which are important. I'm talking about asking puzzle problems like Tower of Hanoi and then marking people down for using an iterative instead of recursive solution.

Justsignedup 12y ago

Funny, about 13 years ago, someone told me about this exact problem / solution. His professor said that it was impossible to solve the problem without recursion. He solved it with the exact solution given, and basically got an A in his class for it (a bet with the professor). Oh well. moving on.

nbevans 12y ago

This is one of the worst articles I've ever read.

mattxxx 12y ago
It's disappointing to see someone talk so smugly about a bad opinion.

jnbiche 12y ago

So... you (the writer) have noticed that the more experienced a candidate is, the less likely they are to get your interview question "right" (i.e., done the way you want). And...you haven't questioned this process? Sometimes, I think half the reason developers stay in unsatisfactory jobs is that they don't want to go through interviews led by interviewers like this guy. Who I think is probably similar to the majority of interviewers, based on my experience.

na85 12y ago
Agree. I also note without surprise that there's no qualification as to why the recursive solution is "better". Indeed I think the author does a great job explaining why the recursive solution is usually worse, namely: harder to maintain, less intuitive, and only marginally faster.
- troels 12y ago
  Also, depending on the language you work in, a function call may be quite expensive, compared to a straight loop.
nilkn 12y ago
> Sometimes, I think half the reason developers stay in unsatisfactory jobs is that they don't want to go through interviews led by interviewers like this guy. There's really no doubt about it. I myself have refrained to apply or turned down a number of recruiters at various places that I'd otherwise be interested in because I know what the interview process is going to be like and whatever respectable pay raise they might offer isn't worth the trouble. Interviewing really takes a chunk out of you sometimes. That said, I'd gladly take a booming industry with incredibly annoying interviews over a dead or dying industry.
- jnbiche 12y ago
  >That said, I'd gladly take a booming industry with incredibly annoying interviews over a dead or dying industry. Absolutely. Other than the interviews and the occasional death march, it's a great profession (I mean that seriously).

bkeroack 12y ago

This is a way to optimize hiring towards those who are good at whiteboarding code under pressure. In other words, a task that is not at all related to the vast majority--if not any--software development roles.

onezeno 12y ago
Instead we should give them boring tedious problems in a code base with no documentation and an incomplete buggy spec, and grade their solution in a couple weeks?

ryandvm 12y ago

Funny. I'm always leery of the developer that instinctively reaches for the recursive solution. Unless your data or algorithm is recursive in nature (e.g. trees, nested data, QuickSort, etc.), than a recursive solution is going to be less intuitive and more difficult for the next guy to maintain. Ideally, you match your implementation with the data structure and/or algorithm you'll be dealing with.

pacofvf 12y ago
I never go for the recursive solution rightaway, if I'm the interviewer and the developer goes for the iterative solution then it means that he/she didn't memorized(or googled) a few lines of code, instead he/she is actually trying to solve the problem, even if the developer doesn't succeed it's more valuable than the developer that got the recursive solution at the first attempt, sadly most interviewers think that if you can solve puzzles with the "right" solution in the minimum time, then you are the best candidate for the job.
- baddox 12y ago
  It's certainly possible to learn to "think recursively," and thus be able to work out recursive solutions to new problems in the same way that other people work out iterative solutions to new problems. The book The Little Schemer is a great way to learn to think recursively. It has been 5 years since I read it, and I haven't kept the skill fresh, so I've probably lost most of it. http://www.amazon.com/The-Little-Schemer-4th-Edition/dp/0262560992 http://www.amazon.com/The-Little-Schemer-4th-Edition/dp/0262...
baddox 12y ago
I'm not sure how you can call any specific data structure or algorithm "recursive in nature." Trees can be defined and operated on iteratively. Likewise, lists can be define and operated on recursively.

tbrock 12y ago

Is this a racist question to be asking in an interview? I seem to remember some back story about people being imprisoned and forced to solve this problem during the Vietnam war (possibly in a tower -- for extra meta level punishment).

sago 12y ago

> There’s a particular sinking feeling that comes when the candidate starts on one of these problems and immediately writes a for loop. > in most embedded/real-time/kernel work, ... When there are strict bounds on stack sizes, recursive algorithms can be downright dangerous, especially when operating on user-supplied data. Seems like an excellent interview question. Certainly from the first three paragraphs, I can tell that this is a company that recruits mediocre graduates because they don't pay attention to real-world constraints. A company I definitely shouldn't be working for.

dominotw 12y ago

I was asked this question in an interview and the only reason I was able to come up with a solution was that I had taken Spivak's calculus previous semester and the proof was one the exercise questions for a chapter on induction.

zak_mc_kracken 12y ago

> I always ask people to write code in a technical interview, and I usually start with a fairly easy warm-up question — some sort of a toy problem like an operation on lists or trees, often the kind of thing that has a neat recursive solution. Interview questions that have a "neat" solution are usually bad interview questions and more a reflection on the fact that the interviewer is trying to feel smarter than the interviewee. On top of that, if the interviewee writes the neat solution right away, what have you learned exactly? Either she's very good or she already knew the neat solution, so you're going to have to ask additional questions to clarify. Why not skip the gimmick question and get to the real interview part?

zck 12y ago
One big thing that this does is mentioned in the problem: warming up. When you're under pressure, you don't want to just step off the street and start talking about some super-hard problem. But if you don't warm up at all, this is exactly what happens. And that's just the candidate! This also lets the interviewer get into interviewing mode. An interview is basically a type of performance. And what performer steps on stage without warming up?
- sigsergv 12y ago
  Usually you have just one hour, there is literally no time for warm ups.

nwyouth 12y ago

And the funny part of it all is that most times the job being interviewed for is simply maintaining/building a web or mobile app for which the candidate will never in the history of their entire career need to think about solving any problem even remotely close to this one. Just end up hiring lots of "experts" capable of creating complex solutions for simple problems.

thaumaturgy 12y ago

HN, you really need to stop dismissing out-of-hand anything you read that doesn't match your expectations. It's embarrassing. 1. The author is Tim Deegan, who's a former Xen maintainer and currently does low-level work in a data storage startup. He holds a PhD from a reputable university (Cambridge...) and has published several papers (http://www.tjd.phlegethon.org/ http://www.tjd.phlegethon.org/). This doesn't immediately make him right of course, but it does mean he's probably not an idiot and his statements merit a little consideration. 2. The bottom paragraph of the article explains his reasoning behind hoping for a recursive version in interviews: "When I actually implemented this in C, the iterative version was not only messier, but also nearly four times slower than the recursive one. ... a modern CPU will predict all the return addresses correctly. And the work of figuring out which of the two candidate disks to move next and where to is quite a bit more than just finding the spare peg. Since any Towers of Hanoi problem that will complete in less than a day should fit entirely in L1 cache, the extra instructions and (potentially mispredicted) branches to find the next move are worse than the extra memory operations for the recursion." It's not clear from some of the comments in this thread that many people read all the way down to that paragraph. 3. His test case is here: http://tjd.phlegethon.org/blog/hanoi.c http://tjd.phlegethon.org/blog/hanoi.c ... if he has done something wrong, this would be the place to go looking for it. I don't see anything obviously wrong with his iterative version, although I'm getting a double-free error after compiling and running his code. I've believed for years that iterative approaches gave better performance than recursive versions. This probably goes all the way back to working in 68k assembly. I'm pretty sure there's a chapter in Beautiful Code that suggests iterative is better than recursive, performance-wise. But if Tim's right, then I've learned something valuable today. edit: I'm busy today and my C is suuuuper rusty; I think there might be something in that for loop in finish() that's screwing up the pegs[2] that's being passed to free() a couple of lines later, but I don't really have the time to debug it. Hopefully someone else is willing to try, I'd like to see what the actual results turn out to be in different environments.

anindyabd 12y ago
Thank you. It seems that people read the title of the post, skimmed through half of it, then rushed to post their opinion. Reminds me of an Ars Technica experiment I read about in Jeff Atwood's blog [1]: "Ars Technica ran a little experiment in 2011. When they posted Guns at home more likely to be used stupidly than in self defense, embedded in the last sentence of the seventh paragraph of the article was this text: If you have read this far, please mention Bananas in your comment below. We're pretty sure 90% of the respondants to this story won't even read it first. The first person to do this is on page 3 of the resulting discussion, comment number 93." [1] http://blog.codinghorror.com/because-reading-is-fundamental-2/ http://blog.codinghorror.com/because-reading-is-fundamental-...

pieguy 12y ago

Here's an iterative solution which is shorter and 3 times as fast: void iterative(int n) { int from[2][3] = {{0,1,2},{0,2,1}}; int to[2][3] = {{1,2,0},{2,1,0}}; for(int i=1; i<1<<n; i++) { int disk = __builtin_ctz(i); int count = (i>>(1+disk))%3; int parity = (disk^n)&1; move(from[parity][count], to[parity][count]); } }

thaumaturgy 12y ago
Neat. Were you able to get his code to run? What did you change / what compiler flags did you use?
- pieguy 12y ago
  I removed the free() call because it was crashing. I also added a cast to the malloc() because I was compiling in C++. Compiled with g++ -o hanoi hanoi.cpp -O2 -lrt
  - thaumaturgy 12y ago
    Thanks. I had also cast malloc() but didn't think to just comment out free(). So I'm seeing similar results as you. Your iterative implementation is about 3x faster than the author's, but still not as fast as the recursive version. I'm surprised!