25
\$\begingroup\$

For example, let's look at the following ASCII art:

/\    - encloses a total of 2 cells - half a cell per slash
\/
 /\   - encloses 4 cells fully and half of 8 cells, for a total of 8 
/  \
\  /
 \/

Your challenge is to write a program that determines (and outputs) the total area enclosed by ASCII art composed only of spaces, slashes and newlines. Slashes won't necessarily be a part of a shape with non-zero area. A point is defined as enclosed iff it is unreachable from any point outside the art's bounding box, if slashes are impassable.

Slashes have zero area and cells are assumed to be \$1\times1\$ squares. /s represent lines that connect the lower left corner with the upper right corner, and \s represent lines the connect the upper left corner with the lower right corner of the corresponding cells. Spaces represent empty space.

Test cases

/\/\ 
\   \
 \/\/

Encloses 3 cells fully and 10 partially, for a total of 8.

///\\\
//  \\
/ /\ \
\ \/ /
\\  //
\\\///

Encloses 12 cells fully (the four innermost slashes have both corresponding half-cells enclosed) and half of 12 cells, for a total of 18.

/\/\
/\/\
/\/\

Encloses 0 cells.

 /\
/  \
\/\/
/\/\
\  /
 \/

Encloses 8 cells fully and 12 cells partially, for a total of 14.

   /\
  /  \
 /  \ \
/   /  \
\ \/  \/
 \ \  /
  \   \
   \/\/

Encloses 25 cells fully and half of 18 cells, for an area of 34.

This is tagged , so the shortest answer wins.

\$\endgroup\$
9
  • \$\begingroup\$ Deleted sandbox post \$\endgroup\$ – the default. Jun 12 '20 at 9:02
  • 2
    \$\begingroup\$ @KrzysztofSzewczyk A possible solution is a graph search, where all cells are split into four quarters (and connections are removed depending on the placement of slashes). The number of quarter-cells not reached is four times the area asked for. \$\endgroup\$ – the default. Jun 12 '20 at 9:22
  • 6
    \$\begingroup\$ I'd like to hear the reasons for the downvote. \$\endgroup\$ – the default. Jun 12 '20 at 9:27
  • 1
    \$\begingroup\$ Do you mean that the input will never be square, or that it will be padded with spaces to an equal length? The latter is okay. \$\endgroup\$ – the default. Jun 12 '20 at 13:06
  • 2
    \$\begingroup\$ Closely related \$\endgroup\$ – Luis Mendo Jun 12 '20 at 15:47
17
\$\begingroup\$

JavaScript (ES6),  228 195 192  185 bytes

Expects a matrix of characters as input.

This can be quite slow on some inputs, such as the last test case.

m=>m.map((r,Y)=>r.map((_,X)=>n+=(g=(x,y,z,q=z&2,r=m[y],v=r&&r[x])=>v?(v|=64+(v>{})+!++v)^(r[x]|=v|4<<z)?g(x+--q*~z%2,y-q*z%2,z^2)&g(x,y,v&3?z^=v&2|1:z+1&3)|!(r[x]=v):1:0)(X,Y,0)),n=0)|n

Try it online!

How?

Grid encoding

We divide each cell into 4 areas as follows:

areas

The current position is encoded as \$(x,y,z)\$, where \$(x,y)\$ is the position in the matrix and \$z\$ is the ID of the area.

The characters in the original matrix are converted on the fly to 7-bit integers as they are visited:

+---------> a marker to tell that this tile has been converted (always 1)
|      +--> 4 bits to tell whether a given area has been visited
|      |
|      |      +-----> set to 1 if the cell contains an anti-slash
|  ____|____  |  +--> set to 1 of the cell contains a slash
| /         \ |  |
1 z3 z2 z1 z0 AS S

The conversion is done with:

v |= 64 + (v > {}) + !++v

The expression (v > {}) is only true for '\' and !++v is true for either '/' or '\'. If v is already an integer, it is left unchanged.

Algorithm

Evaluating the area enclosed by slashes is equivalent to counting the number of cells from which we can't escape from the grid, starting from a given area ID. We arbitrary start from area #0, but that would work with any of them as long as it is consistent.

We iterate on all possible starting points and process some kind of flood-filling that takes the area IDs into account.

For each visited cell, we try to move to an adjacent cell (left figure) and to another area within the same cell (right figure).

moves

The recursion stops either when we escape the grid or when we get trapped.

\$\endgroup\$
13
\$\begingroup\$

J, 108 95 93 91 83 80 77 bytes

-13 due using 4x4 instead of 3x3 masks

-7 thanks to Jonah

-2 5 thanks to Bubbler

This expands the ASCII to a 4 times as big bit map that gets searched in for enclosed spaces. Maybe you can do the calculations on the original map, but at least this approach works for now. :-)

[:+/@,12%~1=2|.@|:@(2(>.*])/\,)^:4^:_[:,"_1/^:2((+./~#:9),-.(,:|.)=i.4){~' \'i.]

Try it online!

How it works

Ungolfed:

12 +/@,@:%~
1=
((,-)=i.2) (] * >./@:(|.!.2))^:_
((+./~#:9) , -. (,:|.)=i.4) ,"_1/^:2@:{~ ' \/'i. ]

Build up 3x4x4 masks, where 0 is a wall:

((+./~#:9) , -. (,:|.)=i.4)

1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

1 1 1 0
1 1 0 1
1 0 1 1
0 1 1 1

That expands each character ' \/'. So from a 3x4 drawing we get a 12x16 bit mask. The empty space has 12 1's (while still allowing traversal) and each side of a slash has 6.

,"_1/^:2@:{~' \/'i.]

Then shift the matrix in the four directions by rotating the matrix. At the borders 2 gets shifted in. The resulting matrices are added up together by taking the highest value (so 2 expands), while 0 in the matrix deletes (so borders blocks expansions). We do this until the result does not change (…)^:_.

2|.@|:@(2(>.*])/\,)^:4^:_

We are interested in the 1's that still stand. And because of our bit masks, we can simply divide by 12 of the total sum of all 1's to get the result.

12 +/@,@:%~
\$\endgroup\$
7
  • \$\begingroup\$ I do not know J at all, so the only characters I understand here are digits, but is the first mask supposed to be all walls? \$\endgroup\$ – the default. Jun 12 '20 at 13:17
  • 1
    \$\begingroup\$ Really like this approach, nice work. Small improvements: 86 bytes \$\endgroup\$ – Jonah Jun 13 '20 at 3:09
  • 1
    \$\begingroup\$ 84 bytes \$\endgroup\$ – Jonah Jun 13 '20 at 3:14
  • 1
    \$\begingroup\$ 81 bytes by porting my APL answer at some parts. \$\endgroup\$ – Bubbler Jun 15 '20 at 2:42
  • 1
    \$\begingroup\$ 77 bytes. \$\endgroup\$ – Bubbler Jun 16 '20 at 23:38
8
\$\begingroup\$

Charcoal, 114 100 96 91 bytes

WS⊞υιFυ«J⁰⁺³ⅉFι«M³→≡κ/P/²\P\²»»≔⁺²Lθθ≔⁺²LυυJ±¹±¹B׳θ׳υψ¤#FυFθ«J׳κ׳ιPX²»≔I÷⁻×⊗υ⊗θ№KA#⁴θ⎚θ

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

WS⊞υι

Input the art.

Fυ«J⁰⁺³ⅉ

Loop over each row of the art.

Fι«M³→

Loop over each cell of the art.

≡κ/P/²\P\²»»

Output it at three times its original size.

≔⁺²Lθθ≔⁺²Lυυ

Adjust the size of the art for a notional 1-square border on each side.

J±¹±¹B׳θ׳υψ

Draw a notional box around the notional border. This allows the border to be filled without actually having drawn anything.

¤#

Fill the exterior of the art with #. Sadly Charcoal doesn't support multiline fill patterns. (Its fill was designed for the challenge, Bake a slice of Pi.)

FυFθ«J׳κ׳ιPX²»

Draw Xs at every position (including the notional border), overwriting all the existing spaces and slashes. This means that each square now has only four #s (or fewer if it didn't get completely filled in).

≔I÷⁻×⊗υ⊗θ№KA#⁴θ

Calculate the number of #s that there would have been had the art originally been empty (including the border), subtract the number of #s actually filled, then divide by 4.

⎚θ

Clear the canvas and output the result.

Alternative solution, based on @xash's idea of 4×4 masks, also 91 bytes:

≔⪫  ⭆θ θ⊞υθWS⊞υ⪫  ι⊞υθB×⁴Lθ×⁴LυψFLυFLθ«J×⁴κ×⁴ι≡§§υικ «↘UR²»/«↓↓↓↗⁴»↘⁴»↖¤#≔I⁻×LυLθ÷№KA#¹²θ⎚θ

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

≔⪫  ⭆θ θ⊞υθ

Generate a padding row.

WS⊞υ⪫  ι

Input the art padded on both sides.

⊞υθ

Add padding to the bottom of the art.

B×⁴Lθ×⁴Lυψ

Draw a notional box around the padded art. This allows the padding to be filled without actually having drawn anything.

FLυFLθ«

Loop over each cell of the art.

J×⁴κ×⁴ι

Jump to the cell.

≡§§υικ «↘UR²»/«↓↓↓↗⁴»↘⁴

Draw the cell at four times size, except that space becomes a dot. This means that it takes up the same amount of space as a / or \ but without impeding the flood fill.

»↖¤#

Move the cursor off the last dot so that the exterior of the art can be flood filled with #.

≔I⁻×LυLθ÷№KA#¹²θ

Divide the number of #s by 12, and subtract that from the padded size of the art.

⎚θ

Clear the canvas and output the result.

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

APL (Dyalog Unicode), 67 bytes

12÷⍨≢⍸1=(⍉∘⌽2(⌈∧⊢)/2,⊢)⍣4⍣≡⊃⍪/,/({(∘.∨⍨1=3|⍳4)(⌽⍵)⍵}∘.≠⍨⍳4)[' /'⍳⎕]

Try it online!

A port of xash's excellent J answer.

How it works

12÷⍨≢⍸1=(⍉∘⌽2(⌈∧⊢)/2,⊢)⍣4⍣≡⊃⍪/,/({(∘.∨⍨1=3|⍳4)(⌽⍵)⍵}∘.≠⍨⍳4)[' /'⍳⎕]

⊃⍪/,/({(∘.∨⍨1=3|⍳4)(⌽⍵)⍵}∘.≠⍨⍳4)[' /'⍳⎕]  ⍝ Preprocessing
     (                         )          ⍝ Create 3 bitmasks
                         ∘.≠⍨⍳4           ⍝ Negated identity matrix of size 4
      {            (⌽⍵)⍵}                 ⍝ Strand with its reflection, and
       (∘.∨⍨1=3|⍳4)                       ⍝ Self OR outer product of 1 0 0 1
                                [' /'⍳⎕]  ⍝ Convert three chars ' /\' to respective bitmasks
   ,/  ⍝ Join horizontally adjacent arrays horizontally
 ⍪/    ⍝ and vertically adjacent ones vertically
⊃      ⍝ Remove nesting

12÷⍨≢⍸1=(⍉∘⌽2(⌈∧⊢)/2,⊢)⍣4⍣≡  ⍝ Flood fill from the outside, and find the answer
        (          2,⊢)      ⍝ Prepend 2 on each row
            2(⌈∧⊢)/          ⍝ Pairwise reduce: (x,y)→lcm(max(x,y),y)
                             ⍝ Effectively, if left is 2 and right is nonzero, make it 2;
                             ⍝ keep the right one otherwise
         ⍉∘⌽                 ⍝ Rotate the matrix 90 degrees
                       ⍣4⍣≡  ⍝ Repeat on the four sides, until the flood fill is complete
12÷⍨≢⍸1=  ⍝  Count ones, and divide by 12
\$\endgroup\$
4
\$\begingroup\$

MATL, 51 50 49 bytes

Ji^G8\*TTYa3XytPJ*-X*Xj~4&1ZIt1)0hm3thZCS6:Y)~Yms

Input is a char matrix, with ; as row separator.

Try it online! Or verify all test cases

Explanation

The approach is similar to that used in my answer to this other challenge.

J        % Push imaginary unit, j
i        % Take input: char matrix
^        % Element-wise power of j raised to the code points of the input.
         % This gives -j, 1, 1 for '/', '\' and ' ' respectively
G        % Push input again
8\       % Modulo 8, element-wise. This gives 7, 4 0 for '/', '\' and ' '
         % respectively. The specific values do not matter; it only matters
         % that ' ' gives 0 and the other chars give nonzero
*        % Multiply. Now we have a matrix that contains -7, 4 and 0 for
         % '/', '\' and ' ' (*)
TTYa     % Pad array with a 2D frame of zeros of length 1 
3Xy      % Push 3×3 identity matrix
tP       % Duplicate, flip vertically
J*-      % Multiply by imaginary unit and subtract. This gives the matrix
         % [1 0 -j; 0 1-j 0; -j 0 1] (**)
X*       % Kronecker product. This replaces each entry of (*) by its
         % product with (**)
Xj       % Real part. We now have a matrix where '/', '\' and ' ' have been
         % transformed into [0 0 -7; 0 -7 0; -7 0 0], [4 0 0; 0 4 0; 0 0 4]
         % and [0 0 0; 0 0 0; 0 0 0] respectively
~        % Negate. We now have a matrix with "pixelated" versions of the
         % input chars at 3 times greater resolution, with an empty frame.
         % Pixels equal to 1 are empty space, and pixels equal to 0 are
         % borders corresponding to the original slash chars
4&1ZI    % Label connected components based on 4-neighbourhood. This
         % transformes the pixels which contained 1 into different numbers
         % We are interested in the area not occupied by the outer
         % connected component and the borders
t1)      % Duplicate. Value of the upper-left corner. This gives the label
         % of the outer component
0h       % Append 0. This is the value of the borders
m        % Ismember: this gives true for pixels that are outer component
         % or border. Each original cell corresponds to a 3×3 block of
         % pixels. Each of those blocks will contain 9 zeros for cells
         % that were fully enclosed; 6 zeros for cells with its two halves
         % enclodes but with a border in between; 3 zeros for cells with
         % one of its halves enclosed, and 0 zeros for cells not enclosed
3thZC    % Matrix where each distinct 3×3 block has been arranged into 
         % a column of length 9
S        % Sort. This sends 1 to the bottom and 0 to the top
6:Y)     % Keep the first 6 rows. This effectively transforms columns with
         % 9 zeros into columns of 6 zeros. So now we have 0, 3 or 6 zeros
         % for not covered, partically covered or fully covered cells
~        % Logical negation
Ym       % Mean of each column. This transforms the 0, 3, and 6 numbers
         % referred to above into 0, 0.5 or 1
s        % Sum. Implicit display
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for linking to that other challenge; comparing my answers, I found that I'd already used at least one of my golfs from the other answer, but there was another golf that I hadn't thought of. \$\endgroup\$ – Neil Jun 12 '20 at 23:33

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.