# What is the Sandbox?

This "Sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to the main page. This is useful because writing a clear and fully specified challenge on the first try can be difficult. There is a much better chance of your challenge being well received if you post it in the Sandbox first.

See the Sandbox FAQ for more information on how to use the Sandbox.

## Get the Sandbox Viewer to view the sandbox more easily

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

# Xor A Rational Number

## Background

Consider the fraction 3/5 in base 2:

0.10011001100110011001100110011...
\___/\__/
(a)  (b)


It has a "regular" or non-repeating part (a) and a repeated part (b). Let's go ahead and shift it right by one bit and xor it with the original:

 x           = 0.10011001100110011001100110011...
(x >> 1)     = 0.01001100110011001100110011001...
(x >> a) ^ x = 0.11010101010101010101010101010...
\__/\/
(a) (b)


By examining the regular (a) and repeating (b) parts, we find that (x >> 1) ^ x = 5/6.

## Input

• Two whole numbers 0 < x, y < 256 such that 0 < x/y < 1 and gcd(x, y) = 1
• Input can be through STDIN or function arguments
• Input passed in any simple format for two decimals is acceptable, e.g. x y, x\ny, (x,y), [x, y], x/y, x%y (Haskell)
• Input must be in base 10

## Output

• The numerator and denominator of ((x/y) >> 1) ^ (x/y), in base 10, in any clear output format.

## Rules

• The submission may be a function or full program
• The output fraction does not have to be in its most reduced form
• Builtins for rational number xor are not allowed
• Infinite precision rational number types are allowed
• This is code golf so shortest answer in bytes wins! (Tie break by first submission)

## Test cases

More tests upon request or when this question is posted.

3/5 -> 5/6
1/2 -> 3/4
1/3 -> 4/6


Note:

I'm not entirely sure whether this has a more or less trivial solution...

This is code golf so shortest answer is bytes wins!

• Great idea. :) Are rational types allowed for I/O? Or at all? – Martin Ender Aug 1 '16 at 14:31
• Great point. No, I believe that builtins for exact rational numbers should be disallowed. Do you think it's clear that the error should be 0, i.e. exact answers only? – Michael Klein Aug 1 '16 at 14:33
• You've disallowed the use of built-ins for xoring rational numbers. Can we use rational types otherwise as long as we don't xor them? If so, it would probably be good to include that in the valid I/O formats as a useful example. – Martin Ender Aug 1 '16 at 14:42
• "Consider a fraction 2/5:" ok, 0.4. I think you should mention either "base 2" or "binary" somewhere in that first sentence. – Peter Taylor Aug 1 '16 at 14:55
• @MartinEnder Yes, that is allowed. I've added that and a couple more valid I/O formats – Michael Klein Aug 1 '16 at 15:23
• I don't think your binary representation of 2/5 is correct. 0.1 in binary is 0.5 in decimal, which is already more than 0.4. 0.01100110... seems to be the correct value. – beaker Aug 1 '16 at 16:50
• @beaker You're totally right. I meant to write 3/5 but typo'd it. Thanks for catching that – Michael Klein Aug 1 '16 at 16:53
• That makes more sense – beaker Aug 1 '16 at 16:53
• You might be interested that the xor of rationals gives the Sierpinski Gasket as a 3D graph. – xnor Aug 2 '16 at 9:38
• I disagree with your third test case. 1/3 = 0.0101010101... so 1/3 ^ 1/6 = 0.011111111... = 1/2. – Peter Taylor Aug 2 '16 at 15:35

# The Hanoi KoTH

The KoTH is like this:

Two stacks of height-8 towers are on either side of a total of 11 pegs, and are coloured red and blue.

(Like this: [["R8", "R7", "R6", "R5", "R4", "R3", "R2", "R1"], [], [], [], [], [], [], [], [], [], ["B8", "B7", "B6", "B5", "B4", "B3", "B2", "B1"]] - each array is a peg.)

The objective is to move your entire tower to the opposite side before your opponent does, Tower of Hanoi-style. Red has to move all of their blocks to where Blue's blocks are, and vice versa.

## Rules:

• You may not place a block on top of a block that is of an equal or smaller size.
• You are only allowed to place a block on your "end tower" once your opponent has cleared away all their blocks.
• If there are no more "moves" for either side, then the game is a draw.
• There is a limit of 10,000 moves. If neither side completes their tower, then the game is a draw.
• If you complete your tower before your opponent does and before the 10,000 moves is over, then you have won.
• Invalid moves include:
• Moving a block that is covered by other blocks
• Moving a block onto a peg that contains smaller or equal-sized blocks than it
• Doing "null" moves (moves that don't do anything).

## Input:

Your input will consist of two numbers separated by a space.

The first number will be the starting peg. Pegs are zero-indexed (so the first peg is 0, and the last peg is 10).

The first number is valid only if the associated peg is not empty, and the block that's on the top of the peg is yours. Any other input is invalid, and your bot will be notified.

The second number will be the peg that your block is moving to. If the stack that the block is moving to is either:

• Empty, or
• Contains only larger blocks than the moving block

then the block can move. Otherwise, your bot will be notified that this is an invalid move.

Valid inputs (based on the starting position) would be:

• 0 4 (Moving the block on peg 0, which is R1, to peg 4)
• 0 3 (Moving the block on peg 0, which is R1, to peg 3)

Invalid inputs (again, based on the starting position) would be:

• 1 3 (Invalid because there are no blocks on peg 1)
• 10 3 (Invalid because the top block on peg 5, B1, is not yours)
• 0 0 (Invalid because that is a null move)

If 5 invalid inputs are committed by the bot in a row, that counts as an automatic loss.

## Output

The program will output to the bot what the current situation is - it will output the eleven arrays, each separated with the / symbol.

So, the starting position is like this:

R8R7R6R5R4R3R2R1//////////B8B7B6B5B4B3B2B1 (the middle nine stacks are empty).

## Point System:

• Win: 5 points
• Draw: -1 point (to discourage drawing)
• Loss: -5 points

I've made a small controller here.

## META STUFF

• Is this challenge a dupe?
• Is there anything I can clarify?
• Can anyone help with the controller (i.e. fix it up, optimise the code)?
• Issues with the code:
• Doesn't work with external files.
• Have you done a game-theoretic analysis to work out the value of the game? (I.e. without the turn limit, is it a win for player 1 or a draw?) – Peter Taylor Aug 20 '16 at 12:27
• @PeterTaylor See 2nd rule and 2nd bit of last rule (TBH, those were implemented just for this cause). I did a small analysis, and most of the rules put in place were to counter draws (because frankly, those aren't interesting). Is it possible that you could suggest any improvements to the game via the rules? This is the sandbox, after all. – clismique Aug 20 '16 at 12:30
• Cabt I trivially move back and forth, to be a nuisance to the other team? – Rohan Jhunjhunwala Aug 21 '16 at 0:22
• Oh never mind just saw the last rule – Rohan Jhunjhunwala Aug 21 '16 at 0:57
• It does seem like the game space is a bit small though – Rohan Jhunjhunwala Aug 21 '16 at 0:57
• @RohanJhunjhunwala Ummm... the rules don't exactly cover the "moving back and forth" thing, but it would be easy to find a counter to that. The game space is adequate enough - I can increase the size if needed. – clismique Aug 21 '16 at 1:08
• By game space I mean the complexity space as in the game tree complexity en.wikipedia.org/wiki/Game_complexity – Rohan Jhunjhunwala Aug 21 '16 at 1:11
• @trichoplax Fixed! – clismique Aug 21 '16 at 7:22
• @trichoplax Yeah, that's true... I wanted to make it so that multiple bots can play Hanoi at the same time (with multiple towers), but I'm mainly not bothered to improve on the bot in that way. I'm fairly sure that this will be fine in order to finish in a reasonable time. – clismique Aug 21 '16 at 7:49
• @trichoplax Fixed, again... also, implemented a controller. Can you help with it (if possible)? – clismique Aug 21 '16 at 8:09
• Now that there's a link to the controller others will be able to give you feedback on it. I won't be able to review it myself at the moment. – trichoplax Aug 21 '16 at 8:12

# Repetition

In a language called Repetition (something I just made up), there consists an infinite string of 12345678901234567890..., with 1234567890 repeating forever.

The following syntax is available to output numbers:

• +-*/: This inserts the operator into the string of repeating digits.
• Examples:
• + -> 1+2 = 3 (The + inserts a + between 1 and 2)
• +* -> 1+2*3 = 1+6 = 7 (Same as above, except two operators are used now)
• / -> 1/2 = 0 (Repetition uses integer division)
• Each operator is inserted so that it has one digit to its left, unless there are ~'s (see below).
• c: Concatenates with the next digit in the string.
• Examples:
• c+ -> 12+3 = 15 (The c "continues" the 1 and concatenates it with the next digit, 2, to form 12)
• +c -> 1+23 = 24
• (): Brackets for processing numbers.
• Examples:
• (c+)* -> (12+3)*4 = 15*4 = 60 (Repetition uses the order of operations)
• (c+)/c -> (12+3)/45 = 15/45 = 0
• s: Skip a number.
• s+ -> 2+3 = 5 (s skips 1)
• csc -> 124 (s skips 3, and c concatenates 12  with 4)

In the examples above, only a finite amount of digits in the infinite string are used. The number of digits used is equivalent to number of operators, concats and skips + 1.

Your task is, when given a string of Repetition code, output the result.

Examples of input and output are:

++ -> 6
- -> -1
(-)* -> -3
cscc -> 1245


This is code golf, so shortest code in bytes wins!

## Meta:

• Is this explained remotely well? Anything I need to clear up?
• Should this be a code golf or a metagolf challenge? I'm thinking of something like my previous challenge, There can be only 1!.
• I'd definitely like it to be a calculator implementation challenge – Destructible Lemon Sep 16 '16 at 8:32
• @DestructibleWatermelon Calculator implementation challenge? – clismique Sep 16 '16 at 8:47
• like this one – Destructible Lemon Sep 16 '16 at 9:02
• @DestructibleWatermelon So, a code-golf, then? – clismique Sep 16 '16 at 9:07
• I'd definitely love both a code-golf and a metagolf. – user48538 Sep 16 '16 at 11:17
• So, two separate challenges? – clismique Sep 16 '16 at 11:19
• Shouldn't the number of digits used be number of operators etc. + 1 – Riley Sep 16 '16 at 19:14
• @Riley Yeah, it should be. Thanks for catching that! – clismique Sep 16 '16 at 23:38
• I guess its tirvially possible to prove that all numbers can be generated like this, by adding a corresponding series of ones lol... negative numbers can start with ones and subtract (-n + 1) ones – Rohan Jhunjhunwala Sep 17 '16 at 0:03
• @RohanJhunjhunwala Yeah, that's true - which is where the metagolfing part comes in, and you have to golf down the output. The code golf doesn't really matter to that either, since you have to process input and return an output. – clismique Sep 17 '16 at 0:05

# Make an un-polyglot-able language!

The cops' task is to create a language that is as hard to polyglot as possible. However, when making a language, you must follow these rules:

• ASCII characters only.
• The language must fit our definition of programming language, i.e. it must be able to add two numbers together, and check, when given a numerical input, if a number is prime or not.
• You must post the adder and prime checker (the full program) into your answer, and they must be at most 1kb in size.
• You must post your full interpreter into the answer as well.
• Also, give a run-down of what each command in your language is and how your language works in general.
• You must complete the robbers' task, which is to create a polyglot of your language and a language from this list that outputs "Hello, World!". It must not exceed 5kb.
• If your language doesn't support ASCII output, you can write a program that outputs the ASCII character codes of each character of "Hello, World!".
• All four of the things above (interpreter, adder, prime checker and "Hello, World!" polyglot) MUST fit into your answer.
• After your challenge is Cracked, you must post your answer to the robbers' task.
• If your language has not been Cracked for over 7 days, then your language is Safe. You must put Safe in your header, and post your solution.

# {language name}, {cracked/safe} (<- the "cracked/safe" is only to be used
when your lang is either cracked or safe)

{language description}

{full interpreter}

{primality checker} (max 1kb)

{Hello World polyglot} (<- only posted if your lang is cracked or safe, max 5kb)


The robbers' task is to create a polyglot using any cops' language that outputs "Hello, World!".

• You must output the exact string "Hello, World!", nothing more and nothing less (except for leading and trailing linefeeds).
• If the cop's language doesn't support ASCII output, you may output the ASCII character codes of "Hello, World!".
• You only need to support two languages: the cops' one and one from this list of common languages.
• The final polyglot must not exceed 5kb.

# {language name}, {original author}, {bytecount}

{insert code here}

{description of code}

• Post a comment on the (in the cops' thread) language that you Cracked, linking them to your answer.

The winner will be:

• (Cops) the safe language that has the lowest byte-count for the "Hello, World!" polyglot. It will be declared after 1 month.
• (Robbers) the person who has cracked the most languages.

In case the language list changes, the languages are:

Java, Python, PHP, C#, Javascript, C++, C, Objective C, R, Swift, Matlab,
Ruby, VBA, Visual Basic, Scala, Perl, Lua, Delphi, Go, Haskell, Rust


## Meta:

• Is this challenge a dupe?
• Anything I can improve on?
• Interesting concept, but this needs some additional work. 1. I couldn't find the winning criterion for the robbers' challenge. 2. You'd somehow have to avoid languages that only compile if the source code has a specific hash. 3. The language list you link to changes every month(?); the challenge spec should be static. – Dennis Oct 7 '16 at 4:20
• Nothing seems to rule out a language where the program 'a' prints Hello world, 'b' adds numbers, 'c' checks primality, and any other programs do nothing. – xnor Oct 7 '16 at 4:43
• @xnor That problem is removed by the author having to make his/her own "Hello, World!" polyglot. – clismique Oct 7 '16 at 4:53
• Where you allow answers to print the character codes of Hello World, it's not clear whether in that case the mainstream language should also print character codes or still Hello, World!. – Martin Ender Oct 7 '16 at 21:04
• Could you specify tie breakers for both winning criteria (cops and robbers)? I guess first to post would work well for the cops, but for the robbers the tie breaker needs to be chosen carefully. If one person cracks 9 languages that are easy to crack, and another person later cracks 9 languages that are hard to crack, being earlier doesn't seem the ideal way to choose a winner. I can't think of a better way though. – trichoplax Oct 16 '16 at 9:13
• Is it worth specifying that the crack answer should link to the answer it is cracking? – trichoplax Oct 16 '16 at 9:18

## Show the Key Signature

Here is are the key signatures for the key of C♯ Major in the treble clef, and C♭ major in the bass clef:

           ♯
─────♯───────────────────────   ─────────────────────────────
♯
──────────────♯──────────────   ─────────────────────────────
♯                               ♭
───────────────────────♯─────   ──────────────♭──────────────
♯                                  ♭
─────────────────────────────   ─────♭───────────────────────
♭
─────────────────────────────   ─────────────────♭───────────
♭


A full list of key signatures can be found here. Hopefully you will notice that a) the sharps and flats are two notes lower in the bass clef as compared to the treble clef b) all key signatures can be obtained from the C♯ Major and C♭ Major key signatures by removing trailing sharps and flats appropriately.

Your task is, given a suitable representation of the clef and key, to output the appropriate key signature using the above format.

• Your output must have at least 11 lines, in order to accommodate all possible placings of sharps and flats.
• To compensate for the terrible aspect ratio, each sharp and flat must be separated by two columns, and there must be at least five empty columns at the beginning and end, but no more than 29 columns in total.
• You may use #, b and - characters instead of ♯, ♭ and ─.

This is , so the shortest solution wins!

• Can I adopt this abandoned challenge? – programmer5000 Jun 9 '17 at 12:07
• @programmer5000 Sorry, I'm not very good at checking back to see how my Sandbox posts are doing. As I don't have many questions myself, I'd rather be the person to ask it, if you don't mind. (But feel free to comment on any changes you think I should make first.) – Neil Jun 9 '17 at 12:25
• Ok sure. I think it is ready to post. – programmer5000 Jun 9 '17 at 12:26
• @programmer5000 Oh, I meant to ask, what input format do you think I should accept for the clef and key? Representing the key as a number between -7 and 7 feels like cheating to me. – Neil Jun 11 '17 at 21:15

The challenge is to write the fastest code possible for computing the permanent of a matrix.

The permanent of an n-by-n matrix A = (ai,j) is defined as

Here S_n represents the set of all permutations of [1, n].

As an example (from the wiki):

In this question matrices are all square and will only have the values -1 and 1 in them.

Examples

Input:

[[ 1 -1 -1  1]
[-1 -1 -1  1]
[-1  1 -1  1]
[ 1 -1 -1  1]]


Permanent:

-4


Input:

[[-1 -1 -1 -1]
[-1  1 -1 -1]
[ 1 -1 -1 -1]
[ 1 -1  1 -1]]


Permanent:

0


Input:

[[ 1 -1  1 -1 -1 -1 -1 -1]
[-1 -1  1  1 -1  1  1 -1]
[ 1 -1 -1 -1 -1  1  1  1]
[-1 -1 -1  1 -1  1  1  1]
[ 1 -1 -1  1  1  1  1 -1]
[-1  1 -1  1 -1  1  1 -1]
[ 1 -1  1 -1  1 -1  1 -1]
[-1 -1  1 -1  1  1  1  1]]


Permanent:

192


You should write code that, given an n by n matrix, outputs its permanent.

As I will need to test your code it would be helpful if you could give a simple way for me to give matrix as input to your code.

Be warned that the permanent can be large (the all 1s matrix is the extreme case).

Scores and ties

I will test your code on random +-1 matrices of increasing size and stop the first time your code takes more than 1 minute on my computer.

If two people get the same score then the winner is the one which is fastest for that value of n. If those are within 1 second of each other then it is the one posted first.

Languages and libraries

You can use any available language and libraries you like but no pre-existing function to compute the permanent. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.

Reference implementations

There is already a codegolf question question with lots of code in different languages for computing the permanent. Mathematica and Maple also both have permanent implementations if you can access those.

My Machine The timings will be run on my 64-bit machine. This is a standard ubuntu install with 8GB RAM, AMD FX-8350 Eight-Core Processor and Radeon HD 4250. This also means I need to be able to run your code.

• Is your system 64-bit? How much memory/disk space can we use? Could you add a reference implementation so that we might have something to initially compare against. – miles Oct 21 '16 at 5:28
• @miles Yes and I added some details to the question. – user9206 Oct 21 '16 at 7:45
• Thanks. Also I meant a reference implementation that strives to be efficient without using builtins. Most of the submissions from that challenge are very inefficient since the requirement was only up to 6x6 matrices. – miles Oct 21 '16 at 8:06
• @miles I see. I found this online bpaste.net/show/c346e05415f9 . I don't know if I am allowed to include it. – user9206 Oct 21 '16 at 10:34

This has been donated to the Secret Santa Sandbox if anyone wants to take up the mantle.

# Crazy Librarian's Interesting Numbers Game

Phew, you just managed to finish your code for the Arithmetic Sequence of Primes, and everything went swimmingly for your Crazy Librarian boss. Indeed, the math teacher taught the librarian a new card game as thanks for the prime sequences. However, the librarian wants to beat the math teacher at their own game, and so you're enlisted (again) to assist.

The card game was described as a two-player variation of a trick-taking game called California Jack. Each player is dealt a particular suit of cards from a standard US 52-card deck, and this forms their hand. A third suit of the cards is randomly shuffled and placed face-down between the players as the trophy deck. The fourth suit is unused. Each round, the top of the trophy deck is flipped face-up, and the two players select a card (in secret) from their hand to be their bid for that round, and places it face-down in front of them. The players reveal their bid card, and the higher card (aces low) wins the trophy card. The trophy card goes into the winner's trophy pile, and the two bid cards are discarded. If the players both bid the same card, neither gets the trophy card, and it is discarded along with both bid cards. The winner after all 13 rounds is whoever has the most points in their trophy pile, with Jack=11, Queen=12, and King=13. Note that it is possible for the game to end in a draw (including a zero-point draw).

Since you really want to impress the Crazy Librarian, you've ... enlisted ... the help of some of your friends, and you're going to create a bracket royale to find the best playing algorithm, and use that so the librarian can show up the math teacher.

### Questions for Meta

• Program I/O? I'm envisioning a stateful program that keeps track of its own cards, where each execution is a run of the game against an outside opponent -- e.g., each input is [W/L] T# that says whether the program Won or Lost the previous round, and what the current-round's Trophy card is. Then, the output would be what card it chooses to bid. Repeat 13 times. Could also do an interactive version, scraping STDOUT and setting STDIN?
• Example of a really simplistic algorithm (in pseudocode) -- return argv[1] -- this just bids the same as whatever the trophy card is.
• The programs could keep track of their opponent's total and their total, but the controller would have final say (obviously).
• I'm envisioning a double-bracket style, where each program is randomly seeded into the bracket. Best 3-of-5 games moves it to the next round, while the loser gets re-seeded into the loser's bracket and can re-win a chance for the final four.
• What am I missing?
• I think input could be expanded a bit. For instance, there doesn't seem to be any way to track your opponent's cards right now (just whether it won/lost the last), even though in an actual game they would be revealed (and would be part of any decent strategy I'd think). – Geobits Oct 9 '15 at 14:03

# Planting Sugarcane

In the game Minecraft the crop sugarcane can only be planted on a block that has water along one of its edges..

Given a area what is the most efficient way to place water such that every tile in the area is next to (does not include diagonals) a water block. That is how do you place water to maximize the amount of sugarcane that can be grown in that area.

For example if you had a small plus:

You could grow the most sugarcane if you put the water in the middle:

Or If you had a three by three square:

You could place six sugarcane:

Sometimes the best answer will still leave dirt patches.

For example:

Is best tiled as:

# I/O

Standard I/O applies.

You may take in an area as either an ASCII diagram with two distinct characters, one representing a block that is in the space and one representing a block that is not or a two dimensional data structure of truthy and falsy values representing the space.

You may output either output a ASCII diagrams with two distinct characters one representing water, and one representing everything else or a two dimensional data structure with truthy and falsy values with the truthy values representing the location of water.

You must also output the number of sugarcanes that can be planted with the scheme described.

## Scoring

This is you will be scored accordingly.

• You want to tighten up the spec a little bit. It's lind of vague as it stands – Conor O'Brien Aug 23 '16 at 23:00
• 1. Define "next to". 2. The closest dupe that I can think of is codegolf.stackexchange.com/q/17096/194 . They're both examples of (non-exact) set cover using a square lattice, but with different neighbourhoods. I would say it's just on the right side of the borderline, but others may disagree. – Peter Taylor Aug 24 '16 at 10:24
• In the second example, what makes it not be [[S,W,S],[W,S,S],[S,S,W]]? – Magic Octopus Urn Nov 1 '16 at 18:17
• @carusocomputing That is also a valid answer – Ad Hoc Garf Hunter Nov 1 '16 at 18:18
• Maybe instead of requiring them to output the explicit combination, have them calculate the maximum number of sugar cane possible. – Magic Octopus Urn Nov 1 '16 at 18:19

# Will the snake bump into itself?

Given a string containing NESW characters, check if a snake will bump into itself if it moves like this:

The snake starts out with length 2.

For every character in the string:

• If the character is N, move the head of the snake up one.
• If the character is E, move the head of the snake right one.
• If the character is S, move the head of the snake down one.
• If the character is W, move the head of the snake left one.

The rest of the snake follows the path of the head of the snake.

The snake grows 1 unit longer every 2 moves.

Your task is to determine if the snake will bump into itself, and give a truthy or falsey value accordingly.

### Truthy Inputs

NS
NWSSENW


### Falsey Inputs

NNN
SS
NWNNNWWWSSS
NWNNEEEESSS


More test cases coming soon.

• Does the snake move between inputs? – Gabriel Benamy Nov 23 '16 at 22:04

# Implement the sin function.

For those unfamiliar with trignometry. The sin function is a mathematical wave function, it can be defined a number of ways, but the canonical definition, is that it is sin(x) gives the ratio of the opposite side of an angle of measure (X) to the hypotenuse of a right triangle

Your job is to implement a program or function, that receives an angle (x) in degrees or radians, and outputs sin(x) to an accuracy of +/- .001 for at least the 360 degree values on a circle (or their radian equivalents). You may also specify a range that has width of a minimum of 360 degrees (or 2 pi radians) and require inputs to be converted to an equivalent angle to fit within that range. See the following table for outputs (multiples of 15 degrees are provided). You may not rely on any inbuilt library for trig functions. (i.e return Math.sin(x) is forbidden, or cos(90-x) or something similar 1/sqrt(tan(x-pi/2)^2+1)).

0|0.0|0.0
15|0.2617993877991494|0.25881904510252074
30|0.5235987755982988|0.49999999999999994
45|0.7853981633974483|0.7071067811865475
60|1.0471975511965976|0.8660254037844386
75|1.3089969389957472|0.9659258262890683
90|1.5707963267948966|1.0
105|1.8325957145940461|0.9659258262890683
120|2.0943951023931953|0.8660254037844387
135|2.356194490192345|0.7071067811865476
150|2.6179938779914944|0.49999999999999994
165|2.8797932657906435|0.258819045102521
180|3.141592653589793|1.2246467991473532E-16
195|3.4033920413889422|-0.25881904510252035
210|3.6651914291880923|-0.5000000000000001
225|3.9269908169872414|-0.7071067811865475
240|4.1887902047863905|-0.8660254037844385
255|4.4505895925855405|-0.9659258262890683
270|4.71238898038469|-1.0
285|4.974188368183839|-0.9659258262890684
300|5.235987755982989|-0.8660254037844386
315|5.497787143782138|-0.7071067811865477
330|5.759586531581287|-0.5000000000000004
345|6.021385919380437|-0.2588190451025207
360|6.283185307179586|-2.4492935982947064E-16


This is , but it aims to be a canonical list of trig function implementation in esolangs, especially those without a sin function built in. No answer may rely on a built in method.

• So you can just use a sin(x) builtin in your program? – user41805 Nov 24 '16 at 16:27
• @KritixiLithos sadly, yes. – Rohan Jhunjhunwala Nov 24 '16 at 16:40
• @KritixiLithos I believe it is frowned upon to outright ban certain built ins. – Rohan Jhunjhunwala Nov 24 '16 at 16:41
• @RohanJhunjhunwala I don't think it would be frowned upon to ban sin(x)-built-ins when the task is to implement exactly such built-ins. – Laikoni Nov 24 '16 at 17:49
• @Laikoni fixed. – Rohan Jhunjhunwala Nov 24 '16 at 19:03
• @KritixiLithos I banned built ins now. – Rohan Jhunjhunwala Nov 24 '16 at 19:04
• Related but not duplicate as the scoring is different. codegolf.stackexchange.com/q/30160/15599 @RohanJhunjhunwala what is frowned upon is "do x without y" challenges, which are often rather unimaginative "print this phrase without using the necessary letters." This is a "do x without x" challenge which is fine. You should ban all trig functions (otherwise I will just do cos x-90) and also complex numbers (I would do i**(x/90) and take the imaginary part.) – Level River St Nov 25 '16 at 0:21
• @LevelRiverSt I did ban all trig functions – Rohan Jhunjhunwala Nov 25 '16 at 4:37
• What about complex exponentiation builtins? Those have a very easy way to implement sin, but can be hard to ban as it's just basic arithmetic. – user62131 Jan 1 '17 at 10:08
• @ais523 that seems moderately more involved, and not agains tthe spirit of the challenge. I think I'll allow it. – Rohan Jhunjhunwala Jan 1 '17 at 13:14

# Dot matrix number visualization

Your task is to make a program that takes a number as input and outputs it as a wall of characters with spaces. The digits should be written like this:

  1    222   333     4  55555  666  77777  888   999   000
11   2   2 3   3   44  5     6   6     7 8   8 9   9 0   0
1 1       2     3  4 4  5555  6        7  8   8 9   9 0  00
1      2    33  4  4      5 6666    7    888   9999 0 0 0
1     2       3 44444     5 6   6  7    8   8     9 00  0
1    2    3   3    4  5   5 6   6  7    8   8 9   9 0   0
11111 22222  333     4   555   666   7     888   999   000


Each digit is represented as a grid of 5x7 characters consisting of spaces and the digit itself. The number should be written like above with a vertical line of spaces separating the different digits.

The preformatted text above should be the output of a 1234567890 number input. If you guys like this challenge, I'll post an image that better visualizes how each number should be printed.

Lowest size program wins.

Edit: Added a picture to better illustrate the digits.

• It's pretty clear what you're giving as the task, but an image would help, as the pre-formatted text is rather hard to read – TrojanByAccident Jan 17 '17 at 11:59
• @TrojanByAccident: It is pretty obvious what result the author wanted even without the image. – sergiol Jan 24 '17 at 17:34

## Powerful numbers integermath

Look at the number 81 expressed as the sum of distinct powers of the same base:

• 81 = 81 (well, duh)
• 81 = 80 + 1 (easy)
• 81 = 9*9
• 81 = 4*4*4 + 4*4 + 1
• 81 = 3*3*3*3
• 81 = 2*2*2*2*2*2 + 2*2*2*2 + 1 (if you thought that was obvious...)
• 81 = 1 + 1 + ... + 1 (yeah, yeah...)

As you can see, for N > 4, there are always 4 trivial bases: 1, 2, N-1 and N. Powerful numbers are those numbers which have at least one nontrivial base. Please write a program or function that, given a number N > 4, outputs a truthy or falsy value for whether a nontrivial base exists. The results for N up to 30 should be as follows:

(1  F)  16  T
(2  F)  17  T
(3  F)  18  F
(4  F)  19  F
5  F   20  T
6  F   21  T
7  F   22  F
8  F   23  F
9  T   24  F
10  T   25  T
11  F   26  T
12  T   27  T
13  T   28  T
14  F   29  F
15  F   30  T


This is , so the shortest solution wins!

• "Your challenge is, given a number N, to return the Nth Powerful number." I doubt that there's any way to generate the Nth number other than counting up from 1 and stopping once you've encountered N of them. So why not reduce it to "given a number, determine whether it's powerful"? – Martin Ender Jan 19 '17 at 12:13
• Simplified definition: "a powerful number is a number which can be written using only the digits 0 and 1 in any base other than 1, 2, n, or n-1." – user62131 Jan 19 '17 at 15:37
• I believe a (very golfed) reference implementation in ES6 to determine whether a number is powerful would be a=>(g=b=>b>1&&(f=c=>c&&c%b|f(c/b|0),f(a)<2)+g(b-1))(a)>3. This gives these first 1000 powerful numbers. The sequence doesn't seem to be on OEIS though. – ETHproductions Jan 19 '17 at 17:36
• @MartinEnder I was under the impression that it was more common to ask for the Nth or first N terms rather than just verifying a particular term. Perhaps if I ask for all Powerful numbers up to N? – Neil Jan 19 '17 at 21:01
• @Neil I think that's even worse. That way you make 100% sure that there's no way to avoid wrapping the entire program in a boring loop. – Martin Ender Jan 19 '17 at 21:10
• I like challenges like this better as a decision-problem, since that's what it comes down to. Outputting the Nth such number or the first N just adds extra code around the real meat of the challenge. – ETHproductions Jan 19 '17 at 22:03
• Example for first N terms: codegolf.stackexchange.com/questions/107420/… – Neil Jan 20 '17 at 9:45
• @MartinEnder OK, how about if, given an integer N greater than 1, the result should be the number of representations? – Neil Jan 20 '17 at 19:18
• @Neil That's fine, but I'm curious why you're so strongly opposed to making it a simple decision problem. :) – Martin Ender Jan 21 '17 at 14:38
• @MartinEnder You want people to add extra code to compare the result to 4 around the real meat of the challenge? (Sorry I couldn't resist!) – Neil Jan 21 '17 at 15:48
• Quoting me now, are you? :P But you don't actually have to count all of them since 4 are already given: 1, 2, n-1, and n. So all you really have to do in a decision-problem is check if there are any between 3 and n-2, inclusive. – ETHproductions Jan 21 '17 at 22:40
• That said, I'm not sure which path would be shorter in most langs. My attempts in JS for both versions of the problem turned out the same length. – ETHproductions Jan 21 '17 at 23:37
• @ETHproductions OK I'm convinced now. – Neil Jan 22 '17 at 1:08
• Related OEIS sequence – ETHproductions Jan 22 '17 at 22:23
• I actually don't know whether decision-problem would be better than just counting how many bases it's powerful in. There are arguments for and against each. My solutions turned out the same length in JS, but in Jelly the decision-problem solution came out as just 2 extra bytes added to an 8-byte counting solution. I guess it just comes down to what you want to see in the challenge. – ETHproductions Jan 23 '17 at 16:48

# Does Mathematica Have a Builtin?

Your task is to take in a question names and its tags; and to guess whether or not Mathematica has a builtin that solves that question.

## Rules

• Your code must be less than 100 bytes long.

• You may use internet to access the Mathematica reference guide you may also use the internet to access the tag wikis. Standard loopholes apply to internet access.

• For this challenge we will consider a valid builtin to be a builtin that does most of the computation for the challenge. Extra bytes spent on trivialities like IO formatting will be ignored.

• You must output a truthy value if Mathematica has a builtin to solve that challenge and a falsy value otherwise.

• If Mathematica has a builtin and for some reason the challenge does not allow Mathematica to compete or bans builtins your program must still output truthy.

## Scoring

This is a so you will be scored on the percentage questions here (This is currently a work in progress there will be more cases in the final question) that your program gets the correct answer on.

• As always with builtins, you'll want to outline exactly what counts as "built-in". For example, if a challenge is about printing hexagonal numbers, does using PolygonalNumber with fixing r = 6 count? (not sure if that's an accurate example, but you get the point). The test battery would make things 100% indisputable, but it's something you might want to think about when making the test battery. – Sp3000 Jan 26 '17 at 1:55
• On a side note, is a hardcoded approach okay, e.g. regex golfing the pass vs fail set? – Sp3000 Jan 26 '17 at 1:55
• @ETHproductions I meant the later, a function that does most of the work. I am not sure if I am going to write a super strict definition of builtin but I will be writing at least a loose one. – Ad Hoc Garf Hunter Jan 26 '17 at 1:57
• @Sp3000 Hardcoded is fine. I would like to see all sorts of approaches to this problem including regex. – Ad Hoc Garf Hunter Jan 26 '17 at 1:58
• My question codegolf.stackexchange.com/questions/107181/… was solved in Mathematica with a built-in that I wasn't expecting. That might be useful for your tests – Gareth Jan 26 '17 at 9:22
• Can you read the Mathematica answer off the page if it exists, or is the idea to only read the question? – xnor Jan 26 '17 at 9:40
• @Gareth Thanks I am in need of more test cases. – Ad Hoc Garf Hunter Jan 26 '17 at 12:52
• Answer: Hardcode truthy because Mathematica ALWAYS has a builtin :P – user42649 Apr 10 '17 at 13:05

# Minimal QWERTY

The task -- to output the layout of a QWERTY keyboard:

QWERTYUIOP
ASDFGHJKL
ZXCVBNM


But, you will be scored based on the length of your code, and on the number of distinct characters in it.

# Rules

1) The code must output the three lines of text above (or the text above with optional trailing newline)

2) Standard loophole restrictions apply

3) If the language contains predefined information about the QWERTY layout, you are not allowed to use that information.

# Scoring

The score will be defined as [Length of the program in bytes]*[# of distinct characters in the program], with lowest score winning.

For example, the code

ABAB1212


would have score 8*4=32 since it has length 8, but only 4 distinct characters: AB12

And the code:

ABC!!!{{{


Would have score 9*5=45, since it has length 9, and 5 distinct characters: ABC!{

• I really like this scoring system; it strikes a great balance between cutting down chars and cutting down the number of distinct chars you're using. I was going to say that this might not be the best way to use this scoring system, but anything other than "output this exact string" would likely be solvable in 10 bytes in golfing languages, or not solvable in 100 in non-golfing langs. (Perhaps a string with more repetition would work better though, but we won't know until the challenge is posted.) – ETHproductions May 6 '17 at 20:31
• About "If the language contains predefined information about the QWERTY layout, you are not allowed to use it.": does this mean you're not allowed to use the language, or just the QWERTY built-in? – ETHproductions May 6 '17 at 20:33
• @ETHproductions Thanks for the input! The reason I thought thought the QWERTY task would work well with this scoring system is that the output consists almost entirely of a large number of distinct characters (meaning any substantial use of string literals for the output would be very bad for the score), and those characters are fairly disordered, meaning a simple loop won't solve it. Do you have thoughts on other possible tasks for this scoring system? – Maria May 7 '17 at 1:54
• Regarding your second question -- the language would be allowed; they just wouldn't be allowed to use the predefined information. I've changed the wording to make that clear (I see that it was ambiguous before - thanks for catching that) – Maria May 7 '17 at 1:58
• May be too close to this challenge. It's not quite the same, but the basic task is similar (golf down a large set of distinct characters into a set of mostly repeated characters). This challenge is even closer, requesting printing a constant string with many distinct characters, and using the same scoring method; that's almost certainly a duplicate at this point. – user62131 May 7 '17 at 2:23
• @ComradeSparklePony I think this is covered by the condition to exclude this? – Paŭlo Ebermann May 7 '17 at 21:02
• @PaŭloEbermann Oops, I missed that. – Comrade SparklePony May 7 '17 at 21:05
• +1, when are you going to post this? – MD XF May 10 '17 at 1:22
• I kinda agree with @ETHproductions first comment regarding a string with more repetition and non-golfing languages. For example, to solve this in fewest bytes in Java 7 (I know, Java 7 is verbose as F.. xD), it will be: String r(){return"QWERTYUIOP\nASDFGHJKL\nZXCVBNM";} (score of 51 bytes * 41 unique characters = 2091). With fewest characters possible you'll abuse unicodes and it becomes pastebin.com/unrn6xj2 (too long for comment..), with a score of 343 bytes * 18 unique characters = 6174.. But of course, you're free to post it nonetheless as is. Java won't ever compete anyway ;) – Kevin Cruijssen May 10 '17 at 9:07
• But I like the scoring mechanism, and it's also a fairly easy challenge for most golfing languages, where the size vs unique characters really matters, which is of course the focus of code-golfing languages. So perhaps just post it, and I'll just score 2091 with my Java 7 answer. ;) – Kevin Cruijssen May 10 '17 at 9:10
• Japt, 4 points ;D :D – caird coinheringaahing May 19 '17 at 20:13

This message is open for anyone to adopt and post to main. For more details, see the chat room or meta post.

# Nonogram it

Nonograms are one of my favorite types of puzzles, but sometimes there are not enough of them to solve!

The challenge here is to write a program that would take an image and output the values for the columns and rows of the puzzle.

INPUT: black and white PNG on STDIN

OUTPUT: two lines with the values to create the puzzle. First line is the columns, second the rows. The format of both lines is: [a,b,c...],[d,...],...  (lists of integers separated with commas delimited with [], with each list separated by commas, ending in a newline. No dangling commas allowed inside the lists or at line end)

The squares on the image should be of 5x5px. The thereshold for determining if a square is filled is if it has at least 30% black inside it.

(3 sample images will be added later)

I'm not sure about the scoring for this challenge, most likely it should be a .

Additional scoring criteria I can think of:

• allowing to enter square size or cols*rows of the puzzle.
• accepting non black and white images
• providing a solver
• wait, is the PNG itself in the STDIN, or a file path to it? I assume the latter, but it's currently formulated as if it's the former. Also, the threshold needs to be clarified. Also, why is the image scaled up in the first place? – John Dvorak Mar 26 '14 at 19:59
• Also, I'd prefer an ascii-art input (a grid of hashes and spaces) than having the challenge complicated by looking up and interfacing an image manipulation API. – John Dvorak Mar 26 '14 at 20:02
• It could be a file path if that's more accesible. I didn't say the image was scaled, the 5*5 squares are for the grid to create the nonogram, just to avoid another required parameter(number of cols*rows desired). About the ascii-art, that would have no challenge, just a count() – Einacio Mar 27 '14 at 15:42
• I don't think a PNG library showoff is a good challenge for this site. There's no thinking present, just having to learn an API and hope it has short enough names. – John Dvorak Mar 27 '14 at 15:45
• I don't understand the 5x5 rule. Is it that there are 5x5 pixels in the image, and 5x5 pixels in the grid? 5x5s are no puzzles. – John Dvorak Mar 27 '14 at 15:46
• It wouldn't be the first challenge using PNG, so I see no problem there. About the grid, I'll prepare the example images later, I hope that'll be clearer to understand – Einacio Mar 27 '14 at 16:02
• Seeing that you prescribe exactly how black and white cells are to be determined, unique solubility of the resulting nonogram is no criterion? – Martin Ender Mar 31 '14 at 11:28
• @m.buettner I proposed the fixed grid and cell criterion with the idea of being able to check results against others. I forgot about ambiguous solutions, and I don't know how difficult is to test for it, specially if it ends as a code-golf. Maybe I should rule it out explicitly to keep answers simpler? – Einacio Mar 31 '14 at 14:18
• @Einacio well, uniqueness could be checked with a solver (there might be easier ways). I suppose you just have to decide whether you want soluble or comparable answers. If you are going for soluble, you can make this a "code challenge" and determine the score based on both code length and similarity to input image. – Martin Ender Mar 31 '14 at 14:58
• Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. – programmer5000 Jun 9 '17 at 16:29
• @programmer5000 Hi, I totally forgot about this challenge, I haven't had much free time in those 3 years to give it some love. I would be delighted to see someone pull it through, do I have to do something more than post it in the chat? – Einacio Jun 9 '17 at 19:40
• @Einacio just post a link to this answer and nothing else in that chat room. – programmer5000 Jun 9 '17 at 19:55

You are a robber in the ASCII world. ASCII lock-key work in similar fashion as the real-world: matching ridges. Your objective is to write a program which generates a duplicate key for the ASCII locks.

Example:

A Lock is given as:

   |\    |\
__| \___| \____
|               |
|_______________|


Its key shall be something like:

 _______________
|   __     __   |
|  |  \   |  \  |
|__|   \__|   \_|


The fit being something like:

 _______________
|   __     __   |
|  ||\\   ||\\  |
|__|| \\__|| \\_|
|               |
|_______________|


# SandBox

I think the fit is weird. It didn't go as I had imagined when I finished typing in the ASCII drawing.

• This has potential, but it needs a clear specification as to what a fit is, and what constitutes a lock (i.e. some constraint on the input). – VisualMelon Jun 14 '17 at 17:47
• Yes. This is very incomplete/unclear as of yet. – officialaimm Jun 15 '17 at 3:27

# Sandbox

This will be my first kolmogorov-complexity submission, does this question fall under that category?

Is the question clear enough?

Is it too trivial?

# Problem

Given no input write a program or a function that outputs or returns the following string:

(<(<>(<>.(<>.<(<>.<>(<>.<>)<>.<>)>.<>).<>)<>)>)

# Rules

• Shortest program wins.
• Trailing whitespace allowed.
• Trailing newlines allowed.
• Unused parameters for functions allowed.
• Can you give more context to the string you're outputting, its significance etc? – Pureferret Jun 15 '17 at 11:24
• It's a poor ASCII representation of a crowd of blank stares a single person being (<>.<>) – LiefdeWen Jun 15 '17 at 11:25
• a more common representation being (-_(-_(-_(-_(-_-)_-)_-)_-)_-) – Skidsdev Jun 15 '17 at 11:28
• @Mayube Yes, I just used a broader face so the outputted string is longer – LiefdeWen Jun 15 '17 at 11:29

## When did I need to be born to celebrate a magic birthday?

I was born in 1984 and in 2016 I became 32 years old, which is 20 in base 16, what a coincidence!

Your task is, given the year of interest -say 2016- , to calculate the year I had to be born to be able to say In 2016 I have celebrated/I will celebrate my 20th birthday (in base 16).

1. take n-digit decimal number - the year xy.
2. Split it in half, if n is odd, the digit the middle is appended to number side.
3. Calculate the year I had to be born to be x base ys old in the year of xy.

Your code shall return Not-a-Number or error message if the decomposition cannot be resolved.

Walkthough:

>  foo(2016)
1: '2016' -> '20' '16'
2: 20 base 16 = 32
3: 2016-32 = 1984
>> 1984

> foo(445)
1: '445' ->'44' '5'
2: 44 base 5 = 24
3: 445-24 = 421
>> 421

>foo(7)
1: '7' -> '7' ''
Error, base not defined
>> nan

>foo(10)
1: '10' -> '1' '0'
Error, base 0 don't exist
>> nan

>foo(1805)
1: '1805'->'18' '5'
Syntax error
>> nan


Test cases:

 7    : nan/error
10    : nan/error
78    : 71
445   : 421
1024  : 1000
1805  : nan/error
1936  : 1891
1984  : 1891
1999  : 1891
2016  : 1984
2015  : 1985
10002 : 9998
10912 : 10759
116015: 115769


Shortest answer in bytes wins. Standard loopholes apply.

• Boo-urns to input validation! Can you add a full example? – Shaggy Jun 21 '17 at 16:14
• Do you mean full ungolfed code or full path from, say 445 to 421? – Crowley Jun 21 '17 at 16:25
• Just a walkthrough of how to get from input to output. – Shaggy Jun 21 '17 at 16:26
• @Shaggy Thanks for sugegstion. Is it better now? – Crowley Jun 21 '17 at 17:16
• Shouldn't 1999 result in 1891? – Emigna Jun 22 '17 at 8:49
• @Emigna Correct. Updated. – Crowley Jun 22 '17 at 13:36

# Don't step on a crack, or you'll break your mother's back

Earlier I was walking down the sidewalk in my town, which is made of concrete slabs and looks something like this (note: not my sidewalk). I decided to try to pace myself such that I didn't step on the little cracks between the concrete slabs. For simplicity, let's say:

• Each slab is 4 feet long.
• Each of my feet is 1 foot long.
• Each crack has 0 width (just like your neighbors' dog).

My natural stride is about 3 feet, which worked out quite well:

(Excuse my horrible MS Paint skills)

Then I got a little ambitious and decided to take 4-foot strides. This obviously worked out even more nicely (aside from making my legs feel weird):

This got me thinking, what other lengths of strides could I take? One non-integer example would be 2⅔ feet:

I could go as short as 1-foot strides, though anything shorter than 1 foot would place my foot-long foot on every crack in the sidewalk. (I didn't do 1-foot strides because I would look weird shuffling down the sidewalk, and also because I was in a rush.)

In fact, there are 6 possible crack-avoiding strides up to four feet: 1, 1⅓, 2, 2⅔, 3, 4.

# Challenge

Given a integer concrete slab length 0 < n < 100, output all stride lengths up to n that I could take on that theoretical sidewalk. Assume I can stretch my legs infinitely far (I am a mathematician, after all).

More mathematically, given an input integer 0 < n < 100, output all numbers 0 < k <= n such that no multiple of k, modulated by n, is greater than n - 1.

Expected outputs for inputs 1 through 9 (rounded to 4 decimal places):

1: [1]
2: [1, 2]
3: [1, 1.5, 2, 3]
4: [1, 1.3333, 2, 2.6667, 3, 4]
5: [1, 1.25, 1.6667, 2, 2.5, 3, 3.3333, 3.75, 4, 5]
6: [1, 1.2, 1.5, 2, 2.4, 3, 3.6, 4, 4.5, 4.8, 5, 6]
7: [1, 1.1667, 1.4, 1.75, 2, 2.3333, 2.8, 3, 3.5, 4, 4.2, 4.6667, 5, 5.25, 5.6, 5.8333, 6, 7]
8: [1, 1.1429, 1.3333, 1.6, 2, 2.2857, 2.6667, 3, 3.2, 3.4286, 4, 4.5714, 4.8, 5, 5.3333, 5.7143, 6, 6.4, 6.6667, 6.8571, 7, 8]
9: [1, 1.125, 1.2857, 1.5, 1.8, 2, 2.25, 2.5714, 3, 3.375, 3.6, 3.8571, 4, 4.5, 5, 5.1429, 5.4, 5.625, 6, 6.4286, 6.75, 7, 7.2, 7.5, 7.7143, 7.875, 8, 9]


The expected output for 99 can be found in this Gist. The length of each output corresponds to A002088.

## Rules

• The input will be a positive integer less than 100.
• The output may be presented in any reasonable format. Entries can be represented as decimal numbers accurate to at least 3 decimal places, or as exact fractions if desired.
• The output may be unsorted, but it may not contain duplicates.

This is , so the shortest code in bytes in each language wins.

• It took me a bit to identify that a foot is 1 foot long. I'd make that more clear. – Nathan Merrill Jul 7 '17 at 17:52
• @NathanMerrill For a second I thought that you were joking :P Should be more clear now. – ETHproductions Jul 7 '17 at 18:33
• output should always be less or equal to input. am i underestood correctly – tsh Jul 7 '17 at 23:46
• @tsh Right, I've clarified that a little more. – ETHproductions Jul 7 '17 at 23:52

# TL;DR:

Given a set of strings, determine whether the characters expose a total ordering based on location in the strings.

In this challenge, strings are used as a predicate to determine the order in which characters should appear in this set. For example, the string

"ONE"

Says:

• All instances of "N" should appear only after instances of "O"

• All instances of "E" should appear only after instances of "N"

By this reasoning, the string "FOOOONZAi.EE" follows this ordering, but "NEEEE3#?EAO" does not (there is an "O" after an "N").

Your challenge is to take a set of strings and determine whether these strings define a total ordering without any logical flaws. This would occur as a cycle of any length, such as:

...or such as:

etc.

Rather than strings, you may take in lists of characters or integers if you wish.

Since this is a , you may output any two consistent values for yes or no, such as true and false, zero and non-zero, exception and no exception, etc. Just specify your output format in your answer.

# Test Cases

["ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX"] -> true (one possible ordering is "TWFOUIVXNHRE")
["ZERO", "FOUR"] -> false ("R" must follow "O", but "O" must follow "U" which must follow "R")
["", ".", "forty", "this->~why();", " -y."] -> true
["AB", "BC", "CD", "DE", "AC", "BD", "CE", "EA"] -> false

(more can be written if needed)


# Scoring

This is , so the shortest answer in each language wins.

# Sandbox

How can I make this more clear? Any suggestions?

• This could be more general if you allow lists as input rather than strings. – lirtosiast Jul 13 '17 at 22:18
• @lirtosiast So a list of lists of characters? – musicman523 Jul 14 '17 at 0:52
• I would recommend lists of integers instead of strings. I feel the challenge would be "cleaner" that way, but that's up to you. Also, you should have a test case where where each pair is consistent but the whole set isn't. – Zgarb Jul 15 '17 at 7:17
• Is this not effectively the same as your previous challenge of whether a directed graph has a cycle? – xnor Jul 16 '17 at 1:19
• @xnor I suppose it is, though I think the challenging part is collecting the edges by vertex. How about this: I rewrite the challenge to be "Give a valid ordering for a set of strings, guaranteed that one exists"? – musicman523 Jul 16 '17 at 3:49
• @musicman523 I remember a DAG sorting challenge, I think that would be a dupe of it. – xnor Jul 16 '17 at 3:52

# Self-Improvement

You must create a self-mutable program that, when run, outputs a non-zero integer and also overwrites the file with a program that outputs double the number.

For example, if I run the program self-improvement and it outputs 10, it must output 20 when I run it the second time, output 40 the next time, and so on.

• You must not rely on any file on the computer other than your program.
• Said program must consist of only one file.
• Of course, no loopholes that are banned from the entire site.
• You can assume that your program won't go tested beyond the range -2^16 to 2^16-1.
• no loopholes banned -> no loopholes that are banned, overwrite -> overwrites. Also, something on how far this needs to go might be important - does it have to work infinitely, or only to INT_MAX for the language in question? If you choose the second option, keep in mind language with very small numeric caps. Otherwise, welcome to PPCG, I really like this question, and I'm glad you Sandbox'd it :) – Stephen Jul 17 '17 at 21:33
• @StepHen Thanks; I decided that they can assume that the parameters won't go beyond INT_MAX. – Lawful Lazy Jul 17 '17 at 21:38
• In case anyone needs to find it at some point, don't forget about this standard loophole. – Stephen Jul 17 '17 at 22:24
• @Artyer I stated "any nonzero integer". That excludes 0. – Lawful Lazy Jul 17 '17 at 22:55
• @LawfulLazy I didn't read that too well. – Artyer Jul 17 '17 at 22:58
• @Artyer I'll make sure to embolden it. I've also set a minimum integer range for StepHen. – Lawful Lazy Jul 17 '17 at 22:59

# Deduplicate equivalent expressions

Suppose we wanted to generate all expressions containing at most 2 of + and −. We might have a list like this:

a + b + c         b + c + a
a + b - c         b + c - a
a - b + c         b - c + a
a - b - c         b - c - a
a + c + b         c + a + b
a + c - b         c + a - b
a - c + b         c - a + b
a - c - b         c - a - b
b + a + c         c + b + a
b + a - c         c + b - a
b - a + c         c - b + a
b - a - c         c - b - a


There is a lot of repetition here. It surely isn't necessary to include all of a + b + c, a + c + b, b + a + c, b + c + a, c + a + b, and c + b + a, since they all mean the same thing. This can be deduced from knowing that, for any x and y, x + y is the same as y + x.

Similarly, b + a - c and a - c + b are equivalent. To deduce this, one must know that, for any x and y, x - y is the same as x + (-y).

Let's assume the following:

[1]: a + b == b + a
[2]: a - b == a + -b


Then, we can deduce that b + a - c and a - c + b are equivalent:

start:  b + a - c
b + a + -c        by 2
a + b + -c        by 1
a + -c + b        by 1
end:    a - c + b         by 2


Therefore, they are the same. After performing similar proofs, we are left with the list:

a + b + c
a + b - c
a - b + c
a - b - c
b - a + c
b - c - a
c - b - a


## Definition of an expression

An expression can be described as:

variable   = "a" | "b" | "c" | ... | "y" | "z";
digit      = "0" | "1" | "2" | ... | "8" | "9";
number     = digit . digit*;
operator   = "!" | "#" | "$" | "%" | "&" | "*" | "+" | "~" | "-" | "." | "/" | ":" | ";" | "<" | "=" | ">" | "?" | "@" | "^" | "_" | "" | "|"; data = number | variable; subexpr = data | operator* . data; expression = subexpr | subexpr . operator . expression;  Where | suggests alternatives, . suggests concatenation (with potential whitespace around each operand), * suggests "0 or more times", and " is a string literal. x + y, j * i - 3, u & 4 * 2 < ~4, q % ~*^t and r are all expressions. You should assume all operators are left-associative. ## Definition of assumptions An assumption is a pair of expressions said to be equivalent. This means one can be transformed into the other. When performing a transformation using an assumption, one replaces all the appropriate variables and maintains the numbers as they are. (These "variables" can also be sub-expressions, which is any expression not using an operator in the assumption.) For example, if the assumption is !a == a + 5, then one can transform t + 5 into !t and 3 + 5 into !3. Another example: if the assumption is a + b == a * b @ b, then 5 + 2 can become 5 * 2 @ 2 and z * 3 @ 3 can become z + 3, but z * 4 @ a cannot be reduced further using this rule. One last example: if the assumption is a < b == a, then 1 + 3 & 5 < 2 * 3 + 6 would become 1 + 3 & 5, and 1 + 2 < x + y < 7$ q would become 1 + 2, since it would be equivalent to (1 + 2) < (x + y) < (7 \$ q), which is thus 1 + 2.

If either side of the assumption is a single variable, numbers are excluded from this assumption. E.g., the assumption a == 3 would only apply to variables.

## Expression equality

Two expressions are equal if they can be proven to be the same. Variables must be the same for each expression; for example, a + b is not by default the same as b + c.

## Challenge

Your task is to remove "duplicate" expressions given some assumptions. You can use any unambiguous symbol or method, including taking a pair of strings, to represent an expression. The expressions remaining in the result do not necessarily have to be in the set, but must be equivalent by the given assumptions. E.g., if you have a + b - c and b - c + a in the input, you can have -c + b + a represent these in the resultant set. You should try each equation in the order that it's given to you (to simulate "precedence").

The input consists of a list of assumptions and a list of input expressions. The input expressions can be an array or container of strings or string pointers, or in any way standard to your language. (E.g., for C, one should expect null-terminated strings.) The input format must be consistent for all runs.

The output can be a list representation (as is standard to your language), can be separated by newlines (\r, \n, and \r\n are acceptable), or separated by commas. The output format must be consistent between runs.

This is a , so the shortest program in bytes wins.

## Test cases

Every output is merely an example, and is not the only valid output.

Assumptions: { e1 == e2, e3 == e4, ... eN-1 == eN }
Input: { expr1, expr2, ... exprN }
Output: { expr1, expr2, ..., exprK }

Assumptions: { "a + b" == "b + a" }
Input: { "3 + 4", "4 + 3", "5 * a", "a + 2", "2 * a", "a * 5", "a + b", "2 + a" }
Output: { "3 + 4", "5 * a", "a + 2", "2 * a", "a * 5", "a + b" }

Assumptions: { "a + 0" == "a", "a * 1" == "a", "a * b" == "b * a", "a + b" == "b + a" }
Input: { "1 * 2 * 3", "3 * 2 + 0", "1 + 2 + 3" }
Output: { "1 * 2 * 3", "1 + 2 + 3" }
OR: { "2 * 3", "1 + 2 + 3" }

Assumptions: { "~a" == "a ~ a" }
Input: { "~z", "z ~ z", "~a", "~~a", "a ~ a ~ a ~ a" }
Output: { "~a", "~z", "~~a" }

Assumptions: { "a + b" == "0" }
Input: { "x + y", "0", "3 + y + a + v + k", "75", "4 + 2" }
Output: { "0", "75" }

Assumptions: { }
Input: { "x + y", "x + y", "y + x", "3", "3 ! 3" }
Output: { "x + y", "y + x", "3", "3 ! 3" }

Assumptions: { "j" == "3" }
Input: { "v + t", "z", "q", "q + r + t", "4 + 2" }
Output: { "v + t", "z", "q + r + t", "4 + 2" }

Assumptions: { "a" == "b" }
Input: { "a", "b + c", "e % t", "q & t", "!3", "z" }
Output: { "a", "b + c", "e % t", "q & t", "!3" }

Assumptions: { "1 & 0" == "0", "1 & 1" == "1", "0 & 0" == "0", "a & b" == "b & a", "0 ? a : b" == "b", "1 ? a : b" == "a" }
Input: { "1 & 1 & 0", "j & k", "y & z", "z & y", "1 & 0 ? k & j : 0" }
Output: { "0", "j & k", "y & z" }

• Several of your expressions are inconsistently quoted. I also think you should explain what should happen when the assumption is something like 3 == a. Would I remove one of: 5, 7? It seems if you had a == b as the assumption you would, but the other one is counter-intuitive to me. Also, a == b is rather odd on its own, perhaps that is also a good test case. Also, the empty assumption if you intend to allow it. – FryAmTheEggman Jul 17 '17 at 3:18
• @FryAmTheEggman Could you clarify your first question? Are you asking what should happen if 5, 7 is the input given the assumption a == 3? – Conor O'Brien Jul 17 '17 at 4:00
• Yes, that's what I meant. – FryAmTheEggman Jul 17 '17 at 4:08
• 1. subexpr = data | operator* . data; is surely equivalent to just subexpr = operator* . data;? 2. For the second test case it would be more illustrative to include an example output like { "0 * 2 + 3", "1 + 2 + 3" }. 3. I'm not sure what you mean by "If either side of the assumption is a single variable, numbers are excluded from this assumption". Is it that an assumption a == 3 with input {"b == 2", "c == 2", "4 == 2"} should give output e.g. {"3 == 2", "4 == 2"} rather than {"3 == 2"}? – Peter Taylor Jul 17 '17 at 7:43
• @PeterTaylor 1. yeah, I original had * mean "1 or more"; will fix. 2. good idea. 3. Well, the way that input would be parsed is b = = 2, with a binary = followed by a unary =. Could you perhaps use a different symbol? I don't quite understand your confusion. – Conor O'Brien Jul 17 '17 at 16:53
• Sure: assumptions: { "a" == "3" }; input: {"b + 2", "c + 2", "4 + 2"}. Is {"3 + 2", "4 + 2"} the correct output? – Peter Taylor Jul 17 '17 at 18:03
• @PeterTaylor Yes, it is. – Conor O'Brien Jul 17 '17 at 18:34
• The definition of assumptions includes an assumption with more than one operator, but none of the test cases do. I would think that's an important thing to test. – Peter Taylor Jul 26 '17 at 11:06
• @PeterTaylor Added. – Conor O'Brien Jul 26 '17 at 19:32

# Levenshtein distance using only SO titles code-golf

Pick 1 or as many titles as you wish from revisions of questions from Stack Overflow. You now have a tuple of all of the characters used in the titles you picked. You may add up to as many newline characters as titles you picked. Using exactly all the elements (characters) in this tuple (you may chose lower or upper versions of each character) write a program or a code snippet that computes the Levenshtein distance between two strings.

That's it. Happy title hunting!

## Clarifications and rules:

### Revisions

• We define a revision as seen on https://stackoverflow.com/posts/XXX/revisions
• for a question without any revision (not edited after being posted), the question itself counts as a revision
• all revisions are eligible, from the initial posted question to the current version of the question
• the revision must be created before 10PM 21 July GMT (before the time of posting this challenge on the sandbox)
• only questions from Stack Overflow qualify (no meta, no other site)
• deleted questions qualify (the only exception: spam questions don't qualify). I realize not everybody has access to deleted questions, but a question can become deleted after you post so I decided to allow it, especial considering the very large number of non-deleted questions: you have where to pick from.
• you may pick one revision multiple times. You may pick multiple revisions from the same question.

For instance you pick these hypothetical titles from valid revisions:

• To be?
• ...Or not to be? you pick this one 3x
• Pls. help me!!

Then the tuple you have is this (between "):

"            !!..........????bbbbeeeeeehllmnnnoooooooOOOpPrrrsttttttT"


to which you may add up to 5 new line characters.

You must use all of these characters (nothing less, nothing more) to write your code. In this example your code must contain exactly 12 (space) characters, 2 ! characters, 10 . characters, 4 ? characters, 4 b/B characters etc.

Lower/upper case: regardless of the character case in the title, you may use any case you want for each. In this example you can use (4 b) or (3 b and 1 B) or (2 b and 2 B) or (1 b and 3 B) or (4 B). Upper/lower as defined on http://www.fileformat.info - Unicode data table

Here are all the character you must use in this example:

+----+-----+
|    |  12 |
|  ! |   2 |
|  . |  10 |
|  ? |   4 |
|  b |   4 |
|  e |   6 |
|  h |   1 |
|  l |   2 |
|  m |   1 |
|  n |   3 |
|  o |  10 |
|  p |   2 |
|  r |   3 |
|  s |   1 |
|  t |   7 |
| \n | 0-5 |
+----+-----+


### Code

• You may write a program or a function and use any of the standard methods of input/output.
• input must be 2 strings
• you can assume both of the 2 strings are not empty
• you cannot take other input
• output must be a number representing the Levenshtein distance between the two strings as defined on wikipedia. You may output leading and trailing white spaces (including new lines).
• you must not output anything else
• You may use any programming language, but note that these loopholes are forbidden by default

### Score

This is , so the shortest valid answer – measured in bytes – wins.

## Format

In order to make it easy on everybody, please:

• link the revisions you use
• show each title
• show the final tuple of characters

Meta discussion:

• Should I encourage/discourage/ban using titles already picked by someone else?
• This seems easily abused using comments or other non-executing code. – KSmarts Jul 24 '17 at 15:17
• @KSmarts yes, you would use comments and non executing code, but it will count to your score. If you need to pick a 20 chars title just to get a certain symbol and the rest of the characters you don't use (you put them after a comment start) then maybe that is not a good deal, isn't it? – bolov Jul 24 '17 at 15:59

Challenge: Count integers 1 to 10, but slowly on a time delay.

Your challenge is to print the integers 1 to 10 to the screen with each integer separated by a newline, but on a time delay, such that it should take “n” seconds before the integer “n” is printed to the screen. For example, the program will wait 1 second before printing 1 and a newline, and then the program will wait 2 seconds before print 2 and a newline, and then the program will wait 3 seconds before print 3 and a newline.

So the expected standard output to the screen is this:

1
2
3
4
5
6
7
8
9
10


But the program will patiently wait “n” seconds before printing the integer “n” to the screen, so as your program may interpret it as …

waiting 1 second …

1


waiting 2 seconds …

2


waiting 3 seconds …

3


, and so on …

Restrictions:

1) Since some programming languages may not have a sense of system time, you are not allowed to use any modules/libraries/functions which can measure the time of your program within your program. Therefore all programming languages can be used. This restriction puts all the programming languages on an equal level.

2) Restriction 1 makes it such that you are required to write a function which takes about 1 second to process, and then you can rerun that function “n” integer of times before printing the next integer “n” in 1 to 10 to the screen. You can call your function whatever you want or if you can get away without naming the function then you can do that, too. So, your program would see this behind the scenes:

performing function fx 1 time. #which the arbitrary function fx takes about 1 second to process.

1


performing function fx 2 times

2


performing function fx 3 times

3


… and so on

3) Therefore, your program should take about 1 + 2 + 3 + 4 … + 10 = 55 seconds to finish printing all the integers from 1 to 10 to the screen. Since you need to write a function that takes about 1 second to process, acceptable solutions can be off by plus or minus 2 seconds from 55 seconds.

4) You must time your script which counts the integers 1 to 10 on a delay, so you can use any external program to time your script. I recommend using the bash function time, and giving me the “real” time or actual elapsed time of your script in seconds. If you time your script another way, tell me how you did it. Give me three digits after the decimal place for the real time in seconds. Do not round or truncate.

winning condition:

The winning condition is the fastest program in terms of actual elapsed real time in seconds which is closest to 55 seconds. If, for example, one submission is 54.9 seconds and another is 55.1 seconds, the 55.1 second submission wins because 54.9 seconds is too fast. Again, the point of this program is to slowly print integers to the screen.

Again, it should take approximately 55 +/- 2 seconds to print the integers 1 to 10 to the screen.

• I modified my problem in such a way that no programming language should have an advantage. – xyz123 Jul 28 '17 at 6:17
• you are not allowed to use any modules/libraries/functions which can measure the time of your program Does this mean things like Stopwatch, getting the DateTime, Thread.Sleep, etc? – TheLethalCoder Jul 28 '17 at 9:56
• Nice challenge by the way but I'm not sure I like the winning condition. What's wrong with a code-golf? Also if I was you I'd trim some of the fluff down, at the moment there is a lot of text to information. – TheLethalCoder Jul 28 '17 at 10:00
• Will this not also vary dependent on what machine is running it? I really like the idea but I can imagine it being quite hard to test - especially with that winning condition, as I can imagine it coming down to hundredths of seconds, which would doubtlessly vary depending on the computer running it. Really like the idea nonetheless – space junk Jul 28 '17 at 11:01
• I suppose you could do it by only running them on TIO? TIO's time limit is 60 seconds so you'll have ample time, & it should be a bit more uniform in terms of processing time. – space junk Jul 28 '17 at 11:02
• Yes, TheLethalCoder you would not be allowed to do that. After I thought about, I realize that different computers may have different specifications for runtimes, although I suppose the winning condition could be the least number of bytes, but I was thinking about setting the winning condition to the fastest program which is closest to 55 seconds because if somebody wrote a program which had less bytes, but it was 1.9 seconds over 55 seconds, then it might be too slow for a lot of the other programs which had more bytes, but were faster. – xyz123 Jul 28 '17 at 15:08
• Although if I set the winning condition to the least number of bytes, then I believe that I would have to increase the restraint to acceptable programs cannot be off by +/- 1 second from 55 seconds. – xyz123 Jul 28 '17 at 15:09

# Random number from 0 to n

## Challenge

Write a program/function that, given a positive integer n, outputs a uniformly random integer from 0 to n.

### Input

• Input will be a positive (non-zero) integer.
• It will be in your language's number handling capabilities. // reword

### Output

• Output must be a uniformly (pseudo)random integer.
• Every integer in the range [0, n) must have an equal chance of being outputted.
• You may assume that your chosen language's built-in RNG is uniform.
• Must be in 0 to n, in [0, n), ≥ 0 and < n

### Specifications

• Standard I/O rules apply.
• Standard loopholes are forbidden.
• This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
• Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
• Built-in functions that perform this task are allowed but including a solution that doesn't rely on a built-in is encouraged.
• Explanations, even for "practical" languages, are encouraged.

## Test cases

Note that this challenge is tagged and hence will have non-deterministic outputs.

Incoming!

# Sandbox

• We seriously don't have this already?!
• Interesting idea, but how will the test cases work? Also I imagine builtins will be the shortest for many languages – Chris_Rands Aug 9 '17 at 8:39
• @Chris_Rands not all challenges need test cases. – TheLethalCoder Aug 9 '17 at 10:27
• Definition of random? We don't have it because it's a bad idea. – feersum Aug 9 '17 at 11:32
• @Chris_Rands They're going to be random test cases. :P And yes, built-ins, but I'm afraid I don't like banning built-ins. – totallyhuman Aug 9 '17 at 12:39
• @feersum Yeah, I have to iterate over that better. Basically, it has to be uniformly pseudo-random. Any suggestions? – totallyhuman Aug 9 '17 at 12:41
• @AdmBorkBork If you do find a dupe, please let me know! I've searched everywhere and asked in chat, but I couldn't find one. – totallyhuman Aug 9 '17 at 12:42
• Extremely closely related – AdmBorkBork Aug 9 '17 at 12:54
• @AdmBorkBork Aha, I didn't find that (probably because it isn't tagged with number :P). It's very close but it has some arbitrary restrictions... Good enough to have a regular one? – totallyhuman Aug 9 '17 at 13:19
• The only way an answer can be valid here and fail the "arbitrary restrictions" there is if it's a trivial call to a built-in, so this question doesn't add anything to the site. – Peter Taylor Aug 9 '17 at 14:12
• Now define pseudorandom. Also, using a hardware random generator is not allowed? – feersum Aug 9 '17 at 14:16
• @feersum I am not sure how much more I can define "random". I have edited in the fact that you can assume that your language's RNG is uniform. Where have I disallowed hardware random generators? – totallyhuman Aug 10 '17 at 2:07
• it has to be uniformly pseudo-random Pseudorandom is not random. – feersum Aug 10 '17 at 12:23
• So now the only definition of "random" we have is that built-ins that are designated as random number generators are considered "random". So the challenge can only be answered by builtins, since there is no other definition provided. – feersum Aug 10 '17 at 12:24
• @totallyhuman What if the language has a built-in RNG which is not a uniform RNG? – isaacg Aug 12 '17 at 13:09

# Modular multiplicative inverse

Your task is to given two integer numbers, a and b calculate the modular multiplicative inverse of a modulo b, if it exists.

The modular inverse of a modulo b is a number c such that ac ≡ 1 (mod b). This number is unique modulo b for any pair of a and b. It exists only if the greatest common divisor of a and b is 1.

## Input and Output

Input is given as either two integers or a list of two integers. Your program should output either a single number, the modular multiplicative inverse that is in the interval 0 < c < b, or a value indicating there is no inverse. The value can be anything, except a number in the range (0,b), and may also be an exception. The value should however be the same for cases in which there is no inverse.

0 < a < b can be assumed

## Rules

• The program should finish at some point, and should solve each test case in less than 60 seconds
• Standard loopholes apply

## Test cases

Test cases below are given in the format, a, b -> output

1, 2 -> 1
3, 6 -> Does not exist
7, 87 -> 25
25, 87 -> 7
2, 91 -> 46
13, 91 -> Does not exist
19, 1212393831 -> 701912218
31, 73714876143 -> 45180085378
3, 73714876143 -> Does not exist


# Scoring

This is code golf, so the shortest code for each language wins.

• I would've thought this would be a duplicate, but it doesn't look like it is. In particular, this challenge is different. – isaacg Aug 20 '17 at 22:21
• Clarification: Can answers throw an error if there is no inverse? Can they loop forever? – isaacg Aug 20 '17 at 22:21
• @isaacg Thought that as well, was really surprised when I could not find any duplicate. – Halvard Hummel Aug 21 '17 at 6:14
• @isaacg Added some clarification to the text. Allowed errors, but the answers should stop at some point. Also made them have to solve each test case in 60 seconds, as otherwise the challenge would become a bit easy (basically looping over all the possible values) – Halvard Hummel Aug 21 '17 at 6:16

# n-gon in m-gon

What is the greatest equilateral triangle you can fit into a regular pentagon? This is what this challenge is about, but with regular n-gons/m-gons.

### Challenge

Given two integers m,n greater or equal to 3, find the maximal ratio of the areas of the two polygons such that the m-gon is completely contained in the n-gon.

### Details

We are always talking about regular polygons, this means that all sides have the same length and all vertices are on a circle. The output can be a floating point-, fixed point- or rational number and must be correct to three decimal places.

### Examples

 m  n  ratio (area m-gon / area n-gon)
x  x  1 (for all x)
3  4  1/4*sqrt(3) = 0.4330
4  3  12/(7*sqrt(3)+12) = 0.4974
3  6  1/2 = 0.5
6  3  2/3 = 0.6667



Would be nice to have larger examples.

• You may consider changing the language of the initial problem specification and input/output chart to specify that you are comparing the areas of the m- and n- gons – Taylor Scott Sep 26 '17 at 21:37
• I see what you mean but right now I have difficulty coming up with a better wording (english is not my native language), if you have a better suggestion feel free to directly edit it! – flawr Sep 26 '17 at 22:39

I bet I can write down your PIN! 0000 0001 0002 0003 ... 9999.

## Task: Write a program that outputs a string containing all possible four digit PINs.

The string should not contain any whitespace (trailing newline is okay).

## Explanation

The output string only needs to contain each PIN somewhere in it; digits can be reused. For instance the string “123456789” contains the PINs 1234, 2345,3456,4567,5678,and 6789. By reusing digits, it's possible to save a significant amount of space from the naive implementation (0000000100020003...9999).

At best, this could be written as a 10,003 digit string. 4 digit for the first PIN, then one more digit for the other 9999 PINs.

I've written a basic Python script that can check your solution and indicate any PINs you are missing.

import sys
passes = True
for ix in range(10000):
pin = "%04d" % (ix)
if s.find(pin) == -1:
print("Missing PIN %s" % pin)
passes = False

if passes:
print('Result passes!')
print('String length is %d characters.' % len(s))

• Nice, but I think you need to replace code-golf with code-challenge as this isn't just scored by shortest code. – Adám Sep 28 '17 at 22:25
• Very related – H.PWiz Sep 28 '17 at 22:29
• This is just codegolf.stackexchange.com/q/42728/194 with hard-coded input, and hence qualifies as a dupe. – Peter Taylor Sep 29 '17 at 11:08
• Too bad it's a duplicate... but now I know about De Bruijn sequences! – Dominic A. Sep 29 '17 at 23:19
• @PeterTaylor: I think there's one even more dupey than that; I've been trying to find it all day. The "background" to it was a keypad on a building door that had a 4-digit code. – Shaggy Sep 30 '17 at 0:59

## Roll identical boson dice code-golfrandom

When you roll two dice, the chance of a 5 and 6 in either order is a 2 in 36 (or 1/18), since it could happen as (5,6) or (6,5). But (6,6) can only happen one way and has a 1 in 36 chance.

Our dice will instead work as identical bosons: (5,6) and (6,5) are a single outcome {5,6} that is equally likely to {6,6}. So, each of these 21 unordered pairs is equally likely, with chance 1/21.

{1,1}, {1,2}, {1,3}, {1,4}, {1,5}, {1,6}, {2,2}, {2,3}, {2,4}, {2,5}, {2,6}, {3,3}, {3,4}, {3,5}, {3,6}, {4,4}, {4,5}, {4,6}, {5,5}, {5,6}, {6,6}


Similarly, for 3 dice, [5,5,6], [5,6,5], and [6,5,5] all count as a single outcome {5,5,6}, but [6,5,6] is different.

Task: Output a random roll of n boson dice, so that each possible result is equally likely as an unordered multiset, i.e. when sorted.

It's OK if your output is ordered as long as the overall probabilities are right. You may sometimes output [5,6] and sometimes [6,5] as long as their total chance is 1/21. They don't have to each be 1/42 chance. You could output [5,6] with 1/21 chance and never [6,5].

Input: A positive integer n

Output: A random list of n numbers from 1 to 6, so that each outcome is equally like when taken as an unordered multiset.

Time restriction: Your code has work up to n=50 within 1 minute.

• I think it's unlikely that there'll be an algorithm for this terser than simply constructing the list of all possibilities, then selecting a random element from it. As such, I'm not sure the randomness adds to the task here. It's possible I'm wrong. (I toyed with some methods of restricting complexity to ban this solution, but I couldn't find one I was satisfied with.) – user62131 Jun 22 '17 at 22:48
• @ais523 I know some fairly nice methods to generate these directly, but I don't know if they'll beat out the boring one you suggest. Rolling repeatedly until sorted is also boring and direct. Maybe a complexity restriction is needed. I'll see what I can golf up. – xnor Jun 23 '17 at 7:24
• with the (new) time restriction this is more like math-golf than code-golf. Can you give away any of your "nice methods"? Is it the weighted probability of every digit of the 50-digit number ,one of them? – user72269 Oct 2 '17 at 17:29

## Limited-Information Maze-Solving Bot

(Still in draft/beta format. Feedback welcome.)

Based on a challenge idea I posted in chat and the ensuing conversation. Thanks to NathanMerrill, zgarb, and Jonathan Frech for assistance in fleshing this out.

### The challenge

You're writing two separate programs/functions/routines/etc. The first, which we'll call the helper program, takes the input maze and calls the second, which we'll call the solving bot. The solving bot must solve the maze based on its interaction with the helper program.

The maze is 51x51 characters in size. For clarity in this challenge description, it is composed of # walls and   corridors, but you can use any two distinct, consistent ASCII characters of your choice. E.g., use ! for walls and x for corridors, use 1 for walls and 0 for corridors, etc. This maze is one of many that will be the input to your helper program/function.

The maze start is always guaranteed to be somewhere on the left-most column, and the exit is always guaranteed to be somewhere on the right-most column. The maze is guaranteed to have at least one path from the start to the exit. As a result of this construction, the very top row and very bottom row are all #, and the very left and right columns are all # except for the start and exit.

The solving bot that you're creating needs to find a solution to the maze (not necessarily the shortest), but is limited in that it can only "see" a new 5x5 section of the maze at a time. The bot is scored by how many times it needs to request a new 5x5 section from the helper program/function.

The upper bound is obviously to simply request every possible 5x5 section, for a score of around 100. The lower bound is where someone with perfect knowledge of the maze can request only those 5x5 sections containing the exact route of the shortest solution, possibly as low as 10. Your bot will be run through (1000?) different mazes, and the bot with the fewest total requests will be the winner.

The solving bot is placed on the left-hand side where the start is, and the first 5x5 section is provided for free. However, the bot doesn't know where, vertically, it is on the left-hand side of the maze. It could be in the top corner (as in the example below), in the bottom corner, or anywhere in between.

### Input/Output

The code you're writing be required to take the maze as an input (STDIN, a file to read, etc.) and call a subroutine of some sort for the solution bot.

Input: (1000?) 51x51 mazes Output: How many total requests your solving bot took

Yes, this is a non-observable requirement to be on the honor system and ensure the two "halves" of your program (i.e., the I/O half and the solving half) talk to each other correctly and accurately. I trust the community enough to believe that this is OK.

### Further rules

Your solving bot should be deterministic. That is, when presented with the same maze two or more times, it should request the same number of 5x5 sections.

### Example Maze

(generated from http://www.delorie.com/game-room/mazes/genmaze.cgi )

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


Example starting block:

#####

# ###
#   #
### #

• Does the solving bot also have to find the maze's start by scanning the left side or is it placed at the start position? – Jonathan Frech Sep 17 '17 at 19:18
• related – Liam Sep 17 '17 at 21:47
• @JonathanFrech Good point. We'll say that it's placed at the start position and the first 5x5 area is free. – AdmBorkBork Sep 18 '17 at 16:39
• You could maybe only use one space wide corridors, as the second space does not add any information and thus you do not really get a true 5x5 section of the maze. Just a thought, though. – Jonathan Frech Sep 25 '17 at 11:50
• @JonathanFrech No, that's a good point. I went with double-wide corridors since it looks more even with the character height, but looks aren't important when doing this challenge. I'll update the sizing. – AdmBorkBork Sep 25 '17 at 15:54
• Are this maze's dimensions not 51x51? – Jonathan Frech Sep 25 '17 at 16:29
• @JonathanFrech Apparently, with that generator, a size 50 doesn't yield a size 50. I'll either find a different generator or make my own for the actual challenge. Thanks! – AdmBorkBork Sep 25 '17 at 17:28
• I think the problem does not lie in the generator; it lies in the maze's nature. If your corridors are always one character wide and you have walls on the far left and far right, your maze size has to be odd. – Jonathan Frech Sep 25 '17 at 19:13
• Does this allow for "relative" vision? As in, after we get the initial block we would request "The next block to the right" instead of "the block at (2,7)"? – Kamil Drakari Sep 26 '17 at 20:22
• @KamilDrakari Sure, that would be allowed. It's dependent upon how that half of your submission works. – AdmBorkBork Sep 26 '17 at 20:32
• @JonathanFrech Good point. Maybe I'll compromise and make it a 51x51 maze. Thanks for the insight. – AdmBorkBork Sep 26 '17 at 20:32