Ordenar basado en sangría

35

Dada una lista ordenada de cadenas de letras del mismo caso (az XOR AZ) donde cada cadena está precedida por 0 o más caracteres de espacio (), genera la misma lista pero con las cadenas ordenadas en cada nivel de sangría. Las profundidades de sangría bajo diferentes padres cuentan como listas distintas para fines de clasificación.

Ejemplo

Si su entrada es:

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

su salida debe ser

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

Si lo desea, piense en él como un listado de directorio, y necesita ordenar los nombres dentro de cada directorio.

Minucias

  • Un elemento puede estar sangrado por cualquier número de espacios. Si está sangrado por el mismo número de espacios que el elemento anterior, pertenece a la misma jerarquía de clasificación que el elemento anterior. Si está sangrado por más espacios, es el comienzo de una nueva sub-jerarquía.
  • Si una línea está sangrada por menos espacios que la línea que está sobre ella, se vincula al subgrupo más cercano sobre ella con el mismo # o menos espacios antes (como el rábano picante en el ejemplo anterior, que enlaza con el grupo wasabi sobre él porque wasabi es el primer elemento sobre él que no tiene más espacios que el rábano picante)
  • Debe conservar el nivel de sangría de cada elemento de entrada en su salida
  • Las pestañas en la salida no están permitidas
  • La primera línea de la entrada nunca se sangrará
  • Su programa debe manejar al menos una de las cadenas en mayúsculas y minúsculas; no tiene que manejar ambos.

Tanteo

Este es un , por lo que gana la respuesta que usa la menor cantidad de bytes.

Techrocket9
fuente
77
Buen desafío!
Adám
1
Por cierto, para la próxima vez, considere usar el Sandbox para resolver problemas con un desafío antes de publicarlo en el sitio principal.
Adám
8
@ Adám No, la lógica de análisis de cadena recursiva requerida es la razón por la que escribí este mensaje.
Techrocket9
2
Si la entrada es ['a','..b', '.c', '..d'], ¿cuál debería ser la salida? ['a','..b', '.c', '..d']o ['a','.c','..b', '..d']o alguna otra cosa? (Estoy usando en '.'lugar de espacio para claridad visual).
Chas Brown
2
@streetster strings (az XOR AZ)
Adám

Respuestas:

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

Try it online!

Takes as input a list of strings; and outputs a list of strings, sorted as required.

La idea es convertir cada elemento en una lista que contenga la "ruta absoluta" como una lista; y luego deje que Python maneje la clasificación. Por ejemplo, si la entrada es:

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

Luego, a través de reduce(), convertimos a una lista de listas:

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

que se ordena como:

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

y luego muestra el último elemento de cada lista en la lista de listas para obtener:

[
 'a',
 ' b'
 ' c',
 '  d',
]
Chas Brown
fuente
Wow the solution I was about to post was 183 bytes...I suck lol
Don Thousand
4
@Rushabh Mehta: My first try was around 205 bytes... then hack away! :)
Chas Brown
7

APL (Dyalog Unicode), 31 bytesSBCS

Anonymous prefix lambda, takes and returns list of strings.

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

Try it online!

{} "dfn"; is argument

⍵[] index the argument with the following indices:

  ' '()¨⍵ apply the following tacit function to each string with space as left argument:

   , concatenate the space to the string

   ⊣= Boolean list indicating where the space is equal to each character that

   ,⊂⍨ use that to partition (begin part where true) the concatenation of space and string

   mix list of lists of strings into matrix of strings

  {}⍀ vertical cumulative reduction by this "dfn"; and are upper and lower args:

   ≢⍵ the length of the lower string

   1= is that equal to 1? (i.e. is there nothing but the single space there?)

   :⍺ if so, return the upper argument

   ⋄⍵ else, return the lower argument

   grade up (find indices which will sort that)

Adám
fuente
7

Retina, 47 bytes

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

Try it online! Note: Several lines have trailing spaces. Explanation:

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

The first step is to insert each word into following lines at the same indentation. For example, with the lines aisle, wasabi and elf the resulting lines are aisle, aisle wasabi and aisle wasabi elf. I discovered this regex by trial and error so there may be edge cases with it.

O$`
$L$&

We can now sort the lines case-insensitively.

\S+ 
 

Delete all of the inserted words.

Neil
fuente
4

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

-5 bytes thanks to nwellnhof

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

Try it online!

This uses Chas Brown's method. An anonymous code block that takes a list of lines and returns a list of lines.

Explanation:

{                                        }  # 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
fuente
@nwellnhof Thanks for pointing that out. I think I've fixed it in the latest version
Jo King
@nwellnhof Ah well, it was shorter in a previous iteration. Thanks for the bytes off, but I had to change it slightly
Jo King
Oh, right. Actually, something like {my@a;.sort:{@a[+.comb(' ')...*>@a]=$_;~@a}} is required to support higher indentation levels.
nwellnhof
3

Clean, 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$

Try it online!

Anonymous function :: [[Char]] -> [[Char]] which wraps $ :: [[Char]] -> [[[Char]]] into the right output format. $ groups the strings into "more spaces than" and "everything else afterwards", recurses over each group and sorts when they're adjoined. At each step, the list being sorted looks like:

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

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

Try it online!

Defines the function $ :: [[Char]] -> [[Char]] which separates the strings into tuples in the form (spaces, letters) which are recursively sorted by the helper function ? :: [([Char],[Char])] -> [[([Char],[Char])]].

Explained:

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

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

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

Try it online!

Similar approach to Chas Brown's Python answer, but using regular expressions instead.

Explanation

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

K4, 51 bytes

Solution:

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

Example:

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"

Assumptions:

a. That each hierarchy will start with the lowest level, i.e. you will not get:

bdellium
      fox
    hound
    alien

Explanation:

{,/(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
fuente
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 (sort of):

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

It's a pretty straightforward recursive implementation. We check the indentation level by searching for the first non-space character (/\S/) and getting its index ($-[0]). Unfortunately, we actually have to declare a handful of variables that are used in the recursion, or else they'll be implicitly global and the recursion won't work correctly.

Silvio Mayolo
fuente