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

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]

• How are tags added to questions? – guest271314 Jan 9 '19 at 7:51
• @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] – DJMcMayhem Aug 29 '19 at 15:19
• Why no featured anymore? Can't we have it auto-added or something? – S.S. Anne Sep 26 '19 at 15:57
• @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary – caird coinheringaahing Sep 29 '19 at 13:43

# Implement the Maximize Affirmed Majorities voting system

There are many different voting systems in existence. Different voting systems have different mathematical properties, which serve to describe the "positive features" of that system. Here is an informative list of these properties and a table of compliance.

In this challenge, you will implement a voting procedure called "Maximized Affirmed Majorities", a method created with the sole purpose of meeting as many mathematical requirements as possible. You will write the shortest (in bytes) program (or named function) possible to determine the winner of an election using this method.

# The Procedure

Each vote is a self-consistent ordering of the candidates. It is possible for a vote to include ties between multiple candidates, like A>B=C>D=E=F. An example of a vote which violates these rules is A>B>A.

## Step 1: Create a tiebreaker

I know it's a little odd that creating a tiebreaker is the first step, but hopefully you never have to use a random tiebreaker for a full-scale election. A tiebreaker is a strict ordering of candidates. Let T(X,Y) be the tiebreak function, return true iff the tiebreaker ranks X above Y.

1. Choose a uniformly random ballot, and adopt the preferences of that ballot.
2. If the ordering is incomplete (like A>B=C>D=E=F), then choose a second uniformly random ballot (without replacement) and use that ballot to tie-break any unresolved orderings.
3. Repeat step 2 until the tiebreaker is complete. If you run out of ballots to create a tiebreaker with, randomly resolve the remainder of the list.

## Step 2: Create a list of majorities

This list takes the form of ordered pairs of candidates.

1. For each pair of candidates (X,Y), let V(X,Y) be the number of voters who ranked X strictly over Y.
1. If V(X,Y) > V(Y,X), then add (X,Y) to the list.
2. If V(X,Y) < V(Y,X), then add (Y,X) to the list.

## Step 3: Sort of the list in order of descending importance

A majority (X,Y) is ranked above (Z,W) if any of the following hold:

• V(X,Y) > V(Z,W); more support of X>Y
• V(X,Y) == V(Z,W) and V(W,Z) > V(Y,X); same support, but less opposition
• V(X,Y) == V(Z,W) and V(W,Z) == V(Y,X) and T(W,Y) == True
• V(X,Y) == V(Z,W) and V(W,Z) == V(Y,X) and Y == W and T(X,Z) == True

## Step 4: Affirm majorities in order of preference

Let F(X,Y) be a function that returns whether or not X finished over Y in the final list. It is initialized to False for every pair of candidates.

1. Iterate through the list of majorities, in order.
1. If F(X,Y) == False and F(Y,X) == False, then Affirm(X,Y).

The function Affirm(X,Y) is defined as follows:

1. Set F(X,Y) to true
2. For each candidate A where X != A != Y
1. If F(A,X) == True and F(A,Y) == False, then Affirm(A,Y)
2. if F(Y,A) == True and F(X,A) == False, then Affirm(X,A)

## Step 5: Determine the top candidate(s)

A candidate X is considered a top candidate if there exists no candidate Y such that F(Y,X) == True. That is, candidate X doesn't explicitly lose to anybody.

## Step 6: Tiebreak to determine the winner

Out of the list of top candidates, the winner is the candidate who appears highest on the tiebreaker list.

# Input

Input will be handled similarly to this online implementation I found, which also provides the complete ordering of candidates instead of just the winner.

Each line of input will contain a ballot, which is a list of space-separated candidates in descending order of preference. Optionally, two candidates separated by an = sign are considered equal in preference. A number followed by a colon at the start of a line denotes a multiple number of ballots.

[line] = ([number]: )?[candidate]( (= )?[candidate])*
[candidate] = alphanumeric string, not starting with a digit
[number] = a positive integer of course


Any candidates no ranked on a ballot are appended to the end and set equal to each other. You may optionally assume 1 or 2 newlines at the end of input.

## Example input:

Bob Sally Test4
Bob Sally Test4
1: Bob = Sally Test4 = Sam
4: Test4 Bob


is the exact same as

Bob Sally Test4 Sam
Bob Sally Test4 Sam
Bob = Sally Test4 = Sam
Test4 Bob Sally = Sam
Test4 Bob Sally = Sam
Test4 Bob Sally = Sam
Test4 Bob Sally = Sam


## Expected Output

Test4


# Sandbox Notes

• Interesting. Maybe some more testcases? – Ypnypn Feb 10 '15 at 21:16

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