# Make a one sequence

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

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.

• By the way, I have a proof that all numbers representable as a one sequence of length l are all the numbers between (l-1)*l/2 and -(l-1)*l/2 which have the same parity as (l-1)*l/2. Oct 4, 2014 at 10:49
• this can be used to make an efficient algorithm (O(n)) to make a desired one sequence Oct 4, 2014 at 10:51

# 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]


## 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

• I'm confused: The {}% part of your code looks nothing like mine (which is just @PeterTaylor's code, replacing dots with underscores). If I contributed anything to your code, it's the {}= operator... Oct 2, 2014 at 18:48
• I initially had _{_W=)+}%\{_W=(+}%+ which was first making two copies, add 1 to the first, subtracting 1 from other. Your example made me figure out how to do that in one { ... }% block. Regarding the { ... }=, I already had reduced it that much in my experimentation, although not posted yet. Oct 2, 2014 at 18:50
• I understand from the question that given input 3 5 the output should be [] and not "" Oct 2, 2014 at 19:06
• @PeterTaylor "an empty set/list/array/etc if not possible" - So I think that I just have to make it clear ... Oct 2, 2014 at 19:10
• Plus, []p in CJam just outputs to "". So its how the language represents empty arrays. Oct 2, 2014 at 19:11

## GolfScript (41 39 bytes)

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


Online demo

Thanks to Dennis for 41->39.

• You can shorten ,0= to ?. A straightforward port to CJam would be 5 bytes shorter: L1,al~:S;({{_W=(+_)))+}%}*{:+S=}=p Oct 2, 2014 at 18:00
• @Dennis oooh, that's handy way of getting ride of two {}% blocks. Mind if I use it ? Oct 2, 2014 at 18:28
• @Optimizer: I don't, but it's not really my work. Oct 2, 2014 at 18:34
• I was talking about the { ... }% block. In my code, I had two, was trying to reduce it to 1. As was as real algorithm goes, I think both Peter and I posted the same algorithm almost at the same time. Oct 2, 2014 at 18:41

# 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.

• -1 from your [] versions Nov 26, 2020 at 16:53
• @cairdcoinheringaahing ...oh. Thanks! Nov 26, 2020 at 17:15
• and I just realized I'd already done that by accident on both of them 🙃 Nov 26, 2020 at 17:16

## 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 {}.

• Mathematica just shines its way on maths/combination related problems, Don't it ? ;) Oct 2, 2014 at 16:29
• @Optimizer I'm sure CJam will beat it nevertheless. ;) Actually this same algorithm shouldn't be hard to do in CJam. Oct 2, 2014 at 16:31
• It will definitely beat it, but just because of short method names. The algorithm will not be as straight forward. Oct 2, 2014 at 16:33
• @Optimizer, huh? I think it's more straightforward with a simple loop and filter than this function composition. Oct 2, 2014 at 17:07

n%s=[x|x<-scanl(+)0mapmapM(\_->[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
• a simple improvement is to change a to an infix function. here's a hint to a more unintuitive improvement: importing Control.Monad just for using replicateM which is already too long. what other monadic function can you use to simulate replicateM? Oct 3, 2014 at 9:26
• by the way, you should return only one solution, so you should add head$ to your solution. Oct 3, 2014 at 9:28 • head does not return [] for [] :: [[a]] - and I hate errors. Oct 3, 2014 at 13:40 • because some time has passed, I'll tell you what I meant. You could use mapM(\x->[1,-1])[2..n] instead of sequence and replicate. Oct 4, 2014 at 10:45 • Interesting. That is even shorter :P Oct 4, 2014 at 15:20 # Husk, 14 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! • Doesn't this always output a sequence that's too long by one element? Dec 10, 2020 at 0:42 • yes, forgot about it. I fixed it. Dec 10, 2020 at 2:22 # 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[]  # 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! # 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  • 17? Nov 26, 2020 at 7:59 • wait, no, 16 Nov 26, 2020 at 8:23 • @UnrelatedString Very nice, thanks! Nov 26, 2020 at 14:42 ## CJam, 6558 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. # CJam, 40 Another approach in CJam. ri,W%)\_:+ri-\{2*:T1$>1{T-W}?2\$+\}/])!*p


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


# 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]


## 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.