Improving the manipulation of 2D Arrays for an easy challenge on HackerRank with Python 3

Question

I am practicing some exercises on HackerRank in order to improve my skills on Python3. I am doing the 30 days challenge. There is one challenge involving matrices. I was able to pass the test cases and provide the correct result. However, I think my code could have huge improvements.

I am not really sure about how would be the best way to iterate over matrices to solve the problem asked. That's the challenge:

That's my code:

import sys

matrix_input = sys.stdin.readlines()
#print (matrix_input)

def make_matrix(matrix):

    final_matrix = []

    for line in matrix:

        #remove new_line
        line = line.strip()

        #remove space
        line = line.split(" ")

        #convert string to int
        line = list(map(int,line))

        final_matrix.append(line)

    return (final_matrix)

"""the function is going to receive a hour glass and return the sum of its elements. The easiest way is to treat things as a rectangle and make the elements on the second line, first col and last col, null, like zero"""

def sum_hour_glass_rec(hour_glass_rec):

    hour_glass_rec[1][0]=0

    hour_glass_rec[1][2]=0

    total = 0

    for linha in hour_glass_rec:
        for coluna in linha:
            total = total + coluna

    return total

def make_list_hour_glasses(matrix):

    A = matrix

    col_var= 0 
    list_part_hour_glass_iter = []
    list_hour_glasses = []
    k_var_iter = 0

    for k in range(0,4):
        col_var = 0
        for j in range(0,4):
            #print (j,"j")  
            for col in range(k_var_iter,k_var_iter+3):
                #print (col,"col")
                #print (A[col][col_var:col_var+3])
                list_part_hour_glass_iter.append(A[col][col_var:col_var+3])
                #print (list_part_hour_glass_iter)
                list_hour_glasses.append(list_part_hour_glass_iter)
            list_part_hour_glass_iter = []
            #print (list_hour_glasses)
            col_var+=1
        k_var_iter +=1

    return list_hour_glasses

matrix_of_recs = (make_list_hour_glasses(make_matrix(matrix_input)))

records = []

for rectangle in matrix_of_recs:
    records.append(sum_hour_glass_rec(rectangle))

maximum_record = max(records)

print(maximum_record)

In order to execute this, I created another file, called d11_input.txt with the input values:

1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18 
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36

My command on terminal would just be:

python3 d11.py < d11_input.txt 

Points that I suspect could have huge improvements:

1 - I treated the hourglass as a square and then, made two elements A21 and A23 zero. Maybe there is a more elegant way to do that.

2 - I used a three nested loop in order to generate all hour glasses a 6x6 matrix can have. Not good in terms of big O notation. Is there a way better?

3 - As you might see, when generating all possible hour glasses, each one was repeated three times which means I am calculating things that I do not need. Nonetheless, I was not able to fix this and also keep the rest of the code working. Here you see a picture of the "problem" involving repeated data that I am talking about:

I hope I will learn with your comments. Thanks in advance =)

Answer 1

Generating all possible hourglasses

Don't :-) It's a lot of memory and processing churn.

A more efficient alternative is to write a function that takes as parameters a matrix and the starting position of an hourglass, and return the sum of values at the appropriate relative positions:

def compute_hourglass_sum(matrix, top, left):
    return sum(matrix[top][left:left+3]) + ...

The caller is responsible for passing parameters to valid hourglasses.

As for the unnecessary recomputing of sums of overlapping hourglasses, given the small sizes of hourglass dimensions, I don't think it's worth it to come up with something more clever.

However, if the dimensions became significantly bigger, then that would indeed make sense. Perhaps prefix sums would be useful for that. I suggest to check out the concept, it's very interesting stuff.

Processing the input

In make_matrix it's not so great that the input parameter is named matrix when in fact it's just unprocessed text. I'd name it input. And then the local final_matrix variable could be renamed to simply matrix.

And I would rewrite the function with a list comprehension:

return [map(int, line.split()) for line in input]

(Thanks @Graipher for simplifying line.strip().split(" ") to line.split().)

Minor things

There is an official coding style guide for Python called PEP8. I suggest to check it out. There is a command line tool that can check your code.

There are some redundant parentheses here and there. I suggest to remove them. The pep8 tool can pinpoint them for you.

The default start value of range(...) is 0, so instead of range(0, 4) you can write simply range(4).