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.

  1. Balanced lists

    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:

    > 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"

  2. Bouncing golf balls

    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:

    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.

    (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.)

  3. Digital roots

    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,

    9 + 7 + 4 + 6 + 8 + 5 = 39
    3 + 9 = 12
    1 + 2 = 3

    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.

  4. Checkerboard paths

    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:

    (5,4) [(3,4), (4,7), (7,2)]

    There are nine paths, so your program should return

    ["LLLL","LLLR","LRRL","LRRR","RLRL","RLRR","RRLL","RRLR","RRRL"]

  5. Spinning sequences

    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:

        [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]
    

    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