Length-terminated sequences

Question

We all know the age-old debate - should strings be length-prefixed or should they be null-terminated? Well, you've run into a blob of binary data and apparently whoever made it decided that the best solution would be a compromise and length-terminated their strings.

For the purposes of this challenge, a length-terminated sequence is a series of one or multiple integers such that the last item in the sequence is equal to the number of items in the sequence, and no prefix of the sequence is also a valid length-terminated sequence. For example, [1], [15, 2], and [82, 19, 42, 111, 11, 6] are all valid length-terminated sequences. [15] is not a valid length-terminated sequence (it hasn't been terminated), and neither is [15, 2, 3] (it should have ended at the 2).

Your task is to write a program or function that takes a list of integers, and outputs all the valid length-terminated sequences within that list. For example, for the input list [7, 6, 5, 4, 3, 2, 1], valid length-terminated sequences would be [1], [3, 2], [5, 4, 3] and [7, 6, 5, 4].

• You must output all valid length-terminated sequences found in the input, in any order. The order may vary between runs of your program. You must output no length-terminated sequences not found within the input, and no sequences found within the input that aren't valid length-terminated sequences.
• If some length-terminated sequence occurs multiple times within the input, it should also be output multiple times. The sequence [9, 8, 3] occurs twice in the input [9, 8, 3, 9, 8, 3] (once starting with the first number, and again starting at the fourth number) and should thus be output twice.
• A number may be part of more than one length-terminated sequence. For example, the input [9, 9, 2, 4] contains both the length-terminated sequences [9, 9, 2, 4] and [9, 2] and they should both be output.
• You may assume all numbers are between 0 and 127 (both inclusive).
• You may assume the input contains no more than 126 numbers.
• You may not make any further assumptions about the input, including the assumption that the input contains at least one valid length-terminated sequence.
• You may take input or produce output by any of the default methods. Input and output formats are flexible (within reason) and the input format need not be the same as the output format. However, the your input and output formats must not depend on the input, and must not vary between runs of your program.
• This is code-golf - make your code as small as possible.

Examples

[input] -> [output], [output], ...
[7, 6, 5, 4, 3, 2, 1] -> [7, 6, 5, 4], [5, 4, 3], [3, 2], [1]
[90, 80, 70] -> (no output)
[1, 2, 3, 4, 5] -> [1]
[100, 0, 2, 2, 2, 0, 0, 2, 4] -> [0, 2], [2, 2], [2, 2], [0, 0, 2, 4], [0, 2]
[] -> (no output)
[54, 68, 3, 54, 68, 3] -> [54, 68, 3], [54, 68, 3]
[4, 64, 115, 26, 20, 85, 118, 9, 109, 84, 64, 48, 75, 123, 99, 32, 35, 98, 14, 56, 30, 13, 33, 55, 119, 54, 19, 23, 112, 58, 79, 79, 45, 118, 45, 51, 91, 116, 7, 63, 98, 52, 37, 113, 64, 81, 99, 30, 83, 70] -> [85, 118, 9, 109, 84, 64, 48, 75, 123, 99, 32, 35, 98, 14], [118, 9, 109, 84, 64, 48, 75, 123, 99, 32, 35, 98, 14, 56, 30, 13, 33, 55, 119, 54, 19, 23, 112, 58, 79, 79, 45, 118, 45, 51, 91, 116, 7, 63, 98, 52, 37], [109, 84, 64, 48, 75, 123, 99, 32, 35, 98, 14, 56, 30, 13, 33, 55, 119, 54, 19], [84, 64, 48, 75, 123, 99, 32, 35, 98, 14, 56, 30, 13], [14, 56, 30, 13, 33, 55, 119, 54, 19, 23, 112, 58, 79, 79, 45, 118, 45, 51, 91, 116, 7, 63, 98, 52, 37, 113, 64, 81, 99, 30], [45, 118, 45, 51, 91, 116, 7]

Answer 1

Python 2, 67 bytes

f=lambda l:l and[l[:x]for i,x in enumerate(l)if-~i==x][:1]+f(l[1:])

Try it online!

Answer 2

Jelly, 9 bytes

Ẇ=J$Ḅ⁼ɗƇ1

A monadic Link accepting a list of integers which yields a list of lists of integers.

Try it online!

Or ẆĖE€Ḅ⁼ʋƇ1 - Try it.

How?

Ẇ=J$Ḅ⁼ɗƇ1 - Link: list of integers
Ẇ         - all sublists
        1 - set right argument to 1
       Ƈ  - filter keep those (sublists) for which:
      ɗ   -   last three links as a dyad - i.e. f(sublist, 1):
   $      -     last two links as a monad i.e. g(sublist)
  J       -       range of length = [1,2,3,...,length]
 =        -       (sublist) equals (that)? (vectorises)
    Ḅ     -     from binary
     ⁼    -     (that) equals (1)?

Answer 3

JavaScript (V8), 65 bytes

Prints the results.

a=>a.map((_,i)=>a.every((v,j)=>j<i|v-++j+i||print(a.slice(i,j))))

Try it online!

Commented

a => a.map((_, i) => // for each value at position i in a[]:
  a.every((v, j) =>  //   for each value v at position j in a[]:
    j < i |          //     yield true and go on with the next iteration if j < i
    v - ++j + i      //     or v is not equal to j - i + 1 (increment j)
    || print(        //     otherwise, print ...
      a.slice(i, j)  //       ... the sublist of a[] from i to j - 1
    )                //     and break (print() returns undefined)
  )                  //   end of every()
)                    // end of map()

Answer 4

Python, 62 bytes

f=lambda l:l and[l[:x]for x in l if[x]==l[x-1:x]][:1]+f(l[1:])

Try it online!

This is a subtle improvement on @xnor's solution.

The solution we wish we could use is

f=lambda l:l and[l[:x]for x in l if x==l[x-1]][:1]+f(l[1:])

However, this will crash on an out-of-bounds index. xnor avoided this problem by using the index at which the value x appeared rather than actually indexing into l, but this required using the expensive enumerate function.

Instead, I used [x-1:x] to slice out the length-1 slice including the index we're interested in. Slicing in Python is much more permissive with respect to out of bounds errors. Now, we only need to check that the part of the list sliced out is [x].

Works in Python 2 or 3.

Answer 5

Brachylog, 12 bytes

a₁ᶠ{a₀.l~t}ˢ

Try it online!

a₁ᶠ{      }ˢ    For every suffix of the input, if possible,
    a₀.         find the shortest prefix
       l        the length of which is
      . ~t      its last element.

An alternate generator solution using s, taking inspiration from Jonathan Allan's Jelly solution:

Brachylog, 13 12 bytes

s.i₁ᶠ=ˢ~gh~l

Try it online!

 .              The output is
s               any substring of the input
  i₁ᶠ           such that a list of all elements paired with their 1-indices
     =ˢ         filtered by equality
       ~g       has only one element, of which
         h      the first element
          ~l    is the length of the output.

Answer 6

Prolog (SWI), 67 bytes

X-Y:-X+Y+1.
[_|X]-Y:-X-Y.
[H|T]+[H|X]+N:-X=[],N=H,!;M is N+1,T+X+M.

Try it online!

Uses the -/2 predicate.

There are two parts to the code.

[H|T]+[H|X]+N:-X=[],N=H,!;M is N+1,T+X+M.

Essentially computes the shortest prefix that end in its length. However it only does this when called with X+Y+1.

Then we have the main predicate -/2

X-Y:-X+Y+1.
[_|X]-Y:-X-Y.

This matches all the prefixes of X than end in their length:

X-Y:-X+Y+1.

and anything that matches the tail of X.

[_|X]-Y:-X-Y.

That turns our predicate over prefixes to a predicate over sublists.

Answer 7

Haskell, 69 64 bytes

((1#)=<<).scanr(:)[]
l#(a:b)|l==a=[[a]]|m<-l+1=(a:)<$>m#b
_#_=[]

Edit: -5 bytes thanks to @Sriotchilism O'Zaic

Try it online!

Answer 8

Haskell, 59 bytes

(>>= \l->take 1[take x l|(i,x)<-zip[1..]l,i==x]).scanr(:)[]

Try it online!

60 bytes

f l@(h:t)=take 1[take x l|(i,x)<-zip[1..]l,i==x]++f t
f _=[]

Try it online!

Answer 9

Perl 5, 59 bytes

/(?<!\d).*?\b(\d++)(??{$1^1+$&=~y, ,,||"(*PRUNE)".say$&})^/

Try it online!

Answer 10

Charcoal, 38 bytes

ＩＥΦＬθ∧‹§θι⁺²ι⬤✂θ⁻⊕ι§θιι¹⁻λ⊕μ✂θ⁻⊕ι§θι⊕ι

Try it online! Link is to verbose version of code. Explanation:

    θ                                   Input array
   Ｌ                                    Length
  Φ                                     Filter over implicit range
       §θι                              Value at current index
      ‹                                 Is less than
          ⁺²ι                           Current index plus 2
     ∧                                  And
             ⬤                          For all elements of
              ✂θ                        Slice of input array
                ⁻⊕ι§θι                  From potential sequence start
                      ι¹                To current index
                         λ              Value
                        ⁻               Does not equal
                          ⊕μ            1-indexed index
 Ｅ                                      Map over matching indices
                            ✂θ⁻⊕ι§θι⊕ι  Extract sequence including length
Ｉ                                       Cast to string for implicit print

Answer 11

J, ²⁸ 22 bytes

a:-.~((#={:)\{.@#<\)\.

Try it online!

Take the empty boxes a: away from -.~ the following result:

For each postfix of the input \. do the following:

Filter # the boxed prefixes of the current input <\ using the boolean mask which asks, also for each prefix of the current input, "Is the length equal to the last item?" (#={:)\.

From those boxed prefixes that do pass the filter, take the first one {.@. If no prefixes pass the filter, this will return the empty box a: (ie, the zero value of a list of boxes).

Note for J-ers: The function always returns a list of boxes, each of which contains a list of numbers. This (desirable) consistency is what creates some of the seeming inconsistencies required to correctly specify the expected values of the test cases:

• (,:1) -- a list containing 1
• ,:<,:1 -- a boxed list containing the list containing 1 (remember: a single box is an atom)

Answer 12

C (clang), 101 98 97 95 bytes

j;f(*l,z){for(l+=z;z;)if((j=-*--l)&&j>~z--&&j-~l[-1]|!z)for(puts("");printf("%d ",l[++j])*j;);}

Try it online!

-1 thanks to @ceilingcat

j; 
f(*l,z){ // function taking a pointer and size  
for(l+=z;z;) // move pointer to the end for backward iteration 
if( // cascaded conditions : 
  (j=-*--l) // skip if value is 0 while assigning to j its negation 
  &&j>~z-- // skip if j>z ( before array begins) 
  &&j-~l[-1] // skip if previous value is 1 less than value  
  |!z // if z =0 previous value doesn't care 
) 
for(puts("") // newline to separate lists obtained 
   ;printf("%d ",l[++j]) // print each value from j before l position 
    *j;);} // to l (j=0) 

Answer 13

Perl 6, 40 bytes

{~<<m:ov/(<<\d+>>)+?%\s<!{$0-$0.tail}>/}

Try it online!

Regex-based approach working with strings of space-separated numbers.

35 bytes when working directly with ASCII strings:

{~<<m:ov/(.)+?<!{$0-$0.tail.ord}>/}

Try it online!

Explanation

{                                      }  # Anonymous block
    m:ov/                             /   # Find all overlapping matches
          <<       # Left word boundary
            \d+    # One or more digits
               >>  # Right word boundary
         (       )+?     # One or more numbers, lazy
                    %\s  # Separated by space
                       <!{          }>  # Negative boolean condition check
                          $0-$0.tail    # Count of numbers minus last number
 ~<<  # Stringify matches

Answer 14

Ruby, 72 70 bytes

-2 bytes by somehow typing a.length instead of a.size when constructing the range, but still using the correct function later down the line when checking the sequences.

->a{(r=0..a.size).map{|i|r.map{|j|a[i,j]}.find{|s|s[-1]==s.size}}-[p]}

Try it online!

Answer 15

Japt -mR, 12 bytes

WsV
¯ÒUbÈɶY

Try it

-mR         //Map each element in the input to the following program, and join with newlines
            //U is the element being mapped over
            //V is the index
            //And W is the original array
WsV         //Set U to the original array, removing the first V(index) elements
¯           //Take the first n elements, where n is the following:
   Ub       //  The first index in U which satisfies the following condition
     郦Y   //    Where the element at that index minus one equals the index
  Ò         //   Add 1 to that result

Answer 16

Curry, 33 bytes

Tested in both KiCS2 and PAKCS.

f(_++u++x:_)|x==1+length u=u++[x]

Curry's powerful patterns let it beat the Haskell answer once again!

To test it you can use Smap. Just select KiCS2 2.2.0 or PAKCS 2.2.0 with the /all-values option and paste the following complete code:

f(_++u++x:_)|x==1+length u=u++[x]
main=f [7, 6, 5, 4, 3, 2, 1]

Answer 17

PHP, 90 bytes

for(;++$i<$c=count($argv);)for($j=$i;$c>$j;$j-$i-$n?:$c=print_r($$i))$$i[]=$n=$argv[$j++];

Try it online!

Input sequence is sent using command arguments (each number is one argument) and output is string representation of arrays using PHP's print_r.

for(;                  // outer loop on $argv input items
  ++$i<                // $i is current index, starts from second item as PHP fills first item with script's name
  $c=count($argv);     // $c is total number of input items
)
  for(                 // inner loop on input items
    $j=$i;             // $j is inner loop's index, always starts from outer loop's index
    $c>$j;             // continue while inner index is less than $c
    $j-$i-$n?:         // THIS IS RUN LAST: if current number ($n) is equal to $j-$i ($j is incremented by one already, so $j-$i gives a position starting from 1 in the $$i)
       $c=print_r($$i) // THIS IS RUN LAST: print the $$i array and set $c to 1 to break the inner loop
  )
    $$i[]=             // THIS IS RUN FIRST: push into an array named by value of $i (if $i=2, variable name is 2)
    $n=$argv[$j++];    // THIS IS RUN FIRST: current number in index of inner loop and increment the index ($j) by one, $n also keeps current number

Answer 18

Red, 149 121 bytes

func[b][j: i: 0 until[if(i: i + 1)> n: length? b[j: j + 1 i: 1]if
b/(j + i) = i[print[copy/part at b j + 1 i]i: n]j = n]]

Try it online!

Answer 19

Python 3, 98 bytes

lambda s,e=enumerate:[s[i-n:i]for i,n in e([9]+s)if all(m+~j for j,m in e(s[i-n:i-1]))>0<n<=i]

Try it online!

Takes the input as a list and maps it to a list of lists where each item is a sublist of length n ending with item n for each item. Then it is filtered so that no list contains other valid length terminators.

-4 bytes thanks to Jonathan Frech

Answer 20

Zsh, 35 37 bytes

+2 bytes to suppress zero-length lists

for x;((s=++i-x+1,x*s>0))&&<<<$@[s,i]

Try it online!

For each element in the input, calculate the index of where the sequence would have to start. If the start index and the element are both >0, then print the elements from there to the current index, inclusive.

Answer 21

Ruby 2.7-preview1, 50 bytes

Uses Ruby 2.7's new Enumerable#filter_map method. (Sorry for no TiO link; TiO is still on Ruby 2.5.5.)

->a{i=0
a.filter_map{|c|i+=1
c>0&&c<=i&&a[i-c,c]}

Answer 22

Icon, 121 bytes

procedure f(b)
r:=[];i:=j:=0
while j<*b do{if*b<(i+:=1)then j+:=1&i:=0 else b[j+i]=i&put(r,b[j+1+:i])&i:=*b}
return r
end

Try it online!

Answer 23

Ruby, 64 bytes

->a,*s{(r=0;a.find{|x|(x==r+=1)&&s<<a[0,x]};w,*a=a)while a[0];s}

Try it online!

Answer 24

Prolog (SWI), 135 bytes

A*B:-reverse(A,B).
[]-_. [A|Q]-[A|R]:-Q-R.
+[Q|R]:-length([Q|R],Q),\+((R*Z,X-Z,S*X,+S)).
Q/R:-N-Q,N*Z,X-Z,R*X,+X.
X//Y:-bagof(R,X/R,Y).

Try it online!

A*B is reverse(A,B)

A-B is true if A is a prefix of B

+A is true if A is a valid encoding, i.e. length-terminated list

A/B is true if, given list A, B is contained within A and B is a valid encoding

A//B is true if, given list A, Y is the list of all valid encodings in A (if there are no valid encodings in A, A//B fails)

Calling predicate ///2 with the left argument a list and the right argument a variable unifies the variable with the required result. For example, [7,6,5,4,3,2,1]S. will unify S with the [[7, 6, 5, 4], [5, 4, 3], [3, 2], [1]]. The TIO link contains a helper predicate that runs all inputs with against this predicate.

Verbose

prefix([],_).
prefix(_,[]):-1<0.
prefix([A|Q], [A|R]):-
	prefix(Q,R).
suffix(A, B):-
	reverse(B, Q),
	prefix(P, Q),
	reverse(A, P).
encoded([H|T]):-
	length([H|T], H),
	\+((suffix(P,T), encoded(P))).
f(Q, R):-
	prefix(N, Q),
	suffix(R, N),
	reverse(R, T),
	encoded(T).
g(List, All):-
	bagof(Encoding, f(List, Encoding), All).

Try it online!

The tricks used from this verbose solution is to first create another predicate for reverse because it is repeated many times. Then operators are used in place of predicate names. The predicate for suffix turns out to only be used once, so it can be removed, replacing its call in f with its conditions. Doing this removes the need to use reverse(R, T) as the suffix predicate already has the same condition.

Answer 25

T-SQL, 175 bytes

with s(r,i)as(select row_number()over(order by(rand())),*from string_split(<Comma delimited integer string>,','))select string_agg(l.i,',')from s,s l where l.r>s.r-s.i and l.r<=s.r and s.r-s.i>=0group by s.i

Try it online!

---

Verbose version

with s(r,i) as
(
    select row_number() over (order by (rand())) -- Add a row number for sorting
          ,*
    from string_split('7,6,5,4,3,2,1',',')       -- to the split out integer list
)
select string_agg(l.i,',')                       -- then aggregate back together
from s,s l                                       -- joining to itself
where l.r > s.r - s.i                            --   where the previous numbers sit in rows between [current int value] rows before
    and l.r <= s.r                               --     and the current row
    and s.r - s.i >= 0                           --     and there are enough list items for the current integer value
group by s.i                                     -- grouped to each output string

Answer 26

05AB1E, 12 bytes

ŒʒDη.Δ¤sgQ}Q

Try it online or verify all test cases.

Explanation:

Π          # Get all sublists of the (implicit) input-list
 ʒ          # Filter it by:
  D         #  Duplicate the current sublist
   η        #  Pop the copy and push its prefixes
    .Δ      #  Find the first prefix that's truthy for:
            #  (or -1 if none are)
      ¤     #   Push the last value (without popping the list itself)
       s    #   Swap so the list is at the top
        g   #   Pop and push its length
         Q  #   Check if the two values are the same
     }Q     #  After the find_first: Check if both are the same
            # (after which the filtered list is output implicitly)

The ¤sgQ could alternatively be Dgſ or Ðθ∍Q for the same byte-count.

      D     #   Duplicate the list
       g    #   Pop the copy and push its length
        Å¿  #   Check if the list ends with this length as trailing value

      Ð     #   Triplicate the list
       θ    #   Pop one copy and push its last value
        ∍   #   Extend/shorten another copy to this length
         Q  #   Check if the two lists are still the same

Answer 27

APL(NARS), chars 148, bytes 296

r←f w;i;j;v;q
k←≢w⋄r←⍬⋄i←0⋄w←(⍳k),¨w
→4×⍳k<i+←1⋄→2×⍳(j>q←≢v←i↑w)∨0=j←2⊃i⊃w⋄v←v↓⍨q-j⋄→3×⍳r≡⍬⋄→2×⍳∨/{(⍵[1]≡v[1])∧⍵⊆v}¨r
r←r,⊂v⋄→2
→0×⍳r≡⍬⋄r←{⍵[2]}¨¨r

because of the problem one has to know index of the element, the input set is elaborate as one set with indices (w←(⍳k),¨w) that in the end were removed (in r←{⍵[2]}¨¨r) test:

  ⎕fmt f 90 80 70
┌0─┐
│ 0│
└~─┘
  ⎕fmt f 100 0  2  2  2 0 0 2 4
┌5─────────────────────────────────────┐
│┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌4───────┐│
││ 0 2│ │ 2 2│ │ 2 2│ │ 0 2│ │ 0 0 2 4││
│└~───┘ └~───┘ └~───┘ └~───┘ └~───────┘2
└∊─────────────────────────────────────┘
  ⎕fmt f 7 6 5 4 3 2 1
┌4──────────────────────────────┐
│┌4───────┐ ┌3─────┐ ┌2───┐ ┌1─┐│
││ 7 6 5 4│ │ 5 4 3│ │ 3 2│ │ 1││
│└~───────┘ └~─────┘ └~───┘ └~─┘2
└∊──────────────────────────────┘
  ⎕fmt f 1 2 3 4 5
┌1───┐
│┌1─┐│
││ 1││
│└~─┘2
└∊───┘
  ⎕fmt f ⍬
┌0─┐
│ 0│
└~─┘