Qiwi Infosec CTF 2016: PPC 400

,

sqliteのmaze.dbから迷路を読み込んで解く。$50 \times 50$なので余裕だが、flagは$695$文字と大きくて驚く。

#!/usr/bin/env python3

# read maze.db
import sqlite3
## sqlite> .schema
## CREATE TABLE start (id integer);
## CREATE TABLE finish (id integer);
## CREATE TABLE points
##                      (id integer primary key,
##                       x integer, y integer, status varchar(10), value varchar(1));
with sqlite3.connect('maze.db') as conn:
    row, = conn.execute('select id from start')
    start, = row
    row, = conn.execute('select id from finish')
    finish, = row
    points = [ [ None for _ in range(50) ] for _ in range(50) ]
    for id_, x, y, status, value in conn.execute('select id, x, y, status, value from points'):
        assert status in [ 'wall', 'gate' ]
        points[y][x] = { 'status': status, 'value': value }
        if id_ == start:
            start = (y, x)
        elif id_ == finish:
            finish = (y, x)

# debug draw
for y in range(50):
    for x in range(50):
        c = points[y][x]['value']
        if points[y][x]['status'] == 'wall':
            c = '\033[47m' + c + '\033[0m'
        print(c, end='')
    print()

# dijkstra
from heapq import heappush, heappop
heap = []
dist = [ [ None for _ in range(50) ] for _ in range(50) ]
y, x = start
value = points[y][x]['value']
heappush(heap, (len(value), y, x, value))
dist[y][x] = points[y][x]['value']
while heap:
    _, y, x, value = heappop(heap)
    for dy, dx in [ (-1, 0), (1, 0), (0, 1), (0, -1) ]:
        ny = y + dy
        nx = x + dx
        if 0 <= ny < 50 and 0 <= nx < 50:
            if points[ny][nx]['status'] == 'gate' and dist[ny][nx] is None:
                nvalue = value + points[ny][nx]['value']
                dist[ny][nx] = nvalue
                heappush(heap, (len(nvalue), ny, nx, nvalue))
y, x = finish
print(dist[y][x])

flag:

154C82F36487A9157315AADFDDED1BB83ECD98E49EADAFEB03DB563A94E0851478C408CFD6B0BB42B030F61A82E655B7FCA0E1FA68DF676758DC60FBFD1016F0EB8E7A2B5170A157497EF711E4009653BC9B20726C98B6561EFBE316AC2AB2DCBE56494F05B44ED3EB62DA4109BEEC2537266FEDE44ACB12A17CA8C8A5BA9E1A4D24ACAD900FFBD228AC187B9024BEDC941D137EA3A92F9F8506740CD8C62DBEDB9990F3E0259434D9FCF070FEC9E60C5697BABA83A4E59EB4C3F0E7AFD44B1B8D9D93933962B27237560B5F8F7D19904D790842FA596FBB52B2A3F7EE15B7F589D28A6F20F747615E7ED135E17AFE8FE073B6606F5C893D40CB78B635AA5FE4E0EE10C572D5E7AECEAF743953D05F78BBC10A9BB3D53B0011AE5F269C806E5F9E6026C954A0CDF9C797953360602B96FC06324C3160701505C24597F6F7C77D5B76CBE25CD2B706A41DA324A1B79CFC4BA8B11F800593514D27754