[GitS 2015] Edgy – Programming 300 Writeup

I participated in Ghost in the Shellcode 2015 with the Plaid Parliament of Pwning. Here is my writeup for Edgy, a hard 300-point programming problem.

When you log in to Edgy, you are asked to solve a series of minefield-traversal puzzles, where you have to walk from the center of a minefield to an edge without hitting any mines. But, there’s a twist:

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

The pattern size is quite limited (between 1/3 and 1/5 of the maze size), so you have to take advantage of the repeating property to solve the puzzles.

My solution was to bruteforce the shift, which is the positional offset produced by a single repeat of the pattern (for example, the pattern WDD produces a shift of (-1, 2) – one unit west and two units down). For each possible shift value, I translate the entire maze repeatedly by the shift value, overlaying every possible translation onto the original grid. Then, finding a short path from the center to the first shift in the translated maze yields a repeated path in the original maze.

Here’s the code for that:

# edgy solution by Robert Xiao (@nneonneo)
# bfs with map compression and bit-operations for speed

import sys
from socket import *
TARGET = ('edgy.2015.ghostintheshellcode.com', 44440)

s = socket()
s.connect(TARGET)

def rduntil(*suffixes):
    out = ''
    while 1:
        try:
            x = s.recv(4096)
            if not x:
                raise EOFError()
            sys.stdout.write(x)
            out += x
        except timeout:
            if not out:
                continue
            break
        for suffix in suffixes:
            if out.endswith(suffix):
                break
        else:
            continue
        break
    return out

def pr(x):
    s.send(x + '\n')
    print "sending %s" % x

# Password prompt
rduntil('Password\n')
pr('EdgesAreFun')
graph = rduntil('moves\n')
def parse_graph(g):
    import re
    m = re.search(r'(--[\w\W]*--)\nYou have a maximum of (\d+) moves', g)
    g, moves = m.group(1), int(m.group(2))
    g = [s[1:-1] for s in g.split('\n')[1:-1]]

    w, h = len(g[0]), len(g)

    mines = [0] * h
    pos = None
    for i, row in enumerate(g):
        for j, col in enumerate(row):
            if col == 'x':
                mines[i] |= 1 << j
            elif col == '@':
                pos = (j, i)

    return w, h, pos, mines, moves

DIRECTIONS = {'A': (-1, 0),
             'W': (0, -1),
             'S': (0, 1),
             'D': (1, 0)}

def print_grid(w, h, x, y, mines):
    print '-' * (w+2)
    for yy in xrange(h):
        out = '|'
        for xx in xrange(w):
            if xx == x and yy == y:
                out += '@'
            elif mines[yy] & (1 << xx):
                out += 'x'
            else:
                out += ' '
        out += '|'
        print out
    print '-' * (w+2)

def shift_mines(w, h, dx, dy, mines):
    newmines = mines[:]
    if dx == 0 and dy == 0:
        raise Exception("you done goofed")
    elif dx == 0:
        n = h / abs(dy)
    elif dy == 0:
        n = w / abs(dx)
    else:
        n = min(w/abs(dx), h/abs(dy))

    shifted = mines[:]
    if dx < 0:
        def shiftx():
            shift = -dx
            for j in xrange(h):
                shifted[j] <<= shift
    else:
        def shiftx():
            shift = dx
            for j in xrange(w):
                shifted[j] >>= shift

    sy = 0
    mask = (1 << w) - 1
    if dy < 0:
        for i in xrange(1, n):
            shiftx()
            sy += -dy
            for y in xrange(h-sy):
                newmines[y+sy] |= shifted[y]
    else:
        for i in xrange(1, n):
            shiftx()
            sy += dy
            for y in xrange(h-sy):
                newmines[y] |= shifted[y+sy]

    return newmines

def find_path(sx, sy, tx, ty, mines, moves):
    ''' BFS from (x,y) to (tx,ty) '''
    from collections import deque
    q = deque()
    q.append((0, sx, sy))
    seen = set()
    parent = {}
    if mines[ty] & (1 << tx):
        return None
    while q and (tx, ty) not in seen:
        dist, x, y = q.popleft()
        if dist > moves:
            break
        if (x,y) in seen:
            continue
        seen.add((x, y))
        for d, (dx, dy) in DIRECTIONS.iteritems():
            xx, yy = x+dx, y+dy
            if 0 <= xx < w and 0 <= yy < h and not (mines[yy] & (1 << xx)) and (xx, yy) not in seen:
                q.append((dist+1, xx, yy))
                parent[(xx, yy)] = (d, x,y)

    if (tx, ty) in seen:
        path = ''
        while (tx, ty) in parent:
            d, tx, ty = parent[tx, ty]
            path = d + path
        return path
    return None

def shift_solver(w, h, x, y, mines, moves):
    for dx in xrange(-moves, moves+1):
        if moves > 100:
            print 'big progress:', dx
        for dy in xrange(-moves, moves+1):
            if abs(dx) + abs(dy) > moves or dx == dy == 0:
                continue
            xmines = shift_mines(w, h, dx, dy, mines)
            path = find_path(x, y, x+dx, y+dy, xmines, moves)
            if path:
                return path

def readall(size):
    out = []
    nbytes = 0
    while nbytes < size:
        res = s.recv(size - nbytes)
        if len(res) == 0:
            raise EOFError()
        nbytes += len(res)
        out.append(res)
    return ''.join(out)

import re
while 1:
    w, h, (x, y), mines, moves = parse_graph(graph)
    path = shift_solver(w, h, x, y, mines, moves)
    pr(path)
    graph = rduntil('moves\n', 'though\n')
    if graph.endswith('though\n'):
        size = int(re.findall(r'Sending (\d+) bytes', graph)[0])
        big = readall(size)
        open('big.z', 'wb').write(big)
        graph = big.decode('zlib') + rduntil('moves\n')