Maximum path sum through any node

free/brute_force.py

"""The brute force: start a walk at every shop, follow the links in every direction, and add up the profits of every
chain that starts there. Every step of every walk is counted."""
import random

from tree import build, random_tree

steps = 0


def best_chain_brute(root):
    """The largest total profit of a chain of linked shops, any two ends, at least one shop."""
    global steps
    shops, links, queue = [], {}, [root] if root else []
    for shop in queue:  # list every shop and its links, up and down, without recursion
        shops.append(shop)
        links.setdefault(shop, [])
        for child in (shop.left, shop.right):
            if child is not None:
                links[shop].append(child)
                links[child] = [shop]
                queue.append(child)
    best = float("-inf")
    for start in shops:
        walk = [(start, None, start.val)]  # (shop, the shop we came from, profit of the chain so far)
        while walk:
            shop, came_from, total = walk.pop()
            steps += 1
            best = max(best, total)  # the chain from start to this shop
            walk += [(nxt, shop, total + nxt.val) for nxt in links[shop] if nxt is not came_from]
    return best


markets = {
    "market A": build([-6, 8, 2, 4, 7, None, 3, 6]),
    "market B, every shop at a loss": build([-3, -7, -2]),
    "one shop": build([5]),
}
for name, root in markets.items():
    steps = 0
    best = best_chain_brute(root)
    print(f"{name}: best chain {best} ({steps} step{'' if steps == 1 else 's'})")

rng = random.Random(1)
for n in (500, 1_000, 2_000):
    steps = 0
    best_chain_brute(random_tree(rng, n))
    print(f"random market of {n:,} shops: {steps:,} steps, n squared is {n * n:,}")

market A: best chain 25 (49 steps)
market B, every shop at a loss: best chain -2 (9 steps)
one shop: best chain 5 (1 step)
random market of 500 shops: 250,000 steps, n squared is 250,000
random market of 1,000 shops: 1,000,000 steps, n squared is 1,000,000
random market of 2,000 shops: 4,000,000 steps, n squared is 4,000,000

free/tree.py

"""Test markets for this lesson: build() reads a level-order list of shop profits, and random_tree() makes markets of
every shape. Neither uses recursion, so they work for any depth."""
from collections import deque


class Node:
    __slots__ = ("val", "left", "right")

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


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


def random_tree(rng, size, low=-10, high=10):
    """A market of `size` shops with profits from low to high: each new shop goes into a random empty place."""
    if size == 0:
        return None
    root = Node(rng.randint(low, high))
    places = [(root, "left"), (root, "right")]
    for _ in range(size - 1):
        parent, side = places.pop(rng.randrange(len(places)))
        child = Node(rng.randint(low, high))
        setattr(parent, side, child)
        places += [(child, "left"), (child, "right")]
    return root