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
26 votes
3 answers
3k views

Help, I'm trapped in an infinite factory!

This challenge is loosely inspired by the Zachtronics game Infinifactory. You are given a top-down view of a rectangular grid of conveyors, represented by ...
35 votes
13 answers
4k views

The Will Rogers Phenomenon

The so-called Will Rogers phenomenon describes a way to tweak statistics by raising the average in two (multi)sets when one element is moved between the two sets. As a simple example, consider the two ...
21 votes
14 answers
2k views

Refined Partitions

Consider an array of integers: [1, 0, 9, 1, 3, 8] There are a lot of ways to partition this list into consecutive sublists. Here are three: ...
46 votes
76 answers
9k views

Is it a leap year?

This challenge is quite simple. You will take an input which will be a year from 1801 to 2400, and output if it is a leap year or not. Your input will have no newlines or trailing spaces: ...
user avatar
18 votes
2 answers
615 views

Finding the Deadlock

Finding the Deadlock When programming a multithreading application one must take good care to avoid deadlocking the various threads when accessing shared resources. A deadlock occurs when a thread ...
  • 1,461
72 votes
47 answers
5k views

Check if words are isomorphs

Two words are isomorphs if they have the same pattern of letter repetitions. For example, both ESTATE and DUELED have pattern <...
  • 140k
25 votes
6 answers
3k views

Valid snakes on a plane

Inspired by one of Vi Hart's videos (which are a treasure trove full of potential challenge ideas) A snake is made up of segments of same length and the connection between each segment can be ...
  • 2,881
13 votes
3 answers
10k views

Is that word Feminine or Masculine?

Write a program or function that takes in a single string containing only lowercase a-z, and prints or returns a truthy value if the word is the feminine version of the thing it represents and a falsy ...
18 votes
4 answers
707 views

Group Therapy: Identify Groups

Write a program, that determines whether the multiplication table of the given finite magma represents a group. A magma is a set with a binary operation that is closed, that means for all \$a,b\$ in \...
  • 43.3k
35 votes
4 answers
3k views

Infinite Labyrinths

Background You are the apprentice of a powerful wizard, and your master is currently developing a spell for creating an inter-dimensional labyrinth to trap his enemies in. He wants you to program his ...
  • 42.3k
25 votes
7 answers
1k views

A Basic Pyth-like Syntax Checker

Pyth is a golfing language based on Python. It uses prefix notation, with each command having a different arity (number of arguments it accepts). Your task is to write a syntax checker for a (non-...
  • 61.2k
10 votes
3 answers
334 views

Identifying Sequences for Cellular Automata

Background For the purposes of this challenge, an n-state cellular automaton is simply a binary function f that takes two ...
  • 42.3k
18 votes
10 answers
1k views

Evaluate a chain of inequalities

Write code to evaluate whether a chain of inequalities is true or false. An example input is the string 3<=4!=9>3==3 This is true because each of its ...
  • 140k
11 votes
4 answers
508 views

Prelude Syntax-Checker

Prelude is an esoteric programming language, which has very few, but unusual, restrictions on what constitutes a valid program. Any block of printable ASCII text ("block" meaning that lines of ...
43 votes
62 answers
9k views

Check whether letters of word are in alphabetical order

Write a function/program that accepts a string of lower/uppercase letters [A-Za-z] as input, that checks whether the occuring letters are unique and in alphabetical order (ignoring lower and uppercase)...
  • 43.3k
22 votes
10 answers
3k views

Can the maze be solved?

Task Print 0 if an n*m maze cannot be solved Print 1 if an n*m maze can be solved (in 1 or more ways) (so I'm not asking for ...
  • 553
12 votes
2 answers
950 views

Tic-Tac-Toe and Chess, with fewest [distinct] characters

In this form of the game Tic-Tac-Chec, the goal is to move chess pieces to get four-in-a-row. Your goal here is to figure out if a position has a winning move. Rules The rules are similar, but not ...
  • 10.8k
21 votes
3 answers
1k views

2D Collision Detection

This challenge is based on actual collision detection I had to write for a simple game recently. Write a program or function which, given two objects, returns a truthy or falsy value depending on ...
50 votes
6 answers
6k views

Your car only turns right!

Introduction You have the misfortune of being stuck in a runaway car on an obstacle course. All of the car's features are non-responsive, save for the steering system, which is damaged. It can ...
  • 1,175
29 votes
12 answers
3k views

Word Search Puzzle

Given a rectangular text as a word search puzzle and a search string, determine if the text contains the search string. The search string may appear: horizontally, vertically or diagonally forwards ...
39 votes
5 answers
2k views

Is this word on the boggle board?

Introduction After a day of drinking and watching the world cup, you sit down to play friendly game of boggle. Tempers rise as you are accused of wasting everyone's time with nonsense words that aren'...
155 votes
1 answer
7k views

"KNOT" or "NOT"?

Write a program that processes an ASCII art representation of a tangled string and decides whether or not it can be untangled into a simple loop. The tangle is represented using the characters ...
  • 19.7k
367 votes
1 answer
116k views

Regex that only matches itself

There are some pretty cool challenges out there involving regex (Self-matching regex, Regex validating regex) This may well be impossible, but is there a regex that will ONLY match itself? NOTE, ...
40 votes
84 answers
10k views

Determine if all decimal digits are unique

Deleted questions on Stack Overflow sometimes make for great golf material. Write a function that takes a nonnegative integer as input, and returns true if all the digits in the base 10 ...
  • 617
41 votes
9 answers
6k views

"Convenient palindrome" checker

If you've ever tried to write palindromic code before, you'd know how much brackets tend to get in your way. ()() is not a palindrome, even though it kinda looks ...
14 votes
21 answers
1k views

Determine if an integer is a palindrome in a given radix (base)

Write a program that reads from stdin two integers, each newline terminated, hereafter called "number" and "radix", and: Prints any fixed message you want if the number is a palindrome in that radix (...
  • 4,770
24 votes
22 answers
5k views

Create a sudoku solution CHECKER

Create a Sudoku solution CHECKER There are oodles of Sudoku SOLVERS here, but I want you to create a solution CHECKER as small as humanly possible (code-golf). A valid entry will be able to either ...
11 votes
13 answers
578 views

Fibonacci distribution validator

Related: Hello world!!! Fibonacci distribution Create a program that returns True if a given input meets the following specifications, and False otherwise: The count of numeric characters (0-9) in ...
  • 2,498
29 votes
69 answers
9k views

Check whether an integer is a power of 2 without using +,- operations [closed]

Write a program that checks if the integer is a power of 2. Sample input: 8 Sample output: Yes Sample input: ...
  • 1,049
20 votes
20 answers
3k views

Verify Brainfuck program

Yet another Brainfuck parsing problem, but this time... different. You are working in the Infinite Monkeys Incorporated, the company making Brainfuck programs, to solve various interesting problems ...
9 votes
2 answers
2k views

Check if the 15 puzzle is solvable

The fifteen puzzle is peculiar in that only half the possible states of arrangement are solvable. If you flip the 14 and 15 tiles, there is no way you can slide the blocks so that they are flipped ...
  • 34.1k
56 votes
76 answers
8k views

Test a number for narcissism

A Narcissistic Number is a number which is the sum of its own digits, each raised to the power of the number of digits. For example, take \$153\$ (3 digits): \$1^3 + 5^3 + 3^3 = 153\$ \$1634\$: \$1^...
  • 2,498
67 votes
43 answers
5k views

Write the shortest self-identifying program (a quine variant)

Write a program that will generate a "true" output iff the input matches the source code of the program, and which generates a "false" output iff the input does not match the source code of the ...
  • 28.7k
42 votes
46 answers
18k views

Shortest code to determine if a string is a palindrome

A palindrome is some string that is spelled the same way both backwards and forwards. For instance, 'Eva, can I stab bats in a cave?' is a palindrome (EVACANISTAB | BATSINACAVE) For this code golf, ...
11 votes
2 answers
951 views

Email validation

Write a function or program to validate an e-mail address against RFC 5321 (some grammar rules found in 5322) with the relaxation that you can ignore comments and folding whitespace (...
  • 42.9k
14 votes
12 answers
1k views

Transposed, primes, oh my!

The task is simple: your program reads an integer as an input, and prints whether it is a prime or not. You can print "yes/no", "true/false" or anything what unambiguously ...
  • 8,100
27 votes
66 answers
8k views

Is string X a subsequence of string Y?

Given strings X and Y, determine whether X is a subsequence of Y. The empty string is regarded as a subsequence of every string. (E.g., '' and ...
  • 3,042
6 votes
12 answers
1k views

"First time" test

What is the shortest C expression that is defined to evaluated to false the first time and true for every time after that: Reference implementation: ...
  • 269
18 votes
31 answers
2k views

Finding Not-Quite-Prime Numbers

Your challenge, should you chose to accept it, is to code-golf a function that returns true or false (or some similar meaningful representation of yes and no) if a number meets the following criteria: ...
  • 2,429
4 votes
14 answers
1k views

Write the shortest code to match a tail-repeating string where one character falls off the head in each repetition

In this code-golf, you will attempt to match a string that is tail-repeating with one character falling off the head on each iteration. The code needs to be able to accept a string, and return to the ...
11 votes
9 answers
3k views

Check if a string is a shuffle of twins

Explanation Two strings can be shuffled by interspersing their letters to form a new string, much like two piles of cards can be shuffled to form a single pile. For example, the strings ...
  • 7,692
8 votes
2 answers
2k views

Determining the winner of a Chess game

Challenge Being someone who plays far too much chess in his spare time, I thought I'd set a code golf challenge inspired by the game of chess (with a software flavour), for those interested. The ...
  • 197
16 votes
40 answers
2k views

Undulant numbers [duplicate]

An undulant number is a number where its digits alternate between up and down like the following number: 461902 or 708143, or even 1010101, but not 123, because 2 < 3. Write a program or function ...
  • 341
6 votes
21 answers
6k views

Check if number is a sum of consecutive numbers or not

Write a program that checks if a given positive integer can be represented as sum of two or more consecutive positive integers. Example: 43 can be represented as 21 + 22 10 = 1+2+3+4 but 4 cannot be ...
23 votes
28 answers
7k views

Find whether a number is happy or not?

A happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (...
  • 4,463
21 votes
4 answers
2k views

Determine if a polygon is convex

Write a program to determine if the input polygon is convex. The polygon is specified with one line containing N, the number of vertices, then N lines containing the x and y coordinates of each ...
21 votes
46 answers
2k views

Detect rotated strings

Read two strings from stdin. Output Yes if one string is a rotated version of the other. Otherwise output ...
  • 15k
91 votes
158 answers
13k views

Determine whether strings are anagrams

Challenge Given two strings, work out if they both have exactly the same characters in them. Example Input word, wrdo This returns true because they are the ...
  • 1,219
8 votes
8 answers
537 views

Is this figure connected?

You are given a list of (x,y) grid coordinates. Your function should decide whether the figure obtained by coloring in the squares of the grid with the given ...

1
10 11 12 13
14