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.

• proud haskeller: 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: this can be used to make an efficient algorithm (O(n)) to make a desired one sequence

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

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

Answer 3

GolfScript ((削除) 41 (削除ここまで) 39 bytes)

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

Online demo

Thanks to Dennis for 41->39.

• Dennis: You can shorten ,0= to ?. A straightforward port to CJam would be 5 bytes shorter: L1,al~:S;({{_W=(+_)))+}%}*{:+S=}=p
• Optimizer: @Dennis oooh, that's handy way of getting ride of two {}% blocks. Mind if I use it ?
• Dennis: @Optimizer: I don't, but it's not really my work.
• Optimizer: 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.

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.

• caird coinheringaahing: -1 from your [] versions
• Unrelated String: @cairdcoinheringaahing ...oh. Thanks!
• Unrelated String: and I just realized I'd already done that by accident on both of them 🙃

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

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

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

• proud haskeller: 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: by the way, you should return only one solution, so you should add head$ to your solution.
• Johannes Kuhn: head does not return [] for [] :: [[a]] - and I hate errors.
• proud haskeller: 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.
• Johannes Kuhn: Interesting. That is even shorter :P

Answer 7

Husk, ^{(削除) 14 (削除ここまで)} 16 bytes

ḟo=0ΣmΘm∫π←2fIṡ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!

• Dominic van Essen: Doesn't this always output a sequence that's too long by one element?
• Razetime: yes, forgot about it. I fixed it.

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

• Unrelated String: 17?
• Unrelated String: wait, no, 16
• caird coinheringaahing: @UnrelatedString Very nice, thanks!

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.