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.
148
questions
1
vote
0answers
15 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\$ ...
13
votes
6answers
573 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 ...
1
vote
3answers
277 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\...
30
votes
17answers
6k 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
721 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
509 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 ...
12
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 ...
18
votes
2answers
646 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
279 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
621 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
328 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 ...
22
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 ...
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....
4
votes
1answer
294 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
201 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
735 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 ...
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
464 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
329 views
Find arrays with distinct subarray sums
Consider an array A of length n. The array contains only integers in the range 1 to ...
9
votes
1answer
836 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 ...
0
votes
5answers
495 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
491 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
584 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 ...
16
votes
1answer
342 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
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 ...
9
votes
2answers
526 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
572 views
7
votes
3answers
914 views
The Missing Number - Version 2
Background:
This question is a remix of the one that I made previously on this forum. The only difference with this one is: the range is significantly larger, AND dynamic. Details below!
Also, I'm ...
22
votes
3answers
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 ...
22
votes
9answers
2k views
Build an Electrical Grid
The Challenge
There are N cities aligned in a straight line. The i-th city is located A[i] kilometers to the right of the origin. No two cities will be in the same ...
6
votes
3answers
360 views
Primitive roots density of number
Definition:
A number m is called a primitive root of a prime p the condition that the smallest integer k for which p dividies mk-1 is p-1
Your task
Given a tuple (a,b) of positive integers, ...
11
votes
7answers
951 views
Count arrays of periods
The period of a string is the shortest non-zero shift so that the string matches itself, ignoring any parts that overhang. So for example, ...
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 ...
3
votes
1answer
1k views
remove duplicates from array [closed]
You have given an array from which we need to remove duplicates.
Rules:
First or immediate duplicates gets removed first.
Array contains natural numbers ...
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 ...
20
votes
4answers
653 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....
2
votes
2answers
230 views
Tips for Fastest Code challenges [closed]
What general tips do you have for how to answer fastest-code challenges?
Please post one tip per answer.
The objective of these challenges is to make the program that will run in the least amount of ...
10
votes
2answers
464 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 ...
10
votes
1answer
557 views
Roll to see all sides!
Let's say you have a 20-sided die. You start rolling that die and have to roll it a few dozen times before you finally roll all 20 values. You wonder, how many rolls do I need before I get a 50% ...
14
votes
12answers
1k views
Finding approximate correlations
Consider a binary string S of length n. Indexing from 1, we can compute the Hamming ...
13
votes
4answers
406 views
Fastest Approximate Common Divisor
Overview
In this challenge, you will be given two numbers which are both a small offset larger than a multiple of a medium-size number. You must output a medium-sized number that is almost a divisor ...
9
votes
5answers
1k views
Count the number of Hamming distance sequences
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 ...
13
votes
2answers
998 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 ...
-5
votes
1answer
170 views
Google search result short summary [closed]
Intro
When you search in google, it always shows you a result with a sample text from the found webpage.
For example if you search for "Madonna greatest vinyl", google will show you one line link, ...
1
vote
0answers
285 views
Generalization of Eight Queen Puzzle [closed]
Here's one generalized version of the famous Eight Queen's Puzzle:
Given an n Ć n chess board, and an integer ...
23
votes
5answers
944 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 ...
9
votes
2answers
459 views
The Tax Historian
Introduction
There is a tax collector that has some trouble managing the taxes of his kingdom: the historical records have burnt down in a great fire.
He wants to find out how many possible pasts ...
26
votes
2answers
1k views
Fastest Mini-Flak Quine
Mini-Flak is a subset of the Brain-Flak language, where the <>, <...> and [] ...
