From: "Eric I." <rubytraining@...>
Date: 2007-11-19T10:40:01+09:00
Subject: Re: Goedel (#147)

I wanted to make an effort at runtime efficiency.  This is
particularly important when trying to decode the message.  For
example, if the value encoded with the current prime (p) is "d", then
the factor is p**101.  The slow way would be to divide the current
Goedel value by p 102 times (101 times, and then the 102nd fails).
But you could also try dividing it by p**64, p**32, p**16, p**8, p**4,
p**2, and p**1.  You would find that it does divide by p**64, p**32,
p**4, and p**1 without a remainder, and 64 + 32 + 4 + 1 == 101.

So as long as all the encoded values are less than 128 (which handles
all printable ascii values), you would have to divide the current
Goedel value only 7 times for each character decoded.  Since I imagine
most characters would be lower-case letters, they would require on the
order of 100+ divisions using the slower method.

For an additional efficiency note that prime**2 is prime squared.  And
prime**4 is prime**2 squared.  And so forth.  So we can generate all
the factors we want to try by successive squaring, which is probably
more efficient than calculating prime**64 separately from prime**32.
The problem is we have to first divide by prime**64, so we can
generate and store all the factors in an array, and try dividing from
the largest down to the smallest.

Eric

====

require 'mathn'  # for Prime class


# Put the coder in a separate class, so we have the potential to use
# other coders, such as the one from the Starburst novel.
class RubyQuizCoder
  def encode(char)
    char[0] + 1
  end

  def decode(number)
    (number - 1).chr
  end

  def max_code
    127
  end
end


def encode(input, primes, coder)
  goedel_value = 1

  input.each_line do |line|
    0.upto(line.size - 1) do |i|
      char = line[i, 1]
      encoding = coder.encode char
      next if encoding.nil?  # skip characters without encoding
      goedel_value *= primes.next ** encoding
    end
  end

  puts goedel_value
end


# Attempt to decode quickly by trying to perfectly divide by
# prime**(2**6), prime**(2**5), prime**(2**4), ..., prime**(2**0) and
# then adding the powers of 2 for which the division worked without a
# remainder.  For example, if a number were divisible by prime**101,
# then it's also divisible by prime**64 * prime**32 * prime**4 *
# prime**1 since 64 + 32 + 4 + 1 = 101.  So, we'll have to divide the
# large number exactly 7 times per prime no matter what the exponent.
# Note: 7 assumes that the encoding results in no value greater than
# 127.
def decode(input, primes, coder)
  goedel_value = input.gets.to_i
  max_two_expnt = (Math.log(coder.max_code) / Math.log(2)).to_i
  factors = (0..max_two_expnt).map { |i| [2**i, nil] }

  while goedel_value > 1
    current_prime = primes.next
    encoded = 0

    factors[0][1] = current_prime
    (1..max_two_expnt).each do |i|
      factors[i][1] = factors[i - 1][1] ** 2
    end

    factors.reverse_each do |expnt, factor|
      quotient, remainder = goedel_value.divmod(factor)
      if remainder == 0
        encoded += expnt
        goedel_value = quotient
      end
    end

    char = coder.decode(encoded)
    putc char unless char.nil?
  end
end


def usage
  STDERR.puts "Usage: %s -e[ncode]|-d[ecode] [file]" % $0
  exit 1
end


# process command-line args and figure out which method to call

task = nil
input = nil
ARGV.each do |arg|
  case arg
  when /^-+e/   : task = :encode
  when /^-+d/   : task = :decode
  else if input : usage
       else       input = open(arg)
       end
  end
end

input = STDIN if input.nil?
primes = Prime.new
coder = RubyQuizCoder.new

case task
when :encode : encode(input, primes, coder)
when :decode : decode(input, primes, coder)
else           usage
end