7 Things We Learned from Advent of Code 2022

Advent of Code is an annual event where the organizer publishes 25 interesting puzzles every day from December 1 to December 25. Each puzzle has two parts; you get a silver star for solving the first part and a gold star for solving the second part.

This year, 100+ Agodans participated in the Advent of Code event. We hosted a private leaderboard and a Slack channel where we shared solutions and ideas about the puzzle. This was an excellent opportunity for developers from multiple teams to interact and share ideas and solutions to the puzzle.

Here are some stats from Agoda in this year’s event

1. We beat our goal of getting 250 stars collectively and finished with over 1,500 stars.
2. Eight Agodans have solved all 25 questions and earned 50 stars.
3. 80+ Agodans solved at least one question.
4. 30+ Agodans got at least 20 stars.
5. Ilia Larchenko, our Senior Data Science Manager, made the global leaderboard on day 22.
6. The programming languages we used to solve the problems include:
   Kotlin, Swift, C#, Python, Rust, Scala, Ruby, Javascript, Excel, and T-SQL.
7. Some also had fun creating animations for the puzzles. Here is one from day 10:

What We Learned

This year’s event covered interesting topics like modular arithmetic, cellular automata, taxicab geometry, graphs and trees, dynamic programming, heuristics, etc.

Here are some things the developers from Agoda found interesting while solving these puzzles.

1. Corners cutting can be useful (and fun) — Ilia Larchenko

I have participated in coding and math competitions before, but the Advent of Code is an interesting combination of both.

• Coding competitions or leetcode-like problems usually ask you to solve the problem in the asymptomatically optimal way and make a universal solution that works for any input and considers all edge cases.
• Math competitions and puzzles require you to find the elegant exact solution for a given problem or some trick that lets you get the answer without any coding.

But AoC problems are often different: you need to answer the question for a particular input using some coding, but you are not required to write the universal code or get the exact formula that always works. Sometimes, you needed to write an efficient solution but then tremendously speed it up by applying some tricks, e.g., dividing numbers by LCM in the 11th problem or finding a cycle in problem 17th.

On other days, the problems didn’t have a fast polynomial solution, but if you write an optimal enough code, you can still get an answer for the particular input in a reasonable time. In some problems, it was even enough to come up with an approximate solution that doesn’t necessarily guarantee the right answer but works faster than the “correct” one and still gives you the right answer for the given input. Maybe all these “corners cutting” tricks are not the best way to write code for production systems, but it is very fun to apply them to brainteasers.

2. Solving the Puzzles in Tsql

Solving the AoC puzzles using set-based T-SQL was an interesting experience. As someone with no math or CS background, it was a new experience for me to put on an algorithmic or mathematical thinking cap.

The main difference between set-based and procedural operations is that everything happens simultaneously, and iterating through an array/result set, one element at a time, isn’t an option. To be clear, T-SQL can work in a procedural manner with variables, loops, cursors, etc. I just chose to stick with set-based operations as a challenge to myself.

SQL Server has non-relational features that can help address unique situations much more efficiently than standard relational tables. Specifically:

• Graph Database — Very efficient in finding the shortest path between 2 nodes. Unfortunately, that’s about it. It can’t give you a list of all indirectly connected nodes.
• Spatial data types — Great for some visual puzzles, like day 15, where we had to find the sensors’ blind spot. Instead of checking whether each of the 4Billion squares is covered, I just created a polygon to represent each sensor’s coverage, concatenating them all into a single polygon, and compared it to a polygon representing the frame and extracted the difference. All of this took 15ms to run.
• Using SQL’s JSON parsing capabilities to parse strings — This I owe to this guy. It is very convenient to replace the unnecessary parts of a string with [, " and ] and then use json_value or json_query to extract the necessary data.

3. The hidden Complexity of Arithmetic operations — Ozioma Ogbe

When we write code to solve problems, we often assume that arithmetic operations like addition and multiplication take constant time, no matter how large the numbers are. That is not the case; the school book’s long multiplication method, for example, takes quadratic time. Finding an efficient multiplication algorithm is listed as one of the unsolved problems in computer science.

One of the steps for solving day 11 of the Advent of Code puzzles involved multiplying very large numbers, which made the naive algorithm’s runtime unrealistic. Solving this problem required identifying the multiplication of large numbers as a bottleneck and figuring out a way to reduce the magnitude of the numbers being multiplied.

4. Brute force is usually enough — Evgeniy Zuykin

Although I didn’t learn much from an algorithmic point of view, AoC does teach one thing to people coming from LeetCode-related platforms — brute force is usually enough. Also, a non-brute-force solution might not even exist. There were a bunch of problems that required recursion with memoization, which is considered a brute force, but also it required precise tweaking of parameters and further decision branching.

5. An opportunity to think outside the box — Mai Benchotidej

You can enjoy challenging yourself and finish the daily puzzles as fast as possible. You can also challenge yourself by using a new programming language that you have yet to use. When solving the puzzles, we should not forget common mistakes like integer overflow or that brute force solutions are not everything. For example, in the Tetris puzzle on day 17, we got five shapes that comes in sequence along with movement patterns, and we were asked to find the height of the blocks after a certain number of falling blocks.

It is easy to get the height of Tetris after dropping 2022 blocks, but when it becomes 1,000,000,000,000 blocks, what is the height of a Tetris tower? Brute force might be a good solution if we use a supercomputer with a high-speed CPU, but with a regular laptop, I had to think outside the box.

On some days, I had to rewrite my solution repeatedly. I got stuck for three days on the open valves puzzle on day 16; while I tried to figure it out on the second day, I heard myself saying, “leave the elephant here and just run”

I also needed clarification about the cube puzzle on day 20 and learned how to cut the cube shape differently.

6. Lots of Learning — Sujit Nair

This was my first time participating in such a global competition. It started as a fun and simple problem and became more challenging towards the final days. I was glued to my Mac by noon every day, just waiting for the next puzzle to be released. Few of my learnings and highlights:

1. The puzzles towards the final days of the competition taught me various ways to optimize my code by implementing dynamic programming.
2. It’s ok to take a step back and rethink the entire question. You may encounter questions that might give you multiple headaches. It’s ok to clean the slate, take a break and then redo the same problem with a different approach. Yes, I am talking about day 16 and day 24!!
3. Learn from others. On Reddit threads, where people share their daily solutions, you can learn new techniques for the same problem you have solved. In swift, for graph and tree questions, I found a new way to create nodes using “indirect enums” instead of the traditional classes, which was interesting.
4. Special mention to day 22, Part 2, Folding the cube and pathfinding question. To comprehend the question, I had to mimic the input structure onto a piece of paper, cut and fold it into a 3D cube, which, for a programming question, was so bizarre and exciting at the same time.

I enjoyed the overall experience and will participate in the next one!

7. Opportunity to Meet the Community — Nattadej Waiyatharee

Advent of Code was new to me. At first, I thought it might be another Leetcode problem, but it turned out to be easier and much more fun to solve. Even though most of the problems were solvable, I needed help with a specific problem, and I had to look for clues on communities like Reddit.
I found some great hints that led me down a rabbit hole where I discovered a bunch of “weird” things, like a specific compiler/runtime optimized for the AoC problems. It made me thrilled at that time.

Conclusion

Advent of Code was not only a great opportunity for coders to learn and solve new problems but also to come together and share as a community to better our problem-solving. That’s how our tech culture is at Agoda. We bring together the best of each field from all over the world to innovate and find solutions at scale. We hope to participate again this year and encourage you to join too!