Bank.swift

/** 
 A user of the system. I prefer to use object right away (instead of just String), makes code more readable makes it more extendable later.
 Implements Hashable since I need this for uniquing later.
 */
struct User: Equatable, Hashable {
    let name: String
    
    var hashValue: Int { return name.hashValue }
}
func ==(lhs: User, rhs: User) -> Bool {
    return lhs.name == rhs.name
}

// A MoneyTransfer is the simples way to represent cash flow - just an amount a single User paid for or ows to the "community"
struct MoneyTransfer {
    let user: User
    let amount: Double
}

// An Balance is a user's balance.
struct Balance {
    let user: User
    var balance: Double
}

// A DebtPayment is a payment from a given user to another user.
struct DebtPayement {
    let from: User
    let to: User
    let amount: Double
}

// A Bank manages money transfers.
struct Bank {
    var transfers: [MoneyTransfer] = []

    // Add an expense, which is an amount payed by a single payer for any number of consumers (may, but doesn't have to include the payer).
    mutating func addExpense(totalAmount: Double, payer: User, consumers: [User]) {
        // Add one money transfer for the payer (increasing his balance by the amount
        transfers.append(MoneyTransfer(user: payer, amount: totalAmount))
        // Add a money transfer for each consumer; the amount is the total amount divided by the count of consumers.
        let amountPerConsumer = -totalAmount/Double(consumers.count)
        transfers.appendContentsOf(
            // Map every consumer to the MoneyTransfer that is added for him.
            consumers.map {
                consumer in
                MoneyTransfer(user: consumer, amount: amountPerConsumer)
            }
        )
    }
    
    // Add a transfer of a given amount from one user to another.
    mutating func addMoneyTransfer(amount: Double, fromUser: User, toUser: User) {
        // Transfer the the amount from the payer to the bank (by increasing that users balance)
        transfers.append(MoneyTransfer(user: fromUser, amount: amount))
        // Transfer the money from the bank to the recipient (by reducing that persons balance)
        transfers.append(MoneyTransfer(user: toUser, amount: -amount))
    }
    
    // Compute a balance for every user.
    func computeBalances() -> [Balance] {
        // Basically: For every user, sum the money transfers he has done.
        let accountHolders: [Balance] =
            Set(
                transfers.map {$0.user} // Compute user of every transfer
            ) // Create a set from the users so we have every user once only
            .map {
                currentUser in // For every user
                let balance = transfers // In every transfer
                    .filter { transfer in currentUser == transfer.user } // use only those transfers, where the current user is the transfer's user
                    .map { $0.amount } // For each of those transfers, get only the amount
                    .reduce(0, combine: +) // And sum the amounts to get the balance
                
                return Balance(user: currentUser, balance: balance)
            }
    
        return accountHolders
    }
    
    // Compute a list of DebtPayments that need to be made for everyone to be even. Does not modify the Bank.
    // Kinda inefficient, but shouldn't matter if you don't have thousands of simultaneous users.
    func computeDebtPayementsWithHighestDebtorsPayingFirst() -> [DebtPayement] {
        var bank = self // I didn't want to mutate the Bank object, so we create a copy here.
        let accuracy = 0.001 // If the debt is less than this amount, we consider it zero. Added this because rounding errors might cause an infinite loop otherwise.
        var debtPayments: [DebtPayement] = [] // The resulting debt payments.
        
        while true { // Infinit loop
            let balances = bank.computeBalances()
            
            let debtors = balances
                .filter { $0.balance < -accuracy } // Find all debtors with a negative balance
                .sort { $0.balance < $1.balance } // Sort them by amount of debt (highest first)
            let payers = balances
                .filter { $0.balance > accuracy } // Find all payers with positive balance
                .sort { $0.balance < $1.balance } // Sort them by amount paid (highest first)
            
            // If we don't have a debtor and payer remaining, we exit the loop.
            guard let highestDebtor = debtors.first else { break }
            guard let highestPayer = payers.first else { break }
            
            // We have a highestDebtor and paymentRemaining! The amount paid is the lower of the two.
            let amount = min(-highestDebtor.balance, highestPayer.balance)
            
            // Add the money transfer to the bank so it's reflected in when we compute the balances again in the next loop iteration.
            bank.addMoneyTransfer(amount, fromUser: highestDebtor.user, toUser: highestPayer.user)
            // Add a DebtPayment object that we can return when we're done.
            debtPayments.append(DebtPayement(from: highestDebtor.user, to: highestPayer.user, amount: amount))
        }
        
        return debtPayments
    }
    
}

// Some testing!
let user1 = User(name: "A")
let user2 = User(name: "B")
let user3 = User(name: "C")
let user4 = User(name: "D")

var bank = Bank()

bank.addExpense(400, payer: user1, consumers: [user1, user2, user3, user4])
bank.addExpense(400, payer: user2, consumers: [user1, user2, user3, user4])
bank.addExpense(40, payer: user3, consumers: [user1, user2, user3, user4])
bank.addExpense(40, payer: user4, consumers: [user1, user2, user3, user4])

let balances = bank.computeBalances().map { "\t\($0.user.name)'s balance: \($0.balance)$" }
print("Balances: ")
print(balances.joinWithSeparator("\n"))

let requiredPayments = bank.computeDebtPayementsWithHighestDebtorsPayingFirst()
let paymentStrings = requiredPayments.map { "\t\($0.from.name) pays to \($0.to.name): \($0.amount)$" }
print("Required payments to balance books:")
print(paymentStrings.joinWithSeparator("\n"))