Introduction

Yesterday, someone posted a question on how to "think like a programmer" on /r/learnprogramming, and I gave this sage advice:

All programming comes down to writing functions. Always think about how you could solve a problem by writing more functions.

While I believe this to be good advice, it made me wonder what my own thought processes really are when I set out to tackle a problem. So I picked on of the other problems on yesterday’s /r/learnprogramming, and studied my own cogitations while I solved it, which may be of interest to beginner programmers. The solution is in C, and should be understandable by anyone with a modicum of experience in this language.

The Problem

The problem is given an array of integers containing the values 1 and zero, find the index of the longest contiguous sequence of the value 1, and the length of that sequence. In other words, given the array:

int v[] = {0,1,1,0,0,0,1,1,1,0,1};

we should end up with the values 6 for the starting index, and 3 for the length.

My Thoughts

Hmm, well I’m going to need a function which takes an array of ints as its parameter, and as we are using C, I’d better pass the length of the array as a parameter too. What shall I call the function? Let’s call it longest for now, so it will look something like this:

longest( int a[], int alen );

And I’ve got to have it return two values? Bugger. I guess I could pass a couple of pointers as parameters to the function and have it return via them?  Nah, lets make a structure to hold the return values. Something like this:

typedef struct {
    int start, length
} Seq;

Now I can write the complete (if empty) function definition:

Seq longest( int a[], int alen ) {
}

Now I’ll flesh this out a little by actually creating a Seq and returning it. And I’ll write a little main() to call it too:

#include <stdio.h>

typedef struct {
  int start, length;
} Seq;

Seq longest( int a[], int alen ) {
  Seq seq = {0,0};
  return seq;
}

int main() {
  int v[] = {0,1,1,0,0,0,1,1,1,0,1};
  int vlen =  sizeof(v) / sizeof(int);
  Seq s = longest( v, vlen );
  printf( "%d %d\n", s.start, s.length );
}

Now I’ll just compile that … yay – it compiles, and run it, which gives me the expected output:

0 0

So now I have to think how to find the longest sequence. I know I’m going to have to walk over that array somehow, so lets write something to do that:

Seq longest( int a[], int alen ) {
  Seq seq = {0,0};
  int i = 0;
  while( i < alen ) {
    i++;
  }
  return seq;
}

And that compiles too – good! Now, at each position in the loop I would really like to know the length of the sequence of the value 1 starting at that position. I’m going to need another function – I’ll call it seqlen. What am I going to pass to it as parameters? Well, it will need the array (and that damned length!) and the current loop index. And the return value – easy; it should return the length of the sequence, or zero if there isn’t one. So it will look like this:

int seqlen( int a[], int alen, int i )

So, how is this going to work? I need to make sure I’m not looking past the end of the array. Then, so long as a[i] contains the value 1 I’m in a sequence of 1’s, so I need to keep looping until I’m not. Something like this:

int seqlen( int a[], int alen, int i ) {
  int n = 0;
  while( i < len && a[i] == 1 ) {
    n++;
    i++;
  }
  return n;
}

Which also compiles! Great. Now I need to use it in my other function.

The problem says that I need to return the index of the longest sequence and its length. This means I’ve got to call seqlen repeatedly, and update the longest and length fields of my Seq struct whenever I find a new longest sequence. So I need to add some code to my while-loop in longest:

while( i < alen ) {
  int sl = seqlen( a, alen, i );
  if ( sl > seq.length ) {
    seq.length = sl;
    seq.start = i;
  }
  i++;
}

And when I run it it gives me the expected output:

6 3

That’s great, but looking at the code I notice that I’m incrementing the loop index in seqlen but then throwing away that increment when the function returns. This means that I’m doing a lot more work than necessary, though I do get the right result. I think a bit about whether this matters, and come to the conclusion that for small problem sizes it doesn’t, but it might for very large ones. In any case, the fix is easy – I just change the increment statement in longest to this:

i += sl ? sl : 1;

which adds the length of the sequence I found, or 1 if there wasn’t one and I just need to skip over a 0 value.

That change worked as  expected, and completes the code, which can be found here.

Summary

OK, so what did my thought processes and programming practices pan out as?

• The very first thing I did was to think of a function I could write; I didn’t start writing loops or anything like that
• I used a struct to return multiple values from a function, rather than doing so via pointers.
• I wrote some simple code which didn’t solve the problem, but did compile. I then started adding small chunks of code to this.
• I then thought of writing another function to handle a subsidiary part of the problem. If the problem was bigger, I would have come up with yet more functions.
• The functions I wrote were short – in fact about typical of the length of functions in my code for "real" applications.

So, I guess my advice on /r/programming wasn’t so bad after all!