A simple lesson in coding

Old truck hiding behind foliage on Washington Island, Wisc. (Photo by the author, 2021).

These days I am revising examples that I use in the first week of my data structures course. These examples help students refresh their basic programming skills. One of the examples turned to be a valuable lesson for me.

It started as a simple problem: to write a method that tells if a string is a palindrome or not. Almost reflexively, I typed the following code:

The verbosity of lines 4, 5, and 6 is for illustrative purposes and will be consolidated in the next attemp.

Looks straightforward but it suffers from shooting-from-the-hipitis. That’s a common malady that befalls second-year students — and sometimes their instructors: we rush to code something without much thinking. We may have the basic logic figured out: assume that any string is a palindrome until we find a pair of letters in it that refutes our assumption. We start comparing pairs of letters from the front and the end of the string, moving towards its center.

There are two things I don’t like in the code above. First, it feels like a waste to run the loop if the string is a single-letter word. To avoid that, I add the if statement of line 3 below. The method now considers all single-letter words to be palindromes. We can change this if we want; for now, I am ok with it.

Notice that the earlier verbosity has been consolidated in a single line (line 5).

The second thing I don’t like about this method is that it’s wasterful. Consider the case: isPalindrome("supercalifragilisticexpialidocious"); Its first letter matches its last ('s'=='s’) and so does its second and second-to-last letters ('u'=='u' ). But this is no longer the case for the third and third-from-last letters, p and o respectively. At this point, the word has been disqualified as a palindrome. Why continue with the remaining 14 pair-wise comparisons. Even if they all show matching letters, the word is not a palindrome. Can’t we save some processing time and call it as soon as we discover the mismatch? Sure we can, just add lines 6 and 7 below.

That’s bad though. Almost as bad as writing:

if (!palindrome)
  break; // the for-loop

If we anticipate a scenario where we do not run the full length of a loop, it’s best to not use the for-loop. Trying to break out of a for-loop prematurely is just bad taste. It works but it’s not good code.

The next step is to rewrite the method with a smarter loop. The while-loop in line 5 below checks every pair of letters. It may stop sooner if a mismatch is found.

This example helps students refresh their knowledge of methods with return type and parameters, String methods, and conditions in an iterative setting. It takes them from verbose, poorly designed code to a more robust method. It accentuates the key differences between for and while loops. And it leads to interesting conversations about design considerations.

One conversation worth having is about the parameter passed into the method. What if we had the call isPalindrome("Noon"); The first and the last letters are not equal and therefore Noon is not a palindrome. But it is and we need to convince our code about it. Therefore, we need to add the following statement to our method.

s = s.toLowerCase(); // or .toUpperCase()

If may pass "Noon" to the method, it will convert it to "noon" (or "NOON") before comparing every pair of letters.

Another consideration is about spaces in arguments. Assume we callisPalindrome("Race car"); Grammatically, it is a palindrome. Our method will return false because s.charAt(3)==s.charAt(4) is false. So, we move to eliminate spaces with:

s = s.replace(" ", "").toLowerCase();

and "Race car" becomes "racecar". Now, all pairwise conditions are true:

s.charAt(0) == s.charAt(6); // true because r acecar  ==  raceca r
s.charAt(1) == s.charAt(5); // true because r a cecar == racec a r
s.charAt(2) == s.charAt(4); // true because ra c ecar == race c ar
s.charAt(3) == s.charAt(3); // true because rac e car == rac e car

But there is more. What about isPalindrome("a man, a plan, a canal: Panama"); Is it a palindrome? If we wash the string through replace() and toLowerCase(), we get "aman,aplan,acanal:panama": not quite a palindrome. We need to wash string s one more time, removing punctuation.

s = s.replaceAll("[^a-zA-Z ]", "").replace(" ", "").toLowerCase();

Method replace() above now is redundant — its role can be delegated to replaceAll() with a slight modification in the regular expression. I am not doing it, however, because I want to illustrate the three separate transformations I am applying to the string argument: remove punctuation, remove spaces, convert to lower (or upper) case. Eventually, the first two removals can be combined in a regular expression that removes all non-letter characters (including spaces, punctuation, numbers, etc). For now, the final product is shown below, with the transformation of string a in line 4.

Next, the conversation can turn to whether or not line 4 above can be delegated to a helper method, i.e.,

Discussing how necessary is this delegation is also good because we get to talk about factoring and reusability as good coding practices.

Finally, there is one more issue to discuss: the placement of the wash() call. We placed it within the if scope, i.e., we call it only for arguments that have two or more characters in them. This can be problematic. Asking isPalindrome("4"); will return true although our intention was to examine words made of letters. Asking isPalindrome("5A"); will also return true because wash() will reduce the argument to just "A". This is an opportunity to talk about expected and unexpected code behavior and the role of testing in our design process.

Students returning to class may be a bit rusty with their basic programming skills. A simple, introductory-level example of building a boolean method helps them explore technical and design considerations and refreshes their coding abilities. From here, we can take the conversation to simple tests, discuss performance analysis, and even scan a few text files to search for palindromes. Then the question of duplicate data arises. This takes us to set-theory behaving data structures, where the real fun begins!

Next: A simple lesson in coding, revisited.