A simple lesson in coding: the playground

Pickle-flavored taffy at the Candy Factory in Phillipsburg, MO. (Photo by the author, 2021).

This is the last article in a series of four, about how a simple idea evolved into a course plan for students taking their first class in data structures. The first article described the simple example that we’ll keep using here: a method to tell if a String is a palindrome or not. The second article refined the method a bit. The third article exposed more flaws and made a case for better planning and design before coding.

Now that we are satisfied with the way our method works, it is time to deploy it in a real setting: let’s scan a book and collect its palindromes. We’ll use Project Gutenberg’s as a source for data, following the plan below.

establish a URL connection to the book
scan the text, word by word
if a word has not been processed before:
  if it's a valid word (letters, spaces, punctuation only):
    if it's a palindrome:
      add it to the list of palindromes for the book
report results

The plan seems straightforward except for that part about a “list of palindromes”. Students coming out of an introductory programming course are familiar with arrays. Naturally, they may get inclined to write code like the following. In the snippet below, book is a Scanner object connected to a web-based text, andpalindromesFound is a String array.

The problem with the code above is, of course, the array palindromesFound[]. Initialize it with too few elements, and we get an index-out-of-bound runtime error. Initialize it with too many elements, and we may be wasting resources. Ideally, we need an array that resizes itself on demand. Arrays in Java cannot do that. So students now have to “invent” dynamic arrays.

Some programmers may ask, why not show students how to use ArrayLists at this point? I could, but my objective is to show students that data structures are solutions to specific problems and that the mechanics of data structures are well within their programming abilities. Eventually, we’ll get to use ArrayLists and other classes from the Java Collections Frameworks and from Guava. For now, the focus is to understand how necessity becomes utility. And simple programming can get us there.

With that in mind, students are invited to solve the problem of resizing arrays. What if we have an array initialized for [10] elements but we want to store one more element? With a little bit of back-and-forth in the classroom, we discover that we can resize an array in Java, albeit not very efficiently:

Now we focus on how often we resize the array. If we resize for every single additional element, things can get really slow. We experiment with different resizing plans, rewriting line 1 as shown below, while we discuss the merits of different resize factors.

String newArray[] = new String[oldArray.length * 2]; 
// or
String newArray[] = new String[3 * oldArray.length / 2];

Eventually, we derive a class to handle resizing on-the-fly. Essentially, we are re-inventing the ArrayList.

Notice that method resize is private. That’s because resizing the array is an internal matter for the class and it should not be initiated by a user. Method resize is invoked by method add every time we reach the array’s capacity.

By using a FlexArray object, we realize that a book, for example, James Joyce’s Ulysses, has thousands of palindromes. Upon closer inspection, we find that most of them are duplicates. Every time our code encounters the indefinite article “a” it adds it to the array palindromesFound. As a result, we end up with thousands of elements in that array, containing the same value (e.g., "a", the indefinite article; "i", the first person pronoun; "did", the inflected form of the auxiliary verb do-; etc).

And so, the next goal is to avoid processing duplicate words, which ensures the array palindromesFound will not contain duplicates. To accomplish this, we need a separate FlexArray object to contain words processed already.

FlexArray wordsProcessed = new FlexArray();
FlexArray palindromesFound = new FlexArray();
while (book.hasNext()) {
  String word = book.next();
  if (!wordsProcessed.contains(word) { // first time word
    wordsProcessed.add(word); // remember this word
    if (isValid(word) && isPalindrome(word)) { // if palindrome
      palindromesFound.add(word); // add it to our collection
    }
  }
}

Using this approach, we find that a massive book like Ulysses, has very few palindromic words; just a few hundreds. That’s because FlexArray wordsProcessed “remembers” the words we’ve been before and helps us skip them. By the time we add a word in FlexArray palindromesFound, we are certain we are not duplicating an existing entry. In fact, Ulysses has more than 250,000 words, but only about 49,000 are unique. There are about 400 palindromes in the book.

Searching for palindromes using class FlexArray can be slow. That’s because method contains scans the array from the beginning until it finds the word it’s looking for. This is not a very efficient method to search words. At this point, I begin to describe to students how we used to search for words in a printed dictionary. This description leads to the way to add and search for data in a binary search tree.

While not perfect, the course plan I describe here and in the previous articles helps students transition from their introductory programming course to their first data structures.