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

4643 Answers 4643

1
10 11
12
13 14
155
4
\$\begingroup\$

Calculate the 'geothmetic meandian' of a set of numbers

Randall Munroe's March 10 xkcd comic "Geothmetic Meandian" defines the 'geothmetic meandian' of a set of positive real numbers as follows.

Define a function F, such that F accepts a set of n positive real numbers and returns the set (a, b, c), where a is the arithmetic mean of the set (the sum of the numbers in the set divided by n), b is the geometric mean of the set (the product of the numbers in the set to the power of 1/n), and c is the median of the set (the average of the middle two numbers in the sorted set when n is even, and the middle number in the set when n is odd). The function F can therefore be applied again to its own output. Iterating F an infinite number of times should cause its three outputs to converge to one value g. This value g is defined as the geothmetic meandian of the original set of positive reals. (For the purposes of this challenge, you may assume this value exists and does not diverge.)

Given a nonempty list of positive real numbers in any convenient and reasonable format and a positive integer q, compute its 'geothmetic meandian' to q significant figures. Standard rules apply, and the shortest code in bytes wins.

Test cases

[[1], 2] --> 1.0
[[2, 8], 4] --> 4.742
[[1, 1, 2, 3, 5], 6] --> 2.08906
[[1, 2, 4, 8], 6] --> 3.13227
[[1.1, 2.2, 4.4, 8.8], 9] --> 3.44550208
\$\endgroup\$
9
  • 4
    \$\begingroup\$ This seems like a decent challenge, but I don't know if the rounding requirement adds anything. \$\endgroup\$
    – rak1507
    Mar 11, 2021 at 2:40
  • \$\begingroup\$ @rak1507 I was accounting for if different languages have different levels of floating-point precision, and also because the calculation needs to stop at some defined point. \$\endgroup\$
    – Cloudy7
    Mar 11, 2021 at 3:24
  • 3
    \$\begingroup\$ The problem with taking the number of significant figures q as input is that you're banning the use of float and double numbers entirely (doubles will break at q >= 16 or so), which is a big no-no. You could take the number of iterations i instead and require the solutions to output the result of i-th iteration. \$\endgroup\$
    – Bubbler
    Mar 12, 2021 at 5:05
  • \$\begingroup\$ @Bubbler I envisioned part of the challenge to be determining when to stop the iteration of F. Should I then restrict q to be a positive integer from 1 to 7 or something similar? \$\endgroup\$
    – Cloudy7
    Mar 12, 2021 at 17:28
  • \$\begingroup\$ Alternatively, we can have have a fixed number of iterations i and output the geothmetic meandian to the highest precision possible given i iterations. However, thinking about it, I agree this part of the challenge may be unfeasible. \$\endgroup\$
    – Cloudy7
    Mar 12, 2021 at 17:39
  • \$\begingroup\$ Oh dear. I just tried another test case and due to floating-point errors in calculation, my program slowly drifts by 2e-12 indefinitely as F is iterated... \$\endgroup\$
    – Cloudy7
    Mar 12, 2021 at 17:49
  • 3
    \$\begingroup\$ How about this: Given a value q (a positive floating-point number), stop iteration when the difference between the maximum and the minimum is less than q, and output any of the three numbers (or all of them). Allow the solutions to fail if q is too small compared to the input (i.e. it is outside the precision capability of the floating-point type in use). I think this is clearer to specify the error margin this way. \$\endgroup\$
    – Bubbler
    Mar 15, 2021 at 3:46
  • \$\begingroup\$ Or just require that all programs use a fixed q, e.g. 100? \$\endgroup\$
    – pxeger
    Mar 20, 2021 at 17:53
  • 1
    \$\begingroup\$ I feel like adding anything to do with the precision will just complicate things, and most of the code will be for handling that, not for actually answering the challenge. IMO it's fine to say 'until it converges', and leave specifics up to the challenge answerers. \$\endgroup\$
    – rak1507
    Mar 22, 2021 at 12:19
4
\$\begingroup\$

Hide a message in ASCII art and an image

(needs cooler title)


Cops


Robbers

\$\endgroup\$
7
  • 1
    \$\begingroup\$ How the heck?! I was just drafting a challenge about stenography and images yesterday and then I see this.. \$\endgroup\$ Mar 26, 2021 at 16:28
  • \$\begingroup\$ @RedwolfPrograms was your idea the exact same as mine? \$\endgroup\$
    – Beefster
    Mar 26, 2021 at 16:35
  • 1
    \$\begingroup\$ Not identical, there was no ASCII art included, but considering there are only 5 steganography questions on the whole site that's an insane coincidence \$\endgroup\$ Mar 26, 2021 at 17:03
  • 1
    \$\begingroup\$ If the robber doesn’t know any of the messages, it might be hard to verify any potential explanation. It might be more fun and easier to verify a correct solution if the cop posts N codes and the solutions to N-1 of them, and the robber has to use those to reverse engineer the method and decode the last one. Alternately, the cop could have to pick from a list of pre-selected messages so the robber has some idea what to look for. \$\endgroup\$ Mar 26, 2021 at 17:33
  • 1
    \$\begingroup\$ Do the ascii+png files have to contain all the information necessary for decoding? For example, could I use a book cipher where the PNG encodes word numbers, and you then have to look up the corresponding words from The Great Gatsby? \$\endgroup\$ Mar 26, 2021 at 18:03
  • \$\begingroup\$ @water_ghosts I think a book cipher should only be allowed if you provide a link to the book. All data needed to decode aside from the image and ascii art should be present in the post and be constant across all encodings. \$\endgroup\$
    – Beefster
    Mar 29, 2021 at 18:43
  • \$\begingroup\$ This is amazing! You, dear sir/ma'am, get an upvote \$\endgroup\$ Apr 3, 2021 at 17:05
4
\$\begingroup\$

Determine Circles

\$\endgroup\$
12
  • \$\begingroup\$ Nice idea, but could you make it clearer what do you mean by cross? A test case would be good. \$\endgroup\$
    – math scat
    Apr 6, 2021 at 7:04
  • \$\begingroup\$ @math intersect or some concept like that. Can you give some better wording if you can understand what I mean? I can't find any word that suit line go over dot \$\endgroup\$
    – okie
    Apr 6, 2021 at 7:09
  • \$\begingroup\$ Maybe: 1, 2, 3 points will need 1 circle only to be sure that the points touch the circles boundary? Is that what you mean? \$\endgroup\$
    – math scat
    Apr 6, 2021 at 7:17
  • \$\begingroup\$ Some testcases are definitely needed, like five points on one circle and three points on another. Also, are the coordinates integers or real numbers? \$\endgroup\$
    – Bubbler
    Apr 6, 2021 at 8:15
  • \$\begingroup\$ @Bubbler Real number I think \$\endgroup\$
    – okie
    Apr 6, 2021 at 8:17
  • \$\begingroup\$ @okie Then you need to explicitly write it down, and add some testcases with non-integer coordinates. \$\endgroup\$
    – Bubbler
    Apr 6, 2021 at 8:21
  • \$\begingroup\$ In this problem, the answer does not change continuously with small perturbations of the input coordinates. Is it allowed to output the wrong answer due to floating point errors? For instance, if the input coordinates were (0,0),(0.3,0.3),(1,1) then the output should be 2. However, if the second point were instead (0.3,0.300...00001) then the answer should be 1. Given that floating point types are usually unable to tell these two cases apart, are we allowed to output either 1 or 2? \$\endgroup\$
    – Delfad0r
    Apr 6, 2021 at 16:01
  • \$\begingroup\$ @Delfad0r Thanks for your help. To solve such problem (float precision), I decided to add a limit to float so that precision are not extreme. \$\endgroup\$
    – okie
    Apr 7, 2021 at 0:15
  • 1
    \$\begingroup\$ Another possible approach (which I personally prefer, but the choice is entirely up to you) could be to only have integer coordinates as input, and then ask for an exact solution. If I am not mistaken, this problem should be solvable without resorting to square roots and similar, and therefore without any possibility of floating point errors. \$\endgroup\$
    – Delfad0r
    Apr 7, 2021 at 12:30
  • \$\begingroup\$ @Delfad0r But it's like a float *100 0.03*100 = 30 which just get every number bigger? \$\endgroup\$
    – okie
    Apr 7, 2021 at 23:38
  • \$\begingroup\$ @okie Yes, but the difference is that computations with integers are exact, while computations with floats are not. It shouldn't matter too much however, do whatever you prefer :) \$\endgroup\$
    – Delfad0r
    Apr 7, 2021 at 23:43
  • \$\begingroup\$ @Delfad0r I think I would take Integer, Thanks! \$\endgroup\$
    – okie
    Apr 8, 2021 at 0:04
4
\$\begingroup\$

posted lol

\$\endgroup\$
8
  • \$\begingroup\$ Another suggestion it can be kolmogorov complexity challe ge too, if someone downloads tags and compresses the text \$\endgroup\$
    – Wasif
    Apr 12, 2021 at 5:31
  • \$\begingroup\$ @Wasif it's better as an internet challenge because a new tag might be created after challenge posting making the list invalid. \$\endgroup\$
    – lyxal
    Apr 12, 2021 at 5:31
  • \$\begingroup\$ Should the list include the synonym tags, i.e. the tags that are listed as being on no questions in the tag listing? \$\endgroup\$ Apr 12, 2021 at 13:30
  • \$\begingroup\$ @cairdcoinheringaahing if it is listed on the tags page, then it needs to be included \$\endgroup\$
    – lyxal
    Apr 12, 2021 at 22:54
  • \$\begingroup\$ What is the 43 for in example program? \$\endgroup\$
    – tsh
    Apr 14, 2021 at 3:18
  • \$\begingroup\$ @tsh 43 is the number of occurrences of tag when you try and access a page of tags that doesn't exist \$\endgroup\$
    – lyxal
    Apr 14, 2021 at 3:19
  • \$\begingroup\$ Rule is still too wide, everyone can upload code to codegolf.stackexchange.com \$\endgroup\$
    – l4m2
    Apr 15, 2021 at 4:19
  • \$\begingroup\$ @l4m2 if people include all the tags in a post, then they will have to a) keep it constantly updated (which wouldn't be viewed favourably by the community) and b) withstand potential downvotes for loop holing on both the answer to this and the answer that has the tags \$\endgroup\$
    – lyxal
    Apr 15, 2021 at 4:45
4
\$\begingroup\$

Implement an Over function

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Can we take \$a\$ and \$b\$ as [a,b]? In effect, this would make the challenge a \$g\$ reduction of \$f\$ mapped over that input list. \$\endgroup\$
    – Adám
    Apr 19, 2021 at 21:12
  • 2
    \$\begingroup\$ @Adám I think it would be unfair (and potentially unobservable) to ban languages from taking it as [a,b], and doing so would likely just create solutions in the form pair input; map f; reduce g \$\endgroup\$ Apr 19, 2021 at 21:41
4
\$\begingroup\$

Death-onacci sequence (WIP)

The traditional Fibonacci sequence grows forever:

0 1 1 2 3 5 8 13 21 ... 1,346,269 ...

and is given by this formula:

f(n) = f(n-1) + f(n-2)

where the initial numbers in the sequence are 0, 1.

However, there's a set of as-yet unnamed sequences, where a previous number 'dies' and is removed from the total.

For instance the sequence for the 5th death-onacci (m = 5) is given by

f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) - f(n-5)

And the first m-1 numbers is 0, followed by a single 1 (so for m=5 the sequence start 0 0 0 0 1)

Test cases:

Here are some test cases:

n f(n), m=3 f(n), m=4 f(n), m=5
0 0 0 0
1 0 0 0
2 1 0 0
3 1 1 0
4 2 1 1
5 2 2 1
6 3 4 2
7 3 6 4
8 4 11 8
9 4 19 14
10 5 32 27
11 5 56 51
12 6 96 96
13 6 165 180
14 7 285 340
15 7 490 640
16 8 844 1205
17 8 1454 2269
18 9 2503 4274
19 9 4311 8048
20 10 7424 15156
21 10 12784 28542
22 11 22016 53751
23 11 37913 101223
24 12 65289 190624
25 12 112434 358984
26 13 193620 676040
27 13 333430 1273120
28 14 574195 2397545
29 14 988811 4515065
30 15 1702816 8502786
31 15 2932392 16012476

You must write a function or program that takes one number M, and prints out the first 31 M-Death-onacci numbers. M will be a whole number larger than 0 and less than 31. The output can be in any human readable format, and you can take input in any reasonable manner. (Command line arguments, function arguments, STDIN, etc.)

As usual, this is Code-golf, so standard loopholes apply and the shortest answer in bytes wins!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Very similar. \$\endgroup\$
    – Razetime
    Apr 24, 2021 at 9:57
  • \$\begingroup\$ @Razetime definitely, but hopefully different enough? \$\endgroup\$ Apr 24, 2021 at 10:02
  • \$\begingroup\$ Well, it's a WIP. You can go ahead and add more details which distinguish it. 'tis the sandbox, after all. \$\endgroup\$
    – Razetime
    Apr 24, 2021 at 10:04
  • \$\begingroup\$ @Razetime how's it looking now? \$\endgroup\$ Apr 24, 2021 at 10:23
  • 1
    \$\begingroup\$ looks better, and the tests are more comprehensive. I suggest posting in TNB for other people's feedback. \$\endgroup\$
    – Razetime
    Apr 24, 2021 at 11:11
4
\$\begingroup\$

Do I need a win streak?

\$\endgroup\$
10
  • 2
    \$\begingroup\$ taking P as a fraction seems fine, but it seems more convenient separately since we're just supposed to increment N and P till the desired ratio is achieved. What is the allowance for floating point errors on this question? \$\endgroup\$
    – Razetime
    Apr 24, 2021 at 10:07
  • \$\begingroup\$ an additional "Streak bonus" for every x games might be an interesting addition. \$\endgroup\$
    – Razetime
    Apr 24, 2021 at 10:08
  • 1
    \$\begingroup\$ @Razetime Oh did I say fraction, I meant a decimal value between 0 and 1, eg: 0.53 for 53%. There wont be more than two decimal places in the input so I doubt if any language will run into floating point errors at all. \$\endgroup\$ Apr 24, 2021 at 10:11
  • 1
    \$\begingroup\$ I updated the question to allow P as decimal. About the streak bonus, I think it might complicate things quite a bit so I am not going with that. \$\endgroup\$ Apr 24, 2021 at 10:21
  • \$\begingroup\$ You should clarify in the text if the inputs W, N can be taken separately or only as one number corresponding to W/N. And if so, please address Razetime's comment on floating point errors \$\endgroup\$
    – Luis Mendo
    Apr 24, 2021 at 15:17
  • \$\begingroup\$ @LuisMendo Yes, taking them separately is fine. I updated the post again, please check if it is clear now. \$\endgroup\$ Apr 24, 2021 at 15:47
  • \$\begingroup\$ I'd suggest also allowing languages to take P as a fraction. Other than that, this looks good to go \$\endgroup\$ Apr 24, 2021 at 16:09
  • 1
    \$\begingroup\$ I think they have to be taken separately. In the first example, if you take W/N as 0.2 you cannot compute the output, because you don't know if W=1, N=5, or W=2,N=10, or... \$\endgroup\$
    – Luis Mendo
    Apr 24, 2021 at 17:32
  • 1
    \$\begingroup\$ Oh yes, you're right about that. You'd have to consider both the values to calculate the answer. \$\endgroup\$ Apr 24, 2021 at 19:01
  • 1
    \$\begingroup\$ @LuisMendo But if it somehow benefits you to take it say as a string of the form "W/N" with the original values of W and N, then that's fine too. I think the rules clarify that point. \$\endgroup\$ Apr 24, 2021 at 19:16
4
\$\begingroup\$

Gelatin integer metagolf

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

Drawing the Stack Overflow logo

\$\endgroup\$
14
  • \$\begingroup\$ I don't think restricting the language is a good idea. Move languages promotes diversity among submissions. However, I'm still new to the site so I'm not really sure. \$\endgroup\$ Apr 30, 2021 at 4:32
  • \$\begingroup\$ Like Ender said, language-specific challenges are strongly discouraged - here, it doesn't add anything, so removing the restriction would improve the challenge by allowing a wider variety of approaches and solutions. \$\endgroup\$
    – hyper-neutrino Mod
    Apr 30, 2021 at 4:34
  • \$\begingroup\$ Also, seeing as to how this is a ascii-art challenge, you will need to either provide the exact text that needs to be outputted or a formal specification of what is considered valid output and what isn't - for example, could I just submit . and claim it's a very zoomed out logo? These will need to be clarified. Overall, I like the idea though. \$\endgroup\$
    – hyper-neutrino Mod
    Apr 30, 2021 at 4:35
  • \$\begingroup\$ I think if you require the output to be the exact example you gave it would make it much easier to determine which answers are valid. \$\endgroup\$ Apr 30, 2021 at 5:15
  • \$\begingroup\$ @RedwolfPrograms It's the best I got, but I'll make it official. \$\endgroup\$ Apr 30, 2021 at 5:20
  • \$\begingroup\$ This challenge looks pretty good now, so I've upvoted, although I'd still recommend waiting a day or two just in case anyone else has feedback on the formatting or finds something unclear. \$\endgroup\$ Apr 30, 2021 at 5:28
  • \$\begingroup\$ A tip for future challenges: Anyone (not just you) reading the challenge and an answer should be able to decide (without disagreement) if the answer is valid or not. "Resembles a logo" is very subjective in this sense, and phrases like "as close as" should be avoided too. \$\endgroup\$
    – Bubbler
    Apr 30, 2021 at 5:34
  • \$\begingroup\$ @Bubbler Is this better? \$\endgroup\$ Apr 30, 2021 at 6:10
  • \$\begingroup\$ Yeah, it's better. A question: would you allow printing trailing spaces at the end of each line, or printing a trailing newline at the end? (These are commonly allowed because they don't impact the ascii art shown and they're hard to avoid in multiple languages) \$\endgroup\$
    – Bubbler
    Apr 30, 2021 at 6:21
  • \$\begingroup\$ @Bubbler I added a list of questions that are asked in the comments. Can I add the same if I posted this on main? \$\endgroup\$ Apr 30, 2021 at 7:39
  • \$\begingroup\$ I'd recommend to edit the challenge text directly to include any clarifications. \$\endgroup\$
    – Bubbler
    Apr 30, 2021 at 7:45
  • \$\begingroup\$ @Bubbler It will do and I'm hoping that when this gets published, I gain enough reputation just to talk in chat. \$\endgroup\$ Apr 30, 2021 at 7:50
  • \$\begingroup\$ Tags-wise: [kolmogorov-complexity]. I'd suggest just removing the 2 paragraphs beneath the output, as they just make it more confusing. A simple "output this exact text, with an optional trailing newline. Lines may have optional trailing spaces. Shortest code wins" is enough (plus the output itself) \$\endgroup\$ Apr 30, 2021 at 17:35
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ May 1, 2021 at 13:46
4
\$\begingroup\$

Reveal by Halves (in need of a better name)

Inspired by this: http://nolandc.com/smalljs/mouse_reveal/ (source).

A valid answer:

  • Takes a number \$w\$ and (assumed non-negative) integer \$x\$.
  • Outputs an integer list with a length of \$2^w\$, initially filled with zeroes.
  • For each number \$n\$ from \$0\$ to \$w-1\$ (inclusive), divide the list into sub-lists of size \$2^n\$, then increment all of the values in the sub-list that contains the index \$x\$.

Examples

(with coordinates from left, 0 indexed, but your answer may have change these)

w=3, x=1
23110000

w=2, x=2
0021

w=3, x=5
00002311

w=4, x=4
1111432200000000

w=2, x=100
Do not need to handle (can do anything) because x is out of bounds

Meta questions

  • Are these tags fitting?
  • Would this be better in one dimension? (like \$3, 2\$ returns 11320000) Edit: I've changed it to one dimension but I can revert if it makes it less interesting.
  • Should \$w\$ or \$2^w\$ be the input?
  • Is this a duplicate?
\$\endgroup\$
1
  • 1
    \$\begingroup\$ My opinions on some meta questions. 1) I think one dimension would be better, the core of the challenge remains the same but the challenge itself becomes more "pure" which, in my opinion, is a good thing. 2) I'm a fan of flexible I/O, so if it were up to me I'd let people choose if they want \$w\$, \$2^w\$ or both as input. If you don't like this, both options are honestly fine. \$\endgroup\$
    – Delfad0r
    May 10, 2021 at 22:24
4
\$\begingroup\$

I'm Lazy*: Top-left align my text

posted

\$\endgroup\$
2
  • \$\begingroup\$ Definitely not too trivial for code golf \$\endgroup\$
    – qwr
    Jun 2, 2021 at 14:20
  • \$\begingroup\$ I think squash up could be its own challenge which has room for simplification. My thoughts being using a transposed grid of strings, which I guess can work for this challenge too \$\endgroup\$
    – qwr
    Jun 2, 2021 at 14:21
4
\$\begingroup\$

Demonstrate some advanced abstract algebra

\$\endgroup\$
10
  • \$\begingroup\$ I think we should be able to define the types and values of S, rather than necessarily using integers. In that case, - and + would not (necessarily) be actual arithmetic negation and addition, so maybe they would have to be renamed to use other symbols (or just use function syntax f(a,b)?) \$\endgroup\$
    – pxeger
    May 31, 2021 at 8:50
  • \$\begingroup\$ And do all 9 functions have to operate on the same set S? I think it could be more interesting if they didn't have to, but it might result in cheating/loopholes. Also, what does "uniquely exhibits" mean exactly? Demonstrates exactly one of the 9 properties? \$\endgroup\$
    – pxeger
    May 31, 2021 at 8:52
  • \$\begingroup\$ In fact, I think people will just submit "addition, addition, multiplication, subtraction" for the first 4 at least, and I suspect they will almost always be the shortest option in most languages so it might not be very interesting as it is \$\endgroup\$
    – pxeger
    May 31, 2021 at 9:04
  • \$\begingroup\$ Writing one program is hard enough. Writing 9 seems like a lot to ask. I think you could make a stripped down challenge using just commutativity and associativity. I barely known any abstract algebra. I think these varieties are called magmas? \$\endgroup\$
    – qwr
    Jun 2, 2021 at 14:54
  • \$\begingroup\$ Is this even possible with the surjectivity condition? You should provide an example of each program. \$\endgroup\$
    – qwr
    Jun 2, 2021 at 14:57
  • \$\begingroup\$ @qwr I don't have examples for each program, and even if I did, I wouldn't include them as that would just lead to people porting them into their own languages. Yes, I believe magma is the correct term for \$*\$ here. I'm not sure if this is possible, but I'd be surprised if it isn't. I've allowed for an answer to be a proof of impossibility however, on that off-chance. \$\endgroup\$ Jun 2, 2021 at 15:04
  • \$\begingroup\$ Well it's more than a magma since you added more two more operators right \$\endgroup\$
    – qwr
    Jun 2, 2021 at 15:18
  • \$\begingroup\$ @qwr No, I believe a magma is just a pair, the binary operator and the set its closed on, no matter the additional operators defined on that set \$\endgroup\$ Jun 2, 2021 at 15:31
  • \$\begingroup\$ This is a really cool problem. It is hard so I wouldn't be again having a separate "easy" version with just the main three: commutative/associative/distributive. Uniquely exhibiting those is already a nontrivial and neat challenge. I don't know if others would vote a dupe, but I'd def be in favor of having both. As is, I don't think the harder version will have a lot activity. But I do think an easier one would! \$\endgroup\$
    – AviFS
    Jun 13, 2021 at 1:18
  • \$\begingroup\$ @AviFS I do actually have an easier version Sandboxed, where I think they're clearly separate enough to not be dupes. \$\endgroup\$ Jun 13, 2021 at 1:42
4
\$\begingroup\$

Minimal distinct character quine

\$\endgroup\$
3
  • \$\begingroup\$ This seems well specificed \$\endgroup\$ Jun 16, 2021 at 10:04
  • \$\begingroup\$ distinct means different? \$\endgroup\$
    – math scat
    Jun 19, 2021 at 10:01
  • \$\begingroup\$ @math Yes (filler) \$\endgroup\$
    – emanresu A
    Jun 19, 2021 at 10:30
4
\$\begingroup\$

Full name quine

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice question but seems hard \$\endgroup\$
    – math scat
    Jun 25, 2021 at 18:11
  • 1
    \$\begingroup\$ i assume custom SBCS languages will have to output the full names of their characters when represented in unicode? Or should they output the name of the visual representation? \$\endgroup\$
    – Razetime
    Jun 28, 2021 at 6:20
  • \$\begingroup\$ Full names represented in unicode. \$\endgroup\$
    – emanresu A
    Jun 28, 2021 at 8:29
4
\$\begingroup\$

r my Vyxal

\$\endgroup\$
6
  • \$\begingroup\$ Needs more test-cases. Also, in the explanation you use spaces as though they're ignored, but that isn't mentioned in the description of the task itself. I'd suggest just saying that "all other characters" will be limited to ASCII letters only, for example?. \$\endgroup\$
    – pxeger
    Jul 4, 2021 at 7:47
  • \$\begingroup\$ @pxeger In Vyxal, spaces are NOPs used to seperate stuff. In the subset I'm using, spaces are a function like everything else. I'll make that clearer, and add more testcases. \$\endgroup\$
    – emanresu A
    Jul 4, 2021 at 8:15
  • \$\begingroup\$ But I'm suggesting limiting the definition of what are functions to ASCII letters only to provide more golfing opportunities without having to handle edge cases that might occur because of spaces \$\endgroup\$
    – pxeger
    Jul 4, 2021 at 8:54
  • \$\begingroup\$ @pxeger Ok. (filler) \$\endgroup\$
    – emanresu A
    Jul 4, 2021 at 8:55
  • \$\begingroup\$ It says that we can assume there will always be two values to pop, but one of the testcases is simply “1”. Is that something that we will have to account for? \$\endgroup\$ Jul 4, 2021 at 15:09
  • \$\begingroup\$ @AaronMiller What I meant is, wherever there's a function, there will be two. I'll add that. \$\endgroup\$
    – emanresu A
    Jul 4, 2021 at 19:58
4
\$\begingroup\$

Fastest untyped lambda calculus evaluator

Challenge

What it says on the tin. Mainly because googling "fastest untyped lambda calculus" gives almost zero meaningful results.

Each submission is expected to take a lambda term from STDIN and print its normal form to STDOUT. The lambda term is represented using de Bruijn indexes, and we will use prefix notation for this challenge. Since a de Bruijn index may have multiple digits, each token will be separated by a single space. The input will have no surrounding whitespace, but you may output any amount of whitespace before and after the formatted lambda term.

LambdaChar = "\"             // single backslash
DeBruijnIndex = [1-9][0-9]*  // a positive integer
ApplyChar = "@"
Term = DeBruijnIndex | LambdaChar " " Term | ApplyChar " " Term " " Term

For example, \ \ @ 1 @ 2 1 represents lambda x. lambda y. y (x y).

The evaluation semantics to implement is normal order beta-reduction (no eta-reduction).

The test cases will be hand-crafted so that it takes significantly more time to evaluate the expression than to parse the input and format the output. Also, they will involve various kinds of Church- and Scott-encoded terms, so optimizing for any specifically encoded data (hopefully) has less effect than optimizing for general improvement. It is guaranteed that the test cases have a normal form and do not contain free variables.

Good starting points include this PEPM '17 paper and my Haskell implementation which was modified from the paper's algorithm to actually return the normal form. Other notable keywords: graph reduction, supercombinators, G-machine, TIGRE, STG (spineless tagless G-machine). Note that, if your submission has separate compilation and execution phases, both phases count towards the total execution time (which may negatively impact your score).

The submissions will be scored within WSL (Ubuntu 20.04) on my Windows 10 PC, which has Intel Core i7-6700 CPU (3.40GHz) and 8GB of RAM. The score is the sum of the timings measured for all the test cases. Lowest score wins.


Meta

  • Todo: write example and actual test cases.
  • Should I include a description about how the "normal order beta reduction" works for de Bruijn indexes?
\$\endgroup\$
2
  • \$\begingroup\$ are you planning to actually test with >9 levels of lambda nesting? \$\endgroup\$
    – ngn
    May 26, 2021 at 2:48
  • \$\begingroup\$ @ngn Depends on what I come up with. \$\endgroup\$
    – Bubbler
    May 26, 2021 at 3:04
4
\$\begingroup\$

Extremely small data compressor

In 2014 Jarek Duda at Purdue University wrote a paper containing several ideas for encoding computer data, entitled “Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding". The paper is available at Cornell University Library’s ArXiv project: https://arxiv.org/abs/1311.2540

One of the many fascinating things about this paper is that it begins by describing an extremely simple data compression algorithm, using the concept of the "Uniform asymmetric binary systems (uABS)". In fact, it is so simple, that you can implement it in only a few lines of code.

Basically it attempts to interpret a sequence of input symbols as a single Integer, and as each symbol comes in the Integer can be appended with new information. The trick is that the Integer is represented not using a place-value binary number system, but an alternative system. This representation is designed so that sequences of symbols which occur with higher probability will be represented by a smaller amount of space within the Integer's encoding.

Challenge

You will implement the simple uABS compression algorithm, so that given a sequence of 0s and 1s, your program will compress them into a (usually) smaller sequence of 0s and 1s.

Pseudocode

The algorithm in psuedocode is as follows:

  • Begin with an Integer X, and set it to 1. This will be the main Integer that we append during the algorithm.
  • The input data is a sequence of symbols, each 0 or 1, called Input
  • Find the probability P that any given symbol in Input is 1, (the number of 1s divided by the total number of symbols)
  • For each symbol S in Input, set X to the output of the function Encode(x,s,p)
  • After processing all the input symbols, output the final integer X. -- This encoded integer will hopefully have less bits than the input

The Encode function itself can be described as follows:

$$ Encode(x,s,p)= \left\{ \begin{array}{11} \mbox{if } s = 0 & \big\lceil\frac{x+1}{1-p}\big\rceil-1 \\ \mbox{if } s = 1 & \big\lfloor\frac{x}{p}\big\rfloor \end{array} \right. $$

Where

$$ \begin{array}{11} s \text{ is a symbol, either 0 or 1} \\ x \text{ is the Integer} \\ p \text{ is the probability that any symbol in the Input data is 1 } \\ \lceil \rceil \text{ is the mathematical ceiling function } \\ \lfloor \rfloor \text{ is the mathematical floor function } \end{array} $$

Notes

  • The input is a sequence of symbols, each symbol being 0 or 1, in any method that is available in your chosen language. Examples include a sequence of ascii characters '0' '1', an array of integers, etc.

  • The output will be a sequence of symbols in the same format as the input sequence. The output sequence represents the compressed version of the input data.

  • Empty input data has undefined behavior.

  • Input data containing only 0s has undefined behavior.

  • Sometimes the encoded Integer might have more bits than the input, not less. This typically happens when the number of 1s and 0s is relatively even. Data with an unbalanced number of 0s and 1s results in better compression.

  • You may assume that the size of Integer will be your language's largest integer type. The test cases outside this range can be ignored for your language.

  • Note that if you are trying to test this by 'decoding' or 'decompressing' the compressed data, and compare it to the original, one would have to store additional information, such as the length of input and probability P, but for simplicity this has been left out of the challenge.

Example Input and Output

Short examples:

Input             Output    
10                101
10010100000       1011101001
1111              1
11111111111       1
10000000          11011
10011111010101    10110000100101    

Longer examples:

Input  11111110110111110111111111011111
Output 11111000011110110

Input  000000000001000000010000000000001100000000001
Output 1110000101100111000011111

Input  000000000001000000010000000000001100000000001000000000000000000000000000000000000000000000000000000000000000001
Output 1010100110111110010111011110110101010

Scoring

  • The program with the fewest number of characters wins.
\$\endgroup\$
9
  • \$\begingroup\$ 1. IMO the pseudocode could be made clearer by firstly explaining what "machine integer" means (does it mean "unbounded integer" aka "big integer"?) and secondly golfing it a bit: using a "foreach" loop notation for S and eliminating the variable X'. 2. I think it would be helpful to be explicit about how p should be derived from the input. I presume that it means looping over the input twice, once to count and once to compress. 3. IMO restricting the input format to strings of ASCII 0 and 1 detracts from the core challenge. Why not allow arrays/lists of integers? \$\endgroup\$ Jul 7, 2018 at 12:13
  • \$\begingroup\$ Thanks, i have revised. \$\endgroup\$
    – don bright
    Jul 7, 2018 at 14:08
  • \$\begingroup\$ I really like this one. Something quasi-practical, and yet simple and small enough to be fun. Just to be clear, the output is the binary representation fo the integer X, without any leading zeros, correct? \$\endgroup\$
    – Sundar R
    Jul 8, 2018 at 19:02
  • \$\begingroup\$ Also, you mention "input size of at least 128 symbols", but it might be more important to specify output size limit, since many languages have hard bounds on maximum integer size. Since output size varies for the same input length, it might have to be something like "you may assume that the number of symbols in the output is less than or equal to the number of bits in your language's largest integer type". (The last test case would then be optional in languages that can handle only up to 32 bit integers). \$\endgroup\$
    – Sundar R
    Jul 8, 2018 at 19:12
  • \$\begingroup\$ yes the output is the binary representation of the final integer X, i believe the leading zeros is correct. do you think 32 bit is the good limit or 64, since modern machines tend to be 64 bit? thanks \$\endgroup\$
    – don bright
    Jul 8, 2018 at 20:05
  • \$\begingroup\$ 32 is probably a reasonable limit, one that most languages can handle without need for external libraries. \$\endgroup\$
    – Sundar R
    Jul 14, 2018 at 14:22
  • \$\begingroup\$ @sunar thanks, i have updated. \$\endgroup\$
    – don bright
    Dec 29, 2018 at 14:21
  • \$\begingroup\$ I assume the intent is for P to be calculated as # of '1' in the input / # of symbols in the input? That seems like it would match the definition given, but it would be helpful if it's described explicitly. \$\endgroup\$ Jan 3, 2019 at 22:24
  • \$\begingroup\$ Done, thanks.... \$\endgroup\$
    – don bright
    Jan 3, 2019 at 23:32
4
\$\begingroup\$

Converting Pinyin to Zhuyin or vice versa

Challenge

Pinyin and Zhuyin are systems that are used to help people pronounce characters in Mandarin Chinese. Write a function/program that converts Pinyin to Zhuyin or vice versa (clarify which one you are doing) according to the tables below. You are not required to deal with tones or incorrect inputs (including edge cases such as ḿ(呣), ǹg(嗯), and ê̄(诶/誒)).

Pinyin to Zhuyin

Pinyin Zhuyin
b
p
m
f
d
t
n (at the beginning)
l
g (at the beginning)
k
h (at the beginning)
j
q
x
zh (except in zhi)
zhi
ch (except in chi)
chi
sh (except in shi)
shi
r (at the beginning)
ri
z (except in zh, zi)
zi
c (except in ch, ci)
ci
s (except in sh, si)
si
a (at the end)
o (except in ao, ou, ong)
e (except in ei, en, eng, er, ie, ue, üe, ye)
e (only in ie, ue, üe, ye)
i (except in ai, ei, ui, iu, iong, yi, zhi, chi, shi, ri, zi, ci, si)
y (except in yong, yi)
yi
u (except in ou, iu, wu, ue and except after j, q, x, y)
w (except in wu)
wu
o (only in ong except in iong, yong)
u (right after j, q, x)
ü
yu
io
yo (only in yong)
ai
ei
i (only in ui)
ao
ou
u (only in iu)
an (except in ang)
ang
en (except in eng)
n (only in in, un except in ing)
eng
ng (only in ing, ong)
er

Zhuyin to Pinyin

Zhuyin Pinyin
b
p
m
f
d
t
n
l
g
k
h
j
q
x
ㄓ (by itself) zhi
ㄓ (not by itself) zh
ㄔ (by itself) chi
ㄔ (not by itself) ch
ㄕ (by itself) shi
ㄕ (not by itself) sh
ㄖ (by itself) ri
ㄖ (not by itself) r
ㄗ (by itself) zi
ㄗ (not by itself) z
ㄘ (by itself) ci
ㄘ (not by itself) c
ㄙ (by itself) si
ㄙ (not by itself) s
a
o
e
e
ㄧ (at the beginning, not by itself, and not before ㄣ, ㄥ) y
ㄧ (after ㄐ, ㄑ, ㄒ) i
ㄧ (by itself or before ㄣ, ㄥ and at the beginning) yi
ㄨ (not at the beginning) u
ㄨ (at the beginning except by itself) w
ㄨ (by itself) wu
ㄨ (before ㄥ and not at the beginning) o
ㄩ (after ㄐ, ㄑ, ㄒ) u
ㄩ (after ㄋ, ㄌ) ü
ㄩ (by itself or before ㄝ, ㄢ, ㄣ and at the beginning) yu
ㄩ (not at the beginning and before ㄥ) io
ㄩ (at the beginning and before ㄥ) yo
ai
ㄟ (not after ㄨ unless ㄨ is at the beginning) ei
ㄟ (after ㄨ unless ㄨ is at the beginning) i
ao
ㄡ (not after ㄧ unless ㄧ is at the beginning) ou
ㄡ (after ㄧ unless ㄧ is at the beginning) u
an
ang
ㄣ (not after ㄧ, ㄨ, ㄩ unless ㄨ is at the beginning) en
ㄣ (after ㄧ, ㄨ, ㄩ unless ㄨ is at the beginning) n
ㄥ (not after ㄧ, ㄨ, ㄩ unless ㄨ is at the beginning) eng
ㄥ (after ㄧ, ㄨ, ㄩ unless ㄨ is at the beginning) ng
er

This is code-golf, so the answer with the least bytes wins.

Test Cases

Pinyin Zhuyin
chuang ㄔㄨㄤ
xue ㄒㄩㄝ
diu ㄉㄧㄡ
juan ㄐㄩㄢ
ri
song ㄙㄨㄥ
ㄌㄩ
qiong ㄑㄩㄥ
zhen ㄓㄣ
huo ㄏㄨㄛ
ying ㄧㄥ

Additional test cases and information

\$\endgroup\$
7
  • \$\begingroup\$ Am I required to support single characters or a word / sentence? Also, there are some edge cases as I know, for example, ḿ(呣), ǹg(嗯), ê̄(诶/誒). Would these be excluded from testcases? May I assume no erhua (儿化/兒化) would be applied? \$\endgroup\$
    – tsh
    Oct 12, 2021 at 6:44
  • \$\begingroup\$ There are far more rules than testcases. I would suggest to add more testcases as many rules are not ever touched by any testcases here. \$\endgroup\$
    – tsh
    Oct 12, 2021 at 6:54
  • \$\begingroup\$ @tsh Single characters. The edge cases would not be required to check for as inputs. No erhua. I will try to add some more testcases to cover the other rules. \$\endgroup\$
    – Yousername
    Oct 12, 2021 at 11:19
  • \$\begingroup\$ Suggest a whole list, it's likely just 300+ possible inputs \$\endgroup\$
    – l4m2
    Oct 12, 2021 at 18:13
  • 1
    \$\begingroup\$ The number of rules makes this an intimidating task to write and golf. Consider limited to a simpler subset of rules or situations. \$\endgroup\$
    – xnor
    Oct 13, 2021 at 7:12
  • \$\begingroup\$ @xnor It's not actually as many rules as it looks like. A simple regex can be used for most of them. \$\endgroup\$
    – Yousername
    Oct 13, 2021 at 21:41
  • \$\begingroup\$ This is probably a lot harder to reason about for people not already familiar with mandarin and pinyin. \$\endgroup\$
    – qwr
    Jul 10, 2022 at 0:40
4
\$\begingroup\$

Play RPS with 3 bits of memory

This is a rough draft for now, the specifics, presentation and title will probably be adjusted

In this game you will be building bots to play rock paper scissors against each other. Of course rock paper scissors is not a very interesting game, just pick one of the three randomly. Can't get better than that?

The first thing here is that, we will play a slight variation on the game which introduces a small amount of strategy.

But more importantly in this version we will be designing very simple bots. Your bot will not be able to pick things randomly, nor will it be able to simulate complex strategies, because your bots will have 3 bits of working memory.

The game

Before we get into exactly how the bots will be made and what exactly it means to have only 3 bits of memory lets cover the game.

For each pair of bots we will play 48 rounds of RPS. In each round both bots will select a choice of Rock, Paper or Scissors. Rock beats scissors, paper beats rock and Scissors beats paper, if the two chose the same move they tie.

When you win you will receive points based on your play. If you win with scissors you get 1 point, if you win with paper you get 3 points, and if you win with rock you get 6 points. If you tie or lose you get 0 points.

Each bot will play every other bot and the bots will be scored on the number of points gained in total.

The bots

Your bot will have 3 bits of working memory, that means at any given time it will have stored a number between 0 and 7. To decide what to play it will know two things

  1. What it has in memory
  2. The last move it's opponent made

Given those it should spit out

  1. What move it wants to make
  2. 3-bits to write into memory

This is so simple you don't actually need to write "code" to represent your bot. Your bot is really just a \$8\times 3\$ lookup table, plus a single move which it will make as it's first move. (We can assume that the starting memory is 0 without loss of generality)

And in fact you will submit your bots in this format as it makes it easy to verify your bot works and doesn't cheat.


Sandbox

I like this challenge because it is

  1. Completely deterministic who wins, to the point where you can, for small bot pool work out with pen and paper the scores.
  2. It is basically language agnostic. No need to bother with JS.
  3. There's basically no way to cheat. It's going to be really hard to exploit a vulnerability in the handler when you can't run arbitrary code.

I am a little concerned though that there might not be a whole lot to do? I'm not sure how much better one bot really can be than others. Obviously you can always take 1 bot and design a bot which plays perfectly against it. But I'm not totally sure how much a carefully arranged bot is going to do better than ones that are just a pile of random connections.

Turning the memory size up could improve this but the larger you make it the more complex each bot gets, and I think the fun is really in being able to hand tune your bot.

However I don't know what I can do to find out other than just post this.

\$\endgroup\$
6
  • \$\begingroup\$ Seems bruteforceable \$\endgroup\$
    – pxeger
    Oct 17, 2021 at 18:40
  • 4
    \$\begingroup\$ This is a unique challenge, and I think you could post it. If it doesn't work out, then we'll all know not to do it again (or an improved version could be posted later). If it does work, CGCC'll have a new kind of challenge, which would be great. \$\endgroup\$
    – user
    Oct 17, 2021 at 18:57
  • \$\begingroup\$ @pxeger There are 1333735776850284124449081472843776 machines possible. Brute forcing that would probably mean playing every machine against every other machine. It may be solvable, but I don't think it is feasible to brute force it. \$\endgroup\$
    – Wheat Wizard Mod
    Oct 17, 2021 at 21:15
  • 1
    \$\begingroup\$ I'd prefer to have rigid I/O (fixed I/O method and format) for KotH purposes. Or you could just say "write down the 8x3+1 possible outputs in a specific format". The barrier to post some bot looks pretty low, so I'd expect a large number of answers in the worst(?) case which would require some kind of automated controller. \$\endgroup\$
    – Bubbler
    Oct 18, 2021 at 1:13
  • \$\begingroup\$ @WheatWitch ah, I misread the challenge \$\endgroup\$
    – pxeger
    Oct 18, 2021 at 6:59
  • 1
    \$\begingroup\$ @bubbler oh I absolutely will write a controller once the rules are nailed down a bit. Just because you can score this by hand does not mean it would not be very tedious \$\endgroup\$
    – Wheat Wizard Mod
    Oct 18, 2021 at 7:40
4
\$\begingroup\$

Remove submatrices

\$\endgroup\$
4
\$\begingroup\$

Solve the halting problem for ^/a*b*/b*a*/[ab]*$ in ///

///, a.k.a. Slashes is an esoteric programming language with simple two operations. One is to output its source to remove from it. The other is to substitute itself. The language is proven to be Turing-complete, so some programs such as /ab/bbaa/aab won't halt while some such as /ab/bbaa/ab will.

At first I questioned if halting problem for ^/[ab]*/[ab]*/[ab]*$ is solvable, but I learned unlikely.

So I am simplying to ^/a*b*/b*a*/[ab]*$.

Problem

Given a slashes program that matches ^/a*b*/b*a*/[ab]*$ in POSIX BRE (i.e. below), determine whether the program halts or not.

Format of program, if you are not familiar with POSIX BRE

program = "/" first "/" second "/" third
first = "" | first "a" | first first.b
first.b = "" | first.b "b"
second = "" | second "b" | second second.a
second.a = "" | second.a "a"
third = "" | third "a" | third "b"

Constrains

In this problem every program's length is up to 153.

Detailed rules

  • Can be either a full program or a function.
  • Standard i/o apply.
    • Examples of input format
      • a string of program
      • three strings p,q,r when the program is /p/q/r
      • integers p,q,r,s and a string t when the program is /a\{p\}b\{q\}/b\{r\}a\{s\}/t
      • entirely as an integer (think of it by yourself)
    • Examples of output format
  • Standard loopholes apply.
  • This is ; shortest code wins.

Examples

Testcase generator 1

My noncompetive solution

///: no
/a//: yes
/ab/bba/aab: yes
/ab/bba/aaab: yes
/ab/bba/aabb: no

Meta

  • Were similar things ever done before?
  • I am not even sure if this problem is solvable.
  • Just thought there are answers if I clarify maximum length of input.
  • Should I change the problem's genre to ? Would making a maximum length of the program be boring?
\$\endgroup\$
2
  • 1
    \$\begingroup\$ /// is turing-complete, so this is not possible \$\endgroup\$
    – pxeger
    Apr 25, 2021 at 12:33
  • \$\begingroup\$ Should we simplify it more? \$\endgroup\$
    – user100411
    Apr 25, 2021 at 20:23
4
\$\begingroup\$

Implement a BrainFlump interpreter

BrainFlump is the latest alternate memory model brainfuck-esque turing tarpit.

It operates on a memory model we call a "Dump", which is simply an un-ordered collection of integers, with a pointer indicating the current item to operate on. As it is "unordered", when moving to the next item, one is simply chosen at random (chosen uniformly between the items that are not the currently selected item) and the operation pointer is moved to that item.

Commands

+   #Increment the item at the pointer
-   #Decrement the item at the pointer
:   #Add a 0 to the dump, and move the pointer to it
;   #Move the pointer to a random item that is not the pointer's current position
(   #Skip to the matching ) if the item at the pointer is 0
)   #Skip to the matching ( if the item at the pointer is not 0
,   #Read a single character from STDIN and push its ascii value to the dump
    #This also moves the pointer to the new item
.   #Print the current item at the pointer modulo 127 as an ASCII character

Other notes

  • When the ; command is used if the dump contains only 1 item, a new 0 is pushed to the dump, and the pointer is moved to it
  • The . command does not pop the item from the dump
  • When the , command is used if STDIN has been exhausted, a new 0 is pushed to the dump, and the pointer is moved to it
  • Any item in the dump who's value is 0 is not considered to exist, unless it is the item at the pointer, therefore to "pop" an item from the dump, you simply set its value to 0
  • Nested loops are supported
  • The random number generator used for the interpreter does not have to be cryptographically secure, but must chose with uniformity.
  • BrainFlump does not support floating point numbers or negative integers. Attempting to decrement a number below 0 has no effect.
  • The maximum value of an item in the dump is 255

Examples/Testcases

brainf**k emulation

++++++(;++++++++;-);.

This should output 0

Explanation

++++++        #Increment the first item to 6
(             #While the item under the pointer is not 0
    ;         #Move to another item in the dump
              #    Note the first time this loop runs,
              #    this will insert a new item
    ++++++++  #Increment the new item by 8
    ;         #Switch to another item in the dump
              #    Note there are only 2 items currently,
              #    So this will switch to the only other
              #    item, the one we initially incremented to 6
    -         #Decrement the item
)             #Repeat the loop if the item is not 0
;             #Switch to the other item
              #    Note this switches the pointer back to
              #    The item we have been incrementing by
              #    8 each loop
.             #Output as ASCII character

This is effectively a 6*8 operation, followed by an output, and is nearly identical to brainf**k's ++++++[>++++++++<-]>. program, which also outputs 0.

Note, however, that brainf**k-esque dump manipulation is only deterministically possible if there are never more than 2 items in the dump.

Random output

+:++:+++:++++:+++++:;.

This will actually always output an unprintable character, however which character is output will be random each time, selected from: SOH, STX, EST, EOT, ENQ, ie ASCII characters 1-5. In a correctly implemented interpreter, this output should be uniformly random between the 5 possibilities.

Explanation

+      #Increment first item to 1
:      #Add new item and move to it
++     #Increment new item to 2
:      #Add new item and move to it
+++    #Increment new item to 3
:      #Add new item and move to it
++++   #Increment new item to 4
:      #Add new item and move to it
+++++  #Increment new item to 5
:      #Add new item and move to it
       #    Note this last item is added because ; will
       #    always switch to an item that is *not* the
       #    currently selected item
;      #Switch randomly to an item in the dump
.      #Output as ASCII character

To give a little more info on this, by the time the ; command is reached, the dump should look like this:

1 2 3 4 5 0
          ^

As ; always switches to a different item, the result will be the pointer at one of the non-zero items.

cat

,(.,)

Nice and simple, and identical to brainf**k's cat program.

For scoring purposes, you should use this gist as input when testing.

When will it end?

++++(,:+++++;++(;++++++;--):++++;---)

This program doesn't output anything, but runs for a non-deterministic amount of time.

Explanation

++++             #Increment first item to 4
(                #Start loop
    ,            #Read char from STDIN to new item in dump
    :+++++       #Push 5 to dump
    ;++          #Switch to random item in dump and add 2
    (            #Start loop
        ;++++++  #Switch to random item in dump and add 6
        ;--      #Switch to random item in dump and subtract 2
    )            #End loop
    :++++        #Push 4 to dump
    ;---         #Switch to random item in dump and subtract 3
)

This one is a little tricky, as ; will never switch to a 0 (Remember items with a value of 0 are considered to not exist)

The inner loop will only exit if ;-- switches to a number <= 2

The outer loop will only exit if ;--- switches to a number <= 3

Due to the inherent randomness of the language, this should always terminate... eventually.

For scoring purposes, you should use the exact string Hello, World! as input when testing.

Scoring

This is meaning the interpreter that on average runs the fastest, wins!

Scoring will be determined by running each of the 4 test-cases above 100 times, and determining an average runtime (due to the inherent randomness of the language, a high number of runs should be made to minimise anomalous results).

Then once you have an average for each testcase, sum the 4 times, and that is your final score. Lower is better

\$\endgroup\$
1
  • \$\begingroup\$ I feel like a lot of time will come from the RNG, so better solutions might sacrifice some "randomness" for speed - You might want to standardise "randomness" \$\endgroup\$
    – emanresu A
    Dec 22, 2021 at 3:42
4
\$\begingroup\$

Converge to a number

\$\endgroup\$
4
\$\begingroup\$

Schrödinger's cat program

\$\endgroup\$
1
  • \$\begingroup\$ This is probably good to post now, and it looks like a good challenge! \$\endgroup\$
    – emanresu A
    Dec 27, 2021 at 5:59
4
\$\begingroup\$

Incrementally Increment Identical Integers

\$\endgroup\$
2
  • \$\begingroup\$ Total rewording suggestion for everything up until before "To demonstrate": Given a non-empty non-descending list of any integers, increment each number by how many identical elements occur to its left. \$\endgroup\$
    – Adám
    Jan 1, 2022 at 18:16
  • 2
    \$\begingroup\$ @Adám For what it's worth, I find that less understandable than the current description. It's probably a difference of APL mindset vs. Python mindset. \$\endgroup\$
    – DLosc
    Jan 1, 2022 at 18:18
4
\$\begingroup\$

Egyptian fraction representations of 1

\$\endgroup\$
4
\$\begingroup\$

Remove odd indices and double the even indices

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The test cases are now consistent with the example explanation, but not with the "remove odd, double even" description. You could fix this by either changing this to "remove even, double odd", or switching to 0-indexing \$\endgroup\$
    – pxeger
    Jan 17, 2022 at 12:40
4
\$\begingroup\$
\$\endgroup\$
3
  • \$\begingroup\$ It'd be nice to link the ITTM paper. Also, showing an example ITTM and explaining its halting time (like your ⍵×⍵ 2-state ITTM) would be helpful. \$\endgroup\$
    – user41805
    May 7, 2021 at 12:39
  • \$\begingroup\$ @user41805 I'm currently working on an explanation for my 2-state ITTM champion. But the animations are a bit time consuming. I meant to link some ITTM papers, so I will add those links when I finish the edit I am working on. Thanks. \$\endgroup\$
    – Wheat Wizard Mod
    May 7, 2021 at 12:42
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/36747/45613 and codegolf.stackexchange.com/questions/18028/… (This doesn't seem to be a duplicate) \$\endgroup\$
    – Beefster
    May 18, 2021 at 16:25
4
\$\begingroup\$

Score a Scrabble Play

\$\endgroup\$
5
  • 2
    \$\begingroup\$ I think removing the letter points mapping from the challenge as you suggest is a good idea. Otherwise a lot of the byte count will be taken up just in storing the map, with less of the answer being the interesting part, which is the scoring algorithm. Honestly it might even be worth assuming all letters score 1, because the interesting computational problem is really just detecting what the words formed in the grid are. \$\endgroup\$
    – pxeger
    Jan 24, 2022 at 20:53
  • 1
    \$\begingroup\$ @pxeger I think I would like to keep the specific point values, so that the challenge still involves the words themselves somehow. Otherwise it would suffice just to find the distances between relevant tiles and certain empty squares as well as losing some (important, in my opinion) flavor. \$\endgroup\$ Jan 24, 2022 at 21:01
  • \$\begingroup\$ That's a good point; I hadn't considered that the letters themselves would no longer matter in that case. I'd still recommend going for the version with points mapping as input. \$\endgroup\$
    – pxeger
    Jan 24, 2022 at 21:03
  • \$\begingroup\$ Where do we get the word dictionary? \$\endgroup\$
    – Ginger
    Jan 24, 2022 at 21:08
  • \$\begingroup\$ @GingerIndustries There is no need for a word dictionary. As I wrote in my post, answers do not need to consider the legality of the play. \$\endgroup\$ Jan 24, 2022 at 21:11
4
\$\begingroup\$

Find the index of the matching parentheses for each character

\$\endgroup\$
1
  • \$\begingroup\$ please check if i have explained properly as some may not understand \$\endgroup\$
    – DialFrost
    Feb 2, 2022 at 9:20
1
10 11
12
13 14
155

You must log in to answer this question.

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