11
\$\begingroup\$

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


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

Charcoal, 88 bytes

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

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

↓§θ⁰

Print the first word vertically.

⊞υ⁺E³¦⁰θFυ«

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.

FΦι›λ³«

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.

J§ι¹§ι²M⌕§ι³ε✳⁻⁶§ι⁰M⌕ζε✳⁻²η

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.