145 Puzzle

I've just started reading a blog Praxis that features programming problems to solve and shows their solutions typically in scheme. You're encouraged to submit your own solutions there to for others to look examine. The ones that come from Bonsai Code in Haskell are nothing short of amazing in their brevity.

Anyway, one I've solved is the 145 puzzle. Here's the description from Praxis ...

Form all the arithmetic expressions that consist of the digits one through nine, in order, with a plus-sign, a times-sign, or a null character interpolated between each pair of digits; for instance, 12+34*56+7*89 is a valid expression that evaluates to 2539. What number is the most frequent result of evaluating all possible arithmetic expressions formed as described above? How many times does it occur? What are the expressions that evaluate to that result?

.

So here's my solution in Ruby:

#
# Consider this math puzzle:

# Form all the arithmetic expressions that consist of the digits one through
# nine, in order, with a plus-sign, a times-sign, or a null character
# interpolated between each pair of digits; for instance, 12+34*56+7*89 is a
# valid expression that evaluates to 2539. What number is the most frequent
# result of evaluating all possible arithmetic expressions formed as
# described above? How many times does it occur? What are the expressions
# that evaluate to that result?
# 
# Your task is to answer the three questions. When you are finished, you are
# welcome to read or run a suggested solution, or to post your own solution or
# discuss the exercise in the comments below. 

# Multi-combination. Takes the elements to combine, a "level" (how many ways
# will we do the combination), the current multi-combination, and a block that
# we'll yield to.
def mc(elements, level, current=[], &block)
    elements.each do | e |
        if level == 1 then
            yield current << e
        else
            mc(elements, level-1, current << e, &block)
        end
        current.pop
    end
end

# Main program.
digits = ['1', '2', '3', '4', '5', '6', '7', '8', '9']

# DON'T initialize the hash with "[]" (as I initially did). You'll end up with
# the same array in every hash position.
results = Hash.new()

# Generate each multi-combination in the 8 spots (between each of the digits.
mc(['*', '+', ''], 8) do | operators | 

    # Initialize the string to evaluate.
    eval_string = ''

    # Add the digits and operators to the eval_string.
    0.upto(digits.length-2) { |i| eval_string << digits[i] << operators[i] }

    # Add teh final digit.
    eval_string << digits.last

    # Evaluate the string and save the result in the hash. Create a new array
    # if one doesn't exist at this position.
    (results[eval(eval_string)] ||= []) << eval_string
end

# Get the results that occur the most times.
m = results.max { |a, b| a[1].length <=> b[1].length }

# Print out the answer.
puts "Most evaluated number = #{m[0]} Number of times evaluated = #{m[1].length} values = #{m[1]}"

Let me know if you have questions and take some time to explore Praxis and solve some of the problems yourself.