# Sandbox for Proposed Challenges

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

Sandbox FAQ

## Posting

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

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

## Discussion

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

• Parts of the challenge you found unclear
• Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

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

## Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

# Posted here

• What is the order each rules applied? For example, for rules "11=12", "12=21", "22=3". If input is "1112", should it be "1112 -> 1212 -> 2121" or "1112 -> 1221 -> 131" or "1122 -> 1222 -> 123"?
– tsh
Feb 22 at 7:58
• All of them. See the original specification for Shue in the linked challenge, or the interpreter. Feb 22 at 15:11
• As challenges should be self-contained, I suggest you add the mathematical definition from my post (and maybe an informal explanation of how the rules are applied non-deterministically) Feb 22 at 16:46

# Convert to UTF-∞

• I believe if Unicode code points are used up. They are most probability caused by CJK characters. Until then, there are already >50% used code points represent CJK characters. And characters used by Chinese dialect other than Cantonese (HK source) are still missing in Unicode.
– tsh
Feb 22 at 8:23

# Ragged slice

Your task is to slice a ragged list. Your input is a ragged list and two lists of integers, corresponding to the beginning index and end index of the slice, where the beginning index is inclusive and the end index is exclusive.

# Explanation

Let's start from the very basics. How does regular slicing work? Let's say we have the list [a,b,c,d,e,f] and we want the slice [1,4]. How does this work? Here is an illustration:

[a,b,c,d,e,f]
^ ^ ^ ^ ^ ^ ^
0 1 2 3 4 5 6
v v v v
[b,c,d]


This means that [a,b,c,d,e,f][1,4]==[b,c,d]. Ragged slicing is a bit tricky, so please make sure that the previous diagram is mostly clear. Ok, now ragged lists.

Let's first just draw the indices like previously for the list [a,[b,c],[d,[e]],f]:

[a, [b,c] , [d, [e] ] ,f]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
0 1 1 1 1 2 2 2 2 2 2 3 4
0 1 2   0 1 1 1 2
0 1


Now, let's see what a slice of [1 1, 2 1 0] would look like:

[a, [b,c] , [d, [e] ] ,f]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
0 1 1 1 1 2 2 2 2 2 2 3 4
0 1 2   0 1 1 1 2
0 1
v v v v v v
,c] , [d, [
c] , [d
[[c] , [d]]


The last steps are probably the most confusing. But basically we want to do two things, in the following order:

1. Trim the left side until an element, or an opening bracket is encountered. Do the same on the right side, except with a closing bracket.
2. Balance the remaining brackets and keep the depth of every array element the same as in the input, by wrapping the output in brackets.

Now, let's look at what happens when we have empty arrays. In fact, let's replace every letter in our previous example with an empty array:

[[] , [[] ,[] ] , [[] , [[] ] ] ,[] ]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 4
0   0 0 1 1 2   0 0 1 1 1 1 2   0
0   0       0   0 0 1
0
v v v v v v v v
,[] ] , [[] , [
[] ] , [[]
[[[] ] , [[]]]


Notice that for the empty array, the starting bracket doesn't have an index. This is because for an empty array, an index of 0 is already "one past the end" in an empty array, so there is no smaller index for the beginning.

If we would have used index 2 1 0 0 as the ending index, then this would have happened:

[[] , [[] ,[] ] , [[] , [[] ] ] ,[] ]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 4
0   0 0 1 1 2   0 0 1 1 1 1 2   0
0   0       0   0 0 1
0
v v v v v v v v v
,[] ] , [[] , [[]
[] ] , [[] , [[]
[[[] ] , [[] , [[]]]]


Lastly, let's see what happens if the slice is empty. We'll use [1 1 0, 2]:

[[] , [[] ,[] ] , [[] , [[] ] ] ,[] ]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 4
0   0 0 1 1 2   0 0 1 1 1 1 2   0
0   0       0   0 0 1
0
v v v
] ] ,


Here after step 1, the input just disappeared. We'll just return the empty list [].

# Rules

Your input will contain only lists (no numbers, letters, etc.), and the starting and ending index. Indices can in bounds or one past the last in some array. Indices are non-empty lists of non-negative integers. The starting index is not greater than then ending index.

You can choose the order of the indices and also if they are 0 or 1 based (but they must be inclusive-exclusive).

This is so shortest code wins.

# Meta

This is a bit tricky to explain. If there were parts that were unclear, or poorly written, etc. then please comment. If you think there is a better explanation, please also let me know.

• I don't get why sometimes the opening bracket is indexed, and sometimes not. Could you explain? Feb 27 at 16:41
• @pajonk I've added a paragraph explaining that. Basically it only happens for empty lists (that the starting bracket doesn't have an index). Feb 27 at 16:57
• Ok, that was a little confusing. Suggestion: replace empty lists with elements (like numbers) and disallow empty lists - wouldn't this be +/- equivalent and easier to explain? Feb 27 at 17:06
• I would suggest simply index any elements and the ending of an array. So for example, Array [1, 2, 3] is indexed as [ 0=>1 1=>, 2 2=>, 3 3=>​ ]. And a slicing simply exclude the ending element.
– tsh
Mar 1 at 7:56

# Draw the Ukrainian Flag

Draw the Ukrainian Flag

• "horizontally down the middle" -> "horizontally across the middle"
– att
Mar 18 at 21:54
• @att oops, fixed Mar 18 at 21:57
• Ginger u stole my challange idea :D (i thought it was too easy so i didnt post it) Mar 19 at 0:23

# Remove unmatched brackets

• "containing of brackets"->"containing brackets"? Also, what characters to expect apart from brackets? You may also want to specify that we want to match the closest brackets together (inferred from example). And I think you lost first 543 in your example. Mar 17 at 19:51
• @pajonk Fixed those. Mar 17 at 20:19
• What's with the 1 in the third testcase? Mar 18 at 6:30
• @ophact A typo. Mar 18 at 7:44
• "the input will only contain those and lowercase letters" - but the example string contains digits too! Could you remove them? Mar 23 at 6:39
• @pxeger Oops... Mar 23 at 8:28
• I think it would be good to add a definition of "matched." It may not be immediately obvious to everyone who reads the challenge why [abc]def] should result in [abc]def and not [abcdef], since you could view either close bracket as being matched with the open bracket. Mar 23 at 14:06
• @DLosc Done. (filler) Mar 24 at 3:26

# CGCC Rocket Biking

Something I found while looking through some old files. It seemed like a neat idea for a code golf challenge.

## The intro

One of the most popular events at the annual Cyclist's Grand Competition for Charity (CGCC) is the rocket bike parcours. The rules are simple: Inspect the parcours and place a bet on wheather is it possible to reach the end with a speed of 0 m/s exactly. If those who said that it is possible can't prove it, the rest of the participants win, else the one to prove it wins.

## The parcours

The rules for the parcours are as follows:

• A parcours consists of uphills, downhills and flat bits.
• The up-/downhills accelerate/decelerate the bike by 10 m/s.
• On the flat bits the driver must either speed up or slow down manually, again, by 10 m/s. They mustn't do nothing.

## The inspection

The participants don't know the parcours beforehand. They may only walk through it once before placing theirs bets and one other time to devise a strategy. The use of any form of map of the parcours is forbidden and leads to disqualification.

We model the parcours as a sequence of /, \ and _ for the hilly bits and the flat bits. Given such a sequence as the input, output whether the parcours can be finished with a speed of 0 m/s at the finish line or not (validator). If yes, take the sequence again and output a sequence of + and - as an instruction for the driver on what to do on the flat bits (generator). The drivers start with a speed of 0 m/s.

## The rules

• This is , shortest answer wins.
• Submit two programs that validate the parcours and generate the instructions for the driver if valid. Their length is added together for scoring.
• The I/O format may be freely chosen, as long as it is not ambiguous.
• The generator program only needs to work on valid parcours.
• Each program may only read the input once and it may not save the input while reading.
• The input length is not bounded.

## The examples

Input:
\_///

Formatted for clarity:
/
/
\_/

Validator output:
Falsy (The driver will come to a stop before the last uphill)

Input:
\_\__/

Formatted:
\_
\__/

Validator output:
Truthy

Generator output:
--+

Input:
\_\_\

Formatted:
\_
\_
\

Validator output:
Falsy (The driver will finish the parcours with at least 10 m/s)


## The meta

• Is anything unclear?
• Should anything be changed to improve the qustion?
• Do you have a better idea for the acronym pun? :)

If this gets enough upvotes to be posted, I'll add more and longer test cases.

• Suggestion: Split it to two challenges (validating and generating instructions). Mar 27 at 18:00
• Good challenge! Just one question: what does may not save the input while reading mean? Does "save" just mean saving to a file, or does it include variables too? In some languages, it would be impossible to do anything with input without saving it somewhere, even if not in an explicitly named variable. Mar 27 at 18:02
• @pajonk That's a good idea, thanks! Mar 28 at 12:22
• @SylvesterKruin I think the idea behind that could also be written as "The program may not work on more than one character of the input at any time.", i.e. reading the entire input bit-by-bit into a var and doing transformations on that isn't allowed. I used the wording from the file directly, which wasn't a good idea as it is rather lacking in other places too. Mar 28 at 12:23
• this does seem like an interesting challenge! I do think the while thing about only reading the input once is A) confusing and mostly unnecessary, and B) kinda against the meta consensus against unobservable requirements. The code obviously takes a single text string in somehow, but what it does with that is not controllable. Also seconding the suggestion to split this into two challenges/get rid of one of them, as determining whether it is possible is a different matter from determining how to precisely stop at the end Apr 3 at 1:08

# Interpret +-=

• I would say this is a fairly simple challenge, but it could still produce some interesting answers. However, it definitely needs some more clarification on input specifications. Should code read from a file? Prompt for input once and interpret that program? Prompt for an input, interpret that, and then repeat? Mar 23 at 21:36
• @des54321 prompt, interpret, repeat, as i think that has more golfing potential Mar 23 at 22:07
• However I do realize that it won't exactly work on TIO... so idrk Mar 23 at 22:10
• A few things I think you should specify : Is this code-golf or something else ? Can we assume input is always valid? Usually we do the task just once, it can be a full program or a function tacking arguments. Mar 24 at 12:17
• @AZTECCO 1. this... is code-golf... are you ok? 2. Yes you can. Mar 24 at 21:13
• Instead of explaining my suggestions in a comment I edited adding comments, feel free to reject anything you don't like. Hope it helps a bit.. Nice challenge btw! Mar 24 at 21:41
• I would perhaps add a test case that results in negative output(s) (e.g. +=----= resulting in 1 -3) and perhaps one with multiple adjacent == (e.g. --== resulting in -2 -2). Apart from that I'd say it's good enough to be posted. And it may be simple, but it's good to have some simple challenges every now and then. :) In fact, I'd say it becomes harder and harder to come up with easy challenges suitable for beginners that aren't duplicates yet, so +1 from me. (I've already prepared a solution for when it goes to main.) Mar 28 at 15:31
• @KevinCruijssen how about some of these? Mar 28 at 19:42
• @BowlingPizzaBall Looks good. 👍 Mar 28 at 20:35

# Convert angle to clock time

• I strongly discourage strict output format restriction. Also, you may want to specify that only integer angles will be inputted (if that's the case). Apr 14 at 12:18
• @pajonk Is it okay now? Apr 14 at 12:30
• As long as identifiable as clock times by humans is also a list of hours and minutes and other reasonable formats - I'm fine with that :-) Apr 14 at 12:38
• Outputting 0:00 instead of 12:00 is invalid, right? Apr 17 at 23:34
• @Steffan Yes. The 12-hour time convention should be used. Apr 18 at 0:01

# How normal is this group?

Let $$\(G, *)\$$ be some group. That is, for all $$\x, y, z \in G\$$, the following axioms hold:

• $$\x * y \in G\$$
• $$\x * (y * z) = (x * y) * z\$$
• There exists some $$\e \in G\$$ such that $$\x * e = e * x = x\$$
• There exists some $$\x^{-1} \in G\$$ such that $$\x * x^{-1} = x^{-1} * x = e\$$

For some group $$\(G, *)\$$, we define a subgroup of this as a group $$\(H, *)\$$ for some subset $$\H \subseteq G\$$. The trivial subgroups of a group $$\(G, *)\$$ are when $$\H = \{e\}\$$ (the identity element of $$\G\$$) and when $$\H = G\$$.

For the sake of convenience, we will denote $$\x * y\$$ as $$\xy\$$. Let $$\N\$$ be a subgroup of $$\G\$$. We say that $$\N\$$ is normal if, for all $$\g \in G\$$ and $$\x \in N\$$, $$\gxg^{-1} \in N\$$. For any group, the trivial subgroups are normal, and so any group has at least 2 normal subgroups.

For example, let $$\G = \{0,1,2,3\}\$$ and $$\x * y = x + y \bmod 4\$$. The subgroups of $$\G\$$ are $$\\{0\}\$$, $$\\{0, 2\}\$$ and $$\\{0,1,2,3\}\$$, all of which are normal. Therefore, $$\(G, *)\$$ has 3 normal subgroups.

Given a finite group, output a positive integer $$\n \ge 2\$$ counting the number of normal subgroups of the input. You may take a group as input in any reasonable manner, including but not limited to:

• The set $$\G\$$ (as a set, list, etc.) along with a black-box function $$\* : G \times G \to G\$$
• A square matrix representing the Cayley table of the group. You may choose whether to take $$\G\$$ as a separate input
• A collection of triples $$\(a, b, c)\$$ where $$\a, b, c \in G\$$ and $$\c = a * b\$$ (the order of such a triple is irrelevant, but must be consistent for all triples)
• etc.

This is a challenge, so the shortest code in bytes in each language wins.

## Test cases

G
∗ : G×G → G
output

{0,1,2,3}
a*b = a+b mod 4
3

• You may want to define a subgroup: a group defined by the same operation $*$ as $G$, with elements which are a strict subset of $G$. Apr 12 at 8:29

# King of the Cards

• This seems like it won't be particularly strategic May 9 at 18:01

# Whyte Notation Translator

• I think the scoring is sufficiently punishing to answers missing any cases that none will be able to make use of that in interesting ways. May 16 at 19:25
• @RadvylfPrograms That's true, i guess i could change that to a multiplication instead. How about S = codesizefunc1 * (1+u) + codesizefunc2 * (1+v) ? Or maybe using the square root on u and v ? May 16 at 19:27
• Those might work too, but then you run into the risk of people optimizing the combination of code size and cases handled, and getting something boring like x=>"AA20". I think it'd be better to just use the sum of the code sizes as the score. Since it seems like parsing the os into indices into a list is probably going to be how most solutions work, and that's the interesting part of the challenge (since the outputs can't really be compressed), you might even consider allowing a third program that provides the list of names, that's weighted to count for less. May 16 at 19:39
• @RadvylfPrograms What would be the purpose of the third program and the reduced weight of it ? May 18 at 10:27
• Since there's no interesting way to compress the list of names May 18 at 13:28
• Prairie and Adriatic are both mapped to oOOOo. May 28 at 20:34
• @Arnauld You're right, it's corrected and posted May 29 at 17:13

# Invert A Non-commutative Function

• I like the challenge, and I think you explain it really well. For I/O, there's a lot of reasonable ways to allow it to be done, for output you could probably just allow a list (or string representation of a list) which contains tuples, lists, sets, clearly delimited strings representations of pairs, etc. of two elements. May 28 at 16:30

# Tell me how many there are, in Polish

Today, you're going to be writing Polish. No, not Polish notation—Polish, the actual language spoken in Poland.

Given a number and a noun, output a Polish sentence telling me that there are that many of that thing, using the appropriate template below.

The input consists of an integer in the range from 0 to 200, and a string of 1 to 10 lowercase ASCII letters (called the "noun"). You may accept these inputs in any reasonable format.

The output must consist of one of the below output templates, where the number in the template (if any) has been replaced with the input integer, and the word kot in the template has been replaced with the input noun.

## Output templates

If the input number is 0, then use the output template

Nie ma żadnych kotów.


If the input number is 1, then use the output template

Jest 1 kot.


If the input number ends with 2, 3, or 4, but does not end with 12, 13, or 14, then use the output template

Są 4 koty.


In any other case, use the output template

Jest 8 kotów.


Note that the special characters used in these templates are:

• ż (in "żadnych") – U+017C Latin small letter Z with dot above
• ó (in the suffix "-ów") – U+00F3 Latin small letter O with acute
• ą (in "Są") – U+0105 Latin small letter A with ogonek

You may output these characters in any reasonably common character encoding (including HTML entities), and you may use combining characters instead of precomposed characters (or even a mixture of the two).

## Test cases

0 pomidor -> Nie ma żadnych pomidorów.
1 kwiat -> Jest 1 kwiat.
2 dom -> Są 2 domy.
5 wilk -> Jest 5 wilków.
13 komputer -> Jest 13 komputerów.
24 but -> Są 24 buty.
101 kurczak -> Jest 101 kurczaków.


## Do plurals in Polish really work that way?

No, the way it actually works is much more complicated.

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

• Suggested test-cases with 3-digit numbers ending with 02-04, 12-14, x2-x4 (with x>1) and outside those ranges (>101). Jun 3 at 8:11

# Find the winning Mormon Bridge card

Mormon Bridge (also called Oh Heck, similar to Oh H***) is a card game played (at least by me) with a standard Rook deck. A standard Rook deck includes cards 1-14 in 4 suits, which are black, red, green, and yellow, and a Rook card. Each round, a card is taken from the deck. It's suit is chosen as "trump." Then, players take turns playing cards. We'll call the suit of the first players card "sub-trump". If the Rook card is played, it wins. If trump was played, the highest trump card wins. Otherwise, the highest sub-trump card wins.

Your goal is to take input for:

• Trump
• Sub-trump
• Cards played

and output the winning card. You may take input in any reasonable manner, swapping suit colors for numbers is fine, as is taking input for all cards played in order instead of separating the first card. , so shortest answer in bytes wins.

## Test cases

(note that input can be taken in any reasonable format, these are written in a human-readable format.)

Trump: Red
Cards played: Red 4, Rook, Black 14, Yellow 7
Output: Rook

Trump: Green
Cards played: Red 14, Red 8, Green 2, Yellow 6
Output: Green 2

Trump: Yellow
Cards played: Red 5, Green 7, Red 12, Black 6
Output: Red 12


## Meta

What tags should be on this? Are the rules clear enough?

• I think the rules are pretty clear. It would be great if you could add some examples of input => expected output Jun 7 at 21:14
• @mathjunkie added test cases Jun 8 at 1:05

# Is it a valid list?

• Suggestion: allow input also with {} or (), maybe even allow separators to be spaces or semicolons. Jun 12 at 5:28
• "Outputting by erroring/not erroring is not allowed" - I presume this is to prevent people from submitting solutions which are just eval. This tends not be a good approach, and I think solutions like eval are still interesting. Maybe instead you could ask that people post solutions which don't directly do any parsing into one Community Wiki answer, like is sometimes done for builtin answers to catalogue-style questions. [contd...] Jun 12 at 9:18
• @pxeger Good idea :P Jun 12 at 9:19
• [...contd] But I think disallowing error output is not the right way to go about it, because (1) people will still post them, but wrapped in a try-catch or whatever, which is a no more interesting answer; and (2) people can write interesting answers which don't use eval, but which can be shorter using error output as a kind of "short-circuiting" output mechanism. Jun 12 at 9:20
• Suggested falsey test-case: [[]][[]], which may erroneously be accepted by eval-like solutions Jun 12 at 12:22
• @pxeger Added.. Jun 12 at 19:46

# Fix my FizzBuzz

• You need some more test cases, to cover: inputs that are already valid and don't need shuffling, inputs with only numbers, inputs with no numbers, inputs with FizzBuzz in them. Jun 26 at 16:40
• @pxeger Done. (filler) Jun 26 at 19:47

# Which R version is it? It's Peanuts!

• Related yesterday
• I'm pretty sure there's some other challenge more closely related to this one. But I personally don't care as I love this kind of challenges anyway. ;) yesterday
• Ah, here it is: related yesterday
• @Arnauld thanks! I hope it won't be considered a duplicate... yesterday

# Pairs at every distance

Given a list x of 2 or more integers, output whether there exists a pair of equal integers in x separated by exactly n elements for all n such that 0 =< n < length(x)-2.

In other words: output whether, for all overlapping slices/windows of length n, there exists at least one slice/window where the head of the slice/window equals the tail.

For example: [1, 1, 3, 2, 3, 1, 2, 1] will return truthy, because

[1, x, x, x, x, x, x, 1]
These 1s are separated by 6 elements, the most possible in an 8 element list,

[x, 1, x, x, x, x, x, 1]
These 1s are separated by 5 elements,

[1, x, x, x, x, 1, x, x]
These 1s are separated by 4 elements,

[x, 1, x, x, x, 1, x, x]
These 1s are separated by 3 elements,

[x, x, x, 2, x, x, 2, x]
These 2s are separated by 2 elements,

[x, x, 3, x, 3, 1, x, 1]
These 3s are separated by 1 element (as are the 1s, but either pair is sufficient),

[1, 1, x, x, x, x, x, x]
And these 1s are separated by 0 elements, the least possible.


But [1, 1, 2, 2, 1, 1] will return falsy, as there is no pair of equal elements separated by exactly one element. That is, there is no length 3 slice/window with a head equal to it's tail. See all length 3 slices/windows below:

[1, 1, 2]
[1, 2, 2]
[2, 2, 1]
[2, 1, 1]


Standard I/O applies, input does not have to allow negatives, or input can be a string of characters, etc.

Anything reasonable as long as you're not cheating :)

## Examples

Truthy

[1, 1]
[1, 1, 1]
[3, 3, 7, 3]
[2, 2, 1, 2, 2]
[2, 1, 2, 2, 2]
[1, 3, 1, 3, 1, 1]
[1, 1, 3, 2, 3, 1, 2, 1]
[1, 1, 1, 1, 1, 1, 2, 1]


Falsy

[1, 2]
[1, 2, 1]
[1, 2, 3, 4]
[3, 1, 3, 1, 3]
[3, 1, 1, 3, 1]
[1, 3, 1, 1, 3, 1]
[1, 1, 2, 2, 2, 2, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 2]


# Huffman Decoding

Write a programm which takes two strings as input and prints a text.

The first argument is a Huffman Tree, serialized in the following format:

• every ascii character except ~ is always a leaf, if ~ is the first characater it is also a leaf.
• <tree0><tree1>~ is a tree where <tree0> is the left subtree and <tree1> is the right subtree.

Example: ab~cde~~~ generates this tree:

 ┌─┴─┐
┌┴┐ ┌┴─┐
a b c ┌┴┐
d e


where a would have the key 00, b 01, c 10, d 110 and e the key 111.

The second argument is a text that has been compressed with with the Huffman code that is defined by the first parameter. This bit-string can contain any bit sequence (also null-bytes and non-printable characters) and is not byte aligned, therefore it has been encoded with a variation of the standard Base64 encoding:

• the characters used for the encoding are the standard base64 characters: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
• the bitstring is broken up into 6-bit chunks and mapped to this characters
• if the last chunk is smaller than 6 bits, a character with this prefix is used, and padding characters are added to the string:
• - : the last chunk was five bits long
• = : the last chunk was four bits long
• =- : the last chunk was three bits long
• == : the last chunk was two bits long
• ==- : the last chunk was one bit long

Example:

bits:       1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1
chunks:    |1 1 1 1 0 1|1 0 1 0 0 1|1 1 0 1 0 1|0 0 0 1 1 0|1[0 0 0 0 0]|
characters:       9           p           1           G           g
base64:     9p1Gg==-


Your programm has to decode the text encoded in the second parameter and print it to stdout.

You have to provide your source code encoded in the way described above. The length of your encoded source code + the length of your serialized huffman tree will be the winning criterion.

TODO: example input

• It would be helpful to explicitly state the 64 characters used in the encoding. I presume they're A-Za-z0-9+/ but (especially if you're expecting people to implement that part explicitly) it's best to make the problem self-contained. Oct 8, 2012 at 16:23
• Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.)
– user58826
Jun 9, 2017 at 15:30

## Polygon prefixes

Polygons are named after the number of sides that they have. A pentagon has 5 sides, an octagon has 8 sides. But how are they named? What's the name for a 248-sided polygon?

All polygons are suffixed with -gon. There are specific prefixes for each polygon depending on the number of sides. Here are the prefixes for the lower numbers:

3 - tri
4 - tetra
5 - penta
6 - hexa
7 - hepta
8 - octa
9 - nona
10 - deca
11 - undeca
12 - dodeca
13 - triskaideca
20 - icosa


Polygons with 21 to 99 sides have a different system. Take the prefix for the tens digit (found on the left column), the ones digit (right column below), and then stick a "kai" between them to get (tens)(ones)gon.

20 - icosi       | 1 - hena
30 - triaconta   | 2 - di
40 - tetraconta  | 3 - tri
50 - pentaconta  | 4 - tetra
60 - hexaconta   | 5 - penta
70 - heptaconta  | 6 - hexa
80 - octaconta   | 7 - hepta
90 - nonaconta   | 8 - octa
| 9 - nona


The 3-digit sided polygons are named in a similar fashion. A 100-sided polygon is called a hectogon. Take the hundreds digit, find it on the column for ones digits, then stick a "hecta" to its right. Now number off the tens and ones like above: (hundreds)hecta(tens)(ones)gon. If the hundreds place digit is a 1, don't put the prefix behind "hecta".

So, given an integer (3 <= n <= 999), return the name of an n-sided polygon. n-gon is not a valid answer :P

As with all code golf, shortest code wins.

Is the description good? Would it be harder if I instead asked for the number of sides, given a name?

• What is a 101-sided figure called? "hectahenagon"? Is "hena" from the column for ones digits you mention? If so, then what is a 111-sided figure called? I'd say "hectaundecagon", but then that comes from a column where "hena" is not present. Feb 11, 2013 at 11:15
• @Gaffi: Yep, it's hectahenagon, from what Google says. Feb 11, 2013 at 16:03
• I am going to take this if you allow me or if you don't respond May 30, 2017 at 1:13

## Code golfing problem: Surface classification

The task: Given a surface-word reply with the classification of what surface it is.

Example 1: Input: aba'b' ----> Output: 1T

Example 2: Input: aabcb'c' ----> Output: 3P

Bounds on the problem: Since there are only 26 letters, there will never be more than that many labels. Additionally output should be in the form S,nT,mP for n,m positive integers.

Background: In the study of algebraic topology students are often presented with diagrams such as the one below. The represent instructions for how to assemble a surface. The assembly is prescribed as: if there are two edges labeled with the letter x then glue them together so that the arrows point the same direction. To make our job easy, topologists have discovered an algorithmic way to classify surfaces using 'words' assembled from these 'plane gluing-diagrams'.

Choosing a corner arbitrarily (top right) and orientation (ccw) we read off the labels on the edges where an inverse appears wherever the arrow points against the orientation. In this case the 'word' that represents this plane model is given as abab.

A surface word is a string that contains the letters a,b,...,@ up to some letter @ and each letter is contained in it exactly twice. In the two occurrences of each letter: 0, 1, or 2 of them may be postfixed by a ' which I am considering using to represent 'inverse' (opposite orientation).

If in a surface word all letters appear twice: once without the ' and once with it (f.ex. ba'b'a) then we say that the surface the word represents is orientable. If a surface is orientable then it is necessarily the direct sum of n Tori for some non-negative integer n. If this condition doesn't hold (like in aab'b) then the surface represented is non-orientable: in this case it is the direct sum of m Projective Planes for some positive integer m.

Once you have found out if the reduced word is orientable or not, the final answer is given as follows. If orientable and number of unique letters in the reduced word is 1 then output should be S. Otherwise if the number of unique letters in an orientable word is n (it will be even) then the output should be sT where s = n/2. If the word is non-orientable then the output should be mP where m is the number of distinct letters in the reduced word.

The goal is to take as input some surface word, reduce it via reduction rules 1-6 and then classify it as a sphere, some number of connected tori, or some number of connected projective planes. Here are the 6 reduction rules where ~ represents 'reduces to':

Let M,A,B,C,D be surface words, x be a single letter, and juxtaposition represents concatenation:

1. Cycle Rule: If M = AB then M ~ BA
2. Flip Rule: M ~ M'
3. Sphere Rule: Axx'B ~ AB
4. Block Rule: ABC ~ ADC if B is a surface word and B ~ D by 1 or 2
5. Cylinder Rule: If M = AxBCx'D, then M ~ AxCBx'D
6. Möbius Rule: If M = AxBxC then M ~ AxxB'C ~ AB'xxC

I am looking for input on:

• should this be code-golf or programming-challenge?
• how would scoring work?
• ???

If I feel satisfied with the question in a few days I'll post it to the site.

• If, for each input, there is only one correct output, then it should probably be code-golf. The scoring criteria would then be source code length. Jun 8, 2013 at 14:33
• Yes, this is the case. In general however there is not a unique series of applications of the reduction rules for any given instance.
– Kaya
Jun 8, 2013 at 16:21
• I don't think the order of explanation is correct. You should explain reduction before talking about "the reduced word". And "reduce it via reduction rules" doesn't entirely make sense, because the rules are presented as equivalences rather than reductions, and most of them don't have a "natural" direction. Jun 10, 2013 at 8:49
• It's also occurred to me that you haven't defined the notation M'. Does it just consist of toggling the orientation of each token, or does it also reverse the entire string? And do you have test cases which between them force implementation of all of the reduction rules? Jun 11, 2013 at 8:32
• Good call on the string inverse, yes you have the right idea and I will make it clear. I have a lot of test cases from when I did a number of these computations by hand in a university course and (anecdotal experience) I am pretty sure that it is possible to force the use of all the reduction rules (except maybe 4 which is really just a meta-rule for convenience when doing proofs). Additionally you have alerted me to some concerns regarding the form of the proper output: it's definitely underspecified. I'll put some work into this today.
– Kaya
Jun 11, 2013 at 14:04

# Fastest Code: checking if interval pairs overlap

Given an unsorted input of many interval pairs (50+), write the fastest algorithm to determine if they do not overlap.

An interval pair is said to overlap if interval x and interval y are overlapping.

Example input 1:
interval x , interval y

10-25, 50-60
10-15, 25-60


Output:
Can be in any true false format.

false (They overlap)


reasoning:

a.x overlaps b.x
a.y overlaps b.y


Example input 2:

10-25, 50-60
20-30, 25-30


Output:

true (they do not overlap)


reasoning:

a.x overlaps b.x
a.y does not overlap b.y


Scoring:

[not sure...]
brute force gives a worst case n^2 runtime

• It's hard to understand what the program is supposed to do. It's better to give three separate self-contained test cases than to mix them together with extra identifiers which won't be in the actual input. But if I understand correctly, there's nothing difficult here at all. It's just interval overlap testing (two ifs) done twice for no obvious reason. Jul 5, 2013 at 19:45
• The problem is that there will be a very large input. I'm thinking > 50 lines. Jul 5, 2013 at 20:50
• I'm not sure whether or not to score it based on time, or worst case runtime. Jul 5, 2013 at 20:59
• Instead of asking for overlap, ask for disjoint: "Check if a family of intervals is disjoint". I also think it would be more interesting if you give intervals in interval notation but I you should at least specify whether or not the endpoints are included. Dec 21, 2013 at 7:41

I have no idea how to create a good code golf question!

See this description of a ray tracer with source code that fits on a business card. The author stopped when the code size was 1337 bytes.

Achieving identical output, optimise for minimum code size. Execution time is not relevant.

• I think what you have here is a straight ahead golf. All languages. You need only define the requirements. Do you want identical output or do you want "good output encompassing <list of features>"? Oct 6, 2013 at 17:22
• For a minimum feature list I'd suggest something like (1) it is ray tracer (2) supports point-like lights and shadow + ambient light (3) supports mirrored (implies reflection) and matte surfaces (3) all objects are sphere and overlaps are allowed. With no requirement for (a) anti-aliasing; (2) finite sized light sources; (c) atmosphere effect or (d) depth of field; or (e) tiling and gradients. Notice however, that the example supports at least (b), (d) and (e). Oct 6, 2013 at 17:29
• BTW--The one you linked can get a little bit more with #define Q return (R was already taken for the rand wrapper) and #define O operator. Oct 6, 2013 at 17:33
• I suggest reading the Teapot question in the sandbox Mk IV and the comments - it's not the same question, but some of the same issues are relevant, and it might give you ideas for improvements to the spec. Oct 6, 2013 at 22:48
• Yes. Read the teapot question for guidance. Ultimately I decided that one was too big, but we did get into some pertinent details. Dec 1, 2013 at 9:48
• This sandbox post has had little activity in a while and little positive reception from the community. Please improve / edit it or delete it to help us clean up the sandbox.
– user58826
Jun 9, 2017 at 15:32

# Countdown: Federal Holidays in the United States

Inspired by this question:

Christmas Countdown

Write a program or script that will countdown to the nearest U.S. federal holiday, at any given time, and will switch the display to an appropriate greeting during each holiday.

The following holidays must be tracked, and announced:

Holiday                         Date                    Greeting
==========================================================================================
New Year's Day                  Jan. 1                  Happy New Year!
Martin Luther King, Jr. Day     3rd Mon. in Jan.        Happy Martin Luther King, Jr. Day!
President's Day                 3rd Mon. in Feb.        Happy President's Day!
Memorial Day                    Last Mon. in May        Happy Memorial Day!
Independence Day                Jul. 4                  Happy Independence Day!
Labor Day                       First Mon. in Sept.     Happy Labor Day!
Columbus Day                    2nd Mon. in Oct.        Happy Columbus Day!
Veterans Day                    Nov. 11                 Happy Veterans Day!
Thanksgiving                    4th Thu. in Nov.        Happy Thanksgiving!
Christmas                       Dec. 25                 Merry Christmas!


The strings listed under "Holiday" and "Greeting" are all free. Shortcuts like "Merry X-mas!" or "Happy 4th of July" will count against you - the full and proper holiday names are free, so there's no good reason not to use them.

The following strings are also free, only when used as a label for time units or in advertising the next upcoming holiday:

days
hours
minutes
seconds
milliseconds
until
time


On any given non-holiday, the program must show a count-down timer which displays time remaining at least down to the second, and updates the display with an accurate value (according to the system clock) at least once per second. Time remaining until a holiday must be counted as the time until midnight (00:00:00) on that day.

How the days, hours, minutes, and seconds (and milliseconds, if you choose) are displayed is up to you, so long as all mandatory items are present and it is clear which numbers represent which value. Again, the strings defining units of time are free so there's no really good reason not to use them. (Though you won't be penalized for not using these strings, so long as it is still unambiguous which time units are which.) The program should also make apparent which holiday is being counted down towards.

On any given holiday, the program must cease displaying the countdown timer and instead display the appropriate greeting for that holiday from 00:00:00 until 23:59:59.

After a holiday is over, at 00:00:00 the next day, the holiday greeting must go away and be replaced with the countdown timer for the next holiday.

• Name of language
• Score (length of golfed code, minus free characters)
• Golfed code
• Total length of golfed code
• Total number of free characters used
• Un-golfed code, with descriptive comments

The program must be capable of running accurately (according to the system clock) at any time, and must be able to run indefinitely. The only limitations to this should be those imposed by the host computer or the nature of the programming language.