Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [path-finding]

Problems in geometry or graph theory that involve finding an optimal (e.g. shortest) path, subject to constraints (obstacles).

15
votes
15answers
1k views

Weight of the Least Weighted RoD Path

Let A be an m by n rectangular matrix of positive integers, where ...
12
votes
6answers
646 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 ...
13
votes
3answers
429 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. ...
22
votes
3answers
980 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. ...
21
votes
1answer
409 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 ...
24
votes
3answers
699 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
10answers
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 ...
9
votes
0answers
100 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! ...
57
votes
9answers
8k 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 ...
25
votes
11answers
1k 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 ...
33
votes
2answers
913 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 ...
43
votes
6answers
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 ...
2
votes
0answers
132 views

Dynamic programming - decreasing number [closed]

The challenge You are given an integer n, and you have to use these operations to make it 1. Divide it by 3. Divide by 2. Subtract 1. Examples: ...
30
votes
5answers
1k views

Life is a Maze: We take the wrong Path before we learnt to walk

Input: A maze containing the characters: -- (horizontal wall); | (vertical wall); + (...
19
votes
2answers
515 views

Solve an Ice Maze

Ice mazes have been one of my favorite staples of Pokémon games since their debut in Pokémon Gold and Silver. Your task will be to make a program that solves these types of problems. Ice mazes ...
31
votes
7answers
1k views

Longest domino chain

Challenge description Dominoes is a game played with tiles with two values on it - one on the left, one on the right, for example [2|4] or ...
12
votes
3answers
732 views

Generate a map for a roguelike

Today, we'll be generating a map for a roguelike RPG! Example Map: ...
2
votes
0answers
95 views

All-pairs shortest return paths without reusing edges [closed]

All-pairs shortest paths is a standard pathfinding problem. This is a twist on that. Definitions We are searching for paths on a directed graph. Graphs are defined by square matrices, for example <...
9
votes
1answer
127 views

Shortest self-avoiding path given a sequence of turns

Write a program or function which, given a non-empty sequence of right or left turns, outputs the length of the shortest self-avoiding path on a 2D lattice with those turns. The input should be taken ...
23
votes
7answers
803 views

Distance Between Two Points Travelling on a Polar Graph Chart

Brief Problem Explanation Write a program to find the minimum distance between two points traveling only on rays emanating from the origin and circles centered on the origin. Explanation of Premise ...
14
votes
1answer
426 views

Taxicab in San Francisco

You are a taxicab driver in San Francisco. As is typical of taxicab drivers, you are navigating a grid where the only valid directions you can move are the left, right, up, and down. However, San ...
5
votes
0answers
229 views

Solve a Single Player Tron Game [closed]

Solve a Tron Game Tron is a great game, and if you haven't played it the internet has MANY online versions available. A fun challenge is to try to write an AI that plays Tron, which is normally much ...
24
votes
9answers
2k views

Traveling Pumpkin Problem

Background: Jack is a pumpkin that enjoys spooking the citizens of the villages near his pumpkin patch every Halloween. However, every year after someone lights the candle inside of him, he has a ...
17
votes
5answers
835 views

Wolves and Chickens

There's a river and there are wolves and chickens on one side of the river. They have a raft and they all need to get to the other side. However, the raft cannot travel on its own. The raft will sink ...
14
votes
1answer
346 views

Checkers: King Me?

Challenge: Given a checkerboard, output the smallest amount of moves it would take (assuming black does not move at all) to king a red piece, if possible. Rules: Red's side will always be on the ...
23
votes
2answers
899 views

A Mouse with Dynamite

You're a mouse. Your mouse friends have all been captured, and are unconscious and trapped in a maze that has only one entrance/exit. You happen to have a perfect map of the maze, so you can plot a ...
13
votes
5answers
512 views

Find the right path

Given a list of paths, output the correct path. Example of path: /\ ----+/ | - and ...
23
votes
3answers
1k views

The Burnt Pancake Problem

This challenge is related to Flipping Pancakes. You may have heard of pancake sorting, where a stack of pancakes is sorted by size by inserting spatula into the stack and flipping all of the pancakes ...
8
votes
1answer
288 views

Extendable Train Swapping Problem

Extended Train Swapping Problem Part 1: Normal Train Swapping Problem In the 1996 CCC (Canadian Computing Competition), the first Stage 2 problem was a Train Swapping Problem. You can visit the link ...
10
votes
4answers
347 views

A queen's walk across a spiral

In a far-off kingdom, a chess queen takes a daily walk across a spiral path, numbered from 1 to n, not caring to follow the spiral itself, but simply making queen's ...
4
votes
3answers
557 views

King of the Torus!

King of the Torus! Your job is to conquer the torus, but wait, there are multiple other players banded together in teams facing you! You will need to use your wit's to conquer the torus. There are ...
8
votes
2answers
622 views

Guard your can with your life!

Lets Play Kick The Can! Although Moogie is the current winner, if anyone can take his crown they are encouraged to do so Kick the can is a children's game. Involving one defender, and multiple ...
13
votes
8answers
1k views

Can Mario go to the end of this map

Create a program that determines, given an input of the path, whether Mario can reach the end, denoted by E, from the start, denoted by ...
10
votes
3answers
293 views

Ways to get to the number

Given the input of the first number and the second number (both positive integers, zero exluded), determine in how many ways could you make the second out of the first, using following actions: ...
4
votes
1answer
300 views

Let's play ASCII mini-golf [closed]

Let's play code golf... by playing golf. Input Your input will be a string consisting of #'s, an o, an ...
15
votes
4answers
338 views

Shortest paths in a divisor graph

Introduction In this challenge, we will be dealing with a certain infinite undirected graph, which I call the high divisor graph. Its nodes are the integers starting from 2. There is an edge between ...
22
votes
2answers
647 views

Find the treasure in a 2D dungeon

You are in a one-floor dungeon. There is a treasure which is protected by locked doors. Doors can be opened by finding the corresponding keys. Your goal is to find the shortest path to the treasure. ...
6
votes
2answers
897 views

Find the longest path, avoiding obstacles in a 2D plane

The Scenario You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can ...
16
votes
1answer
452 views

Help develop Alphys' newest puzzle!

Alphys, the Underground's Royal Scientist, has finished a prototype for a new puzzle. However, she can't seem to find anyone willing to test it. The rules of her puzzle are as follows: The goal is ...
21
votes
3answers
502 views

Follow incomplete directions

A friend of yours has given you directions to the best restaurant in town. It's a series of left and right turns. Unfortunately, they forgot to mention for how long you need to go straight ahead ...
14
votes
3answers
370 views

Longest path on a 2d plane

You are provided a set of arbitary, unique, 2d, integer Cartesian coordinates: e.g. [(0,0), (0,1), (1,0)] Find the longest path possible from this set of coordinates, with the restriction that a ...
22
votes
2answers
382 views

A Peak Experience: Quickly Visit All the Peaks

I am standing at point (0,0) in a H x W map where the altitude is represented by digits, for ...
10
votes
1answer
263 views

The autopilot mode

A helicopter starting at the top left corner is descending (in a 2D space, for the purpose of this question) towards the ground. It has an autopilot mode and a manual mode. The autopilot mode behaves ...
45
votes
3answers
612 views

Combination bike lock

The scenario After a long day's work slogging in the office and browsing stackexchange.com, I finally walk out the door at 16:58, already weary with the day. Because I am still only an intern, my ...
8
votes
0answers
359 views

Make a Frogger Solver

🐸🐸 You must make the shortest program to always find the optimal solution to a simplified Frogger game on a 9x9 grid. Course Elements: L - Log (Length: 3-4). ...
18
votes
2answers
305 views

Run-Length Racers

You will be given two pieces of input: a string in run-length encoded format defining the running track, and a capital letter representing the lane to start from. For example, the string "3a4A6b5B" ...
43
votes
2answers
3k views

Help, I'm trapped in a Sierpinski triangle!

Drawing the Sierpinski triangle has been done to death. There's other interesting things we can do with it though. If we squint hard enough at the triangle, we can view upside-down triangles as nodes ...
17
votes
2answers
531 views

Playing Billiards

In this code golf, you will have to determine the direction of the shortest shot that hits exactly n cushions before falling into a pocket. The billiard table is a 6 pocket pool table with the ...
10
votes
2answers
326 views

Crack the safe!

Inspired by https://puzzling.stackexchange.com/questions/24334/to-catch-a-thief You are given an n by n (...
21
votes
3answers
588 views

How varied is my obstacle course?

Background I have constructed a simple obstacle course by placing boxes in a rectangular room. Now I want to count the number of essentially different ways in which it can be solved. I need you to ...