# Sandbox for Proposed Challenges

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

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
• 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 needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

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!

# 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

# 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 – Wzl Mar 24 at 21:58
• Fortunately the common lisp hyperspec already describes the bulk of it well. – Wzl 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) – Wzl 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 – Wzl 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
• 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)? – Wzl 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

• 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 Apr 13 at 3:57

## Remove first encountered elements from a second list

• While this comes from an SE question, having two arrays seems a bit odd. A more standard task is simply to remove the first occurrence from the single array. (Though, it may be a duplicate then) – Nathan Merrill Aug 17 '16 at 18:33
• @NathanMerrill I thought of limiting it to just one array, but in my opinion this way is more challenging. – pajonk Aug 17 '16 at 19:01
• I agree, it does increase the difficulty of the challenge. – Nathan Merrill Aug 17 '16 at 19:04
• The separator between the elements of the list needs to be distinct from the separator between lists -- it just means that the two output lists should be distinguishable (and not clumped into a single list, for example), right? The current wording doesn't make much sense if we can return two lists from a function. – Bubbler Apr 12 at 23:07
• @Bubbler, yes, that's right - I'll change it. Thanks. – pajonk Apr 13 at 5:06
• I suggest using standard JSON in your examples, e.g. [2,3,3,5,5,4,3,7,1] – Adám Apr 13 at 6:58
• I think removing elements from L2 is unnecessary. The essence of the challenge is to remove elements from L1 based on the first occurrence of each unique element in L2. – Adám Apr 13 at 7:00
• Thanks @Adám for the comments. You're right - I edited accordingly. – pajonk Apr 13 at 19:41

# Interpret control characters like a terminal

• As "your program does not need to interpret backslash escape sequences - the input will contain the literal control codes themselves.", I'd suggest actually including the characters in the test cases, or at least including a TIO link (or pastebin etc.) with the literal characters – caird coinheringaahing Apr 12 at 13:14
• @cairdcoinheringaahing \r isn't really usable on the web because it will be converted to a newline, and most languages have their own literal syntax for entering those characters anyway, so I think it wouldn't really help – pxeger Apr 12 at 13:18
• Suggest a aaaaaaa\b\b\b\t case, do TAB fill them space? – l4m2 Apr 15 at 4:17
• @l4m2 thanks - that helped me discover some subtle bugs in my reference implementation too – pxeger Apr 15 at 9:01

# A Self-Referential Sentence

## The Story

One day, you decide that you want a sentence that tells you where in the sentence the letter T occurs (excluding whitespace and punctuation). Out of curiosity, you try to make one. Messing around a little you get

T is the first, fourth, eleventh, sixteenth, twenty-fourth, ....

Oh dear, this sentence appears to run forever. But you now think you have an interesting number sequence, so you slap it into the OEIS search bar and lo and behold you find sequence A005224, Aronson's sequence. And better yet, an interesting code-golf problem that no appears to have posed before!

Your task is to write a program that takes in a single positive integer, n, as input and gives the position of the n-th "t" in the above sentence (indexing begins at 1 for the sake of this problem). For example, an input of 1 should return 1, while 2 should return 4. The input number will not exceed 4 decimal digits in length (i.e. the maximum input is 9999)

As always, the shortest code in bytes wins, and standard loopholes apply.

## The Meta

Ok, so I have a couple of questions, since this my first sandbox post.

1. What can I do to flesh out this problem? This seems short, especially for a CGSE prompt. Should I somehow flesh out the heading fluff? Or should I add something more to the task itself?
2. I was pretty thorough in my search of the sandbox and main site for similar problems, but I could always have missed something, so please let me know if this is a duplicate.
3. Is the 4 digit input limit reasonable? Should I raise it or lower it? Remove it entirely? Since I'm not providing a file with ordinal strings, it seems like having a restriction on the size of the input is quite important.
4. Finally, please let me know if there's any other glaring problems in this prompt, this is both a first draft, and my first attempt at a code-golf prompt (since high-school).
• Nice first challenge! I'd suggest following the standard sequence I/O rules and allowing programs to output either the first $n$, the $n$th term or all terms. Additionally, forcing 1-indexing (for the sequence) doesn't improve the challenge any more than allowing either 0 or 1 indexing. I cannot find any challenge that could be a dupe through some searching, so this looks to be 100% original. Finally, I'd recommend including either test cases or the first 10 or so terms in the challenge body – caird coinheringaahing Apr 24 at 16:21
• @cairdcoinheringaahing 1-indexing is fundamental to the recursive definition of this sequence, as “T is the zeroth, third, tenth, twelfth, seventeenth, twentieth, …” is quite a different sequence (not just off by one). – Anders Kaseorg Apr 25 at 18:25
• @AndersKaseorg I meant 0 indexing in the input, not in the position of the T (e.g. n = 0 would output 1, n = 1 would output 4, etc.) – caird coinheringaahing Apr 25 at 18:27

# diddly darn posted

• Tag chess? – pxeger Apr 12 at 6:43
• My god, this is amazing. I can't wait to see the full version! – StackMeter Apr 12 at 9:48
• It's not clear to me what should be output in the non-deterministic cases. Do we have to output all possibilites? – kops Apr 22 at 23:35
• Addtionally, what do you want the result of this to be: ,v, \n >,A \n ^<B (pastebin; is multline code possible in a comment?) Rules as written I think it's a tie since the center cell is reached twice but it's not clear this is desirable. – kops Apr 22 at 23:37
• @kops it's okay for the board to result in a tie. – lyxal Apr 22 at 23:43
• And the point is to output the result of the board, which may not be deterministic – lyxal Apr 22 at 23:43
• So each possibility has to be output with the correct probability in the non-deterministic cases? And for the specific board in my second comment, it's very much morally an A victory, not a tie, but the technicality of passing through the same cell going in different directions makes it a tie in these rules which I find a bit weird. – kops Apr 22 at 23:46
• @kops no it is not the probability but the result of running it once. That result may vary. And even though that may seem like it should be a win for A, it could be the result of some clever play from B to trick A into thinking they've won – lyxal Apr 22 at 23:50
• @Lyxal I didn't mean to say the probability itself should be output, but that for each possibility, the probability of that possibility being output has to be correct? – kops Apr 22 at 23:56
• @kops you only ever output one result - the winner of the game when evaluated. Because there are commands that change the direction, it can be impossible to 100% tell who wins. I was simply pointing out that there is more than one possible output for such boards. – lyxal Apr 22 at 23:59

# CDGLF:TMN2APL

## Meta questions:

• Is this a duplicate? (I've looked and there are several challenges with operator precedence, but there are large differences such as floor/ceiling and the output format)
• How can I objectively define "equivalent expressions"? Should I write a reference interpreter or answer?
• Would it be more interesting going the other way?
• Should answers be required to reject invalid input? Seems not
• Should I I've replaced the unicode operators ×÷⌈⌉⌊⌋ with ascii symbols */{}[].
• Is the exponentiation operator necessary? (It might just make the challenge more cumbersome because of its different associativity)
• It was previously APL2TMN. I'm changing it to TMN2APL to make it more interesting. – Wzl Apr 22 at 14:42
• TMN's +-×÷ are left-associative, but in APL everything is right-associative. The equivalent of TMN 3-5÷2+1 in APL is (3-5÷2)+1; APL 3-(5÷2)+1 is 3-((5÷2)+1). – Bubbler Apr 22 at 23:41
• Thanks, I completely forgot about associativity. I don't think my grammar handles it, however, so I'm not sure exactly how to resolve this. – Wzl Apr 22 at 23:44
• Also, I suggest to state the output format (APL) in the same way as you did for the input format (TMN), and state the precedence and associativity (for both TMN and APL) separately in plain English for those who are not familiar with parser grammars. And I think input validation is unnecessary here. – Bubbler Apr 22 at 23:52
• I think the Unicode operators definitely should be replaced with ASCII, because otherwise it's 10 bytes used on every answer. This would require you to remove or change the output syntax of exponentiation, but I don't really feel like it adds much tbh. – pxeger Apr 24 at 15:57
• @pxeger I've changed it, and I agree. – Wzl Apr 25 at 0:53

# Distance between vowels

## Objective

Given two vowels represented in single IPA characters, calculate the distance between them.

## Vowels

Vowels are characterized by three factors: Height, backness, and roundedness. Here, all vowels have the three characteristics as integers.

### Unrounded vowels (z = 0)

    x=0       x=1       x=2       x=3       x=4
y=6 i(U+0069)           ɨ(U+0268)           ɯ(U+026F)
y=5           ɪ(U+026A)           ʊ(U+028A)
y=4 e(U+0065)           ɘ(U+0258)           ɤ(U+0264)
y=3                     ə(U+0259)
y=2 ɛ(U+025B)           ɜ(U+025C)           ʌ(U+028C)
y=1 æ(U+00E6)           ɐ(U+0250)
y=0 a(U+0061)                               ɑ(U+0251)


(I know, Wikipedia states ʊ as rounded, but official IPA doesn't specify the roundedness of ʊ. It will be considered unrounded for this challenge.)

### Rounded vowels (z = 1)

    x=0       x=1       x=2       x=3       x=4
y=6 y(U+0079)           ʉ(U+0289)           u(U+0075)
y=5           ʏ(U+028F)
y=4 ø(U+00F8)           ɵ(U+0275)           o(U+006F)
y=3
y=2 œ(U+0153)           ɞ(U+025E)           ɔ(U+0254)
y=1
y=0 ɶ(U+0276)                               ɒ(U+0252)


## Metric

Your metric $$\d\$$ shall fit the usual definition of metric:

• $$\d(v,w)=0\$$ if and only if $$\v=w\$$

• For all $$\v\$$ and $$\w\$$, $$\d(v,w)=d(w,v)\$$

• For all $$\v\$$, $$\w\$$ and $$\x\$$, $$\d(v,x)≤d(v,w)+d(w,x)\$$

As an additional constraint, the norm $$\\Vert\cdot\Vert\$$ induced by $$\d\$$ shall satisfy:

• For all $$\x≠0\$$, $$\y\$$ and $$\z\$$, $$\\Vert(0,y,z)\Vert<\Vert(x,y,z)\Vert\$$

• For all $$\x≠0\$$, $$\y\$$, $$\z\$$ and $$\k>1\$$, $$\\Vert(x,y,z)\Vert<\Vert(kx,y,z)\Vert\$$

• Analogous rules for the y-axis and z-axis

All of these apply only to the vowels above. All other inputs fall in don't care situation.

## Rules

• Input format is flexible. It may be two chararacters, or a single string containing two charcters. In any case, every input that doesn't fit in your format falls in don't care situation.

• Output format is also flexible.

# Fastest untyped lambda calculus evaluator fastest-codefunctional-programminglambda-calculusinterpreter

## Challenge

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

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

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


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

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

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

Good starting points include this PEPM '17 paper and my Haskell implementation which was modified from the paper's algorithm to actually return the normal form.

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

## Meta

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

# Backromymiser code-golfstringsubsequence

## Background

A backronym is an acronym that was formed from an existing word. For example, spam is actually named after the canned meat product as used in the Monty Python sketch, but can be interpreted as "stupid pointless annoying mail".

They can also be constructed using a more facetiously, such as "What Horse shYte" (that chat conversation was the inspiration for this challenge)

## Challenge

Given a sentence a and a word b, capitalise the correct letters of a such that they spell out b.

You may assume a will always consist only of lowercase ASCII letters and space, and b will always consist only of uppercase ASCII. Alternatively, you may assume b will always be lowercase, but this must be consistent.

You do not need to handle empty inputs or inputs that have no possible backronymisation.

You should always move left-to-right and capitalise the first occurence of each letter.

## Example

a = "im never gonna give you up", b = "VIP"

• Working through the letters of VIP:
• v: find the first instance of v in im never gonna give you up and upper-case it -> im neVer gonna give you up
• i: find and upper-case the next instance of i (after the already found v) -> im neVer gonna gIve you up
• p: do the same with p -> im neVer gonna gIve you uP

## Test cases

a                             b        output
=====================================================================
"im never gonna give you up"  "VIP"    "im neVer gonna gIve you uP"
"dbdacbec"                    "ABC"    dbdAcBeC
"x"                           "X"      "X"
"xxxx"                        "X"      "Xxxx"
"what horse shyte"            "WHY"    "WHat horse shYte"
"facdbbbd"                    "ABC"    (impossible; does not need to be handled)


# Meta

• Is this a duplicate? (related, related)
• Is this clear enough?
• Any other feedback?
• I quite like this challenge, but why are there four possible outputs for xxxx, X? Was it not specified that the first occurrence should be capitalized and only that one? – ophact May 27 at 19:31
• I'll change it so that it's always the first option. – pxeger May 28 at 7:35

# Generate a UK number platecode-golfstringdaterandom

• I'd suggest saying AANNXXX or something like that instead of AA12XXX so it's clear the age identifier isn't always 12 (that's clarified later, but still). – user Apr 28 at 18:12
• Just a note: the last 3 characters can't be either Q or I – caird coinheringaahing May 1 at 18:13
• @cairdcoinheringaahing I thought that too, but I found no mention of it in the government document so I kept it as the whole alphabet. shrug – pxeger May 1 at 19:37
• There's a Q in the alphabet for the first letter, but then you say the alphabet, minus IJQTUXZ. – Arnauld May 5 at 18:13
• @Arnauld yep, that shouldn't be there. Too much muscle memory from typing the alphabet correctly I guess :þ – pxeger May 5 at 19:15

# Worst time complexity for an irreducible program

Time complexity, typically represented in Big O notation, represents how long a program will typically take to run given some input(s), ignoring constants.

Your task is to do one of the following things, with the worst time complexity possible:

• Sort an array of integers
• Find duplicates in an array
• Find longest strictly increasing slice of an array of integers

All of the tasks involve taking one input, an array of items, in any reasonable format, and returning an array. If your language supports mutable array data types, this is an allowed output format. Assume all items in the arrays will be (not necessarily positive) integers.

If you choose sorting: You may choose to sort the array by minimum or maximum.

If you choose listing duplicates: You may include a duplicate item any number of times in the output; [1, 2, 2, 3, 4] could result in [2, 4], [2, 2, 4], or even [2, 4, 4, 4].

If you choose longest strictly increasing slice: Duplicate items do not count as increasing, so [1, 2, 2, 4] is not strictly increasing. The items do not have to increase by a steady amount; [-1, 4, 14, 16, 17] is strictly increasing.

Rules:

Your program must be irreducible. This means removing any slice of the program, other than the whole thing (or nothing), will cause it to no longer perform the required task. Your program should terminate in a finite amount of time. You can assume your program will never run out of memory, and it does not have to terminate before the heat death of the universe.

This is a . The winner will be based on the average time complexity, with slower being better, followed by the minimum and then maximum for ties.

• Unfortunately, this answer broke all "irreducible" challenges. You can execute (almost) arbitrary code unrelated to the task without breaking the "irreducible" requirement. – Bubbler Apr 22 at 0:16
• @Bubbler Hmm, and I don't think irreducible is a sensible requirement for this either. It definitely makes more sense with bytes than time, along with pristine. I'll have to think about some creative limitations. Maybe unique bytes only? – Redwolf Programs Apr 22 at 0:22

# Non-quining infinite printer

Seems like the title could be better but I'm not sure what to do instead

I have heard that a monkey typing random keys on a typewriter, given infinite time, will eventually type out the entire works of Shakespeare, and in fact type out every possible string of characters of any length. This sounds to me like the basis for a profitable business venture in publishing. Unfortunately, however, as a result of previous failed business ventures, I am legally barred from possessing either monkeys or typewriters, so I'll instead need a program. I want this program to provably generate every possible string of characters, assuming infinite time and memory. Repetition is fine, as long as everything is outputted at least once. There's a catch, though. I imagine once my business gets off the ground and people realize the potential profits, they might want to get their hands on my program. The trouble is that since I'm outputting every possible string of text, in theory I'll eventually end up outputting the program itself, leaving it open to be stolen. To prevent this, I want the program never to output its own source code. It should still output every other possible string, just not itself (or, obviously, any strings which it is a substring of). Because my funds are currently very tight, I can't afford to pay for more bytes than are necessary, so I'm seeking the shortest possible program that does the job (This is a code-golf challenge, shortest answer in bytes wins). Is it communicated well enough what this challenge is asking for? Should I add a TL;DR and/or a more technical explanation of what's being looked for?

• I've had enough run-ins with the law in previous ventures, I'd like this one to go smoothly. So no abusing loopholes in the program, please.
• Given that this program is my financial plan for the next infinity years, I'd like some reassurance that it actually does what it's supposed to. Please provide at least a brief explanation of why your code works, since it can't exactly be tested.
• Any character encoding is fine, please specify though. The exception is that your source code must be printable in the encoding you use. Is this a reasonable way to handle this that is fair to all languages?
• No reading your own source, because that makes quine-related holes uncool, and uncoolness does not fit with my businesses' brand persona.
New contributor
je je is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• How are the strings in the output separated? Some previous challenges about "print all possible strings" were closed as unclear because of this. – Bubbler Jun 7 at 1:06
• @Bubbler The strings don't have to be separated. What I mean is that every string should be a substring of the "main" output if that makes sense. Put another way, running a regex match on the output for any string of characters (other than the source) should return at least one result. Would adding something to that effect clear up that confusion? – je je Jun 7 at 1:13
• It should still output every other possible string, just not itself (or, obviously, any strings which it is a substring of) Okay, the task makes sense now. I think you'll need to add that information somewhere before the sentence I quoted. Now I wonder if the task is actually possible... – Bubbler Jun 7 at 1:39
• @Bubbler Sure, it's possible. One approach is to store the program's source in a string, and then run some sort of code that generates every possible string, checking after each generation whether the generated string contains the source string, and only printing if it doesn't. There might be some trouble in making sure the source isn't present in a combination of two consecutively generated strings (i.e. if the source code is AB, then outputting XA and BX consecutively is an issue), but a simple solution to that is to insert a character not present in the source between each pair. – je je Jun 7 at 8:02
• Here's an implementation in Python tio.run/… – je je Jun 7 at 8:03

# Implement Fix2 code-golffunctional-programminglambda-calculus

## Background

The fixed-point combinator $$\\textsf{fix}\$$ is a higher-order function that computes the fixed point of the given function.

$$\textsf{fix}\ f = f\ (\textsf{fix}\ f)$$

In terms of programming, it is used to implement recursion in lambda calculus, where the function body does not normally have access to its own name. A common example is recursive factorial (written in Haskell-like syntax). Observe how the use of fix "unknots" the recursive call of fac.

fix f = f (fix f)
fac = fix facFix where
facFix fac' n = if (isZero n) then 1 else (mult n (fac' (pred n)))
-- which is equivalent to the following recursive function:
fac n = if (isZero n) then 1 else (mult n (fac (pred n)))


Now, have you ever thought about how you would do the same for mutually recursive functions? This article describes the fully general $$\\textsf{Y}^*\$$ combinator, which takes a list (or equivalent) of unknotted definitions and returns the list of mutually recursive ("knotted") functions. This challenge will focus on a simpler situation with exactly 2 mutually recursive functions; the respective combinator will be called fix2 throughout this challenge.

A common example of mutual recursion is even and odd defined like this:

even n = if n == 0 then true else odd (pred n)
odd n = if n == 0 then false else even (pred n)


The unknotted version of these would look like this (note that mutually recursive definitions should have access to every single function being defined):

evenFix (even, odd) n = if n == 0 then true else odd (pred n)
oddFix (even, odd) n = if n == 0 then false else even (pred n)


Then we can knot the two definitions using fixPoly to get the recursive even and odd back:

fix2 (a, b) = fix (\self -> (a self, b self))
where fix f = f (fix f)
let (even, odd) = fix2 (evenFix, oddFix)


## Challenge

Implement fix2. To be more precise, write a function or program that takes two unknotted black-box functions fFix and gFix and a non-negative integer n, and outputs the two results (f(n), g(n)) of the knotted equivalents f and g. Each f and g is guaranteed to be a function that takes and returns a non-negative integer.

You can choose how fFix and gFix (and also fix2) will take their arguments (curried or not). It is recommended to demonstrate how the even-odd example works with your implementation of fix2.

Standard rules apply. The shortest code in bytes wins.

# I'm Lazy: Close my Parens

• It's clear what to do with ], but what does [ represent? Is it the same as just (? – DJMcMayhem Jun 1 at 22:00
• Why is ([(] invalid but [(] is not? Will there ever be multiple ] in a row? – DJMcMayhem Jun 1 at 22:05
• @DJMcMayhem ([(] is invalid because it is the same as [(] but with an unmatched ( at the beginning since the ] only closes the [. There may be multiple ] in a row. – Wzl Jun 1 at 22:08
• So basically ] matches as many open parens as possible until it hits a [ at which point it has to stop? – DJMcMayhem Jun 1 at 22:10
• @DJMcMayhem yes. Should I add that to the question for clarity? – Wzl Jun 1 at 22:12
• Yes, I think that would help. – DJMcMayhem Jun 1 at 22:17
• Not sure if lisp tag is appropriate, because the challenge itself doesn't have to do with lisp. – qwr Jun 2 at 14:43
• Tag: balanced-string? – pxeger Jun 3 at 10:47
• @pxeger nice tag-finding skills :) I'll add that. – Wzl Jun 3 at 13:04
• @qwr How else do I get the tag badge :P – Wzl Jun 3 at 13:07

# Write a C++ demangler

If you have ever looked at an objdump of a C++ program, you have likely seen something like this:

_ZN3foo3bar3bazI6sampleEE3quxvi3foo


This is a C++ mangled symbol, which encodes the namespaces, classes, and function/template arguments, using the Itanium ABI.

Specifically, it is for the following function:

void foo::bar::baz<sample>::qux(int, foo);


Your job is to demangle a C++ symbol in a dramatically simplified version of the Itanium ABI. (That is incompatible with c++filt or __cxa_demangle(), so don't try it).

Everything will be plain identifiers (so no int, void, or "special" identifiers like std::), no const/pointers, no return type encoding, no reuse of template args, etc.

Specifically, these are the syntax rules:

• All mangled symbols start with _Z. Any symbol that doesn't start with _Z is to be printed as-is.
• Everything is case sensitive.
• All identifiers are encoded as <length><name>, where <length> is the positive length of <name> in base 10, so foo is encoded as 3foo, sample is encoded as 6sample, etc.
• Each symbol is one base identifier, optionally followed by a list of function parameters.
• Each identifier can be prefixed with a namespace, or suffixed with a template.
• Namespaces are encoded as a sequence of 1 or more identifiers between an N and an E. Each identifier is printed as the identifier, followed by ::. So N3fooE is foo::, and N3foo3barE is foo::bar::.
• Templates are encoded similar to namespaces, only using I..E instead of N..E. They are printed as a comma separated list of identifiers, wrapped in <angle brackets>. These come before :: in a namespace. So I3fooE is <foo>, and I3foo3barE is <foo,bar>.
• These may be nested.
• All identifiers after the base symbol are to be treated as function parameters, and they are to be printed as a comma separated list wrapped in (parentheses). This does not apply to namespaces or template arguments.

So, let's take a simpler example:

_ZN3fooI3barEE3baz3qux
_Z                      Mangle prefix
N          E          Namespace
3foo                   Identifier foo
I    E              Template
3bar                Identifier bar
3baz      Base: Identifier baz
3qux  Parameters: Identifier qux


The result is this:

foo<bar>::baz(qux)


Your function or program will take a string, and the output will either be the demangled symbol or the string verbatim, depending on whether the function was a mangled identifier.

You can safely assume each string will only contain numbers, letters, and underscores.

Assume all mangled symbols are valid, standard input/output format, you know the deal.

You can have any amount of whitespace between identifiers, however, empty parameter/template/namespaces and trailing commas are not allowed.

This is , so shortest program in bytes wins.

### Test cases:

_Z1x -> x
_Z3foo3bar -> foo(bar)
_ZN3fooE3bar -> foo::bar
_Z3FOOI3barE -> FOO<bar>
_Z3foo3bar3baz -> foo(bar,baz)
_Z3fooI3barE3baz -> foo<bar>(baz)
_Z3fooI3bar3bazE -> foo<bar,baz>
_ZN3fooE3bar3baZ -> foo::bar(baZ)
_ZN3fooI3barEE3baz3qux -> foo<bar>::baz(qux)
_ZN9CPlusPlusI2isEE11soooooooooo5great -> CPlusPlus<is>::soooooooooo(great)
_ZN2soI1II4herdEE1UI4liekEE9templates -> so<I<herd>>::U<liek>::templates
_Z12identifier12 -> identifier12
_Z2_Z -> _Z
_ZN1a1b1c1d1e1f1g1hE1i -> a::b::c::d::e::f::g::h::i
_ZN1a1bI1c1d1eE1fE1gN1hE1iIN1jE1kI1lEEN1m1nE1o -> a::b<c,d,e>::f::g(h::i<j::k<l>>,m::n::o)
_Z14N3redE7herring1x7foo_bar -> N3redE7herring(x,foo_bar)
foo -> foo
1x -> 1x
NZ3foo -> NZ3foo
_S14N3redE7herring1x7foo_bar -> _S14N3redE7herring1x7foo_bar


# Meta questions

• Is the "if it doesn't start with _Z" ok, or should I remove it?
• Are these rules easy enough to understand?
• Is _ZN3foo3barE3baz -> foo(bar)::baz valid? – tsh Jun 7 at 8:39
• That would be foo::bar::baz. The base identifier is baz, and it is prefixed with the namespace foo::bar. – EasyasPi Jun 7 at 14:27
• Won't foo::bar::baz be _ZN3fooEN3barE3baz or _ZNN3fooE3barEbaz? – tsh Jun 8 at 6:14
• No, nested namespaces are placed together without a separator. – EasyasPi Jun 8 at 12:39

# Remove All Comments From Smalltalk for Code Golf

## Tags?

• May string contains \" as escaped characters? – tsh May 31 at 8:05
• I might suggest changing  to a different character, simply because it's hard to use in markdown – pxeger May 31 at 8:43
• @tsh no ;) – Wzl May 31 at 16:20
• Suggest testcases with multiple groups of strings, multiple groups of comments, and their combination: "a"b"c", 'a'b'c', a'"'b'"'c, a"'"b"'"c – tsh Jun 1 at 6:19
• I'm not sure if this'd be very interesting, since it's just a matter of replacing /"[^"]"/ if I'm correct. – user Jun 10 at 1:03
• @user I think there's a misunderstanding. The program must also not remove comments in strings, such as 'a"b"c' is not changed – Wzl Jun 10 at 1:23

# But, Is It Art?

• I think it is clear, but the second example of "is not equivalent to" is a little unnecessary in my opinion. – Alex bries Jun 2 at 10:03

# Count my sheep code-golfmatrix

Given a boolean matrix representing my grass field, sheep length $$\n\$$ and wool thickness $$\k\$$, you will have to count my sheep.

A sheep is a single independent unbroken line of sheep length $$\n\$$ and thickness $$\k\$$.

#|##|# | #
#|  | #|#


are all valid sheep for $$\n=2,k=1.\$$

##|###|##  |  ##
##|###| ## | ##
##|   |  ##|##


are all valid sheep for $$\n=3,k=2.\$$

The diagonal sheep must be composed of horizontal lines of length k.

you are to count occurrences of valid sheep across a given grid.

Sheep will not intersect. you will be guaranteed that $$\n,k≥1.\$$

so for $$\n=2,k=1\$$:

##
#
##  #


should give 3. Sheep may be right next to each other, and smaller animals may be present in the grid. You should get the max number of sheep that can be recognized from the grid.

## Test Cases

n=3, k=1

#      #
# ### #
#
#
#
#


Output: 3

n=1,k=4

####
####

#
#
####


Output: 3

n=3, k=1

#  #
##
###
#
#


Output: 2

n=2, k=5

###
###
###
###
###
###


Output: 1

• You might want to clarify how the diagonals work, although that's a small thing and this looks good overall I think – Redwolf Programs May 9 at 3:58
• May 1-thick diagonal sheep intersect? – Unrelated String May 28 at 7:54
• Sheep should not intersect. I'll make that clear. – Razetime May 28 at 7:58

## Play Simple 2-Dimensional Minecraft

Recently I found this video of "HansLemurson" showing a computer that was built in minecraft, which runs minecraft. He is playing minecraft on a computer that was built in minecraft that is running on his computer. To be specific, it is a two dimensional version with an 8x8 grid of cells. There is gravity, block placement, and even jumping. It is worth noting that the computer is single purpose. The same person has built programmable computers, but making them single purpose allows the computer to be much smaller.

## Details

The minecraft world is an 8x8 grid (one horizontal and one vertical dimension). The grid is comprised of either Xs (representing blocks) or empty spaces. The player is an X that is blinking on and off about once every second.

There are two modes in the game, controlled by a toggle switch. The first mode is movement. This is controlled by a WASD-like button arrangement. If the player chooses to move left/right/down, the computer checks to see if the space immediately in that direction is empty. If so, then the player moves into that space.

If the player chooses to move up, then the computer checks that the block underneath the player is solid. If so, then the player moves upward two units. Notice that this can propel the player into a solid block. If this happens, the player is obscured by the solid block, but can still move to an empty block next to him. When the player is inside on a solid block, the game continues as if the block isn't there, although the block is still there once the player leaves it.

After each move, the player falls down one unit if there is empty space there. This simulates gravity. This is also why moving up moves up two units, so that the gravity makes a net movement of up one unit. Gravity does not cause the player to fall all of the way to the ground, just one unit.

The second mode is block placement. In this mode, the same exact WASD buttons are used. Instead of moving the player, they toggle the state of the block in that direction. If the player presses "left" and there is a block there, then the block is destroyed. If there is not a block there, then a block is placed. Again after this move, the player is again subject to gravity. The blocks are not subject to falling.

Toggling the toggle switch does not count as a move, and does not invoke gravity.

The game board is a torus, so all actions (movement, block creation) can wrap around the board. The board does not scroll with the player. The player moves, and the blocks stay in the same place.

## The challenge

You challenge is to write the shortest program that simulates this game. Your program should display and update the map correctly (with Xs as blocks, and with the blinking player). It should accept input from a button that toggles the state and four buttons for movement and actions. This is code golf.

There are imaginary bonus points for adding more features (block types, game size, etc) to your game.

## Suggestions?

• With more complicated challenges I find that it helps to do a reference implementation so that you have a very concrete idea of how much work is involved. Aside from that, I like it. – dmckee --- ex-moderator kitten Jun 3 '12 at 20:11
• Is the blink rate selected to fit with the ANSI escape sequence? Either way I would explicitly allow that, because it's the obvious way to do it on compatible terminals. – Peter Taylor Jun 5 '12 at 7:14
• The blink rate wasn't selected to be anything specific. I think that I will broaden the restriction. Maybe any blink rate between 3 blinks per second to 1 blink every 2 seconds. – PhiNotPi Jun 5 '12 at 20:21
• @programmer5000 No, for two main reasons: First, challenges can go extended periods of time in the sandbox before they are posted and/or adopted. In the past I've posted challenges after not touching them for 4 years. Second, deleting this answer will not reduce lag, as deleted answers are still present, simply not visible. Users with sufficient rep will see all 4040 answers in the sandbox, and you will too once you earn the "view deleted answers" privilege. – PhiNotPi Apr 13 '17 at 18:15

Overview:

Let's say you've decided to operate your computer using voice recognition software, but unfortunately you did a horrible job researching the various products out there and chose a package that does not recognize numbers as numerals, only words. (i.e. "one" (spoken) == "one" (typed), not "1".) Rather than spend more money to get another option, you decide to make do. Now you want to use the computer's calculator, but this poses a problem, since your machine doesn't know how to add "one plus one".

Objective:

Implement a basic calculator that will read in a string of the written-out equation, perform the correct calculations, then return the result in its text form. Your code should be as short as possible; this is code golf.

Rules/Constraints:

• Input/output will be using your preferred method (STDIN, ARGV, etc.).
• Your calculator must be able to handle input and output within the billions (non-inclusive) -1,000,000,000 < i < 1,000,000,000, but you may expand to more if you wish.
• Decimal values and/or parts must be accepted (0 < i < 1) up to 3 places/digits.
• When calculating answers, proper rounding must be used, so "three point one four one five nine two six" must be returned as "three point one four two".
• Basic calculator functions required:
• "Add"/"Plus"/"Sum"/"And" (+)
• "Subtract"/"Minus"/"Remove" (-)
• "Multiply"/"Times" (*)
• "Divide"/"Divided"/"Divide by"/"Divided by" (/)
• "Raise"/"Exponent"/"Power"/"To the power of" (^)
• "<Base>Root"/"<Base>Radical" (√)
• "Point"/"Decimal" (.)
• "Pi" (π)
• All strings in the list above must be accounted for in your code, capitalization does not matter.
• Numbers may be presented as their full value ("one thousand") or by digit (one zero zero zero).
• Negative numbers may be assigned using "Minus" or "Negative".
• The string "Minus" bust be accounted for as an operator and identifier. (see example)
• "And" is only acceptable as an operator, not as part of a named number.
• "one hundred and one"
• "one hundred one"
• "a" or the absence of a number does not equate to any number; all numbers will be explicitly accounted for in the program input.
• "a hundred" does not equate to "one hundred" and is not a valid input.
• No more than 2 terms will be used.
• "one plus one minus one" will not be implemented.
• If an invalid input is supplied, your function/program should handle the error and exit gracefully with an error description.

Example I/O:

• "one add one" --> "two"
• "five thousand thirty four subtract ten thousand six hundred" --> "negative five thousand five hundred sixty six"
• Alternatively: "five zero three four subtract one zero six zero zero"
• "three root twenty seven" --> "three"
• "ten minus minus ten" --> "twenty"
• Alternatively: "ten subtract negative ten"

## Sandbox Questions:

1. Is this too basic/complicated? (I'm assuming some languages will handle this much more simply than the method I have in my head...)
2. Does the title fit?
3. Are there any constraints that should be added/lifted?
4. Are any more examples needed for clarification?

• @PeterTaylor I had had a similar thought re: operators. ("plus" versus "add"`, etc.) I think it would be more interesting to account for all, but given the wide variety of possible inputs, it may generally be better to limit the options to a specifically defined set (which I have yet to define). – Gaffi Jun 15 '12 at 15:18