MTGO

Question 3 - MTGO
Points: 200
Find the key!
Server: mtgo.2015.ghostintheshellcode.com:7463

Solution files:

$ ncat mtgo.2015.ghostintheshellcode.com 7463 -o solve.log --sh-exec ./solve.py
...
Huh. Guess this is broken.
All is known, flee at once.

They provided the source of the server program. It shuffles a deck of 20 cards, shows you the first 7 cards, and then you have guess the remaining 13.

The obvious flaw was seeding the RNG with the current time:

def get_tick():
    # gives you a string down to the millisecond*10
    return datetime.datetime.now().isoformat()[:-4]

The solution was really easy. Just locally brute-force seeds around the current time (including hours so that you account for different time zones; turns out the server was UTC) until you match on the first 7 cards. The only detail to keep track of was that each round shuffles the deck as it existed at the end of the previous round, not how it was initially.

def findseed(basedeck, testdeck, now):
    for hour in [0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5, -6, 6, -7, 7, -8, 8, -9, 9, -10, 10, -11, 11, -12, 12]:
	for centisec in range(-500, 500):
	    seed = (now + datetime.timedelta(hours=hour, seconds=centisec/100.)).isoformat()[:-4]
	    newdeck = shuffle(basedeck[:], seed)
	    if str(newdeck[:7]) == testdeck:
		return seed, newdeck

Originally the problem was unsolvable because of a bug in the server. It was comparing a string and a list:

if sock.recv(2048) == deck[7:20]:

Then they changed it to compare two strings:

if sock.recv(2048) == ','.join(deck[7:20]):

Edgy

Question 9 - Edgy
Points: 300
How well do you solve puzzles?
Server: edgy.2015.ghostintheshellcode.com:44440 Password: EdgesAreFun

Solution files:

$ ncat edgy.2015.ghostintheshellcode.com 44440 -o solve.log --sh-exec ./solve
Password
Welcome to Edgy, please solve the following puzzle with the WASD keys
The pattern provided will be repeated until the edge of the map is reached
 Example: If WDD is sent then it will repeat WDDWDDWDD... until an edge is reached

---------
|xxxx x |
|x  x x |
| x     |
| x @ xx|
|       |
|  xx   |
|x x x  |
---------
You have a maximum of 3 moves
dss
...
You have a maximum of 27 moves
sssasaaaaasassassddsds
Fine then. You've managed to solve my puzzles
One more, I promise
Sending 141547 bytes of zlib data. I still expect the answer in text though
zlib-compressed 1001×1001 puzzle
You have a maximum of 199 moves
ddsdssddwdddsdssddsssdsssdssdddsdsddsddssdssddddsdsdssssddwwwwdwdwdwddwdddwdwwddwwdddsddwddssdsdsdddwdwdddssssdssssdsddsssdddsssdssdsddwdwwwwdds
I guess you've earned it, the key is:
EdsgerDijkstraWasOnTheRightPath

I got this one solved about an hour after the contest ended.

The challenge was to write a solver for the above type of puzzle that is fast enough to finish before the contest is over. The puzzles get bigger and bigger as you go, from 7×7 in round 1 to 197×197 in round 112. Then in round 113 comes a zlib-compressed 1001×1001 puzzle. Your algorithm had to be better than necessary for the earlier rounds because of the last round. My final program did the first 112 rounds in under a minute but took over 10 minutes on the final round (at 400% CPU).

I started with the obvious thing, generate candidate strings w, a, s, d, ww, wa, ws, wd, aw, aa, as, ad, ... and simulate each one to see if it works. You can do a little optimization of this process: if you run into an obstacle during the first iteration through the pattern, then you can ignore all future patterns that have that prefix. For example, if you enter "sdsa", it gets repeated as many times as necessary:

sdsasdsasdsasdsasdsasdsasdsasdsasdsasdsa...

If you hit an obstacle on the first iteration,

   x
sdsasdsasdsasdsasdsasdsasdsasdsasdsasdsa...

Then you never need to look at any other pattern that begins with "sdsa", because they will always hit the same obstacle. The same is not true if it happens in a second or later iteration,

     x
sdsasdsasdsasdsasdsasdsasdsasdsasdsasdsa...

Because for example if "sdsasd" hits an obstacle, another prefix such as "sdsaa" may avoid it.

You can also apply the simple optimization of never immediately backtracking to the same square. Despite these attempts, my first program stalled for hours around round 80 or so. Eventually the limiting factor was memory pressure from the long list of pending paths to visit.

The key to solving it was the repetition of the input sequence. Think about reaching the edge in a sequence of same-sized (X, Y) steps. In the puzzle below, the way to win is with a repetition of (−2,−1) "awa" moves through the squares labeled 1, 2, 3.

 -----------
 |   x x   |
3|   xx xx |
 |2 x      |
 |x 1 x  x |
 | xx @   x|
 |   x  x  |
 |x       x|
 |x x xxxx |
 |xx x     |
 -----------

The crucial thing to realize is that the same sequence of relative moves has to get you from @ to 1, from 1 to 2, and from 2 to 3. In other words, you need to find a patch that works for all those sub-problems simultaneously. This fact actually makes the overall problem easier. I.e., if we have the three subproblems

....... ....... .......
.1 x  . .2 x  . .3    .
.x @  . .x 1 x. .  2 x.
. x  x. . xx  . .  x  .
....... ....... .......

we can combine them into one subproblem (with more obstacles) by ORing all the obstacles into one board. (This is what the accumulate function does.)

.......
.1 x  .
.x @ x.
. xx x.
.......

If you find a path that works when you include the obstacles from *all* of the subproblems, then you know the same path will work for all the subproblems; i.e., if you can find a path from @ to 1 in the immediately above diagram, that's the solution to the whole puzzle. The shortest-path computation is fast and uses much less memory (linear rather than exponential in board size).

For an example that doesn't work, look what happens if you try (2, −1) steps:

 -----------
 |   x x   |
 |   xx xx |3
 |  x     2|
 |x   x 1x |
 | xx @   x|
 |   x  x  |
 |x       x|
 |x x xxxx |
 |xx x     |
 -----------

The subproblems you have to solve are:

....... ....... .......
.  x 1. .    2. . x  3.
.x @  . .x 1x . .  2  .
. x  x. .    x. . x   .
....... ....... .......

And the combined subproblem with the OR of all obstacles, leaving no path between @ and 1:

.......
. xx 1.
.x @x .
. x  x.
.......

So the only thing remaining is to find a fixed-size step size that works. For that I just used brute force: does there exist a sequence of (1, 0) steps that reaches the edge? a sequence of (1, 0) steps? ... a sequence of (1, 2) steps? ... for all step sizes that you can reach within the puzzle-imposed move limit.

Ghost in the Shellcode 2015 writeups

MTGO

Edgy