# Tagged Questions

for challenges involving combinatorics.

88 views

### Generate ordered binary combinations without repetitions [closed]

Challenge Write the shortest program that receives two signed integers n and i and for each i between 1 and 2^n - 1 returns the next ordered permutation based on the binary representation of the ...
625 views

### The Coin Problem

Background The official currency of the imaginary nation of Golfenistan is the foo, and there are only three kinds of coins in circulation: 3 foos, 7 foos and 8 foos. One can see that it's not ...
249 views

### Count the trees

A tree is a connected, undirected graph with no cycles. Your task is to count how many distinct trees there are with a given number of vertices. Two trees are considered distinct if they are not ...
307 views

### Number of domino tilings

Write a program or function that given positive n and m calculates the number of valid distinct domino tilings you can fit in a n by m rectangle. This is sequence A099390 in the Online Encyclopedia of ...
134 views

### join lists by common elements [closed]

You have N lists A = [5, 6, 10, 15] B = [3, 0, 7, 4] C = [49, 59, 29] D = [19, 29, 39] E = [9, 15, 3, 10] You have to combine them such that: Two lists which have a common elements they should be ...
4k views

### Which Friends characters were really the best friends?

The six main cast members of the American sitcom Friends all agreed that they would be paid the same salary throughout the run of the series (after season 2, at least). But that doesn't mean that they ...
425 views

### Too many pawns on a chess board

Given an integer 2n, find the number of possible ways in which 2n^2 black pawns and 2n^2 white pawns can be arranged on a 2n by 2n chess board such that no pawn attack another. A black pawn can ...
171 views

### Calculate a Pedigree

A little genetics lesson When you only have access to someone's visible traits or phenotype, a pedigree of their family history is often used to figure out the actual genetic information or, genotype ...
932 views

### Print all colorings of a 3x3 grid

You have a 3x3 grid. Each cell can be colored black or white. Display all 512 of these colorings. Fewest bytes wins. You can display the grids in any formation as long as they are visually separated ...
1k views

### Calculate a probability exactly

This task is about writing code to compute a probability exactly. The output should be a precise probability written as a fraction in its most reduced form. That is it should never output 4/8 but ...
617 views

### Extending OEIS: Counting Diamond Tilings

I promise, this will be my last challenge about diamong tilings (for a while, anyway). On the bright side, this challenge doesn't have anything to do with ASCII art, and is not a code golf either, so ...
640 views

### Random ASCII Art of the Day #5: Diamond Tilings

Mash Up Time! This is instalment #5 of both my Random Golf of the Day and Optimizer's ASCII Art of the Day series. Your submission(s) in this challenge will count towards both leaderboards (which you ...
896 views

### Hook length product

A Young diagram is an arrangement of boxes in left-justified rows and top-justified columns. For each box, all the spaces above it and to its left are occupied. XXXXX XXX XXX X The hook length of a ...
492 views

### Supersonic domino tilings

Task Write a program that reads three integers m, n either from STDIN or as command-line arguments, prints all possible tilings of a rectangle of dimensions m × n by 2 × 1 and 1 × 2 dominos and ...
358 views

### Permutations of the Fifteen Puzzle

The Challenge Consider the following diagram of the Fifteen Puzzle in its solved state: _____________________ | | | | | | 1 | 2 | 3 | 4 | |____|____|____|____| | | | | | ...
234 views

### Number of ways to sum [1..n] with [n+1..2n] such that each sum is prime

Let n > 0. Let X = [1..n] and Y = [n+1 .. 2n]. Define a(n) as the number of permutations p of Y such that every element of X + p(Y) is prime. For example: n = 2 X = [1,2] Y = [3,4] p0(Y) = [3,4] ...
346 views

183 views

### Plus one sheep minus one sheep

Once upon a time long long ago...when there was no money or stocks yet, people were trading sheep. Even before (but close to) the invention of abacus, the great-grandfather of Warren Buffet decided it ...
312 views

### Count balanced binary strings matching any of a set of masks

A binary string is a string which contains only characters drawn from 01. A balanced binary string is a binary string which contains exactly as many 0​s as 1​s. You are given a positive ...
405 views

### Order 40 sticks

We have 40 sticks of same widths but different heights. How many arrangements are there possible to put them next to each other so that when we look from right we see 10 sticks and when we look from ...
293 views

### Maximum Concatenated Product

We are given a list of integers p1, ..., pk (not necessarily distinct) where each has a value between 1 and 9, inclusive. Using each of the p1, ..., pk exactly once, we can form concatenations of ...
415 views

### Twelve-coin problem

Background The twelve-coin problem is a classic balance puzzle commonly used in job interviews. The puzzle first appeared in 1945 and was posed to my father by my grandfather when he asked to marry ...
533 views

### Can you cast the spell?

In Magic: the Gathering, mages (known as "planeswalkers") battle each other by casting spells. Spells cost mana. Five colors of mana exist: White, Blue, Black, Red, and Green, represented as {W}, {U}, ...
631 views

### Matrix property X revisited (or the Joy of X)

This challenge is partly an algorithms challenge, partly an optimization challenge and partly simply a fastest code challenge. A T matrix is fully specified by its first row r and first column c. ...
174 views

### Number of unique outputs by substituting variables

Given a set of formulas like this: bacb bcab cbba abbc Give an algorithm that finds the number of unique results you can get when each variable is substituted for either "0" or "1" in every ...
545 views

### Count the number of Hankelable matrices

Background A binary Hankel matrix is a matrix with constant skew-diagonals (positive sloping diagonals) containing only 0s and 1s. E.g. a 5x5 binary Hankel matrix looks like a b c d e b c d e f c d ...
3k views

### Vampire Compatibility

A little known fact about vampires is that they must drink the blood of victim that has a compatible donor blood type. The compatibility matrix for vampires is the same as the regular red blood cell ...
5k views

### The Urinal Protocol

Background The so-called "Urinal Protocol", describing the order in which individual urinals are picked in a men's bathroom, has been discussed in multiple places. One version is given in this xkcd ...
528 views

### Sorted Lexical Partition of a Number

The challenge is really simple: given a number, you split its digits into an array of smaller numbers such that the resulting numbers are non-decreasing. The catch is that you have to split it such ...
354 views

### Latin Word Judgment

Because I can't concentrate on any task for more than about 5 seconds, I often find myself breaking up words into a sub-strings, each of which is a different length and doesn't contain any repeated ...
166 views

### Count Maximal Fence Arrangements

Background I want to build a fence. For that, I have collected a bunch of poles, and stuck them to the ground. I have also collected lots of boards that I'll nail to the poles to make the actual ...
604 views

### Generate the set of prepend-append permutations in lexicographically sorted order

Define a prepend-append sequence of length n to be a permutation of the numbers 1, 2, ..., n that can be generated by the following procedure: Start with the number 1. For each number from 2 to n, ...
1k views

### Random Golf of the Day #3: Integer Partitions

About the Series First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You ...
198 views

### count number of valid, unique sequences for moving on a 1xn board [closed]

There's a board with n squares in a horizontal row. You start in the leftmost square, and roll a 3-faced dice. 3 possible outcomes for a single roll of the die: Left: you move 1 step to the left, ...
236 views

### Generate a Davenport-Schinzel Sequence

Background A Davenport-Schinzel sequence has two positive integer parameters d and n. We will denote the set of all Davenport-Schinzel sequences for given parameters by DS(d,n). Consider all ...
335 views

### Total number of topological sorts

For a given DAG (directed acyclic graph), each of its topological sorts is a permutation of all vertices, where for every edges (u,v) in the DAG, u appears before v in the permutation. Your task is ...
163 views

### Array combinatoric comparison

Introduction You may remember sudoku, where there can only be one of each number in each row, column and block of nine. The general idea is that if the array contains but one element, you can submit ...
994 views

### The number of reachable snake orientations

This challenge is not about the game Snake. Imagine a 2d snake formed by drawing a horizontal line of length n. At integer points along its body, this snake can rotate its body by 90 degree. If we ...
883 views

### How many ways to write N as a product of M integers?

Given an integer N, count how many ways it can be expressed as a product of M integers > 1. Input is simply N and M, and output is the total count of distinct integer groups. Meaning you can use an ...
2k views

### Generate the Stöhr sequence

I am learning Ruby and wrote my first nontrivial code to solve this problem. The challenge is to generate the first n elements of the Stöhr sequence, S, which is defined as follows: S[0] = 1 ...
1k views

### Building a long chain of words

This challenge is to find the longest chain of English words where the first 3 characters of the next word match the last 3 characters of the last word. You will use an common dictionary available in ...
1k views

### Golf me some cash from the ATM

The task is simple. Get me some 1000, 500 and 100 notes. How ? you might ask. Don't worry, no need of robbing a bank as there is an ATM nearby which accepts your credit card. But your credit limit is ...
510 views

### Curator's Dilemma

Introduction You are a friend of a curator for an art museum, who has had the recent delight of getting modern art from four artists (some of which may give the curator zero pieces of art, young ...
314 views

### Robot roadie needed to pack the truck

As the band's roadie, you have to pack the truck. Your program will place the packages so that they fit in the smallest height. A badly packed truck Rules Packages may be rotated through ...
301 views

### Compute the Join and Meet of Partitions

Background In this challenge, a partition of a set S means a collection of nonempty subsets of S, which are mutually disjoint and whose union is S. We say that a partition p is finer than another ...
101 views

### Minimum number of coins to get -closest- to target value? [closed]

There's the old, well hashed version of the question that uses Dynamic Programming to calculate the minimum number of coins to reach a target value, but what if the coins you're given can't reach the ...
645 views

### Generate the shortest De Bruijn

A De Bruijn sequence is interesting: It is the shortest, cyclic sequence that contains all possible sequences of a given alphabet of a given length. For example, if we were considering the alphabet ...
369 views

### Forming Polyominoes with a Chain of Rods

Background Consider a (closed) chain of rods, each of which has integer length. How many distinct hole-free polyominoes can you form with a given chain? Or in other words, how many different ...
711 views

### Combinatorial products of unique primes

Statement of problem Given a set of unique, consecutive primes (not necessarily including 2), generate the products of all combinations of first powers of these primes — e.g., no repeats — and also ...
396 views

### Print all domino tilings of 4x6 rectangle

This is an extension of Fibonacci Domino Tiling. Your goal is to print all 281 ways to tile a 4x6 rectangle with 1x2 and 2x1 dominoes. Fewest bytes wins. Use the vertical bar | to indicate a space ...