# Tagged Questions

The tag has no usage guidance.

397 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 array of strings. All maps are 5 ...
371 views

### Walk the labyrinth

Or maybe it's not really a labyrinth, but still. Rules: Input is a two-line string, consisting of *, 1, x and X. That string is a labyrinth to walk through. The lines have the equal length. You ...
101 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 G, there is an edge in the dual graph connecting the ...
558 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 ...
381 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 ...
278 views

### How far from the exterior?

Take a 2D region of space divided into axis aligned unit square elements with their centers aligned at integer intervals. An edge is said to be internal if it is shared by two elements, otherwise it ...
266 views

### Walking on the Hypercube

I recently read up on graph theory, especially hypercubes and thought about interesting ways to construct paths on them. Here's what I came up with. As you might know, you can construct an n-...
956 views

### On the edges of the hypercube

Your job will be to write a function or a program, that will take an integer n>0 as input and output a list of the edges of the n-dimensional hypercube. In graph theory an edge is defined as a 2-...
207 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. ...
435 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 ...
290 views

### Longest path on a 2d plane

You are provided a set of arbitary, unique, 2d, integer Cartesian coordinates: e.g. [(0,0), (0,1), (1,0)] Find the longest path possible from this set of coordinates, with the restriction that a ...
115 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 ...
336 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 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 ...
291 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 ...
134 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 ...
205 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 ...
158 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 ...
268 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. ...
363 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 ...
272 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. ...
201 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 ...
516 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 ...
625 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" ...
299 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 ...
454 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 ...
346 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 ...
394 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 ...
221 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 ...
272 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 ...
383 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 ...
701 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 ...
483 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 ...
344 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 ...
359 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 ...
378 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, ...
704 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: ...
401 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 ...
541 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. ...
2k 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): [[0,0,...