All Questions
Tagged with graph-theory path-finding
16 questions
7
votes
4
answers
573
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,864
32
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 ...
- 24.6k
2
votes
0
answers
149
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
<...
- 891
7
votes
1
answer
358
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 ...
- 42.6k
24
votes
5
answers
862
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 ...
- 197k
14
votes
3
answers
534
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 ...
- 241
24
votes
3
answers
487
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 ...
- 341
50
votes
3
answers
4k
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 ...
- 197k
8
votes
2
answers
264
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 ...
- 8,629
9
votes
2
answers
536
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, ...
- 93
10
votes
8
answers
889
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:
...
- 3,503
22
votes
10
answers
3k
views
Can the maze be solved?
Task
Print 0 if an n*m maze cannot be solved
Print 1 if an n*m maze can be solved (in 1 or more ways)
(so I'm not asking for ...
- 551
50
votes
6
answers
6k
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 ...
- 1,185
21
votes
1
answer
919
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 ...
- 1,943
40
votes
6
answers
6k
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 mine, ...
- 197k
14
votes
1
answer
1k
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:
...
- 21k