Created
November 18, 2020 16:45
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Impressed 👍