Sandbox for Proposed Challenges

Question

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

Sandbox FAQ

Posting

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

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

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

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

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

If you think one of your posts 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".

Answer 1

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

Count the pips in a pair of dice

👉 Moved here

Answer 2

Waving Hands bot

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

---

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

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

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

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

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

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

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

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

---

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

Answer 3

Conquer the Solar System

king-of-the-hill

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

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

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

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

The Setting

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

The Model

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

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

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

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

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

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

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

Gameplay

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

Combat System

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

Implementation

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

On their turn, each bot will be provided with

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

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

Further Design Decisions

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

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

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

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

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

Answer 4

King of the Hill- Simple RPG

king-of-the-hill

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

The Rules of the Game

The Board

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

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

Mechanics

Each turn, a player can:

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

Combat

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

Damage is calculated using this formula:

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

Special Attacks

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

Monsters

In the game, there are 5 monsters:

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

If you kill another player, you receive 100XP.

Attributes

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

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

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

Implementation

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

Here are the additional functions you get for your convenience:

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

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

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

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

Winning Condition

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

Answer 5

Build a golfing language with me

Answer 6

DTMF Decoder

code-challenge audio (dsp?)

---

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

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

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

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

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

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

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

---

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

Answer 7

Anarchist chess

king-of-the-hill

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.

Answer 8

Underwater Survival Game

king-of-the-hill

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

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

The Arena

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

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.

Answer 9

10-character golfing language

language-design test-battery

{{{rewriting}}}

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

Design and Implementation rules

Your language should have the following characteristics:

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

Winning

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

The Challenges

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

1: Greetings, Humans!

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

Example Output:

Greetings, Humans!

2: Even cats

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

Example Input:

Hello, World!

Example Output 1:

Hlo ol!

Example Output 2:

el,Wrd

3: Do the wave

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

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

4: Quine

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

5: Coprimality

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

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

6: Ternary

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

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

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

7: Word value sum

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

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

8: Shutters

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

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 quine rules apply.

12: Product

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

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

13: Sort a string

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

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

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

14: Repeat indexing

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

R, I, "S" -> "output"
4, 1, "Hello, World!" -> "Heeeello, World!"
0, 0, "language" -> "anguage"
3, 3, "hi!" -> "hi!!!"
5, 2, "aaabbb" -> "aaaaaaabbb"

Answer 10

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

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

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

_{(hint: it isn't)}

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

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

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

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

A unit is decided by the following:

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

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

Sandbox notes:

• This is in development.
• Test cases coming later. Feel free to provide some.
• If somebody has code they would like to donate to me for test case generation, please do. :P
• I might change the units req. to a higher number depending on how this turns out.
• Any other advice?

Answer 11

Who needs a GUI anyway?

code-golf ascii-art

Most people like GUIs.

You don't.

They say that GUI's show them pretty pictures.

Your task:

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

Challenge

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

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

  • \x1b[48;5;<bgcode>m sets the colour.

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

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

  • You may use image processing libraries to parse images.

• The output must be viewable in any terminal sized over 80x24.

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

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

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

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

  • Each character of the resized image represents 1 pixel.

• The characters printed must be a space.

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

  • In this case, the similarity of 2 colours can be defined as: ((R1-R2)^2+(G1-G2)^2+(B1-B2)^2)^0.5 where results closer to zero indicate closer similarity.

• If your image format supports the alpha channel, you may assume it is empty/doesn't exist.

Example

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

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

Answer 12

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?

Answer 13

Global Warming king-of-the-hill

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

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

Movement and positioning

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

Pushing

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

Input

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

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

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

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

Example input:

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

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

Output

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

For movement:

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

For pushing:

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

To do nothing, simply don't output anyting

Where move and push are string literals.

Example:

move,0.0,0.7

or

push,d5e86

The following lines are valid outputs for your program:

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

Detailed Rules and remarks

A list of important points to consider:

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

Scoring

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

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

The winner will be chosen at INSERT DATE

Examples in pseudocode

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

#!/bin/env pseudocode
data = read_csv(stdin)
foreach line in data.range(1,data[0,1]):
    if distance(me, line[1], line[2]) <= 1:
        write_csv_line(stdout, ["push", line[0], 1.0])

Answer 14

Random Golf of the Day

code-golfrandom

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

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

About the Series

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

#1: Shuffle an Array

array-manipulationpermutations

#2: Numbers from a Normal Distribution

number

#3: Integer Partitions

numbercombinatoricsinteger-partitions

#4: The Bertrand Paradox

geometry

#5: Diamond Tilings

ascii-artcombinatoricstiling

#6: Roll a d20

geometryabstract-algebrapermutations

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

string

#8: Shuffle an infinite list

array-manipulationpermutations

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.

Answer 15

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

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

For example, ooO O represents the situation:

ooO O
===== 
  ^

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

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

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

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

Answer 16

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?

Answer 17

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.

Answer 18

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.

Answer 19

Prime Spiral

primescode-golfgraphical-output

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

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

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

If you're at number n<N:

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

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

Examples

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

Answer 20

ASCII Line Extender

code-golf ascii-art

Introduction

I have an ASCII grid of size 10x10

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

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

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

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

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

Challenge

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

Test cases

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

Test for overlap

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

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

Test for Xs

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

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

Test for X and avoiding

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

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

Test for slashes in the same row

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

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

Test for lots of lines

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

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

Test for empty grid

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

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

Scoring

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

Answer 21

The Ever-Changing Labyrinth (Controller WIP)

king-of-the-hill grid maze javascript

---

Controller • Source • Chat • Submit

This is a 2-player asymmetric KotH challenge.

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

Gameplay

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

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

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

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

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

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

Illustration of how adventurers observe the maze:

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

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

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

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

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

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

The maze master does not carry over mana between rounds.

Coding

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

Adventurers Interface

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

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

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

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

Vision is defined as an object with this schema

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

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

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

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

Maze Master Interface

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

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

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

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

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

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

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

{
    eastCost: number
    southCost: number
}

Submission Format

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

# <submission type>: <name>

Optional blurb

    // relevant functions, constants, variables go here

    return /* the object */

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

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

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

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

Scoring and The Tournament

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

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

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

The adventurer bot with the highest score wins.

The maze master bot with the lowest score wins.

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

---

king-of-the-hill grid maze javascript

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

Parts still in need of implementation:

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

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

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

Answer 22

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.

Answer 23

Evolution of Squares!

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

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

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

Summary

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

Cell lifetime

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

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

Genetics

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

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

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

Characteristics which could be included are:

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

The Simulation

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

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

Answer 24

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

Answer 25

N-Player Battleship

king-of-the-hill

The Rules

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

The Specs

Input

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

S X .
S O M
S . H

These are the meanings of the characters:

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

Output

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

Meta

• Adjustments to the fleet?
• More details needed in the spec or rules?

Answer 26

king-of-the-hill game python

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!

Answer 27

Validate Sudoku on a Mobius Strip

Answer 28

Don't touch the walls!

Answer 29

Construct this point

Given a constructible point \$(x, y) \in \mathbb R^2\$, output the steps required to construct \$(x, y)\$

Constructing a point

Consider the following "construction" of a point \$(\alpha, \beta)\$ in the Cartesian plane:

Begin with the points \$(0, 0)\$ and \$(1, 0)\$. Then, more points can be added by performing a finite number of the following steps:

• Draw the unique infinitely long line between two existing points \$(x, y)\$ and \$(x', y')\$

• Draw the unique circle centered on an existing point \$(x, y)\$ that passes through a distinct existing point \$(x', y')\$

• Add a point \$(x, y)\$ where any two lines or circles intersect

For example, if we draw the line connecting \$(0, 0)\$ and \$(1, 0)\$, then the circle centered on \$(1, 0)\$ with radius \$1\$ (passes through \$(0, 0)\$), we can construct the point \$(2, 0)\$ where the circle and line intersect. Now, if we draw the circles centered on \$(0, 0)\$ and \$(2, 0)\$ that pass through \$(2, 0)\$ and \$(0, 0)\$ respectively, we construct the point \$(1, \sqrt 3)\$, and so on.

If both \$x\$ and \$y\$ are constructible numbers (i.e. there exists some closed form expression of \$x\$ and \$y\$ involving only integers, the 4 basic arithmetic operations and square roots), then \$(x, y)\$ can be constructed in a finite number of these steps.

---

This is a code-golf challenge, where you are provided, in exact form, two constructible numbers, \$x\$ and \$y\$, and should output the steps to construct the point \$(x, y)\$, beginning from the initial set of points \$S = \{(0, 0), (1, 0)\}\$.

As both \$x\$ and \$y\$ are constructible, they can be expressed as a finite combination of addition, multiplication, division, subtraction and square roots of integers - termed here as "closed form numbers". You may take input in any form that exactly represents any closed form number. This could be as an exact symbolic number (if your language has these), a string unambiguously representing the composition of the 5 operations (e.g. 7*sqrt(2)-sqrt(3), 7*s2-s3 or even sub(times(7, sqrt(2)), sqrt(3))), and so on. You may not input as floating point values. Note that the format you choose should be unambiguous for all possible inputs.

In short, you may choose any input format - not limited to strings - so long as that input format can represent any closed form number exactly and unambiguously. Additionally, be mindful of this standard loophole about encoding extra information into the input format - this is fairly loose, but try not to use formats that contain more information than just the 5 standard operations.

As output, you should produce some list of operations that, if followed, add the point \$(x, y)\$ to the set of constructed points \$S\$. By default, we will assume that all new points after each step are automatically added to \$S\$, and so you only need to output two possible instructions at each step:

• Draw a circle centered at a point \$(a, b)\$ going through a point \$(c, d)\$
• Draw a line through the points \$(a, b)\$ and \$(c, d)\$

This can be in any format that clearly includes both points necessary for each instruction, and which instruction is used. At the most basic, the options of [0, a, b, c, d] and [1, a, b, c, d] for circle and line respectively are completely fine. In short, you must be able to unambiguously distinguish each instruction from the next, the circle instruction from the line, and the two points \$(a, b)\$ and \$(c, d)\$. However, the values of \$a, b, c, d\$ must be exact constructible numbers.

Note that you may output any finite valid list of steps, not just the shortest.

This is a code-golf challenge, so the shortest code in each language wins

---

Worked example

Take the point \$H = (\sqrt 3, \sqrt 3)\$. This can be constructed in 8 steps, with the first point in the circle instruction being the center:

Line: (0, 0), (1, 0)
Circle: (1, 0), (0, 0)
Circle: (2, 0), (0, 0)
Circle: (0, 0), (2, 0)
Circle: (4, 0), (2, 0)
Line: (1, 0), (1, √3)
Line: (1, √3), (3, √3)
Line: (0, 0), (1, 1)

The construction lines from this can be seen as:

This can be extended with 5 more lines to construct the more complicated point \$(\sqrt 3, \sqrt 2)\$:

Line: (2, 0), (1, 1)
Line: (1, -√3), (3, -√3)
Line: (0, 0), (1, -1)
Line: (2-√2, √2), (√2, √2)
Line: (√3, √3), (√3, -√3)

Test cases

To be completed

Here, we use C (a, b), (x, y) to represent a circle with center \$(a, b)\$ and L (a, b), (x, y) a line that passes through the two points.

(x, y) -> Steps
(0, 0) -> []
(6, 0) -> ["L (0, 0), (1, 0)", "C (1, 0), (0, 0)", "C (2, 0), (0, 0)", "C (4, 0), (2, 0)"]
(1, √3) -> ["L (0, 0), (1, 0)", "C (1, 0), (0, 0)", "C (0, 0), (2, 0)", "C (2, 0), (0, 0)"]
(1, 1) -> ["L (0, 0), (1, 0)", "C (1, 0), (0, 0)", "C (2, 0), (0, 0)", "C (0, 0), (2, 0)", "C (4, 0), (2, 0)", "L (1, 0), (1, √3)"]
(-1/2, √2) -> ["L (0, 0), (1, 0)", "C (0, 0), (1, 0)", "C (-1, 0), (0, 0)", "L (-1/2, √3/2), (-1/2, -√3/2)", "C (1, 0), (0, 0)", "C (0, 0), (2, 0)", "C (2, 0), (0, 0)", "L (1, 0), (1, √3)", "L (0, 0), (1, 1)", "L (0, 0), (1, -1)", "L (√2, √2), (-√2, √2)"]
(1+√3+√2/2, 0) -> ["L (0, 0), (1, 0)", "C (1, 0), (0, 0)", "C (2, 0), (0, 0)", "C (0, 0), (2, 0)", "L (1, √3), (1, 0)", "C (4, 0), (2, 0)", "L (1, √3), (3, √3)", "L (0, 0), (1, 1)", "L (2, 0), (1, 1)", "L (1, -√3), (3, -√3)", "L (√2, √2), (2, 0)", "L (2-√2, √2), (0, 0)", "C (1, 0), (1, 1+√2)", "L ((1+√2)/√2, 1/√2), ((1+√2)/√2, -1/√2)", "C ((1+√2)/√2, 0), ((1+√2)/2, √3))"]
(√2+√3, √5) -> ["L (0, 0), (1, 0)", "C (1, 0), (0, 0)", "C (2, 0), (0, 0)", "C (0, 0), (2, 0)", "L (1, √3), (1, 0)", "L (0, 0), (1, 1)", "L (0, 0), (1, -1)", "L (√2, √2), (√2, -√2)", "C (4, 0), (2, 0)", "L (1, √3), (3, √3)", "C (0, 0), (√2, √3)", "C (0, 0), (1, 0)", "C (√2, 0), (√2, √3)", "L (0, 1), (0, -1)", "C (0, √5), (0, 0)", "L (0, √5), (√5, √5)", "C (√2+√3, 0), (0, 0)", "L (√2+√3, 0), (√2+√3, √2+√3)"]

---

Meta

• Feedback?
• Is this doable?
• Is this a duplicate?
• Tags are code-golf, math, number-theory and abstract-algebra. Any others?

Answer 30

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.