# 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 requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

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

## Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

# Rob the King: Hexagonal Mazes

Consider the following hexagonal maze:

     E . \ . . .
. . . \ . \ .
. . . . \ . \ .
_ _ _ _ . \ . \ .
. / . . . . . . | .
. | . . _ _ _ _ / . .
. \ . \ . . . / . .
. \ . \ . . / . .
. \ . \ . . . .
. \ . \ / . .
. \ . | . X


E represents the entrance, X the exit. |_/\ are walls and . are free spaces. In order to navigate from E to X, we can move to any free space in the up to 6 immediately surrounding spaces. The path from E to X, marked with P is:

     E P \ P P P
. . P \ P \ P
. . . P \ P \ P
_ _ _ _ P \ P \ P
. / . . . P P P | P
. | . . _ _ _ _ / . P
. \ . \ . . . / . P
. \ . \ . . / . P
. \ . \ . . . P
. \ . \ / . P
. \ . | . X


This isn't the only path, but the others are trivial variations on it.

# Cops

You are to write a function in Python 3 which takes a positive integer $$\n \ge 2\$$ and returns a hexagonal maze of side-length $$\n\$$, as shown above. The maze will meet the following criteria:

• The only characters in the output are EX.|_\/, space and newline
• The hexagon is shown as a hexagon. That means:
• The first $$\n\$$ lines will have one more non-space character than the previous line (the first has $$\n\$$ non-space characters), separated by a single space, and offset from adjacent lines
• The first $$\n\$$ lines have one fewer leading space than the previous line (the first line has $$\n - 1\$$ leading spaces)
• The next $$\n - 1\$$ lines have one more leading space than the previous line
• The next $$\n - 1\$$ lines will have one fewer non-space character than the previous line, separated by a single space, and offset from adjacent lines
• Lines may not have trailing whitespace
• The E is the first non-space character on the first line, and the X is the last non-space character on the last line
• There is at least 1 valid path that connects the E and the X, only moving from one free space to an adjacent free space.

How your program generates these mazes is entirely up to you. It could randomly places walls in the grid, ensuring there is always at least one path left, or it could only block the center row except for one gap, or anything else.

You may return either a multi-line string, or a list of lines. Lines should have appropriate space padding at the start, and may have a consistent amount of trailing spaces. "Consistent" here means either the same number on each line, or padding each line to the same length.

The Robbers will be writing maze-solving programs that try to solve your mazes, so you should aim to generate mazes that are somewhat difficult to solve.

This is not , you are under no obligation to golf your submission.

Additionally, you may submit multiple submissions. You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified

Empty mazes of sizes $$\n = 2, 3, 4, 5, 6\$$:

                                                                 E . . . . .
E . . . .            . . . . . . .
E . . .          . . . . . .          . . . . . . . .
E . .        . . . . .        . . . . . . .        . . . . . . . . .
E .      . . . .      . . . . . .      . . . . . . . .      . . . . . . . . . .
. . .    . . . . .    . . . . . . .    . . . . . . . . .    . . . . . . . . . . .
. X      . . . .      . . . . . .      . . . . . . . .      . . . . . . . . . .
. . X        . . . . .        . . . . . . .        . . . . . . . . .
. . . X          . . . . . .          . . . . . . . .
. . . . X            . . . . . . .
. . . . . X


# Robbers

You are to write a Python 3 function that takes in the return value of a cop's answer. It may also take the number of sides, $$\n\$$, as an argument if you so wish. The input will only contain EX_|/\. and space, and newlines if inputting as a multiline string. It will either be a multiline string or a list of lines. Your function should handle both.

Your function should then output the maze with any valid path connecting the E and X using only connected free spaces. You may show the path with any character aside from EX_|/\., space or newline.

This is not , you are under no obligation to golf your submission.

Additionally, you may submit multiple submissions. You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified

## Scoring

The scoring will take the form of a round-robin, similar to challenges. Every cop will be paired up with every robber, and the following will happen with each pair:

• The controller will call the cop's function 5 times with $$\n = 2\$$ as an argument, saving each of the 5 mazes. The cop will have 1 minute to produce each maze
• It will then pass each maze to the robber to solve. The robber will have 1 minute per maze to produce a correct output.
• If all 5 mazes are correctly solved by the robber within 1 minute each, the controller goes again, but with $$\n = 3\$$, and so on, increasing the $$\n\$$ by one, until either:
• The robber fails to solve a maze within 1 minute
• The robber produces an incorrect solution to an input maze
• The cop fails to return a maze within 1 minute
• The cop returns a maze with no path

At this point, both the cop and the robber receive points equal to the highest $$\n\$$ that neither of them failed. If the cop failed, the robber receives an additional point, and if the robber failed, the cop receives an additional point instead.

If both the cop and the robber reach $$\n = 50\$$ without failing, they both receive $$\50\$$ points.

After all pairs have be run, the cop and robber with the most points are the respective winners

# Meta

• If you want to automate the scoring process, you might want to restrict the I/O further, e.g. only allow stdin/stdout as a hexagon-shaped multi-line string. (I'm suggesting stdio because I assume you want to allow different languages.) Looks interesting, though I have a slight feeling that a full Dijkstra impl in C will almost surely win as a robber. Apr 12, 2021 at 23:01
• @Bubbler Good point, I've updated the I/O to be stricter. Apr 12, 2021 at 23:22
• @Bubbler I've decided to limit it to Python 3 functions, as I was struggling to make a controller that would allow any language to compete Apr 23, 2021 at 15:49
• It's a minor thing, but maybe change E and X to A and B? It seems more logical that way Apr 24, 2021 at 15:52
• @pxeger I chose E and X as "entrance" and "exit" respectively, but I doubt it'll affect any solutions as opposed to A/B Apr 24, 2021 at 16:06

## Death-onacci sequence (WIP)

The traditional Fibonacci sequence grows forever:

0 1 1 2 3 5 8 13 21 ... 1,346,269 ...


and is given by this formula:

f(n) = f(n-1) + f(n-2)


where the initial numbers in the sequence are 0, 1.

However, there's a set of as-yet unnamed sequences, where a previous number 'dies' and is removed from the total.

For instance the sequence for the 5th death-onacci (m = 5) is given by

f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) - f(n-5)


And the first m-1 numbers is 0, followed by a single 1 (so for m=5 the sequence start 0 0 0 0 1)

Test cases:

Here are some test cases:

n f(n), m=3 f(n), m=4 f(n), m=5
0 0 0 0
1 0 0 0
2 1 0 0
3 1 1 0
4 2 1 1
5 2 2 1
6 3 4 2
7 3 6 4
8 4 11 8
9 4 19 14
10 5 32 27
11 5 56 51
12 6 96 96
13 6 165 180
14 7 285 340
15 7 490 640
16 8 844 1205
17 8 1454 2269
18 9 2503 4274
19 9 4311 8048
20 10 7424 15156
21 10 12784 28542
22 11 22016 53751
23 11 37913 101223
24 12 65289 190624
25 12 112434 358984
26 13 193620 676040
27 13 333430 1273120
28 14 574195 2397545
29 14 988811 4515065
30 15 1702816 8502786
31 15 2932392 16012476

You must write a function or program that takes one number M, and prints out the first 31 M-Death-onacci numbers. M will be a whole number larger than 0 and less than 31. The output can be in any human readable format, and you can take input in any reasonable manner. (Command line arguments, function arguments, STDIN, etc.)

As usual, this is Code-golf, so standard loopholes apply and the shortest answer in bytes wins!

• Very similar. Apr 24, 2021 at 9:57
• @Razetime definitely, but hopefully different enough? Apr 24, 2021 at 10:02
• Well, it's a WIP. You can go ahead and add more details which distinguish it. 'tis the sandbox, after all. Apr 24, 2021 at 10:04
• @Razetime how's it looking now? Apr 24, 2021 at 10:23
• looks better, and the tests are more comprehensive. I suggest posting in TNB for other people's feedback. Apr 24, 2021 at 11:11
• taking P as a fraction seems fine, but it seems more convenient separately since we're just supposed to increment N and P till the desired ratio is achieved. What is the allowance for floating point errors on this question? Apr 24, 2021 at 10:07
• an additional "Streak bonus" for every x games might be an interesting addition. Apr 24, 2021 at 10:08
• @Razetime Oh did I say fraction, I meant a decimal value between 0 and 1, eg: 0.53 for 53%. There wont be more than two decimal places in the input so I doubt if any language will run into floating point errors at all. Apr 24, 2021 at 10:11
• I updated the question to allow P as decimal. About the streak bonus, I think it might complicate things quite a bit so I am not going with that. Apr 24, 2021 at 10:21
• You should clarify in the text if the inputs W, N can be taken separately or only as one number corresponding to W/N. And if so, please address Razetime's comment on floating point errors Apr 24, 2021 at 15:17
• @LuisMendo Yes, taking them separately is fine. I updated the post again, please check if it is clear now. Apr 24, 2021 at 15:47
• I'd suggest also allowing languages to take P as a fraction. Other than that, this looks good to go Apr 24, 2021 at 16:09
• I think they have to be taken separately. In the first example, if you take W/N as 0.2 you cannot compute the output, because you don't know if W=1, N=5, or W=2,N=10, or... Apr 24, 2021 at 17:32
• Oh yes, you're right about that. You'd have to consider both the values to calculate the answer. Apr 24, 2021 at 19:01
• @LuisMendo But if it somehow benefits you to take it say as a string of the form "W/N" with the original values of W and N, then that's fine too. I think the rules clarify that point. Apr 24, 2021 at 19:16

# Drawing the Stack Overflow logo

• I don't think restricting the language is a good idea. Move languages promotes diversity among submissions. However, I'm still new to the site so I'm not really sure. Apr 30, 2021 at 4:32
• Like Ender said, language-specific challenges are strongly discouraged - here, it doesn't add anything, so removing the restriction would improve the challenge by allowing a wider variety of approaches and solutions.
– hyper-neutrino Mod
Apr 30, 2021 at 4:34
• Also, seeing as to how this is a ascii-art challenge, you will need to either provide the exact text that needs to be outputted or a formal specification of what is considered valid output and what isn't - for example, could I just submit . and claim it's a very zoomed out logo? These will need to be clarified. Overall, I like the idea though.
– hyper-neutrino Mod
Apr 30, 2021 at 4:35
• I think if you require the output to be the exact example you gave it would make it much easier to determine which answers are valid. Apr 30, 2021 at 5:15
• @RedwolfPrograms It's the best I got, but I'll make it official. Apr 30, 2021 at 5:20
• This challenge looks pretty good now, so I've upvoted, although I'd still recommend waiting a day or two just in case anyone else has feedback on the formatting or finds something unclear. Apr 30, 2021 at 5:28
• A tip for future challenges: Anyone (not just you) reading the challenge and an answer should be able to decide (without disagreement) if the answer is valid or not. "Resembles a logo" is very subjective in this sense, and phrases like "as close as" should be avoided too. Apr 30, 2021 at 5:34
• @Bubbler Is this better? Apr 30, 2021 at 6:10
• Yeah, it's better. A question: would you allow printing trailing spaces at the end of each line, or printing a trailing newline at the end? (These are commonly allowed because they don't impact the ascii art shown and they're hard to avoid in multiple languages) Apr 30, 2021 at 6:21
• @Bubbler I added a list of questions that are asked in the comments. Can I add the same if I posted this on main? Apr 30, 2021 at 7:39
• I'd recommend to edit the challenge text directly to include any clarifications. Apr 30, 2021 at 7:45
• @Bubbler It will do and I'm hoping that when this gets published, I gain enough reputation just to talk in chat. Apr 30, 2021 at 7:50
• Tags-wise: [kolmogorov-complexity]. I'd suggest just removing the 2 paragraphs beneath the output, as they just make it more confusing. A simple "output this exact text, with an optional trailing newline. Lines may have optional trailing spaces. Shortest code wins" is enough (plus the output itself) Apr 30, 2021 at 17:35
• I've edited this down to a stub now that it's been posted to save space May 1, 2021 at 13:46

# Time bomb KoTH

• Enforcing determinism prevents luck based winning, which I personally like. Adds a sense of balance. May 1, 2021 at 15:59
• Determinism also means anyone can run a simulation of the game on their own machine. The game then devolves into aggressive metagaming and iteratively updating one's bots to always beat the opponents'. If you decide to enforce determinism among the bots, you must have some outside source of randomness to prevent players from simply simulating the entire game and instead actually formulate a strategy that is robust enough to still work well in the face of unknowns. May 2, 2021 at 9:57
• I personally like a bit of non determinism to spice things up but then this came along. So you have to be careful. May 2, 2021 at 9:58
• @EnderShadow8 yeah I saw that answer. In the current design, the array for the numbers selected in the previous round will be initialized with random numbers on the first round, giving the initial seed of randomness May 2, 2021 at 15:36
• Another thing to consider: high numbers will have very small winning chances, and the entire game is biased towards low numbers (they come first, they don't subtract much, large numbers take many points on explosion vs large numbers give many points on success). So all "smart" bots will choose <= n / 2 numbers, but then the trigger will also be lower, so bots have to choose even lower numbers. That can lead to a case of positive feedback. It may or may not cause problems, but it may be good to keep that in mind.
– FZs
May 2, 2021 at 19:24
• And to the determinism topic: a viable compromise between determinism and randomness could be made: making the only allowed non-deterministic part a seeded PRNG function provided by the controller. The PRNG seeds used for the official ranking are kept secret, but it's still possible to replicate the given match by using the same seed.
– FZs
May 2, 2021 at 19:58
• @FZs That's true. I may need to buff the reward for larger numbers to encourage playing them. Also about the determinism topic, after some searching I found some method to provide a seeded random, and I think I'm going to try that. May 3, 2021 at 7:41
• More about the determinism: I decided to decide the secret seed before the challenge starts and provide the hash to prove that I won't change the key mid-challenge. May 3, 2021 at 9:14
• I've edited this down to a stub now that it's been posted to save space May 3, 2021 at 14:17

# Count up to 21

21 is a game my teachers had my classmates and I play in order to kill some time. The game works as follows:

• All contestants stand in a circle. The aim is to count to 21, one by one.
• At any time, any player may begin the counting by saying 1.
• The plays then continue the counting by saying the next number. However, if multiple players say the number at the same time, the count resets, and someone has to say 1 again.
• The first player who says 21 is "out", and the game begins again with the same contestants except for the "out" player(s)
• The final player left is disqualified, and the entire game begins again. The last player not disqualified wins.

We are going to run a challenge, where bots aim to play this game.

You are to write a function in Python 3 that takes a list of lists $$\L\$$ as argument. Each list in $$\L\$$ represents a round in the game, with the last element being the most recent. The $$\i\$$th element of each list always corresponds to the same bot. Each list in $$\L\$$ will contain $$\n\$$ integers between $$\0\$$ and $$\21\$$, where $$\n\$$ is the number of contestants left in the game. The lists are either all $$\0\$$s, or are $$\n-1\$$ $$\0\$$s and a single non-zero value $$\v\$$.

If a list is all $$\0\$$s, either it is the first round, or the counter was reset in the previous round.

That function should then return either:

• $$\0\$$, meaning that your bot stays quiet
• $$\v+1\$$, meaning that your bot is attempting to guess this round

And that's it!

The competition will work exactly as described above. The controller will run 100 games. Each game will works as follows:

• The first round begins with all $$\n\$$ contestants. They will count up to 21, eliminating each contestant as they count to 21, and resetting the count to 0. The final player left is then eliminated, and the next round with $$\n-1\$$ contestants is run. At the end, the final player left standing wins
• The player with the most wins after 100 games wins overall

You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified

If any game has more than 10000 rounds, it'll be terminated and no player will win.

## Example bot

This is Random:

import random

def bot(history):
return random.choice([0, max(history[-1]) + 1])

• Infinite loops might happen quite often Apr 28, 2021 at 1:51
• @RedwolfPrograms Put a limit of 10000 rounds per game Apr 28, 2021 at 20:32
• TNB Feedback link Apr 28, 2021 at 21:16
• So, if next number is 21: Is there any reason a bot will not to say 21 in that round?
– tsh
Apr 29, 2021 at 1:30
• I feel like someone's going to just add a bot to say every single number no matter what. Apr 29, 2021 at 10:54
• @tsh If multiple bots say 21, none of them win and the count resets Apr 29, 2021 at 11:51
• Can you post the code to run the game so we can test our bots? Apr 29, 2021 at 21:05
• @fasterthanlight I haven't written the controller yet, so no Apr 29, 2021 at 22:57
• but if i will lost their turn if i dont say 21, and the worst case is a tie if I say 21? So any reason I try to be silent?
– tsh
Apr 30, 2021 at 5:10
• Because there's no reason to not say 21, infinite loops are probably going to occur no matter what. You might want to consider adding a rule regarding this to prevent infinite loops (or if everyone but 1 says a number the bot who said 0 can be eliminated) Apr 30, 2021 at 12:44
• Just wondering, is saving state between different turns allowed? Or between rounds? Or between games? You also don't seem to distinguish between rounds and turns (i.e times when the count resets vs. opportunities to guess), which may cause confusion. Also, a suggestion: Maybe let each game have only a small subset of the bots as contestants, so that if there's that one bot who always says 21 as soon as possible, it would just harm itself rather than ruining the challenge. (Sorry for this long block of text.) May 4, 2021 at 3:42
• Interestingly, this is completely different from the game of 21 I know. May 23, 2021 at 15:57

# Reveal by Halves (in need of a better name)

Inspired by this: http://nolandc.com/smalljs/mouse_reveal/ (source).

• Takes a number $$\w\$$ and (assumed non-negative) integer $$\x\$$.
• Outputs an integer list with a length of $$\2^w\$$, initially filled with zeroes.
• For each number $$\n\$$ from $$\0\$$ to $$\w-1\$$ (inclusive), divide the list into sub-lists of size $$\2^n\$$, then increment all of the values in the sub-list that contains the index $$\x\$$.

## Examples

(with coordinates from left, 0 indexed, but your answer may have change these)

w=3, x=1
23110000

w=2, x=2
0021

w=3, x=5
00002311

w=4, x=4
1111432200000000

w=2, x=100
Do not need to handle (can do anything) because x is out of bounds


## Meta questions

• Are these tags fitting?
• Would this be better in one dimension? (like $$\3, 2\$$ returns 11320000) Edit: I've changed it to one dimension but I can revert if it makes it less interesting.
• Should $$\w\$$ or $$\2^w\$$ be the input?
• Is this a duplicate?
• My opinions on some meta questions. 1) I think one dimension would be better, the core of the challenge remains the same but the challenge itself becomes more "pure" which, in my opinion, is a good thing. 2) I'm a fan of flexible I/O, so if it were up to me I'd let people choose if they want $w$, $2^w$ or both as input. If you don't like this, both options are honestly fine. May 10, 2021 at 22:24

# I'm Lazy*: Top-left align my text

posted

• Definitely not too trivial for code golf
– qwr
Jun 2, 2021 at 14:20
• I think squash up could be its own challenge which has room for simplification. My thoughts being using a transposed grid of strings, which I guess can work for this challenge too
– qwr
Jun 2, 2021 at 14:21

# Demonstrate some advanced abstract algebra

• I think we should be able to define the types and values of S, rather than necessarily using integers. In that case, - and + would not (necessarily) be actual arithmetic negation and addition, so maybe they would have to be renamed to use other symbols (or just use function syntax f(a,b)?) May 31, 2021 at 8:50
• And do all 9 functions have to operate on the same set S? I think it could be more interesting if they didn't have to, but it might result in cheating/loopholes. Also, what does "uniquely exhibits" mean exactly? Demonstrates exactly one of the 9 properties? May 31, 2021 at 8:52
• In fact, I think people will just submit "addition, addition, multiplication, subtraction" for the first 4 at least, and I suspect they will almost always be the shortest option in most languages so it might not be very interesting as it is May 31, 2021 at 9:04
• Writing one program is hard enough. Writing 9 seems like a lot to ask. I think you could make a stripped down challenge using just commutativity and associativity. I barely known any abstract algebra. I think these varieties are called magmas?
– qwr
Jun 2, 2021 at 14:54
• Is this even possible with the surjectivity condition? You should provide an example of each program.
– qwr
Jun 2, 2021 at 14:57
• @qwr I don't have examples for each program, and even if I did, I wouldn't include them as that would just lead to people porting them into their own languages. Yes, I believe magma is the correct term for $*$ here. I'm not sure if this is possible, but I'd be surprised if it isn't. I've allowed for an answer to be a proof of impossibility however, on that off-chance. Jun 2, 2021 at 15:04
• Well it's more than a magma since you added more two more operators right
– qwr
Jun 2, 2021 at 15:18
• @qwr No, I believe a magma is just a pair, the binary operator and the set its closed on, no matter the additional operators defined on that set Jun 2, 2021 at 15:31
• This is a really cool problem. It is hard so I wouldn't be again having a separate "easy" version with just the main three: commutative/associative/distributive. Uniquely exhibiting those is already a nontrivial and neat challenge. I don't know if others would vote a dupe, but I'd def be in favor of having both. As is, I don't think the harder version will have a lot activity. But I do think an easier one would! Jun 13, 2021 at 1:18
• @AviFS I do actually have an easier version Sandboxed, where I think they're clearly separate enough to not be dupes. Jun 13, 2021 at 1:42

# Minimal distinct character quine

• This seems well specificed Jun 16, 2021 at 10:04
• distinct means different? Jun 19, 2021 at 10:01
• @math Yes (filler) Jun 19, 2021 at 10:30

# Full name quine

• Nice question but seems hard Jun 25, 2021 at 18:11
• i assume custom SBCS languages will have to output the full names of their characters when represented in unicode? Or should they output the name of the visual representation? Jun 28, 2021 at 6:20
• Full names represented in unicode. Jun 28, 2021 at 8:29

# r my Vyxal

• Needs more test-cases. Also, in the explanation you use spaces as though they're ignored, but that isn't mentioned in the description of the task itself. I'd suggest just saying that "all other characters" will be limited to ASCII letters only, for example?. Jul 4, 2021 at 7:47
• @pxeger In Vyxal, spaces are NOPs used to seperate stuff. In the subset I'm using, spaces are a function like everything else. I'll make that clearer, and add more testcases. Jul 4, 2021 at 8:15
• But I'm suggesting limiting the definition of what are functions to ASCII letters only to provide more golfing opportunities without having to handle edge cases that might occur because of spaces Jul 4, 2021 at 8:54
• @pxeger Ok. (filler) Jul 4, 2021 at 8:55
• It says that we can assume there will always be two values to pop, but one of the testcases is simply “1”. Is that something that we will have to account for? Jul 4, 2021 at 15:09
• @AaronMiller What I meant is, wherever there's a function, there will be two. I'll add that. Jul 4, 2021 at 19:58

# Extremely small data compressor

In 2014 Jarek Duda at Purdue University wrote a paper containing several ideas for encoding computer data, entitled “Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding". The paper is available at Cornell University Library’s ArXiv project: https://arxiv.org/abs/1311.2540

One of the many fascinating things about this paper is that it begins by describing an extremely simple data compression algorithm, using the concept of the "Uniform asymmetric binary systems (uABS)". In fact, it is so simple, that you can implement it in only a few lines of code.

Basically it attempts to interpret a sequence of input symbols as a single Integer, and as each symbol comes in the Integer can be appended with new information. The trick is that the Integer is represented not using a place-value binary number system, but an alternative system. This representation is designed so that sequences of symbols which occur with higher probability will be represented by a smaller amount of space within the Integer's encoding.

## Challenge

You will implement the simple uABS compression algorithm, so that given a sequence of 0s and 1s, your program will compress them into a (usually) smaller sequence of 0s and 1s.

## Pseudocode

The algorithm in psuedocode is as follows:

• Begin with an Integer X, and set it to 1. This will be the main Integer that we append during the algorithm.
• The input data is a sequence of symbols, each 0 or 1, called Input
• Find the probability P that any given symbol in Input is 1, (the number of 1s divided by the total number of symbols)
• For each symbol S in Input, set X to the output of the function Encode(x,s,p)
• After processing all the input symbols, output the final integer X. -- This encoded integer will hopefully have less bits than the input

The Encode function itself can be described as follows:

$$Encode(x,s,p)= \left\{ \begin{array}{11} \mbox{if } s = 0 & \big\lceil\frac{x+1}{1-p}\big\rceil-1 \\ \mbox{if } s = 1 & \big\lfloor\frac{x}{p}\big\rfloor \end{array} \right.$$

Where

$$\begin{array}{11} s \text{ is a symbol, either 0 or 1} \\ x \text{ is the Integer} \\ p \text{ is the probability that any symbol in the Input data is 1 } \\ \lceil \rceil \text{ is the mathematical ceiling function } \\ \lfloor \rfloor \text{ is the mathematical floor function } \end{array}$$

## Notes

• The input is a sequence of symbols, each symbol being 0 or 1, in any method that is available in your chosen language. Examples include a sequence of ascii characters '0' '1', an array of integers, etc.

• The output will be a sequence of symbols in the same format as the input sequence. The output sequence represents the compressed version of the input data.

• Empty input data has undefined behavior.

• Input data containing only 0s has undefined behavior.

• Sometimes the encoded Integer might have more bits than the input, not less. This typically happens when the number of 1s and 0s is relatively even. Data with an unbalanced number of 0s and 1s results in better compression.

• You may assume that the size of Integer will be your language's largest integer type. The test cases outside this range can be ignored for your language.

• Note that if you are trying to test this by 'decoding' or 'decompressing' the compressed data, and compare it to the original, one would have to store additional information, such as the length of input and probability P, but for simplicity this has been left out of the challenge.

## Example Input and Output

Short examples:

Input             Output
10                101
10010100000       1011101001
1111              1
11111111111       1
10000000          11011
10011111010101    10110000100101


Longer examples:

Input  11111110110111110111111111011111
Output 11111000011110110

Input  000000000001000000010000000000001100000000001
Output 1110000101100111000011111

Input  000000000001000000010000000000001100000000001000000000000000000000000000000000000000000000000000000000000000001
Output 1010100110111110010111011110110101010


## Scoring

• The program with the fewest number of characters wins.
• 1. IMO the pseudocode could be made clearer by firstly explaining what "machine integer" means (does it mean "unbounded integer" aka "big integer"?) and secondly golfing it a bit: using a "foreach" loop notation for S and eliminating the variable X'. 2. I think it would be helpful to be explicit about how p should be derived from the input. I presume that it means looping over the input twice, once to count and once to compress. 3. IMO restricting the input format to strings of ASCII 0 and 1 detracts from the core challenge. Why not allow arrays/lists of integers? Jul 7, 2018 at 12:13
• Thanks, i have revised. Jul 7, 2018 at 14:08
• I really like this one. Something quasi-practical, and yet simple and small enough to be fun. Just to be clear, the output is the binary representation fo the integer X, without any leading zeros, correct? Jul 8, 2018 at 19:02
• Also, you mention "input size of at least 128 symbols", but it might be more important to specify output size limit, since many languages have hard bounds on maximum integer size. Since output size varies for the same input length, it might have to be something like "you may assume that the number of symbols in the output is less than or equal to the number of bits in your language's largest integer type". (The last test case would then be optional in languages that can handle only up to 32 bit integers). Jul 8, 2018 at 19:12
• yes the output is the binary representation of the final integer X, i believe the leading zeros is correct. do you think 32 bit is the good limit or 64, since modern machines tend to be 64 bit? thanks Jul 8, 2018 at 20:05
• 32 is probably a reasonable limit, one that most languages can handle without need for external libraries. Jul 14, 2018 at 14:22
• @sunar thanks, i have updated. Dec 29, 2018 at 14:21
• I assume the intent is for P to be calculated as # of '1' in the input / # of symbols in the input? That seems like it would match the definition given, but it would be helpful if it's described explicitly. Jan 3, 2019 at 22:24
• Done, thanks.... Jan 3, 2019 at 23:32

# Alphabet Reconstruction

• Fairly similar Oct 17, 2021 at 11:00
• @Dingus but mine is better :P I'll give this some thought and if I can't think of a new spin to put on this ill just delete it cause its a dupe. Thank you! Oct 17, 2021 at 16:06
• @Dingus hope this changes it enough. Flipped it on its head :D Oct 18, 2021 at 13:20
• I certainly like the new story better! I found it a bit confusing that the first example has the unordered letters first in the output; the significance of 'any given wordlist may have more than one proper alphabet' hadn't sunk in. I'd suggest expanding on this point under one of the earlier subheadings. Oct 19, 2021 at 0:55
• For the printable characters, perhaps specify ASCII 33-126? But I'd actually suggest restricting it to only alphabetic (A-Za-z) characters instead. Handling ^ or $ (for instance) doesn't really add anything to the challenge but will complicate any regex-based solutions. Oct 19, 2021 at 0:55 • @Dingus noted! ill think abt how to word the "more than one proper alphabet" bit, and once i figure it out ill make both edits :) thank you for your help Oct 19, 2021 at 2:02 • @Dingus does this clarify the multiple valid options thing? also, do you think I should include every valid output for the Cod Com Dy example? Oct 19, 2021 at 13:14 • Nice, it's crystal clear now. The only other suggestion I'd make is to consider deferring to the default I/O formats instead of stipulating space/newline delimited strings. At the least, taking input as a list of strings seems fairly natural, as does outputting a list of characters. Oct 19, 2021 at 23:11 • @Dingus ah, it was some weird holdover. What exactly should I write, "May take input and output in any reasonable format"? Oct 20, 2021 at 0:05 • Yep sounds good. Oct 20, 2021 at 1:06 • @Dingus great :) im at +3 so ill ask chat for feedback and unless theres any objections, i think ill post it :] Oct 20, 2021 at 2:15 ## Play RPS with 3 bits of memory This is a rough draft for now, the specifics, presentation and title will probably be adjusted In this game you will be building bots to play rock paper scissors against each other. Of course rock paper scissors is not a very interesting game, just pick one of the three randomly. Can't get better than that? The first thing here is that, we will play a slight variation on the game which introduces a small amount of strategy. But more importantly in this version we will be designing very simple bots. Your bot will not be able to pick things randomly, nor will it be able to simulate complex strategies, because your bots will have 3 bits of working memory. ## The game Before we get into exactly how the bots will be made and what exactly it means to have only 3 bits of memory lets cover the game. For each pair of bots we will play 48 rounds of RPS. In each round both bots will select a choice of Rock, Paper or Scissors. Rock beats scissors, paper beats rock and Scissors beats paper, if the two chose the same move they tie. When you win you will receive points based on your play. If you win with scissors you get 1 point, if you win with paper you get 3 points, and if you win with rock you get 6 points. If you tie or lose you get 0 points. Each bot will play every other bot and the bots will be scored on the number of points gained in total. ## The bots Your bot will have 3 bits of working memory, that means at any given time it will have stored a number between 0 and 7. To decide what to play it will know two things 1. What it has in memory 2. The last move it's opponent made Given those it should spit out 1. What move it wants to make 2. 3-bits to write into memory This is so simple you don't actually need to write "code" to represent your bot. Your bot is really just a $$\8\times 3\$$ lookup table, plus a single move which it will make as it's first move. (We can assume that the starting memory is 0 without loss of generality) And in fact you will submit your bots in this format as it makes it easy to verify your bot works and doesn't cheat. ## Sandbox I like this challenge because it is 1. Completely deterministic who wins, to the point where you can, for small bot pool work out with pen and paper the scores. 2. It is basically language agnostic. No need to bother with JS. 3. There's basically no way to cheat. It's going to be really hard to exploit a vulnerability in the handler when you can't run arbitrary code. I am a little concerned though that there might not be a whole lot to do? I'm not sure how much better one bot really can be than others. Obviously you can always take 1 bot and design a bot which plays perfectly against it. But I'm not totally sure how much a carefully arranged bot is going to do better than ones that are just a pile of random connections. Turning the memory size up could improve this but the larger you make it the more complex each bot gets, and I think the fun is really in being able to hand tune your bot. However I don't know what I can do to find out other than just post this. • Seems bruteforceable Oct 17, 2021 at 18:40 • This is a unique challenge, and I think you could post it. If it doesn't work out, then we'll all know not to do it again (or an improved version could be posted later). If it does work, CGCC'll have a new kind of challenge, which would be great. – user Oct 17, 2021 at 18:57 • @pxeger There are 1333735776850284124449081472843776 machines possible. Brute forcing that would probably mean playing every machine against every other machine. It may be solvable, but I don't think it is feasible to brute force it. – Wheat Wizard Mod Oct 17, 2021 at 21:15 • I'd prefer to have rigid I/O (fixed I/O method and format) for KotH purposes. Or you could just say "write down the 8x3+1 possible outputs in a specific format". The barrier to post some bot looks pretty low, so I'd expect a large number of answers in the worst(?) case which would require some kind of automated controller. Oct 18, 2021 at 1:13 • @WheatWitch ah, I misread the challenge Oct 18, 2021 at 6:59 • @bubbler oh I absolutely will write a controller once the rules are nailed down a bit. Just because you can score this by hand does not mean it would not be very tedious – Wheat Wizard Mod Oct 18, 2021 at 7:40 # Remove submatrices # Solve the halting problem for ^/a*b*/b*a*/[ab]*$ in /// code-golf

///, a.k.a. Slashes is an esoteric programming language with simple two operations. One is to output its source to remove from it. The other is to substitute itself. The language is proven to be Turing-complete, so some programs such as /ab/bbaa/aab won't halt while some such as /ab/bbaa/ab will.

At first I questioned if halting problem for ^/[ab]*/[ab]*/[ab]*$ is solvable, but I learned unlikely. So I am simplying to ^/a*b*/b*a*/[ab]*$.

# Problem

Given a slashes program that matches ^/a*b*/b*a*/[ab]*\$ in POSIX BRE (i.e. below), determine whether the program halts or not.

## Format of program, if you are not familiar with POSIX BRE

program = "/" first "/" second "/" third
first = "" | first "a" | first first.b
first.b = "" | first.b "b"
second = "" | second "b" | second second.a
second.a = "" | second.a "a"
third = "" | third "a" | third "b"


# Constrains

In this problem every program's length is up to 153.

# Detailed rules

• Can be either a full program or a function.
• Standard i/o apply.
• Examples of input format
• a string of program
• three strings p,q,r when the program is /p/q/r
• integers p,q,r,s and a string t when the program is /a\{p\}b\{q\}/b\{r\}a\{s\}/t
• entirely as an integer (think of it by yourself)
• Examples of output format
• Standard loopholes apply.
• This is ; shortest code wins.

# Examples

Testcase generator 1

My noncompetive solution

///: no
/a//: yes
/ab/bba/aab: yes
/ab/bba/aaab: yes
/ab/bba/aabb: no


# Meta

• Were similar things ever done before?
• I am not even sure if this problem is solvable.
• Just thought there are answers if I clarify maximum length of input.
• Should I change the problem's genre to ? Would making a maximum length of the program be boring?
• /// is turing-complete, so this is not possible Apr 25, 2021 at 12:33
• Should we simplify it more?
– user100411
Apr 25, 2021 at 20:23

# Implement a BrainFlump interpreter

BrainFlump is the latest alternate memory model brainfuck-esque turing tarpit.

It operates on a memory model we call a "Dump", which is simply an un-ordered collection of integers, with a pointer indicating the current item to operate on. As it is "unordered", when moving to the next item, one is simply chosen at random (chosen uniformly between the items that are not the currently selected item) and the operation pointer is moved to that item.

## Commands

+   #Increment the item at the pointer
-   #Decrement the item at the pointer
:   #Add a 0 to the dump, and move the pointer to it
;   #Move the pointer to a random item that is not the pointer's current position
(   #Skip to the matching ) if the item at the pointer is 0
)   #Skip to the matching ( if the item at the pointer is not 0
,   #Read a single character from STDIN and push its ascii value to the dump
#This also moves the pointer to the new item
.   #Print the current item at the pointer modulo 127 as an ASCII character


## Other notes

• When the ; command is used if the dump contains only 1 item, a new 0 is pushed to the dump, and the pointer is moved to it
• The . command does not pop the item from the dump
• When the , command is used if STDIN has been exhausted, a new 0 is pushed to the dump, and the pointer is moved to it
• Any item in the dump who's value is 0 is not considered to exist, unless it is the item at the pointer, therefore to "pop" an item from the dump, you simply set its value to 0
• Nested loops are supported
• The random number generator used for the interpreter does not have to be cryptographically secure, but must chose with uniformity.
• BrainFlump does not support floating point numbers or negative integers. Attempting to decrement a number below 0 has no effect.
• The maximum value of an item in the dump is 255

## Examples/Testcases

### brainf**k emulation

++++++(;++++++++;-);.


This should output 0

### Explanation

++++++        #Increment the first item to 6
(             #While the item under the pointer is not 0
;         #Move to another item in the dump
#    Note the first time this loop runs,
#    this will insert a new item
++++++++  #Increment the new item by 8
;         #Switch to another item in the dump
#    Note there are only 2 items currently,
#    So this will switch to the only other
#    item, the one we initially incremented to 6
-         #Decrement the item
)             #Repeat the loop if the item is not 0
;             #Switch to the other item
#    Note this switches the pointer back to
#    The item we have been incrementing by
#    8 each loop
.             #Output as ASCII character


This is effectively a 6*8 operation, followed by an output, and is nearly identical to brainf**k's ++++++[>++++++++<-]>. program, which also outputs 0.

Note, however, that brainf**k-esque dump manipulation is only deterministically possible if there are never more than 2 items in the dump.

### Random output

+:++:+++:++++:+++++:;.


This will actually always output an unprintable character, however which character is output will be random each time, selected from: SOH, STX, EST, EOT, ENQ, ie ASCII characters 1-5. In a correctly implemented interpreter, this output should be uniformly random between the 5 possibilities.

### Explanation

+      #Increment first item to 1
:      #Add new item and move to it
++     #Increment new item to 2
:      #Add new item and move to it
+++    #Increment new item to 3
:      #Add new item and move to it
++++   #Increment new item to 4
:      #Add new item and move to it
+++++  #Increment new item to 5
:      #Add new item and move to it
#    Note this last item is added because ; will
#    always switch to an item that is *not* the
#    currently selected item
;      #Switch randomly to an item in the dump
.      #Output as ASCII character


To give a little more info on this, by the time the ; command is reached, the dump should look like this:

1 2 3 4 5 0
^


As ; always switches to a different item, the result will be the pointer at one of the non-zero items.

### cat

,(.,)


Nice and simple, and identical to brainf**k's cat program.

For scoring purposes, you should use this gist as input when testing.

### When will it end?

++++(,:+++++;++(;++++++;--):++++;---)


This program doesn't output anything, but runs for a non-deterministic amount of time.

### Explanation

++++             #Increment first item to 4
(                #Start loop
,            #Read char from STDIN to new item in dump
:+++++       #Push 5 to dump
;++          #Switch to random item in dump and add 2
(            #Start loop
;++++++  #Switch to random item in dump and add 6
;--      #Switch to random item in dump and subtract 2
)            #End loop
:++++        #Push 4 to dump
;---         #Switch to random item in dump and subtract 3
)


This one is a little tricky, as ; will never switch to a 0 (Remember items with a value of 0 are considered to not exist)

The inner loop will only exit if ;-- switches to a number <= 2

The outer loop will only exit if ;--- switches to a number <= 3

Due to the inherent randomness of the language, this should always terminate... eventually.

For scoring purposes, you should use the exact string Hello, World! as input when testing.

## Scoring

This is meaning the interpreter that on average runs the fastest, wins!

Scoring will be determined by running each of the 4 test-cases above 100 times, and determining an average runtime (due to the inherent randomness of the language, a high number of runs should be made to minimise anomalous results).

Then once you have an average for each testcase, sum the 4 times, and that is your final score. Lower is better

• I feel like a lot of time will come from the RNG, so better solutions might sacrifice some "randomness" for speed - You might want to standardise "randomness" Dec 22, 2021 at 3:42

# Rearrange a list so no element is in its original place

Rules: take a list of positive integers (allowing duplicates) and output those integers reordered such that no item of the output list is equal to the item in the same index of the input. Assume this is possible for any input you will get.

Examples:

 in: 1,2,3,4
out: 2,3,4,1

in: 3,3,1,2
out: 2,1,3,3

in: 1,1,2,2,3,3,3
out: 3,2,3,3,2,1,2


# meta:

Is this a dupe of this? Duplicate items aren't allowed in that challenge, and you have to uniformly-random-ly output one of all valid derangements. Sort of a tossup on whether that's too similar in my own opinion, I have no idea.

• what happens when the input is [1, 2, 2, 2, 2, 2]? Dec 16, 2021 at 13:31
• @justANewbie "Assume this is possible for any input you will get" means that you wont get that input. Should I rewrite that clause to be clearer? Dec 16, 2021 at 13:33
• I see no reason to restrict it to single digit numbers, positive integers seems fine. Dec 17, 2021 at 18:24

# Schrödinger's cat program

• This is probably good to post now, and it looks like a good challenge! Dec 27, 2021 at 5:59

# Incrementally Increment Identical Integers

• Total rewording suggestion for everything up until before "To demonstrate": Given a non-empty non-descending list of any integers, increment each number by how many identical elements occur to its left.
Jan 1 at 18:16
• @Adám For what it's worth, I find that less understandable than the current description. It's probably a difference of APL mindset vs. Python mindset. Jan 1 at 18:18

# Remove odd indices and double the even indices

• The test cases are now consistent with the example explanation, but not with the "remove odd, double even" description. You could fix this by either changing this to "remove even, double odd", or switching to 0-indexing Jan 17 at 12:40

# Cops and Robbers - Find my other token

• The robbers wins = many cracks (accept the most upvoted) Jan 14 at 14:26
• 3. No you can't Jan 14 at 14:26
• 2. No maybe secret is too hard. do you mean secret guessing game? Jan 14 at 14:28
• 1. Yeah this is ok Jan 14 at 14:28
• 4. If you want then No, else Yes Jan 14 at 14:30
• 2 votes is best, if you want then goto post Jan 14 at 14:48
• @Fmbalbuena The sandbox guideline says typically at least 3 votes. Jan 14 at 15:02

# Score a Scrabble Play

• I think removing the letter points mapping from the challenge as you suggest is a good idea. Otherwise a lot of the byte count will be taken up just in storing the map, with less of the answer being the interesting part, which is the scoring algorithm. Honestly it might even be worth assuming all letters score 1, because the interesting computational problem is really just detecting what the words formed in the grid are. Jan 24 at 20:53
• @pxeger I think I would like to keep the specific point values, so that the challenge still involves the words themselves somehow. Otherwise it would suffice just to find the distances between relevant tiles and certain empty squares as well as losing some (important, in my opinion) flavor. Jan 24 at 21:01
• That's a good point; I hadn't considered that the letters themselves would no longer matter in that case. I'd still recommend going for the version with points mapping as input. Jan 24 at 21:03
• Where do we get the word dictionary? Jan 24 at 21:08
• @GingerIndustries There is no need for a word dictionary. As I wrote in my post, answers do not need to consider the legality of the play. Jan 24 at 21:11
• please check if i have explained properly as some may not understand Feb 2 at 9:20

# Print 2^n graph in ASCII

Your challenge is to output this infinite graph:


o
o
oo
oo
oo
oo
ooo
ooo
ooo
ooo
ooo
ooo
ooo
ooo
oooo
oooo
oooo
oooo
oooo
oooo
oooo
oooo
oooo
oooo
oooo
oooo
oooo
oooo
oooo
oooo
ooooo
ooooo
ooooo
ooooo
ooooo
ooooo
...


with the xth line having floor(log_2(x)) os (or other characters). Tag: code-golf, ascii-art, kolmogorov-complexity.

• wow this looks interesting tbh, is there supposed to be a \n at the start of the sequence? Feb 12 at 13:48
• @DialFrost Yeah, because floor(log_2(1)) = 0.
– null
Feb 12 at 15:05
• nice, but is there a reason you chose o? Feb 20 at 10:55