I got a bit carried away with this one; it has the extra credit along
with three on/off switches. I even wrote a little combinatorics
library (attached) to go with it, which has quite a few more functions
than I needed, including two string permutors, and an algorithm I
borrowed from the ASPN Python Cookbook.
As yet another demonstration of the benefits of convention over
configuration, the array and string permutors had almost no
difference; I only had to change 'each' to 'each_byte'.
Note that it doesn't print every equation it tests, as the extra
switches make it possible to produce millions of possibilities. To
have it solve the original example, use either of the following
commands:
ruby -- ./ruby119.rb -R 123456789--+=100
./ruby119.rb -R 123456789--+=100
Anyway, here it is. Beware of cheap hacks.
quiz119.rb (3.42 KB)
combinatorics.rb (4.39 KB)
ยทยทยท
On Apr 6, 6:55 am, Ruby Quiz <j...@grayproductions.net> wrote:
Extra Credit: Write your program to accept an arbitrary number and
ordering of digits, an arbitrary set of operators (but allowing the
same operator more than once), and an arbitrary target number that
the equation is supposed to evaluate to.
#########################
#!/usr/bin/env ruby -w
# ruby119.rb -- solves combinatorial arithmetic puzzles
# Released 2007 with no license by Harrison Reiser
require 'combinatorics'
require 'getoptlong'
def dispense_advice
puts "Usage: #{$0} [OPTIONS] digits ops = sum"
puts " e.g. #{$0} 123456789 + - - = 100"
puts "equiv: #{$0} 123 - 45 - 67 + 89 = 100"
puts
puts "Will attempt to search for a combination of the digits and"
puts "operators given that produce the sum. Each solution uses"
puts "each digit once and includes all given operator types."
puts
puts "Operators recognized: +, -, *, /, . (decimal point)"
puts "Standard operator precedence is used: (*, /) over (+, -)"
puts
puts "Options:"
puts " --help, -h"
puts " Shows this message."
puts " --permute-digits, -p"
puts " Allows the given digits to be combined arbitrarily."
puts " --no-permute-digits, -P"
puts " Maintains the given order of the digits. (default)"
puts " --repeat-ops, -r"
puts " Uses arbitrary (1..*) operator multiplicity. (default)"
puts " --no-repeat-ops, -R"
puts " Maintains each of the given operators' multiplicities."
puts " --unary-minus, -n"
puts " Allows the use of '-' as negation of the first number."
puts " --no-unary-minus, -N"
puts " Disallows the use of the negation operator. (default)"
exit
end
opts = GetoptLong.new(
['--help', '-h', GetoptLong::NO_ARGUMENT],
['--permute-digits', '-p', GetoptLong::NO_ARGUMENT],
['--no-permute-digits', '-P', GetoptLong::NO_ARGUMENT],
['--repeat-ops', '-r', GetoptLong::NO_ARGUMENT],
['--no-repeat-ops', '-R', GetoptLong::NO_ARGUMENT],
['--unary-minus', '-n', GetoptLong::NO_ARGUMENT],
['--no-unary-minus', '-N', GetoptLong::NO_ARGUMENT]
)
repeat_ops = true
unary_minus = false
permute_digits = false
opts.each do |opt, arg|
case opt
when '--help'
dispense_advice
when '--permute-digits'
permute_digits = true
when '--no-permute-digits'
permute_digits = false
when '--repeat-ops'
repeat_ops = true
when '--no-repeat-ops'
repeat_ops = false
when '--unary-minus'
unary_minus = true
when '--no-unary-minus'
unary_minus = false
end
end
dispense_advice if ARGV.length == 0
digits =
operators =
arg_str, sum = ARGV.join.split(/=/)
sum = sum.to_i
dispense_advice if sum == 0
arg_str.each_byte do |byte|
case byte
when ?0..?9
digits << byte.chr
when ?-, ?+, ?*, ?/
operators << byte.chr
else
dispense_advice
end
end
operators.uniq! if repeat_ops
count = 0
hits = 0
ops_send_args = repeat_ops ? [:each_tuple, 0] : [:each_unique_permutation]
digits_message = permute_digits ? :each_partition : :each_ordered_partition
digits.send(digits_message) do |part|
next unless repeat_ops or part.length == operators.length + 1
part = part.map { |x| x.join } if part.first.respond_to?(:join)
ops_send_args[1] = part.length - 1 if repeat_ops
operators.send(*ops_send_args) do |tuple|
expr = part.zip(tuple).join(' ')
if eval(expr.gsub(/ (\d*) /, ' \1.0 ').gsub(' . ', '.')) == sum
puts "#{expr}= #{sum}"
hits += 1
end
count += 1
if unary_minus and operators.include?('-')
num = part[0].to_i
part[0] = (-num).to_i
redo if num > 0
end
end
if permute_digits
part << part.shift
redo unless part.first == part.min
end
end
print "#{count} equation#{count == 1 ? '' : 's'} searched, ",
"#{hits} solution#{hits == 1 ? '' : 's'} found.\n"