Python Matrices - Find the number of empty cells at a distance of at most K to every house

Question

I'm new to algorithms and would like to challenge myself to this question. I have done all validations (although not optimized, but at least it is working), but the upcoming logic in the question is too challenging for me. I would really appreciate if I could have guidance or at least code with explanation so that I can understand what is going on.

The challenge is to build a house with every surrounding houses in close approximate (max distance = K). Distance hops are calculated only vertically and horizontally.

In any cases, the validations are:

K is the distance from a house to an empty plot, and within 1-800.
The Matrices N x M must be within 2-400
1 to denote a house
0 to denote an empty plot
There is at least 1 house (one 1, possible for list=[[0, 0, 0], [0, 1, 0], [0, 0, 0]])

As per my example (the list I'm using in my code), the graph should look like this: Row = R, Column = C

So based on distance K which is 2, the max distance is 2 cells. As such, the only possible solution is row,column index of (1, 1) which is the house I'm building, X.

  C C C
R 0 1 0
R 1 X 0
R 0 0 1

This is currently my code, and I have also stored all existing houses index position row,column into a list:

def solution(k, arr):
    if not 1 <= k <= 800:
        return False

    rows = len(arr)
    is_there_1 = False
    columns = 0

    if not (2 <= rows <= 400):
        return False
    else:
        for i in arr:
            if type(i) != list:
                if not (2 <= len(list(str(i))) <= 400):
                    return False
                else:
                    columns = len(list(str(i)))
                    for j in i:
                        if j == 1:
                            is_there_1 = True

                        if j != 1 and j != 0:
                            return False
            else:
                if not (2 <= len(i) <= 400):
                    return False
                else:
                    columns = len(i)
                    for j in i:
                        if j == 1:
                            is_there_1 = True

                        if j != 1 and j != 0:
                            return False

        if not is_there_1:
            return False

    print("Rows: " + str(rows))
    print("Columns: " + str(columns))
    print("-------------------------")
    for i in arr:
        print(i)
    print("-------------------------")

    house_index_list = []

    for r_count, r_ele in enumerate(arr):
        for c_count, c_ele in enumerate(r_ele):
            if c_ele == 1:
                house_index_pos = (r_count, c_count)
                house_index_list.append(house_index_pos)

    print("-------------------------")
    print("House in Coordinates: " + str(house_index_list))

    for x, y in enumerate(house_index_list):
        pass


list3 = [[0, 1, 0], [1, 0, 0], [0, 0, 1]]
print(solution(2, list3))

To be honest, I'm not even sure how to go on now. I can plot the graph but I'm confused as to how I can use the positions of the houses with the distance K to find the optimal empty plot to build my house. In addition, I'm working with a small list. Judging by the large value of N and M, I'm feeling the stress and challenge of this problem. I'm using return True/False for testing purposes, the solution is supposed to be a series of Row/Column of possible plots to build house X in a tuple.

I'm not even sure if my index positions of the existing houses are useful.

I would really appreciate any form of guidance.

Thank you so much.

Python Matrices - Find the number of empty cells at a distance of at most K to every house

0 Answers