0

I need to build a recursive solution to Towers of Hanoi in Scheme. This is different from many of the other Hanoi Scheme questions that have been asked on here before, because I need actually alter the list, not just return a list of instructions.

Requirements

The function call should look like:

(define towers '((1 2 3)()()))
(hanoi towers)

I should return the list every time the peg is moved.

The Status

I have two parts of the puzzle done:

  1. Altering lists in Scheme, I do this by just building a new list using cons or list.

  2. The logic of Towers of Hanoi. This logic is everywhere, I understand how the puzzle is supposed to work.

I'm just having trouble combining them together.

Relevant Code

(define (first-flip Tower)
  (list (return-stack 1 Tower)
        (return-stack 3 Tower)
        (return-stack 2 Tower)))

(define (second-flip Tower)
  (list (return-stack 3 Tower)
        (return-stack 2 Tower)
        (return-stack 1 Tower)))

(define (hanoi height Tower)
  (if (= height 1)
      (move Tower)
      (hanoi (decrement height) 
             (second-flip 
               (move 
                 (hanoi (decrement height) (first-flip Tower)))))))

Summary of Other Code

You can assume the following about my code:

Return stack will return an unnested list (1 source, 2 destination, 3 auxiliary/temp).

So (return-stack 1 '((1 2 3)()())) would return '(1 2 3).

Move will move the top peg of the leftmost list to the top of the middle list.

So (move '((1 2 3)()())) would return '((2 3)(1)()).

Decrement will just return the parameter-1.

Finally, don't worry that the hanoi function listed here takes slightly different parameters than the required hanoi function, I will just create a shell with the proper parameters to call this one.

The Problem

I'm almost certain that the problem lies in my hanoi function. There is something wrong about the logic I'm calling. I've had several TA's look at the code and they were not able to offer relevant help due to a lack of knowledge of scheme and of Towers of Hanoi. I'm hoping the good citizens of the internet can help me here.

Jack Thias
  • 70
  • 1
  • 9
  • This guy was asking the same thing as me, but never got the correct help because he failed to explain the requirements up front: http://stackoverflow.com/questions/35448717/scheme-towers-of-hanoi-recursion – Jack Thias Feb 14 '17 at 07:33
  • This appears to be the most popular Stackoverflow thread on Hanoi+Scheme, but it follows the format of 'print the instructions' which is not acceptable for my assignment: http://stackoverflow.com/questions/20389382/towers-of-hanoi-in-scheme-recursive – Jack Thias Feb 14 '17 at 07:34
  • Finally, I would like to say that I have full confidence in the helper function mentioned in my 'Summary of Other Code'. I have tested those extensively and can say for sure that they work. – Jack Thias Feb 14 '17 at 07:35
  • I have approached the issue in a few different ways, besides the one that I have presented here. The first was to use a begin block with the first call, move, second call. But that doesn't actually do anything (as far as I can tell), because they're not altering a variable (because Scheme doesn't work like that) and so each call has no effect on the following call. – Jack Thias Feb 14 '17 at 07:37
  • The second approach was to mimic OO-logic and use a let block. I had a `(let (x (move (hanoi (- n 1) (list (*swap things around based on Tower*))) (hanoi (- n 1) (list (*swap things around based on x*))))`. – Jack Thias Feb 14 '17 at 07:44
  • I'm actually not sure why the second one didn't work either. But I then went with what seemed like the most 'Scheme-like' solution which was to use onion-style nesting by building two helper functions to handle the swapping of source, aux, and destination. And that's what I have now. – Jack Thias Feb 14 '17 at 07:45
  • So, why can't you modify the solution that prints out the steps taken to print out the current state of the list instead? Isn't that what you are looking for? – Michael Vehrs Feb 15 '17 at 07:41
  • you should provide clear statement, i.e. your inputs, sample call, desired output, actual output; and all the code. what is `(play-towers (decrement height) (hanoi Tower))` and why is it calling `hanoi` with only one argument but definition says there's two? Which is it? Do you need to return a list of all the tower configurations along the process, or just print each of them? – Will Ness Feb 18 '17 at 00:37
  • @WillNess play-towers and single argument hanoi were both errors in my post from trying to simplify my actual code for this post. I just needed to print each tower configuration. – Jack Thias Feb 18 '17 at 02:22
  • @MichaelVehrs Because they don't actually manipulate the list. If you don't understand why they wouldn't work I encourage you to try modifying them to do that, but the summary is that they're not passing a modified tower between calls, they're just passing around tokens and printing what moves would be made. For a solution that manipulates a list, you cannot use a begin block for your logic (as much of the examples I've seen do). – Jack Thias Feb 18 '17 at 02:27
  • I actually worked out a solution to this, I'm hoping to edit my post with the answer later this weekend, it's just not my priority at the moment. – Jack Thias Feb 18 '17 at 02:27
  • @JackThias do not edit your question with an answer! post your own answer to this question, it's perfectly OK to do that. :) – Will Ness Feb 18 '17 at 11:45
  • you probably meant `(hanoi (decrement height) (first-flip Tower)))))))`. just guessing. – Will Ness Feb 18 '17 at 12:30
  • Yeah, that looks right. – Jack Thias Feb 19 '17 at 06:50

0 Answers0