Fast and slow pointers: middle and cycles

brute/brute_force.py

"""Brute force for both problems, with the work counted.

A: the first node of a redirect loop, using O(1) memory: walk the chain, and at each step walk again from the start
to check whether the node just reached was seen before. B: the repeated ticket, by counting every possible number.
"""
from chains import chain


def loop_start_brute(first):
    """Return (the first node seen twice, or None, steps). Step k walks k nodes from the start again."""
    steps, node, k = 0, first, 0
    while node is not None:
        probe = first
        for _ in range(k):  # is node among the k nodes before it?
            steps += 1
            if probe is node:
                return node, steps
            probe = probe.next
        node, k = node.next, k + 1
    return None, steps


def repeated_ticket_brute(tickets):
    """Return (the number that appears twice or more, comparisons), counting each number from 1 to n."""
    comparisons = 0
    for v in range(1, len(tickets)):
        count = 0
        for t in tickets:
            comparisons += 1
            count += t == v
        if count > 1:
            return v, comparisons
    return None, comparisons


start, steps = loop_start_brute(chain("abcde", loop_to=2))
print(f"A: a -> b -> c -> d -> e -> back to c: the loop starts at {start.address} ({steps} steps)")
start, steps = loop_start_brute(chain("abc"))
print(f"A: a -> b -> c with no loop: {start} ({steps} steps)")
for n in (500, 1_000):  # a tail of n/2 nodes, then a loop of n/2 nodes
    kept = chain(range(n), loop_to=n // 2)
    _, steps = loop_start_brute(kept)
    print(f"A: {n:>5,} nodes: {steps:>9,} steps")

for tickets in ([4, 2, 5, 1, 3, 5], [3, 3, 3, 3], [2, 6, 4, 1, 3, 6, 5]):
    print(f"B: {tickets} -> {repeated_ticket_brute(tickets)[0]}")
for n in (1_000, 2_000):  # the repeated number is n, the last one the brute force counts
    _, comparisons = repeated_ticket_brute(list(range(1, n + 1)) + [n])
    print(f"B: n = {n:>5,}: {comparisons:>9,} comparisons")
n = 100_000
print(f"B: n = {n:,}: about {n * (n + 1):,} comparisons, {n * (n + 1) / 1e7 / 60:.0f} minutes at 10^7 a second")

A: a -> b -> c -> d -> e -> back to c: the loop starts at c (13 steps)
A: a -> b -> c with no loop: None (3 steps)
A:   500 nodes:   125,001 steps
A: 1,000 nodes:   500,001 steps
B: [4, 2, 5, 1, 3, 5] -> 5
B: [3, 3, 3, 3] -> 3
B: [2, 6, 4, 1, 3, 6, 5] -> 6
B: n = 1,000: 1,001,000 comparisons
B: n = 2,000: 4,002,000 comparisons
B: n = 100,000: about 10,000,100,000 comparisons, 17 minutes at 10^7 a second

brute/chains.py

"""Helpers for chains of redirects: nodes with an address and the next node, which may loop back."""


class Node:
    """One redirect: an address and the next node (None after the last address)."""

    def __init__(self, address, next=None):
        self.address = address
        self.next = next


def chain(addresses, loop_to=None):
    """Build a chain of nodes in order; with loop_to = i, the last node points back at node i. Returns the first node."""
    nodes = [Node(a) for a in addresses]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    if loop_to is not None and nodes:
        nodes[-1].next = nodes[loop_to]
    return nodes[0] if nodes else None