|
Match Editorial |
 |
|
||||||||||||
| |||||||||||||
| MATCH EDITORIAL LINKS: | |||||||||||||
|
|||||||||||||
| |||||||||||||
May 21, 2002
The Problems
The Level One was simply to write the algorithm they described - not hard at all. One could keep a "current index" for the roaster and move it forward, or simply calculate it at each point with a modulus. Probably the hardest part was the formatting for the output. ZorbaTHut's solution used the C++ sprintf() function, while John Dethridge did the conversion by hand. For Java, kv's solution demonstrates a clever solution - adding 256 to it, thereby forcing a 0 in the second place if it's less than 16, converting it to hex, and chopping the first character off. kv's solution was also the fastest.
The Level Two, on the other hand, was a simple simulation - follow the instructions, code the program. Keep an array of everyone's score, keep track of the current "3-man", current player, and current place in the pickValues, and just do it. You could code it slightly faster if you realized that "add one to everyone's score" didn't actually need to be done - since all you care about is the lowest score, obviously writing that isn't going to change anything. Yarin's solution, the fastest, is also quite easy to read.
As for the Level Three, only two solutions survived - John Dethridge's and ZorbaTHut's - and both of them are basically unreadable, though I believe John's is slightly better than mine. I don't know what his solution involves - however, I'll try to explain mine a little bit. I've got it set up to organize the components by name, not by adding ID numbers or anything, and the pin identifiers I used are, in fact, the same ones used in the input. (I was slightly worried about speed, but I didn't think it would be an issue - it wasn't.)
First I simplified the wiring into what I termed "melanges" - a pretty lousy term overall, but it serves its purpose. If A is connected to B, and B is connected to C, then logically speaking, A is connected to C also. Therefore, I don't care about the internal setup; I only care what's contained in the "networks" that are connected to each other. So I went through and found what all the connections were in each group - start with the "first" wire in the group, then add more things if they're directly connected until you've passed through the entire remaining wires once without having to add anything. Repeat until all the wires are in one group or another. The random_shuffle is simply to get rid of a potential worst-case scenario - it may have been unnecessary, but I didn't feel it worth the risk.
After that, I went through and parsed all the components, connecting each pin to a melange. I'd already defined "melange 0" as "nothing connected", and therefore undefined - the real melanges started at #1. This meant I could use C++'s std::map to default to 0, since that's the behavior if you access something that doesn't yet exist.
Once all the pins were connected, I simply started at the output component (which I'd stored when parsing the components) and recursively descended down. Calculating a melange, I started with the first output pin it was connected to and set the overall melange to that. Then I went through the rest of the output pins, and if any conflicted with its current value, I set it to UNDEFINED. An output pin was obviously a recursive call of its own - AND gates and OR gates were calculated according to the given rules, using their own melanges as input. Through all this I cached the results to avoid speed problems. I did INPUTs simply as precached results, with no logic behind them to recalculate them otherwise.
And then it was just a matter of translating from the constant values I'd come up with to the output strings, and that was the solution.
