Learning to play harmonica

My new harmonica.

As it turns out, lectures don't start until Monday, so (excluding a short workshop tomorrow afternoon) I don't really start back at university this week. That's given me an extra few days to recover and get over this illness. My cough is almost gone, thankfully.

I bought a harmonica a week ago and I love the wee thing. I seem to have picked it up quite quickly and can knock out a few riffs and jam along to some backing tracks, but my embouchure could be a lot better. Practice makes perfect, though. Right now I'm doing my family a favour and practising while they're out of the house. Apparently my grandmother was a good harmonica player, although I don't imagine she jammed along to blues music. Maybe I'm wrong...

I suppose I'm the only musical person in two generations of my family. My grandmother came from a very musical background (I think her mother was a music teacher) and my grandfather was quite musical too, but it seems to have skipped a generation and no-one else plays anything. I've spent a lot of my life playing music, having played bass and guitar since very early in high school. Since university I've also started to play ukulele and harmonica.

Last week I was unable to do any exercise but as I'm feeling a bit better now, I've started to run again. I've ran three times since Monday and I'm slowly getting back into it. You'd be surprised at what effects even a week of illness can have on fitness. I know I'm not going to be breaking any personal records at the moment (actually that's a lie, I ran my fastest ever mile on Monday) but right now I'm just trying to limit damage.

Finding maximum zero submatrix with C#

After spending most of this evening attempting to solve this problem, it only feels right that I share my solution.

Suppose you have a binary matrix and you wish to find the largest zero submatrix, i.e. the largest rectangle of zeroes in the matrix (see below, highlighted in orange).

1 1 0 0 0 1 0

1 0 0 0 0 1 1

1 1 0 1 0 1 1

1 1 1 0 1 1 0

The brute-force approach to this problem isn't particularly efficient, with complexity O(n²m²). It involves looking at every position in the matrix, taking that position as an arbitrary point of the submatrix (e.g. the top-left point) and then testing all possible rectangles which originate at that point (e.g. all possible bottom-right points).

This algorithm finds the largest zero submatrix by looking at each position in turn and attempting to "grow" the submatrix up, to the left, and to the right. A dynamic programming approach is used and it keeps track of where the value 1 occurs. Array d contains the previous row where a 1 was found for each column. Array d1 contains the position of the left borders, and d2 contains the position of the right borders.

A complete code snippet for this program is available here. This has code to output the results and shows how to make use of the values calculated in this function.

static void MaxSubmatrix(int[,] matrix)
{
 int n = matrix.GetLength(0); // Number of rows
 int m = matrix.GetLength(1); // Number of columns

 int maxArea = -1, tempArea = -1;

 // Top-left corner (x1, y1); bottom-right corner (x2, y2)
 int x1 = 0, y1 = 0, x2 = 0, y2 = 0;

 // Maximum row containing a 1 in this column
 int[] d = new int[m];
 
 // Initialize array to -1
 for (int i = 0; i < m; i++)
 {
  d[i] = -1;
 }

 // Furthest left column for rectangle
 int[] d1 = new int[m];

 // Furthest right column for rectangle
 int[] d2 = new int[m];

 Stack<int> stack = new Stack<int>();

 // Work down from top row, searching for largest rectangle
 for (int i = 0; i < n; i++)
 {
  // 1. Determine previous row to contain a '1'
  for (int j = 0; j < m; j++)
  {
   if (matrix[i,j] == 1)
   {
    d[j] = i;
   }
  }

  stack.Clear();

  // 2. Determine the left border positions
  for (int j = 0; j < m; j++)
  {
   while (stack.Count > 0 && d[stack.Peek()] <= d[j])
   {
    stack.Pop();
   }
   
   // If stack is empty, use -1; i.e. all the way to the left
   d1[j] = (stack.Count == 0) ? -1 : stack.Peek();
   
   stack.Push(j);
  }

  stack.Clear();

  // 3. Determine the right border positions
  for (int j = m - 1; j >= 0; j--)
  {
   while (stack.Count > 0 && d[stack.Peek()] <= d[j])
   {
    stack.Pop();
   }
   
   d2[j] = (stack.Count == 0) ?  m : stack.Peek();
   
   stack.Push(j);
  }

  // 4. See if we've found a new maximum submatrix
  for (int j = 0; j < m; j++)
  {
   // (i - d[j]) := current row - last row in this column to contain a 1
   // (d2[j] - d1[j] - 1) := right border - left border - 1
   tempArea = (i - d[j]) * (d2[j] - d1[j] - 1);

   if (tempArea > maxArea)
   {
    maxArea = tempArea;

    // Top left
    x1 = d1[j] + 1;
    y1 = d[j] + 1;
    
    // Bottom right
    x2 = d2[j] - 1;
    y2 = i;
   }
  }
 }
}

East vs West

The most noticeable difference, at least from an outdoors perspective, between where I've been staying on the east coast of Scotland and where I live on the west? It's so flat! I've smashed my personal bests for running (for distance, not speed) without my quadriceps even complaining. At home, however, it feels like I'm almost always going either up or downhill.

It's not that I dislike uphill running, no, it's the downhill stretches that get to me. I find uphill running to be relaxing; it strongly encourages good form and pace, else you'll burn out quickly. I like feeling "in the zone" as I (slowly) make my way up the hill. Downhill, though, just doesn't feel right. Maybe I'll get used to it as I run more.

In my 100 miles challenge, I've covered 70. That leaves me with 30 miles in 11 days; easy! A couple of bike rides in there and I'm set.

I'm going to have to organise my time better once university starts back. Last year I failed to make a compromise between work and fun and training and as such cut out the training completely. That has taken it's toll on my body and my fitness and I'm determined to not have that happen again. It won't be easy finding time to stay on top of studies as well as just chilling out and training, but I'll find a way.

It'll help my studies too. I love that feeling where your mind empties when you're out pushing yourself and you get a fresh perspective on things. One of my lecturers in first year said the best way to tackle programming problems was to sleep on it; just step away from the computer, go for a walk and think about it. You're dead right, Quintin.

Side projects and running

Yesterday I started work on a new Android project, to pass some time and to create something which I, and hopefully others, will find useful. It's going to be an editor for GPS files which allows you to create, edit and share routes, using gpx (GPS exchange format) files. With the help of a friend, it's already made good progress in to something really lacking in features and polish, but still usable.

The image above is a screenshot showing what's implemented so far. Routes can be drawn by tapping the touch-screen to add a new waypoint and altered by dragging-and-dropping existing waypoints. Something I may also implement, if I can find out an elegant way to do it, is selecting points by a long press and then giving the option to, say, delete it.

Right now we're working through a to-do list and turning this into something which may eventually end up on the Android Market. Just after starting it, though, I'll be putting it on hold for a few days while I go off to stay with family on the other side of the country. Hopefully the weather stays reasonable, because I'll be taking my hiking boots, running shoes and, maybe, bike. It'll be great to just chill out, explore new places, and unwind for a few days.

I'm almost halfway there in my 100 mile challenge; I've covered 47.5 miles so far in the past 13 days. I've been running so much lately that I'm not racking up the miles as fast as I would be if I were cycling. My running is certainly improving though; both in speed and endurance. My technique is beginning to get more consistent as well, which is helping me to pace myself.

C#, Surface and Running

Since my last post I've taken up running. I've bought new shoes, fought through some hiking blisters and learned that I need to smarten up and pace myself. Running never really appealed to me before, but that was largely because I sucked at it. I'd put on any pair of trainers and head out without any consideration for progression and form. It was really an oversight on my part, because I've had experience with weightlifting which taught me to put an emphasis on proper form and planned workouts aimed at making progress.

I wish I was there again...

I'm addressing all of these issues now though and for the past week have been starting to carefully build up a base of fitness. Walking and cycling over the past few weeks has improved my fitness but I still need to ease my body into this, especially as running is more of an "impact" sport than cycling. My running trainers are comfortable and provide just as much support as I need, being flat footed. I've not yet ran over 2 miles in a single session, instead focusing on starting small and building my distance up slowly. After this post is finished I'll be heading out for another, while there is a break in the rain.

I'm a week into my 100 mile challenge and I've already covered 29 miles. Feels good.

In my fourth year of university I'll be undertaking a solo project which accounts for a significant part of my degree. Although I'm still discussing and arranging the details, I'm most likely going to be working with Microsoft Surface, Microsoft's touch-screen tabletop computing system. It's a technology completely new to me and I'm excited about working with it.

Of course, that means learning to develop for it, which also requires me to learn C# (C sharp), a language I've got no experience with. So far I've had no difficulty with it; it's so alike to other languages that I've used before. It has some small details though which I really like.

One of these is "Properties". Properties provide easy encapsulation without the need to explicitly call accessor and mutator methods. Whereas encapsulation in Java requires that for a private variable foo you create and use methods getFoo and setFoo, C# allows you to do the following:

public class Nyan

{

    private int foo;

    public int Foo

    {

        get { return foo; }

        set { foo = value; }

    }

}

Although the definition is similar to that in Java, it means you can access foo through the Foo property, like so:

x = Nyan.Foo;

Nyan.Foo = 15;

It's a minor detail, but it's an idea I really like.