File size: 7,654 Bytes
2b86c60 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | #!/usr/bin/env python3
"""Compare bounded baskets against independent exhaustive enumeration (no network)."""
import argparse
from datetime import datetime, timezone
from fractions import Fraction
import hashlib
from itertools import product
import json
from pathlib import Path
import platform
import random
import sys
import time
ROOT = Path(__file__).resolve().parents[1]
sys.path.insert(0, str(ROOT))
from backend.flagship.basket import optimize
def oracle(requirements, budget_minor=None):
"""Enumerate every bounded assignment per category; objectives are additive.
The only cross-category constraint is an upper price budget, so a sum of each
category's cheapest feasible assignment is globally cheapest. Among equal
prices, independently minimizing normalized overfill also minimizes its sum.
"""
cost, excess = 0, Fraction(0)
for req in requirements:
allowed = [v for v in req['variants'] if v['available'] and v['unit'] == req['unit']
and v['brand'].casefold() not in {b.casefold() for b in req['disallowed_brands']}
and (not req['preferred_brands'] or v['brand'].casefold() in {b.casefold() for b in req['preferred_brands']})]
best = None
for quantities in product(*(range(v['purchase_limit'] + 1) for v in allowed)):
volume = sum(q * v['volume'] for q, v in zip(quantities, allowed))
if volume < req['target_quantity']:
continue
candidate = (sum(q * v['price_minor'] for q, v in zip(quantities, allowed)),
Fraction(volume - req['target_quantity'], req['target_quantity']))
if best is None or candidate < best:
best = candidate
if best is None:
return None
cost += best[0]
excess += best[1]
return None if budget_minor is not None and cost > budget_minor else (cost, excess)
def generated_case(seed, index):
rng = random.Random(seed + index * 100003)
requirements = []
for category in range(1 + index % 3):
unit = ('g', 'ml', 'count')[category]
preferred = ['Alpha'] if index % 7 == 0 else []
excluded = ['Beta'] if index % 5 == 0 else []
variants = []
for variant in range(3):
identity = f'{index}-{category}-{variant}'
variants.append({'spin_id': 'spin-' + identity, 'sku_id': 'sku-' + identity,
'brand': ('Alpha', 'Beta', 'Gamma')[variant], 'price_minor': rng.choice([0, 50, 100, 150, 200]),
'volume': rng.randint(1, 12), 'unit': ('ml' if unit != 'ml' else 'g') if index % 11 == 0 and variant == 0 else unit,
'purchase_limit': rng.randint(1, 3), 'available': not (index % 9 == 0 and variant == 1)})
requirements.append({'category': f'category-{category}', 'target_quantity': rng.randint(1, 25),
'unit': unit, 'preferred_brands': preferred, 'disallowed_brands': excluded, 'variants': variants})
return requirements, None if index % 3 == 0 else rng.choice([0, 100, 250, 500, 1000, 2000])
def verify_result(requirements, budget, result, expected):
if expected is None:
return result.get('status') == 'infeasible', None
if result.get('status') != 'optimal':
return False, None
cost, excess = 0, Fraction(0)
selected = result['selected_items']
for req in requirements:
quantity = 0
catalog = {(v['spin_id'], v['sku_id']): v for v in req['variants']}
seen = set()
for item in [v for v in selected if v['category'] == req['category']]:
key = (item['spin_id'], item['sku_id'])
if key not in catalog or key in seen:
return False, None
seen.add(key)
variant = catalog[key]
q = item['quantity']
if (not isinstance(q, int) or isinstance(q, bool) or not 1 <= q <= variant['purchase_limit']
or not variant['available'] or variant['unit'] != req['unit']
or variant['brand'].casefold() in {b.casefold() for b in req['disallowed_brands']}
or (req['preferred_brands'] and variant['brand'].casefold() not in {b.casefold() for b in req['preferred_brands']})):
return False, None
cost += q * variant['price_minor']
quantity += q * variant['volume']
if quantity < req['target_quantity']:
return False, None
excess += Fraction(quantity - req['target_quantity'], req['target_quantity'])
if any(v['category'] not in {r['category'] for r in requirements} for v in selected):
return False, None
actual = (cost, excess)
return actual == expected and cost == result['subtotal_minor'] and (budget is None or cost <= budget), actual
def evaluate(cases=500, seed=20261020):
started = time.perf_counter()
results = []
for index in range(cases):
requirements, budget = generated_case(seed, index)
expected = oracle(requirements, budget)
begin = time.perf_counter()
try:
result = optimize(requirements, budget)
passed, actual = verify_result(requirements, budget, result, expected)
except Exception as exc:
result, passed, actual = {'status': 'error', 'error_type': type(exc).__name__}, False, None
encode = lambda obj: None if obj is None else {'price_minor': obj[0], 'normalized_excess': str(obj[1])}
results.append({'id': f'solver-{index:04}', 'passed': passed, 'requirements': requirements, 'budget_minor': budget,
'expected': encode(expected), 'actual': encode(actual), 'result': result,
'latency_ms': round((time.perf_counter() - begin) * 1000, 4)})
import scipy
import numpy
return {'suite': 'solver-v1', 'source': 'seeded_simulation', 'captured_at': datetime.now(timezone.utc).isoformat(),
'cases': cases, 'passed': sum(r['passed'] for r in results),
'failures': [r['id'] for r in results if not r['passed']],
'configuration': {'seed': seed, 'categories': [1, 2, 3], 'variants_per_category': 3, 'max_purchase_limit': 3,
'objective': 'integer price, then sum of normalized excess', 'network_calls': 0, 'model_calls': 0},
'runtime': {'python': platform.python_version(), 'platform': platform.platform(), 'scipy': scipy.__version__,
'numpy': numpy.__version__, 'elapsed_seconds': round(time.perf_counter() - started, 4)},
'source_sha256': {p: hashlib.sha256((ROOT / p).read_bytes()).hexdigest() for p in
('backend/flagship/basket.py', 'scripts/eval_solver.py')},
'limitations': ['Bounded generated cases do not establish all possible basket sizes or live provider correctness.'],
'results': results}
if __name__ == '__main__':
parser = argparse.ArgumentParser(description=__doc__)
parser.add_argument('--cases', type=int, default=500)
parser.add_argument('--seed', type=int, default=20261020)
parser.add_argument('--output', type=Path, required=True)
args = parser.parse_args()
if not 1 <= args.cases <= 10000:
parser.error('--cases must be 1 to 10000')
report = evaluate(args.cases, args.seed)
args.output.parent.mkdir(parents=True, exist_ok=True)
args.output.write_text(json.dumps(report, indent=2, allow_nan=False) + '\n')
print(json.dumps({k: report[k] for k in ('suite', 'cases', 'passed', 'failures', 'runtime')}))
raise SystemExit(0 if report['passed'] == report['cases'] else 1)
|