Questions tagged [graph-theory]
For challenges regarding graphs, mathematical structures used to model relations between objects.
49
questions
29
votes
8answers
3k 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 ...
39
votes
6answers
5k 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, ...
26
votes
4answers
2k views
Golf Me An OOP!
Golf Me An OOP!
Two important components of object-oriented programming are inheritance and composition. Together, they allow for creating simple yet powerful class hierarchies to solve problems. ...
22
votes
10answers
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 ...
12
votes
1answer
966 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:
...
16
votes
15answers
2k 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. ...
8
votes
14answers
5k 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 ...
20
votes
14answers
2k views
Check if all non-zero elements in a matrix are connected
Input:
A matrix containing integers in the range [0 - 9].
Challenge:
Determine if all non-zero elements are connected to each other vertically and/or horizontally.
Output:
A truthy value if all ...
18
votes
4answers
595 views
Generate a Portmantout!
Background
Three years ago, this guy Tom Murphy got it into his head to extend the idea of a portmanteau to all words in a language and called this a portmantout (portmanteau plus tout [French for ...
17
votes
8answers
4k 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 ...
14
votes
11answers
1k views
Spanning tree of a rectangular grid
Background
A spanning tree (Wikipedia) of an undirected graph is a subgraph that is a tree which includes all of the vertices of the original graph. The following is an example of a spanning tree of ...
9
votes
0answers
119 views
Order of Elements of the Rubik's Cube [duplicate]
Introduction
All the possible moves and their combinations of a Rubik's Cube form a group. A group in general is a set with some binary operation defined on it. It must contain a neutral element with ...
18
votes
7answers
938 views
Longest Cycle in a Graph
Given a directed graph, output the longest cycle.
Rules
Any reasonable input format is allowed (e.g. list of edges, connectivity matrix).
The labels are not important, so you may impose any ...
17
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 ...
17
votes
12answers
766 views
Is this Sequence Graphic?
A graphic sequence is a sequence of positive integers each denoting the number of edges for a node in a simple graph. For example the sequence 2 1 1 denotes a ...
19
votes
1answer
714 views
Seeking Leapers
I recently got a really weird irregular chess board. It's squares are all over the place and not even all connected. At least they're still laid out on a regular grid. I want to adapt the chess rules ...
9
votes
1answer
394 views
Advent Challenge 2: The Present Vault Raid!
<< Prev Next >>
Challenge
Now that Santa has finally figured out how to get into his present vault, he realises that somehow the elves got in there before him and stole some of his presents! ...
5
votes
4answers
527 views
Determine number of connected 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 ...
51
votes
18answers
4k views
Can my 4-note music box play that song?
I have a crank-operated music box that can play a series of four notes. When I turn the crank, it plucks one of four strings, depending on the position of the crank and the direction of the turn. When ...
19
votes
2answers
3k 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 ...
40
votes
8answers
6k views
40 Numbers in 9 Bytes
There are 40 ways a directed Hamiltonian path can be arranged on a 3×3 grid:
This graphic (thanks Sp3000!) shows only the 20 undirected paths. Traverse each colored line in both directions for the 40 ...
15
votes
7answers
2k views
Where should I put my restaurant?
You are the owner of a restaurant. You are opening in a new area in Cartesia where there is only one main road, known as the y-axis. You want to place your restaurant such that you minimize the total ...
25
votes
1answer
739 views
Is it a Cactus?
In graph theory, a Cactus is a connected graph such that any distinct two simple cycles in the graph share at most one vertex.
Here is a Cactus with 3 simple cycles outlined with dashed lines.
The ...
29
votes
8answers
2k 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, ...
24
votes
5answers
3k 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 ...
20
votes
2answers
545 views
Are these trees isomorphic?
Introduction
In this challenge, your task is to write a program that decides whether two given trees are isomorphic.
A tree means a directed acyclic graph where every node has exactly one outgoing ...
27
votes
2answers
1k views
23
votes
1answer
718 views
Dependency Graph Visualization
The goal of this challenge is to write a program that visualizes a dependency graph in the form of a tree.
While "dependency graph" in this context means nothing more than a directed graph, the ...
23
votes
13answers
2k views
Do the NP: find the largest clique
Background
At the time of writing this, the P vs NP problem is still unsolved, but you might have heard of Norbert Blum's new paper claiming proof that P != NP, which is already suspected to be ...
19
votes
2answers
291 views
Island Golf #2: The Eccentric Hermits
This is the second in a series of Island Golf challenges. Previous challenge
Two hermits have arrived on a desert island. Since they came seeking solitude, they wish to live as far away from each ...
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.
...
13
votes
3answers
624 views
Grids can be curvy. How long is yours?
Consider depicting a simple, open, two-dimensional curve on a W wide by H high grid of text where X represents part of the curve and ...
10
votes
2answers
652 views
9
votes
3answers
719 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
303 views
Is my Graph Graceful?
A Graceful Graph is a type of Simple Graph. Graceful graphs are special because there is a way to label all their nodes with positive integers so that when the edges are also labeled with the ...
3
votes
1answer
694 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. ...
29
votes
4answers
924 views
Arranging Bubbles
Note, challenge copied from question asked at math.stackexchange.
Recently, I attained quite some skill at blowing bubbles. At first I would blow bubbles like this:
But then things started getting ...
16
votes
4answers
814 views
Strongly Connected Components
Two distinct vertices in a directed graph are strongly connected if there is path in the graph from each to the other. A strongly connected component of the graph is a subset of the graph such that ...
14
votes
1answer
417 views
Save the Geese from Extinction
The species of geese known as Alex A are known for residing in triangular grids consisting of 64 cells:
(Picture taken from this unrelated Project Euler problem.)
We'll label each cell with the ...
13
votes
3answers
2k views
Hexcellent Minesweeping
Hexcells is a game based off of Minesweeper played on hexagons. (Full disclosure: I have nothing to do with Hexcells. In fact I don't really like the game.) Most of Hexcells rules can be pretty ...
12
votes
5answers
575 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 to ...
10
votes
4answers
682 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 ...
9
votes
7answers
699 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 ...
9
votes
3answers
410 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 ...
6
votes
5answers
721 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. ...
4
votes
1answer
228 views
Equivalence classes on the Transitive Closure of a Reflexive Relation
The goal of this challenge is to compute the set of equivalence classes over the transitive closure of a symmetric, reflexive relation. For those who don't know what that means, here is a brief ...
3
votes
5answers
810 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 ...
1
vote
3answers
248 views
Havel-to-da-Hakimi [duplicate]
It was a dark and stormy night. Detective Havel and Detective Hakimi arrived at the scene of the crime.
Other than the detectives, there were 10 people present. They asked the first person, "out of ...
-3
votes
1answer
216 views
Find an Eulerian Circuit
Challenge
You have been assigned a task to write a program which takes a multigraph as its input and if it contains an Eularian circuit to return one. Otherwise, the program's behavior is undefined, ...
