8
\$\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\$
2
  • \$\begingroup\$ Are spaces allowed between the numbers, like 1 2 3+4+5 rather than 123+4+5? \$\endgroup\$
    – Tim
    Commented May 10, 2015 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
    Commented May 10, 2015 at 17:44

9 Answers 9

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\$
1
  • \$\begingroup\$ A very nice solution; both concise and fairly readable even without much knowledge of Perl. \$\endgroup\$
    – JohnE
    Commented May 10, 2015 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\$
3
  • 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
    Commented May 10, 2015 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\$ Commented May 10, 2015 at 17:44
  • \$\begingroup\$ One of the best code I have ever seen... \$\endgroup\$ Commented Apr 1, 2019 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\$

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\$
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\$
2
  • \$\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
    Commented May 11, 2015 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
    Commented May 11, 2015 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\$

APL(Dyalog Unicode), 54 50 48 bytes SBCS

↑b/⍨100=⍎¨b←{' '~⍨,(1↓⎕D),⍪⍵,' '}¨(,∘.,)⍣7⍨'-+ '

Try it on APLgolf!

A tradfn submission which uses strict right to left evaluation.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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