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 Nordern on 2024-12-06 at 22:53

@felyashono @teotwaki My solution is in Typescript/Javascript, does a bunch of unneeded object allocations and still brute-forces in half a second on a base M1.

I'd say something odd is going on to hit the minutes in a compiled language...

=> More informations about this toot | More toots from nordern@chaos.social

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

@nordern @teotwaki

I assume by "brute-force” we're all talking about trying to place an obstacle on each of the 5,000+ points on the original path.

Are you also re-running the entire patrol route in each case afterwards to check for loops? I re-run it from the start, breaking it if the guard leaves the map or encounters the same tile a second time while facing the same direction.

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

Written by Nordern on 2024-12-06 at 23:04

@felyashono @teotwaki Yes, you walk through the map once to find all relevant points, iterate through all the points, put an obstacle there on a copy of the original map, let the guard run on that until you hit a loop or the bounds.

=> More informations about this toot | More toots from nordern@chaos.social

Toot

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

@nordern @felyashono I guess one way to optimise it further would be to memoise the path simulation. You only need to check the guard’s decisions when its path is aligned on either x or y axis with the new obstacle. Haven’t figured out how to implement that, though.

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

Descendants