Search

Hey everyone! Thought I would do a post ahead of the event to cover the major topics that will probably come up

---

What is Advent of Code?

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

Each day will have two different puzzles that must be solved in order (you get access to the second after solving the first). Each puzzle has the same backstory but each person has different input they get for that puzzle.

Puzzles are released every day at midnight ET and can be completed anytime after they are released (but people who solve them quicker after theyre been released get more points for the site leaderboard)

(Puzzles are on https://adventofcode.com)

---

What can I post here?

Anything relating to the event! Whether that be a meme, asking for help, sharing solutions, etc.

How should I format my post titles?

Try to keep titles in this general format:

> [help, etc. category if applicable] [YEAR Day # (Part X)] [programming language if applicable] Post Title

For example:

> [2023 Day #5 (Part 3)] [Rust] My attempt at a solution

Another example:

> [Help] [2023 Day #2] What does this sentence mean

This helps people avoid spoilers and lets people use it as an archive by searching if they find out about the event in the middle and are starting from the beginning then

Should I post in the solution thread or separately?

If its just a solution try to keep it in the solution megathread so the community doesn't get spammed with solutions! If you add something onto that such as a doing a visualization, making it a meme, or etc. though feel free to post it separately

What can I post in the solution megathread?

The top level comments in the solution megathread should be solutions to that day. If you want to write something that is not a solution feel free to make a new post about it.

Any replies to top level comments though can be whatever

---

Lemmy-UI doesn't handle code blocks well, what do I do?

I pushed an update to lemmy-ui that adds code block support that will be arriving to all instances in version 0.19. This is currently in release clients and I expect it to release in the middle of the event.

For now though feel free to mirror any code you post onto some other site such as pastebin. if you can try to do both code blocks and pastebin to future proof it for when 0.19 eventually drops

To make a code block make three backticks, make a new line and put the code on lines, then put a newline and do three backticks on that

e.g.

\\\ console.log('Hello World') \\\

becomes

console.log('Hello World')

If your instance decided to beta test 0.19 you might be able to see code blocks already on the site, I put a code block above and in the sidebar so if one of those renders for you you have code block support

If youre using an app instead of the site though this section does not apply to you and depends on whether the developer of your app has added code block support or not

Anybody got some ideas to optimize today? I've got it down to 65ms (total) on my desktop, using A* with a visitation map. Each cell in the visitation map contains (in part 2) 16 entries; 4 per direction of movement, 1 for each level of straightaway. In part 2, I use a map with 11 entries per direction.

Optimizations I've implemented:

• use a 2D array instead of a hashset/map. No idea how much this saves, I did it in the first place.
• the minimum distance for a specific cell's direction + combo applies for higher combo levels as well for part 1. For part 2, if the current combo is greater than 4, we do the same*. Gains about 70(!!) ms
• A* heuristic weighting optimization, a weight of about 1% with a manhattan distance heuristic seems to gain about 15 ms (might be my input only tho)

*Correctness-wise: the reason we're splitting by direction is because there's a difference between being at a cell going up with a 3 combo but a really short path, and going right with a 0 combo but a long path. However, this is fine because a 3 combo in the same direction as a 0 combo is identical, just more restrictive.

Optimizations that could be done but I need to ensure correctness:

the same optimization for the combo, but for directions. If I'm on a specific combo+direction, does that imply something about the distance for another direction? Simply doing the same for every non-opposite direction isn't correct

Code: https://codeberg.org/Sekoia/adventofcode/src/branch/main/src/y2023/day17.rs

Warning: quite ugly, there's like 8 copy-pastes for adding to the queue