461
\$\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

2615 Answers 2615

3
\$\begingroup\$

Comedy of exceptions

Your goal is to demonstrate the shortest program or function that can throw 10 different types of errors/exceptions (I use the two interchangeably here) at runtime.

This question is only open to languages which have an object-oriented type system for errors. Furthermore, in the case of each error, a message including a clear identification of the exception's type must be printed. Evidently, it must also have at least 10 error types. Other systems such as an integer error code identifying the error, or all errors represented by strings are not acceptable.

Input is an integer from 0 to 9 inclusive. The program should reliably throw a different type of error for each input.

Methods which allow exceptions of arbitrary type to be thrown may not be used. E.g, throw ....

Determining whether two errors are of different type (TODO: fill in detail of output)

Java: x and y print different stack traces, but are the same type, so they can't be used.

Python: UnboundLocalError ..... and NameError ....... would count as two types of error, since, although UnboundLocalError is a subclass of NameError, type() would give different results for the two.

C++: stoi("aaaa") printing ......... would be valid since the message gives std::invalid_argument. Integer division by zero would not since it crashes the program without a message informing of the error type

Sandbox

Please comment if you are aware of a language that is borderline on eligibility, blurs boundaries between error types, or has other loopholes.

\$\endgroup\$
  • \$\begingroup\$ Would exceptions from standard modules be allowed (e.g. from urllib.error import *)? How about third-party modules/libraries (e.g. django, boost)? Or even custom exception subclasses? \$\endgroup\$ – grc Nov 26 '15 at 11:17
  • 1
    \$\begingroup\$ I don't know if I can find 10 different ones, but CJam can print a number of errors. Some of these are CJam-specific errors (empty stack, type mismatch; these tend to be displayed as "RuntimeException" but with a distinguishing error message) and some of them, I think, are just crashes happening in the interpreter exiting with a Java exception. How would that be treated? (I think it's also different between the Java and the JavaScript interpreter.) \$\endgroup\$ – Martin Ender Nov 26 '15 at 15:01
  • 1
    \$\begingroup\$ To make this more specific, here are 11 different errors (with different error messages), but some are backed by the same exception type within the interpreter. Would these still count as different? pastebin.com/VJCiVYMf (Also note that CJam itself has no concept of exceptions... if there's an error it crashes... these are just the exceptions types used by the interpreter.) \$\endgroup\$ – Martin Ender Nov 26 '15 at 15:14
  • 2
    \$\begingroup\$ I can think of a language which has exceptions but not an object-oriented type system: SML. (Haskell almost certainly has some exception monad too...). \$\endgroup\$ – Peter Taylor Nov 26 '15 at 21:05
  • \$\begingroup\$ @grc I think I will allow standard libraries, but not 3rd-party ones. Any method of defining and throwing a custom exception type should fall under the rule "Methods which allow exceptions of arbitrary type to be thrown may not be used." \$\endgroup\$ – feersum Nov 27 '15 at 0:28
  • \$\begingroup\$ @MartinBüttner It appears that the are Java exceptions and that CJam does not have its own exception type system, meaning it cannot be used. \$\endgroup\$ – feersum Nov 27 '15 at 0:29
  • \$\begingroup\$ @PeterTaylor HM-based type systems should be OK. Maybe I can find a better description than "object-oriented". \$\endgroup\$ – feersum Nov 27 '15 at 0:31
  • 1
    \$\begingroup\$ @feersum Then you should probably clarify what you mean by "error" (because the first sentence says that both errors and exceptions are allowed... just because there's no way to catch the error doesn't mean that language doesn't have errors... and most of these errors are actually thrown by the interpreter on purpose, and not raised by Java due to the interpreter having a bug). \$\endgroup\$ – Martin Ender Nov 27 '15 at 14:18
  • \$\begingroup\$ @sysreq The input is a number when determines which type of exception you should throw. \$\endgroup\$ – feersum Dec 10 '15 at 23:24
3
\$\begingroup\$

Count up by factor keys

TODO: Better title

Information

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

  • Compute the prime factorization of n: n = p1e1 * p2e2 * p3e3 * ... where all pi are prime, distinct and in increasing order, and all ei are positive integers.

  • Compute each piei; call these factors the fi. So n = f1 * f2 * f3 *....

  • Convert each fi to a string.

  • Concatenate all the strings together.

  • Evaluate as a number.

Examples:

The factor key of 2376 is 82711, since 2376 = 23 * 33 * 11 = 8 * 27 * 11.

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

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

Challenge

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

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

This is , so the shortest solution in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ In the case (I'm not sure whether it occurs, but you haven't stated that it doesn't) that two numbers have the same factor key, can they be output in any order or do you want to define a tie-break? \$\endgroup\$ – Peter Taylor Nov 30 '15 at 12:35
  • \$\begingroup\$ @PeterTaylor It does occur (see 36 and 49), but the question states "If two numbers have the same factor key, output the smaller number first." \$\endgroup\$ – Mego Nov 30 '15 at 20:48
  • \$\begingroup\$ By reverse engineering, it seems that the e_i must be non-zero. That's worth stating in the spec, and backing up with an example (i.e. any odd number greater than 1). \$\endgroup\$ – Peter Taylor Nov 30 '15 at 22:18
  • \$\begingroup\$ @PeterTaylor Done. \$\endgroup\$ – lirtosiast Nov 30 '15 at 22:25
3
\$\begingroup\$

Juggling without collisions

Determine if a siteswap juggling pattern is valid, meaning that no two balls land on the same beat. Fewest bytes wins.

Input: A non-empty list of positive integers.

Output: A consistent Truthy value for valid or Falsey value for invalid.


Siteswap is a notation for juggling patterns. Dividing time into units called beats, a siteswap pattern says how high to throw the ball each beat, measured in beats that it's airborne until you catch it. For example, the pattern

4 2 3

says

  • On the first beat t=1, throw the ball 4 beats high, so you catch it at t=5.
  • On the second beat t=2, throw the ball 2 beats high, so you catch it at t=4.
  • On the third beat t=3, throw the ball 3 beats high, so you catch it at t=6.

If we treat this pattern as a periodic sequence

... 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 ...

note that on every beat, you catch exactly one ball. But, in

 5 1 3 4 2 ...

the ball thrown for 5 beats at t=1 and the ball thrown for 3 beats at t=3 both come down at t=6, which we don't want (let's ignore that we have two hands). This happens whenever two numbers in the sequence have the same different as the number of beats between them, with the bigger on first. Note that this may happen across repetitions, like in 8 1 2, where the marked balls collide at *.

 v             v *
 8 1 2 8 1 2 8 1 2 8 1 2 ...

TODO: Test cases.

Sandbox: Does the explanation make sense? Is it too long for the challenge?

\$\endgroup\$
  • \$\begingroup\$ Related. :) \$\endgroup\$ – Martin Ender Dec 21 '15 at 11:26
  • \$\begingroup\$ @MartinBüttner Those are some nice ASCII diagrams, mind if I steal them? \$\endgroup\$ – xnor Dec 21 '15 at 11:32
  • \$\begingroup\$ Sure, if you don't mind them blowing up your spec. ;) \$\endgroup\$ – Martin Ender Dec 21 '15 at 11:32
  • \$\begingroup\$ I think this challenge should still be happening. :) \$\endgroup\$ – Martin Ender Jun 19 '16 at 21:16
  • \$\begingroup\$ @MartinEnder I've had this in the sandbox way too long, and don't have the energy to polish it up now. Do you want to take it? \$\endgroup\$ – xnor Feb 15 '18 at 5:35
3
\$\begingroup\$

Elements with 100 ≤ Z < 1000


The International Union of Pure and Applied Chemistry (IUPAC) decided that it is necessary to have a systematic naming for the elements, even for those which had not been discovered. The rules for naming are:

  1. The name is derived directly from the atomic number of the element using the following Latin numerical roots:

    Number     Root
    ------     ----
    0          nil
    1          un
    2          bi
    3          tri
    4          quad
    5          pent
    6          hex
    7          sept
    8          oct
    9          enn
    
  2. The roots are put together in the order of the digits which make up the atomic number and terminated by 'ium' to spell out the name. The final 'n' of 'enn' is omitted when it occurs before 'nil', and the final 'i' of 'bi' and of 'tri' when it occurs before 'ium'.

  3. The symbol of the element is composed of the initial letters of the numerical roots which make up the name.

For this challenge, let us consider the elements having a three digit atomic number.

Examples:

100 --> Unnilnilium
101 --> Unnilunium
111 --> Unununium
150 --> Unpentnilium
200 --> Binilnilium
500 --> Pentnilnilium
999 --> Ennennennium

Input

  • Input can be taken from one of the following

    • stdin
    • Command-line arguments
    • Function arguments (One argument, as a string)
  • Input will contain either a valid IUPAC name of an element, or a valid IUPAC symbol of an element.

Output

  • Output the corresponding
    • IUPAC name if the input is a symbol of an element.
    • symbol if the input is an IUPAC name of an element.

Rules

  • The input will contain a valid IUPAC name/symbol.
  • The first character of the symbol/name in input will be in upper-case and should remain capitalized in the output.
  • You are permitted to write a full program or a function.
  • There should be no unnecessary characters except an optional trailing newline character.

Test Cases

Unu            --> Unnilunium
Eee            --> Ennennennium
Enn            --> Ennilnilium
Bnb            --> Binilbium
Ubt            --> Unbitrium
Qsn            --> Quadseptnilium

Septenntrium   --> Set
Hexunbium      --> Hub
Octennilium    --> Oen
Bibibium       --> Bbb
Ununennium     --> Uue
Triquadpentium --> Tqp

Scoring

This is , so the shortest submission (in bytes) wins.


Tags:


Sandbox: What do you guys think about this challenge? Anything to improve? Did I miss anything?

\$\endgroup\$
  • \$\begingroup\$ For the title, maybe "Elements after Fermium", since that's element 100. \$\endgroup\$ – isaacg Dec 26 '15 at 11:14
  • \$\begingroup\$ Omit the line "not relevant in this challenge" \$\endgroup\$ – isaacg Dec 26 '15 at 11:15
  • \$\begingroup\$ Related: codegolf.stackexchange.com/questions/60208/… \$\endgroup\$ – lirtosiast Dec 26 '15 at 23:13
  • \$\begingroup\$ @ThomasKwa Oh. Thanks! Didn't know that a similar challenge existed! \$\endgroup\$ – Spikatrix Dec 27 '15 at 4:40
  • \$\begingroup\$ @isaacg Thanks! I made some changes now. \$\endgroup\$ – Spikatrix Dec 27 '15 at 4:41
3
\$\begingroup\$

Rational Number to Repeating Numeral Conversion

As I'm sure you know, the decimal expansion of every rational number is either terminating—consisting of a finite number of digits, or repeating—consisting of infinitely many digits, but ending with a finite pattern that repeats itself indefinitely: for example, the decimal expansion of the rational number 1/6 is 0.1666..., where the sixes repeat forever. One way to represent this decimal expansion finitely and unambiguously, is to write the repeating part, called the repetend, enclosed in parentheses: going back to the previous example, under this scheme the number 1/6 is written as 0.1(6). We call this representation a repeating decimal. Of course, none of this is specific to base 10. More generally, we call such a representation, in any base, a repeating numeral. Note that, for the sake of this challenge, we use the term "repeating numeral" (or simply, "numeral") to refer to any numeral written using this scheme, whether or not it actually has a repeating part.

Challenge

Write a program or a function taking a pair of integers, p and q, and returning a repeating numeral representing the rational number p/q. You may assume that p ≥ 0, and q > 0, so that p/q is never negative. The resulting numeral should be in base 10, unless you go for the relevant bonus below.

There is more than one possible numeral representing a given rational number. For example, the rational number 1/1 can be represented, among (infinitely many) other options, as 1, 1.0, 1.(0), 0.(9), and so on... For this challenge, however, we'd like the output to be unique. The following set of rules, which your program must follow, takes care of that:

  • When the integer part of the numeral is zero, there should be a single 0 before the radix point. For example, given the input 1/2, the output should be 0.5, and not .5.

  • The repetend, if exists, must begin after the radix point; that is, it shouldn't apply to the integer part. For example, given the input 10/9, the output should be 1.(1), and not (1).

  • The output should be finite and minimal, under the above rules. This is the most significant rule controlling the output, so it's worth highlighting some of its consequences:

    • There should be no leading or trailing zeroes. For example, given the input 3/2, the output should be 1.5, and not 01.5 or 1.50.

    • If the fractional part is zero, it should be omitted. For example, given the input 1/1, the output should be 1, and not 1.0.

    • If the repetend is zero, it should be omitted. For example, given the input 1/2, the output should be 0.5, and not 0.5(0).

    • When the input admits a terminating numeral, there shouldn't be an unnecessary repetend. For example, given the input 1/1, the output should be 1, and not 0.(9).

    • The repetend, and the rest of the fractional part, should not be superfluous; there shouldn't be any repetition in the repetend itself, nor in the repetend and the rest of the fractional part. For example, given the input 1/99, the output should be 0.(01), and not 0.01(01), 0.(0101), or 0.0(10).

As usual, you may not use any built-in or library functions aimed specifically at this problem.

Input and Output

You may take the input through the command line, through STDIN, as function arguments, or using an equivalent method. You may use any convenient format for the input, but make sure to specify it in your post. You may assume that p and q are no greater than 10,000,000, to the extent that it helps you to avoid overflow.

You may write the output to STDOUT, return it as the function's result or through an output parameter, as a string, or use an equivalent method.

Score

This is code-golf. The shortest answer, in bytes, combined with the any of the bonuses, wins.

Bonuses

If, in addition to the requirements listed above, your program satisfies the requirements for any of the following bonuses, multiply your score by the specified amount.

×0.8 Bonus Support other bases
Your program should take a third parameter, b, which is an integer between 2 and 36, inclusive, and return the corresponding numeral in base b, instead of base 10. The letters of the alphabet, either in lowercase or uppercase, should be used as digits above 9. For example, given the input 1/2 and b=3, the output should be 0.(1). Note that base b applies only to the output—if your program takes its input in string form, it should interpret it in base 10.

×0.6 Bonus O(1) space complexity
Your program's space complexity should be O(1), where the unit of space is the amount of space required to hold the input. In other words, the amount of memory required by your program should, on a large scale, be proportional to the amount of memory required by the input. You may not use the fact that the input range is bounded when reasoning about your program's space complexity, other than to the extent of establishing the amount of space required by the input. If you go for this bonus, it is strongly advised that you include at least a brief explanation of your program, so that others can verify that it meets the criterion.

If your program does not print the output directly, but rather returns a string, you may ignore the space occupied by the string as long as your program only appends to the string, and doesn't modify or read from it otherwise. (Note that something like s=s+"0" is fine, even though it technically involves reading from the string.)

Test Cases

Each of the test cases below lists the input, p/q, on the first line, and the corresponding output on the second line. Some of the tests list a third parameter, b, which specifies a different base for the output. These tests are only applicable for the relevant bonus.

Short-Output Tests

Your program should solve each of the following tests in a matter of seconds.

0/1
0

123/123
1

12/3
4

1/2
0.5

1/3
0.(3)

7/6
1.1(6)

3/11
0.(27)

1234/9999
0.(1234)

7/12
0.58(3)

22/7
3.(142857)

123/456
0.269(736842105263157894)

7124771/4545450
1.56(745118)

1/68
0.01(4705882352941176)

678/2345
0.2(891257995735607675906183368869936034115138592750533049040511727078)

7683/238
32.2(815126050420168067226890756302521008403361344537)

123631/99999
1.(23632)

4576/2345
1.9(513859275053304904051172707889125799573560767590618336886993603411)

2239231/4950000
0.45236(98)

673/23430
0.0(2872385830132309005548442168160478019632949210413999146393512590695689)

8984/2318
3.(875754961173425366695427092320966350301984469370146678170836928386540120793787748058671268334771354616048317515099223468507333908541846419327006039689387402933563416738567730802415)

1/2 2
0.1

214/5467 13
0.(067ccb5145334200a07b6253394bc5ca12bc650017b87998acc2c516a7993810702ba1)

214 5467 11
0.0(481119a34a86245a0053a1022114643a64131367585a8095498942556925833303993816590371976aa2a6952238969a61490900a792044229187a18262724060a517a986785002750566607877532070733842a95a27a4476828a12971701a4740884573649355153)

330420/335923 36
0.(zero)

9322181/306936 28
12.ab(cd)

123/6573 29
0.(0flb8c3hblol)

123/6573 21
0.0(85669592cjj9ca173fij6g67hhg7g940b5efk6j2bb7276c1ch25ikf7dd070jf4h96hek41ji102h3ea6kb2ic5hc3089b19kjc8dfhaf9147c48kgg4k5ab463d1fd5k86eigacciai54ihj3k2e7aghdbcfeebfbi811b8ajdh521e4ed334d4bgk9f650e1i99dide8j83if205d77kdk15g3be360gj12jki3h6ae09i28f38hkcb9jb018c753a5bjgd8gc044g0fa9geh7j57f0ce624a882a2fg231h0i6da4379)

Long-Output Tests

The following tests produce significantly longer output. Instead of listing their full output, only the MD5 checksum of the output if given. The checksum is calculated without a trailing newline, and using lowercase letters for digits above 9 (in the relevant test cases). If you want to see the full output for these tests, or to calculate the checksum under different conditions, you can use the test snippet below. Your program should solve each of the following tests in no more than a few minutes.

343/677472
e1810c85500a97c36f2ba5dcc94a2aa6

234/62332
662adcee10cd77d001282f0e31a84b77

57628/7894211
81222aaa93f192c6d8334fcde6381a74

67332/1267232
3ea190c83a735a8bafc922cbb177e6f4

954/3684332
d4ef940c9986f9c2ac52ee822d94d6a7

783232/3462241
7724d3444b5540b8b4f07d13317e8da3

83/7657124
b295369267f48e642e202e0364898c82

764231/54646224
ecf7f3dd12f2d495b31a178fc03662d7

6743/1231234
9f447fd27447abb881795fc5e2f814e5

764/9343249
8381dc6f127be6d95cadc0b5bdd70104

345/2234448 22
667d437e35c3825696f64f1b27e6a827

63451/2343324 3
5d86d77856cc0a15ac8a51b46c2f22d6

93457/546464 2
1084e884aded53f0da933480c45db1b8

678541/453524 9
5bb54bddaab7bd933258d4d78a83cdba

4572/2341198 15
39af2bc67ab58438068f672ed3a8357d

1/4821466 6
57ba79a48c438b7fd21aa39ee3575c8d

145/5821417 21
009f087ae661cfd4690cc51ba71a827f

5472/2333645 33
d24583dfdad205de61763c6a87637979

Test Snippet

If you want to further test your submission, you can use the following test snippet to find the repeating numeral representation of arbitrary rational numbers, or to find the rational number corresponding to arbitrary repeating numerals. Note that the result can get very big, very fast, which can be a little much for your browser; in this case, you might want to uncheck the "Result" checkbox, and check the "MD5" checkbox, to only get the MD5 checksum of the output. Note also that you can resize the input and output boxes.

<style>* { font-family: sans-serif; }table { border-collapse: collapse; }table > tbody > tr > td { padding: 0px; }#status { display: none; }#status[loading] { display: initial; font-style: italic; }#main { display: none; width:100%; border-right:.7em solid transparent; font-size: 95%; }#main[loaded] { display: table; }#main > tbody > tr + tr > td { padding-top: .25em; }#main > tbody > tr > td + td { padding-left: .5em; }#main > tbody > tr > td:first-of-type { width: 4.25em; }.label { white-space: pre; }#flags { padding-left: 2.4em; font-size: smaller; }#flags > table > tbody > tr > td + td { padding-left: 1em; }#error { display: none; font-size: smaller; color: #880000; }#error[error] { display: initial; }#job_cancel, #job_throbber { display: none; vertical-align: bottom; }#job_cancel[working], #job_throbber[working] { display: initial; }#job_throbber > img { height: 1em; }#job_throbber[working] { padding-left: .3em; }#job_cancel[working] { padding-left: 1em; }#job_cancel > input { height: 1.8em; font-size: small; }input[type="text"], input[type="number"], textarea { padding: 0.25em; height: 1.4em; font-family: monospace; }textarea { width: 100%; }#base { width: 2.8em; text-align: right; }.output { background-color: #e4e4e4; border: none; }#length { width: 8em; text-align: right; }#md5 { width: 20em; text-align: center; }#result_container[active="false"] { display: none; }#md5_container[active="false"] { display: none; }</style></head><body><div id="status" loading>Loading...</div><table id="main" onkeydown="handle_key_down(event)"><tr><td id="input_label" class="label">Fraction:</td><td><textarea id="input" oninput="update(true)" spellcheck="false">123/456</textarea></td></tr><tr><td class="label">Base:</td><td><table><tr><td><input id="base" type="number" value="10" spellcheck="false" oninput="update(true)"></td><td id="flags"><table><tr><td><label><table><tr><td><input id="flag_result" type="checkbox" checked onchange="handle_flag('result')"></td><td>Result</td></tr></table></label></td><td><label><table><tr><td><input id="flag_md5" type="checkbox" onchange="handle_flag('md5')"></td><td>MD5</td></tr></table></label></td><td><label><table><tr><td><input id="flag_uppercase" type="checkbox" onchange="handle_flag('uppercase')"></td><td>Uppercase</td></tr></table></label></td><td><label><table><tr><td><input id="flag_trailing_newline" type="checkbox" onchange="handle_flag('trailing_newline')"></td><td>Trailing Newline</td></tr></table></label></td><td><label><table><tr><td><input id="flag_progressive_output" type="checkbox" onchange="handle_flag('progressive_output')"></td><td>Progressive Output</td></tr></table></label></td></tr></table></td></tr></table></td></tr><tr><td></td><td><span id="error"></span></td></tr><tr><td class="label">Length:</td><td><table id="length_table"><tr><td><input id="length" class="output" type="text" spellcheck="false" readonly></td><td id="job_throbber"><img src="http://i.stack.imgur.com/sHKZY.gif"></td><td id="job_cancel"><input type="button" value="Cancel" onclick="cancel_job()"><td></tr></table></td></tr><tr id="md5_container"><td class="label">MD5:</td><td><input id="md5" class="output" type="text" spellcheck="false" readonly></td></tr><tr id="result_container"><td id="result_label" class="label">Numeral:</td><td class="full_width"><textarea id="result" class="output" spellcheck="false" readonly></textarea></td></tr></table><script async type="text/javascript" src="https://gist.githack.com/anonymous/49705525fd01ba66c1ad/raw/c35226ad89444e3af07d0e505f7163df8574b860/repnum.js"></script>

\$\endgroup\$
  • \$\begingroup\$ Isn't space complexity technically going to be at least O(log (p+q))? \$\endgroup\$ – Martin Ender Dec 22 '15 at 15:20
  • \$\begingroup\$ @MartinBüttner Technically, yes. I'm going to define the unit of space as the amount of space required to hold the input, thus implicitly dividing by O(log n). \$\endgroup\$ – Ell Dec 22 '15 at 15:25
  • \$\begingroup\$ Ah, that's a very good idea. Much better than the usual attempts of "but ignore the memory used to store the input...". \$\endgroup\$ – Martin Ender Dec 22 '15 at 15:26
  • \$\begingroup\$ I completely ignored your actual question: no, I wouldn't consider it a duplicate. ;) \$\endgroup\$ – Martin Ender Dec 22 '15 at 16:28
  • 1
    \$\begingroup\$ I like the simplicity of the idea and would suggest keeping it simple by not requiring other bases or having a complexity limit. \$\endgroup\$ – xnor Dec 23 '15 at 6:37
  • \$\begingroup\$ I agree with @xnor; I also think the bonuses are unnecessary. \$\endgroup\$ – lirtosiast Dec 30 '15 at 21:44
  • \$\begingroup\$ @ThomasKwa Keep in mind that xnor's comment was written before the actual spec, when the bonuses were proposed as hard requirements (see the edit history.) I'm not likely to get rid of the O(1) space thing entirely—I think it makes for a much more interesting challenge (there's also a closely related challenge [edit history] that I don't want to get too close to.) TBH, I think the different bases bonus is mostly interesting in conjunction with the O(1) space bonus; I agree that in itself it doesn't add too much to the challenge. \$\endgroup\$ – Ell Dec 30 '15 at 22:17
  • \$\begingroup\$ I'm not a fan of the bonuses. Also, I'm concerned there will be disagreements about the space complexity of built-ins. In some languages, implementation is not apecified, only result. It's also hard to tell n log n from linear because of constants. \$\endgroup\$ – xnor Dec 30 '15 at 23:25
  • \$\begingroup\$ @xnor I'm going to go with common sense with regard to builtins: If the most obvious implementation of a builtin is O(1), then, unless someone knows otherwise, I'm fine with it. If the builtin does something nontrivial, that might not be O(1), then it's the poster's responsibility to show it's O(1), or not use it. I agree that reasoning about complexity is tricky, and complicates things: that's part of the challenge, and that's why I think it deserves a bonus. \$\endgroup\$ – Ell Dec 31 '15 at 13:12
  • \$\begingroup\$ The space complexity required to hold the input is O(n), not O(1), since n is conventionally the input length, and O(1) is a constant that does not depend on the input. \$\endgroup\$ – xnor Dec 31 '15 at 17:14
  • \$\begingroup\$ @xnor We can use whatever "frame of reference" we want when measuring complexity. If we define the unit of space to be the amount of space required by the input, then a complexity of O(1) simply means that space usage has to be proportional to the space occupied by the input, which might (in "absolute" terms) be fixed, or might depend on the actual value of p and q. Specifying it this way allows us to define the complexity requirement uniformly, without worrying about the details. \$\endgroup\$ – Ell Dec 31 '15 at 19:40
  • \$\begingroup\$ @xnor, ThomasKwa, Anyway, having thought about it some more, I might end up dropping the bonuses, and doing the complexity thing out-of-band as a bounty. I'm going to leave this in the sandbox for a while longer, at least until next year... Happy new year! \$\endgroup\$ – Ell Dec 31 '15 at 19:42
  • \$\begingroup\$ No, that's like saying we define 2 to be 3 and then 2+2=6. O(1) means O(1). 1 is not a variable. Readers will get confused if you redefine existing notation. \$\endgroup\$ – xnor Dec 31 '15 at 19:46
  • \$\begingroup\$ How if my program allocates p+q+n space with n constant and unit space is byte? \$\endgroup\$ – Akangka Jan 1 '16 at 2:08
  • \$\begingroup\$ Make all bonus mandatory. \$\endgroup\$ – Akangka Jan 1 '16 at 2:08
3
\$\begingroup\$

This challenge was closed, because it was way too broad, but, in the comments, SuperJedi224 suggested a slightly different challenge that I thought was a really good idea, so I'm stealing it and posting it here.


Write a text editor in 2000 bytes or less

Write a text editor in 2000 bytes or less. It should support loading and saving files (or something else if your language doesn't support that, maybe?), modifying text, and displaying the contents of a file that's currently open in some format.

Sandbox questions

  • I'm not sure if 2000 bytes is the right number. SuperJedi224 originally suggested 10000, but that seems to me like too many.
  • Should some features be required, or should it just be by votes? Will votes take care of possible submissions that aren't actually text editors?
  • Should there be some kind of bonus for shorter submissions? Maybe an extra point for every 20 or so bytes you don't use? No, there probably shouldn't be.
  • Should languages that don't support file operations be allowed?
\$\endgroup\$
  • \$\begingroup\$ This is still very broad, and I think I would vote to close as off-topic, as this is essentially a UX contest, which isn't much different from an art contest. \$\endgroup\$ – FryAmTheEggman Jan 6 '16 at 15:55
  • 1
    \$\begingroup\$ I would recommend either an upper limit on bytes, or plain code golf. Trying to be somewhere in between with a bonus seems awkward. \$\endgroup\$ – trichoplax Jan 7 '16 at 0:02
  • 1
    \$\begingroup\$ @trichoplax I agree. Plain code golf won't work unless we can create a much more precise specification, and that doesn't seem as interesting as a popularity contest, so I guess it should just be an upper limit. \$\endgroup\$ – KSFT Jan 7 '16 at 0:42
  • 1
    \$\begingroup\$ I think that the more precise you make the requirements, the more the voting can reflect how well the code fulfills these, rather than just being about arbitrary popularity. The more open ended the popularity criteria, the more likely the question will be closed. \$\endgroup\$ – trichoplax Jan 7 '16 at 0:56
  • \$\begingroup\$ That's a good point. Do you have any suggestions for criteria? \$\endgroup\$ – KSFT Jan 7 '16 at 0:58
  • \$\begingroup\$ Whatever limit you choose, there will be some languages which are excluded by this and other languages for which the limit is too high to provide any restriction. So instead of trying to suit all languages, it might be easiest to just think about the readers of the answers - how much code do you want them to have to read through for each answer? \$\endgroup\$ – trichoplax Jan 7 '16 at 0:59
  • \$\begingroup\$ I guess you can add criteria gradually while it's here in the sandbox until it seems ready. What's the bare minimum it should be able to do? Do you just want keyboard input or mouse input too? Are there any shortcuts that should be included? \$\endgroup\$ – trichoplax Jan 7 '16 at 1:01
  • \$\begingroup\$ Not sure if this will be relevant, but just as a rough guide, this list of small text editors includes Emacs in 2000 lines of C. I'm guessing 2000 bytes will be more than enough for a very basic text editor in most languages. \$\endgroup\$ – trichoplax Jan 7 '16 at 1:22
  • 3
    \$\begingroup\$ I recommend doing this as a code-golf challenge, an upper limit just discourages the use languages where you are not sure whether you make it under that limit. Then also please make precise requirements, my suggestion: accept filename via stdin, file should contain printable ascii characters only, display blinking(or static) cursor, display should have a certain width (given number of characters) and enforces line breaks if the lines are longer, navigation via arrows, enable backspace (and if you want delete) \$\endgroup\$ – flawr Jan 7 '16 at 21:13
3
\$\begingroup\$

Stitch a Picture

A few weeks ago, I asked Stitch a picture. Since then:

  • The question has received several upvotes and no downvotes - hopefully an indication that the community thinks this is as interesting as I do
  • No complete answers
  • Several interesting comments - in particular this one from @bazzargh

In short it looks like this question is a lot harder than I though it would be. It turns out from @bazzargh's comment that I have stumbled into an area of current research, and that perfect solutions are not so easily attainable as I had assumed.

With that in mind, I think its time I took this back to the sandbox to make this into the decent question that I think the subject deserves - and I think I need some community help with that.

I am posting several possibilities I am considering as comments. Vote for these comments as you feel appropriate, and/or add your own suggestions.


I'm going to Yosemite this weekend (woohoo!) so will probably pick this up again next week.

Update

I have relinquished control of this question by putting it in Secret Santa's Sandbox.

\$\endgroup\$
  • 2
    \$\begingroup\$ @Will pointed out that padding the original picture with black boundaries possibly makes the problem harder. Instead we can have the original picture be cropped down to the nearest 100x100 pixel multiple and not worry about black boundaries at all \$\endgroup\$ – Digital Trauma Oct 24 '14 at 17:49
  • 4
    \$\begingroup\$ @MartinBüttner suggested turning this into a code-challenge and scoring based on the number of correctly placed tiles. Given that perfect solutions appear to be hard to come by in general, this is probably a better scoring criteria \$\endgroup\$ – Digital Trauma Oct 24 '14 at 17:50
  • 4
    \$\begingroup\$ Briefly reviewing the paper cited in @bazzargh's comment I see that my problem is even more complex, in that the tiles are also randomly rotated. Since this is complicating the problem beyond current research, I think it would be good to remove the rotation part completely. \$\endgroup\$ – Digital Trauma Oct 24 '14 at 17:50
  • 5
    \$\begingroup\$ Note that I didn't suggest scoring by correctly placed tiles but by correctly aligned edges. That's a huge difference, and in your version you could basically correctly assemble almost the entire picture, but still get 0 score if the chunk you've assembled correctly is off by a tile (since there's no indication where it goes unless you manage to get W tiles next to or H tiles on top of each other. \$\endgroup\$ – Martin Ender Oct 24 '14 at 23:44
  • \$\begingroup\$ @MartinBüttner Yes, that is a better idea. \$\endgroup\$ – Digital Trauma Oct 24 '14 at 23:46
  • \$\begingroup\$ @DigitalTrauma I suggest only allowing translation (no rotation) of the tiles, which simplifies it somewhat, but I suspect still difficult enough to be a challenge. \$\endgroup\$ – flawr Jan 8 '16 at 17:23
  • \$\begingroup\$ Taken codegolf.meta.stackexchange.com/questions/2140/… \$\endgroup\$ – Christopher Jun 5 '17 at 23:20
3
\$\begingroup\$

Addition of doubles... without doubles

For this challenge, you must write a GOLF assembly program that takes two IEEE 754 double-precision numbers and returns their sum.

The Format

IEEE 754 doubles use 8 bytes to store a floating-point value. The memory is laid out like this:

(Wikipedia)

For the purposes of this challenge, all numbers will be in big-endian, and you won't have to worry about overflows or underflows. Addition works roughly like this (I won't go into all of the details):

  1. Align the two numbers to a common exponent.
  2. Add the fractional parts, taking into account the sign.
  3. If the addition overflows, then change the exponent to match.

I/O

Your program will receive 16 bytes of input. The first 8 represent the (big-endian) first number, and the rest represent the second number. Your program will return 8 bytes representing the sum of the two.

Rules

  • This is , so the program that completes the task with the least cycles wins.
  • The score of an answer is the mean number of cycles required for adding uniformly distributed numbers in [-10^64, 10^64].
  • You must test with at least 2500 trials.
  • Your code doesn't have to handle infinities/NaNs.
  • Your GOLF binary (after assembling) must fit in 4096 bytes.

Meta Questions

  • Do I have too many/too few trials?
  • Is there something that I overlooked?
  • Is there a more fitting title?
  • How much explanation should I provide? I don't want this question to turn into a Wikipedia article, but questions requiring external resources are generally frowned upon.
  • Is dead?
\$\endgroup\$
3
\$\begingroup\$

HTML Obfuscation

Write a program or function that takes HTML as a string as input and outputs "obfuscated" HTML. Leave the text between the <s and >s unchanged, but escape all other text.

  • You can assume that the < and > characters will only be used to open/close HTML tags.
  • You can safely leave any text between these characters alone. However, any text not between those characters should take on the form <ampersand><pound><ascii-encoding><semi-colon>.
  • You do NOT have to support self closing tags.

Test cases:

Input:

<div>Hello World</div>

Output:

<div>&#72;&#101;&#108;&#108;&#111;&#32;&#87;&#111;&#114;&#108;&#100;</div>

Input:

ABC<input type="text">DEF<div>

Output:

&#65;&#66;&#67;<input type="text">&#68;&#69;&#70;<div>

Note: it's ok that the HTML is invalid

Input:

eee<div data-bracket=">">eee

Output:

&#101;&#101;&#101;<div data-bracket=">&#34;&#62;&#101;&#101;&#101;

Note: here your program would mess up the HTML. That's ok for the purposes of the challenge.

This is code golf, so the shortest program wins.

\$\endgroup\$
  • \$\begingroup\$ I think you should be more specific about what exact subset of HTML needs to be handled correctly (and include test cases that cover all of it). \$\endgroup\$ – Martin Ender Feb 12 '16 at 15:24
  • \$\begingroup\$ @MartinBüttner thanks for the feedback. Do you think the edits clarify the challenge? \$\endgroup\$ – sudo rm -rf slash Feb 12 '16 at 15:43
  • 1
    \$\begingroup\$ Basically: take a character and return the hexadecimal HTML entity. \$\endgroup\$ – Ismael Miguel Feb 13 '16 at 20:08
3
\$\begingroup\$

Play Flippy Bit

There's a simple game called "Flippy Bit and the Attack of the Hexadecimals from Base 16", originally made as an April Fool's prank in 2014.

The premise is simple: Enemies enter the field from the top. Each one has a hexadecimal number, and are destroyed when the player's binary number matches. For example, an enemy with number 2Ah = 00101010b would be destroyed as soon as the user's number is 00101010. Of course, enemies can only be destroyed after they enter the screen.

The player manipulates their binary number by flipping individual bits with the qwertyui keys, where q is the most significant bit. Each press flips the bit at that location. Therefore, the 2A enemy above will explode if, starting from 0, the player presses etu in any order. When an enemy explodes, the player's number is reset to 0.

Challenge

Given a list of enemies, determine a sequence of keypresses that can destroy all enemies in the order given. This isn't as simple as it seems: if you're trying to destroy 3 but there's another enemy called 2 on the board, you'll need to press i before u. Your algorithm must terminate within a bounded time.

Input

A list of strings of hex digits 0123456789ABCDEF, with each string 1 or 2 digits long, and where the 2-digit strings have no leading zero. You may also take the input in a reasonable format other than a list; for example, newline-separated. The input will always represent a solvable configuration.

Output

A string representing the sequence of keypresses.

Test cases

Note that there are multiple possible outputs for most inputs.

2A 01 02 04 08 10 20 40 A0 88
quetqwertyui

[add more test cases]

Verify your solutions with the following Python:

[add verification code]

This is , so the shortest solution in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ This may or may not be an excuse to award a bounty to the highest Flippy Bit score. \$\endgroup\$ – lirtosiast Jan 20 '16 at 18:13
  • 3
    \$\begingroup\$ I had no idea that the qwertyui keys would flip the bits. This would actually make kind of a cool esoteric language, however. \$\endgroup\$ – Conor O'Brien Jan 21 '16 at 3:49
  • \$\begingroup\$ The statement that "destroy[ing] all enemies in order ... isn't as simple as it seems" puzzled me for a while, because I couldn't see what was wrong with the simple approach of setting the bits from the least significant to the most significant. Having thought about it, I presume that what's missing is a statement that the order in question is the order in which the enemies are presented in the input. But then an input like 03 01 02 is impossible to solve, so you also need to address insoluble inputs. \$\endgroup\$ – Peter Taylor Jan 25 '16 at 12:15
  • \$\begingroup\$ @PeterTaylor Actually, it's not! quiq. The point of this is some sort of search. \$\endgroup\$ – lirtosiast Jan 25 '16 at 14:58
  • \$\begingroup\$ ff 01 02 04 08 10 20 40 80 then. (Although I see you've addressed the issue, so this comment is only for completeness). \$\endgroup\$ – Peter Taylor Jan 25 '16 at 16:06
3
\$\begingroup\$

Radiation-Protected Expressions

Challenge

Write a program, taking an integer n as input from -999,999 to 999,999 inclusive, that returns a string representing a valid expression evaluating to that number in your language. The catch: this expression must NOT evaluate to any other number when evaluated if any single character is removed from it.

Restrictions

Your program must be <= 1024 bytes in length.

The outputted expressions must be in the same language as the generating program.

Scoring

Your score is the number of bytes in the largest string generated by your program for the entire range of valid numbers. Tiebreakers go to shortest code.

Examples of Valid Outputs (in JavaScript)

  • Math.PI|0||3 for n=3, because:

    • ath.PI|0||3, Mth.PI|0||3, Mah.PI|0||3, and Mat.PI|0||3 cause ReferenceErrors,

    • MathPI|0||3 causes a ReferenceError,

    • Math.P|0||3, Math.I|0||3, and Math.PI0||3 result in 3,

    • Math.PI|||3 causes a SyntaxError,

    • Math.PI|0|3 results in 3, and

    • Math.PI|0|| causes a SyntaxError.


  • 9*(8) is valid for n=72

  • (n=9e5)>96?n:9e5 for n=900,000

  • 1 for n=1


Examples of Invalid Outputs (in JavaScript)

  • 1e2 for n=100 because 12 is a valid expression that evaluates to a number other than 100.
\$\endgroup\$
  • \$\begingroup\$ "cause an error or continue to evaluate". Those are two very different things, I'd say to just pick that the expression should continue to evaluate \$\endgroup\$ – Downgoat Feb 27 '16 at 0:38
  • \$\begingroup\$ @Downgoat My intent was that the expression could do anything except evaluate to a different number in the range. I thought it would make the challenge more approachable in different languages to allow errors. \$\endgroup\$ – jrich Feb 27 '16 at 1:02
  • \$\begingroup\$ I get 0 for Math.P|0. \$\endgroup\$ – feersum Feb 27 '16 at 5:37
  • \$\begingroup\$ @feersum Whoops, typed this too quickly. Fixed \$\endgroup\$ – jrich Feb 27 '16 at 16:09
  • \$\begingroup\$ For a lot of languages this probably boils down to one or two special cases and the rest of them are max(expr,expr) for numbers greater than 9, min(expr,expr) for numbers less than 0. So it's borderline dupe of this. \$\endgroup\$ – Peter Taylor Mar 1 '16 at 15:58
  • \$\begingroup\$ @PeterTaylor True. Didn't think of that approach. In this case there would be incentive to golf the code to only employ the strategies necessary to achieve the minimal score, so it's not a complete dupe, but I'm not sure that the challenge in its current form is as interesting as I initially thought... \$\endgroup\$ – jrich Mar 1 '16 at 23:45
3
\$\begingroup\$

Output the points of this twisting fractal

Challenge

Output the points (in order) for the following fractal of size n:

Size 4 example

(The above example is for n = 4)

We begin with the Binary Sierpinski Triangle, which can be generated recursively, by a number of cellular automata (including Rule 90), and by Pascal's Triangle.

As a refresher, Pascal's triangle is:

   |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7| 
---+----+----+----+----+----+----+----+---+
 0 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0|
 1 |  1 |  1 |  0 |  0 |  0 |  0 |  0 |  0| 
 2 |  1 |  2 |  1 |  0 |  0 |  0 |  0 |  0|
 3 |  1 |  3 |  3 |  1 |  0 |  0 |  0 |  0|
 4 |  1 |  4 |  6 |  4 |  1 |  0 |  0 |  0|
 5 |  1 |  5 | 10 | 10 |  5 |  1 |  0 |  0|
 6 |  1 |  6 | 15 | 20 | 15 |  6 |  1 |  0|
 7 |  1 |  7 | 21 | 35 | 35 | 21 |  7 |  1|

Here rows are i, columns are j, and the values are i choose j.

Using Pascal's triangle, we replace each value with its remainder mod 2 to get:

   |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7| 
---+----+----+----+----+----+----+----+---+
 0 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0|     O        
 1 |  1 |  1 |  0 |  0 |  0 |  0 |  0 |  0|     OO       
 2 |  1 |  0 |  1 |  0 |  0 |  0 |  0 |  0|     O O      
 3 |  1 |  1 |  1 |  1 |  0 |  0 |  0 |  0|     OOOO     
 4 |  1 |  0 |  0 |  0 |  1 |  0 |  0 |  0|     O   O    
 5 |  1 |  1 |  0 |  0 |  1 |  1 |  0 |  0|     OO  OO   
 6 |  1 |  0 |  1 |  0 |  1 |  0 |  1 |  0|     O O O O  
 7 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1|     OOOOOOOO 

With the result "plotted" to the right, the n = 1 iteration of the Sierpinski Triangle.

Now, to keep the "centers" well defined, we take the center of each triangle to be its NE corner like so:

'              ^
''             |
'*'            N 
''''       <--E W-->
'  *'          S
''  ''         |
'*' '*'        v
''''''''  

Here is pseudocode to generate the fractal:

fractal(n):
    position = nth center
    while SE possible:
        go SE
        mark position
    while not all full:
        if current level not full:
            rotate counterclockwise on current level
            mark position
        else:
            go NW until reach non-full level
            rotate counterclockwise on current level
            while SE possible:
                mark position
                go SE
    return marked positions

Here's what that looks like for n = 2:

 '                              
 ' '                            
 ' 12'                          
 ' ' ' '                        
 '      9'                      
 ' '     ' '                    
 ' 10'   ' 11'                  
 ' ' ' ' ' ' ' '                
 '               '              
 ' '             ' '            
 '  4'           '  8'          
 ' ' ' '         ' ' ' '        
 '      1'       '      5'      
 ' '     ' '     ' '     ' '    
 '  2'   '  3'   '  6'   '  7'  
 ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '

Giving the following points marked (in order):

[[3, 12], [1, 14], [5, 14], [1, 10], [11, 12], [9, 14], [13, 14], [9, 10], [3, 4], [1, 6], [5,6], [1,2]] 

Rules

  • Entry may be either a function or full program.
  • Input is a non-negative integer.
  • Output is the (properly ordered) list of points for the fractal above.
  • You may use something other than a list to output the results if it allows the easy reading of the points, in order. For example, newline separated is fine.
  • Output must contain exactly (3^n - 3)/2 points.
  • This is code golf so shortest wins!

Questions

  • Is everything well defined?
  • Should I reformat the ASCII triangles? Or even replace everything with images?

Test cases if anyone is interested or I post this.

This is a challenge that I enjoyed solving so I hope I can smooth out the corners relatively quickly.

\$\endgroup\$
  • \$\begingroup\$ I don't quite understand what the diagram with the ' and * represents. Would it be possible to explain the construction without having to read pseudocode? \$\endgroup\$ – Martin Ender Mar 13 '16 at 13:46
  • \$\begingroup\$ @MartinBüttner I believe so. I considered making a better animation but hoped it would be clear without one. The options I see are: animation, representative list of steps, or general improvement/refactoring of what I have so far. What do you think? \$\endgroup\$ – Michael Klein Mar 13 '16 at 20:58
  • \$\begingroup\$ Related: codegolf.stackexchange.com/questions/66875/… \$\endgroup\$ – Michael Klein Mar 30 '16 at 9:55
  • \$\begingroup\$ I've been playing with this one recently, have a gif: gifyu.com/image/pumE \$\endgroup\$ – Michael Klein Dec 10 '17 at 19:31
3
\$\begingroup\$

Replace magic numbers

Tags:

Introduction

Magic numbers are a common problem in software development, since they tend to make software hard to maintain. Best practise is to use named constants instead of raw numbers in the source code. In this challenge you have to clean up some code that makes extensive use of magic numbers.

The Challenge

Given a piece of code, replace every number that is not 0, 1 or 2 with named constants. If you encounter a number that you already created a constant for, use the existing constant instead of adding another one. The replacement is done by replacing the number with an uppercase letter [A-Z] and prepending an assignment in the form of A=5 to the initial input.

Example

x=input()
if x == 2:
    print 42
elif x == 1337:
    print 666
print 42

becomes

C=666
B=1337
A=42
x=input()
if x == 2:
    print A
elif x == B:
    print C
print A

Notes

  • The order of the assinments that get prepended to the input does not matter.
  • The order of replacements does not matter as well. You don't have to replace the first magic number with an A for example.
  • You may take the input as a list of strings instead of a multiline string.
  • You will never have to use more than 26 constants.
  • A number that has to be replaced matches the regex [0-9]{2,}|[3-9].

Rules

Happy Coding!

\$\endgroup\$
  • 2
    \$\begingroup\$ Cases to consider - 5.3, 0x30, a12 (simple replacement would corrupt the code), A (already existing in the code), 04 (same as 4 or not)? \$\endgroup\$ – ugoren Apr 25 '16 at 7:15
  • 1
    \$\begingroup\$ Also, your regex implies that 1337 does't need to be replaced. \$\endgroup\$ – ugoren Apr 25 '16 at 7:16
  • \$\begingroup\$ @ugoren Yea that regex is definetly wrong. Gonna correct this and also add clarifications for the edge cases. \$\endgroup\$ – Denker Apr 25 '16 at 10:13
3
\$\begingroup\$

Word Squares

Create a function or program that given a list of words and size n as arguments or standard input, outputs a word square with dimensions n by n. The output can be either formatted in a similar shape to a word square, or as a list of the words used in order by rows from the top and then by columns from the right.

Explanation

Word squares are a grid of letters that form words when read horizontally and vertically. The size of the square refers to the number of letters in each word.

Example

This is a size 5 word square. The words formed by each row are heart, ember, abuse, resin, and trend. In this example, the same words are formed by each column, but this is not a necessary condition.

H E A R T
E M B E R
A B U S E
R E S I N
T R E N D

Another example is this word square with size 4. The words formed by each row in this case are different from the words formed by each column.

L A C K
I R O N
M E R E
B A K E

Rules

  • This is so the shortest solution wins.
  • Builtins that solve this and the standard loopholes are not allowed.
  • The words must be from this dictionary. You can take the filename of the dictionary or the contents as input or as an argument. (Recommend a dictionary here that consists of only English alphabet letters, in all lowercase or all uppercase.)
  • If no such word square can be found using the given dictionary, no output or a false (or falsey) value can be returned.

Test Case

n = 4, dictionary = ...
L A C K
I R O N
M E R E
B A K E
-- or --
LACK
IRON
MERE
BAKE
-- or --
["lack", "iron", "mere", "bake", "limb", "area", "cork", "knee"]
-- or --
[["lack", "iron", "mere", "bake"], ["limb", "area", "cork", "knee"]]
-- or --
Similar to the above but with swapped cases.
The case is not important as long as it remains consistent.
\$\endgroup\$
  • \$\begingroup\$ Nice one. Plus 1. \$\endgroup\$ – Arjun May 8 '16 at 22:07
  • \$\begingroup\$ I don't think it's necessary to mention the standard loopholes, but if you do I'd recommend making that a link. \$\endgroup\$ – trichoplax May 9 '16 at 13:19
  • \$\begingroup\$ @trichoplax Yeah but it's more for informing new visitors of standard rules for code-golf. I do agree an actual link to the meta post would be more beneficial since a new visitor may not find it. \$\endgroup\$ – miles May 9 '16 at 16:01
  • \$\begingroup\$ May a word square contain a word multiple times as horizontally or vertically? Will all words in the dictionary have the right length? \$\endgroup\$ – xnor May 16 '16 at 10:05
  • \$\begingroup\$ @xnor I think the dictionary input should only contain words with length n matching the input size. As for repeating words, I don't see any reason to add it as an additional constraint as it's not a rule for standard word squares. \$\endgroup\$ – miles May 16 '16 at 20:41
3
\$\begingroup\$

Draw the Cool S

Given a number n≥3, print or output the Cool S made with n vertical bars. The outputs for 3,4,5,6 are:

  / \
 /   \
|  |  |
|  |  |
 \  \/
 /\  \
|  |  |
|  |  |
 \   /
  \ /

    /\
   /  \
  /    \
 /  /\  \
|  |  |  |
|  |  |  |
|  |  |  |
 \  \  \/
 /\  \  \
|  |  |  |
|  |  |  |
|  |  |  |
 \  \/  /
  \    /
   \  /
    \/

     / \
    /   \
   /     \
  /  / \  \
 /  /   \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \  \  \/
 /\  \  \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \   /  /
  \  \ /  /
   \     /
    \   /
     \ /

       /\
      /  \
     /    \
    /  /\  \
   /  /  \  \
  /  /    \  \
 /  /  /\  \  \
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
 \  \  \  \  \/
 /\  \  \  \  \
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
 \  \  \/  /  /
  \  \    /  /
   \  \  /  /
    \  \/  /
     \    /
      \  /
       \/

Any invisible whitespace is optional (trailing spaces and trailing/leading newlines).

How to draw the Cool S

Draw the Cool S just like you've done since childhood, except the number of vertical bars can be more than 3.

enter image description here

  • Draw two rows of vertical bars.
  • Connect them with slanted lines, tucking away the two remaining bars.
  • Pair of the bars with slanted lines at the top and bottom.

Here's how we do this for ASCII art. Let's look at n=5.

A row has n vertical bars with two spaces between them

|  |  |  |  |

Draw two groups of n-1 rows, leaving two empty lines between them

|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |


|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |

Connect each top bar to the bottom bar one position right with a slanted line of two \, then close off the two unused bars with a /.

|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \  \  \/
 /\  \  \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |

Complete the S on the top and bottom by drawing lines sloping inwards that meet at the center. When n is odd, a gap of one space is left and the center bar isn't used.

     / \
    /   \
   /     \
  /  / \  \
 /  /   \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \  \  \/
 /\  \  \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \   /  /
  \  \ /  /
   \     /
    \   /
     \ /

Spun off from this Sandboxed challenge by Beta Decay.

\$\endgroup\$
  • 1
    \$\begingroup\$ Golfing my childhood \$\endgroup\$ – Alex A. May 13 '16 at 22:40
  • \$\begingroup\$ I've never drawn a "Cool S", whether in my childhood or since. Does that mean that I'm disqualified from answering this question? \$\endgroup\$ – Peter Taylor May 14 '16 at 19:19
3
\$\begingroup\$

Strip Iterated Prisoner's Dilemma

Inspired by https://xkcd.com/696/, of course.

The Prisoner's Dilemma is a classic game (more in the game theory sense than the family fun sense) where two agents - two accomplices to a crime, in the original formulation - must choose whether to sell out the other.

If each player chooses not to betray the other, both win. If one player chooses treachery and the other does not, it wins, but if both betray each other, neither wins. The "iterated" variation is where the game is played multiple times with the same players, and both players know all the decisions each player has made in the past.

Of course, that's all a bit dull, and has been done before besides. We're going to tart it up a bit.

(Unfortunately due to the nature of the test all solutions must be in the same language, and one that supports executing strings. I've chosen Python 3, since it's my favorite and I have to write the runner.)

The Game:

Submit a program - specifically a Python 3 function - that plays Iterated Prisoner's Dilemma against another such program. If both functions betray each other, each one gets one character deleted from the end of its source code. If one function betrays the other, the betrayed function gets two characters deleted from the end of it, and the traitor gets a # appended to it, immunizing it against one future loss. If neither turns traitor, both go unharmed. Functions will be restored to their original text between each contest with a new opponent.

Submissions are scored based on failure rate and length; specifically, score = round( (number_of_trials_failed / total_number_of_trials) * ( length / 2 ) ). The submission with the lowest score wins.

The length of a submission is the number of non-whitespace characters in the submission. Comments are not counted, but are also removed before the contest begins, so a commented out "guard" at the end will not protect your code from deletions. Length also does not count the function specifier (the def submission(y, o, t): which should not be included in your submission text anyway.)

Your function will be called with three parameters, y (your history), o(opponent's history), and t (text of the opponent itself). t is the very same text that the game runner will execute as your function's opponent, which you may analyze or otherwise use to run simulations. It will then return True if it wishes to betray its opponent or False if it does not.

Every possible 2-combination of submissions will be contested against each other - including each submission against itself. Each contest consists of 2,500 trials.

Other Rules:

  • All submissions must be in Python 3. (Specifically, they should run under Python 3.4.4)

  • The submission text must be the only code that is run to produce the result; you may not import any libraries, ask for user input, read from /dev/urandom/or equivalent, and of course you can't pull results from some webserver (which is already a violation of the standard loophole rules.) You MAY execute the given opponent text, and of course you're allowed to call all the builtins.

  • The submission must terminate and return an answer within 1 second (this will be run on a 12GB i7 gaming computer, so this should be plenty of time).

  • A submission that emits an uncaught exception or returns an invalid value loses that round.

  • Submissions that do not return in one second or less are immediately disqualified.

  • Submissions will be closed on [date posted + 8 days] and programmatically judged, results will be appended to the challenge. There will be a "trial run" in the evening of [date posted + 4 days].

API:

The "submission text" is valid, 4-space-indented Python 3 source code that will have the function specifier line def submission(y, o, t):\n appended to the beginning and a single 4-space-indent added to the beginning of each line. So:

if len(y) == 0: return False
else: return (not y[-1])

...is run as...

def submission(y, o, t):
   if len(y) == 0: return False
   else: return (not y[-1])

The function should return True to betray its opponent or False to trust its opponent. Returning any other value (such as if your return statement has been deleted and you return None`) is an error and will result in an automatic loss of that round.

o is a list of True-es or False-es, representing the opponent's previous moves when playing against you; o[n] equals the decision your opponent made in round n, and of course this list will be empty in the first trial. y is similar except it's your previous moves. t is the text of the opponent submission, formatted as specified above.

This is the program that will perform the contest:

[said code here]

Example Submissions: These will also be included in the actual contest.

Chronic Villain Syndrome:

#always choose 'betray'
return True
11111111 #padding

The Patsy:

#always choose 'trust'
return False
11111111 #padding

Do Onto Others...:

#always choose what opponent chose last round
if o:
   return o[-1]
return True

Professor X:

me="""
#Read opponent's mind and choose optimally.
exec("def e(y, o, t):\n"+t)
return False e(o, y, me)
#Opponent's choice this turn if we betray...
tb = e(o,y+[True], me)
#if we trust...
tt = e(o,y+[False], me)

#Opponents choice NEXT turn if we betray then betray...
tbb = e(o+[tb], y+[True], me)
#... betray then trust...
tbt = e(o+[tb], y+[False], me)
#... trust then betray...
ttb = e(o+[tt], y+[True], me)
#... trust then trust...
ttt = e(o+[tt], y+[False], me)

#Maps (your_choice,opponent_choice) to desirability
#Betrayed = -2, mutual betrayal = -1,
#mutual cooperation = 1, betray opp. = 2
v = {(False, True): -2, (True, True): -1,
     (False, False): 1, (True, False): 2}
#Best outcome next turn of trusting now
ftv = max(v[ttt], v[ttb])
#... of betraying now
fbv = max(v[tbt], v[tbb])
#value of betraying now
bv = v[tb] + fbv
#... of trusting now
tb = b[tt] + ftv

#Tuple comparison is done l to r, so
#this returns True if tv >= bv,
#False if bv > tv.
return max( (bv, True), (tv, False) )
"""
exec(me)

(p.s. this one gets disqualified every time - why is left as an exercise to the reader)

\$\endgroup\$
  • \$\begingroup\$ So this is a KOTH? \$\endgroup\$ – Rɪᴋᴇʀ May 13 '16 at 22:07
  • \$\begingroup\$ And why is the professor X bot disqualified? \$\endgroup\$ – Rɪᴋᴇʀ May 13 '16 at 22:10
  • \$\begingroup\$ Finally, should there be a rule against running the opponents code to pick the best output for yourself? \$\endgroup\$ – Rɪᴋᴇʀ May 13 '16 at 22:12
  • \$\begingroup\$ It's a KOTH, yes, with a little bit of golf mixed in. "Professor X" gets disqualified because it will eventually play against itself, which means unbounded recursion, which means never halting and thus getting kicked out by the "must return in one second" rule. So any bot that tries to run its opponent is going to have to at least have some way of stopping its opponent from running it without corrupting the answer. All in all that kind of "mind reading" is cool enough and easy enough to defeat that I think it should be left in. \$\endgroup\$ – Schilcote May 14 '16 at 1:26
  • \$\begingroup\$ Modified quines aren't hard, and neither are narcissist programs. I think you should add a rule against that. I'll see if I can create a bot like that. \$\endgroup\$ – Rɪᴋᴇʀ May 14 '16 at 2:03
  • \$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ Right, but it should be pretty easy to pull stuff like having side effects (store something in a global for example) or unwinding the stack to see who your caller is. \$\endgroup\$ – Schilcote May 14 '16 at 2:41
  • \$\begingroup\$ Can't you do something like this? Wouldn't that almost always win? \$\endgroup\$ – Rɪᴋᴇʀ May 14 '16 at 3:23
  • \$\begingroup\$ @No, for a few reasons; one, there'd probably be other "mind reader" variations (that's the whole reason Professor X is in there) which means you'd have to check for ALL of them, which would mean a massive character count. For another, I can think of at least two ways (stack unwinding & using globals to check for two calls that are given same sized y) to check if your opponent has done that and alter your decision accordingly. I don't want to make "mind readers" impossible, I just want to put interesting challenges in their way, and I think this ruleset does that. \$\endgroup\$ – Schilcote May 14 '16 at 17:33
  • \$\begingroup\$ @Shilcote okay, forgot that more mind readers could exist. \$\endgroup\$ – Rɪᴋᴇʀ May 14 '16 at 18:14
  • \$\begingroup\$ What does number_of_trials_failed mean? The number where you were disqualified? And why 4-space-indented? That guarantees that when you lose a space from the indentation you will lose the next three rounds due to parse errors. \$\endgroup\$ – Peter Taylor May 14 '16 at 19:14
  • \$\begingroup\$ @PeterTaylor No, when you're disqualified you're totally out, you don't even get a score. number_of_trials_failed is the number of times you got betrayed and lost. Good thought on the indentation; maybe it should delete one non-whitespace character? Or better yet, one statement? \$\endgroup\$ – Schilcote May 15 '16 at 0:29
  • \$\begingroup\$ This is likely going to be a one-up challenge. Given a set of programs, you'd always be able to write another program that beats all previously existing programs. \$\endgroup\$ – Nathan Merrill May 16 '16 at 18:37
  • \$\begingroup\$ I'm sure there'll be a lot of that, but I don't think it'll be exclusively that... \$\endgroup\$ – Schilcote May 17 '16 at 1:10
3
\$\begingroup\$

Do my algebra homework for me!

Inspired by a true story

Ugh, my maths teacher gave me so much homework on quadratics.

Two whole worksheets, filled with equations like Expand (x+1)(x-6) and Factorize x^2-2x+1. I already hate it.

Suddenly, a lightbulb appeared out of nowhere, and landed about five centimetres above my head.

A stroke of thought went through me: Why not write a piece of code down instead of all those stupid answers? It would save me tons of time!

So here's the task: Make an algebra solver for me! To save my hand from breaking, the code needs to be as short as possible.

Instructions:

  • Given an input in the form expand/factorize equation, return the algebraic equation:
    • Expanded, if the keyword (the first word) is expand (e.g. expand (x+1)(x+6) would return x^2+7x+6), or
    • Factorized, if the keyword is factorize (e.g. factorize x^2+9x+14 would return (x+2)(x+7).
  • The equation will be quadratic, in the form ax^2+bx+c or (x+d)(x+e) (a to e are all placeholders, while x is the variable - the variable can be any letter from a to z - so an equation like expand (a+3)(b+6) would still hold).
  • With an expansion equation that contains two or more unknowns (e.g. expand (a+3)(b+6)), place the letters in the summands with two or more letters in alphabetical order, and place the remaining summands in alphabetical order (so the previous example would equal ab+6a+3b+18).

This is code-golf, so shortest code in bytes wins. Good luck!

Meta

  • Any dupes?
  • I probably need a better title. Any suggestions?
\$\endgroup\$
3
\$\begingroup\$

Capture the Flag

Do you ever wonder why we're here?

Objective

Capture the enemy team's flag and return it to your base. The first team to 3 captures wins the round. The player with the most wins across all (number TBD) rounds wins the game.

Teams

There will be two teams each round. Teams will be randomly, evenly assigned to all submissions at the start of each round.

Playing

The game will be turn-based. At the start of each turn, each player will be given the current map. All players will move simultaneously. Players shall submit their move as a one or two character ASCII string, composed from the following options:

  • First character: wait, move, stab (if not holding flag), drop (if holding flag), or pick-up (if standing on a flag)
  • Second character: north, east, south, or west, or nothing if waiting, dropping, or picking-up

Moving a direction will result in the player moving one square in that direction if possible, otherwise standing still (for example, if the player is attempting to move into a wall, or into an occupied square). Stabbing in a direction will result in killing the player standing in the adjacent square in that direction, unless the player is a teammate (no teamkilling). Stabs are processed before moves each turn. Dropping the flag results in it being placed on the ground beneath the player. Drop, pick-up, and wait commands ignore the second character. Invalid commands are interpreted as waiting. Case is ignored, so W and w are the same command. Either team may pick up either flag.

If two or more players attempt to move onto the same square, one of the players will be randomly selected to successfully move, and the rest will not move.

If a player is killed, they will drop the flag they are holding (if they are holding one), and will respawn in 3 turns in an unoccupied square in their home base. If there is no unoccupied square in their home base, they will respawn in the nearest square to the base. Respawns happen after stabs, but before moves.

Inside each base, there will be a 5x5 square room, with doorways in the middle of each wall, and the team's flag in the center of the room. Players who spend 5 consecutive turns inside their team's flag room (this includes the 4 doorways), while no enemies are present in the flag room and they are not holding a flag, will be killed at the conclusion of the 5th turn, to discourage camping. Successfully placing the enemy's flag on top of your flag's stand (in the center of the room), either by dropping it or being killed on top of the flag stand, will result in a point being scored for your team and the enemy's flag immediately returning to their flag stand.

The Map

(work in progress)

The world map will be a single level (no upstairs or downstairs), represented as such:

# : wall, cannot be moved into
. : an empty space
F : the enemy team's flag
f : your flag
! : a flag stand (with no flag on it)
@ : you
$ : you, carrying the enemy flag
% : you, carrying your flag
p : one of your teammates
P : an enemy player
c : a teammate, carrying or standing on top of the enemy flag
C : an enemy player, carrying or standing on top of your flag
s : a teammate, carrying or standing on top of your flag
S : an enemy player, carrying or standing on top of the enemy flag

Here is an example map (the actual maps used in the tournament will be posted later):

####################################################
#..................................................#
#..###.###########.######........###......##########
#..#....................#..........................#
#..#.....###.###...................#######.........#
#..#.....#.....#........#..........................#
#..#.....#.....#........#...................#...#..#
#..#........f...........#..........................#
#........#.....#........#....#########.............#
#..#.....#.....#........#..........................#
#..#.....###.###........#......##################..#
#..#...............................................#
#..#.#################.............................#
#.........................###########.........###..#
#..................................................#
####################################...............#
####################################...............#
#..................................................#
#..................................................#
#...............####################################
#...............####################################
#..................................................#
#..###.........###########.........................#
#.............................#################.#..#
#...............................................#..#
#..##################......#........###.###.....#..#
#..........................#........#.....#.....#..#
#.............#########....#........#.....#........#
#..........................#...........F........#..#
#..#...#...................#........#.....#.....#..#
#..........................#........#.....#.....#..#
#.........#######...................###.###.....#..#
#..........................#....................#..#
##########......###........######.###########.###..#
#..................................................#
####################################################

Controller

The controller and an example map and player are located on the challenge's GitHub project. Once I finish the controller, I'll copy the program here.

Restrictions

  • Bots must be fully deterministic. RNGs may not be used.
  • Bots may be written in any language, so long as they support reading ASCII input from STDIN and writing ASCII output to STDOUT. Anything that is written to STDERR will be ignored.
  • Bots' processes will be started at the beginning of each turn, and must output their command and terminate within the given 5 seconds.
  • Each bot will be able to store up to 1 MiB (1024*1024 bytes) of data on disk per game, for saving any stateful data they desire. The name of the bot's data file will be passed as the first command line argument to the bot process. Should a bot write more than 1 MiB of data during a single game, data from the beginning of the file will be removed to append additional data to the end of the file. At the end of each game, the data files will be wiped.
  • Any attempt to tinker with the controller, runtime or other submissions will be disqualified. All submissions should only work with the inputs and storage they are given.
  • Bots should not be written to beat or support specific other bots.

Sandbox notes

Anything missing or unclear (other than the parts specifically marked as TBD)?

\$\endgroup\$
  • \$\begingroup\$ 1. The rules make most sense if turns are sequential rather than simultaneous, but it's nowhere stated which is the case. Simultaneous moves are fairer, but make the rules more complicated. Sequential moves make the assessment of what to do more complicated, because unless you track a lot of state from last time you don't know who's already moved. 2. Respawning in an unoccupied square requires there to be an occupied square. What if there isn't? 3. What stops camping just outside the door, in such a way that no-one can pass? \$\endgroup\$ – Peter Taylor Mar 4 '16 at 10:40
  • \$\begingroup\$ @PeterTaylor I've addressed all 3 of these points in the latest edit. \$\endgroup\$ – Mego Mar 4 '16 at 20:41
  • \$\begingroup\$ No RNG? :( That's not as much fun. \$\endgroup\$ – Conor O'Brien Mar 6 '16 at 0:36
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Trust me, you'll be glad for that. Nobody wants a Caboose on their team. \$\endgroup\$ – Mego Mar 9 '16 at 7:00
  • \$\begingroup\$ So they can't stab themselves or take their own flag? \$\endgroup\$ – Rɪᴋᴇʀ Mar 9 '16 at 16:41
  • \$\begingroup\$ @RikerW Correct on the stabbing bit. I can't imagine why a player would want to stab themselves, though. Either team can pick up either flag; I need to fix that. \$\endgroup\$ – Mego Mar 9 '16 at 21:56
  • \$\begingroup\$ @Mego Every heard of EmoWolf? >.< \$\endgroup\$ – Rɪᴋᴇʀ Mar 10 '16 at 0:02
  • \$\begingroup\$ @RikerW That is exactly why suicides are not allowed. A rule is not needed, because that's a standard loophole. \$\endgroup\$ – Mego Mar 10 '16 at 0:03
  • \$\begingroup\$ You should make a rule that submissions can't lose on purpose by sacrificing their own flag \$\endgroup\$ – Rɪᴋᴇʀ Mar 10 '16 at 0:03
  • \$\begingroup\$ You never define what a "base" is. Is it half of the board? \$\endgroup\$ – MegaTom Jun 13 '16 at 15:25
3
\$\begingroup\$

Determine the winner of Beggar my Neighbour

The card game Beggar my Neighbour is boring in that the final outcome is entirely determined by the initial arrangement of the deck, so long as certain rules are followed for the order in which cards are picked up from the playing field and moved to decks.

The Game

  1. Both players are dealt 26 cards.

  2. Players play their top card alternately, starting with the player who won the previous stack or Player 1 at the beginning of the game.

  3. Play is interrupted when either player plays a picture card. In that case their opponent must play a number of cards equal to the value of the picture card above 10, i.e. Jack = 1, Queen = 2, King = 3, Ace = 4. The player then wins all the played cards which are returned to the bottom of their hand, unless the opponent themselves plays a picture card, in which case this rule interrupts their play.

  4. If at any point one of the players needs to draw a card from their deck, but their deck is empty, they immediately lose the game.

Example play

Player 1 starts with 7; Player 2 plays 3; subsequent plays are 9; 9; T; A; 6, J; A; 2, 3, 7, 6: Player 2 adds the cards 7399TA6JA2376 to his deck.
Player 2 starts: J; K; 9, 4, A; 5, 2, J; 2: Player 1 adds the cards JK94A52J2 to his deck.
Player 1 starts: 6; T; T; 5; 9; A; A; 3, K; K; 7, Q; 5, T: Player 1 adds the cards 6TT59AA3KK7Q5T to his deck.

The Challenge

Given two lists of cards in the players' decks, in any convenient format, output a truthy value if Player 1 wins, and a falsey value if Player 2 wins.

For convenience, a 10 card will be represented with a T, and face cards will be abbreviated (Ace -> A, King -> K, Queen -> Q, Jack -> J), so that all cards are one character long. Alternatively, ranks may be represented with decimal integers 2-14 (Jack -> 11, Queen -> 12, King -> 13, Ace -> 14) or hex digits 2-E (10 -> A, Jack -> B, Queen -> C, King -> D, Ace -> E). Since suits don't matter, suit information will not be given.

You may assume that all games will terminate at some point (though it may take a very long time), and one player will always run out of cards before the other.

There are variations for more than two players but they will not be considered here.

\$\endgroup\$
3
\$\begingroup\$

Primitive Pythagorean triples

Introduction

A Pythagorean triple is a tuple of three positive integers a, b and c so that a² + b² = c². One example of that is (3, 4, 5).
One subset of those are primitive Pythagorean triples which require a, b and c to also be coprimes, so their only common divisior is 1. One example is (5, 12, 13)

The Challenge

Given three numbers representing a triple, output a truthy value if there is a triple representation of them that form a primitive Pythagorean triple and a falsy value if not.

Test cases

Truthy

Coming Soon

Falsy

Coming soon

tags:

TODO

  • What about zero as input?
  • Test cases
  • Example for the different triple configurations?
  • What about builtins?
  • More descriptive title
\$\endgroup\$
  • \$\begingroup\$ Unless I'm bad at maths, can't you check for these two conditions totally separately? Since if gcd(a,b,c) = G then we could instead write (Gx)^2 + (Gy)^2 = (Gz)^2 where x,y,z are a,b,c divided by G. Since that doesn't change the equality, wouldn't you just have to check for it being a triple and that they are all coprimes? It's fine if that's what you want (I also may have misunderstood) but it feels... disconnected? \$\endgroup\$ – FryAmTheEggman Jun 15 '16 at 14:11
  • \$\begingroup\$ @FryAmTheEggman, no need to check them all. If a and b have a common factor, it's also a factor of c. So it's a GCD test and a Pythagorean test. @DenkerAffe, "if there is a triple representation of them that form" would be much easier to understand as "if they are". Zero as input is fine: (0, 1, 1) is a (degenerate) primitive Pythagorean triple. I wouldn't worry about built-ins: GCD has been asked before, and a built-in for "Is this a Pythagorean triple" is rather too specific to exist except as a 30-character Mathematica function. \$\endgroup\$ – Peter Taylor Jun 15 '16 at 14:25
  • 1
    \$\begingroup\$ @PeterTaylor You're right, but what I was trying to get at was that the challenge felt like two different tests with an and slapped in the middle. While this isn't exactly a problem (particularly because the primitive triples are actually studied) I was trying to suggest the challenge might be better if it felt more like they were connected. However, I have no idea how to accomplish that... \$\endgroup\$ – FryAmTheEggman Jun 15 '16 at 14:55
  • \$\begingroup\$ Also, here is a test script I wrote, if it helps. It only works on sorted inputs, currently. \$\endgroup\$ – FryAmTheEggman Jun 15 '16 at 14:55
  • \$\begingroup\$ @FryAmTheEggman I definetly see you point. Just read about it and wanted to make a challenge about it ^^. It should be fine, since it not just two random things with an AND between them, but I will think about it. \$\endgroup\$ – Denker Jun 15 '16 at 17:24
  • \$\begingroup\$ @PeterTaylor I agree the wording is a bit off. Will clarify later. Thanks for your other thoughts as well! \$\endgroup\$ – Denker Jun 15 '16 at 17:26
3
\$\begingroup\$

Join the dots without crossing the line


Given a collection of distinct points in the unit square, output the points in order. This can be any order such that a closed polygon formed by straight line segments joining each point to the next (and the last back to the first) has no two lines crossing.

Input

  1. There will be between 4 and 255 points.

  2. Each one is represented by an ordered pair (x, y)

  3. The coordinates will have entries in the range [0, 1), that is 0 <= x < 1

  4. Each entry may have up to 8 decimal places, so the range is 0 to 0.99999999.

  5. You may choose to accept integers instead, in which case the range will be 0 to 99999999.

  6. You may take input in any reasonable format. For example:

    • (0.1, 0.2), (0.3, 0.4), (0.5, 0.7)
    • 10000000 20000000 30000000 40000000 50000000 70000000

Output

The output format need not match the input format as long as both are unambiguous.

Impossible cases

The code does not need to work for impossible cases, such as all points being colinear. Neither does it need to report such cases - it can simply not work. Behaviour is undefined.

Random algorithms

Your code must be deterministic. That is, it must always give the same output for the same input. For this purpose, the same points in a different order will be counted as distinct inputs and need not have the same output.

You may use pseudo random number generators provided the output is still consistent. If this requires setting a seed, that seed must be zero.

Time limit

Your code does not have to be particularly efficient, but it must finish for the 255 point test case in under 5 minutes.

The requirement for the code to be deterministic is so that this time limit can be checked with a single run. If your random number generator of choice cannot give consistent behaviour by default, then you will need to seed it with zero. If a random number generator does not allow for seeding and does not give consistent behaviour then you may not use that generator.

Test cases

[ TO BE ADDED ]

Output verification snippet

[ TO BE ADDED ]

Scoring

This is code golf. Shortest code in bytes wins.


Note that this is not a Traveling Salesman Problem. There is no requirement for the tour to be short, only for it to be non-intersecting.

\$\endgroup\$
  • 1
    \$\begingroup\$ It would be good to be explicit about whether non-deterministic solutions are accepted, and if so then what that means for the time limit. \$\endgroup\$ – Peter Taylor Jun 30 '16 at 9:47
  • 1
    \$\begingroup\$ I think that it would be reasonable to say that RNGs which seed automatically and can't be reseeded with value 0 may not be used. This would mean that e.g. CJam answers have to be deterministic, but there's a perfectly good deterministic approach anyway. (The obvious approach IMO is to find the convex hull, then remove those points and recurse). \$\endgroup\$ – Peter Taylor Jul 1 '16 at 21:04
3
\$\begingroup\$

The Fast and The Fourier

Implement the Discrete Fourier Transform (DFT) for a sequence of any length using a Fast Fourier Transform algorithm (FFT). This may implemented as either a function or a program and the sequence can be given as either an argument or using standard input. A DFT has time complexity of O(n2) whereas a FFT has time complexity of O(n log n).

The algorithm will compute a result based on standard DFT in the forward direction. The input sequence has length n and consists of the complex values {x0, x1, ..., xn-1}. The output sequence will have the same length and consists of {y0, y1, ..., yn-1} is defined by the relation below.

DFT

Bluestein's algorithm

One algorithm that meets these requirements Bluestein's algorithm. It is a special case of the Chirp-Z transform and is able to compute the FFT for a sequence of any length n by transforming it in order to solve it as a cyclic convolution which can be solved with a time complexity of O(n log n).

Keep in mind that it is not required that you only use this algorithm in your implementation. If you know a better way, feel free to use it.

First, an identity is used to rewrite the initial DFT in a form where a convolution can easily be recognized.

Chirp transform

You can obtain two sequences from this new form

Chirp sequences

which allow you to write the DFT as a convolution of two sequences.

Chirp convolve

Sample

Get the input
    x = [1, 2, 3, 4, 5]

Get the length of the input
    n = 5

Compute the 'a' sequence
    a = [1, 1.618 - 1.176j, -2.427 - 1.763j, 3.236 + 2.351j, -4.045 + 2.939j]

Compute the 'b' sequence
    b = [1, 0.809 + 0.588j, -0.809 + 0.588j, 0.809 - 0.588j, -0.809 - 0.588j]

Compute the convolution of 'a' and 'b' (using summation)
    y[0] = (a[0]*b[0] + a[1]*b[1] + a[2]*b[2] + a[3]*b[3] + a[4]*b[4]) / b[0]
         = 15 / 1 = 15

    y[1] = (a[1]*b[0] + a[0]*b[1] + a[2]*b[1] + a[3]*b[2] + a[4]*b[3]) / b[1]
         = (-4.045 + 1.314j) / (0.809 + 0.588j) = -2.5 + 3.441j

    y[2] = (a[2]*b[0] + a[1]*b[1] + a[3]*b[1] + a[0]*b[2] + a[4]*b[2]) / b[2]
         = (1.545 - 2.127j) / (-0.809 + 0.588j) = -2.5 + 0.813j

    y[3] = (a[3]*b[0] + a[2]*b[1] + a[4]*b[1] + a[1]*b[2] + a[0]*b[3]) / b[3]
         = (-2.5 + 0.813j) / (0.809 - 0.588j) = -2.5 - 0.813j

    y[4] = (a[4]*b[1] + a[3]*b[1] + a[2]*b[2] + a[1]*b[3] + a[0]*b[4]) / b[4]
         = 4.253j / (-0.809 - 0.588j) = -2.5 - 3.441j

The Fourier tranform of x
    y = [15, -2.5 + 3.441j, -2.5 + 0.813j, -2.5 - 0.813j, -2.5 - 3.441j]

Rules

  • This is so the shortest solution wins.
  • Builtins that compute FFT in forward or backward (also known as inverse) directions are not allowed.
  • Builtins that compute the convolution are not allowed. (Most will have not been allowed by the previous rule as they use FFT internally.)
  • Your solution must have time complexity of O(n log n) where n is the length of the input sequence.
  • Floating-point inaccuracies will not be counted against you.

Test Cases

FFT([1, 1, 1, 1]) = [4, 0, 0, 0]
FFT([1, 0, 2, 0, 3, 0, 4, 0]) = [10, -2+2j, -2, -2-2j, 10, -2+2j, -2, -2-2j]
FFT([1, 2, 3, 4, 5]) = [15, -2.5+3.44j, -2.5+0.81j, -2.5-0.81j, -2.5-3.44j]
FFT([5-3.28571j, -0.816474-0.837162j, 0.523306-0.303902j, 0.806172-3.69346j, -4.41953+2.59494j, -0.360252+2.59411j, 1.26678+2.93119j] = [2, -3j, 5, -7j, 11, -13j, 17]

Related

  • Compute the Discrete Fourier Transform - This contains some implementations for the standard DFT algorithm which has time complexity O(n2). You'll want to understand how to implement this before trying FFT.
  • Too Fast, Too Fourier: FFT Code Golf - This previous challenge is the precursor to the current challenge here. Before, you only had to consider sequences where the length n was a power of 2 which allowed for simpler recursive implementations. The difference here is that you now have to implement an FFT algorithm that will work for sequences with any length.
\$\endgroup\$
  • \$\begingroup\$ nice choice for the title \$\endgroup\$ – Abr001am May 7 '16 at 20:47
  • \$\begingroup\$ Duplicate? \$\endgroup\$ – Luis Mendo Jun 16 '16 at 7:43
  • \$\begingroup\$ @LuisMendo That challenge is for sequences where the length is a power of two, but this is for sequences of any length. \$\endgroup\$ – miles Jun 16 '16 at 7:48
  • \$\begingroup\$ Oh, sorry then. I suggest you add a link in your challenge explaining the difference. I think many people may get confused as I did. Apart from this, if length is not a power of 2 there's another potential problem: what algorithms count as a FFT? \$\endgroup\$ – Luis Mendo Jun 16 '16 at 7:52
  • \$\begingroup\$ @LuisMendo I had a short snippet stating the difference but I deleted it in my previous edit for some reason. I want it to be so that any FFT algorithm that has a time complexity better than the naive DFT - O(n^2) - will be accepted. It would probably be best to explain an algorithm, ie Cooley-Tukey FFT, that has time complexity O(n log n), and work through a specific example using it. Applying other algorithms would be left to the solver. \$\endgroup\$ – miles Jun 16 '16 at 8:02
  • \$\begingroup\$ I think the sentence your solution must have time complexity of O(n log n) covers that. Sorry, I missed that again! \$\endgroup\$ – Luis Mendo Jun 16 '16 at 8:04
  • \$\begingroup\$ @LuisMendo Nevertheless, it'd probably be a good idea to explain one approach for solving this. I'll try to add one later. \$\endgroup\$ – miles Jun 16 '16 at 8:14
  • \$\begingroup\$ Is there such a thing as a slow Fourier Transform? \$\endgroup\$ – luser droog Jun 24 '16 at 3:18
3
\$\begingroup\$

Language succession

Given two words (two strings of lowercase-only letters separated by a space) as input to a program PX written in language X, output two programs in languages Y and Z such that program PY outputs the first word and program PZ outputs the second word. You may output or return these results. These programs may be returned in any fashion as long as it is evident that there are two distinct programs, e.g. double newline, or an array containing the result, or even a fancy box.

Here's the catch: the next answer's language X must be either language Y or Z from a past answer that has not as of the answer been used as a language X. The resulting nodes Y and Z cannot be a language that has appeared yet.

For example, say the first answer is a program written in Java that outputs a programs in Python 2 and Whitespace. Then, the next answer would write a program in either Python 2 or Whitespace that outputs programs in languages different than Java, Whitespace, and Python 2. Let's say it outputs answers in Foo and C++. Then, the next answer must be written in Whitespace, Foo, or C++.

The same user, however, may not extend their own nodes. That is, the person who posted the Java answer in the above example may not extend in Python 2 or Whitespace. Also, no person can extend two nodes of the same answer. So, someone couldn't extend both the Python 2 answer and the Whitespace one.

Here are languages I consider the "same":

  • Different versions of the same language. So, Python 2 is Python 3.
  • Trivial derivatives of a language. Brainfuck syntax substitutions are not valid, say.

However, this does not mean that Python 2 can be exchanged for Python 3.

The next solution in the chain must use the same character set as the previous program PX, adding or removing only 5 characters from that set. There is no restriction on the length of the set. Any characters may be added or removed from the set. Even if characters are not used in a submission, they still remain in the characters set until forcibly removed. (You may optionally substitute the characters with characters in another code page at the same place.) If you need an example, look below.

The winner of this challenge is the one with the last answer. I define "last answer" as the most recently posted answer on this challenge where after a period of seven days after the answer was posted, no new nodes have been extended. Feel free to continue extending nodes after the challenge has ended, but I will not revise the accepted answer. You may use languages made/updated after this challenge and still compete, but only if that language was not made/updated specifically for this challenge.

First post

(this will not be part of the resulting question)

I will start it off. Here's the answer markdown:

# J, initial answer

    split =: 3 : 0
     w1 =. > 0 { ;: y
     w2 =. > 1 { ;: y
     ('alert("' , w1, '")') ; ('print("', w2, ')"')
    )

Languages used:
 1. JavaScript
 2. Python 3

Character set used: `"'(),.0123:;=>aeilnprstwy{`, space, `\r`, and `\n`.

Code points used: `10 13 32 34 39 40 41 44 46 48 49 50 51 58 59 61 62 97 101 105 108 110 112 114 115 116 119 121 123`.

No differences, is initial answer.

Call it like `split 'multiple words'`. Output looks like this:

    +-----------------+--------------+
    |alert("multiple")|print("words")|
    +-----------------+--------------+

Answer format

Here's an example of the answer format to be used.

# Language, extends [language](link to post)

    program

Languages used:
  1. lang 1
  2. lang 2

Character set used: `characters`.

Code points used: `code points`.

Differences:
 * added "c"
 * removed " "

<extra info>

Also, please edit posts saying that one of your languages has been used, like so:

Languages used:
  1. lang 1 ([used](link to post))
  2. lang 2

Language Availability Snippet:

/* Configuration */

var QUESTION_ID = 47338; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 8478; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var LANG_REG = /<h\d>\s*([^\n,]*[^\s,]),[^]*?Languages used:\n\s*1. ([^\n]*)\n\s*2. ([^\n]*)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var used = [];
  var available = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(LANG_REG);
    if (match)
      used.push({
        language: match[1],
        user: getAuthorName(a),
        link: a.share_link
      });
      available.push({
        language: match[2],
        link: a.share_link
      });
      available.push({
        language: match[3],
        link: a.share_link
      });
      
  });
  
  available.filter(function (a) {
      return used.map(function (b) {return b.language}).indexOf(a.language) + 1
  });
  
  used.sort(function (a, b) {
    if (a.language > b.language) return 1;
    if (a.language < b.language) return -1;
    return 0
  });
  available.sort(function (a, b) {
    if (a.language > b.language) return 1;
    if (a.language < b.language) return -1;
    return 0
  });

  used.forEach(function (a) {
    
    var used_lang = jQuery("#used-template").html();
    used_lang = used_lang.replace("{{LANGUAGE}}", a.language)
                   .replace("{{NAME}}", a.user)
                   .replace("{{LINK}}", a.link);
    used_lang = jQuery(used_lang);
    jQuery("#used").append(used_lang);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();
    
  });
  
  available.forEach(function (a) {
    
    var avail_lang = jQuery("#available-template").html();
    avail_lang = avail_lang.replace("{{LANGUAGE}}", a.language)
                   .replace("{{LINK}}", a.link);
    avail_lang = jQuery(avail_lang);
    jQuery("#available").append(avail_lang);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();
    
  });

}
body { text-align: left !important}

#used-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#available-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="avail-list">
  <h2>Available</h2>
  <table class="avail-list">
    <thead>
      <tr><td>Language</td><td>Link</td></tr>
    </thead>
    <tbody id="available">

    </tbody>
  </table>
</div>
<div id="used-list">
  <h2>Used</h2>
  <table class="used-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Link</td></tr>
    </thead>
    <tbody id="used">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="available-template">
    <tr><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="used-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
  • \$\begingroup\$ I thought about it a bit, and I think you will run into trouble with the challenge being too easy to extend. I think your second options is better, particularly in that the different branches could have different character sets, which would be cool. Also I think last answer is a better winning criterion, but all of that is just my opinion. Also, probably would be a good idea to ban people from adding children to their own posts (unless you have it and I missed it...) \$\endgroup\$ – FryAmTheEggman Jun 17 '16 at 17:48
  • \$\begingroup\$ @FryAmTheEggman Thanks a lot! I'll hold off on deciding wining criterion until more feedback comes (if any). I will ban people from adding children to their own post, that's a good idea. \$\endgroup\$ – Conor O'Brien Jun 17 '16 at 17:53
  • \$\begingroup\$ @FryAmTheEggman Oh, nice catch! \$\endgroup\$ – Conor O'Brien Jun 17 '16 at 18:09
3
\$\begingroup\$

Xor A Rational Number

Background

Consider the fraction 3/5 in base 2:

0.10011001100110011001100110011...
\___/\__/
 (a)  (b)

It has a "regular" or non-repeating part (a) and a repeated part (b). Let's go ahead and shift it right by one bit and xor it with the original:

 x           = 0.10011001100110011001100110011...
(x >> 1)     = 0.01001100110011001100110011001...
(x >> a) ^ x = 0.11010101010101010101010101010...
               \__/\/
               (a) (b)

By examining the regular (a) and repeating (b) parts, we find that (x >> 1) ^ x = 5/6.

Input

  • Two whole numbers 0 < x, y < 256 such that 0 < x/y < 1 and gcd(x, y) = 1
  • Input can be through STDIN or function arguments
  • Input passed in any simple format for two decimals is acceptable, e.g. x y, x\ny, (x,y), [x, y], x/y, x%y (Haskell)
  • Input must be in base 10

Output

  • The numerator and denominator of ((x/y) >> 1) ^ (x/y), in base 10, in any clear output format.

Rules

  • The submission may be a function or full program
  • The output fraction does not have to be in its most reduced form
  • Builtins for rational number xor are not allowed
  • Infinite precision rational number types are allowed
  • This is code golf so shortest answer in bytes wins! (Tie break by first submission)

Test cases

More tests upon request or when this question is posted.

3/5 -> 5/6
1/2 -> 3/4
1/3 -> 4/6

Note:

I'm not entirely sure whether this has a more or less trivial solution...

This is code golf so shortest answer is bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Great idea. :) Are rational types allowed for I/O? Or at all? \$\endgroup\$ – Martin Ender Aug 1 '16 at 14:31
  • \$\begingroup\$ Great point. No, I believe that builtins for exact rational numbers should be disallowed. Do you think it's clear that the error should be 0, i.e. exact answers only? \$\endgroup\$ – Michael Klein Aug 1 '16 at 14:33
  • \$\begingroup\$ You've disallowed the use of built-ins for xoring rational numbers. Can we use rational types otherwise as long as we don't xor them? If so, it would probably be good to include that in the valid I/O formats as a useful example. \$\endgroup\$ – Martin Ender Aug 1 '16 at 14:42
  • \$\begingroup\$ "Consider a fraction 2/5:" ok, 0.4. I think you should mention either "base 2" or "binary" somewhere in that first sentence. \$\endgroup\$ – Peter Taylor Aug 1 '16 at 14:55
  • \$\begingroup\$ @MartinEnder Yes, that is allowed. I've added that and a couple more valid I/O formats \$\endgroup\$ – Michael Klein Aug 1 '16 at 15:23
  • \$\begingroup\$ I don't think your binary representation of 2/5 is correct. 0.1 in binary is 0.5 in decimal, which is already more than 0.4. 0.01100110... seems to be the correct value. \$\endgroup\$ – beaker Aug 1 '16 at 16:50
  • 1
    \$\begingroup\$ @beaker You're totally right. I meant to write 3/5 but typo'd it. Thanks for catching that \$\endgroup\$ – Michael Klein Aug 1 '16 at 16:53
  • \$\begingroup\$ That makes more sense \$\endgroup\$ – beaker Aug 1 '16 at 16:53
  • 1
    \$\begingroup\$ You might be interested that the xor of rationals gives the Sierpinski Gasket as a 3D graph. \$\endgroup\$ – xnor Aug 2 '16 at 9:38
  • 1
    \$\begingroup\$ I disagree with your third test case. 1/3 = 0.0101010101... so 1/3 ^ 1/6 = 0.011111111... = 1/2. \$\endgroup\$ – Peter Taylor Aug 2 '16 at 15:35
3
\$\begingroup\$

The Hanoi KoTH

The KoTH is like this:

Two stacks of height-8 towers are on either side of a total of 11 pegs, and are coloured red and blue.

(Like this: [["R8", "R7", "R6", "R5", "R4", "R3", "R2", "R1"], [], [], [], [], [], [], [], [], [], ["B8", "B7", "B6", "B5", "B4", "B3", "B2", "B1"]] - each array is a peg.)

The objective is to move your entire tower to the opposite side before your opponent does, Tower of Hanoi-style. Red has to move all of their blocks to where Blue's blocks are, and vice versa.

Rules:

  • You may not place a block on top of a block that is of an equal or smaller size.
  • You are only allowed to place a block on your "end tower" once your opponent has cleared away all their blocks.
  • If there are no more "moves" for either side, then the game is a draw.
  • There is a limit of 10,000 moves. If neither side completes their tower, then the game is a draw.
  • If you complete your tower before your opponent does and before the 10,000 moves is over, then you have won.
  • Invalid moves include:
    • Moving a block that is covered by other blocks
    • Moving a block onto a peg that contains smaller or equal-sized blocks than it
    • Doing "null" moves (moves that don't do anything).

Input:

Your input will consist of two numbers separated by a space.

The first number will be the starting peg. Pegs are zero-indexed (so the first peg is 0, and the last peg is 10).

The first number is valid only if the associated peg is not empty, and the block that's on the top of the peg is yours. Any other input is invalid, and your bot will be notified.

The second number will be the peg that your block is moving to. If the stack that the block is moving to is either:

  • Empty, or
  • Contains only larger blocks than the moving block

then the block can move. Otherwise, your bot will be notified that this is an invalid move.

Valid inputs (based on the starting position) would be:

  • 0 4 (Moving the block on peg 0, which is R1, to peg 4)
  • 0 3 (Moving the block on peg 0, which is R1, to peg 3)

Invalid inputs (again, based on the starting position) would be:

  • 1 3 (Invalid because there are no blocks on peg 1)
  • 10 3 (Invalid because the top block on peg 5, B1, is not yours)
  • 0 0 (Invalid because that is a null move)

If 5 invalid inputs are committed by the bot in a row, that counts as an automatic loss.

Output

The program will output to the bot what the current situation is - it will output the eleven arrays, each separated with the / symbol.

So, the starting position is like this:

R8R7R6R5R4R3R2R1//////////B8B7B6B5B4B3B2B1 (the middle nine stacks are empty).

Point System:

  • Win: 5 points
  • Draw: -1 point (to discourage drawing)
  • Loss: -5 points

I've made a small controller here.

META STUFF

  • Is this challenge a dupe?
  • Is there anything I can clarify?
  • Can anyone help with the controller (i.e. fix it up, optimise the code)?
    • Issues with the code:
      • Doesn't work with external files.
\$\endgroup\$
  • 1
    \$\begingroup\$ Have you done a game-theoretic analysis to work out the value of the game? (I.e. without the turn limit, is it a win for player 1 or a draw?) \$\endgroup\$ – Peter Taylor Aug 20 '16 at 12:27
  • \$\begingroup\$ @PeterTaylor See 2nd rule and 2nd bit of last rule (TBH, those were implemented just for this cause). I did a small analysis, and most of the rules put in place were to counter draws (because frankly, those aren't interesting). Is it possible that you could suggest any improvements to the game via the rules? This is the sandbox, after all. \$\endgroup\$ – clismique Aug 20 '16 at 12:30
  • \$\begingroup\$ Cabt I trivially move back and forth, to be a nuisance to the other team? \$\endgroup\$ – Rohan Jhunjhunwala Aug 21 '16 at 0:22
  • \$\begingroup\$ Oh never mind just saw the last rule \$\endgroup\$ – Rohan Jhunjhunwala Aug 21 '16 at 0:57
  • \$\begingroup\$ It does seem like the game space is a bit small though \$\endgroup\$ – Rohan Jhunjhunwala Aug 21 '16 at 0:57
  • \$\begingroup\$ @RohanJhunjhunwala Ummm... the rules don't exactly cover the "moving back and forth" thing, but it would be easy to find a counter to that. The game space is adequate enough - I can increase the size if needed. \$\endgroup\$ – clismique Aug 21 '16 at 1:08
  • \$\begingroup\$ By game space I mean the complexity space as in the game tree complexity en.wikipedia.org/wiki/Game_complexity \$\endgroup\$ – Rohan Jhunjhunwala Aug 21 '16 at 1:11
  • \$\begingroup\$ @trichoplax Fixed! \$\endgroup\$ – clismique Aug 21 '16 at 7:22
  • \$\begingroup\$ @trichoplax Yeah, that's true... I wanted to make it so that multiple bots can play Hanoi at the same time (with multiple towers), but I'm mainly not bothered to improve on the bot in that way. I'm fairly sure that this will be fine in order to finish in a reasonable time. \$\endgroup\$ – clismique Aug 21 '16 at 7:49
  • \$\begingroup\$ @trichoplax Fixed, again... also, implemented a controller. Can you help with it (if possible)? \$\endgroup\$ – clismique Aug 21 '16 at 8:09
  • \$\begingroup\$ Now that there's a link to the controller others will be able to give you feedback on it. I won't be able to review it myself at the moment. \$\endgroup\$ – trichoplax Aug 21 '16 at 8:12
3
\$\begingroup\$

Repetition

In a language called Repetition (something I just made up), there consists an infinite string of 12345678901234567890..., with 1234567890 repeating forever.

The following syntax is available to output numbers:

  • +-*/: This inserts the operator into the string of repeating digits.
    • Examples:
      • + -> 1+2 = 3 (The + inserts a + between 1 and 2)
      • +* -> 1+2*3 = 1+6 = 7 (Same as above, except two operators are used now)
      • / -> 1/2 = 0 (Repetition uses integer division)
    • Each operator is inserted so that it has one digit to its left, unless there are ~'s (see below).
  • c: Concatenates with the next digit in the string.
    • Examples:
      • c+ -> 12+3 = 15 (The c "continues" the 1 and concatenates it with the next digit, 2, to form 12)
      • +c -> 1+23 = 24
  • (): Brackets for processing numbers.
    • Examples:
      • (c+)* -> (12+3)*4 = 15*4 = 60 (Repetition uses the order of operations)
      • (c+)/c -> (12+3)/45 = 15/45 = 0
  • s: Skip a number.
    • s+ -> 2+3 = 5 (s skips 1)
    • csc -> 124 (s skips 3, and c concatenates 12 with 4)

In the examples above, only a finite amount of digits in the infinite string are used. The number of digits used is equivalent to number of operators, concats and skips + 1.

Your task is, when given a string of Repetition code, output the result.

Examples of input and output are:

++ -> 6
- -> -1
(-)* -> -3
cscc -> 1245

This is code golf, so shortest code in bytes wins!

Meta:

  • Is this explained remotely well? Anything I need to clear up?
  • Should this be a code golf or a metagolf challenge? I'm thinking of something like my previous challenge, There can be only 1!.
\$\endgroup\$
  • \$\begingroup\$ I'd definitely like it to be a calculator implementation challenge \$\endgroup\$ – Destructible Lemon Sep 16 '16 at 8:32
  • \$\begingroup\$ @DestructibleWatermelon Calculator implementation challenge? \$\endgroup\$ – clismique Sep 16 '16 at 8:47
  • \$\begingroup\$ like this one \$\endgroup\$ – Destructible Lemon Sep 16 '16 at 9:02
  • \$\begingroup\$ @DestructibleWatermelon So, a code-golf, then? \$\endgroup\$ – clismique Sep 16 '16 at 9:07
  • \$\begingroup\$ I'd definitely love both a code-golf and a metagolf. \$\endgroup\$ – user48538 Sep 16 '16 at 11:17
  • \$\begingroup\$ So, two separate challenges? \$\endgroup\$ – clismique Sep 16 '16 at 11:19
  • \$\begingroup\$ Shouldn't the number of digits used be number of operators etc. + 1 \$\endgroup\$ – Riley Sep 16 '16 at 19:14
  • \$\begingroup\$ @Riley Yeah, it should be. Thanks for catching that! \$\endgroup\$ – clismique Sep 16 '16 at 23:38
  • \$\begingroup\$ I guess its tirvially possible to prove that all numbers can be generated like this, by adding a corresponding series of ones lol... negative numbers can start with ones and subtract (-n + 1) ones \$\endgroup\$ – Rohan Jhunjhunwala Sep 17 '16 at 0:03
  • \$\begingroup\$ @RohanJhunjhunwala Yeah, that's true - which is where the metagolfing part comes in, and you have to golf down the output. The code golf doesn't really matter to that either, since you have to process input and return an output. \$\endgroup\$ – clismique Sep 17 '16 at 0:05
3
\$\begingroup\$

Make an un-polyglot-able language!

The cops' task is to create a language that is as hard to polyglot as possible. However, when making a language, you must follow these rules:

  • ASCII characters only.
  • The language must fit our definition of programming language, i.e. it must be able to add two numbers together, and check, when given a numerical input, if a number is prime or not.
    • You must post the adder and prime checker (the full program) into your answer, and they must be at most 1kb in size.
  • You must post your full interpreter into the answer as well.
  • Also, give a run-down of what each command in your language is and how your language works in general.
  • You must complete the robbers' task, which is to create a polyglot of your language and a language from this list that outputs "Hello, World!". It must not exceed 5kb.
    • If your language doesn't support ASCII output, you can write a program that outputs the ASCII character codes of each character of "Hello, World!".
  • All four of the things above (interpreter, adder, prime checker and "Hello, World!" polyglot) MUST fit into your answer.
  • After your challenge is Cracked, you must post your answer to the robbers' task.
  • If your language has not been Cracked for over 7 days, then your language is Safe. You must put Safe in your header, and post your solution.
  • Your language answer should look like this:

    # {language name}, {cracked/safe} (<- the "cracked/safe" is only to be used 
                                       when your lang is either cracked or safe)
    
    {language description}
    
    {full interpreter}
    
    {adder} (max 1kb)
    
    {primality checker} (max 1kb)
    
    {Hello World polyglot} (<- only posted if your lang is cracked or safe, max 5kb)
    

The robbers' task is to create a polyglot using any cops' language that outputs "Hello, World!".

  • You must output the exact string "Hello, World!", nothing more and nothing less (except for leading and trailing linefeeds).
    • If the cop's language doesn't support ASCII output, you may output the ASCII character codes of "Hello, World!".
  • You only need to support two languages: the cops' one and one from this list of common languages.
  • The final polyglot must not exceed 5kb.
  • Your answer should look like this:

    # {language name}, {original author}, {bytecount}
    
        {insert code here}
    
    {description of code}
    
  • Post a comment on the (in the cops' thread) language that you Cracked, linking them to your answer.

The winner will be:

  • (Cops) the safe language that has the lowest byte-count for the "Hello, World!" polyglot. It will be declared after 1 month.
  • (Robbers) the person who has cracked the most languages.

In case the language list changes, the languages are:

Java, Python, PHP, C#, Javascript, C++, C, Objective C, R, Swift, Matlab,
Ruby, VBA, Visual Basic, Scala, Perl, Lua, Delphi, Go, Haskell, Rust

Meta:

  • Is this challenge a dupe?
  • Anything I can improve on?
\$\endgroup\$
  • 1
    \$\begingroup\$ Interesting concept, but this needs some additional work. 1. I couldn't find the winning criterion for the robbers' challenge. 2. You'd somehow have to avoid languages that only compile if the source code has a specific hash. 3. The language list you link to changes every month(?); the challenge spec should be static. \$\endgroup\$ – Dennis Oct 7 '16 at 4:20
  • \$\begingroup\$ Nothing seems to rule out a language where the program 'a' prints Hello world, 'b' adds numbers, 'c' checks primality, and any other programs do nothing. \$\endgroup\$ – xnor Oct 7 '16 at 4:43
  • \$\begingroup\$ @xnor That problem is removed by the author having to make his/her own "Hello, World!" polyglot. \$\endgroup\$ – clismique Oct 7 '16 at 4:53
  • 1
    \$\begingroup\$ Where you allow answers to print the character codes of Hello World, it's not clear whether in that case the mainstream language should also print character codes or still Hello, World!. \$\endgroup\$ – Martin Ender Oct 7 '16 at 21:04
  • \$\begingroup\$ Could you specify tie breakers for both winning criteria (cops and robbers)? I guess first to post would work well for the cops, but for the robbers the tie breaker needs to be chosen carefully. If one person cracks 9 languages that are easy to crack, and another person later cracks 9 languages that are hard to crack, being earlier doesn't seem the ideal way to choose a winner. I can't think of a better way though. \$\endgroup\$ – trichoplax Oct 16 '16 at 9:13
  • \$\begingroup\$ Is it worth specifying that the crack answer should link to the answer it is cracking? \$\endgroup\$ – trichoplax Oct 16 '16 at 9:18
3
\$\begingroup\$

Show the Key Signature

Here is are the key signatures for the key of C♯ Major in the treble clef, and C♭ major in the bass clef:

           ♯
─────♯───────────────────────   ─────────────────────────────
                    ♯
──────────────♯──────────────   ─────────────────────────────
        ♯                               ♭
───────────────────────♯─────   ──────────────♭──────────────
                 ♯                                  ♭
─────────────────────────────   ─────♭───────────────────────
                                           ♭
─────────────────────────────   ─────────────────♭───────────
                                                       ♭

A full list of key signatures can be found here. Hopefully you will notice that a) the sharps and flats are two notes lower in the bass clef as compared to the treble clef b) all key signatures can be obtained from the C♯ Major and C♭ Major key signatures by removing trailing sharps and flats appropriately.

Your task is, given a suitable representation of the clef and key, to output the appropriate key signature using the above format.

  • Your output must have at least 11 lines, in order to accommodate all possible placings of sharps and flats.
  • To compensate for the terrible aspect ratio, each sharp and flat must be separated by two columns, and there must be at least five empty columns at the beginning and end, but no more than 29 columns in total.
  • You may use #, b and - characters instead of ♯, ♭ and ─.

This is , so the shortest solution wins!

\$\endgroup\$
  • \$\begingroup\$ Can I adopt this abandoned challenge? \$\endgroup\$ – programmer5000 Jun 9 '17 at 12:07
  • \$\begingroup\$ @programmer5000 Sorry, I'm not very good at checking back to see how my Sandbox posts are doing. As I don't have many questions myself, I'd rather be the person to ask it, if you don't mind. (But feel free to comment on any changes you think I should make first.) \$\endgroup\$ – Neil Jun 9 '17 at 12:25
  • \$\begingroup\$ Ok sure. I think it is ready to post. \$\endgroup\$ – programmer5000 Jun 9 '17 at 12:26
  • \$\begingroup\$ @programmer5000 Oh, I meant to ask, what input format do you think I should accept for the clef and key? Representing the key as a number between -7 and 7 feels like cheating to me. \$\endgroup\$ – Neil Jun 11 '17 at 21:15
3
\$\begingroup\$

The challenge is to write the fastest code possible for computing the permanent of a matrix.

The permanent of an n-by-n matrix A = (ai,j) is defined as

enter image description here

Here S_n represents the set of all permutations of [1, n].

As an example (from the wiki):

enter image description here

In this question matrices are all square and will only have the values -1 and 1 in them.

Examples

Input:

[[ 1 -1 -1  1]
 [-1 -1 -1  1]
 [-1  1 -1  1]
 [ 1 -1 -1  1]]

Permanent:

-4

Input:

[[-1 -1 -1 -1]
 [-1  1 -1 -1]
 [ 1 -1 -1 -1]
 [ 1 -1  1 -1]]

Permanent:

0

Input:

[[ 1 -1  1 -1 -1 -1 -1 -1]
 [-1 -1  1  1 -1  1  1 -1]
 [ 1 -1 -1 -1 -1  1  1  1]
 [-1 -1 -1  1 -1  1  1  1]
 [ 1 -1 -1  1  1  1  1 -1]
 [-1  1 -1  1 -1  1  1 -1]
 [ 1 -1  1 -1  1 -1  1 -1]
 [-1 -1  1 -1  1  1  1  1]]

Permanent:

192

The task

You should write code that, given an n by n matrix, outputs its permanent.

As I will need to test your code it would be helpful if you could give a simple way for me to give matrix as input to your code.

Be warned that the permanent can be large (the all 1s matrix is the extreme case).

Scores and ties

I will test your code on random +-1 matrices of increasing size and stop the first time your code takes more than 1 minute on my computer.

If two people get the same score then the winner is the one which is fastest for that value of n. If those are within 1 second of each other then it is the one posted first.

Languages and libraries

You can use any available language and libraries you like but no pre-existing function to compute the permanent. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.`

Reference implementations

There is already a codegolf question question with lots of code in different languages for computing the permanent. Mathematica and Maple also both have permanent implementations if you can access those.

My Machine The timings will be run on my 64-bit machine. This is a standard ubuntu install with 8GB RAM, AMD FX-8350 Eight-Core Processor and Radeon HD 4250. This also means I need to be able to run your code.

\$\endgroup\$
  • \$\begingroup\$ Is your system 64-bit? How much memory/disk space can we use? Could you add a reference implementation so that we might have something to initially compare against. \$\endgroup\$ – miles Oct 21 '16 at 5:28
  • \$\begingroup\$ @miles Yes and I added some details to the question. \$\endgroup\$ – user9206 Oct 21 '16 at 7:45
  • \$\begingroup\$ Thanks. Also I meant a reference implementation that strives to be efficient without using builtins. Most of the submissions from that challenge are very inefficient since the requirement was only up to 6x6 matrices. \$\endgroup\$ – miles Oct 21 '16 at 8:06
  • \$\begingroup\$ @miles I see. I found this online bpaste.net/show/c346e05415f9 . I don't know if I am allowed to include it. \$\endgroup\$ – user9206 Oct 21 '16 at 10:34
3
\$\begingroup\$

This has been donated to the Secret Santa Sandbox if anyone wants to take up the mantle.

Crazy Librarian's Interesting Numbers Game

Phew, you just managed to finish your code for the Arithmetic Sequence of Primes, and everything went swimmingly for your Crazy Librarian boss. Indeed, the math teacher taught the librarian a new card game as thanks for the prime sequences. However, the librarian wants to beat the math teacher at their own game, and so you're enlisted (again) to assist.

The card game was described as a two-player variation of a trick-taking game called California Jack. Each player is dealt a particular suit of cards from a standard US 52-card deck, and this forms their hand. A third suit of the cards is randomly shuffled and placed face-down between the players as the trophy deck. The fourth suit is unused. Each round, the top of the trophy deck is flipped face-up, and the two players select a card (in secret) from their hand to be their bid for that round, and places it face-down in front of them. The players reveal their bid card, and the higher card (aces low) wins the trophy card. The trophy card goes into the winner's trophy pile, and the two bid cards are discarded. If the players both bid the same card, neither gets the trophy card, and it is discarded along with both bid cards. The winner after all 13 rounds is whoever has the most points in their trophy pile, with Jack=11, Queen=12, and King=13. Note that it is possible for the game to end in a draw (including a zero-point draw).

Since you really want to impress the Crazy Librarian, you've ... enlisted ... the help of some of your friends, and you're going to create a bracket royale to find the best playing algorithm, and use that so the librarian can show up the math teacher.


Questions for Meta

  • Program I/O? I'm envisioning a stateful program that keeps track of its own cards, where each execution is a run of the game against an outside opponent -- e.g., each input is [W/L] T# that says whether the program Won or Lost the previous round, and what the current-round's Trophy card is. Then, the output would be what card it chooses to bid. Repeat 13 times. Could also do an interactive version, scraping STDOUT and setting STDIN?
  • Example of a really simplistic algorithm (in pseudocode) -- return argv[1] -- this just bids the same as whatever the trophy card is.
  • The programs could keep track of their opponent's total and their total, but the controller would have final say (obviously).
  • I'm envisioning a double-bracket style, where each program is randomly seeded into the bracket. Best 3-of-5 games moves it to the next round, while the loser gets re-seeded into the loser's bracket and can re-win a chance for the final four.
  • What am I missing?
\$\endgroup\$
  • 1
    \$\begingroup\$ I think input could be expanded a bit. For instance, there doesn't seem to be any way to track your opponent's cards right now (just whether it won/lost the last), even though in an actual game they would be revealed (and would be part of any decent strategy I'd think). \$\endgroup\$ – Geobits Oct 9 '15 at 14:03

You must log in to answer this question.

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