Here's my solution to Day4's AOC challenge. I had to use brute force to solve it, but doing it ths way gave me enough time to practice with blender and build this image the hero image so overall I'm really happy with the result. I might have to try completing AOC with Geometry nodes next year ;)
"""
Advent of Code Day4
"""
def part1(diagram: str) -> int:
"""
Transform the diagram into an array, find all the '@' symbols on that array and add them to a stack, then count the number of neighbouring '@' symbols each of those '@' symbols have and return the total amount of '@' symbols that have less than 4 '@' neighbours.
"""
total = 0
limiting_neighbours = 4
# we'll need to know the these values for boundary checking later so it's worth computing them now.
y_max = len(diagram.strip().split('\n'))
x_max = len(diagram.split('\n')[0])
# transform the diagram from a string with newlines into an array
# the "[::-1]" in the first comprehension is to ensure that the point 0,0 is in the bottom left, this is not strictly necesary, and might add a bit of obfuscation to the logic of this program, but I wanted to make it match the coordinates of a cartesean plane, so here we are.
# Example
# 9 - . . @ @ . @ @ @ @ .
# 8 - @ @ @ . @ . @ . @ @
# 7 - @ @ @ @ @ . @ . @ @
# 6 - @ . @ @ @ @ . . @ .
# 5 - @ @ . @ @ @ @ . @ @
# 4 - . @ @ @ @ @ @ @ . @
# 3 - . @ . @ . @ . @ @ @
# 2 - @ . @ @ @ . @ @ @ @
# 1 - . @ @ @ @ @ @ @ @ .
# 0 - @ . @ . @ @ @ . @ .
# | | | | | | | | | |
# 0 1 2 3 4 5 6 7 8 9
#
# NOTE: All this is theoretically uncessesay since we could just create a simple function to resolve a (x,y) coordinate to a location on the string and vise versa, but this is simpler for me.
rolls = [list(x) for x in [y for y in diagram.strip().split('\n')[::-1]]]
stack = []
# get all the '@' symbols and add them to the stack, we use y_max and x_max since they've already been computed
for y in range(y_max):
for x in range(x_max):
if rolls[y][x] == '@':
stack.append((y,x)) # NOTE: this should probably be (x,y) mathematically speaking, but to simplify the logic I'm going to use (y,x).
# store the 8 directions we want to check in
directions = [
(-1, 1),( 0, 1),( 1, 1),
(-1, 0), ( 1, 0),
(-1,-1),(0, -1),( 1,-1)
]
# perform a 'half BFS' to find the number of nearby neighbours
for point in stack:
neighbours = 0
# check all eight directions
for direction in directions:
dy = point[0] + direction[0]
dx = point[1] + direction[1]
# boundary checking to make sure we don't try to index a value off the diagram/array
if (dx >= x_max or dx < 0) or (dy >= y_max or dy < 0):
pass
elif rolls[dy][dx] == '@':
neighbours += 1
# if number of neighbours is less more than 'limiting_neighbours' add one to the total
if neighbours < limiting_neighbours:
total += 1
return total
def part2(diagram: str) -> int:
"""
Transform the diagram into an array, find all the '@' symbols on that array and add them to a stack, then count the number of neighbouring '@' symbols each of those '@' symbols have and return the total amount of '@' symbols thatd
"""
total = 0
limiting_neighbours = 4
# part 2 follows most of the same steps as part one, so I'll only comment what's changed
y_max = len(diagram.strip().split('\n'))
x_max = len(diagram.split('\n')[0])
rolls = [list(x) for x in [y for y in diagram.strip().split('\n')[::-1]]]
# our stack has been renamed to queue, since we are using it more like a queue than a stack
queue = []
for y in range(y_max):
for x in range(x_max):
if rolls[y][x] == '@':
queue.append((y,x))
directions = [
(-1, 1),( 0, 1),( 1, 1),
(-1, 0), ( 1, 0),
(-1,-1),(0, -1),( 1,-1)
]
# this is the main logic of the code that's changed from part 1
# for this implementation, need to repeat the checks from part 1 multiple times removing any with less than 'neighbour_limit' number of neighbours and continue doing this until we have no more with less than 'neighbour_limit' neighbours.
# the simplest way to do this is to put the logic from part 1 inside a infinite for loop, and check when there are no more changes that have been done last round at which point we know we can safely exit since modifications to the next round depend on modifications to the last round
while True:
# this is our flag to determine if a neighbour was removed last round
neighbours_removed = False
# instead of iterating over each item in the stack, we will instead iterate once for every number in the stack at the start, and remove symbols from the stack adding them back in only if they have more than 'limiting_neighbours' neighbours
for i in range(len(queue)):
point = queue.pop(0)
neighbours = 0
# neighbour checking
for direction in directions:
dy = point[0] + direction[0]
dx = point[1] + direction[1]
if (dx >= x_max or dx < 0) or (dy >= y_max or dy < 0):
pass
elif rolls[dy][dx] == '@':
neighbours += 1
if neighbours >= limiting_neighbours:
# any point with more than 'limiting_neighbours' number of neighbours gets added back to the stack for next round
queue.append(point)
else:
# any point with less than 'limiting_neighbours' number of neighbours has one added to the total
total += 1
# gets nullified on the original map
rolls[point[0]][point[1]] = '.'
# and sets the neighbours_removed flag to true so the program knows that we need to test the map one last time to see if this change caused any symbols to lose enough neighbours to be removed.
neighbours_removed = True
# if no neighbours have been removed last round that means that there must be no more possible '@' characters to remove and the loop can safely exit.
if neighbours_removed != True:
break
return total
if __name__ == '__main__':
test_file = open('test1.txt','r')
test_data = test_file.read()
test_file.close()
print(f'part 1 - test 1 output : {part1(test_data)}')
input_file = open('input1.txt','r')
input_data = input_file.read()
input_file.close()
print(f'part 1 - output : {part1(input_data)}')
test_file = open('test1.txt','r')
test_data = test_file.read()
test_file.close()
print(f'part 2 - test 1 output : {part2(test_data)}')
input_file = open('input1.txt','r')
input_data = input_file.read()
input_file.close()
print(f'part 2 - output : {part2(input_data)}')