# What is the Sandbox?

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

See the Sandbox FAQ for more information on how to use the Sandbox.

## Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

• How are tags added to questions? – guest271314 Jan 9 '19 at 7:51
• @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] – James Aug 29 '19 at 15:19
• Why no featured anymore? Can't we have it auto-added or something? – S.S. Anne Sep 26 '19 at 15:57
• @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary – caird coinheringaahing Sep 29 '19 at 13:43

# Count the Matches

Given a stripped-down regular expression, estimate (rules below) the number of lower-ASCII-only strings that it matches fully (meaning it matches the whole string).

You should handle the following:

• Literals/sequencing
• Vertical bars ...|...
• Groups (...) or (?:...)
• Special characters escaped with a preceding \
• Character classes [...]
• Complemented classes [^...]
• The standard classes ., \d, \w, \s, \D, \W, and \S
• The escape sequences \f, \n, \r, \t, and \xhh
• The quantifiers ?, {x}, and {a,b}

# Estimation Rules

## Literals

Literals, obviously, match only one string.

aaaaa --> 1


## Classes

The estimate for a class is the number of characters that it can match. If multiple are seen, then their individual counts can be multiplied. There are also the standard classes: \d is [0-9], \w is [_A-Za-z\d], and \s is [ \n\t\r]. \D, \W, and \S are the complements of their lowercase versions.

a.b --> 127
\D --> 118
[a-gd-k] --> 11

# Tired Sumo Fighters

This is a simple KOTH challenge in which you program a bot to push other bots out of a ring. Each round consists of two bots, and every bot will compete against each other bot at least 10 times. The reason that this KOTH is different from other similar KOTHs is that the bot only is very tired, so it only has a little bit of energy, and it cannot waste it.

## Moving

Your bot can move around the ring (An 11x11 square) using one of 10 commands:

moveForward() //Moves forward
moveLeft() //Moves left
moveBackward() //Moves backward
moveRight() //Moves right
moveToward() //Moves toward enemy
moveAway() //Moves away from enemy
approachCenter() //Moves toward center of ring
approachEdge() //Moves away from center of ring
moveCounterClockwise() //Moves counter-clockwise around ring
moveClockwise() //Moves clockwise around ring


However, each movement takes energy. As a parameter, set the energy consumption (Defaults 1). If one bot stays still and the other runs into it, the moving bot pushes the still bot. If the bots run into each other, the bot who allotted more energy pushes. If there is a tie, the bots do not move.

## Pushing

Say that bot 1 and bot 2 are fighting. If bot 1 is at position (-4,5) and bot 2 is at (-2,5), there is one space between them. If each bot moves toward the opponent, the one who spent more energy moves forward. If there is a tie, the bots do not move. If a bot has any coordinate with an absolute value greater than 5, it loses. If any bot has energy under 0, it loses. It is possible to live with 0 energy, but you will be quickly pushed out of the ring. Every bot starts with 200 energy

## Detection

To find your opponent or yourself, use these commands:

locateSelf() //Returns as array [x,y]
locateOpponent() //Returns as array
opponentEnergy() //Returns opponent's energy


## Example

function sumoChamp() {
if (energyLevel() > opponentEnergy()) {
moveToward(5);
} else {
moveCounterClockwise(2);
}
}


As you can see, a basic sumo bot takes just a few lines. However, a smart sumo bot would be able to overpower it, and a genius bot could even figure out its pattern and destroy it. You cannot build systems designed to target specific bots that have already been designed. To save information for later, store it in your bot's function, like this:

sumoChamp.opponentResearch.avgEnergy = 4


# Rules

Standard loopholes not allowed

Entries can be in any language that supports functions and arrays, but all entries will be converted to JavaScript before the game starts.

• There should be more specification. What's the exact distance the bot will be pushed? – user202729 May 19 '18 at 16:46
• @user202729 1 space – Redwolf Programs May 21 '18 at 2:26
• Perhaps my understanding is not complete, however would there be an optimum solution that would either guarantee a win or tie? i.e. move to the centre of the ring and then subequently push the opponent toward the outside of the ring with half of the remaining energy that you have each step. If the opponent uses less energy they are pushed, otherwise they will have wasted more energy than the first bot and eventually run out of energy prior to the first bot, thus get push out – Moogie Jul 20 '18 at 4:09

# Bananagrams

Bananagrams is a tile-based word game where you race to make crosswords and use all your letters before everyone else does. In the original game, finishing your crossword allows you to say "peel", causing everyone to draw another letter tile. Whoever finishes their crossword when there are no more letter tiles to draw is the winner.

# Challenge

You will be given a list of letter tiles and your task is to arrange them into a crossword using this list of alphabetic words as your dictionary. In the spirit of the board game, you need to do this as quickly as possible.

# Input and Output

Input to your solution will be a list of letters and you should output a grid of letters. You will need to read in the list of words.

As an example: given abcdeiloopswy, your program/function might produce

cowboy
a l
side
p


# Test cases for timing

• aabcdeeefghiijklmnoopqrssttuuvwxy

more TBA

# Rules

• No abusing standard loopholes
• Input and output may be in any convenient format.
• You must load the linked word list exactly, not a stripped down version.
• You may assume that you will be given only lowercase letters
• You may assume that there is at least one possible crossword from your given set of letters.
• This is a challenge, so the answer with the shortest execution time in each language wins.
• Be sure to post execution time and CPU as part of your solution.
• Why do solutions need to be written in Python? What if a solution calls out from Python to another language? – isaacg May 7 '18 at 21:23
• @isaacg: one way or another, there needs to be a way to compare solutions on performance. The other option would be to make a test driver for several languages, but I don't want to write 10 test drivers. – Beefster May 8 '18 at 2:15
• I don't see why you need a test driver like that. Just require submissions to read from a file and write their outputs to a file, and have your test script read their file to evaluate their solutions. – isaacg May 8 '18 at 5:12
• @isaacg: how would I be able to score on execution time? I guess I could ditch that as a scoring requirement in favor of a time limit. – Beefster May 8 '18 at 18:17
• Time the execution of the submission, with something like the time command. Or require submissions to time themselves. I'm not suggesting you change your rules at all, just use different timing. – isaacg May 8 '18 at 18:29
• @Beefster (time command is a Linux utility, which can be used to measure the execution time of any process, which is also what TIO used to measure the time, however do note that TIO is not acceptable for measuring time) – user202729 May 9 '18 at 13:36
• @isaacg: How would I adjust for differences in language speeds? Solutions in C would have a massive advantage over solutions in pretty much any other language. – Beefster May 9 '18 at 19:28
• @user202729: See above comment – Beefster May 9 '18 at 19:29
• @Beefster A lot of the time, algorithmic speed is more important than complilation quality, so it'll matter what language the program is easiest to write fast code in, which is not always C. Take a look at past fastest-code contests. C++, Rust, and Nim are popular. – isaacg May 9 '18 at 19:39
• @isaacg: After looking around, you have me convinced. I thought language advantages were a bigger deal than they really were. – Beefster May 9 '18 at 20:13
• I'm not a fastest-code expert (ask Dennis for more details?), but I'm afraid that using a "sample benchmark program" doesn't solve the "on which machine" issue, because on some machines some operations can be done faster than other machines. – user202729 May 11 '18 at 1:05

# Construct any Sporadic Simple Group

There are 26 sporadic simple groups. Your task is to write a program which defines an operation isomorphic any of these groups.

Input: Two symbols that represent elements of the group. You can choose how these symbols will be represented (characters, numbers etc.).

Output: The result of the operation on the input.

Taken as a whole, the operator defined must be isomorphic to one of the 26 sporadic groups.

I don't actually know anything about group theory; I haven't even taken a course in it yet, just read some Wikipedia and thought this could be interesting. If it isn't trivially solvable, maybe someone could post it?

• I think this has potential but needs a bit of work. 1. As it stands, it's almost 26 questions in one. Intuitively I would expect the smallest group to be the most golfable, but to really be sure I'd have to make a semi-serious effort with all 26. I suggest picking one group or at most one family of groups. 2. "Symbols" is a bit vague. I'm not sure whether I'd be allowed to use an array which must be a permutation of the numbers 0 to N for suitable N (which is the obvious way of doing some if not all of the groups). 3. You haven't specified a winning condition. I assume code-golf. – Peter Taylor May 20 '18 at 21:59
• 4. (Hadn't thought of this when I wrote 2). Since every finite group is a permutation group, with a suitable input format this can be reduced to codegolf.stackexchange.com/q/1490/194 . So if you want to tackle it as group action, you need to constrain the input representation and running time quite harshly. However, it reminds me of codegolf.stackexchange.com/a/26423/194 where golfing a representation of a simpler perm group was an interesting subtask. The solution might be to ask to generate all elements of the group in a non-trivial representation (as perms or reduced words). – Peter Taylor May 20 '18 at 22:07

# K-th largest element

Find the k-th largest element of n elements in at worst O(n)

It shouldn't be affected by

• element arranging
• element range
• RNG (if you use)
• This can be done with a heapify algorithm in O(n). Not that complicated. – Beefster May 19 '18 at 20:33
• @Beefster But (1) it's not trivial (at least for golfing languages, C++ has built-in nth_element) and (2) your algorithm is wrong (it takes O(n+k log n), which is about O(n log n) for k in O(n)) – user202729 May 20 '18 at 2:36
• "O(n)" implies "at worst O(n)". Big-O notation only upper-bound the complexity, it doesn't lower-bound. (so an algorithm that is O(n) is also O(n²), O(n!), ...) – user202729 May 20 '18 at 2:37
• Also, please "Write your challenge just as you would when actually posting it." -- people find it hard to understand your posts, so it would have a lower change of them not understanding your challenge. – user202729 May 20 '18 at 2:38
• To the two people who have upvoted this answer: @user202729's point is relevant to you too. Do you seriously think this is ready to post with just a title and tags? – Peter Taylor May 20 '18 at 22:14
• @PeterTaylor No because of the character limit xd (I thought it was a 0 vote, didn't know it's a +2/-2) – l4m2 May 21 '18 at 1:20
• @user202729 nth_element is average O(n), worst O(n^2) iirc? – l4m2 May 21 '18 at 1:21
• ... I think so. cppreference says "O(n) on average", and doesn't specify the worst case behavior. You may want to add "the algorithm must have deterministic runtime". – user202729 May 21 '18 at 1:23

Meta

Polyomino detection itself is a duplicate. And there was also a very similar question concerning simple connectedness of a tiling pattern. So I won't submit.

# Holey polyomino

A polyomino is a plane polygon consisting of equally-sized squares connected at edges. A polyomino might have a hole if it contains a region with a square on all four sides.

# The challenge

Determine if a collection of squares is a polyomino with a hole.

## Input

The input will be a matrix of 0s and 1s, where a 1 indicates a square in that position. For example, the top left nonomino in the picture above could be:

## Output

A truthy or falsey value for whether the input represents a polynomino with a hole.

## Test cases

Arrays of rows:

[[1, 1, 1], [1, 0, 1], [1, 1, 1], [0, 1, 0]] => TRUE

[[1, 1, 1, 0], [1, 0, 1, 0], [1, 1, 1, 0], [0, 1, 0, 1]] => FALSE

• Are holes of size greater than 1 considered? For example (as a list of rows since formatting is limited in comments) [[1111] [1001] [1111]] – Kamil Drakari May 22 '18 at 20:21
• @Kamil Drakari yes, that counts. I'll add a test case. And there's no need for the input to be square, so I'll change that too. – ngm May 22 '18 at 20:24
• Proposed test case [[0, 1, 1, 1], [1, 1, 0, 1], [1, 0, 0, 0], [1, 1, 1, 1]] => FALSE to cover the situation where there's an empty square with non-empty squares in all four directions but which still has a path to the exterior. – Peter Taylor May 23 '18 at 7:42
• I don't think this challenge is likely to get much traction. I've just proposed a simpler "Is this a polyomino?" question which I think should go first, and might open up possibilities for other challenges. – ngm May 23 '18 at 14:37
• The simpler one is, as I wrote in a comment there a duplicate. This one is not a duplicate AFAIK, so you should stick with this one (if any). – Stewie Griffin May 23 '18 at 18:54
• Can there be two (or more) holes? – Stewie Griffin May 23 '18 at 18:58
• @StewieGriffin I've deleted the other one. And this one is very close to codegolf.stackexchange.com/questions/69030/… so I don't think I would proceed. – ngm May 23 '18 at 18:58
• @StewieGriffin the two-or-more hole thing could work, but I would be inclined to make it a question about topology rather than polyominoes. As in "calculate the genus of this surface" where the surface is represented by the binary array as in my examples. – ngm May 23 '18 at 19:07

# Go shopping!

You're shopping for four specific items. Your town contains fifteen shopping malls. Unfortunately you can't always find the item you want at the nearest mall. You want see whether you can purchase the four items on a single shopping trip.

For each item, there is a list of malls (given as coordinates) where the item can be purchased. Some malls however will only sell you a given item if you visit that mall first. Furthermore, the entrances and exits to the malls are badly placed and you can only visit malls in increasing order of coordinates.

Examples:

1. Item 1 can be purchased at mall (7, 2) but only if you visit that mall first. It can also be purchased at mall (3, 1).
2. Item 2 can be purchased at mall (7, 1).
3. Item 3 can be purchased at mall (3, 2), (4, 2), (5, 2) or (6, 2).
4. Item 4 can be purchased at mall (7, 2).

With this scenario, it's not possible to purchase both items 2 and 3 in one trip.

1. Item 1 can be purchased at mall (3, 3), (4, 3), (5, 3), (6, 3).
2. Item 2 can be purchased at mall (3, 2), (4, 2), (3, 3) or (4, 3).
3. Item 3 can be purchased at mall (6, 1), (7, 1), (6, 2) or (7, 2).
4. Item 4 can be purchased at mall (4, 1), (5, 1), (6, 1) or (7, 1), but only if you visit that mall first.

In this secnario, you would visit mall (4, 1), (4, 2), (6, 2), and then (6, 3), and successfully purchase all four items on a single trip.

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

• 1. "(given as coordinates)": always 2D and in integers? 2. "Some malls however will only sell you a given item if you visit that mall first." How is this indicated in the input? 3. "in increasing order of coordinates." What's the order in dimensions higher than 1D? Lexicographic? – Peter Taylor May 24 '18 at 13:49
• I think your two examples need more separation. It was difficult to tell whether the middle "With this scenario..." line connects to the first, second, or both lists. I would add "Example 1:..." and "Example 2:..." to show the distinction. – Kamil Drakari May 24 '18 at 15:03
• @PeterTaylor 1. Yes. 2. I don't mind how that special case is indicated in the input; you could have two separate lists, or a boolean with the coordinates. 3. You can choose which coordinate(s) to increase. – Neil May 24 '18 at 19:04
• How come in the first scenario I can't go (3,1) (3,2) (7,1) (7,2) and purchase all four items? Do items need to be bought in order? If so, that should be explicitly stated. – AdmBorkBork May 25 '18 at 14:03
• @AdmBorkBork You can't go from (3, 2) to (7, 1) because 1 < 2. (And you can't go from (2, 3), to (1, 7) either, for the same reason.) – Neil May 25 '18 at 15:40
• Ah, both coordinates need to be non-decreasing. That could probably be made a little more clear. – AdmBorkBork May 25 '18 at 15:58
• This should be reflavored as an IKEA trip. :P – Beefster May 29 '18 at 19:01

# Softcode

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

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

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

# The Challenge

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

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

Input/output format is up to you.

# The catch

Not your interpreter code should be golfed. Your JSON code should be golfed. Or, more specifically, golfable. That is: you will have to present a JSON file that, if fed to your program, will solve a given golfing challenge and will have smallest size out of all JSON files presented here. This will determine the winner; the size of the interpreter code is not relevant.

# Technical details

Unfortunately, given how this challenge is defined, if I would define any particular problem your JSON-program should solve, one could get away with a simple trick of defining one particular command in one's JSON programming-language that solves this particular problem. To instead encourage creating a language that is as concise as possible, this challenge will be split into two phases. Phase 1 will last a month since posting this challenge; you will then write your compilers or interpretes. Then I will, on random, choose one challenge from this site that has at least 5 upvotes. (If this challenge proves unsuitable for this problem, I'll roll the dice again.) Afterwards, Phase 2 will begin, when you will present a JSON-program that solves this challenge.

Be creative.

# Example interpreter

For reference, below is a simple JS interpreter of a Turing-complete JSON programming language. Of course, it does not strive to define a language suitable for golfing. (I hope there are no bugs in this interpreter, but I don't feel like testing it now.)

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

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

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

var vars = {};

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

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

• What's the winning criterion? – feersum May 26 '18 at 23:29
• @feersum Size of the JSON program. But nevermind. I realized how hard did I screw. Trivially, the correct solution is to pass the sole property name to an already-existant golfing language interpreter. I'll post a take 2 in a while... – gaazkam May 27 '18 at 8:12

You have been given the following tree structure make from dictionaries and lists

{'snapshot': {'outer': {'inner': {'dir1': {'blob':
[{'file': '8ke45'}, {file1: '72d4kl'}]},
'dir2': {'blob': [{'file1': 'fa65e'}]}},
'something': {'blob': [{'thing1': '8447v'}]}}}


The dictionary contains all the directories and blobs(arbitrary file) in a given directory, in this case 'snapshot,' which contains the directory outer and no blobs. 'Outer' has all of its corresponding directories and blobs and so on until the end of the branch. Blobs objects are a dictionary with the key 'blob' and the value of a list of dictionaries containing the filename and content hash.

the tree looks like:

snapshot
|_outer
|__ inner
|     |__dir1
|     |   |__file
|     |   |__file1
|     |__dir2
|     |   |__somefile
|     |__another_file
|__ something
|__thing1


the objective to create trees files, wherein each directory is the hash of the hash of the underlying directories or blobs.

e.g the 'inner' file:

    name: 7j3429ds
contents: tree 8340dnwh28a          --di1
tree sh2991ka86n          --dir2
blob 12046bshs63          --anotherfile


You may hash the file using any known checksum ie. sha1, md5 ect. This is an example for the hash of the contents of a file:

def hash_(name):
hash_object = hashlib.sha1(bytes(str(name), encoding='utf-8'))
hex_dig = hash_object.hexdigest()
return(hex_dig)


An Example of the final output given the dictionary:

{'snapshot': {'inner': {'dir1':{'blob': [{'file': '8ke4528dgsk'}},
'dir2': {'blob': [{'file1': 'fa65ek97n37'}]}}}


should look as such:

45334423112
|_ds498kdh72b
|__ ak37ka729sm
|     |__193bal7q8gl
|__ o8pdn279ax8
|__9y728s7ndsn


note the names of the files are just random hashes in the example when actually computing the hashes, the hash should consist of the hashes or all trees and blobs contained within that tree

45334423112 contents:

tree ds498kdh72b


ds498kdh72b contents:

tree ak37ka729sm
tree o8pdn279ax8


ak37ka729sm contents:

blob 8ke4528dgsk
blob fa65ek97n37


note that the blobs are the value of the filname key in the lowest level directory of the tree ie.

'dir1':{'blob': [{'file': '8ke4528dgsk'}]}


The winning criterion is the shortest solution.

If the question is seemingly vague, please comment on what you're unfamiliar with. Good luck ;)

• would any which way mean returning the first character of the file name is fine? :P – ASCII-only May 27 '18 at 11:08
• "any way you want" is too open to abuse. x => 0 is a valid hash function, just have a lot of collisions. – user202729 May 27 '18 at 11:10
• Cool thanks, very valid feedback :) – Charl Kruger May 27 '18 at 11:20
• Your example has a mismatching [. (besides -- actually, the sandbox is relatively inactive, it's hard to get feedback) – user202729 May 27 '18 at 13:41

Given some lists of strings containing only lowercase letters, slice the first few (1 to length) characters for each string in each list, so that when each list is joined without separating symbol, it can't be any other list's possible expression.

For example, for {[ab,cd],[abcd]}, {ac,a} is valid, but {abc,a} is not because abc can also mean [abcd].

You can assume the result exist. If more than one solution, either output all of them or one of them. Shortest code win.

# Link the pairs of points

Given some pairs of points on a plane, connect each pair with a simple polygonal chain such that any two different chains don't have any common points. The points won't necessarily be integral. Any two points in the input won't overlap.

Samples:

[{(0,1.2),(1,2)}] -> [{(0,1.2),(2.6,1),(1,2)}] # Output doesn't need to be optimized
[{(0,0),(1,1)},{(1,0),(0,1)}] -> [{(0,0),(1,1)},{(1,0),(9999,0),(0,999),(0,1)}]


Reasonable I/O method allowed. Code-golf, shortest code win.

• I think you want to describe a simple polygonal chain. – user202729 May 28 '18 at 5:37
• Is there any two points in the input that have the same coordinate? – user202729 May 28 '18 at 5:38
• @user202729 The chain shouldn't intersect with itself and other chains – l4m2 May 28 '18 at 10:23
• Is it a sufficient answer to sort the points by angle and join them all up in order, and if not why not? – Peter Taylor May 29 '18 at 14:13
• @PeterTaylor You are to link each pair, not to link all of the points together – l4m2 May 29 '18 at 14:22