Advent of Code: Day 2

 Link to problem: https://adventofcode.com/2024/day/2

Day 2 seems pretty straightforward too, at least the first problem:

Each line is processed independently so I figured I'd define a function rather than having a really messy for loop.

And... I was struggling to get my limited attention spam to parse 5 conditional statements.... so I brought it down to 4 by using that set safe

safe = {1, 2, 3}
def isSafe(levels: tuple[int]) -> bool:
increasing = True
decreasing = True
for a, b in zip(levels, levels[1:]):
if abs(a - b) not in safe:
return False
if a > b:
increasing = False
if b > a:
decreasing = False
if not (increasing or decreasing):
return False
return True

Yes, I know, this is not a very good use of zip... I wouldn't ever use it in that situation if it was possible that the input was very large, it's very inefficient both in its use of memory and time. But I just discovered it! Let me be!

This time, I did actually open the file instead of copy pasting it into a string and then splitting it into a list because I was too lazy to hit save as.

reports = []
with open("input.txt") as file:
for line in file:
reports.append(tuple([int(i) for i in line.split()]))

Again... I know reading everything into memory isn't always the move, but we do know the size of the input here, so I think it's all good.

And... that's it for part 1.

print(sum([1 for report in reports if isSafe(report)]))

Oh... and part 2 adds a whole new level of complexity, right?

Well, I'm in class right now, so I might have to do something lazy.

def dampener(levels: tuple[int]):
if isSafe(levels):
return True

for i in range(len(levels)):
if isSafe(levels[:i] + levels[i+1:]):
return True

return False

I'm... not sure if that's efficient at all. Looks to be O(N^2)... does it get better than that? I'm unsure. Maybe we can do some dynamic programming here, but with the input size being single digit, I'm not sure that's worth it.

print(sum([1 for report in reports if dampener(report)]))

That's it.

But wait, what if it's super slow? 

So we know the isSafe function is like... the most simple operation that needs to be done here. And it's O(N). Let's see how many times isSafe is called with and without the dampener.

I modified the isSafe function a tiny bit, with a global variable counter that it's going to add to each time its run. 

safe = {1, 2, 3}
counter = 0
def isSafe(levels: tuple[int]) -> bool:
global counter
counter += 1
increasing = True
decreasing = True
for a, b in zip(levels, levels[1:]):
if abs(a - b) not in safe:
return False
if a > b:
increasing = False
if b > a:
decreasing = False
if not (increasing or decreasing):
return False
return True

And then ran

print(sum([1 for report in reports if isSafe(report)]))
print(counter)
counter = 0
print(sum([1 for report in reports if dampener(report)]))
print(counter)

Which gives us

257 1000 (counter after running without dampener... i.e. number of reports in input) 328 5589 (counter after running with dampener)

See... that's not too bad! 

Might come back and try and implement a faster way.






Comments