"""Original four-site set selection; Python 3.9 standard library."""
import itertools,json
from pathlib import Path
def validate(d):
 for key in ("choose","budget","capacity"):
  if not isinstance(d[key],int) or isinstance(d[key],bool) or d[key]<0:raise ValueError("Invalid bound")
 ids=[s["id"] for s in d["sites"]]
 if len(ids)!=len(set(ids)):raise ValueError("Duplicate sites")
 for s in d["sites"]:
  for key in ("cost","load","score"):
   if not isinstance(s[key],int) or isinstance(s[key],bool) or s[key]<0:raise ValueError("Invalid site number")
 if d["choose"]<1 or d["choose"]>len(ids):raise ValueError("Invalid selection size")
 for a,b in list(d["requires"].items())+d["incompatible"]:
  if a not in ids or b not in ids:raise ValueError("Unknown dependency site")
def assess(d,ids):
 by={s["id"]:s for s in d["sites"]}
 if len(ids)!=len(set(ids)) or any(i not in by for i in ids):raise ValueError("Invalid selected identifiers")
 rows=[by[i] for i in ids];reasons=[]
 if len(rows)!=d["choose"]:reasons.append("count")
 if not set(d["required_types"])<={s["type"] for s in rows}:reasons.append("types")
 if any(a in ids and b not in ids for a,b in d["requires"].items()):reasons.append("dependency")
 if any(set(pair)<=set(ids) for pair in d["incompatible"]):reasons.append("incompatible")
 cost=sum(s["cost"] for s in rows);load=sum(s["load"] for s in rows);score=sum(s["score"] for s in rows)
 if cost>d["budget"]:reasons.append("budget")
 if load>d["capacity"]:reasons.append("capacity")
 return {"ids":sorted(ids),"cost":cost,"load":load,"score":score,"reasons":reasons}
def solve(d):
 validate(d);all_rows=[assess(d,ids) for ids in itertools.combinations([s["id"] for s in d["sites"]],d["choose"])]
 feasible=[r for r in all_rows if not r["reasons"]];best=max((r["score"] for r in feasible),default=None)
 return {"examined":len(all_rows),"feasible_count":len(feasible),"best_score":best,"best":[r for r in feasible if r["score"]==best],"feasible":feasible}
if __name__=="__main__":
 print(json.dumps(solve(json.loads(Path(__file__).with_name("sites.json").read_text())),indent=2))
