Questions tagged [decision-problem]
For challenges which involve deciding whether or not the input meets certain criteria, and outputting some data, representing that decision.
734
questions
6
votes
1
answer
200
views
Determine if a Spider Solitaire game is stale
Let's introduce a simplified variant of the well known Spider Solitaire.
From Wikipedia:
The main purpose of the game is to remove all cards from the table, assembling them in the tableau before ...
- 12.2k
9
votes
8
answers
1k
views
Is it a valid hidden word?
The Universal Crossword has a set of guidelines for crossword puzzle submissions.
In this challenge we are going to be concerned with their rules for hidden word themes. A hidden word clue consists ...
- 96.5k
26
votes
9
answers
3k
views
Is it a Valid Crossword Grid?
In crossword terminology, the grid is the region into which the crossword answers are inserted, consisting of white and black squares. The crossword answers, called entries, are inserted into ...
- 7,061
21
votes
8
answers
2k
views
Do you win a Numeric Mahjong?
Background
Numeric Mahjong is a hypothetical variation of Japanese Mahjong, played with nonnegative integers instead of Mahjong tiles. Given a list of nonnegative integers, it is a winning hand if it ...
- 73.8k
22
votes
19
answers
3k
views
Is it an Element?
𝖧ello all, I hope this finds you well.
There are 118 elements on the Periodic table at the moment, each one corresponds to the number of protons in an atom's nuclei.
Each element also has a 'symbol'. ...
- 3,833
17
votes
12
answers
949
views
Is it a canonical elementary CA rule number?
Background
Given an elementary cellular automaton rule number like, for example, 28 = 00011100…
We can swap \$\color{red}{\text{the 2nd bit with the 5th bit}}\$ ...
- 68.1k
6
votes
4
answers
506
views
Walk by walls in a room
Challenge
You just entered a room. Here's how it looks (you are the X):
|\ /|
| \/ |
| X |
| |
|----|
You challenge yourself to see if you can reach where you ...
- 683
16
votes
6
answers
3k
views
Is it a valid Go type?
Write the shortest program or function that will determine if an input is a valid Go type.
Spec
This challenge will use the following simplified subset of Go types. For more information, see the ...
- 8,538
21
votes
18
answers
2k
views
Is this set laminar?
A family of sets is called laminar if for any two sets \$A\$ and \$B\$ in the family one of the following is true:
\$ A \subseteq B \$
\$ A \supseteq B \$
\$ A \cap B = \emptyset \$
Or less ...
- 5,677
17
votes
25
answers
3k
views
Is this a powerful number?
A powerful number is a positive integer \$n\$ such that for every prime \$p\$ that divides \$n\$, \$p^2\$ also divides \$n\$. Or equivalently, \$n\$ is powerful if and only if it can be written in the ...
- 46.5k
14
votes
15
answers
1k
views
Two Parallel Linked Chains
Background
We define the two types of chain to be a string that contains only dashes, "-", or only underscores, "_". We link two chains using one equals sign, "=".
...
- 1,777
21
votes
32
answers
2k
views
Reversed Squares
Given an integer n, your task is to determine whether it is a perfect square that when reversed, is still a perfect square. You may assume n is always positive.
When numbers such as 100 (10x10) are ...
- 3,443
11
votes
9
answers
1k
views
Decide Contiguous Binary Tree
Objective
Given an unlabelled binary tree, decide whether it is contiguous in indices.
Indices
This challenge gives one-indexing on binary trees. The exact definition expresses all indices in binary ...
- 5,447
24
votes
16
answers
4k
views
Is it a plausible chess move?
Not a duplicate of the valid move challenge because that asks for specific pieces.
Backstory
The other night I was doing a little trolling with ChatGPT and chess. I was trying to get it to call me out ...
- 32.5k
15
votes
20
answers
2k
views
String Comparison
You are given two strings \$a\$ and \$b\$ consisting of characters from a to z in lowercase. Let \$n\$ be the length of \$a\$. Let \$m\$ be the length of \$b\$. Let \$a'\$ be the string \$a\$ repeated ...
- 1,178
9
votes
5
answers
744
views
On The Subject Of Simon Says
This challenge is from a game, Keep Talking And Nobody Explodes.
This is like one of those toys you played with as a kid where you have to match the
pattern that appears, except this one is a knockoff ...
- 5,447
26
votes
6
answers
1k
views
Detect sonar imposters
You are the sonar captain aboard an underwater submarine. The way sonar works is that every submarine sends out a ping at regular intervals. Each interval is a whole number of seconds. Each submarine ...
- 96.5k
13
votes
4
answers
1k
views
Is it a Frog List?
Challenge:
A Frog List is defined by certain rules:
Each frog within a Frog List has an unique positive digit [1-9] as id (any 0...
- 123k
29
votes
13
answers
3k
views
Is it a valid chemical?
Non-metals typically* have a fixed number of covalent bonds in every chemical they are part of. Given the number of bonds every element requires, output whether it's possible to construct a single ...
- 11.8k
29
votes
17
answers
3k
views
Is it traversable?
Imagine that a list of integers describes the heights of some two-dimensional terrain as seen from the side.
Stamina: [ 4 4 4 4 4 4 3 3 3 3 2 2 2 - ]
O
...
- 22.7k
4
votes
2
answers
196
views
Ragged list pattern matching, Part 2
This is a sequel to Ragged list pattern matching. In this challenge, the wildcard may match a sequence of items of any length instead of just a single item.
Given a pattern and a ragged list of ...
- 46.5k
16
votes
6
answers
1k
views
Detect round trips on a hyperbolic grid
You're driving a car in an infinite city whose blocks are pentagons arranged in the order-4 pentagonal tiling. At each step, you proceed to the next intersection and choose whether to continue left, ...
- 621
10
votes
9
answers
969
views
Language Word Checker
Develop a program to check if a given word is part of a language defined by the following rules:
The language has a set of rules.
The empty string is considered a valid word in the language.
Two ...
- 1,178
13
votes
7
answers
762
views
Guessing on straws
Dedicated to Martin Gardner, taken from his book
Background
In the old days, the Slavs had a divination method for finding out whether a girl would get married. The girl would clutch six straws in her ...
- 3,239
3
votes
1
answer
211
views
Triangularly embed a graph on a surface
This challenge arises from a claim made in a MathOverflow answer and a paper linked in that answer which seems to back up the claim:
Searching for triangular embeddings is much quicker than ...
- 3,707
11
votes
2
answers
229
views
Making one shape out of dissections of another
Introduction
One question that I have come across recently is the possibility of dissecting a staircase of height 8 into 3 pieces, and then re-arranging those 3 pieces into a 6 by 6 square.
Namely, is ...
- 12.7k
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 ...
- 96.5k
10
votes
7
answers
607
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, ...
- 5,212
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:
...
- 17.8k
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 ...
- 20.4k
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 ...
- 8,465
21
votes
21
answers
2k
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 ...
- 38k
18
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 ...
- 481
6
votes
2
answers
343
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 ...
- 533
17
votes
3
answers
399
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 ...
- 96.5k
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 ...
- 2,491
12
votes
0
answers
437
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 ...
- 12.7k
12
votes
3
answers
474
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
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 ...
- 10.6k
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 ...
- 16k
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 ...
- 18.6k
3
votes
2
answers
529
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 ...
- 16k
26
votes
15
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 ...
- 11.8k
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 ...
- 14.6k
21
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 ...
- 96.5k
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 ...
- 3,967
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 ...
- 9,726
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:
...
- 14.7k
21
votes
5
answers
642
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). ...
- 9,682
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 ...
- 32.5k