What is the Sandbox?

This "Sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to the main page. This is useful because writing a clear and fully specified challenge on the first try can be difficult. There is a much better chance of your challenge being well received if you post it in the Sandbox first.

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, and click "Answer This Question". Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, replace the post here with a link to the challenge and delete it.

See the Sandbox FAQ for more information on how to use the Sandbox.

Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

Conway's Golf of Life- Brains vs Brawn Edition

2 programs play a competitive version of the game of life, where each program can set as many cells in the initial condidtions as there are characters in the other's source code.

The 2-player game of life is played on an infinite grid of cells. Each cell holds a value a, b, or 0. On each turn, the following rules are applied simultaneously to each cell:

• A non-zero cell with 2 or three non-zero neighbours keeps its value
• A non-zero cell with less than 2 or more than 3 non-zero neighbours is set to 0
• A zero cell with 3 non-zero neighbours is set to the value of the majority of its non-zero neighbours
• A zero cell with more or less than three non-zero neighbours keeps its value

The two player programs A and B have nA and nB characters respectively, and nA <= nB.

The grid is initialized to 0 everywhere

First, program A is called with the command line argument nB. It must output 2 * nB integers to stdout, which will be interpreted as a list L of nB ordered pairs. For each ordered pair in L, the cell at the coordinates in that pair will be set to 'a'

Second, program B is called with the command line argument nA followed by the 2*nB integers output by program B. It must output 2*nA integers to stdout, which will be interpreted as a list L of nA ordered pairs. For each ordered pair in L, the cell at the coordinates in that pair will be set to 'b'

Note: The coordinates output by programs must fit within 16 bit signed integers. However, calculation of steps will take place on an effectively infinite grid.

Once both programs have run, the grid is run through 10,000 turns. After this, if more cells are set to a, program A wins. Otherwise, program B wins.

The challenge is to create a program that has the best win/loss ratio against all other submissions.

• Might be worth requiring the output of the program to be distinct cells as a precaution against a highly golfed program which manages to output something with only 2 chars in an attempt to win by default. – Peter Taylor Feb 9 '15 at 17:44
• Also, I think you should probably run two games for each pair of bots, because if one bot is allowed to place all its cell first, I'm sure that will give a bias in some direction. Also, is the grid infinite? – Martin Ender Feb 9 '15 at 17:50
• – Martin Ender Feb 9 '15 at 17:52
• By infinite you mean the programs could choose silly coordinates like (1.000.000, 100.000.000)? – user16991 Feb 9 '15 at 17:56
• @kuroineko Yes. And that the patterns can move 10,000 cells in any direction without hitting a wall or wrapping around to the other side of a finite domain. – Martin Ender Feb 9 '15 at 17:58
• well in that case I would try to spawn walker launchers all over the place, with a huge random starting position. – user16991 Feb 9 '15 at 18:01
• The computation you will need to do is O(step_number^3) so 10000 steps means around Const*10^12 calculation which is undoable. I would advise 100 steps. The two player's cells probably wouldn't interact anyway if they don't do it in 100 steps. One other thing: I would still add a coordinate-limit like -2^30<x,y<2^30 as you probably don't want to do arithmetic with arbitrarily big integers. You should set the output requirement clear as the golfed codes' outputs might include extra spaces, linebreaks etc. if not stated otherwise. Otherwise I think it's a great challenge. – randomra Feb 14 '15 at 18:10
• Randomra: look up the algorithm "HashLife" which I would use to implement the control program. Calculating game of life steps can almost always be reduced to O(log(n)) - a pretty stunning result! I like the idea of limiting coordinates- I think I'll limit them to signed 32 bit integers, so contestants don't have to worry about handling inputs that break their language – QuadmasterXLII Feb 15 '15 at 17:14
• @QuadmasterXLII HashLife dissolves my concern. If you use the @[name] syntax at the start of your comment the person will be notified of your response and will notice it unlike I did. :) – randomra Feb 22 '15 at 18:50

Rendezvous palace optimization

Introduction

This comes from a well-liked question on the Math SE by RobAu and a more specific follow-up to that by Danikov.

There is a palace which is a grid of n × n rooms, which we will index using two coordinates 0 ≤ x,y < n. The rooms are organized in a torus topology, i.e. with wrap-around at the edges. So the room to the right of (n-1,3) is (0,3) again, and likewise for the y direction.

Two robots are placed into this grid, and their objective is to rendezvous. But the problem is that these only can can keep track of relative changes in position and orientation. So each robot has its own local coordinate system, where its initial position is called (0,0), but these two coordinate systems relate to one another in any of 4n2 possible ways, accounting for 4 possible relative rotations and n × n relative shifts. Each of these relations has equal probability.

The palace has no doors. The robots can move around the palace by teleportation. They move in a synchronized way, teleporting at exactly the same instant. To meet they either have to be in the same room at the same time, or to swap places during teleportation.

Challenge

Your task is to write a program for these robots, trying to minimize the expected time till rendezvous. The same program will be executed for both robots, and the robots have no way to distinguish which one is which. So we'll be executing two copies of your code in parallel.

Input

The only input is n, the size of the palace. In addition to that, the code has access to a random number generator, and the random numbers from one instance are assumed to be independent from those in the other instance. No other input or communication between the instances is allowed.

Output

The output of your code should be an infinite sequence of coordinate pairs, (x,y), indicating the target room for the next teleportation. The coordinates are relative to where the robot started, not relative to where he currently is located. Giving the same output repeatedly means you are staying put in a given room.

Framework

You are asked to evaluate your code yourself. Write or copy a framework which will randomly choose relative starting positions, execute two instances of your code in parallel, detect a successful rendezvous and report the time to rendezvous. Run that code a number of times, and compute the average and standard deviation of the time to rendezvous. See the section below for ready-to-copy code.

Submission

Your answer must include the code which constitutes the program for one robot. It must also include the average time to rendezvous and its standard deviation for the following setups:

1. at least 1,000,000 runs for n = 2
2. at least 100,000 runs for n = 64
3. at least 10,000 runs for n = 256

You don't have to paste your framework by default, but be willing to provide it upon request. An explanation of what your code is doing and why you wrote it that way might bring upvotes.

Scoring

The title of best answer will go to the code with the minimal expected time to rendezvous for n = 64. I'll re-evaluate the top contenders myself, to make sure you included genuine results. The closer two competitors are, the more often I'll run their code to establish a reliable expected value from the average. This is an open-ended contest, so the title may be re-awarded when a better answer comes along.

Example frameworks

C++

You can use the following fixture if you like.

#include <random>
#include <iostream>
#include <iomanip>
#include <cmath>

constexpr int n = 64;
const int orientations[4][4] = {
{1, 0, 0, 1},
{0, 1, n - 1, 0},
{n - 1, 0, 0, n - 1},
{0, n - 1, 1, 0}
};

std::default_random_engine randEngine((std::random_device())());
std::uniform_int_distribution<int> randDist{0, n - 1};
std::uniform_int_distribution<int> randDist4{0, 3};
int rand() { return randDist(randEngine); }

typedef std::pair<int, int> pos_t;

class Robot {
public:
pos_t next() { return {rand(), rand()}; }
};

class Transform {
int dx, dy, ori;
public:
Transform() : dx{rand()}, dy{rand()}, ori{randDist4(randEngine)} { }
pos_t operator()(const pos_t& in) const {
int x = in.first, y = in.second;
const int *o = orientations[ori];
return { (o[0] * x + o[1] * y + dx) % n, (o[2] * x + o[3] * y + dy) % n };
}
};

unsigned long run() {
Transform tr;
pos_t p1{0, 0}, p2{0, 0};
p2 = tr(p2);
Robot r1, r2;
unsigned long t = 0;
while (p1 != p2) {
++t;
pos_t q1 = r1.next();
pos_t q2 = tr(r2.next());
if (p1 == q2 && p2 == q1) break;
p1 = q1;
p2 = q2;
}
// std::cout << std::setw(8) << t << "\n";
return t;
}

int main(int argc, char** argv) {
double sum = 0, sumSq = 0;
int report = 10;
for (int i = 1; ; ++i) {
double r = run();
sum += r;
sumSq += r*r;
if (i == report) {
double avg = sum / i;
double var = (sumSq - sum*avg) / (i - 1);
double sd = std::sqrt(var);
std::cout << std::setw(8) << i << " runs: Expected: "
<< std::fixed << std::setprecision(2) << avg
<< ", SD: "
<< std::fixed << std::setprecision(2) << sd
<< std::endl;
report *= 10;
}
}
}


In a submission you'd just paste the next function. A possible statistical report for the above could read:

n = 2: Expected 2.40, SD 2.68 in 10,000,000 runs
n = 64: Expected 4105.08, SD 4104.22 in 10,000,000 runs
n = 256: Expected 64911.36, SD: 65204.72 in 10,000 runs


Python, …

To be extended for other languages. Feel free to donate your own framework if you feel like it.

A Continuously Running KOTH, or "An MMO with all AIs"

This was an idea discussed in chat, I'm throwing a sandbox post together because I thought it would be really fun to do.

The main idea is that the KOTH is hosted an an external website, where the competitions is continuously running. When a person submits an answer, that player's pixels (or whatever they're called) will be spawned in the game world. Over time, build a larger army of themselves.

Basically, it's an MMO with all AIs.

As of right now, I don't have the capability to host a website for this. I think someone (Optimizer?) said that they had a website. Regardless, we probably don't have to worry about that until we figure out what the rules are going to be.

Some ideas

• The world is a large array of randomly generated pixels. Every submission has a unique color. As pixels travel around, they can encounter other pixels of the same color, which then activate and join them.
• A more Minecraft-y options involve more detailed resource gathering / crafting. Con: the complexity can get pretty hard for contestants.
• A space theme can involve a randomly generated galaxy, which players can travel across. They can then colonize planets and build an empire. (Maybe resembling EVE Online?)
• Some recommendations for ideas are Clash of Clans and Globulation 2, although I've never played either.
• Maybe each player controls an adventure in a super-simplified Dwarf Fortress-style world.

You are free to edit this post to add ideas.

• Sounds really interesting! But I think the backend of this can get really complicated... – rorlork Apr 6 '15 at 22:16
• Would it be possible for a player to die out completely, so that the answer is permanently out of the competition? Is there some way that this could be prevented so every answer is represented, even if only by a very small number of pixels/creatures/... – trichoplax Apr 7 '15 at 21:33
• Respawning with a single individual would be one way. – trichoplax Apr 7 '15 at 21:35
• Alternatively each individual could have resilience inversely proportional to the number of individuals the player currently controls. So as the individuals reduce in number they get stronger, preventing the final individual from ever being killed. – trichoplax Apr 7 '15 at 21:36
• @trichoplax None of the specifics have really been thought through yet, but I think it would make sense to say that, upon death, players lose resources, but can't go below what they started the game with. – PhiNotPi Apr 7 '15 at 21:37
print $a[1]-1 ." "; }  Here, the function nine() takes the source code of the C program and manipulates it to get the number 9, then adds a space to the printed output. For scoring purposes, only the subroutine counts - the additional code was added for illustration purposes only and need not be listed on an entry in general. The input string for the next function will start with the "s" in "sub" and go through the final "}" The score for this function is thus 54 (including the actually unnecessary CRs and spaces). The technique used here is string splitting. An entry that included this code would thus look like this: 9: Perl sub nine{ @a=split(/"/,$_[0]);
print \$a[1]-1 ." ";
}


Score: 54

Technique: String split

...

Total

Base score: (54 + ... ) = 512

Unique techniques: 8

Final score: (512 / 8) = 64

• The goal of the rules is to 1) avoid trivial solutions and 2) encourage thinking about the next step while writing the current one. If the rules need to be added to enhance either aim, let me know.
• Is ten functions too many? I could start the count at 5 if that seems better
• I think 10 is good, as it encourages users to be ever more creative with each function. – mbomb007 Sep 10 '15 at 20:44
• "Doing something meaningful" is very hard to make precise. – Peter Taylor Sep 10 '15 at 20:54
• @Peter I defined it as having variable output based on the input. While something as simple as an if statement will cause that to happen, I think it might be OK when combined with the incentive for different techniques - 10 trivial "if input >=< something" routines won't be a very good score anyway as all techniques will be "comparison". Of course I'm open to better wording suggestions. :) – ThaddeusB Sep 10 '15 at 21:29
• @ThaddeusB Great idea. +1 – mınxomaτ Sep 16 '15 at 3:21

The Algebra of Reflecting Points

This is a challenge based on manipulating points with a specific set of operations, each dealing with the reflection of some points over others.

Warning: There's not actually a challenge here yet, just the basis for a challenge that could be to "simplify the given expression" or something.

Lists of Points

The fundamental object is an ordered list of points, like (A,B,C) or ([2,3],[5,8],[6,8]).

Reflection

A r B represents the reflection of point A across point B, resulting in a new point C so that B is the midpoint of AC.

A r (B,C,D) represents the reflection over a series of points, and is equivalent to A r B r C r D.

(A,B,C) r (D,E) represents (Ar(D,E),Br(D,E),Cr(D,E)), with either list being of any positive length.

The result of the reflection operator is a list of points that is the same length as the first operand. (If the first operand is a single point, then the output is a single point.)

A list with a single point is that same as that single point. (B) == B

Lists can be arbitrary grouped inside of other lists. (A,B,C,D) == (A,(B,C),D) == ((A,B,C),D)

Simplification

A point reflected over itself is an identity, CrC is the same as C. Any point reflected over the same point twice is an identity, rCrC can be removed.

(A,B,C) equals (C,B,A)

For any three points ABC there exists a unique fourth point D=C-B+A such that anything r (A,B,C) = anything r D. This means that any long chain of ArBrCrDrErF... can be reduced to have fewer than three rs.

((A,...,B)r(C,...,D)) == ((D,...,C),(A,...,B),(C,...,D)) and (ArB) == (B,A,B)

Examples

Show that Cr(CrA)rB == Cr(BrArC)

Cr(CrA)rB         #original
Cr(A,C,A)rB       #expanding 4th simplification rule
CrArCrArB         #the list is equivalent to a series of rs
CrAr(C,A,B)       #grouping to form a list
CrAr(B,A,C)       #swapping, the 2nd simplification rule
CrArBrArC         #expanding list
CrCrArBrArC       #Identity operation of C=CrC
Cr(C,A,B,A,C)     #listifying
Cr((C,A),B,(A,C)) #further grouping
Cr(Br(A,C))       #using the 4th simplification rule
Cr(BrArC)         #expanding parenthesis


Here is this proof visualized geometrically.

Whose Llama is it anyways?

BetaDecay posted a legit looking movie poster in chat, which got me into thinking that this could be a very nice challenge!

Your task is to overlay a nifty llama poster on top of a movie poster in a way that it still looks a legitimate movie poster. The image posted by Beta Decay is:

a http://pictures.boxxspring.com/pictures/960x0/100588

Your program will be provided with an input of fixed size (TBD) movie poster of any popular movie and a fixed llama cutout to overlay that poster as arguments. You may scale (proportionally), rotate or translate the llama cutout anywhere on the movie poster to make it look like a llama is photobombing the poster. At the same time, the output image should still look like a legitimate movie poster in a way the above poster feels real. You cannot perform any operations on the movie poster and no other operations on the cutout other than scaling, rotation and translation.

This is a popularity contest, so the answer with the most net votes wins. Voters are encouraged to judge answers by:

• The correct placement of the cutout such that it does not outright look like a cutout
• The scaling of the cutout to match with people/objects in the movie poster
• The placement of the cutout with respect to the movie text. i.e. The cutout should not hide the movie title in a way that its no longer understandable.

Input

Two images in any common image format. The input can come as paths to the images or the images themselves (if your language support image input) either as function arguments, ARGV, STDIN or equivalent.

The first image (movie poster) will be of fixed resolution and the second image (the llama cutout) will be of enough resolution in order to have good quality even after scaling or rotation.

Output

A single image of the same resolution as the movie poster image in any favorable image format.

[TBD]

Test Images

Here are a few images to test your algorithm on. Click on the images to get the actual resolution.

TBD

Please include some examples for these test images (along with other examples if needed) in your submission. Its also a good practice to briefly explain your algorithm as well.

Help Agent Zigzag with his secret messages

The WW2 double agent Eddie Chapman — aka "Agent Zigzag" — used an unusual cipher to communicate with his German controllers. It is described in the appendix of Ben Macintyre's book about Chapman and can also be viewed at the National Archives, apparently.

Read the following description and write a program to encrypt and decrypt messages using this system.

Your program should accept three inputs via stdin and/or command line switches:

1. A keyword
2. A flag to select either encryption or decryption
3. A message to be encrypted or decrypted

The output should be the corresponding ciphertext/plaintext, arranged into groups of 5 letters separated by single spaces. You may assume that the keyword consists entirely of uppercase letters, but should accept plaintexts and ciphertexts containing mixed case characters, punctuation and spaces. Non-alphabet characters should be stripped from the input and should not appear in the output (which may only contain groups of 5 uppercase characters separated by spaces, with an optional line break at the end). The date value used for keyword processing should be obtained from the system clock using the local time zone.

This is a code-golf challenge. The shortest code (measured in bytes) will win.

1. Keyword processing

Write out the keyword, and below each letter write the position in which this letter would appear if the letters were all sorted alphabetically. If the same letter appears more than once, number them from left to right. For example, the 14-letter keyword CONSTANTINOPLE would be processed as follows:

C   O   N   S   T   A   N   T   I   N   O   P   L   E
2   9   6   12  13  1   7   14  4   8   10  11  5   3


(Notice how the three Ns are numbered 6, 7 and 8.) Combine this sequence of digits into a single number, and multiply by the current date (from 1 to 31). For example, if the transmission is being made on the 8th of the month:

2961213171448101153 x 8 = 23689705371584809224


2. Encryption

Pad the secret message to a multiple of five characters in length by appending the null character X as many times as necessary, then encrypt Vigenere-style by cycling each letter through the alphabet by offsets corresponding to successive digits of the number calculated at step 1. For example, the message

Have arrived safely and in good health. Awaiting further instructions.


is encrypted as follows:

havearrivedsafelyandingoodhealthawaitingfurtherinstructionsx << Plaintext
236897053715848092242368970537158480922423689705371584809224 << Key (repeated)
JDBMJYRNYLEXIJMLHCPHKQMWXKHJDSUMIAIICKPKHXXBQLRNQZUWCGBIXPUB << Ciphertext


because 'H'+2='J', 'A'+3='D', 'V'+6='B', etc.

Finally, read off the encrypted message in groups of five characters:

JDBMJ YRNYL EXIJM LHCPH KQMWX KHJDS UMIAI ICKPK HXXBQ LRNQZ UWCGB IXPUB


• For languages that don't have system clock access, is it acceptable to take the date/time as an additional input? – Geobits Sep 23 '15 at 14:09
• @Geobits Would you mind if I said no? We have so many code-golf questions that are dominated by esolangs, I thought it would make a change to have one that favours higher-level languages. (Although it looks like Pyth can do dates...) – r3mainer Sep 23 '15 at 14:55
• I don't personally mind since I don't tend to use them. Some might, so I figured it was better to ask/clarify while it was sandboxed rather than on main. – Geobits Sep 23 '15 at 14:57
• It's not just about esolangs: removing the direct coupling with the system clock allows test cases which work consistently. – Peter Taylor Sep 23 '15 at 20:19
• @PeterTaylor But only 31 test cases are needed. – r3mainer Sep 23 '15 at 22:02