# Questions tagged [graph-theory]

For challenges regarding graphs, mathematical structures used to model relations between objects.

63 questions
Filter by
Sorted by
Tagged with
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 ...
• 1,861
3k 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 ...
• 46.4k
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
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. ...
3k views

### smallest number of steps for a knight in chess

If you place a knight on any square of a chessboard, what is the smallest amount of steps to reach every position? Rules It is an 8 by 8 board. The knight starts at an arbitrary position, taken as ...
• 435
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
2k 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 ...
• 77k
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. ...
• 1,778
6k 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 ...
• 42k
3k views

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 ...
• 1,100
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 ...
• 6,772
753 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 ...
• 197k
1k 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 ...
757 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 ...
815 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 ...
• 98.8k
1k 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 ...
• 37k
4k 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 ...
• 197k
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: ...
• 20.9k
479 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! ...
• 42.4k
122 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 ...
• 43.8k
577 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 ...
• 2,172
5k 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 ...
• 3,742
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 ...
• 89.8k
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 ...
• 23.9k
5k views

### Can the 🐸 visit all the 🪷?

In this challenge you will be simulating a frog jumping from lily-pad to lily-pad in a pond. A frog's jump distance is uniquely determined by the size of the lily pad it jumps from. So for example ...
• 98.8k
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, ...
• 8,619
947 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 ...
• 11.6k
1k 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 ...
• 98.8k
1k views

### 2D Maze Minus 1D

This challenge is about converting 2D mazes into 1D mazes. Overview ...
• 1,646
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 ...
• 4,266
818 views

### Can this village have a wedding?

The quaint hamlet of Кодгольф in the Russian far east has a problem: their population is low (below 66), and no new people have arrived for years. Moreover, after centuries of near-isolation, just ...
• 1,373
756 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 ...
• 7,707
3k views

### Drawing one-liner

CodeDrawing one-liner Teaser Behold this formidable drawing: Can you draw this in a single stroke? Give it a try. Can you do this one, now: Give it a try. How it works These "make this drawing ...
• 14.1k
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 ...
• 10.1k
2k views

### Calculating Transitive Closure

First attempt at a question. Calculating Transitive Closure According to Wikipedia, "the transitive closure $R^*$ of a homogeneous binary relation $R$ on a set $X$ is the smallest ...
• 550
605 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 ...
• 42.7k
983 views

### Convert between graph representations

What? Let's say I have this graph: 1 \ \ 2 3 \ / \ / 4 I can represent it in 2 ways: A list of connected vertices. ...
• 1,655
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 ...
• 406
341 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 ...
• 39.7k
894 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 ...
• 42k
592 views

### Can this Scottish village have a wedding?

This is the exact same question I asked earlier, but without the annoying Cyrillic factor which many found superfluous. I hope this is a better puzzle! The quaint hamlet of North Codetown in the ...
• 1,373
8k views

### Determine if a relation is transitive

Challenge description Let's start with some definitions: a relation is a set of ordered pairs of elements (in this challenge, we'll be using integers) For instance, ...
• 5,652
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. ...
• 42.7k
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 ...
• 4,452
951 views

### Detect round trips on a dodecahedron

An ant starts on an edge of a dodecahedron, facing parallel to it. At each step, it walks forward to the next vertex and turns either left or right to continue onto one of the other two edges that ...
• 621
2k views

### Solve the Trolley Problem

Philosophers have long pondered the Trolley problem. Unfortunately, no human has solved this problem yet. Luckily, as programmers we can use computers to solve the problem for us! Input Your program ...
• 7,235
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 ...
• 98.8k
655 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 ...
• 89.8k
450 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 ...
• 8,619