# Forum: Ruby 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.
on 2007-04-06 14:57
```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
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...```
on 2007-04-06 15:33
```On 4/6/07, Ruby Quiz <james@grayproductions.net> wrote:
>
> the quiz, you are supposed to write down the digits 1-9 in order, followed by "
> can be formed, and the actual result of that equation. The equation that results
>         123456 - 7 - 8 + 9 = 123450
> 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...
>
>
For the rest sounds like fun.

Cheers
Robert```
on 2007-04-06 15:47
```On Apr 6, 2007, at 8:32 AM, Robert Dober wrote:

> 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```
on 2007-04-06 20:12
```OK only 43 hours to go...

Stupid non spoiler rule```
on 2007-04-06 20:31
```On Apr 6, 12:11 pm, "Kyle Schmitt" <kyleaschm...@gmail.com> wrote:
> OK only 43 hours to go...
>
> Stupid non spoiler rule

Did you get all the extra credit already?```
on 2007-04-06 20:43
```Everything but the arbitrary ordering and number of digits.

And it can run in O(n) time
;)```
on 2007-04-06 21:54
```[Ruby Quiz <james@grayproductions.net>, 2007-04-06 14.55 CEST]
[...]
> 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?```
on 2007-04-06 23:01
```On Apr 6, 1:53 pm, Carlos <a...@quovadis.com.ar> wrote:
>
> 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.```
on 2007-04-06 23:08
```Phrogz wrote:
> On Apr 6, 1:53 pm, Carlos <a...@quovadis.com.ar> wrote:

> > 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.```
on 2007-04-07 07:38
```James Gray wrote:
> 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 :D

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
- 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```
on 2007-04-08 15:55
```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"
#    :ops - an array of strings representing the operators to be
inserted into
#           digits, default is %w[- - +]
#
#    :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',
:ops => %w[- - +],
:verbose => false,
:return_counts => false
} .merge(options)
digits= options[:digits]
goal, digits, ops, verbose, return_counts =
*options.values_at(:goal, :digits, :ops, :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_to(:verbose=> true)
get_to(:goal => 357, :ops => %w[+ - +], :verbose=> true)
get_to(:goal => 302, :digits => '987654321')
get_to(:goal => 98, :verbose => true)
p get_to(:goal => 336)
get_to(:goal => -355)

--
Rick DeNatale

My blog on Ruby
on 2007-04-08 16:18
```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 **"```
on 2007-04-08 16:26
```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

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}"}```
on 2007-04-08 16:27
```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:
# 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

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```
on 2007-04-08 16:47
```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```
on 2007-04-08 16:56
```On 4/8/07, Kyle Schmitt <kyleaschmitt@gmail.com> wrote:
> 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```
on 2007-04-08 17:04
```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```
on 2007-04-08 17:40
```On Fri, 06 Apr 2007 21:55:37 +0900, Ruby Quiz wrote:

>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps
> original quiz message, if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=
> 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)
>   12 - 34 + 567 - 89 = 456
> You should not print the same equation more than once. ("1 - 2 - 3 +
>   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}"```
on 2007-04-08 18:39
```=begin
> The quiz, then, is to solve this problem without thinking, instead
> letting the computer think for you.

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.
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 }.
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```
on 2007-04-08 20:10
```This solution does the extra credit -- at least for binary operators
that are meaningful to ruby eval. It seemed easier to do the extra
credit than not.

The fact that the string of digits keeps its order makes this problem
much simpler. You don't need to find all of the permutations of
digits; you just need to iterate over the string to insert the
operators at each legal position in each unique permutation. This
solution does that recursively -- which is hopefully easier to
understand from looking at insert_ops, which does most of the work,
than by putting it into words.

#!/usr/bin/env ruby
#

require 'permutation'

class EqGenerator
def initialize(digits, operators, result)
@digits = digits
@operators = operators
@result = result
end

def solve
# create array of possible solutions, then print, testing
against desired result as we go
correct = 0
@eqs = permute_ops(@operators).collect { |o| insert_ops(@digits,
o) }.flatten
@eqs.each do |e|
res = eval(e)
if (res == @result)
correct += 1
puts "***#{e}=#{res}***"
else
puts "#{e}=#{res}"
end
end
puts "A total of #{@eqs.length} equations were tested, of which #
{correct} " + ((correct == 1)? "was": "were") + " correct"
end

private
def permute_ops(ops)
# use gem from <http://permutation.rubyforge.org/> to get unique
permutations of operators and return as array
perm = Permutation.new(ops.length)
return perm.map { |p| p.project(ops) }.uniq
end

def insert_ops(digs, ops)
res = Array.new
# if only one op to insert, just put it in each available spot
and return array of equations
if ops.length == 1 then
0.upto(digs.length-2) { |i| res << digs[0..i] + ops + digs[i
+1..digs.length]}
# if more than 1 op, for each legal placement of first op:
recursively calculate placements for other ops and digits, then
prepend first op
else
0.upto(digs.length - (ops.length+1)) { |i| res << insert_ops
(digs[i+1..digs.length], ops[1..ops.length]).collect { |e| digs[0..i]
+ ops[0..0] + e } }
end
return res.flatten
end

end

eg = EqGenerator.new("123456789", "--+", 100)
eg.solve

........................................................................
............................
John Browning```
on 2007-04-08 20:25
```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"```
on 2007-04-08 20:41
```On Mon, 09 Apr 2007 01:39:19 +0900, Christian Neukirchen wrote:

> 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.)

> 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?```
on 2007-04-08 22:10
```On Sun, 08 Apr 2007 23:25:14 +0900, Kyle Schmitt wrote:

> First we have this version
>
>   little=Array.new(@setlength+@maxops) do
>
>
>
>
> end
>
>   t.store(e,eval(e))
>   t.store(Array.new(17){|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}"}

For those reading along, the magic number 6560=='22222222'.to_i(3)
His goal is to just generate 6560 different combinations of the
operators
using a random generator.

One should note that this technically violates the rules of code golf
which require the solution to terminate within a short period of time (I
believe 4 seconds), so that its correctness can be verified
automatically
without having to worry about DOS attacks.```
on 2007-04-08 22:20
```On 4/8/07, Christian Neukirchen <chneukirchen@gmail.com> wrote:
>     puts "*****************" if s == 100
>   }

That's brilliant. It took me a minute to figure out how it worked, but I
like.

I started working on a generalized solution using this algorithm, but
it gets tricky. It isn't too hard to generalize the number sequence,
but generalizing the operators really makes it messy.

Ryan```
on 2007-04-08 22:49
```On 4/8/07, Ryan Leavengood <leavengood@gmail.com> wrote:
>
> I started working on a generalized solution using this algorithm, but
> it gets tricky. It isn't too hard to generalize the number sequence,
> but generalizing the operators really makes it messy.

OK, I figured out the generalized solution based on Christian's
submission:

seq = ARGV[0]
ops = ARGV[1]
res = ARGV[2].to_i
uops = ops.split('').uniq
print (0..(uops.length.to_s * (seq.length-1)).to_i(uops.length+1)).
map { |x| x.to_s(uops.length+1).rjust((seq.length-1), '0').
tr('012345', uops.join.ljust(6, ' ')) }.
find_all { |x| uops.inject(true){|b, op| b and (x.count(op) ==
ops.count(op))} }.
map { |x|
t = seq[0,1] + x.split('').zip(seq[1..-1].split('')).join.delete(' ')
[eval(t), t]
}.each { |s, x|
puts "*****************" if s == res
puts "#{x}: #{s}"
puts "*****************" if s == res
}.size
puts " possible equations tested"

This supports any arbitrary sequence of numbers, up to 5 different
operators in whatever combination, and whatever result. It gets slower

This was fun, but I can just see how slow it is, especially with the

As you can see I also added printing how many equations were tested.

Ryan```
on 2007-04-09 00:00
```here is my first pass:

class Array
def combinations(n)
case n
when 0: []
when 1: self.map { |e| [e] }
when size: [self]
else
(0..(size - n)).to_a.inject([]) do |mem,i|
mem += self[(i+1)..size].combinations(n-1).map do |rest|
[self[i],*rest]
end
end
end
end
end

equations = 0
separator = "************************"

(1..8).to_a.combinations(3).each do |partitions|
3.times do |n|
equation = "123456789"

partitions.reverse.each_with_index do |partition,index|
equation = equation.insert(partition, (index == n ? ' + ' : ' -
'))
end

result = eval(equation)
equation << " = #{result}"

if result == 100
equation = "#{separator}\n#{equation}\n#{separator}"
end

puts equation

equations += 1
end
end

puts "#{equations} possible equations tested"```
on 2007-04-09 00:13
```After going back and reading the current solutions, I like Ken Bloom's
each_partition method.  It's much cleaner than my combinations method.```
on 2007-04-09 04:15
```#!/usr/bin/ruby
#
# Q119 Solution by Sergey Volkov
# Accept
#   - an arbitrary number and ordering of digits,
#   - an arbitrary set of operators (but allowing
#     the same operator more than once),
#   - an arbitrary target number
# Output every possible equation that can be formed,
# and the actual result of that equation.
# The equation that results in target number have
# stars around it.
# At the end, print out the number of formulae
# that were possible.
#
require 'rubygems'
require 'facets/core/enumerable/permutation'

# all possible unique permutations
def op_seqs a
res = Hash.new
a.each_permutation{ |pe|
res[pe] = true
}
res.keys
end

# generate all expressions without reordering,
# recursive implementation;
# I could have implemented Array#each_incut( arr )
# to get more generic solution, but I'm too lazy..
# Will it be better to avoid recursion?
# Not required for this quiz, but must for generic method.
# Does anybody knows elegant nonrecursive implementation? Please show
me.
def incut_all digs, opcs, scurr='', &block
if digs.empty? || opcs.empty?
# result string
block[ %/#{scurr}#{digs}#{opcs.pack('C*')}/ ]
return
end
# extend with digit
incut_all digs[1..-1], opcs, scurr+digs[0].to_s, &block
# extend with operator
incut_all digs, opcs[1..-1], scurr+opcs[0].chr, &block
end

# output all possible equations
def show_all digits, opers, target
# validate arguments
a_digs = digits.scan(/./).map{ |d| Integer( d ) }
fail "invalid operator, only [-, +, *, /] allowed" unless %r|^[-
+*/]+| =~ opers
a_ops  = opers.unpack('C*')
n_targ = Integer( target )

count = 0 # equation counter
# operators char set
op_cs = %/[#{ Regexp.quote a_ops.uniq.pack('C*') }]/
# Regexp for 'incorrect' expression
for op_seq in op_seqs( a_ops )
incut_all( a_digs, op_seq ){ |exp|
# beautify expression
exp.gsub!( %r/#{op_cs}/, %q/ \0 / )
# evaluate expression
next unless val = eval( exp ) rescue nil
s = %/#{exp} = #{val}/
sep = (val == n_targ) && '*'*s.size
puts sep if sep
puts s
puts sep if sep
count += 1
}
end
puts %/#{count} possible equations tested/
end

# Arguments accepted:
# an arbitrary number and ordering of digits
digits = ARGV[0] || '123456789'
# an arbitrary set of operators (but allowing the same operator more
than once)
opers  = ARGV[1] || '+--'
# an arbitrary target number
target = ARGV[2] || 100

# Output all possible equations
show_all( digits, opers, target )
exit

#=================================================

> L:\Ruby\bin\ruby.exe -w L:\rb\Quiz\Q119.rb
...
123-456-7+89 = -251
123-45-678+9 = -591
******************
123-45-67+89 = 100
******************
123-45-6+789 = 861
123-4-5678+9 = -5550
...
168 possible equations tested```
on 2007-04-09 05:10
```My first quiz attempt ever so go easy on me :)

>From looking at the submissions so far it seems like my solution is
quite verbose but I am proud to have a solution that works! (Extra
Credit Too)

#file permutate.rb
module Permutate

def Permutate.generate(n)
permutations = Array.new
perm = Array.new

#first permutation
(1..n).each{|i|
perm << i
}

#  print "#{perm}\n"
permutations << perm.to_s

(2..(fact(n))).each do |i|
m = n - 2

while (perm[m] > perm[m+1])
m = m - 1
end
k = n - 1

while perm[m] > perm[k]
k = k - 1
end
swap(perm,m,k)
p = m + 1
q = n - 1
while p < q
swap(perm,p,q)
p = p + 1
q = q - 1
end
#    print "#{perm}\n"
permutations << perm.to_s
end
permutations
end

def Permutate.swap(array, a, b)
temp = array[a]
array[a] = array[b]
array[b] = temp
end

def Permutate.fact(n)
return 1 if n == 0
result = 1
(2..n).each do |i|
result *= i
end
result
end

end

#file equation.rb
class Equation

#digits contains an array of digits in the problem
#rhs is the right hand side of the equation
#overlay is a string representation of operators
# and their position in available positions between
# digits

def initialize(digits, rhs, overlay)
@digits = digits
@rhs = rhs
@overlay = overlay
@eqn = buildEquation

@valid = isValid?
end

def buildEquation
equation = @digits.to_s

#overlay permutation string over digits
#put a space before and after all operators
(0..@overlay.size).each{|i|
equation.insert((4*i + 1)," #{@overlay[i,1]} ")
}

#take _ placeholders out
equation.gsub!(" _ ","")

return equation
end

def isValid?
(eval(@eqn) == @rhs)
end

def to_s
#output the equation in standard format
result = "#{@eqn} = #{eval(@eqn)}".squeeze(" ")

if @valid
marker = "*" * result.size
return "#{marker}\n#{result}\n#{marker}"
else
return result
end
end

end

#file equationlist.rb
require 'permutate'
require 'equation'

class EquationList

def initialize(digits, operators, rhs)
@digits = digits
@operators = operators
@rhs = rhs
@list = Array.new
end

def build
#get permutations for location of operators
perms = Permutate.generate(@digits.size - 1)

#now assign each operator to a number in the perms list
operators.each_with_index{|operator,i|
perms.each{|perm|
perm.sub!(Regexp.new((i+1).to_s),operator)
}
}

#now replace each number left with _
#to denote that field is unused
perms.each{|perm|
perm.gsub!(/\d/,"_")
}

#now we need to get rid of nonunique equations
perms.uniq!

#now build a list of equation objects with this information
perms.each{|perm|
#puts perm
@list << Equation.new(@digits,@rhs,perm)
}
end

def display
puts @list
puts "#{@list.size} possible equations tested"
end
end

#file getTo100.rb
require 'equationlist'

digits = %w[1 2 3 4 5 6 7 8 9]
operators = %w[+ - -]
rhs = 100

equations = EquationList.new(digits, ops, rhs)
equations.build
equations.display

Comments are welcome, I'm here to learn!

Matt Hulse
matt.hulse@gmail.com```
on 2007-04-09 05:21
```On 08/04/07, Carl Porth <badcarl@gmail.com> wrote:
> After going back and reading the current solutions, I like Ken Bloom's
> each_partition method.  It's much cleaner than my combinations method.

I agree, very clean and efficient.  The three lines that put it all
together using #zip are what makes this work for me:

Digits.each_partition(Operators.length+1) do |digitspart|
OperatorPerms.each do |operatorsperm|
expression=digitspart.zip(operatorsperm).flatten.join
...

I think I would be feeling very happy if I'd submitted this solution :)```
on 2007-04-09 05:30
```require 'rubygems'
require 'test/unit'

# http://permutation.rubyforge.org/
require 'permutation'

#
# Partitions collections into all possible in-order subsets
#
#
module Enumerable

#
# Generate the partion sizes for a collection of a given
# length and a specific number of partitions.
#
def Enumerable.partition_sizes( collection_length,
partition_count, &proc )
Enumerable.generate_partition_sizes( [], collection_length,
partition_count, proc )
end

#
# Create all in-order partitions of the given collection.  Each
# partition should have partition_count elements.
#
# For example partitions( [1,2,3], 2 ) would yield
#      [1],[2,3]
# and  [1,2],[3]
#
# and partitions( [1,2,3,4], 2 ) would yield
#      [1],[2,3,4]
# and  [1,2],[3,4]
# and  [1,2,3],[4]
#
def partitions( partition_count, &proc )
Enumerable.partition_sizes( self.size, partition_count ) do |
partition|
partitioned_collection = []
consumed_so_far = 0
partition.each do |partition_size|
partitioned_collection << self[ consumed_so_far,
partition_size ]
consumed_so_far += partition_size
end
yield partitioned_collection
end
end

private
def Enumerable.generate_partition_sizes( so_far, length,
partition_count, proc )

raise "Invalid parameter" if( ( partition_count < 1 ) ||
( partition_count > length ) )
partition_size_sum_so_far = so_far.inject(0) { |total,item|
total+item }

if so_far.length == partition_count -1
working = so_far.dup
working << length - partition_size_sum_so_far
proc.call( working )
else
up_to = length - partition_size_sum_so_far -
(partition_count - so_far.length ) + 1
for size in 1..( up_to )
working = so_far.dup
working << size
generate_partition_sizes( working, length,
partition_count, proc )
end
end
end
end

class PartitionTest < Test::Unit::TestCase
def test_partition_size_4_count_2
expected = []
[1,2,3,4].partitions( 2 ) do |partition|
expected << partition
end

assert_equal expected, [
[ [1], [2, 3, 4] ],
[ [1, 2], [3, 4] ],
[ [1, 2, 3], [4] ]
]
end

def test_partition_size_4_count_3
expected = []
[1,2,3,4].partitions( 3 ) do |partition|
expected << partition
end

assert_equal expected, [
[ [1], [2], [3, 4] ],
[ [1], [2, 3], [4] ],
[ [1, 2], [3], [4] ]
]
end

def test_partition_size_5_count_1
expected = []
[1,2,3,4,5].partitions( 1 ) do |partition|
expected << partition
end

assert_equal expected, [
[ [ 1, 2, 3,4, 5 ] ],
]
end

def test_partition_size_5_count_5
expected = []
[1,2,3,4,5].partitions( 5 ) do |partition|
expected << partition
end

assert_equal expected, [
[ [1], [2], [3], [4], [5] ],
]
end

end

def find( digits, operators, magic_number )
# Generate all possible permutation of operations. Make sure that
each operator set
# begins with an "+" since we are actually creating an equation of
# "+{term1} {op1}{term2} {op2}{term3}" as it is easier to compute
operator_permutations = Permutation.for( operators ).map { |p|
( "+" + p.project).split(//) }.uniq

separator_string = "*" * 20

total_equations_evaluated = 0

# Partition the digits into groups of length one more than the
number of operators
digits.partitions( operators.length + 1 ) do |digit_partition|

# For each operator permutation we'll compute the result of
mixing the operators
# between the current partition
operator_permutations.each do |operator_permutation|

# Match up the digit partition and the operators
equation = digit_partition.zip( operator_permutation )

# Create the string representation, joining operators
# and operands into a resulting equation.
equation_string = equation.inject("") do |result,term|
# Only add the operator if we have something in the string
# this strips out the initial dummy "+" operator from our
# equation.
result = result + " " + term[1] + " " unless result.empty?
result = result + term[0].join
end

# Evaluate the equation
equation_value = eval( equation_string )
total_equations_evaluated += 1

# Output as required with stars surrounding any
# equation that yielded the value we wanted
puts separator_string if equation_value == magic_number
puts "#{equation_string} = #{equation_value}"
puts separator_string if equation_value == magic_number
end
end
puts "#{total_equations_evaluated} possible equations tested"
end

digits = [1,2,3,4,5,6,7,8,9]
operators = "--+"
find( digits, operators, 100 )```
on 2007-04-09 06:47
```Wow, this is pretty freaky.  My solution is eerily similar to Ken's
(albeit less concise), and I hadn't seen his code until now.  Look:

On Apr 8, 9:21 pm, "Marcel Ward" <ward...@gmail.com> wrote:
> On 08/04/07, Carl Porth <badc...@gmail.com> wrote:
>
> > After going back and reading the current solutions, I like Ken Bloom's
> > each_partition method.  It's much cleaner than my combinations method.

I wrote an Array#each_partition too, and my first implementation of it
looked almost just like his:

def each_partition(n = length)
if n < 1
yield []
else
(0..length-n).each do |x|
section=self[x, length]
self[0, x].each_partition(n-1) do |part|
yield part << section
end
end
end
self
end

I rewrote this when I found an iterative algorithm for it, but I
hadn't realized that that seemingly extraneous argument could be used
to limit the number of partitions, which is clever.  Still, this is a
fundamental algorithm in combinatorics, so I'm not too surprised that
he chose to put in Array.  This is where it gets eerie:

> I agree, very clean and efficient.  The three lines that put it all
> together using #zip are what makes this work for me:
>
> Digits.each_partition(Operators.length+1) do |digitspart|
>   OperatorPerms.each do |operatorsperm|
>      expression=digitspart.zip(operatorsperm).flatten.join
> ...

my version of the above:

digits.send(digits_message) do |part|
...
operators.send(*ops_send_args) do |tuple|
expr = part.zip(tuple).join(' ')
...

And then I go on to eval(expr), as Ken did.  Take it for granted that
my uses of send() do essentially the same thing.  Weird, no?

>
> I think I would be feeling very happy if I'd submitted this solution :)
>
> --
> Marcel

I was, too, before I saw Ken's.

Harrison```
on 2007-04-09 10:33
```Christian Neukirchen wrote:
> with checking the immediate results.
>   find_all { |x| x.count("-") == 2 and x.count("+") == 1 }.
>
>
>
I'm sorry to be a noob on this, but can someone please explain to me
what this is doing.  If it works, it must be genius, and I can't figure
it out.

Raj Sahae```
on 2007-04-09 11:36
```On 4/9/07, Raj Sahae <rajsahae@gmail.com> wrote:
> > Writing this code took maybe ten minutes and happened step-by-step
> >                                                    tr('012', '-+ ') }.
> > __END__
> > 1-23-456+789: 311
> >
> >
> I'm sorry to be a noob on this, but can someone please explain to me
> what this is doing.  If it works, it must be genius, and I can't figure
> it out.
>
> Raj Sahae
>
>
Actually I have no idea whatsoever, this is normally a good starting
point ;)
irb is our friend of course, so let us hack away:
irb(main):003:0> (000..'222'.to_i(3)).map{|x|x.to_s(3).rjust(3,
"0").tr('012', '-+ ')}
=> ["---", "--+", "-- ", "-+-", "-++", "-+ ", "- -", "- +", "-  ",
"+--", "+-+", "+- ", "++-", "+++", "++ ", "+ -", "+ +", "+  ", " --",
" -+", " - ", " +-", " ++", " + ", "  -", "  +", "   "]

Aha the ternary array is used to create all kind of operator
combinations including " ".
I do not know exactly what this is good for right now, but I guess we
will learn.
As a next step I increase 3 to 8 as I think we can understand that now
and I will add the next method
(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 }
=> ["--+     ", "-- +    ", "--  +   ", "--   +  ", "--    + ", "--
+", "-+-     ", "-+ -    ", "-+  -   ", "-+   -  ", "-+    - ", "-+
-", "- -+    ", "- - +   ", "- -  +  ", "- -   + ", "- -    +", "-
+-    ", "- + -   ", "- +  -  ", "- +   - ", "- +    -", "-  -+   ",
"-  - +  ", "-  -  + ", "-  -   +", "-  +-   ", "-  + -  ", "-  +  -
", "-  +   -", "-   -+  ", "-   - + ", "-   -  +", "-   +-  ", "-   +
- ", "-   +  -", "-    -+ ", "-    - +", "-    +- ", "-    + -", "-
-+", "-     +-", "+--     ", "+- -    ", "+-  -   ", "+-   -  ", "+-
- ", "+-     -", "+ --    ", "+ - -   ", "+ -  -  ", "+ -   - ", "+
-    -", "+  --   ", "+  - -  ", "+  -  - ", "+  -   -", "+   --  ",
"+   - - ", "+   -  -", "+    -- ", "+    - -", "+     --", " --+
", " -- +   ", " --  +  ", " --   + ", " --    +", " -+-    ", " -+ -
", " -+  -  ", " -+   - ", " -+    -", " - -+   ", " - - +  ", " - -
+ ", " - -   +", " - +-   ", " - + -  ", " - +  - ", " - +   -", " -
-+  ", " -  - + ", " -  -  +", " -  +-  ", " -  + - ", " -  +  -", " -
-+ ", " -   - +", " -   +- ", " -   + -", " -    -+", " -    +-", "
+--    ", " +- -   ", " +-  -  ", " +-   - ", " +-    -", " + --   ",
" + - -  ", " + -  - ", " + -   -", " +  --  ", " +  - - ", " +  -
-", " +   -- ", " +   - -", " +    --", "  --+   ", "  -- +  ", "  --
+ ", "  --   +", "  -+-   ", "  -+ -  ", "  -+  - ", "  -+   -", "  -
-+  ", "  - - + ", "  - -  +", "  - +-  ", "  - + - ", "  - +  -", "
-  -+ ", "  -  - +", "  -  +- ", "  -  + -", "  -   -+", "  -   +-", "
+--   ", "  +- -  ", "  +-  - ", "  +-   -", "  + --  ", "  + - - ",
"  + -  -", "  +  -- ", "  +  - -", "  +   --", "   --+  ", "   -- +
", "   --  +", "   -+-  ", "   -+ - ", "   -+  -", "   - -+ ", "   - -
+", "   - +- ", "   - + -", "   -  -+", "   -  +-", "   +--  ", "   +-
- ", "   +-  -", "   + -- ", "   + - -", "   +  --", "    --+ ", "
-- +", "    -+- ", "    -+ -", "    - -+", "    - +-", "    +-- ", "
+- -", "    + --", "     --+", "     -+-", "     +--"]

It is a little longer but we see already that only 2 minuses and 1
plus is allowed...
By storing this into a variable tmp we can continue easily to explore
what is happening
tmp.map{|x|  t = "1" + x.split(//).zip((2..9).to_a).join.delete(" ") ;
[eval(t),t]}
=> [[456785, "1-2-3+456789"], [56754, "1-2-34+56789"], [6443,
"1-2-345+6789"], [-2668, "1-2-3456+789"], [-34479, "1-2-34567+89"],
[-345670, "1-2-345678+9"], [-456787, "1-2+3-456789"], [-56756,
"1-2+34-56789"], [-6445, "1-2+345-6789"], [2666, "1-2+3456-789"],
[34477, "1-2+34567-89"], [345668, "1-2+345678-9"], [56763,
"1-23-4+56789"], [6722, "1-23-45+6789"], [311, "1-23-456+789"],
[-4500, "1-23-4567+89"], [-45691, "1-23-45678+9"], [-56807,
"1-23+4-56789"], [-6766, "1-23+45-6789"], [-355, "1-23+456-789"],
[4456, "1-23+4567-89"], [45647, "1-23+45678-9"], [6551,
"1-234-5+6789"], [500, "1-234-56+789"], [-711, "1-234-567+89"],
[-5902, "1-234-5678+9"], [-7017, "1-234+5-6789"], [-966,
"1-234+56-789"], [245, "1-234+567-89"], [5436, "1-234+5678-9"],
[-1561, "1-2345-6+789"], [-2322, "1-2345-67+89"], [-3013,
"1-2345-678+9"], [-3127, "1-2345+6-789"], [-2366, "1-2345+67-89"],
[-1675, "1-2345+678-9"], [-23373, "1-23456-7+89"], [-23524,
"1-23456-78+9"], [-23537, "1-23456+7-89"], [-23386, "1-23456+78-9"],
[-234565, "1-234567-8+9"], [-234567, "1-234567+8-9"], [-456789,
"1+2-3-456789"], [-56820, "1+2-34-56789"], [-7131, "1+2-345-6789"],
[-4242, "1+2-3456-789"], [-34653, "1+2-34567-89"], [-345684,
"1+2-345678-9"], [-56769, "1+23-4-56789"], [-6810, "1+23-45-6789"],
[-1221, "1+23-456-789"], [-4632, "1+23-4567-89"], [-45663,
"1+23-45678-9"], [-6559, "1+234-5-6789"], [-610, "1+234-56-789"],
[-421, "1+234-567-89"], [-5452, "1+234-5678-9"], [1551,
"1+2345-6-789"], [2190, "1+2345-67-89"], [1659, "1+2345-678-9"],
[23361, "1+23456-7-89"], [23370, "1+23456-78-9"], [234551,
"1+234567-8-9"], [56794, "12-3-4+56789"], [6753, "12-3-45+6789"],
[342, "12-3-456+789"], [-4469, "12-3-4567+89"], [-45660,
"12-3-45678+9"], [-56776, "12-3+4-56789"], [-6735, "12-3+45-6789"],
[-324, "12-3+456-789"], [4487, "12-3+4567-89"], [45678,
"12-3+45678-9"], [6762, "12-34-5+6789"], [711, "12-34-56+789"], [-500,
"12-34-567+89"], [-5691, "12-34-5678+9"], [-6806, "12-34+5-6789"],
[-755, "12-34+56-789"], [456, "12-34+567-89"], [5647, "12-34+5678-9"],
[450, "12-345-6+789"], [-311, "12-345-67+89"], [-1002,
"12-345-678+9"], [-1116, "12-345+6-789"], [-355, "12-345+67-89"],
[336, "12-345+678-9"], [-3362, "12-3456-7+89"], [-3513,
"12-3456-78+9"], [-3526, "12-3456+7-89"], [-3375, "12-3456+78-9"],
[-34554, "12-34567-8+9"], [-34556, "12-34567+8-9"], [-56778,
"12+3-4-56789"], [-6819, "12+3-45-6789"], [-1230, "12+3-456-789"],
[-4641, "12+3-4567-89"], [-45672, "12+3-45678-9"], [-6748,
"12+34-5-6789"], [-799, "12+34-56-789"], [-610, "12+34-567-89"],
[-5641, "12+34-5678-9"], [-438, "12+345-6-789"], [201,
"12+345-67-89"], [-330, "12+345-678-9"], [3372, "12+3456-7-89"],
[3381, "12+3456-78-9"], [34562, "12+34567-8-9"], [6903,
"123-4-5+6789"], [852, "123-4-56+789"], [-359, "123-4-567+89"],
[-5550, "123-4-5678+9"], [-6665, "123-4+5-6789"], [-614,
"123-4+56-789"], [597, "123-4+567-89"], [5788, "123-4+5678-9"], [861,
"123-45-6+789"], [100, "123-45-67+89"], [-591, "123-45-678+9"], [-705,
"123-45+6-789"], [56, "123-45+67-89"], [747, "123-45+678-9"], [-251,
"123-456-7+89"], [-402, "123-456-78+9"], [-415, "123-456+7-89"],
[-264, "123-456+78-9"], [-4443, "123-4567-8+9"], [-4445,
"123-4567+8-9"], [-6667, "123+4-5-6789"], [-718, "123+4-56-789"],
[-529, "123+4-567-89"], [-5560, "123+4-5678-9"], [-627,
"123+45-6-789"], [12, "123+45-67-89"], [-519, "123+45-678-9"], [483,
"123+456-7-89"], [492, "123+456-78-9"], [4673, "123+4567-8-9"], [2012,
"1234-5-6+789"], [1251, "1234-5-67+89"], [560, "1234-5-678+9"], [446,
"1234-5+6-789"], [1207, "1234-5+67-89"], [1898, "1234-5+678-9"],
[1260, "1234-56-7+89"], [1109, "1234-56-78+9"], [1096,
"1234-56+7-89"], [1247, "1234-56+78-9"], [668, "1234-567-8+9"], [666,
"1234-567+8-9"], [444, "1234+5-6-789"], [1083, "1234+5-67-89"], [552,
"1234+5-678-9"], [1194, "1234+56-7-89"], [1203, "1234+56-78-9"],
[1784, "1234+567-8-9"], [12421, "12345-6-7+89"], [12270,
"12345-6-78+9"], [12257, "12345-6+7-89"], [12408, "12345-6+78-9"],
[12279, "12345-67-8+9"], [12277, "12345-67+8-9"], [12255,
"12345+6-7-89"], [12264, "12345+6-78-9"], [12395, "12345+67-8-9"],
[123450, "123456-7-8+9"], [123448, "123456-7+8-9"], [123446,
"123456+7-8-9"]]

Well this is very impressive as it solves the quiz but I lost him
there, I guess we have to look into the block applied to tmp.map
{|x|  t = "1" + x.split(//).zip((2..9).to_a).join.delete(" ") ;
[eval(t),t]}

okay let us take just one x, e.g.
x= tmp[32]
=> "-   -  +"
## To my great despair tmp[42] is not a very good example :(

Now we split x into single characters and zip the digits 2 to 9 into
them
x.split(//).zip([*2..9])
=> [["-", 2], [" ", 3], [" ", 4], [" ", 5], ["-", 6], [" ", 7], [" ",
8], ["+", 9]]
and I think I understand what happened now, the rest is basic, add a 1
in the front flatten the array and delete all spaces, and you get the
expressions needed for the quiz.

I guess that the final sort.each is quite straight forward.

HTH

BTW I want to have my ball back James, or adjust my handicap please ;).

Cheers
Robert```
on 2007-04-09 14:19
```On 4/8/07, Marcel Ward <wardies@gmail.com> wrote:
> ...
>
> I think I would be feeling very happy if I'd submitted this solution :)

May I have the temerity to point out that I posted basically the same
solution, which I posted two hours before Ken's.

--
Rick DeNatale

My blog on Ruby
on 2007-04-09 14:48
```Ken Bloom <kbloom@gmail.com> writes:

>> the immediate results.
>
> 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.)

Yes, but that confuses the application logic.  I don't think it will
save memory compared to yours, you are #to_s'ing a lot more than me!```
on 2007-04-09 14:52
```"Ryan Leavengood" <leavengood@gmail.com> writes:

>>     puts "#{x}: #{s}"
>>     puts "*****************" if s == 100
>>   }
>
> That's brilliant. It took me a minute to figure out how it worked, but I like.
>
> I started working on a generalized solution using this algorithm, but
> it gets tricky. It isn't too hard to generalize the number sequence,
> but generalizing the operators really makes it messy.

The number sequence is easy, and the operators are easy too (just
change the base), as you have shown.  The real problem is to allow the
numbers in any order.

> Ryan

P.S: The code was not written deliberately in a cryptic style (but
admittedly unfactored).  This is how I code one-shot things.```
on 2007-04-09 16:09
```On 09/04/07, Rick DeNatale <rick.denatale@gmail.com> wrote:
> >      expression=digitspart.zip(operatorsperm).flatten.join
> > ...
> >
> > I think I would be feeling very happy if I'd submitted this solution :)
>
> May I have the temerity to point out that I posted basically the same
> solution, which I posted two hours before Ken's.

Indeed you may -- apologies, I thought I had been back through all the
posts but didn't go back as far as yours.

So I think you should also be feeling very happy :)

I do have one small piece of constructive criticism (if I may) since
you brought attention to your code:

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

Could also have been written:

found = val == goal
puts "*****************" if found
puts "#{eqn} = #{val}" if verbose || goal == val
puts "*****************" if found
found_in_a_row = found ? found_in_a_row + 1 : 0

For the same number of lines, I find the second much easier to follow
without having to remember any state for the second time around.
There does not seem to be any advantage in placing the asterisk lines
together. (?)

As another aside, I'm in two minds as to whether it's necessary to
provide such a complete set of parameters (and comments) for these
solutions.  On the one hand it sets a good example to newcomers (and
it satisfies our quest for perfection) but on the other it does tend
to obscure some of the more interesting details.  It's like you're
damned if you do and damned if you don't - the difficulty is finding
the right balance.

I think there's room for both kinds of posts but certainly the shorter
ones seem more appealing even if longer ones do use the same
underlying methods.  I also like to work at making a solution more
generic for future purposes but I've come to the conclusion that
(unless the extra credits mention it) there's no point because I'm
only going to prejudice my solution.

In the real world I would go for the more generic code and proper
comments any day but for the purposes of the quiz I like to see
solutions that do just as much as is asked of them and ideally fit on
one page of my screen.

--
Marcel```
on 2007-04-09 16:25
```On Apr 9, 6:18 am, "Rick DeNatale" <rick.denat...@gmail.com> wrote:
> >   OperatorPerms.each do |operatorsperm|
> >      expression=digitspart.zip(operatorsperm).flatten.join
> > ...
>
> > I think I would be feeling very happy if I'd submitted this solution :)
>
> May I have the temerity to point out that I posted basically the same
> solution, which I posted two hours before Ken's.
>

Indeed!  Well, isn't too coincidental after all for me to have used
the same mechanism.   Great minds must think alike, no?

Harrison Reiser```
on 2007-04-09 16:28
```Thanks for another fun Ruby Quiz.  Here is my take on it, I did not
see other solutions that used String formatting to generate the
expressions.

class String
def unique_permutations
# modified to get unique permutations
# from
# which says it was inspired by a RubyQuiz! :)
return [self] if self.length < 2
perms = Hash.new

0.upto(self.length - 1) do |n|
#rest = self.split('')
rest = self.split(//u)            # for UTF-8 encoded strings
picked = rest.delete_at(n)
rest.join.unique_permutations.each { |x| perms[picked + x] =
nil }
end

perms.keys
end
end

digits = ARGV[0]
ops = ARGV[1]
target = ARGV[2].to_i

# pad ops list with spaces to match the number of slots between the
digits
ops = ops + " " * (digits.size - ops.size - 1)

# build a format string with slots between the digits
digits = digits.split("").join("%s")

operator_perms = ops.unique_permutations
operator_perms.each do |p|
# build expression by inserting the ops into the format string,
# after converting spaces to empty strings
exp = digits % p.split("").map{|x|x.chomp(" ")}
val = eval(exp)
puts "*******************" if val==target
puts exp + " = " + val.to_s
puts "*******************" if val==target
end
puts
puts "%d possible equations tested" % operator_perms.size

Regards,
Paul```
on 2007-04-09 16:31
```On Apr 9, 2007, at 4:35 AM, Robert Dober wrote:

> BTW I want to have my ball back James, or adjust my handicap

I'm just glad you broke that code down for us.  Now maybe I can read
it to look smart when I write up the summary.  ;)

James Edward Gray II```
on 2007-04-09 16:39
```On 4/9/07, James Edward Gray II <james@grayproductions.net> wrote:
>
;)```
on 2007-04-09 16:51
```On Apr 8, 2007, at 10:10 PM, Matt Hulse wrote:

> My first quiz attempt ever so go easy on me :)

Welcome to Ruby Quiz.

James Edward Gray II```
on 2007-04-09 17:05
```On Apr 9, 8:25 am, "paul" <nova...@gmail.com> wrote:
>     perms = Hash.new
>   end
> end
>

Clever use of hashes.  I wrote a String#each_unique_permutation, but
didn't think that it could be used like this.

>   # after converting spaces to empty strings
>   exp = digits % p.split("").map{|x|x.chomp(" ")}

I like that you permute the ops string with extra spaces.  Much
simpler than something like digits.each_ordered_partition.

Harrison Reiser```
on 2007-04-09 17:07
```On Apr 8, 2007, at 10:10 PM, Matt Hulse wrote:

> Comments are welcome, I'm here to learn!

* print "...\n" is just puts "..." in Ruby.

* Ruby has a command-line switch to enable a debuggin mode:  -d.
Among other things, this sets \$DEBUG to true.  So instead of
commenting out print statements, just do something like:

puts ... if \$DEBUG

You can then run with ruby -d ... when you want the output.

* You can swap values without a temporary variable in Ruby:  array
[a], array[b] = array[b], array[a].

* When you set something and then go into an iterator to modify it,
you probably want inject() instead:  (2..n).inject { |fac, n| fac * n }.

* The Ruby naming convention is to use snake_case for variables and
methods.

The above are just some suggestions.  The code seems to work, which
is the most important part.  Nice work.

James Edward Gray II```
on 2007-04-09 17:15
```On 4/9/07, Marcel Ward <wardies@gmail.com> wrote:
> On 09/04/07, Rick DeNatale <rick.denatale@gmail.com> wrote:

>
>   found = val == goal
>   puts "*****************" if found
>   puts "#{eqn} = #{val}" if verbose || goal == val
>   puts "*****************" if found
>   found_in_a_row = found ? found_in_a_row + 1 : 0

>
> For the same number of lines, I find the second much easier to follow
> without having to remember any state for the second time around.
> There does not seem to be any advantage in placing the asterisk lines
> together. (?)

Not quite the same I think.  I wrote it the way I did to cover the
(admittedly probably rare case where two solutions occur  one after
the other. That's why the variable found_in_a_row is there.

I wanted to see:

********
xxxxxx = 100
yyyyyy = 100
********

********
xxxxxx = 100
********
********
yyyyyy = 100
********

> underlying methods.  I also like to work at making a solution more
> generic for future purposes but I've come to the conclusion that
> (unless the extra credits mention it) there's no point because I'm
> only going to prejudice my solution.
>
> In the real world I would go for the more generic code and proper
> comments any day but for the purposes of the quiz I like to see
> solutions that do just as much as is asked of them and ideally fit on
> one page of my screen.

I see it as an opportunity to document my thoughts in solving the
quiz, and thereby teach myself and others.  The best way to learn is
to teach.

And, Frankly, I'm kind of an anti-golf advocate, except when I have a
club in my hands instead of a keyboard at my finger-tips.

Finally I figure that it's JEG II's choice as to how to summarize the
solutions.

Chacun a son
goût!
--
Rick DeNatale

My blog on Ruby
on 2007-04-09 19:02
```On 09/04/07, Rick DeNatale <rick.denatale@gmail.com> wrote:
>
> ********
>   xxxxxx = 100
> ********
> ********
>   yyyyyy = 100
> ********

Aha, thanks for clarifying.  I think this would be a prime candidate
for a comment.  Before someone else gets their mits on the code and
starts refactoring inappropriately (like me).

> > underlying methods.  I also like to work at making a solution more
> quiz, and thereby teach myself and others.  The best way to learn is
> to teach.

I can't disagree with that - it's been my theory up until now but I
have no idea how useful it's been to others.  If I'm just turning
people away with long posts then I'd prefer to shorten them down to
meet the audience's expectations better.

> And, Frankly, I'm kind of an anti-golf advocate, except when I have a
> club in my hands instead of a keyboard at my finger-tips.
>
> Finally I figure that it's JEG II's choice as to how to summarize the solutions.
>
> Chacun a son goût!

I'm definitely in favour of comments and readability.  I guess I was
just verbalising some inner thoughts and wondering how others try to
find the right balance.

--
Marcel```
on 2007-04-09 19:12
```On Apr 9, 2007, at 12:00 PM, Marcel Ward wrote:

> On 09/04/07, Rick DeNatale <rick.denatale@gmail.com> wrote:
>
>> Finally I figure that it's JEG II's choice as to how to summarize
>> the solutions.
>>
>> Chacun a son goût!
>
> I'm definitely in favour of comments and readability.  I guess I was
> just verbalising some inner thoughts and wondering how others try to
> find the right balance.

It can be tricky to know when to use them.  A good comment can ease
you right into some code.  A bad comment can do the opposite and I
even find that a good comment sometimes hurts completely obvious code.

In general though, I like seeing them in Ruby Quiz solutions for two
reasons:

* It helps me understand the code.  That's how I know if I want to
write about it and it helps me know what to say if I do.

* It helps others understand all the solutions I don't cover.  Always
a big win, I think.

There's my two cents worth.

James Edward Gray II```
on 2007-04-09 19:21
```Marcel Ward wrote:

>> I see it as an opportunity to document my thoughts in solving the
>> quiz, and thereby teach myself and others.  The best way to learn is
>> to teach.
>
> I can't disagree with that - it's been my theory up until now but I
> have no idea how useful it's been to others.  If I'm just turning
> people away with long posts then I'd prefer to shorten them down to
> meet the audience's expectations better.

I say: go for long emails if you have to, but try to be as precise as
you can. This has the "learning through teaching" effect, and helps to
keep your emails at a manageable length.

It is my opinion, that those, who can't be bothered to read a long
explanation, won't read the documentation either, which results in
somebody who can't be educated in the first place.

Rest assured, if the topic interests me, I'll read a long email, too.

> I'm definitely in favour of comments and readability.  I guess I was
> just verbalising some inner thoughts and wondering how others try to
> find the right balance.

Well, if the code is readable and speaks for itself, comments can be
omitted. Otherwise, the comments should explain what the code does, not
what it should do.

I.e.:
#Opening a file
f = File.open("foo")

^
|
is superfluous.

#This does stuff to the passed argument bar
def do_stuff(bar)
#doing stuff to bar
end
^
|
Isn't superfluous, and aids debugging if the thing doesn't do what it
should. And you know that it doesn't do what it is supposed to do,
because your tests tell you that it doesn't.

But such a thing merits it's own thread, I'd say.

--
Phillip "CynicalRyan" Gawlowski
http://cynicalryan.110mb.com/

Rule of Open-Source Programming #8:

Open-Source is not a panacea.```
on 2007-04-09 19:39
```Weighing in about the comments and explanations of the quiz answers:
the comments are good, and important especially when using tricks.
Especially considering that I'm not alone in suggesting that
ruby-newbies I meet read old quizzes and the solutions that were
simple, code is sometimes best left uncommented so that the reader is
forced to parse it and figure out exactly what's going on.  It aides
in their understanding.

And yes I know I'm horribly guilty of not entering enough comments in
myself, especially in some of the ugly code. :)

--Kyle```
on 2007-04-09 19:56
```Robert Dober wrote:
> point ;)
> irb is our friend of course, so let us hack away:

also went into irb and stepped through the process even more
thoroughly.  I'm amazed at how changing the base and then using string
translation makes the problem so simple.```
on 2007-04-10 06:17
```James Gray wrote:
> The three rules of Ruby Quiz:

=] Here is my solution.

You will forgive the extension of the file, but this quiz was an excuse
for me to learn and play with new things, like OptParse. I rather

My solution handles extra credits, and my own suggestions except
parenthesis precedence. With full options, it runs very slow, because
the number of permutations and combinations grows n!

As an example, a run with these options

\$ ruby quiz119.rb --o +,-,*,/ --f --m --v --d 1234567

produces

123+4+5*0.67 = 130.35
123+4+5*6.7 = 160.50
0.123+4+5*67 = 339.12
.....

17 times target reached, out of 217224 equations tested:
123*4-56*7 = 100.00
1+23+4+5+67 = 100.00
1+2+34+56+7 = 100.00
1+23-4+56/0.7 = 100.00
12+0.3*45*6+7 = 100.00
12+3*4.5*6+7 = 100.00
12+3*45*0.6+7 = 100.00
-1-234+5*67 = 100.00
1*23*4+56/7 = 100.00
-1/2+34-0.5+67 = 100.00
-1+0.2*34*5+67 = 100.00
-1+2*3.4*5+67 = 100.00
-1+2*34*0.5+67 = 100.00
1*23*4-5+6+7 = 100.00
-1-2+34*5-67 = 100.00
-1/2+3/0.4/5*67 = 100.00
-1/2+3/4/0.5*67 = 100.00
Total run time: 50.844356 seconds

Trying to do that for digits 1 to 9 is a craziness @.@

Here is the file:

http://pastie.caboo.se/52702```
on 2007-04-10 23:55
```My first posted solution - hope it's ok!

## Start target.rb
class TargetFinder

def initialize(inputs, operators)
self.inputs = inputs
self.operators = operators
reset
end

# Clear out cached, calculated data
def reset
@equations = nil
@results = nil
end

# Only allow digits as input
def inputs= new_inputs
@inputs = new_inputs.gsub /\D/, ''
reset
end

# Only the +, - and * operators are really safe to use with this
approach
def operators= new_ops
@operators = new_ops.gsub(/[^+*-]/, '').split(//)
reset
end

# Loop through our results putting the required stars around the
correct lines
def get_to target
calculate if @results.nil?
@results.each do |eq, result|
puts "*" * 30 if result == target.to_i
puts "#{eq} = #{result}"
puts "*" * 30 if result == target.to_i
end

puts "%d equations tested" % @equations.length
end

# Calculate all of the possible equations given a set of inputs
def calculate
@equations = self.class.permutate(@inputs, @operators)
@results = {}
@equations.each do |eq|
@results[eq] = eval(eq)
end
end

# Here's the workhorse, recursively calculates all possible equations
from an
input string and operators
def self.permutate(inputs, operators)
return [inputs] if operators.empty?
arr = []
# Loop through all the possible 'first' value/operator pairs
operators.uniq.each do |op|
other_operators = operators.without(op)
(1..inputs.length-operators.length).each do |i|

# Find all possible endings from the remaining inputs and
operators, and
prepend this beginning to all of them
permutate(inputs[i..-1], other_operators).each do |permutation|
arr << "#{inputs[0...i]} #{op} #{permutation}"
end

end
end
arr
end
end

# A long-winded way of removing a single item from an array which may
have
duplicates
# Almost certainly not the best way of doing this but good enough
class Array
def without item
new_array = []
found = false
each do |x|
if x == item
new_array << x if found
found = true
next
end
new_array << x
end
new_array
end
end

if \$0 == __FILE__
inputs = ARGV.shift || "123456789"
target = ARGV.shift || "100"
operators = ARGV.shift || "+--"

finder = TargetFinder.new(inputs, operators)
finder.get_to target
end```
on 2007-04-11 05:10
```On Mon, 09 Apr 2007 21:47:43 +0900, Christian Neukirchen wrote:

>>> without thinking too much or locating Knuth on the bookshelve. Writing
>>> (00000000..'22222222'.to_i(3)).map { |x| x.to_s(3).rjust(8, "0").
>>
>> (It doesn't keep maintain references to the bad combinations of
>> operators, allowing the GC to reclaim them earlier.)
>
> Yes, but that confuses the application logic.  I don't think it will
> save memory compared to yours, you are #to_s'ing a lot more than me!

I didn't claim that it saves memory by allocating less. It saves memory
by retaining less references, so it can GC earlier.

--Ken```
on 2007-04-11 05:40
```On Mon, 09 Apr 2007 21:18:16 +0900, Rick DeNatale wrote:

>>   OperatorPerms.each do |operatorsperm|
>>      expression=digitspart.zip(operatorsperm).flatten.join
>> ...
>>
>> I think I would be feeling very happy if I'd submitted this solution :)
>
> May I have the temerity to point out that I posted basically the same
> solution, which I posted two hours before Ken's.

I typically compose my solution on Friday afternoon, and sit on it for
two days before posting to ruby-talk. When I post on Sunday, I do so
before reading any other solutions out there. After posting, I browse
the
solutions, marvel at the clever ones, and usually notice that a bunch of
people have come up with the same idiomatic solution as me, thereby
suggesting that:
1) those people are also interested in clear idiomatic code
2) I'm unlikely to be the one summarized.

--Ken```
on 2007-04-11 09:59
```On 4/11/07, Ken Bloom <kbloom@gmail.com> wrote:
> >>
> I typically compose my solution on Friday afternoon, and sit on it for
> two days before posting to ruby-talk. When I post on Sunday, I do so
> before reading any other solutions out there. After posting, I browse the
> solutions, marvel at the clever ones, and usually notice that a bunch of
> people have come up with the same idiomatic solution as me, thereby
> suggesting that:
> 1) those people are also interested in clear idiomatic code
> 2) I'm unlikely to be the one summarized.
Cheer up Ken;) http://www.rubyquiz.com/quiz110.html```
on 2007-04-16 02:30
```Note:
Like I said in my submission to #120, this seems not to have gotten
through
when I sent it last week, and I just noticed. So here it is again
(though
I have changed it a bit since then - originally I had an Operation
called
Cat that concatenated adjacent numbers; now that's done separately).

------------------------

Like my submission for last week's quiz, this one grew too long. But
there's
some things I like about it, so here it is. First I wrote an algorithm
to generate all permutations of an Array, but excluding those that are
the
same as others ('--+' and '--+' won't both be generated). To do this,
for each
unique element of the Array, I append it to all results of running it
recursively on the rest (if that's worded confusingly, look at the code
at the
top of array_stuff.rb).

I then build an Operator class, which is just a Proc with a name so to_s
can
be, say, '+' instead of '#<Proc:0xb7acef88...>'. All Operators sit
inside an
Array, and take two arguments: the Array they're in, and their index
within
that Array. When called, they modify the Array. For example:

The Add Operator can then be called by either of these:

a.exec_op_at!(1)

and afterwards a == [3]. First I build an Array containing all the
initial
Operators (Sub, Sub, Add). This Array is what I call
each_uniq_permutation on.
Each perm then gets mixed in to the data by the each_mix method in
array_stuff.

Example:

nums = [1, 2, 3]

calling:

nums.each_mix(ops)

will yield each of:
... etc etc

Some will be valid expressions, many won't.

Each Operator also has a precedence. For each Operator in the
Array from highest to lowest precedence, we let it modify the Array.

[1, Add, 2, Mult, 2, 3]
-> [47]

One thing I don't like about my code is that I scan through the
expression
Arrays a lot, like for finding the next adjacent numbers to concatenate
or the
next Operator to apply. Ops can have arbitrary effects on the Array, so
we need
to watch everything. Maybe an Op expands to other Ops or something. I
thought
of implementing this in different ways, like specifically keeping an
ordered-by-precedence list of all Ops in the expression, but didn't get
to it.
Oh, and I've implemented Ops for addition, subtraction, multiplication,
division, and parenthesis.

Here's the code:

#
---------------------------------------------------------------------------
# array_stuff.rb
# Ruby Quiz 119: Getting to 100

class Array
# Yield once for each unique element of this Array.
def each_uniq_element
self.uniq.each { |e| yield e }
end

# Like Array delete(), but only delete a single occurrence of e
# all of them. Also unlike delete(), it returns a new Array instead of
# modifying this one (why isn't delete() named delete!() ?)
def delete_one(e)
arr = self.clone
i = arr.index(e)
arr.delete_at(i) if not i.nil?
arr
end

# Generates all unique permutations of this Array, yielding each one.
# By 'unique' I mean both permutations [...,x,...,y,...] and
[...,y,...,x,...]
# will not be generated if x == y.
# (wonder if there's a non-recursive way to do this?)
def each_uniq_permutation
if self.size.zero?
yield []
else
self.each_uniq_element do |e|
self.delete_one(e).each_uniq_permutation do |perm_part|
yield([e] + perm_part)
end
end
end
end

# Find the lowest index of val, starting from index start.
def index_past(val, start)
(start...self.size).each { |i| return i if self[i] == val }
nil
end

# Replace all values from indices i through j (inclusive) with the
single
# value val.
def replace_at!(i, j, val)
raise 'Bad indices given' if i < 0 or j < i or j >= self.size
self.slice!(i, j-i+1)
self.insert(i, val)
end

# "Mix together" self and arr in all possible ways that preserve the
order of
# each, yielding the results.
def each_mix(arr)
if    self.empty? then yield arr.clone
elsif arr.empty?  then yield self.clone
else
self.slice(1, self.length).each_mix(arr) do |mix|
yield [self.first] + mix
end
self.each_mix(arr.slice(1, arr.length)) do |mix|
yield [arr.first] + mix
end
end
end
end

#
---------------------------------------------------------------------------
# ops.rb
# Ruby Quiz 119: Getting to 100

require 'array_stuff'
require 'enumerator'

class Symbol
# This nice ol' trick.
def to_proc
proc { |obj, *args| obj.send(self, *args) }
end
end

class Array
# Return the index of the next-highest-precendence operator within
this Array.
def next_op_index
# Yuck... a linear search.
op_i = nil
self.each_index do |i|
if self[i].is_a?(Proc) and
(op_i.nil? or
Ops.precedence_of(self[i]) > Ops.precedence_of(self[op_i]))
op_i = i
end
end
op_i
end

# Execute the operation that is at the given index on self.
def exec_op_at!(index)
raise 'Not a Proc' if not self[index].is_a? Proc
self[index][self, index] # I like this line..
end

# Concatenate any adjacent numbers. Repeat until none are left.
def concat_nums!(base = 10)
# There's gotta be a much, much better way to do this...
i = 0
while i < self.size-1
while self[i].is_a? Numeric and self[i+1].is_a? Numeric
# Would logs & exponents be better than strings for this?
self[i] = (self[i].to_s(base) + self[i+1].to_s(base)).to_i(base)
self.delete_at(i+1)
end
i += 1
end
end

# Process all operators in self, from highest-precedence to lowest.
Along the
# way, adjacent numbers will be concatenated (which always has higher
# precedence than any operators).
def process_ops!
concat_nums!
op_i = self.next_op_index
while not op_i.nil?
self.exec_op_at! op_i
concat_nums!
op_i = self.next_op_index
end
self
end

# Just like process_ops!, but return a new Array instead of working on
self.
def process_ops
arr = self.clone
arr.process_ops!
arr
end
end

module Ops
# Here lie blocks of incense, burning for the Proc God.
# Inhale.

# Proc with a name for prettier to_s.
class Operator < Proc
def initialize(name)
super() { yield }
@name = name.to_s
end
def to_s; @name; end
end

# Produces an Operator that sits between two numbers and replaces
them.
# For example, [1,Add,2] => [3]
# Its name will be op.to_s.
BinaryOp = lambda do |op|
Operator.new(op.to_s) do |list, index|
num_left, num_right = list[index-1], list[index+1]
raise 'Not numeric.' if not num_left.is_a?  Numeric or
not num_right.is_a? Numeric
list.replace_at!(index-1, index+1, op.to_proc[num_left,
num_right])
end
end

# Operators that sit between two numbers and perform arithmetic on
them.
Mult = BinaryOp[:*]
Div  = BinaryOp[:/]
Sub  = BinaryOp[:-]

# Operator to group things.
LeftParen = Operator.new('(') do |list, left_paren_index|
right_paren_index = list.index_past(RightParen, left_paren_index+1)
raise 'No right paren' if right_paren_index.nil?
contained = list.slice!(left_paren_index,
right_paren_index - left_paren_index + 1)
contained.shift; contained.pop # Remove parens on ends
contained.process_ops!
list.insert(left_paren_index, *contained)
end

# Does nothing; LeftParen takes care of everything.
RightParen = Operator.new(')') { |list, index| }

# Precedence of operators.
Precedence = {
LeftParen  => 3,
RightParen => 2,
Mult       => 1,
Div        => 1,
Sub        => 0
}

# Get the precedence of the given Operation. Higher is more important.
def Ops.precedence_of(op)
Precedence[op]
end
end

#
---------------------------------------------------------------------------
# getting_to_100.rb
# Ruby Quiz 119: Getting to 100

require 'array_stuff'
require 'ops'

# Main method for this Quiz. Print out one line for each valid way of
arranging
# nums and ops into an expression. The marker will appear around results
# matching target.
#
# Arguments:
#   nums: Something that, when to_a is called on it, returns an Array of
#         numbers.
#   ops:  An Array of Operators.
#   target: Target number.
#   marker: String to print above & below target hits.
def get_to(nums, ops, target = 100, marker = '************************')
nums = nums.to_a
num_tested = num_valid = num_found = 0

# Permute the ops in all uniq ways, and mix them with nums to generate
# expressions.
ops.each_uniq_permutation do |op_perm|
nums.each_mix(op_perm) do |expr|
num_tested += 1
begin
result = expr.process_ops
num_valid += 1

if result.size == 1
if result.first == target
num_found += 1
puts marker
puts "#{num_valid}: #{expr.join} = #{result.join(',')}"
puts marker
else
puts "#{num_valid}: #{expr.join} = #{result.join(',')}"
end
else
# The list didn't collapse all the way to a single element.
#\$stderr.puts 'Warning: operation did not collapse:'
#\$stderr.puts "#{num_tested}: #{expr.join} =
#{result.join(',')}"
end
rescue Object => ex
# Some operation didn't work. Perhaps non-matching parens. Maybe
this
# should be handled another way..
#\$stderr.puts 'Warning: operation failed.'
#\$stderr.puts ex
end
end
end

puts '----------------'
puts "#{num_tested} possible expression were generated."
puts "  Of those, #{num_valid} were valid."
puts "    Of those, #{num_found} matched the target."
end

# Example from the Quiz.
#get_to( (1..9), [Ops::Sub, Ops::Sub, Ops::Add] )

# Example showing off parenthesis.
#get_to( (1..3), [Ops::Add, Ops::Mult, Ops::LeftParen, Ops::RightParen],
9 )

#
---------------------------------------------------------------------------```
This topic is locked and can not be replied to.