Skip to content

Instantly share code, notes, and snippets.

@ei-grad
Created December 17, 2012 10:22
Show Gist options
  • Save ei-grad/4317280 to your computer and use it in GitHub Desktop.
Save ei-grad/4317280 to your computer and use it in GitHub Desktop.
PHDays Quals 2012 - Misc 400
#!/usr/bin/env python2
# coding: utf-8
from collections import deque
import socket
import logging
import re
logging.basicConfig(level=logging.DEBUG)
class Found(Exception):
pass
class NotFound(Exception):
pass
DATA = []
def read_task(sock, chunks=None):
if chunks is None:
chunks = []
while True:
chunk = sock.recv(10000).decode('ascii')
DATA.append(chunk)
if chunk == '':
raise ValueError('Empty chunk recieved :-(')
chunks.append(chunk)
if re.match(
'.*Find a path between (.*) and (.*):',
''.join(chunks[-2:]).splitlines()[-1]
) is not None:
break
logging.debug('...')
logging.debug('labirinth readed (%d chunks)', len(chunks))
data = ''.join(chunks)
layers = [i.splitlines() for i in data.split('layer ')[1:]]
task = layers[-1].pop(-1)
start, finish = tuple(tuple(map(int, i.split(', ')))
for i in re.findall('[0-9]+, [0-9]+, [0-9]+', task))
logging.debug('task: %s', task)
logging.debug('start: %s', start)
logging.debug('finish: %s', finish)
layers = [[i[::2] for i in l[1:]] for l in layers]
return start, finish, layers
def read_file(fname):
labs = []
layer = []
ways = []
for line in open(fname).read().splitlines():
if line.startswith('layer (0,'):
layer = []
labs.append(layer)
if line[0] == '(':
ways.append([tuple(map(int, i.split(',')))
for i in re.findall('[0-9]+,[0-9]+,[0-9]+', line)])
if line.startswith('layer'):
layer.append([])
elif len(line) > 0 and (line[0] == '=' or line[0] == ' '):
res = line[::2].replace('=', u'█')
assert len(res) == 50
layer[-1].append(res)
return labs, ways
def ways_proj(ways):
import Image
for n, way in enumerate(ways):
img_x = Image.new('RGB', (50, 50))
img_y = Image.new('RGB', (50, 50))
img_z = Image.new('RGB', (50, 50))
for x, y, z in way:
img_x.putpixel((z, y), (255, 0, 0))
img_y.putpixel((z, x), (255, 0, 0))
img_z.putpixel((y, x), (255, 0, 0))
img_x.save('ways/%.2d-x.png' % n)
img_y.save('ways/%.2d-y.png' % n)
img_z.save('ways/%.2d-z.png' % n)
def draw_all(labs, ways):
import Image
def draw(layer, way):
img = Image.new('RGB', (50, 50))
for x in range(50):
for y in range(50):
if layer[x][y] == ' ':
img.putpixel((x, y), (255, 255, 255))
for x, y in way:
img.putpixel((x, y), (255, 0, 0))
return img
for n, (lab, way) in enumerate(zip(labs, ways)):
for m, (layer, w) in enumerate(zip(
[[''.join(lab[x][y][z] for z in range(50))
for y in range(50)] for x in range(50)],
[[(y, z) for x, y, z in way if x == i]
for i in range(50)]
)):
draw(layer, w).save('lab/%.2d-x-%.2d.png' % (n, m))
for m, (layer, w) in enumerate(zip(
[[''.join(lab[y][z][x] for z in range(50))
for y in range(50)] for x in range(50)],
[[(x, z) for x, y, z in way if y == i]
for i in range(50)]
)):
draw(layer, w).save('lab/%.2d-y-%.2d.png' % (n, m))
for m, (layer, w) in enumerate(zip(
[[''.join(lab[z][x][y] for z in range(50))
for y in range(50)] for x in range(50)],
[[(x, y) for x, y, z in way if z == i]
for i in range(50)]
)):
draw(layer, w).save('lab/%.2d-z-%.2d.png' % (n, m))
def solve(start, finish, layers):
path = {}
queue = deque()
queue.append(start)
def go(pos, x, y, z):
if (x, y, z) in path:
return
path[(x, y, z)] = pos
if (x, y, z) == finish:
raise Found()
if x < 0 or x >= 50 or y < 0 or y >= 50 or z < 0 or z >= 50:
logging.debug('bad coord: %s)', (x, y, z))
return
if layers[x][y][z] != ' ':
return
queue.append((x, y, z))
logging.debug('starting search...')
try:
while queue:
s = queue.popleft()
x, y, z = s
go(s, x - 1, y, z)
go(s, x + 1, y, z)
go(s, x, y - 1, z)
go(s, x, y + 1, z)
go(s, x, y, z - 1)
go(s, x, y, z + 1)
raise NotFound()
except Found:
logging.debug('found!')
if layers[finish[0]][finish[1]][finish[2]] == '=':
logging.debug('finish is a brick!')
pos = path[finish]
else:
pos = finish
reversed_path = []
while pos != start:
reversed_path.append(pos)
pos = path[pos]
if layers[start[0]][start[1]][start[2]] == '=':
logging.debug('start is a brick!')
else:
reversed_path.append(start)
result = ''.join('(%d,%d,%d)' % i for i in reversed(reversed_path))
logging.debug('result: %s', result)
return result + '\r\n'
if __name__ == "__main__":
sock = socket.socket()
sock.connect(('ctf.phdays.com', 1165))
logging.debug('connected')
user = sock.recv(100).decode('ascii').split()[-1].encode('ascii')
logging.debug('captcha: %s', user.decode('ascii'))
sock.send(user + b'\r\n')
ans = ''
while True:
logging.debug('reading task')
start, finish, layers = read_task(sock, [ans])
logging.debug('solving...')
result = solve(start, finish, layers)
DATA.append(result)
sock.send((result).encode('ascii'))
logging.debug('result sent')
ans = sock.recv(500).decode('ascii')
DATA.append(ans)
logging.debug('got answer: %s', ans)
if ans[:5] != 'layer':
print(ans)
break
with open('labirinth.data', 'w') as f:
f.write(''.join(DATA))
@ei-grad
Copy link
Author

ei-grad commented Dec 17, 2012

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment