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 golf golfowy ; 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 

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.

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

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

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.

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!

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 .

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!

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