Note: This post was written a few weeks ago but kept off the internet until all schools finished the challenge.
Remember my post from a while back about the Sudoku challenge and my subsequent trip to San Francisco? Well, the event was such a success that SignalFire is organizing it again next year. The event is invite-only and the qualifying round happened this weekend. Basically, they provide a coding challenge that presents both intellectual and coding difficulties and the participants try to solve it in 4 hours.
Anyways, if you read my blog about the last contest, you’ll recall that I wrote a solution that completely ignored the given input and printed out a correct Sudoku every time, which earned me third place on the leaderboard and a free trip to a sick hackathon in San Francisco.
Since that approach worked so well for me last time, I decided to spend my time finding ways to break the system without actually solving the challenge. I was working in Halligan with six or eight other guys. We chatted about the problem for a while, discussing algorithms that could be used to solve it. The challenge centered around an art thief who is trying to get through a room full of sensors. Each sensor has a set of coordinates and a circular radius. He wants to turn off as few sensors as possible so that there’s a clear path from one side of the room to the other.
We determined that the best way to actually solve the problem would be to create a clustering algorithm to figure out which circles were touching, then check if there was a cluster that touched both walls of the room. If so, there would be no way to get across, so at least one circle would have to be removed. A breadth-first search would try removing each circle individually and check for a path with each one. Then it would try all pairs, all triplets, and so on until a path was determined.
But who wants to code that?
First thing I did was to grab a random number generator that would return a number between 0 and the number of sensors in a room. Easy! But then I realized that the distribution wouldn’t necessarily be even within that range. That is, you don’t want to choose an entirely random number because it seems more likely that you’ll only have to remove two or three circles to clear a path. So I weighted the number generator so that it was more likely to choose a number between 0 and n/2 than n/2 and n.
I submitted that a few times with passable results. They run a bunch of test cases on the submitted solutions and use some unidentified scoring rubric to assign points to each submission. Around this point, I realized that I had no idea what their test cases looked like, and so my probability distributions could be way off. I could keep trying random distributions until I got better results… or I could try and look at the test cases they were using.
I decided it was time to call in reinforcements. My friends Tony and Michael were also working on the challenge. I explained my idea: Python is a programming language that (among other cool things) has a really nice library to write scripts to send emails. So we write a program that reads in the data, emails it to Tony, and then spits out some made-up solution. Then we open the email, determine the correct answers, and submit a second solution that has them hardcoded in.
Pretty quickly, they had it up and running on our personal computers. Unfortunately, we then discovered that the machines running the contests were probably virtual servers somewhere, and weren’t connected to the internet, so no luck sending emails.
Disappointed but not ready to give up, Michael suggested we start playing around with other cool python features, like the one that lets you run bash commands. This actually gave us the ability to see all the files on the box that was running the contest, which was interesting. Michael kept playing around with it, but despite his best efforts, could neither locate the test files nor destroy the entire machine.
So that’s what I did this weekend. Hung out in the comp sci building and tried to break the system. #H4CK3RZ