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.
23
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
387 views
Arbitrary Randomness (Speed edition)
Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
4
votes
2answers
254 views
Find arrays with distinct subarray sums
Consider an array A of length n. The array contains only integers in the range 1 to ...
7
votes
1answer
752 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
4answers
429 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
456 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
561 views
Block partition a string
Inspiration.
Consider a list l, consisting of numbers. Define a block operation at index i on the list ...
23
votes
2answers
921 views
Delete some bits and count
Consider all 2^n different binary strings of length n and assume n > 2. You are allowed ...
14
votes
1answer
290 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 with their indices) fall on a polynomial of degree k.
That is,
No ...
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
485 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
456 views
7
votes
3answers
571 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
2k 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 ...
23
votes
9answers
1k 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
352 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, ...
12
votes
7answers
932 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 ...
16
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
587 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
186 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
429 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
542 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
372 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 ...
10
votes
5answers
854 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 ...
14
votes
2answers
942 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
166 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
214 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 ...
22
votes
5answers
854 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
446 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 ...
25
votes
2answers
1k views
Fastest Mini-Flak Quine
Mini-Flak is a subset of the Brain-Flak language, where the <>, <...> and [] ...
14
votes
1answer
302 views
Read a crossword with a twist!
Similar to this question, but this is a crossword variation!
Instead of only one letter per grid square, you can have one or two.
Input:
A 2d array, or whatever works in your language.
You can ...
26
votes
9answers
3k 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 ...
6
votes
1answer
362 views
Help the poor Cryptographers - DLP Edition
Introduction and Motivation
I'm mainly active on Cryptography.SE and as such have already stumbled across the question: "How the hell am I supposed tools like cado-nfs to do stuff!?". They are super-...
2
votes
5answers
2k 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
...
24
votes
2answers
2k views
Compute the maximum number of runs possible for as large a string as possible
[This question is a follow up to Compute the runs of a string ]
A period p of a string w is any positive integer ...
16
votes
3answers
546 views
Find all the Solutions to this Number Puzzle in the Shortest Time Possible
History
My company sends out a weekly newsletter to everyone within the company. Included in these newsletters is a riddle, along with a shoutout to whomever in the company was the first to email/...
14
votes
3answers
717 views
Quickly express a number with only 0-9 and the four operations, plus one more extra
Explanation
Befunge is a two-dimensional program that uses stacks.
That means, to do 5 + 6, you write 56+, meaning:
...
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 ...
10
votes
2answers
508 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 ...
6
votes
2answers
922 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 ...
3
votes
5answers
295 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 ...
62
votes
13answers
8k 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
4answers
638 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 ...
10
votes
1answer
257 views
Set Theoretic Arithmetic (+ and *) [closed]
Set Theoretic Arithmetic
Premise
There have been a couple challenges already that involve multiplying without the multiplication operator ( here and here ) and this challenge is in the same vein (...
11
votes
2answers
1k views
Fastest Longest Common Subsequence Finder
Your task is to solve the Longest Common Subsequence problem for n strings of length 1000.
A valid solution to the LCS problem for two or more strings S1, … Sn is any string T of maximal ...
15
votes
8answers
792 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, ...
19
votes
12answers
3k views
Sum of smallest prime factors
SF(n) is a function which computes the smallest prime factor for a given number n.
We'll call T(N) the sum of every SF(n) with 2 <= n <= N.
T(1) = 0 (the sum is over 0 summands)
T(2) = 2 (2 ...
