# 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] – James 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

At the ASCII Stock Exchange, each character has a price. If a character is used more often, its price rises, otherwise the price decreases over time.

Initially, each character has price 10. [Meta: Is this too low/high?] After each answer, the prices change as follows:

• Each character that is not used in the answer's code has its price decreased by one, except when the price is already one, in which case it stays one.
• If a character is used n-times, then its price increases by n.

We define the score of a piece of code as the sum of the prices of its characters.

### Example

For the sake of simplicity, we only consider characters A, B and C for this example. The challenge itself works with all bytes from \0 to \255. Initially, we have the following prices:

A -> 10, B -> 10, C -> 10


If the code of the first answer is BAAA, then is has a score of 40 (computed by taking the previous character prices into account) and the prices change to

A -> 13, B -> 11, C -> 9


If the next answer is CC, it has a score of 18 and the prices are updated to

A -> 12, B -> 10, C -> 11


Your objective is to write a program or function which calculates the score of a given piece of code in dependence of a list of previous answers which all influence the initial prices in the way described above.

The goal is to do so while minimizing the submission's score itself in the context of this challenge, that is your submission should be able to calculate its own score by taking a list of all previous submissions and its own source code as input.

The answer with the lowest score in each language wins.

## Rules

• You may take a list of strings and a string as input, or require that the string to be scored is the first/last element of the list, or any other reasonable input format.
• You may not answer twice in a row.
• If an answer in language X has already been posted, you may only post another answer in language X if your submission achieves a lower score than the previous answer and the code is not identical.
• For this challenge only major releases of languages are considered their own language (e.g. Java 7 vs. Java 8). If there already is an answer in version A of a language and you have an answer in version B of the language and are in doubt whether version B is different enough from version A to be treated as different language, make sure that your code is not valid in version A.

To avoid having to copy all previous answers in order to calculate your submission's score, the chain will maintain a score calculator on TIO. Click on the link to the calculator in the previous answer and enter your code into the input field to calculate its score. Then add your code as a command-line argument, generate a new link and include it in your answer for the next submission.

If you wrote answer number 42 in Haskell with a score of 100, please format it as

 <code>


## Test Cases

These test cases are in the format list of strings, string to score -> result.

[], "BAAA" -> 40
["BAAA"], "CC" -> 18
["abc"], "abc" -> 33
["ab12", "aa22", "31a"], "ac23" -> 42
["a","b","c","d","e","f","g","h","i","j"], "123" -> 3


## Meta

• Any idea what could be a good initial price? I picked the number 10 rather arbitrarily.
• Letting the cost of unused characters decrease until 0 might lead to score 0 answers. Do you think this is a problem and the minimum cost should be 1? Minimum changed to 1.
• I'm unsure what range of characters is a sensible choice. Limiting answers to printable ASCII plus white space would make things easier but also exclude a lot of languages. Another possibility would be to allow the whole byte range from \0 to \255. Then also golfing languages could participate, albeit to score them they would need to be converted to their byte form which usually contains a lot of unprintable characters. The score calculator is able to handle unprintables, but I don't know how to insert them into the text fields on TIO. All bytes from \0 to '\255' are allowed.
• Is the winning criterion suitable for answer chaining?
• A leader board snippet would be nice, but I don't know how to modify the existing ones. If someone could provide such a snippet, I would be very grateful.
• Relevant tags?
• I think decreasing the scores to 1 is more sensible, because otherwise I could write a submission using all (or even just one of) the zero-score characters a billion times (say, in a comment), keeping a "minimum" score, but then subsequent submissions would have completely absurd scores, and it'd be easy to outgolf later, leading to a boring answer chain. – Giuseppe Oct 2 '17 at 18:08
• You may want to correct "enter your code into the input field to calculate its score. Then add your code as a command-line argument," – caird coinheringaahing Oct 2 '17 at 19:55
• I think allowing all 256 bytes is a good idea because languages like Jelly, 05AB1E, etc. will more than likely use more than the printable ASCII chars. – ETHproductions Oct 2 '17 at 20:30
• "While in principal Python 2.7.14 and Python 2.7.13 are different languages according to the site rules, I recommend to avoid using the fact that it is technically allowed as an excuse to post boring answers." Recommendations do not work, especially when they're as imprecise as this. (Are you "recommending" not treating Python 2 and Python 3 as separate languages? I have no idea). If you want to ban boring exploitation of the convention on different interpreters, ban it outright, but give a clear definition of how lines should be drawn. – Peter Taylor Oct 2 '17 at 21:21

Note: If you are seeing this first, you might want to sort by active.

## Unhappy numbers ascii art

Draw a square (or a rectangle as close to a square as possible) that represents the cycle of an unhappy number.

[ short description of unhappy numbers here + example ]

[ square formating rules ]

Unhappy integer.

ASCII art.

### Example

Input:
4
Output:
4 -  16 - 37
20         58
42 - 145 - 89

• The cycle of an unhappy number is a constant. – J B Mar 7 '11 at 23:42
• @JB: thanks, I will rephrase the question. I didn't mean the 4 cycle. (Why did I chose 4 as an example? :/ ) – Eelvex Mar 8 '11 at 4:56
• @Eelvex This is an nice challenge. Are you still interested in finishing it? – J Atkin Feb 7 '16 at 19:06
• This challenge proposal has been inactive for over a month. I would like to take ownership of the challenge and make it ready for posting. Please let me know within the next 2 weeks if you have any objections and would still like to finish and post this challenge yourself. – J Atkin Feb 10 '16 at 0:19
• @JAtkin, no objections. – Eelvex Feb 12 '16 at 11:20
• If this was posted, can you please delete it? – MD XF Aug 17 '17 at 16:58

# Tower Builder king-of-the-hill

The king is coming to visit! Your city is competing with another neighboring city to attract his attention.

Each player owns their own tower within a city full of other players. Each turn you place 1 blocks on your tower or another tower in your city.

After 100 turns, the king will only visit the city with the highest tower. If he visits your city, then you will gain points equal to the number of blocks in your personal tower. In the case of a tie, neither city is visited.

Games include all players, and each game will randomly arrange players into cities. Your score is the total score across all games.

• Player identifiers are randomly generated at the start of the tournament, but are consistent from game to game.
• In addition, contrary to past KoTHs: I allow saving state from game to game (but not between tournaments)
• You will always have complete information, including:
• The size of everybody's towers (including the other city)
• The actions players have taken
• The current score of all players
• How is always playing on the tallest tower in your city a bad strategy? Maybe the other city will do the same, but you won't lose. – aschepler Jul 22 '17 at 22:47
• @aschepler because the number of points you get is height of your personal tower. If you only build on another's tower, and never your own, you'll never get any points. – Nathan Merrill Jul 23 '17 at 1:55
• @NathanMerrill it took me a few minutes to understand what you even meant by that. you probably need to make this more clear – Destructible Lemon Aug 7 '17 at 0:24
• If the points are only awarded to the player who is visited by the king, it would seem that putting 99 blocks on the city tower and 1 block on your personal tower guarantees victory, no? – AdmBorkBork Jan 30 '18 at 17:22
• @AdmBorkBork there's no singular "city tower". Furthermore, you are still competing against the players in your city. Your score is your total score across many games. – Nathan Merrill Jan 30 '18 at 17:40
• Oh, the part that I missed was that multiple players share a city. I think that should be made more clear because that will drastically change strategy. I read it as you have a personal tower and everyone also gets their own city with a separate tower, and it's only the city's tower that matters for the king. – AdmBorkBork Jan 30 '18 at 17:45
• This needs some clarification about arrangement. The game will randomly arrange players into one of () cities, or a city with () others in it – pfg Jan 30 '18 at 19:10
• @pfg It'll definitely be one of () cities, but I'm not sure how many. My intuition says "2", but I can't give a solid reason. Any suggestions? – Nathan Merrill Jan 30 '18 at 19:21
• 2 or 3 per city or total cities? 3 seems good per city because with just two the strategy is much easier @Nathan Merrill – pfg Jan 30 '18 at 19:23
• Hmmm...I'm thinking 100 players in 2 cities, and allow for duplicate entries. – Nathan Merrill Jan 30 '18 at 19:28
• It seems to me that if you allow saving state you can simplify the last point to "You will be notified of the actions of every player" and let those who want to analyse it calculate the sizes of the towers, scores, etc. Normally I would favour supplying calculated information to save the players from re-implementing the game logic, but here the logic is simpler than the serialisation would be. – Peter Taylor Jan 31 '18 at 8:43
• @PeterTaylor I already provide complete information about the current game (including its history). The difference here is that you are allowed to persist information from game to game, meaning you can remember players who are antagonistic. – Nathan Merrill Jan 31 '18 at 15:04
• My point is that the communication between the server and the bots would be simpler if you didn't provide that information, and you don't need to provide it because it can be calculated easily. – Peter Taylor Jan 31 '18 at 15:07

## Can the robotic arm reach itself?

( ͡° ͜ʖ ͡°) title is kinda sketch at the moment

A robotic arm is made up of a set of line segments, each with a positive integer length. Each joint on the robot has two possible positions: straight or 90 degrees clockwise.

Here is a robotic arm with 4 line segments of sizes 4, 2, 3, 2

+---+-+--+-+


Here is the same robot arm with one joint bent

+---+-+
|
|
+
|
+


(vertical scale is kinda messed up)

Right now, the robotic arm isn't reaching itself. By bending all of the segments, however, the arm can reach itself.

+X--+
|  |
+--+


So, a robotic arm of size [4,2,3,2] can reach itself.

Here is a robotic arm of size [3,1,4,3] that can't reach itself:

+--++---+--+

+
|
|+--+
+---+


Whereas a robotic arm of size [1,1,2,2,3] can reach itself.

++-+-+--+

+
X++
| |
+-+


A robotic arm of size [2,2,3,5,3,4] can also reach itself

a-b-c--d----e--f---g

e--f
|  |
|  |
|a-b
|  g
d--c


## Challenge

Given list of numbers, such as [1,2,3,4,5], output a truthy value of the robotic arm can reach itself and a falsey value if it cannot.

• s/touch/intersect/g? – El'endia Starman Feb 17 '16 at 20:27
• We've had some related challenges I think. At least codegolf.stackexchange.com/q/45059/8478 – Martin Ender Feb 17 '16 at 21:01
• codegolf.stackexchange.com/q/49713/8478 – Martin Ender Feb 17 '16 at 21:03
• The scenario reminds me of stretchy snakes kissing. Except, these snakes are unusually rigid ... you know what, never mind. – xnor Feb 17 '16 at 21:45
• The first few examples would be clearer if either you also used letters to distinguish the joints or if you at least marked one end of the chain in both the straight and the folded representation. – Martin Ender Feb 18 '16 at 7:55
• You could probably also use more than one example where self-intersection only happens when not all joints are bent like the [1,1,2,2,3] example. If that's possible it would be good to have one where you need to bend joints on both sides of a straight joint to make the self-intersection happen, but I don't know if that can happen. – Martin Ender Feb 18 '16 at 12:23
• @El'endiaStarman s/touch/reach/g – mbomb007 Apr 7 '16 at 15:13
• Is 4,2,3,3 truthy or falsy? – Zgarb Feb 7 '18 at 8:12
• Can the robotic arm go through itself? The [2,2,3,5,3,4] case seems to indicate so. – stanri Feb 7 '18 at 10:50

# Overview

While the ants of the highlands gather food and walk around each other, their distant cousins live in the forests below, growing fungus and aggressively raiding the ground and other nests for food. But like their highland counterparts, they want food, and they have armies of workers at their disposal to get at it.

## The Arena

The arena is a torodial 1000*2500 rectangular grid of cells. Each cell has one of eight colors, and at most one object at any one time. There are three types of objects of significance:

• Ants are either queens, which are spawned at the start of the game, or workers, which are spawned by queens.
• Food is a prized possession, and may be hoarded or consumed.
• Fungi are ant-placed objects which may be created at low cost and will grow slowly into food if left alone within the vicinity of food.

In this game, adjacency refers to being in the Moore Neighborhood unless otherwise specified. Some rules instead specify the von Neumann neighborhood.

## Game Overview

Each game, 16 submissions are put against each other in a game. If the competition has fewer than 16 submissions, all of them participate in a game, and if there are more, the 16 players are chosen randomly.

At the beginning of each game, each cell is reset to the color 0 (white), each submission used in the game has its corresponding submission object constructed, and 2500 food, and 16 queens are randomly scattered onto the map. Queens are very unlikely to be adjacent to food or other queens, but this is not a guarantee.

Then the game itself proceeds. The game lasts for 15000 turns, and each turn consists of the following phases, each of which is resolved concurrently in turn:

• Decide: Each ant's views are determined based on the current state of the arena and previous move history, and each ant's decision is determined and validated separately.
• Move: Each ant's decision is executed simultaneously, and the presence of multiple objects in a single cell resolved once all ants that decided to move into a cell have done so.
• Grow: Each object that can potentially change as a result of its surroundings has its neighborhood resolved, and the changes to the objects as a result happen simultaneously.

After the 15000 turns is up, the game ends. Submission objects are disposed of, caches trimmed down, food amounts logged, and the process started again if more scores need to be collected.

## Ant Senses

Each ant has a 5*5 area of sight centered on themselves. This area of sight is arranged to give the ants a relative sense of direction in the immediate term, but not innately in the long term. Ants can see the color of empty cells, and the properties of objects in filled cells, but not the color of filled cells.

Each ant also has an internal state that can take one of eight values. This state is internal to that ant, and to transfer information between herself and other ants or to remember more than this, she must position herself, drop payloads, or mark the ground below her, all which are subject to enemy interference.

## Ant Actions

Using their senses, ants can decide to move or drop payloads, and also color their current cell and change their current state simultaneously, once per turn. The coloring happens on the cell that the ant is currently in, before she moves.

Ants move orthogonally or diagonally one cell at a time. Worker ants are free to move into other cells at their own risk, but a queen may not move to a cell that her view shows is in the Moore neighborhood of a non-adjacent queen, nor to a cell that her view shows is in the von Neumann neighborhood of an adjacent queen. (However, it is legal for a queen to stay still on a cell adjacent to another queen.) Additionally, a queen without food may not move into a step into a cell already occupied by a laden worker, lest she step onto a laden worker that decides to stay still, which would without this restriction kill her.

Instead of moving, ants may instead drop a payload into an adjacent cell. Food payloads cost one food, and can only be performed if the ant is carrying food. Fungus payloads cost nothing, and may be freely placed. Ant payloads may be performed only by the queen, cost one food, and consistently result in a new loyal worker. It is legal to drop payloads on oneself, but this will usually result in the dropped object being picked back up or destroyed during collision resultion, to no substantive effect.

## Ant Lifecycle

Both queen and worker ants start in state 0. Worker ants are oriented such that their "from" cell is the cell the queen occupied when spawning the worker, while queen ants have a random initial orientation. From there, it is up to submissions to perform ant-specific initialization and differentiation if desired.

Once spawned, ants have an indefinite lifetime. Queen ants are guaranteed to live up to the end of the game, but worker ants may die by colliding with other ants.

## Ant Leeching

After movements and collisions are handled, a queen may neighbor one or more unladen enemy workers. If the number of such neighbors is equal to or less than the amount of food carried by that ant, then the queen loses food equal to the number of adjacent enemy workers. An unladen worker ant that neighbors one or more enemy queens that lose food this way gains one food. If a worker is next to multiple such enemy queens, she receives only one food, and one or more food is simply lost forever.

This transfer does not occur between allied ants. To perform such food transfers, you must command the laden ant to drop her food in an adjacent cell, and have another ally be in that cell to automatically pick it up.

## Fungi

Fungi are a means of spawning more food. Fungus farms may potentially lead to bountiful harvests for submissions that invest the resources to spawn, watch over, guard and harvest these fungi. They may also be strategically planted to obscure the ground or probe for food from a distance.

If food is within a 9 by 9 cell area centered around the fungus, then the fungus will grow. Internally, fungus takes 32768 steps to mature and spawn into food, and will gain 1 step per generation per piece of food placed in this vicinity. Therefore, placing more food in the vicinity of a fungus will speed up the fungus's growth, but will also make a nice feast for any ants that find it. If a fungus is not within the vicinity of food, it will not grow.

Growth stages are visible to all ants, and work as a coarse indicator of the age of the fungus. 0 means that the fungus has taken no steps toward maturity, 1 means the fungus has taken 1-7 steps toward maturity, 2 means the fungus has taken 8-63 steps toward maturity, 3 means the fungus has taken 64-511 steps toward maturity, 4 means the fungus has taken 512-4095 steps toward maturity, and 5 means the fungus has taken 4096-32767 steps toward maturity. (If a fungus completes all 32768 steps of growth, it matures into food in time for ants to see it as food the next turn.)

# Collision Resolution

As noted above, all decisions are executed at once, and collisions are resolved as they happen once surrounding ants have all their decisions executed.

## Ants

Collisions are an unavoidable consequence of multiple ants deciding to enter the same cell independently, or one or more ants entering a cell of an ant that decides not to move from it. Because ants may move only one cell at a time, up to 8 ants can move into the same cell at a time, and may run into an ant standing still in it. Queen-queen collisions are prevented by the rules restricting movement within the vicinity of other queens.

Collisions of ants are resolved depending on the ants involved. For the purposes of collision resolution, an ant is considered moving if and only if she spent her turn moving herself to a different cell. A newly spawned worker is treated like a moving worker.

• A queen, if involved in a collision, is always the only survivor. She loses one food if she moved to a cell containing a laden worker that stayed still. As stated previously, a queen without food may not move to a cell already occupied by a laden worker, preventing the case where an unladen queen would step on a laden worker staying still.
• The collision of more than one moving laden ants in a worker-only collision results in all involved workers dying, leaving food behind in the cell.
• If a still laden worker is in a worker-only collision with no more than one moving laden worker, she survives, but loses her food if there was a moving laden worker in the collision.
• If a single ant in a worker-only collision held food and she moved, then she alone is the survivor. She loses the food she carried if she moved onto a worker ant that stood still.
• If none of ants in a worker-only collision held food, then they all die.

## Food and Fungi

Fungi do not stack. If multiple fungi are placed into a cell at once, collision resolution proceeds as if only one were placed in. Putting fungus in a cell already containing fungus will destroy the old fungus and create a new one. Fungus is destroyed if it shares its cell with any other object.

A queen ant that stays or moves into a cell will pick up all contained and/or placed food in that cell. However, if a worker does the same, she can only pick up one of these pieces, and the rest are simply lost forever. If no ants are available to pick up the food, then only one food remains in the cell, with the rest lost forever.

# Submission

Each submission must be a Javascript class, with two methods holding special significance: a constructor, which is called once per game start to initialize each object before eachTurn is ever called, and an eachTurn method, which is called concurrently on all new ant views to determine what to do.

The constructor is given no arguments, while eachTurn is given to arguments, an integer corresponding to the current ant's state, and a 25-length view array.

A possible submission skeleton is as follows:

class MyAnt {

constructor() {
//TODO: You fill this in
}

eachTurn(state, view) {
//TODO: You also fill this in
}

}


## Input

The view array contains objects of the following form:

{
contents: Integer representing the contents of the cell, 0 for empty, 1 for food, 2 for fungus, 3 for ant
details: Object giving details about the cell contents
}


The details object yields further information about the object in the cell, and for each of the possible cell contents, it has the following forms:

• Empty Cell:

{
color: Integer from 0-7 inclusive representing color of the cell
}

• Cell with Food:

{} // Yes, an empty object

• Cell with Fungus:

{
stage: Integer from 0-5 representing fungus stage, a very coarse indicator of age and time to maturity
}

• Cell with Ant:

{
queen: Boolean representing whether the ant is a queen
friend: Boolean representing whether the ant is ally or enemy
food: Integer representing the current food stores of that ant
}


Each view object provided represents reflects the true state of a cell in the arena, albeit with incomplete information. The array itself always corresponds to a flattened 5*5 cell area of the arena centered on the ant, rotated 0, 90, 180, or 270 degrees such that:

• For ants that have moved since spawning, either the cell to the top or to the top left correspond to the cell that the ant was in before the one currently inhabited
• For worker ants that have not moved since spawning, either the cell to the top or to the top left correspond to the cell that the queen occupied the turn she spawned the worker
• For queen ants that have not moved since spawning, the orientation is randomly determined at the start of the game and remains until the queen moves

Indices in the view array correspond to cells in english reading order:

 0  1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24


There is no means of getting orientation information definitively either form inside or outside, and it must be inferred by current state and surroundings.

## Output

The output expected of the eachTurn method is an object with the following fields:

{
cell: (Mandatory) Integer in 0-8 inclusive, representing the cell to move to or to drop a payload to
spawn: (Optional) If present, 0 for no payload, or 1, 2, or 3 for a payload of food, fungus, or worker, respectively
state: (Optional) If present, an integer in 0-7 inclusive, representing the state to change to
color: (Optional) If present, an integer in 0-7 inclusive, representing the color to color the old cell with
}


The cell is interpreted with the same rotation as the view. Output cells 0-2 correspond to view indices 6-8, output cells 3-5 correspond to view indices 11-13, and output cells 6-8 correspond to view indices 16-18. If you compare this to the index chart above, this is in the same english reading order as the view array provided.

## No Side Effects

Submissions may not make state modifications except to themselves, and should take care so that internal state modifications from calls to eachTurn are not visible from outside. Debugging submissions using input and output is allowed, but once submitted as an answer, they are forbidden. Attempting to use input or output in a submission will result in an error and disqualification until edited out.

## Consistency

Submissions are expected to behave deterministically, and the eachTurn function is expected to be pure, returing the same decision object for a given combination of state and view, regardless of how eachTurn was previously called or is currently being called.

Built-in functions may be called, if they are similarly externally pure. Math.abs() is fine, but Date.getTime() is not, for some examples. In particular, you are not allowed to call Math.random(). Supply your own pseudorandom numbers from constants, ant states, and ant views.

Unless you have a good handle on javascript concurrency and are willing to stress-test the code for concurrency bugs, I recommend using well-tested concurrency patterns and performing only idempotent modifications of objects, or avoiding modification in the eachTurn object altogether.

## Resource Limits

Each game submission starts with 1 second of reserve time. Each call to the constructor and eachTurn add 1 millisecond to the reserve time, then decrement from the reserve time the time they took to execute. Calls are memoized, and don't count against a submission if they are found in cache. If a submission exhausts its reserve time, it is disqualified.

Submissions are also limited to 64 Megabytes of memory at any one time. Unlike the time limit, this limit is not enforced automatically, but if a submission turns out to consistently hog memory during games it participates in, I will use a memory profiler to determine if this limit is exceeded.

# After Submission

## Disqualification

To keep tournaments running smoothly, submissions are disqualified if their submission performs an invalid action. Disqualified submissions will be excluded from future games within a tournament after a disqualification, and will be kept out of future tournaments until the problem causing the disqualification is fixed.

The following conditions are detected automatically, and therefore result in disqualification immediately:

• Exhausting reserve time, as described above
• Returning an ill-formed or badly typed object from eachTurn
• Throwing an exception from the constructor or eachTurn
• Attempting to spawn food or workers with no food
• Attempting to spawn a worker with another worker
• Attempting to move a queen too close to another queen
• Attempting to move an unladen queen to a cell containing a laden worker
• Performing input/output from submitted answers

It might seem harsh to disqualify for a single wrong move or bug, rather than consider it "no move" or ignoring it, but by insisting on correctness from entries, I can focus my efforts on keeping tournaments running quickly and smoothly. This is not supposed to be an additional challenge, so a reason is given for any disqualification, and an explanation given, with specific input and output given to help solve the disqualifying problem.

You may provide multiple answers, provided that each one stands as a competitor in its own right, does not team up with other submissions, and at least in part is the product of your own substantive effort. You may take advantage of other submissions' weaknesses in an effort to achieve a higher score in comparison. Keep in mind that submissions come in, the chances of running into another particular submission will decrease.

You may also edit your submissions to tune them however you choose. There are no guidelines about whether to create a new post or edit a currently existing post; the choice is yours.

If you make a variation of another submission, remember to differentiate it, and if is derived from someone else's work, remeber to credit your sources.

## Scoring

At the end of a game, submissions are ranked on how much food their queens held at the end of the game. Submissions which score exactly equal to each other simply share the average of the ranks they would have if they scored differently from each other.

Submissions with the highest average rank over a multitude of games win. For this challenge, I will give out working first places from tournaments as scores accumulate enough significance that Dunn's test indicates that there is a single distinct first place with at least 98% confidence.

# Chat

For questions and extended discussion of this challenge, please use the chat room. Comments on this post are likely to be cleared up from time to time, while chat room text will be kept around permanently.

If you want to contribute to the specification itself, see the github repository hosting the latest changes to this specification, right here.

• Chat room for this contest: chat.stackexchange.com/rooms/77728/the-formic-forest – eaglgenes101 May 18 '18 at 23:53
• Part of the complexity is making sure that the queen can't become a wrecking ball, but has clearly-defined restrictions so she can't be disqualified by no fault of her own. Take it from me, there's been more than a bit of arguing about how much the queen can and can't do. – eaglgenes101 May 21 '18 at 22:13
• Why are submissions a JavaScript class? You have rules about side effects and consistency so why not just make a toy language that must be functionally pure to implement the ants? Since the ants have a very limited view of the world it could easily be done with a fall through pattern matching. This would have the added benefit that people wouldn't need to learn JavaScript to participate, they would need to learn the toy language but IMO the language could be simple enough that it could be completely understood from a short description. – Ad Hoc Garf Hunter May 22 '18 at 23:24
• I'm following the mold of the Formic Functions challenge. Javascript is a familiar language that has had thousands of dollars worth pumped into creating optimized implementations, and while it has its shares of impurities and quirks, it's old and widespread enough that its warts are well-known and well-documented. – eaglgenes101 May 22 '18 at 23:41
• @HatWizard If you have any suggestion you can make one, and then someone else may write a JS interpreter of that language. Or this... well, almost all of those are esolang, nevermind. – user202729 May 24 '18 at 11:52
• I think that the choice of JavaScript was one of the mistakes of the original formic functions challenge. The way I see it, it is like using a jackhammer to crack a nut, sure you can do it but Javascript is a lot of machinery for the task and some things you want like functional purity are lacking. I'm not even specifically opposed to Javascript, I think that any other production programming language would be overkill for the task even if it had functional purity. I'm suggesting a small language that could be programmed in about 30 min and learned in about 2 min. – Ad Hoc Garf Hunter May 24 '18 at 15:18
• @HatWizard I can't imagine a language that takes 2 minutes to learn to be nearly enough. I'm not against this idea in general, though. – Alion May 24 '18 at 16:23
• @HatWizard a learning time of 2 minutes and a language powerful enough to have many approaches to the challenge (i.e. so not just specialized for pattern matching (even if that's the best option out there)) don't go together. Sure, >90% of my FF pattern matching code is just a ton of (nested) .maps and arrays but others might prefer different styles (e.g. Alions framework was class based, others just went linearly). For the original FF I thought of making a language specifically for my pattern matching ideology, but gave up as the requirements for me to consider it usable were too big. – dzaima May 24 '18 at 16:35

# Make A Full Dobble™ Deck

Dobble (A.K.A. Spot It!) is a deck of (55) cards each of which has a set of (8) distinct symbols, such that every pair of cards matches on exactly one symbol and all symbols are members of pairs.

The base aim of any of the games one plays with a Dobble deck is to find the matching symbols between pairs of cards quicker than your competitors; if you've never played I recommend it.

The deck as sold contains 55 cards and uses 57 symbols, but it is actually a "Full Dobble Deck" of 57 cards with 2 missing. If the missing 2 cards were added there would be 8 distinct symbols on each card such that each symbol would appear 8 times across the deck. Here is a deck I've been playing with, each row being a card (with the 2 missing cards added and asterisked):

  Anchor     Apple      Bird       Dinosaur   Dolphin    Ghost      Ladybird   Turtle
Anchor     Bang       Car        Clef       Flower     Key        Lips       Lock
Anchor     Bolt       Clown      Glasses    No-entry   Snowman    Spider     Target
Anchor     Bomb       Bottle     Dog        Heart      Ice-cube   Moon       Zebra
Anchor     Bulb       Cactus     Dragon     Flame      Scissors   Sun        Tree
Anchor     Candle     Clover     Hand       Man        Skull      Snowflake  Splat
Anchor     Carrot     Cheese     Clock      Hammer     Knight     Maple      Web
Anchor     Cat        Drop       Eroteme    Eye        Igloo      Pencil     Yin-yang
Apple      Bang       Igloo      Maple      Moon       Scissors   Snowflake  Spider
Apple      Bolt       Cactus     Car        Carrot     Heart      Pencil     Skull
Apple      Bomb       Cat        Hand       Lock       Snowman    Tree       Web
Apple      Bottle     Clover     Dragon     Flower     Hammer     No-entry   Yin-yang
Apple      Bulb       Cheese     Clown      Drop       Key        Man        Zebra
Apple      Candle     Clef       Clock      Dog        Eroteme    Flame      Target
Apple      Eye        Glasses    Ice-cube   Knight     Lips       Splat      Sun
Bang       Bird       Flame      Glasses    Heart      Man        Web        Yin-yang
Bang       Bolt       Bottle     Clock      Dinosaur   Drop       Hand       Sun
Bang       Bomb       Carrot     Clown      Dragon     Eroteme    Ghost      Splat
* Bang       Bulb       Dog        Eye        Hammer     Ladybird   Skull      Snowman
Bang       Cactus     Candle     Cat        Dolphin    Knight     No-entry   Zebra
Bang       Cheese     Clover     Ice-cube   Pencil     Target     Tree       Turtle
Bird       Bolt       Bomb       Candle     Cheese     Eye        Flower     Scissors
Bird       Bottle     Eroteme    Key        Knight     Skull      Spider     Tree
Bird       Bulb       Carrot     Clef       Hand       Ice-cube   Igloo      No-entry
Bird       Cactus     Drop       Hammer     Lock       Moon       Splat      Target
Bird       Car        Cat        Clover     Clown      Dog        Maple      Sun
Bird       Clock      Dragon     Lips       Pencil     Snowflake  Snowman    Zebra
Bolt       Bulb       Clover     Dolphin    Eroteme    Lips       Moon       Web
Bolt       Cat        Flame      Ghost      Hammer     Ice-cube   Key        Snowflake
Bolt       Clef       Ladybird   Maple      Splat      Tree       Yin-yang   Zebra
Bolt       Dog        Dragon     Igloo      Knight     Lock       Man        Turtle
Bomb       Bulb       Car        Dinosaur   Knight     Snowflake  Target     Yin-yang
Bomb       Cactus     Clock      Clover     Glasses    Igloo      Key        Ladybird
Bomb       Clef       Dolphin    Hammer     Man        Pencil     Spider     Sun
Bomb       Drop       Flame      Lips       Maple      No-entry   Skull      Turtle
Bottle     Bulb       Candle     Ghost      Glasses    Lock       Maple      Pencil
Bottle     Cactus     Clef       Clown      Eye        Snowflake  Turtle     Web
Bottle     Car        Cheese     Dolphin    Flame      Igloo      Snowman    Splat
Bottle     Carrot     Cat        Ladybird   Lips       Man        Scissors   Target
Bulb       Cat        Clock      Flower     Heart      Spider     Splat      Turtle
Cactus     Cheese     Dog        Ghost      Hand       Lips       Spider     Yin-yang
* Cactus     Dinosaur   Eroteme    Flower     Ice-cube   Man        Maple      Snowman
Candle     Car        Dragon     Drop       Ice-cube   Ladybird   Spider     Web
Candle     Carrot     Key        Moon       Snowman    Sun        Turtle     Yin-yang
Candle     Clown      Dinosaur   Hammer     Heart      Igloo      Lips       Tree
Car        Clock      Eye        Ghost      Man        Moon       No-entry   Tree
Car        Eroteme    Glasses    Hammer     Hand       Scissors   Turtle     Zebra
Carrot     Clover     Dinosaur   Eye        Flame      Lock       Spider     Zebra
Carrot     Dog        Dolphin    Drop       Flower     Glasses    Snowflake  Tree
Cat        Cheese     Clef       Dinosaur   Dragon     Glasses    Moon       Skull
Cheese     Eroteme    Heart      Ladybird   Lock       No-entry   Snowflake  Sun
Clef       Clover     Drop       Ghost      Heart      Knight     Scissors   Snowman
Clock      Clown      Dolphin    Ice-cube   Lock       Scissors   Skull      Yin-yang
Clown      Flame      Flower     Hand       Knight     Ladybird   Moon       Pencil
Dinosaur   Dog        Key        No-entry   Pencil     Scissors   Splat      Web
Dolphin    Dragon     Eye        Hand       Heart      Key        Maple      Target
Flower     Ghost      Igloo      Skull      Sun        Target     Web        Zebra


This is actually a Full Dobble Deck of order N=7, where the order defines the number of :

• symbols (N2+N+1);
• cards (also N2+N+1);
• symbols per card (N+1); and
• cards containing any given symbol (also N+1)

A Full Dobble Deck is analogous to a finite projective plane with points and lines as cards and symbols (or as symbols and cards) and thus may be constructed for any prime-power order (it is an open question whether finite projective planes exist for any non-prime-power order). We shall restrict ourselves to prime orders (it is much simpler to implement).

For example here is a Full Dobble Deck of order 3 (PG(2,3)) using 13 objects/colours (lines) and 13 cards (points) with 4 colours per card (lines incident with each point):

...and here it is as a list of cards containing the objects [0,12]:

[[2,3,8,11],[2,5,6,7],[1,2,9,12],[4,7,8,9],[4,5,11,12],[1,3,4,6],[0,6,8,12],[0,3,5,9],[0,1,7,11],[1,5,8,10],[6,9,10,11],[0,2,4,10],[3,7,10,12]]


### The challenge

Given a prime (N) yield a Full Dobble Deck of that order in any convenient form.
One must be able to observe completion for N=11 (no brute forcing here)
For any other input undefined behaviour is acceptable.

* You may alternatively take as input N+1 or N2+N+1

Here is a Python program that validates a potential Full Dobble Deck (it must be given as a valid list of lists in Python syntax such as the "list of cards containing the objects [0,12]" example above).

• You might want to consider some performance constraint which eliminates brute force approaches and forces people to think about the mathematics. – Peter Taylor May 29 '18 at 11:15
• @PeterTaylor Thanks for having a look at this. I was thinking of having a "one must be able to observe it complete successfully for N=11" but if you have a more concrete idea for a constraint do let me know (maybe it should simply be "N=11 in one minute"? I should probably code something up in a less efficient language to try...) On another note I am also wondering whether to restrict the input from prime-powers to just prime as supporting prime-powers as well as primes adds some complexity to the requirements on the implementation; still mulling, any further input very much appreciated. – Jonathan Allan May 29 '18 at 12:48
• Observing it complete is preferable to "in one minute" because it means that if I have a slower computer it doesn't invalidate my answer, but merely slows down when I can post it. Using just primes is certainly much easier because there's no need to build field towers with irreducible polynomials. I personally would be much more inclined to answer if it's primes only. – Peter Taylor May 29 '18 at 14:03
• Related/dupe maybe? – Dom Hastings May 29 '18 at 20:12
• @DomHastings weird I though, I'd searched both Dobble and Spot It, now I see two. The only things this would bring over the other code-golf question would be: (1) the alphabet there is bounded; and (2) implementing a constraint like Peter suggested. The current answer would need to iterate across (a least a large proportion of) the c(133,12) = 3.8*10^16 possible cards for N=11. I dont think (1) stops this being a dupe, but (2) might. Thoughts anyone? – Jonathan Allan May 29 '18 at 21:22
• @DomHastings Oh, and the brute-force solution there actually fails for N=4 (the first non-prime prime-power) even though I was planning on not requiring that to work the other (at present) does. – Jonathan Allan May 29 '18 at 22:33
• I only vaguely remembered it from when I first played Dobble too! Agree that the answer from the challenge I linked can't be copied over which I think is the main criteria for dupe, right? But the reverse might be true, all answers for your challenge should also solve the previous? So not sure if that make the older one a dupe, but that sounds too political for me! – Dom Hastings May 30 '18 at 11:39
• If the input for this one is restricted to N being prime (or even prime-power) then answers to this would not necessarily solve the other. Furthermore while the other is limited to an alphabet of 62 (while I plan on an execution observation for N=11 which has an alphabet of size 133) answers to the other would not necessarily answer this one. Seems like maybe it's not a dupe after all, even though the premise is exactly the same! – Jonathan Allan May 30 '18 at 12:03

# Chess ASCII Art, Knight

In honor of the world chess championship, in the shortest possible program, output the following ASCII art piece

      ,....,
,::::::<
,::/^\".
,::/,    e.
,::; |        '.
,::|  \___,-.  c)
;::|     \   '-'
;::|      \
;::|   _.=\
;:|.= _.=\
'|_.=   __\
\_..== /
.'.___.-'.
/          \
('--......--')
/'--......--'\
"--......--"


This is a code-golf challenge

• You might want to make sure all the lines are aligned properly (they could be fine, since I'm on mobile and I know it can display differently, but it looks bent to me). – Οurous Nov 23 '18 at 19:59
• you're right, it was a little bent, I've reformatted it – Thaufeki Nov 23 '18 at 20:17
• Seems straightforward enough – Quintec Nov 24 '18 at 1:23
• lol, akin to image compression of pixel art in a very specific case :) I like the idea. – alan2here Nov 24 '18 at 22:22
• The very worst is approx 145 bytes + "verbatim output this". Be fun to see much better ones :) – alan2here Nov 24 '18 at 22:33
• Isn't the World Chess Championship already over? According to google it ended nov. 28th. ;) Did you forgot to post it? – Kevin Cruijssen Dec 3 '18 at 9:08
• Yeah, I made this post on November 23rd, cross-posting from sandbox eventually slipped my mind – Thaufeki Dec 3 '18 at 14:42
• @Thaufeki You could still post it, or are you going to wait a year? ;) – Kevin Cruijssen Dec 4 '18 at 10:22
• I would have to wait two, next one isn't until 2020! I'll post it now – Thaufeki Dec 4 '18 at 14:43

# Is this checkmate?

Input

A chess position in FEN format. You can assume the input is a valid chess position.

Output

Two distinct consistent outputs for checkmate or not.

Examples

8/8/8/8/8/5BKN/8/7k b - - 93 47
Mate

• I suggest wording similar to “two distinct consistent outputs for checkmate or not” – Quintec Mar 12 '19 at 11:52
• @Quintec Thanks. – Anush Mar 12 '19 at 11:58
• I'd recommend keeping it all self-contained and having a description for the FFN format, as well as a few more test cases – Jo King Mar 12 '19 at 21:41
• Is restricted to the FFN format a part of the challenge? Why not allow it in any reasonable format? – tsh Mar 13 '19 at 5:47
• @Quintec why not just say truthy or falsey? – qwr Jun 20 '19 at 14:48
• I suggest removing the restriction to FEN format, as it doesn't really add anything to the challenge, and specifying that the output be a truthy or falsey value as that is the usual spec for these types of challenges. – scatter Aug 26 '19 at 13:28

## Lexicographically earliest valid UTF-8 byte sequence permutation

There are currently 1,114,112 possible Unicode characters (code points). Each character has a unique valid byte sequence in the UTF-8 encoding. Different characters have different length encodings:

• ASCII characters have a 1-byte encoding 00-7F.
• The next 1920 characters have a 2-byte encoding C2 80-DF BF.
• The rest of the BMP has a 3-byte encoding E0 A0 80-ED 9F BF and EE 80 80-EF BF BF.
• The other planes have a 4-byte encoding F0 90 80 80-F4 8F BF BF.

It's possible for two strings (specific non-normalised sequences of Unicode code points) of Unicode to have byte sequences that are permutations of each other in a number of ways:

• One string could simply be a permutation of the other at the Unicode level, e.g. ab (61 62) and ba (62 61).
• UTF-8 continuation bytes could be switched between two characters, e.g. ¡â (C2 A1 C3 A2) and ¢á (C2 A2 C3 A1).
• UTF-8 continuation bytes could be switched within a character, e.g. ᴵ (E1 B4 B5) and ᵴ (E1 B5 B4).

For this challenge I would like you to write a program or function that finds the string whose UTF-8 byte sequence is lexicographically earliest of all such sequences that are permutations of the UTF-8 byte sequence of a given Unicode string.

For example, if your input is ᵴ¢ába (E1 B5 B4 C2 A2 C3 A1 62 61) your output would be ab¡âᴵ (61 62 C2 A1 C3 A2 E1 B4 B5).

Note however that some byte sequences are not valid UTF-8 (e.g. E0 80 A0 which is an overlong encoding for a space) so you need to take care to avoid these.

It would be helpful if your "Try It Online" or similar link includes a footer that helps demonstrate the correctness of your output, where this is not obvious from the I/O format or code.

This is , so the shortest program or function that breaks no standard loopholes wins!

• For test cases, it will probably be a good idea to provide both strings and hex since I'd guess many languages will have to try both. Also this probably needs at least a link to an explanation of UTF8 continuation bytes. – FryAmTheEggman Jun 29 '19 at 16:57
• "permutation of its canonical" should be "permutation of the input's canonical". – Erik the Outgolfer Jun 29 '19 at 17:00
• @FryAmTheEggman ... but I provided the hex? I'm not sure what I'm missing... – Neil Jun 29 '19 at 23:24
• @EriktheOutgolfer How about "I would like you to write a program or function that returns the Unicode string whose canonical UTF-8 byte sequence is the lexicographically earliest of all such sequences that are permutations of the canonical UTF-8 byte sequence of a given Unicode string"? – Neil Jun 29 '19 at 23:27
• I meant in the example that you actually had, and presumably some number of test cases. I only mentioned it because I thought it was odd that you did it in the explanation but not the example. – FryAmTheEggman Jun 29 '19 at 23:54
• @Neil Looks good. :) – Erik the Outgolfer Jun 30 '19 at 16:34
• I'm wary of the use of the word "canonical" in this question, because it raises issues in my mind about normalisation of Unicode strings. I think that the intended challenge is really about byte arrays with constraints on the most significant bits, and I think it would be better to make that explicit (and to make the constraints explicit). – Peter Taylor Jul 2 '19 at 11:16
• @PeterTaylor There is that, but I wanted to exclude sequences such as E0 80 A0. – Neil Jul 2 '19 at 13:23
• @Neil, I think there's a miscommunication here. I'm saying that instead of talking about Unicode strings the question should explicitly state the FSS-UTF constraints on byte sequences, and maybe rule out encoding UTF-16 surrogate codepoints and codepoints greater than 0x10FFFF. – Peter Taylor Jul 2 '19 at 13:48
• @PeterTaylor OK but I really wanted this to be a string question rather than a byte sequence question... – Neil Jul 2 '19 at 16:20
• The problem then is dealing with the lexicographically first rearrangement of C3 A9 (é in normal form C) being 65 CC 81 (é in normal form D). – Peter Taylor Jul 2 '19 at 16:29
• @PeterTaylor Is that possible to do just by permuting the byte sequence? – Neil Jul 2 '19 at 16:34
• No, and that's why I'm arguing that the question should be phrased in terms of byte sequences rather than strings. – Peter Taylor Jul 2 '19 at 17:40
• There’s a mistake in the example: á is C3A1 and ¡ is C2A1. Good challenge. From the sound of it I/O will be flexible; this seems sensible since it keeps it open to more languages. – Nick Kennedy Jul 2 '19 at 17:54
• @PeterTaylor I wanted it to be clear that these byte sequences must be a valid UTF-8 encoding of a Unicode string. I've tried rewriting the question a bit... – Neil Jul 2 '19 at 23:55
• Can you add some test cases? – MilkyWay90 Jul 27 '19 at 14:35
• @MilkyWay90 Ok I added some – Ad Hoc Garf Hunter Jul 27 '19 at 14:47
• Okay, I give /support (also, you may want to add disallowing standard loopholes and using any default io method to finish it up) – MilkyWay90 Jul 27 '19 at 14:48
• @MilkyWay90 Those are already standard I am not going to be making my post any more cluttered with stuff that adds nothing. – Ad Hoc Garf Hunter Jul 27 '19 at 14:53

# Move arrows along a contour

Posted here

• I've edited in a question since it needs 2D for clarity. – Adám Jul 26 '19 at 8:48
• @Adám Only the arrows move. "+-|" always stay in place, or are "hidden" behind an arrow. So, you second example is correct (I deleted the first one) – Galen Ivanov Jul 26 '19 at 9:02
• Continuing @Adám's question: Are shapes always separated by at least one space, or can they be next to each other like ++++\n++++, and we have to determine if it's a ++++\n++++ or +--+\n+--+ based on the directions the arrows are facing? I.e. is this a possible/valid input, and are those outputs correct? – Kevin Cruijssen Jul 26 '19 at 11:26
• @GalenIvanov I didn't have anything but arrows move, and not it doesn't follow, because you couldn't tell what was behind the arrows, -s or +s which is what would make the two possible answers. – Adám Jul 26 '19 at 11:28
• @KevinCruijssen Example 2 has two adjacent shapes with no (vertical) spacing. – Adám Jul 26 '19 at 11:29
• @Adám Ah, you're right. As for your question however, you'd still know +<<+\n+>>+ is +--+\n+--+ due to the directions of the arrows in combination with the rule "when an arrow is on a corner, it keeps its current direction and changes it only after the turn is taken". See the pastebin in my previous comment for some test cases where you do know it's ++++\n++++ instead, because of the arrow directions. +^<+\n+>v+ will be two ++++\n++++ boxes, but +<<+\n+>>+ will be one +--+\n+--+ box. – Kevin Cruijssen Jul 26 '19 at 11:37
• @KevinCruijssen Good point, but OP actually never says that the input is an obtainable state, though it does make sense. I still have a feeling that there could be ambiguous cases. – Adám Jul 26 '19 at 11:41
• @KevinCruijssen The shapes will always be separated by at least one space, I'll add it to the description. – Galen Ivanov Jul 26 '19 at 11:44
• @GalenIvanov Probably better indeed to not have to deal with confusing ambiguous cases. In that case I would also have at least a newline separation, so test case 2 should be slightly modified. :) – Kevin Cruijssen Jul 26 '19 at 11:45
• @Adám Oh, I see - indeed I need to correct the second case to have a vertical space between the shapes. – Galen Ivanov Jul 26 '19 at 11:51
• Even single tracks can be incredibly difficult: [" ++ ","++++","++^+"," ++ "] only has one possible output: [" ++ ","++++","+++>"," ++ "] – Adám Jul 26 '19 at 11:55
• @AdámYes, this is the only output. Do you think a condition that sharp turns are forbidden will help? (this means no two + can be adjacent) – Galen Ivanov Jul 26 '19 at 12:21
• @GalenIvanov Maybe that's indeed better to reduce confusion and make the challenge someone more manageable. Although you can still deduct the solution in Adam's comment above, having no spaces inside the space makes it rather difficult to parse correct. Always having at least one |/- between two + will always give the shapes always spaces, making it easier to parse individual shapes. In which case Adam's one would become [" +-+ "," | | ","+-+ +-+","| |","+-+ ^-+"," | | "," +-+ "] -> [" +-+ "," | | ","+-+ +-+","| |","+-+ +>+"," | | "," +-+ "] – Kevin Cruijssen Jul 26 '19 at 13:55
• @KevinCruijssen Thanks, I added clarification. – Galen Ivanov Jul 26 '19 at 14:09
• @GalenIvanov Maybe also change the one Adam edited in, since it's still with ++ below one-another. :) – Kevin Cruijssen Jul 26 '19 at 15:08
• I found a lot of similar questions, but not quite the same. Would it be considered a duplicate? – Jitse Aug 1 '19 at 8:17
• we've had double factorial closed before as a dupe of the vanilla factorial question – Giuseppe Aug 1 '19 at 12:03
• @Giuseppe Thanks! I found that post, but I thought the variable factorial range might make it considerably different from the original challenge. – Jitse Aug 1 '19 at 12:12
• Can we take input as two integers? – Adám Aug 1 '19 at 12:49
• Can you give a definition for the multi-factorials above 2? – MilkyWay90 Aug 2 '19 at 4:55
• @Adám That makes the challenge somewhat easier, but I suppose it is fair. I added the other input option. – Jitse Aug 2 '19 at 7:04
• @MilkyWay90 Yes! Totally skipped that part, oops. Is it clear enough like this? – Jitse Aug 2 '19 at 7:05
• @KevinCruijssen Input numbers can be in any format, of course. I thought this was included in the default I/O rules, buy I will specify this in the challenge. – Jitse Aug 2 '19 at 12:39
• @KevinCruijssen In the input, at least one factorial sign is expected, i.e. a positive integer. I suppose the correct return value for a factorial number of zero would just be the base, but as the challenge is to calculate a factorial, this seems like an unreasonable restriction. The same goes for a factorial number lager than the base. If the factorial number is equal to the base, the base should be returned as per the generalized formula. I will add additional examples to clear this up. Thanks for the feedback! – Jitse Aug 2 '19 at 12:39
• @KevinCruijssen The range(start,stop,step) function in Python 3 returns a generator with an initial value of start (or 0 if not specified) and a final value of stop-1. For example, the list representation of range(1,4) is [1,2,3]. If this list is sliced as [1,2,3][::-1], the returned list is [3,2,1], which can also be achieved with range(3,0,-1). When the slicing operator is applied to the generator directly, a new generator is returned which generates the sliced list instead. Does that answer your question? Also, range(420,0,-30) would be a cleaner approach in this case. – Jitse Aug 2 '19 at 13:08
• @Jitse Ah ok, now it makes more sense. I indeed knew range(1,4) is [1,2,3]. And I also knew [::-1] reverses the order, since I see it used in answers every now and then. Seeing the range(1,4)[::-1] == range(3,0,-1) now I'm not sure why I didn't see it myself when I asked you the question. And yes, range(value,0,-n) would indeed be clearer than range(1,value+1)[::-n]. ;) – Kevin Cruijssen Aug 2 '19 at 13:24
• Seems good except maybe you should specify that $n!^{(k)} = n\underbrace{!\ldots!}{k}$ (n!^{(k)} = n\underbrace{!\ldots!}{k}) – MilkyWay90 Aug 2 '19 at 16:47

# Cliquish Program

Challenge: Write a program that accepts a character (or byte, see additional information) as input. Then:

1. If the character is contained within the source code, output a different character also in your source code.
2. If the character is not contained within the source code, output a different character also not in your source code.

This is a , so the shortest program (in bytes) wins.

• Your program must consist of at least 2 distinct characters.
• Your program must have at least 2 possible outputs.
• Your program does not have to be deterministic; it may output a character at random (with any distribution), so long as it conforms to the above criteria.
• Your program may optionally take a byte as input instead of characters. If you do, the code page the input is written in must contain at least each distinct byte in the source code, as well as at least two different bytes not in the source code.
• You may take input and give output in any reasonable way. For example, you may take input as a function parameter, a command-line argument, a line from STDIN, a triple-nested array containing a single character, etc. You could output via return value, STDOUT, exit code (if applicable), fax output, etc. The input and output formats must be consistent, however.
• Your output can only consist of the required character, optionally followed by one trailing newline. Prompt information (such as ans =) is exempt from this rule; such unpreventable output is acceptable.
• Slightly more interesting than most generalised quines. Have you checked quine for dupes? – Peter Taylor Aug 2 '19 at 7:32
• @PeterTaylor related related related. I couldn't find any exact dupes. – Conor O'Brien Aug 2 '19 at 19:39
• What if your program contains all but one possible character? What encoding are the characters in? UTF-8? latin-1? ASCII? – Beefster Aug 2 '19 at 20:18
• @Beefster Hopefully I've addressed your first question. As per your second, I believe we have a standard consensus on what a character is – Conor O'Brien Aug 11 '19 at 18:13
• By induction the program must have 4 possible outputs. Inside/outside of the source × two included in each (if choose one, output the other). Btw I don't understand the title – Mark Jeronimus Aug 22 '19 at 7:05

# ASCII Maze Unrendering 3000

Posted

• Part of the wall for the current only test case seems a bit too narrow. – Unrelated String Aug 28 '19 at 2:37
• I think this could be considered a special case of this challenge, with slight differences in the voxel style. – flawr Aug 29 '19 at 6:56
• @flawr You're right. As written, this is a duplicate. Do you know if the reverse has been done, taking the 3d version and returning the original? – Hiatsu Aug 29 '19 at 17:52
• I don't think the reverse has been done, but I'm not sure this would make a good challenge. I'm still thinking about how one could make this. I mean the 2d version you propose would make it a bit simpler. – flawr Aug 29 '19 at 19:10
• Yes. The full 3d version would almost certainly be impossible, because most voxels would be completely blocked. Here, every block is visible, and a human can figure out where the walls are, so a computer should be able to do it too. – Hiatsu Aug 29 '19 at 19:17

# Game of Lives

In this , your goal is to create a GOL (Game of Life) pattern that creates the most live cells after $$\n\$$ steps. The twist is, you will be competing against 3 other patterns on the same playing field at the same time.

Here are the rules of the Game of Life, with a couple of additions:

• Each player's starting living cells will be a specific colour.
• Any live cell with 2 or 3 live neighbours will stay alive, otherwise they'll die
• Note that 'neighbours' includes diagonals, so there are 8 possible neighbours for a cell.
• Any dead cell with exactly three neighbours will become a live cell with the colour of the most common neighbouring cell. If there is no majority, it will become a neutral colour, which won't count for further conversions.
• 2 Reds + 1 Blue = Red
• Red + Blue + Green = Neutral
• 2 Neutrals + Red = Red
• The playing field will be $$\x\$$ by $$\x\$$, where each quarter of the field is each player's starting configuration.
• Cells outside the playing field will always be considered as dead, and cannot be resurrected.
• Each starting configuration will be flipped and rotated so the right and bottom sides face the enemy.

For example, if your submission was:

And you plotted them against one another, the starting configuration could be:

Note how the bottom right isn't symmetrical, but still has the correct sides facing inwards.

Your submission should be a $$\x/2\$$ by $$\x/2\$$ GOL pattern that assumes it is in the top left corner.

Rounds will be run until only one competitor remains or the whole pattern repeats, where the competitor with the most cells when the pattern repeats is the winner.

### Sandbox:

• I haven't decided yet what sizes the playing field should be ($$\x\$$), nor how long each game should run ($$\n\$$).
• I was thinking about a 128 by 128 playing field, with 64 by 64 for each player. Is that too large or too small? For reference, the submission would be the size of: with some gliders and stuff for reference. Is that too many or too little? I haven't really got much reference.
• I am working on a visual controller like the Formic Functions question
• Overall winner? Check all combinations (way too much time as more submissions are added)? Tournament structure (multiple rounds per elimination)?
• So... where's the programming part? – Alion Nov 1 '18 at 12:36
• @Alion Your submission is a GOL pattern. I guess you could say you're programming in GOL – Jo King Nov 1 '18 at 12:52
• Fairy enough. I just think it's a missed opportunity. You could easily make it into a JavaScript competition, where programs just run multiple rounds of the currently planned game, having access to what happened last round, and thus being able to iterate on their patterns. You don't exclude anything - at the start, you're just going to get a lot of static entries (and I don't think anyone's going to be discouraged by the fact the they have to write return before their pattern). – Alion Nov 1 '18 at 13:03
• Unless you want to see the best static pattern, full stop. I can see that being fun as well - my comment was just a suggestion. – Alion Nov 1 '18 at 13:04
• 1) Is it just me, or is the example picture screwed up? The distances to the dotted lines don't match up. 2) My computer would greatly appreciate it if the side length of the board was a power of 2 - the closest size to that is 128x128. 3) You could make the game last until the pattern settles down, i.e. starts being periodic. – Alion Nov 1 '18 at 14:36
• I don't know if the challenge is interesting or not, mainly because it's very unintuitive to "program" in GoL. – user202729 Nov 1 '18 at 15:15
• @Alion "best" static pattern? I think how a pattern behaves also depends on its opponents. – user202729 Nov 1 '18 at 15:16
• @Alion I've fixed the image and changed the field size to 128, thanks. – Jo King Nov 1 '18 at 23:48
• @user202729 It might not be intuitive, but it is possible. Very possible. – Jo King Nov 1 '18 at 23:52
• We need to clarify the behavior on the borders outside of the whole playing field. Does the grid extend indefinitely? Or does it wrap around? Or maybe simply hard dead cells (cannot turn to alive whatsoever) outside the given area? – Bubbler Nov 2 '18 at 5:32
• @Bubbler Cells outside the playing field will always be considered as dead, and cannot be resurrected. Though wrapping cells might be interesting... – Jo King Nov 2 '18 at 5:44
• Oops, I didn't notice that. – Bubbler Nov 2 '18 at 6:04
• If they are all different colours, then the cell will be randomly picked from those colours. Given the nature of complex GoL patterns, I would suspect that one random cell choice can make a huge difference, so it might be nicer to keep the outcome deterministic and just kill such a cell. – Laikoni Nov 2 '18 at 8:49
• @Laikoni For clarity: we're talking about cell colors being chosen randomly, right? While I agree that this could generate large bias within a single game, I don't think it matters in the grand scheme of things. As for the solution (if this is to be considered a problem) - breaking the GoL rules seems odd. For example, a 3-color blinker would just disappear. How about adding an additional, neutral color in that case? It would behave the same way that all the other colors behave, but wouldn't give any points to anyone. A 3-color blinker would lose its outer colors that way, but keep existing. – Alion Nov 2 '18 at 10:29
• You should probably explicitly mention that GoL uses a Moore neighborhood (which includes diagonals), as opposed to a von Neumann neighborhood (which does not). – Mego Nov 2 '18 at 23:12
• @Night2 Indeed, didn't notice that point, I fixed the samples in the rules to include AA-000-AA – Elcan Sep 20 '19 at 6:25
• Are the letters mandatory to be uppercased, or could we output in lowercase as well? – Kevin Cruijssen Sep 20 '19 at 9:51
• @KevinCruijssen Yes, letters are mandatory to be uppercase, also I feel like you ask that because of a builtin somewhere :P – Elcan Sep 20 '19 at 12:36
• Fine by me. I was mainly asking because it isn't a core-part of the challenge, and in some challenges lowercase/uppercase/mixed case is all allowed. But you're indeed right that lowercase would save a byte in my language of choice 05AB1E, where A is the lowercase alphabet builtin, and I'd need an additional u to uppercase it. ;p But since number plates are always uppercase, I can understand to keep the uppercase mandatory here as well. I had prepared a 24-byter, but will throw it away for now since I feel this can be done shorter.. Will try again later when it's posted to main. :) – Kevin Cruijssen Sep 20 '19 at 12:41
• Another question, or more recommendation: allowed both 0-based and 1-based indexing for answers. I see your test cases are 0-based, but some languages use 1-based indexing instead. – Kevin Cruijssen Sep 20 '19 at 12:44
• @KevinCruijssen Sure, no problem with 1-based indexing, going to fix the rules to add that. As I've never used such languages, I often forget about them – Elcan Sep 20 '19 at 13:19
• I would say if the format irl has to be in uppercase then following that would be better. I've got myself an 85-byte JS answer that conforms to the irl format though. – Shieru Asakoto Sep 21 '19 at 1:06
• @ShieruAsakoto That's what I also advocate for, minus all the dumb real life rules that would just make it unfun to do. Anyway, going to post this – Elcan Sep 23 '19 at 18:41

# Win the competition king-of-the-hill

Write a Javascript function, that, given two functions as strings, deterministically picks one as the winner and returns 1 for the first input and 2 for the second input. The choice must not depend on the order of inputs.

Every unordered pair of submissions will be compared via every submission. Every time a program is chosen as the winner, it is assigned 1 point. If a program doesn't halt in 0.5 seconds (when run by me locally), it is stopped and disqualified.

Submissions must not store any information between runs, interfere with the controller or somehow destroy my computer. Submissions must not duplicate other submissions or be longer than 200 KiB.

The submission with the most points wins.

I still have to write a controller (that is pretty minimalistic compared to some KOTHs, but I haven't started yet).

# Sandbox stuff

• How can I prevent the last answer from always winning?
• Would it be a good idea to introduce other requirements for the submissions, such as transitivity?
• That is a really fun idea but probably more a social- than a programming challenge:) I guess one problem is that newer submissions can always be tuned to favor themselves against all the existing ones, so it is probably gonna end up as a "last submission wins" if you don't include any counter measures. – flawr Nov 26 '19 at 9:06
• I suggest a rule against randomness (and probably a language restriction, too, those make it a lot easier) – Redwolf Programs Nov 26 '19 at 13:55
• @RedwolfPrograms I can see why is randomness bad, but why should I add the language restriction? I have thought about it, and know I will probably add it in the end (because I can write an automated tester only in some langauges), but does it actually improve anything? (I guess I'll restrict to one of Javascript, C# or Python; Javascript seems to be the most common so it is also the most likely) – my pronoun is monicareinstate Nov 26 '19 at 14:23
• @mypronounismonicareinstate No specific reason, but it tends to simplify things massively. It also allows the bots to more effectively read the source code – Redwolf Programs Nov 26 '19 at 14:48
• To minimise the problem flawr mentions you could consider only showing a "peek" of the programs to be judged, and then include a suitable upper bound on length. Of course, this has the problem of choosing that upper bound, but I think it may lead to a better back-and-forth? Posting will also still have a negative effect on your ability to win, however. – FryAmTheEggman Nov 26 '19 at 19:34
• Some languages make extensive use of non-ascii characters, and some languages don't support non-ascii characters as input. Restricting the language is one way to solve this problem. – 79037662 Nov 29 '19 at 17:13
• You should post it, just to see how it goes. Five upvotes just in the sandbox...if you added a language restriction and a few more rules to prevent the last answer from always winning, I think it'd be a popular challenge – Redwolf Programs Dec 1 '19 at 23:08
• Do we submit functions that take strings, programs that read from STDIN, or perhaps even functions that take functions? – Jo King Dec 2 '19 at 4:57
• I feel like the "no hashing" condition might be a bit problematic: For the last program submitted not to have an easy time with the rest, the scoring method of a program needs to be very hard to predict and game, and hashes are basically the optimal way about this. This then might end up with a challenge where people try to implement almost-but-not-quite hashing functions without upsetting you. – AlienAtSystem Dec 14 '19 at 9:22
• @AlienAtSystem I see your point; removed the hashing restriction and also a loophole (where a solution that is a few GiB large, but presumably full of comments so that it doesn't run too slowly, makes all others time out). – my pronoun is monicareinstate Dec 14 '19 at 12:09

# lc's dvntrs n Wndrlnd

Your program or function will be given as input the first 6 paragraphs of Lewis Carroll's famous novel Alice's Adventures in Wonderland, with all vowels [aeiouAEIOU] removed and all other characters left intact.

It must output the original text, byte-for-byte identical.

As a reminder, you are not allowed to fetch any data from an external source (this is a default loophole). If you do that, you'll be trapped in the Rabbit hole for 6 months.

## Input

Your program or function will be given this exact ASCII string, where $$\703\$$ vowels are missing:

lc ws bgnnng t gt vry trd f sttng by hr sstr n th bnk, nd f hvng nthng t d: nc r twc sh hd ppd nt th bk hr sstr ws rdng, bt t hd n pctrs r cnvrstns n t, "nd wht s th s f  bk," thght lc "wtht pctrs r cnvrstns?"
S sh ws cnsdrng n hr wn mnd (s wll s sh cld, fr th ht dy md hr fl vry slpy nd stpd), whthr th plsr f mkng  dsy- chn wld b wrth th trbl f gttng p nd pckng th dss, whn sddnly  Wht Rbbt wth pnk ys rn cls by hr.
Thr ws nthng s _vry_ rmrkbl n tht; nr dd lc thnk t s _vry_ mch t f th wy t hr th Rbbt sy t tslf, "h dr! h dr!  shll b lt!" (whn sh thght t vr ftrwrds, t ccrrd t hr tht sh ght t hv wndrd t ths, bt t th tm t ll smd qt ntrl); bt whn th Rbbt ctlly _tk  wtch t f ts wstct-pckt_, nd lkd t t, nd thn hrrd n, lc strtd t hr ft, fr t flshd crss hr mnd tht sh hd nvr bfr sn  rbbt wth thr  wstct- pckt, r  wtch t tk t f t, nd brnng wth crsty, sh rn crss th fld ftr t, nd frtntly ws jst n tm t s t pp dwn  lrg rbbt-hl ndr th hdg.
n nthr mmnt dwn wnt lc ftr t, nvr nc cnsdrng hw n th wrld sh ws t gt t gn.
Th rbbt-hl wnt strght n lk  tnnl fr sm wy, nd thn dppd sddnly dwn, s sddnly tht lc hd nt  mmnt t thnk bt stppng hrslf bfr sh fnd hrslf fllng dwn  vry dp wll.
thr th wll ws vry dp, r sh fll vry slwly, fr sh hd plnty f tm s sh wnt dwn t lk bt hr nd t wndr wht ws gng t hppn nxt. Frst, sh trd t lk dwn nd mk t wht sh ws cmng t, bt t ws t drk t s nythng; thn sh lkd t th sds f th wll, nd ntcd tht thy wr flld wth cpbrds nd bk-shlvs; hr nd thr sh sw mps nd pctrs hng pn pgs. Sh tk dwn  jr frm n f th shlvs s sh pssd; t ws lblld "RNG MRMLD", bt t hr grt dsppntmnt t ws mpty: sh dd nt lk t drp th jr fr fr f kllng smbdy ndrnth, s mngd t pt t nt n f th cpbrds s sh fll pst t.

• Size: 1677 bytes
• Paragraph separator: LF
• SHA-256: df40659e07f6185ea348028dd22f137902fa50b9abcb790ff39353e189656c6f

## Output

Your code must print or return this exact string.

Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it, "and what is the use of a book," thought Alice "without pictures or conversations?"
So she was considering in her own mind (as well as she could, for the hot day made her feel very sleepy and stupid), whether the pleasure of making a daisy- chain would be worth the trouble of getting up and picking the daisies, when suddenly a White Rabbit with pink eyes ran close by her.
There was nothing so _very_ remarkable in that; nor did Alice think it so _very_ much out of the way to hear the Rabbit say to itself, "Oh dear! Oh dear! I shall be late!" (when she thought it over afterwards, it occurred to her that she ought to have wondered at this, but at the time it all seemed quite natural); but when the Rabbit actually _took a watch out of its waistcoat-pocket_, and looked at it, and then hurried on, Alice started to her feet, for it flashed across her mind that she had never before seen a rabbit with either a waistcoat- pocket, or a watch to take out of it, and burning with curiosity, she ran across the field after it, and fortunately was just in time to see it pop down a large rabbit-hole under the hedge.
In another moment down went Alice after it, never once considering how in the world she was to get out again.
The rabbit-hole went straight on like a tunnel for some way, and then dipped suddenly down, so suddenly that Alice had not a moment to think about stopping herself before she found herself falling down a very deep well.
Either the well was very deep, or she fell very slowly, for she had plenty of time as she went down to look about her and to wonder what was going to happen next. First, she tried to look down and make out what she was coming to, but it was too dark to see anything; then she looked at the sides of the well, and noticed that they were filled with cupboards and book-shelves; here and there she saw maps and pictures hung upon pegs. She took down a jar from one of the shelves as she passed; it was labelled "ORANGE MARMALADE", but to her great disappointment it was empty: she did not like to drop the jar for fear of killing somebody underneath, so managed to put it into one of the cupboards as she fell past it.

• Size: 2380 bytes
• Paragraph separator: LF
• SHA-256: 86abbfeb5dfa10bd9b266ea91723b9f79ab49306e2e8266174a0aa4c49ba7d57

You can use this script to test your output.

• This is a wonderful challenge idea! Minor comment: I think having line-breaks for fixed width in the text is kind-of weird. It feels not so much part of the text, as the format used to display it. – xnor Mar 25 at 8:23
• I suggest reminding readers about the loophole of fetching the text from an external source, which someone is bound to try. – xnor Mar 25 at 8:26
• @xnor Thank you for your feedback. Updated accordingly. Edit: Hmm. Using a single LF between paragraphs might be better. – Arnauld Mar 25 at 8:55

I attempted a problem I threw out as a suggested for 1p5.

In c, lex and yacc I needed more than 9600 characters ungolfed (fully commented, errors handled, some debugging code left in place, but some efficiency sacrificed in the name of shorter code), which seems pretty long, but c is about the most pessimal language you could choose for this problem except fortran 77 or something from the Turing Tarpit. The reference implementation can run its own build, which has some of that bootstrapping voodoo.

None-the-less, this is a relatively big project, and I don't want to post it unless people feel it is both well specified and interesting.

As yet there is no validation script, and I am not sure how one could be written as the acceptable output order could be post-order depth first or post-order breadth first and there is a left-first vs. right-first ambiguity on both. What a bother.

Aside: I'm quite proud of the lex and yacc part of my code, as I consider it spiffy.

## A minimal implementation of the make (1) utility.

By minimal I mean,

• No built in rules, and no pattern or suffix rules.
• No variables and therefore no variable assignment or manipulations; also no variable expansion which includes no expansion of environment variables.
• No automatic variables like $< and$@.

This only leaves constructs (called rules) of the form

<target> ":" <prerequisite>* "\n" ["\t" <action> "\n"]*


Where each <target> and <prerequisite> is a whitespace delimited string which may (or may not) represent a filename. Empty lines have no effect and "#" marks the beginning of a end of line comment (the sequence "#[^\n]*\n" should be treated as "\n" so it does not interfere with rules; this has the side effect of making "#" illegal in targets, prerequisites and actions). Colons are prohibited in identifiers.

The program should take its input from the standard input or by reading a file called "makefile" - implementer's choice. The program then attempts to "build" every target named on the command line. Any targets specified on the command line which do not appear in the makefile and do not represent an existing file should generate an error and cause the program to exit before execution of any rules. In the event that no target is named on the command line, default to building the first target in the input.

Duplicate targets may (not must!) be treated as an error.

A target is deemed already built if

1. It names an existing file and
2. All its prerequisites are fulfilled

Otherwise it is built by

1. Building all unfulfilled prerequisites then
2. Running each <action> sequentially in the order they appear in the input, and if the action returns an exceptional exit state, stopping the program.

A prerequisite is deemed fulfilled if

• The prerequisite represents an existing file and
• The prerequisite is built and
• The target is "newer" than the (fully built) prerequisite

A target is deemed "older" (i.e. not "newer") than its prerequisite if one of

• Both represent files and the prerequisite has been modified more recently than the target.
• The target does not represent an existing file, and the prerequisite does.

apply.

Authors on systems which do not support fork/exec semantics may write a batch file or script which is invoked as the program terminates, but that script must stop on the first unsuccessful action.

## Sample Input

# Babymake compatible makefile for babymake
all:babymake

babymake : lex.yy.o  y.tab.o  babymake.o
cc -o babymake lex.yy.o y.tab.o babymake.o

babymake.o : babymake.c babymake.h
cc -c babymake.c

lex.yy.o: lex.yy.c y.tab.h
cc -c lex.yy.c

lex.yy.c : babymake.l
lex babymake.l

y.tab.o: y.tab.c babymake.h
cc -c y.tab.c

y.tab.c : babymake.y
yacc -d babymake.y

clean:
rm -f babymake.o  lex.yy.o  y.tab.o

cleaner: clean # just testing end of line comments
rm -f y.tab.c y.tab.h
rm -f lex.yy.c

bogus: boguser
echo "building bogus" # test in another context


## Sample output

$./babymake < babymake.example cleaner rm -f babymake.o lex.yy.o y.tab.o rm -f y.tab.c y.tab.h rm -f lex.yy.c$ ./babymake < babymake.example all
cc -c babymake.c
yacc -d babymake.y
cc -c y.tab.c
lex babymake.l
cc -c lex.yy.c
cc -o babymake lex.yy.o y.tab.o babymake.o
$./babymake < babymake.example$ ./babymake < babymake.example bogus
ERRNO: 2: No such file or directory No rule to make target 'boguser'.

• The program should take it's input from the standard input or by reading a file called "makefile" - is this a choice for the implementer to make? Or should the program read stdin, and if it's empty then look for makefile? Any targets specified on the command line which do not appear in the makefile and do not represent an existing file should generate an error before execution of any rules. Does "generate an error" include aborting, such that no rules are executed? Running each in sequence - missing "action"? Why is the sample input indented? I'll do an edit for punctuation in a bit. – Peter Taylor May 20 '11 at 21:36
• In order. (1) Implementer's choice. Should be more specific. (2) Generate an error means abort; this is a unix utility after all. (3) The sample is indented because I made a strenuous effort to get the tabs in, and MarkDown just doesn't like tabs. Also there is a new sample input that has some comments in. – dmckee --- ex-moderator kitten May 20 '11 at 21:49
• More questions: 1) The target is "newer" than the prerequisite once *they* have been fulfilled. What does this mean? Should this text be talking about building? 2) Under what circumstances can a target be built twice? – Peter Taylor May 21 '11 at 19:51
• 1) Yes and 2) Standard make never builds a target twice, and neither does my reference implementation. But I should probably say that it is or is not allowed. Do you have a feeling in the matter? – dmckee --- ex-moderator kitten May 21 '11 at 20:43
• Saying that it is not allowed is probably best. Otherwise there's potential for stuff to go wrong when multiple targets depend on clean, which will never be built because it doesn't correspond to a file. – Peter Taylor May 21 '11 at 21:15
• I suggest that the golf exercise be to simply output the list of commands to run, not actually execute them. Will make testing much easier. – MtnViewMark May 27 '11 at 0:50
• This is awesome. But I'm too mystified by make to even fathom how it goes about it. I'd never be able to do this without stealing ideas from other posts on the page. But then, I'm an introverted intuitive, intellectuals would probbly have an easier time. :) I haven't checked, but .. I say it's ready to post. Answers may be slow in coming, but they WILL come! – luser droog Nov 23 '12 at 4:45
• @luserdroog my reference implementation builds a directed graph (in the technical sense) of dependencies and then starts evaluating from the named target(s). I can't recall right off if I enforced acycality on the graph or not. I believe that real make insists on it. – dmckee --- ex-moderator kitten Nov 23 '12 at 5:10
• That doesn't semm quite so unfathomable. I suppose the variables and impicit rules are responsible for much of the mystery. – luser droog Nov 23 '12 at 5:45
• This has been inactive for five years. If you're not going to post it, may I? – MD XF Aug 17 '17 at 16:59
• @MDXF I think I'd rather post this one myself, but it may be a few days. – dmckee --- ex-moderator kitten Aug 17 '17 at 19:51

## Verification of solutions to the 3 knishops problem

For the purposes of this question, a knishop is a fairy chess piece which can move to precisely those squares which are not an integer distance away. So knight moves (distance $\sqrt{5}$) are ok, as are bishop moves (non-zero multiples of $\sqrt(2)$) and many more besides.

The 3 knishops problem is to place 3 knishops on an infinite chessboard such that none of them attack each other, but every square other than the 3 they occupy is attacked by at least one of them. A more prosaic formulation is to find three lattice points which form an Erdős-Diophantine graph.

Your task is to write code (see below) which takes three co-ordinates as input and produces a truthy or falsy output: truthy if the co-ordinates are a solution to the 3 knishops problem, and falsy otherwise. The code must be able to handle each of the test cases below in no more than one minute on a reasonable desktop machine.

### The small print

"Write code" should be understood to permit one of the following:

• A program which takes input via stdin and gives output via stdout. The permitted input formats are 6 integers, delimited by your choice of a comma or whitespace, and optionally wrapped in one of parentheses (), curly brackets {}, or square brackets []; or three pairs, each pair similarly delimited and wrapped, and the pairs similarly delimited and wrapped. Examples:

0 0 3 4 12 13
(0,0,3,4,12,13)
{0,0},{3,4},{12,13}
{{0 0} {3 4} {12 13}}
[{0 0} {3 4} {12 13}]


Or using different whitespace for the two types of delimiter:

0 0
3 4
12 13

• A named function, verb, block, or equivalent which takes input as an array of six values, an array of three two-element arrays, three separate arrays of two-element arrays, or six separate parameters; and gives output as a return value.

You may assume that none of the input values or the unattacked points have coordinates outside the range $\pm 2^30$.

### Test cases

input                          output

(0 0) (0 0) (0 0)              false
(0 0) (3 4) (12 13)            false
(5 -5) (8 -1) (2 -9)           false
(0 0) (384 2030) (720 1653)    true


TODO More test cases.

NB I need to code up some naïve approaches and test whether the one-minute restriction is actually relevant. I'm hoping that MathJAX will be enabled; if not, the stuff in dollars will be replaced before posting.

# Write a Connect Four Bot

Your task is to write a Connect Four bot. Your submission must be less than 2000 bytes long. You may not save state. You may not use libraries or external resources that are, at my discretion, related to Connect Four.

Gameplay

Your submission will play against each other submission one hundred times. Each player will play first for exactly half of the matches. Each match flows like:

1. Player 1 drops a red token into a column.
2. If Player 1 has not won, then Player 2 drops a black token into a column.
3. If Player 2 has not won, repeat.

Tokens fall down a column until they collide with another token in the row beneath it or hit the bottom of the board. Your program will be terminated and called anew after each move. You win the match if you connect four tokens vertically, horizontally or diagonally.

The winner of the challenge is the submission with the most match wins at the end of a tournament.

Input

The first command line argument you will receive is the game board. Rows are ; delimited . Cells are , delimited. The first row is the top of the board. A cell contains 0 if unoccupied, 1 if occupied by Player 1, and 2 if occupied by Player 2. The board you receive will always be 7 columns by 6 row.

The second command line argument you will receive is your player number. That means 1 or 2.

Examples:

java ThatBot 0,0,0,0;0,0,0,0;0,2,1,0;0,1,2,1 1

Output

You will print the column for which you would like to move to STDOUT. Columns are zero indexed. The following earns an immediate loss:

• Dropping a token into a full column
• Dropping a token into a column that does not exist
• Failing to output anything to STDOUT within one second

Deliverables

You must submit the following:

• A program
• A unique name
• A method of calling your program via command line
• Any instructions I might need to compile your program. I'll try my best, but my best isn't always good enough.

• Oops, didn't see that, sorry :S I think there might be problems still, as several moves could be hard-coded in. (i.e. the first move(s) is always just the middle column) – FryAmTheEggman Feb 4 '15 at 17:07
• @FryAmTheEggman I am totally fine with a few hard coded moves, but perhaps I should reintroduce the byte limit that I originally had in place. Do you think 500 characters is sufficient? I went ahead and added it back. I also added a restriction on external resources to prevent external hard coding. It's probably a loophole, but one worth covering I think. (I'm in chat btw if you want to discuss.) – Rainbolt Feb 4 '15 at 17:08
• 500 seems fine, but it might squeeze Java / C# entries. I'll see how long a pretty bad bot is over the weekend if you haven't posted yet ;p – FryAmTheEggman Feb 4 '15 at 17:21
• @FryAmTheEggman It will be a little while. I haven't written the controller yet. Thanks for the feedback! – Rainbolt Feb 4 '15 at 17:25
• I took a program that claims to do perfect play and added some timing: the vast majority of its moves take less than 1ms; in about 1 game in 8 it has a single move which takes more than 1s. The longest I've seen was just short of 2s, so with a bit of optimisation and a more modern computer it might well come inside the 1s limit. The byte limit would hit it hard, though: its opening book is 12k. – Peter Taylor Feb 4 '15 at 20:14
• @PeterTaylor Thank you for that. Knowing what you just found out, do you think that the 500 byte limit plus the timing restriction are enough to make the challenge interesting? If someone can solve Connect Four optimally under those restrictions, then at least PPCG has created something worth having, right? I'm just asking because nobody has upvoted the sandbox proposal, so I assume that maybe there are still some concerns about it. – Rainbolt Feb 4 '15 at 20:37
• I got distracted by looking for work on perfect play and didn't post the thoughts I had. I'm slightly confused about the input format: is \n a literal backslash followed by an n, or does it mean a newline character? The latter would be my assumption, but the example input makes it look literal (and wouldn't work if it were newline). I don't think you specify whether the output assumes 0-indexed or 1-indexed columns. I'm not sure whether the rule about external resources is intended to indicate that I can fetch stuff from the web without it counting towards the byte limit. – Peter Taylor Feb 4 '15 at 21:18
• I feel that with a strict byte limit, you're most likely to see mainly versions of min/max or other "simple" algorithms. If you want more interesting or varied players, you may want to relax it. Banning extensive hard-coding is good, but I'd hate for it to come at the expense of creativity. – Geobits Feb 4 '15 at 21:19
• The byte limit and timing restriction between them may be too much: I can't see any approach which attempts a real analysis fitting into 500 bytes except in a golfing language which will struggle with the time limit. Maybe 2kB would be a better compromise. – Peter Taylor Feb 4 '15 at 21:20
• @PeterTaylor 2000 bytes it shall be, then. I changed the row delimiter to ; to eliminate confusion. I added that columns are zero indexed. The rule about external resources was intended to allow you to fetch from existing resources, but to disallow you to fetch from resources that were created after the fact. In hindsight, this might open the door to abuse, so I've removed that allowance. I'm unsure if this leaves the challenge vulnerable or not, so I'll bring it up in chat. – Rainbolt Feb 4 '15 at 21:28
• Discussed in chat and made the change. I think I've addressed all comments up to now. – Rainbolt Feb 4 '15 at 21:38
• I didn't look very closely at that command line. It should be java MyBot (or maybe java -classpath c:\ MyBot, not java C:\MyBot.java. Other that that, looks good. – Peter Taylor Feb 4 '15 at 22:40

# Fortnightly Challenge #4 - Data Structures

Join us in the Fortnightly Challenge Chat to work out the details of this challenge!

Imagine square coloured blocks where each side can be connected to another block, allowing you to move or rotate connected blocks as one. Let's call a collection of such blocks, all connected to each other either directly or indirectly, a group.

Your task is to simulate these blocks via a number of commands which you must implement.

# Commands

All input commands will be given one per line (via STDIN), and likewise all query outputs should one per line (via STDOUT).

• place <x> <y> <colour>: Place a block with a given colour at the specified coordinates.
• remove <x> <y>: Remove the block at the specified coordinates, deleting any connections with it.
• connect <x1> <y1> <x2> <y2>: Connect two adjacent blocks.
• disconnect <x1> <y1> <x2> <y2>: Disconnect two adjacent blocks.
• count: Count the number of groups and print the result.
• move <x> <y> <dx> <dy>: Move the entire group containing the specified block by the given offset.
• rotate <x> <y> <times anticlockwise>: Rotate the entire group containing the specified block anticlockwise about said block by some number (guaranteed to be either 1, 2 or 3) of times
• connected <x1> <y1> <x2> <y2>: Print y if blocks exist at the two given coordinates and they are in the same group, or n otherwise.
• nearest <x> <y>: Print the nearest block to the given coordinate by Manhattan distance (difference in x-coordinate + difference in y-coordinate), in the form <x> <y> <colour>. If there are no placed blocks, print none. If there is more than one closest block, print any.
• colour <colour>: Print all block coordinates with the given colour, each space-separated and of the form (<x>, <y>). If there are no such blocks, print none.
• halt: Terminate the program

## Errors

Commands will always be given with the correct number and type of arguments. However sometimes an operation doesn't make sense, for example:

• Placing a block where a block already exists
• Removing, connecting, disconnecting, moving or rotating non-existent blocks
• Connect or disconnecting blocks which are already connected or disconnected
• Move or rotate commands which end up with two blocks overlapping (with emphasis that only the final state matters — groups which are rotated 2 or 3 times do not need to check for overlaps after each rotation)

If any of the above occur, print Error: <command>. For example, if there is no block at 0,0, then the command remove 0 0 will result in

Error: remove 0 0


Note that queries should never result in an error.

# Scoring

There will be six types of test cases:

1. A test which is biased towards place/remove commands
2. A test which is biased towards connect/disconnect/count/connected commands
3. A test which is biased towards move/rotate commands
4. A test which is biased towards nearest commands
5. A test which is biased towards colour commands
6. An all-rounder test

This is , so the goal is to make your program process the commands as quickly as possible. A leaderboard will be kept for each type of test,, and the winner will be the user with the lowest sum of placements over all tests (e.g. if you came 1st, 3rd, 2nd, 2nd, 3rd, 4th then your score is 1 + 3 + 3 + 2 + 2 + 4 = 15).

The tests and test generator can be found on this Github page, along with a unit tester which will be run for each submission to ensure correctness.

# Rules/clarifications

• To prevent cluttering the leaderboard, each user may provide at most one submission
• No multithreading or parallel processing
• Use no more than 2GB of RAM — this rule is not strictly enforced, but horribly space-inefficient solutions may be disqualified
• No third party libraries (standard libraries are OK)
• All coordinates are guaranteed to fit into a 32-bit int, and all colours are alphanumeric strings

# Example

(in progress)

• 2. Lego pieces/attachable cubes – trichoplax Jan 25 '15 at 21:07
• 5. Controller-mediated build-your-own data structure – trichoplax Jan 25 '15 at 21:11
• A. Lego pieces. – trichoplax Jan 28 '15 at 8:35
• B. Attachable unit cubes (for simplicity) – trichoplax Jan 28 '15 at 8:36
• Winning criteria: – Sp3000 Jan 28 '15 at 23:43
• I. Code golf (fewest bytes) – Sp3000 Jan 28 '15 at 23:43
• II. Fastest algorithm – Sp3000 Jan 28 '15 at 23:44
• Number of cube structures: – Sp3000 Jan 29 '15 at 0:42
• 1. Exactly one structure – Sp3000 Jan 29 '15 at 0:42
• 2. Any number of structures – Sp3000 Jan 29 '15 at 0:43
• Connections/adjacency: – Sp3000 Jan 29 '15 at 0:43
• A. Connections should be explicitly given via a function call – Sp3000 Jan 29 '15 at 0:44
• B. Each cube is connected to the cube it was built off – Sp3000 Jan 29 '15 at 0:45
• Moving to 2D might simplify rotations greatly, while retaining enough complexity to be worth a challenge. – user16991 Feb 5 '15 at 1:49

# Bitstring Family Trees

This challenge is reproduced from memory and my own solution, from a challenge that was posted in the job-application section of http://itasoftware.com before they were bought by Google. I reached out to ITA and Google a few years ago, after the acquisition, to ask to re-post this here (and on codegolf.com when it existed) and never heard back from them.

A bitstring is a string of 1s and 0s. Bitstrings reproduce asexually through a mutation-prone process, producing a child that is a copy of its parent but with each bit flipped with 25% probability. Starting with a list containing one bitstring, we repeatedly select one bitstring from the list at random, produce its child, and add that child to the list. This produces a list of bitstrings, each of which (except the first) has somewhere earlier in the list a parent from which it was mutated.

Now, the challenge. Your program will be presented with a list of bitstrings produced as described above, but the order of the list will be shuffled. You are to calculate the least improbable family tree for the given bitstrings. If there are two or more such trees, choose any of them.

Your input can be in any useful format, including as a list/array of lists/strings as a function parameter or in a variable, already existing on the stack for a stack based language, or from stdin with delimiters but not operators, so four four-bit strings might be "1010\n1001\n1011\n0010" or "[1010,1001,1011,0010]" or even "4 1010100110110010".

Your output can be in any unambiguous format. The canonical format is a list of integers, where the nth integer in the list is the index of the nth provided bitstring's parent in the original list, and a sentinel value for the root entry. Another acceptable form could be an actual tree data structure. Either of these might be returned from a function, printed to stdout, left in a variable, or left on the stack of a stack based language.

The above two provisions should be interpreted with the context that this challenge is not about golfing the input and output code. It's about golfing the algorithmic logic.

For the example input above of 1010,1001,1011,0010 the most likely family tree is that the first entry is the root, the last two are children of the first, and the second is a child of the third, all three mutations involving a single bit flip out of four bits.

With the challenge I will provide a few data sets of different sizes (10 10-bit strings, 100 100-bit strings, maybe bigger) with their solutions.

• Could you give a more precise definition of 'most likely'? – feersum Jun 7 '15 at 21:30
• If two family trees are equally likely, can either be output, or would you prefer a rule to specify which one must be output? – trichoplax Jun 7 '15 at 22:18
• Would it be interesting to have the 25% probability provided as an input p, or would keeping the parameter fixed allow for more golfing opportunities? – trichoplax Jun 7 '15 at 22:20
• @feersum I'm not sure what you mean. Highest probability? Least improbable? – Sparr Jun 8 '15 at 2:45
• @trichoplax I hadn't considered that. I guess I'd accept either. I'll mention that. The probability in the original question was 20%, but I think a non-repeating decimal in base 2 will be much more golf-friendly. – Sparr Jun 8 '15 at 2:46
• With respect to @feersum's question, I see at least two subtleties. Firstly, what assumption should be made about the distribution of the initial bitstring? Secondly, the "family tree" isn't in bijection with the sequence of random selections. The first one needs to be addressed explicitly; the second is probably best addressed with a worked example which calculates the probabilities for each possible sequence and then sums them over the family tree corresponding to each sequence. As an additional point, an important corner case will be one where the bitstrings aren't all distinct. – Peter Taylor Jun 9 '15 at 11:22
• @PeterTaylor The initial bitstring is a sequence of bits chosen independently and uniformly at random. I am unclear on your second point. Do you mean that it's possible for the family tree produced at random to not be the one most likely to have produced a given result set? That makes sense, but seems obvious. I can work out the 4x4 example by hand with probabilities for each of the 6 possible family trees, if that would clarify things? – Sparr Jun 10 '15 at 15:44
• I agree that it's obvious, but it is often a good idea to state the obvious, because otherwise it can be overlooked. For example, it's also obvious that the 4x4 example must have more than 4! = 24 possible family trees... (I think it's 64 possible trees, so maybe that was just a typo). – Peter Taylor Jun 10 '15 at 16:28

# The Virtual Prisoners king-of-the-hill

### Background

The year is 2251. You are a self-evolving KOTH bot, in the mysterious land known as Programming Puzzles and Code Golf. To evolve, you need permissions, and to get permissions, you need reputation. You decide that the best way to do this is to take over all of the questions to gain as much reputation as possible. The only problem? Every other bot has decided to do the exact same thing.

### Game Explanation

Each round is battled on a question, with 11 vote nodes, between you and your enemy. The board starts as this:

A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11


A is player A's nodes, B is player B's nodes, and N is a neutral node.
Each turn, you may:

• Vote on a vote node. If both players vote, nothing happens. If one side votes:
• and the node is controlled by no-one (neutral), it becomes that side's.
• and it is controlled by the voter's enemy, it becomes neutral.
• and it is controlled by the voter, nothing happens.
• Guard a vote node. This guards the node from votes (friendly or enemy) for 2 turns.
• Use your 'power'. The powers are listed below, including how to use them.

Your side wins if it controls at least 2/3rds (66%) of the vote nodes.

10000 rounds will be run, and the winner of the KOTH is whichever bot has the most wins (in the event of a tie, or indeterminate outcome, more matches are run until a clear winner is decided.)

### How Your Bot Should Work

It should accept as command-line arguments:
B A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11
Where A denotes Player A's nodes, N denotes a neutral node, B denotes Player B's nodes, and the first argument (B in this case) is the player your bot is. (This is decided randomly, your bot should work regardless.)
It should return one of the following (powers are general rules):

• V-4, vote on node 4
• G-3, guard node 3
• P-N, use power 'Neutralize'
with or without a trailing newline.

### Powers

Intended to give bots a small boost. If X was your power, you would use P-X. You may only have one power per bot.

• N - Neutralize: Turn 2 random nodes to neutral ones.

• R - Rebellion: Pick a random node, and randomly turn it to a friendly, neutral, or hostile node.
• S - Swift Strikes: Pick two random nodes, and vote on them.

Here are the extra rules:

• The bots must fully run offline.
• The bots may not attempt to read any files, including their own source code.
• The bots may not tamper with, hack, or destroy other bots.
• The bots must return one of the three commands (V, G, or P). If they do not, they forfeit their turn.
• The bots must not be targeting other bots specifically. (Beating general strategies is welcome.)
• You may update your bot as often as you like, but bots that are updated very frequently with no good reason (i.e, fixing fatal errors is a good reason) will be disqualified.
• Your bot must take under 90 seconds for it's turn. If it takes longer, it will be disqualified.

### Submission contents

• The code for the bot
• The language it is written in (and a link to an offline interpreter, if necessary)
• How to compile and run your bot

If you do not include all of the required items in your submission, you will be notified, but your bot may not compete until this is fixed.

### Example Match

Matches are organized between 2 randomly-selected bots. Here is an example, with bots A and B:
The board begins as this:

A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11


Bot A makes his move, voting on N4, then Bot B votes on N5:

A1 A2 A3 A4 B5 N6 N7 N8 B9 B10 B11


Node 4 becomes A4, and it is now controlled by Bot A. Likewise, node 5 becomes B5.

A votes on N8, and so does B:

A1 A2 A3 A4 B5 N6 N7 N8 B9 B10 B11


Why did nothing happen? That's because both bots voted on the same node - cancelling out each other's effects.

When one bot controls 66% or greater of the nodes, that bot gains a win and the other bot gains a loss.

The game ends after 1024 turns, to prevent any bots that wait around forever. Whoever has the most nodes afterwards wins, or a draw if they have the same amount.

• I will be submitting an example bot written in Python as part of my challenge. You are free to use and modify this bot for your submission.
• If your bot gives invalid output (not of the form C-A, where C is the command and A is the argument), the bot forfeits its turn. If it does, you will be notified, and your bot will be removed until it is fixed.

## Meta Questions and Notes

• Are there any loopholes?
• Should I add/modify/delete some of the powers?
• Is something too simple/confusing/uninteresting/overpowered?
• Should bots be able to see which nodes are and are not guarded?
• Should I limit people to one bot? If not, I will prevent the same person's bots from battling each other.
• I have thought of the following alternative way to win matches:
• The game lasts 1024 turns. Whoever has the most nodes at the end wins.
• If, at one point, one bot controls all 11 nodes, that bot automatically wins.
• Would this be a better win condition?
• I have a few questions. 1) If I make a new node, will it be neutral? 2) How are the matches organized? If there are, say, 5 submissions, does each pair have a separate battle, after which you count victories, or do they somehow work in teams (as the title suggests)? 3) With some strategies it may be that the game runs forever. You should probably add a time limit (some N turns), after which the game automatically ends in a draw, or a win for the player controlling the most nodes. – Zgarb Apr 7 '15 at 15:38
• @Zgarb Thanks for your feedback! I've included a section on how the game works. – ASCIIThenANSI Apr 7 '15 at 15:53
• Could you add C# (or .NET in general?) – LegionMammal978 Apr 7 '15 at 15:55
• @LegionMammal978 How do you install that on Linux? The list is mostly because I can't run a lot of things like GolfScript, but I'd be glad to, if you can tell me where to find it. – ASCIIThenANSI Apr 7 '15 at 15:56
• @ASCIIThenANSI you could use Mono. I'm mainly just looking for C#. – LegionMammal978 Apr 7 '15 at 16:02
• @LegionMammal978 Oh, OK. Turns out I installed it for an earlier purpose, thanks for your help! – ASCIIThenANSI Apr 7 '15 at 16:09
• It's not complete, but this question has instructions for running a number of languages. – Peter Taylor Apr 15 '15 at 22:15
• @PeterTaylor Thanks for the link! – ASCIIThenANSI Apr 16 '15 at 12:57
• Maybe add a clock time limit for each turn, so bots don't simply run an endless loop blocking you running the simulation? – Paŭlo Ebermann Oct 11 '15 at 8:33
• @PaŭloEbermann I'll watch each of the simulations (with output on what the bots are doing), and any bot that takes too long is disqualified. – ASCIIThenANSI Oct 12 '15 at 14:04

I nearly posted this without sandboxing, but thought it was perhaps too trivial - comments welcome. I was considering perhaps making it too with no digits [0-9] in the source code.Done.

# Golf the numbers round a dartboard

For those of you not familiar with the game of darts, a standard dartboard looks like this:

This challenge is simple - output the sequence of numbers starting from 20 moving in a clockwise direction:

20 1 18 4 13 6 10 15 2 17 3 19 7 16 8 11 14 9 12 5

To make it a bit more interesting, the digits [0-9] may not appear anywhere in your source code.

• Your entry must not accept any input and it must output this list in exactly this order.
• The formatting of the list output may be whatever is convenient for your language.
• You must not use any builtins designed explicitly to generate this sequence.

OEIS fans may like to note that this is sequence has an entry.

• I like the restricted source version – quintopia Dec 9 '15 at 19:16
• @TimmyD Link added. I'm surprised we don't have an OEIS tag - I guess it wouldn't really add much. – Digital Trauma Dec 9 '15 at 20:18
• @ quintopia - yes, I think that's probably the way to go - edited. – Digital Trauma Dec 9 '15 at 20:19
• I was able to do this in CJam in 26 bytes using character to int conversion (it only didn't work online for 13 because it's character is carriage return.) Should this be allowed? goo.gl/JxEcjo . Also, in CJam 1,2,3 and 10-20 are single letter constants. Should those be allowed? – geokavel Dec 10 '15 at 5:58
• @geokavel yes, and yes. – Digital Trauma Dec 10 '15 at 6:16
• This is just asking for string compression, especially since digits can't be used even indirectly. – xnor Dec 10 '15 at 19:32
• @xnor to discourage that, maybe restrict entries to printable ASCII (or give a bonus of *log 95/log 256 for using only printable ASCII)? – lirtosiast Dec 10 '15 at 23:40

# Verify a game of Morpion Solitaire

Morpion Solitaire is an interesting, unsolved "single-player game". (The linked site lists several variants - we're talking about 5T here.) It has been proven that solving or even approximating it is NP-hard. But we're going to do something simpler here: your challenge will be to verify whether the game has been played correctly.

The rules are fairly simple. You start on a regular (infinite) grid, with 36 intersections marked in the following shape:

Now a move consists of drawing a straight line segment, orthogonally or 45 degrees with the grid, through four marked and one unmarked intersection. The unmarked intersection will then be marked for future moves:

The lines may cross or touch, but they must never overlap (notice that the last move shares an endpoint in a straight line with an earlier move, but does not overlap with it). The goal of the game is to make as many move as possible. The world record is at 178 moves.

Because the grid gets very messy after a while, it becomes very hard to reconstruct a game. People work around this problem, by writing consecutive numbers into the intersections they add. However, even when this is not done, it is always possible to verify the validity of game.

## The Challenge

You're given an ASCII representation of a played game of Morpion Solitaire (the game may or may not be finished). Every other cell represents an intersection, which can be either unmarked (.), one of the initial intersections (o) or one of the intersections added by a move (#). All other cells are either spaces, or one of -, |, /, \, X indicating that a line-segment was drawn across the two adjacent intersections. The example above would look like this:

. . . . . . . . . . . .

. . . . o-o-o-o-# . . .
|/     /
. . . . o . . o . . . .
/|    /
. . . # o . # o . . . .
/  |  /
. o-o-o-o-# . o o o o .
/    |/
. o . . # . . . . . o .
|
. o . . # . . . . . o .
|
. o o o o . . o o o o .
|
. . . . o . . o . . . .
|
. . . . o . . o . . . .

. . . . o o o o . . . .

. . . . . . . . . . . .


Output a truthy value if the game represented by graph can be played by following the rules, and a falsy value otherwise.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may assume that the initial intersections always form the cross shape displayed above (although I doubt any answers will be affected by this).

Your code should solve any of the test in less than 5 seconds. This should not be an issue as very efficient solutions exist.

Standard rules apply.

## Sandbox Notes

• The simplest representation for parsing would be to give either the endpoints of each line as cartesian coordinates, or one endpoint and a direction (either one of 8 directions, or it could be standardized to one of 4 directions if the N/E/NE/NW is always the endpoint given.) Checking would then be fairly straightforward: start with the empty grid and see which lines are allowed, until all are exhausted. – Level River St Dec 21 '15 at 9:34
• The ASCII art representation will require more effort for parsing: I think it's unambiguous because you can identify endpoints by looking for for intersections which don't have opposite pairs of |_\/, but it could take quite a few parses through the file. You would also need some way of identifying the start points. – Level River St Dec 21 '15 at 9:35
• @steveverrill There will be no information about endpoints in the input. In a finished game (without numbering) you only have individual line segments (four of which make up a move). That's why I think an ASCII representation is simpler than a graph, where you need to piece together manually which edges form a straight line of four segments. I also think an ASCII representation doesn't necessarily need to be parsed at all: I think it can be solved straight via manipulation of the character grid (in fact, this should be doable in Retina). – Martin Ender Dec 21 '15 at 9:45
• 1. It would be clearer to talk about drawing a straight line segment through 4 marked and one unmarked lattice point, as "straight line" often implies that it's infinite. 2. It seems that the lines must be axis-aligned or at 45 degrees to the axis. If so, it would be good to state that explicitly in the description of play. 3. The page linked in the first sentence is very uninformative. I assume you did it because the diagrams on the Wikipedia page are for a different initial setup, but there must be some better external link. – Peter Taylor Dec 21 '15 at 9:48
• In that case I would go for the ASCII art representation. It also depends to some extent on which is the most convenient way for you to obtain / generate test cases. – Level River St Dec 21 '15 at 9:51
• @PeterTaylor Thanks, I'll edit those suggestion in. As for the page I linked, did you see the navigation in the left iframe? (I overlooked that at first.) I'll link to Wikipedia as well though. – Martin Ender Dec 21 '15 at 9:52
• I agree with Peter that the website is a bit of a mess. There are many variations of the game, so I think you should state that this is the 5T variant (identified by the fact that Christopher Rosin holds the records for 5T at 178 moves and 5D at 82 moves.) It took me a while to work out why Marc Bertin at 216 moves in 1974 was not the record holder: (He was playing 5T+.) Only the 5T (endpoints of parallel lines touching allowed) and 5D (endpoints of parallel lines must be disjoint) variants are unsolved according to the website. – Level River St Dec 21 '15 at 9:57
• The person who wrote that site needs to be dragged kicking and screaming into the 21st century. But I'd prefer a link to morpionsolitaire.com/English/Rules.htm and the navigation be damned than a link to the front page. – Peter Taylor Dec 21 '15 at 10:01

# Four-Byte Bloom Filter

Bloom filters are cool. In the words of that Wikipedia article:

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set".

The motivation behind Bloom filters is that, by giving up perfect accuracy, the amount of memory necessary can be dramatically decreased.

A Bloom filter takes the form of a set of bits, along with a set of hash functions. To insert something into the Bloom filter, calculate the N different hashes and flip those bits to 1.

initialization
00000000

letter P maps to 1 when using hash function F and 6 when using hash function G
01000010


letter h maps to 6 and 4
01001010


To test if an element is a member of a set, perform the hashes and check to see if those bits are 1. If not all of them are 1, then it can't possibly be a member of the set. If they are all 1s, then it could be a member.

letter W maps to 0 and 4
01001010
^   ^
W is not a member

letter P maps to 1 and 6
01001010
^    ^
P could be a member (it is)

letter i maps to 4 and 1
01001010
^  ^
i could be a member (it is a false positive)


As more elements are added to the set, the probability of false positives increases. In large-scale applications, a Bloom filter with a small error rate is still an order of magnitude smaller than an exact database. Below is a neat diagram from this great article on probabilistic data structures.

In this challenge, you will implement a miniature Bloom filter. A really, really small Bloom filter with 32 bits. Your data type will be the 94 non-whitespace printable ASCII characters.

Functionality

The Bloom filter will have 32 bits and 2 hash functions. It is up to you what those two hash functions are, they simply must be decently independent of one another. (Sandbox note, should I specify the hash functions?). Your program will be asked to do two separate tasks:

• Given a current state of the bloom filter and a list of characters, add those characters to the filter and output the new filter state
• Given a current state of the bloom filter and a list of characters, test those characters for membership and output a list of truthy (could be a member) or falsey (definitely not a member) values.

Formatting specifics

Input consists of the current state, an operation, and a list of characters. The Bloom filter state will be represented as a string of 8 hexadecimal characters. This will then be followed by either + for adding or ? for membership testing. Finally, there will be a list of between 1 and 94 characters (printable non-whitespace ASCII) as data points.

Output will either be the new state, as 8 hex characters, or a list of truthy/falsey values.

## Example I/O

This represents adding the characters in my username to a blank filter
00000000+PhiNotPi
This is a possible output (7 bits have been permanently flipped)
48a01030

This represent adding the character 1 to the current filter
48a01030+1
This is a possible output (9 bits flipped so far)
48a01074

This represents testing for membership of Phi
48a01074?Phi
Output must be all true since they were added in earlier
[True, True, True]

This represents testing for membership of 12345
48a01074?1234
Output must be true for 1, but not necessarily false for the others
[True, False, False, True, False]

• You should specify the hashing function, if you don't want the hashing function is a mod 32 or worse, return 4. – Akangka Jan 14 '16 at 14:34

# The largest convex polygon

Given an input of at least one coordinate pair on the Cartesian plane, determine the largest number of sides a convex, non-self-intersecting polygon formed from those points can have.

A convex polygon is a polygon such that there is an angle strictly less than 180˚ and greater than 0˚ between each pair of consecutive sides. Note that if three points are collinear, they still only form one side. Two sides cannot have a 180˚ angle between them.

The ordinate and abscissa of a coordinate are not necessarily integers, and they can be positive, negative, or zero.

If there are less than 3 points, or if the points inputted cannot form a convex polygon, the program should output 0.

Test cases

(0,0) (1,1) (3,4)
==> 3

(0,0) (-1,-1) (5,5)
==> 0

(-1,0) (1,0) (0,1) (5,5) (-5,5) (0,-5)
==> 3

(-3,2) (4,6) (-1,2) (0,4) (5,-3) (-2,-2) (1,1)
==> 5

(0,0) (10,0) (10,10) (9,1) (10,4) (9,6) (5,4)
==> 5


Here are pictures for the test cases, in order. Note that solutions are not necessarily unique. (Made with Geogebra)

• For the third test case, can't you get a four-side polygon (-5,5) -- (5,5) -- (1,0) -- (-1,0) -- (-5,5)? (or (0,-5) -- (-1,0) -- (0,1) -- (1,0) -- (0,-5)) – David Feb 16 '16 at 0:09
• @David Thanks for catching that. I will fix it tomorrow, – Arcturus Feb 16 '16 at 5:06
• This could probably use some more test cases where the result is not the convex hull... if possible even one where none of the points of the convex hull are part of the solution. – Martin Ender Feb 16 '16 at 7:45
• @MartinBüttner The last test case is not the convex hull, as (10,0) and (10,10) are not included in the output polygon. – AdmBorkBork Feb 16 '16 at 15:08
• @TimmyD The emphasis in my sentence was on "more". ;) (I admit that may not have been obvious.) – Martin Ender Feb 16 '16 at 15:09
• @MartinBüttner I read it as "This could probably use some more test cases, [such as] where the result is not the convex hull" ... yay, English. – AdmBorkBork Feb 16 '16 at 15:15
• @TimmyD I like ambiguity more than most people. – Martin Ender Feb 16 '16 at 15:22

# Introduction

The classic snake game where bots control the snakes. Can you create a bot that out lives the rest?

Snakes will enter the arena and hope to survive. Eat pellets and grow in length. Can you force your competition to crash and die while you survive?

See video for visuals of my simple bot playing against itself. I am sure you can do better!

# Features

• Real-time graphics provided by Love2D
• Multiple snakes per game
• Solo game as well
• Humans can play too!
• Highly configurable settings
• Supports any programming language that can use sockets.

# Requirements

• Love2D: 2D game engine written for Lua
• Socket-compatible programming language
• Controller: The main controller for this challenege

## Optional

• Lua winapi: Handy way to spawn processes in the background

# Controller Contents

1. main.lua: Main loop for Love.
2. snake.lua: Support library for game mechanics
3. config.lua: Configuration settings.
4. bots\: location of externally-defined bots
1. simple.lua: Example bot written in Lua

# Executing

Run the love2d executable on the controller directory

love.exe <location_of>\battlesnake

or

[Recommended] Use ZeroBrane Studio with the 'Love' interpreter. Change your project directory to where you installed the controller, and then run the script in ZeroBrane. You'll still have to install Love separately.

# Configuration

All configurable options are located in the config.lua file in the controller. The options are detailed in that file itself.

# Rules

General snake rules apply. Hit something and you die. This includes the walls, other snakes, or even yourself.

Collisions happen before the board is updated. Therefore, if you move to a spot where another snake's tail is, it will still cause a collision. Even though it could be moving away that turn. If two or more snakes enter the same spot the same turn, they all collide with each other.

Eat a pellet and gain points. You also grow in size for a number of turns. Your head continues moving but your tail stays stationary until you stop growing.

# Mechanics

The game uses a server-client model, where the main game loop is the server and each snake is a client. The game communicates to each snake over TCP through an assigned port. The default host is the localhost, no external networks are required.

When the game starts, it will start each snake (aka bot) by starting its associated program and sending the IP ADDRESS and PORT and PLAYER ID to it as input arguments:

bots\someBot.exe 127.0.0.1 52311 1

The main server then waits for a socket connection from that bot at the given IP and PORT. If the connection times out, it will error and the game will not start. If the server receives a connection from the bot, it will proceed on to the next bot.

Once all bots are started and connected to the server, the game will be generated. Bots are expected to block until receiving data from the server. Typically this is just an infinite loop with a blocking socket.receive() call at the top of the loop.

## Board

The game board can be of any width and height. The coordinate system starts at x = 1, y = 1 at the top-left. Increasing x values go left-to-right and increasing y values go top-to-bottom. The board has hard walls, hitting them will kill your snake. (Lua is 1-based, that is why it starts at 1)

## Order of Events

1. First the game settings are broadcast to all bots

1. Board Information

bi width,height

Where width and height are integer values

2. Pellet Location

p x,y

Where x and y are integer values >= 1 and <= to their respective width and height.

3. For each bot

• For each body part, starting at the head and going to the tail

si snake_id x,y

Where snake_id is an integer value, and x and y are as described before.

ready

All bots are initialized by now, so the next command will be from the main game loop.

2. Main Loop

1. For each tick (tick is when all snake movements will be applied)

1. Server will broadcast to each bot

mov

The bot needs to respond to this request with a direction to head in

• r Head Right
• l Head Left
• u Head Up
• d Head Down

If the bot doesn't respond within a specified time, it will continue to move in its previous direction. (Previous direction is r on the first turn)

The bot should send a single char back, nothing more will be parsed.

2. Check End Game Conditions

If the game ended this tick each bot will be sent either a quit or nil message from the server. Each bot is expected to clean up after itself when it receives this signal.

3. Updated Pellet Info [optional]

If a pellet was eaten this tick, a new pellet packet will be broadcast to all active bots

p x,y

4. Server broadcasts snake deltas that were applied this turn

s snake_id new_x,new_y,removed_x,removed_y

Where all parameters are integers. new_x and new_y are the new head location of a given snake.

If removed_x and removed_y are >= 1, this is where the tail used to be, so each bot knows the updated board.

If remove_x and removed_y are == -1, then that bot is actively growing in size, so its tail didn't move.

If a snake died this tick, its deltas will not be broadcast. It is up to the bots to remove the body from their game state.

See the example bot for details

# Matches

Games are grouped together in best-of matches. For the purposes of the bots, they do not need to understand the concept of a match. The bot that wins the required number of games in a match is declared the match winner.

# Scoring

1. Scoring

• Match winner: +2500 points per match
• Last Man Standing: +1000 points per game
• Pellets Eaten: +50 points per pellet
• Game Ticks Alive: +1 point per tick

If two or more bots enter the same square on the same tick, they all die. If this square happened to be the pellet, none of those bots will be rewarded the pellet points. However, the pellet will be "consumed" and a new location will be generated for the remaining bots to eat.

If there is a tie at the end of the game among the bots, the game is a wash. A new game will be started.

2. King-of-the-hill Scoring

This challenge will combine two parts: A solo effort and a classic king-of-the-hill part.

Each bot will be given the same random seed at the start of the competition. There will also be imposed a maximum time between eating pellets to prevent bots from going around in circles to farm points.

1. Solo

Each bot will enter into a 10-game match to see how long it lasts and how well it eats by itself. The scores of each game in the match will be summed to compose its final Solo-score.

2. King-of-the-hill

All the bots will enter into a best-of-39 match. If the game ends and there is still a final living bot, the game still end at that point. That bot will be given the last man standing bonus.

The scores of each game will be summed and composed into the snakes final KOTH-score.

3. Final Scoring

All the bots will be ranked in each part separately. Ties in ranks are permitted at this stage. Then their positional rank in each part will be summed together to give their final score. The bot with the lowest combined rank wins!

In case of a tie at this level, the bot with the better KOTH rank will win. If still a tie, the bot with the better Solo rank will win.

## Sandbox Questions

My biggest concerns

1. Requires a few third-party programs to work. So that will limit the number of people who enter.
2. Requires sockets. I couldn't figure out a good way with Lua\Love2d to have bidirectional pipes with STDIN and STDOUT. So I thought sockets would be the best alternative to open the challenge to as many people as possible.
3. Too hard?
4. Haven't optimized scoring yet.

## Count the Cats code-challengeimage-processingtest-batterycounting

This is a cat:

Specifically, that is my cat. She is my only cat. And, in that image, there is only one cat: her.

These are also cats (image credit):

In that picture, there are two cats. It is relatively easy to count them, thanks to their distinct coloring.

This is a picture of 5 cats (image credit):

It's harder to differentiate the cats because of their similar coloring, but there are definitely 5.

This is a landscape (image credit):

There are no cats in this image.

## The Challenge

Given an image, output the number of cats in the image.

## Rules

• Submissions must output and terminate within 1 minute for a single image.
• Any common image format is acceptable for input, as long as no additional data (such as the number of cats present in the image) is encoded in the format.
• Submissions must be fully deterministic, and make a genuine attempt at counting the cats. Outputting a random number or a consistent but unrelated number (such as the value of the last hex digit of the SHA-256 hash of the image data) is not allowed.
• The images in the test cases will contain no animals besides cats. There may or may not be humans in the images - they are not cats, and thus should not be counted as cats.

## Scoring

The score for a single image is the square of the difference between the true number of cats in the image and the output of the submission ((actual - output)**2). The total score is the sum of all of the individual scores. The submission with the lowest score wins.

[scoring images TBD]

• I feel like this is probably a dupe of either the goat question or the rice question. I'm not sure that it being a test battery question or the precise subimage to identify really makes it much different from these other ones? – FryAmTheEggman Jun 23 '16 at 19:17
• @FryAmTheEggman I don't think it's a dupe of goats - goats wanted a boolean classification, where this one asks for a count. The rice question is closer, but there is a possibility (and perhaps a need) for different approaches, given that a) cats can overlap, b) cats come in different colors, and c) cats have much more complex shapes than rice grains (which are ellipses). – Mego Jun 23 '16 at 19:19
• "Submissions must output and terminate within 10 seconds for a single image." I don't know about that, counting the amount of cats and only cats is a rather difficult task already, a 10-second limit seems really small. Perhaps a couple minutes? – Downgoat Jun 23 '16 at 20:03
• Also, I think there should be some specification for how the cats would appear. At least having the full cat's face showing would make this challenge more approachable. If a test-case shows the back of a cat that seems a bit too difficult for a PPCG challenge. Also: Will there be a mix of cats and other animals? Are built-ins allowed (I'm very sure there's mathematica builtin)? – Downgoat Jun 23 '16 at 20:07
• @Upgoat The time requirement can be extended. The number of cats will always be clear to a human viewer with 20/20 eyesight and adequate attention for detail. The challenge is about counting cats, not about picking out camouflaged cats, so there won't be any excessive trickery in the test images. Built-ins are allowed, but I'm on the fence about whether or not I'm going to allow them to be competitive, since Mathematica is likely the only language that would benefit from built-ins. – Mego Jun 23 '16 at 20:12
• Showing a picture of a dog and expecting a zero output doesn't seem fair. Writing a program that distinguishes between dogs and cats seems like a difficult enough task as it is, and you have it here as sort of an afterthought. Empty images should be emptier, imo. – Liam Jun 25 '16 at 22:45
• @Liam On the other hand, if all of the test images consisted of 0-5 cats and no other animals, it would be too easy to get a perfect score. Having harder test cases means that submissions will have room for improvement, and thus there will be more competition. – Mego Jun 27 '16 at 1:46
• Is fitting allowed? I think learning will probably be the most practical approach to this challenge. Though this does need some specification before it's ready to post imo and limits on the possible inputs as I doubt any answer will be able to conform to the wide variety of things cats can be e.g. color, position, shape, size, direction, camera position, etc. – Downgoat Jun 27 '16 at 5:15
• @Downgoat As per usual with these types of challenges, optimizing for the test cases is not allowed. However, given that a ML-oriented approach would be interesting and perform well on this challenge, I'd be willing to include a training set, separate from the scoring set. As for limits on possible inputs, I'm trying to work out a good set. – Mego Jun 27 '16 at 5:41
• I think the part about the dog makes this a chameleon challenge -- distinguishing a cat from a dog is much harder than identifying and counting cats on an image free of distracters. – xnor Jun 27 '16 at 23:48
• @xnor On the other hand, without the distracters, it would likely be too easy to get a perfect score. – Mego Jun 28 '16 at 2:48
• Distinguishing a cat from a dog on a picture already requires decently advanced algorithms (CNNs are the first that come to mind) which in turn require a LOT of training data to generalize decently. – Fatalize Jun 29 '16 at 9:09
• @Fatalize Would using non-mammilian animals (such as lizards and birds) be better in your opinion? – Mego Jun 29 '16 at 9:10
• @Mego It probably would be easier because it wouldn't force people to use machine learning techniques (You could use texture comparison to distinguish feathers from scales, color detection, etc.). Counting the number of each is an added difficulty that makes it maybe too difficult as a whole. Only classifying is easier but probably a dupe of the goats challenge. Only counting might be good though. – Fatalize Jun 29 '16 at 9:14
• The problem with this scoring technique is that even if people make legit attempts at counting the cats, they will try to optimize their code for the limited test set, which will make their approaches less general on new data. One solution could be to provide a validation set (for say 2 weeks if that's the time frame in which you can post an answer) on which people can evaluate their answers, and choose the winning answer based on a test set that was not available during those 2 weeks containing new images. – Fatalize Jul 1 '16 at 13:27