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.
173
questions
6
votes
1answer
404 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 ...
6
votes
3answers
336 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 ...
4
votes
3answers
292 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 ...
16
votes
2answers
338 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^...
20
votes
12answers
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 ...
-1
votes
1answer
129 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 ...
7
votes
3answers
341 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 ...
5
votes
1answer
280 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 ...
27
votes
0answers
707 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 [...] ...
2
votes
0answers
217 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 ...
10
votes
4answers
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 (...
40
votes
7answers
4k 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....
10
votes
7answers
2k 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 ...
-6
votes
1answer
149 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 ...
3
votes
0answers
159 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
1answer
305 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 ...
8
votes
3answers
478 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 ...
11
votes
3answers
488 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 ...
9
votes
1answer
501 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 ...
4
votes
0answers
274 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 ...
18
votes
0answers
488 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 ...
11
votes
2answers
395 views
Spanning paths in a tournament on n nodes
The goal of this challenge is to extend the On-Line Encyclopedia of Integer Sequences (OEIS) sequence A038375.
Maximal number of spanning paths in tournament on n nodes.
A tournament on \$n\$ ...
15
votes
6answers
708 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 ...
3
votes
3answers
330 views
Generate A298757 [closed]
Miller-Rabin test
Given a base \$b\$ and an odd number \$n\$:
Write \$n\$ as \$2^{s}\times d + 1\$ where \$d\$ is odd
\$n\$ is a strong probable prime if either:
\$b^d\equiv 1 \pmod n\$
\$b^{d\cdot2^...
32
votes
18answers
7k 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 ...
26
votes
4answers
826 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 ...
7
votes
1answer
557 views
Average number of strings with Levenshtein distance up to 4
This is a version of this question which should not have such a straightforward solution and so should be more of an interesting coding challenge. It seems, for example, very likely there is no easy ...
13
votes
4answers
2k views
Can you calculate the average Levenshtein distance exactly?
The Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions to convert one string into the other one.
The challenge is to compute ...
21
votes
2answers
707 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\$ ...
-1
votes
1answer
139 views
Symbol Search Deleter [rephrased] [closed]
Your challenge is to parse nonsensical text and output a "congruous phrase" - which I shall define here to be text with any contiguous characters in between, and including, a given set of like symbols ...
-5
votes
2answers
349 views
Fastest N times Hello World (Java/C/ C++) [closed]
Not a new one:
Input
N, being n, 0 ≤ n ≤ 5.
Output
N times "Hello World."
Example:
Input
3
Output
Hello World.
Hello World.
Hello World.
These 2 are my ...
8
votes
1answer
664 views
Compute OEIS A161169, approximately and quickly
\$T(n, k)\$ gives the number of permutations of length \$n\$ with up to \$k\$ inversions. This values grows very quickly, for example for \$T(20, 100) = 1551417550117463564\$.
The maximum number of ...
5
votes
1answer
347 views
Find minimal set of rows to retain all unique values in each column
Given a matrix, the goal is to ensure all the values in each column occur at least once, while at the same time doing so requiring the least possible amount of rows. Fastest solution wins.
Note: a ...
29
votes
11answers
10k 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 ...
36
votes
17answers
7k 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....
5
votes
1answer
405 views
Multiplication in Brainfuck - minimum number of evaluations [closed]
Given two numbers in tape location #0 and tape location #1 in Brainfuck, compute their product into another tape location (specify with answer). Optimize for the least amount of time-units used, where ...
8
votes
0answers
224 views
Fastest way to iterate over sublattice of discrete lattice
I need to construct a functor that iterates over the linear representation of a sub-lattice of size \$d_x,d_y,d_z,d_q\$ embedded in a lattice of size \$n_x,n_y,n_z,n_q\$. The sub-lattice corner is ...
6
votes
2answers
853 views
Check if all vowels exist in pairs of strings [closed]
Your program should find the number of string pairs (pairs of 2) that contain all vowels (a e i o u), when given an integer N and ...
26
votes
6answers
1k 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 ...
11
votes
3answers
499 views
Arbitrary Randomness (Speed edition)
Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
5
votes
2answers
577 views
Find arrays with distinct subarray sums
Consider an array A of length n. The array contains only integers in the range 1 to ...
10
votes
1answer
899 views
Count arrays that are really unique
This is a follow up to Count arrays that make unique sets . The significant difference is the definition of uniqueness.
Consider an array A of length ...
-1
votes
5answers
534 views
Fastest algorithm to output array containing all integers in range excluding duplicate digits
Input is a single integer in ascending digit order.
The only valid inputs are:
12
123
1234
...
11
votes
3answers
531 views
Count arrays that make unique sets
This question has a similar set up to Find an array that fits a set of sums although is quite different in its goals.
Consider an array A of length ...
11
votes
2answers
611 views
Block partition a string
Inspiration.
Consider a list l, consisting of numbers. Define a block operation at index i on the list ...
27
votes
2answers
1k views
Delete some bits and count
Consider all 2^n different binary strings of length n and assume n > 2. You are allowed ...
16
votes
1answer
364 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 ...
12
votes
7answers
2k views
Calculate the Hafnian as quickly as possible
The challenge is to write the fastest code possible for computing the Hafnian of a matrix.
The Hafnian of a symmetric 2n-by-2n ...
9
votes
2answers
591 views
How many draws are there in Quarto?
Introduction
This challenge is similar to Project Euler problems. I came up with it because I was playing a deceivingly simple board game and couldn't come up with an efficient solution to answer a ...
10
votes
2answers
693 views
