[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')