What is the Sandbox?

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

To post to the Sandbox scroll to the bottom of this page and click "Answer This Question". Give the details of your challenge just as you would when actually posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, and mark it as posted here.

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

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

Submission Directory

This is a community-maintained list of the most active Sandbox submissions, sorted by major contest type. Add an entry to the top of this list if you add a new submission or update an old one. If you don't have enough reputation to edit questions you can ask in chat for a higher-rep user to add your submission for you. You may include a [status] indicator and tags to categorize your submission.

If this list grows too long you may remove entries that have been inactive for several days. It's best to remove submissions from this list once they've been posted to the main page.

code-golf

king-of-the-hill

Others

share

340 Answers 340

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.

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 bytes)
    --------         = 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 (host life.twnc.org, TCP port 1970).
  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 "wandernauta/" 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 difference between the amount of wins and the amount of losses, wins.

share
2  
That's great: it makes it clear that it's binary data and shows the endianness. –  Peter Taylor Mar 24 at 23:27
1  
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 at 9:13
1  
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 at 18:49
1  
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 at 19:38
2  
@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 at 19:44
2  
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 at 20:14
3  
"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 at 7:49
1  
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 at 17:22

Let's Play Mafia!


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

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

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

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

How to make a working bot

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

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: 
16: Will you please use your power on this player tonight?

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

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

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

The town has killed player_name!
They were a villager

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

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

The town opted to lynch no one today.

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

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)

share
3  
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. –  tohecz Jun 9 at 14:33

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.

share
1  
@Geobits, I believe in updating the accepted answer when a better answer comes along. –  Peter Taylor Apr 9 at 14:14

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.

share

Keep the unique characters down

The challenge

It's very simple: Your program should print the following text:

Elizabeth obnoxiously quoted (just too rowdy for my peace): "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG," giving me a look.

Scoring

The number of bytes in your code multiplied by the number of unique bytes in your code

Lowest score wins.

For example, a brainfuck or a whitespace answer would have a huge advantage here, as the multiplier would be very low (8 and 3 respectively). However, generally, writing programs in those languages produces much longer code which may negate that advantage.

share

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?

share

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.
  • Defence: your defence bonus.
  • Constitution: added to your HP (10 by default). Note: If your bot's constitution is -10, it dies immediately.

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

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

Here are the additional functions you get for your convenience:

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

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

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

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

Winning Condition

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

share

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

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

Cell lifetime

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

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

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.

share
1  
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? –  githubphagocyte Jun 7 at 1:35

Global Warming

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

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

Movement and positioning

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

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
data = read_csv(stdin)
foreach line in data.range(1,data[0,1]):
    if distance(me, line[1], line[2]) <= 1:
        write_csv_line(stdout, ["push", line[0], 1.0])
share
1  
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 at 13:32
1  
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 at 1:07
1  
@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 at 13:14

Underwater Survival Game

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

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

The Arena

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

enter image description here

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

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

The Game

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

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

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

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

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

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

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

The Species

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

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

The Hazards

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

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

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

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

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

How about ASCII Generator?

    _    ____   ____ ____  _____ _____ ____ _   _ ___    _ _  ___     __  __ 
   / \  | __ ) / ___|  _ \| ____|  ___/ ___| | | |_ _|  | | |/ / |   |  \/  |
  / _ \ |  _ \| |   | | | |  _| | |_ | |  _| |_| || |_  | | ' /| |   | |\/| |
 / ___ \| |_) | |___| |_| | |___|  _|| |_| |  _  || | |_| | . \| |___| |  | |
/_/   \_\____/ \____|____/|_____|_|   \____|_| |_|___\___/|_|\_\_____|_|  |_|

 _   _  ___  ____   ___  ____  ____ _____ _   ___     ____        ____  __
| \ | |/ _ \|  _ \ / _ \|  _ \/ ___|_   _| | | \ \   / /\ \      / /\ \/ /
|  \| | | | | |_) | | | | |_) \___ \ | | | | | |\ \ / /  \ \ /\ / /  \  / 
| |\  | |_| |  __/| |_| |  _ < ___) || | | |_| | \ V /    \ V  V /   /  \ 
|_| \_|\___/|_|    \__\_\_| \_\____/ |_|  \___/   \_/      \_/\_/   /_/\_\

__   _______     _             _       __       _     _  _ _    _           
\ \ / /__  /__ _| |__   ___ __| | ___ / _| __ _| |__ (_)(_) | _| |_ __ ___  
 \ V /  / // _` | '_ \ / __/ _` |/ _ \ |_ / _` | '_ \| || | |/ / | '_ ` _ \ 
  | |  / /| (_| | |_) | (_| (_| |  __/  _| (_| | | | | || |   <| | | | | | |
  |_| /____\__,_|_.__/ \___\__,_|\___|_|  \__, |_| |_|_|/ |_|\_\_|_| |_| |_|
                                          |___/       |__/                  
                                  _                                         
 _ __   ___  _ __   __ _ _ __ ___| |_ _   ___   ____      ____  ___   _ ____
| '_ \ / _ \| '_ \ / _` | '__/ __| __| | | \ \ / /\ \ /\ / /\ \/ / | | |_  /
| | | | (_) | |_) | (_| | |  \__ \ |_| |_| |\ V /  \ V  V /  >  <| |_| |/ / 
|_| |_|\___/| .__/ \__, |_|  |___/\__|\__,_| \_/    \_/\_/  /_/\_\\__, /___|
            |_|       |_|                                         |___/     


ref: http://www.rootsecure.net/index.php?p=ascii_generator
share
1  
Including kerning? That'd require a little more specification, though. –  Joey Mar 23 '11 at 20:52
2  
serif or san-serif? (joke :D) –  mauris Mar 28 '11 at 5:54

Ruby on Rails

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

CipherSaber

Special for gnibbler, who posted numerous nice entries for the original (now-deleted) CipherSaber thread.

Find the shortest (suggestions for better metrics welcome) way to write CipherSaber. There are several parts to this puzzle:

1. RC4/Arcfour

Arcfour is fully specified elsewhere, but for completeness, I'll describe it here. (In case of any discrepancies between the Internet-draft and this description, the former is normative.)

Key setup

Set up two arrays, S and S2, both of length 256, where k_1 is the first byte of the key, and k_n is the last.

S = [0, ..., 255]
S2 = [k_1, ..., k_n, k_1, ...]

(S2 is filled with the bytes of the key, again and again, until all 256 bytes are filled up.)

Then, initialise j to 0, and shuffle 256 times:

j = 0
for i in (0 .. 255)
    j = (j + S[i] + S2[i]) mod 256
    swap S[i], S[j]
end

This completes key setup. The S2 array is no longer used here, and can be scrubbed.

Cipher stream generation

Initialise i and j to 0, then generate the key stream as follows:

i = 0
j = 0
while true
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    swap S[i], S[j]
    k = (S[i] + S[j]) mod 256
    yield S[k]
end

Encrypting/decrypting data

  • To encrypt, XOR the keystream output with the plaintext
  • To decrypt, XOR the keystream output with the ciphertext

2. CipherSaber

CipherSaber (which is what we're implementing in this question) is a variation of RC4/Arcfour in two ways:

10-byte IV/nonce

When encrypting a message, 10 random bytes should be obtained, such as via /dev/urandom, and be written into the first 10 bytes of the encrypted output. When decrypting a message, the first 10 bytes of the input is the IV used to encrypt it.

The RC4/Arcfour key setup stage is run with passphrase || IV as the key, where passphrase is the user-specified passphrase, IV is as described above, and || is concatenation. So, a passphrase of "Hello, world!" and an IV of "supercalif" (however unlikely that is :-P) would result in a key of "Hello, world!supercalif".

Multiple iterations of key setup

In order to help prevent the vulnerability that made WEP encryption completely broken, the key setup stage of RC4 is run a user-specified number of times. The value of j should be retained between iterations.

Because of this variation on the key setup, using your system's RC4 is unlikely to work (although kudos to you if you pull it off :-D).

3. Test vectors

Here are some test vectors you can use to test your programs. I can post some more if people want more data to test with.

You only need to implement the encryption program. You do not need to supply the decryption program, but your encryption program's output must roundtrip correctly to the original input when processed with a correctly-implemented decryption program using the correct key.

share
1  
I've put up an online CipherSaber encryption & decryption tool that people can use to check their results before posting answers. –  squeamish ossifrage Apr 4 at 13:00

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.

share
1  
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 at 22:29

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

share
3  
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 at 0:58

Objection!


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

If there are no contradictions, output this instead:

No objections, Your Honor.

Examples

Input:

Evidence
My badge: L is true.
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

share
1  
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 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.

Upgrade system:

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

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

Types of weapons:

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

Additional Notes:

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

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

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!

share
1  
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 at 10:54
3  
@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 at 7:23
2  
@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 at 10:42

Transport Tycoon [control program WIP]

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

Chatroom for this challenge

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

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

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
share
1  
check out dinopoloclub.com/minimetro for a minimalistic transport network game that might be amenable to computer solution –  Sparr Aug 11 at 13:39
1  
@SohamChowdhury github.com/professorfish/ttkoth –  professorfish Sep 16 at 10:33

15P: Integer Creme Pi

This task is under consideration as part of the First Periodic Premier Programming Puzzle Push.

Write a program to obtain and output an estimate of pi = 3.14159265358979323846... using only integer arithmetic.

Requirements:

  • Your estimate of pi should be printed as a [fully reduced???] fraction: 22/7

  • The required precision is an input [3--8] to your program. You may choose the definition of "precision" that best suits you method from

    1. The number of figures in the full decimal expansion before the first non agreeing digit.
    2. The maximum number of figures for which the rounded real and estimated values are equal
    3. The largest number n for which (pi-estimate)/pi < (0.5 * 10^i)

    The value given above (22/7 = 3.142857142... is correct to 3 figures by all three methods). Please state which method you use.

  • You must not use any floating-point, non-integer fixed-point, or rational number type or constant supplied by you language or by a external library. (NB the restriction on using floating point constants means you may not do something like Print ( round(Math::Pi()*10^p), "/", (10^p))

  • Entries should be complete programs

Testing

[[ Here I will provide a script in python to check a input against each of the three "precision" evaluators list above ]]

Evaluation

Code golf rules. Programs must be correct for precisions [3--8].

Possible methods

I see several approaches here:

  • Graphical integration using Bresenham circle or similar algorithm
  • Monte Carlo integration
  • Summing one of the many series or possibly evaluating a continued fraction.
  • Evaluating area/perimeter for inscribed and/or circumscribed regular polygons

which should provide some room for players to get creative.

share

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

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

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

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

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


A minimal implementation of the make (1) utility.

By minimal I mean,

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

This only leaves constructs (called rules) of the form

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

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

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

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

A target is deemed already built if

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

Otherwise it is built by

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

A prerequisite is deemed fulfilled if

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

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

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

apply.

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

Sample Input

# Babymake compatible makefile for babymake
all:babymake

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

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

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

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

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

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

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

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

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

Sample output

$ ./babymake < babymake.example cleaner
 rm -f babymake.o  lex.yy.o  y.tab.o
 rm -f y.tab.c y.tab.h
 rm -f lex.yy.c
$ ./babymake < babymake.example all    
 cc -c babymake.c
 yacc -d babymake.y
 cc -c y.tab.c
 lex babymake.l
 cc -c lex.yy.c
 cc -o babymake lex.yy.o y.tab.o babymake.o
$ ./babymake < babymake.example    
$ ./babymake < babymake.example bogus
ERRNO: 2: No such file or directory No rule to make target 'boguser'.
share
1  
I suggest that the golf exercise be to simply output the list of commands to run, not actually execute them. Will make testing much easier. –  MtnViewMark May 27 '11 at 0:50

How long until my next birthday is on a weekend

I would like to know how much time (in days) I have to wait (from now) until my birthday occurs on a weekend...

  • The required tool could accept arguments or standard input.
  • The only variable passed as input (as argument or stdin) is my birth day in the strict form YYYY/MM/DD with only digits, separated by / (of course: YYYY for birth year, MM for the month and DD for the day of month.
  • The output must present the number of days to wait, from now, and the target date with the day of week, in the form Wait DTW days to WWW, YYYY/MM/DD where DTW in integer is the number of days to wait, WWW as day of week abbreviation could be Sat or Sun and the target date in same form as input.
  • Once done, there is no more request (tool could finish quietly, loop, bug or crash)
  • About February 29th, there are 3 ways you can handle it:

    • strict: Where birthday may occur once every 4 years
    • right: Where birthday is March 1st while Feb 29th doesn't exist.
    • relax: Where birthday could be Feb 28th or March 1st, but only while Feb 29th doesn't exist.

    The tool must match in the right manner, but could accept an option as choice between one of the three ways.

  • Shortest golfed code wins
    • -3 explanation (while golfed version must use one letter variable, ungolfed version is welcome with useful variable names)
    • -3 if properly loop on STDIN
    • -5 if no requirement of external library
    • -10 if an option to choose the way of considering February 29th.
    • 0 for shebang (unless they contain more than runtime options: switch r in sed or p in perl are runtime options, they count for null)
    • N embed code on shebang line in counted normally.
share
2  
How would you handle birthdays on February 29th? It would be an interesting special case, and it will increase the complexity of the problem. –  PhiNotPi Dec 13 '13 at 23:15
1  
Is this going to get answers which are much different to the currently active calendar-related questions? IMO it would be best left for a couple of months. Variety is a good thing. –  Peter Taylor Dec 13 '13 at 23:41

Digital Music Box

What are holidays without music boxes?

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

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

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

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

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

Input

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

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

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

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

Output

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

QUESTIONS

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

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

share

Line up for golf!


Alice, Bob, Carol, Dave, and Eve are going out for a nice game of golf and need your help to decide in what order they will play.

Your program will input some statements, which are defined as a condition, and then one or more optional logical boolean operators followed by another condition. (That's [Condition]([Logical][Condition])* in regexp notation.) A logical boolean operator is "and" or "or."

A condition is a name, followed by the word "is," followed optionally by the word "not," followed by one of these:

  • in front of
  • behind
  • n spaces in front of
  • n spaces behind
  • next to
  • nth
  • nth to last

An example of a valid condition is "Alice is not next to Bob".

Associativity is from left to right, except for "not," which only applies to a single statement. This means that "x or y and z or not a" means "((x or y) and z) or a," where x could be "Alice is 1st" or "Alice is behind Bob" or "Alice is not 2nd to last."

Your output must be the order in which the players line up, separated by commas, from front to back of the line.

Here's the full specification in regexp notation:

[Statement] = [FullCondition]([Logical]([Condition]|[FullCondition]))*
[FullCondition] = [Name] is [Condition]
[Condition] = (not)? (in front of|behind|[Number] space(s)? (in front of|behind)|next to|[Ordinal]|[Ordinal] to last)
[Logical] = and|or
[Number] = 1|2|3|4...
[Ordinal] = 1st|2nd|3rd|4th...

And finally, here are some sample inputs and outputs.

Input:
The players are Alice, Bob, and Carol.
Alice is 2nd.
Bob is in front of Alice.

Output:
Bob, Alice, Carol
Input:
The players are Alice, Bob, and Carol.
Alice is 1 space in front of Bob. // remember to handle pluralization correctly!
Carol is 1st to last.

Output:
Alice, Bob, Carol
Input:
The players are Alice, Bob, and Carol.
Alice is in front of Bob.

Output:
Alice, Bob, Carol
Carol, Alice, Bob // multiple outputs may be required
Input:
The players are Alice, Bob, and Carol.
Alice is in front of Bob.
Bob is in front of Alice.

Output:
// nothing
Input:
The players are Alice, Bob, and Carol.
Alice is not in front of Bob and Carol is not 2nd or Bob is 1st.

Output:
Carol, Bob, Alice
Bob, Alice, Carol
Bob, Carol, Alice

This is , so the shortest code in bytes will win!


share
3  
The comments in the test cases reduce their usefulness as test cases. Moreover, the first one contradicts the "full specification", and the second one adds to it. The spec should contain everything needed to justify the correctness of the test cases. You also need to specify desired behaviour when there is no solution, and to include a test case for that scenario. –  Peter Taylor Mar 7 at 14:04
1  
How are conditionals to be interpreted when mixed in a single full condition? Alice is 1st or 1st to last and in front Bob or 1 space behind Bob –  Jan Dvorak Mar 7 at 14:12

4 and 20 baked in a π

While some might describe π as a string of seemingly random numbers, one can also look at it in a way similar to a monkey with a typewriter. Eventually, it should calculate out to something more interesting. For example, the sequence 1337 shows up 4,814 places to the right of the decimal. At 700,731 places right of the decimal, you'll find the sequence 160151, which is "pi" represented as ASCII (although you'll find a 'pointer' to it much faster, as the sequence 700731 begins at 29,830 digits to the right).

So, your task is to make a program to find things in π. Your program will accept a positive integer and output the number of places right of the decimal point that number appears. To keep the run times down, input can be limited to numbers in the range of 0 to 1000 (without leading zeros).

Example: Using 415 as the input, the output should be 2:

3.14159
   ^

Rules:

  • You can not use any precalculated values of π, including language constants, built in functions that return π or digits of π, or any resource outside the code itself (such as files or websites).
  • You can not use any trig functions to calculate π.

Bonus points if you find the sequence 072 101 108 108 111 044 032 087 111 114 108 100 033.

This is code golf, so lowest score wins.

share
1  
It's not clear to me whether you require answers to support leading zeroes. Also: program, named function or snippet? And how indexed? (Giving 415 as a test case would be a good way to answer the last question) –  Peter Taylor Mar 11 at 6:58
3  
Isn't this just Calculate 500 digits of pi with a search function tagged on at the end? By the way, your bonus points are quite safe — even if you searched a trillion trillion trillion digits of pi, your chance of finding an arbitrary 39-digit sequence would still be less than 0.1%. –  squeamish ossifrage Mar 11 at 14:59

I like trees

...so this is a challenge to make me a tree.

Produce a program or function called tree which takes a single integer argument, N and draws a Pythagorean Tree N levels deep, where level 0 is just the trunk.

Each junction of the tree should place the vertex of the triangle at a random point on the perimeter (this point should be uniformly distributed over at least 5 equally spaced points, or uniformly over the whole semicircle).

Optionally your tree may be 3d, be colourful, or be lit according to the time of day. However, this is code-golf, so the smallest file wins.

Tags: code-golf, graphical-output

share
3  
If you post this as a code golf challenge, I think you should be a lot more rigorous about what you're asking for. An example: "Write a program that uses a Lindenmayer system to generate a fractal tree image based on a set of rules given as input (e.g., (X → F-[[X]+X]+F[+FX]-X), (F → FF))‌​" –  squeamish ossifrage Mar 21 at 23:27
2  
@squeamishossifrage, that would definitely be closed as a duplicate. ali0sha, questions which ask for random output usually run into problems around what distribution and how good an entropy source they need; and I think there's a reasonable chance that as written this would be closed as a near-enough duplicate of the question I just linked. –  Peter Taylor Mar 22 at 5:40

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.

share

Ping an IP address continually and report the dropped to returned ratio

Create a console program that pings an IP address at most once per second and reports the ratio of dropped to returned packets to the screen in real time.

The IP address will be provided on the command line in standard IPv4 notation. (eg. 192.168.0.1)

The 'ping' method should be ICMP echo (See here for a summary of ICMP packet structure) with a packet size of at least 32 bytes.

Your program must be "standalone" and cannot rely on external programs, libraries, or resources.

This is so let the shortest answer win

share

You must log in to answer this question.

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