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/

  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
(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:

  1. LOOK AND SAY
  2. TWO A ONE D ONE K ONE L ONE N TWO O ONE S ONE Y
  3. ONE A ONE D SIX E ONE K ONE L SEVEN N NINE O ONE S TWO T TWO W ONE
    Y
  4. 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?

Ruby Q. wrote:

  1. LOOK AND SAY
  2. TWO A ONE D ONE K ONE L ONE N TWO O ONE S ONE Y
  3. ONE A ONE D SIX E ONE K ONE L SEVEN N NINE O ONE S TWO T TWO W ONE Y
  4. 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?

In case the string gets quite long, what is the canonical English
representation (for this quiz) of:
101 - “One hundred one” or “One hundred and one”? (Not “One Oh One”, I
suppose.)

(From that answer I suppose I can extrapolate the answer for similar
edge cases, largely involving the presence of absence of the word
‘and’.)

On 9/6/07, Phrogz [email protected] wrote:

In case the string gets quite long, what is the canonical English
representation (for this quiz) of:
101 - “One hundred one” or “One hundred and one”? (Not “One Oh One”, I
suppose.)

(From that answer I suppose I can extrapolate the answer for similar
edge cases, largely involving the presence of absence of the word
‘and’.)

I was taught in the US that “and” in a spelled out number designates
the decimal point. So, “ONE HUNDRED ONE” would be 101, while “ONE
HUNDRED AND ONE TENTH” would be 100.1 - “ONE HUNDRED AND ONE” would
then be considered an incorrect designation. I think this is based on
check-writing/banking standards.

But I have heard that others learned by other standards both in the US
and elsewhere.

-A

On 9/7/07, Phrogz [email protected] wrote:

In case the string gets quite long, what is the canonical English
representation (for this quiz) of:
101 - “One hundred one” or “One hundred and one”? (Not “One Oh One”, I
suppose.)

I’d say “ONE HUNDRED AND ONE”, but you could always add it as a
parameter

martin

On Sep 6, 1:35 pm, Phrogz [email protected] wrote:

In case the string gets quite long, what is the canonical English
representation (for this quiz) of:
101 - “One hundred one” or “One hundred and one”? (Not “One Oh One”, I
suppose.)

I’ve always felt that the answer to the question “What is the smallest
positive integer spelled with the letter ‘a’?” is 1,000.

Chris

On Sep 6, 2007, at 2:40 PM, Phrogz wrote:

the letters
edge cases, largely involving the presence of absence of the word
‘and’.)

This has come up in past quizzes. Here’s a line of thought from and
oldy but goody:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/135449

James Edward G. II

On Sep 8, 2007, at 12:55 PM, Mark T. wrote:

This has come up in past quizzes. Here’s a line of thought from and
oldy but goody:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/135449

James Edward G. II

Hehe… I used that for Integer#to_english. That made solving this
Ruby Q. fairly easy. Can I post my solution now?

Sure can.

James Edward G. II

This has come up in past quizzes. Here’s a line of thought from and
oldy but goody:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/135449

James Edward G. II

Hehe… I used that for Integer#to_english. That made solving this
Ruby Q. fairly easy. Can I post my solution now?

by Martin DeMello

I decided not to miss all the fun, and implemented my own spelling not
lookong in prior quuiz solutions. BTW, the full-fledged spelling is not
necessary, as the biggest number to spell for this quiz I found was 37
(bigger input texts will require more), but - fun is fun. Interesting
facts
(hope I did not make any typos, they would screw up all statistics):
Worst (or one of) word in unix dictionary is ‘SYMPATHIZED’ - 303 hops
before
entering loop of 885 iterations;
Best - surprise! - ‘ERROR’ - only 7+5

################## spelling part ##########################
TOTEENS=[nil, ‘one two three four five six seven eight nine ten eleven
twelve thirteen fourteen fifteen sixteen seventeen eighteen
nineteen’.split].flatten
TENS=[nil, nil, ‘twenty thirty forty fifty sixty seventy eighty
ninety’.split].flatten
EXPS_US=[nil,‘thousand million billion trillion quadrillion quintillion
sextillion septillion octillion nonillion decillion undecillion
duodecillion
tredecillion quattuordecillion quindecillion sexdecillion
septendecillion
octodecillion novemdecillion vigintillion’.split].flatten
EXPS_NON_US=[nil,‘million billion trillion quadrillion quintillion
sextillion septillion octillion nonillion decillion’.split].flatten

class Integer
def spell(us=true)
return ‘zero’ if self==0
self<0 ? 'minus '+(-self).spell_unsign(us) : self.spell_unsign(us)
end

def spell_unsign(us=true)
size=us ? 3 : 6
res=[]
self.to_s.reverse.scan(%r"\d{1,#{size}}").each_with_index {|s, i|
n=s.reverse.to_i
if n>0
sp=us ? n.spell_small : n.spell(true)
sp.gsub!(‘thousand’,‘milliard’) if i==1 && !us
sc=us ? EXPS_US[i] : EXPS_NON_US[i]
res << sc if sc
res << sp
end
}
res.compact.reverse.join(’ ')
end

def spell_small
res=[]
hundred=TOTEENS[self/100]
res << hundred << ‘hundred’ if hundred
res << TENS[self%100/10] << (self<20 ? TOTEENS[self%100] :
TOTEENS[self%10])
res.compact.join(’ ‘)
end
end
################## actial quiz part ##########################
def count_and_say str
h=str.split(//).inject(Hash.new(0)){|h,c|h[c]+=1; h}
h.delete(’ ‘)
res=’’
h.keys.sort.each {|k|
res << ’ ’ unless res.empty?
res << h[k].spell << ’ ’ << k
}
res
end

it=start=0
hres={(orig=last=ARGV[0].downcase.delete("^a-z"))=>it}
while true
puts now=count_and_say(last)
it+=1
key=now.delete(’ ') # slight optimization, gives ~10% on ‘sympathized’
break if start=hres[key]
hres[key],last=it,key
end
puts “#{start} + #{it-start}”

For fun, I thought I’d see what it looked like to implement the
integer-based algorithm that this quiz is based on. Here’s what I came
up with. (I’m a big fan of monkeypatching. :slight_smile:

class Integer
def each_digit
to_s.each_byte{ |b| yield( b - ?0 ) }
end
def look_and_say
digits, counts = [], []
each_digit{ |d|
if digits.last == d
counts[ counts.size - 1 ] += 1
else
digits << d
counts << 1
end
}
counts.zip( digits ).join.to_i
end
end

n = 1
12.times{ p n; n = n.look_and_say }
#=> 1
#=> 11
#=> 21
#=> 1211
#=> 111221
#=> 312211
#=> 13112221
#=> 1113213211
#=> 31131211131221
#=> 13211311123113112211
#=> 11131221133112132113212221
#=> 3113112221232112111312211312113211

Solution to Ruby Q. #138 by Gavin K.

SEED = “LOOK AND SAY”

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
Ones = %w[ zero one two three four five six seven eight nine ]
Teen = %w[ ten eleven twelve thirteen fourteen fifteen sixteen
seventeen eighteen nineteen ]
Tens = %w[ zero ten twenty thirty forty fifty sixty seventy eighty
ninety ]
Mega = %w[ none thousand million billion trillion quadrillion
quintillion sextillion septillion octillion ]
def to_english
places = to_s.split(//).collect {|s| s.to_i}.reverse
name = []
((places.length + 2) / 3).times do |p|
strings = Integer.trio(places[p * 3, 3])
name.push(Mega[p]) if strings.length > 0 and p > 0
name += strings
end
name.push(Ones[0]) unless name.length > 0
name.reverse.join(" ")
end
private
def Integer.trio(places)
strings = []
if places[1] == 1
strings.push(Teen[places[0]])
elsif places[1] and places[1] > 0
strings.push(places[0] == 0 ? Tens[places[1]] :
“#{Tens[places[1]]}-#{Ones[places[0]]}”)
elsif places[0] > 0
strings.push(Ones[places[0]])
end
if places[2] and places[2] > 0
strings.push(“hundred”, Ones[places[2]])
end
strings
end
end

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
}

On Sep 9, 12:11 pm, “Eugene K.” [email protected] wrote:

Interesting facts
(hope I did not make any typos, they would screw up all statistics):
Worst (or one of) word in unix dictionary is ‘SYMPATHIZED’ - 303 hops before
entering loop of 885 iterations;
Best - surprise! - ‘ERROR’ - only 7+5

Hey, thanks for providing this! I was wondering about that best case,
and tried random words seeing how they played out, but didn’t think to
run the full dictionary against it. :slight_smile:

Krishna D.'s solution to Ruby Q. 138.

I followed Glenn Parker’s reasoning on naming numbers, but didn’t

look at his code.

class CountSay

def initialize(str)
@str = str
end

def succ
letters = @str.scan(/\w/)
@str = letters.uniq.sort.map do |l|
[letters.select{ |e| e == l }.size.to_words, l]
end.join(" ").upcase
end

def each(limit = nil)
if limit.nil?
while true
yield succ
end
else
limit.times { yield succ }
end
end

end

class Integer
NUMS_0_19 = %w(zero one two three four five six seven eight nine ten
eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen
nineteen)
NUMS_TENS = [nil, nil] + %w(twenty thirty forty fifty sixty seventy
eighty ninety)
NUMS_TRIPLETS = [nil] + %w(thousand million billion trillion)

Return the english words representing the number,

so long as it is smaller than 10**15.

The specifications for this method follow the reasoning in:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/135449

though I wrote the code without seeing Glenn’s.

def to_words
case self
when 0…19
NUMS_0_19[self]
when 20…99
a, b = self.divmod(10)
[NUMS_TENS[a], NUMS_0_19[b]].reject { |w| w == “zero” }.join("-")
when 100…999
a, b = self.divmod(100)
“#{NUMS_0_19[a]} hundred#{b == 0 ? ‘’ : ’ ’ + b.to_words}”
else
raise "Too lazy to write numbers >= 1015" if self >= 1015
triplet = (self.to_s.size - 1) / 3 # find out if we are in
thousands, millions, etc
a, b = self.divmod(10**(3 * triplet))
“#{a.to_words} #{NUMS_TRIPLETS[triplet]}#{b == 0 ? ‘’ : ’ ’ +
b.to_words}”
end
end

end

class SimpleCycleDetector

Expects an object that responds to #each.

Returns an array containing the number of

iterations before the cycle started, the length

of the cycle, and the repeated element.

def self.detect(obj)
results = []
obj.each do |e|
if i = results.index(e)
return [i, results.size - i, e]
else
results << e
end
end
end

end

unless ARGV[0] == “-test”

seed = if ARGV.empty?
“LOOK AND SAY”
else
ARGV.join(’ ').upcase
end

puts “Seeding CountSay with ‘#{seed}’”
cs = CountSay.new(seed)
initial, period, phrase = SimpleCycleDetector.detect(cs)
puts “Repeated phrase ‘#{phrase}.’ Started cycle of length #{period}
after #{initial} iterations.”

else
require “test/unit”

class TestToWords < Test::Unit::TestCase

def test_to_words_0_19
  assert_equal("zero", 0.to_words)
  assert_equal("nine", 9.to_words)
  assert_equal("eleven", 11.to_words)
  assert_equal("nineteen", 19.to_words)
end

def test_to_words_20_99
  assert_equal("twenty", 20.to_words)
  assert_equal("twenty-one", 21.to_words)
  assert_equal("forty-two", 42.to_words)
  assert_equal("seventy-seven", 77.to_words)
  assert_equal("ninety-nine", 99.to_words)
end

def test_to_words_100_999
  assert_equal("one hundred", 100.to_words)
  assert_equal("nine hundred three", 903.to_words)
  assert_equal("two hundred fifty-six", 256.to_words)
end

def test_to_words_999_and_up
  assert_equal("one thousand", 1000.to_words)
  assert_equal("one thousand one hundred one", 1101.to_words)
  assert_equal("twenty-two thousand", 22_000.to_words)
  assert_equal("one million", (10**6).to_words)
  assert_equal("twenty-two million nine hundred thousand four

hundred fifty-six", 22_900_456.to_words)
assert_equal(“nine hundred ninety-nine trillion twenty-two
million four thousand one”, 999_000_022_004_001.to_words)
assert_equal(“nine hundred ninety-nine trillion nine hundred
ninety-nine billion nine hundred ninety-nine million nine hundred
ninety-nine thousand nine hundred ninety-nine”,
999_999_999_999_999.to_words)
end

def test_error_on_big_number
  assert_raise(RuntimeError) { (10**15).to_words }
  assert_nothing_raised(RuntimeError) { ((10**15) - 1).to_words }
end

end

class TestSimpleCyleDetector < Test::Unit::TestCase
def setup
@nums = [1,2,3,1,2,3]
@letters = %w( x y a b c d a e f )
end

def test_detect
  assert_equal([0, 3, 1], SimpleCycleDetector.detect(@nums))
  assert_equal([2, 4, 'a'], SimpleCycleDetector.detect(@letters))
end

end

class TestCountSay < Test::Unit::TestCase

def setup
  @output = <<END_OUTPUT
  1. LOOK AND SAY

  2. TWO A ONE D ONE K ONE L ONE N TWO O ONE S ONE Y

  3. ONE A ONE D SIX E ONE K ONE L SEVEN N NINE O ONE S TWO T TWO W ONE Y

  4. 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
    END_OUTPUT

    @lines = @output.to_a.map { |l| l[3…-2] } # without leading
    number or newline
    @cs = CountSay.new(@lines.first)
    end

    def test_succ
    @lines[1…-1].each do |line|
    assert_equal(line, @cs.succ)
    end
    end

    def test_each_with_limit
    @lines.shift
    @cs.each(3) do |str|
    assert_equal(@lines.shift, str)
    end
    end

end
end

On Sep 9, 2007, at 1:15 PM, Eugene K. wrote:

TOTEENS=[nil, ‘one two three four five six seven eight nine ten eleven
twelve thirteen fourteen fifteen sixteen seventeen eighteen
nineteen’.split].flatten

A small suggestion:

%w{one two three …}
=> [“one”, “two”, “three”, “…”]

James Edward G. II

Phrogz wrote:

For fun, I thought I’d see what it looked like to implement the
integer-based algorithm that this quiz is based on. Here’s what I came
up with. (I’m a big fan of monkeypatching. :slight_smile:

Another monkeypatchingversion (i like reopening classes,
i’m not realy a fan of the term ‘monkeypatching’)


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}

cheers

Simon

On Sep 10, 6:23 am, Simon Kröger [email protected] wrote:

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

Dude, that’s elegant. Thanks for sharing. I particularly like keeping
it as a String, avoiding the performance issues of Bignum for the
truly large.

Your solution scales much, much better than mine after a few
iterations:

                user     system      total        real

Simon up to 30 0.203000 0.000000 0.203000 ( 0.219000)
Gavin up to 30 0.500000 0.000000 0.500000 ( 0.531000)

Simon up to 32 0.390000 0.000000 0.390000 ( 0.407000)
Gavin up to 32 0.672000 0.000000 0.672000 ( 0.672000)

Simon up to 34 0.485000 0.000000 0.485000 ( 0.484000)
Gavin up to 34 1.578000 0.000000 1.578000 ( 1.579000)

Simon up to 36 0.750000 0.016000 0.766000 ( 0.765000)
Gavin up to 36 4.000000 0.000000 4.000000 ( 4.032000)

Simon up to 38 1.328000 0.000000 1.328000 ( 1.328000)
Gavin up to 38 10.312000 0.094000 10.406000 ( 10.471000)

Simon up to 40 2.500000 0.015000 2.515000 ( 2.531000)
Gavin up to 40 28.016000 0.031000 28.047000 ( 28.270000)

Simon up to 42 4.375000 0.079000 4.454000 ( 4.485000)
Gavin up to 42 80.219000 0.046000 80.265000 ( 81.029000)

On Sep 10, 7:07 am, James Edward G. II [email protected]
wrote:

On Sep 9, 2007, at 1:15 PM, Eugene K. wrote:

TOTEENS=[nil, ‘one two three four five six seven eight nine ten eleven
twelve thirteen fourteen fifteen sixteen seventeen eighteen
nineteen’.split].flatten

A small suggestion:

%w{one two three …}
=> [“one”, “two”, “three”, “…”]

Moreover:
irb(main):001:0> [ nil, *%w| two three | ]
=> [nil, “two”, “three”]

No need to flatten.

On 9/6/07, Ruby Q. [email protected] wrote:

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?

My solution follows. I rolled my own integer to word routine. The
shortest cycle I found starts with letter ‘Y’:
C:\code\quiz>looksay2.rb y
Y

After 50 iterations, repeated pattern 48:
SIXTEEN E SIX F TWO G THREE H FIVE I TWO L NINE N NINE O SIX R FOUR S
FOUR T FIVE U FIVE V TWO W TWO X ONE Y
Loop length = 2

-Adam

—looksay2.rb—

class Integer
GROUPS =%W{ THOUSAND MILLION BILLION TRILLION QUADRILLION
QUINTILLION SEXILLION SEPTILLION OCTILLION NONILLION}.unshift nil
DIGITS = %W{ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE}.unshift nil
TEENS = %W{TEN ELEVEN TWELVE THIRTEEN FOURTEEN FIFTEEN SIXTEEN
SEVENTEEN EIGHTEEN NINETEEN}
TENS = %W{TEN TWENTY THIRTY FOURTY FIFTY SIXTY SEVENTY EIGHTY
NINETY}.unshift nil
def to_w
return @word if @word
p “making word for #{self}” if $DEBUG
digits = to_s.split(’’).reverse.map{|c|c.to_i}
return @word = “DECILLIONS” if digits.size > 33
phrase,group = [],0
until digits.empty?
phrase << GROUPS[group]
d = digits.slice!(0,3)
d[1]||=0
if d[1] == 1
phrase << TEENS[d[0]]
else
phrase << DIGITS[d[0]] << TENS[d[1]]
end
phrase << “HUNDRED” << DIGITS[d[2]] if (d[2] and d[2]!=0)
phrase.pop if (phrase.compact! and phrase[-1] == GROUPS[group])
group+=1
end
@word = phrase.reverse.join ’ ’
end
end

if FILE == $0

phrase = ARGV[0]||“LOOK AND SAY”
print = ARGV[1] == ‘p’
results=[];
h=Hash.new(0)
i=0
str = phrase.upcase
puts str
until (m = results.index str)
print "#{i}: ", str, “\n” if print
results<< str
str.split(’’).each{|c| h[c]+=1}
h.delete(’ ')
str = h.to_a.sort.map{|c,n| [n.to_w,c] }.join " "
h.clear
i+=1
end
puts "\nAfter #{i} iterations, repeated pattern #{m}: "
puts str
puts “Loop length = #{i-m}”
end

On Sep 6, 7:00 am, Ruby Q. [email protected] wrote:

The three rules of Ruby Q.:

Here is my solution. Pretty simple.


#! /usr/bin/ruby

Quiz 138 - Ruben M.

Will find cycles on a deterministic action

(that is, applying one defined action to an object, it will always

produce the same result)

def find_cycles(initial, action, times, output)

collector = []

collector << initial
iteration = initial

1.upto(times) do |i|
print "#{i}: " if output
iteration = action[iteration]
if collector.include? iteration
puts “Found cycle at #{x = collector.index(iteration)} – #{i}”,
iteration,
“cycle length is #{i - x}”
return
end
collector << iteration
puts iteration if output
puts if output
end
puts “No cycles found for “#{initial}” in #{times} iterations”
end

require ‘number_names’

if FILE == $0

require ‘optparse’

options = {}
OptionParser.new do |opts|

opts.banner = "Usage: ruby quiz138 [WORDS]+ [options]"

opts.on("-t", "--times [INTEGER]") {|times| options[:times] =

times.to_i }
opts.on("-o", “–output”) { options[:output] = true }
opts.on_tail("-h", “–help”, “Show this message”) do
puts opts
exit
end

end.parse!

text = ARGV.join(’ ‘)
ALPHABET = [*‘a’…‘z’]
find_cycles( text,
proc do |text|
ALPHABET.inject(’’) do |str, letter|
x = text.count(letter)
str + (x == 0 ? ‘’ : "#{x.name} #{letter} ")
end.strip
end,
options[:times] || 1000, options[:output])
end


I assume Integer#name method is implemented, for brevity of the post.

On Sun, 9 Sep 2007 05:37:02 +0900 Josef ‘Jupp’ Schugt wrote:

Seems as if something got broken 8-|

###############################################################################
a

Looup table for tens with the first two values only being fillers.

  when 100...1000:

end
EOF

SUMMARY

Josef ‘Jupp’ Schugt

Josef ‘Jupp’ Schugt

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs