Internetwache CTF 2016 - Code90/Dark Forest

Description: Someone pre-ordered a forest and now I'm lost in it. There are a lot of binary trees in front and behind of me. Some are smaller or equal-sized than others. Can you help me to invert the path and find out of the forest?

Service: 188.166.133.53:11491

So, something to do with binary trees, inversion...

Example:

$ nc 188.166.133.53 11491
I'm lost in a forest. Can you invert the path?
Level 1.: [7, 12]
[12, 7]
Nope, that's not the right solution. Try again later!

Inverting a binary tree sounds simple enough: https://leetcode.com/problems/invert-binary-tree/

Decide to do it myself without looking up the solution for max credibility.

class Node:
  # my first tree class
  def __init__(self, value):
       self.value = value
       self.left = None
       self.right = None

  def invert(root):
    if root is None:
        return None

    inverted = Node(root.value)

    inverted.left = invert(root.right)
    inverted.right = invert(root.left)
    return inverted

Take that Max!

Not sure how this array ([7, 12]) represents a binary tree. Few ideas pop up on google: https://stackoverflow.com/questions/8256222/binary-tree-represented-using-array.
But they're often a bit ambiguous, several possible trees represented by the same array.

Oh well, level 1 is just two numbers. How many combos can there be?

$ nc 188.166.133.53 11491
I'm lost in a forest. Can you invert the path?
Level 1.: [5, 9]
[5, 9]
Yay, that's right!
Level 2.: [7, 3, 19, 23]
[23, 19, 3, 7]
Nope, that's not the right solution. Try again later!

So we don't just reverse the array :o

Example:
$ nc 188.166.133.53 11491
I'm lost in a forest. Can you invert the path?
Level 1.: [7, 12]
[7, 12]
Yay, that's right!
Level 2.: [7, 3, 19, 23]
[7, 3, 19, 23]
Nope, that's not the right solution. Try again later!

Again, small number of possible solutions for each question. I wanted to find some right answers so I could figure out the pattern.

whitelist = re.compile('^\[[0-9, ]*]$')
while True:
        level = receive()
        array = level.split(": ")[1]
        if whitelist.match(array):
            # anti-rootkit v2
            array = eval(array)
        else:
            quit()  # u've been hakt

        send(shuffle(array))

Got a bunch of 'correct' solutions this way:

[11,11,18,27] -> [11,18,27,11]
[11,2,35,30] -> [11,35,30,2]
[33,21,32,30] -> [33,21,32,30]

Draw these trees out assuming binary search trees, and you can hopefully see that the representation here is 'print current node, print left subtree, print right subtree', also known as 'preorder', also known as the second word in the challenge description. :(.

Sooo, we're given the pre-ordered representation of a binary search tree. Let's knock something up to build up the tree from that representation, invert it, then send back the preorder of that tree... phew.

class Node:
    # my first tree class
    def __init__(self, value):
         self.value = value
         self.left = None
         self.right = None


def insert_in_tree(root, value):
    new_node = Node(value)
    current = root
    while True:
        if value <= current.value:
            if current.left is None:
                current.left = new_node
                break
            current = current.left
        else:
            if current.right is None:
                current.right = new_node
                break
            current = current.right
    return root


def array_to_tree(values):
    root = Node(values[0])

    for value in values[1:]:
        root = insert_in_tree(root, value)

    return root


def invert(root):
    if root is None:
        return None

    inverted = Node(root.value)

    inverted.left = invert(root.right)
    inverted.right = invert(root.left)
    return inverted


def preorder(root):
    if root is None:
        return []

    # current, left, right
    return [root.value] + preorder(root.left) + preorder(root.right)


def solve():
    whitelist = re.compile('^\[[0-9, ]*]$')

    receive()

    while True:
        level = receive()
        array = level.split(": ")[1]
        if whitelist.match(array):
            # anti-rootkit v2
            array = eval(array)
        else:
            quit()
        print "GOT ARRAY: ", array

        tree = array_to_tree(array)
        send(preorder(invert(tree)))

Final level, only 100 nodes. No problem!

GOT ARRAY:  [46, 32, 17, 2, 42, 36, 553, 197, 56, 136, 68, 63, 65, 104, 98, 102, 136, 132, 130, 113, 111, 185, 172, 140, 156, 171, 189, 196, 412, 397, 334, 279, 275, 240, 232, 224, 236, 234, 252, 270, 260, 262, 309, 287, 292, 313, 397, 392, 339, 441, 418, 413, 417, 430, 419, 435, 545, 496, 491, 462, 506, 735, 626, 566, 556, 565, 563, 595, 574, 585, 621, 629, 664, 631, 666, 696, 691, 682, 775, 770, 923, 839, 835, 821, 783, 817, 796, 833, 829, 859, 875, 870, 874, 875, 897, 913, 951, 952, 952, 958]
SENT: [46, 553, 735, 775, 923, 951, 952, 958, 952, 839, 859, 875, 897, 913, 870, 874, 875, 835, 821, 833, 829, 783, 817, 796, 770, 626, 629, 664, 666, 696, 691, 682, 631, 566, 595, 621, 574, 585, 556, 565, 563, 197, 412, 441, 545, 496, 506, 491, 462, 418, 430, 435, 419, 413, 417, 397, 334, 397, 392, 339, 279, 309, 313, 287, 292, 275, 240, 252, 270, 260, 262, 232, 236, 234, 224, 56, 136, 185, 189, 196, 172, 140, 156, 171, 68, 104, 136, 132, 130, 113, 111, 98, 102, 63, 65, 32, 42, 36, 17, 2]
RECV: Yay, that's right!
=== FLAG: IW{10000101010101TR33} ===