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.
212 questions
6
votes
2
answers
338
views
Count the possible folds of an n² grid
Inspired by this recent video, I figured we could get a new value for the OEIS sequence A001418 with a fastest-code challenge. There's a sample java implementation here if you change the 2 on line 159 ...
- 1,448
4
votes
3
answers
514
views
Fill in matrices for matrix bit flipping as quickly as possible
Consider an n by n binary matrix. If it has rank r <= n, then we want to compute the largest number bits flips necessary to reduce its rank to a specific value. All computations should be done ...
- 3,275
3
votes
4
answers
478
views
Create 251610 matrices as quickly as possible
There are 251610 6 by 6 binary matrices that are inequivalent. We say two matrices are equivalent if there is some permutation of their rows and/or columns that makes them equal.
For example:
...
- 3,275
8
votes
5
answers
904
views
Pólya trees counted efficiently
The number of unlabeled rooted trees with n nodes is a fundamental sequence in graph theory and in discrete mathematics in general.
Some authors call these trees 'Polya trees'. The number of these ...
- 1,502
3
votes
3
answers
263
views
Non-Decreasing Fibonacci Sequence modulo M
Given integers \$a,b,m, k, n\$ and array \$F = (f_1, f_2,...,f_n)\$ defined as:
\begin{cases}
f_1 = \text{a}\\
f_2 = \text{b}\\
f_i = (f_{i-1} + f_{i-2}) \text{ mod m},∀i > 2
\end{cases}
When \$F\$ ...
- 123
11
votes
6
answers
2k
views
9-16-25 2D Matrix
Given three grids and the sum of rows and columns of each grid, your task is:
Grid \$3×3\$: Fill the grid from \$1\$ to \$9\$, ensure no repeats within the grid.
Grid \$4×4\$: Fill the grid from \$1\...
user123147
-1
votes
3
answers
502
views
Sum of Positive and Negative Powers of 2
Given a binary string equivalent to \$n\$, write out the least possible number of terms needed to express \$n\$.
A term is defined as an addition of either \$2^k\$ or \$(-2^k)\$, where \$k\$ is a non-...
user123116
3
votes
4
answers
703
views
Fastest count of certain hypercubes with labeled vertices
CHALLENGE
This is a fastest-code challenge.
Count how many n-dimensional hypercubes with n=1,2,3,4 exist, with vertices labeled with either 1 or 0, such that there does not exist any rectangle formed ...
- 139
2
votes
2
answers
248
views
Binary expansion and partition numbers [closed]
Not sure if it's correct to ask such a question on this site, but let's try.
Let a(n) be a sequence of positive integer such that a(1) = 1. To reproduce the sequence a(n) through itself, use the ...
10
votes
5
answers
2k
views
Random factorized numbers
Input
The code should take an integer \$n\$ between 1 and 1000.
Output
The code should output positive integers with \$n\$ bits. Accompanying each integer should be its full factorization. Each ...
- 3,275
6
votes
5
answers
776
views
Count the size of the Levenshtein neighborhood
Input
A binary string \$s\$ of length \$n\$ and a positive integer \$k \leq n\$.
Output
The number of binary strings with Levenshtein distance exactly \$k\$ from the string \$s\$.
Example outputs
Each ...
- 3,275
5
votes
4
answers
667
views
Compute convolution quickly and accurately
Input
An array A of integers of length 100,000. The array will contain only integers in the range 0 to 1e7.
Output
The convolution of A with itself. As this will be of length 199999 you should time ...
- 3,275
16
votes
5
answers
862
views
Compute the chromatic number of special graphs
This challenge is about computing the chromatic number of special types of graphs.
Input
The input will consist of two integers.
A positive integer \$n > 1\$.
A distance \$d < n\$.
Task
The ...
- 3,275
12
votes
10
answers
3k
views
Calculate max depth of JSON data
Challenge
Given some JSON data, calculate the maximum depth reached. (Both arrays and dictionaries increase the depth)
Input/Output
The program is expected to read a JSON string from stdin and as soon ...
user118390
21
votes
8
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,918
0
votes
1
answer
311
views
Generate all possible equations from a list of numbers [closed]
This is my first codegolf post so let me know if I have missed anything. Thanks :)
Description
You are given a list of numbers with 2 < n <= 6 length i.e. [1, ...
- 21
10
votes
5
answers
625
views
Record Least Uncommon Multiple Counts
The Greatest Common Divisor, or gcd, of two positive integers \$x\$ and \$y\$ is the largest positive integer that divides both \$x\$ and \$y\$.
The Least Common Multiple, or lcm, of two positive ...
- 1,767
10
votes
1
answer
449
views
Find the linear transformation
Given a set of bit vectors \$A\$ and a binary matrix \$M\$, we can define the set \$MA = \{ Mx : x \in A \}\$, where \$ M x \$ is the result of the matrix multiplication of \$ M \$ by \$ x \$ over \$\...
- 10.7k
5
votes
1
answer
369
views
Triangularly embed a graph on a surface
This challenge arises from a claim made in a MathOverflow answer and a paper linked in that answer which seems to back up the claim:
Searching for triangular embeddings is much quicker than ...
- 3,945
4
votes
1
answer
869
views
Generate all possible equations with 10 characters
Nerdle is a Wordle variant, in which instead of words, the answers are equations. Each equation entered in the game must be a valid one.
Examples: 13³-1=2196, ...
- 151
8
votes
5
answers
434
views
Simultaneously solve N-queens and no-3-in-line
An intriguing MathsSE question asked if there were large N-queens solutions where no three queens lie on a line. That question's body included the unique 4×4 solution up to symmetries
...
- 3,945
9
votes
2
answers
595
views
Base64 fixed point
It can be proven that there's exactly one string of infinite length that remain same after base64 encoding ...
- 28.3k
13
votes
4
answers
2k
views
Tips for improving your score in fastest code challenges
Fastest code is a scoring method on this site where the goal is to write code that is as fast as possible.
From the tag wiki:
The winner of a fastest-code challenge is determined by the runtime ...
- 13.5k
9
votes
4
answers
611
views
RADD decomposition of an integer
Introduction
The \$RADD(n)\$ operation is defined as the sum of \$n + [\$ the number whose decimal representation are the decimal digits of \$n\$ in reverse order \$]\$, see A004086. After reversal, ...
- 701
8
votes
3
answers
436
views
Smallest and largest 100-bit square with maximum Hamming weight
Introduction
In the binary representation of a \$k-\$bit \$(k>1)\$ square number \$n^2, \$ not all bits can be \$1\$. The maximum number of \$1\$-bits (Hamming weight, \$B\$ for short) is given in ...
- 701
-10
votes
4
answers
394
views
Fastest code: Does a list of string contains %s, %d, %f, or %r?
The aim is to create an algorithm to detect that one of the string in a small list of strings contains %s, %d, ...
- 313
19
votes
13
answers
894
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
20
votes
7
answers
4k
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 ...
- 9,001
7
votes
5
answers
989
views
Fastest Gematria calculator
Gematria is an ancient Jewish method to determine a numeric value of a letter sequence, using a fixed value for each letter. Gematria is originally applied to Hebrew letters, but for the context of ...
- 183
6
votes
3
answers
594
views
Generate Fibonacci Primes Quickly
Unsurprisingly, fibonacci primes are primes that are also Fibonacci numbers. There are currently 34 known Fibonacci primes and an additional 15 probable Fibonacci primes. For the purpose of this ...
- 2,495
6
votes
1
answer
2k
views
fastest matrix multiplication on x86
This challenge requires integration with C, so you can stop reading if you're not interested.
Matrix multiplication is a simple operation, but the performance depends a lot on how efficiently the code ...
- 2,375
1
vote
1
answer
538
views
Best performance on x/(y+z) + y/(x+z) + z/(x+y) = N
Consider the equation $$\frac x {y+z} + \frac y {x+z} + \frac z {x+y} = n$$ for positive integers \$x, y, z\$ and \$n \ge 4\$. Your code will receive \$n\$ as an input, and output three integers \$x, ...
- 1,548
10
votes
2
answers
553
views
The maximum liberty of a group on a Go board
Bounty
One of the convincing conjectures, by Loopy Walt is,
...
- 2,375
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,918
12
votes
6
answers
1k
views
High throughput prime numbers
This challenge is inspired by the High throughput Fizz Buzz challenge.
The goal
Generate a list of prime numbers up to 10,000,000,000,000,000. The output of primes should be in decimal digits followed ...
- 2,375
6
votes
2
answers
885
views
Write the most optimized assembly program to detect a prime number (from a bigger range!)
This is the second version of the task. The original task had a defect that the given range of integers was too small. This was pointed out by @harold that other methods couldn't defeat the way of ...
- 2,375
2
votes
1
answer
1k
views
An Scalable Event Scheduler That Can Handle Billions of Events [closed]
The event scheduler is a recurrent theme in event-driven architectures: something triggers an event that needs to be checked in the future one or more times. I has particular use in trading where you ...
user108147
6
votes
1
answer
600
views
Fast Matrix Multiplicator Evaluator
A triplet of real tensors \$(A,B,C)\$ of size \$\gamma \times \gamma \times \sigma\$ represents a matrix multiplication algorithm with \$\sigma\$ elementary multiplications iff the following function ...
- 69
7
votes
4
answers
1k
views
Bigram frequencies in text
Introduction
This challenge is about producing a code to count the frequency of bigrams in a text. A bigram is two consecutive letters in a text. For instance 'aabbcd' contains the bigrams aa, ab, bb, ...
- 179
7
votes
2
answers
530
views
Compute the size of intersections of sets
Input
A positive integer N representing the size of the problem and four positive integers v, x, y, z.
Output
This is what your code should compute. Consider a set of N distinct integers and consider ...
user7467
6
votes
4
answers
414
views
Swap encoding iteration count
Introduction
In this challenge, I asked you to implement swap encoding.
Swap encoding is an encoding method where you iterate through the string, reversing substrings between identical characters. The ...
- 44.2k
7
votes
3
answers
455
views
Fastest unique finder
Given 4096 16-bit integers, only four of which are unique and others appeared twice (so 2050 different integers exist). Find the four uniques.
To time precisely and limit RAM usage, your program will ...
- 28.3k
15
votes
2
answers
438
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^...
- 9,001
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
-2
votes
1
answer
202
views
Print all digits of an integer [duplicate]
Challenge
Given a positive integer, find the fastest way to iterate over its digits. Bytecode size doesn't matter as much as speed of execution.
Examples
For 6875, the program would output ...
- 105
9
votes
3
answers
437
views
Patterns in Permutations
This fastest-code challenge is based partly on this MSE question and exists to extend some OEIS sequences, and create others. If I extend or create sequences based on this challenge, I'll link to this ...
- 9,001
5
votes
1
answer
365
views
2D Pathfinding with Momentum
You are piloting a spaceship, outfitted with an engine that can accelerate you at 1km/s^2 in the direction the ship is facing (you have very good inertial dampers). You also have thrusters which can ...
- 2,179
44
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 [...] ...
- 9,001
2
votes
0
answers
278
views
Compute the Three Dimensional Discrete Cosine Transform
Challenge
I've checked that there is a question Compute the Discrete Cosine Transform which is a competition for implementing a shortest solution to compute the one dimensional discrete cosine ...
- 403
8
votes
4
answers
1k
views
Compute all close strings quickly
Input
A string S of length between 10 and 16 inclusive. The characters are taken from the 95 printable ASCII characters, byte values 32 (...
user7467