Saturday, November 23, 2002

Implementation

With a limit of 15 choosers, there are at most 2¹⁵ configurations of the choosers, and 15 possible locations for the ball. This gives us a total of 15*2¹⁵ possible states. We can then move the ball around, according to the rules, and cache the states we reach. Then, if we ever reach the same state twice, there is a loop, since the sequence of states is totally deterministic. This can be simply implemented by representing each of the states as a bitmask and using an array as a cache.

If the input was larger, we might run into memory limits and would have to find a different solution. One other way to do this is to run the marble through twice, simultaneously, with one marble moving through two choosers at a time, while the other only goes through one at time. Then, if the one going twice as fast every gets to the same state as the slow one, there is a loop somewhere. However, this isn't neccessary.

Implementation

This is a classic string parsing problem. You should start in a CODE state, and then scan the strings, one at a time. If you hit "//" then you simply ignore the rest of the line. If you hit "/*", then you ignore until you see "*/". One thing to watch for is the case {"/*/*/"}, where the output should be {}, not {"*/"}. It was this case that caused SnapDragon to resubmit.

The most difficult case to handle is probably that involving double quotes. If you are in the CODE state, and you see a double quote, you should then ignore all characters until you see another double quote. However, there is the possibility that there will be an escaped double quote, which must not terminate the first double quote. A few other things to watch out for are slashes at the end of strings, and slashes at the end of one string, followed by an asterisk at the beginning of the next.

Implementation

Computational geometry is always ugly, and tonight was certainly no exception. This problem combined three subtasks. You have to be able to reflect a ray when it hits a segment, find the intersection of a line and a ray, and find the distance from a line to a point.

Once you solve all of these subproblems using some dot products and cross products and such, its not too hard to combine then, but its certainly not trivial. You should start with the ray defined by the start input. Then, you should find the intersection between this ray, and every mirror. Of all the mirrors that the ray intersects, you have to find the one closest to the start, and pick it. Then, you also have to check if the ray hits an object before it hits the mirror. If it does, you are done, otherwise, you reflect the ray with the mirror you found, and repeat the whole process until you either hit an object, yourself, or the hit no mirrors.

One interesting note to add is that there are classes in java.awt which have methods for finding the distance from a line to a point, and whether or not two lines intersect. Using this can make it much easier, but unfortunately for them, all the coders used C++.