Sunday, January 25, 2015

CalendarRecycle

Problem:

TopCoder Problem Statement - CalendarRecycle
Single Round Match 163 Round 1 - Division II, Level Two

Overview:

Determine the next year that shares a calendar with the given year. That is, all dates fall on the same day of the week.

Java Source:
01: import java.util.Calendar;
02: import java.util.GregorianCalendar;
03: 
04: public class CalendarRecycle {
05: 
06:  public int useAgain(int year) {
07: 
08:   boolean firstYearIsLeap = isLeapYear(year);
09: 
10:   int dayOfWeek = 0;
11: 
12:   while(true)  {
13: 
14:    // Determine which day the next year starts on.
15:    dayOfWeek += 365;
16:    if (isLeapYear(year)) dayOfWeek++;
17:    dayOfWeek %= 7;
18: 
19:    year++;
20: 
21:    /*
22:    * If the next year starts on the same day of the week, and they
23:    * have the same leap year status, then return.
24:    */
25:    if ((dayOfWeek == 0) && (firstYearIsLeap == isLeapYear(year)))  {
26:     return year;
27:    }
28:   }
29: 
30:  }
31: 
32:  private static boolean isLeapYear(int year)  {
33: 
34:   // If the year is divisible by 4
35:   if ((year % 4) == 0)  {
36: 
37:    // And not divisible by 100, unless also divisible by 400
38:    if ((year % 100 != 0) || ((year % 400) == 0))  {
39:     return true;
40:    }
41:   }
42: 
43:   return false;
44:  }
45: 
46: 
47: 
48:  /*
49:  * An alternate solution using Java's GregorianCalendar.
50:  */
51:  public int useAgain2(int year)  {
52: 
53:   GregorianCalendar c = new GregorianCalendar(year, Calendar.JANUARY, 1);
54:   int initialDayOfWeek = c.get(Calendar.DAY_OF_WEEK);
55: 
56:   while (true)  {
57:    c.add(Calendar.YEAR, 1);
58:    if ((c.get(Calendar.DAY_OF_WEEK) == initialDayOfWeek) &&
59:      (c.isLeapYear(c.get(Calendar.YEAR)) == c.isLeapYear(year))) {
60:     return c.get(Calendar.YEAR);
61:    }
62:   }
63:  }
64: }
Notes:

We say that two calendars are the same if the meet the following conditions:

  1. Any date falls on the same day of the week. (i.e. Jan 1 is a Sunday for both years). and
  2. Both years have the same leap year status. Either both are, or both aren't leap years.

The first thing useAgain() does is store the leap year status of the current year. We'll need this later to check that it matches the status of the candidate year.

Next, we set dayOfWeek to it's initial value. Note that we don't care what day this represents. It could be Sunday, Monday, etc. The only thing that matters is that we return to this value.

Finally, it's just a matter of adding 365 (+1 if it's a leap year), mod'ing that by 7 and seeing if we're back to the starting day. If so, and the leap year status matches, we've found our answer.

The logic for isLeapYear() is taken directly from the problem description. First check to see if the year is divisible by 4. If so, then check to see if it's not divisible by 100, unless it is also divisible by 400.

I've provided an alternate solution in useAgain1() that makes use of Java's GregorianCalendar.

Here, we create a new GregorianCalenar for January 1st of the given year (any date could have been chosen), and remember its day of the week. Then we keep adding a year and checking the day of the week and leap year status just as before.

An interesting note about GregorianCalendar - it provides an instance method isLeapYear(int year). A better way would be to create a static method GregorianCalendar.isLeapYear(int year) that could give the result for any year; and also provide an instnace method isLeapYear() with no parameters that gives the status of the current object. With the chosen implementation, you must create an instance of the GregorianCalendar to get the leap year status of some year that may be unrelated to that object. The second half of useAgain2()'s if statement could be much cleaner as:

GregorianCalendar.isLeapYear(year) == c.isLeapYear()

No comments:

Post a Comment