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
-5
votes
1answer
172 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
290 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
956 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
482 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 [] ...
13
votes
1answer
346 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 ...
28
votes
9answers
4k 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
395 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
4k 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
695 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
749 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
549 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
1k 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
299 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 ...
70
votes
13answers
11k 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
712 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
281 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
2k 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
843 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 ...
14
votes
7answers
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 ...
7
votes
1answer
3k 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 ...
-5
votes
3answers
681 views

Solve the Diophantine Pell equation

Given a natural number c as input, our task is finding the fastest way to calculate one -atleast- availabe integer solution (a,b) of pell equation c=a²-b². Rules Built-in functions and loopholes ...
10
votes
4answers
642 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 ...
6
votes
3answers
634 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 ...
6
votes
1answer
615 views

Compute 30000 Digits of Pi (π), as Fast as Possible [duplicate]

Compute 30000 digits of the mathematical constant π, with the fastest code. Implement in any computer programming language that I can run in my 64 bit Linux machine. You should provide your compiler ...
10
votes
2answers
846 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 ...
10
votes
5answers
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 ...
47
votes
2answers
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 ...
10
votes
3answers
638 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 ...
1
vote
0answers
40 views

Searching for a sum [duplicate]

In this challenge you will take two inputs One input will be a string of numbers of any length which you will put into an array/table/whatever you call it in your language Ex: ...
11
votes
4answers
2k views

Magic Sequences of length n

A magic sequence is a sequence of non-negative integers x[0..n-1] such that there are exactly x[i] instances of ...
10
votes
3answers
498 views

Count balanced binary strings matching any of a set of masks

A binary string is a string which contains only characters drawn from 01. A balanced binary string is a binary string which contains exactly as many 0​s as 1​s. You are given a positive ...
12
votes
3answers
648 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...
11
votes
1answer
806 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,...
18
votes
3answers
920 views

Finding all-but-one matches

This challenge is about writing code to solve the following problem. Given two strings A and B, your code should output the start and end indices of a substring of A with the following properties. ...
5
votes
7answers
4k views

Fastest array-by-array nearest neighbour search

Intro - Nearest neighbour comparison between two arrays is something that can be done very efficiently when only 1 variable per array is involved, because it can be done by sorting and then performing ...
5
votes
2answers
808 views

Coding a recursive function for highest possible input

Challenge You are given the following function:- which is the same as:- with the base cases q(r, b, L) = 1 whenever r ≤ L, q(r, 0, L) = 0, if r > L and q(r, 0, L) = 1, if r ≤ L. Your task is to ...
20
votes
2answers
559 views

Forming Polyominoes with a Chain of Rods

Background Consider a (closed) chain of rods, each of which has integer length. How many distinct hole-free polyominoes can you form with a given chain? Or in other words, how many different non-self-...
-4
votes
2answers
162 views

Magical Squares [closed]

A perfect square is a number that is the square of an integer. However, let's define something called a Magical Square, which is a perfect square with the following restriction: The perfect square ...
1
vote
1answer
316 views

Chotchkies Restaurant [duplicate]

Because there isn't enough xkcd on PPCG... Challenge The challenge is the same as above - given a menu and a total price, you need to find what the customer ordered. The menu will be supplied as a ...
13
votes
3answers
873 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....
7
votes
4answers
4k views

Un-hash the Java Hash

Hash Un-hashing The basic goal of this challenge is to exploit the high probability of collision in the Java Hash function to create a list of plausible inputs that created an outputted hash. The ...
12
votes
6answers
551 views

False Positives on an Integer Lattice

Leaderboard ...
13
votes
8answers
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 ...
6
votes
3answers
2k views

Another Euler Brick in the Wall

A Euler Brick is a cuboid where the length of all the edges are integers and all of the diagonals of the faces are integers as well. All sides must also be different. Your program has to find as many ...
6
votes
3answers
850 views

The distance between circles

Imagine you are given two lists of numbers which are to be interpreted as points on a circle of circumference 1000. Let us say ...
7
votes
2answers
1k views

2nd byte bias of RC4

Short version RC4, designed in 1987, is one of the most famous stream ciphers. This question asks you to practically demonstrate its 2nd byte bias (for a ...