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:

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

1061 Answers 1061

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)

Will the control program empty the to_server and from_server files or will that be the responsibility of the bot? Should the bot wait for to_server to be empty before reading from from_server? – trichoplax Jun 4 '14 at 20:24
@githubphagocyte The server will do it. Whenever your bot is run, that means the server is ready for you. I'll make that clear in the rules – undergroundmonorail Jun 4 '14 at 20:54
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
The problem with letting town work out you are a power role is that the Mafia have to be included in such discussions (or else you would know they are Mafia). So the Doctor will then have to decide whether to protect the power role, assuming the Mafia will go after them, or decide not to, hoping the Mafia will assume they are protected and not waste a kill. It's a "wine in front of me" situation. – trlkly Jul 13 '14 at 17:22
Hello, I just posted a sandbox question involving mafia. Do you still intend on making your mafia challenge eventually? If not then I will continue my mafia challenge. If you dont continue, I would appreciate your thoughts on my setup and how I can make a controller, etc. – Faraz Masroor Jun 9 '15 at 22:27
@FarazMasroor It's been so long since I did this that I've kind of lost my drive to make it happen, haha. If I do end up posting it, it probably won't be for a long while. I can take a look at yours. – undergroundmonorail Jun 12 '15 at 17:41
How do mafiosos die? – ASCIIThenANSI Sep 22 '15 at 17:00
@ASCIIThenANSI The village has to vote for them. – LegionMammal978 Sep 26 '15 at 19:58
I personally think my java controller is better because its more understandable and doesn't rely on messages so much as states of each individual player... – Faraz Masroor Dec 6 '15 at 20:17
But I still need to figure out how to make a controller and load all the answer bots into my program. – Faraz Masroor Dec 6 '15 at 20:17
According to Wikipedia, the optimal strategy for both townsfolk and the mafia is to choose people randomly... although that assumes everyone is playing perfectly en.wikipedia.org/wiki/Mafia_(party_game)#Game_theory – Jezzamon Feb 8 at 9:59
There should probably be two teams of Mafia (when the number of players reaches a certain limit), to make the game more interesting. – DerpfacePython May 22 at 1:41

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#
Very similar to Help Mr Jones to enjoy his bicycle round-trip. – dmckee Apr 27 '11 at 15:18
Fair enough. Is it worth making changes to it, or should I let it die, alone and unloved like the mangy mongrel it is? :-) – Gareth Apr 27 '11 at 15:32
Don't know. We don't really have a policy about near duplicates., and there are some differences. Maybe you could just put it aside for awhile, and come back to it when Mr Jones is a faded memory. – dmckee Apr 27 '11 at 15:42
@dmckee Ok. Will do. – Gareth Apr 27 '11 at 15:45
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
@MrLister No. Do you think there would be interest? I could copy it into the latest sandbox and give it a chance to be seen by new eyes. – Gareth Mar 15 '14 at 12:00
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
@MartinBüttner I posted this 3 and a half years ago, so in my mind it had been dead and buried. I suppose now it's got 6 upvotes it might be worth looking at again and bumping to see what interest there is. I'll have a look sometime this weekend. – Gareth Sep 4 '14 at 11:37
@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
1. It's not clear whether the intention of the "no backtracking" rule is that each station is part of a loop which includes the > tile, or whether we can e.g. create a little stationless loop which allows the train to turn around. 2. "in order for the track to be considered complete each piece of track must be adjacent to a previous piece of track" But the examples show that this isn't actually the case at stations. 3. It's not at all clear that the characters chosen for each track tile are relevant to anything. I note here particularly the |- in the first example. – Peter Taylor Jul 12 '15 at 17:03
4. You haven't actually specified that output is required, let alone in what format. – Peter Taylor Jul 12 '15 at 17:04
@PeterTaylor The question needs a lot of rewriting (this is actually the first question I ever tried to write here :-). The idea is that the answer would be a loop beginning and ending at the > character which must contain each of the of the M stations. I'm trying to decide whether to keep the different orientations of track or just use a single orientationless character like . or * - but I'm not sure if that would take some of the challenge away. I'm inclined to go for . but if there's a strong feeling that - / | \ is better then I need to clarify what combinations are allowable. – Gareth Jul 12 '15 at 21:10
@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?

rel="nofollow" isn't really part of Markdown processing. Passing HTML through directly needs clarification on how ill-formed HTML should be handled. Should "horizontal rules (<hr>)" say "horizontal rules (---, * * * , etc.)"? What about auto-links? Links and images with title attributes? Setext-style headers? Other unordered list bullets? Spaces before list bullets or numbers? Improperly nested em and strong (e.g. * This ** is * wrong **)? Paragraph tags? – Peter Taylor Aug 27 '13 at 11:20
As for test cases, check out michelf's test cases for MarkdownPHP. Your simplifications mean that a lot of them will fail, but providing "expected" output for them will go a long way to making this question worth attempting. – Peter Taylor Aug 27 '13 at 11:22
@PeterTaylor, I doubt a full markdown parser would get any responses, because of the number of rules. I'm trying to limit it as much as possible, while still including all of the basic challenges of it (indentation, links vs images, lists, etc.). I'll take a look at the PHP tests, thanks :-) And we're amusing valid markdown, and safe HTML. The user is escaping their <s, not leaving open tags, and not doing any invalid usage of syntax. – FakeRainBrigand Aug 27 '13 at 11:40
* This ** is * wrong ** should compile as <em>This</em> <em>is</em> wrong **. I'll clarify it in the question. – FakeRainBrigand Aug 27 '13 at 11:42
Yes, I've forked a .Net Markdown parser to make it compatible with MarkdownPHP and handling nesting interactions is one of the main sources of messiness, so you do seem to have removed a lot of the sources of problems. The improper nesting of em and strong is one of the points of contention: from memory, I think that MarkdownPHP would convert my example to <em> This <strong> is </strong></em><strong> wrong </strong>. – Peter Taylor Aug 27 '13 at 13:50
This is a good code-golf challenge, why haven't you posted it already? – Khaled.K Dec 30 '15 at 10:14
"-5 for a detailed explaination" should be removed. Bonuses in code-golf is something to avoid. – mbomb007 Mar 1 at 21:39
@mbomb007 that seems to be talking about a different type of bonus. I don't think it applies here. Also it's a few years too late to change now. – FakeRainBrigand Mar 2 at 1:26
@FakeRainBrigand Why? It hasn't been posted yet... – mbomb007 Mar 2 at 3:19
Oh oops, I didn't see that this was in sandbox. Anyway, because the bonus doesn't require changes to the code and everyone can easily claim it, it's not an issue. – FakeRainBrigand Mar 2 at 3:45
@FakeRainBrigand Who decides what detailed means? It's way too subjective. – Morgan Thrapp Mar 30 at 17:53
@Morgan'Venti'Thrappuccino the author of the answer. – FakeRainBrigand Mar 31 at 9:05
Note that in HTML5 closing </li> tags are optional. – gcampbell Jul 11 at 13:49

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 the next level. The full explanation of our work is available as an ongoing series on my blog since it is far too lengthy to fit here.

  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

The complete list of core components, complete with animations and links to VarLife implementations, is available on two of my blog pages: wires and gates.

  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. A-and-not-B gate (aka N-IMPLY gate)
  9. Wire crossing
  10. Some diagonal wiring
  11. Delay wire of 4:3, 22:11, and 33:11.
  12. Clocks of length 11 and 33.
  13. A serial adder.


  1. Opposing input, double-output logic gates.

  2. A 22-clock that actually fits in the box.

  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 only a cell or two.

  5. 2's complement converter

  6. Memory, including read/write and addressing

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.

@ChristianIrwan Unfortunately, your XOR design was actually too fast for use. In order to make the next levels of design easier, it is necessary for each of the basic gates (including bare wire) to have the same eaxct delay. I have modified the design to slow it down (animated above). Your diode, on the other hand, works fine. – PhiNotPi Jan 16 at 17:43
I guess OR will be difficult here. I can only think of (x AND y) XOR (x XOR y). – Christian Irwan Jan 16 at 22:23
@ChristianIrwan I think OR will be easy with an additional cell type. It's the wire crossing I am concerned about. – PhiNotPi Jan 16 at 22:32
Wait, I think there is only B1/S and B2/S – Christian Irwan Jan 16 at 22:44
@ChristianIrwan Metapixels can be set to any life-like rule. I just haven't used anything other than B1/S and B2/S yet. – PhiNotPi Jan 16 at 22:52
Then OR is easy, then I just have difficulty creating OR with only two cells. – Christian Irwan Jan 17 at 0:22
And for wire-crossing, three XOR combined like the Wireworld's wire-crossing works. – Christian Irwan Jan 17 at 0:25
OR, clock, and I'm trying to modify Christian's wire crossing so the signals actually cross instead of just being passed forward. – El'endia Starman Feb 16 at 4:30
GOT IT! Top one is Christian's, bottom one is mine. – El'endia Starman Feb 16 at 7:26
Even better, the wires go out at the same level that they come in. – El'endia Starman Feb 16 at 7:34
@El'endiaStarman is it possible to make it 7px x 7px? – Mars Ultor Feb 17 at 9:47
And not gate. Thank for El'endia Starman for the "applet" goo.gl/5s9Ffq – Christian Irwan Feb 19 at 10:54
Opposing input, two output and gate goo.gl/z10D9F – Christian Irwan Jun 4 at 17:21

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.

Is this intended as a short-term, deadlined competition, or will you be posting new results as submissions come in? I imagine for a contest like this, it may take a while to get something robust. Sounds fun, though! – Geobits Apr 9 '14 at 14:07
@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
gamerz.net/~fm/Main is [almost?] identical to Waving Hands, with an actually implemented human-vs-human version of the game. – Sparr Jul 25 '14 at 7:33
@Sparr, see also games.ravenblack.net/rules/0/index.html (which I'm sure used to say that it was Waving Hands with no disclaimers about being a variant) – Peter Taylor Jul 30 '14 at 9:07
Having seen a number of very complex KotH, I've changed my mind about their suitability and no longer plan to pursue this. – Peter Taylor Aug 17 '14 at 19:30
@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
Should a bot be eliminated from the rest of a tournament if it dies? – TheNumberOne Jan 13 '15 at 1:40
@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
@PeterTaylor I think it sounds interesting. There are some things in the rules that would make it really hard though. Example: a player hit by amnesia or confusion doesn't get to pick their gesture. How do they know if they were/weren't? Monsters make it complex also. Spells that cancel. Etc. – mbomb007 Feb 26 '15 at 15:21

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.

Defending player gets, "Planet X is under attack by Y enemy units. Will you Defend, Leave, or SplitYourForce." Obviously the defender doesn't have the option to wait (because you are under attack whether you like it or not), and it doesn't really make sense for defending forces to "join". – Rainbolt May 25 '14 at 4:20
If A takes over a base/flagship of B, what happens to the fighters of B? Are they given back to B, are they lost or are they given to A? – ProgramFOX Jun 3 '14 at 17:33
@ProgramFOX I've still got to edit in the most recent changes, but a flagship will be your "king", so if you lose it you die. Hence, if a flagship is killed, everything (units and bases) from B goes over to A (except his flagship, which will vanish - otherwise that would create a few situations I don't want). If you just take over a base, nothing happens to the units. More likely than not, B won't even have units on that body any more. – Martin Ender Jun 3 '14 at 17:38
@ProgramFOX edited the draft – Martin Ender Jun 3 '14 at 20:34
@githubphagocyte Yes to both. At the beginning of each round you can use all units present on the body, whether they arrived/spawned before the fight started or during the most recent round of fighting doesn't matter. – Martin Ender Jun 4 '14 at 20:04
"Should bots have full information about the game?" - Things you could hide: which fighters are where, if a player is building a base but it has not yet been completed. (For an element of surprise.) Things you can show: the amount of bases each player has, eventually with locations. (This allows players to determine who to attack and when.) Additionally, I think it might be a good idea if a player can place one or more fighters on an otherwise unoccupied planet and that the planet would not be his in that case, but the fighters can defend the planet to stop others from taking it over. – user2428118 Jun 13 '14 at 22:51
Perhaps you could require that at least one fighter is present at a planet, and that the flagship will bring in the "building material" for the base? Another idea: the flagship can transport troops, or be accompanied by fighters. "How should vulnerability during base-building be modelled?" - When a flagship is building a new base and it is attacked, if there are any of your units on the planet that are not involved in the fight, the base can continue to be built. – user2428118 Jun 13 '14 at 22:52
However, the building process cannot be completed as long as the planet is under attack; the final step, "raising the flag in the pole", cannot be executed if there are enemy troops attacking. If noone is building on the base (or waiting to raise the flag), the base will decay twice the rate it was constructed. If the flag ship leaves, the base will be destroyed. – user2428118 Jun 13 '14 at 22:53
@user2428118 I have to tell people the number of fighters on a body for them to make any informed decisions about attacking it or not. Any further identity of fighters is meaningless anyway. I could keep the exact distribution of fighters from them for planets they don't currently have units or bases on, though. In any case they need to know the number of bases and units each player controls to determine the leading player, which I think is very important information for certain strategies. The reason I'm considering full information is just to make the game it bit simpler. – Martin Ender Jun 14 '14 at 10:49
As for placing fighters on unoccupied planets, that is definitely intended to be possible. I'm not sure having to leave one fighter behind will accomplish anything. It's necessary in Risk because no territory can ever be unoccupied (as there are no rules for claiming such a territory), but here it seems quite pointless, because you can always claim planets without units or convert the bases on them. So I think it should be up to the players if they want to abandon their bases or not. – Martin Ender Jun 14 '14 at 10:54
The flagship introducing additional troops seems to complicate things even further, and I think the d8 bonus should be sufficient to want the flagship around in an important battle. Building the base while the fight continues (as long as the flagship doesn't take part) was my intention anyway. I like the idea of "raising the flag" being only possible when the base is not under attack any more, but I'll have to think about the implications. Having the base decay sounds like a valid option too, although I think decaying at the building rate or even slower is sufficient. – Martin Ender Jun 14 '14 at 10:58
The base being destroyed if the flagship leaves sounds a bit harsh but it would eliminate the problem of another flagship arriving and not being able to start a new base because there is a half-finished one already there. Thanks for your input, I'll give this some thought and work it into the specification! – Martin Ender Jun 14 '14 at 10:59
I'd like to point out that orbital motions of just two bodies is really hard to ensure conservation of orbit for more than a few dozen orbits, most particularly when using xyz-coords. Jumping up to 100 is going to be a pain to track that. It might be easier to move the planets in r-phi plane (since only 1 of those changes) and convert those to xy coords. – Kyle Kanos Jul 2 '14 at 2:31
@KyleKanos I'm fully aware of that, and that's exactly what I was going to do (that's what I meant by the second paragraph in "The Model"). But thanks for the concern. :) (Also there are only 8 bodies whose orbits will be "simulated" at all, because satellites are basically assumed to be a cloud around their planet.) – Martin Ender Jul 2 '14 at 7:52
If I understand correctly, there's no benefit to fighters hiding in interplanetary space, as their only function is to attack and defend planets. And the flagship already has a reason to stay on planets. So perhaps the refueling is unnecessary? – James_pic Jul 4 '14 at 13:38

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?
For what it's worth, I was completely confused the first time I read this. I thought Haystack and Needle were 'variables' and could be any string specified by the cop. This is actually pretty clear (especially after the examples were added), but maybe put "" around the code blocks? – FryAmTheEggman Nov 17 '14 at 18:17
I'm concerned that because the programs simply print fixed strings, this will be mostly a challenge of manipulating data rather than code, with answers like print(to_ASCII(142048593840593*3545403984543%20395405454)). – xnor Nov 18 '14 at 1:21
@xnor That's a good point, and you might be right. I'll think about how I can fix that. – Martin Ender Nov 18 '14 at 1:23
Allowing different languages for Haystack and Needle looks a nice idea to me. This might result in interesting cracks. – ProgramFOX Nov 30 '14 at 16:28
@ProgramFOX Now that you mention it will also make it incredibly hard to be sure that there's only one solution to your code. You'd need to know a lot of the terser languages to be sure one can't work around the intended solutions. So I think this isn't actually a very good idea after all... maybe I should rather allow people to choose an arbitrary (disclosed) string instead of Needle. – Martin Ender Nov 30 '14 at 16:31
@MartinBüttner That's true, I hadn't thought of that. Another idea might be that the Cop provides an answer in language A and tells that the Needle can be found in language B, where A and B can be equal or different. Then it's easier to check whether there is just one solution. – ProgramFOX Nov 30 '14 at 16:34
@ProgramFOX ah yes, actually my sandbox post already mentions that the Needle's language would have to be specified in this case. – Martin Ender Nov 30 '14 at 17:10
Why hasn't this been posted yet? Just my 2 cents, multiple languages would make it incredibly difficult for users with limited language experience. – J Atkin Feb 8 at 18:00
@JAtkin At the time I didn't have the leaderboard for CnRs yet (which I do now). In the meantime I wasn't sure any more how good an idea this would be since the search space is much smaller here than for other CnRs we've done (like unscramble the source code for example). But I guess that just means submissions have to be longer to make them safe. My main problem though is that this is as susceptible to hashing/cryptography/expmod as any other CnR and I haven't yet found a good way around that other than making a CnR where that isn't beneficial in the first place (e.g. TPLQ). – Martin Ender Feb 15 at 15:31

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
(b) Maybe you could post your script in addition. – TheNumberOne Jan 9 '15 at 13:36
@MartinBüttner Good points. I'll re-tag this as a code challenge. I'm trying to come up with a scoring system that prefers innovative hacks over long-winded but 100% correct solutions; if you can suggest any improvements then please do. I've just generated a set of sample images. In most of them, the two dice are non-overlapping, so it should be possible to score reasonably well without going overboard on the segmentation. – squeamish ossifrage Jan 9 '15 at 20:02
@TheBestOne The Python script doesn't do anything exciting. It just places two dice in the camera's field of view with randomly selected faces pointing up, then gives then a random z-axis rotation from 0 to 2π (repeating the process if the two bounding boxes intersect). I added a little devilry at the post-processing stage (pincushion distortion, glare FX and depth of field blurring) to better simulate the output of a real camera and foil solutions that expect images with perfect geometry, but none of this takes place in the Python script. – squeamish ossifrage Jan 9 '15 at 20:15
@squeamishossifrage I meant so that people can generate more test cases if 100 isn't enough. – TheNumberOne Jan 9 '15 at 22:10
You could post 1000 cases and then announce the subset of 100 that will be used for scoring. – trichoplax Jan 12 '15 at 23:33
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
@trichoplax Yes, they would be standard right-handed dice. I can't see the point in announcing a subset of images for testing, since this would only benefit latecomers – squeamish ossifrage Jan 13 '15 at 10:34

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.

That sounds very nice. Just to clarify, the area of effect of the area attack is a 5x5 square and the range attack can target any entity I see? Do the chasing monsters stop chasing me when I don't see them anymore? And a fixed arena size might be problematic, because it makes a vastly different game depending on how many participants there are. – Martin Ender Jun 15 '14 at 8:41
@m.buettner Yes, the effect of the area attack is a 5x5 square (but of course, you don't hit yourself). The sight ranges of all monsters are the same as yours. And there is only one of each bot participating in a game, so there won't really be a difference. – Alex Jun 15 '14 at 13:06
I don't know. If there are 5 participants, I might try to hunt for dragons and kill as many as possible. If there are 50 participants, it's unlikely that I'll meet any of them anyway, so I might be able to ignore them completely in my bot. I think the strategies might well differ depending on the monsters/bots ratio. – Martin Ender Jun 15 '14 at 13:23
Will the current number of surviving players be provided to the player each turn, or will the player just have to work with what is visible from the current position? – trichoplax Jun 18 '14 at 0:48
@githubphagocyte Yes, they will only know what is visible. – Alex Jun 18 '14 at 18:48
Can't you just min-max with -10 ranged, -10 area, -9 const, +1 melee, +40 defense just tank an enemy until it dies? Even +35 attack would still deal no damage against +40 defense, even with a roll of 5. If this is allowed and not patched, I preemptively claim this solution for myself. – archaephyrryx Nov 19 '14 at 0:13
@archaephyrryx So do you think disallowing stats above +20 would be a good idea in that case? – Alex Nov 23 '14 at 23:50
It's up to you whether to go that route or not, but in general consider pathological cases (edge cases) to see what those would lead to. If certain cases have consequences that you did not intend to be possible or are not acceptable to you, you may want to modify the conditions; if they are intended or permissible/acceptable, you may want to leave the conditions unmodified. Also, you should consider the question as to whether defense can be negative, and examine the consequences of having negative defense. – archaephyrryx Nov 25 '14 at 15:45
@Alex Are you still developing this? – Manu Mar 6 '15 at 10:22
@Manu Yes, but I haven't been able to work on it for a rather long while. – Alex Mar 6 '15 at 22:33
@Alex Cool, looking forward to the challenge:) – Manu Mar 7 '15 at 8:03
I'd enjoy this o.o – The_Basset_Hound Aug 2 '15 at 18:05

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
@PeterTaylor Based on this, should we assume that the votes will never result in a tie? – ASCIIThenANSI Aug 31 '15 at 18:05
@ASCIIThenANSI, huh? Pyrrha changed the question to handle three+ way ties. – Peter Taylor Aug 31 '15 at 18:51
@PeterTaylor Whoops. Didn't see that :\ – ASCIIThenANSI Aug 31 '15 at 18:53

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
Let us continue this discussion in chat. – trichoplax Jul 29 '14 at 9:14
"Shrimp always attack with scissors" How appropriate... – trichoplax Jul 29 '14 at 13:06
This challenge is old but good. I predict you'll get a lot of rep for this... – Agent CrazyPython Jun 23 at 17:18
@uoɥʇʎPʎzɐɹC provided it ever happens and isn't too complicated... – Martin Ender Jun 23 at 17:19
@MartinEnder Yeah, it's been a couple years now... – Agent CrazyPython Jun 23 at 17:43

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?
Some images failing and succeeding the test would be cool – Quill Jan 14 at 3:07
I know, working on test cases. Will do tomorrow. – Eᴀsᴛᴇʀʟʏ Iʀᴋ Jan 14 at 3:08
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
Could you shrink the images? It looks kinda freaky scrolling through the sandbox and seeing this... (p.s. you can use the img tag <img src=... width="300" />) – J Atkin Feb 12 at 0:38
@EᴀsᴛᴇʀʟʏIʀᴋ famous last words "will do tomorrow" lol – Rohan Jhunjhunwala Jul 13 at 20:45
@RohanJhunjhunwala ....oops. >_> I need code to generate the test cases, haven't written it. – Eᴀsᴛᴇʀʟʏ Iʀᴋ Jul 16 at 18:11
@EᴀsᴛᴇʀʟʏIʀᴋ haha – Rohan Jhunjhunwala Jul 16 at 18:26

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.
As discussed in chat, the "random partitions" doesn't require much modification of one existing answer on a partition question, although since most can't be modified so easily it's probably on the right side of the borderline. The chessboard is sure to generate controversy over the definition of "believable". The random expr seems very close to a number of existing questions which require enumeration of arithmetic expressions. The Unicode one is basically just a Kolmogorov compression of the table of assigned codepoints. – Peter Taylor Feb 3 '15 at 14:24
@Peter, the chessboard challenge will come with an unambiguous spec. For the arithmetic expressions, I'll make sure to check what we've already had. Unicode: hm yeah, it would definitely be one of the simpler challenges. – Martin Ender Feb 3 '15 at 14:32
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
1. Points on a sphere with uniform distribution: I'd be surprised if you weren't aware, but dA/dz for a sphere is constant: all slices of the same thickness have the same external surface area. So all you need is a uniform distribution of longitude and a uniform distribution of z height. 2. I like the chessboard idea. – Level River St Jun 14 '15 at 1:31
@steveverrill I wasn't aware that dA/dz is constant, but I was aware that this would be a rather simple instalment of the series. I've started to think that the chessboard challenge would be a pain to specify and to solve correctly. Currently, my favourites are the random polyomino and the Poisson disc sampling. – Martin Ender Jun 14 '15 at 10:26

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.

Interesting challenge but I fear it will share some of the problems describes here – Downgoat Aug 3 '15 at 6:12
@vihan The difference is that these different objects have quite different shapes, unlike cars which, to an untrained eye, all look the same – Beta Decay Aug 3 '15 at 9:27
I'm unsure how to feel about this proposal. On the one hand, I like the thought of an image recognition challenge. On the other, it feels like you just copied my proposal and changed the subject. – Geobits Aug 3 '15 at 14:30
@Geobits Mm I did think about that. How about, you post your challenge first (if you are going to do that), then, if it doesn't work out, I'll try this at a later date. If yours does work out, then I'll delete this – Beta Decay Aug 3 '15 at 14:38
Well, I think this one would probably work better in the long run, it was just odd seeing so shortly afterward. I'm not going to be upset if you post it or anything. Critique-wise, you can probably lose the line "All images will be the objects in flight against a white background.", since the next sentence invalidates it ;) – Geobits Aug 3 '15 at 14:42
@Geobits Well I'll give this some time before posting it, so you can do whatever you want in the meantime :) – Beta Decay Aug 3 '15 at 14:43
I think it's not unlikely someone will get all the images right. What's the tiebreak then? How about code golf? – xnor Aug 3 '15 at 20:19
@xnor Yeah I guess – Beta Decay Aug 3 '15 at 20:20
You may want to specify what kinds of libraries/services can be used. – Reto Koradi Aug 3 '15 at 20:43
@RetoKoradi Well every library can be used. I don't think any specific image recognition libraries exist – Beta Decay Aug 3 '15 at 20:48
There are lots of image recognition libraries, as well as cloud services. See for example here: quora.com/…. – Reto Koradi Aug 3 '15 at 20:54
@RetoKoradi I see. I'll limit it to offline services – Beta Decay Aug 3 '15 at 20:56
It really depends on what your goal for the challenge is. If the goal is to find the best way of applying a library to this specific problem, that should work. If you want people to actually write image recognition code, you'll probably have to exclude libraries. But then you have the languages where a lot of functionality is built-in, where it would be in libraries for other languages. – Reto Koradi Aug 3 '15 at 21:02
Just to give you an idea of what might come into play, depending on how you specify the problem: reference.wolfram.com/language/ref/ImageIdentify.html, reference.wolfram.com/language/ref/ImageInstanceQ.html. – Reto Koradi Aug 3 '15 at 21:11
Do we get a bonus if we correctly identify the picture as being Superman? – Neil Jan 31 at 10:20

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])
@MartinBüttner Thanks for the feedback!: 1. Made the format very flexible for a CSV. 2. Yes, the radius will evolve non-linearly and vary at runtime based on variables outside the program's reach. 3. There is no strength to a push, will clarify. It simply changes the target's speed as if it issued a move. 4. Yes, speeds will be normalized so they never exceed 1 in any direction (moving diagonally will not be faster). I just updated the answer I hope it explains these points. – Kroltan Jul 26 '14 at 12:04
@MartinBüttner Good point, I couldn't find a appropriate term for this (capping the net speed, not their axial components), would you direct me at a better word? (English is my second language) Players can indeed move at speeds slower than 1. Should I say "your net speed will be capped at 1"? – Kroltan Jul 26 '14 at 12:47
@MartinBüttner Good point. Will update. – Kroltan Jul 26 '14 at 13:01
I'm still not entirely sure about the push. What will be the resulting speed? 1? The previous speed, just rotated? In that case, I'd be immune to pushes be standing still. – Martin Ender Jul 26 '14 at 13:03
@MartinBüttner Good catch on standing still. I guess the push speed would be the average of yours and your target's, in the direction away from you. The idea of not moving at full speed is exactly to minimize push efficiency, but with the average I can't imagine a exploit. – Kroltan Jul 26 '14 at 13:25
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
@MartinBüttner That would be interesting... And less of a warped reality. xD Though I do not intend do make this a completely physics-based challenge, so I guess that the direction will just set to "away from eachother". Plus, these quirks can make a really unexpected playfield. – Kroltan Jul 26 '14 at 13:51
Yes, I'd leave it at that. It would be a lot more complicated if you made it really physics based, since the velocities wouldn't change so abruptly. So you could just make a push always along the direction connecting the two players, but apply the push to both of them. – Martin Ender Jul 26 '14 at 13:58
Reworded the question (answer?) to a more readable manner. – Kroltan Jul 28 '14 at 1:59
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
@Zaq Totally didn't think about that. If any player is pushed by two people at once, he is stopped. About the speed, the execution will work at 1 speed per turn. Will edit this info into this answer now. – Kroltan Jul 29 '14 at 2:54
@Kroltan: Do you want to make it conform better to reality by taking the resultant direction (and speed) when a target is pushed by two people, instead of stopping it? It's weird to see that a target being pushed by two people from behind get stopped. But this is your universe, so this is up to you. =) – justhalf Jul 29 '14 at 6:46
@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
@justhalf I know ;D – Kroltan Aug 18 '14 at 20:32

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
@MartinBüttner if it was a code-challenge, would I do that with N gradiations of noise (sets of test files, or maybe just a big one) and the "score" would be what's the worst you can handle? Maybe a single long file (hundreds of tones) with increasing amounts of noise, score is how many are correctly decoded? – Nick T Oct 18 '14 at 0:17
Either that, or you include multiple difficulties, provide a hundred (say) test files with random parameters, and the score is the number of correctly recognised files. – Martin Ender Oct 18 '14 at 0:20
@MartinBüttner fleshed it in a bit more as a challenge, see anything awful? – Nick T Oct 18 '14 at 8:53

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)
Very nice proposal. One question, how will you determine a bot's average probability of winning a round ? – Casey May 4 '11 at 13:43
number of hands won over number of hands played. This bot played N games AGAINST THE SAME OPPONENTS and won M of them. FOR THAT SET, p(winning) = (N/M) – arrdem May 4 '11 at 15:41
As proposed the game is equivalent to a full shuffle between every deal, and prevents card counting strategies from being very valuable. This is fine, but suggests a variation, where shoes are played to some fraction of exhaustion. For that version persistent state would be a must. – dmckee May 4 '11 at 16:29
Alternate metric: Allow the bot to engage in variable betting, and measure the biggest winner. Input format <your card> <visible cards> <current stake> <your chips>. Output: [<bet>|<[Hit|Stand|sPlit|Doubledown]>] or something. Here betting is done if the bot runs with no current hand. – dmckee May 4 '11 at 16:32
good suggestion @dmckee, I like the betting format. – Casey May 4 '11 at 17:44
Question. I started implementing this today, and I realized that I could save a bunch of effort if I made the dealer yet another bot and just plugged him/it in via my existing bot framework. This begs the question, why have a dealer? Just as easily, I could run 1v1 bot vs. bot games in the same kind of face-offs as in TPD. Thoughts? The only real impact on the game this has is that the entry bots are less likely to win because of opponent busts. – arrdem May 8 '11 at 3:23
@rmckenzie: I wouldn't want to discourage you from implementing the dealer as a bot, but the rules of blackjack are usually asymmetric: the house is constrained to behave in particular ways, and players loose when they bust even if the house subsequently busts as well, etc. – dmckee May 8 '11 at 15:46
@dmckee - good point that. besides, 1v1 makes card-counting much less useful than in 6vHouse. – arrdem May 8 '11 at 16:48
A dealer often has additional rules (must hit on 16). ... I've got a card-counting program that I used against the Kindle Blackjack (all manual, unfortunately: you have to type all the cards played each hand). – luser droog Mar 27 '13 at 0:46

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?

Can we take it that there will always be a tempo change before the first line of music? It's hard to see how you could judge sound quality in an objective way. I like the question though. – Gareth Dec 24 '13 at 22:03
Yes, there will be a tempo change before the first line of music. Also, I agree that sound quality probably shouldn't be the focus, I have the real software for that. – PhiNotPi Dec 25 '13 at 0:37
What about sharps / flats? Could you clarify the sustain req with respect to the envelope you expect for e.g. note,sus,sus,sus? How much flexibility when note length not a factor of sample rate? (E.g. 57bpm @ 16kHz: if there are 57 lines must output be exactly 60*16000 samples or can each line be rounded to 16842 samples?) If raw output (i.e. wav without RIFF header) is not allowed, best to be explicit. – Peter Taylor Dec 28 '13 at 10:15
"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

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
@Katenkyo I like your reasoning about the 16 colours. The 10k turns is not final yet - I'll see how long a game is realistic when I test the controller, but I'll use your idea of basing the number of colours on the cost of a clock when I work out the final numbers. – trichoplax Jun 17 '15 at 13:18
@Katenkyo I share your concern about the food distribution at the start of the game before there are any workers. I originally said the queen would start on an empty cell, then I changed it to an empty 3 by 3 neighbourhood. I'm now wondering if I should make it a larger neighbourhood that is guaranteed to be empty. – trichoplax Jun 17 '15 at 13:21
lowering a little bit the number of turns could be nice, if you take in account the fact that there's "only" 20k cells. But be care while lowering, because I think less than 12 colors (still 20k possibilities for 4cells) would be harmful, as some strategies will need a lot of them. – Katenkyo Jun 17 '15 at 13:25
regarding the food distribution, I don't know how to "fix" it, a starting pattern forced around the queen? As we don't know which direction we face, we can't do an "optimal" trajectory – Katenkyo Jun 17 '15 at 13:27
@Katenkyo I think I will have at least 16 colours - if I change that it will probably be an increase. Note that there are 2,000,000 cells and 2000 pieces of food in the current arena size. – trichoplax Jun 17 '15 at 13:28
I don't know how I computed 20k instead of 2M, must be really tired. 16 colours looks good, as we will have to use them to see our random too... This constraint will be horrible to overcome x) – Katenkyo Jun 17 '15 at 13:33
@Katenkyo I'm glad to see someone seeing the horrible constraint as a challenge rather than something to change :) – trichoplax Jun 17 '15 at 13:34
@Katenkyo If by "optimal" trajectory you mean choosing to search in a horizontal line rather than a vertical line, to maximise the chance of finding food before returning to the starting point, I guess moving in a diagonal line would be one way of getting around not knowing which way is vertical. – trichoplax Jun 17 '15 at 13:36
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
by optimal, I mean "by moving twice 0, and one 1 I will be in the area with the most food around the starting point because I know the pattern". I was speaking in case of setting the spread pattern around the starting point of queens (in a 10x10 radius?). Which could counteract the randomness of distribution by a little – Katenkyo Jun 17 '15 at 13:41
This looks really interesting. Your example bots look quite strong so my only concern is that if you include them in the competition then they might beat the other bots :) – The E Jun 17 '15 at 20:07
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'm assuming that the enemies and friends parameters are arrays, if so you probably need to specify that explicitly in the challenge – The E Jun 17 '15 at 20:14
@TheE the example bots are meant to be simple thought provokers, which should be easy to beat. The only one which uses workers for searching is Worker's Spiral, which should be beatable. I could make the workers follow their spiral in reverse to get back to the queen rather than cutting across, which would make them much less competitive. I'll see how they perform once the controller is ready for testing. – trichoplax Jun 18 '15 at 3:43

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 is a little interesting too me that you basically require the submitter to turn in a incompletely golfed submission. Or is this not intended to be a [code-golf]? – dmckee Aug 17 '11 at 14:24
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
Alternately, I could count the length of the golfed result instead of the original program, though I'm not sure it will make much difference in determining the winner. – migimaru Aug 17 '11 at 14:38
I think I need to add a rule that prevents a simple trim() operation to eliminate whitespace at the end of a line. Would it be sufficient to say "all trim()-like operations are banned"? – migimaru Aug 18 '11 at 15:02
why ban trim()? You force competitors to manually implement an otherwise built-in function. Besides, would "r_( )+$__" or an equivalent trivial trailing space replacement be counted? – arrdem Aug 18 '11 at 15:33
Hmm, I'm not sure what to do about it now. I don't like having to ban a function, but trim() allows for single statement solutions where you just read in the first line and trim off 5 trailing spaces. I was hoping for a challenge that would be more interesting. – migimaru Aug 18 '11 at 15:37
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
@Peter Taylor I was already planning on banning comments. I don't think replacing variable names is non-trivial, though it might be in some languages. Whitespace is a big problem, though. In the end, I agree that this question doesn't seem like it'll work out. – migimaru Aug 29 '11 at 14:42
I think you need to add a source restriction, so that the user cannot create a gigantic program with tons of spaces then just remove a bunch. Make it so the program can only have 10 of each character or something. And maybe make the score the difference of the starting and ending programs. Then, I'd say that the output of the 2nd program doesn't have to be the same as itself, it can be even shorter! Then just use the eventual output of the nth program in comparison to the original. – mbomb007 Jun 4 '15 at 22:03
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
What about popularity-contest and drop conditions about other programs. The program should take it's own code and golf it in such way, that the resulting syntax tree differs. On any input both programs should behave in the same way. – Qwertiy Apr 22 at 17:41

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.

Is ctrl-C a "simple means to stop the program"? What's the minimum resolution required? (I'm assuming you won't consider a solution which only captures movement in a 2x2 square to be acceptable). What's the minimum acceptable range of frequency? – Peter Taylor Apr 2 '14 at 20:16
@PeterTaylor Thanks for reviewing. I've edited to address your comments. – Digital Trauma Apr 2 '14 at 20:33
Thanks. 1000x1000 is a bit harsh on people who want to golf on their netbooks. – Peter Taylor Apr 2 '14 at 20:46
@PeterTaylor Good point. I'll drop that to 500x500. – Digital Trauma Apr 2 '14 at 20:48

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.

Sounds like a good idea in general. In fact, "challenge using genetic algorithms" is on my PPCG ideas list. :D ... What's not clear to me is if you will prescribe the design of the genome in the final challenge, or whether designing the genome is something participants should do as they see fit. And I think in any case you should define the genome of the cells before explaining how the simulation is carried out. – Martin Ender May 28 '14 at 16:24
@m.buettner the reason why I posted this in the sandbox is to get suggestions for it. i still haven't decided whether it will be a code-golf with bonuses or a popularity-contest – professorfish May 29 '14 at 8:47
Do the cells have input? That is, is their behaviour affected by awareness of their remaining lifetime counter (or that of their neighbours), the contents of surrounding grid squares, their location on the grid, the location of nearby or distant food sources? Do they have senses or just follow their genome regardless of their surroundings? – trichoplax Jun 4 '14 at 20:02
@githubphagocyte They can have senses. The point of my posting this here is to get ideas for features, either to make a strict specification or just for ideas. I think I'll be making this a popularity-contest The grid shouldn't wrap at the edges, although in my JavaScript version it sort-of does (the squares are numbered left to right, top to bottom, so you can cross the left edge and end up 1 square above and on the other side from your original position) – professorfish Jun 5 '14 at 7:22
Yes I understood that you are looking for ideas - so I've just thrown those I can think of to see which ones you like. I like the idea of a popularity contest so we can see lots of different approaches. How flexible would you like it to be? You have "squares" in your title - are you attached to this? Would you welcome hexagonal grids too? – trichoplax Jun 5 '14 at 12:17
@githubphagocyte If someone can do it, great! Cubes as well, maybe... (+10000 for four dimensions ;) you could display cross-sections of it) What would a good name be then? Evolution of ...? – professorfish Jun 5 '14 at 13:18
I guess the name would be the last thing to settle on, once you know what the possibilities will be. It might be named something to do with cells if you know the cells will always be individual, or something more expansive if creatures can evolve that are made up of more than one cell (like snakes or jellyfish or plants...). Once you decide where to draw the lines the name should follow... – trichoplax Jun 5 '14 at 17:20
@githubphagocyte if someone could implement simple multi-celled creatures, that would be amazng – professorfish Jun 5 '14 at 17:45
Another characteristic you could add is immunity to being eaten. Maybe a cell can only eat those with a higher eating characteristic or those with a life higher than X? Also, I think that the food is a good idea, but how would the simulation handle finite food? – kitcar2000 Jun 5 '14 at 20:52
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
How important is the grid to you? Would you want to exclude grid free artificial life environments where movement is not restricted to integer steps? For example, like in the Hunger Gaming question (it has a video). – trichoplax Jun 7 '14 at 1:41
It's possible to get interesting behaviour emerging without even having senses, with a very simple simulation. For example: this flash version of simulated evolution – trichoplax Jun 10 '14 at 17:12
@professorfish "Evolution of Regular Geometries"? – Patrick Roberts Jun 27 at 3:41

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
@ProgramFOX Well, I can't guarantee that I will be here forever, and I limit the time of computation to 2s on machine. But you're right, that's not much a burden, so I changed it. Thanks. – yo' Jun 9 '14 at 14:22
@tohecz: In a previous contest I wrote a Python wrapper for submissions. This is reasonably cross-platform (using subprocess for communication), so I think it could work for your challenge. I could volunteer to write such a thing if your problem was posted. – nneonneo Jun 28 '14 at 23:44
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
Does the second player know how many cards the first one changed or are the changes simultaneous? – randomra Jul 11 '15 at 10:03
@randomra I think simultaneous is best here. Otherwise I'll have to alternate turns as P1/P2 due to the advantage. – Geobits Jul 11 '15 at 14:49

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
@Peter Taylor. Thank you for your comment. I do it for the x in lambda functions. For the second remark, it is also true, but since it is a popularity contest and since creativity is encouraged, is it absolutely necessary to be too precise regarding how the data has to be stored? – ברוכאל Mar 26 '14 at 4:51
Popularity contests should be more tightly specified than contests with objective criteria, not less, because otherwise they're just an invitation to throw crap at the wall and see what sticks. – Peter Taylor Mar 26 '14 at 14:34
@Peter Taylor. OK. What do you think of the current version? – ברוכאל Mar 26 '14 at 14:50
The more I think about this question, the less suited I think it is for this site. – Peter Taylor Mar 26 '14 at 19:48
@Peter Taylor. OK. I will try to find another one later. Regards. – ברוכאל Mar 26 '14 at 19:51

Anarchist chess

Initial position

Just like chess, except that instead of two opposing armies, it's a free-for-all among the pawns.

The two players alternate moves. The allowed moves are to move a pawn one square forward (if the square ahead is unoccupied); if the pawn is on its initial position, to move it two squares forward (if the two squares ahead are unoccupied), or to capture a pawn that is one square ahead diagonally. Pawns do not promote upon reaching the last row and there is no en passant. The player who is left without a legal move loses.

This is an example of an impartial game.

The space of valid positions seems rather small. Is this not a solved game? – Martin Ender Feb 5 at 22:30
@MartinBüttner You're right, it's definitely too small as is. If I post it I'll need to make the board larger than 8x8. I don't know if the game has been previously suggested. – feersum Feb 5 at 22:59
Oh you just made it up? I thought it was a thing. In that case, you probably don't need to be worried about it being solved but maybe about participants solving it ;) – Martin Ender Feb 5 at 23:00
So it's only one set of pawns and they can capture each other? – Peter Taylor Feb 6 at 13:53
@PeterTaylor Yes. – feersum Feb 6 at 14:49
OK, so this is also a combinatoric game, because captures can split it into independent subgames. Some subgames, at least, are easy to analyse. Maybe worth asking on math.se whether anyone can find a full analysis. – Peter Taylor Feb 6 at 15:21

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.

So the player who's turn it is controls all of the bots, which all execute the same program? How do the bots interleave their actions and the actions they receive via zapping? – Peter Taylor Mar 30 at 12:06
@PeterTaylor No, the player whose turn it is only controls their singular bot, which executes its program during the same turn. Zapping causes an action to be taken immediately by the zapped robot. More precisely, zapping doesn't change the order of actions, it simply changes which robot is performing the action. – PhiNotPi Mar 30 at 12:18
Here's for hoping for super long ZAP ZAP chains – Nathan Merrill Mar 30 at 14:27
Also, I'd argue for multiple bot control (maybe 5 or so)? It'd allow for complex shipping operations – Nathan Merrill Mar 30 at 14:30
@NathanMerrill There's not really anywhere to ship stuff to at the moment though. I am undecided about whether I should just have the bots collect crystals (no need to return to base) or require them to return to base (which can make the game more complicated). – PhiNotPi Mar 30 at 15:15
Ah, I guess I assumed bots wanted to return crystals to base. If there are fewer crystals than bots, then this would become a "steal the flag" sort of game? – Nathan Merrill Mar 30 at 15:19
C: clone. Creates a bot on the square in front of you that will keep executing your string of commands until the next H (halt) – Cyoce Mar 31 at 3:32

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
@dmckee: Note that the »best« paths change dynamically and might call for waiting or hiding at times even. At the moment I neither have a clearer specification nor a solution :-). Also no need to rule out GolfScript; I wouldn't make this a golf. – Joey May 13 '11 at 6:56
it's still path-finding. It's just that conceptually it's a 3D graph (two spatial and one temporal dimension), so the interesting bit is coming up with a strategy to keep the graph size tractable. – Peter Taylor May 13 '11 at 23:04
Did I mention that I'm very bad with graphs? ;-P – Joey May 13 '11 at 23:22

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.
The flashlight option could increase the vision radius of its bearer, but also make the bearer more visible to others. – trichoplax Aug 11 '14 at 13:59
This sounds interesting. – Soham Chowdhury Sep 14 '14 at 17:55
You had me at "lasers." – Alex A. Oct 11 '15 at 19:11

Transport Tycoon [control program WIP]

The specification is now complete; the control program will now be written

Chatroom for this challenge

Your task is to create an AI which builds a profitable transport network to carry passengers. In each game, the first entry to have $262,144 or more in cash wins!

Every entry must have a name and version numbering for each time it is altered. You may submit up to 8 entries, but they must not collaborate.


Each round has four players. Each player has a number from 1 to 4.

A simple map will be randomly generated by the control program for each game. This map will be stored in a file map.txt two directories above your program (i.e. ../../map.txt), and updated each game tick. Each player's bank balance (as a number without the $ symbol) will be in ../../account_<PLAYERNUMBER>.txt. Vehicle data will be in ../../vehicles_<PLAYERNUMBER>.txt. You may view other player's vehicle and account files.

Your program will be invoked once, at the start of the game. When your program has finished initializing, it must output READY. If it takes more than 60 seconds to initialize, it will be terminated and disqualified from that game. It may keep files between rounds (for example, to predict an opponent's strategy after watching them for a few games). Other players may not view these files. The tournament will be re-run and the leaderboard updated every 2 days. Your program may not keep files between tournaments.

The control program will put the text WAITING-player_number (e.g. WAITING-4) and a newline to your program's standard input when each game tick begins. You will submit actions on standard output, separated by new lines, terminated by END. Actions that are invalid for whatever reason will be completely ignored. If your program takes longer than 1 second to output END, it will receive TIMEOUT on standard input and no action will be executed for this turn.

If no winner has been found after 30 minutes, the player with the most money wins.

Map format

The map will be a two-dimensional ASCII grid where the top is north, the bottom is south, the left is west and the right is east. Example:


# represents a road. / represents empty land. * is for difficult terrain (e.g. hills, swamps, whatever) - more on that later. @ represents a house. ~ is a body of water. + is a completed bridge over water. | is a partially constructed bridge. The numbers 1 to 4 represent stations belonging to players (e.g.: if you are player 4, your stations will be marked as 4). 5 to 8 represent 'inactive' stations belonging to players 1 to 4 respectively.

The line endings in the file will be Windows-style CRLF.

The top left corner is (0,0). X is horizontal and Y is vertical.


Each tick, a player can perform up to 4 construction actions. These are:

  • replace a / with a # (build a road)
  • replace a * with a / (prepare terrain)
  • replace a # with an inactive station (build a station)
  • replace a ~ with a | (start a bridge)
  • replace a | with a + (finish a bridge)
  • replace one of your stations with a # (demolish a station)

You may not perform more than one action on a tile in one turn (you cannot go from ~ to | and to + in a single turn).

You cannot demolish roads, bridges, water, houses or other players' stations.

Each action costs $512, and is sent to the control program on standard output in the following format (B is for Build):


For example, this will build a road at (8,4):


Invalid commands will be ignored.


Each player can own an unlimited number of vehicles. The basic bus has the following properties:

  • carries 32 passengers
  • travels 8 tiles per turn
  • consumes $8 per tile in running costs

Each vehicle can have up to 4 upgrades out of the following (but no more than 2 of each type):

  • +16 capacity (denoted by C)
  • +4 tiles/tick speed (S)
  • -$2 running costs (R)

At most one vehicle can be bought by each player per turn. The basic bus costs $4096 and each upgrade costs $1024; the maximum possible cost is therefore $8192 (all 4 upgrades). A bus can be sold at any time for half of its purchase price (including upgrades; a bus with 4 upgrades can be bought for $8192 and sold for $4096). At most one vehicle can be sold each turn.

The command for purchasing a vehicle is (P is for Purchase):


For example, this will buy a bus with no upgrades, assign it the ID 5, and place it at (7,7):


The command for selling a vehicle is simply (V is for Vend)


Vehicles are stored in vehicles_N.txt in the following format, separated by newlines:


For example, this bus has ID 4, is at (5,5), contains 15 passengers, has two speed upgrades and one running cost upgrade, and last stopped at (3,4). If the bus has never run A before, use the coordinates where it was created for the "last station" coordinates. Update the coordinates every time A is run for that bus.


Vehicles can travel on roads (#), bridges (+) and station tiles (12345678). In the above example, it is possible to drive from the top left corner to the bottom right corner. However, the two road sections in the map below aren't connected, because they are only diagonally touching. Building a road on one of the * would solve this.


Vehicles can only stop to pick up and drop off passengers at stations belonging to their owner - player 3's bus can only stop at a 3 or a 7, but not at any of 124568#+.

Your AI has complete control over the movement of its buses. It will submit directions as commands. For example, the following command set will move bus 8 in a circle, then two spaces south, then make it offload 8 passengers, then make it wait for passengers (N, E, S and W are north, east, south and west; R is for Remove; A is for Acquire):


NB: Waiting at a station with A counts towards the limit of tiles that the bus can travel each turn, although it is not moving. While waiting, double running costs are charged. A bus may wait for multiple turns. If a bus moves fewer tiles than it is able to (e.g. can move 8 tiles per turn but chooses to move 5 times), halved running costs are charged for the unused turns.


Each time an R command is submitted for a bus that is at a station, the bus loses 8 of its passengers. The diagonal distance (using Pythagoras' theorem) between its current station and the previous one is calculated and rounded down (floored). Each passenger offloaded gives this amount of profits (e.g. if the previous station is 1.4 tiles away, each passenger gives $1; if it is 5.9 tiles away, each passenger gives $5).

Each time an A command is submitted for a bus that is at a station, the bus gains passengers. Each house in range of your station provides 1/number_of_active_stations_in_range_of_house passengers.

If there are three stops, A, B and C, and the bus has a route from A to B and then to C, but only picks up passengers at A, then passengers offloaded at B will pay the price for A to B, and passengers offloaded at C will pay for A to C. However, if any passengers are loaded at B, then all of the passengers offloaded at C, even if some of them boarded at A, will pay the fare for B to C.

In the map below, the tiles marked with @ and # are in range (4 tiles or less away), but not the tiles marked with /; the bus at 1 will gain 32 passengers because there are 32 houses in range and no other stations.



You will be charged $64 per turn for each station, active or not, that you own.

Each turn, active stations have a 1 in 8 chance of becoming inactive. This is reverted when a bus runs A at the station.

You will start with $32768.

You may not have a negative quantity of money.

When someone wins, all competing programs will receive GAMEEND on standard input. They may no longer submit commands after this happens, but they may read and write from files (to prepare for a subsequent game, for example). After 60 seconds, all competing programs will be killed.

The map will be 256*256 tiles.


  • Write control program
  • Write map generator
  • Plan tournament format
check out dinopoloclub.com/minimetro for a minimalistic transport network game that might be amenable to computer solution – Sparr Aug 11 '14 at 13:39
If a bus makes a journey from station X to station Y to station Z, and not all of the passengers picked up at X get off at Y, how much will they pay when they get off at Z? Will everyone who gets off at Z be charged as if they had travelled from Y? In order to charge the higher amount for a journey from X to Z, would the bus need to avoid stopping at Y? – trichoplax Aug 31 '14 at 21:25
@githubphagocyte Yes, it would need to avoid stopping at Y. I don't think there's a way to fix this without overcomplicating things. Alternatively the R command could be changed to drop off all the passengers; this would eliminate the option to only drop off some passengers. (This is what happens in OpenTTD - vehicles always drop off all their passengers at stations AFAIK) – professorfish Sep 1 '14 at 8:58
@githubphagocyte which is better? just leaving it as it is or changing R? – professorfish Sep 1 '14 at 9:04
I don't have a preference I just wanted to make sure the behaviour is unambiguous. You can model it in as much or as little detail as you like as long as there are no loopholes or unclear behaviour. – trichoplax Sep 1 '14 at 13:30
In real life the number of people who get on a bus depends on its announced destination rather than just its pick up point, but I don't think it's necessary to model that in order to have an interesting competition. There's already the potential for complex interaction between companies that can't prevent other companies from using roads they didn't pay for. – trichoplax Sep 1 '14 at 13:35
@githubphagocyte I've added a disambiguation: "If there are three stops, A, B and C, and the bus has a route from A to B and then to C, but only picks up passengers at A, then passengers offloaded at B will pay the price for A to B, and passengers offloaded at C will pay for A to C. However, if any passengers are loaded at B, then all of the passengers offloaded at C, even if some of them boarded at A, will pay the fare for B to C." – professorfish Sep 1 '14 at 13:45
It's worth trying to think of winning strategies to see if that highlights any loopholes. The best return seems to be from journeys along a straight line a multiple of 8 squares long (or 12 or 16 squares with an upgraded bus). If there are a number of squares nearby where a rival could benefit from building a station, do you benefit from building stations there just to block? How do the costs compare under your current parameters? – trichoplax Sep 1 '14 at 13:55
@githubphagocyte I could partially prevent blocking by not allowing a player to build two of their own stations next to each other (but allow them to build next to a competitor). Would that work? – professorfish Sep 1 '14 at 17:09
I suppose it depends whether the cost of building a number of unused stations just to block one rival station is worth it. As long as building a new station isn't too cheap it should sort itself out. I wasn't suggesting preventing people from blocking, just making sure it is sufficiently expensive that it doesn't happen too easily. – trichoplax Sep 1 '14 at 17:35
@githubphagocyte Currently the station costs $512 to build and $64 per turn (inc opponent's turns) to maintain. how much higher should the costs be? $1024 and $64 maybe? – professorfish Sep 1 '14 at 17:40
The current figures may be fine. Just something to bear in mind during testing with example contestants. – trichoplax Sep 1 '14 at 22:40
Is any controller up for this? – Soham Chowdhury Sep 16 '14 at 9:28
@SohamChowdhury I'm working on it.... one day I'll finish it – professorfish Sep 16 '14 at 10:31
@SohamChowdhury github.com/professorfish/ttkoth – professorfish Sep 16 '14 at 10:33

You must log in to answer this question.

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