The 2024 Developer Survey results are live! See the results

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
Filter by
Sorted by
Tagged with
753 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 ...
• 78k
943 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 ...
• 78k
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,723
567 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,839
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 ...
• 39.6k
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
286 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
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 ...
• 24k
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: ...
• 39.6k
1k views

• 523
535 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,448
904 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
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
436 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
335 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 ...
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
515 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 ...
• 10.3k
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.8k
879 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
5k views

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
546 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.9k
484 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 ...
468 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 ...
744 views

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 ...
• 797
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
1k views

Weight of the Least Weighted RoD Path

Let A be an m by n rectangular matrix of positive integers, where ...
• 9,757
960 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
657 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
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
614 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
783 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 ...
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 ...
• 14k
110 views

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,966
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,219
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
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