Sortir berbasis indentasi

35

Diberikan daftar terurut dari string huruf yang sama (az XOR AZ) di mana setiap string didahului oleh 0 karakter spasi atau lebih, mengeluarkan daftar yang sama tetapi dengan string yang diurutkan pada setiap tingkat indentasi. Kedalaman indentasi di bawah orang tua yang berbeda dihitung sebagai daftar yang berbeda untuk keperluan penyortiran.

Contoh

Jika input Anda adalah:

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

output Anda seharusnya

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

Jika Anda suka, anggap itu seperti daftar direktori, dan Anda perlu mengurutkan nama-nama dalam setiap direktori.

Detel

  • Item dapat diindentasi oleh sejumlah spasi. Jika diindentasi dengan jumlah spasi yang sama dengan item sebelumnya, item tersebut termasuk dalam hierarki sortir yang sama dengan item sebelumnya. Jika diindentasi oleh lebih banyak ruang, ini adalah awal dari sub-hierarki baru.
  • Jika sebuah garis diindentasi oleh lebih sedikit spasi daripada garis di atasnya, ia menghubungkan ke sub grup terdekat di atasnya dengan # yang sama atau lebih sedikit spasi sebelumnya (seperti lobak pada contoh di atas, yang menghubungkan ke grup wasabi di atasnya karena wasabi adalah item pertama di atasnya yang tidak memiliki lebih banyak ruang daripada lobak)
  • Anda harus menjaga level indentasi setiap item input dalam output Anda
  • Tab pada output tidak diizinkan
  • Baris pertama dari input tidak akan pernah diindentasi
  • Program Anda harus menangani setidaknya satu string semua huruf besar dan huruf kecil semua; tidak harus menangani keduanya.

Mencetak gol

Ini adalah , jadi jawaban yang menggunakan byte paling sedikit menang.

Techrocket9
sumber
7
Tantangan yang bagus!
Adám
1
Btw, untuk waktu berikutnya, pertimbangkan untuk menggunakan Sandbox untuk menyelesaikan masalah dengan tantangan sebelum mempostingnya ke situs utama.
Adám
8
@ Adám Tidak, logika parsing string rekursif yang diperlukan adalah alasan saya menulis prompt ini.
Techrocket9
2
Jika inputnya ['a','..b', '.c', '..d'], apa yang seharusnya menjadi output? ['a','..b', '.c', '..d']atau ['a','.c','..b', '..d']atau hal lain? (Saya menggunakan '.'bukannya ruang untuk kejelasan visual).
Chas Brown
2
@streetster string (az XOR AZ)
Adám

Jawaban:

14

Python 2 , 117 byte

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

Cobalah online!

Dibawa sebagai input daftar string; dan menampilkan daftar string, diurutkan sesuai kebutuhan.

Idenya adalah untuk mengubah setiap elemen menjadi daftar yang berisi "jalur absolut" sebagai daftar; dan kemudian biarkan Python menangani penyortiran. Misal jika inputnya adalah:

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

Kemudian melalui reduce(), kami mengonversi ke daftar daftar:

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

yang akan diurutkan sebagai:

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

dan kemudian menampilkan elemen terakhir dari setiap daftar di daftar-daftar untuk mendapatkan:

[
 'a',
 ' b'
 ' c',
 '  d',
]
Chas Brown
sumber
Wow solusi yang akan saya posting adalah 183 byte ... Saya payah lol
Don Thousand
4
@Rushabh Mehta: Percobaan pertama saya adalah sekitar 205 byte ... lalu retas! :)
Chas Brown
7

APL (Dyalog Unicode) , 31 byte SBCS

Lambda awalan anonim, mengambil dan mengembalikan daftar string.

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

Cobalah online!

{... } "dfn"; adalah argumen

⍵[... ] indeks argumen dengan indeks berikut:

  ' '(... )¨⍵ terapkan fungsi tacit berikut untuk setiap string dengan spasi sebagai argumen kiri:

   , menyatukan ruang ke string

   ⊣= Daftar Boolean menunjukkan di mana ruang sama dengan setiap karakter itu

   ,⊂⍨ menggunakannya untuk mempartisi (mulai bagian yang benar) gabungan ruang dan string

   mencampur daftar daftar string ke dalam matriks string

  {... }⍀ reduksi kumulatif vertikal dengan "dfn" ini; dan args atas dan bawah:

   ≢⍵ panjang senar bawah

   1= apakah itu sama dengan 1? (yaitu apakah tidak ada satu pun ruang di sana?)

   :⍺ jika demikian, kembalikan argumen atas

   ⋄⍵ selain itu, kembalikan argumen yang lebih rendah

   naik kelas (cari indeks yang akan mengurutkannya)

Adm
sumber
7

Retina , 47 byte

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

Cobalah online! Catatan: Beberapa garis memiliki spasi tambahan. Penjelasan:

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

Langkah pertama adalah menyisipkan setiap kata ke dalam baris berikut dengan lekukan yang sama. Misalnya, dengan garis aisle, wasabidan elfgaris yang dihasilkan adalah aisle, aisle wasabidan aisle wasabi elf. Saya menemukan regex ini dengan coba-coba sehingga mungkin ada kasus tepi dengan itu.

O$`
$L$&

Kita sekarang dapat mengurutkan garis case-insensitive.

\S+ 
 

Hapus semua kata yang dimasukkan.

Neil
sumber
4

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

-5 byte berkat nwellnhof

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

Cobalah online!

Ini menggunakan metode Chas Brown . Blok kode anonim yang mengambil daftar garis dan mengembalikan daftar garis.

Penjelasan:

{                                        }  # 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
sumber
@nwellnhof Terima kasih telah menunjukkan itu. Saya pikir saya sudah memperbaikinya dalam versi terbaru
Jo King
@nwellnhof Ah well, itu lebih pendek dalam iterasi sebelumnya. Terima kasih atas byte yang mati, tetapi saya harus mengubahnya sedikit
Jo King
Oh benar Sebenarnya, sesuatu seperti {my@a;.sort:{@a[+.comb(' ')...*>@a]=$_;~@a}}diperlukan untuk mendukung tingkat indentasi yang lebih tinggi.
nwellnhof
3

Bersih , 112 101 byte

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

f o$

Cobalah online!

Fungsi anonim :: [[Char]] -> [[Char]]yang terbungkus $ :: [[Char]] -> [[[Char]]]dalam format output yang tepat. $mengelompokkan string menjadi "lebih banyak ruang daripada" dan "segala sesuatu yang lain sesudahnya", berulang di setiap grup dan mengurutkannya ketika disatukan. Pada setiap langkah, daftar yang diurutkan terlihat seperti:

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

Bersihkan , 127 byte

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

Cobalah online!

Menentukan fungsi $ :: [[Char]] -> [[Char]]yang memisahkan string menjadi tupel dalam bentuk (spaces, letters)yang secara rekursif disortir oleh fungsi helper ? :: [([Char],[Char])] -> [[([Char],[Char])]].

Dijelaskan:

$ 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
Suram
sumber
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])

Cobalah online!

Pendekatan yang mirip dengan jawaban Python Chas Brown, tetapi menggunakan ekspresi reguler sebagai gantinya.

Penjelasan

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

K4 , 51 byte

Larutan:

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

Contoh:

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"

Asumsi:

Sebuah. Bahwa setiap hierarki akan mulai dengan level terendah, yaitu Anda tidak akan mendapatkan:

bdellium
      fox
    hound
    alien

Penjelasan:

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

Perl 5, 166 byte

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

Tidak disatukan (semacam):

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

Ini implementasi rekursif yang cukup mudah. Kami memeriksa level indentasi dengan mencari karakter non-spasi pertama ( /\S/) dan mendapatkan indeksnya ( $-[0]). Sayangnya, kami benar-benar harus mendeklarasikan beberapa variabel yang digunakan dalam rekursi, atau mereka akan secara global dan rekursi tidak akan berfungsi dengan benar.

Silvio Mayolo
sumber