Archive

Posts Tagged ‘imperative’

Car Talk Puzzler #2: What do these words have in common? An imperative and functional approach using Java and Scala

May 15, 2010 1 comment

Here’s the second in my series of Car Talk puzzler solutions. Today I’m going to be illustrating a solution first in Java, and then in Scala in order to show how functional programming features  can drastically reduce the number of lines of code, while still expressing the developer’s intent.

Puzzler:
What do these words have in common: pig, table, cab, real, yet, and ride?

RAY: Here’s the answer. If you notice, the first letter in each of the words is from farther down in the alphabet than all the subsequent letters. And if we assigned a number to every letter in the alphabet, so that A is one, B is two, C is three and so on…

TOM: Yeah, yeah, yeah.

RAY: Then the numerical place in the alphabet of the first letter is equal to the sum of the numerical places of all the other letters. For example, Table: T is 20, A is 1, B is 2, L is 12, E is 5, so 1 plus 2 plus 12 plus 5 –

TOM: Is 20.

So, we have the answer.  But as the guys mention on the show, there are probably other words as well.  Let’s do a brute force search through the dictionary to find all such words.  The dictionary I”ll be using is available here, as a new line separated list of words, one per line.  This makes it very easy to deal with.

Here’s the rather straightforward solution in Java:

``` import java.io.FileReader;
import  java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;

/**
* Determines all the words such that the first letter's ordinal position
* equals the sum of the remaining letters' ordinal positions.  For instance,
* "table"'s ordinal numbers are [20,1,2,12,5], and 20 = 1+2+12+5.  Thus
* "table" has this property.
*/
public class OrdinalPositionPuzzlerSolver {

/**
* Assumes the string consists just of A-Z, a-z.
*/
public static boolean hasProperty(String s) {
if (s.length() < 2) {
return false;
}
char[] letters = s.toCharArray();
int sum = 0;
for (int i = 1; i < letters.length; i++) {
int ordinal = ordinal(letters[i]) ;
sum += ordinal;
}
return sum == ordinal(letters[0]);
}

/**
* @return the 1 based ordinal position of the letter.  For instance,
* a is 1, b is 2, etc.
*/
public static int ordinal(char letter) {
return Character.toLowerCase(letter) - 'a' + 1;
}

public static void main(String[] args) {
String dictionaryPath = "dict.txt";
/**
http://www.javapractices.com/topic/TopicAction.do?Id=42
*/
try {
BufferedReader input = new BufferedReader(new FileReader(dictionaryPath));
try {
String line = null;
while (( line = input.readLine()) != null){
if (hasProperty(line)) {
System.out.println(line);
}
}
}
catch (FileNotFoundException e) {
System.err.println("Error, file " + dictionaryPath + " didn't exist.");
}
finally {
input.close();
}
}
catch (IOException e) {
System.err.println("IO Error:" + e);
}

}
}
```

The only place that bears some explanation might be the ordinal function:

```/**
* @return the 1 based ordinal position of the letter.  For instance,
* a is 1, b is 2, etc.
*/
public static int ordinal(char letter) {
return Character.toLowerCase(letter) - 'a' + 1;
}
```

Basically, letters (characters) in Java are really just numbers under the hood which get mapped back into letters when printed to the screen.  So, we can do arithmetic using letters.  ‘a’ + 1 = ‘b’, ‘b’ + 2 = ‘d’, and so on.  (This only works because the letters a-z and A-Z are mapped to a continuous range of integers).  So if we want to convert a->1, first we figure out a’s position from the start of the alphabet (‘a’ -‘a’ == 0, it’s the first), and add 1 to get the 1-based number.

The other thing to notice is how much junk code there is just to read the lines from our file:

```try {
BufferedReader input = new BufferedReader(new FileReader(dictionaryPath));
try {
String line = null;
while (( line = input.readLine()) != null){
if (hasProperty(line)) {
System.out.println(line);
}
}
}
catch (FileNotFoundException e) {
System.err.println("Error, file " + dictionaryPath + " didn't exist.");
}
finally {
input.close();
}
}
catch (IOException e) {
System.err.println("IO Error:" + e);
}
```

Believe it or not, this is relatively idiomatic Java code to accomplish this task.  First we wrap a file reader in a buffered reader so that we do not continuously access the file; rather we read chunks into the file and buffer them for in-memory access.  That’s 20 lines of code just to iterate over the lines of a file, determine if they match a pattern, and print it to the terminal.

It really should not be this hard.

As I’ve said before, Java’s verbosity is one of my biggest complaints about it.  The program works, and it’s relatively straightforward, but it can’t really be described as elegant.  In that same post I mentioned my interest in Scala as an alternative to Java.  It’s a compiled language that runs in the JVM, but through its type inferencing and functional language aspects, it is much more concise; the creator Martin Odersky claims a typical Source Line of Code (SLOC) reduction of 2x between equivalent Scala and Java programs. Let’s reimplement the program in Scala, and see if this claim rings true.  (Note: I’m not an expert in scala so there’s probably even more concise, idiomatic ways to accomplish what I’m trying to do.  But let’s start somewhere).

The syntax of scala is very similar to that of Java.  One of the main differences is that type declarations occur after the variable rather than before.

``` int x = 0; // Java
val x: Int = 0 // Scala
```

Another syntactic difference is that generic type arguments occur within square brackets rather than angle brackets

``` List<Integer> intList = ...; // java
val intList: List[Int] =  ..// scala
```

Because of this, array indexing is done through use of parentheses rather than square brackets.

``` // Java
int[] x = {1,2,3,4};
x[0] // 1
```
``` // Scala
val x: List[Int] = List(1,2,3,4)
x(0) // 1
```

Due to type inferencing, you often don’t need to declare the type of your variables; the compiler can figure it out.  Thus the last declaration could be rewritten as

``` val x = List(1,2,3,4)
```

I highly recommend you watch Martin Odersky’s introduction to Scala video; it’s about an hour long and goes over the design considerations and differences from Java.

There are no static functions in Scala; rather you create a singleton object through the keyword ‘object’ and access the method in the same way.

Finally, there is a read/eval/execute interpreter built-in, accessible by calling ‘scala‘ in the command line.  This allows you to experiment without having to explicitly compile any code; it allowed me to create the pieces iteratively before plunking them into a file for later compilation.

``` scala
Welcome to Scala version 2.7.3.final (Java HotSpot(TM) Client VM, Java  1.5.0_22).
Type in expressions to have them evaluated.
Type  :help for more information.

scala> 1+1
res0: Int = 2

scala> print("hello world")
hello world
scala>
```

OK, enough beating around the bush.  Let’s solve this puzzler!

We’ll tackle this in 3 parts.
1) Summing a list of numbers
2) Completing the ordinal number function
3) Iterating over all the lines in the dictionary file

Summing a list of numbers

A first pass at a sum function might be as follows:

```def sum(nums: Iterable[Int]): Int = {
var sum = 0
for (num <- nums) {
sum += num
}
sum
}
```

Note the declaration of sum as a var as opposed to a val; a val is equivalent to a final value while a var can be reassigned.  Why did I declare the nums argument to be of type Iterable rather than List?  Well, a List is iterable.  So is an array.  So are any number of things.  We want to keep this function as generic as possible. Pasting this into our interpreter, we can test this out.

```scala> def sum(nums: Iterable[Int]): Int = {
|     var sum = 0
|     for (num <- nums) {
|         sum += num
|     }
|     sum
| }
sum: (Iterable[Int])Int

scala> sum(List())
res4: Int = 0

scala> sum(List(1,2,3,4,5))
res5: Int = 15

scala> sum(Array(1,2,3,4))
res6: Int = 10
```

This works, but let’s look at another way to solve this problem – a functional rather than imperative solution.  Java is inherently imperative, meaning you’ll see a lot of explicit while and for loops.  Here’s just a quick excerpt of each the wikipedia articles to define each programming paradigm:

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state.

In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state. In much the same way that imperative mood in natural languages expresses commands to take action, imperative programs define sequences of commands for the computer to perform.

So whereas the imperative manner is completely explicit in how the sum is created, using a mutable state variable (sum), a more functional approach will eliminate the use of mutable state altogether.

The reduce function is absolutely crucial to understand in order to program in a functional manner; let’s examine Python’s definition of it before applying it to the problem at hand.

Here is the Python definition of reduce function:

reduce(function, iterable[, initializer])

Apply function of two arguments cumulatively to the items of iterable, from left to right, so as to reduce the iterable to a single value. For example, reduce(lambda x, y:x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). The left argument, x, is the accumulated value and the right argument, y, is the update value from the iterable. If the optional initializer is present, it is placed before the items of the iterable in the calculation, and serves as a default when the iterable is empty. If initializer is not given and iterable contains only one item, the first item is returned.

And the description of the built-in sum function is as follows:

sum(iterable[, start])

Sums start and the items of an iterable from left to right and returns the total. start defaults to 0. The iterable‘s items are normally numbers, and are not allowed to be strings. The fast, correct way to concatenate a sequence of strings is by calling ”.join(sequence). Note that sum(range(n), m) is equivalent to reduce(operator.add,range(n), m) To add floating point values with extended precision, see math.fsum().

While Scala doesn’t have a built-in sum function, it does have support for reducing a list through use of a function.  It has both a reduce left (left to right reduction) and reduce right (right to left reduction).  Here is Scala’s definition of reduceLeft:

def reduceLeft[B >: A](op : (B, A) => B) : B
Combines the elements of this iterable object together using the binary operator op, from left to right
Notes Will not terminate for infinite-sized collections.
Parameters
op – The operator to apply
Returns op(… op(a0,a1), …, an) if the iterable object has elements a0, a1, …, an.
Throws
Predef.UnsupportedOperationException – if the iterable object is empty.

This might be a little confusing but bear with me.

First, we need to write a binary function for our sum operator – after all, we want to pairwise reduce the list by using an add operator.  A first pass is as follows:

```scala> def add(x: Int, y: Int): Int = { x + y }
add: (Int,Int)Int

scala> List(1,2,3,4).reduceLeft(add)
res12: Int = 10
scala> List().reduceLeft(add)
java.lang.UnsupportedOperationException: Nil.reduceLeft
at scala.List.reduceLeft(List.scala:1093)
at .(:6)
at .()
at RequestResult\$.(:3)
at RequestResult\$.()
at RequestResult\$result()
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethod...
scala> List(-5,5).reduceLeft(add)
res14: Int = 0
```

Note that you cannot call sum on an empty list any more; doing so results in an UnsupportedOperationException.  This is arguably more correct than returning 0, but we will have to ensure that we don’t attempt to sum an empty iterable object.

So a working sum definition would be

```def sum(nums: Iterable[Int]): Int = {
def add(x: Int, y: Int): Int = { x + y }
nums.reduceLeft(add)
}
```

Note that you can nest function definitions, as functions are objects in Scala, and thus can be defined wherever a variable could.  Note too that I never have to explicitly return a value; the last evaluated value is implicitly returned by the function.

Finally, if you want to be even more terse, you can replace the explicitly defined add function with an anonymous one:

```def sum(nums: Iterable[Int]): Int = {
nums.reduceLeft(_+_)
}
```

Read the Daniel Spiewak’s excellent blog post for a better explanation for what’s going on here.  Here’s a quick explanation:

(_+_) is actually a Scala shorthand for an anonymous function taking two parameters and returning the result obtained by invoking the + operator on the first passing the second.  Less precisely: it’s addition.  Likewise, (_*_) would define multiplication.

Completing the ordinal number functional

Recall the function that we had in Java for computing the ordinal position of each letter:

```    public static boolean hasProperty(String s) {
if (s.length() < 2) {
return false;
}
char[] letters = s.toCharArray();
int sum = 0;
for (int i = 1; i < letters.length; i++) {
int ordinal = ordinal(letters[i]) ;
sum += ordinal;
}
return sum == ordinal(letters[0]);
}

/**
* @return the 1 based ordinal position of the letter.  For instance,
* a is 1, b is 2, etc.
*/
public static int ordinal(char letter) {
return Character.toLowerCase(letter) - 'a' + 1;
}
```

Again, we could directly translate this code into Scala but doing so would not be making full use of Scala’s functional underpinnings.  We are converting from characters of the string to their ordinal positions in the alphabet.  While the Java code does this one letter at a time, keeping a sum, it’s just as correct to do the entire mapping process and then sum over the new list.  Pictorially:

Just as there is a reduce function to convert an iterable object into a single entry, so too is there a function to convert an Iterable of one type into an Interable of another; it is the map function.

```// The underscore in an anonymous function like  this is a placeholder for the entry in the iterable collection currently  being processed
scala> List(1,3,4).map(_+5)
res19: List[Int] =  List(6, 8, 9)
scala> List("hi","there").map(_.toUpperCase())
res22:  List[java.lang.String] = List(HI, THERE)
```

The above examples map from Int-> Int and String->String but there’s nothing stopping us from converting types.

```scala> List(100,300,400).map(_.toString())
res23:  List[java.lang.String] = List(100, 300, 400)
```

Finally, let’s apply the ordinal function to a string:

```scala> "cat".map(Character.toLowerCase(_) - 'a' +  1)
res24: Seq[Int] = ArrayBufferRO(3, 1, 20)
```

Thus the entire function for determining if the word is a match is

[sourecode language=”scala”]
/**
* Determines if the word has the desired property of the ordinal position
* of first letter equalling the sum of the ordinal positions of the other
* letters
* Expects letters in the range [a-zA-Z];
*/
def matches(word: String): Boolean = {
if (word.length() < 2) {
false
}
else {
val ordinals = word.map(Character.toLowerCase(_) – 'a' + 1)
val ordinalSum = sum(ordinals.drop(1))
ordinals(0) == ordinalSum
}
}
[/sourecode]

Iterating over the lines in a file

Remember how it took 20 lines to iterate over all the lines in a file?  Fortunately Scala makes it incredibly easy:

```val lines =  scala.io.Source.fromFile("dict.txt").getLines
```

The variable is actually not an array or a list; it is an iterator over the lines in the file.  But iterators are still iterable, so all of our previously mentioned functions for dealing with iterable objects still work.  Again, rather than looping over each element, explicitly testing, and printing whether it matched, we will use a functional approach, namely the ‘filter’ function.

```scala>  List(1,2,3,4).filter(_%2==0)
res25: List[Int] = List(2, 4)
```

The function passed into filter must return Boolean; since our matches() function does that, we can insert it right in:

```val lines =  scala.io.Source.fromFile("dict.txt").getLines
val matching =  lines.filter(matches)
matching.foreach(print(_))
```

When we run the complete code, we get the following list of matches:

• acknowledgements
approximation
bumptiously
capitalizations
circuitously
conceptualizing
consciousness
consistently
credulousness
crystallizing
disconcertingly
discriminatory
electrocutions
excommunication
existentialism
experimentally
exploitations
expressively
extraneously
governmentally
impersonations
incomprehensibly
indispensability
initializations
intercommunicated
interpolations
notwithstanding
organizationally
oversimplifying
phenomenologically
sportswriting

Wait a minute… what’s going on here?  These obviously don’t follow the pattern.  Let’s open a terminal and do some testing.

First we paste our two helper method definitions in

``` Welcome to Scala version 2.7.3.final (Java  HotSpot(TM) Client VM, Java 1.5.0_22).
Type in expressions to have  them evaluated.
Type :help for more information.

scala>  def sum(nums: Iterable[Int]): Int = {
|          nums.reduceLeft[Int](_+_)
|     }
sum: (Iterable[Int])Int

scala>

scala>     /**
|      * Determines  if the word has the desired property of the ordinal position
|      * of first letter equalling the sum of the ordinal positions of  the other
|      * letters
|      * Expects letters in  the range [a-zA-Z];
|      */

scala>     def  matches(word: String): Boolean = {
|         val ordinals =  word.map(Character.toLowerCase(_) - 'a' + 1)
|         val  ordinalSum = sum(ordinals.drop(1))
|         ordinals(0) ==  ordinalSum
|     }
matches: (String)Boolean

scala> matches("table")
res0: Boolean = true

scala>  matches("chair")
res1: Boolean = false

scala>  matches("consistently")
res2: Boolean = false
```

This is very strange.  “consistently” is one of the words on the list, but it doesn’t pass the test on its own.  In fact, none of them do.

What’s the problem?  After googling and debugging for a bit, I realized that the precondition I was assuming in my matches method was being violated; the letters were not in the range [A-Za-z].  How could that be?  Well, it turns out that the getLines() method returns the lines in the file – with new lines included!

```scala> matches("consistently\r\n")
res5: Boolean = true
```

(The file had been created on Windows, and thus has a carriage feed as well as a new line marker).

Fortunately there is a method to eliminate whitespace (including control characters like these); it’s known as trim.

We can put the trim in one of two places, either in the matches() method itself,

```def matches(word: String): Boolean = {
val ordinals = word.trim().map(Character.toLowerCase(_) - 'a' + 1)
val ordinalSum = sum(ordinals.drop(1))
ordinals(0) == ordinalSum
}

scala> matches("consistently\r\n")
res6: Boolean = false

scala> matches("consistently")
res7: Boolean = false

```

Or we can introduce the trim while iterating over the lines in the collection.  I’ve opted for this second approach; I’m making it a precondition of calling the method matches() that the input is already sanitized.  We introduce an implicit mapping from the string to the trimmed version of the string:

```// An iterator of lines in the file; note that they have newline control characters
val lines = scala.io.Source.fromFile("dict.txt").getLines
// Filter the lines, eliminating the new lines through trim mapping
val matching = lines.filter(i => matches(i.trim()))
matching.foreach(print(_))
```

After making the change, the result is

• cab
• hag
• jade
• leaf
• leg
• maced
• mica
• mid
• need
• pig
• real
• ride
• same
• sand
• seam
• sod
• table
• toad
• toe
• vial
• ward
• whack
• who
• wick
• win
• yeas
• yet
• zebra
• zinc

Tada!

The final version of the program is

```object OrdinalPositionSolver {
/**
* Determines if the word has the desired property of the ordinal position
* of first letter equalling the sum of the ordinal positions of the other
* letters
* Expects letters in the range [a-zA-Z];
*/
def matches(word: String): Boolean = {
if (word.length() < 2) {
false
}
else {
val ordinals = word.map(Character.toLowerCase(_) - 'a' + 1)
val ordinalSum = sum(ordinals.drop(1))
ordinals(0) == ordinalSum
}
}

def sum(nums: Iterable[Int]): Int = {
nums.reduceLeft[Int](_+_)
}

def main(args: Array[String]) {
// An iterator of lines in the file; note that they have newline control characters
val lines = scala.io.Source.fromFile("dict.txt").getLines
// Filter the lines, eliminating the new lines through trim mapping
val matching = lines.filter(i => matches(i.trim()))
matching.foreach(print(_))
}
}
```

Conclusion

I have solved the puzzler in two different ways, once in an imperative Java style and once in a more functional Scala style.  The functional way is extremely concise and expressive, doing in 30 lines of code what it takes the Java code to do in over 60, confirming the claim that a typical Scala program is at least twice as compact as the corresponding Java program.  I have introduced some of the salient syntactic differences between Java and Scala. I have also introduced some of the mainstays of the functional programming paradigm, namely map, reduce, and filter.  While there are efforts to make Java more functional, the fact that you cannot pass functions as objects severely inhibits the use of functional programming paradigms.