Questions tagged [decision-problem]
For challenges which involve deciding whether or not the input meets certain criteria, and outputting some data, representing that decision.
719
questions
14
votes
8
answers
2k
views
But is it a pretty place?
Your challenge, should you choose to accept it, is to take as input:
A program in DirectionLang (as an ASCII string consisting of DirectionLang instructions)
A list of pairs of integers, henceforth ...
- 1,533
7
votes
1
answer
234
views
Find run ascending lists faster
In this question I asked you to determine if a run ascending list could be made. It was code-golf so naturally most the answers are very slow. But what if we want it to be fast. In this challenge I ...
- 94.1k
13
votes
8
answers
922
views
Can a run ascending list be made?
A run ascending list is a list such that runs of consecutive equal elements are strictly increasing in length. For example [1,1,2,2,1,1,1] can be split into three ...
- 94.1k
18
votes
23
answers
3k
views
+500
Crossing a Lily Pond
The Narrative
You are a frog who is at the edge of a pond with waterlilies. You would like to cross the pond without getting wet, so you plan to jump from lily to lily. There is, however, one problem: ...
- 1,457
12
votes
7
answers
2k
views
Is Wally there?
Inpired by recent Stand-up Maths' video.
Task
Wrapping a list x can be seen as inserting "line-breaks" into x every <...
- 13.8k
24
votes
20
answers
5k
views
Is this expression Python 2/3 safe?
Given an expression like 4 / 2 + 3, determine whether the expression has the same value in Python 2 and Python 3. Recall that in Python 2 division rounds down (so ...
- 13.7k
18
votes
9
answers
2k
views
Is this polynomial a square?
Given an integral polynomial \$p\$, determine if \$p\$ is a square of another integral polynomial.
An integral polynomial is a polynomial with only integers as coefficients.
For example, \$x^2+2x+1\$ ...
- 40.4k
19
votes
6
answers
2k
views
Is it 1089-able?
\$ 1089 \$ is a very special number. To prove why, select any 3-digit number whose first and last digits differ by at least 2. Then, reverse the digits, and take the difference of these two numbers. ...
- 20.4k
8
votes
5
answers
758
views
Will this makina program halt?
makina is a cell-based esolang composed of automata which move around a grid. These automata follow paths of instructions that direct their movement. Your task is to, given a makina program using only ...
- 5,301
15
votes
14
answers
1k
views
Ragged list pattern matching
Given a pattern and a ragged list of positive integers, your task is to decide whether the pattern matches the ragged list.
The pattern is also represented by a ragged list. But in addition to ...
- 40.4k
14
votes
5
answers
723
views
Is this propositional formula an instance of an axiom?
Please help me automate my discrete mathematics homework. Given a valid propositional formula, check if it is an instance of one of Łukasiewicz's axioms. Here's how it works.
A term can be defined ...
- 971
17
votes
9
answers
2k
views
Is it irrational?
Your task is to make a program that decides if a real number between 0 and 1 is irrational or not. As stated, this is obviously impossible, so instead we will use the following definition:
...
- 6,795
22
votes
1
answer
676
views
Can you draw this in one stroke?
Related | Related
Given an ASCII art with |, _, and , check if you can draw the art in one ...
- 7,457
20
votes
20
answers
2k
views
Can the Tune be Played?
Can the Tune be Played?
Explanation
A broken musical keyboard has keys labelled with positive integers. It is broken in two ways:
It takes a long time to process key presses: after pressing the key ...
- 977
20
votes
20
answers
3k
views
Gambling with an Alien
You met a 4-th dimensional being who challenged you to a game of dice. The rules are simple: each player rolls 3 6-sided dice and takes the sum of each combination of 2 dice. The player with the ...
- 391
12
votes
3
answers
536
views
Solve an alien wordle
You've arrived on an alien planet. The writing system, the culture and the language there are completely foreign to any language you know. But somehow they are all playing wordle already.
So as a ...
- 94.1k
15
votes
8
answers
603
views
Is it a sub-permutation?
A finite-permutation is a function which takes an \$n\$-tuple and produces an \$n\$-tuple such that every element of the input is present in the output, and the ordering does not rely on the values of ...
- 94.1k
19
votes
27
answers
2k
views
Is it a tower permutation?
A tower is made out of layers, each one being one unit shorter than the one below it. Every layer is completely on top of the previous layer. For example, here is a tower along with it's height map:
<...
- 6,795
30
votes
35
answers
3k
views
Is it a fibonacci-like sequence?
The Fibonacci Sequence is a sequence of positive integers where the first two elements are 1 and the rest are the sum of the previous two. It begins \$1, 1, 2, 3, 5, 8, 13\$ and continues forever.
But ...
- 32.6k
15
votes
2
answers
856
views
Golf the prime numbers in Shue
I'd like to introduce a new? programming language I call Shue (Simplified Thue). It has very simple syntax.
Here is a program that checks if an input is divisible by three:
...
- 6,795
15
votes
3
answers
323
views
Is it a bigger regex?
You are given two regexes and your task is to determine if the strings matched by the first regex are a subset of the strings matched by the second regex.
For this we are going to use a limited ...
- 6,795
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
363
views
Mahjong Checker
Mahjong is a tabletop game played using tiles. It features three "number" suits (pins, sous, mans, represented as p, s ...
- 4,947
20
votes
1
answer
509
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 ...
- 11.3k
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,826
22
votes
6
answers
791
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\$ ...
- 2,987
10
votes
4
answers
284
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 ...
- 17k
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,199
12
votes
8
answers
523
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 ...
- 94.1k
21
votes
4
answers
892
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 ...
- 40.4k
30
votes
9
answers
675
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 ...
- 94.1k
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.8k
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.6k
9
votes
3
answers
307
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,795
26
votes
53
answers
4k
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. ...
- 5,301
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 ...
- 94.1k
6
votes
10
answers
782
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,871
14
votes
13
answers
970
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 ...
- 94.1k
16
votes
6
answers
757
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 ...
- 94.1k
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 (...
- 533
5
votes
6
answers
290
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 ...
- 70k
8
votes
10
answers
942
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.8k
14
votes
11
answers
712
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 ...
- 70k
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.6k
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,871
11
votes
3
answers
293
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,075
15
votes
10
answers
793
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 ...
- 70k
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 ...
- 27.7k
15
votes
7
answers
749
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 = \{\...
- 48.4k