# What is the Sandbox?

This "Sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to the main page. This is useful because writing a clear and fully specified challenge on 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.

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

# Peel away the layers - Robbers

• I feel like you could remove a lot of the complexity of the challenge description by just requiring robbers to crack the whole submission at once, and so you don't need to specify MD5 hashes or anything like that and you don't need to worry about rep/CW/answer chaining. This might also allow for creativity by creating 'misleading' chains of polyglots (you decode with lang A in a chain, you get Greetings?, but in lang B you get Greetings!). You should also specify whether multiple of the same language in a chain is allowed. – Sisyphus Sep 26 '20 at 11:42
• Also consider that answers of the form echo "....." would be valid, and reduce to The Programming Language Quiz. You might be able to ward off just replicating the original challenge by having a very strict set of allowed languages (eg. must be on TIO), which would force using the polyglot system effectively. – Sisyphus Sep 26 '20 at 11:42
• @Sisyphus I've sat on it for a few days, and I think that's probably the best way forwards, even if it does make the Robbers' jobs harder. "You may repeat languages" is already in the spec (now bolded). I don't want to have to limit the available languages/interpreters any more than I have to, as some of the best answers to the last challenge like this (TPLQ) relied on the more obscure interpreters, and limiting languages could ruin that. Given that this requires 2 languages minimum, and that echo "..." style answers probably won't be competitive, I think this should be different enough – caird coinheringaahing Sep 30 '20 at 22:25
• Looks a lot better. You have my upvote. – Sisyphus Sep 30 '20 at 22:52
• You should limit the program size to fitting literally inside the answer, otherwise you might get unary shenanigans that make cracking literally impossible – pxeger Oct 1 '20 at 16:06
• @pxeger On second thoughts, I've decided to limit each program to 65535 bytes, just to keep it sensible – caird coinheringaahing Oct 1 '20 at 16:33
• Does an inner layer have to output a full program, or can it print a function? – pxeger Oct 1 '20 at 18:50
• @pxeger Either is fine, I'll edit that in – caird coinheringaahing Oct 1 '20 at 18:55
• So just to clarify, we don't need to reveal the number of layers, just the number of distinct languages? – Sisyphus Oct 4 '20 at 7:43
• "Free here means that anyone can use the program without having to pay to do so" - is it still free if they must pay with their time and sanity? – pxeger Oct 4 '20 at 8:42
• Did you mean Robbers' not Robber's chatroom - it's not entirely clear – pxeger Oct 4 '20 at 11:52
• @Sisyphus the robbers' task is hard enough as is, let alone having to deal with cops that may use 2 languages but have 15 or so layers, so I've edited it to consistently say that you have to reveal the number of layers, – caird coinheringaahing Oct 4 '20 at 19:35
• @pxeger "Free" means per site standards, and yes, I've corrected that typo – caird coinheringaahing Oct 4 '20 at 19:35

# King of the Hill: Avalon king-of-the-hill

(See revision history)

# We're all unique in our own way

• I like the idea, but I feel like there should be some incentive to make the byte requirement small, large, contain common bytes, contain uncommon bytes, etc. Is there any reason to pick anything other than randomly? – Redwolf Programs Oct 4 '20 at 0:05
• @RedwolfPrograms I've decided to make the number of bytes allowed has to be unique for each answer (i.e. only one answer may allow 120 bytes etc.), which means that people will have to be more selective with how many bytes are allowed when posting new answers, as well as which of those bytes are allowed – caird coinheringaahing Oct 4 '20 at 0:44
• Suggested edit: "The chain ends when 14 days pass with no new answers being posted or when all unique number of bytes have been used" – Lyxal Oct 4 '20 at 6:13
• Also, there's no incentive to answer high no.bytes, as no one wants to have a high amount tacked onto their score. – Lyxal Oct 4 '20 at 6:14
• Further, I suggest you add a "languages cannot be newer than 4/10/2020" to avoid sandbox sniping – Lyxal Oct 4 '20 at 6:16
• Proposed scoring system: each answer is worth 257 - n points (n = number of allowed bytes), highest score wins. – Lyxal Oct 4 '20 at 6:18
• Does “each byte must be used a minimum of one times” mean you have to use every byte in the list? If so, I think framing this as a list of bytes you “can use” is misleading. Also, if you have to use 100 bytes, but your answer only needs 20, does anything stop you from just stuffing those remaining 80 bytes in a comment or an unused string variable? It might be more interesting if you force those bytes to have some function in the program, or get rid of this requirement and let people use a subset of the allowed bytes. – water_ghosts Oct 4 '20 at 16:14
• @Lyxal I've added in that ending condition. I don't think any scoring system that involves the number of bytes available will provide an incentive to answer with both high and low bytes, so I've changed the score to be the number of answers posted. I dislike banning languages in general, so I've only banned languages specifically designed to answer this challenge – caird coinheringaahing Oct 4 '20 at 20:37
• @water_ghosts Yes, it does mean that, I've edited to reflect that. Nothing's stopping you from having portions of the code completely unexecuted, and requiring all code to be run is an unobservable requirement. Given how broad new answers can be in terms of language and output, I think it shouldn't be an issue with requiring all the bytes be present – caird coinheringaahing Oct 4 '20 at 20:50

# The Great Code Golf Heist

Alternatively, the most literal cops'n'robbers you'll ever see

## Backstory

Sandbox Note: This part will be specific to each thread, so I've provided each version

### Robbers

For the last few years, you and your team of robbers have been planning to rob the International Code Golf Museum (ICGM) of some of it's most prized possessions (rumour has it, they have a rare transcript of Dennis being outgolfed!). Tonight is the night that your plans will be put into action... tonight you will walk away with glorious riches and legendary artifiacts of code golf history.

That is, if you can actually manage to get in, loot the rooms and get back out without getting caught.

### Cops

Tonight has been a quiet night at the Internation Code Golf Museum (ICGM)...too quiet for one's liking.

Of course, that's probably due to the fact that a bunch of robbers are rumoured to strike tonight and steal the most priceless artifacts from the ICGM's collections (we can't have them finding out the fact that Arnauld is a machine learning algorithm designed to answer challenges with Javascript, can we. [that's a joke we love you Arnauld!])

It's your job to stop the robbers and make sure that not a single thing leaves the museum.

## The Museum

Sandbox Note: This part is common to both cops and robbers

Here is a map of the museum:

You may be wondering "hang on, what are the dimensions of that map?". Well the answer is simple: you don't need to know.

Movement around the ICGM is analogous to a Henry Stickmin game: in each room, you can either move to an adjacent room, or perform an action in that room.

Robbers start at the Getaway Car and can enter through either Hallway A or Hallway B. They then move through Hallway A.A then Hallway A.B or move through Hallway B.A and then Hallway B.B. Either way, they end up at the exhibition room. From the exhibition room, robbers can move to any of the treasure rooms which is where all the valuables are stored. After that, they make their way back to the getaway car to, well, escape and get away.

Cops are randomly allocated a position at the start of the heist, and can move wherever they need to.

Sandbox Note: There's going to be a system where each room takes a certain number of "strides" to get from one end to another. This way, robbers with stolen items are "slowed down" a little and the cops have a bit of a chance to catch up

## Stealing Treasures

Sandbox Note: Robber specific

Once you reach a treasure room, you have the oppourtunity to get your hands on some of the finest works the ICGM has to offer. There will be a selection of items to choose from, each with different values. Sandbox Note: I might add a part where there is a limit on how much robbers can carry

However, items with more value impact how fast you can move through. Sandbox Note: Something relating to the stride system here.

But being the sneaky robbers you are, you have a few tricks up your sleeve(s). When moving through the ICGM, you can:

• Activate a trap that will slow down the cops (avaliable only once Sandbox Note: Subject to change)
• [Other things coming soon]

Once you get back to the getaway van, everything you have stolen is considered "safe" and counts towards your team's score. But once you're in the van, that's it... you can't go back for more.

Your team wins if you manage to steal items with a combined worth of insert value here

## Protecting the ICGM

Sandbox Note: Cop specific

In order to protect the artifacts of the ICGM from being stolen, you have a few abilities you can use against the robbers. You can:

• Apprehend a robber if they are in your proximity
• [Other things coming soon]

For your team to win, the total value of items stolen must not exceed insert value here

## The Catch

Sandbox Note: Common to both threads

The heist program will only be simulated once. That means that if your submission errors, you're out of the game for good. I mean, you don't see criminals replace the things they stole just to rerun the heist over and over to see how good they are ;P.

The heist will occur on insert date here. You can edit your submissions all you like until the time of running.

Coming soon.

# Feedback

• Seeing as how this is a first draft, there are bound to be flaws with things like the movement mechanics and cop/robber interactions. I'm more looking for first impressions and overall flaws in the challenge.
• I can't wait to see the valuables you place in the treasure room. – RGS Oct 13 '20 at 17:13

# Secret ">" Stacking Challenge: cheating code-golftetris

Sequel to Secret ">" Stacking Challenge: grading. You can skip the whole Background section if you already read the first one.

## Background

Tetris Grand Master 3 has a hidden grading system based on the shape of the stack at the end of the game, which is called Secret ">" Stacking Challenge. It consists of entirely filling the lowest rows except for the zigzag pattern which starts at the left bottom cell and spans the entire width:

#
.#########
#.########
##.#######
###.######
####.#####
#####.####
######.###
#######.##
########.#
#########.
########.#
#######.##
######.###
#####.####
####.#####
###.######
##.#######
#.########
.#########


The board is graded by how many lines follow this exact pattern from the bottom line. Note that the topmost hole in the pattern must be blocked by an extra piece of block. If you consider the #s and .s as the mandatory pattern (blanks can be anything), you can get the score of 19 only if the exact pattern above is matched from the bottom line. Analogously, if the board matches this pattern

   #
###.######
##.#######
#.########
.#########


but not

    #
####.#####
###.######
##.#######
#.########
.#########


then the score is 4.

For this challenge, consider a board of arbitrary size (other than 20 cells high and 10 cells wide). We can grade the board for the same pattern: for example, if the board has width 4, this is the pattern for score 3:

  #
##.#
#.##
.###


and this is the pattern for score 10:

   #
###.
##.#
#.##
.###
#.##
##.#
###.
##.#
#.##
.###


## Challenge

Given the board width and the desired score for Secret ">" Stacking Challenge, pick a sequence of tetrominoes and generate the sequence of moves that will achieve the score. The Tetris moves can be represented in any ways that clearly specify where each tetromino is placed in which orientation, optionally along with the board state after each placement.

For the Tetris movement rules, we use simple permissive rule as in this challenge: you can place a tetromino anywhere (even in closed rooms), as long as it doesn't float in the air or overlap with existing pieces. Therefore, if you plan to use coordinates, you need to specify both x and y coordinates (the y coordinate should be counted from the bottom, as the board can grow upwards without bound -- or count from the top by also outputting the field height).

You can assume the width is at least 5 and the score is nonzero. You should theoretically support arbitrarily high score. The generated sequence doesn't need to be minimal.

Standard rules apply. The shortest code in bytes wins.

## Output example

For board with 6 and score 2, one possible way is as follows: (As are the tetromino placed at each turn, # are existing pieces on the board, and . are empty cells)

......  ......  ......  ......  ......
A.....  #.....  #.....  .AA...  .##AA.
AA....  ##AA..  ####AA  #.AA..  #.##AA
.A....  .#AA..  .###AA  .#####  .#####


The above is a valid output format (you can choose any distinct chars/values in place of .A#). The following is also valid (although it is less obvious, it is indeed an unambiguous description of tetromino placements):

......  ......  ......  ......  ......
A.....  ......  ......  .AA...  ...AA.
AA....  ..AA..  ....AA  ..AA..  ....AA
.A....  ..AA..  ....AA  ......  ......


And this: (tetromino code, rotation, x and y coordinates from bottom left, 0 indexed)

S 1 0 0
O 0 2 0
O 0 4 0
Z 0 1 1
Z 0 3 1


And anything in between (e.g. showing tetrominos as a canonicalized matrix instead of a code). If in doubt, ask in comments.

# Calculate the inverse of a matrix

• n , nor n2, will never exceed the maximum value... and The elements of M−1 will never exceed... Even under those assumptions, intermediate computations can exceed the maximum. So maybe it's better to say something more general, maybe along the lines of this – Luis Mendo Oct 2 '20 at 23:18
• Also, matrix inversion notoriously causes floating-point error build-up when naïve algorithms (i.e. algorithms not specifically designed to avoid error accumulation) are used. This results in relatively large errors in the output. And those algorithms are likely to be the ones used in a golfing challenge (if the language doesn't have a builtin). So maybe you should add a note saying that it is sufficient if the algorithm works when arbitrary precision is assumed – Luis Mendo Oct 2 '20 at 23:18
• @LuisMendo I've edited in "It is acceptable if your program fails for some inputs due to floating point issues, so long as the underlying algorithm or method works for arbitrary matrices." which I think should cover both of those points – caird coinheringaahing Oct 4 '20 at 20:58

# Can I print my picture on {A,B,C}{0-10} paper?

The task is to find the smallest paper size on which it is possible to print a picture of the dimensions given in milimetres. The image will be printed without margins.

# Input:

Two numbers (bigger than zero) and a letter a, b, or c, for example:

290
200
A


# Output:

Paper size, for example:

A4

Another examples:

218,297,a      A3
1,1,c          C10
9999,9999,c    ??? (error)
74,52,A        A8
31,44,B        B10
26,1100,A       A0


• Upper- and lowercase variants of letters "A", "B" and "C" are allowed on input and on output.
• The image can be printed vertically or horizontally.
• The values can be passed as a parameter or entered by the user.
• Width and height of picture will be always > 0, and letters will be always 'a', 'b', or 'c'. You don't need to validate them.
• You need to handle paper sizes A0 - A10, B0 - B10 and C0 - C10. If the image is too large, you can throw an exception, print an error or whatever you want, as long as it is clearly different from valid result and the application will not hung up.

Paper sizes, please ignore inch values (source: Wikipedia) :

This is - fewest bytes wins.

• Perhaps you should inline what sizes the An, Bn and Cn papers are. Also, some more test cases (~5-10) would be nice for the final version. – Sisyphus Oct 22 '20 at 0:03

Posted to main

# Brainfuck arbitrary precision multiplication

## Goal

The goal is to multiply two numbers in the shortest amount of cycle.

## The Input

The input is two numbers written decimally separated by a space. The number is NOT restricted by the size of the integer inside of the cells. The program must accept arbitrary sized integer

## The Output

The output is a single integer written decimally.

## Brainfuck variants used

Since the flavors of the Brainfuck is important in this challenge, you are required to use this flavor

### Memory

The memory is an array of cells, unbounded to the left and the right, with 8-bit integer as the contents.

### Input/Output

The input and the output uses ASCII symbol mapping. EOF is interpreted as \0 char.

### Looping

The [ means that "check the current cell. If it's zero, jump to the instruction after the matching ]" The ] means that "jump to the matching [." no cycle is taken in this instruction.

### Cycle

Every instruction takes a single cycle every time it's executed except for ]. ] is a free instruction.

### Reference implementation

For the reference implementation, use copy.sh with this option:

1. Cell size (Bits): 8
2. Dynamic (infinite) Memory: yes
3. End of input: char: \0
4. Count instructions

## Scoring

The winner is the program that is: (later number is for tiebreaker)

1. The program with lowest computational complexity (counted by using cycle metric as explained above, and in x where x is the length of the largest input in base 10) is the winner.
2. The program with lowest space complexity (counted by finding the rightmost cell reached by program)
3. The program that takes the least cycle to execute 1234567890*987654321
4. The program that takes the least memory to execute 1234567890*987654321
5. The shortest code

Computational complexity is determined in terms of the number of digits each arguments have.

• fastest-code is the winning criterion tag, so you don't need code-challenge. To lower the obstacle before starting to work on the challenge, I suggest to use the copy.sh online interpreter as the standard. (I think it satisfies the cycle count rule?) – Bubbler Sep 3 '20 at 7:02
• @Bubbler Actually, I designed my challenge with copy.sh as the reference. The only difference is that the memory tape is not unbounded to the left. – Xwtek Sep 3 '20 at 7:25
• You can set "memory overflow behavior" to "abort" for that. – Bubbler Sep 3 '20 at 7:39
• @Bubbler It's not possible to have both infinite memory and abort as memory overflow behavior. I changed the challenge so that the memory is also unbounded to the left. – Xwtek Sep 3 '20 at 7:42
• Can we make assumptions such as 'the number of digits in the numbers is less than X' or 'the number of digits in the number of digits in the numbers is less than X'? – the default. Sep 5 '20 at 14:32
• @thedefault. No. The program must handle arbitrary sized number. – Xwtek Sep 5 '20 at 15:57
• @Xwtek So it would be impossible to answer it in a flavor with 30000 cells of one byte each? I think the limit on the size of each number should be half of the number of cells (and thus infinite for flavors with infinite cells) – Redwolf Programs Sep 9 '20 at 23:30
• @RedwolfPrograms Yes, it's impossible. Maybe I'll make a challenge to minimize memory use, but for now, you have to use infinite flavors. "I think the limit on the size of each number should be half of the number of cells" Not necessarily, I bet you need much more memory than that. – Xwtek Sep 11 '20 at 2:20
• "Given a list of strings of two-letter abbreviations (see below) for US states, determine whether they are connected." So can we expect a python list? Or should we expect a comma separated list? I think you should clarify the input. Giving the input as a python list gives python (and any other languages that have the same syntax) an advantage over, for example bash. – nthnchu Nov 8 '20 at 14:27
• What should the output be? Is it <input> is not connected. or <input> is connected.? Or can it just be true/false? – nthnchu Nov 8 '20 at 14:48
• @nthnchu I think they mean a list of strings, whatever that is in your language. I agree with using truthy/falsy for connected/not connected. – Razetime Nov 8 '20 at 15:13
• @Keba Are we required to compress the list, or take it as an input? If we need to compress it, add kolmogorov-complexity. – Razetime Nov 8 '20 at 15:14
• Thanks for your replies. My idea was that the exact input/output format should not matter to much. Accepting a list of strings is fine but I guess just a long string such as "AK WA OR" or even "AKWAOR" is also fine – whatever works well in your language. And output should be truthy/falsy, yes. Thought that was covered by standard I/O rules but tried to clarify it. – Keba Nov 8 '20 at 17:20
• @Razetime: Sorry, I am not sure whether I can follow. The code should output a truthy/falsey value for a given list of strings. – Keba Nov 8 '20 at 17:22
• @Keba They are asking whether the list of states is provided as input or if we must keep it in our code. If we should keep it in the code, you should add the kolmogorov-complexity tag. – nthnchu Nov 8 '20 at 22:20
• @nthnchu The input should consist of a list of strings such as ["AK", "WA"] (or something equivalent) and nothing more. The list of neighboring states, however, is not included in the input. Still, the output is not constant and hence that tag does not apply? – Keba Nov 8 '20 at 22:49
• @Keba It still has the large constant string of the neighboring states. Look at wikipedia and kolmogorov-complexity's info page for more info. – nthnchu Nov 8 '20 at 22:57
• Even though the output isn't constant is still relates to it. – nthnchu Nov 8 '20 at 23:04
• From that page: ”a post should be tagged kolmogorov-complexity iff the bulk of the challenge is to produce a string or a subset of a dataset which is given in the question.“ I do not thing that the bulk of the challenge is to produce that string. First, that string does not need to appear anywhere and second, the main problem should be to decide whether the corresponding graph is connected or not. – Keba Nov 8 '20 at 23:17
• And this question looks very different from the ones posted with that tag. – Keba Nov 8 '20 at 23:18
• Yeah you're kind of right. Just wondering, is ["AK"] considered connected? – nthnchu Nov 8 '20 at 23:41
• It is, I add it to the list of test cases. – Keba Nov 8 '20 at 23:50
• My case for the tag is that compressing the string is one of the only ways to win; I just completed the challenge in less bytes than the string in python because I compressed it. – nthnchu Nov 9 '20 at 0:01

# Is my triangle on the lattice? decision-problemcode-golfgeometry

Posted on the main site.

# Is it a Lobster Number?

## Posted

• I like the idea, but the fact that prime numbers don’t count seems a bit arbitrary. – user Jan 23 at 21:11
• It definitely is a bit arbitrary, but I felt that it made sense as an edge case, since while it is a prime factor, it is already the number itself, and there are no other factors. The related (but not identical) OEIS sequence also seems to have made this distinction, so it seemed reasonable. It also has the simple explanation that lobsters are not needed to get the result for the prime numbers, and shouldn't be overly difficult to work around in golfing, as all you need is a single comparison (is there only one factor, or is the first factor equal to the number). – IronEagle Jan 23 at 21:35
• Yeah, that makes sense, and it's not a deal-breaker for me, it would just make writing an answer slightly more annoying :) – user Jan 23 at 21:36
• @user - Posted since there seems to be no general problems with the question. – IronEagle Jan 24 at 15:04
• Well, I don't see any problems with it myself, but it would have been good to let it sit a few more days to get more feedback – user Jan 24 at 15:07
• @user - I'll keep that in mind, this is my first question here, this site is quite a bit different from the other StackExchange sites. – IronEagle Jan 24 at 15:13

## BF memory layout optimizer (posted).

See the notes in the revision history.

• (upvote this comment if you want a variant with [fastest-code] instead.) – user202729 Jan 31 at 2:11
• (upvote this comment if you want both a [code-golf] version and a [fastest-code] version.) – user202729 Jan 31 at 2:11
• (upvote this comment if you want only a [code-golf] version.) – user202729 Jan 31 at 2:11

Note:

• as you can probably tell, this is a simpler variation; however the poster of the other sandbox post has not been visiting the site for a while.
• because of the current situation, I recently (after the 2 upvotes is made) changed the winning criteria. Is there any problem with the description?
• What info should be included in the header?...

## Efficient table-lookup computation

• (ah, right. The sandbox is still as inactive as usual.) – user202729 Jan 30 at 17:16
• Or it could be that the challenge is simply a little hard to read.) – user202729 Jan 31 at 14:45
• If two answers have the same A+B, is the one with lower A or lower B considered better, or is there no tie-breaker? – Dingus Feb 2 at 8:43
• @Dingus No, see the meta post about challenge having multiple winning conditions. codegolf.meta.stackexchange.com/questions/19041/… – user202729 Feb 2 at 10:19
• There's no consensus on that meta question. I think you should state that if two answers have the same A+B then they score the same. – Dingus Feb 2 at 10:37
• @Dingus +1 is not a consensus? – user202729 Feb 2 at 10:42
• A post is considered as a consensus only if it's at >= +10 and upvotes >= 2*downvotes. So +5/-4 (at the time of writing) is closer to a controversy than a consensus. I guess many people have just feelings without enough justification about whether it's fine or not. I personally view it as a good challenge, so I upvoted it. – Bubbler Feb 8 at 23:20
• A minor nitpick: In your Python code, adding string to a number is invalid. I guess you meant to take the inputs as strings, e.g. m1 = "0" etc. – Bubbler Feb 8 at 23:21
• For the lack of sandbox feedback, I usually leave my challenges for at least a week, regularly asking for feedback in the chat (at least 2 or 3 times before moving to main). – Bubbler Feb 8 at 23:24
• @Bubbler Fixed. – user202729 Feb 9 at 1:41
• to me it looks like the given method to generate a single score from A and B only adds confusion, especially the "combined score" part... what's the advantage compared to a simpler formula like A^2+B^2? (I would be in favour of just using A and B and letting all pareto-optimal solutions win, but I understand that at the moment there's not enough consensus for this) – Leo Feb 12 at 8:57
• @Leo Because it doesn't encourage these solutions, obviously? -- (I think that the solution with minimum A is pretty interesting, but I'd like to see a solution that generates reasonably-good parametrized solutions too.) – user202729 Feb 12 at 9:53
• @Leo as explained in the linked meta post -- (did I explain it clearly enough?) that method would allow essentially the same "every solutions win" situation by letting every such "winning" solution improves the "combined" score. (and is the only one that I can come up with with that condition) – user202729 Feb 12 at 9:54
• The problem with the combined score is that you have two scores again, the "normal" one and the "combined" one... Does only one or the other count for "victory"? – Leo Feb 12 at 10:29
• @Leo Obviously the combined one. Note that the criteria is chosen so that the combined score is always better than or equal to the normal score, and the combined score is always better than the previous combined score. – user202729 Feb 12 at 10:32

# Generalise perfect numbers

• Better having a statement "in this challenge $\sigma^n(k)$ denotes...". It can be interpreted as $(\sigma(k))^n$ too. – user202729 Feb 24 at 4:15
• Can answers assume that "the sequence is infinite"? – user202729 Feb 24 at 4:16
• @user202729 Addressed both questions – caird coinheringaahing Feb 28 at 1:18

# Byte-sized Huffman Coding (WIP)

Huffman codings are a method to compress data with certain frequency properties, usually text. Normally, these operate on bits rather than bytes, but this challenge will instead operate on whole bytes instead. Since you wouldn't get any benefit otherwise, you can represent multiple consecutive characters with a sequence of one or more bytes, for instance '. ' (a period followed by a space) could be represented by byte 1, 'The' could be represented with byte 2, and 'Ishmael' could be represented by a 255 then a 7 (among many other sequence codings).

# Challenge

Create a program that compresses a plain-text version of a work of literature by returning a byte-wise Huffman coding table and a sequence of bytes that represents the text with that table.

## Rules and Assumptions

• You may assume that the text is written in English and uses only printable ASCII characters plus space, newline, and tab.
• It must be a proper Huffman coding; no mapping may be the prefix of another.
• Not all Huffman sequences need to be mapped to a particular character sequence; you could, for instance, not have 7 mapped to anything or not have 255, 39 mapped to something, but have every other 1 and 2 byte sequence mapped to something.
• The returned coding table must be able to encode every possible sequence of valid characters (as per the first assumption above). The simplest way to do this is to make sure that every individual character is mapped to a Huffman byte sequence.
• It can be possible to encode a body of text multiple ways using the returned encoding table. If both ca and at are mapped to byte sequences, cat could be encoded two ways. This is totally fine.
• Case must be preserved.
• Runs do not need to be deterministic, i.e. two runs of the same program with the same input could produce different Huffman tables and compressed output.
• Your program must return a result within a reasonable amount of time to be considered a valid solution. (If you want a hard limit, I'll say 5 minutes on a 2GHz Intel dual-core i5 with 16 GB RAM running Windows 10)

## Scoring

Your results will be run against a corpus of (TBD) 12 publicly available literary (and non-fiction) works. For each work of literature, your score will be the size, in bytes, of the compressed text, plus the total length of all text strings mapped to a byte sequence in the Huffman-coding table. Your overall score is the total score across all 12 works.

Lowest score wins.

### Literature list

• The King James Bible
• Hamlet by William Shakespeare
• Dracula by Bram Stoker
• Frankenstein by Mary Shelley
• On the Origin of Species by Charles Darwin
• Moby-Dick by Herman Melville
• Little Women by Louisa May Alcott
• Tom Sawyer by Mark Twain
• Pride and Prejudice by Jane Austen
• The Hound of the Baskervilles by Arthur Conan Doyle
• < Something that entered the public domain in 2019 because it was published in 1923 >
• < Something written in the last 20 years willingly released into the public domain or with a Creative Commons license that allows derivative works >

### Sandbox

At least one of the last two literary works should preferably be written by a female and/or non-white author to hopefully make writing styles diverse enough to make hard-coded Huffman tables ineffective. Each work should be comparable in length to the other works.

Links to these books (in plain text) would be appreciated. Substitution suggestions are welcome.

• If you want to vary writing styles, is there a non-fiction work that only contains the allowed characters? – trichoplax Sep 24 '19 at 23:21
• @trichoplax The most notable non-fiction book I can think of for that would be "On the Origin of Species" by Charles Darwin. I've also thought about throwing in the King James bible. Maybe I could bump up the total to 12 works. I also probably will drop War and Peace because the plain text version I found was machine converted and has issues. – Beefster Sep 25 '19 at 15:21
• Regarding plain text books, have you checked Project Gutenberg? They have plaintext versions of many of their books. – AdmBorkBork Sep 25 '19 at 18:35
• I have no idea how much sample text is a good amount for this challenge (number of books, length of books) but it's probably worth doing some kind of rough check that there is enough text to give variation between answers (no optimal solution) while still being little enough text that running in a reasonable time is realistic (doesn't require weeks of work before an answer is efficient enough to meet the time restriction). Maybe others can suggest good ways of approximating this? – trichoplax Sep 25 '19 at 20:16
• @trichoplax so basically you suggest sampling out, say, a few chapters instead of the whole book and then reducing the required runtime? I'm open to that, especially since the word count difference between Hamlet and the Bible is so big. The interesting thing about the Bible is that it has a ton of different authors, so it would almost be better to have the first chapter of each book instead of inserting, say, the entirety of Genesis. – Beefster Sep 26 '19 at 4:41
• I couldn't guess at this point whether more text or less text would be better, and I don't have a way of estimating, just wondering if anyone else does. – trichoplax Sep 26 '19 at 7:32
• I see no problem with 5 minutes as a rough time limit. I'd lean towards a time limit that allows someone to write a quick answer and then improve on it gradually, to encourage more participants. How long that needs to be for the text you settle on I don't know. As long as you're confident an optimal solution can't be found, you could just time a naive approach and then choose a time that doesn't exclude that. Then you can get lots of early answers to get the competition going, but still have open ended improvement over the long term – trichoplax Sep 26 '19 at 7:38
• Not to say that this isn't an interesting challenge as it is but I do wonder if it wouldn't be more interesting without requiring that we use Huffman Encoding? – Shaggy Sep 27 '19 at 22:21

# What's the odd one out?

• Looks like this but a bit more interesting – Razetime Mar 9 at 13:35
• Great challenge! Seems ready to be posted – ophact Mar 9 at 16:03

# Sociable sequences

• You probably need to describe what a proper divisor is. Separately, I'm not sure how great requiring infinite output is. I'd probably consider allowing another optional argument that limits how many sequences to output? – FryAmTheEggman Nov 12 '20 at 19:47
• @FryAmTheEggman I've updated the challenge to be closer to the normal [sequence] I/O rules – caird coinheringaahing Nov 26 '20 at 15:23
• So is 25 a 1-sociable number, since its divisors sum to 6, and then there's a cycle? – user Jan 6 at 21:04
• @user No, $25$ is not a $1$-sociable number. "They are numbers whose proper divisor sums form cycles beginning and ending at the same number". $25$'s "cycle" is $25 \to 6 \to 6 \to \cdots$, which does not begin and end with the same numbers. I'll edit that in though – caird coinheringaahing Feb 22 at 17:50
• That "begin and end at the same number" is unclear. (it's a cycle, it neither begins nor ends) Perhaps "the initial number is inside the cycle". – user202729 Feb 24 at 4:30
• Should that "given value" be interpreted as "value that will be given as input"? – user202729 Feb 24 at 4:31
• That "does not diverge" sounds like a terribly hard conjecture... EDIT indeed it is. en.wikipedia.org/wiki/Catalan%E2%80%93Dickson_conjecture ("likely false"), and looks like that the sequence you came up with already have a name. – user202729 Feb 24 at 4:32
• with that, it's problematic, you'd better specify that "If there are $n$ such numbers, the answer must provably finish printing them all without assuming the conjecture" -- although for most approaches it isn't that hard. – user202729 Feb 24 at 4:38

# 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:

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

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:

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
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.

# 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?
• @Beefster Aside from involving tiling, I'm not quire sure how that challenge is related, let alone a possible duplicate – caird coinheringaahing Sep 28 '20 at 22:00
• 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. – Beefster Sep 28 '20 at 22:03
• Related – Beefster Sep 28 '20 at 22:04
• 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. – xash Mar 17 at 19:21
• @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 – caird coinheringaahing Mar 17 at 19:22
• @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 – caird coinheringaahing Mar 17 at 19:26
• 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. :-) – xash Mar 17 at 19:29
• 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. – Nick Kennedy Mar 20 at 7:42
• Will the 19 possible tiles be supplied as an input or do they need to be encoded into the answer? – Nick Kennedy Mar 20 at 7:46
• @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 – caird coinheringaahing Mar 21 at 11:52

# Write an interpreter generator

• Can an input contain one or more operations? like a + 1 - 4 * 8? Is input guaranteed to be valid? – Wasif Mar 22 at 17:11
• @Wasif editing the answer – ophact Mar 22 at 17:12
• Another suggestion, you might make it a code-challenge, where the objective will be to generate as short output as possible (Which means to golf the generated interpreter as much as possible), where the original source code length will not matter, so people can work for their code more peacefully, But code-golf (original challenge) one is good too. – Wasif Mar 22 at 17:14
• @Wasif hmm... not a bad idea at all. This challenge does seem more effective with the code-challenge tag, I will edit that into the answer. – ophact Mar 22 at 17:17
• @Wasif on second thought, I'm not really sure how you would actually test the length of the output... it would not be fair for one answerer to test with a 100-command language while another tests with a simple 1-command language. Thanks for the suggestion, but code-golf seems like the better option for now. – ophact Mar 22 at 17:19
• OK, also how would handle destructive input like a / 0, which attempts to divide the accumulator by 0, which would result into crashing the interpreter? – Wasif Mar 22 at 17:22
• the input is valid doesn't seem like a good enough description, let me change that – ophact Mar 22 at 17:22
• "each command is one letter long." so, highest number of inputs are 26? – Wasif Mar 22 at 17:33
• Can we pre-define the input array in the header section of Try It Online? – Wasif Mar 22 at 17:35
• @Wasif yes, that can be inferred from that fact. Not sure what the header is, because I don't really use tio – ophact Mar 23 at 6:23
• Header section means the part where you write code, is not added to the byte count. – Wasif Mar 23 at 6:52
• Let us continue this discussion in chat. (Automatically comments were moved there because lengthy conversations cannot be run in comments) – Wasif Mar 23 at 6:52
• I've edited this to a stub now that it's been posted – caird coinheringaahing Mar 23 at 15:40
• @ChartZBelatedly thank you, forgot to do that – ophact Mar 23 at 16:05

# Keep PPCG running in Game of Life

• "Minimally destroying CGCC", "Keep PPCG running". Hmm, someone doesn't like the name change :). May I ask why you have this proposal too, though? – user Mar 22 at 19:24
• @OriginalOriginalOriginalVI Because the two tasks are different, and I very much doubt answers to the two will be trivially similar – caird coinheringaahing Mar 22 at 19:38
• Right now you could just place a glider in the box and it would run forever. Maybe redefine 'fixed position'? – A username Mar 23 at 8:16
• @Ausername "If any spaceships or patterns of infinite growth are generated, the board will never reach a "fixed state" and such cases are invalid submissions." A glider is a spaceship – caird coinheringaahing Mar 23 at 13:13
• Oh ok, didn't see that bit. – A username Mar 23 at 19:37

## Limit of lists code-golf

You're given a never-ending sequences of lists, each of which appends some number of values to the end of the previous one. That is, each list is a prefix of the next.

3
3,1,4
3,1,4,1
3,1,4,1
3,1,4,1
3,1,4,1,5,9,2,6
...


While some steps may leave the list unchanged, its length grows unboundedly, giving an infinite list in the limit. Your goal is to output this infinite list.

Note that you can't know a-priori how many lists you must read to get, say, the 5th value in the infinite list, just that you'll eventually hit a list with 5 or more elements.

Input and output:

The list elements are digits 0-9. You may treat them as characters if you wish.

The input and output are both infinite lists. These can be represented in various ways, and may be different for the input and output.

• An infinite list or stream
• A stateful method or black-box function that produces a new value with each call
• Repeatedly reading from STDIN or writing to STDOUT, or file buffers or the like

A mapping from index to value isn't allowed for input or output. The output must be uniform, without chunks of digits grouped together.

Sandbox: Infinite list I/O is hard. Any suggestions?

• "Your goal is to output this infinite list" - can you clarify that it's by taking later elements from the lists that get later and later in the input list - I had to read this several times to understand that. Also, while I don't think there's any getting around the infinite input requirement, perhaps you could change the output to standard sequence rules to make it more flexible? – pxeger Mar 27 at 18:04
• Is the first list guaranteed to be one element long? Or can it be any length? Can it (and any subsequent lists) be empty? – pxeger Mar 27 at 18:09
• You should probably specify the intermediate output/s needs to be as soon as it's available from the input infinite lists, or at least in finite time, so noone can submit tail -1 – pxeger Mar 27 at 18:21

• Yay, a lisp challenge! Does each 'a' mean a car and each 'd' a cdr? – user Mar 24 at 21:56
• @OriginalOriginalOriginalVI yeah, but I'm to lazy to have written a description in english so far. I guess I'll get to it eventually :P – Wezl Mar 24 at 21:58
• Fortunately the common lisp hyperspec already describes the bulk of it well. – Wezl Mar 24 at 22:22
• You might want to make the reference implementation a link to TIO (unless it doesn't work on TIO, of course) – user Mar 24 at 22:23
• @OriginalOriginalOriginalVI Why? (I can't access TIO anyway) – Wezl Mar 24 at 22:25
• Meh, I just don't like those code snippets, and it makes it easier to pull out of the question, modify the input, and stuff. These code snippets sometimes break for me. If you can't access TIO, though, it doesn't matter, of course. – user Mar 24 at 22:26
• posted – Wezl Mar 25 at 15:04
• I've edited this down to a stub now that it's been posted – caird coinheringaahing Mar 28 at 14:01

# Reverse Zip Bomb

Posted to main (2021-03-29)

• Does the compression have to be lossless? – water_ghosts Mar 27 at 1:04
• Is the “common compression algorithm” defined by the spec or the implementation? If I find a gzip implementation with a bug that produces unbounded output, is that a valid solution? And if it’s not valid, then if I use my computer’s built-in gzip, do I have to verify that it complies with the spec? – water_ghosts Mar 27 at 1:29
• @water_ghosts It depends. I think anything like that would be handled on a case by case basis. I'd expect bugs in the (official or widely used) implementations of common compression algorithms to be quite rare. The compression doesn't have to be lossless, within what's reasonable (JPEG would be allowed, for example) – Redwolf Programs Mar 27 at 1:54
• "common compression algorithm" isn't clear enough IMO. You should either allow any and all compression algorithms (so long as an implementation exists, perhaps before the challenge) or specify an exact list people can choose from – caird coinheringaahing Mar 27 at 16:15
• I think well-known enough to have a Wikipedia article (or part of one) written about them is clear (I'll reword it to make it clear that there should actually be an article for it), any specific things you'd recommend changing about it? – Redwolf Programs Mar 27 at 16:56
• Certainly interesting, but there doesn't seem to be any codewriting involved. – Alex bries Mar 27 at 17:09
• @Alexbries I think it'd be allowed, since it's fairly similar to "find the password" type CnRs. IMO, although you're not writing Python or JS, you could still sort of consider it "writing in gzip" or "writing in png" since you're trying to find an input that gets "compiled" into a larger output. – Redwolf Programs Mar 27 at 17:16
• @Alexbries Answers don't always have to be code – caird coinheringaahing Mar 27 at 17:25
• I think specifying about a Wikipedia page should be enough @RedwolfPrograms – caird coinheringaahing Mar 27 at 17:26
• It's unclear what kind of expressions we have to deal with, but it looks good, and interesting . E.g. do we have to handle expr |> function(with_one_parameter)? – Wezl Mar 25 at 15:27
• @Wezl I was thinking the expression could be anything with printable non-whitespace ASCII but I realize now that could be problematic. I'll change it to be more restrictive. – 79037662 Mar 25 at 15:30
• @Wezl I specified that you may assume all functions will take only one parameter, so you do not have to handle expr |> function(with_one_parameter). – 79037662 Mar 25 at 15:39
• Why do some piped expressions have () and some do not? Are we meant to support both of these? – A username Mar 26 at 4:45
• @Ausername It's to demonstrate that both are valid, but as I state in the rules you need only support one convention. – 79037662 Mar 26 at 13:17

# What's my TIO uniqueness?

• Oops, didn't read that – user Mar 23 at 20:59
• Maybe you could say "undefined" instead of 0 in the sentence "The TIO uniqueness of a language for which this is impossible is 0". Also, do you want submissions to store all 680 language names in the code? – Bubbler Mar 24 at 23:58
• @Bubbler Changed to undefined, it fits better. Yes, submissions should have some way of storing the names, be it in an external file or in the program itself etc. – caird coinheringaahing Mar 25 at 0:02
• @FryAmTheEggman Given that there are 680, I think it may be impractical to include the full list in the question, which is why I linked to this gist with all languages and their outputs – caird coinheringaahing Mar 25 at 0:20
• Ah, sorry, I missed the link. – FryAmTheEggman Mar 25 at 3:44
• "subsequence" tag? Why? – tsh Mar 29 at 8:58
• @tsh Because the TIO uniqueness depends on the shortest substring that isn't common with any other language – caird coinheringaahing Mar 29 at 18:49
• but substring is not subsequence – tsh Mar 30 at 0:32
• @tsh No, but [substring] isn't a tag, and [subsequence] is the best alternative – caird coinheringaahing Mar 30 at 21:37

I want to avoid responding to illegal or spoofed addresses. One type that's easy to detect is an address that should not exist on a packet received by my router: a special-use address.

## Challenge

Given an IPv4 32-bit address, identify whether it is valid general-use address.

## Challenge rules

• Special-use addresses, as defined by the Internet Engineering Task Force, are considered invalid.
• Special-use addresses are listed at https://en.wikipedia.org/wiki/IPv4#Special-use_addresses. A copy of the list (omitting explanatory columns) is below.
• Input will be in the dot-decimal notation, consisting of four positive decimal numbers (called "octets") each in the range 0–255 separated by periods (e.g., 169.254.0.31). Each octet represents an 8-bit segment of the address.
• Output must indicate true or false, using any two indicators of your choice for true and false.

## General rules:

• This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.

## Test cases:

• 192.0.0.254 false
• 192.0.1.254 true
• 0.255.0.0 false
• 128.2.3.82 true
• 253.8.22.37 false
• 203.0.114.201 true

0.0.0.0/8 0.0.0.0–0.255.255.255
10.0.0.0/8 10.0.0.0–10.255.255.255
100.64.0.0/10 100.64.0.0–100.127.255.255
127.0.0.0/8 127.0.0.0–127.255.255.255
169.254.0.0/16 169.254.0.0–169.254.255.255
172.16.0.0/12 172.16.0.0–172.31.255.255
192.0.0.0/24 192.0.0.0–192.0.0.255
192.0.2.0/24 192.0.2.0–192.0.2.255
192.88.99.0/24 192.88.99.0–192.88.99.255
192.168.0.0/16 192.168.0.0–192.168.255.255
198.18.0.0/15 198.18.0.0–198.19.255.255
198.51.100.0/24 198.51.100.0–198.51.100.255
203.0.113.0/24 203.0.113.0–203.0.113.255
224.0.0.0/4 224.0.0.0–239.255.255.255
240.0.0.0/4 240.0.0.0–255.255.255.254
255.255.255.255/32 255.255.255.255

Note on address blocks. This is a shortcut method of listing an address range, called CIDR notation. The notation is four octets followed by a slash and a decimal number. The decimal number is the count of leading 1 bits in the network mask, and indicates how many leading bits in the underlying 32-bit address range are specified as fixed. For example, a mask of 24 indicates that only the last 8 bits of the address range vary. Thus writing 192.0.2.0/24 indicates that only the last octet varies. The range for 192.0.2.0/24 is 192.0.2.0–192.0.2.255.

New contributor
rsjaffe is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• You should generally include the definition of things like this directly in the challenge rather than just linking to a Wikipedia article on it, so people don't have to go to an external site – pxeger Apr 8 at 8:42
• I think it would be clearer if you used boolean true/false for "is this valid", rather than "invalid" vs "valid". You might also want to change classification to decision-problem – pxeger Apr 8 at 8:46
• @pxeger Thanks. Included both suggestions. – rsjaffe Apr 8 at 15:55
• Is this means the input should always be a string / list of characters? May I take input as an array of 4 integers / a 32 bit unsigned integer / a built-in type for IP address (if there is one)? – tsh 8 hours ago