8
\$\begingroup\$

Write a program or function to produce the following output in the correct order.

EDIT: The symbols are not mathematical! The numbers just represent unique data and the + and - could be any two arbitrary symbols.

Take an non-negative integer input n. The first line is always -, even for n=0.

  • If the current line is -, the next line is 1+2+ ... (n-1)+n-
    • n=4: - => 1+2+3+4-
  • If the last integer is equal to n, remove all integers from the end that are immediately followed by a -, then change the last + to a -
    • n=4: 1-2+3-4- => 1-2-
    • EDIT: When the string is full (all the integers from 1 to n are included), remove all integers from the end that are followed by a -, until you reach an integer followed by a +. Leave that integer but change its following + to a -
    • Using the same example as immediately above (which does not follow -), remove 4-, remove 3-, change 2+ to 2-. 1- doesn't change since we stop at 2. Result: 1-2-
  • If the last integer is less than n, append the remaining integers with a + after each one, except the final integer which should have a - appended
    • n=4: 1+2- => 1+2-3+4-
    • EDIT: If the current string is not full (does not contain all the integers from 1 to n), add each integer not already included in ascending order up to n-1 with a + after each one, and then append the last integer n followed by a -
    • If the current line is 1-, append 2+, append 3+ which is n-1 if n=4. Then append 4-. Result: 1-2+3+4-
  • If the current line contains all the integers and each one is immediately followed by a -, exit the code
    • n=4: 1-2-3-4- => END

There must be no leading or trailing spaces on any line. There must be a line break between each line. There may or may not be a line break on the last line.

EDIT: You should test your code up to at least n=10 (over 1000 lines of output so I can't include it here). Any number that doesn't cause your code to run out of resources should (eventually!) produce the correct output but you don't have to wait for the universe to end!

This is , so shortest code in bytes wins!

Input n=0:

-

Input n=1:

-
1-

Input n=2:

-
1+2-
1-
1-2-

Input n=4:

-
1+2+3+4-
1+2+3-
1+2+3-4-
1+2-
1+2-3+4-
1+2-3-
1+2-3-4-
1-
1-2+3+4-
1-2+3-
1-2+3-4-
1-2-
1-2-3+4-
1-2-3-
1-2-3-4-
\$\endgroup\$
5
\$\begingroup\$

Haskell, 89 bytes

g takes an integer and returns a string.

g n=unlines$max"-".foldr(\(s,i)r->id=<<[show i++s:r|s:r>"+"])""<$>mapM(mapM(,)"+-")[1..n]

Try it online!

How it works

  • Loosely speaking, the algorithm constructs a list of all 2^n combinations 1+2+...n+, 1+2+...n- up to 1-2-...n-, strips away the final +-terminated numbers, and if the result is empty, replaces it with -.

  • mapM(,)"+-" is a shorter way (using the function monad) to write \i->[('+',i),('-',i)].

  • mapM(mapM(,)"+-")[1..n] generates (using the list monad for the outer mapM) a list with all combinations as lists of tuples e.g. [(1,'+'),(2,'-'),...,(n,'+')].
  • foldr ... <$> ... combines each of these lists of tuples into a string, using the lambda expression to build it from the right.
    • (s,i) is a tuple of a sign and a number, and r is the string constructed from the tuples to its right.
    • id=<<[show i++s:r|s:r>"+"] prepends i and s to the string r constructed so far, but not if the sign s is positive and r is empty.
      • This is tested by comparing s:r to "+". By luck this is the lexicographically smallest string that can result from concatenating them, so the comparison can use > rather than /=.
  • Also by luck, "-" is smaller than any nonempty string that can be constructed by the fold, so the empty string can be replaced with it by using max.
  • Finally unlines turns the strings into a single string of lines.
\$\endgroup\$
5
\$\begingroup\$

Python 2, 101 bytes

n=input()
for i in range(2**n):s='';m=n;exec"s=`m`+'+-'[i%2]+s;s*='-'in s;i/=2;m-=1;"*m;print s or'-'

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Nice use of s*=<condition> \$\endgroup\$
    – Chas Brown
    Jul 14 '17 at 4:00
3
\$\begingroup\$

Python 2, 136 141 133 bytes

def f(n,s="+"):
 while"+"in s:s=s[:s.rfind("+")]+"-";print s[s>"-":];s+="+".join(map(str,range(len(s)/2+1,n+1)))+"-";print(n>0)*s[1:]

Try it online!

The first - (un)surprisingly added a fair few bytes to the code.

\$\endgroup\$
6
  • \$\begingroup\$ So the string manipulation solution was shorter after all? \$\endgroup\$
    – hyper-neutrino
    Jul 14 '17 at 1:45
  • \$\begingroup\$ Or I'm just bad :P \$\endgroup\$
    – hyper-neutrino
    Jul 14 '17 at 1:45
  • \$\begingroup\$ The approach does seem to be shorter, but there are a few things that could be improved on yours; I'll post a comment with some tips in a bit. \$\endgroup\$
    – notjagan
    Jul 14 '17 at 1:47
  • \$\begingroup\$ n=0 incorrectly produces two - lines. \$\endgroup\$
    – CJ Dennis
    Jul 14 '17 at 2:20
  • \$\begingroup\$ @CJDennis Fixed. \$\endgroup\$
    – notjagan
    Jul 14 '17 at 2:51
3
\$\begingroup\$

Python 2, 150 164 159 154 146 118 bytes 115 112 bytes

def f(n,i=0):
 while i<2**n:t=''.join(`j+1`+'+-'[i>>n+~j&1]for j in range(n));print t[:t.rfind('-')+1]or'-';i+=1

Try it online!

Edit: Oops! It has to work for numbers greater than 4 as well... then chip away... until I realized I was overthinking it and saved 28 bytes... and then 6 more via little golfs.

\$\endgroup\$
4
  • \$\begingroup\$ Output is incorrect for input above n=4. \$\endgroup\$
    – CJ Dennis
    Jul 14 '17 at 2:22
  • \$\begingroup\$ @CJ Dennis I think it works now; output is the same as notjagan for,e.g, n=5 \$\endgroup\$
    – Chas Brown
    Jul 14 '17 at 2:38
  • \$\begingroup\$ The output appears to be correct now! I'll add that you should test to at least 10... \$\endgroup\$
    – CJ Dennis
    Jul 14 '17 at 2:46
  • \$\begingroup\$ I just noticed that you set i=0 in the input! That means I can just generate lines from i onwards, such as f(24,16777200)! :-) \$\endgroup\$
    – CJ Dennis
    Jul 15 '17 at 13:16
3
\$\begingroup\$

Pyth, 23 bytes

j+\-mssVSQd<Lx_d\-t^"+-

Demonstration

The basis of this program is noticing that other than the initial -, the plus and minus sequence corresponds to the standard sequence of combinations of + and - with replacement, with all trailing + removed.

Explanation:

j+\-mssVSQd<Lx_d\-t^"+-
j+\-mssVSQd<Lx_d\-t^"+-"Q    Implicit string completion and variable introduction
                   ^"+-"Q    Form all sequences of + and - of length equal to
                             the input, ordered lexicographically.
                  t          Remove the first one, which we don't use.
           <L                Take the prefix of each one of length
             x               index in
              _d             the reversed string
                \-           of '-'.
    m                        Map the results to
      sV                     Apply the sum function to pairs of
        SQ                   [1, 2, 3 ... input]
          d                  and the previous string
     s                       Sum the pairs.
 +\-                         Add a '-' on to the front of the list
j                            Join on newlines.
\$\endgroup\$
2
\$\begingroup\$

Python 2, 73 bytes

f=lambda n,a=2,d='\n1':a<n+2and f(n,a+1,d+'+'+`a`)+d+f(n,a+1,d+`-a`)or'-'

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Haskell, 70 bytes

f n=unlines$"-":foldr(\i x->tail[show i++s:y|s<-"+-",y<-"":x])[][1..n]

Try it online!

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

Python 3, 305 bytes

x=int(input())
o=lambda:list(range(1,x+1))or[0]
q=o()
q[-1]*=-1
print('-')
def f(a):print(''.join(str(abs(x))+'-+'[x>0]for x in a))
while any([k>0 for k in q])or[-k for k in q]!=o():
	f(q)
	if-q[-1]==x:
		while q[-1]<0:q=q[:-1]
		q[-1]*=-1
	elif-q[-1]<x:
		while q[-1]<x:q+=[abs(q[-1])+1]
		q[-1]*=-1
f(q)

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ I'm a bit confused by your tab/space mixing. First I didn't even think you COULD in Python 3, and second it seems to serve little purpose? Why bother doing <tab><space> when <space><space> would be the same # of bytes? I guess perhaps if you did the small indents with <space> and the larger with <tab> it would be saving a byte... \$\endgroup\$
    – nmjcman101
    Jul 14 '17 at 1:51
  • \$\begingroup\$ @nmjcman101 erm. I must be really tired, or stupid, or both. I was trying to save bytes by doing that space/tab indent not tab/tabspace >< thanks! \$\endgroup\$
    – hyper-neutrino
    Jul 14 '17 at 1:55
  • \$\begingroup\$ This is 17 bytes shorter, but it does exit on an error. Still trying to shorten that pesky q[-1] to q[0]. BTW: mixing tabs and spaces doesn't work in Python 3, so the current code yields an error. \$\endgroup\$
    – notjagan
    Jul 14 '17 at 1:58
  • \$\begingroup\$ @notjagan oh hm. never mind then, it must have been because earlier I was being dumb :P but okay, thanks for the suggestion; i'll try to work from there \$\endgroup\$
    – hyper-neutrino
    Jul 14 '17 at 2:18

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.