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
18
votes
19
answers
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,310
3
votes
2
answers
220
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,417
10
votes
6
answers
825
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.3k
15
votes
7
answers
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.3k
16
votes
6
answers
1k
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,853
7
votes
4
answers
617
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,210
16
votes
11
answers
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.2k
8
votes
1
answer
289
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
15
votes
1
answer
314
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
32
votes
10
answers
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.3k
26
votes
18
answers
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.2k
13
votes
8
answers
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
21
votes
4
answers
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.3k
10
votes
3
answers
705
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 ...
- 19.6k
14
votes
10
answers
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 ...
- 19.6k