This challenge is intended to be solved by using, creating, or resolving some processing algorithm.
18
votes
5answers
541 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', ...
16
votes
0answers
337 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 ...
-1
votes
1answer
118 views
Filling slot based on limit [closed]
Duplicate of http://stackoverflow.com/questions/15726734/iterating-item-in-a-loop
I have a List<int> with the values like 60,45,45,45,45,30,60,60,15 people
Also i have two slots. 1st slot is ...
-2
votes
1answer
93 views
IPv4 “in subnet” function [closed]
Implement the following JavaScript method as short as possible:
function same_subnet(ip_a,ip_b,sn_mask)
{
}
It should get 2 IP addresses and a subnet mask. It should return true if ip_a and ip_b ...
1
vote
9answers
584 views
recursive power algorithm
Have a look at my (javascript) version of a O(log(n)) xn algorithm:
function pow(x,n)
{
return n==0?1:n==1?x:n==2?x*x:pow(pow(x,(n-n%2)/2),2)*(n%2==0?1:x);
}
Can you get it shorter?
7
votes
1answer
335 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 ...
11
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:
...
9
votes
5answers
548 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 ...
8
votes
8answers
412 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 ...
2
votes
2answers
344 views
Rail fence cipher- Is there any better solution?
I have coded Rail Fence Cipher in Python. I was wondering if there could be a better solution.
For those who don't know what rail fence cipher is, it is basically a method of writing plain text in a ...
8
votes
1answer
300 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 ...
-1
votes
2answers
376 views
“Defragmenting” a list
A fragmented file is a file which is seperated into several parts on a harddrive, because it can't fit into a certain space.
On all harddrives, there are files called unmovable files, which are ...
3
votes
3answers
405 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 ...
4
votes
4answers
376 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 ...
2
votes
1answer
249 views
Implement DES key expansion
I wanted to make a challenge to do the full DES encryption algorithm, but that may be a bit too involved to get a ton of participation. This challenge is to simply generate the 16 48-bit subkeys used ...
7
votes
5answers
320 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 ...
8
votes
7answers
497 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 ...
5
votes
2answers
527 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, ...
-1
votes
1answer
272 views
The real knapsack problem
Given
the number of goods N
positive weight of each good weight[N]
positive profit of each good profit[N]
and a positive number W which is the knapsack capacity.
This problem is called “the ...
4
votes
7answers
599 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 ...
12
votes
7answers
449 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 ...
5
votes
1answer
190 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 ...
2
votes
2answers
488 views
Generate N number of “Go First” dice
Background
As described here http://www.ericharshbarger.org/dice/#gofirst_4d12, "Go First" Dice is a set of four dice, each with unique numbering, so that:
There will never be a tie. Each die has ...
1
vote
0answers
245 views
Splitting goods among people so that everyone feels happy
A favorite puzzle of mine: There are n people and k goods. The goods can be arbitrarily split (let's imagine they're different raw metals, for example). Your task is to split them among those n people ...
2
votes
1answer
217 views
Minimum number of transactions so everyone has paid the same
On a road trip, N people pay for fuel. Each pays a different amount. At the end of the trip, calculate the minimum number of transactions so that each person has paid the same amount.
e.g. on the ...
-5
votes
2answers
246 views
Help Alice in giving candies
Alice is a kindergarden teacher. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual ...
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 ...
16
votes
3answers
678 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 ...
4
votes
4answers
503 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 ...
8
votes
3answers
594 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 ...
2
votes
9answers
967 views
Triangle Puzzle
Triangle Puzzle
Consider the triangle below.
This triangle would be represented by the following input file.
5
9 6
4 6 8
0 7 1 5
By starting at the top and ...
12
votes
4answers
577 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 ...
-5
votes
1answer
227 views
Sort an array with values of integer
There is an array of integer values to be sorted.During the sorting process, the places of two numbers can be interchanged. Each interchange has a cost, which is the sum of the two numbers involved.
...
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 ...
0
votes
2answers
1k views
Water-Bucket problem
How to measure 4 liters of water with just two uneven shaped buckets, one of 3 liter another of 5 liter, in minimum number of steps. To extend and generalize this, write a program to evaluate the ...
0
votes
0answers
374 views
How to check for balanced parentheses with mod? [closed]
Using a single double and different int's for various types of parentheses, without stack how to check for balanced parentheses with mod?
-1
votes
1answer
201 views
Which is the most efficient prime algorithm? [closed]
Which is the most efficent and easy to understand prime algorithm in c++?
2
votes
14answers
735 views
determine longest group of consecutive numbers
INPUT:
10 random numbers
each number is greater than 0 and less than 100
list of numbers is presorted, lowest to highest
the list will not contain any duplicate numbers
the solution should be in ...
16
votes
4answers
724 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
...
10
votes
1answer
566 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
/|\
/ | \
|
|
...
-7
votes
5answers
411 views
write a code the find n-th number of Gray Code list
Write a function that, given N >= 0, finds the Nth number in a standard Gray code.
Example input:
1
2
3
4
Example output:
1
3
2
6
Additional reference
1
vote
5answers
283 views
position of the only 1 in a number in binary format
Given N is a number from this list : 1, 2, 4, 8, 16, .... 2^i
as you know there is only a single "1" in binary representation of above numbers.
Question : write a code to find out the position 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 ...
5
votes
2answers
271 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 ...
2
votes
1answer
543 views
Determining the winner of a Chess game
Challenge
Being someone who plays far too much chess in his spare time, I thought I'd set a code golf challenge inspired by the game of chess (with a software flavour), for those interested.
The ...
5
votes
1answer
407 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 ...
1
vote
0answers
159 views
Minimize the number of coins for a purchase [closed]
We have a set of 5 coin denominations: penny, nickel, dime, quarter, and half-dollar. The number of coins for a purchase is the number of coins given from the buyer to the seller, plus the number ...
3
votes
1answer
310 views
Set the chessboard
Objective
Given an arbitrary chessboard as standard input (in which each piece is on a square), produce as standard output a list of moves needed to regularize, or set up, the chessboard. The moves ...
3
votes
2answers
426 views
Arithmetic Golf: Reach 2011
This is an ai-player challenge. Your goal is to reach the number 2011 as quickly as possible, or to get as close to it as you can.
Rules:
A "hole" consists of a rectangular grid of digits (0-9).
...
2
votes
4answers
438 views
Tricky Median Question
Given n points, choose a point in the given list such that the sum of distances to this point is minimum ,compared to all others.
Distance is measured in the following manner.
For a point (x,y) all ...
