James Gray
6/18/2007 1:47:00 PM
Begin forwarded message:
> 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.