From: Eric Lavigne <lavigne.eric@...>
Date: 2007-11-19T04:54:36+09:00
Subject: Re: [QUIZ] Goedel (#147)

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

                    - C.A.R. Hoare -