# 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.

141 questions
Filter by
Sorted by
Tagged with
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 ...
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, ...
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 ...
574 views

### Block partition a string

Inspiration. Consider a list l, consisting of numbers. Define a block operation at index i on the list ...
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'...
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 ...
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 ...
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,...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
449 views

### Arbitrary Randomness (Speed edition)

Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
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 ...
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% ...
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 ...
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 ...
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 ...
532 views

### Biggest square in a grid [closed]

Challenge Given a grid like this, ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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, ...
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 ...
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: ...
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 ...
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 ...
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 ...