CS100M Fall 2000
Final Exam Solutions

function Problem1a
clear;
size=3;
x = floor(rand(size)*19)-9+floor(rand(size)*19*i)-9*i;
y = cell(1,size);
for jj=1:size
   y{jj} = x(1:jj,jj);
end
y{:}

******
public class Problem1b {
    public static void main(String[] args) {
        final int SIZE = Integer.parseInt(args[0]);
	Complex[][] x = makeFull(SIZE);
	Complex[][] y = makeTria(SIZE);
	fillTria(x,y);
	printFull(x);
	printTria(y);
    }
    public static void printFull(Complex[][] x) {
	for(int i=0;i<x.length; i++) {
	    System.out.println();
	    for(int j=0;j<x[i].length;j++)
		System.out.print(x[i][j]+" ");
	}
    }
    public static void printTria(Complex[][] y) {
	System.out.println();
	System.out.println();
	for(int j=0;j<y.length; j++) {
	    System.out.println("ans =");
	    System.out.println();
	    for(int i=0;i<j+1;i++)
		System.out.println("  "+y[j][i]);
	}
    }
    public static void fillTria(Complex[][] x,Complex[][] y) {
	for(int j=0;j<x.length; j++)
	    for(int i=0;i<j+1;i++)
		y[j][i]=x[i][j];
    }
    public static Complex[][] makeTria(int size) {    
	Complex[][] tmp = new Complex[size][];
	for(int j=0;j<size;j++)
	    tmp[j]=new Complex[j+1];
	return tmp;
    }
    public static Complex[][] makeFull(int size) {    
	Complex[][] tmp = new Complex[size][size];
	for(int i=0;i<size;i++)
	    for(int j=0;j<size;j++)
		tmp[i][j] = crand(9,19);
	return tmp;
    }
    public static Complex crand(int low, int high) {
	return new Complex(rrand(low,high),rrand(low,high));
    }    
    public static int rrand(int low, int high) {
	return (int) Math.floor(Math.random()*high)-low;
    }
}

class Complex {
    private int real;
    private int imag;
    Complex(int real, int imag) {
	this.real = real;
	this.imag = imag;
    }
    public String toString() {
	String sign="+",space="";
	if (real >= 0) space=" ";
	if (imag < 0)  sign="";
	return space+real+sign+imag+"i";
    }
}

********
// Problem 2

class File {
    int id;
    protected int size;
    private int author_id;
    public File() { }
    public File(int i, int s, int a) { id=i; size=s; author_id=a; }
    private void useless1() { }
    protected void useless2() {
	useless1();  //................................1. Correct [ ]  Incorrect [ ]
    }
    public void whoDidIt() {
	System.out.println("Author "+author_id); //....2. Correct [ ]  Incorrect [ ]
    }
} // Class File

class ImageFile extends File {
    private boolean color;
    public static int numColors=2;
    public ImageFile() { }
    public ImageFile(int i, int s, int a, boolean c) {
	super(i,s,a);
	color = c;
    }
    public void whoDidIt() {
	System.out.println("Artist "+author_id); //....3. Correct [ ]  Incorrect [ ]
    }
    public static void strange1() {
	numColors++; //................................4. Correct [ ]  Incorrect [ ]
    }
    public void strange2() {
	numColors++; //................................5. Correct [ ]  Incorrect [ ]
	int twice = size*2; //.........................6. Correct [ ]  Incorrect [ ]
	super.useless1(); //...........................7. Correct [ ]  Incorrect [ ]
    }
} // Class ImageFile

public class Problem2 { 
    int size=3;
    public static void main(String[] args) {
	int tmp;
	File x = new File(1,1000,1013);
	tmp = x.id; //.................................8. Correct [ ]  Incorrect [ ]
	tmp = size; //.................................9. Correct [ ]  Incorrect [ ]
	tmp = x.author_id; //.........................10. Correct [ ]  Incorrect [ ]
	ImageFile pic = new ImageFile(101,9000,1234,true); 
	                                            //11. Correct [ ]  Incorrect [ ]
	pic.useless1(); //............................12. Correct [ ]  Incorrect [ ]
	tmp = pic.numColors; //.......................13. Correct [ ]  Incorrect [ ]
	x = new ImageFile(); //.......................14. Correct [ ]  Incorrect [ ]
	pic = new File(); //..........................15. Correct [ ]  Incorrect [ ]
    }
} // Class Problem2

*******

function Problem3
   count = 7;     % letters to choose
   bag=fillBag;   % form initial set of letters
   points = 0;

   disp(['Number of letters in bag:  ',num2str(length(bag))]);	

   [my_letters,bag] = pickLetters(count,bag); % grab count letters from bag
   [points,my_word] = enterWord(count,my_letters);  % get letters
   remain = getRemaining(my_word,my_letters);

   disp(['Final points:  ',num2str(points)]);
   disp(['Leftover letters: ',num2str(remain)]);
   disp(['Remaining letters in bag:  ',num2str(length(bag))]);

function [points,my_word] =  enterWord(count,my_letters)

  disp(['Your letters are: ', my_letters]); % display string of letters
  my_word=upper(input('Form a word: ','s'));       % ask user to enter a word
  while (~legal(my_letters,my_word))  % check that word is legal (<= length, good chars)
      disp('The word you entered is not a valid');
      my_word=upper(input('Form a word: ','s'));   % enter word again
  end
  points = length(my_word); % assign 1 point per letter


function letters=fillBag()
  A2F= 'AAAAAAAABBBBCCCCDDDDEEEEEEEEEEEEEEFFFF';
  G2P= 'GGGHHHHIIIIIJJKKLLLLMMMMNNNNOOOOOOPPPP';
  Q2Z= 'QRRRRSSSSTTTTUUUVVVVWWWXYYYZ';
  letters = [A2F G2P Q2Z]; % concatenate

function [letters,bag]=pickLetters(count,bag)
  letters='';
  for ii=1:count
     index=1+floor(rand*(length(bag)));  % random index of letter
     letters(ii)=bag(index);                  % extract letter
     bag=bag([1:index-1 index+1:length(bag)]); % remove $letter$ from $bag$
  end

function word=removeOccurences(lettersToRemove, word)

  for letterIndex = 1:length(lettersToRemove)
    removeIndexArray = findstr(word, lettersToRemove(letterIndex)); 
    if (~isempty(removeIndexArray))
      removeIndex = removeIndexArray(1);
      word = [word(1:removeIndex-1), word(removeIndex+1:end)];
    end
  end
   
function testValue = legal(letters,word)

  testValue = isEnglish(word) & isempty(removeOccurences(letters, word));
  
% need dictionary file!
function flag=isEnglish(word)
flag=1; % always true

function remaining = getRemaining(word,letters)

	remaining = removeOccurences(word, letters)
 

*********

public class Problem4 {
    public static void main(String[] args) {
	System.out.print("Welcome to BELT! Enter a size: ");
	TokenReader in = new TokenReader(System.in);
	int size = in.readInt();
	runSimulation(size,in);	
    }
    public static void runSimulation(int size, TokenReader in) {

       	// initialize stuff:
	Worker[] workers = new Worker[size];
	Tray[] trays = new Tray[size];
	for(int i=0;i<size;i++) {
	    workers[i]=new Worker();
	    trays[i]=new Tray();
	}
	
	Belt belt = new Belt(workers,trays);
	int run = 1;

	while(trays[size-1].currentBoxes()==0) {
	    System.out.println("Current run: "+run++);
	    doOneRun(belt);
	    in.waitUntilEnter(); // pause
	}
	System.out.println("The Workers are overloaded!");
	System.out.println("Leftovers: "+trays[trays.length-1].currentBoxes());

    }

    public static void doOneRun(Belt b) {
	b.shiftTrays();
	b.refillFirstTray();
	b.printContents("Old");
	b.extractContents();
	b.printContents("New");
	b.decreaseEfficiency();
	b.report();
    }

} // Class Problem4

class Belt {
    private int totalBoxes; 
    private Worker[] workers;
    private Tray[] trays;
    Belt(Worker[] workers,Tray[] trays) {
	this.workers = workers;
	this.trays=trays;
    }

    // print contents of all trays:
    public void printContents(String s) {
	System.out.print(s+" contents: ");
	for(int i=0;i <= trays.length-1;i++)
	    System.out.print(trays[i].currentBoxes()+" ");
	System.out.println();
    }

    // workers extract items from trays
    // increment totalBoxes and update leftovers:
    public void extractContents() {
	// each worker takes items from CURRENT tray
	for(int i=0;i <= workers.length-1;i++)
	    totalBoxes +=  workers[i].extractBoxes(trays[i]);
    }

    // shift Trays to the right
    public void shiftTrays() {
	// the last tray[size-1] is thrown out because it was empty:
	for(int i=trays.length-1;i>=1;i--)
	    trays[i] = trays[i-1]; 
    }

    // refill first tray
    public void refillFirstTray() {
	// first tray gets new items:
	trays[0] = new Tray();
	trays[0].fillTray();
    }
    
    // decrease worker efficiency for next run:
    public void decreaseEfficiency() {
	for (int i=0;i <= workers.length-1;i++)
	    workers[i].changeEfficiency();
    }
    // report findings:
    public void report() {
	System.out.println("Total boxes so far: "+totalBoxes);
    }

} // Class Belt

class Worker {
    private double efficiency;           // Worker efficiency initially ranges from 75% to 100%
    private final double FACTOR = 1.05;  // efficiency reduction factor
    //	Construct a new Worker and choose a random efficiency:
        public Worker() { setEfficiency(); }
    //	Set a random efficiency:
        private void setEfficiency() { efficiency = Math.random()*(1.00-0.75)+0.75; }

    // Actually, my efficiency model is bad(?) only workers who have done work should become less efff
    // there should be some modeling to apply rules -- maybe a hump -- start off stiff, loosen up, then get 
    // tired.

    //	Reduce current Worker's efficiency:
        public void changeEfficiency() { efficiency /= FACTOR; }
    //	Extract boxes from input Tray and update Tray's amount of boxes:
        public int extractBoxes(Tray tray) {
	// If Tray is empty, extract nothing:
	   if ( !tray.isEmpty() ) {
	       //  Based on efficiency, Worker extracts boxes:
	           int boxes = (int) Math.round(efficiency*tray.currentBoxes());
	       //  Remove boxes from current Tray:
		   tray.removeBoxes(boxes);
	       //  Return amount of extracted boxes:
		   return boxes;
	}
	// Otherwise, return no boxes because Tray is empty:
	return 0;
    }
} // Class Worker

class Tray { 
    private final int MIN = 0;     // minimum amount of boxes stored on a Tray
    private final int MAX = 5;     // maximum amount of boxes stored on a Tray
    private int boxes;             // amount of boxes on current Tray
    //	Construct an "empty" Tray:
        public Tray() { }
    //	Return the number of boxes on current Tray:	
        public int currentBoxes() { return boxes; }
    //	Reduce the number of boxes on current Tray by input $r$: 	
        public void removeBoxes(int r) { if (!isEmpty()) boxes=boxes-r; }
    //	Store a random amount of boxes on the current Tray:
        public void fillTray() { boxes = (int) Math.floor(Math.random()*(MAX-MIN+1))+MIN; }
    //	Return a Boolean value depending on whether or not current Tray is empty:
        public boolean isEmpty() { return (boxes == 0); }
} // Class Tray

*******

public class Problem5 {
    public static void main(String[] args) {
	    new Game();
    }
}

class Game {
    private int target;   // randomly chosen number
    private int guess;    // guess of $target$
    private int count;    // number of guesses to reach $target$
    private final int LOW=0;      // lowest value of $target$
    private final int HIGH=100;     // highest value of $target$
    private final int STOP=HIGH-LOW;     // how many guesses?

    
    // Construct a $NumberGuess$ object:
    public Game() {
	target = guessNumber();   // choose a random number $target$
	guessForTarget();         // prompt user to guess for $target$
	reportGame(); // report results of current game
    }
    
    // Report results of game:
    private void reportGame() {

	System.out.println(guess);
	if (guess==target){
	    System.out.println("Hooray for Java!");
	    System.out.println("Java took "+ count);
	}
	else {
	    System.out.println("Boo for Java!");
	    System.exit(0);
	}
    }

    private int guessNumber() {
	return (int) Math.floor(Math.random()*(HIGH-LOW+1))+LOW;
    }

    // guess
    private void guessForTarget() {
	
	int right = HIGH;
	int left = LOW;
	double rawguess;

	do {
	    rawguess = (right+left)/2.0;

	    if (rawguess < target) // guess becomes new left point 
		rawguess = left =  (int) Math.ceil(rawguess);
	    
	    else if (rawguess > target)
		rawguess = right = (int) Math.floor(rawguess);
	    
	    guess = (int) rawguess;
	    
	    count++;

	    System.out.println(count+" "+target+" "+rawguess+" "+guess);
	    
	} while( guess != target && count < STOP);
	
	if (count >= STOP) {System.out.println("stopping"); System.exit(0);}

    }
} // Class NumberGuess