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:
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
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.4334The 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.7132@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