Given an array of numbers, find what operations will evaluate to a target value.

sum_to.rb

#
#  www.reddit.com/r/programming/comments/358tnp/five_programming_problems_every_software_engineer/
#
#  THE 5TH EXERCISE:
#
#     Write a program that outputs all possibilities to put + or - or nothing between
#     the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. 
#     For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.
#

#  While the exercise only wanted to use the numbers (1..9) and evaluating to 100,
#  I thought I'd try and solve this more generally using backtracking.
#
#  - Mike

class SumTo
  
  def find target, numbers_to_use
    @target    = target
    @numbers   = numbers_to_use.to_a
    @solutions = []
    solver
    return @solutions
  end

  def find_and_stringify target, numbers_to_use
    find(target, numbers_to_use).map do |solution|
      @numbers.zip(solution).flatten.map { |op| stringify_op op }.reduce(:+)
    end
  end

  private

  def solver ops = []
    
    # base-case: too many operations have been generated.  dead end.
    return if ops.count >= @numbers.count

    current_value = calculate(ops, @numbers)
    
    # base-case: a solution has been found!
    if current_value.eql?(@target) && ops.count.eql?(@numbers.count - 1)
      return @solutions << ops
    
    # base-case: the target value has been overshot.  dead end.
    elsif current_value > @target
      return
    end

    # explore the next operation options
    solver(ops + [:combine])
    solver(ops + [:+])
    solver(ops + [:-])
  end
end

def calculate ops, input
  eval input.to_a[0..ops.length].zip(ops).flatten.map {|op| stringify_op op }.reduce(:+)
end

def stringify_op op
  case op
  when :+
    ' + '
  when :-
    ' - '
  when :combine
    ''
  else
    op.to_s
  end
end

sum_to_spec.rb

require 'rspec'
require './sum_to'

describe SumTo do
  let(:summer) { SumTo.new }

  it 'should find a solution' do
    expect( summer.find(3, (1..2)) ).to eq([[:+]])
  end

  it 'should find_and_print a solution' do
    expect( summer.find_and_stringify(3, (1..2)) ).to eq(['1 + 2'])
  end

  it 'should print a larger solution' do
    expect( summer.find_and_stringify(100, (1..9)) ).to include('1 + 23 - 4 + 56 + 7 + 8 + 9')
  end

  it 'should work for non-sequential number cases' do
    expect( summer.find_and_stringify(123, [1,2,3,4,5,9]) ).to include('123 - 4 - 5 + 9')
  end

  it 'should work for numbers in a specific but arbitrary order' do
    expect( summer.find_and_stringify(123, [9,1,3,4,7,9]) ).to include('9 + 1 + 34 + 79')
  end
end

describe '::calculate' do

  it 'should combine two digits' do
    expect( calculate([:combine], [1, 2]) ).to eq(12)
  end

  it 'should combine three digits' do
    expect( calculate([:combine, :combine], [1, 2, 3]) ).to eq(123)
  end

  it 'should add two digits' do
    expect( calculate([:+], [1, 2]) ).to eq(1 + 2)
  end

  it 'should subtract two digits' do
    expect( calculate([:-], [1, 2]) ).to eq(1 - 2)
  end

  it 'should only return a value for the number of operations given' do
    expect( calculate([:+, :+], (1..99)) ).to eq(1 + 2 + 3)
  end

  it 'should perform a mix of combines, additions, and subtractions' do
    expect( calculate([:combine, :+, :-], [1, 2, 3, 4]) ).to eq(12 + 3 - 4)
  end
end