// Input: nothing to use default or owner line // plus one or more customer lines. The owner line // a list of money entries seperated by a single // space. The customer line has the total integer // for purchases followed by a list of money entries // all seperated by a single space. Money entries // for both are two integers: the bill's denomination // and count of those held separated by an asterisk. // Created for this challenge: // https://www.sololearn.com/post/65703 // [Challenge] Cashier // Assuming you're a cashier and having some bills and coins. Now some customers need to pay some money and also have some bills and coins, but some of them need changes, so you should sort them and decide how they should pay so that everyone can get their changes right after they pay. // For example, // You have: [200*5, 100*2, 50*3, 10*2, 5*3, 1*3] // Customer 1 should pay 121 and have: [200*1] // Customer 2 should pay 45 and have: [50*1, 5*2, 1*6] // Then Customer 2 should pay first with [50*1, 1*5] and get change [10*1] // And then Customer 1 should pay [200*1] and get changes [50*1, 10*1, 5*3, 1*4] // Data class for some money holding a single bill // denomination and an amount of them being held. // Override the method to convert to a string. data class Money(val bill: Int, var amount: Int) { override fun toString() = "$bill*$amount" } // Money // Base class to hold and deal with a list of money. // Both the owner and customer classes inherit from // this one. But, it is also used to hold money // outside of those classes. open class Cash() { // Default the money to an empty list. var money = MutableList(0) { Money(0, 0) } // Declare a class wide set of bill denominations // so we can know the possibilities. companion object { private var denomination = mutableSetOf() // Class wide method to return a sorted list // of available bills from largest to smallest. fun denominations() = denomination.sortedByDescending { it } } // object // Secondary constructor to clone an instance // of this class. For all the money held by // the original instance, clone the money and // add it to the new instance's list of money. constructor(original: Cash) : this() { for (value in original.money) money.add(Money(value.bill, value.amount)) } // constructor // Secondary constructor to create an instance // holding a specific amount of money using // the largest denominations to handle that // amount. constructor(amount: Int) : this() { // Make a writable copy of the amount so we // can subtract the bills we used. For each // denomination starting with the largest, // figure out what we need. var cash = amount for (bill in denominations()) { // Count how many times this bill can go into // the remaining cash subtracting it each time // from the cash. var count = 0 while (cash >= bill) { count++ cash -= bill } // while // If this bill could be used, add it to our // money list with how many we can have. if (count > 0) money.add(Money(bill, count)) } // for } // constructor // Secondary constructor to create an instance // initialized by a list of money. constructor(cash: List) : this() { this.earn(cash) } // constructor // Method to return the number of money elements. fun size() = money.size // Operator method to read a particular money // element via array access. operator fun get(index: Int) = money[index] // Method to find the index of the money element // for the specified bill or -1, when not found. fun find(bill: Int) = money.indexOfFirst { it.bill == bill } // Method to make a list of the instance's money. fun toList() = money.toList() // Method to total our money. fun funds() = money.sumBy { value: Money -> value.bill*value.amount } // Method to figure out what bills and how many // of them to cover the specified amount. It // can either find an exact match or the closest // possible amount above the requested one. It // returns the selected bills and their count, // when found, or and empty list, when impossible. fun bills(amount: Int, exact: Boolean): List { // Default our result selection list to empty. // Default the selected sum to zero (sum of // values in our list.) We are going to remember // a bill that can provide more that our // requested amount in case we can not find an // exact fit (our extra defaulted to zero.) For // each element in our instance's money list, // process them. val selection = MutableList(0) { Money(0, 0) } var selected = 0 var extra = 0 for (value in money) { // Count how many of this bill we can use. // While we still haven't used them all and // one more doesn't put us over our target, // we can use another so increment the count. var count = 0 while (value.amount > count && value.bill* (count+1)+selected <= amount) count++ // Add this bill to our selection list and // update the selected sum to reflect it. // If we didn't use them all, this could // be the bill to use for the extra. selection.add(Money(value.bill, count)) selected += value.bill*count if (value.amount != count) extra = value.bill } // for // If we failed to reach our target and we // must be exact or even with our extra // push bill we fail to reach our target, // toss the list. if ((selected < amount && exact) || selected+extra < amount) selection.clear() // Otherwise, if we need the extra bill to // reach our target, for each bill, find the // extra bill plus all of the smaller ones // and adjust their counts to end up with a // total as close as posible to the target. else if (selected < amount) { for (index in selection.indices) // If we found our extra bill, add it to our // selection list and selected sum. if (selection[index].bill == extra) { selection[index].amount++ selected += extra // Otherwise, if the bill is smaller than // the extra bill, we need to adjust it. // While it's count is more than zero // and losing one is still our target // or more, subtract it from our selection // list and selected sum. } else if (selection[index].bill < extra) while (selection[index].amount > 0 && selected-selection[index].bill >= amount) { selection[index].amount-- selected -= selection[index].bill } // while } // if // Return the list we selected without any // elements we don't need because we never // used them or tossed their use. return selection.filter { value: Money -> value.amount > 0 } } // bills // Method to add the list of money to whatever // we already had. fun earn(list: List) { // Sort the list into an array from biggest // to smallest. val data = Array(list.size) { Money(list[it].bill, list[it].amount) } data.sortByDescending { value: Money -> value.bill } // Default the instance's money index to zero // and for each bill in our sorted array, process // it. var index = 0 for (value in data) { // Make sure the bill is in our list of bill // denominations. While our money index is // valid and our sorted array element's bill // is smaller than our current element in // our money list, increment to the next money // list index. denomination.add(value.bill) while (index < money.size && value.bill < money[index].bill) index++ // If we reached the end of our money list, // add the current array element to our money // list as we don't currently hold that bill. if (index == money.size) money.add(value) // Otherwise, if the bill in the array is // bigger than the one from our money list, // we don't currently hold that bill so // insert it before this one. else if (value.bill > money[index].bill) money.add(index, value) // Otherwise, the bill exists in both the // array and list so increment the list's // count by the array's. else money[index].amount += value.amount } // for } // earn // Method to remove a list of money from whatever // we already had. fun spend(list: List) { // Sort the list into an array from biggest // to smallest. val data = Array(list.size) { Money(list[it].bill, list[it].amount) } data.sortByDescending { value: Money -> value.bill } // Default the instance's money index to zero // and for each bill in our sorted array, process // it. var index = 0 for (value in data) { // While our money index is valid and our // sorted array element's bill is smaller // than our current element in our money // list, increment to the next money list // index. while (index < money.size && value.bill < money[index].bill) index++ // If we reached the end of the money list, // the bill was not found in the list, or // there are not enough of them available, // throw an exception. Should never happen // as the list parameter should be made from // our money list. if (index == money.size || value.bill > money[index].bill || value.amount > money[index].amount) throw IllegalStateException("Bill missing!") // Decrement our money's count of bills by // the array count. If the result is zero, // remove that element from our list. money[index].amount -= value.amount if (money[index].amount == 0) money.removeAt(index) } // for } // spend // Method to search our money for the given // list and return the list of what was missing. fun missing(list: List): List { // Default our result list to a list of every // denomination with a cout of zero. Each // index in the result list will map to // different indexes in our instance's money // list and the list of wanted bills so we // need three different indexes. Default // them to zero and increment as needed so // they point to the matching element or // some future one. val result = denominations().map { Money(it, 0) }.toMutableList() var original = 0 var wanted = 0 for (index in result.indices) { // If our index into the wanted list is // valid and the bill of the result list // element matches the bill of the wanted // list element, if (wanted < list.size && result[index].bill == list[wanted].bill) { // If our index into the money list is // valid and the bill of the result list // element matches the bill of the money // list element, we got all three lists // with the same bill's element. Now we // need to process them. if (original < money.size && result[index].bill == money[original].bill) { // If we want more than we have, we // need those missing so put that // amount into our result list. In // either case, the original index // must be incremented to the next // money element. if (list[wanted].amount > money[original].amount) result[index].amount = list[wanted].amount- money[original].amount original++ // Otherwise, the money list is missing this // bill so we are missing the entire count // of wanted element. } else result[index].amount = list[wanted].amount // Increment the wanted index to the next // element. wanted++ // Otherwise, the wanted list doesn't match // so if our index into the money list is // valid and the bill of the result list // element matches the bill of the money // list element, increment the money index. } else if (original < money.size && result[index].bill == money[original].bill) original++ } // for // Return our result list without the bills // that have a zero count. return result.filter { it.amount > 0 } } // missing // Overriden method to convert our money list // into a string with a total. override fun toString(): String { var result = "" for (bill in money) result += "$bill " return result+"for ${funds()}" } // toString } // Cash // Class to maintain a single purchase information // for later display. We can update this to force // bill exchanges to allow all transactions to // succeed. Class properties required on creation: // customer identifier, the cash data for the // payment, and the cash data for thw change given. // This data has already been reflected in the // owner and customer classes. class Purchase(val identifier: Int, val pays: Cash, val change: Cash) { // Class wide property to maintain a list of // purchases defaulting to empty. companion object { val purchases = MutableList(0) { Purchase(0, Cash(), Cash()) } // Class wide method to display all of the // purchases in the list. fun print() { for (purchase in purchases) println(purchase) } // print } // object // Constructor initialization to add this instance // to the class wide list of instances. init { purchases.add(this) } // init // Override the method to convert the class to a // string. The beginning part is identical // displaying the customer and their payment. // If no change was required, just finish with // the funds payed. Otherwise, display the // required payment and tge change given. override fun toString(): String { val refund = change.funds() var result = "Customer $identifier: pays with"+ " $pays for purchases of " result += if (refund == 0) "${pays.funds()}" else "${pays.funds()-refund} getting $change"+ " in change." return result } // toString } // Purchase // Singleton class for the store owner inheriting // the cash class. class Owner private constructor() : Cash() { // Class based instance of the class. companion object { val instance = Owner() } // object // Override the method to convert the class to a // string. override fun toString() = "Owner: holds ${super.toString()}" } // Owner // Class for the store customer inheriting the // cash class. class Customer() : Cash() { // Class wide properties for the customer: mext // identifier to assign defaulted to one and list // of all instances of the class defaulted to // empty. companion object { var next = 1 val customers = MutableList(0) { Customer() } // Class wide method to reset both properties, // used if the user entered data is junk so // the default test case is going to be used. fun clear() { customers.clear() next = 1 } // clear // Class wide method to display all of the // customer instances. fun print() { for (customer in customers) println(customer) } // print } // object // Instance base properties of the class: the // customer identifier and the amount of products // to purchase. Once paid for, the purchase // becomes zero. val identifier = next++ var purchase = 0 // Constructor initialization to add this instance // to the class wide list of instances. init { customers.add(this) } // init // Method to verify the customer has enough funds // to pay for the products. fun verify() = funds() >= purchase // Override the method to convert the class to a // string. The text ignores paid for purchases. override fun toString() = if (purchase == 0) "Customer $identifier: holds "+ "${super.toString()}" else "Customer $identifier: buys"+ " $purchase with ${super.toString()}" } // Customer // Function to process the transactions. fun process() { // Calculate how much was spent. We will deduct // each payment made from this, until we reach // zero or can't make change for some of our // customers. Save the original owner's money // so the purchases can be sorted into the // order needed. var spent = Customer.customers.sumBy { it.purchase } val original = Cash(Owner.instance.toList()) // Function to see if this customer can pay their // bill right now because we either have their // change in hand or they have the exact amount // owed. fun check(customer: Customer): Boolean { // Default whether we found a transaction to // no and the amount to see if we can pay to // our purchases. While we failed to find a // working transaction and the customer still // has funds we can spend, try again. var found = false var amount = customer.purchase while (!found && amount <= customer.funds()) { // Find the nearest higher or matching // combination of money to our current // amount. If we succeeded, see if we // can pay with this. val list = customer.bills(amount, false) if (list.size > 0) { // Update our amount to the funds used // by our list and, if it happens to be // an exact match to our purchases, this // transaction is good so finish it. amount = list.sumBy { it.bill*it.amount } if (customer.purchase == amount) { // Create a purchase transaction so we // can update it later to trade bills. // Note we found a transaction, decrement // the purchase price from spent & change // our purchases to zero so we know they // were paid, and remove the money from // the customer giving it to the owner. val purchase = Purchase( customer.identifier, Cash(list), Cash()) found = true spent -= customer.purchase customer.purchase = 0 customer.spend(list) Owner.instance.earn(list) // Otherwise, change is required so try // making it. } else { // Find an exact match for our change // needed to complete this transaction. // If found, this transaction is good // so finish it. val refund = Owner.instance.bills( amount-customer.purchase, true) if (refund.size > 0) { // Create a purchase transaction so we // can update it later to trade bills. // Note we found a transaction, decrement // the purchase price from spent & change // our purchases to zero so we know they // were paid, remove the money spent // from the customer giving it to the // owner, and give the change to the // customer removing it from the owner. val purchase = Purchase( customer.identifier, Cash(list), Cash(refund)) found = true spent -= customer.purchase customer.purchase = 0 customer.spend(list) Owner.instance.earn(list) customer.earn(refund) Owner.instance.spend(refund) } // if } // if } // if // Increment the next amount to search for. amount++ } // while // Return whether we found a transaction for // this customer. return found } // check // Function to decide if a customer can trade // the bills we are short for larger ones we // don't need so we can give the correct change // for the purchases that failed. fun fix(): Boolean { // Function to exchange a couple bills with // the other customer. Returns true, if the // exchange fails. fun exchange(bill: Int, amount: Int, other: Customer): Boolean { // Function to verify the owner will have // the change needed at time required. If // not, try reordering. fun verify(purchase: Purchase): Boolean { // Clone the original owner cash, the // purchase payment (adding our new bill), // and the purchase change (adding it's // replacement.) val test = Cash(original) val pays = Cash(purchase.pays) pays.earn(listOf(Money(bill, amount))) val change = Cash(purchase.change) change.earn(listOf(Money(bill*amount, 1))) // Default our result to usable. Setup // to possibly move our purchase by // defaulting seen to not yet and our // positions to invalid. var result = true var seen = false var from = -1 var to = -1 // For each existing purchase, we will make // sure the required funds are available // in the owner money to make our change. for ((index, transaction) in Purchase.purchases.withIndex()) { // If this is the purchase in question, // remember it's position in the list // and, if the owner has the required // change, it can stay put, otherwise, // not it was seen & process it later. if (transaction == purchase) { from = index if (test.missing(change. toList()).size == 0) { test.earn(pays.toList()) test.spend(change.toList()) } else seen = true // Otherwise, we have some other // transaction so if the owner has the // required change, it can stay put. } else if (test.missing(transaction.change. toList()).size == 0) { test.earn(transaction.pays.toList()) test.spend(transaction.change.toList()) // Otherwise, it is likely this transaction // needs our purchase in question so, if // it has been seen and the owner now has // the required change, it must move here. // Update our owner money to reflect this. // If the owner now has the required // change, note the purchase has been // moved to this spot and process the // current transaction. Otherwise, we // have a circular reference so abort. } else if (seen && test.missing( change.toList()).size == 0) { test.earn(pays.toList()) test.spend(change.toList()) if (test.missing(transaction.change. toList()).size == 0) { seen = false to = index test.earn(transaction.pays.toList()) test.spend(transaction.change. toList()) } else { result = false break } // if // Otherwise, something is very wrong // so abort. } else { result = false break } // if } // for // If we are good and we have valid indexes // for our move, move the purchase. if (result && from > -1 && to > 0) { Purchase.purchases.add(to-1, Purchase.purchases.removeAt(from)) // Otherwise, if we didn't find a spot to // move to and, if the owner has the required // change now, move the purchase to the // end of our list, otherwise, abort. } else if (seen) { if (test.missing(change. toList()).size == 0) Purchase.purchases.add( Purchase.purchases.removeAt(from)) else result = false } // if return result } // verify // We can only use money of a customer that // has managed to pay for their purchase so // default to being successful, look up the // purchase transaction for our customer, // and, if not found, fail. var failed = false val purchase = Purchase.purchases.find { it.identifier == other.identifier } if (purchase == null) failed = true // Otherwise, see if we can exchange the // money used for the purchase. If so, // perform the exchange. else if (purchase.pays.toList().find { it.bill == bill*amount && it.amount >= 1 } != null) { // Create a list of the bigger bill and // remove it from both the purchase payment // & owner putting it back in the customer's // money. var list = listOf(Money(bill*amount, 1)) purchase.pays.spend(list) Owner.instance.spend(list) other.earn(list) // Create a list of the smaller bill and // remove it from the customer putting it // back in both the purchase payment & // owner's money. list = listOf(Money(bill, amount)) other.spend(list) purchase.pays.earn(list) Owner.instance.earn(list) // Otherwise, see if the owner currently // holds it. If so, perform the exchange. } else if (Owner.instance.toList(). find { it.bill == bill*amount && it.amount >= 1} != null && verify(purchase)) { // Create a list of the bigger bill and // remove it from the owner putting it // back in both the purchase change & // customer's money. var list = listOf(Money(bill*amount, 1)) Owner.instance.spend(list) purchase.change.earn(list) other.earn(list) // Create a list of the smaller bill and // remove it from the customer putting it // back in both the purchase payment & // owner's money. list = listOf(Money(bill, amount)) other.spend(list) purchase.pays.earn(list) Owner.instance.earn(list) // Otherwise, we can't fix it so fail. } else failed = true return failed } // exchange // Get the list of bill denominations and // generate a conversion table. Each bill // is paired with the number that is required // to equal the next higher bill. val bills = Cash.denominations() val conversion = List(bills.size) { Pair(bills[it], if (it == 0) 0 else bills[it-1]/bills[it]) } // Default to unable to fix the customers that // could not be given their change. For each // customer, stopping once one has been fixed // and skipping the ones that have already // completed their purchase, find one we can // fix. var result = false for (customer in Customer.customers) // If this customer could not be processed, // figure out why. if (customer.purchase > 0) { // Figure out how much the customer would // pay, how much change would be needed // for that payment to work, and what // doesn't currently exist. Now we just // need to figure out where to find it. val credit = Cash(customer.bills( customer.purchase, false)) val refund = Cash(credit.funds()- customer.purchase) val needed = Cash(Owner.instance.missing( refund.toList())) // Default the customer to suceed and for // each bill & amount we need find some // customer to get them from. var failed = false for (money in needed.toList()) { // Find the conversion we need for this // bill and a customer that can perform // it for us. Note: we only convert // 5*2 for 10*1 NOT 5*1 1*5 for 10*1. val (bill, amount) = conversion.first { val (bill, amount) = it bill == money.bill } val other = Customer.customers.find { val money = it.toList().find { m -> m.bill == bill } money != null && money.amount >= amount } // If we failed to find a customer that // we can exchange with, note this // customer failed. if (other == null) failed = true // Otherwise, we can perform the exchange // so do it and note that this customer // failed, when the exchange failed. else if (exchange(bill, amount, other)) failed = true } // for // If we didn't fail, we should have one // customer that can be completed so // get out of here. if (!failed) { result = true break } // if } // if // Return true if we fixed a customer so it // can be processed now. return result } // fix // Display our initial owner and customer // information. While we still have customers // that haven't paid their bill, process them. println(Owner.instance) Customer.print() println() while (spent > 0) { // Default to no transactions found. For each // customer, if they haven't paid as yet, try // to make them pay. If we suceed, we have // found a new transaction. var found = false for (customer in Customer.customers) if (customer.purchase > 0) found = check(customer) || found // If we didn't find any new transactions, // try fixing things so we will. If we failed, // give up. if (!found && !fix()) break } // while // If we failed, display the customers that can // not be handled. if (spent > 0) { print("Can not give change to the "+ "following customers:") for (customer in Customer.customers) if (customer.purchase > 0) print(" ${customer.identifier}") println() println() } // if // Display our transactions and our final // information for our owner and customers. Purchase.print() println() println(Owner.instance) Customer.print() } // process // Main function to read the transactions from the // user and verify they are valid. Any error will // cause the data to be tossed in favor of the // default test case. fun main(args: Array) { // Function to convert a list of integer pairs // into the equivant list of money. Default // to an empty list and increment through the // pairs adding them as the bill held and the // amount of those bills. fun convert(list: List): List { val result = MutableList(0) { Money(0, 0) } for (index in list.indices step 2) result.add(Money(list[index], list[index+1])) return result.toList() } // convert // Function to read the user data. Any failure // will cause an exception. fun readData() { // Default the count of data to zero and, while // there is more data to process, process the // next line. var count = 0 while (true) { // Read the next line and, if there wasn't // one or it was empty, exit the loop. val input = readLine() ?: break if (input.length == 0) break // If the count is zero, this is the owner // line so process it. Form a list spliting // on the spaces. Form a second nested list // spliting on the asterisk, converting to // integers, and flatten it. If the second // list has twice the elements as the first, // the data was correctly entered as pairs. // If incorrectly entered, throw an exception. // Otherwise, convert the list of integers // into a money one to add to the owner. if (count == 0) { val data = input.split(" ") val money = data.map { it.split("*").map { it.toInt() } }.flatten() if (data.size*2 != money.size) throw IllegalArgumentException( "owner money pairs") Owner.instance.earn(convert(money)) // Otherwise, this is a new customer line. // Create the customer. Form a list spliting // on the spaces. Form a second nested list // spliting on the asterisk, converting to // integers, and flatten it. If the second // list has the purchase price without a // pair and twice the elements as the first // for the rest of them, the data was // correctly entered as pairs. If incorrectly // entered, throw an exception. Otherwise, // store the purchase, remove it from the // list of integers, convert the rest of the // list of integers into a money one to add // to the customer, and verify the funds are // sufficent to pay for the purchases. If // insufficent, throw an exception. } else { val customer = Customer() val data = input.split(" ") val money = data.map { it.split("*").map { it.toInt() } }.flatten() if (data.size*2-1 != money.size) throw IllegalArgumentException( "customer $count money pairs") customer.purchase = money[0] customer.earn( convert(money-money[0])) if (!customer.verify()) throw IllegalArgumentException( "customer $count insufficent funds") } // if // Increment the count of lines successfully // processed. count++ } //while // If we failed to get at least an owner line // and customer line, throw an exception. if (count < 2) throw IllegalArgumentException( "missing ${2-count} data lines") } // readData // Function to replace any partial user data // with the default test case. fun default() { // Create a list of the owner's money pairs, // convert to a money list, and give it to // the owner. var money = listOf(200, 5, 100, 2, 50, 3, 10, 2, 5, 3, 1, 3) Owner.instance.earn(convert(money)) // Clear any user entered customers. Create // the first customer, it's list of money // pairs with leading purchases, and give // them to the customer. The first list // element is stored in the purchase property. // The rest are converted to a money list to // be given to the customer. Customer.clear() var customer = Customer() money = listOf(121, 200, 1) customer.purchase = money[0] customer.earn(convert(money-money[0])) // Repeat for the second customer. customer = Customer() money = listOf(45, 50, 1, 5, 2, 1, 6) customer.purchase = money[0] customer.earn(convert(money-money[0])) } // default // Try reading the user's transactions throwing // an exception on any error. try { readData() // On exception, complain including a reason before // setting up the defaults. } catch(error: Throwable) { val reason = when (error) { is java.lang.NumberFormatException -> "non-integer" else -> error.message } // when println("Bad inputs (${reason}) using defaults!") default() // In either case, process the data. } finally { process() } // try } // main

change ch