"""route: a tiny language for choosing the order of three deliveries.

Pure Python, standard library only, no regular expressions, no backslashes (the source is embedded
verbatim into the device handler). The engine moves the robot along a fixed shortest Manhattan path
between chosen houses; the expert only chooses the order.

Program (JSON):
  {"name": "nearest first", "steps": [ {"pick": "nearest"} ]}
  step.pick: list | nearest | farthest | shortest_total | house
  step.house: A | B | C   (only with pick = house)
Steps apply in order, one decision each; the last step repeats until all houses are delivered.
Ties are broken alphabetically and named in the decision text. Levels used on the page have no ties.
"""
import json
import random

GRID = 7
HOUSES = ("A", "B", "C")
PICKS = ("list", "nearest", "farthest", "shortest_total", "house")
MAX_STEPS = 3
LEVEL1 = {"id": "level1", "start": [0, 3], "houses": {"A": [5, 1], "B": [1, 4], "C": [4, 3]}}


def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def validate(program):
    if not isinstance(program, dict):
        return False, "program must be an object with 'steps'"
    steps = program.get("steps")
    if not isinstance(steps, list) or not steps:
        return False, "'steps' must be a non-empty list"
    if len(steps) > MAX_STEPS:
        return False, "at most %d steps" % MAX_STEPS
    for i, step in enumerate(steps):
        if not isinstance(step, dict):
            return False, "step %d must be an object" % (i + 1)
        for key in step:
            if key not in ("pick", "house"):
                return False, "step %d: '%s' is not a word in route" % (i + 1, key)
        pick = step.get("pick")
        if pick not in PICKS:
            return False, "step %d: pick must be one of list, nearest, farthest, shortest_total, house" % (i + 1)
        if pick == "house" and step.get("house") not in HOUSES:
            return False, "step %d: house must be A, B or C" % (i + 1)
        if pick != "house" and "house" in step:
            return False, "step %d: 'house' goes only with pick = house" % (i + 1)
    name = program.get("name", "")
    if not isinstance(name, str) or len(name) > 60:
        return False, "'name' must be a short string"
    return True, "ok"


def total_len(pos, order, houses):
    n, cur = 0, pos
    for h in order:
        n += dist(cur, houses[h])
        cur = houses[h]
    return n


def permutations(items):
    if len(items) <= 1:
        return [list(items)]
    out = []
    for i, x in enumerate(items):
        for rest in permutations(items[:i] + items[i + 1:]):
            out.append([x] + rest)
    return out


def choose(step, pos, left, houses):
    """Returns (house or None, why, tie)."""
    pick = step["pick"]
    if pick == "house":
        h = step["house"]
        if h in left:
            return h, "house %s first, as the rule says" % h, False
        return None, "house %s is already delivered, next step" % h, False
    if pick == "list":
        return left[0], "first undelivered house in the list", False
    if pick in ("nearest", "farthest"):
        scored = sorted(((dist(pos, houses[h]), h) for h in left), reverse=(pick == "farthest"))
        best = scored[0]
        tie = len(scored) > 1 and scored[1][0] == best[0]
        why = "%s undelivered house, %d cells" % ("nearest" if pick == "nearest" else "farthest", best[0])
        if tie:
            why += " (tie with %s, alphabetical wins)" % scored[1][1]
        return best[1], why, tie
    if pick == "shortest_total":
        scored = sorted((total_len(pos, p, houses), "".join(p)) for p in permutations(list(left)))
        best = scored[0]
        tie = len(scored) > 1 and scored[1][0] == best[0] and scored[1][1][0] != best[1][0]
        why = "shortest total route from here: %s, %d cells" % (" then ".join(best[1]), best[0])
        if tie:
            why += " (tie, alphabetical wins)"
        return best[1][0], why, tie
    return None, "no rule matched", False


def walk(a, b):
    """Shortest Manhattan path from a to b, x first then y, excluding a, including b."""
    path, x, y = [], a[0], a[1]
    while x != b[0]:
        x += 1 if b[0] > x else -1
        path.append([x, y])
    while y != b[1]:
        y += 1 if b[1] > y else -1
        path.append([x, y])
    return path


def run(program, level, law=None):
    houses = {k: list(v) for k, v in level["houses"].items()}
    pos = list(level["start"])
    left = list(HOUSES)
    steps = program["steps"]
    order, decisions, path, ties = [], [], [], 0
    log = [{"t": 0, "pos": list(pos), "event": "start"}]
    si = 0
    guard = 0
    while left and guard < 10:
        guard += 1
        h, why, tie = None, "", False
        rule_no = None
        if law == "clinic_first" and "C" in left and not order:
            h, why, tie, rule_no = "C", "town law: the clinic (house C) is always served first", False, 0
        while h is None and si < len(steps):
            step = steps[si]
            h, why, tie = choose(step, pos, left, houses)
            rule_no = si + 1
            if h is None:
                si += 1          # step could not apply (house already delivered); move on
            elif si < len(steps) - 1:
                si += 1          # each step decides once; the last one repeats
        if h is None:            # steps exhausted: finish in list order, say so
            h, why, rule_no = left[0], "steps exhausted, list order", len(steps)
        ties += 1 if tie else 0
        t = len(path)
        decisions.append({"at": list(pos), "house": h, "why": why, "step": rule_no, "t": t, "cells": dist(pos, houses[h])})
        log.append({"t": t, "pos": list(pos), "event": "decide", "house": h, "rule": rule_no, "why": why})
        for cell in walk(pos, houses[h]):
            path.append(cell)
            log.append({"t": len(path), "pos": list(cell), "event": "move"})
        pos = houses[h]
        left.remove(h)
        order.append(h)
        log.append({"t": len(path), "pos": list(pos), "event": "deliver", "house": h})
    log.append({"t": len(path), "pos": list(pos), "event": "done"})
    return {"status": "success", "order": order, "moves": len(path), "delivered": len(order), "path": path,
            "decisions": decisions, "ties": ties, "log": log, "level": level, "law": law}


def make_level(seed):
    """Random 7x7 level with three houses, no ties for nearest/farthest/shortest_total, list order not optimal."""
    rng = random.Random(seed)
    for _ in range(2000):
        cells = set()
        while len(cells) < 4:
            cells.add((rng.randint(0, GRID - 1), rng.randint(0, GRID - 1)))
        cells = list(cells)
        rng.shuffle(cells)
        level = {"id": "seed%d" % seed, "start": list(cells[0]), "houses": {"A": list(cells[1]), "B": list(cells[2]), "C": list(cells[3])}}
        if any(dist(level["start"], v) < 2 for v in level["houses"].values()):
            continue
        if any(dist(level["houses"][a], level["houses"][b]) < 2 for a in HOUSES for b in HOUSES if a < b):
            continue
        ok = True
        for pick in ("nearest", "farthest", "shortest_total"):
            r = run({"steps": [{"pick": pick}]}, level)
            if r["ties"]:
                ok = False
        best = min(total_len(level["start"], p, level["houses"]) for p in permutations(list(HOUSES)))
        listed = run({"steps": [{"pick": "list"}]}, level)["moves"]
        if ok and listed > best:
            return level
    return dict(LEVEL1, id="fallback%d" % seed)


def describe(program):
    """One human sentence per step, built from the program, not from the wish."""
    words = {"list": "take the houses in list order", "nearest": "go to the nearest undelivered house",
             "farthest": "go to the farthest undelivered house first", "shortest_total": "take the shortest total route through the remaining houses"}
    parts = []
    for s in program["steps"]:
        parts.append("visit house %s" % s["house"] if s["pick"] == "house" else words[s["pick"]])
    text = parts[0] + ", after each delivery" if len(parts) == 1 else ", then ".join(parts)
    return text[0].upper() + text[1:] + "."


def check_program(program, seeds=(11, 12, 13)):
    ok, reason = validate(program)
    if not ok:
        return False, {"grammar": reason}
    report = {"grammar": "ok", "levels": []}
    for level in [LEVEL1] + [make_level(s) for s in seeds]:
        r = run(program, level)
        good = sorted(r["order"]) == list(HOUSES) and r["delivered"] == 3
        report["levels"].append({"level": level["id"], "order": "".join(r["order"]), "moves": r["moves"], "ok": good})
        if not good:
            return False, report
    return True, report


if __name__ == "__main__":
    for pick in ("list", "nearest", "shortest_total", "farthest"):
        r = run({"steps": [{"pick": pick}]}, LEVEL1)
        print(pick, r["order"], r["moves"], "ties", r["ties"], "|", r["decisions"][1]["why"])