Sun, 10 Dec 2006

FourFours in Common Lisp

I came across the FourFours problem recently. Stated succinctly, it asks: what are the ways to calculate each of the integers from 1 to 100 with formulas which use the digit four exactly four times? (No digits other than four can be used at all.)

People have solved it in C# (138 lines, 380ms), Python (119 lines, 20s), Haskell (73 lines, 900ms), and Perl (one (really long) line, 45s). I thought it would be interesting to try it in Common Lisp, so I did.

For one thing, I found that my code was slower than the C# and Haskell solutions; I consistently get about 2.5 seconds for my solution. That seems mostly to be a result of both the dynamic nature of Lisp and the particularly-dynamic approach I took (more on that in a bit). I also took more lines (148 significant lines; excludes comments, doc strings, empty lines, and a couple of ancillary definitions).

In my defense, I did things somewhat more generally than the others; I don't like hardcoded data, so my code generates a lot of stuff on the fly. One notable example is the ordering of operations on the four values: the other solutions I've seen all hardcode the orderings, but my code generates the code structure (just a binary tree) at runtime based on the number of elements. I then use the code/data duality of Lisp to generate both functions and the printed representation of the operations from those trees. Likewise, my code will figure out the possible values to use in the calculations from a supplied digit.

All that flexibility let me play around a lot more with the structure of the problem. Although everyone else used five operations (addition, subtraction, multiplication, division, and exponentiation), I found that only four were necessary (addition, subtraction, multiplication, and division). (I checked smaller numbers of operations, too. I considered all of the functions in Common Lisp that would return ratios or integers when given a pair of ratios or integers as parameters. I was unable to get all the way from 1 to 100 with fewer than four distinct functions.)

With the given parameters (four fours, with 4, 4!, sqrt(4), .4, .4bar, and sqrt(.4bar)) and operators (+, -, *, /), you can actually go all the way up to 102. (Adding exponentiation does not allow you to go any further.)

I can calculate the consecutive chains for arbitrary base digits:

1: 1

1: 2 / 2

1: 3! / (3 + 3)
2: (3 + 3) / 3
3: (3 + 3) - 3
4: 3 + (3 / 3)
5: (3! / 3) + 3
6: (3 * 3) - 3
7: 3! + (3 / 3)
8: 3! + (3! / 3)
9: 3 + (3 + 3)
10: (3! - 3) / .3
11: (.3 + 3) / .3
12: 3 + (3 * 3)
13: (3 / .3) + 3
14: (3! / .3) - 3!
15: 3! + (3 * 3)
16: (3 / .3) + 3!
17: (3! / .3) - 3
18: 3 * (3 + 3)
19: (3! - .3) / .3
20: (3 + 3) / .3
21: (3! * 3) + 3

1: (4 + 4) / (4 + 4)
2: (4 * 4) / (4 + 4)
3: (4 + (4 + 4)) / 4
4: 4 + (4 * (4 - 4))
5: (4 + (4 * 4)) / 4
6: 4 + ((4 + 4) / 4)
7: (4 + 4) - (4 / 4)
8: (4 + (4 + 4)) - 4
9: (4 / 4) + (4 + 4)
10: (4! + (4 * 4)) / 4
11: ((4! + 4) / 4) + 4
12: 4 * (4 - (4 / 4))
13: (4! + (4! + 4)) / 4
14: (4! / 4) + (4 + 4)
15: (4 * 4) - (4 / 4)
16: 4 + (4 + (4 + 4))
17: (4 / 4) + (4 * 4)
18: ((4! * 4) - 4!) / 4
19: 4! - (4 + (4 / 4))
20: 4 * (4 + (4 / 4))
21: (4 / 4) + (4! - 4)
22: 4! - ((4 + 4) / 4)
23: ((4! * 4) - 4) / 4
24: (4 * 4) + (4 + 4)
25: ((4! * 4) + 4) / 4
26: 4! + ((4 + 4) / 4)
27: (4! + 4) - (4 / 4)
28: (4 * (4 + 4)) - 4
29: (4 / 4) + (4! + 4)
30: (4! + (4! * 4)) / 4
31: 4! + ((4! + 4) / 4)
32: (4 * 4) + (4 * 4)
33: ((4 - .4) / .4) + 4!
34: (4! / 4) + (4! + 4)
35: ((4 / .4) + 4) / .4
36: 4 + (4 * (4 + 4))
37: ((.4 + 4!) / .4) - 4!
38: (4 / .4) + (4! + 4)
39: 4! + (4! / (.4 * 4))
40: (4 * (4 * 4)) - 4!
41: (.4 + (4 * 4)) / .4
42: (4! + 4!) - (4! / 4)
43: (4! + 4!) - (sqrt(4) / .4)
44: (4 * 4) + (4! + 4)
45: (4! - (4! / 4)) / .4
46: ((4! - 4) / .4) - 4
47: (4! + 4!) - (4 / 4)
48: 4 * (4 + (4 + 4))
49: (4 / 4) + (4! + 4!)
50: (4 + (4 * 4)) / .4
51: ((.4 + 4!) - 4) / .4
52: (4! / .4) - (4 + 4)
53: (sqrt(4) / .4) + (4! + 4!)
54: (4! / 4) + (4! + 4!)
55: ((4! - .4) / .4) - 4
56: 4! + (4 * (4 + 4))
57: ((.4 + 4!) / .4) - 4
58: (4 / .4) + (4! + 4!)
59: (4! / .4) - (4 / 4)
60: (4 * (4 * 4)) - 4
61: (4! / .4) + (4 / 4)
62: (4 * (4 * 4)) - sqrt(4)
63: ((4! - .4) / .4) + 4
64: (4 + 4) * (4 + 4)
65: ((.4 + 4!) / .4) + 4
66: ((4! + 4) / .4) - 4
67: ((4! + 4) / .4bar) + 4
68: 4 + (4 * (4 * 4))
69: ((4! + 4) - .4) / .4
70: (4! / .4) + (4 / .4)
71: (.4 + (4! + 4)) / .4
72: 4! * (4 - (4 / 4))
73: (sqrt(.4bar) + (4! + 4!)) / sqrt(.4bar)
74: ((4! + 4) / .4) + 4
75: (4! + (4! / 4)) / .4
76: ((4! - 4) * 4) - 4
77: ((4! - .4bar) / .4bar) + 4!
78: ((4! - 4) * 4) - sqrt(4)
79: ((4! - sqrt(4)) / .4) + 4!
80: 4 * (4 + (4 * 4))
81: ((4! / .4) - 4!) / .4bar
82: sqrt(4) + ((4! - 4) * 4)
83: ((4! - .4) / .4) + 4!
84: ((4! - 4) * 4) + 4
85: ((4 / .4) + 4!) / .4
86: (4! * 4) - (4 / .4)
87: (4! * 4) - (4 / .4bar)
88: (4! * 4) - (4 + 4)
89: ((sqrt(4) + 4!) / .4) + 4!
90: (4! * 4) - (4! / 4)
91: (4! * 4) - (sqrt(4) / .4)
92: (4! - (4 / 4)) * 4
93: (4! * 4) - (sqrt(4) / sqrt(.4bar))
94: ((4! + 4) / .4) + 4!
95: (4! * 4) - (4 / 4)
96: 4! * ((4 + 4) - 4)
97: (4 / 4) + (4! * 4)
98: .4 + ((.4 + 4!) * 4)
99: ((4! + 4!) - 4) / .4bar
100: (4! + (4 / 4)) * 4
101: (sqrt(4) / .4) + (4! * 4)
102: (4! / 4) + (4! * 4)

1: 5 / (5 + (5 * (5 - 5)))
2: ((5 + (5 + 5)) - 5) / 5
3: (5 + (5 * 5)) / (5 + 5)
4: (5 + (5 + (5 + 5))) / 5
5: (5 + (5 + 5)) - (5 + 5)
⋮
154: (5! / 5) + (5! + (5 + 5))
155: 5 + (5 * (5 + (5 * 5)))
156: (5! + (5! * (.5 + 5))) / 5
157: (5 / (.5bar * (.5bar - .5))) - 5
158: (((5! / 5) - 5) / .5) + 5!

1: (6 + (6 + 6)) / (6 + (6 + 6))
2: (6 + (6 + (6 + 6))) / (6 + 6)
3: ((6 + (6 + (6 + 6))) - 6) / 6
4: (6 * (6 + 6)) / (6 + (6 + 6))
5: (6 + (6 + (6 + (6 + 6)))) / 6
6: 6 + (6 * ((6 + 6) - (6 + 6)))
⋮
881: 6! + (((.6bar * (6! + 6!)) + 6) / 6)
882: ((6! / 6) + 6) * (6 + (6 / 6))
883: ((.6bar + (6! / (.6bar + 6))) / .6bar) + 6!
884: (6! / (.6 * 6)) + (6! - (6 * 6))
885: (.6 * ((6 * 6) + (6! + 6!))) - .6
886: ((6! / (6 - .6)) * (.6 + 6)) + 6

I'll probably experiment with solutions that involve concatenation of digits next. That'll involve some fairly significant code changes, though. And I'll probably just end up duplicating the work of the definitive Four Fours answer key.

Tue, 31 Oct 2006

Delphi Naming Non-Conventions

It often happens in programming that you need to name two things that are similar but different. This can be a difficult task, but one would expect that if you were designing a language or its standard library you'd put extra effort into your naming. Sadly, it sometimes seems that the people designing Delphi didn't put in that effort. For a simple example, consider division by zero. If you try to divide by zero, Delphi generates an exception at runtime, but if you were doing an integer divide the exception is EDivByZero, whereas floating-point division generates EZeroDivide.

For a more extreme example, let's look at String comparisons. Delphi has functions for native Delphi strings and C-style null-terminated strings, functions for case-sensitive and case-insensitive comparison, functions that understand multibyte character coding systems and use Windows locale info and functions that don't, and some null-terminated functions that also take a character count (analogous to strncmp).

Function String Type Multibyte-aware Case-Sensitive Specify Length
= String No Yes No
CompareText String No No No
CompareStr String No Yes No
AnsiCompareText String Yes No No
AnsiCompareStr String Yes Yes No
StrIComp PChar No No No
StrLIComp PChar No No Yes
StrComp PChar No Yes No
StrLComp PChar No Yes Yes
AnsiStrIComp PChar Yes No No
AnsiStrLIComp PChar Yes No Yes
AnsiStrComp PChar Yes Yes No
AnsiStrLComp PChar Yes Yes Yes

Granted, the null-terminated functions are pretty consistent with their Ls and Is, but I can never remember which of CompareStr and CompareText is which (not to mention remembering which names are for null-terminated strings and which are for Delphi strings). And the rule of thumb is to always use the Ansi functions, because they honor locale orderings. Presumably the non-Ansi functions are around because they're faster (they do a straight numeric compare on the ordinal value of each character), but the naming implies that they should be the default.

Another hairy mess of naming I run into moderately often is the task of turning a TDateTime into a string. Should I use DateToStr or TimeToStr, which each take one parameter (the TDateTime variable) and use several global variables to determine their formatting? Should I use FormatDateTime, which takes two parameters: the TDateTime variable and a format string? Should I use DateTimeToStr, which works just like FormatDateTime, but takes a third parameter, a string variable passed by reference, into which the result is placed? (DateToStr, TimeToStr, and FormatDateTime are Delphi functions while DateTimeToStr is a Delphi procedure.)

I consider Format to be Delphi's analog to sprintf, and use it exclusively, but Delphi provides FmtStr, Format, and FormatBuf. Format is a function that returns a formatted Delphi string. FmtStr is a procedure that gets its result variable passed in by reference. FormatBuf is the direct analog to snprintf: you must pass in the result variable and the format string as PChars, as well as the lengths of those two strings; the result is placed into the passed variable and the function returns the length of that string.

StrUpper upcases an entire PChar. AnsiStrUpper does the same, but understands multibyte encodings and honors the Windows locale. UpperCase and AnsiUpperCase are the same, but for Delphi strings. UpCase upcases a single character.

Low gives the lowest value of a range type or the lowest index of an array. Lo gives the low-order byte of an integer. Likewise, High gives the highest value of a range type or the highest index of an array while Hi gives the high-order byte of an integer. (More properly, Hi returns the second-lowest-order byte of an integer; it assumes all integers are 16-bit.)

Trunc takes a floating point number and truncates it to an integer. Truncate deletes all data in a file past the current seek point. I use Trunc just rarely enough that I almost always use Truncate when I mean to use Trunc.

I suppose all languages have similar issues (I'm reminded of Common Lisp with aref, svref, bit, sbit, nth, elt, char, schar, and (I suppose) row-major-aref), but in most other cases, I don't often find myself trying to decide which of several similarly-named functions is the right one and which is wrong. Delphi's setup just feels more muddied to me.

Thu, 22 Jun 2006

Life in Text Mode

I primarily use Unix-based computers, mostly Linux. On those computers, I live in text mode. This entry is an attempt to document the software I find most useful to my text-mode guerrilla lifestyle. Included are links to the programs I rely on, links to alternative programs, and links to my config files.

screen (.screenrc, .screenrc-mithrandir). Simply indispensable. It slices and dices console sessions. Pretty much everything I do, I do in screen. For extensive details, see my ode to screen.

zsh (.zshrc, .zshenv, .zshprompt). My shell of choice. Think of all the good features of bash, ksh, and tcsh rolled together. (Without much of the ickiness, particularly the csh heritage.) Personally, the killer application of zsh was that fact that not only did it have context-sensitive completion but (unlike tcsh) it shipped with hordes of completion definitions right out of the box. Type 'dpkg -L fo<tab>' and zsh will autocomplete on the Debian packages currently installed on your system. With an ssh-agent running, type 'scp otherhost:fo<tab>' and zsh will ssh to the other system and autocomplete on the files available on that host.

irssi (config, theme). The best IRC client I've come across, certainly beating out IrcII, BitchX, and even epic. Multiple windows, extensible, tons of plugins available.

bitlbee. This is actually an IRC-to-Instant-Messaging gateway. It allows me to use AIM, Jabber, and the like from within my preferred chat program, irssi.

snownews. curses-based RSS aggregator. I shopped around a bit before finding an aggregator that I liked. snownews does everything I need.

mutt (.muttrc, config directory). Possibly the best mail client around, GUI or not. While pine is okay (and simpler to use), mutt is much more customizable and scales better to large volumes of email.

procmail (.procmailrc). Slices and dices my email. I have procmail rewriting things so they're easier for me to deal with, sorting my list mail into separate mailboxes (automatically; no need to add new lists by hand), and checking (and dealing with) spam. Essential to my email usage.

Emacs (.emacs). My text editor of choice. Feel free to substitute XEmacs or vi (preferably vim) at your own preference. I prefer emacs to vi, though I know a decent amount of vi, as any sysadmin should. I actually like XEmacs a little better than GNU Emacs, but GNU Emacs has better UTF-8 support.

w3m. Web browser. Among other things, w3m does tabbed browsing, though it's not multithreaded, so you can't read one tab while another is loading. It even has image support; run it with a valid $DISPLAY and it'll render images on the page. There are other text-mode browsers, most notably links. I'm not tremendously familiar with links because w3m fills all of my needs. (My original decision between the two came about because w3m had better HTML support, but I don't believe this is any longer the case.) The grandaddy of text-mode browsers is, of course, lynx, but it's lagged far behind w3m and links in support for newer aspects of HTML.

moosic (config). This is a music jukebox. The features that distinguish it from other such programs are twofold. First, it runs as a standalone server; you interact with it via a command line client. (In theory, a curses or GUI client could be written, but to my knowledge none yet has.) Second, it's customizable with regards to how it plays music. It has a config file where you tell it what programs to use to play various music formats (it does come with reasonable defaults). A program with similar design is mpd. mpd does its own music playing, which allows some advantages over moosic, but moosic has much better playlist management.

mplayer (config). Okay, this is kind of a hedge. I do indeed use it purely in text mode on occasion--it has better support for streaming media (usually mp3s) than any of the actual mp3 players I use. mplayer's main advantage is that it will play pretty much any video format I throw at it. (I'm not quite masochistic enough to watch the videos in aalib, though.)

surfraw (.surfraw.conf). surfraw is a collection of command-line based jumping-points to various web-based information, mostly searches. For a quick google search, I need only go to a command line and type 'sr google my search terms'. (Debian uses a single program, 'sr', as a wrapper for all of the surfraw "elvi". On other systems, you would probably just run 'google your search terms'.)

wget. The swiss-army-knife of grabbing things off the web (and via FTP). I've automated many downloads, some tweaked in interesting ways, with wget.

tdl. Completely command-line todo list manager. Along similar lines is DevTodo; I haven't really played with it because tdl does everything I need. Those two are both command-line based. For more of a todo list editor, you might want to take a look at hnb or woody. (Though, of those two, hnb has better support for todo lists.)

Those are the bigger programs that jump to mind most readily. I use a host of other programs, too. Listed briefly, they are: less (pager), mpg321 (mp3 player), GnuPG (OpenPGP implementation) (options), aumix (volume control), teTeX (TeX implementation), pal (nice colored calendar with a number of features), bc (simple command line calculator), dict (actually a dictionary network protocol but their command-line client is also named 'dict'), mp3gain (normalization of mp3s (ideally should be done non-destructively via ID3v2 but no one supports that)), netcat (connect directly to TCP sockets), BitTornado (bittorrent client; slightly nicer than the standard one), subversion (source revision control; nicer than cvs), abcde (CD ripper) (.abcde.conf), lame (MP3 encoder), nmap (portscanner), hping (packet generator), and tcpdump (packet sniffer).

I do normally run X; it lets me have multiple xterms on the screen at once. For managing those xterms, I run ion (config directory), a tiling window manager.

There are a couple of GUI programs I use regularly. I've already mentioned mplayer; you really need a pixelmapped interface to watch movies. There's also Ethereal, an excellent network sniffer and protocol analyzer (much nicer than plain tcpdump), and GnuCash, one of the best asset management programs I've come across. (But see clacct for straight command line checkbook balancing.) Oh, and Firefox, for those websites that just won't work with w3m.

War of Honor

allconsuming link

It's past five in the morning. I've been up reading for almost the last four hours because I wanted to finish the book. It's good. The pace is much slower than I remember previous Honor Harrington books being, but things do move along.

Reading all of the Honor anthologies before this book is highly recommended.

Spoilers below.

See more ...

Wed, 07 Jun 2006

Ruby vs. Python (vs. Perl) (vs. Lisp)

I've recently been playing with Ruby, and I think I've finally found a replacement for my various uses of Perl. For a while now, I've been using one of two languages for my at-home programming: Common Lisp for the more complex or interesting tasks; and Perl for the simpler tasks, standalone programs, and one-line text processing.

I've long had a love/hate relationship with Perl. On the one hand, its DWIM approach to things make it easy to do simple things, especially one-off text munging. perl -pe '<stuff>' has long been my friend. It also has CPAN going for it; many of my problems have been solved with a CPAN module and a little glue code. On the other hand, Perl tends towards extreme ugliness, especially when the code starts to get complicated. I've never liked the OO interface for Perl, for example; not only does it feel very obviously bolted on to an existing infrastructure, it didn't even get the sharp, pointy edges sanded down when they did it.

Thus it was that I was impressed with Python when I first met it. It felt like a language designed with OO from the bottom up. (But it wasn't; the addition of OO stuff had just been done in a much better way than Perl's.) It had nice data introspection. It had functions as first-class objects (so they got the benefit of introspection, as well as the other benefits of first-classness). I figured I could live with the whitespace-as-syntax wart. As I got to know it more, Python started falling down in a few places. For one thing, Guido van Rossum apparently doesn't like functional programming. Python has some functional programming constructs, like map and filter, but Guido keeps threatening to remove them. There's no good way to create anonymous functions, because Python's lambda is only useful for relatively trivial purposes. Python is also not terribly useful from the command line, largely because of the whitespace-as-syntax thing. Again, it works for some trivial cases, but is not general purpose enough.

So it was that I resisted bothering with Ruby for a while. "Oh," I said, "It's just another fad, like Python." But I kept hearing good things about it, even apart from all the buzz that Ruby on Rails has generated. So I finally resolved to poke at it a bit, and I'm pretty impressed. It's a much cleaner language than Perl, but it's better at functional and command-line usage than Python. It's enough to make me want to switch to Ruby for all my non-Lisp needs.

There are some things that feel like they might bother me, though. While Ruby not only supports anonymous functions but uses anonymous-function-like blocks all over the place, functions in Ruby are not first class objects, which means that you can't quite sling them around as easily as data. The use of special characters to determine variable scope (globals, class variables, instance variables, etc.) seems a bit weird to me, but at least it's not as bad as Perl's variable special characters.

Basically, Python has too much insistence on doing things its own particular, sometimes convoluted way. Ruby stole all the useful things from Perl while otherwise maintaining a very clean language that doesn't spit on my Lisp-influenced thinking.

Doing Your Own Math

When I was going to Catonsville Community College (now the Catonsville Campus of The Community College of Baltimore County), I took a couple of computer science courses. The first of those was essentially an introduction-to-programming course, with the textbook using C. The professor, however, said that he would accept programs in any language that was cleared with him beforehand. Since I already knew C, I used the class as an opportunity to learn Common Lisp.

One of the problems from the course that I still remember fondly was the "do your own math" one. We were allowed to have a function that used the language's built-in addition operator to add one to a supplied value, and the same for the subtraction operator. Building on those two functions (i.e. not using any of the language's other math operators or functions), we had to write functions to implement addition, subtraction, multiplication, division, modulus, exponentiation, greatest common divisor, and least common multiple. To simplify things, we only had to make the functions work in the domain of positive integers (so the division would be integer divisions). Because I felt like setting myself a little more of a challenge, I added a couple of my own constraints. I decided that I would make my functions work for all integers, both positive and negative, and that I would match the interfaces for the Common Lisp functions I was replacing (at least as far as integers were concerned).

I found the problem to be quite interesting because it involves breaking down common mathematical operations into their basic forms. It's also rather neat to build up a hierarchy of common routines where you've constructed each layer yourself and you end up with a tower where you've built each layer, aside from some small contributions for the foundation.

I was bored recently and decided to redo the problem, now that I've got more Common Lisp experience under my belt. In particular, I realized that I could make a new package and shadow the functions that I was replacing, so all of my code would look normal, even though I was using my own functions. I also thought it would be interesting to compare my Common Lisp programming from nearly a decade ago with my Common Lisp programming now. Here's my original code and my new code.

Probably my biggest surprise was that my original version of least common multiple gave wrong answers when supplied with multiple arguments. I clearly hadn't tested it enough in school. What's interesting is that I originally tried the same approach with my recent code, but had to fix it when I saw that it wasn't right. My recent code is also more efficient; division is orders of magnitude faster, especially for small divisors, and my old code triggers a stack overflow when asked to multiply large numbers. Structurally speaking, the newer stuff tends to be more compact; helper functions are declared with labels rather than at the toplevel, and I make better use of some Common Lisp functions, most notably reduce.

So now I've gotten even more out of the interesting problem. In addition to the fun of solving it at all, I also get a comparison of changes in my programming style over time. Perhaps I'll address it again in another decade or so.


Phil! Gold