572
\$\begingroup\$

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 requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

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

\$\endgroup\$
0

4643 Answers 4643

1
2 3 4 5
155
56
\$\begingroup\$

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

Count the pips in a pair of dice

👉 Moved here

\$\endgroup\$
17
  • 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\$ Jan 9, 2015 at 11:20
  • \$\begingroup\$ (b) Maybe you could post your script in addition. \$\endgroup\$ Jan 9, 2015 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, 2015 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, 2015 at 20:15
  • \$\begingroup\$ @squeamishossifrage I meant so that people can generate more test cases if 100 isn't enough. \$\endgroup\$ Jan 9, 2015 at 22:10
  • 2
    \$\begingroup\$ You could post 1000 cases and then announce the subset of 100 that will be used for scoring. \$\endgroup\$ Jan 12, 2015 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\$ Jan 12, 2015 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\$ Jan 12, 2015 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, 2015 at 10:34
  • \$\begingroup\$ Ooo... a clustering algorithm question, this I like +1. \$\endgroup\$ Sep 23, 2016 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\$ Nov 3, 2016 at 18:48
  • \$\begingroup\$ Seems like a perceptron could do the trick \$\endgroup\$ Jun 14, 2017 at 17:13
  • \$\begingroup\$ See also: markfickett.com/stuff/artPage.php?id=389 \$\endgroup\$
    – asmaier
    Apr 25, 2018 at 14:55
  • \$\begingroup\$ and: dropbox.com/s/buyg5swn0o0und2/SnakeEyesFinalPres.pptx?dl=0# \$\endgroup\$
    – asmaier
    Apr 25, 2018 at 15:06
  • \$\begingroup\$ Do you know about the Secret Santa's Box? \$\endgroup\$
    – DELETE_ME
    Jun 26, 2018 at 16:22
36
\$\begingroup\$

Waving Hands bot

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


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

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

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

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

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

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

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

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


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

\$\endgroup\$
14
  • \$\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, 2014 at 14:07
  • 2
    \$\begingroup\$ @Geobits, I believe in updating the accepted answer when a better answer comes along. \$\endgroup\$ Apr 9, 2014 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, 2014 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, 2014 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\$ Jul 30, 2014 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\$ Aug 17, 2014 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\$ Sep 4, 2014 at 12:06
  • \$\begingroup\$ Should a bot be eliminated from the rest of a tournament if it dies? \$\endgroup\$ Jan 13, 2015 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\$ Jan 13, 2015 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, 2017 at 20:10
  • \$\begingroup\$ @mbomb007, I'm not sure what other winning criterion that variant could use. \$\endgroup\$ Oct 9, 2017 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, 2017 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\$ Oct 9, 2017 at 21:16
  • \$\begingroup\$ Then just make it so the first solution wins. \$\endgroup\$
    – mbomb007
    Oct 10, 2017 at 13:23
30
\$\begingroup\$

Conquer the Solar System

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

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

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

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

The Setting

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

The Model

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

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

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

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

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

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

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

Gameplay

  • Each player starts with a base on a random body. The remaining bodies will be uninhabited.
  • Each player starts with one flagship, and n fighters (where n needs to be determined, but I'm thinking on the order of 10) – collectively referred to as units.
  • Players write a bot that is asked for a move whenever one of their own units is idle or needs to act, because it's being attacked or similar.
  • Fighters are a lot faster than flagships, so they will act as scouts as well, to avoid time-wasting travel with the flagship.
  • Flagships can build new bases on uninhabited bodies, or take over enemy bases (the former taking longer than the latter).
  • Each additional base immediately grants another n fighters.
  • Each base regularly spawns new fighters (say, once a week). If a player controls an entire planet system (the planet and all satellites), the spawn rate on all bodies in that system is increased (to, say, once every five days).
  • Flagships are vulnerable while working on bases. Either they can't interrupt the building process upon arrival of enemies, or such an interruption will cause the total build time to increase.
  • Upon landing on a body, units can't leave immediately. They need to remain for p % of the time it took to get there (p ≈ 10?) in order to refuel. Technically, this is to prevent units from hiding all the time in interplanetary space. (formula subject to change)
  • If there are units from multiple players on a body, they may engage in combat (see next section for details on combat).
  • If a player's flagship is defeated they immediately lose the game! All their units and bases go over to the player who killed the flagship.
  • The bot may always decide to wait idly (I'll set a minimum on this, to prevent bots from spamming the control program with millisecond waits). Waiting will be interrupted by any relevant event like allies or enemies arriving somewhere.

Combat System

  • Fights are carried similar to the rules of Risk. Please refer to the Wikipedia page or the internet for the exact rules for now – all necessary rules will be part of the final challenge post though.
  • Attackers may choose to attack with 1 to 3 units, defenders choose to defend with 1 or 2 units. The outcome is determined by rolling dice. After each round of battle, battle may either continue with the remaining units or be aborted.
  • One round of combat takes 1 day. (subject to change)
  • Whether a player is attacker or defender depends on whether he has a base on the current body. This means that two attackers could be fighting each other on an unclaimed body, in which case both may use 3 units in a fight, but units from both sides die in a tie.
  • If a player has a flagship on the body where the fight takes place, one unit will roll a d8 instead of a d6, unless they are currently working on a base (building one or converting one).
  • When players lose units, they always lose fighters first. Hence, if a player has a flagship on a planet, and loses less than all of his units, the flagship will remain.

Implementation

I will either go with Rusher's approach of writing a Java controller where participants only need to implement an interface (and provide a wrapper for non-Java submissions) or I'll write a controller that invokes bots as separate processes whenever its their turn.

On their turn, each bot will be provided with

  • the current time
  • the number of bases and units controlled by each player
  • the state of all bodies the player currently has units or bases on
  • the ID and location of the idle unit(s) that can currently perform an action
  • a list of all bodies with their current positions (in Cartesian coordinates, so distances can easily be determined)
    • potentially I'll just provide a list of travel times for each idle unit instead, to save the bots the need to compute those
  • a list of all bodies with their current angular positions

The latter can safely be ignored, but is provided for bots that want to predict planetary motion to take shortcuts. Static numerical data like orbital radii and periods will not be provided to the bots, but I'll publish a table with the challenge to be hardcoded into the bots if desired.

Further Design Decisions

I realise that there is a lot of complexity in this. This is why I need your help to refine the concept and remove unnecessary details while keeping the heart of the challenge in tact (while making sure the rules are consistent). Please give me all the feedback you can think of, but here are a few particular questions I have in mind that need to be answered:

  • How should vulnerability during base-building be modelled? By penalising or by disallowing interruptions?
  • How can fights between more than two parties be handled?
  • Is the "refuelling" necessary/useful? Do the details for it need work?

In any case, I don't doubt this challenge will remain fairly complex when finalised. It might help to gather some momentum if a few heroes volunteered up front to submit a bot to this - ideally ones which show that the entry barrier doesn't need to be as high as it looks.

Anyway, thanks a lot for reading this and helping out with the design of this challenge!

I'm happy to discuss details in chat (The Nineteenth Byte or Golf/Puzzle Lab; but ping me so I know you've posted there) or just here, but this challenge may need more discussion than fits in comments.

\$\endgroup\$
22
  • \$\begingroup\$ 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". \$\endgroup\$
    – Rainbolt
    May 25, 2014 at 4:20
  • \$\begingroup\$ 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? \$\endgroup\$
    – ProgramFOX
    Jun 3, 2014 at 17:33
  • \$\begingroup\$ @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. \$\endgroup\$ Jun 3, 2014 at 17:38
  • \$\begingroup\$ @ProgramFOX edited the draft \$\endgroup\$ Jun 3, 2014 at 20:34
  • \$\begingroup\$ @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. \$\endgroup\$ Jun 4, 2014 at 20:04
  • \$\begingroup\$ "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. \$\endgroup\$ Jun 13, 2014 at 22:51
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 13, 2014 at 22:52
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 13, 2014 at 22:53
  • \$\begingroup\$ @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. \$\endgroup\$ Jun 14, 2014 at 10:49
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 14, 2014 at 10:54
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 14, 2014 at 10:58
  • \$\begingroup\$ 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! \$\endgroup\$ Jun 14, 2014 at 10:59
  • \$\begingroup\$ 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. \$\endgroup\$
    – Kyle Kanos
    Jul 2, 2014 at 2:31
  • \$\begingroup\$ @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.) \$\endgroup\$ Jul 2, 2014 at 7:52
  • \$\begingroup\$ 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? \$\endgroup\$
    – James_pic
    Jul 4, 2014 at 13:38
24
\$\begingroup\$

King of the Hill- Simple RPG

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

The Rules of the Game

The Board

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

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

Mechanics

Each turn, a player can:

  1. Move: you can move north, east, west, or south, or not move at all. Attempting to move into an obstacle, or off the edge of the board, will result in you not moving at all.
  2. Perform a special attack: you can either perform a ranged attack, an area attack, or no special attack at all.
  3. Battle: if you encounter an enemy, you can fight them.

Combat

Whenever you enter a square that is already occupied by a monster or another player, you fight them. You and your opponent take turns attacking each other, with the first move being decided randomly. At any point in the combat, you may flee. Also, once per battle, you may use a special attack which does double damage.

Damage is calculated using this formula:

Damage = Attacker's attack modifier + Random number from 1 to 5 - Defender's defence modifier

Special Attacks

There are two special attacks: A ranged attack, that targets any enemy within 5 squares, and an area attack, that targets all enemies within 2 squares. Damage is calculated using the same formula as for melee damage.

Monsters

In the game, there are 5 monsters:

  1. Goblin. Attack: 1; Defence: 1; HP: 1; moves randomly; 1XP for killing.
  2. Orc: Attack: 3; Defence: 2; HP: 5; follows players; 5XP for killing.
  3. Troll: Attack: 5; Defence: 2; HP: 10; moves randomly; 10XP for killing.
  4. Giant: Attack: 10; Defence: 5; HP: 15; follows players; 50XP for killing.
  5. Dragon: Attack: 20; Defence: 10; HP: 20; follows players; 100XP for killing.

If you kill another player, you receive 100XP.

Attributes

When you create your bot, you must give it 5 attributes. They are:

  • Attack: your attack bonus when using a melee attack.
  • Ranged Attack: your attack bonus when using a ranged attack.
  • Area Attack: your attack bonus when using an area attack.
  • Defence: your defence bonus.
  • Constitution: added to your HP (10 by default). Note: If your bot's constitution is -10, it dies immediately.

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

Implementation

public class MyBot extends RpgBot
{
    public static final int ATTACK = <insert here>;
    public static final int RANGED_ATTACK = <insert here>;
    public static final int AREA_ATTACK = <insert here>;
    public static final int DEFENCE = <insert here>;
    public static final int CONSTITUTION = <insert here>;
    // you can add something here
    public MyBot() { super(); }
    public Move move() {
        // insert here: return either Move.NORTH, Move.EAST,
        // Move.WEST, Move.SOUTH, or Move.NO_MOVE.
    }
    public SpecialAttack makeSpecialAttack() {
        // insert here: return either SpecialAttack.RANGED,
        // SpecialAttack.AREA, or SpecialAttack.NONE.
        // For ranged attacks, use setTargetX() and setTargetY()
        // to set the target beforehand.
    }
    public Attack attack(Entity m) {
        // insert here: return either Attack.NORMAL,
        // Attack.SPECIAL, or Attack.FLEE.
        // Entity m is one of the monster entities.
    }
}

Here are the additional functions you get for your convenience:

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

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

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

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

Winning Condition

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

\$\endgroup\$
14
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 15, 2014 at 8:41
  • \$\begingroup\$ @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. \$\endgroup\$
    – Alex
    Jun 15, 2014 at 13:06
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 15, 2014 at 13:23
  • \$\begingroup\$ 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? \$\endgroup\$ Jun 18, 2014 at 0:48
  • \$\begingroup\$ @githubphagocyte Yes, they will only know what is visible. \$\endgroup\$
    – Alex
    Jun 18, 2014 at 18:48
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Nov 19, 2014 at 0:13
  • \$\begingroup\$ @archaephyrryx So do you think disallowing stats above +20 would be a good idea in that case? \$\endgroup\$
    – Alex
    Nov 23, 2014 at 23:50
  • \$\begingroup\$ 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. \$\endgroup\$ Nov 25, 2014 at 15:45
  • \$\begingroup\$ @Alex Are you still developing this? \$\endgroup\$ Mar 6, 2015 at 10:22
  • 1
    \$\begingroup\$ @Manu Yes, but I haven't been able to work on it for a rather long while. \$\endgroup\$
    – Alex
    Mar 6, 2015 at 22:33
  • \$\begingroup\$ @Alex Cool, looking forward to the challenge:) \$\endgroup\$ Mar 7, 2015 at 8:03
  • \$\begingroup\$ I'd enjoy this o.o \$\endgroup\$ Aug 2, 2015 at 18:05
  • \$\begingroup\$ Are you still developing this? \$\endgroup\$
    – user58826
    Jun 9, 2017 at 16:53
  • 1
    \$\begingroup\$ @Alex Are you still working on this? \$\endgroup\$
    – Gryphon
    Oct 13, 2017 at 17:27
20
\$\begingroup\$

Build a golfing language with me

\$\endgroup\$
22
  • 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, 2018 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, 2018 at 14:41
  • \$\begingroup\$ Added simple descriptions for the rest of the challenges. \$\endgroup\$
    – Bubbler
    Mar 20, 2018 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\$
    – N. Virgo
    Mar 22, 2018 at 13:43
  • 7
    \$\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\$
    – N. Virgo
    Mar 22, 2018 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\$ Mar 22, 2018 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, 2018 at 21:43
  • \$\begingroup\$ @dylnan Challenges must have a winner to be on-topic \$\endgroup\$ Mar 22, 2018 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, 2018 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\$
    – N. Virgo
    Mar 23, 2018 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\$
    – N. Virgo
    Mar 23, 2018 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 Mod
    Mar 26, 2018 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\$
    – Riker
    Apr 2, 2018 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\$ Apr 5, 2018 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\$ Apr 5, 2018 at 15:52
19
\$\begingroup\$

DTMF Decoder

(?)


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

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

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

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

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

DTMF Table

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

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


\$\endgroup\$
5
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ Oct 18, 2014 at 0:15
  • \$\begingroup\$ @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? \$\endgroup\$
    – Nick T
    Oct 18, 2014 at 0:17
  • \$\begingroup\$ 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. \$\endgroup\$ Oct 18, 2014 at 0:20
  • \$\begingroup\$ @MartinBüttner fleshed it in a bit more as a challenge, see anything awful? \$\endgroup\$
    – Nick T
    Oct 18, 2014 at 8:53
  • \$\begingroup\$ @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. \$\endgroup\$
    – Nick T
    Jun 13, 2017 at 15:13
19
\$\begingroup\$

Anarchist chess

Initial position

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

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

This is an example of an impartial game.

\$\endgroup\$
9
  • 3
    \$\begingroup\$ The space of valid positions seems rather small. Is this not a solved game? \$\endgroup\$ Feb 5, 2016 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, 2016 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\$ Feb 5, 2016 at 23:00
  • \$\begingroup\$ So it's only one set of pawns and they can capture each other? \$\endgroup\$ Feb 6, 2016 at 13:53
  • \$\begingroup\$ @PeterTaylor Yes. \$\endgroup\$
    – feersum
    Feb 6, 2016 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\$ Feb 6, 2016 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\$ Aug 13, 2016 at 14:18
  • 3
    \$\begingroup\$ @GeorgeV.Williams Good observation... so for a tournament only odd-sized boards should be considered. \$\endgroup\$
    – feersum
    Aug 14, 2016 at 2:51
  • 4
    \$\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\$ Aug 15, 2016 at 3:31
18
\$\begingroup\$

Underwater Survival Game

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

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

The Arena

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

enter image description here

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

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

The Game

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

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

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

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

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

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

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

The Species

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

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

The Hazards

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

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

N     N
NN   NN
 NNNNN
  NNN

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

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

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

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

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

The Fights

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

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

Sandbox notes

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

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

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

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

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

10-character golfing language

{{{rewriting}}}

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

Design and Implementation rules

Your language should have the following characteristics:

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

Winning

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

The Challenges

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

1: Greetings, Humans!

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

Example Output:

Greetings, Humans!

2: Even cats

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

Example Input:

Hello, World!

Example Output 1:

Hlo ol!

Example Output 2:

el,Wrd

3: Do the wave

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

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

4: Quine

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

5: Coprimality

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

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

6: Ternary

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

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

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

7: Word value sum

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

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

8: Shutters

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

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

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

input
output

1
/

2
//
/

3
///
//
/

4
////
///
//
/

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

9: Roll a die

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

10: Where am I walking?

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

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

11: Reproduction

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

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

12: Product

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

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

13: Sort a string

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

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

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

14: Repeat indexing

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

R, I, "S" -> "output"
4, 1, "Hello, World!" -> "Heeeello, World!"
0, 0, "language" -> "anguage"
3, 3, "hi!" -> "hi!!!"
5, 2, "aaabbb" -> "aaaaaaabbb"
\$\endgroup\$
27
  • 1
    \$\begingroup\$ "Your language should be capable of basic input" - is a language that only implicitly does both (or indeed either) acceptable? (I'm guessing yes) \$\endgroup\$ Jun 23, 2018 at 12:51
  • 1
    \$\begingroup\$ Quine - proper, or is say 0 a quine if it outputs 0? \$\endgroup\$ Jun 23, 2018 at 12:54
  • 1
    \$\begingroup\$ 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... \$\endgroup\$
    – DELETE_ME
    Jun 23, 2018 at 14:33
  • 2
    \$\begingroup\$ @JonathanAllan Yes to comment #1, no to #2 \$\endgroup\$ Jun 23, 2018 at 20:01
  • 1
    \$\begingroup\$ @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... \$\endgroup\$ Jun 23, 2018 at 20:03
  • 3
    \$\begingroup\$ 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) \$\endgroup\$ Jun 24, 2018 at 15:53
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ Jun 24, 2018 at 22:01
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – DLosc
    Jun 28, 2018 at 4:51
  • 1
    \$\begingroup\$ @DLosc Good idea, and thanks for the grammar fix tho \$\endgroup\$ Jun 28, 2018 at 5:27
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – DLosc
    Jun 28, 2018 at 16:59
  • 1
    \$\begingroup\$ rand=lambda seed: 4 #guaranteed to be random (please define random) \$\endgroup\$
    – Jo King Mod
    Jun 29, 2018 at 14:56
  • 2
    \$\begingroup\$ @JoKing no? I'm pretty sure this site has a definition of random. (I distinctly remember there being at least 1 meta about randomness) \$\endgroup\$ Jun 29, 2018 at 18:04
  • 1
    \$\begingroup\$ @AidanF.Pierce Thanks for the feedback, I'll simply disallow reading the program's source for that particular challenge. \$\endgroup\$ Jun 29, 2018 at 18:10
  • 1
    \$\begingroup\$ So 6 if seed>5 else seed+1 is valid? Random doesn't mean uniformly by default \$\endgroup\$
    – Jo King Mod
    Jun 30, 2018 at 0:13
  • 1
    \$\begingroup\$ Suggestion: A challenge mixing string and number input, e.g. repeat this string N times \$\endgroup\$
    – Jo King Mod
    Jun 30, 2018 at 2:33
16
\$\begingroup\$

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

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

enter image description here

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

enter image description here

(hint: it isn't)

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

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

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

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

A unit is decided by the following:

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

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

Sandbox notes:

  • This is in development.
  • Test cases coming later. Feel free to provide some.
  • If somebody has code they would like to donate to me for test case generation, please do. :P
  • I might change the units req. to a higher number depending on how this turns out.
  • Any other advice?
\$\endgroup\$
13
  • \$\begingroup\$ Some images failing and succeeding the test would be cool \$\endgroup\$
    – Quill
    Jan 14, 2016 at 3:07
  • \$\begingroup\$ I know, working on test cases. Will do tomorrow. \$\endgroup\$
    – Riker
    Jan 14, 2016 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, 2016 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, 2016 at 0:38
  • \$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ famous last words "will do tomorrow" lol \$\endgroup\$ Jul 13, 2016 at 20:45
  • \$\begingroup\$ @RohanJhunjhunwala ....oops. >_> I need code to generate the test cases, haven't written it. \$\endgroup\$
    – Riker
    Jul 16, 2016 at 18:11
  • \$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ haha \$\endgroup\$ Jul 16, 2016 at 18:26
  • \$\begingroup\$ @EasterlyIrk Perhaps it will magically do itself in 6 to 8 weeks! :-) \$\endgroup\$
    – wizzwizz4
    Oct 28, 2016 at 13:05
  • \$\begingroup\$ You going to post this riker? \$\endgroup\$
    – user63187
    Jul 10, 2017 at 9:41
  • \$\begingroup\$ Is this ever going to get posted? \$\endgroup\$
    – MD XF
    Aug 5, 2017 at 1:42
  • \$\begingroup\$ @MDXF yes, but it's not going to be soon. \$\endgroup\$
    – Riker
    Aug 5, 2017 at 12:03
  • \$\begingroup\$ @Rɪᴋᴇʀ 2 yrs later... \$\endgroup\$
    – Miriam
    Apr 1, 2019 at 22:30
  • 2
    \$\begingroup\$ @ArtemisFowl hush, I'll do it eventually™... \$\endgroup\$
    – Riker
    Apr 2, 2019 at 3:07
16
\$\begingroup\$

Who needs a GUI anyway?

Most people like GUIs.

You don't.

They say that GUI's show them pretty pictures.

Your task:

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

Challenge

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

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

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

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

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

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

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

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

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

    • Each character of the resized image represents 1 pixel.

  • The characters printed must be a space.

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

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

Example

PPCG logo

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

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

\$\endgroup\$
13
  • 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, 2015 at 14:46
  • \$\begingroup\$ Updated to answer 1,2,3,5. Answer to 4 upcoming. \$\endgroup\$
    – Blue
    Sep 6, 2015 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\$ Sep 6, 2015 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, 2015 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, 2015 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\$ May 3, 2016 at 18:43
  • \$\begingroup\$ @trichoplax currently discussing this in chat \$\endgroup\$
    – Blue
    May 3, 2016 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\$ May 3, 2016 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\$ May 3, 2016 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, 2016 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, 2016 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, 2017 at 3:28
  • \$\begingroup\$ @MDXF Ping me tomorrow about it in TNB and I'll post it then :P \$\endgroup\$
    – Blue
    Aug 18, 2017 at 7:57
15
\$\begingroup\$

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?

\$\endgroup\$
13
  • \$\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\$ Aug 17, 2011 at 14:24
  • 3
    \$\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, 2011 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, 2011 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, 2011 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, 2011 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, 2011 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\$ Aug 29, 2011 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, 2011 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, 2015 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\$ Oct 19, 2015 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, 2016 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, 2017 at 18:23
  • \$\begingroup\$ It is a compiler and when it compiles it has to come up with a program to do this. Bonus points for securing a banking algorithm. \$\endgroup\$
    – Willtech
    Dec 28, 2023 at 6:36
14
\$\begingroup\$

Global Warming

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

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

Movement and positioning

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

Pushing

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

Input

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

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

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

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

Example input:

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

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

Output

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

For movement:

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

For pushing:

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

To do nothing, simply don't output anyting

Where move and push are string literals.

Example:

move,0.0,0.7

or

push,d5e86

The following lines are valid outputs for your program:

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

Detailed Rules and remarks

A list of important points to consider:

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

Scoring

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

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

The winner will be chosen at INSERT DATE

Examples in pseudocode

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

#!/bin/env pseudocode
data = read_csv(stdin)
foreach line in data.range(1,data[0,1]):
    if distance(me, line[1], line[2]) <= 1:
        write_csv_line(stdout, ["push", line[0], 1.0])
\$\endgroup\$
18
  • \$\begingroup\$ @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. \$\endgroup\$
    – Kroltan
    Jul 26, 2014 at 12:04
  • \$\begingroup\$ @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"? \$\endgroup\$
    – Kroltan
    Jul 26, 2014 at 12:47
  • \$\begingroup\$ @MartinBüttner Good point. Will update. \$\endgroup\$
    – Kroltan
    Jul 26, 2014 at 13:01
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 26, 2014 at 13:03
  • \$\begingroup\$ @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. \$\endgroup\$
    – Kroltan
    Jul 26, 2014 at 13:25
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jul 26, 2014 at 13:32
  • \$\begingroup\$ @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. \$\endgroup\$
    – Kroltan
    Jul 26, 2014 at 13:51
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 26, 2014 at 13:58
  • \$\begingroup\$ Reworded the question (answer?) to a more readable manner. \$\endgroup\$
    – Kroltan
    Jul 28, 2014 at 1:59
  • 1
    \$\begingroup\$ 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?) \$\endgroup\$
    – Zaq
    Jul 29, 2014 at 1:07
  • \$\begingroup\$ @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. \$\endgroup\$
    – Kroltan
    Jul 29, 2014 at 2:54
  • \$\begingroup\$ @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. =) \$\endgroup\$
    – justhalf
    Jul 29, 2014 at 6:46
  • 1
    \$\begingroup\$ @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 \$\endgroup\$
    – Kroltan
    Jul 29, 2014 at 13:14
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – feersum
    Aug 18, 2014 at 19:50
  • \$\begingroup\$ @justhalf I know ;D \$\endgroup\$
    – Kroltan
    Aug 18, 2014 at 20:32
14
\$\begingroup\$

Random Golf of the Day

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

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

About the Series

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

#1: Shuffle an Array

#2: Numbers from a Normal Distribution

#3: Integer Partitions

#4: The Bertrand Paradox

#5: Diamond Tilings

#6: Roll a d20

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

#8: Shuffle an infinite list

Further ideas (still unordered):

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

Which way will the see-saw turn?

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

For example, ooO O represents the situation:

ooO O
===== 
  ^

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

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

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

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

\$\endgroup\$
5
  • \$\begingroup\$ *consistently. Also, related (but not duplicate) \$\endgroup\$
    – Luis Mendo
    Jan 2, 2017 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, 2017 at 11:08
  • \$\begingroup\$ I'm sure that O isn't lower case. ;) \$\endgroup\$
    – user48538
    Jan 3, 2017 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, 2017 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, 2017 at 14:04
12
\$\begingroup\$

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?

\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – Gareth
    Dec 24, 2013 at 22:03
  • \$\begingroup\$ 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. \$\endgroup\$
    – PhiNotPi
    Dec 25, 2013 at 0:37
  • \$\begingroup\$ 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. \$\endgroup\$ Dec 28, 2013 at 10:15
  • 1
    \$\begingroup\$ "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? \$\endgroup\$
    – r3mainer
    Jan 14, 2014 at 10:22
  • 1
    \$\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.) \$\endgroup\$
    – user58826
    Jun 9, 2017 at 15:42
12
\$\begingroup\$

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.
\$\endgroup\$
5
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – ProgramFOX
    Jun 9, 2014 at 14:01
  • \$\begingroup\$ @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. \$\endgroup\$
    – yo'
    Jun 9, 2014 at 14:22
  • \$\begingroup\$ @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. \$\endgroup\$
    – nneonneo
    Jun 28, 2014 at 23:44
  • 2
    \$\begingroup\$ As far as tagging goes, I'd go with code-challenge. \$\endgroup\$
    – nneonneo
    Jun 28, 2014 at 23:45
  • \$\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, 2017 at 16:52
12
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ 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? \$\endgroup\$ Mar 30, 2016 at 12:06
  • \$\begingroup\$ @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. \$\endgroup\$
    – PhiNotPi
    Mar 30, 2016 at 12:18
  • 1
    \$\begingroup\$ Here's for hoping for super long ZAP ZAP chains \$\endgroup\$ Mar 30, 2016 at 14:27
  • \$\begingroup\$ Also, I'd argue for multiple bot control (maybe 5 or so)? It'd allow for complex shipping operations \$\endgroup\$ Mar 30, 2016 at 14:30
  • \$\begingroup\$ @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). \$\endgroup\$
    – PhiNotPi
    Mar 30, 2016 at 15:15
  • \$\begingroup\$ 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? \$\endgroup\$ Mar 30, 2016 at 15:19
  • \$\begingroup\$ 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) \$\endgroup\$
    – Cyoce
    Mar 31, 2016 at 3:32
12
\$\begingroup\$

Prime Spiral

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

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

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

If you're at number n<N:

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

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

Examples

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – JAD
    Dec 31, 2016 at 10:37
12
\$\begingroup\$

ASCII Line Extender

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 , so the code with the shortest number of bytes wins!

\$\endgroup\$
9
  • \$\begingroup\$ @user202729 Thanks. \$\endgroup\$ Apr 3, 2018 at 1:29
  • \$\begingroup\$ I'll add that in as a link, thanks \$\endgroup\$ Apr 3, 2018 at 1:35
  • \$\begingroup\$ 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. \$\endgroup\$
    – N. Virgo
    Apr 3, 2018 at 6:32
  • \$\begingroup\$ @Nathaniel Thanks \$\endgroup\$ Apr 3, 2018 at 9:13
  • \$\begingroup\$ Suggest testcase XXXXXXXXXX\nX________X\nX________X\nX________X\nX________X\nX________X\nX________X\nX________X\nX________X\nXXXXXXXXXX (_ for space) \$\endgroup\$
    – tsh
    Apr 4, 2018 at 8:08
  • \$\begingroup\$ @tsh Is that an empty grid (because it's of size 10x10) or is it a grid that is bordered by Xs? \$\endgroup\$ Apr 4, 2018 at 9:36
  • \$\begingroup\$ @NathanWood All borders are filled with X. Output should be 10 line of 10 Xs. \$\endgroup\$
    – tsh
    Apr 4, 2018 at 9:53
  • 1
    \$\begingroup\$ Sounds like a job for Nhohnhehr \$\endgroup\$
    – Jo King Mod
    Apr 4, 2018 at 11:18
  • \$\begingroup\$ If only this was posted... \$\endgroup\$
    – Razetime
    Apr 25, 2021 at 4:33
12
\$\begingroup\$

The Ever-Changing Labyrinth (Controller WIP)


ControllerSourceChat • 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:

Adventurer vision 1 Adventurer vision 2

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.


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.

\$\endgroup\$
34
  • \$\begingroup\$ Assumes that the maze master will only wait if the adventurer waits, would that always make waiting a bad choice for the adventurer? \$\endgroup\$
    – DELETE_ME
    Aug 7, 2020 at 1:19
  • \$\begingroup\$ Does "not visible" mean "not visible at the moment"? \$\endgroup\$
    – DELETE_ME
    Aug 7, 2020 at 1:20
  • \$\begingroup\$ Is the "increase over time" by power of 2 or linear? \$\endgroup\$
    – DELETE_ME
    Aug 7, 2020 at 1:21
  • \$\begingroup\$ @user202729 waiting is probably never a good idea for the adventurer, yes, and linear. \$\endgroup\$
    – Beefster
    Aug 7, 2020 at 5:16
  • \$\begingroup\$ Would the score of every maze master change whenever an adventurer program is posted, and vice versa? \$\endgroup\$
    – DELETE_ME
    Aug 7, 2020 at 5:31
  • \$\begingroup\$ 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) \$\endgroup\$
    – DELETE_ME
    Aug 7, 2020 at 5:34
  • \$\begingroup\$ 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. \$\endgroup\$
    – DELETE_ME
    Aug 7, 2020 at 5:34
  • \$\begingroup\$ There should be some time limit for each turn. \$\endgroup\$
    – DELETE_ME
    Aug 7, 2020 at 5:35
  • \$\begingroup\$ @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. \$\endgroup\$
    – Beefster
    Aug 7, 2020 at 15:54
  • \$\begingroup\$ 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]? \$\endgroup\$
    – DELETE_ME
    Aug 8, 2020 at 0:37
  • \$\begingroup\$ "The behavior must be deterministic with a fixed RNG"? (I'm not sure how to phrase this.) \$\endgroup\$
    – DELETE_ME
    Aug 8, 2020 at 0:43
  • \$\begingroup\$ 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. \$\endgroup\$
    – DELETE_ME
    Aug 8, 2020 at 0:49
  • \$\begingroup\$ And I believe that asymptotically it's not possible to do better. \$\endgroup\$
    – DELETE_ME
    Aug 8, 2020 at 0:50
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Alion
    Aug 19, 2020 at 22:30
  • 1
    \$\begingroup\$ I can help with the controller. \$\endgroup\$
    – emanresu A
    May 14, 2021 at 21:33
11
\$\begingroup\$

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.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ Mar 25, 2014 at 22:29
  • \$\begingroup\$ @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? \$\endgroup\$ Mar 26, 2014 at 4:51
  • \$\begingroup\$ 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. \$\endgroup\$ Mar 26, 2014 at 14:34
  • \$\begingroup\$ @Peter Taylor. OK. What do you think of the current version? \$\endgroup\$ Mar 26, 2014 at 14:50
  • \$\begingroup\$ The more I think about this question, the less suited I think it is for this site. \$\endgroup\$ Mar 26, 2014 at 19:48
  • \$\begingroup\$ @Peter Taylor. OK. I will try to find another one later. Regards. \$\endgroup\$ Mar 26, 2014 at 19:51
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 16:29
11
\$\begingroup\$

Evolution of Squares!

This is an idea for a question, and is very much unfinished. Please help me develop it further.

This is inspired by an evolution simulation I coded a few years ago in JavaScript. The source code and documentation can be found on GitHub, and you can play the simulation itself here.

This will be a . I'll provide a specification which all answers must keep to and a few ideas for features, but otherwise add as many features as you can.

Summary

Your task is to build a simulation which demonstrates evolution by natural selection ("survival of the fittest"). The world in which this will be carried out will be a two-dimensional, n by n (exact dimensions to be decided) grid. Each cell on the grid can be empty or occupied by a living cell (or by food resources?).

Cell lifetime

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

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

Genetics

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

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

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

Characteristics which could be included are:

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

The Simulation

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

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

\$\endgroup\$
14
  • \$\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\$ May 28, 2014 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, 2014 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\$ Jun 4, 2014 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, 2014 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\$ Jun 5, 2014 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, 2014 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\$ Jun 5, 2014 at 17:20
  • \$\begingroup\$ @githubphagocyte if someone could implement simple multi-celled creatures, that would be amazng \$\endgroup\$
    – user16402
    Jun 5, 2014 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, 2014 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\$ Jun 7, 2014 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\$ Jun 7, 2014 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\$ Jun 10, 2014 at 17:12
  • \$\begingroup\$ @professorfish "Evolution of Regular Geometries"? \$\endgroup\$ Jun 27, 2016 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, 2017 at 16:48
11
\$\begingroup\$

Construct this point

\$\endgroup\$
0
10
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ would this be code-golf? \$\endgroup\$
    – TheDoctor
    Oct 24, 2015 at 20:40
  • 5
    \$\begingroup\$ Do you ever plan to post this? \$\endgroup\$
    – MD XF
    May 31, 2017 at 21:49
10
\$\begingroup\$

N-Player Battleship

The Rules

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

The Specs

Input

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

S X .
S O M
S . H

These are the meanings of the characters:

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

Output

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

Meta

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

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!

\$\endgroup\$
8
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jun 5, 2015 at 22:19
  • \$\begingroup\$ What happens in a head-on collision? \$\endgroup\$
    – N. Virgo
    Apr 26, 2018 at 1:37
  • \$\begingroup\$ 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.) \$\endgroup\$
    – N. Virgo
    Apr 26, 2018 at 1:39
  • \$\begingroup\$ @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. \$\endgroup\$
    – mbomb007
    Apr 26, 2018 at 3:33
  • \$\begingroup\$ 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. \$\endgroup\$
    – mbomb007
    Apr 26, 2018 at 3:48
  • \$\begingroup\$ 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. \$\endgroup\$
    – N. Virgo
    Apr 26, 2018 at 4:14
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Beefster
    Apr 26, 2018 at 18:42
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – mbomb007
    Apr 26, 2018 at 19:16
10
\$\begingroup\$

Validate Sudoku on a Mobius Strip

\$\endgroup\$
14
  • \$\begingroup\$ I think loosening the input and output requirements would be well received. \$\endgroup\$
    – pajonk
    Sep 22, 2021 at 12:02
  • \$\begingroup\$ @pajonk can you give an example? \$\endgroup\$ Sep 22, 2021 at 12:02
  • 1
    \$\begingroup\$ Like inputting in any consistent format (including comma separated, native types of arrays etc., in reverse order, rows/columns first, ...). And the same for output. \$\endgroup\$
    – pajonk
    Sep 22, 2021 at 12:04
  • \$\begingroup\$ @pajonk, so basically saying your input and output can meet your needs so long as you accept all of the squares as input and output all of the squares as solved (paraphrasing of course)? \$\endgroup\$ Sep 22, 2021 at 12:09
  • \$\begingroup\$ Well, hmmm, yes. \$\endgroup\$
    – pajonk
    Sep 22, 2021 at 12:24
  • \$\begingroup\$ @pajonk how's that? \$\endgroup\$ Sep 22, 2021 at 13:33
  • \$\begingroup\$ Looks good now (for me). \$\endgroup\$
    – pajonk
    Sep 22, 2021 at 16:51
  • 2
    \$\begingroup\$ I like the puzzle idea, I think it's neat. However I feel like as a code-golf challenge this just has a lot going on. Big challenges can be fun but the bulk of this is pretty much the same as the existing solve a sudoku challenge with a different shape. If you really want to stick with this challenge I can recommend pruning the challenge down a bit, and going with "validate a mobius sudoku instead". Most solutions to the existing challenge would probably do that as a sub-challenge anyway and it's the most unique part. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 22, 2021 at 21:42
  • \$\begingroup\$ @WheatWizard how's that? \$\endgroup\$ Sep 23, 2021 at 20:18
  • \$\begingroup\$ @WheatWizard do you mind helping me rephrase it? I changed it to accept a completed strip as input and provide whether the provided input is a valid solution as output, but perhaps I'm having trouble with making that a clear statement? \$\endgroup\$ Sep 24, 2021 at 12:19
  • 1
    \$\begingroup\$ Oh sorry I interpreted "How's that?" as you not understanding what I was saying. I've read the changes now and I think it is good. You might want to check out this in terms of output. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 24, 2021 at 12:22
  • \$\begingroup\$ @WheatWizard so like 0 for false, input for true? \$\endgroup\$ Sep 24, 2021 at 12:44
  • \$\begingroup\$ I'm not making any concrete suggestion here, it is up to you. I'm just point out a place where we have had discussions about this so you can read what people have said and come to the conclusion that suits you. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 24, 2021 at 12:47
  • \$\begingroup\$ @WheatWizard I appreciate it; I was pointing out where I arrived for feedback before updating the post lol \$\endgroup\$ Sep 24, 2021 at 13:09
10
\$\begingroup\$

Don't touch the walls!

\$\endgroup\$
7
  • \$\begingroup\$ Explain "non-jagged" a bit more. \$\endgroup\$ Jun 8, 2022 at 7:40
  • \$\begingroup\$ Also, make the 3D test case appear earlier, else it seems like you "added a twist". \$\endgroup\$ Jun 8, 2022 at 7:41
  • \$\begingroup\$ Can multi-dimensional be 1D? 100D? 0D? \$\endgroup\$ Jun 8, 2022 at 7:41
  • \$\begingroup\$ Re: "non-jagged" - I think you may use "rectangular" as it will be more intuitive, and explain that in non-2D case all dimensions of the array must have the same length (per analogy to the 2D case). \$\endgroup\$
    – pajonk
    Jun 8, 2022 at 7:58
  • \$\begingroup\$ Why this "touch the edges" framing, when you can just say something to the effect of "not the first/last item or within the first/last item of the array/a subarray"? I feel like that explanation should come much sooner. i.e. before the first example \$\endgroup\$ Jun 8, 2022 at 14:56
  • \$\begingroup\$ not quite a duplicate, but this is the opposite of hollow out an array? \$\endgroup\$
    – cjquines
    Jun 11, 2022 at 5:31
  • \$\begingroup\$ @cjquines It's related, but that only runs in 2 dimensions, and being the opposite way round makes it quite different \$\endgroup\$
    – pxeger
    Jun 11, 2022 at 5:54
9
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ May 28, 2011 at 22:35
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ Jun 1, 2011 at 6:49
1
2 3 4 5
155

You must log in to answer this question.

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