Lab #4: A Few Fun Exercises
Assigned: Wed 16 Feb 2005
Due: Wed 25 Feb 2005
The following exercises are drawn from problem sets of past years of the Willamette University High School Programming Contest: Willamette and a sponsoring organization (recently the SAO Foundation of the Software Association of Oregon) hold this contest early every Spring on Willamette's campus in the Cat Cavern. Teams of students from all around Oregon come and compete to solve the most problems in a fixed amount of time (5 hours) using a single computer.
The contest is always on my mind at this time of year since I am busy with all sorts of preparations: mailing lists, food, trophies, computers and ... judges! Willamette students "volunteer" as judges (we actually pay you and feed you lunch and dinner!), so please see me if you are interested!
Another big part of contest preparation is the problem set given to the students, usually about 14 problems of widely-varying difficulty. Since you know enough Haskell now to do some more interesting things, I thought it would be fun for you to solve some of the contest problems in Haskell. Although they are not exactly "real-world" problems, they tend to be more interesting and less "make-work" than the initial simple exercises we do as you learn the language.
As you complete these exercises, remember that the winning high school students solve 9-12 of these problems in 5 hours ... but many of their problems are harder, involving graph traversal, parsing, queuing simulations, etc. (We don't quite have the data structures background in Haskell yet to make these sorts of problems easy to solve, so I will go easy on you for now! :) ) I have also modified the problem statements to involve lists as inputs and outputs rather than the various I/O conventions we set up for the contest.
A list of numbers is balanced if the sum of the first half of the list
is identical to the sum of the second half (the middle number in a list
of odd length contributes to neither half). A list is heavy on the left
if the sum of the first half is greater than the sum of the second half,
and heavy on the right if the sum of the second half is greater than the
sum of the first half.
Write a program which will read in a series of integers, all on one
line, and tell if the list is balanced, heavy on the left or heavy on
the right. Your program should read and report on several such lines
until the input is exhausted (i.e., a line with no numbers appears in
the input).
Sample input and output:
When a golf ball is dropped onto concrete, it bounces to 85% of its
previous height. When it is dropped onto a rug, it bounces back to 20%.
The input to your program will be an initial height for a golf ball (in
feet) and the letter C or R to designate whether the ball is dropped
onto Concrete or a Rug. Your program should report how many bounces are
required before the height of the next bounce is less than a foot.
For example:
(For the Haskell version, you can just write a function which takes an integer
and a value of an enumerated data type and returns an integer.)
The digital root of a (positive) integer is the number obtained by
repeatedly summing the digits until a one-digit sum is obtained. For
example, for the number 974685,
So, the digital root of 974685 is 3, a result which was in this case
obtained in 3 steps.
Write a program which will read in a single positive integer and write
out both its digital root and the number of steps required to obtain it.
Hint: you can use the show function to convert an integer into a
string, and the digitToInt function to convert a digit character
into the corresponding integer number.
A checkerboard has eight rows and columns of squares, colored
alternately red and black so that no two squares of the same
color share an edge. A checker can move diagonally forward, to
the left or to the right, to a square of the same color. A
checker may not move onto a square already occupied by another.
Assume that the squares of the board are given integer co-ordinates,
so that the lower left is square (1,1) and the upper right is
square (8,8). Write a function which will take a description
of a board, in terms of currently occupied squares (i.e., a list of
pairs of integers), along with a starting square (a single pair of
integers), and return a list of all "paths" that can be
taken by a checker starting from that square. Paths are
Strings of letters "L" and "R", representing moves forward
diagonally to the left or right, respectively. You should report
if there is no path or if the piece is already on the last row.
Sample input:
There are nine paths, so your program should return
Given a sequence of non-negative integers, we can transform the
sequence by "rotating" it as many places to the right as
specified by the first number, wrapping the rightmost number
around to come in on the left side. If we repeatedly rotate a
sequence of numbers in this fashion, we can call it "spinning
the sequence". Your program should take a list of numbers
and tell how many times the sequence can be
rotated before it yields a repetition, i.e., a sequence which
has been seen before in the process. For example, the following
sequence rotates 4 times before returning to a previously seen
order:
Note that if a zero value is first in the sequence, we will consider
that it must be rotated once, by that zero value, before
returning to its original state (and similarly for any
"self-generating" sequence).
Please have answers to the above exercises ready for the lab session on
Wednesday 25 February 2005
> balance [10, 20, 30, 40, 50]
"Heavy on the right"
> balance [5, 10, 15, 20, 15, 10, 5]
"Balanced"
> balance [3, 7, 12, 8, 5, 10, 6, 9]
"Balanced"
> balance [100, 10, 90, 20, 5]
"Heavy on the left"
15 C produces The ball will bounce 16 times.
2 R produces The ball will bounce 0 times.
30 R produces The ball will bounce 2 times.
9 + 7 + 4 + 6 + 8 + 5 = 39
3 + 9 = 12
1 + 2 = 3
(5,4) [(3,4), (4,7), (7,2)]
["LLLL","LLLR","LRRL","LRRR","RLRL","RLRR","RRLL","RRLR","RRRL"]
[5, 2, 3, 1, 7, 0, 2]
=> [3, 1, 7, 0, 2, 5, 2]
=> [2, 5, 2, 3, 1, 7, 0]
=> [7, 0, 2, 5, 2, 3, 1]
=> [7, 0, 2, 5, 2, 3, 1]
