P Pr Pref Pref Префикс Префикс Префикс Префиксы

34

Имея некоторый конечный список, вернуть список всех его префиксов, включая пустой список, в порядке возрастания их длины.

(В основном реализация функции Haskell inits.)

Детали

  • Список ввода содержит числа (или другой тип, если это более удобно).
  • Вывод должен быть списком списков .
  • Представление может, но не обязательно должно быть функцией, любой ввод / вывод по умолчанию может быть использован.
  • Есть ответ CW для всех тривиальных решений .

пример

[] -> [[]]
[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]]
flawr
источник
Если язык не определяет какие-либо типы, кроме символов, могу ли я взять ввод в виде строки и отделить ввод переводом строки, в случае полной программы?
NieDzejkob
@NieDzejkob Я не уверен, какой консенсус существует для этого случая, но ответ Brainfuck, кажется, делает что-то подобное.
flawr
Можем ли мы ожидать, что список будет заканчиваться нулем?
Это особенно часто встречается в C / C ++, в основном это строки.
@Rogem Если это так, я думаю, что позволять это разумно.
flawr

Ответы:

15

Haskell , 20 байтов

Изменить: еще байта короче с совершенно другим сканированием.

Анонимная функция немного превосходит тривиальный импорт.

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

Попробуйте онлайн!

  • Используется =<<для сокращения (scanr(\_->init)=<<id) l = scanr(\_->init) l l.
  • Сканирует список lсправа налево, собирая промежуточные результаты с помощью функции \_->init.
  • Эта функция игнорирует просканированные элементы (они используются только для получения правильной общей длины для собранных результатов), поэтому действительно повторяет применение initк начальному значению сканирования, которое также l.
Орджан Йохансен
источник
13

Брейкфук , 21 12 байт

-9 байт благодаря Арно, предложившему разделитель ÿвместо новых строк

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

Попробуйте онлайн!

Принимает байты через STDIN без нулевых байтов и печатает серию префиксов, разделенных ÿсимволом с начальным ÿсимволом. Например, для вводаPrefixes , выход ÿÿPÿPrÿPreÿPrefÿPrefiÿPrefixÿPrefixeÿPrefixes.

Для удобства чтения, вот версия с переводом строки .

Объяснение:

-              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
Джо Кинг
источник
1
Это работает только в реализациях BF с 8-разрядными беззнаковыми обертывающими ячейками.
Дев
11

JavaScript (ES6), 33 байта

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

Попробуйте онлайн!

Как?

+--- 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
Arnauld
источник
вау, это совершенно новый уровень объяснения кода, потрясающая работа: O
Брайан Х.
@BrianH. Спасибо! Простые задачи - это хорошая возможность написать подробные объяснения, которые невозможно выразить в более плотном коде.
Арно
Вы сделали это вручную? или вы получили помощь от любого странного программного обеспечения, о котором я никогда не слышал?
Брайан Х.
2
Просто Notepad ++ с некоторыми режимами редактирования колонок .
Арно
8

CW для всех тривиальных записей

чистый , 19 байт

Версия на Haskell работает и в Clean.

import StdLib
inits

Попробуйте онлайн!

Haskell , 22 байта

import Data.List
inits

Попробуйте онлайн!

Пролог (SWI) , 6 байт

prefix

Попробуйте онлайн!

только для ASCII
источник
Так рвется - голосовать или нет. С одной стороны, я ценю все встроенные решения в одном месте. С другой стороны, мне очень не нравятся встроенные функции, потому что они такие простые ...
6

Желе , 3 байта

ṭṖƤ

Попробуйте онлайн!

Как это работает

ṭṖƤ  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.
Dennis
источник
6

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
Kamil Drakari
источник
6

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

Sean
источник
2
O_o what is even happening here
ASCII-only
1
@ASCII-only triangular reduction
user202729
5

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.

Giuseppe
источник
1
39 using lapply
digEmAll
@digEmAll thanks!
Giuseppe
4

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.

LegionMammal978
источник
We can write the same solution more compactly as {}~FoldList@Append~#&.
Misha Lavrov
@MishaLavrov Thanks! I didn't think to use the curried 1+2-argument form like that.
LegionMammal978
3

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.

AdmBorkBork
источник
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.
Veskah
@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
AdmBorkBork
3

K (ngn/k), 8 bytes

,\(,!0),

Try it online!

ngn
источник
1
This is some kind of voodoo. ,\(,()), in K4. Joining enlisted null along enlisted input? howsitwork?
streetster
1
@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".
ngn
1
@streetster в k4 это может быть на байт короче: 1_',\0,но мой парсер не достаточно умен, чтобы справиться с этим ...
ngn
3

Common Lisp , 39 байт

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

Попробуйте онлайн!

объяснение

(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
ASCII-только
источник
3

F #, 53 байта

На самом деле у меня есть два довольно похожих ответа, оба одинаковой длины. Они оба принимают общую последовательностьs as a parameter.

Первое решение:

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

Попробуйте онлайн!

Seq.takeзанимает первые nэлементы последовательности. Seq.initсоздает новую последовательность с количеством (в данном случае) длины последовательности sплюс 1, и для каждого элемента в последовательности принимает первые nэлементы в s.

Второе решение:

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!

Ciaran_McCarthy
источник
fun s->Seq.map(fun n->Seq.take n s){0..Seq.length s} saves 1 byte
Embodiment of Ignorance
3

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
Suever
источник
use v instead of []. And doesn't : use 1 as the default first argument? So this could be vin:"G@:)]Xh for 12 bytes.
Giuseppe
@Giuseppe Thanks! My MATL is a little rusty it seems :(
Suever
2

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.

Neil
источник
2

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.)
Zacharý
источник
2

Groovy, 37 bytes

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

Try it online!

GolfIsAGoodWalkSpoilt
источник
{it.inits().reverse()} will work once we get groovy 2.5 on TIO
ASCII-only
2

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!

user202729
источник
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.
user202729
40 bytes with some rearranging
Jo King
2

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

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

Try it online!

dana
источник
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.
LiefdeWen
@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.
dana
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.
dana
2

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.

dana
источник
2

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

ბიმო
источник
You can golf it to 77 bytes by just using java.util.stream.IntStream directly and drop the import.
Kevin Cruijssen
@KevinCruijssen: Oh thanks! I didn't even know that this was possible, that's certainly helpful (at least for golfing purposes).
ბიმო
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.
Olivier Grégoire
@OlivierGrégoire: In that case you can probably get away with System.out.print since the output is still unambiguous.
ბიმო
@BMO Indeed, that would be possible!
Olivier Grégoire
2

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)
Fatalize
источник
2

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
  }
}
Asone Tuhid
источник