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:
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, ]*]\$')

while True:
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} ===
``````