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

4705 Answers 4705

29 30
32 33

Wargame Tank Simulation

Some of you may have heard of the Wargame series of computer based real time strategy game. These games pit teams of players with primarily cold war era units to see how a hot cold war would have played out. The goal of this challenge is to simulate a tank battle in these games.


  • Two "tanks" (one red and one blue) will be entered into your program or function. Each tank is classified by a rate of fire, accuracy, armor value, and attack power value.


From the inputs above, simulate the two tanks fighting. You will do this by having each tank fire according to its rate of fire. If it hits (randomly determined by accuracy), a tank will do damage according to the armor value of its target and its own attack power. The formula for damage is floor[(attackpower - armor)/2]. Therefore a tank with 10 attack power against a tank with 5 armor would do 2 damage.

Tank crews also have morale, which follows the following rule

  • There are four possible morale values; calm, worried, scared, and panicked. Tanks always start calm. These names do not need to be in your code, in the sample below I've used calm = 1, worried = 2, etc.
  • Each morale value reduces the accuracy as follows: Calm -> 100% (no change), worried -> 75%, scared -> 50%, panicked -> 25%. Therefore a panicked tank which normally has 60% accuracy now has 0.25 * 0.6 = 15% accuracy
  • Each hit by the opposing tank degrades morale by one level, each miss upgrades the morale by one level.

For example:

morale: calm  |  worried  |  calm  |  worried  |  scared
hit:         hit         miss     hit         hit


  • Input should be two parameters to repesent each tank (I've used two tuples in the example below). Inputs may be provided in any order, just be sure to state which one is which. Input may be provided by user input via STDIN, read from a file, or parameters passed to a function call.
  • Each tank starts with 10 health.
  • Rate of fire will either be 8.5, 7.5, 6.5, 6, or 5 seconds between shots.
  • Tanks start loaded, so each fires at time = 0. Because Communists are sneaky, red fires first.
  • Accuracy must be randomly rolled.
  • Ineffective hits (hits which do no damage) have an effect on morale! (because it probably sounds terrifying)
  • Naturally since we want to see the action, output will be an update after each shot. The update will contain the time of the shot, whom it was made by (red or blue), health of both tanks, and the morale of both tank crews. Output maybe be presented in any format so long as it contains all of the required information in a human readable fashion (items must be delimited in some way). Similar to input, please describe your output format in the answer.
  • Engagements are limited to 100 seconds. If you play the game you know this is because a plane has swooped in by then. For our purposes if both tanks are alive at this point, it is a draw.
  • After one tank reaches 0 health (or after 100 seconds), print which tank is victorious ("Red" or "Blue") or "Draw" if appropriate. I don't care about trailing whitespace or newlines.
  • Printint output may be printing to STDOUT or writing to a file
  • Shortest answer in bytes wins

Sample Python Implementation

import random, math

def Shot_Result(acc, morale, power, armor):
    Morale = {1: 1., 2: 0.75, 3: 0.5, 4: 0.25}
    actual_acc = acc * Morale[morale]
    roll = random.random()
    if roll < actual_acc:
        dmg = max(0,math.floor((power-armor)/2))
        dmg = -1
    return dmg
def main(Red, Blue):
    red_rate, red_acc, red_armor, red_pow = Red
    blue_rate, blue_acc, blue_armor, blue_pow = Blue
    red_health = blue_health = 10
    red_morale = blue_morale = 1
    red_shots = [("Red", shot/100.) for shot in range(0,10000,int(red_rate*100))]
    blue_shots = [("Blue", shot/100.) for shot in range(0,10000,int(blue_rate*100))]
    Shots = sorted(red_shots + blue_shots, key=lambda x: x[1])
    print "{:^6}|{:^6}|{:^12}|{:^12}|{:^12}|{:^12}|".format("Shot","Time","Red Health","Blue Health","Red Morale","Blue Morale")
    for shot in Shots:
        if shot[0] == "Red":
            dmg = Shot_Result(red_acc, red_morale, red_pow, blue_armor)
            if dmg >= 0:
                blue_health -= dmg
                blue_morale = min(blue_morale+1,4)
                blue_morale = max(blue_morale-1,1)
            dmg = Shot_Result(blue_acc, blue_morale, blue_pow, red_armor)
            if dmg >= 0:
                red_health -= dmg
                red_morale = min(red_morale+1,4)
                red_morale = max(red_morale-1,1)
        print "{:^6}|{:^6}|{:^12}|{:^12}|{:^12}|{:^12}|".format(shot[0], shot[1], red_health, blue_health, red_morale, blue_morale)
        if red_health <= 0:
            print "Blue tank is victorious!"
        if blue_health <= 0:
            print "Red tank is victorious!"
        print "It's a draw!"

Sample Output (Yours does not need to be this fancy)

 Shot | Time | Red Health |Blue Health | Red Morale |Blue Morale |
 Red  | 0.0  |     10     |    5.0     |     1      |     2      |
 Blue | 0.0  |     10     |    5.0     |     1      |     2      |
 Blue | 6.5  |     10     |    5.0     |     1      |     2      |
 Red  | 8.5  |     10     |    5.0     |     1      |     1      |
 Blue | 13.0 |    5.0     |    5.0     |     2      |     1      |
 Red  | 17.0 |    5.0     |    5.0     |     2      |     1      |
 Blue | 19.5 |    5.0     |    5.0     |     1      |     1      |
 Red  | 25.5 |    5.0     |    5.0     |     1      |     1      |
 Blue | 26.0 |    0.0     |    5.0     |     2      |     1      |
Blue tank is victorious!
  • \$\begingroup\$ Its a good challenge, but you need to define your input/outputs a little more. I'd recommend indicating that tanks are passed in as a tuple/list, which tank is passed in first, and then define what the functions should return if red wins/blue wins/tie. \$\endgroup\$ Commented Mar 28, 2016 at 15:32
  • \$\begingroup\$ @NathanMerrill, I've made some slight updates to the rules. I want to keep things open as I often find myself frustrated with arbitrary I/O restrictions. \$\endgroup\$
    – wnnmaw
    Commented Mar 28, 2016 at 15:58
  • \$\begingroup\$ Flexible I/O is the way to go :) Looks good from my end. \$\endgroup\$ Commented Mar 28, 2016 at 16:05

Diagonals of an Array

The k-th diagonal of a two-dimensional array is a list of all elements in positions (a,a+k). Your task is to output all of the diagonals.

For example, the diagonals of




Which can be visualized thusly:

k -2-1 0 1 2 3
    \ \ \ \ \ \
     \ \ 3 1 4 1
      \ \ \ \ \
       \ 5 9 2 6
        \ \ \ \
         5 3 5 8


A rectangular nested array or 2D array of positive integers, which will be nonempty.


Its diagonals in any consistent order.

Test cases





Maybe a second question about n-dimensional arrays?

  • \$\begingroup\$ I suggest a requirement that the order of the output diagonals be consistent (the same irrespective of input); and add a row matrix and column matrix as test cases \$\endgroup\$
    – Luis Mendo
    Commented Mar 26, 2016 at 18:21
  • 1
    \$\begingroup\$ Now almost a duplicate. Also, Jelly has a 2-character built-in for this. (Just to let you know.) \$\endgroup\$ Commented Apr 6, 2016 at 8:51

Help! Everything is in Wingdings!

Your task is to write a program or function that converts wingdings to a readable font. The input to the program will be the path to a png file with between 1 and 10 wingdings characters. Your output should be the message contained in the wingdings characters.


Each test case will be a screenshot of the message as rendered in Microsoft Word (Black text on a white background, size 36, and 100% zoom). The image will be cropped to the bounding box of the message.

[insert 20 test cases, 2 of each size between 1 and 10]

[insert link to test cases + reference images]


(% of characters right in test cases)*10 - code length

(Highest score wins)


  • Standard loopholes apply.
  • No catering to the test cases.

(Note that this is just a concept for a challenge. I will expand the challenge if this receives a positive response).

  • \$\begingroup\$ @EasterlyIrk The input is an image containing wingdings characters. \$\endgroup\$
    – Daniel M.
    Commented Apr 10, 2016 at 3:34
  • \$\begingroup\$ Related \$\endgroup\$
    – Leaky Nun
    Commented Apr 10, 2016 at 3:35
  • \$\begingroup\$ @KennyLau This is different because the test cases will have up to 10 characters in the same image (and catering to the test cases is a standard loophole). I'll work on this more tomorrow. \$\endgroup\$
    – Daniel M.
    Commented Apr 10, 2016 at 3:44
  • \$\begingroup\$ The description of the image seems underspecified to me. Will the characters all be the same font size? How will they be laid out? Colours? Anti-aliasing? \$\endgroup\$ Commented Apr 10, 2016 at 21:36
  • \$\begingroup\$ What is the subpixel rendering setting? \$\endgroup\$ Commented Apr 11, 2016 at 10:22
  • \$\begingroup\$ @JanDvorak I'm not completely sure, so it's probably at whatever the default for Windows 10 is. If needed I can run the images through a program that creates a 1-bit image. \$\endgroup\$
    – Daniel M.
    Commented Apr 11, 2016 at 10:56

Find point on the Hilbert curve

The Hilbert curve space filling curve. It is a limit of recursive approximations. Being spacefilling means there is a parametrization of the curve which is continuous. So we can map the interval [0,1] continuously to the unit square [0,1]x[0,1]. Let us call this map h. (Note that the image of the [0,1] is not the complete [0,1]x[0,1] but rather a dense subset. E.g. (.5,.1) is obviously not in the Hilbert curve, as it is not in any of the approximations.)

Your task is now to write a progarm that given a value in [0,1] to return the corresponding value unit square [0,1]x[0,1], where h(0)=(0,0) and h(1)=(1,0), and h(.5) = (.5, .5)


  • This could also be done backwards.
  • Test cases to be added.
  • \$\begingroup\$ Are forwards and backwards sufficiently different tasks to make this two separate questions? \$\endgroup\$ Commented Apr 11, 2016 at 20:14
  • \$\begingroup\$ I just thought about this: the 'backwards' challenge would be relatively difficult, as h is continuous but only injective, but the inverse is not continuous anymore. So I think this direction is the better suited one for a challenge. \$\endgroup\$
    – flawr
    Commented Apr 11, 2016 at 20:45
  • \$\begingroup\$ Yes the backwards challenge would have more than one valid output. Maybe 4? You could just ask for any 1, or all (4?) or as many as exist (I'm guessing the 4 corners have only one answer). Forwards seems more than enough of a challenge to start with though. \$\endgroup\$ Commented Apr 11, 2016 at 21:19
  • \$\begingroup\$ I'd recommend either a formula or a reference implementation to make the correct output explicit. The Hilbert curve is fairly easily confused with similar-but-not-quite-the-same curves. \$\endgroup\$ Commented Apr 11, 2016 at 21:21
  • \$\begingroup\$ @trichoplax Yes I'm certainly going to add a reference. What other curves do you have in mind? \$\endgroup\$
    – flawr
    Commented Apr 11, 2016 at 21:32
  • \$\begingroup\$ I was thinking of curves like the Moore curve but now that I look it up, I see that answers using this would be ruled out by test cases using the end points (0 or 1). \$\endgroup\$ Commented Apr 12, 2016 at 0:05
  • \$\begingroup\$ Right, I was not aware of this curve and it certainly looks quite similar! \$\endgroup\$
    – flawr
    Commented Apr 12, 2016 at 8:06
  • \$\begingroup\$ I really like it because its ends meet so it can form a closed loop. \$\endgroup\$ Commented Apr 12, 2016 at 12:55

KOTH: Black Hole

I've recently seen this video (by Tom Scott), in which it featured a game called Black Hole. Let's play that for KOTH!

Overview (the original version in the video)

  • Two "players" have 10 counters, each labelled 1 to 10.
  • These two players take it in turns to place counters in increasing order on a grid of 21 "spaces" arranged in a triangle (i.e. a triangle with 6 rows).
  • Once all 21 counters have been placed, the remaining space that hasn't been used is the "black hole", and the dots surrounding the black hole are "sucked in".
  • The person with the lowest sum of the counters "sucked in" wins.

For the purpose of KOTH, the triangular grid will consist of 120 spaces (i.e. the triangle "pyramid" will be 15 rows high), and each player will have 59 counters (Yes, that means that there will be 2 black holes).

Point System

  • Win: 10 points, Draw (very rare): 3 points, Loss: no points


  • The bot must output a number between 1 and 120 each turn, and a "counter" with the same number as the current no. turn made by the bot will be placed there.
  • After 118 turns, the black holes activate, the score is counted, and points are awarded.

NOTE: If there is no output within 5 seconds, the bot immediately loses.

"Battle" System

  • The competition will be a round-robin, except each bot battles every other bot 5 times.
  • The top three bots will then play each other 10 times each.
  • The final winner is the winner of the competition.

Info on controller stuff

The controller will be in Python, but I don't have the first clue how to make an controller. Any help?

  • \$\begingroup\$ Well I think that you have to choose a way of inputting and outputting data first to have an idea how to write the controller. If it's going to be single language KOTH you can just ask people to write you functions/classes in some way and you can attach those to a regular program performing the game. On the other hand the challenge seems simple enough that you may just give the input as arguments to an execution of the programs and read output for them (calling an instance of the bot for each move). \$\endgroup\$
    – Lause
    Commented Apr 11, 2016 at 10:12
  • \$\begingroup\$ Yeah... I'll probably do it as an input/output thing, regardless of language. \$\endgroup\$
    – clismique
    Commented Apr 11, 2016 at 10:55
  • 1
    \$\begingroup\$ 1. I think you've changed the size of the board so many times that there are figures in the question from at least three different board sizes. 2. In the video, the counters must be placed in increasing order of value, but the question doesn't mention this anywhere. 3. From my experience of other koths, best-of-50 is going to be far too time-consuming. I suggest making it best-of-5 or at most best-of-7. \$\endgroup\$ Commented Apr 11, 2016 at 21:39
  • \$\begingroup\$ Ah. Thanks for the tips... sorry if it's confusing. Will edit. \$\endgroup\$
    – clismique
    Commented Apr 12, 2016 at 1:10
  • \$\begingroup\$ Interesting game. There is discussion about the different options for input and output on meta, and also there's a general tips for writing KotHs. \$\endgroup\$ Commented Apr 12, 2016 at 13:14
  • \$\begingroup\$ So... if there are multiple languages, will I have to install other things that can run those languages? That's a lot of stuff to prepare for, considering it's only for a short while (maybe for longer if I keep on doing KotHs). \$\endgroup\$
    – clismique
    Commented Apr 13, 2016 at 10:13

Generate a waveform from audio

Given an audio file, in any common audio format (such as MP3, OGG, WMA, M4A, or WAV) of your choice, as input, output an image, in any common image format (such as PNG, JPG, PPM, BMP, SVG, or GIF) of your choice, of a waveform representing the audio input.

Here is an example image, generated with Audacity from this audio:

waveform example

For reference, here is what an amplitude 1 sine wave at 440 Hz looks like:

sine 440

And this is what it sounds like (warning: it doesn't sound good).


  • The background of the image must be white (#FFFFFF in HTML notation)
  • The waveform may be any color that is sufficiently distinguishable from the background
  • The input audio must be sampled at 44.1 kHz with 32-bit floats (in the inclusive range [-1, 1])
  • For raster graphics:
    • Sample points must be plotted every 5 pixels
    • The height must be an odd number of pixels, no less than 101
  • Because vector graphics can scale indefinitely, the above restrictions do not apply
  • The horizontal line in the middle of the image represents 0 amplitude, and the top and bottom of the image represent 1 and -1 amplitude, respectively
  • The vertical scale must be linear, not logarithmic (the amplitude of the wave, not the relative loudness)
  • The color of the wave, height of the image, input format, and output format must be the same every time your submission is run (for example, you cannot output as a PNG for one input, and a JPG for another)
  • For the sake of testing/verification, submissions must run in under 1 minute on my machine (Core i3-3240 quad core, 3.4 GHz, 8 GB RAM) for any input.
  • \$\begingroup\$ "common format"? \$\endgroup\$ Commented Mar 2, 2016 at 21:37
  • \$\begingroup\$ @CoolestVeto Examples for audio include MP3, WAV, WMA, M4A, and OGG (basically any format Audacity can export to). Examples for graphics include PNG, JPG, BMP, SVG, PPM, GIF, etc. \$\endgroup\$
    – user45941
    Commented Mar 2, 2016 at 21:40
  • \$\begingroup\$ So we're permitted to use any of those formats, not that we must allow for any of those formats? \$\endgroup\$ Commented Mar 2, 2016 at 21:42
  • \$\begingroup\$ @CoolestVeto Correct. \$\endgroup\$
    – user45941
    Commented Mar 2, 2016 at 21:43
  • \$\begingroup\$ Horizontal scale is specified, but (minimum) vertical scale is not. \$\endgroup\$ Commented Mar 2, 2016 at 22:31
  • \$\begingroup\$ @PeterTaylor What do you mean? The horizontal center of the image should represent 0 (silence), and the top/bottom should represent ±1 (the maximum/minimum measureable sample amplitude). The vertical scale should be linear, not logarithmic (measuring amplitude of the wave, not the loudness in decibels). \$\endgroup\$
    – user45941
    Commented Mar 2, 2016 at 22:40
  • \$\begingroup\$ A 3-pixel high image could meet that spec. \$\endgroup\$ Commented Mar 3, 2016 at 7:06
  • \$\begingroup\$ @PeterTaylor Oh, I see the issue now, thanks. \$\endgroup\$
    – user45941
    Commented Mar 3, 2016 at 19:51
  • \$\begingroup\$ Re The input audio must be sampled at 44.1 kHz with 32-bit floats (in the inclusive range [0, 1]), did you maybe mean the inclusive range [-1, 1]? \$\endgroup\$
    – zwol
    Commented Apr 21, 2016 at 23:13
  • \$\begingroup\$ @zwol I did indeed, thanks. \$\endgroup\$
    – user45941
    Commented Apr 21, 2016 at 23:23

The free monoid on two letters 'x' and 'y' is the set of all finite strings you can make up from them, including the empty string, with their concatenation a binary operation. So the elements of this free monoid look like this: "", "x", "y", "xy", "yx", "xx", "yy" and so on. Strings like "xxxx" are often written as powers and we don't generally use the quotes: x^4.

This challenge is about a certain binary relation on this free monoid. Suppose we decide to treat x^2 abd y^2 as "the same". Which other strings (or "words", as they're called) will have to become "the same" (or congruent under the relation x^2 = y^2) as a result? In xxy, we can substitute yy for xx, which means that xxy is congruent to yyy. But then, the last yy in that string can be turned into xx as well, so yxx is congruent to the previous ones as well. A nice thing about this relation is that any congruent words will have to have the same length, so the number of words congruent to a given one is always finite. (To read up on this, you can look up things like "string rewriting systems", "transitive closure", "congruence relation".)

Take a string as input. The string is assumed to be of any length (including the empty string) and to contain at most two different characters (chosen by the user from the printable ASCII set or equivalent), say x and y. The program will interpret the string as a word in the free monoid on x and y and output all the other words of that monoid, also as strings, using the characters chosen by the user, congruent to the input word under the relation x^2 = y^2, in any order. Every congruent word must occur exactly once, including the input.

The words in the output have to be consistently separated by any non-empty string of printable characters not chosen by the user. If the input word contains less than two distinct characters, your program will assume the missing one(s) according to your choice, but that must not overlap with the separator. How exactly you want to take the input and output the words is up to you, but it must be possible to enter any valid string as input.

This has to be a complete program, not a function. No loopholes please.

Examples of input and output:

in: empty string
out: empty string

in: xx
out: xx yy

in: xy
out: xy

in: xyx
out: xyx

in: xyy
out: xyy xxx yyx

in: xxxx
out: xxxx yyxx yyyy yxxy xyyx xxyy

in: xyyxy
out: xyyxy xxxxy yyxxy yyyyy xxyyy xxyxx yyyxx yxxxx yxyyx yxxyy

(Note that the whitespace is a valid input character -- your program must choose a different separator if the user chooses to use it as a letter.)

Don't worry about things like the maximal length of the input or the output. The logic of your program has to work for all input word lengths, but the program only needs to work for reasonably long inputs.

Please give a short explanation of why your program works.

  • \$\begingroup\$ You might want to include some more background about monoids and congruent words. Also, test cases should include the expected output as well. The test cases would also be more readable in a code block without quotes. And I get that you want to show with the test cases that the choice of characters is arbitrary, but that's fairly clear from the spec. It would be more useful if you stuck to one set of characters in the test cases to make it easier for people to transform all of them at once into their own input format (instead of having to rewrite each one independently by hand). \$\endgroup\$ Commented Feb 16, 2016 at 8:17
  • \$\begingroup\$ @MartinBüttner I guess I'm not attached to the test cases. I got rid of them and added a short introduction. \$\endgroup\$
    – ymar
    Commented Feb 17, 2016 at 0:47
  • \$\begingroup\$ I didn't mean you should get rid of the test cases. They're important. I just meant, use the same pair of characters throughout to make them more usable. \$\endgroup\$ Commented Feb 17, 2016 at 8:15
  • \$\begingroup\$ @MartinBüttner I've added new test cases. \$\endgroup\$
    – ymar
    Commented Mar 8, 2016 at 14:35
  • \$\begingroup\$ Why are functions banned? \$\endgroup\$ Commented Mar 9, 2016 at 5:38
  • \$\begingroup\$ @CatsAreFluffy This is personal preference - it's hard for me to understand why a function should be OK. It doesn't do the job (by itself) and it seems unfair to the people who write runnable programs. I feel that they do more. I'm new here and new to code golf so I don't know. Is there a reason functions should be allowed other than to make the top answer this much shorter? \$\endgroup\$
    – ymar
    Commented Mar 9, 2016 at 7:29
  • \$\begingroup\$ Well, in powerful golfing languages, making a function can actually be longer (eg Cjam, Golfscript) But in Java, you have to include class Q{public static void main(String[]a){...}} in all your programs. Even in other (normal) languages, fewer bytes for input/output could help beat a golfing language. tl;dr It helps languages like Java have a chance against Python or other less-boilerplatey languages. \$\endgroup\$ Commented Mar 9, 2016 at 15:20
  • \$\begingroup\$ Why are you demanding that the program allow its user to input a separator? What's the benefit in that as opposed to allowing the program to use whatever separator (not one of the letters, obviously) the programmer wants? \$\endgroup\$
    – msh210
    Commented Apr 27, 2016 at 19:25
  • \$\begingroup\$ @msh210 I don't think I'm saying that. My intention was to say exactly what you're saying. The separator is chosen by the programmer/program, but it can't be one of the letters. The letters are chosen by the user from a certain set and the separator is chosen from the same set. \$\endgroup\$
    – ymar
    Commented Apr 27, 2016 at 19:52
  • \$\begingroup\$ Oh, okay, thanks for the edit. \$\endgroup\$
    – msh210
    Commented Apr 27, 2016 at 20:04
  • \$\begingroup\$ Allowing the user to choose any letters and forcing the program to come up with a different separator seems like it only adds arbitrary complexity that’s unrelated to the interesting part of the challenge. You should either guarantee that the valid input letters are x and y, or allow the programmer to choose the valid input letters. \$\endgroup\$ Commented May 4, 2016 at 22:13

Determine whether one graph is a subgraph of the other

Given two unlabelled graphs as adjecency matrices with the same number of vertices, the goal is determining whether the first graph is a subgraph of the second one.


A graph G=(V,E) comprises a set of vertices V={1,2,3,...,n} and a set of edges E ⊆ V x V = {(u,v) | u,v ∈ V}. The adjecency matrix A={a(i,j)}of a graph G is defined entry wise:a(i,j) = 1 if (i,j) ∈ E, 0 otherwise.

A graph H=(W,F) with adjecency matrix B={b(i,j)} is a subgraph of G iff all following statements hold:

  • V=W
  • There is a permutation p:V→W=V such that b(p(i),p(j)) ≤ a(i,j) for all i,j ∈ V=W


First the trivial ones:

  • Obviously, every graph is a subgraph of itself.
  • If H has more edges than G then it cannot be a subgraph.
  • If you remove edges from a valid subgraph, the result will again be a subgraph.
  • If every of the n nodes in G has edges to every other node, then every graph H with n nodes is a subgraph.

6 vertices, isomorphic (one big cycle) (remove some ones from Graph 1 in order to generate more valid subgraphs)

Permutation: [5 6 4 1 3 2]
Graph 1:     [0 1 0 0 0 0;0 0 1 0 0 0;0 0 0 1 0 0;0 0 0 0 1 0;0 0 0 0 0 1;1 0 0 0 0 0]
Graph 2:     [0 0 1 0 0 0;0 0 0 0 1 0;0 1 0 0 0 0;1 0 0 0 0 0;0 0 0 0 0 1;0 0 0 1 0 0]

Visualization of the above example by @KennyLau:

10 vertices, same number of edges, non isomorphic (g1 has minimal cycles of length 3,4,5, g2 has minimal cycles of length 3,4,4)

Graph 1:    [0 1 0 1 0 0 0 0 0 0;0 0 1 0 0 0 0 0 0 0;1 0 0 0 0 0 0 0 0 0;0 0 0 0 1 0 0 0 0 0;0 0 0 0 0 1 1 0 0 0;1 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 1 0 0;0 0 0 0 0 0 0 0 1 0;0 0 0 0 0 0 0 0 0 1;0 0 0 0 1 0 0 0 0 0]
Graph 2:    [0 0 0 0 0 0 0 1 0 1;0 0 0 0 0 0 1 0 0 0;0 0 0 0 0 1 0 0 0 0;1 0 0 0 0 0 0 0 0 0;0 1 0 1 0 0 0 0 0 0;1 0 0 0 0 0 0 0 0 0;0 0 0 0 1 0 0 0 0 0;0 0 1 0 0 0 0 0 0 0;0 0 0 0 0 1 0 0 0 0;0 0 0 0 1 0 0 0 0 0]
  • \$\begingroup\$ Sample input output? \$\endgroup\$
    – Leaky Nun
    Commented Apr 30, 2016 at 11:22
  • 1
    \$\begingroup\$ I added some now. \$\endgroup\$
    – flawr
    Commented Apr 30, 2016 at 14:06
  • \$\begingroup\$ @KennyLau How did create those visualizations? \$\endgroup\$
    – flawr
    Commented Apr 30, 2016 at 15:21
  • 1
    \$\begingroup\$ Microsoft Paint. \$\endgroup\$
    – Leaky Nun
    Commented Apr 30, 2016 at 15:27

Nested brackets in source code


This challenge is somewhat unusual. Basically, your inputs are a correctly matched string of brackets S and a number n ≥ 0, and your output is the number of matched pairs at nesting level n in S. The outermost pairs are at level 0, those inside them are at level 1, and so on. The twist is that the string S is part of your source code, and incorrectly matched strings must result in compilation or runtime errors.

The task

Your task is to write four strings, A, B, L, and R, that satisfy the following conditions.

  • The strings L and R are non-empty and distinct. They represent a left and right bracket.
  • If S is a concatenation of Ls and Rs that is correctly matched, then the concatenation ASB is a valid program (full runnable program or function definition) is your programming language of choice. It takes an integer n ≥ 0 and outputs the number of L-R pairs in S at nesting level n.
  • If S is a concatenation of Ls and Rs that is not correctly matched, then ASB either fails to compile, or throws an error on every possible input.


Suppose that the strings A, B, L, and R are BEGIN;, END;, DO(i++; and );, respectively, in an imaginary programming language. Then the string DO(i++;);DO(i++;DO(i++;);); is a correctly matched concatenation of Ls and Rs. On input 0, the program


should output 2, because there are two matched pairs at level 0. However, the program


should result in an error, because the brackets are not correctly matched.

More examples

Here is a table of some programs, inputs and expected outputs.

Program          Input  Output
AB               <any>  0
ALRB             0      1
ALRB             1      0
ALLRRB           1      1
ALRLRB           0      2
ALRLLRRB         0      2
ALRLLRRB         1      1
ARB              <any>  error
ALB              <any>  error
ARLB             <any>  error
ALLRB            <any>  error
ALLRRRLRB        <any>  error
ALLRRLLRB        <any>  error
ALLRRRLLLRRB     <any>  error

Rules and scoring

Your score is the sum of the lengths of the four strings, lower score being better. You must identify the strings in your answer. You are not allowed to read your source code directly or indirectly. Standard loopholes are also disallowed.

Sandbox notes

  • Is the task of counting pairs on a nesting level too easy? I don't want it to be trivial, but not so hard either that it shadows the source layout aspect. A slightly more difficult variant would be to count the number of peaks (substrings LR) at nesting level n.
  • Is the restriction of erroring on mismatched brackets interesting? I could also require the program to always return -1 in this case, or something similar.
  • \$\begingroup\$ Shouldn't DO(i++;);DO(i++;DO(i++;)) be DO(i++;);DO(i++;DO(i++;););? \$\endgroup\$ Commented May 14, 2016 at 19:23
  • \$\begingroup\$ @PeterTaylor Yes it should, good catch. \$\endgroup\$
    – Zgarb
    Commented May 14, 2016 at 19:25
  • \$\begingroup\$ Thought about this more. By making A end in ", L be (, R be ), and B start with ", I can reduce it to matching brackets in a string. If it's not a duplicate of an existing question, it has at least neutered the twist. \$\endgroup\$ Commented May 16, 2016 at 14:30
  • \$\begingroup\$ @PeterTaylor That's a valid approach, but I'm hoping that more quine-like solutions will be shorter, at least in "normal" languages. The error rule is intended to help with that too. \$\endgroup\$
    – Zgarb
    Commented May 16, 2016 at 17:15

Three Indistinguishable Dice

Given three dice rolls (integer values from 1-6) in sorted order (so as to be indistinguishable), write a program that converts them to the sum of two dice with an identical distribution.

Inspired by standupmath's The Three Indistinguishable Dice Puzzle. A follow-up "solution" video was also posted, but arguing about "elegance" of one way or another is a bit subjective. Counting characters isn't. :D


  • Score is the length of the program in characters
  • The program can be a function that's called somehow, or executable script that reads from stdin, or whatever's convienent.
  • No "rerolling" by getting entropy from another source

Example Test Code

Rather than doing any sort of probabilistic testing, it's easy enough to rip through the 216 (63) cases of all the three dice and assert that your function returns each value as many times as it should. It will be called with identical parameters (e.g. the cases 1, 2, 3 and 3, 2, 1, ... are presumed indistinguishable and are (arbitrarily) converted to 1, 2, 3).

The below is in Python, written hopefully generically enough to be clear to port. If your language of choice uses stdin/stdout, it would be a bit different. The testing code is just for testing and not scored (though if you want to provide it for other users of your language or I/O method, that might be useful).

from thing import f

# this is the fair distribution of the sum of two dice, 
# multiplied by 6 (because each should be hit 6x more)
dist = {
    2: 6,   12: 6,
    3: 12,  11: 12,
    4: 18,  10: 18,
    5: 24,   9: 24,
    6: 30,   8: 30,
    7: 36,

d = [1, 2, 3, 4, 5, 6]
for i in d:
    for j in d:
        for k in d:
            ijk = sorted([i, j, k])
            result = f(ijk)
            dist[result] -= 1

for key in dist:
    assert dist[key] == 0

Brainfuck-golf: find the maximum of two numbers

You will be provided with two numbers on the first two memory cells, and you will write a code in brainfuck to put the maximum of the two numbers on the third memory cell.

  • You may use this template and this template to test your code. Just append your code to the templates.
  • You may destroy the numbers in the first two cells.
  • The pointer must initially point to the first cell.
  • The two initial numbers will be positive.
  • , will halt your program (waits for input which I will not supply).
  • The tape is semi-infinite. Your numbers are on the first two memory cells.
  • The cells do not wrap around. They just increase until the number is bigger than the age of the universe in terms of picoseconds.
  • \$\begingroup\$ Language specific challenges are generally frowned upon. And if this wasn't restricted to BF, it would be to trivial. \$\endgroup\$
    – DJMcMayhem
    Commented May 21, 2016 at 8:36
  • \$\begingroup\$ How is regex-golf different from this? \$\endgroup\$
    – Leaky Nun
    Commented May 21, 2016 at 8:43
  • \$\begingroup\$ Regex-golf is slightly different since there are many versions of regex with different behavior. But hey, I could be wrong. We've had BF only challenges before. (such as codegolf.stackexchange.com/questions/33019/brainfuck-sorting, codegolf.stackexchange.com/questions/9178/…, and codegolf.stackexchange.com/questions/2445/… I'd leave it up for a while and see what other people think. \$\endgroup\$
    – DJMcMayhem
    Commented May 21, 2016 at 8:54
  • \$\begingroup\$ It may be a duplicate of the first linked challenge, because this challenge is only about comparing... \$\endgroup\$
    – Leaky Nun
    Commented May 21, 2016 at 9:03
  • \$\begingroup\$ Can we use ,, and if so what will it do (e.g. set to 0, set to -1, no change)? \$\endgroup\$
    – Sp3000
    Commented May 21, 2016 at 11:39
  • 1
    \$\begingroup\$ Since this is a) language specific, b) asks for a snippet, c) asks for a task that is probably often just a minor component of a more elaborate program, how about posting it as a tips question instead? \$\endgroup\$ Commented May 21, 2016 at 11:51
  • 3
    \$\begingroup\$ You should also specify the details of the Brainfuck interpreter. Semi-infinite or infinite tape? Byte values or arbitrary-precision integers in the cells? Etc... \$\endgroup\$ Commented May 21, 2016 at 11:52
  • \$\begingroup\$ Why tips? \$\endgroup\$ Commented Jun 13, 2016 at 23:33

Do my algebra homework for me!

Inspired by a true story

Ugh, my maths teacher gave me so much homework on quadratics.

Two whole worksheets, filled with equations like Expand (x+1)(x-6) and Factorize x^2-2x+1. I already hate it.

Suddenly, a lightbulb appeared out of nowhere, and landed about five centimetres above my head.

A stroke of thought went through me: Why not write a piece of code down instead of all those stupid answers? It would save me tons of time!

So here's the task: Make an algebra solver for me! To save my hand from breaking, the code needs to be as short as possible.


  • Given an input in the form expand/factorize equation, return the algebraic equation:
    • Expanded, if the keyword (the first word) is expand (e.g. expand (x+1)(x+6) would return x^2+7x+6), or
    • Factorized, if the keyword is factorize (e.g. factorize x^2+9x+14 would return (x+2)(x+7).
  • The equation will be quadratic, in the form ax^2+bx+c or (x+d)(x+e) (a to e are all placeholders, while x is the variable - the variable can be any letter from a to z - so an equation like expand (a+3)(b+6) would still hold).
  • With an expansion equation that contains two or more unknowns (e.g. expand (a+3)(b+6)), place the letters in the summands with two or more letters in alphabetical order, and place the remaining summands in alphabetical order (so the previous example would equal ab+6a+3b+18).

This is code-golf, so shortest code in bytes wins. Good luck!


  • Any dupes?
  • I probably need a better title. Any suggestions?

Shortest program with unknown halting status


  1. Post a term on the binary λ-calculus (BLC) whose termination is unknown.

  2. If someone proves that your term does or doesn't terminate, you entry is disqualified.

  3. The term with the smallest number of bits on the BLC wins.

Don't forget to also post a quick description of what you did and the original source code, otherwise we will just have to trust your random string meets the specs!

Example submission

Size: 579 bits

Program: 01001001000100010001000101100111101111001110010101000001110011101000000111001110

Explanation: this term, if it terminates, reduces to a list with all church-encoded natural numbers of the sequence of Collatz (A006577) from 0 to 2^256. It is not known if collats(n) halts for all n; we only know up to about 2^64, so my submission satisfies the specification. For a longer explanation, I've set this repository. The original code was written on Caramel and also on the repository. Here is a brief:

-- Receives fix and a natural, returns the number of
-- recursive calls until the collatz function halts.
collatz fix n = (fix go n)

    -- The recursive search
    go go n = (succ (even_odd_or_leq_one n even odd leq1))
        even = (go go (half n))
        odd  = (go go (succ (mul n 3)))
        leq1 = 0
  • 1
    \$\begingroup\$ The only thing I'd like to comment on is that the challenge shouldn't be limited to BLC, and that other languages should be allowed so long as they are valid. For example, there is no reason to disallow a python solution that does the same thing as the above BLC code. \$\endgroup\$
    – Zwei
    Commented Jun 7, 2016 at 3:39
  • \$\begingroup\$ I agree with @Zwei, but also ban IO and other nondeterministic code. \$\endgroup\$
    – HEGX64
    Commented Jun 7, 2016 at 9:56
  • 2
    \$\begingroup\$ As commented on main, you need to define the system of axioms which are permitted for the proof. \$\endgroup\$ Commented Jun 7, 2016 at 11:03
  • \$\begingroup\$ Fair enough. I feel like this will never get enough momentum for any relevant answer, though. I might just not ask it. \$\endgroup\$
    – MaiaVictor
    Commented Jun 7, 2016 at 11:10
  • 1
    \$\begingroup\$ @Dokkat This challenge is interesting imo, there are just a few things that need to be worked out such as how does one prove that a program does or does not terminate. Remove the BLC only rule and define the axiom system and this challenge should be good for main. \$\endgroup\$
    – Zwei
    Commented Jun 7, 2016 at 14:59
  • \$\begingroup\$ I think it's better to keep the language restriction. \$\endgroup\$
    – feersum
    Commented Jun 7, 2016 at 20:18
  • \$\begingroup\$ @feersum for what reason? \$\endgroup\$
    – Zwei
    Commented Jun 8, 2016 at 0:15
  • \$\begingroup\$ @Zwei the whole point of the challenge is that I want the program with the lowest Kolmogorov Complexity. It is hard to talk about this metric when you don't have a fixed language. There is a very clear and trivial measure of the complexity of a term on the binary lambda calculus. In fact, I'd say the only way for a code golf challenge to be an objective competition (not just a popularity contest) is by using a fixed language with a clear complexity metric, and the BLC is about as good as we know. \$\endgroup\$
    – MaiaVictor
    Commented Jun 8, 2016 at 13:50
  • \$\begingroup\$ @Dokkat fair enough. \$\endgroup\$
    – Zwei
    Commented Jun 8, 2016 at 15:23
  • \$\begingroup\$ That link is to binary combinatory logic, not binary lambda calculus. \$\endgroup\$ Commented May 31, 2017 at 17:55

Determine the winner of Beggar my Neighbour

The card game Beggar my Neighbour is boring in that the final outcome is entirely determined by the initial arrangement of the deck, so long as certain rules are followed for the order in which cards are picked up from the playing field and moved to decks.

The Game

  1. Both players are dealt 26 cards.

  2. Players play their top card alternately, starting with the player who won the previous stack or Player 1 at the beginning of the game.

  3. Play is interrupted when either player plays a picture card. In that case their opponent must play a number of cards equal to the value of the picture card above 10, i.e. Jack = 1, Queen = 2, King = 3, Ace = 4. The player then wins all the played cards which are returned to the bottom of their hand, unless the opponent themselves plays a picture card, in which case this rule interrupts their play.

  4. If at any point one of the players needs to draw a card from their deck, but their deck is empty, they immediately lose the game.

Example play

Player 1 starts with 7; Player 2 plays 3; subsequent plays are 9; 9; T; A; 6, J; A; 2, 3, 7, 6: Player 2 adds the cards 7399TA6JA2376 to his deck.
Player 2 starts: J; K; 9, 4, A; 5, 2, J; 2: Player 1 adds the cards JK94A52J2 to his deck.
Player 1 starts: 6; T; T; 5; 9; A; A; 3, K; K; 7, Q; 5, T: Player 1 adds the cards 6TT59AA3KK7Q5T to his deck.

The Challenge

Given two lists of cards in the players' decks, in any convenient format, output a truthy value if Player 1 wins, and a falsey value if Player 2 wins.

For convenience, a 10 card will be represented with a T, and face cards will be abbreviated (Ace -> A, King -> K, Queen -> Q, Jack -> J), so that all cards are one character long. Alternatively, ranks may be represented with decimal integers 2-14 (Jack -> 11, Queen -> 12, King -> 13, Ace -> 14) or hex digits 2-E (10 -> A, Jack -> B, Queen -> C, King -> D, Ace -> E). Since suits don't matter, suit information will not be given.

You may assume that all games will terminate at some point (though it may take a very long time), and one player will always run out of cards before the other.

There are variations for more than two players but they will not be considered here.


Maximal root multiplicity of integer polynomials

Given a non constant polynomial with integer coefficients, determine the maximal multiplicity of it's (perhaps complex) roots.


Multiplicity: Let p be a polynomial with complex coefficients and x0 some complex number. If x0 is a root, it is said to have multiplicity n if p(x) = a(x) * (x-x0)^n where a is another (complex) polynomial such that (x-x0) does not divide a. If x0 is not a root it is defined to have multiplicity 0. Note that the polynomials we consider do only have integral coefficients (consider the integers as a subset of the complex numbers).

Maximal Multiplicity: Let x0,...,xk be the roots of of p,then the maximal multiplicity of p is defined as the maximal multiplicity of xi for i=0,...,k.


For the input and output, the polynomials can be written in any convenient format, e.g. also as a (variable length) list of coefficients.


A polynomial has a root of multiplicity greater than one if and only if it shares a root with it's derivative. This can e.g. be checked with the discriminant.


polynomial     maximal multiplicity
1              0
x^7-1          1
x^8-x^7-x-1    2
x^3-3x^2+3x-1  3
  • \$\begingroup\$ What sorts of builtins are allowed/banned? Root finding? Polynomial GCD? \$\endgroup\$
    – Sp3000
    Commented Jun 7, 2016 at 9:19
  • \$\begingroup\$ I did not plan to ban anything, would you suggest banning these? \$\endgroup\$
    – flawr
    Commented Jun 7, 2016 at 9:22
  • \$\begingroup\$ Not really, it's fine if nothing's banned. Just making sure it was considered :) \$\endgroup\$
    – Sp3000
    Commented Jun 7, 2016 at 9:47
  • 1
    \$\begingroup\$ Do you have any test cases for roots which repeat in different irreducible factors and thus demonstrate that it can't be done by counting multiplicity of irreducible factors? \$\endgroup\$ Commented Jun 7, 2016 at 10:49
  • \$\begingroup\$ Answering my own question: it can be done by counting multiplicity of irreducible factors, because the minimal polynomial of an algebraic number is a factor of any polynomial of which that number is a root. So factor to irreducibles is worth mentioning as related, although it's far more than needed. \$\endgroup\$ Commented Jun 7, 2016 at 14:01
  • \$\begingroup\$ I considered factoring as the obvious approach but I think most languages do not have the means to calculate with exact complex numbers (except some CAS' like Mathematica), so the method via resultants/discriminants should just provide another way, which surprisingly only needs integer arithmetic. \$\endgroup\$
    – flawr
    Commented Jun 7, 2016 at 14:31
  • \$\begingroup\$ The line on maximal multiplicity ends rather abruptly, I'd assume that that was an accident? Anyway, I'm not sure the terminology "does not divide" is correct here. It's been a while for me, but I think you should say something like: "does not divide a(x) such that the quotient is a polynomial"? \$\endgroup\$ Commented Jun 7, 2016 at 14:40
  • \$\begingroup\$ Right, I think I wanted to add something regarding the constant polynomials, but now I excluded those too for the sake of simplicity. Statements about divisibility usually only make sense in the context of rings, and is defined as: A divides B if there is a C such that B = AC. As soon as you consider a field (in your example the field of rational functions) the divisibility becomes trivial, as any nonzero element divides every element of the field. \$\endgroup\$
    – flawr
    Commented Jun 7, 2016 at 14:59
  • \$\begingroup\$ The method via factoring only requires integer arithmetic. I don't find it at all surprising that an approach with resultants only needs integer arithmetic, because subresultants are the standard efficient way to do polynomial GCD. \$\endgroup\$ Commented Jun 7, 2016 at 16:12
  • \$\begingroup\$ @PeterTaylor I agree, the "surprisingness" is subjective, as far as I know the resultants are usually defined via the product of the differences of the zeros. From that perspective it isn't really obvious that this might result in something even real=) Regarding the factoring we probably did not have the same thing in mind or I do not understand what you mean. I thought about factoring into linear factors, which generally results in general algebraic numbers, far from integers. What did you have in mind? \$\endgroup\$
    – flawr
    Commented Jun 7, 2016 at 16:38
  • \$\begingroup\$ Factoring to polynomials which are irreducible over the integers, as in the linked question. Equivalently, as I realised between my first and second comment, factoring to the minimal polynomials of the roots. Edit: ah, but wait. Can the minimal polynomial contain the root multiple times? \$\endgroup\$ Commented Jun 7, 2016 at 19:10
  • \$\begingroup\$ I'm not sure in general, I think this might fail for some fields with finite characteristic, but for algebraic numbers (=elements of finite field extensions of the rational numbers) the minimal polynomials have distinct roots in the corresponding splitting field. \$\endgroup\$
    – flawr
    Commented Jun 7, 2016 at 20:11

Pareto frontier

A point (x1,y1) dominates another point (x2,y2) if both x1≥x2 and y1≥y2. A set of points is a Pareto frontier if no point dominates another point. In other words, any increase in one coordinate must be met with a decrease in the other coordinate.

Your task is to decide whether a given set of points is a Pareto frontier.

Input: A collection of two or more points, which are pairs of positive integers. No two points will have the same x-value or the same y-value. You may not assume the points are given in a particular order.

Output: A consistent Truthy value if it is, and a consistent Falsey value if it's not.


[(12, 1), (6, 4)]
[(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)]
[(4, 4), (3, 8), (12, 3), (20, 1)]
[(106, 106), (107, 102), (104, 127)]


[(5, 9), (4, 8)]
[(1, 1), (11, 11)]
[(5, 3), (2, 4), (7, 7), (1, 2)]
[(15, 2), (7, 8), (4, 14), (6, 6)]


  • Is it better to do the decision problem, or the filtering problem of finding the upper Pareto frontier of non-dominated points?

  • Should the input be allowed to be taken pre-zipped, as two lists of n numbers? What about a 2D 2-by-n array versus an n-by-2 array?

  • \$\begingroup\$ I'd recommend only doing the filtering problem if there is a nicer solution than subsets -> filter on decision -> take longest that you can enforce with restraints of some kind. Otherwise I feel like it might be kind of chameleon-y. \$\endgroup\$ Commented Jul 13, 2016 at 1:49
  • \$\begingroup\$ The decision problem can be done as filter and check equality; or sort on one axis and check that the other axis is in reverse order. The filter problem can be done by filtering the power set with the decision problem and taking the longest; or by folding a removal of dominated points. IMO the filter problem is more interesting, because sort builtins are very common and typically cheap. \$\endgroup\$ Commented Jul 13, 2016 at 10:37
  • \$\begingroup\$ @PeterTaylor The largest Pareto-incomparable subset might contain points dominated by the rest of the set. I expect filtering would be done by folding removal. Does that affect your opinion? \$\endgroup\$
    – xnor
    Commented Jul 20, 2016 at 5:16
  • \$\begingroup\$ Ah, true. Folding removal still seems more interesting to me than sorting and checking reverse order. \$\endgroup\$ Commented Jul 20, 2016 at 7:39

Lets play Stratego!

Stratego is a game of imperfect information which centers around strategy foresight and deception.


Your mission should you choose to accept it. is to write a bot which either uses polymorphism in a java class file, and/or communicate with the arena via an stdin/stdout wrapper.

The arena code and/or stdin out wrapper will be made available if there is interest. Here is the summary.

Piece Summary

? = Unkown enemy piece
lowercase characters = your pieces
Upper case or special characters (!@#$%^&*()) or F B is the enemy pieces
f or F represents an immobile flag if the enemy moves on to this square it is game over.
b or B represents an immobile if any hostile piece steps on to it then it dies. If an enemy miner (8) steps on it will succesfully defuse or capture the bomb.
s or S gets killed when attacked by any piece, but can kill the 10 by stepping on it.
9 or ) can move any number of squares orthagonally.
Otherwise all pieces can capture pieces with a higher number than themselves. I.E 1 captures two which captures three which captures a 4 which captures a five etc...
When you attack a piece, the values of both pieces are revealed (thus the enemy will no longer see a "?") If the attacking piece is stronger it takes the spot, if it is weaker, it dies and the defender remains unharmed, and if they are equal both disappear. 

Spaces empty are indicated with a space. Spaces with an impassable lake are indicated with an L. The wikipedia article has some great sample strategies and explanations. The protocol for communication will involve Outputting four zero indexed coordinates for the start and end locations of a piece. Invalid moves will simply result in no action taken.

  • \$\begingroup\$ do you have a bot API? \$\endgroup\$ Commented Jul 23, 2016 at 18:56
  • \$\begingroup\$ Not yet. It was something I was pondering in my head. If there is any interest in this I can slap together an api. @AgentCrazyPython do you think this is a doable challenge \$\endgroup\$ Commented Jul 23, 2016 at 19:27
  • \$\begingroup\$ I think it's doable. You'd get a whole ton of rep for it. \$\endgroup\$ Commented Jul 23, 2016 at 21:17
  • \$\begingroup\$ @AgentCrazyPython lol I need the rep. I will write up an arena controller. Should I do it through an stdin/stdout interface or an abstract class? I think I will first write an interface that allows you to inherit from an abstract class. Than I would write a wrapper. The only thing is that I have no clue how to go about implementing a sample bot. \$\endgroup\$ Commented Jul 23, 2016 at 21:23
  • \$\begingroup\$ depends on if you want to let one language or all languages. I think you should go just one langauge: JS. JS can be demoed easily in the browser and it's great for writing bots. the spacewar! challenge is a good example \$\endgroup\$ Commented Jul 23, 2016 at 21:25
  • \$\begingroup\$ I need to learn JS, but I am slightly discouraged after learning about jsf*** lol. It seems like an <s>odd</s> unique language lol. \$\endgroup\$ Commented Jul 23, 2016 at 21:27
  • \$\begingroup\$ I will first prototype a Java arena, and then I will first write a wrapper (probably by modifying @Moogie 's) wrapper. Then I will stare at a wall idly considering porting it to Java script. \$\endgroup\$ Commented Jul 23, 2016 at 21:28
  • \$\begingroup\$ @AgentCrazyPython ^ Forgot to ping you on the above comments \$\endgroup\$ Commented Jul 23, 2016 at 21:29
  • \$\begingroup\$ js is super easy to learn. JS has really similar syntax \$\endgroup\$ Commented Jul 23, 2016 at 22:10
  • \$\begingroup\$ Yeah, but the dynamic typing stuff really gets me. I do have some python background which should help, but I am I java dev mainly. @Agent CrazyPython That being said, I will try to learn java as stack snippets do appeal to me. \$\endgroup\$ Commented Jul 23, 2016 at 23:00
  • \$\begingroup\$ java ≠ javascript!!!!!!! why is dynamic typing hard - it's looser than static typing \$\endgroup\$ Commented Jul 23, 2016 at 23:48
  • \$\begingroup\$ @AgentCrazyPython I know that JS!=Java lol. THats why I am scared of it. For someone reason I do prefer being sure of type safety as I code rather than at run time \$\endgroup\$ Commented Jul 24, 2016 at 3:39
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ Commented Jul 24, 2016 at 3:39

Reversing the Game of Life

Though computing successive generations of Conway's Game of Life may seem simple enough, reversing the process is not.

Given an initial board configuration in Conway's Game of Life, either return a predecessor, or some value indicating that it is a Garden of Eden (and therefore contains an orphan), meaning it has no predecessor. A predecessor is a previous generation of a board configuration, meaning that after running the game for a some number of generations, you will arrive at the successor generation, the board configuration that you were initially given.

Any given configuration may have zero or more predecessors. Some have infinitely many, such as still life patterns.

It will probably be simplest to find a parent, a predecessor configuration from the preceding generation, such that reaching the successor takes one generation.

Two parents of the Block

If given a state bounded by a 6x6 rectangle, for example, a parent (if any) will be found by searching the 8x8 rectangle around it. This is a fastest-code challenge, since brute force solutions would take a long time, even for relatively small inputs.

All Game of Life patterns bounded by a 6x6 rectangle have a predecessor. Source

Example Input

Input can be how you like. If you prefer a list of active points, or a matrix of Booleans, that's fine. Just make your output be the same format.

This input represents a block:

Block still life

[(1, 1), (1, 2), (2, 1), (2, 2)]


The original Garden of Eden:

Garden of Eden

All cells outside the image are dead (white).

Example Output:

This is a parent to the block.


Garden of Eden:

No predecessor


  • \$\begingroup\$ Not exactly a dupe, but searching for a parent was how I approached an earlier fastest-code game-of-life question. \$\endgroup\$ Commented Jul 22, 2016 at 21:34
  • \$\begingroup\$ Why is it undecidable? Theoretically, you could just enumerate over every possible parent state until one generates the pattern (or you run out of possible parents in the case of a Garden of Eden). \$\endgroup\$ Commented Jul 22, 2016 at 21:41
  • \$\begingroup\$ @LegionMammal978 I don't understand either, but from the linked Wikipedia article: For one-dimensional cellular automata, orphans and Gardens of Eden can be found by an efficient algorithm, but for higher dimensions this is an undecidable problem. Nevertheless, computer searches have succeeded in finding these patterns in Conway's Game of Life. \$\endgroup\$
    – mbomb007
    Commented Jul 22, 2016 at 21:43
  • \$\begingroup\$ I think it's saying that there is no way that a decidable AND efficient algorithm exists? Not sure. \$\endgroup\$
    – mbomb007
    Commented Jul 22, 2016 at 21:44
  • \$\begingroup\$ @mbomb007 Maybe it's talking about polynomial-time algorithms or something, last time I checked, bruteforce wasn't undecidable \$\endgroup\$ Commented Jul 22, 2016 at 21:53
  • \$\begingroup\$ @LegionMammal978 K, I'll remove that part. Is there enough explanation, do you think? There is probably required reading from the links I provided in order for a decent non-brute-force solution to be developed. \$\endgroup\$
    – mbomb007
    Commented Jul 22, 2016 at 21:55
  • \$\begingroup\$ @mbomb007 Looks fine to me \$\endgroup\$ Commented Jul 22, 2016 at 21:56
  • 3
    \$\begingroup\$ I feel like the performance of an algorithm will heavily depend on how test cases are generated. You should specify this. \$\endgroup\$
    – xnor
    Commented Jul 22, 2016 at 23:17
  • \$\begingroup\$ @LegionMammal978: The "undecidable" part is probably due to how you can have spaceships crash together from a distance to make new patterns. \$\endgroup\$ Commented Jul 23, 2016 at 12:39
  • 1
    \$\begingroup\$ @El'endiaStarman However, all that matters for finding the previous generation is the part of the spaceship within the n+2 X m+2 box that can affect the pattern \$\endgroup\$ Commented Jul 23, 2016 at 14:34
  • \$\begingroup\$ @LegionMammal978: Hmm, true. I don't know either. \$\endgroup\$ Commented Jul 23, 2016 at 14:47
  • \$\begingroup\$ @LegionMammal978, the undecidable problem is "Given the rules for a 2-dimensional cellular automaton, does any Garden of Eden exist with those rules?" \$\endgroup\$ Commented Jul 25, 2016 at 20:38
  • \$\begingroup\$ @PeterTaylor See the Garden of Eden theorem. It says that any CA with multiple patterns that evolve to the same pattern must contain some Garden of Eden (presumably by a variant of the pigeonhole principle). \$\endgroup\$ Commented Jul 25, 2016 at 21:04
  • 1
    \$\begingroup\$ @mbomb007 One way to do the test cases would be random grids. Most of these would likely have many predecessors and be doable with a heuristic search. If you want hard examples, maybe it's possible to generate ones with few predecessors and mix in gardens of eden. I don't know how doable that is. For returning a g.o.e. in an mxn grid, can't one just return a known minimal one if it fits and falsey otherwise? Generating optimal gardens of eden seems really hard even if you have good heuristics. \$\endgroup\$
    – xnor
    Commented Jul 25, 2016 at 21:48
  • 1
    \$\begingroup\$ @LegionMammal978, so the existence of twins is logically also undecidable, but I'm not sure why you think that's important to point out. \$\endgroup\$ Commented Jul 26, 2016 at 8:42

Do X without Y​ again!

Here is an X done with Y:

YyYy        YyYy
 YyYy      YyYy 
  YyYy    YyYy  
   YyYy  YyYy   
   yYyY  yYyY   
  yYyY    yYyY  
 yYyY      yYyY 
yYyY        yYyY

As you can see, there are 92 Y/ys in this X. Conveniently, there are also exactly 92 printable ASCII characters in the range ! to ~ if you exclude Y and y. Your challenge is to write a program to output or a function to return the above X with all the Y/ys replaced by any permutation of those 92 characters. Leading and trailing white space is permitted. Shortest code wins!

  • \$\begingroup\$ Should that say "each of those 92 characters" (in the range ! to ~, excluding Yy)? \$\endgroup\$
    – nanofarad
    Commented Jul 30, 2016 at 13:15
  • \$\begingroup\$ Just drop the exclamation mark already. \$\endgroup\$
    – Leaky Nun
    Commented Jul 30, 2016 at 13:15
  • \$\begingroup\$ Maybe I'm misunderstanding the question, but you seem to be requiring all answers to be exactly 92 characters long and within that constraint aiming to be the shortest... \$\endgroup\$ Commented Jul 30, 2016 at 17:12
  • \$\begingroup\$ @PeterTaylor: He doesn't specify a length of an answer... He says that in the above ascii X each Y is replaced by another character of the 92 printable characters that are not y or Y; each char is only used once. \$\endgroup\$
    – KarlKastor
    Commented Jul 30, 2016 at 19:41
  • 1
    \$\begingroup\$ I'd make it obvious that a permutation of the 92 characters are to be used (no repeating a character) \$\endgroup\$ Commented Jul 31, 2016 at 1:13
  • \$\begingroup\$ Have you abandoned this altogether already? \$\endgroup\$
    – Leaky Nun
    Commented Aug 18, 2016 at 0:16
  • \$\begingroup\$ @LeakyNun It only got 1 upvote, unless you know a better way of telling when it's ready. \$\endgroup\$
    – Neil
    Commented Aug 18, 2016 at 0:17

The Enemy's Gate is Down! (Ender's Game)

Please note this is a work in progress

Your challenge should you choose to accept it is to play ender's game to win style, in honor of Martin Ender first receiving 100k rep! You will split up into teams. You are red if you are an even post and blue if you are odd.

Here is a simplified ascii representation of the map.

W       1                        F                         2    W
W                  WwW                                          W
W        WWW                                                    W
W                                            WWWWWWWW           W
W                WWWWWWWWWWWWWWWWW                              W  
W                                                               W  
W                                                               W  
W             WWWWWWWWW                    WWWWWWWWWWW          W  
W                                                               W  
W                              WWWWW                            W  
W                                                               W
W       3                        G                         4    W

Your gate is represented by the "F" and the enemies gate is "G". W's represent walls which will be arranged in an unbiased distribution. The goal is to get to the enemies gate first. Each turn you will output a number from 0-15.

 0-7 will allow you to "push" off of a block assuming there is a block in the 8 blocks closest to you (orthagonally or diagonally")
8-17 allows you to shoot a bullet in a given direction which will continue to travel in a given direction. 
It will break upon hitting a wall or another player. The bullet represented by "P" on the ascii map is iterated after each step. Any player that drifts into it will also be killed. 



The winning team is the team which either captures the flag first the last man (bot/woman) standing!

All submission are deterministic java programs. A psuedorandom generator will be provided. The winning team is the team which wins the first game, (if there are ties).

Games will be halted after a significant number (1000) turns. I may allow multiple copies of the same bot on each team to make it more interesting.

Collisions with players are treated like collisions with walls.

  • \$\begingroup\$ What about collisions between players? \$\endgroup\$ Commented Aug 3, 2016 at 2:44
  • \$\begingroup\$ Both die (i guess) \$\endgroup\$ Commented Aug 3, 2016 at 3:07
  • \$\begingroup\$ @DestructibleWatermelon a \$\endgroup\$ Commented Aug 3, 2016 at 3:08
  • \$\begingroup\$ Would it be possible to add an Stdin/out wrapper? \$\endgroup\$ Commented Aug 3, 2016 at 3:18
  • \$\begingroup\$ What if friendly bots can be in the same square, and push off each other to confuse the enemy? That seems cool. Probably make it so it doesn't affect the non-pushing bot just to reduce troublemaker bots ;) (Also, I guess each player would need an indication that they have a teammate in the same square or something) \$\endgroup\$ Commented Aug 3, 2016 at 3:32
  • \$\begingroup\$ @DestructibleWatermelon ok I can make it so all players atreated like walls u can push off of. \$\endgroup\$ Commented Aug 3, 2016 at 11:46
  • \$\begingroup\$ It would be nice for the programs to be able to be in any language (using subprocess pipe) \$\endgroup\$
    – Blue
    Commented Aug 3, 2016 at 15:11
  • \$\begingroup\$ @Blue I can write an stdin/stdout wrapper once I get an arena. The onl issue is that by starting subproceses the performance may be significantly harmed \$\endgroup\$ Commented Aug 3, 2016 at 16:56

Golf an InterpretMe interpreter (in any language other than InterpretMe)

This is a very simple challenge.

The joke language InterpretMe consists of one command; *, which causes the program to take input of an InterpretMe program and execute it. An InterpretMe program will interpret as many InterpretMe programs as there are * in input. Your goal is to create a program that interprets InterpretMe in as few bytes as possible.

Test cases consist not of input and output, but input and termination. A newline denotes a new input to be interpreted as InterpretMe.

1. *   (executes input as an interpret me program, finishes)
2. *   (^same)
3. **  (executes input as an interpret me program, then does this again after the first program is done, finishes)
4. hi  (nothing, first star of previous line finishes)
5. **  (same as the other two star line)
6. hi  (nothing, first star of previous line finishes)
7. hi  (nothing, second star of line 5 finishes, so second star of line 3 finishes, so line 2 finishes, so line one finishes)

hi  (does nothing and finishes)

*hi  (executes inputted program, finishes)
*yo  (executes inputted program, finishes)
hey  (nothing)


How can I make this challenge more clear? I understand that this challenge is simple, but that is part of the point; it sees how small a program can be for this purpose

  • 2
    \$\begingroup\$ To make the challenge more clear, you could supply the specification for the language which has to be interpreted. It shouldn't be necessary for each answerer to search for the basic definition of the problem. \$\endgroup\$ Commented Aug 3, 2016 at 14:46
  • \$\begingroup\$ @PeterTaylor, Excuse me, it's right there. An InterpretMe interpreter takes input, and runs an InterpretMe interpreter (which takes new input) as many times as "*" occurs in input. (dumb blockquotes) \$\endgroup\$ Commented Aug 3, 2016 at 23:09
  • \$\begingroup\$ Maybe if you state up front that it's a joke language that would prime the reader to not expect it to do anything useful. \$\endgroup\$ Commented Aug 4, 2016 at 7:19
  • \$\begingroup\$ @PeterTaylor Thanks \$\endgroup\$ Commented Aug 4, 2016 at 7:31

I wanna be the very best...

Wow, there's so many Pokemon in my Pokedex! Well, there seems too many... I wish there was some good way of sorting all of them!

Can you help?

Given a list of Pokemon with their stats - level and HP - and a sorting criterion, output the sorted list.

An example input would be:

([["Squirtle", 2, 10], ["Charizard", 58, 140], ["Mew", 75, 160], ["Pichu", 10, 25]], "alphabetical")

As you can see, each Pokemon is shown like so:

[pokemon_name, level, hp]

There are three sorting options:

  • "alphabetical": The Pokemon are sorted alphabetically.
    • If two or more Pokemon have identical names, then they are sorted by level, then HP.
  • "level": The Pokemon are sorted by level.
    • If two or more Pokemon have the same level, then they are sorted alphabetically, then by HP.
  • "hp": The Pokemon are sorted by HP.
    • If two or more Pokemon have the same HP, then they are sorted alphabetically, then by level.


  • You are guaranteed that:
    • The hp and level of every Pokemon are integers.
    • The level of a Pokemon will not exceed 100.
    • The hp will not exceed 200.

If two or more Pokemon share all stats, then they can be arranged however you like.

The output will be the sorted list.

This is , so shortest code in bytes wins.


  • Is the challenge too easy/hard?
  • Any improvements to my explanation?
  • 1
    \$\begingroup\$ Could you perhaps add some test cases? Also, since you haven't mentioned it I'm assuming the input is unrestricted? (I.e. we're allowed to use an array as parameter, a comma-separated string, a list, etc. Everyone's own choice?) And one very important question, does the list potentially include all 721 Pokémon (with more incoming in generation 7..) \$\endgroup\$ Commented Aug 4, 2016 at 12:38
  • \$\begingroup\$ I think this challenge is pretty chameleon-y. I'm not sure if there is a dupe target floating around, but even if it isn't a dupe I'm not convinced this adds very much to the basic sorting challenges. \$\endgroup\$ Commented Aug 4, 2016 at 18:26
  • \$\begingroup\$ @KevinCruijssen It can contain anything, really - it could contain all 721 Pokemon available, but it doesn't have to contain Pokemon at all. \$\endgroup\$
    – clismique
    Commented Aug 5, 2016 at 7:58
  • \$\begingroup\$ @DerpfacePython I know, it's just a string. My last question was kinda a sarcastic one.. :) \$\endgroup\$ Commented Aug 5, 2016 at 8:25

Make a Four Color Map

The Four Color Theorem states that it is possible to color any map separated into contiguous regions using only four colors such that no two adjacent regions are the same color. While the Five Color Theorem has been proven, no proof exists for only using four colors (though there have also been no counterexamples). Given an image containing white regions separated by black borders, generate a four color map. You may assume that the borders of the image are also region borders and that shared corners do not count as adjacencies.

Related: Four Color Theorem


An image in a standard format containing white regions separated by black borders


Displaying or writing an image file in any standard format that contains the original image colored according to the Four Color Theorem


Your colorings do not need to match mine, they just need to be valid solutions ====> ====>

Note that the map of the US is not colored by state, it is colored by contiguous borders

This is so shortest code wins!

  • \$\begingroup\$ Isn't the first example invalid? I see two adjacent red regions in the bottom left. \$\endgroup\$ Commented Aug 5, 2016 at 17:11
  • \$\begingroup\$ Whoops! Thanks, I'll fix that. \$\endgroup\$ Commented Aug 5, 2016 at 17:14
  • 1
    \$\begingroup\$ I thought the four-color one was definitively proven a couple years ago? \$\endgroup\$ Commented Aug 5, 2016 at 18:19
  • \$\begingroup\$ It might have been, I was just going off of wikipedia. I just read the Wolfram article on it and it looks like it was proven for maps that are flat (and maybe all maps?) but I don't 100% follow it so not positive. \$\endgroup\$ Commented Aug 5, 2016 at 18:28
  • 1
    \$\begingroup\$ 1. The four colour theorem was proven in the 70s. 2. This is essentially a dupe of this question but with a really bad input format. \$\endgroup\$ Commented Aug 5, 2016 at 21:09
  • \$\begingroup\$ Here's the relevant Wikipedia section if you're looking for more info on the proof \$\endgroup\$ Commented Aug 6, 2016 at 14:42
  • \$\begingroup\$ The theorem was "disproved" by counterexample on some mailing list I believe. It was a joke. Someone produced a pretty complex map and claimed that it couldn't be colored with only 4 colors. I think he was just seeing if he could get people to waste time looking at it. \$\endgroup\$
    – Liam
    Commented Aug 10, 2016 at 23:48

Your job is to take an input like below:

Hello, world!

π is cool!

and output it as a series of <kbd>.

Every character, including enter and space get their own <kbd> HTML element, like so:



Other characters like space and newline that are invisible and typeable (so no option, command, control, function, escape, delete, arrow keys, etc.) are all uppercase, like SPACE and NEWLINE. OPT is an exception because it is used to create new characters. The code for these characters are:

<kbd>SPACE</kbd> <kbd>NEWLINE</kbd>

Special characters needing to be typed using option use the following format OPT + P instead of π. The following code is used for these:

<kbd><kbd>OPT</kbd> + <kbd>P</kbd></kbd>

The same applies to characters that are typed using OPT + SHIFT + K instead of .

We're assuming this is a QWERTY layout computer.

Here are the available option keys:

Option keys

Any of the orange keys are not allowed in this.

Here are the OPT + SHIFT keys:

Option shift keys

  • 5
    \$\begingroup\$ +1 for well laid out challenge -1 for being mac specific \$\endgroup\$ Commented Aug 9, 2016 at 19:33
  • \$\begingroup\$ @RohanJhunjhunwala It's not technically Mac-specific, but rather uses the same shortcut keys to type special characters as a Mac. \$\endgroup\$ Commented Aug 9, 2016 at 19:35
  • 1
    \$\begingroup\$ Yeah, Ina all seriousness here have an upvote, It does seem like targetting the opt key may be somewhat confusing for some S̶a̶n̶e̶ pc users. \$\endgroup\$ Commented Aug 9, 2016 at 19:39
  • 1
    \$\begingroup\$ For each letter you check which of the three character sets it is in then add some fixed strings to it. It doesn't seem to me like there is much interesting stuff to do in there? I'm not sure this adds much to the other keyboard focused challenges that we have. \$\endgroup\$ Commented Aug 9, 2016 at 20:23
  • \$\begingroup\$ Do all of those characters even have Unicode codepoints? \$\endgroup\$ Commented Aug 10, 2016 at 5:31

How synchronized are my clocks?

I have two clocks, A and B, and A always shows the exact time, however B is off by a certain amount of time, that I'd like to find out. (I know A and B run at the exact same speed.) I cannot read the exact time of both simultaneously, that means I can only switch back and forth and read the time sequentially. (For the sake of simplicity, both show their time as a real number (lets say hours), and each real number encodes an unique point in time.)

So here is an example: B: 1, A: 3, A: 5, B: 4.5. We see because of the first two entries B: 1, A: 3 that B is behind A by at most 2 hours, and that because of the last two entries A: 5, B: 4.5 we see that B is behind A by at least half an hour. So the possible interval of how much B is off is [-2,-0.5].


Given a list of timestamps with their labels, return the possible interval by how much B can be off.


  • The list can be in any convenient format like [(timestamp, label),...] or as two lists [timestamp,...],[label,...] e.t.c
  • You can assume that all the readings from A are in ascending. (and the same for B)
  • If there is no such time interval, output something falsy.


(more to be added)

label  A  B  A
time   1  4  5
output [-1,3]

label  A B B A
time   1 2 5 2.5
output false


  • Should only valid cases be considered, or should there be a check for invalid ones (remove point 2 or 3 of the details?)

  • Should the challenge be restricted to alternating readings (ABABABABABA) or should random ones be allowed (ABBAAABABAABBBABBBBB)? Restricting to alternating readings would make it pretty much trivial.

  • \$\begingroup\$ IMO go with alternating readings \$\endgroup\$
    – Downgoat
    Commented Aug 11, 2016 at 23:26
  • \$\begingroup\$ @Downgoat But that makes it almost trivial I think... \$\endgroup\$
    – flawr
    Commented Aug 11, 2016 at 23:27
  • 1
    \$\begingroup\$ We see that B is at least two hours behind, but at most half an hour behind. I find that wording confusing. How about this? We see (B: 1, A: 3) that B is behind A by at most 2 hours, and that (A: 5, B: 4.5) B is behind A by at least half an hour. \$\endgroup\$
    – Luis Mendo
    Commented Aug 11, 2016 at 23:42
  • \$\begingroup\$ @LuisMendo Thank you, I'm going to correct that. \$\endgroup\$
    – flawr
    Commented Aug 12, 2016 at 8:41

Print a booklet

I want to take a PDF document and put four pages of that document onto the front and four pages onto the back of a sheet of paper. Then I'll fold and cut that page so that I end up with a 1/4─size booklet that holds 8 pages. This would produce two folios comprising one signature.

           Fold here
       │    │    │
       │    │    │ ← Outer folio
Cut    │    │    │
here → ╞════╪════╡
       │    │    │
       │    │    │ ← Inner folio
       │    │    │

LaTeX's pdfpages package allows me to place 2x2 pages of a PDF per sheet of paper with a given page ordering.

If I were to specify the option pages={2,7,4,5,8,1,6,3} to pdfpages, I would get:

       Front of sheet

        (1)     (8)     Back of sheet
          \     /
        ┌────┬────┐      (7)     (2)
        │    │    │        \     /
Outer   │  2 │  7 │      ┌────┬────┐
folio → │    │    │      │    │    │
        ╞════╪════╡      │  8 │  1 │ ← Outer folio
Inner   │    │    │      │    │    │
folio → │  4 │  5 │      ╞════╪════╡
        │    │    │      │    │    │
        └────┴────┘      │  6 │  3 │ ← Inner folio
        /          \     │    │    │
     (3)            (6)  └────┴────┘
                        /           \
                      (5)            (4)

(Numbers put in parenthesis are referring to the back of the page.)

Why do we need that strange order of numbers? So that the fronts and backs of pages line up when put into the signature. This is how you read the book:

    Start here at (1) on the back. Continue to 2 on the front.
      │      End here at (8)
      ↓     /
    │    │    │
    │  2 │  7 │ ← Outer folio
    │    │    │
On to (3) in
inner folio
      ↓     ↑
          On to (6)
          in outer folio
    │    │    │
    │  4 │  5 │ ← Inner folio
    │    │    │

But that's just for two folios from one sheet of paper. What if I want to use two sheets of paper, make four folios, and still combine all of them in one signature?

            Start at (1)
             │      End here at (16)
             ↓       │
            (1)    (16)  (5)    (12)
              \     /      \     /
            ┌────┬────┐  ┌────┬────┐
            │    │    │  │    │    │
Outermost → │  2 │ 15 │  │  6 │ 11 │ ← Folio #3
 folio (#1) │    │    │  │    │    │
            ╞════╪════╡  ╞════╪════╡
            │    │    │  │    │    │
 Folio #2 → │  4 │ 13 │  │  8 │  9 │ ← Innermost
            │    │    │  │    │    │    folio (#4)      
            └────┴────┘  └────┴────┘
              /     \      /     \
            (3)    (14)  (7)    (10)

            Front of      Front of
             sheet 1       sheet 2

And your LaTeX option would be:



Write a function taking an integer n of the number of pages in the final booklet (8 and 16 in the examples above) and returning a list integers (of length n and ranging from 1 to n) for the page numbers in the right order.


> f(8)
=> [2,7,4,5,8,1,6,3]

> f(16)
=> [2,15,4,13,16,1,14,3,6,11,8,9,12,5,10,7]

Since we're dividing a sheet of paper into 4 pieces and using front and back, the input is always a multiple of 8. If the input is not a multiple of 8, the output is not defined but would prefer that it's rounded up to the next multiple of 8.

  • 1
    \$\begingroup\$ Is the code required to work for integers that don't fit and leave unused pages? Should such integers be rounded up to the next integer that fits? \$\endgroup\$ Commented Aug 12, 2016 at 11:40
  • 2
    \$\begingroup\$ 1. I don't understand the repeated mention of US Letter. Surely this is completely independent of the paper size? 2. I don't understand the first two diagrams. It seems to me that the instructions in the first diagram give a booklet with page order 2,3,4,1, and the folds in the two diagrams can only be consistent with each other if one of the 1s is turned upside down. 3. The meaning of folio doesn't seem to be consistent between the 4-page example (which has two folios, implying that a folio is a half-sheet of paper) and the 8-page example (which has just an outer and an inner folio). \$\endgroup\$ Commented Aug 12, 2016 at 12:09
  • \$\begingroup\$ I specified what to do with integers that don't fit, removed mention of US letter, and simplified the diagrams. \$\endgroup\$
    – Caleb Paul
    Commented Aug 12, 2016 at 16:52
  • \$\begingroup\$ @PeterTaylor, the first example is 8 pages (1 physical sheet of paper divided into 2 folios), the second example is 16 pages (2 physical sheets of paper divided into 4 folios). A folio is just a half sheet of paper. I cleaned up the terminology of sheet vs page in the question. \$\endgroup\$
    – Caleb Paul
    Commented Aug 12, 2016 at 16:56
  • \$\begingroup\$ Ok, I think it's clearer now, but to check that I've understood what the task is. Would the following serve as a reference implementation? Given n which is a multiple of 8, form the array [1 2 ... n-1 n]. Then while the array is non-empty, remove the first four elements and the last four elements, apply permutation [2 7 4 5 8 1 6 3] to them, and recurse on the remaining elements. \$\endgroup\$ Commented Aug 12, 2016 at 17:40
  • \$\begingroup\$ Might turn into something interesting, but if you just print, cut, fold, then sort and glue, there is nothing keeping you from switching upper with lower halfs, turning half-pages around or swapping half-pages between pages. You either need to specify the exact way the paper will be combined or you should add information which solutions are acceptable. \$\endgroup\$
    – MarLinn
    Commented Aug 13, 2016 at 1:20

Count Langford pairings

A Langford pairing is a permutation of the numbers 1, 1, 2, 2, ..., n, n such that there is one number between the 1s, two numbers between the 2s, etc. E.g. (with the pairs marked)

+-----------+ +---------------+
| +-----+   | | +---------+   |
| |     |   | | |         |   |
5 2 8 6 2 3 5 7 4 3 6 8 1 4 1 7
    | |   |       | | | |   |
    | |   +-------+ | | +---+
    | +-------------+ |

If we reverse a Langford pairing then obviously we get another Langford pairing. The number of distinct Langford pairings (i.e. modulo this symmetry) for given n is OEIS sequence A014552.

Write a program which takes n as either a command-line argument or on stdin and prints the number of distinct Langford pairings for that n. You may assume that the input given will be a positive integer no greater than 32.

To avoid hard-coding, your program must be capable of calculating the number of Langford pairings for n=32, optionally modulo a number of your choice which is at least 230; and the only case splitting permitted for valid input is to split on the value of n % 4.

To avoid brute-forcing, your program must be capable of calculating the number of Langford pairings for n=16 in less than 15 minutes on my reference machine. (TODO). The standard approach is an algebraic technique due to Mike Godfrey and works by evaluating a generating function at {-1,1}^2n, but variants such as evaluating Godfrey's generating function at {0,1}^2n and using inclusion-exclusion are also possible.

The time limit is about twice the time required by my (partially optimised) reference solution, an algebraic approach in Java; a fully optimised approach in C should have a lot of slack. That gives people a trade-off in the symmetries they use, and should allow slow scripting languages to submit valid answers but at a penalty of having to spend more code on handling symmetries than faster languages.

However, I'm worried that it might allow trivial modification of answers to Langford strings , so I probably need a reference implementation which works by enumeration for comparison.

  • 4
    \$\begingroup\$ Wow, that's really unhelpful. That page for A014552 has a forumla of a(n) = A176127(n)/2, and guess what the page for A176127 has? Yep, a(n) = 2 * A014552(n). :P \$\endgroup\$
    – Doorknob
    Commented Oct 8, 2014 at 11:38
  • \$\begingroup\$ @PeterTaylor could you give us some hints on optimisation? As in, the basic hacks that nearly everyone will do? \$\endgroup\$ Commented Oct 8, 2014 at 12:39
  • \$\begingroup\$ There's this now. \$\endgroup\$ Commented Aug 14, 2016 at 14:18
  • 1
    \$\begingroup\$ @MartinEnder, I ran across the linked page the other day when I was tidying my bookmarks (it now 404s), but I didn't remember that this was in the sandbox. IMO the performance requirement and ability to avoid enumeration mean that it wouldn't be a dupe. May try to write a reference implementation tomorrow, since it's a public holiday here. \$\endgroup\$ Commented Aug 14, 2016 at 16:35
  • \$\begingroup\$ Yeah I wasn't sure whether it would be a dupe (or whether there would be ways to avoid enumeration), but I figured you'd be the best judge of that, so I just thought I'd let you know. \$\endgroup\$ Commented Aug 14, 2016 at 17:40

The Coin Flop KoTH

In this challenge, you start out with a stack of 100 coins, alternating between gold and silver:

1.   Gold
2.   Silver
3.   Gold
4.   Silver
99.  Gold
100. Silver

Now, Gold, Inc. will pay you for any gold coins you can give them. Furthermore, they really like bulk shipment. If a shipment contains N coins, they will pay you N^2 for that shipment.

However, you've only got 1 truck to share between you and your opponent, who has a similar contract with Silver, Inc.

Game play

Each turn, the following steps occur:

  1. Flip a section of coins (like pancakes)
  2. Collect the top coins (of the same type)
  3. Ship off the collected coins (worth N^2)

1. Flip:

You or your opponent can each select a range to reverse. For example, if you selected the range [1,3], the following would occur:

Gold                        Gold
Silver                      Gold
Gold          ->            Gold
Gold                        Silver
Silver                      Silver

Notice how the top stack now has 3 golds in a row, which would be worth 9.

However, you only get to flip every other turn, and your opponent gets to flip on the other turns.

2. Collect

We collect all similar coins from the top of the stack, and put them in the truck:


Would result in 2 Silvers being put in the truck.

3. Ship

If the truck contains gold coins, then we send it off to Gold, Inc and we get paid N^2, where N is the number of coins in the truck. (Our opponent gets paid if the truck contains silver coins)

After the stack is empty, the player with the most money wins!

Sandbox questions:

  1. Is this clear?
  2. Does this seem interesting at all (if it isn't, please say so)? What are some interesting strategies you can come up with?
  3. Is there a never-lose strategy?
  4. I'm debating adding a "Freeze" as an alternative to "Flip", which would cause 2 collect/ship actions to occur. (Your opponent's turn would then be next)
  • \$\begingroup\$ Could you add tags so it's clear this is a KOTH? \$\endgroup\$
    – Zgarb
    Commented Aug 15, 2016 at 15:31
  • \$\begingroup\$ "If the truck contains gold coins, then we send it off to Gold, Inc (otherwise Silver, Inc), and we get paid" Is this correct? Earlier you said that we had a contract with Gold, Inc and the opponent with Silver, Inc, so it seems that we should be paid for gold and the opponent for silver. \$\endgroup\$ Commented Aug 15, 2016 at 21:02
  • \$\begingroup\$ @PeterTaylor does that make it clearer? \$\endgroup\$ Commented Aug 15, 2016 at 21:09
  • \$\begingroup\$ Yes, thanks. Follow-up: I presume the controller will show different things to the two players so we both think we're the one collecting gold? \$\endgroup\$ Commented Aug 16, 2016 at 5:38
  • \$\begingroup\$ @PeterTaylor correct. The only difference players will notice is whether or not Gold is the first coin. \$\endgroup\$ Commented Aug 16, 2016 at 12:20

Still to-do:

  1. Add more test cases
  2. Make input requirements a little looser
  3. Make output requirements looser
  4. Specify that a full program is not required
  5. Change the name of gem-elements maybe?
  6. Come up with a title
  7. Come up with a cool story

I saw this as a problem over on CodeReview, here is the original question. I thought it would be fun to golf.

You have discovered various rocks. Each rock is composed of various elements, and each element is represented by a lowercase letter from 'a' to 'z'. The same element can be present multiple times in a rock. An element is called a 'common-element' if it occurs at least once in each of the rocks. Given the list of rocks you have to determine how many different kinds of common-elements you have.

Input Format

  • Each rock is a string which consists of lowercase letters from 'a' to 'z' representing elements
  • You can take the strings in whatever way is easy for you (lines from STDIN, pipe delimited STDIN, array of strings as a method param, etc.)

Output Format

  • The number of different types of common-elements for the given list of rocks. This can be as an integer or string


  • There will always be at least one rock
  • Each rock will always have at least one element
  • You do not need to make a full program (functions & methods are allowed)

Sample Input


Sample Output



Only 'a' and 'b' are common-elements since these are the only characters that occur in each of the rocks' composition.

More test cases











  • 3
    \$\begingroup\$ N doesn't seem to actually be a useful input, so I'd consider making it optional. In addition, tight I/O requirements are usually frowned upon, I'd consider modifying it to allow any format that doesn't add any additional information. I'd also recommend removing the quote block, and adding at least one test case with N=1 and one where the result itszero. Good luck with your challenge and thanks for using the sandbox! :) \$\endgroup\$ Commented Jun 23, 2016 at 19:47
  • 1
    \$\begingroup\$ Also can we take the input in the default list/array format for our language? As FryAmTheEggman, good luck with the challenge! \$\endgroup\$
    – Blue
    Commented Jun 23, 2016 at 20:04
  • \$\begingroup\$ How do I say "any format that doesn't add additional information" in a way that doesn't sound silly? Is that fine as-is? \$\endgroup\$ Commented Aug 11, 2016 at 18:36
  • \$\begingroup\$ Nice edits, looking much better! If you want an example of a nice way to word the preamble, you could try emulating this question. I think "any reasonable format" is a fine way to say what you want, but what you have is fine, too. \$\endgroup\$ Commented Aug 11, 2016 at 19:44
  • 2
    \$\begingroup\$ This might be fun to golf in Java, but in the languages which are predominantly used on this site nowadays it's two built-ins and something like 3 to 6 characters depending on the language, so it's actually a pretty boring question. \$\endgroup\$ Commented Aug 11, 2016 at 21:44


This is a KOTH challenge based on the popular board game Stratego.


Stratego is played on a 10x10 board which looks like this (starting position):


A **********
B **********
C **********
D **********
E ..~~..~~..
F ..~~..~~..
G xxxxxxxxxx
H xxxxxxxxxx
I xxxxxxxxxx
J xxxxxxxxxx

*: enemy piece; x: your piece, .: empty space, ~: lake

There are twelve types of pieces: the flag (F), the bomb (B), the spy (S), and pieces numbered 2-10 (ten is 0). You can see the identities of your pieces, but not your opponent's. Each player starts with:

  • 6 bombs
  • 1 flag
  • 1 ten
  • 1 nine
  • 2 eights
  • 3 sevens
  • 4 sixes
  • 4 fives
  • 4 fours
  • 5 threes (miners)
  • 8 twos (scouts)
  • 1 spy

A player may arrange their pieces however they wish within their starting area.

The players take turns moving one piece into an adjacent square.

  • The bomb and flag may not move.
  • Twos (scouts) may move any number of squares in one direction, like a chess rook.
  • You may not move into a square containing one of your pieces.
  • If you attempt to move into a piece containing an enemy piece:
    • The identities of both pieces are revealed to the other player.
    • If both pieces are equal, they both lose.
    • If both pieces are numbered, the higher piece wins.
    • If the attacked piece is a bomb…
      • and the other piece is a miner, the miner wins.
      • otherwise, the bomb wins.
    • If the attacked piece is the flag, then the player owning the flag loses.
    • If the attacking piece is the spy…
      • and the defending piece is a 10, the spy wins.
      • otherwise, the spy loses.
    • If the attacked piece is the spy, it loses.
    • If the attacking piece won, the attacked piece is removed from the board and the attacking piece moves into its place.
    • If the attacked piece won, the attacking piece is removed from the board and the attacked piece remains in place.
    • If both pieces lose, they are both removed from the board.
  • A scout's move may end on an enemy piece, but it may not go over enemy pieces during its move.

Play continues until one player loses their flag or is unable to move on their turn, at which point that player loses.


Bots may be written in any language that I can get to run on macOS. They will communicate with the server using newline-separated JSON on stdin/stdout. When a bot is started, it should send the following message:

  "type": "start",
  "layout": "..." /* starting layout, as 4x10 string; last line is edge of board */

When it is the bot's turn, the server will send the following message:

  "type": "turn",
  "board": "...", /* current board state, as 10x10 string; you half of the board is always on the bottom */
  "yourPreviousTurn": { /* result of your previous turn; not present on your first turn */
    "from": "B8",
    "to": "B9", /* you moved a piece from B8 to B9 */
    "movedPiece": "5" /* you moved a 5 */
    "attackedPiece": "8" /* the piece you attacked was an 8; only present if you attacked a piece on your last turn */,
    "winner": "them" /* their piece won; only present if you attacked a piece */
  "theirPreviousTurn": { /* result of the turn they just took; not present on first turn of the game */
    "from": "H8",
    "to": "G8",
    "movedPiece": "4" /* they moved a 4; only present if they attacked */
    "attackedPiece": "9" /* they attacked your 9; only present if they attacked */,
    "winner": "you" /* your piece won; only present if they attacked */
  "yourGraveyard": ["B", "3", ...], /* array of your pieces that have already died */
  "theirGraveyard": ["7", "4", ...] /* array of their pieces that have already died */

You must respond with:

  "type": "move",
  "from": "A6",
  "to": "A7"


Submit your bot as a pull request to [github link added here]. You do not need to include your entire bot in the SE answer, but please include the main/interesting parts of the code; I would recommend not including the layouts that you are using so that they remain secret (not that secret, but better than nothing). I will run bots regularly and post the latest scores here.

  • \$\begingroup\$ 1. Can you give references to indicate that there is no legal issue here (with respect to copyright, trademarks, etc)? 2. Why 2 to 9 and then 0? Would it be simpler to use 1 to 9? 3. The list of starting pieces could be presented much more succinctly as a single string (BBBBBBF9...), and the combat table as a grid with columns and rows headed by B, F, etc and using one of three symbols to indicate the outcome. 4. Docker images? Are you serious? You should be trying to lower the barrier of entry, not raise it. \$\endgroup\$ Commented Aug 25, 2016 at 9:57
  • 1
    \$\begingroup\$ This is a dupe of my stratego challenge.... \$\endgroup\$ Commented Aug 25, 2016 at 14:10
  • \$\begingroup\$ meta.codegolf.stackexchange.com/a/9653/46918 \$\endgroup\$ Commented Aug 25, 2016 at 14:11
  • \$\begingroup\$ 1. I feel that the copyright on the game is unlikely to be enforced for something this small. 2. The original game uses 2-10, so I am staying with that. 3. That would be more succinct, but less useful for understanding the game -- it would be nice not to have to analyze a table to understand things like "larger number wins." 4. Agreed. I will edit to remove the Docker requirement. \$\endgroup\$
    – Gaelan
    Commented Aug 25, 2016 at 15:29
  • \$\begingroup\$ @Peter see above \$\endgroup\$
    – Gaelan
    Commented Aug 25, 2016 at 15:31
  • \$\begingroup\$ Whether the copyright holder decides to take action or not is irrelevant: if posting this challenge would violate copyright then this site's legal terms prohibit it. (CC @RohanJhunjhunwala). \$\endgroup\$ Commented Aug 25, 2016 at 16:48
  • \$\begingroup\$ @PeterTaylor game rules can not be copyrighted: copyright.gov/fls/fl108.pdf \$\endgroup\$
    – Gaelan
    Commented Aug 25, 2016 at 17:09
  • 1
    \$\begingroup\$ @PeterTaylor from what I understand, developing an AI to play a game isn't really breaching the copyright of the game holder. However I feel we should take this to meta. \$\endgroup\$ Commented Aug 25, 2016 at 17:31
  • \$\begingroup\$ @PeterTaylor feel free to continue to discuss this here meta.codegolf.stackexchange.com/q/9925/46918 \$\endgroup\$ Commented Aug 25, 2016 at 17:35
  • \$\begingroup\$ Gaelan, the document you link states that game rules are subject to copyright: it's the mechanics which aren't. The design elements probably extend to such matters as board layout and tile distribution: or, at least, the major Scrabble clones' owners weren't confident enough of winning against Hasbro, and changed their layouts and distributions under legal pressure. And I (and the SE legal terms) also mentioned trademarks: Stratego is a registered trademark in the US. \$\endgroup\$ Commented Aug 25, 2016 at 21:49
  • \$\begingroup\$ @RohanJhunjhunwala, the AI might not be, but a king-of-the-hill doesn't work without a controller. \$\endgroup\$ Commented Aug 25, 2016 at 21:50
  • \$\begingroup\$ @PeterTaylor I will rename the challenge to avoid the trademark issue. Nothing in the PDF says anything about rules being copyrighted. It says the specific wording of the rules that came with the game are copyrightable, but I wrote the rules in my own words from memory. Also, see the dupe link in the meta question. \$\endgroup\$
    – Gaelan
    Commented Aug 25, 2016 at 21:57
  • \$\begingroup\$ @Gaelan you have failed to address the issue that it is a dupe of my challenge \$\endgroup\$ Commented Aug 25, 2016 at 22:00
  • \$\begingroup\$ @PeterTaylor sure I can edit the name of my challenge to avoid stomping on a trademark. (But from what I understand you can saw the name of a company, without infringing their trademarks) \$\endgroup\$ Commented Aug 25, 2016 at 22:01
  • \$\begingroup\$ @RohanJhunjhunwala sorry, I didn't realize your challenge was this recent. Are you still planning on running your challenge? \$\endgroup\$
    – Gaelan
    Commented Aug 25, 2016 at 22:03
29 30
32 33

You must log in to answer this question.

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