Questions tagged [decision-problem]
For challenges which involve deciding whether or not the input meets certain criteria, and outputting some data, representing that decision.
601
questions
15
votes
4answers
339 views
Validate Blokus Board
Blokus is a board game in which players take turns placing pieces on a \$ n \times n \$ square grid. In this version of the game, there will be just one person playing. The person is given \$ 21 \$ ...
10
votes
13answers
1k views
Is this a half-sort?
The problem over here introduces an new type of strings: if you split the string into equal halfs and swap the pairs, it produces the same output as sorting the string. We call that a half-sort.
...
25
votes
11answers
3k views
Make true and false global!
We all know true and false, but what do speakers around the globe say?
...
22
votes
17answers
1k views
Bubbler numbers
Background
My user ID is 78410, or \$1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0_2\$. One interesting property of this number is that, in binary,
it doesn't have three consecutive identical digits, and yet
it ...
11
votes
10answers
2k views
Cheat activated
Background
The game Grand Theft Auto: San Andreas went down in history also thanks to its wide selection of cheats. They're almost 90 and anyone who has ever touched this game, no doubt has tried ...
19
votes
53answers
3k views
Check if an array (or equivalent) has the same number of odd and even numbers - Code Golf Edition!
Inspired by this code review question, I am curious to see what happens if we turn that into a code-golf challenge!
The description is easy, the input is an array or any similar data structure with ...
6
votes
3answers
250 views
Can I trade today?
Back in 2018, there has been introduced new law in Poland to ban trading on sundays,
but certain exceptions have been made (listed below). The task today is to determine,
can one trade on the sunday ...
9
votes
5answers
480 views
Is this a cube?
This challenge is a riff on Dion's challenge "Is this a rectangle?". The goal of this challenge is to write a program to decide whether or not some collection of tuples of integers represents a ...
8
votes
1answer
471 views
Test a polyomino against Conway criterion
Background
Conway criterion is a method to test if a given polygon can tile (i.e. cover without overlapping) an infinite plane. It states that a polygon can tile the plane if the following conditions ...
20
votes
18answers
5k views
Can I Type This With My Left Hand?
Inspiration
The longest words that can be typed with only the left hand on a standard QWERTY keyboard are "sweaterdresses", "tesseradecades", and "aftercataracts" (Source: Wikipedia).
Challenge
...
6
votes
3answers
546 views
Classify State's Senators
United States senators are sorted into three classes, based on what year their six-year term starts. Since each state has two senators, each state has a senator in two of the three classes.
Given a ...
11
votes
2answers
205 views
Verify a solution for Conway Immobilizer
Background
Conway immobilizer problem is a puzzle that reads like the following:
Three positions, "left," "middle," and "right," are marked on a table.
Three cards, an ace, a king, and a queen, ...
10
votes
4answers
363 views
Holey Knight's Tour
Given a rectangular board of cells with some number of holes in it, determine whether it is possible to complete a "holey knight's tour" (That is, a path that visits every non-hole cell exactly once ...
16
votes
12answers
2k views
Is the input Bl lu ur rr ry?
This is based off this challenge.
Given an input string, check whether the string is blurry.
What's a blurry string?
A blurry string is a string that's contained in the set of all blurrified pure-...
11
votes
6answers
419 views
Reachability measure in Conway's Soldiers
Background
Conway's Soldiers is a version of peg solitaire played on an infinite checkerboard. The board is initially full of pegs below an infinite horizontal line, and empty above it. Following the ...
24
votes
20answers
2k views
Is this a winning *Frustration* configuration?
Frustration is a solitaire card game which is played by calling out the sequence:
“Ace”, “Two”, “Three”, ... , "Nine", "Ten", “Jack”, “Queen”, “King”, “Ace”, “Two”, etc.
With each call, you ...
11
votes
2answers
521 views
Are these two DFAs equivalent?
Two Deterministic Finite Automata or DFAs can be checked to see if they accept same set of strings in polynomial time. See section 3.3 of this for a long list of methods and this SO question/answer ...
27
votes
15answers
3k views
The ultimate inequality challenge
Task
Given two positive integers a, b and a Unicode mathematical inequality symbol c, ...
10
votes
38answers
2k views
Is it a brainfuck instruction?
A very simple challenge today. Output a truthy value whether the ASCII character (or it's code) supplied is a brainfuck instruction (one of +-,.<>[]), and a ...
17
votes
11answers
2k views
Is this a rectangle?
The challenge:
Given four coordinates, each in x y form, your job is to find out whether or not the given coordinates form a rectangle, and output a truthy/falsey.
Rules:
For the sake of simplicity,...
32
votes
21answers
3k views
Check membership of an infinite list
As input you will receive
An integer \$a\$
A list of integers that is infinite and strictly-monotonic1.
Your program should check in finite time if \$a\$ appears the list.
You should output one of ...
9
votes
12answers
367 views
Does base n have any Rotate-Left-Double numbers?
Task
A Rotate-Left-Double number in base \$n\$ is a number \$m\$, when its base-\$n\$ digits are rotated left once, equals \$2m\$. The base-\$n\$ representation of \$m\$ cannot have leading zeros.
...
24
votes
13answers
5k views
Is this a legal date? - April Fools' edition
Task
A date can be compactly represented in a 6-character string in the format ddmmyy where the first two characters (dd) ...
22
votes
19answers
4k views
Even a clock that isn't working gets the time right two or three times a day
Context
When I was a little kid, I watched a Disney movie where Goofy told his son "Boy, even a broken clock is right two or three times a day." (see this youtube clip, courtesy of @Arnauld).
...
19
votes
13answers
1k views
Appearing a unique number of times
Your task is to write a program or function that takes as input a list of positive integers and determines if there are any two integers in the list, that both appear the same number of times.
For ...
5
votes
5answers
461 views
Special Character Coding Challenge - Check string for validity (Lots of rules) [closed]
There are 5 different "special characters": % & # $ !
These special characters are in a string with numbers. Like so: "5 ! 60%2$5.3" (valid). You must determine the validity of the string and ...
24
votes
10answers
1k views
Embedding Sets of Sets
Setup: For two sets \$A,B\$, we say \$A \subseteq B\$ if every element in \$A\$ is also in \$B\$.
Another way of saying this, is that we can order the elements of \$A,B\$ into two lists \$L_A,L_B\$, ...
18
votes
19answers
2k views
Is this a circular step sequence?
Background
We define a circular step sequence of order \$n\$ as follows:
$$
a_1, a_2, \dots, a_n = \text{Permutation of } 1 \dots n \\
b_i = \min ( |a_{i+1} - a_i|, n-|a_{i+1} - a_i| ), 1 \le i < ...
29
votes
21answers
5k views
Egg, sausage, bacon and spam (lovely spam!)
You are given four integers: \$e,s,b\in\{0,1\}\$ and \$S\in \{0,1,2,4\}\$, where \$e,s,b,S\$ stand for egg, sausage, bacon and spam respectively.
Your task is to figure out whether the corresponding ...
18
votes
27answers
3k views
Drawing one-liner
CodeDrawing one-liner
Teaser
Behold this formidable drawing:
Can you draw this in a single stroke? Give it a try.
Can you do this one, now:
Give it a try.
How it works
These "make this drawing ...
21
votes
1answer
738 views
Are They Similar Polygons?
Task
Given the x,y coordinates (coordinates are guaranteed to be integers) of the vertices of two simple polygons in clockwise or anti-clockwise order. Output a Truthy value if both the polygons are ...
24
votes
7answers
3k views
10-pin bowling split spare
Bowling
Bowling is a game where, essentially, each player gets 10 turns to:
Take 2 attempts at knocking down 10 pins arranged in a triangle.
between turns the pins are reset
from the 1st to the 2nd ...
22
votes
26answers
3k views
Can I join the music box?
The magic music box (MMB)
This explains the motivation for the challenge, feel free to ignore.
The magic music box is a word game played by a group of people, where one is the owner of the magic ...
44
votes
11answers
4k views
Simple Circular Words
A "simple circular" word is a word whose chords do not intersect. The chords of a word may be seen by laying out the alphabet in a circle, and then connecting the word's consecutive letters.
...
16
votes
8answers
1k views
Is this quadrilateral tangential?
Related: Is this quadrilateral cyclic?
Background
A tangential quadrilateral is a quadrilateral which has an incircle:
Examples include any square, rhombus, or a kite-like shape. Rectangles or ...
10
votes
11answers
414 views
Integer Keys and Duplicates
Given a non-empty list/vector of positive integers, write a function to check the following conditions in as few bytes as possible.
Take the first integer (the key, or k1) and check that the next k1 ...
23
votes
1answer
514 views
Compare Dowker Knotation
Dowker notation is a common way of representing mathematical knots.
Dowker notation can be derived from a knot diagram in the following way (based on the description from the wikipedium):
We will ...
22
votes
13answers
2k views
Check if simple regex matches string
A simple regex is either:
_ (which matches the empty string)
Any lowercase letter a to z (...
10
votes
2answers
588 views
Play Big 2 by yourself, as fast as you can
Introduction
Big 2 is a card game popular in East Asia and South East Asia, in which 4 players are dealt 13 cards each (ie, an equal division of a standard deck without jokers). The goal is to empty ...
16
votes
3answers
301 views
Is this board Latin-style?
Inspired by Flow Fit: Sudoku, a brand-new mobile puzzle game (as of Nov 2019).
Background
A Latin square is a square grid of side length \$ n \$ filled with \$ n \$ different symbols, where each row ...
23
votes
5answers
3k views
Is this platform game level winnable?
Given a level from a simple platform game, your task is to make a program or function to determine if a level is winnable. Platform game levels are 4 characters tall and any number of characters wide. ...
20
votes
4answers
1k views
Can Alice win the game?
Can Alice win the game?
The game's rules are as follows. First, a finite non empty set of positive integers \$X\$ is defined. Then, Alice and Bob take turns choosing positive integers, with Alice ...
16
votes
2answers
457 views
Can this Scottish village have a wedding?
This is the exact same question I asked earlier, but without the annoying Cyrillic factor which many found superfluous. I hope this is a better puzzle!
The quaint hamlet of North Codetown in the ...
26
votes
2answers
674 views
Can this village have a wedding?
The quaint hamlet of Кодгольф in the Russian far east has a problem: their population is low (below 66), and no new people have arrived for years. Moreover, after centuries of near-isolation, just ...
23
votes
47answers
6k views
Am I being run backwards?
Your task is to write a program, function, or snippet that will output one value if run forward, and another if run backward. The program must run without errors.
The output can be any two distinct ...
10
votes
8answers
456 views
1D Shikaku Validation
Shikaku is a 2D puzzle. The basic rundown of it is that a rectangular grid has some numbers in it, and you want to partition the grid into rectangular components such that each component contains ...
16
votes
13answers
1k views
Is it rectilinear?
Today's challenge:
Given an ordered list of at least 3 unique integer 2D points forming a polygon, determine if the resulting polygon is Rectilinear.
A polygon is rectilinear if every interior ...
21
votes
16answers
4k views
Check the validity of a 10-digit telephone number
Your task is to write a program or function that checks if a string is a valid phone number.
Given a string (or list of characters/codepoints) input, you will output a truthy value if the input is a ...
10
votes
8answers
558 views
Is this a valid input for this hardware?
The (slightly harder, but still easy) sequel of Generate input for this hardware.
Background
I have a hardware that has a 32-bit input register. The register has the following characteristics:
The ...
7
votes
1answer
478 views
Follow the Path, but is it valid?
Follow the Path
I got directions to my friend's house, but it looks like his map might have some mistakes. He's expecting me soon, so I need some short code to figure out if I can get there.
The ...
