Questions tagged [combinatorics]
For challenges involving combinatorics.
268
questions
16
votes
30answers
604 views
(RGS 2/5) How many strings can you count within these character classes?
Task
Given a string composed of ASCII printable characters, return how many strings could fit the given pattern with character literals and regex-like ranges.
Pattern string
The pattern string ...
14
votes
1answer
285 views
+250
Impress Donald Knuth by counting polyominoes on the hyperbolic plane
This challenge is inspired by a talk about Schläfli symbols, etc that I gave in a Geometry seminar. While I was putting together this challenge, I saw that Donald Knuth himself was interested in (some ...
14
votes
12answers
245 views
Combinations of stepwise increasing integers
Working on something in probability theory, I stumbled across another combinatorical exercise. These are always fun to solve, searching for intelligent approaches. Of course, one can use brute force ...
3
votes
1answer
220 views
Estimate the mean minimum Hamming distance
Task
Inputs \$b \leq 100\$ and \$n \geq 2\$. Consider \$n\$ binary strings, each of length \$b\$ sampled uniformly and independently. We would like to compute the expected minimum Hamming distance ...
21
votes
17answers
2k views
Concentric rings on a snub square tiling
This challenge takes place on the snub square tiling.
Start by choosing any triangle, and color it \$c_1\$.
Next, find all tiles which touch this triangle at any vertex, and color them \$c_2\$. Next,...
14
votes
14answers
724 views
Computing a specific coefficient in a product of polynomials
Generator functions
This gives the context for why this challenge came to life. Feel free to ignore.
Generator functions are a nice way of encoding the solution to a problem of combinatorics. You ...
13
votes
18answers
2k views
Given a list of strings, find all elements which are still in the list when any character is deleted
Write a program using the fewest bytes of source code which given a list of strings finds all elements which are still in the list when any character is deleted.
For example, given a list of all ...
21
votes
9answers
1k views
Counts Of Orderings Containing At Most K Of The Kth Class
This challenge is about the number of orderings which contain at most \$n\$ classes and at most \$k\$ of the \$k^{\text{th}}\$ class.
One way to represent such an ordering is as a sequence of ...
20
votes
19answers
2k views
Super permutations
Super permutations
Input: A string
The program should loop through all lengths of the input (decrementing one each time), generate all combinations with replacement of the string, then make ...
7
votes
1answer
499 views
Average number of strings with Levenshtein distance up to 4
This is a version of this question which should not have such a straightforward solution and so should be more of an interesting coding challenge. It seems, for example, very likely there is no easy ...
2
votes
0answers
52 views
Compositional inverse of a power series [duplicate]
If \$f(x) = x + \sum_{i>1} a_ix^i\$ and \$g(x)=x+\sum_{i>1}b_ix^i\$ then there is a composite power series \$f(g(x))\$ also of this form. Given a power series \$f\$ the goal is to find a ...
19
votes
21answers
5k views
Largest monetary amount impossible to make with two types of coin
Suppose we have two different types of coin which are worth relatively prime positive integer amounts. In this case, it is possible to make change for all but finitely many quantities. Your job is to ...
13
votes
7answers
503 views
Make a random drum loop
Do randomly generated drum loops sound good?
A drum loop is a \$5\times 32\$ matrix \$A\$ of \$1\$s and \$0\$s such that
\$A_{1,1}=A_{1,17}=A_{2,9}=A_{2,25}=1\$,
for each \$i\$, the \$i\$th row has ...
11
votes
4answers
2k views
Can you calculate the average Levenshtein distance exactly?
The Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions to convert one string into the other one.
The challenge is to compute ...
6
votes
1answer
569 views
Average number of strings with Levenshtein distance up to 3
The Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions to convert one string into the other one. Given a binary string \$S\$ of ...
17
votes
15answers
3k views
Stack Exchange Answerer
Oof! You've been coding the whole day and you even had no time for Stack Exchange!
Now, you just want to rest and answer some questions. You have T minutes of free time. You enter the site and see N ...
14
votes
1answer
487 views
Circular robot instructions
This challenge is based on Project Euler problem 208. Also related to my Math Stack Exchange question, Non-self-intersecting "Robot Walks".
You have a robot that moves in arcs which are \$1/n\$ of a ...
14
votes
8answers
539 views
Decorate Pascal's Triangle
Although what is a Pascal's triangle is well-known and we already can generate it, the task is now different:
Output \$n\$ first lines of the Pascal's triangle as colored bricks.
Color number is ...
23
votes
15answers
3k views
Triangular domino tiling of an almost regular hexagon
Background
An almost regular hexagon is a hexagon where
all of its internal angles are 120 degrees, and
pairs of the opposite sides are parallel and have equal lengths (i.e. a zonogon).
The ...
16
votes
1answer
371 views
Counting symmetric grid chains
Notation and definitions
Let \$[n] = \{1, 2, ..., n\}\$ denote the set of the first \$n\$ positive integers.
A polygonal chain is a collection of connected line segments.
The corner set of a ...
15
votes
6answers
453 views
Roman Numeral Counting
Roman numerals can be (mostly) written in a one column format, because each letter intersects the top and the bottom of the line. For example: I, or 1 intersects ...
7
votes
3answers
210 views
Multigraphs with a given degree sequence
This challenge will give you an input of a degree sequence in the form of a partition of an even number. Your goal will be to write a program that will output the number of loop-free labeled ...
17
votes
2answers
605 views
Number of distinct tilings of an n X n square with free n-polyominoes
The newest "nice" OEIS sequence, A328020, was just published a few minutes ago.
Number of distinct tilings of an n X n square with free n-polyominoes.
This sequence counts tilings up to symmetries ...
17
votes
14answers
1k views
Permutations in Disguise
Given a \$n\$-dimensional vector \$v\$ with real entries, find a closest permutation \$p\$ of \$(1,2,...,n)\$ with respect to the \$l_1\$-distance.
Details
If it is more convenient, you can use ...
21
votes
10answers
2k views
Count the number of shortest paths to n
This code challenge will have you compute the number of ways to reach \$n\$ starting from \$2\$ using maps of the form \$x \mapsto x + x^j\$ (with \$j\$ a non-negative integer), and doing so in the ...
32
votes
23answers
4k views
Brute-force the switchboard
The other day, our team went to an escape room. One of the puzzles involved a board of six mechanical switches where you had to find the correct combination of on and off in order to unlock a box, ...
8
votes
1answer
200 views
Compute my Sacred Geometry [closed]
In the tabletop RPG named Pathfinder, there is a feat that characters can take called Sacred Geometry, which allows a character who has it to buff their spells in exchange for doing some math: to use ...
-1
votes
3answers
231 views
Find all a, b, c, d, e, such that a + b + c + d + e = 1000 with no more than 3 loops [closed]
The rule is:
a, b, c, d, e is an integer from 0 to 1000, no relation between ...
12
votes
2answers
604 views
Counting generalized polyominoes
This challenge will have you count pseudo-polyforms on the snub square tiling.
I think that this sequence does not yet exist on the OEIS, so this challenge exists to compute as many terms as possible ...
3
votes
1answer
216 views
Multiplication in the Steenrod Algebra
Here's yet another Steenrod algebra question. Summary of the algorithm: I have a procedure that replaces a list of positive integers with a list of lists of positive integers. You need to repeatedly ...
16
votes
11answers
1k views
Generate basis elements of the Steenrod algebra
The Steenrod algebra is an important algebra that comes up in algebraic topology. The Steenrod algebra is generated by operators called "Steenrod squares," one exists for each positive integer i. ...
1
vote
0answers
88 views
Finding row wise sum of transpose of hv-convex binary matrix [closed]
I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).
...
35
votes
21answers
6k views
Amount of permutations on an NxNxN Rubik's Cube
Introduction:
A 3x3x3 Rubik's Cube has \$43,252,003,274,489,856,000\$ possible permutations, which is approximately 43 quintillion. You may have heard about this number before, but how is it actually ...
13
votes
3answers
381 views
Counting the number of restricted forests on the Möbius ladder of length n
OEIS sequence A020872 counts the number of restricted forests on the Möbius ladder Mn.
The Challenge
The challenge is to write a program that takes an integer as an input ...
20
votes
8answers
845 views
Cycles on the torus
Challenge
This challenge will have you write a program that takes in two integers n and m and outputs the number non-...
6
votes
2answers
305 views
Buy the most appropriate items
A store is having a big sale.
If your price reaches $199 or more, you can reduce it by $100.
You can buy each product only once.
Here's an example list of products: (in order to simplify, the names of ...
6
votes
2answers
717 views
Check if all vowels exist in pairs of strings [closed]
Your program should find the number of string pairs (pairs of 2) that contain all vowels (a e i o u), when given an integer N and ...
13
votes
6answers
330 views
Unique Brick Tilings Within A Rectangle
I was browsing Stackoverflow and saw this question about tiling an MxN rectangle, and I thought it would be great for golfing. Here is the task.
Given the dimension M and N, write a program that ...
6
votes
5answers
324 views
Generate the k-ary necklaces of length n
The set of necklaces is the set of strings, where two strings are considered to be the same necklace if you can rotate one into the other. Your program will take nonnegative integers ...
17
votes
1answer
316 views
Partition a square grid into parts of equal area
This challenge is based on the following puzzle: You are given an n by n grid with n cells ...
16
votes
4answers
737 views
Number of \$n\$-carbon alkanes
Given a positive number \$n\$, find the number of alkanes with \$n\$ carbon atoms, ignoring stereoisomers; or equivalently, the number of unlabeled trees with \$n\$ nodes, such that every node has ...
18
votes
9answers
2k views
Partitioning the grid into triangles
Goal
The goal of this challenge is to produce a function of n which computes the number of ways to partition the n X 1 grid ...
10
votes
3answers
461 views
Arbitrary Randomness (Speed edition)
Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
25
votes
24answers
3k views
Arbitrary Randomness
Randomness is fun. Challenges with no point are fun.
Write a function that, given integer input n, will output a set (unordered, unique) of exactly ...
5
votes
2answers
313 views
Find arrays with distinct subarray sums
Consider an array A of length n. The array contains only integers in the range 1 to ...
9
votes
1answer
835 views
Count arrays that are really unique
This is a follow up to Count arrays that make unique sets . The significant difference is the definition of uniqueness.
Consider an array A of length ...
0
votes
5answers
492 views
Fastest algorithm to output array containing all integers in range excluding duplicate digits
Input is a single integer in ascending digit order.
The only valid inputs are:
12
123
1234
...
6
votes
4answers
157 views
Seeking Substantial Subcollections
(thanks to @JonathanFrech for the title)
Challenge
Write a program or function that, given a collection of positive integers \$S\$ and a positive integer \$n\$, finds as many non-overlapping ...
11
votes
3answers
485 views
Count arrays that make unique sets
This question has a similar set up to Find an array that fits a set of sums although is quite different in its goals.
Consider an array A of length ...
9
votes
12answers
1k views
Different combinations possible
Problem
Given a value n, imagine a mountain landscape inscribed in a reference (0, 0) to (2n, 0).
There musn't be white spaces between slopes and also the mountain musn't descend below the x axis.
...
