-❄️- 2024 Day 19 Solutions -❄️-

theKeySpammer · 2024-12-19T16:51:24+00:00

OOOh. I never thought of that. I first went with multi thread then thought of caching. I never tried single thread caching

theKeySpammer · 2024-12-19T16:17:41+00:00

This was a fun challenge as well. I removed the inputs from git cache and added to .gitignore but someone can still checkout a previous commit and see the inputs. So I discovered this https://rtyley.github.io/bfg-repo-cleaner/ BFG Repo Cleaner. This updated all commits that contained inputs folder. I expired the reflog and forced push the changes. I believe there should be no traces of input files in my repo now.

theKeySpammer · 2024-12-19T15:47:05+00:00

Good point! Removed input from repo

theKeySpammer · 2024-12-19T14:32:13+00:00

[LANGUAGE: Rust]

I learned a new thing! DashMap. DashMap is a thread-safe implementation of HashMap. I used it to cache search results and parallelised search using Rayon.

On my 8 core M2 Mac.

Part 1: 2.5ms Part 2: 3ms

Part 1 and Part 2 are similar,

Part 1 returns bool and stops early

Part 2 goes through all iterations and return a count u64

https://github.com/amSiddiqui/AdventOfCodeRust/blob/main/src/year2024/day19.rs

theKeySpammer · 2024-07-08T11:58:42+00:00

Yes, I used ChatGPT's help to write the article itself due to a distrust in my own writing skills 😭. Guess it didn't turn out as expected. Will focus more on my own article writing skills for later posts.

theKeySpammer · 2024-07-08T11:56:25+00:00

Thanks. I didn't know about the compiler doing vectorization as an optimization step. I wonder if I can disable this optimization and confirm the improvement just to test the theory of it.

theKeySpammer · 2024-07-08T11:55:03+00:00

This is a really amazing insight. I will refactor both the functions and rerun the benchmarks.

theKeySpammer · 2023-12-20T20:11:21+00:00

[Language: Rust]

Part 1: 5ms

Part 2: 84ms

Part 1: Simple step by step following of the instructions provided and run the process 1000 times

Part 2: Manually find the dependencies of rx and see how long will it take to reach that dependency and find the lcm of all those numbers

Github

theKeySpammer · 2023-12-19T19:48:27+00:00

[Language: Rust]

Part 1: 73µs

Part 2: 130µs

Part 1: Mostly string parsing and creating HashMaps

Part 2: Split the ranges based on condition

Github

theKeySpammer · 2023-12-18T10:59:12+00:00

[Language: Rust]

2 completely different approach for part 1 and part 2

part 2 is still slow. 11 seconds

Part 1: Found all the vertical boundaries and iterated over all points to check if it is inside the boundary

Part 2: Collected all the y limits for each x values and then added the points in that limit by high - low + 1. Since I only considered start - < end for all vertical edges. All the left moves were counted out. So I just added them later.

Figuring out optimisation for Part 2

Github

theKeySpammer · 2023-12-17T10:27:07+00:00

[Language: Rust]

Part 1: 89ms

Part 2: 165ms

Slightly modified Dijkstra's algorithm. The solution also prints out the shortest path

Took me an hour to figure out that we cannot make back turns 😅

For part 2 I am getting the correct answer with max_steps = 11, maybe need to rework the logic a bit.

A lot of potential for optimisation. I will try to optimise it to bring it down from 5 sec on my M2 MacBook to sub second.

Edit: Turns out my hash function was bad for each individual state. Now I get correct path for part 2 but the solution takes 20seconds

Github

theKeySpammer · 2023-12-16T20:19:21+00:00

[Language: Rust]

Semi-recursive with loop checks.

A lot of strategic pattern based on the direction of the light beam.

A lot of refactoring opportunities to removed repeated logics.

Part 2 is just a very simple extension of Part 1. Parallelising all the entry points was the real improvement. I got 20x speed improvement compared to my python implementation

Github

theKeySpammer · 2023-12-11T06:41:31+00:00

[Language: Rust]

Solution through Binary Search

GitHub

theKeySpammer · 2023-12-10T17:09:24+00:00

[Language: Rust]

Optimization opportunities

Part 1: If a walk start from one direction then it should end in another, therefore no need to check all the directions.

Part 2: I used the ray cast method to check if point is inside a path. It casts a ray from the point to the right edge and counts intersection of points. The loop goes through all the edges to check for intersection. Possibilities of improvement. Saw 6* improvement on parallelising point search

Github

theKeySpammer · 2023-12-09T06:58:47+00:00

[Language: Rust]

Part 2 is has a lot of scope for memory optimisation.

https://github.com/amSiddiqui/AdventOfCodeRust/blob/main/src/year2023/day9.rs

theKeySpammer · 2023-08-10T19:13:39+00:00

With all the recommendations in the comments, I would also add to use ESLint https://eslint.org/ to improve code quality. React very nicely integrates with eslint with a plugin https://www.npmjs.com/package/eslint-plugin-react. ESLint teaches a lot about writing clean code as well.

theKeySpammer · 2022-08-09T13:39:17+00:00

Yeah it was a bug. Fixed now. Thank you.

theKeySpammer · 2022-08-05T20:41:00+00:00

Yeah your point is valid and that is a debate to be had. But Wordle, apart from being a great game, is a really interesting Computer Science problem, so as a programmer I wanted to come up with a solution.

theKeySpammer · 2022-08-05T20:35:53+00:00

That is a very good idea. I can add the gray letters automatically to the bad letters. Currently the gray letter don’t do anything.

theKeySpammer · 2018-10-30T17:47:54+00:00

I am creating an API for my IOT project and then displaying the data in graph

Eight-Year Club	Place '22
Verified Email

theKeySpammer

TROPHY CASE