Skip to content

Instantly share code, notes, and snippets.

@YannisDC
Created November 18, 2020 16:45
Show Gist options
  • Save YannisDC/98838410927ccdfc5bc384b43c64e038 to your computer and use it in GitHub Desktop.
Save YannisDC/98838410927ccdfc5bc384b43c64e038 to your computer and use it in GitHub Desktop.
This is just a training style problem solve to the 2020 Nobel Prize in Economics
import UIKit
// https://www.nobelprize.org/prizes/economic-sciences/2020/summary/
// All objects are auctioned simultaneously
// Bidder silently post their bids
// At the end of the first round the bidders can see all the bids and decide if they want to increase their bids or withraw their bid for thee next round
// The rounds keep going until we have a round where no more bids are placed or no more bids are withdrawn
enum LotAction {
case bid(offer: Double)
case withdraw
}
typealias RankingBid = (bidderId: String, price: Double)
typealias BidderLotAction = (bidderId: String, action: LotAction)
typealias RoundAction = (lotId: String, action: LotAction)
typealias RankingRound = (round: Int, ranking: [RankingBid])
class Lot {
let name: String
let id: String = UUID().uuidString
var reservePrice: Double
private var bids = [RankingBid]()
private var bidHistory = [RankingRound]()
init(name: String, reservePrice: Double = 0.0) {
self.name = name
self.reservePrice = reservePrice
}
func updateBids(with actions: [BidderLotAction]) {
var bidsToAdd = [RankingBid]()
var bidsToRemove = [String]()
actions.forEach { (bidderLotAction) in
switch bidderLotAction.action {
case .bid(let offer):
// Guard that the a bid is bigger then the reserve and the current highest bid
// If increased bid then update current bid
let currentHighestOffer = bids.map { $0.price }.sorted(by: >).first ?? reservePrice
guard offer > reservePrice, offer > currentHighestOffer else {
return
}
bidsToAdd.append(RankingBid(bidderId: bidderLotAction.bidderId, price: offer))
case .withdraw:
// If withdrawal then remove from bids
bidsToRemove.append(bidderLotAction.bidderId)
}
}
bidsToRemove.forEach { removeRankingBid(for: $0) }
bidsToAdd.forEach { updateRankingBid($0) }
bidHistory.append(RankingRound(round: bidHistory.count + 1, ranking: currentBids()))
}
func currentBids() -> [RankingBid] {
bids.sorted { (lhs, rhs) -> Bool in
lhs.price > rhs.price
}
}
func currentWinningBid() -> RankingBid? {
currentBids().first
}
func currentBidHistory() -> [RankingRound] {
bidHistory.sorted { (lhs, rhs) -> Bool in
lhs.round < rhs.round
}
}
private func removeRankingBid(for bidderId: String) {
bids.removeAll { $0.bidderId == bidderId}
}
private func updateRankingBid(_ rankingBid: RankingBid) {
bids.removeAll { $0.bidderId == rankingBid.bidderId}
bids.append(rankingBid)
}
}
class Bidder {
let name: String
let id: String = UUID().uuidString
var roundActions = [RoundAction]()
init(name: String) {
self.name = name
}
func bid(_ price: Double, for lot: Lot) {
if let previousBid = roundActions.first(where: { $0.lotId == lot.id }), let index = roundActions.firstIndex(where: { $0.lotId == lot.id }) {
if case .bid(let previousPrice) = previousBid.action {
guard price > previousPrice else {
return
}
roundActions.remove(at: index)
}
}
let action = RoundAction(lotId: lot.id, action: .bid(offer: price))
roundActions.append(action)
}
func withdraw(for lot: Lot) {
if let previousBid = roundActions.first(where: { $0.lotId == lot.id }), let index = roundActions.firstIndex(where: { $0.lotId == lot.id }) {
if case .bid(_) = previousBid.action {
roundActions.remove(at: index)
return
}
}
let action = RoundAction(lotId: lot.id, action: .withdraw)
roundActions.append(action)
}
func resetRoundActions() {
roundActions = [RoundAction]()
}
}
class SimultaneousMultiRoundAuction {
let lots: [Lot]
let bidders: [Bidder]
private var auctionConcluded: Bool = false
public var isAuctionConcluded: Bool {
auctionConcluded
}
struct BidderAction {
let bidderId: String
let action: RoundAction
}
init(lots: [Lot], bidders: [Bidder]) {
self.lots = lots
self.bidders = bidders
}
func updateRound() {
guard !auctionConcluded else {
return
}
// Assume the auction is concluded
auctionConcluded = true
for lot in lots {
var bidderActions = [BidderAction]()
for bidder in bidders {
guard let action = bidder.roundActions.first(where: { $0.lotId == lot.id }) else {
// If no action was found for this lot, do nothing
continue
}
// As soon as we find an action the auction is not concluded yet
auctionConcluded = false
bidderActions.append(BidderAction(bidderId: bidder.id, action: action))
}
let bidderLotActions = bidderActions.map {
BidderLotAction(bidderId: $0.bidderId, action: $0.action.action)
}
lot.updateBids(with: bidderLotActions)
}
bidders.forEach { $0.resetRoundActions() }
}
func leaders() {
let currentLeaders = lots.map { lot -> String in
if let winningBid = lot.currentWinningBid(), let winningBidder = bidderDetails(for: winningBid.bidderId) {
return "\(winningBidder.name) bid \(winningBid.price) for \(lot.name)"
}
return "No bids for \(lot.name)"
}
currentLeaders.forEach { print($0) }
}
func bidderDetails(for bidId: String) -> Bidder? {
bidders.first(where: { $0.id == bidId })
}
}
let lot1 = Lot(name: "Lot 1")
let lot2 = Lot(name: "Lot 2")
let alice = Bidder(name: "Alice")
let bob = Bidder(name: "Bob")
let charlie = Bidder(name: "Charlie")
let auction = SimultaneousMultiRoundAuction(lots: [
lot1,
lot2
], bidders: [
alice,
bob,
charlie
])
alice.bid(20.0, for: lot1)
auction.updateRound()
auction.lots.forEach { print($0.currentBids()) }
alice.bid(22.0, for: lot1)
bob.bid(21.0, for: lot1)
auction.updateRound()
auction.lots.forEach { print($0.currentBids()) }
auction.isAuctionConcluded
alice.withdraw(for: lot1)
charlie.bid(5.0, for: lot2)
auction.updateRound()
auction.lots.forEach { print($0.currentBids()) }
auction.leaders()
auction.isAuctionConcluded
auction.updateRound()
auction.isAuctionConcluded
@marcdecleene
Copy link

Impressed 👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment