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

Two mountain hikers want to meet, but must stay at the same altitude

This question is totally inspired by this question on Puzzling SE. For ease, I have reproduced the original question here:

Two hikers are separated by a two-dimensional mountain range, like the one shown below. The mountain range alternates between peaks and valleys, connected by straight lines.

Both hikers are at sea level, and the mountain range never dips below sea level.

The two hikers want to meet up with each other. Prove that they can do this while staying at the same altitude as each other for their entire journey. They are allowed to backtrack.

Source: http://www.cs.cmu.edu/puzzle/puzzle12.html

Input/Output

Meta: what input/output format would be better?

Continuous:

• Input: a list of ordered pairs (x,y) that represent the peaks and valleys.
• Output: a sequence of positions where one hiker or both changes direction, formatted like so:

(x1 y1) (u1 v1)
(x2 y2) (u2 v2)
(x3 y3) (u3 v3)
...

Discrete:

• Input: a sequence of heights that represent the height of the terrain (with no flat portions). (I.e., 0 1 2 3 4 5 4 3 4 5 6 7 6 5 6 5 4 3 2 3 2 1 0, maybe with steps larger than 1?)
• Output: the left/right moves each hiker has to make, outputted like

L R
L L
L L
R L
...

Scoring

• Scoring is in bytes.
• Bonus: -5% if your program produces optimal solutions.

Meta:

• I'm pretty sure this is not a duplicate, but still, is it?
• I'd like a better title. Would "Mountain Hikers" be good enough?
• Any other feedback?

Answer 2

Bridge Flowers code-golf

---

One of the example inputs for this challenge is a really minor puzzle in Undertale, and the example output is the solution. You have been warned.

In the Underground, there is a mysterious plant known as the Bridge Flower. They always come in groups of four Bridge Seeds, and have some interesting properties:

• When dropped in water, a Bridge Seed floats away from you in the direction you were facing when you dropped it. It floats until it hits a wall or another Bridge Seed, at which point it stops moving.
• If four Bridge Seeds are touching, forming a straight line, and none of them are moving, they will bloom into Bridge Flowers. Bridge Flowers can support a monster's weight (or a human, but when will that ever happen?), hence the name.
• Another mysterious plant, the Bell Blossom, has a special interaction with Bridge Flowers. The Bell Blossom can be rung to turn all Bridge Flowers back into Bridge Seeds and return them to their original spot.

Consider this map, where . is ground, is water, and X is a Bridge Seed. You'll always be on the part of the map where the Bridge Seeds are. The gap is only four tiles wide, so it's quite easy to make a bridge of Bridge Flowers.

........    ........  |  ........    ........
..X.....    ........  |  ........    ........
.X.X....    ........  |  ........XXXX........
..X.....    ........  |  ........    ........
........    ........  |  ........    ........

Here's a slightly more difficult gap to cross. Even though the straight-line distance is longer than four tiles, you can make it across with a little bit of thought.

........       ........  |  ........       ........
..X.....       ........  |  ........       ........
.X.X....       ........  |  ........       ........
..X.....       ........  |  ........       ........
........       ........  |  ........       ........
..         ............  |  ..     XXXX............
..         ............  |  ..         ............

Here's one that's even trickier than the last two. Most of this river is three tiles wide or fewer, so you can't simply make a straight-line bridge across! Thinking outside the box, though, you'll arrive at the solution.

....   ............  |  .... X ............
...   .............  |  ...  X.............
....   ............  |  .... X ............
.....  ............  |  .....X ............
....   ...X.X......  |  ....   ............
....   ...X.X......  |  ....   ............
     ..............  |       ..............
       ............  |         ............

For this challenge, write a program or function that takes a map like the ones here and outputs the same map, but with the puzzle solved (the Bridge Seeds moved to the final position of the Bridge Flowers). If there's more than one possible answer, any of them will do. You may assume there will be exactly two areas of land separated by water, with the one that you start on denoted by the presence of exactly four Bridge Seeds.

If the program can't find an answer... well, just because it's impossible doesn't mean you should give up! Don't lose your Determination! Output Ding to sound the Bell Blossom, reset the Bridge Seeds and try again!

Answer 3

Based on this question in the Puzzling SE. Not 100% sure on the scoring, and this is my first time posting a PPCG challenge, so I'd appreciate any suggestions on improving it.

---

Unicode Box Drawing

Write a program which outputs a diagram using all of the standard Unicode box drawing characters:

─ │ ┌ ┐ └ ┘ ├ ┤ ┬ ┴ ┼
═ ║ ╔ ╗ ╚ ╝ ╠ ╣ ╦ ╩ ╬
    ╒ ╕ ╘ ╛ ╞ ╡ ╤ ╧ ╪
    ╓ ╖ ╙ ╜ ╟ ╢ ╥ ╨ ╫

The diagram should have no loose ends, so:

┌┐ <-Allowed  ┌┐ <-Not allowed  ┌┐┌┐ <-Allowed
└┘            └┴                └┴┴┘

Also, single lines should line up with other single lines, and double with double:

├─, ╟─, ╠═, ╞═ <-Allowed  ├═, ╟═, ╠─, ╞─ <-Not allowed

The diagram must use each of the 40 characters at least once, and must form one contiguous, connected shape. Because the characters might look different depending on your browser font, do not consider the space between double lines to be an actual separation. Separations can only be between two characters. In other words:

┌╖ <-Allowed  ┌┐┌┐ <-Not allowed
└╜            └┘└┘

Your code must compute the diagram from scratch. You may not create an already existing diagram and just print it out. A bonus of 20% will be awarded if your program outputs a different valid diagram based on a random seed. (This seed may be provided as input, or you may use system time, read the seed from a file, or any other means you choose.) Note that a random seed may be provided externally, but the diagram itself may not. If you implement this bonus, please provide multiple examples showing different output.

This is code-golf, so scoring will be based on the number of bytes in the source code. In addition, the length of the output will also be counted. You get 40 characters free to account for the required characters. Any additional characters will come at a 10% penalty. This includes spaces/tabs, and any duplicate graph pieces. Newlines are free (to be fair to the differences between OSs).

If your program produces multiple outputs of different lengths (due to randomness), you may use the shortest output produced, but you must provide a seed that results in that output so it can be verified. Since this might be difficult if you used system time as a seed, entries using system time must somehow prove that they are capable of producing the smallest claimed output. (For instance, if they produce the same length output every time, or produce the minimum claimed output at least 50% of the time.)

So in summary:

• Take length of source code in bytes.
• Add 10% for each whitespace character (not counting newlines) or duplicated character in the output.
• Subtract 20% if you implement the random seed input.

Standard loopholes apply.

Answer 4

Find pattern in pixel carpet

[insert story why this needs to be as short as possible]

Given an image the goal is finding the biggest* connected* pattern of pixels, that occurs more than once. If there is more than one distinct pattern of maximum size, find the one that occurs more.

The output should consist of mask (bw image) of the size of the input, that is black where the copies of the pattern were on the original image, and white otherwise.

* Specs

• Biggest as in number of pixels
• connected means four connected

Two instances of the pattern must not overlap.

Example

Meta

• consider rotations / mirroring of the patter too, or only translations?
• runntime requirement?

Answer 5

Optional parentheses

In text, parentheses can denote optional asides. These (often intrusive) additions can be read or skipped over, either option giving a valid sentence. Given a string with parentheses, possibly nested, output all possible readings where each parenthesized section may be omitted.

The(( quick)( brown)) fox jumps( over the( lazy) dog).

The fox jumps.
The quick fox jumps.
The brown fox jumps.
The quick brown fox jumps.
The fox jumps over the dog.
The quick fox jumps over the dog.
The brown fox jumps over the dog.
The quick brown fox jumps over the dog.
The fox jumps over the lazy dog.
The quick fox jumps over the lazy dog.
The brown fox jumps over the lazy dog.
The quick brown fox jumps over the lazy dog.

The outputs can be in any order, but must be distinct. Note the case of (( quick)( brown)), where omitting both quick and brown is redundant with omitting the whole expression. But, the input won't contain any parens that enclose the empty string or are redundant with another pair of pairs.

You may not use regular expressions.

The input string will consist of only letters, spaces, punctuation .,, and parens (). The parens will be properly matched.

Answer 6

Compete with awk

fastest-code

The goal of this challenge is to see if the assertion often see in awk question on SO is true:

This would be faster in whatever

Test Input

A 10 million lines file generated by this script line:

awk 'BEGIN{for (i=1;i<=10000000;i++) print (i%5?"miss":"hit"),i,"  third\t \tfourth"}' > file

Head of it:

$ head -10 file
miss 1   third          fourth
miss 2   third          fourth
miss 3   third          fourth
miss 4   third          fourth
hit 5   third           fourth
miss 6   third          fourth
miss 7   third          fourth
miss 8   third          fourth
miss 9   third          fourth
hit 10   third          fourth

Goal:

The main goal is to compete with awk, to benchmark it will be on this challenge description:

• Split each line on any number of spaces (regex [ ]+)
• If the line start by hit X with X being an even number
  • print fields: 4th 1st and 3rd (in this order)

Example output (first 5 lines):

fourth hit third
fourth hit third
fourth hit third
fourth hit third
fourth hit third

Restrictions:

The idea being to compete with awk, your program must behave on the same way:

• The file must be read.
• The match and output order must be modifiable as an awk program can be (Needing a simple code update is OK, it has not to be a command line parameter).
• The number of line in input file should be considered unknown.
• As long as your output can be piped to awk, the submission is valid.

Validation:

Pipe the output of your program to

awk '!seen[$0]++{unq++;r=$0} END{print ((unq==1) && (seen[r]==1000000) && (r=="fourth hit third")) ? "PASS" : "FAIL"}'

If it show PAST, you're in :)

Winner

The fastest code would win, to bench yourself here is a mawk version really competitive (which won't count toward answers as I think it's pretty hard to beat):

awk '/^hit +[0-9]*[02468] / { print $4, $1, $3 }' file

I've build a test suite on github here which build a result table here.

Answers will be integrated within it to bench all answer on the same machine, if there's a specific way to launch your program, make it appear in the answer so I don't penalize your answer by the way it is launched.

Side challenge:

If you wish to save me time and craft a pull request to include your code in the test system, you're welcome.

Answer 7

Count up by factor keys

code-golf math

TODO: Better title

Information

Let the factor key of a number n be the result of the following process:

• Compute the prime factorization of n: n = p₁^e₁ * p₂^e₂ * p₃^e₃ * ... where all p_i are prime, distinct and in increasing order, and all e_i are positive integers.

• Compute each p_i^e_i; call these factors the f_i. So n = f₁ * f₂ * f₃ *....

• Convert each f_i to a string.

• Concatenate all the strings together.

• Evaluate as a number.

Examples:

The factor key of 2376 is 82711, since 2376 = 2³ * 3³ * 11 = 8 * 27 * 11.

The factor key of 931 is 4919, since 931 = 7² * 19 = 49 * 19.

As a special case, the factor key of 1 is 0.

Challenge

Output all positive integers, starting from 1, in increasing orders of their factor keys. If two numbers have the same factor key, output the smaller number first. The output must be separated by a delimiter, but this delimiter can be any non-numeric character. If you choose spaces, your output should start with the following:

1 2 3 4 5 7 8 9 11 13 16 17 19 6 23 10 25 14 27 29 31 37 41 12 43 28 47 36

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

Answer 8

This is currently WIP, but please post feedback if you have any!

---

Best General-Purpose Compression

Abstract

^{This paragraph is meant to summarize, the binding rules are below.}
Your task is to implement the best general purpose compression algorithm in the context of this challenge. You will be given a file corpus which contains a mix of different file types. The goal is to beat an existing answer in terms of overall size. The size is determined by the size of the compiled compression program (and decompression program if they are two different programs) plus the compressed size of the corpus. Your algorithm must beat standard 7z with default settings by at least 10 bytes, or if there is an existing answer, this answer by 10 bytes.

Corpus

This paragraph lists all files that are part of the input to your program, their size and the baseline 7z score in 7z 9.38 beta. Licenses are linked where needed. Disclaimer: There is no political or humorous motivation behind the choices. All files were chosen because of their representation of certain formats or unique compression behavior.

Natural Language

#1 - ASCII - Bibliography of Computer Security Articles 1983-88: Download^Save-As

Uncompressed:      146 119
7z 9.38 beta:       17 142
File name:    articles.law

#2 - ASCII - Pre-Flight Launch Preparation for the Space Shuttle: Download^Save-As

Uncompressed:        44 515
7z 9.38 beta:        15 304
File name:    6_2_4_4_2.TXT

#3 - ASCII - 1984 News report archive about the Bundespost Hack: Download^Save-As (transcribed by Chaos Computer Club, cites full-text articles from Die ZEIT, taz et al.)

Uncompressed:      102 242
7z 9.38 beta:       32 382
File name:    boh-20f8.txt

#4 - ASCII - (Unofficial historical transcript of) His Last Bow by Arthur Conan Doyle: Download^Save-As (lic. Public Domain)

Uncompressed:           330 042
7z 9.38 beta:           110 481
File name:    doyle-his-382.txt

#5 - UTF8 - Transcript of the Rosetta Stone translated to English: Download^RAW->Save-As (lic./© The Nile, Notes for Travelers in Egypt, by E. A. Wallis Budge, 9th Edition, London, Thos. Cook and Son, [1905], pp. 199-211)

Uncompressed:                  18 270
7z 9.38 beta:                   6 299
File name:    Rosetta_EN_UTF8+BOM.txt

Source Code (+ Markdown)

#1 - C - CPU control code taken from the linux kernel: Download^RAW->Save-As (lic. GPL, Rusty Russell)

Uncompressed: 18 866
7z 9.38 beta:  5 683
File name:     cpu.c

#2 - QBASIC - COMBAT ARENA (Game): Download^RAW->Save-As (© Jeff Copperthite)

Uncompressed: 59 792
7z 9.38 beta: 11 921
File name: COMBAT.BAS

#3 - XML - The 9/11 Wikimedia dump: Download (lic. GFDL, CC-BY-SA 3.0)

Uncompressed:                                40 557 621
7z 9.38 beta:                                   578 993
File name:    sep11wiki-20071116-pages-meta-history.xml

#4 - C# - Source of the .NET Framework System.Array (CLR): Download^RAW->Save-As (lic. MIT)

Uncompressed:  133 646
7z 9.38 beta:   15 172
File name:    Array.cs

#5 - JavaScript - jQuery 1.11.3: Download^RAW->Save-As (lic. MIT)

Uncompressed:          284 394
7z 9.38 beta:           73 585
File name:    jquery-1.11.3.js

Binary Media

#1 - JPG - "Flower in the Garden": Download (lic. CC-BY-NC-ND 2.0 & © wellenkern)

Uncompressed: 10 482 521
7z 9.38 beta: 10 434 631
File name:    flower.jpg

#2 - MP3 - "Mariam's Cake" by Robin Grey: Download (lic. CC-BY-NC-SA 3.0)

Uncompressed: 8 468 990
7z 9.38 beta: 8 162 146
File name:     cake.mp3

#3 - Bitmap24 - DP1M7218 16:9 COLOR: Download (lic. CC-BY-SA 3.0 & © iKobe!)

Uncompressed: 37 834 326
7z 9.38 beta: 14 652 746
File name:    street.bmp

#4 - MP4 - "Home 5x5": Download (lic. CC-BY 3.0 & © Michael Jones)

Uncompressed: 6 173 898
7z 9.38 beta: 6 013 047
File name:     home.mp4

#5 - binary - Block of cryptographically secure random data, a.k.a. "The Incompressible File": Download

Uncompressed: 100 000
7z 9.38 beta: 100 129
File name:    rnd.bin

Rules

(De/)Compression Program and Algorithm

1. The program used to compress and decompress a file is the compiled executable (or executable script).
2. You may use two or more programs and ship additional files if needed, however only one program per step (a step is de- or compression) is executed.
3. No program or part of a program is allowed to request resources that are not included in your distribution. Exceptions are standard system resources (clean install, i.e. a Java runtime would not be available when you use Windows).
4. You may use linux-, windows- or architecture-specific code.
5. You must not modify files or file names. The file names listed above are binding. Note: Some downloads may not carry the file name, you have to rename them (case-sensitive). The file names of compressed files do not matter. However, the original file names must be restored after decompression.
6. You can use any existing or new algorithm. Content mixing is of course allowed, however, you may not call any compression routines available on your system (or language). You program must be a self-contained implementation.
7. Your algorithm must not specifically target this corpus, it has to be general purpose. You are however allowed to target the used file types (e.g. by identifying the type via "Magic Bytes" and adjusting the algorithm accordingly).
8. The (de)compression program only accepts one argument, a file name. Piping program output somewhere or providing anything else is forbidden. (I.e. you'll have to write the output file yourself).

Running your entry

Your compression program is called 15 times, once for every file in the corpus:

comp articles.law
comp ...

This process must produce 15 compressed files on disk in the same directory (original files can be overwritten). (comp is just an example name, you don't have to use this name)

Decompression is similar. Your decompression program (which may be the same executable) is called 15 times, once for every file in the corpus:

decomp ...

Where ... is the file name of the compressed file. This will produce the original 15 files on disk (with their original file names) (compare the SHA256 when in doubt).

Neither the compression or decompression program may take any additional command line parameters.

Scoring

Your score is P+C, where

• P is the size of all programs used in your distribution
• C is 15 files, the compressed corpus

in bytes.

Your answer must include the following:

• The source code for all parts of P. (Is not counted in the score).
• A link to a GitHub repository containing both P and C. Means you actually have to run your solution and include all compressed files. If your repository features additional files that should not be included in your score (gitignore, README etc.), put the scored files in a separate folder.

To beat someones score, your score has to beat it by at least 10 bytes. If some answer has the score X, then your answer has to have a score of N <= X-10, where N is your score. The starting score is set by 7z.

Invalid Answers

Please refrain from posting invalid answers, such as:

• Answers without source code for P,
• answers without compressed files, or where compressed files run against P produce anything but the original corpus,
• answers that contain only partial solutions.

For clarity, here's how an answer might look like:

I did this algorithm X. This code is used for compression:

<comp.c>

and this for decompression:

<decomp.c>

I used windows, my score therefore is 9001:

comp.exe:          234 bytes
decomp.exe:        124 bytes
Compressed files: 8643 bytes

You can download the programs and compressed files from my
repository here: github.com/foobar42.

Leaderbaord and History

Current score: 423,424 (P) + 40,229,661 (C) = 40,662,085
Set by: 7z 9.38 beta (Win32) on 2015-12-18

---

code-challenge compression

Answer 9

Add two numbers (or Arithmetic on continued fraction expansions)

code-golf math

Given two continued fraction expansions N,M as lists of integers (in any suitable (human readable) format for your language) and an operation @ (addition, substraction, multiplication and division) +-* or / (e.g. encoded as numbers 1-4 or as characters or whathever is suitable for your language) return N@M (the sum/difference/product/ratio) again in the form of a continued fraction expansion.

By continued fraction expansion I mean a simple continued fraction expansion which are of the form:

                   1
 a0 + -----------------------
                     1
       a1 + ------------------
                       1
             a2 + ------------
                         1
                   a3 + ------
                          ...
                

Which will be represented as a list of the form [a0,a1,a2,a3,...]

Meta

Is this too complicated? Should the challenge be reduced to only one operation e.g. + or *?

Answer 10

Number of cells used in optimal BF representation of a constant

Relevant.

Your task is deceptively simple. Given a number n (or a character C with char code value n in your encoding), output the number of cells utilized in the optimal representation of that number n in a standard Brainf*** interpreter with 0 <= n <= 255. (8-bit wrapping.)

Examples

> input
< output

> 4
< 1   ; ++++

> 0
< 1   ; empty program

> 201
< 4   ; >+[-->-[-<]>]>+

> 190
< 5   ; ++[-->-[<]>-]>

> 185
< 2   ; -[>-<-------]>++

> 255
< 1   ; -

> 242
< 1   ; --------------

> 241
< 2   ; ---[>-----<+]>

---

Meta

Does more describing need to be done? Should I just remove the bonuses? Bonuses removed.

Answer 11

Roll a Die

code-golf ascii-art

Most of the time in PPCG, challenges that involve dice rolling normally focus on some numeric property. However all I want you to do is to actually display the die itself in an isometric 3D format.

Your program or function should accept two optional integers representing the numbers to be displayed on the top and the front of the die respectively. If no valid value for the top is given then one of the 24 possible rolls should be uniformly chosen (but it does not need to be completely random so a time-dependent result is acceptable). If no valid value for the front is given then one of the 4 valid values should be uniformly chosen.

The die to be displayed is a standard Western die. Example: when rolling a 4, if the 1 is at the front, the number to the right is a 5; to display any other number would be an error. A more complex example is also shown below; in this case, not only is the 2 the correct number to display on the right, but all three numbers must be displayed as shown, i.e. the diagonal of the number 2 must point from 1/4 to 3/6 and not 1/3 to 4/6; the diagonal of the number 3 must point from 1/5 to 2/6 and not 1/2 to 5/6; the number 6 must point from 3 to 4 and not from 2 to 5.

    o-------o     o-------o 
   / *   * /|    / *   * /| 
  /       /*|   / *   * / | 
 / *   * /  |  / *   * /  | 
o-------o*  | o-------o*  | 
|       | * | |     * |   | 
|       |  *o |       |  *o 
|   *   |  /  |   *   |  /  
|       |*/   |       | /   
|       |/    | *     |/    
o-------o     o-------o     

You must draw all the sides, corners and pips preferably using the characters as shown above. Additional whitespace is permissible if you are consistent (only the pips may vary between rolls).

This is code-golf, so the shortest answer will be the winner.

Reference code (Batch):

@echo off
setlocal enableextensions
call :%1%2 2>nul
if errorlevel 1 call :%1 2>nul
if errorlevel 1 goto %time:~6,1%
goto :eof
:1
set /a front = (%time:~7,1% %% 2) * 2 + (%time:~9,1% %% 2) + 2
goto 1%front%
:2
set /a front = (%time:~7,1% %% 2) * 3 + (%time:~9,1% %% 2) * 2 + 1
goto 2%front%
:3
set /a front = (%time:~7,1% %% 2) * 4 + (%time:~9,1% %% 2) + 1
goto 5%front%
:4
set /a front = (%time:~7,1% %% 2) * 4 + (%time:~9,1% %% 2) + 1
goto 5%front%
:5
set /a front = (%time:~7,1% %% 2) * 3 + (%time:~9,1% %% 2) * 2 + 1
goto 5%front%
:6
set /a front = (%time:~7,1% %% 2) * 2 + (%time:~9,1% %% 2) + 2
goto 6%front%
:12
echo     o-------o
echo    /       /^|
echo   /   *   /*^|
echo  /       /  ^|
echo o-------o   ^|
echo ^| *     ^| * ^|
echo ^|       ^|   o
echo ^|       ^|  /
echo ^|       ^|*/
echo ^|     * ^|/
echo o-------o
goto :eof
:13
echo     o-------o
echo    /       /^|
echo   /   *   /*^|
echo  /       /  ^|
echo o-------o*  ^|
echo ^|     * ^| * ^|
echo ^|       ^|  *o
echo ^|   *   ^|  /
echo ^|       ^|*/
echo ^| *     ^|/
echo o-------o
goto :eof
:14
echo     o-------o
echo    /       /^|
echo   /   *   / ^|
echo  /       /  ^|
echo o-------o*  ^|
echo ^| *   * ^|   ^|
echo ^|       ^|  *o
echo ^|       ^|  /
echo ^|       ^| /
echo ^| *   * ^|/
echo o-------o
goto :eof
:15
echo     o-------o
echo    /       /^|
echo   /   *   /*^|
echo  /       /  ^|
echo o-------o*  ^|
echo ^| *   * ^|   ^|
echo ^|       ^|  *o
echo ^|   *   ^|  /
echo ^|       ^|*/
echo ^| *   * ^|/
echo o-------o
goto :eof
:21
echo     o-------o
echo    / *     /^|
echo   /       /*^|
echo  /     * /  ^|
echo o-------o*  ^|
echo ^|       ^|   ^|
echo ^|       ^|  *o
echo ^|   *   ^|  /
echo ^|       ^|*/
echo ^|       ^|/
echo o-------o
goto :eof
:23
echo     o-------o
echo    /     * /^|
echo   /       / ^|
echo  / *     /  ^|
echo o-------o   ^|
echo ^| *     ^| * ^|
echo ^|       ^|   o
echo ^|   *   ^|  /
echo ^|       ^| /
echo ^|     * ^|/
echo o-------o
goto :eof
:24
echo     o-------o
echo    /     * /^|
echo   /       /*^|
echo  / *     /* ^|
echo o-------o*  ^|
echo ^| *   * ^|   ^|
echo ^|       ^|  *o
echo ^|       ^| */
echo ^|       ^|*/
echo ^| *   * ^|/
echo o-------o
goto :eof
:26
echo     o-------o
echo    / *     /^|
echo   /       / ^|
echo  /     * /  ^|
echo o-------o*  ^|
echo ^| * * * ^| * ^|
echo ^|       ^|  *o
echo ^|       ^|  /
echo ^|       ^| /
echo ^| * * * ^|/
echo o-------o
goto :eof
:31
echo     o-------o
echo    /     * /^|
echo   /   *   /*^|
echo  / *     /  ^|
echo o-------o   ^|
echo ^|       ^|   ^|
echo ^|       ^|   o
echo ^|   *   ^|  /
echo ^|       ^|*/
echo ^|       ^|/
echo o-------o
goto :eof
:32
echo     o-------o
echo    / *     /^|
echo   /   *   /*^|
echo  /     * /  ^|
echo o-------o* *^|
echo ^|     * ^|   ^|
echo ^|       ^|* *o
echo ^|       ^|  /
echo ^|       ^|*/
echo ^| *     ^|/
echo o-------o
goto :eof
:35
echo     o-------o
echo    / *     /^|
echo   /   *   / ^|
echo  /     * /  ^|
echo o-------o   ^|
echo ^| *   * ^| * ^|
echo ^|       ^|   o
echo ^|   *   ^|  /
echo ^|       ^| /
echo ^| *   * ^|/
echo o-------o
goto :eof
:36
echo     o-------o
echo    /     * /^|
echo   /   *   /*^|
echo  / *     /  ^|
echo o-------o*  ^|
echo ^| *   * ^| * ^|
echo ^|       ^|  *o
echo ^| *   * ^|  /
echo ^|       ^|*/
echo ^| *   * ^|/
echo o-------o
goto :eof
:41
echo     o-------o
echo    / *   * /^|
echo   /       /*^|
echo  / *   * /  ^|
echo o-------o*  ^|
echo ^|       ^| * ^|
echo ^|       ^|  *o
echo ^|   *   ^|  /
echo ^|       ^|*/
echo ^|       ^|/
echo o-------o
goto :eof
:42
echo     o-------o
echo    / *   * /^|
echo   /       / ^|
echo  / *   * /  ^|
echo o-------o   ^|
echo ^|     * ^| * ^|
echo ^|       ^|   o
echo ^|       ^|  /
echo ^|       ^| /
echo ^| *     ^|/
echo o-------o
goto :eof
:45
echo     o-------o
echo    / *   * /^|
echo   /       /*^|
echo  / *   * /  ^|
echo o-------o* *^|
echo ^| *   * ^|   ^|
echo ^|       ^|* *o
echo ^|   *   ^|  /
echo ^|       ^|*/
echo ^| *   * ^|/
echo o-------o
goto :eof
:46
echo     o-------o
echo    / *   * /^|
echo   /       /*^|
echo  / *   * /  ^|
echo o-------o   ^|
echo ^| *   * ^|   ^|
echo ^|       ^|   o
echo ^| *   * ^|  /
echo ^|       ^|*/
echo ^| *   * ^|/
echo o-------o
goto :eof
:51
echo     o-------o
echo    / *   * /^|
echo   /   *   / ^|
echo  / *   * /  ^|
echo o-------o*  ^|
echo ^|       ^| * ^|
echo ^|       ^|  *o
echo ^|   *   ^|  /
echo ^|       ^| /
echo ^|       ^|/
echo o-------o
goto :eof
:53
echo     o-------o
echo    / *   * /^|
echo   /   *   /*^|
echo  / *   * /* ^|
echo o-------o*  ^|
echo ^| *     ^|   ^|
echo ^|       ^|  *o
echo ^|   *   ^| */
echo ^|       ^|*/
echo ^|     * ^|/
echo o-------o
goto :eof
:54
echo     o-------o
echo    / *   * /^|
echo   /   *   / ^|
echo  / *   * /  ^|
echo o-------o   ^|
echo ^| *   * ^| * ^|
echo ^|       ^|   o
echo ^|       ^|  /
echo ^|       ^| /
echo ^| *   * ^|/
echo o-------o
goto :eof
:56
echo     o-------o
echo    / *   * /^|
echo   /   *   /*^|
echo  / *   * /  ^|
echo o-------o*  ^|
echo ^| * * * ^|   ^|
echo ^|       ^|  *o
echo ^|       ^|  /
echo ^|       ^|*/
echo ^| * * * ^|/
echo o-------o
goto :eof
:62
echo     o-------o
echo    / * * * /^|
echo   /       /*^|
echo  / * * * /  ^|
echo o-------o*  ^|
echo ^| *     ^|   ^|
echo ^|       ^|  *o
echo ^|       ^|  /
echo ^|       ^|*/
echo ^|     * ^|/
echo o-------o
goto :eof
:63
echo     o-------o
echo    / *   * /^|
echo   / *   * / ^|
echo  / *   * /  ^|
echo o-------o*  ^|
echo ^|     * ^|   ^|
echo ^|       ^|  *o
echo ^|   *   ^|  /
echo ^|       ^| /
echo ^| *     ^|/
echo o-------o
goto :eof
:64
echo     o-------o
echo    / *   * /^|
echo   / *   * /*^|
echo  / *   * /  ^|
echo o-------o*  ^|
echo ^| *   * ^| * ^|
echo ^|       ^|  *o
echo ^|       ^|  /
echo ^|       ^|*/
echo ^| *   * ^|/
echo o-------o
goto :eof
:65
echo     o-------o
echo    / * * * /^|
echo   /       /*^|
echo  / * * * /  ^|
echo o-------o   ^|
echo ^| *   * ^| * ^|
echo ^|       ^|   o
echo ^|   *   ^|  /
echo ^|       ^|*/
echo ^| *   * ^|/
echo o-------o

---

        o-------o
        | *   * |
        |       |
        |   *   |
        |       |
        | *   * |
o-------o-------o-------o-------o
| *   * |       | *     | * * * |
|       |       |       |       |
|       |   *   |   *   |       |
|       |       |       |       |
| *   * |       |     * | * * * |
o-------o-------o-------o-------o
        | *     |
        |       |
        |       |
        |       |
        |     * |
        o-------o


    o-------o
   / * * * /|
  / * * * /*|
 / * * * /* |
o-------o* *|
| * * * | * |
|       |* *o
| * * * | */
|       |*/
| * * * |/
o-------o

Answer 12

Polyphonic Pitch Detection

Tags: code-challenge test-battery

Sandbox Notes

• Still in progress. I haven't made any of the test cases or snippets yet.
• I'm not sure what to tag this as. It doesn't quite fit the definition of any existing tags. math maybe?
• I'm thinking of making a monophonic version of this challenge as a precursor to this one, since monophonic pitch detection is much easier and this one may be too difficult for most to attempt. Also note that monophonic would have more of an emphasis on perfecting an algorithm, rather than getting it to work at all.

---

Take an array of samples, and output the frequencies of the waveforms found in the samples.

---

Despite how simple this may sound, it is actually quite difficult. Even though it has been researched for almost a century, a robust and versatile algorithm for polyphonic pitch detection is yet to be found. Let's look at a simple waveform as an example:

^{(The X-axis is in 1/440ths of a second, use the "Play Samples" snippet below to hear what it sounds like)}

This is a 440hz sine wave. In musical terms, it is middle A or A4. The next image is a 554hz sine wave (or C#5) on top of the 440hz wave:

It looks exactly the same, except slightly "squashed" (and sounds a bit "higher"). It is a major 3rd above A4, which means they sound pleasant when played together, however when you look at the waveform that adding them together creates:

The resulting waveform appears vastly different. To further complicate matters, it changes shape depending on the time. There are other factors like overtones, background noise and the fact that real-world waveforms are more complex than sine waves which also make it tricky. (But the human brain still manages to do this effortlessly!)

Your Task

Receive a list of samples as signed 16-bit integers at a fixed sample-rate of 44100 samples-per-second. The input waveform will contain between 1 and 5 (inclusive) simultaneous frequencies in the range of 100hz to 2000hz.

You must output a list of frequencies detected (in hertz) with up to 2 decimal places of precision.

Test Cases

Each test case is on it's own line. Each line begins with the name of the test case, followed by a semi-colon (;), then the frequencies present in the test case (accurate to 2 decimal places) separated by commas (,), followed by another semi-colon, then the samples separated by commas:

Test Case Name;123.45,67.8,90.12;3,75,1234,56789,4321,-23,-408,-9266,41,0,etc...

Each test case will be exactly 44100 samples (1 second) long.

(link to test case file, will include synthesized waveforms, real instrument sounds, multiple instrument/waveform types, a variety of harmonies and pitches, combinations of each of these)

Scoring

The score of a submission is a percentage based on how close the submission's results are to the actual frequencies of each test case. Specifically it will calculated using the formula in the snippet below (use this to calculate your score):

(snippet for calculating score)

Rules

• No built-ins that detect pitch or extract waveform frequencies are allowed.
• Helper functions that are designed to aid frequency analysis like FFT are permitted.
• You may optimise your solution for the test cases, but you cannot hard-code the results for these specific test cases.

Play Samples

You can hear what certain frequencies or a list of samples sounds like by pasting them into this snippet (requires a browser that supports the Web Audio API):

document.write('Enter frequencies separated by commas: <input type="text" ' +'id="Frequencies" value="440,554"><br>' +'<button id="Play" onclick="togglePlay()">Play</button><br>' +'Paste the whole test case line here: <input type="text" id="Test"><br>' +'<input type="checkbox" id="Loop"> Loop?<br>' +'<button id="PlayTest" onclick="togglePlayTest()">Play</button>');var position = 0,samples = null,sampleSize = 0xffff + 1,halfSampleSize = sampleSize / 2,bufferSize = 4096,sampleRate = 44100,context = new AudioContext(),processor = context.createScriptProcessor(bufferSize, 1, 1),oscillators = null;processor.connect(context.destination);processor.onaudioprocess = function(e) {var buffer = e.outputBuffer.getChannelData(0);if(samples) {var sampleLength = samples.length,loop = Loop.checked;for(var i = 0; i < bufferSize; i++) {position += sampleRate / context.sampleRate;if(loop) position %= sampleLength;buffer[i] = ~~samples[position | 0] / halfSampleSize;}if(position >= sampleLength) togglePlayTest();}else buffer.fill(0);};function togglePlayTest() {if(samples) {samples = null;PlayTest.textContent = "Play";}else {var parts = Test.value.split(";");if(parts.length > 1) {PlayTest.textContent = "Stop - " + parts[0] + " (" +parts[1].split(",").map(function(f) { return f + "hz"; }).join(", ") +")";samples = parts[2].split(",").map(function(n) { return +n; });position = 0;}}}function togglePlay() {if(oscillators) {oscillators.forEach(function(o) { o.stop(); });oscillators = null;Play.textContent = "Play";}else {oscillators = [];var frequencies = Frequencies.value.split(","),gain = context.createGain();gain.gain.value = 1 / (frequencies.length + 1);gain.connect(context.destination);frequencies.forEach(function(frequency) {var oscillator = context.createOscillator();oscillator.frequency.value = frequency;oscillator.connect(gain);oscillator.start();oscillators.push(oscillator);});Play.textContent = "Stop";}}

Links

• MUSIC Algorithm
• ESPRIT Algorithm
• YIN Algorithm (monophonic pitch detection)

Answer 13

Anything but stacks

language-design

---

Stack-based languages are, like totally, all the rage these days. From GolfScript, to CJam, to MATL, it seems like stack-based languages are popping up everywhere. But now, it is time to push forward and explore new memory models.

In this challenge, you are to create a new programming language based off of any other data structure.

---

Still undecided is the "goal" of this challenge. The main idea is that, by using a unique data structure, these new languages may have advantages for certain types of problems. Since different languages would use different structures, however, there's not any single set of challenges that would provide a fair comparison. An alternative idea is to pick a single data structure and have everybody use it.

---

I'm going to work off the "use a specific data structure" idea, since that's really the only thing that can narrow the focus of this question. So, maybe some options are...

• Queues
• Trees (except I'm not sure how a "tree without branching" would be different from a "stack")
• Priority Queues
• Sets, etc.
• Associative arrays (dicts/hashmaps)

The next step might be to find some types of problems to target. Are there any algorithms that are known to be exceptionally difficult to implement with a stack?

Answer 14

Write Hamlet in 1024 bytes

Here is a text file containing Shakespeare's play Hamlet.

You will write a program, less than 1024 bytes in length, that outputs this text to a file, STDOUT or nearest available equivalent. Since this is clearly impossible, you don't have to output the exact text, just get as close as possible.

To measure how close your output is to the original, use the Python 3 script below. It works by concatenating the original text onto the end of your file, then compressing the result using the lzma algorithm, and then subtracting the compressed size of your file alone. This works because if your file contains a lot of common features with the original then the compression algorithm can take advantage of this to make a smaller file. A more sophisticated version of this idea is called normalised compression distance.

All answers should contain the code, at least a brief explanation of how it works (full explanations are encouraged), and the first 2000 characters or so of its output.

This is code-challenge. Scores are calculated using the script below. The lowest score wins.

Rules and clarifications

• Your program must be completely self-contained within a single file, taking no input, loading no files, and executing no other programs. Importing libraries is permitted.

• Your program must run deterministically, producing the same output every time

• Your output must contain only printable ASCII characters, tabs and newlines. (That is, characters with codes 32 to 126 inclusive, plus 9 and 10.) The comparison script checks for this.

• Your output must be the same size as the original file, 182581 bytes.

• You may not use any built-ins or library code that provides compression or decompression algorithms. (e.g. lzma, bz2 etc.) It's OK to use them if you can implement them yourself inside the character limit. Base conversion is OK, and libraries implementing data structures such as Huffman trees are OK.

• If for some reason your language or one of its libraries contains a function that outputs some or all of the text of Hamlet, you may not use that function.

• Your program must be written in a programming language, as defined in this answer. This definition must apply to your source code, not just to any compiler/interpreter flags used to run it.

• In the case of any inconsistency in the script's behaviour between machines, the version on my machine is the definitive one. (Python 3.4.3 on a Mac.)

Here is the comparison code to use. It requires Python 3 because of the lzma dependency. (lzma is much better than bz2 or gzip for this purpose.) It requires the text file linked above to be in the same directory with the name ORIGINAL.txt. Run it with a command like

python3 compare.py my_output.txt

[to do: produce and supply a zip file containing this script together with ORIGINAL.txt]

import lzma
import sys

with open("ORIGINAL.txt", 'r') as file:
    orig = file.read()

with open(sys.argv[1], 'r') as file:
    text = file.read()

def csize(txt):
    return len(lzma.compress(txt.encode('utf-8')))

character_codes = {ord(c) for c in text}
valid_codes = set([9,10] + list(range(32,127)))
if character_codes - valid_codes:
    print("NOT VALID: file contains a non-printable character")
else:
    print( csize(text + orig) - csize(text) )

Technical notes

The compressed size of the original file is 64976 bytes. In an ideal world the original file would have a score of 0, but it actually scores 100. Shakespeare's Macbeth scores 61776, so that should probably be considered a pretty good score.

Tags: code-challenge compression

Answer 15

Create an unkillable Windows process

code-golf

In various versions of the Microsoft Windows operating system, it is possible for a process to enter a state where it cannot be killed by the 'End Process' feature in the Task Manager. Your goal is to create a user-mode program that enters such a state (or spawns a process that does) using as few bytes of code as possible. Please state the version of Windows on which you have tested the program.

Some techniques for creating unkillable processes can be found here.

Be warned that such processes may cause a performance impact, so be prepared to reboot if necessary when testing any of these programs.

TODO:

• Minimum version? The #1 in the accepted answer seems too easy.
• #2 is also lame so maybe taskkill should be the standard instead of Task Manager.

Answer 16

The greatest power...

code-golfnumber-theorysequence

Yeah, I'm still trying to come up with a better title...

A positive integer n is a perfect power of order k if it can be written in the form mk for some integer m. The greatest power of n is the largest number k for which n is a perfect power of order k. Some examples:

• 9 = 32 is a perfect square, and it cannot be written in the form mk for k > 2, so it's greatest power is 2.
• 16 = 42 is also a perfect square. However it can also be written as 16 = 24, so it's greatest power is 4 instead.
• 24 = 241 is not a perfect power of any order k > 1 so it's greatest power is 1.

The Challenge

Given a positive integer n > 1, determine its greatest power. This is OEIS entry A052409 (with a(1) defined as 0, but you don't need to handle that).

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Standard code-golf rules apply.

The first 100 terms of the sequence (starting from n = 2) are:

1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 
3, 1, 1, 1, 1, 5, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1

Answer 17

code-golf

**The Noether Challenge**

It is Emmy Noether's birthday. She was a pioneer in the field of ring theory.

The challenge is to compute two graph-theoretic invariants of a certain graph we can associate with any ring R.

For this challenge, we don't require a unity (multiplicative neutral element) in R, do require the commutativity of multiplication, and additionally require that the ring have finitely many elements. That is, we want to consider finite commutative rings, not necessarily unitary. From now on, "ring" will mean just that.

We will also need the concept of a zero divisor. A zero divisor of a ring R is an element r of R such that r*s=0 for some non-zero s in R. 0 is a trivial example of a zero divisor in any ring with more than one element since it can be shown that 0*s=0 always.

Something Emmy Noether didn't think about is zero-divisor graphs. They have, however, been quite extensively studied recently. The zero-divisor graph of a ring is simple, undirected graph formed as follows. The vertices are the the zero divisors excluding 0. Two vertices r and s are connected by an edge whenever r*s=0, excluding the cases in which r=s (that is excluding possible loops).

In this challenge you are given a file with (addition and) multiplication table(s) for some ring R as input. Your program in any language has to output the diameter and the girth of the zero-divisor graph of R.

The file's name is "ring" and it's a text file. You may assume any extension you wish. Depending on your preference, you may assume that the addition table is not present. If it is, it comes below the multiplication table. The ring is assumed to have at most 62 elements and the elements can be denoted by any subset of the alphanumeric characters including lower- and upper-case letters of the English alphabet. The only other characters assumed to be in the file are the whitespace, the newline, "+" and "*". The "0" character is reserved for 0, so you don't need to check which label stands for 0. The rows and columns for 0 come next after the label rows and columns in both tables. The character "1" doesn't have any special meaning.

The first row and the first column of each table are reserved for labels and the labels' order is the same everywhere (in both tables and both in the columns and in the rows). The upper-left-most character of the multiplication table is "*" and the upper-left-most character of the addition table is "+". The characters in either table are not separated. "*" is the first character in the file. You may assume anything you want about the numbers of whitespaces that follow each row of either table before there's a new line. If two tables are present, they are separated by exactly one additional newline. You may assume whatever you want about the number of newlines and whitespace after the last table.

The output is two numbers, in whatever human-readable and human-understandable form. And the form shouldn't make the user angry. They are to represent the girth and the diameter of the zero-divisor graph. If either of the invariants is infinite, again, it's up to you how you want to output them but it needs to be understandable. If you want to use a nonstandard symbol, like "i", for that, tell the user what it means. We assume that the input is valid. In particular, we assume that the operations in the file are actually ring operations! Your code should be ready to go in whatever way is standard for your language of choice. It shouldn't need any more code to run.

Reading up and research are encouraged, but if you want to use some non-obvious mathematical fact, please give a source or a proof. And in general, please explain how your program works. All standard loopholes are disallowed.

Answer 18

Igpā Atinlā (Pig Latin)

This is code-golf.

In this challenge, we will be translating strings of words to Pig Latin.

Input: A string of words (a "word" is a continuous sequence of the characters A-Za-z) (ASCII only).

Output: The translated version of the input. Translations described below.

Some Definitions:

First, the following are vowels: "A,a, E,e, I, i, O, o, U, u". Any alphabet character that is not a vowel is a consonant. A consonant cluster is any continuous sequence of consonants surrounded on both sides by non consonant characters (or beginning/end of input). An example, the clusters are in bold:

"I am two hundred years young, you child-mother."

A word is a set of alphabet characters surrounded on both sides by non-alphabet characters.

Translation:

1. If the string "'s" or "'d" or "'t" appears ("apostrophe s/d/t"), remove the apostrophe.

For each word in the string, do the following:

2. If a word only contains capital letters (A-Z), ignore the next step.

3. If the beginning of the word was a capital letter (A-Z) AND a consonant, change it to its lower-case equivalent (a-z). Then capitalize the first vowel in the word. If no vowel exists, then recapitalize the letter. e.g. Stretch --> strEtch, "Twxx" --> "Twxx"

4. If the word begins with a consonant cluster, move that consonant cluster to the end of the word. e.g. stretch --> etchstr

5. Append the "hard a" character to the word. If every letter is capital, append 'Ā'. Otherwise append 'ā' e.g. etchstr --> etchstrā, "ATC" --> "ATCĀ"

   • If your language is unable to output 'ā' and 'Ā', you may use "ay" and "AY" respectively.

6. If the word is "A" or "a", ignore previous instructions. Transform the word to "Anā" or "anā", respectively. (because in Pig Latin, everything begins with a vowel, so we use the article "an" instead of "a")

Test Cases: (I think these are right)

• "I want to be a cat." --> "IĀ antwā otā ebā anā atcā"

• "That's a really nice... ass-car?" --> "Atsthā anā eallyrā icenā... assā-arcā?"

• "[CR][NL]'ssssssssssssssssssTRUExxxxxxxxIAMSOCOOL" --> "[CRĀ][NLĀ]UExxxxxxxxIAMSOCOOLssssssssssssssssssTRā"

• "THIS CHALLENGE IS PROBABLY A DUPE" --> "ISTHĀ ALLENGECHĀ ISĀ OBABLYPRĀ Anā UPEDĀ"

• "I SAT ON an APPLE" --> "IĀ ATSĀ ONĀ anā APPLEĀ"

Answer 19

Maximum of Two Roman Numerals

You should write a program or function which returns the maximum of two Roman numerals.

Input

• Two positive integers between 1 and 3999 (inclusive) with their Roman numeral representation string.
• The two strings can be separated by a space or inputted in the standard list representation of your language.
• 4, 9, 40, ... are written as IV, IX, XL, ...
• Trailing newline is optional.

Output

• The larger Roman numeral as string.
• Trailing newline is optional.
• If the two inputs are equal you should still only return one of them.

Examples

Format is input => output (explanation)

XXIX DI => DI (29 < 501)
V X => X    

TODO more

Built-in functions involving Roman numerals are prohibited.

This is code golf so the shortest entry wins.

Answer 20

Entropy Golf

This is a scoring system without a challenge.

My idea is to score entries based on the total Shannon entropy contained within them. This provides an incentive to both use fewer unique characters and to have a shorter program overall.

Given a string of characters, the score is calculated as follows, where C(x) is the number of occurrences of the given letter. To help provide a correction for multi-file programs or languages in which the program length encodes information, the EOF character at the end of every file is to be counted for the purposes of this scoring mechanism. Lowest score wins.

$$\mathrm{score} = -\sum_x{C(x)\log_2\frac {C(x)}{\mathrm{Length}}}$$

Anybody who knows better notation/MathJax is free to edit.

Answer 21

Wargame Tank Simulation

Some of you may have heard of the Wargame series of computer based real time strategy game. These games pit teams of players with primarily cold war era units to see how a hot cold war would have played out. The goal of this challenge is to simulate a tank battle in these games.

Input

• Two "tanks" (one red and one blue) will be entered into your program or function. Each tank is classified by a rate of fire, accuracy, armor value, and attack power value.

Challenge

From the inputs above, simulate the two tanks fighting. You will do this by having each tank fire according to its rate of fire. If it hits (randomly determined by accuracy), a tank will do damage according to the armor value of its target and its own attack power. The formula for damage is floor[(attackpower - armor)/2]. Therefore a tank with 10 attack power against a tank with 5 armor would do 2 damage.

Tank crews also have morale, which follows the following rule

• There are four possible morale values; calm, worried, scared, and panicked. Tanks always start calm. These names do not need to be in your code, in the sample below I've used calm = 1, worried = 2, etc.
• Each morale value reduces the accuracy as follows: Calm -> 100% (no change), worried -> 75%, scared -> 50%, panicked -> 25%. Therefore a panicked tank which normally has 60% accuracy now has 0.25 * 0.6 = 15% accuracy
• Each hit by the opposing tank degrades morale by one level, each miss upgrades the morale by one level.

For example:

morale: calm  |  worried  |  calm  |  worried  |  scared
hit:         hit         miss     hit         hit

Rules:

• Input should be two parameters to repesent each tank (I've used two tuples in the example below). Inputs may be provided in any order, just be sure to state which one is which. Input may be provided by user input via STDIN, read from a file, or parameters passed to a function call.
• Each tank starts with 10 health.
• Rate of fire will either be 8.5, 7.5, 6.5, 6, or 5 seconds between shots.
• Tanks start loaded, so each fires at time = 0. Because Communists are sneaky, red fires first.
• Accuracy must be randomly rolled.
• Ineffective hits (hits which do no damage) have an effect on morale! (because it probably sounds terrifying)
• Naturally since we want to see the action, output will be an update after each shot. The update will contain the time of the shot, whom it was made by (red or blue), health of both tanks, and the morale of both tank crews. Output maybe be presented in any format so long as it contains all of the required information in a human readable fashion (items must be delimited in some way). Similar to input, please describe your output format in the answer.
• Engagements are limited to 100 seconds. If you play the game you know this is because a plane has swooped in by then. For our purposes if both tanks are alive at this point, it is a draw.
• After one tank reaches 0 health (or after 100 seconds), print which tank is victorious ("Red" or "Blue") or "Draw" if appropriate. I don't care about trailing whitespace or newlines.
• Printint output may be printing to STDOUT or writing to a file
• Shortest answer in bytes wins

Sample Python Implementation

import random, math

def Shot_Result(acc, morale, power, armor):
    Morale = {1: 1., 2: 0.75, 3: 0.5, 4: 0.25}
    actual_acc = acc * Morale[morale]
    roll = random.random()
    if roll < actual_acc:
        dmg = max(0,math.floor((power-armor)/2))
    else:
        dmg = -1
        
    return dmg
    
    
def main(Red, Blue):
    red_rate, red_acc, red_armor, red_pow = Red
    blue_rate, blue_acc, blue_armor, blue_pow = Blue
    
    red_health = blue_health = 10
    red_morale = blue_morale = 1
    
    red_shots = [("Red", shot/100.) for shot in range(0,10000,int(red_rate*100))]
    blue_shots = [("Blue", shot/100.) for shot in range(0,10000,int(blue_rate*100))]
    
    Shots = sorted(red_shots + blue_shots, key=lambda x: x[1])
    
    print "{:^6}|{:^6}|{:^12}|{:^12}|{:^12}|{:^12}|".format("Shot","Time","Red Health","Blue Health","Red Morale","Blue Morale")
    
    for shot in Shots:
        if shot[0] == "Red":
            dmg = Shot_Result(red_acc, red_morale, red_pow, blue_armor)
            if dmg >= 0:
                blue_health -= dmg
                blue_morale = min(blue_morale+1,4)
            else:
                blue_morale = max(blue_morale-1,1)
        else:
            dmg = Shot_Result(blue_acc, blue_morale, blue_pow, red_armor)
            if dmg >= 0:
                red_health -= dmg
                red_morale = min(red_morale+1,4)
            else:
                red_morale = max(red_morale-1,1)
                
        print "{:^6}|{:^6}|{:^12}|{:^12}|{:^12}|{:^12}|".format(shot[0], shot[1], red_health, blue_health, red_morale, blue_morale)
        
        if red_health <= 0:
            print "Blue tank is victorious!"
            break
        if blue_health <= 0:
            print "Red tank is victorious!"
            break
    else:        
        print "It's a draw!"

Sample Output (Yours does not need to be this fancy)

 Shot | Time | Red Health |Blue Health | Red Morale |Blue Morale |
 Red  | 0.0  |     10     |    5.0     |     1      |     2      |
 Blue | 0.0  |     10     |    5.0     |     1      |     2      |
 Blue | 6.5  |     10     |    5.0     |     1      |     2      |
 Red  | 8.5  |     10     |    5.0     |     1      |     1      |
 Blue | 13.0 |    5.0     |    5.0     |     2      |     1      |
 Red  | 17.0 |    5.0     |    5.0     |     2      |     1      |
 Blue | 19.5 |    5.0     |    5.0     |     1      |     1      |
 Red  | 25.5 |    5.0     |    5.0     |     1      |     1      |
 Blue | 26.0 |    0.0     |    5.0     |     2      |     1      |
Blue tank is victorious!

Answer 22

Diagonals of an Array

code-golf array-manipulation

The k-th diagonal of a two-dimensional array is a list of all elements in positions (a,a+k). Your task is to output all of the diagonals.

For example, the diagonals of

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

are:

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

Which can be visualized thusly:

k -2-1 0 1 2 3
    \ \ \ \ \ \
     \ \ 3 1 4 1
      \ \ \ \ \
       \ 5 9 2 6
        \ \ \ \
         5 3 5 8

Input

A rectangular nested array or 2D array of positive integers, which will be nonempty.

Output

Its diagonals in any consistent order.

Test cases

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

[[42]]
[[42]]

[[57,72,15,66,49,01,53,28,60,60,65,12,09,00,82]]
[[57],[72],[15],[66],[49],[1],[53],[28],[60],[60],[65],[12],[9],[0],[82]]

[[57],[72],[15],[66],[49],[1],[53],[28],[60],[60],[65],[12],[9],[0],[82]]
[[57],[72],[15],[66],[49],[1],[53],[28],[60],[60],[65],[12],[9],[0],[82]]

---

Maybe a second question about n-dimensional arrays?

Answer 23

Help! Everything is in Wingdings!

code-golfimage-processing

Your task is to write a program or function that converts wingdings to a readable font. The input to the program will be the path to a png file with between 1 and 10 wingdings characters. Your output should be the message contained in the wingdings characters.

Specifications

Each test case will be a screenshot of the message as rendered in Microsoft Word (Black text on a white background, size 36, and 100% zoom). The image will be cropped to the bounding box of the message.

[insert 20 test cases, 2 of each size between 1 and 10]

[insert link to test cases + reference images]

Scoring:

(% of characters right in test cases)*10 - code length

(Highest score wins)

Rules

• Standard loopholes apply.
• No catering to the test cases.

(Note that this is just a concept for a challenge. I will expand the challenge if this receives a positive response).

Answer 24

Find point on the Hilbert curve

The Hilbert curve space filling curve. It is a limit of recursive approximations. Being spacefilling means there is a parametrization of the curve which is continuous. So we can map the interval [0,1] continuously to the unit square [0,1]x[0,1]. Let us call this map h. (Note that the image of the [0,1] is not the complete [0,1]x[0,1] but rather a dense subset. E.g. (.5,.1) is obviously not in the Hilbert curve, as it is not in any of the approximations.)

Your task is now to write a progarm that given a value in [0,1] to return the corresponding value unit square [0,1]x[0,1], where h(0)=(0,0) and h(1)=(1,0), and h(.5) = (.5, .5)

Meta

• This could also be done backwards.
• Test cases to be added.

Answer 25

KOTH: Black Hole

I've recently seen this video (by Tom Scott), in which it featured a game called Black Hole. Let's play that for KOTH!

Overview (the original version in the video)

• Two "players" have 10 counters, each labelled 1 to 10.
• These two players take it in turns to place counters in increasing order on a grid of 21 "spaces" arranged in a triangle (i.e. a triangle with 6 rows).
• Once all 21 counters have been placed, the remaining space that hasn't been used is the "black hole", and the dots surrounding the black hole are "sucked in".
• The person with the lowest sum of the counters "sucked in" wins.

For the purpose of KOTH, the triangular grid will consist of 120 spaces (i.e. the triangle "pyramid" will be 15 rows high), and each player will have 59 counters (Yes, that means that there will be 2 black holes).

Point System

• Win: 10 points, Draw (very rare): 3 points, Loss: no points

Instructions

• The bot must output a number between 1 and 120 each turn, and a "counter" with the same number as the current no. turn made by the bot will be placed there.
• After 118 turns, the black holes activate, the score is counted, and points are awarded.

NOTE: If there is no output within 5 seconds, the bot immediately loses.

"Battle" System

• The competition will be a round-robin, except each bot battles every other bot 5 times.
• The top three bots will then play each other 10 times each.
• The final winner is the winner of the competition.

Info on controller stuff

The controller will be in Python, but I don't have the first clue how to make an controller. Any help?

Answer 26

Generate a waveform from audio audio graphical-output code-golf

Given an audio file, in any common audio format (such as MP3, OGG, WMA, M4A, or WAV) of your choice, as input, output an image, in any common image format (such as PNG, JPG, PPM, BMP, SVG, or GIF) of your choice, of a waveform representing the audio input.

Here is an example image, generated with Audacity from this audio:

For reference, here is what an amplitude 1 sine wave at 440 Hz looks like:

And this is what it sounds like (warning: it doesn't sound good).

Restrictions

• The background of the image must be white (#FFFFFF in HTML notation)
• The waveform may be any color that is sufficiently distinguishable from the background
• The input audio must be sampled at 44.1 kHz with 32-bit floats (in the inclusive range [-1, 1])
• For raster graphics:
  • Sample points must be plotted every 5 pixels
  • The height must be an odd number of pixels, no less than 101
• Because vector graphics can scale indefinitely, the above restrictions do not apply
• The horizontal line in the middle of the image represents 0 amplitude, and the top and bottom of the image represent 1 and -1 amplitude, respectively
• The vertical scale must be linear, not logarithmic (the amplitude of the wave, not the relative loudness)
• The color of the wave, height of the image, input format, and output format must be the same every time your submission is run (for example, you cannot output as a PNG for one input, and a JPG for another)
• For the sake of testing/verification, submissions must run in under 1 minute on my machine (Core i3-3240 quad core, 3.4 GHz, 8 GB RAM) for any input.

Answer 27

code-golf

The free monoid on two letters 'x' and 'y' is the set of all finite strings you can make up from them, including the empty string, with their concatenation a binary operation. So the elements of this free monoid look like this: "", "x", "y", "xy", "yx", "xx", "yy" and so on. Strings like "xxxx" are often written as powers and we don't generally use the quotes: x^4.

This challenge is about a certain binary relation on this free monoid. Suppose we decide to treat x^2 abd y^2 as "the same". Which other strings (or "words", as they're called) will have to become "the same" (or congruent under the relation x^2 = y^2) as a result? In xxy, we can substitute yy for xx, which means that xxy is congruent to yyy. But then, the last yy in that string can be turned into xx as well, so yxx is congruent to the previous ones as well. A nice thing about this relation is that any congruent words will have to have the same length, so the number of words congruent to a given one is always finite. (To read up on this, you can look up things like "string rewriting systems", "transitive closure", "congruence relation".)

Take a string as input. The string is assumed to be of any length (including the empty string) and to contain at most two different characters (chosen by the user from the printable ASCII set or equivalent), say x and y. The program will interpret the string as a word in the free monoid on x and y and output all the other words of that monoid, also as strings, using the characters chosen by the user, congruent to the input word under the relation x^2 = y^2, in any order. Every congruent word must occur exactly once, including the input.

The words in the output have to be consistently separated by any non-empty string of printable characters not chosen by the user. If the input word contains less than two distinct characters, your program will assume the missing one(s) according to your choice, but that must not overlap with the separator. How exactly you want to take the input and output the words is up to you, but it must be possible to enter any valid string as input.

This has to be a complete program, not a function. No loopholes please.

Examples of input and output:

in: empty string
out: empty string

in: xx
out: xx yy

in: xy
out: xy

in: xyx
out: xyx

in: xyy
out: xyy xxx yyx

in: xxxx
out: xxxx yyxx yyyy yxxy xyyx xxyy

in: xyyxy
out: xyyxy xxxxy yyxxy yyyyy xxyyy xxyxx yyyxx yxxxx yxyyx yxxyy

(Note that the whitespace is a valid input character -- your program must choose a different separator if the user chooses to use it as a letter.)

Don't worry about things like the maximal length of the input or the output. The logic of your program has to work for all input word lengths, but the program only needs to work for reasonably long inputs.

Please give a short explanation of why your program works.

Answer 28

Determine whether one graph is a subgraph of the other

mathgraph-theorydiscrete-math

Given two unlabelled graphs as adjecency matrices with the same number of vertices, the goal is determining whether the first graph is a subgraph of the second one.

Definitions

A graph G=(V,E) comprises a set of vertices V={1,2,3,...,n} and a set of edges E ⊆ V x V = {(u,v) | u,v ∈ V}. The adjecency matrix A={a(i,j)}of a graph G is defined entry wise:a(i,j) = 1 if (i,j) ∈ E, 0 otherwise.

A graph H=(W,F) with adjecency matrix B={b(i,j)} is a subgraph of G iff all following statements hold:

• V=W
• There is a permutation p:V→W=V such that b(p(i),p(j)) ≤ a(i,j) for all i,j ∈ V=W

Examples

First the trivial ones:

• Obviously, every graph is a subgraph of itself.
• If H has more edges than G then it cannot be a subgraph.
• If you remove edges from a valid subgraph, the result will again be a subgraph.
• If every of the n nodes in G has edges to every other node, then every graph H with n nodes is a subgraph.

6 vertices, isomorphic (one big cycle) (remove some ones from Graph 1 in order to generate more valid subgraphs)

Permutation: [5 6 4 1 3 2]
Graph 1:     [0 1 0 0 0 0;0 0 1 0 0 0;0 0 0 1 0 0;0 0 0 0 1 0;0 0 0 0 0 1;1 0 0 0 0 0]
Graph 2:     [0 0 1 0 0 0;0 0 0 0 1 0;0 1 0 0 0 0;1 0 0 0 0 0;0 0 0 0 0 1;0 0 0 1 0 0]

Visualization of the above example by @KennyLau:

10 vertices, same number of edges, non isomorphic (g1 has minimal cycles of length 3,4,5, g2 has minimal cycles of length 3,4,4)

Graph 1:    [0 1 0 1 0 0 0 0 0 0;0 0 1 0 0 0 0 0 0 0;1 0 0 0 0 0 0 0 0 0;0 0 0 0 1 0 0 0 0 0;0 0 0 0 0 1 1 0 0 0;1 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 1 0 0;0 0 0 0 0 0 0 0 1 0;0 0 0 0 0 0 0 0 0 1;0 0 0 0 1 0 0 0 0 0]
Graph 2:    [0 0 0 0 0 0 0 1 0 1;0 0 0 0 0 0 1 0 0 0;0 0 0 0 0 1 0 0 0 0;1 0 0 0 0 0 0 0 0 0;0 1 0 1 0 0 0 0 0 0;1 0 0 0 0 0 0 0 0 0;0 0 0 0 1 0 0 0 0 0;0 0 1 0 0 0 0 0 0 0;0 0 0 0 0 1 0 0 0 0;0 0 0 0 1 0 0 0 0 0]

Answer 29

Nested brackets in source code

code-golf source-layout quine balanced-string

---

Introduction

This challenge is somewhat unusual. Basically, your inputs are a correctly matched string of brackets S and a number n ≥ 0, and your output is the number of matched pairs at nesting level n in S. The outermost pairs are at level 0, those inside them are at level 1, and so on. The twist is that the string S is part of your source code, and incorrectly matched strings must result in compilation or runtime errors.

The task

Your task is to write four strings, A, B, L, and R, that satisfy the following conditions.

• The strings L and R are non-empty and distinct. They represent a left and right bracket.
• If S is a concatenation of Ls and Rs that is correctly matched, then the concatenation ASB is a valid program (full runnable program or function definition) is your programming language of choice. It takes an integer n ≥ 0 and outputs the number of L-R pairs in S at nesting level n.
• If S is a concatenation of Ls and Rs that is not correctly matched, then ASB either fails to compile, or throws an error on every possible input.

Example

Suppose that the strings A, B, L, and R are BEGIN;, END;, DO(i++; and );, respectively, in an imaginary programming language. Then the string DO(i++;);DO(i++;DO(i++;);); is a correctly matched concatenation of Ls and Rs. On input 0, the program

BEGIN;DO(i++;);DO(i++;DO(i++;););END;

should output 2, because there are two matched pairs at level 0. However, the program

BEGIN;DO(i++;DO(i++;);END;

should result in an error, because the brackets are not correctly matched.

More examples

Here is a table of some programs, inputs and expected outputs.

Program          Input  Output
------------------------------
AB               <any>  0
ALRB             0      1
ALRB             1      0
ALLRRB           1      1
ALRLRB           0      2
ALRLLRRB         0      2
ALRLLRRB         1      1
ALLRLLLRRRLRRLRB 0      2
ALLRLLLRRRLRRLRB 1      3
ALLRLLLRRRLRRLRB 2      1
ALLRLLLRRRLRRLRB 3      1
ALLRLLLRRRLRRLRB 4      0
ARB              <any>  error
ALB              <any>  error
ARLB             <any>  error
ALLRB            <any>  error
ALLRRRLRB        <any>  error
ALLRRLLRB        <any>  error
ALLRRRLLLRRB     <any>  error

Rules and scoring

Your score is the sum of the lengths of the four strings, lower score being better. You must identify the strings in your answer. You are not allowed to read your source code directly or indirectly. Standard loopholes are also disallowed.

---

Sandbox notes

• Is the task of counting pairs on a nesting level too easy? I don't want it to be trivial, but not so hard either that it shadows the source layout aspect. A slightly more difficult variant would be to count the number of peaks (substrings LR) at nesting level n.
• Is the restriction of erroring on mismatched brackets interesting? I could also require the program to always return -1 in this case, or something similar.

Answer 30

Three Indistinguishable Dice

code-golf

Given three dice rolls (integer values from 1-6) in sorted order (so as to be indistinguishable), write a program that converts them to the sum of two dice with an identical distribution.

Inspired by standupmath's The Three Indistinguishable Dice Puzzle. A follow-up "solution" video was also posted, but arguing about "elegance" of one way or another is a bit subjective. Counting characters isn't. :D

Details

• Score is the length of the program in characters
• The program can be a function that's called somehow, or executable script that reads from stdin, or whatever's convienent.
• No "rerolling" by getting entropy from another source

Example Test Code

Rather than doing any sort of probabilistic testing, it's easy enough to rip through the 216 (6³) cases of all the three dice and assert that your function returns each value as many times as it should. It will be called with identical parameters (e.g. the cases 1, 2, 3 and 3, 2, 1, ... are presumed indistinguishable and are (arbitrarily) converted to 1, 2, 3).

The below is in Python, written hopefully generically enough to be clear to port. If your language of choice uses stdin/stdout, it would be a bit different. The testing code is just for testing and not scored (though if you want to provide it for other users of your language or I/O method, that might be useful).

from thing import f

# this is the fair distribution of the sum of two dice, 
# multiplied by 6 (because each should be hit 6x more)
dist = {
    2: 6,   12: 6,
    3: 12,  11: 12,
    4: 18,  10: 18,
    5: 24,   9: 24,
    6: 30,   8: 30,
    7: 36,
}

d = [1, 2, 3, 4, 5, 6]
for i in d:
    for j in d:
        for k in d:
            ijk = sorted([i, j, k])
            result = f(ijk)
            dist[result] -= 1

for key in dist:
    assert dist[key] == 0