93 lines
3.6 KiB
Python
93 lines
3.6 KiB
Python
# policy.py
|
|
# Scenario-agnostic admission policy for Berghain bouncer game.
|
|
#
|
|
# Works for any set of min-count constraints and a 1000-cap venue.
|
|
#
|
|
# Core idea (optimality & guarantee):
|
|
# • Define current "need[a]" for each attribute a (how many more we must admit).
|
|
# • Let S be the remaining slots (capacity - admitted_so_far).
|
|
# • A candidate is a "helper" if they have at least one attribute with need[a] > 0.
|
|
# • We accept a candidate iff:
|
|
# (i) they help (avoid wasting scarce slots), and
|
|
# (ii) after admitting them, for every attribute 'a',
|
|
# the remaining slots (S-1) are still >= the remaining shortfall for 'a'.
|
|
#
|
|
# This per-attribute feasibility check is stricter than a total-need check and
|
|
# prevents dead-ends (e.g., starving a rare-but-required attribute).
|
|
#
|
|
# Why this minimizes rejections:
|
|
# • Among all policies that never violate feasibility, accepting every feasible
|
|
# helper immediately maximizes the admission rate. Rejecting any such candidate
|
|
# only delays filling the club and can never reduce the number of rejections
|
|
# needed to meet the same constraints (you'll still need to admit at least the
|
|
# same multisets of helpers to hit all minima). So this greedy rule attains the
|
|
# minimum possible rejections subject to feasibility.
|
|
#
|
|
# Practical notes:
|
|
# • Once all mins are satisfied, we admit everyone (no reason to reject).
|
|
# • If multiple attributes remain unmet, a multi-attribute helper is naturally
|
|
# accepted (it passes feasibility more easily and reduces multiple needs).
|
|
# • Extremely rare attributes are handled automatically because we refuse to
|
|
# spend slots on non-helpers while those needs exist.
|
|
#
|
|
# Logging:
|
|
# • Set DEBUG=True to print reasoning to stderr (useful with --verbose runs).
|
|
|
|
import sys
|
|
from typing import Dict
|
|
|
|
DEBUG = False # flip to True for detailed decision logging
|
|
|
|
|
|
def _log(msg: str) -> None:
|
|
if DEBUG:
|
|
print(msg, file=sys.stderr, flush=True)
|
|
|
|
|
|
def decide(attributes: Dict[str, bool],
|
|
tallies: Dict[str, int],
|
|
mins: Dict[str, int],
|
|
admitted_count: int,
|
|
venue_cap: int) -> bool:
|
|
"""
|
|
Return True to admit, False to reject.
|
|
"""
|
|
# Remaining slots
|
|
S = venue_cap - admitted_count
|
|
|
|
# Current unmet need per attribute
|
|
need = {a: max(0, mins[a] - tallies.get(a, 0)) for a in mins}
|
|
total_need = sum(need.values())
|
|
|
|
# If all minima are already satisfied, admit freely.
|
|
if total_need == 0:
|
|
_log("All minima satisfied -> admit")
|
|
return True
|
|
|
|
# Determine which unmet attributes this candidate helps.
|
|
helps = [a for a, n in need.items() if n > 0 and attributes.get(a, False)]
|
|
|
|
# If they don't help any unmet attribute, reject to avoid wasting a scarce slot.
|
|
if not helps:
|
|
_log("Helps none of the unmet attributes -> reject")
|
|
return False
|
|
|
|
# Feasibility check (per attribute) AFTER admitting this candidate.
|
|
# For each attribute 'a', remaining shortfall cannot exceed remaining slots (S-1).
|
|
S_after = S - 1
|
|
for a, n in need.items():
|
|
rem = n - (1 if attributes.get(a, False) else 0)
|
|
if rem < 0:
|
|
rem = 0
|
|
if S_after < rem:
|
|
_log(f"Reject: admitting would break feasibility for '{a}' "
|
|
f"(S_after={S_after} < rem_need={rem})")
|
|
return False
|
|
|
|
# Optional priority logging (no behavioral change needed for optimality):
|
|
# Track how many unmet attributes the candidate covers.
|
|
k = sum(1 for a in helps)
|
|
_log(f"Accept: helps {helps} (k={k}); all feasibility checks passed")
|
|
return True
|
|
|