Short thanks to scipy.ndimage.label 3rd party solution for Boundary Blocks by Phil15 - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Short thanks to scipy.ndimage.label solution in 3rd party category for Boundary Blocks by Phil15

from scipy.ndimage import label
import numpy as np

neighbors = lambda M, i, j: map(int, M[max(0, i-1):i+2, max(0, j-1):j+2].flat)

def boundary_blocks(grid):
    grid, nb_zones = label(np.array([[x != 'X' for x in row] for row in grid]))
    if nb_zones > 1:  # otherwise, no boundary block.
        for i, row in enumerate(grid):
            for j, nb_zone in enumerate(row):
                if not nb_zone and len(set(neighbors(grid, i, j))) > 2:
                    yield i, j

May 16, 2019

Comments:

kurosawa4434 on May 26, 2019, 2:10 p.m.
awesome solution. I used this solution to improve Visibility's `init.js`.

Phil15 on May 26, 2019, 5:26 p.m.
Great! <h3>Since I prepared an answer to your <a href="https://py.checkio.org/forum/post/13201/new-mission-boundary-blocks/#comment-73477">question</a>, there it is...</h3> Like always, documentation (below) is useful but a bit rough. Look the attached image. So... it help to find objects (or connected components in a more technical way) in an image, and the number of objects in it. Here, in our case, we have a binary array (black cells and not black cells), empty cells are what we search in the array. If we find two objects or more, it means that black cells are separating empty ones in several parts, it's against the last rule. Basically, `structure` argument default search horizontally and vertically, not diagonally. But we can change that if we want. <pre class='brush: python'>label(input, structure=None, output=None) Label features in an array. Parameters ---------- input : array_like An array-like object to be labeled. Any non-zero values in \`input\` are counted as features and zero values are considered the background. structure : array_like, optional A structuring element that defines feature connections. \`structure\` must be symmetric. If no structuring element is provided, one is automatically generated with a squared connectivity equal to one. That is, for a 2-D \`input\` array, the default structuring element is:: [[0,1,0], [1,1,1], [0,1,0]] output : (None, data-type, array_like), optional If \`output\` is a data type, it specifies the type of the resulting labeled feature array If \`output\` is an array-like object, then \`output\` will be updated with the labeled features from this function. This function can operate in-place, by passing output=input. Note that the output must be able to store the largest label, or this function will raise an Exception. Returns ------- label : ndarray or int An integer ndarray where each unique feature in \`input\` has a unique label in the returned array. num_features : int How many objects were found. If \`output\` is None, this function returns a tuple of (\`labeled_array\`, \`num_features\`). If \`output\` is a ndarray, then it will be updated with values in \`labeled_array\` and only \`num_features\` will be returned by this function. See Also -------- find_objects : generate a list of slices for the labeled features (or objects); useful for finding features' position or dimensions Examples -------- Create an image with some features, then label it using the default (cross-shaped) structuring element: >>> from scipy.ndimage import label, generate_binary_structure >>> a = np.array([[0,0,1,1,0,0], ... [0,0,0,1,0,0], ... [1,1,0,0,1,0], ... [0,0,0,1,0,0]]) >>> labeled_array, num_features = label(a) Each of the 4 features are labeled with a different integer: >>> num_features 4 >>> labeled_array array([[0, 0, 1, 1, 0, 0], [0, 0, 0, 1, 0, 0], [2, 2, 0, 0, 3, 0], [0, 0, 0, 4, 0, 0]]) Generate a structuring element that will consider features connected even if they touch diagonally: >>> s = generate_binary_structure(2,2) or, >>> s = [[1,1,1], ... [1,1,1], ... [1,1,1]] Label the image using the new structuring element: >>> labeled_array, num_features = label(a, structure=s) Show the 2 labeled features (note that features 1, 3, and 4 from above are now considered a single feature): >>> num_features 2 >>> labeled_array array([[0, 0, 1, 1, 0, 0], [0, 0, 0, 1, 0, 0], [2, 2, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0]]) </pre>

kurosawa4434 on May 27, 2019, 1:56 a.m.
I understood the label(). Thank you very much! This can be used for various CheckiO missions :-D

Phil15 on May 28, 2019, 7:44 a.m.
Somehow, I didn't understand that you created a pull request. I finally saw it thanks to a script of my own, so I just merged/sync it.

rodka81 on May 29, 2019, 1:54 p.m.
Another nice solution with `scipy.ndimage.label`, which I also used again in my solution :) I like the fact that you used generators instead of producing an array or set.

Phil15 on May 30, 2019, 6:59 a.m.
I use generators as much as I can. I think that readability thanks me for that. :-)

przemyslaw.daniel on June 1, 2019, 4:48 a.m.
Actually numpy is not necessary

Phil15 on June 1, 2019, 6:54 a.m.
Indeed! Thanks, it's good to know. `label([[...], ...])` give a `numpy.ndarray` and an `int`.

swagg010164 on June 2, 2019, 8:26 p.m.
Very interesting solution! I did not guess in my solution to use scipy. Instead, I decided to use a modified DFS algorithm. Also, thanks for explaining how scipy.ndimage.label works!)

Ylliw on June 13, 2019, 1:05 p.m.
Nice, short and efficient

Different kind of sets

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.