For a while now, I’ve been considering what would constitute warm up exercises at the coding dojo. Typically, in a martial arts group, these exercises serve to prepare participants for the athletic exertion of the session. Often, these exercises bear some relation to the martial art and therefore serve a dual purpose: a warm-up with some bearing on the art itself. A clever teacher might even relate the warm-up exercises to the evening’s study.
A couple of sessions ago, I remarked to AC about a question I’d asked during a recent job interview session. The question was related to traversing a linked list (a typical, simple programming question). The actual question had been to reverse the linked list, but AC (still in the process of de-cycling) misheard and thought I’d said “print” the list in reverse order. He quickly suggested that this should be an easy endeavour. With this challenge, I decided to take the opportunity to present a potential solution that went well beyond the initial question in order to explore a common container data structure use pattern.
Deciding to use C, we started the exercise with a definition and declaration of a linked list:
typedef struct _s_node Node;
struct _s_node {
char* name;
Node* next;
};
int main(int argc, char* argv[])
{
Node n4 = { "node4", NULL };
Node n3 = { "node3", &n4 };
Node n2 = { "node2", &n3 };
Node n1 = { "node1", &n2 };
Node n0 = { "node0", &n1 };
return 0;
}
From this point, I decided that I should demonstrate a simple iteration over the linked list. Using a loop, we print the name field in the Node structure:
#include <stdio.h>
typedef struct _s_node Node;
struct _s_node {
char* name;
Node* next;
};
int main(int argc, char* argv[])
{
Node n4 = { "node4", NULL };
Node n3 = { "node3", &n4 };
Node n2 = { "node2", &n3 };
Node n1 = { "node1", &n2 };
Node n0 = { "node0", &n1 };
Node* it = &n0;
do {
printf("%s\n", it->name);
} while ( NULL != (it = it->next) );
return 0;
}
Now, that we had an understanding of how our simple linked list could be used and interpreted, we returned to the challenge at hand: operating on the list in reverse order. In order to make the problem interesting to AC (who’d grown a little bored during the 5-10 minutes it took us to get this far), I suggested that we could accomplish that requirement without using a looping structure. That challenge was enough to whet his interest again. After a few more minutes of typing, I completed a recursive solution to the challenge:
#include <stdio.h>
typedef struct _s_node Node;
struct _s_node {
char* name;
Node* next;
};
void print_reverse(Node* n)
{
if ( n ) {
print_reverse(n->next);
printf("Node: %s\n", n->name);
}
}
int main(int argc, char* argv[])
{
Node n4 = { "node4", NULL };
Node n3 = { "node3", &n4 };
Node n2 = { "node2", &n3 };
Node n1 = { "node1", &n2 };
Node n0 = { "node0", &n1 };
Node* it = &n0;
do {
printf("%s\n", it->name);
} while ( NULL != (it = it->next) );
print_reverse(&n0);
return 0;
}
Having solved the problem, I could’ve ended the exercise at this point. In approximately 10 minutes, I’d presented a simple data structure and a fun little way of using it. Since none of the other dojo regulars had arrived yet (and I was having fun), I decided to continue the exercise into a generalized solution that demonstrated a typical pattern that I’ve observed when working with container data structures.
Since the initial operation on the list (print all the names) and the second were so similar, refactoring the solution seemed to be the next task on the list. For symmetry, the do/while loop of the first operation was turned into a recursive approach.
#include <stdio.h>
typedef struct _s_node Node;
struct _s_node {
char* name;
Node* next;
};
void print_forward(Node* n)
{
if ( n ) {
printf("Node: %s\n", n->name);
print_forward(n->next);
}
}
void print_reverse(Node* n)
{
if ( n ) {
print_reverse(n->next);
printf("Node: %s\n", n->name);
}
}
int main(int argc, char* argv[])
{
Node n4 = { "node4", NULL };
Node n3 = { "node3", &n4 };
Node n2 = { "node2", &n3 };
Node n1 = { "node1", &n2 };
Node n0 = { "node0", &n1 };
print_forward(&n0);
print_reverse(&n0);
return 0;
}
The obvious similarity of the two print_ procedures was immediately apparent after this refactoring. In fact, that’s the nice thing about refactoring iteratively: you get to slowly see the patterns emerge in your code. After a few minutes of discussion, we decided to implement a generalized solution. We extracted the operative functionality from the traversal of the container using function pointers:
#include <stdio.h>
typedef struct _s_node Node;
struct _s_node {
char* name;
Node* next;
};
void print_name(Node* n)
{
printf("Node: %s\n", n->name);
}
typedef void (*map_f)(Node*);
void apply(Node* n, map_f pre, map_f post)
{
if ( n ) {
if ( pre ) {
(*pre)(n);
}
apply(n->next, pre, post);
if ( post ) {
(*post)(n);
}
}
}
int main(int argc, char* argv[])
{
Node n4 = { "node4", NULL };
Node n3 = { "node3", &n4 };
Node n2 = { "node2", &n3 };
Node n1 = { "node1", &n2 };
Node n0 = { "node0", &n1 };
apply(&n0, print_name, NULL);
apply(&n0, NULL, print_name);
return 0;
}
I’ve taken to calling this pattern the traverser (which came from a long-running conversation between myself and MC). As mentioned above, it’s a separation of an algorithm that iterates over a container and the operations during that iteration.
Later on, I refined this solution to implement the actual question that I’d asked earlier in the day: reversal of the elements of a linked list. Here’s the solution that I came to (omitting the common parts of previous code listings):
void reverse(Node* n)
{
if ( n->next ) {
n->next->next = n;
n->next = NULL;
}
}
int main(int argc, char* argv[])
{
Node n4 = { "node4", NULL };
Node n3 = { "node3", &n4 };
Node n2 = { "node2", &n3 };
Node n1 = { "node1", &n2 };
Node n0 = { "node0", &n1 };
apply(&n0, NULL, reverse);
apply(&n4, print_name, NULL);
return 0;
}
This entire exercise took less than half an hour to accomplish. That’s a short enough time that I don’t think attention will wander. The only remaining issue with this concept is the simplicity of the exercises. A decent programmer will tend to solve the problem and remember the solution for the next time. My concern is that they will grow bored with the process once we run out of little problems to tackle.
In a certain way, the projects portion of the dojo services this concern. A project tends to be longer running and more like the typical sort of thing a programmer will face in their day job. To a certain extent, this tends to grab the attention of programmers at the dojo for longer periods of time. Of course, even projects tend to wax and wane. Once the interesting aspects of the project have been solved, attention also wanders.
In order to get something useful out of the concept I’ve introduced in this posting, I’ll have to make certain that all of the exercises orbit around core tenants of programming (Patterns, for example). The more I consider it, I suspect this signifies the beginning of a style at the dojo. Deriving a style, I think, is a fundamental part of the progress of an art.
At least we’re on the right track.
