All Questions
215 questions
11
votes
3
answers
464
views
Spanning paths in a tournament on n nodes
The goal of this challenge is to extend the On-Line Encyclopedia of Integer Sequences (OEIS) sequence A038375.
Maximal number of spanning paths in tournament on n nodes.
A tournament on \$n\$ ...
- 6,627
24
votes
5
answers
862
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 ...
- 1,402
5
votes
1
answer
369
views
Triangularly embed a graph on a surface
This challenge arises from a claim made in a MathOverflow answer and a paper linked in that answer which seems to back up the claim:
Searching for triangular embeddings is much quicker than ...
- 3,945
8
votes
5
answers
905
views
Pólya trees counted efficiently
The number of unlabeled rooted trees with n nodes is a fundamental sequence in graph theory and in discrete mathematics in general.
Some authors call these trees 'Polya trees'. The number of these ...
- 6,627
23
votes
6
answers
493
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 ...
- 211
9
votes
3
answers
225
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 ...
- 7,711
15
votes
9
answers
573
views
Cutpoints in a maze
A maze is given as a matrix of 0s (walls) and 1s (walkable space) in any convenient format. Each cell is considered connected to its 4 (or fewer) orthogonal neighbours. A connected component is a set ...
- 1,029
18
votes
5
answers
1k
views
Ways to paint a backbone on a tree
Say I have some unlabelled tree graph:
I'll define a "backbone" as a path on a graph that can't be extended - both its ends are at terminal vertices. There are three ways to overlay a ...
- 4,817
21
votes
20
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 ...
- 1,029
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 ...
- 6,627
81
votes
40
answers
12k
views
Wait a minute – in less than ten seconds
Task
Using any type of parallelisation, wait multiple periods, for a total sleep time of at least a minute (but less than a minute and a half).
The program/function must terminate within 10 seconds ...
- 10.8k
20
votes
3
answers
572
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.
...
- 7,711
19
votes
8
answers
1k
views
Longest hypercube path
Challenge
You are given two distinct bit strings of the same length. (For example, 000 and 111.) Your goal is to find a path ...
- 7,711
24
votes
3
answers
487
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 ...
- 7,711
5
votes
5
answers
309
views
Calculating Graph Powers
Calculating Graph Powers
(very similar to my other question asked here)
According to Wikipedia, "the \$k\$th power \$G^k\$ of an undirected graph \$G\$ is another graph that has the same set of ...
- 50k
17
votes
3
answers
740
views
Calculate Coefficient of Inbreeding
Your task is, given a family tree, to calculate the Coefficient of Inbreeding for a given person in it.
Definition
The Coefficient of Inbreeding is equal to the Coefficient of Relationship of the ...
- 6,627
22
votes
2
answers
472
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. ...
- 7,711
13
votes
5
answers
459
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 ...
- 28.5k
14
votes
3
answers
583
views
Is this an interval graph?
Background
An interval graph (Wikipedia, MathWorld, GraphClasses) is an undirected graph derived from a set of intervals on a line. Each vertex represents an interval, and an edge is present between ...
- 7,711
16
votes
10
answers
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 ...
- 7,665
6
votes
2
answers
222
views
Pareto-optimal shortest paths
Given a directed graph on the nodes 0, 1, ..n, where each edge has two non-negative integer costs, return the set of all possible Pareto Optimal path costs between ...
- 6,627
15
votes
12
answers
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 ...
- 6,627
12
votes
3
answers
400
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 ...
- 7,711
9
votes
3
answers
1k
views
The smallest number of steps for a chess piece to reach a position
I have previously posted a challenge, smallest number of steps for a knight in chess.
Now I would like to go a step further by adding the possibility to choose your piece.
If you place a piece on any ...
- 4,810
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, ...
- 1
10
votes
2
answers
483
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! ...
- 7,711
16
votes
5
answers
862
views
Compute the chromatic number of special graphs
This challenge is about computing the chromatic number of special types of graphs.
Input
The input will consist of two integers.
A positive integer \$n > 1\$.
A distance \$d < n\$.
Task
The ...
- 3,275
12
votes
9
answers
953
views
Chromatic polynomial of a graph
Given a undirected graph \$G\$ and a integer \$k\$, how many \$k\$-coloring does the graph have?
Here by a \$k\$-coloring, we mean assigning one of the \$k\$ colors to each vertex of the graph, such ...
- 6,627
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 ...
- 198k
8
votes
14
answers
662
views
Construct a line graph / conjugate graph
Introduction
Given an undirected graph G, we can construct a graph L(G) (called the line graph or conjugate graph) that represents the connections between edges in G. This is done by creating a new ...
- 50k
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 ...
- 6,035
22
votes
1
answer
733
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 ...
- 13.5k
9
votes
14
answers
1k
views
Simplify a Cycle
Alternatively: That one challenge I forgot I had in the sandbox and is about stuff from Discrete Mathematics I learned like 5-6 months ago and kinda don't remember
Given a path of vertices that form a ...
- 6,627
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 ...
- 6,627
5
votes
3
answers
380
views
Minimum Cut finder
Write a program that takes an undirected graph and finds the minimum cut, i.e., the set of edges that, if removed, would disconnect the graph into two or more connected components. The program should ...
- 6,627
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 ...
- 42.1k
10
votes
8
answers
889
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:
...
- 18.3k
11
votes
3
answers
625
views
The von Koch conjecture
You may know the mathematician von Koch by his famous snowflake. However he has more interesting computer science problems up his sleeves.
Indeed, let's take a look at this conjecture:
Given a tree ...
- 7,711
5
votes
2
answers
276
views
Broken Path Detection
Challenge
Given a plot with broken paths, return the plot with all paths connected in the minimum number of changes.
Explanation
This problem deals with graphs on the Cartesian plane. Every node ...
- 7,711
15
votes
5
answers
961
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 ...
- 535
16
votes
17
answers
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, ...
- 131k
19
votes
14
answers
3k
views
Is this graph a tree?
Given an undirected graph, find out if it is a tree.
A tree is an undirected graph in which there is exactly one path between any two vertices. In other word, the graph is both acyclic and connected.
...
- 4,525
10
votes
4
answers
208
views
Hamiltonian levencycle of 1-dup permutations
The word "levencycle" is inspired by cyclic levenquine challenge.
Definitions
A 1-dup permutation of order \$n\$ is some permutation of \$1, \cdots, n\$ plus one duplicate number in the ...
- 24.6k
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.
...
- 11.2k
14
votes
12
answers
2k
views
Small Ramsey Numbers
Background: the Ramsey number \$R(r,s)\$ gives the minimum number of vertices \$v\$ in the complete graph \$K_v\$ such that a red/blue edge coloring of \$K_v\$ has at least one red \$K_r\$ or one blue ...
- 11.2k
18
votes
20
answers
1k
views
Generate a regular graph
Inspired by this Mathematica.SE post
Given two positive integers \$n, k\$ with \$n > k \ge 1\$, output a binary \$n\times n\$ matrix such that every row and column contains exactly \$k\$ 1s, and ...
- 432
7
votes
4
answers
573
views
Train Route Planning
We can model a rail network as a directed graph, where each node is a train station and each edge is a train connecting two train stations. We'll assume that each train travels between its ...
- 7,734
12
votes
7
answers
660
views
Find the paths!
You must write a program or function.
The input is a 'map' of numbers. You can choose to take the map as either a string with new line characters (\n) or a 2D ...
- 751
87
votes
39
answers
11k
views
Implement Sleep Sort
Sleep Sort is an integer sorting algorithm I found on the Internet. It opens an output stream, and for each input numbers in parallel, delay for the number seconds and output that number. Because of ...
- 2,513
12
votes
1
answer
1k
views
Find a dual graph
A dual graph is defined such that for every "face" in a graph G, there is a corresponding vertex in the dual graph, and for every edge on the graph ...
CommunityBot
- 1