So my friend Vincent referred me to this quaint little convention called
DEFCON
and more importantly the capture-the-flag competition they were hosting, colorfully titled the Legitimate Business Syndicate Casualty Trauma Festival (their domain was LegitBS.net) . Figured it would be nice, given that it's a hacking competition and I haven't done that in a while, so I joined under the banner SSHv3 with Vincent and two states universities in Florida.
It was relatively nice starting -- Vincent let me know that he had a stash of junk food and coffee if needed (a warning which I unwisely waved off) -- and then it started becoming terrible when the first question opened up.
Nigel was invited to it with us but he stayed home. We set up a webcam session for him to participate in proxy. But after glancing at the first question he effectively gave up and began using the webcam session to broadcast 4th grade video projects and to overlay his face with a picture of a cat.
After three hours no one had solved a thing yet and the organizers decided to open up another question while simultaneously insulting our heritage. We figured out pretty quickly that it was a sliding puzzle and managed to come up with some innovative ideas. My approach was to generate every possible configuration (9! / 2 = 181440 possibilities) and their solutions, store them on disk, and then just do a lookup when it was necessary (the puzzle was timed). Eventually, when it was taking too long (this was around 2 AM) we collectively decided to throw out my approach and do something sensible. I offered to modify it to accept any state already found as a goal state and just append the solution, which worked a bit better but not enough.
The program had stored nearly 3000 solutions by now and it was solving them relatively quickly but there were a few that were troublesome. We'd both gone through nearly two cups of coffee around now. Vincent eventually started looking up his own algorithms when it became clear I was too stubborn to accept that my horribly inefficient bruteforce method was awful.
He found a Java program that did it relatively fast and we began hacking through the code for it.
Around this time, he pointed out that the sun was coming up.
I was ready to kill something by this point. The scoreboard's theme -- a flashy, pink, hacking syndicate posing as a Japanese business -- grew from "mildly humorous" to "absolutely mocking." I downed another coffee.
We were both completely dead, and I was relegated to running the code every time it failed in the hopes that we'd get lucky with really easy slider configurations, when suddenly a line that wasn't a slider puzzle appeared at the bottom of the window:
"The key is enemas on parade."
After 10 hours we have contributed our first and only point to the team.
The people at the universities fared better; they managed a nice 17 points by the end of it (plus our one makes 18) and actually got some sleep.
It was not bad.
My guess about what happened is based on several assumptions:
ReplyDelete1. The generator was made puzzles by starting with a sorted state (1 2 3 , 4 5 6 , 7 8 -) and then making a random sequence of moves from there. This would generate a solvable configuration.
2. If the game finds a slider that's in the correct order, it spits out the key.
If these assertions are true, then it's likely that you got to a configuration where the randomly generated moves made a puzzle that was already in order, that is, they slid blocks around, but got back to the initial configuration. In that case, no other work is necessary.
I worked until about 1:30 on a solution, went to bed, got up, and fixed my solution, but by that time, you guys had solved the problem. If you want, I can discuss my solution at a later meeting. The strategies involved might be helpful.
-- Hachinijuku