for challenges involving combinatorics.

learn more… | top users | synonyms

-4
votes
0answers
36 views

What is the “best” solution of sudoku? [on hold]

Consider "points" of a sudoku solution is: where c[k] = sum of all abs[(xi - xj)(yi - yj)] such that the values of cell (xi, yi) and (xj, yj) are both equal to k. How many points can you get ?
10
votes
1answer
565 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 ...
5
votes
5answers
449 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
474 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. ...
20
votes
3answers
903 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 ...
8
votes
3answers
689 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 ...
32
votes
8answers
2k 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
278 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
336 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 ...
-1
votes
1answer
140 views

Finding nCr for code-golf [duplicate]

The problem is to compute nCr = n!/(r!) * (n-r)! in the fewest characters possible. The input will be in the form: 1st line will have number of test cases and second line will have n and r for each ...
6
votes
5answers
202 views

Golfing: How many unit-length squares in a list of 2d coordinates?

Given a list of 2d (x, y) coordinates, determine how many unit squares (edge length 1 unit) can be formed using the coordinates. Input will be an array of 0 or more pairs of coordinates: e.g. in ...
5
votes
7answers
317 views

Chess960 position lookup

This is a follow-up to Chess960 position generator. In Chess960, there are 960 possible starting positions that can be enumerated from 0 to 959 (or, at your choice, from 1 to 960). The enumeration ...
10
votes
6answers
606 views

Chess960 position generator

Context Chess960 (or Fischer Random Chess) is a variant of chess invented and advocated by former World Chess Champion Bobby Fischer, publicly announced on June 19, 1996 in Buenos Aires, ...
1
vote
6answers
289 views

Counting ways of scoring k points in n games with half-points for draws

If a game can result in a win, worth one point; a draw, worth half a point; or a loss, worth no points; how many ways are there of scoring k points in n games? Applicable scenarios include NFL and ...
2
votes
8answers
894 views

Compute the number of ways how you can express a number as a sum

For a given natural number n, compute the number of ways how one can express n as a sum of positive natural numbers. For example, for n = 1 there is just one way. For n = 4 we have 5 possible ways: 1 ...
17
votes
2answers
846 views

The number of possible numeric outcomes of parenthesizations of 2^2^…^2

Consider an expression 2^2^...^2 with n operators ^. Operator ^ means exponentiation ("to the power of"). Assume that it has no default assosiativity, so the expression needs to be fully parenthesized ...
3
votes
10answers
436 views

Generate ordered combinations with repetition

Given a string of different characters, and a number n, generate all the ordered combinations with repetition, of length 1 to n, using those characters. Another way to define it is to see the given ...
6
votes
3answers
518 views

The making of “Spot It!”: Finding almost unique sets

Puzzle: Find a deck of c cards, each containing p pictures, such that no two pictures match on a given card, and exactly 1 picture on each card matches exactly 1 picture on each of the other cards, ...
12
votes
7answers
609 views

Write all possible Braille characters

An interesting puzzle came to me looking at the elevator buttons this morning. You are required to generate a list of all Braille patterns that fit in a 2x3 grid. Use a hash # to denote a bump and a ...
1
vote
5answers
235 views

All non-empty finite sets of positive integers

The challenge is to create an iterator(/generator) which iterates (in any order so as to reach all of them... ie no set should occur at infinity) over all possible non-empty finite sets(/tuples/lists) ...
4
votes
7answers
1k views

Generating combinations without recursion

Given a list of strings and a length, give all combinations of that list with the given length. The problem is: your code must not be recursive. Yes, it can be done. I have done it myself, when I had ...
7
votes
13answers
783 views

Code-Golf: Permutations

Write a function that takes as input a set of integers (can be a list, array or any other container with distinct numbers), and outputs the list of all its permutations. Python (95 chars): p=lambda ...
13
votes
29answers
3k views

Generate Pascal's triangle

Pascal's triangle is generated by starting with a 1 on the first row. On subsequent rows, the number is determined by the sum of the two numbers directly above it to the left and right. To ...
4
votes
3answers
356 views

Organize a tournament

Here is a real question somebody asked me. Suppose you have n teams, one terrain. Each team must play each other team exactly once. The number of times a team plays two matches in a row should be ...
7
votes
6answers
823 views

Enumerate all binary trees with n nodes

Given an integer n, enumerate all possible full binary trees with n internal nodes. (Full binary trees have exactly 2 children on every internal node). The tree structure should be output as a ...
1
vote
1answer
776 views

Getting an answer from a string of digits.

Write a program which will find all solutions to make the string "123456789" evaluate to a integer input value by inserting any of the four basic arithmetic operations (+ - * /) into the string in any ...
7
votes
24answers
1k views

Mathematical Combination

Write a program that takes an input such as: n,k which then computes: and then prints the result. A numerical example: Input: 5,2 Internal computation: Printed Output: 10 I'd like ...
11
votes
6answers
953 views

Decompose a permutation into cycles

There is a well-known theorem that any permutation can be decomposed into a set of cycles. Your job is to write the shortest possible program to do so. Input: Two lines. The first contains a ...
8
votes
3answers
303 views

Permutation group operation

There is a well-known bijection between the permutations of n elements and the numbers 0 to n!-1 such that the lexicographic ordering of the permutations and the corresponding numbers is the same. For ...