Un tableau de défis n ° 2: séparer un tableau imbriqué

36

Remarque: il s’agit du numéro 2 d’une série de défis liés à la de . 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 , 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 .

FlipTack
la source
Ajoutez un cas de test avec des nombres supérieurs à un chiffre pour les réponses basées sur des chaînes.
Orlp
@ orlp bonne idée.
FlipTack
2
Peut-on supposer une certaine profondeur maximale? Dis, 16 ans?
Orlp
@ orlp Je vais dire oui, la profondeur imbriquée maximale sera de 10, car je suis plus intéressé par l'exécution de votre algorithme et de votre méthode que par les contraintes de votre langage. Mettra à jour le fil maintenant.
FlipTack
Puis-je sortir en tant que chaîne?
Rohan Jhunjhunwala

Réponses:

4

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]
Fataliser
la source
Que fait l' Zargument sur TIO? Sans cela, cela semble sortir avec true / false, ce qui donne l'impression que Zc'est nécessaire dans le nombre d'octets.
FlipTack
@FlipTack Zindique à Brachylog que l'argument de sortie est une variable. C'est cette variable qui est unifiée avec la sortie résultante. Lorsque vous le supprimez, il indique à Brachylog que la sortie est une variable anonyme et indique à la place si le prédicat principal réussit ou échoue. C'est la même chose que dans Prolog où le résultat est "mis" dans une variable.
Fataliser
Ok :) bonne réponse!
FlipTack
19

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.

Martin Ender
la source
8

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.
Zgarb
la source
3

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)
}
JAD
la source
Sympa, c'est la méthode que j'ai utilisée avec ma première solution Python pour les cas de test :)
FlipTack
is.list(y)au lieu de class(y)=='list'? ne peut pas vérifier que cela fonctionnera réellement.
Giuseppe
180 octets
Giuseppe
3

Retina , 34 octets

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

Essayez-le en ligne!

Martin Ender
la source
Comment ça (?<-2>)marche?
Kritixi Lithos
@KritixiLithos C'est un groupe en équilibre . Cela ressort de la pile de capture 2, ce qui me permet de garder une trace de la profondeur d'imbrication actuelle.
Martin Ender
2

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]
orlp
la source
2

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))
Conor O'Brien
la source
Est-ce *que l'argument comme un bloc de code?
Downgoat
@Downgoat dans ce cas, il enveloppe les d-1temps d' argument . $funcest une fonction qui peut être manipulée.
Conor O'Brien
2

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
}
Titus
la source
Où le résultat est-il initialisé?
Neil
@Neil: PHP ne nécessite pas d'initialisation explicite. Obtient des $réléments dans la boucle ou la fonction renvoie un tableau vide. Cela peut donner des avis, mais ceux-ci ne sont pas imprimés avec la configuration par défaut.
Titus
Cela ne signifie-t-il pas que vous ne pourrez l'appeler qu'une fois?
Neil
1
Vous pourriez aussi bien devenir fou: !cos(). cos()renvoie nullpour chaque tableau et un float! = 0 pour chaque entier positif. Je veux dire ... qui se soucie des avertissements?
Christoph
1
@Christoph: les avertissements sont imprimés, pas les notifications (dans la configuration par défaut). Mais c’est une bonne idée! On is_int: Inverser la condition ne sauve rien; J'ai besoin d'un espace entre elseet foreach. MAIS: $b[0]pour un entier est NULL.
Titus
2

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.

Bleu
la source
Vous pouvez changer a+=[n(l,d)]en a+=n(l,d),(notez la virgule)
FlipTack
Avez-vous même besoin d'assigner à t?
Zacharý
Cela fonctionne-t-il lorsque vous l'appelez plus d'une fois?
Zacharý
Vous pouvez passer nà la fonction et supprimer le premier argument, car il le sera toujours l.
Zacharý
repl.it/EwPz
Zacharý
2

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
Neil
la source
2
Dans les deux blocs de code, je pense que vous avez omis le début f=.
Conor O'Brien
@ ConorO'Brien Encore une fois ...
Neil
1

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.
smls
la source
1

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.

nimi
la source
0

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!

Adam
la source