Duncan Davidson

The case of aaaabbbcca

Implicit in a recent pointer to a code puzzle was the fact that a test-driven approach would be perfect. So, I dove in.

Allen Holub retweeted a code puzzle that Alexey Grigorev posted which Alexey claimed that most candidates couldn’t solve within a 25-minute screening interview:

Input: 'aaaabbbcca'
Output: [('a', 4), ('b', 3), ('c', 2), ('a', 1)]

My first thought was that this should be easy: a quick matter of counting up the number of times each letter occurred in the string. Then, I saw that final a character and realized that something a little more sophisticated was needed. It took me about 10 minutes (yes, I timed myself) to hack out the following solution in Ruby using IRB:

'aaaabbbcca'.chars.reduce([]) do |a, c|
  if b = a.last and b[0] == c
    b[1] = b[1] + 1
  else
    a << [c, 1]
  end
  a
end

This produced the following output, which is close enough even though it’s in Ruby’s array of array output format:

[['a', 4], ['b', 3], ['c', 2], ['a', 1]]

Of course, those one-letter variable names are only good for a few minutes. They really need to be cleaned up into something more readable. Here we go:

'aaaabbbcca'.chars.reduce([]) do |accum, char|
  if last = accum.last and last[0] == char
    last[1] = last[1] + 1
  else
    accum << [char, 1]
  end
  accum
end

Based on my recent interview experience, I’m really not sure I could have been able to do it within Alexey’s 25 minute screening. Indeed, I’d have to be in a reasonable frame of mind to have a shot and not totally flub it up due to performance paralysis.

Other solutions

A few other solutions stood out in the threads of these discussions. One I quite like is Sam Ruby’s one-liner using scan and a regexp:

'aaaabbbcca'.scan(/((.)\2*)/).map(&:first)

which returns:

["aaaa", "bbb", "cc", "a"]

To return the same format as mine, you can use the following as the map function:

.map { |item| [item[1], item[0].size] }

Vítězslav Ackermann Ferko used the same approach in JavaScript:

'aaaabbbcca'.match(/((.)\2*)/g).map((v) => [v[0], v.length])

I think my absolute favorite, however, is this solution by Raymond Hettinger:

$ echo 'aaaabbbcca' | fold -w 1 | uniq -c
 4 a
 3 b
 2 c
 1 a

This one wins the prize!

Let’s be test-driven, ok?

Implicit (to me at least) in Allen’s pointer to the problem is that this is the kind of thing that would be great for a test-driven approach. So, instead of hacking it out in IRB, I could have written a test first:

def test_simple
  expected = [['a', 4], ['b', 3], ['c', 2], ['a', 1]]
  assert_equal expected, solve('aaaabbbcca')
end

You might think that setting up a test-driven approach is overkill for a code puzzle like this. Certainly, it can be a pain in the arse to set up separate files and a test driver. In Ruby, at least, you can do this in a single file:

#!/usr/bin/env ruby

def solve(input)
  input.chars.reduce([]) do |accum, char|
    if last = accum.last and last[0] == char
      last[1] = last[1] + 1
    else
      accum << [char, 1]
    end
    accum
  end
end

require 'test/unit'

class Tests < Test::Unit::TestCase
  def test_simple
    expected = [['a', 4], ['b', 3], ['c', 2], ['a', 1]]
    assert_equal expected, solve('aaaabbbcca')
  end
end

I started using this all-in-one test-first approach in the last code interview I did recently, and it really worked out nicely. It certainly helped keep my thinking a little bit more structured during the process.

Of course, if we really wanted to take the original instructions literally, we could have used a test-first approach and just returned the string asked for:

#!/usr/bin/env ruby

def solve(input)
  "[('a', 4), ('b', 3), ('c', 2), ('a', 1)]"
end

require 'test/unit'

class Tests < Test::Unit::TestCase
  def test_simple
    expected = "[('a', 4), ('b', 3), ('c', 2), ('a', 1)]"
    assert_equal expected, solve('aaaabbbcca')
  end
end

You’d just need the right je ne sais quoi expression to go along with presenting this solution. Maybe one day, I’d be in a good frame of mind to do that.