Questions tagged [decision-problem]
For challenges which involve deciding whether or not the input meets certain criteria, and outputting some data, representing that decision.
678
questions
13
votes
2
answers
289
views
Determine if a dot(comma) program halts
Dotcomma is a simple esolang I made a while ago that only uses four operators: [.,]. In this challenge, you'll determine if a dotcomma program consisting only of <...
- 17.4k
26
votes
5
answers
2k
views
I before E, except after C
You may be aware of the famous old rhyme, "I before E, except after C". It is a rule taught to aid in the spelling of certain English words.
Quoting Wikipedia:
If one is not sure whether a ...
- 17.6k
20
votes
51
answers
2k
views
Are All the Items the Same?
Given a list of non-negative integers, return whether or not that list is all the same number.
Rules
Input and output can be taken/given in any reasonable and convenient format
Truthy/Falsey values ...
- 22.1k
18
votes
19
answers
3k
views
Did I die or not?
Given a permutation of the alphabet and an intended "word", determine if the word was guessed in a game of Hangman, where the permutation is the list of guesses.
For example, given ...
- 47.3k
10
votes
6
answers
380
views
Rejecting invalid IPv4 addresses
I want to avoid responding to illegal or spoofed addresses. One type that's easy to detect is an address that should not exist on a packet received by my router: a special-use address.
Challenge
Given ...
- 201
17
votes
19
answers
1k
views
Check B-powersmoothness
from Wikipedia, a number is called B-powersmooth if all prime powers \$p^v\$ that divide the number satisfy \$p^v \leq B\$. B-powersmoothness is important, for example, for Pollard's p-1 factorization ...
- 3,173
12
votes
15
answers
788
views
Check if B is composed of substrings of A of length n
Given two strings \$ A \$ and \$ B \$ and a positive integer \$ n \$, determine whether \$ B \$ is composed entirely of (possibly overlapping) strict substrings of \$ A \$ of a length of at least \$ ...
- 21.5k
23
votes
5
answers
1k
views
Can this pattern be made with dominoes?
Given a pattern of squares on a grid, determine if it is possible to create that pattern with non-overlapping dominoes. In case you are not familiar, a domino is a rectangular shape created by joining ...
- 9,791
25
votes
10
answers
1k
views
Unique half rainbows
If we take a positive integer \$n\$ and write out its factors. Someone can determine \$n\$ just from this list alone. In fact it is trivial to do this since the number is its own largest factor.
...
- 88.8k
13
votes
4
answers
1k
views
I ain't no Fortunate sum
The primorial \$p_n\#\$ is the product of the first \$n\$ primes. The sequence begins \$2, 6, 30, 210, 2310\$.
A Fortunate number, \$F_n\$, is the smallest integer \$m > 1\$ such that \$p_n\# + m\$ ...
- 47.3k
26
votes
11
answers
2k
views
Test if a Gray code is Beckett
Background
An \$n\$-bit Gray code is an ordering of \$2^n\$ binary sequences so that adjacent sequences always differ by exactly one bit.
A Beckett-Gray code is a special kind of Gray code. In ...
- 62.9k
20
votes
1
answer
396
views
Is this Game of Go configuration fully alive?
Background
This challenge is about the Game of Go. Here are some rules and terminology relevant to this challenge:
Game of Go is a two-player game, played over a square board of size 19x19.
One of ...
- 62.9k
24
votes
13
answers
5k
views
Is it a vampire number?
Repost and improvement of this challenge from 2011
A vampire number is a positive integer \$v\$ with an even number of digits that can be split into 2 smaller integers \$x, y\$ consisting of the ...
- 47.3k
12
votes
6
answers
799
views
Golf this Thumb-2 Constant!
One thing that is constantly frustrating when golfing ARM Thumb-2 code is generating constants.
Since Thumb only has 16-bit and 32-bit instructions, it is impossible to encode every immediate 32-bit ...
- 4,110
25
votes
14
answers
4k
views
Is this an L-shape?
Background
An L-shape is defined as a polyomino which can be made by extending two rectangular legs in orthogonal directions from a full square (called a pivot). The size of the square should be at ...
- 62.9k
32
votes
16
answers
6k
views
Is it a lobster number?
Introduction
A "lobster number", by my own designation, is a number that contains within itself all of its prime factors. The "lobster" description was inspired by the recent ...
- 429
11
votes
3
answers
401
views
A graph and its seven closures
Background
A little while ago, someone posted an interesting puzzle on Math.SE:
What is the smallest digraph (directed graph) G where the following eight graphs are all distinct:
G, the original ...
- 62.9k
14
votes
8
answers
2k
views
Is my triangle on the lattice?
Write a program or function which takes three positive integers \$a, b, c\$ and returns/outputs one value if there is, and a different value if there isn't, a triangle on the square lattice, whose ...
- 407
9
votes
3
answers
847
views
Validating a Battleship board
Do you know the game Battleship? Well, I want to play with my little brother, but before we can begin we need to set up our ships on the board. This is your input.
Now, we need to check that the ships ...
- 113
20
votes
19
answers
2k
views
Vandalizing Marquees
A marquee is a low-tech board that allows customizable letters. For example, here is a marquee:
SALE ON SNEAKERS
However, someone might come along and vandalize it ...
- 13.5k
9
votes
8
answers
507
views
Equality up to Swapping
inputs / outputs
your program/function/routine/... will be a predicate on two tuple sequences; call it relation ≡. for the purpose of simplicity we use natural ...
- 59
13
votes
2
answers
405
views
Can you make your way through the Ulam spiral?
You will be given a point (x,y) relative to the center of the Ulam spiral (the center being the point which represents one), and length ...
- 11.4k
29
votes
21
answers
3k
views
Can we spell a third number?
You are given two strings, each consisting of the English word for a number between 1 and 13:
...
- 168k
21
votes
23
answers
1k
views
Compatible strings
When studying numerology, you can say two words (strings consisting entirely of letters) are compatible if they produce the same number under the following operation (let's use the string ...
- 47.3k
21
votes
38
answers
4k
views
Is It A Rainbow Color?
Challenge:
The challenge is to determine whether or not a color, given it's name, is one of the colors in the rainbow.
When supplied with a color, your program should output a truthy value if it is a ...
- 1,067
28
votes
17
answers
3k
views
Which side should I serve on?
Introduction
In Tennis, the server alternates serving on the left side or the right side of the court every point, starting on the right. It is possible to figure out which side to serve on for that ...
- 1,343
18
votes
7
answers
841
views
What valence does this APL train have?
Context
In APL, trains are tacit sequences of monadic/dyadic functions that can be called with one or two arguments. We'll code something to check if a given train follows the correct structure we ...
- 13.8k
38
votes
17
answers
4k
views
Is it a digit haiku?
We can read 13576870234289 digit-by-digit in English, and it makes a haiku:
one three five seven
six eight seven zero two
three four two eight nine
We say it's a &...
- 66k
23
votes
17
answers
2k
views
A Portuguese sequence of integers
Context
Consider the following sequence of integers:
$$2, 10, 12, 16, 17, 18, 19, ...$$
Can you guess the next term? Well, it is \$200\$. What about the next? It is \$201\$... In case it hasn't become ...
- 13.8k
25
votes
12
answers
2k
views
Decide a C integer literal
Objective
Given an ASCII string, decide whether it is a valid C integer literal.
C integer literal
A C integer literal consists of:
One of:
0 followed by zero or ...
- 4,163
33
votes
9
answers
2k
views
Dice Paths on a Grid
You place a standard die at the origin of a 2D grid that stretches infinitely in every direction. You place the die such that the 1 is facing upwards, the 2 is facing in the negative y direction, and ...
- 11.8k
15
votes
16
answers
1k
views
Concatenations of powers and their squares
At time of writing, my reputation is \$16,256\$. As I noted in chat,
Oh cool my rep is the concatenation of two powers of 2: 16,256
Or even the concatenation of a power of 2 and its square, which is ...
- 47.3k
9
votes
21
answers
802
views
Word Length-Sum Multiples
A port of my other question: Double Prime Words
Consider a word/string of n alphanumeric characters with sum of the characters, s...
- 1,886
23
votes
16
answers
2k
views
Delicate primes
Inspired by Find the largest fragile prime.
By removing at least 1 digit from a positive integer, we can get a different non-negative integer. Note that this is different to the ...
- 47.3k
20
votes
14
answers
1k
views
sporeball numbers
Background
We've studied at least five different types of numbers based on the IDs of different users on this site. Why not study another?
My user ID is \$91030_{10}\$. Its binary representation is \$...
- 1,648
15
votes
15
answers
1k
views
Dovetail two blocks of bits
Check if two blocks of bits dovetail perfectly.
Specifications
A block of bits is a fixed sequence of 8 bits just like this for example : 11110101.
For simplicity we refer to ...
- 9,436
-5
votes
2
answers
392
views
Is my Processor 32 or 64 bit?
Not to be confused with Is my OS 32-bit or 64-bit.
This one is very simple, tell me whether or not my CPU supports 64-bit instructions. If my CPU supports 32-bit instructions, print '32', if my CPU ...
- 3,583
16
votes
21
answers
1k
views
Double Prime Words
Consider a word/string of length \$n\$, only including the letters A-Z, a-z. A word/string is a double prime word if and only if n is prime and the sum of the letters, s, is also prime, using their ...
- 1,886
31
votes
31
answers
5k
views
Is it almost-prime?
Sandbox
Definition: A positive integer n is almost-prime, if it can be written in the form n=p^k where ...
- 1,365
25
votes
10
answers
2k
views
Are they connected by a Brussels choice?
Background
Two numbers, \$a\$ and \$b\$, are said to be connected by a Brussels choice operation* if \$b\$ can be reached from \$a\$ by doubling or halving (if even) a substring (the substring must ...
- 6,449
27
votes
4
answers
2k
views
Never trust a mastermind
You probably know the game mastermind:
The player tries to guess a code of 4 slots, with 8 possible colors - no duplicates this time.
Let's call those colors A through H, so possible solutions could ...
- 763
14
votes
7
answers
1k
views
Can I exit the maze with this many bombs?
Inspired by this Puzzling challenge, and easier version of my previous challenge.
Challenge
A 2D rectangular grid is given, where each cell is either an empty space or a wall. You start at the top ...
- 62.9k
26
votes
24
answers
2k
views
Antisymmetry of a Matrix
A matrix is antisymmetric, or skew-symmetric, if its transpose equals its negative.
The transpose of a matrix can be obtained by reflecting its elements across the main diagonal. Examples of ...
- 1,989
17
votes
6
answers
547
views
Play a Game of Minigolf
Background
I feel that for a site named code-golf we have a shockingly little amount of golf being played. Let's fix that.
Challenge
Determine whether the hole of a minigolf course can be reached ...
- 1,131
22
votes
20
answers
2k
views
Verify a Superpermutation
A superpermutation on n symbols is a string which contains every permutation of n symbols in its body. For instance, 123121321 is a superpermutation on three ...
- 1,989
12
votes
4
answers
245
views
Is it a uniform polyhedron?
Objective
Given a vertex figure consisting of regular convex polygons, determine whether it represents a convex uniform polyhedron.
What is a uniform polyhedron?
A uniform polyhedron is a polyhedron ...
- 4,163
17
votes
18
answers
2k
views
JFor? More like XNor
As it turns out, Python allows for 1j for to be compressed to 1jfor. However, jfor sounds ...
- 16k
18
votes
12
answers
3k
views
Are These Scores Possible?
Background
In the sport of Table Tennis (aka Ping-Pong or Whiff Whaff), two opponents play a sequence of rounds, where each round consists of players hitting a ball back and forth until one player (...
- 16k
9
votes
2
answers
813
views
Tents and Trees feasibility
Sequel to Verify Tents and Trees solution.
Background
Tents and Trees (try here) is a puzzle played on a square (or rectangular) grid, where the objective is to place tents horizontally or vertically ...
- 62.9k
24
votes
20
answers
3k
views
Solve a 2xN Maze
Given a \$2\times N\$ maze, determine if you can get from the start top left corner to end bottom right corner using only up, down, left, and right moves.
Input
A \$2\times N\$ block (\$1 \le N \le ...
- 11k