Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.