🧵 How to best navigate a grid?
Anonymous at Sat, 16 Nov 2024 05:22:06 UTC No. 16477499
I don't know if this is the correct board to post this, it is something that has been bothering me for a while and I'm dumb.
See the picture, I need to find a path that goes from one point to the other. Assuming the line can only follow the grid, what is the path that will result in the smallest distance travelled, and why?
Anonymous at Sat, 16 Nov 2024 05:32:55 UTC No. 16477505
All paths that go down and right in any order are the same length.
If you find this interesting, it happens to have an entire field of study: https://wikiless.org/wiki/Taxicab_g
Anonymous at Sat, 16 Nov 2024 06:13:55 UTC No. 16477538
>>16477505
This dude is right in what he's trying to say (although you can get to a lot of unwanted places by random combinations of down and right). If your real problem is more general, you need a pathfinding algorithm. Look them up, see what's suitable to your task.
Anonymous at Sat, 16 Nov 2024 07:18:39 UTC No. 16477564
>>16477499
https://en.wikipedia.org/wiki/Bread
Anonymous at Sun, 17 Nov 2024 04:48:51 UTC No. 16478586
>>16477505
>All paths that go down and right in any order are the same length.
On the other hand, if we can add another constraint like minimizing turns then we will be able to find an optimal path
raphael at Sun, 17 Nov 2024 22:59:08 UTC No. 16479908
>>16477499
just use brute force nigga
raphael at Sun, 17 Nov 2024 23:00:08 UTC No. 16479910
>>16479908
then extract from the simulation the lowest distance traveled
Anonymous at Sun, 17 Nov 2024 23:00:42 UTC No. 16479912
>>16477499
Just use A*. A* (or really any Dijkstra's derivative) will work.
Anonymous at Mon, 18 Nov 2024 04:23:32 UTC No. 16480201
>>16478586
There are still two optimal paths in that case: you can either go down-right or right-down.
>>16477538
>>16479912
Not what OP asked.
Anonymous at Mon, 18 Nov 2024 04:26:05 UTC No. 16480203
>>16479908
>just use brute force nigga
>>16479908
>then extract from the simulation the lowest distance traveled
only the tiniest, smoothest of brains' first instinct is to rush and program a 'simulation' instead of actually thinking critically about the problem
fucking idiot
Anonymous at Mon, 18 Nov 2024 05:07:34 UTC No. 16480221
>>16477499
catalan numbers
/thread
Anonymous at Mon, 18 Nov 2024 12:55:38 UTC No. 16480617
>>16477499
This is some leetcode question, ask /g/
Anonymous at Mon, 18 Nov 2024 13:34:42 UTC No. 16480670
If you're walking in a city, try to keep the remaining number of horizontal crossings and vertical crossings the same, so your path resembles a diagonal than an L. The distance traveled isn't shorter, but you won't waste time waiting for the light to change since you're conserving the option to adjust your path.
raphael at Mon, 18 Nov 2024 23:41:51 UTC No. 16481442
>>16480203
can i solve it just draw stairs retard it goes diagonal
raphael at Mon, 18 Nov 2024 23:42:22 UTC No. 16481444
>>16480203
i can solve it retard just draw stairs
Anonymous at Tue, 19 Nov 2024 00:00:35 UTC No. 16481459
Random walk