hundreds.rb

# From https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour
# 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.

# Hacky version:
["", "+", "-"].repeated_permutation(8).each do |operations|
  string = (2..9).zip(operations).reduce("1") do |str, (operand, operator)|
    "#{str}#{operator}#{operand}"
  end
  puts "#{string} = 100" if eval(string) == 100
end

puts "---"

# Less hacky version:

def insert(ast, operator, operand)
  op, left, right = ast
  if operator == :dot
    if right && op != :dot
      [op, left, insert(right, operator, operand)]
    else
      [operator, ast, operand]
    end
  else
    [operator, ast, operand]
  end
end

def evaluate(ast)
  op, left, right = ast
  case op
  when Integer
    op
  when :dot
    (evaluate(left) * 10) + evaluate(right)
  when :add
    evaluate(left) + evaluate(right)
  when :sub
    evaluate(left) - evaluate(right)
  end
end

def stringify(ast)
  op, left, right = ast
  case op
  when :dot
    stringify(left) + stringify(right)
  when :add
    stringify(left) + "+" + stringify(right)
  when :sub
    stringify(left) + "-" + stringify(right)
  else
    op.to_s
  end
end

def search(numbers, matching)
  [:dot, :add, :sub].repeated_permutation(numbers.length - 1).each do |operations|
    tree = operations.zip(numbers[1..-1]).reduce([numbers.first]) do |ast, (operator, operand)|
      insert(ast, operator, operand)
    end

    string = stringify(tree)
    value  = evaluate(tree)
    puts "#{string} = #{value}" if value == matching
  end
end


search (1..9).to_a, 100