Created
May 8, 2015 18:06
-
-
Save zerowidth/e0141b107d7f5446d2f4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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