[QUIZ] Getting to 100 (#119)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Gavin Kistner

The NPR show "Car Talk" has regular quizzes that they call "Puzzlers"[1]. The
one listed on their web site for March 12th[2] is titled "Getting to 100". In
the quiz, you are supposed to write down the digits 1-9 in order, followed by "
= 100", and then insert between them two minus symbols and one plus symbol (in
any order) to make the formula correct. You aren't allowed to re-arrange digits,
or do some toothpick math like combine two minus signs to make a plus. You must
use every digit, and all three operators. For example, here's one incorrect
solution:

123 + 45 - 67 - 89 = 100 (This is an incorrect formula; it totals 12)

The quiz, then, is to solve this problem without thinking, instead letting the
computer think for you. Your program should output every possible equation that
can be formed, and the actual result of that equation. The equation that results
in 100 should have stars around it. At the end, you should print out the number
of formulae that were possible. Here's an excerpt of some example output:

...
12 - 34 - 567 + 89 = -500
12 - 34 + 567 - 89 = 456
12 + 34 - 567 - 89 = -610
************************
123 - 45 - 67 + 89 = 100
************************
123456 - 7 - 8 + 9 = 123450
123456 - 7 + 8 - 9 = 123448
123456 + 7 - 8 - 9 = 123446
...
168 possible equations tested

You should not print the same equation more than once. ("1 - 2 - 3 + 456789" is
the same as "1 - 2 - 3 + 456789", even if the computer thinks that the two minus
symbols come in a different order.)

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.

[1] 2007 Puzzler Index: http://www.cartalk.com/content/puzzler/2007.html
[2] http://www.cartalk.com/content/puzzler/transcripts/200711/index.html

 

[Robert Dober]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Gavin Kistner

The NPR show "Car Talk" has regular quizzes that they call "Puzzlers"[1]. The
one listed on their web site for March 12th[2] is titled "Getting to 100". In
the quiz, you are supposed to write down the digits 1-9 in order, followed by "
= 100", and then insert between them two minus symbols and one plus symbol (in
any order) to make the formula correct. You aren't allowed to re-arrange digits,
or do some toothpick math like combine two minus signs to make a plus. You must
use every digit, and all three operators. For example, here's one incorrect
solution:

123 + 45 - 67 - 89 = 100 (This is an incorrect formula; it totals 12)

The quiz, then, is to solve this problem without thinking, instead letting the
computer think for you. Your program should output every possible equation that
can be formed, and the actual result of that equation. The equation that results
in 100 should have stars around it. At the end, you should print out the number
of formulae that were possible. Here's an excerpt of some example output:

...
12 - 34 - 567 + 89 = -500
12 - 34 + 567 - 89 = 456
12 + 34 - 567 - 89 = -610
************************
123 - 45 - 67 + 89 = 100
************************
123456 - 7 - 8 + 9 = 123450
123456 - 7 + 8 - 9 = 123448
123456 + 7 - 8 - 9 = 123446
...
168 possible equations tested

You should not print the same equation more than once. ("1 - 2 - 3 + 456789" is
the same as "1 - 2 - 3 + 456789", even if the computer thinks that the two minus
symbols come in a different order.)

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)

sorry for being picky but I guess it might be useful
- an arbitrary set of operators
+ an array of operators that can come in any order
hopefully somebody will find the correct formal expression to describe
the beast ...
, and an arbitrary target number that the equation is supposed to evaluate

to.

[1] 2007 Puzzler Index: http://www.cartalk.com/content/puzzler/2007.html
[2] http://www.cartalk.com/content/puzzler/transcripts/200711/index.html

For the rest sounds like fun.

Cheers
Robert

 

[James Edward Gray II]

sorry for being picky but I guess it might be useful
- an arbitrary set of operators
+ an array of operators that can come in any order
hopefully somebody will find the correct formal expression to describe
the beast ...
, and an arbitrary target number that the equation is supposed to
evaluate

We had that quiz, though this one is definitely similar:

http://www.rubyquiz.com/quiz7.html

James Edward Gray II

 

[Kyle Schmitt]

OK only 43 hours to go...

Stupid non spoiler rule

 

[Phrogz]

OK only 43 hours to go...

Stupid non spoiler rule

Did you get all the extra credit already?

 

[Kyle Schmitt]

Everything but the arbitrary ordering and number of digits.

And it can run in O(n) time

 

[Carlos]

The NPR show "Car Talk" has regular quizzes that they call "Puzzlers"[1]. The
one listed on their web site for March 12th[2] is titled "Getting to 100". In
the quiz, you are supposed to write down the digits 1-9 in order, followed by "
= 100", and then insert between them two minus symbols and one plus symbol (in
any order) to make the formula correct. You aren't allowed to re-arrange digits,
or do some toothpick math like combine two minus signs to make a plus. You must
use every digit, and all three operators.

Can the plus and minus symbols be used as unary operators?

--

 

[Phrogz]

The NPR show "Car Talk" has regular quizzes that they call "Puzzlers"[1]. The
one listed on their web site for March 12th[2] is titled "Getting to 100". In
the quiz, you are supposed to write down the digits 1-9 in order, followed by "
= 100", and then insert between them two minus symbols and one plus symbol (in
any order) to make the formula correct. You aren't allowed to re-arrange digits,
or do some toothpick math like combine two minus signs to make a plus. You must
use every digit, and all three operators.

Can the plus and minus symbols be used as unary operators?

Not as described, in the original quiz, but I'd say...sure! It
would require that it either be applied before the first digit:
-12345 - 67 + 89
or after another operator:
123 + -45 -6789
but I don't see any reason to disallow that sort of extra logic if you
want to do it.

 

[Sebastian Hungerecker]

Can the plus and minus symbols be used as unary operators?

[...]
but I don't see any reason to disallow that sort of extra logic if you
want to do it.

Well, one reason would be that using a plus as a unary operator is the
same as not using it at all, so that would allow you to circumvent the
use-all-operators-rule.

 

[Ruben Medellin]

The three rules of Ruby Quiz:

Yay. I remember doing this exercise in math class back there in
secondary school. Not to be conceited, but I remember having so much fun
with that I tried some variations on the exercise, finding around 200
solutions or so. But, of course, I', crazy

I want to suggest some extra credits for all those crazy people put
there ;D

- You can use parenthesis to change precedence of operators (if you use
ore than addition and subtraction)
- You can use decimal dot in numbers. As for example: .1 - 2 + (3 * 4) +
5 + 6 + 78.9 = 100
- Given the set of numbers, rules and operations, say if it can yield
all numbers on a given range, or try to find the largest range possible.

Certainly I love these quizes. =D

 

[Rick DeNatale]

Here's my solution. It handles both extra credit suggestions, and
adds control over the verbosity of the output, and some options for
finding 'interesting' inputs.


I found this quiz rather easy. I had a basic solution in about 15
minutes, and spent about another half hour or so generalizing it.

The main problem was partitioning the string of digits in order to
place the operators. I did this with a recursive method on String
which iterates over the possible partitionings using block
composition.

In order to generalize the inputs I used Florian Frank's permutation
gem to get the permutations of the operators.

require 'rubygems'
require 'permutation'

class String

# yield each partitioning of the receiver into count partitions
#
# This is a recursive implementation using composition of the block argument.
#
# The approach is to iteratively split the string into two parts,
# an initial substring of increasing length, and the remainder.
# For each initial substring we yield an array which is the concatenation
# of the initial substring and the partitioning of the remainder of
the string # into count-1 partitions.
def each_partition(count, &b)
# if the count is 1 then the only partition is the entire string.
if count == 1
yield [self]
else
# Iterate over the initial substrings, the longest initial
substring must leave
# at least count-1 characters in the remaining string.
(1..(size-(count-1))).each do |initial_size|
self[initial_size..size].each_partition(count-1) {|remaining|
b.call([self[0,initial_size]] + remaining)}
end
end
end
end

# print combinations of digits and operators which evaluate to a goal
#
# Arguments are supplied by a hash the keys are:
#
# Main arguments
# :goal - the number being sought, default is 100
# :digits - a string of digits, default is "123456789"
# ps - an array of strings representing the operators to be inserted into
# digits, default is %w[- - +]
#
# Additional arguments
# :verbose - unless false, print all attempts, default is false
# :return_counts - unless false, return an array of value, count arrays for
# values with multiple solutions, used to find interesting
# inputs, default is false
def get_to(options={})
options = {
:goal => 100,
:digits => '123456789',
ps => %w[- - +],
:verbose => false,
:return_counts => false
} .merge(options)
digits= options[:digits]
goal, digits, ops, verbose, return_counts =
*options.values_atgoal, :digits, ps, :verbose, :return_counts)
operators = Permutation.for(ops).map{|perm| perm.project}.uniq
puts "Looking for #{goal}, digits=#{digits}, operators=#{ops.inspect}"
counts = Hash.new(0)
found_in_a_row = 0
digits.each_partition(ops.size + 1) do |numbers|
operators.each do |ops|
op_index = -1
eqn = numbers.zip(ops).flatten.compact.join(' ')
val = eval(eqn)
counts[val] += 1 if return_counts
found = val == goal
puts "********************************" if found_in_a_row == 0 && found
puts "********************************" unless found_in_a_row ==
0 || found
puts "#{eqn} = #{val}" if verbose || goal == val
found_in_a_row = found ? found_in_a_row + 1 : 0
end
end
return_counts ? counts.select {|key,value| value > 1} : nil
end

get_to
get_toverbose=> true)
get_togoal => 357, ps => %w[+ - +], :verbose=> true)
get_togoal => 302, :digits => '987654321')
get_togoal => 98, :verbose => true)
p get_togoal => 336)
get_togoal => -355)

 

[Marcel Ward]

My solution below uses simple recursion - hopefully it's easy to read
and understand. It meets the extra credit criteria.

Looking forward to seeing how some of the power of Ruby could be used
by others to create a more elegant solution. (I admit my solution is
a bit lacklustre!)

Thanks to Gavin & James.

# Marcel Ward <wardies ^a-t^ gmaildotcom>
# Saturday, 2006-04-07
# Solution for Ruby Quiz #119 <http://www.rubyquiz.com/>
#
################################################
# getting-to-x.rb

class GettingToX
def initialize(no_of_plusses, no_of_minusses, target_number)
@plusses = no_of_plusses
@minusses = no_of_minusses
@target = target_number
end

# Recursively called whilst preparing the calculation string,
# which is passed in calc_prefix
def prepare_sum(rem_plus, rem_minus, cur_digit, calc_prefix)
cur_digit += 1

# Do we have any remaining plus signs to use up?
if rem_plus > 0
prepare_sum(rem_plus - 1, rem_minus, cur_digit,
calc_prefix + " + %c" % (?0 + cur_digit))
end

# Do we have any remaining minus signs to use up?
if rem_minus > 0
prepare_sum(rem_plus, rem_minus - 1, cur_digit,
"#{calc_prefix} - %c" % (?0 + cur_digit))
end

digits_remaining = 10 - cur_digit
if rem_plus + rem_minus < digits_remaining
# We can use a digit here and we'll still have room to
# fit in all our operators later
prepare_sum(rem_plus, rem_minus, cur_digit,
"#{calc_prefix}%c" % (?0 + cur_digit))
elsif rem_plus + rem_minus == 0
# We have run out of operators; use up all the digits
cur_digit.upto(9) {|n| calc_prefix += "%c" % (?0 + n)}
calc(calc_prefix)
end
end

# Print out the sum (with highlights if the target value was hit).
def calc(whole_sum)
result = eval(whole_sum)
target_hit = (result == @target)
puts '*' * 30 if target_hit
puts whole_sum + ' = ' + result.to_s
puts '*' * 30 if target_hit
@total_evals += 1
@target_matches += 1 if target_hit
end

def do_sums
@total_evals = 0
@target_matches = 0
# We must always start with a string containing the first digit,
# i.e. "1" because after this comes either the next digit or +/-
prepare_sum(@plusses, @minusses, 1, '1')
puts "#{@total_evals} possible equations tested"
@target_matches
end
end

# Show results for 1 plus, 2 minusses, target of 100
x = GettingToX.new(1, 2, 100)
matches = x.do_sums

# How did we do?
puts "** #{matches} equation(s) matched target value **"

 

[Kyle Schmitt]

My submission uses extreme (in)elegance in accordance with this
weeks quiz saying "don't think, let the computer think for you"

I'm submitting several versions, one full version that includes the
extra credit, and several "golf" versions

Enjoy!

--Kyle

First we have this version
#########begin########### 42 lines long
elegance = nil

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

to100 = Hash.new()

@setlength=9#set, starting from 1 to use

@maxops=@setlength-1#the maximum number of operators (including space)
in any equation

@operator = ["", "+", "-"]

@oplength = @operator.length

keylength = @oplength.power!(@maxops)



def bogoGen()

little=Array.new(@setlength+@maxops) do

|i|

if i.modulo(2)==0 then

i=i/2

i+=1

else

i=@operator[rand(@oplength)]

end

end

return(little.join)

end



writingHamlet = Time.now()



while to100.keys.length<keylength

elegance = bogoGen()

to100.store(elegance,eval(elegance))

#puts "Found #{to100.keys.length} formulas" if to100.keys.length%100==0

end



millionMonkeys = Time.now()



to100.sort.each do

|answer|

fortytwo=answer[1]==100?'*':' '

#display the answer!

puts "#{fortytwo} #{answer[0]}=#{answer[1]} #{fortytwo}"

end



willFinish = Time.now()

#puts "Total calculation time: #{millionMonkeys - writingHamlet} seconds"

#puts "Total run time: #{willFinish - writingHamlet} seconds"
#####end ######




#compact v1
t={}

while t.length<(6561)

e = Array.new(17){|i| i=i%2==0?i/2+1:["","+","-"][rand(3)]}.join

t.store(e,eval(e))

end

t.sort.each {|a| f=a[1]==100?'*':' '; puts "#{f} #{a[0]}=#{a[1]} #{f}"}

#compact v2
t={}

while t.length<(6561)

t.store(Array.new(17){|i| i=i%2==0?i/2+1:["","+","-"][rand(3)]}.join,'')

end

t.sort.each {|a| f=eval(a[0])==100?'*':' '; puts "#{f}
#{a[0]}=#{eval(a[0])} #{f}"}

#compact v3
t=Array.new(6561){|i|i}

t.each_index{|a| while t[a]=Array.new(17){|i|
i=i%2==0?i/2+1:["","+","-"][rand(3)]}.join and not
t.length==t.uniq.length;end}

t.sort.each {|a| f=eval(a)==100?'*':' '; puts "#{f} #{a}=#{eval(a)} #{f}"}

 

[Ryan Leavengood]

Here is my solution. Again I've used Test::Unit to test my solution,
as well as providing a fairly nice command-line operation. I too did
the extra credit (I actually coded it that from the beginning, seemed
easy enough.)

I borrowed some code for the operator permutations, but after writing
my own code to create the numerical groups for the equations I
wondered if it might be possible to use one basic algorithm for both.
But I don't have time to fix this up at the moment. I may submit
another solution later this week.

# Based on:
# http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/139290
# Author: Endy Tjahjono
class String
def perm
return [self] if self.length < 2
ret = []

0.upto(self.length - 1) do |n|
rest = self.split(//u) # for UTF-8 encoded strings
picked = rest.delete_at(n)
rest.join.perm.each { |x| ret << picked + x }
end

ret
end
end

# All the rest is Ryan Leavengood code
class EquationSolver
attr_reader :num_seq, perators, :result

def initialize(num_seq = "123456789", operators = "--+", result_wanted = 100)
@num_seq, @operators, @result_wanted = num_seq, operators, result_wanted
end

SEP = '*' * 24

def solve
equations = 0
ops = op_combinations(@operators).map{|a| a.split('')}
generate_groups(@num_seq).each do |group|
ops.each do |op|
eq = group.zip(op).join(' ')
result = eval(eq)
puts SEP if result == @result_wanted
puts "#{eq}= #{result}"
puts SEP if result == @result_wanted
equations += 1
end
end
puts "#{equations} possible equations tested"
end

def op_combinations(operators)
operators.perm.uniq
end

# Returns an array of numeric strings representing how the given
# number can be split into the given number of groups
def num_split(number, num_groups)
return [number.to_s] if num_groups == 1
return ["1" * num_groups] if number == num_groups
result = []
((number + 1)-num_groups).times do |i|
cur_num = i + 1
num_split(number - cur_num, num_groups - 1).each do |group|
result << "#{cur_num}#{group}"
end
end
result
end

def generate_groups(num_seq, num_groups = @operators.length+1)
num_split(num_seq.length, num_groups).map do |split_on|
# Turn the result from num_split into a regular expression,
# with each number becoming grouped dots
reg_exp = split_on.split('').map{|n| "(#{'.' * n.to_i})"}.join
num_seq.scan(/#{reg_exp}/).first
end
end
end

require 'test/unit'

class SolverTester < Test::Unit::TestCase
def setup
@es = EquationSolver.new
end

def test_string_perm
assert_equal(["1"],
"1".perm)
assert_equal(["12","21"],
"12".perm)
assert_equal(["123", "132", "213", "231", "312", "321"],
"123".perm)
end

def test_op_combinations
assert_equal(["1"],
@es.op_combinations("1"))
assert_equal(["12","21"],
@es.op_combinations("12"))
assert_equal(["123", "132", "213", "231", "312", "321"],
@es.op_combinations("123"))
assert_equal(["223", "232", "322"],
@es.op_combinations("223"))
assert_equal(["--+", "-+-", "+--"],
@es.op_combinations("--+"))
end

def test_num_split
assert_equal(["11"],
@es.num_split(2,2))
assert_equal(["111"],
@es.num_split(3,3))
assert_equal(["12", "21"],
@es.num_split(3,2))
assert_equal(["13", "22", "31"],
@es.num_split(4,2))
assert_equal(["112", "121", "211"],
@es.num_split(4,3))
end

def test_generate_groups
assert_equal([["1", "2", "34"], ["1", "23", "4"], ["12", "3", "4"]],
@es.generate_groups("1234", 3))
end
end

if $0 == __FILE__
# By default do not run the test cases
Test::Unit.run = true

if ARGV.length > 0
if ARGV[0] == 'ut'
# Run the test cases
Test::Unit.run = false
else
begin
if ARGV.length != 3
raise
else
if ARGV[0] =~ /^\d*$/ and
ARGV[1] =~ /^[\+\-\*\/]*$/ and
ARGV[2] =~ /^-?\d*$/

EquationSolver.new(ARGV[0], ARGV[1], ARGV[2].to_i).solve
else
raise
end
end
rescue
puts "Usage: #$0 <number sequence> <string of operators>
<result wanted>"
puts "\tOr just the single parameter 'ut' to run the test cases."
exit(1)
end
end
else
# Solve the default case
EquationSolver.new.solve
end
end
__END__

Regards,
Ryan

 

[Kyle Schmitt]

Ohh yea, and despite the evilness of my implementation it does, in
fact, run in a reasonable amount of time. I averaged 100 seconds for
the full version and only 10 minutes for the last, most compact, golf
version.

--Kyle

 

[Ryan Leavengood]

Ohh yea, and despite the evilness of my implementation it does, in
fact, run in a reasonable amount of time. I averaged 100 seconds for
the full version and only 10 minutes for the last, most compact, golf
version.

Hahaha, yeah I tried running the last one and gave up. You might want
to explain what these are doing, as it isn't exactly obvious.

But in general I would think if it takes the computer 10 minutes to
solve, you might as well do it yourself (or rewrite your algorithm

Ryan

 

[Kyle Schmitt]

It's using an algorithm based on a bogosort to generate the equation
the hash based implementations run reasonably quick. The array based
one has to check for uniqueness each time, so it's rather poor
performance wise.

Basically
123456789 is interspersed with " " + and - randomly, inserted into the
hash and repeated until the size of the hash is 8^3 (which is the
number of unique formulas)

It's not written for speed, it's written for the computer to do all
the work, and the programmer to be well.. lazy!

--Kyle

 

[Ken Bloom]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz
until 48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone on Ruby Talk follow the discussion. Please reply to the
original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- =-=-=-=-=

by Gavin Kistner

The NPR show "Car Talk" has regular quizzes that they call
"Puzzlers"[1]. The one listed on their web site for March 12th[2] is
titled "Getting to 100". In the quiz, you are supposed to write down the
digits 1-9 in order, followed by " = 100", and then insert between them
two minus symbols and one plus symbol (in any order) to make the formula
correct. You aren't allowed to re-arrange digits, or do some toothpick
math like combine two minus signs to make a plus. You must use every
digit, and all three operators. For example, here's one incorrect
solution:

123 + 45 - 67 - 89 = 100 (This is an incorrect formula; it totals 12)

The quiz, then, is to solve this problem without thinking, instead
letting the computer think for you. Your program should output every
possible equation that can be formed, and the actual result of that
equation. The equation that results in 100 should have stars around it.
At the end, you should print out the number of formulae that were
possible. Here's an excerpt of some example output:

...
12 - 34 - 567 + 89 = -500
12 - 34 + 567 - 89 = 456
12 + 34 - 567 - 89 = -610
************************
123 - 45 - 67 + 89 = 100
************************
123456 - 7 - 8 + 9 = 123450
123456 - 7 + 8 - 9 = 123448
123456 + 7 - 8 - 9 = 123446
...
168 possible equations tested

You should not print the same equation more than once. ("1 - 2 - 3 +
456789" is the same as "1 - 2 - 3 + 456789", even if the computer thinks
that the two minus symbols come in a different order.)

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.

[1] 2007 Puzzler Index:
http://www.cartalk.com/content/puzzler/2007.html [2]
http://www.cartalk.com/content/puzzler/transcripts/200711/

index.html

#!/usr/bin/env ruby

#requires are only necessary to construct the
#operator permutation table from the list of operators
#if you want to hard code that (and not do the extra credit)
#then no extra libraries are necessary
require 'rubygems'
require_gem 'facets'
require 'facets/core/enumerable/permutation'
require 'enumerator'

Digits= (ARGV.shift || "123456789").split(//)
RequestedResult=(ARGV.shift || 100).to_i
rawoperators=(ARGV.shift || "+--")

#construct the operator permutation table from the list of operators
Operators=rawoperators.split(//).map{|x| " #{x} "}
OperatorPerms=Enumerable::Enumerator.new(Operators,:each_permutation).
map{|p| p}.uniq

class Array

#Yields all partitionings of the array which have +num+ partitions
#and retain the order of the elements
#
#To relax the ordering constraint, use this in combination
#with Enumerable#each_permutation
def each_partition num
if num==1
yield [self]
return self
end
(0..length-num).each do |x|
firstset=self[0..x]
self[(x+1)..-1].each_partition(num-1) do |y|
yield [firstset,*y]
end
end
return self
end
end

#The actual solution to the problem
counter=0
found=0
Digits.each_partition(Operators.length+1) do |digitspart|
OperatorPerms.each do |operatorsperm|
counter+=1
expression=digitspart.zip(operatorsperm).flatten.join
result=eval(expression)
puts "************************" if RequestedResult==result
puts "#{expression} = #{result}"
puts "************************" if RequestedResult==result
found+=1 if RequestedResult==result
end
end
puts "#{counter} possible equations tested"
puts "#{found} equation(s) equaled #{RequestedResult}"

 

[Robert Dober]

Here goes my solution for another nice quiz, yes I know I repeat myself.
It should get all the extras plus one extra from the last quiz, the
fuzzy solutions.

Cheers
Robert
Defaults = { fuzz => 0, target => 100, digits => [*1..9], ops
=> [ :-, :- , :+ ] }

### Override the default values if you want .
Defaults.each do
| key, value |
instance_variable_set "#{key}", value
end # Configurable.each do
### If you are really serious about overriding the default values do it
### again .
@ops.map!{|o| " #{o} "}
class Array
def each_with_rest
each_with_index do
| ele, i |
yield ele, self[0, i] + self[i+1..-1]
end
end # each_with_rest
def runtempatios
return [[]] if empty?
remps = []
each_with_rest do
| ele, rest |
remps += rest.runtempatios.map{ | p | p.unshift(ele) }
end # each_with_rest do
remps.uniq
end # def runtempatios
end

# My wife does not like it very much when I am slicing the bread, the
slices are of
# very variable thickness!!!
# A long earned skill that I can eventually put to work now
def _slices outer, inner
## In order to be able to slice we have to assure that outer.size > inner.size
return [ outer ] if inner.empty?
r = []
(outer.size-inner.size+1).times do
|i|
_slices( outer[i+1..-1], inner[1..-1] ).each do
| slice |
r << outer[0,i.succ] + inner[0..0] + slice
end # slices( outer[i+2..-1], rest ).each do
end # (outer.size-inner.size).times do
r
end

def slices outer, inner
_slices( outer, inner ).reject{|s| inner.include? s.last }
end

@count = 0
@total = 0
@target = (@target-@fuzz .. @target+@fuzz)
@ops.runtempatios.each do
| ops |
slices( @digits, ops ).each do
| expression |
e = expression.join
value = eval e
e << " = #{value}"
if @target === value then
@count += 1
puts e.gsub(/./,"*")
puts e
puts e.gsub(/./,"*")
else
puts e
end
@total += 1
end # slices( @digits, ops ).each do
end # @ops.runtempatios.each do
puts "="*72
puts "There were #{@count} solutions of a total of #{@total} tested"

 

[Ken Bloom]

=begin

I did not intent to seriously submit this solution, but it can be
helpful as an example of how to use Ruby to solve a problem quickly
without thinking too much or locating Knuth on the bookshelve. Writing
this code took maybe ten minutes and happened step-by-step with checking
the immediate results.

Since there are only 168 solutions (254 if you allow a sign before the
first digit), brute-forcing is the simplest thing one can do. Additional
operations can be added by changing the base and mapping the digits onto
further operations. (Different digit order is not that easy to
implement and maybe be futile to do with brute-forcing.) =end

(00000000..'22222222'.to_i(3)).map { |x| x.to_s(3).rjust(8, "0").
tr('012', '-+ ') }.
find_all { |x| x.count("-") == 2 and x.count("+") == 1 }.

A less ram-intensive version of this would swap the map and find_all
calls as follows:

(00000000..'22222222'.to_i(3)).
find_all { |x| x.to_s(3).count("0") == 2 and
x.to_s(3).count("1") == 1 }.
map { |x| x.to_s(3).tr('012', '-+ ').rjust(8," ")}.

(It doesn't keep maintain references to the bad combinations of
operators, allowing the GC to reclaim them earlier.)

map { |x|
t = "1" + x.split(//).zip((2..9).to_a).join.delete(" ") [eval(t), t]
}.sort.each { |s, x|
puts "*****************" if s == 100
puts "#{x}: #{s}"
puts "*****************" if s == 100
}

__END__

2#787<p4>lilith:~/mess/current$ ruby quiz119.rb |grep -C4 100$
123-456-7+89: -251
123+45-67-89: 12
123-45+67-89: 56
*****************
123-45-67+89: 100
*****************
12+345-67-89: 201
1-234+567-89: 245
1-23-456+789: 311

I like this answer a lot. Think you could generalize it to the extra
credit?