Ruby implementation of the "look and say sequence" (after John H. Conway and Bob Morris)

look_and_say_sequence.rb

#########################################################################
# A simple Ruby implementation of the Look-and-Say sequence (also known
# as the Conway sequence or the Morris puzzle).
#
# In the Look-and-say Sequence, each term describes the previous term.
# So, the first term is "1". This term consists of 1 of the digit '1',
# so the next term is "11". This term consists of 2 of the digit '1',
# so the next term is "21". This term consists of a single 2, followed
# by a single "1", and so the next term is "1211". The next term would
# be "111221", and so forth.
#
# For more information, see:
#   <http://en.wikipedia.org/wiki/Look-and-say_sequence>
#
# Usage:
#    ruby look_and_say_sequence.rb [term number] [initial value]
#
# The term number defaults to 1, and the initial value defaults to "1",
# which matches the traditional expression of the sequence. If, for
# example, you supply "5" as the initial value, the sequence will
# proceed as "15", "1115", etc.
#
# Performance Note:
# -----------------
#
# term_at and next_term both slow down dramatically for terms greater
# than about 45 into the sequence, owing to the recursive nature of the
# algorithm.
#
# On my system (MacBook Pro 2x2.7GHz, 8GB RAM), execution times are
# approximately as follows:
#
#  n    calculation time (secs)       # of digits in term
# ---   -----------------------       --------------------
#   5          0.0003                           6
#  10          0.0003                          20
#  20          0.0085                         302
#  30          0.0565                       4,462
#  40          2.0943                      63,138
#  50         27.9635                     894,810
#  60        178.6764                  12,680,852
#########################################################################
# Tammy Cravit <[email protected]> 01-04-2012
#########################################################################
# If you want to run this as is, you'll need to install the
# tcravit_ruby_lib gem, or else remove the include and define
# Kernel.on_execute as in https://gist.github.com/1565768
#########################################################################

#========================================================================
# A bit of hackery for running this from the command line or including
# it into another program.
#========================================================================

require 'tcravit_ruby_lib/on_execute'

#========================================================================
# THe actual implementation
#========================================================================

class MorrisPuzzle

  def initialize(the_start_string="")
    @the_string = the_start_string
    @start_string = the_start_string
    @count = 1
  end

  def term_at(an_index, display_visual_feedback=false)
    r = ""
    saving_old_value do
      1.upto(an_index.to_i) do |c|
        @count = c
        r = next_term(display_visual_feedback)
      end
    end
    r
  end

  def next_term(display_visual_feedback=false)
    current_char = ''
    current_count = 0
    result_string = ''

    # A bit of a kludge to provide visual feedback on the progress
    if (@count % 5 == 0) && display_visual_feedback
      print "<#{@count}>..."
    end

    if @the_string.length == 0
      result_string = "1"
    else
      0.upto(@the_string.length) do |index|
        if (index == 0)
          current_char = @the_string[0]
          current_count = 1
        else
          if @the_string[index] == current_char
            current_count += 1
            if index == @the_string.length
              result_string << "#{current_count}#{current_char}"
            end
          else
            result_string << "#{current_count}#{current_char}"
            current_char = @the_string[index]
            current_count = 1
          end
        end
      end
    end
    @the_string = result_string
  end

  protected


  def saving_old_value(&block)
    old_val = @the_string
    @the_string = @start_string
    result = yield if block_given?
    @the_string = old_val
    result
  end
end

#========================================================================
# When run from the command line, return the n'th argument of the sequence.
#========================================================================

on_execute do
  term_no = (ARGV.length > 0 ? ARGV[0] : 1)
  starting_at = (ARGV.length > 1 ? ARGV[1] : "1")

  print "----------------------------------------------------\n"
  print "Morris Puzzle: Term #{term_no}, Initial #{starting_at}\n"
  print "----------------------------------------------------\n\n"
  print "Calculating: "
  start_time = Time.now
  r = MorrisPuzzle.new(starting_at).term_at(term_no, true)
  end_time = Time.now
  print "done.\nThe answer is: #{r}\n"
  print "Calculated in #{(end_time - start_time).round(4)} seconds.\n"
  print "The result is #{r.to_s.length} digits in length.\n"
end