Triplebyte Programming Challenge

triplebyte_programming_challenge.rb

# The first 12 digits of pi are 314159265358. We can make these digits into an expression evaluating to 27182 (first 5 digits of e) as follows:

# 3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182   
# or 
# 3 + 1 - 415 * 92 + 65358 = 27182

# Notice that the order of the input digits is not changed. Operators (+,-,/, or *) are simply inserted to create the expression.  

# Write a function to take a list of numbers and a target, and return all the ways that those numbers can be formed into expressions evaluating to the target. Do not use the eval function in Python, Ruby or JavaScript

# For example: 
# f("314159265358", 27182) should print:      

# 3 + 1 - 415 * 92 + 65358 = 27182 
# 3 * 1 + 4 * 159 + 26535 + 8 = 27182 
# 3 / 1 + 4 * 159 + 26535 + 8 = 27182 
# 3 * 14 * 15 + 9 + 26535 + 8 = 27182 
# 3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182

################################

def check(sum, previous, digits, target, expr)
  if digits.length == 0
    if sum + previous == target.to_f
      puts "#{expr} = #{target}"
    end
  else
    1.upto(digits.length) do |i|
      current = digits[0...i]
      remaining = digits[i..-1]
      check(sum + previous, current.to_f, remaining, target, "#{expr} + #{current}")
      check(sum, previous * current.to_f, remaining, target, "#{expr} * #{current}")
      check(sum, previous / current.to_f, remaining, target, "#{expr} / #{current}")
      check(sum + previous, -current.to_f, remaining, target, "#{expr} - #{current}")
    end
  end
end

def f(digits, target)
  1.upto(digits.length) do |i|
    current = digits[0...i]
    remaining = digits[i..-1]
    check(0, current.to_f, remaining, target, current)
  end
end

require 'benchmark'
time = Benchmark.measure do  
  f("314159265358", 27182)
end
puts time

I found your solution very helpful. Similar to a java solution here (http://stackoverflow.com/questions/32594710/generate-all-combinations-of-mathematical-expressions-that-add-to-target-java-h). I was wondering if you can add a few comments on detailing how the program functions or works in ruby, especially for the check function.

Thanks

Thanks to Kevin for get this started. Python version here:
https://gist.github.com/STashakkori/d6d93d20f57b15df1067

I have a working C++ version here:
https://gist.github.com/chasem91/c6e5261624b7b4a0e539