_{Remarque: il s’agit du numéro 2 d’une série de défis liés à la manipulation de tableaux . Pour le défi précédent, cliquez ici .}

Séparation des listes imbriquées

Pour séparer les valeurs d'une liste imbriquée, aplatissez-la, puis affichez chaque valeur de manière à ce qu'elle se trouve à la même profondeur imbriquée qu'auparavant.

C'est-à-dire cette liste:

[1, [2, 3], [4, 4, [5, 2], 1]]

Deviendrait:

[1, [2], [3], [4], [4], [[5]], [[2]], [1]]

Le défi

Votre tâche consiste à écrire un programme qui prend toute liste imbriquée d’entiers positifs (dans les limites de votre langue) et effectue cette opération de séparation.

Vous pouvez soumettre une fonction prenant la liste en argument, ou un programme complet effectuant des E / S.

Comme il s'agit de code-golf , la soumission la plus courte (en octets) gagne! *

_{* Les trous de golf standard sont interdits. Vous connaissez le refrain.}

Cas de test

Les listes d’entrée ne contiendront jamais que des entiers de la taille d’entier standard de votre langue. Pour éviter les contraintes linguistiques empêchant leur concurrence, les valeurs ne seront pas imbriquées à des profondeurs supérieures à 10.

Vous pouvez supposer que l'entrée n'aura pas de sous-listes vides: par exemple - [[5, []]]ne sera pas donnée. Cependant, la liste principale pourrait être vide.

[]            ->  []

[[1, 2]]      ->  [[1], [2]]
[3, [4, 5]]   ->  [3, [4], [5]]
[3, [3, [3]]] ->  [3, [3], [[3]]]
[[6, [[7]]]]  ->  [[6], [[[7]]]]
[[5, 10], 11] ->  [[5], [10], 11]

N'hésitez pas à laisser un commentaire si j'ai raté une affaire de coin.

Exemple

J'ai jeté ensemble une solution Python 3 rapide (ungolfed) comme un exemple - vous pouvez le tester sur repl.it .

Brachylog , 16 octets

:{##:0&:ga|g}ac|

Essayez-le en ligne!

Explication

Example input: [1:[2:3]]

:{          }a     Apply the predicate below to each element of the list: [[1]:[[2]:[3]]]
              c    Concatenate: Output = [1:[2]:[3]]
               |   Or: Input = Output = []

  ##                 Input is a list: e.g. Input = [2:3]
    :0&              Call recursively the main predicate with this input: [2:3]
       :ga           Group each element in a list: Output = [[2]:[3]]
          |          Or (not a list): e.g. Input = 1
           g         Group into a list: Output = [1]

Mathematica, 24 21 octets

##&@@List/@#0/@#&/@#&

ou l'un de ceux-ci:

##&@@List/@#&/@#0/@#&
##&@@List@*#0/@#&/@#&
##&@@List/@#&@*#0/@#&

Explication

La raison pour laquelle il est si court est qu’il s’agit d’une récursion ne nécessitant pas de scénario de base explicite.

Il y a beaucoup de sucre syntaxique ici, commençons donc par dé-golfer. &indique une fonction non nommée à gauche de celle-ci, dont l'argument est écrit ainsi #. À l'intérieur de cette fonction, il est #0fait référence à la fonction elle-même, qui permet d'écrire des fonctions récursives sans nom. Mais commençons par donner un nom à la fonction interne et le retirer:

f[x_] := ##& @@ List /@ f /@ x
f /@ # &

L'autre sucre syntaxique important f/@xest l'abréviation de Map[f, x]c.- à- d. Qu'il fait appel fà chaque élément de x. La raison f[x_] := ... f /@ xqui ne mène pas à une récursion infinie est que le fait de mapper quelque chose sur un atome laisse cet atome inchangé sans appeler réellement la fonction. Par conséquent, il n'est pas nécessaire de vérifier explicitement le cas de base (l'élément en cours est un entier).

Donc, la fonction frevient d'abord à la liste la plus profonde à l'intérieur x, à quel point f/@devient un no-op. Ensuite, nous appelons utilisation ##& @@ List /@à ce sujet. La cartographie Listsur la liste chaque élément consiste simplement à insérer dans une liste séparée, donc {1, 2, 3}devient {{1}, {2}, {3}}. Ensuite, nous y appliquons la règle ##& , c'est-à-dire que la tête (c'est-à-dire la liste externe) est remplacée par ##&, ainsi cela devient ##&[{1}, {2}, {3}]. Mais ##&renvoie simplement ses arguments en tant que Sequence(ce que vous pouvez considérer comme une liste non enveloppée ou une sorte d’opérateur "splat" dans d’autres langues).

Ainsi se ##& @@ List /@transforme une liste {1, 2, 3}en {1}, {2}, {3}(en quelque sorte, cette dernière chose est réellement enveloppée dans la tête Sequence, mais elle disparaît dès que nous utilisons la valeur n'importe où).

Cela laisse la question de savoir pourquoi felle-même n'est pas déjà la solution au problème. Le problème est que la liste la plus externe doit être traitée différemment. Si nous avons des suggestions, {{1, 2}, {3, 4}}nous voulons {{1}, {2}, {3}, {4}}et non {{1}}, {{2}}, {{3}}, {{4}} . Ma solution initiale corrigeait cela en transmettant le résultat final sous forme de liste d'arguments permettant de Joinrestaurer le niveau externe de listes, mais celui-ci ignorait simplement le niveau externe en s'utilisant f lui-même dans une carte sur la sortie. Par conséquent, fs’applique uniquement aux éléments individuels de la liste la plus externe et n’arrive jamais à toucher cette liste.

Quant aux trois autres solutions, la première applique simplement la récursion en dehors de flaquelle fonctionne tout aussi bien. Les deux autres solutions évitent une Mapopération répétée en composant d’abord deux fonctions, puis en mappant le résultat une seule fois.

J , 19 18 octets

(<@]/@,~>)S:0 1{::

Il s'agit d'un verbe anonyme qui prend et renvoie des tableaux encadrés, qui sont la version de J (plutôt lourde) des tableaux imbriqués. Le voir passer tous les cas de test.

Explication

Ceci utilise les opérations quelque peu exotiques {::( map ) et S:( spread ), qui opèrent sur des tableaux en boîte. {::remplace chaque feuille par le chemin encadré vers cette feuille. S:applique un verbe donné à une profondeur d'imbrication donnée, puis divise les résultats en un tableau.

(<@]/@,~>)S:0 1{::  Input is y.
(        )          Let's look at this verb first.
        >           Open the right argument,
      ,~            append the left argument to it,
    /               then reduce by
 <@]                boxing. This puts the left argument into as many nested boxes
                    as the right argument is long.
                    This verb is applied to y
               {::  and its map
            0 1     at levels 0 and 1.
                    This means that each leaf of y is paired with its path,
                    whose length happens to be the nesting depth of y,
                    and the auxiliary verb is applied to them.
          S:        The results are spread into an array.

R, 199 octets

function(l){y=unlist(l);f=function(x,d=0){lapply(x,function(y){if(class(y)=='list'){f(y,d=d+1)}else{d}})};d=unlist(f(l));lapply(1:length(d),function(w){q=y[w];if(d[w]){for(i in 1:d[w])q=list(q)};q})}

Cette question était difficile. Les listes de R sont un peu bizarres et il n'est absolument pas simple de parcourir tous les éléments des sous-listes. Il n'est également pas simple de déterminer ensuite la profondeur de cette liste. Ensuite, le défi consiste à recréer la liste avec tous les éléments séparés. Nous avons donc besoin d'un moyen de créer de manière adaptative une liste d'une certaine profondeur.

La solution consiste en deux grandes parties. Une fonction récursive qui parcourt toutes les listes et enregistre la profondeur:

  f=function(x,d=0){
    lapply(x,function(y){
      if(class(y)=='list'){
        f(y,d=d+1)
      } else {
        d
      }})
  }

Lorsque nous avons unlist(l)stocké les profondeurs de chaque entrée du vecteur , dnous créons implicitement une liste lapplyet la remplissons avec la fonction suivante:

  lapply(1:length(d),function(w){
    q=y[w]
    if(d[w]){
      for(i in 1:d[w]){
        q=list(q)
      }
    }
    q
  })

Dans cet appel d'application, nous créons un objet qavec la valeur de l'entrée dans la liste, vérifions sa profondeur et voyons s'il est différent de zéro. S'il est égal à zéro, nous pouvons simplement le laisser sous forme de valeur numérique. S'il est différent de zéro, nous devons l'imbriquer dans ce nombre de listes. Nous appelons donc un dtemps de boucle for et appelons à plusieurs reprises q=list(q).

lapplypuis met toutes ces valeurs de qdans une liste, créant le résultat souhaité.

Programme complet avec un espacement correct et tel que:

function(our.list){
  values <- unlist(our.list)
  f <- function(part.list, depth = 0){
    lapply(part.list, function(y){
      if(class(y)=='list'){
        f(y, depth <- depth + 1)
      } else {
        return(depth)
      }})
  }
  depths <- unlist(f(our.list))
  new.list <- lapply(1:length(depths), function(w){
    q <- values[w]
    if(depths[w] != 0){
      for(i in 1:depths[w]){
        q <- list(q)
      }
    }
    return(q)
  })
  return(new.list)
}

Retina , 34 octets

+`(.(?>()\[|(?<-2>)]|.)+)\2,
$1],[

Essayez-le en ligne!

C (gcc), 147 octets

d=0,l,i;
P(n,c){for(;n--;)putchar(c);}
main(c){for(;~(c=getchar());l=i)i=isdigit(c),P((l<i)*d,91),P(i,c),P((l>i)*d,93),P(l>i,32),d+=(92-c)*(c>90);}

Exemple d'entrée:

1 [23 3] [40 4 [5 2] 1]

Exemple de sortie:

1 [23] [3] [40] [4] [[5]] [[2]] [1]

empilé , non compétitif, 25 octets

{e d:e$wrap d 1-*}cellmap

Cette fonction modifie le membre supérieur de la pile. Si vous voulez une fonction de bonne foi, il suffit d' ajouter [et ]au début et à la fin. Essayez-le ici!

Voici une version lisible:

{ arr :
  arr { ele depth :
    ele   $wrap depth 1- * (* execute wrap n times, according to the depth *)
  } cellmap (* apply to each cell, then collect the results in an array *)
} @:a2
(1 (2 3) (4 4 (5 2) 1)) a2 out

Cas de test:

(1 (2 3) (4 4 (5 2) 1))    (* arg on TOS *)
{e d:e$wrap d 1-*}cellmap
out                        (* display TOS *)

Sortie sans nouvelles lignes:

(1 (2) (3) (4) (4) ((5)) ((2)) (1))

PHP, 101 94 octets

sauvé 1 octet grâce à @Christoph, sauvé 6 autres inspirés par cela.

function s($a){foreach($a as$b)if($b[0])foreach(s($b)as$c)$r[]=[$c];else$r[]=$b;return$r?:[];}

fonction récursive, assez simple

panne

function s($a)
{
    foreach($a as$b)                // loop through array
        if($b[0])                       // if element is array
            foreach(s($b)as$c)$r[]=[$c];    // append separated elements to result
        else$r[]=$b;                    // else append element to result
    return$r?:[];                   // return result, empty array for empty input
}

Python 2, 122 106 octets

Assez terrible score, juste une mise en œuvre simple.

Merci à @Zachary T pour avoir aidé à économiser 16 octets!

def x(l,a=[],d=0):
 n=lambda b:b and[n(b-1)]or l
 if'['in`l`:[x(e,a,d+1)for e in l];return a
 else:a+=n(d)

Appel xavec un argument à exécuter. Pour une raison quelconque, il ne peut être exécuté qu'une seule fois.

JavaScript (Firefox 30-57), 53 octets

f=a=>[for(e of a)for(d of e.map?f(e):[e])e.map?[d]:d]

La meilleure réponse ES6 que j'ai à ce jour est de 76 octets:

f=(a,r=[],d=0)=>a.map(e=>e.map?f(e,r,d+1):r.push((n=d=>d?[n(d-1)]:e)(d)))&&r

Pyth - 29 octets

.b]FYt-F/LN`[)PsM._:`Q"\d"3.n

Suite de test .

Perl 6 , 60 47 octets

sub f{[$_~~List??|([$_] for .&f)!!$_ for |$^a]}

( Essayez-le en ligne. )

Explication:

1. [... for |$^a]: Parcourez le tableau en entrée et construisez un nouveau tableau à partir de celui-ci.
2. $_ ~~ List ?? ... !! ...: Pour chaque élément, vérifiez s'il s'agit d'un tableau.
3. |([$_] for .&f): Si l'élément est un tableau, appliquez-lui la fonction de manière récursive, parcourez les éléments du nouveau tableau renvoyé par cet appel récursif, placez chaque élément dans un tableau distinct et glissez-le dans la liste externe.
4. $_: Si l'élément n'est pas un tableau, transmettez-le tel quel.

Haskell, 71 octets

data L=N Int|C[L] 
d#C l=((C .pure.d)#)=<<l
d#n=[d n]
f(C l)=C$(id#)=<<l

Encore une fois, je dois définir mon propre type de liste, car les listes natives de Haskell ne peuvent pas être imbriquées de manière arbitraire. Ce nouveau type Lpeut être retourné à partir d'une fonction mais ne pas être imprimé par défaut, donc pour voir un résultat, je définis une showinstance pour L:

instance Show L where
  show (N n)=show n
  show (C l)=show l

Nous pouvons maintenant faire quelques tests dans le REPL:

*Main> f $ C[N 1, C[N 2, N 3], C[N 4, N 4, C[N 5, N 2], N 1]]
[1,[2],[3],[4],[4],[[5]],[[2]],[1]]

*Main> f $ C[C[N 6, C[C[N 7]]]]
[[6],[[[7]]]]

Comment ça marche: une récursivité simple qui passe le niveau d'imbrication en fonction des Cconstructeurs. Nous commençons avec la fonction d'identité idet chaque fois qu'il y a une liste (-> correspondance de modèle d#C l=), nous ajoutons une couche supplémentaire de C(-> C .pure.d) à l'appel récursif de #tous les éléments de la liste. Si nous rencontrons un nombre, nous appliquons simplement la fonction dde niveau d'imbrication au nombre.

APL (Dyalog) , 44 octets *

Fonction de préfixe tacite anonyme. Prend la liste APL imbriquée en argument et renvoie un tableau APL imbriqué.

∊{⊃⊂⍣⍵,⍺}¨{⊃¨(j∊⎕D)⊆+\-⌿'[]'∘.=j←⎕JSON⍵}

Essayez-le en ligne!

{… } Applique la fonction explicite suivante où l'argument est représenté par ⍵:

 ⎕JSON⍵ convertir l'argument en JSON

 j← stocker dans j

 '[]'∘.= tableau où les jéquivalents ouvrent (rangée supérieure) et se ferment (rangée inférieure)

 -⌿ rangée supérieure moins rangée inférieure (réduction de la différence verticale)

 +\ somme cumulative (cela donne le niveau d'imbrication pour chaque caractère)

 (… )⊆ Partition, en commençant une nouvelle partition chaque fois qu'un 1 n'est pas précédé d'un 1 dans…

  j∊⎕D où chaque personnage de jest membre de l'ensemble de D igits

 ⊃¨ choisissez le premier de chaque (cela donne le niveau d'imbrication par nombre à plusieurs chiffres)

∊{... }¨ applique la fonction suivante pour chaque niveau d' imbrication ( ⍵), en utilisant l'élément correspondant de l' ε argumentation nlisted (aplatie) comme argument de gauche ( ⍺):

 ,⍺ défiler (lister) le nombre (parce que les scalaires ne peuvent pas être inclus)

 ⊂⍣⍵ clôturer les ⍵temps

 ⊃ divulguer (car la liste la plus interne est elle-même une pièce jointe)

^{* Utilisation de Dyalog Classic avec ⎕ML←3(par défaut sur de nombreux systèmes), en remplacement ⊂de ⊆et ↑pour ⊃. Tio!}