Cedric Foll
1/6/2005 2:12:00 PM
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.
#!/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