459
\$\begingroup\$

What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, 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. 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, replace the post here with a link to the challenge and delete it.

See the Sandbox FAQ for more information on how to use the Sandbox.

The Sandbox works best if you sort posts by "active".

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43
  • \$\begingroup\$ I think the sentence 'replace the post here with a link to the challenge and delete it' may specify that the deletion should be done immediately . \$\endgroup\$ – AZTECCO Oct 5 at 19:39

2565 Answers 2565

2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ So the example is an invalid input? \$\endgroup\$ – feersum Nov 17 '15 at 10:20
  • \$\begingroup\$ @feersum It's valid, but in trying to clarify the redundancy condition, I realized it's unclear what ( quick)( brown)( quick brown) should give. Hmm. \$\endgroup\$ – xnor Nov 17 '15 at 10:23
  • \$\begingroup\$ "You may not use regular expressions." T_T \$\endgroup\$ – Martin Ender Nov 17 '15 at 11:20
  • \$\begingroup\$ @MartinBüttner Would it make you happier if I made reg-exp and non-reg-exp two separate "leagues"? \$\endgroup\$ – xnor Nov 17 '15 at 11:21
  • \$\begingroup\$ Hm, I don't know. I wonder if it's a bit of a duplicate of this. If I was allowed to use a regex approach, my answer would be almost the same (instead of repeatedly moving the contents of the parentheses to a new line, I'd duplicate the line and remove the parentheses from one of the copies, and the parentheses together with their contents from the other; followed by duplicate removal). \$\endgroup\$ – Martin Ender Nov 17 '15 at 11:24
  • \$\begingroup\$ (Also note that even Retina can't beat a non-regex approach in Pyth on that challenge, so I doubt it'll be much different here.) \$\endgroup\$ – Martin Ender Nov 17 '15 at 11:25
2
\$\begingroup\$

Find runs of triple multiples of squares

Your task is simple: For a given input N, find all runs of three or more consecutive integers less than N which are all perfect squares or multiples of perfect squares (of numbers greater than 1, obviously). You should then list each triplet (or greater) on a single line, indicating the square and the factor that divides it, e.g. 48 = 2² * 12. If a number is a product of two (or more) perfect squares, you may write it in either of two ways, e.g. 100 = 2² * 5² or 100 = 10². If your language doesn't support the ² character, you may use ^2 instead. For example, for an N of 1000, your code should produce the following:

48 = 2² * 12, 49 = 7², 50 = 5² * 2
98 = 7² * 2, 99 = 3² * 11, 100 = 10²
124 = 2² * 31, 125 = 5² * 5, 126 = 3² * 14
242 = 11² * 2, 243 = 9² * 3, 244 = 2² * 61, 245 = 7² * 5
342 = 3² * 38, 343 = 7² * 7, 344 = 2² * 86
350 = 5² * 14, 351 = 3² * 39, 352 = 4² * 22
423 = 3² * 47, 424 = 2² * 106, 425 = 5² * 17
475 = 5² * 19, 476 = 2² * 119, 477 = 3² * 53
548 = 2² * 137, 549 = 3² * 61, 550 = 5² * 22
603 = 3² * 67, 604 = 2² * 151, 605 = 11² * 5
724 = 2² * 181, 725 = 5² * 29, 726 = 11² * 6
774 = 3² * 86, 775 = 5² * 31, 776 = 2² * 194
844 = 2² * 211, 845 = 13² * 5, 846 = 3² * 94, 847 = 11² * 7, 848 = 4² * 53

or

48 = 2² * 12, 49 = 7², 50 = 5² * 2
98 = 7² * 2, 99 = 3² * 11, 100 = 2² * 5²
124 = 2² * 31, 125 = 5² * 5, 126 = 3² * 14
242 = 11² * 2, 243 = 3² * 3² * 3, 244 = 2² * 61, 245 = 7² * 5
342 = 3² * 38, 343 = 7² * 7, 344 = 2² * 86
350 = 5² * 14, 351 = 3² * 39, 352 = 2² * 2² * 22
423 = 3² * 47, 424 = 2² * 106, 425 = 5² * 17
475 = 5² * 19, 476 = 2² * 119, 477 = 3² * 53
548 = 2² * 137, 549 = 3² * 61, 550 = 5² * 22
603 = 3² * 67, 604 = 2² * 151, 605 = 11² * 5
724 = 2² * 181, 725 = 5² * 29, 726 = 11² * 6
774 = 3² * 86, 775 = 5² * 31, 776 = 2² * 194
844 = 2² * 211, 845 = 13² * 5, 846 = 3² * 94, 847 = 11² * 7, 848 = 2² * 2² * 53

The input may be supplied via command line, user input, read from a file, or any other means you see fit (though it should not be hardcoded). This is code golf, so shortest code wins. Usual loopholes apply.

Note that these numbers are sometimes called "non-squarefree" numbers, which are listed at A013929. (This lists all non-squarefree numbers, not just consecutive ones, so it may be useful as a reference, but is not a direct source.)

Side note: The 242-245 and 844-848 runs are the only sets of more than 3 below 1000. It's possible that they become more common at higher numbers, but so far, graphing the sets I know about produces a pretty steady line, with no noticeable curve towards greater or reduced frequency. It would be interesting to see a mathematical proof on whether there are or are not an infinite number of these sets...

\$\endgroup\$
  • \$\begingroup\$ 1. What is the relevance of N? It seems to be taken as input and then not used. 2. You're missing an important qualification. All integers are multiples of the perfect square 1². 3. This question would benefit from a link to OEIS A013929 \$\endgroup\$ – Peter Taylor Nov 15 '15 at 16:16
  • \$\begingroup\$ Sorry, missed that. It's just a cap so your program doesn't run forever. Oh, and obviously 1² would be disqualified, I can make some clarifications. \$\endgroup\$ – Darrel Hoffman Nov 15 '15 at 16:35
  • \$\begingroup\$ @MartinBüttner: I already accounted for that. Non-Unicode languages can use ^2. It's an extra byte, though, so might be more golf-friendly to use ². \$\endgroup\$ – Darrel Hoffman Nov 15 '15 at 17:41
  • \$\begingroup\$ @DarrelHoffman Sorry, must have overlooked that. I suppose for interpreters which expect the source code to be UTF-8, it would be two bytes either way. \$\endgroup\$ – Martin Ender Nov 15 '15 at 21:16
  • \$\begingroup\$ Re the side note, see comments on A045882. \$\endgroup\$ – Peter Taylor Nov 23 '15 at 21:53
  • \$\begingroup\$ @PeterTaylor - Well alright then. Looks like you have to get into some pretty high numbers to see longer runs. Though it still doesn't answer the question as to whether they become more or less frequent the higher you go. I was surprised, for example, to discover there were fewer triplets between 500-1000 than between 0-500. This might be a bit off-topic for PPCG though. Maybe should start a thread in Mathematics? \$\endgroup\$ – Darrel Hoffman Nov 23 '15 at 22:03
2
\$\begingroup\$

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: DownloadSave-As

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

#2 - ASCII - Pre-Flight Launch Preparation for the Space Shuttle: DownloadSave-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: DownloadSave-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: DownloadSave-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: DownloadRAW->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: DownloadRAW->Save-As (lic. GPL, Rusty Russell)

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

#2 - QBASIC - COMBAT ARENA (Game): DownloadRAW->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): DownloadRAW->Save-As (lic. MIT)

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

#5 - JavaScript - jQuery 1.11.3: DownloadRAW->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


\$\endgroup\$
  • \$\begingroup\$ I love this, even if it's above my skill level. I hope it gets posted! \$\endgroup\$ – cat Dec 18 '15 at 3:18
  • \$\begingroup\$ 1. "The file names listed above are binding" for what? My best guess is that the compressor has to store the original filename in the file, and the decompressor has to output to that name, but I didn't notice that that was stated explicitly anywhere. 2. comp articles.law: are we required to use command-line arguments and to pick an output filename ourselves, or could we use stdio and invoke as comp <articles.law >articles.law.myz? 3. "Your answer must include ... A standard ZIP file". How? \$\endgroup\$ – Peter Taylor Dec 18 '15 at 8:38
  • \$\begingroup\$ @PeterTaylor 1. It is irrelevant how the file name is stored, however it must be restored after decompression. I'll add that. 2. The compressed filename is not specified in the rules so it can be anything. According to the current rules comp <articles.law >articles.law.myz would be invalid. The only calid way to call one step is program file, files must be created by the step program. I'll add that. 3. I'm thinking of changing this part to "GitHub Repository". Suggestions? \$\endgroup\$ – mınxomaτ Dec 18 '15 at 16:12
  • \$\begingroup\$ I would posit that there is no such thing as truly "General-Purpose Compression", at least in an information-theory sense. Text (and various other formats) compress nicely because they are not general. But compression of random data will not give any gain in the long run. \$\endgroup\$ – Digital Trauma Dec 18 '15 at 20:47
  • \$\begingroup\$ @DigitalTrauma GP in terms of compression algorithm means that the algorithm does not specifically target the specific files in a test suite. ZIP for example is a GP algorithm, as most other algorithms. \$\endgroup\$ – mınxomaτ Dec 18 '15 at 20:53
  • \$\begingroup\$ Rather than using GitHub repos, I think the best approach is to require all answers to be deterministic and then the scores can be verified by just running them. \$\endgroup\$ – Peter Taylor Dec 19 '15 at 12:26
2
\$\begingroup\$

Clean numbers

We call a positive integer a clean number if it is expressible by using only a positive digit once or more and no other sign. For example 88 is expressible with 2's as 2222.

A more complex example is

$$141289730531295606313143345858933 = 3^{33}3^{3^3}3333$$

Details

The possible operations are

  • exponentiation
  • multiplication (only if the first part contains exponentiation as otherwise it is just digit concatenation)
  • digit concatenation

Precedence is as normal. Power towers are computed from right to left (top to bottom).

Task

sandbox note: which one should it be? I'm thinking d) now

  • a) given a number return if it is clean
  • b) given a number return the digit with which it is clean
  • c) given a number and a digit return if the number is clean with that digit
  • d) given a number and a digit return digit-clean numbers up to the given number
  • e) given a number find the smallest digit or digit-sequence which makes it clean (eg. 63504 = 2522)

Test cases

TODO
(11^1)*11
2^(2^2*22)

Your program should solve every test case in a couple of minutes.

This is code golf.

\$\endgroup\$
  • 1
    \$\begingroup\$ Unfortunately, this site doesn't have latex support. It should though. \$\endgroup\$ – SuperJedi224 Jan 2 '16 at 14:55
  • \$\begingroup\$ @SuperJedi224 I know and I will add image for the final version. I'm just lazy to do it already. \$\endgroup\$ – randomra Jan 2 '16 at 15:00
  • \$\begingroup\$ Unfortunately, Meta does have LaTeX support. You just have to double up on the dollar signs. \$\endgroup\$ – Dennis Jan 2 '16 at 16:06
  • \$\begingroup\$ Not anymore... i guess \$\endgroup\$ – ev3commander Jan 3 '16 at 17:47
  • \$\begingroup\$ If combinations are allowed, then 2016=C(2^C(2^2,2),2) ;) \$\endgroup\$ – ev3commander Jan 3 '16 at 17:49
  • \$\begingroup\$ @BlockCoder1392 seeing that in the chat gave the idea for the challenge \$\endgroup\$ – randomra Jan 3 '16 at 18:05
  • \$\begingroup\$ Yes, I know. I was just suggesting combinations (which probably wouldn't be accepted anyways) \$\endgroup\$ – ev3commander Jan 3 '16 at 18:21
2
\$\begingroup\$

Add two numbers (or Arithmetic on continued fraction expansions)

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 *?

\$\endgroup\$
  • \$\begingroup\$ It's not very complicated, and handling the four functions isn't much harder than handling just one; but if you assume that the input is two finite lists then it's possible to do a boring approach of evaluating them as reduced rationals, doing the operation, and converting back. IMO it would be more interesting to restrict to languages which support either functions with state or infinite lazy lists and to include some test cases which work with "nice" irrationals like sqrt 2 and e evaluated to a given number of terms. \$\endgroup\$ – Peter Taylor Jan 2 '16 at 17:33
  • \$\begingroup\$ Would that be equivalent to letting the program take two lists of sufficient* length and a number n, and requiring it to return the first n terms? *sufficiently long such that the first n terms can correctly be evaluated. \$\endgroup\$ – flawr Jan 2 '16 at 19:01
  • \$\begingroup\$ I don't see how that would avoid the approach of converting to rationals, performing the operation, and converting back. \$\endgroup\$ – Peter Taylor Jan 2 '16 at 19:50
  • \$\begingroup\$ I am just trying to understand what you meant in the first comment=) You obviously can only output a finite number of terms, but this also implies that you only need a finitely many input terms. So I do not see why you would have to use 'infitine' lists as input, if you can only output finite lists. And for not excluding too many languages, my suggestion was passing another argument n that determines how many terms the output should consist of. \$\endgroup\$ – flawr Jan 2 '16 at 21:57
  • 1
    \$\begingroup\$ It's the difference between "You only need these a terms" and "You need a terms, but it's up to you to work out what a is". Working out how many terms you need is the interesting part; converting between a finite continued fraction and a rational expressed as numerator and denominator is comparatively boring. \$\endgroup\$ – Peter Taylor Jan 2 '16 at 23:21
  • \$\begingroup\$ Now I see what you mean, thank you for elaborating! I like your suggestion, I'm going to try to come up with some suitable test cases. \$\endgroup\$ – flawr Jan 3 '16 at 13:50
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "Optimal" in what sense? And surely 0 needs one cell, to store the output? \$\endgroup\$ – Peter Taylor Jan 7 '16 at 19:25
  • \$\begingroup\$ I too think that this needs clarification. In the chat you said optimal representation = the shortest brainfuck program outputting this number. But I think there still might be some ambiguity, as the shortest might not be unique, and therefore might not have an unique number of used cells. \$\endgroup\$ – flawr Jan 7 '16 at 21:03
  • \$\begingroup\$ @flaws that is true. Minimal output length, minimizing the number of cells used. \$\endgroup\$ – Conor O'Brien Jan 7 '16 at 21:04
  • \$\begingroup\$ @PeterTaylor optimal as in shortest. Will add that at home. And I'm referring to the number of cells required to modify another cell. Perhaps I'm wrong in my reasoning. \$\endgroup\$ – Conor O'Brien Jan 7 '16 at 21:06
  • \$\begingroup\$ However you count the cells, 0 should surely return the same value as 4, because neither of them use <>. \$\endgroup\$ – Peter Taylor Jan 7 '16 at 21:41
  • \$\begingroup\$ I vote for "remove bonuses" \$\endgroup\$ – quintopia Jan 9 '16 at 6:37
  • \$\begingroup\$ @quintopia Agreed, in retrospect they are a bad idea. \$\endgroup\$ – Conor O'Brien Jan 9 '16 at 17:38
  • \$\begingroup\$ @ThomasKwa Indeed. \$\endgroup\$ – Conor O'Brien Jan 9 '16 at 17:38
  • \$\begingroup\$ @PeterTaylor That is true. \$\endgroup\$ – Conor O'Brien Jan 9 '16 at 17:39
  • 2
    \$\begingroup\$ I'm not sure what part of this challenge is "deceptively simple". ;) \$\endgroup\$ – Martin Ender Jan 10 '16 at 15:01
2
\$\begingroup\$

Let's play Ticket to Ride!

(Note, this challenge was inspired by the board game Ticket to Ride, but is massively simplified to a graph-searching problem).

For this challenge, you have a list of cities (nodes), connections (edges), and tickets ([City, City, Point] tuple). You also have a limited number of trains, where each connection takes exactly 1 train to fill. For each ticket you complete (there is a filled-in path between the two cities), you get the ticket's point value.

Your goal is to maximize the number of points you get. For example, given the following graph:

A-B-C-D

and two tickets [(A,B)=>1, (B,D)=>2], and 2 trains, then you should output (B,C), (C,D) as that gives you a total of 2 points, because you have created a path from B to D, which matches the second ticket.

Everybody will be working on the same large graph and set of tickets, so your score is the score of your solution. Your solution is a list of filled connections (not the code that generated them, although your code should be included).

\$\endgroup\$
  • \$\begingroup\$ This is very unclear. "tickets (point value to make a path between two cities)" sounds like you need to have that many points in order to create an edge, then you say "Your goal is to maximize the number of points you get"... but you don't describe how you get points. And then "you should output (B,C), (C,D) as that gives you a total of 2 points": how does (B,C), (C,D) give you points? \$\endgroup\$ – msh210 Jan 15 '16 at 18:17
  • \$\begingroup\$ @msh210 is that better? \$\endgroup\$ – Nathan Merrill Jan 15 '16 at 18:52
  • \$\begingroup\$ 1. To check I've understood: there's a sense in which what we have isn't a list of edges but a list of potential edges, and we have to choose n edges from those listed to create an actual graph on which reachability analysis will be performed? 2. Is there any reason to think that the answers won't all be optimal? \$\endgroup\$ – Peter Taylor Jan 15 '16 at 19:35
  • \$\begingroup\$ @PeterTaylor 1. correct. I'll make that clearer. 2. I believe that the optimal solution requires a massive big O, but I may be wrong. \$\endgroup\$ – Nathan Merrill Jan 15 '16 at 19:39
  • \$\begingroup\$ @NathanMerrill, yep! \$\endgroup\$ – msh210 Jan 15 '16 at 19:42
  • \$\begingroup\$ At the moment there's no runtime restriction preventing people from using an algorithm which considers every n-element subset of the edges. \$\endgroup\$ – Peter Taylor Jan 15 '16 at 19:44
  • \$\begingroup\$ @PeterTaylor When I post the challenge, I'm going to be including a single, large test case. A submission will simply be a list of connections, not the program that generated them (although the program would certainly be nice) \$\endgroup\$ – Nathan Merrill Jan 15 '16 at 19:48
  • 1
    \$\begingroup\$ If answers don't have to include code (or at least pseudo-code), the question is off-topic on this site. \$\endgroup\$ – Peter Taylor Jan 15 '16 at 20:00
  • \$\begingroup\$ What about this challenge: codegolf.stackexchange.com/questions/52496/… \$\endgroup\$ – Nathan Merrill Jan 15 '16 at 20:05
2
\$\begingroup\$

Roll a Die

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 , 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
\$\endgroup\$
  • 1
    \$\begingroup\$ Re "real standard dice". Both left-handed and right-handed dice exist (depending on culture), so it might be worth mentioning explicitly which of the two it is, instead of giving a single example. "You can earn a bonus for rolling several dice but in this case you must display the dice horizontally." You forgot to mention how much that bonus is worth but I would recommending leaving it out completely. \$\endgroup\$ – Martin Ender Jan 25 '16 at 14:47
  • 1
    \$\begingroup\$ It's also sort of implied that two numbers is also valid input (provided they can be on adjacent sides), but you never state how that input is to be handled. Likewise, what if the input has more than two numbers? I'd also prefer a fixed output format instead of letting people choose their own ASCII art. It's bound to derail into arguments of how much visual complexity is sufficient to display the die properly. \$\endgroup\$ – Martin Ender Jan 25 '16 at 14:49
  • \$\begingroup\$ @MartinBüttner Sorry I didn't know about Chinese dice, and the bad wording in some of my paragraphs; I hope this version is better. \$\endgroup\$ – Neil Jan 25 '16 at 17:37
  • 1
    \$\begingroup\$ The diagram of two dice isn't quite enough for me to visualise the all the cases, and the batch script isn't the easiest to read either because of the escaping. I think it would be an improvement to give an unfolded net, possibly a diagram showing all the possible pip positions, and if you want to have a full test suite then to rewrite it in JavaScript and make it a Stack Snippet. Since I've already gone to the effort of producing the first two diagrams to evaluate how helpful I find them, I'll edit them in as a footnote and leave you to decide whether and where you want to use them. \$\endgroup\$ – Peter Taylor Jan 25 '16 at 21:02
2
\$\begingroup\$

Polyphonic Pitch Detection

Tags:

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

440hz Sine Wave

(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:

554hz Sine 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:

440hz Sine Wave + 554hz Sine Wave

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

\$\endgroup\$
  • \$\begingroup\$ I think it is patented in some countries, but a quite successfull one is the yin algorithm. And you might want to add test-battery \$\endgroup\$ – flawr Jan 18 '16 at 13:27
  • \$\begingroup\$ @flawr Added. Although note that while the YIN algorithm is quite successful at finding the fundamental frequency, most of the test cases will contain multiple frequencies. \$\endgroup\$ – user81655 Jan 19 '16 at 0:01
  • \$\begingroup\$ Is that desmos I see? \$\endgroup\$ – Cyoce Jan 30 '16 at 7:46
  • \$\begingroup\$ @Cyoce Yep. ;-) \$\endgroup\$ – user81655 Jan 30 '16 at 10:38
2
\$\begingroup\$

Anything but stacks


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?

\$\endgroup\$
  • \$\begingroup\$ I think a lot of people will follow Pyth (fixed-arity prefix with iteration as a backup) or Jelly (tacit) if the goal is a golfing language. \$\endgroup\$ – lirtosiast Feb 1 '16 at 4:30
  • 4
    \$\begingroup\$ This is currently too broad by miles. \$\endgroup\$ – Peter Taylor Feb 1 '16 at 8:17
  • 1
    \$\begingroup\$ I definitely agree with Peter. "An alternative idea is to pick a single data structure and have everybody use it." That seems a like a much better idea, and then you need to make sure that that's the only type of memory that's allowed (maybe except for a finite amount, like a handful of registers). Even then, it definitely needs some sort of goal. Requiring TC-ness might also be a good idea depending on what kind of answers you're looking for. \$\endgroup\$ – Martin Ender Feb 1 '16 at 10:11
  • \$\begingroup\$ I think set-based languages would be the most interesting, since sets can't have an order, and most other data structures can implement stacks easily. There are also so many different directions to take with them. \$\endgroup\$ – Fricative Melon Feb 1 '16 at 16:47
  • \$\begingroup\$ Somewhere far down on my list of esolang ideas are two languages using stacked cups as a data structure (I'd like to implement a very minimalistic one that doesn't go far beyond the instructions in that challenge, and a feature-rich one, where you're actually programming two hands that can move cups). Anyway, I'd be willing to offer that idea as a data structure for your challenge. \$\endgroup\$ – Martin Ender Feb 1 '16 at 19:14
  • \$\begingroup\$ @user1657355 HPR is set-based, although the set can contain lists. \$\endgroup\$ – Zgarb Feb 1 '16 at 19:22
  • \$\begingroup\$ Regular expressions. Those are probably hard with a stack based language. Parsing expressions would be hard, I would think, as well. \$\endgroup\$ – Conor O'Brien Feb 1 '16 at 20:06
  • \$\begingroup\$ I was thinking of two deque based languages. \$\endgroup\$ – Akangka Feb 18 '16 at 12:06
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ One problem I see is dictionary compression should be really powerful here, but prohibitive for any languages that don't have a built-in dictionary (because including one would clearly exceed the byte limit). What about languages that do have built-in dictionaries though? (Jelly's string literals can be dictionary-compressed out of the box, and I think Mathematica can load a dictionary with a single function call, too.) \$\endgroup\$ – Martin Ender Feb 1 '16 at 13:35
  • \$\begingroup\$ @MartinBüttner I guess I personally am OK with languages with built-in dictionaries - it just seems like using the right tool for the job. But if that would be seen as unacceptably biasing the challenge toward a certain set of languages, I'm OK with putting something in to prohibit it. \$\endgroup\$ – Nathaniel Feb 1 '16 at 13:39
  • \$\begingroup\$ I just realised that the optimal solution might consist of a 1024-character string literal. For that reason I might add a requirement that the output be the same length as the original file. (But first I have to think about whether that's really likely to be a problem.) \$\endgroup\$ – Nathaniel Feb 1 '16 at 13:41
  • \$\begingroup\$ Does base conversion count as a "compression or decompression algorithm"? What about Huffman tree-related functions? \$\endgroup\$ – Peter Taylor Feb 1 '16 at 22:32
  • \$\begingroup\$ @PeterTaylor I think I would say both are OK - I'm mostly just trying to prevent solutions that don't do much other than bz2.decompress('[some long string]'). If you implemented your own decompression then we learn something from the answer, even if you did it using tools designed for that purpose. However, if you have an intuition that this would devolve into something uninteresting please let me know. \$\endgroup\$ – Nathaniel Feb 2 '16 at 4:57
  • \$\begingroup\$ @PeterTaylor I've added a restriction on the source character set as well, which should head off some of the most annoying consequences of those things. \$\endgroup\$ – Nathaniel Feb 2 '16 at 5:01
  • 1
    \$\begingroup\$ I asked about base conversion because it's one of the techniques most frequently used on this site for compression, and about Huffman because it seemed like a gray area which should be mentioned explicitly. On an unrelated note, would it not be a better measure to do the concatenation the other way round, so that the "compressed" Hamlet is training the LZMA bigraph dictionary for the real one? Otherwise the best score would probably be obtained by repeating some large chunk from near the end of the real one as many times as needed to meet the target length. \$\endgroup\$ – Peter Taylor Feb 2 '16 at 12:50
  • \$\begingroup\$ @PeterTaylor I've made that change. (I tested it on a few test files, including one composed of the last 5% of Hamlet repeated 20 times, and it didn't make much difference, but it changed the scores by 100 or so.) \$\endgroup\$ – Nathaniel Feb 2 '16 at 12:57
  • \$\begingroup\$ (One of the reasons that LZMA is good for this purpose is that it's close to being a "normal compression algorithm", which includes being close to invariant with respect to swapping the concatenated strings around.) \$\endgroup\$ – Nathaniel Feb 2 '16 at 13:07
  • \$\begingroup\$ I changed my mind about trying to keep the source printable. It's a nice thing to have but it means having rules that are too complex, and people will just try to loophole their way around them anyway. So that means base coding is just fine. \$\endgroup\$ – Nathaniel Feb 2 '16 at 13:23
2
\$\begingroup\$

Create an unkillable Windows process

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.
\$\endgroup\$
  • 5
    \$\begingroup\$ This is coming fairly close to a challenge asking for malicious software. \$\endgroup\$ – Martin Ender Feb 22 '16 at 9:49
  • \$\begingroup\$ @MartinBüttner It's not completely clear, but the discussion on that question seemed to indicate that a process in a zombie state could not actually execute any longer, making it useless for malware. \$\endgroup\$ – feersum Feb 22 '16 at 9:53
2
\$\begingroup\$

The greatest power...

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 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
\$\endgroup\$
  • \$\begingroup\$ Can anyone find a similar challenge we've already done? \$\endgroup\$ – Martin Ender Feb 26 '16 at 18:08
  • \$\begingroup\$ I thought up this exact challenge a few days ago, but didn't bother writing it out. Glad to see that someone else did :) \$\endgroup\$ – ETHproductions Feb 26 '16 at 18:13
  • \$\begingroup\$ Power Points? :P \$\endgroup\$ – FryAmTheEggman Feb 26 '16 at 18:35
  • \$\begingroup\$ Also I think I found it: codegolf.stackexchange.com/q/501/31625 although I would prefer to close that as a dupe of this one, I think. It has basically no spec... \$\endgroup\$ – FryAmTheEggman Feb 26 '16 at 18:37
  • \$\begingroup\$ @FryAmTheEggman Hmmm, that might editable without invalidating answers though. \$\endgroup\$ – Martin Ender Feb 26 '16 at 18:47
  • \$\begingroup\$ By the looks of it, some answers are already invalid, and a bunch give 0 for the values that, in yours, should give 1. Not sure what to do with that, I think it'd have to say that 1 or 0 was acceptable? \$\endgroup\$ – FryAmTheEggman Feb 26 '16 at 18:56
  • 1
    \$\begingroup\$ @FryAmTheEggman I think even by the little bit of spec that's there, returning 0 for anything is wrong. Let's see if froddy responds to my comment. Otherwise, I'll probably go ahead with this one. \$\endgroup\$ – Martin Ender Feb 26 '16 at 18:57
  • \$\begingroup\$ Rather than "greatest power" it's "greatest-order root". But of course that's not a catchy title :-) \$\endgroup\$ – Luis Mendo Feb 26 '16 at 19:23
  • \$\begingroup\$ @DonMuesli I think it would be the greatest root-order, because the greatest-order root should be m, right? \$\endgroup\$ – Martin Ender Feb 26 '16 at 20:48
  • \$\begingroup\$ @Martin Yes, you are right. I had understood the challenge the other way around. Very nice challenge BTW! (Meaning I think I have a 10-byte answer, hehehe) \$\endgroup\$ – Luis Mendo Feb 26 '16 at 21:34
  • \$\begingroup\$ Submit to a greater power? \$\endgroup\$ – Digital Trauma Feb 27 '16 at 2:16
  • \$\begingroup\$ There was a similar question about expressing your number n in all possible ways as n=a^b, but I'm not finding it now. \$\endgroup\$ – xnor Feb 27 '16 at 22:44
  • \$\begingroup\$ @xnor Hmmm, let me know when you do. \$\endgroup\$ – Martin Ender Feb 27 '16 at 23:01
  • \$\begingroup\$ @xnor There's codegolf.stackexchange.com/q/564/8478 also by froddy. \$\endgroup\$ – Martin Ender Feb 27 '16 at 23:02
  • \$\begingroup\$ @MartinBüttner Here is is: codegolf.stackexchange.com/q/58047/20260 \$\endgroup\$ – xnor Feb 27 '16 at 23:08
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ The asterisk seems to make italics sometimes instead of just being text. Can you help me with this? Why does it happen and how do I escape it? \$\endgroup\$ – ymar Mar 23 '15 at 4:12
  • 1
    \$\begingroup\$ Why it happens. The general solution is to escape with backslash. I think Martin's intention was that you mark up entire equations as code, not just the asterisk character. \$\endgroup\$ – Peter Taylor Mar 24 '15 at 10:24
  • \$\begingroup\$ Comments on the question itself: 1. It's not obvious that this is a graph theoretic question rather than an algebraic question until a long way into it. Ideally the title should make that clear. 2. The first two ring axioms are clearly misstated. But 3. listing them seems to be a waste of space. The real question (given a multiplication table, identify the zero divisor graph and its diameter and girth) can be stated quite clearly without them. 4. Both diameter and girth can be infinite. How should that be represented in output? \$\endgroup\$ – Peter Taylor Mar 24 '15 at 10:41
  • 1
    \$\begingroup\$ 5. A question shouldn't be popularity-contest unless there's no other reasonable way of scoring it. This would function perfectly well as code-golf, and with a minor change to allow arbitrary sizes of input could be a fastest-code. \$\endgroup\$ – Peter Taylor Mar 24 '15 at 10:42
  • \$\begingroup\$ @PeterTaylor I've made corrections. \$\endgroup\$ – ymar Mar 8 '16 at 14:18
  • \$\begingroup\$ Thanks. Looking back at this, I have two further comments: 6. It's generally considered best to be a bit more flexible on input mechanisms: i.e. rather than specifying that the input must be read from a file, specify its format as a string and leave the default formats open (so people can read from stdin, write a function which takes a string parameter, etc). 7. Some test cases would be good. \$\endgroup\$ – Peter Taylor Mar 8 '16 at 21:49
2
\$\begingroup\$

Igpā Atinlā (Pig Latin)

This is .

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:

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

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

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

  4. 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.
  5. 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Ā"

\$\endgroup\$
  • \$\begingroup\$ Is the string: bc a consonant cluster? \$\endgroup\$ – Downgoat Mar 6 '16 at 5:30
  • \$\begingroup\$ Yeah. "bc" --> "bcā". Is that not what the spec says? \$\endgroup\$ – Liam Mar 6 '16 at 5:32
  • \$\begingroup\$ ok, I wanted to clarify if the start/end of a string counts as a "non-vowel" character. Perhaps a better description is: "a sequence of consonants"? \$\endgroup\$ – Downgoat Mar 6 '16 at 5:34
  • \$\begingroup\$ I think it's clearer now? \$\endgroup\$ – Liam Mar 6 '16 at 5:52
  • \$\begingroup\$ Very closely related. \$\endgroup\$ – FryAmTheEggman Mar 7 '16 at 15:46
  • \$\begingroup\$ @FryAmTheEggman I think mine is sufficiently more complicated that it wouldn't be a dupe. However I don't know that the complexities are interesting enough to merit posting. \$\endgroup\$ – Liam Mar 7 '16 at 19:22
  • \$\begingroup\$ Some languages might not support the special a and A. Maybe allow regular A's? \$\endgroup\$ – CalculatorFeline Mar 9 '16 at 5:43
  • \$\begingroup\$ @CatsAreFluffy I know that some languages can't but I think that makes the challenge more interesting. At least a bit. If people disagree, I might change it to "ay" and "AY" \$\endgroup\$ – Liam Mar 9 '16 at 5:49
  • \$\begingroup\$ In the THIS CHALLENGE IS PROBABLY A DUPE test case, the A should become Anā instead of ANĀ. \$\endgroup\$ – user48538 Mar 9 '16 at 7:07
  • \$\begingroup\$ I'd call this a dup. \$\endgroup\$ – mbomb007 Mar 11 '16 at 15:29
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Can I adopt this abandoned challenge? \$\endgroup\$ – programmer5000 Jun 9 '17 at 12:12
  • \$\begingroup\$ @programmer5000 Yep! \$\endgroup\$ – randomra Jun 10 '17 at 17:02
2
\$\begingroup\$

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

enter image description here

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

\$\endgroup\$
  • \$\begingroup\$ As it is you would still get many Lenguage-like answers in the form of unary string, base convert, exec. Edit: Actually that wouldn't work, never mind. \$\endgroup\$ – feersum Jun 6 '15 at 15:51
  • 2
    \$\begingroup\$ The line between lenguage and slashes and brainfuck and real languages would be hard to define. Languages with fewer symbols tend to require more uses of those symbols to accomplish anything. \$\endgroup\$ – Sparr Jun 6 '15 at 17:01
  • \$\begingroup\$ @Sparr It's mainly about languages that encode information in the length of the program itself. It's not about number of symbols, although I could probably put a requirement that the program uses at least two symbols. \$\endgroup\$ – PhiNotPi Jun 6 '15 at 18:05
  • 3
    \$\begingroup\$ Alternatively you could consider each program to be terminated by an EOF character, which is included in the calculations. Then a $n$-character program in lenguage would score $-n \lg n/(n+1) - \lg 1/(n+1)$, which does grow indefinitely. PS I've just realised that my edits come down to the same thing as you were doing by flipping the quotient in the log upside down. Sorry about that. Revert if you want, but be aware that I might not be the only person who has $p \lg p$ so branded in their mind that anything else looks wrong. \$\endgroup\$ – Peter Taylor Jun 6 '15 at 18:46
  • \$\begingroup\$ @PeterTaylor p log (1/p) should be much more intuitive for people who see this the first time. \$\endgroup\$ – jimmy23013 Jun 7 '15 at 1:20
  • \$\begingroup\$ If you meant unique characters, Sclipting has an advantage for that selecting a character from the whole Unicode contains a lot of information (compared to the length of a short program). \$\endgroup\$ – jimmy23013 Jun 7 '15 at 1:23
2
\$\begingroup\$

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!
\$\endgroup\$
  • \$\begingroup\$ Its a good challenge, but you need to define your input/outputs a little more. I'd recommend indicating that tanks are passed in as a tuple/list, which tank is passed in first, and then define what the functions should return if red wins/blue wins/tie. \$\endgroup\$ – Nathan Merrill Mar 28 '16 at 15:32
  • \$\begingroup\$ @NathanMerrill, I've made some slight updates to the rules. I want to keep things open as I often find myself frustrated with arbitrary I/O restrictions. \$\endgroup\$ – wnnmaw Mar 28 '16 at 15:58
  • \$\begingroup\$ Flexible I/O is the way to go :) Looks good from my end. \$\endgroup\$ – Nathan Merrill Mar 28 '16 at 16:05
2
\$\begingroup\$

Diagonals of an Array

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?

\$\endgroup\$
  • \$\begingroup\$ I suggest a requirement that the order of the output diagonals be consistent (the same irrespective of input); and add a row matrix and column matrix as test cases \$\endgroup\$ – Luis Mendo Mar 26 '16 at 18:21
  • 1
    \$\begingroup\$ Now almost a duplicate. Also, Jelly has a 2-character built-in for this. (Just to let you know.) \$\endgroup\$ – Martin Ender Apr 6 '16 at 8:51
2
\$\begingroup\$

Help! Everything is in Wingdings!

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

\$\endgroup\$
  • \$\begingroup\$ @EasterlyIrk The input is an image containing wingdings characters. \$\endgroup\$ – Daniel M. Apr 10 '16 at 3:34
  • \$\begingroup\$ Related \$\endgroup\$ – Leaky Nun Apr 10 '16 at 3:35
  • \$\begingroup\$ @KennyLau This is different because the test cases will have up to 10 characters in the same image (and catering to the test cases is a standard loophole). I'll work on this more tomorrow. \$\endgroup\$ – Daniel M. Apr 10 '16 at 3:44
  • \$\begingroup\$ The description of the image seems underspecified to me. Will the characters all be the same font size? How will they be laid out? Colours? Anti-aliasing? \$\endgroup\$ – Peter Taylor Apr 10 '16 at 21:36
  • \$\begingroup\$ What is the subpixel rendering setting? \$\endgroup\$ – John Dvorak Apr 11 '16 at 10:22
  • \$\begingroup\$ @JanDvorak I'm not completely sure, so it's probably at whatever the default for Windows 10 is. If needed I can run the images through a program that creates a 1-bit image. \$\endgroup\$ – Daniel M. Apr 11 '16 at 10:56
2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Well I think that you have to choose a way of inputting and outputting data first to have an idea how to write the controller. If it's going to be single language KOTH you can just ask people to write you functions/classes in some way and you can attach those to a regular program performing the game. On the other hand the challenge seems simple enough that you may just give the input as arguments to an execution of the programs and read output for them (calling an instance of the bot for each move). \$\endgroup\$ – Lause Apr 11 '16 at 10:12
  • \$\begingroup\$ Yeah... I'll probably do it as an input/output thing, regardless of language. \$\endgroup\$ – Qwerp-Derp Apr 11 '16 at 10:55
  • 1
    \$\begingroup\$ 1. I think you've changed the size of the board so many times that there are figures in the question from at least three different board sizes. 2. In the video, the counters must be placed in increasing order of value, but the question doesn't mention this anywhere. 3. From my experience of other koths, best-of-50 is going to be far too time-consuming. I suggest making it best-of-5 or at most best-of-7. \$\endgroup\$ – Peter Taylor Apr 11 '16 at 21:39
  • \$\begingroup\$ Ah. Thanks for the tips... sorry if it's confusing. Will edit. \$\endgroup\$ – Qwerp-Derp Apr 12 '16 at 1:10
  • \$\begingroup\$ Interesting game. There is discussion about the different options for input and output on meta, and also there's a general tips for writing KotHs. \$\endgroup\$ – trichoplax Apr 12 '16 at 13:14
  • \$\begingroup\$ So... if there are multiple languages, will I have to install other things that can run those languages? That's a lot of stuff to prepare for, considering it's only for a short while (maybe for longer if I keep on doing KotHs). \$\endgroup\$ – Qwerp-Derp Apr 13 '16 at 10:13
2
\$\begingroup\$

Generate a waveform from audio

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:

waveform example

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

sine 440

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.
\$\endgroup\$
  • \$\begingroup\$ "common format"? \$\endgroup\$ – Addison Crump Mar 2 '16 at 21:37
  • \$\begingroup\$ @CoolestVeto Examples for audio include MP3, WAV, WMA, M4A, and OGG (basically any format Audacity can export to). Examples for graphics include PNG, JPG, BMP, SVG, PPM, GIF, etc. \$\endgroup\$ – Mego Mar 2 '16 at 21:40
  • \$\begingroup\$ So we're permitted to use any of those formats, not that we must allow for any of those formats? \$\endgroup\$ – Addison Crump Mar 2 '16 at 21:42
  • \$\begingroup\$ @CoolestVeto Correct. \$\endgroup\$ – Mego Mar 2 '16 at 21:43
  • \$\begingroup\$ Horizontal scale is specified, but (minimum) vertical scale is not. \$\endgroup\$ – Peter Taylor Mar 2 '16 at 22:31
  • \$\begingroup\$ @PeterTaylor What do you mean? The horizontal center of the image should represent 0 (silence), and the top/bottom should represent ±1 (the maximum/minimum measureable sample amplitude). The vertical scale should be linear, not logarithmic (measuring amplitude of the wave, not the loudness in decibels). \$\endgroup\$ – Mego Mar 2 '16 at 22:40
  • \$\begingroup\$ A 3-pixel high image could meet that spec. \$\endgroup\$ – Peter Taylor Mar 3 '16 at 7:06
  • \$\begingroup\$ @PeterTaylor Oh, I see the issue now, thanks. \$\endgroup\$ – Mego Mar 3 '16 at 19:51
  • \$\begingroup\$ Re The input audio must be sampled at 44.1 kHz with 32-bit floats (in the inclusive range [0, 1]), did you maybe mean the inclusive range [-1, 1]? \$\endgroup\$ – zwol Apr 21 '16 at 23:13
  • \$\begingroup\$ @zwol I did indeed, thanks. \$\endgroup\$ – Mego Apr 21 '16 at 23:23
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You might want to include some more background about monoids and congruent words. Also, test cases should include the expected output as well. The test cases would also be more readable in a code block without quotes. And I get that you want to show with the test cases that the choice of characters is arbitrary, but that's fairly clear from the spec. It would be more useful if you stuck to one set of characters in the test cases to make it easier for people to transform all of them at once into their own input format (instead of having to rewrite each one independently by hand). \$\endgroup\$ – Martin Ender Feb 16 '16 at 8:17
  • \$\begingroup\$ @MartinBüttner I guess I'm not attached to the test cases. I got rid of them and added a short introduction. \$\endgroup\$ – ymar Feb 17 '16 at 0:47
  • \$\begingroup\$ I didn't mean you should get rid of the test cases. They're important. I just meant, use the same pair of characters throughout to make them more usable. \$\endgroup\$ – Martin Ender Feb 17 '16 at 8:15
  • \$\begingroup\$ @MartinBüttner I've added new test cases. \$\endgroup\$ – ymar Mar 8 '16 at 14:35
  • \$\begingroup\$ Why are functions banned? \$\endgroup\$ – CalculatorFeline Mar 9 '16 at 5:38
  • \$\begingroup\$ @CatsAreFluffy This is personal preference - it's hard for me to understand why a function should be OK. It doesn't do the job (by itself) and it seems unfair to the people who write runnable programs. I feel that they do more. I'm new here and new to code golf so I don't know. Is there a reason functions should be allowed other than to make the top answer this much shorter? \$\endgroup\$ – ymar Mar 9 '16 at 7:29
  • \$\begingroup\$ Well, in powerful golfing languages, making a function can actually be longer (eg Cjam, Golfscript) But in Java, you have to include class Q{public static void main(String[]a){...}} in all your programs. Even in other (normal) languages, fewer bytes for input/output could help beat a golfing language. tl;dr It helps languages like Java have a chance against Python or other less-boilerplatey languages. \$\endgroup\$ – CalculatorFeline Mar 9 '16 at 15:20
  • \$\begingroup\$ Why are you demanding that the program allow its user to input a separator? What's the benefit in that as opposed to allowing the program to use whatever separator (not one of the letters, obviously) the programmer wants? \$\endgroup\$ – msh210 Apr 27 '16 at 19:25
  • \$\begingroup\$ @msh210 I don't think I'm saying that. My intention was to say exactly what you're saying. The separator is chosen by the programmer/program, but it can't be one of the letters. The letters are chosen by the user from a certain set and the separator is chosen from the same set. \$\endgroup\$ – ymar Apr 27 '16 at 19:52
  • \$\begingroup\$ Oh, okay, thanks for the edit. \$\endgroup\$ – msh210 Apr 27 '16 at 20:04
  • \$\begingroup\$ Allowing the user to choose any letters and forcing the program to come up with a different separator seems like it only adds arbitrary complexity that’s unrelated to the interesting part of the challenge. You should either guarantee that the valid input letters are x and y, or allow the programmer to choose the valid input letters. \$\endgroup\$ – Anders Kaseorg May 4 '16 at 22:13
2
\$\begingroup\$

Determine whether one graph is a subgraph of the other

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]
\$\endgroup\$
  • \$\begingroup\$ Sample input output? \$\endgroup\$ – Leaky Nun Apr 30 '16 at 11:22
  • 1
    \$\begingroup\$ I added some now. \$\endgroup\$ – flawr Apr 30 '16 at 14:06
  • \$\begingroup\$ @KennyLau How did create those visualizations? \$\endgroup\$ – flawr Apr 30 '16 at 15:21
  • 1
    \$\begingroup\$ Microsoft Paint. \$\endgroup\$ – Leaky Nun Apr 30 '16 at 15:27
2
\$\begingroup\$

Nested brackets in source code


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.
\$\endgroup\$
  • \$\begingroup\$ Shouldn't DO(i++;);DO(i++;DO(i++;)) be DO(i++;);DO(i++;DO(i++;););? \$\endgroup\$ – Peter Taylor May 14 '16 at 19:23
  • \$\begingroup\$ @PeterTaylor Yes it should, good catch. \$\endgroup\$ – Zgarb May 14 '16 at 19:25
  • \$\begingroup\$ Thought about this more. By making A end in ", L be (, R be ), and B start with ", I can reduce it to matching brackets in a string. If it's not a duplicate of an existing question, it has at least neutered the twist. \$\endgroup\$ – Peter Taylor May 16 '16 at 14:30
  • \$\begingroup\$ @PeterTaylor That's a valid approach, but I'm hoping that more quine-like solutions will be shorter, at least in "normal" languages. The error rule is intended to help with that too. \$\endgroup\$ – Zgarb May 16 '16 at 17:15
2
\$\begingroup\$

International Choice of Urinal Protocol efficiency

A long while ago, Randall Munroe of xkcd fame wrote a blog post entitled Urinal protocol vulnerability. The titular "International Choice of Urinal Protocol" is that when men enter a bathroom that has a row of urinals along the wall, they will first take the end urinals, and then take the urinals that are furthest from the other men. All men seek to avoid awkwardness, which happens when two men use adjacent urinals.

For example, if there are five urinals in a row, then by following this protocol, men will take urinals in this order:

UUUUU
1 3 2

In this case, the packing efficiency is optimal. However, when there are seven urinals, then this happens:

UUUUUUU
1  3  2

This is essentially the worst case. Fewer than half of the urinals are used, and Randall continues investigating when the best and worst cases happen. For this challenge, though, your only task is to calculate the packing efficiency of this protocol when given a number n of urinals, which is k/n where k is the number of urinals taken before awkwardness ensues.

Spec

  • Standard I/O and rules apply.
  • Input is a single positive integer n, which may be given as either decimal or unary.
  • Output must be either a float or a simplified fraction. If your language cannot do either of these easily (e.g. BF or Retina), then you may simply output k (in decimal or unary).

Test cases

Decimal

 1 1.0
 2 0.5
 3 0.6666666666666666
 4 0.5
 5 0.6
 6 0.5
 7 0.42857142857142855
 8 0.5
 9 0.5555555555555556
10 0.5

Fractions

 1 1/1 {or} 1
 2 1/2
 3 2/3
 4 1/2
 5 3/5
 6 1/2
 7 3/7
 8 1/2
 9 5/9
10 1/2

Urinals taken k

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

Note: this is A166079.

Related: The Urinal Protocol, which asks for all the possible ways men could take urinals with no restriction on the first and no awkwardness.

\$\endgroup\$
2
\$\begingroup\$

Find the smallest number bigger than the input whose digital sum is the input

"Digital sum" refers to the sum of all the digits in a number.

For example, the digital sum of 1324 is 10, because 1+3+2+4 = 10.

The challenge is to write a program/function to calculate the smallest number bigger than the input whose digital sum is the input.

Example with walkthrough

As an example, take the number 9 as the input:

9 = 1+8 -> 18
9 = 2+7 -> 27
9 = 3+6 -> 36
...
9 = 8+1 -> 81
9 = 9+0 -> 90

The valid output would be the smallest number above, which is 18.

Specs

Note that 9 is not the valid output for this example, because the reversed number must be greater than the original number.

Note that the input will be positive.

Test-Cases:

 2 => 11
 8 => 17
12 => 39
16 => 79
24 => 699
32 => 5999

References:

This is OEIS A161561.

\$\endgroup\$
  • \$\begingroup\$ As far as I know it's either 2 or there is none \$\endgroup\$ – levanth May 23 '16 at 14:14
  • \$\begingroup\$ I see what you mean, let me specify this a little better \$\endgroup\$ – levanth May 23 '16 at 14:17
  • \$\begingroup\$ I edited the question to include the additional rule and changed the term digital root with digital sum \$\endgroup\$ – levanth May 23 '16 at 14:38
  • \$\begingroup\$ Do you mean I should remove the mentioned part? \$\endgroup\$ – levanth May 23 '16 at 14:44
  • \$\begingroup\$ Could I edit the question for you? You can rollback the edit afterwards if you don't like it. \$\endgroup\$ – Leaky Nun May 23 '16 at 14:47
  • \$\begingroup\$ You are welcome to. This is my first Challenge I post here \$\endgroup\$ – levanth May 23 '16 at 14:49
  • \$\begingroup\$ Done. How's it now? \$\endgroup\$ – Leaky Nun May 23 '16 at 15:01
  • \$\begingroup\$ Also, you are welcome to join our chat. \$\endgroup\$ – Leaky Nun May 23 '16 at 15:01
  • \$\begingroup\$ Yes thats exactly what I meant. thank you \$\endgroup\$ – levanth May 23 '16 at 15:04
  • \$\begingroup\$ "because the reversed number must be greater than the original number." I don't know what you mean by this. Do you mean the output number must be greater than the input number? \$\endgroup\$ – AdmBorkBork May 23 '16 at 16:39
  • \$\begingroup\$ Yes it has to be greater. If you look at the examples you can see it: input 9 and output has to be a number which has at least two numbers which have 9 as its sum. \$\endgroup\$ – levanth May 23 '16 at 16:47
  • \$\begingroup\$ Can I post this abandoned proposal? \$\endgroup\$ – programmer5000 Jun 9 '17 at 13:03
2
\$\begingroup\$

Light the Way!

This is based on the Lights Out game. There is a grid of tiles, and clicking on a tile (performing a "move") toggles the state of the clicked tile as well as the (orthogonally) adjacent tiles. This variation will also toggle the diagonally adjacent tiles.

It is helpful to note that (on a board with only two states) all moves commute, so the order in which they are performed is not important. It follows that performing a collection of moves a second time will undo what was done the first time.

There are a few ways to present this challenge, so I'll describe some possibilities. Let me know what you think. The challenge could be one of the below:

  • Given a board size n (optional) and the initial state of the n-by-n board, determine an optimal collection of moves that will toggle every lit ("on") tile into its dark ("off") state.
  • Given n and a sequence of moves performed on an initially dark board of size n, provide the resulting matrix of states.
  • A variation on the above involving graphical output.

Input format would be flexible. n >= 1.


Snippet to show how the game works:

The board size may be adjusted in the first input field. The second field (functionality added by Conor O'Brien) will take a list of coordinates ([[0,0],[1,2],[3,0],...]) and perform the moves for you.

var table;
var color1 = "aqua",
	color2 = "yellow";
var moveList = [];

window.onload = function () {
	table = document.getElementById("lightGame");
	buildTable();

	var updateButton = document.getElementById("updateButton");
	if (updateButton) {
		updateButton.onclick = buildTable;
	}

	// added by Conor O'Brien
	document.getElementById("perform").addEventListener("click", function() {
		var toPerf = JSON.parse(document.getElementById("moves").value);
		//console.log(toPerf);
		function rec(arr) {
			var m = arr.shift();
			var x = m[0],
				y = m[1];
			var cell = table.rows[y].cells[x];
			update(cell);
			if (arr.length) {
				setTimeout(rec, 500, arr);
			}
		}
		rec(toPerf);
	});
};

function buildTable() {
	// get size
	var input = document.getElementById("size");
	var size = new Number(input && input.value || 5);
	
	var rows = size,
		cols = size;
	
	// clear moves
	moveList = [];
	moveHolder.innerHTML = "[]";
	
	// remove existing rows
	while (table.lastChild) {
		table.removeChild(table.lastChild);
	}
	
	// create new rows
	for (var y = 0; y < rows; y++) {
		var row = document.createElement("tr");
		
		for (var x = 0; x < cols; x++) {
			var cell = document.createElement("td");
			cell.style.backgroundColor = color1;
			cell.x = x;
			cell.y = y;
			cell.onclick = function () {
				update(this);
			};
			row.appendChild(cell);
		}
		table.appendChild(row);
	}
}

function update(cell) {
	var x = cell.x;
	var y = cell.y;
	
	var xMax = table.rows[0].cells.length;
	var yMax = table.rows.length;
	
	// update cell
	changeColor(cell);
	
	// update orthogonally adjacent
	if (x > 0) changeColor(table.rows[y].cells[x - 1]);
	if (x + 1 < xMax) changeColor(table.rows[y].cells[x + 1]);
	if (y > 0) changeColor(table.rows[y - 1].cells[x]);
	if (y + 1 < yMax) changeColor(table.rows[y + 1].cells[x]);
	
	// update diagonally adjacent
	if (x > 0 && y > 0) changeColor(table.rows[y - 1].cells[x - 1]);
	if (x > 0 && y + 1 < yMax) changeColor(table.rows[y + 1].cells[x - 1]);
	if (x + 1 < xMax && y > 0) changeColor(table.rows[y - 1].cells[x + 1]);
	if (x + 1 < xMax && y + 1 < yMax) changeColor(table.rows[y + 1].cells[x + 1]);
	
	// update moves
	// added by Conor O'Brien
    moveList.push([x, y]);
    moveHolder.innerHTML = JSON.stringify(moveList);
}

function changeColor(cell) {
	cell.style.backgroundColor = cell.style.backgroundColor === color1 ? color2 : color1;
}

function getStyle(elt, styleProp) {
	if (elt.currentStyle)
		return elt.currentStyle[styleProp];
	return document.defaultView.getComputedStyle(elt, null)[styleProp];
}
body {
	background-color: darkslategray;
	color: white;
}
#gameDiv {
	text-align: center;
}
header {
	margin: 25px;
}
h2, h4 {
	color: red;
	text-shadow: -2px -2px black;
}

#lightGame {
	border: 1px solid white;
	margin: auto;
}
#lightGame td {
	/*background-color: aqua;*/
	padding: 1px;
	height: 25px;
	width: 25px;
}
#updateDiv {
	margin: 25px;
}
button {
	margin-left: 10px;
}

#autoMoveDiv {
	margin-top: 10px;
}

footer {
	position: fixed;
	bottom: 0px;
	width: 100%;
}
footer small {
	color: cyan;
	position: absolute;
	bottom: 0px;
}
img {
	float: right;
}
<div id="gameDiv">
	<header>
		<h2>Light Game</h2>
	</header>
	<div>
		<table id="lightGame">
		</table>
	</div>
	<div id="updateDiv">
		<input id="size" name="size" type="number" min="1" max="20" pattern="\d{1,2}" value="5" required />
		<button id="updateButton" type="button">Update</button>
	</div>
	<div>
		Your moves: <span id="moveHolder">[]</span>
	</div>
	<div id="autoMoveDiv">
		Auto move: 
		<input id="moves" />
		<button id="perform" type="button">Do Moves</button>
	</div>
</div>


Related Questions

JsFiddle of the snippet I made.

\$\endgroup\$
  • 3
    \$\begingroup\$ Option 1 would be a duplicate IMO. I do like option 2, though. \$\endgroup\$ – Nathan Merrill May 24 '16 at 17:36
  • 1
    \$\begingroup\$ I agree with Nathan Merrill. \$\endgroup\$ – El'endia Starman May 24 '16 at 17:37
  • \$\begingroup\$ @NathanMerrill This does include diagonals too, so it's different. But I don't know how different that'd be programmatically. \$\endgroup\$ – mbomb007 May 24 '16 at 17:40
  • 1
    \$\begingroup\$ Does the board wrap? \$\endgroup\$ – trichoplax May 24 '16 at 17:43
  • \$\begingroup\$ Option two sounds like it's pretty much a duplicate of this one, though. Except for the initial board state and diagonals, that is. \$\endgroup\$ – Geobits May 24 '16 at 17:44
  • \$\begingroup\$ Does it need further variation? Hexagonal board? 3d? Broader effect? Random effect? Context dependent effect? \$\endgroup\$ – trichoplax May 24 '16 at 17:48
  • \$\begingroup\$ I'd definitely make diagonals bold. I completely missed that when reading. I think diagonals make either 1 or 2 unique. \$\endgroup\$ – Nathan Merrill May 24 '16 at 17:50
  • \$\begingroup\$ @trichoplax The board does not wrap. \$\endgroup\$ – mbomb007 May 24 '16 at 20:01
  • \$\begingroup\$ "Given a board size n (optional) and the initial state of the n-by-n board, determine an optimal collection of moves that will toggle every lit ('on') tile into its dark ('off') state." Or you can have "determine an optimal collection of moves that will toggle every lit tile into its dark state and vice versa". \$\endgroup\$ – msh210 Jun 15 '16 at 22:53
  • 1
    \$\begingroup\$ @msh210 If the goal is to toggle every tile, the solution is trivial. If the goal is merely to end with all light, then with all dark, getting from one to the other is also trivial (it's the set of all moves minus the set from the first answer). \$\endgroup\$ – mbomb007 Jun 16 '16 at 13:25
2
\$\begingroup\$

Shortest program with unknown halting status

Rules

  1. Post a term on the binary λ-calculus (BLC) whose termination is unknown.

  2. If someone proves that your term does or doesn't terminate, you entry is disqualified.

  3. The term with the smallest number of bits on the BLC wins.

Don't forget to also post a quick description of what you did and the original source code, otherwise we will just have to trust your random string meets the specs!

Example submission

Size: 579 bits

Program: 01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010

Explanation: this term, if it terminates, reduces to a list with all church-encoded natural numbers of the sequence of Collatz (A006577) from 0 to 2^256. It is not known if collats(n) halts for all n; we only know up to about 2^64, so my submission satisfies the specification. For a longer explanation, I've set this repository. The original code was written on Caramel and also on the repository. Here is a brief:

-- Receives fix and a natural, returns the number of
-- recursive calls until the collatz function halts.
collatz fix n = (fix go n)

    -- The recursive search
    go go n = (succ (even_odd_or_leq_one n even odd leq1))
        even = (go go (half n))
        odd  = (go go (succ (mul n 3)))
        leq1 = 0
\$\endgroup\$
  • 1
    \$\begingroup\$ The only thing I'd like to comment on is that the challenge shouldn't be limited to BLC, and that other languages should be allowed so long as they are valid. For example, there is no reason to disallow a python solution that does the same thing as the above BLC code. \$\endgroup\$ – Zwei Jun 7 '16 at 3:39
  • \$\begingroup\$ I agree with @Zwei, but also ban IO and other nondeterministic code. \$\endgroup\$ – HEGX64 Jun 7 '16 at 9:56
  • 2
    \$\begingroup\$ As commented on main, you need to define the system of axioms which are permitted for the proof. \$\endgroup\$ – Peter Taylor Jun 7 '16 at 11:03
  • \$\begingroup\$ Fair enough. I feel like this will never get enough momentum for any relevant answer, though. I might just not ask it. \$\endgroup\$ – MaiaVictor Jun 7 '16 at 11:10
  • 1
    \$\begingroup\$ @Dokkat This challenge is interesting imo, there are just a few things that need to be worked out such as how does one prove that a program does or does not terminate. Remove the BLC only rule and define the axiom system and this challenge should be good for main. \$\endgroup\$ – Zwei Jun 7 '16 at 14:59
  • \$\begingroup\$ I think it's better to keep the language restriction. \$\endgroup\$ – feersum Jun 7 '16 at 20:18
  • \$\begingroup\$ @feersum for what reason? \$\endgroup\$ – Zwei Jun 8 '16 at 0:15
  • \$\begingroup\$ @Zwei the whole point of the challenge is that I want the program with the lowest Kolmogorov Complexity. It is hard to talk about this metric when you don't have a fixed language. There is a very clear and trivial measure of the complexity of a term on the binary lambda calculus. In fact, I'd say the only way for a code golf challenge to be an objective competition (not just a popularity contest) is by using a fixed language with a clear complexity metric, and the BLC is about as good as we know. \$\endgroup\$ – MaiaVictor Jun 8 '16 at 13:50
  • \$\begingroup\$ @Dokkat fair enough. \$\endgroup\$ – Zwei Jun 8 '16 at 15:23
  • \$\begingroup\$ That link is to binary combinatory logic, not binary lambda calculus. \$\endgroup\$ – CalculatorFeline May 31 '17 at 17:55
2
\$\begingroup\$

Pareto frontier

A point (x1,y1) dominates another point (x2,y2) if both x1≥x2 and y1≥y2. A set of points is a Pareto frontier if no point dominates another point. In other words, any increase in one coordinate must be met with a decrease in the other coordinate.

Your task is to decide whether a given set of points is a Pareto frontier.

Input: A collection of two or more points, which are pairs of positive integers. No two points will have the same x-value or the same y-value. You may not assume the points are given in a particular order.

Output: A consistent Truthy value if it is, and a consistent Falsey value if it's not.

True:

[(12, 1), (6, 4)]
[(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)]
[(4, 4), (3, 8), (12, 3), (20, 1)]
[(106, 106), (107, 102), (104, 127)]

False:

[(5, 9), (4, 8)]
[(1, 1), (11, 11)]
[(5, 3), (2, 4), (7, 7), (1, 2)]
[(15, 2), (7, 8), (4, 14), (6, 6)]

Sandbox:

  • Is it better to do the decision problem, or the filtering problem of finding the upper Pareto frontier of non-dominated points?

  • Should the input be allowed to be taken pre-zipped, as two lists of n numbers? What about a 2D 2-by-n array versus an n-by-2 array?

\$\endgroup\$
  • \$\begingroup\$ I'd recommend only doing the filtering problem if there is a nicer solution than subsets -> filter on decision -> take longest that you can enforce with restraints of some kind. Otherwise I feel like it might be kind of chameleon-y. \$\endgroup\$ – FryAmTheEggman Jul 13 '16 at 1:49
  • \$\begingroup\$ The decision problem can be done as filter and check equality; or sort on one axis and check that the other axis is in reverse order. The filter problem can be done by filtering the power set with the decision problem and taking the longest; or by folding a removal of dominated points. IMO the filter problem is more interesting, because sort builtins are very common and typically cheap. \$\endgroup\$ – Peter Taylor Jul 13 '16 at 10:37
  • \$\begingroup\$ @PeterTaylor The largest Pareto-incomparable subset might contain points dominated by the rest of the set. I expect filtering would be done by folding removal. Does that affect your opinion? \$\endgroup\$ – xnor Jul 20 '16 at 5:16
  • \$\begingroup\$ Ah, true. Folding removal still seems more interesting to me than sorting and checking reverse order. \$\endgroup\$ – Peter Taylor Jul 20 '16 at 7:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .