Ancestors

Written by Felyashono on 2024-12-06 at 21:25

I've completed "Guard Gallivant" - Day 6 - Advent of Code 2024 #AdventOfCode https://adventofcode.com/2024/day/6

[#]Swift

https://github.com/Felyashono/AdventOfCode24/blob/main/Day6.swift

=> More informations about this toot | More toots from felyashono@disabled.social

Written by Felyashono on 2024-12-06 at 21:30

I did Part 1 running the simulation step by step. I leveraged one key insight for Part 2: any new obstacle must be placed somewhere on the original path from Part 1. This reduces the search space from 19K to 5K (approx) tiles, and I brute forced it from there.

And the trick for detecting a loop was being on a previously traversed tile and facing the same direction.

Runtime was around 25 minutes single-threaded on an Apple M1 Pro.

[#]AdventOfCode #Swift

=> More informations about this toot | More toots from felyashono@disabled.social

Written by Felyashono on 2024-12-06 at 22:20

And I got the runtime down to 3.5 minutes by adding concurrency, running on the same 10-core M1 Pro.

[#]AdventOfCode #Swift

=> More informations about this toot | More toots from felyashono@disabled.social

Written by Sebastian Lauwers on 2024-12-06 at 22:41

@felyashono You should get much better speeds; my solution is running in 1.8s.

=> More informations about this toot | More toots from teotwaki@mastodon.online

Written by Felyashono on 2024-12-06 at 22:43

@teotwaki

Are you saying my code should be getting better speeds than it is, or that I should have optimized it more/better?

=> More informations about this toot | More toots from felyashono@disabled.social

Written by Sebastian Lauwers on 2024-12-06 at 22:47

@felyashono I haven’t looked at your code, and I don’t know swift, but I just think in general AOC solutions should run in a few seconds on commodity hardware. Your description of the problem/solution sounds similar to mine.

In Rust there’s a tremendous performance difference between debug and release builds. Could there be the same with Swift?

=> More informations about this toot | More toots from teotwaki@mastodon.online

Toot

Written by Felyashono on 2024-12-06 at 22:53

@teotwaki

Yes, and I built it for the debug target. I also haven't optimized the code in any way, and that means that I'm copying value-semantics data structures all over the place.

I wasn't expecting this code to be performant: I wrote it without optimization in mind, as a brute force solution, and then threw concurrency at the most expensive part.

I'm curious: what was your strategy, that got it done in under 2 seconds?

=> More informations about this toot | More toots from felyashono@disabled.social

Descendants

Written by Sebastian Lauwers on 2024-12-06 at 23:00

@felyashono don’t know if you read Rust, but here’s my solution: https://github.com/teotwaki/aoc/blob/main/2024/06/src/lib.rs

In essence, I have a hashmap with the locations of the obstacles and a hashset of visited locations/direction combo. The hashset is used to detect loops. I add one obstacle on every location along the path and simulate the route again. I remove some path locations as possible candidates by checking if they would send out of bounds.

=> More informations about this toot | More toots from teotwaki@mastodon.online

Written by Felyashono on 2024-12-06 at 23:07

@teotwaki

I suspect you just hit on a key optimization I hadn't bothered to apply: you use a hashmap for the locations of the obstacles. I use an array. I expect obstacles.contains(point-in-front-of-me) to run in O(n) where n is the number of obstacles. You expect it in O(1).

=> More informations about this toot | More toots from felyashono@disabled.social