This problem just shows me how important it is to test. I started working on this problem yesterday and found myself getting a bit stuck on it. I was scratching my head because I thought I had a good algorithm but couldn’t figure out why things were working. Well, that’s because there were at least 2 or 3 or more bugs in the code. I started working on this today by writing tests for each method on my Matrix class. Once I did, I was able to pinpoint problems and fix them easily.
This code works, but it’s not something that I’d use more than once. First of all, it’s not all that quick. The problem takes about 32 seconds to complete. While not bad, it’s also not good if you’re wanting to work with a matrix any bit larger than what we’re given for this problem.
Additionally, I’ve been thinking a lot at work lately about good APIs. I’d say
that what I have here is not an idea API. Some methods that I have on the
Matrix class really shouldn’t be methods on that class and instead should
probably just be top level functions. Examples of this being the _next_vertex
and _next_vertex_via_rollback methods. There’s nothing in them that is
requiring access to the Matrix class itself, so why have it as a method on that
class? I didn’t find it all that important to fix this while working on the
problem since this is just one off work, but just some thoughts for if I were
to actually need this code long term.
given = """
7 53 183 439 863
497 383 563 79 973
287 63 343 169 583
627 343 773 959 943
767 473 103 699 303
"""
empty = """
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
"""
easy = """
0 0 0 0 5
0 0 0 5 0
0 0 5 0 0
0 5 0 0 0
5 0 0 0 0
"""
problem = """
7 53 183 439 863 497 383 563 79 973 287 63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463 29 23 487 463 993 119 883 327 493 423 159 743
217 623 3 399 853 407 103 983 89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915 45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601 95 973
445 721 11 525 473 65 511 164 138 672 18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513 17 901 711 993 293 157 274 94 192 156 574
34 124 4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615 77 281 613 459 205 380 274 302 35 805
"""
class Matrix(list):
# Assumptions:
# 1. The matrix passed to new_matrix_from_str is square.
# 2. No value in the matrix is greater than 999.
@staticmethod
def new_matrix_from_str(matrix_string):
matrix = Matrix()
row_list = matrix_string.split('\n')
for row in row_list:
item_str_list = row.split()
if not item_str_list:
continue
item_int_list = [1000-int(item) for item in item_str_list]
matrix.append(item_int_list)
return matrix
def calculate_max_sum(self):
# start with an initial depth of vertexes
vertexes = [(i, i) for i in range(self.dimention - 1)]
min_sum = float('inf')
# the last vertex will be added in the while loop
i, j = self.dimention - 1, self.dimention - 1
while i < self.dimention and j < self.dimention:
vertexes.append((i, j))
current_sum = self.vertex_sum(vertexes)
if current_sum < min_sum and len(vertexes) == self.dimention:
min_sum = current_sum
if self._vertexes_complete(vertexes):
break
i, j = self._next_vertex(vertexes, current_sum > min_sum)
return self._inverse_sum(min_sum)
def _next_vertex(self, vertexes, force_rollback):
if force_rollback:
next_i, next_j = self._next_vertex_via_rollback(vertexes)
else:
next_i, next_j = vertexes[-1][0] + 1, 0
while next_i < self.dimention and next_j < self.dimention:
if self.is_available_vertex(vertexes, (next_i, next_j)):
break
next_j += 1
else:
next_i, next_j = self._next_vertex_via_rollback(vertexes)
return next_i, next_j
def _next_vertex_via_rollback(self, vertexes):
while vertexes:
last_i, last_j = vertexes.pop()
next_i, next_j = last_i, last_j + 1
while next_j < self.dimention:
# get the next available item on the row
if self.is_available_vertex(vertexes, (next_i, next_j)):
return next_i, next_j
next_i, next_j = next_i, next_j + 1
# if one is not available, continue to pop another
return next_i, next_j
def _vertexes_complete(self, vertexes):
i, j = self.dimention - 1, 0
while j < self.dimention:
if (i, j) not in vertexes:
return False
i -= 1
j += 1
return True
@property
def dimention(self):
return len(self)
def _inverse_sum(self, min_sum):
return self.dimention * 1000 - min_sum
def vertex_sum(self, vertexes):
return sum(self[i][j] for i, j in vertexes)
def is_available_vertex(self, existent_vertexes, next_vertex):
for i, j in existent_vertexes:
if i == next_vertex[0] or j == next_vertex[1]:
return False
return True
if __name__ == '__main__':
max_sum = Matrix.new_matrix_from_str(problem).calculate_max_sum()
print('The maximum matrix sum is:', max_sum)
import pytest
import problem
_test_matrix = """
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
"""
def test_new_matrix_from_str():
matrix = problem.Matrix.new_matrix_from_str(_test_matrix)
assert matrix == [
[999, 998, 997, 996],
[995, 994, 993, 992],
[991, 990, 989, 988],
[987, 986, 985, 984],
]
def test_dimention():
matrix = problem.Matrix.new_matrix_from_str(_test_matrix)
assert matrix.dimention == 4
def test__inverse_sum():
matrix = problem.Matrix.new_matrix_from_str(_test_matrix)
assert matrix._inverse_sum(123) == 3877
@pytest.mark.parametrize('vertexes,expected', (
([(0, 0)], 999),
([(0, 0), (1, 1)], 1993),
))
def test_vertex_sum(vertexes, expected):
matrix = problem.Matrix.new_matrix_from_str(_test_matrix)
assert matrix.vertex_sum(vertexes) == expected
@pytest.mark.parametrize('vertexes,vertex,expected', (
([(0, 0)], (0, 0), False),
([(0, 0)], (1, 0), False),
([(0, 0)], (0, 1), False),
([(0, 0), (1, 1)], (0, 1), False),
([(0, 0), (1, 1)], (2, 3), True),
))
def test_is_available_vertex(vertexes, vertex, expected):
matrix = problem.Matrix.new_matrix_from_str(_test_matrix)
assert matrix.is_available_vertex(vertexes, vertex) is expected
@pytest.mark.parametrize('vertexes,expected', (
([(0, 0)], False),
([(3, 3)], False),
([(3, 3), (2, 2)], False),
([(3, 0), (2, 1), (0, 2), (1, 3)], False),
([(3, 0), (2, 1), (1, 2), (0, 3)], True),
))
def test__vertexes_complete(vertexes, expected):
matrix = problem.Matrix.new_matrix_from_str(_test_matrix)
assert matrix._vertexes_complete(vertexes) is expected
@pytest.mark.parametrize('vertexes,expected_return,expected_vertexes', (
([(0, 0)], (0, 1), []),
([(0, 0), (1, 1)], (1, 2), [(0, 0)]),
([(0, 2), (1, 3)], (0, 3), []),
([(0, 1), (1, 3)], (0, 2), []),
([(0, 1), (1, 3), (2, 2)], (0, 2), []),
([(0, 0), (1, 1), (2, 2), (3, 3)], (2, 3), [(0, 0), (1, 1)]),
))
def test__next_vertex_via_rollback(vertexes, expected_return, expected_vertexes):
matrix = problem.Matrix.new_matrix_from_str(_test_matrix)
actual = matrix._next_vertex_via_rollback(vertexes)
assert vertexes == expected_vertexes
assert actual == expected_return
@pytest.mark.parametrize('vertexes,force_rollback,expected_return,expected_vertexes', (
([(0, 0)], True, (0, 1), []),
([(0, 0), (1, 1)], True, (1, 2), [(0, 0)]),
([(0, 2), (1, 3)], True, (0, 3), []),
([(0, 1), (1, 3)], True, (0, 2), []),
([(0, 1), (1, 3), (2, 2)], True, (0, 2), []),
([(0, 0), (1, 1), (2, 2), (3, 3)], True, (2, 3), [(0, 0), (1, 1)]),
([(0, 0)], False, (1, 1), [(0, 0)]),
([(0, 0), (1, 1)], False, (2, 2), [(0, 0), (1, 1)]),
([(0, 2), (1, 3)], False, (2, 0), [(0, 2), (1, 3)]),
([(0, 1), (1, 3)], False, (2, 0), [(0, 1), (1, 3)]),
([(0, 1), (1, 3), (2, 2)], False, (3, 0), [(0, 1), (1, 3), (2, 2)]),
([(0, 2), (1, 3), (2, 1)], False, (3, 0), [(0, 2), (1, 3), (2, 1)]),
([(0, 0), (1, 1), (2, 2), (3, 3)], False, (2, 3), [(0, 0), (1, 1)]),
([(0, 1), (1, 2), (2, 3), (3, 0)], False, (1, 3), [(0, 1)]),
))
def test__next_vertex(vertexes, force_rollback, expected_return, expected_vertexes):
matrix = problem.Matrix.new_matrix_from_str(_test_matrix)
actual = matrix._next_vertex(vertexes, force_rollback)
assert vertexes == expected_vertexes
assert actual == expected_return
@pytest.mark.parametrize('test_matrix,expected', (
(problem.empty, 0),
(problem.easy, 25),
(problem.given, 3315),
))
def test_calculate_max_sum(test_matrix, expected):
matrix = problem.Matrix.new_matrix_from_str(test_matrix)
assert matrix.calculate_max_sum() == expected