# Questions tagged [decision-problem]

For challenges which involve deciding whether or not the input meets certain criteria, and outputting some data, representing that decision.

601 questions
Filter by
Sorted by
Tagged with
3k views

### Will one-cell brainfuck halt?

Brainfuck is an esoteric programming language that is Turing Complete, meaning you can't tell whether a given program will halt without running it. It's cell-based and has an infinite tape of cells, ...
2k views

### Open or Close the Parentheses

Every phone needs a calculator app. Because of the limited screen real estate, the developer of mine has decided to save some buttons. Instead of having two dedicated bracket buttons - one for open <...
2k views

### Digit small numbers

A digit small number is a positive integer $n$ such for any two numbers that multiply to $n$, their total number of digits is more than the digits in $n$. In otherwords: there are no two ...
1k views

### Infinite ordinals from a well-ordering

Your task is to write a short program that represents a large (infinite) ordinal, using a well-ordering of the set of positive integers. Your program will take two different positive integers and ...
602 views

### Is it an elementary matrix?

Consider a linear system of equations, in $n$ unknowns, expressed as $$A \textbf x = \textbf b$$ where $A \in M_{n,n}(\mathbb Z)$ is an $n \times n$ matrix of integers, $\textbf x$ is a column ...
230 views

### A rolling drop gathers all pearls?

Quell is a single-player grid-based puzzle game. Pearls are scattered across a 2D map and the aim is to collect them all by rolling a drop of water over them. For this challenge we will only consider ...
2k views

### Crossing a river with weird animals

Background One kind of river-crossing problems involves two kinds of animals. One such problem reads like this: (all wordings, including animal species, are arbitrary) A farmer has to cross a river ...
5k views

### Is This Scrabble Board Valid?

Background Scrabble is a word game in which players collaboratively build a board consisting of letter tiles that spell words. Each word must be connected to another word, and players gain points ...
2k views

### Is it a prefix normal word?

Prefix normal words arise in the context of binary jumbled pattern matching. A binary word $w$ consisting of $0$s and $1$s is said to be prefix normal * if, among all of its substrings, none ...
849 views

### Maybe fractal sequence?

Background A fractal sequence (Wikipedia; MathWorld) is an infinite sequence of positive integers meeting the following conditions: Each positive integer appears infinitely many times in the sequence....
546 views

### Is this Flow Free puzzle trivial?

Background Flow Free is a series of puzzle games whose objective is to connect all the same-colored pairs of dots on the grid. In this challenge, we consider the original game on a rectangular grid (...
533 views

### Validate Sudoku on a Mobius Strip

@BeastlyGerbil presents, the world's very first MOBIUS SUDOKU: Google Sheets version (The left most square backs onto the right most square, and the middle squares back onto each other. The ends are ...
823 views

### Neural Processing Lattice Checker

Consider the following 9 "row patterns", using 0s to represent empty cells and 1s to represent a full cell. Each pattern is associated with an integer $n$, such that $0 \le n \le 8$ (...
3k views

### Is it a row of Pascal's triangle?

Pascal's triangle is a triangular diagram where the values of two numbers added together produce the one below them. This is the start of it: ...
328 views

### Parse Ternary Lambda Calculus for correctness

Wheat Wizard has once tried to come up with a parsing problem unsuitable for regex, but it failed due to Anders Kaseorg's Perl regex answer. This is the second attempt. Now that we know that Perl ...
1k views

### Parse a lambda for correctness

The goal of this challenge is to fill a niche that is mostly lacking on this site. In my observations there most parsing verification challenges fall into two categories: Super easy parsing. This ...
482 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 ...
277 views

### Will Alice win in this Stick Bomber game?

Background Stick Bomber is a two-player game I just made up. Initially, some sticks are placed in one or more groups, and the sticks in each group are laid out in a straight line. So a configuration ...
1k views

### Compare positions of integers in this sequence

A001057 is one way to represent an integer as a natural number. It lists them according to the following pattern: 0, 1, -1, 2, -2, 3, -3, 4, -4, ... In this ...
716 views

### Sliding Dice in a Dish

We have 3 dice in a square dish. The dish is 8 units wide and tall and each die is 3 units wide and tall. The dice are facing up each with a different number on their top face. ...
2k views

### Is this a Jordan matrix?

Background A Jordan matrix is a block-diagonal matrix where each block on the diagonal has the structure of  \begin{bmatrix} \lambda & 1 & 0 & \cdots & 0 \\ 0 &...
149 views

### Is this an ordinal transform? [duplicate]

Related: What's my telephone number? which asks to calculate the terms of A000085, the number of possible ordinal transforms of length n. Background Ordinal transform is a transformation on an integer ...
2k views

### Is it a Giuga number?

Giuga numbers (A007850) are composite numbers $n$ such that, for each prime factor $p_i$ of $n$, $p_i \mid \left( \frac n {p_i} -1 \right)$. That is, that for each prime factor $p_i$, you ...
2k views

### Recognize most smaller primes with a regex

This time, you are working on a regex. Your regex is meant to approximately full-match the base-10 representations of primes $0 \le p < 1000$, while ignoring any non-numeric string or composite ...
3k views

### Is this a Permutation of 1..n

Input a non-empty array with $n$ positive integers. Test if the input array contains every integer in $1\cdots n$. In case you prefer 0-indexed numbers, you may choose to input an array of non-...
2k views

### Is it a checkered tiling?

Background A checkered tiling of a rectangular grid is a tiling using some polyominoes, where each region can be colored either black or white so that no two polyominoes sharing an edge has the same ...
4k views

### Is there a single straight line in the matrix?

Inspired by Wzl Determine if a given square binary matrix has exactly one row or column consisting of entirely 1s, and the rest of the matrix is ...
2k views

### Is there a left-right connection?

Task Given a square array of 0s and 1s, determine whether or not there exists a path of 1s connecting the leftmost and rightmost columns. A path can take steps of one unit up, down, left or right, ...
2k views

### Is it a valid Parker Square

5 Years ago, this happened, and then it became sort of a meme. Challenge The Challenge today is, to check if a "magic square" is a valid parker square. What is a Real Magic square? All the ...
2k views

### But, Is It Art?

But Is It Art? is an esolang created by ais523, where one step is break the program into orthogonally connected "tiles": A BBBB A B B AA CC A CC Each ...
317 views

### Help me prove the Four Color Theorem!

This is not just another challenge asking you to color random maps... In this challenge, you are asked to write a program that is actually used in the formal proof of the Four Color Theorem. First I ...
1k views

### Is this FEN board a Fischer random chess starting board?

Introduction Fischer random chess, also known as Chess960 for the 960 valid starting boards, is a variant of chess where each player's pieces are randomly shuffled at the start. As a reminder, each ...
6k views

### iHateOddNumbers

Task Given a non-negative number, check if it's odd or even. In case it's even, output that number. Otherwise, throw any exception/error that your language supports, and stop the program. Example with ...
244 views

### Solve the halting problem for S combinatory logic

Background Combinatory logic is a system where a term is written using a finite set of combinators and function application between terms, and reduction rules are defined for each combinator. The well-...
873 views

### Are vertices in a clockwise order?

Your program must accept as input six numbers, which describe a triangle - for example, the inputs 80, 23, 45, 1, 76, -2 describe a triangle with vertices (80, 23), (45, 1), and (76, -2). The input ...
1k views

Background Link-a-Pix is a puzzle on a rectangular grid, where the objective is to reveal the hidden pixel art by the following rules: Connect two cells with number N with a line spanning N cells, so ...
1k views

### Dimensional Chess positions

Task Any one of these two: Determine if a given position (an ordered non-empty collection of integers in the range ‒8 to 8, or ‒7 to 7 if you want) is a valid Dimensional Chess position. List all the ...
2k views

### Is it a chess cycle?

Inspired by a discussion from the Esolangs.org unofficial Discord Server. Instructions A chess cycle is an arrangement of a chess board where each piece must attack one other piece, and only one other ...
167 views

### Are We Fast And Furious? [closed]

There are currently nine feature length films in the core Fast & Furious/The Fast and the Furious media franchise, a series of films about bald men scowling and driving cars very fast. The names ...
231 views

### Determine if a dot(comma) program halts

Dotcomma is a simple esolang I made a while ago that only uses four operators: [.,]. In this challenge, you'll determine if a dotcomma program consisting only of <...
2k views

### I before E, except after C

You may be aware of the famous old rhyme, "I before E, except after C". It is a rule taught to aid in the spelling of certain English words. Quoting Wikipedia: If one is not sure whether a ...
2k views

### Are All the Items the Same?

Given a list of non-negative integers, return whether or not that list is all the same number. Rules Input and output can be taken/given in any reasonable and convenient format Truthy/Falsey values ...
3k views

### Did I die or not?

Given a permutation of the alphabet and an intended "word", determine if the word was guessed in a game of Hangman, where the permutation is the list of guesses. For example, given ...
369 views

I want to avoid responding to illegal or spoofed addresses. One type that's easy to detect is an address that should not exist on a packet received by my router: a special-use address. Challenge Given ...
from Wikipedia, a number is called B-powersmooth if all prime powers $p^v$ that divide the number satisfy $p^v \leq B$. B-powersmoothness is important, for example, for Pollard's p-1 factorization ...