From: James Edward Gray II Date: 2007-11-19T06:05:39+09:00 Subject: Fwd: [QUIZ] #147 Goedelize message --Apple-Mail-1-216889552 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Begin forwarded message: > From: Hugh Sasse > Date: November 16, 2007 1:38:10 PM CST > To: James Edward Gray II > Subject: [QUIZ] #147 Goedelize message > > You said resend my code when the quiz comes up. It's attached, > unless something's botched. > > Hugh > --Apple-Mail-1-216889552 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0666; name=goedel.rb Content-Disposition: attachment; filename=goedel.rb #!/usr/local/bin/ruby -w=0D =0D PRIMES =3D [2,3]=0D =0D # Work out what the x'th prime is, starting from 0.=0D # Uses the PRIMES array, declared above.=0D # The algorithm is based on:=0D # k is prime if no number other than 1 divides it.=0D # If some n divides it then n * m =3D k, so one of =0D # these must be <=3D sqrt(k), so we only need to search=0D # up to n: n * n =3D k. If some n divides it, then =0D # if that n is not prime, it has prime factors. Else it=0D # must be prime itself. So we only need to search through=0D # the list of primes found so far, rather than testing all=0D # possible factors.=0D def primes(x)=0D # puts "x is #{x}"=0D if x < PRIMES.size =0D return PRIMES[x]=0D else=0D k =3D PRIMES[PRIMES.size - 1] + 1=0D # puts "k is #{k}, PRIMES.size is #{PRIMES.size}"=0D while (PRIMES.size <=3D x)=0D # puts "k is #{k}"=0D is_prime =3D true=0D 0.upto(PRIMES.size) do |i|=0D p =3D PRIMES[i]=0D break if p.nil?=0D break if p * p > k=0D quot =3D k / p=0D if (k =3D=3D quot * PRIMES[i]) then=0D is_prime =3D false=0D # puts "#{k} is not prime"=0D break=0D end=0D end=0D PRIMES << k if is_prime=0D k +=3D 1=0D end=0D return PRIMES[x]=0D end=0D end=0D =0D #Goedelize the message in the string. Uses ASCII+1 encoding=0D #rather than that used in Starburst, because it was easiest=0D #to code.=0D def goedelize(message)=0D code =3D 1=0D count =3D 0=0D message.each_byte do |b|=0D code *=3D primes(count) ** (b+1)=0D count +=3D 1=0D end =0D return code=0D end =0D =0D # This is used by goedelize2 to speed up the search for=0D # the power of some prime that divides the number.=0D # If p ** k divides n, then the highest value of k must=0D # be >=3D k. Search until we find that highest power.=0D # Normal binary search puts the midpoint on one side,=0D # but we need to keep the greatest power found so far=0D # in case we don't find a bigger one.=0D def binary_search(n, p, lo, hi)=0D # puts "binary_search(#{n}, #{p}, #{lo}, #{hi})"=0D # puts "binary_search(n, #{p}, #{lo}, #{hi})"=0D if lo > hi=0D raise "not found, #{lo}, #{hi}"=0D end=0D if lo =3D=3D hi=0D return lo=0D else=0D mid =3D (lo + hi) / 2=0D if mid =3D=3D lo=0D return mid=0D end=0D guess =3D p ** mid =0D # quot =3D n / guess=0D # if quot * guess =3D=3D n=0D if n.remainder(guess).zero?=0D return binary_search(n, p, mid, hi)=0D else=0D return binary_search(n, p, lo, mid)=0D end=0D end=0D end=0D =0D # Convert the character code (number), to a character=0D # according to the encoding. The encoding in Starburst=0D # on page 58 is of the form "A =3D> 1, B =3D> 2,...", with=0D # an example where space is coded as 0. Otherwise there=0D # seems to be no punctuation. Hence my extending this to=0D # complete bytes, by default. Clearly this could be further=0D # extended to UTF16, UTF32...=0D def decode(code, encoding)=0D result =3D ""=0D case encoding=0D when :ascii=0D result +=3D (code-1).chr=0D else=0D case code=0D when 0=0D result +=3D " "=0D when 1..26=0D # 1 =3D A, 2 =3D B...=0D result +=3D (code+64).chr=0D else=0D result +=3D "."=0D end=0D end=0D return result=0D end=0D =0D # This is like degoedelize, only instead of searching for the=0D # index (power) by counting up, it uses a binary search strategy.=0D # For a byte this should be only about 8 tests, rather than about=0D # 128 on average.=0D def degoedelize2(n,encoding=3D:ascii)=0D result =3D ""=0D quot =3D n=0D i =3D 0=0D p =3D primes(i)=0D while quot > 1=0D # puts "quot =3D #{quot}"=0D # puts "p =3D #{p}"=0D if quot.remainder(p).zero?=0D puts "quot is #{quot.to_s.size} digits, p is #{p.to_s.size} = digits"=0D code =3D binary_search(quot, p, 0, 256)=0D # result +=3D (code -1).chr=0D result +=3D decode(code, encoding)=0D # This next is needed as the example in the book contains a lot=0D # of space it turns out.=0D result.squeeze!(" \t.") if encoding =3D=3D :Pohl=0D puts "result =3D #{result}"=0D quot /=3D (p ** code)=0D else=0D result +=3D decode(0, encoding)=0D result.squeeze!(" \t.") if encoding =3D=3D :Pohl=0D end=0D i +=3D 1=0D p =3D primes(i)=0D puts "quot is #{quot.to_s.size} digits, p is #{p.to_s.size} digits" = if (i%1000).zero?=0D end=0D return result=0D end=0D =0D # Increasing prime factors as we go through the =0D # message, we try to find the power of that prime=0D # which was used to encode the message. This is =0D # p ** k is a factor of n, for the largest value of=0D # k.=0D def degoedelize(n,encoding=3D:ascii)=0D result =3D ""=0D quot =3D n=0D i =3D 0=0D p =3D primes(i)=0D puts "p is #{p}"=0D while quot > 1=0D count =3D 0=0D guess =3D 128=0D quot =3D n / p=0D puts "quot is now #{quot}"=0D while quot * p =3D=3D n=0D # it is a factor=0D count +=3D 1 =0D n =3D quot=0D quot =3D n / p=0D puts "quot is #{quot}"=0D puts "count is #{count}"=0D puts "i is #{i}"=0D puts "p is #{p}"=0D end=0D if count.zero?=0D puts "count unexpectedly #{count}"=0D else=0D result +=3D decode(count,encoding)=0D # This next is needed as the example in the book contains a=0D # lot of space it turns out.=0D result.squeeze!(" \t.") if encoding =3D=3D :Pohl=0D end=0D i +=3D 1=0D p =3D primes(i)=0D puts "i is #{i}, p is #{p}"=0D end=0D return result=0D end=0D =0D if __FILE__ =3D=3D $0=0D =0D if ARGV.size =3D=3D 0=0D # We are just running checks to see all is well.=0D 0.upto(20) do |x|=0D puts primes(x)=0D end=0D message =3D "A rose by any other name would smell as sweet"=0D g =3D goedelize(message)=0D puts g=0D sleep 5=0D str =3D degoedelize(g)=0D puts "str is #{str}"=0D sleep 5=0D str2 =3D degoedelize2(g)=0D puts "str2 is #{str2}"=0D puts "str =3D=3D str2 is #{str =3D=3D str2}"=0D else=0D # We are processing files.=0D case ARGV[0]=0D when "-d"=0D # decode=0D open(ARGV[1], "r") do |ifp|=0D msg =3D ifp.read.gsub(/\s+/m, '').to_i=0D open(ARGV[2], "wb") do |ofp|=0D ofp.print degoedelize2(msg,:ascii)=0D end=0D end=0D when "-e"=0D # encode=0D open(ARGV[1], "rb") do |ifp|=0D msg =3D ifp.read=0D open(ARGV[2], "w") do |ofp|=0D ofp.print goedelize(msg)=0D end=0D end=0D when "-p"=0D # starburst by Frederik Pohl ISBN 0-345-27537-3, page 56=0D # msg =3D (3.875 * (12 ** 26)).to_i +... # We'd prefer this to=0D # be integer, so rewrite as:=0D msg =3D (558 * (12 ** 24)) +=0D (1973 ** 854) + (331 ** 852) +=0D (17 ** 2008) + (3 ** 9707) + (2 ** 88) - 78=0D txt =3D degoedelize2(msg, :Pohl)=0D puts txt=0D else=0D puts <<-EOM=0D Usage: #{$0} [-deh] [infile outfile]=0D where -d means decode (degoedelize)=0D -e means encode (goedelize)=0D -h (or anything) means help=0D If files are given, at the moment they must be true files, not '-'=0D for stdin, stdout, and both must be given. This cannot be used=0D as a filter at the moment.=0D If no arguments are given, the program self tests.=0D EOM=0D end=0D end=0D end=0D --Apple-Mail-1-216889552 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed --Apple-Mail-1-216889552--