# 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!

Sandbox note: This is partially inspired by There's a fault in my vault!, which I thought had some interesting ideas in it. This is my effort to frame those ideas in a clearer fashion.

# Cops/Robbers: Create a weak block cipher

In cryptography, we often use block ciphers, which are a form of keyed encryption. More specifically, for a plain text string $$\s\$$ and a secret key $$\k\$$, we design an encryption function $$\E(s, k)\$$ and a decryption function $$\D(\hat{s}, k)\$$ such that if we encrypt and then decrypt the text with the same key, we get back our original text. That is, we have $$\D(E(s,k),k) = s\$$ for all possible strings $$\s\$$ and $$\k\$$.

One security property a good block cipher has is that it is resistant against key-recovery attacks. This means that if we have the ability to run $$\E(s, k)\$$ and $$\D(\hat{s}, k)\$$ for various choices of $$\s\$$ and $$\\hat{s}\$$ and collect pairs of encrypted and decrypted text we cannot tell what the key is.

In this challenge, you will design a simple block cipher that is intentionally vulnerable to a key recovery attack, and challenge others to try and exploit it.

## The Cops' Challenge

1. Design a block cipher. Design an encryption function $$\E(s,K)\$$ and decryption function $$\D(\hat{s},k)\$$ that take strings (or your language's closest equivalent) of a fixed length $$\16\$$ bytes and a key of fixed length $$\16\$$ bytes and outputs a string of length $$\16\$$ bytes. Your $$\E\$$ and $$\D\$$ functions must have the property that $$\D(E(s,k),k) = s\$$ for all 16-byte strings $$\s\$$ and $$\k\$$.1 The functions must be deterministic (not use any randomness) and pure (not rely on any outside state). Your $$\E\$$ and $$\D\$$ must work within the integer/float precision of your language. Specifically, you may not treat floating point as if it's arbitrary precision, nor may you assume integers of arbitrary size if your language utilizes fixed-size integers.
2. Implement a secret key-recovery attack on your block cipher. Write a program that makes calls to $$\E\$$ and $$\D\$$ for a secret, unknown key $$\k\$$ and fully recovers the key by observing properties of the input/output pairs. The key must be recovered with probability $$\1\$$ - you may not rely on probabilistic approaches.2 You must treat $$\E\$$ and $$\D\$$ as black boxes, from which you can only observe their input and output. This means you must not utilize runtime introspection, timing information, or other side effects of the implementation. You must only pass full $$\16\$$ byte strings to $$\E\$$ and $$\D\$$, and not any other type. This means you may not rely on special objects with overloaded operators or similar to glean information about how the input is processed by $$\E\$$ and $$\D\$$. Your attack may be adaptive, in that it decides which strings to pass in based on outputs to previous strings. To enforce a practicality limit, your attack must work for a combined total of strictly less than $$\2^{16}\ = 65536\$$ calls to $$\E\$$ and $$\D\$$ for any key $$\k\$$. If the block cipher you design has the property that for keys $$\k_1\$$ and $$\k_2\$$ that $$\E(s,k_1)=E(s,k_2)\$$ and $$\D(s,k_1)=D(s,k_2)\$$ for all $$\s\$$, then we call these keys functionally identical, and your attack may recover any functionally identical key to the original.

That's it! You will reveal both the encryption and decryption functions $$\E\$$ and $$\D\$$, and challenge the robbers to find your key recovery attack (or possibly a different one).

Clearly, the challenge is to design your $$\E\$$ and $$\D\$$ to look secure, but they have some catastrophic weakness that allow you to recover the key with very few calls. Another approach is to 'trapdoor' the function in some way only known to you. In the spirit of Kerckhoffs's principle, you are encouraged to post a short explanation of what your $$\E\$$ and $$\D\$$ do, especially if they are written in an esoteric language.

You may use cryptographic functions if you wish, but using them presents several practical problems. Hashing functions are designed to be one way and your are unlikely to be able to design both an encryption and decryption function that utilizes them. Symmetric ciphers have both encryption and decryption, but is unlikely to allow the key recovery attack outlined here.

If no-one mounts a successful attack in 7 days, you may post your key recovery attack and mark your answer as safe, which prevents it from being cracked. Note your submission can still be cracked until your reveal your attack.

Your answer is invalid if you do not follow the rules set above. Your answer can be declared invalid even after it is marked safe, if it turns out your revealed attack does not obey the rules.

The shortest safe submission, calculated as the sum of the bytes of the two functions $$\E\$$ and $$\D\$$, wins. Your functions must be named.

## The Robbers' Challenge

1. Find a vulnerable answer. That is an answer, which hasn't been cracked yet and which isn't safe.
2. Crack it by designing a key recovery attack. Your attack must follow the rules outlined in the cops section. To recap, this means:
• The total number of calls to $$\E\$$ and $$\D\$$ with the key $$\k\$$ must be strictly less than $$\2^{16}\$$
• You must only pass $$\16\$$ byte strings to $$\E\$$ and $$\D\$$, and must have the key $$\k\$$ initially be unknown
• The attack may be adaptive but must work to recover any 16 byte key $$\k\$$ (or a functionally identical key)
• You must treat $$\E\$$ and $$\D\$$ as black box, and may not use runtime introspection, timing information, etc.

If you've found such a attack, post an attack on the robber's thread linking back to the answer. If possible, you should post a link to an online interpreter which allows others to run your attack for various keys $$\k\$$. You are encouraged to post how your answer works, and the maximum number of calls your approach makes to $$\E\$$ and $$\D\$$. If your attack does not recover the key, but instead a functionally identical one, explain (briefly) why they are functionally identical.

The user who cracked the largest number of answers wins the robbers' challenge. Ties are broken by the sum of bytes of cracked answers (more is better).

## Example #1

### Python 3, 133 bytes (cop)

E=lambda s,k:''.join(chr((ord(c)+ord(d))%256) for c,d in zip(s,k))
D=lambda s,k:''.join(chr((ord(c)-ord(d))%256) for c,d in zip(s,k))


Try it online!

My program computes the sum of $$\s_i\$$ and $$\k_i\$$ for each $$\i\$$.

### Python 3, cracks xxx's answer

leaked_key = E('\0'*16,k)
print('key = %s' % leaked_key)


Try it online!

My crack completes in $$\1\$$ call and uses that fact that $$\0 + k = k\$$.

## Example #2

### Python 3, 147 bytes (cop)

def E(s,k):
o=''
V=[*range(256)]
j=0
for i in range(16):
j+=V[i]+ord(k[0])
j%=256
V[i],V[j]=V[j],V[i]
o+=chr(ord(s[i])^j)
return o
D=E


Try it online!

My program uses a complicated thing.

### Python 3, cracks yyy's answer

leaked_key = ''
for c in range(256):
if E('f'*16,chr(c))==E('f'*16,k):
leaked_key = chr(c)+'x'*15
break

print('key = %s' % leaked_key)
assert E('abcdabcdabcdabcd', leaked_key) == E('abcdabcdabcdabcd', k)
assert D('abcdabcdabcdabcd', leaked_key) == D('abcdabcdabcdabcd', k)


Try it online!

They only ever use the first byte of the key, so we can just bruteforce the first byte and pad with anything to get a functionally identical key. This involves a maximum of $$\256\$$ calls to $$\E\$$ with the secret key.

1. This means that if your language uses null-terminated strings, such as C, then you should be using memcpy-type operations instead of string operations. Since the input length is fixed as 16 bytes, this should be no issue.
2. This requirement forbids most kinds of Birthday attack.

# Questions to sandbox users:

• I know this is a lot to take in. Is it clear?
• Can anyone think of a trivial way to trapdoor $$\E\$$ and $$\D\$$ with eg. a hashing function? I don't think it's possible, but I could be wrong.
• I love this idea! I think it's written in a pretty clear way, I think you could trivially trapdoor E and D, by doing something like if (s == hash("sixteen_byte_str")) return k, but disallowing cryptography functions should fix that – Redwolf Programs Sep 7 '20 at 14:06
• @RedwolfPrograms Glad you think it's clear! Out of curiosity, if you wrote that as your encryption function, how would you write the corresponding decryption function? – Sisyphus Sep 7 '20 at 22:58
• Something like if (ŝ == k) return hash("sixteen_byte_str"), you'd just need to ensure there's no way it could be confused with a value that legitimately encrypts to k (which would be easily doable by replacing it with whatever hash("sixteen_byte_str") would typically encrypt to). Using crypto functions to trivially win a CnR challenge is practically a loophole, and is likely to be downvoted anyway. (Btw, when I write x == hash("sixteen_byte_str"), I mean hash(x) == "sixteen_byte_str") – Redwolf Programs Sep 8 '20 at 1:51
• Actually, wait, I'm being stupid. I think there's no way to not have it return hash(x) == "sixteen_byte_str" in one of the two functions, so there doesn't appear to be a trivial way to trapdoor it. I'd still disallow crypto in case someone uses some sort of fancy asymmetric thing, but I can't figure it out if there is. – Redwolf Programs Sep 8 '20 at 12:08

# Take 6!

A good card game is a wonderful thing. I got me a nice fresh set of Take 6! Too bad though, I have no-one to play with. And so I turn to you!

## The Game

The game is played with a set of 104 cards, numbered 1 to 104 inclusively. Each card has a number of 'cows' attached. Here's a quick Python function to calculate the number of cows:

def cows(card):
out = 1
if(card % 5) == 0:
out += 1
if(card % 10) == 0:
out += 1
if(card % 11) == 0:
out += 4
if(card % 5) == 0:  # C-c-c-combo
out += 1
return out


Therefore, there is a total of

• 1 card with 7 cows (number 55)

• 8 cards with 5 cows (the other multiples of 11: 11, 22, 33, 44, 66, 77, 88, 99)

• 10 cards with 3 cows (multiples of ten: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100)

• 9 cards with 2 cows (other multiples of five: 5, 15, 25, 35, 45, 65, 75, 85, 95)

• 76 cards with 1 cow (all other cards)

The game is played by up to 10 players.

Each player is given 10 cards. 4 cards are placed on the table as the starts of 'rows'. Then 10 turns of play take place. Then, results are calculated.

### A turn

Each player selects one of their remaining cards. At the same time, they reveal their selected cards.

Going in the order of lowest card number, the player whose card it is must place it into a row according to rules:

1. If there is a row with the top card of a lower number than the player's and no such row with a lower number exists, their card must be placed at the end of the row. If their card is the sixth in a row, they take the first 5 cards and put them on their result pile, leaving theirs as the new start.

2. If no such row exists, they must pick one of the rows, take all the cards there to their result pile, and leave their card as the new start.

Examples:

row tops: 10 20 30 40

played: 25

must be placed on the row with a 20, creating the configuration 10 25 30 40 with a possible cow gain

row tops: 10 20 30 40

played: 9

pick any row, creating for example 10 20 9 40, but guaranteed to gain cows

### Counting

The sum of cow values of the cards in a player's result pile is their score. The lower the score the better.

Scores may be added up over several games, creating an overall score for a match.

## Bots

Bots will be standalone programs. Everything belonging to a bot will be placed in a single directory, the name of the directory will be used as the name of the bot. A launch script named launch (may be the entire bot) must be provided. If necessary, a compilation script named build may be provided. Both scripts shall be placed directly in the bot's directory and should use shebangs to specify how they are to be run.

Bots shall not interfere with other bots, the controller, or the git repositories used.

The bots will have the option of storing extra information in files in their own directory. It will be wiped when a fresh series is being run (such as after adding a new bot).

An override input format may be provided. I intend to use StringTemplate for this, I'll write up some details when working on the controller. The default format will have all messages newline-terminated.

Once launched, the bot will be first given their cards, as a list of card numbers, where the numbers may or may not be ordered.

The default format will be

cards 0 1 2 3 4 5 6 7 8 9


No response is expected.

For each round, the bot will be prompted with the current state of the grid, that is the number of cards in each row, the sum of cows in each row and the top number card in the row.

The default format will be

count 1 2 3 4

cows 5 6 7 8

top 11 20 22 35


The bot shall answer with the number of one of its remaining cards.

The list of all the cards used by all bots in the round will be given to each bot. Not that this includes the bot's own card. The order of bots in this message will be consistent within a game.

The default format will be

used 0 1 2 3 4 5 6 7 8 9


No response is expected.

If the placement rule 2. has to be invoked, the bot will receive a message containing the board state at the time when it needs to pick a row

The default format will be

pickrow

count 1 2 3 4

cows 5 6 7 8

top 11 20 22 35


The bot shall respond with the number of the row it wishes to take. The rows will be 0-indexed for this.

If the bot's move results in a gain of result cows, it will be informed of which cards and how many cows it has gained (note that the lower the number the better).

The default format will be

cardgain 1 2 3 4 5

cowgain 6


No response is expected.

At the end, all bots will be shown their score as well as all the scores of others, in the order consistent with the used cards message.

The default format will be

score 30

others 0 1 2 3 4 5 6 7 8


No response is expected.

If the bot makes an invalid move, it will be delivered a special message informing it of such. From that point the bot's current game is over. It gets 100 points of penalty.

The default format will be

invalid


A timely shutdown is expected.

The bot may of course try to save information to its private file at any time, including at the end.

After the final message, the bot shall terminate in a timely manner.

Scoring will be added up over many games, number depends on how fast the games end up running, but at least 100 sounds reasonable to me.

Bots will be placed in a separate github repository TODO for easy setup and reseting. Bots that need a compilation script but don't have one will be given one.

## Controler

Work has started at https://github.com/MrRedstoner/Take6KOTH

The controller will be designed to run in Java 1.8+, using the Process API to launch bots.

# Notes:

While the number of bots is too low, it will be padded to 10 by using multiples of primitive bots. The tournament style once 11+ submissions exist is for now playing all subsets of size 10.

I intend to write up at least a few primitive bots, to get the games going. Something like using cards in the order they were given, or randomly. These will also demonstrate the custom input functionality. Maybe even one that uses external input, to let me play for fun!

Limits for execution time, storage of data etc. are not given at this time. If bots start to behave excessively limits may be added.

Sandbox notes:

Any better idea for tournament?

Should bots be given the names of their competitors as well? Currently leaning towards yes.

Planned tags:

• Even though most people can read python, you should still include a written description of how the cows are counted. As it is, your program counts twice for it being divisible by 5 in the case of 55, is that intentional? – FryAmTheEggman Sep 18 '20 at 18:13
• @FryAmTheEggman it is indeed intentional, it's a combo for a reason :D. The result also matches what wikipedia describes about the game. Should have some more to edit soon so I'll make the change then. – Mr Redstoner Sep 18 '20 at 18:16
• But when do you take 720?? /s – Jo King Sep 21 '20 at 9:39

# Output all of printable ASCII using all of printable ASCII

Posted

• "Irreducible" isn't really an observable requirement; I'd recommend looking into using pristine-programming to make it an objective criterion. – hyper-neutrino Oct 12 '20 at 18:31
• What do you mean by "observable"? "irreducible" simply means you can't purely remove characters (not purely substrings) from the program and have it still work (not merely not error). That's pretty objective, is it not? – pxeger Oct 12 '20 at 18:39
• Actually, yes it seems you're right, I was probably thinking of some other common criteria that isn't valid. Otherwise challenge looks good, doesn't seem to be a duplicate. I would say this isn't kolmogorov complexity since it's not constant but it is restricted source albeit not in the common usage. – hyper-neutrino Oct 12 '20 at 18:48
• Can my program contain additional non-ASCII bytes? – Adám Oct 12 '20 at 19:00
• @Adám yes, in the post it says "Your program, and its output, can contain any additional non-printable-ASCII bytes (bytes, not characters) if you like, such as newlines". "non-printable-ASCII" includes "non-ASCII" – pxeger Oct 12 '20 at 19:01
• Ah, I see. Maybe clarify that you mean both non-[printable-ASCII] and [non-printable]-ASCII. – Adám Oct 12 '20 at 19:03
• Perhaps subtract 95 from each score so that scores look more reasonable – lyxal Oct 13 '20 at 10:51
• @Lyxal my reasoning for not doing that was because I suspect most answers will be quite a lot longer in order to make sure they're irreducible, it would complicate things, and IMO it doesn't really matter if they're that length – pxeger Oct 13 '20 at 10:55

# Round a Matrix

Your input is a 2d array of nonnegative floats A. It can be supplied in whatever format is most acceptable for your language. It can have any dimensions.

Let r and c be the 1d arrays of row and column sums of A respectively, rounded to the nearest integer, with the rule that 0.5 is rounded up to 1.

Your task is to output a 2d array of nonnegative integers B such that |b_{ij} - a_{ij}| < 1 for all i and j, and also the row and column sums of B are equal to r and c respectively.

In other words, B is obtained by rounding each element of A up or down, in such a way that the row and column sums are preserved.

There may be many possible solutions. In this case, you only need to output one of them.

If there is no solution, your program's behaviour can be undefined.

Example:

 A = 1.2 3.4 2.4
3.9 4.0 2.1
7.9 1.6 0.6


in this case, the row sums are [7.0, 10.0, 10.1] and the column sums are [13.0, 9.0, 5.1] so after rounding these, you get r = [7 10 10] and c = [13 9 5]. One acceptable solution is

 B = 1   3   3
4   4   2
8   2   0


This is code golf, so the shortest code wins.

## Motivation

I am also interested in what clever algorithms people can come up with. I guess the most obvious is just to do a random search, but that can take a very long time, even if the array is only 10x10 or so.

## Questions

• Is it clear? Please can you edit it if it's not in the right format?
• Has it appeared here before? (I don't think so, because I was searching Stackoverflow for a while in order to come up with a solution to this.)
• Is there always a solution under the conditions given here?
• Would it be better in some other format than code golf?
• Should the condition |b_{ij} - a_{ij}| < 1 be |b_{ij} - a_{ij}| <= 1?
• Since you want optimal, interesting solutions, rank by time complexity. You'll get fewer answers, but they will be more optimal than a direct brute force approach. – Razetime Oct 22 '20 at 6:53
• The suggestion of using complexity isn't often a good one - most challenges here that try to do that wind up closed or unanswered. It would be much simpler to go by execution time for some number of test cases that you pick. For the actual question, I think you should explicitly say that r and c are computed by summing and then rounding (assuming that is the correct order) as it isn't precisely clear from what you have right now. – FryAmTheEggman Oct 22 '20 at 20:34

# The Fibonacci Rectangular Prism Sequence (posted)

• There are the square roots of A127546. It looks like there are ways to generate this sequence shorter than just generating Fibonacci numbers and adding their squares. So, this doesn't strike me as a duplicate but an interesting challenge in its own right. I'd recommend removing the square-root step from the challenge and just asking for the sum of the three squares, which is a whole number. This might also allow for more interesting recursive solutions. You should include test cases, perhaps something like the first 15 elements of the sequence and maybe one big one. – xnor Oct 27 '20 at 0:39