This quiz is really just an optimization problem. It’s pretty trivial

to do a

conversion to and from a Goedel number. See Eric L.'s

under-30-lines

solution for a great example of this. The challenge arises when the

message

gets big enough that finding all of the factors takes significant time.

Eric I. figured out how to cut quite a few corners on the decoding

process, so I

want to take a look at his code.

Before we get into the actual encoding and decoding process though,

let’s talk a

bit about primes. Obviously, we need a source of prime numbers to do

our work.

Ruby does ship with a standard mathn library that includes a Prime

class. Many

solutions did put that library to good use. There are two downsides to

that

approach though: mathn is a pure Ruby library and the Prime class

implementation in Ruby 1.8 is not very clever. Both of these slow us

down.

To get around that, Eric built a drop-in replacement for the Prime class

that

cheats. It simply reads the numbers from a huge list you can download,

skipping

any calculation effort. This turns out to be faster for our needs.

Here’s the

code:

# Generates a stream of prime numbers as they’re read from a sequence

# of files with names such as “primes1.txt”, “primes2.txt”, and so

# forth. Such files can be downloaded from:

# The first fifty million primes

class Prime

def initialize

@current_file = 0

@io = open_next_file

@current_primes = []

@current_index = 0

end

```
def next
load_next_primes until value = @current_primes[@current_index]
@current_index += 1
value
end
private
def load_next_primes
while true
while line = @io.gets
if line =~ /^\s*\d+(\s+\d+)*\s*$/
@current_primes = line.split.map { |e| e.to_i }
@current_index = 0
return
end
end
@io.close
open_next_file
end
end
def open_next_file
@current_file += 1
filename = "primes%d.txt" % @current_file
begin
@io = open(filename)
rescue
raise "ran out of primes because couldn't open file \"%s\"" %
filename
end
end
```

end

As you can see, this is simple stuff. The class just opens a file

called

primes1.txt when initialize()d (see open_next_file()). As needed, lines

are

read from this file, split() and converted into Integers, and tucked

away inside

an Array (see load_next_primes()). Primes are then just handed out from

this

Array (see next()) and when the supply is exhausted new lines are read.

When we

run out of lines, the code will move on to a primes2.txt file.

The site linked to in the comment has the first 15 million primes

available in

files like this. That more than covers the needs of this code, so this

turns

out to be a simple but effective cheat to save time.

With a zippy Prime class defined, we are ready to get down to the real

work:

require ‘primes’ # or the standard mathn library

# 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

# …

Here we see the require for the code that we just examined. Note that

this code

will work fine with a mathn require as well though.

The class defined here is the simple encoding described in the quiz. As

the

comment indicates, pulling this code into the class makes it easy to

swap out

with other encoding schemes.

The work horse methods for the solution are encode() and decode(), of

course.

Here’s the easy one:

# …

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

# …

The code works its way line by line and character by character through

the

input. Each character is encoded using the RubyQuizCoder class we saw

earlier,

used as an exponent for a prime based on its position, and finally

multiplied

into the overall Goedel value. When all of the characters have been

dealt with,

the overall value is printed as a result.

The reverse operation is harder to digest, because it’s where the

optimizations

are hiding:

# …

# 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

# …

The biggest trick in here is the use of factorization to narrow down the

divisions needed. Until the overall value hits one, each prime is

pulled in

turn and factored into the possible divisors. Each of those numbers is

then

tried in reverse order. Those that divide evenly are added to the

encoded

character count and drop the overall count accordingly. After all of

the

factors have been tried, the character count is passed through our

RubyQuizCoder

object and the resulting character is printed.

This strategy results in a constant number of divisions for each

character and

in most cases, those divisions should be significantly less than the

brute force

approach.

The rest of the code just provides an interface to these routines:

# …

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

This is just some basic argument parsing code. It hunts for a -e or -d

switch

to figure out if we are encoding or decoding. It also opens a file of

input for

the first non-switch argument or defaults to STDIN. Failing to select a

mode or

providing multiple input parameters triggers the usage message and an

exit()

call. Otherwise, the selected routine is called with the input, a prime

generator, and the coder.

356592611993533159357704171943707065506245018107843654420869995255779400

940327637098004636805658940369248254005741705095861927174094085632357462

907907043655503052325570584135928519171701028451925211424184061134912519

346213124822184698766352106671144335797309339814960788404357329829880747

370816749488671200451708065007982023372864606432786154466561150882383337

665739304198857199016703678239557259404453555953430721034149637848167371

696741427087919115033228735590823604859393603457456530272005167282069777

767057670186595718538513692305202904620672162211361327059254731120977063

134449493970743739621694338383775782689258152219852727482221819916188854

728922544056620806588370831318213885828889837200379775053853865140225412

662845287202726609004691108889366849057859320331241672049374448503639685

391414041859040062271216363732269502663137649053220830210776147948360695

030849925289805667675539825659032822205396840604174306471211962857755270

446984071785349996985198175348758225276208258987173267939423506126205306

366658339817220773597781191289736402029252868902666231417359731588146165

666320778680777303480755853750057521054497117887073508511901428397946093

449376833443738252027373639560059173037124844900113551258953525303486104

043722150604562552368672756555770801627883622940792114968157184742775843

032899157541783062241525730231786371568328435169052449375068965888786768

418148739617709373626622156165087821359521473101982925802046545744126160

160591686651704019368238740807898239650093187094408149981270808624486401

576666800438277327766454315294642692798530476745070050857038213692995319

240862517113963583832414299967798488646237585020392202957001143544708578

006399968115609032521439107622793677586436726234995703756213467526362754

053665223526567818472971465689078159087061330179433352620768373562074252

272173230499663950656487104976363578669988246793426315517241324669161225

95456614469899787029059315850805248000000000000000000000000000000000

Tomorrow we will …