571
\$\begingroup\$

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

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

  • Parts of the challenge you found unclear
  • Comments addressing specific points mentioned in the proposal
  • Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

\$\endgroup\$
1
  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    May 15 at 14:05

4688 Answers 4688

1
86 87
88
89 90
157
1
\$\begingroup\$

Challenge - Find the nearest "well known" fraction

Find the nearest useful, well-known fraction for any decimal.

Here I'm defining well-known fractions as

  • 1/2s - everyone can get on board with halves
  • 1/3s - similarly easy to picture
  • 1/4s - slicing up a pizza for greedy people
  • 1/5s - at the edge of usefulness, but I think still useful
  • 1/6s - only 1/6 and 5/6 are not covered by the above, but it's a pizza slice so just sneaks in

BUT NOT

  • 1/7s - no-one uses sevenths
  • 1/8s and 1/9s - might as well just go to decimals now

Thus, the challenge is, given any number between 0 and 1, output a numerator and denominator where the latter is between 1 and 6 inclusive, with a forward slash in-between, representing the nearest fraction to the decimal, from the following:

0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1

Zero and One results can either be output as 0/1 or 0, 1/1 or 1

TIE BREAK - where a decimal is equidistant between two common fractions (e.g. 0.775 is equidistant from 4/5 and 3/4), then the LOWEST denominator wins, so an input of 0.775 outputs 3/4.

(Sandbox comment - I hope this isn't trivially easy!)

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Hello, and welcome to Code Golf! This seems like it's definitely not a trivially easy challenge. \$\endgroup\$ Oct 31, 2023 at 14:46
  • 3
    \$\begingroup\$ Nice first challenge! The requirement of a slash between the numerator and denominator seems a bit annoying. Why can't answers return a pair of numbers? Regarding the tie breaker - if the input is a floating-point number, then none of the midpoints are exactly representable, which mean the tie breaker isn't relevant, which significantly disadvantages taking the input as a fraction. I'd suggest either dropping the tie breaker, or allowing only exact fractions as input. Lastly, the phrasing is a bit awkward - just "return the closest fraction with denominator as most 6" would be enough. \$\endgroup\$ Oct 31, 2023 at 16:29
  • \$\begingroup\$ I was thinking of posing a similar question, except the output would be one of the Unicode vulgar fractions U+00BC-U+00BE or U+2150-215E (you would pick the nearest as before). \$\endgroup\$
    – Neil
    Nov 6, 2023 at 1:40
  • \$\begingroup\$ The other approach for tie breaking is for a given input the code should always output the same result but for the ties either output is acceptable. \$\endgroup\$
    – Neil
    Nov 6, 2023 at 1:42
1
\$\begingroup\$

Twist words to intersect

Given three strings of alphabetic characters \$A\$, \$B\$, and \$X\$, (all uppercase or all lowercase, your choice), output an arrangement of \$A\$ and \$B\$ on a grid such that they intersect only at the letters of \$X\$. Each word can start at any location in the grid; after that, every character in the word must be placed in the grid at a location orthogonal (directly above, below, to the left, or to the right) of the previous character. The word must not intersect itself. The grid can be arbitrarily large.

For example, if \$A\$ was ASHAMEFULACT, \$B\$ was CHARACTER, and \$X\$ was HAT, one possible arrangement is shown below.

enter image description here

In text format:

_ _ _ _ _ _ _
_ _ a m e f _
_ c H a r u _
_ a s c A l _
_ _ e T c _ _
_ _ r _ _ _ _
_ _ _ _ _ _ _

(The places where the words intersect are shown in capitals; the rest of the letters are shown in lowercase.)

You can output in any reasonable format -- the format above is not required. For example, you do not need to have the intersecting letters be a different case than the rest of the letters in the words. One possible output format would be a 2D array of characters, like

[ ["",  "A", "M", "E", "F"],
  ["C", "H", "A", "R", "U"],
  ["A", "S", "C", "A", "L"],
  ["",  "E", "T", "C", "" ],
  ["",  "R", "",  "",  "" ] ]

You can assume that such an arrangement is possible to create -- e.g. \$A\$ and \$B\$ will both have the letters of \$A\$ as a subsequence (in order).

Standard loopholes are forbidden. As this is , shortest program wins.

\$\endgroup\$
2
  • \$\begingroup\$ Is the grid assumed to be of infinite size? You might want to say that somewhere. Also, I think you should recommend a specific format that might help answerers get on track, and then they can come up with golfier formats. (A matrix of characters doesn't seem complicated, but this challenge looks a bit more complicated than it is, so it might be better to state some options outright.) \$\endgroup\$
    – noodle man
    Nov 2, 2023 at 21:34
  • \$\begingroup\$ @noodleman Does this address edit your concerns? Do you have a suggestion for a golf-y format to mention? \$\endgroup\$ Nov 2, 2023 at 23:43
1
\$\begingroup\$

Print the banned characters based on the most common characters

This is an post, so in this challenge every answer (except the first answer) depends on the previous answer.

The goal of this challenge is to output the restricted characters based on the most common n characters, if happens to be a tie, then the characters with the lowest UTF-8 range is banned

The max bytes for every answer is:

\begin{align}2n+60\end{align}

where n is answer number

Rules

  • The answers only output the restricted characters, no newlines, no other characters like that.

    • The code may output the restricted characters once, in any order.
  • Standard loopholes are forbidden by default.

  • No answerer may answer twice in a row.

  • No languages may used in the last 5 answers (Or any answer if there are less than 5 answers).

  • Every answer takes empty or no input, and outputs to STDOUT. No answer should output to STDERR.

  • The wrong answers (that break rules or don't do that this challenge say) are completely ignored if this answer is 10 minutes old, and should be deleted.

Scoring

The lowest score is the best. Using this formula:

\begin{align}\frac{b+1}{n+1}\end{align}

Where b is byte count and n is answer number, we can score the answers based on the lowest score. The answer is accepted if the challenge hasn't recieved answers for 5 days.

Tiebreaker is the earliest answer.

Example

First answer

# 1: Python 3

    print(end="")

Character uses:

    ": 2 (Banned)
    n: 2
    (: 1
    ): 1
    =: 1
    e: 1
    i: 1
    p: 1
    r: 1
    t: 1

The second answer should output ". If the second answer's code is ppaaa, then the third answer should output either pa or ap (because you should output two restricted characters), and doesn't use these characters.

Note: The scoring formula is based on the byte count and the answer number. The goal is to output the restricted characters efficiently while adhering to the specified byte limits.

Have a great day!

\$\endgroup\$
2
  • \$\begingroup\$ What should clarify that codes can't use restricted characters (at least I'm assuming they can't). In the example, if the second answer was ppaaa, would the third one have to output p and a? \$\endgroup\$ Nov 1, 2023 at 3:08
  • \$\begingroup\$ @CommandMaster If the first answer is print(end=""), and the second answer is ppaaa then the third answer have to output p and a, so you're right. \$\endgroup\$
    – Fmbalbuena
    Nov 1, 2023 at 17:51
1
\$\begingroup\$

I'm building a Code-Golf type game for an authorization language. The premise is to review a piece of an authorization policy and the permissions to identify the least number of rules you need to create in order to keep the permissions true.

Example of one policy and two permissions below. What are Alice and Anthony's roles?

  • Alice can read Organization metaworldpeace
  • Anthony can add_member Organization metaworldpeace

actor User { }

resource Organization { 
    roles = ["admin", "member"];
    permissions = ["read", "add_member"];
# role hierarchy:
# admins inherit all member permissions
"member" if "admin";

# org-level permissions
"read" if "member";
"add_member" if "admin";

   

\$\endgroup\$
3
  • \$\begingroup\$ ??? i cant see what this has to do with code golf \$\endgroup\$
    – Seggan
    Nov 10, 2023 at 18:32
  • 1
    \$\begingroup\$ @Seggan It's underspecified, but does seem like an atomic-code-golf. \$\endgroup\$ Nov 10, 2023 at 18:34
  • \$\begingroup\$ Or perhaps a metagolf...? \$\endgroup\$ Nov 10, 2023 at 18:46
1
\$\begingroup\$

Can I do this parkour?


In this challenge, you'll be given a list of platforms (line segments), a start point, a goal point, and your acceleration, stopping, and jump strength. Your task will be to determine whether it's possible to make it from the start point to the goal point by running and jumping on the given platforms.

Physics

I can be modelled as a point, subject to gravity. All positions will be given in meters, and gravity can be assumed to accelerate me downward at \$10\:\mathrm{m/s^2}\$. If I'm standing on a horizontal platform, I can accelerate in a direction I'm moving in (or if I'm at \$0\:\mathrm{m/s}\$) at a rate of \$a\:\mathrm{m/s^2}\$, where \$a\$ is the acceleration taken as input.

(unfinished)

\$\endgroup\$
7
  • \$\begingroup\$ Even though it's unfinished, I'll leave some thoughts: (1) Should time be treated as continuous or discrete (i.e. can you change your acceleration at any time \$t \in \mathbb{R}\$ or just at \$t=0,1,\ldots\$)? (2) Are the platforms all the same size, or can they vary in width (I'm assuming they can vary in position)? (3) It might be nicer if you have the acceleration be 1 m/s^2 (or 1 in whatever units you're using). \$\endgroup\$ Nov 10, 2023 at 19:20
  • \$\begingroup\$ (4) I'm not quite sure what "I can accelerate in the direction I'm moving in" means; does that mean if your current velocity is positive in the x axis, you can only accelerate in the positive x direction, or can you also decelerate in that direction? Does this only apply to the x (horizontal) axis, or does it include the y as well? \$\endgroup\$ Nov 10, 2023 at 19:23
  • \$\begingroup\$ @97.100.97.109 1. Time is continuous 2. The platforms can be arbitrary line segments on a vertical 2d plane, so yes, any length 3. Maybe I'll change acceleration to be a constant yeah 4. Deceleration has a separate speed \$\endgroup\$ Nov 10, 2023 at 19:25
  • \$\begingroup\$ I'm thinking I'll remove the separate deceleration speed, probably unnecessary complexity \$\endgroup\$ Nov 10, 2023 at 19:25
  • \$\begingroup\$ Oh sorry, I realized I misspoke -- for (3) I was referring to making the acceleration due to gravity have a unit acceleration (1 m/s^2), not the "player's" acceleration. \$\endgroup\$ Nov 10, 2023 at 19:26
  • \$\begingroup\$ Also, the line segments can have arbitrary x and y positions and lengths? If so, then this question seems like it's basically asking the solvers to write a 2D physics engine, which seems a little bit too much. (I was assuming the platforms were restricted to \$y=0\$.) \$\endgroup\$ Nov 10, 2023 at 19:29
  • \$\begingroup\$ @97.100.97.109 Yes, they can have arbitrary positions \$\endgroup\$ Nov 10, 2023 at 19:55
1
\$\begingroup\$

Add two natural numbers

\$\endgroup\$
1
  • \$\begingroup\$ I think it's an interesting idea, and reasonably clear -- I would phrase it differently however; these aren't exactly the rules that define addition. I would say "show a sequence of applications of these two operations to get from a+b to a single number representing their sum" or something like that. \$\endgroup\$ Nov 10, 2023 at 19:15
1
\$\begingroup\$

posted: Convert real numbers between factoradic and positive integer bases

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

Prefix-Suffix equality, part 1

Given an array of two distinct byte-sized values, please perform the following operations or their equivalent:

  • Construct an array of its nontrival prefixes and suffixes, starting with the array itself and working down to its first and last elements.
  • Compare each element of the two arrays elementwise, with the result 1 if the two elements are identical and 0 if they are not.
  • Taking the array of 1s and 0s, interpret that as a number in base 2.
  • Double this number.

The result turns out to be the expected number of uniformly random selections between your original two values to get the input array.

Example using H and T as the two byte-sized values:

HTTHT  HTTHT   1
HTTH    TTHT   0
HTT      THT   0
HT        HT   1
H          T   0

Converting 10010 to decimal gives 18, which is then doubled to give the final result of 36. This is the expected number of coin tosses to produce the pattern HTTHT.

This is , so the shortest program or function that breaks no standard loopholes wins!

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

Deja vu

Given two arrays, let's call them a and b, and a number n, your task is to see if there exists a subarray in a so that that subarray's sum is n and there is a subarray in b that also sums to n and has the same length. You may assume that all elements in a and b are positive integers, and so is n.

For example, if a is [1, 2, 3, 4, 5], b is [2, 2 ,2, 6, 7] and n is 6, the output would be truthy because 1 + 2 + 3 = 6 in a and 2 + 2 + 2 = 6 in b.

Test cases

[1, 2, 3, 4, 5] [2, 2, 2, 6, 7], 6 => True
[] [] 0 => True

Shortest code wins!


  • More test cases coming soon
  • Not sure if Deja vu is a good title or not
\$\endgroup\$
1
\$\begingroup\$

Write the date in abbreviated Latin

\$\endgroup\$
7
  • \$\begingroup\$ If 01/03 is 3 day delay then why 01/04 is not 2 day delay? \$\endgroup\$
    – l4m2
    Nov 29, 2023 at 7:43
  • \$\begingroup\$ Is Kal Iul intended if others are Jul? \$\endgroup\$
    – l4m2
    Nov 29, 2023 at 7:44
  • \$\begingroup\$ @l4m2 Thanks! They were all supposed to be Iul. I don't know how I typoed all these Jul in there. It's fixed now. \$\endgroup\$
    – Stef
    Nov 29, 2023 at 9:00
  • \$\begingroup\$ @l4m2 Because 01/04 is the day just before Non Ian, so it's prid Non Ian. If you look at the second bullet-point in the three bullet points at the beginning of "How to write dates": "A date which is just before a special day is encoded by writing prid followed by the name of that special day;" Which is why we only ever need roman numerals between 3 and 19; we never need 2. \$\endgroup\$
    – Stef
    Nov 29, 2023 at 9:02
  • \$\begingroup\$ I added this paragraph suggested by the author of the original latin.stackexchange post: "The Roman counting system is oddly inclusive to modern taste. Whenever we would say that something is n days earlier, the Romans would have said n+1. The day just before the special day is two days before it (we'd say one day) and uses prid instead of numbering, so the unnamed days start their numbering at 3." \$\endgroup\$
    – Stef
    Nov 29, 2023 at 9:27
  • \$\begingroup\$ Mai missing in places \$\endgroup\$
    – l4m2
    Nov 29, 2023 at 12:38
  • \$\begingroup\$ @l4m2 Thanks, fixed \$\endgroup\$
    – Stef
    Nov 29, 2023 at 12:48
1
\$\begingroup\$

Challenge

Create a sorting algorithm in as few bytes as possible. It can be, at worst, \$ O(n^2) \$. This can be insertion sort, mergesort, quicksort, or any other sorting algorithm with \$O(n^2)\$ time complexity.

Input

An array of numbers, such as [1,2,3] or [41,17,8].

Output

You can print an array of numbers in order, or you can print them (ordered) one by one. Sorting [3,1,2] could return:

[1,2,3]

or

1
2
3

Rules

  • Program must run in \$ O(n^2) \$ time or better
  • The program cannot use any sorting functions, libraries, etc. You can, however create a function that sorts, but it must be made from scratch in your program.

Test cases

[0,1,2,3] -> [0,1,2,3]

[5,2,8,91,4,6] -> [2,4,5,6,8,91]

[16,42,13,2,71] -> [2,13,16,42,71]
\$\endgroup\$
6
  • 3
    \$\begingroup\$ What exactly counts as a predefined function (I guess predefined sorting function, but still)? APL and its descendant languages don't have "sort"; instead, they use "grade" (given an array A, calculates [x, y, z, ...] such that [A[x], A[y], A[z]...] == sorted(A)) to implement sorting. \$\endgroup\$
    – Bubbler
    Dec 5, 2023 at 0:11
  • 1
    \$\begingroup\$ Also check out the comments under this related challenge, especially the "can I use X?" ones. \$\endgroup\$
    – Bubbler
    Dec 5, 2023 at 0:27
  • \$\begingroup\$ @Bubbler thank you for the response! I'll make sure to specify that it must be built from scratch and cannot use any sorting functions, libraries, etc. \$\endgroup\$
    – Flummox
    Dec 5, 2023 at 14:38
  • \$\begingroup\$ "Built from scratch" is still ambiguous in today's standards. Can I use min? index? Counter? partition? select_nth_unstable? \$\endgroup\$
    – Bubbler
    Dec 6, 2023 at 1:48
  • \$\begingroup\$ @Bubbler It's really hard to define. Do you have a better way to phrase it? \$\endgroup\$
    – Flummox
    Dec 6, 2023 at 14:16
  • \$\begingroup\$ No, and that's why Do X Without Y type of challenges are not recommended. \$\endgroup\$
    – Bubbler
    Dec 6, 2023 at 23:28
1
\$\begingroup\$

Pi to n digits

Calculate \$π\$ to n digits - no overshooting. The input will be a positive integer or 0. Your program should output \$π\$ displayed with exactly n digits (not counting '3.'). You cannot use any function that uses or returns pi under the hood. Standard loopholes are not allowed.

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

\$\endgroup\$
3
  • \$\begingroup\$ Does this have to work with arbitrarily large values of n if supported by the language? e.g. does a Python answer have to work for n=99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999989999999999? \$\endgroup\$
    – Someone
    Dec 7, 2023 at 2:33
  • 2
    \$\begingroup\$ This seems like a dupe of Calculate 500 digits of pi, requiring the number of digits to be variable wouldn't affect answers interestingly in my opinion. \$\endgroup\$ Dec 7, 2023 at 6:54
  • 1
    \$\begingroup\$ @Somebody It only has to work up to the largest number type supported by the language. \$\endgroup\$
    – Flummox
    Dec 7, 2023 at 14:23
1
\$\begingroup\$

Is your license plate Tetris-compliant?

Write a program that outputs a truthy value if the letters in its input are only letters that name Tetris pieces (I, J, L, O, S, T, Z), and a falsy value if otherwise.

Input: A string. You can assume it is either empty, or contains only numbers, letters in a case of your choice, and spaces.

Output: A truthy value (printing true or 1 to the console is fine) if there are no letters in the input, OR if all the letters are from the set {I, J, L, O, S, T, Z}

Objective: Code golf, so lowest score wins! Standard per-language scoring rules apply, so bytes for C#/Java/etc., codels for Piet, and so forth.

Test cases:

"" => true
"1234" => true
"123 TOL" => true
"9584K94LSZ" => false
"HELLO WORLD" => false
"LLO OL" => true
"876 TSL 234 IOT" => true,
"123 tol" => true
" " => true

Reference function:

public static bool IsTetrisCompliant(string s)
{
    var tetrisLetters = new[] { 'i', 'o', 't', 's', 'z', 'j', 'l' };
    var letters = s.ToLowerInvariant().Where(c => char.IsLetter(c));
    return letters.All(l => tetrisLetters.Contains(l));
}

Good luck!

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

Auto-golf an esolang

\$\endgroup\$
2
  • \$\begingroup\$ It's pretty easy to prove; just find code for 0 through 5 and you can get anything else from + spam. (Having all of those in the test cases might be nice.) Also maybe note the initial value of the accumulator outside of just a command specification. Possibly even consider cutting ! entirely in favor of a single implicit output so partitioning the digits doesn't detract from finding the right sequence of +~, but the limited range might make some answers more interesting anyways. \$\endgroup\$ Dec 5, 2023 at 7:52
  • 1
    \$\begingroup\$ @UnrelatedString Thank you for your input. But that proof is boring, isn't it? (-; I added the additional examples and the initial accumulator value. I believe, the possibilities given by partitioning will make this more interesting. And there are still enough numbers like 805 with a winning solution without partitioning. \$\endgroup\$
    – Philippos
    Dec 5, 2023 at 8:09
1
\$\begingroup\$

Test whether a sequence is bitonic

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

Optimal infinite monkeys: output Shakespeare with the highest probability

This challenge is something of a sequel to Write Moby Dick, approximately, but the mechanics and scoring system are quite different, and I expect it to lead to quite a different challenge.

We all know that a monkey hammering out random bytes will output the works of Shakespeare with some probability. This probability is extremely low.

But what if the monkey would type out a computer program instead, and then we run the computer program and see if that outputs the works of Shakespeare? The program might itself behave randomly, but in such a way that the probability of outputting Shakespeare is much higher overall.

The essence of this challenge is to maximise the following probability:

p(the monkey outputs your program) * p(your program outputs the works of Shakespeare)

To make that work as a practical challenge we will have to fake the randomness. Your program will not really behave randomly but will output probabilities instead, so that we can calculate the probability that your program outputs the works of Shakespeare, even if that probability is astronomically low.

more details

The following file contains the complete works of Shakespeare in ASCII format. [to do: create the file and upload it somewhere]

Your program is meant to represent a random process that might output the works of Shakespeare with some probability. But depending on how your program works that probability might be so low that it would never practically happen. So instead of using a random number generator, every time your program would output a letter it will output a probability distribution instead. Another program will keep track of the total probability.

It works like this: your program (or function etc.) will be called multiple times (about 3,500,000 times). On each invocation it will be given the first n characters of shakespeare.txt. Its output will be a probability distribution over ASCII characters, which is its probability of guessing a given next character. This output can be in any reasonable format - for example, it could be a Python array of 128 floats. But it must be a probability distribution, i.e. in this example the floats must sum to 1.

The following pseudocode shows how your score is calculated:

log_p_monkey_outputs_program = -(size of your submission in bytes)*8

log_p_program_outputs_shakespeare = 0
target_text = contents of shakespeare.txt
for n = 1 to length(target_text)-1
    probabilities = your_program(first n characters of target_text)
    correct_prob = probabilities[(n+1)th character of target_text]
    log_p_program_outputs_shakespeare += log2(correct_prob)

score = log_p_monkey_outputs_program + log_p_program_outputs_shakespeare

The score that this program calculates is the logarithm of the probability that the monkey outputs your program and your program then outputs Shakespeare, assuming that we always feed the program's output back in as input. We calculate the logarithm to avoid floating point errors, as the final probability will be extremely small.

Note that the logarithm is to base 2. If your language doesn't provide the log2 function you should use log(correct_prob)/log(2).

If the scoring program is implemented correctly, the score will always be negative. A higher score (closer to 0) is better.

Note that your program outputs a probability distribution but it should not itself behave randomly. Your program may not use a random number generator - it must always return the same probability distribution for a given input.

If you want to store state in between invocations this is allowed. You can do this by writing to an external file, by using static or global variables, by submitting a class rather than a function, using a state monad, or whatever else works for your language.

Submission format

Your submission should include the following, which do count towards the size of your submission. If they are excessively large you can link to github etc.

  • your program
  • any data it needs in order to run

Your submission should also include the following, which don't count towards its size:

  • the code used to calculate its score, implementing the pseudocode above (this doesn't need to be in the same language as your submission). Please don't golf this.
  • any code that was used to generate your submission (e.g. to create any data files that you included)
  • an explanation of how your submission works.

Rules

As mentioned, your program must run deterministically, so that it always outputs the same probability distribution given the same input (and hence always gets the same score).

If at any time the value of correct_prob in the scoring pseudocode is 0, then your score is -∞, which is the worst possible score.

You may not use any libraries or functions that your language might have that include data or statistics about natural language. This includes pre-trained neural networks, word lists, etc. It also includes any built-in function that outputs any of Shakespeare's works. It's fine to use neural networks and word lists etc., but the data or weights must be included in your submission and count towards its byte count.

You may not use any libraries or functions designed for compressing or decompressing data. It's fine to use algorithms like bzip etc., but you have to implement them yourself (and hence include the implementation in your byte count).

If you want to store state between invocations you can do this however you like, as long as your program never has access to 'future' bytes from the shakespeare.txt file. (So, for example, you can't just pass it a string containing all of the input and get back a big list of probability distributions as output.)

You must actually run your test program and calculate/verify your score before submitting your entry. If your submission runs too slowly for you to verify its score then it is not qualified to compete, even if you know what its score would be in principle.

You may import existing libraries other than the exceptions above, but you may not load any other external files unless they're included in your byte count. Your code may not access the shakespeare.txt file in any way other than described above.

A note about the scoring system

In the sandbox, several people had an intuition that the optimal answers to this challenge will take the form of compressing the shakespeare.txt file and outputting it deterministically. However, the scoring system has been carefully chosen so that this strategy will not be optimal. If you have a stochastic solution then in theory you can turn it into a perfect deterministic solution, at the cost of adding -log2(p(program outputs shakespeare)) bits of code into your program. This extra code decreases p(monkey outputs program) by exactly the same factor that it increases p(program outputs shakespeare), resulting in zero change to the overall score.

But this is the absolute best you can do. Any real encoding will be less than perfect, so in reality the net result of such a strategy will be to slightly decrease the score. Because of this, it's likely that the most competitive answers will be stochastic. However, deterministic, compression-based answers are permitted and are welcome to complete, as long as they meet the spec.


sandbox notes:

On the off chance that I'm wrong about the properties of the scoring system, I intend to battle-test this challenge before I post it. To do this I will implement (i) the obvious illegal solution using bzip2 to compress the whole text, and (ii) the not-quite-so-obvious illegal solution using bzip2 to stochastically predict the next character from the ones already received, without including a compressed version of the text in the code. I expect solution (ii) to beat solution (i), for the reasons described in the last section of the question. If it doesn't I will either give up on the challenge or add a fudge factor into the scoring system to give slightly more reward to stochastic solutions.

I'll also post a sample answer (legal but not very competitive), in order to address the point about the spec being a bit daunting to understand.

I'm unsure about the rule banning built-in compression algorithms. It seems more elegant to leave it out, and it would still be a meaningful challenge without that rule. But in Paint Starry Night, objectively, in 1kB of code off-the-shelf compression spoiled the fun a bit, and I'm worried that with this scoring system the same could happen here. I'm happy to hear any thoughts about that.

I'd also really like feedback on the score calculation pseudocode - is it sufficiently clear how the score is calculated, and can I make it clearer?

Finally, a very specific query: the ban on word tables seems like it would rule out some golfing languages. I don't want to rule out any languages but don't want to open the floodgates either, so if someone can think of a good middle ground it would be helpful.

\$\endgroup\$
16
  • \$\begingroup\$ I'd say you can encode randomness into program, resulting in a pure "output Shakespeare shortest code" \$\endgroup\$
    – l4m2
    Dec 10, 2023 at 3:51
  • \$\begingroup\$ @l4m2 if I understand correctly that would just make it a kolmogorov-complexty challenge. This is meant to be more of an optimisation challenge like Paint Starry Night or Write Moby Dick. I like Kolmogorov complexity challenges but these optimisation type challenges are quite different in terms of what makes a good answer, and that's what I'm going for with this question. \$\endgroup\$
    – N. Virgo
    Dec 10, 2023 at 3:54
  • \$\begingroup\$ @l4m2 ah - or maybe you're saying that the optimal solution will be to compress the shakespeare file and just output it deterministically? If so that's a reasonable criticism but having done the maths I'm more or less certain it's not the case. \$\endgroup\$
    – N. Virgo
    Dec 10, 2023 at 10:12
  • \$\begingroup\$ The point is that compressing the file in this way produces an optimal p_program_outputs_shakespeare but you have to include all the data in compressed form in the program, so you pay for it in p_monkey_outputs_program. If you can do some kind of lossy compression then you'll do worse at p_program_outputs_shakespeare but should be able to save more on p_monkey_outputs_program. So I expect the optimum to be some combination of compression and probabilistic guessing. \$\endgroup\$
    – N. Virgo
    Dec 10, 2023 at 10:19
  • \$\begingroup\$ Basically, if I'm right, the optimal solution should be to implement a learning algorithm with good inductive biases - something that doesn't contain much specific information about Shakespeare (hence doesn't take up much space and does well on p_monkey_outputs_program) but is good at learning patterns in the text, so that it gets better at predicting it over time and scores well on p_program_outputs_shakespeare. I could be wrong, but I've been thinking about this for a very long time and if I am wrong I don't think it will be for a trivial reason. \$\endgroup\$
    – N. Virgo
    Dec 10, 2023 at 10:24
  • \$\begingroup\$ But what is fed to learn? \$\endgroup\$
    – l4m2
    Dec 10, 2023 at 10:42
  • \$\begingroup\$ @l4m2 on each time step it gets fed the first n bytes and has to predict the (n+1) th one. So by the time it's guessing the millionth byte it's had a megabyte of data to learn from. \$\endgroup\$
    – N. Virgo
    Dec 10, 2023 at 10:53
  • \$\begingroup\$ I will check I'm right - before I post this I will implement the obvious compression-based solution using bzip etc. and see if I can beat it with stochastic guessing. If I can't then your worry is correct and I will have to change the scoring system. \$\endgroup\$
    – N. Virgo
    Dec 10, 2023 at 10:57
  • \$\begingroup\$ Come on people: comment on how the challenge can be improved or say why you think it's not suitable for this site. Just downvoting the sandbox answer doesn't help anyone. \$\endgroup\$
    – N. Virgo
    Dec 12, 2023 at 6:10
  • 1
    \$\begingroup\$ I don't understand the two downvotes personally; I'd ignore them. It might need some work, I haven't read it thoroughly enough to think of any possible issues, but it certainly seems like a cool concept \$\endgroup\$ Dec 12, 2023 at 21:17
  • \$\begingroup\$ not use a random number generator = deterministic program \$\endgroup\$
    – W D
    Dec 13, 2023 at 3:11
  • \$\begingroup\$ @WD that's right, yes - the program has to be deterministic, because we fake the randomness in order to be able to calculate the score. If this isn't clear please let me know and I will do my best to improve it. \$\endgroup\$
    – N. Virgo
    Dec 13, 2023 at 3:13
  • 2
    \$\begingroup\$ Challenge seems good, but also a bit daunting/confusing - a sample kolmogorov-complexity-esque answer could help serve as a 'template' for what kind of inputs/outputs you should program \$\endgroup\$
    – W D
    Dec 13, 2023 at 5:20
  • \$\begingroup\$ I don't think this is meaningfully different from kolomogorov complexity - given a solution to this challenge, using arithmetic coding you can get an answer which outputs Shakespeare exactly, and is only a little bit longer (assuming you can encoding raw data at almost-full efficiency). On the other hand, an answer which outputs Shakespeare exactly trivially gives a solution to this challenge \$\endgroup\$ Dec 20, 2023 at 4:53
  • \$\begingroup\$ @CommandMaster I don't think it's necessarily true that it will be only a little bit longer. Assuming optimal coding the extra length is around -log2(p(program outputs shakespeare)) bits. Adding those bits into your code means you increase -log2(p(monkey outputs program)) by exactly the same amount. But (i) optimal coding is hard, and (ii) you also have to pay the cost of implementing the decoding. These two factors mean that in practice the stochastic solution is likely to be better than the deterministic one. \$\endgroup\$
    – N. Virgo
    Dec 20, 2023 at 7:53
1
\$\begingroup\$

Convert to Spoken Binary

Convert from Spoken Binary

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

How many machines do I need?

In the game Planet Crafter, there is limited scope for automation. In particular, you can grow or extract materials, combine them into products, and launch them in rockets, which then trades them for Terra Tokens.

You can launch up to 25 items at once, and the trade takes 10 minutes to complete, during which time you would like to be able to craft the next 25 items. However, you can also craft multiple trading rockets. This means that you'll need more machines so that you can turn each rocket around before the next one arrives back. The special case is actually for single rocket, which takes the same time as two rockets but you need two more Auto-Crafters so that you can store the products while waiting for the rocket to return.

The following items are accepted for trade:

  • Bacteria Sample. Requires 3 Algae, 3 Water. Unfortunately I don't know the production speed of Algae, but 1 Water can produced every 100 seconds.
  • Iridium Rod. Requires 9 Iridium. 1 Iridium can be produced every 75 seconds.
  • Osmium Rod. Requires 9 Osmium. 1 Osmium can be produced every 75 seconds.
  • Super Alloy Rod. Requires 8 Super Alloy, 1 Aluminium. Both can be produced every 75 seconds.
  • High Quality Food. Requires 1 Honey, 1 Beans. Unfortunately I don't know the production speed of Beans, but 1 Honey can be produced every 160 seconds.
  • Fabric. Requires 2 Silk. 1 Silk can be produced every 200 seconds.
  • Uranium Rod. Requires 9 Uranium. 1 Uranium can be produced every 75 seconds.
  • Cookie. Unfortunately I don't know the production speed. It needs two extra Auto-Crafters.
  • Rocket Engine. Requires 1 Super Alloy, 2 Uranium, 9 Iridium. Each can be produced every 75 seconds. Also requires an extra Auto-Crafter.
  • Circuit Board. Requires 1 Iron, 2 Silicon, 1 Aluminium, 1 Nitrogen, 1 Water, 2 Mushroom, 1 Zeolite. Unfortunately I don't know the production speed for Mushroom. 1 Nitrogen can be produced every 80 seconds, while the others can be produced every 75 seconds. Also requires an extra Auto-Crafter.
  • Pulsar Quartz. Requires 1 Zeolite, 1 Osmium, 1 Uranium, 1 Iridium, 1 Methane. 1 Methane can be produced every 80 seconds, while the others can be produced every 75 seconds.
  • Fusion Energy Cell. Requires 3 Zeolite, 5 Osmium, 3 Uranium, 3 Iridium, 3 Methane, 1 Obsidian. 1 Methane can be produced every 80 seconds, while the others can be produced every 75 seconds. Also requires an extra Auto-Crafter.

Just to complicate matters, it's possible to buff your machines; each buff makes your machine 25% more efficient, so that four buffs would double the output, eight would triple it, and so on, however only 8 machines can be affected by a buff, at which point the buff is equivalent to two extra machines.

Fortunately, I am not expecting you to produce detailed recipes for each product. Instead, your program or function will be given the following data:

  • The number of trading rockets you wish to supply
  • The quantity required of a particular material
  • The extraction speed of that material
  • The number of buffs you intend to apply

Your program or function should then output the number of extraction machines required.

Example: Extracting Methane for Pulsar Quartz for 4 Trading Rockets:

  • You only need 1 Auto-Crafter
  • Methane takes 80 seconds each to extract.
  • Because you want to turn around 3 rockets while waiting for the 4th, you want 75 Methane in 10 minutes which is 1 every 8 seconds
  • You therefore need 10 extraction machines.

Example: Extracting Water for Bacteria Samples for 3 Trading Rockets, with 1 buff:

  • You need 1 Auto-Crafter
  • Water takes 100 seconds each to extract, but with 1 buff this reduces to 80 seconds.
  • Because the recipe uses 3 Water, and you want to turn around 2 rockets while waiting for the third, you want 150 Water in 10 minutes which is 1 every 4 seconds
  • You therefore need 20 extraction machines. (In practice, you would have 25 extraction machines, or 23 with 8 receiving 1 buff, or 21 with either 16 receiving 1 buff or 8 receiving 2 buffs, etc.)

Example: Extracting Zeolite for Fusion Energy Cells for 1 Trading Rocket, with 2 buffs:

  • You need 4 Auto-Crafters (2 for Fusion Energy Cells and 2 for only having one Rocket)
  • Zeolite takes 75 seconds each to extract, but with 2 buffs this reduces to 50 seconds.
  • Because the recipe uses 3 Zeolite, you want 75 Zeolite in 10 minutes which is 1 every 8 seconds
  • You therefore need 7 extraction machines.

This is , so the shortest program or function that breaks no standard loopholes wins!

Bonus brownie points for writing a program that takes the name of a recipe and the number of rockets and outputs the number of Auto-Crafters you need.

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

Slowest Irreducible Sorting Algorithm

Inspired by the biggest irreducible quine and hello world challenges

Sorting things quickly is something that has been greatly researched. However, sorting things in the slowest and most inefficient way is something you don't hear about very often. Let's change that.

Your task today is to write the slowest sorting algorithm, as measured by worst case scenario (O notation).

However, it needs to be optimally not-optimal - removing any steps from the algorithm should not result in a more optimal algorithm - bogosorting in a loop that runs O(n^2) times is not irreducible, as it can be done with a single bogosort.

Answer with the slowest complexity wins, tie-broken on shortest answer in bytes.

Sandbox meta

  • How could I better specify irreducibility? It's obviously not as easy as the irreducibility requirements of the byte based challenges, but there should be some method of objectively determining it.
\$\endgroup\$
3
  • \$\begingroup\$ Why can't you use byte irreducibility? \$\endgroup\$ Dec 29, 2023 at 2:52
  • \$\begingroup\$ @CommandMaster I intentionally wanted to make it about the algorithm speed rather than byte count. \$\endgroup\$
    – lyxal
    Dec 29, 2023 at 3:07
  • \$\begingroup\$ You can still require byte irreducibility to disallow useless code, but it does allow for some weird manipulations. Perhaps looking at minors of the AST which are themselves valid ASTs? \$\endgroup\$ Dec 29, 2023 at 3:19
1
\$\begingroup\$

"Perfect" an array

Given an n non-negative integers, how many numbers must be changed so that each number x appears x times? You cannot add or remove elements, only replace them.

For example:

1 6 23 6 9 23 1 1 6

can be turned into:

1 6 2 6 6 2 6 6 6

with 5 changes, which is optimal.

Test cases

0 => 1
1 2 3 => 1
5 5 5 5 5 => 0
23 7 4 8 => 3
100 100 100 6 => 4

    • Would appreciate help checking the test cases (and the sample case)
  • \$\endgroup\$
    2
    • 1
      \$\begingroup\$ Why is it being in a grid relevant? Couldn't it just be a flat array? \$\endgroup\$ Dec 28, 2023 at 19:54
    • \$\begingroup\$ @Command Master Good point. \$\endgroup\$ Dec 28, 2023 at 23:01
    1
    \$\begingroup\$

    Output a unique subset of the positive integers

    Your challenge is to output an infinite subset of the positive integers. However, the subset your program outputs must be disjoint from all the subsets that the other answers output.

    For example, if the first answer outputs an infinite sequence of square numbers 1,4,9,16,25..., the sets output by all subsequent answers cannot contain any square numbers, so the second answer can't output for example the triangle numbers 1,3,6,10... as it contains a 1. It could however output the primes 2,3,5,7,11... as by definition primes cannot be square. A third answer could output odd powers of 10 10, 1000, 100000,10000000... as this is disjoint from the previous two.

    To avoid answers taking up too much of the output space, the probability of a random positive integer being in your set should converge to a value less than 0.01. For example, the following sets would be fine:

    • 1,2,3,5,8,13... (fibonacci numbers, chance converges to 0)
    • 1,4,9,16,25... (square numbers, chance converges to 0)
    • 2,3,5,7,11... (primes, chance converges to 0?)
    • 1000,2000,3000,4000... (multiples of 1000, chance converges to 0.001)

    But the following would not:

    • 1,4,6,8,9,10,12... (composite numbers, chance converges to 1 (?))
    • 1,3,5,7,9,11... (odd numbers, chance converges to 0.5)

    Your answer may not rely on unproven conjectures, and you should be able to prove that your set is infinite and disjoint from all previous answers. For example, outputting the perfect numbers would not be allowed as it is not known whether there are infinitely many, and in the previous example outputting the pentagonal-triangular numbers \$ > 1\$ as the third answer would not be allowed as it is not known whether there are any members of that sequence that are squares.

    You may output an infinite sequence of integers, or take an integer \$n\$ and output the \$n\$th or first \$n\$ terms, using 0-indexing or 1-indexing.

    <insert winning criteria here>

    Meta

    • Should I allow taking a number and returning whether it's in the set?
    • I'm not sure about the winning criterion. I want to incentivise short code and simple sequences, so the standard "last answer wins" or "second-to-last answer wins" might not work too well, but balancing anything based on code length is annoying.
    \$\endgroup\$
    4
    • 3
      \$\begingroup\$ 1. If your sequence is <1% of unchosen values then this can go infinitely, which seems good 2. If everyone just output p^n for prime p this would get bad. We need to at least encourage someone to jump out \$\endgroup\$
      – l4m2
      Jan 3 at 23:41
    • \$\begingroup\$ If you want this to be non-cooperative then the score could be some function which increases with length and number of previous answers, and decreases with number of following answers. However, there's the problem of someone using a (seeded) RNG to choose the sequence, which would almost definitely require all following answers to implement that PRNG and generate the sequence to avoid colliding with it \$\endgroup\$ Jan 4 at 17:56
    • \$\begingroup\$ I was gonna do all of the positive integers :( \$\endgroup\$ Jan 4 at 19:23
    • \$\begingroup\$ "2,3,5,7,11... (primes, chance converges to 0?)" << Yes. The so-called prime number theorem says there are approximately a frequency of 1/log(n) primes up to n. This takes a very long time to fall below 1%, but it does eventually :-) \$\endgroup\$
      – Stef
      Jan 7 at 9:16
    1
    \$\begingroup\$

    Forward foo, reverse bar, but avoid dead code

    \$\endgroup\$
    6
    • \$\begingroup\$ Trying to count "dead bytes" is a bad idea. Consider this Pyth program. The string "rab" is interpreted and the interpreted code is even executed but since the output is suppressed it does nothing observable. This makes it extremely difficult to determine what dead code is (only made worse by not counting unexecuted code), which will almost certainly result in this being closed. \$\endgroup\$ Oct 3, 2023 at 19:16
    • \$\begingroup\$ @FryAmTheEggman This is obviously no dead code. This may make things boring for some languages, but the idea is to bring up creative solutions in other languages. \$\endgroup\$
      – Philippos
      Oct 4, 2023 at 7:55
    • \$\begingroup\$ @FryAmTheEggman I found a better definition of »dead code«, that takes in account your example. \$\endgroup\$
      – Philippos
      Dec 1, 2023 at 6:52
    • \$\begingroup\$ That is better, but what does "most other characters" mean? I think you would want to say "any other byte", but that will make languages that refuse to interpret certain bytes unable to have any dead code (which doesn't seem like what you want). \$\endgroup\$ Dec 1, 2023 at 15:49
    • \$\begingroup\$ You got me right. Even in the python or shell examples, no one shall argue, that replacing the comment characters by a newline will change the behaviour. But there is no doubt that you can replace those by most characters without anything happens. I don't want to give an exact definition of »most«. This is not legislation, it's about giving the direction of thinking, where the spirit of the challenge (and hopefully the fun) can be found. \$\endgroup\$
      – Philippos
      Dec 1, 2023 at 16:49
    • \$\begingroup\$ I think this is code-challenge. \$\endgroup\$
      – Jakav
      Dec 15, 2023 at 1:59
    1
    \$\begingroup\$

    Implement a typeface based on a 3x3 bitmap matrix

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

    Is it mate in one?

    Given a 8x8 chessboard, determine if white can checkmate black in one move. For this challenge, you may assume there are only 4 types of pieces:

    kings (represented by a "k")

    queens (represented by a "q")

    rooks (represented by a "r")

    and knights (represented by a "n".)

    The black version of these pieces are the capital version of the white pieces. You may assume both sides start with a king, and that every position will be legal, (e. g. there won't be any positions where white can just take black's king) and white will never be in check. Squares with no pieces on them can be any char you like that is not in "kqrnKQRN". You will not have to consider short or long castles. All pieces move the same way they do in normal chess.

    An example

    For example, in the following position:

    ......RK
    .......Q
    ........
    ......nq
    .........
    .........
    .........
    k.......
    

    White can play the move Qxh7, checkmate.


    • I have not tried this myself.
    • Any suggestions or/for test cases?
    \$\endgroup\$
    2
    1
    \$\begingroup\$

    Validate a CPF number

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

    Aircraft registration numbers

    Write a program that takes a United States aircraft registration number and returns a 24-bit ICAO hex code corresponding to that registration and vice-versa.

    An aircraft registration number always begins with an N and is followed by 1 to 5 characters: 1 to 5 digits and then 0 to 2 letters. That is, one of the following three patterns:

    • N plus 1 to 5 digits
    • N plus 1 to 4 digits then one letter
    • N plus 1 to 3 digits then two letters

    The first digit cannot be 0 and the letters I and O are not used. The letters always follow the digits.

    ICAO hex codes assigned to the US are numbers from A00001 to ADF7C7 (in hexadecimal). They are assigned in alphanumeric order: A00001 corresponds to N1, A00002 corresponds to N1A, A00003 to N1AA, A00004 to N1AB, etc., up to ADF7C7 for N99999.

    Some test cases:

    Registration ICAO code (hex) ICAO code (decimal)
    N17CA A11707 10557191
    N1PP A00155 10486101
    N959ZP AD5863 11360355
    N999ZZ ADF669 11400809

    You can assume no invalid inputs will be given.

    \$\endgroup\$
    1
    • \$\begingroup\$ s/numbers/digits/ \$\endgroup\$
      – Philippos
      Jan 15 at 15:43
    1
    \$\begingroup\$

    Validate a codice fiscale

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

    The TAK function

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

    This is my first challenge here, and I know I'm not supposed to start with a KotH. But I had this idea and I think it is simple enough while allowing more advanced strategies, so here it is:


    Tank Game

    There are two tanks on a 16×16 toroidal grid (wrapping in both directions), one starting at (0, 0) and its opponent starting at (8, 8). The objective is to occupy the enemy base (starting point) without getting shot. Some grid cells are walls, which tanks can't move, shoot or see through. Each submission includes 2 separate programs that form a team, a commander and a tank driver. Direct communication between them is not allowed, but actions of the commanders are visible to the drivers, allowing you to encode some information that way.

    The commander

    • Sees the entire map and the positions of the tanks.
    • Can build or destroy walls.

    The tank

    • Has very limited vision but knows its position.
    • Sees the actions of both the friendly and the enemy commander.
    • Can move in a straight line up to 3 cells.
    • Can shoot in a straight line.

    Details of the game

    The tanks and commanders take turns in the following order:

    1. Commander of 1st submission
    2. Tank driver of 2nd submission
    3. Commander of 2nd submission
    4. Tank driver of 1st submission

    Although from an outside perspective your tank may start at either (0, 0) or (8, 8), the map and all other coordinates provided to your programs (including enemy actions) will be translated by the controller to make it look like your tank started at (0, 0) and has to go to (8, 8). This is done so your program doesn't have to check where it started from.

    The starting position looks like this:

          | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15 <--- Coordinates observed by Tank 1
          | 8| 9|10|11|12|13|14|15| 0| 1| 2| 3| 4| 5| 6| 7 <--- Coordinates observed by Tank 2
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
     0  8 |T1|  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
     1  9 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
     2 10 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
     3 11 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
     4 12 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
     5 13 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
     6 14 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
     7 15 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
     8  0 |  |  |  |  |  |  |  |  |T2|  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
     9  1 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
    10  2 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
    11  3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
    12  4 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
    13  5 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
    14  6 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
    15  7 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    ^^ ^^
    || ++---- Coordinates observed by Tank 2
    ++---- Coordinates observed by Tank 1
    
    T1: Starting position of Tank 1, target of Tank 2
    T2: Starting position of Tank 2, target of Tank 1
    

    The commander receives two arguments, map and enemyAction:

    • map: (x: number, y: number) => Cell:

      • A Cell is one of the following:

        • ' ' (space): empty cell
        • '#': wall
        • 'F': friendly tank
        • 'E': enemy tank
      • x and y wrap around (mod 16).

      • You can't directly modify the map

    • enemyAction: Action

      • type Action = { action: 'B'|'D', x: number, y: number } | null
        
      • The last action of the enemy commander.
      • Given only for convenience, it could be computed from the map.

    And must return one of the following actions:

    • { action: 'B', x: number, y: number }:

      • Builds a wall.
      • Walls can not be built on the two bases ((0,0) and (8,8)) and on cells with tanks. Attempting to do so is an error.
    • { action: 'D', x: number, y: number }:

      • Destroys a wall.
      • Attempting to destroy a non-existing wall is an error.
    • null:

      • Does nothing.

    The tank driver receives four arguments:

    • x: number, y: number: position of your tank
    • friendlyAction: Action, enemyAction: Action: the last actions of the friendly and enemy commanders.

    And must return one of the following actions:

    • { action: 'M', direction: Direction, distance: number }

      • Move the tank (up to 3 cells in a straight line, instantly).
      • Direction is one of the following:
        • 'U': negative y direction (up)
        • 'L': negative x direction (left)
        • 'D': positive y direction (down)
        • 'R': positive x direction (right)
      • 1 <= distance <= 3
      • If the tank can't move distance cells because a wall or the enemy tank is in the way, it stops moving before colliding with that (it will not move at all if the obstacle is directly in front of it).
    • { action: 'S', direction: Direction }

      • Shoot.
      • The bullet travels in a straight line until it hits a wall or a tank, instantly.
      • If you hit the enemy tank, you immediately win the round 2-0.
      • You can't shoot yourself.
    • { action: 'L', callback: (Result) => void }

      • Look around (in straight lines in all 4 directions).
      • type Result = { U: number, L: number, D: number, R: number, enemyDirection: Direction | null }
        
        • U, L, D and R are the lengths of empty cells in the respective directions.
        • enemyDirection is the relative direction of the enemy tank, if visible. If there are no walls in the row/column, it will be the direction which the enemy is closer in.

    Scoring

    • Reaching (8,8) and surviving until your next turn: win 3-0
    • Shooting down the enemy tank: win 2-0
    • Reaching turn number 40 without a winner: draw 1-1
    • Throwing an error or returning invalid action: lose 0-3

    Technical details

    The submissions must consist of two separate programs written in . The programs may not use any APIs that aren't part of the language itself (i.e. browser or Node.js APIs) and may not introduce globally observable changes (including but not limited to prototype pollution and mutating built-in objects). The programs may not run code asynchronously.

    To keep the game reproducable, Math.random() will be replaced with a seeded PRNG, which you can use for randomness, but please don't introduce any other non-determinism.

    The commander must be a script with a function commander in the top-level scope. Likewise, the tank driver has to have a function named tankDriver. You may create helper functions and variables for storing state (state will be reset after each game).

    Each submission will be run against every other submission in pairs, 2×5 times for each pair (each submission starting 5 times). The maps will be randomly generated. The submission reaching the highest total score wins the challenge.

    The controller is not yet done, I want to get feedback about the challenge first.

    Besides the ones listed above, standard loopholes also apply.

    I reserve my right to disqualify entries that violate the above rules or ones that I deem to be cheating. I will always notify the author in advance and allow them to fix the problems.

    \$\endgroup\$
    12
    • \$\begingroup\$ If all tanks start at (0, 0), does that mean multiple tanks can be on the same tile? And also, what do the numbers in C1 T2 C2 T1 mean? \$\endgroup\$ Jan 25 at 14:25
    • \$\begingroup\$ @AlanBreadel From an outside perspective, one tank starts at (0,0) and the other at (8,8) as mentioned in the introduction. But both tanks see the world as if the tile they started on is (0,0), so they don't have to use conditional logic to decide if they should go to (0,0) or (8,8). I'll try to clarify this. Also, I can easily remove this rule if it's too confusing. C1 T2 C2 T1 means "commander of first player; tank of second player; controller of second player; driver of first player" \$\endgroup\$
      – FZs
      Jan 25 at 15:15
    • \$\begingroup\$ Ah, so each tank is paired up with one other tank. Is that other tank with another submission or something else? \$\endgroup\$ Jan 25 at 15:20
    • \$\begingroup\$ Yeah, 2 tanks at a time. One submission consists of one team of a commander and a driver, controlling one tank and editing the map. \$\endgroup\$
      – FZs
      Jan 25 at 15:22
    • \$\begingroup\$ I'm pretty sure king of the hills are supposed to put all submissions against each other, but this is probably also fine. Maybe a swiss format? (e. g. one tank and commander against every other tank and commander team.) \$\endgroup\$ Jan 25 at 15:24
    • \$\begingroup\$ Also, (0, 0) and (8, 8) imply a 9x9 grid (assuming those are the edges. I'm a bit confused because it specifies 16x16.) It should be (0, 0) and (7, 7) with 0-based indexing, or (1, 1) and (8, 8) with 1-based indexing. \$\endgroup\$ Jan 25 at 15:25
    • \$\begingroup\$ This is described near the end, "Each submission will be run against every other submission [...]". Also, I have seen KotH's on this format on CGCC \$\endgroup\$
      – FZs
      Jan 25 at 15:27
    • \$\begingroup\$ The map is 16×16, and toroidal (meaning wrapping around). This means (0,0) and (8,8) are the furthest cells (because to get to (15,15) you could just wrap around from 0 to 15 in two steps). \$\endgroup\$
      – FZs
      Jan 25 at 15:30
    • \$\begingroup\$ If a tank moves right say, 5 squares, is that instant or does it take 5 turns with 1 square per turn? \$\endgroup\$ Jan 25 at 15:39
    • \$\begingroup\$ I'll have to clarify that. Tanks can move up to 3 cells instantly. They can move longer than 3 cells in multiple turns \$\endgroup\$
      – FZs
      Jan 25 at 15:44
    • \$\begingroup\$ So for example I try to move 7 tiles, I'll move 3 in one turn, 3 in the next, and 1 in the turn after that, right? But then I decide I want to do something else on the second or third turn. Can I stop the movement and do something else or does it override everything? \$\endgroup\$ Jan 25 at 17:05
    • \$\begingroup\$ I already edited my post, see the edit. You can't return "move 7 tiles", that is an error. You'd have to go "move 3", "move 3", "move 1" to move 7 in effect. \$\endgroup\$
      – FZs
      Jan 25 at 19:18
    1
    \$\begingroup\$

    Demonstrate that 1³+2³+...+n³ = (1+2+...+n)²

    The following image is a proof without words that \$\sum_{i=1}^{n}i^3=\left(\sum_{i=1}^{n}i\right)^2\$, or in other words, the sum of the first n cubes equals the square of the sum of the first n positive integers.

    enter image description here

    The image contains (the equivalent of) 1 square with side length 1, 2 squares with side length 2, etc up to 5 squares with side length 5. The 1x1 squares have a total area of 1x1x1 = 1³, the 2x2 squares have a total area of 2x2x2=2³, and the 5x5 squares have a total area of 5x5x5=5³. Overall, the total area of all the squares is 1³ + 2³ + 3³ + 4³ + 5³.

    But, the larger square has a side length of 1+2+3+4+5, and an area of (1+2+3+4+5)². And, since all the small squares take up the same space as the large square, they must have the same total area, so 1³+2³+3³+4³+5³ = (1+2+3+4+5)². This can be shown to work for all positive integers.

    The above can also be represented as the following integer matrix:

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

    This matrix can be thought of as a series of "bands", where each band #n contains all points at coordinates (x, y) where max(x, y) = n. Every point in the first band, containing the point at coordinates [1, 1], contains 1; the second, containing [[1, 2], [2, 2], [2, 1]], and the third, containing [[1,3],[2,3],[3,3],[3,2],[3,1]], contain only 2s, the next 3 bands contain only 3s, and so on up to 5.

    Your challenge is to, given a positive integer n, output the corresponding integer matrix for n. The above matrix should be output when 5 is input.

    This is , shortest wins!

    \$\endgroup\$
    3
    • \$\begingroup\$ Can I print this matrix infinitely? Or take i,j and output the element in those coordinates? \$\endgroup\$ Jan 29 at 3:55
    • \$\begingroup\$ @CommandMaster I'm gonna say no to that, I don't really see the point of the first and the second oversimplifies things. \$\endgroup\$
      – emanresu A
      Jan 29 at 6:34
    • \$\begingroup\$ Looks similar to the one that output \$\begin{matrix}1&2&3&4\\2&2&3&4\\3&3&3&4\\4&4&4&4\end{matrix}\$ \$\endgroup\$
      – l4m2
      Jan 29 at 6:41
    1
    86 87
    88
    89 90
    157

    You must log in to answer this question.

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