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

# Watermelon Contest

You and your buddies are contesting a lone piece of watermelon left in the middle of the table. You decide to make a program to contest for you.

## The Goal

You want to be the last program standing. Then you get the watermelon.

## The Process

Every iteration 1 program will be eliminated from the watermelon contest. This will be decided by a vote among all the remaining programs. This means that your program will have 1 and only 1 vote to spend on the elimination of another program. Whichever program ends up with the most votes is eliminated.

This continues until there are only 1 program left, the winner. This entire process is considered a "round".

After there is a winner, another round will be started with a new piece of watermelon. All programs will be re-entered. When 10,000 rounds have been completed, the program with the most "wins" will be considered the "grand champion". All the rounds combined is considered the "tournament".

## The Catch

Every program will have an opportunity to send a message to all the other programs. The message must be the same for every program. The message is a string, up to 500 bytes long.

You may have a file in which you may store any data you wish from previous rounds. This will persist over the entire tournament.

## The Program

Write a program or function that accepts the following input in any (convenient) form:

[program-name], [message], "The Slug", "hey! don't vote for me!", "Chucknorium II", "a2TEI5ds#" ...


and outputs the name of the program that you vote for:

Chucknorium II


## Notes

• In the likely event of a tie, one of the high scoring programs will be randomly eliminated
• Messages can be anything that doesn't mess with stuff it's not supposed to (e.g. don't mess with the controller or other people's programs). This is what makes the challenge interesting.
• You may not hard-code program names into your program! In other words, numbering the programs randomly at the beginning of the game should produce the same output. Names are just more fun.
• For observation purposes, your program will still be run even if it has been eliminated. It will not, however, have a chance to vote that round.
• This seems to reward out-of-band collaboration (or posting multiple answers, which is effectively the same thing). – Peter Taylor Oct 20 '15 at 8:20
• So the winner between the last two is basically always random (since I assume neither will vote themselves out)? – Geobits Oct 20 '15 at 18:34
• @Geobits correct. Over several thousand rounds this should even out. – Stretch Maniac Oct 20 '15 at 19:49
• I see. There's nothing about how many rounds will be played, so I was wondering about that. If you add this, you should make sure to distinguish turns/rounds or rounds/games, etc. – Geobits Oct 20 '15 at 19:53
• Also, do programs continue to be called once they're "out"? If I want to track who did well each round, for instance, I don't think I can (since I think I only get input up to when I get voted out). – Geobits Oct 20 '15 at 19:56
• Good point. Yes. You just won't be able to vote. I'll change that (and other things) when I get to a computer. – Stretch Maniac Oct 20 '15 at 19:59
• I don't need to hard-code program names: I just need to agree a signature algorithm whereby the combination of name and message means that either the program is a collaborator or they're piggybacking on our agreement. – Peter Taylor Oct 20 '15 at 20:37
• I see... How about a statement that prevents engineering to specific programs? Would that prevent pre-determined collaboration? – Stretch Maniac Oct 20 '15 at 20:42
• Can you clarify the format of the input – user193661 Oct 21 '15 at 9:05
• I hate to be a party pooper, but I honestly don't see the point of this KOTH since it seems to be more politics than programming. Then again I didn't get the cake cutting one either and look at how that one turned out... – Sp3000 Oct 23 '15 at 12:36

# An Assortment of Sorting

Sorting an array of integers in ascending order is one of the most fundamental tasks in programming. Indeed, there are many algorithms which exist to accomplish this. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in many languages. So let's sort some integers!

Rosetta code features lists by sorting algorithm and language of idiomatic approaches to array sorting. However, "most idiomatic" often does not coincide with "shortest." In an effort to make Programming Puzzles and Code Golf the go-to site for code golf, this challenge seeks to compile a catalog of the shortest approach in every language, similar to "Hello, World!", Is this number a prime?, and Golf you a quine for great good!.

Write a full program that, when given an array of strictly positive integers, will print the ascending sorted version of the input array using one particular algorithm that is guaranteed to terminate.

The sorting algorithm used must be specified in the post. Note that bogosort is not allowed as it is not guaranteed to terminate.

### Input

To ensure that the focus of submissions is on the mechanics of the algorithm rather than parsing input, a variable (with a name of your choosing) must be hard-coded in the program. However, the hard-coded value must be easily exchangeable; it may appear in only a single place in the entire program. For scoring purposes, submit the program that corresponds to the one-element array 1.

The elements of the array may be in their decimal representations, unary representations (using a character of your choice), as byte arrays (big or little endian), or as single bytes (if this is your languages largest data type).

All elements of the array can be assumed to be in the range 1 to 255, inclusive. Your program must be able to handle an array of any size from 1 to 255, inclusive.

### Output

Output has to be written to STDOUT or closest alternative.

If possible, the output should consist solely of the sorted array with an optional trailing newline. The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

The output array can be formatted in any reasonable way. For example, [3,2,1] and 3 2 1 would both be fine.

• There should be only one language and algorithm combination per answer. Please submit separate algorithms in the same language or separate languages with the same algorithm as separate posts.

• All submissions are required to feature some kind of explanation of the code.

• Unless entirely unpreventable in your language, nothing should be output to STDERR.

• This is not about finding the language with the shortest approach for sorting, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.

• Submissions in most languages will be scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

The language Piet, for example, will be scored in codels, which is the natural choice for this language.

Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.

• Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program sorts an array, then congratulations for paving the way for a very boring answer.

Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

• If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

• Built-in functions for sorting with a particular algorithm are allowed. This challenge is meant to catalog the shortest possible solution in each language, so if it's shorter to use a built-in in your language, go for it. However, you must provide a link that proves that the built-in uses whichever algorithm you claim.

• The input cannot be assumed to already be sorted.

• Unless they have been overruled earlier, all standard rules apply, including the Loopholes that are forbidden by default.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalog as complete as possible. However, do primarily upvote answers in languages where the author actually had to put effort into golfing the code.

### Catalog

The Stack Snippet at the bottom of this post generates the catalog from the answers as a list of the shortest solutions per language and algorithm, as well as an overall leaderboard.

# Language, Algorithm, N bytes


where N is the size in bytes of your submission. If you improve your score, you can keep old scores in the headline by striking them through. For instance:

# Ruby, Bubble Sort, <s>101</s> <s>96</s> 90 bytes


If you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, Insertion Sort, 43 + 2 (-p flag) = 45 bytes


You can also make the language name a link which will then show up in the snippet:

# [><>](http://esolangs.org/wiki/Fish), Heapsort, 121 bytes


Insert a super awesome snippet here

## Meta questions:

• Should this be restricted to specific set of sorting algorithms or is it okay to allow any deterministic algorithm?

• Is the title okay? The catalog challenges tend to have straightforward, descriptive, searchable titles (with the notable exception of Golf you a quine for great good!). I figured this title is clear enough while still being interesting, but perhaps it's better to opt for something more straightforward.

• At Peter's suggestion I've modified the input method. Arrays are now to be hard-code rather than being taken as input. This eliminates the need for parsing input. If I were to allow a variable to already exist, submissions would be snippets rather than full programs, which I don't want for this.

• Is the closed interval [1, 255] appropriate for bounds on the integer values in the array as well as the length of the array? Is it better to make the array an arbitrary size?

• If you require people to label their answers with the algorithm name, I guarantee you will have at least one argument in comments about the difference between bubble sort, insertion sort, and selection sort. – Peter Taylor Oct 21 '15 at 6:31
• Are extremely inefficient solutions like "Check every possible permutation of the list" allowed, if they are guaranteed to terminate? I don't mind them but they almost don't seem like sorting algorithms :p – Fatalize Oct 21 '15 at 13:44
• @PeterTaylor Do you think it would be best to scrap the entire part about choosing a specific algorithm? – Alex A. Oct 21 '15 at 16:19
• @Fatalize I don't see why not. I'm sure that's already a documented sorting algorithm, however inefficient. – Alex A. Oct 21 '15 at 16:19
• To be honest, I think this question is on such thin ice with respect to dupe votes (e.g. 49935, 40744, 26947, 36447, 12028, 20478, ...) that I'm not sure it's worth dedicating effort to. But if you are going to post it, I would make two big changes: 1. Make it per-language, ask people to explain their code (giving algorithm name and complexity where possible), and allow them to give alternative algorithms in the same answer. 2. Ditch the I/O. The point of the "catalogue" questions is to showcase basic computational building blocks, not I/O. – Peter Taylor Oct 21 '15 at 17:51
• @PeterTaylor Is that per language, not per language/algorithm? And by ditching I/O do you mean allowing a variable to be defined containing the array (for example)? – Alex A. Oct 21 '15 at 17:58
• Yes, and exactly. – Peter Taylor Oct 21 '15 at 18:36
• @PeterTaylor Okay. I think I'm on board with the latter, especially since it's been difficult trying to come up with a truly convenient means of getting an array as input. Having it already defined scoots it a little closer to being a dupe of 49935 though. :/ But I think separating algorithms makes this more unique than the others. – Alex A. Oct 21 '15 at 18:49
• @PeterTaylor I changed the I/O. Any better? – Alex A. Oct 21 '15 at 20:07
• @PeterTaylor "and allow them to give alternative algorithms in the same answer." I think this is problematic because you'd still get multiple answers for each language, and if each language contains a few implementations they are spread out over the answers quite weirdly. That's why I suggested putting each algorithm in a separate answer and labelling it - then at least you know where to find each implementation (although I agree that the definitions of the different sorting algorithms aren't really applicable in some esolangs). – Martin Ender Oct 22 '15 at 7:37
• @MartinBüttner, I don't see the problem. Maybe because I see it as a catalogue of sorting, and you see it as a merger of many separate catalogues for bubble-sort, insertion-sort, quicksort, etc? – Peter Taylor Oct 22 '15 at 7:47
• @PeterTaylor I guess I'm just generally not a fan of multiple solutions in a single answer (even for a normal code golf, I'd rather just post two answers if the approaches are significantly different). – Martin Ender Oct 22 '15 at 7:51
• @MartinBüttner, but if the question is presented as a catalogue of the shortest way to sort in every language then e.g. any answer in GolfScript other than $ would deserve to be voted to about -5. – Peter Taylor Oct 22 '15 at 18:35 • @PeterTaylor It doesn't need to be presented like that. All I'm saying is that separate approaches should be kept in separate answers. Whether the leaderboard reads the algorithm from the header or not is a different matter. – Martin Ender Oct 22 '15 at 19:15 • Regarding build-in functions: few language specifications clearly state which sorting algorithm has to be used, so all depends on the either the compiler/interpreter or the std library. The used algorithm may change over time, for example Cs (g)libc used to use quickersort (hence the name qsort) but switched to a mixture of algorithms depending on input size - the name remained. Therefore a C answer using qsort should also name the library version to be verifiable ... – nimi Oct 23 '15 at 15:01 # "The" Gaidhlig Challenge The Gaidhlig language has some non-trivial rules when it comes to putting "the" in front of a word. You're challenge is to create a program that takes two inputs, the first input is a string of text, a real word or made up that we can pretend is a noun. The second input is either the letter 'f' or the letter 'b' to denote whether the word is masculine or feminine. The type of delimiter between these two inputs is your choice but must not be the letters a to z, a dash, or an apostrophe. 1. The first input is always assumed to be a noun. 2. The second input denotes whether the noun is masculine (f) or feminine (b). 3. We will always assume all inputs is valid. You're output will be the the first input, modified for the following rules: ## Masculine Nouns (where 'f' is supplied.) 1. Before vowels: An t- 2. Before b f m p: Am 3. Before all other instances: An ## Feminine Nouns (where 'b' is supplied.) 1. Before sl sr sn so se si su: An t- 2. Before b m p c g : A' [with lentition] 3. Before f: An [with lentition] Before all other instances: An ## Whether the word is masculine or feminine: Words that start with l n r sg sm sp st always start with: An ## Lentition When lentition is asked for, you must add the letter h after the first letter of your word in cases where the word starts with b c d f g m p s t. Otherwise the word remains unchanged. Further, you must not add an additional letter h if there is already a h in place. Examples Lentition of Aran: Aran Lentition of Ghoul: Ghoul Lentition of Goul: Ghoul Lentition of House: House # Examples Cat f An Cat Cat b A' Chat fear f Am fear fear b A' fhear Obair f An t-Obair Obair b An Obair snow f An snow snow b An t-snow Shortest code in bytes wins. • I think you have a consistent typo: it should be lenition, right? – Peter Taylor Oct 23 '15 at 21:54 I would love to hear your thoughts about the following challenge. Too difficult or contrived? Or should we actually want more complicated and challenging tasks? I'll provide an example implementation in MATLAB by the time I post the challenge. ## Concert Harp: Pedal Meddle code-golf Sometimes I hear people say, ‘Why would anyone outside the ICT business learn how to program?’ Often, they get replies like ‘well, sometimes there are problems to which there is no software available’, but when asked about what kind of problems these would be, they’re forced to admit that all they really wanted was to make Conway’s Game Of Life for their own entertainment. However, I recently found a problem that I think the home-and-garden programmer could face in reality. It considers a harp (a side effect sharing an apartment with a significant other) and a completely dumbfound pianist/programmer, who’s struggling enough with one pedal as it is. The harp in question has seven. Now, for some background music/harp theory. You may skip as much as your musical background, or lack thereof, allows. # Music theory (a very condensed version) Both in a harp and a piano, the strings/keys are laid out as follows: … C | D | E F | G | A | B C | D | E F | G A | B …  There are seven root notes, [A-G], with at some locations a | in between to signify that there’s a note in between. These |’s are address by making a note higher by appending a #, or lower by appending a b. For example, C#==Db, F#==Gb (and also, Fb==E). Using these notes, we can make a scale. The difference between D and D# is called a half note, and between D and E a whole note. Scales are made as follows: 1: take the root note 1: Find the next notes by going up a whole or half number of notes in the following pattern (last step in () because that makes you end up at the root note again) Major: 1 1 ½ 1 1 1 (½) Minor: 1 ½ 1 1 1 1 (½)  For example, D major and A# minor D E F# G A B C# (D) A# B# C# D# E# F# G# A# Of course, these notations are not unique, since for example E#==F. # Problem A harp has seven pedals, each responsible for one note. This note, they can either raise half a note, or lower half a note. For example, the C pedal can either make all C’s sound like C#(==Db) or like Cb(==B). Let’s designate raising by a pedal setting of +1 and lowering by -1, and leaving it as-is as 0. Given an input scale, write a program or function that outputs how each of the pedals should be set to achieve all of the tones in that scale. # Input A scale designation. Scales are designated as follows: R[m][k] • R: Root. [A-G] • [m]: Optional: modification. Either flat b or sharp # • [k]: Optional: minor key, designated as m. Valid inputs would be for example • C C major • Dm D minor • Fbm F flat minor # Output The pedal setting -1, 0 or 1 for each of the pedals, in the following order, reflecting the actual location of the pedals on a harp: D C B | E F G A  Test cases: (not exhaustive; i.e., there may be more solutions, I only included a double solution to one input) C , B#, Am -> 0 0 0 | 0 0 0 0 Cm, B#m -> 0 0 0 | -1 0 0 0 F#m, Gbm -> 1 1 0 | 1 1 1 1 or -> -1 -1 -1 | -1 0 -1 -1  • I'm confused: you say "Given an input scale" and then describe the input as "A chord designation". Which is it? – Peter Taylor Oct 25 '15 at 7:38 • @PeterTaylor thanks, I was doubting between two versions of this challenge so that must've slipped through, edited now. What do you think of the challenge itself though? – Sanchises Oct 25 '15 at 10:18 Oh, no! There's been a fire at Claus HQ, and it's destroyed Santa's flight route! He has called on you to come up with a route that has him arriving at every home between the hours of 9PM Christmas Eve and 7AM Christmas Day. He'd also like to finish his deliveries in as little time as possible. Input Your program will take data for as many geographical areas as you or Santa chooses to enter. For every geographical area to be added, your program will accept:the name of the area, and the geographical coordinates of the area's center and the number of "nice" children who live in that geographical area. Output In a .csv file your program will place: 1) Each geographical area's name, 1 per line, listed in order, with the area to be visited first placed first, and the area to be visited last placed last. 2) Next to the name, an ETA to the area in local time, and estimated time of departure, assuming Santa takes about 1/6100 seconds per child. 3) At the last line of the file, the total number of miles travelled, as determined by the sum of the great-circle distances - determined using the Vincenty formula, assuming an oblate spheroid Earth - from each stop to the next. Other than as stated above, I don't care what your file looks like. Rules -You may not use any external library to perform any task except the following: --Converting from one timezone to another. -You may give your output file whatever name you choose. -Estimated departure times must be no later than 7:01 AM. Scoring For simplicity, scoring will be done using US states as areas. The population inputted will be the number of 14-and-under Christians residing in each state. You get 1 point for every thousand miles travelled and an additional point for every hour of travel. • 1. "Vincenty formula" should be hyperlinked to a clear explanation, and geode parameters should be supplied. 2. Converting between timezones isn't hard, and doesn't need an external library, but the input does need to include the timezones. It would also be good to state explicitly whether or not the International Date Line needs to be taken into consideration. 3. We have no way of calculating travel times, because you haven't given us a speed. We also have no way of scoring our programs, because you haven't supplied the test data. – Peter Taylor Nov 8 '15 at 8:11 ## Convert your Language to Turing Machine Code You are locked into a room, with only a laptop and a single-bidirectionallyinfinite-tape, two symbols Turing Machine (Therefore supports only 0s and 1, and it has a tape which is infinite in both directions). Your perverted captor set you a task: he will set you free only if solve all of the problems on the Project Euler page. However, there is a catch. You are not allowed to solve the problem using your laptop, but you'll need to use the Turing Machine instead. Since you think it will be incredibly tedious to convert your code to Turing Machine Code, you decided to write an source-to-source compiler on your computer, and since you're incredibly eager to get out, you decide to write your code in the shortest form possible. ## Summary • Write in your language of choice an compiler that converts your language into your Turing Machine Code. • Your language may not need to be completely transformed, but at least the basic operations needed for mathematical computations need to be implemented, therefore you will need to implement at least three of the following, with mandatorily being able to translate a looping construct of your language, then for each more operator implemented you will get a 10% bonus: • Addition • Subtraction • Division • Multiplication • Modulus • Looping (Mandatory) • Bitwise operators: &(AND) |(OR) ^(XOR) !(NOT) (they count as 3 distinct ones) In practice your code should be able to translate at least a primality testing algorithm into Turing Machine Code. • When I refer to Turing Machine Code, I refer to code for TML (Syntax explained later here) ## Technicalities • The turing machine does not support decimal numbers, only binary, so you may (or may not if you have a better method) write numbers in unary. e.g 11111011 are respectively 5 and 2 • Since the Turing Machine does not have a predefined IO, you may consider leaving the return value on the tape and halting as returning a value. e.g 111110000 and halting will return 5. • For the Input, you have full access to the starting tape, according that you don't do any other operation rather than initializing the variables. e.g if you implemented add(a,b) and run add(5,7) you may initialize the tape to this: 1111101111111 or 11111001111111 or 111110001111111 exc. but you may not initialize the tape to: 111111111111 • TML Language description. TML which is the language your are interpreting your code to, uses a systems of cards, in this form 0{0-1}{0-1}{Integer}-1{0-1}{0-1}{Integer} where the first value determines which piece of code to execute (reading a value from the tape and comparing it, if it is 0 it will execute the code after the 0 until the dash, else the other piece of code), the second one tells what to write on the tape(0, 1), the third one finally tells the tape whether to go left(1) or right(0). The last value tells us to which card to go next, with the card 0 reserved for halting. Note that TML is not 100% complete, so if your code follows the specs, but doesn't actually work just let me know, so I can fix the Language interpreter (if it's actually broken) This is Code Golf, so the shortest code wins! • 1. The mention of interpreters is confusing: what you're asking for is a source-to-source compiler. 2. It would be useful to mention in the first sentence that the TM only supports two symbols. 3. What does "when to execute the card" mean? 4. In what circumstances could n be useful? It just seems to overcomplicate the explanation. 5. Is the tape infinite in both directions or just one? 6. What are "the basic operations needed for mathematical computations"? – Peter Taylor Nov 7 '15 at 12:31 • @PeterTaylor I've modified the question a bit, I think it should be clearer this way, the only thing I haven't changed is the use of n, which I think could be useful if one were to implement something like a "pass" card (just speculating). What do you think? – WizardOfMenlo Nov 7 '15 at 13:04 • That's rather a long list of mathematical operations! Is the intention to handicap higher levels languages because they support more operations and so will have more cases to compile? Write nothing is equivalent to writing what you read; move nothing is "Enter an infinite loop" if you wrote the symbol you read, or "See the other side of this card" otherwise. So all ns can be eliminated trivially except the infinite loop case, which can be eliminated by adding two cards x and y with instructions 000y-100y and 001x-101x respectively. – Peter Taylor Nov 7 '15 at 13:19 • @PeterTaylor. The long list of operations I've introduced as sample operations, that I think a standard programming language should have, however I am no Programming Language expert, and I'm quite ignorant (yet) of the variety that they present, especially regarding the operations. Regarding the "n", I think that your logic is more than valid, and I will also project this change to the language itself. Thank you a lot! P.s If you have some more effective ideas for the operations to implement, please be welcome! – WizardOfMenlo Nov 7 '15 at 23:17 • There are a lot of astandard languages on this site! The obvious language to use to answer this challenge is BF, which doesn't have anything more than increment and decrement. (And even a language as mainstream as Java doesn't have an operator for exponentiation or integer square root). – Peter Taylor Nov 7 '15 at 23:39 • @PeterTaylor I've now added a system of bonuses, what do you think? Do you think the question is ready to be asked? – WizardOfMenlo Nov 8 '15 at 8:51 • In addition to the issue of languages not having all of the operations on that list built-in, I find long lists of bonuses unappealing in general. I suggest that you scrap the list of operations, and instead require that the source language has to be able to translate all of its own functionality. This would create an interesting tradeoff between languages which are powerful, but have too many functions to implement, and ones that have the advantage of being minimal, but are difficult to program in. If you go with this, make sure to require the source language be Turing-complete. – feersum Nov 9 '15 at 8:10 # First 100 Twin Primes ### What Are Twin Primes? Twin primes are two prime numbers that has a gap of 2 between them; i.e. 3-5, 5-7, 11-13... ### Goal • Take no input and print first 100 twin primes to STDOUT. • Shortest code in bytes wins. ### Rules • Your submission should be an executable complete program. • Every prime couple should be on a new line. • Printed twins should have a space between them. • All standard rules are applied. ### Restrictions • No usage of built-in or external methods or functions that returns a prime number. • No hardcoded prime numbers except 2 (as number, not count). Any suggestions? I looked to similar questions but i couldn't see an identical one. • Unfortunately, we consider questions for which most solutions can be easily transferred duplicates, so without the restriction on builtins (and probably even with) your question would be closed as a duplicate of codegolf.stackexchange.com/questions/31822/… – lirtosiast Nov 10 '15 at 1:14 # Rounding Fractions Back in the old days of game programming, before FPUs were the norm, games predominantly used fixed-point math to represent non-integer values. Typically, the lower 8 or 12 bits of a 32-bit word are used as fractional parts, and the rest are treated as the integral part. Sometimes when looking at fixed-point constants in old game code, I get confused trying to figure out what they were actually trying to approximate, particularly if it's not a number between 0 and 1 (0x4C = 0.3, 0x119 = 1.1?, 0x73 = ???). Since just rounding 1/256ths and 1/4096ths has a limited range of applications, the challenge here is to take any integer ratio a/b, and output the simplest fraction that rounds down to it. More specifically, output the ratio p/q with lowest denominator such that a/b ≤ p/q < (a+1)/b. This code should support any non-negative a and positive b up to at least 10,000, and should run in a reasonable time for anything in that range (nothing on the order of minutes, at least). Answers should be correct, i.e., no rounding errors due to floating-point. Answers can be in the form of a full program or function, and use any convenient input / output (a string '1/2', an ordered pair (1, 2), a list of two integers {1, 2}, etc). This challenge is code-golf, lowest score in bytes wins. Some test cases: 1/3 -> 1/3 4/10 -> 2/5 33/100 -> 1/3 66/100 -> 2/3 67/100 -> 19/28 115/256 -> 9/20 (who knew?) 0/417 -> 0/1 653/654 -> 653/654 1404/702 -> 2/1  ## Sandbox Questions Hey! I'm a long-time lurker, first-time-question-asker; I'm pretty sure this hasn't been asked before (more general than "Un-round fractions", not quite "Closest fraction"). Not sure what to set for a deadline before accepting an answer, since this is my first time actually participating. Anything else obvious I missed? • Don't set a deadline before accepting an answer, at least in the sense of putting a date in the question. As a rule of thumb, wait a week, accept the winning answer, and if someone later posts an improved answer then change the accepted answer. – Peter Taylor Nov 14 '15 at 18:19 • Sort of duplicate? The differences seem to be normal rounding vs rounding down and the odd restriction to a single loop in the existing challenge. – Martin Ender Nov 14 '15 at 23:46 • That challenge is only about decimals, whereas this starts with an arbitrary rational number. Not sure if that's enough of a differentiation, but this one's broader, I guess. – Jonathan Aldrich Nov 15 '15 at 0:02 • @MartinBüttner, I agree it's borderline, but some of the answers to the older question couldn't easily be adapted because they rely on converting float to string, and that only works in base 10. – Peter Taylor Nov 15 '15 at 8:47 • @PeterTaylor It is a duplicate. floor(x)=round(x-0.5) – Xwtek Nov 17 '15 at 12:04 • @ChristianIrwan, why is that relevant? – Peter Taylor Nov 17 '15 at 14:32 • @PeterTaylor Oh, sorry, misread. – Xwtek Nov 18 '15 at 9:45 # Nondeterministic Turing Machine ## Introduction We all know the concept of Turing machines, if not let's reiterate the concept. We have the following things that define a Turing machine: • A tape that is divided into cells and is (potentially) infinite to the right. • A read/write head that moves along the tape and reads and writes from it • A state that changes according to what the head read • A transition function that defines state changes and the direction in which the head shall move, based on the current state and the input read. We can now have to supply some input, and the definition of the transition function (the set of states is implicit, and contains all states defined in the function). Additionally we assume that the alphabet is [0-9a-zA-Z!?()^+-] and space is the blank symbol. The tape head is then postioned over the leftmost character on the tape, which in our case is the first character of the input tape. The machine then starts applying the transition function. The computation continues until one of the following happens: • The machine reaches the HALT state • There is no transition defined in the transition function for the current state with the given input. If the first case occurs, we say that the machine "accepts" the word. If the second case occurs we say that the machine "rejects" the word. We can now extend this definition, to obtain a nondeterministic Turing Machine. To do this we allow the transition function to define more than one "next" state for each state/input combination. The machine can then choose which "execution path" to take. We then say that the machine accepts the word if it reaches the "HALT" state in any execution path, and it rejects it if it does not reach this state in all exection pats. ## Problem definition You must supply a program or function that accepts a string and returns a truth-ish value (either true/false, or 0/1, or anything else, at long as the meaning is clear) indicating wheter the word is accepted for at least one computation path or not. The input has the following for: (<current_state>,<input_read>,<output>,<follow_up_state>,<move_direction>)  All the parts of the tuple are provided as strings where • <input read> is a string of length 1, which can contain any character except "," • <output> is also a string of length 1 • <move_direction> is either "l" (move left) or "r" (move right) You may assume the following: • The machine will always halt (i.e. no infite loops) • There is only one state on which the machine halts which is HALT • The alphabet is [0-9a-zA-Z!?()^+-] plus space as the blank symbol • The leftmost character is always a blank, to indicate the ending of the tape on the left side. • States are defined implicitly by the tranistion function. So the only states the machine knows are the one that occure during the definition of the transition function and there is no explicit definition of the states. • The initial state is always s_i The input has the following form <nr_of_tuples_for_definition_of_transition_function> <tuple_1> <tuple_2> ... <tuple_n> <input_string>  All lines end with a newline character (\n) and the input string is not under double quotes. Standard loopholes are disallowed! Shortest answer in byte wins. # Notes Working example is still missing, I'll update that in the following days • "The machine then starts the computation at the beginning of the input": I suggest adding "i.e. with the first character under the tape head, and the others to the right". I'm not sure what you mean by "States are defined implicitly by the tranistion function". – Peter Taylor Nov 13 '15 at 13:59 • Followup questions: 1. What characters can appear in the name of a state? 2. What delimiters occur between the tuples in the input? 3. What delimits the end of the initial tape contents and the start of the tuples? – Peter Taylor Nov 13 '15 at 18:20 • Thank you very much for your feedback. I just realized that I didnt think the input part through, I'll need some time to rethink that. – wastl Nov 13 '15 at 18:54 • I realised today that there's another thing which needs specifying in the input: what is the starting state? This could done implicitly by saying that it's the <current_state> of the first tuple. – Peter Taylor Nov 14 '15 at 18:20 • I added input specification. Do you think this is an adequate method to provide the input? – wastl Nov 16 '15 at 11:39 • Yes, that works. – Peter Taylor Nov 16 '15 at 12:16 # DND Level Tables In 3rd edition DND, there a lot of stats that you have to keep track for when you level up. Let's fix that by making some nice tables for them. ## Crash Course on 3rd edition DND 3rd edition DND is very complex since it does not have "classes" in the traditional sense of most RPG games. Instead of picking a class when you create a character and more or less sticking to it, in 3rd edition you can actually "opt in" into any class you want at any time. Essentially, when you level up, you can choose to put that level in any class you want. This means that you can potentially have three levels in Rogue, two levels in Fighter, etc. In addition to this, 3rd edition has special things called skills, which are unique to each class. When you level up you get some skill points that you can spend on skills. You can spend one skill point to get one "rank" in a skill. However, if that skill does not belong to your class you only get one-half of a "rank" in that skill. There are also feats, which are essentially general skills that don't belong to any class and have their own "skill points", and stat increases, which are little stat bonuses you get on level up. All together, this is probably enough to make your head swim. Luckily, this challenge doesn't require you to get too much into the nitty gritty of this. ## Challenge Given an number representing a level as input, print out a table starting from level 1 up to and including the specified level of the following stats: • The total amount of XP you've gained to reach this level • Maximum class skill rank you've gained • Maximum cross-class skill rank you've gained • Whether you've gained a feat or stat increase (they are not gained every level) and the number of it. The stats should be in this exact order. The table should be formatted with columns for each stat, with at least 4 spaces between each column. The level, feat and status increase numbers should have their appropriate suffixes (like 3rd). If you do not get a status increase or feat at a level, write -- where the feat or status increase number would go. Now, without further ado, the math for all of this. Assume x is the level. Total XP: Class Rank: Cross-Class Rank: Feats: If (x divisible by 3), then you have gained your feat. You also automatically gain a feat at 1st level. Stat Increases: If then you have gained your stat increase. Unlike feats, you do not get one of these at 1st level. ## Examples Sample input: 40 Sample output: 1st 0 4 2.0 1st -- 2nd 1000 5 2.5 -- -- 3rd 3000 6 3.0 2nd -- 4th 6000 7 3.5 -- 1st 5th 10000 8 4.0 -- -- 6th 15000 9 4.5 3rd -- 7th 21000 10 5.0 -- -- 8th 28000 11 5.5 -- 2nd 9th 36000 12 6.0 4th -- 10th 45000 13 6.5 -- -- 11th 55000 14 7.0 -- -- 12th 66000 15 7.5 5th 3rd 13th 78000 16 8.0 -- -- 14th 91000 17 8.5 -- -- 15th 105000 18 9.0 6th -- 16th 120000 19 9.5 -- 4th 17th 136000 20 10.0 -- -- 18th 153000 21 10.5 7th -- 19th 171000 22 11.0 -- -- 20th 190000 23 11.5 -- 5th 21st 210000 24 12.0 8th -- 22nd 231000 25 12.5 -- -- 23rd 253000 26 13.0 -- -- 24th 276000 27 13.5 9th 6th 25th 300000 28 14.0 -- -- 26th 325000 29 14.5 -- -- 27th 351000 30 15.0 10th -- 28th 378000 31 15.5 -- 7th 29th 406000 32 16.0 -- -- 30th 435000 33 16.5 11th -- 31st 465000 34 17.0 -- -- 32nd 496000 35 17.5 -- 8th 33rd 528000 36 18.0 12th -- 34th 561000 37 18.5 -- -- 35th 595000 38 19.0 -- -- 36th 630000 39 19.5 13th 9th 37th 666000 40 20.0 -- -- 38th 703000 41 20.5 -- -- 39th 741000 42 21.0 14th -- 40th 780000 43 21.5 -- 10th  ## Reference Implementation Perl: sub formatNum {$_=pop;
$first = substr$_,-2,-1;
if($first == "1" and length$_ > 1) { return $_."th"; }$digit = substr $_,-1; if($digit == "1") { return $_."st"; } if($digit == "2") { return $_."nd"; } if($digit == "3") { return $_."rd"; } else { return$_."th" };
}

sub space {
print " "x4;
}

while(<>) {
$limit =$_;
for(my $c = 1;$c <= $limit;$c++) {
print formatNum $c; space; print ($c*($c-1)*500); space; print ($c + 3);
space;
printf ("%.1f", ($c - 1)/2 + 2); space; if($c % 3 == 0) { print formatNum $c/3+1; } elsif($c == 1) { print "1st"; }
else { print "--"; }
space;
if($c % 4 == 0) { print formatNum$c/4; }
else { print "--"; }
print "\n";
}
}


Try it online.

## coreutils default behavior stdin/stdout

We have a lot of challenges to implement just one of these operations, but a lot more are missing. Instead of adding a challenge for each of them, I thought I'd see if I could make a multiple-holes challenge that's complex enough to inspire some code re-use. This challenge is to reproduce a small subset of what Busybox does, namely to implement the default behavior of [almost] all of the GNU coreutils that (usually) read input from stdin or a file and send output to stdout or a file.

The utilities to reproduce are as follows:

1. cat copy stdin to stdout
2. tac copy stdin to stdout, reversing the order of the input lines (last line first)
3. nl copy stdin to stdout, adding a line number to the start of each line. Start at 1, use spaces to pad each number to a width of 6, and add two spaces between the line number and the original line
4. od I can't come up with a concise unambiguous way to describe the default output from od. I might skip it.
5. base64 for every 3 bytes of stdin, split into groups of 6 bits, look those 6-bit values up in the base64 alphabet, and output 4 such bytes to stdout. wrap output lines at 76 characters. pad missing bits with 0s, and output an all-padding 0b000000 as "="

I'll finish filling out descriptions for some subset of the following if this idea proves popular enough to proceed with.

fmt, pr, fold, head, tail, split, csplit, wc, sum, sort, shuf, uniq, ptx, tsort, cut, tr, expand, unexpand, yes

The format of an entry would be either one program or one function, which can perform all of these tasks, just like busybox can. As a program, it might read its own process name to decide which tool to run. As a program or a function, the first parameter might be which tool to run. As a program, input should come from stdin and go to stdout. As a function, input should be a single string parameter, and return a single string.

• I think it would be better to say "These ones have already been implemented" with links to the appropriate questions, and to then ask for a multi-tool which implements the non-dupes. That keeps things clear and, frankly, the ones which have already been done are probably mainly the less interesting ones. – Peter Taylor Nov 21 '15 at 23:07
• @PeterTaylor fewer holes means less likelihood of code reuse. I'm annoyed at other challenges where code reuse is possible but it's not useful. I hope to see it in winning entries here. – Sparr Nov 22 '15 at 2:06

# Find the nested source codes

A cops and robbers challenge where the cops write between 2 and 8 programs that produce output in the same language and interweave the programs together. WLOG, let's discuss this action being performed on two programs. By interweaving, I mean adding the characters of the second program to the first program so that when the characters of either the (WLOG) first program are removed, the second program can be seen. Obviously, commenting in any program is not allowed.

The cops will post their combined codes, the number of different programs in what they post, and the language the codes are written in, and what the programs print as output. To get credit for cracking the submission, the robbers must post the split codes and what each one outputs.

As a general rule, cops cannot use a language more than once.

Scoring

A cop will receive points if their submission is safe for one week from the time of posting. Their score will be the sum of the two following.

• The first value is 256 divided by 2 to the power of the number of different programs used.
• Round the number of bytes in the combined codes up to the nearest power of 2 and call this number x. The second value is 1024 divided by x.

A cop will lose 10 points for every code that is cracked before the one-week period is up.

Robbers will receive a number of points equal to the sum of the following for each cracked submission.

• The first value is 2 to the power of the number of different programs used in the cop's answer.
• Round the number of bytes in the combined codes up to the nearest power of 2 and call this number y. The second value is 1024 divided by y.

Example

Python, 2 codes

prpriintn("t"(hlellamlao")"[0])

Prints llama and h

Codes: print("llama") and print("hello"[0])

• Can I see an example? – Conor O'Brien Nov 22 '15 at 1:46
• @CᴏɴᴏʀO'Bʀɪᴇɴ Updated. – Arcturus Nov 22 '15 at 1:54
• On interweaving: does one have to say which method they used to interweave? – Conor O'Brien Nov 22 '15 at 1:57
• Interweaving is done in order. The example given would be prPRiIntN("T**"(HlElLamLaO")"[0]**, where bold and capitalization represent the second code. – Arcturus Nov 22 '15 at 2:03
• @CᴏɴᴏʀO'Bʀɪᴇɴ Think this is good enough to post officially? – Arcturus Nov 22 '15 at 2:36
• I'd wait a day or two, and ask some other people in chat. – Conor O'Brien Nov 22 '15 at 3:03

# Complete the Digit Sequence

We have a string of digits with some elements missing and marked with .s.

74..7.1..1.3...8.781256


We want to fill the missing parts in a way that they would form an arithmetic sequence with the previous on next elements. E.g. 8...2 becomes 8642. If this kind of filling is not possible with single digits, mark the positions with ?. E.g. 7..3 would become 7??3.

With this rules our original example becomes

745674111123???8?781256


You should write a program or function which receives a digit string as input and outputs or returns the filled sequence.

Input:

TODO


Output:

TODO


Examples:

TODO


This is code golf so the shortest entry wins.

Sandbox note: this seems boring so ideas are welcomed.

• Idea: turn the entire string into an arithmetic sequence of as many integers as possible (after inserting spaces). e.g. 7....2 would become 765432, i.e. 7 6 5 4 3 2, but 7....3 would have to become 791113, i.e. 7 9 11 13, whereas 7....4 would have to become 727374 (72 73 74) or 767574 (76 75 74) – Martin Ender Nov 23 '15 at 11:38
• @MartinBüttner I like it although I would like to avoid the extensive brute-force approaches. – randomra Nov 23 '15 at 12:37
• I just noticed there are a lot more possibilities for my last test case, like 72 53 44. But yeah, I'm not sure how much one could optimise solutions for this. (Also, I'd still keep the possibility of given digits within the sequence, I just used the x....y format for simplicity.) – Martin Ender Nov 23 '15 at 12:40

## Find runs of triple multiples of squares

Your task is simple: For a given input N, find all runs of three or more consecutive integers less than N which are all perfect squares or multiples of perfect squares (of numbers greater than 1, obviously). You should then list each triplet (or greater) on a single line, indicating the square and the factor that divides it, e.g. 48 = 2² * 12. If a number is a product of two (or more) perfect squares, you may write it in either of two ways, e.g. 100 = 2² * 5² or 100 = 10². If your language doesn't support the ² character, you may use ^2 instead. For example, for an N of 1000, your code should produce the following:

48 = 2² * 12, 49 = 7², 50 = 5² * 2
98 = 7² * 2, 99 = 3² * 11, 100 = 10²
124 = 2² * 31, 125 = 5² * 5, 126 = 3² * 14
242 = 11² * 2, 243 = 9² * 3, 244 = 2² * 61, 245 = 7² * 5
342 = 3² * 38, 343 = 7² * 7, 344 = 2² * 86
350 = 5² * 14, 351 = 3² * 39, 352 = 4² * 22
423 = 3² * 47, 424 = 2² * 106, 425 = 5² * 17
475 = 5² * 19, 476 = 2² * 119, 477 = 3² * 53
548 = 2² * 137, 549 = 3² * 61, 550 = 5² * 22
603 = 3² * 67, 604 = 2² * 151, 605 = 11² * 5
724 = 2² * 181, 725 = 5² * 29, 726 = 11² * 6
774 = 3² * 86, 775 = 5² * 31, 776 = 2² * 194
844 = 2² * 211, 845 = 13² * 5, 846 = 3² * 94, 847 = 11² * 7, 848 = 4² * 53


or

48 = 2² * 12, 49 = 7², 50 = 5² * 2
98 = 7² * 2, 99 = 3² * 11, 100 = 2² * 5²
124 = 2² * 31, 125 = 5² * 5, 126 = 3² * 14
242 = 11² * 2, 243 = 3² * 3² * 3, 244 = 2² * 61, 245 = 7² * 5
342 = 3² * 38, 343 = 7² * 7, 344 = 2² * 86
350 = 5² * 14, 351 = 3² * 39, 352 = 2² * 2² * 22
423 = 3² * 47, 424 = 2² * 106, 425 = 5² * 17
475 = 5² * 19, 476 = 2² * 119, 477 = 3² * 53
548 = 2² * 137, 549 = 3² * 61, 550 = 5² * 22
603 = 3² * 67, 604 = 2² * 151, 605 = 11² * 5
724 = 2² * 181, 725 = 5² * 29, 726 = 11² * 6
774 = 3² * 86, 775 = 5² * 31, 776 = 2² * 194
844 = 2² * 211, 845 = 13² * 5, 846 = 3² * 94, 847 = 11² * 7, 848 = 2² * 2² * 53


The input may be supplied via command line, user input, read from a file, or any other means you see fit (though it should not be hardcoded). This is code golf, so shortest code wins. Usual loopholes apply.

Note that these numbers are sometimes called "non-squarefree" numbers, which are listed at A013929. (This lists all non-squarefree numbers, not just consecutive ones, so it may be useful as a reference, but is not a direct source.)

Side note: The 242-245 and 844-848 runs are the only sets of more than 3 below 1000. It's possible that they become more common at higher numbers, but so far, graphing the sets I know about produces a pretty steady line, with no noticeable curve towards greater or reduced frequency. It would be interesting to see a mathematical proof on whether there are or are not an infinite number of these sets...

• 1. What is the relevance of N? It seems to be taken as input and then not used. 2. You're missing an important qualification. All integers are multiples of the perfect square 1². 3. This question would benefit from a link to OEIS A013929 – Peter Taylor Nov 15 '15 at 16:16
• Sorry, missed that. It's just a cap so your program doesn't run forever. Oh, and obviously 1² would be disqualified, I can make some clarifications. – Darrel Hoffman Nov 15 '15 at 16:35
• @MartinBüttner: I already accounted for that. Non-Unicode languages can use ^2. It's an extra byte, though, so might be more golf-friendly to use ². – Darrel Hoffman Nov 15 '15 at 17:41
• @DarrelHoffman Sorry, must have overlooked that. I suppose for interpreters which expect the source code to be UTF-8, it would be two bytes either way. – Martin Ender Nov 15 '15 at 21:16
• Re the side note, see comments on A045882. – Peter Taylor Nov 23 '15 at 21:53
• @PeterTaylor - Well alright then. Looks like you have to get into some pretty high numbers to see longer runs. Though it still doesn't answer the question as to whether they become more or less frequent the higher you go. I was surprised, for example, to discover there were fewer triplets between 500-1000 than between 0-500. This might be a bit off-topic for PPCG though. Maybe should start a thread in Mathematics? – Darrel Hoffman Nov 23 '15 at 22:03

# The Language Relay!

A typical relay race only has four competitors per team, but where's the fun in that? Instead, let's see how many teammates you can cram onto the bus to the stadium and still finish the race. (This analogy is starting to break down, so I'll cut to the chase.)

Your task is to write a program or function in 256 bytes or less. It will take no input, and its output will be a program or function in another language. That program or function will also take no input, and its output will be a program or function in another language... and so on and so forth, until the last program, which will output the following:

.     \O/      .
|===== |_ =====|
|    _/  |     |


The winner is whoever manages to use the most languages. If there is a tie, the winner is the one with the shortest code in bytes.

You cannot use the same language twice, and different versions of the same language do not count as different languages. The output must also be different every time (no using languages that leave the program or function untouched.)

Here's a small example:

#include<stdio.h>
int main(){printf("print(\".     \\O/      .\\n|===== |_ =====|\\n|    _/  |     |\")");}


This C code produces this Python code:

print(".     \O/      .\n|===== |_ =====|\n|    _/  |     |")


And the Python produces the final output. I've used two languages, so my score is 2, and I'm going to lose terribly.

• I'd implement some way to incorporate byte counts into the score because otherwise I'm sure there will be plenty of ties. – Downgoat Nov 25 '15 at 17:45
• Good idea, thanks. – Luke Nov 25 '15 at 17:46

This might already exist, but through my search I couldn't find anything like it, so here it goes.

## Find My Number code-golf

My friends and I have made are playing a game where we have a variable N that represents a number from 0 to 10. Using an expression they give us containing + - * / for addition subtraction multiplication and division, > < = for greater than, less than, and equal to, and the integers 0-10, we must find there number or what their number can possibly be.

I’m lazy, so I want you to write a Program that takes an input from STDIN or an acceptable alternative and return the possible numbers to STDOUT or an acceptable alternative.

Examples:

Input:

N+3>N*2-2

Output

1, 2, 3, 4

Input

N+2=N*2

Output

2

Input

N*4/6=N*2

Output

0

Because I might be caught, I want the program to be a small as possible in characters to avoid me friends seeing it, so the shortest solution wins!

• What it is impossible such as N<N or the result is all real numbers such as N=N? – Downgoat Nov 26 '15 at 16:18
• Well in the first one is impossible, so nothing works, so it doesn't output anything. The second one since anything works it prints all numbers 0-10 – Generic User Nov 26 '15 at 20:12
• I assume that the n in one of the examples is a typo for N. This is not really an interesting question. The addition of < and > makes it marginally different to existing "evaluate this expression" questions, but it's still trivial to handle with eval in languages which use infix operators. – Peter Taylor Nov 26 '15 at 21:14
• Thanks for pointing out the typo, I think expression still works since I explained what I mean, but I will try to find a way to reword the question. Anyone have suggestions? – Generic User Nov 26 '15 at 21:43

I'm thinking I want to make a KOTH challenge that has bots play the classic game of Mafia. Bots will be placed in groups of seven, roles randomly assigned, and they play the game!

Explanation of Game Mechanics The game proceeds in multiple turns, each turn consisting of Night followed by Day. At night, each person completes his role as will be described below. During the daytime, players (in real life) discuss the events of the night (communicated by God, a separate person who does not participate in the game besides prompting people to their roles.) Just before night, the players have the option of voting to lynch another player, the objective being to lynch a mafia member to help the town win. Choosing not to lynch is always an option if you think it is too risky to lynch someone who might be innocent.

In real life, God would tell everyone to sleep, then ask mafia to wake up and silently agree on who to kill, tell them to sleep, and continue with the other roles in a similar manner. Town wins if all the mafia are dead; mafia wins if they at least outnumber the town.

There are four roles in this game, but I have played many games with more than seven people with more ridiculous roles that are very fun to play. Each player bot is assigned an ID number indicating his role.

• Mafia - There will be 2 mafia in this game. The two mafia will come to a consensus on who to kill. If one is dead the other decides on his own. The two mafia can not choose one of them to be killed. Mafia has a role of either 1 or 2, which are identical in function.

• Inspector - There will be 1 in this game. At night he visits a person, and receives a report on that person's innocence. Both Mafia members will appear as guilty and the rest will appear as innocent. He can not inspect himself nor dead people. His number is 3.

• Doctor - There will be 1 in this game. At night he visits a person, and that person will not die that night. Doctor can not save himself nor dead people. His number is 4.

• Townsperson - Does nothing at night. Numbers 5, 6, 7.

The Challenge

You will write a Java player class who will have (at least) three important methods: night, claim, and vote. All of these three methods will return the player to 'act' on (of course, depending on your role), given an ArrayList of information that the other players have claimed in public.

I am not very clear on how to run a KOTH challenge and what github is supposed to do and how to use it so it would be very helpful if someone could point me in the right direction. As of now I'm still working out the exact details of a Java class to run the game, as well as making a generic Player class that the answers will have to extend and use methods from.

Right now, I have a generic Player class that each answer will extend, and each Player object has two Identity objects: a public, claimed Identity and a private Identity. The private Identity will hold the players actual role (kept secret, of course), as well as a doctor arraylist of Integers and a cop arraylist of Strings. If the player happens to be a cop, the controller program will add an entry to the private cop arraylist which will serve as his way of receiving a verdict. I'll make a method called verdict() which returns the last element to make the programming easier. An example string is "4G" which means that player 4 is guilty. This player 4 may be mafia 1; player numbers are just given for discussion purposes and to identify a player based on his claims and is independent on role. Doctor is the same except integers because you only need to store who was saved that night.

The public, claimed Identity works in much the same way except that the controller will never modify it, only the player can. An identity object contains a role (an integer representing the role number), an ArrayList of strings called 'visits' (to be used if you are a cop or doctor, to store a list of people visited and any outcomes), and an ArrayList of suspicions to indicate that your bot suspects or is guessing that another player has a given role. It will also have a lynch value which can be changed during the day, and this is where a player decides on who to lynch (if at all). Finally, it will have a boolean for if the player is dead or alive. You had better not mess with this. The idea of having two is that you can claim whatever you want; so a Mafia can claim to be Cop or a townsperson and the doctor can claim to be a cop.

Initially your public claim ID is 0, indicating that you have not claimed. The program will give you your private ID, which will contain your actual role and and is not necessarily meant to be made public just yet. The program controller will only modify your private ID object, and only then if your are Doctor or Cop. It will append to the visits ArrayList in the private identity object the result of the visit; the doctor will have access to everyone he has visited, and the cop will have access to everyone he has inspected and their alignment.

The controller, each night, will ask Mafia 1 for his choice then Mafia 2 for his choice, then repeat, say, 25 times. If at any point the two mafia agree, then it stops because the Mafia have just made their choice. The number of times attempted thus far will be given to the Mafia's night method, so the code will look like M1.night(<other players info>, 1) then M1.night(<other players info>, 2), etc. is that arraylist of public identities previously mentioned. If no consensus, no kill. Similarly prompt cop and doctor once for their choice on who to visit.

In the day time, every player's lynch value will be 0, indicating that they do not vote yet; each player will be given 25 chances to act. An action can consist of adding to the list of suspected values, claiming a role, changing a role, changing the list of suspected values, voting to lynch someone, changing a lynch vote, etc., or more. Some actions are smarter than others, and your goal is to have a good action strategy. Upon each call of a players act() method, he will be given an arraylist of everyone else's public identity objects, as well as how many times before he has been prompted. This gives him access to what other players claim to be, who other players claim to have visited and outcomes, who they suspect as who, and who others are voting to lynch. If at any point there is a majority (more than half but not exactly half) of people wanting to lynch a person (No lynch, indicated by the value -1, counts too), then day time ends, that person is lynched and his role revealed. If majority voted -1 (no lynch) then nobody dies and day time ends.

Again, please guide me on how I should design my classes, controller, and what files I should put up and how people are going to test their bot at home. I would be glad to show you what I have so far, which includes a controller program and a dummy player class.

• Note that we already have a Mafia KOTH here in the sandbox. – Alex A. Dec 5 '15 at 1:45
• @AlexA. Note also that he allowed me to take over. – Faraz Masroor Dec 5 '15 at 2:17
• Some important notes: The messages from the past post were a really good idea. Use them. Also, I think that its a good idea to have people submit a bot that plays a single role. Then, from round to round, simply switch in/out the bots for that role. – Nathan Merrill Dec 7 '15 at 4:40
• I am not very clear on how to run a KOTH challenge and what github is supposed to do and how to use it so it would be very helpful if someone could point me in the right direction I like this KoTH, and I've got quite a few of them under my belt. If you pop into chat I'd be happy to chat about it with you (and help with the code, if you'd like) – Nathan Merrill Dec 7 '15 at 4:49
• @FarazMasroor are you still planning on doing this? – Nathan Merrill Dec 27 '15 at 13:12

# Generate a graphical representation of a Stern–Brocot tree of depth n

I am aware of this challenge. Would this be considered as a dupe?

# Gilbert-Shannon-Reeds Shuffle

### Background

The Gilbert-Shannon-Reeds (GSR) shuffle is a simple model of riffle shuffling close to how real humans shuffle a deck of cards. The well-known rule of thumb to riffle-shuffle a deck of 52 cards seven times for sufficient randomness is based on the GSR shuffle.

### Algorithm

• Cut the deck at a position k, 0≤k≤n. If there are n cards, the probability that any given k is chosen is (n nCr k)/(2^n).

• Put the first k cards into one pile, and the other n-k in a second pile.

• Until all the cards are gone:

• Where the sizes of the two piles are x and y, choose the first pile with probability x/(x+y) and the second pile with probability y/(x+y).

• Move the first card in that pile to the new array.

### Challenge

Input: An array of positive integers, of length n<1000.

Output: The array shuffled once.

### Rules

You may use any algorithm that gives equivalent results to the GSR shuffle.

• Just to clarify: We have to shuffle once, yes? – Dennis Dec 4 '15 at 19:45
• Closely related. This is one of the rare cases where I would actually favour closing an older question as a duplicate of a newer one. – Peter Taylor Dec 4 '15 at 20:27

# Play Chess with a One-Move Lookahead

"I see only one move ahead, but it is always the correct one."

– Jose R. Capablanca, World Chess Champion 1921-1927

This is a chess tournament with a twist: your chess engine is only allowed to look 1 move (2 ply) ahead. In order to succeed, you must create the best board evaluation algorithm.

• En passant, castling, and under-promotion will be allowed. Of course, it is up to you if you want to bother adding those capabilities to your AI. I personally find these to be some of the best rules of chess.

I am considering making a "template" bot which implements alpha-beta pruning, and requiring users to just fill in the method for board evaluation. Otherwise, there may be ways to stretch what it means to "look ahead." The benefit for users would be that they don't have to write their own getLegalMoves() method.

• How is the algorithm scored? – Doorknob Dec 7 '15 at 2:24
• I don't think there's any way to specify "look ahead" which isn't vulnerable to stretching. Even if you just ask for the board evaluation. – Peter Taylor Dec 7 '15 at 9:44
• Why would you need pruning for a bot that only looks 1 move ahead?? – feersum Dec 7 '15 at 11:50

# Broken FizzBuzz - Greg Is Confused underhandedcode-golfpopularity-contest

(FizzBuzz suggested by quartata in chat)

Meet Greg. Greg is the new debugger at your company, and he deals with checking programs to see if they work. If they don't, he tries to find out why and fix them.

Greg is rather new to programming and understands the basics, but still gets tripped up by some advanced things. Sometimes, programs don't work and he doesn't know why.

You don't really like Greg, so you decide to play a game. You create two nearly-identical FizzBuzz-style programs - one which works, and one which doesn't.

For example:

n = input()
if (n % 3 == 0) {
print "Fizz"
}
if (n % 5 == 0) {
print "Buzz"
}


works, but

n = input()
if (n % 3 = 0) {
print "Fizz"
}
if (n % 5 == 0) {
print "Buzz"
}


doesn't. Greg is confused (but not by something as simple as this).

And because Greg has a desk only a few feet away from you, your code must be as small as possible, so he doesn't catch on.

## Rules

• Your correct program must accept an integer as input and return output as specified below, and your incorrect program must do something else (such as throwing an error or giving invalid output).
• The valid program's output must print "Fizz" if the number is divisible by 3, "Buzz" if it divisible by 5, "FizzBuzz" if it divisible by both 3 and 5, and nothing if it isn't divisible by 3 or 5.
• The invalid program's output may do anything else.
• Greg knows all programming languages to date, including super-obscure ones. Therefore, your answer may be in any language you choose (providing it was created before this challenge was posted.)
• You MUST have the two programs be nearly identical, except for one small change. The more concealed or insignificant-looking, the better.
• Greg uses PPCG and has participated in underhanded challenges before, so he knows about the C trigraph (??/). You can't trick him with it.
• Greg has also seen replacing ASCII characters with nearly-identical Unicode or abusing fonts, meaning that won't work either. Therefore, your program's change must work with all fonts, any may not exploit visual similarity between characters with different code-points.
• Changing an a to an A is allowed, as long as it's not obvious that that's what broke the program. However, changing a to <unicode character that looks exactly the same> is forbidden.
• Both programs must be written in the same language with the same version.
• The language both programs are written in
• Two programs: one FizzBuzz program, and another that is broken
• How to run both of them (the commands must be identical with identical arguments)
• Why one doesn't work (in spoilertext)
• The output of the broken one
• Your programs must have a Levenshtein distance of no more than 10 from one-another. (Meaning that you may add, delete, or change up to 10 characters in the broken code from the correct one.)
• Your score is the total bytecount of both of your programs.
• The winner is the post with the smallest score over 20 votes.

Meta Questions

• Is 10 too small a maximum Levenshtein distance? I was also considering 15.
• Are any of my rules already forbidden by the standard loopholes? I'd like to remove them if possible to make the post shorter.
• Similarly, should I remove or change any of my rules?
• This is a code-golf version of this previous edit. Should I keep it as code-golf or change it back?
• "replacing ASCII characters with nearly-identical Unicode" doesn't really express what that old chestnut does. "Exploiting visual similarity between characters with different code-points" is more accurate. Although it's arguable whether that covers e.g. switching space for non-breaking space, and I don't think it covers using non-whitespace non-printable characters (which with the right font are invisible). – Peter Taylor Dec 16 '15 at 16:44
• I think there is something interesting here in making seemingly equivalent programs behave very differently. But I'm generally sceptical of underhanded pop-cons, because they're usually way too broad and this one doesn't seem to be an exception. The primary cause is probably that there's no actual task that the program should accomplish. That means you can literally write any code that leads to failure from a small change (which is probably most code although the failure will not be surprising for most of those changes). I'd recommend giving a task for at least one of the two programs. – Martin Ender Dec 16 '15 at 16:49
• @PeterTaylor Maybe something like "Your program's change must work with all fonts, any may not exploit visual similarity between characters with different code-points"? – ASCIIThenANSI Dec 16 '15 at 16:53
• @MartinBüttner I've changed it to two programs that should print "Hello, world!" (only the correct program will work). How does this look? – ASCIIThenANSI Dec 16 '15 at 16:57
• There are some very closely related underhanded challenges: codegolf.stackexchange.com/q/31647/8478 codegolf.stackexchange.com/questions/23250/what-no-error codegolf.stackexchange.com/questions/19379/… – Martin Ender Dec 18 '15 at 16:37
• @MartinBüttner I've added them in. Do you think they're close enough to be duplicates? – ASCIIThenANSI Dec 18 '15 at 16:42
• @ASCIIThenANSI I can't predict how the community will vote, but I wouldn't mod hammer it. – Martin Ender Dec 18 '15 at 16:45

# Rearrangement Inequality: The Sequel code-challengegrid

Your mathematics teacher looked at your test results on inequalities. Not good.

Hence he decided to give you some homework on inequalities.

Since this is about inequalities (how unfair), he decided to give each student a differing amount of homework. The exact amounts do not matter to him.

After allocating the homework, he had a bunch of complaints. Apparently, some students have some neighbouring students who have less homework than them.

Hence, he has decided to rearrange the students such that there will be fewer complaints. As long as each student sees that at most one adjacent student has less homework than them, they will not complain. (The students are quite reasonable.)

Note that he can swap the position of two students, but he cannot move a student into an empty spot as the empty spot has no chairs and the chairs in this classroom cannot be moved around due to safety concerns.

## Input

Here are different forms of input you can consider:

Optional: You can include integers in your input for the size of the classroom for convenience. This is , so input and output does not matter too much.

Function input: Container with truthy and falsy values representing if a student is there or not. All truthy values must be the same, similarly, all falsy values must be the same.

Standard Input: A grid of 2 different characters, which can be separated by spaces. Possible input:

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


or

_@@_@
@@@@@
@_@@@
@@@@@


## Output

The teacher wants to know how to arrange the students. Each student can be represented as an integer from 1 to n from the least amount of homework to the most amount of homework. For the input:

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


where 1 means there is a student and 0 means there isn't any students, a possible output is:

0  12 13 0  4
10 11 16 15 3
9  0  14 17 2
8  7  6  5  1


where the students labelled 16 and 17 are not satisfied.

Your score for every test case will be the number of students which are satisfied over the total number of students in that test case. It is guaranteed that there is at least one student in each test case. Your final score will the average of your scores over all test cases.

If you want to use another form of input and output, please clearly state it in your answers.

## The teacher has some concerns:

Please ensure that your code is deterministic, as the teacher may test it several times. You are allowed to code your own psuedorandom number generator if you need random numbers.

Please ensure that your code terminates within a minute for each test case, as the teacher is impatient.

The teacher has been to PPCG for a long time, so he knows all the standard loopholes.

The teacher has a very large classroom (100 by 100), and would be worried if your program fails to give an answer for such a large classroom.

## Finally:

This is , and the winner will be the person with the largest score.

# Sandbox Meta:

I still need to generate some large test cases, so I'm leaving this in the Sandbox until I have large test cases. How should I show people large test cases?

• Is it acceptable to use a built in pseudorandom number generator provided it is always run with the same seed? – trichoplax Dec 29 '15 at 15:37
• @trichoplax I may need to be able to test the code multiple times, so that may require all compilers/interpreters to implement the same pseudorandom number generator, which I am not sure if that is the case. – Element118 Dec 29 '15 at 15:41
• Ah, I see. That is definitely guaranteed for some languages, and definitely not for others... Banning all built in RNGs does at least seem fair to all languages. – trichoplax Dec 29 '15 at 15:58

# Approximate an image using all colours

I know that this is basically a subset of the then very popular American Gothic in the palette of Mona Lisa: Rearrange the pixels but I think it is worth making it a new challenge.

As @MartinBüttner pointed out, there has also been the Images with all colors challenge, but in my opinion it has very little in common with the proposed challenge.

# Challenge

Given a image of 2^12 x 2^12 pixels as input, your program should recreate this image, but you have to use each of 8-bit RGB colour exactly once.

# Meta

These are roughyl 12MP images, quite large. So one could just restrict it to 7-bit RGB then the pictures would only have to be 2^18 pixels, that means e.g. 512 x 512 pixels which would be way more suitable for the challenges here.

Or does anyone know a convenient other colour representation?

• There's also this. I'm really not sure you'll get any better approaches than those used for CH's palette challenge. – Martin Ender Dec 22 '15 at 19:11
• I was wondering that too on the other hand you have the advantage of exactly knowing the pallete and at the same time the disadvantage of having to use all the colours, even those that do not follow a "natural distribution" (a palette that is similar to "natural" images.) – flawr Dec 22 '15 at 19:15
• I lean towards thinking this is too much of a duplicate of "in the palette of", but if it turns out to be accepted I'd recommend changing the title to "Approximate an image using all colours" to make it clear it's not "Images with all colors" again. – trichoplax Dec 29 '15 at 15:52
• As noted in my answer to "in the palette of", it was directly adapted from a program which does this, so as far as I'm concerned it's a dupe. – Peter Taylor Dec 30 '15 at 10:54

## Make a New Year countdown

Editor's note: This challenge is cancelled because it is the year 2016, and I'm too late. XP It is kept here for posterity.

It is New Year coming soon. As such, it would be a great idea to make a New Year countdown. That is your challenge today!

Happy New Year!

### The full rules

• Create a program taking from STDIN the current time and outputting a countdown until New Year into STDOUT.

• The program should be flexible - after Year 2015 has concluded, the program should count down until New Year 2017, and so on. See examples for more information.

• The program should count down until it is taken down by external means (using Ctrl-C, the Task Manager, the reset button, et cetera).

• The countdown may be formatted however you like.

• At the null second in the new year (YYYY-01-01 00:00:00), it should output 0 days, 0 hours, 0 minutes 0 seconds in your chosen format.

• This is , so shortest answer wins.

• The last rule: Have fun!

### Examples

Given the input after from: the following countdown should be given, in any format you like (after to:).

from:
2015-12-31 06:00:00
to:
0 days 18:00:00

from:
2015-12-31 23:59:57
to:
0 days 00:00:03

from:
2016-01-01 00:00:00
to:
0 days 00:00:00

from:
2016-01-01 00:00:01
to:
364 days 23:59:59

• Three things: 1. IMO this is close enough to this question that it's a borderline dupe. 2. 2016 is a leap year, so from 2016-01-01 00:00:01 to 2017-01-01 00:00:00 is 365 days 23:59:59 (assuming no leap seconds are added, but that can't be predicted in advance). 3. Because of points such as the previous one, for testing date questions it's usually better to take the current time on stdin rather than read it from the clock. – Peter Taylor Dec 31 '15 at 10:59
• For 3; changed the rules to get the time from STDIN – user48538 Dec 31 '15 at 16:40

## Sig-fig calculator

As a scientist, sig-figs are definitely one of the most important parts of measurements and calculatations (unless you are a theoretical scientist, where everything must be exact!). Sig-figs is an important way of measuring uncertainty and accuracy of a value. To calculate the number of sig-figs for a value, use the following to help you (from here):

1. ALL non-zero numbers (1,2,3,4,5,6,7,8,9) are ALWAYS significant.

2. ALL zeroes between non-zero numbers are ALWAYS significant.

3. ALL zeroes which are SIMULTANEOUSLY to the right of the decimal point AND at the end of the number are ALWAYS significant.

4. ALL zeroes which are to the left of a written decimal point and are in a number >= 10 are ALWAYS significant.

5. Exact numbers in an equation have infinite sig-figs. For example, in the equation $A=pi*r^2$, $pi$ has infinite sig-figs and the exponent of 2 also has infinite sig-figs. (not included in the above link)

To calculate the number of sig-figs from a calculation, use the following rules:

1. For multiplication and division, the number of sig-figs for the result is equal to the number of sig-figs for the least accurate value (i.e. the value with the least number of sig-figs). For example, 2.000*5.00 = 10.0 and 4.5*6.00 = 27

2. For addition and subtraction, the result has as many decimal places as the one with the least decimal places. For example, 5.00-2 = 3 while 6.0-3.000 = 3.0

3. logs (including natural logs) have as many decimal places as the number of sig-figs of the value of whose log is being taken (I am not sure if this sentence of English is correct!). For example, log(2.45) = 0.389.

4. Other functions, such as square roots, exponents, sines, cosines, etc. can be assumed to have the same number of sig-figs as its argument. So the sin(3.14) = 0.00159

Challenge

The challenge is to write a sig-fig calculator with the following functions:

2. sine, cosine, tan, and their inverses
3. sinh, cosh, tanh, and their inverses
4. Exponents, including shortcuts for e^x and 10^x, along with sqrt. The exponents are assumed to be exact and has infinite sig-figs
5. log of base 10 and natural log.

The result of each calculation should give you the correct result, but insert a "\" before the last sig fig. If there is infinite sig figs, there should be no "\" at all. Also, undefined and infinite values should give an error or NaN or print "infinity" or "undefined". For example,

sin(3.14) = 0.0015\9265292
log(1.01) = 0.00\432137378
5.00*2 =\10
2.00^5=32.\0


This is a so the shortest code wins!

• The positioning of the backslash in the output spec is rather confusing, but I think that one of the examples disagree with the spec. 5.00 * 2 is 10 with one sig fig according to the rule for multiplication that you take the number of sig figs of the least accurate value. Of course, this runs into the problem that your (unconventional, I believe) rule 4 does not provide any way to represent the number 10 with only 1sf, but even so I think the correct output should be \10. – Peter Taylor Nov 24 '15 at 22:06
• @PeterTaylor thanks! It is now fixed – TanMath Nov 24 '15 at 22:59

# Clean numbers

We call a positive integer a clean number if it is expressible by using only a positive digit once or more and no other sign. For example 88 is expressible with 2's as 2222.

A more complex example is

$$141289730531295606313143345858933 = 3^{33}3^{3^3}3333$$

## Details

The possible operations are

• exponentiation
• multiplication (only if the first part contains exponentiation as otherwise it is just digit concatenation)
• digit concatenation

Precedence is as normal. Power towers are computed from right to left (top to bottom).

sandbox note: which one should it be? I'm thinking d) now

• a) given a number return if it is clean
• b) given a number return the digit with which it is clean
• c) given a number and a digit return if the number is clean with that digit
• d) given a number and a digit return digit-clean numbers up to the given number
• e) given a number find the smallest digit or digit-sequence which makes it clean (eg. 63504 = 2522)

## Test cases

TODO
(11^1)*11
2^(2^2*22)


Your program should solve every test case in a couple of minutes.

This is code golf.

• Unfortunately, this site doesn't have latex support. It should though. – SuperJedi224 Jan 2 '16 at 14:55
• @SuperJedi224 I know and I will add image for the final version. I'm just lazy to do it already. – randomra Jan 2 '16 at 15:00
• Unfortunately, Meta does have LaTeX support. You just have to double up on the dollar signs. – Dennis Jan 2 '16 at 16:06
• Not anymore... i guess – user46167 Jan 3 '16 at 17:47
• If combinations are allowed, then 2016=C(2^C(2^2,2),2) ;) – user46167 Jan 3 '16 at 17:49
• @BlockCoder1392 seeing that in the chat gave the idea for the challenge – randomra Jan 3 '16 at 18:05
• Yes, I know. I was just suggesting combinations (which probably wouldn't be accepted anyways) – user46167 Jan 3 '16 at 18:21

I wasn't able to find a challenge like this before, but it wouldn't surprise me if it already exists.

A strand of DNA is made up of bases notated by the letters A, T, C, and G. A always pairs with T, C always pairs with G, and vice versa.

Therefore, you can find the opposite side of a DNA strand by swapping all occurrences of a base with its complement.

Here's the catch: your program cannot contain the characters A, T, C, or G at all – in string literals or in the body of the program.

The input is a string of continuous uppercase characters (you can assume that this string only contains the above bases). The input can be any length. The output should be the complementary strand of DNA.

Examples

Input:   AC
Output:  TG

Input:   ACCTAGTAT
Output:  TGGATCATA

Input:   GCATC
Output:  CGTAG

Input:   TCTGAAACTAGGGGC
Output:  AGACTTTGATCCCCG


This is code golf, so the shortest program wins.

• I think this is the closest existing question. Note that it's a more complicated question, and the winner is still only 24 bytes. I have a 16 char solution to this question in CJam. – Peter Taylor Jan 5 '16 at 23:18
• It seems like this is basic character table translation in languages that support that, in pyth and cjam these answers seem near optimal, they're also kind of boring, idk if people will think it's too boring... – FryAmTheEggman Jan 6 '16 at 15:28
• @FryAmTheEggman that's why I added the requirement the character restriction. I don't think it will be as easy to do a character replacement without using the actual characters. – erdekhayser Jan 6 '16 at 18:20
• @erdekhayser in many languages you can just use base encoding of some kind to avoid that. – FryAmTheEggman Jan 6 '16 at 18:35
• @FryAmTheEggman simple thing would be to prohibit the use of base encoding... – TanMath Jan 6 '16 at 19:05
• @FryAmTheEggman I have a 17 byte Pyth answer using only simple ASCII characters. It is possible to solve this challenge without base encoding – TanMath Jan 6 '16 at 19:06
• @TanMath without base encoding I think most languages would just add to character codes... – FryAmTheEggman Jan 6 '16 at 19:17
• @FryAmTheEggman I think that is the only route to go, which is what I used. Any problem with that? – TanMath Jan 6 '16 at 19:20
• @TanMath not necessarily, but a challenge where the only challenge is working around an obvious solution by restricting workarounds isn't one I would personally find interesting. – FryAmTheEggman Jan 6 '16 at 21:43
• @TanMath or just specify ranges around the desired characters in the translate command. Like this 15 char Retina solution TB-H@-UH-BU-@ – Rainer P. Jan 6 '16 at 22:18
• 20 bytes in Seriously using only arithmetic on character codes (no base encoding or translate): ,O6╙(-7P/≈u6╙+cMεj – quintopia Jan 7 '16 at 16:55
• Should I add a restriction on base encoding, or should I not post this challenge? – erdekhayser Jan 7 '16 at 19:48

# Format a list of words

Your challenge is to format a list of words across multiple lines that are no longer than a given number of characters, so that each line contains as many words as possible and no words are unnecessarily cut off.

## Input

The input will be a space-separated list of words and then a number that is at least 4.

## Output

The output should be the input words grouped into lines so that none of the lines contains more characters than the input number. The lines should be output in the order they were input. The words should be comma-separated, and each line except the last should end with a comma. If a word is too long to fit on a line, it should be cut off as little as possible while following the other rules, and "..." should be added to the end.

## Test cases

Input:
foo bar baz qux 12

Output:
foo, bar,
baz, qux

Input:
foo bar baz qux 5

Output:
foo,
bar,
baz,
qux

Input:
strength dexterity constitution intelligence wisdom charisma 10

Output:
strength,
dexterity,
consti...,
intell...,
wisdom,
charisma

Input:
quas wex exort 4
...,
wex,
e...


## Sandbox questions

• Has this been done before?

# Smallest Turing Complete Interpreter

## Sandbox Notes

• Has anything like this ever been done before?
• Do you think this will be well received?
• In my research I couldn't find a simple definition of what makes a language "Turing complete". What alterations or additions should I make to the language rules? I would prefer that the language in every answer was not exactly the same, but at the same time I want to keep the complexity as low as possible (while still being Turing complete) so that ideally one of the answers would become the world's smallest (non-eval) interpreter.
• Are there any other loopholes I missed?

Let me know in the comments!

Your challenge is to make the smallest possible interpreter for a programming language.

## What is the language we are interpreting?

You get to create the language! You can implement any instructions you like, however the language must be Turing complete. For the purposes of this challenge, your "Turing complete" language must be able to:

• Store and retrieve an arbitrary amount of data in memory The amount must be theoretically infinite, but your interpreter only needs to handle a minimum of 64 kilobytes (256 ^ 0xffff distinct values). The format could be an array of numbers, a string, a very large integer (if the language of your interpreter supports 524288-bit integers :P ) or any other format that provides the same number of distinct values.
• Loop conditionally The loop must also be able to alter the execution flow (if you implement a while loop that can only have one instruction in the body, it won't be able to affect anything outside of the while loop). This can be one command (eg: while A do { B C D }) or two (eg: if A then B and goto C) or any number that produces the same effect.
• Print any ASCII character This includes code points 32 to 126 inclusive. Newline is not required but being able to print characters outside of this range is fine.

It does not need to take input. Any extra features are fine as long as it meets these requirements. The language does not have to be pleasant to use, but each of these requirements must be usable in the real world.

See the languages here for some inspiration...

## Input

• Your interpreter must take a single string containing the source code of a program in your language.
• The input will always be a valid program. You do not need to handle endless loops, impossible instructions, etc.

## Output

• A single string containing the output of the program.
• A single trailing newline is allowed, any other leading or trailing whitespace is not.

## Rules

• The only rule is that you cannot use eval (or equivalent) in your interpreter.
• Your interpreter must be a full program, not just a function. Input and output must be from STDIN, STDOUT or their equivalents.
• The interpreter and the specifications of your language must be posted in your answer. Make sure you include all details that prove the language is Turing complete!
• Your language can be identical to an existing language or a language from another answer.

## Remember...

This is . Your score is the number of bytes in the source code of your interpreter, so design your language to minimise this score.

Good luck!

# JavaScript (ES6), 148 bytes

s=prompt();o="";m=[];for(p=i=0;c=s[i];i++)v=m[p],+c?c-1?c-2?c-3?c-4?o+=String.fromCharCode(v):p++:p--:m[p]=~~v+1:m[p]=~~v-1:m[p]?i=m[p+1]:0;alert(o)


## Language Specification

Memory is stored on an infinite tape. The pointer variable points to a position within this tape. The index variable holds the index of the current instruction in the source code being executed. Each instruction is a single-digit number. The numbers do the following:

• 5 = print character ASCII code at pointer
• 4 = increment pointer
• 3 = decrement pointer
• 2 = increment value at pointer
• 1 = decrement value at pointer
• 0 = if the value at pointer is non-zero, set index to the value at pointer + 1

## Explanation

Using numbers instead of letters for the instructions means I can check with c-3 instead of c=="x".

s=prompt();
o="";
m=[];
for(p=i=0;c=s[i];i++)
v=m[p],
+c?
c-1?
c-2?
c-3?
c-4?
o+=String.fromCharCode(v)
:p++
:p--
:m[p]=~~v+1
:m[p]=~~v-1
:m[p]?i=m[p+1]:0;


## Test

prompt = () => input.value;
alert = (output) => result.textContent = output;
var solution = _=>{ s=prompt();o="";m=[];for(p=i=0;c=s[i];i++)v=m[p],+c?c-1?c-2?c-3?c-4?o+=String.fromCharCode(v):p++:p--:m[p]=~~v+1:m[p]=~~v-1:m[p]?i=m[p+1]:0;alert(o) };
<textarea id="input" rows="5" cols="70">222222222222222222222222222222222222222222222222222222222222222222222222522222222222222222222222222222522222225522254222222222222222222222222222222222222222222225111111111111531111111111111111111111115222222222222222222222222522251111115111111115425</textarea><br />
<button onclick="solution()">Go</button>
<pre id="result"></pre>

• You ought to add that all submissions include a proof of TC-ness – quintopia Jan 9 '16 at 6:49
• @quintopia Yes. I've been contemplating what the simplest way to prove turing-completeness is. At the moment the only way to check is by looking at their language specs and comparing them to the checklist in my question, but maybe there's a simple program that uses all these rules that I could require (or at least recommend) to be made and run in their language which proves Turing completeness... – user81655 Jan 9 '16 at 8:03
• The only way to prove TC-ness that I know is to reduce a universal language to it. But you can let the submitter decide which language they want to reduce to it. – quintopia Jan 9 '16 at 8:07
• 1. I would vote to close this as too broad. It essentially duplicates half of the interpreter tag. See in particular codegolf.stackexchange.com/q/40300/194 . 2. What makes a language TC is the ability to emulate a universal TM. This is often proven by proving ability to emulate another known-TC system and applying transitivity. 3. In "a minimum of 64 kilobytes (256 ^ 0xffff distinct values)", what is ^ and how does 256 ^ 0xffff relate to 64 kB? 4. Not all TC systems have an explicit concept of loop. – Peter Taylor Jan 9 '16 at 17:04
• 5. Output in ASCII seems to directly contradict your stated intention to "keep the complexity as low as possible" and inspire "the world's smallest (non-eval) interpreter". 6. The restriction against eval seriously constrains some languages' ability to process input. – Peter Taylor Jan 9 '16 at 17:05
• @PeterTaylor Yeah, the broadness of the challenge is my main concern. I'm not sure there is a way to fix this without changing the purpose of the challenge as well. Addressing your other points: 3. There are 256 to-the-power-of 0xffff different ways you can arrange the bits of a 64 kilobyte block of bits. I just worded it like this to illustrate that the memory can be stored in any way that produces the same effect (rather than enforcing a 16384 length array of 32-bit integers, etc). The wording could be improved. – user81655 Jan 10 '16 at 2:47
• @PeterTaylor 4. I assumed that would be necessary. How would it compute a recursive algorithm without the execution jumping back to the start of the algorithm repeatedly? 5. True. It's purpose was to unify the output of the languages and simplify testing but it would probably be more work for some interpreter languages. 6. That was to prevent trivial answers like eval(input). I could make an exception for using eval to parse the input as a literal. – user81655 Jan 10 '16 at 2:47

# "Compress" text into Zalgo

Zalgo, the Nezperdian hivemind of chaos, is a type of text that uses combining characters to make very tall and noisy text. If you don't know what I'm talking about, maybe this will jog your memory:

<zalgo>

H̡̢̢̡̡̧̢̡͎̟͚̮͓͇̦̮̙̗̜̱̱͔̲̹̣̱̠̀̀͐̑̾̓̃́̃̍̀͆̇͆̽̔̒̚̕͘̚͜͝͠͠ͅE̢̧͓̺͉̟͙͇̳̰͉͖̺̻͕̰̱̝̳̙̰̟̠̯̘̰̲̎̑͋͂͑́͛̎͋̇̍̾̊̈́̂̽̿͆͛͑̽̒̊́͠͝͠͝͝ͅ ̨̢̟̳̥̖̺̼͎̩̘̰̣̼͇̰̫̞̜̲̰͔̗̠͔̩̻̳͇̾͌̆̑̍̄̊͗̓̃̆̊̄̽̐̂͛̏͑̒̓̆͝͝͝Ç̛̬̩͙̱̥̦̪̮̖͚͚͔̼̱̺̳̳̬̭͍̣͍̙̹̜̫̟̳͌̓͗͊̐̈̄́̏̀͂̎̃̈́̈́̎͋̀̒̊̀̈́͒̽͘̕͝Ȏ̡̡̨̡̝̬̠͚̠̯͖̹̟͓̮̻̲͙̖̪̯͇̍̅̂̌̌̒͗̈́̉͆̇̑͒̉̂̾̃̌̽͛͘͝͝ͅM̡̢̢̘͉̤͍̫̺̻͕̱̤̤̞̟̞̹͉͓̥̳͖̹̤̆̋̓͂̂͑̃̌͛͂̋̂̓̏́̀̾̋̈́̅̐̅̎̇̐̽͜͝Ȩ̨̛̭̥̹̳̫͎͖͈̳̠͍͙͉̻̼͍̞̜̺̝̻̝̗̳̏̈̓͋̐́̋͆͋̓̿͐͆̾̾̃͌͌̾̊́̚͘͘͜S̡̢̡̡̛̯̪̬̹̲̙̮̲̲̤͖͖̞̲̞̼̪͓͇̤̼͇͆͋̊̈̑̆̿̐̎͑̾̅̀̒̓̎̐̍̽̈́̋̽̓̔̍͜͝

</zalgo>


As a new twist on the age-old Zalgo generation problem, your goal is to take a string and "compress" it into a single Zalgo character. You will write two programs, one which takes in a string of printable ASCII and outputs a single Zalgo character, and a second which takes in a single Zalgo character and outputs the original ASCII string.

• I think the most golfable solution will be to encode the input in unary and use a single combining mark. Is that what you're looking for? – Martin Ender Jan 9 '16 at 22:11
• Maybe require the zalgo output to be shorter in some sense? – xnor Jan 9 '16 at 22:38