A Pocketful of Self-Checkout Change

There are a lot of things wrong with self-checkout machines. They are every bit as unpleasant as a vending machine. They are confrontational (“Item removed from bagging area!”). The speed and volume of the recorded speech is calibrated for the mildly retarded and partially deaf. Feeding them bills and coins is a frustratingly slow process. They don’t offer advice or tell you what’s on sale. They deprive you of a reasonable and pleasant human interaction that might ordinarily benefit both parties.

By far the most annoying feature of self-checkout machines is the change mechanism. I would like to meet the engineers who designed these things. Almost all human cashiers will dispense change in a way that maximizes the coins of highest value and thereby minimizes the total number of coins. This is called a “greedy algorithm” and it works because the denominations of US currency were well-chosen.¹

The machine at CVS was dispensing 2–3 nickels at a time, which will never result in a minimum coin count. Perhaps, I figured, the machine was using a different but still customer-friendly algorithm: minimizing the total weight of the change. How would that work? Using weights published on the US Mint Web site, I wrote a couple of quick Python scripts to help me understand the difference between the minimized-count and minimized-weight approaches. It turns out that for values between 30–34, 40–44, 55–70, 80–84, and 90–94 cents, they do differ. But the improvement comes from higher numbers of dimes, which are the lightest of the coins. In neither case will an optimum coin distribution contain more than 1 nickel.

This self-checkout change dispenser is controlled by some other approach. But what? Maximizing the time between refilling the machine with coins? Further study is required. But it’s clear to me that these machines are not working with my interests in mind. When you relinquish a perfectly reasonable job to a computer, I suppose one should expect no sympathy from the machine.

A 2003 paper by Jeffrey Shallit points out that Americans could make change with, on average, 17% fewer coins by replacing the dime with a 18-cent coin. ↩︎

shazam (May 13, 2012)

Here’s one for you: at Gatwick airport, the W.H. Smith store has self-checkout machines which ask you to scan your boarding pass (or “boarding card” for you Brits) in order to complete a transaction. Of course, when I realize this, I call the attendant over and ask her in disbelief if this is really true. “Oh, I’ll take care of that,” she says, and swipes a card, presses a few touchscreen buttons, and expertly overrides a series of annoying options that must cause problems constantly. A pain for employees as well as customers! No one but NCR (or whoever manufactures these contraptions) is benefitting from this.
Foonyor (May 16, 2012)

As for the denominations, the USA is unusual in not using the more widespread 0.01/0.02/0.05/0.10/0.20/0.50/1/2/5/10/20/50/100/200/500 system. As you didn’t make your coin-counting script open source, I had to write my own version to determine that the US denominations use on average 4.74 coins for values between 0.01 and 1, compared to 3.42 for the GB/EU system.

Then again, the most sensible approach of all is to round everything to the nearest 0.05, like in Finland, Canada, etc.

Am: I think the boarding card thing is about the tax amount depending on whether you’re leaving the EU or something like that? How come you didn’t want to scan yours?
Scott (May 17, 2012)

True, but you have so many different types of coins!

I suppose I should have posted my code. I didn’t imagine anyone would want to see it!
Foonyor (May 17, 2012)

That’s true, after writing it I realized that of course it’s an unfair comparison because there are different numbers of coins. I suppose you could represent each as the proportion of the minimum for a given number of coins. The article you linked has conveniently calculated these minima, showing the USA uses 122% of the minimum for a 4 coin system, and the GB/EU uses 117%.
shazam (May 18, 2012)

I didn’t want to scan it because doing so would have required setting down the magazine I wished to purchase, slogging upstairs to get my boarding card from its place in my backpack (which was sitting with Paul), and then coming back down and doing the whole thing again.

The magazine had been an afterthought: the expedition was to find a water fountain (which was hidden in the small bathroom behind the massive duty-free shop) and fill our two water bottles for the journey. Even though the UK does have water fountains, it seems to have done everything possible at Gatwick to make them unfindable so that you purchase water bottles at a pound a pop. I had gotten the intel on the water fountain from the info desk, where the woman told me “I think they still have one in the restroom that’s downstairs behind the duty-free, but I don’t know for sure.” Clearly there used to be more!

Gatwick was otherwise a nice airport, and certainly very easy to get to from where we were.