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
17
votes
18
answers
1k
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,220
3
votes
2
answers
217
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
818
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
615
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,192
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
288
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
311
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
703
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.4k
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.4k
20
votes
16
answers
2k
views
Is there a left-right connection?
Task
Given a square array of 0s and 1s, determine whether or not there exists a path of 1s connecting the leftmost and rightmost columns. A path can take steps of one unit up, down, left or right, ...
- 2,072
14
votes
5
answers
631
views
Road golf through the mountains
You have a bunch of cities on a grid which you wish to link up. Roads can be placed on any tile that doesn't contain a city, and connect to all roads or cities adjacent to them, vertically, ...
- 46.2k
22
votes
26
answers
2k
views
Delannoy numbers
Consider a grid from \$(0,0)\$ in the bottom-left corner to \$(m,n)\$ in the top-right corner. You begin at \$(0,0)\$, and can only move in one of these three ways:
Directly north \$(+0, +1)\$,
...
- 50.9k
18
votes
8
answers
2k
views
May the wind be always at your back
You are Odysseus, and are finally free from Calypso (who has kept you captive for many years) after you drugged her while she was sleeping1. You wish to return to your homeland of Ithaca, but the ship ...
- 771
5
votes
1
answer
408
views
2D Pathfinding with Momentum
You are piloting a spaceship, outfitted with an engine that can accelerate you at 1km/s^2 in the direction the ship is facing (you have very good inertial dampers). You also have thrusters which can ...
- 2,189
8
votes
8
answers
659
views
Coordinate Connecting
Input:
Ten unique integer coordinates, between (0,0) and (100,100).
Output:
The coordinates arranged in the order/an order such ...
- 1,194
15
votes
8
answers
2k
views
Can I exit the maze with this many bombs?
Inspired by this Puzzling challenge, and easier version of my previous challenge.
Challenge
A 2D rectangular grid is given, where each cell is either an empty space or a wall. You start at the top ...
- 79.3k
42
votes
8
answers
3k
views
Constructing an evil maze against random exploration
RollerCoaster Tycoon 2's maze is the inspiration for this question. Credit to Marcel Vos for thoroughly breaking the classic RCT2 AI. The pathfinding AI in this question is the AI in the latest ...
- 39.4k
13
votes
3
answers
519
views
Minimal cost path in wall-breaking maze
Inspired by this Puzzling challenge.
Challenge
Given a 2D rectangular grid where each cell is either an empty space or a wall, find the path (or one of the paths) from the top left cell to the bottom ...
- 79.3k
11
votes
0
answers
363
views
Cover positions with snakes of same 'colour'
Imagine a grid where the origin square \$(0,0)\$ is at the top left of the screen, and positive \$x\$ is rightwards whereas positive \$y\$ is downwards. Coloured squares are at various positions on ...
- 523
19
votes
3
answers
574
views
What is the fastest safe way down a mountain?
Intro
Help! I'm stuck on a snow-covered mountain and I need to get down as fast as possible, preferably without dying. I have a map showing how high each part of the mountain is above the normal ...
- 3,508
10
votes
11
answers
1k
views
Generate self-avoiding loops of a specific length
This question is a sequel to this one, working in the opposite direction.
For a reminder of terminology, the letters L, R, <...
- 7,405
25
votes
18
answers
3k
views
Remove loops from a walk
I've been playing around with a robot on the coordinate plane. This robot is able to tell me if it goes left, right, up, or down by reporting back a string consisting of the letters ...
- 7,405
15
votes
5
answers
495
views
Escape the Candlelit Maze
You find yourself in a strange place. A frighteningly dark maze, lit only by dim candles resting in the occasional hallway. Numerous paths lie only in impassable darkness, foreboding and-- ...Hm? What?...
- 251
7
votes
0
answers
362
views
Count the length of head movement
Once upon a time I wanted to order custom tokens for a board game. They say they can do it, and then they present me their price list. I was confused because they charge per inch of head movement, and ...
- 179
15
votes
11
answers
2k
views
Reach the number in minimum steps
In this challenge, you are given a number x. You have to find the minimum number of steps required to reach x from 1. At a particular point, you have two choices:
1) Increment the number by 1.
2) ...
- 179
9
votes
2
answers
545
views
Follow the Path, but is it valid?
Follow the Path
I got directions to my friend's house, but it looks like his map might have some mistakes. He's expecting me soon, so I need some short code to figure out if I can get there.
The ...
- 11.4k
18
votes
9
answers
2k
views
Find the shortest route on an ASCII road
You want to find the length shortest path between two points, on an 2d ASCII "map". The roads are made up of + characters, and the two endpoints are represented by <...
- 19.3k
26
votes
5
answers
1k
views
Can Jimmy escape the ghosts?
It is Halloween and Jimmy (/o\) has gone into a mysterious neighborhood for trick-or-treating (ask himself why). Now some evil ghosts are chasing him. Can Jimmy ...
- 5,997
37
votes
15
answers
5k
views
Unlock your Lock
You have locked your bike with a combination lock of 3 digits. Now you want to go for a ride and need to unlock it with the help of following program.
Input
1st parameter
The digit combination of ...
- 471
17
votes
3
answers
610
views
Bridge the Gaps
Given a black and white image with a white background and a set of black dots, paint a set of white pixels red, such that there is a path between each pair of black pixels.
Details
A path is a set ...
- 44.1k
8
votes
2
answers
515
views
Can the cursor reach the bottom?
In a matrix of characters, a cursor is a movable position between two adjacent characters, before the first character or after the last character in a line, like that "I"-shaped indicator ...
user85052
10
votes
4
answers
500
views
Cell phone Charge
Challenge Taken with permission from my University Code Challenge Contest
The dependence we have on mobile phones makes us charge them every night up to the maximum level of the battery, so we do not ...
17
votes
6
answers
804
views
Passwords Strong Against Bishops
Not to be confused with Password Bishop Goodness!
Given a string, answer (truthy/falsy or two consistent values) if it constitutes a password which is strong against bishops.
A password is strong ...
- 837
32
votes
4
answers
2k
views
A Turtle Finds a Portal
The turtle wants to move along the grid to get to his food. He wants to know how many moves it will take for him to get there.
As well since he is slow he has teleporters set up around his domain that ...
- 571
19
votes
16
answers
1k
views
Weight of the Least Weighted RoD Path
Let A be an m by n rectangular matrix of positive integers, where ...
- 9,777
15
votes
7
answers
1k
views
Get me out of here
Challenge
Given a grid size, obstacles' positions, player position and target position your task is to find a path for the player to get to the target and avoid the obstacles at the same time (if ...
- 967
15
votes
3
answers
705
views
Multi-level free parking space finder
Kids-related intro
Whenever I take my kids to an amusement park, the kids get more nervous the closer we are to the park, with the nerve peak when we are in the parking lot and find no place to park. ...
- 13k
24
votes
4
answers
1k
views
Paths & Wasting Time
Premise
So recently I was about half an hour early to an appointment, and decided to wait outside. I also determined that it would look strange if I just stood motionlessly in front of the house. ...
- 331
23
votes
2
answers
678
views
Roguelike pathfinding
Roguelike pathfinding
Your task will be, given a two-dimensional array of the elements described below, which represents a dungeon, to output or return a single number representing the amount of gold ...
- 331
24
votes
3
answers
865
views
Ice Golf Challenge
The goal of this challenge is to write a program or function that returns the least amount of strikes needed to complete a given course.
Input
The layout of the course can be passed in any suitable ...
28
votes
10
answers
2k
views
Alarm Optimization
My Alarm Clock
I'm American, and so is my (digital) alarm clock. To set the alarm, it starts at the time it was previously. Hitting the hour button moves it up one hour, and hitting the minute button ...
- 14.2k
10
votes
0
answers
112
views
Space Navigation [duplicate]
Oh no! There are a bunch of meteoroids on my way through the universe ... what am I and my space ship, the SP4C3, supposed to do?
I need to manoeuver my shuttle through these rocks or I am done for!
...
- 2,986
60
votes
9
answers
9k
views
Is my prison secure?
Your challenge is given an input of a prison layout to work out whether any of the prisoners can escape.
Input
Input may be in any reasonable format such as a string, array, array of arrays etc. The ...
- 7,269
28
votes
11
answers
2k
views
Triangular Manhattan Distance
The Manhattan distance on a regular grid is the number of orthogonal steps one needs to take to reach one cell from another. Orthogonal steps are those that go through the edges of the grid cells (as ...
- 198k