Dibujando un árbol de una matriz

24

Dada una matriz posiblemente anidada, no vacía, de enteros positivos de un solo dígito (no garantizado como único), genera la representación de arte ASCII como un árbol, utilizando los caracteres de dibujo de caja ┌ ┴ ┐ ─ │ ┬ ┼. (Se copiaron de la página de códigos 437, pero puede usar cualquier representación equivalente).

Cada entero de la matriz debe ser una hoja del árbol. Los elementos del mismo nivel profundo en la matriz deben estar presentes en el mismo nivel del árbol. Todos los elementos deben estar separados por suficiente espacio en blanco para ser distintos (depende de usted determinar cuán ancho, mínimo de un espacio entre ellos).

Por ejemplo, una matriz dada [[1, [2]], [3, [4, 5]]], genera el siguiente árbol

 ┌─┴─┐
┌┴┐ ┌┴─┐
1 │ 3 ┌┴┐
  2   4 5

Para la matriz, [1, 2, 3]el árbol podría verse como

┌─┼─┐
1 2 3

Pero la matriz [[1, 2, 3]]se vería así

  │
┌─┼─┐
1 2 3

Mientras que la matriz [1, [1, [1, [1]]]]podría verse así

 ┌─┴┐
 1 ┌┴─┐
   1 ┌┴┐
     1 │
       1

Como un ejemplo más complicado, [1, [[[2, 3], 4], 5]]podría ser

┌┴───┐
1  ┌─┴┐
 ┌─┴┐ 5
┌┴┐ 4
2 3

o varias otras variaciones.


  • La entrada y salida se pueden dar por cualquier método conveniente .
  • Puede imprimirlo en STDOUT o devolverlo como resultado de una función.
  • Un programa completo o una función son aceptables.
  • Cualquier cantidad de espacios en blanco extraños es aceptable, siempre y cuando los caracteres se alineen apropiadamente.
  • Las lagunas estándar están prohibidas.
  • Este es el por lo que se aplican todas las reglas habituales de golf, y gana el código más corto (en bytes).
AdmBorkBork
fuente
[1,[[[2,3],4],5]]podría ser un caso de prueba interesante ya que necesita que la raíz se extienda artificialmente para que el subárbol derecho no choque con el subárbol izquierdo.
Poke
@Poke Agregado como ejemplo. Hay varias variaciones posibles para ese caso de prueba.
AdmBorkBork
2
El primer ejemplo para ese caso de prueba no puede ser correcto. Esto sugiere que el segundo elemento próximo a la 1es una matriz de 3 artículos: [2,3], 4, y 5. Pero 4 y 5 no son adyacentes.
Draco18s
44
Eso me parece [1, [[[2, 3]], [4], 5]]a mí.
Neil
¿Cuál (si alguno) de estos formatos de entrada alternativos sería aceptable?
Horrible

Respuestas:

12

Python 3 , 400 393 390 bytes

L=len
S,*K=' ┴┼│123456789'
def T(x):
 try:return[str(x+0)]
 except:
  z=[*map(T,x)];q=max(map(L,z))
  for p in z:p+=[S*L(p[0])]*(q-L(p))
  b=[S.join(a)for a in zip(*z)];t=b[0];l=L(t);s=0;e=L(z);r=[S]*l
  if e<2:return['│'.center(l),*b]
  for i in range(l):
   if t[i]in K:s+=1;r[i]='┬┌┐'[(s<e)-(s>1)]
   elif 0<s<e:r[i]='─'
  c=l//2;r[c]=K[r[c]=='┬'];return[''.join(r),*b]

Devuelve una lista de cadenas de arriba a abajo.

EDITAR 1: recortó 7 bytes evitando la duplicación de ┴┼(ahorro neto de 2 bytes), cortando 0 de una cadena, cambiando la forma en que se seleccionan los caracteres de dibujo ┬┌┐(uso en <lugar de ==) y reemplazando un L(z)que perdí cone

EDIT 2: -2 bytes gracias a ovs y -1 byte gracias a Kevin Cruijssen

Pruébalo en línea!

Sin golf

def layer(item):
    if isinstance(item, int):
        return [str(item)]
    else:
        subs = [layer(sub) for sub in item]
        longest = max(map(len, subs))
        for sub in subs:
            sub += [' ' * len(sub[0])] * (longest - len(sub))
        below = [' '.join(l) for l in zip(*subs)]
        top = below[0]
        l = len(top)
        if len(subs) == 1:
            return ['│'.center(l), *below]
        seen = 0
        expected = len(subs)
        builder = [' '] * l
        for i in range(l):
            c = top[i]
            if c in '┴┼│123456789':
                seen += 1
                if seen == 1:
                    builder[i] = '┌'
                elif seen == expected:
                    builder[i] = '┐'
                else:
                    builder[i] = '┬'
            elif 0 < seen < expected:
                builder[i] = '─'
        center = l // 2
        if builder[center] == '┬':
            builder[center] = '┼'
        else:
            builder[center] = '┴'
        return [''.join(builder), *below]

Construye un árbol desde las hojas hacia arriba, una capa a la vez.

Carne de res
fuente
2
Agregué los casos de prueba a su enlace TIO ¡ Pruébelo en línea!
pizzapants184
¡Buena respuesta! Puede acortar este por dos bytes asignando el espacio a una variable de la siguiente manera: S,*K=' ┴┼│123456789'.
ovs
1
e==1puede ser e<2guardar un byte (no creo que alguna vez pueda ser 0, ya que el desafío indica que la entrada no está vacía, y las entradas vacías ya habrían fallado max(map(L,z))en ese caso de todos modos)
Kevin Cruijssen
3

Limpio , 544 506 bytes

Los escapes se usan para evitar UTF-8 inválido en SE / TIO pero se cuentan como un byte ya que son literales válidos

import StdEnv,Data.List;::T=I Int|L[T];$l#m= @l#k=map maxList(transpose m)=flatlines[[last[' ':[(\_|v<0|w<[j]|q>hd w|q<last w|any((==)q)w|q==j='\305'='\302'|q==j='\301'='\304'='\277'='\332'='\263'=toChar v+'0')0\\[v,r,j:w]<-m|r/2==p&&q>=hd w&&q<=last w]]\\q<-[0..k!!3]]\\p<-[0..k!!1]];@(L l)#p=twice(\p=[[v,r+1:[e+sum([2\\[v:_]<-i|0<=v]++zipWith(\c j=j!!2-c!!3)t(takeWhile(\[z:_]=v+z< -1)(tl t)))-x!!1\\e<-x]]\\i<-inits p&t<-tails p&[v,r:x]<-p])(concatMap@l)#g=[g\\[_,2,g:_]<-p]=[[-1,0,(hd g+last g)/2:g]:p];@(I i)=[[i,0,0,0]];

Pruébalo en línea!

Toma entrada en el formato L[I 3, L[I 4, I 5], I 2]..

Conecta los árboles de abajo hacia arriba, de izquierda a derecha, luego ajusta las distancias de derecha a izquierda.

Prettified, tipo de:

import StdEnv, Data.List;
:: T = I Int | L [T];
$ l
    #m = @l
    #k = map maxList (transpose m)
    = flatlines [
        [
            last[
                ' ':
                [
                    if(v < 0)
                        if(w < [j])
                            if(q > hd w)
                                if(q < last w)
                                    if(any ((==) q) w)
                                        (
                                            if(q == j)
                                                '\305'
                                                '\302'
                                        )(
                                            if(q == j)
                                                '\301'
                                                '\304'
                                        )
                                    '\277'
                                '\332'
                            '\263'
                        (toChar v + '0')
                    \\ [v, r, j: w] <- m
                    | r/2 == p && q >= hd w && q <= last w
                ]
            ]
            \\ q <- [0..k!!3]
        ]
        \\p<-[0..k!!1]
    ];
@ (L l)
    #p = twice
        ( \p
            = [
                [
                    v, r + 1:
                    map
                        (
                            (+)
                            (
                                sum [2 \\ [v: _] <- i| 0 <= v]
                                + sum (
                                    zipWith
                                        (
                                            \[_, _, _, c: _] [_, _, j: _] = j - c
                                        )
                                        t
                                        (
                                            takeWhile (\[v: _] = v < 0) (tl t)
                                        )
                                ) * (1 - sign (v + 1))
                                - x!!1
                            )
                        )
                        x
                ]
            \\ i <- inits p
            &  t <- tails p
            &  [v, r: x] <- p
            ]
        )
        (concatMap @ l)
    #g = [g \\ [_, 2, g: _] <- p]
    =[[-1, 0, (hd g + last g)/2: g]: p];
@ (I i) = [[i, 0, 0, 0]];
Οurous
fuente
3

Carbón , 127 123 bytes

↶≔⟦⟦θ⟧⟧ηFη«≔⊟ιζ¿⁼Iζ⪫⟦ζ⟧ω⊞υ⊞OιζFLζ⊞η⁺ι⟦⊖Lζκ§ζκ⟧»Wυ«≔⌊υι≔Φυ¬⁼κιυJ±⊗Lυ⊘⊖LιI⊟ιWι«≔⊟ιζ¿ζ«←§┐┬‹ζ⊟ιW⁼KKψ←─≔⁰ι»¿⊟ι┌¶┴¦│

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

Cambie la dirección de dibujo predeterminada a arriba ya que no dibujamos nada a la derecha.

≔⟦⟦θ⟧⟧η

El primer paso es convertir la representación de la matriz anidada en una representación de índice, que es una lista de todas las entradas junto con los índices de las submatrices, por ejemplo, para la entrada q=[1, [[[2, 3]], [4], 5]]the 5is q[1][2]y, por lo tanto, la lista que queremos es 1, 2. Comenzamos con una sola entrada para procesar, que es una lista que contiene una lista de los índices actuales (es decir, ninguno hasta ahora) y la entrada original.

Fη«

Pase sobre las matrices a medida que las procesamos. (Convenientemente, el carbón continuará iterando sobre una lista si lo presionas durante la iteración).

≔⊟ιζ

Obtenga la siguiente matriz para procesar.

¿⁼Iζ⪫⟦ζ⟧ω

¿Es esto realmente un escalar en lugar de una matriz?

⊞υ⊞Oιζ

Si es así, la lista que teníamos en realidad pertenece a la lista final de listas de índices.

FLζ

De lo contrario, repita cada elemento en esta matriz ...

⊞η⁺ι⟦⊖Lζκ§ζκ⟧»

... y guárdelo con su nueva lista de índices hasta ahora para su posterior procesamiento. También se guarda el índice máximo de la matriz, que se utiliza para casos especiales del último elemento de la matriz.

Wυ«

Ahora estamos listos para recorrer la lista de listas de índices. Sin embargo, la lista no está en orden lexicográfico, por lo que no podemos iterarla directamente.

≔⌊υι

Encuentra el siguiente elemento en orden lexicográfico.

≔Φυ¬⁼κιυ

Eliminarlo de la lista.

J±⊗Lυ⊘⊖Lι

Salta a la posición del escalar en la salida. Podemos calcular esto dado que podemos contar el número de escalares que producimos y también sabemos el número de entradas en su lista de índice.

I⊟ι

Realmente imprime el escalar.

Wι«

Recorre las entradas en la lista de índice. Nuevamente, esto no es una iteración simple, porque las entradas vienen en pares, y también debemos ser capaces de salir del ciclo.

≔⊟ιζ

Extraiga el siguiente índice de la lista.

¿ζ«

Si este no es el primer elemento de la lista ...

←§┐┬‹ζ⊟ι

... luego imprime o depende de si este es el último elemento de la lista ...

W⁼KKψ←─

... e imprima suficientes s para completar la entrada anterior en este nivel ...

≔⁰ι»

... y borra la variable para salir del ciclo ya que hemos terminado aquí.

¿⊟ι┌¶┴

De lo contrario, si este es (el primer elemento de) una lista de elementos múltiples, imprima ┌┴y deje el cursor sobre el para tratar con el padre de este nivel.

¦│

De lo contrario, si se trata de una lista de 1 elemento, simplemente imprima ay suba una línea para tratar con el padre de este nivel.

Neil
fuente