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.

Filter by
Sorted by
Tagged with
8
votes
3answers
362 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 ...
8
votes
3answers
343 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 ...
8
votes
1answer
343 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 ...
15
votes
0answers
285 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 ...
4
votes
0answers
166 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 ...
11
votes
2answers
355 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\$ ...
14
votes
6answers
603 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 ...
30
votes
17answers
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 ...
25
votes
4answers
751 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 ...
2
votes
3answers
293 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\...
29
votes
16answers
4k 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....
23
votes
8answers
4k 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 ...
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 ...
7
votes
1answer
520 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 ...
8
votes
0answers
414 views

Write a FAST word equation solver

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. ...
19
votes
2answers
659 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
132 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
287 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 ...
70
votes
13answers
11k 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 ...
8
votes
1answer
628 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
330 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 ...
0
votes
5answers
500 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 ...
4
votes
1answer
301 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 ...
7
votes
0answers
203 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 ...
20
votes
2answers
559 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-...
6
votes
2answers
750 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
2answers
1k views

Fastest Mini-Flak Quine

Mini-Flak is a subset of the Brain-Flak language, where the <>, <...> and [] ...
16
votes
1answer
345 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 ...
27
votes
2answers
1k 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 ...
9
votes
1answer
855 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 ...
6
votes
3answers
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 ...
2
votes
2answers
870 views

Fastest C/C++ comparison function for an opaque field containing doubles

Description: Write the fastest comparison function for an opaque field containing a double. Here is my example: ...
5
votes
4answers
14k views

Solve the Magic Hexagon [closed]

A magic hexagon is a hexagon where every row and every diagonal add up to the same value. In this case the value is 38. Each number from 1 to 19 must be used exactly once. This image shows a solution ...
25
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 ...
10
votes
3answers
483 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
453 views

Find arrays with distinct subarray sums

Consider an array A of length n. The array contains only integers in the range 1 to ...
11
votes
3answers
513 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 ...
17
votes
5answers
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 ...
6
votes
2answers
1k views

Find the longest path, avoiding obstacles in a 2D plane

The Scenario You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can ...
22
votes
8answers
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 ...
151
votes
21answers
108k views

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

I have this code which I have written in Python/NumPy ...
15
votes
8answers
843 views

Integral triangles and integral medians

Consider a triangle ABC where each side has integer length (an integral triangle). Define a median of ABC to be a line segment from a vertex to the midpoint of the opposing side. In the figure below, ...
13
votes
8answers
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 ...
11
votes
2answers
601 views

Block partition a string

Inspiration. Consider a list l, consisting of numbers. Define a block operation at index i on the list ...
26
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 ...
12
votes
8answers
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 ...
2
votes
5answers
4k views

The fastest square root calculator

Write a program which outputs the square root of a given number in the shortest time possible. Rules It may not use any builtins or powering with non-integers. Input format as a function argument ...
28
votes
9answers
4k 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 ...
16
votes
5answers
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, ...
6
votes
5answers
1k views

Code-Challenge: Farey sequence (II)

Challenge In this task you would be given an integer N (less than 10^6), output the number of terms in the Farey sequence of order N. The input N < 106 is given in a single line, the inputs ...