for challenges involving combinatorics.

learn more… | top users | synonyms

11
votes
3answers
218 views

Permutations of the Fifteen Puzzle

The Challenge Consider the following diagram of the Fifteen Puzzle in its solved state: _____________________ | | | | | | 1 | 2 | 3 | 4 | |____|____|____|____| | | | | | ...
7
votes
3answers
206 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] ...
17
votes
2answers
296 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
votes
0answers
14 views

Help with shortening this Haskell combinations snipped [migrated]

I was happy with my shell script that needed to generate alphanumeric combinations of length N (in this case, 3) for i in {a..z}{a..z}{a..z}; do ... Now I became less happy when I needed ...
4
votes
1answer
166 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 ...
10
votes
3answers
296 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 ...
13
votes
4answers
390 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 ...
11
votes
6answers
268 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 ...
9
votes
0answers
200 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 ...
19
votes
2answers
383 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}, ...
5
votes
3answers
566 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. ...
9
votes
1answer
156 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 ...
10
votes
3answers
529 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 ...
26
votes
19answers
2k 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 ...
36
votes
10answers
4k 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 ...
15
votes
6answers
513 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 ...
6
votes
3answers
284 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 ...
9
votes
2answers
159 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 ...
12
votes
10answers
586 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, ...
13
votes
11answers
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 ...
2
votes
1answer
186 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, ...
10
votes
1answer
217 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 ...
8
votes
5answers
323 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 ...
2
votes
2answers
155 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 ...
11
votes
2answers
970 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 ...
10
votes
5answers
784 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 ...
10
votes
22answers
1k 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 ...
15
votes
8answers
755 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 ...
26
votes
2answers
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 ...
7
votes
4answers
504 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 ...
12
votes
1answer
296 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 ...
4
votes
2answers
213 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 ...
2
votes
0answers
78 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 ...
14
votes
4answers
603 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 ...
18
votes
2answers
350 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 ...
12
votes
9answers
675 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 ...
5
votes
4answers
329 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 ...
13
votes
8answers
864 views

Draw a range of mountain ranges

Inspired by Fibonacci domino tiling, this problem is about generating ASCII art representing another famous combinatorial sequence. A n-step mountain diagram is a drawing of a mountain range, using ...
8
votes
9answers
1k views

Fibonacci domino tiling

There's classic combinatorial result that the number of ways to tile a 2*n strip by 1*2 dominoes is the nth Fibonacci number. You goal is to print all the tilings for a given n, drawn with dashes and ...
6
votes
1answer
226 views

Arranging Fenceposts

If you want to build a fence and have different length boards available, there are many different ways to set up your posts. So, given a minimum and maximum board length, a number of boards, and the ...
10
votes
1answer
614 views

How much time will I need to unlock my Android phone?

Scenario I am using pattern matching lockscreen and I sadly forgot my pattern. I would like to know how much time I will need to unlock it. Here are the specifications of Google's lock screen, that ...
6
votes
5answers
489 views

Permutation Numbering

The Challenge For a given set of n integers, write a program which will output its lexicographic index. The Rules The input must only be a set of unique non-negative integers separated by spaces. ...
6
votes
5answers
546 views

Output nth term in Catalan type sequence

Given a number, starting with 1, create new numbers (children) by taking the last digit, n, and concatenating 1 through n+1. This seems to be a much better explanation of the sequence A071159. ...
7
votes
6answers
562 views

Unique Array Combinations

The goal is to write a function or program which takes a set of integer arrays and returns a set of all possible arrays which meet the following criteria: A valid array must contain at least one ...
20
votes
4answers
1k views

Build a pair of spies that will throw stones into a river

Recently at the newly released Puzzling.SE, there was a problem about spies throwing stones into a river that was actually quite challenging: Two spies must pass each other two secret numbers (one ...
17
votes
1answer
903 views

Android Lock Screen

Intro You are sitting in a board room at the end of a long table. You look around and see Tim Cook, the Apple Board of Directors, the ghost of Steve Jobs, and Jack Donaghy. Apple has called this ...
9
votes
3answers
1k views

building circuit for divisibility by 3

A boolean circuit in TCS is basically a DAG consisting of And, Or, Not gates, and by what is known is "functional completeness" they can compute all possible functions. eg this is the basic principle ...
33
votes
8answers
1k views

Lazy battleship placement

Imagine the following scenario: you are playing battleships with a friend but decide to cheat. Rather than moving a ship after he shoots where your ship used to be, you decide not to place any ships ...
2
votes
2answers
464 views

How many unique ways are there to achieve a score in Football? [duplicate]

Challenge: given a number, calculate how many unique, order-independent ways there are to achieve a score of that number in American Football. Let's see how few characters can be used in each of ...
11
votes
1answer
355 views

Generate the fewest lottery tickets to play in order to have at least N good numbers

This is a rather complex but very interesting maths subject (known as "covering problem"), And I'd like your help for implementing it. Imagine a lottery game, where each ticket must choose 5 random ...