Slash the matrix

30

6

You are given a matrix of forward and back slashes, for instance:

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

A slash cuts along the diagonal of its cell corner-to-corner, splitting it in two pieces. Pieces from adjacent (horizontally or vertically) cells are glued together. Your task is to count the number of resulting pieces. For the same example, the pieces are easier to see in this illustration - 8 of them:

enter image description here

Write a function or a complete program. Input is a non-empty matrix in any convenient form. You may choose any pair of values (characters or numbers) to represent / and \; in the tests below we use 0=/ and 1=\. Loopholes forbidden. Shortest wins.

in:
[[0,0,1,1],
 [1,0,0,1],
 [0,0,1,0]]
out:
8

in:
[[1]]
out:
2

in:
[[1,0],
 [1,1],
 [0,1],
 [0,0]]
out:
6

in:
[[1,0,1,1,0,1,0,0,0,1,1,1],
 [1,0,1,0,1,1,1,1,1,1,1,0],
 [1,1,1,0,1,1,0,1,1,1,1,0],
 [0,1,0,1,0,1,0,0,1,0,1,1],
 [1,1,1,1,0,0,1,1,1,0,0,1]]
out:
19

in:
[[1,0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,1],
 [1,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,1],
 [1,0,0,1,0,1,0,1,0,0,1,0,1,1,1,1,1],
 [1,0,0,1,1,1,0,0,1,0,0,1,0,1,1,1,1],
 [0,1,0,0,0,0,1,0,1,0,0,1,0,1,1,1,1],
 [0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,1,0],
 [0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,1,0]]
out:
27

in:
[[0,1,1,1,1,1,1,1,0,0,1,0,1,0,0,0,0],
 [1,1,1,0,0,0,1,1,1,1,1,0,1,1,0,1,0],
 [1,0,0,1,1,1,0,0,0,1,0,1,0,0,1,1,1],
 [0,0,0,1,1,0,1,0,0,0,1,1,0,1,1,1,0],
 [1,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,0],
 [0,1,0,1,0,0,0,1,0,1,0,1,0,1,1,0,0],
 [0,1,1,1,0,0,1,0,1,0,0,0,0,1,1,1,1]]
out:
32

ngn

Posted 2019-10-28T13:31:34.743

Reputation: 11 449

Answers

28

MATL, 21 bytes

3XytPJ*-X*Xj~4&1ZIunq

The input is a matrix with 1 for \ and j (imaginary unit) for /.

Try it online! Or verify all test cases.

With some extra code, you can see the different pieces in random colours. Or increase the resolution for a better looking result.

Explanation

Consider input [1,j; 1,1; j,1; j,j] as an example. This corresponds to

\/
\\
/\
//

3Xy creates a 3×3 identity matrix:

1 0 0
0 1 0
0 0 1

tP pushes a copy of this matrix and flips it vertically. J* multiplies each entry by the imaginary unit, to give

0 0 j
0 j 0
j 0 0

- subtracts the two matrices:

 1     0    -j
 0   1-j     0
 -j    0     1

X* takes the input matrix implicitly and computes the Kronecker product. This replaces each entry in the input matrix by its product with the above 3×3 matrix:

 1    0   -j    j    0    1
 0  1-j    0    0  1+j    0
-j    0    1    1    0    j
 1    0   -j    1    0   -j
 0  1-j    0    0  1-j    0
-j    0    1   -j    0    1
 j    0    1    1    0   -j
 0  1+j    0    0  1-j    0
 1    0    j   -j    0    1
 j    0    1    j    0    1
 0  1+j    0    0  1+j    0
 1    0    j    1    0    j

Xj takes the real part:

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

Note how the above matrix is a "pixelated" version of

\/
\\
/\
//

~ applies logical negation, that is, swaps 0 and 1:

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

4&1ZI specifies 4-connectivity, and finds connected components considering 1 as foreground and 0 as background. The result is a matrix of labelled connected components, where each original 1 is replaced by an integer label:

0 3 3 3 3 0
1 0 3 3 0 5
1 1 0 0 5 5
0 1 1 0 5 5
2 0 1 1 0 5
2 2 0 1 1 0
2 2 0 0 1 1
2 0 4 4 0 1
0 4 4 4 4 0
4 4 0 4 4 0
4 0 4 4 0 6
0 4 4 0 6 6

unq computes the number of unique elements and subtracts 1. This gives the number of components, which is implicitly displayed.

Luis Mendo

Posted 2019-10-28T13:31:34.743

Reputation: 87 464

would it help if you chose [1,0,0; 0,1,0; 0,0,1] and [0,0,j; 0,j,0; j,0,0] as the two values for \ and /? – ngn – 2019-10-28T19:46:32.433

4The essential idea of resizing the slashes so that connected components work naturally is fantastic. – Jonah – 2019-10-28T20:07:11.027

3@ngn I assumed that wasn't allowed. Yes, it would help, but allowing that would make the challenge less interesting in my opinion. (Also my answer would be less interesting, as Jonah's eloquent comment illustrates). By that rule, using [1,0,0; 0,1,0; 0,0,1] and [0,0,1; 0,1,0; 1,0,0] would probably be valid too?, and then the challenge would just be "find connected components", which is less interesting and possibly a dupe. So my recommendation, if I may say so, is to require two different characters or numbers as inputs. That's how I understood "Given a matrix of forward and back slashes" – Luis Mendo – 2019-10-28T21:00:33.713

2@LuisMendo tbh, when i designed the challenge i didn't anticipate that reduction to connected components could be done so easily - that's the beauty of your solution. i'll amend it as you recommend. – ngn – 2019-10-28T21:06:36.143

4

MSX-BASIC, 226 199 bytes

1SCREEN2:READC,L:W=256/C:H=192/L:FORJ=1TOL:FORI=1TOC:A=H:B=H:READD:IFDTHENA=0:B=-H
2LINE(I*W,J*H-A)-STEP(-W,B):NEXTI,J:FORY=0TO191:FORX=0TO255:IFPOINT(X,Y)=4THENR=R+1:PAINT(X,Y)
3NEXTX,Y:SCREEN0:?R

This script draw slashes on a whole screen and use PAINT operator to count closed areas.

The MSX-BASIC script in process

Result

To test:

  • copy to clipboard the script with test cases data (see below)
  • open online emulator https://webmsx.org/
  • press Alt-V and Ctrl+V to past test script into MSX
  • press Enter and F5 to run test script
  • wait a some time to see a result (press Shift-Alt-T to switch in CPU Turbo 8X mode to save your time)
1SCREEN2:READC,L:W=256/C:H=192/L:FORJ=1TOL:FORI=1TOC:A=H:B=H:READD:IFDTHENA=0:B=-H
2LINE(I*W,J*H-A)-STEP(-W,B):NEXTI,J:FORY=0TO191:FORX=0TO255:IFPOINT(X,Y)=4THENR=R+1:PAINT(X,Y)
3NEXTX,Y:SCREEN0:?R
10 ' this and below lines are not counted
20 ' the script runs first uncommented test case.
30 ' comment unnecessary test cases
100 '
110 'test case 1: expected output=8
120 'DATA 4,3
130 'DATA 0,0,1,1,1,0,0,1,0,0,1,0
200 '
210 'test case 2: expected output=2
220 'DATA 1,1
230 'DATA 1
300 '
310 'test case 3: expected output=6
320 'DATA 2,4
330 'DATA 1,0,1,1,0,1,0,0
400 '
410 'test case 4: expected output=19
420 'DATA 12,5
430 'DATA 1,0,1,1,0,1,0,0,0,1,1,1
440 'DATA 1,0,1,0,1,1,1,1,1,1,1,0
450 'DATA 1,1,1,0,1,1,0,1,1,1,1,0
460 'DATA 0,1,0,1,0,1,0,0,1,0,1,1
470 'DATA 1,1,1,1,0,0,1,1,1,0,0,1
500 '
510 'test case 5: expected output=27
520 DATA 17,7
530 DATA 1,0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,1
540 DATA 1,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,1
550 DATA 1,0,0,1,0,1,0,1,0,0,1,0,1,1,1,1,1
560 DATA 1,0,0,1,1,1,0,0,1,0,0,1,0,1,1,1,1
570 DATA 0,1,0,0,0,0,1,0,1,0,0,1,0,1,1,1,1
580 DATA 0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,1,0
590 DATA 0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,1,0
600 '
610 'test case 5: expected output=32
620 DATA 17, 7
630 DATA 0,1,1,1,1,1,1,1,0,0,1,0,1,0,0,0,0
640 DATA 1,1,1,0,0,0,1,1,1,1,1,0,1,1,0,1,0
650 DATA 1,0,0,1,1,1,0,0,0,1,0,1,0,0,1,1,1
660 DATA 0,0,0,1,1,0,1,0,0,0,1,1,0,1,1,1,0
670 DATA 1,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,0
680 DATA 0,1,0,1,0,0,0,1,0,1,0,1,0,1,1,0,0
690 DATA 0,1,1,1,0,0,1,0,1,0,0,0,0,1,1,1,1

mazzy

Posted 2019-10-28T13:31:34.743

Reputation: 4 832

1Wait a second... this isn't powershell – Veskah – 2019-11-01T18:32:07.280

1oops! ¯\(ツ) – mazzy – 2019-11-01T18:36:48.560

3

JavaScript (ES6),  175  174 bytes

This is probably overcomplicated.

a=>a.map((r,y)=>r.map((v,x)=>[2,4].map(s=>v&s||(n++,g=(x,y,s,i,v=(r=a[y])&&r[x])=>!(v&(s^=i%2==v%2&&6))/v&&g(x+1-(r[x]|=s,s&2),y++,s^6)|g(x,y-=v%2*2^s&2,s,v))(x,y,s))),n=0)|n

Try it online!

Arnauld

Posted 2019-10-28T13:31:34.743

Reputation: 111 334

2

Charcoal, 70 bytes

≔׳Lθη≔׳L§θ⁰ζBζηψFLθ«J¹⊕׳ιF§θι«¿κP\²P/²M³→»»Fη«J⁰ιFζ«⊞υ¬℅KK¤#→»»⎚IΣυ

Try it online! Link is to verbose version of code. Uses the same format as the examples (except Charcoal requires the list of inputs as an outer array). Explanation:

≔׳Lθη≔׳L§θ⁰ζ

Like @LuisMendo, we're going to be drawing the matrix at 3x scale, so calculate that in advance.

Bζηψ

Draw an empty rectangle of that size so that we can fill the edge pieces.

FLθ«J¹⊕׳ιF§θι«

Loop over the rows and columns.

¿κP\²P/²M³→»»

Draw each slash at triple size and move to the next one.

Fη«J⁰ιFζ«

Loop over all of the squares.

⊞υ¬℅KK

Record whether this square was empty.

¤#→»»

But try filling it anyway before moving on to the next square. (Fill does nothing if the current square is not empty.)

⎚IΣυ

Clear the canvas and output the total number of empty squares found, which equals the number of pieces (because each piece would have been immediately filled in as soon as we counted it).

Neil

Posted 2019-10-28T13:31:34.743

Reputation: 95 035

2

C# (Visual C# Interactive Compiler), 292 bytes

n=>{var x=n.SelectMany(l=>"\0".Select(g=>l.SelectMany(r=>r.Skip(g).Concat(r.Take(g))).ToList())).ToList();int i=0,j=0,t=0;for(;i<x.Count;i++)for(j=0;j<x[0].Count;k(i,j++))t+=x[i][j]%2;void k(int a,int b){try{if(x[a][b]<50){x[a][b]='2';k(a+1,b);k(a-1,b);k(a,b-1);k(a,b+1);}}catch{}}return t;}

The \0 should be a literal null byte.

112 for /, 211 for \

Try it online!

Embodiment of Ignorance

Posted 2019-10-28T13:31:34.743

Reputation: 7 014

1

Jelly, 50 46 bytes

®_ż+¥"SƝż€"Jż‘$$ḞṖ
ZJḤ©Żż‘$;€þJ;ÇẎfƇ@Ẏ¥€`Q$ÐLL

Try it online!

A full program taking a matrix as its input with -0.5 as / and 0.5 as \. Returns an integer with the number of pieces.

Full explanation to follow, but works by generating a list of all the pairs of connected cells, and then merging overlapping sets until there’s no change. The final number of sets is the desired answer.

Nick Kennedy

Posted 2019-10-28T13:31:34.743

Reputation: 11 829