4. The Rite of Spring by Igor Stravinsky
5. Playing the Fool by Gentle Giant

In the summer of 1978, probably August, I spent two or three weeks staying with an aunt and uncle who lived in Québec City. While there I purchased a couple of LP's. By extreme coincidence they were the two listed above. I'm not sure which orchestra did The Rite of Spring. I checked this morning and, sadly, neither disk remains in my collection. I do, however, have multiple versions of the former on my iPod as well as the reissued version of the latter.

In 1978 I was nineteen and had just completed my second year of university at UBC. My first year was at the Okanagan College in Vernon, BC. During that first year I took a music appreciation course which must have been where I was exposed to the The Rite of Spring. The teacher of that course suggested to my friends and me that we might like Gentle Giant. How had she even heard of them? But was she ever right (for me at least, my friends stuck with big band jazz). I loved Gentle Giant's brand of pretentious progressive rock. They referenced RD Laing. They played the harpsichord. They were gargantuan. They played recorders. What was not to like?

I never got to see Gentle Giant in concert. By the time I was interested in them they weren't touring North America and were pretty close to breaking up. One of the guys at my residence at UBC had seen them play live. I think they opened for Yes. He said something about a dragon.

A decade or so ago (in the late 1990's) I went up to San Francisco and saw the San Francisco Symphony Orchestra perform The Rite of Spring under Michael Tilson Thomas. I thought I knew that piece of music very well. I'd listened to it regularly for twenty-plus years. I knew that piece of music. Ha! Watching it performed live was a revelation. I had chosen a seat close to and in front of the cello section (I was learning to play the cello at the time). I remember my astonishment at seeing waves of melody passing through the cellos. Themes that I had never consciously heard before.

I suppose I should make some pithy observation about those who listen but do not hear. But who would benefit from that? Me? I think not.

3. London Calling by The Clash

I generally have my iPod cycle through albums at random. On 5 January 2010 I read a posting on Boing Boing about the 30th anniversary of the release of London Calling in the United States. That very day it started playing during my commute home from work. It came up again today. I am listening to it as I write this post. Personally I think it has aged very well. It sounds as fresh to me now as it did when I first heard it on CITR when I was a student at UBC in the early 1980's.

Update:

I forgot to mention that I actually got to see The Clash in concert. They opened for The Who during their first farewell tour in 1982. This was at the Kingdome in Seattle. A friend drove a bunch of us there for the concert. I was not a fan of The Who but my friends were. I had heard that The Clash were opening and that was good enough for me. We were miles away from the stage. Up in the cheap seats. Even the huge screen showing the performers was too small to be seen clearly. The first act was, interestingly, T-Bone Burnett. I had never heard of him before. Later on he became a favourite. In part because he married Sam Phillips whose music I loved. I don't really remember anything about the music. I believe I was underwhelmed by The Clash. I didn't know much about The Who. Their music washed over me and left me unchanged.

Since that was The Who's farewell tour and I was there I have refused to listen to anything by them ever since! Why no, I am not vindictive. Heh.

Final Update:

While I remember almost nothing of the music I heard at this concert I do have two very clear memories: one from before and one from after. My friends and I were living at a residence on UBC and the cook there made us all bag lunches to take along since we would be missing dinner that night. We waited outside the Kingdome for a while until they started letting people in. When it was our turn to enter, the security guards made us throw away our bag lunches. I guess they were worried we'd start throwing apples at people or something.

On the way home, being quite hungry, we stopped at a restaurant that was open late. Some kind of fast food place no doubt. In the parking lot was one of my friends from Vancouver who had also driven down for the concert.

Those two memories are very clear. Everything is kind of blurry.

I still like the Clash...

2. Six Suites for Unaccompanied Cello by J.S. Bach

Judging by the number of recordings I have of this music it is a huge favourite. Here's a partial list of artists I have playing one or more of these suites:

• Jaap Ter Linden
• Pieter Wispelwey
• Anner Bylsma
• Pablo Casals
• Janos Starker
• Yo-Yo Ma

When I studied cello (for about five years in the mid-1990's) I reached the point where I could play most of the first suite. I still have the score Karen, my teacher, and I marked up with fingerings. I don't think I will ever have the time or energy to pick up the cello again but I am happy that I was able play some of them.

My cello teacher played the first suite during my wedding reception at Hakone Gardens in Los Gatos in August of 1999. My wife and I had wanted her to play it while we were walking down the aisle but, well, I don't really remember why she wouldn't.

1. Historical Anthology of Music (volume I).

I have played the recorder off and on since the mid-1990's. I first encountered this book when my teacher gave me a photocopy of piece number 49, a madrigal by Jacopo da Bolgna. I believe I first played it on a Baroque alto in F.

When my son was born (premature and with issues) in 2000 I dropped almost all my extracurricular activities. I stopped all music lessons (voice, cello and recorder) and focussed on my wife and child. I started playing the recorder again about three years ago and restarted lessons (with the same teacher; thanks Carol!) about six months ago.

I recently revisited this piece. This time I am using it to learn to play the Renaissance alto in G. I also now have my own copy of this book and it is full of wonderful music. I suspect it will be a constant companion during 2011.

John Terauds of The Star proposes this challenge:

What are the 100 pieces of music -- including full operas -- that we simply can't live without in 2011?

Thinking about the music that I love has brought back memories of where I was and what I was doing when I first heard the piece. I'm going to try and capture some of those thoughts in a few posts about the music that is meaningful to me.

I'm going to talk about the music that I play (or have played) as an amateur musician as well as the music that I listen to a lot on my iPod. I will not claim that the music I discuss is significant to anyone other than me. Also, I will be listing pieces in the order in which they occur to me.

The next Project Euler problem I want to tackle is number 22:

What is the total of all the name scores in the file of first names?

The file in question contains data that looks like this:

"MARY","PATRICIA","LINDA","BARBARA",...

It's a nice list but I will need to clean it up to get it into a form that is easy to process. To that end I define a couple of helper functions. These allow me to use .NET's Regex class in a more functional manner:

open System.Text.RegularExpressions

let split pattern input =

    (new Regex(pattern)).Split(input)

let replace pattern (replacement:string) input =

    (new Regex(pattern)).Replace(input, replacement)

The value for a name is computed by adding the values for each letter ( a = 1, b = 2, c = 3, etc.). This is pretty easy in F# because a string can be treated as a sequence of characters. Thus the value of a name can be computed like this:

let value (name:string) =

    name |> Seq.map (fun c -> (int)c - (int)'A' + 1) |> Seq.sum

All the names in the file are already in uppercase so we don't have to do any normalisation there.

Once all the names have a value I need to compute a score for each name. This score is the name's value multiplied by its position in the alphabetically sorted list.

So, in words, here's what we do:

1. Read in the names.
2. Sanitize them by getting rid of the extraneous quotes.
3. Split the resulting string into an array of name strings.
4. Sort the array.
5. Compute the score for each name.
6. Sum the resulting scores.
7. Display the result.

Using the previously defined functions this algorithm translates directly into F# code:

open System.IO

File.ReadAllText(@"e:\Project Euler\names.txt")

    |> replace "\"" ""

    |> split ","

    |> Array.sort

    |> Array.mapi (fun i name -> (i + 1)*(value name))

    |> Array.sum

    |> printfn "total = %A"

The twenty-first Project Euler problem is:

Evaluate the sum of all amicable pairs under 10000.

An amicable pair is two numbers such that the sum of the proper divisors of the first number adds up to the second and vice versa. Each member of the pair is considered to be an amicable number. As always Wikipedia has a good article on the subject.

Following the suggestion from the statement of the problem I define a function d(n) that computes the sum of n's divisors:

let d n =

    {1..n/2} |> Seq.filter (fun i -> n%i = 0) |> Seq.sum

Now I need to test whether a given number is amicable:

let amicable n =

    let sum = d n

    (sum <> n) && (d sum = n)

Note that we exclude so called perfect numbers where the sum of n's divisors is n.

Finally, I can compute the sum of all the amicable numbers under 10,000 as follows:

{1..10000} |> Seq.filter (fun i -> amicable i) |> Seq.sum |> printfn "total = %A"

Numerically, the next Project Euler problem is number 20:

Find the sum of digits in 100!

Hmmm... what to do, what to do? Well, as always, lets start with the helper functions. 100! is a very big number. Thus we will have to use F#'s BigInt type. Here's a factorial function:

let factorial n = Seq.fold ( * ) 1I [1I .. n]

Of course, F# already has a factorial function for BigInts but since this is a learning exercise I felt that I had to write my own.

Next I want to turn a big number into a series of digits. This is the function I used for that purpose in my solution to problem number 16:

let rec digits n =

    seq {

        if n > 0I then

            yield n%10I

            yield! digits (n/10I)

    }

Finally we can put these together to create a solution:

factorial 100I |> digits |> Seq.sum |> printfn "sum = %A"

On my computer I get the answer in less time than it takes to threaten the monitor with my fist.

The next Project Euler problem on my list is number 19:

How many Sundays fell on the first of the month during the twentieth century?

For this problem it seemed to me that the easiest attack would be to create a sequence containing all the first days of each month in the given range and then filter it by testing whether the day in question was a Sunday. To make this work I would need a way of calculating the day of the week from the date. Fortunately, once again Wikipedia came to the rescue.

Following the algorithm from this article we define a few helper functions. To calculate the century we say:

let century y = 2 * (3 - (y/100)%4)

To determine whether we have a leap year:

let leap y =

    if y%400 = 0

        then true

        else

            if y%100 = 0

                then false

                else

                    if y%4 = 0

                        then true

                        else false

For the month table I used a pattern match expression which takes the month number and whether it's a leap year or not:

let month l m =

    match m with

    |  0 -> if l then 6 else 0

    |  1 -> if l then 2 else 3

    |  2 -> 3

    |  3 -> 6

    |  4 -> 1

    |  5 -> 4

    |  6 -> 6

    |  7 -> 2

    |  8 -> 5

    |  9 -> 0

    | 10 -> 3

    | 11 -> 5

Note that this match generates a warning to the effect that there are cases which may not be covered:

      match m with
  ----------^
stdin(19,11): warning FS0025: Incomplete pattern matches on this expression. For example, the value '12' may indicate a case not covered by the pattern(s).

In this case I am controlling all the inputs and I know that I would never make a mistake so I decided not to worry about it.

Next I needed to compute the year value:

let year y = y%100 + (y%100)/4

With these helpers, given a date tuple in the form (y, m, d) the day of the week it falls on is given by:

let day (y, m, d) = (century y + year y + month (leap y) m + d)%7

In this scheme Sunday is day 0.

The list of dates I want to examine are given by this sequence:

let dates =

    seq {

        for y in 1901..2000 do

            for m in 0..11 do

                yield (y, m, 1) }

Putting the pieces together to solve the puzzle:

dates |> Seq.filter (fun x -> day x = 0) |> Seq.length |> printfn "count = %A"

Returning to my irregularly scheduled series on Project Euler solutions I'd like to look at problem 18:

Find the maximum sum travelling from the top of the triangle to the base.

Here is a little example:

1

3 2

4 1 6

I have marked the maximum sum with red numbers. For a small triangle of numbers like this you could easily brute force the solution and just check all paths from the top to the bottom. For a large triangle, that would be too labour intensive. A better solution, I think, is to coalesce the rows of the triangle working from the bottom up. So, in this simple example, you would first replace the second row with the maximum value possible by adding a number in that row to the two numbers below it in the triangle. In this case, 3 + 4 > 3 + 1 so you would replace 3 by 7 and 2 + 6 > 2 + 1 so you'd replace 2 by 8. That would reduce the triangle to this:

1

7 8

Performing the same step on the reduced triangle would give you the final answer (since 1 + 8 > 1 + 7).

9

To solve this problem I put the data into an array of arrays:

let data =

    [|

    [|04; 62; 98; 27; 23; 09; 70; 98; 73; 93; 38; 53; 60; 04; 23|];

    [|63; 66; 04; 68; 89; 53; 67; 30; 73; 16; 69; 87; 40; 31|];

    [|91; 71; 52; 38; 17; 14; 91; 43; 58; 50; 27; 29; 48|];

    [|70; 11; 33; 28; 77; 73; 17; 78; 39; 68; 17; 57|];

    [|53; 71; 44; 65; 25; 43; 91; 52; 97; 51; 14|];

    [|41; 48; 72; 33; 47; 32; 37; 16; 94; 29|];

    [|41; 41; 26; 56; 83; 40; 80; 70; 33|];

    [|99; 65; 04; 28; 06; 16; 70; 92|];

    [|88; 02; 77; 73; 07; 63; 67|];

    [|19; 01; 23; 75; 03; 34|];

    [|20; 04; 82; 47; 65|];

    [|18; 35; 87; 10|];

    [|17; 47; 82|];

    [|95; 64|];

    [|75|]

    |]

You will notice that I inverted the triangle so that the widest part is at the bottom. I wanted my algorithm to proceed from the start of the array to end and not vice versa.

Next I defined a helper function:

let max x y = if x < y then y else x

Now I want a function that will coalesce two arrays into one:

let coalesce (a:int[]) (b:int[]) =

    [| for i in 0..b.Length-1 -> max (a.[i]+b.[i]) (a.[i+1]+b.[i]) |]

So, the idea here is that two one-dimensional arrays are passed in. The first one is assumed to be one longer than the second (in production code you'd probably want to enforce the precondition). This function creates a new one-dimensional array with the same length as the second input array. Each entry in the new array is the max of the entry in the second array with either of the numbers above it in the first array.

Finally, I want to apply the coalesce operation to the entire data array:

data |> Array.fold coalesce (Array.zeroCreate (data.[0].Length+1)) |> printfn "%A"

I have created an array with length one greater than the maximum line in the data array and I'm using that as the state accumulator passed to the fold function. At each step in the fold operation it will be replaced by an array one entry smaller until, when it's done, there will just be an array with a single element which will be the final answer.

I should note that one potential problem with this solution arises if you want to know the actual path that led to the answer. 

Many years ago, in the late 1980's when I lived in Vancouver, I took night school courses to learn conversational Cantonese. I stopped when I moved to California in 1990 and all the vocabulary I acquired then has been slowly eroding. However, my previous post on spelling out numbers reminded me of how one says the numbers in Cantonese. Here are the numbers with their Chinese character and Cantonese pronunciation:

one	1	yāt	一
two	2	yih	二
three	3	sàam	三
four	4	sei	四
five	5	nǵh	五
six	6	luhk	六
seven	7	chat	七
eight	8	baat	八
nine	9	gáu	九
ten	10	sahp	十

Subsequent numbers are built logically from these. For example, eleven (11) is 十一, twenty-one (21) is 二十一 and thirty-one (31) is 三十一. In Cantonese you would pronounce 三十一 as "sàam sahp yāt".


A program equivalent to the one that counted the number of letters in the English spelling of numbers would probably count the strokes of the Chinese numbers. It would have a lot fewer special cases than the program I presented earlier.


I use the Yale Romanization for Cantonese since that's what I was taught long back. There is a lot of information about Chinese Numerals online.