« Another wilfully obscure post | Main | 30 days in 30 seconds »
February 26, 2006
A really quite involved example of a particular kind of laziness
I’ve been spending some of my time working my head around the programming language Haskell, using Paul Hudak’s The Haskell School of Expression book as a guide. It’s going quite well, and I’m working my way through the exercises fairly successfully, and really the only thing slowing me down is not making enough time to spend on it.
I always find though, when I’m getting my head around a new programming language - which isn’t something I try often, by the way, it’s just something I do to feed my pet fantasy that I could become self-employed via my programming skills but that I’ll need a super-effective language to do it with - but when I’m wrapping my head around a new language and amn’t feeling too lazy about it, I try to do the programming exercises. I get them perhaps 90% of the time, but there’s always one or two that don’t necessarily depend on your knowledge of the language, but instead rely on your knowing something entirely separate, like a particular mathematical formula, or some scientific nugget about physics. I suppose the point is that you go look that stuff up and work out how to express it in the programming language du jour. But sometimes it’s just obscure stuff you have to think about to work out, and I don’t know about you, but I find serious, patient thinking hard to maintain once thirty seconds have gone by. I need to be genuinely interested in what I’m thinking about, and far more often than not, these programming exercises aren’t that interesting. They can’t be; if they were, you might miss the technique you’re supposed to be hammering into your tired brain.
One classic example is this: Out of nowhere, you’re suddenly working in a shop, and you’re in the middle of serving a customer. This lovely customer (let’s call her Gertrude) has given you too much money for the goods she’s buying off of you, and so you have to give her change. But wait! What kind of change do you have, and how do you work things out so that you give Gertrude the lowest number of coins possible - don’t go giving her 53 pennies now!
Okay, for a human, this is not so tough. But trying to get the essence of the problem expressed in a programming language is a bit trickier. You have to derive an algorithm that, when given an amount owed and a list of coins available (fifty-cent pieces, twenty-cent pieces, etc.) will tell you how many of each kind of coin to give back.
The standard solution is that you pay with the largest coins first, until you have to move to the next largest coin, and so on. So if you’re owed 97 cents and you have fifty-cent, ten-cent and one-cent pieces on hand, you give back one fifty, four tens and seven one cent pieces. Although in that situation I’d probably check with the customer first to see if they had three cents, but I don’t think my programming textbook allows for that kind of thinking.
The optimal change problem a fairly common problem in programming textbooks for many different languages, and it’s quite satisfying to work out that the Haskell solution takes two lines, while a C++ solution could take 20 or more (at a guess). Assuming brevity of expression - without sacrificing clarity of expression - is a desirable trait in a programming language (for me it definitely is), Haskell seems well worth knowing.
But then, the twist. The 10% of problems I never manage to answer, whether due to boredom or impatience or because the solution requires some mathematical understanding I’ve no interest in pursuing. Like many programming books, The Haskell School of Expression has a website that includes, along with the usual software downloads, a list of errata. Mistakes made in the text. One of these is actually a footnote to the above problem, pointing out that the “obvious” solution isn’t necessarily the “optimal” one. What if, for example, you live in some manner of crazy universe where they have three cent pieces? You owe them six cents, and you have four-cent pieces, three-cent pieces, and one-cent pieces. Use the scheme described above, and you give them one four-cent piece and two one-cent piece. But the better solution would be to give them two three-cent pieces - that way they get fewer coins. So the solution above isn’t optimal.
What is? I don’t know. But it’s going to bug me until I work it out (cursory googling reveals nothing). Or until I forget about it. It’s at that point where I don’t quite care enough to justify thinking about it deeply.
There’s a certain class of person out there who might suggest that I’d have a solution by now if I spent the time writing this on thinking about it. Well, duh. Writing about not knowing is more fun, and easier, than thinking hard about it, see? Damn my lazy, easily-bored hide.
Posted by Oliver at February 26, 2006 12:27 PM
Comments
Hey Oliver, don’t know you directly but got here through Graham’s travel blog. Anyway, just browsing and decided to add my 2 cents to this post (yes that was an intentional pun). This “minimum number of coins to make a certain amount” actually sounds like a variation on the classical bin packing problem: http://en.wikipedia.org/wiki/Binpackingproblem. In other words, an optimal algorithm is going to really hard to find. “Good enough” is the way to go :)
Posted by: cian at March 10, 2006 12:01 PM
“Good enough” wins again!
Posted by: Oliver at March 30, 2006 06:01 PM
Post a comment
AWVC uses the Markdown formatting system, a very simple way to format your comments. Whitespace is converted directly. Enclose a phrase with asterisks to italicise, and two asterisks (**) to embolden. A good introduction to the Markdown format is available here.
Cleverly, though, the preview is basically useless (it will just show what you've typed). If you want a real preview, enter your text into the Markdown Dingus, then re-enter it here.