« January 2006 | Main | March 2006 »
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 12:27 PM | Comments (2)
February 05, 2006
Another wilfully obscure post
Last Thursday week I stood in a boardroom of the German Department of Education in Berlin, and delivered a presentation - my first - to a room full of largely non-native English speakers. I didn’t do too badly (at least, my boss was kind enough to say I did quite well). More than anything it was a relief to get something done that I’d been dreading all week.
I have this odd memory of when I was being inculcated as an altar boy. Myself and the other inculcatees (I’m happy making up words now) were laughing non-stop at one particular guy who loved the attention and couldn’t keep his mouth shut no matter how patiently the priest hushed him. That said, there were two or three of us who pointedly wouldn’t laugh at anything he said, instead acting all grown-up and un-amused. I was laughing along most of the time, though I’d keep seeing them not laughing and wanting to be serious like they were. I wanted to be like the altar boy geeks!
Now the demands of this job that I sort of wandered into are changing me into the ideal required for this job. In the meantime whatever it is in me that I’d like to think would resist such gerry-mandering currently seems okay with both the gerrying and the mandering, let alone the combination. I don’t think this is quite what I thought I’d be like when I was all done growing up. Then again, blow slightly too much air into a balloon and it pops, right? So my hope that I’ll stay true to some core of myself seems largely based on a metaphor I stole from House. Hmmm.
After the presentation I got to go back to Berlin’s Jewish Museum. Fallen Leaves is still great.
Posted by Oliver at 01:22 AM | Comments (0)