Tuesday, May 30, 2006

Ah, Memorial Day weekend: backyard barbeques, warm weather, and hacking. This longish post is dedicated to Leah, our youngest child who was home visiting from college this last weekend, along with her boyfriend Zanky. Late last Saturday night, they were playing a math game called 24 that we got a number of years ago. It's simple: there's a deck of cards, each with four numbers. You have to figure out how to make 24 by using each number exactly once, in any order, with any of the basic mathematical operators of addition, subtraction, multiplication, and division. For example, given the four numbers [1, 5, 3, 7], you can do the following: (1 + 5) is 6, (7 - 3) is 4, 6 * 4 is 24: you win.

Each card is rated as easy, medium, or hard, and they had spent a long time trying to solve a hard one, with no success: [7, 8, 9, 2]. Donna and i chewed on it for quite a while too (donna came up with the solution first: there's a hint at the bottom if you need it, and i'll feel smarter if you do!). But before that point, i had already taken the usual geek detour: i could write a program to do this! I met Leah's objection of "where's the satisfaction in that?" with "it all depends on what you find satisfying!"

It's an interesting little problem. Given four numbers, there are 24 different ways to order them (4 * 3 * 2 * 1). Given one of those sequences, you have to define the different possible orders of operation, because ((4 / 2) * 3) is different than (4 / (2 * 3)). For any four items [a, b, c, d], they can be ordered in these four ways:

(((a b) c) d)

((a (b c)) d)

(a (b (c d)))

((a b) (c d))

Lastly, for one of these groupings, there are three places where an operator can be inserted, and four possible operators (+ - * /), making 4 * 4 * 4 or 64 possible ways to evaluate a grouping. Putting it all together: 24 sequences * 4 groupings * 64 operator insertions, means a total of 6144 ways to combine the four numbers.

Since i mostly program in Perl these days, i started out that way, but after a couple of hours, i'd run aground on the complexity of representing lists of lists in Perl: it seems i have to re-learn how they work every time i use them. Ah for the good old days, when, as a young programmer at an AI company, i spent many happy hours balancing parens in Lisp! Lisp is a perfect match for this kind of programming problem: you have an interpreter to try out expressions, you can build your program incrementally by creating one function at a time and composing them, and Lisp expressions can be both data and code, e.g. (* 2 3). But despite all the benefits, we had to give up Lisp programming a decade ago, for the simple reason that we delivered code to our customers, who didn't have Lisp programmers. It's not that they could have understood or modified our code anyway: but with Lisp, they knew they couldn't, and that simply wasn't acceptable. So gradually C++ and Java took over, and Lisp usage faded away. I haven't had a machine with Lisp since the 90s.

These days, though, Lisp is experiencing a bit of a renaissance, largely because the world is moving toward web services, and behind a web server, nobody knows or cares what language you're running. I had recently learned that the good folks at Franz provide a trial edition of their Allegro Common Lisp software: so i downloaded the copy, and even though it's been several years, most of it came back pretty quickly (with a few online checks to a version of Common Lisp the Language).

I wound up with a handful of functions for generating sequence permutations, grouping then into the binary branching structure above, and inserting the various operators. Then one master function simply generates all the possible sequences and evaluates them all one by one, printing out any that equal 24 (and trapping some that produce division by zero errors). Of course, this brute-force search approach is far from optimal: for example, you wind up evaluating the same numeric sequences several times. But it only takes a few seconds on my laptop, so there's no real benefit to further optimization. You can find the code here. I wouldn't score too many points for code elegance, but hey, it's been a while.

All in all, a fun Memorial Day hack, a happy trip down S-expression Lane, and hopefully i've re-established my claim (at least in my daughter's eyes) to the title of Smartest Dad Ever.

[Hint for the problem above: see if you can make 32 along the way.]

11:24:17 PM #  Click here to send an email to the editor of this weblog.  comment []  trackback []