Close
Glad You're Ready. Let's Get Started!

Let us know how we can contact you.

Thank you!

We'll respond shortly.

LABS
Ruby Puzzler

puzzler I was just sitting around my living room listening to NPR, and heard the following Car Talk puzzler:

I want you to get a pencil and write down the numbers, 1 – 9, inclusive, and leave enough space between them. At your disposal you have one plus sign and two minus signs. You can insert those plus and minus signs wherever you want, to make the total come out to 100.

Naturally, I thought, “Gee, that would be tedious to solve it by hand. But it would be fun to write a Ruby program to solve it!” 9 minutes later I was sending the result (and the source code) to Car Talk Plaza.

So here’s your challenge: can you write a program to solve this puzzle? And can you beat my time?

My solution is below the fold… don’t click “more” until you’ve taken a stab at it yourself.

#!/usr/local/bin/ruby

(1..8).each do |plus|
  (1..8).each do |minus1|
    next if minus1 == plus
    ((minus1+1)..8).each do |minus2|
      next if minus2 == minus1 or minus2 == plus
      exp = ""
      (1..9).each do |digit|
        exp = "#{exp}#{digit}"
        exp = "#{exp}+" if digit==plus
        exp = "#{exp}-" if digit==minus1 or digit==minus2
      end
      x = eval(exp)
      if x == 100
        puts "#{exp}=#{x}"
      end
    end
  end
end

And a follow-on challenge: can you refactor my code to make it either clearer or more concise (i.e. obfuscated)?

Comments
  1. Dav says:

    I just did a brute force, and it took me 17 minutes. I got hung up on the pattern/regex part. Yours is prettier too. Oooo, the pain! I was expecting more than winner for some reason.

    
    class CarTalk
    
      def initialize
        @str = '123456789'
        @winners = []
      end
    
    
      def check_result( pattern, a, b, c, d )
        formula = "#{a} #{pattern[/(.)../,1]} #{b} #{pattern[/.(.)./,1]} #{c} #{pattern[/..(.)/,1]} #{d}"
        result = 0
        eval "result = #{formula}"
        puts formula + ' = ' + result.to_s
        @winners < < formula if result == 100
      end
    
      def run
        workstr = @str.dup
        for i1 in 0..(workstr.length-4) do
          slice0 = workstr.slice(0..i1)
          for i2 in (i1+1)..(workstr.length-3) do
            slice1 = workstr.slice(i1+1..i2)
            for i3 in (i2+1)..(workstr.length-2) do
              slice2 = workstr.slice(i2+1..i3)
              slice3 = workstr.slice(i3+1..workstr.length)
              check_result '+--', slice0, slice1, slice2, slice3
              check_result '-+-', slice0, slice1, slice2, slice3
              check_result '--+', slice0, slice1, slice2, slice3
            end
          end
        end
        @winners.each { |f| puts "#{f} = 100!" }
      end
    end
    
    CarTalk.new.run
    
  2. Dav says:

    Hmm, stupid markdown ate half my code. Trying again:

    class CarTalk

    def initialize
    @str = ‘123456789’
    @winners = []
    end

    def check_result( pattern, a, b, c, d )
    formula = “#{a} #{pattern[/(.)../,1]} #{b} #{pattern[/.(.)./,1]} #{c} #{pattern[/..(.)/,1]} #{d}”
    result = 0
    eval “result = #{formula}”
    puts formula + ‘ = ‘ + result.to_s
    @winners << formula if result == 100 end def run workstr = @str.dup for i1 in 0..(workstr.length-4) do slice0 = workstr.slice(0..i1) for i2 in (i1+1)..(workstr.length-3) do slice1 = workstr.slice(i1+1..i2) for i3 in (i2+1)..(workstr.length-2) do slice2 = workstr.slice(i2+1..i3) slice3 = workstr.slice(i3+1..workstr.length) check_result ‘+–‘, slice0, slice1, slice2, slice3 check_result ‘-+-‘, slice0, slice1, slice2, slice3 check_result ‘–+’, slice0, slice1, slice2, slice3 end end end @winners.each { |f| puts “#{f} = 100!” } end end CarTalk.new.run

  3. Erik says:

    Here’s my entry, in JS. Requires prototype.js.

    String.prototype.insert = function(i,s) {
    return this.substring(0,i) + s + this.substring(i);
    }

    $R(1,8).each(function(m1) {
    $R(1,8).each(function(m2) {
    $R(1,8).each(function(p1) {
    var x = “123456789”.insert(m1,”-“).insert(m2+1,”-“).insert(p1+2,”+”);
    try {if (eval(x) == 100) alert(x);} catch(e) {}
    });
    });
    });

  4. Alex says:

    I guess you meant “I was expecting more than one winner.” Yeah, me too. Actually, the reason I say “puts “#{exp}=#{x}”“ even though x is always 100 is that I first ran it on all 168 combinations just to see. And I just fiddled with my code to find that there are only 2 duplicates (both negative):

    -355=[“1-23+456-789″, “12-345+67-89″]
    -610=[“1+234-56-789″, “12+34-567-89″]

  5. Chad says:

    Here’s mine, brute force too. However, my algorithm does have the benefit of being able to work on any arbitrary set of numbers, of any size or in any order.

    a=[]
    i = 1
    0.step(17,2) do |index|
    a[index] = i
    a[index+1] = ”
    i = i + 1
    end

    combos = [[‘-‘,’-‘,’+’],[‘-‘,’+’,’-‘],[‘+’,’-‘,’-‘]]
    combos.each do |combo|
    1.step(16,2) do |index1|
    a[index1] = combo[0]
    (index1+2).step(16,2) do |index2|
    a[index2] = combo[1]
    (index2+2).step(16,2) do |index3|
    a[index3] = combo[2]
    expression = a.join(”)
    sum = eval(expression)
    p “#{expression} = #{sum}” if sum == 100
    a[index3] = ”
    end
    a[index2] = ”
    end
    a[index1] = ”
    end
    end

  6. Yogi says:

    This was fun…

    a = (1..9).to_a
    
    c = []
    (0..6).each {|x|
      ((x+1)..7).each {|y|
        ((y+1)..8).each {|z|
          next if z == 8
          c << [ a[0..x].to_s, a[(x+1)..y].to_s, a[(y+1)..z].to_s, a[(z+1)..8].to_s ]
        }
      }
    }
    
    [ %w{- - +}, %w{- + -}, %w{+ - -} ].each {|ops|
      c.each{|nums|
        expr = "#{nums[0]} #{ops[0]} #{nums[1]} #{ops[1]} #{nums[2]} #{ops[2]} #{nums[3]}"
        res = eval expr
        puts expr if res == 100
      }
    }
    
  7. I was going to parameterize this more, but it would have sacrificed readability, so I didn’t. I’m surprised nobody else tried inserting the operators and evaling the string. Came out nice and compact.

    #!/usr/bin/env ruby
    
    source = "123456789"
    target_value = 100
    
    (0..8).each do |i|
      sub1 = source.dup.insert(i, "-")
      (0..9).each do |j|
        sub2 = sub1.dup.insert(j, "+")
        (0..10).each do |k|
          sub3 = sub2.dup.insert(k, "-")
          puts sub3 if (target_value == (eval sub3))
        end
      end
    end
  8. Alex says:

    I’m surprised nobody else tried inserting the operators and evaling the string

    Huh? All of us evaled the string, and Erik did an insert. (The rest of us did an append, which is arguably equivalent.)

    Looks like the insert method is more compact, and as readable, so I think you and Erik get the prize. Which is… nothing! Congratulations!

  9. Ian says:

    Oh, oops. Good point. Well, it was really late when I did the challenge, and I didn’t read them to avoid prejudicing myself. :-)

    More what I meant to say was I was surprised more folks didn’t just manipulate the string directly, then eval that. But as you point out, that’s pretty much what Erik did. I will be happy to share my prize with him!

  10. Ian says:

    …of course his is JavaScript, and this was supposed to be a Ruby challenge… He could at least have done it in rjs… ;-)

  11. Chad says:

    Actually, Erik, me, you and Yogi all used an eval approach. Only Dav and Alex didn’t.

    I think this is a telling statement on how someone approaches a problem. I personally was never good at math, so I definitely went for the eval route. I’m all about the string manipulation, I guess it comes from writing too much REXX at IBM back in the day :)

    — Chad

  12. Erik says:

    Oh yeah, I was supposed to do it in Ruby. Um, just pretend that it was all wrapped in <%= and %> :)

    I’m suprised that my JS implementation was shorter than any of the Ruby implementations. As much as I like JS (ducks), I find that Ruby code is usually shorter and clearer than JS code. (Perhaps I just took more shortcuts than the other contestants…)

    Since I didn’t follow the rules, I concede the prize to Ian.

    Ian, don’t ever say I never gave you nothing :)

  13. steve dp ( from Zubio ) says:

    Here’s what I came up with in 10 minutes to get the answer….

    def e(so, indexes)
      s = ""; so = so.dup
      (1..9).each { |num| s << num.to_s; s << so.shift  if indexes.include? num }
      eval(s)
    end
    
    (1..8).each { |i| (1..8).each { |j| (1..8).each { |k|
      [%w(+ - -), %w(- + -), %w(- - +)].each do |ops|
        puts "#{ops.inspect}: [#{i}, #{j}, #{k}]" or exit  if e(ops, [i, j, k]) == 100
      end
    }}}
    

    Erik’s JS inspired me to write this 2 liner (not going over 80 cols)

    ('1'..'8').each { |i| (i.succ..'8').each { |j| (j.succ..'8').each { |k|
    puts @s if eval(@s="123456789".sub(i,i+'-').sub(j,j+'-').sub(k,k+'+'))==100}}}
    
  14. steve dp says:

    doh, just realized the i.succ and j.succ are unnecessary and would miss answers other than 100 by always keeping sign order the same. shameful exit

  15. steve dp says:

    Another 2 liner… that uses inject!

    ('1'..'8').each{|i|('1'..'8').each{|j|('1'..'8').each{|k|p @s if eval(@s=('1'..
    '9').to_a.inject(""){|s,n|s+n+((o=%w(- + -)[(i+j+k=~/#{n}/)||9])?o:'')})==100}}}
    
  16. JohnB says:

    This took much longer than the allotted 10 minutes – but its the distillation of my initial idea: permute the array of operators and merge it into the array of numbers. It gets ugly due to an eval failure when an operator is past the last digit.

    recurse( 9, ['','','','','','','+','-','-',''] )
    def recurse depth, operators
      recurse( depth - 1, shuffle(operators) ) if depth > 0
      guess = shuffle( ['1','2','3','4','5','6','7','8','9',''] + operators ).join
      puts "#{guess} equals 100" if guess =~ /ds*$/ and 100 == eval(guess)
    end
    def shuffle array
      mid = array.length / 2
      [array[0..(mid-1)],array[mid..-1]].transpose.flatten
    end
    

    If we only had Array.permute(&block) then I think it could be much smaller…

  17. Adam Milligan says:

    I just came across this somewhat randomly. I didn’t time how long it took, but I came up with almost an identical solution to Alex’s original. With a few renamed variables to make it consistent with Alex’s solution:

    (2..9).each do |plus|
    (2..9).each do |minus1|
    next if minus1 == plus
    ((minus1 + 1)..9).each do |minus2|
    next if minus2 == plus

    result = eval(expression = (1..9).inject([]) do |expr, digit|
    expr << ” + ” if digit == plus expr << ” – ” if digit == minus1 || digit == minus2 expr << digit end.join) puts “#{expression} = #{result}” if result == 100 end end end

  18. Erik says:

    Here’s a different approach:

    begin
    s = ‘123456789’
    3.times { |n| s.insert(rand(s.size), %w(+ – -)[n]) }
    end until eval(s) == 100
    puts s

  19. Erik says:

    Markdown took out the percent sign in front of my “w”….

Post a Comment

Your Information (Name required. Email address will not be displayed with comment.)

* Copy This Password *

* Type Or Paste Password Here *