Monday, August 4, 2014

Birthday

Problem:

TopCoder Problem Statement - Birthday

Overview:

Given a set of dates, determine the next date to occur after a given date.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 151
04: Division: 2
05: Level: 2
06: Points: 500
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1739
08:  */
09: 
10: import java.util.ArrayList;
11: import java.util.Arrays;
12: import java.util.Collections;
13: import java.util.List;
14: 
15: public class Birthday {
16: 
17:     public String getNext(String date, String[] birthdays) {
18: 
19:         List reminders = new ArrayList<>();
20:         for (String s : birthdays) {
21:             reminders.add(new Reminder(s));
22:         }
23:         Collections.sort(reminders);
24: 
25:         Reminder now = new Reminder(date);
26: 
27:         for (Reminder next : reminders) {
28:             if (next.compareTo(now) >= 0) {
29:                 return next.toString();
30:             }
31:         }
32: 
33:         return reminders.get(0).toString();
34:     }
35: 
36:     public class Reminder implements Comparable {
37: 
38:         final int month;
39:         final int day;
40:         final String monthStr;
41:         final String dayStr;
42: 
43:         public Reminder(String s) {
44: 
45:             String s1[] = s.split("( )|(/)");
46:             month = Integer.parseInt(s1[0]);
47:             day = Integer.parseInt(s1[1]);
48:             monthStr = s1[0];
49:             dayStr = s1[1];
50:         }
51: 
52:         public int compareTo(Object o) {
53: 
54:             Reminder other = (Reminder) o;
55:             if (month < other.month) { return -1; }
56:             if (month > other.month) { return 1; }
57:             if (day < other.day) { return -1; }
58:             if (day > other.day) { return 1; }
59:             return 0;
60:         }
61: 
62:         public String toString() {
63: 
64:             return monthStr + "/" + dayStr;
65: 
66:         }
67:     }
68: 
69:     public String getNextImproved(String date, String[] birthdays) {
70: 
71:         Arrays.sort(birthdays);
72: 
73:         for (String next : birthdays) {
74:             if (next.compareTo(date) >= 0) {
75:                 return next.split(" ")[0];
76:             }
77:         }
78: 
79:         return birthdays[0].split(" ")[0];
80:     }
81:     
82: }
Notes:

This solution illustrates 2 important concepts. First is Java's Comparable interface:

The solution creates an inner class named Reminder that implements Comparable. This allows us to easily sort and compare dates. The Reminder class takes a String for it's constructor and parses out the month and day. Next, it provides compareTo() which uses the month and day to determine if another Reminder comes before, after, or is equal to the current object. Finally, Reminder provides a toString() method to give the date in the format required.

Using the Remidner class, the for loop at line 20 converts all the Strings into Reminders. Then we sort them on line 23. The remaining lines get the new date and use compareTo() to find the first date that comes after the given date. If there are no such dates, then we return the first date of the new year.

Now, for the second important lesson - don't rush to start coding! In this case, birthdays could have been sorted just the way they were, as Strings. Given their format of MM/DD, birthdays would be sorted in exactly the same way. If the format was DD/MM - then this would not be the case. But here, the Reminder class was completely unnecessary. I've included the method getNextImproved() at the bottom which is obviously much better.

No comments:

Post a Comment