1
\$\begingroup\$

Challenge

Given a positive integer \$N \ge 3\$, generate an alternating series of \$N\$ random numbers within the range \$[1, N]\$, such that their sum equals \$N\$. Expressed mathematically as

$$N = \sum_{i=1}^{N} (-1)^{i-1} a_i$$ where \$a_i \in [1,N]\$ are random terms.

Input

\$N\$

Output

A string representing the alternating series of \$N\$ terms (each prefixed by \$+\$ or \$-\$) that sum up to \$N\$.

Notes

Random numbers can be generated using any standard random number generation function. For example, rand() in C, random.randint() in Python, Math.random() in Javascript, etc.,...

Examples

N alternating series
3 +1-1+3
4 +4-1+3-2
5 +4-2+4-4+3
6 +5-1+4-4+3-1
7 +6-1+4-7+4-1+2
8 +6-7+7-5+7-1+2-1
9 +3-7+8-3+2-8+9-2+7
10 +10-4+4-2+8-3+1-4+5-5
11 +11-7+1-2+2-10+3-5+10-2+10
... ...
\$\endgroup\$
9
  • 4
    \$\begingroup\$ "Alternating" needs to be better defined within the spec here. \$\endgroup\$
    – Shaggy
    Feb 5 at 1:18
  • 7
    \$\begingroup\$ Do the outputs have to be equally likely? \$\endgroup\$
    – xnor
    Feb 5 at 2:11
  • 5
    \$\begingroup\$ Saying you should produce one or several outputs randomly without further specification is one of the things to avoid when writing challenges, and IMO just saying that you have to use a uniform RNG with values in \$[1,N]\$ isn't enough - do you have to use the straightforward rejection sampling algorithm? \$\endgroup\$ Feb 5 at 9:15
  • 3
    \$\begingroup\$ To solve the issue mentioned by xnor and Command Master, a simple solution could be requiring each possible output to have nonzero probability \$\endgroup\$
    – Luis Mendo
    Feb 5 at 12:44
  • 3
    \$\begingroup\$ @vengy choosing each term uniformly and testing for correctness repeatedly will be biased towards some answers over others (although all valid solutions are still possible outputs). \$\endgroup\$ Feb 5 at 17:36

8 Answers 8

2
\$\begingroup\$

Jelly, 15 bytes

ṗḅ-⁼ɗƇ⁸XṚṭNƭ€”+

A full program that accepts a positive integer, \$n\$, and prints a possible alternating sum, in the given format, with \$n\$ terms with absolute values from \$[1,N]\$.

All possible outputs are equally likely.

Try it online!

How?

ṗḅ-⁼ɗƇ⁸XṚṭNƭ€”+ - Main Link: positive integer, n
ṗ               - {[1..n]} Cartisian power {n}
                   -> all length n lists formed of values [1..n]
     Ƈ          - keep those for which:
    ɗ ⁸         -   last three links as a dyad - f(potential, n)
  -             -     literal -1
 ḅ              -     convert {potential} from base -1
                       -> last - penultimate + antepenultimate - ...
   ⁼            -     equals {n}?
       X        - uniform choice
        Ṛ       - reverse
            €   - for each:
           ƭ    -   alternate between:
         ṭ   ”+ -     a) tack to '+'; and
          N     -     b) negate
                - implicit, smashing print
\$\endgroup\$
2
  • \$\begingroup\$ \$[3,6]\$ run quicky, but \$7\$ onwards are really slow. Is that a result of the language? Thanks. \$\endgroup\$
    – vengy
    Feb 5 at 18:05
  • 3
    \$\begingroup\$ That is mostly a result of the implementation, it is first getting all \$n^n\$ possible arrays of \$n\$ numbers from the alphabet \$[1,n]\$. This is golf :) \$\endgroup\$ Feb 5 at 18:19
1
\$\begingroup\$

Google Sheets, 154 bytes

Assuming \$n\$ is in \$A1\$

=LET(F,LAMBDA(F,LET(o,JOIN(,MAKEARRAY(A1,1,LAMBDA(i,_,IF(MOD(i,2),"+","-")&RANDBETWEEN(1,A1)))),IF(A1=SORTN(QUERY(,"select "&MID(o,2,99))),o,F(F)))),F(F))

Recursive formula that generates a random sequence. If the sum is \$n\$, it returns it, otherwise it generates a new sequence and the process is repeated.

\$\endgroup\$
2
  • \$\begingroup\$ Looks like it works most of the time for the range [3,35], but higher values give an error. \$\endgroup\$
    – vengy
    Feb 5 at 3:46
  • \$\begingroup\$ I believe changing 99 to LEN(o) should fix the logic of the formula and maybe the error too. But performance-wise it's still going to be pretty bad. \$\endgroup\$
    – z..
    Feb 5 at 5:03
1
\$\begingroup\$

Python 3.8 (pre-release), 120 bytes

from random import*
def f(n):
 while sum(L:=[s*randint(1,n)for s in(1,-1)*n][:n])-n:1
 return''.join('%+d'%v for v in L)

Try it online!

Brute-force method. Generates a list of \$N\$ random numbers until their sum is equal to \$N\$.

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

05AB1E, 19 bytes

L¤ãε(2Å€Ä'+ì]ʒOQ}ΩJ

Try it online or verify all possible results for a given input.

ε(2Å€Ä'+ì] could alternatively be ε'+ìι`(.ι} for the same byte-count:

Try it online or verify all possible results for a given input.

Explanation:

L             # Push a list in the range [1, (implicit) input]
 ¤            # Push its last item (without popping): the input
  ã           # Cartesian product to have all possible input-sized lists
   ε          # Map over each inner list:
    (         #  Negate all values
     2Å€      #  Then for every 2nd item (0-based index is divisible by 2):
        Ä     #   Absolute value to make the negative value positive again
         '+ì '#   Prepend a "+" instead
   ]          # Close both the every and outer maps
    ʒ         # Filter:
     O        #  Sum the values in the list together
      Q       #  Check whether this is equal to the (implicit) input-integer
    }Ω        # After the filter: keep a random inner list
      J       # Join it together to a single string
              # (which is output implicitly as result)

   ε          # Map over each inner list:
    '+ì      '#  Prepend a "+" before each value
       ι      #  Uninterleave the list into two parts
        `     #  Pop and push both parts separately to the stack
         (    #  Negate the values in the top list
          .ι  #  Interleave the two lists back together
   }          # Close the map
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 25 bytes

NθW⁻↨⮌υ±¹θ≔Eθ⊕‽θυ⭆υ⁺§+-κι

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input N.

W⁻↨⮌υ±¹θ

Until interpreting the reverse of the predefined empty list as base -1 results in N, ...

≔Eθ⊕‽θυ

... assign N random integers in the range 1..N to the list.

⭆υ⁺§+-κι

Output the list with + and - signs inserted as appropriate.

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

Pyth, 20 bytes

s+V*"+-"QOf!u-HGTQ^S

Try it online!

Explanation

s+V*"+-"QOf!u-HGTQ^SQQ    # Implicitly add QQ
                          # Implicitly assign Q = eval(input())
                   SQ     # range(1, Q+1)
                  ^  Q    # repeated cartesian product, Q times
          f               # filter over lambda T
            u-HGTQ        #   reduce T over subtraction with Q as the starting value
           !              #   true if 0
         O                # choose a random value from the list
 +V                       # vectorized addition with
   *"+-"Q                 # "+-" repeated Q times
s                         # join into one string
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 74 bytes

f=(n,i,s)=>i^n?f(n,-~i,[s]+"+-"[i&1]+-~(Math.random()*n)):eval(s)-n?f(n):s

Try it online!

Commented

f = (               // f is a recursive function taking:
  n,                //   n = input
  i,                //   i = counter, initially undefined
  s                 //   s = output string, initially undefined
) =>                //
i ^ n ?             // if i is not equal to n:
  f(                //   do a recursive call:
    n,              //     pass n unchanged
    -~i,            //     increment the counter
    [s] +           //     append to s ...
    "+-"[i & 1] +   //     ... either "+" or "-" according to
                    //     the parity of i
    -~(             //
      Math.random() //     followed by a random integer
      * n           //     in [1, n]
    )               //
  )                 //   end of recursive call
:                   // else:
  eval(s)           //   evaluate the expression
  - n ?             //   if the result is not equal to n:
    f(n)            //     try again
  :                 //   else:
    s               //     stop and return it
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 118 112 bytes

-6 bytes, thanks to @Arnauld

i=0,s=0,a[];f(n){for(s=0;s-n;)for(i=s=0;i<n;)s+=a[i++]=(i%2*2-1)*~(rand()%n);for(i=0;i<n;)printf("%+d",a[i++]);}

Try in online!

\$\endgroup\$
1

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