Sandbox for Proposed Challenges

Question

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

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

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
• Comments addressing specific points mentioned in the proposal
• 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!

Answer 1

Add two real numbers ... probably

The problem statement here is pretty simple, take two real numbers between 0 and 1 as input and output their sum, with probability 1.

The catch here is that there are a lot of real numbers. There are in fact so many real numbers that it is impossible to fit all of them into any finite data type. As such any way to input real numbers has to be potentially infinite, and any algorithm that handles arbitrary real numbers cannot consume all of the input.

For this challenge you will input (and output) real numbers as lazy sequence (e.g. stream, generator, lazy list, function) of bits, representing their binary expansion. You can assume that the input will be normalized and will not end in an infinite repetition of 1.

Even with this special input format it isn't possible to add any two real numbers. Any potential algorithm can be tricked into an infinite loop.

So instead we are going to settle for almost working. To "work" on a pair of inputs your program needs to be able to output any bit of the input in finite time. For example, if you output a generator I should be able to read to the 5th bit without the program getting stuck in a loop. Your answer needs to work with probability 1, meaning that the measure of the set of inputs which your program does work needs to have measure 1. The behavior for which the program doesn't work is undefined it can loop forever give an incorrect answer etc. so long as these cases themselves have measure zero.

This is code-golf the goal is to minimize the size of your source code as measured in bytes.

Answer 2

Infinite Apple Dilemma

Posted here

Answer 3

How many sorting networks?

fastest-codesequence

Below on the left is a picture of a sorting network that can sort 4 inputs. On the right you can see it sorting the input 3,2,4,1.

A sorting network of size n consists of a set of n horizontal wires where two wires can be connected by a vertical wire. The inputs to a sorting network move from the left to the right on the horizontal wires and whenever a vertical wire connects two elements they swap places if the lower element comes before the higher element.

The example sorting network above has the property that it correctly sorts all inputs. You could add even more wires but the behavior would not change. But if you removed a wire then there would be some inputs that it would not sort anymore.

Two networks behave the same if for every input permutation they produce the same output permutation. Your task is to find out how many possible behaviors there are for a given size. That is, output a sequence of the number of behaviors (equivalence classes) for n=1,2,3,... etc.

Your code will be scored based on its speed on an AMD Ryzen 1800X linux system. The code should output the sequence described above and I'll run each submission for 5 minutes and with a 16GiB ram limit. Whichever code has outputted most of the sequence wins. Ties are broken by whichever program outputted the final number first.

Sequence output

1
2
11
261
43337
TODO

Answer 4

Rotate an Image

Answer 5

Reverse the polyglot, change the language.

Answer 6

Approximate a root of an odd degree polynomial

Answer 7

Whole Number Groups

Answer 8

Fibonacci Binary Squares

Answer 9

"Candy Crush" a string

Answer 10

Help Me Type on My New Keyboard

Answer 11

Largest Binary Area

Answer 12

Calculate the p-adic square root of -1

Given a prime number \$p\$, a \$p\$-adic number is a number whose representation in base \$p\$ may have infinitely digits to the left of the radix point, but only finitely many digits to the right of it. A \$p\$-adic integer has no digits after the radix point.

\$p\$-adic numbers have some interesting properties. It can be proven that for any prime number \$p\$, there exists a \$p\$-adic integer \$x\$ such that \$x^2 = -1\$ if and only if the congruence \$x_0^2 \equiv -1 \pmod{p}\$ has a solution. (That is, there is some integer \$x_0\$ such that \$x_0^2 + 1\$ is divisible by \$p\$.)

Your task is to determine whether this is the case and calculate the digits of the number \$x\$. Note that there will always be two solutions which are additive inverses of each other; you only need to calculate one.

Input

A prime number \$p \ne 2\$. (You don't need to verify that it's prime.)

Output

Find the digits of the \$p\$-adic square root of \$-1\$, as described above. Following the standard sequence rules, do one of the following:

• Given an index \$i\$, output the \$i\$-th digit from the end. Since base representations are naturally 0-indexed, you may not use 1-indexing.
• Given a positive integer \$n\$, output the last \$n\$ digits. You can choose between little-endian and big-endian.
• Output all digits in the form of a non-halting program, a generator, an infitite lazy list, etc.

If the \$p\$-adic square root of \$-1\$ does not exist, do anything that can be clearly distinguished from a valid output, such as raising an exception or returning an empty list.

Algorithm

Here I describe one possible way to solve this challenge.

• Find a number \$x_0\$ between \$0\$ and \$p-1\$ such that \$x_0^2 \equiv -1 \pmod{p}\$. If not found, report failure.
• Find a number \$y\$ between \$0\$ and \$p-1\$ such that \$2x_0y \equiv 1 \pmod{p}\$. (This is always possible.)
• Let \$c_0 = \left\lfloor\frac{x_0}{p}\right\rfloor\$.
• For each positive integer \$i\$:
  • Let \$h_i = c_{i-1} + \sum_{j=1}^{i-1} x_j x_{i-j}\$.
  • Let \$x_i = (p-1-h_i)\cdot y \bmod p\$.
  • Let \$c_i = \left\lfloor\frac{h_i + 2 x_0 x_i}{p}\right\rfloor\$.
• The sequence \$\left(x_i\right)\$ is the output.

Ungolfed Python implementation:

def sqrt_minus_one(p, n):
    for x in range(p):
        if (x * x + 1) % p == 0:
            last_digit = x
            break
    else:
        return None # no solution
    for x in range(p):
        if (x * 2 * last_digit) % p == 1:
            inv = x
    digits = [last_digit]
    carry = (last_digit * last_digit) // p
    for i in range(1, n):
        h = sum(digits[j] * digits[i - j] for j in range(1, i)) + carry
        digits.append((p - 1 - h) * inv % p)
        carry = (h + 2 * last_digit * digits[i]) // p
    return digits

It's also possible to use a brute-force approach where you find an \$n\$-digit number \$x\$ such that \$x^2 + 1\$ ends with \$n\$ zeroes in base \$p\$. I suppose this could lead to much golfier solutions, so maybe I should make the challenge restricted-complexity to forbid this?

Test cases

  p | first 20 digits (two possible outputs)
  3 | ---
  5 | 2,1,2,1,3,4,2,3,0,3,2,2,0,4,1,3,2,4,0,4
    | 3,3,2,3,1,0,2,1,4,1,2,2,4,0,3,1,2,0,4,0
  7 | ---
 11 | ---
 13 | 5,5,1,0,5,5,1,0,1,8,8,6,12,6,3,0,4,7,4,5
    | 8,7,11,12,7,7,11,12,11,4,4,6,0,6,9,12,8,5,8,7
 17 | 4,2,10,5,12,16,12,8,13,3,14,0,6,1,0,15,1,8,14,5
    | 13,14,6,11,4,0,4,8,3,13,2,16,10,15,16,1,15,8,2,11
 47 | ---
101 | 10,5,29,66,10,30,44,29,72,25,34,82,83,5,52,17,67,94,65,52
    | 91,95,71,34,90,70,56,71,28,75,66,18,17,95,48,83,33,6,35,48

Answer 13

Is it traversable?

Answer 14

Great Leap to the Right

code-golf

Given a string s consisting of characters a-z lowercase, generate 5 arrays a1, a2, a3, a4, and a5 of size n (length of s) where the i-th element of each array represents the index of the next occurrence of the i-th character in s, with the following conditions:

• If no such occurrence exists, set the value to n (0-based indexing) or n+1 (1-based indexing) depending on the indexing convention you use.
• a1 represents the 1st next occurrence of the character, a2 represents the 2nd next occurrence, a3 represents the 4th next occurrence, a4 represents the 8th next occurrence, and a5 represents the 16th next occurrence.

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

Here are some test cases. They all use 0-based indexing.

Input: aakakakakka
Output:

1 3 4 5 6 7 8 10 9 11 11
3 5 6 7 8 10 9 11 11 11 11
7 10 9 11 11 11 11 11 11 11 11
11 11 11 11 11 11 11 11 11 11 11
11 11 11 11 11 11 11 11 11 11 11

Input: sydgdtsfixuvhdgisifdyovjcgs
Output:

6 20 4 14 13 27 16 18 15 27 27 22 27 19 25 17 26 27 27 27 27 27 27 27 27 27 27
16 27 13 25 19 27 26 27 17 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27

Input: qmorzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
Output:

59 59 59 59 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
59 59 59 59 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59
59 59 59 59 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 59 59
59 59 59 59 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 59 59 59 59 59 59
59 59 59 59 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59

Answer 15

Is it a Frog List?

Tags: code-golfnumberintegerdecision-problem

Challenge:

A Frog List is defined by certain rules:

1. Each frog within a Frog List has an unique positive digit [1-9] as id (any 0 in a list is basically an empty spot, which can mostly be ignored).
2. A Frog List will always have exactly one Lazy Frog. A Lazy Frog will remain at its position.
3. Every other frog in a Frog List will jump at least once, and will always jump towards the right from its starting position.
4. When a frog jumps, the distance of its jump is always the same.
5. When a frog jumps, it will continue jumping until it's outside the list's right bound.
6. 0-1 jumping frogs can stand on top of a Lazy Frog, as long as their summed ids is still a single digit. (Jumping frogs cannot stand on top of one another! Which implicitly also means there cannot be two jumping frogs on a Lazy Frog simultaneously.)

Note that the frog-ids within a Frog List describe how a frog has already jumped (past sense). Focusing on an individual frog-id within a Frog List shows how it has jumped, and at what positions within the Frog List it has landed, and jumped onward from - with the exception of the Lazy Frog, which hasn't moved.

Worked out explanation of the first Frog List [1,2,1,0,8,2]:

1. The Lazy Frog has id \$\color{green}{7}\$ at position ~~~~7~:

2. The first jumping frog has id \$\color{red}{1}\$ at positions 1~1~1~ with jump distance 2:

3. The second jumping frog has id \$\color{blue}{2}\$ at positions ~2~~~2 with jump distance 4:

All three frogs summed gives the Frog List, so [1,2,1,0,8,2] would be truthy:

All Test cases including explanation:

Input                 Explanation:

Truthy:

[1,2,1,0,8,2]         Lazy Frog 7 doesn't jump                ~~~~7~
                      frog 1 jumps (with jumping distance 2)  1~1~1~
                      frog 2 jumps (with jumping distance 4)  ~2~~~2

[1,0,0,0,0,1,2,7,2,2] Lazy Frog 5 doesn't jump                ~~~~~~~5~~
                      frog 1 jumps (with jumping distance 5)  1~~~~1~~~~
                      frog 2 jumps (with jumping distance 1)  ~~~~~~2222

[9,8,9,1]             Lazy Frog 7 doesn't jump                ~7~~
                      frog 1 jumps (with jumping distance 2)  ~1~1
                      frog 9 jumps (with jumping distance 2)  9~9~

[1,0,1,3,3,3,1]       Lazy Frog 2 doesn't jump                ~~~~2~~
                      frog 1 jumps (with jumping distance 2)  1~1~1~1
                      frog 3 jumps (with jumping distance 2)  ~~~3~3~
(Note that the 3 at ~~~~3~~ is Lazy Frog 2 and jumping frog 1 on top of one another,
 and not jumping frog 3.)

[7]                   A single Lazy Frog 7

[7,0,0,0]             A single Lazy Frog 7~~~

Falsey:

[1,2,3,0,2,1,3]       (rule 2) there is no Lazy Frog: 1~~~~1~
                                                      ~2~~2~~
                                                      ~~3~~~3
TODO                  (rules 2 & 3) there are two Lazy Frogs (TODO: is this even possible without also applying to rule 6?)
[1,6,1,8,6,1]         (rule 4) frog 1 jumps irregular 1~1~~1 / 1~11~1
                                                      ~6~~6~ / ~6~~6~
                                                      ~~~8~~ / ~~~7~~
[2,8,2,8,0,9]         (rule 5) frog 2 stopped jumping 2~2~~~
                                                      ~~~~~1
                                                      ~8~8~8
[1,2,3,2,7]           (rule 6) two jumping frogs at the last position with: 1~~~1
                                                                            ~2~2~
                                                                            ~~3~3
                                                                      (Lazy)~~~~4
                                                                                ^
                      OR two jumping frogs at the third and last positions with: 1~1~1
                                                                                 ~2222
                                                                           (Lazy)~~~~4
                                                                                   ^ ^

Challenge rules:

• The integers in the input-list are guaranteed to be \$0\leq n\leq9\$ (aka single digits).
• Any single-value inputs are Frog List, since they'll contain a single Lazy Frog and no jumping frogs.
• I/O is flexible. You may take the input as a list/array/stream of digits, an integer, a string, etc. You may output any two values or type of values (not necessarily distinct) to indicate truthy/falsey respectively.
• You can assume a Frog List will never starts with a 0 (doesn't matter too much for list I/O, but can be for integer I/O).

General Rules:

• This is code-golf, so the shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (e.g. TIO).
• Also, adding an explanation for your answer is highly recommended.

---

Sandbox questions:

1. Anything unclear?
2. Any missing rules?
3. Any suggested test cases?

Sandbox TODO's:

• Reference implementation to verify larger test cases.
• Possible convert this to a sequence challenge when the TODO above is done?

Answer 16

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

Answer 17

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
14 - tetradeca
15 - pentadeca
16 - hexadeca
17 - heptadeca
18 - octadeca
19 - nonadeca
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?

Answer 18

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.

Answer 19

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

Answer 20

Business Card Ray Tracer

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.

http://fabiensanglard.net/rayTracing_back_of_business_card/index.php

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

Answer 21

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.

Answers must include:

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

code-golf holidays

---

Are there any additions/deletions/modifications that should be made to these rules?

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?

Answer 22

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.

Your program will:

• 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%

Your program will not:

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

Answer 23

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

Answer 24

Unified format patcher

code-challenge

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;
}

Answer 25

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:

1. Start with the three digit number 407.
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:

1. Start with 47.
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 (2⁶⁴-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}

Answer 26

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 code-golf

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.

Answer 27

Find words in word square solver

code-golf

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
fad
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 code-golf so shortest code wins.

Answer 28

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 "a_i" be the value of f applied to n recursively i times so that a₀ = n , a₁ = f(n) , a₂ = f(f(n)) ... a_i = f(a_i-1)

Let A be the set {a₀, a₁, ..., 1}

Thus, for n=10, we get the sequence

a₀ = 10 --> a₁ = 5 --> a₂ = 16 --> a₃ = 8 --> a₄ = 4 --> a₅ = 2 --> a₆ = 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

Your score is calculated as

( ( (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 code-challenge

---

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.

Answer 29

Filter out repetitive lines

Google Suggest doesn't show any results if a string contains more than 4 repetitions of a substring. More specifically, if a substring is repeated 4 times in a row, followed by the first character of that substring (i.e. abcabcabcabca or x x x x x), nothing is suggested. This rule changes slightly if the substring is all the same digit - a digit may be repeated 5 times in a row, but no more. This is probably to allow searching for ZIP codes like 22222. (This doesn't extend to strings like 1010101010, though.)

Let's simulate this behavior! Write a program that takes lines on standard input and echoes those lines back on standard output, unless the line fits the criteria for repetitiveness, in which case it's silently discarded.

Sample input:

a simple query
nananananananana
ffffgggghhhh
48719999936
abc abc abc abc asdf
xyzzzzzyx
122333444455555666666
repetitiverepetitiverepetitiverepetitive
erepetitiverepetitiverepetitiverepetitive
101010101
55555 zzzzz

Output:

a simple query
ffffgggghhhh
48719999936
repetitiverepetitiverepetitiverepetitive

(Google's behavior is actually quite a bit more complicated than this; there are a few exceptions to all of these rules, but let's just ignore those for this challenge.)

code-golf strings

---

There was a similar challenge posted awhile ago (Recognizing Repetition in strings), but it was closed due to vagueness. I think the criteria proposed above are more than thorough enough.

Answer 30

Am I a Matroid?

Input:

A list I that is a subset of the powerset of E={1,2,...,n} which represents the independent sets of elements of the purported matroid M=(E,I). Note that the cardinality of the ground set may be for the purposes of this question ignored. Any elements of E that appear in none of the elements of I cannot contribute (i.e. if M=(E,I) is a matroid then M=(E union K,I) is a matroid for any set K.

Input may be in whatever list format you desire, be it as simple as no separators but spaces (using 0 for the empty set): 0 1 2 3 12 13 or as complicated as whatever list literals are in your favorite language (such as python's: [[],[1],[2],[3],[1,2],[1,3]]).

Output:

A variation on 1/0, true/false, yes/no answering the question: is M a matroid?

Definition:

M=(E,I) is a matroid if:

1. I is not the empty set
2. If J is in I and K is a subset of J, then K is in I
3. If J,K are in I and |K|<|J| then there exists an element x that is in the set difference J-K such that K union {x} is in I.

There are equivalent formulations of condition 1 and 3, also there are conditions on the bases (maximal elements of I w.r.t. cardinality) that are equivalent to these. If people want I can post those too or leave them as optional research.

Examples:

I={{},{1},{2},{1,2}} is a matroid.

I={} is not a matroid because it is empty (by axiom 1).

I={{},{1},{1,3}} is not a matroid because if it has {1,3} independent then it must have {3} independent (by axiom 2).

I={{},{1},{2},{3},{1,2}} is not a matroid because if it has {1,2} and {3} independent then it must have either {1,3} or {2,3} independent (by axiom 3).

I={{}} is always a matroid, as is I=powerset([1,2,...,n]) for any n>0 as they both trivially satisfy the axioms.

Specs:

Submission is either a program taking input from standard input or command line argument or a function that takes I as input (as a string) and returns the specified binary answer. No upperbound on the size of input should be hardcoded.

I would intend for this to be a code-golf challenge.