Stwórz alphabeTrie

31

Rozważ następującą alfabetycznie posortowaną listę słów:

balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom

Wszystkie słowa zaczynają się od b, a pierwszych 5 zaczyna się od bal. Jeśli spojrzymy tylko na pierwsze 2 słowa:

balderdash
ballet

zamiast tego moglibyśmy napisać:

balderdash
  +let

gdzie ' 'jest używane, gdy słowo dzieli znak przedrostka z poprzednim słowem; z wyjątkiem '+'znaku wskazującego OSTATNI znak, w którym drugie słowo ma przedrostek z poprzednim słowem.

Jest to rodzaj wizji „trie” : rodzic ma „ bal” i ma 2 potomków: 'derdash'i 'let'.

Z dłuższą listą, taką jak:

balderdash
ballet
brooding

możemy dodatkowo użyć znaku potoku, '|'aby wyjaśnić, gdzie kończy się wspólny prefiks, w następujący sposób:

balderdash
| +let
+rooding

a równoważne drzewo miałoby korzeń 'b'posiadania dwojga dzieci: poddrzewo mające korzeń 'al'i jego dwoje dzieci 'derdash'oraz 'let'; a 'rooding'.

Jeśli zastosujemy tę strategię do naszej oryginalnej listy,

balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom

otrzymujemy wynik, który wygląda następująco:

balderdash    
| +let     
|  +oonfish
|   | +ist 
|   +t     
+rooding   
   +m 

Jeśli dwa kolejne słowa na liście nie mają wspólnego prefiksu, znaki specjalne nie są zastępowane; np. dla listy:

broom
brood
crude
crumb

chcemy wynik:

broom
   +d
crude
  +mb

Wkład

Słowa na wejściu będą się składać wyłącznie z znaków alfanumerycznych (bez spacji i interpunkcji); może to mieć postać listy ciągów, pojedynczego ciągu lub innego rozsądnego podejścia, o ile podasz wybrany format. Żadne dwa kolejne słowa nie będą takie same. Lista zostanie posortowana alfabetycznie.

Wydajność

Dane wyjściowe mogą zawierać końcowe białe znaki na linię lub łącznie, ale nie mogą zawierać wiodących białych znaków. Dopuszczalna byłaby również lista ciągów lub temu podobnych.

To jest ; najkrótszy kod w każdym języku zachowuje prawo do chwalenia się. Obowiązują zwykłe zakazy dotyczące luk.

Przypadki testowe

Input:
apogee
apology
app
apple
applique
apply
apt

Output:
apogee     
 |+logy    
 +p        
 |+le      
 | +ique   
 | +y      
 +t        

Input:
balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom
donald
donatella
donna
dont
dumb

Output:
balderdash 
| +let     
|  +oonfish
|   | +ist 
|   +t     
+rooding   
   +m      
donald     
| |+tella  
| +na      
| +t       
+umb 
Chas Brown
źródło
Co z przypadkiem, w którym mam słowo ballpo balloon. Jakiej produkcji powinniśmy się spodziewać?
Don Thousand
@RushabhMehta Zgaduję, że miałbyś +mniej niż pierwsze o, ale nie napisałem wyzwania, więc nie jestem pewien.
Theo
5
@RushabhMehta Słowa są posortowane alfabetycznie, więc tak się nie stanie.
Neil,
@Neil Oh dobra uwaga
Don Thousand
2
Słowa na wejściu będą się składać wyłącznie z alfanumerycznych : czy to naprawdę zawiera cyfry, czy miałeś na myśli alfabet?
Arnauld

Odpowiedzi:

11

Retina 0.8.2 , 58 57 bajtów

^((.*).)(?<=\b\1.*¶\1)
$.2$* +
m)+`^(.*) (.*¶\1[+|])
$1|$2

Wypróbuj online! Link zawiera jeden przypadek testowy. Edycja: Zapisałem 1 bajt dzięki @FryAmTheEggman wskazując, że przeoczyłem przejście z \bna ^możliwe przez m). Wyjaśnienie:

m)

Włącz per-line ^dla całego programu.

^((.*).)(?<=^\1.*¶\1)
$.2$* +

Dla każdego słowa spróbuj dopasować jak najwięcej od początku poprzedniego słowa. Zmień dopasowanie na spacje, z wyjątkiem ostatniego znaku, który staje się a +.

+`^(.*) (.*¶\1[+|])
$1|$2

Wielokrotnie zamieniaj wszystkie spacje bezpośrednio nad +s lub |s na |s.

Neil
źródło
@FryAmTheEggman Rzeczywiście, dodałem m)specjalnie, aby móc to zrobić, więc denerwuję się, że przegapiłem instancję.
Neil,
Ugh, dlaczego nawet zawracam sobie głowę odpowiadaniem na komentarze, jeśli ludzie zamierzają je usunąć ...
Neil,
9

JavaScript (ES6), 128 bajtów

Oczekuje i zwraca listę list znaków.

a=>a.map((w,y)=>a[~y]=w.map(m=(c,x)=>(p=a[y-1]||0,m|=c!=p[x])?c:p[x+1]==w[x+1]?' ':(g=y=>a[y][x]<1?g(y+1,a[y][x]='|'):'+')(-y)))

Wypróbuj online!

W jaki sposób?

Spacje i +'można wstawiać, przechodząc od pierwszego do ostatniego słowa w kolejności, ale |' można wstawić a posteriori dopiero po +zidentyfikowaniu. Można to osiągnąć, wykonując dwa różne przejścia, ale zamiast tego zapisujemy wskaźnik do każdego zmodyfikowanego wpisu, a[~y]aby można go było później zaktualizować ponownie w tej samej map()pętli.

Teoretycznie prostszym obejściem byłoby obejrzenie słów w odwrotnej kolejności i odwrócenie wyników również na końcu procesu. Ale jest to trochę kosztowne w JS i nie znalazłem sposobu na uzyskanie krótszej wersji za pomocą tej metody.

a =>                           // a[] = input array
  a.map((w, y) =>              // for each word w at position y in a[]:
    a[~y] =                    //   save a pointer to the current entry in a[~y]
    w.map(m =                  //   initialize m to a non-numeric value
      (c, x) => (              //   for each character c at position x in w:
        p = a[y - 1] || 0,     //     p = previous word or a dummy object
        m |= c != p[x]         //     set m = 1 as soon as w differs from p at this position
      ) ?                      //     if w is no longer equal to p:
        c                      //       append c
      :                        //     else:
        p[x + 1] == w[x + 1] ? //       if the next characters are still matching:
          ' '                  //         append a space
        : (                    //       else:
            g = y =>           //         g() = recursive function to insert pipes
            a[y][x] < 1 ?      //           if a[y][x] is a space:
              g(               //             do a recursive call to g()
                y + 1,         //               with y + 1
                a[y][x] = '|'  //               and overwrite a[y][x] with a pipe
              )                //             end of recursive call
            :                  //           else:
              '+'              //             make the whole recursion chain return a '+'
                               //             which will be appended in the current entry
          )(-y)                //         initial call to g() with -y (this is ~y + 1)
    )                          //   end of map() over the characters
  )                            // end of map() over the words
Arnauld
źródło
czy mógłbyś spojrzeć na moje rozwiązanie, sam to wymyśliłem, ale przypomina o twoim rozwiązaniu. więc jeśli jest zbyt blisko, możesz przesłać go jako swój (lub nie) i źle go usunąć :)
DanielIndie
@DanielIndie Bez obaw. Jest wystarczająco inny.
Arnauld,
2

JavaScript (Node.js) , 125 122 118 117 bajtów

a=>a.map((w,i)=>a[i]=w.map((T,k)=>+i&&l[k]==T?l[-~k]<w[-~k]?(g=_=>a[--i][k]<"+"?g(a[i][k]="|"):"+")():" ":(i=l=w,T)))

Wypróbuj online!

  • dzięki @Arnauld za testowanie tio :)
DanielIndie
źródło
1

Python, 263 260 bajtów

- 3 bajty dzięki Jonathanowi Frechowi

Kod:

p=lambda t,f,g:"\n".join([(f[:-1]+"+"if(a!=min(t))*g else"")+a+p(t[a],(f+" "if len(t[a])>1or a==max(t)else f[:-1]+"| "),1)for a in t])if t else""
def a(t,x):
 if x:c=x[0];t[c]=c in t and t[c]or{};a(t[c],x[1:])
def f(*s):t={};[a(t,i)for i in s];return p(t,"",0)

Wypróbuj online!

Wyjaśnienie:

To rozwiązanie buduje trie ze słów wejściowych i rekursywnie analizuje je na wymagane dane wyjściowe. Funkcja pobiera trójkę i ciąg s oraz dodaje x do t. Próbki są implementowane jako zagnieżdżone słowniki. Każdy słownik reprezentuje węzeł w trie. Na przykład słownik reprezentujący trie wygenerowany przez pierwszy przypadek testowy wygląda następująco:

{'b': {'a': {'l': {'d': {'e': {'r': {'d': {'a': {'s': {'h': {}}}}}}}, 'l': {'e': {'t': {}}, 'o': {'o': {'n': {'f': {'i': {'s': {'h': {}}}}, 'i': {'s': {'t': {}}}}}, 't': {}}}}}, 'r': {'o': {'o': {'d': {'i': {'n': {'g': {}}}}, 'm': {}}}}}}

Funkcja p powtarza się przez tę strukturę i generuje ciąg reprezentujący trie oczekiwaną przez wyzwanie. Funkcja f przyjmuje kilka argumentów jako argumenty, dodaje je wszystkie do trie za pomocą a, a następnie zwraca wynik wywołania p na trie.

Zachary Cotton
źródło
1
Możliwe 252 bajty .
Jonathan Frech,
1

C (gcc) , 165 155 bajtów

Przyjmuje trzy argumenty:

  • char** a : tablica słów zakończonych znakiem null
  • char* m : tablica długości każdego słowa
  • int n : liczba słów w tablicy
f(a,m,n,i,j)char**a,*m;{for(i=n;--i;)for(j=0;j<m[i]&j<m[i-1]&a[i][j]==a[i-1][j];j++)a[i][j]=a[i][j+1]^a[i-1][j+1]?43:++i<n&j<m[i]&a[i--][j]%81==43?124:32;}

Wypróbuj online!

Curtis Bechtel
źródło
@Arnauld Oczywiście! Chociaż ++i<n&j<m[i]&a[i--]zachowanie nie jest niezdefiniowane? Czy mogę polegać na ocenie gcc od lewej do prawej?
Curtis Bechtel
Jest to bardzo prawdopodobne zachowanie nieokreślone. Ale definiujemy języki według ich implementacji, więc dopóki działa ono spójnie z tą wersją gcc, myślę, że to w porządku.
Arnauld
1

Perl 6 , 149 144 142 bajtów

{1 while s/(\n.*)\s(.*)$0(\+|\|)/$0|$1$0$2/;$_}o{$=({.[1].subst(/^(.+)<?{.[0].index($0)eq 0}>/,{' 'x$0.ords-1~'+'})}for '',|$_ Z$_).join("
")}

Wypróbuj online!

Jestem pewien, że można to jeszcze bardziej pograć w golfa, zwłaszcza że nie jestem ekspertem od wyrażeń regularnych. Wykorzystuje to ten sam proces, co odpowiedź Retina Neila .

Jo King
źródło
0

Python 2 , 191 bajtów

def f(w,r=['']):
 for b,c in zip(w[1:],w)[::-1]:
	s='';d=0
	for x,y,z in zip(r[0]+b,b,c+b):t=s[-1:];s=s[:-1]+[['+'*(s>'')+y,t+' |'[x in'+|']][y==z],t+y][d];d=d|(y!=z)
	r=[s]+r
 return[w[0]]+r

Wypróbuj online!

Chas Brown
źródło
0

Rubin , 118 bajtów

->a{i=1;a.map{s="";a[i+=j=-1].chars{|c|a[i][j+=1]=i<0&&a[i-1][/^#{s+=c}/]?a[i+1][j]=~/[|+]/??|:?\s:c}[/[| ]\b/]&&=?+}}

Wypróbuj online!

Akceptuje tablicę ciągów wyjściowych, modyfikując oryginalną tablicę wejściową w miejscu.

Wyjaśnienie

Podstawowa transformacja łańcucha nie jest zbyt skomplikowana, ale aby poprawnie wstawić pionowe rury, musimy iterować w odwrotnej kolejności, a ponieważ reversemetoda jest dość szczegółowa, zrobimy to w trudniejszy sposób. Tutaj używamy maptylko do uruchomienia pętli, zostawmy pierwsze słowo w spokoju, a następnie iterujemy od końca za pomocą indeksów ujemnych:

->a{
 i=1;                   #Initialize word indexer
 a.map{                 #Loop
  s="";                 #Initialize lookup string
  a[i+=j=-1]            #Initialize char indexer and decrement i
  .chars{|c|            #Loop through each char c of current word
   a[i][j+=1]=          #Mofify current word at position j 
    i<0&&               #If it's not the first word and
    a[i-1][/^#{s+=c}/]? #Word above matches current one from start to j
     a[i+1][j]=~/[|+]/? #Then if char below is | or +
      ?|:?\s:c          #Then set current char to | Else to Space Else leave as is
  }[/[| ]\b/]&&=?+      #Finally, replace Space or | at word boundary with +
 }
}
Kirill L.
źródło