Skip to main content
Commonmark migration
Source Link

#JavaScript (ES6),  228 195 192  185 bytes

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?

How?

###Grid encoding

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

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.

#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.

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.

saved 7 bytes
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650

#JavaScript (ES6),  228 195 192  192185 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,z^=v&3?v&3|1:v>>3-z&4v&3?1z^=v&2|1:3z+1&3)|!(r[x]=v):1:0)(X,Y,0)),n=0)|n

Try it online!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).

movesmoves

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

#JavaScript (ES6),  228 195  192 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,z^=v&3?v&3|1:v>>3-z&4?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.

#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.

saved 3 bytes
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650

#JavaScript (ES6),  228 195  195192 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,z^=v&3?v&1||3v&3|1:v>>(z^3)&4v>>3-z&4?1:3)|!(r[x]=v):1:0)(X,Y,0)),n=0)|n

Try it online!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.

#JavaScript (ES6),  228  195 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,z^=v&3?v&1||3:v>>(z^3)&4?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.

#JavaScript (ES6),  228 195  192 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,z^=v&3?v&3|1:v>>3-z&4?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.

fixed a bug
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
saved 3 bytes
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
added an explanation
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
saved 3 bytes
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
saved 2 bytes
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
saved 2 bytes
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
saved 7 bytes
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
saved 31 bytes / removed the original version
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
saved 4 bytes
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
added a shorter version
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
saved 3 bytes
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading
Source Link
Arnauld
  • 197.7k
  • 20
  • 179
  • 650
Loading