What specific things had they not learned in their CS education/which puzzles utilized them?
- When to use CFG versus regex for parsing. Many inputs could be parsed with regexes if you made certain assumptions and got lucky. But CFGs were much easier for some.
- Shunting-yard algorithm. This came up, I think, in 2018.
- Using fast/slow to detect cycles and cycle length (one step at a time versus two, when they collide you can determine that there is a cycle and then determine how long the cycle is). Most used a hash table/map but this was not effective (due to RAM requirements) for some very large inputs. This actually comes up a few times. Variants of game of life, or just numeric processes.
- Multi-threading. It was very useful to implement the intcode VM using threads in 2019. Everyone who tried to juggle state and run multiple VMs at a time struggled when we later had to have a large number of VMs communicating with each other.
- Maybe not CS proper, but typically covered as part of a CS curriculum in a discrete math course. Several times problems related to modular arithmetic and permutations came up. If you understood them, the problem was tractable. If not, you struggled and maybe solved it but it wasn't efficient.
- Various graph and search algorithms. Particularly A* and Dijkstra's. Looking back, it seems there were a couple maze ones in 2019 and several more maze/path finding ones in 2018.
- Sorting/ordering of graph nodes, specifically topological sort. If you know what it is, it makes several of the problems much simpler over the years. I think it was specifically used in 2018.
I have no formal CS training, but did a lot of online courses and so I use events like this to help plug gaps and learn new languages, and it would have been great to have a mentor like yourself through some of these puzzles last year as it can be quite hard to solve algorithm knowledge gaps etc. when also quickly trying to roll your own solutions.
Still, really a cool thing. I couldn't resist starting again today.
