Close

Thank you!

We'll respond shortly.

LABS

Ruby 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

Post a Comment

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.

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

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) {}

});

});

});

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”]

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

This was fun…

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.

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!

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!

…of course his is JavaScript, and this

wassupposed to be a Ruby challenge… He could at least have done it in rjs… ;-)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

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

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

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

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 exitAnother 2 liner… that uses inject!

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.

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

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

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

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