Goedel (#147)

[bbazzarrakk]

The three rules of Ruby Q.:

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 Q. 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 T. follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Hugh S.

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.

[bbazzarrakk]

On Nov 16, 2007, at 1:43 PM, Ruby Q. wrote:

by Hugh S.

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).

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

James Edward G. II

[bbazzarrakk]

    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

[bbazzarrakk]

On Nov 16, 2007, at 7:20 PM, Eric I. wrote:

10992805522291106558517740012022207329045811217010725353610920778

28664749233402453985379760678149866991742205982820039955872246774

86029159248495553882158351479922840433375701904296875000000000000

00000000000000000000000000000000000000000000000000000000000000000
000000

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 G. II

[bbazzarrakk]

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)
str = “”
$stdout.sync = 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 = self
true while !(n+=1).prime?

n

end

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

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

true

end

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

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

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

factors

end

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

cnt = 1 ; n = self

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

cnt

end
end

if $0 == 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

[bbazzarrakk]

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

[bbazzarrakk]

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=Prime.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=Prime.new)
return “” unless num > 1
prime = primes.next
multiplicity = 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

On Nov 16, 2007 2:43 PM, Ruby Q. [email protected] wrote:

communications and encode a message by Gödelizing it (detailed on page 58).
86029159248495553882158351479922840433375701904296875000000000000

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 -

[bbazzarrakk]

On Nov 18, 2007 3:42 PM, steve [email protected] wrote:

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
[email protected]

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 -

[bbazzarrakk]

Quoth Eric L.:

primes = Prime.new
final line. Is there a shorter way?
yes.

primes = Prime.new
primes.next.doSomething
primes.instance_variable_get("@primes").last.doSomethingElse

Instead of doing that, you could just extend the Prime class:

class Prime
def this
@primes.last
end
end

primes = Prime.new
primes.next.doSoemthing
primes.this.doSomethingElse

That should work how you want, yes?

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

HTH,

[bbazzarrakk]

On Nov 18, 2007 2:50 PM, steve [email protected] wrote:

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 -

[bbazzarrakk]

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 § is “d”, then
the factor is p101. 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 p64, p32, p16, p8, p4,
p2, and p1. You would find that it does divide by p64, p32,
p4, and p1 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 prime2 is prime squared. And
prime4 is prime2 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 prime64 separately from prime32.
The problem is we have to first divide by prime64, 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**(26), prime(25), prime(24), …, 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 prime64 * prime32 * 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

[bbazzarrakk]

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
chunks
and start at 2 again:

Use first 256 prime numbers from

List of prime numbers

Primes = [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 = plain_text.split(“”).map{|c| c[0]}

msg = 1
for i in 0...ascii.size
  pwr = ascii[i] == ' ' ? 0 : (ascii[i] + 1)
  msg *= Primes[i] ** 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=2x3x2x5, so could div 60 by 2 until result%2 != 0
plain_text = “”

i = 0
while msg > 1

  letter_count = 0
  while msg % Primes[i] == 0
    letter_count += 1
    msg /= Primes[i]
  end

  plain_text += letter_count == 0 ? ' ' : (letter_count - 1).chr
  i += 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
only
256 primes are defined in the initial array. To work with larger inputs,
the
following functions are provided to break the input up into smaller
chunks
(blocks):

def GoedelCipher.large_encrypt(plain_text, block_size = Primes.size)
blocks = []
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 != 1
puts “Usage: goedel_cmb.rb message_text”
else
msg = GoedelCipher.large_encrypt(ARGV[0])
puts “Encrypted Message: #{msg}”

plaintext = GoedelCipher.large_decrypt(msg)
puts “Decrypted Message: #{plaintext}”
end

Here are pasties of everything:
Goedel Module: Parked at Loopia
Command Line Program: Parked at Loopia
Benchmark: Parked at Loopia

Thanks,

Justin

[bbazzarrakk]

On Nov 18, 2007, at 7:40 PM, Eric I. wrote:

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 G. II

[bbazzarrakk]

On Nov 18, 10:26 pm, James Edward G. II [email protected]
wrote:

On Nov 18, 2007, at 7:40 PM, Eric I. wrote:

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.

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 E.'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 K.: 11.779
Justin Either: 11.868
Eric L.: 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

[bbazzarrakk]

On Nov 19, 2007, at 12:15 AM, Eric I. wrote:

so far back to back on decoding (not encoding). The plain text is the
tries merely to comprehend a\nlittle of this mystery every

Eric I: . 3.485
James K.: 11.779
Justin Either: 11.868
Eric L.: 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 G. II

[bbazzarrakk]

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:

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

[bbazzarrakk]

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 -

[bbazzarrakk]

On Nov 19, 8:48 am, Eric L. [email protected] wrote:

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.

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

[bbazzarrakk]

On Nov 19, 2007, at 7:48 AM, Eric L. wrote:

code,
understand. Which entries are Rubyesque?
Well, in my opinion, you’re latest entry is quite nice.

James Edward G. II

[bbazzarrakk]

On Nov 16, 12:43 pm, Ruby Q. [email protected] wrote:

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[i]**(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