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

Answer 1

Output 5-line calendar

Given year, month and optionally weekday of 1st, output the calendar of the month.

For empty cell, fill it with the date where it's supposed to be, in last or next month, and add # to indicate gray. If last few days can't fit in 5 lines, then they share last line with 5th week, use / to separate two days.

Sample Input: Nov 2023

Sample Output:

 #28   #29   #30     1     2     3     4
   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    #1    #2

Sample Input: Dec 2023

Sample Output:

 #26   #27   #28   #29   #30     1     2
   3     4     5     6     7     8     9
  10    11    12    13    14    15    16
  17    18    19    20    21    22    23
24/31   25    26    27    28    29    30

Outputting a 2D array of string is fine

Answer 2

Longest irreducible quine

Posted here

Answer 3

How long is this string, really?

Answer 4

answer-chaining cops-and-robbers

In this challenge answers will provide three elements:

• A programming language: \$L\$
• An output string: \$S\$
• And a non-empty string: \$B_n\$

You will also write, but not reveal, a program in \$L\$ which outputs \$S\$, built by concatenating copies of the \$B_n\$ strings from your answer and previous answers in any order.

For example here are two answers given in pseudocode:

Answer 1

\$S\$ = H
\$B_0\$ = print "H"

The program is print "H"

Answer 2

\$S\$ = Hiiii
\$B_1\$ = ++"i"

The program is print "H"++"i"++"i"++"i"++"i"

Robbers will try to discover a valid solution, that is a program made from the \$B_n\$ strings in your answer and previous answers which outputs your \$S\$. Your goal will be to make this as hard as possible.

States

As with any cops-and-robbers challenge, cops' posts here can have 4 different states:

• Vulnerable
• Cracked
• Safe
• Revealed

All cops' posts start as vulnerable. If a robber finds and posts a solution to a vulnerable post they will receive 1 point and the post will become cracked. If a post lasts 10 days in vulnerable without being solved it automatically becomes safe. A cop with a safe post may choose to reveal their program and their safe post will become revealed. A robber can still solve a safe post, if they do they receive a point and the post becomes revealed.

Only revealed posts are eligible for scoring. Robbers are only permitted to solve vulnerable and safe posts.

Scoring

For cops' an answer's score is the number of cops' posts before it if it is revealed and 0 if it is any other state. The goal is to get as high a score as possible.

Languages

In the interest of fairness, we are going to require that languages are free and reasonably cross platform. Both languages you choose must be freely available on Linux and FreeBSD (the two largest foss operating systems). This includes languages which are free and open source.

Your selected languages must predate this challenge.

Programs here should be complete programs not functions, expressions or snippets.

Answer 5

How many cacti can I plant here?

Answer 6

Draw a Fibonacci Swoosh

Answer 7

Scroll That Text Faster!

Lots of television news stations will show a ticker at the bottom, which can be thought of as a window into a larger string that shifts to the right by one space each cycle:

"Lorem ipsum dolor sit amet, consectetur adipiscin"
"orem ipsum dolor sit amet, consectetur adipiscing"
"rem ipsum dolor sit amet, consectetur adipiscing "
"em ipsum dolor sit amet, consectetur adipiscing e"
"m ipsum dolor sit amet, consectetur adipiscing el"

This works great if the cycle time is short and the text can scroll by quickly. But not every updating text application is so lucky. Radio Data System is used by FM radio stations to send small amounts of data, about 1.2 kilobits per second, which contains information about the station or song or what-have-you. But with such a low bitrate, updates can be quite slow, and stations I see update the text about once a second.

With small enough windows, this can be annoyingly slow if we only advance it one character at a time. But some stations use a trick: separate the message by spaces and fit as many as we can into one window. Any words longer than the window must be scrolled one character at a time.

The Challenge

Write a function f(s, w) where s is the full string to scroll through and w is the size of the window in characters. w must be an integer and greater than 0. The output is a sequence of strings (array or output to console separated by newlines or whatnot), where each line is one step of the ticker.

To build the output, we can divide the words into those that fit into the window and those that don't. Of the first kind, fit as many as you can into one window, ignoring trailing spaces. If a word is exactly 1 window wide, it is considered of the first kind. If we get to a word that doesn't fit in the window but we still have empty space in the current window, just leave the rest of the window blank.

For words that don't fit in the window, scroll through them one character at a time until the end of the word is visible as the last character of the window. Each scroll step becomes its own output line. Words that don't fit in the window never share windows with those that do - the output shouldn't be "NEVER GON", "NA ", it should be "NEVER ", "GONNA ".

Examples

s = "RICK ASTLEY - NEVER GONNA GIVE YOU UP", w = 10

 0123456789
"RICK      "
"ASTLEY -  "
"NEVER     "
"GONNA GIVE"
"YOU UP    "

s = "LUDWIG VAN BEETHOVEN - SYMPHONY NO. 7 IN A MAJOR, OP. 92", w = 6

 012345
"LUDWIG"
"VAN   "
"BEETHO"
"EETHOV"
"ETHOVE"
"THOVEN"
"-     "
"SYMPHO"
"YMPHON"
"MPHONY"
"NO. 7 "
"IN A  "
"MAJOR,"
"OP. 92"

s = "SHERMAN BROTHERS - SUPERCALIFRAGILISTICEXPIALIDOCIOUS", w = 15

 012345678901234
"SHERMAN        "
"BROTHERS -     "
"SUPERCALIFRAGIL"
"UPERCALIFRAGILI"
"PERCALIFRAGILIS"
"ERCALIFRAGILIST"
"RCALIFRAGILISTI"
"CALIFRAGILISTIC"
"ALIFRAGILISTICE"
"LIFRAGILISTICEX"
"IFRAGILISTICEXP"
"FRAGILISTICEXPI"
"RAGILISTICEXPIA"
"AGILISTICEXPIAL"
"GILISTICEXPIALI"
"ILISTICEXPIALID"
"LISTICEXPIALIDO"
"ISTICEXPIALIDOC"
"STICEXPIALIDOCI"
"TICEXPIALIDOCIO"
"ICEXPIALIDOCIOU"
"CEXPIALIDOCIOUS"

Notes

• Words are defined as any sequence of non-space characters between space characters, at least U+0020. Word delimiters aren't dashes, commas, or punctuation.
• ASCII support only is fine, though you can get bonus style points if it supports a broader selection of Unicode, including fancy Unicode whitespace.
• Supporting uppercase-only, lowercase-only, or mixed case is fine.
• Trailing whitespace in output strings to pad to the window width is optional.
• This is code golf, so smallest program (bytes, codels, etc.) wins!

Answer 8

Count trapped self-avoiding walks fastest-code path-finding

Imagine an infinite grid of square tiles. You are standing on one of the tiles. You can move to any of the four cardinally adjacent tiles in a move, but you cannot step on the same tile twice. Calculate the number of ways you can get yourself trapped, i.e. the states where all four adjacent tiles have been already stepped on, after exactly \$n\$ moves. To take symmetry into account, only count the paths where your first move is to the right, and your first vertical move is upwards.

This is sequence A077482:

1, 2, 11, 25, 95, 228, 752, 1860, 5741, 14477, 42939, 109758,
317147, 818229, 2322512, 6030293, 16900541, 44079555, 122379267,
320227677, 882687730, 2315257359, 6346076015, 16675422679,
45502168379, 119728011251, 325510252108, 857400725204, ...

This is a fastest-code challenge. Submit a program that outputs the answers to the question for \$n = 7, 8, 9, 10, \cdots\$, indefinitely. The score of a submission will be the largest \$n\$ whose answer is printed in a minute on my local machine. Highest score wins; tie is broken by the time taken to output up to that term.

My local machine is a Windows 10 machine with the following specs:

• CPU: 12th Gen Intel Core i7-12700 (2.1GHz, 12 cores)
• RAM: 32GB

If a submission has no way to run on Windows, you can provide your own measurement, or online code execution services such as TIO/ATO/Godbolt may be used. I know this is not ideal, but I don't have other good options at the moment.

Answer 9

Sorting with a deque

Answer 10

Given an integer \$n\$. Connect all pairs of points on \$\mathbb Z^2\$ whose distance is \$\sqrt n\$. Count how many connected sets remain.

In case that infinite sets exist, return something not a positive integer. (0 used below)

Test cases

1 => 1
2 => 2
3 => 0
4 => 4
5 => 1
25 => 1

Answer 11

Shift right by half a trit

Answer 12

Completely introduce your friends

Answer 13

Visualize "Destroying Democracy" code-golf grid

This MathPickle post poses an interesting problem about gerrymandering.

An n-by-n square grid is given, and all cells are initially painted green. You can paint some cells red and partition the grid into several rectangles. The color of a rectangle is red if there are strictly more red cells than green; otherwise it is green (including when the numbers are equal). Your objective is to "win the election" by having strictly more red rectangles than green, with as few red cells as possible.

• The rectangles must cover the grid, and may not overlap.
• The largest rectangle's area must be strictly less than twice the smallest.

This problem has been solved for n <= 12 in this Puzzling post, and for more sizes in this OEIS entry.

Some examples: (same letter = one rectangle, uppercase = red)

n = 3: 4 red cells
AAa
BBb
ccc

n = 4: 6 red cells
AAad
BBbd
CCcd
eeee

n = 5: 8 red cells
AAafg
BBbfg
CCcfg
DDdfg
eeefg

n = 6: 11 red cells
aaaaad
bEFGHd
bEFGHd
befghd
bIIIid
bccccc

In this challenge, you don't need to minimize the number of red cells. Instead, find any one way to win the election by painting \$\frac{n^2}{2}\$ or fewer cells red and partitioning the grid following the rules.

I/O

The input is one integer n which is at least 3.

The output must be a 2D structure with n rows and n columns, where each item identifies the color and the rectangle the cell belongs to. The following are some valid outputs for n = 3:

2D array of nonzero integers, where sign = color and absolute value = rectangle ID
[[-1, -1, 1],
 [-2, -2, 2],
 [3, 3, 3]]

2D array of tuples of (bool, string)
[[(false, "A"), (false, "A"), (true, "A")],
 [(false, "B"), (false, "B"), (true, "B")],
 [(true, "C"), (true, "C"), (true, "C")]]

Strings printed over n lines
R1 R1 G1
R2 R2 G2
G3 G3 G3

Note that the "letter representation" used above is for illustration purposes and not allowed, since the number of rectangles can go over 26.

Standard code-golf rules apply. The shortest code in bytes wins.

Answer 14

Stuck on Sokoban

Answer 15

Is it a date format of YYMMDD, MMDDYY, and/or DDMMYY?

code-golf decision-problem date

Answer 16

Color theory auction deception kinda thing KotH

king-of-the-hill

---

In this game, bots will compete to collect color tiles, in order to get points for having partial or full rainbows, and/or multiple tiles of a single color.

Colors

This game has 9 base colors: red, orange, yellow, lime, green, cyan, blue, purple, and magenta. Each color comes in a light and dark shade, making a total of 18 shades.

Gameplay

In this KotH, bots will start with a small set of tiles, and purchase more at auction to build rainbows and multiples. Bots start with a number of bids, which are used to acquire tiles. Each tile auction consists of a number of rounds. In each round, bots may choose to spend a bid, or to pass. Bids don't have associated prices; a bot either bids or it doesn't. If only a single bot bids, that bot wins the tile. Otherwise, the bids are consumed, and the next round starts. If two consecutive rounds go by with no bids, any prior bids are returned to their respective bots, and the tile is not sold. If a tile is sold to a bot, all bids are consumed, including those by other bots.

Most auctioned tiles will be from an unowned pool, but bots may put tiles they own up for auction. If the tile sells, the seller gets all bids from the winning bidder (which, unless the tile is sold in a single round, will not be all of the bids spent). If it doesn't sell, the tile is returned to the seller.

All bids are visible to all other bots on the following turn.

Once six tiles have failed to sell in a row, the game will end, and scores will be tallied.

Scoring: Rainbows

A rainbow is a set of color tiles which are adjacent on a circular color wheel. The smallest rainbow which can count for points is 3 colors (e.g., yellow-lime-green or magenta-red-orange, but not blue-blue-purple). Rainbows are scored as follows:

• A base score of 2(n - 3) points, where n is the number of tiles. 3-tile rainbows are an exception, and have a base score of 1 point
• A score which increases with more variation in light vs. dark shades, calculated as min(light, dark) / 2

A rainbow with 4 dark shades and 2 light shades would thus score 7 points.

Once a rainbow contains all 9 base colors, it can continue to wrap around the color wheel. This is subject to two rules:

• The rainbow must still be continuous and progress in a single direction. Red-orange-yellow-...-magenta-red-orange is okay, but red-orange-yellow-...-purple-magenta-green would not be allowed
• The rainbow must not contain two identical shades of the same color. A rainbow can contain both dark green and light green tiles, but not two dark greens. This limits rainbows to 18 tiles, scoring 34.5 points

Scoring: Multiples

A multiple is a set of tiles which are the same base color. Multiples are scored as follows:

• If the multiple is all the same shade, the score is n - 2, where n is the number of tiles (n=3 is the smallest multiple which scores points)
• If the multiple contains both shades of a color, the minority shade counts for half (e.g., 4 dark blues and 3 light blues would count for (4 + 3/2 - 2) = 3.5 points)

With few tiles of a base color, more points are scored by combining both shades. But with a significant number of both shades, two multiples, each containing only a single shade, will score more points.

Scoring Rules

A single tile may only contribute to one rainbow, and to one multiple. However, these are independent, so a tile may contribute to a rainbow and to a multiple simultaneously.

Bots don't need to worry about finding the optimal groupings of tiles into rainbows and multiples themselves; this will be figured out by the controller.

Color Pool

In order to create scarcity, base colors will have varying weights, chosen randomly at the start of the game, and given to bots. E.g., a game might have a pool of tiles which is 25% blues, but only 2% reds. The initial tiles given to bots are always chosen uniformly, as is whether a tile is light or dark.

Knowledge

Bots will have nearly full knowledge of the game state; one thing which is secret is other bots' initial sets of tiles, which must be inferred.

Bots will be able to maintain state between rounds and between games, so they can attempt to refine winning strategies if they're sufficiently capable.

Answer 17

Alien Weekends

I've crash-landed on another planet! Luckily, the alien society I landed in is almost identical to that of Earth's, except for their timekeeping. Their calendar doesn't use months, so each day is represented by a single nonnegative integer. Each alien week consists of m weekdays followed by an n-day weekend, with the first day of the first week being 0. I'd like to know exactly how many weekdays and weekends are in a week, but I'm too embarrassed to ask.

Fortunately, one of the local aliens started talking about xyr job and mentioned a few days that are part of the week, and a few that are part of the weekend. I'd like some code that could use what xe said in order to tell me how long the week is.

---

Challenge

Given two lists of nonnegative integers (d and e), output two positive integers m and n such that:

• For each weekday di in d, di%(m+n)<m
• For each weekend day ei in e, ei%(m+n)>=m

Alternatively, you may output m+n and either m or n. If you wish, you can take input as 1-indexed: that is, the first week starts on 1, (di-1)%(m+n)<m and (ei-1)%(m+n)>=m. If you use an alternative input or output method, mention it in your answer. You are guaranteed that there exists at least one pair of valid m and n values. If multiple outputs are possible, you may output any of them.

---

Examples

[0, 3, 4, 8, 11], [5, 6, 12] -> 5, 2

The alien (yet familiar) calendar looks like this:

A  B  C  D  E  F  G
-------------- ~~~~~
0  1  2  3  4  5  6
7  8  9  10 11 12 13

Days A (0), B (8), C, D (3), and E (4, 11) are weekdays, while F (5, 12) and G (6) are weekends. Note that the calendar will always begin on a weekday, and end on a weekend.

---

[0, 2, 6], [7, 9] -> 1, 1 OR 6, 3/4/5/...

The calendar might look like this:

A B
- ~
0 1
2 3
4 5
6 7
8 9

OR like this:

A B C D E F G H I
----------- ~~~~~
0 1 2 3 4 5 6 7 8

As such, both 1, 1 and 6, 3 are valid outputs. Notably, 6, 4 or 6, [integer greater than 2] are also valid, with none of the mentioned days occurring on the second week.

---

Samples

TODO

---

code-golf number

Answer 18

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 19

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 20

DeCSS

It is known that the DVD Content Scrambling System can be deciphered with a rather short program (434 bytes of C, 472 bytes of Perl). Can you do better?

<< Test cases go here >>

---

I don't plan to include a more detailed spec, because it will just wind up duplicating some of the code. The test cases would be in the form of (key, link to data file, md5sum of the deciphered stream).

Answer 21

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 22

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 23

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 24

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 25

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 26

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 27

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 28

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 29

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 30

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.