Forum: Ruby Re: Getting to 100 (#119)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Af67824baa024e77966c5521589d95e9?d=identicon&s=25 Harrison Reiser (Guest)
on 2007-04-09 01:13
(Received via mailing list)
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.

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.

#########################

#!/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"
This topic is locked and can not be replied to.