Combinatorics

You know, for the Code Jam problem,  you just have to know how many "fair and square" numbers there are in a given interval. That's not necessarily the same thing as having to generate all of them.

Having done (or read) the analysis, we know that the number of "fair and square" numbers between m and n is the number of palindromic numbers between ⌈sqrt(m)⌉ and  ⌊sqrt(n)⌋ (we've shown how to get those values in previous posts)--let's call those values m' and n' respectively--for which the sum of the squares of the digits is less than 10.

Let's just consider d-digit base 10 numbers for d > 1, so we don't have to worry about 0 or 3. If [m'..n'] includes all d-digit base 10 numbers, or, given our theorem, at least the d-digit base 10 numbers from 10...01 to either 20...02 (if d is even) or 20..010...02 (if d is odd), then it has all the d-digit palindromes of the sort we want. (Writing them that way is serious handwaving about how big d is, sorry.) How many is that?

m `choose` 0 = 1
m `choose` n = product [m - n + 1..m] `div` product [1..n]

numTwoTwos d
    | d == 1    = 0
    | even d    = 1
    | otherwise = 2

numOneTwos d
    | d == 1    = 1
    | even d    = 0
    | otherwise = d `div` 2

numNoTwos d
    | d == 1    = 2
    | otherwise = if even d then n else 2 * n
                  where d' = d `div` 2 - 1
                        n = sum [d' `choose` i | i <- [0..min d' 3]]

numYs :: Int -> Int

numYs d = numTwoTwos d + numOneTwos d + numNoTwos d

(OK, so I went ahead and handled the d = 1 case.)

Then you need only actually generate and filter the Ys from m' to the next higher power of ten, and from the largest power of ten <= n' to n'. The others you can count. Sorry, Little John; if you wanted the numbers themselves you should have taken it up with the Code Jam people.

UPDATE: Fixed my errors, and went ahead and dealt with the one-digit case in the various num*Twos functions.

Now, the only question is what to do about the portion of the interval from ⌈sqrt(m)⌉ to ⌊sqrt(n)⌋ that doesn't cover a whole range of values for a given power of ten? More precisely, how to handle it efficiently, without generating Y values any more than we have to?

UPDATE: revised numNoTwos to omit 0 for the one-digit case, since the statement of the problem says it's not dealing with 0.

Compare and contrast

...as my English teachers used to say.

"Finally, although the subject is not a pleasant one, I must mention PL/1, a programming language for which the defining documentation is of a frightening size and complexity. Using PL/1 must be like flying a plane with 7000 buttons, switches and handles to manipulate in the cockpit. I absolutely fail to see how we can keep our growing programs firmly within our intellectual grip when by its sheer baroqueness the programming language —our basic tool, mind you!— already escapes our intellectual control. And if I have to describe the influence PL/1 can have on its users, the closest metaphor that comes to my mind is that of a drug. I remember from a symposium on higher level programming language a lecture given in defense of PL/1 by a man who described himself as one of its devoted users. But within a one-hour lecture in praise of PL/1. he managed to ask for the addition of about fifty new “features”, little supposing that the main source of his problems could very well be that it contained already far too many “features”. The speaker displayed all the depressing symptoms of addiction, reduced as he was to the state of mental stagnation in which he could only ask for more, more, more... When FORTRAN has been called an infantile disorder, full PL/1, with its growth characteristics of a dangerous tumor, could turn out to be a fatal disease." --Edsger W. Dijkstra, from "The Humble Programmer" (ACM Turing Award Lecture 1972)

"This is the first Part of n, or lets [sic] say many entries in this blog. In total I hope to be able to cover most papers in 3-4 blog posts, giving the reader an overview over the suggestions and changes for C++ at the coming C++ Committee Meeting in April. In total there are 98 Papers, so I will skip some, but try to get as much covered as possible. I'll skip papers with Meeting Minutes for sure, and try to focus on those focusing on C++11 or C++14 features. As the papers are ordered by there [sic] Number (N3522 being the first), I'll go top down, so every blog post will contain different papers from different fields of C++ Standardization. As N352-24 are Reports about Active Issues, Defects and Closed Issues I'll skip them for now, also I will not read through Meeting Minutes and such." --Jens Weller, from "A look at C++14: Papers Part I"

Plus ça change...

Good company

Just saw something on Hacker News pointing to a tweet from John Carmack:

"I want to do a moderate sized Haskell project, and not fall to bad habits. Is there a good forum for getting code review/criticism/coaching?"

From a later tweet from Mr. Carmack: "The Haskell code I started on is a port of the original Wolf 3D...."

I'm sure I'm not at his level, but it's reassuring to be in good company... as I feel I am in my opinion of C++.

UPDATE: here's an HN link. This comment is particularly interesting; I'll have to keep an eye open for new ghc releases.

More attempts at optimization

I set up for profiling, and I made two changes. First, I put back the memoization of powers of ten. Second, it occurred to me that most of the time I invoke oddDigitPal, I'm invoking it twice with just the middle digit changing. So, I went for

oddDigitsPals :: Integer -> Int -> [Integer] -> [Integer]

oddDigitsPals topHalf nDigits middles =
    let noMiddle = topHalf * tenToThe (nDigits + 1) + backwards topHalf
    in [noMiddle + m * tenToThe nDigits | m <- middles]

I also changed over to Int (32-bit integers) for numbers of digits. I'm not worried at this point about going for fair and square numbers of over two billion digits. (Little John, you're on your own after that, OK?)

It did make some difference, based on profiling output. Most notably, it took about 14% off bytes allocated. Time was less impressive; with the profiling pulled, it took execution time down from not quite 1.9 seconds to not quite 1.7 seconds.

A C solution that I downloaded, compiled, and ran took more like 0.4 seconds. I'm bummed by that factor of slightly over four, but OTOH:

• I'm no expert at Haskell optimization.
• I'd much rather try to understand the Haskell I've written than the C or C++ solutions I've seen so far.

Just goes to show that Knuth was right

One other thing occurred to me as a possible optimization: I'm raising 10 to some integer power a lot. Why not try

powersOfTen = [10 ^ i | i <- [0..]]

tenToThe :: Int -> Integer

tenToThe n = powersOfTen !! n

which would memoize those pesky exponentiations? (!! lets you retrieve elements from lists sort of as if they were arrays, with "subscripts" starting at zero.)

It was easy enough to try out, but the results were disappointing. Even on my Eee 900A, with a 32-bit processor that you'd think would get the most benefit, the variations in time output from one run to the next were large enough that I can't say with certainty that it made any difference at all. Time output for the first large data set:

real    0m1.093s
user    0m1.068s
sys     0m0.016s

For the second large data set:

real    0m5.531s
user    0m5.472s
sys     0m0.044s

These are with the program compiled--I still haven't done the file opening code.

One thing that doesn't carry immediately over

One thing that you can do with a compiled Haskell program that doesn't lend itself to ghci is I/O redirection. That's why I have yet to run the large data sets against the code running under the interpreter--I'll have to modify main to take a file name and use it as input source.

I will do it, though. I'm highly motivated, because it's related to what caused me to start all this in the first place.

Since I don't have Code Jam time limits...

...I should improve the style.

Lisp is a wonderful language. It's the first (largely) applicative language. Having a simple form that all language constructs follow means you can write seriously powerful tools to manipulate programs without wasting your time on convoluted parsing.

Compare that with the horrors of parsing C++, which strictly speaking is impossible! Thanks to templates, you have to solve the halting problem to successfully parse C++. Even ignoring that, there are ambiguous constructs, with a rule that says which way to decide in the presence of ambiguity. I suspect it all goes back to Stroustrup's eschewing formal language-based tools when writing that first ad hoc preprocessor for what was then "C with Classes". (BTW, Perl has the same problem. Perhaps there's something about kitchen sink languages.)

All that said, Haskell style isn't Lisp style. Any serious Haskell programmer would look at my palindrome program and say I lean far too heavily on if ... then ... else and I don't take advantage of Haskell's pattern matching and guards when defining functions.

Guards!

Take the backwards function. At first it was

backwards n = backwards' n 0
    where backwards' n accum = if n < 10 then n + accum
                                         else backwards' (n `div` 10) (10 * (n `mod` 10 + accum))

and that's perfectly valid Haskell, but we can do better. How about this?

backwards n =
    let backwards' m accum
          | m < 10    = accum + m
          | otherwise = backwards' (m `div` 10) (10 * (m `mod` 10 + accum))
    in backwards' n 0

Here we are using guards, and while, thanks to the current layout, there is still wraparound, the code now honors the golden 80-column punched card that some things, most notably standards for source code layout, still bow down to in the computer world. (UPDATE: I waved a dead chicken at the layout, and it now fits.) Things to note:

• there's no = immediately after the list of formal parameters of backwards' the way there was in the first version. The = are after the guards.
• it may just be that I'm not familiar enough with Haskell syntax, but I had to turn things around and use a let rather than a where for the definition of the helper function backwards'. 
• speaking of style, did you notice I changed the name of the first parameter of backwards'? I decided I'd better do that, the same  way I'd avoid gratuitously redeclaring a variable in an inner block with the same name as one in an outer block.

Patterns

That's not the only way to avoid if then else, though. Remember choose?

nDigits `choose` nOnes =
    if      nOnes   == 0     then [0]
    else if nDigits == 1     then [1]
    else if nDigits == nOnes then [sum [10 ^ n | n <- [0..nDigits - 1]]]
    else                          concat [[0 + 10 * x | x <- (nDigits - 1) `choose` nOnes],
                                          [1 + 10 * x | x <- (nDigits - 1) `choose` (nOnes - 1)]]

Let's take advantage of pattern matching as well as guards:

_ `choose` 0 = [0]
1 `choose` _ = [1]
m `choose` n
    | m == n    = [sum [10 ^ i | i <- [0..m - 1]]]
    | otherwise = concat [[0 + 10 * x | x <- (m - 1) `choose` n],
                          [1 + 10 * x | x <- (m - 1) `choose` (n - 1)]]

For this, you should know that _ matches anything. An identifier matches anything, too, but you can refer to it on the other side of the =. Use _ when, given the other parameters and/or the previously checked patterns, the value of the function does not depend on the value that _ matches. The patterns are applied in order, by the way, so here 1 `choose` 0 will match  _ `choose` 0 and not 1 `choose` _.

Yes, I must admit that I chose shorter parameter names. While in the case of this test, I am passing in a number of digits, that is distracting from the function, so here I would say that my initial choice was wrong. It's not just a matter of making lines fit in 80 columns.

DRY

DRY here is an acronym, and it applies no matter what your programming language. DRY = Don't Repeat Yourself. I said, Don't Repeat Yourself.

I very much repeat myself in the original program when it comes to the formation of a palindrome from its upper half (or in the case of an odd number of digits, the upper half and the middle digit). That needs its own function, or rather functions.

In theory those are all the parameters needed; you can calculate the number of digits in the upper half. Since we have that value, though, I'm inclined to pass it in.

Also speaking of DRY, I should use these functions to generate the palindromes with two 2s rather than making a special case of them. Say what you mean, as clearly as possible.

[We pause here for some testing and checking of run times for the input file with values up to 10¹⁰⁰.]

It's hard to say whether it makes a difference; just running the same program repeatedly shows variance in the time output. Here's one towards the low end:

real    0m1.822s
user    0m1.804s
sys     0m0.012s

while here's one towards the high end:

real    0m1.905s
user    0m1.872s
sys     0m0.028s

IMHO the result is worth the minimal, if it even exists, increase in run time.

Here's the code after the smoke cleared:

import Prelude
import Data.List

backwards :: Integer -> Integer

backwards n =
    let backwards' n accum
          | n < 10    = accum + n
          | otherwise = backwards' (n `div` 10) (10 * (n `mod` 10 + accum))
    in backwards' n 0

evenDigitsPal :: Integer -> Integer -> Integer

evenDigitsPal topHalf nDigits = topHalf * 10 ^ nDigits + backwards topHalf

oddDigitsPal :: Integer -> Integer -> Integer -> Integer

oddDigitsPal topHalf nDigits middle = (topHalf * 10 + middle) * 10 ^ nDigits + backwards topHalf

choose :: Integer -> Integer-> [Integer]

_ `choose` 0 = [0]
1 `choose` _ = [1]
m `choose` n
    | m == n    = [sum [10 ^ i | i <- [0..m - 1]]]
    | otherwise = concat [[0 + 10 * x | x <- (m - 1) `choose` n],
                          [1 + 10 * x | x <- (m - 1) `choose` (n - 1)]]

chooseRange :: Integer -> [Integer] -> [Integer]

m `chooseRange` ns = concat [m `choose` n |  n <- ns, n <= m]

twoTwos :: Integer -> [Integer]

twoTwos n
    | even n    = [evenDigitsPal msd (n `div` 2)]
    | otherwise = [oddDigitsPal msd (n `div` 2) d | d <- [0,1]]
    where msd = 2 * 10 ^ (n `div` 2 - 1)

oneTwo :: Integer -> [Integer]

oneTwo n
    | even n    = []
    | otherwise = let halfN = n `div` 2
                      msd = 10 ^ (halfN - 1)
                  in [oddDigitsPal (msd + x) halfN 2 |
                        x <- (halfN - 1) `chooseRange` [0..1]]

noTwos :: Integer -> [Integer]

noTwos n
   | even n    = [evenDigitsPal (msd + x) halfN | x <- choices]
   | otherwise = concat [[oddDigitsPal (msd + x) halfN 0,
                          oddDigitsPal (msd + x) halfN 1] | x <- choices]
   where halfN   = n `div` 2
         msd     = 10 ^ (halfN - 1)
         choices = (halfN - 1) `chooseRange` [0..3]

possibles :: Integer -> [Integer]

possibles 1 = [0..3]
possibles 2 = [11, 22]
possibles n = sort (concat [noTwos n, oneTwo n, twoTwos n])

ys = concat [possibles nDigits | nDigits <- [1..]]

xs = [y * y | y <- ys]

palSquares :: Integer -> Integer -> [Integer]

palSquares m n = takeWhile (<= n) (dropWhile (< m) xs)

-- jagd's main, which I believe is set up to read stdin

solve i num = do
        [a, b] <- getLine >>= return . map read . words
        putStrLn $ "Case #" ++ show i ++ ": " ++ (show $ length (palSquares a b))
        if i < num
           then solve (i+1) num
           else return ()

main = do
       num <- getLine >>= return.read
       solve 1 num

UPDATE: Aside from something in a later message, the only things I can think of to do are

• adding concise comments that suffice to describe what the code does and how to the extent that the code itself is unclear
• changing some function names. possibles sort of made sense when we were range checking and/or palindrome checking right there, but the range checking is moved out and given the math, they're not possible, they're certain. Also, choose isn't quite right. We're not counting combinations, as the phrase "m choose n" is meant in standard math nomenclature--we're generating them. I'm not sure what to use in their place, though.

Palindromes again?

Actually, it's more Haskell than palindromes.

I've been looking over other people's solutions to the "Fair and Square" problem, and they are pretty impressive. As a still-inexperienced Haskeller, I am taking inspiration from then rather than feeling discouraged.

In particular, jagd's solution reminded me that I was not thinking Haskell. Haskell is lazy; values aren't calculated until you require them. That lets you define infinite data structures! You only get into trouble if you do something that requires the whole thing.

For example, [1..] is the infinite list of all positive integers. You can safely use it, as long as you only use a finite amount of it. For example, if you try

uptoSqrt n = [x | x <- [1..], x * x <= n]

and then ask for

uptoSqrt 25

you will get back 1, 2, 3, 4, and 5, and then the function call will hang. You and I  realize that \x -> x * x is monotonically increasing for positive numbers, but Haskell doesn't, and obligingly tries to check the infinitely many integers greater than 5 to see whether any have squares no greater than 25. That takes forever, so it never finishes.

To get the result you want, you will have to write something like

uptoSqrt n = [x | x <- (takeWhile (\y -> y * y <= n) [1..])]

What's takeWhile? Here's a declaration for it:

takeWhile :: (a -> Bool) -> [a] -> [a]

Give it a function that takes an a and returns a Bool, and a list of as, and it will hand you back a prefix of that list--all the items up to, but not including, the first one for which the function returns false.

With that definition,

uptoSqrt 25

gives you the

[1,2,3,4,5]

you expect, because we know that [1..] is in ascending order and the square function is monotonically increasing.

(There's nothing magic about takeWhile; if you ask for

takeWhile even [2, 4..]

it will print even numbers forever, because [2, 4..] is the infinite list of positive even integers, and hence takeWhile will never find an odd number to make it stop.)

That means that I can simply define the whole infinite list of "fair and square" numbers. To make it possible to get those in a certain range, I will have to generate them in ascending order, so back comes the sort that we omitted for a while. I'm going to do something that clashes a bit with a Haskell convention for patterns in function definitions, because it matches the nomenclature of the problem discussion, in which the "fair and square" numbers are referred to as X and the palindromes they are squares of as Y.

possibles nDigits =
    if      nDigits == 1 then [0..3]
    else if nDigits == 2 then [11, 22]
                         else sort (concat [noTwos nDigits, oneTwo nDigits, twoTwos nDigits])

ys = concat [possibles n | n <- [1..]]
xs = [y * y | y <- ys]

palSquares m n = takeWhile (<= n) (dropWhile (< m) xs)

dropWhile is kind of like takeWhile, but it gives you a suffix of the list you hand it, namely everything from the first item for which the function returns false on. If you drop the values less than m from the front of a sorted list, and then grab the values <= n from the front of what's left, you have precisely those values between m and n inclusive. (I'm being a bit free with my language here, of course. Haskell doesn't destroy the original list--at least not if anyone's looking.)

Note that we aren't using floorSqrt or ceilSqrt any more, so they can go away, and we thus aren't counting bits any more.  We're defining the whole list, so we aren't counting decimal digits, either, and digitsIn can go away as well.

So do infinite data structures provide any advantage? Well, consider that I have yet to actually solve the Code Jam problem as such. Remember that it requires reading a file with ranges of values m and n for which we have to print a line of a given format with the value of

length (palSquares m n)

Defining the infinite list of Xs is a form of memoization, remembering the values of a function you calculate so you don't have to do the work if you invoke it again with the same arguments. Suppose two of the input lines are

200 1000
40 500

Evaluating

palSquares 200 1000

will evaluate all the Xs between 0 and 1000 (actually one more past that, because you have to find the stopping place), so that when it comes time to process the next line, all the values between 40 and 500 will have already been determined, so all we have to do is select the values in range.

It's not what you'd want for serious memoization; after all, the input lines could all be within a small interval of the upper bound, so we would arguably have wasted the determination of all those lesser "fair and square" numbers. But it does have the potential of saving time. Let's see what happens with the Code Jam inputs (and with jagd's version of main)...

Cool! Of course, I didn't submit these officially--I'm using a portion of someone else's solution, and peeked at the analysis of the problem, and took far longer to write the program than the rules permit, so it would in no way be fair to take credit--but Google let me download the inputs, and confirmed that the output generated is correct. Here's the time output, first for large input 1, 10K lines with ranges a subset of [1, 10¹⁴]:

real    0m0.229s
user    0m0.220s
sys     0m0.008s

and then for large input 2, 1K lines with a range of [1, 10¹⁰⁰]:

real    0m1.796s
user    0m1.784s
sys     0m0.012s

Not shabby for time--and to refer back to Mr. Reeder's blog post, I'm sure that with those times, an interpreted version would have no trouble running in the eight minute limit Code Jam imposes--but how about memory? Time to instrument again... and sure enough, keeping that list, or perhaps those lists, around eats RAM. With large input 1, it uses 60+ kilobytes of RAM (the graph generated doesn't show the scale all the way up the Y (RAM) axis), and with large input 2, it uses about five megabytes of RAM. Even the five megabytes is small change these days, and now I suspect I wasn't looking closely at which run I was checking memory usage for last time around. I bet I thought a 10¹⁰⁰ run was a 10¹⁴ run, and I shouldn't have blamed the sort at all.

UPDATE: I'm truly amazed at the brevity of jagd's solution; you really should check it out. I will have a good time studying it further.  Just for the heck of it, I compiled it with ghc -O2, and tried it on the large input files.  For large input 1,

real    0m0.226s
user    0m0.220s
sys     0m0.008s

For large input 2,

real    0m14.410s
user    0m14.200s
sys     0m0.184s

I wonder what it's doing differently to make it run 63.8 times slower on the larger input rather than 7.84 times slower?

UPDATE:  part of it is the way it's keeping the list of Ys both in numeric and string form, with lots of conversions back and forth. That means more memory; on large input 2, jagd's program uses over 55 Mbytes of RAM, with a very interesting shape to the plot of RAM versus time.

I see that jagd also at least thinks he or she is generating some values that might not be valid Ys, given the

filter (ispalindrome . square)

applied to potential Ys. Maybe that's part of the RAM usage fluctuation.

("." is function composition in Haskell, and filter has a signature that should be familiar to you from takeWhile:

filter :: (a -> Bool) -> [a] -> [a]

filter takes a function and a list and hands  you back all the items in the list for which the function returns true.)

Fun with palindromes, and the joys of Haskell

An item in Hacker News caught my eye recently. (Ouch!) It linked to a post, "Ruby is Too Slow for Programming Competitions", by a gentleman named Clif Reeder. A summary: Mr. Reeder chose Ruby to try on a Google Code Jam qualification round problem, and found that his solution ran too slowly to meet the Code Jam time constraints (on the official runs, you have eight minutes from downloading the input to upload your output). A version written in the (compiled) Go language ran much faster.

Commenters on the HN item pointed out

• Mr. Reeder didn't think through the problem fully; there were more possible optimizations. In fact, there's a list of 387 people who used Ruby to successfully handle either the small sample input (which has a four-minute time limit) or the large or really large inputs (with the eight-minute time limit).
• Like C, the size of int in Go may vary, so the Go version might or might not be able to handle the larger inputs correctly.

There was also a long discussion of whether it's really worth writing programs in a higher-level language and dropping to a lower-overhead language for the time-critical parts (something I thought was SOP these days).

Anyway, I thought I'd add my voice to the chorus of "it's the algorithm, not the language" (or more accurately, if the algorithm isn't efficient, compiled vs. interpreted or high versus low level language doesn't matter) by writing in Haskell. The goal: writing code as clear as I can manage while still solving the problem quickly enough.

(I hasten to add that I am no Haskell expert, and I hope to see someone put Haskell to better, more idiomatic use while maintaining or improving clarity.)

Strictly speaking, I'm writing code that solves the main part of the problem:

Given natural numbers M and N, how many numbers between M and N inclusive are both (base ten) palindromes and squares of numbers which are (base ten) palindromes?

More about the full problem later. For now, let's refer to an example of the kind of number we want as X, where X is a palindrome and also equal to the square of a palindrome Y, as the Code Jam analysis of the problem does.

When you look at the problem, some possible optimizations over the brute force method come to mind:

1. Rather than look in [M, N] for Xs, look over values in [⌈sqrt(M)⌉, ⌊sqrt(N)⌋] for Ys. Mr. Reeder took advantage of this in his program; it helps a great deal.
2. Rather than looking at each number in the range for palindromes, better to generate the palindromes in the range. A palindrome is determined by half its digits (unless it has an odd number of digits, in which case there's another digit in the middle that's not constrained to match any other digit), so that gives another reduction on the same order as (1).
3. If Y squared has to be a palindrome, Y is still further constrained. Suppose Y = 4.....4. Then Y squared has the form n....6, where 16 ≤ n < 25, so it can't be a palindrome. A similar argument rules out five through nine, cutting the work down by two thirds.

That, alas, is as far as I took the analysis. With that much, straightforward Haskell code will spit out all the "fair and square" numbers, as the problem statement calls them, between 1 and 10¹⁴ in about a second on my Eee 900A netbook. That range includes all the values in the smaller large input file.

Fortunately, it's possible to do much better than that! Google's full analysis of the problem can be found on the Code Jam site. To summarize it:

1. Given the constraint on Y's leading and trailing digits, there can't be a carry out of the most significant digit when you add up the partial products of Y * Y to get X, so if Y has n digits, X has 2n - 1 digits, an odd number.
2. In fact, there's no carry out of any position in the sum of the partial products of Y and Y; that's both a necessary and sufficient condition for X = Y * Y to be a palindrome if Y is a palindrome.
3. The middle digit of X is thus (since Y is a palindrome) the sum of the squares of the digits of Y, and must be no bigger than 9.

It follows immediately from (3) is that the only Y containing the digit 3 is 3 itself. All other possible Y values can only contain the digits 0, 1, and 2, and can be broken down into three cases:

• No 2s at all. They can have up to nine 1s if they have an odd number of digits, eight if they have an even number of digits.
• One 2. The 2 must be the middle digit, requiring an odd number of digits, and the rest of Y can have no more than four ones (if there were five, Y couldn't be a palindrome). Aside from 2, there must be at least two ones, the most and least significant digits.
• Two 2s. This allows at most one 1, and that only in the middle, which can only happen if there are an odd number of digits.

 Any other digits in Y must be zeroes.

Just constraining the digits to 0, 1, and 2 did speed things up somewhat; the resulting program managed to get up into the 48-digit Xs in about three minutes, but that's nowhere near fast enough to handle the largest test input, which has values up to 10¹⁰⁰, in the eight minutes Code Jam limits you to. To do it right, you have to seriously skip values that don't meet the sum of squares constraint.

Here's the code I ended up with. I split out the one- and two-digit cases so that the noTwos, oneTwo, and twoTwos functions don't have to bother with them.

I should point out that

• I did this without the time constraints of Code Jam, over about eight days after the Hacker News post
• Of course, you're not seeing the mistakes I made over that eight days!
• The integer square root function came from an answer to a Stack Overflow question, which in turn was taken from Crandall and Pomerance, "Prime Numbers: a Computational Perspective"
• The trivial Main is adapted from Chapter 25 of Real World Haskell having to do with profiling (about which more later)

import Prelude
import System.Environment
import Text.Printf

backwards :: Integer -> Integer

backwards n = backwards' n 0
    where backwards' n accum = if n < 10 then n + accum
                                         else backwards' (n `div` 10) (10 * (n `mod` 10 + accum))

numPalindrome :: Integer -> Bool

numPalindrome n = (n == backwards n)

twoTwos :: Integer -> [Integer]

twoTwos nDigits =
    let justTwos = 2 * 10 ^ (nDigits - 1) + 2
    in
        if even nDigits then [justTwos]
                        else [justTwos, justTwos + 10 ^ (nDigits `div` 2)]

choose :: Integer -> Integer-> [Integer]

nDigits `choose` nOnes =
    if      nOnes   == 0     then [0]
    else if nDigits == 1     then [1]
    else if nDigits == nOnes then [sum [10 ^ n | n <- [0..nDigits - 1]]]
    else                          concat [[0 + 10 * x | x <- (nDigits - 1) `choose` nOnes],
                                          [1 + 10 * x | x <- (nDigits - 1) `choose` (nOnes - 1)]]

chooseRange :: Integer -> [Integer] -> [Integer]

chooseRange nDigits onesRange = concat [nDigits `choose` nOnes | nOnes <- onesRange, nOnes <= nDigits]

oneTwo nDigits =
    if even nDigits then []
                    else
                         let msd = 10 ^ (nDigits `div` 2 - 1)
                         in  [((msd + x) * 10 + 2) * 10 ^ (nDigits `div` 2) + backwards (msd + x) |
                                      x <- chooseRange (nDigits `div` 2 - 1) [0..1]]

noTwos :: Integer -> [Integer]

noTwos nDigits =
    let halfN   = nDigits `div` 2
        msd     = 10 ^ (halfN - 1)
        choices = chooseRange (halfN - 1) [0..3]
    in
        if even nDigits then [         (msd + x)           * 10 ^ halfN + backwards (msd + x) | x <- choices]
                        else concat [[((msd + x) * 10 + 1) * 10 ^ halfN + backwards (msd + x),
                                       (msd + x) * 10      * 10 ^ halfN + backwards (msd + x)] | x <- choices]

possibles :: Integer -> [Integer]

possibles nDigits =
    if      nDigits == 1 then [0..3]
    else if nDigits == 2 then [11, 22]
                         else concat [noTwos nDigits, oneTwo nDigits, twoTwos nDigits]

digitsIn :: Integer -> Integer -> Integer

digitsIn base n = digitsIn' n 1
    where digitsIn' n count = if n < base then count else digitsIn' (n `div` base) (count + 1)

candidates :: Integer -> Integer -> [Integer]

candidates m n = [x | x <- concat (map possibles [digitsIn 10 m..digitsIn 10 n]), x >= m, x <= n]

floorSqrt :: Integer -> Integer

floorSqrt n = if n == 0 then 0 else floorSqrt' (2 ^ ((1 + digitsIn 2 n) `div` 2))
    where floorSqrt' x =
               let y = (x + n `div` x) `div` 2
               in if y >= x then x else floorSqrt' y

ceilSqrt :: Integer -> Integer

ceilSqrt n =
    let y = floorSqrt n
    in if y * y == n then y else y + 1

palSquares :: Integer -> Integer -> [Integer]

palSquares m n = [x * x | x <- candidates (ceilSqrt m) (floorSqrt n)]

main = do
    [d] <- map read `fmap` getArgs
    printf "%d\n" (length (palSquares 1 d))

Now, the times mentioned above are for runs without main, under ghci, an interpreter, using a version that sorted the results of possibles to make the output easier to check against the values at "Palindromic Square Numbers". I should also mention that under ghci it was able (again, with the sort) to generate the list of "fair and square" numbers between 1 and 10¹⁰⁰ in about 28 seconds on my 2.8 GHz Athlon II X4 630 processor. Some of that time was I/O.

Profiling meant using the compiler, and what a difference that made! The first version of main didn't bother to read the command line arguments, and instead wired in 10¹⁰⁰ as the upper bound. Compiling with -O2, it ran fast enough that I made the change to read the command line arguments lest it have optimized away all the calculations. That done, time output for a run, again using 10¹⁰⁰ as the upper bound, showed

real  0m0.495s
user  0m0.480s
sys   0m0.012s

With the sort pulled, the time output was

real  0m0.389s
user  0m0.380s
sys   0m0.004s

The sort also turned out to be a major source of memory usage. With sort, it was using nearly four megabytes of RAM. Without, the profile showed it using more like 40K.

Now, you couldn't use the interpreted version in the straightforward way to successfully pass the Code Jam large and larger input tests; you'd want to take advantage of their giving the range of values, generate the list and then convert it to a structure that lends itself to quickly determining how many values are in a given range. (Sorted list, perhaps a search tree...)

The compiled version, on the other hand...  the smaller large input file has no more than 10000 lines, confined to [1, 10¹⁴].  Results of time on that range:

real    0m0.003s
user    0m0.004s
sys     0m0.000s

If every input line covered the whole range, that would be thirty seconds, plus the time for I/O--well within the eight minute range.

The larger large input file has no more than 1000 lines, confined to [1, 10¹⁰⁰]. If every input line covered the whole ranges, that would be 389 seconds plus I/O time. That's cutting it rather close, but it's still possible.

So, have we shown what we set out to show? Clearly compiled Haskell is far faster than interpreted Haskell. (To give a better comparison, since I ran the interpreted cases on my Eee 900A--the compiled version ran in about 2.5 seconds on the larger range on the Eee.) But that's not the point; the optimized algorithm could trivially run the first large data set even interpreted, and with the precalculation could probably do the larger large data set interpreted.

All that said, the revelation for me was this: it was incredibly easy to write the code, straightforward to test and debug in the interpreter, and I had only to add import lines and the simple main to be able to compile it. Total: sixty-three (nonblank) lines of code. It's helped along by Haskell having arbitrary-precision integers and list comprehensions, which I used liberally.

One could argue that this problem is one particularly well-suited to Haskell, but for me this was a sufficiently enjoyable task that I will do more with Haskell, and I urge you to give it a try too.

UPDATE: Looks like Ruby has Bignum, and various people have posted fairly concise-looking constructs to get the effect of list comprehensions.  It might be fun to rewrite the above in Ruby.

UPDATE: Here are the solutions in Haskell from the Code Jam web site. Check out jadg's code; it's very impressively short. I'll be studying that one.

Night of the Living Blog

A good friend nudged me to start putting up stuff I am working/have worked on, so Aging Nerd Notes is shuddering back to activity after what, eight years? I'm amazed Google has kept it around so long.

O would some god the giftie gie us...

Recently I've gotten some email from word-of-mouth-connection.com. People can register that they have experience with a particular person or business, say something about how well they know said entity and how recent their experience is, and then others who want to find out about said entity can go looking through the database and inquire via email; the contacts are done anonymously.

At the time of writing, there are apparently three people who claim to know me well who have registered that fact, and hence, I suppose, their willingness to tell others about me, and one person looking to find out about me.

I guess that it's good that word-of-mouth-connection.com tells me that this is happening...but to be honest, it creeps me out. That, in turn, probably points out my tendency to assume the worst. For all I know, the three people are happily telling anyone who asks that I'm a heck of a guy, but I would have been happy to continue to not think about people talking about me behind my back. If it's anonymous, I suppose I could email the three and ask what they think, and the one and ask what he or she wants to know, but I'm not sure I want to find out.

Ah, well. As the guy said at the end of Asimov's "The Dead Past," happy goldfish bowl, everybody.

OK, now say "shibboleth"...

Computers are far more widespread than they used to be--which perforce means that most of the people who use them are ignorant of how they work, just as most people couldn't tell you how their TVs, cars, or phones work. (Not that there's anything wrong with that.) So, how can you tell the posers from the real deal? One sure mark of someone who doesn't know diddly about computers is this: referring to mass storage space (hard disk, CD-ROM, DVD-ROM) as "memory."

What are some other misstatements that reveal computer ignorance? Someone should compile a list of them--so send your favorites our way, please!

Not the best intro, I guess...

I probably would be more favorably inclined to Joan of Arcadia had I watched it from the beginning, but I started with this evening's episode.

Joan of Arcadia is sort of the mutant offspring of Touched by an Angel and Calvin and Hobbes. Did you ever notice how, if agents of the divine really did all the stuff that the angels on TbaA did, there would be no doubt at all of the existence of a non-denominational Christian God? JoA bypasses that problem by making God an ever-shifting Hobbes to Joan's Calvin. God/Hobbes tells Joan/Calvin what to do, and occasionally gives the stray oblique lecture (apologies to Brian Eno). Joan is supposedly trying to figure out just what God has in mind, but if the producers have any sense, it will never happen; just as the unseen monster is always scarier than the guy in the rubber suit who finally emerges, any supposed divine plan that the writers come up with will necessarily seem lame. (Though come to think of it, if the blatant hint of the title holds, any end is going to be pretty definitive...)

Tonight, there are three plot threads: Joan's family's reactions to her brother's paralysis, Joan's interactions with the in crowd at high school, and the bringing in of a "psychic" in a kidnapping case. Joan's father, the new chief of police in the town they've moved into, is the voice of rationality, and doesn't at all appreciate the psychic. In a tense interaction between the two, the psychic claims to have gained her talents after a near-death experience, and asks him whether it's "the tragedy" that makes him so resistant to her presence.

I am extremely disappointed in the writers of this show; they had and blew a wonderful opportunity for the father to take the "psychic" to task. What he should have said at that point is, "How dare you live off the suffering of others! You've just begun a 'cold reading,' asking vague leading questions to try to pump me for information that you can then claim to have gotten from the spirits or via your supposed powers. Nearly everybody has had some tragedy, and if I happen to be someone who has managed to avoid personal tragedy, you could claim that you were referring to the disappearance. You can sucker a lot of people, even intelligent people, with that scam, but not this time. Now get out!"

Why is it that the media so often pander to pseudoscience like this?
Can't the rational characters get the upper hand once in a while?

Verbal Abuse as Entertainment

When I grew up, my parents always told me that there was a sort of person who needed to tear down others to try to salvage his or her nonexistent self-esteem, and that I should not be that sort of person. Judging by radio and TV today, though, such people seem to be doing awfully well.

Verbal abuse is now a popular entertainment form. Weakest Link, American Idol, Cupid... all “reality shows” that showcase and derive their popularity from gratuitous viciousness. David Letterman has made a career of finding people from “flyover country” and interviewing them in such a way that he and his audience can derive their sick jollies from feeling hip and superior. Such interviews and prank calls are a major feature of, for example, Mancow Muller’s syndicated radio show. We’ve already mentioned “Dr. Laura.” One sees the actions of, say, Simon Cowell rationalized as “honesty” or “tough love”—but one can be honest without being vicious or abusive.

So why are these TV and radio shows doing so well? Have we turned into the people that our parents warned us not to be, or a cowardly variant thereof who just enjoy watching someone else do the dirty work? It doesn’t speak very well for us.

Grumble, Grumble...

I have just one thing to say to the Academy of Motion Picture Arts and Sciences for not giving the Best Animated Feature award to Lilo and Stitch:

Meega na la kweesta!

Sic Transit

The Islamic cultures once were important centers of philosophy, science, mathematics, and literature. Just go through a technical dictionary looking for words that start with al- (Arabic for "the"): algebra, algorithm, alcohol, aldehyde... We have them to thank for the Alhambra, Leyli and Majnun (whose influence stretches through Tristan and Isolde, Romeo and Juliet, and Derek and the Dominoes), and the poetry of Rumi. (Speaking of the Alhambra--the Moors were considerably more tolerant than Los Reyes Católicos, who offered the Jews the choice of conversion or eviction shortly after coming to power.)

So, how on earth could such a culture produce the vile beasts who now rule Iraq, or who make sure schoolgirls dressed "indecently" don't escape burning buildings? Are such people the norm, or are they as reviled in their culture as Nazis and their deluded followers are in the West? I'd like to think the latter.

On Its Way Back...

Anyone who listens to the radio knows that commercial music radio, with very few exceptions, is the "vast wasteland" of Newton Minow's immortal phrase. If you want something out of the ordinary, or even if your tastes just differ from the homogenized focus-group dreck that the large media companies know is best for you, the place to go is to webcasting...and one of the very best webcasters was Luxuria Music.

Luxuria Music featured a wild and varied blend of music. They encouraged feedback, and actually played requests (like the old days!). Alas, in April 2001 it went away, but...if you go to the LM web site today, you'll find that it's coming back on March 1, 2003. This is good news indeed. Until then, you can listen to recordings of old LM shows on a live365.com stream. Check it out.

Update from after their relaunch--they've gone over to making people listen to three minutes of ads before they get to hear the music, and have chosen a Windows Media Player/Internet Explorer-only setup for doing that... and when I tried it on a Windows box, I got the "this page is trying to run a DirectX plugin, but your security settings aren't letting it run, so this web page may not work," and sure enough, it didn't--after letting it sit there for five minutes or so claiming to be loading something, I killed it. So it seems that Luxuria has succumbed to the Great Satan, and doesn't care to use open standards for its stream. I urge people interested in good music to check out BeOS Radio.

Buzz Off, Robert Browning...

Grow old along with me,
The best is yet to be!
The last of life, for which the first was made...

Browning is full of it. Aging sucks. Systems break down, and it's not going to get better. To borrow a phrase from Tom Lehrer, you're "sliding down the razor blade of life."
I just hope that Ray Kurzweil and Hans Moravec are right, or better yet, too conservative, and I can download myself into a Primo 3M+ body.

Not to Be Missed

Just got home from seeing the National Theater of the Deaf's production of Oh, Figaro! based on the Beaumarchais characters that gave rise to Le Nozze di Figaro and The Barber of Seville (which I don't remember the Italian for....). They kicked serious posterior; the show was a hoot. It was signed and spoken, and while I'm sure there was ASL wordplay that sailed right over my head (I'm a rank beginner at the language), I still had a wonderful time. If it comes to your area, don't miss it. If it doesn't come to your area, go to its area.

Experts in Their Field

If political affairs should ever hinge on the proper use of vibrato, I will listen to what Barbra Streisand has to say about it. Should the fate of the homeless depend on proper blocking, I will defer to Mike Farrell...

...but until then, could the entertainment industry collectively take its pontification and rants elsewhere?

I commend this petition to your attention.

The Ubiquity of Kitsch, and Preachiness

It's February, and we're about to see Washington and Lincoln reduced to shilling for car and furniture outlets again. I can't help thinking that is the ultimate fate of rulers everywhere:

• Two very good friends once went to Europe, and they brought me back a souvenir—a T-shirt with the standard issue cartoon image of a Viking and the caption "ERIK BLOODAXE RULES OK"
• I got to go to Japan once. I wound up with a coworker at the re-rebuilt Osaka Castle, still impressive even though it is not as large as the initial structure. Up on the third floor was the souvenir shop, where you could get Hideyoshi Toyotomi knicknacks.
• Caesar, of course, sells pizzas these days (but who'd buy a pizza with a spear hole through it?)
• As for King Tut, two words: Steve Martin. (Yes, I realize he was making fun of the marketing of Tutankhamen.)

Sturgeon's Law ("90% of everything is crap") seems to apply particularly to Christian music. I think I know part of the reason.

Remember Edith Hamilton's insightful distinction between Greek mythology and Norse mythology? In MTV generation terms, Greek mythology is like series TV; you know the good guys will win, and nothing can really change, lest continuity break. Norse mythology is like a movie. In hopes of minimizing the angular velocity of Ms. Hamilton's grave, here's a closer paraphrase: Greek mythology has no heroes, at least among the gods, because they always win. In Norse mythology, the gods are heroes, because they act even though they know that Ragnarok is coming and they're all going to die.

Christianity, at least the simple-minded Christianity of much Christian music, is like Greek mythology in that respect. Everything is going to be fine, and there's one answer to everything. Unfortunately, preaching is dull, and life's not like that. The best religious lyrics, as the English teacher always said, show rather than tell, and aren't cocksure: for example, "Mary was an Only Child" on Art Garfunkel's Angel Clare album, T.S. Eliot's "The Journey of the Magi," Holst's gorgeous setting of "Lullay My Liking," or Jars of Clay's "Flood."

I shouldn't pick specifically on Christian music, though; I've just been listening to a pagan webcast, and Wiccans can be just as preachy, as a really bad song I just heard about the "Burning Times" that parrotted the hype shows (come on, people, the reality was bad enough). Protest songs of course, often beat you over the head with preachiness and the singer's self-righteousness. (Speaking of which, two words: Natalie Merchant.)

Government as God

Bill Clinton several times referred to a "new covenant" between the US government and the American people. You'll recall that the original covenant was that between God and Israel, followed, according to the Christian faith, by a new covenant between God and Christians, mediated by Christ.

Am I alone in being disturbed by such language and the implied equating of government with a god? What a monstrous ego it must take to liken oneself to Moses or Christ, and how different from the point of view of the Founding Fathers, who at least tried to carefully limit the powers of government!

Government is not reason; it is not eloquent; it is force. Like fire, it is a dangerous servant and a fearful master. —George Washington

Why bring this up when Clinton is, thank goodness, no longer President? Because George W. Bush, while not exalting himself as Clinton did, still uses religious imagery. "Power, power, wonder-working power" belongs in the old hymn to the blood of the Lamb of God, but Bush attributes it to "the goodness and idealism and faith of the American people." Is there any operational difference between that and Clinton's deification of government? Considering the stream of massive new federal government spending programs GWB proposed in the same speech, I fear that there might not be.

(Side note: despite what you might guess from the above, I am effectively an atheist.)

Assorted Despicable Things and People, Part Two

Dr. Laura

I actually listened to some of one of her shows (not voluntarily; I was traveling with a friend, and we were scanning the AM band for something to listen to). Callers to her show must either be desperate or masochistic, to put up with her rudeness and verbal abuse, and the fans must have a sadistic streak. Dr. Laura (whose doctorate is in physiology, having nothing to do with how she makes a living these days) is big on family...but a few weeks ago her mother's dead body was discovered in an apartment, apparently having been there unnoticed for months. Dr. Laura tells callers to stop sniveling and "face the day," but check out her behavior on a trip to Dallas to give a talk to the women's division of the Jewish Welfare Federation.

Same Song, Opposite Aisle

These days there are a number of web sites where people mostly post quotations from news articles and/or commentaries on said articles. (The sources of the news articles don't much appreciate the quotation; there's been at least one lawsuit over the matter.)

freerepublic.com is the right-wing flavor. There you'll find a lot of creationism threads--there are either a lot of creationists or a few really vocal ones at freerepublic.com. (OTOH, there are rational people there, too.) You'll find a lot of religious ranting and bashing of homosexuals, and people who dare point out that GWB is pushing big government despite the posturings of the Republican Party are flamed at great length. There's a libertarian contingent that regularly points out the idiocy of the Drug War, and is just as regularly flamed for their troubles, and simultaneously told that (1) they're too few in number to be significant and (2) they're helping the Democrats by "stealing" votes from Republican candidates. During the Clinton administration, there was a tinfoil hat contingent that went somewhat off the deep end (and considering Clinton, that requires some work).

democraticunderground.com is the left-wing flavor. There you'll find a number of religious threads, mostly arguing that "true Christianity" favors income redistribution and the welfare state. There's an astrology contingent, so one certainly can't say that the left is immune to pseudoscience and other such claptrap. There's a Green contingent who's mostly told that they're helping the Republicans by "stealing" votes from Democratic candidates. There's a large, or at least vocal, tinfoil hat contingent who wholeheartedly believes GWB let 9/11 happen so his buddies could make money, that the Republicans assassinated Paul Wellstone, etc.

To freerepublic.com's credit, they're a lot more willing to tolerate varying opinions than democraticunderground.com, which bans people for thoughtcrime, and back in 2002 prohibited posts that the moderators thought might hurt the Democratic Party...but upon reflection, it seems like what we have here in large part are two batches of True Believers, just working opposite sides of the street.

Assorted Despicable Things and People, Part One

Microsoft

Once upon a time, only technical people knew the details of how Microsoft rose to power. Now, you have to have been comatose or living in the outback not to know. If you don't know, go read Wendy Goldman Rohm's The Microsoft File and you'll find out.

C++

The PL/I of the 90s; a bloated obscenity of poorly thought-out, ill-fitting features and kludged syntax that no one person can keep in his head. These days, people say that the day of programming languages that try to be all things to all men is gone, but nobody bothered to tell Bjarne Stroustrup.

The Clintons

The most loathsome, amoral, corrupt person to ever occupy the White House, and his equally vile and power-hungry wife. To quote Dick Morris, "It’s a good thing those two are sociopaths. Otherwise their consciences might bother them..." Time for a "reality show" parody, if that's not a redundancy.

"Rasputin--LOCK THE DOOR!"

Long ago, radio and TV stations actually had to come up with their own programming a lot of the time. Today, if you scan the radio dial at night, on AM you'll hear many stations broadcasting identical syndicated talk shows; the only difference is which such show they run when. Before, each station would carry a local show, only merging on hour boundaries for network news. On TV, if you scanned the dial at night, you'd find a lot of stations showing movies actually selected individually at each station... and on Saturday nights, chances are those movies would be SF or horror movies with a host who would appear at the beginning and end, and around commercial breaks.

Each station had its own host, who often was a local celebrity of sorts (if only the sort depicted by Roger Miller in his song "Kansas City Star"). Alas, the earliest hosts, such as the incomparable and sultry Vampira, were before my time; my initiiation to late night horror movies was at my paternal grandparents' creaky house watching KVOO (Tulsa, Channel 2) with Fantastic Theater and its eerie synthesized theme music, watching films like Frankenstein 1970 and Attack of the 50-Foot Woman. (Trudging up the stairs in the dark after hearing that music always scared the heck out of me.) Later on in Oklahoma City, I grew up watching the witty and fun Count Gregore on Nightmare, who got to do things like hang out with the Green Slime Girls back when Green Slime first came out (remember the cheesy Green Slime theme song?) and sing "Some enchanted evening, you will meet a strangler..." When I went to Chicago, I discovered the joys of Son of Svengoolie's Saturday night horror movie program.

My favorite horror host, though, was on the air after I returned to Oklahoma in the early 1980s. For reasons known only to the folks who ran the Norman cable TV system at the time, they carried Kansas City channel 41, and there I discovered Creature Feature, hosted by Crematia Mortem.

Creature Feature showed many so-bad-they're-good movies: Invasion of the Star Creatures, The Incredible Melting Man, The Devil's Rain, and a shaggy cannibal story featuring the hit "Popcorn" by Hot Butter, Shriek of the Mutilated. Crematia would comment on and make fun of the movie before and after the commercials, have little subplots and running gags going on through the show, and would read viewer mail (which one sent, of course, to the Dead Letter File). It didn't at all hurt that Crematia was not only witty, but also gorgeous (and if you check out the web site where Roberta Solomon, who portrayed Crematia, advertises her excellent voiceover work, you'll see that she still is). I was among those who wrote, and I wish to heck that I had videotape of the shows, especially when she showed the address I'd done up in blackletter and the portrait I drew of her.

She'd call out to her assistant, Rasputin, to lock the door at the beginning of the show and unlock it at the end, though I don't think many viewers had any urge to leave or change the channel.

Sad to say, Norman cable TV dropped Channel 41, and paid our protests no heed. Creature Feature went on for a few more years, but fell prey to the homogenization of American commercial media.

There are some horror movie hosts still on the air (notably Chicago's Svengoolie), and I suppose that for a time USA's Up All Night sort of carried on the tradition--but for the most part, they are gone, replaced by the output of the sausage machine that is today's commercial mass media. I post this as a belated thanks to all those eerie folk who made my childhood more fun (when I wasn't risking bodily injury running to bed when the lights went out) and were equally enjoyable later in life. Count Gregore, (Son of) Svengoolie, and Crematia Mortem, affectionate thanks to you all.

My Renaissance Fair Pet Peeve

Here it is: in my experience, Renaissance fairs are not at all the best places to go to hear Renaissance music.

Disclaimer the First

I enjoy Renaissance fairs. I even sing at them, and the group I currently sing with is just as guilty as the rest. Yes, I know there are exceptions, and I cherish them.

But, That Said...

If you go to a Renaissance fair and check out the paid musical acts, what will you typically hear? Sea chanteys (one web site says the golden age of the sea chantey was the early to mid-19th century!). Irish music, from Carolan (late 17th to early 18th century) to songs of the 1916 Easter rebellion. Scottish songs, often dealing with the 18th century Jacobite rebellion, and some by modern composers (e.g. "Queen of Argyle," "Flower of Scotland").

A year or so ago on the alt.fairs.renaissance newsgroup, someone posted a request for suggestions for material for performance. Someone responded, "How about something actually from the Renaissance?" and was generally shouted down. The shouters-down typically had the opinion that the responder was being a jerk (arguably true; certainly the response at least seemed sarcastic, and immediately put the requester on the defensive), but also that the paying customers at Renaissance fairs want only music of a sort they're familiar with. There was also the common belief that surviving period music is all elitist--a belief only holdable by people massively ignorant of early music. (To correct that notion, listen to "Tappster, Drynker," "Blow Thy Horn, Hunter," "Hoyda, Jolly Rutterkin," "And I Were a Maiden," "Martin Said to His Man" (one of the "freemen's songs" Henry VIII is said to have enjoyed singing with Lord Peter Carew; given the subject matter, I can't help imagining them singing it after a few brewskis), "Matona Mia Cara," "O Bene Mio Fa Me Un' Favore," most of the songs of the Carmina Burana, which were written by freaking goliards (monk dropouts), for heaven's sake, a goodly number of the troubadour/trouvere works, and then there was that motet, "Hare hare hye/Balaam" that some French university students sang as they rioted over a tax on booze; gee, protest songs have gone downhill over the past few centuries...may I stop now, please?) Another response gave one example of a folk song having a tune going back to a medieval origin (I suppose in the way "Orientis partibus" morphed into "The Friendly Beasts"), apparently attempting to justify the performance of any and all "traditional" songs at Renaissance fairs.

Disclaimer the Second

Many of the groups that play very non-period music at Renaissance fairs do so with impeccable musicianship and showmanship, and when I can count them as friends, I do so happily and with great pride.

So...

On alt.fairs.renaissance, people will go on at great length about authenticity of language and clothing. I don't think people would excuse performers at Renaissance fairs dressed as slackers, goths, flappers, Gibson girls, or like Minutemen... (Well, they do excuse something similar in the "wench" attire. Cleavage trumps verisimilitude, I guess.) ...but they seem to tolerate the musical equivalent. I don't understand why. Period music can be just as raucous, risque, and outrageous as any other music—it's not all madrigals, chant, and isorhythmic motets—and there's got to be some way it can be sold to a modern audience. (Owain Phyfe does all right getting an audience by performing early music (and doing it exceptionally well); I wish I could sit and talk to him about it for a while.) If people don't want to hear early music, why is the market big enough to support a quarterly magazine about it these days?

Curious Signs

Some signs just strike me as odd. Long ago I saw a sign on a restaurant that read

ALL YOU CAN EAT
SHRIMP

Gee...if I were to take a short woman out on a date, would I go there? I think not!

More recently, signs on rest rooms are showing up that say

BABY CHANGING STATION

"Dear, we always wanted a girl...let's take little Bobby to the baby changing station!" (What's even worse is that the picture on one of the signs shows a baby elephant in diapers. You'd think Jeremy Rifkin would be protesting...)

So, is conclusion-jumping aerobic?

Some years back--back when the intercom in the complex worked--I called out for a pizza, and then went back to reading or whatever I was doing at the time.

About a half hour later, the heart-stopping shriek of the intercom made me jump. I followed the posted protocol: I hit the "talk" button and said "Hello?" No reply, save for the shriek of the intercom signal. I hit the "talk" button again and said "Hello?" No reply...and then another insanely loud beep.

I thought some joker was trying to be funny. I hit the "talk" button and said "Look, whoever you are; this isn't funny. Hit that button again and I'm calling the police." A few seconds and sure enough, it BEEEPed again.

Enraged, indignant, and not bothering to think that anyone who would harass someone might not draw the line there, and could be waiting for me with utensils of destruction, I stomped up the stairs and opened the door...to find a young man standing there with my pizza. After a few seconds of silence, I realized that he was deaf.

I paid for the pizza, inferred that the sign he made was "thank you" and repeated it to him, and headed down the stairs--thinking that the pizza place should perhaps have let me know and established some beep pattern to indicate that it was him upstairs, but mostly abashed at having leapt to a conclusion without sufficient data. I saw him a few more times when I ordered pizzas, and I wonder from time to time what happened to him.

Since then, initially largely because my now-wife was wanting to take the lessons but was hesitant to, and now because the subject is interesting and to prove to myself that I can still learn something, I've been taking ASL lessons. It's frustrating in parts. Spoken/written languages provide one with an enormous corpus of grammatical utterances of native speakers available at any time, but we have yet to find anything at all like that for ASL. The lessons have settled into a routine of the instructor signing us sentences that we parrot back, left to our own devices to figure out what was said. The sentences themselves are written by a person who, while skilled in ASL, is a hearing person--so that ASL is his second language and we're never sure whether we're getting what native ASL speakers would say is grammatical. (Indeed, our instructor, who is deaf, has looked at some of the sentences and looked less than pleased with them.)

So...frustrating as hell...but still worth it. At then end of our second ten-lesson session, the classes had a pot-luck dinner. I'd looked stuff up, and at what seemed like the appropriate time, at the table, with two instructors seated there as well, I looked to one of them and signed "I MUST ASK B-I-L-L-I-E IMPORTANT QUESTION. PLEASE CHECK MY SIGN." She nodded, and I looked at my now-wife and signed "YOU WANT MARRY ME?" About the time I got to MARRY people were looking and saying "He didn't sign what I think he signed, did he?" The opening of the case with the ring confirmed their suspicions, and the other instructor was in tears.

I was sufficiently nervous that I didn't even see Billie sign YES in reply, even though she'd been in on the ring design--after all, she was the one who'd be wearing it--and hence there was minimal surprise involved. She turned the brightest red I'd ever seen her turn. I'm very glad I asked then and in that way.

What Was It Like?

Remember the Great Folk Music Scare back in the 60s? That [stuff] almost caught on. --Martin Mull

I was five or six back then; the scare faded out in the early 60s in the face of early rock and surf music, and the British Invasion killed it stone dead, partly, ironically enough, with British groups feeding us back our own folk songs electrified.

I do still remember the stray Kingston Trio, Burl Ives, and New Christy Minstrels song, and Glenn Yarbrough singing "Baby, The Rain Must Fall" through my parents' Pepto-Bismol pink AC-DC tube radio, from back when even Top 40 radio had a vastly more eclectic mix than the focus group and demographics-driven sewer of today's commercial radio. I wasn't old enough to notice the irony of clean-cut college types raking in the dough via faux solidarity with migrant farm workers and coal miners. I just enjoyed it as music, and was blissfully ignorant of any message or emotion therein in my five or six year old way.

Fast forward about forty years...

A slightly stooped but quietly dignified man with a neatly trimmed beard walks into the coffee shop, carrying two guitar cases. (I haven't checked whether one has scorch marks on it from the last night at the coffee shop's old location--but that's another story.) He walks to the stage, acknowledging the greetings of the people who've come to hear the music, checks volume and reverb levels and tuning, and heads out for one last cigarette.

A few minutes later, in walks another man, as if the archetypal grandfather had decided to take a break from Plato's heaven-- though one doesn't think of the perfect grandfather as packing an electric bass and amp. He does the analogous greeting and setup, and then goes to the counter after a beverage.

The gentlemen in question are, respectively, Bob Cook and Gary Audsley. Their audience is reminiscent of a goldfish, growing to fit its container. At the old coffee house site, a proverbial hole in the wall in a suburban strip mall, if you wanted a choice of seat, you had to arrive at least an hour early. (I never got around to asking whether we'd be packed in oil or tomato sauce.) At the new site, there's a lot more room, and you don't have to arrive too early, but it's still pretty well full when the lights go down.

Once they take their respective stools and start playing, you forget about the stoop and Plato's grandfather, and get lost in the music and the images of sailors and hardscrabble farmers, railway men and highwaymen, gamblers and horse thieves. I figure that this what it must've been like during the scare.

It's over too soon--the one concession to time is that they stop at 11:30 rather than midnight. But you'll be back next time, the first and third Saturdays of each month (and fifth when it happens), at Starry Night--The Coffee Connection, now in Ankeny, Iowa.

P.S. Say, "Plato's Grandfather" would be a good name for a band...

lettinme be mice elf agin...

OK, I'll bite. What the bleep do I have to be thankful for? It's now over a year since I was laid off, and I'm now living off savings that were intended for my retirement while the places I apply for work either ignore me or send me little "thank you for playing" postcards.

Well...there are a few things. I'm not hospitalized with cellulitis the way I was last year, nor am I wearing a humongous leg wrap or on a continuous antibiotic IV drip. I still have a place to live... for now, anyway... and now I'm married to a wonderful, talented woman who loves me. (It's still a little hard to believe, even after a month an a half.) Could be worse. Enjoy your turkey, or tofu if you're vegetarian.

Didja Ever Notice How Irritating Andy Rooney Is?

As the holiday season approaches, so does one of my pet peeves. Not the "Let's start prodding people to Christmas shop on Labor Day" routine, though goodness knows I'm sick of that. No, this is one that comes up most fiercely around Easter, because there isn't quite as much shameless marketing as for Christmas, but I saw an ad yesterday that set me off.

The pet peeve is this: it's not "spiral sliced ham," dagnabit, it's HELICALLY sliced ham! If it were spiral sliced, it would unroll like a carpet. I know it's a hopeless cause...people still say "spiral staircase" after all these years...but I'll continue to fight the good fight.

Cable of Tomorrow...Like Yesterday's, but More Obnoxious

Digital cable sucks, for various reasons:

• It's yet another box requiring yet another outlet and another piece of coax and remote.


• It gives you all the joys of lossily compressed MPEG video.


• It returns you to the thrilling days before "cable ready" TVs and VCRs, and all the inconvenience of not being able to watch one show and tape another. You say you bought yourself a spiffy picture-in-picture TV? Too bad; it's worthless with digital cable.


• It's yet another thing you get billed for.

When I Was Your Age, Sonny, I Wound the Film Myself...

We're a little out of sequence here; apologies.

I was at the Iowa State Fair doing volunteer work-- photography for VSA Iowa. VSA Arts (a name created by the Dept. of Redundancy Dept., I guess, as VSA stands for "Very Special Arts") is an organization that promotes artists with disabilities. My fiancée (well, for the next month-- nervous? me?) schleps and rides VSA performers around the hilly and crowded terrain of the fairgrounds on a golf cart each year. They needed a photographer, and I was interested and [insert deity of choice] knows I have the time... sigh.

The photography was fun and educational; I was lent a camera and lens for the job-- actually the lens first, and the camera when it turned out not to work with my SLR. The educational part? The camera was a very non-automatic Pentax, with me lazy and used to my very automatic Minolta Maxxum 450si. I reviewed the definition of f-stop, and discussions of depth of field, and the operation of the camera... and it only took me one wasted roll to get into it. (Sigh of relief.)

It worked out very well, everyone was happy (though I'd have been happier if I'd been paid, and happier still if I could get a Minolta AF zoom lens like the one on the Pentax...), but that's not what I'm really wanting to write about.

One can find quite a few "oldies" groups at the Iowa State Fair; indeed, one of the regular events is the "Rock and Roll Reunion" at which a number of groups from the early sixties perform. It turns out that on the very last day of the Iowa State Fair this year, there would be two performances by... The Association.

I've not followed The Association over the years since their heyday, but I nevertheless love their music. They were masters of harmony and weren't afraid to take chances with tracks like "Pandora's Golden Heebie-Jeebies" and "Requiem for the Masses." They could rock-- "Six-Man Band" took the genre seriously, unlike, say, Peter, Paul & Mary's tongue-in-cheek "I Dig Rock and Roll Music" or any hit of the Fifth Dimension. ("Let the Sunshine In" is more gospel-influenced than rock.)

So...VSA Iowa didn't have anything going on that last afternoon, but it was around 5:15 p.m., most of the way through The Association's first performance of the day, before we made it to the stage they were on. As we approached, I was shocked to hear them doing covers of 60s R&B songs. WHAT?! They have a large and wonderful oeuvre; what the heck do they need to cover those songs for? I thought to myself. As the performance ended and people started on their way out, we noticed a couple of friends. "Did they do 'Pandora's Golden Heebie-Jeebies' or 'Requiem for the Masses'?" I asked. "No," came the reply.

After the first performance, the group (all clad in white suits) came out to greet people and sign things. No CDs or things for sale... I got in line, and when I made it up to the table I said I didn't have anything needing signing, but just wanted to thank them for lots of fine music. One of the group said thanks. I asked if there were any chance I'd hear... well, you know which two songs by now... and he said not tonight, but perhaps in a future performance. I thanked him again and went back to where my fiancee was. (I noticed that two of them were signing items with "aloha" and "mahalo"-- the latter means "thank you" and the former means, well, a lot of things-- and inferred that they were from Hawai`i.)

We had plenty of time to wait between sets, and plenty of spaces available to sit in, so we found a good spot, right in front of the sound guy, and waited.

Maybe half to two-thirds as many were there for the last show. They did the hits you'd expect, and some less well known ones ("Everything That Touches You" and a Dylan cover that was on their first album). The fellow who did much of the talking then said they'd like to do some of the songs that they sang backstage between shows, and they went into a string of R&B covers again. I certainly couldn't complain about how well they sang them, but it was nonetheless a disappointment. They returned to a hit for the close.

My fiancee wandered away to see about getting the sign insert for the stage sign that read "THE ASSOCIATION"-- after all, it was the last show and they would probably just be chucking it. She got there just in time and sweet-talked the maintenance people who had retrieved it into letting her have it.

After the last show, we walked back in hopes of getting the sign signed, but it didn't look like they were going to come out after this show. They probably had to be on their way ("...we just got the time to say hello and then a fast goodbye..."). Were it just me there, I'd have trundled silently away--but my fiancee is much better at these things than I am, and I think she tallked to the soundman and to one or two of the group... and eventually they all came out and signed. We responded with "mahalo nui" (thank you very much) to the two who signed with Hawai`ian, and got smiles as a result. I certainly appreciate their all taking the time.

Since that night, I've read some biographical information on the web. There have been personnel changes over time-- one of the members of the group we saw is a son of one of the original group members-- and one page refers to the name "The Assocation" being rented out to people to perform under. Goodness knows that one rather vehement fan site probably thinks ill of me for here referring to the group we saw as "The Association," but I can only say that this is as close as I expect ever to get to the live experience of The Association; the group members are all very good at what they do, and unfailingly courteous-- they certainly didn't have to take the time that they probably needed to be preparing to get back on the road to sign a lone fan's object saved from the dumpster. They have my appreciation and respect and thanks... but I wish they'd done more Association songs.

"After all the time we spent together/Just doesn't seem fair, no fair at all..."

P.S. It's interesting how quickly allusions and references become dated. In "Six Man Band," the "seventeen jewels that dictate the rules" and thus enslave the band to the clock and schedule are the jewels of an analog watch movement. How many people have analog watches any more, much less know their construction well enough to get the reference?