Questions tagged [path-finding]
Problems in geometry or graph theory that involve finding an optimal (e.g. shortest) path, subject to constraints (obstacles).
135
questions
10
votes
6
answers
741
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 ...
- 76k
15
votes
7
answers
927
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 ...
- 76k
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,683
7
votes
4
answers
560
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 ...
- 3,829
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 ...
- 37.8k
8
votes
1
answer
217
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
277
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 ...
- 10.8k
31
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 ...
- 23.7k
24
votes
17
answers
2k
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:
...
- 37.8k
13
votes
8
answers
1k
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,655
19
votes
3
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 ...
- 76k
10
votes
3
answers
623
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 ...
- 15.9k
14
votes
10
answers
965
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 ...
- 15.9k
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, ...
- 541
13
votes
4
answers
463
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, ...
- 37.8k
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)\$,
...
- 49.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
359
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,135
8
votes
8
answers
579
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,184
14
votes
7
answers
1k
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 ...
- 76k
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.1k
13
votes
3
answers
414
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 ...
- 76k
11
votes
0
answers
272
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
533
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,398
10
votes
11
answers
901
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,387
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,387
14
votes
4
answers
405
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?...
- 241
7
votes
0
answers
331
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 ...
- 169
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
514
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 ...
- 9,348
14
votes
6
answers
1k
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 <...
- 18.7k
25
votes
4
answers
875
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,957
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
538
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 ...
- 43.8k
7
votes
2
answers
476
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
467
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
742
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 ...
- 793
30
votes
3
answers
1k
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 ...
- 551
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,757
15
votes
7
answers
958
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
649
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. ...
- 12.9k
22
votes
3
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. ...
- 311
23
votes
2
answers
607
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
780
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 ...
- 13.8k
10
votes
0
answers
110
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,946
59
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,209
27
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 ...
- 197k
31
votes
2
answers
1k
views
Office Escape: Plan your way out!
It's the final sprint... and half your team is off ill. You're working late, just making your last commit for the day, looking forward to... why have the lights turned off? I don't remember the ...
- 3,888
43
votes
6
answers
2k
views
Island Golf #1: Circumnavigation
This is the first in a series of Island Golf challenges. Next challenge
Given an island in ASCII-art, output an optimal path to circumnavigate it.
Input
Your input will be a rectangular grid ...
- 39.4k