The winner of a fastest-code challenge is determined by the runtime performance of the submissions. For fairness, all submissions should be benchmarked on the same machine, which usually means all submissions have to be tested by the host of the challenge. For scoring by asymptotic time complexity, ...
6
votes
1answer
238 views
Help the poor Cryptographers - DLP Edition
Introduction and Motivation
I'm mainly active on Cryptography.SE and as such have already stumbled across the question: "How the hell am I supposed tools like cado-nfs to do stuff!?". They are super-...
1
vote
3answers
251 views
The fastest square root calculator [closed]
Write a program which outputs the square root of a given number in the shortest time possible.
Rules
It may not use any builtins or powering with numbers between 0 and 1.
Input format
as a ...
23
votes
2answers
1k views
Compute the maximum number of runs possible for as large a string as possible
[This question is a follow up to Compute the runs of a string ]
A period p of a string w is any positive integer p such that w[i]=w[i+p]
whenever both sides of this equation are defined. Let per(...
16
votes
3answers
374 views
Find all the Solutions to this Number Puzzle in the Shortest Time Possible
History
My company sends out a weekly newsletter to everyone within the company. Included in these newsletters is a riddle, along with a shoutout to whomever in the company was the first to email/...
15
votes
3answers
654 views
Quickly express a number with only 0-9 and the four operations, plus one more extra
Explanation
Befunge is a two-dimensional program that uses stacks.
That means, to do 5 + 6, you write 56+, meaning:
56+
5 push 5 into stack
6 push 6 into stack
+ pop the first two items in ...
25
votes
2answers
1k views
Approximating a special case of the Riemann Theta function
This challenge is to write fast code that can perform a computationally difficult infinite sum.
Input
An n by n matrix P with integer entries that are smaller than 100 in absolute value. When ...
10
votes
2answers
413 views
Tic-tac-toe with only crosses as quick as possible
As per Luke's request and Peter Taylor's addition to this challenge.
Introduction
Everyone knows the game tic-tac-toe, but in this challenge, we are going to introduce a little twist. We are only ...
6
votes
1answer
347 views
Find the longest path, avoiding obstacles in a 2D plane
The Scenario
You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can ...
3
votes
5answers
282 views
Reproportioning a population by adding fixed sized groups
Introduction
Say you have a population of people. This population is made up of 100 Alices and 25 Bobs. So, 80% of the population are Alices and 20% are Bobs. We want to change the proportional ...
46
votes
13answers
3k views
Calculate the number of primes up to n
π(n) is the number of primes less than or equal to n.
Input: a natural number, n.
Output: π(n).
Scoring: This is a fastest-code challenge. Score will be the sum of times for the score cases. I ...
8
votes
4answers
457 views
Counting orthogonal circulant matrices
Two rows of a matrix are orthogonal if their inner product equals zero. Call a matrix with all rows pairwise orthogonal an orthogonal matrix. A circulant matrix is one where each row vector is rotated ...
10
votes
1answer
219 views
Set Theoretic Arithmetic (+ and *) [closed]
Set Theoretic Arithmetic
Premise
There have been a couple challenges already that involve multiplying without the multiplication operator ( here and here ) and this challenge is in the same vein (...
11
votes
2answers
630 views
Fastest Longest Common Subsequence Finder
Your task is to solve the Longest Common Subsequence problem for n strings of length 1000.
A valid solution to the LCS problem for two or more strings S1, … Sn is any string T of maximal ...
7
votes
3answers
367 views
Integral triangles and integral medians
Consider a triangle ABC where each side has integer length (an integral triangle). Define a median of ABC to be a line segment from a vertex to the midpoint of the opposing side. In the figure below, ...
19
votes
12answers
2k views
Sum of smallest prime factors
SF(n) is a function which computes the smallest prime factor for a given number n.
We'll call T(N) the sum of every SF(n) with 2 <= n <= N.
T(1) = 0 (the sum is over 0 summands)
T(2) = 2 (2 ...
14
votes
7answers
989 views
Find the maximum determinant for each size Toeplitz matrix
For a fixed n, consider the n by n Toeplitz matrices with entries which are either 0 or 1. The aim is to find maximum determinant over all such Toeplitz matrices.
Task
For each n from 1 upwards, ...
7
votes
1answer
629 views
Snakes and Ladders probability of winning
(This is my first Q here, and I don't know much about code golfing.)
Your aim is to predict the winner of an ongoing Snakes and Ladders game.
INPUT
A single number (2-1000) indicating the number of ...
-7
votes
2answers
239 views
Solve the Diophantine Pell equation
Given a natural number c as input, our task is finding the fastest way to calculate one -atleast- availabe integer solution (a,b) of pell equation c=a²-b².
Rules
Built-in functions and loopholes ...
9
votes
4answers
474 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 ...
6
votes
3answers
551 views
Covering Array Validator
A covering array is an N by k array in which each element is one of {0, 1, ..., v-1} (so v symbols in total), and for any t columns chosen (so an N x t array) contains all possible v^t tuples at least ...
5
votes
1answer
430 views
Compute 30000 Digits of Pi (π), as Fast as Possible [duplicate]
Compute 30000 digits of the mathematical constant π, with the fastest code.
Implement in any computer programming language that I can run in my 64 bit Linux machine. You should provide your compiler ...
9
votes
2answers
732 views
Probabilities - how high can you go?
I previously asked a question for how to compute a probability quickly and accurately. However, evidently it was too easy as a closed form solution was given! Here is a more difficult version.
This ...
8
votes
5answers
950 views
Calculate a probability exactly and quickly
[This is a partner question to Calculate a probability exactly ]
This task is about writing code to compute a probability exactly and quickly. The output should be a precise probability written as a ...
31
votes
2answers
1k 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 ...
9
votes
3answers
521 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 ...
1
vote
0answers
37 views
Searching for a sum [duplicate]
In this challenge you will take two inputs
One input will be a string of numbers of any length which you will put into an array/table/whatever you call it in your language
Ex:
10 10 145 20 53 102 20
...
11
votes
4answers
804 views
Magic Sequences of length n
A magic sequence is a sequence of non-negative integers x[0..n-1] such that there are exactly x[i] instances of i
For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence since there are 6 0's, 2 1’s, ...
10
votes
3answers
346 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 0s as 1s.
You are given a positive ...
10
votes
3answers
578 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 ...
11
votes
1answer
313 views
Constructing an Orthogonal-Diagonal Greco-Latin Square
Consider a grid of NxN unique elements. Each element has a letter (from A to the Nth letter, inclusive) and a number (from 1 to N, inclusive). Hence, each number/letter pair is in the grid exactly ...
18
votes
3answers
813 views
Finding all-but-one matches
This challenge is about writing code to solve the following problem.
Given two strings A and B, your code should output the start and end indices of a substring of A with the following properties.
...
4
votes
7answers
509 views
Fastest array-by-array nearest neighbour search
Intro -
Nearest neighbour comparison between two arrays is something that can be done very efficiently when only 1 variable per array is involved, because it can be done by sorting and then performing ...
5
votes
2answers
777 views
Coding a recursive function for highest possible input
Challenge
You are given the following function:- which is the same as:-
with the base cases q(r, b, L) = 1 whenever r ≤ L, q(r, 0, L) = 0, if r > L and q(r, 0, L) = 1, if r ≤ L.
Your task is to ...
18
votes
2answers
408 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 non-self-...
-4
votes
2answers
142 views
Magical Squares [closed]
A perfect square is a number that is the square of an integer.
However, let's define something called a Magical Square, which is a perfect square with the following restriction:
The perfect square ...
1
vote
1answer
280 views
Chotchkies Restaurant [duplicate]
Because there isn't enough xkcd on PPCG...
Challenge
The challenge is the same as above - given a menu and a total price, you need to find what the customer ordered.
The menu will be supplied as a ...
12
votes
3answers
796 views
Be an Epidemiologist!
Challenge
You must create a simple model of how disease spreads around a group of people.
Rules and Requirements
The model must be a 1000 by 1000 2D array with each element being a different person....
12
votes
6answers
472 views
False Positives on an Integer Lattice
Leaderboard
User Language Score
=========================================
Ell C++11 293,619,555
feersum C++11 100,993,667
Ell C++...
12
votes
8answers
913 views
Digit sum of central binomial coefficients
The task is simply to see how much faster you can calculate n choose n/2 (for even n) than the builtin function in python. Of course for large n this is a rather large number so rather than output ...
5
votes
3answers
1k views
Another Euler Brick in the Wall
A Euler Brick is a cuboid where the length of all the edges are integers and all of the diagonals of the faces are integers as well. All sides must also be different.
Your program has to find as many ...
5
votes
3answers
772 views
The distance between circles
Imagine you are given two lists of numbers which are to be interpreted as points on a circle of circumference 1000. Let us say
circleA = [10, 24, 44, 175, 321, 579, 618, 841, 871, 979]
circleB = [...
7
votes
2answers
593 views
2nd byte bias of RC4
Short version
RC4, designed in 1987, is one of the most famous stream ciphers. This question asks you to practically demonstrate its 2nd byte bias (for a theoretical proof, see section 3.2 of this ...
7
votes
1answer
545 views
'Number' Crunching Benchmark
I just want to do some benchmarking of different programming languages. So here is a tip: You can use as many characters as you want. In the end there is only the time your program needed.
So, here ...
2
votes
0answers
113 views
Write program which finds shortest expression for number [duplicate]
Write program which finds shortest expression for big integer.
Expression may consist of + - * / ^ ! ( ) operations.
! stands for factorial, ^ - exponentiation, / - rational division.
Number itself ...
5
votes
0answers
281 views
Write a FAST word equation solver [duplicate]
This question is similar to Write a word equation solver by David Frank but different in three important ways: (1) David asked for just the first solution found, and I am asking for all the solutions. ...
5
votes
1answer
1k views
Optimal Minesweeper on the Largest Board
Overview:
Your challenge is to write a program that will play minesweeper optimally, giving the best move in any position. Moreover, you must do this on the largest board possible.
Game details: ...
4
votes
2answers
728 views
Longest mathematical expression in a grid
Given a grid which contains these signs: 0..9, x, =, write the fastest code that outputs the longest string of connected (horizontally, vertically, and diagonally adjacent), distinct cells which is a ...
0
votes
1answer
230 views
Find the fastest swim relay (shortest path of unique nodes and types)
fastest relay time = lowest possible total integer value of
(a freestyle swimmers time) + (1 breastroke swimmers time) + (another backstroke swimmers time) + (another butterfly swimmers time)
Each ...
1
vote
2answers
675 views
Find nth root of variable without using math operators/functions
Write a program which, given two positive integers n and x, will display the n-th root of x (which is also x1/n) in decimal to an accuracy of 0.00001. The program must output the resulting number in ...
15
votes
3answers
3k views
Fastest player for Dots and Boxes
The challenge is to write a solver for the classic pencil and paper game Dots and Boxes . Your code should take two integers m and n as input which specifies the size of the board.
Starting with ...
