After taking part in Google's Code Jam and the more recent IPSC, which was an abject failure, we found another coding competition: ICFP. ICFP ran for 72 hours this weekend, from 8AM Friday to 8 AM Monday (EST). We worked on it for a total of about 12 hours each, because things like eating, swim practice, family chores, sleep, etc, got in the way. We competed under the team name of IDKJava as usual, and we were very hopeful going into it, and pretty satisfied, but a little annoyed coming out. If you want to take a look at the problem which we were trying to tackle, here is the
.
The results were that with five minutes left of the contest, we were two digits away from getting the key prefix (a total of 17 digits) and we knew how to fix it. Unfortunately, we ended up finishing several minutes after the end. We are disappointed that we were not able to finish in time, but we were pretty proud of what we were able to do, because the problem was really challenging, and if not for a few stupid mistakes, we would have submitted a working circuit for the first car, which would have gotten us more than 0.000 points, and bumped us into the top ~200. If you want to know what we did each day, and more of the technical details, read on.
The circuit that we ultimately designed to output the correct key prefix was:
30R:
3L3R0#1L1R,
0L0R0#2L2R,
1L1R0#30LX,
4L4R0#0L0R,
5L5R0#3L3R,
6R6L0#4L4R,
8L8R0#5R5L,
9R9L0#8R8L,
7R7L0#6L6R,
11L11R0#7R7L,
12R12L0#11L11R,
10L10R0#9L9R,
13L13R0#10R10L,
14L14R0#12L12R,
15L15R0#13L13R,
16L16R0#14L14R,
18L18R0#15L15R,
19L19R0#18L18R,
17L17R0#16L16R,
22L22R0#17L17R,
28R28L0#21R21L,
20R20L0#22R22L,
21R21L0#19L19R,
29L29R0#24L24R,
23L23R0#25L25R,
24L24R0#26L26R,
25L25R0#27L27R,
26L26R0#28L28R,
27L27R0#20R20L,
30L30R0#23L23R,
2LX0#29L29R:
2R
Basically, it has gates in a row, connected to each successive gate with backward wires. The input thus moves down the chain one gate every click. By changing which outputs connected to the next gate and by adding in gates that were connected by forward wires we were able to modify the output to achieve the key prefix that we needed to submit in order to get past the first car.
Unfortunately, this technique was realized late Sunday night, and it was not until the next morning when Ryan woke up and explained it better that we were able to finish the circuit. If we had worked just a little bit faster, we would have been able to place in the top 200 out of ~800 which we thought was pretty impressive for competing as teenagers with no formal programming experience and a lot of things getting in the way. We're pretty sure that if we had had a little bit more time, or not had so many things conflicting with the contest, we would have been in the top 200.
A little timeline on our progress in ICFP:
8AM-Friday: Both of us are in our US History Regents. Neither of us will even read the problem until we come out.
11AM-Friday: We first read the problem, and realize how difficult this is going to be. Ryan goes home, ponders, and starts work. Gurtej has a Spanish final, so he mostly just ponders.
4PM-Friday: Both of us finally have time to work on the competition at home. We have figured out how to wire a circuit and the syntax of the circuit. We think the 19L in the sample circuit however, means "19 Lines". We also believe that the Xs (the external input/output streams) both have to be on the same gate, and that gate has to be on the bottom.
6PM-Friday: After messing around a lot, we realize we made a mistake earlier and figure out that the gate with the Xs can be anywhere on the circuit, but still think that the two Xs have to be on the same gate. We also realize the top and bottom labels are the locations of the Xs.
6 - 10 Friday: Many, many, circuits are made, lots of math and diagrams and truth tables. We document a bunch of different circuits to try to find patterns. We argue about what the wires initialize to, and what the external gate is. Both of us have different techniques for finding the truth table.
1PM Saturday: Both Gurtej and Ryan can work again, after swim practice and other things. We both get together at Gurtej's house. We spend a little bit working with circuits, then write a program to attempt to brute force the truth table. We don't realize that what we wrote won't actually work until about 2 hours later because we had been thinking of the special gate incorrectly. At this point, we decide to take a break: thank you, Modern Warfare! When we get back, we make more attempts at various stuff until we realize that we made a mistake and that the X's can be on different gates, and the problem suddenly becomes 20x easier. Within 15 minutes we know how the gates work, and develop the following truth table:
0,0=0,2
0,1=2,2
0,2=1,2
1,0=1,2
1,1=0,0
1,2=2,1
2,0=2,2
2,1=1,1
2,2=0,0
We were then able to get the input stream as follows 5-10m after we had the gates:
01202101210201202
The next step was building the program to simulate the circuit. Unfortunately we still were hazy on one issue: the backwards vs forwards facing wires. We thought at the time that loopback wires were ones that were required to wait one cycle before sending input because otherwise the result would be an infinite loop that would never stabilize. Therefore, we developed a recursive algorithm that was able to label these "lag" wires. At the end of the day, we have a semi-functional program that could identify the "lag" wires based our ideas. Ryan slept over at Gurtej's house so that we could continue work the next day.
Sunday Morning: We don't make much progress besides fixing a number of special case bugs in our program. We get a little frustrated and take another break. The next major discovery comes at about 2PM when Gurtej realizes that "lag" wires were actually just those that went from higher numbered gates to lower numbered gates, and could be accounted for by simply running through the gates in order of number, rather than using a crazy recursive function to make sure gates wait for the input from any non-lag wires before computing outputs. This made our program 10x simpler and we were able to get it working perfectly in an hour (see below for the C++ source code if you're interested). This allowed us to compute the key prefix:
11021210112101221
The next step was building a circuit that could output that key prefix. We had experience with working with normal circuits (Gurtej had significantly more than Ryan), so the first thing we tried to do was make modules that we could use to build a circuit. We came up with a number of modules but we were still missing a clock or a counter.
The next major breakthrough was a normalizer which could take the input stream and change it into a stream of 0s. Gurtej did this by taking a basic circuit which produced 220220220220... and adding a circuit to remove the 2s.
Input Normalizer:
0R:
0LX0#0L1R,
3R0R0#2R2L,
1R1L0#3L3R,
2L2R0#X1L:
3L
So we now could produce a constant stream of 0s. We also realize that we could convert that to a 2s stream pretty easily by tagging on a 0 - 2 converter (one of the modules we built earlier).
0 - 2 Converter:
0L:
X0L0#0RX:
0R
We then try to get a 1s stream, which was a little bit harder, but we eventually get it. The 1s stream is never actually needed so we don't have it typed out. Ryan comes up with a way to use the 1s stream to get a stream of 210 repeating, thus a mod3 counter. We also are able to create a mod7 counter which produces 2 outputs of different combinations modulo 7 given two streams of steady 0s as input. This way, we can easily produce 17 different 3 number combinations which are unique to which click the circuit was on, which we can then feed to a truth table circuit that will produce a certain output based on each input. This was certainly possible, but we realize it would be pretty hard. Additionally, we need something that could normalize any stream, not just the input stream, and eventually get this:
1s Eliminator:
0L:
X2L0#1R1L,
0R0L0#2R2L,
1R1L0#0RX:
2R
2s + 0s Stream Normalizer:
0R:
3LX0#1R1L,
0R0L0#2L2R,
1L1R0#0LX:
2R
Full 0-Normalizer:
0L:
X2L0#1R1L,
0R0L0#2R2L,
1R1L0#0R3R,
5L2R0#4R4L,
3R3L0#5L5R,
4L4R0#3LX:
5R
We basically only have to build a truth table circuit at this point, but we are really low on time.
After taking a shower, Ryan realizes that the same concept that we had used for the mod7 emitter could be used to create any input stream and be controlled very easily. Unfortunately, however, he does not explain it very well to Gurtej and goes to sleep before he can implement it himself, so it is not completed.
Monday Morning: Ryan wakes up at about 7:00 and is still really tired so he calls Gurtej and explains how the circuit has to be built so Gurtej could build it. By 7:30 Gurtej understands it completely and begins working on it. He is 2 numbers away from it working at the end, but fails to fix it because he is accidentally modifying the wrong gate. The circuit is then completed by Ryan about 15 minutes after the contest ended.
In the end, we had a lot of fun, and we look forward to it next year. We think that we actually preformed very well despite not quite finishing in time, and had we not made some of the mistakes that we did, we would have been in the top 1/4, which is very good, considering that we are still in high school, and that this is an international open competition.
Finished simulator source code:
#include
#include
#define PAUSE while(cin.get() != '\n') {}
#define LEFT 0
#define RIGHT 1
using namespace std;
int input(int side, int gate);
int inputnum, inputside;
ifstream factory("factory");
int main()
{
ofstream outputstream("output");
int inputarray[17], outputnum, outputside, colons = 0, nodes = 1;
int* wireval;
char in;
int truthtable[3][3] =
{
{2, 8, 5},
{5, 0, 7},
{8, 4, 0}
};
//Cache the inputstream
ifstream inputstream("input");
for(int i = 0; i <>> inputarray[i];
}
inputstream.close();
//Run through array and get stuff
factory.seekg(0);
factory >> inputnum;
factory >> in;
if(in == 'L')
{
inputside = LEFT;
}
else
{
inputside = RIGHT;
}
while(colons <>> in;
if(in == ':')
{
colons++;
}
if(in == ',')
{
nodes++;
}
}
factory >> outputnum;
factory >> in;
if(in == 'L')
{
outputside = LEFT;
}
else
{
outputside = RIGHT;
}
//Done running though factory...
//Create the variable sized arrays and initialize them
wireval = new int[nodes*2];
for(int i = 0; i < j =" 0;" i =" 0;" il =" input(LEFT," ir =" input(RIGHT," il ="=" out =" truthtable[inputarray[j]][wireval[ir]];" ir ="=" out =" truthtable[wireval[il]][inputarray[j]];" out =" truthtable[wireval[il]][wireval[ir]];" left ="=" right ="=" gate ="=" side ="=" nodes =" 0,">> num;
factory >> in;
factory >> in;
//Move it after the correct comma
while(nodes <>> in;
if(in == ',')
{
nodes++;
}
}
if(gate != inputnum || inputside != LEFT)
{
factory >> num;
}
factory >> in;
if(side == RIGHT)
{
factory >> num;
factory >> in;
}
if(in == 'L')
{
sidefinal = LEFT;
}
else
{
sidefinal = RIGHT;
}
return num*2+sidefinal;
}
