# Tagged Questions

Problems relating to graph theory

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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. ...
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 ...
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 ...
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" ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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, ...
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: ...
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 ...
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. ...
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 ...
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. ...
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): ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...