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


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.


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.


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

  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    Commented May 15 at 14:05
  • \$\begingroup\$ @None1 If you don't get feedback for a while you can ask in the nineteenth byte \$\endgroup\$
    – mousetail
    Commented May 29 at 13:27

4729 Answers 4729

14 15
17 18

Turn my keyboard into a piano

I'm sure we've all thought "man, wouldn't it be cool if my keyboard played musical notes as I program?". Of course, the answer to that question is a resounding no.

Regardless, it's what you're going to make.


Input will be given, in real-time, on the keyboard.

The keyboard mapping that you will use is given in the diagram below. This kind of layout is used by several music programs already.

A keyboard layout, with notes assigned to several of the keys.

You can see that the bottom row (Z, X, C, V, B... ., /) represents all of the white keys, and the black keys are added on the row above (S, D, G, H, J... L, ;). This is then repeated on the two rows above, except the notes are an octave higher.

The notes C5 to E5 are repeated both on the lower rows and the upper rows.

So, if the user were to input Q (or ,) on the keyboard, middle-C (C5) should play. Similarly, if they input B, G4 should play.

The diagram above is an edited form of an image found here.


The only output will be sound. The actual sound used is up to you (it could be a piano sample or the internal beeper), but it should output sound at the correct pitch.

The program should not terminate by itself - the user should be able to keep inputting notes until they get bored.


  • A diagram of the US keyboard layout (for comparison with the image above) can be found here.
  • A table of the frequencies of notes can be found here. The range of notes that you will be using are from C4 to E6, inclusive.

Rules and Disambiguation

  • This is , so the shortest correct implementation wins.
  • Input should be given in real-time (i.e. no pressing Enter between each inputted note).
    • There should be no greater than a 0.25 second delay between pressing a key and hearing the note.
  • Only programs that have the notes correctly mapped to the QWERTY keyboard will be accepted.
  • The only output should be sound. There should be nothing displayed (except for a mandatory console window or similar).
  • Polyphony (multiple notes playing at once) is not part of the specification.
  • The program should not terminate by itself - a user should be able to keep pressing keys and hearing notes until they decide to close it.
  • The waveform outputted is not important (it can be a beep or a piano sound or whatever you like); the pitch, however, should be accurate.
    • The file size of any sound files used will not be counted in the bytecount.
    • Please link any sound files you use with your answer.


  • There are probably some obvious things that I've forgot to explain - please point these out!
  • Also let me know if any of the wording is confusing.
  • I've assumed that the readers will at least know very basic music theory (e.g. that there are 12 semitones in an octave). Is this okay?
  • "Polyphony is not part of the specification" - polyphony is not the focus of the program, and therefore shouldn't be a consideration when submitting answers (i.e. if the shortest implementation means that one note will stop when a new note is played, then that's fine). Is this acceptable?
  • Should I exclude the use of any external libraries that are designed to play sound or designed to repeat a function at regular intervals? Should I count sound file size in the score? I'm worried that having either of these would limit the possible entries to those that can use the internal beep (so, C/C++, C#, Python, Java?...).
  • Another problem may be portability, or the lack thereof (e.g. C/C++ using the Windows API to access the Beep() function).

Really meta: answers/edits by me won't be done until the morning (approximately 9 hours from now).

  • \$\begingroup\$ Does sound need to continue until key_up, or is just a short "beep" okay no matter how long the key is pressed? \$\endgroup\$
    – Geobits
    Commented Sep 10, 2014 at 0:26
  • \$\begingroup\$ "Of course....resounding no.... regardless.." why shit on your own question? Change it to a slightly ironic "Of course we have! Well, that's what you're going to make" \$\endgroup\$ Commented Sep 15, 2014 at 21:37
  • \$\begingroup\$ 1,2 The wording is mostly OK Regarding @Geobits point, I think a short beep has to be acceptable. One must delve deep into API to know when a key is released (if the hardware tells at all.) Make the US keyboard requirement clearer. Take the linked image of a US keyboard, mark note names on it in color and include it in the question (I may do it for you.) Without having both on the same diagram, I found it hard to work out which notes on my Spanish keyboard end up in odd places. 3. Theory is very basic here, no need to explain Maybe link to en.wikipedia.org/wiki/Scientific_pitch_notation \$\endgroup\$ Commented Sep 16, 2014 at 23:20
  • \$\begingroup\$ Allow libraries for sound functions. Otherwise it'll definitely be won by a language with builtins. Portability is always an issue with sound, but on codegolf.stackexchange.com/a/25242/15599 the OP did get my Windows answer working on his Linux machine after many comments. Avoid polyphony. Computer & phone keyboard matrixes can't handle it properly. If you press 1,3,7,9 on a numeric keypad and release 1, the release can't be detected because there's still an electric path through the other keys. Real music keyboards have a diode on every key, or individual wires, to avoid this problem. \$\endgroup\$ Commented Sep 16, 2014 at 23:39
  • \$\begingroup\$ Hi, @steveverrill, thanks for your comments. I haven't really been very interested in PCCG recently so I haven't been replying/making changes. Thanks for the suggestions - I'll review the post sometime soon. \$\endgroup\$ Commented Sep 17, 2014 at 0:07
  • \$\begingroup\$ If this is code-golf, then I suggest that you choose a set sound to make it fair for everyone. \$\endgroup\$
    – Beta Decay
    Commented Jul 5, 2015 at 7:49

Let's talk about this...

I am planning on hosting a King of the Hill challenge in which bots will have to coordinate each other in order to be successful. The idea is to play a Diplomacy-like game between bots. The engine (still in development) will start the bots and communicate with them via stdin/stdout. There will be three phases:

0. Initialization

Well, this is not a recurring phase, it is just the engine telling each bot his id, the total number of bots participating and a seed, which can be used for generation of pseudo-random numbers (bots need to be deterministic).

1. Talking Phase (10s)

In the Talking phase, bots can send messages to each other (via engine) in order to coordinate their actions. To this end, a common language is necessary. This language should be able to express any ideas, plans and opinions a bot could have. However, not every bot is forced to be able to understand everything. Simpler bots might just ignore messages they do not understand.

Since I would like each player to be able to submit more than one bot, it is forbidden to implement a "secret handshake" by which bots recognize each other and from then on work together unconditionally.

2. Planning Phase (2s)

In this phase, bots submit what they want to do this turn. Each bot has a certain amount of supply (initially five), and can command one action per supply point. There are three possible actions:

  1. Attack another bot
  2. Support another bot's attack against a third bot
  3. Defend another bot

There are some restrictions:

  • Per opponent, you can either attack or defend them, and only once
  • You cannot support an attack against a bot you also defend
  • You cannot attack, defend, support yourself or a dead bot, and neither can you support attacks against yourself

3. Resolution Phase (as short as possible)

After all orders have been submitted, the engine will resolve them simultaneously in the following way:

The defending strength of each bot is the number of bots defending that bot. The attacking strength of each attack is the number of support orders for that attack. Each attack with an attacking strength greater than the defending strength of the attacked bot results in the supply counter of the attacked bot being reduced by one, and the supply counter of the attacker being increased by one.

Support orders which support a non-existent attack do nothing.

Then, all bots with supply of zero or less will be shut down by the engine: they died.

Afterwards, all remaining bots are informed about the decisions of other bots, and a new turn begins with its Talking Phase.

Further Rules

A game will consist of ten plus random number turns, so that "last turn betrayals" are not possible. The supply count of each bot will count towards their total score. I plan an ensemble of about 100 games. The bot with the highest total score wins. Tie-breaker will be the popularity (number of votes).

I am interested in your opinion: do you think that this challenge is too complex? I imagine that the code of a decent bot would be too long to fit in a post. So people would have to use github or pastebin or similar to submit their entries. The main problem imo is the interpretation of the (yet to be determined) common language.

  • \$\begingroup\$ I like it a lot. One possible variation would be to make the "secret handshakes" a feature. To do this, you could allow multiple instances of the same bot. Then part of the challenge is to recognise your own kin and mutually support them; and a viable strategy is to try and work out other players' secret handshakes and imitate them. If you're ok with emphasising this aspect of it, then you can make the shared language pretty unrestricted, e.g. bots can just send arbitrary strings to each other. (I realise this is not what you have in mind, I just thought I'd mention the idea.) \$\endgroup\$
    – N. Virgo
    Commented Oct 31, 2014 at 15:13
  • \$\begingroup\$ @Nathaniel, what you propose is a battle of obfuscation/cryptography. What I would like to see is a battle of diplomacy. \$\endgroup\$
    – M.Herzkamp
    Commented Nov 2, 2014 at 14:27
  • \$\begingroup\$ Fair enough - I just thought I'd say it in case it sparked any interesting thoughts for you, but I knew it was probably too different from what you want to see. If I have any other ideas about your challenge I'll let you know. Designing the language really seems to be the hard part. \$\endgroup\$
    – N. Virgo
    Commented Nov 3, 2014 at 0:06
  • \$\begingroup\$ A diplomatic KOTH is something I've been wanting to see for a while. Working out the specifics of the "diplomatic language" is going to be the most difficult part. My proposal is that each message can either 1) state an intention to another bot, or 2) request an action from another bot. Each message would be formatted in a way similar to how a final command would be. \$\endgroup\$
    – PhiNotPi
    Commented Nov 9, 2014 at 14:45
  • \$\begingroup\$ @PhiNotPhi: Thanks for the Feedback! I also imagined something similar with the ability to link atomic statements in a boolean fashion. \$\endgroup\$
    – M.Herzkamp
    Commented Nov 11, 2014 at 9:23

Happy Holidays!


With the holidays upon us, I decided to make an appropriately themed challenge. You are provided with a list of holidays and their respective date ranges, and given a date, you have to output a holiday greeting or the time remaining until the next holiday as appropriate.


The list of holidays is below. You have to include it in your program (so no using a library or other external resource for this). Feel free to use any convenient format.

Start  | End    | Name
------ | ------ | -------------------
Dec 6  | Dec 7  | Saint Nicholas' Day
Dec 13 | Dec 14 | Saint Lucy's Day
Dec 24 | Dec 27 | Christmas
Jan 1  | Jan 2  | New Year
Jan 6  | Jan 7  | Epiphany
Feb 14 | Feb 15 | Valentine's Day

You are given a date as input (STDIN, function argument, or anything convenient) in YYYY-mm-dd HH:MM:SS format (e.g.: 2014-12-30 11:15:00).

You may assume that the time zone is either UTC or the system's time zone. The holiday lasts from 00:00:00 on the start date (inclusive) to 00:00:00 on the end date (exclusive).

If the date falls within the range of the holiday, you must output Happy <holiday>!, except if it's Christmas, in which case you must output Merry Christmas!.

If it doesn't, but another holiday is coming at most a week in the future, you must output:

<time> left until <holiday>.

where <time> is in the following format:

<days>d <hours>h <minutes>m <seconds>s

You can't use a library for converting the time to that format.

If there are no whole days, hours, minutes or seconds remaining, omit the number entirely. For example, 1d 0h 3m 4s should be printed as 1d 3m 4s.

If there are no upcoming holidays, you must output (no pun intended):

There are no upcoming holidays.

A trailing newline is optional, but be consistent in your program—don't add a trailing newline in one case and omit it in another.

Standard loopholes are obviously forbidden.

Test cases

Date                | Output
------------------- | ----------------------------------
2014-12-05 23:59:59 | 1s left until Saint Nicholas' Day.
2014-12-06 00:00:00 | Happy Saint Nicholas' Day!
2014-12-06 12:00:00 | Happy Saint Nicholas' Day!
2014-12-06 23:59:59 | Happy Saint Nicholas' Day!
2014-12-07 00:00:00 | 6d left until Saint Lucy's Day.
2014-12-14 00:00:00 | There are no upcoming holidays.
2014-12-24 00:00:00 | Merry Christmas!

Note that your program must work for any year, not just 2014.


This is code golf, so the submission with the fewest number of bytes wins. An answer will be accepted after a week, but I'll be happy to change the accepted answer if a new valid submission beats the previous high score.

  • \$\begingroup\$ How do you expect people to test the test cases? It would probably be better to take input than to use the current time, because then it actually makes sense to talk about test cases. You should check date for duplicates, and if there are none you should add that tag. \$\endgroup\$ Commented Dec 29, 2014 at 14:51
  • \$\begingroup\$ @PeterTaylor You're right, I'll do that. \$\endgroup\$
    – user344
    Commented Dec 29, 2014 at 15:37
  • \$\begingroup\$ @PeterTaylor I couldn't find any exact duplicates, only two holiday-themed questions, both of which ask for much less than my challenge. \$\endgroup\$
    – user344
    Commented Dec 30, 2014 at 11:28

Find the Minimum Width of a Set of Points

Given a set of points in 2D space, you're to find the direction along which those points occupy the shortest width.

More formally, consider a set of n points P = {p1, ..., pn}, where pi = (xi,yi), and a unit vector d = (xd, yd). Now K is the set of lengths obtained from orthogonal projection of P onto d. In particular, ki = xixd + yiyd. The width L of P along d is defined as max ki - min ki. Your task is to find the d along which L is minimal.

To keep things interesting, your algorithm's time complexity must not exceed O(n log n).

You may write a program or function, taking input via STDIN, command-line argument or function argument. The result may be printed to STDOUT or returned.

You can expect the input P to be in any convenient list or string format, but the input must not be pre-processed (e.g. sorted by coordinates). You may assume that the input contains at least 2 points and that no two points coincide.

The output must be correct to 10 significant (decimal) digits. Of course, d is only unique up to the relative sign of the coordinates, so there are two correct answers for each input. You may return either of those.

You must not use built-in functions related to this problem, like finding the minimum width of a polygon, or computing the convex hull of a set of points. You may use built-in vector/matrix types and operations.

Sandbox Notes

  • I'll write my own solution at some point next week, and use it to provide a number of test cases.
  • I'm also planning to add a handful of diagrams to clarify the definitions.
  • The challenge was inspired by this proposal from Calvin's Hobbies, I think they are sufficiently different, as this problem here is only one approach to tackling his challenge (and even then it's only a subproblem). But if people think, they are too similar, and posting this one would make his a duplicate in the future, I'll retract this challenge (as I'd really like to see his posted some time).
  • \$\begingroup\$ I hope you're still planning on posting this. Just a few notes: (a) The minimal direction is not generally unique (e.g., if we have a regular polygon, or just a single point). You'd might want to make the actual (scalar) width the output instead. (b) I assume the input is never empty? (c) Can it contain duplicates? \$\endgroup\$
    – Ell
    Commented Jan 3, 2015 at 16:01
  • \$\begingroup\$ @Ell yes I still want to post this. Just didn't get around to writing the reference yet. a) good point. I'll think about asking for the width vs asking for any minimal direction. b) yes, will clarify. c) I'll think about that. Probably not. \$\endgroup\$ Commented Jan 3, 2015 at 16:07

The Genetic Game of Life

In this game, you play as cells (as in cellular automata). Your goal is to reproduce and kill off other cells on the board.

At the beginning of the game, two distinct configurations will be randomly chosen, one for reproduction, one for killing. The configurations will consist of 3 squares in a 5 by 5 area, not including the center square. For example,


is an example configuration, where X represents a cell, and O can either be empty or filled. The configurations do not work if rotated.

The cells will be placed randomly, but equidistant from each other in a toroidal board. Cells will be placed in a random turn order.

Each turn, each cell will move a square one at a time. If a cell's movement creates the reproduction configuration with cells of the same type, and the center square is empty, then a new cell will spawn. If a cell's movement creates the killing configuration with cells of any type, and the center square is filled, then the cell in the center square will die.

When a new cell spawns, its DNA will be conglomeration of the DNA of the bots in the configuration. It will take its first turn after all other cells have taken 1 turn.

A cell that has not been part of a killing configuration after 200 turns will die.

The cell type with the most cells after 100K turns wins.


Each turn, you will be passed a string of 1s and 0s representing your DNA, and a list of 49 integers representing a 7x7 grid of the vision around the cell. Specimens of the same type will have the same integer, and 0 will represent an empty square.

You must return a single character (N, E, S, W or X) representing the direction that the cell will travel. Attempting to move into another cell will result in your cell not moving.

  • \$\begingroup\$ What size genome are you thinking? \$\endgroup\$ Commented Jan 21, 2015 at 15:18
  • \$\begingroup\$ When designing a bot, I think it would make a big difference if the total number of players was known. You could say "a game consists of 50 players competing on a board" and make up the numbers with a simple example bot if there are less than 50 answers. Obviously 50 is just an example - it could be 10 or 2 or 20 or whatever works best. \$\endgroup\$ Commented Jan 21, 2015 at 18:54
  • \$\begingroup\$ I say this because it means a bot writer will then know the maximum size of the 49 integers they need to process. \$\endgroup\$ Commented Jan 21, 2015 at 18:56
  • \$\begingroup\$ Could you specify whether a killing configuration can be made up using cells of different teams? \$\endgroup\$ Commented Feb 5, 2015 at 0:38
  • 2
    \$\begingroup\$ 1. The latest version of this question talks a lot about types, but doesn't define them. What is the type of a cell? Its genome? Its team? 2. What is meant by the "conglomeration" of the genomes of the bots in the spawning configuration? Is it the concatenation? Some kind of bit-by-bit random selection between the three parents' genomes? 3. What's the initial setup? How many cells do I get, and do they all have the same genome? \$\endgroup\$ Commented Feb 5, 2015 at 10:32

Convert a Finite State Machine to a Regular Expression

Anyone can make a finite state machine for matching a regular expression. But what about a regular expression that emulates a finite state machine? This inverse operation is much more confusing.


  • A positive integer N, denoting the number of states in the machine. They are labeled 0 to N - 1.
  • A list of accepting states of the machine. A string is considered to be accepted by the machine if it ends in one of these when there are no characters left.
  • A list of triples (integer a, character b, integer c) representing the transition rules: when the machine is at state a and the current character in the string is b, then it may advance one character and move to state c.

You may specify the ordering and formatting of input.


A regular expression that matches a string iff it is accepted by the finite state machine.

Additional Rules

  • An input for the state machine may contain only printable ASCII characters which are not in the set ^$()[]|+?*\..

  • The machine begins in state 0.

  • You should not use any regex features other than |, (), ?, *, +

  • You may not use libraries designed for this task (which apparently exist).

  • The regex should match full strings (assume it is surrounded by ^ and $).

  • An answer is either a program which prints the regex to stdout, or a function which returns the regex.

This is code golf: write your code in as few bytes as possible.

Sandbox Question

Should the FSM be deterministic or non?

  • \$\begingroup\$ Why not allow character classes? Alteration seems like an overkill alternative, and answers might like to detect parallel edges. \$\endgroup\$ Commented Feb 5, 2015 at 14:38
  • \$\begingroup\$ "a function which returns the regex." - do we need to actually construct the regex object or are we allowed to return a string representation thereof? \$\endgroup\$ Commented Feb 5, 2015 at 14:40
  • \$\begingroup\$ General FSMs tend to produce really big regexes. Not sure if allowing non-determinism inflates that even further, but I believe it actually does not. \$\endgroup\$ Commented Feb 5, 2015 at 14:46
  • \$\begingroup\$ Are you sure you want to allow { and } in the input? Because we'd have to escape these... \$\endgroup\$ Commented Feb 5, 2015 at 14:47
  • \$\begingroup\$ @JanDvorak Thanks. I'll allow character classes although I doubt they would be used in golf. I'm aware they will be big (like this question). \$\endgroup\$
    – feersum
    Commented Feb 5, 2015 at 14:52
  • \$\begingroup\$ (a) Can we assume anything at all about the SM? Are all terminal states accepting? Are all states reachable? Can there be no reachable accepting states, and what would be the output in this case? (b) Are the blacklisted input chars also invalid as input for the regex? That is, can we use \* in our regex with the intention that it's never matched? (c) How liberal can we be with the input format? Can we take the transition table as, for example, {src_state: [(char1, dest_state1), (char2, dest_state2)], ... }, or must it be a list of triplets? \$\endgroup\$
    – Ell
    Commented Feb 8, 2015 at 13:33
  • \$\begingroup\$ @Ell For (a) and (b), the metacharacters are not allowed in the input strings, so one way to match nothing would be using one of them literally. About (c), it must be a list of triples. \$\endgroup\$
    – feersum
    Commented Feb 13, 2015 at 3:39

ASCII Robot Wars

This idea is based off of the game "Besiege" (which I've never played) and a previous sandboxed idea of mine called "Epic Customizable Tank Battle."

The main idea is that your program is the AI that controls a robot equipped with various weapons. In this challenge, however, you will also have the opportunity to design your robot

List of Parts

(completely arbitrary and subject to total replacement)

  • Wooden planks + and armored metal plates # make up the body of the robot.
  • Wheels @ allow your robot to move. TODO - turning
  • Most weapons are formed with two parts, a body and a pointer v^<> to denote the direction of aim.
  • Cannons have a body of %, ballistas have a body of (something), spikes and battering rams are (something).
  • Maybe helicopter blades can be X.
  • Banners, which serve no purpose but decoration, could be $.

Example 5x5 robot

This robot has four wheels, three cannons facing forward, armored sides, and a flag in the middle.


Controlling the Bot

I think this would make a really cool Stack-Snippet KOTH, since it is "visually interesting" to watch robots blow each other into pieces. Writing the controller will be hard because this is a major deviation from previous pixel-based KOTHs.


Sorting Source Code

Your task in this challenge is to write a program that takes no input and outputs This program consists of followed by your program's source code characters, but in alphabetical order.


  • You may only use printable ASCII characters and line breaks in your program.
  • When outputting all source code characters, ignore line breaks and sort all characters by their ASCII number from lowest to highest.
  • Reading your program's source code is not allowed.
  • This is , so the shortest valid submission (in bytes) wins.

Here is a correctly ordered list of all printable ASCII characters (mind the space at the very beginning):



If the source code for your program is

print 'This program consists of ';
print this.sort();

then output must be

This program consists of       ''().;;Tacfghhiiiiimnnnooooppprrrrrssssssttttt
  • 1
    \$\begingroup\$ You should probably add the quine tag to this. And you should also specify whether reading the source code is allowed. That said, I'm not sure how much it adds over existing (generalised) quine challenges. Ultimately, solutions will just be language's standard quine, followed by sorting the string and prepending This program consists of. \$\endgroup\$ Commented May 18, 2015 at 17:33
  • \$\begingroup\$ Are submissions in which the original source code is already sorted, allowed? \$\endgroup\$
    – ProgramFOX
    Commented May 18, 2015 at 17:34
  • \$\begingroup\$ @ProgramFOX: I don't see why they shouldn't be allowed. Is there any particular reason? \$\endgroup\$
    – vauge
    Commented May 18, 2015 at 18:42
  • \$\begingroup\$ @MartinBüttner: Good point. I've added the quine tag, but probably there's no point in posting this challenge if there are already enough similar questions! \$\endgroup\$
    – vauge
    Commented May 18, 2015 at 18:45
  • \$\begingroup\$ @vauge No, I missed that you had to print a sentence before the sorted characters. Initially I thought of a one-char solution like 1 which works in some languages (and which would pretty much miss the purpose of the challenge), but of course that doesn't print the sentence. \$\endgroup\$
    – ProgramFOX
    Commented May 18, 2015 at 19:06
  • \$\begingroup\$ In addition to not reading the source code, you might want to link to these working definitions of what counts as a proper quine. With the requirement of printing the additional string it's not very likely that there are a lot of loopholes left, but better safe than sorry. \$\endgroup\$ Commented May 19, 2015 at 7:04
  • \$\begingroup\$ The problem with quines is that there's a reusable technique to print any function of the source code, so twists like this don't actually change much. \$\endgroup\$
    – xnor
    Commented May 19, 2015 at 7:20

Strange question about transit schematics (title tbd)

In this challenge, your goal is to produce a schematic diagram of a transit network, given a list of lines and a list of stations as input. This is a popularity-contest -- the program's goal is to maximize the readability of the diagram by carefully choosing where to draw the stations and lines.

Each line in the transit network is formatted as a list of strings. For instance:

"Peel Line", "Douglas", "Port Erin", "Braddan Halt", "Union Mill", "Crosby"

The first string on the list is the name of the line. The remaining strings are the stations that that particular line stops at. In this example the Peel Line stops at Douglas, Port Erin, Braddan Halt, Union Mill, and terminates at Crosby. The lines are bidirectional so the Peel Line would also go back the other way.

Of course, most transit networks will have more than one line. Each line of the transit network will have its own line in the input. For instance:

"Peel Line", "Douglas", "Port Erin", "Braddan Halt", "Union Mill", "Crosby"
"Foxdale Line", "Ramsey", "St. John's", "Union Mill", "Bishop", "Foxdale"

Notice how both lines stop at Union Mill. This means that Union Mill is an interchange station for those two lines. A station is an interchange station if more than one line stops at it. Here is an attempt at what the network might look like:

bad map

This map does some things well but fails at other things. The lines are coloured different colours which helps differentiate the lines. In addition, the interchange station is emphasised with the white dot to show it is an interchange station. However, it fails at other things, the most prominent being that the text "Union Mill" is overlapping the line, and there is a lack of a key showing which line is which. When we fix these elements the map looks like this:

another map!

Much better! (Another way I could have resolved the Union Mill overlapping issue was to change the paths of the lines.) In addition, we can also have lines being a loop. This is indicated by the first and last train stations being the same. For instance:

"Island Line", "Port Erin", "Kitterland", "Kalfr", "Ardglass", "Kearney", "Port Erin"

The Island Line in this case is a loop that goes from Port Erin to Kitterland to Kalfr, then to Ardglass and Kearney, before finally returning to Port Erin, completing the loop.

With more complicated train networks, it becomes more difficult to arrange the stations and lines in a readable manner. Here are some inputs of varying complexity and density to try your program on. Some of them are based of actual networks, while others are made up for this challenge.

Challenge Input 1: Oslo, Norway:

"1", "Frognerseteren", "Voksenkollen", "Lillevann", "Skogen", "Voksenlia", "Holmenkollen", "Besserud", "Midtstuen", "Skådalen", "Vettakollen", "Gulleråsen", "Gråkammen", "Slemdal", "Ris", "Gaustad", "Vinderen", "Steinerud", "Frøen", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Ensjø", "Helsfyr", "Brynseng", "Hellerud", "Tveita", "Haugerud", "Trosterud", "Lindeberg", "Furuset", "Ellingsrudåsen"
"2", "Østerås", "Lijordet", "Eiksmarka", "Ekravein", "Røa", "Hovseter", "Holmen", "Makrellbekken", "Smestad", "Borgen", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Ensjø", "Helsfyr", "Brynseng", "Hellerud", "Tveita", "Haugerud", "Trosterud", "Lindeberg", "Furuset", "Ellingsrudåsen"
"3", "Mortensrud", "Skullerud", "Bogerud", "Bøler", "Ulsrud", "Oppsal", "Skøyenåsen", "Godlia", "Hellerud", "Brynseng", "Helsfyr", "Ensjø", "Tøyen", "Grønland", "Jernbanetorget (Oslo S)", "Stortinget", "Nationaltheatret", "Majorstuen", "Blindern", "Forskningsparken", "Ullevål stadion", "Berg", "Tåsen", "Østhorn", "Holstein", "Kringsjå", "Sognsvann"
"4", "Storo", "Nydalen", "Ullevål stadion", "Forskningsparken", "Blindern", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Ensjø", "Helsfyr", "Brynseng", "Høyenhall", "Manglerud", "Ryen", "Brattlikollen", "Karlsrud", "Lambertseter", "Munkelia", "Bergkrystallen"
"5", "Storo", "Nydalen", "Ullevål stadion", "Forskningsparken", "Blindern", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Carl Berners plass", "Hasle", "Økern", "Risløkka", "Vollebekk", "Linderud", "Veitvet", "Rødtvet", "Kalbakken", "Ammerud", "Grorud", "Romsås", "Rommen", "Stovner", "Vestli"
"6", "Bekkestua", "Ringstabekk", "Jar", "Bjørnsletta", "Åsjordet", "Ullernåsen", "Montebello", "Smestad", "Borgen", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Carl Berners plass", "Sinsen", "Storo"

Here's what the official map looks like for some inspiration (click to enlarge):


TODO: more challenge inputs coming!

Sandbox Notes

  • I've had this one sitting around for a while. I've wanted to try and make a that wasn't just about making the prettiest image. So instead it's about making the most functional image, which I'm not sure is any better than the art challenges...
  • Another thing I've been considering is changing it to a . I'd have minimum requirements for the final output (a key, coloured lines, distinguished interchange stations, etc.) and the shortest code that implemented all the requirements would win. I'd like your thoughts on whether this challenge would work better as code golf or popularity contest.
  • 3
    \$\begingroup\$ I like this concept, but I somewhat like it better as a popcon. As a golf, you will get the bare minimum requirements for sure, and it might not be very functional/readable at all. As a popcon, you'll probably get at least a couple platform-ready posters. I don't normally recommend popcon for things that could be golfed, but this feels like one them. \$\endgroup\$
    – Geobits
    Commented May 19, 2015 at 16:37
  • \$\begingroup\$ For test cases, I think Tokyo would make for something nice and complicated. \$\endgroup\$
    – Geobits
    Commented May 19, 2015 at 16:41
  • \$\begingroup\$ @Geobits That is a fantastically complicated network, but it's got all sorts of things that the input format can't handle -- if I'm reading it right, when the Yokosuka Line reaches Chiba and Soga it splits off into different paths with different terminus stations. \$\endgroup\$
    – absinthe
    Commented May 19, 2015 at 22:18
  • \$\begingroup\$ Good point, I'm guessing many large cities have split lines like that. I suppose if you want a simple input format it'll have to be some boring old map ;) \$\endgroup\$
    – Geobits
    Commented May 20, 2015 at 14:01
  • 2
    \$\begingroup\$ There doesn't seem to be an obvious reason for not using an input format which allows lines to fork and loops to encompass only part of a line. Why not take input in a subset of the .dot format? \$\endgroup\$ Commented May 21, 2015 at 19:23

Permutations of the Fifteen Puzzle



How to Gossip Appropriately

We all know how important it is to get social arrangements right:


You have a group of friends who love to gossip. However, gossip is notorious for changing as it gets spread from friend to friend, and if somebody hears two versions of the same gossip, it just ruins it for them.

Hence, you and all of your friends have agreed to gossip in an orderly manner, and it is your job to define who will gossip with who and for how long. Ideal gossiping must follow the following rules:

  1. Each friend must gossip for a specific amount of time. This time is different for each person.

  2. Any pair of friends will only spend so long gossiping. Any longer, and it will become dull. We will refer to this time as L. This time is the same for all friends.

  3. Gossipping only comes in minute increments. We have no idea why this is, but its true.

  4. Gossip must eventually reach everybody. If any given friend has new gossip, then all of your friends must eventually get that gossip.

  5. Proper gossipping never includes circles. If A gossips to B and C, and then B gossips to C, then C will hear the news from two different people, and therefore, two different stories.

As an example say you are given the following as input:


Let's start by looking at B. She prefers to gossip for only 1 minute, so she will only be able to gossip with one friend.

We know that she can't gossip with D, as that breaks rule #4

If we have B gossip with C, then C will have 1 minute of gossipping left, and A won't be able to fill his 2 minutes of gossipping needs.

Therefore, we know that B must gossip with A for 1 minute, and A must gossip for 1 minute with C. C and D each have 1 minute of gossipping remaining, so they must both gossip with E.

E needs 2 more minutes of gossip.

If E gossips with F for 2 minutes, then gossip can't ever reach G.

If E gossips with F for 1 minute and G for 1 minute, then F must gossip with H for 1 minute, and H will then gossip with G for 2 minutes. This will create a circle, breaking rule #5.

Therefore, we know that E gossips with G for 2 minutes, G gossips with H for 1 minute, and H gossips with F for 2 minutes.

Our final gossipping tree looks like:


Input will be in the following format, and will be passed to your program via STDIN (or closest alternative):

Max_Gossip_Time [Node0_Ideal_Gossip_Time, Node1_Ideal_Gossip_Time, ...] [[Node0, Node1], [Node0, Node1], ...]

The second array passed is the friend list, and are integers that refer to the positions in Ideal_Gossip_Time array.

The example above would be input as follows:

2 [2, 1, 2, 1, 4, 2, 3, 3] [[0, 1], [0, 2], [1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [4, 5], [4, 6], [5, 7], [6, 7]]

Output should be to STDIO (or closest alternative) in the following format:

[[Node0, Node1, Gossip_Time], [Node0, Node2, Gossip_Time], ...]

On the above example, the output should be similar to:

[[0, 1, 1], [0, 2, 1], [2, 4, 1], [3, 4, 1], [4, 6, 2], [5, 7, 2], [6, 7, 1]]

On both input and output, the friend list can be in any order.

  • \$\begingroup\$ I didn't notice that you state anywhere that the weights must be integers. Some more test cases would be good. Do you know anything about the complexity class of this problem? \$\endgroup\$ Commented May 17, 2015 at 16:07
  • \$\begingroup\$ @PeterTaylor I don't think the complexity is too crazy, but I don't know it. The hardest part of this challenge is actually ensuring that there are no cycles as min-maxing the edges will solve everything else. \$\endgroup\$ Commented May 17, 2015 at 18:51
  • \$\begingroup\$ I can see a research paper coming out of this! \$\endgroup\$
    – Optimizer
    Commented May 27, 2015 at 13:23

If it floats, it boats!

The goal of this challenge is to determine whether or not an ASCII-art shape will float. Like any other boat, ASCII boats obey the law of buoyancy: it will float if it displaces an equal mass of water.

ASCII boats are made out of O characters arranged in some contiguous shape (diagonals are connected). There may be trailing spaces, but the whole input is a rectangle (trailing newline optional). Example boat:

   O         O    
    O        O    

The material of the boat has twice the density of water. When a boat is floating, the number of displaced water characters is at least twice number of O character in the boat. Here is an artist's impression of a boat while floating.

   O         O    
~~~~O        O~~~~

This boat has 13 O characters, but displaces 19 water characters, so it floats.

The key to floating is the creation of an air pocket. Air pockets can be formed in two ways: either the water cannot reach the pocket (because the boat has walls keeping it out), or air is trapped in the pocket and cannot escape. Here's an example of a capsized boat which can still float (warning: do not attempt at home).

~~~~O        O~~~~
~~~O         O~~~~

The following shapes aren't boats because they can't float:


   O         O    
    O        O    

The Goal

Write a program that, when given an ASCII-art shape, outputs a truthy value if it boats, and a falsey value if it doesn't boat. This is code golf, fewest bytes wins.

  • \$\begingroup\$ Do you want this to be the simple version (if it displaces enough water it floats) or a more complex version (some of the air spaces may be filled as it sinks, but remaining air spaces are sufficient to keep it afloat). I'm thinking of examples with multiple air spaces with different height walls, so at a certain depth the water can only fill some of them. That is, the weight of the boat is too great to keep all of the air spaces empty, but the remaining ones are sufficient to keep it from sinking any further. \$\endgroup\$ Commented Jul 24, 2015 at 21:58
  • \$\begingroup\$ 1. Bearing in mind the example of the capsized boat: are we supposed to test all possible rotations of the input, or just the orientation in which it's supplied? 2. It would be good to have test cases which are right on the edge (one which floats by displacing exactly its mass, and one which is one unit too heavy). 3. Another corner case which isn't mentioned is discontiguous boats. Should we assume that the input is fully connected? \$\endgroup\$ Commented Jul 24, 2015 at 22:04
  • 1
    \$\begingroup\$ @trichoplax I am leaning towards the more complex version, where the boat is "lowered into" the water, which may float various parts until the equilibrium is reached. PeterTaylor I'll say that only the given orientation should be tested. Also, boats will always be contiguous. \$\endgroup\$
    – PhiNotPi
    Commented Jul 24, 2015 at 22:08
  • \$\begingroup\$ Why are the non-boat example not boats? Or do you mean they are boats that don't float? \$\endgroup\$
    – xnor
    Commented Jul 26, 2015 at 7:41
  • \$\begingroup\$ @xnor They don't float. It was supposed to be an extension of "if it floats, it boats" so the ones that don't float aren't boats. \$\endgroup\$
    – PhiNotPi
    Commented Jul 26, 2015 at 21:30
  • \$\begingroup\$ The boat has 13 O characters, and the material is twice the density of water. Doesn't it therefore need to displace 26 characters in order to float? Sure, this shape will float but it will sit lower in the water than you have drawn it. \$\endgroup\$ Commented Aug 4, 2015 at 15:35

Multiples - a wrap battle


Change cells in multiples to wipe out your opponent, while avoiding being wiped out yourself.

This is a 2 player game, played on a linear string of cells of length L that wrap in a loop. Counting along the loop eventually brings you back to where you started (after L steps). L will be fixed across all battles, and will be a reasonably large prime.

Each cell is controlled by player 1, player 2, or is neutral. These will be indicated as 1, 2 and 0 respectively.

Starting position

Player 2 starts with a cell at position 0 (since all are equivalent).

Player 1 starts with a randomly chosen cell from 1 to floor(L/2).

Player 1 moves first, reflecting the fact that player 1 has further to go to catch player 2.

Taking a turn

Each player begins with a stockpile of 0, and at the start of each turn the player's stockpile is increased by the number of cells that they currently control. The player then takes their turn. They choose any cell they control and specify a number N, which can be any non-negative integer up to and including the size of the stockpile. The stockpile is reduced by this number, and N loop cells are affected as follows:

Starting with the chosen cell as cell 0, each of the cells N, 2N, 3N, ... N*N are changed.

  • Choosing 0 means nothing happens, at zero cost.
  • Choosing 1 means the cell immediately after the chosen cell is changed, at a cost of 1.
  • Choosing 2 means the cell 2 cells on and the cell 4 cells on are changed, at a cost of 2.
  • Choosing 3 means the cells 3, 6 and 9 cells on are changed, at a cost of 3.
  • In general, choosing N changes N cells at a cost of N.

When a cell is changed it follows the following rules:

  • A neutral cell becomes the player's.
  • An enemy cell becomes neutral.
  • A cell already owned by the player becomes the enemy's

Large N

I expect most moves will choose N considerably smaller, but saving up would allow choosing N considerably larger than L in theory.

Choosing N=L means that all of the changed cells will be the same - the chosen cell, and it will be changed L times.

Choosing N=L-1 means that the L-1 consecutive cells before the chosen cell will all be changed (that is, every cell except the chosen one will be changed).


If a move leaves no enemy cells remaining, that player wins.

After 1000 moves any player who has more cells than their enemy at the start of 2 consecutive turns in a row (one theirs, one their enemy's, in either order) wins.

After 2000 moves the game is a draw (tie).

Input and output


At the start of a game the player's code will be called with a command line argument of 1 or 2 indicating which player they are (player 1 moves first and is represented by 1s in the loop string).

Each turn the player will be supplied with:

  • A string of 0s, 1s and 2s representing the loop.
  • An integer S representing the size of their stockpile.
  • An integer R representing the size of their opponent's stockpile.
  • An integer representing the number of turns taken so far (this will always be an even number for player 1).


The player should output 2 integers:

  • The cell C to play from, in the range 0 <= C < L.
  • The number of cells to change N, in the range 0 <= N <= S (their current stockpile size).

Sandbox questions

  • I like the idea of this being a 1 dimensional game, but I can also see it working on a 2d grid, where each move is applied both horizontally and vertically (either on a square L by L, or with 2 distinct large primes as side lengths). Does anyone have anything for or against either 1d or 2d?

  • Any recommendations on what input to provide? I was thinking at least the values of all the cells, but would a history also be good, or better to make the players decide what history to track for themselves rather than providing it? Alternatively they could be memoryless and decide purely based on the current cell formation.

  • Is the random starting position a good idea? Would it be better to fix the starting position at floor(L/2), ensuring this number is prime, and let the players taking turns to be player 1 balance out any bias?


Help Indiana Jones and his crew cross the bridge!

This codegolf will solve the Bridge and Torch problem. In this problem, there are multiple people (I'm thinking four) who must all cross a weak bridge to escape an evil dragon as quickly as possible. Because the bridge is weak, only two people can cross the bridge at a time. The whole crew is armed with one torch, which is necessary for 1 or 2 people to cross the bridge. Furthermore, each person takes a certain, integral amount of time to cross the bridge. When two people cross together, they must run at the rate of the slower person. The whole crew needs to quickly figure out how to get all the people across the bridge in the least amount of time to maximize their chances of survival.

Input A list of names of the crew (one word, a-zA-Z) and how long they take to cross the bridge alone.

Output An explanation of who crosses the bridge in which order so that the total time is minimized, and the total time.

Example Input: Indiana 5 Jones 10


Indiana, Jones 10

Input: A 1 B 2 C 5 D 8


A, B A C, D B A, B 15

I'm thinking of either just solving this problem with any number of people, or another version in which anyone not at the end (ie. on the first side or on the bridge) after the time limit dies, and the goal is to minimize the number of deaths.

  • \$\begingroup\$ If it's code-golf it's easier for you as the question poster. If you put a time limit, then different computers will achieve different amounts in that time limit, so you would need to run all the answers on your own computer to give them an official score. \$\endgroup\$ Commented Jul 3, 2015 at 16:45

Bad Lip Reading Generator

A malapropism is the substitution of one word for another that sounds similar, often as a way to make something sound unintentionally humorous. For example, "He's a wolf in cheap clothing" is a malapropism, since the expected word, "sheep's", got replaced by "cheap", which sounds similar but means something different.

A modern version of malapropism is to take scenes from movies and redub the dialog with different words that match the actors mouth movements as a parody. There is a YouTube channel called "Bad Lip Reading" that uses this technique.

I would like to apply the process to some old videos with subtitle files, then watch the videos with the sound turned down to turn it into a long series of malapropisms.

Using mouth movements gives a more flexible range of malapropism so there is some flexibility between different sounds.


Create a malapropism generator. I want to be able to feed text from subtitles into the generator and have text which is different, but still matches the mouth movements of the actors.


A string of English words, (already processed to remove punctuation and forced to uppercase).


A string of English words, (same format as input).


To simplify the challenge, all input words are in upper case, separated by whitespace, with all punctuation except apostrophes removed.

Lets agree to constraint what words "sound like", to be based on the CMUDICT. You may scrub the data so you don't have to worry about comments or special punctuation entries and remove stress numbers.

Lets also agree on the mouth-movements associated with the sounds, called "visemes". Here is a mapping used by Microsoft's SAPI library, which is itself based on Disney animation rules. Microsoft uses the same set of phonemes from ARPABet as CMUDict data.

#   ARPAbet Phoneme

1   AE AH
2   AA
3   AO
4   EH EY UH
5   ER
6   IH IY Y
7   UW W
8   OW
9   AW
10  OY
11  AY
12  HH
13  R
14  L
15  S  Z
17  DH TH
18  F  V
19  D  N  T
20  G  K  NG
21  B  M  P

You should be able to take each English word, convert to a set of phonemes, then to a set of visemes, then produce a list of words with matching visemes and randomly select one of the other words from the list. If a word doesn't match, or doesn't have any alternative, the original word should be copied to output.



Test Cases

Since the words are random, I have selected some pairs of words with unique pronunciation. Your function or program should always return one word when presented with the other:

Input            Output
"APOGEE"         "APACHE"
"LAMPS"          "LUMPS"
"SCORN"          "SCORED"
"WEPT"           "WEBBED"


  • You can write a full program or function.
  • Input should be taken from stdin or function parameters. Output should be printed through stdout or returned.


This is [code-golf]. Submission with least number of bytes, (not including data file(s)) wins.

  • 1
    \$\begingroup\$ Interesting challenge, but I have some small suggestions. 1. The example in the first paragraph (moths vs moss) is inconsistent with the definition which follows, and that could confuse. Maybe borrow one of the test cases, or mention The Importance of being Earnest? 2. Why not link to the YouTube channel? 3. For subheadings, ### is better than *. 4. Since the input is nicely cleaned, I can't see why you specify all input words are in the same case rather than all input words are in upper case. The latter would be more useful, since it matches the CMUDICT file. \$\endgroup\$ Commented Aug 20, 2015 at 17:22
  • \$\begingroup\$ 5. The mapping of ARPAbet to viseme ID is very long and offputting, and it's not really necessary. If you replace it by a list of groups (AE AH newline ... newline B M P) in preformatted text (indent by four spaces) then it will convey all the necessary information while taking a lot less space. 6. Talking of which, it might be worth mentioning ARPAbet to pre-empt questions in the comments. \$\endgroup\$ Commented Aug 20, 2015 at 17:22
  • \$\begingroup\$ 7. It's a good idea to be explicit that when you say randomly you mean with equal probability or (easier for those whose libraries give them random floats) with a difference between the greater and least probabilities of no more than 1%. 8. The test cases aren't very useful for testing. The most useful test cases will be where most of the words have one or two possible outputs. E.g. MINT CONDITION STAMPS becomes PINNED CONDITION STUMPS. CATERER is also a good test case because it has a repeated phoneme at the end of the word, which could catch some buggy regex-based approaches. \$\endgroup\$ Commented Aug 20, 2015 at 17:23



  • I'm not sure how well single language questions do. It automatically limits the question to those that already know the language, and those that are willing to learn just for this question. There's no need to limit to Chef with some of the magic this community can produce!

  • "selfish/demanding" sounds quite strong and could sound like a bit of a personal attack on Beta Decay. It certainly isn't intended like that, and I expect it will be accepted as intended, but is it better to err on the side of caution?

  • 4
    \$\begingroup\$ Is there any particular reason to limit the challenge to Chef? Writing code that mimics a real world cake recipe could be entertaining in other languages as well. \$\endgroup\$
    – Dennis
    Commented Sep 9, 2015 at 18:36
  • 2
    \$\begingroup\$ @Dennis, I suppose not! I wouldn't have thought it possible, but I've seen some of the magic this community can produce! \$\endgroup\$ Commented Sep 10, 2015 at 11:39
  • \$\begingroup\$ I feel like the best tasting submission might just be an actual cake recipe which acts as a no-op, with the actual printing merely tacked on somewhere (eg in Foo) \$\endgroup\$
    – Sp3000
    Commented Sep 11, 2015 at 4:12
  • \$\begingroup\$ @Sp3000, that's possible. I added that rule because with Chef, the ratios for ingredients are often way off. \$\endgroup\$ Commented Sep 11, 2015 at 6:12

Source code ecological footprint

You've just been hired by a German car manufacturing company. Your first task, as an engineer, is to write a program that computes the ecological footprint of source code.

The ecological footprint of a character is computed as follows (you can assume the source code is ASCII-encoded):

Write the character's ASCII code in binary, and count the number of 1's.

For example, A has a footprint of 2, but O is dirtier with a footprint of 5.

The global footprint of a program is the sum of the footprints of its characters.

Your program must accept a string as parameter, compute its ecological footprint, and output it.

There is a subtlety though. As you wish to enter a new, more restrictive market, you need to tune your program so that it behaves differently in "test mode". Thus:

The program should output 0 when it receives the string test as parameter.


The source code with the smaller ecological footprint wins (and yes, the answer test is forbidden!)

  • 2
    \$\begingroup\$ This anonymous company doesn't happen to be named Volt's Wagons, does it? \$\endgroup\$
    – Geobits
    Commented Sep 25, 2015 at 3:20
  • \$\begingroup\$ @Zach Sorry, I rolled back your edits - the horizontal lines were really harming readability ? and the fact that we output 0 only when we receive test is important ? \$\endgroup\$
    – Arnaud
    Commented Sep 25, 2015 at 3:33
  • \$\begingroup\$ You could have removed the hr tags.. Also, I added a lot of punctuation and grammar fixes.. I didn't removed the "output 0 only when we receive test" detail either? I only removed the redundant clause. \$\endgroup\$
    – Zach Gates
    Commented Sep 25, 2015 at 3:35
  • 2
    \$\begingroup\$ What's the expected output for an empty input string? I'd normally say 0, but "(and only when)" seems to disqualify that. \$\endgroup\$
    – Geobits
    Commented Sep 25, 2015 at 3:36
  • \$\begingroup\$ @Zach I've re-reported your changes. Thanks for your help! \$\endgroup\$
    – Arnaud
    Commented Sep 25, 2015 at 3:45
  • \$\begingroup\$ Can we assume that the input will never be empty? \$\endgroup\$
    – Zach Gates
    Commented Sep 25, 2015 at 6:08
  • \$\begingroup\$ @Zach I would accept empty input and output 0, as the footprint of an empty program is zero ? \$\endgroup\$
    – Arnaud
    Commented Sep 25, 2015 at 6:50

Group Students Into Pairs

Synopsis: A graph theory matching problem. Given a list of which students like and dislike each other, pair the students up to maximise the overal happiness of the classroom.


If you've ever been a teacher before, you've likely encountered the extremely frustrating experience that is getting students to do pair work. More often than not no one is happy with their partner, and the mood of the classroom suffers.

In this challenge, we're going to solve the enduring problem of pair work in classrooms. Here's how our system will work:

  1. Each student shall write down what students they are happy to work with, and which ones they are not happy to work with.
  2. We will take those lists, and generate student pairs such that the total happiness of the classroom is at its maximum.
  3. The students are now (mostly) happy!

So how is the happiness of the classroom calculated? For each student in each pair of students:

  • If a student's partner is in their "happy to work with" list, increase the happiness of the classroom by 1.
  • If a student's partner is in their "not happy to work with" list, decrease the happiness of the classroom by 1.
  • If a student is neutral towards their partner (not in either list), the happiness of the classroom does not change.

Here's a useful table that summarises the possible changes in the happiness with each pair of students:

| Student 1 Feeling | Student 2 Feeling | Happiness Modifier |
| Happy!            | Happy!            | +2                 |
| Happy!            | Neutral           | +1                 |
| Happy!            | Not happy...      | 0                  |
| Neutral           | Happy!            | +1                 |
| Neutral           | Neutral           | 0                  |
| Neutral           | Not happy...      | -1                 |
| Not happy...      | Happy!            | 0                  |
| Not happy...      | Neutral           | -1                 |
| Not happy...      | Not happy...      | -2                 |


First line of input is a positive integer n indicating the number of students to match up. n is always even. Following that are n lines, each line which has the format:

name likes dislikes

where name is the name of the student (which will only contain characters from [A-Za-z]), likes is a comma separated list of people he or she would be happy to work with, and dislikes is a comma separated list of people he or she would not be happy to work with. For instance:

Clarence Tiger,Anna,Jamal Amelia,James

This would indicate that Clarence is happy to work with Tiger, Anna, or Jamal; he is not happy to work with Amelia or James; and towards any other student he is neutral.

Another line:

Ilya Amelia,Clarence,Anna,Tiger,Jamal _

This would indicate that Ilya is happy to work with Amelia, Clarence, Anna, Tiger, and Jamal. For dislikes, we've used the special keyword _, which indicates that Ilya doesn't have anyone he is not happy to work with. Any remaining students Ilya would be neutral towards.


Output space separated comma separated pairs of names, where each name corresponds to a pair of students. The pairs should be such that the happiness of the classroom is maximised. Every student should be in exactly one pair.

Example Inputs and Outputs

Writing reference implementation. This is one of those types of questions where you can't really judge the correct output for an input "by eye".

Sandbox Questions

  1. This problem is quite difficult compared to typical code-golf fare, requiring two different algorithms to solve the weighted maximum matching problem. Is it too difficult for a code-golf? And if it is, what could make a better winning criterion?
  • \$\begingroup\$ It's certainly not too difficult for a code golf at present, because there are no time constraints so I could brute-force it. With time constraints I'd have to do some research before tackling it, but it's good to have the occasional code golf problem which can't be solved in 30 characters. \$\endgroup\$ Commented Jun 25, 2015 at 17:32
  • \$\begingroup\$ I would think the challenge would actually do well with a loose time constraint to prevent brute force. While you'd definitely get fewer answers, those answers would definitely be more interesting \$\endgroup\$ Commented Jun 27, 2015 at 1:55
  • \$\begingroup\$ "Jamal Amelia" -- Where is the comma? And I think that this would be fine for code-golf. BTW, add which all characters a name could have in the challenge. \$\endgroup\$
    – Spikatrix
    Commented Jun 27, 2015 at 9:42
  • \$\begingroup\$ @CoolGuy There's no space because Jamal is the end of the likes and Amelia is the start of the dislikes. I added in which characters a name can contain. \$\endgroup\$
    – absinthe
    Commented Jun 27, 2015 at 11:29
  • \$\begingroup\$ Cool Guy's question raises the point that you should be explicit about cases where a person has no likes, no dislikes, or neither. I.e. can trailing spaces be omitted? Can the entire line be omitted if the person has neither likes nor dislikes but is liked or disliked by someone else? \$\endgroup\$ Commented Jun 27, 2015 at 14:29

Approximate phi using Fibonacci numbers

As shown by Johannes Kepler, the quotient of successive Fibonacci numbers approaches phi.

Thanks, Wikipedia.

(where F(n) = the nth Fibonacci number)

The fine folks at Wikipedia also say that if you choose two different starting values for the Fibonacci sequence, this expression still holds.

Last, but not least, if you use a later number in the series in the numerator, you get some interesting properties:

Thanks again, wikipedia

The challenge

  • Create a full program or function that approximates phi using Fibonacci numbers.
  • The program or function will take a single integer, n (unless a bonus is applied). It will output to STDOUT as follows, stopping when it reaches n:

1/1=1 2/1=2 3/2=1.5 5/3=1.66666666 ... F(n+1)/F(n)=...

  • Fibonacci numbers must be calculated using iteration or recursion.
  • No built-ins / standard loopholes, and neither the square root function nor phi should appear in the source code.
  • It is OK if floating point limitation/integer overflow prevent accuracy beyond 4 or 5 digits, but you should use the most precise primitive data type (yes, double is one character longer than float).

There are two bonuses that you can earn, for a total of a 25% lower score:

  • Input two additional integers as starting values for the Fibonacci sequence. This will still converge on phi, though it may take a bit longer. Reward: -10%.
  • Input one additional integer for a in the above formula. This will result in the sequence converging to phi^a. Reward: -15%.


Total score is the size of the program, in bytes, minus any bonuses. Since this is , lowest score wins.

(Insert leaderboard snippet) (Insert example snippet)

Example implementation snippet:

document.getElementById("button").addEventListener("click", process, false);

function process() {
  //Store field values to vars
  var itrNum = parseInt(document.getElementById("itrNum").value);
  var prevNum = parseInt(document.getElementById("start1").value);
  var curNum = parseInt(document.getElementById("start2").value);
  var aNum = parseInt(document.getElementById("aVal").value);
  document.write("(Click \"Run\" to reset)<br><br>");

  //Iterate through each fibbonacci number
  for (var i = 0; i < itrNum; i++) {

    dispNum = getFutureItr(prevNum, curNum, aNum);
    document.write(dispNum + " / " + prevNum + " = " + dispNum / prevNum + "<br>");
    //prepare numbers for next iteration
    var tempNum = curNum + prevNum;
    prevNum = curNum;
    curNum = tempNum;

//Helper function for F(n+a)
function getFutureItr(prevNum,
  aNum) {
  var tempNum = curNum;
  for (var i = 1; i < aNum; i++) {
    tempNum = curNum + prevNum;
    prevNum = curNum;
    curNum = tempNum;
  return curNum;
<!DOCTYPE html>

  Iteration number:
  <input type="number" min=0 id="itrNum" value=20>
  <hr>Starting value 1:
  <input type="number" min=1 id="start1" value=1>
  <br>Starting value 2:
  <input type="number" min=1 id="start2" value=1>
  <hr>Value of a:
  <input type="number" min=1 id="aVal" value=1>
  <button id="button">Calculate</button>


  • \$\begingroup\$ There's a fibonacci tag. It's generally worth making it clear which of the two indexing conventions answers to use: F(0) = 0 or F(0) = 1? \$\endgroup\$ Commented Nov 2, 2015 at 14:37
  • \$\begingroup\$ Does the output need to be in the exact format 3/2=1.5? \$\endgroup\$
    – xnor
    Commented Nov 4, 2015 at 21:54

Counting the Pattern Unlocks


Upon thinking about this challenge harder, I've realized that it is fairly trivial. Unless I am really bad at counting (which I am liable to be), there are at least 2 ways and at most 4 ways to draw any given pattern.

I think that this makes the challenge considerably less attractive. For this reason, I am thinking of ways to spice it up. For this, I would like your feedback. Currently I am thinking of:

-->Changing the rules so that dots can be used multiple times.

Let me know what you think of this change to the challenge, or suggest other changes.

The Premise

Many modern smartphones have options that allow you to choose how you would like to unlock your phone. For example, my phone allows

  1. PIN input: a 4 digit number (low security)
  2. Pattern Unlock: connect the dots in a pattern (medium security)
  3. Password entry: enter a password (high security)
  4. Fingerprint.

When you elect this second option, you are shown a 3x3 grid of dots (9 dots total) that looks something like this

.    .    .

.    .    .

.    .    .

Instead of using dots, we will use numbers in the following fashion for ease of reference.

1    2    3

4    5    6

7    8    9

You are then prompted to connect dots to form a pattern. This process is subject to the following rules:

  1. The pattern must use at least 3 dots.
  2. The pattern must be one continuous connection, that is once you lift your finger, the pattern ends.
  3. Each dot may be used at most once (there is a quasi exception to this in rule 4)
  4. If you take three collinear dots, in connecting the outer two dots, you must connect the inner dot if it is not already used. For example, if you make the connection 1-3, if 2 is not already used, you are really making the connection 1-2-3. If 2 is already used, then you are just making the connection 1-3. This is where the quasi exception to rule 3 comes in. You are passing over 2 again, even though you have already used it.

I believe that these are all the rules. Note that some phones may use different rules, but if you think I am missing something important, please let me know.

The Task

Our goal is to count how many ways there are to draw a given pattern.

For example if you see the following pattern:


4    5    6

7    8    8

It could have been drawn in one of four ways:

1 --> 2 --> 3    or
3 --> 2 --> 1    or
2 --> 3 --> 1    or
2 --> 1 --> 3


You will be given a series of integers between 1 and 9 to stdin. They will represent connected dots on a grid.

The above example could be input via any of the following sequences:

1 2 3    or
3 2 1    or
2 3 1    or
2 1 3    or
1 3      or
3 1

If input is invalid, your program may do whatever it wants.


Your program is to output the number of ways there are to draw the pattern, as an ingeter, to stdout or equivalent. In the above example, the output would be


Wining Criterion

This is code golf, shortest code (bytes) wins.


Take off 20% if your answer also outputs all ways to draw the pattern (any understandable syntax acceptable).


(1) grid layout

1    2    3
4    5    6
|  /
7    8    9

possible inputs:

input>> 4 7 3
     >> 4 7 5 3
     >> 3 7 4
     >> 3 5 7 4
     >> 5 3 7 4
output<< 3

the ways are (for the bonus):

4 --> 7 --> 5 --> 3    or
3 --> 5 --> 7 --> 4    or
5 --> 3 --> 7 --> 4


4    5----6
|         |

input>> 3 2 1 4 7 8 9 6 5    or
     >> 3 1 7 9 6 5          or
     >> 5 6 9 7 1 3          or
     a couple others
output<< 3

example directions:

 3 --> 1 --> 7 --> 9 --> 6 --> 5   or
 5 --> 6 --> 9 --> 7 --> 1 --> 3   or
 2 --> 3 --> 1 --> 7 --> 9 --> 6 --> 5
 (or could include extra collinear points)

  • \$\begingroup\$ you are correct. Counting is just really hard apparently. Fixed (I think). \$\endgroup\$
    – Liam
    Commented Nov 4, 2015 at 9:03
  • \$\begingroup\$ I've done worse... This is what the sandbox is for :) \$\endgroup\$ Commented Nov 4, 2015 at 9:06
  • \$\begingroup\$ It's generally good advice to write an ungolfed reference implementation while sandboxing. This will help ensure test cases are consistent, and also will sometimes highlight potential problems/changes that none of us could spot without an implementation. \$\endgroup\$ Commented Nov 4, 2015 at 9:08
  • \$\begingroup\$ Nice challenge, by the way. \$\endgroup\$ Commented Nov 4, 2015 at 9:13
  • \$\begingroup\$ Okay, thanks. I'll work on an implementation \$\endgroup\$
    – Liam
    Commented Nov 4, 2015 at 9:24
  • \$\begingroup\$ Related and related. Might give you some ideas (or at least ensure that your claims about the pattern are consistent with theirs!) \$\endgroup\$ Commented Nov 5, 2015 at 21:51

Who is the Star Abuser?

In The Nineteenth Byte some people often star chat messages without any reason. You decided to go on a quest to find out who is the star abuser.

You logged the chat actions as a string, each action represented by a character (as you are a code golfer after all).

  • Every user is marked with a letter of the alphabet.
  • An uppercase version marks the user entering chat and a lowercase one marks his/her leaving the chat.
  • At the start there is no one at the chat room.
  • A star marks a starring. We assume that each person in the chat could have starred with the same probability when a starring happened. (E.g. if there are 2 users in the chat we assume both of them had 50% chance to star.)

An example log:


You should output one uppercase letter showing the letter of the user who has the highest number of expected starring. If there are multiple users, output exactly one of them.







This is code golf so the shortest entry wins.

  • \$\begingroup\$ As soon as you add IO and ping me. I will upvote this \$\endgroup\$
    – Xwtek
    Commented Nov 17, 2015 at 12:06
  • \$\begingroup\$ Example : MOA***a**oS**s*Cc > M \$\endgroup\$
    – Xwtek
    Commented Nov 18, 2015 at 9:50

Comedy of exceptions

Your goal is to demonstrate the shortest program or function that can throw 10 different types of errors/exceptions (I use the two interchangeably here) at runtime.

This question is only open to languages which have an object-oriented type system for errors. Furthermore, in the case of each error, a message including a clear identification of the exception's type must be printed. Evidently, it must also have at least 10 error types. Other systems such as an integer error code identifying the error, or all errors represented by strings are not acceptable.

Input is an integer from 0 to 9 inclusive. The program should reliably throw a different type of error for each input.

Methods which allow exceptions of arbitrary type to be thrown may not be used. E.g, throw ... .

Determining whether two errors are of different type (TODO: fill in detail of output)

Java: x and y print different stack traces, but are the same type, so they can't be used.

Python: UnboundLocalError ..... and NameError ....... would count as two types of error, since, although UnboundLocalError is a subclass of NameError, type() would give different results for the two.

C++: stoi("aaaa") printing ......... would be valid since the message gives std::invalid_argument. Integer division by zero would not since it crashes the program without a message informing of the error type


Please comment if you are aware of a language that is borderline on eligibility, blurs boundaries between error types, or has other loopholes.

  • \$\begingroup\$ Would exceptions from standard modules be allowed (e.g. from urllib.error import *)? How about third-party modules/libraries (e.g. django, boost)? Or even custom exception subclasses? \$\endgroup\$
    – grc
    Commented Nov 26, 2015 at 11:17
  • 1
    \$\begingroup\$ I don't know if I can find 10 different ones, but CJam can print a number of errors. Some of these are CJam-specific errors (empty stack, type mismatch; these tend to be displayed as "RuntimeException" but with a distinguishing error message) and some of them, I think, are just crashes happening in the interpreter exiting with a Java exception. How would that be treated? (I think it's also different between the Java and the JavaScript interpreter.) \$\endgroup\$ Commented Nov 26, 2015 at 15:01
  • 1
    \$\begingroup\$ To make this more specific, here are 11 different errors (with different error messages), but some are backed by the same exception type within the interpreter. Would these still count as different? pastebin.com/VJCiVYMf (Also note that CJam itself has no concept of exceptions... if there's an error it crashes... these are just the exceptions types used by the interpreter.) \$\endgroup\$ Commented Nov 26, 2015 at 15:14
  • 2
    \$\begingroup\$ I can think of a language which has exceptions but not an object-oriented type system: SML. (Haskell almost certainly has some exception monad too...). \$\endgroup\$ Commented Nov 26, 2015 at 21:05
  • \$\begingroup\$ @grc I think I will allow standard libraries, but not 3rd-party ones. Any method of defining and throwing a custom exception type should fall under the rule "Methods which allow exceptions of arbitrary type to be thrown may not be used." \$\endgroup\$
    – feersum
    Commented Nov 27, 2015 at 0:28
  • \$\begingroup\$ @MartinBüttner It appears that the are Java exceptions and that CJam does not have its own exception type system, meaning it cannot be used. \$\endgroup\$
    – feersum
    Commented Nov 27, 2015 at 0:29
  • \$\begingroup\$ @PeterTaylor HM-based type systems should be OK. Maybe I can find a better description than "object-oriented". \$\endgroup\$
    – feersum
    Commented Nov 27, 2015 at 0:31
  • 1
    \$\begingroup\$ @feersum Then you should probably clarify what you mean by "error" (because the first sentence says that both errors and exceptions are allowed... just because there's no way to catch the error doesn't mean that language doesn't have errors... and most of these errors are actually thrown by the interpreter on purpose, and not raised by Java due to the interpreter having a bug). \$\endgroup\$ Commented Nov 27, 2015 at 14:18
  • \$\begingroup\$ @sysreq The input is a number when determines which type of exception you should throw. \$\endgroup\$
    – feersum
    Commented Dec 10, 2015 at 23:24

Juggling without collisions

Determine if a siteswap juggling pattern is valid, meaning that no two balls land on the same beat. Fewest bytes wins.

Input: A non-empty list of positive integers.

Output: A consistent Truthy value for valid or Falsey value for invalid.

Siteswap is a notation for juggling patterns. Dividing time into units called beats, a siteswap pattern says how high to throw the ball each beat, measured in beats that it's airborne until you catch it. For example, the pattern

4 2 3


  • On the first beat t=1, throw the ball 4 beats high, so you catch it at t=5.
  • On the second beat t=2, throw the ball 2 beats high, so you catch it at t=4.
  • On the third beat t=3, throw the ball 3 beats high, so you catch it at t=6.

If we treat this pattern as a periodic sequence

... 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 ...

note that on every beat, you catch exactly one ball. But, in

 5 1 3 4 2 ...

the ball thrown for 5 beats at t=1 and the ball thrown for 3 beats at t=3 both come down at t=6, which we don't want (let's ignore that we have two hands). This happens whenever two numbers in the sequence have the same different as the number of beats between them, with the bigger on first. Note that this may happen across repetitions, like in 8 1 2, where the marked balls collide at *.

 v             v *
 8 1 2 8 1 2 8 1 2 8 1 2 ...

TODO: Test cases.

Sandbox: Does the explanation make sense? Is it too long for the challenge?

  • \$\begingroup\$ Related. :) \$\endgroup\$ Commented Dec 21, 2015 at 11:26
  • \$\begingroup\$ @MartinBüttner Those are some nice ASCII diagrams, mind if I steal them? \$\endgroup\$
    – xnor
    Commented Dec 21, 2015 at 11:32
  • \$\begingroup\$ Sure, if you don't mind them blowing up your spec. ;) \$\endgroup\$ Commented Dec 21, 2015 at 11:32
  • \$\begingroup\$ I think this challenge should still be happening. :) \$\endgroup\$ Commented Jun 19, 2016 at 21:16
  • \$\begingroup\$ @MartinEnder I've had this in the sandbox way too long, and don't have the energy to polish it up now. Do you want to take it? \$\endgroup\$
    – xnor
    Commented Feb 15, 2018 at 5:35

Elements with 100 ≤ Z < 1000

The International Union of Pure and Applied Chemistry (IUPAC) decided that it is necessary to have a systematic naming for the elements, even for those which had not been discovered. The rules for naming are:

  1. The name is derived directly from the atomic number of the element using the following Latin numerical roots:

    Number     Root
    ------     ----
    0          nil
    1          un
    2          bi
    3          tri
    4          quad
    5          pent
    6          hex
    7          sept
    8          oct
    9          enn
  2. The roots are put together in the order of the digits which make up the atomic number and terminated by 'ium' to spell out the name. The final 'n' of 'enn' is omitted when it occurs before 'nil', and the final 'i' of 'bi' and of 'tri' when it occurs before 'ium'.

  3. The symbol of the element is composed of the initial letters of the numerical roots which make up the name.

For this challenge, let us consider the elements having a three digit atomic number.


100 --> Unnilnilium
101 --> Unnilunium
111 --> Unununium
150 --> Unpentnilium
200 --> Binilnilium
500 --> Pentnilnilium
999 --> Ennennennium


  • Input can be taken from one of the following

    • stdin
    • Command-line arguments
    • Function arguments (One argument, as a string)
  • Input will contain either a valid IUPAC name of an element, or a valid IUPAC symbol of an element.


  • Output the corresponding
    • IUPAC name if the input is a symbol of an element.
    • symbol if the input is an IUPAC name of an element.


  • The input will contain a valid IUPAC name/symbol.
  • The first character of the symbol/name in input will be in upper-case and should remain capitalized in the output.
  • You are permitted to write a full program or a function.
  • There should be no unnecessary characters except an optional trailing newline character.

Test Cases

Unu            --> Unnilunium
Eee            --> Ennennennium
Enn            --> Ennilnilium
Bnb            --> Binilbium
Ubt            --> Unbitrium
Qsn            --> Quadseptnilium

Septenntrium   --> Set
Hexunbium      --> Hub
Octennilium    --> Oen
Bibibium       --> Bbb
Ununennium     --> Uue
Triquadpentium --> Tqp


This is , so the shortest submission (in bytes) wins.


Sandbox: What do you guys think about this challenge? Anything to improve? Did I miss anything?

  • \$\begingroup\$ For the title, maybe "Elements after Fermium", since that's element 100. \$\endgroup\$
    – isaacg
    Commented Dec 26, 2015 at 11:14
  • \$\begingroup\$ Omit the line "not relevant in this challenge" \$\endgroup\$
    – isaacg
    Commented Dec 26, 2015 at 11:15
  • \$\begingroup\$ Related: codegolf.stackexchange.com/questions/60208/… \$\endgroup\$
    – lirtosiast
    Commented Dec 26, 2015 at 23:13
  • \$\begingroup\$ @ThomasKwa Oh. Thanks! Didn't know that a similar challenge existed! \$\endgroup\$
    – Spikatrix
    Commented Dec 27, 2015 at 4:40
  • \$\begingroup\$ @isaacg Thanks! I made some changes now. \$\endgroup\$
    – Spikatrix
    Commented Dec 27, 2015 at 4:41

Rational Number to Repeating Numeral Conversion

As I'm sure you know, the decimal expansion of every rational number is either terminating—consisting of a finite number of digits, or repeating—consisting of infinitely many digits, but ending with a finite pattern that repeats itself indefinitely: for example, the decimal expansion of the rational number 1/6 is 0.1666..., where the sixes repeat forever. One way to represent this decimal expansion finitely and unambiguously, is to write the repeating part, called the repetend, enclosed in parentheses: going back to the previous example, under this scheme the number 1/6 is written as 0.1(6). We call this representation a repeating decimal. Of course, none of this is specific to base 10. More generally, we call such a representation, in any base, a repeating numeral. Note that, for the sake of this challenge, we use the term "repeating numeral" (or simply, "numeral") to refer to any numeral written using this scheme, whether or not it actually has a repeating part.


Write a program or a function taking a pair of integers, p and q, and returning a repeating numeral representing the rational number p/q. You may assume that p ≥ 0, and q > 0, so that p/q is never negative. The resulting numeral should be in base 10, unless you go for the relevant bonus below.

There is more than one possible numeral representing a given rational number. For example, the rational number 1/1 can be represented, among (infinitely many) other options, as 1, 1.0, 1.(0), 0.(9), and so on... For this challenge, however, we'd like the output to be unique. The following set of rules, which your program must follow, takes care of that:

  • When the integer part of the numeral is zero, there should be a single 0 before the radix point. For example, given the input 1/2, the output should be 0.5, and not .5.

  • The repetend, if exists, must begin after the radix point; that is, it shouldn't apply to the integer part. For example, given the input 10/9, the output should be 1.(1), and not (1).

  • The output should be finite and minimal, under the above rules. This is the most significant rule controlling the output, so it's worth highlighting some of its consequences:

    • There should be no leading or trailing zeroes. For example, given the input 3/2, the output should be 1.5, and not 01.5 or 1.50.

    • If the fractional part is zero, it should be omitted. For example, given the input 1/1, the output should be 1, and not 1.0.

    • If the repetend is zero, it should be omitted. For example, given the input 1/2, the output should be 0.5, and not 0.5(0).

    • When the input admits a terminating numeral, there shouldn't be an unnecessary repetend. For example, given the input 1/1, the output should be 1, and not 0.(9).

    • The repetend, and the rest of the fractional part, should not be superfluous; there shouldn't be any repetition in the repetend itself, nor in the repetend and the rest of the fractional part. For example, given the input 1/99, the output should be 0.(01), and not 0.01(01), 0.(0101), or 0.0(10).

As usual, you may not use any built-in or library functions aimed specifically at this problem.

Input and Output

You may take the input through the command line, through STDIN, as function arguments, or using an equivalent method. You may use any convenient format for the input, but make sure to specify it in your post. You may assume that p and q are no greater than 10,000,000, to the extent that it helps you to avoid overflow.

You may write the output to STDOUT, return it as the function's result or through an output parameter, as a string, or use an equivalent method.


This is code-golf. The shortest answer, in bytes, combined with the any of the bonuses, wins.


If, in addition to the requirements listed above, your program satisfies the requirements for any of the following bonuses, multiply your score by the specified amount.

×0.8 Bonus Support other bases
Your program should take a third parameter, b, which is an integer between 2 and 36, inclusive, and return the corresponding numeral in base b, instead of base 10. The letters of the alphabet, either in lowercase or uppercase, should be used as digits above 9. For example, given the input 1/2 and b=3, the output should be 0.(1). Note that base b applies only to the output—if your program takes its input in string form, it should interpret it in base 10.

×0.6 Bonus O(1) space complexity
Your program's space complexity should be O(1), where the unit of space is the amount of space required to hold the input. In other words, the amount of memory required by your program should, on a large scale, be proportional to the amount of memory required by the input. You may not use the fact that the input range is bounded when reasoning about your program's space complexity, other than to the extent of establishing the amount of space required by the input. If you go for this bonus, it is strongly advised that you include at least a brief explanation of your program, so that others can verify that it meets the criterion.

If your program does not print the output directly, but rather returns a string, you may ignore the space occupied by the string as long as your program only appends to the string, and doesn't modify or read from it otherwise. (Note that something like s=s+"0" is fine, even though it technically involves reading from the string.)

Test Cases

Each of the test cases below lists the input, p/q, on the first line, and the corresponding output on the second line. Some of the tests list a third parameter, b, which specifies a different base for the output. These tests are only applicable for the relevant bonus.

Short-Output Tests

Your program should solve each of the following tests in a matter of seconds.





















1/2 2

214/5467 13

214 5467 11

330420/335923 36

9322181/306936 28

123/6573 29

123/6573 21

Long-Output Tests

The following tests produce significantly longer output. Instead of listing their full output, only the MD5 checksum of the output if given. The checksum is calculated without a trailing newline, and using lowercase letters for digits above 9 (in the relevant test cases). If you want to see the full output for these tests, or to calculate the checksum under different conditions, you can use the test snippet below. Your program should solve each of the following tests in no more than a few minutes.











345/2234448 22

63451/2343324 3

93457/546464 2

678541/453524 9

4572/2341198 15

1/4821466 6

145/5821417 21

5472/2333645 33

Test Snippet

If you want to further test your submission, you can use the following test snippet to find the repeating numeral representation of arbitrary rational numbers, or to find the rational number corresponding to arbitrary repeating numerals. Note that the result can get very big, very fast, which can be a little much for your browser; in this case, you might want to uncheck the "Result" checkbox, and check the "MD5" checkbox, to only get the MD5 checksum of the output. Note also that you can resize the input and output boxes.

<style>* { font-family: sans-serif; }table { border-collapse: collapse; }table > tbody > tr > td { padding: 0px; }#status { display: none; }#status[loading] { display: initial; font-style: italic; }#main { display: none; width:100%; border-right:.7em solid transparent; font-size: 95%; }#main[loaded] { display: table; }#main > tbody > tr + tr > td { padding-top: .25em; }#main > tbody > tr > td + td { padding-left: .5em; }#main > tbody > tr > td:first-of-type { width: 4.25em; }.label { white-space: pre; }#flags { padding-left: 2.4em; font-size: smaller; }#flags > table > tbody > tr > td + td { padding-left: 1em; }#error { display: none; font-size: smaller; color: #880000; }#error[error] { display: initial; }#job_cancel, #job_throbber { display: none; vertical-align: bottom; }#job_cancel[working], #job_throbber[working] { display: initial; }#job_throbber > img { height: 1em; }#job_throbber[working] { padding-left: .3em; }#job_cancel[working] { padding-left: 1em; }#job_cancel > input { height: 1.8em; font-size: small; }input[type="text"], input[type="number"], textarea { padding: 0.25em; height: 1.4em; font-family: monospace; }textarea { width: 100%; }#base { width: 2.8em; text-align: right; }.output { background-color: #e4e4e4; border: none; }#length { width: 8em; text-align: right; }#md5 { width: 20em; text-align: center; }#result_container[active="false"] { display: none; }#md5_container[active="false"] { display: none; }</style></head><body><div id="status" loading>Loading...</div><table id="main" onkeydown="handle_key_down(event)"><tr><td id="input_label" class="label">Fraction:</td><td><textarea id="input" oninput="update(true)" spellcheck="false">123/456</textarea></td></tr><tr><td class="label">Base:</td><td><table><tr><td><input id="base" type="number" value="10" spellcheck="false" oninput="update(true)"></td><td id="flags"><table><tr><td><label><table><tr><td><input id="flag_result" type="checkbox" checked onchange="handle_flag('result')"></td><td>Result</td></tr></table></label></td><td><label><table><tr><td><input id="flag_md5" type="checkbox" onchange="handle_flag('md5')"></td><td>MD5</td></tr></table></label></td><td><label><table><tr><td><input id="flag_uppercase" type="checkbox" onchange="handle_flag('uppercase')"></td><td>Uppercase</td></tr></table></label></td><td><label><table><tr><td><input id="flag_trailing_newline" type="checkbox" onchange="handle_flag('trailing_newline')"></td><td>Trailing Newline</td></tr></table></label></td><td><label><table><tr><td><input id="flag_progressive_output" type="checkbox" onchange="handle_flag('progressive_output')"></td><td>Progressive Output</td></tr></table></label></td></tr></table></td></tr></table></td></tr><tr><td></td><td><span id="error"></span></td></tr><tr><td class="label">Length:</td><td><table id="length_table"><tr><td><input id="length" class="output" type="text" spellcheck="false" readonly></td><td id="job_throbber"><img src="https://i.sstatic.net/sHKZY.gif"></td><td id="job_cancel"><input type="button" value="Cancel" onclick="cancel_job()"><td></tr></table></td></tr><tr id="md5_container"><td class="label">MD5:</td><td><input id="md5" class="output" type="text" spellcheck="false" readonly></td></tr><tr id="result_container"><td id="result_label" class="label">Numeral:</td><td class="full_width"><textarea id="result" class="output" spellcheck="false" readonly></textarea></td></tr></table><script async type="text/javascript" src="https://gist.githack.com/anonymous/49705525fd01ba66c1ad/raw/c35226ad89444e3af07d0e505f7163df8574b860/repnum.js"></script>

  • \$\begingroup\$ Isn't space complexity technically going to be at least O(log (p+q))? \$\endgroup\$ Commented Dec 22, 2015 at 15:20
  • \$\begingroup\$ @MartinBüttner Technically, yes. I'm going to define the unit of space as the amount of space required to hold the input, thus implicitly dividing by O(log n). \$\endgroup\$
    – Ell
    Commented Dec 22, 2015 at 15:25
  • \$\begingroup\$ Ah, that's a very good idea. Much better than the usual attempts of "but ignore the memory used to store the input...". \$\endgroup\$ Commented Dec 22, 2015 at 15:26
  • \$\begingroup\$ I completely ignored your actual question: no, I wouldn't consider it a duplicate. ;) \$\endgroup\$ Commented Dec 22, 2015 at 16:28
  • 1
    \$\begingroup\$ I like the simplicity of the idea and would suggest keeping it simple by not requiring other bases or having a complexity limit. \$\endgroup\$
    – xnor
    Commented Dec 23, 2015 at 6:37
  • \$\begingroup\$ I agree with @xnor; I also think the bonuses are unnecessary. \$\endgroup\$
    – lirtosiast
    Commented Dec 30, 2015 at 21:44
  • \$\begingroup\$ @ThomasKwa Keep in mind that xnor's comment was written before the actual spec, when the bonuses were proposed as hard requirements (see the edit history.) I'm not likely to get rid of the O(1) space thing entirely—I think it makes for a much more interesting challenge (there's also a closely related challenge [edit history] that I don't want to get too close to.) TBH, I think the different bases bonus is mostly interesting in conjunction with the O(1) space bonus; I agree that in itself it doesn't add too much to the challenge. \$\endgroup\$
    – Ell
    Commented Dec 30, 2015 at 22:17
  • \$\begingroup\$ I'm not a fan of the bonuses. Also, I'm concerned there will be disagreements about the space complexity of built-ins. In some languages, implementation is not apecified, only result. It's also hard to tell n log n from linear because of constants. \$\endgroup\$
    – xnor
    Commented Dec 30, 2015 at 23:25
  • \$\begingroup\$ @xnor I'm going to go with common sense with regard to builtins: If the most obvious implementation of a builtin is O(1), then, unless someone knows otherwise, I'm fine with it. If the builtin does something nontrivial, that might not be O(1), then it's the poster's responsibility to show it's O(1), or not use it. I agree that reasoning about complexity is tricky, and complicates things: that's part of the challenge, and that's why I think it deserves a bonus. \$\endgroup\$
    – Ell
    Commented Dec 31, 2015 at 13:12
  • \$\begingroup\$ The space complexity required to hold the input is O(n), not O(1), since n is conventionally the input length, and O(1) is a constant that does not depend on the input. \$\endgroup\$
    – xnor
    Commented Dec 31, 2015 at 17:14
  • \$\begingroup\$ @xnor We can use whatever "frame of reference" we want when measuring complexity. If we define the unit of space to be the amount of space required by the input, then a complexity of O(1) simply means that space usage has to be proportional to the space occupied by the input, which might (in "absolute" terms) be fixed, or might depend on the actual value of p and q. Specifying it this way allows us to define the complexity requirement uniformly, without worrying about the details. \$\endgroup\$
    – Ell
    Commented Dec 31, 2015 at 19:40
  • \$\begingroup\$ @xnor, ThomasKwa, Anyway, having thought about it some more, I might end up dropping the bonuses, and doing the complexity thing out-of-band as a bounty. I'm going to leave this in the sandbox for a while longer, at least until next year... Happy new year! \$\endgroup\$
    – Ell
    Commented Dec 31, 2015 at 19:42
  • \$\begingroup\$ No, that's like saying we define 2 to be 3 and then 2+2=6. O(1) means O(1). 1 is not a variable. Readers will get confused if you redefine existing notation. \$\endgroup\$
    – xnor
    Commented Dec 31, 2015 at 19:46
  • \$\begingroup\$ How if my program allocates p+q+n space with n constant and unit space is byte? \$\endgroup\$
    – Xwtek
    Commented Jan 1, 2016 at 2:08
  • \$\begingroup\$ Make all bonus mandatory. \$\endgroup\$
    – Xwtek
    Commented Jan 1, 2016 at 2:08

This challenge was closed, because it was way too broad, but, in the comments, SuperJedi224 suggested a slightly different challenge that I thought was a really good idea, so I'm stealing it and posting it here.

Write a text editor in 2000 bytes or less

Write a text editor in 2000 bytes or less. It should support loading and saving files (or something else if your language doesn't support that, maybe?), modifying text, and displaying the contents of a file that's currently open in some format.

Sandbox questions

  • I'm not sure if 2000 bytes is the right number. SuperJedi224 originally suggested 10000, but that seems to me like too many.
  • Should some features be required, or should it just be by votes? Will votes take care of possible submissions that aren't actually text editors?
  • Should there be some kind of bonus for shorter submissions? Maybe an extra point for every 20 or so bytes you don't use? No, there probably shouldn't be.
  • Should languages that don't support file operations be allowed?
  • \$\begingroup\$ This is still very broad, and I think I would vote to close as off-topic, as this is essentially a UX contest, which isn't much different from an art contest. \$\endgroup\$ Commented Jan 6, 2016 at 15:55
  • 1
    \$\begingroup\$ I would recommend either an upper limit on bytes, or plain code golf. Trying to be somewhere in between with a bonus seems awkward. \$\endgroup\$ Commented Jan 7, 2016 at 0:02
  • 1
    \$\begingroup\$ @trichoplax I agree. Plain code golf won't work unless we can create a much more precise specification, and that doesn't seem as interesting as a popularity contest, so I guess it should just be an upper limit. \$\endgroup\$
    – KSFT
    Commented Jan 7, 2016 at 0:42
  • 1
    \$\begingroup\$ I think that the more precise you make the requirements, the more the voting can reflect how well the code fulfills these, rather than just being about arbitrary popularity. The more open ended the popularity criteria, the more likely the question will be closed. \$\endgroup\$ Commented Jan 7, 2016 at 0:56
  • \$\begingroup\$ That's a good point. Do you have any suggestions for criteria? \$\endgroup\$
    – KSFT
    Commented Jan 7, 2016 at 0:58
  • \$\begingroup\$ Whatever limit you choose, there will be some languages which are excluded by this and other languages for which the limit is too high to provide any restriction. So instead of trying to suit all languages, it might be easiest to just think about the readers of the answers - how much code do you want them to have to read through for each answer? \$\endgroup\$ Commented Jan 7, 2016 at 0:59
  • \$\begingroup\$ I guess you can add criteria gradually while it's here in the sandbox until it seems ready. What's the bare minimum it should be able to do? Do you just want keyboard input or mouse input too? Are there any shortcuts that should be included? \$\endgroup\$ Commented Jan 7, 2016 at 1:01
  • \$\begingroup\$ Not sure if this will be relevant, but just as a rough guide, this list of small text editors includes Emacs in 2000 lines of C. I'm guessing 2000 bytes will be more than enough for a very basic text editor in most languages. \$\endgroup\$ Commented Jan 7, 2016 at 1:22
  • 3
    \$\begingroup\$ I recommend doing this as a code-golf challenge, an upper limit just discourages the use languages where you are not sure whether you make it under that limit. Then also please make precise requirements, my suggestion: accept filename via stdin, file should contain printable ascii characters only, display blinking(or static) cursor, display should have a certain width (given number of characters) and enforces line breaks if the lines are longer, navigation via arrows, enable backspace (and if you want delete) \$\endgroup\$
    – flawr
    Commented Jan 7, 2016 at 21:13

Stitch a Picture

A few weeks ago, I asked Stitch a picture. Since then:

  • The question has received several upvotes and no downvotes - hopefully an indication that the community thinks this is as interesting as I do
  • No complete answers
  • Several interesting comments - in particular this one from @bazzargh

In short it looks like this question is a lot harder than I though it would be. It turns out from @bazzargh's comment that I have stumbled into an area of current research, and that perfect solutions are not so easily attainable as I had assumed.

With that in mind, I think its time I took this back to the sandbox to make this into the decent question that I think the subject deserves - and I think I need some community help with that.

I am posting several possibilities I am considering as comments. Vote for these comments as you feel appropriate, and/or add your own suggestions.

I'm going to Yosemite this weekend (woohoo!) so will probably pick this up again next week.


I have relinquished control of this question by putting it in Secret Santa's Sandbox.

  • 2
    \$\begingroup\$ @Will pointed out that padding the original picture with black boundaries possibly makes the problem harder. Instead we can have the original picture be cropped down to the nearest 100x100 pixel multiple and not worry about black boundaries at all \$\endgroup\$ Commented Oct 24, 2014 at 17:49
  • 4
    \$\begingroup\$ @MartinBüttner suggested turning this into a code-challenge and scoring based on the number of correctly placed tiles. Given that perfect solutions appear to be hard to come by in general, this is probably a better scoring criteria \$\endgroup\$ Commented Oct 24, 2014 at 17:50
  • 4
    \$\begingroup\$ Briefly reviewing the paper cited in @bazzargh's comment I see that my problem is even more complex, in that the tiles are also randomly rotated. Since this is complicating the problem beyond current research, I think it would be good to remove the rotation part completely. \$\endgroup\$ Commented Oct 24, 2014 at 17:50
  • 5
    \$\begingroup\$ Note that I didn't suggest scoring by correctly placed tiles but by correctly aligned edges. That's a huge difference, and in your version you could basically correctly assemble almost the entire picture, but still get 0 score if the chunk you've assembled correctly is off by a tile (since there's no indication where it goes unless you manage to get W tiles next to or H tiles on top of each other. \$\endgroup\$ Commented Oct 24, 2014 at 23:44
  • \$\begingroup\$ @MartinBüttner Yes, that is a better idea. \$\endgroup\$ Commented Oct 24, 2014 at 23:46
  • \$\begingroup\$ @DigitalTrauma I suggest only allowing translation (no rotation) of the tiles, which simplifies it somewhat, but I suspect still difficult enough to be a challenge. \$\endgroup\$
    – flawr
    Commented Jan 8, 2016 at 17:23
  • \$\begingroup\$ Taken codegolf.meta.stackexchange.com/questions/2140/… \$\endgroup\$
    – user63187
    Commented Jun 5, 2017 at 23:20

Addition of doubles... without doubles

For this challenge, you must write a GOLF assembly program that takes two IEEE 754 double-precision numbers and returns their sum.

The Format

IEEE 754 doubles use 8 bytes to store a floating-point value. The memory is laid out like this:


For the purposes of this challenge, all numbers will be in big-endian, and you won't have to worry about overflows or underflows. Addition works roughly like this (I won't go into all of the details):

  1. Align the two numbers to a common exponent.
  2. Add the fractional parts, taking into account the sign.
  3. If the addition overflows, then change the exponent to match.


Your program will receive 16 bytes of input. The first 8 represent the (big-endian) first number, and the rest represent the second number. Your program will return 8 bytes representing the sum of the two.


  • This is , so the program that completes the task with the least cycles wins.
  • The score of an answer is the mean number of cycles required for adding uniformly distributed numbers in [-10^64, 10^64].
  • You must test with at least 2500 trials.
  • Your code doesn't have to handle infinities/NaNs.
  • Your GOLF binary (after assembling) must fit in 4096 bytes.

Meta Questions

  • Do I have too many/too few trials?
  • Is there something that I overlooked?
  • Is there a more fitting title?
  • How much explanation should I provide? I don't want this question to turn into a Wikipedia article, but questions requiring external resources are generally frowned upon.
  • Is dead?

HTML Obfuscation

Write a program or function that takes HTML as a string as input and outputs "obfuscated" HTML. Leave the text between the <s and >s unchanged, but escape all other text.

  • You can assume that the < and > characters will only be used to open/close HTML tags.
  • You can safely leave any text between these characters alone. However, any text not between those characters should take on the form <ampersand><pound><ascii-encoding><semi-colon>.
  • You do NOT have to support self closing tags.

Test cases:


<div>Hello World</div>




ABC<input type="text">DEF<div>


&#65;&#66;&#67;<input type="text">&#68;&#69;&#70;<div>

Note: it's ok that the HTML is invalid


eee<div data-bracket=">">eee


&#101;&#101;&#101;<div data-bracket=">&#34;&#62;&#101;&#101;&#101;

Note: here your program would mess up the HTML. That's ok for the purposes of the challenge.

This is code golf, so the shortest program wins.

  • \$\begingroup\$ I think you should be more specific about what exact subset of HTML needs to be handled correctly (and include test cases that cover all of it). \$\endgroup\$ Commented Feb 12, 2016 at 15:24
  • \$\begingroup\$ @MartinBüttner thanks for the feedback. Do you think the edits clarify the challenge? \$\endgroup\$ Commented Feb 12, 2016 at 15:43
  • 1
    \$\begingroup\$ Basically: take a character and return the hexadecimal HTML entity. \$\endgroup\$ Commented Feb 13, 2016 at 20:08

Play Flippy Bit

There's a simple game called "Flippy Bit and the Attack of the Hexadecimals from Base 16", originally made as an April Fool's prank in 2014.

The premise is simple: Enemies enter the field from the top. Each one has a hexadecimal number, and are destroyed when the player's binary number matches. For example, an enemy with number 2Ah = 00101010b would be destroyed as soon as the user's number is 00101010. Of course, enemies can only be destroyed after they enter the screen.

The player manipulates their binary number by flipping individual bits with the qwertyui keys, where q is the most significant bit. Each press flips the bit at that location. Therefore, the 2A enemy above will explode if, starting from 0, the player presses etu in any order. When an enemy explodes, the player's number is reset to 0.


Given a list of enemies, determine a sequence of keypresses that can destroy all enemies in the order given. This isn't as simple as it seems: if you're trying to destroy 3 but there's another enemy called 2 on the board, you'll need to press i before u. Your algorithm must terminate within a bounded time.


A list of strings of hex digits 0123456789ABCDEF, with each string 1 or 2 digits long, and where the 2-digit strings have no leading zero. You may also take the input in a reasonable format other than a list; for example, newline-separated. The input will always represent a solvable configuration.


A string representing the sequence of keypresses.

Test cases

Note that there are multiple possible outputs for most inputs.

2A 01 02 04 08 10 20 40 A0 88

[add more test cases]

Verify your solutions with the following Python:

[add verification code]

This is , so the shortest solution in bytes wins.

  • \$\begingroup\$ This may or may not be an excuse to award a bounty to the highest Flippy Bit score. \$\endgroup\$
    – lirtosiast
    Commented Jan 20, 2016 at 18:13
  • 3
    \$\begingroup\$ I had no idea that the qwertyui keys would flip the bits. This would actually make kind of a cool esoteric language, however. \$\endgroup\$ Commented Jan 21, 2016 at 3:49
  • \$\begingroup\$ The statement that "destroy[ing] all enemies in order ... isn't as simple as it seems" puzzled me for a while, because I couldn't see what was wrong with the simple approach of setting the bits from the least significant to the most significant. Having thought about it, I presume that what's missing is a statement that the order in question is the order in which the enemies are presented in the input. But then an input like 03 01 02 is impossible to solve, so you also need to address insoluble inputs. \$\endgroup\$ Commented Jan 25, 2016 at 12:15
  • \$\begingroup\$ @PeterTaylor Actually, it's not! quiq. The point of this is some sort of search. \$\endgroup\$
    – lirtosiast
    Commented Jan 25, 2016 at 14:58
  • \$\begingroup\$ ff 01 02 04 08 10 20 40 80 then. (Although I see you've addressed the issue, so this comment is only for completeness). \$\endgroup\$ Commented Jan 25, 2016 at 16:06
14 15
17 18

You must log in to answer this question.

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