Daily Update Saturday Oct. 11 (Programming Competition)

1.     Daily Update Saturday Oct. 11

a.     Woke up bright and early and biked over to the programming competition! The first task was to find the room, hidden under the CSE building. Tried to find Team House Baratheon in crowd but failed.

b.     After reviewing the nature of the competition—a bunch of problems that you write code to solve and then submit the code online to judges; most problems solved wins and tiebreaks are on total time—we trekked over to the lab, where we solved a practice problem.

c.      Got manila envelope containing problems. After solving the easy first problem, my teammates, a junior and senior (I was only assigned to their team because I registered late and someone on their team couldn’t come) went to work on a complicated problem involving networks and the shortest path out of a network. We could only use one computer between us, so I started working on other problems on paper. Two hours later, pizza arrived and they finally solved the problem. I punched in the solution to the other easy problem. After review by my teammates, I realized an intermediate problem defied my simple solution. After some debate, my teammate punched in the revised solution, we debugged it, and submitted it.

d.     Now the going got intense. I fruitlessly struggled to find another easy problem in the remaining problems, gave up on two, then found an intriguing geometry problem. Basically, you had a rover that could only move 10 units in its current direction or rotate 45 degrees to the right. Each action took one second. Given a integer (x,y) point and the number of seconds available to the rover, figure out how close the rover can get to the given point. A clean mathematical solution eluded me. Eventually a crazy idea took hold of me. The maximum amount of seconds that would be specified was 24; on each of those seconds, the rover would take one of two actions. Thus the total number of final outcomes was 2^24, only about 16 million. So I embarked on a mad mission to brute-force the problem by exploring each of the possible outcomes. I used a recursive algorithm to traverse all outcomes. When I first ran the algorithm, it actually ran in the given amount of time. But I still had to go through each final position and calculate the distance to the target point to determine the closest the rover could get to the target point. To do this, I had to square each of 32 million floating point values and take the square root, a much more costly operation than those used to get from one level of recursion to the next. Even when I removed the square root and compared the squared distances, the algorithm turned out to be too slow. (I am convinced the problem designers chose 24 seconds on the precise threshold between brute-force-eable and exponentially too difficult to force, to trick coders into pursuing an approach that doesn’t quite work.) I just might have been able to bring the runtime within the threshold, but I ran out of time.

e.     While I was working on paper designing this algorithm, my teammates came this close to solving another problem. It worked on every sample value they could think of, but there was some edge case they couldn’t think of on which the program choked.

f.      So we almost solved six problems, but only ended up finishing four. This put us in the middle of the pack, a result that I was very happy with. The whole thing was a great experience, and my teammates were very nice to me despite my noobity.

g.     After the contest, I went back to the dorm, then went out and played some one-on-one basketball.

h.     Made it back to the dorm in time to watch the end of the UW vs. Cal football game with Jamie.

i.       Worked on journal updates.

j.       Went to get dinner at the 8; read more Logicomix.

k.     Returned to dorm, worked more on the journal.

l.       Did education homework (I’m going to be the discussion facilitator next week) and went to bed.