Monday, April 6, 2015

Animation

Problem:

TopCoder Problem Statement - Animation
Single Round Match 167 Round 1 - Division I, Level One
Single Round Match 167 Round 1 - Division II, Level Two

Overview:

Simulate particles moving both left and right through a chamber.

Java Source:
01: import java.util.ArrayList;
02: import java.util.List;
03: 
04: public class Animation {
05: 
06:  public static final char EMPTY_POSITION = '.';
07:  public static final char OCCUPIED_POSITION = 'X';
08:  public static final char RIGHT = 'R';
09:  public static final char LEFT = 'L';
10: 
11:  // If the position contains both a R and L moving particle.
12:  public static final char BOTH = 'B';
13: 
14:  public String[] animate(int speed, String init) {
15: 
16:   List result = new ArrayList<>();
17: 
18:   result.add(init);
19: 
20:   String prevFrame = init;
21: 
22:   while(!isEmptyChamber(prevFrame))  {
23:    char[] nextFrame = new char[init.length()];
24: 
25:    // Initialize the chamber to all empty;
26:    for (int i = 0; i < nextFrame.length; i++)  {
27:     nextFrame[i] = EMPTY_POSITION;
28:    }
29: 
30:    for (int i = 0; i < prevFrame.length(); i++)  {
31:     if (prevFrame.charAt(i) != EMPTY_POSITION)  {
32: 
33:      if ((prevFrame.charAt(i) == RIGHT) || (prevFrame.charAt(i) == BOTH))  {
34:       int newPos = i + speed;
35:       if (newPos < nextFrame.length)  {
36:        if (nextFrame[newPos] == LEFT) {
37:         nextFrame[newPos] = BOTH;
38:        } else  {
39:         nextFrame[newPos] = RIGHT;
40:        }
41:       }
42:      }
43: 
44:      if ((prevFrame.charAt(i) == LEFT) || (prevFrame.charAt(i) == BOTH))  {
45:       int newPos = i - speed;
46:       if (newPos >= 0)  {
47:        if (nextFrame[newPos] == RIGHT)  {
48:         nextFrame[newPos] = BOTH;
49:        } else  {
50:         nextFrame[newPos] = LEFT;
51:        }
52:       }
53:      }
54: 
55:     }
56:    }
57: 
58:    String s = new String(nextFrame);
59:    result.add(s);
60:    prevFrame = s;
61: 
62:   }
63: 
64:   // Convert the List into a String[] and return it.
65:   String[] resultList = new String[result.size()];
66: 
67:   for (int i = 0; i < result.size(); i++)  {
68:    resultList[i] = markOccupied(result.get(i));
69:   }
70:   return resultList;
71:  }
72: 
73:  /*
74:  * Replaces any position marked with a 'R', 'L', or 'B'
75:  * with an 'X'
76:  */
77:  private static String markOccupied(String s)  {
78: 
79:   StringBuilder sb = new StringBuilder(s.length());
80: 
81:   for (int i = 0; i < s.length(); i++)  {
82:    sb.append((s.charAt(i) == EMPTY_POSITION) ? EMPTY_POSITION : OCCUPIED_POSITION);
83:   }
84: 
85:   return sb.toString();
86:  }
87: 
88:  /*
89:  * Returns true iff the chamber is empty.
90:  */
91:  private static boolean isEmptyChamber(String s)  {
92: 
93:   for (int i = 0; i < s.length(); i++)  {
94:    if (s.charAt(i) != EMPTY_POSITION)  return false;
95:   }
96: 
97:   return true;
98:  }
99: }
Notes:

This is a pretty simple simulation. In each iteration of the loop, we use the current state to create the next state. At the end of the loop, we set the current state equal to next, and repeat.

At the start of each loop, check to see if the chamber is empty. The isEmptyChamber() just looks at the input String one character at a time. As soon as it finds any character that is not EMPTY_POSITION, it returns false. If it reaches the end of the String, it returns true.

If we have a non-empty chamber, then we iterate through each position. The value at any position will either be 'L' for a left moving particle, 'R' for a right moving particle, 'B' if a 'R' and 'L' overlap, or a '.' if the position is empty. For either a 'L' or an 'R', we calculate the new position by either adding or subtracting speed, checking to make sure we stay within the bounds of the array. If the position is marked 'B', then a particle will be placed both to the left and to the right.

Because we don't know how large the return String[] will be, it is maintained as a List and then converted at the end. During this covnersion, we also change all 'L', 'R', and 'B' characters to just 'X'.

The only difficulty here is being careful to manage positions where left and right moving particles overlap, and ensuring that you don't try to move a particle outside the bounds of the array.

EyeDrops

Problem:

TopCoder Problem Statement - EyeDrops
Single Round Match 167 Round 1 - Division II, Level One

Overview:

Determine a schedule for taking medication.

Java Source:
01: public class EyeDrops {
02:
03:     public double closest(int sleepTime, int k) {
04:
05:         double interval = 24.0 * 60.0 / (double) k;
06:
07:         if (interval > (sleepTime * 60)) return interval;
08:
09:         return 60.0 * (24 - sleepTime) / (double) (k - 1);
10:     }
11: }
Notes:

There are two cases to consider here. One in which our calculated interval is shorter than the sleep time. The other is when the interval is longer.

Begin by calculating the interval by dividing the day up into k equal segments (line 5) - ignoring sleepTime for the moment. If the sleepTime fits entirely within one of those intervals, then simply return the interval. In this case, the person could take the drops, remain awake for a period of time, then sleep, wake back up, and take the drops again. The interval is the same just as if they had never slept.

For example, if the drops needed to be taken twice per day and you slept for 8 hours per day, them the drops would be taken every 12 hours, and the sleep time would not affect the schedule.

In the second case, we need to subtract the sleepTime off the length of the day, and then divide the remainder of the day by k-1 to get the interval.

An example of this case is if the person sleeps for 8 hours and then needs to take the drops 5 times. Here, they'd take the first drop as soon as the woke up (say 8:00 AM). They'd take the remaining drops at 12:00PM, 4:00PM, 8:00PM, and finally at 12:00AM (just before going back to sleep).

Be careful to cast ints to doubles where needed.