557
\$\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".

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3992 Answers 3992

1
9 10
11
12 13
134
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\$

Complete the landscape

Carcassonne is a tile-based game, where the objective is to construct Roads, Cities and Monasteries, in order to score points. The game works by players taking turns to draw and place tiles to construct a landscape, then claiming roads, cities and monasteries. An example landscape is:

Example Landscape

There are \$19\$ distinct tiles (ignoring rotations), each of which contains at least one feature (Road, City or Monastery):

All tiles

Also, notice that the landscape must be consistent. This means that roads must connect to other roads, city edges must connect to other city edges and fields must connect to fields. Therefore, these tiles are inconsistent:

Inconsistent tiles

To avoid this challenge being about image processing, we can translate each tile into a list containing \$5\$ values, according to this legend:

[North edge, East edge, South edge, West Edge, # of cities]

0: Field
1: Road
2: City

For instance, this tile can be described as [2, 0, 1, 1, 1]. Using this legend, we can describe each tile uniquely, and it's rotations are rotations of the first four elements. The entire grid can be described as a rectangular matrix, with a \$20^\text{th}\$ distinct value for an empty square. Translating the first landscape into this format, we get:

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

using [] to represent an empty square. The complete list of tiles (ignoring rotations) in the same grid as the second image is

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

Your task is to take in a rectangular matrix where every element save one is one of the 19 tiles given above or one of their rotations. Tiles can appear more than once, and not every tile will appear in every input. This landscape will be consistent, as defined above. You should take in this input and output the tile that could fill the empty space in the array, keeping the landscape consistent, as defined above.

As the number of cities on a tile is redundant for this task, you may choose instead to only work with 17 tiles (as 2 tiles are duplicated when ignoring cities) and take input as lists in the form [N, E, S, W] instead.

If there are multiple tiles that would work, you may output either all of them or just one. If no such tile exists, you may produce any output/result that could not be construed as a tile (i.e. it's not in the 19 tiles specified above, nor in any of their rotations). The representation of the "empty space" in the input may be your choice, so long as its consistent, and (although I'm not sure why you would) it isn't one of the 19 tiles above or their rotations, and there will only ever be a single empty space.

This is , so the shortest code in bytes wins.

Test cases

test cases to be added


Meta

  • Is this clear enough?
    • More specifically, is the definition of a "consistent landscape" objective and understandable?
  • This is a somewhat related question, but I believe there are enough differences between the two for them to not be duplicates. Thoughts?
  • Tags are , , , . Any suggestions?
  • Any further feedback?
\$\endgroup\$
10
  • \$\begingroup\$ @Beefster Aside from involving tiling, I'm not quire sure how that challenge is related, let alone a possible duplicate \$\endgroup\$ Sep 28, 2020 at 22:00
  • \$\begingroup\$ Filling Carcassonne tiles in a grid can be thought of as a specific case of wang tiles with a different set of tiles, but upon closer inspection, seeing as your challenge is to complete the landscape, rather than fill a grid from nothing, this is actually a pretty different challenge. \$\endgroup\$
    – Beefster
    Sep 28, 2020 at 22:03
  • \$\begingroup\$ Related \$\endgroup\$
    – Beefster
    Sep 28, 2020 at 22:04
  • \$\begingroup\$ Does the 5th field, the # of citys, add anything? Makes it more cumbersome to store/rotate the tiles. Though it's understandable if you want to keep true to Carcassonne. \$\endgroup\$
    – xash
    Mar 17, 2021 at 19:21
  • \$\begingroup\$ @xash Yes, without the number of cities, some tiles (e.g. [2,2,0,0,1] and [2,2,0,0,2]) have the same representation as an array \$\endgroup\$ Mar 17, 2021 at 19:22
  • \$\begingroup\$ @xash As "there will only ever be a single empty space.", "the empty space" makes more sense, as it refers to the only empty space in the input \$\endgroup\$ Mar 17, 2021 at 19:26
  • \$\begingroup\$ Ah! I thought "The "empty space" in the input may be your choice" refers to which empty space to choose to fill, not the representation. Sorry, haven't slept well, makes perfect sense. :-) \$\endgroup\$
    – xash
    Mar 17, 2021 at 19:29
  • \$\begingroup\$ While I agree that to match Carcassonne, the number of cities field is useful for disambiguating two different tiles, it would never affect whether a tile fits into the space or not, so for this challenge it seems redundant. \$\endgroup\$ Mar 20, 2021 at 7:42
  • \$\begingroup\$ Will the 19 possible tiles be supplied as an input or do they need to be encoded into the answer? \$\endgroup\$ Mar 20, 2021 at 7:46
  • \$\begingroup\$ @NickKennedy Good point, I didn't realise that. I've added in a note about the redundancy of the city count. No, the tiles will not be provided as input, so the answer will need to implement some way of encoding them \$\endgroup\$ Mar 21, 2021 at 11:52
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\$
    – mathcat
    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\$
    – mathcat
    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\$

Rob the King: Hexagonal Mazes

Consider the following hexagonal maze:

     E . \ . . .
    . . . \ . \ .
   . . . . \ . \ .
  _ _ _ _ . \ . \ .
 . / . . . . . . | .
. | . . _ _ _ _ / . .
 . \ . \ . . . / . .
  . \ . \ . . / . .
   . \ . \ . . . .
    . \ . \ / . .
     . \ . | . X

E represents the entrance, X the exit. |_/\ are walls and . are free spaces. In order to navigate from E to X, we can move to any free space in the up to 6 immediately surrounding spaces. The path from E to X, marked with P is:

     E P \ P P P
    . . P \ P \ P
   . . . P \ P \ P
  _ _ _ _ P \ P \ P
 . / . . . P P P | P
. | . . _ _ _ _ / . P
 . \ . \ . . . / . P
  . \ . \ . . / . P
   . \ . \ . . . P
    . \ . \ / . P
     . \ . | . X

This isn't the only path, but the others are trivial variations on it.


Cops

You are to write a function in Python 3 which takes a positive integer \$n \ge 2\$ and returns a hexagonal maze of side-length \$n\$, as shown above. The maze will meet the following criteria:

  • The only characters in the output are EX.|_\/, space and newline
  • The hexagon is shown as a hexagon. That means:
    • The first \$n\$ lines will have one more non-space character than the previous line (the first has \$n\$ non-space characters), separated by a single space, and offset from adjacent lines
    • The first \$n\$ lines have one fewer leading space than the previous line (the first line has \$n - 1\$ leading spaces)
    • The next \$n - 1\$ lines have one more leading space than the previous line
    • The next \$n - 1\$ lines will have one fewer non-space character than the previous line, separated by a single space, and offset from adjacent lines
    • Lines may not have trailing whitespace
  • The E is the first non-space character on the first line, and the X is the last non-space character on the last line
  • There is at least 1 valid path that connects the E and the X, only moving from one free space to an adjacent free space.

How your program generates these mazes is entirely up to you. It could randomly places walls in the grid, ensuring there is always at least one path left, or it could only block the center row except for one gap, or anything else.

You may return either a multi-line string, or a list of lines. Lines should have appropriate space padding at the start, and may have a consistent amount of trailing spaces. "Consistent" here means either the same number on each line, or padding each line to the same length.

The Robbers will be writing maze-solving programs that try to solve your mazes, so you should aim to generate mazes that are somewhat difficult to solve.

This is not , you are under no obligation to golf your submission.

Additionally, you may submit multiple submissions. You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified

Empty mazes of sizes \$n = 2, 3, 4, 5, 6\$:

                                                                 E . . . . .
                                           E . . . .            . . . . . . .
                         E . . .          . . . . . .          . . . . . . . .
           E . .        . . . . .        . . . . . . .        . . . . . . . . .
 E .      . . . .      . . . . . .      . . . . . . . .      . . . . . . . . . .
. . .    . . . . .    . . . . . . .    . . . . . . . . .    . . . . . . . . . . .
 . X      . . . .      . . . . . .      . . . . . . . .      . . . . . . . . . .
           . . X        . . . . .        . . . . . . .        . . . . . . . . .
                         . . . X          . . . . . .          . . . . . . . .
                                           . . . . X            . . . . . . .
                                                                 . . . . . X

Robbers

You are to write a Python 3 function that takes in the return value of a cop's answer. It may also take the number of sides, \$n\$, as an argument if you so wish. The input will only contain EX_|/\. and space, and newlines if inputting as a multiline string. It will either be a multiline string or a list of lines. Your function should handle both.

Your function should then output the maze with any valid path connecting the E and X using only connected free spaces. You may show the path with any character aside from EX_|/\., space or newline.

This is not , you are under no obligation to golf your submission.

Additionally, you may submit multiple submissions. You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified


Scoring

The scoring will take the form of a round-robin, similar to challenges. Every cop will be paired up with every robber, and the following will happen with each pair:

  • The controller will call the cop's function 5 times with \$n = 2\$ as an argument, saving each of the 5 mazes. The cop will have 1 minute to produce each maze
  • It will then pass each maze to the robber to solve. The robber will have 1 minute per maze to produce a correct output.
  • If all 5 mazes are correctly solved by the robber within 1 minute each, the controller goes again, but with \$n = 3\$, and so on, increasing the \$n\$ by one, until either:
    • The robber fails to solve a maze within 1 minute
    • The robber produces an incorrect solution to an input maze
    • The cop fails to return a maze within 1 minute
    • The cop returns a maze with no path

At this point, both the cop and the robber receive points equal to the highest \$n\$ that neither of them failed. If the cop failed, the robber receives an additional point, and if the robber failed, the cop receives an additional point instead.

If both the cop and the robber reach \$n = 50\$ without failing, they both receive \$50\$ points.

After all pairs have be run, the cop and robber with the most points are the respective winners


Meta

\$\endgroup\$
5
  • 2
    \$\begingroup\$ If you want to automate the scoring process, you might want to restrict the I/O further, e.g. only allow stdin/stdout as a hexagon-shaped multi-line string. (I'm suggesting stdio because I assume you want to allow different languages.) Looks interesting, though I have a slight feeling that a full Dijkstra impl in C will almost surely win as a robber. \$\endgroup\$
    – Bubbler
    Apr 12, 2021 at 23:01
  • \$\begingroup\$ @Bubbler Good point, I've updated the I/O to be stricter. \$\endgroup\$ Apr 12, 2021 at 23:22
  • \$\begingroup\$ @Bubbler I've decided to limit it to Python 3 functions, as I was struggling to make a controller that would allow any language to compete \$\endgroup\$ Apr 23, 2021 at 15:49
  • \$\begingroup\$ It's a minor thing, but maybe change E and X to A and B? It seems more logical that way \$\endgroup\$
    – pxeger
    Apr 24, 2021 at 15:52
  • \$\begingroup\$ @pxeger I chose E and X as "entrance" and "exit" respectively, but I doubt it'll affect any solutions as opposed to A/B \$\endgroup\$ Apr 24, 2021 at 16:06
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\$

Time bomb KoTH

\$\endgroup\$
9
  • \$\begingroup\$ Enforcing determinism prevents luck based winning, which I personally like. Adds a sense of balance. \$\endgroup\$
    – Razetime
    May 1, 2021 at 15:59
  • 2
    \$\begingroup\$ Determinism also means anyone can run a simulation of the game on their own machine. The game then devolves into aggressive metagaming and iteratively updating one's bots to always beat the opponents'. If you decide to enforce determinism among the bots, you must have some outside source of randomness to prevent players from simply simulating the entire game and instead actually formulate a strategy that is robust enough to still work well in the face of unknowns. \$\endgroup\$ May 2, 2021 at 9:57
  • 1
    \$\begingroup\$ I personally like a bit of non determinism to spice things up but then this came along. So you have to be careful. \$\endgroup\$ May 2, 2021 at 9:58
  • \$\begingroup\$ @EnderShadow8 yeah I saw that answer. In the current design, the array for the numbers selected in the previous round will be initialized with random numbers on the first round, giving the initial seed of randomness \$\endgroup\$
    – leo3065
    May 2, 2021 at 15:36
  • 1
    \$\begingroup\$ Another thing to consider: high numbers will have very small winning chances, and the entire game is biased towards low numbers (they come first, they don't subtract much, large numbers take many points on explosion vs large numbers give many points on success). So all "smart" bots will choose <= n / 2 numbers, but then the trigger will also be lower, so bots have to choose even lower numbers. That can lead to a case of positive feedback. It may or may not cause problems, but it may be good to keep that in mind. \$\endgroup\$
    – FZs
    May 2, 2021 at 19:24
  • 1
    \$\begingroup\$ And to the determinism topic: a viable compromise between determinism and randomness could be made: making the only allowed non-deterministic part a seeded PRNG function provided by the controller. The PRNG seeds used for the official ranking are kept secret, but it's still possible to replicate the given match by using the same seed. \$\endgroup\$
    – FZs
    May 2, 2021 at 19:58
  • 1
    \$\begingroup\$ @FZs That's true. I may need to buff the reward for larger numbers to encourage playing them. Also about the determinism topic, after some searching I found some method to provide a seeded random, and I think I'm going to try that. \$\endgroup\$
    – leo3065
    May 3, 2021 at 7:41
  • 1
    \$\begingroup\$ More about the determinism: I decided to decide the secret seed before the challenge starts and provide the hash to prove that I won't change the key mid-challenge. \$\endgroup\$
    – leo3065
    May 3, 2021 at 9:14
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ May 3, 2021 at 14:17
4
\$\begingroup\$

Count up to 21

21 is a game my teachers had my classmates and I play in order to kill some time. The game works as follows:

  • All contestants stand in a circle. The aim is to count to 21, one by one.
  • At any time, any player may begin the counting by saying 1.
  • The plays then continue the counting by saying the next number. However, if multiple players say the number at the same time, the count resets, and someone has to say 1 again.
  • The first player who says 21 is "out", and the game begins again with the same contestants except for the "out" player(s)
  • The final player left is disqualified, and the entire game begins again. The last player not disqualified wins.

We are going to run a challenge, where bots aim to play this game.

You are to write a function in Python 3 that takes a list of lists \$L\$ as argument. Each list in \$L\$ represents a round in the game, with the last element being the most recent. The \$i\$th element of each list always corresponds to the same bot. Each list in \$L\$ will contain \$n\$ integers between \$0\$ and \$21\$, where \$n\$ is the number of contestants left in the game. The lists are either all \$0\$s, or are \$n-1\$ \$0\$s and a single non-zero value \$v\$.

If a list is all \$0\$s, either it is the first round, or the counter was reset in the previous round.

That function should then return either:

  • \$0\$, meaning that your bot stays quiet
  • \$v+1\$, meaning that your bot is attempting to guess this round

And that's it!


The competition will work exactly as described above. The controller will run 100 games. Each game will works as follows:

  • The first round begins with all \$n\$ contestants. They will count up to 21, eliminating each contestant as they count to 21, and resetting the count to 0. The final player left is then eliminated, and the next round with \$n-1\$ contestants is run. At the end, the final player left standing wins
  • The player with the most wins after 100 games wins overall

You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified

If any game has more than 10000 rounds, it'll be terminated and no player will win.


Example bot

This is Random:

import random

def bot(history):
	return random.choice([0, max(history[-1]) + 1])
\$\endgroup\$
12
  • 7
    \$\begingroup\$ Infinite loops might happen quite often \$\endgroup\$ Apr 28, 2021 at 1:51
  • 1
    \$\begingroup\$ @RedwolfPrograms Put a limit of 10000 rounds per game \$\endgroup\$ Apr 28, 2021 at 20:32
  • \$\begingroup\$ TNB Feedback link \$\endgroup\$ Apr 28, 2021 at 21:16
  • 2
    \$\begingroup\$ So, if next number is 21: Is there any reason a bot will not to say 21 in that round? \$\endgroup\$
    – tsh
    Apr 29, 2021 at 1:30
  • 2
    \$\begingroup\$ I feel like someone's going to just add a bot to say every single number no matter what. \$\endgroup\$
    – emanresu A
    Apr 29, 2021 at 10:54
  • \$\begingroup\$ @tsh If multiple bots say 21, none of them win and the count resets \$\endgroup\$ Apr 29, 2021 at 11:51
  • \$\begingroup\$ Can you post the code to run the game so we can test our bots? \$\endgroup\$ Apr 29, 2021 at 21:05
  • \$\begingroup\$ @fasterthanlight I haven't written the controller yet, so no \$\endgroup\$ Apr 29, 2021 at 22:57
  • 2
    \$\begingroup\$ but if i will lost their turn if i dont say 21, and the worst case is a tie if I say 21? So any reason I try to be silent? \$\endgroup\$
    – tsh
    Apr 30, 2021 at 5:10
  • 2
    \$\begingroup\$ Because there's no reason to not say 21, infinite loops are probably going to occur no matter what. You might want to consider adding a rule regarding this to prevent infinite loops (or if everyone but 1 says a number the bot who said 0 can be eliminated) \$\endgroup\$ Apr 30, 2021 at 12:44
  • \$\begingroup\$ Just wondering, is saving state between different turns allowed? Or between rounds? Or between games? You also don't seem to distinguish between rounds and turns (i.e times when the count resets vs. opportunities to guess), which may cause confusion. Also, a suggestion: Maybe let each game have only a small subset of the bots as contestants, so that if there's that one bot who always says 21 as soon as possible, it would just harm itself rather than ruining the challenge. (Sorry for this long block of text.) \$\endgroup\$
    – Andrew Li
    May 4, 2021 at 3:42
  • \$\begingroup\$ Interestingly, this is completely different from the game of 21 I know. \$\endgroup\$
    – pxeger
    May 23, 2021 at 15:57
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\$
    – mathcat
    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\$
    – mathcat
    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\$

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 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 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 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 at 12:40
1
9 10
11
12 13
134

You must log in to answer this question.

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