7
\$\begingroup\$

Prelude:

This task is taken from Five Problems Every Software Engineer Should Be Able to Solve in Less Than an Hour, which I really recommend.

The task:

Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100.

Winning Criteria:

Shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Are spaces allowed between the numbers, like 1 2 3+4+5 rather than 123+4+5? \$\endgroup\$ – Tim May 10 '15 at 16:27
  • 1
    \$\begingroup\$ Pretty similar to codegolf.stackexchange.com/questions/3019/… (this link allows for * & / and does not specify the target 100) \$\endgroup\$ – Kyle Kanos May 10 '15 at 17:44
13
\$\begingroup\$

Perl 5.10.0 - 50 46 45B

say for grep{eval==100}glob join'{,+,-}',1..9

Usage: perl -M5.10.0 scratch.pl (I think I get the version for free)

\$\endgroup\$
  • \$\begingroup\$ A very nice solution; both concise and fairly readable even without much knowledge of Perl. \$\endgroup\$ – JohnE May 10 '15 at 18:15
4
\$\begingroup\$

CJam, 43 40 bytes

"-"SL]8m*{A,2>.+1\+s}%{~]:+100=},N*S/'+*

Here is how it works:

"-"SL]                     e# This is an array containing -, space and empty character
                           e# This represents -, + and joints correspondingly
      8m*                  e# Get all cartesian products of these 3 strings of length 8
                           e# For instance, all cartesian products of length 2 are:
                           e# [["-" " "] ["-" "-"] ["-" ""] [" " " "] [" " "-"] [" " ""]
                           e# ["" " "] ["" "-"] ["" ""]]
         {          }%     e# Map these cartesian products over this loop
          A,2>             e# Get array [2, 3, 4, 5, 6, 7, 8, 9]
              .+           e# In-order concatenation of the above two arrays
                1\+s       e# Prepend 1 to the result from above and convert it to string
{        },                e# Now we have all possible strings of 1 to 9 with all possible
                           e# operators as well as joins (things like 567). Its time to
                           e# filter out what add up to 100
 ~                         e# Evaluate the string. This leaves some numbers on stack.
  ]:+                      e# Wrap those numbers in an array and take their sum
     100=                  e# Check if the sum is equal to 100
           N*              e# Join all filtered strings by newline
             S/'+*         e# We used space instead of +. So now we replace space with +

Try it online here

\$\endgroup\$
3
\$\begingroup\$

My shot at this:

Python 2, 93 bytes

def a(e,i):
 if i<=9:[a(e+x+`i`,i+1)for x in("+","-","")]
 elif eval(e)==100:print e
a("1",2)
\$\endgroup\$
  • 1
    \$\begingroup\$ You can use single space indents and also str(i) -> `i`. Also, you might want to mention that this is Python 2 specific :) \$\endgroup\$ – Sp3000 May 10 '15 at 16:52
  • \$\begingroup\$ @Sp3000 Thanks! I'm trying to improve my code golf skills and I'd never heard of the backtick thing. \$\endgroup\$ – James Williams May 10 '15 at 17:44
  • \$\begingroup\$ One of the best code I have ever seen... \$\endgroup\$ – Arun Joshla Apr 1 at 11:32
2
\$\begingroup\$

Mathematica, 93 92 bytes

Print/@Select[""<>ToString/@Range@9~Riffle~#&/@{"+","-",""}~Tuples~{8},ToExpression@#==100&]

Fairly straightforward: generates all possible strings using Tuples and then filters them.

For reference, I get:

1+2+3-4+5+6+78+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
123+4-5+67-89
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89
\$\endgroup\$
2
\$\begingroup\$

Pyth, 26 bytes

fqvT100m+ssC,r1Td9^c3"+-"8

First, we generate all 8 element combinations of ["+", "-", ""]. c3"+-" chops "+-" into 3 rougly equal sied pieces, giving the appropriate list. ^c3"+-"8 gives the 8 element combinations.

Then, we greate the arithmetic sequences. C,r1Td zips together the operators with the numbers 1 through 8, which are then summed twice to give the string, and + ... 9 puts a 9 at the end.

Finally, fqvT100 filters for those expressions which evaluate to 100.


The update to the interpreter which allowed this code to work was this one, which was made about a day before this question was asked, so this code would have only worked on the command line compiler, not the online one, when the question was asked.

Demonstration.

\$\endgroup\$
1
\$\begingroup\$

JavaScript, 86 92

Head to head with the best. That must be an anomalous problem.

Edit -6 thx @nderscore

for(i=6562;k=--i;eval(o)-100||alert(o))for(j=o=1;j++<9;k=k/3|0)o+=k%3?' +-'[k%3]+j:[j]

Test in any browser console, it pops up just 11 times.

Or this snippet:

function out(x) { OUT.innerHTML = OUT.innerHTML + '\n' + x; }

// 6562 is 3 powered to 8 +1
for(i=6562;k=--i;eval(o)-100||out(o))
  for(j=o=1;j++<9;k=k/3|0)
    o+=k%3?' +-'[k%3]+j:[j]
    
<pre id=OUT></pre>

\$\endgroup\$
  • \$\begingroup\$ Here's -6: for(i=6562;k=--i;eval(o)^100||alert(o))for(j=o=1;9>j++;k=k/3|0)o+=k%3?' +-'[k%3]+j:[j] \$\endgroup\$ – nderscore May 11 '15 at 1:56
  • \$\begingroup\$ @nderscore thanks, some obvious changes against my sloppy golfing, but the last trick with the ternary is very clever \$\endgroup\$ – edc65 May 11 '15 at 3:58
0
\$\begingroup\$

Python (176)

39 minutes and counting (for all problems that is)

from itertools import*
for i in product(('+','-',''),repeat=8):
 s=''.join(''.join(j)for j in chain(izip_longest(map(str,range(1,10)),i,fillvalue='')))
 if eval(s)==100:print s

This could probably be shorter, but this was my actual solution for this problem, just golfed down a bit.

\$\endgroup\$
0
\$\begingroup\$

K, 61 50 bytes

t@&100=.:'t:{:[x>9;,y;,/_f[x+1]'(y,"+";y,"-";y),\:$x]}[2;"1"]

Tested with Kona.

The general approach is to recursively generate all the expressions and then filter out those which eval (.) to 100. This is reasonably competitive as written, but I think there's still room for improvement.

edit:

t@&100=.:'t:(,"1"){,/x,/:\:("+";"-";""),\:$y}/2+!8

Altering my approach a bit to be iterative rather than recursive, which removes the need for explicit base cases as well as saving me some brackets.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.