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.
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:
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:
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.
This quiz will run for two weeks because of the holiday. The no-spoiler period is still the normal 48 hours.
James Edward Gray II
···
On Nov 16, 2007, at 1:43 PM, Ruby Quiz wrote:
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:
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
···
On Nov 17, 2007 2:43 AM, Ruby Quiz <james@grayproductions.net> wrote:
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:
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.
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:
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:
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.
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
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.
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:
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:
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.
--
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.
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
# 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
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
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.
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:
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.
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:
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:
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.
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
On Nov 16, 12:43 pm, Ruby Quiz <ja...@grayproductions.net> 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.
Yeah, I think you are right. I've updated the quiz page.
James Edward Gray II
···
On Nov 16, 2007, at 7:20 PM, Eric I. wrote:
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:
there's an instance var @primes which has the list of already generated
primes, @primes.last would do it
···
On Nov 19, 2007 2:54 AM, Eric Lavigne <lavigne.eric@gmail.com> wrote:
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
On Nov 16, 2007 2:43 PM, Ruby Quiz <james@grayproductions.net> wrote:
> 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.
>
>
--
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.
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
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)
--
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.
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:
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
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
primes.@primes.last.doSomethingElse
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
···
On Nov 18, 2007 3:42 PM, steve <oksteev@yahoo.com> wrote:
there's an instance var @primes which has the list of already generated
primes, @primes.last would do it
--
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.
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
···
On Nov 18, 10:26 pm, James Edward Gray II <ja...@grayproductions.net> 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.
> 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
primes.@primes.last.doSomethingElse
Here is what finally worked, but I can't believe the verbosity of the
final line. Is there a shorter way?
--
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,
···
On Nov 18, 2007 3:42 PM, steve <oksteev@yahoo.com> wrote:
On Nov 18, 10:26 pm, James Edward Gray II <ja...@grayproductions.net> > 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 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 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.
Well, in my opinion, you're latest entry is quite nice.
James Edward Gray II
···
On Nov 19, 2007, at 7:48 AM, Eric Lavigne wrote:
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?
