Tokyo Westerns MMA CTF - palindrome [ppc warmup]

palindrome.py

#!/usr/bin/env python
from pwn import *
context(log_level='debug')

def has_common_prefix(a, b):
    return a[:len(b)] == b[:len(a)]

def solve(prefix, postfix, words):
    pre_flat = ''.join(prefix)
    post_flat = ''.join(postfix)
    if not words:
        w = pre_flat + post_flat
        if w == w[::-1]:
            yield ' '.join(prefix + postfix)
    else:
        if len(pre_flat) <= len(post_flat):
            for i, word in enumerate(words):
                if has_common_prefix(pre_flat + word, post_flat[::-1]):
                    for x in solve(prefix + [word], postfix, words[:i] + words[i+1:]):
                        yield x
        else:
            for i, word in enumerate(words):
                if has_common_prefix(pre_flat, (word + post_flat)[::-1]):
                    for x in solve(prefix, [word] + postfix, words[:i] + words[i+1:]):
                        yield x

r = remote('ppc1.chal.ctf.westerns.tokyo', 31111)
for _ in range(30):
    r.recvuntil("\nInput: ")
    inp = r.recvline(False).split(" ")
    print(inp)
    if int(inp[0]) != len(inp) - 1:
        raise RuntimeError("?!")
    for sol in solve([], [], inp[1:]):
        r.recvuntil("Answer: ")
        r.sendline(sol)
        break
    else:
        raise RuntimeError("no sol?!")
r.interactive()