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

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

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


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

------=_Part_12134_6500295.1195415431886--