[QUIZ] Getting to 100 (#119)

ruby-talk
21

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 :slight_smile:
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"

22

=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. Additional
operations can be added by changing the base and mapping the digits onto
further operations. (Different digit order is not that easy to
implement and maybe be futile to do with brute-forcing.) =end

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

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

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

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

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

__END__

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

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

···

On Mon, 09 Apr 2007 01:39:19 +0900, Christian Neukirchen wrote:

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

23

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 4/8/07, Christian Neukirchen <chneukirchen@gmail.com> wrote:

(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
  }

24

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 Apr 8, 2:59 pm, "Carl Porth" <badc...@gmail.com> wrote:

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"

25

Christian Neukirchen wrote:

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

__END__

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

I'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

26

Welcome to Ruby Quiz.

James Edward Gray II

···

On Apr 8, 2007, at 10:10 PM, Matt Hulse wrote:

My first quiz attempt ever so go easy on me :slight_smile:

27

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 Gray II

···

On Apr 8, 2007, at 10:10 PM, Matt Hulse wrote:

Comments are welcome, I'm here to learn!

28

OK only 43 hours to go...

Stupid non spoiler rule

29

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.

--
Ist so, weil ist so
Bleibt so, weil war so

30

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

31

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 Sun, 08 Apr 2007 23:25:14 +0900, Kyle Schmitt wrote:

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

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

Enjoy!

--Kyle

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

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

to100 = Hash.new()

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

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

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

@oplength = @operator.length

keylength = @oplength.power!(@maxops)

def bogoGen()

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

    >i>

    if i.modulo(2)==0 then

      i=i/2

      i+=1

    else

      i=@operator[rand(@oplength)]

    end

  end

  return(little.join)

end

writingHamlet = Time.now()

while to100.keys.length<keylength

  elegance = bogoGen()

  to100.store(elegance,eval(elegance))

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

end

millionMonkeys = Time.now()

to100.sort.each do

  >answer>

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

  #display the answer!

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

end

willFinish = Time.now()

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

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

#compact v1
t={}

while t.length<(6561)

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

  t.store(e,eval(e))

end

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

#compact v2
t={}

while t.length<(6561)

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

end

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

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

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

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

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

32

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
as you add operators though.

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

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

Ryan

···

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.

33

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 :slight_smile:

···

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.

--
Marcel

34

Actually I have no idea whatsoever, this is normally a good starting point :wink:
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 :frowning:

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 4/9/07, Raj Sahae <rajsahae@gmail.com> wrote:

Christian Neukirchen wrote:
> =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.
> 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 }.
> map { |x|
> t = "1" + x.split(//).zip((2..9).to_a).join.delete(" ")
> [eval(t), t]
> }.sort.each { |s, x|
> puts "*****************" if s == 100
> puts "#{x}: #{s}"
> puts "*****************" if s == 100
> }
>
> __END__
>
> 2#787<p4>lilith:~/mess/current$ ruby quiz119.rb |grep -C4 100$
> 123-456-7+89: -251
> 123+45-67-89: 12
> 123-45+67-89: 56
> *****************
> 123-45-67+89: 100
> *****************
> 12+345-67-89: 201
> 1-234+567-89: 245
> 1-23-456+789: 311
>
I'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

--
You see things; and you say Why?
But I dream things that never were; and I say Why not?
-- George Bernard Shaw

35

Ken Bloom <kbloom@gmail.com> writes:

···

On Mon, 09 Apr 2007 01:39:19 +0900, Christian Neukirchen wrote:

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

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!

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org

36

"Ryan Leavengood" <leavengood@gmail.com> writes:

(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
  }

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 4/8/07, Christian Neukirchen <chneukirchen@gmail.com> wrote:

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org

37

Did you get all the extra credit already?

···

On Apr 6, 12:11 pm, "Kyle Schmitt" <kyleaschm...@gmail.com> wrote:

OK only 43 hours to go...

Stupid non spoiler rule

38

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 :slight_smile:

Ryan

···

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.

39

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:

> 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 :slight_smile:

--
Marcel

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

Harrison

···

On Apr 8, 9:21 pm, "Marcel Ward" <ward...@gmail.com> wrote:

On 08/04/07, Carl Porth <badc...@gmail.com> wrote:

40

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

···

On 4/8/07, Marcel Ward <wardies@gmail.com> wrote:

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 :slight_smile:

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/