PHDays Quals 2012 - Misc 400

misc400.py

#!/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))

See write-up: http://darkbyte.ru/2012/61/phdays-quals-2012-writeup/#m400