Skip to main content

Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
51 votes
18 answers
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 ...
apsillers's user avatar
  • 3,742
50 votes
3 answers
3k 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 ...
Martin Ender's user avatar
50 votes
6 answers
6k 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 ...
phosgene's user avatar
  • 1,185
44 votes
3 answers
3k 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 ...
Martin Ender's user avatar
42 votes
8 answers
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 ...
Calvin's Hobbies's user avatar
40 votes
6 answers
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, ...
Martin Ender's user avatar
35 votes
4 answers
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 ...
Zgarb's user avatar
  • 42.7k
31 votes
10 answers
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 ...
pxeger's user avatar
  • 23.9k
30 votes
13 answers
3k views

Is it a valid chemical?

Non-metals typically* have a fixed number of covalent bonds in every chemical they are part of. Given the number of bonds every element requires, output whether it's possible to construct a single ...
mousetail's user avatar
  • 12.7k
30 votes
8 answers
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, ...
absinthe's user avatar
  • 8,619
30 votes
5 answers
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 ...
Wheat Wizard's user avatar
  • 98.8k
29 votes
8 answers
5k views

Should we be friends?

Note this is a question primarily focusing on data-structures Introduction Bacefook wants people to be friendlier! As such, they are implementing a new system to suggest friends! Your task is to help ...
Thunda's user avatar
  • 1,199
29 votes
4 answers
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 ...
TheNumberOne's user avatar
  • 11.6k
29 votes
8 answers
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 ...
turbulencetoo's user avatar
29 votes
4 answers
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. ...
user avatar
29 votes
1 answer
652 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 ...
isaacg's user avatar
  • 42k
29 votes
2 answers
1k views

Help Pac-Man count the Pac-Dots

On the advice of Ms. Pac-Man who's worried about him getting overweight, Pac-Man has decided to keep track of his daily Pac-Dot intake. Help him count the number of Pac-Dots on a given path in the ...
Arnauld's user avatar
  • 193k
28 votes
5 answers
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 ...
Wheat Wizard's user avatar
  • 98.8k
27 votes
8 answers
2k views

Somewhere On The Tube ...But On Which Lines?

The London Underground A.K.A. The Tube is the oldest underground railway in the world, it currently consists of eleven lines* servicing 267 named stations (strictly 269** stations since "Edgware ...
Jonathan Allan's user avatar
27 votes
2 answers
1k views

2D Maze Minus 1D

This challenge is about converting 2D mazes into 1D mazes. Overview ...
H Walters's user avatar
  • 1,646
26 votes
10 answers
2k views

Knight Distance

In Chess, a Knight on grid \$(x, y)\$ may move to \$(x-2, y-1)\$, \$(x-2, y+1)\$, \$(x-1, y-2)\$, \$(x-1, y+2)\$, \$(x+1, y-2)\$, \$(x+1, y+2)\$, \$(x+2, y-1)\$ or \$(x+2, y+1)\$ in one step. Imagine ...
tsh's user avatar
  • 34.9k
26 votes
15 answers
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 ...
Felix Palmen's user avatar
  • 4,266
26 votes
3 answers
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 ...
KeizerHarm's user avatar
  • 1,373
24 votes
15 answers
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 ...
Bjop's user avatar
  • 435
24 votes
32 answers
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 ...
RGS's user avatar
  • 14.1k
24 votes
7 answers
2k views

Are these states connected?

With the US election going on right now, I noticed that there is one (completely meaningless, but still) thing which Trump can still achieve and which is out of reach for Biden: Having the won states ...
Keba's user avatar
  • 451
24 votes
5 answers
800 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 ...
Martin Ender's user avatar
24 votes
1 answer
1k views

Determine if a Graph is Toroidal

A simple graph is toroidal if it can be drawn on the surface of a torus without any edges intersecting. Your task is to take a simple undirected graph via any reasonable method (adjacency matrix, ...
Wheat Wizard's user avatar
  • 98.8k
24 votes
2 answers
969 views

Draw a network of nodes

There is a network of up to 26 nodes (named A to Z or a to ...
ghosts_in_the_code's user avatar
24 votes
1 answer
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 ...
Ell's user avatar
  • 7,707
23 votes
10 answers
2k views

Two-Coloring Overlapping Circles

Write a program or function that takes in the following input in a reasonable format of your choice: Two positive integers W and H that define the width and height of the image you'll be generating. ...
Calvin's Hobbies's user avatar
23 votes
12 answers
3k views

Drunkard's Journey Home

Drunkard's Journey Home In this challenge you are to write a program which simulates a drunkard stumbling his way home from the bar. Input: The input will be an adjacency matrix (representing a ...
fəˈnɛtɪk's user avatar
  • 4,194
23 votes
5 answers
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 ...
FUZxxl's user avatar
  • 10.1k
22 votes
23 answers
3k views

Pointer jumping

Suppose we have an array \$\texttt{ps}\$ of length \$n\$ with pointers pointing to some location in the array: The process of "pointer jumping" will set every pointer to the location the pointer it ...
ბიმო's user avatar
  • 16.8k
22 votes
7 answers
3k views

Surface of the 3x3x3 cube as a graph

Your task is to generate a graph with 54 vertices, each corresponds to a facet on a Rubik's cube. There is an edge between two vertices iff the corresponding facets share a side. Rules You may ...
jimmy23013's user avatar
22 votes
10 answers
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 ...
dwana's user avatar
  • 551
22 votes
7 answers
3k 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: ...
Martin Ender's user avatar
22 votes
3 answers
1k 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 -...
absinthe's user avatar
  • 8,619
22 votes
1 answer
435 views

Is this Game of Go configuration fully alive?

Background This challenge is about the Game of Go. Here are some rules and terminology relevant to this challenge: Game of Go is a two-player game, played over a square board of size 19x19. One of ...
Bubbler's user avatar
  • 77k
22 votes
2 answers
454 views

Complete the grid-filling meander

A grid-filling meander is a closed path that visits every cell of a square \$N \times N\$ grid at least once, never crossing any edge between adjacent cells more than once and never crossing itself. ...
Jordan's user avatar
  • 10.1k
22 votes
1 answer
727 views

Can you draw this in one stroke?

Related | Related Given an ASCII art with |, _, and , check if you can draw the art in one ...
math scat's user avatar
  • 9,408
22 votes
2 answers
438 views

A Peak Experience: Quickly Visit All the Peaks

I am standing at point (0,0) in a H x W map where the altitude is represented by digits, for ...
cozyconemotel's user avatar
21 votes
18 answers
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 ...
Stewie Griffin's user avatar
21 votes
13 answers
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 ...
SanguineL's user avatar
  • 550
21 votes
2 answers
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 ...
Zgarb's user avatar
  • 42.7k
21 votes
1 answer
918 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 ...
Eric Tressler's user avatar
20 votes
14 answers
2k views

Get to the Zone!

You are playing a famous game called \$1\text{D Array BattleGround}\$. In the game, the player can be stationed in any position from \$0\$ to \$10^5\$. You are a Paratrooper in the game and have the ...
Jubayer Abdullah Joy's user avatar
20 votes
12 answers
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. ...
zoomlogo's user avatar
  • 1,655
20 votes
7 answers
2k views

Break The Chain

You are given an \$ 25 \times 25 \$ square lattice graph. You are to remove certain nodes from the graph as to minimize your score, based on the following scoring system: Your score will be the \$ \...
dingledooper's user avatar
  • 22.7k
20 votes
9 answers
2k views

Enumerate binary trees

Binary trees A binary tree is a tree with nodes of three types: terminal nodes, which have no children unary nodes, which have one child each binary nodes, which have two children each We can ...
Guy Coder's user avatar
  • 321

1
2 3 4 5