From: John Baylor <john.baylor@...>
Date: 2007-09-09T09:01:09+09:00
Subject: Re: [QUIZ] Count and Say (#138)

------=_Part_1873_20978574.1189296067069
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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/

------=_Part_1873_20978574.1189296067069--