This challenge is intended to be solved by using, creating, or resolving some processing algorithm.
56
votes
23answers
6k views
Contest: fastest way to sort a big array of Gaussian-distributed data
Following the interest in this question, I thought it would be interesting to make answers a bit more objective and quantitative by proposing a contest.
The idea is simple: I have generated a binary ...
39
votes
23answers
5k views
Implement Sleep Sort
Sleep Sort is an integer sorting algorithm I found on the Internet. It opens an output stream, and for each input numbers in parallel, delay for the number seconds and output that number. Because of ...
30
votes
2answers
1k views
Help Indiana Jones to get the treasure
Story
Indiana Jones was exploring a cave where a precious treasure is located. Suddenly, an earthquake was happen.
When the earthquake was ended, he noticed that some rocks fell from the ceiling ...
19
votes
6answers
703 views
Shortest common superstring
Given a list of strings s_0, s_1, ..., s_n find the shortest string S that contains each of s_0, s_1, ..., s_n as a substring.
Examples:
S('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', ...
17
votes
45answers
2k views
Find the Factorial
Create the shortest function that finds the factorial of a positive number.
The factorial is found by multiplying a number by each of the digits that lead up to it.
5! = 5 * 4 * 3 * 2 * 1 = 120
...
16
votes
30answers
1k views
Calculate ISBN-13 check digit
Write the shortest code that can calculate the check digit for an ISBN-13 from the first 12 digits.
Requirements:
Must be a function that accepts a string
Returns the full ISBN-13 as a string
Uses ...
16
votes
1answer
1k views
Implement QuickSort in BrainF***
As discussed in the Lounge room on Stack Overflow:
if you can't implement the Quicksort algorithm given en.wikipedia.org/wiki/Quicksort in any language you have minimal knowledge of, you might ...
16
votes
3answers
697 views
Code-Golf: Count Islands
A simple contest, inspired by this stackoverflow question:
You are given an image of a surface photographed by a satellite.The image is a bitmap where water is marked by '.' and land is marked by ...
16
votes
4answers
742 views
Optimal short-hand roman numeral generator
Goal:
Write a function that takes a number as input and returns a short-hand roman numeral for that number as output.
Roman Numeral Symbols:
Symbol Value
I 1
V 5
X 10
L 50
...
16
votes
0answers
389 views
The number of possible numeric outcomes of parenthesizations of 2^2^…^2
Consider an expression 2^2^...^2 with n operators ^. Operator ^ means exponentiation ("to the power of"). Assume that it has no default assosiativity, so the expression needs to be fully parenthesized ...
13
votes
16answers
1k views
The Luhn algorithm for verifying credit card numbers, etc.
Write the shortest (fewest number of characters) function that performs the Luhn algorithm checksum on a number.
Requirements:
Use the Modulus 10 version (original)
Function should accept a string ...
12
votes
7answers
2k views
Compute the CRC32 table at compile-time
The reference implementation of CRC32 computes a lookup table at runtime:
/* Table of CRCs of all 8-bit messages. */
unsigned long crc_table[256];
/* Flag: has the table been computed? Initially ...
12
votes
3answers
1k views
Solve Rubik's cube
Write the shortest program that solves Rubik's cube (3*3*3) within a reasonable amount of time and moves (say, max. 5 seconds on your machine and less than 1000 moves).
The input is in the format:
...
12
votes
7answers
457 views
Write all possible Braille characters
An interesting puzzle came to me looking at the elevator buttons this morning.
You are required to generate a list of all Braille patterns that fit in a 2x3 grid. Use a hash # to denote a bump and a ...
12
votes
5answers
619 views
Shortest terminating program whose output size exceeds Graham's number
Write the shortest possible program (length measured in bytes) satisfying the following requirements:
no input
output is to stdout
execution eventually terminates
total number of output bytes ...
11
votes
5answers
1k views
Solve 2-SAT (boolean satisfiability)
The general SAT (boolean satisfiability) problem is NP-complete. But 2-SAT, where each clause has only 2 variables, is in P. Write a solver for 2-SAT.
Input:
A 2-SAT instance, encoded in CNF as ...
10
votes
19answers
2k views
Calculate pi to 5 decimals
This comes from http://programmers.blogoverflow.com/2012/08/20-controversial-programming-opinions/
"Given that Pi can be estimated using the function 4 * (1 – 1/3 + 1/5 – 1/7 + …) with more terms ...
10
votes
1answer
575 views
I used to solve code golf puzzles like you, but then I took an arrow in the knee
Getting hit in the knee with arrows seems to be the injury of choice right now. As such, I propose the following golf challenge.
You have an adventurer that looks like this:
O
/|\
/ | \
|
|
...
9
votes
5answers
557 views
Swapping numbers
This is a common puzzle many of you have solved manually. Now this is the time to write an algorithm to solve the same.
There are equal number match sticks lined up in two different side facing each ...
9
votes
4answers
1k views
Best Scoring Boggle Board
I was interested in seeing the answers to this question, but the it was never corrected/improved.
Given a set of 6-sided Boggle dice (stolen from this question), determine in two minutes which board ...
8
votes
8answers
414 views
Make a pattern alternate
Problem
You are given a sequence of coloured balls (red R and green G). One such possible sequence is:
RGGGRRGGRGRRRGGGRGRRRG
In as few moves as possible, you must make it so that each ball is a ...
8
votes
7answers
503 views
Output a shuffled deck using random input
Input/Output:
Input: A uniformly random, infinitely long, string of '0's and '1's, taken from stdin. The string is assumed to be truly random, not pseudo-random. It is uniform in that each ...
8
votes
6answers
355 views
Soundex function
Write the shortest function to generate the American Soundex code for a surname only containing the uppercase letters A-Z. Your function must produce output consistent with all the linked page's ...
8
votes
3answers
603 views
Score a game of Go
Scoring a Go game is a task that is not all too easy. In the past there have been several debates about how to design rules to cover all the strange corner cases that may occur. Luckily, in this task ...
8
votes
1answer
309 views
Compact a Befunge program
Befunge is a 2-dimensional esoteric programming language. The basic idea is that (one-character) commands are placed on a 2-dimensional grid. Control flow walks across the grid, executing commands it ...
7
votes
9answers
565 views
Equilibrium index of a sequence
Equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:
A[0]=-7 A[1]=1 A[2]=5 ...
7
votes
9answers
652 views
Find largest sum of subsequence
Given a sequence of integers find the largest sum of a subsequence (integers on consecutive positions) of the sequence. The subsequence can be empty (in which case the sum is 0).
Input is read from ...
7
votes
6answers
1k views
Arbitrary Base Conversion
Create a routine that takes an array of blocks in one numeric base system, and convert them to an array of blocks in another numeric base system. Both the from and to systems are arbitrary and should ...
7
votes
8answers
1k views
Binary tree encoding
Let's suppose you have a complete binary tree (i.e. each internal node has exactly two non empty descendants). Each node contains a nonzero integer. You are given the task of encoding and decoding the ...
7
votes
5answers
321 views
Bijection between binary strings and pairs thereof
Input: Either one or two strings of '0's and '1's. If there are 2, they are separated by a space. All strings are of length at least 1.
Output: If one string was input, 2 are output. If 2 were ...
7
votes
2answers
488 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 ...
7
votes
5answers
749 views
Paint that fence
You are Tom Sawyer and you have to paint a fence of 102400 m long. Luckily, your friends decided to help you in exchange of various things. Each friend will paint L meters, starting from S with ...
7
votes
1answer
348 views
Generate a number by using a given list of numbers and arithmetic operators
You have a list of numbers L = [17, 5, 9, 17, 59, 14], a dictionary of operators O = {+:7, -:3, *:5, /:1} and a number N = 569.
Task
Output an equation that uses all numbers in L on the left-hand ...
5
votes
25answers
2k views
Program that determines whether an int is greater or lesser
Write a program which prompts a user to input two integers A and B, the program should determine whether A is greater than or lesser than B without the use of greater than [>] or less than [<] ...
5
votes
10answers
2k views
Print NxN spiral of ascending numbers
The numbers should be printed with leading zeroes in a field with length = (number of digits of N^2).
input (N):
4
output:
01 12 11 10
02 13 16 09
03 14 15 08
04 05 06 07
I am interested in ...
5
votes
4answers
327 views
Binary search (“bisect”) tool
Implement the binary search algorithm as used to identify the source code revision that breaks a computer software program. Your tool should take two arguments specifying the earliest and latest ...
5
votes
1answer
192 views
Write a CFG acceptor
Write a program that, given a context free grammar and a string, returns whether the string is a word of the language defined by the grammar.
Input
Your program should read a context free grammar ...
5
votes
2answers
273 views
Unfolding an integer
Given the functions
L: (x, y) => (2x - y, y)
R: (x, y) => (x, 2y - x)
and a number N generate a minimal sequence of function applications which take the initial pair (0, 1) to a pair which ...
5
votes
2answers
536 views
Domino Effect Problem
Last week we had a programming contest in my university and I am very curious about one of the problems , one which only one team (but from another city) was able to solve. May be its not that hard, ...
5
votes
1answer
426 views
Help at an IOI problem! [closed]
I'll participate in IOI 2011 this year, and I'm solving past IOI problems in order to get properly prepared. This problem is quite difficult. A binary search which uses two guesses to provide a ...
5
votes
1answer
409 views
Optimize matrix chain multiplication
This challenge is to compute the most efficient multiplication order for a product of several matrices.
The size of the matrices is specified on a single line of standard input. You should print to ...
4
votes
8answers
342 views
Is this figure connected?
You are given a list of (x,y) grid coordinates. Your function should decide whether the figure obtained by coloring in the squares of the grid with the given coordinates is connected or not.
Squares ...
4
votes
4answers
381 views
Fast inverse square root
Inspired by Write a code golf problem in which script languages are at a major disadvantage question on meta, I've decided to make a question which could be problematic for scripting languages.
The ...
4
votes
4answers
489 views
Code-Challenge:The Nearest Prime
Challenge
In this task you would be given an
integer N you have to output the
nearest prime to the integer.
If the number is prime itself output the number.
The input N is given in a single ...
4
votes
7answers
633 views
Generating n unique random numbers with a specific sum
Write an algorithm in any programming language you desire that generates n unique randomly-distributed random natural numbers (i.e. positive integers, no zero), sum of which is equal to t, where t is ...
4
votes
3answers
370 views
Help with an IOI problem! [closed]
I'll participate in IOI 2011 this year, and in order to prepare myself properly, I'm solving past IOI tasks. This task is kind of easy but it needs "a key" I can't figure out. I thought of making a ...
4
votes
3answers
351 views
Break the broken hash
Some time ago, I found this unused hash function (written in Java) in our codebase:
long hashPassword(String password)
{
password = password.toUpperCase();
long hash = 0;
int multiplier = ...
4
votes
4answers
888 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 ...
4
votes
4answers
508 views
Use a genetic algorithm to recreate a string
AKA: the most complex way to return a string I could think of.
Requirements:
*Edit: * @Griffin, You are correct, the goal is to use crossover/mutation of characters in a string to eventually come up ...
3
votes
3answers
455 views
Sum of Fibonacci numbers
I found this task here.
Given the ith (1<=i<=35) Fibonacci
number F(i) calculate the sum of the
ith till i+9th number
F(i)+F(i+1)+...+F(i+9) and the last
digit of the i+246th one ...
