Desenhando uma árvore de uma matriz

24

Dada uma matriz não vazia, possivelmente aninhada, de números inteiros positivos de um dígito (não garantido exclusivo), imprima a representação de arte ASCII como uma árvore, usando os caracteres de desenho de caixa ┌ ┴ ┐ ─ │ ┬ ┼. (Eles foram copiados da Página 437 do Código, mas você pode usar qualquer representação equivalente).

Todo número inteiro da matriz deve ser uma folha da árvore. Elementos com o mesmo nível na matriz devem estar presentes no mesmo nível da árvore. Todos os elementos devem ser separados por espaços em branco suficientes para serem distintos (depende de você determinar a largura, o mínimo de um espaço entre eles).

Por exemplo, dada matriz [[1, [2]], [3, [4, 5]]], produz a seguinte árvore

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

Para matriz, [1, 2, 3]a árvore pode parecer

┌─┼─┐
1 2 3

Mas a matriz [[1, 2, 3]]pareceria

  │
┌─┼─┐
1 2 3

Embora a matriz [1, [1, [1, [1]]]]possa parecer

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

Como um exemplo mais complicado, [1, [[[2, 3], 4], 5]]poderia ser

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

ou várias outras variações.


  • A entrada e a saída podem ser fornecidas por qualquer método conveniente .
  • Você pode imprimi-lo em STDOUT ou retorná-lo como resultado de uma função.
  • Um programa completo ou uma função são aceitáveis.
  • Qualquer quantidade de espaço em branco estranho é aceitável, desde que os caracteres sejam alinhados adequadamente.
  • As brechas padrão são proibidas.
  • Isso é portanto todas as regras usuais de golfe se aplicam e o código mais curto (em bytes) vence.
AdmBorkBork
fonte
[1,[[[2,3],4],5]]pode ser um caso de teste interessante, pois precisa ter a raiz estendida artificialmente para que a subárvore direita não colide com a subárvore esquerda.
Puxa
@Poke Adicionado como exemplo. Existem várias variações possíveis para esse caso de teste.
AdmBorkBork
2
O primeiro exemplo para esse caso de teste não pode estar certo. Isso sugere que o segundo elemento é próxima à 1de um conjunto de 3 elementos: [2,3], 4, e 5. Mas 4 e 5 não são adjacentes.
Draco18s
4
Isso [1, [[[2, 3]], [4], 5]]me parece .
Neil
Quais (se houver) desses formatos de entrada alternativos seriam aceitáveis?
Οurous

Respostas:

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]

Retorna uma lista de cadeias de cima para baixo.

EDIT 1: Aparado 7 bytes, evitando a duplicação de ┴┼(economia líquida de 2 bytes), cortando 0 de uma sequência, alterando a maneira como os caracteres de desenho são selecionados ┬┌┐(use em <vez de ==) e substituindo um que L(z)eu perdi pore

EDIT 2: -2 bytes graças a ovs e -1 byte graças a Kevin Cruijssen

Experimente online!

Ungolfed

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]

Constrói uma árvore a partir das folhas, uma camada de cada vez.

Beefster
fonte
2
Adicionei os casos de teste ao seu link TIO Experimente online!
pizzapants184 14/02
Boa resposta! Você pode encurtar este por dois bytes, atribuindo o espaço para uma variável como este: S,*K=' ┴┼│123456789'.
ovs 14/02
11
e==1pode ser e<2para salvar um byte (eu não acho que isso nunca pode ser 0, uma vez que o desafio afirma a entrada é não vazio - e entradas vazias já teria falhado no max(map(L,z))., nesse caso, de qualquer maneira)
Kevin Cruijssen
3

Limpo , 544 506 bytes

Escapes são usados ​​para evitar UTF-8 inválido no SE / TIO, mas contados como um byte, pois são literais 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]];

Experimente online!

Recebe entrada no formato L[I 3, L[I 4, I 5], I 2]..

Conecta as árvores de baixo para cima, da esquerda para a direita, e ajusta as distâncias da direita para a esquerda.

Pretificado, mais ou menos:

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]];
Furioso
fonte
3

Carvão , 127 123 bytes

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

Experimente online! Link é a versão detalhada do código. Explicação:

Altere a direção do desenho padrão para cima, pois não desenhamos nada à direita.

≔⟦⟦θ⟧⟧η

O primeiro passo é converter a representação de matriz aninhada em uma representação de índice, que é uma lista de todas as entradas juntamente com os índices das sub-matrizes, por exemplo, para a entrada q=[1, [[[2, 3]], [4], 5]]the 5is q[1][2]e, portanto, a lista que queremos 1, 2. Começamos com uma única entrada para processar, que é uma lista que contém uma lista dos índices atuais (ou seja, nenhum até agora) e a entrada original.

Fη«

Passe pelas matrizes enquanto as processamos. (Convenientemente, o Charcoal continuará a iterar sobre uma lista se você pressionar durante a iteração.)

≔⊟ιζ

Obter a próxima matriz para processar.

¿⁼Iζ⪫⟦ζ⟧ω

Isso é realmente um escalar e não uma matriz?

⊞υ⊞Oιζ

Nesse caso, a lista que tínhamos realmente pertence à lista final de listas de índices.

FLζ

Caso contrário, faça um loop sobre cada elemento nesta matriz ...

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

... e salve-a com sua nova lista de índices até o momento para processamento adicional. O índice máximo da matriz também é salvo, o qual é usado para casos especiais do último elemento da matriz.

Wυ«

Agora estamos prontos para percorrer a lista de listas de índices. No entanto, a lista não está em ordem lexicográfica, portanto, não podemos iterá-la diretamente.

≔⌊υι

Encontre o próximo elemento em ordem lexicográfica.

≔Φυ¬⁼κιυ

Remova-o da lista.

J±⊗Lυ⊘⊖Lι

Pule para a posição do escalar na saída. Podemos calcular isso, pois podemos manter a contagem do número de escalares que produzimos e também sabemos o número de entradas em sua lista de índices.

I⊟ι

Na verdade, imprima o escalar.

Wι«

Passe pelas entradas na lista de índices. Novamente, essa não é uma iteração simples, porque as entradas vêm em pares e também precisamos ser capazes de sair do loop.

≔⊟ιζ

Extraia o próximo índice da lista.

¿ζ«

Se este não for o primeiro elemento da lista ...

←§┐┬‹ζ⊟ι

... imprima ou dependendo se esse é o último elemento da lista ...

W⁼KKψ←─

... e imprima s suficientes para preencher a entrada anterior neste nível ...

≔⁰ι»

... e limpe a variável para sair do loop, pois terminamos aqui.

¿⊟ι┌¶┴

Caso contrário, se este for (o primeiro elemento de) uma lista de vários elementos, imprima o ┌┴, deixando o cursor acima do para lidar com o pai desse nível.

¦│

Caso contrário, se esta for uma lista de 1 elemento, basta imprimir a e mover uma linha para cima para lidar com o pai desse nível.

Neil
fonte