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. Alternatively, the submission can be compared to a reference program. For scoring by asymptotic time complexity, use [fastest-algorithm] instead.
204
questions
332
votes
40
answers
289k
views
High throughput Fizz Buzz
Fizz Buzz is a common challenge given during interviews. The challenge goes something like this:
Write a program that prints the numbers from 1 to n. If a number is
divisible by 3, write Fizz instead....
- 2,539
153
votes
21
answers
112k
views
How slow is Python really? (Or how fast is your language?)
I have this code which I have written in Python/NumPy
...
user9206
74
votes
16
answers
15k
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 ...
- 3,205
71
votes
23
answers
12k
views
Fastest way to sort a big array of Gaussian-distributed data
Following the interest in this question, I thought it would be interesting to make answers a bit more objective and quantitative by proposing a contest.
The idea is simple: I have generated a binary ...
- 713
54
votes
14
answers
20k
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 ...
user9206
53
votes
4
answers
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 ...
- 196k
45
votes
3
answers
4k
views
Help Indiana Jones to get the treasure
Story
Indiana Jones was exploring a cave where a precious treasure is located. Suddenly, an earthquake happened.
When the earthquake ended, he noticed that some rocks that had fallen from the ...
- 3,472
41
votes
0
answers
2k
views
Topologically distinct ways of dissecting a square into rectangles
I was asked by OEIS contributor Andrew Howroyd to post a Code Golf Challenge to extend OEIS sequence A049021.
Would be super great to get a couple more terms for [...] A049021. Kind of thing [...] ...
- 8,659
39
votes
18
answers
8k
views
Bentley's coding challenge: k most frequent words
This is perhaps one of the classical coding challenges that got some resonance in 1986, when columnist Jon Bentley asked Donald Knuth to write a program that would find k most frequent words in a file....
- 621
37
votes
12
answers
6k
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 ...
- 89.3k
37
votes
4
answers
18k
views
Fastest semiprime factorization [closed]
Write a program to factorize a semi-prime number in the shortest amount of time.
For testing purposes, use this:
\$38!+1\$ (\$523022617466601111760007224100074291200000001\$)
It is equal to:
\$...
- 1,649
36
votes
19
answers
10k
views
Fastest yes in the west
There has been a question about yes in the past, but this one is slightly different. You see, despite yes having a rather long size, it is incredibly fast. Running ...
- 495
36
votes
12
answers
17k
views
The fastest Sudoku solver
Winner found
It seems as if we have a winner! Unless anyone plans on contesting the world's current fastest Sudoku solver, user 53x15 wins with the staggeringly fast solver Tdoku. For anyone still ...
- 6,837
35
votes
11
answers
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 ...
user9206
30
votes
9
answers
5k
views
Calculate the permanent as quickly as possible
The challenge is to write the fastest code possible for computing the permanent of a matrix.
The permanent of an n-by-n matrix ...
user9206
28
votes
3
answers
1k
views
Delete some bits and count
Consider all 2^n different binary strings of length n and assume n > 2. You are allowed ...
user9207
27
votes
6
answers
2k
views
Prime containment numbers (speed edition)
This is sequence A054261
The \$n\$th prime containment number is the lowest number which contains the first \$n\$ prime numbers as substrings. For example, the number \$235\$ is the lowest number ...
- 6,837
27
votes
4
answers
972
views
Buildings made from cubes
In this fastest-code challenge, you are provided with a set of \$n\$ identical blocks and need to determine how many unique buildings can be constructed with them. Buildings must satisfy the following ...
- 19.1k
26
votes
2
answers
3k
views
Fastest Mini-Flak Quine
Mini-Flak is a subset of the Brain-Flak language, where the <>, <...> and [] ...
- 96.5k
26
votes
3
answers
2k
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 ...
user9206
24
votes
2
answers
2k
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 ...
user9206
23
votes
12
answers
2k
views
Quicksand (piles)
In this fastest-code challenge, you take a positive integer as input, which represents the height of a sand pile, located at (0,0) on an infinite square grid. For example, if our input is ...
- 7,828
23
votes
4
answers
3k
views
The Missing Number Revised
Background:
I originally posted this question last night, and received backlash on its vagueness. I have since consulted many personnel concerning not only the wording of the problem, but also its ...
- 405
23
votes
6
answers
1k
views
Fastest Home Prime Generator
What is a home prime?
For an example, take HP(4). First, find the prime factors. The prime factors of 4 (in numerical order from least to greatest, always) are 2, 2. Take those factors as a literal ...
- 861
22
votes
9
answers
2k
views
Build an Electrical Grid
The Challenge
There are N cities aligned in a straight line. The i-th city is located A[i] kilometers to the right of the origin. No two cities will be in the same ...
- 2,421
22
votes
3
answers
842
views
Find the number of n-by-n (-1, 0, 1) matrices with zero permanent as quickly as possible
The permanent of an \$n\$-by-\$n\$ matrix \$A = (a_{i,j})\$ is defined as:
$$\operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}$$
For a fixed \$n\$, consider the \$n\$-by-\$n\$ ...
- 665
22
votes
8
answers
1k
views
Products that equal a sum and vice versa
A fun pair of equivalences is 1 + 5 = 2 · 3 and 1 · 5 = 2 + 3. There are many like these, another one is 1 + 1 + 8 = 1 · 2 · 5 and 1 · 1 · 8 = 1 + 2 + 5. In ...
- 39k
21
votes
4
answers
23k
views
Fastest code to find the next prime
The problem is as follows.
Input: An integer n
Output: The smallest prime bigger than n.
The challenge is to give the ...
user7467
21
votes
7
answers
1k
views
How many sorting networks?
Below on the left is a picture of a sorting network that can sort 4 inputs. On the right you can see it sorting the input 3,2,4,1.
A sorting network of size ...
- 7,828
21
votes
2
answers
589
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-...
- 196k
20
votes
12
answers
3k
views
Fastest draw in the west! [closed]
We're going rootin' tootin' cow-poke shootin!
This is a simple contest, first program to draw their pistol wins.
How it works:
I require 2 things from you, an executable, and a command to be run
from ...
- 3,831
20
votes
9
answers
21k
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 ...
- 11.5k
20
votes
7
answers
2k
views
The smallest area of a convex grid polygon
I got an email from Hugo Pfoertner, an Editor-in-Chief at the On-Line Encyclopedia of Integer Sequences, with a terrific idea for a fastest-code challenge, which will also help verify or expand the ...
- 8,659
20
votes
4
answers
695
views
Plant trees in a park - As fast as you can!
This challenge is inspired by this app. The test cases are borrowed from that app.
This is a fastest-code challenge, where the objective is to solve the largest test cases in the least amount of time....
- 46.2k
20
votes
2
answers
1k
views
The number of possible numeric outcomes of parenthesizations of 2^2^...^2
Consider an expression 2^2^...^2 with n operators ^. Operator ...
- 2,513
20
votes
1
answer
758
views
Acyclic orientations of an n-dimensional cube
The goal of this challenge is to check and extend the OEIS sequence A334248: Number of distinct acyclic orientations of the edges of an n-dimensional cube.
Take an n-dimensional cube (if n=1, this is ...
- 309
19
votes
12
answers
4k
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 ...
- 599
19
votes
6
answers
1k
views
Fastest tweetable integer factorizer
The task is to find a non-trivial factor of a composite number.
Write code that finds a non-trivial factor of a composite number as quickly as possible subject to your code being no more than 140 ...
user9206
19
votes
13
answers
859
views
As many near-repdigit primes as possible
A near-repdigit number is a positive integer where all the digits are the same, except one. For example 101 and 227 are near-repdigits. A near-repdigit prime is a near-repdigit that is also prime. For ...
user108721
18
votes
3
answers
953
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.
...
user9206
17
votes
3
answers
4k
views
Longest non-repeating Game-of-Life sequence
Given a positive integer N,
determine the starting pattern on a N x N-grid that yield
the longest non-repeating sequence under Game of Life-rules, and ends
with a fixed pattern (cycle of length 1), ...
17
votes
3
answers
8k
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 ...
user9206
17
votes
5
answers
4k
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, ...
user16402
16
votes
3
answers
746
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/...
- 299
16
votes
2
answers
419
views
Permutations such that no k+2 points fall on any polynomial of degree k
Description
Let a permutation of the integers {1, 2, ..., n} be called minimally interpolable if no set of k+2 points (together ...
- 8,659
15
votes
5
answers
3k
views
Fastest Sort in BrainF***
After having implemented QuickSort in BrainF***, I realized it probably wasn't that quick. Operations that are O(1) in normal languages (like array indexing) are significantly longer in BF. Most of ...
- 4,601
15
votes
6
answers
785
views
Calculate the average longest common substring exactly
[Question inspired by Can you calculate the average Levenshtein distance exactly? . Thank you Anush. ]
The longest common substring between two strings is the longest substring which is common to ...
user7467
15
votes
2
answers
417
views
Connecting the Dots: Counting n²-gons in the n×n Grid
The recent volume of MAA's Mathematics Magazine had an article "Connecting the Dots: Maximal Polygons on a Square Grid" by Sam Chow, Ayla Gafni, and Paul Gafni about making (very convex) \$n^...
- 8,659
14
votes
12
answers
1k
views
Finding approximate correlations
Consider a binary string S of length n. Indexing from 1, we can compute the Hamming ...
user9206
14
votes
8
answers
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 ...
user9206