Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
67-liner: projection in 3d grid solution in 3rd party category for Triangular Islands by przemyslaw.daniel
'''
Let's try inserting triangular grid in a two-dimensional table
1 2 3 4 5 ... (diagonals)
------------------------
1 |4 |9 |16 |25
3| 8| 15| 24|
------------------------
2 |7 |14 |23 |
6| 13| 22| |
------------------------
5 |12 |21 | |
11| 20| | |
------------------------
10 |19 | | |
18| | | |
Now split them by the diagonals
1 | | | | |4 | | | | |9 | |
| | | | 3| | | | | 8| | |
------------------------ ------------------------ ------------------------
| | | | 2 | | | | |7 | | |
| | | | | | | | 6| | | |
------------------------ ------------------------ ------------------------
| | | | | | | | 5 | | | |
| | | | | | | | | | | |
------------------------ ------------------------ ------------------------
| | | | | | | | | | | |
| | | | | | | | | | | |
| | |16 | | | | |25
| | 15| | | | | 24|
------------------------ ------------------------
| |14 | | | | |23 |
| 13| | | | | 22| |
------------------------ ------------------------ ...
|12 | | | | |21 | |
11| | | | | 20| | |
------------------------ ------------------------
10 | | | | |19 | | |
| | | | 18| | | |
When stack them one on another we get three-dimensional grid representing original
structure. Let's have a look at an example. Number 7 has two neighbors in the same
layer which are 6 and 8. The cell in layer below is empty, so there is no neighbor.
The cell in layer above is 13.
All we have to do is to project every element in 3d grid, label them and count the
number of elements for every separate group
'''
from typing import Set, Iterable
from scipy.ndimage import label
from numpy import zeros
from math import isqrt
def triangular_islands(triangles: Set[int]) -> Iterable[int]:
grid3d = zeros([max(triangles)] * 3)
for triangle in triangles:
diag = isqrt(triangle - 1)
pos = triangle - 1 - diag ** 2
grid3d[diag][pos // 2][diag - pos // 2 - pos % 2] = 1
result, number = label(grid3d)
result = result.flatten().tolist()
return [result.count(group + 1) for group in range(number)]
Aug. 1, 2020
Comments:
