Rysowanie drzewa z tablicy

24

Biorąc pod uwagę potencjalnie zagnieżdżoną, niepustą tablicę jednocyfrowych liczb całkowitych dodatnich (nie gwarantowanych niepowtarzalnych), wyprowadzaj reprezentację ASCII-art jako drzewo, używając znaków rysujących ramkę ┌ ┴ ┐ ─ │ ┬ ┼. (Zostały one skopiowane z Code Page 437, ale możesz użyć dowolnej równoważnej reprezentacji).

Każda liczba całkowita tablicy powinna być liściem drzewa. Elementy tego samego poziomu głęboko w tablicy powinny znajdować się na tym samym poziomie drzewa. Wszystkie elementy powinny być oddzielone wystarczającą liczbą białych znaków, aby były wyraźne (to Ty decydujesz, jak szeroka, minimum jedna przestrzeń między nimi).

Na przykład podana tablica [[1, [2]], [3, [4, 5]]]wyświetla następujące drzewo

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

Dla tablicy [1, 2, 3]drzewo może wyglądać

┌─┼─┐
1 2 3

Ale tablica [[1, 2, 3]]wyglądałaby tak

  │
┌─┼─┐
1 2 3

Podczas gdy tablica [1, [1, [1, [1]]]]może wyglądać

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

Bardziej skomplikowanym przykładem [1, [[[2, 3], 4], 5]]może być

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

lub kilka innych odmian.


  • Dane wejściowe i wyjściowe można podać dowolną dogodną metodą .
  • Możesz wydrukować go do STDOUT lub zwrócić jako wynik funkcji.
  • Dopuszczalny jest pełny program lub funkcja.
  • Dopuszczalna jest dowolna ilość obcych białych znaków, o ile znaki są odpowiednio ustawione w jednej linii.
  • Standardowe luki są zabronione.
  • To jest więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).
AdmBorkBork
źródło
[1,[[[2,3],4],5]]może być interesującym przypadkiem testowym, ponieważ musi on sztucznie rozciągać się root, aby prawe poddrzewa nie kolidowało z lewym poddrzewem.
Poke
@Poke Dodano jako przykład. Istnieje kilka możliwych odmian tego przypadku testowego.
AdmBorkBork
2
Pierwszy przykład tego przypadku testowego nie może być prawidłowy. Sugeruje to, że s drugi element obok 1jest tablicą z 3 elementów: [2,3], 4, i 5. Ale 4 i 5 nie sąsiadują ze sobą.
Draco18s
4
To mi wygląda [1, [[[2, 3]], [4], 5]].
Neil
Który (jeśli w ogóle) z tych alternatywnych formatów wejściowych byłby dopuszczalny?
Οurous

Odpowiedzi:

12

Python 3 , 400 393 390 bajtów

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]

Zwraca listę ciągów znaków od góry do dołu.

EDYCJA 1: Skrócono 7 bajtów, unikając powielania ┴┼(oszczędność netto 2 bajtów), wycinając 0 z jednego ciągu, zmieniając sposób wybierania znaków rysunkowych ┬┌┐(używaj <zamiast ==) i zastępując L(z)brakującee

EDYCJA 2: -2 bajty dzięki ovs i -1 bajtów dzięki Kevin Cruijssen

Wypróbuj online!

Bez golfa

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]

Z liści tworzy się drzewo, jedna warstwa na raz.

Wołowina
źródło
2
Dodałem skrzynki testowe do linku TIO Wypróbuj online!
pizzapants184
Niezła odpowiedź! Można skrócić ten przez dwa bajty, przypisując przestrzeń do zmiennej tak: S,*K=' ┴┼│123456789'.
ovs
1
e==1może być e<2zapisanie bajtu (nie sądzę, że może to być zawsze 0, ponieważ wyzwanie mówi, że dane wejściowe są niepuste - a puste dane i tak już by się nie udały max(map(L,z))w tym przypadku.)
Kevin Cruijssen
3

Czysty , 544 506 bajtów

Ucieczki służą do uniknięcia nieprawidłowego UTF-8 na SE / TIO, ale są liczone jako jeden bajt, ponieważ są poprawnymi literałami

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

Wypróbuj online!

Pobiera dane wejściowe w formacie L[I 3, L[I 4, I 5], I 2]..

Łączy drzewa od dołu do góry, od lewej do prawej, a następnie dostosowuje odległości od prawej do lewej.

Prettified, sorting of:

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]];
Obrzydliwe
źródło
3

Węgiel drzewny , 127 123 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

Zmień domyślny kierunek rysowania na wyższy, ponieważ nie rysujemy niczego po prawej stronie.

≔⟦⟦θ⟧⟧η

Pierwszym etapem jest konwersja zagnieżdżonych reprezentację tablicy do reprezentowania indeksu, który znajduje się lista wszystkich wpisów wraz z indeksom subarrays, np dla wejścia jest i dlatego chcemy listy jest . Zaczynamy od pojedynczego wpisu do przetworzenia, który jest listą zawierającą listę bieżących indeksów (tj. Jak dotąd żadnych) i oryginalne dane wejściowe.q=[1, [[[2, 3]], [4], 5]]5q[1][2]1, 2

Fη«

Pętla nad tablicami podczas ich przetwarzania. (Dogodnie węgiel drzewny będzie kontynuował iterację po liście, jeśli naciśniesz ją podczas iteracji.)

≔⊟ιζ

Uzyskaj kolejną tablicę do przetworzenia.

¿⁼Iζ⪫⟦ζ⟧ω

Czy to rzeczywiście skalar, a nie tablica?

⊞υ⊞Oιζ

Jeśli tak, to lista, którą mieliśmy, faktycznie należy do ostatecznej listy list indeksów.

FLζ

W przeciwnym razie zapętlić każdy element w tej tablicy ...

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

... i zapisz go z nową listą indeksów do dalszego przetwarzania. Zapisywany jest również maksymalny indeks tablicy, który jest używany do specjalnego przypadku ostatniego elementu tablicy.

Wυ«

Jesteśmy teraz gotowi na przeglądanie listy list indeksów. Jednak lista nie jest uporządkowana leksykograficznie, więc nie możemy iterować jej bezpośrednio.

≔⌊υι

Znajdź następny element w porządku leksykograficznym.

≔Φυ¬⁼κιυ

Usuń go z listy.

J±⊗Lυ⊘⊖Lι

Przeskocz do pozycji skalara na wyjściu. Możemy to obliczyć, biorąc pod uwagę, że możemy zliczać liczbę skalarów, które wypisujemy, a także znamy liczbę pozycji na liście indeksów.

I⊟ι

Właściwie wydrukuj skalar.

Wι«

Pętla nad wpisami na liście indeksów. Ponownie, nie jest to prosta iteracja, ponieważ wpisy przychodzą parami, a my musimy także być w stanie wyjść z pętli.

≔⊟ιζ

Wyodrębnij następny indeks z listy.

¿ζ«

Jeśli to nie pierwszy element na liście ...

←§┐┬‹ζ⊟ι

... następnie wydrukuj lub w zależności od tego, czy jest to ostatni element na liście ...

W⁼KKψ←─

... i wydrukuj tyle s, aby wypełnić poprzedni wpis na tym poziomie ...

≔⁰ι»

... i wyczyść zmienną, aby wyjść z pętli, odkąd skończyliśmy.

¿⊟ι┌¶┴

W przeciwnym razie, jeśli jest to (pierwszy element) listy wieloelementowej, wydrukuj ┌┴, pozostawiając kursor powyżej, aby zająć się rodzicem tego poziomu.

¦│

W przeciwnym razie, jeśli jest to lista 1-elementowa, po prostu wydrukuj a i przejdź w górę linii, aby poradzić sobie z rodzicem tego poziomu.

Neil
źródło