Please Forward: Ruby Quiz Submission

ruby-talk
1

From: James Koppel <darmaniiii@yahoo.com>
Date: June 15, 2007 11:37:34 AM CDT
To: submission@rubyquiz.com, submission@rubyquiz.com
Subject: Please Forward: Ruby Quiz Submission

Here is my solution to Ruby Quiz #128. It simply brute-forces the problem, and thus is O(n!), where n is the number of distinct letters. It took a little bit to output the correct (well, besides being in a different order due to the hash) solution to send+more=money, although on smaller problems it completed (practically) instantaneously.

Since eval does much of the work for it, it was trivial to make this solution work for any mathematical expression.

One significant speed improvement that occurred to me is to have the base case be one level of recursion higher and calculate the value of the last letter using simple algebra. However, that would yield more complex code.

def find_solution(expr)
  expr = expr.sub('=','==')
  chars =
  expr.scan(/./){|c| chars |= [c] unless "*/%+-()=".include? c}
  solution_helper chars, expr
end

def solution_helper(rem_chars, expr, rem_nums=(0..9).to_a,
    char_reps={})
  if rem_chars.empty?
    return eval(expr.gsub(/./){|c|
      (char_reps.keys.include? c) ? char_reps[c] : c}) ?
      char_reps : nil
  end

  rem_nums.each do |n|
    next if n==0 && expr =~ /(^|[*\/%+\-(=])#{rem_chars[0]}/
    s = solution_helper(rem_chars[1..-1], expr, rem_nums - [n],
      char_reps.merge({rem_chars[0]=>n}))
    return s if s
  end
  nil
end

find_solution(ARGV[0]).each_pair do |k,v|
  puts "#{k}: #{v}"
end

Choose the right car based on your needs. Check out Yahoo! Autos new Car Finder tool.

ยทยทยท

Begin forwarded message: