The tag has no usage guidance.

learn more… | top users | synonyms (1)

9
votes
3answers
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 ...
14
votes
5answers
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 ...
5
votes
0answers
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 ...
14
votes
1answer
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 ...
15
votes
4answers
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 ...
14
votes
4answers
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 ...
9
votes
5answers
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-...
10
votes
6answers
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-...
18
votes
2answers
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. ...
20
votes
3answers
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 ...
14
votes
3answers
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 ...
6
votes
1answer
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 ...
21
votes
2answers
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 ...
34
votes
15answers
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 ...
13
votes
0answers
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 ...
3
votes
1answer
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 ...
10
votes
4answers
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 ...
4
votes
0answers
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 ...
42
votes
2answers
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 ...
7
votes
3answers
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. ...
12
votes
3answers
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 ...
19
votes
2answers
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 ...
19
votes
4answers
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. ...
7
votes
2answers
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 ...
21
votes
1answer
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 ...
16
votes
3answers
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" ...
11
votes
2answers
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 ...
16
votes
4answers
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 ...
38
votes
8answers
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 ...
9
votes
2answers
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 ...
25
votes
1answer
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 ...
8
votes
0answers
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 -...
15
votes
7answers
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 ...
12
votes
1answer
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 ...
17
votes
2answers
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 ...
15
votes
10answers
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 ...
19
votes
3answers
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 ...
9
votes
1answer
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 ...
8
votes
5answers
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. ...
34
votes
4answers
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 ...
9
votes
2answers
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 ...
9
votes
2answers
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, ...
9
votes
7answers
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: ...
9
votes
5answers
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 ...
6
votes
5answers
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. ...
16
votes
8answers
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 ...
15
votes
11answers
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. ...
18
votes
7answers
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,...
8
votes
3answers
327 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 ...
13
votes
3answers
589 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 ...