Questions tagged [decision-problem]
For challenges which involve deciding whether or not the input meets certain criteria, and outputting some data, representing that decision.
705
questions
23
votes
23
answers
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:
...
- 33.6k
11
votes
5
answers
442
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 ...
- 69.3k
25
votes
5
answers
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 ...
- 92.2k
13
votes
2
answers
511
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 ...
- 69.3k
8
votes
5
answers
341
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 ...
- 69.3k
16
votes
19
answers
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 ...
- 18.4k
18
votes
3
answers
733
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.
...
- 92.2k
21
votes
11
answers
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 &...
- 69.3k
5
votes
3
answers
160
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 ...
- 69.3k
30
votes
14
answers
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 ...
- 48.4k
20
votes
6
answers
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 ...
- 3,667
32
votes
46
answers
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-...
- 32.1k
30
votes
12
answers
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 ...
- 69.3k
34
votes
26
answers
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 ...
- 48.4k
20
votes
16
answers
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, ...
- 541
26
votes
9
answers
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 ...
- 6,366
17
votes
7
answers
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 ...
- 48.4k
22
votes
1
answer
727
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 ...
- 749
13
votes
8
answers
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 ...
- 11.3k
32
votes
86
answers
7k
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 ...
- 483
16
votes
2
answers
315
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-...
- 69.3k
3
votes
8
answers
911
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 ...
- 641
25
votes
14
answers
1k
views
1D monochrome Link-a-Pix solvability
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 ...
- 69.3k
18
votes
9
answers
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 ...
- 29.1k
24
votes
4
answers
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 ...
- 26.6k
9
votes
1
answer
174
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 ...
- 191
13
votes
2
answers
297
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 <...
- 18.4k
26
votes
5
answers
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 ...
- 20.3k
25
votes
57
answers
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 ...
- 26.3k
18
votes
19
answers
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 ...
- 48.4k
10
votes
6
answers
382
views
Rejecting invalid IPv4 addresses
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 ...
- 201
17
votes
19
answers
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 ...
- 4,615
12
votes
15
answers
794
views
Check if B is composed of substrings of A of length n
Given two strings \$ A \$ and \$ B \$ and a positive integer \$ n \$, determine whether \$ B \$ is composed entirely of (possibly overlapping) strict substrings of \$ A \$ of a length of at least \$ ...
- 23k
23
votes
5
answers
1k
views
Can this pattern be made with dominoes?
Given a pattern of squares on a grid, determine if it is possible to create that pattern with non-overlapping dominoes. In case you are not familiar, a domino is a rectangular shape created by joining ...
- 9,841
25
votes
10
answers
1k
views
Unique half rainbows
If we take a positive integer \$n\$ and write out its factors. Someone can determine \$n\$ just from this list alone. In fact it is trivial to do this since the number is its own largest factor.
...
- 92.2k
13
votes
4
answers
1k
views
I ain't no Fortunate sum
The primorial \$p_n\#\$ is the product of the first \$n\$ primes. The sequence begins \$2, 6, 30, 210, 2310\$.
A Fortunate number, \$F_n\$, is the smallest integer \$m > 1\$ such that \$p_n\# + m\$ ...
- 48.4k
27
votes
11
answers
2k
views
Test if a Gray code is Beckett
Background
An \$n\$-bit Gray code is an ordering of \$2^n\$ binary sequences so that adjacent sequences always differ by exactly one bit.
A Beckett-Gray code is a special kind of Gray code. In ...
- 69.3k
20
votes
1
answer
410
views
Is this Game of Go configuration fully alive?
Background
This challenge is about the Game of Go. Here are some rules and terminology relevant to this challenge:
Game of Go is a two-player game, played over a square board of size 19x19.
One of ...
- 69.3k
25
votes
13
answers
5k
views
Is it a vampire number?
Repost and improvement of this challenge from 2011
A vampire number is a positive integer \$v\$ with an even number of digits that can be split into 2 smaller integers \$x, y\$ consisting of the ...
- 48.4k
15
votes
6
answers
820
views
Golf this Thumb-2 Constant!
One thing that is constantly frustrating when golfing ARM Thumb-2 code is generating constants.
Since Thumb only has 16-bit and 32-bit instructions, it is impossible to encode every immediate 32-bit ...
- 4,500
25
votes
14
answers
4k
views
Is this an L-shape?
Background
An L-shape is defined as a polyomino which can be made by extending two rectangular legs in orthogonal directions from a full square (called a pivot). The size of the square should be at ...
- 69.3k
32
votes
16
answers
6k
views
Is it a lobster number?
Introduction
A "lobster number", by my own designation, is a number that contains within itself all of its prime factors. The "lobster" description was inspired by the recent ...
- 429
12
votes
3
answers
420
views
A graph and its seven closures
Background
A little while ago, someone posted an interesting puzzle on Math.SE:
What is the smallest digraph (directed graph) G where the following eight graphs are all distinct:
G, the original ...
- 69.3k
14
votes
8
answers
2k
views
Is my triangle on the lattice?
Write a program or function which takes three positive integers \$a, b, c\$ and returns/outputs one value if there is, and a different value if there isn't, a triangle on the square lattice, whose ...
- 407
9
votes
3
answers
958
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 ...
- 113
20
votes
19
answers
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 ...
- 13.6k
9
votes
8
answers
513
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 ...
- 59
13
votes
2
answers
411
views
Can you make your way through the Ulam spiral?
You will be given a point (x,y) relative to the center of the Ulam spiral (the center being the point which represents one), and length ...
- 11.8k
30
votes
21
answers
3k
views
Can we spell a third number?
You are given two strings, each consisting of the English word for a number between 1 and 13:
...
- 176k
21
votes
23
answers
1k
views
Compatible strings
When studying numerology, you can say two words (strings consisting entirely of letters) are compatible if they produce the same number under the following operation (let's use the string ...
- 48.4k