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.
202
questions
5
votes
5
answers
675
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 ...
- 1,521
4
votes
4
answers
507
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 ...
- 1,521
14
votes
5
answers
792
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 ...
- 1,521
12
votes
10
answers
2k
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 ...
- 261
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,670
0
votes
1
answer
267
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
602
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,637
7
votes
0
answers
203
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 \$\...
- 7,448
3
votes
1
answer
210
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,707
5
votes
1
answer
489
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, ...
- 161
8
votes
4
answers
335
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,707
9
votes
2
answers
449
views
Base64 fixed point
It can be proven that there's exactly one string of infinite length that remain same after base64 encoding ...
- 19.1k
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 ...
- 11.4k
9
votes
4
answers
582
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
360
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
-8
votes
4
answers
337
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, ...
- 317
19
votes
13
answers
851
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
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,649
7
votes
5
answers
819
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
557
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,435
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,325
1
vote
1
answer
501
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,532
9
votes
2
answers
541
views
The maximum liberty of a group on a Go board
Bounty
One of the convincing conjectures, by Loopy Walt is,
...
- 2,325
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,670
11
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,325
6
votes
2
answers
746
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,325
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
585
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
980
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
520
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
407
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 ...
- 34.4k
7
votes
3
answers
431
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 ...
- 19.1k
15
votes
2
answers
416
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,649
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,825
-1
votes
1
answer
196
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 ...
- 107
8
votes
3
answers
408
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 ...
- 8,649
5
votes
1
answer
354
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,125
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,649
2
votes
0
answers
261
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
328
votes
40
answers
282k
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,499
12
votes
7
answers
3k
views
Fastest square root of an arbitrary size
We do seem to have a fastest square root challenge, but it's very restrictive. In this challenge, your program (or function) will be given an arbitrarily sized nonnegative integer, which is the square ...
- 18.5k
-6
votes
1
answer
178
views
No. Of Factors Does the Number Have [duplicate]
Create a function which takes in a input integer and then returns the number of factors it has, like if you pass 25 then it will return ...
- 157
3
votes
0
answers
174
views
Sums of permutations of vectors [closed]
I am looking for a more efficient way of computing the following.
Let A and B be two vectors of non-negative integers of length <...
2
votes
1
answer
340
views
Crazy Blazin' DOM Injection
Introduction
This problem is a challenge that has to do with DOM manipulation at scale and overcoming some issues that may be inherent in dealing with the DOM.
This challenge is interesting because ...
- 153
9
votes
3
answers
532
views
Number of tilings on a triangular board with triangular tiles
Background
Consider the shape \$T(n)\$ consisting of a triangular array of \$\frac{n(n+1)}{2}\$ unit regular hexagons:
John Conway proved that \$n = 12k + 0,2,9,11\$ if and only if \$T(n)\$ can be ...
- 73.2k
11
votes
3
answers
557
views
Triangles in a tetrahedron
The goal of this challenge is to extend the OEIS sequence A334581.
Number of ways to choose \$3\$ points that form an equilateral triangle from the \$\binom{n+2}{3}\$ points in a regular tetrahedral ...
- 8,649
10
votes
1
answer
592
views
How quickly can you convert an NFA to a DFA?
Convert NFA to DFA as quickly as possible.
Input
Your input will be an NFA. In order to be able to test your code, it needs to be able to handle an NFA in the following format. This is taken ...
user9207
5
votes
0
answers
398
views
Hamming distance traveling salesman problem
The Hamming distance between two strings is the number of positions they differ at.
You are given a set of binary strings. The task is to find the length of the shortest route that visits all of them ...
- 8,415
20
votes
1
answer
751
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