Problems relating to graph theory

learn more… | top users | synonyms

4
votes
1answer
38 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 ...
8
votes
0answers
132 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 ...
10
votes
0answers
230 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
126 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
183 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
145 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 ...
41
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
242 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
360 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
258 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
192 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 ...
20
votes
1answer
491 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
618 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
276 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
430 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
303 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
380 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
197 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
271 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
364 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
472 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
337 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
353 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
358 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
688 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
393 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
528 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
313 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
574 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
303 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 ...
42
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
848 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 ...
12
votes
4answers
736 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
2k 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
705 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. ...
21
votes
7answers
957 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
552 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
352 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 ...
24
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, ...