32
\$\begingroup\$

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]
\$\endgroup\$
  • 8
    \$\begingroup\$ 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. \$\endgroup\$ – Greg Martin Oct 14 at 17:34
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Sara J Oct 14 at 17:35
  • 2
    \$\begingroup\$ @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). \$\endgroup\$ – Graham Oct 14 at 22:52
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Sara J Oct 15 at 7:19
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Ben Oct 16 at 6:11

20 Answers 20

7
\$\begingroup\$

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

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()
\$\endgroup\$
  • \$\begingroup\$ Is it any better to use reduce, and look at current-memo.length? \$\endgroup\$ – Pureferret Oct 14 at 16:16
  • \$\begingroup\$ @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. \$\endgroup\$ – Arnauld Oct 14 at 16:59
  • \$\begingroup\$ 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. \$\endgroup\$ – Pureferret Oct 14 at 17:19
7
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ What's wrong with using s? -4 bytes: Try it online! \$\endgroup\$ – Kroppeb Oct 14 at 10:40
  • \$\begingroup\$ "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. \$\endgroup\$ – Unrelated String Oct 14 at 10:43
  • \$\begingroup\$ (Your -4 bytes is in fact what I had before I noticed that it fails the third test case.) \$\endgroup\$ – Unrelated String Oct 14 at 10:44
  • 1
    \$\begingroup\$ Oof, missed that. \$\endgroup\$ – Kroppeb Oct 14 at 10:47
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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] \$\endgroup\$ – Sara J Oct 14 at 17:46
  • \$\begingroup\$ @SaraJ Ah then I must be misunderstanding the challenge. \$\endgroup\$ – Wheat Wizard Oct 14 at 17:49
  • \$\begingroup\$ @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. \$\endgroup\$ – Wheat Wizard Oct 14 at 17:52
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

Perl 5, 59 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 38 bytes

IEΦLθ∧‹§θι⁺²ι⬤✂θ⁻⊕ι§θιι¹⁻λ⊕μ✂θ⁻⊕ι§θι⊕ι

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

    θ                                   Input array
   L                                    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
 E                                      Map over matching indices
                            ✂θ⁻⊕ι§θι⊕ι  Extract sequence including length
I                                       Cast to string for implicit print
\$\endgroup\$
2
\$\begingroup\$

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

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

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

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!

\$\endgroup\$
2
\$\begingroup\$

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

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

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ m!=j+1for can be golfed to m+~j for, saving one byte. \$\endgroup\$ – Jonathan Frech Oct 14 at 8:47
  • \$\begingroup\$ all(...)and 0<... could possibly be all(...)>0<.... \$\endgroup\$ – Jonathan Frech Oct 14 at 8:47
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Sara J Oct 15 at 15:32
  • \$\begingroup\$ Thanks Sara, edited. \$\endgroup\$ – GammaFunction Oct 15 at 19:47
1
\$\begingroup\$

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

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!

\$\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.