Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
18 votes
11 answers
1k views

Identify a "reverse checkers" position

Task A reverse checkers position is a chess position where every piece for one player is on one colour and every piece for the other player is on the other colour. Your task is to find if the given (...
user avatar
5 votes
6 answers
268 views

AoCG2021 Leftover: Recursive Combat

This challenge is one of the two challenges which were planned for Advent of Code Golf 2021, but didn't fit into the 25-day schedule. Related to AoC2020 Day 22, Part 2. Combat is a simple two-player ...
user avatar
  • 62.8k
8 votes
10 answers
919 views

AoCG2021 Day 24: Is the bus company cheating?

Part of Advent of Code Golf 2021 event. See the linked meta post for details. Related to AoC2020 Day 13, Part 2. Why Bubbler isn't posting this; Why Riker isn't posting this A shuttle bus service ...
user avatar
  • 21.4k
14 votes
11 answers
687 views

AoCG2021 Day 20: Wonky license check

Part of Advent of Code Golf 2021 event. See the linked meta post for details. Related to AoC2018 Day 8. The license file for an imaginary software system is defined as follows: The entire file is a ...
user avatar
  • 62.8k
24 votes
17 answers
2k views

Is the room lit up?

Imagine you have a grid where some squares are walls, some are empty, and some are lights that shine for arbitrary distances in the four cardinal directions until they meet walls: ...
user avatar
  • 30.5k
24 votes
27 answers
1k views

Check if the string is reshaped

Challenge Given an input string X, determine if X can be obtained from reshaping a strict prefix of itself (a prefix that is not ...
user avatar
  • 2,509
11 votes
3 answers
286 views

Is it a valid line in "Girls & Boys"?

Intro Blur's song Girls & Boys featured the lines girls who are boys who like boys to be girls who do boys like they're girls, who do girls like they're boys ...
user avatar
  • 2,045
15 votes
10 answers
780 views

AoCG2021 Day 14: Adjusting dancing program's period

Part of Advent of Code Golf 2021 event. See the linked meta post for details. Related to AoC2017 Day 16. I'm using the wording from my Puzzling SE puzzle based on the same AoC challenge instead of the ...
user avatar
  • 62.8k
15 votes
21 answers
1k views

AoCG2021 Day 12: Oct's Fool

Part of Advent of Code Golf 2021 event. See the linked meta post for details. The story continues from AoC2017 Day 11. Obligatory why me and not Bubbler link After having rescued a child process lost ...
user avatar
  • 22.1k
15 votes
7 answers
735 views

Are these the basis vectors?

A basis of a vector space \$V\$ is a set of vectors \$B\$ such that every vector \$\vec v \in V\$ can be uniquely written as a linear combination of the vectors in \$B\$. In other words, let \$B = \{\...
user avatar
24 votes
29 answers
3k views

AoCG2021 Day 2: Naughty or nice?

Part of Advent of Code Golf 2021 event. See the linked meta post for details. The story continues from AoC2015 Day 5, Part 2. Santa needs help figuring out which strings in his text file are naughty ...
user avatar
  • 62.8k
21 votes
5 answers
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, ...
user avatar
  • 30.5k
29 votes
31 answers
3k 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 <...
user avatar
  • 6,359
18 votes
21 answers
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 ...
user avatar
  • 88.3k
28 votes
11 answers
2k 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 ...
user avatar
  • 6,705
18 votes
6 answers
748 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 ...
user avatar
9 votes
2 answers
244 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 ...
user avatar
  • 10.5k
19 votes
3 answers
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 ...
user avatar
  • 62.8k
20 votes
7 answers
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 ...
user avatar
19 votes
15 answers
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 ...
user avatar
  • 10.5k
16 votes
7 answers
873 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....
user avatar
  • 62.8k
13 votes
2 answers
567 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 (...
user avatar
  • 62.8k
15 votes
2 answers
598 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 ...
user avatar
9 votes
9 answers
853 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\$ (...
user avatar
  • 12.8k
24 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: ...
user avatar
  • 30.5k
11 votes
5 answers
401 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 ...
user avatar
  • 62.8k
24 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 ...
user avatar
  • 88.3k
13 votes
2 answers
502 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 ...
user avatar
  • 62.8k
8 votes
5 answers
307 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 ...
user avatar
  • 62.8k
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 ...
user avatar
18 votes
3 answers
725 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. ...
user avatar
  • 88.3k
21 votes
10 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 &...
user avatar
  • 62.8k
5 votes
3 answers
155 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 ...
user avatar
  • 62.8k
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 ...
user avatar
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 ...
user avatar
32 votes
43 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-...
user avatar
  • 29.4k
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 ...
user avatar
  • 62.8k
33 votes
25 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 ...
user avatar
19 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, ...
user avatar
  • 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 ...
user avatar
  • 4,423
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 ...
user avatar
22 votes
1 answer
706 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 ...
user avatar
  • 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 ...
user avatar
  • 11k
31 votes
82 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 ...
user avatar
16 votes
2 answers
286 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-...
user avatar
  • 62.8k
3 votes
8 answers
889 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 ...
user avatar
24 votes
13 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 ...
user avatar
  • 62.8k
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 ...
user avatar
  • 27.7k
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 ...
user avatar
  • 25.2k
9 votes
1 answer
171 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 ...
user avatar

1
2
3 4 5
14