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.