Skip to content

Instantly share code, notes, and snippets.

@ei-grad ei-grad/misc400.py
Created Dec 17, 2012

Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

commented Dec 17, 2012

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.