Where's Waldo - Text style

Ok, it's a word search.

We're always looking for interesting applications to build lessons around. Over the years, I've tried different things when teaching 2 dimensional arrays. Simple game boards, representing a crossword puzzle, tables of various sorts, etc.

This year, JonAlf, one of my amazingly talented colleagues, decided to go with building a word search. I decided to steal the idea. It's a great one.

I thought I'd use this post to go through the project and why I like it.

Ultimately, the students end up with a program that will generate an n by m word search filled with random words from a dictionary. We gave the kids a skeleton of the base class. The only actual code we had to supply was the method that loaded a dictionary file into memory. You can check out the assignment here and the finished code here (we updated the repository as the project developed).


The first part of the project are pretty mundane. The kids write a couple of constructors and toString. Basically just practice traversing a 2D array. The project starts to get interesting at part 2, when they write the methods that add words into the grid. First horizontally:



After they write the method to add words vertically, we can start to refine things. We notice that the routines are essentially the same. The only difference between adding a word horizontally and vertically is  what we add  to the row and column each time. For one, there is a delta column of + 1, for the other it's a delta row. Further, they realize that adding diagonal words just needs both deltas. This leads us to factoring out the common aspects of the code and writing something like:



All of a sudden, they've written one piece of code that can add words in 8 orientations.

After filling the rest of the grid with random letters, we turn our attention to building a random puzzle.

This part of the project involves using an ArrayList of words. Our students frequently mix up array and ArrayList notation early on so by having a project that uses both but in clearly delineated areas, the students can be more comfortable with each.

For this piece, the code is again straight forward. Students run a loop that gets a random word from our dictionary and tries to place it in our grid at a random location choosing one of our possible orientations randomly. We get to see another nice little refinement again when we move from the typical first take at building a random puzzle which uses a three (or more) way if statement to select how to add words:



to using our more general addWords method described above:




When we're all done, we had some time to project the word search on the board and fun was had by all.

Peter, another one of our CS teachers had a great suggestion that I think I'll try. Start a competition to have the students modify the program so that it generates as densely packed  a wordsearch  as possible (giving higher scores first for longer words, then number of words).

Between the way the project broke down, the topics covered and the little refinements, I really enjoyed working with my classes on this project -- I'm hoping they enjoyed it as well.

Sorting from the top and from the bottom

I've been meaning to write this post for a couple of weeks, but some times life just gets in the way.

I've always thought it important to arm students with as many different tools with which to attack problems as possible. As such, the courses I teach use a number of different languages, each highlighting a different paradigm and thought process. The hope is that by the end of the sequence, they can look at problems from many different angles.

In my advanced placement classes, we recently studied sorting algorithms. It think the quicksort is a good example of a problem that can be looked at from multiple points of view.

In my experiences talking to teachers and students who cut there teeth using languages like Java, C, or C++, much of the discussion deals with the actual partitioning of the array. Comparing elements, swapping them and arriving in the middle. One might end up with something like this as a first cut:

 1:  public void qsort(int[] a,int l, int h)
 2:  {
 3:  if (l>=h)
 4:    return;
 5:  
 6:  /* Just use lowest index as pivot for now */
 7:  int pivot = a[l];
 8:  int low=l;
 9:  int high=h;
10:  
11:  /* partition the data set around the pivot value */
12:  while (l<=h)
13:  {
14:    while (a[l]<pivot)
15:      l++;
16:    while (a[h]>pivot)
17:      h--;
18:    if (l<=h)
19:    {
20:      int tmp=a[l];
21:      a[l]=a[h];
22:      a[h]=tmp;
23:      l++;
24:      h--; 
25:    }
26:  }
27:  
28:  /* sort items below and above the pivot */
29:  qsort(a,low,l-1);
30:  qsort(a,l,high);
31:  
32:  }

A fair amount of time and detail is spent dealing with the low level movement of data within the array . This is important – good stuff, but it takes the emphasis away from the higher level elegance of the algorithm.

The quicksort can be described as:

1. If the size of the list is <= 1, return.
2. 1. Select a pivot element
   2. Generate the list L of items smaller than the pivot
   3. Generate the list H of items larger than the pivot
   4. the sorted list is qsort(L)+pivot+qsort(R)

Having seen some scheme in their intro class, our students have a tool with which we can describe the quicksort in terms much closer to the description (allowing for the fact that this doesn't deal with multiple values equal to the pivot correctly):

 1:  (define makefilter
 2:    (lambda (op x)
 3:      (lambda (n) (op x n))))
 4:  
 5:  (define qsort 
 6:    (lambda (l)
 7:      (cond ((null? l) '())
 8:            (else (append (qsort (filter (makefilter > (car l)) l))
 9:                          (list (car l))
10:                          (qsort (filter (makefilter < (car l)) l)))))))

This allows us to discuss the quicksort at a much higher level and focus on things like selecting a good pivot or the analysis of the run time. I believe this makes it much easier to really understand what's going on.

Having discussed it in this functional context, we can also look at the same thing in a scripting language such as python:

1:  def qsort(l):
2:      if len(l)<=1:
3:          return l
4:      else:
5:          return qsort([x for x in l[1:] if x <= l[0]]) + [l[0]]+\
6:              qsort([x for x in l[1:] if x > l[0]])
7:  

Again, the focus is on the algorithm, not the array or list manipulation.

Looking at the problem from both the more abstract side, which in this case functional languages allow, and the more concrete, as we did in Java gives our students more tools with which to attack problems.

Just some food for thought.