Préfixe Préfixe Préfixe Préfixe

34

Pour une liste finie, retourne une liste de tous ses préfixes, y compris une liste vide, dans l'ordre croissant de leur longueur.

(Implémentation de la fonction Haskell inits.)

Détails

  • La liste de saisie contient des nombres (ou un autre type si cela convient mieux).
  • La sortie doit être une liste de listes .
  • La soumission peut, mais ne doit pas nécessairement être une fonction, toutes les E / S par défaut peuvent être utilisées.
  • Il existe une réponse CW pour toutes les solutions triviales .

Exemple

[] -> [[]]
[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
la source
Si une langue ne définit aucun type, à l'exception des caractères, puis-je prendre une entrée sous forme de chaîne et séparer l'entrée par une nouvelle ligne, dans le cas d'un programme complet?
NieDzejkob
@NieDzejkob Je ne suis pas sûr du consensus sur ce cas, mais la réponse de Brainfuck semble faire quelque chose comme ça.
Flawr
Pouvons-nous nous attendre à ce que la liste soit terminée à zéro?
C'est particulièrement courant en C / C ++, l'utilisation principale étant les chaînes.
@Rogem Si c'est aussi commun, je pense que le permettre est raisonnable.
Flawr

Réponses:

15

Haskell , 20 octets

Edit: Encore un octet plus court avec un scan complètement différent.

Une fonction anonyme battant légèrement l’importation triviale.

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

Essayez-le en ligne!

  • Utilisations =<<pour l'abréviation (scanr(\_->init)=<<id) l = scanr(\_->init) l l.
  • Parcourt une liste lde droite à gauche, en collectant des résultats intermédiaires avec la fonction \_->init.
  • Cette fonction ignore les éléments analysés (ils ne sont utilisés que pour obtenir la longueur totale correcte pour les résultats collectés). Il est donc vraiment itéré de s’appliquer inità la valeur initiale de l’analyse, qui est également l.
Ørjan Johansen
la source
13

brainfuck , 21 12 octets

-9 octets grâce à Arnauld qui a suggéré le séparateur ÿau lieu des sauts de ligne

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

Essayez-le en ligne!

Prend des octets via STDIN sans octets nuls et imprime une série de préfixes séparés par le ÿcaractère précédé d'un ÿcaractère. Par exemple, pour l'entrée Prefixes, la sortie est ÿÿPÿPrÿPreÿPrefÿPrefiÿPrefixÿPrefixeÿPrefixes.

Pour plus de lisibilité, voici une version avec des nouvelles lignes .

Explication:

-              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
Jo King
la source
1
Cela ne fonctionne que sur les implémentations BF avec des cellules d'encapsulation non signées 8 bits.
Dév
11

JavaScript (ES6), 33 octets

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

Essayez-le en ligne!

Comment?

+--- 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
la source
wow, c'est un tout nouveau niveau d'explication de code, super boulot: O
Brian H.
@BrianH. Merci! Les tâches simples sont de bonnes occasions d’écrire des explications détaillées qui ne peuvent pas être évoquées dans un code plus dense.
Arnauld
L'avez-vous fait à la main? ou avez-vous eu l'aide d'un logiciel étrange dont je n'ai jamais entendu parler?
Brian H.
2
Juste Notepad ++ avec une édition en mode colonne .
Arnauld
8

CW pour toutes les entrées triviales

Propre , 19 octets

La version Haskell fonctionne également dans Clean.

import StdLib
inits

Essayez-le en ligne!

Haskell , 22 octets

import Data.List
inits

Essayez-le en ligne!

Prolog (SWI) , 6 octets

prefix

Essayez-le en ligne!

ASCII uniquement
la source
Si déchiré - à inviter ou non. D'un côté, j'apprécie toutes les solutions intégrées en un seul endroit. D'autre part, je n'aime vraiment pas les éléments intégrés car ils sont si élémentaires ...
6

Gelée , 3 octets

ṭṖƤ

Essayez-le en ligne!

Comment ça marche

ṭṖƤ  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
la source
6

Japt , 4 octets

²£¯Y

Essayez-le en ligne!

Explication:

²       :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
la source
6

Perl 6 , 13 octets

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

Essayez-le en ligne!

Expliquer:

En Perl 6, vous pouvez placer un opérateur entre crochets comme moyen alternatif d’écrire une réduction de liste. [+] @arrayrenvoie la somme des éléments entrants @array, [*] @arrayrenvoie le produit, etc. Vous pouvez également faire précéder l'opérateur d'une barre oblique inverse pour créer une réduction "triangulaire", que certaines langues appellent "analyse". Donc, [\+] @arrayretourne une liste composée du premier élément de @array, puis de la somme des deux premiers éléments, puis de la somme des trois premiers éléments, etc.

Voici [\,] @_une réduction triangulaire sur le tableau d'entrée @_à l'aide de l'opérateur de construction de liste ,. Donc, il s’agit d’une liste de listes: le premier élément de @_, les deux premiers éléments de @_, etc. C’est presque ce dont nous avons besoin, mais le problème appelle d’abord une liste vide. Ainsi, le premier élément de la liste de retour est une liste vide littérale (),, puis la réduction sur la liste d'entrée est aplatie dans le reste de la liste de retour avec |.

Sean
la source
2
O_o ce qui se passe même ici
ASCII seulement
1
@ Réduction triangulaire
utilisateur202729
5

Python 2 , 32 octets

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

Essayez-le en ligne!

ovs
la source
1
Fonctionne également en Python 3
ASCII uniquement
5

R , 40 39 octets

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

Essayez-le en ligne!

-1 octet grâce à digEmAll

La sortie du listtype de R est un peu bizarre; il utilise l'indexation séquentielle, de sorte que, par exemple, la sortie de

list(1,2) est

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

Prendre une entrée en tant que vecteur donne un format de sortie plus net, bien que les entrées ne soient pas techniquement lists.

Giuseppe
la source
1
39 utilisant lapply
digEmAll
@digEmAll merci!
Giuseppe
4

JavaScript, 36 octets

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

Essayez-le en ligne!

Oliver
la source
4

Mathematica, 22 21 octets

-1 octet grâce à Misha Lavrov !

{}~FoldList@Append~#&

Fonction pure. Prend une liste en entrée et renvoie une liste de listes en sortie. Je crois que c'est la solution la plus courte possible.

LegionMammal978
la source
Nous pouvons écrire la même solution plus compactement que {}~FoldList@Append~#&.
Misha Lavrov
@MishaLavrov Merci! Je ne pensais pas utiliser la forme au curry 1 + 2 arguments comme ça.
LegionMammal978
3

PowerShell , 65 octets

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

Essayez-le en ligne!

PowerShell déroule utilement les listes de listes lorsque la valeur par défaut Write-Outputsurvient à la fin du programme. Vous obtenez ainsi un élément par ligne. Clique sur a -join','pour mieux voir la liste de listes, en convertissant les listes intérieures en chaînes.

(Ab) utilise le fait que toute tentative de sortie d'un tableau vide (par exemple @()) n'entraîne aucune sortie. Par conséquent, une entrée de tableau vide a simplement ''pour sortie, car elle $a[0..$_]n'aboutira à rien. Cela déclenchera également des messages d'erreur spectaculaires.

AdmBorkBork
la source
Le placer entre parenthèses au lieu de l’affecter économise 20 octets . À moins que vous ne pensiez pas que cela compte comme retour d'une liste de listes. J'ai toujours été flou sur cette distinction.
Veskah
@veskah Ouais, c'est presque ce que j'avais avant mon édition de cette version. Le problème avec votre solution ou ma solution précédente - il ne retourne pas une liste de listes. TIO1 vs TIO2
AdmBorkBork
3

K (ngn / k) , 8 octets

,\(,!0),

Essayez-le en ligne!

ngn
la source
1
C'est une sorte de vaudou. ,\(,()),dans K4. Rejoindre les enrôlés null le long des entrées enrôlées? howsitwork?
streetster
1
@streetster ()est une liste vide. (,()),xle prépare à x. fait finalement ,\ un concat-scan. le xest omis pour former une composition. notez que la fin ,est dyadique, donc "concat", pas "enrôler".
ngn
1
@streetster in k4 cela peut être un octet plus court: 1_',\0,mais mon analyseur n'est pas assez intelligent pour gérer ça ...
ngn
3

Common Lisp , 39 octets

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

Essayez-le en ligne!

Explication

(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 seulement
la source
3

F #, 53 octets

J'ai en fait deux réponses assez similaires pour cela, les deux de la même longueur. Ils prennent tous deux une séquence générique sen paramètre.

Première solution:

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

Essayez-le en ligne!

Seq.takeprend les premiers néléments de la séquence. Seq.initcrée une nouvelle séquence avec un compte (dans ce cas) de la longueur de la séquence splus 1, et pour chaque élément de la séquence prend les premiers néléments dans s.

Deuxième solution:

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

Semblable à avant, sauf qu'il crée une séquence de 0 à la longueur de s. Puis prend ce nombre d'éléments de s.

Essayez ceci en ligne aussi!

Ciaran_McCarthy
la source
fun s->Seq.map(fun n->Seq.take n s){0..Seq.length s} sauve 1 octet
Incarnation de l'Ignorance
3

MATL, 15 12 octets

3 octets sauvés grâce à @Giuseppe

vin:"G@:)]Xh

Essayez-le sur MATL Online .

En raison de la façon dont MATL affiche la sortie, vous ne pouvez pas voir explicitement le tableau vide dans le tableau de cellules. Voici une version qui montre la sortie un peu plus explicitement.

Explication

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
la source
utiliser vau lieu de []. Et ne pas :utiliser 1comme premier argument par défaut? Donc, cela pourrait être vin:"G@:)]Xhpour 12 octets.
Giuseppe
@ Giuseppe Merci! Il semble que mon MATL soit un peu rouillé :(
Suever
2

charbon , 6 octets

Eθ…θκθ

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Explication:

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

Il est possible, avec un coût d'un octet, de demander à Charcoal d'imprimer un n+1tableau d'élément comportant le dernier élément en entrée, mais le résultat est identique, bien que la position du curseur soit différente si vous imprimez autre chose.

Neil
la source
2

RAD , 7 octets

(⊂⍬),,\

Essayez-le en ligne!

Cela fonctionne également dans Dyalog APL en tant que fonction.

Comment?

Cela fonctionne de la même manière pour APL et RAD, étant donné leur relation étroite.

  • (⊂⍬) le tableau vide
  • , préposé à
  • ,\ les préfixes (qui excluent le tableau vide.)
Zacharý
la source
2

Groovy , 37 octets

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

Essayez-le en ligne!

GolfIsAGoodWalkSpoilt
la source
{it.inits().reverse()}fonctionnera une fois que nous aurons le groovy 2.5 sur TIO
ASCII uniquement
2

brainfuck , 43 octets

Prend une liste de caractères non nuls en entrée et renvoie tous les préfixes séparés par une nouvelle ligne. Nécessite un ruban double-infini ou enveloppant.

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

Essayez-le en ligne!

utilisateur202729
la source
Une autre réponse m'a égaré de plus de moitié, parce que je ne pensais pas à l'impression en lisant. Bien sûr, cette méthode ne fonctionnera pas avec l’impression croissante de suffixes.
user202729
40 octets avec quelques réarrangements
Jo King
2

C # (compilateur interactif Visual C #) , 39 octets

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

Essayez-le en ligne!

Dana
la source
Vous devez inclure l'utilisation System.Linq; dans votre décompte. Et il semble qu'une partie de votre logique de sortie se trouve dans votre sortie des tableaux. Parce qu'un tableau vide ne retourne qu'un tableau vide.
LiefdeWen
@LiefdeWen - Si j'ai bien compris, cet interpréteur faisant référence à System.Linq, je n'ai pas à l'inclure dans le nombre d'octets. Ma soumission serait considérée comme une langue différente de celle dite .NET Core. github.com/dotnet/roslyn/wiki/C%23-Interactive-Walkthrough - Vous parlez de l’impression qui est un problème distinct, je voudrais obtenir des précisions sur cette première étape .
Dana
En ce qui concerne l’impression, voici une version qui enregistre le résultat dans la console - tio.run/##XY29CsIwGEX3PEXGBGKhtVt/… - pas aussi jolie à coup sûr! La question que j'est quand est - il acceptable d'utiliser Arrayvs IListvs IEnumerable.
Dana
2

F # (Mono) , 45 octets

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

Essayez-le en ligne!

Je ne suis pas tout à fait sûr que cela soit valable, mais il semble que cela respecte la même syntaxe de "lambda anonyme" que celle que j'ai apparemment utilisée dans plusieurs autres langues.

Dana
la source
2

Java 8+ , 86 77 octets

-9 octets grâce à Kevin Cruijssen (se débarrasser de l'importation)!

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

Essayez-le en ligne!

Alternative, 65 octets

Les personnes suivantes imprimeront les résultats sur la sortie standard (à cause d’ Olivier Grégoire ):

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

Essayez-le en ligne

ბიმო
la source
Vous pouvez y attribuer 77 octets en utilisant simplement java.util.stream.IntStreamdirectement et abandonner l'importation.
Kevin Cruijssen
@ KevinCruijssen: Oh merci! Je ne savais même pas que c'était possible, c'est certainement utile (du moins pour le golf).
ბიმო
x->{for(int i=0;i<=x.size();)System.out.println(x.subList(0,i++));}( 67 octets ). Cela imprime au lieu d'utiliser des flux. L'impression est généralement le moyen le plus rapide de générer des structures complexes.
Olivier Grégoire
@ OlivierGrégoire: Dans ce cas, vous pouvez probablement vous en tirer System.out.printpuisque la sortie est toujours non ambiguë.
ბიმო
@BMO En effet, ce serait possible!
Olivier Grégoire
2

Brachylog , 9 octets

a₀ᶠ~b.hĖ∧

Essayez-le en ligne!

Explication

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)
Fataliser
la source
2

Ruby , 31 29 octets

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

Essayez-le en ligne!

Explication:

->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
la source