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

1
\$\begingroup\$

RAD, 7 bytes

(⊂⍬),,\

Try it online!

This also works in Dyalog APL as a function.

How?

This works the same for both APL and RAD, given their close relation.

  • (⊂⍬) the empty array
  • , prepended to
  • ,\ the prefixes (which exclude the empty array.)
\$\endgroup\$
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
\$\begingroup\$

Powershell, 24 bytes

,@()
$args|%{,($x+=,$_)}

Explanation:

  1. The trivial accumulator wrapped to array by unary ,.
  2. The script uses splatting. See parameter @a.

Test script:

$f = {

,@()
$args|%{,($x+=,$_)}

}

@(
    ,( @()        , @() )
    ,( @(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)) )
) | % {
    $a,$expected = $_
    $result = &$f @a

    $false -notin $(
        $result -is [array]
        $result.Count -eq $expected.Count
        for($j=0; $j-lt$result.Count; $j++){
            "$($result[$j])" -eq "$($expected[$j])"
        }
    )

    # $result   # uncomment this line to display a result

}

Output:

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

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\$
  • \$\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\$ – Kevin Cruijssen Dec 10 '18 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 Dec 10 '18 at 14:53
  • \$\begingroup\$ Just edited my comment when I realized that. Just not sure how to fix the test suite.. \$\endgroup\$ – Kevin Cruijssen Dec 10 '18 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\$
  • 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 Dec 10 '18 at 14:56
  • \$\begingroup\$ @maxb Thanks, that simplifies the test suite a lot. Need to remember that. And thanks for the golf! \$\endgroup\$ – Kevin Cruijssen Dec 10 '18 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\$
  • 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\$ – Conor O'Brien Dec 10 '18 at 23:25
  • \$\begingroup\$ @ConorO'Brien: Thanks a lot! 1 fewer byte than Python now :D \$\endgroup\$ – Eric Duminil Dec 11 '18 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\$
  • \$\begingroup\$ I think you might want to reverse that if test. \$\endgroup\$ – Ørjan Johansen Dec 12 '18 at 20:00
  • \$\begingroup\$ @ØrjanJohansen Yep. Thank you. \$\endgroup\$ – Comrade SparklePony Dec 12 '18 at 20:23
1
\$\begingroup\$

D, 70 bytes (31 imports, 39 expression)

import std.algorithm,std.range;
alias prefixes = t=>(t.length+1).iota.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?

\$\endgroup\$
  • 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\$ – Sriotchilism O'Zaic Dec 10 '18 at 15:39
  • 1
    \$\begingroup\$ There is one problem though. I'm pretty sure you need to count the imports. \$\endgroup\$ – Zacharý Dec 10 '18 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\$ – FeepingCreature Dec 10 '18 at 21:33
  • \$\begingroup\$ Though fair enough, the Java example seems to count module names. Bleh. edit: Though it seems pretty nonsensical to count the imports and not the alias, and in any case what about the void main()... seems like it'd just become a boilerplate size contest, rather than expression size. \$\endgroup\$ – FeepingCreature Dec 10 '18 at 21:39
  • 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\$ – Zacharý Dec 11 '18 at 18:38
1
\$\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\$
1
\$\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\$
  • \$\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 Jan 2 at 2:05
  • \$\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\$ – Brian McCutchon Jan 2 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 Jan 2 at 6:27
  • \$\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\$ – Brian McCutchon Jan 2 at 6:38
  • \$\begingroup\$ Oh wait, you can define functions like variables, nvm \$\endgroup\$ – ASCII-only Jan 2 at 6:39
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
\$\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\$
0
\$\begingroup\$

Kotlin, 32 bytes

{l->(0..l.size).map{l.take(it)}}

{ list ->
    (0..list.size).map {  // map over range [0, length of list]
        list.take(it)  // first n items of list
    }
}

Try it online!

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

Pushy, 7 bytes

1@$O_vI

Try it online!

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

Tcl, 65 bytes

proc P {L J\ {{}}} {lmap e $L {lappend J [lappend K $e]}
list $J}

Try it online!

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

Forth (gforth), 57 bytes

: x here 0 begin 2dup type cr 1+ key dup c, 5 < until ; x

Try it online!

Takes bytes through STDIN and prints a series of prefixes, each terminated by a newline.

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

str, 6 bytes

e;:dno

Try it online!

Each output line corresponds to an entry in the prefix array.

Explanation

e;:dno
            -- preamble --
e           push empty string
            -- iteration --
  :         append current char to build string
   d        duplicate it
    n       push "\n"
     o      output it
            (implicitly output duplicated entry)
\$\endgroup\$
0
\$\begingroup\$

Perl 5 + -a, 24 bytes

say"@F[0..$_]"for-1..$#F

Try it online!

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

Actually, 13 bytes

;╗ru⌠╜H⌡M[]@o

Try it online!

Explanation:

;╗ru⌠╜H⌡M[]@o
;╗             save a copy of input in register 0
  ru           range(1, len(input)+1)
    ⌠╜H⌡M      for i in range:
     ╜H          first i elements of input
         []@o  prepend an empty list
\$\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.