Project Wonderful is no more. ☹ As a little project, I've been trying to (slowly) re-implement the service. Here's my implementation of the Infinite Auction. The main function is
run_auction; you feed it
Bids and it'll tell you when you need to change what ad is showing and how much to deduct from the account.
"""An implementation of Project Wonderful's Infinite Auction.""" # This implementation is unaffiliated with Project Wonderful and is not # guaranteed to behave identically to Project Wonderful's implementation. # For a friendly description of the algorithm, see: # https://web.archive.org/web/20180612112237/ # https://www.projectwonderful.com/abouttheinfiniteauction.php from collections import deque NANOSECONDS_PER_DAY = 86400000000000 Nanotime = int Currency = int Tokens = int class Bid: __slots__ = 'bid', 'expense_limit', 'expiry', 'id' def __init__(self, bid: Currency, expense_limit: Tokens, expiry: Nanotime, id=None): self.bid = bid self.expense_limit = expense_limit self.expiry = expiry self.id = id def winning_bid(bids, increment: Currency) -> (Bid, Currency): """Get the highest bid. In the event of a tie, goes with the first.""" try: return next(winning_bids(bids, increment)) except StopIteration: return None, 0 def winning_bids(bids, increment: Currency) -> [(Bid, Currency)]: bids = sorted(enumerate(bids), key=lambda a: (a.bid, -a)) output = deque() to_beat = 0 for i, bid in bids: bid_amount = bid.bid output.appendleft((bid, min(bid_amount, to_beat))) to_beat = bid_amount + increment yield from output def valid_bids(bids: [Bid], now: Nanotime=0) -> [Bid]: """Filter bids for valid ones. It's best to do this in SQL or something; don't use this function please. """ for bid in bids: if bid.bid > 0 and bid.expense_limit > 0 and bid.expiry > now: yield bid def find_end(amount: Currency, limit: Tokens, expiry: Nanotime, now: Nanotime) -> (Nanotime, Tokens): """Find the end point of a bid, so a timer can be set. WARNING: Assumes that this is the only bid; ensure that expiry is the minimum of the expiry date of the bid and the amount's validity. A naïve use would be to take the minimum of all bids' expiry dates, but this is suboptimal. """ if expiry <= now: raise ValueError("Expiry date in the past! Bid invalid.") if amount == 0: return expiry, 0 broke = (limit // amount) + now if broke > expiry: return expiry, ((expiry - now) * amount) return broke, limit - (limit % amount) def run_auction(bids: [Bid], increment: Currency, now: Nanotime) -> [(Bid, Nanotime, Tokens)]: """Run an auction and yield (current bid, when it ends, tokens spent).""" bids = list(bids) expense_limits = [bid.expense_limit for bid in bids] while bids: candidates = winning_bids(bids, increment) while True: try: candidate, candidate_amount_c = next(candidates) except StopIteration as e: return # No more candidates index = bids.index(candidate) if candidate_amount_c <= expense_limits[index]: # It has a chance of being able to pay bid = candidate bid_amount_c = candidate_amount_c break candidate_index = None while True: try: candidate, candidate_amount_c = next(candidates) except StopIteration as e: expiry = bid.expiry break candidate_index = bids.index(candidate) if candidate_amount_c <= expense_limits[candidate_index]: expiry = min(candidate.expiry, bid.expiry) break del candidate, candidate_amount_c, candidate_index now, spent_t = find_end(bid_amount_c, expense_limits[index], expiry, now) assert bid_amount_c == 0 or spent_t > 0, "Stuck in an infinite loop!" expense_limits[index] -= spent_t yield bid, now, spent_t i = 0 while i < len(bids): if bids[i].expiry <= now: del bids[i] del expense_limits[i] else: i += 1
You can find the tests here. I've tried to make the program clear, but it's really a bit of a mess. How can I improve it?