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
37 votes
4 answers
18k 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: \$...
Soham Chowdhury's user avatar
153 votes
21 answers
112k views

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

I have this code which I have written in Python/NumPy ...
user avatar
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 ...
Liam's user avatar
  • 3,205
54 votes
14 answers
20k views

How Slow Is Python Really (Part II)?

This is a follow up to How slow is Python really? (Or how fast is your language?). It turns out it was a bit too easy to get a x100 speedup for my last question. For those who have enjoyed the ...
user avatar
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 ...
ardnew's user avatar
  • 2,329
9 votes
4 answers
2k views

Counting k-mers

The task is to count the number of distinct substrings of length k, for k = 1,2,3,4,..... Output You should output one line per k you manage to complete with one ...
user avatar
-7 votes
3 answers
1k views

write a code the find n-th number of Gray Code list [closed]

Write a function that, given N >= 0, finds the Nth number in a standard Gray code. Example input: 1 2 3 4 Example output: ...
mohammad shamsi's user avatar
337 votes
42 answers
315k 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....
Omer Tuchfeld's user avatar
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 ...
Martin Ender's user avatar
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 ...
Calvin's Hobbies's user avatar
30 votes
9 answers
5k 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 ...
user avatar
17 votes
3 answers
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 ...
user avatar
15 votes
5 answers
3k views

Fastest Sort in BrainF***

After having implemented QuickSort in BrainF***, I realized it probably wasn't that quick. Operations that are O(1) in normal languages (like array indexing) are significantly longer in BF. Most of ...
AShelly's user avatar
  • 4,631
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
10 votes
5 answers
1k views

Calculate a probability exactly and quickly

[This is a partner question to Calculate a probability exactly ] This task is about writing code to compute a probability exactly and quickly. The output should be a precise probability written as a ...
user avatar
6 votes
3 answers
2k views

The making of "Spot It!": Finding almost unique sets

Puzzle: Find a deck of c cards, each containing p pictures, such that no two pictures match on a given card, and exactly 1 picture on each card matches exactly 1 picture on each of the other cards, ...
Edward Brey's user avatar
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 ...
Ali1S232's user avatar
  • 425
45 votes
3 answers
4k views

Help Indiana Jones to get the treasure

Story Indiana Jones was exploring a cave where a precious treasure is located. Suddenly, an earthquake happened. When the earthquake ended, he noticed that some rocks that had fallen from the ...
JiminP's user avatar
  • 3,472
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 ...
Asad-ullah Khan's user avatar
36 votes
12 answers
18k 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 ...
maxb's user avatar
  • 6,847
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 ...
user avatar
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 ...
user avatar
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 ...
Noah L's user avatar
  • 861
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 ...
TheProgrammer's user avatar
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 ...
AnttiP's user avatar
  • 7,848
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 ...
user avatar
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 ...
Peter Kagey's user avatar
  • 8,659
20 votes
9 answers
21k views

Super speedy totient function

The goal is simple: calculate the totient function for as many numbers as you can in 10 seconds and sum the numbers. You must print your result at the end and you must actually calculate it. No ...
qwr's user avatar
  • 12.1k
20 votes
4 answers
705 views

Plant trees in a park - As fast as you can!

This challenge is inspired by this app. The test cases are borrowed from that app. This is a fastest-code challenge, where the objective is to solve the largest test cases in the least amount of time....
Stewie Griffin's user avatar
14 votes
8 answers
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 ...
user avatar
14 votes
12 answers
1k views

Finding approximate correlations

Consider a binary string S of length n. Indexing from 1, we can compute the Hamming ...
user avatar
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 ...
user avatar
13 votes
8 answers
2k views

Filter a large file quickly

The challenge is to filter a large file quickly. Input: Each line has three space separated positive integers. Output: All input lines A ...
user avatar
13 votes
3 answers
678 views

Count the number of Hankelable matrices

Background A binary Hankel matrix is a matrix with constant skew-diagonals (positive sloping diagonals) containing only 0s and 1...
user avatar
13 votes
3 answers
903 views

Be an Epidemiologist!

Challenge You must create a simple model of how disease spreads around a group of people. Rules and Requirements The model must be a 1000 by 1000 2D array with each element being a different person....
Beta Decay's user avatar
  • 23.3k
13 votes
4 answers
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 ...
user avatar
11 votes
1 answer
932 views

Constructing an Orthogonal-Diagonal Greco-Latin Square

Consider a grid of NxN unique elements. Each element has a letter (from A to the Nth letter,...
Nathan Merrill's user avatar
11 votes
3 answers
560 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 ...
Peter Kagey's user avatar
  • 8,659
10 votes
2 answers
814 views

Biggest square in a grid [closed]

Challenge Given a grid like this, ...
NL628's user avatar
  • 723
10 votes
3 answers
696 views

Supersonic domino tilings

Task Write a program that reads three integers m, n either from STDIN or as command-line arguments, prints all possible tilings of a rectangle of dimensions m × n by 2 × 1 and 1 × 2 dominos and ...
Dennis's user avatar
  • 210k
10 votes
2 answers
937 views

Probabilities - how high can you go?

I previously asked a question for how to compute a probability quickly and accurately. However, evidently it was too easy as a closed form solution was given! Here is a more difficult version. This ...
user avatar
10 votes
4 answers
701 views

Too many pawns on a chess board

Given an integer 2n, find the number of possible ways in which 2n^2 black pawns and 2n^2 white pawns can be arranged on a 2n by 2n chess board such that no pawn attack another. A black pawn can ...
Agnishom Chattopadhyay's user avatar
8 votes
3 answers
1k views

List prime-factorized natural numbers up to N in ascending order

For a given n list prime factorization of all natural numbers between 1 and n in ascending ...
Petr's user avatar
  • 4,372
7 votes
1 answer
4k views

Snakes and Ladders probability of winning

(This is my first Q here, and I don't know much about code golfing.) Your aim is to predict the winner of an ongoing Snakes and Ladders game. INPUT A single number (2-1000) indicating the number of ...
ghosts_in_the_code's user avatar
7 votes
3 answers
676 views

Covering Array Validator

A covering array is an N by k array in which each element is one of {0, 1, ..., v-1} (so v ...
Ryan Dougherty's user avatar
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. ...
fR0DDY's user avatar
  • 4,579
6 votes
4 answers
15k 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 ...
PriestVallon's user avatar
5 votes
2 answers
667 views

Find arrays with distinct subarray sums

Consider an array A of length n. The array contains only integers in the range 1 to ...
user avatar