# Make an alphabeTrie

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

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 ; 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
• What about the case where I have the word ball after balloon. What output should we expect? – Rushabh Mehta Aug 13 at 20:05
• @RushabhMehta I'm guessing you would just have a + under the first o, but I didn't write the challenge so I'm not certain. – Theo Aug 13 at 20:12
• @RushabhMehta The words are alphabetically sorted, so this won't happen. – Neil Aug 13 at 20:14
• @Neil Oh good point – Rushabh Mehta Aug 13 at 20:18
• The words in the input will be made up of only alphanumerics: does that really include digits, or did you mean alphabetic? – Arnauld Aug 14 at 1:40

# 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.

• @FryAmTheEggman Indeed, I added the m) specifically to be able to do that, so I'm annoyed that I missed an instance. – Neil Aug 15 at 23:41
• Ugh, why do I even bother replying to comments if people are just going to delete them... – Neil Aug 16 at 8:30

# 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
• would you look at my solution, i came up with it myself but it reminds of your solution. so if its too close you can submit it as yours (or not) and ill delete it :) – DanielIndie Aug 17 at 16:22
• @DanielIndie No worries. It's different enough. – Arnauld Aug 20 at 11:00

# JavaScript (Node.js), 125122118 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 :)

# 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.

# 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!

• Some quick wins – Arnauld Aug 14 at 10:08
• @Arnauld Of course! Although isn't ++i<n&j<m[i]&a[i--] undefined behavior? Can I rely on gcc evaluating it left to right? – Curtis Bechtel Aug 14 at 13:31
• It's very likely to be undefined behavior. But we define languages by their implementation, so as long as it works consistently with this version of gcc, I think that's fine. – Arnauld Aug 14 at 13:34

# 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.

# 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!

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