ICFP 2012: Lambda Mining

This year's competition struck a familiar note -- elements on a grid, being updated every timestep. The premise of the problem was a worldwide shortage of "Lambdas" due to increased use of functional programming languages. The input was a map, consisting of earth, rocks, lambdas, etc. Your character (a mining robot) started in one location of the map, and the Lambda Lift (your target) started in another location. Your objective was to output a series of movements to collect as many Lambdas as possible, avoid rocks and other hazards, and ultimately arrive at the lambda lift for maximal points. For more details about the problem statement, see icfpcontest.org.

As a team of 5 MIT rising sophomores, we put together a solution revolving around a genetic algorithm. Below is the README file describing our algorithm which we attached with our solution:


Team IDKJava - 96121980
* Gurtej Kanwar
* Anthony Lu
* Will Oursler
* Gary Wang
* Tim Yang

Summary:
Looking at this kind of problem, a human would most likely break down the map into various smaller situations he knew how to solve, or which were easy to solve. Designing a program to follow these principles would have been much more difficult, especially as the new types of materials and effects were discovered throughout the competition. As such, we decided to go with a more general solution -- our idea was that by avoiding any casework at all, our code would be simpler and easier to extend as changes arose. By making use of randomness and many iterations in the form of a genetic algorithm, we were able to to do just that.

The genetic algorithm:
Our genetic algorithm was defined generally, to allow for easy variation. It operated on "Creatures", which could be anything we chose them to be. The class GeneticAlgorithm accepted three functions on these creatures -- getRandomCreature, breed, and fitness. The first, getRandomCreature, generated a random creature, which was used to create the initial "population". Breed took two creatures and produced another creature which was effectively the average of the two (with a healthy dose of randomness, to allow the population to vary). Fitness was a scoring function, which was then used in selecting which creatures to breed and advance to the next generation. By iterating generations of selective breeding, the "creatures" progressively get higher and higher scores, which corresponds to a higher final score.
When deciding the creature, we had a few options. Ultimately, we went with defining a creature as a sequence of waypoints for the robot to hit on the map. This way affecting earlier waypoints wouldn't change the location of later waypoints (as it would have if we had simply used instruction sequences as creatures). Our breeding function averaged waypoints, adding in randomness. Our fitness function made use of an A* pathfinding algorithm to determine the optimal path between waypoints, and the fitness was the score at the end of traversing all waypoints.
It's worth noting that the environment was by no means static, with rocks falling, beards growing, water rising, etc. Because of this, we had to define our A* system to operate on Nodes which were actually a series of MineState objects. Connections between nodes were commands to the robot. Of course, since movement was still grid-based, we were able to use Euclidean distance as a reasonably effective heuristic. The elegance of this system was that our MineState class could then handle all special cases, including ones added as the contest progressed, and our actual algorithm would not be affected at all.

Conclusion:
Though our algorithm had a lot of potential, implementing it using C++ (in order to get the speed we needed) instead of a more functional language was painfully slow. In the end, we ran short on time and weren't able to add in optimizations such as representing the MineState in memory as a series of diffs. Our genetic algorithm ran fairly well on smaller maps, but anything that got remotely larger started to eat up a lot of memory, as each MineState stored it's own copy of the grid, and A* created many copies of MineState.

IPSC 2012 Results

Overall

IPSC this year had an interesting mix of normal algorithm programs and some more unique ones. A breakdown of some of the more interesting problem is given below. Overall, we did much better than last year, finishing in 213th place out of 644 teams who scored points, with a final total of 11 points (7 easy problems and 2 hard ones). With IPSC out of the way, we can set our eyes on ICFP, our all-time favorite competition, but more on that at a later date. Without further ado, our breakdown of the problems:

Problems

A - Abundance of Sweets

As usual, Problem A was not much of a challenge. The easy solution required simply iterating through a matrix and outputting the number of 'o's found. The harder challenge required checking the surrounding values of all the 'o's, but could still be easily done with a brute force method.

B - (blank)

This was one of the more interesting problems of the challenge this year. Given no problem statement, we moved on from this challenge, though in hindsight we should have attacked this problem earlier on. When we did get around to it, we tried a random submission and immediately saw how this problem was laid out when we received a hint in response. Following the hints, we eventually understood what the solution was -- a sequence of 6 or more numbers forming a sequence such that each number was a multiple of the one before, and all of them totaled 123456789. Eventually we managed to use the prime factorization and some educated guessing to come up with a solution that worked. The better solution was much simpler -- just take the binary representation to get a sequence of powers of 2.

The hard counterpart for this problem used a similar hint upon submission method, though required more submissions to move towards the answer. We made good progress on this solution, but unfortunately ran out of time just as we were only 1 or 2 tries away from completion.

C - Card game

This problem dealt with probability, not one of our strong points. After a few wrong tries, we were able to get the first solution, but decided to work on other problems instead of attempting the hard part.

D - Data mania

This problem was more of an aggregate of problems, consisting of several data analysis problems on last year's IPSC user statistics. Each problem in the easy set was relatively easy, and we arrived at an answer, but were judged incorrectly. After looking through it, we were unable to find our mistake, so we moved on.

E - Evil matching

We looked over evil matching some, but didn't come up with any good methods to approach it, and ultimately weren't able to code any solutions.

F - Fair coin toss

This was again a problem focusing more on probability. After thinking through the problem, we came to the correct conclusion for the easy problem that only having a 1/2 probability coin would do it.

For the hard problem it took some thinking through, but it wasn't too hard to come up with a formula for the number of subsets of coins which had at least one probability 1/2 coin in it.

G - Gems in the maze

The easy sub-problem for this problem was easily brute forced. Simply looping through all initial chambers and following the paths was enough to pass.

For the hard test case, we initially though that dynamic programming was the solution, but realized that the possible looping made this impractical. After some thought, we realized that all chamber sequences were some sequence followed by some loop (either of which could be of zero length). In addition, once you found this sequence, all chambers on this sequence were determined, thus giving a linear time algorithm. Implementing this bug-free was somewhat of a challenge, and we ultimately ran out of time on this problem.

H - Harvesting potatoes

For the easy case, we realized that casework would get the job done. Unfortunately as we coded the solution, more and more edge cases came to mind, and the code became complicated quickly. Looking at the scores, we noticed that none of the top teams had finished the problem, so we moved on. At the end we didn't have enough time, and didn't end up finishing either part of the problem.

I - Invert the you-know-what

This was again a fun problem consisting of several username:password hashes which you were tasked with the challenge of decrypting. Luckily the easy subproblem only required decrypting one of the passwords, and passing them through a simple MD5 decrypter got us several passwords. We were stuck for a little bit because the salt prepended to the password threw us off. When we realized to remove the salt then submit we got the easy case.

We weren't sure how to tackle the hard sub-problem, so we moved on.

J - Jukebox

This problem was also a very unique one. As input, you were given MP3 files and the same files in text format, which described waveforms. Unfortunately, we realized analyzing these would require a Fast Fourier Transform, so instead we decided to listen to the pieces and simply transcribe them by ear (at least for the easy case). After a few mistakes, we got a correct submission.

For the hard sub-problem this was clearly not possible, and we didn't have time to figure out writing a Fast Fourier Transform, so we moved on.

K - Keys and locks

In hindsight this problem was very tractable, but we didn't have an good ideas at first and so didn't attempt this problem for very long.

L - Light in a room

After reading this problem, we knew it would take a while and moved on to easier problems.

M - Matrix nightmare

After reading through the wise words at the beginning of the problem statement and quickly scanning through, we again realized this was beyond our level and moved on.

IPSC 2012 is coming up!

The annual Internet Problem Solving Contest, a mathematics and programming competition open to all participants from around the world, is coming up this weekend. We competed in IPSC last year, and unfortunately didn't do as well as we would have liked. This year, Ryan and I are back, with vengeance.

IPSC accepts teams of up to three, so we asked some of our friends at MIT if they wanted to participate. This year we will be participating with Timothy Yang, a rising sophomore at MIT. Tim is also an EECS major, making that all three of us. We're not quite as math-heavy as we might have wanted, but we're still hopeful that something of our first year at MIT will carry over into the competition.

We'll just have to wait until the competition to find out how well we do!

Tej Kanwar
IDKJava

Clower Stats

Our partner in crime for ICFP this year, Mr. Michael Clawar, recently established his new website for the various statistically-oriented projects that he does in his free time (he's crazy). I just thought we'd throw up a link if those of you as crazy as him want to check it out. It's really pretty cool actually.

Here ya go: www.clowerstats.com

ICFP 2011: Results

After many hours of hard work, we finally got the results ... and took place 192 out of 199! Though this may sound terrible, and it is, it is better than last year, in which we tied for last with 0 points because the competition was so devilishly hard. This year, we got a total of 68 points. Considering a win was worth 6 points, and a tie was pretty rare, this probably means we won 11 games and tied 2. There was a total of 198 games, so that's a pretty miserable win/loss ratio. In retrospect, I think our biggest problem was that we targeted the most used slots in hope of breaking them, but we didn't really kill slots fast enough. If we had the time we should have made use of some of the higher functions, especially zombie. Unfortunately our schedules really conflicted with ICFP this year, so we weren't really able to all get together and get a solid few days of work done on it. Overall, I'm pretty happy with the results, because there are some pretty experienced programmers in this competition, and to even have placed above any teams at all is a pretty good accomplishment.

ICFP 2011

It's been a few days since ICFP 2011 and we've finally had a chance to cool off and relax, so I thought I'd throw a blog post up about what we actually did.

Before I go into the details of the competition, allow me to introduce our team. We had four members in total. Three of us are prefrosh at MIT: Ryan Cheu, Kevin King, and myself Gurtej Kanwar. The three of us also happen to be the core members of IDKJava. Our fourth member, a talented statistician named Michael Clawar, is a rising senior at the high school Ryan and I attend. Naturally we were wary, because he aspires to attend our rival, Ha'vard. He was, however, a valuable member of our team, and we grudgingly came to accept his choice. With this formidable team assembled, we were ready to dominate.

We started off at around 8 PM, when the contest opened in our local timezone. We read the problem and immediately felt a little lost. None of us had any experience with Lambda Calculus or SKI combinators, and so we spent much of our precious time figuring out how the problem worked. In addition, we immediately had issues with the fact that we could not all meet up for the majority of this competition, because Kevin lives several hours away from the rest of us, and Michael was out of town for the majority of the competition. As a result we ended up using a lot of Skype, AIM, and Facebook to figure things out.

After finally getting a grasp of the problem statement about a day in, Ryan and I got together and we started work on simulating the situation, so that our "player" would have some idea of what was going on to make AI decisions. Ryan and I met up Friday evening, and we got cracking. We realized that the best way to code this would be to create some of our own data structures, such as a struct Slot and a class Card. One question we ran into was how to represent non-basic functions, such as functions that had been returned by S or attack. We decided to create individual classes for each of the different "stages" in these cards. For example with S, there is the main S card, and then two intermediate stages. Thus we had classes called S1, S2, and S3 to represent this. These classes could then call on the display functions of the arguments they had been passed to display themselves in proper parenthesized form.

Once we had our basic simulation set up, there was about a day's worth of debugging to go through, and special cases to add in. In particular, the zero card threw us off, because originally we thought there was a difference between it and the number 0. In the end, however, we realized that zero and 0 were the same thing, and then zero could not be called as a function as we originally thought. In addition we had to work out the zombie loop and add in another function to deal with the fact that some cards changed how they worked when being called by the zombie loop.

This took up the majority of our time on Saturday, leaving us just Sunday to get some strategy done. On Sunday I set up our program with the framework for creating an AI: a system for adding moves to a queue to be executed (actually a stringstream), and a few utilities, such as clearing slots, applying an SKI combinator, and applying a slot to another slot (given that the first slot was a function). I then unfortunately had to go to work, leaving Ryan to develop our entire strategy for all of Sunday. When I came back with two hours left in the competition, I found an elegant system, in which our program would constantly change which slots it would use, and constantly use help to add vitality and then use that extra vitality to attack the slots most used by the opponent program. Unfortunately, there were several bugs with our system, and it did not work as expected or segfaulted repeatedly, so we spent much of our remaining two hours trying to work out these bugs. With an outside pair of eyes, thankfully we managed to work them all out and with only a few minutes left to go had a working program. Because we were short I did not get a chance to test using the provided utility to see if our program actually worked, but we managed to get everything in on time, and we'll see how we did soon!

I'm pretty proud of how much we accomplished with such sub-optimal timings and conditions. If we had had all four days free and all of us could meet up, I believe we would have been in much better shape, but the fact that we actually submitted a working program at all is an improvement over last year, in which we were close but just missed the deadline on getting in something that worked. We did a great job!

Tegra 2 Issues

Hi Everyone,

We've been fighting a bug recently on the Atrix relating to our textures not working correctly in our development version. We've tracked the problem down to glTexSubImage2D in android native. It appears that the width of the area which you wish to change must be a power of 2. The height however does not need to be a power of 2. This behavior has not been observed on any other device to our knowledge. Hope this helps anyone who has similar issues!

-IDKJava Team

EDIT: We got it working on the first try! After all we've been through with this issue I think we deserved it.

The Hint

Apparently our program is trying to give us a hint:



EDIT: We found this later; still not quite sure what it's trying to tell us:

MIT!

We both got accepted into MIT as of last night! The wait was long, but it's over now. Hopefully we will have more time to get some work done on The Elements and the UAV now.

Happy holidays everyone!!

DestinyCloudFist Risk

Because of the lack of a good Risk game for Android, Ryan and I decided to take it upon ourselves to hack out a functional one ASAP. We started about 5 days ago and so far have a skeleton of the Activities set up and are just about getting into the game-play itself. Since we've never dealt with AI before, that part may be a bit of a challenge, but we're setting Feb 1 as our deadline for non-AI gameplay.

We decided to call our Risk game DestinyCloudFist in reference to a hilariously-named Starcraft strategy. Our Google Code page can be found at http://code.google.com/p/destinycloudfist/.

As always, if you have any advice, admonitions, compliments or threats, email them to idkjava@gmail.com!

Progress

So we'd thought we'd update you on what we've been doing so far. We've been fairly busy, but the UAV has made progress; we've been putting it together and working a bit on the programming side. Here are some pictures from our work.

Marking the position for gluing airfoil pieces
Skeleton of the UAV put together, no electronics in yet.

Attempting to test our motor and propeller, hoping for lack of explosion. Later found that brushless motors don't connect like normal motors. We wasted an hour here.

Cool picture of the wing

College stuff done!

Hi Everyone,

Gurtej and I are finally done with our college applications! This means that pretty soon we should be pumping out updates again. Currently there's a coding competition called CodeChef that Gurtej and I(Ryan) are participating in so it might be about a week before the first update comes out, but we promise it is coming!

On another topic, if you happen to be a college admissions officer looking for the site that Gurtej and I have been working on, the website is up at 74.70.156.22:8080 (ISP doesn't let incoming port 80 through). The source code of this page is up now as well at 74.70.156.22:8080/www.tar.gz! All of the pages, including PHP code are up, with the only change being removing the password/user names in PHP.

College Applications almost done!

Hi Everyone,

Sorry for the lack of updates for such a long time. Gurtej and I(Ryan) have been pretty busy the last few months with college applications and schoolwork. Starting soon, we will be returning to all of our Android programming and new updates will be flowing out!

Money for a Server

We plan to add a save feature to The Elements soon. This would hopefully allow everyone to upload something like 3 saves for others to browse and load. However, currently our server is just a patched together laptop sitting in my (Gurtej's) basement. It is neither a dedicated server nor fast. Ideally we would like to buy a computer that we can use as a dedicated server. Unfortunately, we lack the funds. Thus, we are calling upon you to buy the Falling Sandpaper app (think of it as a donate version of our app with a free gift!) and donate through the button here in our blog to raise the money we need. Once we get enough money together, hopefully we can find a decent server and buy it, or at least rent space in one. Please, help us out so that we can continue to improve this app!

Falling Sand Live Wallpaper

A few of you may have noticed that recently, we released a second application to the market called "Falling Sand Live Wallpaper." It is essentially a live wallpaper of our application, "The Elements."

There are a few known bugs.

-It does not work on the official 2.2 update for the Nexus One.

-When tested on a custom 2.2 Nexus One ROM, it caused slowdown on the phone. This did not happen on 2.1 Droid.

We hope you will purchase this app to support us!

-IDKJava Team

Update 4.0 / 4.1

Recently, we released two updates to our application, 4.00 and 4.10.

4.00 Added custom elements, fixed an explosion bug ( which in turn caused another bug), and added mud.

4.10 Was primarily bug fixes, the specifics of which can be found on the Google Code Site.

-IDKJava Team

Open Source!

Both Gurtej and I are huge opensource supporters. We both use Ubuntu Linux as our main OS on our computer, and use Android on our phones. We proud to say that as of yesterday, our project, The Elements, has been opensourced! You can now find the project here, on Google Code. This means that now everyone can see and use the code we have written for The Elements. The only thing we ask is that if you port it to a closed system (iPhone, Windows), please make the application a paid app. On open systems (Android, Linux), please make it a free app. Thanks!

If you want to contribute, there are a few things that we need. First off, if someone who is knowledgeable in C/Java wants to help make our code neater and more organized we definitely need that. There are a number of tasks that I have in mind if any other programmers want to help as well. If you are skilled in art, we need someone to make a better icon, buttons for the main menu, an eraser button for the UI, and a better background for loading screen and main page.

If you're not skilled in programming or art, we also have a few things there as well. The most useful thing is reporting bugs, and testing. When you report bugs, try to post the exact steps to follow to reproduce the bug if possible. Bugs with vague descriptions such as: "It crashes sometimes when C4 is used" are not very helpful since they are hard to reproduce and determine exactly what is the problem. A better bug report would be: "When I place C4 on the bottom left edge of the screen in zoomed mode, and then place magma along the upper left edge, when the two react and the C4 explodes, the game crashes without a force close button." That allows us to look into the problem and place debug calls to find out what is happening.

Another thing we need is people to write out information for our game. We need people to fill the wiki, make a better help page for the game, and help translate the game. Anything else you can think of to help would be great as well!

-IDKJava Team

UAV: Update 1

We've made big plans again! This time we're going to be working on building a UAV (Unmanned Air Vehicle) over the summer, desgined to drop water balloons on pre-programmed GPS coordinates. So far, we have ordered several servos, the Arduino Duemilanove board, brushless motors, and lots of different propellers. We're pouring the meager profits we made from ads in our Elements app into buying these parts, though we're still in the red unfortunately!

We are currently in the design stage. We have so far decided to use a balsa frame with cellophane covering (we'll see how that goes and maybe try something else). We're going to order the balsa pieces precut, which means we had to design the entire plane first. To achieve this end, we are using SketchUp 7. Here is one of our beautiful preliminary designs:

As you can see, the nose still needs to be designed. In addition, we need to finish modelling the ailerons and put them into this file. We will continue to document our progress, with as many videos and pictures as possible, and maybe at the end we can write up a tutorial for how we did it (assuming we actually succeed!)

ICFP 2010

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 task description.

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;
}

Code Jam!

In other news: both of us competed in Google's Code Jam 2010. Code Jam is a timed programming competition, in which you are given problems and have to write code quickly to solve them. Both of us got past the Qualification Round, but we struggled in Round 1 because it was significantly shorter and we both had other events that cut into it. Not to mention, in the last sub-round, lack of sleep managed to knock out Ryan, but Gurtej progressed to the next round.

If you want to see our placements, you can view the our scores in all the rounds. Gurtej registered as "looterguf" and Ryan registered as "choochoo".

Unfortunately, neither of us would have been able to compete in the next round anyways because it conflicts with our SATs. Our next competition is going to be the International Problem Solving Competition on June 6 for which we will be a team under the name IDKJava. In the meantime, we will continue our development of our next Android app, and hopefully release more elements.