Make an alphabeTrie

Question

Consider the following alphabetically sorted list of words:

balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom

All of the words start with b, and the first 5 start with bal. If we just look at the first 2 words:

balderdash
ballet

we could write instead:

balderdash
  +let

where the ' ' is used where a word shares a prefix character with the previous word; except for the '+' character which indicates the LAST character where the second word shares a prefix with the previous word.

This is a sort of 'trie' visualization: the parent is 'bal', and has 2 descendants: 'derdash' and 'let'.

With a longer list, such as:

balderdash
ballet
brooding

we can additionally use the pipe character '|' to make it clearer where the shared prefix ends, as follows:

balderdash
| +let
+rooding

and the equivalent tree would have a root of 'b' having two children: the subtree having root 'al' and and its two children 'derdash' and 'let'; and 'rooding'.

If we apply this strategy to our original list,

balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom

we get output that looks like:

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

If two consecutive words in the list have no shared prefix, no special characters are substituted; e.g. for the list:

broom
brood
crude
crumb

we want the output:

broom
   +d
crude
  +mb

Input

The words in the input will be made up of only alphanumerics (no spaces or punctuation); this may be in the form of a list of strings, a single string, or any other reasonable approach, as long as you specify your chosen format. No two consecutive words will be the same. The list will be alphabetically sorted.

Output

Your output can contain trailing whitespace per line or in total, but no leading whitespace. A list of strings or similar would also be acceptable.

This is code-golf; the shortest code in each language retains bragging rights. The usual prohibitions against loopholes apply.

Test Cases

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 

Answer 1

Retina 0.8.2, 58 57 bytes

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

Try it online! Link includes one test case. Edit: Saved 1 byte thanks to @FryAmTheEggman pointing out that I overlooked a switch from \b to ^ made possible by the m). Explanation:

m)

Turn on per-line ^ for the whole program.

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

For each word, try to match as much as possible from the beginning of the previous word. Change the match to spaces, except the last character, which becomes a +.

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

Repeatedly replace all spaces immediately above +s or |s with |s.

Answer 2

JavaScript (ES6), 128 bytes

Expects and returns a list of lists of characters.

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

Try it online!

How?

Spaces and +'s can be inserted by walking through the first to the last word in order, but |'s can only be inserted a posteriori once a + has been identified. This could be achieved by doing two distinct passes, but instead we save a pointer to each modified entry in a[~y] so that it can later be updated again within the same map() loop.

In theory, a simpler workaround would be to walk through the words in reverse order and to reverse the output as well at the end of the process. But this is a bit costly in JS and I didn't find a way to get a shorter version with this method.

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

Answer 3

JavaScript (Node.js), 125 122 118 117 bytes

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

Try it online!

• thanks to @Arnauld for tio testing :)

Answer 4

Python, 263 260 bytes

-3 bytes thanks to Jonathan Frech

Code:

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)

Try it Online!

Explanation:

This solution builds a trie out of the input words and recursively parses it into the required output. The a function takes a trie t and a string s and adds x to t. Tries are implemented as nested dictionaries. Each dictionary represents a node in the trie. For example, the dictionary representing the trie generated by the first test case looks like this:

{'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': {}}}}}}

The p function recurses through this structure and generates the string representation of the trie expected by the challenge. The f function takes a bunch of strings as arguments, adds them all to a trie with a, then returns the result of calling p on the trie.

Answer 5

C (gcc), 165 155 bytes

Takes three arguments:

• char** a : an array of null-terminated words
• char* m : an array of the length of each word
• int n : the number of words in the array

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

Try it online!

Answer 6

Perl 6, 149 144 142 bytes

{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("
")}

Try it online!

I'm sure this can be golfed a more, especially as I'm not an expert on regexes. This uses much the same process as Neil's Retina answer.

Answer 7

Ruby, 118 bytes

->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/]&&=?+}}

Try it online!

Accepts an array of strings, outputs by modifying the original input array in-place.

Explanation

The basic string transformation is not too complex, but in order to insert vertical pipes properly, we need to iterate in reverse order, and since reverse method is quite verbose, we'll do it in a trickier way. Here, we use map just to run the loop, leave the first word alone, and then iterate from the end using negative indices:

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

Answer 8

Python 2, 191 bytes

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

Try it online!