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

2876 Answers 2876

1
41 42
43
44 45
96
1
\$\begingroup\$

Posted: Is this number secretly Fibonacci?

| |
\$\endgroup\$
1
\$\begingroup\$

Toy floating point coprocessor: ceil

Summary: implement the ceiling function for 16-bit IEEE 754 floating point numbers in logic gates, using as few gates as you can.

16-bit IEEE 754 floating point

For a more detailed description, see Wikipedia:Half-precision floating-point format.

The 16 bits are divided into three chunks: sign (1 bit), exponent (5 bits), mantissa (10 bits).

  • The sign is 0 for positive numbers and 1 for negative numbers.
  • The exponent is biased: interpret as an unsigned 5-bit number and subtract 15 to get the true exponent. Special cases are described below.
  • The mantissa is an unsigned 10-bit number with an implicit leading 11th bit which depends on the exponent.

If the exponent is 00000 (corresponding to -15), the number is subnormal. The implicit leading bit of the mantissa is 0, but there's a bonus factor of two, so the interpreted value is \$(-1)^{\textrm{sign}}\; 2^{-14}\; 0.\textrm{mantissa}\$, or (expanding the \$0.\textrm{mantissa}\$ binary notation) \$(-1)^{\textrm{sign}}\; 2^{-24}\; \textrm{mantissa}\$.

If the exponent is 11111 (corresponding to 16), the number is either infinite (if the mantissa is 0000000000) or a NaN.

For all other exponents, the implicit leading bit of the mantissa is 1, so the interpreted value is \$(-1)^{\textrm{sign}}\; 2^{\textrm{exponent}-15}\; 1.\textrm{mantissa}\$, expanded to \$(-1)^{\textrm{sign}}\; 2^{\textrm{exponent}-25}\; (2^{10} + \textrm{mantissa})\$

Ceiling function

The ceiling function maps real numbers to integers, rounding up. So if the input value is an integer, the output value is unchanged; if the input value is not an integer, the output value is the smallest integer greater than the input value.

Examples:

$$\begin{array}{c|c} x & \textrm{ceil}(x) \\ \hline -1 & -1 \\ -0.5 & 0 \\ 0 & 0 \\ 0.00001 & 1 \\ 1 & 1 \\ 1.8 & 2 \\ \end{array}$$

Corner cases

Given an infinity, the output must be the same infinity.

Given a NaN, the output must be a NaN, but it can be any NaN.

IEEE 754 floating point systems have signed zeroes. Given a zero, the output must be the same zero.

Gates and scoring

You must implement a logic gate with 16 inputs and 16 outputs. You may use any two-input logic gates and you may mix different types of logic gates. We idealise the gates: don't worry about things like fan-out limitations or propagation delays. The score is the number of gates, and the fewer the better. If you choose to explain your design by giving code which uses bitwise operation on integers, be sure to document clearly how many bits are being processed by each operation.

Test cases

TODO, but will cover both infinities, both signed zeroes, positive and negative subnormals, positive and negative integer values, positive and negative non-integer values, and a NaN.

| |
\$\endgroup\$
  • \$\begingroup\$ I assume 2-to-1 gate, or 2-to-any? \$\endgroup\$ – l4m2 Nov 16 '18 at 15:21
1
\$\begingroup\$

Minimize your standard deviation


The standard deviation of a collection of numbers is calculated in the following manner:

  1. Find the arithmetic mean of the collection.
  2. Find the difference of each item from the mean.
  3. Square each difference and sum them.
  4. Divide by the number of items in the collection minus 1.
  5. Take the square root.

Or, expressed mathematically:

$$ s = \sqrt{ \frac{ \sum^N_{i=1} (x_i - \bar x)^2 }{N - 1} }, $$

where \$N\$ is the number of items, \$x_i\$ is the \$i\$th item, and \$\bar x\$ is the arithmetic mean.

Challenge

Your challenge is to write a program or function in your language of choice that, given an array of bytes, calculates the standard deviation of the array. The catch: the standard deviation of the bytes in your code will be added to your score.

Rules

  • Input may be in any reasonable format (e.g. numbers separated by newlines or commas, an actual array or buffer, etc.)
  • You may assume that the items in the input are all integers \$0 \le n < 256\$.
  • You may assume that there are at least two integers in the input.
  • The output or return value must be the standard deviation of the array as calculated above, accurate to at least 2 decimal places (i.e. \$ \pm 0.005 \$)

Test cases

(test cases to come)

Scoring

The score of your code is its length in bytes, plus the standard deviation of its bytes (i.e. \$N + s\$). The code with the lowest score in each language wins.

(If you somehow find a language with a 1-byte built-in that fulfills the challenge, your score will just be 1. In the impossible case of a 0-byte built-in, your score will be \$0 + \frac{0}{-1} = 0\$.)

Sandbox questions

  • Is this too similar to the vanilla standard deviation challenge?
  • For non-golfing languages that primarily use ASCII, the standard deviation will likely be much lower than the byte count, leading to golfing the code being significantly more important than reducing \$s\$. How could this best be combated? \$\sqrt N + s\$? \$N + s^2\$? (where \$N\$ is the length of the code) Obviously I wouldn't want to just use \$s\$, as you could just append one byte (e.g. ; in many languages) over and over to lower it arbitrarily.
| |
\$\endgroup\$
  • \$\begingroup\$ Standard deviation was my enemy in algebra. \$\endgroup\$ – MilkyWay90 Nov 11 '18 at 1:19
  • \$\begingroup\$ It seems difficult to create a scoring that penalizes appending redundant bytes and that the shortest solution wouldn't always win. \$\endgroup\$ – lirtosiast Nov 20 '18 at 1:48
1
\$\begingroup\$

Calculate your Icy Score

| |
\$\endgroup\$
1
\$\begingroup\$

Classify arity of verbs inside trains in J

Related: Clearly parenthesize APL trains

Background

J is an APL-family language. While it inherits the basic train syntax from APL (take a look at the linked challenge above), J is more versatile with the introduction of [:, & and @ among many others. But the problem is, the more features a tacit expression has, the harder it is to read and understand what it does. Even worse, most of the built-in verbs have both monadic and dyadic usage, and some of them have two completely different meanings! So let's build a helper to classify the arity of verbs.

Notations

  • # is a monadic verb.
  • + is a dyadic verb.
  • [ is a special symbol called "cap" which can appear at specific positions inside a train.
  • @ and & are conjunctions, which take two verbs on both sides and form a single verb.
  • x and y are left and right arguments to a given train, respectively. If x is missing, the train is called monadically (with one argument y); otherwise, dyadically (with both arguments).

Basics

  • In a train of verbs, the last 3 verbs are recursively grouped.
  • Conjunctions bind from left to right.

Rules

Monadic
(# + #) y   =>  (# y) + (# y)
(+ #) y     =>  y + (# y)
([ # #) y   =>  # (# y)
(+ # + #) y =>  (+ (# + #)) y
(# + # + # + #) y => (# + (# + (# + #))) y
(# + [ # # + #) y => (# + ([ # (# + #))) y

Dyadic
x (+ + +) y   =>  (x + y) + (x + y)
x (+ #) y     =>  x + (# y)
x ([ # +) y   =>  # (x + y)
x (+ # + #) y =>  x (+ (# + #)) y    <= the 3-group is run monadically
x (+ + + + + + +) y => x (+ + (+ + (+ + +))) y
x (+ + [ # + + +) y => x (+ + ([ # (+ + +))) y

Conjunction &
(#&#) y   => # (# y)
x (+&#) y => (# x) + (# y)

Conjunction @
(#@#) y   => # (# y)
x (#@+) y => # (x + y)

How to determine arity of each verb

   (?  (? ?&?@?    ?) ?) y
=> (# d(? ?&?@?    ?) #) y    monadic 3-train: # + #
=> (#  (+ d?&?@?   +) #) y    dyadic 3-train:  + + +
=> (#  (+ d(?&?)@? +) #) y    conjunction binds from left; arity is determined from right
=> (#  (+ m(?&?)@+ +) #) y    dyadic `@`:  #@+
=> (#  (+  (#&#)@+ +) #) y    monadic `&`: #&#

Challenge

Given an expression that represents the structure of a J train, determine the arity of every verb in the expression.

Input & output

TBD

Test cases

TBD

Scoring & winning criterion

Standard rules apply. The shortest valid program or function in each language wins.

| |
\$\endgroup\$
1
\$\begingroup\$

How fast can I Flood-It?

There's a one-player game called Flood-It, in which the player must flood the whole board with one color within a certain number of moves.

  • The board is a two-dimensional square grid of size n.
  • At the start, each square in the grid is one of k colors.
  • A move consists of selecting a color, and doing a 4-connected flood fill with that color starting in the top left corner.

For example, selecting Red on this size-3 board with 4 colors:

GGE
RGB
RDE

causes the board to change to this—now the two already-red squares are connected to the top left:

RRE
RRB
RDE

After the further moves DBE, all squares are colored Emerald, and the game has been won in an optimal 4 moves.

Challenge

Given two integers n and k, output the number of moves required to win the game of Flood-It with those parameters, in the worst case over all possible arrangements of colors.

| |
\$\endgroup\$
1
\$\begingroup\$

mAkE a StRiNg EpIc

Now that the meme is mostly dead, we can have this challenge. It's pretty simple: take a string (either as stdin or a parameter to a function), and change the case to alternate capital and lowercase letters, starting with lowercase. Examples:

"Hello, World!" -> "hElLo, WoRlD!"
"PPCG" -> "pPcG"
"Ok now this is epic" -> "oK nOw ThIs Is EpIc"
"" -> ""

Rules:

  • Can take input as a parameter to a function or as stdin

  • Punctuation marks are left alone

  • Must not take any input other than the input string

  • It's , so the shortest code in bytes wins!

Sandbox questions:

  • The obvious one: is it a duplicate? I don't think so, but I don't know for sure.

  • Is it too trivial for some languages?

Thanks everyone!

| |
\$\endgroup\$
1
\$\begingroup\$

Find the best K year period to have invested

A stock index is a way of measuring the overall performance of the stock prices of a group of companies (which may change from time to time). An example from the US is called the S&P 500. An index fund is an investment that grows at the same rate as the underlying index.

Here are the annual returns for a hypothetical S&P 500 stock index fund for each calendar year from 1928 to 2017, expressed as a multiplier. So in 1927 you might say "the index went up by 37.88%" which I've represented here by 1.3788.

1.3788, 0.8809, 0.7152, 0.5293, 0.8485, 1.4659, 0.9406, 1.4137, 1.2792, 0.6141,  1.2521, 0.9455, 0.8471, 0.8214, 1.1243,  1.1945, 1.138, 1.3072, 0.8813, 1,  0.9935, 1.1026, 1.2178, 1.1646, 1.1178,  0.9338, 1.4502, 1.264, 1.0262, 0.8569,  1.3806, 1.0848, 0.9703, 1.2313, 0.8819,  1.1889, 1.1297, 1.0906, 0.8691, 1.2009,  1.0766, 0.8864, 1.001, 1.1079, 1.1563,  0.8263, 0.7028, 1.3155, 1.1915, 0.885,  1.0106, 1.1231, 1.2577, 0.9027, 1.1476,  1.1727, 1.014, 1.2633, 1.1462, 1.0203,  1.124, 1.2725, 0.9344, 1.2631, 1.0446,  1.0706, 0.9846, 1.3411, 1.2026, 1.3101,  1.2667, 1.1953, 0.8986, 0.8696, 0.7663,  1.2638, 1.0899, 1.03, 1.1362, 1.0353,  0.6151, 1.2345, 1.1278, 1, 1.1341,  1.296, 1.1139, 0.9927, 1.0954, 1.1942

Challenge

Given as inputs this array of annual returns and an array of size \$1\le K \le 89\$ non-negative real numbers (the amounts to invest in each year), write a program or function that outputs what would have been the best \$K\$ year period to have invested each amount in the array in this hypothetical index fund, assuming the returns from each year are reinvested at the beginning of the next year.

Rules

  1. This is , so the fewest bytes in each language wins.

  2. If you don't like the way I've represented the array of annual returns, you can change them to any other array of 89 numbers that you prefer. (SANDBOX NOTE: This is intended to allow for some input flexibility (people might prefer to use the given array minus 1, or the cumulative returns) but not too much (so that people don't cheat and change the array to some multi-dimensional monster that nearly solves the whole problem).)

  3. You can output the best \$K\$ year period in any consistent manner (e.g. 0-indexed or 1-indexed, the first or the last period to have invested, the entire range of years, the actual years themselvs, etc.) but you need to say what your output represents if it isn't obvious.

  4. In case of a tie, output any or all correct answers.

Example

Suppose the array consisted of \$[ 10000, 20000, 30000]\$.

If you had invested these amounts in 1928, 1929, and 1930 (the 1-indices 1, 2, and 3) you would have ended up with \$42743.10\$.

But if you had invested those amounts in 2015, 2016, and 2017 (the 1-indices 87, 88, and 89) you would have ended up with \$66722.66\$.

It turns out the best three year period to have invested these amounts would have been 1995, 1996, and 1997 (1-indices 68, 69, and 70).

Test cases

1-indexed, first year of optimal period

[ 1, 2, 3 ]                          ->  68
[ 1 ]                                ->   6
*any array of length 89*             ->   1
[ 1, 1 ]                             ->  27
[ 1, 2 ]                             ->   8
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]  ->  63
[ 1, 2, 3, 4, 5, 4, 3, 2, 1 ]        ->  64
* 1 repeated 20 times *              ->  53
| |
\$\endgroup\$
  • \$\begingroup\$ I remember there being a challenge about when to invest before. Have you checked for duplicates? \$\endgroup\$ – lirtosiast Nov 20 '18 at 22:52
  • \$\begingroup\$ @lirtosiast I did check. I did not see any non-King of the Hill investment questions. That being said it's not always easy to find dupes. \$\endgroup\$ – ngm Nov 21 '18 at 1:44
1
\$\begingroup\$

Exploring generalzations of Cheryl's birthday problem

In this challenge we will generalize the Cheryl's birthday problem to arbitrary finite subsets of pairs of integers

Challenge

Cheryl gives Albert and Bernard a finite collection of pairs of integers S. Cheryl chooses an element (x, y) from S and tells x to Albert and y to Bernard. Assume everyone speaks truthfully.

Albert says: "I don't know what x and y are, but I know that Bernard doesn't know". More precisely: Albert does not know what y is, but using only the information given in the first paragraph, the elements of S and the value x, Albert is certain that Bernard doesn't know what x is.

Bernard says: "At first I didn't know what x and y were ,but now I do". - That is, before Albert said anything, Bernard doesn't know what x and y are, but after Albert spoke, Bernard knew.

Albert says: "Now I also know what x and y are".

Your task is to write a computer program that takes as input the set S, and outputs a list of all possible values for the (x, y) that Cheryl chose, in any order. (therefore you must use a programming language that can handle lists of pairs of numbers). If there is no solution or that conversation is impossible, output an empty list.

This challenge is code golf, so shortest code in bytes wins.

Example Input and Output

Input:

[(1,1),(2,2),(3,3),(4,4)]

Output:

[]

There is no solution to this problem because the conversation is impossible. Knowing either x or y will result in knowing the other one. Therefore, it's impossible for Bernard to know y but not x.

Input:

[(5,15),(5,16),(5,19),(6,17),(6,18),(7,14),(7,16),(8,14),(8,15),(8,17)]

Output:

[(7,16)]

This is the original problem.

Input:

[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]

Output:

[]

The conversation is impossible as Bernard cannot deduce x from y and the fact that Albert knows that Bernard does not know x.

Input:

[(1,0),(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3),(3,4),(4,1),(4,3)]

Output:

[(2,2)]

If x was 1, then Albert cannot be sure that Bernard doesn't know x, because if y was 0, then Bernard would know that x was 1. Similarly for if x was 3. Therefore x was 2 or 4.

After Albert spoke, Bernard can eliminate x=1 and x=3, and then he can deduce what x was. If Bernard had y = 1 or 3, then Bernard could not distinguish between (2,1) and (4,1), or between (2,3) and (4,3). As Bernard knew, we must have y = 2. After Bernard spoke, Albert knew that y=2, and x=2.

| |
\$\endgroup\$
1
\$\begingroup\$

Sequences that sum to n

Barely too late for Fibonacci Day :(

Given a positive integer n, your challenge is to output a sequence of 1 and 2 that adds to n. For example, for input 8, acceptable outputs include 11111111, 2222, and 121211.

It's not quite that simple, though. Given n, the number of possible outputs is the nth term of the Fibonacci sequence (starting with F(0) = F(1) = 1); you must return each with equal probability. This means that the following Python 3 is invalid:

def foo(n):
  out = ""    # String output is by no means required.
  while n:
    a = min(random.randint(1, 2), n)
    out += str(a)
    n -= a
  return out

While this will return each allowed result with nonzero probability and everything else with zero probability, the distribution is not uniform. In particular, foo(3) is twice as likely to be 21 is it is to be 111 or 12.

Standard IO and loophole rules apply. Output is flexible, but you must use 1 and 2, not 0 and 1 or some other weird thing.

This is , so the shortest code (in bytes) wins! Happy golfing!

| |
\$\endgroup\$
  • \$\begingroup\$ Do you think there will be a choice of strategy for many languages? I have a hard time coming up with a language where creating each string and choosing one uniformly isn't the best approach. This isn't a huge problem, and otherwise I think this is a fine challenge. \$\endgroup\$ – FryAmTheEggman Nov 25 '18 at 18:46
  • \$\begingroup\$ @FryAmTheEggman I could see someone perhaps using a function of the remaining value to tweak probabilities, something that would choose 2 only a third of the time for n = 3. Not sure, though—I haven't yet given this a try :/ \$\endgroup\$ – Khuldraeseth na'Barya Nov 25 '18 at 23:56
1
\$\begingroup\$

Given element count, minimum GCD and maximum LCM, compute the number of distinct integer arrays

Inspired by a question in Turkish National Computing Olympiad.

You are given 3 numbers: n, x and y.

Compute the number of distinct integer arrays with n elements whose GCD is greater than x and lcm is less than y.

Test cases: (n,x,y -> result)

1,1,10 -> 10 // there are 10 1 element arrays with gcd>=1 and lcm<=10, which are [1],[2],[3],...[10].

I can not add much test cases because I could not solve the question (well, I got 10 points by writing a python script which outputs a c++ file which hardcodes the first subtask, but I think the does not count.), please help with test cases.

Rules: i/o is flexible. Standard loopholes are not allowed.

This is code-golf, so the shortest answer in every language wins.

| |
\$\endgroup\$
  • \$\begingroup\$ Should the specification be "greater than or equal"/"less than or equal"? \$\endgroup\$ – user202729 Nov 24 '18 at 17:26
  • \$\begingroup\$ But you still can make small test cases, right... \$\endgroup\$ – user202729 Nov 24 '18 at 17:29
  • \$\begingroup\$ greater than/equal and less than or equal. also, I can only generate cases with n=1 in reasonable time. i may try to write a n=2 or n=3 test-case too if that helps \$\endgroup\$ – Windmill Cookies Nov 24 '18 at 17:31
  • \$\begingroup\$ "Standard loopholes are allowed" - please rethink that. \$\endgroup\$ – Shaggy Nov 25 '18 at 14:22
  • \$\begingroup\$ ok, now they are not allowed \$\endgroup\$ – Windmill Cookies Nov 25 '18 at 15:07
  • \$\begingroup\$ Be advised that the shortest solution in many languages will be "filter all N element subsets of numbers less than Y by whether they meet the criteria" which will take Y^N time to run. \$\endgroup\$ – lirtosiast Nov 25 '18 at 19:46
1
\$\begingroup\$

Fully modular C program

Modularity means that instead of writing one big long procedure, we break up our logic into small, composable functions. We all know that modularity is a good thing. But why settle for a good thing when you can have the best thing? Let's make our programs fully modular. This means that each function must contain zero assignment statements and no more than one function call and one binary operator (if it contains more than that, that's a sign your function is getting too long and you need to break it up).

Example 1:

int multiply_add(int a, int b, int c) { return a * b + c; }

might become

int multiply(int a, int b) { return a * b; }
int multiply_add(int a, int b, int c) { return multiply(a, b) + c; }

Example 2:

int foo(int x)
    int y = x + 3;
    bar(y, y);
}

might become

int bar2(int y) { return bar(y, y); }
int foo(int x) { return bar2(x + 3); }

Sandbox note: I am working on the fully modular C verifier question before this one.

| |
\$\endgroup\$
  • \$\begingroup\$ Is there a name pool or we need to check if a name is used? \$\endgroup\$ – l4m2 Nov 23 '18 at 15:04
  • \$\begingroup\$ Sounds interesting. Is the input a less than fully modular program, and the required output any valid fully modular program that has identical behaviour? Also wondering if the score will be length of the solution code, or length of the output, or something else \$\endgroup\$ – trichoplax Nov 23 '18 at 20:59
  • \$\begingroup\$ @l4m2 You'll be responsible for generating new identifiers that don't clash. Though I'm thinking about making it actually a program where only the behavior of main() needs to be preserved. \$\endgroup\$ – feersum Nov 23 '18 at 23:44
  • \$\begingroup\$ @trichoplax Yes to the first question, and standard code golf with length of the modularizer. \$\endgroup\$ – feersum Nov 23 '18 at 23:45
  • \$\begingroup\$ Sounds interesting, theres going to be a lot of breaking sum_stuff(return a + b + c + d) down into sum_stuff(sum_pair(sum_pair(a, b), sum_pair(c, d))) like rearrangement. \$\endgroup\$ – alan2here Nov 24 '18 at 22:05
  • \$\begingroup\$ Needs more examples. I suggest Fibonacci and integer power. \$\endgroup\$ – Peter Taylor Nov 26 '18 at 17:10
  • \$\begingroup\$ I suggest you name the challenge "Monadic C" \$\endgroup\$ – Vaelus Nov 27 '18 at 0:08
1
\$\begingroup\$

Solve Newcomb's paradox

Newcomb's paradox is a problem that has been stumping philosopher's for decades. And, as anyone who uses reddit knows, a problem posed by a philosopher is best solved by a software engineer.

In Newcomb's paradox, you are presented with two boxes, A and B. You can either take B or take A and B. A contains $1000. B contains $0 if a predictor predicts you will take box A and $1000000 if it predicts you will not take box A.

For this challenge, the predictor will be an execution function or command, such as python's exec function, or the bash eval command. Therefore, you must use a programming language that has one.

Therefore, to solve Newcomb's paradox your program must:

  • Output the string "B" when run with an eval function.
  • Output the string "A+B" when run normally.

This will allow you to win $10001000.

This is , so the shortest answer wins!

| |
\$\endgroup\$
  • \$\begingroup\$ Adequately defining "an eval function" is notoriously difficult, and that lack of clarity is compounded here by the implicit quantifier in "run with an eval function". Does this mean that there must exist a function which takes a string and executes it as code, and the answer should state what this function is; or does it mean that the function must detect when run by any function which takes a string and evaluates it as code? \$\endgroup\$ – Peter Taylor Nov 29 '18 at 12:46
  • \$\begingroup\$ @PeterTaylor I was thinking of a specific eval function that the answer specifies. It should be built into the language though (since its trivial if you make your own). You are right though about the definition of an eval function being vague. Do you think the challenge is salvageable with some modifications? \$\endgroup\$ – PyRulez Dec 1 '18 at 22:41
  • \$\begingroup\$ I'm not sure. It would be good to get some input from a LISPer (where AIUI eval is trivial). I think that .Net is probably an example of a situation where "built in" is imprecise (I'm not sure that there is exactly an eval method for strings in the standard library, but I think it's fairly straightforward to write one with System.CodeDom.Compiler, and third party libraries exist which do that). Then there's a question as to whether an eval method must accept a string, or whether detecting the difference between f() and f.invoke([]) (JavaScript, I think) or similar counts. \$\endgroup\$ – Peter Taylor Dec 1 '18 at 23:08
  • \$\begingroup\$ @PeterTaylor I am thinking of eliminating the eval function aspect entirely. Any ideas as to two different conditions under which to run a program that would be in the spirit of Newcomb's paradox (in a cheeky way)? \$\endgroup\$ – PyRulez Dec 1 '18 at 23:14
1
\$\begingroup\$

Output The End Poem. Outputting as array, or with only one \n or three \n to separate sentences, etc. are fine. Shortest code win.

Upvote to prefer: You can take an input containing all letters in lowercase or uppercase

Downvote to prefer: You can take an input containing all letters in their original cases(upper/lower)

P.S. The two old choices are too similar

Comment if duplicate, fell the length is bad, etc

| |
\$\endgroup\$
  • \$\begingroup\$ I don't see why this isn't a duplicate of codegolf.stackexchange.com/q/6043 \$\endgroup\$ – Peter Taylor Nov 22 '18 at 16:13
  • \$\begingroup\$ @PeterTaylor You're given the text as input and only need to insert the spaces. \$\endgroup\$ – user202729 Nov 22 '18 at 16:13
  • \$\begingroup\$ Optionally, (in the second option) you're allowed to encode (part of) the data into the case of the input. \$\endgroup\$ – user202729 Nov 22 '18 at 16:14
  • 4
    \$\begingroup\$ "Upvote/Downvote" to prefer isn't actually the right approach for the sandbox, votes indicate likelihood of the challenge being well-received on main. \$\endgroup\$ – Erik the Outgolfer Nov 22 '18 at 16:29
  • \$\begingroup\$ @EriktheOutgolfer Any other suggestion? \$\endgroup\$ – user202729 Nov 22 '18 at 16:32
  • \$\begingroup\$ @EriktheOutgolfer The "right" way it was doesn't work fine, usually too inconsistant to main; also occupying the vote for other usage make like/dislike go to comment for clearer reason \$\endgroup\$ – l4m2 Nov 23 '18 at 0:18
  • \$\begingroup\$ I vote all letters in their original cases. Inserting spaces and punctuation is enough of a challenge in itself. \$\endgroup\$ – lirtosiast Nov 29 '18 at 8:27
  • \$\begingroup\$ @lirtosiast Uppercase only be first letter, I and PLAYERNAME I see. Taking input in original cases mean possible ability to learn from cases how to insert spaces \$\endgroup\$ – l4m2 Nov 29 '18 at 12:44
1
\$\begingroup\$

Sums of Bessel Polynomial Coefficients [WIP]

This is https://oeis.org/A001515.

Interesting alternate characterizations include:

Equivalently, number of sequences of n unlabeled items such that each item occurs just once or twice (cf. A105749). - David Applegate, Dec 08 2008

Numerator of (n+1)-th convergent to 1+tanh(1). - Benoit Cloitre, Dec 20 2002

a(n) is also the numerator of the continued fraction sequence beginning with 2 followed by 3 and the remaining odd numbers: [2,3,5,7,9,11,13,...]. - Gil Broussard, Oct 07 2009

Also, number of scenarios in the Gift Exchange Game when a gift can be stolen at most once.

| |
\$\endgroup\$
1
\$\begingroup\$

Compressed RSA keys

Silly cops-and-robbers idea.

As computers get more powerful, RSA keys have grown longer and longer to maintain security. This makes it difficult to:

  • hand out your encryption key on business cards
  • recite it over the telephone
  • quickly scribble it down when you meet someone at a bar
  • etc.

But we are all programmers (maybe even that someone that you met in a bar), so let's come up with RSA keys that can be generated by very short programs. We should be careful, though, that these keys remain resistant to cracking.

Cops

Write a short program (or function) that outputs an RSA key. For this challenge, an RSA key is just any positive integer less than \$2^{1024}\$ that has a non-trivial divisor.

Your program must:

  • take no input
  • output the same number every time it's run
  • finish quickly (a few seconds at most)

Post your program, its language, and what it outputs.

Also, prove that you can use it as an RSA key. Provide a SHA-256 hash of a string that lists all the prime factors of your key.

Robbers

Crack the RSA keys! If an RSA key is the integer \$n\$; find any integer \$1<d<n\$ that divides \$n\$.

Scoring

A key is vulnerable to cracking for 7 days after it's posted. After that, it is considered safe and eligible for scoring.

Cops: The shortest uncracked program wins.

Robbers: Most cracks wins.

(Related: compress RSA public keys on crypto.SE)

| |
\$\endgroup\$
  • \$\begingroup\$ What's to prevent me from feeding random numbers into a 700-bit hash function until I get a semiprime, which I factor on huge amounts of cloud computing time and then post? No one can crack it unless they have a bigger computer. \$\endgroup\$ – lirtosiast Dec 7 '18 at 9:18
  • \$\begingroup\$ Nothing, I guess. It might cost you a lot of money to do that, though. \$\endgroup\$ – japh Dec 7 '18 at 9:37
  • \$\begingroup\$ Also for what it's worth, not all semiprimes have large factors, so you'd have to factor many of them until you get a strong one. The robber only has to factor the one you posted. \$\endgroup\$ – japh Dec 7 '18 at 9:39
1
\$\begingroup\$

Not a challenge, but not certain of the wording so trying it out here:


Tips for golfing in JSLint


What general tips do you have for golfing in JavaScript restricted to satisfying JSLint with default options? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to JSLint (e.g. "remove comments" is not an answer).

| |
\$\endgroup\$
1
\$\begingroup\$

Unjagged my array


Given a jagged array of integers, rearrange the integers such that

  • The shape of the jagged array is unchanged, and

  • The jaggedness of each subarray is minimized.

Here "jaggedness" is defined as the sum of the absolute differences in each subarray. If an array has only one element, then the jaggedness of that array must be 0, since there are no absolute differences to consider.

We only care about the differences in elements in the same subarray. So for example:

[[1, 2], [100]]

has a jaggedness of 1, since the first array has a jaggedness of \$abs(1-2) = 1\$ and the second array has a jaggedness of 0. We don't care that the difference between 2 and 100 is 98 since they are different subarrays.

Here's an example:

Input: [[16, 8], [15], [4, 42, 23]]
jaggedness of input: [abs(16 - 8)] + [0] + [abs(4 - 42) + abs(42 - 23)] =
8 + 38 + 19 = 65

One possible output: [[4, 8], [42], [15, 16, 23]]
jaggedness of this output: [abs(4 - 8)] + [0] + [abs(15 - 16) + abs(16 - 23)] = 4 + 1 + 7 = 12

Of course, this is one possible output. Any of these outputs would also have a jaggedness of 12:

[[4, 8], [42], [23, 16, 15]]
[[8, 4], [42], [15, 16, 23]]
[[8, 4], [42], [23, 16, 15]]

Clarifications

  • The input will always contain non-negative integers. The input will also always have a length >= 1, and all of the subarrays will have a length >= 1. This means that you must handle inputs as small as [[n]], where n is any non-negative integer.
  • If the input is already arranged to be as smooth as possible, it is acceptable for your code to output the integers in a different order, as long as this new order has the same jaggedness. For example, if the input was

    [[1, 2], [3, 4, 5]]
    

    then your program may return the input unchanged, or it may return

    [[5, 4], [1, 2, 3]] 
    

    or any of the other arrangements with jaggedness 3.

Fastest code

This is a challenge, so the submission with the shortest run time for a hidden test case will win. I will use 2 different test cases with different shapes, and your score will be the sum of the time for each. (I haven't yet decided how large these test cases should be. I might adjust them once submissions come in so that it takes an appropriate amount of time.)

All submissions will be tested on my machine:

  • Windows 10
  • i7-4790k
  • 8 GB RAM

You can use any language that is freely available on Windows 10. Please also provide instructions for running your submission. I will test each submission at my soonest convenience after it's posted, and then comment an unofficial score. After 1 week, I will test every submission, and post a leaderboard.

Test Cases

These test cases were generated with and verified by a python brute-forcer.

Input: [[1, 2, 9], [10, 11]]
Output: [[9, 10, 11], [1, 2]] (jaggedness 3)

Input: [[4, 8, 15], [16], [23, 42]]
Output: [[4, 8, 15], [16], [23, 42]] (jaggedness 30)

Input: [[45, 98, 9, 46], [48, 53, 59], [13], [38, 94]]
Output: [[45, 46, 48, 53], [9, 13, 38], [59], [94, 98]] (jaggedness 41)

Note that none of these test cases show the only acceptable answer, merely one acceptable answer. For example, any output would remain valid if a subarray was reversed.

| |
\$\endgroup\$
1
\$\begingroup\$

Destroy the Computers with Magnets!

The robot apocalypse has finally arrived. But as we all know, robots are controlled by computers. And magnets are a convenient way of disabling computers.

Your task: place the magnet close enough to the computer so that it disables the computer.

A computer looks like this (always the exact same size):

 ____
|    |
|    |
|____|

The magnet looks like this:

o

The magnet needs to be touching the computer to do its work:

 o____o
o|    |o
o|    |o
o|____|o
 oooooo

Note the lack of placements on the top; that is intentional. People use the computer on that side, and would easily see the magnet and remove it.

So if you are given a picture of some computers:

       ____
      |    |
 ____ |    |
|    ||____|
|    |      ____
|____|     |    |
           |    |
           |____|

You should place 1 magnet for computer next to the computers:

       ____
      |    |
 ____ |    |
|    ||____|
|    |  o   ____
|____|     |    |
 o        o|    |
           |____|

Magnets may touch computers, but there must be 1 touching magnet per computer.

Due to the apocalypse, resources are scarce, so your program to place magnets must be as short as possible.

Test cases:

Input
~~~~~
Example outputs (not only possible outputs)
=====
       ____
      |    |
 ____ |    |
|    ||____|
|    |      ____
|____|     |    |
           |    |
           |____|
~~~~~
       ____
      |    |
 ____ |    |
|    ||____|
|    |  o   ____
|____|     |    |
 o        o|    |
           |____|

        ____
       |    |
  ____ |    |o
 |    ||____|
 |    |     o____
o|____|     |    |
            |    |
            |____|
=====
More soon....
| |
\$\endgroup\$
  • \$\begingroup\$ Is it permissible for a "component" to be adjacent to multiple voting machines? For example, with two voting boxes 1 space apart, would placing two components in that column be valid? \$\endgroup\$ – Kamil Drakari Dec 15 '17 at 20:03
  • \$\begingroup\$ @KamilDrakari That is allowed, I will edit. \$\endgroup\$ – Comrade SparklePony Dec 16 '17 at 0:27
  • \$\begingroup\$ Would these be valid outputs? Also is the voting machine always the same size? \$\endgroup\$ – ბიმო Dec 16 '17 at 20:24
  • \$\begingroup\$ @BruceForte Those are all valid outputs except for number 4: there must be at least 1 physical component per voting machine (as it says in the challenge.) Voting machines are all the same size. I will edit. \$\endgroup\$ – Comrade SparklePony Dec 18 '17 at 14:24
1
\$\begingroup\$

Minimal Substring Lookup Table

A fairly common component of code golf challenges is taking input as a string, and finding the index of that string within an array. A common way to golf that action is to instead store a substring of each item in the array, and take the same substring of the input to use when looking up the index. For example, this question has some fairly large strings that need to be indexed, but this answer found that each item could be uniquely identified by its 4th letter.

Challenge

Find the shortest substring that, when applied to each string in the input, results in a new set of unique strings.

Input

  • Input is list of strings in any default format
  • The strings will consist of printable ASCII characters.
  • The strings will not have trailing spaces
  • There will be no duplicate strings

Output

  • Output should be a list of the shortened strings after applying the substring
  • If outputting indexes, 0-indexing or 1-indexing may be used.
  • When strings have different lengths, substrings exceeding the length of some lines may be handled any of these ways:
    • Truncate to the available characters, e.g. ["abc","acd","ab"] => ["bc","cd","b"]
    • Pad shorter strings with spaces, e.g. ["abc","acd","ab"] => ["bc","cd","b "]. Note that input strings can contain spaces which need to be taken into account, so ["ab c","acdc","ab"] must not become ["b ","cd","b "].
    • Wrap back to the start of the shorter string, e.g. ["abc","acd","ab"] => ["bc","cd","ba"]. Note that even with this method it is not necessary to look for substrings where every string wraps; the starting index should always be within the length of the longest input string.

Sandbox questions

  • Should I restrict the input strings to only a subset of printable ASCII?
  • Should I enforce one specific behavior for handling shorter strings? Requiring wrapping would let the challenge look for even shorter solutions requiring full wrapping, e.g. ["aba","ab"] => ["a","b"], but I don't want languages with different default substring implementations to need a lot of work just to get the wrapping working.
  • I used the term "substring" as something that is "applied" to a string to get the shortened version, but I know that's extremely wrong. Is there a better way to phrase this?
  • This challenge is related, but uses arbitrary substrings rather than aligned substrings. Should I mention it somewhere?
| |
\$\endgroup\$
  • \$\begingroup\$ "Should I enforce one specific behavior for handling shorter strings?" - Personally, I'd say yes. \$\endgroup\$ – Shaggy Dec 20 '18 at 19:02
  • \$\begingroup\$ I think it would be better to output the position and length of the substring, rather than every substring. \$\endgroup\$ – 12Me21 Dec 30 '18 at 1:24
  • \$\begingroup\$ Alternatively, you could just say that all input strings have the same length. \$\endgroup\$ – japh Jan 16 '19 at 8:43
1
\$\begingroup\$

Piano Scale Fingering

There are 12 different major scales on the piano, which have similar, but not identical, fingering. Furthermore, the fingering for each hand is slightly different.

The fingers of each hand are numbererd starting at 1 for the thumb. Each note usually takes the next finger in turn. For the left hand playing an ascending scale, this means that the numbers decrease, while for the right hand the numbers increase.

Of course you will run out of fingers before you get to the end of the scale. For the left hand, this means that when you get to the thumb you need to start again with one of the other fingers, while for the right hand this means that when you get to a certain finger you need to start again with the thumb.

Although there are eight notes in an octave, the part that repeats in the middle of a scale is seven, which is a prime number. Scales are therefore normally played using the repeatying sequnces 4321321 in the left hand and 1231234 in the right hand; the little finger is only used to avoid switching to the thumb on the first or last note respectively. Other adjustments also apply at the very start and end of the scale.

There are a couple of rules which work for most scales. The first rule is that you try to play the tonic with the thumb except at the appropriate end of the scale when you use the little finger. If you can't follow that rule then with the right hand you use the thumb when switching from a black note to a white note; with the left hand you aim for the thumb to land on a white note just before a black note.

Here is a full list of all 12 keys and their fingerings:

 #  Key Left Hand       Right Hand
-6  Gb  432132143213212 234123423412345
-5  Db  321432132143212 231234123123412
-4  Ab  321432132143212 231231234123123
-3  Eb  321432132143212 212341231234123
-2  Bb  321432132143212 212312341231234
-1  F   543213214321321 123412341231234
 0  C   543213214321321 123123412312345
 1  G   543213214321321 123123412312345
 2  D   543213214321321 123123412312345
 3  A   543213214321321 123123412312345
 4  E   543213214321321 123123412312345
 5  B   432143213214321 123123412312345
 6  F#  432132143213212 234123123412345

Please write a program function which takes as input the key (or #, which is the number of sharps in the key, or the negation of the number of flats in the key) of a scale and a flag (e.g. L or R) for which hand, and output the fingering for two octaves as above. (For longer scales you simply repeat the middle 7 digits so I don't see the utility of asking you to output an arbitrary number of octaves.)

Note that Gb is enharmonic to F# on the piano but you might find it easier to support one rather than the other. Please indicate which one your answer supports.

As an alternative to writing a single function I will also allow two named functions (one for each hand) but not two lambdas. The 1 byte per extra file penalty applies if you submit two full programs.

| |
\$\endgroup\$
  • \$\begingroup\$ Why not two lambdas? \$\endgroup\$ – wizzwizz4 Dec 24 '18 at 9:42
  • \$\begingroup\$ @wizzwizz4 You're not allowed to encode the answer in your choice of boolean flags, and IMHO allowing lambdas would violate that loophole, but for named functions the answer isn't encoded in the name, so that's OK. (You could of course just pay the penalty for naming your lambdas.) \$\endgroup\$ – Neil Dec 24 '18 at 10:08
  • \$\begingroup\$ Some languages don't feature named lambdas, e.g. a LISP dialect without defvar. It seems completely arbitrary. \$\endgroup\$ – wizzwizz4 Dec 24 '18 at 10:10
  • \$\begingroup\$ What's wrong with lambdas? That rule is completely arbitrary. \$\endgroup\$ – Beefster Dec 28 '18 at 19:29
1
\$\begingroup\$

Front lines go front!

Given two lists of positive integers, bring the elements in the first one that are in the second to the far left, keeping their order the same as in the first list. You can assume that the second list's elements will all be unique.

These approaches are forbidden.

For example, let's call the first list \$A\$ and the second \$B\$. Here are some test cases:

\$A=[1,3,4,1,2,1,4,3,2,1,3,2,4,1],B=[1,3]\rightarrow[1,3,1,1,3,1,3,1,4,2,4,2,2,4]\$

\$A=[],B=[1,4,5]\rightarrow[]\$

\$A=[1,2,3,4,5,6,7,8,10],B=[]\rightarrow[1,2,3,4,5,6,7,8,10]\$

\$A=[],B=[]\rightarrow[]\$

\$A=[1,2,2,1,3,4,4],B=[1,2]\rightarrow[1,2,2,1,3,4,4]\$

\$A=[3,4,4,1,2,1,5],B=[1,5,2]\rightarrow[1,2,1,5,3,4,4]\$

\$A=[1,2,3,2,1,2,3,2,1],B=[4,5,6]\rightarrow[1,2,3,2,1,2,3,2,1]\$

\$A=[2,2,1,2,1,3,3,1,4],B=[1,2,3,4]\rightarrow[2,2,1,2,1,3,3,1,4]\$

Note: the integers aren't necessarily single-digit.

| |
\$\endgroup\$
  • \$\begingroup\$ @JonathanFrech Yes. How could it be used anyway? \$\endgroup\$ – Erik the Outgolfer Dec 27 '18 at 11:42
  • \$\begingroup\$ @JonathanFrech Clarified. \$\endgroup\$ – Erik the Outgolfer Dec 27 '18 at 15:52
1
\$\begingroup\$

Do not not not not make a filter that doesn't not not not get rid of these words!

Tags: code-golf

Your program has to scan each run of "not"s in a sentence, and if the number of "not"s is odd, then replace it with only one "not". If it is even, replace it with the empty string.

Notes:

  • The "not"s are case-insensitive, so your input may be "not" or "Not" or more.
  • The input may only be taken in as a string.

Test cases:

 Don't not not -->  Don't
 not not not a not not  -->  not a
 NoT nOt not NOT noT a Not nOt noT  -->  not a not
hello notnot anot not anota not not not --> hello a anota not
| |
\$\endgroup\$
  • 2
    \$\begingroup\$ We've had a very similar challenge before. On my phone so can't search properly for it to determine if it would be similar enough to be a dupe target. \$\endgroup\$ – Shaggy Dec 21 '18 at 19:27
  • \$\begingroup\$ Oh, let me see that then. \$\endgroup\$ – MilkyWay90 Dec 21 '18 at 19:40
  • \$\begingroup\$ So, input and output as a string? Would list of words be acceptable input/output? \$\endgroup\$ – ბიმო Dec 23 '18 at 14:20
  • \$\begingroup\$ @BMO List of words is not a valid format \$\endgroup\$ – MilkyWay90 Dec 25 '18 at 23:28
  • \$\begingroup\$ So, should I make this a question? \$\endgroup\$ – MilkyWay90 Dec 25 '18 at 23:30
  • \$\begingroup\$ What exactly counts as a not? Can it be part of another word? Do the nots have to be separated from each other by a single space? \$\endgroup\$ – 12Me21 Dec 30 '18 at 1:10
  • \$\begingroup\$ @12Me21 it can be part of another word \$\endgroup\$ – MilkyWay90 Dec 30 '18 at 3:07
1
\$\begingroup\$

Radiation Showdown KotH

In radiation hardening challenges, the goal is to write a program whose behavior doesn't change when an arbitrary character is removed from its source. This KotH explores an adversarial variant on this challenge in which two programs compete to survive the most character deletions. The twist is that each program is provided the source code of its opponent and outputs which character should be deleted from its opponent's source code next.

Gameplay

Suppose program A and B are competitors.

  1. Each program is run and the output is recorded. Let the output of program A be a and the output of program B be b. If one program fails to output a valid character index of its opponent's source code, the other program will be declared the winner of the match. If neither program outputs a valid index, then a tie is declared.
  2. The a'th character is removed from program B and the b'th character is removed from program A.
  3. Repeat steps 1 and 2 until there is a winner or a tie.

Submissions

Submissions should be a complete javascript or python program which:

  • Begins with a shebang (#!) indicating which language it is written. For python entries, this should be #!/usr/bin/python. For javascript entries this should be #!/app/.heroku/node/bin/node.
  • Takes three command line arguments: the code for the opponent program, the start of the range of deletable characters (x), and the end of the range (y). In python these can be accessed using sys.argv, while in javascript they can be found in process.argv.
  • Prints a number in the range [x,y) to stdout and terminates in less than 10 seconds.

Note: The index of the first deletable character of your opponent's program (x) is the index of the first character after the shebang. y is the length of the opponent program in characters (so y-1 is the last deletable character).

Sample Submissions

Python:

#!/usr/bin/python
import sys

# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
print (sys.argv[3]-1)
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

Javascript:

#!/app/.heroku/node/bin/node
// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
console.log(Math.round(Math.random() * process.argv[4]));
// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

Controller

I've hosted a web based controller at https://radiationshowdownkoth.herokuapp.com/. It should conform to the behavior specified in the Gameplay section. Let me know if you find any bugs.

Rules

  • Standard loopholes apply.
  • The use of preexisting interpreters and their components (parsers, lexers, etc) is banned. This includes, but is not limited to, calling the python and node binaries from your program (eg os.popen("python -c ...")), using builtin eval functions (eg python's exec), and using relevant modules (such as python's astlib). However, you may use regular expressions.
  • No malicious code.

Logistics

It will be a Round Robin Tournament. Each submission will be matched against every other submission. For each victory a submission achieves, it will be awarded 1 point. Likewise, ties are worth 0.5 points and losses are worth 0 points. The submission with the most points after all rounds have been completed wins this KotH. The winner will receive a bounty from yours truly, and the most popular entry will be awarded accepted answer. This KotH will be open to entries for a week following its posting, at which point the tournament will be run and a winner declared.

Meta

  • Duplicate?
  • Clarifications?
  • Other Language Suggestions besides Python & Javascript?
  • Are there any trivial strategies that would be overwhelmingly effective?
  • Any other foreseeable problems?
| |
\$\endgroup\$
  • \$\begingroup\$ Would an empty program that outputs 0 auto win? \$\endgroup\$ – user202729 Dec 30 '18 at 3:31
  • \$\begingroup\$ Also, removing the shebang would kill the program. \$\endgroup\$ – user202729 Dec 30 '18 at 3:31
  • \$\begingroup\$ @user202729 Yes, I believe an empty program that outputs 0 would always win as the rules are currently written. Is it possible to write such a program in Javascript or Python? \$\endgroup\$ – Zachary Cotton Dec 30 '18 at 3:35
  • \$\begingroup\$ @user202729 Actually, I am mistaken. If a program outputs 0 it will lose because 0 is not in the valid range of deletable characters (passed in as the second and third arguments to the program). This range starts after the end of the shebang in order to prevent the second exploit you pointed out. I will try to clarify this in the spec. However, a 0 character program that printed its second command line argument would auto win. As far as I know, it is not possible to write such a program in Javascript or Python, but please let me know how if it is. Thanks for the exploits :). \$\endgroup\$ – Zachary Cotton Dec 30 '18 at 3:53
  • \$\begingroup\$ How are x and y computed? \$\endgroup\$ – user202729 Dec 30 '18 at 3:54
  • \$\begingroup\$ @user202729 x is the index of the first character after the shebang. y is the length of the program in bytes. I've edited the spec to include this information. \$\endgroup\$ – Zachary Cotton Dec 30 '18 at 4:07
  • \$\begingroup\$ I like it! I'm not very experienced, but I'd say it's ready to go. \$\endgroup\$ – MilkyWay90 Dec 30 '18 at 4:10
  • \$\begingroup\$ Hm... in that case I'd say that because Python and Javascript are both "sensitive" (?) to radiation, making a program that would never lose is pretty easy. (just remove the first non-comment character or similar) \$\endgroup\$ – user202729 Dec 30 '18 at 4:12
  • \$\begingroup\$ @user202729 One way to defend yourself against a program that deletes the first non-comment character would be to define a variable with a really long name on the first non-comment line of the program. But I see your point. Any ideas for better choices of languages? \$\endgroup\$ – Zachary Cotton Dec 30 '18 at 4:28
  • \$\begingroup\$ It might be better to make the challenge "given a Python/JS program, delete a character so that it throws an error." Because AFAIK it's always possible, and such a program will never lose. \$\endgroup\$ – user202729 Jan 1 '19 at 14:59
1
\$\begingroup\$

Unfactor a list

Jelly has an interesting built-in, ÆẸ. It's the inverse of ÆE. ÆE returns the exponents of the prime factors of an integer n, where each exponent corresponds to the prime number at its index, so, for example, [3, 5, 1] represents \$2^3\cdot3^5\cdot5^1\$. If a prime isn't included in the prime factorization of n, but there is at least one prime after it that is included, a zero is put in its place (\$p^0=1\$). So, for example, [3, 0, 5, 1] represents \$2^3\cdot5^5\cdot7^1\$, and [0, 4, 4, 50, 0, 7] represents \$3^4\cdot5^4\cdot7^{50}\cdot13^7\$.

Your job is to implement ÆẸ, ÆE's inverse. That is, you'll be given a list returned by ÆE, and your job is to find n.

You must always return a positive integer (strictly greater than zero). You may assume the input doesn't have negative or float exponents or trailing zeroes.

Note that you're encouraged not to use ÆẸ or your language's equivalent (if any) in your answer.

Using any of the standard loopholes is prohibited.

Test cases (you don't have to support exponents, an output or an input's length beyond your natural signed integer type's limit):

[] -> 1
[0, 4] -> 81
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] -> 1111
[10] -> 1024
[3, 5, 1] -> 9720
[3, 0, 5, 1] -> 175000
[31] -> 2147483648
[32] -> 4294967296
[63] -> 9223372036854775808
[64] -> 18446744073709551616
[0, 4, 4, 50, 0, 7] -> 5713082599062385095715588395684396863698753591853983125

Make more test cases:

To generate the input that corresponds to a given output, use this program.

To generate the output that corresponds to a given input, use this program.

| |
\$\endgroup\$
  • \$\begingroup\$ @Adám Hm, I included the stuff for clarity, but I can remove it as well. EDIT: Removed the fluff. \$\endgroup\$ – Erik the Outgolfer Jan 7 '19 at 22:49
1
\$\begingroup\$

Where can I get to from each location? (Transitive Closure)

Given an undirected graph (network) \$G\$, construct a new graph in which vertex (node) pair \$(u,v)\$ is an edge (are connected) if and only if a path \$(u,w_1,w_2,...,w_k,v)\$ exists in \$G\$ for some \$k\ge 0\$. This is known as \$G\$'s transitive closure. If this is clear to you, you're ready to get started. Otherwise, just read through the below sections. It is actually a very simple problem.

I/O formats

Take for example the graph (network)

1──2  3──4
│     │
5  6──7──8

We can represent¹ it as an adjacency (connection) matrix:

 │1 2 3 4 5 6 7 8
─┼───────────────
1│  ┘ 
2│
3│      ┘
4│
5│┘
6│            ┘
7│    ┘         ┘
8│

which is:

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

Note that here only one of \$(u,v),(v,u)\$ is represented, but we consider both directions as valid edges (connections).

Or as a list of of edges²:

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

Or for each vertex³ (node), the list of its adjacent vertices:

[[2,5],[1],[7,4],[1],[7],[3,8],[8],[]]

Or as a dictionary⁴:

{"1":[2,5],"3":[7,4],"7":[6,3,8]}

Any of these, and any other reasonable input and output formats (you optionally may use one format for input and another for output) are allowed, but you must state what your formats are. However, it is required that your formats support under-representing (e.g. [3,7] but not [7,3]) and over-representing (e.g. both [3,7] and [7,3]).

Walk-through

Let's use the representation [[1,2],[1,5],[3,4],[5,1],[6,7],[7,3],[7,8]]. Since 1 is connected to 2 then 2 is also connected to 1, so we add (it doesn't matter where) this edge (connection):

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

It is also possible to travel [1,5] in reverse, but that pair is already represented further in the list. Now note that it is possible to find a path from 2 to 5, and vice versa, via 1, so we add these two edges:

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

This completes the left side of the graph. Similarly, we process the right side by adding the reversals of [3,4], [6,7], and [7,3]:

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

Two-step paths via 3 are possible, so we add [7,4] and [4,7]. Similarly, two-step paths via 7 are [6,3], [3,6], [6,8], [8,6], [3,8], and [8,3]:

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

Finally, we add the three-step paths [6,4], [4,6], [4,8], and [8,4]:

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

And this is our answer. It could of course be in any order.


  1. Though the connections do not have direction, I've only put in one entry in the table for each connection, and obviously the diagonal is all-true too, as every node is reachable from itself.
  2. Since the connections in this challenge do not have a direction, [1,5] and [5,1] are the same connection. This serves to illustrate that such may occur in the given data.
  3. Here, each node must have its own list, as the lists are paired to their points by their position in the data. However, each list need not be exhaustive as long as all connections are represented somewhere.
  4. Here, we can omit entries that are fully covered by the other entries.

| |
\$\endgroup\$
  • \$\begingroup\$ Am I over complicating things by allowing all the various I/Os? \$\endgroup\$ – Adám Jan 7 '19 at 13:26
  • \$\begingroup\$ All the input formats you mentioned seem reasonable to me and I'm sure different languages could use different formats when golfing. And if you restrict it to one specific format, you'll get people asking about using other formats anyways. \$\endgroup\$ – Emigna Jan 7 '19 at 14:27
  • \$\begingroup\$ why not state it in graph-theoretic terms - vertex, edge, path, graph, incidence matrix - instead of the more vague location/place/point, connection, journey, network, connection table? "[1,5] and [5,1] are of course the same connection" - it would be just as valid and interesting a problem if it were about directed graphs, so it's not "of course" :) tag "repeated-transformation" is unnecessary - this can be solved in O(n^3) time without the use of ⍣≡. \$\endgroup\$ – ngn Jan 7 '19 at 14:27
  • \$\begingroup\$ @Emigna Fixed. Thanks. \$\endgroup\$ – Adám Jan 8 '19 at 7:25
  • \$\begingroup\$ @ngn Reason: I am not educated enough. Can I bother you to edit those in? I'll remove "of course". \$\endgroup\$ – Adám Jan 8 '19 at 7:26
  • \$\begingroup\$ @Adám sure, i'll edit it. it's nice you put "transitive closure" in the title. many challenge authors (with or without cs/maths degrees) like to reinvent terminology, obscure the problem with backstories, etc. i find that mildly annoying. example - seems to be an interesting challenge but it takes so long to figure out what the words mean. \$\endgroup\$ – ngn Jan 8 '19 at 13:43
  • \$\begingroup\$ @Adám how does it sound now? i'm not sure if i didn't go to far with that pseudo-academic lingo... \$\endgroup\$ – ngn Jan 8 '19 at 14:21
  • \$\begingroup\$ @ngn Thank you so much. I've added in parenthesised layman's terms upon first usage in each section, and added a bit to the intro to keep people from fleeing. I also inserted the word "pair" on the very first line before (u,v) as it seemed to me that it was missing. Correct me if I'm wrong. \$\endgroup\$ – Adám Jan 8 '19 at 15:05
  • \$\begingroup\$ @Adám i forgot to delete the word "vertex". inserting "pair" should be fine too \$\endgroup\$ – ngn Jan 8 '19 at 15:12
  • \$\begingroup\$ Closely related. Directed version. \$\endgroup\$ – Peter Taylor Jan 9 '19 at 11:40
1
\$\begingroup\$

"Cumbersome Crown words"

Introduction

This is my first entry here, so please be gentle if it's poorly stated. I'll need a bit of guidance to make it a good submission.

I am a typewriter maker, and I want to prove that the design of my competitor, Mr. Crown, is very inconvenient to use. To do that, I want a list of the most cumbersome words to type out on a Crown typewriter.

Challenge

Write a program that takes an argument "n" as a positive integer. You may load the Unix words list from any source (ignore case; discard any word containing anything outside of A-Z, such as "O'Brien", "L'vov", etc.). Given the layout shown below, output the "n" most cumbersome words to write, one result per line. Each result is the cumbersome word, some form of separator (eg. a space), then their word score (see below) with two decimals of precision (and your choice of decimal separator). Bonus if results are sorted in descending order by their word score, and further bonus if ties (by score) are also sorted in alphabetic order.

Crown typewriter layout

X Q K G B P M C O F L A N D T H E R I S U W Y J V Z

Word scoring

Assume the pointer starts in the leftmost position, on "X". Count each movement and each hammer strike as one unit, but divide the sum by the number of characters in the word. Hence, sample word scores are:

  • THEIR: 4.8 -- 24 units (14 movements, strike "T", movement, strike "H", movement, strike "E", 2 movements, strike "I", movement, strike "R") divided by 5 characters
  • LAND: 4.25 -- 17 units (10 movements, strike "L", movement, strike "A", movement, strike "N", movement, strike "D") divided by 4 characters
  • FOWL: 9.50 -- 38 units (9 movements, strike "F", movement, strike "O", 13 movements, strike "W", 11 movements, strike "L") divided by 4 characters
  • BARBARA : 8.00 -- 56 units (4 movements, strike "B", 7 movements, strike "A", 6 movements, strike "R", 13 movements, strike "B", 7 movements, strike "A", 6 movements, strike "R", 6 movements, strike "A") divided by 7 characters
  • X: 1 -- just hit the hammer once and you're done

Note: These examples are not the most cumbersome words.

Example Input and Output

Input:

5

Standard output:

ANNA 4.25

THEIR 4.80

LAND 4.25

BARBARA 8.00

FOWL 9.50

Bonus output:

FOWL 9.50

BARBARA 8.00

THEIR 4.80

ANNA 4.25

LAND 4.25

Scoring submissions and determining the winner

I'm really not sure what the best measure of success is. Definitely not code golf, because I can never distinguish the damn things from line noise or pure black magic. But what then? I'm not very familiar with which competition types are available.

If two solutions are tied for a position, but only one of them uses the bonus output format, then that one wins the tie.

| |
\$\endgroup\$
  • \$\begingroup\$ Tak for at du bruger sandkassen! \$\endgroup\$ – Adám Jan 4 '19 at 13:19
  • 1
    \$\begingroup\$ You can find a list of all winning criteria here, though I think code-golf is actually the best fit. When you are bothered by illegible answers, try asking for an explanation, most users are happy to explain how their code works and which tricks they used. \$\endgroup\$ – Laikoni Jan 6 '19 at 8:32
  • 2
    \$\begingroup\$ As for the challenge, it would be helpful to provide a transcript of the order of the letters from the image. I personally like challenges to focus on their core, in this case calculating the score of a word, and to avoid additional tasks, like sorting a list and printing the top n entries, as those can distract from the main challenge. (E.g. in a language without a build-in sort method the challenging part could become implementing a sorting algorithm even though that's presumably not the intention of your challenge.) \$\endgroup\$ – Laikoni Jan 6 '19 at 8:51
  • \$\begingroup\$ @Laikoni thank you for the reference! I am leaning towards [popularity-contest], but otherwise I guess I can settle for [code-golf]. \$\endgroup\$ – KlaymenDK Jan 8 '19 at 9:11
  • 3
    \$\begingroup\$ popularity-contest challenges are very hard to get right, read e.g. here. I'd strongly advise you against using it, as it is not a good fit for this otherwise nice challenge. \$\endgroup\$ – Laikoni Jan 8 '19 at 13:28
  • \$\begingroup\$ Is the word list common for all solutions or may the answerer choose their word list? \$\endgroup\$ – Neil A. Jan 10 '19 at 1:28
  • \$\begingroup\$ I can restrict it to the Unix Words file if that helps. \$\endgroup\$ – KlaymenDK Jan 10 '19 at 9:31
  • \$\begingroup\$ If not a [popularity-contest], then what's the best way to score this, given that I desire code readability (so not [code-golf])? \$\endgroup\$ – KlaymenDK Jan 10 '19 at 9:32
  • \$\begingroup\$ Imo, the heart of the challenge is to determine the score of a word: I consider the rest as unnecessary, reading words from files has been done and will only make it difficult (or even impossible) for some languages, sorting with a custom function too, has been done. So I would extract the heart of this challenge and state it as Given a word, output its score. \$\endgroup\$ – ბიმო Jan 10 '19 at 14:01
  • 2
    \$\begingroup\$ Now, since you don't want a code-golf, popularity-contest is not really the right thing, the challenge is not computationally hard (ruling out fastest-code or the like) that kind of leaves us with: atomic-code-golf or code-challenge. For the former one I don't see a sensible way to define the challenge which leaves us with the latter and gives rise to a start of a really interesting challenge: Make it a code-challenge where the scoring is according to the word's score ("cumbersome-ness"). The problem will be characters outside of that range: \$\endgroup\$ – ბიმო Jan 10 '19 at 14:08
  • \$\begingroup\$ Ideas (for all I'm assuming case-insensitivity): 1) You extend the range to include @!…⅓ and exchange the character _ or the unreadable one after Z with a space. Then you'll only allow submissions using this extended range. [imo the most sensible, it does restrict the submissions heavily but in an interesting and sensible way so] 2) Before scoring the submission, remove all characters outside of the range. [people will abuse this and only use characters outside of that range] 3) Only XQ…Z are valid in a submission. [this is a really tight restriction for most languages] \$\endgroup\$ – ბიმო Jan 10 '19 at 14:14
  • \$\begingroup\$ 4) Instead of ignoring characters outside that range, penalize them with a constant (kind of expensive, but not too expensive). \$\endgroup\$ – ბიმო Jan 10 '19 at 14:21
  • \$\begingroup\$ @BMO, thanks a ton for your feedback! I'm not sure I follow (= I'm pretty sure I don't follow) your "ideas" comment. Could you explain further? \$\endgroup\$ – KlaymenDK Jan 10 '19 at 15:28
  • \$\begingroup\$ If you go the route of code-challenge with score being the "cumbersomeness" of the code itself, it's not clear how you'll treat characters which aren't in the range XQ…Z and there would be need of a way to score these. The ideas (1-4) would be different options to define that. \$\endgroup\$ – ბიმო Jan 10 '19 at 16:17
1
\$\begingroup\$

My Number is Bigger Than Yours: KoTH

The concept of this game is simple; each turn, two bots submit a positive integer (in Python, so no upper bound on its size). Whichever bot submits a larger number wins a certain number of points based on the scoring put forward in the next section. This process is iterated a certain number (100?) times to form the competition, with the bot which has the highest score winning the competition between the two bots.

However, scoring is based on some metric of the difference between the submitted values such that the larger the difference is, the smaller the amount of score gained is. I'm trying to decide some metric which heavily incentivizes making a guess which narrowly beats your opponent's guess, maybe with a metric such as 1/(a-b)**2. However, as the numbers will likely grow throughout the iterations, maybe 1/(a/b)**2 might be better.

Example bot whose goal is to beat opponents who pick a constant number:

def constant_beater(my_score, opp_score, my_numbers, opp_numbers):
    if len(opp_numbers) == 0:
        return 1
    return opp_numbers[-1] + 1

The largest concern I see with this challenge is a bot which just increments much quicker than all other bots so that it wins every game with a minuscule amount every time. Maybe to curb this a score that is below a certain threshold for a game is rounded to zero to encourage more competitive choices.

| |
\$\endgroup\$
  • \$\begingroup\$ I feel like this would be a much better challenge if bounded a bit, from maybe 1-100 for example \$\endgroup\$ – Quintec Jan 11 '19 at 22:57
  • \$\begingroup\$ I was thinking of some sort of bounding, but I'm struggling to then find an incentive for a bot to choose anything except for the upper bound. \$\endgroup\$ – Sebastian Jan 11 '19 at 23:02
  • \$\begingroup\$ Make it a round robin tournament? \$\endgroup\$ – Quintec Jan 11 '19 at 23:19
  • \$\begingroup\$ Numbers from 1 to 100. 100 rounds between 2 bots, higher number wins, can only play each of the 100 numbers 1 time each. Score is the number of rounds won? The play method doesn't work well for difference between numbers. \$\endgroup\$ – fəˈnɛtɪk Jan 13 '19 at 1:43
  • \$\begingroup\$ This sounds extremely abusable, even more if they try to tap into the others' functions. However, it still sounds real fun, reminds me of the Robot Roulette but with much better winning chances. Maybe you could add some restriction like preventing to use the same number X amount of rounds with a maximum number cap (like @fəˈnɛtɪk said but without too much limiting) \$\endgroup\$ – Belhenix Jan 15 '19 at 22:38
  • \$\begingroup\$ Maybe instead of a maximum number cap a maximum sum cap? \$\endgroup\$ – Sebastian Jan 16 '19 at 21:44
  • \$\begingroup\$ If there's a maximum number cap I don't think there needs to be a maximum sum cap. However, there needs to be an incentive so bots don't go spamming the maximum number 24/7 (or worse, having 2 bots spam max number to infinity and ending in a 0 point tie) \$\endgroup\$ – Belhenix Jan 17 '19 at 23:23
  • \$\begingroup\$ Thinking about this: Perhaps the max is 100, and bots score 100-guess if they win, and -(guess/100) if they lose? \$\endgroup\$ – Spitemaster Jan 31 '19 at 22:20
1
\$\begingroup\$

Drawing \$K_n\$ (complete graph with \$n\$ vertices)

Tags: , ,


In graph theory the complete graph with \$n\$ vertices, often written as \$K_n\$, is the graph where every vertex is connected to every other vertex. For example, \$K_3\$ with \$V = \{A,B,C\}\$ has the edges \$\bigr\{\{A,B\},\{B,C\},\{C,A\}\bigl\}\$ - forming a triangle.

Challenge

Given an even \$n \geq 4\$ you will generate/display an image of the graph \$K_n\$ as follows:

  • pick an image width \$\texttt{width} \geq 100\$
  • pick two distinct colors \$\texttt{vertex_color}\$ and \$\texttt{edge_color}\$
  • draw \$1\$ vertex with color \$\texttt{vertex_color}\$ in the middle of the image
  • draw the remaining \$n-1\$ vertices evenly distributed on a circle around it
  • connect every vertex with color \$\texttt{edge_color}\$

Rules

  • the background color doesn't matter (transparent is fine), but it must not coincide with the colors \$\texttt{vertex_color}\$ and \$\texttt{edge_color}\$
  • the radius of the circle should be \$\texttt{width/4}\$
  • the center of the circle should the middle of the image
  • the shape of the vertices doesn't matter, but they must be at least \$3\$ pixels wide
  • the edges must not overlap the vertices
  • the edges may be dashed, dotted etc.

Examples

Example output for \$K_4\$:

K_4

Example output for \$K_{12}\$:

K_12

Example output for \$K_{32}\$:

K_32

| |
\$\endgroup\$
  • \$\begingroup\$ "the edges must not overlap the vertices" is incompatible with "draw 1 vertex ... in the middle of the image" when n is odd. \$\endgroup\$ – Peter Taylor Jan 18 '19 at 16:21
  • \$\begingroup\$ @PeterTaylor: Good call, thank you! Restricted the input to only even integers. \$\endgroup\$ – ბიმო Jan 18 '19 at 16:48
  • \$\begingroup\$ a bit too many rules for me but... still very interesting and fun \$\endgroup\$ – don bright Jan 31 '19 at 2:58
  • \$\begingroup\$ @donbright: What do you mean by too many rules? Since it's graphical output, I have to set rules otherwise it'll become an art contest unfortunately. I'm open to less restrictive suggestions though. \$\endgroup\$ – ბიმო Jan 31 '19 at 14:46
  • \$\begingroup\$ its just my personal taste. like i dont care how wide the image is, how wide vertices are or whether edges overlap, etc etc. i upvoted anyways. good luck. \$\endgroup\$ – don bright Feb 2 '19 at 2:55
1
\$\begingroup\$

Chain round the number!

A decimal place is a digit of a number's location in a number. In the number 987654321, each digit corresponds to its decimal place. For example, in the number 16111, the 6 is in the 4th decimal place.

Normally when rounding to n decimal places, one checks the digit at n-1 (heretofore called x). If x >= 5, then the digit at n is rounded up. Otherwise the digit at n is rounded down (stays the same). Then, all digits including and after x are turned into 0.

For example, take the number 158, rounded to the 3rd decimal place. The digit at the 2nd decimal place (3rd decimal place minus one) is 5. Because of this, the 1 at the third decimal place gets rounded up. This results in the number being 258. However, the 5 and the 8 both get turned into 0, and so the final result is 200.

Chain rounding is like normal rounding, except that you do it to every digit starting with the digit at decimal place 2. Once you round to the decimal place 2, then you round to decimal place 3, and so on until decimal place n.

For example:

Input: 24472
24472    (2 < 5, so the 7 rounds down)
24470    (7 >= 5, so the 4 rounds up)
24500    (5 >= 5, so the 4 rounds up)
25000    (5 >= 5, so the 2 rounds up)
30000    (Final answer. Non chain-rounded answer would be 20000)

The challenge here is to chain round a number to the highest decimal place possible for that number.

Test cases: (all inputs will be positive whole numbers)

24472 -> 30000
1999 -> 2000    ("1 9 9 9" -> "1 9 10 0" -> "1 10 0 0" -> "2 0 0 0")
9945 -> 10000
2001 -> 2000
9444 -> 9000
9445 -> 10000
13579 -> 10000
24681 -> 30000
1337 -> 1000
5 -> 10
1 -> 1
| |
\$\endgroup\$
  • \$\begingroup\$ Good challenge, but I think this needs more explanation on what is happening. It's probably a good idea to fix an example with digits \$ab\$ and explain how the new rounding works (ie. compare \$b\$ to \$5\$ and so on), at first I did not understand where the \$5\$ comes from. You should also address how carries are treated, it's not clear atm. \$\endgroup\$ – ბიმო Jan 22 '19 at 19:17
  • \$\begingroup\$ @BMO I tried to clarify, is that better? (Thank you for the help). \$\endgroup\$ – Comrade SparklePony Jan 22 '19 at 19:56
  • \$\begingroup\$ Yes, looks good to me. Make sure to make a test-case with carries, eg. when rounding \$9996\$ or the like. And also specify whether numbers can be zero or even negative. \$\endgroup\$ – ბიმო Jan 22 '19 at 20:15
1
41 42
43
44 45
96

You must log in to answer this question.

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