# 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. – proud haskeller Oct 4 '14 at 10:49
• this can be used to make an efficient algorithm (O(n)) to make a desired one sequence – proud haskeller Oct 4 '14 at 10:51

## 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... – Dennis Oct 2 '14 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. – Optimizer Oct 2 '14 at 18:50
• I understand from the question that given input 3 5 the output should be [] and not "" – Peter Taylor Oct 2 '14 at 19:06
• @PeterTaylor "an empty set/list/array/etc if not possible" - So I think that I just have to make it clear ... – Optimizer Oct 2 '14 at 19:10
• Plus, []p in CJam just outputs to "". So its how the language represents empty arrays. – Optimizer Oct 2 '14 at 19:11

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


## 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 – Dennis Oct 2 '14 at 18:00
• @Dennis oooh, that's handy way of getting ride of two {}% blocks. Mind if I use it ? – Optimizer Oct 2 '14 at 18:28
• @Optimizer: I don't, but it's not really my work. – Dennis Oct 2 '14 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. – Optimizer Oct 2 '14 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.


## 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 ? ;) – Optimizer Oct 2 '14 at 16:29
• @Optimizer I'm sure CJam will beat it nevertheless. ;) Actually this same algorithm shouldn't be hard to do in CJam. – Martin Ender Oct 2 '14 at 16:31
• It will definitely beat it, but just because of short method names. The algorithm will not be as straight forward. – Optimizer Oct 2 '14 at 16:33
• @Optimizer, huh? I think it's more straightforward with a simple loop and filter than this function composition. – Peter Taylor Oct 2 '14 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? – proud haskeller Oct 3 '14 at 9:26
• by the way, you should return only one solution, so you should add head$ to your solution. – proud haskeller Oct 3 '14 at 9:28 • head does not return [] for [] :: [[a]] - and I hate errors. – Johannes Kuhn Oct 3 '14 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. – proud haskeller Oct 4 '14 at 10:45 • Interesting. That is even shorter :P – Johannes Kuhn Oct 4 '14 at 15:20 # 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+i return[]  # 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  # Python 3, 80 bytes f=lambda l,s,a=:l>1and max(f(l-1,s,a+[a[-1]+x])for x in(1,-1))or(sum(a)==s)*a  Try it online! # Husk, 14 15 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! ## 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 && (x == 1 || x
== -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.