Skip to main content

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
20 votes
12 answers
2k views

Recognize a counting tree

Let a counting tree be a rooted tree in which every node is labeled with the number of descendants it has. We can represent such trees as ragged lists with each node being represented by a list ...
Wheat Wizard's user avatar
  • 99k
10 votes
7 answers
622 views

It's a dog! (Or is it?)

The city defines a dog as any living entity with four legs and a tail. So raccoons, bears, mountain lions, mice, these are all just different sizes of dog. Given an ASCII-art image of an animal, ...
noodle person's user avatar
22 votes
27 answers
3k views

Sum of Consecutive Squares

Your task Given a integer input, \$ n \$ (such that \$ n > 1 \$), decide whether it can be written as the sum of (at least 2) consecutive square numbers. Test cases Truthy: ...
The Thonnu's user avatar
  • 18.2k
16 votes
14 answers
1k views

Painting with Line Filler

Given a matrix of positive integers, output whether it's possible to generate it by starting with an empty1 matrix of the same dimensions and repeatedly filling a whole row or a whole column with the ...
l4m2's user avatar
  • 24.9k
16 votes
12 answers
1k views

Is this a shift matrix?

A Shift matrix is a binary matrix with one superdiagonal or subdiagonal formed by only ones, everything else is a zero. A superdiagonal/subdiagonal is a diagonal parallel to the main diagonal, which ...
math scat's user avatar
  • 9,408
22 votes
24 answers
3k views

Is it true? Ask Pip!

Title is an homage to this classic challenge In Pip, the Scalar data type encompasses strings and numbers. A Scalar value is truthy in most cases. It is falsey only if: It is the empty string ...
DLosc's user avatar
  • 39.9k
19 votes
37 answers
2k views

Friend, or Foe?

Task Provide two programs/functions A and B (not necessarily in the same language) with the following properties: Either ...
AlephSquirrel's user avatar
6 votes
2 answers
387 views

Is this position a pure mirror mate?

Task A pure mirror checkmate is a checkmate position, where the mated king is surrounded by 8 empty squares which are attacked or guarded by the winning side exactly once. You will be given a valid ...
double-beep's user avatar
17 votes
3 answers
401 views

CGAC2022 Day 11: Reduce, Reuse, Regift

Traditionally presents are kept secret in boxes wrapped in paper. Since the ice caps are melting Santa Claus has begun to investigate some ways they might make the whole gift wrapping operation a ...
Wheat Wizard's user avatar
  • 99k
16 votes
9 answers
2k views

CGAC2022 Day 4: Can Santa fit down the chimney?

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details. Christmas is coming up, and Santa hasn't kept to his diet very well this year. Due to his size, he is getting the ...
jezza_99's user avatar
  • 2,511
12 votes
0 answers
512 views

Is it a legal atomic chess move?

Background and Rules There is a variant of chess called atomic chess, which follows essentially the same rules as normal chess, except that pieces explodes other pieces around them when captured. In ...
Aiden Chow's user avatar
  • 13.7k
12 votes
3 answers
505 views

Decide whether a given field of the board game 'Qwirkle' is valid (according to game rules)

The famous game of Qwirkle has simple but intricate rules (See part 2 of this question for a summary of the rules!) The Challenge You are somehow (text input, function parameter, whatever) given a ...
Squareoot's user avatar
  • 145
15 votes
13 answers
1k views

Lengthy numbers type A : remove all occurrences of length

Given a non negative integer number tell if it can be erased by repeatedly removing all occurrences of the length of that number from it including overlapping matches. Erasing means cancel all its ...
AZTECCO's user avatar
  • 10.8k
21 votes
6 answers
2k views

For xor Young (15+)

A Young diagram is a rectangular binary mask whose every row and every column are sorted in descending order. It is easy to check that every rectangular binary mask can be formed by xor-ing together a ...
loopy walt's user avatar
  • 16.7k
19 votes
9 answers
1k views

Is this substring list ambiguous?

Given a set of substrings, such as [ca, ar, car, rd], it's possible to create infinitely many strings by concatting them together. Some examples of this for the ...
Rydwolf Programs's user avatar
3 votes
2 answers
537 views

How Mondrian is your fine art collection? [closed]

For the purpose of this challenge a rectangular piece of ASCII art is Mondrian if it looks the same upside down. What does "looks the same" mean? A feature is any orthogonally connected ...
loopy walt's user avatar
  • 16.7k
26 votes
14 answers
2k views

Is this series of quotes valid Python?

Python string parsing has quite a few edge cases. This is a string: "a" Putting 2 strings immediately after each other implicitly concatenates them, so ...
mousetail's user avatar
  • 12.7k
19 votes
15 answers
1k views

Character insertion on letterboards

You know those letterboards outside old-style cinemas which show upcoming films - perhaps you have a miniature one in your home? If you've operated one, you'll know that you can normally add letters ...
FlipTack's user avatar
  • 14.7k
22 votes
9 answers
1k views

A pieceful standoff

This challenge requires a small amount of knowledge about chess. A description of the details required can be found at the bottom if you are not familiar with chess or want a refresher. For a certain ...
Wheat Wizard's user avatar
  • 99k
22 votes
12 answers
2k views

Does the sequence shut the box?

Determine whether a given sequence could be a winning sequence for the game shut the box. Background There are a few variants to this game, so I'll clarify the rules here. Play begins with 12 tiles (1 ...
CursorCoercer's user avatar
33 votes
37 answers
3k views

Is it an alphadrome?

An alphadrome is a word in which each letter in the first half of the word "reflects" its alphabetical "opposite" in the second half of the word. Write a program or function that ...
Jordan's user avatar
  • 10.1k
44 votes
28 answers
6k views

Tut-tut-tut-tut-tut

The string tut-tutut-tut-tuttut-tut can be constructed with overlapping or concatenated instances of the word tut-tut: ...
Sisyphus's user avatar
  • 14.8k
21 votes
5 answers
653 views

Does there exist a synchronizing word?

A complete deterministic finite automaton is a machine, with some states. Each state in the automaton has, for each character in the alphabet, a pointer to a state (not necessarily a different one). ...
Command Master's user avatar
20 votes
9 answers
1k views

Is This an Equivalence Relation?

Given a relation, and a domain, output whether the relation is an equivalence relation. Context For this challenge, a relation is defined as being a set of ordered pairs that is a subset of the ...
lyxal's user avatar
  • 33.7k
18 votes
25 answers
2k views

Is it a properly tiered list?

A ragged list is a (finite depth) list where each element is either a positive integer or a ragged list. A ragged list is properly tiered if it contains either all positive integers or all properly ...
Wheat Wizard's user avatar
  • 99k
19 votes
14 answers
3k views

Is this graph a tree?

Given an undirected graph, find out if it is a tree. A tree is an undirected graph in which there is exactly one path between any two vertices. In other word, the graph is both acyclic and connected. ...
alephalpha's user avatar
  • 48.7k
32 votes
14 answers
5k views

Have you heard of tralindromes?

I haven't. :P So I decided to define one: A tralindrome is a string which contains three equal-length sections X, Y, Z such that all characters in the string are included in at least one of the three ...
Bubbler's user avatar
  • 77.5k
11 votes
3 answers
383 views

Unique rainbow programs

Given a list of positive integers as input you are to determine if there is a way to pair up the elements such that: All but one element is in a pair No element is in more than one pair Every pair is ...
Wheat Wizard's user avatar
  • 99k
8 votes
7 answers
732 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 ...
AnttiP's user avatar
  • 7,898
23 votes
26 answers
1k 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 ...
thejonymyster's user avatar
9 votes
5 answers
995 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 &...
emanresu A's user avatar
  • 39.2k
13 votes
1 answer
205 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 ...
Wheat Wizard's user avatar
  • 99k
19 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 ...
Wheat Wizard's user avatar
  • 99k
12 votes
4 answers
283 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 ...
cjquines's user avatar
  • 1,231
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: ...
emanresu A's user avatar
  • 39.2k
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 ...
Wheat Wizard's user avatar
  • 99k
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 ...
Wheat Wizard's user avatar
  • 99k
24 votes
25 answers
11k 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 ...
Number Basher's 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 ...
Qaziquza's user avatar
  • 1,623
7 votes
1 answer
239 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 ...
Wheat Wizard's user avatar
  • 99k
13 votes
8 answers
933 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 ...
Wheat Wizard's user avatar
  • 99k
19 votes
27 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: ...
Nilster's user avatar
  • 1,487
13 votes
8 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 <...
pajonk's user avatar
  • 17.2k
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 ...
Sisyphus's user avatar
  • 14.8k
19 votes
10 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\$ ...
alephalpha's user avatar
  • 48.7k
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. ...
dingledooper's user avatar
  • 22.7k
8 votes
5 answers
774 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 ...
Ginger's user avatar
  • 5,700
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 ...
alephalpha's user avatar
  • 48.7k
14 votes
5 answers
743 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 ...
KeizerHarm's user avatar
  • 1,373
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: ...
AnttiP's user avatar
  • 7,898

1
2
3 4 5
16