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
45
votes
3answers
3k 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 ...
8
votes
4answers
715 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 ...
52
votes
14answers
19k 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 ...
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 ...
10
votes
1answer
282 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 length such ...
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 ...
10
votes
4answers
644 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
635 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 ...
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 ...
10
votes
2answers
847 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 ...
6
votes
1answer
619 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
3answers
639 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 ...
12
votes
3answers
649 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...
18
votes
3answers
921 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 ...
6
votes
1answer
2k views

Optimal Minesweeper on the Largest Board

Overview: Your challenge is to write a program that will play minesweeper optimally, giving the best move in any position. Moreover, you must do this on the largest board possible. Game details: ...
29
votes
2answers
14k views

Fastest semiprime factorization

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: ...
6
votes
3answers
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, ...
-4
votes
2answers
163 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 ...
10
votes
12answers
4k views

Write the fastest Fibonacci

This is yet another challenge about the Fibonacci numbers. The goal is to compute the 20'000'000th Fibonacii number as fast as possible. The decimal output is about 4 MiB large; it starts with: ...
13
votes
3answers
874 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....
1
vote
1answer
317 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 ...
6
votes
3answers
852 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 ...
17
votes
3answers
18k 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 ...
7
votes
1answer
884 views

'Number' Crunching Benchmark

I just want to do some benchmarking of different programming languages. So here is a tip: You can use as many characters as you want. In the end there is only the time your program needed. So, here ...
11
votes
8answers
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 ...
2
votes
0answers
120 views

Write program which finds shortest expression for number [duplicate]

Write program which finds shortest expression for big integer. Expression may consist of + - * / ^ ! ( ) operations. ! stands ...
2
votes
2answers
1k views

Find nth root of variable without using math operators/functions

Write a program which, given two positive integers n and x, will display the n-th root of x (which is also x1/n) in decimal to an accuracy of 0.00001. The program must output the resulting number in ...
0
votes
1answer
263 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 ...
1
vote
4answers
291 views

Creating a catalogue index

You have a program which creates an index for a catalogue. The last step is missing: it must find and consolidate page ranges within the list of pages for each entry. Each entry is currently an ...
6
votes
3answers
1k views

Super fast sampling from a tricky random distribution

This is a micro-optimization challenge. The task is to sample from the maximally skewed stable distribution F(x;1,-1,Pi/2,0). See Table 1 of http://arxiv.org/pdf/0908.3961v2.pdf . It is easiest to ...
7
votes
2answers
464 views

Filter a large file in small memory

The challenge is a follow-up to Filter a large file quickly which had two submissions where were as fast as wc! This time the difficulty is that RAM is severely restricted which means that new ...
2
votes
2answers
210 views

Merging text files based on a prefix key

Imagine an ordered file set : file1, file2, ... fileN. Each file is a textual file that is ...
5
votes
2answers
716 views

Analysing the most common words in a text, and replacing them with a single byte

This is a very crude text encoding algorithm I came up with the other day. It won't work if the text has more than 256 different characters in it – but it does support Unicode, at least in my Python ...
10
votes
3answers
691 views

Quickly divide in Manufactoria

Background Manufactoria has been marketed as a game, but we code-golfers can see it for what it really is: a two-dimensional programming language. The Manufactoria programming language is based ...
7
votes
7answers
2k views

Enumerate all number that are palindromic in at least two of base 2, 8, 10, 16 or 64

Multi palindromic numbers Finding all number for which at least two** representation are palindromic, with more than one** characters, if in decimal, octal, hexadecimal, binary or in base64. ** have ...
5
votes
2answers
3k views

Fastest modular exponentiation

The challenge is to write code in any open source, available on linux, language of your choice to perform modular exponentiation. The input will be two randomly chosen 2048 bit positive integers ...
19
votes
2answers
1k views

The number of possible numeric outcomes of parenthesizations of 2^2^…^2

Consider an expression 2^2^...^2 with n operators ^. Operator ...
4
votes
2answers
509 views

List ALL prime-factorized natural numbers in ANY order

This is a variant of List prime-factorized natural numbers up to N in ascending order, but the solutions can be very different. Write a program that outputs prime factorizations of all natural ...
14
votes
2answers
2k views

Fastest python code to find a set of winning words in this game

This is a word game from a set of activity cards for children. Below the rules is code to find the best triplet using /usr/share/dict/words. I thought it was an interesting optimization problem, and ...
1
vote
4answers
547 views

Race to a Million

This falls under the Code puzzles the best. Fastest way to render the numbers 1-million in a web browser. Preferably using PHP, but use what you must. Numbers must be more than one on a line in the ...
4
votes
3answers
4k views

Secret Santa Challenge [duplicate]

Possible Duplicate: Holiday Gift Exchange Background: Secret Santa is a Western Christmas tradition in which members of a group or community are randomly assigned a person to whom they ...
2
votes
2answers
422 views
6
votes
1answer
2k views

Sudoku board generator

A program that randomly generates a Sudoku game board with varying degrees of difficulty (however you decide to measure difficulty). Sudoku requires that there is only one solution, so your program ...