Erann Gat’s Benchmark in Ruby: 11 Lines

codes = (words = File.new("words").read).downcase.gsub(/[^a-z\n]/, '');
%w{e jnq rwx dsy ft am civ bku lop ghz}.each_with_index { |g, i| codes.gsub!(/[#{g}]/, i.to_s) }
$dict = Hash.new { |hash, key| hash[key] = [] }
words.zip(codes) { |word, code| $dict[code.chomp] << " #{word.chomp}" }
def split(s) (1..s.length).each { |length| yield s[0...length], s[length..-1] } end
def match(number, out, digit = true)
  return puts(out) if number == ""
  split(number) { |pre, post| digit &= $dict[pre].each { |word| match(post, out+word) }.empty? }
  match(number[1..-1], "#{out} #{number[0..0]}", false) if digit
end
File.new("numbers").each { |number| match(number.gsub(/[^0-9]/, ''), "#{number.chomp}:") }

See here and here for the background.

11 lines of code, 1.5 hours to get a correct solution, 2 more hours to get an efficient solution, 1 more hour to minimize the number of lines.

It takes 16 seconds to crunch the sample data on a 1.67 GHz PowerPC G4.

Update:

This version drops all pretense of readability and aims for fewest lines of code (5 lines):

c=(w=IO.read("words")).upcase.delete("^A-Z\n");30.times{|i|c.gsub! "E--JNQR\
WXDSYFT-AM-CIVBKULOPGHZ"[i,1],"#{i/3}"};D=Hash.new{|h,k|h[k]=[]};w.zip(c){
|w,c|D[c.chop]<<w.chop};def m(n,o,d=true)puts o if n=="";n.size.times{|l|d&=
D[n[0..l]].each{|w|m(n[l+1..-1],o+" "+w)}==[]};m(n[1..-1],o+" "+n[0,1],nil
)if d&&n!=""end;IO.read("numbers").each{|n|m(n.delete("^0-9"),n.chop+":")}

Can you come up with a shorter version?

blog comments powered by Disqus