Tri basé sur l'indentation

35

Avec une liste ordonnée de chaînes de lettres de même casse (az XOR AZ) où chaque chaîne est précédée de 0 ou plusieurs caractères space (), affiche la même liste mais avec les chaînes triées à chaque niveau d'indentation. Les profondeurs d'indentation sous différents parents sont considérées comme des listes distinctes à des fins de tri.

Exemple

Si votre contribution est:

bdellium
  fox
  hound
  alien
aisle
  wasabi
    elf
    alien
  horseradish
    xeno
irk
wren
tsunami
djinn
      zebra

votre sortie devrait être

aisle
  horseradish
    xeno
  wasabi
    alien
    elf
bdellium
  alien
  fox
  hound
djinn
      zebra
irk
tsunami
wren

Si vous le souhaitez, considérez-le comme une liste de répertoires et vous devez trier les noms dans chaque répertoire.

Menus détails

  • Un élément peut être mis en retrait par un nombre quelconque d'espaces. S'il est mis en retrait par le même nombre d'espaces que l'élément précédent, il appartient à la même hiérarchie de tri que l'élément précédent. S'il est mis en retrait par plus d'espaces, c'est le début d'une nouvelle sous-hiérarchie.
  • Si une ligne est mise en retrait par moins d’ espaces que la ligne située au-dessus, elle est reliée au sous-groupe le plus proche situé au-dessus d’elle avec le même # ou moins d’espaces devant elle (comme le raifort dans l’exemple ci-dessus, qui est relié au groupe wasabi situé au-dessus d’elle, car le wasabi est le premier article au-dessus à ne pas avoir plus d’espace que le raifort)
  • Vous devez conserver le niveau d'indentation de chaque élément d'entrée dans votre sortie.
  • Les onglets dans la sortie sont interdits
  • La première ligne de l'entrée ne sera jamais mise en retrait
  • Votre programme doit gérer au moins une chaîne parmi les chaînes toutes majuscules et minuscules; il n'a pas à gérer les deux.

Notation

C'est un , donc la réponse qui utilise le moins d'octets gagne.

Techrocket9
la source
7
Beau défi!
Adám
1
Pour la prochaine fois, pensez à utiliser le bac à sable pour régler les problèmes avant de le publier sur le site principal.
Adám
8
@ Adám Non, la logique d'analyse récursive de chaînes requise est la raison pour laquelle j'ai écrit cette invite.
Techrocket9
2
Si l'entrée est ['a','..b', '.c', '..d'], quelle devrait être la sortie? ['a','..b', '.c', '..d']ou ['a','.c','..b', '..d']ou quelque chose d'autre? (J'utilise '.'au lieu de l'espace pour la clarté visuelle).
Chas Brown
2
@streetster strings (az XOR AZ)
mercredi

Réponses:

14

Python 2 , 117 octets

lambda S:[s[-1]for s in sorted(reduce(lambda t,s:t+[[v for v in t[-1]if v.count(' ')<s.count(' ')]+[s]],S,[[]]))[1:]]

Essayez-le en ligne!

Prend en entrée une liste de chaînes; et génère une liste de chaînes, triées selon les besoins.

L'idée est de transformer chaque élément en une liste contenant le "chemin absolu" sous forme de liste; puis laissez Python gérer le tri. Par exemple, si l'entrée est:

[
 'a',
 ' c',
 '  d',
 ' b'
]

Ensuite, via reduce(), nous convertissons en une liste de listes:

[
 ['a'],
 ['a',' c'],
 ['a',' c', '  d'],
 ['a',' b']
]

qui est trié comme:

[
 ['a'],
 ['a',' b']
 ['a',' c'],
 ['a',' c', '  d'],
]

puis affichez le dernier élément de chaque liste dans la liste de listes pour obtenir:

[
 'a',
 ' b'
 ' c',
 '  d',
]
Chas Brown
la source
Wow, la solution que je m'apprêtais à poster était de 183 octets ... Je suce lol
Don Thousand
4
@Rushabh Mehta: Mon premier essai a été d'environ 205 octets ... puis piratez-vous! :)
Chas Brown
7

APL (Dyalog Unicode) , 31 octets SBCS sur

Le préfixe anonyme lambda, prend et retourne la liste des chaînes.

{⍵[⍋{1=≢⍵:⍺⋄⍵}⍀↑' '(,⊂⍨⊣=,)¨⍵]}

Essayez-le en ligne!

{} "Dfn";est l'argument

⍵[]  Indexez l'argument avec les index suivants:

  ' '()¨⍵  Applique la fonction tacite suivante à chaque chaîne avec un espace comme argument de gauche:

   , concaténer l'espace à la chaîne

   ⊣= Liste booléenne indiquant où l'espace est égal à chaque caractère qui

   ,⊂⍨ utiliser cela pour partitionner (commencer partie où true) la concaténation d'espace et de chaîne

   mélanger la liste des chaînes de caractères dans la matrice de chaînes

  {}⍀ Réduction verticale cumulative par ce "dfn"; et sont les arguments supérieur et inférieur:

   ≢⍵ la longueur de la ficelle inférieure

   1= est-ce égal à 1? (c.-à-d. n'y a-t-il que l'espace unique?)

   :⍺ si c'est le cas, retourne l'argument supérieur

   ⋄⍵ sinon, retourne l'argument inférieur

   améliorer le niveau (trouver des indices qui vont trier cela)

Adam
la source
7

Retina , 47 octets

+-1m`(?<=^\2(\S+).*?¶( *)) 
$1 
O$`
$L$&
\S+ 
 

Essayez-le en ligne! Remarque: plusieurs lignes comportent des espaces de fin. Explication:

+-1m`(?<=^\2(\S+).*?¶( *)) 
$1 

La première étape consiste à insérer chaque mot dans les lignes suivantes à la même indentation. Par exemple, avec les lignes aisle, wasabiet elfles lignes résultantes sont aisle,aisle wasabi et aisle wasabi elf. J'ai découvert cette expression régulière par essais et erreurs, de sorte qu'il peut y avoir des cas extrêmes.

O$`
$L$&

Nous pouvons maintenant trier les lignes sans distinction de casse.

\S+ 
 

Supprimer tous les mots insérés.

Neil
la source
4

Perl 6 , 120 83 81 63 54 37 47 42 octets

-5 octets grâce à nwellnhof

{my@a;.sort:{@a[+.comb(' ')..*+1]=$_;~@a}}

Essayez-le en ligne!

Cette utilise la méthode de Chas Brown . Un bloc de code anonyme qui prend une liste de lignes et renvoie une liste de lignes.

Explication:

{                                        }  # Anonymous code block
 my@a;  # Declare a local list
      .sort # Sort the given list of lines
           :{                           }  # By converting each line to:
             @a[+.comb(' ')..*+1]=$_;      # Set the element at that indentation level onwards to that line
                                     ~@a   # And return the list coerced to a string
Jo King
la source
@nwellnhof Merci de l'avoir signalé. Je pense l'avoir corrigée dans la dernière version
Jo King
@nwellnhof Ah bien, c'était plus court lors d'une précédente itération. Merci pour les octets, mais je devais le changer légèrement
Jo King
Oh, c'est vrai. En réalité, quelque chose comme {my@a;.sort:{@a[+.comb(' ')...*>@a]=$_;~@a}}est nécessaire pour prendre en charge des niveaux d'indentation plus élevés.
nwellnhof
3

Propre , 112 101 octets

import StdEnv
f=flatten
?e=[0\\' '<-e]
$[h:t]#(a,b)=span(\u= ?u> ?h)t
=sort[[h:f($a)]: $b]
$e=[]

f o$

Essayez-le en ligne!

Fonction anonyme :: [[Char]] -> [[Char]]qui enveloppe $ :: [[Char]] -> [[[Char]]]le bon format de sortie. $regroupe les chaînes dans "plus d'espaces que" et "tout le reste après", revient sur chaque groupe et trie les éléments adjacents. A chaque étape, la liste en cours de tri se présente comme suit:

[[head-of-group-1,child-1,child-2..],[head-of-group-2,child-1,child-2..]..]

Propre , 127 octets

import StdEnv
$l=[x++y\\z<- ?(map(span((>)'!'))l),(x,y)<-z]
?[h:t]#(a,b)=span(\(u,_)=u>fst h)t
=sort[[h:flatten(?a)]: ?b]
?e=[]

Essayez-le en ligne!

Définit la fonction $ :: [[Char]] -> [[Char]]qui sépare les chaînes en tuples sous la forme (spaces, letters)qui sont triées de manière récursive par la fonction d'assistance ? :: [([Char],[Char])] -> [[([Char],[Char])]].

A expliqué:

$ list                                  // the function $ of the list
    = [                                 // is
        spaces ++ letters               // the spaces joined with the letters
        \\ sublist <- ? (               // from each sublist in the application of ? to
            map (                       // the application of
                span ((>)'!')           // a function separating spaces and letters
            ) list                      // to every element in the list
        )
        , (spaces, letters) <- sublist  // the spaces and letters from the sublist
    ]

? [head: tail]                              // in the function ? of the head and tail of the input
    # (group, others)                       // let the current group and the others equal
        = span (                            // the result of separating until ... is false
            \(u, _) = u >                   // only elements where there are more spaces
                          fst head          // than in the head of the input
        ) tail                              // the tail of the input
    = sort [
        [head                               // prepend the head of the input to
             : flatten (?group)             // the flat application of ? to the first group
                               ]            // and prepend this to
                                : ?others   // the application of ? to the other group(s)
    ]

? empty = [] // match the empty list
Οurous
la source
1

JavaScript (Node.js) , 114 100 92 88 octets

x=>x.map(y=>a=a.split(/ */.exec(y)[0]||a)[0]+y,a="_").sort().map(x=>/ *\w+$/.exec(x)[0])

Essayez-le en ligne!

Approche similaire à la réponse Python de Chas Brown, mais utilisant plutôt des expressions régulières.

Explication

x => x.map(                         // 
 y => a = a.split(                  // Renders the indentation paths
  / */.exec(y)[0]                   //  Checks the indentation level
  || a                              //  If this is the top level, go to root
 )[0] + y,                          //  Appends the child to the parent
 a = "_"                            // At first the cursor is at the root
)                                   // 
.sort()                             // Sorts the indentation paths
.map(                               // 
 x => / *\w+$/.exec(x)[0]           // Extracts only the last level of the path
)                                   //
Shieru Asakoto
la source
0

K4 , 51 octets

Solution:

{,/(1#'r),'.z.s@'1_'r:(w_x)@<x@w:&s=&/s:+/'" "=/:x}

Exemple:

q)k){,/(1#'r),'.z.s@'1_'r:(w_x)@<x@w:&s=&/s:+/'" "=/:x}("bdellium";"  fox";"  hound";"  alien";"aisle";"  wasabi";"    elf";"    alien";"  horseradish";"    xeno";"irk";"wren";"tsunami";"djinn";"      zebra")
"aisle"
"  horseradish"
"    xeno"
"  wasabi"
"    alien"
"    elf"
"bdellium"
"  alien"
"  fox"
"  hound"
"djinn"
"      zebra"
"irk"
"tsunami"
"wren"

Hypothèses:

une. Que chaque hiérarchie commence par le niveau le plus bas, c'est-à-dire que vous n'obtiendrez pas:

bdellium
      fox
    hound
    alien

Explication:

{,/(1#'r),'.z.s@'1_'r:(w_x)@<x@w:&s=&/s:+/'" "=/:x} / the solution
{                                                 } / lambda function, implicit x
                                           " "=/:x  / " " equal to each right (/:) x
                                        +/'         / sum up each
                                      s:            / save as s
                                    &/              / find the minimum (ie highest level)
                                  s=                / is s equal to the minimum?
                                 &                  / indices where true 
                               w:                   / save as w
                             x@                     / index into x at these indices
                            <                       / return indices to sort ascending
                           @                        / index into
                      (   )                         / do this together
                       w_x                          / cut x at indices w
                    r:                              / save as r
                 1_'                                / drop first from each r
            .z.s@                                   / apply recurse (.z.s)
          ,'                                        / join each both
    (    )                                          / do this together
     1#'r                                           / take first from each r
  ,/                                                / flatten
streetster
la source
0

Perl 5, 166 octets

sub f{my$p=shift;my@r;while(@i){$i[0]=~/\S/;$c=$-[0];if($p<$c){$r[-1].=$_ for f($c)}elsif($p>$c){last}else{push@r,shift@i}}sort@r}push@i,$_ while<>;print sort@{[f 0]}

Ungolfed (en quelque sorte):

sub f {
    my $p = shift;
    my @r;
    while(@i) {
        $i[0] =~ /\S/;
        $c = $-[0];
        if($p < $c) {
            $r[-1] .= $_ for f($c)
        } elsif ($p > $c) {
            last
        } else {
            push @r, shift @i
        }
    }
    sort @r
}

push @i, $_ while <>;
print sort@{[f 0]}

C'est une implémentation assez simple et récursive. Nous vérifions le niveau d'indentation en recherchant le premier caractère non espace ( /\S/) et en obtenant son index ( $-[0]). Malheureusement, nous devons en fait déclarer une poignée de variables utilisées dans la récursion, sinon elles seront implicitement globales et la récursivité ne fonctionnera pas correctement.

Silvio Mayolo
la source