Part 1
This was a tricky exercise. From the get-go I avoided iterating over the matrix with plain for loops, and again tried to stick with functional principles. Thus, I'd analyse a set of three lines at once. I think there are some further optimisations in code quality by making the matrix variable global: look_at_surroundings_of_char only needs the line index and the index in the line; the first two parameters are unnecessary.
The get_number_string_under_index was a bit tricky: it uses some sort of flood-fill kind of logic to get the full number (eg. ....2513..., and the algorithm starts at the 1 char; it would concatenate 25 to 1 to 3).
Tests
TEST_DATA = """
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598.."""
class Test202303_01(unittest.TestCase):
def test_transform_input_into_game_data(self):
matrix = get_game_data_from_input(TEST_DATA)
self.assertEqual(matrix,
TEST_DATA.strip().splitlines())
def test_upper_current_lower_lines(self):
matrix = get_game_data_from_input(TEST_DATA)
self.assertEqual(get_upper_current_lower_lines(matrix, 0),
(None, matrix[0], matrix[1]))
self.assertEqual(get_upper_current_lower_lines(matrix, 2),
(matrix[1], matrix[2], matrix[3]))
self.assertEqual(get_upper_current_lower_lines(matrix, len(matrix) - 1),
(matrix[len(matrix) - 2], matrix[len(matrix) - 1], None))
def test_number_string_under_index(self):
self.assertEqual(
get_number_string_under_index("...123...", 3),
"123"
)
self.assertEqual(
get_number_string_under_index("...123...", 2),
""
)
self.assertEqual(
get_number_string_under_index("...1234", 3),
"1234"
)
self.assertEqual(
get_number_string_under_index("...4", 3),
"4"
)
self.assertEqual(
get_number_string_under_index(".124", 3),
"124"
)
def test_look_at_surroundings_of_char(self):
matrix = get_game_data_from_input(TEST_DATA)
# match on below right diagonal
self.assertEqual(
look_at_surroundings_of_char(None,
matrix[0],
matrix[1],
2),
True
)
# No matches
self.assertEqual(
look_at_surroundings_of_char(None,
matrix[0],
matrix[1],
5),
False
)
# No matches on 35 above the three
self.assertEqual(
look_at_surroundings_of_char(matrix[1],
matrix[2],
matrix[3],
2),
False
)
# match on 35 above the five
self.assertEqual(
look_at_surroundings_of_char(matrix[1],
matrix[2],
matrix[3],
3),
True
)
# match on 655 below the six
self.assertEqual(
look_at_surroundings_of_char(matrix[1],
matrix[2],
matrix[3],
6),
True
)
self.assertEqual(
look_at_surroundings_of_char(matrix[8],
matrix[9],
None,
5),
True
)
def test_accumulate_part_numbers_in_line(self):
matrix = get_game_data_from_input(TEST_DATA)
self.assertEqual(
accumulate_part_numbers_in_line(matrix, len(matrix) - 1),
[664, 598]
)
self.assertEqual(
accumulate_part_numbers_in_line(matrix, 5),
[]
)
# excerpt from part 1 solution
self.assertEqual(
accumulate_part_numbers_in_line(["$..733*758..."], 0),
[733, 758]
)
def test_solve_part1(self):
self.assertEqual(
solve_part_1(TEST_DATA),
4361
)
Code
from functools import reduce
def get_game_data_from_input(data: str) -> list[str]:
return data.strip().splitlines()
def char_is_a_symbol(char: str) -> bool:
return not (char.isdigit() or char == '.')
def get_upper_current_lower_lines(
matrix: list[str],
line_nbr: int
) -> tuple[str | None, str, str | None]:
upper = (None if line_nbr == 0
else matrix[line_nbr - 1])
lower = (None if line_nbr == len(matrix) - 1
else matrix[line_nbr + 1])
return (upper, matrix[line_nbr], lower)
def get_number_string_under_index(
line: str,
index: int
) -> str:
def get_chars_behind_or_ahead(
index: int,
behind: bool = False) -> str:
if behind:
return (line[index] +
get_chars_behind_or_ahead(index - 1, True)
if index >= 0 and line[index].isdigit()
else "")
else:
return (line[index] +
get_chars_behind_or_ahead(index + 1)
if index < len(line) and line[index].isdigit()
else "")
return (get_chars_behind_or_ahead(index - 1, True)[::-1] +
line[index] +
get_chars_behind_or_ahead(index + 1)
if line[index].isdigit()
else "")
def get_next_non_digit_symbol_index(line: str, index: int) -> int:
return (get_next_non_digit_symbol_index(line, index + 1)
if index < len(line) and line[index].isdigit()
else index)
def look_at_surroundings_of_char(upper: str | None,
line: str, lower: str | None, index: int) -> bool:
# Check vertically
if any(map(lambda x: x is not None and char_is_a_symbol(x[index]),
[upper, lower])):
return True
# Check horizontally
for offset in [-1, 1]:
new_index = index + offset
if 0 <= new_index < len(line):
if (char_is_a_symbol(line[new_index])):
return True
# Check diagonally
if (line[new_index] == '.' and
any(map(lambda x: x is not None and char_is_a_symbol(x[new_index]),
[upper, lower]))):
return True
return False
# recursively checks the line
def accumulate_part_numbers_in_line(
matrix: list[str],
line_nbr: int,
index: int = 0,
result: list[int] = []):
if index >= len(matrix[line_nbr]):
return result
char = matrix[line_nbr][index]
# if a digit is found, check its surroundings.
# if there is a symbol nearby, add the number and keep going
if (char.isdigit() and look_at_surroundings_of_char(
*get_upper_current_lower_lines(matrix, line_nbr),
index)):
# add the number to the result list, and
number = get_number_string_under_index(matrix[line_nbr], index)
# make the index jump to the end of that digit
next_index = get_next_non_digit_symbol_index(matrix[line_nbr], index)
return accumulate_part_numbers_in_line(
matrix,
line_nbr,
next_index,
result + [int(number)]
)
else:
return accumulate_part_numbers_in_line(
matrix,
line_nbr,
index + 1,
result
)
def solve_part_1(data: str) -> int:
matrix = get_game_data_from_input(data)
return sum(reduce(lambda x, y: x + y,
map(lambda x: accumulate_part_numbers_in_line(matrix, x),
range(len(matrix))),
[]))
with open('input', 'r') as f:
data = f.read()
print(solve_part_1(data))Part 2
Part two seems to demand a whole different approach. On Part one, I focused mainly on the numbers, checking whether they were adjacent to anything; this time around, we're only paying attention to * chars (stars), and we must retrieve the cases where there are two adjacent numbers.
So I started working from the bigger functions to the smallest, while devising some tests. It seems like a natural adaptation to change the code to the following:
# recursively checks the line
def accumulate_eligible_gears_in_line(
matrix: list[str],
line_nbr: int,
index: int = 0,
result: list[int] = []):
if index >= len(matrix[line_nbr]):
return result
# if a star is found, check its surroundings.
char = matrix[line_nbr][index]
nbrs = look_at_surroundings_of_star(
*get_upper_current_lower_lines(matrix, line_nbr),
index)
# add the number to the result list, and
# make the index jump to the end of that digit
return accumulate_eligible_gears_in_line(
matrix,
line_nbr,
get_next_star_symbol_index(matrix[line_nbr], index),
result + nbrs if len(nbrs) == 2 else result
)
def solve_part_2(data: str) -> int:
matrix = get_game_data_from_input(data)
return sum(reduce(lambda x, y: x + y,
map(lambda x: accumulate_part_numbers_in_line(matrix, x),
range(len(matrix))),
[]))Debugging
After concluding the code and having the example scenario pass, I came to the unfortunate situation of failing the problem result. Thus, one has to step debug, or try to find, like searching for a needle in a haystack, the piece of code that is making the whole thing crumble.
I tried going line by line and manually check for the correct pairs; comparing each line with the result of accumulate_eligible_gears_in_star_position. This absurd procedure went for a little bit more than what I think is sane (sane = 2 lines. Not more).
Then I tried comparing the number of pairs to the number of stars. This should be a nice metric to have around: it's possible that the number of pairs is fewer than the number of stars (situation where a star is adjacent to a different number of gears than two). What I did not expect, though, is to have more pairs than stars, which is a gross mistake.
On the problem input,
..........................126.121......935*......235.815.......*.887........*........34..........294........*............$..............@...
45......$..651....$...............................*.........526.............41......*......302...................530..........@819.......463
.....710......*....26................734.......791......565............625.......%.887........@.......381..741..*...........................my code finds an additional pair [345, 45]. Not good!
Apparently, I had just missed the condition of the char being a * when calling to accumulate via look_at_surroundings_of_star. The following fixes the problem of having more pairs than stars (which was very much absurd).
def accumulate_eligible_gears_in_star_position(
matrix: list[str],
line_nbr: int,
index: int = 0,
result: list[int] = []) -> list[list[int] | None]:
if index >= len(matrix[line_nbr]):
return result
# if a star is found, check its surroundings;
nbrs = (look_at_surroundings_of_star(
*get_upper_current_lower_lines(matrix, line_nbr),
index)
if matrix[line_nbr][index] == '*' else [])
return accumulate_eligible_gears_in_star_position(
matrix,
line_nbr,
get_next_star_symbol_index(matrix[line_nbr], index + 1),
(result + [nbrs] if nbrs is not None and len(nbrs) == 2
else result)
)And yet, the calculation is was still wrong, and I had not got the slighest clue as to why; only that my answer was below the correct one. So I looked into the output, having also noticed that the test data did not have two gear rations in the same line: and thus, my tests were not thorough enough. Below is the definition of my solver function.
def solve_part_2(data: str) -> int:
matrix = get_game_data_from_input(data)
all_lines = sum(map(lambda t: t[0][0] * t[0][1],
filter(lambda r: r != [],
map(lambda x: accumulate_eligible_gears_in_star_position(matrix, x),
range(len(matrix))))))
return all_linesAnd, for a taste of the output,
[[[102, 206], [449, 140], [138, 301]], [[723, 877], [687, 380], [692, 263]], [[814, 483], [154, 779]], [[733, 758], [489, 551]], [[674, 405]], [[503, 422], [591, 840], [676, 167], [147, 410]] (...)I suppose all_lines is just calculating the product of the first two elements of each sublist (each sublist corresponding to the gear ratios of a line). Thus, what I have is a nesting problem, because, in fact, I'm assuming my final answer to be a flattened list.
def solve_part_2(data: str) -> int:
matrix = get_game_data_from_input(data)
all_lines = sum(map(lambda t: t[0] * t[1],
reduce(lambda x, y: x + y if y is not None else x,
map(lambda x: accumulate_eligible_gears_in_star_position(matrix, x),
range(len(matrix))),
[])))
return all_linesThe reduce is now flattening the list, while also filtering the empty results.
Tests
class Test202303_02(unittest.TestCase):
def test_accumulate_eligible_gears_in_line_upperleft_below(self):
matrix = get_game_data_from_input(TEST_DATA)
self.assertEqual(
accumulate_eligible_gears_in_star_position(matrix, 1),
[[35, 467]]
)
def test_accumulate_eligible_gears_in_line_single_result(self):
matrix = get_game_data_from_input(TEST_DATA)
self.assertEqual(
accumulate_eligible_gears_in_star_position(matrix, 4),
[]
)
def test_accumulate_eligible_gears_in_line_single_result_upperright_below(self):
matrix = get_game_data_from_input(TEST_DATA)
self.assertEqual(
accumulate_eligible_gears_in_star_position(matrix, 8),
[[598, 755]]
)
def test_accumulate_eligible_gears_in_line_double_result(self):
TEST_DATA = """467..114..\n...*..*...\n..35..633."""
matrix = get_game_data_from_input(TEST_DATA)
self.assertEqual(
accumulate_eligible_gears_in_star_position(matrix, 1),
[[35, 467], [114, 633]]
)
def test_accumulate_eligible_gears_in_line_extra_gears_on_real_input(self):
with open("input", "r") as f:
matrix = get_game_data_from_input(f.read())
self.assertEqual(
accumulate_eligible_gears_in_star_position(matrix, 29),
[[235, 791], [887, 34]]
)
def test_can_get_all_adjacent_numbers(self):
TEST_DATA = """467.11.4..\n...*......\n..35.2.333"""
matrix = get_game_data_from_input(TEST_DATA)
self.assertEqual(
look_at_surroundings_of_star(*matrix, 3),
[35, 467, 11],
)
def test_can_get_all_adjacent_numbers_two(self):
TEST_DATA = """467.11.4..\n......*...\n..35.2.333"""
matrix = get_game_data_from_input(TEST_DATA)
self.assertEqual(
look_at_surroundings_of_star(*matrix, 6),
[11, 4, 2, 333]
)
def test_solve_part2(self):
self.assertEqual(
solve_part_2(TEST_DATA),
467835
)
```