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

2591 Answers 2591

0
\$\begingroup\$

Generate a Voronoi Diagram

Challenge

Given a list of coordinates and colours of points, output a 300px by 300px Voronoi Diagram.

Winning

Shortest code in bytes wins.

To be expanded

\$\endgroup\$
  • 1
    \$\begingroup\$ output a what??? \$\endgroup\$ – Titus Apr 21 '17 at 17:15
  • \$\begingroup\$ @Titus A Voronoi Diagram. I'll add an explanation when I have time \$\endgroup\$ – Beta Decay Apr 21 '17 at 18:34
  • \$\begingroup\$ Five months later... \$\endgroup\$ – Gryphon - Reinstate Monica Sep 27 '17 at 4:38
  • \$\begingroup\$ @Gryphon It's a looong expansion ;) \$\endgroup\$ – Beta Decay Sep 27 '17 at 6:06
0
\$\begingroup\$

Google Autocomplete Fun

Your task is to create a program which, given an input string, will output the first Google autocomplete result for that search. The format of input/output is up to you.

Rules

  1. Your program must take 1 input, a string, and output the top Google autocomplete/auto-fill suggestions result. The format of input/output is up to you. Just be sure to mention what your I/O format is.
  2. Obviously, accessing the Internet is allowed.
  3. URL shorteners (like bit.ly, TinyURL, etc.) are strictly disallowed. You should fetch your autocomplete results from this URL: http://suggestqueries.google.com/complete/search?client=your_browser&q=your_query. You are allowed to assume any browser name for client. In the program I wrote, I assume Chrome. Any browser name or string should work.
  4. Please provide an explanation of how your program works. It is not mandatory, but I strongly advise it.
  5. All standard loopholes are strictly forbidden.

This is , so may the shortest code win and the best programmer prosper...

\$\endgroup\$
  • \$\begingroup\$ I think you technically need to allow internet access in the question. \$\endgroup\$ – Comrade SparklePony Apr 23 '17 at 20:51
  • \$\begingroup\$ @ComradeSparklePony You are so right. :) \$\endgroup\$ – ckjbgames Apr 23 '17 at 21:06
0
\$\begingroup\$

Calculate Call-Changes

Before learning to ring methods, novice bell-ringers usually first learn something called call-changes. This is basically a sequence of permutations (the changes), each one obtained from the previous by exchanging a pair of adjacent bells (the call).

The bells always begin in ascending pitch number order (which is actually descending pitch order). Each exchange (call) can be expressed in one of two different ways, depending on the whim of the conductor. Exchanges always use the bell's pitch number, regardless of the bell's current position.

  1. The exchange can be expressed as a pair of adjacent bell numbers in sequence. The first of the pair is always immediately before the second of the pair. The two bells simply exchange places, so the first of the pair ends up immediately after the second of the pair.

    • The exchange can be expressed as a bell number plus a second bell number which is two places before the first bell. The (unnamed) intervening bell and the first bell exchange places. This also results in the first input bell ending up immediately after the second input bell.
    • The above expression cannot be used to move a bell into first (lead) place, because there is no bell for it to end up after. You therefore need to accept an alternate way of expressing that the first two bells change places. Note that this must still refer to the pitch number of the bell in second place, but this might be achieved e.g. by having a sentinel value for the second bell, or by omitting it completely. (In real call-changes the call is "[number] lead!" rather than "[number] to [number]!".)

Your other input will be the number (not list) of bells in the sequence. You can assume that this will not be more than 9 (but supporting larger numbers may get you more upvotes). Here is a worked example showing the list of calls in both of the above formats and the desired output:

Call 1  Call 2  Output
(5 bells input  12345)
12      20*     21345
34      41      21435
14      42      24135
24      40*     42135
21      14      41235
41      10*     14235
42      21      12435
43      32      12345

*example representation.

Your program or function should output the result after each change. (Showing the initial permutation is permitted but not necessary.) Input and output can be any reasonable method, e.g. nested array of numbers or list of strings (note that if you use strings and want to support more than 9 bells then the next three bells are traditionally numbered 0, E and T). You can assume that all inputs follow the above pattern (or your custom representation for calling the seconds place bell into first place).

This is , so the shortest answer that breaks no standard loopholes wins!

\$\endgroup\$
  • \$\begingroup\$ I can't work out what the example is showing. Specifically: what input should the function/program take and what output should it produce? \$\endgroup\$ – Peter Taylor Apr 24 '17 at 8:48
  • \$\begingroup\$ @PeterTaylor Except for the first 12345 row, which is only there to try to help demonstrate the mechanics, the left column contains the result. However for each result there are two acceptable inputs (this is just a fact of life, not an attempt to make the question more complex); these are shown in the other two columns. \$\endgroup\$ – Neil Apr 24 '17 at 9:06
  • \$\begingroup\$ So e.g. the input is "42135", "24" and the output is "41235"? \$\endgroup\$ – Peter Taylor Apr 24 '17 at 9:58
  • \$\begingroup\$ No, the input is 5, "12", "34", "14", "24", "21", "41", "42", "43" and the output is "21345"..."42135", "41235"..."12345". \$\endgroup\$ – Neil Apr 24 '17 at 10:50
  • \$\begingroup\$ Could you edit the question to make that clearer? \$\endgroup\$ – Peter Taylor Apr 24 '17 at 13:51
  • \$\begingroup\$ @PeterTaylor Hopefully my rewrite is clearer now. \$\endgroup\$ – Neil Apr 26 '17 at 9:36
0
\$\begingroup\$

Excel NORMSINV function

Implement the excel NORMSINV function in your favourite language, shortest code wins

Build in functions and standard loopholes are not allowed

Loss of precision is also not allowed

Reference C Implementation

/*
 * Original C++ implementation found at http://www.wilmott.com/messageview.cfm?catid=10&threadid=38771
 * C# implementation found at http://weblogs.asp.net/esanchez/archive/2010/07/29/a-quick-and-dirty-implementation-of-excel-norminv-function-in-c.aspx
 *     Compute the quantile function for the normal distribution.
 *
 *     For small to moderate probabilities, algorithm referenced
 *     below is used to obtain an initial approximation which is
 *     polished with a final Newton step.
 *
 *     For very large arguments, an algorithm of Wichura is used.
 *
 *  REFERENCE
 *
 *     Beasley, J. D. and S. G. Springer (1977).
 *     Algorithm AS 111: The percentage points of the normal distribution,
 *     Applied Statistics, 26, 118-121.
 *
 *      Wichura, M.J. (1988).
 *      Algorithm AS 241: The Percentage Points of the Normal Distribution.
 *      Applied Statistics, 37, 477-484.
 */

#include <math.h>

double normsInv(double p, double mu, double sigma)
{
    if (p < 0 || p > 1)
    {
        printf("The probality p must be bigger than 0 and smaller than 1");
        exit(1);
    }
    if (sigma < 0)
    {
        printf("The standard deviation sigma must be positive");
        exit(1);
    }
    if (p == 0)
    {
        return -1e100;
    }
    if (p == 1)
    {
        return 1e100;
    }
    if (sigma == 0)
    {
        return mu;
    }

    double q, r, val;

    q = p - 0.5;

    /*-- use AS 241 --- */
    /* double ppnd16_(double *p, long *ifault)*/
    /*      ALGORITHM AS241  APPL. STATIST. (1988) VOL. 37, NO. 3
            Produces the normal deviate Z corresponding to a given lower
            tail area of P; Z is accurate to about 1 part in 10**16.
    */
    if (fabs(q) <= .425)
    {/* 0.075 <= p <= 0.925 */
        r = .180625 - q * q;
        val =
               q * (((((((r * 2509.0809287301226727 +
                          33430.575583588128105) * r + 67265.770927008700853) * r +
                        45921.953931549871457) * r + 13731.693765509461125) * r +
                      1971.5909503065514427) * r + 133.14166789178437745) * r +
                    3.387132872796366608)
               / (((((((r * 5226.495278852854561 +
                        28729.085735721942674) * r + 39307.89580009271061) * r +
                      21213.794301586595867) * r + 5394.1960214247511077) * r +
                    687.1870074920579083) * r + 42.313330701600911252) * r + 1);
    }
    else
    { /* closer than 0.075 from {0,1} boundary */

        /* r = min(p, 1-p) < 0.075 */
        if (q > 0)
            r = 1 - p;
        else
            r = p;

        r = sqrt(-log(r));
        /* r = sqrt(-log(r))  <==>  min(p, 1-p) = exp( - r^2 ) */

        if (r <= 5)
        { /* <==> min(p,1-p) >= exp(-25) ~= 1.3888e-11 */
            r += -1.6;
            val = (((((((r * 7.7454501427834140764e-4 +
                       .0227238449892691845833) * r + .24178072517745061177) *
                     r + 1.27045825245236838258) * r +
                    3.64784832476320460504) * r + 5.7694972214606914055) *
                  r + 4.6303378461565452959) * r +
                 1.42343711074968357734)
                / (((((((r *
                         1.05075007164441684324e-9 + 5.475938084995344946e-4) *
                        r + .0151986665636164571966) * r +
                       .14810397642748007459) * r + .68976733498510000455) *
                     r + 1.6763848301838038494) * r +
                    2.05319162663775882187) * r + 1);
        }
        else
        { /* very close to  0 or 1 */
            r += -5;
            val = (((((((r * 2.01033439929228813265e-7 +
                       2.71155556874348757815e-5) * r +
                      .0012426609473880784386) * r + .026532189526576123093) *
                    r + .29656057182850489123) * r +
                   1.7848265399172913358) * r + 5.4637849111641143699) *
                 r + 6.6579046435011037772)
                / (((((((r *
                         2.04426310338993978564e-15 + 1.4215117583164458887e-7) *
                        r + 1.8463183175100546818e-5) * r +
                       7.868691311456132591e-4) * r + .0148753612908506148525)
                     * r + .13692988092273580531) * r +
                    .59983220655588793769) * r + 1);
        }

        if (q < 0.0)
        {
            val = -val;
        }
    }

    return mu + sigma * val;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ A reference implementation is not a specification. \$\endgroup\$ – Peter Taylor Apr 26 '17 at 16:20
  • \$\begingroup\$ Yeah there are people who don't speak C. \$\endgroup\$ – Erik the Outgolfer Apr 26 '17 at 16:50
  • \$\begingroup\$ @Peter, do you have any suggestions on how I can create a specification for this? Do you think people will be interested or is this a dead end? \$\endgroup\$ – Johan du Toit Apr 26 '17 at 16:58
  • 1
    \$\begingroup\$ 1. Define the function: what are the inputs? What does the output mean? On the basis of some quick Googling I understand that it's an offset inverse of erf? But there seems to be disagreement about how many input parameters it takes. 2. Be explicit about the numerical analytic requirements. I'm not sure what "Loss of precision is also not allowed" means: that answers must avoid subtractions of values of similar magnitude? 3. With respect to interest, the thematically related codegolf.stackexchange.com/q/9070/194 got a few answers. \$\endgroup\$ – Peter Taylor Apr 27 '17 at 10:43
0
\$\begingroup\$

Find the Calling Pattern

I've written a program to add two numbers a and b:

f=lambda:lambda a:lambda b:lambda:a+b

This has a very specific calling pattern. It must be called as:

f()(a)(b)()

In this case, it was fairly clear, but sometimes the calling pattern can be more complicated:

f(a,None)()("","","")([0,0],b)(())()

In essence, this challenge is about the cops trying to obfuscate this calling pattern, and the robbers trying to find it.

Rules for Cops:

Calling patterns:

  • The function must only need to be called up to 5 times to give the answer.
  • For the purposes of this challenge, a false-unit is None, "", [], 0, or ().
  • A valid argument to the curried function in the calling pattern is either:
    • a false-unit,
    • a list or tuple containing one to five false units, or
    • one of the actual numbers to be added (represented by a and b).
  • Each time it is called, it should only take up to five arguments.
  • The calling pattern can change based on what arguments are passed to it. Be creative!
  • a and b must each appear once in the calling pattern.

Examples of valid calling patterns:

f(a,b)
f("",a)(b,[0,0])
f(a)("",(),[None],[0,()])(b)()

Examples of invalid calling patterns:

f(a,b,0,0,"",[]) # too many arguments
f(a,[(),[],"",(),[],""])(b) # too many elements in [(),[],"",(),[],""]
f(a) # b is not passed
f([a,b]) # a and b may not be contained in a list
f((0,[None,""]),a)(b) # [None,""] is not a false-unit

For your submission, you must post a lambda that, when called according to your calling pattern, evaluates to a + b.

You can assume that a and b are both positive and that a + b < 2147483647 (the highest signed 32-bit integer).

Your submission is safe if it is not cracked by a robber in one week.

Rules for Robbers

To crack a cop's submission, you must post a submission which takes two inputs and returns a string showing how to call the cop's submission to coerce it into adding your two inputs. For example, if this was a cop's submission:

lambda:lambda x,z:lambda y:x+(y*(z==0))

This could be your crack:

lambda a, b: "f()(%s, 0)(%s)" % (a, b)

Sandbox Notes

  • Is there anything I should clarify? Should I add more examples?
  • Should I try to make this language agnostic or restrict it to Python?
  • Is this too weighted towards one side (is it too easy for the cops or the robbers?)
  • Are there any additional restrictions that could make it more fair?
\$\endgroup\$
  • 1
    \$\begingroup\$ Can you give an example of a cops submission that might be hard to crack? \$\endgroup\$ – Leaky Nun Apr 26 '17 at 5:37
  • \$\begingroup\$ Without a language restriction, some may call Currying a non-observable requirement. \$\endgroup\$ – ATaco Apr 26 '17 at 5:41
  • \$\begingroup\$ @ATaco Which is why I was thinking of restricting it to Python. \$\endgroup\$ – Esolanging Fruit Apr 26 '17 at 5:44
  • \$\begingroup\$ often, after a certain time (a week, for example,) A cop's submission is considered "safe", and they reveal their solution (if they want). You may want to mention/implement something like this \$\endgroup\$ – MildlyMilquetoast Apr 26 '17 at 5:46
  • \$\begingroup\$ @MistahFiggins Added. \$\endgroup\$ – Esolanging Fruit Apr 26 '17 at 6:09
  • \$\begingroup\$ I don't think the example works. \$\endgroup\$ – Peter Taylor Apr 27 '17 at 13:28
  • \$\begingroup\$ @PeterTaylor Edited. \$\endgroup\$ – Esolanging Fruit Apr 27 '17 at 15:17
  • \$\begingroup\$ That's still broken except in the special case that y == 0. \$\endgroup\$ – Peter Taylor Apr 27 '17 at 15:37
0
\$\begingroup\$

To Polar and Back

Background

There are 2 main ways to represent a single point on a plane:

  • in Cartesian form, with an x and y value,
  • and in Polar form, with an angle and a magnitude

For example, the point (5, 5) can also be represented with the angle π / 4 and magnitude 5 * sqrt(2)

In this challenge, we will be using radians, and not degrees.

Conversion

This challenge deals with the mapping of Polar form onto a Cartesian grid, by using the angle as the x value, and the magnitude as the y value.

For example, to change the point (sqrt(3), 1) into Polar form and back, we first convert it into polar form, with an angle of π / 6 and magnitude of 2.

Then, these values are mapped into Cartesian form, yielding the Cartesian point (π/6, 2).

The Challenge

Create a program or function that, given a rectangle in Cartesian form, outputs it's area after it has been converted to Polar form and mapped back onto the Cartesian plane by equating angle with x and magnitude with y.

Input

The input will be a rectangle in Cartesian form whose legs are parallel to the x and y axes. Also, all 4 corners will be in the first quadrant, meaning that all x and y values will be strictly positive.

This means that you may take

  • The Cartesian coordinates of all 4 corners
  • The Cartesian coordinates of opposite corners
  • The Cartesian coordinates of one corner, and a width and height value

or some other reasonable form, such as a rectangle object. The important thing is that you don't take Polar coordinates as input.

You can take the points or values in any order you choose.

Please include the input format you used in your answer.

Output

Output will be a single, decimal number rounded to at least the hundredth's place (2 digits after the decimal).

Explained Example

Note: For the sake of clarity, I will use symbols like π or sqrt(3) instead of their decimal equivalents.

Also keep in mind that this is probably one of many ways to go about this problem, and it doesn't matter what method you use to find the area as long as you do. This example is mostly to explain the above by showing it in action.

Anyways, here is out input, in the form of 4 points:

(1, sqrt(3)), (4, sqrt(3)), (1, 1), (4, 1)

First, we might convert each point into polar form, and map that back onto the Cartesian plane:

(x, y)       -> (angle, magnitude)
(1, sqrt(3)) -> (π/3, 2)
(4, sqrt(3)) -> (arctan(sqrt(3)/4), sqrt(19))
(1, 1)       -> (π/4, sqrt(2))
(4, 1)       -> (arctan(1/4), sqrt(17))

This should be relatively easy using trigonometry and the Pythagorean theorem.

These new Cartesian points give us the corners of our new shape, which looks something like this:

courtesy of http://www.meta-calculator.com

Notice that the sides are not straight, meaning you will have to figure out how to get the equations for the sides as well as how to find the area. I'll leave that up to you.

In any case, the area of this shape is about 0.81810689, but you only need to print 0.82 (without the leading 0, if you prefer).

Other Test Cases

The input will be taken in the form of 4 points, in reading order (left to right, then top to bottom)

input -> output
(1, 1.732), (4, 1.732), (1, 1), (4, 1) -> 0.82

Sandbox: I will add more test cases later - any suggestions about certain edge cases I should include would be helpful.

Scoring

This is , so the shortest answer in bytes wins.

Standard loopholes, as always, apply.

Sandbox

  • Any name ideas?
  • Any tags I should add/remove?
  • Suggestions/help with creating test cases?
  • Is the explanation sufficient?
  • Should I change the accuracy requirement to 3 digits after the decimal point, or would that be too hard?

Thanks!

\$\endgroup\$
  • \$\begingroup\$ I'm not quite sure I understand how the edges should be curved. Additionally, I think you should require the program to use the maximum precision that the language can handle, but I'm not sure how well that would work. \$\endgroup\$ – user42649 Apr 27 '17 at 4:30
  • \$\begingroup\$ @HyperNeutrino The edges curve because more points on the straight line lie in a given angle when the segment looked at is farther from the point closest to the origin. In other words, as the line gets farther from the axes, the line gets closer to parallel with a ray extending from the origin to the line. This means that the line on the new graph will be closer to vertical when it gets closer to the axis (at angles 0 or π/2, depending on whether the original line is vertical or horizontal). Hope this helps! Also, not sure about the accuracy yet, so I'm going to leave it as it is for now. \$\endgroup\$ – MildlyMilquetoast Apr 27 '17 at 4:52
  • \$\begingroup\$ Oh, I see. That makes sense. And yeah, I'd do what you're doing and see if other people make suggestions on the accuracy aspect. \$\endgroup\$ – user42649 Apr 27 '17 at 4:53
  • \$\begingroup\$ "Create a program or function that, given a rectangle in Cartesian form, output it's area after it has been converted to polar form and back." Since the conversion is a bijection, converting to polar form and back leaves it unchanged, so it's just a case of finding the area of the rectangle. That doesn't seem to be what the example does, though, so I have to say that the spec is not clear. \$\endgroup\$ – Peter Taylor Apr 27 '17 at 10:24
  • 1
    \$\begingroup\$ @PeterTaylor You're right, this is poorly worded. It should say something like "given a rectangle in Cartesian form, output it's area after it has been converted to Polar form and mapped back onto the Cartesian plane by equating angle with x and magnitude with y" \$\endgroup\$ – MildlyMilquetoast Apr 27 '17 at 15:32
0
\$\begingroup\$

Get the Decimal! (Posted)

\$\endgroup\$
  • \$\begingroup\$ Rounding on the digit, or return the exact digit? (important distinction if people can generate out to x and then take the last digit, for example) \$\endgroup\$ – AdmBorkBork Apr 21 '17 at 15:11
  • 1
    \$\begingroup\$ Please delete this now that it is posted. \$\endgroup\$ – programmer5000 Apr 27 '17 at 17:24
0
\$\begingroup\$

Electron Configurations: Orbitals

Challenge

Given an elements atomic number as input, output its short electronic configuration.

Explanation

http://www.chemguide.co.uk/atoms/properties/elstructs.html

To come

Examples

Sodium: 11

[Ne] 3s1

Hydrogen: 1

1s1

Helium: 2

1s2 

or

[He]

Vanadium: 23

[Ar] 4s2 3d3

Selenium: 34

[Ar] 4s2 3d10 4p4

Winning

Shortest code in bytes wins

\$\endgroup\$
  • \$\begingroup\$ Do we have to worry about unstable isotopes undergoing Beta Decay? ;) Nice challenge btw! \$\endgroup\$ – user42649 Apr 27 '17 at 16:57
  • 1
    \$\begingroup\$ codegolf.stackexchange.com/q/37657/194 \$\endgroup\$ – Peter Taylor Apr 27 '17 at 21:06
0
\$\begingroup\$

Variably Incremented Chained Ranges

Your task will be, given a well-formed input string s, to parse it as a range, with special properties:

  1. A traditional range is defined as a..b = [a, a+1, .., b-1, b].
  2. An incremental range is an extension of the traditional range in the format a.c.b.
    • The format above uses a and b in the traditional sense, but it will use c as the step.
    • That is to say 1.2.5 = [1,3,5] and a.c.b = [a, a+c, .., b iff b-a is divisble by c]
    • This means that 0.2.5 = [0, 2, 4] because b-a % c != 0.
  3. The ranges are chain-able, meaning that a..b..c..d..e..f..g..h..i is valid.
    • Always should be handled left-to-right.
    • The chain should always be continued from the end of the last range.
    • 0.2.5..3 is not [0,2,4,5,4,3] it is [0,2,4,3].
  4. The format of the range may be a.c.b or a..b, absence of c means c = 1.

I & O Gaurantees

  • c <= difference(b, a), you will never see something like 1.100.2.
  • a and b are positive integers or 0, this makes crap easier
  • Notice, however, that neither a > b nor a < b are guaranteed, both are acceptable.
  • a, b and c will always be integer values, floats aren't supported.

This is , lowest byte count wins.

\$\endgroup\$
0
\$\begingroup\$

Give counterexamples to thesis that prime numbers are finite.

It is known since antiquity that there are infinite prime numbers, first proved by Euclid. An unorthodox yet brief formulation of this proof was recently posted on MathExchange:

There are infinitely many primes, if not, multiply all and add 1.

Challenge

Given a prime number N, output a prime number created by multiplying it with all lower primes and adding one, i. e. (2*3*5*...*N) + 1. In other words, if someone claimed that N is the largest finite number, you have to give a counterexample Euclid would likely compute to prove them false.

You don't have to consider input number that is not a prime.

Your representation of a number must have a range of 32-bit signed integers or larger.

You can use floating point representation as long as your code uses int-specific operations (e.g. no double-specific bit-fu).

Shortest code wins, standard loopholes forbidden. You may use a lookup table of primes.

Example Input and Output

2 → 3          // because             2 + 1 = 3
3 → 7          // because           3*2 + 1 = 7
5 → 31         // because         5*3*2 + 1 = 31
13 → 30031     // because 13*11*7*5*3*2 + 1 = 30031
31 → 223092871 // (largest possible output within `int32` range)

Note

This is very similar to, yet not identical with A006862: your solution must output a number belonging to that sequence. The difference is that your solution must work for inputs that are primes, while A006862 recognizes any natural number (including 0).

If your solution is function f(), the following equivalence must be true:

A006862(n) = M <=> f(A000040(n)) = M

A000040 is the sequence of primes, therefore A000040(n) can be read as "n-th prime number".

\$\endgroup\$
  • \$\begingroup\$ In its current state I would have to vote to close this as unclear what you're asking. 1. What should the output be for input 13? 2. Why is the output for 31 not 200560490131? 3. How does it differ from A006862? If these issues are fixed then it likely becomes a duplicate of codegolf.meta.stackexchange.com/a/11638/194 \$\endgroup\$ – Peter Taylor Apr 29 '17 at 18:20
  • \$\begingroup\$ @PeterTaylor, I hope my edit clarifies your doubts. \$\endgroup\$ – Szymon Apr 29 '17 at 22:50
  • 2
    \$\begingroup\$ Do you realise that 30031 = 59 * 509 and is therefore not prime? \$\endgroup\$ – Peter Taylor Apr 29 '17 at 22:59
  • \$\begingroup\$ Oh, that's a game changer: the challenge is obviously still valid, but now it has little meaningful interpretation. I guess I'll leave it abandoned for future reference of other people not understanding Euclid's theorem. \$\endgroup\$ – Szymon Apr 29 '17 at 23:21
0
\$\begingroup\$

Rewrite a number in the Munafo System

Output

The Munafo Alphabetic PT System (created by Robert Munafo) is a system of concisely writing very large numbers such that ordered values become lexicographically ordered when written. A full description (and some examples) of the system can be found in the link, but here's a series of steps to compute the string M(N) from a positive real number N:

  • If N < 10, then M(N) is simply the single digit of N, possibly followed by an factional part; that is, _ followed by any digits after the decimal place of N.
  • If 10 ≤ N < 100, then M(N) is the letter a followed by the two digits of N, possibly followed by an factional part.
  • If 100 ≤ N < 1000, then M(N) is the letter b followed by the three digits of N, possibly followed by an factional part.
  • If 1000 ≤ N < 10 000, then M(N) is the letter c followed by the four digits of N, possibly followed by an factional part.
  • If 10 000 ≤ N < 100 000, then M(N) is the letter d followed by the five digits of N, possibly followed by an factional part.
  • If 100 000 ≤ N < 10300, then M(N) is:

    1. the letter e
    2. exactly three digits, representing the exponent of N
    3. an underscore _
    4. any number of digits, representing the significand of N in standardized form.


    More specifically, a string M(N) = ex1x2x3_y1y2y3... represents the value N = y1.y2y3... × 10x1x2x3.

  • Finally, if 10300N, then to determine M(N), we must first apply the following recursive process:

    1. Set T = 0 and R = N.
    2. If R < 10300, then break out of this process.
    3. Otherwise, set T = T + 1, set R = log10(R), and return to step 2.


    (Effectively, this sets N equal to 1010R with T nested exponents.) Now, with our values of T and R, the value of M(N) is written as follows:

    1. the letter e
    2. the substring M(T)
    3. an underscore _
    4. the substring M(R).

...and that's the entire system. I apologize if anything I said was unclear or vague; in that case, you should definitely check the link for more detail.

META: Is there anything here that can be clarified?

Operation

As input, your program or function is to take three nonnegative numbers X, Y, and Z. X and Z are guaranteed to fit in your language's default integer type, and Y can fit in the default floating point type. These three values represent the number N = 10Y × 10Z, with X initial exponents as before. From here, the challenge is simple: given X, Y, and Z describing a value N, output the Munafo string M(N).

Test cases

META: Still figuring these out. Will probably end up using at least a couple from the link. Suggestions are welcome.

\$\endgroup\$
0
\$\begingroup\$

Same Same But Different

This challenge involves two similar digit-based routines each of which, when given a non-negative integer seed, produce eventually periodic sequences.
The goal is to find the nth seed number (counting up) that does not define the two sequences to be the identical (by virtue of the order of its digits), yet does yield sequences of equal pre-periodic length.


Reverse & Absolute Difference Routine.

A reverse and difference sequence may be defined in any given base for a non-negative seed by iteratively taking the absolute difference between the number and itself with its digits reversed.

An example:

The number 54410 is 10001000002;
The reverse of which is 00000100012, which is 1710;
The difference between the two is 52710;
Repeating the process we have 52710 = 10000011112, reversed is 11110000012 = 96110, and a difference of 43410;
Repeating again, 43410 = 1101100102, reversed is 0100110112 = 15510, and a difference of 27910;
Repeating again yields 18610, then 9310, and then 0, which will continue to yield 0.

  • So, the pre-periodic reversal and difference base-2 trajectory length of 54410 is six.
    - since the iterative procedure may be performed six times before a periodic part, {0}, is reached:

54410, 52710, 43410, 27910, 18610, 9310, {0}

  • Similarly the pre-periodic reversal and difference base-2 trajectory length of 9310 is one
    ...and the pre-periodic reversal and difference base-2 trajectory length of 0 is zero (as it is in any base).

Note: Ignoring the absolute part of this definition, many low bases have their iterations listed at the OEIS: base-2, base-3, base-4, base-5, base-6, base-7, base-8, base-9, base-10, base-11, base-12, base-16, base-20.


Kaprekar Routine.

A similar, but different sequence is the Kaprekar sequence where the absolute difference above is replaced by the difference, and the reversal is preceded by a digit-sort.

An example:

The number 83638110 is CC31D16;
Which, reverse-sorted is DCC3116, which is 90424110;
And forward-sorted is 13CCD16, which is 8110110;
The reverse-sorted less the forward-sorted is then 82314010;
Repeating the process we have 82314010 = C8F6416, reverse-sorted is FC86416 = 103434010, forward sorted is 468CF16 = 28897510, and the subtraction yields 74536510;
Repeating again yields 67983010, then 67167010, then 80682010, then 75352510, then 67167010...

  • Notice that we have hit a periodic part of the sequence, {67167010, 80682010, 75352510}, so the pre-periodic Kaprekar base-16 trajectory of 83638110 is four:

83638110, 82314010, 74536510, 67983010, {67167010, 80682010, 75352510}

Note:: Once again the OEIS lists the iterations for some low bases: base-2, base-3, base-4, base-5, base-6, base-7, base-8, base-9, base-10.
Furthermore some pre-periodic sequences also exist: base-2, base-3, base-4, base-5, base-6, base-7, base-8, base-9, base-10.


Same same...

Any number whose digits are already either forward or reverse sorted in some base will have the same pre-periodic trajectory length for both sequences in that base, since the resulting procedure will be identical.

There are, however, numbers which have the same pre-periodic trajectory length in both sequences even though their digits in the base in question are not already sorted.

The first example in base-10 is 107 which has a pre-periodic trajectory length of three in both sequences:

Reverse & difference: 107, 594, 99, {0}
Kaprekar: 107, 693, 594, {495}

Aside: Any number with less than three digits will always be sorted or reverse-sorted, as will the first three digit number, so the only others to actually check in base-10 before finding 107 would be [102-106].


The challenge

Write a program or function which when provided with a positive* integer, n, and an integer base greater than one**, b, outputs the nth number (in the natural ordering) which has neither sorted nor reverse-sorted digits in the given base, b, but which does have the same pre-periodic trajectory length for both procedures defined above in the given base.

The input and output are as flexible as ever, however the input and output numbers (or string or list representations thereof) are to be in a single unchanging base, consistent between input and output - for most this will probably mean base ten, but any single base is acceptable, as long as it is consistent across any invocations of the code.

* Feel free to have the counting (i.e. n) be 0-based if you would prefer, just say in your submission.

** Note there are no such numbers in base-1, so the code does not need to handle b=1 as an input.


Test cases (one-based n, IO in base-10)

 n     b  result
 1     2      17
 2     2      33
 3     2      51
 4     2      65
 5     2      73
 6     2      85
17     2     297

 1     3      28
 2     3      29
 3     3      32
 4     3      48
 5     3      51
 6     3      55
17     3     101

 1    10     107
 2    10     160
 3    10     161
 4    10     172
 5    10     186
 6    10     187
17    10     329

 1    16     264
 2    16     266
 3    16     355
 4    16     373
 5    16     400
 6    16     401
17    16     522

 1   257   66179
 2   257   98949
 3   257   98951
 4   257   98953
 5   257   98955
 6   257   98957
17   257   98979

 1  1234 1523375
 2  1234 2242181
 3  1234 2243417
 4  1234 2244655
 5  1234 2245897
 6  1234 2247147
17  1234 2260770
\$\endgroup\$
0
\$\begingroup\$

Formula 1 2016 standings

The Formula 1 2017 season is well underway, but I thought that the final standings could be good idea for a challenge.

The task is to print the standings at the end of 2016 season. This is how the table looks like:

1  N Rosberg    385
2  L Hamilton   380
3  D Ricciardo  256
4  S Vettel     212
5  M Verstappen 204
6  K Raikkonen  186
7  S Perez      101
8  V Bottas     85
9  N Hulkenberg 72
10 F Alonso     54
11 F Massa      53
12 C Sainz      46
13 R Grosjean   29
14 D Kvyat      25
15 J Button     21
16 K Magnussen  7
17 F Nasr       2
18 J Palmer     1
19 P Wehrlein   1
20 S Vandoorne  1
21 E Gutierrez  0
22 M Ericsson   0
23 E Ocon       0
24 R Haryanto   0

The table is divided into 3 columns: position at the end of season, driver name and points. In each of the columns, the contents can be aligned to left or to right for each column independently. If all columns are aligned to right, the output will look like this:

 1    N Rosberg 385
 2   L Hamilton 380
 3  D Ricciardo 256
 4     S Vettel 212
 5 M Verstappen 204
 6  K Raikkonen 186
 7      S Perez 101
 8     V Bottas  85
 9 N Hulkenberg  72
10     F Alonso  54
11      F Massa  53
12      C Sainz  46
13   R Grosjean  29
14      D Kvyat  25
15     J Button  21
16  K Magnussen   7
17       F Nasr   2
18     J Palmer   1
19   P Wehrlein   1
20  S Vandoorne   1
21  E Gutierrez   0
22   M Ericsson   0
23       E Ocon   0
24   R Haryanto   0

The columns should be separated exactly by 1 space. Trailing spaces are allowed as well as 1 trailing newline.

This is competition - shortest answer wins.

\$\endgroup\$
  • \$\begingroup\$ Thanks for posting in the Sandbox before posting on the main site ;-) In its current state, the challenge seems like it's just about finding the shortest way to encode all the drivers' names and how many points each had at the end of the season. While this may be an interesting challenge for some, many users on the site may find it fairly boring with not much room for real innovation. (You can tag it kolmogorov-complexity, btw) \$\endgroup\$ – ETHproductions May 2 '17 at 15:30
  • \$\begingroup\$ While reading this, I had an idea for a challenge where you take in a driver's last name and output the three-letter abbreviation, but that would be rather boring because that's currently just the first three letters of each name... \$\endgroup\$ – ETHproductions May 2 '17 at 15:34
  • \$\begingroup\$ @ETHproductions That could be more interesting with MotoGP or Superbike drivers \$\endgroup\$ – AlexRacer May 2 '17 at 16:54
0
\$\begingroup\$

Golf me a golf-lang

In any programing language of your choice write me an interpreter (or compiler targetting a reasonable pre-existing binary) for a golfing language. You will be scored based on a combination of the length of the interpreter and the golfiness of programs in your (user created language). In particular your goal will be to minimize the following formula.

max((Interpreter Length in bytes),512)/16-25*("checkmarks")

A good answer will not only contain an interpreter, but also contain code samples and documentation to encourage use of your language.

The number of "checkmarks" a language has earned is the number of times an answer in your language has beat or tied with the best answer (out of languages which are submissions to this challenge) to an open, positively voted (score of +1 or higher) question (whatever the win criterion) which postdate your language and were not asked by its creator(s) (in the event of a community wiki submission).

Your language will now be in a meta-competition around stack exchange, and you can earn checkmarks if other people choose to win other challenges with your competition.


Note that use of eval (or similar) is banned. You may write your interpreter/compiler in any preexisting programming language, and your language that you implement may be as similar as you wish to currently existing programming languages.

\$\endgroup\$
  • \$\begingroup\$ I'm worried that crafting a good solution to this will take a lot of time (thus meaning that late answers are fairly common) – it is language-design, after all – but the victory condition means that there's a hard limit to how long answers can arrive. Perhaps the languages should be somehow tested on how they fare on questions that postdate the languages themselves? \$\endgroup\$ – user62131 Apr 12 '17 at 21:23
  • \$\begingroup\$ If a challenge is selected which a language can't implement (e.g. one which requires a GUI, but the language only does I/O via stdio), how is it scored? \$\endgroup\$ – Peter Taylor Apr 12 '17 at 21:27
  • \$\begingroup\$ @PeterTaylor I decided to go a completely different way, challenges your language cant complete neither hurt or help you. \$\endgroup\$ – Rohan Jhunjhunwala Apr 12 '17 at 22:26
  • \$\begingroup\$ @ais523 I restructured the challenge, I liked the idea of being tested based on how you fare on languages that post date yourself, this way later answers are at a disadvantage, but they can still compete (and win). \$\endgroup\$ – Rohan Jhunjhunwala Apr 12 '17 at 22:27
  • 2
    \$\begingroup\$ There are plenty of good reasons to not award an accepted answer tick (e.g. some challenges have a reason to preserve the sort order), so not all challenges will have one. Change that to count questions on which your language has the best answer or tied for the best answer (based on the challenge's victory condition), and I like the new scoring. \$\endgroup\$ – user62131 Apr 12 '17 at 22:29
0
\$\begingroup\$

How many times will you have to golf a quine?

For this challenge, you must create a programme which takes an integer x and outputs its source x many times.

Rules

  • This is codegolf, the programme containing the least amount of bytes wins.

  • If you submit a function, the function must take x as a parameter and either return or print the body of the function x many times to STDOUT

  • If you submit a lambda, it is not required for you to assign it to a variable

  • Standard loophole restrictions apply.

  • Empty programmes are forbidden

\$\endgroup\$
  • \$\begingroup\$ There's really no reason not to use code formatting for x. The image doesn't even load for me, I had to check the markdown to see what you're trying to say. \$\endgroup\$ – Rɪᴋᴇʀ May 2 '17 at 17:53
0
\$\begingroup\$

Steal my credit card

recently a lovely man named Boris that I met online sent me a copy of an album that I didn't even know was released yet, the 16kb '.exe' ('EXtremely Excellent-music' apparently) file didn't open, but I did notice that it had managed to make some charges against my credit card, now I'm normally very secure in my banking, I don't write passwords down at all, and I keep my bank details in a '.txt' (Truly eXceedingly proTected) file, so I'm not sure how the hackers managed to get access, to confirm how secure I am:

  • I keep a .txt file named 'info.txt' in my documents folder
  • There's lots of unimportant information in this
  • I store the credit cards in a specific format
  • All of my credit cards have the same number of digits in the number and cvv
  • the 'Type' of card may be different, but it will always be in the format Cardtype - MM/YY
  • I don't format anything else in a similar manner, you can assume that this is the only two lines together.

Example:

Visa - 10/18
4024007172038209/571

(not a real credit card, i'm not an idiot)

which corresponds to:

Type - MM/YY (Expiry date)
CREDIT_CARD_NUM/CVV

The format will always match:

[a-zA-Z]+ - \d{2}/\d{2}\r?\n\d{16}/\d{3}

so it's very difficult to be read by any automatic parsing program.

my insurance doesn't believe me, so I'm here to prove that it's basically impossible, and since we all know programmers are actually just hackers with day jobs, I figured you would all be able to help me.

after adding all of the default Java libraries together and doing some math I believe there's almost no room left for any actual code in the exe file he sent me, so please try and keep the program as short as possible.

The Challenge:

write a program which takes no arguments, and when run will:

  • read in a file named 'info.txt' from the same directory the program is run in.
  • somewhere in the file, two lines will correspond to the above format
  • return only those two lines
  • any amount of leading or trailing white-space is allowed.
  • you can assume one credit card per file
  • you do not need to do any validity checks on the card number etc.

attached is my original info.txt if you want to test against it, but it should work with any credit card number, that way it will be more believable.

[gdrive link to info.txt]

This is so shortest code in each language wins.

Any code, interpreted or compiled, on any system, in any language is valid.

\$\endgroup\$
  • \$\begingroup\$ It's probably best that the victory condition isn't mentioned in just the fluff at the start; I missed it first time I read this. You probably need to confirm what counts as a credit card number or as a CVV. Given the talk about .exe files in the fluff, you should also confirm what languages are allowed (it's likely best if you allow any language, even interpreted languages). \$\endgroup\$ – user62131 May 5 '17 at 12:06
  • \$\begingroup\$ @ais523 added some more clarification there, and a regex to match the two lines. \$\endgroup\$ – colsw May 5 '17 at 12:23
  • \$\begingroup\$ Minor correction: the second Z in the regex should be capitalized (should be [a-zA-Z] not [a-zA-z]) \$\endgroup\$ – Business Cat May 5 '17 at 13:56
  • \$\begingroup\$ @BusinessCat oopsie, thanks. \$\endgroup\$ – colsw May 5 '17 at 15:14
0
\$\begingroup\$

Is the line closed?

Given input consisting of only whitespace characters and -/\|, tell if the line created by -\/| is closed.

For this challenge, \ points one character up and to the left, as well as one character down and to the right. / points up and to the right, and down and to the left. | points one to one character above and below it. - points one character to the left and right of it.

# means it is being pointed to.

#
 \
  #

  #
 /
#

#-#

#
|
#

A line is a bunch of /\-| characters that point to each other.

     /---\
\    |   |
 \---/   \

The characters - and | cannot validly point to each other. Similarly, / and \ cannot point to each other either.

-| = INVALID

|
-  = INVALID

\
 / = INVALID

 /
\  = INVALID

A closed line is one where each of its characters validly point to another of its characters.

/--\
|  |
\--/ = CLOSED

\--\
|  |
\--/ = NOT CLOSED

---- = NOT CLOSED

Your task, as said above, is to write a program that says if a line is closed.

Test cases coming soon.

\$\endgroup\$
  • \$\begingroup\$ Your -/ connections violate your own specification. I think the clearest specification would be to enumerate all possible legal pairs of connected line segments. \$\endgroup\$ – user62131 May 8 '17 at 13:47
  • \$\begingroup\$ @ais523 My mistake, I will fix both this and the other. \$\endgroup\$ – Comrade SparklePony May 8 '17 at 14:14
0
\$\begingroup\$

Determine if a relation is an equivalence relation

(Content to be added.)

Sandbox

\$\endgroup\$
0
\$\begingroup\$

Uncompress a permutation

I have a number of permutations, of which this is an example:

[0] 1 2 3 15 14 26 27 28 29 30 31 32 33 5 4 16 17 18 19 20 21 22 23 35 34 6 7 8 9 10 11 12 13 25 24 36 37 38 39 [40]

(0 is used for 0-indexed permutations and 40 for 1-indexed permutations.) In order to save space, I want to compress the permutation by reducing each ascending run of consecutive numbers to its first element, giving:

0/1 15 14 26 5 4 16 35 34 6 25 24 36

This compression method is invertible, because each missing element from the compressed form must follow its predecessor among the integers.

Your challenge is to write a program or function that takes a compressed permutation as input and returns an uncompressed permutation. Your input will consist of an array or list or other reasonable type representing the compressed permutation, plus an integer number of elements in the uncompressed permutation. Examples:

[0], 2 -> [0, 1] (0-indexed)
[1], 2 -> [1, 2] (1-indexed)
[6, 2, 0], 8 -> [6, 7, 2, 3, 4, 5, 0, 1] (0-indexed)
[7, 4, 1], 9 -> [7, 8, 9, 4, 5, 6, 1, 2, 3] (1-indexed)

In order to make the compression worthwhile I obviously need as short a decompression routine as possible, so this is a challenge.

\$\endgroup\$
  • \$\begingroup\$ I don't think there's actually a specification of the decompression routine, and the one which I would reverse engineer from the examples at the end is not compatible with the first example. \$\endgroup\$ – Peter Taylor May 8 '17 at 14:34
  • \$\begingroup\$ I believe the specification is just "for each number that doesn't appear in the compressed permutation, place it to the right of that number minus 1". It might be worth specifying that in the question. \$\endgroup\$ – user62131 May 8 '17 at 15:11
  • \$\begingroup\$ @PeterTaylor The specification is "Create a permutation of the first n integers which, when compressed by removing consecutive numbers after the first, results in the input array/list". \$\endgroup\$ – Neil May 8 '17 at 18:33
  • \$\begingroup\$ I've made an edit which I think makes that clearer. \$\endgroup\$ – Peter Taylor May 8 '17 at 21:24
0
\$\begingroup\$

Friendly Reputation Competition

Challenge

Given a list of user IDs, output the IDs of the two applicable people whenever someone's reputation surpasses the others.

Specifics

Let's take me (id 46249) and programmer5000 (id 58826) as examples. At the time of posting, our reputations are quite close.

Your program has to update at a consistent rate, and at least once every 1 minute (+/-5%). When it updates, it should check for the reputation of each of the users specified, and output "<ID> surpassed <ID>" for all instances of such an action, optional trailing whitespace, mandatory trailing newline.

When does someone "surpass" someone else?

Take person A and person B. If person A has less rep than or the same amount of rep as person B at iteration i, and then strictly more rep at iteration i + 1, your program should output <ID-A> surpassed <ID-B> on iteration i + 1.

Other Rules

  • You may ignore the daily SE api quota limit; your program must theoretically be able to run infinitely though.
  • Input is a list of user IDs as integers or strings
  • Output is indeterminate
\$\endgroup\$
  • \$\begingroup\$ This is close enough to the Dennis vs Martin question that IMO it would be a dupe. \$\endgroup\$ – Peter Taylor May 11 '17 at 9:39
  • \$\begingroup\$ @PeterTaylor I would disagree; that one runs once and finds who has higher reputation, whereas this challenge asks to keep watching the reputation and waiting for when people surpass each other. \$\endgroup\$ – user42649 May 11 '17 at 12:49
  • \$\begingroup\$ Wrapping a trivial loop round something does not make it substantially different. \$\endgroup\$ – Peter Taylor May 11 '17 at 13:11
  • \$\begingroup\$ @PeterTaylor I was thinking mainly the difference is finding clever ways to remember the current rep order and check when people are passing each other's rep; that is, not just only comparisons, but also remembering configurations and cross-comparing them. \$\endgroup\$ – user42649 May 11 '17 at 13:12
0
\$\begingroup\$

An implementation of a game called Nomic

Nomic is a game where you can change the rules. Humans are biased judges though, so let's have a computer run the rules! (Note that there are many variations of Nomic. Below is just one example.) Since you're minimalists, you want the original ruleset to be as short as possible.

Your program first accepts as input a list of players. You must be able to accept any list of 2 to 16 unique alphanumeric usernames (you may assume that the list of players names are valid according to this criteria).

Next print The name of this game is nomic. The goal is to get the last line of output of this program to be "[username] is the winner!", where [username] is your username.

Now, for each player print [username], do you want to propose a revision to the rules? If so, type the revised code below: where [username] is the player's username. (This input must be able to accept multiple lines.) If the input is empty, proceed to the next player.

If not, for each player print [username], do you want to accept or reject this change to the rules?(y/n), where [username] is the player's username. (You may assume input to this will either be y or n.) If the number of ys are more than the number of ns, execute it (in the language you are writing the implemenation). If not, proceed with the next player.

If the code executes without an error, the program ends. If not print The ruleset proposed by [username] has crashed. The game will proceed with the original ruleset. where [username] is the players username. Then proceed to the next player after them.

Note: After all the players have either proposed a rule or passed, start with the first player again.

This is . The shortest Nomic implementation wins! (You get 0 characters off your score if you show an example game you played with your friends. This bonus is doubled if all the revised rulesets are golfed.)

\$\endgroup\$
  • \$\begingroup\$ You say a computer has to "run the rules", so is each rule typed by a user an executable piece of code? Basically, your description of what the implementation needs to look like is extremely vague. Be specific. \$\endgroup\$ – mbomb007 May 12 '17 at 16:55
  • \$\begingroup\$ Having long hardcoded strings in a challenge is generally a bad idea unless it's a compression challenge, as the question will be mostly about compressing the strings rather than about what it's meant to be about. One possibility is to not count the strings against the byte count if they appear literally in the code. \$\endgroup\$ – user62131 May 12 '17 at 17:01
  • \$\begingroup\$ @mbomb007 the rule should be a piece of executable code. If it isn't, the program announces the error. \$\endgroup\$ – PyRulez May 12 '17 at 17:14
  • \$\begingroup\$ @ais523 that's a little tricky since it involves a little bit of string splicing. Is there a way around that, or should I just shorten them? \$\endgroup\$ – PyRulez May 12 '17 at 17:15
  • 3
    \$\begingroup\$ Probably best at this point to just use codes for the various situations, e.g. using just V to request someone to vote. \$\endgroup\$ – user62131 May 12 '17 at 18:00
0
\$\begingroup\$

Compute Area of Convex Hull of Roots of Polynomial

Given a nonzero polynomial with integer coefficients, find the area of the convex hull of the complex roots of the polynomial.

Details

The polynomial can be given in any reasonable format, e.g. as a list of coefficients. The area must be correct to 4 significant figures. You can assume that the degree of the polynomial is no larger than 8, and that the coefficients are less than 8^8 = 16777216, (and by Rouché's theorem the roots have therefore an absolute value of less than 8^8 + 1).

Example

The polynomial x^4 - 1 has the roots {1,-1,i,-i} which form the vertices of their convex hull, which is a square of sidelength sqrt(2) so the total area is 2.

The polynomial x^5 - x has the roots {1,-1,i,-i,0}. But the convex hull is again given by the vertices points {1,-1,i,-i}.

The constant polynomial 1 has no roots, and therefore the convex hull of its roots is empty.

The polynomial x^2 - 1 has the roots {1,-1}, so their convex hull is just a line segment, which has no area.

In the following the polynomials are given as a list of coefficient of the monomials in descending degree. (i.e. the constant comes last)

[1,2,3,4,1] 2.0382
[1,2,3,4,5] 3.5830
[1,-1,1,-1] 1.0000
[a,b] 0 (where a != 0 and b arbitrary)
\$\endgroup\$
  • \$\begingroup\$ For what range of inputs must the area be correct to 4s.f.? \$\endgroup\$ – Peter Taylor May 13 '17 at 14:43
  • \$\begingroup\$ Oh I forgot to add that, thanks for mentioning! \$\endgroup\$ – flawr May 13 '17 at 14:44
0
\$\begingroup\$

Hidden Strings

This is real rough, I just wanted to get the idea down.

The strings utility that comes on many GNU/Linux distros finds the strings in executables and lists them. The goal of this challenge is to write a program that has a null-terminated string in the compiled executable (compiled languages only, sorry) but that string does not appear in the source. The scoring is the ratio of the length of the hidden string to the size of your source code.

The following constraints apply:

The string must be entirely dictionary words from todo dictionary with length greater than 2 concatenated together without spaces and without punctuation. If xyz and abc are words in the dictionary, the following is a valid string: xyzabcxyzabc, but the following is not xyabcz (assuming that it is not a concatenation of other strings in the dictionary). For those of you who care, if E is the dictionary of words of length greater than 2, then strings must be in E* where * is the Kleene star.

"Hidden" means that the string and its substrings may not appear as strings or characters in your source. This definition needs a bunch of work.

This challenge was supposed to be something like "Hey, how would you hide a funny string so that it doesn't appear obviously in the source, but does appear when someone looks at the executable". I welcome all suggestions because as I have it currently stated, I think there are a lot of problems.

\$\endgroup\$
  • \$\begingroup\$ I'm guessing that a minimal C program already contains a certain number of strings in the binary? Does this come down to creative you get with compiler flags, asking it to statically link as many libraries as possible? \$\endgroup\$ – Steve Bennett May 15 '17 at 4:28
  • \$\begingroup\$ I suggest specifying a particular string that has to be hidden, in order to prevent solutions based on the default behaviour of the toolchain. (This would also simplify the question somewhat) Additionally, that string should probably be banned from thing like the filename and the current directory. \$\endgroup\$ – user62131 May 15 '17 at 17:58
0
\$\begingroup\$

Write a TIO bot

Write a program/function which:

  1. Takes three strings Language, Code, and Input
  2. Do one of the following:

    1. Assume access to a browser open on https://tio.run/nexus/; click [data-id="Language"
  3. Go to https://tio.run/nexus/Language/

  4. Enters Code in the <textarea id="code">
  5. Enters Input in the <textarea id="input">
  6. Clicks the <span id="run">
  7. Waits for any of these things to happen:
    1. <textarea class="output"> changes
    2. <textarea id="debug"> changes
    3. 60 seconds pass
  8. Returns/prints the content of <textarea class="output">

Alternatively, you may use the TIO API.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'd allow people to use the API, instead of using the HTML. \$\endgroup\$ – Nathan Merrill May 15 '17 at 15:58
  • \$\begingroup\$ @NathanMerrill Added. But good luck finding out what it is. \$\endgroup\$ – Adám May 15 '17 at 16:23
  • \$\begingroup\$ The problem with the API is that it's bound to change until it becomes stable. Incidentally, this is why I'm not documenting it at this point, as nobody should use it while it's still in flux. \$\endgroup\$ – Dennis May 15 '17 at 18:20
0
\$\begingroup\$

Convert ambiguous dates to "the correct way" (YYYY-MM-DD)

A problem I run into often with spreadsheets of data is dealing with dates of unknown ordering.

XKCD says it best

Your task is to take a series of dates that are in one of the following three formats, and output them as YYYY-MM-DD:

  • DD/MM/YYYY
  • MM/DD/YYYY
  • YYYY-MM-DD

No other date formats are acceptable.

Since many dates are ambiguous, you must read all the dates to determine whether the set is MM/DD or DD/MM before outputting anything.

Your program must also detect the following error conditions and return an error code instead (with no other output):

  • -1: Unable to determine date ordering. (All dates provided could be DD/MM or MM/DD)
  • -2: Inconsistent date ordering. (There are dates provided that are definitely DD/MM and others that are definitely MM/DD, within the same set).
  • -3: Bad data. (There are things included that are not valid dates, as defined above, including things like 31/04/2017 and 12/1/1980).

For the purposes of this challenge, February always has 28 days, April, June, September and November have 30 days, and all others have 31 days. All years, from 0001 to 9999 are equivalent.

Sample input/output

['11/05/1988','12/12/1960'] => -1
['15/05/1988','03/18/2001'] => -2
['15/05/1988','31/06/1989'] => -3
['15/05/1988','2014-02-02', '18/03/2001'] => ['1988-05-15','2014-02-02', '2001-03-18']
['05/15/1988','03/18/2001'] => ['1988-05-15','2001-03-18']

I/O

You can receive data in whatever way is normal for your language (line-separated stdin, array of strings, whatever). You may assume that the data you receive is of the correct type (ie, your array won't contain integers, nulls etc), but may contain empty strings.

If outputting to standard output, errors can be sent to stderr, or as program termination code. If implementing a function, you can return an integer instead of an array, throw an error, or whatever seems natural.

Scoring

The score for your program is L - 2Y + 20D where:

  • L is the length of your code, in bytes
  • Y is 2017 minus the year in which the first version of the language you're using was published.
  • D is the number of times the letters 'date', in any case, appear consecutively in your code.

For the purpose of Y, all versions of Lisp are 59, C is 39, C++ is 32, all EcmaScripts are 20 etc. Languages are considered the same if they have the same name (other than the version number). (No cheating by using some golf language that happens to be called C though.)

Tags

(what else?)

\$\endgroup\$
  • 1
    \$\begingroup\$ I think your scoring mechanism isn't going to work. It's probably best you stick to plain old shortest code. \$\endgroup\$ – Okx May 16 '17 at 11:33
  • \$\begingroup\$ Any particular reason why? \$\endgroup\$ – Steve Bennett May 16 '17 at 22:11
  • \$\begingroup\$ Possible dup \$\endgroup\$ – Digital Trauma May 16 '17 at 23:17
  • \$\begingroup\$ @SteveBennett If your score decreases by 20 each time 'date' is in the code, then if someone fits an infinite amount of 'date' into a comment, they win. \$\endgroup\$ – Okx May 17 '17 at 9:28
  • \$\begingroup\$ It increases, not decreases...? \$\endgroup\$ – Steve Bennett May 17 '17 at 11:21
  • \$\begingroup\$ @DigitalTrauma They're both in the same ballpark but a lot of differences, including fundamental task (reformatting vs outputting a single probability), input formats (strict mm/dd/yyyy vs m-d-yy) etc. \$\endgroup\$ – Steve Bennett May 17 '17 at 11:24
0
\$\begingroup\$

Be the Richest Mammut!

The Game

This game is an adaptation of a board game called Mammut, and basically an optimization problem.

Each match contains five players and five rounds, in which every player participates. Every round starts with a bunch of tiles being flipped at random on one of their sides, and put in the middle stack The tile composition will be fixed, but has not been completely decided yet There will be 30-35 of them, and each of them will have two different sides, with exactly 15 different types of tiles, and about half of those only having one single instance available. A random player is chosen as the starting player for the first round, and performance will decide the starter for the following four rounds. In order, each player that doesn't own any tiles will take an action, and this will keep going on until every player has at least one tile. The actions available are:

  1. Take an arbitrary number of tiles from the middle stack.
  2. Take all of the tiles owned by another player, and put one of them back in the middle stack.

Obviously, you can take the entire middle stack, but if there is at least one other player without tiles and you take too many, he will most likely steal your tiles right after.

Scoring

Every player starts with 10 points, and if they end a scoring phase under zero, they will be given enough free points to go back to zero.

When everyone has tiles, the round is over, and we move on to scoring that round. Since this is played by bots and not humans, an infinite loop is possible, so after 1000 actions, the round will be stopped by force, and the players participating in the infinite loop who ended up empty ended will naturally end this round with a terrible score.

Scoring happens all at once, and you get (or lose) points according to the tiles you have, and the tiles the other players have. When scoring is done, we move on to the next round, or declare the winner if that was the fifth round.

The Tiles

There are different types of tiles, and you job is basically to find the best balance between them while not having enough to make your stack worth stealing.

  • Fire | The player who has the fewest fire tiles loses 5 points
  • Meat | The three players owning the most meat tiles get 8, 5 and 2 points respectively
  • Fur | Every fur tile gives you onw "fur point". During every round after the first, the player with the most fur points plays first. At the end of each round, the player with the most fur tiles gets the round number in points (1-5), while the one who has the least loses the round number in points.
  • Ivory Tile | Every Ivory tile gives you two points.
  • Axe Tile | (This one should be discussed) Every axe tile gives you one point, and every axe Tile obtained in the last round is Worth 3 points
  • Animal Tiles | There are 7 different animals (Bat, Opossum, Bunny, Buffalo, Squirrel, Beaver and Duck), and only one of each in the game. When you end the round with one, you "obtain" this animal, and getting the same one again will do nothing. At the end of the game, depending on the number of animals you have obtained, you get points. (0: 0, 1:0, 2:0, 3:4, 4:9, 5:15, 6:22, 7:30)
  • Mystery Tile | If you get a mystery tile, it will be turned around to reveal its other side during the scoring phase. The other side can't be another mystery tile or an animal tile.
  • Tie-Breaker Tile | This tile serves as a tie breaker. One side is the "clockwise" side, and the other side is the "counter-clockwise", so every round will contain a tie-breaker tile. During any and all ties during scoring, the tie-breaker tile decides who wins or loses.

Clockwise?

At the start of the game, every player will be given a random ID between 1 and 5. The player with ID 1 will start the game. Then, for the following rounds, the most fur points decides who starts, and the ID decides the order. Example: ID 3 has the most furs, then the order will be [3, 4, 5, 1, 2].

This is considered "clockwise". The counter-clockwise order would be [3, 2, 1, 5, 4]. This is important, because when dealing with ties, the tie-breaker tile takes the order into account.

If player 4 owns the clockwise tie-breaker tiles, and has 3 meats. Player 1 and 2 also have three meats. The first, second and third place in meat then go to players ID 4, 1 and 2 respectively. If everyone has 3 fires, except player 3 and 5 who have 1, then player 3 is the one to lose points. Having the tie-breaker tiles means you are first in the tie-breaking order, and that tile's visible side decide the rest of the order.

Challenge specifications

You must make a C# class that inherits from a "Player" class. You must also override the method

List<int> ChooseTiles(Dictionary<int, List<Tile>> otherPlayers, List<Tile> center)

This method takes a dictionary of player IDs and List of tiles (could be empty), that are each player's tiles at the moment, plus a list of tiles in the middle. You must return a list of integer, which are the IDs of the tiles you want. If you try to get tiles illegally (not following the instructions for taking an action, which are either any number of tiles from the middle or all tiles except one from a player), you will be asked to choose one more time, and if you fail to follow the rules, you will be counted as "attempting to cheat" and removed from the "playing" pool during this round, so you will get scored for an empty hand. The same thing goes for throwing exceptions and infinite loops (Execution lasting more than 5 seconds). You are given one more chance then given an empty hadn for that round.

Here is the class Player you will be inheriting from:

public class Player
{
    public int ID;
    public int currentPoints;
    public int currentFurs;
    public List<Tile> currentTiles;
    public List<TileType> animalsGotten;

    public Player(int id)
    {
        ID = id;
        currentPoints = 10;
        currentFurs = 0;
        currentTiles = new List<Tile>();
        animauxGotten = new List<TileType>();
    }

    public virtual List<int> ChooseTiles(Dictionary<int, List<Tile>> otherPlayers, List<Tile> center)
    {
        throw new Exception("Fake players don't get to play!");
    }

    public virtual string GetName()
    {
        return "Player";
    }
}

You should also override the GetName() function, but it is not required. You are allowed to create as many private functions or attributes as you want to store data during a game, but each match will create a new instance of your player.

The Tournament

tournament will be played in a round-robin fashion. You are not garanteed a match with every single combination of four opponents available, but you are garanteed at least one match in common with every other bot, and everyone will play the same number of matches. You will also not play twice with the same 5 players. The total number of matches will depend on the number of participants. For each match, the first player will get 5 points, and the others will get respectively 3, 2, 1 and zero points depending on their points earned during the match. Furthermore, and ties in points will not be resolved, and the points of the occupied positions split between tied players. This means that if the points are (40, 37, 37, 37, 35), the points are (5, 2, 2, 2, 0)

\$\endgroup\$
  • \$\begingroup\$ People usually don't like KotH challenges that are restricted to one language. See some other KotH challenges for ways to get around that. \$\endgroup\$ – Stephen May 16 '17 at 13:47
0
\$\begingroup\$

I have a large collection of fine art. My toddler is learning to use scissors and glue; lately she has started playing with my art collection. Fortunately she is really quite good with the scissors and cuts things up into perfect squares. She then uses glue to randomly tile the cut-up squares back into a new piece of art. For example, she reinterpreted my Mona Lisa (which wikipedia kindly hosts for me) as follows:

enter image description here

The following python script simulates what my toddler has done:

#!/usr/bin/python

import sys
import random
from PIL import Image

origname = sys.argv[1]

im = Image.open(origname)
width, height = im.size
width = (int(width + 99) / 100) * 100
height = (int(height + 99) / 100) * 100

im = im.crop((0, 0, width, height))

im2 = Image.new("RGB", (width, height), "black")

blocks = []
for x in range(width / 100):
    for y in range(height / 100):
        blocks.append(im.crop((x * 100, y * 100, (x + 1) * 100, (y + 1) * 100)))

random.shuffle(blocks)



im2.save("shuf" + origname)

Please excuse python skills - I'm still learning, but was happy to see how quick and easy it was to write this script. Polite code-reviews will be graciously accepted ;-)

It does the following:

  • loads the image whose file name was given as a command-line parameter
  • pads that image with black pixels such that the width and height are exactly divisible by 100
  • divides the image into 100x100 pixel blocks
  • randomly shuffles the blocks
  • reassembles the randomly arranged blocks back into a new image with the same size attributes as the (padded) original
  • saves the new image using the original filename prefixed with shuf

Your task is to write a program that takes the output of this script, analyses the edges of each 100x100 block and reassembles them back to the original picture.

Input:

  • an image filename. This may be passed at the commandline, via STDIN or even hard-coded, whichever is most convenient.

Output:

  • either output the a singular rearranged image to a differnent file, or display the singular rearranged output to the screen.

Input and output specs are intended to be lenient here, as filename-parsing is a non-goal of this question.

Other rules

  • The program must be able to correctly reassemble any random arrangement of the wikipedia Mona Lisa by the python script. Hard-coding of block transformations of the example image above is strictly not allowed.

  • It is understood that for some degenerate cases (e.g. chequerboard of 100x100) blocks it is impossible to correctly rearrange the image. In those cases it is acceptable to produce incorrect/undefined output. However I think in general for photo images and almost all "famous" artworks, reassembly should be possible. Works by Mark Rothko are a possible exception.

  • Common image manipulation libraries may be used (e.g. Python's PIL), but any APIs expressly designed for this purpose are strictly banned.

  • Standard “loopholes” which are no longer funny


Now my toddler got a hold of The Scream. This is the result that needs to be fixed:

enter image description here

Special thanks to Digital Trauma!

He wrote the original challenge and gave it up original post here

META:

I need to update the images and the script to not have rotations and to not have black bars. Any ideas?

\$\endgroup\$
  • \$\begingroup\$ The way to make this objective is to have a large list of images (like 50 or so), and require 100% accuracy. You should also reserve the right to regenerate the test cases if anybody is hardcoding the input. \$\endgroup\$ – Nathan Merrill May 16 '17 at 16:01
  • \$\begingroup\$ Please credit the question that the inspiration (or direct copy ?!?) came from. Also, please note the comments to that question very carefully. In its current form, there significant problems (up to and including impossible to get 100% accuracy). \$\endgroup\$ – Digital Trauma May 16 '17 at 22:52
  • \$\begingroup\$ @DigitalTrauma Sorry. I forgot to add that. It was a copy with edits based on you giving it up to gift exchange \$\endgroup\$ – Christopher May 17 '17 at 0:38
  • \$\begingroup\$ Somebody suggested using lossless image formats, which would help a lot in terms of edges now being exact matches. That might be less interesting though. Nathan suggested a large list of images, which could give it the test-battery tag perhaps? My two suggestions I believe are at odds. \$\endgroup\$ – nmjcman101 Jun 20 '17 at 19:25
0
\$\begingroup\$

Make some arrays

A recent post on The Daily WTF concerned the creation of four two-dimensional arrays of height n. Please write a function to create these arrays for me. Here is an example for n=4:

[[1] [[1 0 0] [[0] [[0 0 0]
 [0]  [0 1 0]  [0]  [1 0 0]
 [0]  [0 0 1]  [0]  [0 1 0]
 [0]] [0 0 0]] [1]] [0 0 1]]

Rules:

  • All four arrays must be two-dimensional. Arrays which have been flattened in any way are not acceptable.
  • You can write separate functions for each array, in which case your score is the total of the scores for each function.
  • Your functions can call each other, provided you include the name in your score. Otherwise unnamed functions are acceptable.
  • Rather than returning the array(s), you can be passed them in as an input parameter (e.g. using int** in C).
  • If your language has a builtin for inputting arbitrary data structures, then you can write a full program that outputs using the input format that the builtin would recognise.
  • Alternatively, you can write a full program that outputs source code for the arrays in your language.
  • All standard loopholes are banned.
  • This is , so the shortest function wins.
\$\endgroup\$
  • \$\begingroup\$ Hmmm, I wonder if you can reconstruct these four arrays if you just evaluate that code block as is. If so, that might be a fun challenge too. :) \$\endgroup\$ – Martin Ender May 17 '17 at 12:08
0
\$\begingroup\$

Parse a 4-dimensional array

A 2D array is fairly easy to represent in ASCII art, something like this:

1  2
6 24

One approach for a 3D array is to have a number of 2D arrays, with an extra blank line between each array:

1  2
6 24

1  2
4  8

Things get a little more complicated for 4D arrays though. The best you can do is to arrange a number of 3D arrays side-by-side, but with at least two spaces between each array:

1  2   1  2
6 24   3  4

1  2   1  4
4  8  27 64

So that I don't have to ban full programs, the challenge will be to input 4 (numeric) indices along with a 4D array which will be as some sort of string in the above format, and output the (numeric) 4D array element at those indices. For example, if the 1-indexed indices were 1, 2, 1, 2 then the result would be 4. Rules:

  • You must at a minimum support integers from 0 to 255, written in decimal.
  • The array will not be ragged, but you will not be given the size of the array. Any of the dimensions may be 1, so 0 0 0 0 0 is a valid input in 0-based indexing.
  • Numbers in the array will be consistently justified (please state whether you support left or right, or decimal justification if you support floating-point numbers), but the output must not contain any whitespace except for an optional trailing newline.
  • You may choose 0 or 1-based indexing.
  • You can choose row-major format instead of column-major format, as long as both outer and inner arrays have the same format. The first two indices will however always refer to the outer array and the last two indices to the inner array indexed by the first two indices.
  • You can assume that the indices will always be valid.
  • All standard loopholes are banned.
  • This is , so the shortest program or function wins.
\$\endgroup\$
  • \$\begingroup\$ some sort of string in the above format so no JSON? \$\endgroup\$ – Stephen May 17 '17 at 13:24
  • \$\begingroup\$ @StephenS Correct, you won't be given an actual array, you'll be given an ASCII-art printout of the array. \$\endgroup\$ – Neil May 17 '17 at 13:26
0
\$\begingroup\$

Prove the Undecideability of the Halting Problem

More information on the halting problem.

Either:

Create a program that, when given an input, no single program (which receives your source and your input) can determine if your program terminates, or

Create a function that, when given an input, no single program (which receives your source and your input) can determine if your function returns.

Your score is the byte count of your program plus the byte count of your input (or of the shortest input in the set of input that solves this problem).

Lowest score wins.

//I would love some input on my wording.

\$\endgroup\$
  • \$\begingroup\$ Can I make a request to an external URL until I get a 404? \$\endgroup\$ – programmer5000 May 17 '17 at 18:21
  • \$\begingroup\$ @programmer5000 can an external program determine whether your program will halt? For example, by pinging that URL themselves? \$\endgroup\$ – Stephen May 17 '17 at 18:24
  • \$\begingroup\$ Oh. Could I make a program that stops when it finds 5 points that prove the Happy Ending Problem wrong? \$\endgroup\$ – programmer5000 May 17 '17 at 18:29
  • \$\begingroup\$ @programmer5000 if your program stops with a given input, and another program can predict that it will stop with that input, your program does not match specs. No input is accepted input, but it is very unlikely that an undecidable program can come from no input AFAIK. \$\endgroup\$ – Stephen May 17 '17 at 18:32
  • \$\begingroup\$ @programmer5000 from the Wikipedia page it seems like that problem is already solved, so that program will terminate, so another program could predict that. Could be wrong though. \$\endgroup\$ – Stephen May 17 '17 at 18:33
  • \$\begingroup\$ Um. eval. It's one byte long in GolfScript. \$\endgroup\$ – Peter Taylor May 17 '17 at 21:35
  • \$\begingroup\$ @PeterTaylor you need to provide an input that is undecidable, and that counts towards your score. \$\endgroup\$ – Stephen May 17 '17 at 21:38
  • 2
    \$\begingroup\$ I don't think this is how the halting problem works... \$\endgroup\$ – Destructible Lemon May 17 '17 at 23:50
  • \$\begingroup\$ @DestructibleLemon You may be right; Wikipedia says a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. Do I need to require two inputs? This answer seems to contradict Wikipedia though. \$\endgroup\$ – Stephen May 18 '17 at 0:10
  • \$\begingroup\$ hmmm, you definitely could do this (make it an interpreter) but I'm not sure how much you have to do to make this work... as in what the simplest program would be \$\endgroup\$ – Destructible Lemon May 18 '17 at 0:17
  • 1
    \$\begingroup\$ @StephenS It doesn't require 2 inputs, it requires a pair (program, input). \$\endgroup\$ – Esolanging Fruit May 18 '17 at 1:07
  • 1
    \$\begingroup\$ It's the problem which is undecidable, not the instances. If you want to ask for a program which cannot be proven to halt or not halt, you have to specify the axiom system which can be used for the proof. See e.g. codegolf.stackexchange.com/q/79470/194 , codegolf.stackexchange.com/q/79620/194 \$\endgroup\$ – Peter Taylor May 18 '17 at 6:19

You must log in to answer this question.

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