What is the Sandbox?

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

To post to the Sandbox scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, replace the post here with a link to the challenge and delete it.

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

The Sandbox works best if you sort posts by "active".

You can also search through the sandbox by qualifying your search with inquestion:2140. Here are some examples:

(The Submission Directory has been removed. Go here if you have concerns about that.)

Reminder: to add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]. – Crissov Aug 12 at 11:15
Rofl the downvote on the sandbox – Alex A. Oct 21 at 18:31

744 Answers 744

EDIT: This challenge is looking for someone to either writefinish and run an arena server, or someone that wants to rephrase the challenge so that an arena server is not needed and who is also prepared to run entries manually. Both options turned out to be more complicated for me than I originally envisioned. To make a long story short: it's yours!

It's Life, Jim, but not as we know it

You probably know Conway's Game of Life, the famous cellular automaton invented by mathematician John Conway. Life is a set of rules that, together, allow you to simulate a two-dimensional board of cells. The rules decide which cells on the board live and which ones die. With some imagination, you could say that Life is a zero-player game: a game with the objective to find patterns with interesting behavior, like the famous glider.


A zero-player game... Until today. You are to write a program that plays the Game of Life - and plays it to win, King of the Hill-style. Your opponent (singular) of course tries to do the same. The winner is either the last bot with any live cells, or the player with the most live cells after 5 minutes of clock time.

Game rules

The rules are almost the same as normal (B3/S23) Life:

  • A live cell with fewer than two friendly neighbors dies from starvation.
  • A live cell with two or three friendly neighbors survives.
  • A live cell with more than three friendly neighbors dies from overpopulation.
  • A dead cell with exactly three neighbors of the same player comes alive to fight for that player provided there are no enemy neighbors.

...but after each generation, both you and your opponent get the opportunity to intervene. You can awake up to a maximum of 30 cells to fight for you. (Who goes first is decided by the server.)

The board is a 1024×1024 cell square. All squares are initially dead. The borders do not wrap around (this is not a torus-shaped world) and are permanently dead.

This is is a contest in the spirit of Battlebots and Core Wars. However, unlike those two, you are supposed to run your implementation on your own machine. You fight the other contestants on a central arena server.


The arena server speaks a simple, compact TLV protocol over TCP. Messages have the following format:

^ Type (1 byte, ASCII)
 ^ Length (1 byte, unsigned int)
  ^ Values (Exactly length bytes long)

The meaning of the value depends on the type of message. For example, for a move that sets (781,991) and (214, 1), the message would become (hex-encoded):

--                   = The type (0x4D = M in ASCII)
  --                 = Length (8 bits)
    --------         = 718 and 991 encoded as network-order 16-bit integers
            -------- = ditto for (214,1)

You're probably going to want to write a client. Here's how:

  1. Connect to the central arena server.
  2. Send an I​dentification message with an identification string (up to 250 bytes of UTF-8).
  3. Have your bot wait for a game to begin. The arena hosts one game at a time. You will fight either another contestant's bot, or a training round against my entry, which is not included in the competition.
  4. The game starts when you receive a S​tart message. Included in the message is the name of your opponent, which will start with "Training/" if you're up against the training bot.
  5. When you receive a M​ove, apply it to your board. Moves are encoded as arrays of pairs of 16-bit unsigned integers. For each pair, set the cell at that X/Y-coordinate to the enemy's 'color'.
  6. When you receive a G​eneration marker, evolve your current view of the game board one step according to the rules above.
  7. When you receive a T​urn message, it's your turn. Reply with a Move as soon as possible. (Don't want to interfere? Send a Move message with zero moves.)
  8. When you receive a B​ye message, the game is over and you can disconnect. The value will tell you your score and your opponent's, in that order, as a pair of 32-bit unsigned integers.
  9. Reconnect when you're ready for another round.

Note that the server will not send you the entire state of the board at any time for bandwidth reasons. You'll have to keep track of the evolving yourself. (Here are implementations of normal Life in many languages. You could probably base your implementation on one of those.)

Competition rules

  • You should I​dentify as name/bot, where name is your StackExchange user name and bot is a PG-rated but otherwise very intimidating name for your implementation (Glider of Doom? DiveBomber? Pufferfish?)
  • If your implementation fails to follow the protocol, you'll be disconnected - and the game will be forfeited.
  • You are not allowed to willfully take advantage of a fault in the arena server.
  • Have your AI decide on moves in a sane time. Calculate strategies in advance if at all possible so you'll be able to send your next move as fast as reasonably possible.
  • Finally, please be nice to the server. It's there for your enjoyment.
  • Not following these rules can lead to disqualification.


The bot with the largest KD spread, that is, the largest positive difference between the amount of wins and the amount of losses, wins.

That's great: it makes it clear that it's binary data and shows the endianness. – Peter Taylor Mar 24 '14 at 23:27
Will the server keep track of the number of wins/losses or are we suppose to do it ourselves? In any case, are we supposed to play against all other contestants? is there a minimum number of games to play to qualify? – plannapus Mar 25 '14 at 9:13
I haven't experimented with the rules, only thought about whether standard patterns (like the glider) would work with these rules. The strategy you're talking about sounds like a valid strategy - for example, you could plaster the grid with blinkers, but that will 'only' get you linear growth. I'm hoping someone find a strategy that really uses the Game of Life rules to their advantage. – Wander Nauta Mar 26 '14 at 18:49
Gliders seem useless, due to the dead walls. And is superlinear growth really achieveable with 30 cells per turn and the opponent potentially interfering? If anything goes wrong with your set up you would have been better off just building stable shapes. But as I said, my GoL knowledge does not extend far beyond glider guns. Maybe a torus geometry would actually make it more interesting? Just some ideas... – Martin Büttner Mar 26 '14 at 19:38
@m.buettner Torus world would be interesting, but I think it would increase the chances of the game just turning into chaos, with a random winner. Take a look at this gif: upload.wikimedia.org/wikipedia/en/d/d1/Long_gun.gif The gun destroys itself. With a wall or infinite field, it doesn't. Infinite field isn't doable, so wall it is. – Wander Nauta Mar 26 '14 at 19:44
I see, thanks for the examples. I agree with the walls then. Thinking about enemy cells counting for starvation rules could be interesting though. It could also make the challenge way too complex. Unfortunately, I have no real idea how to figure out what's best. Regarding the client/server think, I still think that simply pairing up all contestants on one server to get an equal amount of matches for each pair would be fairest, but I can understand if you don't have the resources for that. (Maybe some other use would be willing to help out with that?) – Martin Büttner Mar 26 '14 at 20:14
"The bot with the largest KD spread, that is, the largest difference between the amount of wins and the amount of losses, wins." -- does that mean that if we lose every battle, we win the entire tournament? – Jan Dvorak Mar 27 '14 at 7:49
There's a typo in your TLV example; the first number should be 781, not 718. Also, when you say the borders are permanently dead, do you mean that everything outside the 1024×1024 area is permanently dead, or that the outermost 1px-wide border of pixels is permanently dead? – squeamish ossifrage Apr 4 '14 at 9:22
Thinking about it, an effective strategy against artificial waits would be a timeout per move, and if the bot doesn't respond in time, a default move of awaking no cells is assumed. – celtschk Apr 6 '14 at 17:22
@WanderNauta: Why? You have to run the bots yourself, or you cannot be sure that it is really the bot posted here that runs (an identification string is no proof). And then, it seems to be pointless to run it over the internet. – celtschk Apr 8 '14 at 8:13
I think this method is bad. You either need your bot to stay connected indefinitely (waiting for opponents), or you only face one opponent. In order to have every bot face every other bot, you really need them all there on server. – mbomb007 Feb 26 at 17:20

Let's Play Mafia!

Mafia (also known as Werewolf) is a party game that plays roughly like this:

  • The game begins on day 0. After every day n comes a night n. After every night n comes a day n+1. i.e. D0, N0, D1, N1, D2, N2...
  • At the dawn of day 0, a host secretly chooses players to fill certain roles:  
    • Some number of players become the mafia. Every night, every mafioso chooses a player. At the dawn of the next day, the player chosen by the most mafiosos is killed. They are permanently removed from the game and their role is publicly revealed. Mafia-aligned.  
    • Some number of players become cops. Every night, each cop chooses a player. At the dawn of the next day, the cop becomes aware of that players alignment. Village-aligned.  
    • Some number of players become doctors. Every night, each doctor chooses a player. If this player is the same player that the mafia chose to kill, the mafia's actions for that night are canceled. Village-aligned.  
    • All players who aren't chosen for another role are villagers. Villagers have no abilities that aren't shared by the whole town. Village-aligned.
  • Every day except day 0, the entire town (that is, all living players) votes for a player. At the end of the day, that player is removed from the game and their role is revealed. (On day 0, everyone just chills until nightfall.)
  • If, at any point, there are no remaining mafiosos, the game ends with all village-aligned players victorious (including the dead).
  • If, at any point, the village-aligned players do not outnumber the mafia-aligned players, the game ends with all mafia-aligned players victorious (including the dead).

For this challenge, your goal is to write a bot to beat other bots at Mafia!

I've written a control program for this challenge (available here, but I'd recommend against looking at it because it's pretty gross) for you to test your bots with, but the real judging will go down on my Raspberry Pi. (Sandbox note: Details about the Pi [e.g. what OS I'll use, etc.] will come before this gets posted 4 realz)

How to make a working bot

All you have to supply for me is a file called run. Inside the directory structure where this challenge will take place, your bot will live here:

players/               # You are here!
    some_bot/          # Let's pretend you're some_bot.
        run            # This is what you give me

The run file, when executed, will make your bot do its thing. It's important to note that this file must not require any command line arguments or anything. It will be run exactly as ./run. If you need to be executed in a different way, you'll have to work around it by doing something like this:



# code goes here



./real_bot.py --flags --or --whatever

An important thing to note is that all input your bot receives will be found in the file from_server and the control program will look for your bot's output in to_server. I chose to do it this way so that any language that can do file I/O is able to participate. If your language makes it easier to work with stdin and stdout than file I/O, you may want to write a run file that looks like this:


./real_bot.py < from_server > to_server

This will make it so that stdin comes from the from_server file and stdout goes directly to to_server.

Your bot will not stay running for the duration of the game. Instead, it will be run when it needs to make a decision. Likewise, it will not be informed when it's dead, it just won't be run anymore. Plan for this by saving anything you want to remember to a file and reading it later. You may create, write to or read from any file in your bot's folder, but you may not write or read anywhere outside of that folder, including network access or anything. If your bot knows anything that it wasn't told from inside the folder, or if it touches anything that isn't inside that folder, your bot is disqualified.

How to make a functional bot


At the beginning of the game, the file players will be filled with a newline-delimited list of all players in the game. It will not be updated as players leave the game.

At the dawn of day 0, all players will find this message in their from_server file:

Rise and shine! Today is day 0.
No voting will occur today.
Be warned: Tonight the mafia will strike.

If you are the cop, the line You are the cop is appended to the end. The doctor sees You are the doctor. The mafia sees You are a member of the mafia.\nYour allies are: and a newline-delimited list of mafia members, excluding the player reading the message.

At the dawn of all other days, this message will appear:

Dawn of day `day_number`.
Last night, `victim` was killed. They were `victim_role`.
Investigations showed that `cop_target` is `target_alignment`-aligned.
These players are still alive: `remaining_players`

dayNumber is replaced with the number of the day. victim is replaced with the name of last night's victim, and victim_role is one of:

  • a villager
  • a mafioso
  • the cop
  • the doctor

cop_target is the name of the player the cop investigated last night, and target_alignment is either village or mafia. Finally, remaining_players is a list of players that are still alive in this format: player1, player2, player3

The second line is omitted if there was no kill last night, and the third line is shown only to the cop.

Once this message is out of the way, the day begins! Each bot can make 50 actions throughout the day, where an "action" is voting for a player or saying something out loud.

To vote for a player, write vote player_name to your to_server file and terminate. To vote to not kill anyone, write vote no one. When you vote, all players (including you) will see your_bot votes to kill your_selection. Votes are ignored on day 0.

A number of pre-defined messages can be sent to all players. The id of each possible message is listed here:

 0: No
 1: Yes
 2: I am the cop
 3: I am the doctor
 4: I am a normal villager
 5: I trust this player: 
 6: I think this player is suspicious: 
 7: I think this player is the cop: 
 8: I think this player is the doctor: 
 9: I think this player is a normal villager: 
10: I think this player is mafia: 
11: Do you think this player is mafia? 
12: I tried to save this player: 
13: I successfully saved this player: 
14: I investigated this player and found that they were mafia-aligned: 
15: I investigated this player and found that they were village-aligned: 
16: Will you please use your power on this player tonight?

All of these messages except the first five are referring to a specific player. To say one of those messages, write say message_id player_name. For one of the first five messages, just write say message_id. You may add an optional third argument to both of these, specifying the name of a player you're talking to (all players can still read it, but they'll know who the intended recipient is).

When your bot says a message, all players read your_bot says "message", where message is the message associated with the id you wrote. If the message includes a subject, one space character and the subject are inserted directly after the end of the message. If it includes a recipient, their name, one colon and one space character are inserted immediately before the message.

At the end of the day, all living players are run one last time to see the result of the vote. If a player was voted out, this is written:

The town has killed player_name!
They were a villager

... or a mafioso, or the cop, or the doctor.

If no player was voted out, this is written instead:

The town opted to lynch no one today.

When the controller sends these messages, it ignores any response from players. The day is over.


At night, everyone but the villagers get to use their power.


You will read It is night. Vote for a victim.. When this happens, output the name of the player you'd like to kill.


You will read It is night. Who would you like to investigate?. When this happens, output the name of the player you'd like to check.


You will read It is night. Who would you like to save?. When this happens, output the name of the player you'd like to protect.

After this, the next day begins as normal.

General Information

  • The game will not run without 6 or more players.
  • One third of the players, rounded down, will be mafia. One player will be a doctor, and one player will be a cop. All other players are villagers.
  • Ties in the village vote or the mafia's overnight vote are settled randomly.
  • Bot names must be alphanumeric + dashes and underscores.
  • It is forbidden to use knowledge of opponent's code directly. In theory, I should be able to put your bot up against bots you've never seen before and have it perform comparably.
  • Regrettably, if I can't get your program running using exclusively free (as in beer) software, I'll have to disqualify it.
  • I reserve the right to disqualify any submission if I believe it to be malicious. This includes, but is not limited to using excessive abouts of time, memory or space to run. I've intentionally left the limit soft, but remember: I'm running this on a Raspberry Pi, not a supercomputer, and I don't want getting results to take a year. I don't expect to have to use this, since my standards are pretty low. This is basically "if I think you're being a dick on purpose", and if you can convince me otherwise I'll reverse my decision. (Sandbox note: Am I allowed to do this? It's less than "objective" for sure but really it's just going to be a fallback "don't be a dick" rule. If not, what should I say instead?)


Each round, 100 games will be run (this may increase as more bots join to keep the sample size large enough, but in theory that won't affect anything). I will record how many times each bot wins as a villager compared to how many times it plays as a villager, and the same for mafia. A bot's villager_ratio is number of games won as villager / number of games played as villager, and mafia_ratio is the same but s/villager/mafia/g. A bot's score is (villager_ratio - mean villager_ratio) + (mafia_ratio - mean mafia_ratio).

Example bot

Randy the Robot is not a good mafia player. Randy ignores pretty much everything, randomly choosing what to say, who to vote for, and who to target with night powers.



./randy.py < from_server > to_server



import random

with open('players') as f:
    p = f.read().split() + ['no one']

day = True
    line = raw_input()
    if line.endswith(('?', 'victim.')):
        day = False
    if not day:
        print random.choice(p)
        if random.random() > 0.5:
            if random.random() > 0.5:
                print 'vote {}'.format(random.choice(p))
                id = random.randint(0, 17)
                print 'say {}{}'.format(id, (' ' + random.choice(p)) if id > 4 else '')
except: pass

(Sandbox note: I can't shake the feeling that I've forgotten something. Hm. Probably going to be mad when I figure out what it was :P)

Just an idea: Wouldn't it be easier to make the bot to be communicated by stdin/stdout? I mean: recieve line-by-line the messages from others and from the system (things like: DAY begin, NIGHT begins, KILLED xyz, SENTENCED uvw, MESSAGE 5 abc SAID klm, ...)? It would be IMHO easier to control such program, because it would be run only once, so I (as a bot owner) could easily remember things and stuff. – yo' Jun 9 '14 at 14:33
Pardon me if I've misread, but how can the mafia / villagers discuss the target when a program is only run once per "day"? – user2428118 Jun 13 '14 at 23:13

Ruby on Rails

I'm looking to dig out this long-buried question proposal (the number of upvotes suggests a few people are interested). A question for reviewers based on the old question:

  • Keep the different direction tracks (- | / \) or use one character to represent track (. maybe)? Tracks that have a direction pose an extra challenge to the implementer - is that where some of the interest is? In which case I should keep the directions and come up with a stricter definition of which tracks are allowed to be adjacent to others. If it's just the path-finding that's of interest maybe the single track type removes an annoying and uninteresting wrinkle.

You are Ruby, a railway engineer. Your task is to lay track to visit every station in any given valley. The amount of track laid is not important so long as it doesn't cross its own path. There are a couple of other constraints: mountains(^) are impassable so you must go around them, and rivers(~) must be crossed using a bridge(X). You can enter a station(M) from any direction but must exit in a different direction (ie no backtracking).

You have a selection of track to choose from: - | / \ , and in order for the track to be considered complete each piece of track must be adjacent to a previous piece of track or the entrance/exit(>) (Diagonal will be considered adjacent for this question).

Input will be via STDIN and you can assume that all cases will be rectangular and will be solid at all points on the perimeter except for the entrance/exit.

Winner is the shortest code.


# - Valley edge (impassable)
^ - Mountain (impassable)
M - Station
~ - River
> - Entrance and exit point of the valley

X - Bridge
- - Track(East-West)
| - Track(North-South)
/ - Track(SW-NE)
\ - Track(NE-SW)

Test cases

#    M   #
#   ^    #
>  ^^  M #
#    ^   #
# M      #
#       M#

#               #
#  M          M #
#       ^       #
#        ^ M    #
#~~~~~~~^       #
#               #
#   ^           #
#   M^          #
#    ^          #
> ^^^          M#
#        M      #

Possible solutions to test cases

# ---M   #
#/  ^ \  #
>  ^^  M #
#\   ^ | #
# M     \#
# |-----M#

#               #
#  M----------M #
#  |    ^    /  #
#  |     ^ M-   #
#~~X~~~~^  |    #
#  |        \   #
#  \^        \  #
# --M^        \ #
#/   ^         |#
> ^^^          M#
Did you ever publish this? It would be a shame to let something with this good a name die. – Mr Lister Mar 15 '14 at 11:58
@Gareth 8 upvotes and close to 4 years now ;) – Martin Büttner Mar 4 at 3:58
@MartinBüttner Hmm, 10 votes now. Seems to be building a head of steam. I'll need to have a look at this when I have time. – Gareth Mar 17 at 14:02

Waving Hands bot

This is a sketch for a contest for a game which is much more complicated than the previous questions in this genre. Implementing the test framework will be a lot of work and it will require a lot of debugging, so I want to get feedback on whether the game is too complicated before I start work on that.

Waving Hands (original known as Spellbinder) is a two-player simultaneous-turn-based strategy game. At one level it is quite simple. You have two hands. Each turn you perform an action with each hand. Sequences of actions performed with the same hand create spells, which have varied effects.

The first level of complication comes from the number of spells: 42. I don't intend to reproduce a list: there is an online rules page (which is backed up by archive.org should that fallback be necessary).

The second level of complication comes from the interactions between the spells. This is where debugging of the test framework is most likely to be needed. My plan is to allow complaints about the framework's implementation of the rules for a period of two or three weeks or until there are three posted answers, whichever is the later.

At each turn the bot will be provided with a full history (except for moves which the rules say it can't see, which will be so indicated). However, it will not be provided with any other identifying information about its opponent. I think that it will be hard to fingerprint some bots, although probably not all.

The framework will probably be written in Java and hosted on github. I intend to provide one or two wrapper classes for non-JVM languages, and a "bot" which brings up a UI for human play, which will be useful for debugging and testing your own bot.

Under the label of fair play, it will be forbidden to attempt to interfere with the opponents or access their memory. A bot may store information about the current game, to save recomputing it each move, but it may not persist information between games. Competitors may submit more than one bot, but they must be independent: i.e. no submitting bots whose purpose is to help your favoured bot win.

To reassure anyone who's worried about copyright: the creator of the game has stated

I retain full rights to the game, and if any commercial incarnation appears then I want a royalty! I have no objection to people implementing or running derivatives of the Spellbinder so long as they make no money from it, though.

Normally upvotes in the sandbox indicate that you think the question is ready to post. This one clearly isn't. However, please upvote it if you think that the outlined proposal would make a good question. If there's enough support, I will create a separate sandbox answer when the test framework is ready for early criticism.

@Geobits, I believe in updating the accepted answer when a better answer comes along. – Peter Taylor Apr 9 '14 at 14:14
Thank you for introducing me to this game - I'm creating a revamped version and my friends and I at school are all having a great time testing/playing it ;) – Doorknob May 1 '14 at 20:49
@PeterTaylor I still think this one is suitable, because it is possible to start with rather naive strategies (since output is merely two characters each turn) and then gradually build on that to use more interesting strategies. If you're just not willing to expend the effort to implement the controller, I'd be interested in doing that some day, but first I've still got two other KotH proposals lying around (which don't even have as low an entry barrier as this one). – Martin Büttner Sep 4 '14 at 12:06
@TheBestOne, as I say in an earlier comment, I now think this is too complex to be a good KotH, but if I were taking it forward then my answer would be, "By no means!" KotH should be round robins rather than elimination brackets to minimise the non-determinism. – Peter Taylor Jan 13 at 8:05

Basic Markdown Parser

Write a script or function that parses Markdown. These rules must be parsed:

  • `foo`<code>foo</code>
  • *foo*<em>foo</em>
  • **foo**<strong>foo</strong>
  • ***foo***<strong><em>foo</em></strong>
  • _foo_<em>foo</em>
  • __foo__<strong>foo</strong>
  • ___foo___<strong><em>foo</em></strong>
  • [foo](http://bar)<a href="http://bar">foo</a>
  • [foo](bar)[foo](bar)
  • ![foo](http://bar)<img src="http://bar" alt="foo"/>
  • ![foo](bar)![foo](bar)
  • # foo<h1>foo</h1>
  • ## foo<h2>foo</h2> (and h3,h4,h5,h6)

- unordered list:

- foo
- bar
- baz

                                             ⇓                        ⇓                        ⇓


- ordered list:

1. foo
47. bar
22. baz

                                             ⇓                        ⇓                        ⇓


- code block:


                                             ⇓                        ⇓                        ⇓


- blockquote:

> foo
> bar
> baz

                                             ⇓                        ⇓                        ⇓

<blockquote>foo bar baz</blockquote>


  • <b> is not the same as <strong>
  • <i> is not the same as <em>
  • you don't need to parse
    • [1](http://) and [something][1]
  • parse left to right and close before opening, e.g.
    • *Strange **String*here** -> <em>Strange </em> <em>String</em>*
    • note that the mismatched * got passed through without rewriting* This ** is * wrong ** should compile as

You can assume you'll never receive:

  • nested lists
  • code/blockquotes in lists (they end the list)
  • two spaces at the end of a line
  • horizontal rules (<hr>)
  • HTML can be passed through directly (trust the user)


It's code golf; least bytes wins.

-5 for a detailed explaination


I would like to provide some way to test it. I'm thinking I can make a fiddle that takes the generated HTML as a text-box input for a test document, and compares the DOM. I'll try to write up a test document.

This question is quite massive. Feel free to make edits to optimize it. It can always be rolled back, so be brave.

Are __underscore__ variants of the **asterisk** versions needed?


Conquer the Solar System

Here is an outline for a strategical King-of-the-Hill challenge which is loosely based on Risk (loosely enough so as not to preclude a future Classic Risk KotH).

It is far from complete, but I'm posting it here to gather feedback from the community to finalise the rules before getting down to implementing the control program. This would definitely make for one of the more complicated KotHs and I'd like it to be as fun as possible, so that it's worth the participants' time! I will probably leave this up for several weeks before starting work on the controller.

I wanted to try something new: The distinguishing feature of this challenge is that it does not use simultaneous turn-based simulation, but rather something similar to Final Fantasy X's Conditional Turn-Based Battle system. Different actions take different amounts of time, and it's simply your turn again when that time has elapsed. Of course, the control program will simply skip ahead to the next scheduled event.

There are probably more technical details in this post than what will be necessary for participants of the final challenge (and will most likely be presented in a different form then). I just wanted to include everything I've currently got, so people might point me towards issues in the underlying assumptions.

The Setting

The year is 2200: Mankind has spread out over the entire solar system. But we all know how much humans like other humans with different resources – interplanetary war has broken out. Each inhabited planet or natural satellite – collectively referred to as (celestial) bodies – starts out as one faction in this war. The goal is conquer as much of the solar system as possible.

The Model

The arena of the challenge is hence the solar system. I will include all solid planets and natural satellites with a diameter of 10 km or more (just for a bit of realism; this should provide a large enough surface area to build a base). There are 89 of those bodies – I could add even smaller objects should I get more submissions than that, but I think that's near impossible.

Note: I said "solid" bodies. Jupiter, Saturn, Uranus and Neptune are gas giants and hence cannot be landed on (their satellites can be, though).

Planetary motion will be simulated, although in a simplified manner. Orbits are assumed to be circular and lie all in one plane, with a radius of approximately their real-life semi-major axis, and their real-life orbital period. Hence, no gravity is simulated – only simple (uniform) circular motion.

Satellite motion will not be simulated. Travel distances between satellites or between a planet and its satellites are assumed to be fixed (and will be determined once, by me, dependent on the satellites' orbit sizes).

The asteroid belt between Mars and Jupiter can be travelled to, but no bases can be built there – it acts mainly as a hideout. It is modelled as a continuous ring at fixed distance from the sun with fixed orbital period. Bots can choose to land their units at any position on the belt. Individual asteroids are not modelled – not even the larger ones like Ceres, which are way above the size limit.

Technically, the map is a complete graph whose vertices are the above 89 bodies plus the asteroid belt. The travel times between any pair of bodies depends on their distance at the time the travel commences (neglecting motion of the target during the travel). As planetary motion is simulated these travel times do generally change over time though. The future spacecraft is assumed to travel between 500,000 and 1,000,000 m/s and travels in straight lines, giving time scales between 10 seconds and 80 days.

For each match, the solar system will start out in a random configuration (each planet getting a random position on its orbit). Of course, that's not realistic, because the planetary configuration for 2200 is not going to be subject to change, but we need to keep the game fair.


  • Each player starts with a base on a random body. The remaining bodies will be uninhabited.
  • Each player starts with one flagship, and n fighters (where n needs to be determined, but I'm thinking on the order of 10) – collectively referred to as units.
  • Players write a bot that is asked for a move whenever one of their own units is idle or needs to act, because it's being attacked or similar.
  • Fighters are a lot faster than flagships, so they will act as scouts as well, to avoid time-wasting travel with the flagship.
  • Flagships can build new bases on uninhabited bodies, or take over enemy bases (the former taking longer than the latter).
  • Each additional base immediately grants another n fighters.
  • Each base regularly spawns new fighters (say, once a week). If a player controls an entire planet system (the planet and all satellites), the spawn rate on all bodies in that system is increased (to, say, once every five days).
  • Flagships are vulnerable while working on bases. Either they can't interrupt the building process upon arrival of enemies, or such an interruption will cause the total build time to increase.
  • Upon landing on a body, units can't leave immediately. They need to remain for p % of the time it took to get there (p ≈ 10?) in order to refuel. Technically, this is to prevent units from hiding all the time in interplanetary space. (formula subject to change)
  • If there are units from multiple players on a body, they may engage in combat (see next section for details on combat).
  • If a player's flagship is defeated they immediately lose the game! All their units and bases go over to the player who killed the flagship.
  • The bot may always decide to wait idly (I'll set a minimum on this, to prevent bots from spamming the control program with millisecond waits). Waiting will be interrupted by any relevant event like allies or enemies arriving somewhere.

Combat System

  • Fights are carried similar to the rules of Risk. Please refer to the Wikipedia page or the internet for the exact rules for now – all necessary rules will be part of the final challenge post though.
  • Attackers may choose to attack with 1 to 3 units, defenders choose to defend with 1 or 2 units. The outcome is determined by rolling dice. After each round of battle, battle may either continue with the remaining units or be aborted.
  • One round of combat takes 1 day. (subject to change)
  • Whether a player is attacker or defender depends on whether he has a base on the current body. This means that two attackers could be fighting each other on an unclaimed body, in which case both may use 3 units in a fight, but units from both sides die in a tie.
  • If a player has a flagship on the body where the fight takes place, one unit will roll a d8 instead of a d6, unless they are currently working on a base (building one or converting one).
  • When players lose units, they always lose fighters first. Hence, if a player has a flagship on a planet, and loses less than all of his units, the flagship will remain.


I will either go with Rusher's approach of writing a Java controller where participants only need to implement an interface (and provide a wrapper for non-Java submissions) or I'll write a controller that invokes bots as separate processes whenever its their turn.

On their turn, each bot will be provided with

  • the current time
  • the number of bases and units controlled by each player
  • the state of all bodies the player currently has units or bases on
  • the ID and location of the idle unit(s) that can currently perform an action
  • a list of all bodies with their current positions (in Cartesian coordinates, so distances can easily be determined)
    • potentially I'll just provide a list of travel times for each idle unit instead, to save the bots the need to compute those
  • a list of all bodies with their current angular positions

The latter can safely be ignored, but is provided for bots that want to predict planetary motion to take shortcuts. Static numerical data like orbital radii and periods will not be provided to the bots, but I'll publish a table with the challenge to be hardcoded into the bots if desired.

Further Design Decisions

I realise that there is a lot of complexity in this. This is why I need your help to refine the concept and remove unnecessary details while keeping the heart of the challenge in tact (while making sure the rules are consistent). Please give me all the feedback you can think of, but here are a few particular questions I have in mind that need to be answered:

  • How should vulnerability during base-building be modelled? By penalising or by disallowing interruptions?
  • How can fights between more than two parties be handled?
  • Is the "refuelling" necessary/useful? Do the details for it need work?

In any case, I don't doubt this challenge will remain fairly complex when finalised. It might help to gather some momentum if a few heroes volunteered up front to submit a bot to this - ideally ones which show that the entry barrier doesn't need to be as high as it looks.

Anyway, thanks a lot for reading this and helping out with the design of this challenge!

I'm happy to discuss details in chat (The Nineteenth Byte or Golf/Puzzle Lab; but ping me so I know you've posted there) or just here, but this challenge may need more discussion than fits in comments.


Find the Needle in the Haystack

The Cops' Challenge

You are to write a short program, which prints the string "Haystack". However, it must be possible to remove some subset of characters from your program, such that the resulting string is also a valid program, which prints "Needle" instead. Both programs may or may not print a trailing line feed (independently of each other).

Your goal is that the Needle should be very hard to find.

Neither program must take any input. You may print to STDOUT, a GUI dialog (as with JavaScript's alert()), or assume a REPL environment (like a browser console) - but you need to clearly state where your output will go.

Both programs have to complete within 5 seconds on a reasonable machine. You are not allowed to use cryptographic methods, hashing functions, random seeds or string compression.

You should deliver:

  • The language of your programs.
  • The size of the Haystack program in bytes.
  • The Haystack program itself.
  • The target of the Needle program's output (STDOUT, dialog, REPL).

An answer is cracked if the Needle program is found (see The Robbers' Challenge below). If your answer has not been cracked for 7 days, you may claim immunity by revealing the Needle program in your answer (to prove that your answer was solvable).

The winner will be shortest immune Haystack program (measured in bytes).

The Robbers' Challenge

Every user has one attempt at cracking each submission. Your cracking attempt will be a Needle program, obtained by removing some subset of characters from the Haystack program, such that Needle program prints Needle to the specified target. If your guess matches the description (can be constructed from the Haystack program, correct target and of course language), and you are the first correct guess, then you win a point. It is important to note that your program does not have to exactly match the original, as long as it meets the specification and can be found in the Haystack. This means there could be more than one correct answer.

The robber with the most points (correct Needles) wins. Ties are broken by the total size of the corresponding Haystacks.

Robbers should post their cracks as answers to the associated Robbers' thread.


Here are a couple of simple examples in different languages:


Haystack: puts 1>0?"Haystack":"Needle"
Needle:   puts "Needle"

Python 2

Haystack: print "kcatsyaHeldeeN"[-7::-1]
Delete:          XXXXXXXX        XX
Needle:   print "eldeeN"[::-1]

Sandbox Notes

  • I will wait at least a couple of weeks, if not more, before posting this, since the unscrambling question is still too fresh.
  • I intend to provide stack snippets which generate leaderboards for the cops and robbers. Writing those will take some time anyway.
  • I'm considering to allow different languages for Haystack and Needle (the Needle program would still have to be specified). Opinions on this? Arguments for or against it?

King of the Hill- Simple RPG


Your challenge is to make a bot that plays a simple RPG game against other bots.

The Rules of the Game

The Board

The board is a 500x500 2-dimensional array of cells. In any cell, there is one of the following:

  • Nothing.
  • An obstacle. Cannot be occupied by anything.
  • A player.
  • A monster.


Each turn, a player can:

  1. Move: you can move north, east, west, or south, or not move at all. Attempting to move into an obstacle, or off the edge of the board, will result in you not moving at all.
  2. Perform a special attack: you can either perform a ranged attack, an area attack, or no special attack at all.
  3. Battle: if you encounter an enemy, you can fight them.


Whenever you enter a square that is already occupied by a monster or another player, you fight them. You and your opponent take turns attacking each other, with the first move being decided randomly. At any point in the combat, you may flee. Also, once per battle, you may use a special attack which does double damage.

Damage is calculated using this formula:

Damage = Attacker's attack modifier + Random number from 1 to 5 - Defender's defence modifier

Special Attacks

There are two special attacks: A ranged attack, that targets any enemy within 5 squares, and an area attack, that targets all enemies within 2 squares. Damage is calculated using the same formula as for melee damage.


In the game, there are 5 monsters:

  1. Goblin. Attack: 1; Defence: 1; HP: 1; moves randomly; 1XP for killing.
  2. Orc: Attack: 3; Defence: 2; HP: 5; follows players; 5XP for killing.
  3. Troll: Attack: 5; Defence: 2; HP: 10; moves randomly; 10XP for killing.
  4. Giant: Attack: 10; Defence: 5; HP: 15; follows players; 50XP for killing.
  5. Dragon: Attack: 20; Defence: 10; HP: 20; follows players; 100XP for killing.

If you kill another player, you receive 100XP.


When you create your bot, you must give it 5 attributes. They are:

  • Attack: your attack bonus when using a melee attack.
  • Ranged Attack: your attack bonus when using a ranged attack.
  • Area Attack: your attack bonus when using an area attack.
  • Defence: your defence bonus.
  • Constitution: added to your HP (10 by default). Note: If your bot's constitution is -10, it dies immediately.

These attributes must sum up to 12. They may be anywhere between -10 and 22.


public class MyBot extends RpgBot
    public static final int ATTACK = <insert here>;
    public static final int RANGED_ATTACK = <insert here>;
    public static final int AREA_ATTACK = <insert here>;
    public static final int DEFENCE = <insert here>;
    public static final int CONSTITUTION = <insert here>;
    // you can add something here
    public MyBot() { super(); }
    public Move move() {
        // insert here: return either Move.NORTH, Move.EAST,
        // Move.WEST, Move.SOUTH, or Move.NO_MOVE.
    public SpecialAttack makeSpecialAttack() {
        // insert here: return either SpecialAttack.RANGED,
        // SpecialAttack.AREA, or SpecialAttack.NONE.
        // For ranged attacks, use setTargetX() and setTargetY()
        // to set the target beforehand.
    public Attack attack(Entity m) {
        // insert here: return either Attack.NORMAL,
        // Attack.SPECIAL, or Attack.FLEE.
        // Entity m is one of the monster entities.

Here are the additional functions you get for your convenience:

Entity surroundings(int x, int y)- returns an entity representing what is located at that point. x and y range from -5 to +5, with 0, 0 being the square where you are. Trying to access outside that range will result in an Exception being thrown. Entity is one of:

  • Entity.NONE- nothing.
  • Entity.OBSTACLE- an obstacle or the edge of the map.
  • Entity.PLAYER- either you or another player.
  • Entity.GOBLIN- a goblin.
  • Entity.ORC- an orc.
  • Entity.TROLL- a troll.
  • Entity.GIANT- a giant.
  • Entity.DRAGON- a dragon.

At the beginning of the game, the field is randomly populated with 300 obstacles, 1000 goblins, 500 orcs, 100 trolls, 50 giants, and 10 dragons.

void setTargetX(int x) and void setTargetY(int y)- set the target x and y indexes of the ranged weapon. Indexes range from -5 to 5, with 0, 0 being your location. Passing these functions an index outside the range will result in an Exception being thrown.

Winning Condition

The winner is the bot that acquires the most XP before it dies.

@Manu Yes, but I haven't been able to work on it for a rather long while. – Alex Mar 6 at 22:33

Count the pips in a pair of dice

Here are four photographs of a pair of randomly thrown dice (N.B.: click thumbnails for full-size images). From left to right, the numbers of pips shown by the two dice are 3, 9, 9 and 5. Can you program your computer to count the pips automatically?

⚁⚀ ⚄⚃ ⚃⚄ ⚁⚂

The challenge:

Write a program that takes as its input the filename of a 360×240 JPEG image similar to the above examples, and outputs a number corresponding to the total number of pips shown on the top faces of the dice. Your program must accomplish this in less than one minute on an averagely specced desktop computer.


To test your program, download «this gzipped archive» (link to be added later) containing 100 sample images (dice001.jpg ... dice100.jpg) and a CSV file (pip-counts.csv) showing the correct pip count for each image. Using this data, calculate the percentage of correct results produced by your program (from 0 to 100) and subtract the length of your program (in bytes) divided by 100 to obtain your final score. The highest score wins.


  • All the photographs will be taken with the same camera angle and lighting conditions. The only variables will be the position and orientation of the two dice.
  • Do not hard-code your outputs for the sample images. Your program must work with any image of this type, and will be tested with additional images if any shenanigans are suspected.
  • You are welcome to use image processing and computer vision libraries.

For discussion:

  • I thought it would be more interesting to have two dice, but this does increase the complexity of the problem somewhat. Would it be better to have just one instead?
  • The "photographs" are actually produced by a Python script running in Blender, so there's no particular limit to the number of sample images I can make. Is 100 about right?
  • Where would be a good place to store the gzip file?
  • I'm wondering if this would work better as a instead of , but what would be the best way to score answers in this case? Your thoughts on the scoring system would be welcome.
a) Either one or two dice seems fine to me. b) You should be able to upload the zip file into a Gist on GitHub. c) As far as I can, this is a code challenge and not a code golf. The golf score seems negligible in comparison to the accuracy score, and will probably serve mostly as a tie breaker. (And I think that's good.) – Martin Büttner Jan 9 at 11:20
Can we assume these are all standard dice, so any two opposite faces add up to 7? This would allow double checks such as 3 and 4 can never be on adjacent faces, and 6 and 1 can never be on adjacent faces. – trichoplax Jan 12 at 23:35

Global Warming

This KOTH takes place on a melting iceberg. You must stay on it as long as possible, and preferrably, be the last man standing.

The field is a perfectly circular iceberg which shrinks at a unknown rate, in the center of a 2D plane. Gameplay is executed in turns on which your program will be called with the current status of the iceberg and other participants. Each turn you may either change your movement direction or push someone near you (or neither).

Movement and positioning

Positioning is in a 2D plane of floating point coordinates, and movement is a speed of x and y components. When issuing a move command, your entry will keep moving in that direction until you explicitly tell it to stop or change direction with another move command (or a push, more on this soon). The maximum move speed is 1.0 in magnitude, and if you ask to move further than that, your speed will be adjusted to conform this limit.


Your program can issue push commands to any entity within a radius of 1 from you, resulting in you and your target having your speeds changed to point away from eachother and at a given speed. The push speed is directly adjustable, but the direction isn't. Push speed is under the same limitations as a move command, and thus can't be stronger than 1. If two people push the same target at once, the target is pushed in the resultant direction. Pushing will take into account the target's move command, if there was one.


Each round, your program will be invoked from the command line, with a CSV document being passed to its STDIN. The first line of this document provides the current iceberg radius (floating point number) and the amount of remaining competitors (integer)

After this "header", there will be one line for each remaining competitor in the following format (which is on its turn on the format type(variable)):

string(entity id),float(x),float(y),float(velocity x),float(velocity y)

Your entry will always be the first item on the list.

Example input:


(the \ is a trailing newline, represented like that for clarity)


Your program will process the given input and output a ASV (Anything Separated Values) document. A ASV is like a CSV, except everything that doesn't match the regex [.0-9a-z] is considered a separator (even uppercase letters). If your program emits more than 1 line, only the last one is considered.

For movement:

move,float(velocity x),float(velocity y)

For pushing:

push,string(entity id),float(strength)

To do nothing, simply don't output anyting

Where move and push are string literals.





The following lines are valid outputs for your program:


Detailed Rules and remarks

A list of important points to consider:

  • You can skip your turn by returning no output, but this will make you keep moving in the direction you ere headed to.
  • If a competitor loses, it will not show up on the participants list (see below)
  • A player is considered to fall from the iceberg if their distance from the center is greater than the iceberg's radius.
  • Entries do not have a physical radius, so they cannot bump on eachother (except for the push command)
  • You can't know the shrinking rate of the iceberg.


A entry's score is the average turns_survived*players/total_turns out of 10 runs. Each run may have a indefinite (but not infinite) amount of turns, until only one competitor survives.

The scores will be periodically maintained here, and 100% up-to-date at INSERT URL

The winner will be chosen at INSERT DATE

Examples in pseudocode

Antisocial - pushes everyone away from him, doesn't care about where he is.

#!/bin/env pseudocode
data = read_csv(stdin)
foreach line in data.range(1,data[0,1]):
    if distance(me, line[1], line[2]) <= 1:
        write_csv_line(stdout, ["push", line[0], 1.0])
Well you could also minimise its utility by making it more physically correct such that the push is applied to you as well (in the opposite direction)... conservation of momentum and such. Then you could let players choose the push strength, and they'd have to decide how strongly they want to be pushed themselves. – Martin Büttner Jul 26 '14 at 13:32
One issue that isn't addressed is what happens to me after I was pushed. If I try to move and one or more people push me, where do I move? What if player A pushes B pushes C pushes A? Also, since you give a speed (but not distance) moved, you should list how much time is simulated between turns (1 second?) – Zaq Jul 29 '14 at 1:07
@justhalf I didn't want to do that because I had no idea how to, but i just realized it's dead simple to do. Sum the forces and cap to the max speed – Kroltan Jul 29 '14 at 13:14
This game (trying to push other players off of a (possibly shrinking) circular iceberg) is one of the modes in the delightful PS1 title Crash Bash. – feersum Aug 18 '14 at 19:50

Underwater Survival Game

Lions and bears are extinct, the wolves dominate the fauna on land. But in the depths of the sea the battle for survival rages on.

This is the spiritual sequel to Rainbolt's Survival Game, with a few additions. The arena is the sea and hence three-dimensional. Furthermore, you can choose one of three different species this time: write your bot as a whale, a shark or a giant squid!

The Arena

The game is carried out on a three-dimensional grid: +x points East, +y points North, +z points up. There will be 20*√n cells along x and y, where n is the number of participants. The height will always be 21 cells. There are five regions: three are the species' breeding grounds, and two are just non-special regions in between. The 21 layers are distributed as follows:

enter image description here

The board wraps around along the x and y directions but not along z.

Each cell will be populated by at most one animal or hazard.

The Game

Each bot starts with 100 instances randomly distributed in its own breeding layer.

Every turn, each bot can do one of two things:

  • Move: The move can be one cell in any orthogonal or diagonal direction (as well as staying in the same cell, which technically shouldn't be called a "move"). Moves off the board (above the top or below the bottom layer) are ignored.

  • Breed: Each animal starts with a breeding counter at 100 which is decremented every time step if it's greater than 0. If the counter is zero and the animal is in its species' breeding ground, there is a 10% chance that a new animal will spawn on a random (orthogonally or diagonally) adjacent cell - this new animal will simply be a new instance of your bot. If this happens, the breeding counter is reset to 10.

If two animals or hazards move to the same cell they fight until only one of them remains. If more than two animals (or hazards) move the same cell, two of them are picked randomly for a fight until there is only one survivor left. For details on fighting see below.

Your animal will be provided with the arena size, a 3x3x3 map showing its immediate surroundings, its breeding counter and its global z coordinate.

The winner will be bot with the most specimen (instances) surviving after 1000 rounds.

The Species

Your choice of animal determines where in which layer of the arena your animals can breed (see The Arena) and will give you one distinct skill:

  • Whales (W) start with 10% more specimen.
  • Sharks (S) can make an additional Move before their regular action. They will receive their updated surroundings after the first move. The first move must be made into an empty cell or it will be ignored.
  • Squid (Q) can see further and are provided with a 5x5x5 map of their surroundings.

The Hazards

Each layer has a distinct type of hazards which will "play" along the bots.

Fishing nets (N) sweep through the whales' breeding grounds. They will stretch across the entire depth of the layer and have the following pattern in the x-y plane:

N     N

They constantly move in the +y direction. About half of the nets will point and move in the opposite direction.

Jellyfish (J) are found in the sharks' breeding grounds. If there's a jellyfish adjacent to another animal, that animal cannot move (unless that animal is also a Jellyfish). Jellyfish move in alternating pattern such that it always stays in the central 3 layers of the sharks' breeding grounds: twice down, twice up. If no animal is around, they will move straight down and in a random (possibly diagonal) direction up. If there is an animal in one of the 9 cells in the current direction, the jellyfish will move to that cell (or if multiple cells are occupied will pick a random one of these).

Mantis shrimp (M) are only found on the ground (lowest z coordinate of the squid layer). Each turn there is a 10% chance that the shrimp will cause a cavitation bubble, which will blind all animals within a radius of 4 (Chessboard distance) for the next turn. They walk randomly but all in unison (don't ask me how they do it).

Naval mines (O) are found in the regular layers between the breeding grounds. They never move. When stepped upon, the mine explodes, killing everything within a radius of 1 (Chessboard distance) including the animal that triggered the mine.

There will be 30*n hazards in each layer, where n is the number of participants. The exception are the nets. There will be 2*n nets in the whale layer.

The Fights

Each fight is basically a non-uniform coin flip for who survives with the following probabilities:

  • If a bot picked Breed it always dies.
  • Nets are indestructible and hence always survive.
  • Jellyfish and Mantis shrimp will survive with a probability of 1/3.
  • If two bots fight, the odds are 50:50; except if one of the participants is in their own breeding grounds, in which case their chance of survival drops to 1/3 (because animals are unalert in their breeding grounds and that totally makes sense).

Sandbox notes

The controller has yet to be written, but I intend to do a Rainbolt-style KotH where you can either implement an abstract Java class or write a command-line script.

All numbers in the spec are subject to change until the challenge is actually posted.

I'm pretty sure the spec is currently incomplete (of course I/O is missing, but that has to wait until the controller is written), but currently I can't see the wood for the trees, so please point out the holes.

As usual, is anything unclear or could be improved? In particular, it will be hard to get the balancing right for this one, I think. I'm happy to discuss any questions or comments either here or in The Nineteenth Byte.

Next task after getting a controller program written is to write a 3d visual representation to watch back interesting matches... – trichoplax Jul 28 '14 at 22:50
"Shrimp always attack with scissors" How appropriate... – trichoplax Jul 29 '14 at 13:06

Ant Queen of the Hill Contest

To be clear up front: I have other KotH ideas for which I'd like to use other languages or be language agnostic, but for this one, I'm very attached to the idea of it being a Stack Snippet question (or at the very least a jsfiddle if I can't fit the spec and the controller into the 30,000 character question limit).

[ picture to give an intuitive feel of ants on a multicoloured grid ]


Each player starts with one ant - a queen. She collects food, and each piece of food is either stored or used to produce a worker. Workers also collect food to be brought back to the queen.

All players compete in one arena. The winner is the queen storing the most food after she has taken 10,000 turns.

This is a Stack Snippet competition, which means you can watch the game play out in your browser by clicking the "Run code Snippet" button below.

[ Stack Snippet to be added here ]

[ Credit to each of Calvin's Hobbies previous Stack Snippets KotHs on which the code is based ]

[ Link to chat room for this question ]

Ant abilities


Each ant sees the 9 cells in its 3 by 3 neighbourhood. It has no knowledge of any other ants outside this neighbourhood. It sees the contents of each of the 9 cells (other ants and food), and also each cell's colour.

No memory

Each ant makes its decisions based on what it sees - it does not remember what it did in the previous turn and has no way of storing state other than in the colours of the arena cells.

No orientation

An ant does not know where it is or which way it faces - it has no concept of North. The 3 by 3 neighbourhood will be presented to it at a random orientation that changes each turn so it cannot even walk in a straight line unless it has colours to guide it. (Making the same move every turn will result in a random walk rather than a straight line.)

Moving, colour marking and producing workers

See Output below.

Transferral of food

If a laden worker is adjacent to a queen (in any of the 8 directions), the food the worker is carrying is automatically transferred to the queen (this does not take up a turn).

Note that the transferral of food happens for any laden worker adjacent to any queen. If a worker returns to the wrong queen it will lose its collected food to the enemy queen. Similarly a queen that finds a laden enemy worker will automatically take its food.

The arena

The arena is a toroidal (edge wrapping) grid of square cells. It has width 2500 and height 1000. All cells start as colour 1.

Initially 0.1% of cells will contain food. The 2500 pieces of food will be scattered uniformly randomly.

The queens will be placed randomly in empty 3 by 3 neighbourhoods, The queens will start at least 100 cells apart (Euclidean distance to avoid increasing the probability of aligning vertically or horizontally).


Provide a function

Each ant is controlled by an ant function. The player's ant function is called separately for each ant. Each turn, the ant function will receive its input as function arguments and return a move for that particular ant.

No state, no time, no random

A function must not access global variables and must not store state. It may use functions that do not involve storing state. For example, the use of Math.abs() is fine, but Date.getTime() must not be used.

A function may only use a pseudo random number generator that it supplies itself, that does not store state. For example, it may use the colours/food/ants visible as the seed each turn. Math.random() is explicitly forbidden.

A simple random strategy is still possible due to the random orientation of the input - an ant that always returns 0 will perform a random walk rather than a straight line path. See the example answers for ways of using this randomness without needing to implement a random number generator.

Input and output


The orientation of the input will be chosen at random for each ant and for each turn. However, all input in a given turn will be at a consistent orientation for a particular ant.

Cells are numbered in English reading order:

0 1 2
3 4 5
6 7 8

The ant function will receive the following as arguments:

ownType: an integer indicating the ant's own type: 1 to 4 for a worker, 5 for a queen.
foodStore: an integer: the number of pieces of food being carried.
cells: an array of the visible cell colours. Each cell colour is a number from 1 to 16.
foodCells: a potentially empty array of cell numbers which contain food.
friends: a potentially empty array of objects representing visible friends.
enemies: a potentially empty array of objects representing visible enemies.

For each object in the friends and enemies arrays, the properties available are as follows.

.type: 1 to 4 for a worker, 5 for a queen. All enemy workers will show as type 1.
.location: a cell number from 0 to 8.
.hasFood: true or false.


Output is a single integer representing the action to take. Compose the integer from the following parts:

0 to 8: one of the 9 visible cells.
1 to 16: one of the 16 possible colours (to be multiplied by 10).
1 to 4: one of the 4 worker types (to be multiplied by 1000).

The numbers have been chosen to be human readable during debugging.


0: move to the top left cell (cell 0)
4: move to the centre cell (stay still)
30: set cell 0 to colour 3
34: set cell 4 to colour 3 (set the colour of the cell the ant is standing on)
126: set cell 6 to colour 12
1002: produce a worker of type 1 in cell 2
4007: produce a worker of type 4 in cell 7
4027: invalid: specifies both a worker and a colour

An ant moving onto a cell containing food will automatically pick up the piece of food.

A move will fail for any of the following reasons:

  • The cell to move to contains an ant.
  • The cell to move to contains food and the ant is already a laden worker.
  • The cell to produce a worker on is not empty.
  • A worker is trying to produce a worker.

Turn order

Ants take turns in a set order. At the start of a game the queens are assigned a random order which does not change for the rest of the game. When a queen creates a worker, that worker is inserted into the turn order at the position before its queen. This means that all other ants belonging to all players will move exactly once before the new worker takes its first turn.

Limit on number of players

Obviously an unlimited number of players cannot fit into the arena. If there are more than 16 answers, only 16 of them will play in any one game.

Time limit per turn

Each time the ant function is called, it should return within 5 milliseconds. Since the time limit may be exceeded due to fluctuations outside the ant function's control, an average will be calculated. If at any point the average is above 5 milliseconds and the total time taken by that particular ant function across all calls so far is more than 10 seconds, the relevant player will be disqualified. This means they will not be eligible to win and their ant function will not be called again during that game. If a player is disqualified on my machine during a leaderboard game then it will be excluded from all future games until edited.

Multiple answers

You may provide up to 3 answers, provided that they do not team up against the others. For example, one queen that simply supplies additional workers to another would not be acceptable.

End of question wording

Example strategies

To be added as example answers - not part of the question wording. When the question is first posted these simple answers will provide a population against which the early answers will compete. Once the total number of real answers exceeds 16, these examples will probably be disqualified to avoid having to run large numbers of games, although they will remain attached to the question as examples.

Blind faith

The queen never produces workers, and moves randomly in the 4 diagonal directions by always giving output 0 unless food is in sight. If food is in sight, move to it.

Faith and breadcrumbs

The queen never produces workers, and marks fully explored regions red and regions adjacent to food green.

  • If 0 or 1 pieces of food are visible and own cell is not red, mark own cell red.
  • If more than 1 pieces of food are visible and own cell is not green, mark own cell green.
  • If own cell is red and food is visible, move to it.
  • If own cell is red and no food is visible, move to a green cell or an unmarked cell or a red cell, in that order. Favour diagonal movement.
  • If own cell is green and more than 1 piece of food is visible, move to the first piece of food.

Worker's spiral

  • Queen moves randomly until food is found, and then produces a worker.
  • Workers spiral out clockwise from the queen leaving a directional 3 colour path behind them.
  • Laden workers cut across the lines of the spiral back to the queen (the direction encoded in the path also makes inwards and outwards directions clear, since the workers always spiral clockwise).
  • Freshly unladen workers cut across the lines of the spiral back to the outside and continue spiraling.
  • Queen uses 2 of the orthogonally adjacent cells to keep a counter, and produces a new worker every 50 turns.


This is a parasitic strategy. Fair play is for humans.

  • Queen collects 7 pieces of food without creating any workers.
  • Queen moves randomly until adjacent to an enemy queen.
  • Queen produces 7 workers which surround the enemy queen so she cannot be reached by her workers.
  • Queen sits and waits for returning enemy workers, and steals their food.
  • Freshly unladen enemy workers then go out and find more food.


The queen never produces workers, and follows a straight line path with occasional left turns at random. A single marking colour is used.

  • If own cell is not marked, mark own cell.
  • If only own cell is marked, move diagonally.
  • If own cell and one diagonally adjacent cell is marked, decide based on which of the 4 diagonal cells is marked. For the first 3, move straight (directly away from the marked diagonal cell). For the other, turn left (choose the diagonal cell 90 degrees clockwise from the marked diagonal cell).
  • If 2 adjacent (non-opposite) diagonal cells are marked, choose the next one anticlockwise. This turns right if meeting a parallel path.
  • If 2 opposite diagonal cells are marked, choose an unmarked diagonal.
  • If only 1 diagonal cell is unmarked, choose the diagonal cell 90 degrees clockwise from it.
  • If 4 diagonal cells are marked, move to one of them.
  • If food is seen, move to it and then back to a marked cell to continue.

Join the dots

Follow straight line paths in any of the 8 directions, changing direction each time food is encountered.

  • Queen only strategy
  • If all cells are unmarked, mark own cell.
  • If only own cell is marked, move orthogonally.
  • If only one cell is marked, not the centre, mark own cell.
  • If two cells are marked, one the centre, move directly away from the other marked cell.
  • If food is visible and own cell is marked, move to food.

Sandbox questions

  • Does this sound reasonable: If the number of players exceeds 16, any player that is not above the example answers on the leaderboard will be a candidate for being disqualified to keep the numbers to 16. If all players are above the example answers, the example answers will be disqualified to keep the numbers to 16.

  • I've tried to streamline the question spec as much as possible. If any information still appears in more than one place please let me know.

  • I don't want a queen to have a significant advantage based on starting position. I've currently said she will start in an empty 3 by 3 neighbourhood, but would it be better to specify a larger neighbourhood?

  • I had initially specified a clumped distribution of food, and experimented with different methods of clumping. However, I have now replaced this with a uniform distribution, which I believe is already sufficiently clumped to make search strategies interesting. Since on average each piece of food is more likely to be in a dense region than a sparse region, a piece of food found at random is likely to be surrounded by more densely packed food than is found in general. This makes it worthwhile to search near previously found food even when the distribution is uniform. Is my thinking correct here? If so I will use the uniform distribution because it gives less of an advantage to queens that find food early.

  • There must be an upper limit on the number of players per game. I have proposed 16 players for now. If the number of answers is more than the number of players that can play at once, how should a winner be determined?

  • Interesting strategies are possible with just 2 colours, but I wanted more flexibility and the possibility of a single player combining more than one strategy. Is there any reason to think that 16 colours would be too many or too few?

  • I've settled on 0.1% of cells containing food. I may change this once the controller is written and I've tested a few strategies. This is 2500 pieces of food in total. Although most players probably won't convert all the food they find into workers, the game will still need to have a sensible limit on the number of turns to prevent horrendous slowdown. I'd be interested in hearing any reasons for changing the amount of food or the number of turns (10,000).

  • I want the arena to fit on most computer screens. My aim is to display it at half width and half height, with specific regions zoomed when hovered over with the mouse pointer. So the 2500 by 1000 arena would take up 1250 by 500 pixels on screen. Is there significant demand to make this a smaller pixel region? Is it safe to assume that most monitors can now display this in a full screen browser window? I've based this on the majority of users having a resolution of at least 1280 by 720.

  • Is there anything about the input and output formats that would cause unnecessary extra work? Suggestions for potential alternative ways to get the same information across are welcome.

  • I like the simplicity of 1 piece of food producing 1 worker, and I believe that this can be made to be a good ratio by adjusting the density of food in the initial arena. I have considered requiring more than 1 piece of food to produce a worker, but I'd prefer not to take that approach. If there is a reason that would be better, please let me know. Following Katenkyo's comment about the difficulty of producing the first worker, this is almost certainly going to be 1 piece of food to produce 1 worker.

  • How should the 5 function bodies (queen plus 4 worker types) be presented in the answers? I was originally planning on 5 code blocks at the start of the answer, but perhaps it would be more straightforward (and make for less bulky answers to scroll through) to have a single code block with some kind of separator between function bodies? As long as this is something that won't be found elsewhere in the code and can reliably be stripped out, is there any reason not to do this? The separator could be something like ////////////////. I have taken the advice in The E's comment about combining the 5 functions into one which takes an integer to indicate the ant type, so separate functions are no longer necessary

First of all, it is a really interesting concept, I heard you speaking of it in the chat some times ago, and I'm happy to finally see it ! 16 colors are great, it means having a full 10k turns clock costs 4 cell. I think it is balanced, but if you'd like to see turn counter simplified, 22^3 = 10648 :). I think the major problem for food distribution will be the start, a queen can be greatly disadvantaged by this. You shouldn't touch to the food/worker ratio for the same reason:building the first worker could be hard. The arena size seems nice, and your display idea makes me enthusiastic ! – Katenkyo Jun 17 at 7:40
I think this is the most interesting part of your challenge. It is a good idea. This challenge is all about micro-managing units without memory. If we can use random, we can just use colours as road, and random to make them turn 1/10 cell for instance. With this constraints, we will have to know what setup can be viable. to lead ants AND make some of them turn. (this is the part i'm thinking about actually ^^' and found a pattern which could do the work to spread ants without losing them) – Katenkyo Jun 17 at 13:38
You could have it so that only one function is called regardless of the type of ant and have an integer which tells the ant what sort they are. This would be simpler and smaller than having multiple code blocks or separators. I personally think the more colours the merrier because otherwise you could have 2 bots which use the same set of colours (say 1-8) interfering with each other and another bot using 9-16 and not being affected just by chance – The E Jun 17 at 20:12

Instant Runoff

It's the election! The area which we are in implements the system of voting called instant runoff (sometimes called alternative vote or preferential voting). If you're unfamiliar with how instant runoff works, I'll let this friendly koala explain it to you:

preferential voting

(Image modified from original by Patrick Alexander, used under the CC BY-NC-SA 3.0 AU licence).

(Note: It's also possible, although unlikely, for there to be two or more candidates with the least votes. In these situations, choose one of them randomly and eliminate them.)

If you prefer your instant runoff explanation in text form, there's also the Wikipedia article.

In this challenge, the first line of input will be a pipe delineated list of names, which are the candidates for the election. For instance:

The Omitted Anti-neutrino|Scheduled Kitsune|Alexander the Awesome|The Golden Ratio|Dionysius

Following that are n lines of input, each line which represents a single vote. The votes are also pipe-delineated. The first entry represents that votes #1 preference, the next the #2 preference, etc. For example:

Alexander the Awesome|Dionysius|The Golden Ratio|Scheduled Kitsune|The Omitted Anti-neutrino

would mean that that particular vote has Alexander as their first preference, Dionysius as their second, The Golden Ratio as their third, etc. All votes will have all candidates listed.

Given the votes as input, your program should then output the winner of the election.

Example Inputs and Outputs

Thoughts? Well my first thought is that I should change my display name to Alexander the Awesome... – Alex A. Aug 20 at 23:26
It's also possible for there to be a three+ way tie in last place. And it's not clear whether we should assume a) that everyone votes for every candidate; b) that everyone votes for at least one candidate; or c) that some lines might be blank. – Peter Taylor Aug 21 at 15:28
I didn't understand that picture until I clicked on the link below it and read the whole thing. I think the context of the voting process is important for people's understanding of the challenge. – Bad Cat Eye Aug 24 at 10:34

BlackJack (or Twenty-one, whichever)

As I had a blast working on the original KOTH challenge, I wanted to come up with another. For me, the fun of these AI challenges is in refining a comparatively simple bot which plays a very simple game subtly. Due to the probabilistic nature of card games, I think that blackjack could be an interesting KOTH game just like TPD.


I would be delighted to write some, some of the framework can be derived from my work on the TPD scorer. I just wanted to get some reactions to the idea from mods etc.

Clear Rules

  • perfect/ideal hand has a score of 21
  • all face cards have a value of 10
  • all numeric cards are worth their number
  • aces are worth 11 or 1. this will be dealt with automatically by the framework, not the bots.
  • scores in excess of 21 which use an ace as 11 force the ace to reduce in value to 1
  • scores in excess of 21 which cannot be coerced below the threshold of 21 "bust" the bot

General Ambiguities

  • is the addition of betting too much?
  • how to handle decks and seating? - obviously multiples of the standard 52-card deck will be used rather than random values, but should all the bots play at one table, dealt to from about (n/6) decks, or should they be split into 5-6 bot tables which must be shuffled?

Programmer's Interface

I like the argv-only input from TPD, besides it's easy to implement. 1. argv[1] - your hand as a string say "KJ" in caps, where each letter is the first letter of a card in your hand. So for "KJ", the bot's hand is King, Jack therefore score is 20. 2. argv[2] - known cards on the table - the letters of all cards which the bot could see without cheating. 3. argv[3] - total number of cards dealt (integer as string)

Winner Selection

The winner would be the author of the statistically most successful bot, as determined by the bot's average probability of winning a round. Duplicated bots will be DQ'd, and copied strategies are frowned on.


- Formatting fix (4-4-2011)

Evolution of Squares!

This is an idea for a question, and is very much unfinished. Please help me develop it further.

This is inspired by an evolution simulation I coded a few years ago in JavaScript. The source code and documentation can be found on GitHub, and you can play the simulation itself here.

This will be a . I'll provide a specification which all answers must keep to and a few ideas for features, but otherwise add as many features as you can.


Your task is to build a simulation which demonstrates evolution by natural selection ("survival of the fittest"). The world in which this will be carried out will be a two-dimensional, n by n (exact dimensions to be decided) grid. Each cell on the grid can be empty or occupied by a living cell (or by food resources?).

Cell lifetime

Cells have a 'lifetime counter', which starts at some value when the cell is born and diminishes randomly over cycles of the simulation, so the cells age. It can be replenished by food, but when it reaches 0, the cell dies and is removed (or converted to a food block).

Cells instantly die when completely surrounded? Is that a good idea?


Every so often, cells replicate - produce a copy of themselves, with the lifetime counter reset to maximum, normally with identical characteristics.

There is a probability p (to be decided) that when a cell is replicating, its genome will be changed. It can "improve" or get "worse" with equal probability.

The genome can be as simple as an array of true/false booleans for different characteristics, or an array of integers/decimals describing how much of a characteristic there is (e.g. replication per 100 ticks).

Characteristics which could be included are:

  • faster replication
  • eating other cells to increase lifetime counter
  • movement

The Simulation

The simulation starts with a single, very basic cell, with no fancy characteristics, placed at the centre of the grid. If we decide to implement food resources for cells to pick up, some of these will spawn as well.

Every cycle, cells replicate, age, and die as described above.

There are a wide variety of examples of artificial life out there. Since it's a popularity contest I think there will naturally be variety in the answers. The main thing is to specify the restrictions if you don't want it too open ended... Presumably the length of the code will be restricted as it has to be posted into the limits of a single answer? – trichoplax Jun 7 '14 at 1:35

2048 Low Score

The goal is to make an algorithm that plays as low score in 2048 as possible.


  • Your AI will play the game of 2048 repeatedly.
  • If a game takes more than 2s or scores more than 5000, it will be terminated and score 5000 will be used.
  • If a game gets to Game Over, the final score will be used.
  • The quality of the algorithm will be the average score of the separate games.
  • After 4 weeks, the winner will be chosen. However, if another algorithm is proposed, I will test it and change the winner if necessary.

Choosing the winner

  • Each algorithm will be run 1000 times.
  • The best 10 algorithms will be run again 10000 times to precise the quality.
  • If the score of the two best algorithms is closer than 3% from each other, they will be run 20000 more times. If they are closer than 3% after this, both will be named as winners.

Algorithm specification


  • An example code is in files 2048-core.cpp and rand.cpp.
  • Your code should follow the example of that file: a function int NextStep(const Game&) should be provided.

Other languages

  • I surely work with Python, I should be able to run Java. For other languages, provide a short code together with a way how to compile it, so that I can see what can be done.
  • Provide a program code that accepts the following input:

    <size-of-the-board> <score> <1-if the last performed move actually did something> <the-board-top-line-goes-first>

    So a typical output line is:

    4 156 1 0 4 8 2 0 0 0 8 0 0 2 32 0 0 0 4

    And outputs one number for the next step: 0=UP, 1=RIGHT, 2=DOWN, 3=LEFT.

  • For linking your script to the interpreter:

    1. Download 2048-core.inc, 2048-pipe.sh and io.cpp
    2. Compile 2048-io by g++ -O3 -o 2048-io io.cpp
    3. Run ./2048-pipe.sh ./yourprogram , this should work well.

My PC specification

  • Intel(R) Core(TM) i5-4200M CPU @ 2.50GHz, 4GB RAM
  • Fedora linux 3.14.4-200.fc20.x86_64
  • gcc version 4.8.2 20131212 (Red Hat 4.8.2-7) (GCC)
  • (Anyways, I believe that providing 2 seconds per run is more than generous and should be fine. If more people complain they would use more time, I can extend it.)


  • How to make it available to Windows other than C++?
  • Proper tagging.
Why not keeping the contest open forever? If you close it after some time, that would be annoying for people who see your contest when it is already closed if they want to participate. – ProgramFOX Jun 9 '14 at 14:01

DTMF Decoder


Our spies have intercepted super-secret codes being sent to the enemy in some archaic code! Can YOU decode the captured signals and save the republic?

Find the audio clips at this GitHub repo or in this repo ZIP (7 MB).

Each audio file is 8 kHz and 16-bit, provided in both WAV format and text where each line is one sample. Each file contains 30 tones, each no shorter than 100 ms and with an inter-symbol gap also no shorter than 100 ms of "silence" (subject to noise). The testtones.wav file contains all digits, each 200 ms long, separated by 200 ms.

For reference, each of the symbols/tones/keys/digits is comprised of two superimposed sine waves:

DTMF Table

The difficulty increases as the files progress, with ever-increasing amounts of noise present. level01.wav is basically perfect (except for unavoidable quantization noise), level02.wav starts at a signal to noise ratio of 10, and level08.wav has a SNR of about 1 (equal parts signal/noise). The last file (level16.wav) has a signal to noise ratio of approximately 3%, pretty awful, but I think the theoretical limit is down at about 0.1%. That may be the case only if you know the symbol timing, however, and here the symbols are of variable length.

Your score is the highest level file you can decode without error, with additional tiebreaker points for tones successfully decoded from the next higher difficulty.

Nice idea. If you want to make it code golf, I'd probably leave out all the fanciness and require 100% accuracy. If you want to include additional and varying amounts of noise and phase shifts, I think this should rather be a code challenge and you'd need to provide a large benchmark set of audio files to test against. – Martin Büttner Oct 18 '14 at 0:15

Overhanded (Underhanded) Poker

Also if you make a thing I'll whack everyone involved with a large trout ~ Doorknob

You and your poker buddy are bored, and seeking to liven up the usual poker game. Playing one hand just isn't challenging any more, and you're looking to add a bit of depth. So, why not play with two?


This is a round robin tournament of two-player poker. For each round, a player will need to make two hands of five cards each. To do this, each player will be dealt seven cards, with three community cards to fill out the hands. After receiving their seven cards, players will be allowed to exchange any number of them for new cards from the deck one time.

Once each player has exchanged cards, they will split the ten cards (7 in hand, 3 community) into two hands, Over and Under. The object for the Over hand is the highest ranked hand, while the object for Under is lowest.


In each round, a player will receive one point if:

  • Their Over hand is higher than the opponent's Over hand and
  • Their Under hand is lower than their opponent's Under hand

If one hand wins (Over beats Over or Under loses to Under) and the other ties, you get half a point.

If one player wins one and the other wins the other or both hands tie, no points are awarded.


  • Standard poker hand rankings apply (link chart or something here)
  • Play fair! (will expand on this with the usual KotH stuff)




Obviously this needs some more work. Initial thoughts, questions?

I like this idea a lot (and you getting smacked with a trout is intriguing). One suggestion: it doesn't seem you make a mention of how many games each bot will play against each other bot. Since this problem is (presumably) dominated by the RNG gods, deciding how many rounds are necessary to ensure rewarding good programs instead of lucky programs may be tricky. (Relevant meta) – BrainSteel Jul 8 at 19:03
That's mainly because I haven't decided yet. I'll try to make it enough, but not too many ;) – Geobits Jul 8 at 23:18

Self-Golfing Code

I think it would be interesting to have a challenge to write a program where the program could "golf" itself. The hard part is coming up with the right specification and restrictions to keep the submissions interesting. What I'm currently thinking of are the following:

  • The input is the program's own source code, provided in stdin or as a file.
  • The output is a "golfed" version of the source code that must be shorter by at least 5 characters.
  • If the "golfed" version was run with the same input (the original source code), the output must be the same as the output of the original.
  • If the program was run with any other program (in the same language) as the input, the output must still be syntactically valid. It does not need to shorten it, and it does not matter if the resulting program doesn't function the same way.
  • If the program's source code was placed within another program (in the same language), then running the golfer on that other program would still "golf" the embedded source code in the same way. (The idea here is to prevent something like a program that just deletes the first five characters of itself.)
  • The score is the length of the original "ungolfed" program.

Is this challenge interesting enough in a variety of languages? And what other cheap tricks need to be guarded against?


Gerrymander a Map

Congratulations! You have been selected as the chairman of your state's redistricting commission. It is your job to propose a division of the state into electoral districts. Your true goal, however, is to make sure that your party wins. To avoid suspicion, your divisions should appear as innocuous as possible while still giving your party an edge.

The map will be provided as a grid of 0s and 1s. The 1s represent your party. Below is a simple example map:


You are also given a number which represents the number of electoral districts that must be created. Continuing with the example, 4 will be the number for now.

A division of the map is a partition into N number of contiguous regions. If P is the total population (number of digits), each district must contain at least floor(P/N) people (digits). A division can be represented by a new map, with each district labeled by a unique (non-whitespace, printable) ASCII character. The following represents a division into four segments:


A map has been successfully gerrymandered if the number of districts with a 1 majority is greater than the number of districts with a 0 majority. In the above division, districts a and b have a 0 majority, while districts c and d have a 1 majority.

Here is an alternative division in which gerrymandering was successful.


District a has a 0 majority, while districts b, c, and d have a 1 majority. This means that the 1 party has a clear majority in the election.

The Distortion Metric

There are many ways to gerrymander a map, but you want to make sure that your method passes a visual inspection. Thus, the shapes should appear as regular as possible. One method for measuring this is by summing up the perimeters of each district. The lower the total perimeter, the more disguised the gerrymandering.

aa  c
a   c d
  b c d
 bb   d

Both divisions above have a total perimeter of 32 (each district has a perimeter of 8). On a 3x4 map, this is as good as you can get. Below is a map with a total perimeter of 16 + 22 + 20 + 16 + 22 = 96.


The Goal

The goal is to write the shortest program which, hen given a map of 0s and 1 and a number N, outputs a gerrymandered division of the map into N districts with the lowest possible total perimeter.

More detail coming soon


Random Golf of the Day

Meta: I am running this as a little series of challenges revolving around the topic of randomness - in the form of a 9-hole golf course. I'm maintaining a leaderboard across all challenges in the series, and offer a large bounty to the person competing in all of them with the lowest overall score.

Just to be clear, despite the name, I won't be posting these once a day. Expect the next one in 6 to 8 weeks.

About the Series

This will be a series of 9 challenges. See the first instalment for more information about the series.

#1: Shuffle an Array

#2: Numbers from a Normal Distribution

#3: Integer Partitions

#4: The Bertrand Paradox

#5: Diamond Tilings

Further ideas (still unordered):

  • Poisson disc sampling: This is a method to randomly distribute points across the plane densely while maintaining a minimum distance between points. I think this might be nice to golf. Further reading.
  • Generate a random chessboard: The submissions should randomly produce a believable chessboard. "Believable" here mostly affects pawns: they may not appear on the first row of their colour, there may be more pieces of other types if pawns are missing (due to conversion), and two pawns may only be in the same column if at least one of the opponent's pieces is missing. Submissions should be able to generate any valid board with finite probability, but it doesn't have to be uniform.
  • Generate a random arithmetic expression: This basically asks to create a tree of binary and unary operators, subject to some constraint - either on the structure of the tree (n nodes, say) or on the result of the arithmetic expression (generate a random expression that evaluates to a given n).
  • Generate a random hole-free polyomino (or orthogonal polygon) (of given size).
  • Vague idea: Generate points on a sphere with uniform distribution.
  • Vague idea: I'd like to include a challenge on random walks.
  • Vague idea: I'd like to include a challenge which has to generate a random number with a constraint based on its digits, but where you're not allowed to use strings or arrays (so you have to access the digits arithmetically).
  • Idea I'm not sure about: Generate a valid Unicode character as a set of UTF-8 bytes with uniform randomness.
  • Idea: Implement a (specific) PRNG.
  • Idea: Generate a random Brainfuck program (or other balanced string). Would probably need to require uniform distribution and deterministic runtime to be interesting.
Idea: "reverse-engineering". Given a sequence of 1000000 random numbers from a generator of a known type (e.g. this), determine the next number. Have to discourage (or somehow disallow) brute-force answers. – anatolyg Mar 3 at 21:32

Thinking functionally (1): removing variables

If you're not programming functionally, then you're programming dysfunctionally.

Long time ago, in the first ages of universe, coders and variables were living peacefully; but one day, they turned evil and then began a long war between them and men. Unfortunately men could not do much against so many variables. Only a few men are still alive today, but fortunately you can do something for them. You have heard about the ancient art of computer programming and you even spoke one day to a very old functional programmer. Your mission is to kill as many variables as you can.

This should be the first challenge in a longer series called "Thinking functionally".

Goal: write a short and interesting piece of code in some language where variables are usually needed (we all know that you can write some code in J or in some stack-based language with no variable, but please, choose some other language for this challenge), and use fewer variables than what would have been expected. You must explain what you did.

Rules: What has to be avoided here are mainly variables involved in keeping some information for later use (next step, next iteration, next line, etc.); this covers global or local variables, closures, etc.; if list or tuples are obviously used to replace several variables with no interesting "trick" they should be avoided. Using complex numbers in a tricky way is ok, but using some mathematical operation with them should be preferred rather than merely using separately both parts in the number. Using bitwise trick is fine, but again, try to be clever (see example 1 below) and don't use them only with some masks for separating the data. In all cases, mathematical tricks should be preferred rather than complicated ways of inserting data in some type. On the other hand, you are allowed to use as many bound variables for writing functions as required. Your code should explicitely contain an interesting "trick" for avoiding a variable in a place where everybody else would have used one. The most important requirement is: don't try to hide data with too much energy, rather ask yourself if data is really useful.

Example 1: Here is a first example in python, acceptable and interesting. The computer will guess which number you are thinking at with an optimal strategy, with only one variable.

a = 256

while True:
  print("I am going to guess the number you are thinking at.")
  print("Is it",a,"?")
  print(":: 0 for less, 1 for more, Ctrl-C for OK")
  a = (
      lambda x: x - ( (1 + (x ^(x-1))) >> 2 ),
      lambda x: x + ( (1 + (x ^(x-1))) >> 2 )
  )[input("? ")](a)

Explanation: usually this game requires at least two variables, a and b, which allow the program to remember the smallest and largest possible number, then a third number is computed (a+b)/2 and a or b is updated according to the answer of the player. Here the code uses only one variable, and checks for successive bits in order to set them or not. It is obvious here that no hidden data is used, but we notice that the "natural" way of coding this game is redundant; using two variables isn't really needed since each guess actually belongs to a single possible path.

Example 2: Here is another example, acceptable but not as much interesting. How can I swap two variables?

a = 42
b = 17
a = a + b
b = a - b
a = a - b

Explanation: everyone knows that three variables are needed for swapping two variables, and we laugh when students try something like a=b followed with b=a, but you actually can swap variables without any temporary variable.

Score: this is a popularity contest; the winner will be for the answer with the most upvotes. Vote for an answer if you find it clever and tricky.

You probably need to say something about scope (to rule out the argument that the first example actually has three variables: a, x, and the other x) and bit packing (since Minsky proved that it's possible to have a Turing-complete system with only two variables using Gödel numbering, and it can be argued that every Fractran program uses only one variable). – Peter Taylor Mar 25 '14 at 22:29

Good Vibrations

The sound of the theremin has been immortalized in The Beach Boys song Good Vibrations. Many also associate its sound with the theme for the original series of Star Trek, though apparently it was a soprano's emulation.

This challenge requires you to implement a theremin.

  • Take 2 dimensional input from a mouse or other input device (e.g. you could use a joystick), which will produce a tone from an audio output device as follows:
    • increasing x will increase the frequency of the tone. Note that frequency increases exponentially with musical note, so you must implement a linear relationship between mouse x position and the musical note, and
    • increasing y will increase the volume of the tone.
  • There appears to be confusion regarding the waveform produced by a real theremin, so for simplicity, a sine wave (or close approximation thereof) must be used.
  • Because the output tone is dynamically-generated, care must be take to ensure the tone is a continuous waveform; that is there are no audible clicks or pops caused by sudden changes of phase or amplitude.
  • The tone produced must have at least a 2-octave range. More range is acceptable. A-440 must lie within the range.
  • In order to create the audible appearance of continuously variable frequency and amplitude, the range of values considered in both dimensions from the input device must be at least 500 Implementations may open a window (at least 500x500 pixels) to read input from mouse cursor position. Or without opening a window, coordinates may be read directly from the mouse or other input device.
  • There must be a simple means to stop the program - key-combination, mouse-click or other common input device. CTRL-c is sufficient.
  • Any standard libraries may be used, as long as they do not totally implement the solution with no other work required.

This is , so the shortest answer in any language wins.


Epic Customizable Tank Battle (Work-In-Progress)

This is an idea I have been working on in conjuction with users @Trimsty and @githubphagocyte in the chat room. It is inspired by the flash game "Bubble Tanks" by Armor Games.

This will be a challenge.

Main Idea

The main idea is that a large number of competitors fight each other in a large arena. Each program is the AI of a different tank. These tanks are customizable from a list of available parts which can be purchased, so the competitors can choose how to upgrade their tank as the battle progresses and they earn points.

The Arena:

The arena may be an almost-infinite plane with a light source near the center. Tanks can travel far away, but lose energy away from the light. This is a continuous-space game, so the tanks have locations/directions determined by floating-point numbers.

The Bots:

The tanks are basically circles, with the center point of the tank being the location. There is no collision detection, except that projectiles inside of another tank's radius are considered hits. The tank's size (radius) will be determined by the different upgrades it has, with larger weapons giving more size.

Bots will also have a health level which reduces upon injury from opponent's weapons. The health will start at some number, and the bot dies upon the health reaching zero. As bots kill others and collect points, health can be restored over time.

If a tank goes too long without making progress (collecting points or killing), then it will begin to rust. Rust will slowly damage the tank and kill it. Rust can be eliminated by making progress.

Weapons also need time to recharge, and this time is dependent upon rust and other factors.

The tanks are solar-powered. The farther the tank goes from the light source, the slower it can move, the longer it takes for the weapons to recharge, and the shorter its range-of-visions is.

Bot vision:

A tank's vision range will be determined by the light level. If an object is located in a high-light area, then it can be seen from farther away. An object in a low-light area can only be seen by nearby observers. A tank will be able to see things which are closer than the light level in that object's location. The bot will be able to see other tanks, as well as other features (bullets in-flight, heat-seekers, maybe mines). The information available about other tanks will be that tank's weapons (maybe).

Winning criterion:

Each match will be one single battle-to-the-death involving all of the tanks. The tanks' scores will be the time until death.

It might be that several matches are held with the winner being the contestant with the highest average (or median?) score.

Upgrade system:

Each tank starts with a certain number of skill points (4000) and a certain kill value (10). The tank can spend skill points on upgrades to the various weapons. Once a bot spends points on an upgrade, the transaction cannot be reversed.

When a tank kills another, the victor's own kill value is increase. The killed bot drops skill points on the area which can be collected by nearby bots. The kill value of a bot determines (in part) how many skill points will be dropped upon that bot's death.

Types of weapons:

  • Guns of various ranges, strengths, and reload rates
  • Lasers
  • Mines (proximity and timed)
  • Area-effect (damages nearby bots)
  • Heat-seekers (costly and very accurate, but short range and low damage)
  • Shields (not a weapon, but a form of protection that comes in different strengths)

Additional Notes:

There may be different feature which can be added, such as: - flashlights which enable bots to see farther in the dark zones. - self-destruct, which scatters the dropped points across a broader area. - leech-weapons which steal health - speed boosts or reductions


Some sample code provided by trimsty about skill points and kill values:

class BotsThingy:
    def __init__(self):
        self.bots = []
    def fatalShot(self, firer, victim):
        d = (self.bots[firer].points - self.bots[victim].points) / 15
        if d < 0:
            self.bots[firer].killValue -= d
            self.dropPointsAt(d + 50 + self.bots[victim].killValue * 5, self.bots[victim].location)

# bot.killValue starts out at 10.
# bot.points can be anything that's above 100-ish, I'd say 4000 is good.

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.


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


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.


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.


  • 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


(in progress)

enter image description here

2. Lego pieces/attachable cubes – trichoplax Jan 25 at 21:07
5. Controller-mediated build-your-own data structure – trichoplax Jan 25 at 21:11
B. Attachable unit cubes (for simplicity) – trichoplax Jan 28 at 8:36
I. Code golf (fewest bytes) – Sp3000 Jan 28 at 23:43
II. Fastest algorithm – Sp3000 Jan 28 at 23:44
Number of cube structures: – Sp3000 Jan 29 at 0:42
2. Any number of structures – Sp3000 Jan 29 at 0:43
A. Connections should be explicitly given via a function call – Sp3000 Jan 29 at 0:44
Moving to 2D might simplify rotations greatly, while retaining enough complexity to be worth a challenge. – user16991 Feb 5 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 at 21:30
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 at 11:22

Frame ASCII art

I draw ASCII art on a rectangular canvas of spaces. This can leave some sides with too much empty space, while others are flush against the edge.

       |\                   \      l____       
       | \___________________\     |\   \      
       | |                    |    |\l___\___  
  [__]_[ |                    |[\\]| |__|_\__\ 
 /\[__]\ |                    |\[\\]\|. | |===\
 \ \[__]\[____________________] \[__]|__|..___]
   ( @ )                        ( @ )  =  ( @ )
    `-'                          `-'       `-' 

(Image from http://www.chris.com/ascii/)

Write code that outputs the ASCII art framed with a margin of one space on the top and bottom, and two spaces on the left and right.

|                                                  |
|         ____________________                     |
|        |\                   \      l____         |
|        | \___________________\     |\   \        |
|        | |                    |    |\l___\___    |
|   [__]_[ |                    |[\\]| |__|_\__\   |
|  /\[__]\ |                    |\[\\]\|. | |===\  |
|  \ \[__]\[____________________] \[__]|__|..___]  |
|   \/.-.\_______________________\/.-.\____\/.-.\  |
|    ( @ )                        ( @ )  =  ( @ )  |
|     `-'                          `-'       `-'   |
|                                                  |

Fewest bytes wins.


Truth is one, paths are many

A truth-machine is a simple program that works like this:

  • If the first and only character on STDIN is the digit 0 (the byte 48), the program outputs a 0, optionally followed by a newline (the byte 10), and terminates.
  • If the first and only character on STDIN is the digit 1 (the byte 49), the program outputs 1\n1\n1\n... (alternating bytes 49 and 10), looping forever.
  • In any other case, the behavior is undefined -- the program may do whatever.

(The idea derives from the esolangs wiki, where truth-machines are used as a prototypically simple program that demonstrates I/O, decision, repetition, and termination. Often, these concepts are represented in unique ways in esoteric programming languages, so that this simple program is representative of any language's quirks. I've rewritten the definition to be a little more exact.)

Your task is to write a program that is a valid truth-machine in as many programming languages as possible. For example, the following code is a truth-machine in Python 2 and in C99:

#include <stdio.h>
a = 0 // 1; """
; int main() {
    char c = getchar();
    do { putchar(c); puts(""); } while (c != '0');
    return 0;
} /* """
c = input()
while True:
    if c == 0: break #*/

Code length is not a factor in scoring. The submission that covers the most programming languages by (two weeks from now) wins. If there are two leading submissions that work in the same number of languages, community votes shall be a tie-breaker. (Failing that, I'll pick a winner myself, favoring creativity and use of "weird" languages.)

This feels like a simple, fun challenge. Considerations:

  • There have been previous challenges, but most of them require your program to print a constant string. This one actually demands logic, so submissions will need to rely less on how e.g. print("hello") happens to work in many languages (Python, Python 3, Ruby, Julia, QBasic, R, Lua...)

  • This is not . Code length isn't a factor, so there's no "balance" to make: I want to encourage very elaborate solutions that are valid in dozens of languages by interleaving comment syntaxes and whatnot.

What I need help with:

  • Counting languages. We've established what constitues a programming language in Meta, but how do I stop a Brainfuck solution from being counted as Brainfuck, Brainfuck++, [Brainfuck$](https://esolangs.org/wiki/Brainfuck$), etc? Are Python 2 and Python 3 different languages? I feel like there must have been discussion on this before. I want to establish some good condition for "are these two languages distinct", without strictly imposing a set list of languages.

  • (This is minor, but) tags. I'm considering and . Is anything else relevant?

And if you start talking in terms of languages being derived from others and looking at genealogy, you run the risk of prohibiting C/Java polyglots, even though they're very different languages. – Peter Taylor Aug 23 at 7:38
@PeterTaylor: One idea I'm thinking of now is to have a curated list of languages based on this query that counts the most common languages used on the site, and allow only those. This sounds overly limiting, but very many languages people like to use are still on there, and it's the only way to avoid disputes or confusion. Here's a tentative list of languages with at least 10 answers in them on the site. – Mauris Aug 25 at 22:23

Is this word a valid gismu?


The language Lojban is a constructed language, meaning in part that all of its words have been created rather than allowed to develop naturally. The semantic base of Lojban are its gismu, or root words, which were synthesized by combining roots from widely spoken natural languages like Chinese, Hindi, and English. All gismu are 5 letters long and follow a certain strict form.


For our purposes, the Lojban alphabet is:


That is, the Roman alphabet without hqwy.

This alphabet can be divided into four categories:

  • Vowels aeiou

  • Sonorant consonants lmnr

  • Unvoiced consonants ptkfcsx. When voiced, these become respectively the...

  • Voiced consonants bdgvjz (No voiced consonant corresponds to x.)

To be a valid gismu, a 5-char-long string must:

  1. Be in one of the consonant-vowel patterns CVCCV or CCVCV, where C represents a consonant, and V represents a vowel.

  2. Follow consonant-matching rules.

Consonant-matching rules for CCVCV words:

The first two characters must constitute one of the following 48 pairs (source):

bl br
cf ck cl cm cn cp cr ct
dj dr dz
fl fr
gl gr
jb jd jg jm jv
kl kr
ml mr
pl pr
sf sk sl sm sn sp sr st
tc tr ts
vl vr
xl xr
zb zd zg zm zv

Note that this looks rather nicer when separated into voiced and unvoiced pairs. In particular, every voiced-voiced pair is valid iff the corresponding unvoiced-unvoiced pair is valid. (As you can see, this does not extend to pairs with a sonorant consonant.)

Consonant-matching rules for CVCCV words (source):

The third and fourth characters must follow the following rules:

  1. It is forbidden for both consonants to be the same [...]

  2. It is forbidden for one consonant to be voiced and the other unvoiced. The consonants “l”, “m”, “n”, and “r” are exempt from this restriction. As a result, “bf” is forbidden, and so is “sd”, but both “fl” and “vl”, and both “ls” and “lz”, are permitted.

  3. It is forbidden for both consonants to be drawn from the set “c”, “j”, “s”, “z”.

  4. The specific pairs “cx”, “kx”, “xc”, “xk”, and “mz” are forbidden.

Note that there are 179 of these pairs possible.


Determine if the given string follows the gismu formation rules. This is , so fewest bytes wins.

Input: A string of length 5 from the Lojban alphabet.

Output: A truthy value if the string can be a gismu and a falsey value otherwise.

Test cases (will add more)





Evading smokers

I'm a non-smoker. And pretty adamant about that as well. Since I also have a hypersensitivity against anything smoke-like (cigerette smoke, exhaust gases, incense sticks, ...) I tend to evade them if possible.

Given a map that contains walkable terrain and obstacles as well as position of people and their movement vectors, figure out a path to your destination that will expose you to as little smoke as possible.

Smokers have clouds of smoke around them in a certain distance and therefore leave a slowly-fading trail of smoke you'd better avoid. People don't change their walking direction and if they bump into an obstacle it's their fault; you can ignore them trying to walk through walls there.

Just a rough idea. This would be a code challenge, not a golf and I think it still needs way more details. This is mostly so that I don't forget the task :-)

Path finding and minimization. It can be written to call for floating point arithmetic if you wish to make like hard for the GS hackers. Nice. The input format would need some consideration as it could get complicated in a hurry. – dmckee May 13 '11 at 0:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .