import random
import numpy as np

#parameters
N = 100
B = 100

# array of budgets (they all have the same budget initially) 
Bs = [B]*N
revenue = 0

for i in range(N): #rounds
  for j in range(B): #queries
    idx = np.argmax(Bs[i:]) # taking the index with the most budget, from the list(greedy approach)
    #print (Bs[i:])
    if Bs[i+idx]>0:
      Bs[i+idx] -= 1
      revenue += 1
      print (f'Round {i} query {j} -- allocated to bidder {i+idx}')
    else:
      print (f'Round {i} query {j} -- not allocated')

print (f'Total revenue: {revenue}')

# Parameters
N = 100  # Number of advertisers
B = 100  # Initial budget
R = 100  # Number of rounds

def generalized_balance():
    """
    Generalized BALANCE algorithm
    Selects advertiser with highest ψ_i = x_i * (1 - e^(-f_i))
    where f_i = 1 - (spent_i / B) and x_i = 1 (uniform bid)
    """
    budgets = [B] * N
    spent = [0] * N
    revenue = 0
    
    for r in range(R):
        for q in range(B):
            # Calculate psi for eligible advertisers
            eligible = [i for i in range(r, N) if budgets[i] > 0]
            
            if len(eligible) > 0:
                best_idx = max(eligible, key=lambda i: 1 * (1 - np.exp(-(1 - spent[i]/B))))
                budgets[best_idx] -= 1
                spent[best_idx] += 1
                revenue += 1
                print(f'Round {r} query {q} -- allocated to bidder {best_idx}')
            else:
                print(f'Round {r} query {q} -- not allocated')
    
    return revenue


revenue = generalized_balance()
print(f'\nTotal revenue: {revenue}')