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
6 votes
6 answers
587 views

Is it an ordinal?

Background (feel free to skip) Ordinals are the abstract representation of well-orders. A well-order of a set is a total order, which basically means that every element in the set can be compared ...
user avatar
  • 6,705
22 votes
21 answers
945 views

Pairs at every distance

Given a list \$X\$ of 2 or more integers, output whether, for all \$n\$ such that \$0 \leq n < length(X)-2\$, there exists a pair of equal integers in \$X\$ separated by exactly \$n\$ elements. In ...
user avatar
8 votes
5 answers
902 views

Is it shuffled FizzBuzz?

A twin of this. FizzBuzz is where a range of positive integers is taken, and numbers divisible by 3 are replaced with "Fizz", divisible by 5 with "Buzz" and divisible by 15 with &...
user avatar
  • 30.6k
13 votes
1 answer
183 views

Is this a strange pond?

In this challenge we considered a frog hopping around a lily pond. To recap the lily pond was represented as a finite list of positive integers. The frog can only jump forward or backwards by a ...
user avatar
  • 88.8k
18 votes
16 answers
2k views

Check a mushroom forest

In this challenge you will receive a list of pairs of non-negative integers representing a mushroom forest. Each pair represents a mushroom whose center is at that horizontal coordinate. The only ...
user avatar
  • 88.8k
13 votes
4 answers
257 views

Is it a heapable sequence?

A binary max heap is a rooted tree with integer labeled nodes such that: No node has more than 2 children. The label of every node is greater than all of its children. We say a sequence of integers ...
user avatar
  • 1,221
18 votes
25 answers
2k views

Is it a valid list?

Given a string like [[[],[[]]],[]], made of only commas and square brackets, your challenge is to determine whether it represents a list. A list is either: ...
user avatar
  • 30.6k
30 votes
5 answers
5k views

Can the 🐸 visit all the 🪷?

In this challenge you will be simulating a frog jumping from lily-pad to lily-pad in a pond. A frog's jump distance is uniquely determined by the size of the lily pad it jumps from. So for example ...
user avatar
  • 88.8k
19 votes
12 answers
2k views

Detect Mongolian vowel harmony

The Mongolian language has "vowel harmony". In short the vowel harmony means that certain vowels are not allowed to be placed next to each other in a word. This means that suffixes of ...
user avatar
  • 88.8k
21 votes
22 answers
10k views

`lol` is an ambigram, `dad` isn't

Given a word, decide if it is an ambigram. When rotated: b > q d > p l > l n > u o > o p > d q > b s > s u > n x > x z > z Assume ...
user avatar
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 ...
user avatar
7 votes
1 answer
214 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 ...
user avatar
  • 88.8k
13 votes
8 answers
911 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 ...
user avatar
  • 88.8k
18 votes
23 answers
3k views

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: ...
user avatar
  • 1,287
12 votes
7 answers
1k 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 <...
user avatar
  • 11.8k
24 votes
20 answers
4k 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 ...
user avatar
  • 11.8k
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\$ ...
user avatar
18 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. ...
user avatar
  • 17.6k
9 votes
5 answers
745 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 ...
user avatar
  • 3,380
14 votes
13 answers
883 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 ...
user avatar
14 votes
5 answers
704 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 ...
user avatar
18 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: ...
user avatar
  • 6,705
21 votes
1 answer
538 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 ...
user avatar
  • 4,453
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 ...
user avatar
  • 837
20 votes
21 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 ...
user avatar
  • 391
13 votes
3 answers
516 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 ...
user avatar
  • 88.8k
15 votes
8 answers
598 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 ...
user avatar
  • 88.8k
20 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: <...
user avatar
  • 6,705
32 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 ...
user avatar
  • 30.6k
16 votes
2 answers
807 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: ...
user avatar
  • 6,705
15 votes
3 answers
304 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 ...
user avatar
  • 6,705
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 ...
user avatar
  • 237
5 votes
3 answers
321 views

Mahjong Checker

Mahjong is a tabletop game played using tiles. It features three "number" suits (pins, sous, mans, represented as p, s ...
user avatar
  • 3,029
19 votes
1 answer
467 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 ...
user avatar
  • 4,726
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 ...
user avatar
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\$. ...
user avatar
  • 3,941
22 votes
6 answers
759 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\$ ...
user avatar
10 votes
4 answers
277 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 ...
user avatar
  • 12.8k
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 ...
user avatar
  • 3,079
12 votes
8 answers
517 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 ...
user avatar
  • 88.8k
21 votes
4 answers
836 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 ...
user avatar
30 votes
9 answers
669 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 ...
user avatar
  • 88.8k
17 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 ... ...
user avatar
  • 21.5k
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 (...
user avatar
  • 30.6k
9 votes
3 answers
285 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 ...
user avatar
  • 6,705
20 votes
42 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. ...
user avatar
  • 3,380
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 ...
user avatar
  • 88.8k
6 votes
10 answers
765 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: ...
user avatar
  • 2,509
15 votes
13 answers
948 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 ...
user avatar
  • 88.8k
17 votes
6 answers
747 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 ...
user avatar
  • 88.8k

1
2 3 4 5
14