Questions tagged [path-finding]
Problems in geometry or graph theory that involve finding an optimal (e.g. shortest) path, subject to constraints (obstacles).
137 questions
Score of 20
20
votes
22 answers
22
answers
1969 views
2k
views
Order a list by the difference of its elements
Task
Given an unsorted list of integers, order it in such a way that the absolute difference of every two adjacent elements will always be equal to 1:
\$|dx| = 1\$
There will be guaranteed one or more ...
- 3,790 reputation score 3790
Score of 3
3
votes
2 answers
2
answers
234 views
234
views
Winding a Queue
You will be given a matrix. It contains a ride exit (with a direction), some path, as well as some obstacles. Your goal is to build the longest possible queue line in that space, which connects the ...
- 2,405 reputation score 2405
Score of 10
10
votes
6 answers
6
answers
866 views
866
views
CGAC2022 Day 13: Santa's gift and the laser lock, Part 2
Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.
You successfully route the laser into the sensor, but nothing happens.
"What?" Frustrated, you flip the ...
- 79.8k reputation score 79784
Score of 15
15
votes
7 answers
7
answers
1130 views
1k
views
CGAC2022 Day 12: Santa's gift and the laser lock
Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.
There's a good news and a bad news.
Good news: you got a Christmas present from Santa. (Already?! Christmas is two ...
- 79.8k reputation score 79784
Score of 16
16
votes
6 answers
6
answers
1529 views
2k
views
Santa's Shortest Path Problem
Santa's Shortest Path Problem
Trying to be as time-efficient as possible Santa needs to plan his trips carefully. Given a 5X5 grid representing a map of villages it is your task to be Santa's flight ...
- 3,863 reputation score 3863
Score of 7
7
votes
4 answers
4
answers
628 views
628
views
Train Route Planning
We can model a rail network as a directed graph, where each node is a train station and each edge is a train connecting two train stations. We'll assume that each train travels between its ...
- 4,220 reputation score 4220
Score of 16
16
votes
11 answers
11
answers
2185 views
2k
views
Flood fill by distance
Say I have a grid with some obstacles:
----
| X |
| |
|XX |
| |
----
I can fill this with numbers, as distance from the top left corner. But, because ...
- 46.7k reputation score 46725
Score of 8
8
votes
1 answer
1
answer
310 views
310
views
Is this a Hamiltonian cycle?
There is a 3x3 square block made of 1x1 square blocks, with coins in each 1x1 block, starting from top left block you want to collect all the coins and return to top left block again, if possible ...
- 619 reputation score 619
Score of 15
15
votes
1 answer
1
answer
320 views
320
views
Shanghai ascii game sticks
Remove one stick and output the stack updated.
Description
You can remove only sticks on top( completely drawn).
You can assume:
there are 5 sticks on the table.
there's one and only one stick you ...
- 11k reputation score 10994
Score of 33
33
votes
10 answers
10
answers
4898 views
5k
views
Who Is Kevin Bacon?
You may know the game The Six Degrees of Kevin Bacon, based on the conjecture that every actor in Hollywood can be connected to Kevin Bacon by no more than 6 "co-star" relations, so Kevin ...
- 25.6k reputation score 25597
Score of 26
26
votes
18 answers
18
answers
2735 views
3k
views
Is the room lit up?
Imagine you have a grid where some squares are walls, some are empty, and some are lights that shine for arbitrary distances in the four cardinal directions until they meet walls:
...
- 46.7k reputation score 46725
Score of 13
13
votes
8 answers
8
answers
1598 views
2k
views
Find the number of paths in a n×n grid
Information
Given a non-negative odd integer (let's call it \$n\$), find the number of all possible paths which covers all squares and get from the start to end on a grid.
The grid is of size \$n\$×\$...
- 1,665 reputation score 1665
Score of 21
21
votes
4 answers
4
answers
1903 views
2k
views
Crossing a river with weird animals
Background
One kind of river-crossing problems involves two kinds of animals. One such problem reads like this: (all wordings, including animal species, are arbitrary)
A farmer has to cross a river ...
- 79.8k reputation score 79784
Score of 10
10
votes
3 answers
3
answers
715 views
715
views
Follow the border
Inspired by Is this Flow Free puzzle trivial? by @Bubbler. Lengthy chunks of this challenge are borrowed from there. This may be one step of a solution for the linked challenge, depending on chosen ...
- 20.2k reputation score 20219
Score of 14
14
votes
10 answers
10
answers
1190 views
1k
views
Revert Flow Free puzzle
Inspired by Is this Flow Free puzzle trivial? by @Bubbler. Lengthy chunks of this challenge are borrowed from there. This may be one step of a solution for the linked challenge, depending on chosen ...
- 20.2k reputation score 20219