From: Cedric Foll <cedric.foll@...>
Date: 2005-01-06T23:16:46+09:00
Subject: Re: [SUMMARY] Cryptograms (#13)

--------------090908030201050808050200
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Hi,


my solution!

Two minuts later :(.

I've just finished it (started yesterday evening)

The general idea was to construct a dictionnary structure which 
containes all the dictionary.
It's a kind of true with a value '@final' with false or true depends if 
the node is the end of a word.

The I have a method (exist) which is able to find if a word exist on it 
very quickly and using '.' for unknow characters.

The example is found in few minuts on my laptop.

Regards.

--------------090908030201050808050200
Content-Type: text/plain;
 name="crypto.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="crypto.rb"

#!/usr/bin/ruby

require 'pp'

class Array
	def flop
		self.reverse!
		char = self.pop
		self.reverse!
		return char
	end
end

class Dico
	def initialize(tab)
		tab = tab.split('') if tab.class == String
		@char = Hash.new
		@final = false
		if tab.length == 0
			@final = true
		else
			char = tab.flop
			@char[char] = Dico.new(tab)
		end
		@tested = Hash.new
	end
	def add(tab)
		tab = tab.split('') if tab.class == String
                if tab.length == 0 
                        @final = true
                else
			char = tab.flop
			if @char[char]
				@char[char].add(tab)
			else
				@char[char] = Dico.new(tab)
			end
		end
		
	end
	def has(tab)
		tab = tab.split('') if tab.class == String
		return @final if tab == []
		char = tab.flop
		if !@char[char]
			return false
		else
			return @char[char].has(tab)
		end
	end
	def exist(tmp,without=[])
		if @tested[tmp*'']
			return @tested[tmp*'']
		end
		tab = tmp.dup
		tab = tab.split('') if tab.class == String
		return @final if tab == []
		char = tab.flop
                if char != "." 
			if !@char[char]
        	                return false
                	else
	                        return @char[char].exist(tab)
        	        end 
		else
			for i in @char.keys
       	                        next if without.index(i)
				if @char[i].exist(tab)
					@tested[tmp*'']=true
					return true
				end
			end
			return false
		end
	end
end

def calc(words,letters)
	return words.map {|word| word.split('').map {|l| letters[l]}}
end

def print_res(letters)
	for i in 'a' .. 'z'
		print i
	end
	puts ''
	for i in 'a' .. 'z'
		print letters[i] if letters[i]
		print '.' if !letters[i]
	end
	puts ''
end

$i = 0

def test_combi(words, letters, dico)
	new_words = words.map {|word| word.split('').map {|l| letters[l]}}
	$i += 1
	print_res(letters) if $i % 1000 == 0
	p new_words if $i % 1000 == 0
	new_words.each {|word|
		return false if not dico.exist(word,letters.values)
	}
	if new_words.flatten.index('.')
		return true
	else
		print_res(letters)
		p new_words
		exit
	end
end

mydico = Dico.new('')

i = 0
$stdout.sync=true
while $stdin.gets
	mydico.add($_.chomp)
	i += 1
	print '.' if i%1000 == 0
end
puts ''

words = ARGV
letters = Hash.new
for i in words.join('').split('').sort.uniq
	letters[i]='.'
end


for a in 'a' .. 'z'
next if letters.values.include?(a)
letters['a'] = a if letters['a']
next if !test_combi(words,letters,mydico)

for b in 'a' .. 'z'
next if letters.values.include?(b)
letters['b'] = b if letters['b']
next if !test_combi(words,letters,mydico)

for c in 'a' .. 'z'
next if letters.values.include?(c)
letters['c'] = c if letters['c']
next if !test_combi(words,letters,mydico)

for d in 'a' .. 'z'
next if letters.values.include?(d)
letters['d'] = d if letters['d']
next if !test_combi(words,letters,mydico)

for e in 'a' .. 'z'
next if letters.values.include?(e)
letters['e'] = e if letters['e']
next if !test_combi(words,letters,mydico)

for f in 'a' .. 'z'
next if letters.values.include?(f)
letters['f'] = f if letters['f']
next if !test_combi(words,letters,mydico)

for g in 'a' .. 'z'
next if letters.values.include?(g)
letters['g'] = g if letters['g']
next if !test_combi(words,letters,mydico)

for h in 'a' .. 'z'
next if letters.values.include?(h)
letters['h'] = h if letters['h']
next if !test_combi(words,letters,mydico)

for i in 'a' .. 'z'
next if letters.values.include?(i)
letters['i'] = i if letters['i']
next if !test_combi(words,letters,mydico)

for j in 'a' .. 'z'
next if letters.values.include?(j)
letters['j'] = j if letters['j']
next if !test_combi(words,letters,mydico)

for k in 'a' .. 'z'
next if letters.values.include?(k)
letters['k'] = k if letters['k']
next if !test_combi(words,letters,mydico)

for l in 'a' .. 'z'
next if letters.values.include?(l)
letters['l'] = l if letters['l']
next if !test_combi(words,letters,mydico)

for m in 'a' .. 'z'
next if letters.values.include?(m)
letters['m'] = m if letters['m']
next if !test_combi(words,letters,mydico)

for n in 'a' .. 'z'
next if letters.values.include?(n)
letters['n'] = n if letters['n']
next if !test_combi(words,letters,mydico)

for o in 'a' .. 'z'
next if letters.values.include?(o)
letters['o'] = o if letters['o']
next if !test_combi(words,letters,mydico)

for p in 'a' .. 'z'
next if letters.values.include?(p)
letters['p'] = p if letters['p']
next if !test_combi(words,letters,mydico)

for q in 'a' .. 'z'
next if letters.values.include?(q)
letters['q'] = q if letters['q']
next if !test_combi(words,letters,mydico)

for r in 'a' .. 'z'
next if letters.values.include?(r)
letters['r'] = r if letters['r']
next if !test_combi(words,letters,mydico)

for s in 'a' .. 'z'
next if letters.values.include?(s)
letters['s'] = s if letters['s']
next if !test_combi(words,letters,mydico)

for t in 'a' .. 'z'
next if letters.values.include?(t)
letters['t'] = t if letters['t']
next if !test_combi(words,letters,mydico)

for u in 'a' .. 'z'
next if letters.values.include?(u)
letters['u'] = u if letters['u']
next if !test_combi(words,letters,mydico)

for v in 'a' .. 'z'
next if letters.values.include?(v)
letters['v'] = v if letters['v']
next if !test_combi(words,letters,mydico)

for w in 'a' .. 'z'
next if letters.values.include?(w)
letters['w'] = w if letters['w']
next if !test_combi(words,letters,mydico)

for x in 'a' .. 'z'
next if letters.values.include?(x)
letters['x'] = x if letters['x']
next if !test_combi(words,letters,mydico)

for y in 'a' .. 'z'
next if letters.values.include?(y)
letters['y'] = y if letters['y']
next if !test_combi(words,letters,mydico)

for z in 'a' .. 'z'
next if letters.values.include?(z)
letters['z'] = z if letters['z']
next if !test_combi(words,letters,mydico)

break if !letters['z']
end
letters['z']='.' if letters['z']
break if !letters['y']
end
letters['y']='.' if letters['y']
break if !letters['x']
end
letters['x']='.' if letters['x']
break if !letters['w']
end
letters['w']='.' if letters['w']
break if !letters['v']
end
letters['v']='.' if letters['v']
break if !letters['u']
end
letters['u']='.' if letters['u']
break if !letters['t']
end
letters['t']='.' if letters['t']
break if !letters['s']
end
letters['s']='.' if letters['s']
break if !letters['r']
end
letters['r']='.' if letters['r']
break if !letters['q']
end
letters['q']='.' if letters['q']
break if !letters['p']
end
letters['p']='.' if letters['p']
break if !letters['o']
end
letters['o']='.' if letters['o']
break if !letters['n']
end
letters['n']='.' if letters['n']
break if !letters['m']
end
letters['m']='.' if letters['m']
break if !letters['l']
end
letters['l']='.' if letters['l']
break if !letters['k']
end
letters['k']='.' if letters['k']
break if !letters['j']
end
letters['j']='.' if letters['n']
break if !letters['i']
end
letters['i']='.' if letters['i']
break if !letters['h']
end
letters['h']='.' if letters['h']
break if !letters['g']
end
letters['g']='.' if letters['g']
break if !letters['f']
end
letters['f']='.' if letters['f']
break if !letters['e']
end
letters['e']='.' if letters['e']
break if !letters['d']
end
letters['d']='.' if letters['d']
break if !letters['c']
end
letters['c']='.' if letters['c']
break if !letters['b']
end
letters['b']='.' if letters['b']
break if !letters['a']
end

--------------090908030201050808050200--