Einrückungsbasiertes Sortieren

35

Ausgehend von einer geordneten Liste von Buchstabenfolgen in Groß- und Kleinschreibung (az XOR AZ), vor denen jeder Zeichenfolge 0 oder mehr Leerzeichen () vorangestellt sind, geben Sie dieselbe Liste aus, wobei die Zeichenfolgen auf jeder Einrückungsstufe sortiert sind. Einrückungstiefen unter verschiedenen übergeordneten Elementen werden zu Sortierzwecken als separate Listen gezählt.

Beispiel

Wenn Ihre Eingabe lautet:

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

Ihre Ausgabe sollte sein

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

Wenn Sie möchten, stellen Sie es sich wie eine Verzeichnisliste vor, und Sie müssen die Namen in jedem Verzeichnis sortieren.

Minutiae

  • Ein Element kann durch eine beliebige Anzahl von Leerzeichen eingerückt werden. Wenn es mit derselben Anzahl von Leerzeichen eingerückt ist wie das vorherige Element, gehört es in dieselbe Sortierhierarchie wie das vorherige Element. Wenn es durch mehr Leerzeichen eingerückt wird, beginnt eine neue Unterhierarchie.
  • Wenn eine Zeile um weniger Leerzeichen eingerückt ist als die darüber liegende Zeile, wird eine Verknüpfung zur nächstgelegenen Untergruppe mit dem gleichen # oder weniger Leerzeichen davor hergestellt (wie im obigen Beispiel der Meerrettich, der auf die darüber liegende Wasabi-Gruppe verweist, weil Wasabi ist der erste Artikel darüber, der nicht mehr Leerzeichen als Meerrettich enthält.)
  • Sie müssen die Einrückungsstufe jedes Eingabeelements in Ihrer Ausgabe beibehalten
  • Tabulatoren in der Ausgabe sind nicht zulässig
  • Die erste Zeile der Eingabe wird niemals eingerückt
  • Ihr Programm muss mindestens eine Zeichenfolge aus Groß- und Kleinbuchstaben verarbeiten. es muss nicht beides bewältigen.

Wertung

Dies ist ein , also gewinnt die Antwort, die die wenigsten Bytes verwendet.

Techrocket9
quelle
7
Schöne Herausforderung!
Adám
1
Übrigens sollten Sie beim nächsten Mal in Betracht ziehen, die Sandbox zu verwenden, um Probleme mit einer Herausforderung auszubügeln, bevor Sie sie auf der Hauptseite veröffentlichen.
Adám
8
@ Adám Nein, die erforderliche rekursive String-Parsing-Logik ist der Grund, warum ich diese Eingabeaufforderung geschrieben habe.
Techrocket9
2
Wenn der Eingang ist ['a','..b', '.c', '..d'], was soll der Ausgang sein? ['a','..b', '.c', '..d']oder ['a','.c','..b', '..d']oder was anderes? (Ich benutze '.'anstelle von Raum für visuelle Klarheit).
Chas Brown
2
@streetster Zeichenfolgen (az XOR AZ)
Adám

Antworten:

14

Python 2 , 117 Bytes

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:]]

Probieren Sie es online!

Nimmt als Eingabe eine Liste von Zeichenketten; und gibt eine Liste von Strings aus, die nach Bedarf sortiert sind.

Die Idee ist, jedes Element in eine Liste zu verwandeln, die den "absoluten Pfad" als Liste enthält. und lassen Sie dann Python die Sortierung übernehmen. ZB wenn die Eingabe ist:

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

Dann reduce()konvertieren wir über die in eine Liste von Listen:

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

was sortiert wird als:

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

und dann das letzte Element jeder Liste in der Liste der Listen ausgeben, um Folgendes zu erhalten:

[
 'a',
 ' b'
 ' c',
 '  d',
]
Chas Brown
quelle
Wow, die Lösung, die ich veröffentlichen wollte, war 183 Bytes ... Ich lol saugen
Don Thousand
4
@ Rushabh Mehta: Mein erster Versuch war etwa 205 Bytes ... dann hack weg! :)
Chas Brown
7

APL (Dyalog Unicode) , 31 Byte SBCS

Anonymes Präfix Lambda, nimmt eine Liste von Zeichenfolgen auf und gibt sie zurück.

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

Probieren Sie es online!

{... } "dfn"; ist ein Argument

⍵[] Indexiere das Argument mit folgenden Indizes:

  ' '()¨⍵ Wende die folgende implizite Funktion auf jeden String mit Leerzeichen als linkem Argument an:

   , Verketten Sie das Leerzeichen mit der Zeichenfolge

   ⊣= Boolesche Liste, die angibt, wo das Leerzeichen für jedes Zeichen gleich ist

   ,⊂⍨ Verwenden Sie diese Option, um die Verkettung von Leerzeichen und Zeichenfolge zu partitionieren (wobei der Teil mit true beginnt)

   mischen Sie Liste von Listen von Zeichenfolgen in Matrix von Zeichenfolgen

  {}⍀ Vertikale kumulative Reduktion um dieses "dfn"; und sind obere und untere Argumente:

   ≢⍵ die Länge der unteren Zeichenfolge

   1= ist das gleich 1? (dh gibt es dort nichts als den einzelnen Raum?)

   :⍺ Wenn ja, geben Sie das obere Argument zurück

   ⋄⍵ Andernfalls geben Sie das untere Argument zurück

   grade up (finde Indizes, die das sortieren)

Adam
quelle
7

Netzhaut , 47 Bytes

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

Probieren Sie es online! Hinweis: Mehrere Zeilen haben nachgestellte Leerzeichen. Erläuterung:

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

Der erste Schritt besteht darin, jedes Wort in die folgenden Zeilen mit demselben Einzug einzufügen. Zum Beispiel mit den Linien aisle, wasabiund elfdie sich daraus ergebenden Linien sind aisle, aisle wasabiund aisle wasabi elf. Ich habe diesen regulären Ausdruck durch Ausprobieren entdeckt, daher kann es zu Randfällen kommen.

O$`
$L$&

Wir können die Zeilen jetzt unabhängig von Groß- und Kleinschreibung sortieren.

\S+ 
 

Löschen Sie alle eingefügten Wörter.

Neil
quelle
4

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

-5 bytes dank nwellnhof

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

Probieren Sie es online!

Dies verwendet die Methode von Chas Brown . Ein anonymer Codeblock, der eine Liste von Zeilen aufnimmt und eine Liste von Zeilen zurückgibt.

Erläuterung:

{                                        }  # 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
Scherzen
quelle
@nwellnhof Danke für den Hinweis. Ich glaube, ich habe es in der neuesten Version behoben
Jo King
@nwellnhof Ah ja, es war in einer vorherigen Iteration kürzer. Vielen Dank für die Bytes aus, aber ich musste es leicht ändern
Jo King
Oh, richtig. Tatsächlich ist so etwas {my@a;.sort:{@a[+.comb(' ')...*>@a]=$_;~@a}}erforderlich, um höhere Einrückungsstufen zu unterstützen.
Nwellnhof
3

Sauber , 112 101 Bytes

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

f o$

Probieren Sie es online!

Anonyme Funktion, :: [[Char]] -> [[Char]]die $ :: [[Char]] -> [[[Char]]]in das richtige Ausgabeformat übergeht. $gruppiert die Zeichenketten in "mehr Leerzeichen als" und "alles andere danach", rekursiert über jede Gruppe und sortiert sie, wenn sie benachbart sind. Bei jedem Schritt sieht die sortierte Liste folgendermaßen aus:

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

Sauber , 127 Bytes

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

Probieren Sie es online!

Definiert die Funktion, $ :: [[Char]] -> [[Char]]die die Zeichenfolgen in Tupel (spaces, letters)aufteilt, die von der Hilfsfunktion rekursiv sortiert werden ? :: [([Char],[Char])] -> [[([Char],[Char])]].

Erklärt:

$ 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
quelle
1

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

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

Probieren Sie es online!

Ähnliches Vorgehen wie bei Chas Browns Python-Antwort, jedoch mit regulären Ausdrücken.

Erläuterung

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
quelle
0

K4 , 51 Bytes

Lösung:

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

Beispiel:

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"

Annahmen:

ein. Dass jede Hierarchie mit der niedrigsten Ebene beginnt, dh Sie erhalten nicht:

bdellium
      fox
    hound
    alien

Erläuterung:

{,/(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
quelle
0

Perl 5, 166 Bytes

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 (Art):

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]}

Es ist eine ziemlich einfache rekursive Implementierung. Wir überprüfen die Einrückungsstufe, indem wir nach dem ersten Nicht-Leerzeichen ( /\S/) suchen und dessen Index ( $-[0]) abrufen . Leider müssen wir tatsächlich eine Handvoll Variablen deklarieren , die in der Rekursion verwendet werden, oder sie sind implizit global und die Rekursion funktioniert nicht richtig.

Silvio Mayolo
quelle