# Questions tagged [decision-problem]

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

589 questions
Filter by
Sorted by
Tagged with
714 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: ...
306 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 ...
998 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 ...
469 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 ...
257 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 ...
708 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 &...
147 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 ...
3k 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 ...
269 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 ...
236 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-...
870 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 ...
163 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 ...
227 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 ...
364 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 ...
1k views

### Check B-powersmoothness

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 ...
759 views

632 views

### Validating a Battleship board

Do you know the game Battleship? Well, I want to play with my little brother, but before we can begin we need to set up our ships on the board. This is your input. Now, we need to check that the ships ...
2k views

### Vandalizing Marquees

A marquee is a low-tech board that allows customizable letters. For example, here is a marquee: SALE ON SNEAKERS However, someone might come along and vandalize it ...
497 views

### Equality up to Swapping

inputs / outputs your program/function/routine/... will be a predicate on two tuple sequences; call it relation . for the purpose of simplicity we use natural ...