# Tagged Questions

This challenge is intended to be solved by using, creating, or resolving some processing algorithm.

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 ...
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 ...
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 ...
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', ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 /|\ / | \ | | ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 [<] ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 = ...
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 ...