# Length-terminated sequences

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

• Let's give the OP the benefit of the doubt that they're proposing a fun code-golf challenge and not arguing that the given data structure should be used in real life. – Greg Martin Oct 14 '19 at 17:34
• @Graham If you know where in a blob of arbitrary data your string begins (or, indeed, where it ends), you can absolutely retrieve it. If you don't, it doesn't matter how you represent your strings, you're almost certainly going to find segments of memory that look like strings but aren't the string you're looking for. – Sara J Oct 14 '19 at 17:35
• @SaraJ I don't think it's quite that. - my reading of your rules is that all values must be >= their index in the array. For any value <= its own index, that value will be incorrectly recognised as a terminator. You also have a problem with your [9, 9, 2, 4] example - the point of a terminator is that parsing terminates there, so it can't also return 9,9,2 unless it's going to scan the entire system memory looking for matches (or at least the next 126 bytes, which may break array bounds). – Graham Oct 14 '19 at 22:52
• @Graham The definition of a length terminated string clearly states that the terminator is exactly the length. You might also notice that in the 9,9,2,4 example, the possible strings (9,9,2,4 and 9,2 if we include the terminators) start in different locations, so if you know where the string starts you do get an unambiguous value - the 2 won't terminate 9,9,2 but will terminate 9,2. The input contains zero or more strings in unknown locations because scanning the entire memory for possible matches is exactly what the challenge is about. – Sara J Oct 15 '19 at 7:19
• @Graham You have the problem with this format exactly backwards. If you attempt to store 9 9 2 at some memory location it will result in the memory pattern 9 9 2 4, and reading the memory location later will unambiguously give you back 9 9 2. The problem is that if you try to store 9 9 2 4 9 at some location, that will result in the memory pattern 9 9 2 4 9 6, but reading it back will give you 9 9 2 (and the last 3 numbers will be leaked memory) because the 4 in the data is mistaken for a terminator. – Ben Oct 16 '19 at 6:11

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

# 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)?  • – caird coinheringaahing Nov 10 '20 at 13:55 • @cairdcoinheringaahing Nope, they are not valid when they include a valid prefix. (Otherwise 6) – Jonathan Allan Nov 10 '20 at 15:16 # 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()  • Is it any better to use reduce, and look at current-memo.length? – Pureferret Oct 14 '19 at 16:16 • @Pureferret Do you mean reduce() instead of map() or instead of every()? I fail to see a shorter approach either way, but I've probably not fully understood what you are suggesting. – Arnauld Oct 14 '19 at 16:59 • the former. I tried to get something wherein I would check the length at every stage, building up the array at the time. I was just playing, and couldn't figure out if it was better. – Pureferret Oct 14 '19 at 17:19 # 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. • Nice improvement! I've posted a bounty, which I'll keep up for the 7 days to give this visibility. – xnor Dec 8 '19 at 21:52 # 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.  • What's wrong with using s? -4 bytes: Try it online! – Kroppeb Oct 14 '19 at 10:40 • "and no prefix of the sequence is also a valid length-terminated sequence". Seems better to find the shortest prefix (if any) of every suffix than to filter the substrings for not having length-terminated prefixes. – Unrelated String Oct 14 '19 at 10:43 • (Your -4 bytes is in fact what I had before I noticed that it fails the third test case.) – Unrelated String Oct 14 '19 at 10:44 • Oof, missed that. – Kroppeb Oct 14 '19 at 10:47 # 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. • This seems to fail on the third test case - it outputs [1], [1,2], [1,2,3], [1,2,3,4] and [1,2,3,4,5] when it should only output [1] – Sara J Oct 14 '19 at 17:46 • @SaraJ Ah then I must be misunderstanding the challenge. – Wheat Wizard Oct 14 '19 at 17:49 • @SaraJ Now that I undestand the issue I have resolved it. The indended problem is much easier to express in Prolog than the one I had interpreted. – Wheat Wizard Oct 14 '19 at 17:52 ## 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!

(>>= \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!

# Perl 5, 59 bytes

/(?<!\d).*?\b(\d++)(??{$1^1+$&=~y, ,,||"(*PRUNE)".say$&})^/  Try it online! # 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  # J, 28 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) # C (clang), 1019897 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)  # 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  # 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! # 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  # 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  # 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! # 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 • m!=j+1for can be golfed to m+~j for, saving one byte. – Jonathan Frech Oct 14 '19 at 8:47 • all(...)and 0<... could possibly be all(...)>0<.... – Jonathan Frech Oct 14 '19 at 8:47 # 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.

• RE your edit, I'd say no in this case. Since each of your lists otherwise occupy exactly one line, a blank line would mean explicitly outputting the empty list, which should never be part of the output. – Sara J Oct 15 '19 at 15:32
• Thanks Sara, edited. – GammaFunction Oct 15 '19 at 19:47

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

• Miss a closing brace somewhere? – G B Dec 9 '19 at 6:59
• Also fails on [1,2,3,4,5] – G B Dec 9 '19 at 7:18

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

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

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

# 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


# 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│
└~─┘