Coin change problem with change – Dijkstra’s Algorithm

The coin change problem is a well studied problem in Computer Science, and is a popular example given for teaching students Dynamic Programming. The problem is simple – given an amount and a set of coins, what is the minimum number of coins that can be used to pay that amount?

So, for example, if we have coins for 1,2,5,10,20,50,100 (like we do now in India), the easiest way to pay Rs. 11 is by using two coins – 10 and 1. If you have to pay Rs. 16, you can break it up as 10+5+1 and pay it using three coins.

The problem with the traditional formulation of the coin change problem is that it doesn’t involve “change” – the payer is not allowed to take back coins from the payee. So, for example, if you’ve to pay Rs. 99, you need to use 6 coins (50+20+20+5+2+2). On the other hand, if change is allowed, Rs. 99 can be paid using just 2 coins – pay Rs. 100 and get back Re. 1.

So how do you determine the way to pay using fewest coins when change is allowed? In other words, what happens to the coin change problems when negative coins can be used? (Paying 100 and getting back 1 is the same as paying 100 and (-1) ) .

Unfortunately, dynamic programming doesn’t work in this case, since we cannot process in a linear order. For example, the optimal way to pay 9 rupees when negatives are allowed is to break it up as (+10,-1), and calculating from 0 onwards (as we do in the DP) is not efficient.

For this reason, I’ve used an implementation of Dijkstra’s algorithm to determine the minimum number of coins to be used to pay any amount when cash back is allowed. Each amount is a node in the graph, with an edge between two amounts if the difference in amounts can be paid using a single coin. So there is an edge between 1 and 11 because the difference (10) can be paid using a single coin. Since cash back is allowed, the graph need not be directed.

So all we need to do to determine the way to pay each amount most optimally is to run Dijkstra’s algorithm starting from 0. The breadth first search has¬†complexity $latex¬†O(M^2 n)$ where M is the maximum amount we want to pay, while n is the number of coins.

I’ve implemented this algorithm using R, and the code can be found here. I’ve also used the algorithm to compute the number of coins to be used to pay all numbers between 1 and 10000 under different scenarios, and the results of that can be found here.

You can feel free to use this algorithm or code or results in any of your work, but make sure you provide appropriate credit!

PS: I’ve used “coin” here in a generic sense, in that it can mean “note” as well.

Pizza from dominos – good and bad

Last night we decided we wanted pizza from dominos for dinner. Having been used to Swiggy, I instinctively googled for dominos and tried to place the order online.

There is one major fuckup with the dominos website – it asks you to pick the retail outlet closest to you, rather than taking your location and picking it yourself. And so it happened that we picked an outlet not closest to us.

I quickly got a call from the guy at the outlet where my order had gone, expressing his inability to deliver it, and saying he’ll cancel my order. I gave him a mouthful – it’s 2016, and why couldn’t he have simply transferred the order to the outlet that is supposed to service me?

I was considering cancelling the order and not ordering again (a self-injurious move, since we wanted Dominos pizza, not just pizza), when the guy from the outlet in whose coverage area I fell called. He explained the situation once again, saying my original order was to be cancelled, and he would have to take a new order.

Again – it wasn’t just a fuckup in the payment in the Dominos system, in which case they could’ve simply transferred my order to this new guy. So I had to repeat my entire order once again to this guy (not so much of a problem since I was only getting one pizza) and my address as well (it’s a long address which I prefer filling online).

Then there was the small matter of payment – one reason I’d ordered online was that I could pay electronically (I used PayTM). When I asked him if I could pay online for the new order he said I had to repeat the entire process of online ordering – there was no order ID against which I could simply logon and pay.

I played my trump card at this time – asked him to make sure the delivery guy had change for Rs. 2000 (I’d lined up at a bank 2 weeks back and withdrawn a month’s worth of cash, only that it was all in Rs. 2000 notes). He instantly agreed. Half an hour later, the pizza, along with change for Rs. 2000 was at my door.

The good thing about the experience was that the delivery process was smooth, and more importantly, the outlet where my order reached had taken initiative in communicating it to the outlet under whose coverage my house fell – the salespersons weren’t willing to take a chance to miss a sale that had fallen at their door.

The bad thing is that Jubilant Foodworks’ technology sucks, big time. Thanks to the heavily funded and highly unprofitable startups we usually order from, we’re used to a high level of technology from the food delivery kind of businesses. Given that Jubilant is a highly profitable company it shouldn’t be too hard for them to license the software of one of these new so-called “foodtech” companies to further enhance the experience.

No clue why they haven’t done it yet!

PS: I realise I’ve written this blogpost in the style I used to write in over a decade ago. Some habits die hard.