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?