12
\$\begingroup\$

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: a1, a2, ..., an is a one-sequence if:

For any k (1 ≤  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.

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

11 Answers 11

7
\$\begingroup\$

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

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

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]
\$\endgroup\$
5
\$\begingroup\$

GolfScript (41 39 bytes)

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

Online demo

Thanks to Dennis for 41->39.

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

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

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – proud haskeller Oct 3 '14 at 9:26
  • \$\begingroup\$ by the way, you should return only one solution, so you should add head$ to your solution. \$\endgroup\$ – proud haskeller Oct 3 '14 at 9:28
  • \$\begingroup\$ head does not return [] for [] :: [[a]] - and I hate errors. \$\endgroup\$ – Johannes Kuhn Oct 3 '14 at 13:40
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – proud haskeller Oct 4 '14 at 10:45
  • \$\begingroup\$ Interesting. That is even shorter :P \$\endgroup\$ – Johannes Kuhn Oct 4 '14 at 15:20
2
\$\begingroup\$

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[]
\$\endgroup\$
0
\$\begingroup\$

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.

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

CJam, 40

Another approach in CJam.

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

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
\$\endgroup\$
0
\$\begingroup\$

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]
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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