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)?
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.
December 12, 2007 at 11:50 pm
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
December 12, 2007 at 11:50 pm
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) {}
});
});
});
December 12, 2007 at 11:50 pm
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"]
December 12, 2007 at 11:50 pm
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
December 12, 2007 at 11:50 pm
This was fun…
December 12, 2007 at 11:50 pm
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 endDecember 12, 2007 at 11:50 pm
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!
December 12, 2007 at 11:50 pm
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!
December 12, 2007 at 11:50 pm
…of course his is JavaScript, and this was supposed to be a Ruby challenge… He could at least have done it in rjs… ;-)
December 12, 2007 at 11:50 pm
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
December 12, 2007 at 11:50 pm
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 :)
December 12, 2007 at 11:50 pm
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)
December 12, 2007 at 11:50 pm
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
December 12, 2007 at 11:50 pm
Another 2 liner… that uses inject!
December 12, 2007 at 11:50 pm
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…
December 12, 2007 at 11:50 pm
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
September 21, 2008 at 7:36 pm
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
September 22, 2008 at 7:09 am
Markdown took out the percent sign in front of my “w”….
September 22, 2008 at 7:13 am