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

4636 Answers 4636

1
85 86
87
88 89
155
1
\$\begingroup\$

Fastest decimal to binary

Same challenge, but code golf

Given a decimal number, your task is to convert it to binary.

Test cases

8496867758 -> 111111010011100111110100110101110
28284301455933783441 -> 11000100010000110000001100101000101001000111111110011110110010001
701550526345030865283462565098928586836 -> 1000001111110010011011011101110100010101010100010110011100010101100110100000111111010100100011101000000011010011011100000001010100

Rules

  • You can take input either as a string containing decimal digits, or a list of decimal digits.
  • You need to output the number in binary, either as a string containing the binary digits or a list of binary digits.
  • You are allowed to have leading zeros in the output.
  • The input won't contain leading zeros.

Scoring

Your score is the maximum number of digits your code can handle in under a second on my computer (Intel Core i7-9700 with 8 threads, 32GB RAM). If your code takes less than a second for a number with a million digits, you beat all solutions which can't do that, and the tie-breaker is the time it takes for a million digit number.

To calculate the time I will randomly select 10 numbers, and look at the average time.

Meta question

Is this a dupe? I looked for this question but couldn't find it.

I noticed that using GMP's standard I/O functions this takes 0.05 seconds for a million digit number. Is there a point to this question, or is it likely GMP is optimized enough that this will be the winning solution?

\$\endgroup\$
6
  • \$\begingroup\$ Will the program be reset between calls or is it allowed to reuse temporary values (e.g powers of 10) computed in the first call for the other 9 calls \$\endgroup\$
    – bsoelch
    Sep 21, 2023 at 15:35
  • \$\begingroup\$ @bsoelch I'd say it's reset between calls, although allowing precomputation somehow might be good? I'm not sure what would be more interesting. \$\endgroup\$ Sep 21, 2023 at 15:39
  • \$\begingroup\$ On my computer time python3 -c 'bin(int("1"*1000000))' executes for 4 seconds \$\endgroup\$
    – l4m2
    Sep 22, 2023 at 0:31
  • \$\begingroup\$ About GMP: You could ban third party libraries. At least in Python the standard library version of string to int is not the fastest possible solution (I tried a relatively simple recursive approach and managed to get the time for 1000000 digits from over 4 seconds to below one second). \$\endgroup\$
    – bsoelch
    Sep 22, 2023 at 17:20
  • 1
    \$\begingroup\$ Bad news: Python is probably getting an impl that can convert 4,000,000-digit numbers in 0.3s. It is already available as a 3rd party lib. github.com/python/cpython/issues/90716#issuecomment-1717742073 \$\endgroup\$
    – Bubbler
    Sep 25, 2023 at 6:32
  • 1
    \$\begingroup\$ Also there is very little point in banning 3rd party libs, as you can always copy the entire code to submit it anyway. \$\endgroup\$
    – Bubbler
    Sep 25, 2023 at 6:38
1
\$\begingroup\$

Barbrack

Your task is to write a program or function that takes a non-negative integer (in decimal or any other convenient base for your language) and output a number in the numbering system Barbrack.

What's that?

Barbrack is a numbering system I made up that can represent non-negative integers. Zero is represented with an empty string or an underscore, one is represented with [], and all other positive integers can be represented with a brack.

A brack is delimited with brackets [] and works as follows (with an example of 84):

  1. Take your number a and find its prime factorization. In this case, the prime factorization of 84 is 22*31(*50)*71.
  2. Find the indices of these primes, where the index of 2 is 1. In this case, the index of 3 is 2, since it's the prime right after 2, and the index of 7 is 4, since it's the fourth prime.
  3. Take the exponents of each prime, and put them in brackets in increasing order of the size of the prime, with consecutive exponents being separated by bars (|). So the general format is [exponent of 2|exponent of 3|exponent of 5…]—in this case, [2|1|0|1]. Minimize the number of cells!
  4. Recursively calculate the exponents in Barbrack, remembering that 0 is the empty string and 1 is []. So [2|1|0|1] => [[1]|[]||[]] => [[[]]|[]||[]].
  5. Output the final result.

Test inputs

0 -> (nothing)
1 -> []
2 -> [[]]
5 -> [||[]]
45 -> [|[[]]|[]]
84 -> [[[]]|[]||[]]
65535 -> [|[]|[]||||[](48 bars)[]]
65536 -> [[[[[]]]]]

(sidenote: (48 bars) means 48 consecutive bars in the actual output)

Rules

Scoring

Minimum bytes on a per-language basis.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Can characters other than [|] be used? \$\endgroup\$
    – lyxal
    Sep 24, 2023 at 23:59
  • \$\begingroup\$ No, actually. I would allow other symbols, but I'm trying to stay true to my own base. (Let me guess, angle brackets for Vyxal?) \$\endgroup\$
    – Someone
    Sep 25, 2023 at 0:02
  • \$\begingroup\$ @Someone It's generally preferred to be flexible with the output format. There's no reason for those characters specifically to be used, as far as I can tell. In fact, instead of strings, you could allow nested lists too (unless I'm reading the challenge wrong) \$\endgroup\$
    – user
    Sep 25, 2023 at 1:15
  • \$\begingroup\$ similar challenges: codegolf.stackexchange.com/questions/139034/encode-an-integer codegolf.stackexchange.com/questions/254870/… \$\endgroup\$
    – bsoelch
    Sep 25, 2023 at 9:45
  • \$\begingroup\$ Yeah, the /10 bonus was definitely imbalanced. \$\endgroup\$
    – Someone
    Sep 25, 2023 at 12:56
  • \$\begingroup\$ Input validation is generally discouraged. Is there a particular reason you want it? How would it even work if I write a function which takes unsigned int as input? \$\endgroup\$ Sep 25, 2023 at 18:45
  • \$\begingroup\$ Fair point. The rule was basically just "undefined behavior" but dumber anyway. \$\endgroup\$
    – Someone
    Sep 25, 2023 at 18:47
1
\$\begingroup\$

Golf my code


For this challenge, I'll use edit histories of answers to create a dataset of answers that have been golfed. Your task will be to write a program/function that, given a submission that was golfed in the future, will attempt to golf the submission.

You may choose the language, out of a set I'll choose based on the quantity and quality of data available, that your inputs will be in. You may choose to take inputs from multiple languages, which will not be differentiated (e.g., you can choose to score your answer over a combined Python + Jelly dataset).

The first part of your score will be the sum of bytes golfed by your program for each input, with any submissions that don't become shorter (including becoming longer) or become invalid having no impact on your score (might change this later, since otherwise you have no reason not to use a dataset of all languages).

Your final score will be your score, minus the number of bytes in your program. So, if you golf a total of 1920 bytes off the Python answers dataset, with 1080 bytes of code, your final score will be 840. Higher scores are better.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I get the idea that the program is supposed to golf answers in a specific language, but I don't understand how we're expected to do that and programmatically return correct golfed answers, please add an example \$\endgroup\$
    – noodle man
    Sep 30, 2023 at 18:18
  • 1
    \$\begingroup\$ On top of the problem of validation, I feel like this has some problems depending on the languages you pick. Definitely don't include unary. \$\endgroup\$ Oct 3, 2023 at 19:20
1
\$\begingroup\$

Given A Binary String, Determine Which Of Certain Substrings Are Equal And Opposite

yea the title is going to need some work

Concept

Take an even length binary string

1 1 0 1 0 0 1 0

Between each bit, place an arrow

1 1 0 1 0 0 1 0
 ^ ^ ^ ^ ^ ^ ^

Next, find each substring centered on each arrow which includes either/both the start and the end of the string

1 1
 ^
1 1 0 1
   ^
1 1 0 1 0 0
     ^
1 1 0 1 0 0 1 0
       ^
    0 1 0 0 1 0
         ^
        0 0 1 0
           ^
            1 0
             ^

If each half of the binary string has all of the flipped bits of the other half (in any order), replace the arrow with a 1, else a 0

1 1
 0
1 1 0 1
   0
1 1 0 1 0 0
     1
1 1 0 1 0 0 1 0
       1
    0 1 0 0 1 0
         0
        0 0 1 0
           0
            1 0
             1

Then get rid of the sublists which will leave you with just the arrows-turned-bits

 0 0 1 1 0 0 1

You must output those bits.

Examples:

00 0
01 1
10 1
11 0
0000 000
0001 001
0011 010
1001 111
1011 100
1100 010
000011 00010
100101 11111
101101 10001
00110011 0101010
00111100 0101010
10101010 1111111
11000101 0111011
11010010 0011001
11100010 0011101

Meta

yea I don't have the vocabulary for this. I'm gonna hammer at it some more but if you read this and something jumps out at you where youre like "oh i know what thats called" Please let me know thank you

\$\endgroup\$
10
  • \$\begingroup\$ What does "opposite digits" mean? \$\endgroup\$
    – Someone
    Sep 25, 2023 at 0:22
  • \$\begingroup\$ @Someone im not sure how to phrase it, but if you have X 1s and Y 0s on one end, you need to have Y 1s and X 0s on the other side. \$\endgroup\$ Sep 25, 2023 at 1:05
  • \$\begingroup\$ So order doesn't matter? \$\endgroup\$
    – Someone
    Sep 25, 2023 at 12:55
  • \$\begingroup\$ @Someone exactly. Would tacking "in any order" onto it fix that, or would you suggest a full rephrasing? EDIT: actually tried something out here, any better or still off? \$\endgroup\$ Sep 25, 2023 at 19:08
  • \$\begingroup\$ It's good—I was just making sure. I think the examples explain it well enough. \$\endgroup\$
    – Someone
    Sep 25, 2023 at 19:23
  • 1
    \$\begingroup\$ (1) For your example 11010010, the answer should be 0011001, shouldn't it? (2) Can I rephrase the task to »For each position to break the string into two, starting from the left, place a 1 if the number of 0 digits on the shorter part is equal to the number of 1 digits among the neighboring substring of the same length on the other side, otherwise, put a 0.«? \$\endgroup\$
    – Philippos
    Oct 3, 2023 at 12:25
  • \$\begingroup\$ @Philippos (1) Yes, typo, corrected, thanks! (2) Yes! Can I include that wording / a version of it? that seems like the way to go as far as making this more explicit/formally stated... Thanks :-) \$\endgroup\$ Oct 3, 2023 at 15:10
  • \$\begingroup\$ (1) The same typo is in the final line of the demonstrated example; I'm sorry I can't correct it myself. (2) Of course you can, maybe with some more words to make it more comprehendable. \$\endgroup\$
    – Philippos
    Oct 3, 2023 at 16:51
  • \$\begingroup\$ @Philippos (1) lmao how did i miss that twice, thanks (2) Thank you, I'll keep working on it based on your suggestion :-) \$\endgroup\$ Oct 3, 2023 at 17:11
  • \$\begingroup\$ If you want to thank me, please comment on my idea. someone downvoted, but did not write why. \$\endgroup\$
    – Philippos
    Oct 3, 2023 at 17:56
1
\$\begingroup\$

Generate Conway's Atomic Elements

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

Implement the RegPack decompressor

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

Is it a stable structure?

In this challenge, a structure is a combination of row of ---- and columns of |, such that all rows are above at least one column and all columns are on top of either a row or the ground. Additionally, a structure must have all its component rows or columns connected vertically.

For example, the following are structures:

          ---      -----      -----
     |     |        |  |      | | |
|    ---   |----    -- -----  |---|
|     |    |   |    |  |   |  | | |

And the following are not:

|             |                     |
     --    ---|   ---- ---          |-----
|   |  |    | |   |      |     ---  || |

The last two are not structures because, although they satisfy all the other rules, they contain multiple vertically connected parts - specifically, the end of a - cannot connect with the side of a |.

A single row of -s can have multiple |s under it. That row is stable if the center of the row occurs within the span of the |s. For example, take this row:

---X---
 |  ||

The center of that row is the position marked X, and as this falls within the outer two |, the row is stable.

---XX---     ---XX---
   |||          |

You can also have rows with even length, in which case both central positions have to fall within the span of the columns. The first example here is stable, the second is not.

---X---
   |

Rows can even be balanced on a single | as long as their center is on that |.

A structure is stable if every row of ---- in it is stable by the above criteria.

Your challenge is to, given a valid ascii-art structure by the criterion above, determine whether it is stable or not.

Output may either be truthy/falsy using your language's convention (swapping is allowed) or outputting two distinct values for truthy/falsy.

This is , shortest wins!

Testcases

Truthy

|

-
|

---
| |

  ---
  | |
--- ---
 ||  |

-----
 | ||
 |---
 | |

|
---------
 | |    |


   -------
   |  |
  ------
  | |  |
-----  |
|  |   |

Falsy

--
|

--------
   |

------
| |
------
 |  |

  ---
    |
---------
    |


------------------
 | | |

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

Make a super fair number

\$\endgroup\$
1
  • \$\begingroup\$ I'm not sure if the super fair condition is equivalent to every slice with an arithmetic progression of digit positions being evenly distributed, but I think this alternate condition might be easier for solvers to prove correctness for. \$\endgroup\$
    – xnor
    Aug 5, 2022 at 11:38
1
\$\begingroup\$

Compile Japt to JavaScript

this is a work in progress challenge! the spec is not finished

[Japt] is a programming language designed by [@ETHProductions] in 2017 designed as a code-golf version of JavaScript (from which its name is derived; JavaScript → Japt). Code written in Japt is compiled to JS code. This challenge is about code-golfing that compilation process.

For this challenge, we will be using a slightly simplified version of Japt that does not support compressed string literals, shortcuts, or ß for recursion. This version of Japt also lacks the semi-famous bug that unterminated array literals make the parser break.

Japt syntax

Japt programs consist of a series of chained function calls (like the JavaScript something.a(1).b(2).c(3)). In Japt, these are written as follows:

a1 b2 c3 

Each lowercase letter tells the parser to start reading arguments, and each space tells it to stop and call the function with those arguments. Here's what passing multiple arguments to functions looks like:

a1,2 b3,4,5 c6 

Japt programs don't just consist of lowercase letters, digits, and spaces. Japt has syntax for four kinds of literals:

  1. Numbers, like 1234 or 1.23 or 0.7
  2. Strings, like "abcd" or "player 1 has {U} points" (interpolation)
  3. Arrays, like [1,2,3] or [1,"a",["b","c",[2]],"d"]
  4. Functions, like X{X+1} or XYZ{XaY b5 +Z} (uppercase letters are parameter names, brackets surround function body)

An expression is made of one of the above literals, followed by any number (including zero) of chained function calls.

Note that, when the either the program ends or the parser hits a newline, any unfinished literal or function call is automatically closed:

mX{Xa"bcd

can still be parsed as calling m with a function that takes X and calls a on it with argument "bcd", even though many structures are not fully

Compilation to JavaScript

Japt expressions translate pretty much one-to-one with JavaScript expressions. Many expressions can be translated slightly differently and have the same results, so for this challenge, any output that is equivalent to the JavaScript expression as explained here is OK output. For example, for a1 b2 c3 you may choose to output U.a(1).b(2).c(3) or you might output U.a(1 ).b((2)).c(3 ) or similar.

If a number literal is the first part of a chained function call, it must be either surrounded in parentheses (1.5 becomes (1.5)) or have a trailing space (1.5 ). Your submission may choose either of these. You may also choose to have all numbers follow one of these conventions, not only

Test cases

Japt:
a1 b2 c3
JavaScript:
U.a(1).b(2).c(3)

Japt:
a1b2c3 d4  e5
JavaScript:
U.a(1 .b(2 .c(3).d(4)).e(5)

Japt:
q| mZ{ùT+=Zl} ú mZ{Z+S+V
JavaScript:
U.q("I").m((Z)=>Z.ù(T+=Z.l())).ù().m((Z)=>Z+S+V)

Japt:
1 +2 +3 +4
JavaScript:
(((1)+2)+3)+4
\$\endgroup\$
1
\$\begingroup\$

Pushing Penguins on an Integer Iceberg

An iceberg is represented by a rectangular grid of cells. Each cell can hold one of three penguins. Penguins can be pushed in any free orthogonal direction, but they slide until they reach the edge of the grid or would bump into another penguin. Example:

.........
.1.....2.
....3....
.........

If you push each penguin in turn to the right, they will end up in the following positions:

.........
......1.2
........3
.........

Given an initial position and a target cell, your challenge is to push any of the penguins so that it comes to rest in that cell.

You can take the initial position as an iceberg size and list of penguin coordinates, or as an iceberg array of bytes, with one value for the empty cells and one or three distinct values for the penguins. In the latter case the target cell can have its own distinct value or it can be a coordinate. (Although the input can only be bytes the type of the array can be larger.)

The output list of pushes should identify the penguin to be pushed, either by its initial index or its current position, and either the direction (which can be encoded as any four convenient byte values) or target of the push, or if the penguins have three distinct values then it can be a list of updated iceberg arrays each with one penguin having been pushed to a new position from the previous. (The initial position does not have to be included in the output.)

You can assume that the target cell will be in the interior of the iceberg as the edge cells are trivial as they only require two penguins to solve. (And the corner cells are even more trivial as they only require one penguin.)

Your doesn't have to output an optimal solution but it must be deterministic. One approach is to devise a systematic solution that solves every cell on the iceberg but only output as far as the target cell.

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

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

Moved to the main site

\$\endgroup\$
2
  • \$\begingroup\$ I'd recommend not having a fixed message required for the case where no order is possible -- AFAIK, the way it's usually done in code golf challenges is to allow the golfer to pick any distinct symbol to output. (Also, of the two options given, there is absolutely no way that any golfer would choose to output the full sentence instead of the empty string.) \$\endgroup\$ Oct 16, 2023 at 22:06
  • \$\begingroup\$ @97.100.97.109 Of course not! This was just meant to be a funny side mark, maybe drawing some other jokes in the answers. But I can omit it if it confuses. \$\endgroup\$
    – Philippos
    Oct 17, 2023 at 9:53
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\$

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

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
    85 86
    87
    88 89
    155

    You must log in to answer this question.

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