[SUMMARY] Count and Say (#138)

[Ruby Quiz]

If you'll permit a brief diversion, this solution to the Look and Say problem
from Simon Kröger is worth a look:

class String
def look_and_say
gsub(/(.)\1*/){|s| "#{s.size}#{s[0,1]}"}
end
end

s = '1'
12.times {p s; s = s.look_and_say}

As you can see, the bulk of the work here is done by a single regular
expression. The pattern matches any non-newline character, followed by a run of
zero or more of the exact same character. Replacing those matches with a count
of the matched run followed by that first unique character will generate a
single step in the sequence. Wrap that in an iterator, like the times() call
here, and you have yourself a complete solution.

I thought that was pretty slick and just wanted to make sure we all got a good
look at it. On to the actual quiz problem.

Solving Count and Say is really just two steps:

1. Translating the counts to English words
2. Iterating over the transformations while watching for a repeated pattern

The first step has come up in the Ruby Quiz a couple of times now. See the
English Numerals for the first time this challenge came up.

This occurrence was almost identical to previous showings. Everyone argues
about the correct way to translate the numbers and then steals Glenn Parker's
solution to Ruby Quiz #25. I'll spare you covering that material again and just
recommend you have a look back at that quiz.

Ironically, that turns out to be the harder part of this quiz, with step two
being pretty easy to whip up.

Let's examine are the relevant pieces of Gavin Kistner's code. First, we have
some extensions to the core classes:

# ...

module Enumerable
def item_counts
inject( Hash.new(0) ){ |counts, item|
counts[ item ] += 1
counts
}
end
end

class String
def look_and_say
counts = upcase.scan( /[A-Z]/ ).item_counts
counts.keys.sort.map{ |letter|
"#{counts[letter].to_english.upcase} #{letter}"
}.join( ' ' )
end
end

# Code courtesy of Glenn Parker in Ruby Quiz #25
class Integer
# ...

def to_english
# ...
end

# ...
end

# ...

The extension to Enumerable is a simple counter of items. It creates and
returns a Hash where the keys are unique items within the Enumerable object and
the values are the counts for how many times that item occurs.

The method added to String handles steps in the Count and Say sequence just as
we saw Simon do earlier for Look and Say. In this version, scan() is used to
locate the letters which are transformed into the count Hash we just examined.
The code then walks the letters in sort()ed order adding the count and letter to
the result. The count is converted to an English word before it lands in the
String using Glen's code.

The rest of the problem is just locating the repeating sequence:

SEED = "LOOK AND SAY"

# ...

str = SEED
strs_seen = {}
0.upto( 9999 ){ |i|
puts "%4d. %s" % [ i, str ]
if last_seen_on = strs_seen[ str ]
print "Cycle from #{i-1} back to #{last_seen_on}"
puts " (#{i - last_seen_on} lines in cycle)"
break
else
strs_seen[ str ] = i
end
str = str.look_and_say
}

This code runs in a loop with a counter for two reasons. First, we may need to
protect ourselves from too much looping, in case the pattern never repeats or
doesn't start repeating for a very long time. The other reason is that it
allows us to track where the repetition begins and how long each cycle is.

The if statement is what actually detects the duplicate. On all iterations,
save the last one, the else branch just adds the current phrase to a seen Hash.
This has phrases for the key and the iteration count where they appeared as the
value. When a duplicate comes up, the if branch will run, printing the
collected statistics and ending the iteration.

It's really just that simple.

My thanks to all who answered this random question form the wild. It's funny
that those can be so much fun.

Tomorrow we will tackle a simple problem, but flex our programmer muscles by
trying to solve it as efficiently as possible...