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


4486 Answers 4486

110 111
113 114


Often computers are used to perform consecutive jobs. Sometimes the order of doing these jobs does not matter. Other times there are dependencies between jobs that restrict the order that jobs can be performed. Additionally, jobs may require significant resources to store results, so it may be necessary to first schedule those jobs that will consume previous results before performing jobs that produce even more results. Furthermore, there may be significant costs to change from one type of job to another. The challenge then becomes finding the optimal execution order of jobs.


Allow me to illustrate the problem with an example. Consider a list of 10 jobs, numbered 0 to 9. Each of these jobs can be dependent on zero or more other jobs. (Assume there are no circular dependencies.) For example:

Job : Dependent on
---   ------------
0   : 8
1   : 6
2   :
3   : 0 6 9
4   : 7 9
5   : 2
6   : 4 8
7   :
8   : 9
9   :

This can be illustrated graphically as follows:


One possible solution to this particular example is to perform the 10 jobs in the order: 9 8 7 4 6 0 2 1 3 5 While this solution satisfies the dependency requirements, it is not ideal. To see why, let us perform the jobs one at a time:

Job : Results stored in memory
---   ------------------------
9   : 9
8   : 8 9
7   : 7 8 9
4   : 4 8 9
6   : 6 8 9
0   : 0 6 9
2   : 0 2 6 9
1   : 0 1 2 6 9
3   : 1 2 3
5   : 1 3 5

After performing the first job (job 9), we only have the result of job 9 in memory. After performing job 8 we need to store the results of 8 and 9, and after job 7 we have the results of jobs 7, 8 and 9. After performing job 4 we find that the results of job 7 is no longer needed and we can discard that, leaving only the results of job 4, 8 and 9. Carrying on we find that the worst case memory usage is after job 1 when we have to store the results of 5 different jobs (0, 1, 2, 6 and 9).

As it turns out there is a better solution to this example, and that is to do the jobs in the order: 7 9 4 8 6 0 3 2 5 1 The memory usage is then:

Job : Results stored in memory
---   ------------------------
7   : 7
9   : 7 9
4   : 4 9
8   : 4 8 9
6   : 6 8 9
0   : 0 6 9
3   : 3 6
2   : 2 3 6
5   : 3 5 6
1   : 1 3 5

This time we only ever needed to store the results of 3 jobs in memory, instead of the 5 in the previous solution.

Finally, consider that each job is of a certain "type", and changing from one type to another is something that should be avoided. For example, let's say we have 3 types of jobs: A, B and C, and our 10 jobs in the example have the following types: Jobs 0-3 is type A, jobs 4-7 is type B, and jobs 8 and 9 is type C.

Job : Results stored in memory : Job Type Change
---   ------------------------ : ---------------
7   : 7                          B
9   : 7 9                        C
4   : 4 9                        B
8   : 4 8 9                      C
6   : 6 8 9                      B
0   : 0 6 9                      A
3   : 3 6                        .
2   : 2 3 6                      .
5   : 3 5 6                      B
1   : 1 3 5                      A

As you can see, we had to change the job type 8 times: B C B C B A B A

When minimizing job changes, while still keeping maximum memory usage to 3, we now find that the optimal solution is: 9 8 7 4 6 0 3 1 2 5

Job : Results stored in memory : Job Type Change
---   ------------------------ : ---------------
9   : 9                          C
8   : 8 9                        .
7   : 7 8 9                      B
4   : 4 8 9                      .
6   : 6 8 9                      .
0   : 0 6 9                      A
3   : 3 6                        .
1   : 1 3                        .
2   : 1 2 3                      .
5   : 1 3 5                      B

This solution require only 4 job type changes (C B A B), while still only needing memory to store 3 results.

The solutions to this example that I presented here was found using a brute force search, ie going through every permutation of job order. From doing this I can tell you that this example has 1485 solutions that satisfy the dependency requirements. Of these 1485 solutions only 15 solutions require memory for no more than 3 results. Of these 15 solutions only 2 require only 4 job changes. The one is shown above (9 8 7 4 6 0 3 1 2 5). The other is: 9 8 7 4 6 0 3 2 1 5.

Unfortunately, brute force is not viable when the total number of jobs increase beyond 10, eg 100. The challenge is to come up with an algorithm that can find the optimal solution (or any one of them if there are more than one) using an algorithm that significantly outperforms brute force.

Example Input and Output

The input to the algorithm is a list of N jobs numbered 0 to N-1, each with a job type (A-Z) followed by a list of zero or more dependencies, eg:

0, A, 8
1, A, 6
2, A
3, A, 0 6 9
4, B, 7 9
5, B, 2
6, B, 4 8
7, B
8, C, 9
9, C

The output of the algorithm is the optimal execution order, eg:

9 8 7 4 6 0 3 1 2 5

Answers may be presented in any programming language or even pseudo code. I will translate them all to C++ and test them for correctness against the brute force algorithm using randomly generated inputs. The winner will be the algorithm that is fastest (and correct).

  • \$\begingroup\$ So, is this fastest-algorithm or fastest-code? \$\endgroup\$
    – wastl
    Jun 9, 2018 at 18:35
  • \$\begingroup\$ What if there is a solution with memory 2, job changes 3, and one with memory 3, job changes 2? In other words, which one is given priority? \$\endgroup\$
    – wastl
    Jun 9, 2018 at 18:39
  • \$\begingroup\$ @wastl I think fastest-code would be the easiest because it might get difficult determining which is the fastest-algorithm. Least memory usage has a higher priority than least job changes. \$\endgroup\$
    – Barnett
    Jun 12, 2018 at 9:36

I want to do this, Render an ASCII maze but with ascii pipe characters.
I know this is similar, but I think the extra logic required to figure out which character to put at each position makes this sufficiently different.

here is what I am thinking of asking.

Write code that replaces non whitespace characters in a string with ascii pipe characters depending on adjacency to other non-whitespace characters.
this will create something like a maze where non-whitespace characters are the walls, and whitespace is abscence of walls here are the rules

your code should take its input from stdin and output to stdout

This table shows the correct output character for each combination of adjacent walls in directions: Left, Down, Up, and Right

 L D U R -> Output
 0 0 0 0 -> any non-whitespace character
 1 0 0 0 -> ─
 0 0 0 1 -> ─
 1 0 0 1 -> ─
 0 1 0 0 -> │
 0 0 1 0 -> │
 0 1 1 0 -> │
 1 1 0 0 -> ┐
 1 0 1 0 -> ┘
 0 1 0 1 -> ┌
 0 0 1 1 -> └
 1 1 1 0 -> ┤
 1 1 0 1 -> ┬
 1 0 1 1 -> ┴
 0 1 1 1 -> ├
 1 1 1 1 -> ┼

if characters are on the edge of a string then they should treat the outside as whitespace

This will be a code golf challenge

  • 1
    \$\begingroup\$ codegolf.stackexchange.com/q/80634/194 ? \$\endgroup\$ Jun 6, 2018 at 8:51
  • \$\begingroup\$ I didn't see that one, but I still think this is different, because this does not require specific characters as input, the input can be any string \$\endgroup\$
    – JoshM
    Jun 6, 2018 at 13:59
  • \$\begingroup\$ Can you add some test cases? \$\endgroup\$
    – 3D1T0R
    Jun 6, 2018 at 18:18
  • 1
    \$\begingroup\$ Although there are some minor differences, this was probably be closed as a duplicate. \$\endgroup\$
    – wastl
    Jun 6, 2018 at 19:23
  • \$\begingroup\$ i'll try to think of something to make this one different \$\endgroup\$
    – JoshM
    Jun 6, 2018 at 19:30

N represented with only 1s in any base from 2 to N-2?

This is mostly a less interesting special case of Repdigit Base Finding so I won't submit.

Any positive integer N can be expressed as 11 in base N-1 or as N concatenated 1s in base 1. Let's call those the trivial cases in which N can be represented using only 1s. Let's call any other "all 1s" representation non-trivial. Some examples:

  • 7 has an "all 1s" representation in base 2, so 7 has a non-trivial "all 1s" representation.
  • 16 has no non-trivial "all 1s" representation.
  • 11 itself has no non-trivial "all 1s" representation by my definition because it is "all 1s" in base 10, which is 11-1.


Provide a program/function that produces one of two distinct, consistent values for whether or not an integer N > 3 has a non-trivial "all 1s" representation in a base between 2 and N-2.

  • \$\begingroup\$ I was thrown off by the 11 example, because there is quite clearly a way to express that using only 1, but then I realized that it's trivial because base 10 is base n-1 in that situation. That might be a good note to add. \$\endgroup\$ Jun 6, 2018 at 15:54
  • \$\begingroup\$ This should generate the truthy numbers up to 1000 \$\endgroup\$ Jun 6, 2018 at 20:37
  • \$\begingroup\$ @KamilDrakari very nice, thanks. I wonder how many numbers have more than one such base (like 31)? That's an entirely different challenge. \$\endgroup\$
    – ngm
    Jun 6, 2018 at 20:42
  • \$\begingroup\$ I updated the code to search for duplicates, but could only find 31 and 8191. Golfed to fit the link in a comment \$\endgroup\$ Jun 6, 2018 at 21:22
  • \$\begingroup\$ Table seems wrong \$\endgroup\$
    – l4m2
    Jun 7, 2018 at 4:20
  • \$\begingroup\$ Not an exact dupe, but closely related: codegolf.stackexchange.com/q/75623/194 . \$\endgroup\$ Jun 7, 2018 at 8:01
  • \$\begingroup\$ Note that these are numbers of the form (b**x - 1) / (b-1) for integer b > 1 and integer x > 2. \$\endgroup\$ Jun 7, 2018 at 8:03
  • 1
    \$\begingroup\$ Also: OEIS A053696. Either your reference implementation was broken or you didn't remove duplicates. \$\endgroup\$ Jun 7, 2018 at 8:10
  • \$\begingroup\$ @PeterTaylor thank you for alerting me to the other challenge, which is close enough for me to say this one is a dupe (at least and easier and less interesting special case.) \$\endgroup\$
    – ngm
    Jun 8, 2018 at 18:24
  • \$\begingroup\$ Thanks for using the Sandbox! \$\endgroup\$
    – JayCe
    Jun 9, 2018 at 23:10

# Proposed Question #

List the amount of factors for a given number.

For Example:

If given 1936, the output should be 15 (as 1936 has 15 factors)
If given 196, the output should be 9 (as 196 has 9 factors)

Test cases:

  • 64 - Outputs 7
  • 196 - Outputs 9
  • 1936 - Outputs 15


Code Golf - Least number of bytes for each language wins (No answer)

I have made my own in JavaScript - 143 Bytes.
Available here: https://glot.io/snippets/f1tl0vrnmy
To use different numbers, change the console.log(f(64).length) to console.log(f(###).length) where ### is your desired number.

BTW, if JavaScript or similar, only the defining function is considered in code length. The method of outputting (eg. console.log) does not count.

  • \$\begingroup\$ I'm not sure as I'm not a native speaker, but isn't that called "divisor" (not factor)? \$\endgroup\$
    – wastl
    Jun 9, 2018 at 16:26
  • 1
    \$\begingroup\$ I fear it would get closed as a duplicate of this one \$\endgroup\$
    – JayCe
    Jun 9, 2018 at 23:08
  • \$\begingroup\$ Exact duplicate. \$\endgroup\$
    Jun 10, 2018 at 3:30
  • \$\begingroup\$ @wastl depends which country you are in (America or the rest of the world). \$\endgroup\$
    – Suda
    Jun 11, 2018 at 1:41
  • \$\begingroup\$ @JayCe i don't think so the, as that is the prime factorisation of the number, where i am asking for the factor count. But, as with user202729, it is an exact duplicate. So, Thanks guys :D \$\endgroup\$
    – Suda
    Jun 11, 2018 at 1:43
  • \$\begingroup\$ Thanks for using the Sandbox :) \$\endgroup\$
    – JayCe
    Jun 11, 2018 at 2:06

Block partite a string


Consider a list l, consisting of numbers. Define a block operation at index i on the list l to be the act of moving 3 consecutive elements starting from i in l to the end.


l, i (1-indexing) -> l (after applying block operation at index i)
[1,2,3,4,5], 1 -> [4,5,1,2,3]
[1,2,3,4,5,6,7], 3 -> [1,2,6,7,3,4,5]

Given a list consisting of only 0 and 1, your challenge is to partite it so that zeros are at the front, and ones are at the back, using only block operations. Output should be the indices in the order they are applied on the list.

Because this is impossible for the list [1,0,1,0], the list length is guaranteed to be at least 5.

Also (as a bonus, to avoid handling special cases) there is at least 5 ones and 5 zeroes.

Test cases (1-indexing)

(there are other valid outputs)

[1,1,1,0,0] -> [1]
[0,1,0,1,0] -> [1,2,1,1]
[0,0,0,1,1,1,0,0,0] -> [4]

Use this script to generate more test cases. (only input)

Winning criteria

This is , the shortest code in bytes wins.
Don't let code-golf languages discourage you from posting your solution. Try to come up with as short as possible solution for any language.


  • [atomic-code-golf] variant.
  • You're free to brute force, although I expect that a non-brute-force solution would be much shorter.
  • 1
    \$\begingroup\$ @HatWizard This is the code-golf variant, I'm sure that I didn't post it. The other one is atomic-code-golf. \$\endgroup\$
    Jun 10, 2018 at 13:16

Which number nearest?

We say 2018 is near 2000, but not 2018 is near 2030, though |2030-2018|<|2000-2018|. Given some pairs of numbers (a,b) and two numbers g>0 and x, find an x+t for min((|t|c+g)*bd) for t as a real number making (x+t) mod a = 0, (a,b) as one of the pairs. You can decide c to be 1 or 2, and d to be 1 or -1, as long as it's constant.

Samples: (c=1, d=1)

In: {(1000, 1), (10, 100)}, g=1, x=2018
Out: 2000

In: {(1000, 1), (10, 1)}, g=1, x=2018
Out: 2020

In: {(1, 1), (10, 1)}, g=1, x=2018
Out: 2018

  • 1
    \$\begingroup\$ I think this is an interesting challenge, but you really need some nicely formatted formulas here. The plain-text forms are hardly readable. \$\endgroup\$
    – Adám
    Jun 13, 2018 at 18:06
  • \$\begingroup\$ @Adám MathJax is currently not supported. \$\endgroup\$
    Jun 14, 2018 at 1:42
  • 1
    \$\begingroup\$ I'm confused. Why wouldn't we say 2018 is near 2030? It seems grammatically fine to me. \$\endgroup\$
    – Jo King Mod
    Jun 14, 2018 at 10:20
  • \$\begingroup\$ @JoKing 2030 is not that integer, and saying it near another strange number is quite meaningless \$\endgroup\$
    – l4m2
    Jun 14, 2018 at 10:23
  • \$\begingroup\$ Sorry? I think there's a language barrier here. I'm not sure what you mean. \$\endgroup\$
    – Jo King Mod
    Jun 14, 2018 at 10:27
  • \$\begingroup\$ I guess the intent is to find the nearest round number, with the (a,b) pairs deciding what a "round number" is. I agree that better formatting would help with readability, and more importantly some explanation text: what is c, what is d, what does g's value affect, and in general how did the min((|t|c+g)*bd) formula come about? \$\endgroup\$
    – Sundar R
    Jun 25, 2018 at 7:37

Is there a dangling else?

Define a statement as follows (Backus-Naur form) (based on Java syntax):

statement ::= ";"
  | "if(true)" <statement>
  | "if(true)" <statement> "else " <statement>

Example valid statements:

if(true);else ;
if(true);else if(true);else ;

Example invalid statement that is valid Java syntax, but considered invalid for simplicity:

if(1>0);else ;
System.out.println("This is invalid");

Your task is, given a valid statement, determine if it contains a dangling else (that is, it can be parsed into more than one ways)

Test cases

Truthy test cases (contains a dangling else)

Presented in the format {input}¶ -> {parse 1}¶ -> {parse 2}

if(true)if(true);else ;
 -> if(true){if(true);}else ;
 -> if(true){if(true);else ;}

if(true)if(true);else if(true);else ;
 -> if(true){if(true);else if(true);}else ;
 -> if(true){if(true);}else{if(true);else ;}

if(true);else if(true);else if(true)if(true);else ;
 -> if(true);else if(true);else if(true){if(true);}else ;
 -> if(true);else if(true);else if(true){if(true);else ;}

Falsy test cases (uniquely parsed)

if(true)if(true);else ;else ;
if(true);else if(true);else if(true);else ;

Quine of Hanoi


Make a program that print a rearranged version of itself


  • Your program will consist of newlines and 3 blocks : A, B and C where each block will have distinct and nonzero lengths, i.e. 0 < length(A) < length(B) < length(C).
  • The output will be based on the order of the code blocks and newlines, it will be a new arrangement that progresses toward a solved state by one move unless it is already solved, following Tower of Hanoi rules.

For example:


Will print


Additional rules

  • Your program don't have to handle invalid orders, e.g. CAB
  • You have to handle at least one configuration of each group (but not necessarily all of them).
  • The order of the lines is irrelevant.

For example


CAN print



#Group 0 - will output itself

#Group 1 - will output one of group 0

#Group 2 - will output one of group 1

#Group 3 - will output one of group 2


This is , so the one with the shortest code (A+B+C) wins

  • \$\begingroup\$ To me, this seems like a "challenge rules inferred from test cases" situation. Specifically, it seems that the desired behavior is "when the code is run, it outputs a new arrangement that progresses toward a solved state by one move unless it is already solved", but you just say "follow Tower of Hanoi rules". \$\endgroup\$ Jun 15, 2018 at 14:43
  • \$\begingroup\$ @KamilDrakari indeed, can I use your description in the challenge? \$\endgroup\$
    – Rod
    Jun 15, 2018 at 14:45
  • \$\begingroup\$ I don't mind, go ahead. \$\endgroup\$ Jun 15, 2018 at 14:47

Most times a loop

Given a positive integer n. For an array of length n, each two element of which are different, repeatedly rearrange it using the same permutation till it's the same as original. How many times was the array rearranged at most?


input output example permutation
1     1      [a1]
2     2      [a2 a1]
3     3      [a3 a1 a2]
4     4      [a4 a1 a2 a3]
5     6      [a3 a1 a2 a5 a4]
  • \$\begingroup\$ Must the permutation be outputted, or only the number of steps? \$\endgroup\$
    Jun 14, 2018 at 11:19
  • \$\begingroup\$ @user202729 only the one number \$\endgroup\$
    – l4m2
    Jun 14, 2018 at 11:25
  • 1
    \$\begingroup\$ In short: Given a number n, what is the largest order of an element in a symmetric group on n letters? \$\endgroup\$
    Jun 14, 2018 at 11:39
  • 1
    \$\begingroup\$ You might want to clarify that the input is the length of the array. Since the question starts "Given an array", I assumed the input was an array and was confused at first. (I think it needs more elaboration in general too.) \$\endgroup\$
    – Sundar R
    Jun 16, 2018 at 8:21
  • \$\begingroup\$ @sundar problem edited; what if given an array where some elements may be same? (maybe turns into another problem) \$\endgroup\$
    – l4m2
    Jun 16, 2018 at 10:57
  • \$\begingroup\$ oeis.org/A000793 \$\endgroup\$ Jun 19, 2018 at 9:06
  • \$\begingroup\$ can you show the steps of doing a permutation? for dumb dumbs like me? \$\endgroup\$
    – don bright
    Jul 7, 2018 at 2:32

Rotational symmetry in which bases from 2 to 36

A number (here, a non-negative integer) is rotationally symmetric if it "looks" the same after being rotated 180 degrees. For example, 69 (heh.) Here's a related challenge.

We're going to consider bases from 2 to 36, using the symbols 0-9A-Z as the digits. We're going to be generous with what digits are rotationally similar. Each of the following pairs will qualify (order not relevant):

00, 11, 22, 55, 69, 88, B8, D0, DD, E3, I1, L7, S5, SS, Z2, XX, ZZ

The challenge

Given a non-negative integer n in base 10, write a program or function that produces a list of bases from 2 to 36 in which the n is rotationally symmetric.

Input and output

Any reasonable input format is allowed (the integer itself, its character representation, an array of digits, an array of digits as characters.)

Any output format that communicates the desired result in an unambiguous way is acceptable. For example, a 35 element array of truthy/falsey values. If it's easier to include base 1 (always truthy) that's fine too.


This is . Fewest bytes in each language. Usual rules apply.

  • \$\begingroup\$ Why take input in base 10? I don't think it would make it too easy to take input in other bases ... \$\endgroup\$
    – wastl
    Jun 25, 2018 at 19:18
  • \$\begingroup\$ this is fun, but are there examples? im a bit slow on the uptake \$\endgroup\$
    – don bright
    Jul 7, 2018 at 2:13



Given an input, n, print a circle with the circumference of n characters.


  • The characters for the circumference of the circle can be any non-whitespace character
  • Shapes don't have to be an amazing circle, kinda roundish shapes are still valid
  • The circle can have a small gap, but no overlap


Input: 1

Input: 2

Input: 3

Input: 7
o   o

Input: 20
 o      o
o        o
o        o
 o      o    
  • 4
    \$\begingroup\$ Objective valid criteria please? \$\endgroup\$
    Jun 26, 2018 at 2:19
  • \$\begingroup\$ (BTW SE won't allow you to post a title with <15 chars. NBSP and some ZWSP can reduce it to 7, but no less.) \$\endgroup\$
    Jun 26, 2018 at 2:20
  • 1
    \$\begingroup\$ Also, most languages will suffer from the floating inaccuracy of \$\pi\$ or trigonometric functions (\$\sin\$ or \$\cos\$), so you should say "although theorically it must work for all input, in practice your program only need to work with \$n\le1000\$ (or some other bounds) \$\endgroup\$
    Jun 26, 2018 at 2:28
  • 1
    \$\begingroup\$ Thank you all for the feedback! The valid criteria is a very valid point, i'm working on making my own solution right now so I have something I can give to reproduce. I am aware of the title limit, I'm trying to come up with a better title before it is posted. And I will think about the inaccuracy of pi, because that could cause some headaches. Thank you again! :) \$\endgroup\$
    – GammaGames
    Jun 26, 2018 at 4:27

Shortest code to send an html s/mime signed message with one attachment over smtps

Simple challenge : use a valid RSA based security certificate in order to sign message according to s/mime rules and send it over smtp over TLS on port 465 (or starttls on port 25).

Rules :

  • The program parameters takes an ʜᴛᴍʟ string consisting of message body ; a message subject as string ; a sender address as string ; and list of recipients address.
    They can be obtained either as function/class parameters or program arguments or read from keyboard input.
  • The security certificate is read from an hardcoded file name of your choice or a hardcoded non empty string.
    It can be in the format of your choice.
  • The attachment is read is read from an hardcoded file name of your choice or 2 non empty hardcoded strings (1 for filepath and the other 1 for content)
  • The s/mime signing rules state that message body should be signed and other part shoudln’t be signed, this means in practice that data stating the message is in the html format and all data about attachments should be signed (subject priority, and e‑mail addresses aren’t signed).
  • When I say you have free choice, just pick up the solution using the fewest bytes.


The code which uses the fewest bytes.

  • \$\begingroup\$ I dont understand, what's the point in giving both the filepath and the content? Is the content enough? \$\endgroup\$
    Jun 27, 2018 at 5:04
  • \$\begingroup\$ @user202729 Inside e‑mail data, a valid attachment consists of a file path and it’s data. Otherwise, does the question looks Ok ? \$\endgroup\$ Jun 27, 2018 at 8:52
  • \$\begingroup\$ One problem with this type of "minimal code to do a task over a protocol" question is that it's not clear how much of the protocol must be implemented. E.g. should the client handle grey-listing? \$\endgroup\$ Jun 29, 2018 at 8:50

Earth mover's distance

Dupe check: Do we already have a challenge about the Earth mover's distance? Some possibilities could be to compute it for a 1D array, a 2D array, or a circle.

  • \$\begingroup\$ Not as such, but it's basically just linear programming so you'd want to avoid creating a dupe of codegolf.stackexchange.com/q/156287/194 . I don't recall any non-integer linear programming questions; the technique has been used in some KotH answers, but I think they encode the solution rather than the solver. \$\endgroup\$ Jun 29, 2018 at 8:45

Fewest instructions to copy bytes in memory in WebAssembly.

Implement the functionality for copying bytes in memory in WebAssembly.


  • Use WebAssembly, written in wast (the text format).
  • Any of the WebAssembly instructions are fine.
  • In calling copy, it doesn't need to worry about overriding an existing string.
  • Doesn't need to worry about the strings being too large to fit into memory, strings will be reasonable size and wont overflow over the end. For example, the total memory is 10000 bytes, so strings might be 100 bytes and only go to 5000 in the memory. (But those aren't actual hardcodable values).
  • No calling JavaScript functions.
  • The string "Hello World" starts of at position 0 in memory. Copy this string to random places in memory and log it, as shown in the xample below.

The winning answer is the one with the fewest WebAssembly instructions. That is, feel free to have a functions in WebAssembly, just no calling or importing JavaScript functions.


To get started, here is the start of the WebAssembly module:

// example.wast
  (memory (export "mem") 1)
  (data (i32.const 0) "Hello World")
  ;; instructions counting starts from here:
  (func (export "copy")
    (param i32) ;; existing start index
    (param i32) ;; size in bytes
    (param i32) ;; new index to copy to

And here is how to load it, as well as the tests:

// example.js
WebAssembly.instantiateStreaming(fetch('example.wasm'), {}).then(mod => {
  var exports = mod.instance.exports
  var i8 = new Uint8Array(exports.mem)
  var i = 200 + rand(500)
  exports.copy(0, 11, i)
  var i2 = 1000 + rand(500)
  exports.copy(i, 11, i2)
  console.log(i, getString(i, 11))
  console.log(i2, getString(i2, 11))

  function rand(size) {
    return Math.floor(Math.random() * (size + 1))

  function getString(index, size) {
    var string = ''
    for (var i = index; i < index + size; i++) {
      string += String.fromCharCode(i8[i])
    return string


Potentially useful resources:

  • \$\begingroup\$ It's been a few days, wondering if I could post this :) \$\endgroup\$
    – Lance
    Jul 10, 2018 at 3:02
  • 1
    \$\begingroup\$ Limiting this challenge to wast only will probably result in this question not going over well with the people on this stack exchange. \$\endgroup\$ Jul 10, 2018 at 21:46

Concatenate my strings!

As you know, we all like to save bytes around here. So, my strings are special: they come in four different flavours depending on the highest code point in the string:

  • ASC (code points up to 0x7F). Like ISO but all bytes have values less than 0x80.
  • ISO (code points up to 0xFF). Each byte represents a code point.
  • UTF (code points up to 0x7FF). Uses UTF-8 encoding.
  • UCS (code points up to 0xFFFF). Uses UCS-2 encoding.

For input you will receive two strings, each represented by a flavour identifier and a sequence of bytes representing the code points according to the flavour. You then need to output a byte sequence using the best flavour to hold the concatenation. Except where limited by standard loopholes, you don't need to use the designations ASC, ISO, UTF and UCS, so for instance if you choose to use numbers 0-3 for the flavours then the output flavour is simply the maximum of the two input flavours.


ISO 43 6F 64 65 A0 + ASC 47 6F 6C 66 = ISO 43 6F 64 65 A0 47 6F 6C 66 

This is , so the shortest program or function wins!

  • \$\begingroup\$ how do you define the best flavor for concatenation? im guessing 'shortest'... but it would help to say it. also maybe a few more examples? \$\endgroup\$
    – don bright
    Jul 7, 2018 at 2:22
  • \$\begingroup\$ @donbright "depending on the highest code point in the string" \$\endgroup\$
    Jul 7, 2018 at 4:49
  • \$\begingroup\$ @donbright You can do it depending on the highest code point, but you can just assume the highest code point of the input strings given their flavour if it's easier. \$\endgroup\$
    – Neil
    Jul 7, 2018 at 10:04
  • \$\begingroup\$ oh i get it now. thanks. i like this. \$\endgroup\$
    – don bright
    Jul 7, 2018 at 14:13
  • \$\begingroup\$ Well, I still don't get it - (1) why do you say "code points up to 0x7FF" for UTF-8? UTF-8 can encode codepoints up to 10FFFF. Do you mean some byte-limited variant of UTF-8? (2) except for UTF-8, it seems the task is just to choose the higher encoding ("maximum of the two input flavours" as you say), and possibly add 00 prefix bytes if output flavour is UCS-2. Is UTF-8 intended to be the main part of the challenge? Or am I missing something? (More examples and test cases would probably help by the way.) \$\endgroup\$
    – Sundar R
    Jul 8, 2018 at 19:43
  • \$\begingroup\$ @sundar Because U+0800 takes 3 bytes in UTF-8 but only 2 in UCS-2, I'm pretending that I'm choosing the golfiest encoding for the bytes... I didn't want the challenge to get bogged down in the detail of choosing which encoding was best for a given string. Also, 00 suffix bytes only helps for some of the conversions. \$\endgroup\$
    – Neil
    Jul 8, 2018 at 20:59

Count binomial coefficient entries

This task is very simple. For integer \$n \ge 0 \$, given the binomial coefficients of all the expansions of \$ (x+y)^m \$ for \$ 0 \le m \le n \$, count the number of occurrences of \$ n \$. This is OEIS A003016.

This is , so the shortest program or function that breaks no standard loopholes wins!


Smallest Match-3 Game

I was reading about Match Three games, games about manipulating a field of symbols to generate lines of three or more matching symbols, and was thinking a playable game would be a pretty short program, if golfed.

The reason I think that is because it has less rules than Chess, so I thought that when golfed it'd be a simpler program shorter than the Smallest chess program, which uses 487 bytes of Assembly, or less than 2 MB in any language used to answer that question.

Here's the other questions on this site, relating to Match-3 games:


How small can a Match-3 Game Program be?


  • The symbols used can be any ones you want, just have at least 3 different symbols.

  • At least a 4x4 board. Board size can be customized, if that's somehow easier.

  • Board must start with a valid configuration, can stall player interaction and visibly reform the board, but player action must only be start to be allowed on a valid board.

  • Any method of moving symbols is allowed. It could be sliding rows around, instead of swapping the positions of pieces, either side by side or anywhere on the board, or some other innovative way of moving pieces. But the board starts filled, and you move the symbols already there.

  • Any method of selection of what to move is allowed.

  • When a match happens, it's removed, and new pieces arrive, somehow. They don't have to fall from the top.

  • It'd be nice if it could detect when there's no more valid moves.

  • Random progression instead of deterministic would be nice as well.

Sandbox Questions

Not sure how much variability in the end result I should have. I want to have maximum customization.

I suppose I could have the score for each entry be something like:

Bytes of code - average number of bytes used to implement each optional feature.

  • \$\begingroup\$ what is match-3? \$\endgroup\$
    – don bright
    Jul 7, 2018 at 2:45
  • \$\begingroup\$ Yeah, it would be good to have a short description of the game, to keep the question self-contained and make sure we're all on the same page. Also might be good to mention at the start that you're looking to golf a playable, interactive version of the game, and not a solver or anything like that (which is what I initially assumed). \$\endgroup\$
    – Sundar R
    Jul 8, 2018 at 19:23

An example text for scrambled-words experiment. Version 1


This challenge is based on an old experiment that proves that we only need first two and last two letters in order to uniquely identify a word. The remaining middle-characters can be completely scrambled and yet we should not have any problems in reading the whole word. And the speed of reading even longest scrambled-words based text shouldn't be significantly longer than reading an "normal" text.

The challenge itself is to write a shortest possible code (any language) that can be used to generate test texts to prove above described idea.

The experiment in the background of this challenge was conducted many years ago by some English or American scientist. I can't credit particular source or recall any other details. The challenge itself is created by me.


Write the shortest possible code to generate test text (any length) based on following algorithm:

  1. For each word in input text.
    • If word is 5 characters long or less -- keep it unchanged.
    • If word is 6 characters long or longer -- keep first two and last two characters unchanged and scramble remaining ones.
  2. Print generated resulting text with scrambled words.

There there no corner cases except for two assumptions:

  1. Words with 5 characters and less should be kept untouched.
  2. Your code must support all UTF-8 characters, not just English / non-Latin alphabet.

I assume "standard" approach here, so the winner of the challenge will be determined by the length of the code.

Example Input and Output


  • This challenge is based on an old experiment.
  • Print generated resulting text with scrambled words.


  • This chllenage is based on an old exripmeent.
  • Print gertaneed reitlusng text with scbrmaled words.

An example text for scrambled-words experiment. Version 2


The extended version of this challenge adds only one new assumption to base / above algorithm:

  1. For each word in input text.
    • If word is 4 characters long or less -- keep it unchanged.
    • If word is 5 characters long -- keep first and last character unchanged and scramble remaining three.
    • If word is 6 characters long or longer -- keep first two and last two characters unchanged and scramble remaining ones.
  2. Print generated resulting text with scrambled words.

And again:

  1. Words with 5 characters 4 characters and less should be kept untouched.
  2. Your code must support all UTF-8 characters, not just English / non-Latin alphabet.

Example Input and Output


  • This challenge is based on an old experiment.
  • Print generated resulting text with scrambled words.


  • This chllenage is baesd on an old exripmeent.
  • Pirnt gertaneed reitlusng text with scbrmaled wrods.
  • 1
    \$\begingroup\$ See codegolf.stackexchange.com/q/9261/194 and the "Related questions" in its sidebar. This isn't identical, but I don't think it adds anything interesting. \$\endgroup\$ Jul 12, 2018 at 16:41
  • 1
    \$\begingroup\$ I agree with @PeterTaylor; I don't think the differing lengths of what and when to scramble make this sufficiently different from the challenge he linked. Personally, I would dupe hammer this. Don't let that discourage you though; this was a well-written challenge for a newcomer and it's great to see a newcomer making use of the Sandbox. Welcome to PPCG! :) \$\endgroup\$
    – Shaggy
    Jul 13, 2018 at 22:43
  • \$\begingroup\$ I totally agree with both of you that moving this challenge out of Sandbox would produce us a perfect dupe! :> So, obviously, I am not going to do this. I have only one supporting question here. Do we have any tools / ways here at Code Golf to encourage particular language? Among all answers to question you pointed out there are no trace of solution in Javascript or any other way I could run this in a browser. Do I have any option to encourage such solution, if I need it (i.e. some bounty etc.)? \$\endgroup\$
    – trejder
    Jul 16, 2018 at 11:58
  • \$\begingroup\$ @trejder Yes, you can put a bounty on the list of bounties with no deadline. That means you offer a multiple of 50 (up to 500) of your own reputation. \$\endgroup\$
    – wastl
    Aug 1, 2018 at 14:08
  • \$\begingroup\$ @wastl Thanks for the suggestion, but I decided to go with a "regular" bounty instead. \$\endgroup\$
    – trejder
    Aug 5, 2018 at 7:49

Maximal number of programming languages in 1KiB

In this code-challenge your task is to write a program/function with a maximum of 1024 bytes, the goal is to interpret/compile as many programming languages as possible.


You're free to use any combination of inputs and outputs as you wish.


Inputs will be the name1 of the programming language and the source code.

The inputs can be

  • read from a file (you may hardcode a filename if it helps)
  • read from stdin
  • taken as command-line arguments
  • taken as function arguments
  • a combination of the above

1: you may choose to encode them, as long as the encoding is bijective - for example numbering the languages 1 through n.


The output can be

  • the resulting side-effects of interpreting the program in the specified language
  • valid machine code that produces the above

What is a programming language?

For the purpose of this challenge a programming language needs to be

  • Turing-complete
  • publicly listed, as in having one of the following:
  • released before 13. July 2018
  • able to do I/O

What does my interpreter/compiler need to implement?

For each of the chosen programming languages, your program does not need to implement the full language. It suffices to implement a working subset of it as long as it stays Turing-complete.


The answer that implements the greatest number of different programming languages wins.


Tags: , ,

  • Should I leave the source size restriction and use a different scoring, eg. \$\frac{\#bytes}{\#langs ^ n}\$ for some \$n \ge 1\$?
  • Should I disallow using polyglotting (maybe eval could be used several times that way which would be boring)?
  • How should I properly define different programming languages (should I count different versions as 1 each)?
  • Additional places for entries, descriptions of programming languages?
  • Missing tags or other suggestions?
  • \$\begingroup\$ Given that Perl can do BF in 120 bytes, I would think a bunch of BF derivatives like Ook could be tacked on for very little overhead, which would seem to break your scoring system. I'm not sure how to rule that out, though. \$\endgroup\$ Jul 13, 2018 at 16:20
  • \$\begingroup\$ @AdmBorkBork: It kind of depends on what derivatives, I guess. You're right, I need to figure out a good way to rule out counting derivatives which just extend BF, otherwise it would be boring.. An idea would be: For each language you must give a program achieving some trivial task X and it isn't allowed to work in any other language. \$\endgroup\$ Jul 13, 2018 at 17:01
  • \$\begingroup\$ @FryAmTheEggman: You're free to determine language by looking at the source, however you're given the name as input: "Inputs will be the name of the programming language and the source code." Just looked in meta and found this, so I will remove the notice that you can ignore that input (I didn't know that before and didn't want to prevent people from determining the language themselves). \$\endgroup\$ Jul 13, 2018 at 20:18
  • \$\begingroup\$ Sorry, I missed that! Maybe it would be better to put that at the start of the input section? Something like: "Your interpreter will be given the source and language names as inputs inn one of the following ways: ..." perhaps? \$\endgroup\$ Jul 13, 2018 at 20:21
  • \$\begingroup\$ @FryAmTheEggman Thanks for the feedback! I put it to the beginning of that section and removed the notice about encoding further information (it's a standard loophole anyways and doesn't make things clearer). \$\endgroup\$ Jul 13, 2018 at 20:29

Irrational Array indexing Starts at 3.

I came across the following brilliant comment, which suggests that subsequent sets of digit from pi should be used to Index an array, from a user named on the r/programmer humor subreddit context for the curious.

To fix the duplicate problem, instead take an extra digit whenever you are about
to duplicate a key: arr[3], arr[1], arr[4], arr[15], 
arr[9], arr[2], arr[6], arr[5], arr[35] and so on.

Exercise for the reader: write a program that outputs the nth index of this array, and describe for yourself the limitations of the program (what is the maximum value of n? what is the minimum?)

Your task (should you choose to accept it), is to implement a function (or rather pair of functions/ (pair of full programs/ one of each)) that converts to and from this cutting-edge choice.

You may either write a single function that receives two inputs one being an integer input, and two being which way to go, or you can write a pair of functions and your score will be the sum of their sizes.

Put another way, implement both f(x) and \$ f^{-1}(x) \$ according to this table. You may also instead implement f(x-1), and \$ f^{-1}(x) \$ + 1 (1 indexed arrays), but you will get some stern looks.

x f(x)
0 3
1 1
2 4
3 15
4 9
5 2
6 6
7 5
8 35
19 950
21 841
41 6280

This problem is essentially identical to OEIS A064809, although the table there is one indexed.

This is code-golf, so shortest code in bytes wins. As always, you may use any programming language, but standard loopholes are prohibitted. What is allowed though, is that at no penalty you may optionally take in a second or third input with the first 10,000 digits of pi. Your code must work with 0<=x<=1000. Even if you choose to receive pi as input, I'll personally encourage you to write one that doesn't require pi as input, It'll obviously be unscored, but you'll earn some imaginary internet points.

  • \$\begingroup\$ Note that we have mathjax now so you could write \$ f^{-1}(x) \$ etc. You may also want to include the first 3-digit number in the examples. I also expect that every answer will choose to take the optional input, except for those that already have access to the digits of pi. \$\endgroup\$ Jul 18, 2018 at 20:41
  • \$\begingroup\$ I suspect it too. I figured having to dynamically compute all of the digits of pi was a bit beyond the scope of challenge, but I really wanted to see answers that don't. \$\endgroup\$ Jul 18, 2018 at 21:36
  • 1
    \$\begingroup\$ I think they might be different enough to be posted as two different challenges, but its a bit borderline so I'd definitely either ask chat or meta if you wanted to do that. Otherwise, there's not a particularly good reason not to require calculating digits of pi in this way, I think? So if that's the question you'd rather ask then go ahead. The only significant difference will probably be receiving fewer answers, and the only real drawback could be that people say its a dupe of finding pi to an arbitrary number of digits, perhaps. \$\endgroup\$ Jul 19, 2018 at 5:41
  • 1
    \$\begingroup\$ This is OEIS entry A064809. I actually had an idea for a similar challenge recently of splitting a given string into substrings in such a way as to avoid duplicate substrings. \$\endgroup\$
    – Shaggy
    Jul 19, 2018 at 8:27
  • \$\begingroup\$ "but standard loopholes are permitted" <- prohibited perhaps? "If you choose to not take in this input, your code must work with 0<=x<=1000" <- does this mean there's a different limit for those who do take that input? (It looks like with 10000 digits you'd be able to handle upto x = 2675.) \$\endgroup\$
    – Sundar R
    Jul 19, 2018 at 11:57
  • \$\begingroup\$ Definitely post 2 different challenges. \$\endgroup\$
    Jul 19, 2018 at 14:25
  • \$\begingroup\$ should I link them? \$\endgroup\$ Jul 19, 2018 at 16:05
  • \$\begingroup\$ @sundar I'll make that limit apply to both. I'll still give you 10k digits of pi though, out of "kindness". \$\endgroup\$ Jul 19, 2018 at 16:07

The Shifty Maze

You are a wild mouse and you have stumbled on a maze that some human has constructed to observe your behavior. The maze is littered with blobs of peanut butter and has a cache of sunflower seeds near its center. After discovering the seeds, you decide that you want to take them all home to your personal cache. You must find your way to the seeds and exit the maze. Since there are so many seeds, it takes you many trips to get them all.

Things go well your first time. You find your way to the seeds, bring a few back, and return to the maze. To your surprise, when you return the second time, the maze looks nothing like it did before, but you quickly figure out that the entrance was simply in a different place and continue navigating as usual. The next time you return to the maze, you are once again lost, but you find a familiar pattern of peanut butter dabs and find your way to the sunflower seeds once again. Naturally, you catch onto this pattern and eventually retrieve all the sunflower seeds.

The Challenge

Your task is to make a "mouse" bot that navigates through a maze where the entrance moves to somewhere else on the edge of the maze every time you exit and enter it. You have no limits on memory, but no absolute sense of direction and a limited visual field. You can only exit the maze after finding the cache. Your goal is to get all of the seeds in as few steps as possible.


A perfect maze is randomly generated using a randomized version of Prim's Algorithm starting from a cell near the center. The seed cache will be close to the center. 10% of the cells will be dabbed with 3-5 units of peanut butter. There will not be any peanut butter on the same cell as the seed cache. The maze used for scoring will be 30x30 cells.


Each turn, you can move forward or turn 90 degrees in either direction. If there is any peanut butter on your current cell, you may also eat one unit of it instead of moving or turning. (Partially eaten peanut butter can be used to create landmarks for navigation.)


You can see every cell in a straight line in front of you until a wall obstructs your view. You can also see one cell to your left and right, provided there is no wall between that cell and your current cell.

For each cell that you can see, you can see whether there is a wall on each of the four edges of the cell, how much peanut butter is on that cell, and whether it is the seed cache or the exit.


Suppose you had this maze:

|     |  5    | |   |
| ----+-- +---+ | --+
|4    |   |@   3    |
| --+-+ --+---- | --+
|   | |    4   <|   |
| --+ | --+ | | +-+ |
|         | | |   | |
| | +-- --+-+ +-- +-+
| | |    3  | |     |
+-+-+-------+-+ ----+

@ is the seed cache. Numbers are blobs of peanut butter. < is the mouse (facing west)

The vision for the mouse would look something like this:


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

No memory limit

You can remember as little or as much as you would like. The challenge is in figuring out where you are as quickly as possible and reduce the amount of time you spend wandering.

Test Driver

The test driver can be found here.


Your solution should be compatible with Python 3.7. You should implement a class with the following methods:

  • A constructor taking no arguments
  • get_action, which is called with one argument representing your vision on each step of navigation (more on that below). This should return a string representing the action to take: forward, left, right, or eat are valid values. If this returns an action that cannot be taken, an exception will be thrown and your solution will be considered invalid.
  • enter_maze, which is called without arguments each time the maze is entered. No return value is expected and the function doesn't actually have to do anything. The next time get_action is called, you are guaranteed to be on the cell on the edge of the maze facing away from the entrance/exit.

The Vision Object

You will receive an object with the following attributes:

  • left and right: the cells to your left and right. If there is a wall that obstructs your view, this will be '???' instead of the cell view object.
  • forward: a list of all the cells in your forward vision, starting with your current cell and continuing until the last cell in your vision.

Any of these cell views may also be None, indicating the entrance/exit of the maze.

Each visible cell inside the maze will be an object with the following attributes:

  • forward, left, right, back: booleans indicating whether there is a wall in the given directions, oriented the same way as the mouse.
  • contents: an integer representing the amount of peanut butter (if any), None (if nothing is on the cell), or 'cache' if the cell contains the seed cache.

Scoring and Rules

  • Standard loopholes apply.
    • If your bot only works on the scoring maze, it is an invalid solution. Your bot does not receive enough input to distinguish the scoring maze from another maze, so hard-coding a route will produce an invalid solution.
  • Run the test driver to score your result. It uses an isolated and seeded random number generator to ensure that all entries get the same maze and sequence of entrances. The total number of turns it took to retrieve all of the seeds (this takes 100 iterations through the maze) is your score.
  • Include your score, your code, and an explanation in your solution post.
  • You must output a valid move each turn. Moving into a wall or attempting to eat nonexistent peanut butter will result in an error that you have no opportunity to recover from.
  • You may not exit the maze until you have visited the cell containing the seed cache since the last time you entered the maze.
  • \$\begingroup\$ Is it guaranteed that when enter_maze is called, the mouse is on an edge of the maze? \$\endgroup\$
    Jul 20, 2018 at 6:54
  • \$\begingroup\$ @user202729 I should clarify that. Thanks for pointing that out. \$\endgroup\$
    – Beefster
    Jul 20, 2018 at 16:47

Encoding nested tuples

Tags: , , ,

Related: this

Working on my recent esolang μ6 I found myself a neat puzzle: Given the set of all natual numbers and the set of all nested tuples over the natural numbers, find a bijection between those two sets.

A nested tuple \$t \in T\$ is recursively defined, it is one of the two:

  • an natural (\$\ n \in \mathbb{N}_0\ \$) number itself: \$\;t = n\$
  • a tuple of two nested tuples (\$\ t_l,t_r \in T\ \$): \$\;t = (t_l,t_r)\$

If it helps you can think of a nested tuple as a binary tree that has only values in its leaves.


Your task is to define two programs/functions, let's call them \$\ E\ \$ (encode) and \$\ D\ \$ (decode) which are each others inverses:

Given any natural number \$n \in \mathbb{N}_0\$ the output \$E(n)\$ is a unique element of \$\ T\$ and \$\ D(E(n)) = n\$.

Given any nested tuple \$\ t \in T\$ the output \$\ D(t)\$ is a unique element of \$\ \mathbb{N}_0\$ and \$\ E(D(t)) = t\$.


Inputs to the two programs/functions can be

  • an integer or a string representation thereof for \$\ E\$
  • a nested tuple/list, custom data-type1 for \$\ D\$

Outputs can either be of the same type as the input of the inverse function/program or printed to stdout.


Since you're free to implement any bijection, it's difficult to give meaningful test cases. These are just a few examples using this encoding-function and this decoding-function:

0 <-> 0
1 <-> (0,0)
3 <-> ((0,0),0)
20415 <-> ((1,0),(1,2))
55340232221111877631 <-> ((0,(1,0)),(2,1))
1000000000000000000000000 <-> 500000000000000000000000

1: For example if your language doesn't support nested tuples/lists, you don't need to count its definition towards your byte count. As an example a Haskell submission could assume data T = El Integer | Nest T T.


  • Anything unclear?
  • Is this maybe too much to ask in a code-golf?
  • I could "simplify" it by asking for two \$\ E_k \$ and \$\ D_k \$ which would for all inputs \$ k \$ map \$\ \mathbb{N_0} \leftrightarrow \mathbb{N_0}^k\ \$..

Most Turing-incomplete Instruction Set

Tags: ,

This challenge expects you to define an instruction set \$I = \{ \texttt{instr}_1 \dots \texttt{instr}_n \}\$ which is provably Turing complete. The catch is that any subset \$I'\$ that is proper (ie. \$I' \neq I\$) must not be Turing complete.


Your task is to define some environment (eg. a stack, an unbounded tape, tuples, integers, funcions etc.) over which you have complete freedom to choose, let us call this environment \$E\$.

To initialize \$E\$ you will define a way of transforming the source code \$s\$ and inputs \$in_0,\dots,in_r\$ to some \$E_{initial}\$. The same holds for the output of your programming language, you can define the output as any mapping of the end state \$E_{end}\$ to your output set.

The main task is to find an as large as possible number of instructions which define a Turing complete programming language, but removing any instruction from that set must result in a programming language that is not Turing complete.

An instruction \$\texttt{instr}_i\$ takes some non-negative number \$m\$ of arguments and modifies the environment, ie.

$$ \texttt{instr}_i : A_0 \times \cdots \times A_m \times E \to E $$

where \$A_0,\dots,A_m\$ are the sets of valid arguments, you're free to define these as you wish (eg. natural numbers, integers, Booleans, labels etc.).


Your submission will contain

  • the language specification
  • informal proof of validity
  • an implementation of the language.


  • this is a and your score will be the number of instructions, the goal is to maximize this number (ties will be broken by favouring the earliest submission)
  • your programming language only needs to support input by using some special initial environment \$E_{initial}\$
  • the same holds for the output(s), these only need to be encoded in the final \$E_{end}\$
  • the definitions of \$E\$ and the way of transforming input/output do not need to be formal (eg. it suffices to just say something along the lines of: "My language works with a stack of integers, initially it will contain all the inputs beginning with the first one at the bottom of the stack. Output will be the top of the stack or zero if it's empty.")
  • you will need to provide an informal proof of why your submission is valid, consisting of
    • an informal proof of Turing completeness of the instruction set \$I\$
    • an informal proof of why any proper subset of \$I\$ is not Turing complete
  • these proofs may rely on reductions to known Turing complete languages (eg. Turing machines, BitBitJump, brainfuck etc.)


As pointed out by Nathaniel, it is currently possible to get an arbitrary large score.. If anyone has a nice fix that will prevent that (and similar exploits), please leave a comment.

  • 2
    \$\begingroup\$ I like the idea, but the instruction set can easily be made arbitrarily large. E.g. environment starts in state 0. Instruction A1 changes the state to state 1 if it's in state 0, otherwise it's an error. Instruction A2 changes the state to state 2 if it's in state 1, otherwise it's an error. [...] Instruction A1000000 changes the state to state 1000000 if it's in state 999999, otherwise it's an error. Instructions S, K perform as per SK calculus, but only if the environment is in state 1000000. This scores 1000002. \$\endgroup\$
    – N. Virgo
    Aug 7, 2018 at 12:46
  • \$\begingroup\$ @Nathaniel: I didn't think of that :( Finding a nice definition/rule to prevent these kinds of exploits will be quite difficult. I'll see what can be done. \$\endgroup\$ Aug 7, 2018 at 12:51
  • \$\begingroup\$ For N*'s attack, a function can take binary input and decide one state per input \$\endgroup\$
    – l4m2
    Aug 10, 2018 at 15:54
  • \$\begingroup\$ @l4m2: I thought about that too, it's better than what I have now. But it would still allow an "attack" where you abuse the stack/tape/.., for example: Take a setup with a stack, A1 pushes 1, A2 pushes 2 if ToS=1 else pushes 0, .. A<really-large-number> acts as a Turing-complete instruction when ToS = <really-large-number>-1 and else it acts as clear stack. \$\endgroup\$ Aug 10, 2018 at 16:08
  • \$\begingroup\$ Oh and there might be some confusion about state and environment which are not distinguished in that definition. Only allowing moving to one state/environment would prevent a regular add instruction, since the resulting state would be different for a lot of operands. \$\endgroup\$ Aug 10, 2018 at 16:22
  • \$\begingroup\$ @OMᗺ It's still covered \$\endgroup\$
    – l4m2
    Aug 10, 2018 at 16:30
  • \$\begingroup\$ @l4m2: But that would mean that there needs to bean infinite amount of states, each configuration of state and tape/stack/.. would be state. Leaving us with the problem that there can't be an instruction put X where X is placed on the tape/stack because it would be different for different Xs. Or am I missing something? \$\endgroup\$ Aug 10, 2018 at 16:42

Define the structure X as a non-empty array of (smaller) X objects and "1". Split an X object into the smallest amount of continuous parts Y, length of each of Y don't exceed n, so that each X is either part of a Y, or exactly some Ys. It's fine if output only express which part has how many 1's.


[1,[1,1,1]],3 => 1;111
[1,[1,1,1]],2 => 1;11;1 or 1;1;11
[[1,1,1],[1,1,1]],1 => 1;1;1;1;1;1
[[1,1,1],[1,1,1]],2 => 11;1;11;1 or etc.
[[1,1,1],[1,1,1]],3 => 111;111
[[1,1,1],[1,1,1]],4 => 111;111
[[1,1,1],[1,1,1]],5 => 111;111
[[1,1,1],[1,1,1]],6 => 111111
  • \$\begingroup\$ What is a "non-self-contain array"? \$\endgroup\$
    Aug 7, 2018 at 15:17
  • \$\begingroup\$ @user202729 Some languages allow array like A=[A], which is here not allowed \$\endgroup\$
    – l4m2
    Aug 7, 2018 at 15:18
  • \$\begingroup\$ I think you should work on the explanation, it's not very clear without looking at the testcases. Also what about languages that don't allow lists/arrays with different types? Would it be ok to define an appropriate type? Or should input be taken as string? \$\endgroup\$ Aug 7, 2018 at 18:04

Game of Circles

This is a hidden-identity game with Detectives and Robbers. You will write either a Detective bot or a Robber bot. All Robbers know the identity of all other Robbers. Each turn, a bot must either:

  1. Draw a private circle:
    • The actual circle drawn is public information
    • Detectives receive the number of Robbers in the circle privately
  2. Draw a public circle
    • The player that draws the circle declares the number of robbers in the circle (may or may not be true)

Finally, the player with the most circles (public or private) around them dies. In the case of a tie, no player dies.

The game ends when a single side has been eliminated or when no players have died for 3 turns.

Each game consists of 17 Detective and 3 Robbers. (META: These numbers I'm not sure about).

The bots that will participate in each game will be chosen using two genetic algorithms. There will be 100 simultaneous games, and the first genetic algorithm will choose the 1700 players for the Detectives, while the second genetic algorithm will choose the 300 Robbers. The fitness function for each bot will be how long they survived in the game (by percentage).

After 1000 rounds, players are ranked by their population (two scoreboards, one for Detectives, one for Robbers)

  • \$\begingroup\$ Sounds kinda like the Werewolf/Mafia game. Makes me wonder how well The Resistance boardgame will translate to a KotH. \$\endgroup\$
    – Sundar R
    Aug 12, 2018 at 11:20
  • \$\begingroup\$ I don't understand the bit about genetic algorithms though - will the bots that we submit just be the base population for the GA then? Or will there be no mutation or crossover in the GA (in which case it's pretty much not a GA)? That bit needs some more elaboration and possibly some tweaking. \$\endgroup\$
    – Sundar R
    Aug 12, 2018 at 11:21
  • \$\begingroup\$ Yep, this is similar to Werewolf/Mafia. I considered starting out with that, but I thought it might cause some confusion as there is no "nighttime", and robbers have no extra powers outside of knowing all of the other robbers. \$\endgroup\$ Aug 12, 2018 at 13:41
  • \$\begingroup\$ The bots will be the base population. Breeding will be asexual (single parent), and mutations means randomly picking a bot. You are right, this isn't a string GA, but it's the best term I could come up with. \$\endgroup\$ Aug 12, 2018 at 13:43

4B/5B Encoding

Tags: , , ,

To transmit data in binary there's a technique called NRZI where a transition from +V to -V or vice-versa encodes a 1 and the absence of such a transition a 0.

In case there are a lot of 1 s this is a good method because there will be a lot of transmissions and the risk of getting out of sync is smaller, however it's still tricky for long runs of 0. One solution is 4B/5B encoding which takes 4bits and encodes it in 5bits in a way such that there are at most 3 consecutive bits. The encoding is as follows:

0000 -> 11110
0001 -> 01001
0010 -> 10100
0011 -> 10101
0100 -> 01010
0101 -> 01011
0110 -> 01110
0111 -> 01111
1000 -> 10010
1001 -> 10011
1010 -> 10110
1011 -> 10111
1100 -> 11010
1101 -> 11011
1110 -> 11100
1111 -> 11101


Given an bytestring, you will need to encode it with the aforementioned encoding.


  • Input will be a bytestring
    • to avoid padding-issues, it will always have a length that is a multiple of 4 bytes
  • Output will be of the same a bytestring
  • You may not assume that input (nor output) is printable


Note: You need to handle both printable and unprintable examples!

ASCII examples

SSePCcGG -> ]WW-~U]U=O
aHAHaHAHaHAHaHAHaHaO -> rU%%RrU%%RrU%%RrU%%RrU'%]
S#KPOCFWcSaOCR!@sz!\q9OKqY!L -> ]iU]~WUU9ouWW%]UWJ%^}_j%zzk5uWzW:%Z

Unprintables in hexadecimal

c0 ff ee 00 -> d7 bb de 73 de
66 6f 6f 00 -> 73 9d d7 77 de
50 50 43 47 -> 5f 97 e5 55 4f
48 65 6c 6c 6f 2c 20 57 6f 72 6c 64 21 00 00 00 -> 54 9c b7 69 da 77 69 aa 79 6f 77 5f 47 69 ca a2 7d ef 7b de

Drat! This was actually run three years ago! See Implement INTERCAL's Binary Operators

Mingle and Select

The programming language INTERCAL has two operators, "mingle" or "interleave" (represented by $), and "select" (represented by ~).

Mingle takes two 16-bit values and produces a 32-bit value by taking single bits alternately from its left and right operands, and concatenating them together - for example, 65535 $ 0 will yield -1431655766 as follows: 65535 is 0xFFFF, or 0b1111111111111111; 0 is 0b0000000000000000. Taking the bits alternately gives 0b10101010101010101010101010101010, or 0xAAAAAAAA, which evaluates to the signed integer -1431655766.

A simplified implementation of Select takes two 32-bit operands, and produces a 32-bit value by comparing the bits in the two operands, and wherever the right operand has a 1 bit, take the corresponding bit from the left operand. The resulting bits are compressed to the right, and zero-filled on the left - for example, an 8-bit version of select, given 79 ~ 42, would return 3, as follows: 79 is 0b01001111, and 42 is 0b00101010. Numbering the bits from the left starting with 1, we need to take the third, fifth, and seventh bits of 79, which are 0, 1, and 1, respectively. We then compress them to the right - 011 - and zero-fill, yielding 0b00000011, or 3.

The challenge

Without using INTERCAL, and without using in any other language any operator builtin that amounts to either mingle or select, implement both operators. You may implement them for 16- or 32-bit integers, and as either operators or functions, but input and output must be UNsigned decimal integers. (I'm not going to require input or output in INTERCAL-style insanity!)

Further constraint: The minimum bit width of the operands must be 16 bits for mingle (no constraint for select), and if they are unequal in width, the shorter is zero-filled on the left to match the width of the longer (zero fill applies to both mingle and select).

test cases to be written and inserted here

This is , so shortest solution in each language 'wins'. (Naturally, the standard loopholes are forbidden.)

  • \$\begingroup\$ "You may implement them for 16- or 32-bit integers, and as either operators or functions, but input and output must be signed decimal integers." This puts languages such as CJam which only have unbounded integer types at a disadvantage. Is that intended? \$\endgroup\$ Aug 13, 2018 at 11:03
  • \$\begingroup\$ @PeterTaylor - The intent here is not to exclude or disadvantage any particular language (other than INTERCAL), but to 'force' zero-fill on select, and return negative values for some cases of mingle. Would it be better to say that values returned must be some power of 2 times 16-bits wide? \$\endgroup\$ Aug 13, 2018 at 11:32
  • \$\begingroup\$ I'm not sure why an integer width is necessary for select: just say that it's zero-filled and make sure that the corner case of a ~ -1 (the only way that there's nothing to fill) is covered by test cases for a positive, zero, and negative. \$\endgroup\$ Aug 13, 2018 at 11:49
  • \$\begingroup\$ For mingle, it seems to me that if the operands are really 16-bit values then the example should be -1 $ 0, and if you require the output to be negative iff the first operand is negative then it easily generalises to unbounded integer types. However, the result of -1 $ 0 in an unbounded type is unbounded, so there is a genuine problem there. I suggest mentioning that briefly as a rationale for why languages without bounded integer types must nevertheless implement a bounded mingle. \$\endgroup\$ Aug 13, 2018 at 11:52
  • \$\begingroup\$ @PeterTaylor - but zero-filled to what width? One could argue that if an arbwidth is allowed, then no zeros need to be added, and 79 ~ 10 could validly be argued to be -1. \$\endgroup\$ Aug 13, 2018 at 11:52
  • \$\begingroup\$ To infinite width. The most significant bit is effectively a sign bit. \$\endgroup\$ Aug 13, 2018 at 11:57
  • \$\begingroup\$ @PeterTaylor - Good catch on 65535 vs -1. I think that this and the arbwidth problem can be addressed by simply changing the 'signed' constraint to 'unsigned'. \$\endgroup\$ Aug 13, 2018 at 12:06
  • \$\begingroup\$ But how do I tell the (selected) MSB from presumed zero-filling? Is 79~10 equal to 3, or to -1? \$\endgroup\$ Aug 13, 2018 at 12:07
  • \$\begingroup\$ UPDATE: Constraints changed. \$\endgroup\$ Aug 13, 2018 at 12:19
  • \$\begingroup\$ "But how do I tell the (selected) MSB from presumed zero-filling?" The answer would have been that you can only get a negative result if both operands are negative, but now that you've changed to unsigned this is no longer an issue. \$\endgroup\$ Aug 13, 2018 at 13:44
  • \$\begingroup\$ @PeterTaylor - It's been rendered academic; the challenge has already been run - see codegolf.stackexchange.com/questions/54412/… \$\endgroup\$ Aug 13, 2018 at 18:30

Lucas and Fibonacci are in pair



Write a program of at most 150 bytes length that produces different outputs (to stdout) if you insert token-delimiters into the source code.


The program with the highest number of different outputs wins.


For this challenge, we assume that the source code is tokenized prior to compilation/ interpretation. A delimiter is any character which, when inserted at a given position, changes the way the source code is tokenized, but is not part of a token on its own.



a = "0"
b = "0"

This prints 12. If you insert two spaces, you get:

a = "0"
b = "0"
print(a in b)

which prints "True"

This gives a total score of 2 for 2 (known) different outputs

Rule clarifications

  • Only program versions that exit with zero error code count towards the score.
  • All versions have to be listed explicitly in the answer.
  • Put the score into the title of the answer.
  • If your code produces different outputs in different programming languages, they count.

Write in Ge'ez!

Ge'ez is a now-dead language used for liturgy in the Ethiopian Orthodox Church. It's traditionally written in a very distinctive script with many loops and curves. But for ease of reading, it's often transliterated into Latin letters.

Your task here is to take some writing in Latin characters and convert it to the Ge'ez script. For example, the input gəʿəz (the name of the language) should give the output ግዕዝ.


Every letter in the Ge'ez script represents both a consonant and the following vowel. There are eight vowels

ä u i a e ə o wa

and twenty-six consonants

h l ḥ m ś r s ḳ b t ḫ n ʾ k w ʿ z y d g ṭ p̣ ṣ ḍ f p

which give 208 combinations. (In reality, some of these combinations like "wwa" don't actually happen, and there are some extra letters like "mya" not covered by this system, but ignore all that for the purposes of the challenge.)

The combinations are encoded in a convenient way in Unicode. The consonant defines the starting position, and the vowel defines the offset.

C    start (hex)
h    1200
l    1208
ḥ    1210
m    1218
ś    1220
r    1228
s    1230
q    1240
b    1260
t    1270
x    1280
n    1290
ʾ    12A0
k    12A8
w    12C8
ʿ    12D0
z    12D8
y    12E8
d    12F0
g    1308
ṭ    1320
p̣    1330
ṣ    1338
ḍ    1340
f    1348
p    1350

V    offset
ä    +0
u    +1
i    +2
a    +3
e    +4
ə    +5
o    +6
wa   +7

(Again, reality is a bit more complicated, but ignore that for the challenge.)

Your task is to take a string written in Latin letters, and output the corresponding Ge'ez syllables. If a consonant is followed by a vowel, add the consonant's start point to the vowel's offset, and print the corresponding Unicode character. If a consonant is not followed by a vowel, use the start point with no offset (as if the vowel were ä).

Input is a Unicode string, or a list of Unicode codepoints as integers. Output is a Unicode string, or a list of Unicode codepoints as integers. A "Unicode string" here can be in any official encoding (UTF-7, UTF-8, UTF-16, UTF-32…). NFC and NFD are both acceptable.

This is code golf; shortest code (in bytes) in each language wins. Standard loopholes forbidden.

Test cases:

gəʿəz    ግዕዝ
[TODO more to come here]
  • 1
    \$\begingroup\$ One option would be replacing the Unicode characters in the input with ASCII digraphs. Would this make the challenge better? \$\endgroup\$
    – Draconis
    Aug 25, 2018 at 3:15
110 111
113 114

You must log in to answer this question.

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