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

1 2
3
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\$

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

Elixir, 37 bytes

fn x->Enum.scan [[]|x],&(&2++[&1])end

Try it online!

Looking at other languages, this looks rather verbose, but I'm definitely not an expert in Elixir, so please let me know if I missed something obvious.

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

APL (Dyalog Unicode), 12 bytes

(0,∘⍳∘≢⊢)↑¨⊂

Try it online!

Prefix tacit function. TIO link has boxing enabled to make the output more readable.

How:

(0,∘⍳∘≢⊢)↑¨⊂ ⍝ Tacit fn, taking a vector as argument, which will be called ⍵ for simplicity.
         ↑   ⍝ Take the first ⍺ (left arg) elements of ⍵
          ¨⊂ ⍝ Since the ⍺ for ↑ is a vector, we enclose the ⍵ and apply ↑ to it for each of the elements in ⍺.
(      ⊢)    ⍝ Use ⍵ as argument for
      ≢      ⍝ Tally; yields the number of elements in ⍵
    ⍳∘       ⍝ Then, yield the range [1..≢⍵]
 0,∘         ⍝ and prepend a 0.

The function returns a vector of vectors, each with the first [0..≢⍵] elements of the argument.

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

Bash, 34 bytes

I output each list element on a new line as someone else did - bash only has 1-D arrays:

for((;c<=$#;c++)){ echo ${*:1:c};}

Could be 1 byte less but this does not work for null case - don't see why... c++ does not get evaluated...

for((;c<=$#;)){ echo ${*:1:c++};}

This can output text as suggested by OP:

C='echo -n ';A=(${1//[],[]/ });$C[[];for((c=0;c<${#A[*]};)){ B=${A[*]::++c};$C,[${B// /,}];};echo ]

No one should have to decode that. Here is annotated version:

C='echo -n '              # basically a macro to improve my golf
A=( ${1//[],[]/ } )       # convert [,] to spaces - like magic this one
$C[[]                     # echo [[] since every list needs this
for((c=0;c<${#A[*]};)){   # for all elements of list
  B=${A[*]::++c}          # make space separated list of first c elements
  $C,[${B// /,}]          # prefix with ,[ and convert space to comma
}
echo ]                    # terminate list with ]
\$\endgroup\$
0
\$\begingroup\$

Reticular, 60 bytes

Bql:D=:D`:E=l[:D`@d]~*[:E`b@qM[$]:D`:E`-*:E`1-:E=]:D`1+*lbo;

Try it online!

Assumes that the input list is at the top of the stack. To test input, run the following code

'1''2''3''4''5'lbBql:D=:D`:E=l[:D`@d]~*[:E`b@qM[$]:D`:E`-*:E`1-:E=]:D`1+*lbo;

Explanation

B                         # Push every element from the input list to the stack.
 q                        # Reverse stack.
  l                       # Push the size of the stack to the stack.
   :D=                    # Save it as the variable D.
      :D`:E=              # Define the variable E = D.
            l             # Push D to the stack.
             [:D`@d]      # Push the function which duplicates the top D items in the stack
                    ~     # Swap the top two items in the stack
                     *    # Call the above function D number of times.



[                          ]            # Push a function that does the following:
 :E`b                                   # Put the top E items in a list.
     @q                                 # Reverse list that is at the top of the stack.
       M                                # Rotate stack so that top of stack -> bottom of stack.
        [$]:D`:E`-*                     # Delete the top D-E items from the stack.
                   :E`1-:E=             # Define E = E - 1.
                            :D`1+*      # Call the above function D+1 number of times.
                                  q     # Reverse stack.
                                   lb   # Put every item in the stack into a list.
                                     o; # Output the resulting list and exit.
\$\endgroup\$
0
\$\begingroup\$

Scala, 28 bytes

_.scanLeft(Seq[Int]())(_:+_)

Try it online!

This is longer than the Scala answer that's already here, but uses a different method. Unfortunately, the [Int] must be used to avoid Nothing being inferred.

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

Factor + grouping.extras, 25 bytes

[ head-clump { } prefix ]

Try it online!

Mostly a built-in. Just have to add the empty list at the beginning.

Compare to a non-trivial answer:

[ dup length [0,b] [ head ] with map ]

Try it online!

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

Pyth, 6 bytes

Sa._QY

Try it online!

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

Arturo, 31 29 bytes

$[a][map 0..size a=>[take a]]

Try it

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

x86 opcode, 11 bytes

xor eax, eax
inc ecx
P:
xchg eax, esi
stosd
xchg eax, esi
stosd
inc eax
loop P
ret

Take ecx(length) esi(input array) edi(output buffer) output (array,length) pairs

Somehow cheaty :)

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

Thunno, \$ 11 \log_{256}(96) \approx \$ 9.05 bytes

0TzreRz0sAI

Attempt This Online!

Explanation

0TzreRz0sAI  # Implicit input
0T           # Append a 0 (so the length is increased by 1)
  zr         # Length range, [0..len)
    e        # Map over this list:
     R       #   Range from 0 to this number
        sAI  #   Index this into
      z0     #   The input
             # Implicit output
\$\endgroup\$
1 2
3

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.