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

# Simplify a Cycle

Given a path of vertices that form a cycle on a graph, output a simple version of the cycle. That is, if a vertex appears twice, snip out the part in between the two appearances.

## Context

Let $$\u\$$ and $$\v\$$ be vertices of graph $$\G\$$. If there is a cycle from $$\u\$$ to $$\v\$$ of length $$\n\$$, then there exists a simple cycle from $$\u\$$ to $$\v\$$ with length $$\\le n\$$.

This is because any cycle $$\v_1, e_1, v_2, e_2, ..., e_m, v_m\$$ with a vertex visited twice (that is, $$\v_i = v_j\$$ for some $$\v_i\$$ and $$\v_j\$$ in $$\G\$$, where $$\ i < j\$$), can be reduced to $$\v_1, e_1, ..., e_i, v_j, e_{j+1}\$$ and still be a valid cycle between $$\u\$$ and $$\v\$$.

For the sake of this challenge, the edges connecting vertices will be ignored, as the edge taken when going between vertices will be assumed arbitrary.

## Worked Example

Take the graph $$\K_5\$$:

One cycle between vertices $$\1\$$ and $$\3\$$ might look like:

That is, the path taken is [1, 2, 5, 4, 2, 3, 5, 1]. However, that cycle can be simplified to:

Which has path [1, 2, 3, 5, 1]. This cycle is a simple cycle, as only the first and last vertices are equal.

## Rules

• There will always be a simplier cycle in the input.

• The input will be a list of vertices in a graph. Whether you take those as numbers, characters or some other way is up to you.

• There will always be at least 2 vertices.

• Each vertex has degree >= 2.

• Input and output can be given in any reasonable and convenient format.

• As the input represents a cycle, the vertex that is the start and end of the cycle will not be in the input.

Note that the simple cycle may not be the shortest cycle, and the shortest cycle may not be the simple cycle.

## Test Case

Assuming that numbers are used as vertex labels

### Input

[1,2,3,4,2,5]
[4,3,6,2,3,8,5,2,8,7]
[1,1,2]
[1,2,7,2,7,2,3,7]


### Output

[1, 2, 5]
[4,3,8,7]
[1,2]
[1,2,3,7]


This is code golf, so make sure you simplify the byte count of your answers.

## Meta

• Is the challenge a dupe of anything?
• Are the test cases clear?
• Is this somehow trivial in any way?
• A worked out example would be great. I don't get why aren't all vertices from the input in the output. Aug 19 at 8:16
• Is this really "given a path that may include cycles, remove the cycles"? Aug 19 at 8:42
• @UnrelatedString no, it's "given a cycle between two vertices, return the shortest cycle" Aug 19 at 8:43
• The last test case seems to contradict that, since the shortest cycle between 1 and 7 seems like it should just be [1,2,7]. I guess what I'm getting at is there needs to be a clearer spec and/or worked through example :P Aug 19 at 8:47
• So is this a 1-D graph or what? Are you only giving us the X coordinates or what? Or am I just not understanding a thing? If we have the coordinates (both X and Y) is this basically removing adjacent coordinates that are colinear? Aug 19 at 15:50
• @Steffan these numbers arent coordinates; they're just the labels on the nodes of the graph. the input is a path that exists on the graph, meaning you can get from each node in the list to the next node in the list by following a single edge Aug 22 at 2:35
• Maybe an example program will help. Aug 26 at 14:29
• Questions for @lyxal . Aug 26 at 14:39
• Suppose his answers are what I expect, this should work. Aug 26 at 14:40
• It was at 4 char left. Sorry for another post. Why must [1,2,7,2,7,2,3,7] be [1,2,3,7] ([1,2,...,3,7]) and not [1,2,7] ([1,2,7,...])? Aug 26 at 14:42
• The mathematical definition deems that both are correct. You might want to clarify or add that to the test case. Aug 26 at 14:42
• E Aug 26 at 14:44
• ...dited to match the test cases. The last post was too long. Aug 26 at 14:44
• Not a comment on the challenge itself, but I like the four-state CnR system! Aug 8 at 11:21
• Does the cop reveal which of the 4 programs satisfy which of the criteria 1-4? Aug 8 at 11:39
• @pajonk Yes they should. I'll edit it to make it clear.
– Wheat Wizard Mod
Aug 8 at 11:39
• @UnrelatedString I have a feeling this is equivalent to "standard" CnR, where to become safe you need to reveal your language (or other features the challenge is about) - or are there some differences I missed? Aug 8 at 11:42
• @pajonk In a normal CnR if a robber ever gets your answer you cannot score. However here your answer is cracked after 10 days you still get to score your answer. On a lot of CnR's people will delay the reveal to give robbers an extra chance, this ruleset allows you to do that without having to sacrifice your score.
– Wheat Wizard Mod
Aug 8 at 11:45
• @WheatWizard I get it now, thanks! This indeed makes more sense. Aug 8 at 12:16
• Requiring that languages can run on FreeBSD seems unnecessarily restrictive to me, it being a pretty niche OS in the grand scheme of things. Aug 15 at 16:15
• @pxeger The idea is that if it is Free, and runs on both linux and freeBSD it is very likely to run everywhere. And users should be able to sandbox either linux or freeBSD. It also doesn't seem like a very high bar to cross actually. If you can find a language that can't be run on freeBSD but has otherwise wide support that would make a compelling case.
– Wheat Wizard Mod
Aug 15 at 17:52

# Quantise a list code-golfarray

In music production, quantisation is the process of "aligning" recorded notes to the beat, to remove the variability caused by imprecise human playing.

In this challenge, we will implement an abstract and approximate version of quantisation, representing notes as runs of positive integers, and using zeroes to represent gaps. The "beat" will be defined as every second note, starting with the first (even indices, 0-based).

Given a list of non-negative integers, insert or remove zeroes such that every run of non-zeroes begins on an even index (using 0-based indexing).

Runs of non-zeroes may not be split or joined together if they weren't already in the input. In other words, a zero cannot be inserted or removed if it only has non-zeroes next to it.

The minimal number of insertion/removal operations must be performed. If a removal is possible, it should be preferred over an insertion.

## Test cases

todo

blah blah code golf rules

• Removal of double negatives: "No runs of non-zeroes may be split..." -> "Runs of non-zeroes may not be split...", maybe also "...zero cannot be inserted or removed if it only has non-zeroes..." -> "...zero can only be inserted or removed if it has at least one zero..." Aug 30 at 17:24
• The latter conversion is incorrect, because [0, 3, 4] can become [3, 4] because the zero has an end-of-the-list next to it rather than a zero. I agree this could be clearer though Aug 30 at 19:28
• that's not supported by the current phrasing either: "a zero cannot be inserted or removed if it only has non-zeroes next to it". If that zero can be removed, you're saying it has something other than non-zeros next to it, which means you're saying that either "end-of-the-list"s or 3s are zero. Addendum: my head hurts Aug 30 at 19:34
• @thejonymyster My head hurts too and now you see why lol. The way I drafted this in my head is slightly different from how I wrote it down, which doesn't help Aug 30 at 19:38
• Maybe instead of splitting / joining runs, just say the number of runs of nonzeros cant change between input and output. That handles the 0s on the ends situations too and is probably simpler Aug 30 at 19:41
• I mean, the first sentence (before "in other words") explains it pretty well already. Maybe I should just remove the second rephrasing. Aug 30 at 19:45

# Use "e" or a suffix?

## Background

In Māori (the indigenous language of New Zealand), to make a verb a command the verb is either preceded by "e" for example, "oma" (to run) -> "e oma", or, it's given a passive ending to make it a passive verb for example "kōrero" (to speak, talk, say, etc) -> "kōrerotia".

Besides some edge cases with intransitive verbs and different dialects, the rule is that if the verb has exactly two short vowels or one long vowel (which have macrons over the top of them like "ā") then the verb is preceded with "e" otherwise it is given a suffix.

## Challenge

Your challenge is to determine whether which case a verb fits in to. If it should be preceded by "e" output a truthy value, otherwise output a falsey value.

## Rules

• You can assume that all the input will be lower case.
• You may not take input with combining diacritics.
• Because there are very few, if any verbs in Māori with only one short vowel, and the fact that what happens in that case depends on dialect, you don't need to handle those cases.
• This is so the shortest answer wins.

## Test cases

ako -> true
kai -> true
haere -> false
tū -> true
āwhina -> false
kōrero -> false
huri -> true


## Meta

• Thoughts on the combining diacritics rule?
• Are there any other rules that should be added?
• Maybe add a test case with a single short vowel? (Or if there are no actual mono-moraic verbs, consider including in the spec that such an input doesn't have to be considered.) Jul 25 at 7:27
• @UnrelatedString I was thinking about that, I haven't been able to find any verbs with one short vowel, but I just can't be sure that there are none so I'm not really sure what to do about it. Jul 25 at 7:40
• Fix your link! (It's the second one.) Aug 30 at 23:26
• @Laurel Ah, thanks. I'll replace it with a new one. Aug 30 at 23:29
• Tag: decision-problem Aug 31 at 1:26
• You should also probably specify that it has to be exactly two short/one long, and the cases are mutually exclusive -- e.g. say "...the verb has exactly two short vowels or two long vowels, but not both" Aug 31 at 15:02
• @Adam true, done. Aug 31 at 20:51

# Compute the Fabius function

• $$\f(x)\$$ always takes on rational values at dyadic rationals (i.e. $$\\frac m{2^n}\$$ with $$\m,n\in\mathbb Z\$$). It could also be interesting to restrict input to such values, and ask for a rational output.
• Forgive my ignorance, but is it even possible to exactly determine the value of the function for any given input $x$? Sep 5 at 23:03
• @97.100.97.109 What do you mean by "exactly"? There do exist algorithms which can approximate the value of $f$ to arbitrary precision for any given input. For example, from math se
– att
Sep 5 at 23:22
• I suppose the answer to my question is "no" (when the input is not a dyadic rational). In that case, how do solvers decide the level of precision with which to calculate the answer? I think that limiting to dyadic rationals is a good idea because then there is an explicit formula to calculate the values. Sep 5 at 23:38
• @97.100.97.109 I don't think the absence of an explicit, non-limiting formula should be a factor in that decision. How would you "exactly" calculate $\sin$ for arbitrary inputs?
– att
Sep 5 at 23:44
• I think it can make two challenges actually: first with f on dyadic rationals asking for rational output (no floating point errors); second with f at any input with stated required precision (maybe limited to interval 0-1). Sep 7 at 19:51
• I'd prefer keeping the function to [0,1] where it is defined by the cumulative distribution.
– xnor
Sep 10 at 22:08

# Convert integer to IEEE 754 float

The task is simple, given a 32 bit integer, convert it to its floating point value as defined by the IEEE 754 (32-bit) standard.

## IEEE 754

Here is a converter for your reference.

Here is how the format looks:

The standard is similar to scientific notation.

The sign bit determines whether the output is negative or positive. If the bit is set, the number is negative otherwise it is positive.

The exponent bit determines the exponent (base 2), it's value is offset by 127. Therefore the exponent is $$\2^{n-127}\$$ where n is the integer representation of the exponent bits.

The mantissa defines a floating point number in the range $$\[1,2)\$$. The way it represents the number is like binary, the most significant bit is $$\\frac 1 2\$$, the one to the right is $$\\frac 1 4\$$, the next one is $$\\frac 1 8\$$ and so on... A one by default is added to the value.

Now the final number is: $$\text{sign}\cdot 2^{\text{exponent}-127}\cdot \text{mantissa}$$

## Test cases

1078523331 ->   3.1400001049041748046875
1076719780 ->   2.71000003814697265625
1036831949 ->   0.100000001490116119384765625
3264511895 -> -74.24919891357421875
1056964608 ->   0.5
3205496832 ->  -0.5625


For this challenge assume that cases like NaN and inf are not going to be the inputs, and subnormals need not be handled, and you may output 0 for the case where the number represented is -0.

This is code-golf, so the shortest answer in bytes wins.

• Closely related. Kinda opposite task, but I think there are certainly overlapping techniques around reinterpreting a bit pattern from one type to another. Sep 22 at 0:22
• I don't quite understand what this challenge is asking for. Are we supposed to reinterpret the integer as a float? Oct 2 at 21:51
• @pigrammer yes. Oct 3 at 3:42
• @solid.py shouldn't all the digits be accurate, because there is no floating point conversion error when you are reinterpreting an integer as a float Oct 9 at 10:33
• @solid.py 1/2 + 1/4 + 1/8 + ... should be accurately stored, because, well it can be accurately represented by IEEE754, which is supported by most languages... Oct 10 at 15:51

• Is 10000001 actually 81? A simple web search shows 81 is 1010001 Sep 30 at 9:38
• -1 because of that Sep 30 at 9:39
• @py3programmer Since hexadecimal is in base sixteen, hexadecimal 81 is 10000001. Sep 30 at 14:27
• @py3programmer no. Hexadecimal is base 16. I've edited the post so you can remove your downvote. Sep 30 at 14:30
• There's a different way to calculate binary numbers in base 16? I didn't know that. Oct 1 at 2:46
• @py3programmer 81 in base 16 isn't the same as 81 in base 10, the same way that, e.g. 10 in binary is not equal to 10 in decimal. 81 in base 16 is 8*16+1 = 129 in decimal, which is indeed 10000001 in binary. Oct 2 at 18:59
• Since 16 is a power of 2, you can also convert each character individually into binary then concatenate -- 8 -> 1000, 1 -> 0001, 81 -> 10000001. Oct 2 at 19:18
• Yeah, I get you. I was think more in Python terms, bin(81) instead of bin(0x81) Oct 3 at 3:58

# Find a word in the dictionary of all possible words

• Can input use strings? (e.g. 123 and 231 for your example) Oct 2 at 21:47
• @pigrammer that's a default input method and thus should be fune Oct 2 at 22:00
• @solid.py that should be fine so long as tuples of arbitrary length can be handled Oct 4 at 19:19

# Generate QR code from string

I'm surprised to have not seen anyone doing this particular challenge yet.

The challenge is simple: Take input as a string, your task is to turn it into a QR code.

This challenege originally requires outputting to an image (or any graphical output), but to relax the restrictions down, you only need to output the result as a matrix (or a 2D array). A binary string (with splits between) is also acceptable.

And for sake of simplicity, you will only need to output a 25x25 QR code image (which is the most popular QR code size, I believe). For the input Version 2, the image should look like this:

You may not need to handle empty strings.

Standard loopholes are forbidden.

## More resources

• Can we output as a binary string Oct 9 at 9:28
• @py3programmer No, the output string must be full, correct image data. If you are using a binary string to later be used with metadata to output to a, say bitmap file, then yes, you can.
– oeuf
Oct 9 at 10:06
• You may consider turning this into a binary-matrix challenge instead. It would be easier to test on TIO and the like. Oct 9 at 21:02
• Also, it would need to be significantly more specified. Which version of QR code? Which kind of data? With which error correction level? (Challenges are supposed to be self-contained. So, ideally, the full algorithm should be explained.) Oct 9 at 21:05
• @oeuf I meant a binary string that describes whether each pixel is lighted up or not. The binary string would describe the pixels from left to right. Is that valid? Oct 10 at 3:50
– oeuf
Oct 10 at 5:32
• @Arnauld I have edited to relax the output restrictions down and specify more about the output. Thanks for suggestion! I am currently deciding on the error correction level
– oeuf
Oct 10 at 6:08
• Don't we need 2 inputs? One for the version, and one for the string we need to encode the qr code with? Oct 10 at 7:01
• @py3programmer No, we only need one input for the string.
– oeuf
Oct 10 at 7:14
• So you mean that using version 2, you'll encode the input as a QR code? Oct 10 at 7:17
• @py3programmer Yes.
– oeuf
Oct 10 at 7:18
• Can one use built-in libraries that generate QR codes? I think that the real would be to compute the image/matrix Oct 17 at 14:50
• @matteo_c Builtins are allowed, but builtins that solves the entire problem are generally disencouraged.
– oeuf
Oct 18 at 4:50

# Integer Bluffing (Still a draft)

It's an exciting night at the IGS casino, as a brand new table game is being revealed - Integer Bluffing. Bots from all over the network have come to have a chance at playing the inaugral game, and luckily for you, you just happen to have a seat at the table.

## The Rules of Integer Bluffing

At the beginning of a game of Integer Bluffing, each player starts with 20 tokens. A round of Integer Bluffing consists of 4 phases: (i) the deal, (ii) declaring, (iii) reacting, (iv) the showdown

### The Deal

Each round, 1 player is chosen to pay an ante, which increases during the game, into the pot. A random integer in the range [1, 8] is then "dealt" to each player. Players only know the true value of their own integer, and once an integer is given to a player, it can't be dealt to anyone else.

### Declaring

Starting with the player after the player who paid the ante, each player has the choice to either: a) decline to play the round (fold) or b) put 1 token into the pot and declare what their integer is (play).

Here's the twist - if choosing to play, the player doesn't have to tell the truth about the value of their integer - they can lie and declare they have an integer they don't have. The player also sets a flag whether they say they are bluffing or not - this can also be lied about.

Consider the following game with players A, B, C and D:

Player Integer
A 4
B 2
C 7
D 3

Assuming Player A paid the ante for the round, player B goes first in the declaring round. Player B sees that they have a 2, which is highly unlikely to win against other integers, so they fold.

Player C sees that they have a 7, so they choose to play the round. Wanting to trick Players D and A into putting a token into the pot, C declares that they have 2, and states they are not bluffing.

Player D sees that Player C allegedly has 2 and that they aren't bluffing. Player D knows that 3 is higher than 2, but knows that Player A might have a higher integer. Therefore, Player D decides to declare 6, not bluffing, in the hopes that Player A folds.

TODO: Continue writing

• "new table game"? Pfff, I've played this before :3 Oct 14 at 13:28
• You should state the number of players at the table (always exactly 4?), probably in the "The Rules of Integer Bluffing". I also think this sentence: "The player also sets a flag whether they say they are bluffing or not" should be reworded. I think "The player may also set a flag to say they are bluffing" works. Oct 14 at 19:58

# Tic, Tac, stub your Toe

• Welcome to Code Golf, and thanks for using the Sandbox! Currently, this is missing a winning criterion. If it's code-golf, you should probably specify. Oct 26 at 4:12
• I'd also recommend allowing looser I/O formats - see here. It's your challenge though, so if you really want to keep the strict formats, that's okay. Oct 26 at 4:17
• Don't know how to add tags to specify which type so right now it's just fastest possible solution wins. Also will update to remove number of testcases and commas from input. Oct 26 at 14:14

# Is this series of quotes valid python? code-golfdecision-problem

Python string parsing has quite a few edge cases. This is a string:

"a"


Putting 2 strings immediately after each other implicitly concatenates them, so this is also a string:

"a""a"


However, if you put 3 quotes in a row, it will create a "triple quoted string" which can only be ended by another triple quoted string. A triple quoted string can contain other quotes. These quotes will not end the string unless there are 3 of them. Thus this is valid:

"""a"a"""


Of course, you can combine these together, so this is a valid string:

"""a""""a"


And this:

"""""aaa"""""""""


A string is not valid if:

1. Any a appears outside of a string literal (would get SyntaxError: invalid syntax in python) OR
2. The end of the sequence is inside a string literal (would get SyntaxError: unterminated string literal (detected at line 1) in python)

Given a string containing 2 distinct characters, one representing a double quote and another representing any alphanumeric character, determine if it would be a valid python string, or invalid syntax.

You do not need to consider single quotes or how double and single quotes normally interact.

A array of booleans or a array of bytes would also be a valid input method.

This is , shortest answer wins.

## Test Cases

Truthy Falsy
"a" (1-1) "a (1)
"a""a" (1-2-1) "a"a" (1-1-1)
"""a"a""" (3-1-3) ""a"a""" (2-1-3)
"""a""""a" (3-4-1) """a"""a" (3-3-1)
"""""aaa""""""""" (5-9) """""aaa"""""""" (5-8)
"""""""""""" (12) """"""aaa""""""""" (6-8)
"a""a""a""a" (1-2-2-2-1) """" (4)
"a""" (1-3)

eval or exec or ast.literal_eval would be valid answers, though I hope to see more creative python answers as well.

• Well, well, well... exec can be used, so I'm claiming that. Ha! Oct 26 at 12:02
• Ok go for it. Not sure if I would count that as creative though Oct 26 at 12:03
• But the problem with this is, lambdas are not going to work in Python, and neither can normal functions. LHS = SyntaxError = RHS -> hence proved that eval and exec 4 byters are not valid. Oct 26 at 12:06
• And neither will normal inputs. Therefore, python would not work at all for this program, as input cannot only be provided. Oct 26 at 12:07
• Of course python works? You can take input as a string containing quotes Oct 26 at 12:08
• Though I assume it could be made to work in online interpreters like TIO and ATO, but not in IDLE style. Oct 26 at 12:08
• "string containing quotes": won't the string itself contain quotes? Like "a"a" when passed to an argument would be '"a"a"' Oct 26 at 12:09
• Notice the '? Oct 26 at 12:10
• The string will contain only double quotes. Oct 26 at 12:11
• Nod nod so when are you posting this? Oct 26 at 12:15
• When I get 3-4 votes Oct 26 at 12:17
• +1. You're 2 votes away :P Oct 26 at 12:19
• Hey why'd you claim exec? Oct 27 at 6:42
• Because it's boring. Note that duplicate answers are technically allowed but don't expect any votes Oct 27 at 6:52
• But it wasn't your idea to use it... I had to rack my brain for a minute to figure out an alternative approach :( Oct 27 at 11:10

# Does the sequence shut the box?

• small nitpicks: "roles" should be "rolls", "d6 dice" is redundant and should probably just be "six sided dice", and [] input is an edge case, and i think we should probably be able to assume input wont be empty. Oct 10 at 21:58
• actual feedback: cool challenge idea :-) a worked out example of how a specific sequence could be used to shut the box would be very helpful in allowing everyone to understand the challenge more Oct 10 at 21:58
• Thanks for the feedback. I cleaned those things up and added the example. Personally I like the inclusion of the [] input as it adds more thinking to the golfing (can one save bytes by formulating the general case to include the edge case). But I admit it may be weird to say "not playing the game is not a winning sequence". Oct 10 at 23:29
• ultimately up to you :-) thanks for humoring me :P Oct 11 at 2:03

# 50 digits of π in HQ0-9+-INCOMPUTABLE?

• Sorry few questions: are those the only commands avaiable? How would I append to the buffer then if I didn't want to use q/Q? Nov 11 at 0:18
• @DialFrost 1) Yes. 2) It's your job to figure it out. Nov 11 at 0:19

# Base Neutral Numbering System code-golfprimes

• Can we output as a nested list? Like <<1> * <<1>>> = [[[1],[[1]]]] Nov 22 at 20:40
• Also, can we omit the *? Most of the test cases omit it, only the last two use it. Nov 22 at 20:41
• Omitting the * from the test cases was a mistake. I think [[[1],[[1]]]] already qualifies by my rules since I allow replacing <> with [] and * with , . Nov 22 at 21:08

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

I'm considering changing some of the greetings, but I'm not quite sure what to.

• "Happy Martin Luther King, Jr. Day!" is just a mouthful and feels awkward, but shortening it to "Happy MLK Day" feels weird too - any other suggestions?
• I'm not quite sure "Memorial Day" should really be preceded by "Happy" - thoughts?
• Any others?
• I think it would be more interesting if the strings were not free, but you still required exact match. I would like to see the compression scheme used by contestants. Dec 7, 2013 at 12:04
• @JanDvorak This is meant to be code-golf, not kolmogorov-complexity.
– Iszi
Dec 7, 2013 at 22:11
• This challenge proposal has been inactive for over a month. I would like to take ownership of the challenge and make it ready for posting. Please let me know within the next 14 days if you have any objections and would still like to finish and post this challenge yourself.
– user10766
Nov 3, 2014 at 2:01

## Golf a random Human Genome fragment with non-random features

A totally random genome fragment is easy enough: just spit out the letters ATCG in random order, and you're done. So let's try something a little less random and more useful to science.

• Accept an argument from the user for number of base pairs (20bp-10000bp must be supported, more if you wish)

• Accept an argument from the user for GC content. This indicates how frequently the generated sequence should contain the G and C bases as a percentage of total sequence length.

• Include at least one complete gene in every request of 500bp or more, where a gene is defined as an otherwise random sequence that begins with a start codon triplet (ATG) and ends with the first stop codon triplet it encounters (TAG, TGA, or TAA). The distance between the start codon and the stop codon does not have to be a multiple of 3.

• Vary gene content (the portion of the fragment that is "gene", inclusive of the gene's start and stop codons) linearly with respect to GC content (when sequence >= 500bp). At the extremes, when GC content is 0%, gene content is 10%; when GC content is 100%, gene content is 60%.

• Output a single-strand sequence that complies with the above specs and the user's given parameters. (i.e. a single row of letters will suffice since it is trivial to deduce the complementary strand of the DNA given the sequence of one strand)

• Calculate the actual GC content %, actual number of genes, and actual gene content % in the resulting fragment, and output a status line below the sequence conforming to the example format below. Percentages may be rounded to one decimal place. Actual values may deviate by +/- 3% from the expected outcome based on user's input.

GC content: 42.1% | Genes: 3 | Gene content: 32.1%

• Use any Internet, library, or built-in gene sequence generation functions or databases. Roll your own.

Sufficient randomness:

• For the purposes of this challenge, any built-in random/pseudo-random number generator function, GUID generator, well-seeded cryptographic hash function, etc. is considered an acceptable source of randomness.

What-ifs:

• What if another start codon occurs before the stop codon? E.g. ATGXXXATGXXXXXXXXXXXXTAG. This is acceptable, but the "gene" length in this case is calculated from the most proximal start codon to the stop codon.
• What if another stop codon occurs after a stop codon? E.g. ATGXXXXXXXXXXXXXTAGXXXXXXTAG This is also acceptable, but likewise the "gene" length is calculated from the start to the most proximal stop.
• What if both of these things happen? E.g. ATGXXXATGXXXXXXXXXXXXTAGXXXTGA. Here again, the "most proximal" principle applies and the gene content is demarcated by the innermost start and the innermost stop.
• Do "orphaned" start and stop codons that do not demarcate a gene count as gene content? No.

This challenge is code golf, so shortest valid code wins.

Post example output from a 500-bp request with GC content between 35% and 65%, and have fun!

• "Use hardcoded fragments for anything other than the start and stop codons." - why not? Specifying criteria for what counts as enough randomness should make these useless in any case. Speaking of which, you need to specify criteria for what counts as enough randomness. Feb 28, 2014 at 5:54
• The only partial output example given flagrantly violates the spec. If the GC content is 42.1%, the gene content should be 31.05%, not 22.0%. The definition of "gene" is also imprecise: in the sequence AUGCCAUGCCUAGCUAA, which is the gene? Feb 28, 2014 at 12:02
• @PeterTaylor AUG starts the gene, then come the CCA, UGC, CUA and GCU triplets, none of which terminate the gene. Now if there were three C's instead of two, then UAA would be the terminating triplet and the whole sequence would form a gene. I agree the definition is imprecise, though. Feb 28, 2014 at 12:11
• @JanDvorak, (part of) the point of that example is that there are two AUG substrings. Feb 28, 2014 at 12:30
• Good points. I was hoping to avoid having too much text, but that came at the expense of less clarity than the challenge demands. Edit forthcoming. Feb 28, 2014 at 13:58
• Also, I've muddied the waters with RNA encoding and DNA encoding, (U vs T), which we can chalk up to a late night. Feb 28, 2014 at 14:00
• Revised accordingly, although I remain open to suggestions on how best to frame the standards for acceptable randomness. I want something that won't be exploited by answers making no effort at randomness, but that doesn't have the pain-in-the-butt factor of generating 10mb+ of data and running a Diehard test battery. Feb 28, 2014 at 17:20
• " This is acceptable, but the "gene" length in this case is calculated from the most proximal start codon to the stop codon. " - wait, what? In nature, the first one is the start codon, and the rest encode methionine. Under your scheme, methionine (which is an essential amino-acid) would be impossible to include into proteins. Your scheme would also be much harder to splice. Also, what happens to AUG substrings that are not triplet-aligned to previous AUG substrings? Mar 1, 2014 at 9:25
• In nature, the first ATG encodes the start of a protein coding region and defines a reading frame (triplet boundary), the rest encode methionine and the first triplet aligned stop codon encodes the end of the protein coding region (and no amino-acid). Mar 1, 2014 at 9:29
• As for the randomness, I'm not worried about the source of randomness (whatever native library is available is assumed to be good enough) but rather how the source of randomness is used (can we just start the sequence with a start codon and insert an end codon at just the right spot if it doesn't occur naturally sooner, then fill in with more random codons while avoiding ATG subsequences? Your "sufficient randomness" places constraints on the RNG (useless) but no constraints on how it's used (or that it needs to be used at all) Mar 1, 2014 at 9:34
• My true random number sequence generator was sitting there watching silently as I typed away the sequence ACACACACACACAC.... It's all okay. The TRNG was capable of producing something better - it just didn't really get to it. Mar 1, 2014 at 9:38
• In fact, the 3% tolerance for the CG content leaves no room for randomness when there are only 20 base pairs. I can shuffle the pairs and turn some A<->T or C<->G, but that's it. In fact, if the CG content is set to zero, the task is impossible: we want a gene content of 2 base pairs (which is itself impossible), but the start codon contains a G, and a single G in a 2bp sequence means a 5% CG content, 2% than is the limit. Not including a gene means that we are 7% under the gene content lower limit. Similarly, it's not possible to start or stop a gene with nothing but Cs and Gs. Mar 1, 2014 at 9:45
• Yeah, the 20bp starting point is a bad idea. The problem with start codons is that I considered introducing the idea of promoters and decided that would make the whole thing too complex. So in the absence of promoters there has to be some way to determine which Met is the start codon vs an amino acid and the easiest simplification is to have no Mets in the gene. Likewise, for "not triplet aligned", I'm trying to avoid having to go into explanations of frameshift mutations (even though a Frameshift% would be a cool parameter). Mar 1, 2014 at 14:29
• I am starting to think that all of these complexities should be included (this proposal stems from me noticing that most of the extant random DNA generators are pretty weak) and this should just be a popularity contest instead of a golf. Link a couple of good articles on the structure of the genetic code and let people add as many features as they wish. Making it a golf seems to be a catch-22 between too many compromises or a too-impenetrable wall of rules and conditions that will dissuade participation. Mar 1, 2014 at 14:33
• Perhaps a code-challenge where people earn x points for each complexity implemented?
– user10766
Mar 2, 2014 at 5:52

## DIM, the DIM Integer Machine

The DIM Integer Machine is an engine for producing integer sequences.

It has one major problem: To put it mildly, it's kind of...dim.

After producing a single number, it immediately forgets what sequence it was working on. The only thing it remembers is the last number it produced and the current direction of the search, either ascending or descending. (And of course, it remembers the methodology for finding numbers according to the commands it understands).

Consequently, the user is free to change their mind after each number by issuing a new command.

Suppose the DIM has just produced an integer square: 81

• User inputs P and submits the input.
• DIM understands that P is requesting the next prime number after 81
• DIM computes and returns 83.
• DIM forgets what it was doing.
• User inputs O.
• DIM understands that O is requesting the next odious number and returns 84.
• DIM forgets what it was doing.

The DIM functions only for numbers between 1 and 1,000,000. If the DIM reaches either extreme while performing a search it will reverse direction and continue searching.

(For example: If searching in ascending order for a prime when the last number was 999,999, it will encounter 1,000,000 which is not a prime, then switch to descending order and continue searching for the "next" prime by moving downward - 999,999...999,998, etc.)

The DIM remembers the last number as 1 when it is first activated for a searching session.

This is the full list of commands that the DIM understands:

• P - Next prime number
• S - Next square number
• F - Next Fibonacci number
• O - Next odious number
• W - Next wasteful number
• U - Next undulating number
• K - Next katadrome
• R - Reverse direction immediately; the next command will proceed in the new direction

Because the DIM is so...dim, it absolutely DOES NOT precompute lookup tables of numbers in these sequences. It is far too forgetful for that to work. The DIM also has no Internet connection, so it is unable to consult the Online Encyclopedia of Integer Sequences or other such sites. It also has a sense of pride, so it does not make use of built-in Fibonacci functions or NextPrime / PrimeIndex / PrimeTest type functions.

Given the parameters it knows - a starting number, a search direction, the type of number to find - it simply computes the next number by some means other than mere data retrieval.

The DIM may accept input interactively, or from a newline-terminated text file, or from a pre-initialized array. You may not pack extraneous data other than the command sequence into the input - play fair!

This is a code golf, so least number of bytes wins. Submit your program with output results for the following search sessions:

1. P O U R F O R U S O U R P R O W S
2. W O R K F O R P O O R F O R K S K O O P S R O O K S F O U R W O W S
3. P O O P O O P O O P P O O P P R O P S P R O W S P O R K S

It is assumed that you know what prime, square, and Fibonacci numbers are. A brief explanation of the other integer sequences follows.

Odious - a nonnegative number which has an odd number of 1s in its binary expansion. The first few odious numbers are 1, 2, 4, 7, 8, 11, 13, 14, 16, 19

Wasteful - a natural number that has fewer digits than the number of digits in its prime factorization (including the exponents). The first few are 4, 6, 8, 9, 12, 18, 20, 22

Undulating - has alternating digits of the form aba, abab, ababa, etc. Assume all U numbers are non-trivial, i.e. 3 digits or more. The first few: 101, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212

Katadrome - A number whose hexadecimal digits are in strict descending order. The first few are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 32, 33, 48, 49

• When I post the question, I'll also include external links to MathWorld or OEIS for those who need more detail on the less familiar sequences, but the explanations above should be sufficient for most, I think. Mar 6, 2014 at 23:28
• Your definition of "undulating" isn't the one I'm familiar with, which just requires that the digits alternately increase and decrease. Also, it would be better to include expected answers for the test cases, so that submitters can use them as test cases rather than them serving just for you to say "No, this is buggy". Mar 6, 2014 at 23:57
• Yes, that's my plan, I just haven't finished double checking my results for the test cases yet. OEIS and Mathworld have the strict 2-digit definition of undulating, but I'll make sure to make the definition here more prominent so it is clear which interpretation is meant. Mar 7, 2014 at 0:04
• 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 16:09

# Unified format patcher

Write the shortest program that will take a patch file in the unified format from stdin and apply that patch. No external tools that do the process for you can be used.

### Clarifications

• Extra documentation about the unified format can be found here
• All file paths will be relative
• Only one file will be modified per patch
• Timestamps can be ignored
• The patch file will be valid and will apply cleanly to the file specified (it will not lie about line numbers, etc..)
• Assume all files being patched already exist, you don't need to create/delete files

### Extra

• -35 - Take an argument that allows you to unpatch a patch

### Example

/test/a.cpp

#include <iostream>
using namespace std;

int main() {
cout << "Hello world!";
return 0;
}


patch.txt

--- a/test/a.cpp
+++ b/test/a.cpp
@@ -1,7 +1,8 @@
#include <iostream>
+#include <vector>
using namespace std;

int main() {
-    cout << "Hello world!";
+    cout << "Goodbye world!";
return 0;
}


Run patch

patch.exe patch.txt


/test/a.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
cout << "Goodbye world!";
return 0;
}

• Can the program assume that the @@ lines contain the correct line numbers? Mar 6, 2014 at 17:52
• A good explanation of the patch file format is needed. If not too long, include it in the question. Else, provide a link. Mar 6, 2014 at 17:53
• You forgot the obvious "no external tools" disclaimer. You don't want the patch \$1 answer. Mar 6, 2014 at 17:55
• @ugoren thanks for the comments, I added some further clarifications. Mar 6, 2014 at 18:38
• Does "The patch file will be valid (it will not lie about line numbers)" also mean that it will apply cleanly? Mar 6, 2014 at 19:24
• @PeterTaylor yes, updated question. Mar 6, 2014 at 19:51
• "The shorted program" should say "the shortest program", but other than that I think it's ready to go. Of course, no-one's actually going to do more than filter out the lines starting -, remove the first char from each line, and parse the line-numbers to work out how to splice the resulting text in. Mar 7, 2014 at 0:01
• This sandbox post has had little activity in a while. Please improve / edit it or delete it to help us clean up the sandbox. Due to community guidelines, if you don't respond to this comment in 7 days I have permission to vote to delete this.
– user58826
Jun 9, 2017 at 16:10

# Efficient Testing for Armstrong Numbers

An Armstrong Number (also known by different names, including Narcissistic Number; see Wikipedia for more information) is a non-negative number (for our purposes represented in base 10) that is equal to the sum of the individual digits of the number each raised to the power of the number of digits. For example:

2. The individual digits are 4, 0, & 7.
3. Since it is a three digit number, we raise each digit to the third power: 64 (4^3), 0 (0^3), & 343 (7^3).
4. The sum of those values is 407 (64 + 0 + 343).
5. Because the final sum is equal to the original number, it is an Armstrong Number.

By contrast:

2. The individual digits are 4 & 7.
3. A two digit number, so raise each digit to the second power: 16 (4^2) & 49 (7^2).
4. The sum of those values is 65 (16 + 49).
5. The final sum of 65 is not the original number, so it is not an Armstrong Number.

Your mission, should you decide to accept it: Write a program in any programming language (using only standard language features and libraries) implementing the most efficient algorithm possible to test the numbers from 1 through 18,446,744,073,709,551,615 (264-1) inclusive for "Armstrongness", generating a list of Armstrong Numbers, and only Armstrong Numbers, as output.

While any language is acceptable, it should be obvious that interpreted scripting languages will be at a disadvantage in the efficiency department. That being said, a superior algorithm in an interpreted scripting language can beat the pants off an inefficient algorithm in hand tuned assembly language.

## Winning Criteria

The algorithm that can check all possible candidate numbers for "Armstrongness" in the least amount of time on a reference computer will be the winner. The reference computer will have the following specifications: {approximately an AMD Phenom class computer with 8 GB RAM running Windows 7 Ultimate 64 bit}

• I don't know that this would belong in the (already very long, maybe too long) problem statement above, but other historical background. The class was for Fortran 77, and I was in a friendly competition with my TA to write the shortest version. I never could win that one, so I decided to write the most efficient version instead. Hence: I prefer efficiency puzzles to code golf (though code golf is fun too). Feb 20, 2014 at 8:30
• This doesn't seem to have an objective winning criterion. You do list "criteria I'll be using to judge this", but a) it mixes specification with winning criteria; b) it combines factors without indicating their weight. Feb 20, 2014 at 11:51
• The question also seems to be about twice as long as it needs to be. If you use the [link text](url) link notation you can shorten it slightly; you can also lose paragraphs by cutting the worked example and brute-force code (link to the existing question on narcissistic numbers instead); cutting the waffling about which languages you think have advantages; and simplifying the motivation. Feb 20, 2014 at 11:57
• I think efficiency problems are not well suited to code-golf. The efficiency of an algorithm depends on too many factors. You could perhaps require the lowest number of power operations. Feb 20, 2014 at 12:43
• @ugoren, 0 is easily obtained. Feb 20, 2014 at 12:57
• @PeterTaylor, You're right. Still, trying to replace a time measurement with the number of operations of a certain type sometimes helps define the problem better. Feb 20, 2014 at 15:12
• @PeterTaylor: I agree it is quite long, and will consider revisions to it. Feb 20, 2014 at 21:43
• @PeterTaylor: I'm open to better phrasing of the "objective winning criteria" but really, it is pretty objective already. One, no wrong answers allowed in the winner. Two, how efficient is the algorithm (based on the range of numbers tested and time taken to test them). For example, an algorithm that tests all numbers through 9 digits in 100 seconds is faster than an algorithm that takes 20 seconds to test all numbers through 8 digits (10 times larger interval in only 5 times the time). How might you suggest integration of this with the problem statement? Feb 20, 2014 at 21:48
• @PeterTaylor: Glad I included the disclaimer about failing eyesight, given that I searched for narcissistic numbers and came up with nothing. I either searched the wrong portion of PCG (meta) or I made a typo when spelling narcissistic. Feb 20, 2014 at 21:49
• @ugoren: efficiency may not be suited to code golf, but my understanding was that this 'forum' was about "programming puzzles" and "code golf". I certainly would consider finding a more efficient algorithm to be like solving a puzzle, though maybe I'm alone in that, in which case no biggie. Feb 20, 2014 at 21:51
• Edited the problem statement (which is still admittedly quite long, still considering other edits) by removing the final PPS paragraph and replacing the existing links as suggested. Feb 20, 2014 at 21:59
• The winning criterion is still too imprecise IMO. (NB Of the judging criteria you list, the first is part of the spec, so it's an acceptability criterion rather than a winning criterion). A genuinely objective winning criterion allows me to calculate my score before I submit my answer. Mar 12, 2014 at 8:47
• It should be much shorter in order to not discourage people from approaching your challenge. Almost all the text after the definition doesn't add anything to the challenge - beside "don't print wrong numbers" which is of course relevant. I also think that a more precise criterion should be given instead. Mar 12, 2014 at 9:03
• I've posted a "radical" update to it. I suspect the new winning criteria will not be acceptable either, since it involves a "reference computer" for final timing. Very open to suggestions on how to restate it so that a crappy algorithm on fast hardware doesn't beat an efficient algorithm on slow hardware. Mar 12, 2014 at 20:17
• The possibility that processor architecture or available memory affects the results is a tricky issue with fastest-code questions, but there isn't really a better way of comparing speed of programs than measuring on a large test case. I can at least measure how my program compares to someone else's on my computer, and know whether it's close or not. Mar 12, 2014 at 21:23

## Amino Acids Matcher

In genetics, a codon is a set of three nucleotides, the most basic form of nucleic acids. A codon "codes" (no pun intended, that's the actual term used) for a specific amino acid. Given a string of DNA, it is converted into RNA form by taking the opposite complementary pair.

DNA    RNA
A      U (T changes to U)
T      A
C      G
G      C


You will be given a String of unknown length that contains multiple codons. You must convert them to RNA form and print out the amino acid for each. See here for a chart: http://en.wikipedia.org/wiki/RNA_codon_table#RNA_codon_table

## Sample Input

TACTCGGATACT

Is split into

TAC, TCG, GAT, ACT

We now change each letter to its reciprocal

AUG, AGC, CUA, UGA

And print out the amino acids

Methionine, Serine, Leucine, Stop

This would probably be

I know that this is most likely not sufficiently explained and might be too complicated. Additional, tell me if there is any incorrect information above.

• So basically this is a challenge to compress a lookup table. You should probably specify that the string will be a multiple of three characters (or specify what to do otherwise); and it would seem sensible to inline the lookup table so that a) the question doesn't rely on the external page remaining intact; b) you save everyone who wants to answer the question the hassle of calculating it. Mar 17, 2014 at 12:42
• Thanks for the feedback. I'll update accordingly later today. Mar 17, 2014 at 15:48

# Find words in word square solver

On social media I often see images with letters and in them are some positive words for people to find. I challenge you to write a program that finds all words in the puzzle that matches a input dictionary. An example of such puzzle is this one:

An ASCII representation I made of this:

XCUALOVEYKBWSNG
DUAWKCBEAUTYRJV
YOUTHFSMGNEZLPR
MHJREYWDKZLUSTJ
FSUCCESSDHEALTH
ENMQXPTIMELMSAQ
VEXPERIENCEGHBW
GHUMOURLOYMONEY
SYZPOPULARITYNA
AMKCFUNBXHUZYIX
CWIHYSHAPPINESS
HONESTYCFRIENDS
KPYJAETWPOWERQC
BTYACFREEDOMJMO
RIWINTELLIGENCE


Now I imagine we can find words horizontally, vertical and diagonal and all of the mentioned in reverse. The program must be able to take a square and a dictionary like this one and print all the matching words.

As a test case I give custom dictionary:

bar
bid
dir
dog
fed
foo
god
man
mod
set
sun


And a test square:

OGFIR
DOMAN
ODBID
OPGES
OGFIR


Your code should be able to print all but the two last words in the dictionary. For diversity you should specify how the cube and the dictionary is bo be entered.

This is so shortest code wins.

• What should be output? Only the matched words? Their positions? And directions? Apr 3, 2014 at 15:47
• @JanDvorak Just print the words found. Do you think coordinates and direction can be given a bonus? Apr 3, 2014 at 15:51
• Cube? I'm only seeing two dimensions. On a more general note, perhaps for questions of this sort it would be OK to assume the availability of a standard dictionary file like /usr/share/dict, and discount the characters used to access this file? What do people think? Apr 3, 2014 at 15:55
• @squeamishossifrage OMG You're right. I meant square of course :-) I think people can choose. eg. The question is open for diversity like cat square.txt dic.txt | solver now, but I'm open for change that does not discriminate. Apr 3, 2014 at 16:03
• How does the program know where the wordsearch ends and the dictionary starts? Apr 3, 2014 at 21:39
• @PeterTaylor By mistake I made the test a rectagle, but I fixed that. The length of the first line would be the number of lines in the square. Anyway how the input is done I thought should be up to the solver so that they can choose to open files, read stdin or maybe more disturebing ways to get input in... Apr 3, 2014 at 21:47
• 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.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this.
– user58826
Jun 9, 2017 at 16:30
• @programmer5000 It only got two upvotes so I let it be. Feel free to post it if you'd like. Jun 12, 2017 at 15:27

## Collatz ...something

The Collatz conjecture states that every natural number n leads to the number 1 if the recursive function f(n) is applied to it defined as

f(n)=n/2    if n is even
=3n+1   if n is odd


Let "ai" be the value of f applied to n recursively i times so that a0 = n , a1 = f(n) , a2 = f(f(n)) ... ai = f(ai-1)

Let A be the set {a0, a1, ..., 1}

Thus, for n=10, we get the sequence

a0 = 10 --> a1 = 5 --> a2 = 16 --> a3 = 8 --> a4 = 4 --> a5 = 2 --> a6 = 1

and the set A as A = {10,5,16,8,4,2,1}

Your task is to write a function/program that will accept a set of naturals say I. You must output a set of numbers say C such that I is a subset of the union of the sets A for all numbers in C.

### Rules

• Network access is forbidden
• Any of the standard loopholes are forbidden
• Your program must end in less than 200 seconds. You may assume that all the input terms are less than 2^(45); however note that the individual terms of the collatz sequence can go higher.

### Input

• List/array of naturals in I as an argument to a function
• , or space or \n separated naturals in I on STDIN

### Output

• return a list/array/set of all naturals in C
• print all the naturals in C separated by \n

### Scoring

( ( (10)^(number of elements in C) ) * (sum of all elements in C) ) + ceil( 100*log(total number of bytes of your code) )


log() is the natural logarithm

Lowest score wins.

### Examples

Input:

I = { 16 , 32 , 40 }


Possible outputs along with the score

C=                   Score

{ 16 , 32 , 40 }     ((10)^(3))*(16 + 32 + 40) = 8000   + constant
{ 32 , 40 }          ((10)^(2))*(32 + 40)      = 7200   + constant
{ 32 , 13 }          ((10)^(2))*(32 + 13)      = 4500   + constant --> most optimal
{ 1024 , 320 }       ((10)^(2))*(1024 + 320)   = 134400 + constant
... Infinitely many higher numbers


where constant is ceil(100*log(code length))

In this case, the answer { 32 , 13 } is the most optimal.

Note: This is NOT code-golf even though the length of your program is considered. Please also provide a readable version.

I'm being flexible with the I/O so that the more verbose languages might get some benefit. You can write a complete program or a function or a lambda function. It is not required that your function(if you choose to write one) returns. Using a function for input while printing the output is fine if that makes the code shorter.

This will be tagged as

## Sandbox feedback

• Can anyone suggest a better title?

## TODO

• Scoring needs specific test cases. Perhaps the final score could be the average of all scores of the test cases.

• Needs a proper title.

• The timing constraint is not reasonable unless you also provide constraints on the number and size of the inputs. For any input for which the constraint is reasonable at all, I think that the first point of the spec is unnecessary: if a counterexample exists, it's right at the edge of what fits in a 64-bit number. The second point of the spec is currently quite difficult to understand. Apr 3, 2014 at 9:47
• @PeterTaylor Is it OK now? Apr 4, 2014 at 16:15
• Looking around a bit at the standard terminology, I think that it might be best introduced with something like "Each positive integer n generates a Collatz sequence by repetition of the map f(n) = n % 2 == 0 ? n/2 : 3*n+1. Define the orbit of n as the set containing the integers in its Collatz sequence, and the orbit of a set {n_i} as the union of the individual elements' orbits. Your task is to find an optimal set under the constraint that its orbit contain a specified subset." That then leads into the example. Apr 4, 2014 at 16:48
• I'm not sure that it's justifiable to claim that for your example {I2, C5, C10} is "(not the most ideal)". Whether or not it is depends on which arrows are /2 and which are *3+1, which isn't shown in the example. It's also occurred to me, which I missed earlier, that your scoring system requires a bit more of a test suite: at present, you have no way of distinguishing between answers which get the optimal solution to one test case. And I suggest a title, based on my previous comment: "Optimal Collatz orbits". Apr 4, 2014 at 16:52
• I suggest you to add a link describing what is a collatz sequence. As a non-mathematician, I find it hard to understand. There is extra whitespaces after  in your first code block.
– A.L
Apr 4, 2014 at 17:12
• @PeterTaylor Edited a lot. Are you sure it is called an orbit? I couldn't find that term anywhere. Apr 6, 2014 at 16:39
• It occurs 4 times in the Wikipedia page on the Collatz conjecture, and Google gives over 6 million hits for collatz orbit. Apr 6, 2014 at 22:08
• 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.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this.
– user58826
Jun 9, 2017 at 16:31