Sandbox for Proposed Challenges

Question

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

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. 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, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

Parts of the challenge you found unclear
Comments addressing specific points mentioned in the proposal
Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Get the Sandbox Viewer to view the sandbox more easily!

Community · Accepted Answer · 2020-06-17 09:03:53Z

48

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

Count the pips in a pair of dice

👉 Moved here

edited Jun 17 '20 at 9:03

Community♦

1

answered Jan 9 '15 at 11:02

r3mainer

19.4k11 silver badges12 bronze badges

5

\$\begingroup\$ 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.) \$\endgroup\$ – Martin Ender Jan 9 '15 at 11:20
\$\begingroup\$ (b) Maybe you could post your script in addition. \$\endgroup\$ – TheNumberOne Jan 9 '15 at 13:36
\$\begingroup\$ @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. \$\endgroup\$ – r3mainer Jan 9 '15 at 20:02
\$\begingroup\$ @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. \$\endgroup\$ – r3mainer Jan 9 '15 at 20:15
\$\begingroup\$ @squeamishossifrage I meant so that people can generate more test cases if 100 isn't enough. \$\endgroup\$ – TheNumberOne Jan 9 '15 at 22:10
2

\$\begingroup\$ You could post 1000 cases and then announce the subset of 100 that will be used for scoring. \$\endgroup\$ – trichoplax Jan 12 '15 at 23:33
7

\$\begingroup\$ 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. \$\endgroup\$ – trichoplax Jan 12 '15 at 23:35
2

\$\begingroup\$ 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. \$\endgroup\$ – trichoplax Jan 12 '15 at 23:37
\$\begingroup\$ @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 \$\endgroup\$ – r3mainer Jan 13 '15 at 10:34
\$\begingroup\$ Ooo... a clustering algorithm question, this I like +1. \$\endgroup\$ – Magic Octopus Urn Sep 23 '16 at 16:42
5

\$\begingroup\$ 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). \$\endgroup\$ – Martin Rosenau Nov 3 '16 at 18:48
\$\begingroup\$ Seems like a perceptron could do the trick \$\endgroup\$ – Santiago Benoit Jun 14 '17 at 17:13
\$\begingroup\$ See also: markfickett.com/stuff/artPage.php?id=389 \$\endgroup\$ – asmaier Apr 25 '18 at 14:55
\$\begingroup\$ and: dropbox.com/s/buyg5swn0o0und2/SnakeEyesFinalPres.pptx?dl=0# \$\endgroup\$ – asmaier Apr 25 '18 at 15:06
\$\begingroup\$ Do you know about the Secret Santa's Box? \$\endgroup\$ – user202729 Jun 26 '18 at 16:22

| Show 2 more comments

Peter Taylor · Accepted Answer · 2014-04-08 07:06:31Z

32

Waving Hands bot

This is a sketch for a king-of-the-hill 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.

answered Apr 8 '14 at 7:06

Peter Taylor

42.5k8 gold badges51 silver badges113 bronze badges

\$\begingroup\$ 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! \$\endgroup\$ – Geobits Apr 9 '14 at 14:07
2

\$\begingroup\$ @Geobits, I believe in updating the accepted answer when a better answer comes along. \$\endgroup\$ – Peter Taylor Apr 9 '14 at 14:14
2

\$\begingroup\$ 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 ;) \$\endgroup\$ – Doorknob♦ May 1 '14 at 20:49
\$\begingroup\$ gamerz.net/~fm/Main is [almost?] identical to Waving Hands, with an actually implemented human-vs-human version of the game. \$\endgroup\$ – Sparr Jul 25 '14 at 7:33
\$\begingroup\$ @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) \$\endgroup\$ – Peter Taylor Jul 30 '14 at 9:07
\$\begingroup\$ Having seen a number of very complex KotH, I've changed my mind about their suitability and no longer plan to pursue this. \$\endgroup\$ – Peter Taylor Aug 17 '14 at 19:30
1

\$\begingroup\$ @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). \$\endgroup\$ – Martin Ender Sep 4 '14 at 12:06
\$\begingroup\$ Should a bot be eliminated from the rest of a tournament if it dies? \$\endgroup\$ – TheNumberOne Jan 13 '15 at 1:40
1

\$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor Jan 13 '15 at 8:05
\$\begingroup\$ @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. \$\endgroup\$ – mbomb007 Oct 9 '17 at 20:10
\$\begingroup\$ @mbomb007, I'm not sure what other winning criterion that variant could use. \$\endgroup\$ – Peter Taylor Oct 9 '17 at 20:13
\$\begingroup\$ 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. \$\endgroup\$ – mbomb007 Oct 9 '17 at 20:42
\$\begingroup\$ @mbomb007, code-challenge isn't a winning criterion: it's an umbrella so that questions with non-standard winning criteria still have a tag. \$\endgroup\$ – Peter Taylor Oct 9 '17 at 21:16
\$\begingroup\$ Then just make it so the first solution wins. \$\endgroup\$ – mbomb007 Oct 10 '17 at 13:23

Add a comment |

Community · Accepted Answer · 2017-04-13 12:39:25Z

Conquer the Solar System

king-of-the-hill

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

totallyhuman · Accepted Answer · 2017-09-14 22:20:41Z

King of the Hill- Simple RPG

king-of-the-hill

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

The Rules of the Game

The Board

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

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

Mechanics

Each turn, a player can:

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.
Perform a special attack: you can either perform a ranged attack, an area attack, or no special attack at all.
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:

Goblin. Attack: 1; Defence: 1; HP: 1; moves randomly; 1XP for killing.
Orc: Attack: 3; Defence: 2; HP: 5; follows players; 5XP for killing.
Troll: Attack: 5; Defence: 2; HP: 10; moves randomly; 10XP for killing.
Giant: Attack: 10; Defence: 5; HP: 15; follows players; 50XP for killing.
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
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
@Manu Yes, but I haven't been able to work on it for a rather long while. — Alex, Mar 6 '15 at 22:33

Nick T · Accepted Answer · 2014-10-21 18:46:05Z

DTMF Decoder

code-challenge audio (dsp?)

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.

Generate your own DTMF WAV file (might use this for a test file, or convert this to text if needed): http://www.audiocheck.net/audiocheck_dtmf.php
Play with buttons (they like to get stuck on...): http://onlinetonegenerator.com/dtmf.html
Cheat and use a web resource: http://dialabc.com/sound/detect/index.html (works up to about level 8, no, you can't actually use this.)

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

Community · Accepted Answer · 2020-06-17 09:03:53Z

19

Anarchist chess

king-of-the-hill

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.

edited Jun 17 '20 at 9:03

Community♦

1

answered Feb 5 '16 at 14:56

feersum

30.3k18 silver badges24 bronze badges

3

\$\begingroup\$ The space of valid positions seems rather small. Is this not a solved game? \$\endgroup\$ – Martin Ender Feb 5 '16 at 22:30
\$\begingroup\$ @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. \$\endgroup\$ – feersum Feb 5 '16 at 22:59
\$\begingroup\$ 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 ;) \$\endgroup\$ – Martin Ender Feb 5 '16 at 23:00
\$\begingroup\$ So it's only one set of pawns and they can capture each other? \$\endgroup\$ – Peter Taylor Feb 6 '16 at 13:53
\$\begingroup\$ @PeterTaylor Yes. \$\endgroup\$ – feersum Feb 6 '16 at 14:49
\$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Feb 6 '16 at 15:21
3

\$\begingroup\$ 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). \$\endgroup\$ – George V. Williams Aug 13 '16 at 14:18
2

\$\begingroup\$ @GeorgeV.Williams Good observation... so for a tournament only odd-sized boards should be considered. \$\endgroup\$ – feersum Aug 14 '16 at 2:51
3

\$\begingroup\$ @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. \$\endgroup\$ – George V. Williams Aug 15 '16 at 3:31

Add a comment |

caird coinheringaahing · Accepted Answer · 2018-04-13 09:22:15Z

19

Build a golfing language with me

edited Apr 13 '18 at 9:22

answered Mar 18 '18 at 16:51

caird coinheringaahing

37.5k1 gold badge39 silver badges58 bronze badges

5

\$\begingroup\$ Although I'd personally enjoy such a challenge, I am afraid that the sub-tasks have little to no interaction between each other, so the post might be closed as off-topic for being a multi-part challenge, albeit the presence of the tag multiple-holes. How are you going to enforce It doesn't aim to complete one of the sample challenges in one command? Other than that, I don't think the winning criterion makes much sense here. Imo the answer that breaks the chain should win. \$\endgroup\$ – Mr. Xcoder Mar 18 '18 at 17:15
\$\begingroup\$ As per Martin Ender's suggestion, I've added concise descriptions for the first 12 challenges, but I don't have time to finish the rest at this very moment. I feel like the post should be self-contained, having to read so many separate challenges is quite annoying. Feel free to rollback / edit according to your preferences. \$\endgroup\$ – Mr. Xcoder Mar 19 '18 at 14:41
\$\begingroup\$ Added simple descriptions for the rest of the challenges. \$\endgroup\$ – Bubbler Mar 20 '18 at 7:25
\$\begingroup\$ "It doesn't aim to complete one of the sample challenges in one command" seems a bit easy to work around. For example, you could make a command to output ello, World! without breaking this rule, or to store Hello, World! in a variable without printing it, etc. If you try to ban this, finding the right place to draw the line will probably be hard. \$\endgroup\$ – Nathaniel Mar 22 '18 at 13:43
6

\$\begingroup\$ Also, I'm personally not a fan of the two week cutoff, and I was under the impression that time-limited challenges were a bit of an old-school thing that people don't really do any more. It prevents people from participating if they join the game late, and for no good reason. (By the way I like this challenge idea a lot.) \$\endgroup\$ – Nathaniel Mar 22 '18 at 13:45
\$\begingroup\$ @Nathaniel Regarding the two week end, every answer-chaining has to have some way of preventing it from continuing ad infinitum. Answers can (and should) still be posted afterwards, just with the addendum that they can't win. \$\endgroup\$ – caird coinheringaahing Mar 22 '18 at 17:12
\$\begingroup\$ @cairdcoinheringaahing maybe there should just be no winner. Then people won't be discouraged from continuing after one is declared \$\endgroup\$ – dylnan Mar 22 '18 at 21:43
\$\begingroup\$ @dylnan Challenges must have a winner to be on-topic \$\endgroup\$ – caird coinheringaahing Mar 22 '18 at 21:52
\$\begingroup\$ You can still have an objective scoring criterion but not declare a winner. You can decide to forgo meta discussions anyway. \$\endgroup\$ – dylnan Mar 22 '18 at 22:02
\$\begingroup\$ "every answer-chaining has to have some way of preventing it from continuing ad infinitum" <--- why? And why would that apply to answer-chaining and not any other kind of challenge? \$\endgroup\$ – Nathaniel Mar 23 '18 at 0:47
3

\$\begingroup\$ Or another way to put it: your challenge already has a natural cutoff, namely the point where no more golfing is possible (i.e. one of the test challenges can be done in zero bytes and the rest in one byte each, if not before that point). It seems more natural and more fun to let it continue until it reaches that point, rather than cutting it off artificially. \$\endgroup\$ – Nathaniel Mar 23 '18 at 3:09
1

\$\begingroup\$ @cairdcoinheringaahing I don't see that saying that challenges must have a winner, just that you must be able to objectively score yourself. "And the interesting thing that the score alone is enough to create this motivation - there doesn't even need to be competition". \$\endgroup\$ – Wheat Wizard♦ Mar 26 '18 at 4:15
1

\$\begingroup\$ I'd go for "output the sign" vs "sum of 1-n", since you haev another "sum the input" challenge. \$\endgroup\$ – Rɪᴋᴇʀ Apr 2 '18 at 15:24
\$\begingroup\$ Is the challenge itself going to include a base-level answer to every task, or will the first answer need to come up with 2 commands that are sufficient to solve every task (since no other commands would exist yet) as well as actually making those solutions? \$\endgroup\$ – Kamil Drakari Apr 5 '18 at 15:12
\$\begingroup\$ @KamilDrakari I'm currently working on a (almost finished) base interpreter, which will include a base level solution to each task, which I will post as the first answer. \$\endgroup\$ – caird coinheringaahing Apr 5 '18 at 15:52

| Show 7 more comments

Community · Accepted Answer · 2017-04-13 12:39:25Z

Underwater Survival Game

king-of-the-hill

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.

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

Community · Accepted Answer · 2020-06-17 09:03:53Z

17

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

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

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

_{(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?

edited Jun 17 '20 at 9:03

Community♦

1

answered Jan 14 '16 at 3:04

Rɪᴋᴇʀ

7,50612 silver badges25 bronze badges

\$\begingroup\$ Some images failing and succeeding the test would be cool \$\endgroup\$ – Quill Jan 14 '16 at 3:07
\$\begingroup\$ I know, working on test cases. Will do tomorrow. \$\endgroup\$ – Rɪᴋᴇʀ Jan 14 '16 at 3:08
1

\$\begingroup\$ 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? \$\endgroup\$ – user81655 Jan 14 '16 at 12:27
\$\begingroup\$ 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" />) \$\endgroup\$ – J Atkin Feb 12 '16 at 0:38
\$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ famous last words "will do tomorrow" lol \$\endgroup\$ – Rohan Jhunjhunwala Jul 13 '16 at 20:45
\$\begingroup\$ @RohanJhunjhunwala ....oops. >_> I need code to generate the test cases, haven't written it. \$\endgroup\$ – Rɪᴋᴇʀ Jul 16 '16 at 18:11
\$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ haha \$\endgroup\$ – Rohan Jhunjhunwala Jul 16 '16 at 18:26
\$\begingroup\$ @EasterlyIrk Perhaps it will magically do itself in 6 to 8 weeks! :-) \$\endgroup\$ – wizzwizz4 Oct 28 '16 at 13:05
\$\begingroup\$ You going to post this riker? \$\endgroup\$ – Christopher Jul 10 '17 at 9:41
\$\begingroup\$ Is this ever going to get posted? \$\endgroup\$ – MD XF Aug 5 '17 at 1:42
\$\begingroup\$ @MDXF yes, but it's not going to be soon. \$\endgroup\$ – Rɪᴋᴇʀ Aug 5 '17 at 12:03
\$\begingroup\$ @Rɪᴋᴇʀ 2 yrs later... \$\endgroup\$ – Artemis Apr 1 '19 at 22:30
2

\$\begingroup\$ @ArtemisFowl hush, I'll do it eventually™... \$\endgroup\$ – Rɪᴋᴇʀ Apr 2 '19 at 3:07

Add a comment |

Conor O'Brien · Accepted Answer · 2018-06-30 03:18:12Z

10-character golfing language

language-design test-battery

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

The first row has N /s.
The second row has N - 1 /s.
...
The second-to-last row has 2 /s.
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 quine 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 '18 at 12:51
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 '18 at 14:33
@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 '18 at 20:03
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 '18 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 '18 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 '18 at 4:51
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 '18 at 16:59
rand=lambda seed: 4 #guaranteed to be random (please define random) — Jo King♦, Jun 29 '18 at 14:56
@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 '18 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 '18 at 18:10
So 6 if seed>5 else seed+1 is valid? Random doesn't mean uniformly by default — Jo King♦, Jun 30 '18 at 0:13
Suggestion: A challenge mixing string and number input, e.g. repeat this string N times — Jo King♦, Jun 30 '18 at 2:33

migimaru · Accepted Answer · 2011-08-17 12:50:46Z

15

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?

answered Aug 17 '11 at 12:50

migimaru

1,0705 silver badges4 bronze badges

\$\begingroup\$ 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]? \$\endgroup\$ – dmckee --- ex-moderator kitten Aug 17 '11 at 14:24
2

\$\begingroup\$ 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. \$\endgroup\$ – migimaru Aug 17 '11 at 14:28
\$\begingroup\$ 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. \$\endgroup\$ – migimaru Aug 17 '11 at 14:38
\$\begingroup\$ 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"? \$\endgroup\$ – migimaru Aug 18 '11 at 15:02
\$\begingroup\$ 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? \$\endgroup\$ – arrdem Aug 18 '11 at 15:33
\$\begingroup\$ 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. \$\endgroup\$ – migimaru Aug 18 '11 at 15:37
3

\$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Aug 29 '11 at 8:48
\$\begingroup\$ @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. \$\endgroup\$ – migimaru Aug 29 '11 at 14:42
\$\begingroup\$ 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. \$\endgroup\$ – mbomb007 Jun 4 '15 at 22:03
1

\$\begingroup\$ 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. \$\endgroup\$ – Conor O'Brien Oct 19 '15 at 17:45
\$\begingroup\$ 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. \$\endgroup\$ – Qwertiy Apr 22 '16 at 17:41
\$\begingroup\$ 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. \$\endgroup\$ – Heimdall Nov 9 '17 at 18:23

Add a comment |

Kroltan · Accepted Answer · 2014-07-29 13:23:52Z

Global Warming king-of-the-hill

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

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

Movement and positioning

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

Pushing

Your program can issue push commands to any entity within a radius of 1 from you, resulting in you and your target having your speeds changed to point away from eachother and at a given speed. The push speed is directly adjustable, but the direction isn't. Push speed is under the same limitations as a move command, and thus can't be stronger than 1. If two people push the same target at once, the target is pushed in the resultant direction. Pushing will take into account the target's move command, if there was one.

Input

Each round, your program will be invoked from the command line, with a CSV document being passed to its STDIN. The first line of this document provides the current iceberg radius (floating point number) and the amount of remaining competitors (integer)

After this "header", there will be one line for each remaining competitor in the following format (which is on its turn on the format type(variable)):

string(entity id),float(x),float(y),float(velocity x),float(velocity y)

Your entry will always be the first item on the list.

Example input:

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

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

Output

Your program will process the given input and output a ASV (Anything Separated Values) document. A ASV is like a CSV, except everything that doesn't match the regex [.0-9a-z] is considered a separator (even uppercase letters). If your program emits more than 1 line, only the last one is considered.

For movement:

move,float(velocity x),float(velocity y)

For pushing:

push,string(entity id),float(strength)

To do nothing, simply don't output anyting

Where move and push are string literals.

Example:

move,0.0,0.7

or

push,d5e86

The following lines are valid outputs for your program:

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

Detailed Rules and remarks

A list of important points to consider:

You can skip your turn by returning no output, but this will make you keep moving in the direction you ere headed to.
If a competitor loses, it will not show up on the participants list (see below)
A player is considered to fall from the iceberg if their distance from the center is greater than the iceberg's radius.
Entries do not have a physical radius, so they cannot bump on eachother (except for the push command)
You can't know the shrinking rate of the iceberg.

Scoring

A entry's score is the average turns_survived*players/total_turns out of 10 runs. Each run may have a indefinite (but not infinite) amount of turns, until only one competitor survives.

The scores will be periodically maintained here, and 100% up-to-date at INSERT URL

The winner will be chosen at INSERT DATE

Examples in pseudocode

Antisocial - pushes everyone away from him, doesn't care about where he is.

#!/bin/env pseudocode
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
I'm still not entirely sure about the push. What will be the resulting speed? 1? The previous speed, just rotated? In that case, I'd be immune to pushes be standing still. — Martin Ender, Jul 26 '14 at 13:03
@MartinBüttner Good catch on standing still. I guess the push speed would be the average of yours and your target's, in the direction away from you. The idea of not moving at full speed is exactly to minimize push efficiency, but with the average I can't imagine a exploit. — Kroltan, Jul 26 '14 at 13:25
Well you could also minimise its utility by making it more physically correct such that the push is applied to you as well (in the opposite direction)... conservation of momentum and such. Then you could let players choose the push strength, and they'd have to decide how strongly they want to be pushed themselves. — Martin Ender, Jul 26 '14 at 13:32
@MartinBüttner That would be interesting... And less of a warped reality. xD Though I do not intend do make this a completely physics-based challenge, so I guess that the direction will just set to "away from eachother". Plus, these quirks can make a really unexpected playfield. — Kroltan, Jul 26 '14 at 13:51
Yes, I'd leave it at that. It would be a lot more complicated if you made it really physics based, since the velocities wouldn't change so abruptly. So you could just make a push always along the direction connecting the two players, but apply the push to both of them. — Martin Ender, Jul 26 '14 at 13:58
One issue that isn't addressed is what happens to me after I was pushed. If I try to move and one or more people push me, where do I move? What if player A pushes B pushes C pushes A? Also, since you give a speed (but not distance) moved, you should list how much time is simulated between turns (1 second?) — Zaq, Jul 29 '14 at 1:07
@Zaq Totally didn't think about that. If any player is pushed by two people at once, he is stopped. About the speed, the execution will work at 1 speed per turn. Will edit this info into this answer now. — Kroltan, Jul 29 '14 at 2:54
@Kroltan: Do you want to make it conform better to reality by taking the resultant direction (and speed) when a target is pushed by two people, instead of stopping it? It's weird to see that a target being pushed by two people from behind get stopped. But this is your universe, so this is up to you. =) — justhalf, Jul 29 '14 at 6:46
@justhalf I didn't want to do that because I had no idea how to, but i just realized it's dead simple to do. Sum the forces and cap to the max speed — Kroltan, Jul 29 '14 at 13:14
This game (trying to push other players off of a (possibly shrinking) circular iceberg) is one of the modes in the delightful PS1 title Crash Bash. — feersum, Aug 18 '14 at 19:50

Martin Ender · Accepted Answer · 2017-05-13 19:41:51Z

Random Golf of the Day

code-golf random

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

array-manipulation permutations

#2: Numbers from a Normal Distribution

number

#3: Integer Partitions

number combinatorics integer-partitions

#4: The Bertrand Paradox

geometry

#5: Diamond Tilings

ascii-art combinatorics tiling

#6: Roll a d20

geometry abstract-algebra permutations

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

string

#8: Shuffle an infinite list

array-manipulation permutations

Further ideas (still unordered):

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

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

Blue · Accepted Answer · 2017-08-26 17:38:33Z

14

Who needs a GUI anyway?

code-golf ascii-art

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

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!

edited Aug 26 '17 at 17:38

answered Sep 6 '15 at 12:51

Blue

27.6k1 gold badge13 silver badges22 bronze badges

3

\$\begingroup\$ 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? \$\endgroup\$ – ugoren Sep 6 '15 at 14:46
\$\begingroup\$ Updated to answer 1,2,3,5. Answer to 4 upcoming. \$\endgroup\$ – Blue Sep 6 '15 at 15:15
\$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Sep 6 '15 at 17:11
\$\begingroup\$ @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. \$\endgroup\$ – Blue Sep 6 '15 at 18:13
3

\$\begingroup\$ 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. \$\endgroup\$ – Downgoat Sep 7 '15 at 18:39
\$\begingroup\$ 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. \$\endgroup\$ – trichoplax May 3 '16 at 18:43
\$\begingroup\$ @trichoplax currently discussing this in chat \$\endgroup\$ – Blue May 3 '16 at 18:44
\$\begingroup\$ 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" \$\endgroup\$ – trichoplax May 3 '16 at 19:03
\$\begingroup\$ 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. \$\endgroup\$ – trichoplax May 3 '16 at 19:09
\$\begingroup\$ Grammar question - does GUI's need that apostrophe? I'd write GUIs, but I don't know the rules for abbreviations like that \$\endgroup\$ – FlipTack Dec 25 '16 at 16:52
\$\begingroup\$ @Flp.Tkc fixed. I've lost my example program over time now so I'll have to recreate one \$\endgroup\$ – Blue Dec 25 '16 at 16:55
\$\begingroup\$ 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! \$\endgroup\$ – MD XF Aug 18 '17 at 3:28
\$\begingroup\$ @MDXF Ping me tomorrow about it in TNB and I'll post it then :P \$\endgroup\$ – Blue Aug 18 '17 at 7:57

Add a comment |

PhiNotPi · Accepted Answer · 2013-12-25 00:42:11Z

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
"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? — r3mainer, 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.) — user58826, Jun 9 '17 at 15:42

Lynn · Accepted Answer · 2017-01-03 13:51:09Z

13

Which way will the see-saw turn? code-golf

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.

edited Jan 3 '17 at 13:51

answered Jan 1 '17 at 20:54

Lynn

59.7k24 silver badges18 bronze badges

\$\begingroup\$ *consistently. Also, related (but not duplicate) \$\endgroup\$ – Luis Mendo Jan 2 '17 at 1:07
\$\begingroup\$ 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? \$\endgroup\$ – Christoph Jan 3 '17 at 11:08
\$\begingroup\$ I'm sure that O isn't lower case. ;) \$\endgroup\$ – user48538 Jan 3 '17 at 13:36
\$\begingroup\$ @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.) \$\endgroup\$ – Lynn Jan 3 '17 at 13:51
\$\begingroup\$ Hm I wonder of what solution you think :) In the way I'd answer this question there wouldn't be any major difference. \$\endgroup\$ – Christoph Jan 3 '17 at 14:04

Add a comment |

Beefster · Accepted Answer · 2021-05-25 19:05:06Z

The Ever-Changing Labyrinth (Controller WIP)

king-of-the-hill grid maze javascript

Controller • Source • Chat • Submit

This is a 2-player asymmetric KotH challenge.

One player controls a pair of telepathically connected adventurers who are trying to get through a maze.
The other player has the ability to change the maze and tries to keep the adventurers from solving it.

Gameplay

The game is made up of a variable number of rounds, each consisting of up to 1000 turns.

At the beginning of a round, the Maze Master creates an \$n \times n\$ maze, starting at \$n = 3\$, and increasing by \$1\$ on each subsequent round.

Every cell of the maze must always be reachable from every other cell.

Both adventurers begin on the northwest corner cell. The goal is on the southeast corner cell. One adventurer begins facing east and the other begins facing south.

The game proceeds in a turn-based fashion, alternating between each player.

Adventurers:
- Observe surroundings of themself and the other adventurer:
  - The wall directly ahead on the current cell is observed
  - If there is no wall directly ahead on the current cell, every wall is observed along each cell ahead in a straight line until a wall obstructs the adventurer's sight
  - The walls on the left and right of the current cell are observed
  - If there is no wall to the left, the wall ahead on the cell to the left can be observed
  - If there is no wall to the right, the wall ahead on the cell to the right can be observed
  - The relative position of the other adventurer, if present on one of the cells they can see.
- Either moves forward, changes orientation, or waits
The maze master, in order:
- Receives \$ 1 + \lfloor \log_n(t) \rfloor \$ mana (where \$t\$ is the turn number, starting at 1), which can be used to modify the maze
- Observes the entire maze, including the position and orientation of each adventurer
- May remove a wall from anywhere in the maze that is not currently visible to either adventurer
- May add a wall to anywhere in the maze that is not currently visible to either adventurer, provided it does not separate the maze into two unconnected halves.

Illustration of how adventurers observe the maze:

The adventurer in the above image is facing east and sees all the green cells and walls. The dotted green lines indicate non-walls the adventurer can see.

Adventurers may occupy the same space and face different directions. Observation occurs before either of them chooses an action; movement is resolved simultaneously.

The cost to modify the maze increases according to the fibonacci sequence. The first time a particular wall segment is added or removed, it costs 1 mana, the second time costs 1 mana, then 2, 3, 5, 8, 13, 21, 34, 55... Modification cost is independent for each edge of the grid where a wall segment can be placed, so it is more costly to toggle the same wall than it is to toggle different walls each time.

The maze master can stockpile an arbitrarily large amount of mana, but can only change two walls per turn (removing one, then adding one)

The round continues until either of the two adventurers reaches the goal cell, at which point, the game will continue onto the next round.

If neither reaches the goal after 1000 turns, then the maze master wins and the game ends.

The maze master does not carry over mana between rounds.

Coding

Both players may retain as much information as they wish for the entire duration of the game. State may carry on from one round to the next.
State and retained information will not be remembered between games.
Players will not be able to access the state of the other player.
Each player will receive an isolated RNG state at the beginning of each game. To ensure that all games have the same outcome with a given seed, all non-deterministic behavior must use the provided RNG. (Math.random is overridden for each bot, just in case)
Each bot is allotted 50ms of CPU time at the beginning of the round and 1ms for each turn. Exceeding this allotment will result in a strike.
Maze generation has a time limit of \$n^2\$ ms. (i.e. 9ms for the \$3 \times 3\$ maze, 16ms for the \$4 \times 4\$ maze, 25ms for \$5 \times 5\$, and so forth.)
Adventurers are given 10ms to set up state between rounds. Exceeding this time limit results in a strike.
Generating an illegal maze will result in a strike.
If a wall added to the maze divides the maze into two unconnected halves, the maze master will receive a strike.
If a wall to be added or removed is visible by either adventurer, the wall will not change but the mana will still be spent.
If the maze master does not have enough mana to perform both of its requested actions, its actions will be ignored.
If the maze master specifies the same wall for both removing and adding, the actions will be ignored.
If the maze master tries to remove a wall that is already missing or add a wall that is already present, the relevant action will be ignored.
Illegal adventurer moves will be treated the same as a wait action.
If a bot gets a strike, the game will be thrown out of the tournament as an outlier. If any particular bot gets 3 strikes during the tournament, it will be disqualified, and all the matches it was a part of will be discarded and ignored.
Submissions may not attempt to exploit bugs in the controller in order to break other rules.
Submissions must be compatible with being run inside web workers as well as being run in the foreground.
Submissions may not call any asynchronous functions (usually I/O)

Adventurers Interface

Your submission must define the body of a function which receives a single argument (random, a function that returns a pseudorandom number between 0 and 1) returns an object with the following interface:

startRound(mazeSize: number)
takeTurn(vision: [Vision, Vision]) -> [number, number]

takeTurn should return a pair of integers describing the action taken by each adventurer. Actions are defined as follows:

const ACTION = {
    WAIT: 0,
    FORWARD: 1,
    TURN_RIGHT: 2,
    TURN_AROUND: 3,
    TURN_LEFT: 4,
}

Vision is defined as an object with this schema

{
    ahead: [
        {
            ahead: true | false,
            left: true | false,
            right: true | false,
        }
        ...
    ],
    leftAhead:  true | false | null,
    rightAhead: true | false | null,
    friend: [number, number] | null
}

The zeroth element of the ahead array represents the current cell the adventurer is on, and each subsequent element represents the next cell ahead.

null means that wall cannot be seen, so it is uncertain whether it is present or not.

friend will be an ordered pair of numbers representing the number of cells ahead and the number of cells to the right (will be -1 when the other adventurer is to the left) that the other adventurer is relative to this one. If the other adventurer is not visible, friend will be null

Maze Master Interface

Your submission must define the body of a function which receives a single argument (random, a function that returns a pseudorandom number between 0 and 1) returns an object with the following interface:

generateMaze(mazeSize: number) -> Maze
takeTurn(mana: number, maze: Maze) -> [WallCoord | null, WallCoord | null]

generateMaze should return a row-major array of arrays of objects that describe the east and south walls of the cell. Each cell must have the following schema:

{
    east: boolean | null // will be null along the east edge of the maze
    south: boolean | null // will be null along the south edge of the maze
}

takeTurn should return a pair of wall coordinates, describing the wall to remove and the wall to add. Both coordinates are optional and may be null or undefined. Wall coordinates should be an array of the row, column, and 'south' or 'east' representing the location of the wall. The schema is as follows:

[number, number, 'south'|'east']

The maze provided to takeTurn is similar to the maze expected to be returned by generateMaze, but with two additional properties on each cell to define the mana cost to update:

{
    eastCost: number
    southCost: number
}

Submission Format

In order to aid answer scraping, please format your submissions in the following format:

# <submission type>: <name>

Optional blurb

    // relevant functions, constants, variables go here

    return /* the object */

Description/explanation of how the bot works + whatever you want

<submission type> must be the exact string of either Adventurers or Maze Master which corresponds to your submission type

Only the first code block of your post will be scraped. Submissions will be loaded as if they are the body of a function, which is executed once with no arguments. Submission names should be different from any other submissions.

You may submit both an adventurer bot and a maze master bot, each in its own post. You may also submit multiple bots of the same type as long as they are reasonably different from each other. Please don't hog the leaderboard with near-identical bots.

Scoring and The Tournament

Adventurers compete only with other adventurers, and the same goes for maze masters.

The overall score for a game for both roles is 1000 points per maze completed by the adventurers minus the number of turns taken in total. Score can go negative.

Each adventurer bot will play against each opposing maze master bot an equal number of times until the ranking of the top 5 bots for each role are established with 95% confidence. The overall tournament score for a given bot is averaged across all games that bot played in the tournament.

The adventurer bot with the highest score wins.

The maze master bot with the lowest score wins.

Scores will be updated when a adventurer or maze master is added or updated.

king-of-the-hill grid maze javascript

Pull requests welcome on the controller. Vanilla JS only (Current ES standard is fine), preferably, though jQuery is probably ok. It needs to work on GitHub pages in Firefox and Chrome without needing babel or webpack or similar.

Parts still in need of implementation:

Fix bugs in Maze Master modification handling (there are certain cases where visibility is not respected properly)
Code scraper
Tournament controller
Better syntax error reporting for bots
Foreground error reporting for bots (instead of tucking it away in dev tools)
(nice-to-have, preferably before posting to main) improved renderer that shows visible cells and walls and the effects of the last move (or better yet, changes since last render).
(nice-to-have, can wait until after posting to main) background game runner that runs in a web worker and can be controlled by the tournament controller

I recommend checking in via the chat room to avoid duplicating work.

Beta bot submissions also welcome, though I'm not sure how these are going to be integrated at the moment.

Assumes that the maze master will only wait if the adventurer waits, would that always make waiting a bad choice for the adventurer? — user202729, Aug 7 '20 at 1:19
@user202729 waiting is probably never a good idea for the adventurer, yes, and linear. — Beefster, Aug 7 '20 at 5:16
Would the score of every maze master change whenever an adventurer program is posted, and vice versa? — user202729, Aug 7 '20 at 5:31
Perhaps "if the game doesn't terminate after X turns then the score will be X", with X large enough such that the optimal adventurer can always achieve a score smaller than X (but small enough so it's practical to compute) — user202729, Aug 7 '20 at 5:34
Regarding language: if the challenger is implemented in some language that can invoke other programs (such as JavaScript (Node.js)), then it's possible to communicate over standard input/output and let people submit in any language. — user202729, Aug 7 '20 at 5:34
@user202729 A couple reasons why I probably won't communicate over stdin/stdout: 1. it can be tricky to avoid deadlock; 2. I want the challenge to be accessible to many users without requiring them to download additional language runtimes. — Beefster, Aug 7 '20 at 15:54
So the observed information would be [number of free cells to the left, number of free cells to the right, number of free cells in front]? — user202729, Aug 8 '20 at 0:37
"The behavior must be deterministic with a fixed RNG"? (I'm not sure how to phrase this.) — user202729, Aug 8 '20 at 0:43
There exists a maze master algorithm that makes the duration O(n^4) moves regardless of the adventurer algorithm, where n is the side length. — user202729, Aug 8 '20 at 0:49
And I believe that asymptotically it's not possible to do better. — user202729, Aug 8 '20 at 0:50
Here are a couple more ideas that buff the adventurer: a) randomly generated initial maze (might make the game too stale), b) mana costs are 2 ** n instead of n + 1 (personal favorite), c) 2 adventurers, and only 1 has to reach the exit, d) adventurer can move perpendicular to the direction they're facing, e) adventurer can move any number of cells forward in a turn. I don't know how any of these affect the problem, though, as I haven't yet had time to sit down and analyze it. — Alion, Aug 19 '20 at 22:30

Thomas Baruchel · Accepted Answer · 2014-03-26 05:30:53Z

Thinking functionally (1): removing variables

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

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

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

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

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

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

a = 256

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

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

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

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

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

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

You probably need to say something about scope (to rule out the argument that the first example actually has three variables: a, x, and the other x) and bit packing (since Minsky proved that it's possible to have a Turing-complete system with only two variables using Gödel numbering, and it can be argued that every Fractran program uses only one variable). — Peter Taylor, Mar 25 '14 at 22:29
@Peter Taylor. Thank you for your comment. I do it for the x in lambda functions. For the second remark, it is also true, but since it is a popularity contest and since creativity is encouraged, is it absolutely necessary to be too precise regarding how the data has to be stored? — 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. — user58826, Jun 9 '17 at 16:29

yo' · Accepted Answer · 2014-06-09 14:22:59Z

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.

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
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. — user58826, Jun 9 '17 at 16:52

PhiNotPi · Accepted Answer · 2016-11-26 02:01:13Z

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

Community · Accepted Answer · 2017-04-13 12:19:20Z

Prime Spiral

primes code-golf graphical-output

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)

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

Nathan Wood · Accepted Answer · 2018-04-04 09:35:23Z

ASCII Line Extender

code-golf ascii-art

Introduction

I have an ASCII grid of size 10x10

+--------+
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
+--------+

Occasionally, slashes and Xs pop up, but they're too small for me to see!

+--------+
|        |
|      X |
|  \     |
|        |
|        |
| /   /  |
|        |
|        |
+--------+

I need a program that can extend them so that I know where they are

\----\--//
|\    \//|
| \   /X |
|  \ // \/
|   X/  /\
|  //\ / |
| //  X  |
|//  / \ |
//  /   \|
/--/-----\

Challenge

Your task is to create a function or a program that can take in a String of a grid lines separated by \n and outputs grid lines separated by \n (optionally including a trailing newline). When there is a \ or a /, your program must add slashes diagonally until you reach both ends so that the slashes look like a line. Whenever two lines intersect, you must replace them with X. If given an X, you must extend in both diagonal directions. You can assume that no lines have already be extended. and you can assume the border is intact. Standard I/O format applies.

Test cases

These test cases do not contain a trailing newline, due to limitations, however you should add them when testing.

Test for overlap

+--------+
|        |
|        |
|  \     |
|        |
|        |
| /   /  |
|        |
|        |
+--------+

\-------/+
|\     / |
| \   /  |
|  \ /   /
|   X   /|
|  / \ / |
| /   X  |
|/   / \ |
/   /   \|
+--/-----\

Test for Xs

+--------+
|    X   |
| X      |
|        |
|        |
|        |
|    X   |
|        |
|        |
+--------+

\---X-/--+
\\ / X   |
|\X / \  /
|/\X   \/|
/ /\\  /\|
|/  \\/  \
/    X\  |
|   / \\ |
|  /   \\|
+-/-----\\

Test for X and avoiding

+--------+
|        |
|   \    |
|        |
|        |
|  /     |
|  /     |
|        |
|        |
+--------+

+-\-----//
|  \   //|
|   \ // |
|    X/  |
|   //\  |
|  //  \ |
| //    \|
|//      \
//       |
/--------+

Test for slashes in the same row

+--------+
|        |
|   \    |
|        |
|     \  |
|        |
|  /     |
|        |
|X       |
+--------+

+-\------/
|  \    /|
|   \  / |
|    \/  |
|    /\  |
|   /  \ |
|  /    \|
\ /      \
|X       |
/-\------+

Test for lots of lines

+--------+
|  /     |
|   \  / |
| \      |
|      \ |
|  /     |
|     X  |
|        |
| /      |
+--------+

\-\\/---//
\\ X\  ///
|\X \\///|
|/\\ XX/ /
/  \X/X\/|
|  /XX X\|
| ///\X \\
|/// /\\ \
/// /  \\|
//-/----\\

Test for empty grid

+--------+
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
+--------+

+--------+
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
+--------+

Scoring

This is code-golf, so the code with the shortest number of bytes wins!

I think something is wrong with the second test case, the arms of one of the Xs are extended in one direction but not the other. Also, this challenge needs a proper spec, i.e. you should describe exactly how the program should behave, rather than just giving examples. — Nathaniel, Apr 3 '18 at 6:32
Suggest testcase XXXXXXXXXX\nX________X\nX________X\nX________X\nX________X\nX________X\nX________X\nX________X\nX________X\nXXXXXXXXXX (_ for space) — tsh, Apr 4 '18 at 8:08
@tsh Is that an empty grid (because it's of size 10x10) or is it a grid that is bordered by Xs? — Nathan Wood, Apr 4 '18 at 9:36
@NathanWood All borders are filled with X. Output should be 10 line of 10 Xs. — tsh, Apr 4 '18 at 9:53

score 11 · Accepted Answer · 2014-06-05 07:23:54Z

11

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 popularity-contest. 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.

edited Jun 5 '14 at 7:23

answered May 25 '14 at 12:03

user16402

\$\begingroup\$ 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. \$\endgroup\$ – Martin Ender May 28 '14 at 16:24
\$\begingroup\$ @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 \$\endgroup\$ – user16402 May 29 '14 at 8:47
\$\begingroup\$ 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? \$\endgroup\$ – trichoplax Jun 4 '14 at 20:02
\$\begingroup\$ @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) \$\endgroup\$ – user16402 Jun 5 '14 at 7:22
\$\begingroup\$ 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? \$\endgroup\$ – trichoplax Jun 5 '14 at 12:17
\$\begingroup\$ @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 ...? \$\endgroup\$ – user16402 Jun 5 '14 at 13:18
\$\begingroup\$ 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... \$\endgroup\$ – trichoplax Jun 5 '14 at 17:20
\$\begingroup\$ @githubphagocyte if someone could implement simple multi-celled creatures, that would be amazng \$\endgroup\$ – user16402 Jun 5 '14 at 17:45
\$\begingroup\$ 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? \$\endgroup\$ – kitcar2000 Jun 5 '14 at 20:52
1

\$\begingroup\$ 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? \$\endgroup\$ – trichoplax Jun 7 '14 at 1:35
\$\begingroup\$ 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). \$\endgroup\$ – trichoplax Jun 7 '14 at 1:41
\$\begingroup\$ 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 \$\endgroup\$ – trichoplax Jun 10 '14 at 17:12
\$\begingroup\$ @professorfish "Evolution of Regular Geometries"? \$\endgroup\$ – Patrick Roberts Jun 27 '16 at 3:41
\$\begingroup\$ 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. \$\endgroup\$ – user58826 Jun 9 '17 at 16:48

Add a comment |

PhiNotPi · Accepted Answer · 2015-03-15 17:28:15Z

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

\$\begingroup\$ would this be code-golf? \$\endgroup\$ – TheDoctor Oct 24 '15 at 20:40 — TheDoctor, Oct 24 '15 at 20:40
\$\begingroup\$ Do you ever plan to post this? \$\endgroup\$ – MD XF May 31 '17 at 21:49 — MD XF, May 31 '17 at 21:49

El'endia Starman · Accepted Answer · 2015-12-01 09:10:07Z

10

N-Player Battleship

king-of-the-hill

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.

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!

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
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 '18 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 '18 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 '18 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 '18 at 4:14
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 '18 at 18:42
@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 '18 at 19:16

Community · Accepted Answer · 2017-04-13 12:32:32Z

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.

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 --- ex-moderator kitten, May 28 '11 at 22:35
You should drop the complexity test, and worry about brute force. Just give an example big enough that brute force won't work. With this kind of problem, it should easy enough to give such a maze. — MtnViewMark, Jun 1 '11 at 6:49

PhiNotPi · Accepted Answer · 2014-08-11 12:43:25Z

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 king-of-the-hill 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.

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

score 9 · Accepted Answer · 2014-09-02 10:44:35Z

Transport Tycoon [control program WIP] king-of-the-hill game

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

Chatroom for this challenge

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

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

Control

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

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

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

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

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

Map format

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

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

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

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

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

Construction

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

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

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

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

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

B-X-Y-tile

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

B-8-4-#

Invalid commands will be ignored.

Vehicles

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

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

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

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

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

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

P-id-X-Y-upgrades

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

P-5-7-7-

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

V-id

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

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

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

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

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

/////
##*//
/*###
/////

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

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

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

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

Passengers

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

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

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

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

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

Other

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

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

You will start with $32768.

You may not have a negative quantity of money.

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

The map will be 256*256 tiles.

Todo

Write control program
Write map generator
Plan tournament format

check out dinopoloclub.com/minimetro for a minimalistic transport network game that might be amenable to computer solution — Sparr, Aug 11 '14 at 13:39
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
@SohamChowdhury I'm working on it.... one day I'll finish it — user16402, Sep 16 '14 at 10:31

Community · Accepted Answer · 2020-06-17 09:03:53Z

Overhanded (Underhanded) Poker

king-of-the-hill overhanded card-games

Also if you make overhanded 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

Sandbox for Proposed Challenges

Posting

Discussion

Other

3361 Answers 3361

Count the pips in a pair of dice

Waving Hands bot

Conquer the Solar System

The Setting

The Model

Gameplay

Combat System

Implementation

Further Design Decisions

King of the Hill- Simple RPG

The Rules of the Game

The Board

Mechanics

Combat

Special Attacks

Monsters

Attributes

Implementation

Winning Condition

DTMF Decoder

Anarchist chess

Build a golfing language with me

Underwater Survival Game

The Arena

The Game

The Species

The Hazards

The Fights

Sandbox notes

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

Sandbox notes:

10-character golfing language

Design and Implementation rules

Winning

The Challenges

1: Greetings, Humans!

2: Even cats

3: Do the wave

4: Quine

5: Coprimality

6: Ternary

7: Word value sum

8: Shutters

9: Roll a die

10: Where am I walking?

11: Reproduction

12: Product

13: Sort a string

14: Repeat indexing

Self-Golfing Code

Global Warming king-of-the-hill

Movement and positioning

Pushing

Input

Output

Detailed Rules and remarks

Scoring

Examples in pseudocode

Random Golf of the Day

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

Who needs a GUI anyway?

Your task:

Challenge

Example

Digital Music Box

Input