HW 2 Solutions class Date { /* Put your private data fields here. */ int month, day, year; /** Constructs a date with the given month, day and year. If the date is * not valid, the entire program will halt with an error message. * @param month is a month, numbered in the range 1...12. * @param day is between 1 and the number of days in the given month. * @param year is the year in question, with no digits omitted. */ public Date(int month, int day, int year) { this.month = month; this.day = day; this.year = year; } /** Constructs a Date object corresponding to the given string. * @param s should be a string of the form "month/day/year" where month must * be one or two digits, day must be one or two digits, and year must be * between 1 and 4 digits. If s does not match these requirements or is not * a valid date, the program halts with an error message. */ public Date (String s) { int firstSlash = s.indexOf('/'); int lastSlash = s.lastIndexOf('/'); month = Integer.parseInt(s.substring(0,firstSlash)); day = Integer.parseInt(s.substring(firstSlash+1, lastSlash)); year = Integer.parseInt(s.substring(lastSlash+1, s.length())); if (!isValidDate(month, day,year)) throw new IllegalArgumentException(); } /** Checks whether the given year is a leap year. * @returns true if and only if the input year is a leap year. */ public static boolean isLeapYear(int year) { if ((year % 400)==0) return true; if ((year % 100)==0) return false; if ((year % 4)==0) return true; return false; } /** Returns the number of days in a given month. * @param month is a month, numbered in the range 1...12. * @param year is the year in question, with no digits omitted. * @return the number of days in the given month. */ public static int daysInMonth(int month, int year) { switch (month) { case 1: case 3: case 5: case 7: case 8: case 10: case 12: return 31; case 2: if (isLeapYear(year)) return 29; else return 28; default: return 30; } } /** Checks whether the given date is valid. * @return true if and only if month/day/year constitute a valid date. */ public static boolean isValidDate(int month, int day, int year) { if ((month < 0) || (month > 12)) return false; if (year == 0) return false; if ((day < 0) || (day > daysInMonth(month,year))) return false; return true; } /** Returns a string representation of a date in the form month/day/year. * The month, day, and year are printed in full as integers; for example, * 12/7/1998 or 3/21/407. * @return a String representation of the date. */ public String toString() { return month + "/" + day + "/" + year; } /** Determines whether this Date is before the Date d. * @return true if and only if this Date is before d. */ public boolean isBefore(Date d) { if (this.year < d.year) return true; if (this.year > d.year) return false; if (this.month < d.month) return true; if (this.month > d.month) return false; return (this.day < d.day); } /** Determines whether this Date is after the Date d. * @return true if and only if this Date is after d. */ public boolean isAfter(Date d) { if (this.year > d.year) return true; if (this.year < d.year) return false; if (this.month > d.month) return true; if (this.month < d.month) return false; return (this.day > d.day); } /** Returns the number of this Date in the year. * @return a number n in the range 1...366, inclusive, such that this Date * is the nth day of its year. (366 is only used for December 31 in a leap * year.) */ public int dayInYear() { int yeardays = 0; for (int i = 0; i < month; i++) yeardays += daysInMonth(i, year); yeardays += day; return yeardays; } /** Determines the number of days between d and this Date. For example, if * this Date is 12/15/1997 and d is 12/14/1997, the difference is 1. * If this Date occurs before d, the result is negative. * @return the number of days between d and this date. */ public int difference(Date d) { Date first=null, second=null; int days = 0; if (isBefore(d)) { first = this; second = d; } else { second = this; first = d; } if (first.year == second.year) return (second.dayInYear() - first.dayInYear()); if (isLeapYear(first.year)) days += (366-first.dayInYear()); else days += (365-first.dayInYear()); for (int i = first.year+1; i 0)) days -= 366; //no year 0 if (first == this) return -days; else return days; } } 2a. class Towers{ public static void move(int n,int from, int to, int helper){ if (n > 0) { Move(n-1, from, helper, to); System.out.println(from + "->" + to); Move(N-1, helper, to, from); } } public static void main(String[] args){ int t = Integer.parseInt(args[0]); move(t, 1, 3, 2); } } 2b. // Stolen (with minor modifications) from Ryan Said (cs61b-cd) import java.util.*; class Towers2 { static Stack pole1 = new Stack(); static Stack pole2 = new Stack(); static Stack pole3 = new Stack(); static void towers2(int numRings) { if (numRings == 0) return; /** push numRings + 1 to each stack to represent the base of each pole */ pole1.push(new Integer(numRings + 1)); pole2.push(new Integer(numRings + 1)); pole3.push(new Integer(numRings + 1)); /**push numRings rings on to pole 1. The smallest ring is "1", the largest is numRings */ for (int i = numRings; i >= 1; i--) pole1.push(new Integer(i)); Stack destination; //destination of ring during a move Stack source; //the pole the ring was moved from Stack third; //the pole not involved in the move /** If numRings is odd, first move is from pole1 to pole3 */ if(isOdd(new Integer(numRings))) { destination = pole3; source = pole1; third = pole2; destination.push(source.pop()); System.out.println("1->3"); } /** If numRings is even, first move is from pole1 to pole2 */ else { destination = pole2; source = pole1; third = pole3; destination.push(source.pop()); System.out.println("1->2"); } /** Continue iterating if there is something on either pole1 or pole2 */ while (!( ((((Integer) pole1.peek()).compareTo(new Integer(numRings + 1)) == 0 )) && ((((Integer) pole2.peek()).compareTo(new Integer(numRings + 1)) == 0 )) )) { /** Store previous pointers of source, destiantion, and third for assigning purposes */ Stack sourceTemp = source; Stack destinationTemp = destination; Stack thirdTemp = third; /** If the last ring to be moved was an odd number, then the next exchange is between the other two poles, where the smaller ring is placed on the larger */ if (isOdd((Integer) destination.peek())) { /**Exchange between source and third pole: */ Integer ringSource = (Integer) source.peek(); Integer ringThird = (Integer) third.peek(); if (ringSource.compareTo(ringThird) == -1) { //move from source to third third.push(source.pop()); destination = third; // source stays the same, still a source third = destinationTemp; printMove(source, destination); } else { //move from third to source source.push(third.pop()); destination = source; source = third; third = destinationTemp; printMove(source, destination); } } /** If the last ring moved was an even number, then the destination pole remains a destination pole and we move a ring from the third pole in the last exchange */ else { destination.push(third.pop()); source = third; third = sourceTemp; printMove(source, destination); } } } /** isOdd returns true if n (type Integer) is an odd integer */ static boolean isOdd(Integer n) { return ((n.intValue() %2) == 1) } static void printMove(Stack source, Stack destination) { /** Print move */ String from; if (source == pole1) from = "1"; else if (source == pole2) from = "2"; else from = "3"; String moveTo; if (destination == pole1) moveTo = "1"; else if (destination == pole2) moveTo = "2"; else moveTo = "3"; System.out.println(from + "->" + moveTo); } public static void main(String[] args) { towers2(Integer.parseInt(args[0])); } } // Alternate Solution, provided by Alice. Not what I had in mind, // but definetly gets creativity points. import java.util.Stack; /** An iterative solution to the Towers of Hanoi. */ public class Towers2 { /** Simulate recursion by using a Stack. */ private static Stack stack; /** Given a number of rings, solveIt() moves them from pole 1 to pole 3. */ public static void solveIt(int numRings) { stack = new Stack(); stack.push(new Subproblem(numRings, 1, 3)); while (!stack.isEmpty()) { process((Subproblem)stack.pop()); } } /** Given a subproblem, process() breaks it down and pushes the new subproblems onto the stack. If the subproblem can be solved immediately (i.e. only one ring needs to be moved), just prints the move. */ private static void process(Subproblem sp) { if (sp.numRings==1) { System.out.println(sp.from+"->"+sp.to); } else { stack.push(new Subproblem(sp.numRings-1, 6-sp.from-sp.to, sp.to)); stack.push(new Subproblem(1, sp.from, sp.to)); stack.push(new Subproblem(sp.numRings-1, sp.from, 6-sp.from-sp.to)); } } /* Calls solveIt with the command line argument. */ public static void main(String[] args) { solveIt(Integer.parseInt(args[0])); } } /** A container for the info necessary to describe a subproblem. */ class Subproblem { int from; int to; int numRings; Subproblem(int numRings, int from, int to) { this.from=from; this.to=to; this.numRings=numRings; } } 2c. in 2^64-1 seconds, or roughly in the year 584942400000. 3. Here are just come possible right answers... a. An Event should be an abstract class. We don't really know enough about what it should do to make it non-abstract, yet we will want all sub-events (Birthdays, TimedEvents, etc) to inherit from it so we can treat the similarly. b. A TimedEvent can be either an abstract class or an actual class. c. A Timer should be an interface providing a hasOccured() method. If an event implements this interface we can easily check whether it has already occured. d. Birthday should be a non-abstract class. e. Todo should be an interface that sub-classes of event may implement. f. eventChecker should be a method, not a class. g. A day can either be a class outside of the previous hierarchy or just a linked list or array with events. 3 Alternate: Alice's answers. Although different from mine they are just as valid. Event: An abstract class (or maybe an interface). All Events have some similarities, however, we want different kinds of Events to behave slightly differently. TimedEvent: An abstract class which extends Event. It's a kind of event, but still too general to actually use. Timer: A method rather than a class. It stores no data; it actually *does* something. Birthday: A regular class which extends Event. It's specific enough not to be abstract -- we want to put birthdays right on the planner. Todo: A regular class. Stores the task and deadline if there is one. Alternatively, we could make it abstract and have two subclasses, one for tasks with deadlines and one for tasks without deadlines. EventChecker: A method. Like Timer, it performs one specific action. Day: A regular class. We can store the list of events as a field, and implement methods to display the events, add events, etc.