# Count and Say (#138)

**URL:** <https://www.ruby-forum.com/t/count-and-say-138/114500>\
**Category:** Ruby\
**Created:** [September 13, 2007, 2:16pm UTC](https://www.ruby-forum.com/t/count-and-say-138/114500 "2007-09-13T14:16:12Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 13, 2007, 2:16pm UTC](https://www.ruby-forum.com/t/count-and-say-138/114500/1 "2007-09-13T14:16:12Z")

</div>

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 Q. 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 Q. #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 K.'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 Q. #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…