What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, and click "Answer This Question". Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, replace the post here with a link to the challenge and delete it.

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

  • 2
    Suggestion: instead of having a notice on the top answer ("note: if you are..."), you'd better just put a moderator notice below the question – nicael Mar 19 at 19:35
  • 2
    @nicael We can only choose from three post notices: citation needed, current event, and insufficient explanation. – Dennis Apr 7 at 14:43
  • If you remove a post but didn't post it you can replace the text body with [](lots of text here to reach the min chars) to make it much smaller when removed – Christopher Apr 13 at 17:54
  • 4
    @Christopher Please don't do that for old proposals. It clutters the first page with an answer nobody cares about anymore, instead of staying hidden on page 10 where it will bother nobody. – Dennis Apr 13 at 18:17
  • @Dennis ? what are you talking about. As if if you didn't post it like you just removed you own sandbox because dupe or something – Christopher Apr 13 at 18:18
  • 3
    @Christopher If your proposal is still on the first few pages, you can replace the proposal with a stub to save vertical space on these pages. However, if your proposal is already on page 10, editing your proposal will bump it to page 1, where space is more precious than on page 10. – Dennis Apr 13 at 18:21
  • @Dennis ohh that makes sense – Christopher Apr 13 at 18:25
  • Maybe it's time to consider cleaning some of this up a bit. There's just too much to go through and some of these proposals are years old and obviously not going anywhere (even some of the good ones). Perhaps cull anything that is two years old and has likewise been inactive for as long? – ouflak Aug 6 at 9:07
  • @ouflak You can sort posts by "active". That seems to resolve all of the problems you describe. – FryAmTheEggman Sep 27 at 19:04

2266 Answers 2266

Note: If you are seeing this first, you might want to sort by active.

Count the pips in a pair of dice

👉 Moved here

  • 4
    a) Either one or two dice seems fine to me. b) You should be able to upload the zip file into a Gist on GitHub. c) As far as I can, this is a code challenge and not a code golf. The golf score seems negligible in comparison to the accuracy score, and will probably serve mostly as a tie breaker. (And I think that's good.) – Martin Ender Jan 9 '15 at 11:20
  • (b) Maybe you could post your script in addition. – TheNumberOne Jan 9 '15 at 13:36
  • @MartinBüttner Good points. I'll re-tag this as a code challenge. I'm trying to come up with a scoring system that prefers innovative hacks over long-winded but 100% correct solutions; if you can suggest any improvements then please do. I've just generated a set of sample images. In most of them, the two dice are non-overlapping, so it should be possible to score reasonably well without going overboard on the segmentation. – squeamish ossifrage Jan 9 '15 at 20:02
  • @TheBestOne The Python script doesn't do anything exciting. It just places two dice in the camera's field of view with randomly selected faces pointing up, then gives then a random z-axis rotation from 0 to 2π (repeating the process if the two bounding boxes intersect). I added a little devilry at the post-processing stage (pincushion distortion, glare FX and depth of field blurring) to better simulate the output of a real camera and foil solutions that expect images with perfect geometry, but none of this takes place in the Python script. – squeamish ossifrage Jan 9 '15 at 20:15
  • @squeamishossifrage I meant so that people can generate more test cases if 100 isn't enough. – TheNumberOne Jan 9 '15 at 22:10
  • 1
    You could post 1000 cases and then announce the subset of 100 that will be used for scoring. – trichoplax Jan 12 '15 at 23:33
  • 6
    Can we assume these are all standard dice, so any two opposite faces add up to 7? This would allow double checks such as 3 and 4 can never be on adjacent faces, and 6 and 1 can never be on adjacent faces. – trichoplax Jan 12 '15 at 23:35
  • 1
    If the handedness/chirality of the dice is also guaranteed to be consistent then identifying 2 visible faces will uniquely determine the 3rd visible face, as a double check or to fill in unreliable data. I think it's worth stating explicitly whether the dice will be of consistent handedness. People can of course work this out for themselves by examining the image set, but it would be good to know for certain whether that is meant to be a reliable feature of the images. – trichoplax Jan 12 '15 at 23:37
  • @trichoplax Yes, they would be standard right-handed dice. I can't see the point in announcing a subset of images for testing, since this would only benefit latecomers – squeamish ossifrage Jan 13 '15 at 10:34
  • Ooo... a clustering algorithm question, this I like +1. – Magic Octopus Urn Sep 23 '16 at 16:42
  • 4
    JPEG is an image format which is very hard to read when not using a special library. "Divide the size of the program by 100" is not a good idea when allowing programs having less than 50% correctness: A program simply writing random numbers will already have something about 10% correctness and its possible to do this within less than 1000 bytes (-> positive score); a program really evaluating images surely will need more than 10000 bytes (-> negative score). – Martin Rosenau Nov 3 '16 at 18:48
  • Seems like a perceptron could do the trick – Santiago Benoit Jun 14 '17 at 17:13
  • See also: markfickett.com/stuff/artPage.php?id=389 – asmaier Apr 25 at 14:55
  • Do you know about the Secret Santa's Box? – user202729 Jun 26 at 16:22

Waving Hands bot

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


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

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

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

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

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

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

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

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


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

  • Is this intended as a short-term, deadlined competition, or will you be posting new results as submissions come in? I imagine for a contest like this, it may take a while to get something robust. Sounds fun, though! – Geobits Apr 9 '14 at 14:07
  • 2
    @Geobits, I believe in updating the accepted answer when a better answer comes along. – Peter Taylor Apr 9 '14 at 14:14
  • 2
    Thank you for introducing me to this game - I'm creating a revamped version and my friends and I at school are all having a great time testing/playing it ;) – Doorknob May 1 '14 at 20:49
  • gamerz.net/~fm/Main is [almost?] identical to Waving Hands, with an actually implemented human-vs-human version of the game. – Sparr Jul 25 '14 at 7:33
  • @Sparr, see also games.ravenblack.net/rules/0/index.html (which I'm sure used to say that it was Waving Hands with no disclaimers about being a variant) – Peter Taylor Jul 30 '14 at 9:07
  • Having seen a number of very complex KotH, I've changed my mind about their suitability and no longer plan to pursue this. – Peter Taylor Aug 17 '14 at 19:30
  • 1
    @PeterTaylor I still think this one is suitable, because it is possible to start with rather naive strategies (since output is merely two characters each turn) and then gradually build on that to use more interesting strategies. If you're just not willing to expend the effort to implement the controller, I'd be interested in doing that some day, but first I've still got two other KotH proposals lying around (which don't even have as low an entry barrier as this one). – Martin Ender Sep 4 '14 at 12:06
  • Should a bot be eliminated from the rest of a tournament if it dies? – TheNumberOne Jan 13 '15 at 1:40
  • 1
    @TheBestOne, as I say in an earlier comment, I now think this is too complex to be a good KotH, but if I were taking it forward then my answer would be, "By no means!" KotH should be round robins rather than elimination brackets to minimise the non-determinism. – Peter Taylor Jan 13 '15 at 8:05
  • @PeterTaylor Maybe you should make a challenge that is simply to implement the game such that it can be played by two human players. Perhaps don't make it code-golf, though. – mbomb007 Oct 9 '17 at 20:10
  • @mbomb007, I'm not sure what other winning criterion that variant could use. – Peter Taylor Oct 9 '17 at 20:13
  • Maybe just make it code-challenge. I think that if the game is implemented, it should be readable. After all, the game seems to be challenging enough. We don't need to throw in "make this as small as possible" as well. Debugging would be easier, too, since it's for human players, so testing is harder. – mbomb007 Oct 9 '17 at 20:42
  • @mbomb007, code-challenge isn't a winning criterion: it's an umbrella so that questions with non-standard winning criteria still have a tag. – Peter Taylor Oct 9 '17 at 21:16
  • Then just make it so the first solution wins. – mbomb007 Oct 10 '17 at 13:23

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.

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

King of the Hill- Simple RPG

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

The Rules of the Game

The Board

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

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

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.

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

DTMF Decoder

(?)


http://upload.wikimedia.org/wikipedia/commons/thumb/d/d3/66a3aDTMFpad.jpg/320px-66a3aDTMFpad.jpg

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

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

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

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

DTMF Table

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

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


  • 3
    Nice idea. If you want to make it code golf, I'd probably leave out all the fanciness and require 100% accuracy. If you want to include additional and varying amounts of noise and phase shifts, I think this should rather be a code challenge and you'd need to provide a large benchmark set of audio files to test against. – Martin Ender Oct 18 '14 at 0:15
  • @MartinBüttner if it was a code-challenge, would I do that with N gradiations of noise (sets of test files, or maybe just a big one) and the "score" would be what's the worst you can handle? Maybe a single long file (hundreds of tones) with increasing amounts of noise, score is how many are correctly decoded? – Nick T Oct 18 '14 at 0:17
  • Either that, or you include multiple difficulties, provide a hundred (say) test files with random parameters, and the score is the number of correctly recognised files. – Martin Ender Oct 18 '14 at 0:20
  • @MartinBüttner fleshed it in a bit more as a challenge, see anything awful? – Nick T Oct 18 '14 at 8:53
  • Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. – programmer5000 Jun 9 '17 at 20:12
  • @programmer5000 noticed you want this one as well...I'll hold on to it for a little while longer. The issue I had was that I'm not sure how to convert theory--the theoretical limit of detection given a SNR and symbol length--into practice. Probably need to revisit and maybe pester folks at dsp.stackexchange.com for help with that. – Nick T Jun 13 '17 at 15:13

Anarchist chess

Initial position

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

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

This is an example of an impartial game.

  • 3
    The space of valid positions seems rather small. Is this not a solved game? – Martin Ender Feb 5 '16 at 22:30
  • @MartinBüttner You're right, it's definitely too small as is. If I post it I'll need to make the board larger than 8x8. I don't know if the game has been previously suggested. – feersum Feb 5 '16 at 22:59
  • Oh you just made it up? I thought it was a thing. In that case, you probably don't need to be worried about it being solved but maybe about participants solving it ;) – Martin Ender Feb 5 '16 at 23:00
  • So it's only one set of pawns and they can capture each other? – Peter Taylor Feb 6 '16 at 13:53
  • @PeterTaylor Yes. – feersum Feb 6 '16 at 14:49
  • OK, so this is also a combinatoric game, because captures can split it into independent subgames. Some subgames, at least, are easy to analyse. Maybe worth asking on math.se whether anyone can find a full analysis. – Peter Taylor Feb 6 '16 at 15:21
  • 3
    This is an interesting game, but unfortunately the second player will always win since he can mirror whatever move the first player makes along the vertical axis of symmetry (e.g. if P1 moves the 2nd pawn up two, then P2 moves the 7th pawn up two). – George V. Williams Aug 13 '16 at 14:18
  • 2
    @GeorgeV.Williams Good observation... so for a tournament only odd-sized boards should be considered. – feersum Aug 14 '16 at 2:51
  • 2
    @feersum, That's probably a good idea, as well as increasing the board size (the current size takes <1 second to solve). Another option is to consider misère play, where the last player to move loses. Misère play is in general harder, especially since this game appears to be "wild" which is an area of ongoing research. I really think this could be a great competition once the details are ironed out. – George V. Williams Aug 15 '16 at 3:31

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

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

enter image description here

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

enter image description here

(hint: it isn't)

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

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

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

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

A unit is decided by the following:

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

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

Sandbox notes:

  • This is in development.
  • Test cases coming later. Feel free to provide some.
  • If somebody has code they would like to donate to me for test case generation, please do. :P
  • I might change the units req. to a higher number depending on how this turns out.
  • Any other advice?
  • Some images failing and succeeding the test would be cool – Quill Jan 14 '16 at 3:07
  • I know, working on test cases. Will do tomorrow. – Picard Jan 14 '16 at 3:08
  • 1
    Haha, I like this but it does seem rather simple. If a language can only take the pixels as an array of RGB numbers it's pretty trivial (map, divide, floor, sum). Maybe it could be some kind of average so that 150 180 30 would have the same number of units as 100 120 20 (a darker shade of the same colour)? Or match rotated/flipped images? – user81655 Jan 14 '16 at 12:27
  • Could you shrink the images? It looks kinda freaky scrolling through the sandbox and seeing this... (p.s. you can use the img tag <img src=... width="300" />) – J Atkin Feb 12 '16 at 0:38
  • @EᴀsᴛᴇʀʟʏIʀᴋ famous last words "will do tomorrow" lol – Rohan Jhunjhunwala Jul 13 '16 at 20:45
  • @RohanJhunjhunwala ....oops. >_> I need code to generate the test cases, haven't written it. – Picard Jul 16 '16 at 18:11
  • @EᴀsᴛᴇʀʟʏIʀᴋ haha – Rohan Jhunjhunwala Jul 16 '16 at 18:26
  • @EasterlyIrk Perhaps it will magically do itself in 6 to 8 weeks! :-) – wizzwizz4 Oct 28 '16 at 13:05
  • You going to post this riker? – Christopher Jul 10 '17 at 9:41
  • Is this ever going to get posted? – MD XF Aug 5 '17 at 1:42
  • @MDXF yes, but it's not going to be soon. – Picard Aug 5 '17 at 12:03

10-character golfing language

{{{rewriting}}}

Your task is to design and implement a new golfing language. The catch: it must only have 10 significant characters as commands.

Design and Implementation rules

Your language should have the following characteristics:

  • It must be Turing Complete (theoretically).
  • There should be at most 10 characters (of your choice) which are significant to the program. That is, any characters other than your 10 chosen characters should have no effect on regular program execution.
    • You can choose to have these characters be removed via preprocessing or producing an error if there are any in the source code (before program execution; they should not be used to terminate the program early as an 11th instruction, nor be used to encoded additional information).
  • Your selected characters should only consist of ASCII characters, unless:
    • You want to use or create a code page for your language if you desire to use characters outside of the ASCII plane. Said characters should be translated into regular bytes.
  • You should not design an encoding to a language, existing or not. As you are designing a language, your submission must be so. Submitting a “language” which is just a fancy way of encoding a Jelly program is therefore not allowed.
    • By extension, this includes having one of your commands be an "evaluate" function that is not for the language itself. So, you can't implement "eval python" or "execute shell code" functions.
  • Your language should be capable of basic input (through STDIN and/or command line arguments) and output (to STDOUT, STDERR, and/or a file).
    • You may choose to ignore any one of these I/O methods, as long as one of each is supported.
    • Implicit I/O is acceptable.

Winning

1 week after no new answers are added, the winner is the language which completes the following tasks in the fewest total bytes.

The Challenges

All numeric inputs and outputs can be any (consistent) base, including unary.

1: Greetings, Humans!

Challenge: Output the following text, with or without leading/trailing whitespace: Greetings, Humans!

Example Output:

Greetings, Humans!

2: Even cats

Challenge: Output every other byte of input, starting with either the first or second byte given.

Example Input:

Hello, World!

Example Output 1:

Hlo ol!

Example Output 2:

el,Wrd

3: Do the wave

Challenge: Given number N, output the first N lines of the following infinite wave:

#
 ##
   ###
      ###
         ##
           #
           #
         ##
      ###
   ###
 ##
#
#
 ##
   ###
      ###
         ##
           #
     .
     .
     .

4: Quine

Challenge: Write a non-empty program which outputs itself, character for character. It must be a proper quine.

5: Coprimality

Challenge: Given an integer \$n\$, output all integers \$k\$ coprime to \$n\$ such that \$1\le k \le n\$.

input, output
10, 1 3 7 9
7, 1 2 3 4 5 6

6: Ternary

Challenge: Given an integer N, output the base-3 (ternary) digits of N.

Note: You may not take input in base 3 for this challenge.

input, output
1, 1
2, 2
3, 10
4, 11
5, 12
120, 11110
250, 100021
253, 100101
254, 100102
1020, 1101210

7: Word value sum

Challenge: Given a string consisting of only uppercase ASCII characters (A-Z), calculate the sum of their positions in the alphabet (1-indexed).

input, output
"A", 1
"AAAA", 4
"HELLO", 52
"GOLF", 40

8: Shutters

Challenge: Given an integer N, output a triangle of height N, constructed according to the following algorithm:

  1. The first row has N /s.
  2. The second row has N - 1 /s.
  3. ...
  4. The second-to-last row has 2 /s.
  5. The last row has 1 /s.

That is, the Kth row has N - K + 1 /s.

input
output

1
/

2
//
/

3
///
//
/

4
////
///
//
/

10
//////////
/////////
////////
///////
//////
/////
////
///
//
/

9: Roll a die

Challenge: Given an optional seed (for randomness), yield a uniformly-random integer between 1 and 6.

10: Where am I walking?

Challenge: You will be given a list of at most four distinct characters representing the four cardinal directions. I will use ><^v for the sake of example, but you may choose any other four characters. Suppose there is a point at the origin of a 2D plane. Each directional character moves this point 1 unit in that direction. Given this list, output the final destination of this point.

input, output
"", 0 0
">>>>>^", 5 1
">v<^", 0 0
"v>>^>v<^vv^<", 1 -1
"vvvvvvvvvvvvv<<<<<<<<<<<<<", -13 -13

11: Reproduction

Challenge: Write a program \$P_0\$ in your language which outputs another program \$P_1\$ in your language, which outputs another program \$P_2\$ in your language, which outputs another program… and so on. No two \$P_j\$ should be the same, that is, all programs generated should be distinct from each other.

Note: Your program may not read its own source code for this challenge. Standard rules apply.

12: Product

Challenge: Given an optional integer N and N additional integers, output the product of those N integers.

N, ints -> output
5, 1 2 3 4 5 -> 120
1, 3 -> 3
2, 1 1 -> 1
9, 0 1 9 3 4 8 12 9 120 9 -> 0
4, 100 200 300 400 -> 2400000000
3, 91 23 84 -> 175812

13: Sort a string

Challenge: Given a string of printable ASCII characters (and optionally its length), sort the characters by the code points of the string. Here is a list if you're unfamiliar with them.

"input" -> "output"
"hello" -> "ehllo"
"the YMCA" -> " ACMYeht"
"~..~ {_+}" -> " +.._{}~~"
"this is an example input, with some stuff!" -> "       !,aaeeeffhhiiiilmmnnoppssssttttuuwx"

(...more challenges to come...)

14: Repeat indexing

Challenge: Given two integers R and I and a string S, repeat the Ith character of S R times. (K can be 0- or 1-indexed; I will use 0 here.) You may assume that index I exists for S and that R is non-negative.

R, I, "S" -> "output"
4, 1, "Hello, World!" -> "Heeeello, World!"
0, 0, "language" -> "anguage"
3, 3, "hi!" -> "hi!!!"
5, 2, "aaabbb" -> "aaaaaaabbb"
  • "Your language should be capable of basic input" - is a language that only implicitly does both (or indeed either) acceptable? (I'm guessing yes) – Jonathan Allan Jun 23 at 12:51
  • Quine - proper, or is say 0 a quine if it outputs 0? – Jonathan Allan Jun 23 at 12:54
  • The way to win with high probability (encode Jelly) is banned, and the ban is non observable? Again? Come on, this is not quine rules... – user202729 Jun 23 at 14:33
  • 1
    @JonathanAllan Yes to comment #1, no to #2 – Conor O'Brien Jun 23 at 20:01
  • @user202729 I was kinda hoping that people would be able to use their minds and have a bit of common sense. Come on, everyone has one... – Conor O'Brien Jun 23 at 20:03
  • 1
    you need at least 10 challenges (otherwise you can do a SK combinator with single commands to do each of the challenges + empty program to do another) – fəˈnɛtɪk Jun 24 at 15:53
  • @fəˈnɛtɪk Hardcoding will be a problem. I intend on having 15 challenges, along with a hidden set of 15 additional challenges to prevent hardcoding – Conor O'Brien Jun 24 at 22:01
  • I doubt anyone would be so cheeky as to take this as a loophole, but you should probably say explicitly that languages aren't allowed to use command-line flags to modify their behavior (or, alternately, that all solutions must use the same flags across all tasks). – DLosc Jun 28 at 4:51
  • @DLosc Good idea, and thanks for the grammar fix tho – Conor O'Brien Jun 28 at 5:27
  • 1) For the sake of challenge 6, you'll want to change "numeric I/O can be in any consistent base" to exclude I/O in ternary. 2) Suggestion: a challenge that takes two (or more) numeric inputs. – DLosc Jun 28 at 16:59
  • rand=lambda seed: 4 #guaranteed to be random (please define random) – Jo King Jun 29 at 14:56
  • 1
    @JoKing no? I'm pretty sure this site has a definition of random. (I distinctly remember there being at least 1 meta about randomness) – Conor O'Brien Jun 29 at 18:04
  • @AidanF.Pierce Thanks for the feedback, I'll simply disallow reading the program's source for that particular challenge. – Conor O'Brien Jun 29 at 18:10
  • So 6 if seed>5 else seed+1 is valid? Random doesn't mean uniformly by default – Jo King Jun 30 at 0:13
  • Suggestion: A challenge mixing string and number input, e.g. repeat this string N times – Jo King Jun 30 at 2:33

Underwater Survival Game

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

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

The Arena

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

enter image description here

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

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

The Game

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

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

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

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

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

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

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

The Species

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

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

The Hazards

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

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

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

  • 3
    Next task after getting a controller program written is to write a 3d visual representation to watch back interesting matches... – trichoplax Jul 28 '14 at 22:50
  • Let us continue this discussion in chat. – trichoplax Jul 29 '14 at 9:14
  • 1
    "Shrimp always attack with scissors" How appropriate... – trichoplax Jul 29 '14 at 13:06
  • 1
    This challenge is old but good. I predict you'll get a lot of rep for this... – noɥʇʎԀʎzɐɹƆ Jun 23 '16 at 17:18
  • @uoɥʇʎPʎzɐɹC provided it ever happens and isn't too complicated... – Martin Ender Jun 23 '16 at 17:19
  • @MartinEnder Yeah, it's been a couple years now... – noɥʇʎԀʎzɐɹƆ Jun 23 '16 at 17:43
  • You should post this already... – John Dvorak May 5 '17 at 15:57
  • @JanDvorak Sure, are you going to write the controller? ;) – Martin Ender May 5 '17 at 15:59
  • deeeep.io – mbomb007 Oct 9 '17 at 20:12

Who needs a GUI anyway?

Most people like GUIs.

You don't.

They say that GUI's show them pretty pictures.

Your task:

Write a program that displays said image in full 256-colour ANSI art in the terminal. Because you need to show them your leet skillz at programming, you have decided to write this as short as possible. "That's a program?" - Some user

Challenge

  • Given input from stdin or the command line of an image filename, the program must output it to stdout in ANSI.

    • To output a string in green (#00FF00), you can print \x1b[48;5;46mInsert text here! where \x1b is codepoint 27 (hex 1b).
    • \x1b[48;5;<bgcode>m sets the colour.

    • At the end of each line, the colour formatting should be reset so not to make the output look ugly on terminals with a resolution higher than 80x24 set.

  • Your program must support at least one of the following image file formats: PNG, JPG, BMP, PPM, SVG

    • You may use image processing libraries to parse images.
  • The output must be viewable in any terminal sized over 80x24.

    • If the longest side is the x-axis, its length must be resized to 80.

    • If the longest side is the y-axis, its length must be resized to 24.

    • The aspect ratio of the image must be kept the same. Scale using min(80/X,24/Y), rounding down

    • The output can be assumed to be a console that supports ANSI.

    • Each character of the resized image represents 1 pixel.

  • The characters printed must be a space.

  • The colour for an individual pixel must be the closest available colour in the colour map (Text version in wikipedia link above).

    • In this case, the similarity of 2 colours can be defined as: ((R1-R2)^2+(G1-G2)^2+(B1-B2)^2)^0.5 where results closer to zero indicate closer similarity.
  • If your image format supports the alpha channel, you may assume it is empty/doesn't exist.

Example

PPCG logo

Found here is our beloved logo. This hexdump is what your program should output given that image as an input.

This is a code golf, the answer with the shortest answer in bytes wins!

  • 2
    1. Are image processing libraries allowed? Decoding the image is the most difficult part. 2. What does "closest available colour" mean? How do you calculate the distance? 3. Provide a link to a simple reference about using ANSI escaping. 4. An example is great. One is enough, unless more examples can highlight different aspects of the question. 5. should the aspect ratio be maintained? – ugoren Sep 6 '15 at 14:46
  • Updated to answer 1,2,3,5. Answer to 4 upcoming. – Blue Sep 6 '15 at 15:15
  • 1. ANSI is the name of a standards institute. "In ANSI" is not very clearly expressed. 2. It's not clear why, having said that the task is about outputting arbitrary images, you suddenly start talking about printing "Hello, World!". 3. You seem to be assuming that each character on the terminal will correspond to one pixel, but it's not clear why. And then you say that we can use any character. Wouldn't it make more sense to leave foreground alone and just change background and write a space? 4. You've left open a classic loophole by allowing people to scale their image to 0x0 or 1x1. – Peter Taylor Sep 6 '15 at 17:11
  • @PeterTaylor 1. Removed that reference. 2. I hope that's clearer, it was meant to explain how you can use ANSI escaping. 3. Added that explicitly. 4. Loophole closed but I'm not sure how clear it is now. – Blue Sep 6 '15 at 18:13
  • 2
    I think this would be better suited for popularity-contest because image processing / printing may very between systems. Correct output should probably be console based to avoid giving languages like JavaScript an easy advantage. Taking in input with function argument is also common. Also, are PPM allowed? This can make it easier for languages that don't support image processing well to participate. – Downgoat Sep 7 '15 at 18:39
  • If there is a clearly defined objective specification (which there appears to be) then popularity contest doesn't seem to be a good fit. If you don't have a reason to avoid golf, that seems a perfectly good fit. – trichoplax May 3 '16 at 18:43
  • @trichoplax currently discussing this in chat – Blue May 3 '16 at 18:44
  • The resizing rule doesn't quite work since the screen isn't square. For example, if the image is 800 by 700, then the longest side is horizontal but scaling that down to 80 still leaves the vertical at 70, which is longer than 24. I think what you want is "Scale down the image just enough to fit into 80 by 24, while maintaining the aspect ratio as closely as possible" – trichoplax May 3 '16 at 19:03
  • If you want to give an explicit method, scale an X by Y image by min(80/X,24/Y). Then you just need to specify whether fractions become the floor, ceiling or are rounded. – trichoplax May 3 '16 at 19:09
  • Grammar question - does GUI's need that apostrophe? I'd write GUIs, but I don't know the rules for abbreviations like that – FlipTack Dec 25 '16 at 16:52
  • @Flp.Tkc fixed. I've lost my example program over time now so I'll have to recreate one – Blue Dec 25 '16 at 16:55
  • Do you plan to post this? I'd like to do so if you don't. Also, by community guidelines I'm allowed to do so in 7 days if you don't respond to this. This is a great challenge, I'd hate to see it go to waste! – MD XF Aug 18 '17 at 3:28
  • @MDXF Ping me tomorrow about it in TNB and I'll post it then :P – Blue Aug 18 '17 at 7:57

Self-Golfing Code

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

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

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

  • It is a little interesting too me that you basically require the submitter to turn in a incompletely golfed submission. Or is this not intended to be a [code-golf]? – dmckee Aug 17 '11 at 14:24
  • 2
    It's still a code-golf. That's part of the challenge - you still have to golf it but leave room so that your program can still golf itself a little more. I think it would be interesting to see what approaches people take for this. – migimaru Aug 17 '11 at 14:28
  • Alternately, I could count the length of the golfed result instead of the original program, though I'm not sure it will make much difference in determining the winner. – migimaru Aug 17 '11 at 14:38
  • I think I need to add a rule that prevents a simple trim() operation to eliminate whitespace at the end of a line. Would it be sufficient to say "all trim()-like operations are banned"? – migimaru Aug 18 '11 at 15:02
  • why ban trim()? You force competitors to manually implement an otherwise built-in function. Besides, would "r_( )+$__" or an equivalent trivial trailing space replacement be counted? – arrdem Aug 18 '11 at 15:33
  • Hmm, I'm not sure what to do about it now. I don't like having to ban a function, but trim() allows for single statement solutions where you just read in the first line and trim off 5 trailing spaces. I was hoping for a challenge that would be more interesting. – migimaru Aug 18 '11 at 15:37
  • 3
    You'll need to ban comments, unnecessarily long variable names, all unnecessary whitespace... And even then I can see fairly easy cheap tricks like unnecessary variable swaps (`\` in GolfScript). Hard to make this robust enough. – Peter Taylor Aug 29 '11 at 8:48
  • @Peter Taylor I was already planning on banning comments. I don't think replacing variable names is non-trivial, though it might be in some languages. Whitespace is a big problem, though. In the end, I agree that this question doesn't seem like it'll work out. – migimaru Aug 29 '11 at 14:42
  • I think you need to add a source restriction, so that the user cannot create a gigantic program with tons of spaces then just remove a bunch. Make it so the program can only have 10 of each character or something. And maybe make the score the difference of the starting and ending programs. Then, I'd say that the output of the 2nd program doesn't have to be the same as itself, it can be even shorter! Then just use the eventual output of the nth program in comparison to the original. – mbomb007 Jun 4 '15 at 22:03
  • 1
    I believe it's a tad to vague. It would be too easy to do something like (in JS for e.g.) $$$$$$=eval(prompt().replace(/$+/g,"$"))... unless if that's what you want, of course. – Conor O'Brien Oct 19 '15 at 17:45
  • What about popularity-contest and drop conditions about other programs. The program should take it's own code and golf it in such way, that the resulting syntax tree differs. On any input both programs should behave in the same way. – Qwertiy Apr 22 '16 at 17:41
  • There may be a trivial loophole. Let's say that in language X xyz is a syntactically sound program that takes input, ignores it, causes no errors and outputs xyz. So a kind of a quine. Now Let's say that abcccdyz also ignores input and outputs xyz. Then xyz is the golfed version of abcccdyz, so the self golfing condition is met. If you give it another program in language X, it returns a syntactically correct program xyz. If abcccdyz is embedded in another program that you give as an input, it will give a program with xyz embedded in it, as it will be xyz itself. – Heimdall Nov 9 '17 at 18:23

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.

  • 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 '14 at 22:29
  • @Peter Taylor. Thank you for your comment. I do it for the x in lambda functions. For the second remark, it is also true, but since it is a popularity contest and since creativity is encouraged, is it absolutely necessary to be too precise regarding how the data has to be stored? – Thomas Baruchel Mar 26 '14 at 4:51
  • Popularity contests should be more tightly specified than contests with objective criteria, not less, because otherwise they're just an invitation to throw crap at the wall and see what sticks. – Peter Taylor Mar 26 '14 at 14:34
  • @Peter Taylor. OK. What do you think of the current version? – Thomas Baruchel Mar 26 '14 at 14:50
  • The more I think about this question, the less suited I think it is for this site. – Peter Taylor Mar 26 '14 at 19:48
  • @Peter Taylor. OK. I will try to find another one later. Regards. – Thomas Baruchel Mar 26 '14 at 19:51
  • This sandbox post has had little activity in a while. Please improve / edit it or delete it to help us clean up the sandbox. Due to community guidelines, if you don't respond to this comment in 7 days I have permission to vote to delete this. – programmer5000 Jun 9 '17 at 16:29

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

Random Golf of the Day

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

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

About the Series

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

#1: Shuffle an Array

#2: Numbers from a Normal Distribution

#3: Integer Partitions

#4: The Bertrand Paradox

#5: Diamond Tilings

#6: Roll a d20

#7: A distinctly random character (guest entry by trichoplax)

#8: Shuffle an infinite list

Further ideas (still unordered):

  • Poisson disc sampling: This is a method to randomly distribute points across the plane densely while maintaining a minimum distance between points. I think this might be nice to golf. Further reading.
  • Generate a random chessboard: The submissions should randomly produce a believable chessboard. "Believable" here mostly affects pawns: they may not appear on the first row of their colour, there may be more pieces of other types if pawns are missing (due to conversion), and two pawns may only be in the same column if at least one of the opponent's pieces is missing. Submissions should be able to generate any valid board with finite probability, but it doesn't have to be uniform.
  • Generate a random arithmetic expression: This basically asks to create a tree of binary and unary operators, subject to some constraint - either on the structure of the tree (n nodes, say) or on the result of the arithmetic expression (generate a random expression that evaluates to a given n).
  • Generate a random hole-free polyomino (or orthogonal polygon) (of given size).
  • Vague idea: Generate points on a sphere with uniform distribution.
  • Vague idea: I'd like to include a challenge on random walks.
  • Vague idea: I'd like to include a challenge which has to generate a random number with a constraint based on its digits, but where you're not allowed to use strings or arrays (so you have to access the digits arithmetically).
  • Idea I'm not sure about: Generate a valid Unicode character as a set of UTF-8 bytes with uniform randomness.
  • Idea: Implement a (specific) PRNG.
  • Idea: Generate a random Brainfuck program (or other balanced string). Would probably need to require uniform distribution and deterministic runtime to be interesting.
  • As discussed in chat, the "random partitions" doesn't require much modification of one existing answer on a partition question, although since most can't be modified so easily it's probably on the right side of the borderline. The chessboard is sure to generate controversy over the definition of "believable". The random expr seems very close to a number of existing questions which require enumeration of arithmetic expressions. The Unicode one is basically just a Kolmogorov compression of the table of assigned codepoints. – Peter Taylor Feb 3 '15 at 14:24
  • @Peter, the chessboard challenge will come with an unambiguous spec. For the arithmetic expressions, I'll make sure to check what we've already had. Unicode: hm yeah, it would definitely be one of the simpler challenges. – Martin Ender Feb 3 '15 at 14:32
  • 3
    Idea: "reverse-engineering". Given a sequence of 1000000 random numbers from a generator of a known type (e.g. this), determine the next number. Have to discourage (or somehow disallow) brute-force answers. – anatolyg Mar 3 '15 at 21:32
  • 1
    1. Points on a sphere with uniform distribution: I'd be surprised if you weren't aware, but dA/dz for a sphere is constant: all slices of the same thickness have the same external surface area. So all you need is a uniform distribution of longitude and a uniform distribution of z height. 2. I like the chessboard idea. – Level River St Jun 14 '15 at 1:31
  • @steveverrill I wasn't aware that dA/dz is constant, but I was aware that this would be a rather simple instalment of the series. I've started to think that the chessboard challenge would be a pain to specify and to solve correctly. Currently, my favourites are the random polyomino and the Poisson disc sampling. – Martin Ender Jun 14 '15 at 10:26
  • @anatolyg: I was working on that problem for LCGs a while back. It turns out to become an integer programming problem, and I have a suspicion it might even be NP-complete. As such, it may be that brute force is the only solution that works in general. – user62131 May 12 '17 at 21:03
  • The "generate a random balanced string" problem isn't made much more interesting via requiring deterministic runtime and uniformity; you can just generate all balanced strings and pick one at random. It might be possible to make it viable via a complexity bound, but I'm not sure. – user62131 May 14 '17 at 0:07
  • @ais523 the last instalment is probably going to be some form of random walk, so the options still listed in the post are likely irrelevant at this point, unless I ever decide to extend this to 18 holes. Good point though. – Martin Ender May 14 '17 at 2:06

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?

  • Can we take it that there will always be a tempo change before the first line of music? It's hard to see how you could judge sound quality in an objective way. I like the question though. – Gareth Dec 24 '13 at 22:03
  • Yes, there will be a tempo change before the first line of music. Also, I agree that sound quality probably shouldn't be the focus, I have the real software for that. – PhiNotPi Dec 25 '13 at 0:37
  • What about sharps / flats? Could you clarify the sustain req with respect to the envelope you expect for e.g. note,sus,sus,sus? How much flexibility when note length not a factor of sample rate? (E.g. 57bpm @ 16kHz: if there are 57 lines must output be exactly 60*16000 samples or can each line be rounded to 16842 samples?) If raw output (i.e. wav without RIFF header) is not allowed, best to be explicit. – Peter Taylor Dec 28 '13 at 10:15
  • 1
    "When a chord is played, the sounds of all previous chords are stopped" — this isn't how music boxes normally behave; each note just fades out until it's played again. Also, how about accepting MIDI files? – squeamish ossifrage Jan 14 '14 at 10:22
  • Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) – programmer5000 Jun 9 '17 at 15:42

Which way will the see-saw turn?

Given an ASCII string of spaces, os, and Os, balance them on a see-saw pinned at the center, and determine which way it tilts.

For example, ooO O represents the situation:

ooO O
===== 
  ^

A lowercase o has a mass of 1kg, and an uppercase O has a mass of 2kg. The torque of a weight is its mass multiplied by its distance from the center of the see-saw. If the sum of the torques on the right of the see-saw is greater, the see-saw will tilt clockwise. If the sum of the torques on the left is greater, it will tilt counterclockwise.

In the situation above, the total clockwise torque is 2 * 2 = 4, which is greater than the total counter-clockwise torque, 1 * 2 + 1 * 1 = 3. So the see-saw tilts clockwise.

You may choose two fixed output values — one for “clockwise” and one for “counterclockwise”. Your program must consistently output these values for their respective situations.

The input is a string of odd length 3 ≤ n ≤ 255, and it is guaranteed to never be in perfect equilibrium.

  • *consistently. Also, related (but not duplicate) – Luis Mendo Jan 2 '17 at 1:07
  • maybe you could add that the see-saw is always pinned in the middle. The answer seems trival but I like it. Is there a reason to skip equilibrium? – Christoph Jan 3 '17 at 11:08
  • I'm sure that O isn't lower case. ;) – user48538 Jan 3 '17 at 13:36
  • @Christoph I think solutions are often more interesting when they are allowed to cut corners, so I try to add some well-defined corners to cut in my problems. Often, this means allowing solutions to disregard “special” cases (such as equilibrium, even n, or n = 1, in this case.) – Lynn Jan 3 '17 at 13:51
  • Hm I wonder of what solution you think :) In the way I'd answer this question there wouldn't be any major difference. – Christoph Jan 3 '17 at 14:04

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.

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

2048 Low Score

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

Rules

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

Choosing the winner

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

Algorithm specification

C++

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

Other languages

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

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

    So a typical output line is:

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

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

  • For linking your script to the interpreter:

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

My PC specification

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

TO BE SOLVED:

  • How to make it available to Windows other than C++?
  • Proper tagging.
  • 4
    Why not keeping the contest open forever? If you close it after some time, that would be annoying for people who see your contest when it is already closed if they want to participate. – ProgramFOX Jun 9 '14 at 14:01
  • @ProgramFOX Well, I can't guarantee that I will be here forever, and I limit the time of computation to 2s on machine. But you're right, that's not much a burden, so I changed it. Thanks. – yo' Jun 9 '14 at 14:22
  • @tohecz: In a previous contest I wrote a Python wrapper for submissions. This is reasonably cross-platform (using subprocess for communication), so I think it could work for your challenge. I could volunteer to write such a thing if your problem was posted. – nneonneo Jun 28 '14 at 23:44
  • 2
    As far as tagging goes, I'd go with code-challenge. – nneonneo Jun 28 '14 at 23:45
  • Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. – programmer5000 Jun 9 '17 at 16:52

Meta Code Bots

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

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

The Game Field

The playing field is a toroidal grid, with each cell containing either nothing (.), a robot ('>'), a crystal (=), or a base ('@').

..........
.>..@....^
.=..=.>...
.v.......=
..=@..@..^
.........=
^.<.....>=
=.=.=@....
..@....<.@
....=<^.=.

Robot Programming

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

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

Notes:

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

Editing the programming

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

Game Objective

Your goal is to navigate your bot to pick up crystals and return them to a base (they serve as collection points). Each crystal you successfully DROP off at a base earns you one point. Each bot can only carry one crystal at a time. These crystals can be acquired by GRABbing them off the ground or by GRABbing from an opponent bot.

Execution Order

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


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

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

Overhanded (Underhanded) Poker

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

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

Overview

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

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

Scoring

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

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

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

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

Rules

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

Controller

WIP

Meta

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

  • 3
    I like this idea a lot (and you getting smacked with a trout is intriguing). One suggestion: it doesn't seem you make a mention of how many games each bot will play against each other bot. Since this problem is (presumably) dominated by the RNG gods, deciding how many rounds are necessary to ensure rewarding good programs instead of lucky programs may be tricky. (Relevant meta) – BrainSteel Jul 8 '15 at 19:03
  • 1
    That's mainly because I haven't decided yet. I'll try to make it enough, but not too many ;) – Geobits Jul 8 '15 at 23:18
  • Does the second player know how many cards the first one changed or are the changes simultaneous? – randomra Jul 11 '15 at 10:03
  • @randomra I think simultaneous is best here. Otherwise I'll have to alternate turns as P1/P2 due to the advantage. – Geobits Jul 11 '15 at 14:49

Prime Spiral

This challenge was inspired by this question on math.SE by @Karl

You might be familiar with the Ulam spiral. What we're doing here is similar, but a little bit different, given a positive integer N we generate an image:

On an empty equally spaced rectangular 2d grid choose an arbitrary point and place a 1 then place a 2 on the grid point to the right of the 1. Then continue as follows:

If you're at number n<N:

  • If n is composite: Go straight in the same direction to place n+1
  • If n is prime: Turn right to place n+1 (overwrite, if there was another from a previous step)
  • Repeat this for n:=n+1.

Now consider the grid as a pixel image that is plain white. Then colour each pixel where we placed a number on the corresponding grid point. Then choose a finite rectangle that contains all the coloured pixels, and output it as an image.

Examples

For N=10^5 we get following output (by @Wojowu)

  • 1
    Had the same idea :p Maybe the challenge would be interesting as well if the task was to actually place the numbers of the grid. This would also be doable in languages that don't allow for graphical output. – JAD Dec 31 '16 at 10:37

Number-Hopper Maze

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

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

+------------+-----+
|x        |18|28  o|
| +--+--+ |  +--+--+
| |13|29|4|27|10|25|
| |  |  +-+--+     |
| |  |       +-----+
| |  |    |      23|
| |  +----+  ------+
| |  |    |        |
| |  | |  +------  |
| |  | |           |
| |  | |  ------+--+
| |  | |        |8 |
| |  | +-----+  |  |
| |  |  22|9 |  |  |
| |  +----+  |  |  |
|       14|11|     |
+---------+--+-----+
  • - and + are walls, they are interchangeable
  • x is the starting point
  • o (lowercase O) is the destination

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

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

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

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

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

The shortest code wins.

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

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

Gerrymander a Map

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

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

0000
0011
1111

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

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

abcd
abcd
abcd

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

Here is an alternative division in which gerrymandering was successful.

aacd
abcd
bbcd

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

The Distortion Metric

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

aa  c
a   c d
  b c d
 bb   d

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

abbbb
aaaab
aaaab
acccb
ccbbb
ccddd
ecccd
eeeed
eeeed
edddd

The Goal

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

More detail coming soon

  • would this be code-golf? – TheDoctor Oct 24 '15 at 20:40
  • 2
    Do you ever plan to post this? – MD XF May 31 '17 at 21:49

N-Player Battleship

The Rules

  • The field is a 5N by 5N grid, where N is the number of players.
  • The controller places each player's ships randomly.
  • Each player can see their ships and the shots they have made, successful or not. Each player can also see other players' successful shots.
  • Each player gets one shot per turn.
  • Each player's fleet consists of, for a total of 21 squares altogether
    • 1 aircraft carrier - 5 squares
    • 1 battleship - 4 squares
    • 2 destroyers - 3 squares
    • 3 assault boats - 2 squares
  • You are allowed to keep state information between turns, but not between rounds/games.

The Specs

Input

Input will consist of one integer and a list of lists, space-separated, like so: 3 [[S, X, .],[S, O, M],[S, ., H]]. This corresponds to the following grid:

S X .
S O M
S . H

These are the meanings of the characters:

  • . Unknown (i.e., it's empty or no one has attacked there yet)
  • O A piece of your ship that has not been hit
  • X A piece of your ship that has been hit
  • M One of your missed attacks
  • H A hit from another player
  • S A ship that has been sunk, either yours or an enemy's

Output

Output must be a pair of integers in the format x y.

Meta

  • Adjustments to the fleet?
  • More details needed in the spec or rules?
  • 1
    There would be more opportunities for interesting strategic decisions if you knew which enemy had been hit on each square. – Peter Taylor Dec 1 '15 at 20:56
  • If we assume that because this is KOTH, all 5 bots are competing in real-time on a host machine, then don't you need to standardise on a language (or at least open-source the code for the arena in the language(s) accepted) so people can write compatible bots? – cat Dec 2 '15 at 22:47
  • @sysreq: My plan is to communicate via STDIN/STDOUT, and bots will not communicate with each other, only with the controller. – El'endia Starman Dec 2 '15 at 23:42
  • I've never played battleship with more than one other person: suppose my bot guesses (4, 8). Is it a hit if any of the other bots have a ship in that spot? – cat Dec 3 '15 at 0:06
  • what if more than one bot does; all bots stay completely anonymous though the entirety of the game? – cat Dec 3 '15 at 0:07
  • @sysreq: I think it'll be better to have only one bot's ship per square. Yes, a hit will be a hit if any bot has a ship that occupies that square. – El'endia Starman Dec 3 '15 at 1:06
  • Will you be willing to open source the controller code (even if this challenge never goes up)? in the interests of fairness, of course, and that aside this is such a cool idea and I want to be able to do it myself (with less work and someone else's better code) – cat Dec 3 '15 at 1:11
  • is the input in the form of command line args or stdin? – cat Dec 3 '15 at 2:14
  • 1
    @sysreq: Ah, whoops. Input will be as command line args, most likely, At least, initially. I don't know exactly how it'll work yet. And yes, of course I'll open-source any code I write for this. – El'endia Starman Dec 3 '15 at 2:20
  • Depending on your implementation of the controller (and some clever code) it might be possible to write your controller's stdout to a named pipe and then require our bots to read stdin from said pipe --- almost like letting your controller write to the bots' stdin. – cat Dec 3 '15 at 2:23
  • are non-fatal hits to other player's ships represented like S? – cat Dec 4 '15 at 17:25
  • Also, the field you use for the example is a bit small; I think you should use a 10x10 (2 players) example – cat Dec 4 '15 at 17:25
  • I think that known-empty spots and unknown territory should be represented differently (i.e., known-to-be-empty spots as _ and unknown as .) – cat Dec 4 '15 at 19:59
  • @sysreq: Known-to-be-empty spots are misses, M. Non-fatal hits to other ships are just hits, H. Yes, the example field is small. I wrote this post at like 3 in the morning and it was big enough to have each kind of character... :P – El'endia Starman Dec 4 '15 at 20:08
  • Ah, those were stupid questions but thanks anyways. – cat Dec 4 '15 at 20:12

Snakes on a Torus

This would be representative of the classic Snake video game, but multiplayer. The game would be 2-4 players.

Game Description:

Each of the 2-4 snakes will always start at one of four fixed position on the board. Each snake continuously moves forwards at a constant rate. A snake stops moving upon death. The board wraps in both directions, but would be graphically represented as a grid (plane) in an actual game with people, so think of it as "snakes on a plane" if you wish. The dimensions of the grid are TBD.

Apples and poison apples (referred to as Blues and Reds) will spawn in random locations on the board, either at a random rate, or only to replace one as it's consumed (TBD). An blue increases your snake's length by 3. A red reduces your snake's length by 2 (to a minimum of 2). Both are useful in managing your snake's length.

A snake's length will increase by n by the tail not moving for n turns. A snake's length will decrease by n by the tail moving an extra space for n turns. Eating one blue followed immediately by one red should hold the tail for 1 turn, then continue as normal (they cancel).

Your snake will die if its head collides with its body or the head or body of another snake, whether alive or dead. So a head-on collision means both snakes die.

Your Bot's Job:

You will create a bot to play this game by submitting which of the 3 directions to move (turn left, straight, turn right) based on information including:

  • The game's grid as a 2D array
  • Each snake's current length
  • An ordered list of your snake's tiles and orientation
  • An ordered list of each enemy snake's tiles and orientation, and whether the snake is dead or alive.
  • The location of every apple on the board
  • The location of every poison apple on the board
  • Each player's numbers of wins, kills, and deaths.

You will likely be creating class that is an instance of a base class Snake, and implementing the necessary methods. If a move is not returned in the appropriate time-frame, your snake will move straight.

The Winner:

Each snake will be pitted against each other snake multiple times. The one which has the highest score after the most games wins. Scoring TBD, but will likely be something like +100 per win, +10 per death on your snake (someone ran into you), -10 per death. Tied games will be possible, since there will be allowed a short period of time while the last snake is alone on the map, in case it would die soon after winning.

Suggestions?

Suggestions for scoring are welcome. Besides winning, how should apples/length/kills be factored in? Personally, I was thinking most wins, followed by most kills, but I can see that might encourage some people to stay small and avoid everything. Some options (feel free to suggest more):

  • Prioritize wins, then kills
  • Weighted or point-based scoring for wins, kills, apples
  • Just score by length at end of match (so maybe after eliminating the others you could just grow until your bot dies)
  • Collect points by being the longest snake every tick

I don't know how soon I will get to making a controller, etc, but let me know what you think. If enough people are interested, I could invest time in it.

Controller in progress!

Bots must inherit the Player class, implementing the choose_direction() function.

I'm considering making it so that each snake must pick the next three moves at the same time. I'm not sure if this is necessary, but this would make it more like playing like a person, where you can't always react in time. This would keep the games from going super long if no snake would otherwise run into another one. It would also allow for shenanigans, like zipping in front of another snake to kill it.

Another cool idea would be to have the bots make choices asynchronously as the game progresses, the same way human players do. If you don't choose a direction during a tick, you go straight. This way, you could also take extra time to calculate a move by choosing to return a move less often.

Suggestions for input format would be great. (2D matrix of integer types, multiple lists, etc)?

This is based directly off of a game I've played, which I think is called either "Worm ed 2" (as in Worm: edition 2) or "Wormed 2". I was unable to find the game in a short search. The game is likely old, and I don't know where it could be found online if at all. If anyone knows of it, please comment!

  • 1
    I like the idea of players receiving several input types, so they can choose which to use, or use different types at different times, or mix them, as suits them best. For example, a list of every cell in the arena, and a list of every deadly cell (bodies of yourself and others) and separate lists of the individual snakes bodies, and apples and poison apples. – trichoplax Jun 5 '15 at 22:19
  • What happens in a head-on collision? – Nathaniel Apr 26 at 1:37
  • Also, it might be an idea to let apples have an influence on score, to encourage longer snakes. (I realise there is already an incentive to become long, because other snakes are more likely to die by hitting you. This will be stronger when there are more than 2 players. But it's hard to say whether that advantage is strong enough to outweigh the advantage of being small so that you can avoid things more easily, or of just ignoring apples entirely.) – Nathaniel Apr 26 at 1:39
  • @Nathaniel Both snakes die in a head-on collision. Also, I am pretty sure I have a TODO comment in the controller for scoring apples. I just haven't figured out what sort of weights to give them. I'll edit into the post that scoring suggestions would be helpful. Perhaps length could be scored? Idk, that's probably something to experiment with after the controller is finished. – mbomb007 Apr 26 at 3:33
  • The controller seems to be almost finished other than testing and scoring. I may need to look at timing as well. And if someone can look at improving performance, that'd be great, because [fastest-code] doesn't come naturally to me. There's probably a bunch of duplicated data that could maybe be reused. – mbomb007 Apr 26 at 3:48
  • Ah sorry, I saw "Scoring TBD, but will likely be something like +100 per win, +10 per death on your snake (someone ran into you), -10 per death" but had missed the other part where it mentions apples. – Nathaniel Apr 26 at 4:14
  • 1
    Am I the only one who is amused by the snake game being implemented in Python?... And for something more on topic, is there any particular reason you chose +3 and -2 for blues and reds, respectively? I think +1 and -1 might be appropriate. – Beefster Apr 26 at 18:42
  • 1
    @Beefster Because that's how it was in the original game. It would take much longer to play if they were +1/-1. And their value difference is 1 (3 - |-2|) so all lengths are still possible. This makes it so that red apples are actually sometimes useful in practice, because if you get a few too many blues, you may want to shrink yourself. They are not there to simply be avoided. – mbomb007 Apr 26 at 19:16

Optimizing swiping across a 1D keyboard

Many smartphones allow to enter text by swiping your finger across the 2D virtual keyboard. This technology is usually combined with a prediction algorithm that outputs a list of guessed words, sorted from most likely to least likely.

In this challenge:

  • We are going to swipe across a one-dimensional keyboard restricted to a subset of the 26 letters.
  • There will be no prediction algorithm: we want each word to be uniquely identified by its 'swipe sequence'.
  • We want the keyboard to be optimized in such a way that the total number of moves for a given list of words is minimized.

Swiping in one dimension

Below is a lexicographically sorted 1D keyboard with all letters:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

NB: This may be displayed on several rows if you're browsing from mobile. Please think of it as a single row.

To enter the word 'GOLF' on such a keyboard, we will:

  • start at G
  • swipe to the right to O
  • swipe to the left to F

Because L is located between O and F, we just go on swiping without stopping there.

So the swipe sequence of 'GOLF' on this keyboard is GOF.

More generally:

  • The first and last letters are always included.
  • Other letters are included if and only if a direction change is required just after them.
  • Repeated letters must be treated the same way as single letters. For instance, on the above keyboard:

    • 'LOOP' would be encoded as LP (with no stop on O)
    • 'GOOFY' would be encoded as GOFY (the O is included because there's a direction change there -- not because it's doubled)

Keyboard optimization

Let's consider the following list of words: ['PROGRAMMING', 'PUZZLES', 'AND', 'CODE', 'GOLF'].

We need 16 distinct letters to type these words, so we just need a 16-letter keyboard. The following one is -- again -- lexicographically sorted:

ACDEFGILMNOPRSUZ

With this keyboard, the words will be encoded this way:

  • PROGRAMMING: PRGRAMING (9 moves)
  • PUZZLES: PZES (4 moves)
  • AND: AND (3 moves)
  • CODE: CODE (4 moves)
  • GOLF: GOF (3 moves)

That's a total of 23 moves for all words.

But we can do much better with this keyboard:

CGODSELZNUIFRPAM

Which gives:

  • PROGRAMMING: PGMG (4 moves)
  • PUZZLES: PS (2 moves)
  • AND: AD (2 moves)
  • CODE: CE (2 moves)
  • GOLF: GF (2 moves)

for a total of only 12 moves.

Keyboard scoring

For a given list of \$n\$ words, the score of a keyboard is given by:

$$\sum_{k=1}^{k=n}{m_k}^2$$

where \$m_k\$ is the number of moves for the \$k\$-th word.

For instance, the two keyboards described in the previous paragraph would be scored \$9^2+4^2+3^2+4^2+3^2=131\$ and \$4^2+2^2+2^2+2^2+2^2=32\$ respectively.

The lower, the better.

The challenge

  • Given a list of words, your code must output a valid keyboard for this list. A keyboard is considered valid if each word generates a unique swipe sequence.
  • This is a . You'll be given several independent lists of words. Your score will be equal to:

    $$10\times S + L$$ where \$S\$ is the sum of the scores of your keyboards for all lists and \$L\$ is the length of your code in bytes.

  • The submission with the lowest score wins. In case of a tie, the submission that was submitted first wins.

Additional rules

  • Your code must run in less than 1 minute for each list.
  • Your code must be deterministic (i.e. it must always return the same output for a given input).
  • You may take the words in either full uppercase or full lowercase. Mixed cases are forbidden.
  • The input is guaranteed to have at least one solution.
  • Your code must work for any valid input. It will be tested with an undisclosed list of words to make sure that it's not relying on hard-coded results.
  • I reserve the right to increase the size of the test suite at any time to make sure that the submissions are not optimized for the initial test cases.

Word lists

(to be completed)

  • Not a preference, just pointing out different options: M*100+L means 3 words with moves 9, 2, 2 scores the same as 3 words with moves 5, 4, 4. A different scoring mechanism might reward consistency so that the latter scores lower (perhaps taking into account the maximum number of moves per word for a given answer). No idea which way would make a more interesting challenge though. – trichoplax Sep 30 at 17:28
  • @trichoplax Good point. At this stage, I'm not sure either which one would be better but that's definitely worth considering. – Arnauld Sep 30 at 17:34
  • There are probably lots of ways that would work for scoring, but one that comes to mind if you do decide on penalising occasional much longer moves is to make the score the sum of squares of the moves – trichoplax Sep 30 at 18:46
  • I think this is equivalent to the travelling salesman problem? If not, it feels very similar. Either way, I like this challenge. – Nathan Merrill Oct 2 at 2:58
  • You mention: There will be no prediction algorithm: we want each word to be uniquely identified by its 'swipe sequence': Does that mean using the keyboard "ABCD" is invalid if I have both "ABD" and "ACD" as words? – Nathan Merrill Oct 2 at 2:59
  • @NathanMerrill That's correct: ABCD is an invalid keyboard for these words. (DBAC, for instance, is valid.) Also, there exists no valid keyboard at all for, say, MOOD and MOD, but the lists are not going to contain such words. – Arnauld Oct 2 at 7:03
  • Ok, if that is the case, I'd make it very explicit (or give an example), because I didn't catch that on the first read through. – Nathan Merrill Oct 2 at 13:08

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

Dividing Strings

Division with numbers is great: 6 / 3 = 2, but have you ever wanted to divide strings? In this challenge you will, given two strings (s and t) divide s by t

Challenge

Given a string, s, find the substring in which t is repeated the most times (non-overlapping), return the amount of times t is repeated, example:

s = "HiFooFooFooFoo"
t = "Foo"
n = 4

Seems easy enough? Well if the substring ends with the first m characters of t, you should add what fraction of the string t was in the substring (m/t.len):

s = "12121"
t = "12"
n = 2.5

Rules

  • You only need to output to the precision your language supports. The minimum precision is two decimal places.

Examples

First line is s, second line is m, last line is output. Examples are double-newline seperated

FooFooFoo
Foo
3
GoatGoatGoatGo
Goat
3.5
SheepSheepSheep
Goat
0
GoGoatGoatGoat
Goat
3
GoatGoGoatGo
Goat
1.5
ab111cd
1
3
PigPigPi
Pig
2.666666
aabaabaaaba
aaba
2
aabaaaabaaa
a
4
  • 2
    Here's a nice testcase: "PigPigPi" / "Pig" – Conor O'Brien Aug 8 '16 at 19:20
  • what should "GoGoatGoGoatGo"/"Goat" return? – Nathan Merrill Aug 8 '16 at 19:24
  • "aabaabaaaba"/"aaba"-> 2 – Nathan Merrill Aug 8 '16 at 19:32
  • 1
    Can the partial string at the end overlap with an occurrence of the complete string? (The intended answer seems obvious but it's not explicitly specified.) – feersum Aug 8 '16 at 22:31
  • @feersum Not sure what you mean, can you give an example? – Downgoat Aug 10 '16 at 21:44
  • related – Picard Oct 1 '16 at 14:52
  • @Downgoat feersum probably meant something like this: abaabaa/abaa -> aba|(a)|baa, where the middle a is used as both leading/trailing part and thus overlaps (which I personally wouldn't allow for this challenge). Suggested test cases: aabaabaaba/aaba -> 1.75 (...|aaba|aba) and 121141115217/1 -> 3 – Kevin Cruijssen Feb 27 at 9:22

I'm always right

Given the following input:

  • A number consisting of decimal digits, the guess

  • A number consisting of decimal digits, the answer

You are to output a single natural number, the base, such that when you interpret the guess as a number in the base base, the distance between guess and answer is smaller than for any other choice of base.

To be clear,

  • answer is interpreted as base 10

  • guess is interpreted as base base

  • distance means absolute value

  • The base must be greater than the largest digit used. I.e. if 6 appears in the guess, you cannot output a base smaller than 7 because any base smaller than 7 does not use the symbol 6.

Motivation and Example

Your friend asks you a question like "What's the population of New York City?"

You have no clue, so you make a guess "1,400,000 people", you say.

He says "You're an idiot, the population is 8,550,405. You were so far off."

You then do some quick math in your head and say, "I wasn't that far off, I didn't realize you wanted base 10. I was using base 14. In base 10, I said 9,680,832, which wasn't that bad of a guess"

In this example

guess  = 1400000
answer = 8550405
base   = 14

Test cases

Eventually maybe.

You must log in to answer this question.

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