Advent of Code 2022 Day 6 Solve

Recording of me solving day 5 of Advent of Code 2022 in Python. Finished rank #64 and #35 for each part.

Finish times:
Part 1: 1:41
Part 2: 1:54 (+0:13)

I definitely went a bit slower on part 1 than I could've today, actually trying out a sample input -- I was really worried about an off-by-one, and whether it wanted the number of characters until the first 4-distinct-character-block, or the number of characters including that, etc., which looks like it paid off since if I hadn't done that I would've been locked out for a minute.

There's a nice rolling window solution for this problem that was totally unnecessary for inputs of the size given, but I wanted to go over it anyways, and today was a short day, so I spent a good chunk of time talking about this approach near the end of the video.

I didn't actually mention in the video *why* this alternate solution is better / more efficient: in terms of time complexity, if the length of the string is n and the number of distinct characters you need is k, then the "naïve" solution is O(nk) (what I did was technically O(n^2) since I kept slicing the string, but this is a pretty simple change if I wanted it to be O(nk)) and the more efficient solution is O(n). This is because to update the rolling window and check if we've met the distinct condition, which we do each iteration, only takes O(1) in the rolling window approach compared to the naïve approach.

0:00 - Part 1
1:47 - Part 2
2:02 - Commentary
3:56 - Explanation
7:27 - Alternate Solution

[rastislavsvoboda]

def solve(text, part):
n = 4 if part == 1 else 14

line = text.strip()
for i in range(len(line) - n):
if len(set(line[i:i + n])) == n:
return i + n

return None