Search Results

Keyword: ‘car talk’

Car Talk Puzzler #5: The Perfect Square Dance

August 18, 2011 2 comments

PUZZLER: The Perfect Square Dance!

Sally invited 17 guests to a dance party. She assigned each guest a number from 2 to 18, keeping 1 for herself. The sum of each couple’s numbers was a perfect square. What was the number of Sally’s partner?

Puzzler

The fifth in my ongoing series of solving Car Talk Puzzlers with my programming language of choice.  I’m using Python again, just like last time.

There are a few pieces to this.  The first is, how do we generate a list of all possible pairs that match the perfect square constraint?  With list comprehensions and a helper function this is easy.

def perfect_square(n):
  return math.sqrt(n) == int(math.sqrt(n))

# range creates a list that's exclusive of last number.  Thus to go from 1 to n,
# use range(1, n+1)
guests = range(1, num_guests + 1)
# By enforcing the x# a whole bunch of equivalent pairs (e.g. (3,6) and (6,3)).
pairs = [(x,y) for x in guests for y in guests if x<y and perfect_square(x+y)]
>>> guests
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
>>> pairs
[(1, 3), (1, 8), (1, 15), (2, 7), (2, 14), (3, 6), (3, 13), (4, 5), (4, 12), (5, 11), (6, 10), (7, 9), (7, 18), (8, 17), (9, 16), (10, 15), (11, 14), (12, 13)]
OK great.  At this point I have 18 pairs; 9 of these pairs together form the correct setup.  Now, I could try to be very clever and use logic to deduce the correct pairs.  But I’m lazy and it’s a small problem, so I’m going to use brute force.  I’m just going to take all combinations of 9 pairs and test to see which one uses each guest exactly once.  Not only am I so lazy as to do it this way, I’m not even going to write code to calculate the combinations.  Instead, I’ll use the excellent itertools package.
>>> itertools.combinations([1,2,3,4,5], 2)

# This is a sort of generator object which lazily returns the values as needed.
# To force them to all be evaluated at once, to see how this works,
# wrap the call in a list function.
>>>list(itertools.combinations([1,2,3,4,5],2))
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

This performs exactly as how we would expect.  Note that I want combinations rather than permutations because the order does not matter.

As I mentioned earlier, I assume that a brute force solution is going to be fast enough.  Let me check my math here.  How many 9-element combinations taken from an 18-element set are there?
N choose K formula

N choose K formula - number of k element combinations from set of n elements

Number of combinations

Yeah, I think we can handle checking 48620 combinations.

OK, but how do we know whether a given combination (9 pairs of numbers) match our criteria?  The easiest way is to check if the number of unique elements is the same as the number of guests; this indicates that each guest is used only once.  First we flatten our nested list of tuples into a single list, and then use a set to check uniqueness:

def flatten(nested):
  """ Flatten one level of nesting.  Returns a generator object
  For instance:
  list(flatten([(1,3),(5,6)])) --> [1,3,5,6] """
  return itertools.chain.from_iterable(nested)

def all_guests_present_once(combination):
  """ Returns whether each guest is present once
  Combination is a list of tuples, e.g. [(1,5),(7,8)]
  """
  flattened = list(flatten(combination))
  return len(set(flattened)) == len(flattened)

>>> all_guests_present_once([(1,3),(4,5)])
True
>>> all_guests_present_once([(1,3),(3,6)])
False
As you can see, I’m shortcutting a little bit and not checking for the perfect square aspect, since we already did that when constructing our set of pairs.

OK we’re ready to throw it all together.


def dance_arrangement(num_guests):
  """
  Returns a valid pairing for all guests if possible, else an empty set
  """
  # Clearly you need an even number of guests to have everyone paired
  if num_guests % 2 == 1:
    return []
  else:
    # range creates a list that's exclusive of last number.  Thus to go from 1 to n,
    # use range(1, n+1)
    guests = range(1, num_guests + 1)
    # By enforcing the x    # a whole bunch of equivalent pairs (e.g. (3,6) and (6,3)).
    pairs = [(x,y) for x in guests for y in guests if x    # brute force search
    all_arrangements = itertools.combinations(pairs, num_guests / 2)
    return filter(all_guests_present_once, all_arrangements)

Running the program with num_guests = 18, we get

[((1, 15), (2, 14), (3, 13), (4, 12), (5, 11), (6, 10), (7, 18), (8, 17), (9, 16))]
Tada!  Thus Sally’s partner was number 15.
I stumbled onto this page which also sought to solve this problem using programming; it ends with the question
“I wonder if 18 is unique as the total number of dancers which has a solution.  It should be easy to modify the program to check”
It is very easy to modify, and I checked.  I ran the program on all number of guests less than 20, and these are the results:
8 [((1, 8), (2, 7), (3, 6), (4, 5))]
14 [((1, 8), (2, 14), (3, 13), (4, 12), (5, 11), (6, 10), (7, 9))]
16 [((1, 8), (2, 7), (3, 6), (4, 5), (9, 16), (10, 15), (11, 14), (12, 13))]
18 [((1, 15), (2, 14), (3, 13), (4, 12), (5, 11), (6, 10), (7, 18), (8, 17), (9, 16))]

As you can see, 8, 14, and 16 guests can also be paired up in this way.  Something to keep in mind the next time you are going to have a party.

Full sourcecode can be found on Github.

Car Talk Puzzler #4: Flipping Ages

October 26, 2010 2 comments

RAY: This was sent in many weeks ago by Wendy Gladstone, and as usual I tweaked it a little bit.

She writes: “Recently I had a visit with my mom and we realized that the two digits that make up my age when reversed resulted in her age. For example, if she’s 73, I’m 37. We wondered how often this has happened over the years but we got sidetracked with other topics and we never came up with an answer.

“When I got home I figured out that the digits of our ages have been reversible six times so far. I also figured out that if we’re lucky it would happen again in a few years, and if we’re really lucky it would happen one more time after that. In other words, it would have happened 8 times over all. So the question is, how old am I now?”

Question
Answer

Here’s the fourth in my Car Talk Puzzler series; today I’m going to be using Python because it’s my current favorite language, and because it’s well suited to filtering, mapping, etc.  I won’t put too much commentary here.

#  Find all the ages such that the second age is the reverse of the first  age.  Don't worry that there are a lot of impossibilities; we'll fix it  through filtering
# Note that [::-1] is the slice operator that says iterate backwards through the string; this effectively reverses the list.
 matching_ages = map(lambda x:(x, int(str(x)[::-1])), range(0,100))
 matching_ages
 # OUT: [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7),  (8, 8), (9, 9), (10, 1), (11, 11), (12, 21), (13, 31), (14, 41), (15,  51), (16, 61), (17, 71), (18, 81), (19, 91), (20, 2), (21, 12), (22,  22), (23, 32), (24, 42), (25, 52), (26, 62), (27, 72), (28, 82), (29,  92), (30, 3), (31, 13), (32, 23), (33, 33), (34, 43), (35, 53), (36,  63), (37, 73), (38, 83), (39, 93), (40, 4), (41, 14), (42, 24), (43,  34), (44, 44), (45, 54), (46, 64), (47, 74), (48, 84), (49, 94), (50,  5), (51, 15), (52, 25), (53, 35), (54, 45), (55, 55), (56, 65), (57,  75), (58, 85), (59, 95), (60, 6), (61, 16), (62, 26), (63, 36), (64,  46), (65, 56), (66, 66), (67, 76), (68, 86), (69, 96), (70, 7), (71,  17), (72, 27), (73, 37), (74, 47), (75, 57), (76, 67), (77, 77), (78,  87), (79, 97), (80, 8), (81, 18), (82, 28), (83, 38), (84, 48), (85,  58), (86, 68), (87, 78), (88, 88), (89, 98), (90, 9), (91, 19), (92,  29), (93, 39), (94, 49), (95, 59), (96, 69), (97, 79), (98, 89), (99,  99)]

# Here we filter by only allowing matches in which the  mother's age is greater than that of the child.  Note the use of a  lambda expression, basically an anonymous function.
filtered1 = filter(lambda (mother,child):mother > child, matching_ages)
 filtered1
 # OUT: [(10, 1), (20, 2), (21, 12), (30, 3), (31, 13), (32, 23), (40,  4), (41, 14), (42, 24), (43, 34), (50, 5), (51, 15), (52, 25), (53, 35),  (54, 45), (60, 6), (61, 16), (62, 26), (63, 36), (64, 46), (65, 56),  (70, 7), (71, 17), (72, 27), (73, 37), (74, 47), (75, 57), (76, 67),  (80, 8), (81, 18), (82, 28), (83, 38), (84, 48), (85, 58), (86, 68),  (87, 78), (90, 9), (91, 19), (92, 29), (93, 39), (94, 49), (95, 59),  (96, 69), (97, 79), (98, 89)]

# Assume that the mother was at least 15 when she had the kid, and no more than 60
filtered2 = filter(lambda(mother, child):mother-child >= 15 and mother-child < 60, filtered1)
 filtered2
 # OUT: [(20, 2), (30, 3), (31, 13), (40, 4), (41, 14), (42, 24), (50,  5), (51, 15), (52, 25), (53, 35), (60, 6), (61, 16), (62, 26), (63, 36),  (64, 46), (71, 17), (72, 27), (73, 37), (74, 47), (75, 57), (82, 28),  (83, 38), (84, 48), (85, 58), (86, 68), (93, 39), (94, 49), (95, 59),  (96, 69), (97, 79)]
 len(filtered2)
 # OUT: 30

# Create a new list comprised of the differences in age between mother and child
 age_diff = map(lambda(mother,child):mother-child, filtered2)
 age_diff
 # OUT: [18, 27, 18, 36, 27, 18, 45, 36, 27, 18, 54, 45, 36, 27, 18, 54, 45, 36, 27, 18, 54, 45, 36, 27, 18]
 sorted(age_diff)
 # OUT: [18, 18, 18, 18, 18, 18, 18, 27, 27, 27, 27, 27, 27, 36, 36, 36, 36, 36, 45, 45, 45, 45, 54, 54, 54]

# The puzzler states that it's will happen a total of 8 times; that matches the age difference of 18 years

 filter(lambda(mother,child):mother-child == 18, filtered3)
# OUT: [(20, 2), (31, 13), (42, 24), (53, 35), (64, 46), (75, 57), (86, 68), (97, 79)]

Thus the mother is currently 75 years old and the daughter is 57.  Tada

 

Car Talk Puzzler #3: The Palindromic Odometer

May 15, 2010 Leave a comment

The Palindromic Odometer

Driving along, Terry notices that the last four digits on the odometer are palindromic. A mile later, the last five digits are palindromic. [A mile later, the middle four digits are palindromic.] [One mile after that], all six are palindromic. What was the odometer reading when Terry first looked at it?

Full question
Answer

This is the third in my series of Car Talk puzzler solutions using whatever programming language strikes my fancy. Just like the last one I wrote, this one uses Scala. This is a much shorter post, as I am assuming some familiarity with Scala; go back and read the last post if you haven’t already.

object PalindromicPuzzlerSolver {
    // Pad out numbers to 6 places
    // Note that I can cal Java library functions seamlessly
    val df = new java.text.DecimalFormat("000000")

    // A string is a palindrome if it reversed equals itself
    def isPalindrome(word: String): Boolean = {
        // Reverse is a method of a RichString, which a String can be implicitly converted
        // into. Necessary to convert the RichString back into String after the reversal
        word == word.reverse.toString()
    }

    def fitsDescription(miles: Int): Boolean = {
        // Last 4 are palindome (dropping first 2)
        isPalindrome(df.format(miles).drop(2)) &&
        // Add one, last 5 are palindrome
        isPalindrome(df.format(miles + 1).drop(1)) &&
        // Add two more, all six are a palindrome
        isPalindrome(df.format(miles + 3))
    }

    def main(args: Array[String]) {
        val max = 1000000
        println( 0 until max filter fitsDescription )
        // Prints out
        // RangeF(198888, 199999)

        // This is the same as the java style:
        // println( (0.until(max)).filter(fitsDescription) )
        // This syntax only works when you are dealing with
        // methods that take one argument.
    }
}

Thus the solution is 198888, just as the answer proclaims. Another win for brute force.

There are three noteworthy things in this example, which didn’t come up in the last post (or weren’t explained fully)

1. Interoperability with Java
2. Use of drop
3. Convenience methods for specifying a range

Interoperability with Java

Any Java class can be imported and used with Scala; that is one of its strongest selling points. Scala runs in the same JVM as Java, so it makes sense that it should have access to Java classes. In fact many Scala classes are thin wrappers around Java objects, with syntactic sugar built in. For instance, Scala has a BigInt class which wraps a Java BigInteger, while providing overloaded methods to allow them to be used more like standard numbers. For instance,

scala> BigInt("103058235287305927350") + BigInt("288888203959230529352")
res16: BigInt = 391946439246536456702

scala> new java.math.BigInteger("103058235287305927350").add(new java.math.BigInteger("288888203959230529352"))
res21: java.math.BigInteger = 391946439246536456702

Note that the + is actually a method call; this is exactly the same thing as calling

scala> BigInt("103058235287305927350").+(BigInt("288888203959230529352"))
res22: BigInt = 391946439246536456702

In Scala, method names don’t have to be alphanumeric, which is how it gets away with what looks like operator overloading. This makes it a lot nicer to work with classes like BigDecimal or BigInteger, as you can use the more commonly used addition and subtraction symbols rather than explicitly calling “add” and “subtract” methods. Just realize that you are really calling methods like any other under the hood. When you understand this, you’ll also understand why Scala uses an underscore instead of * for wildcard – * can be used in method names, as it is used for multiplication!

Drop

Scala has full support for slicing iterable objects; see my previous discussion on slices if this term is unfamiliar.

scala> List(1,2,3,4).slice(1,3)
res27: List[Int] = List(2, 3)

scala> List(1,2,3,4).slice(1)
warning: there were deprecation warnings; re-run with -deprecation for details
res28: Seq[Int] = List(2, 3, 4)

scala> List(1,2,3,4).drop(1)
res29: List[Int] = List(2, 3, 4)

So drop(n) is exactly the same as slice(n) – it provides a new list with the first n elements removed. I use drop instead of slice due to the deprecation of the single argument form of slice.

Specifying a range
If you need to iterate over a range of numbers in Java, you’d do something like
for (int i = 0; i < max; i++) {
}

whereas in Python you can do something like
for x in range(max):

Scala similarly provides methods to create a range of numbers to iterate over.

scala> 0 until 10
res9: Range = Range(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> 0 to 10
res10: Range.Inclusive = Range(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

Again, I want to stress that until is a method like any other; you are just free to leave off the . and the parens when it is unambiguous what you mean. Note that these commands are actually creating a sequence in memory. If you only need to access each element one at a time, and you are dealing with a large range, you might instead create an Iterator rather than a sequence. The Iterator will create each subsequent number as necessary, rather than building up the whole list ahead of time. This is much more space efficient.

Note that Python makes this distinction as well:

>>> range(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> xrange(10)
xrange(10)

xrange returns a generator object, as opposed to range which returns the actual list.

Returning to Scala, if I wanted an iterator instead I would do

scala> Iterator.range(0,10)
res11: Iterator[Int] = non-empty iterator

scala> Iterator.range(0,10).foreach(println)
0
1
2
3
4
5
6
7
8
9

Conclusion
I have shown another solution using Scala, while illustrating a few more features. In particular one needs to understand that Scala’s syntactic sugar is actually masking standard function calls under the hood; x + y is the same as x.+(y), where “+” is a valid function name.

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?

Answer:

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.

Car Talk Puzzler #1: The Bank Temperature Sign

May 1, 2010 1 comment

One of my favorite podcasts is NPR’s Car Talk, and one of my favorite segments of the show is the weekly puzzler, in which listeners have a week to solve a puzzle that is usually automotive in nature.  It struck me that this would be an ideal way to illustrate some beginning programming techniques, while also illustrating some real world problem solving uses of programming.  Initially I will be posting solutions in Python, but I will probably show how to do them in other ways as well.

You can see the whole archive of 2010 puzzles, but the specific one I’m starting with can be found here.

In short:

PREVIOUS PUZZLER: Stevie and His Moto
Stevie’s riding his motorcycle to work when he sees a big sign displaying the temperature in Fahrenheit and in centigrade. The digits are exactly reversed. He notices the same thing on the way home. What were the temperatures?

This is an ideal choice for a programming solution because it can be brute forced; a computer can try all possible solutions near instantaneously, something they are very good at.  Not all of the puzzlers are so conducive to a programmatic solution.

For those who already know the basics of programming, I’ll post my program first.  Afterwards I post explanations more geared towards beginners, but there still is something that more advanced programmers might not know in Python.

Here’s my solution:

def fahrenheitToCelsius(temp):
 return  (temp - 32) / 1.8

def reverseString(s):
 # Step size is -1,  so start at the end and work backwards
 return s[::-1]

#  Presumably it was above freezing if it's a spring day
LOW_TEMP_FAHRENHEIT  = 32
# Presumably it was below 100 degrees
HIGH_TEMP_FAHRENHEIT =  100

def main():
 for temp in range(LOW_TEMP_FAHRENHEIT,  HIGH_TEMP_FAHRENHEIT):
 # Round the float to nearest whole number,  cast to integer
 celsius = int(round(fahrenheitToCelsius(temp)))

 # Convert the integers to strings so as to be able to reverse the  digits
 fahrenheitString = str(temp)
 celsiusString =  str(celsius)

 # See if the reversed digits match
 if  fahrenheitString == reverseString(celsiusString):
 print temp,  celsius

if __name__ == '__main__':
 main()

Spoiler:

python Temperature.py
61 16
82 28

Tada!  The program calculated the correct solution.

Let’s break the problem into a few logical steps:

1) Convert a Fahrenheit temperature to Celsius (we’re going to be able to do this in order to determine what the temperature on the signs must have been)
2) Round a number to the nearest whole number (converting Fahrenheit to Celsius will often leave a fractional part, but most signs don’t display temperature in increments smaller than 1 degree)
3) Reverse the digits of a number (in order to tell whether the temperatures are the reverse of each other)
4) Test a whole bunch of Fahrenheit temperatures to discover the matching Celsius ones, using steps 1 – 3.

Let’s explain each part in order.

Convert Fahrenheit to Celsius

The first part is the most straightforward:

def fahrenheitToCelsius(temp):
 return (temp  - 32) / 1.8

There’s not a lot to say about this part; this is the formula to convert from Fahrenheit to Celsius.  If you’re new to Python or programming as a whole, this whole block is known as a method declaration; basically methods take in data, do some calculation with the data, and more often than not, return a new piece of data.  In our case, we are passing in the temperature in Fahrenheit, and what comes out of it is a temperature in Celsius.  Just to show that this indeed works:

Python  2.6.4 (r264:75708, Oct 26 2009, 08:23:19) [MSC v.1500 32 bit (Intel)] on  win32
Type "help", "copyright", "credits" or "license" for more  information.
>>> def fahrenheitToCelsius(temp):
...      return (temp - 32) / 1.8
...
>>> fahrenheitToCelsius(212)
100.0
>>>  fahrenheitToCelsius(32)

Round a number to nearest whole number

OK, how about rounding a fractional number to the nearest whole number?

Python has a function called, easily enough, round which does exactly that.  You choose how many decimal places you want; by default it rounds to 0 (i.e. the nearest whole number)

>>> round (2.252,  2)
2.25
>>> round (2.252 )
2.0

Notice how even though we round to 0 decimal places, the answer is “2.0”.  This is because round returns a double rather than an integer.  Integers are what we would think of as “whole numbers” – -1023, 2035, 733, etc. etc.  Doubles are an (inexact) representation of a number with a fractional part.  It’s a little beyond the scope of this tutorial, but suffice to say there are numbers that a computer cannot represent exactly

>>> round (2.1, 1)
2.1000000000000001

The reason I make the distinction is that we want to treat our numbers as integers; after all we’re rounding them to 0 decimal places, so they are in fact integers.  We need the computer to treat them that way.  We do this with the int() method

>>>  round(2.23501)
2.0
>>> int(2.0)
2

Note too that we can combine these two expressions into one; you’ll often see computer programs written this way, as it allows us to express thoughts more concisely.  So the above could be replaced by

>>> int(round(2.23501))
2

This expression can be read as “after rounding the number to 0 decimal places, convert it to an integer”.

Reverse the digits of a number

How do we reverse the digits of a number?  Well, first, we’re going to treat the number as if it were an arbitrary string of letters (characters) rather than numbers.  We are going to cast the integer into a string.  Strings are a programming concept used to express textual information; they are usually enclosed in quotes.

>>> "hello"
'hello'

The string representation of a number is different than the number itself.  For instance, when two strings are “added” together, they become joined (concatenated).  When two numbers are added together, they are added in the mathematical sense.  For instance

>>>  "2" + "2"
'22'
>>> 2 + 2
4

We are going to treat the numbers as strings because it is fairly easy to reverse the characters of a string, but hard to do so for a number.  With a string, you can access each individual character; you cannot (easily) do that with a number.  To understand how to reverse the characters of a string, you need to understand a bit about iterating over collections in Python, as well as a concept known as “slice”.

Let’s start with the basic Python data structure known as a list.  You can put a heterogenous (mixed) set of objects into a list:

a = [2,3,5,6,"hello","world"]

In this case we’ve put a bunch of numbers, and then two strings into the list data structure.  We can get out each element in the list by ‘indexing into’ the array.  Unlike in the normal world, in Python you must count starting at 0.  So instead of counting 1,2,3,…, you count 0,1,2,… .  In other words, if we want to get out the first item we put into the list (the 2), we have to ask for the element at position 0.

>>> a[0]
2

The number within brackets is the index of the element you are accessing from the list.

Now, what if we want the first 3 elements of the list instead of just the first one?  To do that, we need to use what’s known as a “slice” in Python.  The syntax is [startIndex:endIndex+1].  In other words, if we want the first three elements, those at position 0, 1, and 2, we would ask for

>>>  a[0:3]
[2, 3, 5]

This can be read as, “start at the element with index 0 and stop before you get to the element with index 3”.  Yes, this is a little counter-intuitive – but just stick with me.

What if you want all of the items after a certain point?  For instance, I want all the elements including and after the 2nd element.  To do that, you omit the second number, but keep the colon.  This is saying “start and keep going till you reach the end of the collection”

>>>  a[1:]
[3, 5, 6, 'hello', 'world']

You can also omit the first number, in which case it is assumed that you want to start at the beginning of the collection

>>> a[:5]
[2, 3, 5, 6, 'hello']
>>>  a[0:5]
[2, 3, 5, 6, 'hello']

What happens if we omit both numbers?

>>>  a[:]
[2, 3, 5, 6, 'hello', 'world']
>>> a
[2, 3, 5,  6, 'hello', 'world']

We get back all the items of the original list!  This makes sense if you think about it; we assume we’re starting at the beginning, and we assume we’re ending at the end.  Why do I bring this up?  Because there’s one last element you can add to take a new slice out of array: the stride argument.

Whereas we’ve been taking some contiguous subset of the list, there’s nothing preventing us from skipping more than one number between every element, in effect taking every second, or every nth number.

>>> a[::2]
[2, 5, 'hello']

Interestingly, this number doesn’t have to be positive either; if it’s negative it means we start at the end of the collection and work our way towards the front of the list:

>>>  a[::-2]
['world', 6, 3]

Putting this all together then, one way to get the reverse of a list is to take a new slice out of it, taking the whole thing but backwards:

>>> a[::-1]
['world', 'hello', 6, 5,  3, 2]

(More advanced readers: an alternate way, and arguably easier, is to use a list comprehension and the reversed method:

>>> [i for i in reversed(a)]
['world',  'hello', 6, 5, 3, 2]

)

Hopefully you understand how to take slices out of a list now; you can read a whole lot more about slices at any number of sites, including this great introduction to Python.

But why did I start talking about lists?  Weren’t we trying to reverse a string, not a list?  Well, it turns out you can view a string as a list of individual letters (characters), and treat it exactly the same as we did for lists, including indexing and slicing.

>>> "hello"[0]
'h'
>>>  "hello"[:3]
'hel'
>>> "hello"[::-1]
'olleh'

So, the method for reversing a string (or really any subscriptable object, but that’s another issue) is

def  reverseString(s):
 # Step size is -1, so start at the end and work  backwards
 return s[::-1]

The only thing left to say in this regard is that if we want to convert a number to a string, this is accomplished by the str() method.

Iterate over a range of numbers

We want to test a whole range of temperatures, looking for those that yield the properties desired in the puzzle.  Fortunately there is an easy way to generate a list of numbers in a given range in Python: the range command.

</div>
>>>  range(5)
[0, 1, 2, 3, 4]
>>> range(5,10)
[5, 6, 7, 8,  9]
<div>
Once we have our list of numbers, we want to iterate over them, pulling out each temperature.  We do that with a simple for loop:
>>> for x in range(5):
...     print  x
...
0
1
2
3
4
Or, for our purposes
for  temp in range(LOW_TEMP_FAHRENHEIT, HIGH_TEMP_FAHRENHEIT):

Where LOW_TEMP_FAHRENHEIT and HIGH_TEMP_FARENHEIT are two constants defined to limit the range of numbers we are looking at.

Conclusion

I’ve illustrated a brute-force solution to a recent puzzler.  Despite being a fairly simple challenge, it illustrates some important features of Python, including range generation, list comprehension, slicing to reverse selections, and converting between different data types.

I’d love to see some other solutions to this problem, so post in the comments if you have ideas.

Go gotcha #1: variable shadowing within inner scope due to use of := operator

March 3, 2014 2 comments

Disclaimer: Go is open source and developed by many Google employees. I work for Google, but the opinions expressed here are my own and do not necessarily represent that of Google.

Last week I described how the range keyword in conjunction with taking the address of the iterator variable will lead to the wrong result. This week I’ll discuss how it’s possible to accidentally shadow one variable with another, leading to hard to find bugs.

Let’s take the same basic setup as last week; we have a Solution struct, and we’re searching for the best (lowest cost) one in a slice of potential candidates.

package main

import "fmt"

type Solution struct {
    Name     string
    Cost     int
    Complete bool
}

func FindBestSolution(solutions []*Solution) *Solution {
    var best *Solution
    for _, solution := range solutions {
        if solution.Complete {
            if best == nil || solution.Cost < best.Cost {
                best := solution
                fmt.Printf("new best: %v\n", *best)
            }
        }
    }
    return best
}

func main() {
    solutions := []*Solution{
        &Solution{
            Name:     "foo",
            Cost:     10,
            Complete: true,
        },
    }
    fmt.Printf("Best solution is: %v", FindBestSolution(solutions))
}

Output:

new best: {foo 10 true}
Best solution is: <nil>
Program exited.

Go playground

What’s going on? We see that we have a good candidate solution from the debugging information. Why does the function return the wrong value?

The bug is in this line:

best := solution

The problem is that we’re declaring and initializing a new variable (with the := operator) rather than assigning to the existing best variable in the outer scope. The corrected line is

best = solution

Use = to change the value of an existing variable, use := to create a new variable.

If I had not referenced the new variable with the debug print statement, this code would not have compiled:

if best == nil || solution.Cost < best.Cost {
    best := solution
}
prog.go:16: best declared and not used
 [process exited with non-zero status]

Go playground

Why is this shadowing of variables in other scopes allowed at all?

There is a long thread on the subject on Go-nuts, debating this subject.

Arguments For

Nate Finch:

type M struct{}

func (m M) Max() int {
    return 5
}

func foo() {
    math := M{}
    fmt.Println(math.Max())
}

If shadowing didn’t work, importing math would suddenly break this program.


My point was about adding an import after writing a lot of code (when
adding features or whatever), and that without shadowing, merely importing
a package now has the potential to break existing code….

The current shadowing rules insulate code inside functions from what
happens at the top level of the file, so that adding imports to the file
will never break existing code (now waiting for someone to prove me wrong
on this 😉

Rui Maciel:

There is a simpler and better solution: use a short variable declaration
when you actually want to declare a variable, and use an assignment
operator when all you want to do is assign a value to a variable which
you’ve previously declared. This doesn’t require any change to either
the language or the compiler, particularly one which is that cryptic.

Arguments Against

Johann Höchtl:

See it this way. I can carry a gun in my hand aiming towards a target. I
pull the trigger and hit the target. Everything happens exactly the whay
it is expected to happen.

Suddenly an inner block jumps in … the instructor. Me, a gun in my
hand, the instructor in between and on the other side the target. I pull
the trigger.

Still … everything happens exactly the way it is told to behave. Which
still makes the end results not a desirable result. Adding an “inner
block”, which by itself is behaving in a fully specified way,
influences the whole.

Somewhat odd I admit, but you may get what I mean?

Conclusion

I don’t think that the shadowing should be an error but I do think there should be a warning. The go vet tool already helps find common mistakes, such as forgetting to include arguments to printf. For instance:

example.go:

package main

import "fmt"

func main() {
    fmt.Printf("%v %v", 5)
}

Run:

go vet example.go

example.go:6: missing argument for Printf verb %v: need 2, have 1

If the vet tool were modified to add this warning, it would occasionally yield false positives for those cases where the shadowing is done intentionally. I think this is a worthwhile tradeoff. Virtually all Go programmers I’ve talked with have made this mistake, and I would be willing to bet that these cases are far more frequent than intentional shadowing.

Book Review: Team Geek by Ben Collins-Sussman and Brian W. Fitzpatrick

August 27, 2012 1 comment

Team Geek: A Software Developer’s Guide to Working Well with Others, by Ben Collins-Sussman, Brian W. Fitzpatrick
Team Geek cover image

Disclaimers: I received a free copy of this book to review from O’Reilly. I work at Google, as do the authors, but this review reflects my views only and not necessarily those of Google.

One thing I have learned over my three years of professional software development is that you really are writing code for other people to read, not for the compiler. This dual nature of programming, the precise, exacting specifications that run on the computer, and the imprecise, ambiguous human factor, is fascinating to me. Ben Collins-Sussman and Brian W. Fitzpatrick, two of the engineers behind the SVN version control system, currently working at Google, have written Team Geek, a book that aims to impart lessons learned in creating better software through better people skills and teamwork.

Programmers tend to lionize the lone programmer, like Linus Torvalds of Linux fame. In some rare cases, geniuses do manage to accomplish incredible things on their own. But in most cases, great software is a collaborative effort performed by a team of people of varying skills, backgrounds, and communication styles. There are many books which help improve your technical proficiency, but this is one of the few I’ve encountered that addresses the importance of working effectively with teammates.

I won’t reiterate all of the content of the book but there are a few themes that occur throughout that I’d like to touch on.

The first is that it is crucial to spread the knowledge throughout the team rather than keeping it siloed in the heads of a few people. They whimsically refer to this as the “bus factor” – how many people would it take to be hit by a bus (or be otherwise incapacitated) before the project would fall apart?

One way of increasing this shared knowledge is through the use of communication channels that are easily archivable and searchable rather than through point to point communication. For instance, it is better to ask questions of the team via an IRC channel or mailing list than to ask someone directly, because that exchange can be easily found in the future. It also gives other team members visibility and input into the decision making process.

The culture of the team is also frequently discussed. In the previous example, archiving technical discussions would do no good if no one bothers to search and try to find answers by themselves prior to asking someone for the answer. The shared values of the team are crucial to its effectiveness.

Another main theme of the book is focus, or “saying no to all the distractions.” Part of an effective team, the authors say, is a manager who can shield engineers from the chaos inherent in the organization. This is a form of avoiding distractions at a high level – working on things which do not actually matter for your project. One relevant quote I’ve found in this regard is

There is nothing so useless as doing efficiently that which should not be done at all — Peter Drucker

One way the authors suggest to maintain focus is to decide on a mission statement. It might sound cheesy, but they offer a compelling argument as to its efficacy. They relate an example of how they used this technique on one of their projects and it became clear that many of the senior engineers had very different goals and ideas of what the product should do. Had they not forced the team to clearly specify what they were trying to accomplish and what the non-goals of the project were, there would have been significant wasted effort by people working at cross purposes. They use the analogy of a cart being pulled by different team members in different directions – by not working towards one goal, the cart will not move forward as quickly as it would if all were pulling together.

At a lower level, distractions abound as well. While programming, it takes significant concentration and effort to get engrossed in the task at hand and to ‘load’ the program structure into one’s head. Context switching is very bad for productivity because the cost of reloading this state is so high. Sometimes these context-switching distractions come from other team members, such as when someone interrupts to ask a question. The authors suggest that the team come up with a strategy for minimizing these disruptions, both to increase productivity and decrease frustration. For instance, in one team the authors led, any time Alice needs something from Bob, Alice would make her presence known, Bob would verbally acknowledge Bob but not stop what he was doing, finish what he was doing, and only then stop and talk to B.

While much of the book is generalizable to any sort of team environment, the authors do give some coding specific advice. There are discussions on handling code reviews effectively, dealing with people who constantly dig their heels in and criticize others’ technical solutions, and ways to avoid ego while coding.

Conclusion

I thoroughly enjoyed this book, reading it cover to cover over two legs of an international flight. Much of the advice in the book is common sense but there are also many specific, concrete ideas that I had never considered before. I would recommend this book without reservation to anyone working on a team that writes software.

An interview with William Wilson, self-taught developer of Fret Tester and more

March 13, 2012 2 comments

I recently had the opportunity to speak with William Wilson, the man behind Fret Tester, the best guitar fretboard learning application available for iOS, and one of the nicest designed apps I’ve used. I wrote about its great UI features in my previous post, The Best iPhone Guitar Fretboard App: Usability Lessons Learned. I wanted to pick the designer’s brain to see what lessons he could impart about designing usable applications. Here’s what he had to say.


Please tell me a little about your background. Do you design mobile applications for a living or as a hobby?

Guitar Hero Pullquote

I’m actually a professional guitarist. I make my living teaching and performing classical and Spanish guitar in San Diego. I’ve always loved programming, starting with Basic, then HyperCard, Java, Flash, and eventually C. I started designing apps for my guitar students as a way to compete with Guitar Hero. I got tired of hearing: “Sorry Mr. Wilson, I didn’t practice, but I played Guitar Hero, does that count?” My first attempts were in Java, and were really awful. I’ve since done about 15 flash games (on my site guitargames.net) and 4 iOS apps. I’ve mostly learned from books and online tutorials. Right now it’s a hobby, but I’d love to do more of it.


As a musician first and foremost, what were the deficiencies you saw in the other published guitar apps and how did you aim to address them?

Traditionally when learning the neck students start with the natural (not sharp and flat) notes. That way they establish landmarks on the neck. I didn’t see this feature being a big part of any app. For me having the iPhone version just display the natural notes made sense (with a button to shift into sharps). Plus it’s tough to fit 12 buttons on the screen without clutter.

One of the biggest challenges I saw was how to zoom in on the neck. With many of the apps, I tried I lost a sense of where I was on the neck. But if the whole neck was shown it was too small. I decided to have my app zoom to the area that was being tested, but to allow sufficient area on either side so the user had a sense for where they were. Plus I included the option to zoom all the way out should the user prefer it. Related to this, I thought many of the apps lacked reinforcement. When you pushed the correct answer your finger covered it. I added the key style buttons so users could see what note the pushed and thus reinforce the correct answer.

Fret Tester screenshot

Fret Tester screenshot - note that only the natural keys are shown and that the incorrect answer that was pressed pops up above the obstructing finger


How have your students received your work? Have you seen a measurable improvement in their progress?

I wish I could say that the app was a runaway success with my students… Unfortunately there is a mindset out there that you aren’t practicing unless you have a guitar in your hand. Mental practice is too often neglected, both with note naming and music theory. For the students who have taken my advice and used the app I’ve seen good things. I think separating the mental and physical complexities of the guitar is the way to go.


What advice would you offer to other people who are not programmers by trade but have an idea for a program or application that could simplify or improve some aspect of their everyday life? What resources have you found that were useful in turning your dream into reality?

There are tons of great resources out there. I always recommend http://masters-of-the-void.com/ as a first step. Also Steven Kochan’s Programming in Objective C is great for learning to write for iOS.

Obvious pullquote

Outside “traditional” programming there were three books that greatly influenced me. One is The Non-Designer’s Design Book by Robin Williams, it will help you design a decent looking app. Second is Dave Woolridge’s Business of iPhone App Development, make sure you can sell one or two before you spend a year creating an app. And finally Don’t Make Me Think by Steve Krug, a guide for good UI principles.

Also I would say make sure to beta test often. I had about 8 people test Fret Tester and learned something from everyone. I like to hand someone my phone and say, try this. You’d be amazed at how they struggle to find something you thought was obvious.


You mentioned making sure that you can sell a product before you invest too much time in producing it. How do you recommend that app developers do this? Do you create a bare bones v 0.0 prototype and put it on the app store to gauge interest? Or do you have an alternative technique for market research?

Wife nuts pullquote

First I look around and see if there are similar apps already out there. If there are a ton, and they’re good, I move on. If there are none I also move on, since there probably isn’t a market for what I’m designing, I want to at least see things that are similar. My goal is to design an app that reaches an already existing need. Not that I’m always successful in it. After reading Woolridge’s book, as well as listening to Seth Godin’s Purple Cow (Audio Book) I’ve improved in this area. I also just talk to people about my idea. If my wife looks at me like I’m nuts (which happens frequently) I try to rethink things.


Are you working on any new projects currently? Or do you have ideas for the next thing you want to work on?

Yes, I’ve been playing around with Adobe’s new Stage 3D and the Starling Framework. It seems promising. I’m hoping to release my first game using it soon. It is called Tab Warrior and is kind of a cross between Fret Tester and Space Invaders. Also, I’m going to try my hand at an Android app this year.


Great to hear. Thank you for taking the time to speak with me. Do you have any parting thoughts for the readers?

80% pullquote

One thing I read in Apple’s docs was to only include features in an app that 80% of users will use. That totally changed my approach. If you look at Apple’s success I think its largely the result of keeping things simple and easy to use, and gearing products for the average user. Take the same approach in your apps.


Thank you to Mr. William Wilson for granting me this interview. You can find more about him on his website, WilliamWilson.com. See my Google+ album for more screenshots of Fret Tester.

JS 101 – Week 3

February 15, 2011 Leave a comment

In Javascript, functions are first class objects. What does it mean to be a first class object?

A function can be used anywhere an object can be used; in particular, you can pass functions as method arguments. (We did this in last week’s homework by passing the print function into the iterateAndOperate method). This is in contrast to a language like Java where functions are not first class objects, and the programmer must use interfaces and anonymous classes to get around this problem. For instance, in Java, to delay the invocation of a function, you might do the following:

SwingUtilities.invokeLater(new Runnable() {
    @Override
    public void run() {
        System.out.println("I was run!");
    }
})

whereas in Javascript, you could do something like

invokeLater(function() { print("I was run") });

assuming there was an invokeLater function.

Functions and variables share the same namespace. What does this mean and what important implication does this have?

This means that you must take care in not defining variables in the global namespace that have the same name as a function. For instance,

// global variable
x = 5;

function x(args) {
    alert(args);   
}

// The global variable is shadowing the function name;
// the function is not called
x(5);

Douglas Crockford equates Javascript functions with Lambdas, and also mentions that they are a secure construct. Can you do some research and reflect on what he means by ‘secure construct’?

A lambda basically means that you can pass a function as an argument to another function; this is due to the aforementioned first class nature of functions. They are a secure construct because the scope of the functions is such that private variables in function A cannot be accessed by function B when A is passed into B. In other words,

function outer(func) {
  // "undefined", since the ‘privateVariable’
  // field is scoped only to the inner function.
  return func.privateVariable;
}

function inner(a,b,c) {
  var privateVariable = 25;
  return a + ", " + b + ", " + c;
}

alert(outer(inner("cat","dog","bear")));

f

Can you explain the concept of a closure.

A closure means that an inner function continues to have access to variables defined inside of an outer function, even after the outer function has finished. I wrote an example you can view on jsfiddle.

What is the difference between a function and a method?

A method is a function that is bound to an object, and thus it has an implicit “self” reference.

In Javascript there is no implicit type checking of arguments passed to functions. This could lead to bugs if programmers are not careful about what they pass to functions. If you create a function, how would you protect it from well meaning but careless programmers?

You can do defensive checks within the function. For instance, if a method is supposed to take in a number, you could do the following:

function numericalFunction(x) {
    if (typeof(x) != "number") {
        throw("Expected numerical value for numericalFunction; got " + x);
    }
    // Proceed as normal
}

You can also use the arguments implicit variable in the function to check that the number of arguments the user passed in is equal to the number of arguments that the method expects.

Javascript functions have implicit access to something called this. this points to different things depending on how the function was created. Can you explain why we need this, and what it represents in different type of functions.

If a function is created globally, its this pointer will be to the DOMObject. If it’s created and bound to an object, the this pointer points to that object. The following illustrates this:

function f() {
  return "f's this: " + this;
}

function nested() {
  function inner() {
    return "inner's this:" + this;
  }
  return inner();
}

// o is an object; add a method do it
var o = {};
o.f = f;
o.nested = nested;

o.newFunc = function() { return "newFunc's this: " + this; };
o.nestedFunc = function() { 
  var inner = function() {
    return "nestedFunc's inner this: " + this;
  }
  return inner();
}



print(f());
print(nested());
print(o.f());
print(o.nested());
print(o.newFunc());
print(o.nestedFunc());


// prints
// f's this: [object DOMWindow]
// inner's this:[object DOMWindow]
// f's this: [object Object]
// inner's this:[object DOMWindow]
// newFunc's this: [object Object]
// nestedFunc's inner this: [object DOMWindow]
//

Note that only the non nested functions that have been bound to object o point to that object as opposed to the DOMWindow.

The reason we want the this pointer is to be able to introspect on the type and contents of the object that is calling the function. For instance, in my last assignment, I used the this variable to produce a nice representation of an object:

nick = {name:"Nick",age:23};

// This function returns a string representation of whatever
// is invoking it
function selfStringRep() {
  var str = "";
  for (var v in this) {
    // This is not an inherited property
    if (this.hasOwnProperty(v)) {
      str += "’" + v + "’: " + this[v] +"\n";
    }
  }
  return str;
}
Object.prototype.toString = selfStringRep;
print(nick.toString());
// prints
//’name’: Nick
//’age’: 23

4.1

The solution for the cat problem talks about a ‘set’ of names. A set is a collection of values in which no value may occur more than once. If names are strings, can you think of a way to use an object to represent a set of names?

Show how a name can be added to this set, how one can be removed, and how you can check whether a name occurs in it.

var cat_set = {};
// Add a cat
cat_set["Tigger"] = true;
// remove a cat
delete cat_set["Tigger"];

// Check if cat exists
cat_set["Frog"] != undefined

// Wrap it all up nicely: in an object with functions:
var cat_set = {};
cat_set.add_cat = function(cat) {
    this[cat] = true;
}
cat_set.remove_cat = function(cat) {
    delete this[cat];
}
cat_set.cat_exists = function(cat) {
    return this[cat] != undefined;
}

cat_set.add_cat("Frisky");
// prints "true"
show(cat_set.cat_exists("Frisky"))
cat_set.remove_cat("Frisky");
// "false"
show(cat_set.cat_exists("Frisky"))

4.2

Write a function range that takes one argument, a positive number, and returns an array containing all numbers from 0 up to and including the given number.

An empty array can be created by simply typing []. Also remember that adding properties to an object, and thus also to an array, can be done by assigning them a value with the = operator. The length property is automatically updated when elements are added.

// Assumes n >= 0
function range(n) {
    var array = [];
    for (var i = 0; i <= n; i++) {
        array[i] = i;
    }
    return array;
}

4.3

split and join are not precisely each other’s inverse. string.split(x).join(x) always produces the original value, but array.join(x).split(x) does not. Can you give an example of an array where .join(" ").split(" ") produces a different value?

[" ", " ", " "].join(" ").split(" ");
// equals ["", "", "", "", "", ""]

4.4

Write a function called startsWith that takes two arguments, both strings. It returns true when the first argument starts with the characters in the second argument, and false otherwise.

function startsWith(string, pattern) {
    return string.slice(0,pattern.length) === pattern;
}

4.5

Can you write a function catNames that takes a paragraph as an argument and returns an array of names?

Strings have an indexOf method that can be used to find the (first) position of a character or sub-string within that string. Also, when slice is given only one argument, it will return the part of the string from the given position all the way to the end.

It can be helpful to use the console to ‘explore’ functions. For example, type "foo: bar".indexOf(":") and see what you get.

// The sentence is in the form "Blah blah: cat1, cat2, …, catN."
function catNames(paragraph) {
    var colonIndex = paragraph.indexOf(":");
    // Skip the colon and the following space
    var catListString = paragraph.slice(colonIndex + 2);
    return catString.split(", ");
}

/*#p2pu-Jan2011-javascript101*/

Excel 2008 for Mac’s CSV export bug

December 6, 2010 7 comments
I ran into this at work a few weeks ago and thought I’d share.

Excel 2008’s CSV export feature is broken.  For instance, enter the following fake data into Excel:

Row Name Age
0 Nick 23
1 Bill 48
Save as -> CSV file

Full list of choices

When you use standard unix commands to view the output, the results are all garbled.

[Documents]$ cat Workbook1.csv
1,Bill,48[Documents]$
$ wc -l Workbook1.csv
0 Workbook1.csv
What is the issue?  The file command reveals the problem:
$ file Workbook1.csv
Workbook1.csv: ASCII text, with CR line terminators
CR stands for Carriage return, the ‘\r’ control sequence which, along with the newline character (‘\n’), is used to break up lines on Windows.  Unix OSes like Mac OS expect a single ‘\n’ new line character to terminate lines.
How can we fix this?

dos2unix.

# convert the Workbook1.csv file into a Unix appropriate file
dos2unix Workbook1.csv WithUnixLineEndings.csv
If you don’t have dos2unix on your Mac, and you don’t want to install it, you can fake it with the tr command:
tr '\15' '\n' < Workbook1.csv # remove the carriage returns, replace with a newline
Row,Name,Age
0,Nick,23
1,Bill,48
Very annoying that the Mac Excel doesn’t respect Unix line terminators.  Interestingly, I found a post that talks about ensuring that you choose a CSV file encoded for Mac, but that option seems missing from the Mac version itself.
If I’m missing something obvious, please correct me.