Side views and zigzag level order

views/brute_force.py

"""Row by row, rescanning: for each row r, walk the whole formation again, no deeper than r, to collect that row.

All three answers come from the rows: the first and last value of each row are the side views, every other row read
backwards gives the zigzag order, and the row totals give the best row. The counter shows what that costs.
"""
from tree import build, formation, line

visits = 0


def row(root, r):
    """The values of row r, from left to right, found by a depth-first walk that stops below row r."""
    global visits
    values = []
    stack = [(root, 0)] if root is not None else []
    while stack:
        node, depth = stack.pop()
        visits += 1
        if depth == r:
            values.append(node.val)
            continue
        # Push the right child first, so that the left one is taken first: rows come out from left to right.
        if node.right is not None:
            stack.append((node.right, depth + 1))
        if node.left is not None:
            stack.append((node.left, depth + 1))
    return values


def rows_by_rescanning(root):
    rows = []
    while True:
        values = row(root, len(rows))
        if not values:  # an empty row: the formation has no more rows
            return rows
        rows.append(values)


def answers(root):
    rows = rows_by_rescanning(root)
    left_view = [r[0] for r in rows]
    right_view = [r[-1] for r in rows]
    zigzag = [r if d % 2 == 0 else r[::-1] for d, r in enumerate(rows)]
    totals = [sum(r) for r in rows]
    best = totals.index(max(totals)) if totals else -1  # index() finds the first, so the smallest row wins ties
    return left_view, right_view, zigzag, best


print(answers(build([4, -2, 7, 3, -8, None, 5, 6])))
print(answers(build([-3, -1, -2])))
print(answers(None))
print()

for n in (500, 1_000, 2_000):
    visits = 0
    rows_by_rescanning(line(n))
    print(f"a line of {n:,} drones: {visits:,} visits; n(n + 1)/2 + n = {n * (n + 1) // 2 + n:,}")
visits = 0
rows_by_rescanning(formation(4_095))
print(f"a complete formation of 4,095 drones in 12 rows: {visits:,} visits")
n = 100_000
print(f"a line of {n:,} drones would need {n * (n + 1) // 2 + n:,} visits")

([4, -2, 3, 6], [4, 7, 5, 6], [[4], [7, -2], [3, -8, 5], [6]], 3)
([-3, -1], [-3, -2], [[-3], [-2, -1]], 0)
([], [], [], -1)

a line of 500 drones: 125,750 visits; n(n + 1)/2 + n = 125,750
a line of 1,000 drones: 501,500 visits; n(n + 1)/2 + n = 501,500
a line of 2,000 drones: 2,003,000 visits; n(n + 1)/2 + n = 2,003,000
a complete formation of 4,095 drones in 12 rows: 12,273 visits
a line of 100,000 drones would need 5,000,150,000 visits

views/tree.py

"""A binary tree node, a builder for a tree written as a list in level order, and two large test formations."""
from collections import deque


class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build(values):
    """The tree whose level-order list is `values`, with None where a child is missing."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if values[i] is not None:
            node.left = Node(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i])
            queue.append(node.right)
        i += 1
    return root


def score(i):
    """The reserve of drone i of a test formation: a fixed scramble of -1,000 to 1,000, the same in every language."""
    return i * 7919 % 2001 - 1000


def formation(n):
    """A complete formation of n drones, filled row by row from the left; drone i is the i-th in level order."""
    nodes = [Node(score(i)) for i in range(n)]
    for i, node in enumerate(nodes):
        if 2 * i + 1 < n:
            node.left = nodes[2 * i + 1]
        if 2 * i + 2 < n:
            node.right = nodes[2 * i + 2]
    return nodes[0] if nodes else None


def line(n):
    """n drones in one line, each the right follower of the one before."""
    root = None
    for i in range(n - 1, -1, -1):
        root = Node(score(i), None, root)
    return root


def release(root):
    """Takes a tree apart one link at a time.

    Freeing a tree frees each node from inside the step that frees its parent. CPython copes with a line of 100,000
    nodes, but Pyodide, the Python behind the Run button, stopped when a line of 3,000 nodes was freed at once, so the
    examples take their long test trees apart with this loop when they are done with them.
    """
    stack = [root] if root is not None else []
    while stack:
        node = stack.pop()
        stack.extend(child for child in (node.left, node.right) if child is not None)
        node.left = node.right = None