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

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

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

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

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

-

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

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

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

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

## Game rules

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

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

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

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

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

## Protocol

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

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


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

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


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

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

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

## Competition rules

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

## Scoring

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

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

# Let's Play Mafia! king-of-the-hill

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:

start
controller/
tmp/
players/               # You are here!
some_bot/          # Let's pretend you're some_bot.
to_server
from_server
players
run            # This is what you give me
mafia-game-bot/
skynet/


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:

real_bot.py

#!bin/python2

# code goes here


run

#!/bin/bash

./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:

#!/bin/bash

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

Day

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:


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.

Night

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

MAFIA:

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

COP:

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.

DOCTOR:

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?)

Scoring

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.

run

#!/bin/bash

./randy.py < from_server > to_server


randy.py

#!/bin/python2

import random

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

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


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

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

## Ruby on Rails

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

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

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

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

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

Winner is the shortest code.

Key

# - 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 #
#\   ^ | #
#~X~~~~X~#
# M     \#
# |-----M#
##########

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

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

## Waving Hands bot

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

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

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

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

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

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

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

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

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

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

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

## Basic Markdown Parser

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

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

- unordered list:

- foo
- bar
- baz


⇓                        ⇓                        ⇓

<ul>
<li>foo</li>
<li>bar</li>
<li>baz</li>
</ul>


- ordered list:

1. foo
47. bar
22. baz


⇓                        ⇓                        ⇓

<ol>
<li>foo</li>
<li>bar</li>
<li>baz</li>
</ol>


- code block:

    foo
bar
baz


⇓                        ⇓                        ⇓

<pre><code>foo
bar
baz
</code></pre>


- blockquote:

> foo
> bar
> baz


⇓                        ⇓                        ⇓

<blockquote>foo bar baz</blockquote>


### Notes

• <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)

### Scoring

It's code golf; least bytes wins.

-5 for a detailed explaination

### Meta

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

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

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

-

# Conquer the Solar System

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

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

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

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

## The Setting

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

## The Model

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

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

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

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

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

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

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

## Gameplay

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

## Implementation

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.

-

# King of the Hill- Simple RPG

[king-of-the-hill]

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.

## Mechanics

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.

## Combat

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.

## Monsters

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.

## Attributes

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

# Implementation

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


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

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

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

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

# Winning Condition

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

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

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

## Examples

Here are a couple of simple examples in different languages:

Ruby

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

Python 2

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


## Sandbox Notes

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

# Count the pips in a pair of dice

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

## The challenge:

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

## Scoring:

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.

## Notes:

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

# For discussion:

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

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

## Summary

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?).

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?

## Genetics

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

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

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

Characteristics which could be included are:

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

## The Simulation

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

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

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

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

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
NN   NN
NNNNN
NNN


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

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

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

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

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

## The Fights

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

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

## Sandbox notes

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

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

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

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

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

# Analyze overhanded shuffles - posted

-
Overhanded. It's happening. –  Alex A. Jul 11 at 18:21
And in the followup challenge, you play as Tim, trying to sneak your underhanded overhanded shuffle code past everyone. –  feersum Jul 13 at 9:12
Maybe we could pretend to be doing a card trick, but actually shuffle the cards, thus performing an underhanded underhanded overhand shuffle. –  feersum Jul 13 at 15:32

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

# AS OF THIS TIME, THERE IS NO CODE FOR THIS GAME

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.

# Changelog

- Formatting fix (4-4-2011)

-

# Global Warming king-of-the-hill

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.

## Pushing

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.

## Input

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:

12.4,2
1af3b,10.22,5.42,0.0,0.7
d5e86,-2.18,6.66,0.6,-0.2
\


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

## Output

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.

Example:

move,0.0,0.7


or

push,d5e86


The following lines are valid outputs for your program:

moveA0.0A0.7
moveX0.0Y0.7
move!0.0:0.7


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

## Scoring

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
foreach line in data.range(1,data[0,1]):
if distance(me, line[1], line[2]) <= 1:
write_csv_line(stdout, ["push", line[0], 1.0])

-
Well you could also minimise its utility by making it more physically correct such that the push is applied to you as well (in the opposite direction)... conservation of momentum and such. Then you could let players choose the push strength, and they'd have to decide how strongly they want to be pushed themselves. –  Martin Büttner Jul 26 '14 at 13:32
One issue that isn't addressed is what happens to me after I was pushed. If I try to move and one or more people push me, where do I move? What if player A pushes B pushes C pushes A? Also, since you give a speed (but not distance) moved, you should list how much time is simulated between turns (1 second?) –  Zaq Jul 29 '14 at 1:07
@justhalf I didn't want to do that because I had no idea how to, but i just realized it's dead simple to do. Sum the forces and cap to the max speed –  Kroltan Jul 29 '14 at 13:14

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

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

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

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

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

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

# Further ideas (still unordered):

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

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

## Overview

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

### Sight

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

## Coding

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

### Input

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

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.

Examples:

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.

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.

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.

### Cuckoo

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.

### Pretzel

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

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

### Join the dots

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

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

# Sandbox questions

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

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

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

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

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

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

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

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

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

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

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

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

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

### Overview

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.

### Scoring

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.

### Rules

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

WIP

### Meta

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

-
That's mainly because I haven't decided yet. I'll try to make it enough, but not too many ;) –  Geobits Jul 8 at 23:18

# 2048 Low Score

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

## Rules

• 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

C++

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

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

# TO BE SOLVED:

• 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

# Fortnightly Challenge #4 - Data Structures

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

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

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

# Commands

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

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

## Errors

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

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

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

Error: remove 0 0


Note that queries should never result in an error.

# Scoring

There will be six types of test cases:

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

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

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

# Rules/clarifications

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

# Example

(in progress)

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

## Number-Hopper Maze

http://cstheory.stackexchange.com/questions/6358/solving-a-number-hopper-maze

Write a program that solves the Number-Hopper maze described above. The input will be an ASCII art description of the maze

+------------+-----+
|x        |18|28  o|
| +--+--+ |  +--+--+
| |13|29|4|27|10|25|
| |  |  +-+--+     |
| |  |       +-----+
| |  |    |      23|
| |  +----+  ------+
| |  |    |        |
| |  | |  +------  |
| |  | |           |
| |  | |  ------+--+
| |  | |        |8 |
| |  | +-----+  |  |
| |  |  22|9 |  |  |
| |  +----+  |  |  |
|       14|11|     |
+---------+--+-----+

• - and + are walls, they are interchangeable
• x is the starting point
• o (lowercase O) is the destination

The numbers are hop points, to hop from number A to B, you must pay the cost of abs(A - B), the positive difference between two numbers. The goal is to find the solution with the minimum cost.

The solution for the example above is x-13-11-9-8-29-28-o, with total cost of 4.

The input of the program will be the ASCII art of the maze, and the output is the sequence of numbers to hop, with the total cost. In the format of x-13-11-9-8-29-28-o 4

To qualify, you algorithm must be under or equal to O(n^2). Include an informal proof if others suspect you.

I don't want to see pure brute-force solutions where obvious bad solutions such as moving in loops and making total 99999-steps for a small maze are included in the solution space.

The shortest code wins.

-
So the problem is (1) build a undirected, weighted graph from the ASCII maze and (2) find the shortest path from "x" to "o" in that graph. Part 2 is cookbook stuff and languages which have good support for it may have a real advantage, but part one presents some choices. I like it. –  dmckee May 28 '11 at 22:35
You should drop the complexity test, and worry about brute force. Just give an example big enough that brute force won't work. With this kind of problem, it should easy enough to give such a maze. –  MtnViewMark Jun 1 '11 at 6:49

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

-

# Thinking functionally (1): removing variables

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

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

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

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

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

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

a = 256

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


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

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

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


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

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

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

# Good Vibrations

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

This challenge requires you to implement a theremin.

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

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

-

# Find sociable numbers

### Background

A number is perfect if it is the sum of its divisors; for instance 6=1+2+3

A pair of numbers is friendly if they are the sum of each other's divisors; for instance 284=1+2+4+5+10+11+20+22+44+55+110 and 220=1+2+4+71+142.

In general, a list of n numbers is sociable if each element is the sum of divisors of the previous elements, with the first being the sum of divisors of the last.

### Input

An integer, n on STDIN.

### Output

A list of n numbers which are sociable, in the order outlined above, each on its own line. If you can't find any suitable list, you may output nothing, False, or 0, but you must search up to at least 2^32-1, and preferably as high as your language will allow

### Winning

This is code-golf, so the shortest code wins. However, I will also create a bounty to be awarded to the fastest program, as measured on my command-line (Windows 7 with GNU coreutils, python27, python3, node.js, perl) or in a web IDE in chrome (brainfuck, golfscript?)

Edit: to clarify the relationship between input and output

-
I don't think it's a good idea to have a code golf and a fastest code challenge in the same problem. You'll get incomparable answers. Maybe make a composite score that incorporates time and length? –  isaacg Apr 21 '14 at 0:58

# Objection! code-golf

In the near future, the legal world is crumbling. If a case lasts longer than three days, the defendant is assumed to be guilty. Prosecutors create false evidence to get their guilty verdict or flawless record. Defense attorneys are forced to retaliate, claiming that the ends justify the means. In the trials and tribulations of the courtrooms of tomorrow, how will we ever get justice for all? This truly is the dark age of the law.

Luckily, the world has you. Just 11 short years ago, you were a ragtag rookie lawyer in a world of big fish, but you had potential and it showed. You always trusted your client, no matter how bad things looked. You were able to cut through the deception and reach the truth. When times got hard, you forced your biggest smiles. Of course, it was only 3 years before a little misunderstanding cost you your badge, but that's all cleared up now. You're back, ready to protect those no one else will and make miracles happen.

Except... You're pretty sick. For some reason you can't quite remember, you've got a crippling fear of cold medicine. Clearly, you're in no position to stand at the bench. If you can't be there to clear your client's name, you'll have to write a program to do it for you!

For this challenge, you'll be writing a program that can take your place in a cross-examination. There are three different things you need to keep track of: Facts, Evidence, and Statements.

• Facts
• There are 26 Facts, named A, B, C... Y, Z. Usually, only a small number of them will be relevant, but you must be able to handle all of them if necessary. Contrary to their name, a Fact can be either True or False.   You are never told the Facts, but you can figure them out from your...
• Evidence

• Evidence is the most important thing for you to have, because it's how you know the Facts. You could make the case* that Evidence is everything in court. Pieces of Evidence have a name and a description of their relevance to the Facts. Evidence comes in two flavours: Direct and Circumstantial. Direct Evidence proves a Fact, while Circumstantial Evidence proves a fact if and only if a condition is met.   You get your Evidence as input in this format:

Direct Evidence
Name of evidence: [Fact] is <true/false>.

Circumstantial Evidence
Name of evidence: If [Fact] is <true/false>, then [Fact] is <true/false>.

• Statement

• A Statement is a declaration of Fact by a witness. There are also two kinds of Statements: Absolute and Conditional. An Absolute Statement claims a Fact, while a Conditional Statement claims a Fact if and only if a condition is met. Statements are taken as input in the same format as the second half of a piece of Evidence.

Your job is to analyze your Evidence to determine the Facts, then try to find contradictions in the Statements.

A Statement can contradict either an earlier Statement or a piece of Evidence. If a Fact is proven to be True or False and the witness claims the opposite, that is a contradiction. Note that If A is true, then B is true. and If A is true, then B is false. do not contradict unless A is true.

Input

Input comes from either stdin or a file, in exactly this format:

Evidence
<One or more pieces of Evidence on their own lines>
Testimony
<One or more Statements on their own lines>


Output

If there is a contradiction between a proven fact and something the witness claims, you must find the first Statement that contains the contradiction. If it contradicts the Evidence, output this:

Objection! Statement n contradicts this piece of evidence:


followed by a space and the name of the contradicted Evidence. n is replaced with the number of the contradicting Statement (starting at 1). If, instead, the witness contradicts themselves, output this:

Objection! Statement n contradicts statement m.


n is replaced with the number of the contradicting Statement and m is the number of the contradicted Statement (both starting at 1. m < n).

No objections, Your Honor.


Examples

Input:

Evidence
Thinker Clock: C is true.
Receipt: If C is true, then W is false.
Testimony
A is true.
B is false.
If A is true, then W is true.
H is true.
C is false.


Output:

Objection! Statement 3 contradicts this piece of evidence: Receipt


Input:

Evidence
Metal detector: B is true.
Testimony
If B is true, then A is true.
A is false.


Output:

Objection! Statement 2 contradicts statement 1.


Input:

Evidence
Stuffed animal tail: N is false
Testimony
A is true.
N is false.


Output:

No objections, your honor.


Assumptions

• The Evidence will never contradict itself. Evidence is infallible.
• There will never be a logic loop (e.g. If A is true, then B is true., If B is true, then A is true.)

* If you know what I mean

-
Wouldn't the Thinker Clock be the evidence being contradicted, then? There's more direct contradiction between the Thinker Clock and the last statement. –  cjfaure Jun 4 '14 at 17:14

# Epic Customizable Tank Battle (Work-In-Progress)

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

This will be a challenge.

## Main Idea

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

The Arena:

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

The Bots:

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

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

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

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

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

Bot vision:

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

Winning criterion:

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

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

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)

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

Misc.

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
else:
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.

-

# Self-Enumerating Pangram

Lee Sallows, a British electronics engineer had the following sentence prove true:

This pangram contains four as, one b, two cs, one d, thirty es, six fs, five gs, seven hs, eleven is, one j, one k, two ls, two ms, eighteen ns, fifteen os, two ps, one q, five rs, twenty-seven ss, eighteen ts, two us, seven vs, eight ws, two xs, three ys, & one z.

In this instance, the sentence contains the correct number of letters that form the sentence as well as provide the number of letters... Sentence-inception if you will... ;)

The purpose of this exercise is to emulate something similar...

Using whatever programming language (made for golfing or otherwise), start with a prefix, such as: This sentence has and then compute the letter distribution and enumerate (as words) these values in a list. For example this prefix will complete its first iteration as:

This sentence has two t's, two h's, one i, three s's, three e's, two n's, one c and one a

Naturally this newly created sentence is incorrect because the values expressed in the sentence do not match the actual letter distribution within the sentence, and so the program must continue looping, correcting itself until a valid and correct statement has been reached.

Your program must loop through and re-edit the sentence, and stop when it reaches a valid statement. The final result must be the output of the program, with a counter indicating how many turns it took to reach the valid statement...

So in other words the output must be in the format of the following example:

XXX. This sentence has two t's, two h's, one i, three s's, three e's, two n's, one c and one a

Or words to that effect, where the XXX at the front is the number of turns it took to reach the valid statement... Please make sure you provide a sample of your code in your answer as well as the final output that the code provides based on your prefix entered...

Also, I won't tolerate any silly loopholes...

This is code-golf, and so the winner of this challenge will be based on the answer with the lowest bytes, determined within a month's time of the release of this question... Best of luck!

-
Most problems which don't take input can be improved by making them take input. Why not make it take an arbitrary prefix, and then use the prefix "This sentence has" as a test case? (I assume you've checked that it terminates; if you take this approach, it will be worth mentioning that if it doesn't terminate for the given prefix then a program can loop forever). –  Peter Taylor Aug 13 '14 at 10:54
@WallyWest Peter is suggesting that you don't draw the line. For non-terminating inputs the programs should be allowed to not terminate either. –  Martin Büttner Aug 14 '14 at 7:23
@WallyWest Lee Sallows wrote an interesting paper on the subject. He calculated that an introductory text of 25 letters only has a 10% probability of having a solution. The number of iterations needed to find a solution could be very large, especially with naïve search algorithms. –  squeamish ossifrage Aug 14 '14 at 10:42

# Transport Tycoon [control program WIP] king-of-the-hillgame

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

#/////////
######@@@*
/**@@#####
//@@1#@@@*
/@@##@**/#
~~~+~~~~~|
///#######


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

## Construction

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): B-X-Y-tile  For example, this will build a road at (8,4): B-8-4-#  Invalid commands will be ignored. ## Vehicles 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):

P-id-X-Y-upgrades


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

P-5-7-7-


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

V-id


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

id-X-Y-passengers-upgrades-laststationX-laststationY


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.

4-5-5-15-SSR-3-4


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):

N-8
E-8
S-8
W-8
S-8
S-8
R-8
A-8


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.

## Passengers

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.

////@////
///@@@///
//@@@@@//
/@@@@@@@/
####1####
/@@@@@@@/
//@@@@@//
///@@@///
////@////


## Other

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.

## Todo

• 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
@SohamChowdhury github.com/professorfish/ttkoth –  professorfish Sep 16 '14 at 10:33

Sandbox note: This is an idea for a challenge based on the halting problem. As it is, it's hard to imagine it being popular on PPCG, but I'd really like to make it into something people would actually participate in. The reason is that it's really interesting from a theoretical point of view, as a fundamentally open-ended challenge. The beautiful mathematics of Turing and Gödel gurantees that there's always a new innovation that the cops could make, and there's always a way for the robbers to exploit it. So any ideas on how to turn this into something fun would be greatly appreciated.

## HALT in the name of the law

The robbers are getting away, and the cops have to decide whether to wait for them to stop and arrest them, or set up a road block at the state boundary. They do this by trying to predict whether the robbers' program will halt. Please note that this challenge is hard, especially for the cops.

Robbers are represented by programs written in a language called "w", which I invented for this challenge, and which I describe below. w is easy to implement and relatively easy to reason about. I will provide a reference implementation and a macro preprocessor that allows it to be written in a somewhat human-readable form.

Cops must provide a program (in any language) that takes a robber's w program as input, and tries to decide whether it halts or not. A cop submission is invalidated by a robber program for which it returns the wrong answer or fails to terminate.

## Cops

You must write a program that takes as input programs in the (pre-processd) w language. It should attempt to output a truthy value if its input program ever halts, and a falsy value if it doesn't. Your submission should be written in a "real" programming language rather than w. In addition to your program, you should provide a clear English explanation of how it works.

## Robbers

You must "crack" cops' submissions by providing one of the following three things:

• A program written in w that halts, but for which the cop program does not return a truthy value. (The cops waited at the roadblock while you stopped, changed your identities and went underground.) You must demonstrate that the program halts, either by running it in the reference implementation of W or by proving that it has to halt eventually.

• A program written in w for which the cop's program returns a truthy value, together with a proof that your program does not halt. (The cops gave chase, but you kept going until you reached the state border, infinitely far away.)

• A program written in w for which the cop program itself doesn't halt, together with an argument showing that it doesn't halt. (The cops just gave up and got some donuts, hoping nobody would notice.)

## Other rules

If the cops' program is nondeterministic (e.g. because it's doing some kind of stochastic search for halting conditions) then it suffices to show that there is some non-zero probability that it will return the wrong answer or fail to halt.

This is for the cops - the uncracked submission with the most votes wins.

## The w language

Syntax and semantics

w is a very simple structured programming language whose variables can only be incremented and decremented, and whose only control structure is the while loop. The syntax is designed to be as easy to parse as possible. Here is an example w program. Below I'll describe what it does.

a+ a+ a+
b+ b+
a{
a-
b+
}


There is a preprocessor [to be provided] that, among other things, standardises the whitespace, so that the code above will be formatted like this:

a b
a+ a+ a+ b+ b+ a{ a- b+ }


The first line (provided by the preprocessor) is a list of all the variable names that appear in the program. All variables in w are unsigned infinite-precision integers. (Infinite precision means that they will never overflow. This is very important for Turing-completeness.) A variable name is any combination of the characters a-z, A-Z, 0-9 and _. All variables initially hold the value 0.

The second line is a list of expressions. There are three kinds of expression. The first two are <variablename>+, which increments a variable by 1, and <variablename>-, which decrements it by 1. (For C programmers, think of these as the postfix ++ and -- operators.) Since the variables are unsigned, it is an error to decrement a variable whose value is zero. This will halt the program immediately. (Note that errors are counted as halting for the sake of this challenge.)

The third type of expression is a while loop. Its syntax takes the form {<variable_name>,<expression_list>}. If the variable has value 0, the expression list is skipped. Otherwise, the expression list is executed repeatedly until the variable becomes zero. (If the variable never becomes zero, the program fails to halt.) That's it - there's nothing more to the language than that.

Note that if you split the second line of the preprocessed program at the spaces, each item will either be } or a variable name followed by a symbol, so you can easily pop off the last character to see what kind of expression you're dealing with.

Looking back at the example program, the first line, a+ a+ a+ increments a three times, setting it equal to 3, and the second line sets b to three. The while loop decrements a while incrementing b until a is zero. So the value of a is added to b, and at the end of the program, a is zero and b is equal to five.

Alternative syntax

Optionally, the preprocessor can output w programs as a string representing a Python list. The example program would appear as follows. The first sublist is the list of variables, and the second is a list of lists representing the parse tree.

[["a", "b"], ["a+", "a+", "a+", "b+", "b+", "a{", ["a-", "b+"]]]


Input and output

For the sake of this challenge, we only care whether a program halts or not when given no input, so there is no input or output in the w language as described here. However, if we wanted we could say that a special variable (let's say _) is initialised with the program's input, and the value of the last expression evaluated is the output. If we do this, the language becomes Turing complete in the classical sense. (The proof is left as an exercise to the reader.)

Implementation notes

Implementing W correctly requires the use of infinite-precision integers. However, the only operations these need to support are incrementing and decrementing, which makes them much easier to implement. The reference implementation uses Python's unlimited precision integers.

-