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.

Filter by
Sorted by
Tagged with
337 votes
42 answers
314k 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....
3 votes
4 answers
603 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 ...
9 votes
5 answers
1k 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 ...
2 votes
2 answers
219 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 ...
20 votes
7 answers
3k 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 ...
6 votes
5 answers
741 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 ...
14 votes
5 answers
827 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 ...
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 [...] ...
5 votes
4 answers
587 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 ...
11 votes
3 answers
572 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 ...
14 votes
2 answers
1k views

Count how many distance sequences are far from all others

The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. Let P be a binary string of ...
53 votes
4 answers
2k views

Extending OEIS: Counting Diamond Tilings

I promise, this will be my last challenge about diamong tilings (for a while, anyway). On the bright side, this challenge doesn't have anything to do with ASCII art, and is not a code golf either, so ...
37 votes
12 answers
6k views

Find the largest prime whose length, sum and product is prime

The number 113 is the first prime whose length 3 is prime, digital sum 5 = 1 + 1 + 3 is ...
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 ...
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 ...
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 ...
14 votes
9 answers
1k views

Find the maximum determinant for each size Toeplitz matrix

For a fixed n, consider the n by n Toeplitz matrices with entries which are either 0 or 1. The aim is to find maximum determinant over all such Toeplitz matrices. Task For each ...
10 votes
19 answers
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 ...
35 votes
11 answers
8k views

How high can you go? (A coding+algorithms challenge)

Now that everyone has developed their (often amazing) low level coding expertise for How slow is Python really? (Or how fast is your language?) and How Slow Is Python Really (Part II)? it is time for ...
74 votes
16 answers
15k 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 ...
11 votes
5 answers
618 views

Arbitrary Randomness (Speed edition)

Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
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, ...
23 votes
4 answers
3k views

The Missing Number Revised

Background: I originally posted this question last night, and received backlash on its vagueness. I have since consulted many personnel concerning not only the wording of the problem, but also its ...
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 ...
6 votes
4 answers
411 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 ...
28 votes
3 answers
1k views

Delete some bits and count

Consider all 2^n different binary strings of length n and assume n > 2. You are allowed ...
7 votes
6 answers
5k views

Carmichael Numbers

Write a program to print Carmichael numbers. The challenge is to print the maximum number of them in less than 5 secs. The numbers should be in increasing order. Please do not use built in functions. ...
11 votes
3 answers
603 views

Compute OEIS A005434

The task is to compute OEIS A005434 as quickly as possible. Consider a binary string S of length n. Indexing from ...
21 votes
4 answers
23k views

Fastest code to find the next prime

The problem is as follows. Input: An integer n Output: The smallest prime bigger than n. The challenge is to give the ...
23 votes
6 answers
1k views

Fastest Home Prime Generator

What is a home prime? For an example, take HP(4). First, find the prime factors. The prime factors of 4 (in numerical order from least to greatest, always) are 2, 2. Take those factors as a literal ...
19 votes
13 answers
868 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 ...
16 votes
2 answers
421 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
9 answers
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 ...
0 votes
1 answer
337 views

Find the fastest swim relay (shortest path of unique nodes and types)

fastest relay time = lowest possible total integer value of (a freestyle swimmers time) + (1 breastroke swimmers time) + (another backstroke swimmers time) + (another butterfly swimmers time) Each ...
2 votes
11 answers
8k views

compute number of 1 bits in a binary representation of a number

The goal is to write a program that returns number of 1 bits in a given number. Examples 5 -> 2 1254 -> 6 56465 -> 8 Winner The winning ...
6 votes
3 answers
567 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 ...
8 votes
2 answers
741 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 ...
9 votes
4 answers
592 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, ...
22 votes
3 answers
847 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\$ ...
0 votes
1 answer
273 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, ...
20 votes
1 answer
760 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 ...
36 votes
19 answers
10k 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 ...
10 votes
5 answers
611 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 ...
11 votes
3 answers
661 views

Tic-tac-toe with only crosses as quick as possible

As per Luke's request and Peter Taylor's addition to this challenge. Introduction Everyone knows the game tic-tac-toe, but in this challenge, we are going to introduce a little twist. We are only ...
14 votes
9 answers
942 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, ...
26 votes
3 answers
2k 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
5 answers
838 views

Counting orthogonal circulant matrices

Two rows of a matrix are orthogonal if their inner product equals zero. Call a matrix with all rows pairwise orthogonal an orthogonal matrix. A circulant matrix is one where each row vector is rotated ...
4 votes
5 answers
327 views

Reproportioning a population by adding fixed sized groups

Introduction Say you have a population of people. This population is made up of 100 Alices and 25 Bobs. So, 80% of the population are Alices and 20% are Bobs. We want to change the proportional ...
8 votes
4 answers
367 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 ...
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 ...

1
2 3 4 5