9
\$\begingroup\$

Objective

Given a matrix of connected box drawing characters, count its genus, the number of plane sections it encloses.

Valid input

The box drawing characters are ─│┌┐└┘├┤┬┴┼╴╵╶╷ (U+2500 U+2502 U+250C U+2510 U+2514 U+2518 U+251C U+2524 U+252C U+2534 U+253C U+2574 U+2575 U+2576 U+2577). The matrix shall contain these characters only, along with unique "nothing" value that represents a blank.

The input may also be a string with box drawing characters, whitespaces, and line feeds. You cannot mix different types of whitespaces, or different types of line feeds. Trailing whitespaces and line feeds are permitted.

Rule

Invalid input falls in don't care situation. In particular, you don't need to handle any input having multiple connected components, e.g.

# this
┌─┐┌─┐
└─┘└─┘
# or this
┌───┐
│┌─┐│
│└─┘│
└───┘

Examples

For font issues, every example is presented using normal spaces (U+0020) once and ideographic spaces (U+3000) once.

Genus 0

# Using U+0020 space
┤ ╷
└─┘

┌┼┐
 ─┴

# Using U+3000 space
┤ ╷
└─┘

┌┼┐
 ─┴

Genus 1

# Using U+0020 space
┌─┬
│ │
└─┘

┼┬─┬
╵│ │
└┴─┘

# Using U+3000 space
┌─┬
│ │
└─┘

┼┬─┬
╵│ │
└┴─┘

Genus 2

# Using U+0020 space
┼┼┼┼
 ┼┼┼

# Using U+3000 space
┼┼┼┼
 ┼┼┼
\$\endgroup\$
8
  • 1
    \$\begingroup\$ How does nesting work? For instance, this example. What is its genus? 1? 2? 3? \$\endgroup\$ – Abigail Jul 16 '20 at 23:44
  • \$\begingroup\$ @Abigail It is not connected, so it falls in don't care situation. \$\endgroup\$ – Dannyu NDos Jul 16 '20 at 23:45
  • 1
    \$\begingroup\$ You write, "Given a matrix of connected box drawing characters". What does "connected" mean in this context? Half the examples aren't what I would call "connected box drawing characters". \$\endgroup\$ – Abigail Jul 16 '20 at 23:46
  • 1
    \$\begingroup\$ If the full-width space (U+3000) is considered the same as half-width one (U+0020), why should we include it in the question? I cannot see any benefit from it. \$\endgroup\$ – tsh Jul 17 '20 at 2:00
  • 1
    \$\begingroup\$ @tsh If you are referring the examples, it's my concern about rendering. \$\endgroup\$ – Dannyu NDos Jul 17 '20 at 2:03
6
\$\begingroup\$

APL (Dyalog Extended), 73 bytes

1-1⊥∘(∊∨/¨⍮2(-⊃⍤∧∘⌽/⍮(3⊃∧∘⌽)⌿)⊢)(⊂4⍴2)⊤¨(9467+⎕AV⍳'ð{dòlxõ _0h8p∆')⍳⎕UCS

Try it online!

Over half of the bytes were used in converting the char matrix into an easier-to-use format. Basically, converts each box-drawing char into [right, up, down, left], counts non-blanks and joints, and computes 1 - non-blanks + joints.

This works because of Euler characteristic V - E + F = 1 (not counting the surrounding area as a face), thanks to the assumption that the entire figure is connected. If we count any segment starting from the center to some boundary as an edge (and the respective endpoints as vertices), every non-blank char has V - E = 1, but the V in the entire shape is reduced by the number of joints. Plugging into the rearranged equation F = 1 - V + E gives the above formula 1 - non-blanks + joints.

\$\endgroup\$
5
\$\begingroup\$

Retina, 131 bytes

T`─┐┬╴┼┤┴┘│╵└├┌╶╷`L
(?=(.)*[BCEFILMO].*¶(?>(?<-1>.)*)[E-L])
-
(?=[ACEGK-N]-?[A-H])|^
-
+`-\s*\w

C`-

Try it online!

TIO counts the box drawing characters as only one byte even though they are not ASCII (the Retina code page).

How?

This uses a rearranged Euler characterstic F=1+E-V to find the number of faces under the assumption that there is only one connected component.

The number of vertices, V, is the same as the number of box characters.

There is +1 edge for every horizontally adjacent pair of box characters where the first has a right edge and the second has a left edge. There is +1 edge for every vertically adjacent pair of box characters where the first has a down edge and the second has a up edge. This is harder to express in regex, so I borrowed the method of standard vertical matching to deal with vertical edges.

# Translate each of the box characters into letters to avoid repeating them
# We do this smartly:
# ─┐┬╴┼┤┴┘        correspond to A-H and all have a left edge
#     ┼┤┴┘│╵└├    correspond to E-L and all have an up edge
#           └├┌╶  correspond to K-N and all have a right edge
T`─┐┬╴┼┤┴┘│╵└├┌╶╷`L
# Prepend a '-' to the first character of a vertically adjacent pair with (down edge, up edge)
# Each '-' will represent one edge
(?=(.)*[BCEFILMO].*¶(?>(?<-1>.)*)[E-L])
-
# Prepend a '-' to the first character of a horizontally adjacent pair with (left edge, right edge)
# Simply pass over '-' from the previous step using -?
# |^: also prepend an extra '-', which counts as an extra edge, to the beginning of the whole string for the +1
(?=[ACEGK-N]-?[A-H])|^
-
# Now there is a - for each edge and a capital letter for each vertex, with some whitespace
# Compute #(edges) - #(capital letters)
# Until the output is constant:
# Replace an edge and a capital letter with the empty string (`\s*` to pass over whitespace)
+`-\s*\w

# Count the number of `-`s
C`-
\$\endgroup\$
2
  • \$\begingroup\$ The last stage defaults to being a Count stage, so you can save 2 bytes immediately. \$\endgroup\$ – Neil Jul 17 '20 at 9:08
  • \$\begingroup\$ I was able to rearrange the characters to save another byte: Try it online! however I think it's possible that you could probably net a bigger saving using T`─-┼╴-╷`5-u as your first line. \$\endgroup\$ – Neil Jul 17 '20 at 10:17
2
\$\begingroup\$

Charcoal, 100 bytes

WS⊞υιB׳⊕Lθ׳⊕LυψFυ«⸿⸿⸿Fι«M³→F⁴¿&X²λ⍘§”E←T¹÷S1²m[ω→℅P”﹪℅κ⊕⊘φφP✳⊗λ²»»≔⁰ηFLθFLυ«J׳ι׳κ↘≧⁺¬℅KKη¤#»⎚I⊖η

Try it online! Link is to verbose version of code. Takes input as a newline-terminated rectangular character array. While I could have written a version that uses the Euler characteristic, I felt that I should really write a version using all of Charcoal's power to calculate the number of regions in any shape. Explanation:

WS⊞υι

Input the shape.

B׳⊕Lθ׳⊕Lυψ

Draw an empty box large enough to completely enclose the shape at three times scale.

Fυ«⸿⸿⸿Fι«M³→

Loop over each character of the input, positioning the cursor at the appropriate position.

F⁴¿&X²λ⍘§”E←T¹÷S1²m[ω→℅P”﹪℅κ⊕⊘φφP✳⊗λ²

Loop over each direction, looking up the box lines based on taking the ordinal of the character modulo 501 and 23 (the latter automatically via Charcoal's cyclic indexing) in a table of hex digits (and gs for filler), drawing a line for each matching bit in the digit, thus drawing the original shape at triple size.

»»≔⁰η

Start with no regions.

FLθFLυ«

Loop over each character.

J׳ι׳κ↘

Jump to the upper right of the character.

≧⁺¬℅KKη

Increment the region count if it's empty.

¤#

And then try to fill it anyway.

»⎚I⊖η

Print one less then the resulting count (since this procedure counts the outside too).

\$\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.