Dots and lines: networks and puzzles

"""Which figures can be traced in one stroke? Search every route, then compare.

For each small figure (a network of dots and lines) the program counts the
line ends at every dot (the degree), and then searches *every* possible route
that uses each line exactly once, starting from every dot. The search is
exhaustive, so for these figures its answer is certain. We then compare the
search with Euler's rule: a connected figure can be traced in one stroke
exactly when it has 0 or 2 dots of odd degree.

Runs unchanged in the browser (Pyodide) using only the standard library.
"""

import textwrap

#: Each figure is a list of lines; a line joins two dots (letters).
FIGURES = {
    "square": ["AB", "BC", "CD", "DA"],
    "square + diagonal": ["AB", "BC", "CD", "DA", "AC"],
    "envelope (2 diagonals)": ["AB", "BC", "CD", "DA", "AC", "BD"],
    "house": ["AB", "BC", "CD", "DA", "AC", "BD", "DE", "EC"],
    "bow tie": ["AB", "BC", "CA", "CD", "DE", "EC"],
    "two triangles apart": ["AB", "BC", "CA", "DE", "EF", "FD"],
    "Konigsberg bridges": ["IN", "IN", "IS", "IS", "IE", "NE", "SE"],
}

def dots(lines):
    """Return the sorted list of dots that appear on some line."""
    return sorted({d for line in lines for d in line})

def degrees(lines):
    """Return {dot: number of line ends at that dot}."""
    deg = {d: 0 for d in dots(lines)}
    for a, b in lines:
        deg[a] += 1
        deg[b] += 1
    return deg

def odd_dots(lines):
    """Return the sorted list of dots of odd degree."""
    return [d for d, k in degrees(lines).items() if k % 2 == 1]

def is_connected(lines):
    """True if every dot can be reached from every other dot along lines."""
    all_dots = dots(lines)
    if not all_dots:
        return True
    seen, todo = {all_dots[0]}, [all_dots[0]]
    while todo:
        here = todo.pop()
        for a, b in lines:
            for x, y in ((a, b), (b, a)):
                if x == here and y not in seen:
                    seen.add(y)
                    todo.append(y)
    return len(seen) == len(all_dots)

def find_one_stroke(lines):
    """Search every route that uses each line once; return one or None.

    A route is returned as a string of dots, e.g. "ABCA". Every starting dot
    and every order of lines is tried (depth-first search with backtracking).
    """
    used = [False] * len(lines)

    def extend(route):
        if all(used):
            return route
        here = route[-1]
        for i, (a, b) in enumerate(lines):
            if used[i] or here not in (a, b):
                continue
            used[i] = True
            found = extend(route + (b if here == a else a))
            used[i] = False
            if found:
                return found
        return None

    for start in dots(lines):
        found = extend(start)
        if found:
            return found
    return None

def euler_rule_says_yes(lines):
    """Euler's rule: connected, with 0 or 2 dots of odd degree."""
    return is_connected(lines) and len(odd_dots(lines)) in (0, 2)

def main():
    print("Figure                  degrees          odd  rule  search finds")
    agree = 0
    for name, lines in FIGURES.items():
        deg = degrees(lines)
        shown = " ".join(str(deg[d]) for d in dots(lines))
        rule = euler_rule_says_yes(lines)
        route = find_one_stroke(lines)
        agree += rule == (route is not None)
        answer = route if route else "no route"
        print(f"{name:<23} {shown:<16} {len(odd_dots(lines)):>3}  "
              f"{'yes' if rule else 'no':<4}  {answer}")
    print("(Degrees are listed in alphabetical order of the dots.)")
    print()
    print(f"The rule and the search agree on {agree} of {len(FIGURES)} figures.")
    print("Each route starts and ends at the odd dots, when there are two.")
    print("'Two triangles apart' has no odd dots but is not connected,")
    print("so the rule needs the word 'connected'.")
    print()
    print(textwrap.fill(
        "Epistemic status: for each of these seven figures the search tried "
        "every route, so its yes or no is certain (exhaustive-finite). The "
        "agreement with Euler's rule is evidence for the rule, not a proof: "
        "the lesson explains why odd dots must be the ends of a route, and "
        "the Lean module proves that half of the rule for every figure.",
        width=78,
    ))

if __name__ == "__main__":
    main()

"""Shortest routes on a small road map: list every route, then be clever.

Wanjiru cycles from home to the market. The map has five places and six
roads, each marked with its length in kilometres. First the program lists
*every* route that never visits a place twice, with its number of roads and
its length: an exhaustive check. Then it runs Dijkstra's method, which finds
the shortest distance from home to every place without listing all routes,
by always settling the nearest place not yet settled.

Runs unchanged in the browser (Pyodide) using only the standard library.
"""

import textwrap

#: (place, place, kilometres)
ROADS = [
    ("Home", "Well", 7),
    ("Well", "Market", 6),
    ("Home", "School", 2),
    ("School", "Bridge", 3),
    ("Bridge", "Market", 4),
    ("Well", "Bridge", 2),
]

def neighbours(roads):
    """Return {place: {neighbour: km}} for roads that work in both directions."""
    near = {}
    for a, b, km in roads:
        near.setdefault(a, {})[b] = km
        near.setdefault(b, {})[a] = km
    return near

def all_routes(roads, start, goal):
    """Every route from start to goal that never visits a place twice."""
    near = neighbours(roads)
    found = []

    def extend(route):
        here = route[-1]
        if here == goal:
            found.append(route)
            return
        for nxt in sorted(near[here]):
            if nxt not in route:
                extend(route + [nxt])

    extend([start])
    return found

def route_length(roads, route):
    """Total kilometres along a route (a list of places)."""
    near = neighbours(roads)
    return sum(near[a][b] for a, b in zip(route, route[1:]))

def dijkstra(roads, start):
    """Shortest distance from start to every place, and the settling order.

    Repeatedly settle the unsettled place with the smallest known distance,
    then update the distances of its neighbours.
    """
    near = neighbours(roads)
    best = {start: 0}
    settled = []
    while len(settled) < len(near):
        here = min((d, p) for p, d in best.items() if p not in settled)[1]
        settled.append(here)
        for nxt, km in near[here].items():
            if nxt not in best or best[here] + km < best[nxt]:
                best[nxt] = best[here] + km
    return best, settled

def main():
    routes = all_routes(ROADS, "Home", "Market")
    print("Every route from Home to Market that never repeats a place:")
    for route in sorted(routes, key=lambda r: (len(r), route_length(ROADS, r))):
        roads_used = len(route) - 1
        km = route_length(ROADS, route)
        print(f"  {' - '.join(route):<38} {roads_used} roads  {km:>2} km")
    fewest = min(routes, key=len)
    shortest = min(routes, key=lambda r: route_length(ROADS, r))
    print(f"Fewest roads:   {' - '.join(fewest)}"
          f" ({route_length(ROADS, fewest)} km)")
    print(f"Shortest route: {' - '.join(shortest)}"
          f" ({route_length(ROADS, shortest)} km)")
    print()
    best, settled = dijkstra(ROADS, "Home")
    print("Dijkstra's method settles the nearest unsettled place each time:")
    for place in settled:
        print(f"  {place:<7} {best[place]:>2} km from Home")
    print()
    print(textwrap.fill(
        "Epistemic status: exact. All four routes on this small map were "
        "listed, so the 9 km route is certainly the shortest here, and "
        "Dijkstra's method agrees. That the method always gives the shortest "
        "distance (when no road has negative length) is a theorem proved in "
        "later courses; this run checks one map only.",
        width=78,
    ))

if __name__ == "__main__":
    main()