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

learn more… | top users | synonyms

0
votes
0answers
39 views

Find the linked nodes in a list of tuples [on hold]

Suppose that we have a list of tupels like following : t=[('d','t'),('d','k'),('k','r'),('t','p'),('t','n'),('r','z'),('p','h')] this list is contain the nods of a graph with those parent in the ...
4
votes
0answers
181 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 ...
13
votes
2answers
464 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 ...
15
votes
2answers
594 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
293 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
428 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 ...
20
votes
9answers
896 views

Grid-Routing Battle

See the bottom of the post for a leaderboard. This is a semi-cooperative king-of-the-hill challenge, where the bots construct paths through a two-dimensional grid graph. The bot who controls the ...
9
votes
7answers
651 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: ...
9
votes
2answers
526 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 ...
93
votes
24answers
10k 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
87 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 ...
6
votes
0answers
239 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 ...
16
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): ...
31
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 ...
6
votes
4answers
404 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 ...
7
votes
0answers
341 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
618 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 ...
47
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 ...
17
votes
1answer
678 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 ...
34
votes
6answers
3k 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
211 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 ...
9
votes
2answers
427 views

Robots! Collect these pickles!

I seem to have gotten myself into a bit of a pickle. Literally. I dropped a bunch of pickles on the floor and now they're all scattered about! I need you to help me collect them all. Oh, did I mention ...
13
votes
9answers
648 views

Portal Maze Shortest Path

Your goal is to write a program that creates a random 10x10 map using 0, 1, and 2, and finds the shortest path from top-left to bottom-right, assuming that: 0 represents a grass field: anyone can ...
-2
votes
1answer
125 views

meeting point minimizing travel distance for participants? [closed]

The problem is to find the point minimizing the travel distance for around 100 persons in different regions who want to meet in the same place. Travel is by car not by plane. Assuming that I get ...
5
votes
3answers
480 views

Mouse in a room

There is a mouse in a room, in the top-left corner. It can move up, down, left, or right, and the mouse cannot go through any cell in the room twice. Given this, return all the possible paths in which ...
12
votes
1answer
1k views

Code Golf: What is the spaceship's fate? [ASCII art version]

Background In a galaxy (and possibly a universe) far, far away... there was a spaceship and a bunch of planets. A malfunction on board caused the spaceship to run out of fuel. It is now moving at a ...
4
votes
3answers
353 views

Calculate the total number of paths

Description There will be a grid of 9x9, where there will be placed 12 rocks. You will start at a starting-rock and walking with a starting-direction (north, south, west or east), whenever you see a ...
15
votes
1answer
804 views

I used to solve code golf puzzles like you, but then I took an arrow in the knee

Getting hit in the knee with arrows seems to be the injury of choice right now. As such, I propose the following golf challenge. You have an adventurer that looks like this: O /|\ / | \ | | ...
26
votes
3answers
1k views

Build railroad tracks and cheat the government

You are a railroad entrepreneur in the 19th-century United States when trains become popular because they are the most efficient means of transporting large volumes of materials by land. There is a ...
16
votes
5answers
701 views

Jumping and Running

Matthew likes solving puzzles. Whenever he manages to solve one he skips around happily. Recently he really needs to do this as a meteor shower has opened craters and holes in the ground in which he ...
12
votes
4answers
588 views

Textual maze solver

Given a maze on stdin and an entry point, write a program that prints a path to the exit on stdout. Any path is acceptable, as long as your program does not generate the trivial path (passing through ...
41
votes
7answers
3k views

Robot Finds Kitten

The challenge The shortest code by character count to help Robot find kitten in the fewest steps possible. Golfers, this is a time of crisis - Kitten gone missing and it's Robot's job to find it! ...
9
votes
1answer
586 views

Shortest path in a graph

Write a program to take a graph (from either standard input or a file, your choice) and find a shortest path in the graph. Graphs are specified using the following format: A---S F--T | / \ | | / ...