Answered Prayer and Handbags

As a Christian, I believe that God hears and answers prayer. In fact, I don't just believe it, I know it from my own experience. Now I might wish to have some miraculous episode to recount to convince you too; but perhaps it says more about the character of God that my most vivid memories of answered prayer concern Handbags.

The Handbags in question both belonged to my wife, though at the time our concern was that they'd transferred their allegiance elsewhere. The one incident, that prompted this post, is still making itself at home in my memory - it happened just after Christmas.

Noted and forgotten

We'd just finished the shopping at our local supermarket and I was charged with unloading the trolley while my wife visited the Ladies'. As I put the last carrier bag into the boot of the car, I noted the handbag in the front of the trolley. "Musn't forget that", I thought, as I pushed the trolley to join its companions in the trolley shelter.

My wife rejoined me in the car.

"Got my handbag?", she asked.

"Mmm", I replied [I'm grateful to my wife for filling in this part of the story, because I have no memory of it].

It wasn't until several hours later that my usefully ambiguous reply turned out, in this case, to mean "No!", rather than the "Yes" my wife had assumed at the time. We were on the way out of the house laden with platefuls of pizza, our contribution to the Sunday School Christmas party.

"You better just leave your handbag, Mummy", our three-year old daughter insisted, anxious to get to the party, as Mummy hunted in all the places that handbags sometimes get dumped. "It will be alright", she added, innocently. My wife wasn't so naive.

"If we can't find it, someone will have to stay behind to cancel the credit cards."

Since there were only two someones eligible for the task, and the female was being dragged by the non-eligible someone in the direction of the party, I remained behind. Prayer was my first resort, and a heartfelt "Help, Father!" ascended heavenwards. A second search of house and car yielded nothing. "Nothing", was also the answer I got when I phoned customer services at the supermarket to ask if anything resembling a handbag had been handed in.

So I set to work calling up the credit card companies (optimistically asking for only a temporary block to be placed on the cards) and googling to find out the procedure for replacing lost National Insurance cards and Photocard Driver's licenses.

But I felt I couldn't leave it at that. I looked in on my wife and daughter, daughter enjoying the food at the party, wife forcing the appearance of enjoyment, then I set off on the 15 minute drive back to the supermarket.

I didn't have much hope of finding anything, but I wandered round the car park, mobile in hand, repeatedly dialling my wife's number in the hope of hearing an answer from the phone that, opportunists aside, would still be tucked in her bag. I would have paid to hear the cheery Nokia jingle on this occasion: but no such joy.

Hope pretty much gone at this point, I headed into the store to try Customer Services one last time. Then, what to my wondering eyes should appear but my wife’s handbag, open on the Customer Services desk with the Assistant staring bemusedly at the mobile phone she had just fished from it.

“I couldn’t work out how to answer it”, she explained, as I introduced myself as the rightful co-owner of the lost property she held in her hand. She remembered me from my phone call to the store earlier in the evening. Then she confessed that the bag had in fact been behind the desk all along, but she had just that minute found it after disposing of a bag of rubbish that had been stuffed in front of it.

Happy coincidence? I know what I think. But before you reach your final conclusion, let me tell you about Handbag number 2.

A Handbag takes a holiday

This one had accompanied us on holiday to Torquay, in the English Riviera. It stuck with us faithfully throughout the week until the day we visited Cockington, a picturesque, Olde Worlde village a few miles out of town. To preserve the charm of the place they direct all drivers to a car park on the outskirts, from whence they’re instructed to savour the peace as nature intended: on foot. The parking charges paid by the choiceless motorist no doubt go towards preserving the structure of the village.

As I manoeuvred the car into an empty space, my wife bent down in her seat to fish her purse out of her bag. She fished in vain. It was pointless asking her to look again: not even the rubbish that accumulates in the front of our car during a holiday could conceal a handbag as over-stuffed as my wife’s. So I went to the back of the car, and started turning out the boot – also in vain.

Since our daughter – about 18 months at the time – would not appreciate leaving when having barely arrived, my wife remained with her to look around the village whilst I retraced our tracks. Back to the car park down by the harbour; back to the cafe overlooking the sea where we had so lately enjoyed a carefree coffee; back to the car park again. No customer service desk this time; but a Harbour Master just as capable of delivering the lines: “Sorry sir – nothing’s been handed in”.

I was just about to begin a second round when my phone rang. Expecting it to be my wife ringing for the third time to check on my progress, I was instead greeted by my Aunt, calling from back home.

“Afternoon Sam! Has Rachel lost a handbag?”

I wasn’t quite speechless.

“Yes! But how do you know?”

So she explained the convoluted story. Whilst answering phones on the reception desk at our GP surgery where she works, she’d received a call from my wife’s Health Visitor. The Health Visitor needed to get in touch with Rachel Jack, she told my Aunt; she didn’t have a contact number, but she’d remembered that my Aunt was a relation, so could she pass on a message? The message was from a hotel receptionist in Torquay. Apparently, a passing pedestrian had handed in a handbag containing, amongst other things, a purse within which was a Drivers license belonging to a “Mrs Rachel Jack” – but only the telephone number of the Health Visitor on a torn off page of a notebook.

I could hardly believe my ears. To think that all the time I had been making my fruitless enquiries the handbag had been safe and news of it had been on its way to me by this circuitous route!

Having received details of the hotel I set off post-haste to see if this could really be true. When I arrived at the reception desk, I could only stutter my thanks to the diligent girl who had gone right through the bag to find that single scrap that could connected her, by such an unlikely chain, with the owner. And she solved for me the one remaining mystery: how did the bag come to be outside the hotel, half a mile down the road from the habourside carpark?

The anonymous pedestrian, the receptionist said, had seen the bag fall from the roof of the car just outside the hotel. Relating this a few minutes later to my marvelling wife, she remembered that she had placed the bag there as she leant inside the car to strap our daughter into her seat, just before we left the car park. And somehow it had stayed put, until it fell, to be picked up, contents still intact, by the model citizen.

I don’t need to tell you how thankful we were, not only to her (regretfully we never had chance to express it), to the receptionist in the hotel, to my wife’s Health Visitor, and to my Aunt, but to the One who oversaw the whole episode, and “worked all things together for good”.

Now I don't want to give the impression of a God who operates a divine lost property service. The Son of God came into the world to look for and save people who are spiritually lost, rather than things that are carelessly lost by absentminded geeks and their wives. But if God can take care of ours, surely we should take him seriously when he offers to take care of us?

functional => prizes #1

Ladies and Gentlemen, roll up, roll up for the first ever Functional Fun programming competition, where Functional => Prizes.

Many moons ago, at the Microsoft PDC, I won a copy of Windows Vista Ultimate; said software being superfluous to my requirements, I held an auction, and I now have a pot of dosh which I intend to distribute via this blog. And what better way to do that than to hold competitions? Hopefully the stash will stretch to cover a couple throughout the course of the year, so stay subscribed.

Almost a year ago, I launched this blog with a series of posts on solving Project Euler. This competition gives me a chance to turn the tables and try my hand at problem setting.

Thus without further ado:

The Puzzle

Which Mathematicians have found themselves prime positions in the grid below?

You’ll probably want to download this grid in text form.

The Rules

1. All solutions must be emailed to (samuel [dot] jack [at] gmail [dot] com) before Midday (GMT) February 4th 2009.
2. Don’t just give the answer (I’ve already got a pretty good idea what it might be!): what I want to see is code - especially code that goes all the way from input to final answer.
3. The prize will be awarded, not to the first correct answer, but to the solution which, in the opinion of the judge, is the most elegant.
4. Competitors should be aware that C#, particularly in its Version 3 and 4 incarnations, tops the judge’s elegance rankings; this is not to dissuade them from making entries in other languages – merely to let them know that if they choose to enter using an inferior alternative language they’ll have to work harder to make the elegance apparent.
5. The prize will be £25 in Amazon vouchers – but if you are lucky enough to win, and unfortunate enough to live in one of those foreign places (you know, the kind that get rid of their Head of State every few years, and have to choose a new one) then I’ll do my best to accommodate you with a prize in your local currency.
6. If you submit a solution, but think you can better it, don’t hesitate to send another.

Your Choice

Now what are you going to do?

A. Keep quiet about the competition in the hope of increasing your chances of winning?

B. Tell as many of your closest friends as possible in order to increase the publicity and your standing in the community when you win the Inaugural Functional => Prizes challenge?

Nothing new under the sun

With a new member of the household arriving mid-year, we’re in the process of re-purposing the room in our house that, outside of the family we call The Study, but between ourselves we refer to as The Junk Room. Our daughter is looking forward to a pink-themed makeover, with Fifi stickers on the walls; she won’t appreciate sharing with the quantity of books that we have in there.

As we were discussing where we could re-house our mini library my wife had sudden inspiration.

“Why doesn’t someone start a book rental service, like Love Film do with DVDs?”

A pause.

“Ah – that would be a library!”

Windows Vista Ultimate for Sale

Remember that I won a copy of Windows Vista Ultimate at the PDC? Well now I’m auctioning it (in the UK of course).

If any reader wins the auction, let me know, and I’ll include a Functional Fun business card as a bonus :-)

All part of my cunning plan that I hinted at earlier.

Too close for comfort

There was a robbery at the Post Office in the village neighbouring ours this morning. The Post Master was shot in the leg; his son was shot dead. One media account described this as “an armed robbery gone wrong” - as if armed robbery ever goes well! The Daily Mail has the full story.

This is tragically far from unique in the UK, even less in other parts of the world. There are many innocents caught up in ongoing or recurring conflicts around the globe. Murder is perpetrated on a larger scale all too frequently. And when I read of these events I do feel a genuine mental sympathy for the victims. But for some reason this has touched me emotionally in ways that other events have not.

It’s not I feel any more afraid. True, the police did seal off the area, and there were helicopters hovering over the village for the best part of the morning. But Fairfield, where the event took place, is about five minutes drive from the intersection of two Motorways; the robbers could have been a county away within half-an-hour of the crime.

I think its the psychological power of our proximity to the place and those involved that is at work. The Post Office is less than a mile from my house, as the crow flies. I’ve used it myself on several occasions, and was probably served by those involved. And our daughter was at pre-school just around the corner from the place, my wife having dropped her off 40 minutes after the episode, though unaware of it at the time.

So I find myself recalling that I was just arriving at work at the same time the poor man was shot; wondering what thoughts the hapless pair had to themselves as they opened up shop this morning. And trying to imagine the feelings of the Fiancée of the dead man: what must be going through her mind at this very moment?

I guess there’s good reason why the phrase “it brings it all home” has settled itself as a cliché in our language.

My prayers are with the victims, and with the authorities that the perpetrators will be brought swiftly to justice.

Project Euler 89: Converting to and from Roman Numerals

It would not surprise me at all to learn that the Roman Numeral system was invented by a Stone Mason with one eye on his retirement fund. As he charged per character chiseled he could expect a substantial fee whenever called upon to inscribe numbers; dates on tombstones were even better, because on the whole he could expect the length of the inscription and thus the fee to increase as the years progressed.

Everybody knows how the Roman Numeral system works, though the only time we usually get to show off our skills is when the end-credits roll on the the big or small screen and the date of film or programme production flashes up. It consists of 7 symbols, each standing for a value:

Numeral	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

A number in Roman Numerals is just a string of these numerals written in descending order (e.g. M's first, followed by D's, etc.). To convert from Roman Numerals to decimal we just work through the string, adding up the values of the numerals. So MMVIIII represents 2 x 1000 + 1 x 5 + 4 x 1 = 2009.

The only complication is the subtractive rule. This rule makes it possible for some numbers to be written in a more compact form (I'm sure archaeologists will one day unearth a document recording the protests made by the Mason's Union on its introduction!). It allows a numeral of a lower value to be placed before one of a higher value to indicate that the lesser should be subtracted from the greater. Thus IV means 5 - 1 = 4, and XC = 100 - 10 = 90. Unfortunately, it's not quite that simple. According to PPI MMDCL¹, only I, X and C can be used subtractively, and then only in front of numerals up to ten times as big. So I can only be used in front of V and X, X in front of L and C; and C in front of D and M.

Converting Numerals to Decimal Programmatically

It's the subtractive rule that stumped me at first when I tried to figure out an algorithm to parse roman numerals. It certainly makes things complicated if you think about parsing the string from left to right. But as soon as you start thinking backwards, that is working from right to left, the difficulty evaporates:

1. Split the string into characters
2. Convert each character into the value it represents
3. Start from the right - the lowest value numeral
4. Keep a running total, and a record of the maximum numeral encountered so far
5. Take characters one by one:
   1. If character is greater than the maximum, add it to the running total and update the maximum
   2. If character is less than the maximum, subtract it from the running total

This converts straight-forwardly into LINQ:

public static int ConvertToDecimal(this string numerals)
{
    var result = numerals
        .ToCharArray()
        .Reverse()
        .Select(c => _numeralToNumberLookup[c.ToString()])
        .Aggregate(
            new { MaxValue = 0, RunningTotal = 0 },
            (state, item) => new
            {
                MaxValue = Math.Max(state.MaxValue, item),
                RunningTotal = item >= state.MaxValue ? state.RunningTotal + item 
                                                               : state.RunningTotal - item
            }, 
            aggregate => aggregate.RunningTotal);

    return result;
}

You'll note that I'm using an anonymous type in my call to Aggregate to allow me to record both pieces of state. Notice that I have to seed the call to Aggregate with an empty instance of the anonymous type (line 8). The C# compiler makes this possible by ensuring that any anonymous type that has properties with the same name and type and in the same order as another anonymous type actually become the same type. This overload of Aggregate also requires a lambda expression that extracts the overall result from the final aggregate object.

Converting Numbers to Numerals (with added recurserators!)

So that's Parsing taken care of. What about turning a number into numerals?

The algorithm isn't much more difficult, though the implementation I've chosen is a little unusual. The algorithm is recursive. We start off with the number we want to convert, and a stack containing the values of all the numerals that are available to us, greatest on the top. This stack includes the values of "composite numerals" - pairs of numerals that follow the subtractive rule, for example, 4 (IV), 9 (IX) and 40 (XL). In each iteration we peek at the numeral value on the top of the stack and test to see whether the number is divisible by it. If it is we've got us some numerals - we produce part of the final numeral string by looking up the appropriate numeral(s) and repeating them as many times as the number is divisible by the numeral value. If not, we recurse anyway. To recurse, we pop the top numeral off the stack, and pass the reduced list of numerals through to the next iteration, along with the remainder of the number after dividing by the numeral value. We terminate the recursion when we are asked to convert number 0 - which can't be done in roman numerals. If you understood all that, you have permission to skip the next paragraph; otherwise read on for a worked run-through of the algorithm.

For example, suppose we want to convert 2051. We start with the complete list of numerals: { 1000, 900, 500, 400, ... 50, 40, 10, 9, 1}. Peek at the first numeral value, and discover that it's 1000. 2051 is 2 x 1000, with remainder 51. Looking up 1000 in our numeral dictionary yields "M", so the first part of the numeral string is "MM". We're done with that iteration, so we remove 1000 from our list of numerals, and pass the smaller list, and the remainder 51 to the next iteration. The next few numeral values {900, 500, etc.} don't divide into 51, so we keep popping numerals, passing remainders and recursing till we get to a numeral list starting {50, 40, ...}.  51 is divisible by 50 (so we deduce that the next part of the numeral string is "L"). We then pop, pass and recurse until the number 1 is given for conversion, and the numeral list just contains {1}. At this point we add numeral "I" to the result, recursing hits the terminating condition, so we stop.

Now for the implementation. I could have used a straight-forward recursive function: I did this with my solution to Problem 31 (Counting Coin Combinations) which had a similar algorithm. But my Lazy Trampoline hasn't seen much action recently, so I decided to give it a bounce. The idea of the Lazy Trampoline is to create a recursive function that is able to yield a result after each iteration - a recurserator, you could call it.

It looks like this²:

public static string ConvertToNumerals(this int number)
{
    Func<int, IStack<int>, IEnumerable<string>> numeralsEnumerator = Trampoline.MakeLazyTrampoline((int numberToConvert, IStack<int> availableNumerals) =>
    {
        if (numberToConvert == 0)
        {
            return Trampoline.YieldBreak<int, IStack<int>, string>();
        }

        int currentNumeral = availableNumerals.Peek();

        int quotient = numberToConvert / currentNumeral;
        int remainder = numberToConvert % currentNumeral;

        string numberAsNumerals = _numberToNumeralLookup[currentNumeral].Repeat(quotient);

        return Trampoline.YieldAndRecurse<int, IStack<int>, string>(
            numberAsNumerals, 
            remainder, availableNumerals.Pop());
    }
    );

    var result = numeralsEnumerator(number, _availableNumerals)
             .Aggregate(
                new StringBuilder(),
                (sb, numerals) => sb.Append(numerals),
                sb => sb.ToString());

    return result;
}

The call to MakeLazyTrampoline (line 3) generates an iterator (numeralsEnumerator). Each item in the sequence generated by the iterator is a string consisting of one type of numeral. These are all combined by the query starting line 23 to create the complete numeral.

Within the recurserator, note that I return special values generated by Trampoline.YieldBreak and Trampoline.YieldAndRecurse. These control the behaviour of the recurserator. YieldBreak indicates that the recursion should stop now; YieldAndRecurse indicates (as its first parameter) which value should be returned in the sequence, and (in the second and third parameters) which values should be passed through to the next iteration.

It may have slipped under you radar, but in Line 15 I'm making a call to the Repeat method which doesn't exist on the String class. Here's the missing extension method definition:

public static string Repeat(this string value, int count)
{
    if (count == 0)
    {
        return string.Empty;
    }
    
    if (count == 1)
    {
        return value;
    }

    return Enumerable.Repeat(value, count)
        .Aggregate(new StringBuilder(), 
        (aggregate, item) => aggregate.Append(item), 
        aggregate => aggregate.ToString());
}

Solving Project Euler Problem 89

Project Euler Problem 89 gives us a file containing a load of numbers in Roman Numeral form, and asks us to calculate how many characters can be saved if the numbers are compacted using the subtractive rule. Given the two extension methods we've just implemented, the solution is a simple pair of LINQ queries:

[EulerProblem(89, Title = "Develop a method to express Roman numerals in minimal form.")]
class Problem89
{
    public long Solve()
    {
        var lines = File.ReadAllLines("ProblemData\\Problem89Data.txt");

        var numberOfCharacters = lines.Select(line => line.Length).Sum();

        var minimisedNumberOfCharacters = lines
            .Select(line => line.ConvertToDecimal())
            .Select(number => number.ConvertToNumerals())
            .Select(numerals => numerals.Length)
            .Sum();

        return numberOfCharacters - minimisedNumberOfCharacters;
    }
}

The full code is available, as always, on the MSDN Code Gallery page. Hope you like it Saevar.

Footnotes

1. PPI - Prex pro Ineo. ie Request For Comment! Thanks, InterTran!
2. Thanks again to Eric Lippert for his Immutable Stack code.