# Re: Count and Say (#138)

**URL:** <https://www.ruby-forum.com/t/re-count-and-say-138/114165>\
**Category:** Ruby\
**Created:** [September 8, 2007, 11:52pm UTC](https://www.ruby-forum.com/t/re-count-and-say-138/114165 "2007-09-08T23:52:04Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [September 8, 2007, 11:52pm UTC](https://www.ruby-forum.com/t/re-count-and-say-138/114165/1 "2007-09-08T23:52:04Z")

</div>

This week’s quiz was fairly easy. The hardest part was finding and  
choosing a way to turn the numbers into their English equivalents.  
Initially I used an array that extended to TWENTY, but that was  
insufficient. I had solved Ruby Q. #25 and some of the other old ones  
myself a while ago, but lost it due to a harddrive crash and couldn’t  
find a copy. I then just picked someone else’s solution to Ruby Q. #25  
that added a to\_en method to Integer.

Here’s my solution, minus the Integer#to\_en method. I commented out the  
code to print out the elements of the cycle, as it turns out the cycle  
is about 430 elements long!

def count\_and\_say(str)  
(‘A’…‘Z’).map{|l| (str.count(l) \> 0) ?  
[str.count(l).to\_en.upcase, l] : “”}.join(’ ‘).squeeze(’ ')  
end

order = ARGV[0].chomp.to\_i  
prev\_results = {}  
element = “LOOK AND SAY”  
for n in (0…order)  
if prev\_results[element]  
puts “Cycle of length #{n-prev\_results[element]} starting” +  
" at element #{prev\_results[element]}"  
#puts “Cycle’s elements are:”  
#puts (prev\_results[element]…n).to\_a.map{|n|  
prev\_results.invert[n]}  
break  
else  
prev\_results[element] = n  
end  
element = count\_and\_say(element)  
end

----- Original Message ----  
From: Ruby Q. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
To: ruby-talk ML [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
Sent: Thursday, September 6, 2007 7:00:20 AM  
Subject: [QUIZ] Count and Say (#138)

The three rules of Ruby Q.:

1. Please do not post any solutions or spoiler discussion for this quiz  
until  
48 hours have passed from the time on this message.

2. Support Ruby Q. by submitting ideas as often as you can:

[http://www.rubyquiz.com/](http://www.rubyquiz.com/)

1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps  
everyone  
on Ruby T. follow the discussion. Please reply to the original quiz  
message,  
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Martin DeMello

Conway’s “Look and Say” sequence  
([Look-and-say sequence - Wikipedia](http://en.wikipedia.org/wiki/Look-and-say_sequence)) is a sequence of  
numbers in  
which each term “reads aloud” the digits of the previous term. For  
instance, the  
canonical L&S sequence starts off 1, 11, 21, 1211, 111221, …, because:

```
* 1 is read off as "one 1" or 11.
* 11 is read off as "two 1's" or 21.
* 21 is read off as "one 2, then one 1" or 1211.
* 1211 is read off as "one 1, then one 2, then two 1's" or 111221.
* 111221 is read off as "three 1, then two 2, then one 1" or 312211.

```

Over on rec.puzzles, Eric A. proposed a variant in which the letters of  
a  
sentence are grouped, then “counted aloud”, omitting the "s"s for the  
plural  
form. Thus, seeding the sequence with “LOOK AND SAY”, we get:

```
0. LOOK AND SAY
1. TWO A ONE D ONE K ONE L ONE N TWO O ONE S ONE Y
2. ONE A ONE D SIX E ONE K ONE L SEVEN N NINE O ONE S TWO T TWO W 

```

ONE Y  
3. ONE A ONE D TEN E TWO I ONE K ONE L TEN N NINE O THREE S THREE T  
ONE V  
THREE W ONE X ONE Y

and so on. (Note the difference between this and the L&S sequence–the  
letters  
are counted rather than read in order). Eric wants to know when the  
sequence  
enters a cycle, and how long that cycle is. Well?

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [September 9, 2007, 12:20am UTC](https://www.ruby-forum.com/t/re-count-and-say-138/114165/2 "2007-09-09T00:20:08Z")

</div>

Here’s my solution. Coincidentally, it uses the same  
Integer#to\_english method that JEG2 posted from quiz 25 (not  
included, as integer\_to\_english.rb).

–Usage:  
$ ./138\_count\_and\_say.rb LOOK AND SAY  
Took 179 cycles to enter a cycle of length 429

–

#!/usr/bin/env ruby -rubygems

# integer\_to\_english.rb → [http://blade.nagaokaut.ac.jp/cgi-bin/](http://blade.nagaokaut.ac.jp/cgi-bin/)

scat.rb/ruby/ruby-talk/135449  
%w(facet/string/chars facet/enumerable/injecting facet/symbol/to\_proc  
integer\_to\_english).each(&method(:require))

class String  
def letter\_histogram  
upcase.gsub(/[^A-Z]/,‘’).chars.injecting(Hash.new(0)){|h, l| h  
[l] += 1}  
end

def count\_and\_say  
letter\_histogram.sort\_by{|l,n| l}.map{|(l, n)| “#  
{n.to\_english.upcase} #{l}”}.join(" ")  
end  
end

class Object  
def detect\_cycles  
ary = [self]  
loop do  
val = yield(ary.last)  
if ary.include? val  
return [ary.index(val)+1, ary.length - ary.index(val)]  
end  
ary \<\< val  
end  
end  
end

if **FILE** == $PROGRAM\_NAME  
tail, cycle\_length = ARGV.join.detect\_cycles(&:count\_and\_say)  
puts “Took #{tail} cycles to enter a cycle of length #{cycle\_length}”  
end

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [September 9, 2007, 2:02am UTC](https://www.ruby-forum.com/t/re-count-and-say-138/114165/3 "2007-09-09T02:02:13Z")

</div>

Here is my solution for both the number puzzle and the letter one. I  
didn’t  
realize that the numbers wouldn’t converge until I watched it take a  
looong  
time and followed the wikepedia link. In any case, the code handles  
both  
count\_and\_say and look\_and\_say. As others have said, the Fixnum.say  
method  
was more work than the rest of the puzzle.

# Expect a block that takes a first argument of ‘count’ or ‘reorder’

depending on what

# we need to do with the current string.

# In hindsight, this could have taken two Proc objects instead:

count\_proc  
and reorder\_proc  
def find\_cycle string  
puts “Finding a cycle for #{string}”  
sequence = {}  
until sequence[string]  
sequence[string] = sequence.length  
string.gsub!(/ /,’’) # we ignore all spaces  
#STDOUT.write "#{string.length}:#{string[0…50]} " #progress  
feedback  
string = yield( ‘reorder’, string )  
previous\_char, count = string[0…0], 1  
counts = string.split(’’)[1…-1].inject([]) do |memo,obj|  
if previous\_char == obj  
count += 1  
else  
memo \<\< [yield(‘count’,count),previous\_char]  
previous\_char, count = obj, 1  
end  
memo  
end  
counts \<\< [yield(‘count’,count),string[-1…-1]]  
string = counts.flatten.join(’ ')  
end  
“Cycle found at position #{sequence.length}, duplicating position  
#{sequence[string]}: #{string}”  
end

def count\_and\_say string = “1”  
find\_cycle string do |operation, value|  
# in the numerical mode, each operation is a null operation  
case operation  
when ‘reorder’  
value # no need to re-order the string  
when ‘count’  
value.to\_s # just make sure it is a string  
end  
end  
end

def look\_and\_say string = “LOOK AND SAY”  
find\_cycle string do |operation, value|  
case operation  
when ‘reorder’  
value.split(’’).sort.join  
when ‘count’  
value.to\_i.say  
end  
end  
end

class Fixnum  
NUMBERS = %w[zero one two three four five six seven eight nine ten  
eleven twelve thirteen fourteen fifteen sixteen seventeen  
eighteen  
nineteen twenty]  
TENS = %w[zero ten twenty thirty forty fifty sixty seventy eighty  
ninety]  
BIG\_DIGITS = %w[zero ten hundred thousand]  
def ones\_digit; (self % 10); end  
def tens\_digit; ((self / 10) % 10); end  
def say  
result = []  
if NUMBERS[self % 100]  
result \<\< NUMBERS[self % 100] if self == 0 or (self % 100) != 0  
else  
result \<\< NUMBERS[self.ones\_digit] if self.ones\_digit \> 0  
result \<\< TENS[self.tens\_digit]  
end  
str = self.to\_s  
str[0…-3].reverse.split(’’).each\_with\_index do |char,idx|  
result \<\< BIG\_DIGITS[idx+2]  
result \<\< NUMBERS[char.to\_i] if char.to\_i \> 0  
end  
result.reverse.collect {|i| i.upcase }.join(’ ')  
end  
end

I found this to be a lot of fun - just the right amount of work for a  
lazy  
Saturday.  
=\> “Cycle found at position 607, duplicating position 178: ONE A ONE D  
EIGHTEEN E FIVE F TWO G THREE H EIGHT I ONE K TWO L ELEVEN N TEN O THREE  
R  
TWO S TEN T TWO U FIVE V SIX W TWO X ONE Y”

(I hope this is actually correct!)  
JB