Draw a string as a binary tree

Question

The string abcdefghijklmno, with length 2⁴-1, can be formatted as such:

       h
      / \
     /   \
    /     \
   d       l
  / \     / \
 b   f   j   n
a c e g i k m o

Each letter should be kept in the same column, but raised up by the right amount to form the above tree structure. Then, slashes (and backslashes) should be added to link each node to the two below. No slashes should be added between the bottom two rows.

Your challenge is to, given a string of lowercase letters of length 2^k-1, format it as such. This is code-golf, shortest wins!

Testcases

Input	Output
`a`	`a`
`bcd`	`c b d`
`hellowo`	`l / \ e w h l o o`
`abcdefghijklmno`	`h / \ / \ / \ d l / \ / \ b f j n a c e g i k m o`
`thistestcasehasalengththirtyone`	`a / \ / \ / \ / \ / \ / \ / \ t h / \ / \ / \ / \ / \ / \ s e g y / \ / \ / \ / \ h e a a e h r n t i t s c s h s l n t t i t o e`

More interesting is to draw a bunch of strings as a prefix tree — qwr
– qwr, Commented Sep 30, 2024 at 22:48

Neil · Accepted Answer · 2024-10-01 17:54:07Z

Charcoal, 25 bytes

Ｆ²ＦＬθ«Ｊκ⁻¹＆⊕κ±⊕κ¿ι§θκＰ^±ⅉ

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

Ｆ²

Loop twice.

ＦＬθ«

Loop over each input character index.

Ｊκ⁻¹＆⊕κ±⊕κ

Jump to that character's position.

¿ι

On the second pass, ...

§θκ

... output the character.

Ｐ^⁻¹ⅉ

On the first pass, draw / and \ diagonals down to the bottom line.

Due to a bug in Charcoal, replacing ⁻¹ with ± results in an extra trailing line of spaces. This bug also then prevents me from drawing the entire diagram one column to the right, otherwise for 17 bytes:

→ＦＳ«Ｊⅈ±＆ⅈ±ⅈＰ^±⊘ⅉι

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

→

Start with the first character in column 1.

ＦＳ«

Loop over each input character.

Ｊⅈ±＆ⅈ±ⅈ

Jump to that character's position.

Ｐ^±⊘ⅉ

Draw / and \ diagonals halfway to the bottom (without moving the cursor).

ι

Output the current character.

(I do have an experimental branch where this version should print correctly with no padding.)

squareroot12621 · Accepted Answer · 2024-09-29 23:09:35Z

6

Python 3.8 (pre-release), 158 144 143 142 bytes

-14 bytes by Unrelated String.
-2 bytes by emanresu A.

t=lambda s:(r:=len(s)//2)and[l.center(r-~r)for l in[s[r]]+[f'/{" "*i}\\'for i in range(1,r,2)]]+[*map(' '.join,zip(t(s[:r]),t(s[r+1:])))]or[s]

Try it online!

edited Sep 29, 2024 at 23:09

answered Sep 29, 2024 at 21:21

squareroot12621

1,2371 gold badge3 silver badges18 bronze badges

2

\$\begingroup\$ Very nice! 144 by cutting out one of the list comprehensions and reusing your assignment for base case testing. \$\endgroup\$

Unrelated String
– Unrelated String

2024-09-29 21:50:50 +00:00
Commented Sep 29, 2024 at 21:50
2

\$\begingroup\$ -1 with fstrings (edit: I missed unrelatedstring's golf but this still applies) \$\endgroup\$

emanresu A
– emanresu A

2024-09-29 21:54:09 +00:00
Commented Sep 29, 2024 at 21:54
2

\$\begingroup\$ -1 more \$\endgroup\$

emanresu A
– emanresu A

2024-09-29 23:04:55 +00:00
Commented Sep 29, 2024 at 23:04

Add a comment |

Unrelated String · Accepted Answer · 2024-09-30 04:32:07Z

Jelly, 31 28 27 bytes

Jm2BỊḄJ=&ɗⱮJḤṚ|Ɗị"Ø^;;⁶Ʋ€UZ

Try it online!

Yikes... Still feels a little golfable, but it might just be the wrong approach entirely. It seems tantalizingly simple with certain praclang tools, but with so much to juggle, it comes out suprisingly clunky in Jelly!

Returns a list of lines.

Jm2BỊḄJ=&ɗⱮJḤṚ|Ɗ    Build the tree:
Jm2                 For every [1, 3 .. length],
   B                take its arbitrary-length binary representation
     Ḅ              and convert back from binary
    Ị               with all bits set to 1.
Jm2BỊḄ              This creates a bitmask for the period of that column.
         ɗⱮJ        For each [1 .. length],
       =&           is its bitwise AND with each mask equal to
      J             the 1-index of that mask?
            ḤṚ      Double and reverse the comparisons
              |Ɗ    and bitwise OR with the original comparisons.

ị"Ø^;;⁶Ʋ€UZ    Format the tree:
ị              Modular 1-index each row into
 "     Ʋ€      the corresponding character
  Ø^;          appended to "/\"
     ;⁶        with a space appended.
         U     Reverse each row
          Z    and transpose.

l4m2 · Accepted Answer · 2024-09-30 06:38:43Z

2

JavaScript (Node.js), 105 bytes

s=>(g=i=>s[i++*2]?g(i)+s.map(c=>(++j&-j)^i?(x=j&g-1)-i?x+i^g?' ':'\\':'/':(g=2*i,c),j=0).join``+`
`:'')``

Try it online!

Actually I don't understand ...

answered Sep 30, 2024 at 6:38

l4m2

32.5k2 gold badges27 silver badges116 bronze badges

Add a comment |

Antonio Ponce · Accepted Answer · 2024-10-04 15:37:49Z

2

Haskell, 210,196,193,192 bytes

unlines.g
g s|l<-div(length s)2,k<-div l 2=1&s>>i[s!!l](2*l+1)l:zipWith((.(' ':)).(++))(k&map(i"/"l.(l-))[1..]++g(l&s))(k&map(i"\\"l)[0..]++g(drop(l+1)s))
(&)=take
i[c]n p=n&(p&w++c:w)
w=' ':w

-3 bytes thanks to Unrelated String

Try it online!

edited Oct 4, 2024 at 15:37

answered Oct 3, 2024 at 17:52

Antonio Ponce

3111 silver badge5 bronze badges

1

\$\begingroup\$ 193 \$\endgroup\$

Unrelated String
– Unrelated String

2024-10-04 14:27:29 +00:00
Commented Oct 4, 2024 at 14:27

Add a comment |

Kjetil S · Accepted Answer · 2024-10-02 15:11:23Z

1

Perl 5, 152 bytes

sub{map$p=$_||$p=~s| /|/ |gr=~s|\\ ?| \\|gr=~s| \w ?|/ \\|gr,map{$"x($n/2).join($"x$n,@_[grep$_+1==($_^$n),0..$#_]),(0)x(($n>>=1)/2)}0..1.44*log($n=@_)}

Try it online!

answered Oct 2, 2024 at 15:11

Kjetil S

6,15911 silver badges23 bronze badges

Add a comment |

Stack Exchange Network

Draw a string as a binary tree

Testcases

6 Answers 6

Charcoal, 25 bytes

Python 3.8 (pre-release), 158 144 143 142 bytes

Jelly, 31 28 27 bytes

JavaScript (Node.js), 105 bytes

Haskell, 210,196,193,192 bytes

Perl 5, 152 bytes

Your Answer

Hot Network Questions

Draw a string as a binary tree

Testcases

6 Answers 6

Charcoal, 25 bytes

Python 3.8 (pre-release), 158 144 143 142 bytes

Jelly, 31 28 27 bytes

JavaScript (Node.js), 105 bytes

Haskell, 210,196,193,192 bytes

Perl 5, 152 bytes

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions