--------------030403030206060304010407
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Here's my "solution". I must admit that it does not perform very well
on crypto3.txt, although based on copious diagnostic output I think it
would eventually come up with the correct solution after a few days.
The comments in my code may help illuminate some of my thinking, which
was very similar to Michael C. Libby's, although the implementation
details are quite different.
I'll provide a summary of all (two, so far) solutions and a discussion
of my approach on Thursday.
--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoil.com/>
--------------030403030206060304010407
Content-Type: text/plain;
name
solve.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename
solve.rb"
#!ruby
STDOUT.sync rue
# A utility class to read files containing words one-per-line
class WordReader
include Enumerable
def initialize(filename)
@filename ilename
end
def each
File.open(@filename) do |file|
file.each do |word|
word.chomp!
next if word.length 0
yield word
end
end
end
end
# A copy of the dictionary, with words grouped by "signature".
# A signature simplifies a word to its repeating letter patterns.
# The signature for "cat" is 1.2.3 because each successive letter
# in cat is unique. The signature for "banana" is 1.2.3.2.3.2,
# where letter 2, "a", is repeated three times and letter 3, "n"
# is repeated twice.
class Dictionary
def initialize(filename)
@all }
@sigs }
@max_sig il
@max_sig_len il
WordReader.new(filename).each { |word|
word.downcase!
word.gsub!(/[^a-z]/, '')
next if word.empty?
@all[word] rue
sig ignature(word)
@sigs[sig] || ]
@sigs[sig].push(word)
}
self.freeze
end
def lookup(word)
@all[word]
end
def candidates(cipher)
@sigs[signature(cipher)]
end
private
def signature(word)
seen }
u
sig ]
word.each_byte do |b|
if not seen[b]
u +
seen[b]
end
sig.push(seen[b])
end
sig.join('.')
end
end
# CMap maintains the mapping from ciphertext to plaintext and the
# some state related to the solution. @map is the actual mapping.
# @solved is just a string with all the solved words. @shelved
# is an array of ciphertext words that cannot be solved because
# the current mapping resolves all their letters and the result
# is not found in the dictionary.
class CMap
attr_reader :map, :solved, :shelved
def initialize(arg il, newmap il, dword il)
case
when arg.kind_of?(String)
@map rg.dup
when arg.kind_of?(CMap)
@map ewmap || arg.map.dup
@solved rg.solved.dup
@shelved rg.shelved.dup
append_solved(dword) if dword
else
@map .' * 26
@solved '
@shelved ]
end
end
def dup
CMap.new(self)
end
# Attempt to update the map to include all letter combinations
# needed to map cword into dword. Return nil if a conflict is found.
def learn(cword, dword)
newmap map.dup
(0...cword.length).each do |i|
c word[i] - ?a
p ewmap[c]
# check for correct mapping
next if p dword[i]
# check for incorrect mapping
return nil if (p ! .) || newmap.include?(dword[i])
# create new mapping
newmap[c] word[i]
end
CMap.new(self, newmap, dword)
end
def append_solved(dword)
@solved + ' unless @solved.empty?
@solved + word
end
def shelve(cword)
@shelved << cword
end
def convert(cword)
pattern '
cword.each_byte do |c|
pattern << @map[c - ?a]
end
pattern
end
end
# Pruner keeps track of maps that have already been tried.
# Some maps are subsets of previously tried maps, allowing us to skip them.
# This may consume more RAM than it is worth.
class Pruner
def initialize(list)
@pruned }
letter A'
@abbrev }
list.each {|w| @abbrev[w] etter.clone; letter.succ!}
end
def genkey(list)
list.collect{|w|@abbrev[w]}.sort.join('.')
end
def test(list, cmap)
key enkey(list)
return false unless prunelist pruned[key]
prunelist.each do |prunemap|
if /#{prunemap}/ cmap.map
return true
end
end
return false
end
def store(list, cmap)
key enkey(list)
#puts "Pruner.store #{cmap.map} #{key}"
@pruned[key] || ]
@pruned[key] pruned[key].reject do |prunemap|
/#{cmap.map}/ prunemap
end << cmap.map
end
end
class Cryptogram
def initialize(filename, dict)
@dict ict
@words ordReader.new(filename).to_a
# clist is the input cipher with no duplicated words
# and no unrecognized input characters
@clist ]
@words.each do |word|
word.downcase!
word.gsub!(/[^a-z]/, '')
next if word.empty? || @clist.include?(word)
@clist.push(word)
end
# Sort by increasing size of candidate list
@clist clist.sort_by {|w| @dict.candidates(w).length}
end
def solve(max_unsolved , stop_on_first rue)
@max_unsolved ax_unsolved
@stop_on_first top_on_first
@checks
@solutions }
@partials }
# @pruner runer.new(@clist)
solve_p(@clist, CMap.new, 0)
end
def solve_p(list, cmap, depth)
# Simplify list if possible
list rescreen(list, cmap)
return if check_solution(list, cmap)
# return if @pruner.test(list, cmap)
solve_r(list, cmap, depth)
return if done?
# @pruner.store(list, cmap)
end#solve_p
def solve_r(start_list, start_cmap, depth)
for i in (0...start_list.length)
# Pull a cword out of start_list
list tart_list.dup
cword ist.delete_at(i)
pattern tart_cmap.convert(cword)
search(cword, pattern) do |dword|
# Try to make a new cmap by learning dword for cword
next unless cmap tart_cmap.learn(cword, dword)
# Recurse on remaining words
solve_p(list, cmap, depth + 1)
return if done?
end#search
end#for
end#solve_r
def done?
@stop_on_first && @solutions.length > 0
end
# Return the subset of cwords in list that are not fully solved by cmap.
# Update cmap with learned and shelved words.
def prescreen(list, cmap)
start_list ]
list.each do |cword|
pattern map.convert(cword)
if pattern.include?(?.)
# cword was not fully resolved.
start_list << cword
elsif @dict.lookup(pattern)
# cword was resolved and is a known word.
cmap.learn(cword, pattern)
else
# cword cannot be solved.
cmap.shelve(cword)
end
end
start_list
end
# Generate dictionary words matching the pattern
def search(cword, pattern)
# the pattern will normally have at least one unknown character
if pattern.include? ?.
re egexp.new("^#{pattern}$")
@dict.candidates(cword).each do |dword|
yield dword if re dword
end
# otherwise, just check that the pattern is actually a known word.
elsif @dict.lookup(pattern)
yield pattern
end
end
def check_solution(list, cmap)
@checks +
unsolved ist.length + cmap.shelved.length
# Did we get lucky?
if unsolved 0
if not @solutions.has_key?(cmap.map)
@solutions[cmap.map] rue
if not @stop_on_first
puts "\nfound complete solution \##{@solutions.length}"
puts "performed #{@checks} checks"
show_cmap(cmap)
end
end
return true
end
# Give up if too many words cannot be solved
if cmap.shelved.length > @max_unsolved
return true
end
# Check for satisfactory partial solution
if unsolved < max_unsolved
if not @partials.has_key?(cmap.map)
@partials[cmap.map] rue
puts "\nfound partial \##{@partials.length} with #{unsolved} unsolved"
puts "performed #{@checks} checks"
puts Time.now
show_cmap(cmap)
end
end
return false
end
def show
puts "Performed #{@checks} checks"
puts "Found #{@solutions.length} solutions"
@solutions.each_key do |sol|
show_cmap(CMap.new(sol))
end
puts
puts "Found #{@partials.length} partial solutions"
@partials.each_key do |sol|
show_cmap(CMap.new(sol))
end
end
def show_cmap(cmap)
puts(('a'..'z').to_a.join(''))
puts cmap.map
puts
@words.each do |word|
pattern map.convert(word)
printf "%-20s %s %-20s\n",
word, (@dict.lookup(pattern) ? ' ' : '*'), pattern
end
puts '-' * 42
end
end
DICTFILE RGV[0]
PARTIAL RGV[1].to_i
puts "Reading dictionary #{DICTFILE}"
dict ictionary.new(DICTFILE)
ARGV[2..-1].each do |filename|
puts "Solving cryptogram #{filename} allowing #{PARTIAL} unknowns", Time.now
cryp ryptogram.new(filename, dict)
cryp.solve PARTIAL
puts "Cryptogram solution", Time.now
cryp.show
end
--------------030403030206060304010407--