Make a one sequence

Question

A sequence of integers is a one-sequence if the difference between any two consecutive numbers in this sequence is -1 or 1 and its first element is 0.

More precisely: \$a_1, a_2, ..., a_n\$ is a one-sequence if:

$$\forall k \::\: 1\le k<n, |a_k-a_{k+1}| = 1 \\ a_1 = 0$$

Input

• \$n\$ - number of elements in the sequence
• \$s\$ - sum of elements in the sequence

Output

• a one-sequence set/list/array/etc of length \$n\$ with sum of elements \$s\$, if possible
• an empty set/list/array/etc if not possible

Examples

For input 8 4, output could be [0 1 2 1 0 -1 0 1] or [0 -1 0 1 0 1 2 1]. There may be other possibilites.

For input 3 5, output is empty [], since it cannot be done.

Rules

This is a code golf, shortest answer in bytes wins. Submissions should be a program or function. Input/output can be given in any of the standard ways.

Answer 1

JavaScript (E6) 79 82

F=(n,t,
  d=n+n*~-n/4-t/2,
  l=1,
  q=[for(x of Array(n))d<n--?++l:(d+=~n,--l)]
)=>d?[]:q

No need of brute force or enumeration of all tuples.

See a sequence of length n as n-1 steps, each step being increment or decrement.
Note, you can only swap an increment for a decrement, sum varies by 2, so for any given length the sum is always even or always odd.
Having all increments, the sequence is 0, 1, 2, 3, ..., n-1 and we know the sum is (n-1)*n/2
Changing the last step, the sum changes by 2, so the last step weighs 2.
Changing the next to last step, the sum changes by 4, so the last step weighs 4. That's because the successive step builds upon the partial sum so far.
Changing the previous step, the sum changes by 6, so the last step weighs 6 (not 8, it's not binary numbers).
...
Changing the first step weighs (n-1)*2

Algorithm

Find the max sum (all increments)  
Find the difference with the target sum (if it's not even, no solution)  
Seq[0] is 0  
For each step  
  Compare current difference with the step weight
  if is less 
     we have an increment here, seq[i] = seq[i-1]+1 
  else 
     we have a decrement here, seq[i] = seq[i-1]-1.  
     Subtract we current weight from the current diff.
If remaining diff == 0, solution is Seq[]. Else no solution

Ungolfed code

F=(len,target)=>{
  max=(len-1)*len/2
  delta = max-target
  seq = [last=0]
  sum = 0
  weight=(len-1)*2
  while (--len > 0)
  {
    if (delta >= weight)
    {
      --last
      delta -= weight;
    }
    else
    {
      ++last
    }  
    sum += last
    seq.push(last);
    weight -= 2;
  }  
  if (delta) return [];
  console.log(sum) // to verify

  return seq
}

Test In Firefox / FireBug console

F(8,4)

Output

[0, -1, 0, -1, 0, 1, 2, 3]

Answer 2

CJam, 56 47 44 34 bytes

A lot of scope for improvement here, but here goes the first attempt at this:

L0aa{{[~_(]_)2++}%}l~:N;(*{:+N=}=p

Credits to Dennis for efficient way of doing the { ... }% part.

Prints the array representation if possible, otherwise ""

Try it online here

Answer 3

GolfScript (41 39 bytes)

[][1,]@~:^;({{.-1=(+.)))+}%}*{{+}*^=}?`

Online demo

Thanks to Dennis for 41->39.

Answer 4

Jelly, 11 bytes

’Ø-ṗÄS=¥ƇḢŻ

Try it online!

Although I originally had ’2*ḶBz0Z-*ÄS=¥ƇḢŻ, this is close enough to caird's solution in principle now that I'm almost tempted to just suggest it in the comments. In the case that you really really want [] over 0, maybe it's just +3 bytes?, maybe it's +5.

 Ø-            [-1, 1]
   ṗ           to the Cartesian power of
’              n - 1.
    Ä          Cumulative sums.
        Ƈ      Keep only those for which
     S ¥       the sum
      =        is equal to s.
         Ḣ     Take the first survivor
          Ż    and slap a 0 on the start of it.

Answer 5

Mathematica, 73 bytes

f=FirstCase[{0}~Join~Accumulate@#&/@Tuples[{-1,1},#-1],l_/;Tr@l==#2,{}]&;

Simple brute force solution.

I'm generating all choices of steps. Then I turn those into accumulated lists to get the one-sequences. And then I'm looking for the first one whose sum is equal to the second parameter. If there is non, the default value is {}.

Answer 6

Haskell, 56 bytes

n%s=[x|x<-scanl(+)0`map`mapM(\_->[1,-1])[2..n],s==sum x]

Explanation:

• Build a list with the permutations of 1,-1 and length n-1: replicateM n-1[-1,1]
  Example: replicateM 2 [-1,1] == [[-1,-1],[-1,1],[1,-1],[1,1]]
• Build the one-sequence out of it. scanl has poor performance, but it does the right job here.
• Filter all possible one-sequences with length n where the sum is s

Answer 7

Husk, ¹⁴ 16 bytes

ḟo=⁰ΣmΘm∫π←²fIṡ1

Try it online!

Same idea as Unrelated String's answer. I'll add in a version that returns [] once I can find a way to make if work properly.

Now works as advertised!

Answer 8

Python, 138

from itertools import*
def f(n,s):
 for i in[list(accumulate(x))for x in product([-1,1],repeat=n-1)]:
  if sum(i)==s:return[0]+i
 return[]

Answer 9

Python 3, 80 bytes

f=lambda l,s,a=[0]:l>1and max(f(l-1,s,a+[a[-1]+x])for x in(1,-1))or(sum(a)==s)*a

Try it online!

Answer 10

Jelly, 18 16 bytes

’Ø-œċŒ!€ẎÄS=¥ƇḢŻ

Try it online!

Returns 0 if no such list exists. If you insist on returning [], +5 bytes.

-2 bytes thanks to Unrelated String

How it works

Rather than generating all possible lists of length \$n\$ and comparing to specific parameters, this instead generates all possible partial differences, then filters sequences on that

’Ø-œċŒ!€ẎÄS=¥ƇḢŻ - Main link. Takes n on the left and s on the right
’                - n-1
 Ø-              - [-1, 1]
   œċ            - Combinations with replacement
     Œ!€         - Get the permutations of each
        Ẏ        - Tighten into a list of partial differences
         Ä       - Compute the forward sums
             Ƈ   - Filter; Keep those sequences k where the following is true:
            ¥    -   Group the previous 2 links into a dyad f(k, s):
          S      -     Sum of k
           =     -     Equals s
              Ḣ  - Take the first sequence or 0 if there are none
               Ż - Prepend a 0 if a list

Answer 11

CJam, 65 58 54 bytes

Barely shorter than my Mathematica solution, but that's mostly my fault for still not using CJam properly:

0]]l~:S;({{_1+\W+}%}*{0\{+_}%);}%_{:+S=}#_@\i=\0>\[]?p

It's literally the same algorithm: get all n-1-tuples of {1, -1}. Find the first one whose accumulation is the same as s, prepend a 0. Print an empty array if none is found.

Answer 12

CJam, 40

Another approach in CJam.

ri,W%)\_:+ri-\{2*:T1$>1{T-W}?2$+\}/])!*p

Answer 13

Ruby(136)

def one_sequences(n)
  n.to_s.chars.map(&:to_i).each_cons(2).to_a.select{|x|x[0] == 0 && (x[1] == 1 || x[1]
  == -1)}.count
end

Answer 14

J, 47 chars

Checks every sequence like many other answers. Will try to make a shorter O(n) solution.

   f=.4 :'(<:@#}.])(|:#~y=+/)+/\0,|:<:2*#:i.2^<:x'

   8 f 4
0 1 2 1 0 1 0 _1

   3 f 5
[nothing]

Answer 15

APL 38

{⊃(↓a⌿⍨⍺=+/a←+\0,⍉1↓¯1*(⍵⍴2)⊤⍳2*⍵),⊂⍬}

Example:

     4 {⊃(↓a⌿⍨⍺=+/a←+\0,⍉1↓¯1*(⍵⍴2)⊤⍳2*⍵),⊂⍬}8
0 1 2 1 0 1 0 ¯1

This one as many others just brute forces through every combination to find one that matches, if not found returns nothing. Actually it tries some combinations more than once to make the code shorter.