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