# Sandbox for Proposed Challenges

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

Sandbox FAQ

## Posting

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

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

## Discussion

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

• Parts of the challenge you found unclear
• 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 needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

## Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Get the Sandbox Viewer to view the sandbox more easily!

## The Challenge

The goal is to write a complete program that prints out every possible tetris block made up of #.

The blocks must have an equal chance of printing in any order and must appear exactly once each. The blocks may have any rotation, rotation may be consistent between executions. No two blocks can be touching. All blocks must have settled on the "floor".

ValidExample.exe
#   #
## ###      ##   ## #   #
##  #  ####  ## ##  ## ##

TouchingExample.exe
#
#  # ##
## ####  #  # ##   ##
##  # # ##  #  ## ##

FloatingExample.exe
#   #
## ### ## ## #     # ####
##  #   # #  ### ###


Use the language of your choice, lowest number of bytes wins

## Questions

• Is the wording clear enough?
• Does the challenge meet the expectations for a challenge here?
• What can I do to remove any ambiguity if there is any?
• Is the formatting for the question / examples ok?
• Would the challenge be "better" if the blocks had to be made up of their corresponding letter (IOJLZST)
• This could be a dupe of codegolf.stackexchange.com/questions/2223/polyomino-generator
– Sok
Mar 21 '18 at 9:22
• @someone is the new wording better? Replaced random order with a requirement that each order have equal odds. Mar 21 '18 at 10:02
• I think it is. I don't think the blocks-made-of-letters is a good idea. Mar 21 '18 at 10:04
• @Sok No input, random order, only tetrominos, no floating restriction. Those seem to be the main differences. Are they enough to distinguish it? Mar 21 '18 at 10:05

# Hyperprogramming: X×Y, X^Y, X^^Y all in two

, just like the original.

Heavily inspired by Hyperprogramming: N+N, N×N, N^N all in one.

Your task is to write two programs so that they compute different hyperoperations when they are placed in relation to each other in the form of the mathematical notation for that hyperoperation.

Full rules:

Write two rectangular programs of the same size — call them "program A" and "program B" — that each take a single positive integer as input and output that integer. In this case, "rectangular" means that every line is the same length, and that there is no trailing newline. Thus, your two programs will each be composed of M lines of N bytes each.

The catch is that when the two programs are placed next to each other in various positions, they will act as a single program that takes two positive integers, X and Y, as input and outputs either X×Y, X^Y, or X^^Y (tetration), depending on the position. Moreover, when the locations of the two programs are reversed, the resulting program will print Y×X, Y^X, or Y^^X — e.g., with X and Y reversed.

The precise location of the two programs with respect to each other is determined by the notation for that particular operation. For instance, if your program A reads

*this* is
program A


*this* is
program B


your program to output X×Y must contain both program's source codes placed horizontally adjacent without any filler inserted, like so:

*this* is*this* is
program Aprogram B


Because multiplication is commutative, both [AB] and [BA] must function identically.

Your programs to output X^Y and Y^X must contain the code of programs A and B in the locations [ᴀᴮ] and [ʙᴬ], with spaces padding the "exponent" program to the correct horizontal position and optional trailing spaces after each line of the "base" program to pad the layout into a rectangle — no partial padding allowed, it's all or nothing. Padding must be consistent for both X^Y and Y^X (as well as X^^Y and Y^^X later). Illustrated without trailing spaces:

         *this* is
program B
*this* is
program A


and

         *this* is
program A
*this* is
program B


Finally, your programs to output X^^Y and Y^^X must contain the code of programs A and B in the locations [ᴮᴀ] and [ᴬʙ], with spaces padding the "base" program, and trailing spaces after each line of the "superexponent" program to pad the layout into a rectangle if and only if your X^Y and Y^X programs included trailing spaces as padding. Illustrated without trailing spaces:

*this* is
program B
*this* is
program A


and

*this* is
program A
*this* is
program B


You do not have to support arbitrarily large integers, but your answer should work for a reasonable range of X and Y — that is, it should probably at the very least support all combinations of X and Y up to 3 except maybe 3^^3 = 7625597484987.

Source code reading is allowed, as it would be very difficult to otherwise distinguish X^Y and X^^Y in many languages.

As this is , fewest bytes wins.

Note: your score is the total byte count of a single one of your original two programs, not any of the hyperoperation-computing ones — for example, if your programs A and B are each 5×5, your score will be 5×5 + 4 newlines = 29. Since both programs A and B will have identical byte counts, it doesn't matter which one you pick.

• You may want how exacly do you define "newline". See this. Apr 2 '18 at 15:20

## Sandbox Notes

• Which tags should go?
• Is this uncomputable?
• Should I add more test cases?

# Solve logical statements about arithmetic

Ok, some of these need to go.

Integer Expressions:

• 1 is an integer expression.
• If a is an integer expression, then (-a) is an integer expression representing its negative.
• If a and b are integer expressions, then (a+b) and (a*b) are integer expressions representing their sum and product, respectively.
• A string of lowercase Latin letters is an integer expression if it is in scope. A value in scope in an integer or boolean expression is always in scope in all of its subexpressions.

Boolean Expressions:

• If a and b are integer expressions, then (a>b) is a boolean expression representing whether a is greater than b.
• If a and b are boolean expressions, then (a&b) is a boolean expression representing whether they are both true.
• If a is a boolean expression, then (!a) is a boolean expression testing whether a is false.
• If v is some string of lowercase letters, and e would be a boolean expression if v was in scope, then (v^e) is a boolean expression that represents whether e is true for any integer value of v.

You will be given a boolean expression in any reasonable format (such as a string or a parse tree). You should output one of two distinct outputs depending on whether this boolean expression can be shown to be true or false.

## Test Cases

(x^(!(y^(x>y)))) => True


Read: for all x, it is not the case that any y is less than x.
In other words, there is no number greater than all other numbers.

(!(x^(!(y^((y*y)>x))))) => True


Read: there is a number x which is less than the square of any y.
In other words: there is a number smaller than all squares (any negative number).

(x^(x>5)) => False


Read: all numbers are greater than 5.

(!(x^(!(x>x)))) => False


Read: it is not the case that all numbers are not greater than themselves.
In other words: there is a number greater than itself.

(y^(x^(!((!(y>(2*x)))&(!((2*x)>y)))))) => False


Read: for every two integers x and y, y is neither greater than nor less than 2x.
In other words: there is no number divisible by 2.

(x^((x*x)>x)) => False


Read: all numbers are less than their squares.

(x^(!(x>(x*x)))) => True


Read: there is no integer greater than its square.

• why not have - as the inverter for integers? Apr 3 '18 at 3:46
• @DestructibleLemon That was originally because I planned to add subtraction, but then decided to keep it minimal. I'm going to change that. Thanks for catching it! Apr 3 '18 at 3:51
• What about !y^(x^!(x>y&x^(a^(b^(x<a*b+1&x>a*b+-1))))&(a^(b^(x+2<a*b+1&x+2>a*b+-1))))))? (Hopefully I got that right.) Read as "for all y there exists x greater than y, such that x is prime and x+2 is prime." Apr 3 '18 at 4:23
• In short, yes, it is uncomputable I'm afraid. There's a lot of potential for interesting challenges based on this idea though! One way would be to specify a set of axioms and have it determine whether the statement is provable from those axioms, allowing the possibility that it fails to halt if it isn't. That might be quite complicated for a code-golf challenge though. Apr 3 '18 at 4:23
• @Nathaniel I somehow failed to realize that you can do prime checking facepalm Apr 3 '18 at 4:30
• @Nathaniel Do you think it's uncomputable if you remove logical negation? Apr 3 '18 at 4:31
• Do you mean logical negation (!) or integer negation (-)? (Either way it's not obvious whether it stays uncomputable, I'll have to think about it.) Apr 3 '18 at 4:32
• @Nathaniel Logical. Apr 3 '18 at 4:32
• @EsolangingFruit I thought about it for a while and it still wasn't obvious, so I posted a question here Apr 3 '18 at 4:49
• @Nathaniel The question you posted isn't exactly the same; my axioms are slightly restricted. There are only integers (and therefore there is no division), and without negation there's no way to simulate logical OR or a "there exists" qualifier. If you allow the "there exists" qualifier your Twin Prime example should be fairly easy to rewrite. Apr 3 '18 at 4:58
• Ah, you're right, I'd for some reason transposed existential (there exists) and universal (for all) quantifiers in my question --- and your point about and vs or is relevant too. I'll reformulate it and repost. Apr 3 '18 at 5:11
• I've fixed the math.SE question and undeleted it. Apr 3 '18 at 5:15
• Exactly same model
– l4m2
Apr 3 '18 at 5:28
• @EsolangingFruit the math.SE question got an answer that looks correct - even without logical negation it's still undecidable, because it contains a known undecidable problem about whether a polynomial has integer roots. Apr 3 '18 at 12:28
• Info: l4m2 attempted to make this computable by using program halt status the output (which is in turn uncomputable) in a separate sandbox post. May 9 '18 at 11:46

# Antigerrymandering

From this question:

The United States has a unique love of gerrymandering––the deliberate manipulation of an electoral district to predict certain voting results. Just recently there was a gerrymandering case brought before the Supreme Court. Gerrymandering, especially when related to race, is ruled illegal and results in the requirement to redraw the district lines.

Gerrymandering has recently been getting even more attention in the news due to this year's congressional elections. Wouldn't it be nice if we could all decide on a simple, nonpartisan way to determine congressional districts?

Your task is to fix settle this discussion once and for all with a determinate program to partition a map into districts.

## What you gotta do

Write a program or function that takes a positive integer n and a map (described below) and partitions the map into n contiguous districts of equal population (as nearly as possible) while minimizing the total length of the districts' borders.

### The map

The map is a two-dimensional, rectangular matrix of one or more integers, each integer representing the population of its cell. This can be in any convenient format—an array of arrays, a stream of numbers, or even a JPEG, if desired! You are allowed to take the dimensions of the map as additional inputs.

### The borders

Each cell in the map is to be treated as a square of side length 1. Total border length is the sum of the lengths of all edges of cells that are also the edge of a district. Note that this will necessarily include the entire perimeter of the map.

### The partition

The n districts must have the lowest possible maximum difference in population from total population / n. In the case of a tie, they must have the lowest possible total border length, ensuring compact districts.

Take the following map:

1 5 7 8
7 4 2 5
8 5 3 5


It has total population 60. To divide it into two districts, each must have population 30. Additionally, each district must be orthogonally contiguous. Both of the following accomplish just that:

1│5 7 8
└───┐
7 4 2|5
│
8 5 3│5

1 5│7 8
│
7 4│2 5
│
8 5│3 5


Of these two partitions, the upper has total border length 14 (perimeter) + 5 (border) = 19, while the lower has length 17. Of these two options (and the other one I can see at the moment, the vertical line down the middle is to be chosen, since its border length is the lowest.

Now consider:

2 1 2


This again has two possible partitions into two districts, but these are tied in border length. Your program or function can return either partition, but it must return the same one each time.

## Output

Lots of options. A string using one non-numeric character for border and another for no border. An array of numbers, with a surjection to the sixteen possible states of a cell's edges. A JPEG, with borders shaded. A pirate's map: "3 steps south. 2 steps east..." Really, anything that can be mapped to a partition. The output format must be consistent.

This is , so the shortest solution (in bytes) in each language wins!

# Sandboxy stuff

Any clarification needed?

I'm making some test cases (based on real states' population distributions!); these'll be added soon.

Anything else worth mentioning?

Thanks!

• While flexible output formats are commendable, I personally wouldn't want to check the validity of a program with output formats as broad as "anything that can be mapped to a partition". Now, checking validity of every answer isn't my job or anything, but I would want to have the option not be prohibitive. Apr 4 '18 at 19:39
• thematically related, although going in the opposite direction Apr 4 '18 at 19:59
• @KamilDrakari I'll think further on it. Thanks. Apr 4 '18 at 20:06
• @Giuseppe Yep. Meant to link in the question, but wrong link :) Apr 4 '18 at 20:07
• Will the "real" test cases be small? I ask because a golfed answer to the question as it stands is likely to be geologically slow. Apr 6 '18 at 10:00

# Find the Intersection code-golfgeometry

### Challenge

Given some planes in an n-dimensional space, return the intersection of these planes with the highest degree, if it exists.

### Details

You will be given two integers, n and k, such that 0 < k ≤ n and 1 < n. You will also be given (n-k) hyperplanes within the space Rn. (A hyperplane in the space Rn has (n-1) dimensions.) Your task is to find the intersection between them that has the highest number of dimensions, if it exists. This intersection will have at least k dimensions; it may have more than k dimensions if the inputs are not independent.

For example, if we are working in the 3-dimensional space (R3), you would be given planes with 2 dimensions. If you are given 3 distinct planes, you would at best be able to find a single point where they all intersect (0 dimensions). If you are given 2 distinct planes, you could find a line where they intersect (1 dimension). Et cetera.

### Input format

You may choose any standard format to represent hyperplanes in Rn. Here are two formats that I suggest:

1. vn = c1v1 + c2v2 + ... + cn-1vn-1 + cn, where v represents a variable and c represents a scalar constant.

2. c1v1 + c2v2 + ... + cnvn + cn+1=0.

For example, consider the plane z=2x-3y in R3. In format 1, I would write this as v3=2v1-3v2+0, so my program would take in the tuple of scalar constants (2, -3, 0). In format 2, I would rewrite this as 2x-3y-z+0=0, and similarly take the tuple (2, -3, -1, 0). You can choose one of these two formats or another standard format, so long as you provide details in your answer.

You may take in n and k explicitly if you wish, though you should be able to determine both from the list of planes (k is the number of planes, n is one more than the number of dimensions in a plane).

### Output format

You should output a single plane in the same format as your input. If no intersecting plane exists, you should return something recognizably distinct from other valid outputs of your program (such as an empty tuple, false, a thrown exception, etc.).

### Test Cases

These use suggested input format 1, with n and k provided implicitly.

[(c1, c2, ..., cn), (...), ...] => (c1, c2, ...)

In R3, the intersection of z=-3x-2y, z=5+2x+3y, and z=-x-y-1 is the point (2, -3, 0)

[(2, 3, 5), (-3, -2, 0), (-1, -1, -1)] => (2, -3, 0) // This doesn't work

In R3, the intersection of z=4x+y and z=x+2y+1 is the line y=3x-1

[(4, 1, 0), (1, 2, 1)] => (3, -1)

### Scoring criteria

This is , so the shortest answer in each language wins.

# Meta

Can you follow the goal of the challenge and the details I've provided? I've tried to be as clear as possible, but I think I may have been too verbose.

I think my output format needs to change - there's no way to represent a point in Rn the way I've phrased it...any suggestions?

More test cases coming soon.

• The specified input formats force the hyperplane to pass through the origin, but nothing else in the question indicates that restriction. Mar 29 '18 at 13:56
• Good point. I will fix that, thank you Mar 29 '18 at 16:25
• "this can be higher if some of the inputs are equal" should really be "this can be higher if some of the inputs are not independent": three planes can pass through a line without any of them being equal. Other than that, I think you just need the test cases. Apr 3 '18 at 13:48
• Thanks, this is the feedback I was looking for. I knew there were some holes in my math :) Apr 4 '18 at 14:09

# Get Rid of GoTo's

My (pseudo) code is full of goto's! What a mess... Let's change it into a more iterative code.

## SPECIFICATION

Each input consists of:

<HEADER> {
0: <code>
1: <code> (optional)
2: <code> (optional)
...
99: <code> (optional)
}


where:

<HEADER>: It is the method signature, but it can be anything. Just repeat it in the output.

<code>: It is the main code that contains the unwanted goto's and need to be refactored. It is always numbered, starting at 0 and increasing sequentially. code can be one of:

• if [condition] goto [number] [trailing]: this is where the goto's are. The if clause contains any text as a condition, that should be repeated in the output. The number should be between 0 and 99, and should point to a valid line in the input. The trailing could be a semicolon, a text comment or even nothing at all, but it will not appear in the output.
• return: the return clause is special because it ends the method execution. In the input code, a return could be followed by others lines reachable by a goto. But in the output code, a return is never followed by a code line. The return can be followed by a semicolon or nothing at all.
• anything: anything else is just code clauses that should be repeated somewhere in the output code.

## EXAMPLES

BEFORE:

method1() {
0: printMessage("This is the firstMethod");
1: if (inputString(0)) goto 3;
2: return;
3: setVar(10);
4: printMessage("Var is set to 10");
}


AFTER:

method1() {
0: printMessage("This is the firstMethod");
1: if (inputString(0)) {
2:  setVar(10);
3:  printMessage("Var is set to 10");
4: } else {
5:  return;
6: }
}


This is the simplest example. The goto is changed into an if/else structure. The 'return' clause always ends a block (i.e., the code does not continue after it).

BEFORE:

public method2() {
1: play(22, 3468, 4433);
2: int rndNum = random(3)
3: if(rndNum == 1) goto 6
4: if(rndNum == 2) goto 8
5: if(rndNum == 3) goto 10
7: return;
9: return;
11: return;
}


AFTER:

public method2() {
1: play(22, 3468, 4433);
2: int rndNum = random(3)
3: if(rndNum == 1) {
5:     return;
6: } else {
7:     if(rndNum == 2) {
9:         return;
10:    } else {
11:        if(rndNum == 3) {
13:            return;
14:        } else {
16:            return;
17:        }
18:    }
19: }
}


This example is trickier. The three gotos end up creating nested if/else clauses. Also, as the transpiler can't know if rndNum(3) returns something from [1-2-3], there is also an ultimate else clause afterwards.

BEFORE:

public method3() {
0: int curChar = whoMenu("Test", "Super");
1: if (firstChar(currentChar, 1)) goto 5;
2: printMessage("The sun is hot.");
3: if (YesNo(1)) goto 17;
4: return;
15: printMessage("You feel good");
16: if (YesNo(1)) goto 17;
}


AFTER:

public method3() {
0: int curChar = whoMenu("Test", "Super");
1: if (firstChar(currentChar, 1)) {
12:   printMessage("You feel good");
13:   if (YesNo(1)) {
15:   }
16: } else {
17:     printMessage("The sun is hot.");
18:     if (YesNo(1)) {
20:     } else {
21:         return;
22:     }
23: }
}


This example is not so hard, but note there are two goto's going to the same line. As this line does not create a loop, it is permitted (see rules below).

BEFORE:

method4() {
0: printMessage("This is the firstMethod");
1: if (inputString(0)) goto 4;
2: printMessage("End is near.");
3: return;
4: setVar(10);
5: if (inputString(1)) goto 2;
6: printMessage("Var is set to 10");
}


AFTER:

method4() {
0: printMessage("This is the firstMethod");
1: if (inputString(0)) {
2:     setVar(10);
3:     if (inputString(1)) {
4:         printMessage("End is near.");
5:         return;
6:     } else {
7:         printMessage("Var is set to 10");
8:     }
9: } else {
10:    printMessage("End is near.");
11:    return;
12: }
}


This example is also tricky, because it contains a goto to a previous line. This does not create a loop, but it also creates a block that is repeated twice in the code.

## CONSIDERATIONS:

1) Goto's are always associated with an 'if' clause. Replace the goto with a start block '{' clause.

2) Goto's always create an 'if', but not necessarily an 'else'.

3) Some clauses can repeat due to more than one goto's going to the same line (directly or not).

4) There won't be loops. Example of invalid code:

public methodInvalid() {
0: if(YesNo(1)) goto 2;
1: printMessage("this code is invalid.");
2: if(NoYes(1)) goto 0;
3: printMessage("still invalid.");
}


5) Identation in the output is desirable. Each if/else block must be nested with a tab for each nested level. If you want to replace the tab for 2, 3 or 4 spaces, ok, just state it and make it coherent on your code.

6) As there won't be more goto's, the line numbers are optional in the output code. Just don't put them out of order, if you want to keep them.

7) The first line can be ignored (just repeat it in the output) and the last line is always the close statement ('}'). These lines are never numbered.

8) The input will always contains line numbers, starting with 0 and a colon. The next line will be 1 and a colon, and so on. No more than 99 lines will be present.

9) There is also at least one space (or tab or opening parenthesis) after the if statement, one space before the goto statement and one space before the number after it. So "1:ifagoto2" is invalid, but "1:if a goto 2" is valid and also valid is "1: if(a) goto 2". Spaces (or tabs) are optional before the line numbers and between the semicolon and the start of the code.

10) You only need to worry with (a) 'goto's; (b) line numbers; (c) the 'return' clause; and (d) the end of the code (last line). Everything else is gibberish, you don't need to interpret the code. See a valid input below:

BEFORE:

fun with code {
0: gibberish
1: if a goto 3
2: gibberish
3: gibberish
4: gibberish
}


AFTER:

fun with code {
0: gibberish
1: if a {
2:  gibberish
3:  gibberish
4: } else {
5:  gibberish
6:  gibberish
7:  gibberish
8: }
}


Standard loopholes apply, shortest answer in bytes wins!

• Will line number always start with 0 and increase by 1? Is there any un-conditional goto? Will there be any dead code in the input?
– tsh
Apr 8 '18 at 1:32
• @tsh Yes, the number always start with 0 and increase by 1. No, goto's are always preceded by if's. Dead code in the input? I think so, there is no restrictions against that. Apr 8 '18 at 23:54
• Suggested title: Code golf considered harmful. Apr 9 '18 at 4:13
• Is if(a)goto 2 allowed?
– l4m2
Apr 9 '18 at 12:57
• @l4m2 No, because "There is at least ... one space before the goto statement" Apr 9 '18 at 15:08

# Scoring a Game of Composite Boards code-golfclassification

### The Game

Given a board size n which must be a composite number, the game is played on m boards in parallel which correspond to the m factors of n, excluding 1 and n itself.

E.g. if n = 12, we get the following 4 boards, where the same character represents the same field:

01     012     0123     012345
23     345     4567     6789AB
45     678     89AB
67     9AB
89
AB


Two players, Zero and One, take turns in writing a 0 or 1 respectively on an empty field, which makes that number appear on all boards at the corresponding field.

On each board their goal is to get more rows or columns filled with just their number than their opponent, resulting in the board being either a win for Zero, a win for One or a draw if both players fill the same number of rows or columns.

The game is won by the player who wins the majority of boards, or results in a draw if both players win the same number of boards.

### Example

Let's say we have the game 010111010100 of size 12, which corresponds to the following boards:

01
01
11 <- row for player One
01
01
00 <- row for player Zero
no columns for either player -> draw

010
111 <- row for One
010
100
-> One wins this board

0101
1101
0100
^^
one column for each player -> draw

010111
010100
^^^^
two columns for each player -> draw


As player One wins one board and player Zero wins none, player One wins the game.

Given a completed game as input, output which player won or whether the game was a draw. This is , so the smallest answer in bytes in each language wins.

### Input

A one-dimensional array/list/string of two distinct values representing the fields of the boards when read left-to-right and top-to-bottom. You can assume that the input describes a valid game, that is the length will always be a composite number and the two values appear either the same number of times for even board lengths or with a difference of one for odd board lengths.

### Output

Three distinct constant values which correspond to player Zero wins, player One wins or draw.

### Test Cases

Draw: (All games of size 2*p where p is prime necessarily result in a draw)

0110
101010
11010010
010101010
11001111000100


Zero wins:

110110000
001001110101
1000110101011001


One wins:

111100001
010111010100
1100111100010010
0111010001001101


# Curve Matching

Given two lists a, b of the same length n find a third list x of indices such that a(i) = b(x(i)) for all indices i and x(i) <= x(i+1) for all applicable indices i and x(1) = 1 and x(n) = n.

### Details

• The list x is not necessarily unique (for instance when b has a run of two or more equal entries).

• In the challenge description we use 1-based indices, but you can also use 0-based indices.

• You can assume that a and b contain integers, floating point numbers, characters or any other types that have a natural order and have at least 256 distinct values.

• You can assume that such an x exists. (You can for instance assume that a=[1,2,3], b=[1,2,1] are never passed as an input.)

### Examples

a = b = [1,2,3]
x = [1,2,3]

a = [1,3,3], b = [1,1,3]
x = [1,3,3]

a = [1,1,2,3,4,4], b = [1,2,2,3,3,4]
x = [1,1,2,4,6,6] or [1,1,3,5,6,6] etc

a = [1,1,2,3,2,1,1], b = [1,2,1,2,3,2,1]
x = [1,3,4,5,6,7,7]


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

Unless someone can convince me otherwise I think this is too close to Are the brackets fully matched? to be an interesting new challenge, so I won't submit it.

# Well-formed Parentheses Gone Wild

The object is to determine if the "parentheses" in a string are well-formed, in the sense that they are balanced and well-nested.

For example [(ab(c!{})n)] is such a string, while [(ab(c!(d)x){)}] is not (balanced, but not well-nested due to the last closing ) appearing before the closing }).

## But wait, there's more

Those examples took advantage of the commonly understood meanings of the pairs (), {}, and []. But any characters could be opening and closing parentheses, and not just the obvious ones.

## Input

The input consists of two strings with optional trailing newlines. The characters can be any ASCII printable character (hex 20 to hex 7E).

The first string has an even number of characters with no duplicates. Each successive pair of characters defines a pair of opening and closing parentheses. The second string is the test string.

## Output

Truthy or falsy value (with optional trailing whitespace) for whether or not the parentheses in the test string are well-formed (balanced and well-nested). If either the first or second strings are empty, the answer is defined to be truthy.

## Some Tests

Format:

String1
String2
Output


Tests:

(){}[]
[(ab(c!{})n)]
truthy

(){}[]
[(ab(c!(d)x){)}]
falsy

()[]<>
[(ab(c!(d)x){)}]
truthy

<---- empty parenthesis string
%$w%jS(5gS truthy (){}[] <---- empty test string truthy qwertyuiop q##qCfet^Hy&&r$wuiwgJo7({)}erxp
truthy

@#$%^& super b$fox\$#@%%g ongshow^&
falsy


## Scoring and Rules

• This is . Shortest entry wins.
• Standard loopholes forbidden and standard rules apply.
• I believe this is a duplicate Apr 20 '18 at 21:03
• @NathanMerrill this challenge has the input define its own parentheses and require that it's well-formed. That would definitely need different code. Apr 20 '18 at 21:19
• Why not go with 2 separate strings in any convenient format? Can the open and close parentheses be the same, e.g. quotes? Apr 20 '18 at 21:23
• @StephenLeppik - two strings in a convenient format would be better. The , and ! are not relevant to the problem. Would it be canonical to say "two strings with optional trailing newlines"? I want to include the space   as a possible character in either string.
– ngm
Apr 20 '18 at 22:08
• @StephenLeppik Open and close parentheses must be different, as implied by the even number of characters with no duplicates in the first string.
– ngm
Apr 20 '18 at 22:16
• Is it possible to take a list of length-2 string (for the first input)? Apr 21 '18 at 10:09
• This is a better dupe. The 05AB1E answer and the (20-byte) Pyth answer can be directly ported to this challenge. The Javascript answer... need some join-with-| and regex construction. Apr 21 '18 at 10:13
• I'm thinking codegolf.stackexchange.com/questions/77138/… is close enough to make this challenge uninteresting. What's the protocol? Do I delete this or just leave it so nobody else tries the same?
– ngm
Apr 21 '18 at 17:21
• You could always spice up the rules to make your challenge unique. Apr 21 '18 at 19:23
• What if there was an order on the different parenthesis so that () has to be closed before [] can be open or something along these lines? So your String1 in the example would define an order. Jun 11 '18 at 3:42

# Golf the linux kernel

This file [to do: make the file and provide a link] contains all the code in the Linux kernel, concatenated together into a single file. Your task is to output this exact file.

The code in the file has been stripped of all comments, except for the copyright notice at the top, which is a legal necessity in order to distribute it.

This is a challenge, so your score is the size of your submission in bytes, and the smallest score wins.

If your submission will contain multiple files (for example, code and a separate data file), please take note of the rules on scoring and directory structure for multi-file submissions. Any data that your code uses must be included in your score.

Sandbox note

This is an unusual challenge, in that the specified output consists of a really huge file. (Probably in the hundreds of Mb.) Normally that would mean built-in compression methods would dominate, but the Linux kernel has a lot of structure in it, both due to the grammar of C and due to the strict coding standards. For that reason I would expect customised algorithms to out-perform standard ones, so it should make for an interesting open-ended challenge along the lines of Paint Starry Night or Write Moby Dick.

• I think you should have to output it; your program is a way of distributing it. IANAL though. Apr 22 '18 at 15:48
• Because the header is very small in comparison with the text, it should not be too much of a problem. Apr 22 '18 at 16:15
• @wizzwizz4 IANAL either. I imagined it would only count as distribution if you give it to someone else. But since I'm not sure I've changed it for now. Apr 22 '18 at 16:15
• @Nathaniel You're giving it to everybody on the internet, so it's distribution. Apr 22 '18 at 16:15
• @wizzwizz4 right, and that's why I'm including the header. But for someone running their own program and verifying the output, they wouldn't be giving it to anyone, hence no need to reproduce the header. But I've changed it for now anyway. Apr 22 '18 at 16:17
• @Nathaniel That's true. If somebody submitted it, though... (This is just for others reading this; I'm not arguing with you.) Apr 22 '18 at 16:17
• @user202729 it shouldn't be a problem by the numbers, but it would result in a challenge that amounts to "compress this huge amount of code (plus this small amount of English text)", which I thought might be annoying. Not really sure though. Apr 22 '18 at 16:19
• @wizzwizz4 gah, that opens up a whole can of worms I hadn't thought of - the entries to this competition probably count as works derived from the Linux kernel, and hence have to be distributed under the GPL themselves. That probably spells the end for this challenge idea, unless I use some other large body of code that's public domain or released under a much more permissive license. Apr 22 '18 at 16:22
• @Nathaniel Oh... Well, erm... I don't think they... Wait, they would... Ask on Open Source. They'll know. Apr 22 '18 at 16:23
• It might be a good idea to change scoring to be more like the Moby Dick and Starry Night challenges, where the scoring is based on "similarity" rather than requiring an exact match. I think that should get around some of the Open source issues since the output wouldn't really contain the kernel or anything runable at all, and imo tends to favor custom implementations over built-in compression due to higher tolerance for lossy approximations. Apr 22 '18 at 17:03
• @KamilDrakari Then there would be empty submissions... no. Also how will it be different from Moby Dick then? Apr 23 '18 at 0:18
• @user202729 if I wanted to go in that direction, there is a numerical parameter in the Moby Dick scoring system, which in retrospect was set a bit too high. I could change it to L+E or even 0.5L+E, which would result in a significantly different challenge, and the different regularities in the target text would make a big difference also. But I doubt that would really get around the legal issues, and I prefer the pure-ness of this idea, if I can get it to work. I'll just have to find a project with a different license - I'm sure that exists somewhere. Apr 23 '18 at 1:54
• Or I could use a completely different similarity measure. I've been thinking about something based on log loss, which would work much better as a similarity metric, at the cost of being more complicated to explain and implement. A follow-up to Moby Dick is in the works at some point, but I'm very aware of the need to make it different enough from the original. Apr 23 '18 at 1:58
• I've seen claims similar to "For that reason I would expect customised algorithms to out-perform standard ones" fail to be backed up by answers outperforming standard algorithms enough times that IMO it's not worth posting a kolmogorov-complexity challenge unless you have written a reference answer which outperforms bzip2 and gzip. Apr 25 '18 at 11:35
• @PeterTaylor that's a fair point --- if I find a body of code with a suitable license I will do that, and I won't post if I'm wrong. (I did a similar test for Moby Dick.) Apr 25 '18 at 11:40

### Sandbox notes

• Is there anything that is unclear?

# Double Language Supersets

For the purposes of this challenge:

• A language is a partial mapping from programs (strings of bytes) to outputs (streams of bytes). Not every output must be finite or produce any elements before looping indefinitely.
• A language L is an superset of another language K if, for every program of length n given meaning in K, there is a program of length n given meaning in L which produces the same output. In other words, all programs in K can be translated into L without requiring any more bytes.

(cops' part)

As a cop, you must:

• Find two languages, and provide (or link to) a specification in the form of a detailed description or an implementation. Be prepared to answer any questions should ambiguities arise.
• Define a new "solution" language which is a superset of both of the others. This can be in the form of a detailed document, implementation, or a proof that such a language exists.

You should reveal the first two languages, but keep the solution language secret.

The cop whose submission takes the longest to crack is the winner.

(robbers' part)

As a robber, you must:

• Find an existing cop submission.
• Define a new language which is a superset of both of the languages provided by the cop. This can be in the form of a detailed description, an implementation, or a proof that such a language exists.

The robber who cracks the most cop submissions is the winner.

• So it's a partial mapping? Apr 22 '18 at 14:00
• @user202729 Yes Apr 22 '18 at 22:36
• I don't think that polyglot makes sense here. Apr 23 '18 at 14:16
• I don't think this really makes sense as a c'n'r. Both cops and robbers are trying to do the same thing, which is to prove that every program which is valid in both languages gives the same output in those languages. The robber doesn't have to outwit the cop by beating a score or working within extra constraints which the cop chooses and can try to use to add false clues. The only real asymmetry is that the cop chooses the languages, and the only way to exploit that to make it interesting is to make one of them a homebrew which is "specified" with an obfuscated implementation. Apr 25 '18 at 10:56

# Decode my Alphabet Code (Cops)

This is my first C&R challenge, so I thought I'd better post it in the sandbox. This is only the Cops thread and it's still missing some usual C&R rules (such as explaining what should be done once a submission has been cracked).

As a Cop, you must write either a full program or a function that meets the following requirements.

### Input

A non-empty string made of at most 26 distinct characters in a given code page. The input is guaranteed to be valid.

The code page is either UTF-8 or -- at your option and if applicable -- a specific code page used by your language.

### Output

A string of the same length and in the same code page where the first encountered character is replaced with A, the second encountered character (distinct from the first one) is replaced with B, and so on.

For instance, the expected output for Hello, World! is ABCCDEFGDHCIJ, where A=H, B=e, C=l, etc.

### Code restriction

Your code must be a valid input for itself. In other words, it must consist of at most 26 distinct characters in the chosen code page. (But of course, each distinct character may be used several times.)

• The language used
• The code page used
• The size of the code in this code page
• A brief description explaining the nature of your code (program or function) and the I/O formats it's using, in case it slightly differs from string/string.
• The output produced by applying the transformation to your code

Example:

# MyLanguage, 32 characters in MyLanguage code page

A function taking an array of characters and returning a string.



Robbers must crack your submission by finding a working program that produces exactly the same output once transformed. (Finding a shorter program is not a valid crack.)

# Rules

If your answer remains uncracked for a week, you can mark it as Safe and unveil the original code.

The winner is the shortest uncracked answer. In the case of a tie, the oldest answer wins.

### Sandbox questions

• Is it a dupe or too close to an existing challenge?
• In the original version, the encoding was forced to UTF-8. I'm still not sure which option is the best, so I'm interested in any feedback about that.

• All other comments and suggestions are much welcomed!

• Do spaces count too ? Apr 24 '18 at 14:16
• @MuhammadSalman Yes, all distinct characters are taken into account. (The space becomes F in my Hello, World! example.) Apr 24 '18 at 14:18
• I suggest only using bytes. Most languages I know of have SBCS anyway, otherwise the translation from UTF8 to bytes are straightforward enough. Apr 24 '18 at 14:20
• To be clear, this is not code-golf, correct? Apr 24 '18 at 14:24
• @user202729 Using only bytes is indeed another possibility. But it may make the submissions quite harder to check. For instance, if you pass the posted UTF-8 representation of a Jelly program to this same Jelly program which is expecting it in its own code page instead, it's likely to fail. Apr 24 '18 at 14:34
• @user202729 I need to add that the shortest uncracked answer wins. So, I suppose it should be tagged as code-golf as well? (Although the primary winning criterion is to remain uncracked.) Apr 24 '18 at 14:35
• If a language only uses less than 26 characters, can we only support up to that many letters of the alphabet?
– Jo King Mod
Apr 25 '18 at 10:30
• @JoKing No, the program must support all inputs. (But of course it's fine if the code itself is only using a couple of distinct letters.) Apr 25 '18 at 10:37

## Integers as "polynomials"

Suppose we use successive digits of an non-negative integer for coefficient, base and power respectively and construct a "polynomial". For a 4-digit number we'll have:

abcd -> a*b^c + b*c^d + c*d^a + d*a^c.

Each digit must go through the three roles exactly once. For the last two members we wrap around the right edge and use the first/second digit again.

For example 1234 will represent the following "polynomial":

1*2^3 + 2*3^4 + 3*4^1 + 4*1^2 -> 1*8 + 2*81 + 3*4 +4*1 -> 186

We started with an integer and ended with an integer. That gives me the idea that we can feed the result into the procedure again and keep calculating. As it seems the numbers will sooner or later start repeating, leading to an endless loop. For example:

4 -> 1024 -> 12 -> 4 -> ...

I'm interested in how many cycles are needed until we come to a number that has already been calulated.

Start with a non-negative integer and calculate my "polynomial" from it. Keep calculating using the result as input until you reach a number that has already been calculated.

Your answer must be theoretically correct if your language's integer types had infinite width, but you may use any integer type with at least 8 bits

## Input:

You can take the input as:

• A non-negative integer
• A list of digits
• A string

## Output:

A single integer - the number of cycles until a known number is reached.

## Winning criteria:

This is , so shortest code in bytes in each language wins. Explanations of the code are welcome!

## Test cases:

 0:  1
1:  1
2: 34
3:  5
4:  3
5:  3
6: 29
7: 48
8: 33
9: 20
10:  1
11: 35
12:  3
13: 30
14: 34
15:  2
16:  3
17: 35
18:  4
19:  5
20:  1
21:  3
22:  4
23: 79
24: 78
25: 36
26: 34
27: 15
28: 41
29: 57
30:  1
31: 30
32: 79
33:  3
34: 10
35: 45
36: 32
37:  9
38: 64
39: 10
40:  1
41: 34
42: 78
43: 10
44: 30
45: 16
46: 39
47: 13
48: 96
49:  7
50:  1
51:  2
52: 36
53: 45
54: 16
55: 11
56: 40
57:  4
58: 12
59: 17
60:  1
61:  3
62: 34
63: 32
64: 39
65: 40
66: 30
67:  4
68:  6
69: 77
70:  1
71: 35
72: 15
73:  9
74: 13
75:  4
76:  4
77:  9
78: 38
79:  6
80:  1
81:  4
82: 41
83: 64
84: 96
85: 12
86:  6
87: 38
88: 97
89: 13
90:  1
91:  5
92: 57
93: 10
94:  7
95: 17
96: 77
97:  6
98: 13
99: 69

• "Not surprisingly the numbers will sooner or later start repeating, leading to an endless loop" Do you have a proof of this? It seems plausible but not obvious that no chain escapes to infinity. Apr 30 '18 at 14:59
• @Peter Taylor - No, I don't have any proof. Maybe I need to change the description? Apr 30 '18 at 15:18
• I've found a proof: 12 x 9<sup>10</sup> = 4.1841412812 x 10<sup>10</sup>, so any number with 12 or more digits maps to a number with fewer digits. There is one thing which I think it's probably worth adding, and that's a statement about overflow. Options include "Your answer must be correct if intermediate values don't exceed N bits, but may be incorrect if they do exceed that"; "Your answer must be theoretically correct if your language's integer types had infinite width, but you may use any integer type with at least 8 bits". Apr 30 '18 at 15:41
• @ Peter Taylor Thank you for your help! You are completely right abiut the overflow - I have used J's extended precision to make the test cases. I'm going to update the description. May 1 '18 at 8:35

# Relational Division

Given a database of colored marbles in bins, find which bin has the most marbles of a certain color. In database administration, this task is known as relational division.

## Example

Input marbles (flexible format, this is just one possibility):

red,A
blue,B
green,C
red,B
red,A
blue,A


Input color:

red


Program output:

A


## Format

Each 'marble' is represented as a (color, bin) pair, so the entire database of marbles is represented by a list of these pairs. The list can be fed into your program in any reasonable way so long as the association of the input data remains between colors and bins -- for example via CSV on stdin in color,bin pairs split on newlines in string-manipulation programs, or perhaps via a list of (str, str) tuples as a parameter to a function in a language like Python. It's up to you.

In my examples, I'm using strings to represent colors and bins, but you can use any data type that is capable of representing at least 1000 distinct values in your programming language (i.e. no booleans). Examples of other acceptable data types would be integers or floats so long as you're consistent.

It's very important that colors cannot be used as bins, and bins cannot be used as colors (i.e. the set of bin identifiers and the set of color identifiers must be disjoint). If this isn't true, the result is undefined.

In addition to the marble database, your program takes in a color identifier, again in whatever way is most convenient to do I/O of a single value in your language. Your program must output or return a unique identifier for the bin that contains the most marbles of that color.

The result is undefined if the input color doesn't exist, or if there is a tie between multiple bins (i.e. if the input color is red, there are 70 red marbles in total, and two bins both have 30 red marbles). Your program should be expected to handle up to 1000 input marbles without much difficulty.

This is a challenge, so the shortest program wins, with submission time (earlier is better) as the tiebreaker.

• If it's a function, it must output to stdout too? Huh? May 3 '18 at 1:28
• @user202729 Thanks, bug fixed! May 3 '18 at 3:10

# Conway's Battlegrounds

Conway's Battlegrounds will be a mix of PUBG and Conway's Game of Life. In this challenge, you will need to make a Python bot that will play it.

## Game rules

The controller, at the beginning of the round, will create a two-dimensional 500x500 toroidal (edge wrapping) board with chosen cells being alive, the others are dead.

The players are then separated into equal teams, each with 4 bots. If there isn't enough players in the team, some of them might be duplicated.

## Gameplay

### "Parachuting" phase

Everybody in the game will be given the array representing the starting state of the board. Each bot's class will be initialized, with these arguments in order:

• num - an int between 2 and 5 inclusive, representing the number you'd be marked with on the map during the game. The other numbers in the range will be your party members.
• area - Dictionary, where each key is a 2 value tuple (x,y) and each value is either a 0 (dead cell) or 1 (alive cell)

During this phase, each bot's method parachute will be called exactly 10 times. It will be given only one argument:

• team - 4 item dictionary with your and each teammate's ID (between 2 and 5) as key and a 2 item tuple as value, representing the (x,y) position they chosen, or None if they didn't yet chose any.

The method can return a 2 value tuple, representing where the bot want to start or None, if the bot can't decide. The returned value will be visible to every other teammate.

The method will be called again, even if the player already chose a location. The next return value will replace previous. You can prevent that by returning team[self.num], assuming you saved the num parameter from __init__.

It is recommended to spawn your bot near teammates, so it's easier to cooperate later.

If the method has been called the 10th time and the bot didn't return that time a (int, int) tuple, it will be removed from the game.

Each bot will then be spawned at a random location in a 9x9 rectangle, with the returned location in the center. The bot will not collide with other players.

## Starting phase

This phase will take exactly 25 turns. It's almost the same as the later, main phase of the game, except that no cell will die or be created in it.

The start method of each bot will be called once every turn. It will take these arguments in order:

• area - Basically the same as in the previous phase, but with several modifications:
• It will be only a 25x25 fragment of the map, with the bot in the middle.
• It might also contain the ints in range 2..5 representing each teammate.
• It might also contain the int -1 representing an opponent.
• turn - The number of the turn, starting with 0. In the last turn of the phase it will be 24.
• chat - a list of new chat messages, stored in tuples (author_id, msg_id)

The method must return a 0..4 value tuple or list, which may contain up to three actions the bot will perform during it and optionally a single chat message. Each item in tuple is a one move, depending on the value:

• Falsy values (0, None, False) - Do nothing
• Positive int - Move in given direction, according to the rule (where the bot is in the center):

1 2 3
4   6
7 8 9


Bot can only move to a neutral position.

• Negative int - Replace a neighbour dead cell with a neutral alive cell, according to the rule above, ex. -1.
• String - Send a chat message with the given ID, explained later

## Main phase

Similar to the previous phase, but in this one, cells can die. It won't end until only one team is on the board.

The main method of each bot will be called once every turn. It will take these arguments in order:

• area - Same as in starting phase
• team - Dictionary with position of teammates id: (x, y)
• turn - The number of the turn, starting with 0. In the last turn of the phase it will be 24.
• hp - The amount of health points the bot has, explained later. Initially 4.
• chat - a list of new chat messages, stored in tuples (author_id, msg_id)

The return value is the same as in the previous phase.

### Neighbours, dying and reproducing

• A neighbour of a cell a is an another cell that is positioned next to the cell a, either orthogonal or diagonal.
• A neutral cell is any cell that is either 0 or 1 (isn't a bot).
• A bot cell is any cell occupied by a bot, that is, the negative number -1 and positive 2, 3, 4, 5.
• A dead cell is any cell that is exactly 0.
• An alive cell is any cell that is not dead (0). This includes both bot cells and 1's.

In this round, cells can die. They can also reproduce.

• Neutral cells (marked 1) will die (turn to 0) if amount of their alive neighbours is not 2 nor 3.
• Dead cells (marked 0) will reproduce (turn to 1) if amount of their alive neighbours is exactly 3.

Rules about bot cells (-1 and greater than 1) are a bit different though.

• Bot cells will lose 1 hp if amount of their alive neighbours is not 2 nor 3 and no natural cells were reproduced in the neighbourhood.
• Bot cells will die if they have 0 hp.
• Bot cells will gain 1 hp if amount of their alive neighbours is equal to 3 and at least 1 neighbour is a teammate. Cell will not gain hp if it has 3 or more hp.
• Bot cells will be moved if amount of their alive neighbours is not 2 nor 3 and a single nearby cell was reproduced (it will replace it). Bot cells cannot duplicate.

### The red zone

Every 100 generations (turns), the red zone will start in the place with most dead cells. It will end after 10 turns, and every second turn it will spawn a glider.

## Chatting

Bots in the same team can communicate between themselves during the game.

Some of the messages were made because of how the board is generated. Make sure you read this before, so you can use it to collaborate with other bots easier.

Here's a list of all "built-in" messages:

• 1 - Help!
• 2 - Wait!
• 3 - Need healing!
• 4 - Come here
• 5 - Enemies are nearby
• 6 - I'll fight
• 7 - I'll build
• 8 - Search for boats/Build a boat
• 9 - Get in the boat
• 10 - Exit the glider

## The controller

WIP, I won't probably have time to make it this week.

## Example bot

A classic random bot, won't survive long.

import random

class RandomBot:

def __init__(*args): pass

def parachute(self, team: dict):

return random.choice([x for x in team.values() if x])

def start(*args):

return random.randint(-9, 9)

def main(*args):

return RandomBot.start()


• You have access only to non-superuser built-in Python packages
• You must not create, write nor open any files
• You cannot access any of internal or other bot's classes
• You cannot modify any mutable arguments given to your methods, only their copies
• You shouldn't throw any exceptions
• You must return only specified values.
• The code you publish here must not output anything
• During the parachute phase, the team[self.id] should be that bot's last return value, and the other values should be the other teammates in the same order as their ids. May 7 '18 at 18:28
• You say that bots are given Ids from 2 to 6 inclusive with a team of size 4. However, there are 5 values in the range 2 to 6 inclusive. May 7 '18 at 18:46
• @KamilDrakari I noticed that earlier, but somehow didn't edit it in. Thank you! May 7 '18 at 19:05
• I think it needs to be made clearer that the Game Of Life part of this challenge essentially treats all bot locations as "alive" cells. So the location of a bot is relevant for cells spontaneously becoming alive, the bot loses HP in situations where a cell would die, etc. That was the impression that I got, but it didn't immediately "click". Moving the bot if an adjacent tile reproduces and the bot would otherwise take damage is unintuitive, but I guess there's probably a good reason for it. May 7 '18 at 19:23
• @KamilDrakari I edited the challenge to make it more clear. Originally, the reason for bots moving instead of taking damage was to allow the existence of vehicles, but as I look on the challenge now, I think I screwed it up, because a vehicle (glider) won't be any faster than the cell itself. Unless I increase amount of generation between turns May 8 '18 at 11:34
• @Soaku I don't think having multiple generations between turns sounds fun, and it adds some extra weirdness to taking damage (either you can take damage multiple times with no way to act, or you lose the "take damage any time your cell would die" symmetry). I think losing the vehicles is a better tradeoff. May 8 '18 at 12:37
• @KamilDrakari I know. So given that, the rule doesn't make any sense now. May 8 '18 at 12:48

# Nice Tile Connector

Your task is to connect the tiles given to you in the input by removing the lines on sides they connect

## Input

A set of tiles that are not yet connected

## Output

The tiles with the walls removed in the right places to connect them

## Method

Each tile in the input looks like this:

___
|~|
|_|


Every air space looks like this:

...
...
...


On a tile, the top line is in front of the side lines, which are both in front of the bottom line. That means the top line will always replace the | characters that would be there on the sides, and the side lines will always replace the _ characters that would be there on the bottom.

Each tile must have any lines removed that are adjacent to other tiles

## Example

The input

...______...
...|~||~|...
...|_||_|...
...___...___
...|~|...|~|
...|_|...|_|
...______...
...|~||~|...
...|_||_|...


The output

...______...
...|~~~~|...
...|~~__|...
...|~|...___
...|~|...|~|
...|~|...|_|
...|~~___...
...|~~~~|...
...|~~~~|...


As this is , smallest solution in bytes wins.

## Pascal Squared Sums

Most everyone here is familiar with Pascal's triangle, which is formed by taking the summation of the two parent objects. Here are the first few rows:

     1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...


Let's instead rotate this to the left by 45 degrees, and assume that it's forming an infinite matrix. Alternatively, this can be thought of as the triangle is reading the anti-diagonals of the matrix.

1 1 1 1 1
1 2 3 4
1 3 6
1 4   ...
1


Given an input n, take the top-left n x n sub-matrix of this infinite matrix. Then, take the column sums of that n x n matrix as your output.

For example, for input n = 3, this would result in the sub-matrix

1 1 1
1 2 3
1 3 6


Taking the column sums gives us 3, 6, 10, so our output is [3, 6, 10].

### Standard I/O Boilerplate

• Note that the output are just the [2~k+1]'th element on the k'th row (1-indexing) May 11 '18 at 16:27
• @user202729 Really? Dang. I was hoping there was a nice relation, but I didn't expect something that simple. Hmm, maybe need to rethink this. May 11 '18 at 16:54
• Neim, 6 bytes: p₁ᛖ𝕖2𝕘 (polygonal list with side length of input, select first double input elements, remove first two elements)
– Okx
May 11 '18 at 20:36

# Polyraptor/Forerunner Combo

Notice: You probably need to understand the Stack in MTG for this challenge!

A new expansion to the trading card game Magic: The Gathering, Rivals of Ixalan, was released this January. In this set were the two cards important to this challenge: Forerunner of the Empire and Polyraptor, as I learned just now after losing a game of MTG Arena.

I like the Polyraptor in the background of Forerunner. Wizards knew precisely what they had brought about.

If you'll notice, if a Polyraptor enters the battlefield under your control, since it's a Dinosaur (look at the bit just below the art), it triggers Forerunner of the Empire's second ability. You may then have the Forerunner deal one damage to all creatures, including itself and Polyraptor! This clones Polyraptor, and the clone ALSO TRIGGERS THE ABILITY! This time, each Polyraptor (there are two now) takes one damage, and TWO new clones spring into being! However, these clone-making abilities execute one after another, not simultaneously. Both are pushed to the Stack, and the second pops and resolves. The Polyraptor clone enters the battlefield and triggers the Forerunner's ability BEFORE the second Polyraptor clone is created (Forerunner's ability pops from the Stack earlier). Again, Forerunner of the Empire deals one damage to each creature. There are now three Polyraptors, and each takes one damage. Three more Polyraptor clonings enter the Stack, which now contains four. The Forerunner, having at this point taken three damage this turn, dies, and the rest of the Polyraptors enter the battlefield without triggering its ability. When all's said and done, there are seven Polyraptors on the battlefield.

### Generalization

Now, imagine for a moment that Forerunner had five toughness and Polyraptor three instead. Let PA := Polyraptor-cloning ability and FA := One damage to all creatures.

Polyraptor enters.                        Stack: FA
Forerunner deals one to each creature.    Stack: PA PA
Polyraptor enters.                        Stack: PA FA
Forerunner deals one to each creature.    Stack: PA PA PA PA
Polyraptor enters.                        Stack: PA PA PA FA
Forerunner deals one to each creature.    Stack: PA PA PA PA PA PA
At this point, the original Polyraptor dies. It will no longer take damage. Three left.
Polyraptor enters.                        Stack: PA PA PA PA PA FA
Forerunner deals one to each creature.    Stack: PA PA PA PA PA PA PA PA
Another Polyraptor dies. Three left.
Polyraptor enters.                        Stack: PA PA PA PA PA PA PA FA
Forerunner deals one to each creature.    Stack: PA PA PA PA PA PA PA PA PA PA
Another Polyraptor dies. Three left.
Forerunner also dies here.
The Stack empties with no more abilies triggered.


Here, the final Polyraptor count is 13.

Write a program or function that takes as input two nonnegative integers F and P and returns the final count of Polyraptors when a Polyraptor with toughness P is cast while its owner controls a Forerunner of the Empire with toughness F.

### Test cases

Form: F, followed by P, followed by the result and an explanation.

0 0
0
The Forerunner has zero toughness, so it dies before anything happens. The Polyraptor dies immediately upon entering play.

0 5
1
As before, the Forerunner dies, but this time, the Polyraptor lives to see the dawn.

1 0
0
The Forerunner's ability triggers once, but all Polyraptors die on their own.

1 5
2
This time, the Forerunner kills itself damaging and copying the Polyraptor once.

2 5
4
Again, Forerunner kills itself, but this time, it manages to copy the Polyraptor and then both the original and the copy.

3 5
7
See above

5 3
13
See above

More coming! This is hard to do by hand :|


### Rules

• Forerunner of the Empire's ability says "may". Ignore that—it always deals the damage.
• Standard loopholes are forbidden.
• I/O is flexible.
• This is , so the shortest solution (in bytes) in each language wins! Happy golfing!

# Sandboxy Stuff

Did I mess up a test case?

What do y'all think? Should I explain the Stack so all can understand?

• I think you did mess up the 5 3 test case: I get 10, and 5 4 gives 13. Reference implementation (goes to tio.run but I had to use a link shortener because of the limitations of comments and because I used ungolfed variable names etc.) May 14 '18 at 10:30
• And on the basis of reference values, I claim that the solution is pretty straightforward by case split: using f and p respectively for Forerunner and Polyraptor toughness, it's p == 0 ? 0 : f < p ? f*(f+1)/2+1 : p*(p+1)/2 + (f-p)*(p-1), where the last case can be golfed to p*(3-p)/2+f*(p-1). Not sure there's enough here for an interesting challenge. May 14 '18 at 10:44

# Create a solver for the Topspin puzzle

The Topspin puzzle consists of 20 round pieces in one long looped track. The pieces can slide along the loop. There is a turntable on one of the sides of the the loop which can rotate the four adjacent pieces laying within it, so that they reverse their order.

By sliding the pieces left and right and rotating the turntable the puzzle can be scrambled.

The goal is to restore the pieces in their initital order by sliding / rotating them.

Write a program / function that solves the Topspin puzzle from a scrambled to ordered state.

## Input:

The input is a list of the numbered scrambled pieces, in any convenient format. For example:

10 18 12 11 7 2 3 4 6 9 15 19 14 17 1 8 13 5 20 16

You can use 0-indexing, just mention it.

## Output:

The output is a list of moves that solve the puzzle. You a free to chose a notation which suits your language / algorithm. Possible notation:

• 0 - rotate the turntable
• 1 - slide all pieces to the left
• 2 - slide all pieces to the right

or:

• t - rotate the turntable
• l - slide all pieces to the left
• r - slide all pieces to the right

Since the pieces form a loop it is NOT necessary to shift the pieces in the final solution so that the lists starts at 1.

So the output should look something like this:

011022201... and so on

or

tllltltrrt...

Test cases:

14 1 9 10 17 15 13 18 16 6 12 19 2 11 20 4 7 8 5 3 3 4 18 1 5 13 14 8 2 16 10 12 15 9 7 17 20 11 6 19 6 16 5 13 14 17 11 8 10 7 4 3 15 1 18 9 20 12 19 2

You can use this script to generate more scrambled sequences: Try it online!

You can check your solution with this script: Try it online!

(a is 1-indexed list of the scrambled pieces, b is the solution in notation - 1 - slide to left, 2 - slide to right, 3 - turn )

## Winning criteria:

This is , so the shorest solutions in bytes in each language win. Please explain you algorithm!

• Unless I'm missing something, there's no requirement that the solution be the shortest possible, so two moves are sufficient, and it will probably give shorter code to only use two. There's also no requirement that the program finish in any finite limit. Are both of these intentional? May 14 '18 at 14:53
• @Peter Taylor Thank you for your feedback! No, they are not intentional, but my omission. In fact I was wondering how to add the length of the solution (multiplied by some coefficient < 1) to the length of the code and make the total score. I'm open for any suggestions. May 14 '18 at 18:00
• can the output notation be code?
– l4m2
May 15 '18 at 9:29
• @l4m2 I'm not sure what you mean. Can you show/explain? May 15 '18 at 10:09
• Combining two elements to give a single score is usually tricky. GAP finds a solution for 2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 of length 183, so bubble sort should be able to solve an arbitrary permutation in (modulo out-by-one errors) at most 19*10+19*18/2*183 = 31483 moves. Might be worth downloading GAP and seeing what it finds for random permutations, or even whether GrowthFunctionOfGroup completes in a reasonable time. May 16 '18 at 11:39
• @Peter Taylor Thanks! I don't have any experience with GAP, although I have it installed on my computer. I'll give it a try. May 16 '18 at 13:17
• I would just try a bozo sort (and hope it works) if this question does not include the requirements of size of the solution...
– tsh
May 18 '18 at 8:10
• @tsh This is exactly how most people try to solve puzzles :) I think I need to add a requirement that the solution should be reachable in reasonable time. May 18 '18 at 8:29

The following is an idea I hope to eventually make into a full king of the hill. I've never written or participated in a king of the hill so help would be appreciated.

Here is how this is going to work. You are going to be able to write the brain behind a bot. Your bot will have a limited amount of energy to work with. It won't have to expend energy to move around normally, however every time it moves while carrying something it will expend 1 unit of energy. When your bot hits zero energy it won't be able to move any longer and will die have to take a nap.

The goal is to make bots that will take agar from sources to their corresponding goals. However the sources and goals will be too far apart for a single bot to carry a piece of agar all by themselves so you will need to work with other bots to achieve your goals.

## Specifics

### The course

The course will likely be a square grid of yet determined size. On the south and east ends will be sources of agar, which will replenish as it is drained by the bots. On the north and west ends will be goals. Agar placed in the goal will disappear. Agar from the east source should be placed in the west goal and agar from the south source in the north goal.

### The bots

Each player will be given control of 1 bot. Bots will be implemented as a rather simple state-machine. You will implement your bot as a function that takes inputs and produces outputs. At each step of the program a the bot will receive the following pieces of information:

• Whether each of the four squares adjacent to it is inside our outside of the arena.

• Whether there is agar in each of the four squares adjacent to it, and the square it is in.

• Whether there is another bot in each of the four squares adjacent to it.

• Whether it is carrying agar currently.

• How much energy it has remaining.

• An additional 2 bit state, to be explained.

From those inputs the bot will produce two outputs:

• An action, which is either a direction to move, picking up agar, or placing agar back on the ground.

• A 2 bit state to be passed on to your bot at the next step.

The 2 bit state acts as your bot's memory. It's not a lot so you should use it wisely.

### Movement

Your bot has pretty free movement. It can move into any empty space. However there are two limits on movement.

• You may not move outside of the course

• You may not move into a space that has agar if you are carrying agar.

I am not yet sure how I will handle bot collisions.

### Carrying

Your bots can carry agar. They can only carry one piece of agar at a time. To pick up agar a bot must be standing where the agar is located and perform a pick up action. Placing agar works in much the same way. If a bot is carrying agar they may perform a place action to put the agar down where they stand. Placed agar will remain there until a bot picks it up and moves it. Picking up and placing agar does not cost energy, however moving while holding agar does cost a unit of energy for every movement.

### Scoring

Scoring is still up in the air, once I have a working controller I will finalize scoring aspects. That being said thoughts, questions and suggestions are more than welcome.

Each piece of agar will remember which bots helped move it and how many steps they took. Upon being put into the correct goal agar will award every bot 1 point for every step they took while holding the agar. Agar left on the field or put in an incorrect goal will award no points.

More points is better.

I'm not sure how koth scoring usually works overall so you guys might want to help me with that.

## Controller

Once I have the idea down I will start to write a controller. I may need some help from people more experienced in koths in getting the basics down.

I intend to write the controller in elm because I like functional programming and I would like the controller to be runnable from in browser. Answerers will not have to write in elm they will instead write in a toy language I have yet to write the specifics for.

• A few points, all related to a particular event/strategy: 1) Do bots pick up/put down agar in any adjacent square, or specifically on their current square? 2) If a bot picks up then puts down agar without moving in between, does that use energy? 3) Mostly dependent on 1, but if a bot picks up agar and puts it down somewhere else, does that count for scoring even if the bot itself didn't move in between? Apr 20 '18 at 18:59
• @KamilDrakari Bots must stand on agar to pick it up, and placed agar will appear where they stand when they place it.
– Wheat Wizard Mod
Apr 20 '18 at 19:00
• Since you're passing the state with every function call anyways, you could also run each bot as a single process which would allow people to participate in any language of their choice. I once planned a KOTH (which has some copyright issues and I can't post it) and wrote a Python framework, if you're interested I'd share it. Basically it creates a new process for each bot and controller-bot communication works via pipes, st. the bot can just read stdin and write to stdout. This would probably attract more participants than forcing a language. Apr 21 '18 at 12:32
• @BMO The main reason I am using purescript is that it is runnable in browser. I could definitely make this language agnostic but I would have to make it into a desktop application. I'd greatly prefer a challenge that can be run in browser. In addition purescript's pattern matching makes it so you don't really have to know purescript to write a working bot. I can easily write a form that can be filled out to make a bot.
– Wheat Wizard Mod
Apr 21 '18 at 14:58
• Ah, yes that makes sense that people are able to run it in a browser. I've never used purescript but it seems like a nice language. I'm not sure though if people would be willing to get involved with it (not everyone is comfortable with strong type systems), however it seems like there are a lot of people that know JavaScript. So it's probably a good choice for a KOTH. Apr 21 '18 at 15:31

# What a hat at wheat!

Given a word, remove letters one at a time until nothing is left. Output the list of steps.

Example:

 wheat
what or heat
hat or eat
at or ha
a


All words must exist in a word list, but this list may be provided via any means, such as in a file with a specific name, or in a global variable, or built-in to the language, as long as it's a list of words and not some custom data structure. You can however require that the list is pre-sorted in a specific order (in which case you should also provide a suitable sort function, which can be in any language).

If there is more than one solution then you can return any one or all solutions. If there are no solutions then you should return a falsy value. You can assume that the input is taken from the word list. You don't need to return the original input or the empty string as part of the solution.

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

• Heavily-downvoted dupe. May 24 '18 at 9:16
• Technically the other one is not a duplicate target because a <Jelly> solution for this one can't be "easily" ported there... May 24 '18 at 9:17
• @user202729 Yeah, the reason it's heavily downvoted is that it restricts to 4 languages. May 24 '18 at 9:21
• I'd like the word list to be provided as an argument. Otherwise this is a good challenge, and a good dupe target to close the other one. Feb 2 '19 at 1:40

# Softcode, take 2

Softcoding is an anti-pattern defined by “the practice of removing ‘things that should be in source code’ from source code and placing them in some external resource”, which usually are config files, database entries, or both. “At the extreme end, soft-coded programs develop their own poorly designed and implemented scripting languages”, as can be seen by one of the most egregious examples of the practice, the Enterprise Rules Engine.

Thus, programmers who fall to the habit of softcoding, after tons of work, find themselves at the very point they were starting from: they have developed “some sort of COmmon Business-Oriented Language that’s generic enough to code any rule”. But unfortunately for them, there already is such a thing. “It’s called C++. And Java. And C#. And Basic. And, dare I say, COBOL.

For the sources of the above quotations are more information of the practise, see: Soft Coding on The Daily WTF, Softcoding on Wikipedia and The Enterprise Rules Engine on The Daily WTF.

# The Challenge

Softcode! Make an actual, Turing-complete language that will reside in config files!

More specifically, you should write a compiler / interpreter / anything in between that will define a Turing-complete programming language, whose every valid source code will also be a valid JSON file. (The reason why JSON has been chosen is the simplicity of syntax and wide avalability of JSON parsers, so that you won't have to write a parser yourself.)

Input/output format of your JSON language is up to you.

Shortest interpreter / compiler code wins, as long as it implements a Turing-complete language.

# Technical details

Unfortunately, given how this challenge is defined, I must put one arbitrary restriction: If your language of choice supports calling a compiler or interpreter of any Turing-complete language, I must disallow doing that. Otherwise, this challenge would likely degrade to calling eval on a single property name of your JSON input file.

However, not to burden you with writing JSON parsers, you may use third-party libraries, as long as they're freely available. (Otherwise, good ol' C++ would be a nightmare without Boost.)

Be creative.

# Example interpreter

For reference, below is a simple JS interpreter of a Turing-complete JSON programming language. Of course, this code is ungolfed. (I hope there are no bugs in this interpreter, but I don't feel like testing it now.)

importPackage(java.io);
importPackage(java.lang);

// This interpreter implements GOTO-programs, which are Turing-complete.

var prog = JSON.parse(progsrc).prog;

var vars = {};

for(var i = 0; i < prog.length; i++) {
switch(prog[i].command) {
vars[prog[i].varname] = vars[prog[i].varname] || 0;
vars[prog[i].varname] += prog[i].constant;
break;
case 'SUBSTRACT':
vars[prog[i].varname] = vars[prog[i].varname] || 0;
vars[prog[i].varname] -= prog[i].constant;
break;
case 'GOTO':
i = prog[i].index-1;
break;
case 'IF':
vars[prog[i].varname] = vars[prog[i].varname] || 0;
if(vars[prog[i].varname] == prog[i].constant) {
i = prog[i].index-1;
}
break;
case 'HALT':
i = prog.length;
break;
}
}

vars.out = vars.out || 0;
print(vars.out);

• You realize that allowing eval make the challenge trivial. Good. Now you don't allow eval, we just need to implement it. The challenge degrades to "implement the 'eval' function for any Turing-complete language". Not good at all. May 27 '18 at 10:00
• Looks like that it's very difficult for you to write a well-received challenge. It's unfortunate... May 27 '18 at 10:05
• @user202729 You May Not Call Any Already-Existant Compiler Nor Interpreter For Any Turing-Complete Language, is this OK? How are you going to "implement eval" with such a requirement? May 27 '18 at 10:28
• Just reimplement it. For some simple language, e.g., BF. May 27 '18 at 11:11
• @user202729 How is implementing BF going to be shorter (in bytes) than, say, GOTO-programs, WHILE-programs or lambda calculus? BF has 8 instructions, you can do GOTO with 2 May 27 '18 at 11:17
• @user202729 Besides, writing a BF interpreter is an interesting golfing challenge on its own. Figuring out which language will allow a shortest interpreter just adds more depth. May 27 '18 at 11:34
• My point is, this challenge degrades to "interpret any TC language", and the "soft code" part doesn't make the problem significantly different. May 27 '18 at 11:53
• And would probably be closed as duplicate of this. May 27 '18 at 13:58
• @user202729, or closed as "Too broad", as that question also should be. May 29 '18 at 13:39

# Othello Greedy Strategy

The rules for Othello can be found here.

In a greedy strategy, in each go, you just choose a square in which to place your counter such that there are no other places that could allow you to flip more counters. However, there is still often a choice where you need to decide where to put your counter.

Given an integer N as input, when black goes first and both players follow a greedy strategy, output a possible configuration of counters at the end of the game where there are N black counters. Assume that there exists a configuration for N.

Output should be a 64-character string, where the (r-1)*8+1th to r*8th characters (inclusive) represent the rth row from left to right.

I'll add test cases if people think that this is a good challenge.

• I think the core of the challenge is interesting (Implementing Othello rules). However, I think a better way to present it is to give them a board, and have them output a greedy move. May 31 '18 at 14:33
• I think you should add the rules in your post (challenges should be self-contained) Jun 1 '18 at 7:30
• Although the challenge is interrsting, I have no idea how can I solve this in a teasonable time. NathanMerrill's suggestionis better. Jun 2 '18 at 7:24

# Array-of-arrays string conversion

Matrix challenges are popular. There's an issue of how to provide test cases. A common method is the row-wise array-of-arrays representation, such as:

[[1,2],[3,4],[5,6]] -> a 3 by 2 matrix


This is good with vertical space, but there's always the task of converting the test cases into something your language can use, and vice versa for producing test cases to this format.

So this is a challenge and also a repository of conversion functions that people can use when trying or composing matrix challenges.

## Defining the format

A row string of length m is a comma-separated list of m ≥ 1 numbers, enclosed in square brackets.

A row-wise n×m array-of-arrays string is a comma-separated list of n ≥ 1 row strings of length m enclosed in square brackets.

There can be no leading whitespace. One trailing newline immediately after the final ] is optional. Otherwise any whitespace in the string is optional.

## The challenge

Produce two* programs/functions in your language:

1. one which takes a rowwise n×m array-of-arrays string as an input, and outputs the matrix (as implemented in the language.)

2. another one which takes an n×m matrix (as implemented in the language) as an input and outputs the rowwise n×m array-of-arrays string.

*It is allowed for one program/function to perform both tasks and you can have helper code used by both conversion functions.

## Rules

• To be clear: the language must support matrices (or something equivalent like 2D arrays - the name is not important) because the output/input of the two tasks needs to be an actual matrix in the language.
• This is .
• Fewest total number of bytes (from all functions and any helper code) in each language wins.
• If one program or function does both conversions, only count those bytes once.
• Standard rules apply/loopholes forbidden.

Here's the Sandbox and a related question.

• – ngm
May 30 '18 at 18:54
• I'm not sure if I need to explicitly mention the case where the string as defined is already a valid matrix or expression in some language. And if I do need to mention this case, I don't know what the best terminology to use might be.
– ngm
May 31 '18 at 15:08
• Thank you for all your input. I will leave it in the sandbox for another day or two in case other issues arise.
– ngm
May 31 '18 at 16:59
• @Adám I've removed "expression" from the question.
– ngm
Jun 1 '18 at 13:48
– ngm
Jun 1 '18 at 13:48
• I think this one is ready to post.
Jun 20 '18 at 11:08
• I posted it here but it was closed due to lack of clarity, and I did not make any further attempts to address the concerns due to lack of spare time at that moment. I would be open to trying again.
– ngm
Jun 20 '18 at 15:48

## A sort of cyclic program to string together

Write a program that sorts a string.

However, it does some other things too:

1. When given a non-sorted string (that is not your source code), outputs the string in non-descending ASCII code order, as expected.
2. When given a sorted string, outputs your program's source code but sorted.
3. When given your source code but sorted, outputs the original source code.
4. When given your source code (not sorted), outputs any nonempty string that is none of the above outputs
• i.e. Your program cannot output a sorted string and therefore must be at least two characters, and it cannot output your original source code

As a result, consider input string -> output string. If you're starting with any non source code unsorted string:

• The program will start with given unsorted string -> given string sorted. This sorted string can then be input to your program again resulting in given string sorted -> source code sorted
• If you continue to inputting what the program produced as output, it will then cycle through source code sorted -> source code -> chosen unsorted string -> chosen string sorted -> source code sorted.

## Example

Let your program be foobar. Consider the following examples:

-- Case 1 (unsorted string -> sorted string) --

Input:  Programming Puzzles & Code Golf

Input:
This is an unsorted string
Hey look a newline
Output:

-- Case 2 (sorted string -> sorted source code) --

Input:  123ABCDabcd
Output: abfoor

Output: abfoor

Input:  a
Output: abfoor

-- Case 3 (sorted source code -> unsorted source code) --

Input:  abfoor
Output: foobar

-- Case 4 (unsorted source code -> unsorted string) --

Input:  foobar
Output: a1


Using the last example, if your program outputs a1 as your chosen string, then it will continue to cycle through a1 -> 1a -> abfoor -> foobar -> a1.

## Specifications

• Input and output are both strings
• Your source code can't already be in sorted order since there are two different actions depending on whether or not it is sorted
• Standard I/O methods apply and standard loopholes forbidden
• This is code golf so shortest answer in bytes wins

## Sandbox

Usually I have some sort of solution for a challenge but I have absolutely no idea how to go about doing this. I liked the idea though and wanted to know if it's original and if it's clear enough.

# Intro to both

Pseudorandom number generators are used for simulation and security. While most are appropriate for games and simulations (appropriateness depends on statistical properties), only a select few algorithms are appropriate for security because most of the others are too predictable and can introduce severe vulnerabilities. This challenge should (hopefully) demonstrate how easily some algorithms can be cracked and why the choice of RNG algorithm matters for security.

# Cops

Choose/implement/create a pseudorandom number generator, seed it with a constant state, generate the first 10,000 32-bit unsigned integers, and link to it from your post. The robbers will be trying to make a program that generates the same sequence.

• The total number of bits of state used by the generator. For example the well-known Mersenne Twister has 19,937 bits of state.
• Note that if you're using multiple RNG algorithms together, you will have to show the combined count of bits of state.
• Any randomness used to seed the generator does not count toward this value, though the seed must be constant.
• A link to the generated sequence of 32-bit unsigned integers

DO NOT post the source code of your generator. That's what the robbers are trying to figure out.

A submission is considered "cracked" if a robber has made a program that generates the exact same sequence. Therefore it is necessary that a robber determine not only the algorithm, but also the initial state of your generator

## "Bits of State" Explanation

Every random number generator has a state that is used to determine the next number in the sequence and every number thereafter. Each time a number is used, the state is convoluted in some way and a random number is emitted. The minimum number of binary bits required to store this state will be your "bits of state" count. If you were using a 32-bit linear congruential generator, you would have 32 bits of state. If you were using an LCG with a modulus of 123,456,789, you would have 27 bits of state because 27 bits is the minimum number of bits required to represent every integer between 0 and 123,456,788, inclusive, even if such a state would actually be stored on a 32-bit integer.

## Rules and Scoring

• All state must be self-contained within your generator and your program should generate the exact same sequence every time it is run.
• You may not use any external sources of entropy, including uninitialized memory, wall time, input, atmospheric noise, network latency, etc...
• If using an existing algorithm, you will need to make sure to do your research to ensure that the generator meets the above requirements. You may need to seed it manually to ensure that.
• There are no statistical restrictions on your sequence: it does not have to pass any statistical tests and can fit any distribution you would like, so long as it fits within the range of an unsigned 32-bit integer.
• The source code to the program used to generate your sequence cannot be larger than 4 KB.
• A submission that has not been cracked in 168 hours (1 week) will be considered "safe".
• The "safe" submission with the fewest number of bits of state is the winner.

# Robbers

Choose a Cop submission from the other thread (link) and crack its random number generator. It will be considered cracked if you can recreate the sequence exactly.

## Rules and Scoring

• Hard-coding the sequence is not allowed.
• Your program is limited to 4KB
• Your generator does not need to have the same state size as long as it generates the same sequence. In practice, this will be necessary unless the RNG used is a really bad algorithm.
• For each successful crack of a not-yet-safe random number sequence, you will score points according to the number of bits of state used by the generator:
• 1-32 bits: 1 point
• 33-128 bits: 2 points
• 129-1024 bits: 3 points
• 1025-8192 bits: 5 points
• 8193-65536 bits: 8 points
• More than 65536 bits: 13 points
• How would one link a black-box function?
– Jo King Mod
Jun 5 '18 at 3:16
• @JoKing I'm not quite sure how this is supposed to work. I'm going to have to read up on c&r challenges. Jun 5 '18 at 14:58
• Can you give an objective definition of "non-cryptographically-secure PRNG algorithm"? Jun 6 '18 at 8:53
• It seems the algprithm itself can use the seed xor-ed, so giving seed known is useless; but then it's quite bad
– l4m2
Jun 6 '18 at 11:22
• @l4m2 That's a good point Jun 6 '18 at 15:53
• How do "bits of state" work?
– l4m2
Jun 6 '18 at 17:51
• "A submission is considered "cracked" if a robber has made a program that generates the exact same sequence. Therefore it is necessary that a robber determine not only the algorithm, but also the initial state of your generator" I don't think so. As I read the question, the robber's generator only has to agree with the cop's for the first 320000 bits output, but unlike the cop the robber has no size limit, so they can hard-code the full 320000 bits. "Hard-coding the sequence is not allowed" is not an objective restriction. Jun 7 '18 at 8:22
• Cop: have an n-bit counter, take the kth byte of sha(MAGIC + counter++). n=12 if you want to bet that the robber can't compress the stream at all; otherwise n=13. The existence of crypto breaks most C&R ideas, but excluding it objectively is tough, and IMO this is a fairly fundamental problem with C&R. Jun 8 '18 at 19:53
• @PeterTaylor That's actually a good point there. I hadn't thought of using a salted hash. That is a trivial "RNG" algorithm that is pretty much unbreakable. I could hard-ban crypto, but there's no way of verifying that and I already have enough on the honor system for cops. sigh Jun 8 '18 at 20:28
• There is some sense in which RNG is crypto: a seedable RNG can be used as a stream cipher, although it might not be a good one. Jun 8 '18 at 21:41
• So a 1-in-3 and a 1-in-5 is 4 bit or 5 bit?
– l4m2
Jun 13 '18 at 18:28
• @l4m2 I'm not sure what you mean Jun 14 '18 at 20:05
• Having posted and edited to just contain a link, you can also delete. Jun 13 '18 at 11:09

# Add least char to match

Given a string, add at least chars to make the whole string match the given regexp. You can assume it's possible. If there are more than one solution, output a (not necessary uniform) random one.

Here regexp may contain:

|  or
() group
?  possibly not appear
*  may appear for any times. Maybe different in each match
0
1


Samples

0100      (01)*         010101
0         (0|1)(0|1)    00; 01; 10 (any should possibly appear)
1010      ((0|1)(0|1))* 1010
101       ((0|1)(0|1))* 1010; 1011; 1001; 0101; 1101

• Suggested question text for first para: "Given a string of 0s and 1s, and a regexp: add the minimum number of characters (0s and 1s) that makes the whole string match the given regexp. You can assume that this is possible. If there are multiple solutions of the same length, output any one of them." (This is meant to be a rewording of the same conditions, let me know if I've changed the task in some way with this wording.) Jun 16 '18 at 12:10
• @sundar Well I did only implied that the string can only contain 0 and 1, 2) I required random, though it may leads to lots of quite strange solutions(generate one that fit, generate another string of same length, if not match return the sure one)
– l4m2
Jun 16 '18 at 12:13
• " I did only implied that the string can only contain 0 and 1, 2" <- Are you saying that 2 is also allowed? I don't understand what you're saying here. " I required random, though it may leads to lots of quite strange solutions" <- Can you explain what you mean by random here, exactly? Your sample test case says "any should possibly appear", and that's what my proposed text says at the end ("not necessarily uniform random" seems to be a complicated way of saying the same thing). Jun 16 '18 at 12:18
• 2) meant it's the second point. "output any of them" seems it can be determistic as the result is valid @sundar
– l4m2
Jun 16 '18 at 12:27

# Draw the Recamán's Sequence

Recamán's sequence (A005132) is a mathematical sequence, defined as such:

A(0) = 0
A(n) = A(n-1) - n if A(n-1) - n > 0 and is new, else
A(n) = A(n-1) + n


A pretty LaTex version of the above (might be more readable):

The first few terms are 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11

(Description of the sequence borrowed from this older question).

Your task is to animate the drawing this sequence as a series of semi-circles:

Where each entry above is a keyframe in the animation. Tween frames should draw the circle segment, and if necessary, scale the image down when the new locus would be out of frame.

After 600 terms of the sequence you should have something like this: (Image from this Numberphile video)

Your choice whether to draw horizontally, vertically, or diagonally, provided that the entire image fits within the image boundary. Line color can be any value, background can be any value (values must be distinct).

# Winner

• The program to generate the most terms of the sequence wins (before the program terminates, crashes, or otherwise corrupts the output--eg by exceeding file size limitations1).
• Tie will go to the shorter program.

# Rules

• Output image size shall be no smaller than 2048x2048, compiled as a gif, apng, common video format (e.g. mp4), or as an HTML or Javascript canvas (in-place animation).
• Segments should be drawn over 0.5 second intervals
• Frame Rate should be no slower than 24 frames/second
• (That is, each term of the sequence will take at least 12 frames to draw)
• You need not embed the entire output in your answer, although some means of showing off the results of your work is expected (sped up version, choice stills, etc).

1 If your program will happily produce files in excess of 128 MB (the 64 bit NTFS file system will allow up to 16 TB files), post an altered version of your program that terminates after approximately 128 MB to avoid trashing people's hard drives. You may score based on the unaltered bytecount. Do please post a still image of the final frame your program could otherwise produce (within reason: you not required to generate the entire animation in order to determine true termination). You may use a modified / separate program to produce this still, as it is purely for aesthetic and curiosity purposes.

• before the program terminates, crashes, or otherwise corrupts the output--eg by exceeding file size limitations ... Segments should be drawn over 0.5 second intervals. Frame Rate should be no slower than 24 frames/second These requirements are heavily dependent on the machine that one uses and therefore are difficult to measure objectively without a person testing every solution; i.e. you, the challenge poster, will have to run all submissions. Jun 19 '18 at 15:09
• That's a fair point. Jun 19 '18 at 15:21
• too many rules about time limits, output format, etc, imho Jul 7 '18 at 20:11

# American Checkers AKA English Draughts

This is a king of the hill challenge for checkers/draughts enthusiasts.

Note: All code below is written in F#

## Rules

For this game, I am using the rules from The American Checker Federation (Note: it tries to download a .doc file). The relevant rules are listed below.

Moving

Checkers move forward diagonally one square.
Kings move diagonally one square in any direction.

Capturing

Capturing is required in this variant.
Checkers jump forward diagonally two squares; they may only jump over an opponent's piece onto a blank square and continue jumping until there are no more pieces to jump, or until they reach the king row.

King jumps follow the same pattern as checkers jumps, but do not have the restriction on moving forward.

Winning

The game is won when one player has no more pieces or cannot make any more moves.

Draws

A draw is declared when the same position is reached three times or when neither player moves an unkinged checker for 40 moves and there are no captures in those forty moves.

## Play

Each program will take a list of the game history in the form of a PdnTurn list (Read about PDN notation here):

type PieceType = Checker | King
type PdnMove = { Move :int list; ResultingFen :string; DisplayString :string; PieceTypeMoved :PieceType Option }
type PdnTurn = { MoveNumber :int; BlackMove :PdnMove; WhiteMove :PdnMove Option }


It will return the data in the form of a list of ints, where each int represents a square on the board. That is, if you have a piece on square 1 and intend to jump to square 10 over a piece on square 6, your program will return [1; 10] (notation as an F# list). If any player returns an invalid move, they forfeit the game.

## Scoring

Each player will play three games against each opponent; each win will be scored as 1, each loss as 0, and each draw as 1/2. The loser of the match will be disqualified. At the end of the tournament, the player(s) with the highest score win.

## The Tournament (incomplete):

I set up a website at checkerstreasury.azurewebsites.net. Communication from the server to the player is done with SignalR preferring websockets (you can probably just use websockets without SignalR, but I don't know how). Communication from the player to the server is done with POST requests. I am at work now, but I will post the API and finalize this later.

This challenge feels incomplete; am I missing something?

Question: I have my own AI implemented alongside my controller. I intend on submitting this as a base submission, but will not award it the win even if it is the king of the hill. Should I include it in the question, or as an answer? If an answer, should I post it with the question, or wait a while?

• In the interests of the challenge being self-contained I'd suggest providing a summary of the rules that would be sufficient for people to complete it without relying on external resources. Feb 24 '18 at 21:22
– user10766
Feb 24 '18 at 23:04
• I think Mego has an identical koth? Let me check... Feb 25 '18 at 3:42
• Here. Feb 25 '18 at 3:43
• Thanks, @user202729.
– user10766
Feb 25 '18 at 4:17
• Do you intend to post this at some point? I might be interested to write a challenge and a language-agnostic controller (using STDIO and/or argv for I/O), but apparently you and Mego have both created a sandbox post on the same topic. May 25 '18 at 23:53
• I actually wrote a website for my checkers game over the last few weeks. I'm just working out a few more bugs before it is ready. It has an API for bots to tap in to, and all. Check it out at checkerstreasury.azurewebsites.net (note that steady activity playing the computer by a few users gets it rate-limited as I'm using the free option).
– user10766
May 26 '18 at 1:53
• Website "done". I'll finalize this soon!
– user10766
Aug 4 '18 at 22:36