# Questions tagged [decision-problem]

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

758 questions
Filter by
Sorted by
Tagged with
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 ...
• 99k
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, ...
• 8,562
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: ...
• 18.2k
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 ...
• 24.9k
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 ...
• 9,408
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 ...
• 39.9k
2k views

### Friend, or Foe?

Task Provide two programs/functions A and B (not necessarily in the same language) with the following properties: Either ...
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 ...
• 543
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 ...
• 99k
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 ...
• 2,511
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 ...
• 13.7k
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 ...
• 145
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 ...
• 10.8k
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 ...
• 16.7k
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 ...
• 18.8k
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 ...
• 16.7k
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 ...
• 12.7k
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 ...
• 14.7k
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 ...
• 99k
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 ...
• 4,547
3k views

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 ...
• 10.1k
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: ...
• 14.8k
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). ...
• 10.6k
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 ...
• 33.7k
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 ...
• 99k
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. ...
• 48.7k
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 ...
• 77.5k
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 ...
• 99k
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 ...
• 7,898
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 ...
• 3,337
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 &...
• 39.2k
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 ...
• 99k
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 ...
• 99k
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 ...
• 1,231
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: ...
• 39.2k
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 ...
• 99k
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 ...
• 99k
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 ...
• 1,548
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,623
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 ...
• 99k
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 ...
• 99k
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: ...
• 1,487
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 <...
• 17.2k
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 ...
• 14.8k
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$ ...
• 48.7k
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. ...
• 22.7k
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 ...
• 5,700
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 ...
• 48.7k
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 ...
• 1,373