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
12
votes
1answer
811 views

Break the broken cipher

I have designed a simple random generator that cycles two numbers in a chaotic way using a multiply and modulus method. It works great for that. If I were to use it as a cipher generator it would ...
11
votes
7answers
944 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, ...
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 ...
11
votes
2answers
574 views

Block partition a string

Inspiration. Consider a list l, consisting of numbers. Define a block operation at index i on the list ...
11
votes
5answers
685 views

Fast Topswops calculation

From AZSPCS: Suppose you have a deck containing n cards. Each card contains a number from 1 to n, and each number appears on exactly one card. You look at the number on the top card -- let's says it'...
11
votes
3answers
478 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
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 ...
11
votes
1answer
705 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,...
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 ...
10
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 ...
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: ...
10
votes
4answers
590 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 ...
10
votes
2answers
518 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 ...
10
votes
3answers
664 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 ...
10
votes
16answers
11k views

Random sampling without replacement

Create a function that will output a set of distinct random numbers drawn from a range. The order of the elements in the set is unimportant (they can even be sorted), but it must be possible for the ...
10
votes
3answers
449 views

Arbitrary Randomness (Speed edition)

Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
10
votes
3answers
614 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 ...
10
votes
1answer
555 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% ...
10
votes
3answers
470 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 ...
10
votes
2answers
451 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
2answers
820 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
2answers
532 views

Biggest square in a grid [closed]

Challenge Given a grid like this, ...
10
votes
1answer
260 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 (...
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 ...
9
votes
2answers
456 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 ...
9
votes
4answers
2k views

Fast line drawing algorithm

The task is to find a way to draw a horizontal line in an array of 16-bit integers. We're assuming a 256x192 pixel array with 16 pixels per word. A line is a contiguous run of set (1) bits. Lines ...
9
votes
1answer
827 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 ...
9
votes
2answers
513 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 ...
8
votes
4answers
685 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 ...
8
votes
1answer
593 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 ...
8
votes
3answers
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 ...
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 ...
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 ...
7
votes
1answer
577 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 ...
7
votes
1answer
2k 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 ...
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 ...
7
votes
3answers
834 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 ...
7
votes
1answer
851 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 ...
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
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, ...
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 ...
6
votes
2answers
643 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 ...
6
votes
3answers
355 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, ...
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 ...
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: ...
6
votes
2answers
459 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 ...
6
votes
3answers
2k views

Lottery Ball Problem

A woman works at a lottery ball factory. She's instructed to open up a lottery ball creation kit composed of 1 red rubber ball and n strips of digits from 0 through 9. She's instructed to do the ...
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 ...
6
votes
3answers
632 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
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 ...