As has become customary for me, I participated in the annual ICFP programming contest this weekend. I participated as a lone coder this time with the team name "rmathew". The contest this year was irritating and frustrating, not to mention quite humbling (as usual).
The task description was obtuse and it took me at least a couple of readings to even understand what we were supposed to do. Even after understanding it, I didn't feel motivated to solve it as it seemed to have been devised simply to frustrate people. I still went ahead with it as I had already set aside some time for this year's contest.
The overall task was to create cars and fuel for such cars. You had to create cars for which it would be difficult for others to supply fuel and you had to supply fuel to as many other cars as possible. The engines of the cars were provided as streams of "trits" (ternary, or base-3, digits) for which you had to figure out the encoding. Fuel had to be created using circuits that used ternary logic gates for which you had to figure out the encoding of the circuits, the logic used by the gates, the input stream provided to the circuits by the server and the validating key in the output stream without which your circuits were rejected.
The worst part was that you had figure all this out by using educated guesses and by looking at the error messages spewed by the server hosted by the organisers. Needless to say, the server didn't stay up for long and had issues throughout the contest.
The gates took two input trits (left and right) and produced two output trits (left and right). My guess about the format used for encoding the circuits turned out to be right and after a couple of trials it became apparent that there was only one type of gate. I could not figure out a programmatic way of determining the logic used by the gates, so I used pen and paper with a few simple circuits to figure out the logic using the error messages from the server as a guide. The truth-tables (left-input varies by rows, right-input by columns) turned out to be:
LO = (LI - RI + 3) mod 3
RO = (LI * RI + 2) mod 3
The nice structure of the left-output table also allows you to then determine the input stream used by the server. Using this information, I coded a simple circuit simulator that I then used on the key circuit given in the task description to find out the key sequence desired in every output stream.
To proceed further, I needed to figure out how to create a circuit that can convert a given input stream into a given output stream. This is where I hit a dead-end - I just could not work out how to approach this problem without using brute force and that seemed quite prohibitive considering the possibilities. To distract myself I created a simple circuit visualisation tool that converted a description like this:
into a file that could then be converted by Graphviz into this image:
Ha!), but that didn't get me anywhere.
If you're interested, you can see the source-code on Bitbucket.