favorite regular expression

It was clear in one of my philosophy classes at UNH that I was doomed to be a computer nerd even though I was already in the major. It was a class in deterministic and finite autonoma. Actually it was more about Turing machines but the teacher made us write little machines expressed as autonoma without getting into the theory. I loved it. I ate it up.

So it’s little surprise that I love regular expressions. My favorite regular expression has to be this one (expressed using Perl syntax):

$line =~ s#^s*(.*S)?s*$#$1#;

[ Thanks to a reader for correcting this--I forgot the $1 in the replace portion of the regex. ]What does this do? Well, let’s step through it.

$line =~ s{

^s*                  # slurp up all the whitespace at the beginning of the line
(.*S)? # starting at non-whitespace character match everything up to a non-whitespace
s*                      # slurp up all the whitespace at the end of the line
$                            # match end of line
}{

$1     #                 replace entire line with what you matched between the whitespace at beginning and end of line
}x;

key to all of this is the (.*S)? line. The trailing S insures that the match ends with a non-whitespace character. The previous line, ^s*, insures that the next line also starts with a non-whitespace so you are matching the first non-whitespace character to the last non-whitespace character. Neat! Note, that if the line just has whitespace, the (.*S)? is optional because of the ‘?’ and the regex still matches and just strips all the whitespace out of the line.

So this regex removes leading and trailing whitespace from a line of text. Very useful for normalizing input.

Oleana: Review

I’m not a foody.

But restaurants like Oleana in Cambridge make me wish I was. My friends Jane and John took me there for dinner. I recently helped Jane with some computer problems that John had no desire working on. He’s a proud Mac user, which I am now too, who didn’t want to learn Window’s eccentricities to address her problems (backups schedule of a couple things). I just recently started forgetting Windows with the glorious purchase of my MacBook Pro, but I remembered enough so I could still help her out.

Anyway, back to dinner. Simply put Oleana was the best dinning experience I’ve ever had. The ambiance, the food, the service and the company were tops. For my entree I ordered the pan seared Tuna which was a delight. Compared to the standard serving size for food in the US one might be disappointed, however the complexity and variety of tastes in the serving far exceeded the quantity of food on the plate. Quantity vs. Quality my friend. I took the server’s advice and had the glass of San Alejandro ‘Baltasar’ (a Tempranillo/Syrah from Span according to the online menu). Red wine with tuna? Faux pau perhaps, but I love reds much more than whites. It was fantastic. It was smooth and obviously it had breathed before it was served. My last experience I had was a house wine at a restaurant in Quebec that was barely a cooking wine so this was a pleasant change.

John had the Sole which was simply fantastic. He took one bite and paused, smiled, put down his fork and said “pardon me while I bliss out.” I couldn’t turn down his offer, when he made it, after such a reaction. He was right, it was complex but yet cooked to perfection dissolving in you mouth.

Jane had the vegitarian plate which is 5 separate courses of vegitarian dishes. It’s up to the whim of the chef what the dishes are so I can’t look it up on the menu. It was a generous amount of food and it was remarkable from the starting dish of olives with garlic squash with olive oil to the very end (I can’t remember that dish, by then I was overwhelmed).

One appetizer stands out, the Grilled Haloumi. I never heard of this cheese before. But the saltiness of it combined with the grape leaves were in great harmony with each other. As a non-foody nor a food reviewer I find it cheesy to describe food with cliche words. But, nonetheless what choice do I have if my pallette of words are underdeveloped.

Onto dessert. I’m going to focus on my dessert because it was overwhelming (there’s that word again). I had the Baked Alaska. Wow. First how is that done? How is the meringue cooked and slightly browned whiled the ice cream inside doesn’t melt? I dunno. Defies me. By this time in the dinner I shouldn’t have been surprised by the continued excellence. I should have just accepted it as the norm. But I’m glad I couldn’t. The Baked Alaska was delicious ending to a meal. The cookie at the base grounded the dish in the nostalgic familiar which gave me the foundation to be completely taken by the hot meringue coupled with the ice cream inside. Yum. Yum. Yum.

Thank you Jane. We are definitely even. Although I may go into debt–I have to go back to Oleana.

Mood Rings and Technology

OK back to the whimiscle.

I meet weekly with my friend Tim to get some life coaching. He and I have a bargain–I need the advice and he needs the practice. Right now I think we are both pleased with the results.

In our last meeting we were discussing the wesite Stumbledupon.com which uses feedback from websites you’ve rated to recommend other websites.  But, I complained, it doesn’t take in account my mood. If I’m in a whimiscle mood so I really want to read the world headlines from CNN? If I’m sad  I want to read uhh..the headlines from CNN? Anyway you get my point! No! What we need, I decided, is a bluetooth enabled mood ring that can tell my computer what my mood is and influence stumbledupon appropriately! Think of the impact this could have on your web experience! Maybe your webmail would change it’s background colors to softer gentler hues to calm you. Perhaps Amazon would recommend anti-depressents or light-hearted comedies in its deal gold box.

I’m not serious of course. The bluetooth enabled mood ring I find amusing, but not the extra dimension of influence it could have on how websites could personalize the experience for you. *eeek!*

Scoring Cribbage Runs and Recursion

Ever since I posted the iterative solution to scoring cribbage runs it’s bothered me that other algorithm for scoring combos is recursive. It seemed intuitive that scoring runs and scoring combos were very similar. So, I decided to implement scoring runs recursively and it turned out to be harder than I thought but yet when complete beautiful. Logic is usually that way–hard in the struggle but simple in it’s reduction to a solution. So I present the solution in various languages:

(defun score (len duplen duptotal array)
  (cond
   ((null array)
    (if (< len 3)
        0
        (* duptotal len)))
   ((null (cdr array))                                        ; only one item left do an extra recursion so base can end recursion
    (score len 1 (* duptotal duplen) (cdr array)))
   ((= (car array) (car (cdr array)))                   ; adjacent cards =
    (score len (+ duplen 1) duptotal (cdr array))
   ((= (car array) (- (car (cdr array)) 1))            ; differ by 1
    (score (+ len 1) 1 (* duplen duptotal) (cdr array)))
   (t                                                              ; differ by more than 1
    (+ (* duptotal len) (score 1 1 1 (cdr array))))))

To make the logic more beautiful I added an extra step of recursion in the case of an array of one element. I could have rolled that into the base case of an empty list but that forced the computation of the point total to include the current duplen which wasn’t symmetric with the computation of the point total in the default case. Here’s the C (remember I pad the array with a negative -1 to simplify the code):

int ScoreRuns(int len, int duplen, int duptotal, int array[])
{
  if ( *array == -1 ) { // end of cards
    if ( len < 3 ) {
      return 0;
    }
    else {
      return len * duptotal;
    }
  }
  else if ( *(array+1) == -1 ) { // only one card left, do one more call so base can end recursion.
    return ScoreRuns(len, 1, duptotal * duplen, array+1);
  }
  else if ( *array == *(array+1) ) { // adjacent cards =
    return ScoreRuns(len, duplen+1, duptotal, array+1);
  }
  else if ( *array == *(array+1)-1 ) { // adjacent cards differ by 1
    return ScoreRuns(len+1, 1, duplen * duptotal, array+1);
  }
  else { // cards differ by more than 1, so run ends. compute total and score rest of hand.
    return ((len < 3 ? 0 : len * duptotal) + ScoreRuns(1, 1, 1, array+1));
  }
}

Note that this algorithm is O(n) same as the previous iterative version. The computation of the multiplier vector is computed recursively rather stored in a local array. Finally, the Perl code with the recursive function:

sub ScoreRunsWork {
    my $len = shift;
    my $duplen = shift;
    my $duptotal = shift;
    my @array = @_;

    my @rest = @array[1..$#array];

    if ( int(@array) == 0 ) { # end of cards
        if ( $len < $MIN_RUN_LENGTH ) {
            return 0;
        }
        else {
            return $len * $duptotal;
        }
    }
    elsif ( int(@array) == 1 ) { # only one card left, do one more call so base can end recursion.
        return ScoreRunsWork($len, 1, $duptotal * $duplen, @rest);
    }
    elsif ( $array[0] == $array[1] ) { #  adjacent cards =
        return ScoreRunsWork($len, $duplen+1, $duptotal, @rest);
    }
    elsif ( $array[0] == ($array[1] - 1) ) { # adjacent cards differ by 1
        return ScoreRunsWork($len+1, 1, $duplen * $duptotal, @rest);
    }
    else { # cards differ by more than 1, so run ends. compute total and score rest of hand.
        return ( (($len < $MIN_RUN_LENGTH) ? 0 : $len * $duptotal) + ScoreRunsWork(1, 1, 1, @rest) );
    }
}

Cribbage Scoring

It’s something that’s always nagged me. When it gets complicated I usually do it incorrectly—score cribbage hands. When you score car license plates according to cribbage rules trust me it gets complicated. A conversation with my friend, and former computer science nerd (possibly still one), Andrea proved that the algorithm for scoring cribbage hands might not be that hard. This post will attempt to bore my non-computer science friends as I explain the algorithms I used and how I wrote it in Perl.

I don’t want to get into the details of how to play cribbage, I’ll limit it to just tallying your own cribbage hand. Points are gathered in three ways:

• Runs of three or more cards.
• Pairs of two.
• Sets of cards summing to 15.

The points gathered in each of these ways is slightly different:

• the length of the run is the number of points gathered.
• each pair is worth 2 points.
• each group of cards summing to 15 points is worth 2 points.

Examples always makes things clearer:

• 2 3 4 = 3 points
• 2 2 = 2 points
• 7 8 = 2 points
• 2 3 3 4 = 8 points (two runs of three plus one pair)
• 6 7 8 9 = 8 points (one runs of four plus two groups of cards summing to 15)
• 5 5 5 5 = 20 points (four sets summing to 15 for eight points and six pairs for twelve)

I approached this problem by breaking the algorithm down into it’s component parts—computing pairs, runs and groups of 15.

Scoring Pairs

Scoring pairs turns out to be the easiest of all the scoring methods. Scoring runs and scoring sets of 15 is too complicated and probably would encourage check your email and eventually lose interest!

I presented a hand of cribbage cards as an array of cards. The suit of the card doesn’t really matter, so I’ll only store the value of the card in the array. To make the algorithm easier the array is sorted in ascending order. This simplifies this scoring algorithm and others.

What we are looking for is a way to compute all pairs of two cards. To do this I use two loops, one loop over all but the last element in the array and a nested loop from the next element to the end of the array. Basically the first loop isolates one element and the second loop searches for matches among the remaining elements. Every match is a pair worth two points:

sub ScorePairs {
    my $handRef = shift;
    my @hand = @$handRef;
    my $ret = 0;

    for(my $pos = 0; $pos < int(@hand) - 1; $pos++) {
        my $val = $hand[$pos];
        for(my $ppos = $pos + 1; ($ppos < int(@hand)) && ($hand[$ppos] == $val); $ppos++) {
            $ret += $PAIR_PTS;
        }
    }
    return $ret;
}

I won’t get into the details of what’s being passed in—what’s important is the hand of cards that’s passed in is copied into the array @hand.Another way of writing this is scan the array and compute the total number of each card type—it’s not important what type it is. From that use the combination formula formula, nCr, where n is the number of a particular card type and r is two. Repeat this for every card type and multiply by two to generate the score for your pairs. Heck..that might have been easier, it wouldn’t have been O(n**2), rather it be O(n).

Scoring Runs

Computing runs are made easier by sorting the array earlier of cards. But nonetheless not simple because one duplicate card in the run doubles the value of the run. The hand “1 2 3” is worth three points. The hand “1 2 2 3” is worth 8 points ( two runs of three plus the pair). So how to handle this? The solution I came up with is probably not terribly efficient but, it works.
I walk the array increasing a length variable for every adjacent cards with a difference of one. When there is a matching pair of cards, I increase a multiplier by one (initially set to 1), and move to the next card not increasing the length at all. When two adjacent cards are encountered that are neither equal nor have a difference of one, the run has ended and the total score of the run is computed. The score is the length * the multiplier. In the case of “1 2 2 3” the when the end of the array is reached the the score is, 3 * 2, length of 3, multiplier of 2 because two “2s” where found.Wait..what about the hand “1 1 2 2 3”? Is the score 3 * 3 for 9 points (let’s ignore pairs for now). No, sadly that’s wrong. There are four runs of 3 [BTW when should I write 'three' instead of the digit '3'? Sorry for the inconsistencies in this post!]. Herumph! The cardinality of each group of equal cards in a run, is a multiplier of the run. What the heck does that mean? In the example above, “1 1 2 2 3”, there are two groups of equal cards in the run, (1, 1) and (2, 2). Each one generates a multiplier of 2. So the total multiplier is 4. Let’s look at the Perl code:

sub ScoreRuns {
    my $hand = shift;

    my $len = 1;
    my @mult = ( 1 );
    my $ret = 0;
    my @cards = @$hand;

    for(my $pos = 0; $pos = $MIN_RUN_LENGTH ) {
                $ret += $len * ComputeMult(\@mult);
                $len = 1; # reset and move on
                @mult = ( 1 );
            }
        }
    }
    # could exit loop at end of valid run.
    if ( $len >= $MIN_RUN_LENGTH ) {
        $mult = ComputeMult(\@mult);
        $ret += ($len * $mult);
    }
    return $ret;
}

Key to understanding how this works is the multiplier vector. Anytime a non-duplicate is encountered in the hand, a “1” is pushed onto the multiplier vector. If the next card is a duplicate, the current multiplier entry is increased by one. When a run of cards ends the length of the run is multiplied by all the elements in the multiplier vector. Since a new run is starting, the length is reset to 0 and the multiplier vector reset to just the value 1. Let’s look at an example:array: 1 2 2 3 5 6 6 7Scoring only runs, the total number if points in this hand is 12. Why? There are 4 runs of three. There are two places the runs end—between the 3 and 5, and between the 7 and the end of the array. The multiplier vector is (1 2 1) when the 5 is reached. So the multiplier vector times the length, 3, is 1 * 2 * 1 * 3 which is 6. At the end of the array the current run is scored and it is the same as the previous computation 1 * 2 * 1 * 3 = 6. The total points is therefore 12. This portion of the algorithm is O(n). Fun!

Scoring Combos

I don’t know if combos is the right term. Really we’re scoring groups of cards that sum to a particular value. Saying combos, however, sounds cool.Anyway, scoring combos is really a depth first search for groups where the sum is a particular value. Again the algorithm is simplified by the cards being sorted—we can cut off the search when adding a card exceeds the sum amount (again 15 for cribbage). I wrote it originally in C because I found it easier to write using pointer arithmetic:

int work(int array[], int sum) {
  int runningscore = 0;
  if ( sum == 15 ) {
    return 2;
  }
  else if ( *array == -1 ) {
    return 0;
  }
  else if ( sum > 15 ) {
    return 0;
  }
  else {
    for(; *array != -1; array++) {
      runningscore += work(array+1, sum + *array);
    }
  }
  return runningscore;
}

There are three terminating base cases:

• the sum of the set is 15.
• you reach the end of the array (in this example I pad the end of the array with a -1 so I don’t have to track the size of the array).
• the sum of the group is greater than 15.

The inductive step is looping through the entire array recursively calling the score function on each of the elements.

I was having problems translating it to Perl, mostly I think because of getting the array slices correct. Then Andrea suggested (I don’t know if jokingly) writing it in Lisp. Hmm…why not?

(defun score (list sum)
  (cond
    ((= sum 15) 2)
    ((> sum 15) 0)
    ((null list) 0)
    (t
      (+ (score (cdr list) (+ sum (car list))) (score (cdr list) sum))))

I think this is right—I haven’t tested it but what’s important here is the lack of iteration! Using a loop in Lisp is a sin so I called score recursively on the remainder of the list:

(+ (score (cdr list) (+ sum (car list))) (score (cdr list) sum))))

Note that I’m not modifying the sum, I’m just skipping the head of the list by passing the remainder of the list to the score function. So, I should be able to rewrite that C function to not use iteration:

int work(int array[], int sum) {
  int runningscore = 0;
  if ( sum == 15 ) {
    return 2;
  }
  else if ( *array == -1 ) {
    return 0;
  }
  else if ( sum > 15 ) {
    return 0;
  }
  else {
    runningscore += work(array+1, sum + *array) + work(array+1, sum);
  }
  return runningscore;
}

OK, so how does this translate to Perl?

sub ScoreComboWork {
  my $sum = shift;
  my $combo_sum = shift;
  my @hand = @_;</span>

  my $runningScore = 0;

  return 2 if ( $sum == $combo_sum );
  return 0 if ( $sum > $combo_sum );
  return 0 if ( @hand == 0 );

  my @subarray = @hand[1..$#hand];
  $runningScore += ScoreComboWork($sum + $hand[0], $combo_sum, @subarray)
                           + ScoreComboWork($sum, $combo_sum, @subarray);
  return $runningScore;
}

The equivalent of the lisp cdr function is the array hash from 1 to the end of the array which is assigned to @subarray.What is the big-O notation for this algorithm. Hmm..I think it’s O(n*2). Why? In the worst case this will through every element and then within that from the next element to the end of the array. Classic nested loops.

Testing the Speed Testers

A neighbor just got Verizon Fios and I thought I’d test it’s speed. Then I thought, how do I know the values I get are accurate? So, I went to a couple of sites. Here are the values:

speedtest.net

——————-

Download: 11.5M

Upload : 4.3M

cnet.net

———–

Download: 2.3M

Upload : ???

verizon.com

—————-

Download: 7.54M

Upload : 4.503M

speakeasy.com

———————

Download: 14.1M

Upload : 4.6M

Cake and A Cappella

Hmmm..I’m listening to Cake’s awesome version of “I Will Survive” and I’m wondering this could be a pretty funky song done a cappella. I don’t know about the guitar solo but the percussion and the funky base line could kick ass.

podcasts and the gym

My gym visits have been saved. After getting a new workout program from a trainer that consisted of less time on the stair mill/stair master/elliptical, I was worried that I would be bored out of my mind at the gym. Enter podcasts. Now I can listen to a Fresh Air podcast about different points of view on the Iraq war, or Car Talk (“don’t drive like my brother”) episodes while I do lunges, SB bridge curls, barbell deadlifts… It’s great.

If you see some guy at the gym breaking down in laughter while doing a seated row, it’s probably me.

Feature Request: Mail

[ I feel like I've posted this before, if so I'm old and forgetful. Or, I really want this. ]

I want a feature in a mail client that will remind me if I haven’t responded to an email in my inbox. I’ll set the configurable amount to, say, 4 days, and it will remind me to respond to these messages. Also, if I want, if I’ve responded to a message it will be moved to another folder. To this end I want the interface scriptable. Perhaps scriptable in the mail client, but also in a web mail reader. Perhaps scripts could be attached to incoming emails and they would fire at set times. This of course discourages scripts being fired on a server because of the load that would generate. Scripts could be executed on a local mail client however.

Yes, I could do this myself. I could move every message I’ve responded to to another folder by hand and examine the read messages in my inbox folder and file those or respond to them. But this is something that a script could do for me.

Managing your email should not take a lot of time.

Socializing and Dentists

I was chatting with Michelle, my dental assistant, and my dentist Greg we got on the topic of being socially burnt out at the end of the day. They were quite animate about it–they are usually burnt out socially at the end of the day. Greg’s wife, according to Greg, wants to chat with him when he gets home and he apologies and says I need to be anti-social for a bit. It’s an unwritten job requirement that he has the be upbeat and social during his job. Even worse, he has to hold up both sides of the conversation with a client. Similarly Michelle, who is incredibly talkative and social says at times she’ll start giving simple one word answers to everyone for an entire day, she keeps this out of work though. Greg and Michelle said think about barbers and hair stylists–they are expected to be incredibly social the entire time. They are in the same boat.

While this blog entry is not surprising, it’s not something you think about.