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
73
votes
15answers
13k 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 ...
22
votes
2answers
750 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\$ ...
43
votes
8answers
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....
30
votes
11answers
11k 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 ...
9
votes
1answer
503 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 ...
6
votes
1answer
416 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 ...
16
votes
2answers
339 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^...
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
3answers
344 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 ...
29
votes
0answers
732 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 [...] ...
37
votes
4answers
16k 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: \$...
4
votes
3answers
295 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 ...
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 ...
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....
18
votes
6answers
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 ...
-1
votes
1answer
135 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 ...
5
votes
1answer
282 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 ...
7
votes
3answers
344 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 ...
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 ...
2
votes
0answers
220 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 (...
6
votes
1answer
2k views

Sudoku board generator [closed]

A program that randomly generates a Sudoku game board with varying degrees of difficulty (however you decide to measure difficulty). Sudoku requires that there is only one solution, so your program ...
4
votes
3answers
2k views

Fastest python implementation of multiplication table

I'd be interested to see who can come up with the fastest function to produce multiplication tables, in the following format: ...
3
votes
1answer
831 views

Box Blur Challenge

The challenge is to implement a box blur in any language. The input will be as a 32-bit uncompressed bitmap, BGRA, preceded by one byte defining the radius of the blur and one byte defining the width ...
3
votes
1answer
503 views

Fastest alphabetical list sort given the following limitations:

Your function must have an input that takes in an array containing 10000 random names, and must sort these names in alphabetical order. Names have a random length of up to 128 characters. ISO/IEC 8859-...
8
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 ...
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 ...
11
votes
3answers
491 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
votes
18answers
1k views

Square-free semiprime counting

Definition A square-free semiprime is a natural number that is the product of two distinct prime numbers. The task Given a natural number n, count all square-free ...
13
votes
5answers
743 views

Fast Topswops calculation

From AZSPCS: Suppose you have a deck containing n cards. Each card contains a number from 1 to n, and each number appears on exactly one card. You look at the number on the top card -- let's says it'...
-6
votes
1answer
151 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
306 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 ...
17
votes
3answers
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 ...
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 ...
18
votes
0answers
494 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
276 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
396 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
711 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 ...
27
votes
4answers
832 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 ...
3
votes
3answers
331 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^...
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 ...
6
votes
1answer
559 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 ...
9
votes
0answers
480 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. ...
-1
votes
1answer
141 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 ...
-1
votes
5answers
535 views
5
votes
1answer
407 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 ...