CS 2360
Spring 98
Homework Assignment 5
Due no later than 8:00am, Monday, May 11, 1998
Here in 2360-land, we just adore the creative folks at Binary Arts Corp.
They make all sorts of clever puzzles that translate easily into
homework assignments. This week, you get to play with a variation
of a puzzle they call "Top-Spin".
"Top-Spin" consists of twenty tokens, numbered 1 through 20 (of course),
embedded in a plastic oval "racetrack". The tokens start out ordered
like this:
20 1 3 2 4 5
19 6
18 7
17 8
16 9
15 14 13 12 11 10
You can slide the tokens clockwise or counterclockwise in the racetrack,
and when you move one token you end up moving all of them. Here's what
happens when you move the tokens counterclockwise one space:
1 3 2 4 5 6
20 7
19 8
18 9
17 10
16 15 14 13 12 11
The top straightaway of the racetrack passes through a circular
"turnstile" which accommodates exactly four tokens:
* *
* *
* *
* *
* *
20 1 3 2 4 5
19 * * 6
* *
18 * * 7
* *
17 * * 8
16 9
15 14 13 12 11 10
By spinning the turnstile 180 degrees, you can reverse the order
of the four tokens currently in the turnstile:
* *
* *
* *
* *
* *
20 4 2 3 1 5
19 * * 6
* *
18 * * 7
* *
17 * * 8
16 9
15 14 13 12 11 10
The goal of the puzzle solver is to apply some combination of shifting
the tokens counterclockwise (or left, if you look at the tokens at
the top of the track), shifting the tokens clockwise (or right),
and spinning the turnstile to reorder the tokens so that the puzzle
looks like this:
* *
* *
* *
* *
* *
20 1 2 3 4 5
19 * * 6
* *
18 * * 7
* *
17 * * 8
16 9
15 14 13 12 11 10
Your assignment is to write a program called TOP-SPIN which employes a depth-
first state space search to solve any size "Top-Spin" puzzle. TOP-SPIN takes
four arguments. The first argument is a description of the initial state
as a list of N symbols (where N > 0...you don't pass the number N, you
just pass a list of length N and let the program figure out the number).
The second argument is a description of the goal state as a list of N symbols.
The third argument is an integer T indicating how many symbols can fit
in the turnstile (i.e., how many tokens get reversed when you spin the
turnstile). Assume that T is not greater than N.
The fourth argument is either nil or non-nil. If the value is non-nil, your
program should print to the terminal a trace of the sequence of states or
moves being tried as the search progresses. The trace should also point out
where the program runs into a dead end and has to backtrack, as well as
pointing out when the goal has been reached. If the fourth argument is nil,
no trace should be printed. (You'll want to look up some of the print I/O
stuff to make this pretty. Lyman and/or your TAs will undoubtedly provide
some appropriate code for printing that you can just plug into your program.)
So a call to TOP-SPIN to solve the giant 20-token puzzle described at the
very beginning of this assignment would look like this:
? (top-spin '(1 3 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
'(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
4
nil)
When (if?) the goal has been reached, TOP-SPIN should terminate and return a
list of successive states that constitutes the path or sequence of operations
that gets TOP-SPIN from the initial state to the goal state. The pamphlet
that accompanies the "Top-Spin" puzzle says that it can be solved in as
little as twenty moves, but that there are approximately
2,432,902,000,000,000,000 possible orderings of the twenty tokens.
As you can see, the state space is potentially very very big. You really
don't want to be testing your TOP-SPIN program on a 20-token puzzle if
you want to get done by the due date. You should work on substantially
smaller problems. So if your grader invokes TOP-SPIN on a smaller
problem like this:
? (top-spin '(1 2 5 3 4) '(1 2 3 4 5) 3 nil)
your program should return something like this (although not necessarily
exactly this, and certainly without the comments) if your grader
pretty-printed it:
((1 2 5 3 4) ;;start
(4 1 2 5 3) ;;shift right
(2 1 4 5 3) ;;spin first three tokens
(3 2 1 4 5) ;;shift right
(1 2 3 4 5)) ;;spin first three tokens
The result above assumes that you're using operators which shift tokens
only one space in any direction at a time. And as noted above, your
program may find a different path because your program may apply its
operators in a different order than the hypothetical program above does.
That's ok with us. If the goal state can't be reached from the initial
state, TOP-SPIN should just return nil.
If you wish, you can convert my representation for the "Top-Spin" puzzle into
any other representation of your choice if you think that would make your life
easier. I make no claim that the representation I'm using above for passing
the start and goal states to your program is necessarily a great
representation to use in solving the problem. It just happens to be
convenient for representing the states. If you think things might go easier
for you if you use a different representation, please feel free to do so.
However, you still have to deal with my representation as input to
your function as specified above. Furthermore, you'll need to convert your
representation to my representation in order to return the path from the
initial state to the goal state in the correct (i.e., my) format.
Same guidelines as in the past: lots of well-abstracted, well-named, cohesive,
and readable functions, but no global variables, no assignment, and no
iteration. You can use anything that doesn't have side effects (except in
printing your trace...printing is a side effect).
You can find out more about Binary Arts at www.puzzles.com. Maybe
you'll get a look at what we'll be doing in quarters to come.
Copyright 1998 by Kurt Eiselt. All rights reserved.
Last revised: May 5, 1998