Problems relating to graph theory

learn more… | top users | synonyms

0
votes
0answers
49 views

Algorithm to find max no. of nodes that can be visited [on hold]

Given an undirected non-weighted graph edges. '1#2', '2#3', '1#11', '3#11', '4#11', '4#5', '5#6', '5#7', '6#7', '4#12', '8#12', '9#12', '8#10', '9#10', '8#9' where for example node 1 and node 2 is ...
28
votes
4answers
3k views

Infinite Labyrinths

Background You are the apprentice of a powerful wizard, and your master is currently developing a spell for creating an inter-dimensional labyrinth to trap his enemies in. He wants you to program his ...
9
votes
2answers
152 views

Count Maximal Fence Arrangements

Background I want to build a fence. For that, I have collected a bunch of poles, and stuck them to the ground. I have also collected lots of boards that I'll nail to the poles to make the actual ...
9
votes
2answers
287 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, ...
9
votes
7answers
641 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: ...
8
votes
5answers
315 views

Total number of topological sorts

For a given DAG (directed acyclic graph), each of its topological sorts is a permutation of all vertices, where for every edges (u,v) in the DAG, u appears before v in the permutation. Your task is ...
6
votes
5answers
489 views

Grow words from fertile vocabularies

An incremental word chain is a sequence of words of a vocabulary such that each word is the result of either prepending or appending a single character to the previous word, ignoring capitalization. ...
15
votes
8answers
696 views

Building a long chain of words

This challenge is to find the longest chain of English words where the first 3 characters of the next word match the last 3 characters of the last word. You will use an common dictionary available in ...
15
votes
11answers
1k views

Construct a graph

In this challenge, your task is to construct an undirected graph from a sequence of directives. There is one directive for each nonnegative integer, and each transforms a given graph into a new one. ...
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): ...
8
votes
3answers
285 views

3x3 Connected Components

The Challenge Consider the 3x3 king grid, as shown in the following ASCII graphic: A--B--C |\/|\/| |/\|/\| D--E--F |\/|\/| |/\|/\| G--H--I You are given as input a length-9 list of integers that ...
12
votes
3answers
505 views

Four color theorem

The Four color theorem States that no more than four colors are required to color the regions of a map. The challenge Given a list of State borders assign each state ID a color so that no two ...
6
votes
3answers
278 views

Edge Elimination Number

From Erich Friedman's Math Magic, (problem #2 on that page) your challenge is to find the edge elimination number of a connected graph. A single edge elimination is the removal of an edge from a ...
40
votes
3answers
2k views

Create xkcd-Style Narrative Charts

In one of the more iconic xkcd strips, Randall Munroe visualised the timelines of several films in narrative charts: (Click for larger version.) Source: xkcd No. 657. Given a specification of the ...
14
votes
1answer
585 views

Sabotage a Train to Make It Run Late

"I want to go to the Araby bazaar to buy a present for the one I have fallen in love with. However, if I arrive too late all the stores will be closed and I won't be able to buy anything. Can you help ...
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 ...
12
votes
4answers
593 views

Find the Chromatic Number

Surprisingly, we haven't had any challenges on graph colouring yet! Given an undirected graph, we can give each vertex a colour such that no two adjacent vertices share the same colour. The smallest ...
15
votes
10answers
1k views

How to slow down a drunkard on his way home

Consider a square n by n grid graph that looks like this. It is important to notice that this graph is 11 by 11. At any given point a man stands at an intersection and he only ever moves ...
11
votes
4answers
647 views

Growing Manhattan Ameobas

An ameoba graph* is a type of tree whose nodes all have values from 0 to some non-negative integer N, and any particular node with value x < N connects to x+1 distinct nodes with values x+1. ...
20
votes
7answers
851 views

Family Tree Solver

This is one of several challenges left for the community by Calvin's Hobbies. Take a "family tree describing" file with lines of the form: [ID] [mother ID] [father ID] [gender] [full name] such as ...
10
votes
4answers
512 views

How strong are nonary numbers?

You are given a nonary (base 9) non-negative integer consisting of the digits 0 through 8 as usual. However the number of digits in this number (with no leading zeros) is a prefect square. Because of ...
7
votes
1answer
296 views

Swing Through Trees with Your Grappling Hook

You have found the path through the forest and now plan on travelling along it. However, just before you start on your journey, the ground turns into lava. You manage to scurry up the nearest tree ...
17
votes
8answers
1k views

Extreme Whitewater Canoeing

You are paddling a canoe down a fairly fast whitewater river. Suddenly, your paddles explode, and you find yourself in a dangerous situation hurtling down a river rapid without any paddles. Luckily, ...
17
votes
1answer
676 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
vote
1answer
503 views

Racketeer Taxi Driver

The Scenario You are a taxi driver in your city. You picked up a passenger from the airport and he told you the place he'd like to go. To earn more money, you need to drive as much as you can. ...
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 ...
21
votes
8answers
2k views

Are you in the biggest room?

Introduction You have recently accepted a job offer at a Pretty Good Software Company. You're pretty content with the size of your office, but do you have the biggest office? Its kinda hard to tell ...
18
votes
2answers
1k views

Mastermind strategy

I could only find code-golf challenges for Mastermind, so here's a code-challenge version that I would have liked to take on myself. An optimal strategy for the normal Mastermind game, MM(4,6), was ...
8
votes
7answers
382 views

Count the terminal cycles of a directed graph

Task You must write a program or function in the language of your choice which accurately counts the number of terminal cycles of a simple directed graph. This particular kind of directed graph is ...
4
votes
10answers
806 views

Find all reachable nodes in a graph

You are given a directed graph in an adjacency dictionary format. This can be whatever format is most natural for your language. For instance, in python, this would be a dictionary with keys of nodes ...
10
votes
11answers
1k views

Calculate your stack exchange reputation

Background: I often find that, when browsing a Stackexchange site, I begin to wonder how people get the amount of reputation that they have. I know I can always count on codegolf SE to solve my ...
7
votes
4answers
330 views

Wireless Keyboard Inteference

Initech are setting up an office of 36 employees in a soul-crushingly efficient square of cubicles, 6 desks long and 6 desks deep. Management has bought wireless keyboards in bulk from a cheap, ...
3
votes
5answers
706 views

Alex the Truck Driver

Alex is a Truck Driver who wants to find the quickest way to deliver goods to multiple cities. He knows the distances between his destinations, but you need to write a program to help him find the ...
4
votes
4answers
350 views

Determine number of unconnected components

You are given a graph represented through an adjacency list. For example, the input 1-2 2-3 3-4 4-1 would correspond to the graph with nodes 1, 2, 3 and 4, where 1 is connected to 2, 2 is connected ...
19
votes
5answers
2k views

Score a game of Go

Scoring a Go game is a task that is not all too easy. In the past there have been several debates about how to design rules to cover all the strange corner cases that may occur. Luckily, in this task ...
11
votes
11answers
1k views

City names game

If you like, write a program which sorts cities according to the rules of city name game. Each name of the city should start from the last letter in the previous city name. E.g. Lviv -> v -> ...
2
votes
1answer
917 views

Calculate Network Average Clustering Coefficient

The clustering coefficient of a graph (or network) is a: measure of degree to which nodes in a graph tend to cluster together The Wikipedia article gives a much better description of how ...
8
votes
3answers
562 views

Shortest route through a one-way system

My home town, Rhyl, has a one-way traffic system which seems to have been designed to keep people away from their destination for as long as possible. Your task, should you choose to attempt it, is to ...
8
votes
2answers
187 views

BWInf 2011, question 5: Twin towns

This is a challenge that was originally a tas for the German Bundeswettbewerb Informatik (federal competition of computer science [?]), a competition for highschool students. As opposed to the ...
16
votes
9answers
2k views

Choose Your Own Adventure

Choose Your Own Adventure books are a form of interactive literature where the reader must make decisions that affect the outcome of the story. At certain points in the story, the reader has multiple ...
2
votes
0answers
568 views

Traffic light synchronization problem [closed]

I'm not a 100% sure if this qualifies under this stack exchange; however, I asked this question on the stats stackexchange with no answers. I wonder if you can solve it: Traffic light synchronization ...
14
votes
4answers
845 views

Help Mr Jones to enjoy his bicycle round-trip

Mr Jones wants to do a round-trip on his bicycle. He wants to visit several cities in arbitrary order, but his route must not cross it self, since he hates to be at the same place twice in his ...
9
votes
1answer
581 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 | / \ | | / ...