Simulation designed for solving "Mining Massive Datasets MOOC@Coursera" exercise

adverts.jl

typealias Slot   Int
typealias Bidder Int

immutable BidderRoundData
  numSlots      :: Int
  ctr           :: Dict{(Bidder, Slot), Float64}
  bids          :: Vector{Float64}
  budgets       :: Vector{Float64}
  clickThroughs :: Int
end

function simulateRound(roundData :: BidderRoundData, allowedClicks :: Int)
  bidders      = [ i for i in 1:length(roundData.bids) ]
  winnerSlots  = zeros(bidders)
  roundBids    = zeros(roundData.bids)

  bidderClicks = [ 0.0 for _ in 1:roundData.numSlots ]

  # Step 1: Find who would win the slots
  for i in 1:roundData.numSlots
    maxExpRevenue, winner = -1, -1

    for b in bidders
      if roundData.budgets[b] > 0 && winnerSlots[b] == 0
        expRevenue = ctr[ (b, i) ] * roundData.bids[ b ]
        if expRevenue > maxExpRevenue
          maxExpRevenue = expRevenue
          winner = b
        end
      end
    end

    if winner != -1
      winnerSlots[winner] = i
      roundBids[winner]   = roundData.bids[winner]
    end
  end

  # Step 2: Find out how long the bidding war will go on
  # The two ways of ending a phase:
  #  - Bidder running out of money
  #  - Total click-through = 101

  # Step 2.1: Find how many click through-s for each winner remain
  clicksToFinishBudgetForEach = roundData.budgets ./ roundBids

  # Step 2.2: Find how many clicks before the sim ends
  # First, find the CTR of each bidder (non-zero only for the winners)
  winnerCTRs = zeros(roundData.bids)
  for b in bidders
    if winnerSlots[b] != 0
      winnerCTRs[b] = roundData.ctr[ (b, winnerSlots[b]) ]
    end
  end

  combinedCTR = sum(winnerCTRs)
  impressionsToFinishBudget = clicksToFinishBudgetForEach ./ winnerCTRs
  impressionsToFinishCTRs = (allowedClicks - roundData.clickThroughs) / combinedCTR

  # Step 2.3: Find the number of clicks this round will last
  impressionsInRound = apply(min, [ impressionsToFinishCTRs impressionsToFinishBudget' ])

  # Step 3: Create the new round data: for the next round or to end sim

  # Step 3.1: Find out how many clicks each bidder got and their new bidget
  bidderClicks = round(impressionsInRound * winnerCTRs)
  newBudget    = roundData.budgets - roundData.bids .* bidderClicks

  # Step 3.2: If a bidder's budget is too low for a single add, make it zero
  newBudget[ newBudget .< roundData.bids ] = 0.0

  newRoundData = BidderRoundData( roundData.numSlots
                                , roundData.ctr
                                , roundData.bids
                                , vec(newBudget)
                                , roundData.clickThroughs + sum(bidderClicks)
                                )

  return (bidderClicks, newRoundData)
end

function runSim(initRoundData :: BidderRoundData, finalClicks :: Int)
  roundData = initRoundData
  roundIdx = 0
  totalBidderClicks = [ 0 for _ in 1:length(initRoundData.bids) ]

  while roundData.clickThroughs < finalClicks
    (bidderClicks, roundData) = simulateRound(roundData, finalClicks)
    totalBidderClicks = totalBidderClicks + bidderClicks
    roundIdx += 1
    println("Total clicks: ", roundData.clickThroughs, " after round: ", roundIdx, " bidderClicks = ", bidderClicks)
  end

  return totalBidderClicks
end

ctr = {
  (1, 1) => 0.015,
  (1, 2) => 0.010,
  (1, 3) => 0.005,

  (2, 1) => 0.016,
  (2, 2) => 0.012,
  (2, 3) => 0.006,

  (3, 1) => 0.017,
  (3, 2) => 0.014,
  (3, 3) => 0.007,

  (4, 1) => 0.018,
  (4, 2) => 0.015,
  (4, 3) => 0.008,

  (5, 1) => 0.019,
  (5, 2) => 0.016,
  (5, 3) => 0.010
}

initRoundData = BidderRoundData( 3
                               , ctr
                               , [ x / 100 for x in 10:-1:6 ]
                               , [ x for x in 1:5 ]
                               , 0
                               )

# Test: nextRound = simulateRound(initRoundData, 101)
# Execution: runSim(initRoundData, 101)