From: steve <oksteev@...>
Date: 2007-11-19T05:42:50+09:00
Subject: Re: [QUIZ] Goedel (#147)

------=_Part_12200_25509298.1195418572706
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

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

------=_Part_12200_25509298.1195418572706--