Questions tagged [combinatorics]

For challenges involving combinatorics.

Filter by
Sorted by
Tagged with
14 votes
1 answer
618 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/...
user avatar
  • 8,117
15 votes
8 answers
624 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 ...
user avatar
24 votes
16 answers
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 ...
user avatar
  • 64.8k
16 votes
1 answer
407 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 ...
user avatar
  • 8,117
16 votes
6 answers
766 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 ...
user avatar
  • 3,583
8 votes
3 answers
251 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 ...
user avatar
  • 8,117
17 votes
2 answers
866 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 ...
user avatar
  • 8,117
18 votes
14 answers
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 ...
user avatar
  • 43.1k
23 votes
10 answers
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 ...
user avatar
  • 8,117
33 votes
23 answers
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, ...
user avatar
11 votes
1 answer
249 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 ...
user avatar
0 votes
3 answers
241 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 ...
user avatar
  • 1,217
14 votes
2 answers
773 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 ...
user avatar
  • 8,117
4 votes
1 answer
230 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 ...
user avatar
  • 2,085
17 votes
11 answers
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. ...
user avatar
  • 2,085
2 votes
0 answers
95 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). ...
user avatar
35 votes
21 answers
8k 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 ...
user avatar
13 votes
3 answers
402 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 ...
user avatar
  • 8,117
20 votes
8 answers
911 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-...
user avatar
  • 8,117
6 votes
2 answers
332 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 ...
user avatar
  • 173
6 votes
2 answers
874 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 ...
user avatar
  • 173
14 votes
6 answers
361 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 ...
user avatar
  • 721
6 votes
5 answers
391 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 ...
user avatar
  • 7,079
21 votes
2 answers
480 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 ...
user avatar
  • 8,117
16 votes
4 answers
827 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 ...
user avatar
  • 36.2k
20 votes
9 answers
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 into ...
user avatar
  • 8,117
11 votes
3 answers
522 views

Arbitrary Randomness (Speed edition)

Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
user avatar
  • 11.2k
26 votes
24 answers
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 ...
user avatar
  • 11.2k
5 votes
2 answers
624 views

Find arrays with distinct subarray sums

Consider an array A of length n. The array contains only integers in the range 1 to ...
user avatar
10 votes
1 answer
912 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 ...
user avatar
-1 votes
5 answers
561 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 ...
user avatar
6 votes
4 answers
163 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 ...
user avatar
11 votes
3 answers
537 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 ...
user avatar
9 votes
12 answers
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. ...
user avatar
17 votes
3 answers
457 views

Removing points from a triangular array without losing triangles

I have a combinatorics problem that I'd like to put on the OEIS—the problem is that I don't have enough terms. This code challenge is to help me compute more terms, and the winner will be the user ...
user avatar
  • 8,117
20 votes
11 answers
2k views

Socket - Plug compatibility

Traveling with electronics is always fun, especially when you need an adapter to charge them. Your challenge is to make planning a trip a little easier by checking if a given plug will be compatible ...
user avatar
  • 2,222
29 votes
4 answers
1k views

Smallest region of the plane that contains all free n-ominoes

On Math Stack Exchange, I asked a question about the smallest region that can contain all free n-ominos. I'd like to add this sequence to the On-Line Encyclopedia of Integer Sequences once I have ...
user avatar
  • 8,117
14 votes
12 answers
2k views

Fun with strings and numbers

Here's a programming puzzle for you: Given a list of pairs of strings and corresponding numbers, for example, [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]]...
user avatar
16 votes
27 answers
4k views

The Unique Padlock PIN List!

Introduction In a private chat, a friend of mine apparently recently stumbled across a security system which has the following two restrictions on its valid pins: Each digit must be unique (that is &...
user avatar
  • 3,263
11 votes
25 answers
3k views

Cartesian product of a list with itself n times

When given a a list of values and a positive integer n, your code should output the cartesian product of the list with itself n ...
user avatar
  • 437
24 votes
34 answers
2k views

Sign-Swapping Sums

Given a nonempty list of positive integers \$(x, y, z, \dots)\$, your job is to determine the number of unique values of \$\pm x \pm y \pm z \pm \dots\$ For example, consider the list \$(1, 2, 2)\$. ...
user avatar
9 votes
4 answers
567 views

Count the number of ways of putting balls into bins

In this task you are given an odd number of white balls and the same number of black balls. The task is to count all the ways of putting the balls into bins so that in each bin there is an odd number ...
user avatar
16 votes
1 answer
369 views

Permutations such that no k+2 points fall on any polynomial of degree k

Description Let a permutation of the integers {1, 2, ..., n} be called minimally interpolable if no set of k+2 points (together ...
user avatar
  • 8,117
3 votes
2 answers
79 views

Count stacking sequences [duplicate]

Given a list of stack heights, calculate the number of ways those heights could have been arrived at by stacking blocks one at a time. Shortest code wins. Test cases: ...
user avatar
  • 3,195
20 votes
2 answers
524 views

Counting polystrips

Polystrips are a subset of polyominoes conforming to the following rules: each piece consist of 1 or more cells no cell can have more than two neighbours the cells should not enclose a hole Free ...
user avatar
  • 20.6k
11 votes
19 answers
1k views

Sum of combinations with repetition

Write the shortest code you can solving the following problem: Input: An integer X with 2 <= X and X <= 100 Output: ...
user avatar
  • 219
18 votes
8 answers
938 views

Conjugate permutations

A permutation of size n is a reordering of the first n positive integers. (meaning each integer appears once and exactly once). Permutations can be treated like functions that change the order of a ...
user avatar
  • 89.4k
14 votes
8 answers
482 views

Deranged Rearrangements

Your task is to write a computer program such that when it is cut up into lines (split on the newline character) every arrangement of the lines will output a different number between 1 and n! (where n ...
user avatar
  • 89.4k
7 votes
6 answers
439 views

Alice's Tea Party

There are n places set around a circular table. Alice is sat on one of them. At each place, there's a cake. Alice eats her cake, but it doesn't taste very nice. Then the Mad Hatter comes in. He gives ...
user avatar
  • 2,723
24 votes
26 answers
3k views

Find The Rank Of A Word

Definition The rank of a word is defined as the position of the word when all the possible permutations (or arrangements) of its letters are arranged alphabetically, like in a dictionary, no matter if ...
user avatar
  • 4,920

1 2
3
4 5
8