[QUIZ] Count and Say (#138)

ruby-talk
1

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 Quiz #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 Quiz #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 Quiz <james@grayproductions.net>
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Sent: Thursday, September 6, 2007 7:00:20 AM
Subject: [QUIZ] Count and Say (#138)

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk 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:

    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?

____________________________________________________________________________________
Sick sense of humor? Visit Yahoo! TV's
Comedy with an Edge to see what's on, when.
http://tv.yahoo.com/collections/222

2

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/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

3

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

···

On 9/8/07, Brad Ediger <brad@bradediger.com> wrote:

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/
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

--
Random useless thoughts:
http://www.johnbaylor.org/