39
\$\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.
  • This is , so the shortest code in bytes wins

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\$
5
  • \$\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\$
    – Maya
    Commented Dec 8, 2018 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
    Commented Dec 8, 2018 at 21:18
  • \$\begingroup\$ Can we expect the list to be null-terminated? \$\endgroup\$
    – user77406
    Commented Dec 9, 2018 at 10:02
  • \$\begingroup\$ It's especially common in C/C++, main use being strings. \$\endgroup\$
    – user77406
    Commented Dec 13, 2018 at 14:46
  • \$\begingroup\$ @Rogem If it is that common I think allowing it is reasonable. \$\endgroup\$
    – flawr
    Commented Dec 13, 2018 at 14:49

77 Answers 77

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\$
5
  • \$\begingroup\$ You can golf it to 77 bytes by just using java.util.stream.IntStream directly and drop the import. \$\endgroup\$ Commented Dec 10, 2018 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\$ Commented Dec 10, 2018 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\$ Commented Dec 10, 2018 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\$ Commented Dec 10, 2018 at 17:55
  • \$\begingroup\$ @BMO Indeed, that would be possible! \$\endgroup\$ Commented Dec 10, 2018 at 23:28
2
\$\begingroup\$

05AB1E, 8 bytes

That was my first succesfull golf! Thanks for being such a nice community!

)UŒ¹g£Xš

Try it online!

Explanation:

)UŒ¹g£Xš
)        : Create an empty list
 U       : Save it to variable ˙X˙
  Π     : Make the "substrings" of the implicit input
   ¹g£   : Take the first n elements of the result where n is the lenght of input
      Xš : Add the empty list to the beginning       
\$\endgroup\$
2
\$\begingroup\$

Scala, 21 bytes

_.inits.toSeq.reverse

Try it online!

Not quite a trivial answer, since I had to deal with the fact that the inits method returns an iterator in the reverse of the required order.

\$\endgroup\$
5
  • \$\begingroup\$ Not sure if this is valid since this is a function, not a lambda (and you're excluding the function declaration part). Hmmmmmm \$\endgroup\$
    – ASCII-only
    Commented Jan 2, 2019 at 2:05
  • 1
    \$\begingroup\$ @ASCII-only This is Scala's underscore shorthand syntax. It's basically a lambda. Compare to Haskell's sections. See also codegolf.meta.stackexchange.com/questions/11223/… \$\endgroup\$ Commented Jan 2, 2019 at 6:24
  • \$\begingroup\$ Yes, but it can not be assigned to a variable (lambda function). On the other hand, {_.inits.toSeq.reverse} can. \$\endgroup\$
    – ASCII-only
    Commented Jan 2, 2019 at 6:27
  • 1
    \$\begingroup\$ @ASCII-only Nope, the braces are not needed (though you do need to use val instead of var for some reason): tio.run/##JYq9CgIxEAb7e4qvTCAE/… \$\endgroup\$ Commented Jan 2, 2019 at 6:38
  • \$\begingroup\$ Oh wait, you can define functions like variables, nvm \$\endgroup\$
    – ASCII-only
    Commented Jan 2, 2019 at 6:39
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\$
1
  • \$\begingroup\$ @ceilingcat Thanks, will edit it in later when I get back onto a PC. \$\endgroup\$
    – user77406
    Commented Jan 2, 2019 at 20:34
2
\$\begingroup\$

Swift, 60 54 bytes

let f={(i:[Int])in return[[]]+i.indices.map{i[...$0]}}

Try it online!

Defines a function that takes an array of ints and returns an Array of ArraySlices (i.e, they reference the same memory as the input array). To turn into real arrays, it's 67 61 bytes.

let f={(i:[Int])in return[[]]+i.indices.map{Array(i[...$0])}}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Commented Jan 19, 2023 at 17:18
1
\$\begingroup\$

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

l=>new int[l.Count()+1].Select((_,n)=>l.Take(n))

Try it online!

Explanation

l=>                                                // Function with list l as argument
   new int[l.Count()+1]                            // A new array (int is shortest type available) of length l + 1
                       .Select((_,n)=>l.Take(n))   // Where every element is mapped to the first n elements of the input list, where n is the index
\$\endgroup\$
1
\$\begingroup\$

Lua 5.3, 92 bytes

function f(...)t=...if#t>0then return f({table.unpack(t,1,#t-1)},...)else return{...}end end

Keeps creating a copy of the array-like table with the element at the end removed and prepending it to the varargs until the length of the table is 0, then puts the varargs in a table. Relies on defining the variable f to allow recursion.

Lua 5.1, 87 bytes

function f(...)t=...if#t>0 then return f({unpack(t,1,#t-1)},...)else return{...}end end

unpack is a global variable rather than a member of the table library. 0then is syntactically invalid in Lua 5.1, but strangely not in Lua 5.3.

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

Pari/GP, 23 bytes

a->[a[1..n]|n<-[0..#a]]

Try it online!

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

Pip, 16 bytes

{h@<a}M,1+#(h:a)

Try it online!

Explanation

      M            Map
{h@<a}                 Function returning global variable h, cut at index a, and left part taken (0-indexed)
       ,               Range from 1 to
        1+#(   )           1 + the length of
            h:a                Assign global variable h to a, evaulating to the value of h (which is also the value of a - the first parameter to the function)
\$\endgroup\$
1
1
\$\begingroup\$

MY, 7 bytes

ωωι0;↑←

Try it online!

Woah ... never thought MY would actually come in handy.

How?

ωωι0;↑←

  • ω = push(arg[0])
  • ω = push(arg[0])
  • ι = push([1 ... pop()])
  • 0 = push(0)
  • ; = push(pop() + pop())
  • = does the prefixing work by vecifying in a stupid manner.
  • output
\$\endgroup\$
1
\$\begingroup\$

Factor, 63 bytes

USE: fry [ [ dup '[ nip _ swap head ] map-index ] keep suffix ]

Keeps a copy of the input to tack on at the end, like C#.

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

Z80Golf, 18 bytes

00000000: 2511 00ff 1b1a ffa7 20fa cd03 802b 7730  %....... ....+w0
00000010: f076                                     .v

Try it online!

Takes bytes through STDIN with no null bytes and prints a series of prefixes, each terminated by a null byte.

Source code:

    dec h
start:
    ld de, $ff00
.printloop:
    dec de
    ld a, (de)
    rst $38
    and a
    jr nz, .printloop
    call $8003
    dec hl
    ld (hl), a
    jr nc, start
    halt
\$\endgroup\$
1
\$\begingroup\$

FALSE, 57 bytes

1^[$~][\1+^]#%a:0[$a;1->~][0[$@$@>][\$a;\-ø,1+]#\%10,1+]#

Try it online! (you'll have to copy paste the code. Click "Show" and then run)

Like brainf*ck, FALSE only takes one char at a time as input, so this program splits a string into prefixes, separating them with a newline.

Explanation:

1^         {push 1 {counter) and first character onto stack}
[$~][      {while a character is input:}
  \1+^     {add 1 to the counter}
]#

%          {drop truth value from stack}
a:         {define the counter as the variable "a'}
0          {push 0 onto stack (loopvar)}
[$a;1->~][ {while loopvar is less than a-1:}

  0        {push 0 (loopvar2)}
  [$@$@>][ {while loopvar is greater than loopvar2}
    \$a;\- {a-loopvar2 (to get index of char to print)}
    ø,     {copy value at index to top of stack and print}
    1+     {increment loopvar2}
  ]#
  \%       {swap'n'drop (get rid of loopvar2)}
  10,      {print newline}
  1+       {increment loopvar}
]#

A FALSE expert could probably do this using no variables (pure stack) but since I only learnt this language yesterday I think this is alright.

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

MathGolf, 7 bytes

hæ_ï<\]

Try it online!

Explanation

h         length of array/string without popping
 æ        start block of length 4
  _       duplicate TOS
   ï      index of current loop, or length of last loop
    <     slice list
     \    swap top elements
      ]   end array / wrap stack in array
\$\endgroup\$
3
  • \$\begingroup\$ Nice 7 byte alternative to my 7-byter I found an hour ago. :) Actually, I see I can golf mine to 6 bytes by changing { to Å. Thanks for the implicit golf. Now I just need to fix the test suite somehow.. \$\endgroup\$ Commented Dec 10, 2018 at 14:49
  • \$\begingroup\$ You could save a byte for that one by replacing { with Å and removing the }. MathGolf has 1-byte literals for blocks of size up to 8 bytes. \$\endgroup\$
    – maxb
    Commented Dec 10, 2018 at 14:53
  • \$\begingroup\$ Just edited my comment when I realized that. Just not sure how to fix the test suite.. \$\endgroup\$ Commented Dec 10, 2018 at 14:53
1
\$\begingroup\$

MathGolf, 9 7 6 bytes

hÅ_╡]x

-1 byte thanks to @maxb.

Try it online or verify all test cases.

Explanation:

h        # Push the length of the (implicit) input-array, without popping the array
 Å       # Loop this length amount of times,
         # and do the following two commands each iteration:
  _      #  Duplicate the array at the top of the stack
   ╡     #  Remove the right-most item of the array
    ]    # After the loop, wrap everything on the stack in an array
     x   # Reverse it (and output implicitly)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ hÅ_╡]x saves one byte. For doing test suites, just add one input per line, and the code will be executed separately for each input. Check my answer for an example. I should describe that feature better in the docs. \$\endgroup\$
    – maxb
    Commented Dec 10, 2018 at 14:56
  • \$\begingroup\$ @maxb Thanks, that simplifies the test suite a lot. Need to remember that. And thanks for the golf! \$\endgroup\$ Commented Dec 10, 2018 at 15:00
1
\$\begingroup\$

Clojure, 21 bytes

#(reductions conj[]%)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 34 31 bytes

->l{(0..l.size).map{|i|l[0,i]}}

Try it online!

Thanks @ConorO'Brien!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can golf this a bit like so: ->l{(0..l.size).map{|i|l[0,i]}}, using [0,i] for indexing instead of .first i \$\endgroup\$ Commented Dec 10, 2018 at 23:25
  • \$\begingroup\$ @ConorO'Brien: Thanks a lot! 1 fewer byte than Python now :D \$\endgroup\$ Commented Dec 11, 2018 at 8:24
1
\$\begingroup\$

Gambit Scheme (gsi), 77 72 bytes

(define(p z)(if(pair?(car z))(p(cons(reverse(cdr(reverse(car z))))z))z))

Try it online!

First time using Scheme. It's a function that takes a wrapped list ((list (list 1 2 3 4))) as an argument.

\$\endgroup\$
2
  • \$\begingroup\$ I think you might want to reverse that if test. \$\endgroup\$ Commented Dec 12, 2018 at 20:00
  • \$\begingroup\$ @ØrjanJohansen Yep. Thank you. \$\endgroup\$
    – sporkl
    Commented Dec 12, 2018 at 20:23
1
\$\begingroup\$

Google Sheets, 102

  • Input is in Row 1
  • A2: COUNTA(1:1)
  • Output: =ArrayFormula(IF(A2,{T(SEQUENCE(1,A2));IF(SEQUENCE(A2)>=SEQUENCE(1,A2),OFFSET(A1,,,,A2),)},

Output Formatted:

=ArrayFormula(IF(
  A2,
  {
    T(SEQUENCE(1,A2));
    IF(
      SEQUENCE(A2)>=SEQUENCE(1,A2),
      OFFSET(A1,,,,A2),
    )
  },
))
\$\endgroup\$
1
\$\begingroup\$

Add++, 14 bytes

L*,¬b[€bFbUBpA

Try it online!

How it works

L		; Lambda function. Takes A as argument
	*,	; Return the enire stack
		; E.g. A = [1 2 3 4]
	¬b[	; Scan pair;	STACK = [[1 [1 2] [[1 2] 3] [[[1 2] 3] 4]]]
	€bF	; Flatten each;	STACK = [[[1] [1 2] [1 2 3] [1 2 3 4]]]
	bU	; Splat;	STACK = [[1] [1 2] [1 2 3] [1 2 3 4]]
	Bp	; Pop each;	STACK = [[] [1] [1 2] [1 2 3]]
	A	; Push A;	STACK = [[] [1] [1 2] [1 2 3] [1 2 3 4]]
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 3 bytes

K¾p

Try it Online!

\$\endgroup\$
3
  • \$\begingroup\$ Unfortunately, the results have to contain the empty list. \$\endgroup\$
    – lyxal
    Commented May 31, 2021 at 3:06
  • \$\begingroup\$ I'm not happy that the 1 byte answer isn't valid either. But 3 bytes is the best I can think of \$\endgroup\$
    – lyxal
    Commented May 31, 2021 at 3:07
  • \$\begingroup\$ @lyxal oh i didn't notice the empty list requirement before, but we have to accept our fate, whatever \$\endgroup\$
    – Wasif
    Commented May 31, 2021 at 3:08
1
\$\begingroup\$

Julia 1.0, 26 bytes

~l=0:length(l).|>i->l[1:i]

Try it online!

alternative solution in Julia 1.6+, 26 bytes:

~l=first.([l],0:length(l)) Try it online!

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

Pip, 6 bytes

_H,U#_

Anonymous function that takes an iterable and returns a list of iterables. (A full program would be the same number of bytes, but would require flags.) Attempt This Online!

Explanation

    #_  ; Length of function argument
   U    ; Incremented
  ,     ; Range from 0 up to one less than that number, i.e. 0..len
_H      ; For each of those numbers n, get the first n elements of the function argument
\$\endgroup\$
1
\$\begingroup\$

D, 49 bytes (11 imports, 38 expression)

import std;
alias prefixes = t=>iota(t.length+1).map!(i=>t.take(i));

Try it online!

edit: Do I count the alias prefixes = part? You can use the lambda without it, but you have to add parens to disambiguate, so should I count it as 42?

edit: We now got import std; as a shortcut. That solves things!

\$\endgroup\$
8
  • 1
    \$\begingroup\$ I don't program in D, but I think you don't count the alias prefixes. Python lambdas are very similar and they act in that way. \$\endgroup\$
    – Wheat Wizard
    Commented Dec 10, 2018 at 15:39
  • 1
    \$\begingroup\$ There is one problem though. I'm pretty sure you need to count the imports. \$\endgroup\$
    – Adalynn
    Commented Dec 10, 2018 at 18:32
  • \$\begingroup\$ Wait, none of the others use standard library routines? edit: I feel it'd be kind of silly to make code size dependent on what standard definitions the language chooses to make available by default. That seems more of a judgment of a language's module system than its expressivity. \$\endgroup\$ Commented Dec 10, 2018 at 21:33
  • 1
    \$\begingroup\$ One would count this as if it was import std.algorithm,std.range;t=>(t.length+1).iota.map!(i=>t.take(i)) \$\endgroup\$
    – Adalynn
    Commented Dec 11, 2018 at 18:34
  • 1
    \$\begingroup\$ So, in response to my above comment: this would count as 70 bytes. (Note: a golf was applied changing two imports to a single import) \$\endgroup\$
    – Adalynn
    Commented Dec 11, 2018 at 18:38
1
\$\begingroup\$

Go, 72 bytes

func(I[]int)(o[][]int){for i:=0;i<=len(I);i++{o=append(o,I[:i])};return}

Attempt This Online!

Generic, 77 bytes

func f[T any](I[]T)(o[][]T){for i:=0;i<=len(I);i++{o=append(o,I[:i])};return}

Attempt This Online!

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

Haskell, 27 bytes

i[]=[[]]
i l=i(init l)++[l]

Try it online!

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

Canvas, 6 5 bytes

)╶[})

Try it here!

Outputs to the stack; Linked with a trailing raw so that's visible.

)      wrap the (currently empty) stack in an array
 ╶[}   map nothing over the prefixes of the input
    )  wrap the stack (the empty array and the prefixes) in an array

2 bytes without the starting empty array.

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

Attache, 13 bytes

{_[0...0:#_]}

Try it online!

Explanation

{_[0...0:#_]}
{           }    block taking `_` as input
 _[        ]     index from the input
       0:#_      range from 0 to the length of `_` inclusive
   0...          range from 0 to each number that range, right exclusive
\$\endgroup\$
0
\$\begingroup\$

Tcl, 81 bytes

set i -1
set a {{}}
foreach _ $argv {lappend a [lrange $argv 0 [incr i]]}
puts $a

Try it online!

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

Red, 76 bytes

func[b][a: copy[[]]c: b until[append/only a copy/part b c: next c tail? c]a]

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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