gugllinux.blogg.se - Scheme hanoi towers

#Scheme hanoi towers code

Now, we have three stacks labeled A, B and C. By the principle of recursion, we have already solved these subproblems. How do we solve these subproblems? We don't have to.

Move all the discs smaller than disc n from B to C.

Move all the discs smaller than disc n from A to B.

Our problem of moving all the discs from A to C has now been divided into two subproblems: Finally, we move the remaining discs from B to C. First, we move all the discs above disc n from A to B. We can solve our problem in three simple steps. Now, the only way we can move disc n from A to C is by first moving all the discs above it from A to B. Without this invariant, the solution would be trivial. Our job is to move all the discs from stack A to stack C while maintaining the invariant that a bigger disc may never be placed on top of a smaller disc. Given n discs, the smallest disc is labeled 1 and the largest disc is labeled n. I won't give you the solution outright, but I'll explain the intuition behind the solution. Tower of Hanoi is an inherently recursive problem and it has an elegant recursive solution.

#Scheme hanoi towers code

The code for Hanoi is my attempt to turn my project from C++ into Scheme.Īny help is appreciated. My problem with that, is I'm so used to imperative and OOP with the use of variables that I'm not sure how I can do this when Hanoi only takes one parameter. I'm getting an infinite loop since every time it gets used it takes the same value, thus not ever reducing the value. SumSublists returns how many disks there are in the game. (hanoi '((cddr towersNum) (cadr towersNum) (car towersNum))) (hanoi '((car towersNum) (cadr towersNum) (cddr towersNum))) (hanoi '((car towersNum) (cddr towersNum) (cadr towersNum))) (+ (length (car lst)) (sumSublists (cdr lst))) Here's an example of what I've got on my latest attempt.

My professor said they were able to do it with about 6 helper functions.Īs mentioned, I have to solve the problem taking taking the list as the only parameter.

Every solution I come up with doesn't do it recursively, seeing as I can't manage to wrap my head around doing it recursively with the list as the only parameter. I've been ruminating on this for about a week now. I'd like to start off by saying this is homework so I'm not asking for a solution, just some tips.