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

learn more… | top users | synonyms

4
votes
1answer
206 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 @, and .'s. For example: ......@.. .....##.. ......... ......o.. . - playable golf course ...
14
votes
4answers
275 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 ...
20
votes
2answers
370 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
1answer
308 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 ...
13
votes
0answers
243 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 ...
20
votes
3answers
420 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
284 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 ...
10
votes
0answers
163 views

Find the quickest path to reach all of the peaks and go back to where I started

I am standing at point (0,0) in a H x W map where the altitude is represented by digits, for example: 1132 2221 1230 # H = 3, W = 4 I'd like to experience the views from every peak, which in ...
10
votes
1answer
249 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 ...
42
votes
3answers
387 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 ...
6
votes
0answers
180 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). When you hop on a log it carries ...
18
votes
2answers
276 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" ...
42
votes
2answers
2k 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 ...
16
votes
2answers
312 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
291 views

Crack the safe!

Inspired by http://puzzling.stackexchange.com/questions/24334/to-catch-a-thief You are given an n by n (n itself is optional input) grid filled with 0s and 1s (or any other character of your choice). ...
21
votes
3answers
532 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 ...
20
votes
5answers
645 views

Hexagonal maze time!

This challenge has an open 500 rep bounty by Thomas Kwa for a Hexagony solution Time for another maze challenge, but not as you know it. The rules for this challenge are a little different than most ...
48
votes
3answers
2k views

Black and White Rainbows

Given an image that has only black and white pixels and an (x,y) location that's a white pixel, color the white pixels based on their minimal Manhattan distance from (x,y) in a path that only involves ...
21
votes
2answers
362 views

Where'd that germ go?

Introduction You are a biologist studying the movement patterns of bacteria. Your research team has a bunch of them in a petri dish, and you are recording their activity. Unfortunately, you are ...
9
votes
1answer
425 views

Variant of racetrack with exact finishing point and zero terminal velocity

Introduction The challenge is a very interesting variant of the game racetrack and those two challenges: To Vectory! – The Vector Racing Grand Prix Program a Racing Car Source of this ...
2
votes
0answers
132 views

Coloring the switchboard red [closed]

Question If you are currently on a cell with a value x, you can move to any cell in the same row or column, provided it has a value y such that x > y. This move is called a switch. The ...
7
votes
1answer
189 views

The obstacle course

The obstacle course You are currently stuck in some kind of course and you have to escape. However, if you do not choose the fastest way then the exit will close in front of you. Your challenge is to ...
7
votes
2answers
198 views

The Black Pawn's Revenge

Objective The black pawn wants revenge. Plot out its last attack. Rules The black pawn (L) starts at the top row and moves downwards to the bottom row. Maximise points taken, indicating the path ...
16
votes
0answers
385 views

Generating Picture Mazes

Challenge Write a program/function that accepts an "image" and outputs a picture maze formed from that image. Input Your program should accept two arguments: I, the image to form the maze from S, ...
0
votes
1answer
246 views

The Truck Problem [closed]

I am a teacher who was given a problem a few years ago. Every year since I have given it to my advanced students as a bonus assignment, but in ~10 years only 8 solved it, each with a slightly ...
16
votes
2answers
528 views

How did the chicken cross the road?

Cluck cluck. No one knows why the chicken crossed the road, maybe there was a good looking rooster on the other side. But we can figure out how. Write a program, that, left to right, crosses this (or ...
16
votes
3answers
331 views

Toggle, Print, Repeat

This challenge is loosely inspired by the unimplemented esolang Pada. Consider an array of 8 bits, all initialised to zero. We'll introduce a very minimalistic instruction set to print arbitrary ...
32
votes
6answers
1k views

Can you reach this number by doubling and rearranging?

Inspired by this question on Math.SE. Starting with 1 you can repeatedly perform one of the following two operations: Double the number. or Rearrange its digits in any way you want, except that ...
7
votes
0answers
370 views

Settlers of Catan - Longest Road!

This is an endgame board of Settlers of Catan: Background: The roads (the long stick pieces) and the settlements (and cities) are rendered by the little huts. We encode the placement of these ...
11
votes
2answers
302 views

Finding Poly Nemo!

Oh no! Nemo, our small clown fish is lost in this ASCII ocean and his dad Marlin is trying to find him. Your task is to get Marlin to Nemo safely. But beware, we have a feeding frenzy Bruce on the ...
6
votes
1answer
328 views

Evening Commute Solver

I recently moved to an apartment overlooking the inner ring-road of town, and every day, a beautiful scene unfolds. The traffic lights are apparently so confusing (mostly because the Dutch are used to ...
14
votes
2answers
590 views

How do I get more Klotski in my life?

I really love sliding tile puzzles, but recently, I haven't had time for them. Hence, I need a program to give me my fix of sliding-tile puzzles, specifically Klotski puzzles. Your input will be in ...
16
votes
2answers
780 views

Help our robots reach the teleporter

UPDATE: Added a Python framework to get started. The space-station has been overtaken by crusher-bots. You must direct as many of our expensive and fragile tech-bots called "rabbits" to an exit ...
9
votes
2answers
372 views

Downhill Maze Solver

A downhill maze is given as a series of rows of space separated digits from 0 to 9 inclusive, plus one "S" and one "X", where the S denotes the start and the X denotes the finish. In a downhill maze, ...
16
votes
2answers
512 views

Food shortage in the Snakepit

Food shortage in the Snakepit For the first time in 35 years, the snakepit is running out of food. The inhabitant snakes now have to fight each other in order to survive this food shortage. Only one ...
21
votes
10answers
1k views

Grid-Routing Battle

NOTE: This challenge is currently dead, as I'm unable to install the languages needed to run a match. If someone else has the time and interest to do it, I'm not opposed. See the bottom of the post ...
9
votes
7answers
698 views

fourth grade math homework for the week: a most inefficient traveling salesman

My daughter had the following assignment for her math homework. Imagine six friends living on a line, named E, F, G, H, J and K. Their positions on the line are as indicated (not to scale) below: ...
10
votes
2answers
804 views

Build a Mining Robot

Your program will control a mining robot searching underground for valuable minerals. Your robot will tell the controller where you want to move and dig, and the controller will provide feedback on ...
103
votes
24answers
12k views

Lab Rat Race: an exercise in genetic algorithms

This is Fortnightly Challenge #3. Theme: Genetic Algorithms This challenge is a bit of an experiment. We wanted to see what we could do, challenge-wise, with genetic algorithms. Not everything may be ...
6
votes
0answers
103 views

Find the Straightest Path in a Maze [duplicate]

In this challenge, your job is to find the straightest path from point A to point B in a two-dimensional maze. This is very similar to finding the shortest path, which has been done to death, but ...
8
votes
0answers
358 views

Delivery Robots and Destroyer Drones

Program your robots to deliver packages in a warehouse infested with destroyer drones. Avoid the drones and get your packages to the right place as fast as you can. Delivery Robots There are ...
18
votes
7answers
2k views

Can maze be solved?

The puzzle Print 0 if a maze n*m can not be solved Print 1 if a maze n*m can be solved (in 1 or more ways) (so I'm not asking for paths but if it's possible to solve!!!) Input array(2d): ...
34
votes
9answers
3k views

Program a Racing Car

CONGRATULATIONS to @kuroineko. Wins the bounty for excellent speed (672 moves) on the Gauntlet track. LEADER:* Nimi scoring a lightweight 2129. Other entries are larger but showing some serious ...
7
votes
4answers
513 views

Algorithm - Costliest Possible Route in Grid Puzzle

Objective Find the most expensive path from the top-left of a square grid to the bottom-right such that its total cost is below a given threshold. Scenario You are given a square NxN grid. You are ...
8
votes
0answers
375 views

Keep my Trip Cool!

Challenge Walking around Marks and Spencers, I noticed that they had air conditioning units placed randomly around the shop. Wanting to keep cool, I wondered what was the easiest way to move around ...
20
votes
1answer
683 views

Can you hear me now?

Background You are a rich executive of a software empire. Your time is worth a lot of money. As such, you must always travel in the most efficient route possible. However, as an executive, you spend ...
48
votes
6answers
5k views

Your car only turns right!

Introduction You have the misfortune of being stuck in a runaway car on an obstacle course. All of the car's features are non-responsive, save for the steering system, which is damaged. It can ...
20
votes
1answer
765 views

Horror Movie Search Party

Plot: Jimmy is missing; we have to find him. We should split up. Plot twist: Jimmy is already dead. But, our cast doesn't know that, so they need to search the whole area anyway. There is an N ...
38
votes
6answers
4k views

To Vectory! – The Vector Racing Grand Prix

User CarpetPython posted a new take on this problem which puts a much bigger focus on heuristic solutions, due to an increased search space. I personally think that challenge is much nicer than ...
0
votes
1answer
229 views

Find the fastest swim relay (shortest path of unique nodes and types)

fastest relay time = lowest possible total integer value of (a freestyle swimmers time) + (1 breastroke swimmers time) + (another backstroke swimmers time) + (another butterfly swimmers time) Each ...