Download backend/flagship/split.py from Gaurav711/HyperFlow: direct link, hf CLI and curl.
- Browser
- Download file 8.42 kB
-
https://huggingface.co/spaces/Gaurav711/HyperFlow/resolve/main/backend/flagship/split.py
- Command line
-
hf download hf://spaces/Gaurav711/HyperFlow/backend/flagship/split.py
-
curl -L -o split.py https://huggingface.co/spaces/Gaurav711/HyperFlow/resolve/main/backend/flagship/split.py
8.42 kB
| """Cheapest way to split one basket across stores, including per-store fees. | |
| Each store charges a handling fee when used, a delivery fee unless its subtotal reaches a free-delivery | |
| threshold (no threshold: always charged), and a small-cart fee while its subtotal is below a small-cart | |
| threshold (no threshold: never charged). Money is integer minor units throughout. | |
| """ | |
| import itertools | |
| import numpy as np | |
| from scipy.optimize import Bounds, LinearConstraint, milp | |
| STORE_FIELDS = ('delivery_fee_minor', 'free_delivery_threshold_minor', 'handling_fee_minor', | |
| 'small_cart_fee_minor', 'small_cart_threshold_minor') | |
| OPTIONAL = {'free_delivery_threshold_minor', 'small_cart_threshold_minor'} | |
| MAX_ITEMS, MAX_STORES = 50, 6 | |
| def _money(value, optional=False): | |
| if optional and value is None: | |
| return True | |
| return isinstance(value, int) and not isinstance(value, bool) and 0 <= value <= 10**10 | |
| def _validate(items, stores): | |
| if not isinstance(stores, dict) or not 1 <= len(stores) <= MAX_STORES: | |
| raise ValueError(f'Provide 1 to {MAX_STORES} stores') | |
| for name, fees in stores.items(): | |
| if not isinstance(name, str) or not isinstance(fees, dict) or set(fees) != set(STORE_FIELDS): | |
| raise ValueError('Each store needs exactly the documented fee fields') | |
| if not all(_money(fees[f], f in OPTIONAL) for f in STORE_FIELDS): | |
| raise ValueError('Store fees and thresholds must be nonnegative integers in minor units') | |
| if not isinstance(items, list) or not 1 <= len(items) <= MAX_ITEMS: | |
| raise ValueError(f'Provide 1 to {MAX_ITEMS} items') | |
| seen = set() | |
| for it in items: | |
| if not isinstance(it, dict) or not isinstance(it.get('id'), str) or not it['id'] or it['id'] in seen: | |
| raise ValueError('Items need unique nonempty string ids') | |
| seen.add(it['id']) | |
| quantity = it.get('quantity') | |
| if not isinstance(quantity, int) or isinstance(quantity, bool) or not 1 <= quantity <= 10000: | |
| raise ValueError('Item quantity must be a positive integer') | |
| offers = it.get('offers') | |
| if not isinstance(offers, dict) or not set(offers) <= set(stores): | |
| raise ValueError('Offers must reference known stores') | |
| for o in offers.values(): | |
| limit = o.get('purchase_limit') if isinstance(o, dict) else None | |
| if (not isinstance(o, dict) or not _money(o.get('price_minor')) or not isinstance(o.get('available'), bool) | |
| or not isinstance(limit, int) or isinstance(limit, bool) or not 1 <= limit <= 10000): | |
| raise ValueError('Offers need integer minor prices, an available flag and a positive purchase limit') | |
| def _allowed(it): | |
| return {s: o['price_minor'] * it['quantity'] for s, o in it['offers'].items() | |
| if o['available'] and it['quantity'] <= o['purchase_limit']} | |
| def _store_total(fees, subtotal): | |
| free = fees['free_delivery_threshold_minor'] | |
| small = fees['small_cart_threshold_minor'] | |
| return (subtotal + fees['handling_fee_minor'] | |
| + (fees['delivery_fee_minor'] if free is None or subtotal < free else 0) | |
| + (fees['small_cart_fee_minor'] if small is not None and subtotal < small else 0)) | |
| def _price(assignment, costs, stores): | |
| """Store totals and grand total for a complete assignment; shared by the solver and the oracle.""" | |
| subtotals = {} | |
| for item_id, s in assignment.items(): | |
| subtotals[s] = subtotals.get(s, 0) + costs[item_id][s] | |
| totals = {s: _store_total(stores[s], sub) for s, sub in sorted(subtotals.items())} | |
| return totals, sum(totals.values()) | |
| def _result(assignment, costs, stores, unpurchasable): | |
| if not assignment: | |
| return {'status': 'infeasible', 'assignment': {}, 'store_totals_minor': {}, 'total_minor': None, | |
| 'best_single_store': {'store': None, 'total_minor': None}, 'savings_minor': None, | |
| 'unpurchasable': unpurchasable} | |
| totals, total = _price(assignment, costs, stores) | |
| singles = [(_price({i: s for i in assignment}, costs, stores)[1], s) for s in stores | |
| if all(s in costs[i] for i in assignment)] | |
| best = min(singles) if singles else None | |
| return {'status': 'optimal', 'assignment': dict(sorted(assignment.items())), 'store_totals_minor': totals, | |
| 'total_minor': total, 'best_single_store': {'store': best[1], 'total_minor': best[0]} if best else | |
| {'store': None, 'total_minor': None}, 'savings_minor': best[0] - total if best else None, | |
| 'unpurchasable': unpurchasable} | |
| def _prepare(items, stores): | |
| _validate(items, stores) | |
| costs = {it['id']: _allowed(it) for it in items} | |
| unpurchasable = [i for i, c in costs.items() if not c] | |
| return {i: c for i, c in costs.items() if c}, unpurchasable | |
| def solve_split(items, stores): | |
| costs, unpurchasable = _prepare(items, stores) | |
| if not costs: | |
| return _result({}, costs, stores, unpurchasable) | |
| ids, names = list(costs), list(stores) | |
| n, m = len(ids), len(names) | |
| # Variables: x[i,s] (n*m), then used u[s], free-delivery f[s], not-small-cart c[s]. | |
| X, U, F, C = 0, n * m, n * m + m, n * m + 2 * m | |
| size = n * m + 3 * m | |
| cost, upper = np.zeros(size), np.ones(size) | |
| rows, low, high = [], [], [] | |
| def row(coefficients, lo, hi): | |
| r = np.zeros(size) | |
| for index, value in coefficients: | |
| r[index] += value | |
| rows.append(r), low.append(lo), high.append(hi) | |
| for i, item_id in enumerate(ids): | |
| for s, name in enumerate(names): | |
| k = X + i * m + s | |
| if name in costs[item_id]: | |
| cost[k] = costs[item_id][name] | |
| row([(k, 1), (U + s, -1)], -np.inf, 0) # buy only from a used store | |
| else: | |
| upper[k] = 0 | |
| row([(X + i * m + s, 1) for s in range(m)], 1, 1) | |
| for s, name in enumerate(names): | |
| fees = stores[name] | |
| subtotal = [(X + i * m + s, -cost[X + i * m + s]) for i in range(n)] | |
| cost[U + s] = fees['handling_fee_minor'] + fees['delivery_fee_minor'] + fees['small_cart_fee_minor'] | |
| cost[F + s] = -fees['delivery_fee_minor'] | |
| cost[C + s] = -fees['small_cart_fee_minor'] | |
| row([(F + s, 1), (U + s, -1)], -np.inf, 0) | |
| row([(C + s, 1), (U + s, -1)], -np.inf, 0) | |
| if fees['free_delivery_threshold_minor'] is None: | |
| upper[F + s] = 0 | |
| else: | |
| row([(F + s, fees['free_delivery_threshold_minor'])] + subtotal, -np.inf, 0) | |
| if fees['small_cart_threshold_minor'] is None: | |
| row([(C + s, 1), (U + s, -1)], 0, 0) # never charged: waiver tracks use | |
| else: | |
| row([(C + s, fees['small_cart_threshold_minor'])] + subtotal, -np.inf, 0) | |
| result = milp(cost, integrality=np.ones(size), bounds=Bounds(np.zeros(size), upper), | |
| constraints=LinearConstraint(np.array(rows), low, high), | |
| options={'time_limit': 5, 'presolve': False, 'mip_rel_gap': 0.0}) | |
| if not result.success or result.x is None: | |
| raise RuntimeError('Split solver did not reach a verified optimum') | |
| x = np.rint(result.x[:n * m]).reshape(n, m) | |
| assignment = {} | |
| for i, item_id in enumerate(ids): | |
| chosen = [names[s] for s in range(m) if x[i, s] == 1] | |
| if len(chosen) != 1 or chosen[0] not in costs[item_id]: | |
| raise RuntimeError('Split solver returned an invalid assignment') | |
| assignment[item_id] = chosen[0] | |
| # Independent check: re-price the assignment and require it to match the solver's objective. | |
| if _price(assignment, costs, stores)[1] != round(result.fun): | |
| raise RuntimeError('Split solver objective failed independent re-pricing') | |
| return _result(assignment, costs, stores, unpurchasable) | |
| def brute_force_split(items, stores, max_items=8): | |
| """Exhaustive oracle over every store choice per item, for small instances only.""" | |
| costs, unpurchasable = _prepare(items, stores) | |
| if len(costs) > max_items: | |
| raise ValueError(f'Brute force is limited to {max_items} purchasable items') | |
| if not costs: | |
| return _result({}, costs, stores, unpurchasable) | |
| ids = list(costs) | |
| best = min((_price(dict(zip(ids, combo)), costs, stores)[1], combo) | |
| for combo in itertools.product(*(sorted(costs[i]) for i in ids))) | |
| return _result(dict(zip(ids, best[1])), costs, stores, unpurchasable) | |