This particular article explored how to generate arithmetic expressions using a card game as a basis for discussion. It appeared in August 2010, and came about because of me reading two blog posts on entirely different topics within a week or so of each other. The combination triggered an Ah ha! moment, and I wrote it up. The first was for a card game called Krypto and appeared on The Daily WTF; the second was about generating all binary trees of a particular size and appeared on Eric Lippert’s blog, Fabulous Adventures in Coding.
In essence, for the card game you strip out all the court cards and jokers, shuffle the remainder and deal out five cards plus one to the side. The object of the game is to think of an arithmetic expression that links the values of the five cards (in the original sequence, mind) to equal the value of the sixth. You can use the four normal operators in any combination plus as many parentheses as you need. It’s not a bad game to exercise your arithmetic abilities and can be quite difficult for certain combinations of cards. Where enumerating all binary trees come in is to try and write a computer program to list out all possible expressions that satisfy the card layout.
In the article, I used Reverse Polish Notation (RPN) because it’s a damn sight easier than infix notation, and I glibly tossed off an assertion saying it’s easy to convert from RPN to infix. I then wrote a blog post about how easy it was, only to be brought up short, because it damn well isn’t. Sigh.
This article first appeared in issue 297, August 2010.
You can read the PDF here.
(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)
Ace - How Long?
(from Groove Armada’s Late Night Tales)