34
\$\begingroup\$

Given some finite list, return a list of all its prefixes, including an empty list, in ascending order of their length.

(Basically implementing the Haskell function inits.)

Details

  • The input list contains numbers (or another type if more convenient).
  • The output must be a list of lists.
  • The submission can, but does not have to be a function, any default I/O can be used.
  • There is a CW answer for all trivial solutions.

Example

[] -> [[]]
[42] -> [[],[42]]
[1,2,3,4] -> [[], [1], [1,2], [1,2,3], [1,2,3,4]]
[4,3,2,1] -> [[], [4], [4,3], [4,3,2], [4,3,2,1]]
\$\endgroup\$
  • \$\begingroup\$ If a language does not define any types except for characters, can I take input as a string and separate the input by newlines, in the case of a full program? \$\endgroup\$ – NieDzejkob Dec 8 '18 at 20:37
  • \$\begingroup\$ @NieDzejkob I'm not sure what consensus there is for this case, but the Brainfuck answer seems to do something like that. \$\endgroup\$ – flawr Dec 8 '18 at 21:18
  • \$\begingroup\$ Can we expect the list to be null-terminated? \$\endgroup\$ – user77406 Dec 9 '18 at 10:02
  • \$\begingroup\$ It's especially common in C/C++, main use being strings. \$\endgroup\$ – user77406 Dec 13 '18 at 14:46
  • \$\begingroup\$ @Rogem If it is that common I think allowing it is reasonable. \$\endgroup\$ – flawr Dec 13 '18 at 14:49

64 Answers 64

15
\$\begingroup\$

Haskell, 20 bytes

Edit: Yet a byte shorter with a completely different scan.

An anonymous function slightly beating the trivial import.

scanr(\_->init)=<<id

Try it online!

  • Uses =<< for the abbreviation (scanr(\_->init)=<<id) l = scanr(\_->init) l l.
  • Scans a list l from right to left, collecting intermediate results with the function \_->init.
  • That function ignores the elements scanned through (they're only used to get the right total length for the collected results), so really iterates applying init to the initial value of the scan, which is also l.
\$\endgroup\$
13
\$\begingroup\$

brainfuck, 21 12 bytes

-9 bytes thanks to Arnauld suggesting the separator ÿ instead of newlines

-[[<]>[.>],]

Try it online!

Takes bytes through STDIN with no null bytes and prints a series of prefixes separated by the ÿ character with a leading ÿ character. For example, for the input Prefixes, the output is ÿÿPÿPrÿPreÿPrefÿPrefiÿPrefixÿPrefixeÿPrefixes.

For readability, here's a version with newlines instead.

Explanation:

-              Create a ÿ character in cell 0
 [        ,]   While input, starting with the ÿ
  [<]>           Go to the start of the string
      [.>]       Print the string
          ,      Append the input to the end of the string
\$\endgroup\$
  • 1
    \$\begingroup\$ This only works on BF implementations with 8-bit, unsigned, wrapping cells. \$\endgroup\$ – Dev Dec 10 '18 at 3:11
11
\$\begingroup\$

JavaScript (ES6), 33 bytes

a=>[b=[],...a.map(n=>b=[...b,n])]

Try it online!

How?

+--- a = input array
|
|       +--- initialize b to an empty array and include it as the first entry
|       |    of the output (whatever the input is)
|       |
|       |          +--- for each value n in a[]:
|       |          |
|       |          |        +--- append n to b[] and include this new array in
|       |          |        |    the final output
|       |          |        |
a => [b = [], ...a.map(n => b = [...b, n])]
               |                  |
               +---------+--------+
                         |
      spread syntax: expands all elements of
      the child array within the parent array
\$\endgroup\$
  • \$\begingroup\$ wow, that's a whole new level of code explanation, awesome job :O \$\endgroup\$ – Brian H. Dec 10 '18 at 12:54
  • \$\begingroup\$ @BrianH. Thank you! Simple tasks are good opportunities to write detailed explanations that can't be brought up in denser code. \$\endgroup\$ – Arnauld Dec 10 '18 at 13:05
  • \$\begingroup\$ Did you make it by hand? or did you get help from any weird software i've never heard about? \$\endgroup\$ – Brian H. Dec 10 '18 at 13:08
  • 2
    \$\begingroup\$ Just Notepad++ with some column mode editing. \$\endgroup\$ – Arnauld Dec 10 '18 at 13:30
8
\$\begingroup\$

CW for all trivial entries

Clean, 19 bytes

Haskell version works in Clean too.

import StdLib
inits

Try it online!

Haskell, 22 bytes

import Data.List
inits

Try it online!

Prolog (SWI), 6 bytes

prefix

Try it online!

\$\endgroup\$
  • \$\begingroup\$ So torn - to upvote or not. On the one hand, I appreciate all the built-in solutions in one place. On the other, I really dislike builtins because they're so basic... \$\endgroup\$ – user77406 Jan 2 at 20:39
6
\$\begingroup\$

Jelly, 3 bytes

ṭṖƤ

Try it online!

How it works

ṭṖƤ  Main link. Argument: A

  Ƥ  Map the link to the left over all non-empty(!) prefixes of A.
 Ṗ       Pop; remove the last element.
ṭ    Tack; append A to the resulting list.
\$\endgroup\$
6
\$\begingroup\$

Japt, 4 bytes

²£¯Y

Try it online!

Explanation:

²       :Add an arbitrary extra item to the end of the array
 £      :For each item in the new array:
  ¯Y    : Get an array of the items that are before it
\$\endgroup\$
6
\$\begingroup\$

Perl 6, 13 bytes

{(),|[\,] @_}

Try it online!

To explain:

In Perl 6 you can wrap an operator in square brackets as an alternate way to write a list reduction. [+] @array returns the sum of the elements in @array, [*] @array returns the product, etc. You can also precede the operator with a backslash to make a "triangular" reduction, which some languages call "scan." So [\+] @array returns a list consisting of the first element of @array, then the sum of the first two elements, then the sum of the first three elements, etc.

Here [\,] @_ is a triangular reduction over the input array @_ using the list construction operator ,. So it evaluates to a lists of lists: the first element of @_, the first two elements of @_, etc. That's almost what's needed, but the problem calls for a single empty list first. So the first element of the return list is a literal empty list (),, then the reduction over the input list is flattened into the rest of the return list with |.

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

Python 2, 32 bytes

f=lambda l:(l and f(l[:-1]))+[l]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Also works in Python 3 \$\endgroup\$ – ASCII-only Dec 8 '18 at 4:14
5
\$\begingroup\$

R, 40 39 bytes

function(L)lapply(0:length(L),head,x=L)

Try it online!

-1 byte thanks to digEmAll

The output of R's list type is a bit weird; it uses sequential indexing, so for instance, the output for

list(1,2) is

[[1]]                     # first list element
list()

[[2]]                     # second list element
[[2]][[1]]                # first element of second list element
[1] 1


[[3]]                     # third list element
[[3]][[1]]                # first element of third list element
[1] 1

[[3]][[2]]                # etc.
[1] 2

Taking input as a vector instead gives a neater output format, although then the inputs are not technically lists.

\$\endgroup\$
  • 1
    \$\begingroup\$ 39 using lapply \$\endgroup\$ – digEmAll Dec 8 '18 at 12:46
  • \$\begingroup\$ @digEmAll thanks! \$\endgroup\$ – Giuseppe Dec 10 '18 at 14:41
4
\$\begingroup\$

JavaScript, 36 bytes

a=>[...a,0].map((x,y)=>a.slice(0,y))

Try it online!

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

Mathematica, 22 21 bytes

-1 byte thanks to Misha Lavrov!

{}~FoldList@Append~#&

Pure function. Takes a list as input and returns a list of lists as output. I believe this is the shortest possible solution.

\$\endgroup\$
  • \$\begingroup\$ We can write the same solution more compactly as {}~FoldList@Append~#&. \$\endgroup\$ – Misha Lavrov Dec 7 '18 at 21:59
  • \$\begingroup\$ @MishaLavrov Thanks! I didn't think to use the curried 1+2-argument form like that. \$\endgroup\$ – LegionMammal978 Dec 7 '18 at 22:46
4
\$\begingroup\$

Husk, 2 bytes

Θḣ

Gets all the eads and then prepends Θ (in this case []):

Try it online!

(needs type annotation for empty list: Try it online!)

\$\endgroup\$
3
\$\begingroup\$

J, 5 bytes

a:,<\

Try it online!

\$\endgroup\$
3
\$\begingroup\$

PowerShell, 65 bytes

param($a)'';$x=,0*($y=$a.count);0..--$y|%{$x[$_]=@($a[0..$_])};$x

Try it online!

PowerShell helpfully unrolls lists-of-lists when the default Write-Output happens at program completion, so you get one item per line. Tack on a -join',' to see the list-of-lists better, by converting the inner lists into strings.

(Ab)uses the fact that attempting to output an empty array (e.g., @()) results in no output, so an empty array input just has '' as the output, since the $a[0..$_] will result in nothing. It will also throw out some spectacular error messages.

\$\endgroup\$
  • \$\begingroup\$ Wrapping it in parens instead of assigning it saves 20 bytes. Unless you don't think that counts as returning a list of lists. I've always been fuzzy on that distinction. \$\endgroup\$ – Veskah Dec 8 '18 at 2:59
  • \$\begingroup\$ @veskah Yeah, that's almost what I had before my edit to this version. The problem with your solution or my earlier solution -- it doesn't return a list-of-lists. TIO1 vs TIO2 \$\endgroup\$ – AdmBorkBork Dec 10 '18 at 13:44
3
\$\begingroup\$

K (ngn/k), 8 bytes

,\(,!0),

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ This is some kind of voodoo. ,\(,()), in K4. Joining enlisted null along enlisted input? howsitwork? \$\endgroup\$ – streetster Dec 7 '18 at 20:46
  • 1
    \$\begingroup\$ @streetster () is an empty list. (,()),x prepends it to x. finally ,\ does a concat-scan. the x is omitted to form a composition. note that the trailing , is dyadic, so it's "concat", not "enlist". \$\endgroup\$ – ngn Dec 7 '18 at 21:07
  • 1
    \$\begingroup\$ @streetster in k4 it can be a byte shorter: 1_',\0, but my parser isn't smart enough to handle this... \$\endgroup\$ – ngn Dec 7 '18 at 21:13
3
\$\begingroup\$

Common Lisp, 39 bytes

(defun f(l)`(,@(if l(f(butlast l))),l))

Try it online!

Explanation

(defun f(l)                           )  ; Define a function f
           `(                        )   ; With the list (essentially capable of interpolation), containing:
             ,@                          ;     The value of, flattened to one level
               (if l              )      ;         If l is not the empty list (which is the representation of nil, i.e. the only falsy value)
                    (f(butlast l))       ;         Recurse with all of l but the tail
                                   ,l    ;     The value of l
\$\endgroup\$
3
\$\begingroup\$

F#, 53 bytes

I've actually got two pretty similar answers for this, both the same length. They both take a generic sequence s as a parameter.

First solution:

let i s=Seq.init(Seq.length s+1)(fun n->Seq.take n s)

Try it online!

Seq.take takes the first n elements of the sequence. Seq.init creates a new sequence with a count (in this case) of the length of sequence s plus 1, and for each element in the sequence takes the first n elements in s.

Second solution:

let i s=Seq.map(fun n->Seq.take n s){0..Seq.length s}

Similar to before, except it creates a sequence from 0 to the length of s. Then takes that number of elements from s.

Try this online too!

\$\endgroup\$
  • \$\begingroup\$ fun s->Seq.map(fun n->Seq.take n s){0..Seq.length s} saves 1 byte \$\endgroup\$ – Embodiment of Ignorance Dec 9 '18 at 6:41
3
\$\begingroup\$

MATL, 15 12 bytes

3 bytes saved thanks to @Giuseppe

vin:"G@:)]Xh

Try it at MATL Online.

Due to the way that MATL displays the output, you can't explicitly see the empty array in the cell array. Here is a version that shows the output a little more explicitly.

Explanation

v       # Vertically concatenate the (empty) stack to create the array []
i       # Explicitly grab the input
n       # Compute the number of elements in the input (N)
:       # Create an array from [1, ..., N]
"       # Loop through this array
  G     # For each of these numbers, M
  @:    # Create an array from [1, ..., M]
  )     # Use this to index into the initial array
]       # End of the for loop
Xh      # Concatenate the entire stack into a cell array
\$\endgroup\$
  • \$\begingroup\$ use v instead of []. And doesn't : use 1 as the default first argument? So this could be vin:"G@:)]Xh for 12 bytes. \$\endgroup\$ – Giuseppe Dec 10 '18 at 18:34
  • \$\begingroup\$ @Giuseppe Thanks! My MATL is a little rusty it seems :( \$\endgroup\$ – Suever Dec 10 '18 at 22:04
3
\$\begingroup\$

SWI PROLOG 22 bytes

i(X,Y):-append(X,_,Y).

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

Charcoal, 6 bytes

Eθ…θκθ

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

 θ      Input array
E       Map over elements
   θ    Input array
  …     Moulded to length
    κ   Current loop index
        Implicitly print each array double-spaced
     θ  Input array
        Implicitly print

It's possible at a cost of 1 byte to ask Charcoal to print an n+1-element array which includes the input as its last element, but the output is the same, although the cursor position would be different if you then went on to print something else.

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

05AB1E, 3 bytes

η¯š

Explanation:

η    Prefixes
  š  Prepend
 ¯   Global array (empty by default)

Try it online!

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

Groovy, 37 bytes

{x->(0..x.size()).collect{x[0..<it]}}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ {it.inits().reverse()} will work once we get groovy 2.5 on TIO \$\endgroup\$ – ASCII-only Jan 2 at 2:08
2
\$\begingroup\$

Japt, 5 bytes

Êò@¯Y

Try it online!

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

brainfuck, 43 bytes

Take a list of non-null characters as input and returns all prefixes separated by newline. Requires double-infinite or wrapping tape.

,>-[+>,]<[-<]<<++++++++++[[<]>[.>]>[-<+>]<]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Another answer outgolfed me by more than a half, because I didn't think about printing output while reading. Of course that method won't work with printing increasing suffixes. \$\endgroup\$ – user202729 Dec 8 '18 at 9:58
  • \$\begingroup\$ 40 bytes with some rearranging \$\endgroup\$ – Jo King Dec 8 '18 at 10:19
2
\$\begingroup\$

C# (Visual C# Interactive Compiler), 39 bytes

x=>x.Select((_,i)=>x.Take(i)).Append(x)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You need to include the using System.Linq; in your bytecount. And it seems some of your output logic is in your outputting of the arrays. Because empty array just returns empty array. \$\endgroup\$ – LiefdeWen Dec 11 '18 at 9:51
  • \$\begingroup\$ @LiefdeWen - my understanding is that since this interpreter includes a reference to System.Linq, I don't have to include this in the byte count. My submission would be considered a different language than say .NET Core. github.com/dotnet/roslyn/wiki/C%23-Interactive-Walkthrough - You mention printing which is a separate issue, I'd like to get clarity on this first. \$\endgroup\$ – dana Dec 11 '18 at 10:35
  • \$\begingroup\$ With regards to printing, here is a version that basically dumps the result to the console - tio.run/##XY29CsIwGEX3PEXGBGKhtVt/… - not as pretty for sure! The question I have is when is it acceptable to use Array vs IList vs IEnumerable. \$\endgroup\$ – dana Dec 11 '18 at 10:59
2
\$\begingroup\$

F# (Mono), 45 bytes

fun x->List.mapi(fun i y->List.take i x)x@[x]

Try it online!

I am not totally sure if this is valid, but it seems like it follows the same "anonymous lambda" syntax that I've seem used in several other languages.

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

Java 8+, 86 77 bytes

-9 bytes thanks to Kevin Cruijssen (getting rid of the import)!

x->java.util.stream.IntStream.range(0,x.size()+1).mapToObj(t->x.subList(0,t))

Try it online!

Alternative, 65 bytes

The following will print the results to stdout (due to Olivier Grégoire):

x->{for(int i=0;i<=x.size();)System.out.print(x.subList(0,i++));}

Try it online

\$\endgroup\$
  • \$\begingroup\$ You can golf it to 77 bytes by just using java.util.stream.IntStream directly and drop the import. \$\endgroup\$ – Kevin Cruijssen Dec 10 '18 at 7:44
  • \$\begingroup\$ @KevinCruijssen: Oh thanks! I didn't even know that this was possible, that's certainly helpful (at least for golfing purposes). \$\endgroup\$ – ბიმო Dec 10 '18 at 14:19
  • \$\begingroup\$ x->{for(int i=0;i<=x.size();)System.out.println(x.subList(0,i++));} (67 bytes). This prints instead of using streams. Printing is usually the shortest way to output complex structures. \$\endgroup\$ – Olivier Grégoire Dec 10 '18 at 17:01
  • \$\begingroup\$ @OlivierGrégoire: In that case you can probably get away with System.out.print since the output is still unambiguous. \$\endgroup\$ – ბიმო Dec 10 '18 at 17:55
  • \$\begingroup\$ @BMO Indeed, that would be possible! \$\endgroup\$ – Olivier Grégoire Dec 10 '18 at 23:28
2
\$\begingroup\$

Brachylog, 9 bytes

a₀ᶠ~b.hĖ∧

Try it online!

Explanation

a₀ᶠ           Find all prefixes of the input
   ~b         Add an element at the beginning of that list of prefixes
      hĖ      This element is the empty list
     .  ∧     (the list with the additional empty list is the output)
\$\endgroup\$
2
\$\begingroup\$

Ruby, 31 29 bytes

->a{[a*i=0]+a.map{a[0,i+=1]}}

Try it online!

Explanation:

->a{             # take array input a
  [a*i=0]+       # set i to 0 and add whatever comes next to [[]] (a*0 == [])
  a.map{         # for every element in a (basically do a.length times)
    a[0,i+=1]  # increment i and return the first i-1 elements of a to map
  }
}
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 102 97 bytes

Pretty long, as C quite obviously isn't well-suited to manipulating lists of lists. Dependent on certain behavior; running on some platforms requires changing int to short (for +2 bytes), due to wchar_t being UTF-16 rather than UTF-32. Should work on Linux as-is.

Takes in a pointer to the first element of the input array, the length of the array, and a pointer to the variable in which the pointer to output will be stored. Produces a list of lists such that the first integer in the linear array stores the number of sub-lists. Sub-lists start with the number of elements, and are stored in memory in a contiguous manner.

p(r,e,f,i,x)int*e,**r,*x;{x=*r=malloc(4-++f*~f*2);*x++=f;for(i=0;i<f;x+=++i)wmemcpy(x+1,e,*x=i);}

Try it online!

Degolf

p(r,e,f,i,x) int**r,*e,*x; // Function p(), where r is a pointer to the output variable,
                           // e is a pointer to the input location and f is the size of
                           // the input.
{ 
  x=*r=malloc(4-++f*~f*2); // Allocate 4*(x+1)*(x+2)/2+4 bytes of memory. 
                           // This is the exact amount of memory needed.
  *x++=f;                  // Store n+1 (number of sub-lists) in the first four bytes. 
  for(i=0;i<f;x+=++i)      // Iterate over [0, n]->i and 
                           // increment the pointer to x by i+1 every iteration.
    wmemcpy(x+1,e,*x=i);   // Set first element at location pointed to by x to i,
                           // then copy i of either 2 or 4 byte elements, depending on
                           // the system wchar implementation, to location pointed to
                           // by x+1.
}
\$\endgroup\$
  • \$\begingroup\$ @ceilingcat Thanks, will edit it in later when I get back onto a PC. \$\endgroup\$ – user77406 Jan 2 at 20:34

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.