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

# Is this bitstring divisible by 3?

Your challenge is to write a program or function that, given a string of bits representing a positive integer, outputs or returns a truthy value if it's divisible by 3, and a falsy value otherwise.

## Rules

• You may not convert the input to a number in any way. You may manipulate the string or loop through each digit, so long as you don't convert it to your language's native number type.
• Input may be given as a string or an array of digits.

### Truthy examples

11
110
1001
1100
1111
10010
10101
11011
111111
10010011
1010010001
10101010101
100100101010001011110101010001
1000000000000000000000000000000000000000000000000001
1111111111111111111111111111111111111111111111111111
11000001001011110010001010001001010110000010100001001000100101
1111001111110010001110111011001010100100001000110100010011101011110010010111100111011100110101000011100110011111001010000111011110010111000100001010101001000001111011011111000101001111010010010010000110101100011001011111111000111001110110011011101010011000


### Falsy examples

1
10
100
101
111
1000
1010
1011
1101
10000
11111
10101010101011
1101001000100001000001000000100000001
10000000000000000000000000000000000000000000000000001
11111111111111111111111111111111111111111111111111111
11000001001011110010001010001001010110000010100001001000100110
1101011111110011110010011101010011000001101011001111001001011010100000000110001111001101100000001010010111100111000101001001000011100000110111010010100000100001100101110000011010000010110010101011110010100110101100000011101101010000010011000001001001010101


# Sandbox questions

Obviously as a Do X without Y question this is walking a very fine line. There are several string manipulation techniques (which I won't spoil here) that I'd like to see used, rather than solutions that just loop through the string and repeatedly add a digit and take modulo 3. I could be more strict and not allow any numbers in the process, but I don't know if that's a good idea... Suggestions? Is it even possible to make this a good challenge?

• This is going to be very hard to specify cleanly and still leave possible in most languages. E.g. in Java I can't loop through each digit without converting it to a native number type, because char is a native number type. (Well, I might be able to use a regex to split it into one-character strings, but that would be a crazy requirement). – Peter Taylor Feb 25 '17 at 20:13
• I think it should be possible to treat each digit as a number, just not the full string. – Leo Feb 26 '17 at 14:14

# The Mass Murderers of Josephus

Everyone knows the Josephus challenge and its setup: you arrange n people in a circle, and the first person kills the second, and from then on the first alive person to the right of the previous "killer" kills the next alive person to their right. For example, with four people:

  1
4   2    (4 people in a loop)
3

1
4        (1 kills 2)
3

1
(3 is closest to the right of the previous killer 1,
3       and kills 4, who is to the right)

1      (1 is closest to the right of the previous killer 3,
and kills 3, who is to the right)


The last remaining person is 1, in this case.

Your task, however, is to find the most murderous of these people - or whoever killed the most people. In the above example, the "murderer" is 1, who killed 2 people: 2 and 3.

In a bigger example, of 10 people (this is a line of 10 people, right wraps around to the left):

PEOPLE ALIVE  | KILL TALLY
1 2 3 4 5 6 7 |
1   3 4 5 6 7 | 1: 1
1   3   5 6 7 | 1, 3: 1
1   3   5   7 | 1, 3, 5: 1
3   5   7 | 1, 3, 5, 7: 1
3       7 | 3: 2; 1, 5, 7: 1
7 | 3, 7: 2; 1, 5: 1


There's a tie for the person with the most kills: when a scenario like this arises, the answer is average of all the people with the most kills - in this case, it is (3 + 7) / 2 = 5.

You must make a program or function that takes one input, the amount of people in the circle, and output the murderer (or the average of multiple murderers).

## Rules and specs:

• The input will never be above 2^31 - 1.
• The input is guaranteed to be a positive integer.
• Your program must work out 100 within the timeframe of TIO (60 seconds). If you're not using TIO, provide an interpreter for me to test your program on (preferably an online one).
• Averaging multiple murderers seems really artificial. I recommend either outputting the list of all most-murderous people, or saying that any of them can be the single output. Once such a change is made, I'd upvote this proposal! – Greg Martin Mar 5 '17 at 19:51
• Borderline, but IMO this is a dupe of codegolf.stackexchange.com/q/64667/194 or codegolf.stackexchange.com/q/5891/194. If n in binary starts 10 there's a unique murderer, and it's just the Josephus problem; if n in binary starts 11 there's a tie between two people, who are the last two people to die (simple variant on the first candidate dupe); or alternatively the last one to die is the standard Josephus problem, the second-last to die differs in the most significant bit of n (e.g. in the example n=7 the most significant bit is 4 and the murderers differ by 4). – Peter Taylor Mar 5 '17 at 23:31

# Chemistry 101

## Question

Given the atomic number of an element in the range [1-118] print out the group and period, of that element as given by the following Periodic Table Of Elements.

For elements in the Lanthanide and Actinide series, (ranges [58-71] and [90-103]), you should instead print L for the Lanthanides and A for the Actinides

You may write a program or a function and use any of the our standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

[Source] I couldn't have put it better!

[Source]

## Test Cases

The output here separates the group and period with a single space

| Input | Output |
|   1   |  1 1   |
|   33  |  15 4  |
|   45  |  8 5   |
|   71  |  L     |
|   93  |  A     |
|   117 |  17 7  |


## Scoring

Simple . Shortest number of bytes wins

• I'd suggest replacing the table with a text-based one. Otherwise, you're probably good to go. You should allow more flexible output, though. Not everyone likes converting their arrays to string. – John Dvorak Mar 8 '17 at 11:22
• Thanks for the feedback. I'm happy to be flexible on the output, but curious as to what benefit a text based table would provide over the image? Mobile users? – James Webster Mar 8 '17 at 11:24
• Mobile users, yes. Also, low-bandwidth users and people sitting behind overly restrictive firewalls. Not an issue here, but text is easier to edit than images. Also, prevents issues if imgur ever decides to start deleting images. – John Dvorak Mar 8 '17 at 11:35
• Point taken. I'll wait to see if this question is well received before I type up (or find) a text based version! – James Webster Mar 8 '17 at 11:36
• You should allow non-string output as well. Remember that answerers may submit functions instead of full programs. – John Dvorak Mar 8 '17 at 11:37
• I would like to maintain that the result is printed rather than just returned, but otherwise, I don't specifically mention data types. – James Webster Mar 8 '17 at 11:39
• Why would you do that? It's but an inconvenience for the answerers, not a challenge. Also, there are languages where functions can't have side effects - they can only return IO actions that the caller may execute or discard. – John Dvorak Mar 8 '17 at 11:42
• I think it's probably because I haven't used any of those languages. I conceed! – James Webster Mar 8 '17 at 11:49
• In Haskell: the interesting part is f x = (foo x, bar x). With string output it's f x = show (foo x, bar x). As an IO action it's f x = print (foo x, bar x) but now the type is now IO() instead of (Int, Int) or String. A full program is f x = (foo x, bar x); main = readIO >> print.f - unless the compiler can't infer that x is a number, in which case you have to add that bit somewhere, too. – John Dvorak Mar 8 '17 at 11:58
• Rather than a text-based table I would say that since there are only 118 possible inputs you might as well just provide an exhaustive test suite. – Peter Taylor Mar 9 '17 at 8:59
• @PeterTaylor that makes me think of - do we have a tag for a finite number of possible inputs? – John Dvorak Mar 9 '17 at 17:24

# Background

In the land of Android, there exists a password type that looks like this:

It's essentially a connect-the-dots for a password. Today, we'll be making art with it.

Your program should export as many distinct combinations of pattern lock as image files with the following specifications:

1. Images should be 500x500 pixels large.
2. Dots should be located at positions (x, y):
• (125, 125)
• (125, 250)
• (125, 375)
• (250, 125)
• (250, 250)
• (250, 375)
• (375, 125)
• (375, 250)
• (375, 375)
3. Lines should be drawn with a circular brush head of radius 8px.
4. Background color and line color may be any color of your choosing, but must not be the same color and it must be consistent.
5. The pattern should pass through all points ONCE, with the exception of the first point, which should be the first and last point drawn from/to.

# Examples

The following output is valid (starts at top-left):

The following output is valid:

The following output is invalid:

This breaks condition 5 (repeat use of top-left, middle, and middle-left).

The following output is also invalid:

This passes through the top left twice and the start point is not the same as the end point (breaks rule 5 twice).

# Scoring

The program with the largest number of distinct outputs wins, with the shortest program being the tiebreak.

• "The program with the largest number of distinct outputs wins, with the shortest program being the tiebreak." Some simple math gives that there are 362880 possible permutations (9 options for the starting point, 8 options where to go next, 7 options left for the next point...). I think that most, if not all, answers would opt to produce all of these. Makes me wonder how an answer would deal with outputting all these images. Also, it would probably be useful to add a link to the I/O rules: [x](http://meta.codegolf.stackexchange.com/q/2447/13486 "Default for Code Golf: Input/Output methods") – user2428118 Mar 11 '17 at 11:05
• @user2428118 So... roughly 1.5 GB of images per run on my machine. Not bad. – Addison Crump Mar 11 '17 at 11:59
• @user2428118 Also, that math doesn't hold, considering that choosing to go from one corner to any of the others forces pathing through intermediate points, so there are slightly fewer than that many options. – Addison Crump Mar 11 '17 at 12:02
• What do you mean by distinct? There are many lock patterns that are visually the same but require a different path to be made. – Wheat Wizard Mar 12 '17 at 17:48
• Also I don't believe that your first two outputs can be made. A closed loop is not possible on the android lock screen. – Wheat Wizard Mar 12 '17 at 17:50
• In fact, reading your specification a little more thoroughly, I don't believe that the patterns you are describing are really all that similar to the Android lock screen. – Wheat Wizard Mar 12 '17 at 17:52
• @WheatWizard It's similar - I have added the "closed loop" to the spec to increase difficulty and to sate my perfectionism. – Addison Crump Mar 13 '17 at 23:01
• You should still specify what types of moves are legal a little more thoroughly because there are a bunch of niche moves that can be done with the android lock screen that are not clear from your post. Especially if you change some aspects of the way they work. – Wheat Wizard Mar 13 '17 at 23:07

## All your base are belong to us 6 * 9 = 42

When Douglas Adams wrote THHGTTG, he just made up a formula for the answer to Life, the Universe and Everything. And then some spoilsport pointed out that it was a valid formula... when interpreted in base 13.

Given an input formula, please output as many bases as you can find where the formula is valid.

You must at a minimum support base 10 to base 16 inclusive, but you are strongly recommended to support base 2 to at least base 36.

You must at a minimum support the ()*+= operators, but you are strongly recommended to support - and /, and either ** or ^ for exponentiation. Note that the division will always be exact in valid bases, but may not be exact in invalid bases, so for 11/2=8 you should only output 15.

Examples

11/2=8
15

10+10=10*10
2

6*9=42
13

11**11=2101
3


This is , so the shortest answer that breaks no standard loopholes wins.

• As Many Bases as possible seems, annoying... – ATaco Mar 14 '17 at 1:52
• "You must at minimum do this, but you are strongly recommended to also do that" doesn't sound like a great formula for challenges... I'd try to choose a fixed set of requirements and stick to that. – Leo Mar 14 '17 at 10:26
• Suggestions numbered for ease of reference. 1. I think the notation would be clearer with 0 1 2 instead of t u b. 2. Ideally a question should be self-contained. There's plenty of room in the 30k character limit to explain what the trees are rather than relying on external links. 3. I would guess that answers should take a parameter n and enumerate the unary-binary trees M(n), but the question can also be interpreted as wanting infinite output of M(1), M(2), ... This should be explicit. – Peter Taylor Mar 7 '17 at 15:59
• I'll going to make a moderately large edit reordering some stuff. If you don't like it you can revert it. – Peter Taylor Mar 7 '17 at 21:34
• @PeterTaylor Thanks!!! Much appreciated. – Guy Coder Mar 7 '17 at 22:11
• You say the output format is flexible, but does it have to list the node type 0, 1, or 2 in some form? Could each node just be a list that contains 0, 1, or 2 sublists? – xnor Mar 7 '17 at 22:20
• It's always worth leaving something in the sandbox for at least 48 hours (longer at weekends) because other people might spot other ambiguities (as xnor has just demonstrated). – Peter Taylor Mar 7 '17 at 22:34
• @GuyCoder No, I mean like [[[]][]] for (2 (1 0) 0). – xnor Mar 7 '17 at 22:35

# Image Quine code-golf

The challenge is to quite simply, output an image of the source code of your program exactly as it is.

Scoring is by shortest source code wins.

The image must visibly contain the source code, and no other characters or decorations.

Standard quine rules apply, so:
- No 0-byte solutions
- No reading the source code

This is just a draft, so I'll make it more detailed should it be good enough to post.

# Block Puzzle

A popular brain teaser commonly known as a the "IQ Block Puzzle" is comprised of 8 colored shapes which can be rotated, moved and flipped on a 8x8 grid. The puzzle is known as a geometric magic square.

# Challenge

The challenge is to generate and then output all 40 possible pattern combinations that the pieces can be placed in.

The output can be in any form, but must somehow represent the position of all pieces, for example:

Combination 1 of 40:

11113333
12213333
12214444
22555448
22555448
66657788
66657788
66777788

...


There will be a winner for both:

• Shortest code in bytes
• Fastest calculation of all shapes in ms
• How can you beat a simple print statement? – Blue Mar 23 '17 at 19:45
• That looks interesting but may require additional specifications. For instance, do the 40 patterns include symmetrical/rotated solutions? Including the actual shapes of the pieces as ASCII (or whatever) rather than relying on the picture alone would also help. Otherwise looks good! – Arnauld Mar 23 '17 at 19:47
• I forgot: I don't think having two distinct winning criteria is a good idea. – Arnauld Mar 23 '17 at 20:00
• It should be clarified that the shapes in the sample output are the actual shapes that the program should operate with. Also, this doesn't work as fastest-code; it's highly likely to be fastest to hardcode the output (with the only interesting part of the challenge being the fastest way to output a medium-length constant string, which is actually non-obvious). – user62131 Mar 24 '17 at 14:35

# Self-Generator code-challengequine

Challenge: Create a program that, given no input, outputs n programs (in the same language, but not necessarily the same language as the original program) separated by newlines, where each of those programs will print a section of the original program. When these sections are put together, it create the original program.

Your score is the number of bytes in the original program divided by (the number of sections that your code is split into) squared.

• hm, this looks pretty interesting. The problem is, it may easily be won by a short answer with only a couple output programs. – Rɪᴋᴇʀ Mar 23 '17 at 16:07
• Good point. Do you have any scoring ideas? – user42649 Mar 23 '17 at 16:08
• Not at the moment, sadly. I have a very similar one in the sandbox, it's been mostly abandoned for a while though. (not a dupe though, by any means) I've been trying to think of a scoring criterion, and I'll keep thinking for your post also. – Rɪᴋᴇʀ Mar 23 '17 at 16:12
• Also, this isn't code-golf. That tag is for pure bytecount scoring, not formulas. Doesn't matter if it's supposed to be a shortest program. – Rɪᴋᴇʀ Mar 23 '17 at 16:12
• @Riker Oh, okay. Thanks. And oh, I came up with the scoring system after putting the [code-golf] tag first... whoops... thanks for catching that! – user42649 Mar 23 '17 at 16:13
• Perhaps square the number of sections? 20/3 is considerably less appealing than 20/(3**2) – ETHproductions Mar 23 '17 at 16:36
• @ETHproductions Perhaps that would be a better option. I'll consider that. – user42649 Mar 23 '17 at 16:38
• I think in many languages just putting the standard quine on as many lines as you please would work just fine. You might want to do something to ensure that the parts of the program are unique (perhaps say that no section can be its own quine?) – ETHproductions Mar 23 '17 at 17:45
• Isn't it fairly easy to score zero in the limit here, with the squared sections? In most languages, simply writing n copies of a standard quine will give you a score of (length of the quine) / n (because each copy of the quine will output the quine itself, then each of those outputs will output itself (being a quine), thus all those outputs can be combined back into the original program). It might need a few tweaks for newline handling (e.g. adding a duplicate newline at the end of the program) but those are easy enough to make. – user62131 Mar 24 '17 at 14:32

# Average of a tune

Often times when I'm bored, I'll find I have a catchy tune from a song stuck in my head. Then I notice the fingers on my right hand moving as if playing that tune on a piano. If I have nothing better to do, I'll spend some time calculating where on the scale I need to play so that all five fingers get optimal usage. For example, given the tune

C4 C4 G4 G4 A4 A4 G4 F4 F4 E4 E4 D4 D4 C4


I try to center the notes such that if they were weights arranged on a board, the board would balance on my middle finger. (That's probably not a tune I'd have stuck in my head, but you get the idea.) In this case, the notes can be arranged like so:

C4          G4
C4 D4 E4 F4 G4 A4
C4 D4 E4 F4 G4 A4
=================


Now we have to balance the board. If the fulcrum is placed under E4, it will be equivalent to summing the following weights:

-2          +2
-2 -1  0 +1 +2 +3
-2 -1  0 +1 +2 +3


The result is +6, indicating that the board is leaning to the right. So we try moving right so that the fulcrum is under F4, which gives us the following:

-3          +1
-3 -2 -1  0 +1 +2
-3 -2 -1  0 +1 +2


The sum is -8, indicating that the board is leaning to the left, and also leaning further than it had before; therefore, the optimal middle note is E4.

By this point I've usually wasted all the time I had at my disposal, plus a good bit more. So your task is to write a program or function that does this calculation for me. Since I have more important things to waste my memory on, your code should be as short as possible.

Write a program or function which takes in a list of notes and outputs the average of these notes.

• Only notes on the scale of C major (C, D, E, F, G, A, B) should be taken into account; you never need to deal with sharps or flats.
• The notes can range from C0 to B9, inclusive; you'll never get A-1 or C12.
• The input can be given as an array, or as a string separated by spaces, newlines, commas, etc.
• The input will always contain at least one note.
• Input/output can be given in whichever case is desired. If your code only accepts one case or the other, make a note of this in your answer.
• If there are two valid outputs for a given input, you may output either or both.

## Test cases

Input -> Output(s)
C3 -> C3
C0 -> C0
B9 -> B9
C3 C3 -> C3
C3 D3 -> C3 or D3
C3 E3 -> D3
C0 B9 -> B4 or C5
C3 C3 C3 -> C3
C3 C3 D3 -> C3
C3 C3 E3 -> D3
C4 D4 E4 F4 -> D4 or E4
E4 E4 E4 C4 E4 G4 G3 -> D4
C3 D3 E3 F3 G3 A3 B3 C4 -> F3 or G3
C3 C3 E3 F3 G3 A3 B3 C4 -> F3
A3 A3 A3 C4 A3 A3 A3 A3 G3 F3 E3 -> A3
C5 D4 C4 C5 D4 C4 A4 C5 D4 C4 C5 D4 C4 -> F4
C4 C4 G4 G4 A4 A4 G4 F4 F4 E4 E4 D4 D4 C4 -> E4
E3 E3 F3 G3 G3 F3 E3 D3 C3 C3 D3 E3 E3 D3 D3 -> E3
C4 C4 E4 E4 A3 A3 C4 C4 F3 F3 A3 A3 G3 G3 B3 B3 -> B3
C3 C3 E4 E4 A2 A2 C4 C4 F2 F2 A3 A3 G2 G2 B3 B3 -> E3
A3 A3 A3 G3 A3 A3 A3 B3 B3 C4 C4 C4 B3 C4 G4 G4 B3 B3 -> B3
G3 G3 A3 G3 C4 B3 G3 G3 A3 G3 D4 C4 G3 G3 G4 E4 C4 B3 A3 F4 F4 E4 C4 D4 E4 -> B3
B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 B9 A6 -> A9


(Imaginary bonus point for each song you recognize)

## Scoring

Since this is , the shortest code in bytes in each language wins.

# Sandbox questions

• Is there a plain "average of an array of integers" challenge, and would this be a duplicate?
• Is anything unclear, or does any information need to be added?
• Suggestions for a title? I feel like there's a "tuna fish" pun waiting to be made...
• Suggestions for test cases?

# Normal quine, weird quine

Note: This Sandbox entry has a fairly long history, and is basically an attempt to produce a challenge inspired by this comment, but that's immune to wilful misinterpretation (or misunderstanding) of what counts as an error in order to trivialise the question.

## Background

In the world of programming languages, there are lots of different ways to produce output on the usual output streams. Most languages have a way to print a string intentionally, called print, write, or something like that. Sometimes you can even just leave a value to be printed implicitly. Most languages also have situations in which the implementation interjects with its own output, e.g. warnings produced during the compile. We'll call this weird output.

For each method of output to standard output or standard error in a programming language, consider how much of that output is under the programmer's control and thus can contain arbitrary text (e.g. specified as a parameter, part of the program's filename, taken from a variable that can be assigned to, or the like), as opposed to being a single possibility (or a finite set of possibilities) hardcoded into the interpreter. We'll call this output method normal if no more than 3 bytes are outside the programmer's control; and weird if there are 4 or more hardcoded bytes that the programmer cannot control.

In this challenge, you need to write a full program that's a variant, obeying the proper quine rules. Specifically, after performing the entire process of building and running the program (i.e. if there's a separate compile step required, its output counts too):

• All the output produced on standard output and standard error via normal output methods must be identical to the program's source code;
• All the output produced on standard output and standard error via weird output methods must also, separately, be identical to the program's source code.

In other words, the program is a quine in two different ways. You can think of this as being a quine that's also an error quine (also known as a "Kimian quine"), except that the notion of "error" is restricted in order to avoid abuse (mechanisms which would let the program provide an arbitrary "error message" count as normal output, not weird output, on the above definition), but generalized to allow things like warnings, banners that the implementation prints as it loads, and other weird ways to produce output.

## Clarifications

• For the purpose of the proper quine definition, the fixed part of the output that's inherent in a weird output method is considered to not be encoded by the corresponding part of the program (even if that part of the program causes an error). As such, only the normal part of the quine can fail to be a proper quine.
• PPCG doesn't normally count output that's inherent to an implementation (such as compiler progress messages and fixed banners). This challenge is about handling that sort of thing, though, so such output is definitely relevant here (in addition to everything else on the standard output and error streams).
• Unlike in many challenges, the switches given to the compiler, and the program filename, are likely to be highly relevant in this challenge. Using an unusual build configuration may well be required to make the challenge possible, and as such is legal here; however, if you run the implementation in an unusual way, remember that PPCG rules charge a byte penalty for doing so (equal to the number of additional characters that you'd need to add on the command line over the shortest "normal" way to run a program), and thus you'll need to specify the size of the penalty in your post. (For example, if the interpreter you're using reads the program from a file, and has no particular restrictions on the filename, the shortest normal way to run the program would be from a file with a 1-character filename; thus, if you need a 100-character filename to make your program work, you'd incur a byte penalty of +99.)
• The compiler/interpreter version you use may well be relevant, so as part of your submission, please state a specific compiler or interpreter on which your program works, and which version is required. (For example, a C submission might state "C (gcc 6.2.0)" in the header.)
• Note that this task may not be possible in all languages. In the languages where it is, the easiest method will likely be to find an error or warning message for which it's possible to customize some subset of the text (via changing the name of something that gets quoted in the message; filenames are a common choice here, but not the only one). Obviously, if you could customize the entire thing, it wouldn't be weird output and thus wouldn't work. I'll be particularly impressed (and surprised) if someone finds a way to do this using only error and warning messages whose text is entirely fixed.

## Victory condition

This is a challenge, so an entry is considered to be better if it has a smaller byte count. As such, once you've got your program working at all, you want to optimize it to bring the number of bytes down as far as possible. (However, don't be discouraged if there's already a shorter entry, especially if it's in a different language; what we're really looking for here is to shorten a particular algorithm or idea behind a program as much as possible, but seeing multiple solutions in different languages or that rely on different principles is always worthwhile.)

# Sandbox questions

This was moved here from main because many answerers seemed to disagree with everyone else as to what an error message was.

I've aimed to avoid the problem in this rewrite by focusing not on what is and isn't an error message, but rather on the amount of hardcoded content in the message. Is this likely to be interpreted the same way by everyone? Is it objective?

Also, should I edit the original challenge, or should I post it as a new challenge? Out of the two non-deleted answers, one will stay valid (although the explanation will end up somewhat out of context), the other will need to be deleted (although I consider it to be invalid under the original specification too, and thus arguably no changes are being made to which answers are correct).

# Multiplivision

Hopefully a nice simple challenge that's not trivial.

Given an input list of positive integers, alternately multiply and divide them to yield a single numerical answer, according to the following rules:

• with the remaining numbers, alternate between dividing and multiplying, one at a time (that is, in a left-associative way), with the last operation being multiplication

For example, the input {3, 4, 2, 7} would start with 3, then successively compute 3 * 4 = 12, then 12 / 2 = 6, then 6 * 7 = 42 and output 42. (In other words, the input {3, 4, 2, 7} yields the output (((3 * 4) / 2) * 7) = 42.) The first operation had to be a multiplication, because if we'd started with a division, then the last operation would have been division as well, which isn't right.

If the answer is not an integer, then it can be output either as an exact fraction, or as a decimal equivalent, accurate to at least 6 significant figures (either truncating or rounding the end of the decimal is fine). For decimals that terminate before 6 significant figures, either the terminating decimal alone (1.5) or a version with trailing zeros (1.50000) is fine.

Other test cases (only the numerical answer needs to be output, not the intermediate parsed expression):

{3} -> 3
{3, 4} -> 3 * 4 = 12
{3, 4, 2} -> 3 / 4 * 2 = 3/2 or 1.5
{5, 4, 3, 2} -> 5 * 4 / 3 * 2 = 40/3 or 13.3333
{1, 2, 3, 4, 5, 6, 7, 8} -> 1 * 2 / 3 * 4 / 5 * 6 / 7 * 8 = 128/35 or 3.65714
{42, 42, 42, 42, 42, 42} -> 42 * 42 / 42 * 42 / 42 * 42 = 1764
{42, 42, 42, 42, 42, 42, 42} -> 42 / 42 * 42 / 42 * 42 / 42 * 42 = 42


This is , so the shortest code in bytes wins! Golfed answers in all languages are welcome.

• accurate to at least 6 significant figures (including decimals that terminate before the 6th significant figure) In the 3rd test case, shouldn't it then be 1.50000 as it has to be 6s.f.? – Thunda Mar 29 '17 at 3:21
• thanks, clarified above – Greg Martin Mar 29 '17 at 3:22
• In most languages that happens automatically, I really don't think it's necessary – Thunda Mar 29 '17 at 3:40

# King of the Hill: Risk(k)

We all know these well spend evenings where family members and friends got to temporary enemies while playing Risk the board game. The rules are not so complicated, the world is divided in territories on 6 different continents. The different players take control over those territories and afterwards play to conquer the neighbors, form alliances and betray each other until one player reaches world domination.

But wouldn't it be cool, if you just write a bot for you to play this game? here comes your chance.

This is a King of the Hill challenge to write the best bot to play Risk(k). Like in the original game (but not entirely) the world is divided into 6 continents with a total of 41 territories. Afterwards the bots will play this game with reduced rules in a round-based setting. Your bot can be written in or . Although any other language is possible which is capable of producing a dll with cdecl-functions or to implement interfaces. The controller can be found on Github.

### A short classis-game explanation

For all of you, who aren't familiar with this game. Every player plays on his own against all other players. The game begins with the claiming of territories (by positioning a single unit there) which is done consecutively for every player until all territories are owned by a faction. Now the players get the chance of using all units they have left to enforce their territories. Now the game begins round-wise. Every player makes a Attack-Stage and Move-Stage. In the attack-stage the players can attack other territories. This is done with dices. When thrown (the attacker and defender), the dices on each side are ordered and the highest ones are compared to each other. Whoever has the higher dice destroys a unit of the opposite side. Equal dices are considered a tie and no unit dies. You can only attack with max. 3 units at the same time, even when you have more than 3 units on your attacking territory. Also a territory with one unit cannot attack to prevent territory loss. Likewise a territory with two units can only attack with one etc. . When a territory falls to zero units, the attacking territory has to send units over (at least on and max. all except one - in the controller, all units except one are send automatically). After the attack stage, one player gets the chance to move units in the Move-Stage. One can only do so, if the territories you want to move units between are connected by territories owned by you. If your are done with this, the next players turn begins. The game ends, when one player has conquered the whole world.

## The game&rules:

• All bots have to obey the rules. Cheating bots will be punished by the program or by me. Standard loopholes are forbidden.
• Each bot must be in a dll file (name.dll) in the same directory, as the controller.
• Each program with the c++ interface must end with name.cpp.dll
• When the program is started each bot gets loaded into the program and is checked if everything works. The bots get instantiated only one time when the game starts.
• All bots loaded are participating in the game.
• The initialization stage begins:
• Each bot gets asked through the interface about its name and color.
• All bots get introduced to another with their names.
• All bots get consecutively called to select one of the remaining free territories. This goes till no territory is free anymore.
• All bots get to distribute the units left to all territories. [UnitCount = Ceil(82 / BotCount) ]
• The game will stop for now till the user pushes the start-button.
• The game will be round based where each bot will get consecutively called in four stages: Strategy-Stage, Enforcement-Stage, Attack-Stage, Move-Stage
• The Strategy-Stage gives your bot the opportunity to plan a strategy for this round.
• The Enforcement-Stage will give your bot the opportunity to distribute all new units to your territories. Units are gained to: Count of owned territories divided by 5 and floored, continent-bonus (owning a whole continent: North America: +5, South America: +2, Europe: +5, Africa: +3, Australia: +2, Asia: +7), capital-bonus (+1 for each owning of: East US, Brazil, North Europe, South Africa, East Australia, China) and +1 if you conquered a territory last round. You're guaranteed to get at least one new unit per round if your bot is still alive.
• In the Attack-Stage you can order the program do make attacks on enemy territories which can lead to loss on your or the enemy side or you conquering a new territory. The attack will be called multiple times (max.: 100 times) as long as you make an attack every call.
• In the Move-Stage you can move units around owned, connected territories. You can also again plan your strategy there for the next round.
• Each round is time constricted for every bot with 200ms. Taking longer than this will lead to a punishment (suspension) for the next round.
• The game ends when only one bot still lives or when two bots get into an infinite loop (which is surprisingly possible and not rare for the random-bots)

## The controller&interface

How the interfaces work is explained in the template files and the example-bots.

### For c#, .NET Programmer

Your bot has to be in a class which inherits and fully implements the IBotInterface. The class must be compiled into a class-library (dll). Afterwards you can just copy your dll into the game-directory and start the game.

EmptyBot is an empty template which implements the minimum required and adds a lot of useful helper-methods. It can be used as a template.

RandomBot is a bot which implements random behavior in all functions and stages. It acts as a full working example.

### For C++, C, cdecl-function-able-languages

Your dll must implement eight functions with an external definition and cdecl-calling convention. A minimal implementation can be looked at at EmptyCPPBot.

Your dll can afterwards be copied into the game-directory which can be started normally afterwards. Your dll must have the following name structure: nameOfYourDll.cpp.dll to distinguish it from the managed dll's.

RandomCPPBot is a bot which implements random behavior in all functions and stages. It acts as a fully working example.

## Contest Rules

• Players may submit multiple bots and are free to edit them to the deadline.
• A submission must be made as an answer on this thread. The source code can come in pieces, as full project, single file or whatever. And may be provided via download, push request or simple pasted code in the answer with code-tags. If not compile-able with Visual-Studio, i request fairly simple instructions how to compile it myself.
• A submission must specify the name and color of the bot. Although not necessary, an explanation of the bot's strategy would be nice.
• Bots are not allowed to use sources outside the dll/program (no files, no webrequest or similar things).
• Bots must be compatible with the provided interface and work under windows. Custom interfaces are not explicitly forbidden as long as they don't generate a advantage or are not compatible with the main-interface/program.
• The competition will be held in the provided controller (possible altered to automate the process) with all pairings possible to find the best 4 bots.
• The last 4 bots are fighting each other in 10 games. The bot which has won the most, wins the tournament. In a tie situation, the bots will take a single match against each other (golden goal), until one wins.
• Rules are can be changed when necessary which would be introduced on top of this thread.
• The contest ends when a week long no new submissions got made or when I say, its time to end this.
• And again, just to be sure: standard loopholes are forbidden.
• How do you organize players into games, how do you score a single game, and how do you aggregate those scores? When are you instantiating each bot (only once for the tournament, once for each game, or once for each method call?) I'd recommend describing the rules of risk in full for those poor souls that don't know them. – Nathan Merrill Mar 30 '17 at 21:45
• I added a relative "short" description of the classical game. Also I added the answer to all your question into the thread but i'll also anwser it here: 1. All players in the game directory are participating. The tournament will provide automatic pairings if necessary. 2. You score a single game by letting your bot win it. 3. You can't. But you can restart infinitely often. 4. All bots are instantiated on the start of the program. But i could change that to the start of every game (so a reload also instantiate the bots new). – Julien Kluge Mar 30 '17 at 22:35
• 1. What if there are lots of players (10 or even 20?). How would you automatically pair? 2. So the second to last survivor gets the same number of points as the first one to die? What happens if there's an infinite loop? 3. You have to come up with some way to combine the scores across multiple games. 4. Are you OK if submissions store data across games? How do submissions know when a new game starts? – Nathan Merrill Mar 30 '17 at 22:46
• Risk is a famously unbalanced game in which luck is very important. To balance that out you'll need to play hundreds of games per match-up. Each game involves thousands of player decisions. I would not be surprised if it ends up taking a week to run the tournament, and part-way through that week someone might submit a new bot. – Peter Taylor Mar 31 '17 at 12:31

# Check for repeated repeated words

Your code should either read in a stream/file containing printable ASCII text or define a function that takes a string containing printable ASCII and output any repeated words (including their repetitions). If you read from a file then it can have a name of your choice. Output can be a single linefeed-separated string, or a list of strings (one per repeated word).

A word is defined by the regex [0-9A-Za-z'-]+, i.e. it's a run of letters, digits, apostrophes and/or hyphens.

A word is considered to be repeated if it occurs twice or more in succession, separated only by one or more spaces. Repetition is case sensitive: WORD, Word and word are all different.

## Test Cases

Individual test cases are separated by an empty line. For each test case, the first line is the input, subsequent lines are the output. Note that the last test case does not contain any repeated words.

Hello how how are you?
how how

Hello my my friend. Is that that your pen pen pen?
my my
that that
pen pen pen

This is not. not a case of repeated? repeated words! Neither neither is this.

• Why do you disallow functions? – mbomb007 Mar 31 '17 at 16:08
• @mbomb007 I don't :) – user9206 Mar 31 '17 at 16:13
• "No other ways of getting input are allowed." Which means function arguments. – mbomb007 Mar 31 '17 at 16:16
• @mbomb007 That text shouldn't have been there. Thanks. – user9206 Mar 31 '17 at 16:23
• If underscores aren't a valid word character for this challenge, you'll want to add a test case that has underscores. I can see a lot of regex submissions being based on \w otherwise. – DLosc Mar 31 '17 at 17:17
• REgex would would win – Christopher Mar 31 '17 at 20:28

# Island Golf #3: Random Generation

Given the dimensions of a rectangular patch of ocean and the desired number of land tiles, randomly generate a valid island of that many tiles within that rectangle.

## Input

Your input will be three positive integers:

• w, the width of the grid
• h, the height of the grid
• n, the number of tiles to make the island

w and h will always be 3 or greater. n will always be 1 or greater. Also, n will be small enough to fit inside the grid allowing for a border of water tiles: specifically, n <= (w-2)*(h-2).

## Output

Your code must output a w by h rectangular grid consisting of two characters, representing land and water. (In the examples below, land is # and water is ., but you may substitute any two distinct characters you wish.) There must be exactly n land characters, in one contiguous block, representing an island. For example, an input of w=11, h=9, n=40 might result in the following output:

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


Requirements:

• The land tiles must all be contiguous (i.e. there's only one island).
• Land tiles can be connected horizontally or vertically, but not diagonally.
• The water tiles must also be contiguous (i.e. there must not be any lakes).
• The outer border of the grid must remain as water tiles.

Some illegal outputs:

.....
.#.#.   Multiple islands
.....

....
.#..    Diagonal connection
..#.
....

......
.####.  Contains a lake
.#.##.
.##...
......

....
.###    Border contains a land tile
.##.
....


## Details

Your solution may be a full program or a function. Any of the default input and output methods are acceptable. Any of these definitions of randomness are acceptable. Every valid island for a given input should occur with nonzero probability.

You may take the input numbers in whatever format and base is convenient for your language. You may take the three numbers in any order.

Your output may be a multiline string, a list of strings, or a 2D array/nested list of characters/single-character strings. Your output may (optionally) have a single trailing newline. As mentioned above, you may use any two distinct characters in place of #..

Please mention any unusual I/O methods/formats in your submission, so others will be able to test your code more easily.

## Test cases

Given as width, height, size. Note that the first three test cases specify islands of maximal size for the given width and height.

3, 3, 1
9, 3, 7
5, 5, 9
5, 5, 1
10, 10, 60
80, 22, 1100


### Validation program

Here is a validation program in Pip to test whether your output for a given input meets the spec. It expects the three parameters and an island in the format given in this question; for example:

5, 5, 9
.....
.###.
.###.
.###.
.....


If your code has a different output format, you'll need to convert it to this format before plugging it into the validation program.

Sandbox questions:

• This seems like a pretty obvious random-generation challenge, but I didn't find a duplicate in a quick readthrough of previous challenges. Did I miss anything?
• Should I add more stringent rules on what counts as random? Related reading
• Should I allow output to be a 2D array (or nested list) of any two distinct values, not just chars and single-char strings? (E.g. integers 0 and 1, booleans false and true, etc.)
• To the downvoter, if you see this: What's your reason for downvoting? If it's something I can improve about the challenge, I'd like to know so I can improve it. – DLosc Apr 6 '17 at 1:28

# Calculate Wind Chill

The Australian Apparent Temperature (aka, wind chill) in °C AT is given by this algorithm from the Australian Bureau of Meterology (wp, source):

AT = Ta + (0.33 * e) - (.7 * ws) - 4.0

Where:

Ta = Dry bulb temperature (°C)

e = Water vapour pressure (hPa)

ws = Wind speed (m/s) (at an elevation of 10 meters)

The water vapour pressure in hectoPascals e is given by this algorithm:

e = (rh / 100) * 6.105 * exp( ( 17.27 * Ta ) / ( 237.7 + Ta ) )

Where:

Ta = Dry bulb temperature (°C)

rh = Relative humidity [%]

exp represents the exponential function

The domain of:

• Ta is -273.15°C to 2e7°C.

• e is the real numbers

• ws is 0 m/s to 2e7 m/s

• rh is 0% to 100%

For inputs outside these domains, your code can do anything, including give the right answer.

## Output

Given a dry bulb temperature in °C, a wind speed in metres / second, and a relative humidity in %, your code should give the Apparent Temperature in °C, accurate to 0.1°C.

Assuming your platform or language can represent reals, for correct functions correct_func,

or in C, fabsl( correct_func(Ta, rH, ws) - expected ) < 0.1.

### Test cases

value for Ta, rh, ws -> output

0   ->  -4.0
2   ->  -3.3529916671770903
4   ->  -2.6916697830145546
6   ->  -2.0132006039049877
8   ->  -1.3143308806029346
10  ->  -0.5913412821173161
12  ->  0.16000376605969002
14  ->  0.9445099696431676
16  ->  1.767610915646344
18  ->  2.6354298170017625
20  ->  3.5548453789325833
22  ->  4.5335619088440815
24  ->  5.580183785538598
26  ->  6.704294397098089
28  ->  7.916539649854112
30  ->  9.2287161435045


You can use a builtin function for the exponential function, ex, if you like.

This is , so the shortest code wins!

# Factor Sort

This challenge involves sorting positive integers based on a lexicographical ordering of their prime factorizations.

## Overview

lexicographical sorting, used in dictionaries, applies lexicographical order which extends alphabetical order to words:

a
aa
aaa
aaron
ab
abandoned
abc
aberdeen


When programming this sort, however, we typically don't extend alphabetical ordering per se, but rather we extend the order of integers used for an encoding. For example, the same sorting above through ASCII encoding is really:

97
97 97
97 97 97
97 97 114 111 110
97 98
97 98 97 119 100 111 110 101 100
97 98 99
97 98 101 114 100 101 101 110


It is this type of ordering that we're after here... lexicographical ordering by extension of numeric comparison as opposed to alphabetical order.

## The Challenge

In this challenge, you will be sorting positive integers by their ordered prime factorizations (ordered in the sense that the primes are listed smallest to largest). To handle the special case number 1, we can simply say its prime factorization is an empty list, which lexicographically sorts prior to any other number's prime factorization. We'll call this type of sorting factor sorting.

For example, the numbers from 1 to 10, factor sorted, are: 1 2 4 8 6 10 3 9 5 7. To see why, here they are again with the ordered prime factorizations:

 1 []
2 [2]
4 [2 2]
8 [2 2 2]
6 [2 3]
10 [2 5]
3 [3]
9 [3 3]
5 [5]
7 [7]


## Rules

Write a function or program that factor sorts a list of positive integers. Input and output can be anything reasonable, so long as the input is in the specified arbitrary order and the correct output order is apparent from the output.

Keep in mind that the output should be factor sorted numbers, not their prime factorization.

If it matters, numbers in the input will always be ≤ 7928, so:

• The only primes in the prime factorization list are the first 1000 primes
• Composites have factors no larger than 89 inclusive

This is code golf; shortest code in bytes wins.

## Test cases

1 2 3 4 5 6 7 8 9 10
->
1 2 4 8 6 10 3 9 5 7

100 200 300 400 500 600 700 800 900
->
800 400 600 200 900 300 100 500 700

1472 4417 1425 1452 4480 200 339 2868 3835 4760
->
4480 1472 200 4760 1452 2868 1425 339 3835 4417

2 4 6 46 62 466 622 4666 6238
->
2 4 6 46 62 466 622 4666 6238

• This is extremely trivial in golfing languages (e.g. in CJam it's {{mf}\$}), so may attract negative attention and may not attract answers in any language in which it's an interesting challenge (if there are any). – Peter Taylor Apr 3 '17 at 11:27
• I think asking to compare two numbers makes for a nice challenge than sorting them. Implementing sorting based some a key function has been overdone, and many languages just have a built-in for it. Also, I suspect there are strategies for comparison that do not compute the factor vector. – xnor Apr 3 '17 at 22:27
• @xnor "I suspect there are strategies ..." I'm confused about what you're trying to convey here. Granting your suspicion... suppose there's indeed another way to meet the specification. Why would that matter? – H Walters Apr 4 '17 at 3:05
• @HWalters I mean that a challenge to simply compare rather than sort might allow a wider variety of solution strategies, which makes it more interesting to golf. – xnor Apr 6 '17 at 1:59
• Is this in the OEIS? – anna328p Apr 19 '17 at 6:12
• @Mendeleev Not sure how to answer this. Strictly no, since it's not a sequence. If we factor sort all positive integers, then we get an infinite number of infinite "chains" of numbers, each chain of which is ordered. The first such chain is A000079, powers of two, so if you stretch you could say this is A000079. Powers of 3 excluding 1 is another chain after this; 2 times powers of 3 excluding 2 (i.e., 6, 18, 54, ...) is another chain between the two; etc. There's no "second chain" (chain immediately after A000079), and no immediate predecessor chain to powers of 3 excluding 1. – H Walters Apr 19 '17 at 15:01

## Dice Roller

Since I have played a lot of tabletop role playing games, I am looking for an easy to use dice roller. But also being lazy, I would like to have the shortest possible solution, making this code-golf.

Input

You will receive as input a string, composed of 2 or 4 variables.

In the case of 2 parameters, both non-negative numbers, they represent the number of dice and the value of the dice rolled.

Examples:

"2 6" means rolling 2 6-sided die (colloquially written 2d6).
"3 8" means rolling 3 8-sided die (3d8).


In the case where 4 parameters are given, the first 2 are still numbers, as in the case of 2 parameters. The third and forth parameters represent a dice modifier, and whether the modified applies to the dice individually or the sum of all rolled values, respectively. The third parameter is a (possibly) signed number (e.g.: 2, +1, -2, ...), and the forth is a character string, either 'ind' (if the modifier applies to the individual dice) or 'all' (applies to the total sum of the dice rolled).

Examples:

"2 6 +1 ind" means rolling 2 6-sided die, and a modifier of +1 is applied to each individual die (can be written 2d(6+1)).
"3 8 -4 all" means rolling 3 8-sided die, and a modifier of -4 is applied to the sum of the roll (can be written (3d8)-4).


Dice Properties

• Only the following dice are acceptable (second parameter): 2 3 4 6 8 10 12 20 100.

• Regardless of modifier, a dice gives at least a value of 1 when an individual modifier is applied (so for example, "1 6 -10 ind" will return a value of 1, the minimum value allowed by this stipulation). There is no max value to an individual modifier.

• When a modifier is applied to the sum of the dice rolled (4th parameter is "all"), the sum can be less that the number of dice rolled. For example, "2 6 -20 all" will give a sum range of -18 to -8, as the lowest value of 2d6 is 2 and highest value is 12, pre-modifier. There is no min or max value to a this modifier.

Output

The output will be the values of the individual dice rolled, and the sum of all the dice.

Valid examples:

"2 6" => "3 6 : 9"
"3 8" => "1 8 5 : 14"
"2 6 -1 ind" => "1 2 : 3"
"2 6 -10 ind" => "1 1 : 2"
"3 8 +1 ind" => "2 9 6 : 17"
"2 6 10 all" => "3 6 : 19"
"2 6 -10 all" => "3 6 : -1"


Invalid examples (incorrect results):

"2 6" => "3 7 : 10" (7 is not a valid result on a 6-sided die)
"3 8" => "1 8 : 9" (not enough dice rolled)
"3 8" => "1 8 5 4 : 18" (too many dice rolled)
"2 6 -1 ind" => "1 6 : 7" (6 is not a valid result on a 6-sided die with a -1 modifier applied)
"2 6 -1 ind" => "0 5 : 5" (the die has to have a minimum value of 1 with individually applied modifier)

• There's this. As far as I can tell, the only difference is the exact input format and your fourth parameter. I can't say whether or not people will close it as a duplicate (although there's a good chance they will, because all it does is optionally multiply the bonus by the number of dice), but it might generally be unpopular if the community feels it doesn't add anything interesting over an existing challenge. – Martin Ender Apr 4 '17 at 18:51
• @MartinEnder The forth parameter, limits on which dice can be rolled and the negative value modifiers. As for as I can see, the question you linked to doesn't have any consideration for XdY-Z, which I wanted to include as it introduces the minimum 1 constraint for the dice rolls. But that's why I put it in the sandbox first, to see what the community thinks :) – AntonH Apr 4 '17 at 18:55
• @MartinEnder Would it maybe work if I posted a link to that question, but also specified the differences between the questions? – AntonH Apr 4 '17 at 18:57
• I personally don't think that the max(1, roll) makes a sufficient difference. I know it's frustrating when you put a lot of effort into a challenge spec and it turns out to have already been done (the same or similarly), but if it's almost the same as an existing challenge, it's usually better to try something else. It's ultimately up to you, of course. – Martin Ender Apr 4 '17 at 19:06
• @MartinEnder It got stuck in my head and wouldn't leave, so I had to get it down :P I'll wait a bit to see if anyone else has anything else to add, but if it doesn't go anywhere, it's fine. – AntonH Apr 4 '17 at 19:13
• @MartinEnder I wouldn't close it as a dupe. They're similar, to be sure, but a big chunk of the linked challenge is input parsing and validation, which isn't present here. I also think that the fourth parameter (ind vs all, though I would suggest to let people use two distinct values rather than string-matching) coupled with the possibility of negative modifiers all combine to make this challenge distinct. – AdmBorkBork Apr 4 '17 at 19:28
• @AdmBorkBork Instead of "ind"/"all", would you suggest numerical (0/1) or letter ('i'/'a'), or something else? – AntonH Apr 4 '17 at 19:33
• Any of the above. If input parsing isn't the primary goal of your challenge (and it doesn't seem to be), don't limit folks on what inputs they and their chosen language can use best. – AdmBorkBork Apr 4 '17 at 19:41

# Find the Translation Table code-golftranslation

Given two strings, find the translation table between the two, if the translation is not possible, output false. Probably most easily defined through examples:

# Valid Cases

bat,sap = ["bt","sp"]

sense,12312 = ["se","12"]

rabid,snail = ["rabd","snal"]

# Falsy Cases

banana,angular = false (not the same length, impossible).

animal,snails = false (different character patterns, not a translation).

# Rules

• Input may be as a 2 element array or as 2 separate inputs.
• Output can be as an array, on separate lines or space delimited, but must be similar to how I have it shown.
• False output may be 0, -1 or false. If your language uses something different, ask.

# Sandbox Questions

Should I allow inputs of different length to be part of the translation? This will increase the complexity of the question by 100%. I'd suggest using - as the marker for a removal of a character in the translation to make it work. While it makes it more complicated, if this already exists I planned to use that to avoid a duplicate. Let me know what you think. I really like the extension idea though.

• Would empty string "" be an acceptable falsy output? Or empty list []? – mbomb007 Apr 6 '17 at 21:50
• Shouldn't the second valid test case be ["sen","123"]? – Laikoni Apr 6 '17 at 22:46
• 1. The examples suggest, but the spec does not state, that trivial translations should be excluded. Or would ["rabid","snail"] also be an acceptable output for rabid,snail? What about ["rabidz","snailz"]? 2. The comment "(different character patterns, not a translation)" seems misleading to me. E.g. given input abc,ddd I would expect that despite having different character patterns the output should be truthy: to wit ["abc","ddd"]. 3. Does the order of the elements in the translation tables matter? I.e. would ["tb","ps"] be acceptable output for the first example? – Peter Taylor Apr 7 '17 at 10:03

# QR Code Editing: Minimum Change

? This is pretty non-trivial, and finding optimal solutions is probably computationally difficult.

QR codes are a way to represent URLs and other strings of text using a 2D image. What you might not know, however, is that a significant portion of a QR code is error-correction or unused space.

In this challenge, your program will be given a square of 1s and 0s representing a QR code. This QR code may not be functional, or it may be valid or point to some destination. Your program will also receive a string, representing the data that the new QR code should be encoded with. The goal of the program is edit the original QR code to contain the new content, but also to do it with as few pixel-flips as possible.

Here's an image describing some parts of the QR format:

QR code art generator, demonstrating how much of a QR code's space can be modified without changing the content: https://www.qrpixel.com/

Spec is only partially completed, I'll probably have to find some decent resources on QR code formats and error correction.

• sound like it will make an interesting challenge once the spec is fleshed out. I assume you're going to include all the qr code info that we need? – Liam Apr 9 '17 at 22:36

# Pratt certificates

(bumping this proposal to see if there's any interest or comments. If so, speak now; if not, I'll delete)

Your task: write code that generates a Pratt certificate for a prime number, and write code that verifies an existing Pratt certificate.

## What's a Pratt certificate?

A Pratt certificate for a prime number p is a proof, of a particular type, that p is indeed prime. Historically, it was used in situations where proving the primality of p required a computation that was slow due to factoring p-1, but verifying the certificate (once the initial computation generated it) was quite fast.

A Pratt certificate for p is a recursive structure consisting of three parts: the prime p itself; a "witness" integer g (which is actually a primitive root modulo p; see the next section for its properties); and Pratt certificates for all primes dividing p-1. The prime p=2 is special: a Pratt certificate for 2 is just 2 itself.

For example, here is a Pratt certificate for p=3911:

{3911, 13, {2, {5, 2, {2}}, {17, 3, {2}}, {23, 5, {2, {11, 2, {2, {5, 2, {2}}}}}}}}


The witness is 13, and the prime factors of 3911-1 are 2, 5, 17, and 23; each of those new primes itself has a Pratt certificate, which are respectively 2, {5, 2, {2}}, {17, 3, {2}} and {23, 5, {2, {11, 2, {2, {5, 2, {2}}}}}. In this last Pratt certificate, the prime factors of 23 are 2 and 11, so a Pratt certificate for 11 must be included, and so on.

## How do we generate a Pratt certificate?

Given a prime p, a Pratt certificate can be generated by finding a primitive root g modulo p; factoring p-1 into primes (keeping only one copy of each prime factor); and recursively generating Pratt certificates for every prime factor of p-1.

## How do we verify a Pratt certificate?

Given a prime p, a witness g, and the prime factors q1, q2, ... of p-1, a Pratt certificate is verified by checking:

• that p-1 has no prime factors other than q1, q2, ...;
• that the power g^(p-1) is congruent to 1 modulo p;
• that none of the smaller powers g^((p-1)/q1), g^((p-1)/q2), ... are congruent to 1 modulo p; and
• that each of the Pratt certificates of q1, q2, ... are themselves valid.

## Scoring and technicalities

You must write two programs or functions (or one of each): one that takes a prime number as input and returns its Pratt certificate; and one that takes an input formatted like a Pratt certificate and returns a truthy or falsy value depending on whether it is an actual Pratt certificate.

• You may choose any reasonable format for the Pratt certificate: nested lists (like the examples in this question), indented multiline strings (like the example on the Wikipedia page), or something similar that a human being could be trivially trained into parsing by eye. You may use any reasonable convention for the trivial Pratt certificate for 2.
• However: whatever format you choose for the Pratt certificate, your certificate-generating code must output the same format that you take as input to your certificate-verifying code. Note that your certificate-verifying code must be capable of verifying any possible Pratt certificate (in your format) for p, not just the one your other program generates for p.
• If you want, you may write a single program or function that accomplishes both tasks; in that case, your code can either determine which task is being asked of it implicitly from the input, or it can allow the user to instruct it which task to perform in some reasonable way.
• Regardless of whether you use one or two programs, no calculation can be shared or saved between different runs of the code. The programs must work correctly, on any individual prime input and on any individual certificate-shaped input, if it is the first time that code is ever being run on that system.
• You don't have to handle bogus input. You may always assume that the input to your first program is an actual prime number, and that your input to the second program syntactically matches your Pratt certificate format.
• Built-ins that generate or verify Pratt certificates are not allowed. Other types of built-ins (for example, those that factor integers, raise integers to powers in modular arithmetic, find primitive roots) are acceptable.
• This is , so shorter code (in bytes) is better. If two programs are used, the total number of bytes in both programs is the score; if one program is used, its number of bytes is the score.

## Example Pratt certificates given prime inputs

(Note that there are many possible witnesses for any given prime, but the rest of the certificate is unique up to reordering.)

31 -> {31, 3, {2, {3, 2, {2}}, {5, 2, {2}}}}
127 -> {127, 3, {2, {3, 2, {2}}, {7, 3, {2, {3, 2, {2}}}}}}
229 -> {229, 6, {2, {3, 2, {2}}, {19, 2, {2, {3, 2, {2}}}}}}
1093 -> {1093, 5, {2, {3, 2, {2}}, {7, 3, {2, {3, 2, {2}}}}, {13, 2, {2, {3, 2, {2}}}}}}
65537 -> {65537, 3, {2}}


(All the above outputs are examples of truthy inputs for the Pratt-certificate checking code.)

## Example falsy inputs for Pratt-certificate checking

{31, 2, {2, {3, 2, {2}}, {5, 2, {2}}}}
{31, 3, {2, {3, 2, {2}}}
{31, 3, {2, {3, 2, {2}}, {5, 2, {2, {3, 2, {2}}}}}}
{127, 2, {2, {3, 2, {2}}, {5, 2, {2}}}}
{85, 4, {6, 5, {5, 2, {2}}}, {14, 3, {13, 2, {2, {3, 2, {2}}}}}}


# Median fractals

I define 'Median fractal' as this.

Median fractal L1 is a equilateral triangle.

for median fractal Ln, Draw Ln-1, then for each triangle, draw all 3 medians in the triangle.

You will be given an integer n, draw Ln.

# Sandbox

Any suggestions, guys?

• Would benefit from 1. A definition of the median of a vertex; 2. Diagrams of L_2 and L_3; 3. A better name. It's a variant on triangle centre fractals, but perhaps would be best called the vertex-median fractal. – Peter Taylor Apr 15 '17 at 12:12
• I'm not sure what exactly "draw all 3 medians in the triangle" means. I think providing images of the first few fractals would help a lot to make the construction better understandable. – Laikoni Apr 17 '17 at 7:42
• Should add: graphical output questions should at the very least specify minimum sizes to avoid trivial answers which give a 1x1 pixel bitmap output - although I suspect answers will favour vector graphics formats. – Peter Taylor Apr 18 '17 at 16:24

These would be separate questions, and each would link to the other.

A "policy" is defined as a list of well-defined restrictions ("rules") on valid passwords. Here is an example:

• Passwords must contain only digits, letters, and the characters '*&^'.
• Passwords must be at most 8 characters long.
• Passwords must not contain dictionary words (if you use this one, you must use a freely and programmatically accessible dictionary and tell us where to find it).

Policies:

• must contain no more than 10 rules,
• may not involve encryption of any kind, and
• must be clear and unambiguous

For example, these would be a bad rules:

• The MD5 hash or zipfile of the password must not contain the letter "a". (Uses encryption of a sort)
• Passwords may not contain special characters. (It's unclear what counts as a special character)

Over the years, people have come up with some pretty bad password policies. Your challenge is to crack such a policy. These can be found in the cops thread [link]. To crack a policy, write a program to brute force passwords that adhere to that policy. Your program must run in linear time on the number of possible passwords allowed by the policy. You may do this by enumerating or iterating over all possible passwords in some way, such as by calling a function (called, for example, guessPassword) for each possible password. One option is to simply hardcode the possible passwords, if there are only a few. Here is an example (JavaScript):

function* getPasswords() {
yield* ['a', 'b', 'c'];
}


Or, using the second approach:

function bruteForce() {
for (let pw of ['a', 'b', 'c']) {
return pw;
}
}
}


Whoever cracks the most policies wins.

# Sandbox

• Is the linear time approach good? My original thought was just "your program must halt in a reasonable time", but that seems too vague, and this allows a person to crack even policies with a lot of possible passwords (though those hopefully wouldn't win anyway).
• I could also just say, "pick a password in your policy and robbers will try to crack it", maybe having the cops supply a hash of the password.
• I'm worried that this sort of challenge needs far too many arbitrary-seeming restrictions on the policy to make it work. The restriction against prime numbers is already fairly arbitrary, for example. Additionally, "linear time" doesn't make sense here; there's a finite number of possible passwords (according to the victory condition), meaning that any program that enumerates them runs in O(1) (thus faster than linear) by definition. Also, I think it's fairly easy to encode an NP-complete problem into the challenge in an understandable way; many are pretty intuitive. – user62131 Apr 17 '17 at 9:30
• @ais523 Okay, if I require cops to have valid cracks, a few of those restrictions go away, since we don't have to worry about people making policies that are impossible to crack. Also, I know the programs would technically all be constant time, but I'm not sure how else to specify what constitutes a "fast" crack. I could just say, "must run in a few minutes on my machine" or something. – Brian McCutchon Apr 17 '17 at 16:12
• "I'm not sure how else to specify what constitutes a "fast" crack" is IMO evidence that this idea is not workable. – Peter Taylor Apr 17 '17 at 17:57

# shortest angular path

Let's say you have a robot and you measure the orientation of a wheel (e.g. for tracking the exact distance), but the sensor just returns an angle between -180° and 180°. Then you have the problem that even if the wheel just moved three degrees from 179° to 182° the sensor will tell you that the wheel made a jump from 179° to -178°. This makes analyzing and interpreting the data a little bit cumbersome. Given a list of subsequent measurements your goal is now "smoothing" them out, such that from each entry A to the next B, in the list ([...,A,B,...]) there is at most a 180° jump.

### Details

• You can also assume other (single number) representations of angles, e.g. radians (0 to 2*pi) or gradian (0 to 400) or number of turns (0 to 1).
• If it is more convenient, you can assume that the sensor will return data in [0°,360°] instead of [-180°,180°].
• Which way you go if the jump is exactly 180° (or -180° or 540° etc.) is up to you.

### Examples

[0 10 90 80 180 -130 -90 -120 -143 170 0] (Input)
[0 10 90 80 180 230 270 240 217 170 0]    (Output)


# Smooth an array

A typical signal processing operation consists in smoothing a signal to reduce noise.

A very basic way to perform such smoothing, on an array of integers, is using the following formula:

where y'_t is the smoothed value at index t, y_t is the original value at index t, and where β is a smoothing parameter (in [0,1]). Note that y' = floor(y + 0.5) is the classic round half up operation.

For t = 0, there is no y'_(t-1), thus we set that y'_0 = y_0.

Applying that operation on a sequence of integers pictured below on the left, produces the sequence of integers pictured below on the right:

### Challenge

Given a list of integers and β, output that list of integers smoothed in that way.

All integers of the list will be guaranteed to be in the interval [1, sup) where sup is the maximum integer representable in the integer type you use in your language. All integers of the input must be taken, and all integers of the output must be printed, in the decimal base (unless your language does not support decimal numbers, in which case you may use the standard base your language uses).

The input list is guaranteed to have at least 2 elements. You may take that input list in any way or format that is sensible in your language.

β is guaranteed to be in [0,1].

### Test cases

List                               β     Output
[1,2,7,3,11,13,26,5,18,4,3,2,1]    0.5   [1,2,5,4,8,11,19,12,15,10,7,5,3]


### Scoring

This is , so the shortest answer in bytes wins.

# Output the Name of a Number

Idea from a recent question on math SE.

Write a program or a function that takes an integer from range 0 to 255 (inclusive) and outputs the name of its unsigned 8-bit binary representation. Input can be in any integer format you like, but the outputted name must match the number's unsigned 8-bit representation.

The name of the number is determined by the positions of its binary digits that are 1:

1 − John
10 − Watson
11 − Watson John
100 − Kevin
101 − Kevin John
110 − Kevin Watson
111 − Kevin Watson John


Let the names for the eight bits be Laura, William, James, Mary, Alice, Kevin, Watson, and John.

So now the name of 255 (11111111 in binary) is:

Laura William James Mary Alice Kevin Watson John


Zero doesn't have a name under this system so you may output an empty string or nothing at all. Trailing whitespace is allowed for all outputs.

Test cases:

<input (as decimal)>
<8-bit binary>
<output>

10
00001010
Alice Watson

42
00101010
James Alice Watson

128
10000000
Laura

189
10111101
Laura James Mary Alice Kevin John

55
00110111
James Mary Kevin Watson John

96
01100000
William James

37
00100101
James Kevin John

0
00000000

255
11111111
Laura William James Mary Alice Kevin Watson John


This is code-golf, show the shortest answer in bytes wins.

# Optimize for the Test Cases test-batteryoptimizationmetagolf

Given a set of test cases (pairs of input and output strings) as input, output a program in a programming language of your choice that consistently and deterministically produces the correct output for each input.

## Rules

• You may choose any programming language for the output programs, so long as it is a programming language by our definition, it existed prior to the creation of this challenge, and it is capable of taking arbitrary ASCII strings as input and producing arbitrary ASCII strings as output.
• Your solution must use the same programming language for all inputs. The output programs do not need to be in the same language as the solution.
• The output program must consistently and deterministically produce the correct output for each input. That means that, no matter how many times the program is run, it will always produce the correct output (barring any uncontrollable accidents like cosmic rays twiddling bits). PRNGs are allowed so long as a constant seed is provided (making the output consistent and deterministic).
• The test cases' inputs are provided without quotes, but you may require that the input be quoted if it is necessary or convenient (as per our usual policy on quoted input). However, you must either always or never have quotes on the input - you can't have some with quotes and some without.
• It does not matter what the output program does for inputs that are not part of the specific test case the program was created for.
• You may optionally take the number of test cases as input, if that is convenient or necessary.
• Every input in a set of test cases will be mapped to a unique output. Input values will not be repeated within a set of test cases (so [(3, 5), (3, 6)] wouldn't be a valid test case).

## Scoring

Your score will be equal to the sum of the byte counts of all generated programs for the set of scoring cases. Lowest score wins. This is a competition within output languages, not a competition between output languages, so don't be afraid to choose a language that is more verbose than others. I reserve the right to change the scoring cases should it be necessary.

## Examples

A C++ program that outputs (poorly-golfed) Python functions:

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

const string function_skeleton_start = "lambda s:{";
const string function_skeleton_end = "}[s]";

int main() {
int N = 0;
string in, out;
stringstream program;
program << function_skeleton_start;
cin >> N;
cin.ignore();
for(int i = 0; i < N; ++i) {
getline(cin, in);
getline(cin, out);
program << "'" << in << "':'" << out << "',";
}
program << function_skeleton_end;
cout << program.str() << endl;
return 0;
}


An example input:

2
foo
bar
bar
foo


The corresponding output:

lambda s:{'foo':'bar','bar':'foo',}[s]


## Test Cases

(TBD)

• I'd be very interested to see some of the answers this challenge would get +1 – MD XF May 10 '17 at 1:21

# Output "Hello, World!"... Even before it runs?

Please note that this challenge only applies to languages that have a build stage and a build log.

Output "Hello, World!" to the build log. The program may or may not be compiled successfully, the job is to just output "Hello, World!" somewhere in the build log.

# Example (C/C++)

#pragma message("Hello, World!")

• could it be more interesting as a rosetta-stone challenge? – John Dvorak May 13 '17 at 9:32

# Output the Balmer Series

## Challenge

Write a program which outputs the following image (note, it is an svg):

It is the emission spectrum of hydrogen, caused by the Balmer series: https://en.wikipedia.org/wiki/Hydrogen_spectral_series#5

Your program must not read the image from the internet or a local file.

The image may be to an image file or a graphics window. If not a vector, the image sides must be greater than 400 pixels.

Your image must have the same colours and same ratios of spacing between each line.

## Winning

Shortest code wins.

• What does it mean to output the image "exactly"? It's obviously not pixel-for-pixel for two reasons: firstly, because the image isn't raster, and secondly, because the spec allows for variation in image size. – Peter Taylor May 12 '17 at 22:22