# Questions tagged [fastest-code]

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, use [fastest-algorithm] instead.

132 questions
3k 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 ...
1k 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 ...
2k 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 ...
641 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 ...
570 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 ...
632 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 ...
556 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 ...
811 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 ...
1k 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 ...
2k 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 ...
604 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 ...
40 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: ...
2k 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 ...
457 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 ...
624 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 1...
665 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,...
889 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. ...
3k 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 ...
803 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 ...
527 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-...
158 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 ...
309 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 ...
841 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....
3k views

### Un-hash the Java Hash

Hash Un-hashing The basic goal of this challenge is to exploit the high probability of collision in the Java Hash function to create a list of plausible inputs that created an outputted hash. The ...
527 views

1k 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 ...
2k 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 ...
838 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 ...
1k 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 ...
5k views

### Find the largest prime whose length, sum and product is prime

The number 113 is the first prime whose length 3 is prime, digital sum 5 = 1 + 1 + 3 is ...
803 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 ...
119 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 ...
312 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. ...
2k 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: ...
855 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 ...
252 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 ...
1k 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 ...
6k 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 ...
3k views

### Fast Trig Calculation

Fast Trigonometry Calculations Your task is to create a program which can calculate the sine, cosine and tangent of an angle in degrees. Rules No built-in trigonometry functions (not even secant, ...
1k views

### Super fast sampling from a tricky random distribution

This is a micro-optimization challenge. The task is to sample from the maximally skewed stable distribution F(x;1,-1,Pi/2,0). See Table 1 of http://arxiv.org/pdf/0908.3961v2.pdf . It is easiest to ...
456 views

### Filter a large file in small memory

The challenge is a follow-up to Filter a large file quickly which had two submissions where were as fast as wc! This time the difficulty is that RAM is severely restricted which means that new ...
18k views

### Super speedy totient function

The goal is simple: calculate the totient function for as many numbers as you can in 10 seconds and sum the numbers. You must print your result at the end and you must actually calculate it. No ...
5k views

### How much can you quickly multiply?

With the recent Python bashing, here's an attempt to show Python's strengths. Your challenge is to write a program that calculates the factorial of as high a number ...
2k views

### Filter a large file quickly

The challenge is to filter a large file quickly. Input: Each line has three space separated positive integers. Output: All input lines A ...
8k views

### How high can you go? (A coding+algorithms challenge)

Now that everyone has developed their (often amazing) low level coding expertise for How slow is Python really? (Or how fast is your language?) and How Slow Is Python Really (Part II)? it is time for ...
19k views

### How Slow Is Python Really (Part II)?

This is a follow up to How slow is Python really? (Or how fast is your language?). It turns out it was a bit too easy to get a x100 speedup for my last question. For those who have enjoyed the ...
105k views

### How slow is Python really? (Or how fast is your language?)

I have this code which I have written in Python/NumPy ...
208 views

### Merging text files based on a prefix key

Imagine an ordered file set : file1, file2, ... fileN. Each file is a textual file that is ...
709 views

### Analysing the most common words in a text, and replacing them with a single byte

This is a very crude text encoding algorithm I came up with the other day. It won't work if the text has more than 256 different characters in it – but it does support Unicode, at least in my Python ...
285 views

### Creating a catalogue index

You have a program which creates an index for a catalogue. The last step is missing: it must find and consolidate page ranges within the list of pages for each entry. Each entry is currently an ...