[QUIZ] Goedel (#147)

[Ruby Quiz]

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 Hugh Sasse

In the book "Starburst" by Frederik Pohl ISBN 0-345-27537-3, page 56, without
really spoiling the plot, some characters complain about the verbosity of
communications and encode a message by Gödelizing it (detailed on page 58).

The encoding works by taking each successive character of a message and raising
each successive prime to some function of that character, and multiplying these
powers of primes together. So for example we could use the ASCII code + 1 to
allow for nulls to be encoded. Then "Ruby\r\n" would end up as:

(2 ** R) * (3 ** u) * (5 ** b)....

10992805522291106558517740012022207329045811217010725353610920778
28664749233402453985379760678149866991742205982820039955872246774
86029159248495553882158351479922840433375701904296875000000000000
00000000000000000000000000000000000000000000000000000000000000000
000000

The idea is partly to obscure the message by the amount of factorization needed.
This quiz is to write a program to Gödelize a message, and a program to
deGödelize it.

The funtion used to map characters described in the book is "A" => 1, "B" => 2,
etc and an example is given where spaces are 0. Nothing further is said about
punctuation, or lower case. The message sent in the book is:

msg = (3.875 * (12 ** 26)) +
(1973 ** 854) + (331 ** 852) +
(17 ** 2008) + (3 ** 9707) + (2 ** 88) - 78

which it turns out has lots of 0 powers in it, so I strictly don't need the
ASCII + 1 I've used in my example, I could use just ASCII, and the nulls would
not increase the size of the resulting number. This further means that if a list
of characters is sent in decreasing frequency order with the message, the most
frequent could be encoded as 0 and the number would be that much smaller. In
English it is likely to be an "e" or " " which ends up coded as 0.

Interesting things arising from this:

1 Finding the power once a prime is selected
2 Getting the list of primes in the first place
3 encoding of characters, as mentioned above
4 representing the number that results from encoding.

 

[James Edward Gray II]

by Hugh Sasse

In the book "Starburst" by Frederik Pohl ISBN 0-345-27537-3, page =20
56, without really spoiling the plot, some characters complain =20
about the verbosity of communications and encode a message by =20
G=F6delizing it (detailed on page 58).

This quiz will run for two weeks because of the holiday. The no-=20
spoiler period is still the normal 48 hours.

James Edward Gray II=

 

[Eric I.]

The encoding works by taking each successive character of a message and raising

each successive prime to some function of that character, and multiplying these
powers of primes together. So for example we could use the ASCII code + 1 to
allow for nulls to be encoded. Then "Ruby\r\n" would end up as:

(2 ** R) * (3 ** u) * (5 ** b)....

10992805522291106558517740012022207329045811217010725353610920778
28664749233402453985379760678149866991742205982820039955872246774
86029159248495553882158351479922840433375701904296875000000000000
00000000000000000000000000000000000000000000000000000000000000000
000000

If I'm not mistaken, the number given is the encoding for "Ruby\n".
The encoding for "Ruby\r\n" is:


26221858870290182364639031466277185911546960210395902825153752677

86758380406769132705749108355204343696163662611760821989161975619

72000918860271223092350554891796472401033816989022830694122314453

12500000000000000000000000000000000000000000000000000000000000000
000000000000000000000

Eric

 

[James Edward Gray II]

If I'm not mistaken, the number given is the encoding for "Ruby\n".

Yeah, I think you are right. I've updated the quiz page.

James Edward Gray II

 

[steve]

Here's my submission:

http://pastie.caboo.se/119486

class String
def godelize
prime =3D 0 ; product =3D 1
each_byte do |b|
product *=3D (prime =3D prime.next_prime) ** (b+1)
end

product
end

def self.from_godel(godel_integer)
str =3D ""
$stdout.sync =3D true
godel_integer.to_i.factorize.sort_by{|factor, value|factor}.each do
|factor, value|
str << (value-1).chr
end

str
end
end

class Integer
def next_prime
n =3D self
true while !(n+=3D1).prime?

n
end

def prime?
return false if [0,1].include? self.abs

return false if self > 2 and self%2 =3D=3D 0
(3..self/2).step(2) do |n|
return false if self%n =3D=3D 0
end

true
end

def factorize
factors =3D {} ; prime =3D 0 ; n =3D self

while n >=3D prime
prime =3D prime.next_prime
count =3D count_factor(prime)

if count > 0
factors[prime] =3D count
n /=3D prime**count
end
end

factors
end

def count_factor(f)
return 0 if self % f !=3D 0

cnt =3D 1 ; n =3D self

cnt +=3D 1 while (n/=3Df) % f =3D=3D 0

cnt
end
end


if $0 =3D=3D __FILE__
case ARGV.shift
when /--encode/
puts STDIN.read.godelize.to_s(36)
when /--decode/
puts String.from_godel(STDIN.read.to_i(36))
end
end

run it with: *ruby godelize.rb --encode* or *ruby godelize.rb --decode*
it uses stdin/stdout for input/output

it outputs the number in base 36 as a very simple way to reduce the size a
bit

- steve

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.


-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-= =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D

by Hugh Sasse

In the book "Starburst" by Frederik Pohl ISBN 0-345-27537-3, page 56,
without
really spoiling the plot, some characters complain about the verbosity of
communications and encode a message by G=F6delizing it (detailed on page
58).

The encoding works by taking each successive character of a message and
raising
each successive prime to some function of that character, and multiplying
these
powers of primes together. So for example we could use the ASCII code + 1
to
allow for nulls to be encoded. Then "Ruby\r\n" would end up as:

(2 ** R) * (3 ** u) * (5 ** b)....

10992805522291106558517740012022207329045811217010725353610920778
28664749233402453985379760678149866991742205982820039955872246774
86029159248495553882158351479922840433375701904296875000000000000
00000000000000000000000000000000000000000000000000000000000000000
000000

The idea is partly to obscure the message by the amount of factorization
needed.
This quiz is to write a program to G=F6delize a message, and a program to
deG=F6delize it.

The funtion used to map characters described in the book is "A" =3D> 1, "= B"
=3D> 2,
etc and an example is given where spaces are 0. Nothing further is said
about
punctuation, or lower case. The message sent in the book is:

msg =3D (3.875 * (12 ** 26)) +
(1973 ** 854) + (331 ** 852) +
(17 ** 2008) + (3 ** 9707) + (2 ** 88) - 78

which it turns out has lots of 0 powers in it, so I strictly don't need
the
ASCII + 1 I've used in my example, I could use just ASCII, and the nulls
would
not increase the size of the resulting number. This further means that if
a list
of characters is sent in decreasing frequency order with the message, the
most
frequent could be encoded as 0 and the number would be that much smaller.
In
English it is likely to be an "e" or " " which ends up coded as 0.

Interesting things arising from this:

1 Finding the power once a prime is selected
2 Getting the list of primes in the first place
3 encoding of characters, as mentioned above
4 representing the number that results from encoding.

 

[Eric Lavigne]

My solution follows. I would have liked the Prime class to have a
"this" method that would allow me to get the most recently returned
prime number again, as that would have shaved a line off. My goals
were to keep the Encryption class short and stateless, so please let
me know if you see ways to shorten it further.

# code begins

require 'mathn'

class Encryption
=09def Encryption.encode(msg,primes=3DPrime.new)
=09=09return 1 if msg.size.zero?
=09=09return (primes.succ ** (1 + msg[0])) * encode(msg.slice(1,msg.size),p=
rimes)
=09end
=09def Encryption.decode(num,primes=3DPrime.new)
=09=09return "" unless num > 1
=09=09prime =3D primes.next
=09=09multiplicity =3D factor_multiplicity(prime,num)
=09=09(multiplicity-1).chr + Encryption.decode(num / (prime **
multiplicity), primes)
=09end
=09private
=09def Encryption.factor_multiplicity(factor,num)
=09=091.upto(num) {|x| return x - 1 unless num.modulo(factor**x).zero?}
=09end
end

puts "Test encoding: "+Encryption.encode("Ruby\n").to_s+"\n"
puts "Test decoding: "+Encryption.decode(Encryption.encode("Ruby\n"))+"\n"

# code ends

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 ev= eryone
on Ruby Talk follow the discussion. Please reply to the original quiz me= ssage,
if you can.

-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-= =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D

by Hugh Sasse

In the book "Starburst" by Frederik Pohl ISBN 0-345-27537-3, page 56, wit= hout
really spoiling the plot, some characters complain about the verbosity of
communications and encode a message by G=F6delizing it (detailed on page = 58).

The encoding works by taking each successive character of a message and r= aising
each successive prime to some function of that character, and multiplying= these
powers of primes together. So for example we could use the ASCII code + 1= to
allow for nulls to be encoded. Then "Ruby\r\n" would end up as:

(2 ** R) * (3 ** u) * (5 ** b)....

10992805522291106558517740012022207329045811217010725353610920778
28664749233402453985379760678149866991742205982820039955872246774
86029159248495553882158351479922840433375701904296875000000000000
00000000000000000000000000000000000000000000000000000000000000000
000000

The idea is partly to obscure the message by the amount of factorization = needed.
This quiz is to write a program to G=F6delize a message, and a program to
deG=F6delize it.

The funtion used to map characters described in the book is "A" =3D> 1, "= B" =3D> 2,
etc and an example is given where spaces are 0. Nothing further is said a= bout
punctuation, or lower case. The message sent in the book is:

msg =3D (3.875 * (12 ** 26)) +
(1973 ** 854) + (331 ** 852) +
(17 ** 2008) + (3 ** 9707) + (2 ** 88) - 78

which it turns out has lots of 0 powers in it, so I strictly don't need t= he
ASCII + 1 I've used in my example, I could use just ASCII, and the nulls = would
not increase the size of the resulting number. This further means that if= a list
of characters is sent in decreasing frequency order with the message, the= most
frequent could be encoded as 0 and the number would be that much smaller.= In
English it is likely to be an "e" or " " which ends up coded as 0.

Interesting things arising from this:

1 Finding the power once a prime is selected
2 Getting the list of primes in the first place
3 encoding of characters, as mentioned above
4 representing the number that results from encoding.

--=20
There are two ways of constructing a software design: One way is to
make it so simple that there are obviously no deficiencies, and the
other way is to make it so complicated that there are no obvious
deficiencies. The first method is far more difficult.

- C.A.R. Hoare -

 

[steve]

there's an instance var @primes which has the list of already generated
primes, @primes.last would do it

My solution follows. I would have liked the Prime class to have a
"this" method that would allow me to get the most recently returned
prime number again, as that would have shaved a line off. My goals
were to keep the Encryption class short and stateless, so please let
me know if you see ways to shorten it further.

# code begins

require 'mathn'

class Encryption
def Encryption.encode(msg,primes=3DPrime.new)
return 1 if msg.size.zero?
return (primes.succ ** (1 + msg[0])) * encode(msg.slice(1,
msg.size),primes)
end
def Encryption.decode(num,primes=3DPrime.new)
return "" unless num > 1
prime =3D primes.next
multiplicity =3D factor_multiplicity(prime,num)
(multiplicity-1).chr + Encryption.decode(num / (prime **
multiplicity), primes)
end
private
def Encryption.factor_multiplicity(factor,num)
1.upto(num) {|x| return x - 1 unless num.modulo
(factor**x).zero?}
end
end

puts "Test encoding: "+Encryption.encode("Ruby\n").to_s+"\n"
puts "Test decoding: "+Encryption.decode(Encryption.encode("Ruby\n"))+"\n= "

# code ends

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this qui=

z

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.

-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=

=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D

by Hugh Sasse

In the book "Starburst" by Frederik Pohl ISBN 0-345-27537-3, page 56, without
really spoiling the plot, some characters complain about the verbosity of
communications and encode a message by G=F6delizing it (detailed on pag=

e

58).

The encoding works by taking each successive character of a message and raising
each successive prime to some function of that character, and multiplying these
powers of primes together. So for example we could use the ASCII code + 1 to
allow for nulls to be encoded. Then "Ruby\r\n" would end up as:

(2 ** R) * (3 ** u) * (5 ** b)....

10992805522291106558517740012022207329045811217010725353610920778
28664749233402453985379760678149866991742205982820039955872246774
86029159248495553882158351479922840433375701904296875000000000000
00000000000000000000000000000000000000000000000000000000000000000
000000

The idea is partly to obscure the message by the amount of factorizatio=

n

needed.
This quiz is to write a program to G=F6delize a message, and a program = to
deG=F6delize it.

The funtion used to map characters described in the book is "A" =3D> 1, "B" =3D> 2,
etc and an example is given where spaces are 0. Nothing further is said about
punctuation, or lower case. The message sent in the book is:

msg =3D (3.875 * (12 ** 26)) +
(1973 ** 854) + (331 ** 852) +
(17 ** 2008) + (3 ** 9707) + (2 ** 88) - 78

which it turns out has lots of 0 powers in it, so I strictly don't need the
ASCII + 1 I've used in my example, I could use just ASCII, and the null=

s

would
not increase the size of the resulting number. This further means that if a list
of characters is sent in decreasing frequency order with the message, the most
frequent could be encoded as 0 and the number would be that much smaller. In
English it is likely to be an "e" or " " which ends up coded as 0.

Interesting things arising from this:

1 Finding the power once a prime is selected
2 Getting the list of primes in the first place
3 encoding of characters, as mentioned above
4 representing the number that results from encoding.

--
There are two ways of constructing a software design: One way is to
make it so simple that there are obviously no deficiencies, and the
other way is to make it so complicated that there are no obvious
deficiencies. The first method is far more difficult.

- C.A.R. Hoare -

 

[Eric Lavigne]

Here's my submission:

http://pastie.caboo.se/119486

class String
def godelize
prime = 0 ; product = 1
each_byte do |b|
product *= (prime = prime.next_prime) ** (b+1)
end

product
end

def self.from_godel(godel_integer)

I learned about the "self" keyword and adding methods to existing
classes by reading Steve's submission. I modified my own submission to
use these. It is now slightly shorter and significantly easier to use.

# code begins

require 'mathn'

class String
def to_godel(primes=Prime.new)
return 1 if size.zero?
return (primes.succ ** (1 + self[0])) * slice(1,size).to_godel(primes)
end
def self.from_godel(num,primes=Prime.new)
return "" unless num > 1
prime = primes.next
multiplicity = factor_multiplicity(prime,num)
(multiplicity-1).chr + from_godel(num / (prime ** multiplicity), primes)
end
private
def self.factor_multiplicity(factor,num)
1.upto(num) {|x| return x - 1 unless num.modulo(factor**x).zero?}
end
end

puts "Test encoding: "+"Ruby\n".to_godel.to_s+"\n"
puts "Test decoding: "+String.from_godel("Ruby\n".to_godel)+"\n"

# code ends

--
There are two ways of constructing a software design: One way is to
make it so simple that there are obviously no deficiencies, and the
other way is to make it so complicated that there are no obvious
deficiencies. The first method is far more difficult.

- C.A.R. Hoare -

 

[Eric Lavigne]

there's an instance var @primes which has the list of already generated
primes, @primes.last would do it

Sounds simple enough, but accessing instance variables seems to be a
rather verbose operation.

Here is what it should look like (if the Prime class worked the way I
originally expected):
primes = Prime.new
primes.next.doSomething
primes.last.doSomethingElse

Here was my first attempt using your suggestion, which looks
reasonable but doesn't work.
primes = Prime.new
primes.next.doSomething
(e-mail address removed)

Here is what finally worked, but I can't believe the verbosity of the
final line. Is there a shorter way?
primes = Prime.new
primes.next.doSomething
primes.instance_variable_get("@primes").last.doSomethingElse


--
There are two ways of constructing a software design: One way is to
make it so simple that there are obviously no deficiencies, and the
other way is to make it so complicated that there are no obvious
deficiencies. The first method is far more difficult.

- C.A.R. Hoare -

 

[Eric I.]

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

 

[Eric I.]

One other efficiency I played with was in getting the prime values.
It turns out that using the Prime class in the 'mathn' library isn't
that fast as you get to higher primes. As a test, try figuring out
the 10,000th prime in irb.

So, it would be a lot quicker to feed the encoding and decoding
processes pre-computed primes. And it turns out you can easily
download the first 15 million primes from:

http://primes.utm.edu/lists/small/millions/

So, here's a class that can be used in place of the 'mathn' library's
Prime class, that will get its data from the downloaded (and unzipped)
files from that source.

Eric

====

Interested in hands-on, on-site Ruby training? See http://LearnRuby.com
for information about a well-reviewed class.

========

# 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:
# http://primes.utm.edu/lists/small/millions/


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

 

[Justin Ethier]

Hello,

Here is my solution. First, I used a pre-computed array of the first 256
primes. I did this to streamline things and because after a certain number
of input characters it becomes more practical to break the input into chunk=
s
and start at 2 again:

# Use first 256 prime numbers from
http://en.wikipedia.org/wiki/List_of_prime_numbers
Primes =3D [2, 3, 5, 7 ... 1619]

The following function then encrypts text by using ASCII code + 1 as the
power, per the quiz statement. Spaces are encoded as 0 to slightly reduce
overall processing.

def GoedelCipher.encrypt(plain_text)
ascii =3D plain_text.split("").map{|c| c[0]}

msg =3D 1
for i in 0...ascii.size
pwr =3D ascii =3D=3D ' ' ? 0 : (ascii + 1)
msg *=3D Primes ** pwr
end

msg
end

This function converts back to the original plaintext by factoring out each
prime number (2, 3, etc) in turn:

def GoedelCipher.decrypt(msg)
# decoding: see
http://www.math.ksu.edu/~dph/010_readings/Unit1Lesson1.html
# for an intro to factoring prime numbers.
# eg: 60=3D2x3x2x5, so could div 60 by 2 until result%2 !=3D 0
plain_text =3D ""

i =3D 0
while msg > 1

letter_count =3D 0
while msg % Primes =3D=3D 0
letter_count +=3D 1
msg /=3D Primes
end

plain_text +=3D letter_count =3D=3D 0 ? ' ' : (letter_count - 1).chr
i +=3D 1 # Move to next prime
end

plain_text
end

Fortunately, ruby will automatically cast very large integers to BigNum, so
the code does not have to worry about *huge* numbers. The previous 2
functions only work on input that is 256 characters long or less, since onl=
y
256 primes are defined in the initial array. To work with larger inputs, th=
e
following functions are provided to break the input up into smaller chunks
(blocks):

def GoedelCipher.large_encrypt(plain_text, block_size =3D Primes.size)
blocks =3D []
for i in 0..(plain_text.size / block_size)
blocks << encrypt(plain_text[i * block_size, block_size])
end
blocks
end

def GoedelCipher.large_decrypt(msg)
msg.map{|block| decrypt(block)}.join
end

This code is then used to kick-off the encryption / decryption:

if ARGV.size !=3D 1
puts "Usage: goedel_cmb.rb message_text"
else
msg =3D GoedelCipher.large_encrypt(ARGV[0])
puts "Encrypted Message: #{msg}"

plaintext =3D GoedelCipher.large_decrypt(msg)
puts "Decrypted Message: #{plaintext}"
end

Here are pasties of everything:
Goedel Module: http://pastie.caboo.se/119595
Command Line Program: http://pastie.caboo.se/119598
Benchmark: http://pastie.caboo.se/119597

Thanks,

Justin

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.


-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-= =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D

by Hugh Sasse

In the book "Starburst" by Frederik Pohl ISBN 0-345-27537-3, page 56,
without
really spoiling the plot, some characters complain about the verbosity of
communications and encode a message by G=F6delizing it (detailed on page
58).

The encoding works by taking each successive character of a message and
raising
each successive prime to some function of that character, and multiplying
these
powers of primes together. So for example we could use the ASCII code + 1
to
allow for nulls to be encoded. Then "Ruby\r\n" would end up as:

(2 ** R) * (3 ** u) * (5 ** b)....

10992805522291106558517740012022207329045811217010725353610920778
28664749233402453985379760678149866991742205982820039955872246774
86029159248495553882158351479922840433375701904296875000000000000
00000000000000000000000000000000000000000000000000000000000000000
000000

The idea is partly to obscure the message by the amount of factorization
needed.
This quiz is to write a program to G=F6delize a message, and a program to
deG=F6delize it.

The funtion used to map characters described in the book is "A" =3D> 1, "= B"
=3D> 2,
etc and an example is given where spaces are 0. Nothing further is said
about
punctuation, or lower case. The message sent in the book is:

msg =3D (3.875 * (12 ** 26)) +
(1973 ** 854) + (331 ** 852) +
(17 ** 2008) + (3 ** 9707) + (2 ** 88) - 78

which it turns out has lots of 0 powers in it, so I strictly don't need
the
ASCII + 1 I've used in my example, I could use just ASCII, and the nulls
would
not increase the size of the resulting number. This further means that if
a list
of characters is sent in decreasing frequency order with the message, the
most
frequent could be encoded as 0 and the number would be that much smaller.
In
English it is likely to be an "e" or " " which ends up coded as 0.

Interesting things arising from this:

1 Finding the power once a prime is selected
2 Getting the list of primes in the first place
3 encoding of characters, as mentioned above
4 representing the number that results from encoding.

 

[James Edward Gray II]

I wanted to make an effort at runtime efficiency.

Clever stuff. Did you benchmark this against any other approaches?
I would love to know what kind of an improvement you achieved.

James Edward Gray II

 

[Eric I.]

Clever stuff. Did you benchmark this against any other approaches?
I would love to know what kind of an improvement you achieved.

I was curious about this too. So I ran the five solutions submitted
so far back to back on decoding (not encoding). The plain text is the
following quote from Einstein consisting of 329 characters. I wanted
it to be somewhat long to highlight speed differences, and 329
characters is really not all that big. And Einstein and Goedel were
good friends when they both worked at Princeton. Here's the quote;
note the embedded newlines:

The important thing is not to stop questioning. Curiosity
has its own\nreason for existing. One cannot help but be in
awe when he\ncontemplates the mysteries of eternity, of life,
of the marvelous\nstructure of reality. It is enough if one
tries merely to comprehend a\nlittle of this mystery every
day. Never lose a holy curiosity.\n

Encoded, it's an 87,418 digit base 10 number.

I had to adjust some others' solutions minimally. For example, I had
to expand the list of primes that Justin Ethier's solution used, and I
had to put the encoded message in one of his blocks before submitting
it to his decode routine.

Here are the times I got in seconds:

Eric I: . 3.485
James Koppel: 11.779
Justin Either: 11.868
Eric Lavigne: 19.390
steve: 20.982

So it would appear that the complexity of my process pays off in
time. Of course, everything is a tradeoff. I went for speed. Others
aimed for alternate worthwhile goals, such as easy to understand code,
succinct code, and/or highly Rubyesque code.

Eric

 

[James Edward Gray II]

I was curious about this too. So I ran the five solutions submitted
so far back to back on decoding (not encoding). The plain text is the
following quote from Einstein consisting of 329 characters. I wanted
it to be somewhat long to highlight speed differences, and 329
characters is really not all that big. And Einstein and Goedel were
good friends when they both worked at Princeton. Here's the quote;
note the embedded newlines:

The important thing is not to stop questioning. Curiosity
has its own\nreason for existing. One cannot help but be in
awe when he\ncontemplates the mysteries of eternity, of life,
of the marvelous\nstructure of reality. It is enough if one
tries merely to comprehend a\nlittle of this mystery every
day. Never lose a holy curiosity.\n

Encoded, it's an 87,418 digit base 10 number.

I had to adjust some others' solutions minimally. For example, I had
to expand the list of primes that Justin Ethier's solution used, and I
had to put the encoded message in one of his blocks before submitting
it to his decode routine.

Here are the times I got in seconds:

Eric I: . 3.485
James Koppel: 11.779
Justin Either: 11.868
Eric Lavigne: 19.390
steve: 20.982

So it would appear that the complexity of my process pays off in
time. Of course, everything is a tradeoff. I went for speed. Others
aimed for alternate worthwhile goals, such as easy to understand code,
succinct code, and/or highly Rubyesque code.

Great analysis. Thanks!

James Edward Gray II

 

[Eric Lavigne]

Eric I: . 3.485

James Koppel: 11.779
Justin Either: 11.868
Eric Lavigne: 19.390
steve: 20.982

So it would appear that the complexity of my process pays off in
time. Of course, everything is a tradeoff. I went for speed. Others
aimed for alternate worthwhile goals, such as easy to understand code,
succinct code, and/or highly Rubyesque code.

Eric

It makes a lot of sense to optimize for speed here because decryption
is a slow process, and Eric I is the clear winner there.

I am new to Ruby and pulling out the pickaxe book for each line of
code that I write, but none of the entries seem difficult to
understand. Which entries are Rubyesque?

--
There are two ways of constructing a software design: One way is to
make it so simple that there are obviously no deficiencies, and the
other way is to make it so complicated that there are no obvious
deficiencies. The first method is far more difficult.

- C.A.R. Hoare -

 

[James Edward Gray II]

It makes a lot of sense to optimize for speed here because decryption
is a slow process, and Eric I is the clear winner there.

I am new to Ruby and pulling out the pickaxe book for each line of
code that I write, but none of the entries seem difficult to
understand. Which entries are Rubyesque?

Well, in my opinion, you're latest entry is quite nice.

James Edward Gray II

 

[Eric I.]

I am new to Ruby and pulling out the pickaxe book for each line of
code that I write, but none of the entries seem difficult to
understand. Which entries are Rubyesque?

Well there's no official definition of Rubyesque. But using monkey
patching to put the encoding function in String and the decoding
function in Integer strikes me as being Rubyesque. Many of the built-
in classes have a "to_yaml" method, for example, which is another type
of encoding. I think steve was the first to do that.

Eric

 

[Phrogz]

Interesting things arising from this:

1 Finding the power once a prime is selected
2 Getting the list of primes in the first place
3 encoding of characters, as mentioned above
4 representing the number that results from encoding.

Looking at #4, I convert the Fixnum/Bignum into a binary stream:

PRIMES = DATA.read.split(/\s+/).map{ |s| s.to_i }

module Enumerable
def inject_with_index( *arg )
idx = -1
inject(*arg){ |memo,obj| yield( memo, obj, idx += 1 ) }
end
end

class Integer
def to_binary
hex_string = to_s(16)
hex_string = "0#{hex_string}" if (hex_string.length % 2) == 1
[ hex_string ].pack( 'H*' )
end
def self.from_binary( binary_string )
binary_string.unpack( 'H*' )[ 0 ].to_i( 16 )
end
end

class String
def to_godel
split(//).inject_with_index(1){ |prod,s,i| prod *
PRIMES**(s[0]+1) }
end
def self.from_godel( int )
# TODO - steal from someone else's solution
end

def to_godel_binary
to_godel.to_binary
end
def self.from_godel_binary( binary_string )
from_godel( Integer.from_binary( binary_string ) )
end
end

source = "Ruby\n"
p source.to_godel, source.to_godel.to_s(16).length
#=>
10992805522291106558517740012022207329045811217010725353610920778286647492334024539853797606781498669917422059828200399558722467748602915924849555388215835147992284043337570190429687500000000000000000000000000000000000000000000000000000000000000000000000000000000000
#=> 266

p source.to_godel_binary, source.to_godel_binary.length
#=> "\025\321\241\301d\266\253\317\366\246\361\242\226W
\247\300\253\025\345p\326\325=\2569yp\005HY\231\006\354\371;TV
\224\335\b\321\317\230\004\315Hk2?\345\314\365\212\017H\2456@
\224\303\204\244\346\005\205\273\331\031]K\030\370\207di
\216\035\247\262\255I\353\355\256\016\250\e\377{r\260\037\324\354-
\304\212\025!\337\200\000\000\000\000\000\000\000\000\000\000"
#=> 111

# A few primes only, trimmed for posting; add more for larger messages
__END__
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
101 103
107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193
197 199
211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307
311 313
317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421
431 433
439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547
557 563
569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659
661 673
677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797
809 811
821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929
937 941

 

[Phrogz]

p source.to_godel.to_s(16), source.to_godel.to_s(16).length
#=>
109928055222911065585177400120222073290458112170107253536109207782866474923 340245398537976067814986699174220598282003995587224677486029159248495553882 158351479922840433375701904296875000000000000000000000000000000000000000000 00000000000000000000000000000000000000000
#=> 266

Oops, that second result is from:

p source.to_godel, source.to_godel.to_s.length

which is the more interesting value. (As a hex string it's 221 chars,
I believe.)