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
21 votes
21 answers
1k views

Is given number a concat of two squares

Given a positive integer, determine if it can be represented as a concatenation of two square numbers. Concatenated numbers may not begin with 0 (except for 0). Any leading zeros in input should be ...
  • 237
5 votes
3 answers
345 views

Mahjong Checker

Mahjong is a tabletop game played using tiles. It features three "number" suits (pins, sous, mans, represented as p, s ...
  • 4,557
19 votes
1 answer
489 views

Can I wall glitch to there?

Background In a 2d game that I play, each screen is a 2d grid of tiles with walls and walkable tiles, with the player only able to travel on walkable tiles, and being stopped by walls. When the player ...
  • 9,979
7 votes
9 answers
2k views

Write a spam-detection program

You work for a social media platform, and are told to create a program in a language of your choice that will automatically flag certain post titles as "spam". Your program must take the ...
  • 675
21 votes
33 answers
3k views

Sum of two squares

Given a nonnegative integer \$n\$, determine whether \$n\$ can be expressed as the sum of two square numbers, that is \$\exists a,b\in\mathbb Z\$ such that \$n=a^2+b^2\$. ...
  • 4,696
22 votes
6 answers
772 views

Check if a matrix is Zarankiewicz-maximal

My final-year project at the National University of Singapore is on Zarankiewicz's problem: What is the maximum number of 1s in an \$m×n\$ binary matrix (\$m\$ rows and \$n\$ columns) with no \$a×b\$ ...
  • 1,273
10 votes
4 answers
281 views

Is it a possible Hearts result?

Hearts is a 4-player game that uses the following scoring rules: Everyone starts with score 0. Each round every player gets a non-negative amount of points. The sum of the points is 26, and at least ...
  • 13k
17 votes
28 answers
1k views

Reversed Multiple Pair

Intro Two numbers are a reversed multiple pair if they satisfy the following property: $$ a\cdot b = \operatorname{reversed}( (a-1)\cdot b ) $$ Here, \$\operatorname{reversed}()\$ means to reverse the ...
  • 3,179
12 votes
8 answers
521 views

Is there a stable way to stack these?

If we have a binary matrix then we will say that a \$1\$ is stable if it is in the bottom row or it is directly adjacent to a \$1\$ which is stable. In other words there must be a path to the bottom ...
  • 91.5k
21 votes
4 answers
868 views

Is this hexagon symmetric?

TLDR: This is the hexagonal version of Is this square symmetrical? Given a hexagonal grid, decide if it is symmetric. The shape of the grid is a regular hexagon. Each cell in the grid has two possible ...
  • 38.8k
30 votes
9 answers
674 views

Predicting pumpkin planting plans' potential problems

You are going to be planting pumpkins soon, and you are preparing your supplies. Pumpkins come in all sorts of sizes and have their sizes written on the seed bag. A pumpkin that is size n will grow ...
  • 91.5k
18 votes
24 answers
1k views

Is this word in standard order?

Let \$ A \$ represent the alphabet, such that \$ A_1 = \$ a and \$ A_{26} = \$ z. Let's define that a word \$ W = w_1 w_2 ... ...
  • 22.7k
17 votes
6 answers
1k views

Is this continuous terrain?

Very related You're given a piece of ASCII art representing a piece of land, like so: /‾\ __/ ‾\_ \_/‾\ \ Since an overline (...
  • 32.8k
9 votes
3 answers
293 views

Solve nonimplication-SAT

Background This is Post's lattice: Credit: EmilJ It denotes the lattice of all clones on a two-element set {0, 1}, ordered by inclusion (from Wikipedia). That can ...
  • 6,725
25 votes
45 answers
3k views

Is it a pure word?

Introduction A pure word (or perfect word), as defined by me, is a word where the sum of the position in the alphabet of each letter in the word is perfectly divisible by the total length of the word. ...
  • 4,504
17 votes
10 answers
1k views

Is this a word?

Toki pona is a minimalist constructed language, and thus it has minimalist phonotactics (rules describing what sounds make valid words). Toki Pona has 8 consonant sounds ...
  • 91.5k
6 votes
10 answers
777 views

Generate Fmbalbuena Numbers

My user id is 106959 How to check if the number is Fmbalbuena number? First Step: Check if the number of digits is a multiple of 3: ...
  • 2,671
14 votes
13 answers
960 views

Compare shapeless lists

Let's have a ragged list containing no values, only more lists. For example: [[[],[[]],[],[]],[],[[],[],[]],[]] And the list will be finite, meaning that ...
  • 91.5k
16 votes
6 answers
752 views

Mutually recursive lists

Let's define a simple function \$f\$ which takes an integer and produces a list: \$ f(n) = [g(1),g(2),\dots,g(n)] \\ g(n) = [f(0),f(1),\dots,f(n-1)] \$ We can then calculate the first couple of values ...
  • 91.5k
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 (...
5 votes
6 answers
280 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 ...
  • 67.2k
8 votes
10 answers
933 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 ...
  • 22.7k
14 votes
11 answers
694 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 ...
  • 67.2k
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: ...
  • 32.8k
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 ...
  • 2,671
11 votes
3 answers
289 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 ...
  • 2,065
15 votes
10 answers
784 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 ...
  • 67.2k
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 ...
  • 24.5k
15 votes
7 answers
740 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 = \{\...
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 ...
  • 67.2k
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, ...
  • 32.8k
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 <...
  • 6,616
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 ...
  • 91.5k
27 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 ...
  • 6,725
18 votes
6 answers
754 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 ...
9 votes
2 answers
250 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 ...
  • 10.8k
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 ...
  • 67.2k
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 ...
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 ...
  • 10.8k
16 votes
7 answers
881 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....
  • 67.2k
14 votes
2 answers
572 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 (...
  • 67.2k
15 votes
2 answers
612 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 ...
9 votes
9 answers
886 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\$ (...
  • 13k
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: ...
  • 32.8k
11 votes
5 answers
432 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 ...
  • 67.2k
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 ...
  • 91.5k
13 votes
2 answers
510 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 ...
  • 67.2k
8 votes
5 answers
329 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 ...
  • 67.2k
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 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. ...
  • 91.5k

1
2
3 4 5
14