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

Posted

• Maybe consider order testcases simply from -4 to 16? (Without sorted on their output length) Also, maybe add some larger testcases (no need to list all possible solutions if there are too many. maybe you can show one possible solution, and answers need to having same length output)
– tsh
May 14 at 4:01
• @tsh I can add slightly bigger test cases, but there are no known efficient algorithms to calculate it, so I'm bounded by about 100 May 14 at 4:14
• Okay, after larger testcases added, it is not equal to oeis.org/A056792 now. :)
– tsh
May 14 at 5:30
• I believe that one can construct the answer without brute force search. So don't worry about it bound. It is up to you to decide if brute force search is allowed: If allowed, you may say "your program should be able to calculate answers for |n| < 100, and your algorithm should apply to any size n in theory"; If not, you could say "your program should be able to compute up to $\pm 10^8$ in reasonable time (not time out on tio for example)" in the question.
– tsh
May 14 at 5:45
• @tsh from wikipedia: "the determination of a minimal addition-subtraction chain is a difficult problem for which no efficient algorithms are currently known" May 14 at 5:47
• If i understand that statement correctly, it means an efficient (or polynomial) algorithms in $O(P(\log_2 n))$ is not exist. But A solution works under, say, $O(n)$ or maybe $O(n^2)$ is still possible.
– tsh
May 14 at 5:58
• Maybe, but I'm also not aware of any pseudopolynomial algorithm which solves it May 14 at 6:01

# Convert version string to pack_format code-golf

Posted

• @Arnauld thanks, fixed May 16 at 16:52

### Telephone Cipher Encoder

The telephone cipher is a relatively basic cipher originating from the book The Terrible Two. The cipher is explained here as follows:

Does this keypad (below) look familiar? It does? Good. You’ve seen a phone before.

Now, in the telephone cipher, there are two numbers for each letter. The first digit corresponds to the number on a telephone, while the second digit corresponds to the position on the key.

For example:

21 = A

Why? Because A is located on the number 2 on the keypad and A is in the first position of that particular key.

22 = B

B is located on the 2 key and is in the second position of that key.

53 = L

L is located on the 5 key and is in the third position on that key.

Given an input string s, the program should output the string encoded with the telephone cipher.

s may contain single spaces between words, but will not have leading or trailing whitespace and will use only lowercase letters a-z. s will always have a length greater than or equal to 1.

The output should contain no whitespace and be properly encoded with the telephone cipher as described above.

As an example, the following input:

hello world


Should result in:

42325353639163735331


All usual loopholes are disallowed. This is code golf so shortest answer in bytes wins. May the odds be ever in your favor!

• What about the evens? :P May 18 at 21:15
• Back to the days mobile didn't have a touch screen, I typed 4433555 555666 instead of 4232535363 for hello...
– tsh
May 19 at 2:58

# Memory KoTH

Memory is a game where a bunch of pairs of identical cards are laid upside down, and you try to find pairs while only looking at two at a time.

In this KoTH, the way it will work is:

The game will be played on a 4096-item array, and the "cards" will be integers 0-2047.

Each bot takes its turn in order. It has access to the results of previous moves (Up to its previous turn), but their only storage is a single integer.

# Spec

The controller will be written in Javascript.

The bot has a move function, which must return two integers: The positions of both its guesses, in the form [g1, g2], where both are integers between 0 and 4095, and must not be gone already (see below).

The most recent move of every bot, including itself, in the form of an array of [g1,g2,r1,r2], where r1 and r2 are the first and second values revealed. The first item of this will be your bot's most recent guess, and the rest will be the other bots. This will be the global variable prev, and is readonly.

A picture of the entire grid, as a 4096-item array, left to right and top to bottom, where 0 means gone and 1 means still there. This will be the global variable grid, and is readonly.

An array of values that are gone. This will be the global variable gone, and is readonly.

A single ArrayBuffer(50), a 50-bit set of raw binary data. See the docs for help on how to access this. This will be the property this.storage, and can be used to store data.

Writing to globals is banned.

# Game

The bots will take their turn in a predetermined randomised order.

If a bot's moves are two tiles with the same value, those tiles are removed from the game area, and that bot gets a point.

The game ends when all tiles are gone, and the bot with the most points wins. In case of a tie, the bot that is last in the randomised order wins.

Bots should be a Javascript object like:

{
name: "A bot",
move(){
// insert code here
}
}


# Meta

Should I change storage limit or grid size?

• Shouldn't the bot be able to see the values of gone items? May 15 at 9:03
• @CommandMaster True, will add. May 15 at 21:02
• This doesn't really matter too much but if it were up to me, personally, I would change the storage limit from $[1,2^{50}]$ to $[0,2^{50}-1]$ so it's a bitstring of length 50
– hyper-neutrino Mod
May 18 at 6:10
• @hyper-neutrino Oh yes, that's what I intended. May 18 at 6:11
• What if two bots tie? May 18 at 8:18
• @StackMeter The one that is last in the randomised order wins. I'll add that. May 18 at 8:41
• Wouldn't it be easier to use a Uint8Array rather than a Bigint? Purely for ease of use. May 20 at 12:51
• Also need to make it clear that writing to globals is banned, since that's a legal play right now May 20 at 12:52
• @EnderShadow8 Yes, writing to globals is banned. May 20 at 20:07
• @EnderShadow8 How would I format this Uint8Array? Like how many items would it need to be restricted to? May 20 at 20:07
• Up to you. It's just a more convenient method of storing data that's a certain size. May 20 at 23:32
• @EnderShadow8 Actually, I think a BigInt would be better for this challenge, as remembering a single tile is 23 bits, which would be confusing to fit into a Uint8Array. May 21 at 4:22
• Just make it a plain ArrayBuffer and DataView. That's easier. I don't like using bit operations to extract data from integers. May 21 at 4:42
• @EnderShadow8 Ok. May 21 at 4:43
• Are you considering giving the bot the result of its first guess before asking for its second? That would introduce a new layer to the strategy. Eg. explore on the first move and defend or attack on the second May 21 at 5:04

# Calculate $$\ \lfloor n \log_2(n) \rfloor $/extract_tex], exactly Given an integer $$\ 2 \le n $$/extract_tex], you need to calculate $$\ \lfloor n \log_2(n) \rfloor \$$, assuming all integers in your language are unbounded. However, you may not ignore floating-point errors - for example, in python lambda n:int(n*math.log2(n)) is an invalid solution, because for example for n=10**15, int(n*math.log2(n)) is 49828921423310432, while the actual answer is 49828921423310435. ## Rules ## Test cases 2 -> 2 3 -> 4 4 -> 8 5 -> 11 6 -> 15 7 -> 19 8 -> 24 9 -> 28 10 -> 33 100 -> 664 1000 -> 9965 10000 -> 132877  10 brownie points for beating my 4 byte 05AB1E answer. This is code golf, so the shortest answer wins. Good luck! # Symmetrical Triangles, posted ## Meta Questions • Dupe? • More tags? • Should I allow/disallow more output formats? • Is "An equilateral triangle array" clear, or is there a way I can clarify it? • Especially relevant test cases? • Is there an easy way to take up less vertical space and still have a good amount of test cases? • This might not actually be more clear, but I think you can describe it as "output w lists of sizes [1, 2, ..., w] of 1/0s such that the total number of 1s is equal to n and each sublist is a palindrome". – hyper-neutrino Mod May 17 at 20:51 • May 19 at 15:29 • @hyper-neutrino it doesn't have to have each sublist a palindrome to be symmetrical May 19 at 15:30 • When I first read this, I thought that it only took one input n, and had to output a n-sized triangle with n 1s. Now I realise that the size is a different input, but I think it could be more interesting if n == w? May 19 at 15:31 • @pxeger I don't think that makes it more interesting, especially since it removes the point of the challenge (arranging the 1s), by allowing them to be always placed at the bottom of the triangle. May 19 at 15:34 • @Wzl ah, I didn't think of that May 19 at 15:43 # Backromymiser code-golfstringsubsequence ## Background A backronym is an acronym that was formed from an existing word. For example, spam is actually named after the canned meat product as used in the Monty Python sketch, but can be interpreted as "stupid pointless annoying mail". They can also be constructed using a more facetiously, such as "What Horse shYte" (that chat conversation was the inspiration for this challenge) ## Challenge Given a sentence a and a word b, capitalise the correct letters of a such that they spell out b. You may assume a will always consist only of lowercase ASCII letters and space, and b will always consist only of uppercase ASCII. Alternatively, you may assume b will always be lowercase, but this must be consistent. You do not need to handle empty inputs or inputs that have no possible backronymisation. You should always move left-to-right and capitalise the first occurence of each letter. ## Example a = "im never gonna give you up", b = "VIP" • Working through the letters of VIP: • v: find the first instance of v in im never gonna give you up and upper-case it -> im neVer gonna give you up • i: find and upper-case the next instance of i (after the already found v) -> im neVer gonna gIve you up • p: do the same with p -> im neVer gonna gIve you uP ## Test cases a b output ===================================================================== "im never gonna give you up" "VIP" "im neVer gonna gIve you uP" "dbdacbec" "ABC" dbdAcBeC "x" "X" "X" "xxxx" "X" "Xxxx" "what horse shyte" "WHY" "WHat horse shYte" "facdbbbd" "ABC" (impossible; does not need to be handled)  ## Rules # Meta • Is this a duplicate? (related, related) • Is this clear enough? • Any other feedback? • I quite like this challenge, but why are there four possible outputs for xxxx, X? Was it not specified that the first occurrence should be capitalized and only that one? – user100690 May 27 at 19:31 • I'll change it so that it's always the first option. May 28 at 7:35 # Prime Factorization - but on the exponents too • There seems to be a stray double-quote here: "2^(2^2^2)*(3^2). Should it be removed, or should there be a matching one at the end? May 28 at 8:57 • There shouldn't be in the output - it was just to show the string format May 28 at 8:58 • I've edited this down to a stub now that it's been posted to save space Jun 1 at 23:12 • Can answers use vertical tabs instead of space padding? Also, I'd suggest saying that "\n\ will be a positive integer", as "integer" could be zero/negative May 31 at 15:22 • edited: hopefully makes sense May 31 at 15:37 • We usually allow a wide range of I/O methods. It is recommended to rethink your I/O restriction (mainly because it will get downvotes if people think the I/O restriction is unnecessary). Also, is it allowed to print trailing spaces after the backslashes on each line, or a trailing newline after the last line? (I guess yes to the latter from your code, but it's always better to be explicit) Jun 1 at 4:34 • Strictly speaking, that line you are drawing actually has a length of sqrt(32). I think you should make it clear that the length refers to the number of non-whitespace characters. Also, "use a constant in your code" seems to be frowned upon as a method of input. – user100690 Jun 1 at 15:57 • how is the length \\sqrt{32}\??? Jun 2 at 13:53 • Good challenge as a new user. – qwr Jun 2 at 14:14 • The challenge is easy enough that it should not be necessary for answers to explain themselves. Answerers will do this voluntarily if they think it is necessary. – qwr Jun 2 at 14:16 • @MaanasB pythagorean theorem. sqrt(4^2 + 4^2) = sqrt(32) – user100690 Jun 4 at 17:36 # Combinatorial Pipes You're a plumber working on a house, and there's some pipes that must be connected at odd angles. You have 8°, 11.25°, 22.5°, 45°, and 90° fittings at your disposal, and you want to use as few as possible to match the angle as closely as possible. # Goal • Match the desired angle as closely as possible, with as few fittings as possible. It can be over or under the desired angle. • Accuracy is more important than the number of fittings • In the case of two different sets of fittings with the same resulting angle, whichever has the fewest number of fittings should be selected. • If the two sets use different fittings, match the same angle, and have the same number of fittings, either may be chosen. # Input Your input is a random integer between (non-inclusive) 0 and 180, which represents the desired angle. # Output Your output should be an array where [0]-># of 8° fittings, [1]-># of 11.25° fittings, etc. If your language does not support arrays, you may output a comma separated list, where the first value represents the number of 8° fittings, and so on and so forth. Test Cases 90° ->[0,0,0,0,1] 24°-> [3,0,0,0,0] ([0,0,1,0,0] uses less fittings, but is less accurate and therefore incorrect) 140°->[2,1,2,0,1] 140°->"2,1,2,0,1" acceptable if language does not support arrays  # Scoring Lowest byte count for each language wins a high five from me if we ever bump into each other (and the challenge). ## Sandbox Questions Howdy! I feel like this could be an interesting golf, but I'm unsure if the language is clear and concise enough to get the idea across. • Might be interesting to make it more general, give a list of possible pipe fittings as an argument? Jun 16 at 9:12 # Decode USB packets code-golfbinarycoding-theoryencoding Posted • Does this not basically boil down to base-conversion? Jun 9 at 12:59 • @pxeger Base conversion will not work. For one base conversion generally ignores leading zeros, while 00010 /= 10, so its not a bijection. But even if you ignore that it's nowhere near monotonic. 11 > 100 but f(11) = 10 < 11 = f(100). – Grain Ghost Mod Jun 9 at 13:25 # Remove All Comments From Smalltalk for Code Golf ## Duplicate? ## Edge cases? ## Not interesting/challenging? ## Tags? • May string contains \" as escaped characters? – tsh May 31 at 8:05 • I might suggest changing  to a different character, simply because it's hard to use in markdown May 31 at 8:43 • @tsh no ;) May 31 at 16:20 • Suggest testcases with multiple groups of strings, multiple groups of comments, and their combination: "a"b"c", 'a'b'c', a'"'b'"'c, a"'"b"'"c – tsh Jun 1 at 6:19 • I'm not sure if this'd be very interesting, since it's just a matter of replacing /"[^"]"/ if I'm correct. – rues Jun 10 at 1:03 • @user I think there's a misunderstanding. The program must also not remove comments in strings, such as 'a"b"c' is not changed Jun 10 at 1:23 # Determine Centrosymmetric String Let's define a centrosymmetric string as follows: • First, add spaces to the end of each line to make the input a rectangle $$\ A_{m×n} \$$. • The input is "centrosymmetric" string if and only if you get the original rectangle if you rotate the rectangle 180°. That is, it has 2-fold rotational symmetry, so $$\ A_{i,j}=A_{m+1-i,n+1-j} \$$ holds for all $$\ A_{1\dots m, 1\dots n} \$$. ## Input Input a non-empty string. You may assume it: • does not contain leading / trailing new lines; • does not contain trailing spaces on any lines; • only contains new line, space, and lowercase a-z. You may choose to handle any of CR, LF, or CR-LF as the new line character in your program. Input may be in any reasonable format, including but not limited to: • A built-in string type; • A NULL-terminated character array; • An array of integer code-points; Note that you are not allowed to take the string padded already as it trivialises the challenge. ## Output Determine if the given input is a centrosymmetric string (as defined in this post), outputting two distinct values, or truthy vs. falsey values (they can be swapped relative to their normal meaning). ## Test cases ### Truthy a  aba  a b a  ab ba  abc cba  abc ded cba  a a  a a  a a  a c b c a  a b b a  zzzzz z z z zzzzz  n n oo oo n n nn n o o o o nn n n nn o o o o n nn n n oo oo n n  ### Falsy ab  a a b  a b a  ab ab  aa bb   a a a aaaaa a a  • I think a worked-through example would be a good idea May 31 at 8:29 • What is the meaning of the 2 in A_{m×n}2? May 31 at 8:37 • Related May 31 at 8:39 • When you say "square", do you actually mean "rectangle"? May 31 at 8:40 • @pxeger the 2. is accidentally left there after I remove the line break between 1. blah 2. blah. Should be removed. – tsh May 31 at 8:44 • @Bubbler changed to rectangle. I'm not quite sure about these words. – tsh May 31 at 8:44 • @tsh A square is a rectangle with all side lengths the same, so m == n. Sometimes in English, "square" is used as an adjective to simply mean "having right-angled corners", which is quite confusing May 31 at 8:46 # Is there a left-right connection? ## Task Given a square array of 0s and 1s, determine whether or not there exists a path of 1s connecting the leftmost and rightmost columns. A path can take steps of one unit up, down, left or right, but not diagonally. Every symbol on the path must be a 1, and it must start somewhere in the first column and end somewhere in the last column. Shortest code in each language wins. ## Examples 000 111 -> True 111 110 110 -> False 110 101 010 -> False 101 0 -> False 1 -> True 11110 00010 01110 -> True 01000 01111 11110 00010 01100 -> False 01000 01111  ## Notes The array may be represented in any reasonable form, such as a list of lists [[0,0,0],[1,1,1],[1,1,1]] or a string '000 111 111'. It can optionally be in transposed form (so that the roles of rows and columns are exchanged; equivalently the code can instead determine whether there is a top-bottom connection). Any two distinct symbols can be used in place of 0 and 1. The output can be in any truthy/falsy form. # Consecutive Distance Rating code-golfarray-manipulationinteger Posted • This is really neat! Simple, elegant, but nontrivial. It'd be interesting to look at the sum and its growth given an (OEIS) sequence. Jun 12 at 1:25 Title: Make a WebCrawler dictionary writer. Notice: for any text within <> tags, please ignore any .'s. These are simply added so that they are treated as plain text, and not code. Your goal is to make a program that acts as a regular WebCrawler, but also writes a dictionary using the websites. You should have a list that is used to store words that have been added called Dictionary, and another list to store website urls called NextSites. You should also have a variable called sites, and a variable called input2. Any other variables or lists are optional. It should ask for input upon running the program, allowing you to input a website url, from where it will start web crawling. How it asks for input does not matter, so long as you are able to use any website as input. It should then ask for input again, allowing you to chose how many sites it should continue for. The variable much should be set to this input. Next, it should check the website for any text contained within <.p> tags. It should separate the text contained within the tag at any space contained in it. Next, it will compare each part that has been separated against the current text in the list used to store words. Any part that is not already in the list should be added to it. After it has checked all of the text within the <.p> tags on the site, it should check for any <.a> tags on the site. Any urls that it finds in the 'href' part of the <.a> tag should be added to the website url list, so long as the url list is not larger than 99 urls. (This means that the maximum amount of urls that can be in the url list at any one time is 100). When all of the <.a> tags on the site have been checked for urls, it should change the current site it is on to the first site in the list of urls. It should remove this url from the list, and move all other urls to the spot one less than them on the list, so that there is no empty space at the beginning. (eg: If you had 3 urls: 1. google.com , 2. wikipedia.com , 3.stackexchange.com, then after switching to google.com, the list would now be 1. wikipedia.com , 2.stackexchange.com .) It should then repeat the above steps, and continue to do so until the variables sites and much are the same. Next, it should should output the entire list of words that it found. The method used to output it does not matter, so long as all words in the list are outputted, with a new line for each word. E.g.: You may have found the words cat, mouse, and food. The output would look as follows: cat mouse food Scoring: The scoring follows regular code golf rules. The person with the smallest program in bytes wins. However, in the case of a tie between two programs, the program that can webcrawl and write the dictionary starting on wikipedia.com for 100 sites fastest will win. • running this type of program even once would probably ends up throttling the sites and blocking access to the crawler. Is there a good way to prevent that? Jun 17 at 2:32 # Largest Number with No Repeating Digit Pairs Inspired by the problem with the same name on Puzzling SE. You are to find the largest number that only uses every digit pair once, in a given base. For example, in ternary we have 2212011002. We can do this greedily by simply starting with the largest number, and then adding the next largest number we can without repeating a pair, until we’ve gotten them all. Challenge: Given a base from 1-10, output the largest number in that base with no repeating digit pairs. As long as the digits make the number, you may output with anything, or nothing, in between. Whether regularly delimited, or irregularly gibberished. You may also take input in any reasonable way. For example, you might take the base, the max digit, or an ordered list representing the digits available. For octal, this would mean 8, 7 or 76543210. If you feel like a challenge, you can take octal as input. I won't complain! Note that it need only work for bases from 1-10. Invisible points for doing alphanumeric bases like hex, but not at all required. This is , so least bytes per language wins. #### Test Cases Decimal: 10 99897969594939291908878685848382818077675747372717066564636261605545352515044342414033231302212011009 Octal: 8 77675747372717066564636261605545352515044342414033231302212011007 Quaternary: 4 33231302212011003 Ternary: 3 2212011002 Binary: 2 11001 Unary: 1 00  • I was gonna suggest this be able to support even higher bases, up to 36 maybe. Though that might give some languages that have built-in support for higher number bases an unfair advantage? Because other languages might have to add special support for A = 9 + 1 rather than just using the ASCII values. Maybe just base 26, and use only letters, no numbers? Not sure if it's worth bothering... (Ah, I see you added that note after I posted this comment) Jun 16 at 19:27 • @DarrelHoffman I did add the edit to make the question as is clearer, but whether or not to include higher bases is precisely my one hang-up! That's what we're discussing in TNB. Come join us! Jun 16 at 19:37 # Draw an Ascii Grid • You can use this to visualise a tictactoe game -- might just do that. Jun 16 at 7:32 • Looks great, just leave it for another 2 days before posting! – user100690 Jun 16 at 15:56 # Implement a cleave function • @Adám You're right. Thanks! Jun 16 at 7:27 • If my language can directly apply a list of functions to a number, giving me a list of results, does that mean a 0-byte answer, or do I have to wrap the application in no-op code? – Adám Jun 16 at 7:30 • @Adám I have no idea if there's a precedent for 0-byte answers, but if the mere act of writing a list of functions immediately applies them to some object in your programming language, that's interesting and I would want to see it. Would writing a blurb about builtins/builtin behavior being allowed help? Something like "Builtin functionality is allowed but consider adding a less trivial answer as well."? Jun 16 at 7:37 • Yes, that would help, and asking for non-trivial things is nice. You might also want to ask for people to explain. – Adám Jun 16 at 7:38 • @Adám Added, thanks. Jun 16 at 7:43 • While tagged functional-programming, are we still allowed to submit a full program that prompts for \L\ and \n\? – Adám Jun 16 at 7:44 • @Adám I'm not sure. I took a look at some other higher-order function questions for inspiration, for example https://codegolf.stackexchange.com/questions/223881/implement-an-over-function and it uses the language "You may input and output in the most convenient format for your language, and in any convenient method,..." and that seemed to suffice there. Jun 16 at 7:56 • Funny thing is that while you call it a conceptual inverse of map, it is just a map, right? E.g. in JS: (L,n)=>L.map(f=>f(n)) – Adám Jun 16 at 8:03 • Indeed, it can be written in terms of map. Does it seem too trivial, you think? Does it need spicing up? Jun 16 at 8:07 • No, I think it is great. – Adám Jun 16 at 8:07 • How would one apply a list of functions to a number in something like Python, which is not a functional-programming language Jun 16 at 11:07 • @StackMeter lambda l,n:map(lambda f:f(n),l) – user100690 Jun 17 at 5:31 • I see now, thanks @RecursiveCo. Jun 17 at 6:06 # On a Collapsing Platform ## Rules In this KoTH, your task is to not die. It seems simple, right? Well, no. You're on a platform. A giant platform, of size 100 * (entries) ^ 1.1 units across (this may change if we get a lot of entries). And every few turns, a random tile is removed. As well as this, you, not a small mass in the scale of things, can cause a tile to fall down. Let me explain how this works. You (the entrant to this KoTH) control a certain number of bots. You (the bots) can then move around on the platform and try not to die. You (still the bots) can move up to 10 units away at base, and can see up to 100 units away (units will be called u from now). However, jumping over a hole costs 2u more, meaning that the largest gap you can clear is three units (3 * 3 for the gap and 1 to land). Do not try and clear 4u+ gaps; you will die. Going off the edge of the platform also is an unwise choice - you will die. By "you - not a small mass in the scale of things", I mean to say that every step you take takes you closer to your inevitable death - each tile you step on has a hidden durability stat, that will not be revealed to you during the course of the round. When it hits 0, the unlucky bot (hopefully not you (the bot)) on it will be removed with the tile. Do not do this; you will die. Your weight is a random stat that is decided at the start of your game, and is subtracted from a tile's durability each time you step on it (weights are 150 at base, and durability values in the range of 15000 - 45000 * (entrants) ^ 1/2, or 15000 * 1-3 * entrants ^ 1/2, so it only becomes an issue in the long term, or when a lot of players exist.) Do not forget about this and start camping on the same 10 tiles on the end; you will die. Everything takes place on a tick system - every 10 ticks, you can do an action (subject to change to 20ish if this is exploitable) and this may well be the most important part of the game - reduce it at all costs - the fewer ticks you waste, the less durability you take off, and the longer you can thread the needle between life and death. Do NOT, and I mean NOT in caps, forget about this - you will die. There are a few items that you can get that will improve your chances and delay your inevitable death represented by these characters: -: Removes 1-7% of your weight (or 1-7, whichever is lesser) =: Increases your speed by 1 (at 13, this will in fact, prove me wrong and let you clear 4u jumps - still not got the + though). ? Increases vision by 5 (allowing you to see 5 more blocks in either direction. > Reduces your tick delay by 0.1 or 1% of your tick rate, should it drop below 5 (however, before that, you will die most likely.) + Duplicates the bot - you start with 10 bots, and each bot left over at the end is worth 10 000 points (1 per tick survived), so this can, effectively, give you 10 000 points free. Every 10-25 turns, a random platform is removed - unless necessary, this will not drop any bots - the platform chosen will always be empty (just so people don't get unlucky and die at turn 85) unless it is forced not to be - for example, in the endgame, where there is only 10 tiles left. Do not forget this; you will die ## Input and Output To begin with, you will get a string such as this 0, 111, 132, 122, 133, 211, 201, 212, 233, 310, 323, where: The first number represents your unique player id, known as PID in the it gang. Then, you get 10 numbers, representing your bots' start positions. Then, for each turn, for each bot that did not die, you (the player) get a string such as this (shortened to save space): .___.+>-__u__...+>+-_._ representing the bot's vision. You must then return an integer, representing how many units you wish to move forward (negative is backwards) (and do not forget that spaces take 2u more, or you will die.); do not try and move more than your speed, or it will be modulo-ed. Errors and invalid input return 0. Note, spaces are represented with ., in the examples and in game. ## Helper functions (to delay your death, hopefully until the end): info(): gives you a chunk of info, in this format: PID: 0 Bots: 11 Score: 10000 [ BID: 1 Weight: 97 Speed: 12 Tick Delay: 8.8 Vision: 110 Pos: -932 Score: 830 ] [ BID: 3 ... ]  The string is format as such: • First, your unique PID. • Then, the number of bots you still have. • Then, your total score. • Then, for each bot: • Its bot ID (or BID for the it gang). (Note, BID are cannot be reassigned, so if Bot 2 dies, and then Bot 1 duplicates, it will have a BID of 10, not 2 (also we count from 0) as it would be if they were.) • Its weight, speed, tick delay and vision, in that order. • Its position on the platform, in that order. • Its score. position(): gives a position of every bot, ordered by their bot ID, or BID (again, only for the it gang). position(ID): gives the x position for a bot with a specific ID. If that ID has died already, it will return "Dead" - plus the space where it died. If that bot never existed, it will return None. tickdelay(), weight(), speed(), vision(), tickdelay(ID), weight(ID), speed(ID), vision(ID): Does exactly what it says on the tin, returns that specific stat for all bots if no ID is given, or the one with that ID should it be given (again, if the bot is dead, it just returns its stats on the turn it died, and if it never existed, it returns None. Make of it what you will). vision(ID) Gives a specific bot's vision - this is useful for sketching a map of the world in conjunction with position(ID). Note that other bots are represented as s, so if you're lucky enough to get your bot (u) in between two opposing bots (s), feel free to laugh. You are allowed access to ALL the random functions (apart from random.seed(), however I will use a set of predetermined seeds in a random order to facilitate retesting. There will be a large number of trials done - this is just to aid improvements if you so desire to make them. Bots can store variables and write to files, but ONLY in their directory. I will find any bot who does this and ban them. ## Scoring Bots gain 1 point for each turn they survive, increasing by 1 every 100-200 turns. This will be notified with the string Score/turn increased by 1. Every powerup gives +500, except for +, which duplicates the bot, including its score, thus adding its score to your total. At the end, when there is three or fewer tiles left, you gain 10000 + the bot's current score for each bot left alive. This is done for every bot that lives, so people getting 2 or more bots through gain more than those getting 1, and two opposing bots can both get points for their team. At least 10000 games will be run per round (subject to change), each time resetting all the stats to the base, rerolling RNG and restarting from the beginning. After as many rounds as I can get through on my PC, the scores will be added up, and the winner gets an accept. # Meta Help with a Python controller would be appreciated. Any specifications need to be made? Should I edit any formulae? # When's my weekend finally here? # Reverse RegEx Take a regex a as input, output a regex b such that, for each string x, x matches a iff x.reverse matches b. Here, regex need to support such symbols: • .(any character expect \n) • [abc](any character in abc) • [^abc](any character not in abc) • x?(appears 0-1 times), x*(appears any amount of times), x+(appears any positive amount of times) • x{n,m}(appears n to m times, m can be omitted to mean infinite) • (abc) (?:abc)(group block, () can be referred while (?:) can't) • \n(refer to the latest match of n-th group) • ^(begin of string), (end of string) (or begin/end of line, see flags/m) • |(or, choose one in some choices) • Letters, \n(this n is char rather than variable, line-feed) You need to handle flags i(ignore upper/lower case) and m(multiline, ^ and  match begin/end of lines rather than string). You can also just pipe the flags and make the containment of regex work for all possible flags, aka. you can treat pipe free. (They refuse to allow or disallow) Sample Input Sample Output /abcd/ /dcba/ /[abc]/ /a|c|b/ /[^abc]/ /[^abc]/ /(.)abc\1/ /^(.)cba\1/ /1/ /10% of 10/  Shortest code win • What's the regex flavor/set of allowed features/inputs? Is it for a full or partial match? May 10 '19 at 9:07 • @feersum Allowed features need discuss. To be a full match ^ and  can be added – l4m2 May 10 '19 at 9:21 • Why is test case /[^abc]/ there twice? Or is it to give two different example outputs? Since just outputting /[^abc]/ for input /[^abc]/ would be fine. Also, I'm not too familiar with this Regex syntax, but how does /1/ work, since  is the end of the match? And why is it /10% of 10/ reversed? May 10 '19 at 9:27 • @KevinCruijssen twice to show that same input may lead to different output. /1/ and /10% of 10/ both match nothing – l4m2 May 10 '19 at 9:32 • "both match nothing" Ah ok.. I falsely assumed the regex would match something. So incorrect (but still valid) regexes are also allowed as input. Maybe it's a good idea to add some comments to the sample outputs, like /10% of 10/ can be anything as long as it doesn't match anything (and maybe put the /(?!a)[^bc]/ or /[^abc]/ for the same input on one line. May 10 '19 at 9:37 • You should more rigorously explain what x.reverse means, from the examples it looks like you mean the order of letters is reversed, but some people might be confused. May 11 '19 at 21:28 • 1) I think x|y is missing in the list of symbols. 2) The behavior of each symbol is underspecified in so many ways. What does [a-z], [[$], (ab+)*\1, or (((((((((((x)))))))))))\11 do? Do we need to handle any backslash escapes other than newline? 3) Are you sure this is possible? Can you reverse (a(bx*){0,2}c)*\2\1? Jun 22 at 23:38 • 4) Using such a complex flavor of regex is a parsing hell, which I don't recommend with the same reasons as parsing arithmetic. Good challenges about manipulating regexes include this and this. Jun 22 at 23:41 • @Bubbler I'll just don't care [[$$] and assume input only contain letters and \n. (a(bx*){2}c)+\2\1 reverses into (c(x*b)(?:x*b)a)\2\1(c(x*b)(?:x*b)a)*(Handcode, maybe wrong; need some OR to fit your original one)
– l4m2
Jun 23 at 0:53
• I'll ask differently: 1) Should we support range notation [a-z] or not? I assume it's not a set of three chars a-z since - is not a letter. 2) I think you have the knowledge that (x)* only captures the last iteration and \1 fails if it is not actually captured. You need to include it in the post. 3) Should we support multi-digit backreference (like \11 being the eleventh)? Jun 23 at 2:06
• A note for the future: a regex with backreferences is no longer a regular expression in the CS sense, and any kind of manipulation on it can easily fall into an uncomputable problem. Jun 23 at 2:20
• Also, about the "pipe free" thing: you didn't define the term "pipe" anywhere, so it only makes the challenge more unclear. "They refuse to allow or disallow" seems like a misunderstanding on your side; see Jo King's comment there. Basically an I/O method is allowed only when the language or the answer format (function or full program) supports it. And regardless of what site policy says, you can allow anything you want as long as you make it explicit (you already did here, so no need to mention the meta post). Jun 23 at 3:41
• I'm pretty sure that the algorithm you have in mind does not handle ((x)|(y))+\2\3 (though it is reversible). I suspect it can be made irreversible if I replace x and y with something more dynamic. Jun 23 at 4:09

# Play Thud

Thud is a game described by Terry Pratchett in his novel, Thud!.

The game simulates a battle between the Dwarfs (in blue) and the Trolls (in green) on an octagonal board with the Thudstone (an impassable space) in the centre of the board.

I have created an environment to play the game and develop game playing code at: https://ajfaraday.github.io/Thud/dist/index.html

The challenge is to write the most successful dwarf or troll player of this game (these will be two separate challenges).

# Rules

Starting with the Dwarfs, players take it in turns to move.

## Dwarf Movement

On the Dwarf player's turn, they can move one dwarf piece either as a walk or a hurl.

Walk: Dwarfs can move as far as they like in any direction until they hit an obstacle (another dwarf, the edge of the board, or a troll). They can only kill a troll by walking if they are only one space away.

Hurl: If two or more dwarfs are in a line (horizontal, vertical or diagonal), they can hurl the dwarf on the end of the line, by the length of the line (e.g. in a line of 3, the dwarf on the end can be hurled 3 spaces). If a dwarf is hurled into a troll, the troll is killed, reducing the trolls score by 4 points.

## Troll Movement

On the Troll player's turn they can move one troll piece, either as a walk or a shove.

Walk: Trolls can move one space in any direction, unless a troll, dwarf or the edge of the board is in the way. Whenever a troll moves, it kills all dwarfs adjacent to it's destination space.

Shove: If two or more trolls are in a line (horizontal, vertical or diagonal) they can shove the troll at the end of the line that number of spaces away, but only if any of the target space's immediate
neighbours contain a dwarf. When a troll is shoved, it kills all dwarfs on or adjacent to it's destination space.

It is not permitted for a troll to land directly on a dwarf by either walk or shove moves.

Each dwarf killed reduces the dwarfs score by 1 point.

## Scores

The score is calculated thus:

• The dwarf player has one point for every dwarf remaining on the board.
• The troll player has four points for every troll remaining on the board.
• The key figure is the difference between these two. This will be used to calculate players' scores in the tournament.

## Ending the game

The game ends when any of these conditions is met:

• There are no dwarfs on the board.
• There are no trolls on the board.
• Both players have declared the game over.
• The game has reached it's cut-off length of 500 moves.

# How to manually play a game

• Hover the mouse over a piece to see it's available moves.
• Safe moves are outlined in green.
• Dangerous moves (which can be killed the next turn) are outlined in orange.
• Killing moves are highlighted in red when the mouse hovers over them.
• Click a piece to select it for the current move.
• Click one of the available moves to move the piece.
• (You can click the relevant 'Make Peace' button to declare the game over according to that player, during their turn)

# How to set up a local instance of the game

You don't have to clone the repository and use it locally to to create an entry, but it helps.

• git clone git@github.com:AJFaraday/Thud.git
• cd Thud
• npm install
• You can then run ./get_answers.sh to get the latest entries from Stack Exchange

If you prefer, you can use the github pages instance at https://ajfaraday.github.io/Thud/dist/index.html

# How to customize a game

• Open /dist/index.html in your browser
• Click 'Customize'
• Select troll and dwarf clients (manual allows direct control)
• Select a turn time in milliseconds (only relevant to non-manual players)
• Click 'Run Game' to see or play the game.
• (Clicking 'Close' will not enact any changes)

# Clients

The game is played by clients, which represent either a troll or a dwarf player. Each is a JavaScript class which must have these three functions:

• constructor(controller) - controller is an object which acts as your interface with the game (see below).
• turn() - This is called whenever it is your players turn to move.
• end_turn() - This is called after your player's turn is over. It can not move pieces, but can make decisions on whether or not to declare the game over.

## Controller

The controller object is your client's interface with the game itself. You can find full documentation for the controller class here: https://github.com/AJFaraday/Thud/blob/main/docs/controller_interface.md

It provides these methods to interrogate the state of the game:

• turn() - Current turn of the game

• scores() - The current score

• spaces() - Every space, and what's in it

• space_info(x, y) - Detailed information on any space on the board.

• dwarves() - The location of every dwarf

• trolls() - The location of every troll

• pieces() - All pieces belonging to the current player (equivalent of dwarves() or trolls())

• indexed_dwarves() - The location of every dwarf with a fixed index

• indexed_trolls() - The location of every troll with a fixed index

• previous_move() - What got moved to where last turn

• killing_moves() - All moves which can kill one or more opponent

• current_space - Currently selected space (not a function)

• clear_space() - Empties currently selected space These methods are used to actually make your move:

• check_space(x, y)- Find out what moves are available from a given space

• select_space(x, y) - The player decides to move a piece at space.

• check_move(x, y) - Find out what will happen if you move to a place

• move(x, y) - The player moves the current piece to the selected space.

These are concerned with ending the game:

• declare(game_over) - Say whether or not your player thinks the game is over.
• opponent_declared() - Has the opponent declared the game over?

# How to write a client

Warning: There is an issue with the project on Firefox (https://github.com/AJFaraday/Thud/issues/3) which prevents editing the code in the browser. This has been confirmed to work in Chrome.

• Open 'dist/index.html' in your browser.
• Click 'Customize'.
• Select 'dwarf/template' as the Dwarf player (or use another client as a starting point).
• Click 'Edit' beside the Dwarf player select.
• Write your client code in the text box provided.
• The Validate button will change colour based on whether or not the client is passes validations (see below).
• When you're happy with it, click 'Apply' (This can be done before it passes validation, but it may not actually work).
• Select a worthy opponent and click 'Run Game' to see the game.

## Validations

In order for a client to work, and therefore be enterable in the challenge, it has to pass these validations:

• It must evaluate as Javascript code.
• The code must return a class, with a constructor which accepts one argument.
• Instances of this class should have functions named turn() and end_turn()
• The client must play a game until it is over (i.e. it must call a valid move during every turn call). The validator will run games against default opponents to determine if this happens.
• Does not have any forbidden terms ** game. - Only interact with the game via controller ** Math.random - Please keep it deterministic ** setTimeout or setInterval - Keep it sequential
** eval, require or import - Just don't

You can open the developer console (F12) to see more detailed information on your client's validation process.

## How to save a client

If you have cloned the git repository, you can save your entry for future tinkering. This step is not required for entry in the challenge, but it may be helpful.

• Edit a client, as above.
• When you're happy with it (preferably if it's passing validation, too), click 'Copy' from the edit interface.
• Create a .js file in /src/clients/dwarf/entry with the name of your entry e.g. /src/clients/dwarf/entrygreat_dwarf_player.js. (This folder will not be wiped by get_clients.js)
• Run node script/get_clients.js from the Thud directory to make your entry available from the Dwarf player select. You only need to do this once to make it avilable.
• npm run build - this will keep watching for changes in your entry and updating the package.

## How to enter your client in the competition

• Decide on the name of your client, your client_name must only have alpha characters and underscores.
• The first line of your answer should be your client's name as a title (with = characters under it on the second line)
• There should be a code block containing the class for your entry (with or without the preceeding module.exports =)
• After that please include a brief explanation of your client's behaviour, and any other information you'd like to include.

Once this is in place, anyone running ./get_answers.sh will see your client available under your username.

The GitHub Pages instance will also be updated periodically. So by making an entry, your code will be added to the repo.

# Tournament rules

The tournament will pit every available dwarf client (in /src/clients/dwarf/) against every available troll client (in /src/clients/troll/), and each pairing will play exactly one game.

The difference between the two players' scores will then update a running total for each client. The winner will gain the difference, and the loser will lose the difference.

There are two winners in the tournament, the most successful troll player and the most successful dwarf player.

According to the rules, after playing a game, the players swap sides, so please also write an entry on the Troll challenge.

This is now nearly complete (apart from some UI improvments and presenting the tournament results a bit more nicely). There's a working example of the code importer working against these two meta questions:

I could really use someone to attempt an end-to-end run at creating a client and adding it to one of these to check that my instructions are clear and everything works.

• Very well described challenge. Seems nice!
– user100752
Jun 20 at 14:17
• @EliteDaMyth Thank you for taking a look. Glad it looks complete. Jun 20 at 22:43
• Two rule questions: 1. in which direction can be hurled/shoved? 2. It is not permitted for a troll to land directly on a dwarf by either walk or shove moves. but both troll moves have lines like kills dwarfs on … destination/…only if the target space … contains a dwarf.
– xash
Jul 2 at 14:17
• @xash Good questions, I'll update to be clear. The answer is always 8 directions vertical, horizontal and diagonal. Also, I learned about the rule that trolls can't land on anything after writing the rules. I should have updated the steps too Jul 2 at 14:31

# Print this sequence I just made up

• Your test cases are correct. (Confirmed with an ungolfed integer implementation.) Jun 27 at 0:05
• Your code must not fail due to floating point errors. If the language used doesn't have arbitrary-precision integers, an integer implementation may fail because of integer overflow before a floating point implementation fails. :-/ Jun 27 at 0:13
• @Arnauld Thanks for confirming my testcases. Would saying that you cannot use floats work? Jun 27 at 0:34
• I think the current wording is fine. It's just weird that prohibiting floating point errors is likely to lead to integer implementations that are actually worse. Jun 27 at 0:41
• @Arnauld Oh well. Jun 27 at 0:44

# Generate off-by-one regex for a string

Given an alphanumeric string as input, generate JS-flavored regex in order to match any off-by-one errors for that string. In stricter terms, your resulting regex must match any single deletions, single replacements, or single additions like in the below examples.

#### Examples:

"hi" -> "(h|i|.i|h.|.hi|h.i|hi.)"
"golf" -> "(olf|glf|gof|gol|.olf|g.lf|go.f|gol.|.golf|g.olf|go.lf|gol.f|golf.)"


Here is a program for generating the results.

Note: The order of the regex does not need to matter (ie, "hi" could be "(h|h.|hi.| . . .")) so long as all patterns are in the regex.

This is , so shortest program in bytes wins.

• Which flavor of regex will be used?
– rues
Jul 4 at 16:13
• @user Lets go with JS to make it consistent, it shouldn't really matter though as the regex will share the exact same format as the example cases, with only the order possibly changed. However, i've now updated the post for clarity. Jul 4 at 17:23
• May string contains special characters like .[]\$^(?!)\?
– tsh
Jul 5 at 1:36
• Your regexp for input hi also match hi itself, which is not off-by-one. Is this designed behavior?
– tsh
Jul 5 at 1:37
• @tsh for question 1, ill specify alphanumeric, and for question 2, ill keep it as intended just so it doesn't needlessly complicate the question, but if you have a simple way to implement it, be my guest Jul 5 at 9:18

# Are you a probabilist or a physicist?

• Is it fine to be a function in one language and a full program in another? Jul 23 at 2:13
• "Your programs should be true polynomials" - did you mean polyglots? Jul 23 at 7:50
• @Bubbler Yep, that's fine Jul 23 at 11:35
• @pxeger No, clearly you should code mathematical functions involving powers, multiplications and additions to solve this ;) Typo fixed Jul 23 at 11:36

# Calculate the integer square root of a matrix

• Should really be "Calculate the integer square root of a matrix", because there acan be multiple square roots. E.g. [[18, 63], [14, 67]] also has as square root, the given solution divided by 11.
Jul 31 at 23:16
• I think it should be "Calculate an integer square root of a matrix", since "the integer square root" is the language you would use if there were only one. If you find combining "Calculate" with "an" a bit awkward, you could substitute "Determine" or "Find". Aug 4 at 2:22

# Pinpoint the typo!

Write a program that finds the location of an error in its own code!

The program itself must output either nothing or an empty string (or an appropriate equivalent in your language).

Let n be the length of the program in bytes, which must be at least 2. For an integer k with 1<=k<=n, if the kth byte of the source code is deleted, then the resulting program should output the integer k (and nothing else), in as many cases as possible.

Outputs may be 0-indexed if preferred, so that omitting the kth byte outputs k-1, but the choice of indexing must be consistent across all k.

Error messages do not count as valid output unless they are of exactly the required form.

Your score is the number of integers k for which the above condition is satisfied, divided by n. Highest score wins, with ties broken by smallest n.

### Example

Consider the program blob() in a fictitious language. Suppose that:

blob() outputs nothing (this is a requirement)

lob() outputs 1 (right)

bob() outputs 2 (right)

blb() outputs 3 (right)

blo() outputs 4 (right)

blob) outputs nothing (wrong)

blob( outputs 6: Syntax error` (wrong)

Then the score would be 4/6 = 0.66666667

• This might be abused by simply making a very long answer.
– rues
Aug 5 at 20:06
• Aug 5 at 20:11
• @user Yes, I did wonder about that, although such answers might still be interesting. Ideas for a better scoring system? Number of 'wrong' answers is not great, because of very short answers.... Aug 5 at 20:12
• What I did with my 'Quantum quine' question, which is similar, is for the scoring system count the number of chars that it doesn't work for. Aug 6 at 11:23
• @emanresu A The problem I see with that is that very short programs would get an unreasonable advantage. E.g. any 4-byte program that does nothing gets 4 without even trying to accomplish the task... Aug 6 at 13:24
• Perhaps it would be better if the unaltered program must output Hello World or something... Aug 6 at 13:27
• @aeh5040 I also ruled that each answer had to have at least one functional result... Then again, quines do have to be at least a certain size. Your choice. Aug 7 at 10:45