On 4/9/07, James Edward G. II [email protected] wrote:
Thanks for another fun Ruby Q… 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
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/139858
# 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 Apr 9, 8:25 am, “paul” [email protected] wrote:
perms = Hash.newend
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 R.
On Apr 8, 2007, at 10:10 PM, Matt Hulse wrote:
Comments are welcome, I’m here to learn!
Some things I saw while reading through your code:
-
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 G. II
On Apr 8, 2007, at 10:10 PM, Matt Hulse wrote:
My first quiz attempt ever so go easy on me
Welcome to Ruby Q…
James Edward G. II
On 09/04/07, Rick DeNatale [email protected] 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 4/9/07, Marcel W. [email protected] wrote:
On 09/04/07, Rick DeNatale [email protected] 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
instead of
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
http://talklikeaduck.denhaven2.com/
On Apr 9, 2007, at 12:00 PM, Marcel W. wrote:
On 09/04/07, Rick DeNatale [email protected] 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 Q. 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 G. II
Marcel W. 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.
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
posted to learn more about Ruby. The thing is, simple, or not so
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
Robert D. wrote:
point
irb is our friend of course, so let us hack away:
Thanks for the explanation Robert. After reading over your email, I
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.
James G. wrote:
The three rules of Ruby Q.:
=] 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
uploaded it in a pastie.
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+50.67 = 130.35
123+4+56.7 = 160.50
0.123+4+5*67 = 339.12
…
17 times target reached, out of 217224 equations tested:
1234-567 = 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.3456+7 = 100.00
12+34.56+7 = 100.00
12+3450.6+7 = 100.00
-1-234+567 = 100.00
1234+56/7 = 100.00
-1/2+34-0.5+67 = 100.00
-1+0.2345+67 = 100.00
-1+23.45+67 = 100.00
-1+2340.5+67 = 100.00
1234-5+6+7 = 100.00
-1-2+345-67 = 100.00
-1/2+3/0.4/567 = 100.00
-1/2+3/4/0.567 = 100.00
Total run time: 50.844356 seconds
Trying to do that for digits 1 to 9 is a craziness @.@
Here is the file:
My first posted solution - hope it’s ok!
Start target.rb
class TargetFinder
attr_reader :inputs, :operators
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 Mon, 09 Apr 2007 21:47:43 +0900, Christian N. 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 4/11/07, Ken B. [email protected] 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:
- those people are also interested in clear idiomatic code
- I’m unlikely to be the one summarized.
Cheer up Ken;) Ruby Quiz - Method Auto Completion (#110)
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:
- those people are also interested in clear idiomatic code
- I’m unlikely to be the one summarized.
–Ken
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:
a = [1, Add, 2]
The Add Operator can then be called by either of these:
Add[a, 1]
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]
ops = [Add, Sub]
ops.each_uniq_permutation will yield [Add, Sub] and [Sub, Add]. Then
calling:
nums.each_mix(ops)
will yield each of:
1 2 Add Sub 3
1 Add 2 Sub 3
1 Add Sub 2 3
… 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]
-> [1, Add, 2, Mult, 23] # concat adjacent numbers
-> [1, Add, 46] # Mult has higher precedence than Add
-> [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 Q. 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
instead of
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 Q. 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[:/]
Add = 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,
Add => 0,
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 Q. 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 )