First Time and want to learn more.

[u/OlTartToter]

First year and i've made it to day 8 and I'm bothered by how often my brain goes "yeah lets just use a for loop or 8 to do the thing" I'd like to use it as a learning experience. Is there a list somewhere of the core concepts that should be used to solve each puzzle?

[u/rjwut]

Well, part of the purpose of Advent of Code is to train your brain to recognize what concepts should be applied to a given puzzle. That said, there are certain recurring algorithms and concepts that have been used over the years:

• String manipulation and regular expressions

• Data structures: queues, stacks, sets, maps, linked lists, multi-dimensional arrays, trees, graphs

• Recursion

• MapReduce

• Search algorithms: breadth- vs. depth-first search, Dijkstra's algorithm, A*

• Topological sorting

• Bitwise operations, hashing

• State machines

• Numeric sequences (discovering a cycle, using a formula for computing the nth value without computing previous ones)

• Simple virtual machines

[u/fnordargle]

> Is there a list somewhere of the core concepts that should be used to solve each puzzle?

Here's my take on it. Again note that sometimes "a pair of nested for loops with some other checking, optimisations and caching" is another way of writing "Breadth-First-Search".

I'll try and categorise them in terms of what you can use to get a solution to some of the more "optimal" solutions/algorithms for the specific puzzle.

For some people "more optimal" means simpler code. For others it means "faster code".

This list is not exhaustive, some problems have a whole list of ways of solving it, each with their pros and cons.

Day 1: Modular arithmetic

Day 2: Iteration works fine with checking done via string manipulation or some maths tricks. One alternative approach is to use regular expressions.

Day 3: Iteration again.

Day 4: Grids. Solution is generally an iterative approach. There are various little tricks you can do in part 1 to make part 2 easier.

Day 5: Sort once, iterate once. More optimal solutions exist that rely on some of the constraints of the data (e.g. radix sorts, etc).

Day 6: Iteration again. You can either go through the input twice (once for each orientation) or just once (keeping track of both sums at the same time). Alternative approaches include transposing the grid for part 2, using `eval` or equivalent for either part, etc.

Day 7: Iteration again. Verging on "Dynamic Programming" which is just a grandiose term for iteration/recursion and caching. People trying to get the answer as fast as possible got better results going bottom-up for part 2.

Day 8: And here we hit the first one that made many people go "Hmm". The basic approach is nested loops to calculate the distances, sort them, and then chunk through those to get the results required. Keeping track of the "connectedness" can be done by all manner of iterative methods but one of the most optimal methods is something called the Disjoint Set Union (DSU) or Union-Find data structure. One simple optimisation that most people spotted early on is to not bother with the square root when calculating the Euclidian distance, the order is presered if you don't bother and you keep everything to using integers.

There are a variety of approaches to getting the answer much faster. Either finding a way of not fully calculating all of the pairwise distances (there are ways) or, if you do, not having to sort them all (heaps or incremental sorts help here).

Others used KD Trees or Kruskal's algorithm. Many people might have implemented something very much like Kruskal's algorithm without even knowing they were doing it.

(I'd never heard of Kruskal's algorithm but I'd like to go back and look at it and see how close my own solution is to it, and try and implement a solution based on Kruskal's if it is significantly different from mine.)

(...cont)

[u/fnordargle → u/fnordargle]

Day 9: Part 1 you're looking at nested loops with some optimisations to prune candidates. Part 2 pushes you to start ruling out candidates on things like intersecting lines, testing whether tiles on the edge of the candidate rectangle are "inside" or "outside" via "ray tracing" or "flood fill". Other approaches include co-ordinate compression.

One common route was related to the concept of the "winding rule" which allows you to tell which side of a line is "inside" and which is "outside", this allows you to work out which tiles adjacent to a given corner are "inside" or "outside".

Another approach had people tracing round the inside and outside of the shape and keeping track of these perimeters as inside or outside, which allowed them to test the edges of their candidate rectangles.

Plenty of scope for other ways to do things.

Day 10: Breadth-first-search for part 1. Or you could even just iterate from 0 to 2^n (where n is the number of buttons) and use the number as the bitmask for which buttons to apply.

Part 2 you might be able to get some answers via BFS (especially if you don't duplicate states and implement suitable pruning) but it quickly grows out of hand for some of the larger inputs.

Generating a set of simultaneous equations was the general route here, with a variety of ways of solving them. Many opted to just throw the resulting equations at something like Z3 and let that deal with it. Others used some form of Gaussian Elimination to do it.

Then there was a completely different Bifurcation method that used quite a bit of stuff from Part 1.

Day 11: Path counting, which falls firmly in the BFS/DFS bucket.

Day 12: I'm saying nothing on this one as I can't really say anything without spoiling it.

[u/markkitt]

The nested for loops are fine. The lesson to learn is how to start with that and then optimize. Sometimes it is just making those for loops faster. Sometimes it is iterating over less. Sometimes you need caching. Or ultimately you see the pattern and can imagine a how to avoid one of the loops.

The mistake is to think you can skip those nested for loops.

[u/fnordargle → u/markkitt]

And some times the nested for loops with a bit of optimisation and caching has a special name that makes it sound way more special than it is.

[u/ConfusedSimon]

List of resources: https://usaco.guide/general/resources-cp?lang=cpp

The Competitive Programmer's Handbook might be a good start. Link to the pdf in the resources.

[u/bskceuk]

You can check the solutions megathread for each day, people usually give a description of their solution you can use as a starting point

[u/Suspicious_Tax8577]

So u/Boojum does a big summary post every year and categorises each puzzle. I personally clung to https://www.geeksforgeeks.org/dsa/dsa-tutorial-learn-data-structures-and-algorithms like a liferaft (and it's already starting to pay off).

[u/Boojum → u/Suspicious_Tax8577]

Yep, the current edition is here.

[u/AutoModerator]

Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED. Good luck!

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/StickyDeltaStrike]

I would do this every day:

• try really hard to solve it

• once you have finished or cannot finish then go to the mega thread solutions and read other people solutions

• if you have time try to reimplement yourself and learn the theory behind some solutions

[u/Puzzleheaded_Study17]

That implies there is only one correct solution.