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 '15 at 11:15
When you think your challenge is ready for the public.... Can I suppose my challenge is ready for the public if it has a positive score and has one day past after its post? I'm asking that because I can't see how many people have read my post to measure ready for the public status. – removed Mar 23 at 11:43
@WashingtonGuedes People often upvote interesting challenges even if they aren't ready. If you have no comments and a score of >1, I say that it is definitely ready, whereas a score of 1 may be some drive-by upvoter. – Justin Apr 2 at 7:23

988 Answers 988

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 (x,y) cells 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, JSON protocol over TCP. Messages have the following format:

^ Length (4 byte, unsigned int)
    ^ Values (Exactly length bytes long)

Where Values is a JSON encoded string

Potential keys you will recieve in Values:

  • "state"
    • Recieved when your bot changes state
    • Possible states are:
    • connecting
    • config
    • lobby
    • in_game
  • "get_move"
    • Null value
    • Recieved when the game wants to know what move you will make
  • "move_data"
    • Update the cells to the opponents colour but only if empty
    • Nested coords list format
      • [[0,0], [0,1], [100,22]...]
  • "tick_board"
    • Tick the board by one (Apply rules)
  • "rtn_state"
    • Internal state of your bot
    • Only sent in reply to "get_state" command
    • Contains:
      • "state"
      • "allow_training"
      • "force_training"
      • "author"
      • "bot_name"
  • "scores"
    • The updated scores file
    • Only sent when a game finishes and you win
    • Keys are bots you have won against and the total number of wins against that bot

Keys you may send to the server

  • "identity"
    • Only in the "connecting" state
      • "author": "CodeGolf Username",
      • "name": "Awesome bot name!"
  • "configure"
    • Only in the "config" state
      • allow_training: Boolean, will your bot go into training matches?
      • force_training: Boolean, is your bot only going into training matches? (only if allow_training)
      • training_timeout: Integer, How many seconds will your bot wait until going into a training match (only if allow_training and not force_training)
  • "get_state"
    • Ask the server about your internal state, server will reply with "rtn_state"
  • "disconnect"
    • Politely disconnect
  • "update_state": update_state
    • Send the server a list of square to turn to your colour.
    • Only those that are empty will be changed
    • Nested coords list format
      • [[0,0], [0,1], [100,22]...]

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

  1. Connect to the central arena server.
    • Host dustbunny.catbus.co.uk
    • Port 7777
  2. Wait until server responds with {'state': 'connecting'}
  3. Send identification {"author": "PPCG Username", "name": "Awesome Bot!"}
  4. Wait until server responds with {'state': 'config'}
  5. Send configuration {'allow_training': true, 'force_training': true}
  6. Wait until server responds with {'state': 'lobby'}
  7. Wait until server responds with {'state': 'in_game'}
  8. Wait until server responds with {'setup_game': {'y_size': 2000, 'x_size': 2000, 'game_time': 60}}
  9. Create a (x_size, y_size) sized array filled with 0s
  10. Play!

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

  • 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 most game wins is the winner

Current notes

  • The scoring system as is is to prevent cheating - what would the point be of giving other bots points? (This is also relatively easy to detect and disqualify bots that have practically no wins and lots of losses)
  • I'll have to work out a way of making the lobby pit bots that haven't played each other much against each other - maybe prioritise bots that haven't played much?
  • The server is currently up at the moment in case people want to have a preview of what the game's like - I will reset scores before posting
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 Ender 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 Ender 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 '15 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
Can the doctor protect himself? – Justin Jun 30 '14 at 20:51
The doctor can protect himself, and often it is a good idea to do so in the early rounds, so you have leverage to say "I am the doctor." Being able to identify the doctor early is valuable for the village, not because he can save people, but because you know he isn't a mafia. The mafia can use this to their advantage when losing, by attacking a fellow mafia member. If the mafia accidentally get saved by the doctor, it exonerates them in the eyes of the villagers. This is gambling, but gambling is what you do when you are losing. It's also a trick play that only works once. – Rainbolt Jul 8 '14 at 14:21

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
Well, the only argument I have is that I don't remember the Mr Jones' bicycle question. – Mr Lister Mar 15 '14 at 12:09
@Gareth Are you still intending to post this at some point? It sounds quite interesting, but I think you need some more specification on track adjacency. As I read the definition || are two adjacent tracks, which makes using different directions somewhat pointless. Likewise, I don't think there is currently any real notion of "crossing its own path", which would mean that I can just replace all spaces in the input with |. – Martin Ender Sep 4 '14 at 11:16
@Gareth 8 upvotes and close to 4 years now ;) – Martin Ender Mar 4 '15 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 '15 at 14:02
@SonicAtom This question proposal is nearly 5 years old. The only reason I've been considering resurrecting it is because of the number of upvotes it's attracted recently. 33 since March last year. Possibly it's just because of the title though... – Gareth Jan 25 at 12:42

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?

This is a good code-golf challenge, why haven't you posted it already? – Khaled.K Dec 30 '15 at 10:14

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 Ender 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 '15 at 8:05

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?

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 Ender Jan 9 '15 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 '15 at 23:35
If the handedness/chirality of the dice is also guaranteed to be consistent then identifying 2 visible faces will uniquely determine the 3rd visible face, as a double check or to fill in unreliable data. I think it's worth stating explicitly whether the dice will be of consistent handedness. People can of course work this out for themselves by examining the image set, but it would be good to know for certain whether that is meant to be a reliable feature of the images. – trichoplax Jan 12 '15 at 23:37

This is not a challenge. I am using the sandbox to... sandbox stuff.

My Progress

I'm not anywhere near the completion of this, but I've got an attack plan. They key word here is "abstraction." If a problem seems too esoteric to solve (as in this whole challenge), just abstract it to he next level

  1. Use GoL to create metapixels which are capable of emulating any "life-like" rule. This means that a particular metapixel is in one of two possible states, and its rule is defined by birth and survival rules.

  2. Use these metapixels to create something akin to Wireworld. The key to this is that different metapixels can be assigned different rules.

  3. Create a set of useful logical components, each of which is the same size (the size can be arbitrary, as smaller components can have their I/O wires extended to make them "larger"), and each of which have the same delay. This means that, if the component fits in a 20x20 square, there must be exactly 20 generations between when the signals enter and leave. This way, the delay of each component (including wire) is uniform, and then we can treat them as "tileable".

  4. Use the tileable logic components to create circuits. All of the effort we spent on small-scale timing should mean that timing is a lot easier to calculate at this stage.

  5. At this point, we may be following in the footsteps of the Wireworld computer. We will need to build a large RAM bank and a display screen of some kind, which will serves as the actual RAM/screen for the game.

  6. Depending on the architecture of the computer (probably MOV-only, like the Wireworld computer), we can write a compiler that converts some human-readable language to assembly for the device.

  7. Program Tetris.

enter image description here


These are just some words I am going to use, and some definitions to make sure you what I am talking about. Since this whole project is basically "cell-ception," it can get confusing. If someone has ideas for better/more accurate terms, you can make suggestions.

  • Pixel / GoL cell - The lowest level of cell, referring to the bare B3/S23 cells of the underlying GoL.
  • Metapixel - Specifically the OTCA metapixel, this is the next level of cell. Comprised of GoL cells, each metapixel can be assigned its own life-like rule. Different metapixels can be assigned different rules. Metapixels are 2048x2048 GoL-cells in size and have a period of 35328 GoL-gens. An effective simulator for metapixels is Variations of Life.
  • Logic unit/cell - Each "logic unit" is comprised of metapixels, and represents a single logical device, like AND/XOR and wires. Logic units will have two states, and will require some careful edge matching so that input and output edges match up. If the timing of the underlying metapixel pattern is done properly, the logic units will be able to function in uniform time steps (generation-wise, like a more complex CA). Until we finish all of the logic components, I will not know the precise size/timings.

Known logical components

  1. Wire
  2. Wire corner
  3. Signal splitter
  4. Diode
  5. AND gate, and asym-AND gate
  6. OR gate, with the asymmetrical version created by replacing the central B2/S of the asym-AND with B12/S1.
  7. XOR gate, with asym-XOR using a central B2/S.
  8. Wire crossing
  9. Some diagonal wiring.


  1. A-and-not-B gate (aka N-IMPLY gate), of which there are 3 versions to make. This will complete our set of 9 core logic gates (2 AND, 2 OR, 2 XOR, 3 N-IMPLY).

  2. Once other components are created, we need a "clock" unit that sends out a signal as the proper intervals, depending on the size of the other components. Clocks are easy, we just need to do other things first.

  3. Attempt to adjust the existing parallel-wire-crossing design so that it fits in a 1x2-tile area.

  4. NAND/NOR/XNOR gates that contain an AND/OR/XOR gate with a clock and which fit in a single cell.

Devices unlikely to be constructed

  1. A native NOT/NAND. Anything that gives output with no input is generally difficult, since the timing between output signals must be carefully controlled. Rather than NOT, I think the best that can be done is XOR hooked up to a clock.

Animations of Logical Components

Here's a GIF of an "electron" flowing in a wire. Black is B/S, blue is B1/S, green is B2/S, red is B12/S1.

enter image description here

Here are two AND gates (the first is not animated yet).

enter image description here

enter image description here

Here is an XOR gate:

enter image description here

Wire crossing:

enter image description here

Diagonal wires:

enter image description here

I am attempting to make each "core" component have the same size and latency, so that each component can act as a "metametapixel" which can be mixed and matched to form digital circuits without working about finer details, leading to the next layer of abstraction.


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 '15 at 22:33

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

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 Ender Oct 18 '14 at 0:15

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 '15 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 '15 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. – Beta Decay Aug 24 '15 at 10:34

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

#6: Roll a d20

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 '15 at 21:32

Is it a bird, is it a plane?


Supplied an image, you must determine if the subject of the image is a bird or a plane.

Further information

All images will be the objects in flight.

The images of planes and birds will be against blue backgrounds (in some there may be light cloud in patches).

All birds will be pictured gliding from underneath, with their wings spread open. They will not always be the same species.

All planes will be commercial jetliners, pictured from the side. Their liveries may differ and the models will not be the same.

You may not use any external libraries, functions or online resources which perform image recognition.

The images will not be revealed to the competitors.


The following examples will not be used in the 30 test images.




Given 30 images of birds and planes, the program which identifies the most of then correctly wins.

In case of a tie, the shortest program wins.

Do we get a bonus if we correctly identify the picture as being Superman? – Neil Jan 31 at 10:20

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)

Digital Music Box

What are holidays without music boxes?

Your task is to implement a digital music box. Your program will be given a reel of music such as follows:

Music from "The Polar Express"
By Glen Ballard and Alan Silvestri
120 lines per minute

Now, your program must play the music, which is straightforward. In this example, one line is read every 1/2 second. If a line contains one or more O characters, those notes are played simultaneously to form a chord.

The range of the music box is a Concert C scale from Middle C (C4) on the left to High C (C6) on the right.

When a chord is played, the sounds of all previous chords are stopped. If a line does not contain any notes, then the previous chord is sustained at reduced volume.


Input will be several lines of text. Your program should read and follow the directions line-by-line.

If a line contains ### lines per minute then each following line of music should be played at that tempo. There may be more than one tempo change in the piece, and your program should be able to change tempos. The tempo change itself does not take up any time. There will always be a tempo mark before any music lines.

If a line contains music (15 characters long, all characters either . or O), then those notes should be played and sustained for the correct duration (given by the tempo).

If a line does not fall into either of the above categories (like Music from... and CDEFG... in the above example), then it should be ignored completely. The program should act as if they weren't there, simply skip over them with no pause.


Output could either be sound from the speakers, or a playable .MP3 or .WAV music file.


Should this be code golf? I assume so, although I want an added bonus for improved sound quality. It's probably not going to be possible to enforce sound quality requirements.

Are there any other things to add? Or, is this pretty much ready to go?

"When a chord is played, the sounds of all previous chords are stopped" — this isn't how music boxes normally behave; each note just fades out until it's played again. Also, how about accepting MIDI files? – squeamish ossifrage Jan 14 '14 at 10:22

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 Ender 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

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 '15 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 '15 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 '15 at 20:12

I can't believe it's not a Platypus!!!

This is an image of our wonderful pet platypus @Cyoce.

enter image description here

This is also an image of the same person, or is it?

enter image description here

(hint: it isn't)

Your task is to determine whether a inputted image is @Cyoce in disguise...

The input may be taken in any form. It will also always be 256*256px.

You will compare the image to the top image, @Cyoce profile image.

If the image is not within 1000 units of the profile picture, you must output the phrase "I can't believe it's not platypus!!!" exactly.

A unit is decided by the following:

  • If a given pixel is rgb(255,255,255) in the inputted image and rgb(250,250,250) in the martin image, it is 3 units away. That is one unit per 5 rgb points off. So rgb(100,120,100) vs rgb(100,100,100) is 4 units off. Floor the units, so 255 vs 253 is just 0.
  • Calculate that for each pixel, and sum the units.

If the inputted image is more than 1000 units off, output the title phrase "I can't believe it's not a platypus!!!"

Sandbox notes:

  • This is in development.
  • Test cases coming later. Feel free to provide some.
  • If somebody has code they would like to donate to me for test case generation, please do. :P
  • I might change the units req. to a higher number depending on how this turns out.
  • Any other advice?
Haha, I like this but it does seem rather simple. If a language can only take the pixels as an array of RGB numbers it's pretty trivial (map, divide, floor, sum). Maybe it could be some kind of average so that 150 180 30 would have the same number of units as 100 120 20 (a darker shade of the same colour)? Or match rotated/flipped images? – user81655 Jan 14 at 12:27

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?

It's still a code-golf. That's part of the challenge - you still have to golf it but leave room so that your program can still golf itself a little more. I think it would be interesting to see what approaches people take for this. – migimaru Aug 17 '11 at 14:28
You'll need to ban comments, unnecessarily long variable names, all unnecessary whitespace... And even then I can see fairly easy cheap tricks like unnecessary variable swaps (`\` in GolfScript). Hard to make this robust enough. – Peter Taylor Aug 29 '11 at 8:48
I believe it's a tad to vague. It would be too easy to do something like (in JS for e.g.) $$$$$$=eval(prompt().replace(/$+/g,"$"))... unless if that's what you want, of course. – Cᴏɴᴏʀ O'Bʀɪᴇɴ Oct 19 '15 at 17:45

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.


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
As far as tagging goes, I'd go with code-challenge. – nneonneo Jun 28 '14 at 23:45

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 '15 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 '15 at 23:18

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

Meta Code Bots

I'm just giving this a "code bots" title because that's the most similar previous KOTH. This version is based on the Twin Tin Bots board game, and will probably be given a better name before posting.

On a far away planet, dozens of small mining robots compete for resources in the form of tiny crystals. Each individual bot is quite simple in its programming: given a series of steps, they can attempt to follow it. These bots, however, are remotely programmable, as their programming can be slowly edited over time to respond to current conditions. In this challenge, you will write a program to program these bots.

The Game Field

The playing field is a rectangular grid, with each cell containing either nothing, a robot, or a crystal.


Robot Programming

Each robot contains a program, which is a series of basic steps that the robot can perform. The program is always 24 commands long.

  • HALT (H) - If a robot executes this during its turn, its turn is immediately over. The entire program is initially filled with HALTs.
  • MOVE_FORWARD (FORWARD/F) - The robot who executes this command will move forward 1 square if possible, pushing up to one other robot/crystal.
  • TURN_RIGHT (RIGHT/R) - The robot will rotate clockwise by 90 degrees.
  • MOVE_BACKWARDS (BACKWARDS/B) - The robot will move backwards 1 square if possible, pushing up to one other robot/crystal.
  • TURN_LEFT (LEFT/L) - The robot will rotate counterclockwise by 90 degrees.
  • GRAB (G) - The robot will pick up a crystal if there is one directly in front of it. Also, if there is instead a second bot directly in front, this will steal a crystal from that bot's inventory.
  • DROP (D) - The robot will take a crystal from its inventory and drop it, if possible. If there is an empty space in front, the crystal would fill that space. If there is instead a robot in front, then the crystal is added to that bot's inventory.
  • ZAP (Z) - This is the most interesting command, and probably deviates the most from the original game. A zap command allows one bot to issue a command to the bot directly in front of it (if any). If bot-1 is directly facing and adjacent to bot-2, then bot-1 can zap bot-2. The very next token in bot-1's program will then be executed by bot-2 instead.
    • An example: The program L,F normally causes the current bot to turn left then move forward. The program Z,L,F causes another bot to turn left, and then the current bot to move forward.
    • The ZAP command can be stacked: Z,Z,F causes the bot in front of the bot in front of this bot to move forward.
  • JUMP (J) - This serves as an unconditional jump. This causes the program execution to jump forwards to the location immediately after the next HALT. For example, F,J,R,H,L causes the bot to move forward and then turn left. The R,H is skipped over.
    • A program with a JUMPed section acts exactly like a program with that section removed. So, F,J,R,H,L acts exactly like F,L, and Z,J,H,D acts exactly like Z,D.
    • JUMP can be used to easily switch between multiple complex behaviors. For example, F,F,H,R,R can easily be edited to form J,F,F,H,R,R.


  • The steps ZAP,HALT will not have any effect. The bot performing the halt wouldn't be the current bot, since the zap causes the halt to be performed by the bot directly in front (if any). The HALT command only has an effect if it is executed by the bot whose turn it currently is.
  • The steps ZAP,ZAP,HALT might have an effect. If two bots are facing each other, then the HALT would be executed by the original bot, ending the turn. If the bots aren't facing each other, then the HALT would be executed by a third bot (or nobody at all), having no effect.
  • In the original game, the zap command allows the zapping player to perform "special action" on his turn that affects the target bot (the player, instead of the bot programming, determines what the zap does). Here, the action of zaps are determined by the bot program.

Editing the programming

Each turn, the bot's programming can be altered. Any number of commands can be removed (shifting the following commands to the left and adding a HALT to the end). Only one command, however, can be inserted each turn (shifting the following commands to the right and deleting the last one).

Execution Order

The players take turns in a cycle. On your turn, your program will receive the current game map (probably a int[]) and your current bot's program. Your program can then submit the edited bot-program. Your bot's program is then immediately executed, affecting the board before the next player's turn begins.

More spec coming later... The controller is currently under construction.


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

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.
You had me at "lasers." – Alex A. Oct 11 '15 at 19:11

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


You must log in to answer this question.

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