ISE 390 -- Programming Challenges -- Week 2 Notes
This Weeks Goals:
To resolve all lingering problems concerning programming languages
and the Vallidoid site.
To discuss the Tower of Hanoi problem (254), the most interesting
of last week's problems.
To discuss string/character I/O.
To introduce this weeks problems on games and puzzles.
Hints from last class:
Bracketing your program with begining/end of source comments
is a good way to make sure the judge is not confused by junk appended
by your mailer.
/* @BEGIN_OF_SOURCE_CODE */
your program here
/* @END_OF_SOURCE_CODE */
The Tower of Hanoi problem
The Tower of Hanoi problem (254) takes exponential time to simulate,
so any program which solves it must be clever and calculate the
position after a given number of moves.
Note that the problem is easy if the number of moves is 2^i-1
for a given i, as that is how long it takes to move the first i
disks to another pole (which one depends on whether i is even or odd).
Can we use this observation to interpolate between powers of two,
by considering a smaller subproblem?
Programming Ideas:
(1) There are several approaches to reading in the text input required by
many of these problems. Either you can:
(a) repeatedly get single characters (perhaps using a library
function like getchar);
(b) repeatedly get strings (perhaps using a library function like
scanf) and break them down into single characters.
(c) read the entire line as a string (perhaps using a library
function like gets), and then parsing it by accessing
characters in the string.
(d) perhaps more modern ways using streams are easier, perhaps not.
(2) Be aware of how your favorite programming language represents strings.
Java presumably views strings as objects and has a set of operators
and methods acting on them.
C/C++ treats strings as arrays of characters. The string ends when
it hits a null character '\0'. Space must be allocated for the
full array to accommodate the largest possible string unless you
want a core dump. Individual characters of the string are accessible
as array elements, while the string itself is referred to by the
name of the array.
(3) Use arrays and matricies for any structure which is reasonable.
Don't play with linked lists or structures in the interests
of simplicity.
Assigned Problems:
127 -- Implement a simple solitaire game. What is the right data type
to represent a card, and what data structure would represent a game?
170 -- A different version of solitaire. What is the simplest, easiest
data structure to represent the deck?
227 -- A version of the 15-puzzle where we seek to simulate, not find
a set of moves.
339 -- A more challenging game where the shape of the board changes each
round. Keep it simple..
395 -- Find legal moves in a checkers-like game.
Problems for Discussion
-----------------------
What is the probability of winning various card patience games?
What is the probability of clearing a new card on problem 127?
Consider the following variations of problem 170:
(a) what if we make 52 piles, each with one card?
Hint: think permutations.
(b) what if we make 2 piles (red and black) each with 26 cards?