this post was submitted on 16 Dec 2024
12 points (100.0% liked)
NotAwfulTech
386 readers
5 users here now
a community for posting cool tech news you don’t want to sneer at
non-awfulness of tech is not required or else we wouldn’t have any posts
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
20: currently a WIP but:
meme
Wait, so it’s all grids? 🧑🏿🚀🔫🧑🏿🚀Skipping this for now, there are only so many grid maps I can take.
Understandable, have a nice day
ok disco
It took me too long to read the prompt and see that without the shortcuts, it's a single path. I wasted too much time on search algorithms.P1: Here's what I did: Walk the path. Every time you hit a new grid, check if the two shortcuts you can take will save you 100 ps.
To calculate the shortcut saving:
If you index every grid position on the main path from 0, then it takes X ps to reach position X, The time it takes to travel from start to X, then a shortcut to Y, then from Y to the end, is X + 1 + (main path length - Y). The time saved is then just Y - X - 1, modulo maybe like 5 fence post errors.
P2. The prompt wasn't really clear about whether or not cheating meant you can only travel through one set of walls before your cheat ends, or if it meant you could just move through walls for 20ps to wherever you could reach. Turns out, it's the latter.
The above formula is then a special case of Y - X - manhattan distance(X, Y).