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?