Problems relating to graph theory
15
votes
4answers
357 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
4answers
269 views
How far from the exterior?
Take a 2D region of space divided into axis aligned unit square elements with their centers aligned at integer intervals. An edge is said to be internal if it is shared by two elements, otherwise it ...
9
votes
5answers
257 views
Walking on the Hypercube
I recently read up on graph theory, especially hypercubes and thought about interesting ways to construct paths on them. Here's what I came up with.
As you might know, you can construct an ...
10
votes
6answers
945 views
On the edges of the hypercube
Your job will be to write a function or a program, that will take an integer n>0 as input and output a list of the edges of the n-dimensional hypercube. In graph theory an edge is defined as a ...
18
votes
2answers
191 views
Find the haystack in the needles
In a twist on finding a needle in a haystack, you need to find the largest contiguous haystack containing exactly one needle. Note that you cannot connect cells on diagonals, only left/right/up/down.
...
20
votes
3answers
412 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
281 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 ...
6
votes
1answer
100 views
Calculating Parabolic Curves in 3D Space
Task
Write a program or function that will determine if a point in 3D space lies on a 2D parabolic curve.
Input
3 points in 3D space
vertex of a 2D parabolic curve
arbitrary point on the curve
...
10
votes
0answers
158 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 ...
34
votes
13answers
3k 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 ...
11
votes
0answers
247 views
Draw a network of nodes
There is a network of upto 26 nodes (named A to Z or a to z as per your wish). Every pair of nodes may be connected or disconnected. A node may be connected to atmost 4 other nodes. Your task is to ...
3
votes
1answer
130 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 ...
10
votes
4answers
193 views
Build a 4-vertex Connectedness Tester using NAND gates
A connected graph is a graph that contains a path between any two vertices.
Challenge
Build a [2-input NAND-gate] circuit that determines whether a 4-vertex graph is connected.
(A gate's 2 inputs ...
3
votes
0answers
152 views
Hamilton is coming to town
It's almost Christmas, so Santa has to plan his route. You're helping him, for reasons unknown.
Santa needs help planning the route and wants you to give him a solution, but since you're all ...
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 ...
7
votes
3answers
256 views
Guess the hidden communities
Background
This challenge is about the stochastic block model.
Basically, you are given an undirected graph, where the nodes represent people, and the edges represent social connections between them.
...
12
votes
3answers
361 views
A game of locks and keys
There are n boxes, numbered 1-n. Each box is locked, such that it can be opened by only one corresponding type of key (also numbered 1-n). These keys are randomly scattered in the boxes (one box may ...
19
votes
2answers
268 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 ...
19
votes
4answers
1k 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. ...
7
votes
2answers
196 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 ...
21
votes
1answer
502 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 ...
16
votes
3answers
621 views
Loops and Loops and Loops
The Challenge
Create a function that, when given an input of ASCII art (directing a path that may eventually loop), outputs the length of the loop (if there is one) and the length of the "tail" ...
11
votes
2answers
285 views
Count the trees
A tree is a connected, undirected graph with no cycles. Your task is to count how many distinct trees there are with a given number of vertices.
Two trees are considered distinct if they are not ...
16
votes
4answers
437 views
Find the largest independent set in a high-dimensional lattice-like graph
For a given positive integer n, consider all binary strings of length 2n-1. For a given string S, let L be an array of length n which contains the count of the number of 1s in each substring of ...
33
votes
8answers
5k 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 ...
9
votes
2answers
315 views
Play a Perfect Game of 4x4 Hex
Background
Hex is a two-player abstract strategy game played on a K×K rhombus of hexagonal tiles.
Two opposite sides of the rhombus are colored white, and the other two black, and the two ...
25
votes
1answer
385 views
Is My Graph Planar?
Your task is to determine whether a graph is planar.
A graph is planar if it can embedded in the plane, or in other words if it can be drawn without any crossing edges.
Input: You will be given an ...
7
votes
0answers
204 views
Map of Islands (and a river)
Introduction
For many centuries, there has been a certain river that has never been mapped. The Guild of Cartographers want to produce a map of the river, however, they have never managed to succeed ...
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 ...
12
votes
1answer
272 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 ...
17
votes
2answers
374 views
Finding the Deadlock
Finding the Deadlock
When programming a multithreading application one must take good care to avoid deadlocking the various threads when accessing shared resources. A deadlock occurs when a thread ...
15
votes
10answers
697 views
Undirect a Graph
Introduction
In this challenge, you are given a directed graph with self-loops, and your task is to convert it to an undirected graph without self-loops.
Input
Your input is a directed graph with ...
19
votes
3answers
474 views
Is This a Real Tree?
You should write a program or function which receives a string as input and outputs or returns if the input is an ASCII tree.
_
\/ /
\_/
|
|
ASCII trees consist of characters / \ | _ spaces ...
9
votes
1answer
340 views
Slime Molds Can Count!
Background
Slime molds are awesome.
If you place them on a surface with food sources, they will spread their tendrils to find the food, after which they form a network of connections between the ...
8
votes
5answers
357 views
Decide existence of total orderings
In this task, we consider arrays of positive integers such as this:
3 18 321 17 4 4 51 1 293 17
The input comprises a pair of such arrays both of arbitrary, possibly distinct, positive length. ...
34
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
171 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
369 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
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:
...
9
votes
5answers
396 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
530 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. ...
16
votes
8answers
1k 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.
...
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):
...
8
votes
3answers
315 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 ...
13
votes
3answers
577 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
307 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 ...
44
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 ...
15
votes
1answer
891 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 ...
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 ...
