CS 60 "All-Semester Bonus Problems"

The bonus problems on this page may be submitted anytime before the last day of classes, Friday, December 10 at 5 PM. Submit these problems by sending an e-mail directly to Ran (hadas@cs.hmc.edu) with your code attached.

1. The Four Fours Problem (Up to 25 Points) In this problem, we want to know how many consecutive non-negative integers (beginning with 0) can be constructed using arithmetic expressions involving exactly four 4's. We are allowed a number of different arithmetic operations (see below) and we wish to construct each integer using exactly four 4's. Some of the many possible examples for the first few non-negative integers are these:

   0 =  4 + 4 - 4 -4
   
   1 =  44 / 44
   
   2 =  (4/4) + (4/4)
   
   3 =  4 - (4/4) - sqrt(4)
   
   4 =  .4 * (4 + 4 + sqrt(4))
   

   The permitted operations are
   • concatenation (hence forty four is possible with 2 fours)
     
   • decimal point (.4 and 4.4 are allowed)
     
   • powers (4 to the 4th power uses two fours to create 256)
     
   • infinite repetition of a digit following a decimal point. This is usually denoted as a bar on top of the digit:

             _
            .4
            

     This number is four ninths, so that you could write eight as

                       _
            8 =  sqrt(.4) * (4 + 4 + 4)
            

     although there are more concise ways to write eight with 4's.

   • factorial (4!)
     
   • square root
     
   • ordinary use of parentheses
   • the four arithmetic operations (+ - * /), although division is not allowed unless it is exact (no rounding or truncating!)
     

   You may want to base your solution on the "Game of 24" from Assignment 9, though any approach is OK. This is a very open-ended extra credit -- all solutions are necessarily partial solutions. You should consider solving the problem from 0 to 100 an absolute success.

   Martin Gardener (a long-time columnist for Scientific American) claimed that solving it for the integer 113 was impossible, though it's not proven one way or the other! If you do try it, submit your Prolog code in a separate file named bonus.pl. You should name the main predicate as follows:

     fours(N,Tree)
   

   where N is the number which we would like to express as a combination of four fours, and Tree is a representation of the operations that are part of that combination.

2. Einstein's Problem (20 Points) Use Prolog to solve the following logic puzzle, supposedly due to Albert Einstein:

   FACTS:
   1. There are 5 houses in 5 different colours. 
   2. In each house lives a person with a different nationality. 
   3. These 5 owners drink a certain beverage, smoke a certain brand of cigarette and keep a certain pet. 
   4. No owners have the same pet, brand of cigaratte, or drink.
   
   
   CLUES:
   1. The Brit lives in a red house 
   2. The Swede keeps a dog 
   3. The Dane drinks tea 
   4. The green house is on the left of the white house. 
   5. The green house owner drinks coffee. 
   6. The person who smokes Pall Mall keeps birds. 
   7. The owner of the yellow house smokes Dunhill. 
   8. The man living in the house right in the center drinks milk 
   9. The Norwegian lives in the first house. 
   10. The man who smokes Blend lives next to the one who keeps cats 
   11. The man who keeps horses lives next to the man who smokes Dunhill 
   12. The owner who smokes Camel drinks beer 
   13. The German smokes Marlborough. 
   14. The Norwegian lives next to the blue house 
   15. The man who smokes Blend has a neighbour who drinks water.
   
   The question is, who keeps the fish? 
   
   

   You will need to give some thought to how to do this without taking an inordinate amount of computation time.

3. B-trees (15 Points) In class, we looked at B-trees (specifically, "2-3-4 trees") - a beautiful data structure for the Dictionary abstract data type. The wonderful thing about this data structure is that all operations can be performed in O(log n) time. Implement a B-tree class in a file called Btree.java. This class should implement the abstract data type provided in the interface DictionaryADT.java in /cs/cs60/assignments/assignment3/bonus. Specifically, the interface supports the following operations:
   • void insert(int n) which inserts the integer n into the Dictionary.
   • boolean find(int n) which returns true if integer n is in the tree and false otherwise.
   • void inorder() which prints the contents of the tree in order from smallest to largest number.

   In addition, you should have a method int height() which returns the height of the tree. Recall from class that the height of a tree is the length of the longest path from the root to a leaf node, where the leaf nodes are assumed to be "null" nodes. Thus, a tree comprising just a single root node with two null children has height 1. An empty tree is a "null" tree and thus has height 0. Do you see why this height method wasn't specified in the DictionaryADT interface, even though we want to have it implemented in the Btree class?

   Make sure that your code is well-structured, clean, and readable. Submit your file Btree.java and any other files which it requires. Notice that Btree.java defines a B-tree and is not executable. However, you should write a thorough tester program to make sure that your class functions correctly. We will test your Btree class using our own tester programs.