# Create Word Lightning

Sandbox

Inspired by a Codingame challenge I tried (and failed at) about a month ago.

Given a binary tree of words, say:

             HELLO
/     \
WORLD     EATING
/         /   \
ARCH     IDAHO   GUARD
/
DOOZY
/
ZEPPELIN
/    \
POWER   LIGHT

1. Take the root of the tree.
2. Print it in the South direction.
H
E
L
L
O

1. For each of the tree's children, given iteration index i:
1. Find the first character in the child that it has in common with the root. If there are multiple occurrences of that character in the root, choose the first occurrence as the join point.
2. The drawn root word will have to intersect the child at this point.
3. Draw the left node down to the left, and the right node down to the right.
   H
E
LA
LWT
O  I
R    N
L      G
D

1. Now, for each of the diagonal words' children, do the same, except always print downward.
   H
E
LA
LWT
AO  I
R   DN
LC   A G
D H   H U
O A
R
D

1. Go back to step3 and perform the steps again until the tree is complete.
   H
E
LA
LWT
AO  I
R   DN
LC   A G
D H   H U
O A
R
D
O
O
Z
YE
P
OP
W E
E  L
R   II
N G
H
T


## Clarifications

• No two child words will have the same first common letter.
• Words from different subtrees will never intersect.
• Input will always be a valid binary tree.
• Each parent will always have a common character with both of its children.
• Trees can be taken in any suitable and reasonable format for your language.
• Leading and trailing whitespace is allowed, so long as the structure of the lightning is as shown.
• All words will be given in the same case.

# Testcases

PROGRAMMING
|
CHALLENGES
|         \
PUZZLES    CODING

       P
R
PO
UG C
ZRHO
ZA D
LM I
LEM N
E SI G
N   N
G    G
E
S



DIGERIDOO
|        \
GIRDLE    ORNATE
|         |     \
EXQUISITE ROLL   TALONS
|       \
QUEEN    TAPESTRY
|       \
PASTE    YELLOW
|
ERROR

         D
I
G
IE
R R
D  I
L   D
E    O
X    OR
Q     ON
UU     L A
E I     L  T
E  S        AE
N   I        L
T        O
EA       N
P P    S
EA
S
TT
E R
R   Y
R    E
O     L
R      L
O
W


• Can you add a few more test cases? Jun 19, 2021 at 4:32
• sure, will add in a bit(these take a while to make manually) Jun 19, 2021 at 4:35
• What if the parent word has the common letter multiple times? e.g. in case of PROGRAMMING and GOLF, PROGRAMMING has two Gs!
– FZs
Jun 19, 2021 at 5:28
• choose the first occurrence of the common letter. Jun 19, 2021 at 6:13
• What if there are two common letters? e.g. PROGRAMMING and CHALLENGES have both G and A in common.
– Neil
Jun 19, 2021 at 9:10

# Charcoal, 88 bytes

↓§θ⁰⊞υ⁺Ｅ³¦⁰θＦυ«≔¬§ι⁰ηＦΦι›λ³«≔§κ⁰ζ≔§Φζ№§ι³λ⁰εＪ§ι¹§ι²Ｍ⌕§ι³ε✳⁻⁶§ι⁰Ｍ⌕ζε✳⁻²η⊞υ⁺⟦ηⅈⅉ⟧κ✳⁻⁶ηζ≦±η


Try it online! Link is to verbose version of code. Explanation:

↓§θ⁰


Print the first word vertically.

⊞υ⁺Ｅ³¦⁰θＦυ«


Start a breadth-first traversal of the tree, but prefixing three status variables to each entry for the coordinates and the direction.

≔¬§ι⁰η


Get the direction of the previously printed word and flip it to 0 (which will become downwards) if it was non-zero or 1 (which will become down left) if it was zero.

ＦΦι›λ³«


Loop over any child nodes.

≔§κ⁰ζ


Get the current node's word.

≔§Φζ№§ι³λ⁰ε


Find the first letter in its word that's shared with its parent's word.

Ｊ§ι¹§ι²Ｍ⌕§ι³ε✳⁻⁶§ι⁰Ｍ⌕ζε✳⁻²η


Jump to the parent's start, then move to the parent's shared letter, then work back to where this branch's word needs to start.

⊞υ⁺⟦ηⅈⅉ⟧κ


Concatenate this word's position and direction with the node and push that to the list of nodes to traverse.

✳⁻⁶ηζ


Print the node's word in the appropriate direction.

≦±η


Flip the direction in case this word was printed down left and there's a sibling node still to print.