Day 10: Adapter Array
I had a really hard time with this and felt quite stupid at several points. Part 1 took only 10 minutes to solve, but part 2 took literally 5 hours straight. Initially I spent a long time struggling with the combinatory approach before realising that it would never work due to the time complexity required to enumerate all solutions. Eventually, I realised that you can walk over the sorted list of adapter values and look at a window of five elements. If the difference between the first and last is 4, that means the five elements are all sequential numbers, and that you can drop any combination of the middle elements except all three of them, which would violate the "maximum adapter difference = 3" rule. That means, considering it as a boolean problem with three bits that can take any value other than 111, there are seven possible combinations. However, if you don't have five sequential adapter values, then you should just look at whether one element can be dropped without violating the rule, before sliding the window forward by one element and continuing until you've reached the end.
Afterwards, I looked at a couple of other people's solutions (if I remember which ones were good, I'll post them here) and saw a mention of dynamic programming as a more general method of solving it. I don't remember covering DP in undergrad compsci back in the 2000s, but we did do a fair bit of graph theory which would also probably have been a good way to approach this. After a few struggles like today, I'm seeing a recurring issue I tend to run into with these problems: I don't follow a systematic method of understanding and solving them, and instead have to reason about each one from scratch, which usually means coming up with quite inefficient and naieve solutions that need lots of trial and error and head-scratching to manipulate into a useful program.
In my experience of programming in industry, about 95% of my time is spent either in meetings, searching for information, or configuring and wiring things together (e.g. editing Kubernetes YAML manifests), rather than writing "pure" problem-solving code like this, which means it's possible to go through your career without ever really developing good skills for the core problems of computation. This situation feels very unfulfilling, so I'm going to start regularly exercising these problems and going through more of the algorithmic and computational problem-solving literature.