From: Vance A Heron <heron@...>
Date: 2005-01-07T18:02:09+09:00
Subject: Re: [SUMMARY] Cryptograms (#13)

--=-F/fjOwTFLoeqy+p+1VGt
Content-Type: text/plain
Content-Transfer-Encoding: 7bit

Late response, with a question about the solvabilty of these
kind of problems in general.

I used a similar approach and get similar answers to Glenns, only 
much slower (although mine finishes in finite time :)  When running
Glens program, I get many partial solutions in < 1 Sec (including most
that my program finds) - then his progam consumes 99% of my CPU
time indefinately. On my PC, mine runs in ~10 S for crypto1
(partial answer)  ~16 S for crypto2, full correct answer,
and  ~80 S for crypto3, producing garbage. (can I buy a
vowel? :)

Actually I added the ablity to provide a partial map
to help prime the solver - still cant make sense of crypto3.

The main question I have is how does one handle non-dictionary
words that match a dictionary word signature - and then force
other wrong choices.  The specific case is "alva" which can
map to "aqua". Once I have "aqua" as plain text, it prevents
the solver from using the letter 'u' in genius - making that
word match denims.

In fact I can envsion quotes with non-dictionary words that
could map, wrongly, to a set of all dictionary words - i.e.
the solution with 1 or more "unsolved" words would be more
correct than the solution with no unsolved words...

There's also the situation of "bent, cent, vent, went" - where
the choice of any of them doesn't affect any other words in the
cypher text - providing no help selecting between them.

In both these cases, I don't think backtracking can help - other
than to provide a number of possible solutions that a person
could read and pick from?

Addionally, while I agree that brute force w/26! possible maps
is impractial, after a certain point, would it make sense to
use the brute force approach for the "remaining" letters - 
somwhere in the 8-10 letters remaining?

Thanks to all involved in providing this - been reading for a
while, but this is my first try at solving one ... took *way*
more time than I intended, but was lots of fun.  Looking forward
to more in the future.

Vance

--=-F/fjOwTFLoeqy+p+1VGt
Content-Disposition: attachment; filename=rq13
Content-Type: application/x-ruby; name=rq13
Content-Transfer-Encoding: 7bit

#! /bin/env ruby

def sig(w)
#  rtn = '' 
  rtn = 0 
  ltrs = w.split(//)
  ndx = 0 
  while l = ltrs.shift 
    if fnd = ltrs.index(l)
#      rtn += ndx.to_s + ',' +  (fnd+ndx+1).to_s + ' ' 
      rtn = rtn*100 + ndx*10 + fnd
    end
    ndx += 1
  end
  return rtn
end

def get_words (fname, ary )
  file = File.open(fname)
  while word = file.gets
    ary.push(word.chomp) 
  end
  file.close
end

def choices (dict, word, dpairs, pairs, re = nil)
  re = '.'* word.length unless re
  c = eval("dict.grep(\/^#{re}\$\/)")
  c = c.delete_if{ |w| dpairs[w] != pairs[word] }
  return c
end

def decode (cyphertext, cypher, plain)
  code = {}
  ('a'..'z').each { |l| code[l] = '.'}
  kl = cypher.split(//)
  wl = plain.split(//)
  kl.each_index { |i|
    code[kl[i]] = wl[i] if code[kl[i]] == '.'
  }
  clear = []
  cyphertext.each {|w|
     next unless w
     word = ""
     w.each_byte { |c|
       word << code[c.chr] if c
     }
     clear <<  word
  }
  return clear 
end 

def count_options (puzzle, dictionary, pairs, dpairs, sizes, clear)
min_choices = 10000
savi = -1
savl = -1
savt = []
puzzle.each_index { |i|

  t = choices(dictionary, puzzle[i], dpairs, pairs, clear[i])

  sizes[i] = t.length
  next if (clear[i] && clear[i] !~ /\./)
  if sizes[i] > 0 && sizes[i] < min_choices
    min_choices = sizes[i]
    savt = t 
    savi = i
  end
}
if savi == -1
  return nil, nil
else
  return puzzle[savi], savt
end
end

### MAIN 

dictionary = []
puzzle = []
to_try = {} 

get_words(ARGV[0], dictionary)
#dictionary.push('a')
#dictionary.push('i')

get_words(ARGV[1], puzzle)

#puzzle.each {|a| a.uniq! if a }

# find words w/dup letters
pairs = {}
puzzle.each {|w| pairs[w] = sig(w) }

dpairs = {}
dictionary.each {|w| dpairs[w] = sig(w) }

sizes = []
clear = []

eword = []
tries =  []
newtries =  []

etxt = ""
ctxt = ""
trial = ""
c2p = {}
cta = []

# first time
if ARGV[3]
  etxt=ARGV[2].to_s
  ctxt=ARGV[3].to_s
  clear = decode(puzzle, etxt, ctxt)
end
  
eword[0], tries = count_options(puzzle, dictionary, pairs, dpairs, sizes, clear)
puts "#{puzzle.join(' ')}\n" 
puts "#{sizes.join(' ')}"


begin
  tries_s = []
  trial_s = []
  clear_s = []
  sizes_s = []
  zeros = []
  num_opts = []

  etxt += eword[0]
  eword_s = eword[0]

  i = 0
  tries.each{ |trial| 

    next if ( sig(etxt) != sig(ctxt+trial))   # incompatible signatures

    clear = decode(puzzle, etxt, ctxt+trial)
    eword[i], tries_s[i] = count_options(puzzle, dictionary, pairs, dpairs, sizes, clear)

    puts "#{clear.join(' ')}"
#    puts "#{sizes.join(' ')}"

    clear_s[i] = clear
    sizes_s[i] = sizes
    trial_s[i] = trial
    zeros[i] = sizes.grep(0).length
    i += 1
  }


  break unless i > 0

  # find best "trial" 
  best = -1
  num_choices = 10000
  sizes_s.each_index { |i|
    sizes_s[i].each_index { |j|
      if (sizes_s[i][j] > 0 &&
         sizes_s[i][j] <= num_choices &&
         clear_s[i][j] =~ /\./) 
        best = i 
        num_choices = sizes_s[i][j]
      end
    } 
  }

  if best == -1   # no unresolved options w/1 choice ...
    best = zeros.rindex(zeros.min) || -1
  end

  if best  != -1
    ctxt += trial_s[best]
    tries = tries_s[best]
    clear = clear_s[best]
    eword[0] = eword[best] 
    puts "DBG - selected #{eword_s} -> #{trial_s[best]}" 
  end

end while eword[0]


exit

--=-F/fjOwTFLoeqy+p+1VGt--