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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, and click "Answer This Question". Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, replace the post here with a link to the challenge and delete it.

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]

## Make a Four Color Map

The Four Color Theorem states that it is possible to color any map separated into contiguous regions using only four colors such that no two adjacent regions are the same color. While the Five Color Theorem has been proven, no proof exists for only using four colors (though there have also been no counterexamples). Given an image containing white regions separated by black borders, generate a four color map. You may assume that the borders of the image are also region borders and that shared corners do not count as adjacencies.

Related: Four Color Theorem

# Input

An image in a standard format containing white regions separated by black borders

# Output

Displaying or writing an image file in any standard format that contains the original image colored according to the Four Color Theorem

# Examples

Your colorings do not need to match mine, they just need to be valid solutions ====> ====>

Note that the map of the US is not colored by state, it is colored by contiguous borders

This is so shortest code wins!

• Isn't the first example invalid? I see two adjacent red regions in the bottom left. – Business Cat Aug 5 '16 at 17:11
• Whoops! Thanks, I'll fix that. – theLambGoat Aug 5 '16 at 17:14
• I thought the four-color one was definitively proven a couple years ago? – AdmBorkBork Aug 5 '16 at 18:19
• It might have been, I was just going off of wikipedia. I just read the Wolfram article on it and it looks like it was proven for maps that are flat (and maybe all maps?) but I don't 100% follow it so not positive. – theLambGoat Aug 5 '16 at 18:28
• 1. The four colour theorem was proven in the 70s. 2. This is essentially a dupe of this question but with a really bad input format. – Peter Taylor Aug 5 '16 at 21:09
• Here's the relevant Wikipedia section if you're looking for more info on the proof – trichoplax Aug 6 '16 at 14:42
• The theorem was "disproved" by counterexample on some mailing list I believe. It was a joke. Someone produced a pretty complex map and claimed that it couldn't be colored with only 4 colors. I think he was just seeing if he could get people to waste time looking at it. – Liam Aug 10 '16 at 23:48

Your job is to take an input like below:

Hello, world!

π is cool!

and output it as a series of <kbd>.

Every character, including enter and space get their own <kbd> HTML element, like so:

Hello,SPACEworld!NEWLINE

OPT + PSPACEisSPACEcool!

Other characters like space and newline that are invisible and typeable (so no option, command, control, function, escape, delete, arrow keys, etc.) are all uppercase, like SPACE and NEWLINE. OPT is an exception because it is used to create new characters. The code for these characters are:

<kbd>SPACE</kbd> <kbd>NEWLINE</kbd>


Special characters needing to be typed using option use the following format OPT + P instead of π. The following code is used for these:

<kbd><kbd>OPT</kbd> + <kbd>P</kbd></kbd>


The same applies to characters that are typed using OPT + SHIFT + K instead of .

We're assuming this is a QWERTY layout computer.

Here are the available option keys:

Any of the orange keys are not allowed in this.

Here are the OPT + SHIFT keys:

• +1 for well laid out challenge -1 for being mac specific – Rohan Jhunjhunwala Aug 9 '16 at 19:33
• @RohanJhunjhunwala It's not technically Mac-specific, but rather uses the same shortcut keys to type special characters as a Mac. – haykam Aug 9 '16 at 19:35
• Yeah, Ina all seriousness here have an upvote, It does seem like targetting the opt key may be somewhat confusing for some S̶a̶n̶e̶ pc users. – Rohan Jhunjhunwala Aug 9 '16 at 19:39
• For each letter you check which of the three character sets it is in then add some fixed strings to it. It doesn't seem to me like there is much interesting stuff to do in there? I'm not sure this adds much to the other keyboard focused challenges that we have. – FryAmTheEggman Aug 9 '16 at 20:23
• Do all of those characters even have Unicode codepoints? – Peter Taylor Aug 10 '16 at 5:31

# How synchronized are my clocks?

I have two clocks, A and B, and A always shows the exact time, however B is off by a certain amount of time, that I'd like to find out. (I know A and B run at the exact same speed.) I cannot read the exact time of both simultaneously, that means I can only switch back and forth and read the time sequentially. (For the sake of simplicity, both show their time as a real number (lets say hours), and each real number encodes an unique point in time.)

So here is an example: B: 1, A: 3, A: 5, B: 4.5. We see because of the first two entries B: 1, A: 3 that B is behind A by at most 2 hours, and that because of the last two entries A: 5, B: 4.5 we see that B is behind A by at least half an hour. So the possible interval of how much B is off is [-2,-0.5].

## Challenge

Given a list of timestamps with their labels, return the possible interval by how much B can be off.

## Details

• The list can be in any convenient format like [(timestamp, label),...] or as two lists [timestamp,...],[label,...] e.t.c
• You can assume that all the readings from A are in ascending. (and the same for B)
• If there is no such time interval, output something falsy.

## Testcases:

label  A  B  A
time   1  4  5
output [-1,3]

label  A B B A
time   1 2 5 2.5
output false


# Meta:

• Should only valid cases be considered, or should there be a check for invalid ones (remove point 2 or 3 of the details?)

• Should the challenge be restricted to alternating readings (ABABABABABA) or should random ones be allowed (ABBAAABABAABBBABBBBB)? Restricting to alternating readings would make it pretty much trivial.

• IMO go with alternating readings – Downgoat Aug 11 '16 at 23:26
• @Downgoat But that makes it almost trivial I think... – flawr Aug 11 '16 at 23:27
• We see that B is at least two hours behind, but at most half an hour behind. I find that wording confusing. How about this? We see (B: 1, A: 3) that B is behind A by at most 2 hours, and that (A: 5, B: 4.5) B is behind A by at least half an hour. – Luis Mendo Aug 11 '16 at 23:42
• @LuisMendo Thank you, I'm going to correct that. – flawr Aug 12 '16 at 8:41

# Print a booklet

I want to take a PDF document and put four pages of that document onto the front and four pages onto the back of a sheet of paper. Then I'll fold and cut that page so that I end up with a 1/4─size booklet that holds 8 pages. This would produce two folios comprising one signature.

           Fold here
↓
┌────┬────┐
│    │    │
│    │    │ ← Outer folio
Cut    │    │    │
here → ╞════╪════╡
│    │    │
│    │    │ ← Inner folio
│    │    │
└────┴────┘


LaTeX's pdfpages package allows me to place 2x2 pages of a PDF per sheet of paper with a given page ordering.

If I were to specify the option pages={2,7,4,5,8,1,6,3} to pdfpages, I would get:

       Front of sheet

(1)     (8)     Back of sheet
\     /
┌────┬────┐      (7)     (2)
│    │    │        \     /
Outer   │  2 │  7 │      ┌────┬────┐
folio → │    │    │      │    │    │
╞════╪════╡      │  8 │  1 │ ← Outer folio
Inner   │    │    │      │    │    │
folio → │  4 │  5 │      ╞════╪════╡
│    │    │      │    │    │
└────┴────┘      │  6 │  3 │ ← Inner folio
/          \     │    │    │
(3)            (6)  └────┴────┘
/           \
(5)            (4)

(Numbers put in parenthesis are referring to the back of the page.)


Why do we need that strange order of numbers? So that the fronts and backs of pages line up when put into the signature. This is how you read the book:

    Start here at (1) on the back. Continue to 2 on the front.
│
│      End here at (8)
↓     /
┌────┬────┐
│    │    │
│  2 │  7 │ ← Outer folio
│    │    │
└────┴────┘
│
On to (3) in
inner folio
│
↓     ↑
On to (6)
in outer folio
│
┌────┬────┐
│    │    │
│  4 │  5 │ ← Inner folio
│    │    │
└────┴────┘


But that's just for two folios from one sheet of paper. What if I want to use two sheets of paper, make four folios, and still combine all of them in one signature?

            Start at (1)
│
│      End here at (16)
↓       │
(1)    (16)  (5)    (12)
\     /      \     /
┌────┬────┐  ┌────┬────┐
│    │    │  │    │    │
Outermost → │  2 │ 15 │  │  6 │ 11 │ ← Folio #3
folio (#1) │    │    │  │    │    │
╞════╪════╡  ╞════╪════╡
│    │    │  │    │    │
Folio #2 → │  4 │ 13 │  │  8 │  9 │ ← Innermost
│    │    │  │    │    │    folio (#4)
└────┴────┘  └────┴────┘
/     \      /     \
(3)    (14)  (7)    (10)

Front of      Front of
sheet 1       sheet 2


And your LaTeX option would be:

pages={2,15,4,13,16,1,14,3,6,11,8,9,12,5,10,7}


## Objective

Write a function taking an integer n of the number of pages in the final booklet (8 and 16 in the examples above) and returning a list integers (of length n and ranging from 1 to n) for the page numbers in the right order.

Example:

> f(8)
=> [2,7,4,5,8,1,6,3]

> f(16)
=> [2,15,4,13,16,1,14,3,6,11,8,9,12,5,10,7]


Since we're dividing a sheet of paper into 4 pieces and using front and back, the input is always a multiple of 8. If the input is not a multiple of 8, the output is not defined but would prefer that it's rounded up to the next multiple of 8.

• Is the code required to work for integers that don't fit and leave unused pages? Should such integers be rounded up to the next integer that fits? – trichoplax Aug 12 '16 at 11:40
• 1. I don't understand the repeated mention of US Letter. Surely this is completely independent of the paper size? 2. I don't understand the first two diagrams. It seems to me that the instructions in the first diagram give a booklet with page order 2,3,4,1, and the folds in the two diagrams can only be consistent with each other if one of the 1s is turned upside down. 3. The meaning of folio doesn't seem to be consistent between the 4-page example (which has two folios, implying that a folio is a half-sheet of paper) and the 8-page example (which has just an outer and an inner folio). – Peter Taylor Aug 12 '16 at 12:09
• I specified what to do with integers that don't fit, removed mention of US letter, and simplified the diagrams. – Caleb Paul Aug 12 '16 at 16:52
• @PeterTaylor, the first example is 8 pages (1 physical sheet of paper divided into 2 folios), the second example is 16 pages (2 physical sheets of paper divided into 4 folios). A folio is just a half sheet of paper. I cleaned up the terminology of sheet vs page in the question. – Caleb Paul Aug 12 '16 at 16:56
• Ok, I think it's clearer now, but to check that I've understood what the task is. Would the following serve as a reference implementation? Given n which is a multiple of 8, form the array [1 2 ... n-1 n]. Then while the array is non-empty, remove the first four elements and the last four elements, apply permutation [2 7 4 5 8 1 6 3] to them, and recurse on the remaining elements. – Peter Taylor Aug 12 '16 at 17:40
• Might turn into something interesting, but if you just print, cut, fold, then sort and glue, there is nothing keeping you from switching upper with lower halfs, turning half-pages around or swapping half-pages between pages. You either need to specify the exact way the paper will be combined or you should add information which solutions are acceptable. – MarLinn Aug 13 '16 at 1:20

## Count Langford pairings

A Langford pairing is a permutation of the numbers 1, 1, 2, 2, ..., n, n such that there is one number between the 1s, two numbers between the 2s, etc. E.g. (with the pairs marked)

+-----------+ +---------------+
| +-----+   | | +---------+   |
| |     |   | | |         |   |
5 2 8 6 2 3 5 7 4 3 6 8 1 4 1 7
| |   |       | | | |   |
| |   +-------+ | | +---+
| +-------------+ |
+-----------------+


If we reverse a Langford pairing then obviously we get another Langford pairing. The number of distinct Langford pairings (i.e. modulo this symmetry) for given n is OEIS sequence A014552.

Write a program which takes n as either a command-line argument or on stdin and prints the number of distinct Langford pairings for that n. You may assume that the input given will be a positive integer no greater than 32.

To avoid hard-coding, your program must be capable of calculating the number of Langford pairings for n=32, optionally modulo a number of your choice which is at least 230; and the only case splitting permitted for valid input is to split on the value of n % 4.

To avoid brute-forcing, your program must be capable of calculating the number of Langford pairings for n=16 in less than 15 minutes on my reference machine. (TODO). The standard approach is an algebraic technique due to Mike Godfrey and works by evaluating a generating function at {-1,1}^2n, but variants such as evaluating Godfrey's generating function at {0,1}^2n and using inclusion-exclusion are also possible.

The time limit is about twice the time required by my (partially optimised) reference solution, an algebraic approach in Java; a fully optimised approach in C should have a lot of slack. That gives people a trade-off in the symmetries they use, and should allow slow scripting languages to submit valid answers but at a penalty of having to spend more code on handling symmetries than faster languages.

However, I'm worried that it might allow trivial modification of answers to Langford strings , so I probably need a reference implementation which works by enumeration for comparison.

• Wow, that's really unhelpful. That page for A014552 has a forumla of a(n) = A176127(n)/2, and guess what the page for A176127 has? Yep, a(n) = 2 * A014552(n). :P – Doorknob Oct 8 '14 at 11:38
• @PeterTaylor could you give us some hints on optimisation? As in, the basic hacks that nearly everyone will do? – Soham Chowdhury Oct 8 '14 at 12:39
• There's this now. – Martin Ender Aug 14 '16 at 14:18
• @MartinEnder, I ran across the linked page the other day when I was tidying my bookmarks (it now 404s), but I didn't remember that this was in the sandbox. IMO the performance requirement and ability to avoid enumeration mean that it wouldn't be a dupe. May try to write a reference implementation tomorrow, since it's a public holiday here. – Peter Taylor Aug 14 '16 at 16:35
• Yeah I wasn't sure whether it would be a dupe (or whether there would be ways to avoid enumeration), but I figured you'd be the best judge of that, so I just thought I'd let you know. – Martin Ender Aug 14 '16 at 17:40

# The Coin Flop KoTH

In this challenge, you start out with a stack of 100 coins, alternating between gold and silver:

1.   Gold
2.   Silver
3.   Gold
4.   Silver
...
99.  Gold
100. Silver


Now, Gold, Inc. will pay you for any gold coins you can give them. Furthermore, they really like bulk shipment. If a shipment contains N coins, they will pay you N^2 for that shipment.

However, you've only got 1 truck to share between you and your opponent, who has a similar contract with Silver, Inc.

# Game play

Each turn, the following steps occur:

1. Flip a section of coins (like pancakes)
2. Collect the top coins (of the same type)
3. Ship off the collected coins (worth N^2)

## 1. Flip:

You or your opponent can each select a range to reverse. For example, if you selected the range [1,3], the following would occur:

Gold                        Gold
Silver                      Gold
Gold          ->            Gold
Gold                        Silver
Silver                      Silver


Notice how the top stack now has 3 golds in a row, which would be worth 9.

However, you only get to flip every other turn, and your opponent gets to flip on the other turns.

# 2. Collect

We collect all similar coins from the top of the stack, and put them in the truck:

Silver
Silver
Gold
Silver
Gold


Would result in 2 Silvers being put in the truck.

# 3. Ship

If the truck contains gold coins, then we send it off to Gold, Inc and we get paid N^2, where N is the number of coins in the truck. (Our opponent gets paid if the truck contains silver coins)

After the stack is empty, the player with the most money wins!

# Sandbox questions:

1. Is this clear?
2. Does this seem interesting at all (if it isn't, please say so)? What are some interesting strategies you can come up with?
3. Is there a never-lose strategy?
4. I'm debating adding a "Freeze" as an alternative to "Flip", which would cause 2 collect/ship actions to occur. (Your opponent's turn would then be next)
• Could you add tags so it's clear this is a KOTH? – Zgarb Aug 15 '16 at 15:31
• "If the truck contains gold coins, then we send it off to Gold, Inc (otherwise Silver, Inc), and we get paid" Is this correct? Earlier you said that we had a contract with Gold, Inc and the opponent with Silver, Inc, so it seems that we should be paid for gold and the opponent for silver. – Peter Taylor Aug 15 '16 at 21:02
• @PeterTaylor does that make it clearer? – Nathan Merrill Aug 15 '16 at 21:09
• Yes, thanks. Follow-up: I presume the controller will show different things to the two players so we both think we're the one collecting gold? – Peter Taylor Aug 16 '16 at 5:38
• @PeterTaylor correct. The only difference players will notice is whether or not Gold is the first coin. – Nathan Merrill Aug 16 '16 at 12:20

Still to-do:

2. Make input requirements a little looser
3. Make output requirements looser
4. Specify that a full program is not required
5. Change the name of gem-elements maybe?
6. Come up with a title
7. Come up with a cool story

I saw this as a problem over on CodeReview, here is the original question. I thought it would be fun to golf.

You have discovered various rocks. Each rock is composed of various elements, and each element is represented by a lowercase letter from 'a' to 'z'. The same element can be present multiple times in a rock. An element is called a 'common-element' if it occurs at least once in each of the rocks. Given the list of rocks you have to determine how many different kinds of common-elements you have.

# Input Format

• Each rock is a string which consists of lowercase letters from 'a' to 'z' representing elements
• You can take the strings in whatever way is easy for you (lines from STDIN, pipe delimited STDIN, array of strings as a method param, etc.)

# Output Format

• The number of different types of common-elements for the given list of rocks. This can be as an integer or string

# Constraints

• There will always be at least one rock
• Each rock will always have at least one element
• You do not need to make a full program (functions & methods are allowed)

# Sample Input

abcdde
baccd
eeabg


# Sample Output

2


## Explanation

Only 'a' and 'b' are common-elements since these are the only characters that occur in each of the rocks' composition.

# More test cases

a

0

aa

0

aa
aa

1

zyxabc

0

abc
def

0

abc
a

1

abc
ab
cb

1

abc
cba

3

abcdefghijklmnopqrstuvwxyz
qwertyuiopasdfghjklzxcvbnm

26

defabc
bfgcde
chfgde
gedfhi
fgiejh

2

• N doesn't seem to actually be a useful input, so I'd consider making it optional. In addition, tight I/O requirements are usually frowned upon, I'd consider modifying it to allow any format that doesn't add any additional information. I'd also recommend removing the quote block, and adding at least one test case with N=1 and one where the result itszero. Good luck with your challenge and thanks for using the sandbox! :) – FryAmTheEggman Jun 23 '16 at 19:47
• Also can we take the input in the default list/array format for our language? As FryAmTheEggman, good luck with the challenge! – Blue Jun 23 '16 at 20:04
• How do I say "any format that doesn't add additional information" in a way that doesn't sound silly? Is that fine as-is? – Captain Man Aug 11 '16 at 18:36
• Nice edits, looking much better! If you want an example of a nice way to word the preamble, you could try emulating this question. I think "any reasonable format" is a fine way to say what you want, but what you have is fine, too. – FryAmTheEggman Aug 11 '16 at 19:44
• This might be fun to golf in Java, but in the languages which are predominantly used on this site nowadays it's two built-ins and something like 3 to 6 characters depending on the language, so it's actually a pretty boring question. – Peter Taylor Aug 11 '16 at 21:44

# Stratego

This is a KOTH challenge based on the popular board game Stratego.

# Rules

Stratego is played on a 10x10 board which looks like this (starting position):

  12345678910

A **********
B **********
C **********
D **********
E ..~~..~~..
F ..~~..~~..
G xxxxxxxxxx
H xxxxxxxxxx
I xxxxxxxxxx
J xxxxxxxxxx


*: enemy piece; x: your piece, .: empty space, ~: lake

There are twelve types of pieces: the flag (F), the bomb (B), the spy (S), and pieces numbered 2-10 (ten is 0). You can see the identities of your pieces, but not your opponent's. Each player starts with:

• 6 bombs
• 1 flag
• 1 ten
• 1 nine
• 2 eights
• 3 sevens
• 4 sixes
• 4 fives
• 4 fours
• 5 threes (miners)
• 8 twos (scouts)
• 1 spy

A player may arrange their pieces however they wish within their starting area.

The players take turns moving one piece into an adjacent square.

• The bomb and flag may not move.
• Twos (scouts) may move any number of squares in one direction, like a chess rook.
• You may not move into a square containing one of your pieces.
• If you attempt to move into a piece containing an enemy piece:
• The identities of both pieces are revealed to the other player.
• If both pieces are equal, they both lose.
• If both pieces are numbered, the higher piece wins.
• If the attacked piece is a bomb…
• and the other piece is a miner, the miner wins.
• otherwise, the bomb wins.
• If the attacked piece is the flag, then the player owning the flag loses.
• If the attacking piece is the spy…
• and the defending piece is a 10, the spy wins.
• otherwise, the spy loses.
• If the attacked piece is the spy, it loses.
• If the attacking piece won, the attacked piece is removed from the board and the attacking piece moves into its place.
• If the attacked piece won, the attacking piece is removed from the board and the attacked piece remains in place.
• If both pieces lose, they are both removed from the board.
• A scout's move may end on an enemy piece, but it may not go over enemy pieces during its move.

Play continues until one player loses their flag or is unable to move on their turn, at which point that player loses.

# Protocol

Bots may be written in any language that I can get to run on macOS. They will communicate with the server using newline-separated JSON on stdin/stdout. When a bot is started, it should send the following message:

{
"type": "start",
"layout": "..." /* starting layout, as 4x10 string; last line is edge of board */
}


When it is the bot's turn, the server will send the following message:

{
"type": "turn",
"board": "...", /* current board state, as 10x10 string; you half of the board is always on the bottom */
"yourPreviousTurn": { /* result of your previous turn; not present on your first turn */
"from": "B8",
"to": "B9", /* you moved a piece from B8 to B9 */
"movedPiece": "5" /* you moved a 5 */
"attackedPiece": "8" /* the piece you attacked was an 8; only present if you attacked a piece on your last turn */,
"winner": "them" /* their piece won; only present if you attacked a piece */
},
"theirPreviousTurn": { /* result of the turn they just took; not present on first turn of the game */
"from": "H8",
"to": "G8",
"movedPiece": "4" /* they moved a 4; only present if they attacked */
"attackedPiece": "9" /* they attacked your 9; only present if they attacked */,
"winner": "you" /* your piece won; only present if they attacked */
},
"yourGraveyard": ["B", "3", ...], /* array of your pieces that have already died */
"theirGraveyard": ["7", "4", ...] /* array of their pieces that have already died */
}


You must respond with:

{
"type": "move",
"from": "A6",
"to": "A7"
}


Submit your bot as a pull request to [github link added here]. You do not need to include your entire bot in the SE answer, but please include the main/interesting parts of the code; I would recommend not including the layouts that you are using so that they remain secret (not that secret, but better than nothing). I will run bots regularly and post the latest scores here.

• 1. Can you give references to indicate that there is no legal issue here (with respect to copyright, trademarks, etc)? 2. Why 2 to 9 and then 0? Would it be simpler to use 1 to 9? 3. The list of starting pieces could be presented much more succinctly as a single string (BBBBBBF9...), and the combat table as a grid with columns and rows headed by B, F, etc and using one of three symbols to indicate the outcome. 4. Docker images? Are you serious? You should be trying to lower the barrier of entry, not raise it. – Peter Taylor Aug 25 '16 at 9:57
• This is a dupe of my stratego challenge.... – Rohan Jhunjhunwala Aug 25 '16 at 14:10
• meta.codegolf.stackexchange.com/a/9653/46918 – Rohan Jhunjhunwala Aug 25 '16 at 14:11
• 1. I feel that the copyright on the game is unlikely to be enforced for something this small. 2. The original game uses 2-10, so I am staying with that. 3. That would be more succinct, but less useful for understanding the game -- it would be nice not to have to analyze a table to understand things like "larger number wins." 4. Agreed. I will edit to remove the Docker requirement. – Gaelan Aug 25 '16 at 15:29
• @Peter see above – Gaelan Aug 25 '16 at 15:31
• Whether the copyright holder decides to take action or not is irrelevant: if posting this challenge would violate copyright then this site's legal terms prohibit it. (CC @RohanJhunjhunwala). – Peter Taylor Aug 25 '16 at 16:48
• @PeterTaylor game rules can not be copyrighted: copyright.gov/fls/fl108.pdf – Gaelan Aug 25 '16 at 17:09
• @PeterTaylor from what I understand, developing an AI to play a game isn't really breaching the copyright of the game holder. However I feel we should take this to meta. – Rohan Jhunjhunwala Aug 25 '16 at 17:31
• @PeterTaylor feel free to continue to discuss this here meta.codegolf.stackexchange.com/q/9925/46918 – Rohan Jhunjhunwala Aug 25 '16 at 17:35
• Gaelan, the document you link states that game rules are subject to copyright: it's the mechanics which aren't. The design elements probably extend to such matters as board layout and tile distribution: or, at least, the major Scrabble clones' owners weren't confident enough of winning against Hasbro, and changed their layouts and distributions under legal pressure. And I (and the SE legal terms) also mentioned trademarks: Stratego is a registered trademark in the US. – Peter Taylor Aug 25 '16 at 21:49
• @RohanJhunjhunwala, the AI might not be, but a king-of-the-hill doesn't work without a controller. – Peter Taylor Aug 25 '16 at 21:50
• @PeterTaylor I will rename the challenge to avoid the trademark issue. Nothing in the PDF says anything about rules being copyrighted. It says the specific wording of the rules that came with the game are copyrightable, but I wrote the rules in my own words from memory. Also, see the dupe link in the meta question. – Gaelan Aug 25 '16 at 21:57
• @Gaelan you have failed to address the issue that it is a dupe of my challenge – Rohan Jhunjhunwala Aug 25 '16 at 22:00
• @PeterTaylor sure I can edit the name of my challenge to avoid stomping on a trademark. (But from what I understand you can saw the name of a company, without infringing their trademarks) – Rohan Jhunjhunwala Aug 25 '16 at 22:01
• @RohanJhunjhunwala sorry, I didn't realize your challenge was this recent. Are you still planning on running your challenge? – Gaelan Aug 25 '16 at 22:03

# De-Parenthesize Ruby

Reuben wants to start programming and golfing in Ruby. However, since he learned programming from his siblings Cecil and Emma, who program in C and ECMAScript respectively, he's developed a habit of adding parentheses to all sorts of functions when he doesn't need to. However, he can't just remove all the parentheses either! Help him by writing a short program that will remove some of the parentheses for him.

### The Challenge

Given a snippet of Ruby code (you don't need to worry if it's valid code or not), apply the following rules to remove parentheses from function calls wherever possible. Whenever parentheses are removed, put a whitespace in between the function call and the arguments (even if in actual golfing practice it isn't needed, such as in the case of print"hello")

For the purposes of this challenge, not all parts of Ruby need to be checked:

• Variables/functions will contain alphanumerics and underscore only, and won't start with numbers. (No functions like array.slice!(1,4).include?(6), and no variables like a) • Blocks (curly braces after functions, or for declaring stabby-lambdas) are not present. No array.map{|i|i+1} • Function definitions like def f(x) will not be present. • No backslashes \ so you don't have to parse something like "\"hello\"" • No comments. (Comments in Ruby start with #.) If a # appears in code, it's going to be part of a string. These are the only rules you need to check for: Functions without any parameters always have their parens removed. array.size()+array.something().length() -> array.size+array.something.length  Functions at the end of a method chain can be removed only if they are not next to an arithmetic operator. For the purposes of this challenge, the operators used will be +, -, *, /, %. num.parse(3,7) -> num.parse 3,7 string.gsub("this","that").count("t") -> string.gsub("this","that").count "t" 1+string.count("T") -> 1+string.count("T") # no change 1+(string.count("T")) -> 1+(string.count "T") puts(3,8*7) -> puts 3,8*7  If a function contains another function call as its only function argument, apply the other rules to that function as well. print(print(x.sub(a,b.to_s(16)))) -> print print x.sub a,b.to_s(16)  If a string substitution operator #{...} is present within a string (enclosed with double quotes), remove parens from the functions in accordance to the other rules. Assume that the contents within the string substitution don't include any literal strings, including single-character "question mark" strings like ?a. This means that things like "#{"a}#{"}" or "#{?}}" do not need to be dealt with. "hello() #{world().string(5)}" -> "hello() #{world.string 5}" "hello() # {world()}" -> "hello() # {world()}" # no change  Might add more rules or other things in the future if people want, before it gets published of course. Would this be a duplicate of something like Remove unnecessary parentheses? It's a similar concept but with different rules • The "only if they are not in an expression with an arithmetic operator" part seems like it might potentially be a problem. What about 1+(string.count("T"))? Or, how about: print(foo().bar())+1? I think you may want to more aggressively remove some of these edge cases. – FryAmTheEggman Aug 19 '16 at 12:45 • @FryAmTheEggman that's a good point. I will think about how to phrase that case with parentheses to make more sense. For the second example, since the first rule says that empty parens are always removed, it'd become print(foo.bar)+1 as expected anyways. – Value Ink Aug 19 '16 at 18:40 • I think a whitelist of language constructs would be clearer than listing a lot of things that aren't allowed. – feersum Aug 28 '16 at 11:59 • @feersum I don't understand what you mean by that. Should I say something like "only alphanumerics, the dot operator ., these arithmetic operators, and the string substitution operator in strings"? – Value Ink Aug 29 '16 at 17:23 • Yes, or better some sort of grammar describing the allowed input. – feersum Aug 29 '16 at 22:36 # Shift and Sum (I need a better title) Write a program or function that given an input list of non-negative integers of length l, outputs the sum of all the lists of length 2*l-1 that are the input list padded with 0s to each side. (Please suggest ways of improving this description) For example, with the input [1,2,3]: [1,2,3,0,0]+ [0,1,2,3,0]+ [0,0,1,2,3]= [1,3,6,5,3]  More test cases: [1]->[1] [2,1]->[2,3,1] [1,0,1]->[1,1,2,1,1] [0,1,0]->[0,1,1,1,0] [10,20,30]->[10,30,60,50,30] [0,0,0,0,0,0]->[0,0,0,0,0,0,0,0,0,0,0]  You may take input in any reasonable format. If you have any questions about whether an input form is reasonable, ask about it in the comments. • In other words, convolution [inserts dup] – Leaky Nun Aug 31 '16 at 1:42 • Do all the inputs consist of lists of integers 0-9, or can they be greater/negative? – Theo Aug 31 '16 at 1:42 • @Theo I was thinking they would be lists of non-negative integers. I will clarify that. – DanTheMan Aug 31 '16 at 1:47 • codegolf.stackexchange.com/q/80030/194 – Peter Taylor Aug 31 '16 at 7:38 # End the tabs versus space war So, there has been a great deal of debate of whether to use tabs or spaces to indent/format code. Can you help the university settle the dispute, by going to an incredibly crazy unique method of formatting. Your job is to write a full program or function which expands all tabs into four spaces. And then replaces a run of n leading spaces with "/(n-2 *'s)/". You will receive input over multiple lines in any reasonable format (single string array of strings for each new line. Columnar array etc.) Sample input shamelessly stolen. Note that tabs get automagically expanded to four spaces on SE, but you must handle tabs as well. Calculate the value 256 and test if it's zero If the interpreter errors on overflow this is where it'll happen ++++++++[>++++++++<-]>[<++++>-] +<[>-< Not zero so multiply by 256 again to get 65536 [>++++<-]>[<++++++++>-]<[>++++++++<-] +>[> # Print "32" ++++++++++[>+++++<-]>+.-.[-]< <[-]<->] <[>> # Print "16" +++++++[>+++++++<-]>.+++++.[-]< <<-]] >[> # Print "8" ++++++++[>+++++++<-]>.[-]< <-]< # Print " bit cells\n" +++++++++++[>+++>+++++++++>+++++++++>+<<<<-]>-.>-.+++++++.+++++++++++.<. >>.++.+++++++..<-.>>- Clean up used cells. [[-]<]l this is preceded by a tab two tabs three tabs etcetera!  Sample output Calculate the value 256 and test if it's zero If the interpreter errors on overflow this is where it'll happen ++++++++[>++++++++<-]>[<++++>-] +<[>-< /**/Not zero so multiply by 256 again to get 65536 /**/[>++++<-]>[<++++++++>-]<[>++++++++<-] /**/+>[> /******/# Print "32" /******/++++++++++[>+++++<-]>+.-.[-]< /**/<[-]<->] <[>> /******/# Print "16" /******/+++++++[>+++++++<-]>.+++++.[-]< <<-]] >[> /**/# Print "8" /**/++++++++[>+++++++<-]>.[-]< <-]< # Print " bit cells\n" +++++++++++[>+++>+++++++++>+++++++++>+<<<<-]>-.>-.+++++++.+++++++++++.<. >>.++.+++++++..<-.>>- Clean up used cells. [[-]<]l /**/this is preceded by a tab /******/two tabs /**********/three tabs etcetera!  Because the university needs space to download both Vim and Emacs. You are alloted very little storage for your code. Therefore this is and the shortest code wins. ### Disclaimer This "excellent" formatting strategy came courtesy of Geobits, and is reproduced with his permission. No programmers were harmed during the production of this challenge. • Disclaimer: By using this formatting, you hereby absolve Geobits of any liability for any injuries (intentional or otherwise) or damages you may receive as a result. Void where prohibited. – Geobits Aug 31 '16 at 4:00 • Also, do only leading spaces/tabs get replaced? – Geobits Aug 31 '16 at 4:03 • What does "expands all tabs into four space*" mean? Is it a straight replacement à la codegolf.stackexchange.com/q/57462/194 or does it mean expanding to tab stops every 4 chars à la codegolf.stackexchange.com/q/18960/194 ? – Peter Taylor Aug 31 '16 at 7:32 • @PeterTaylor essentially line.repaceAll("\t"," "); – Rohan Jhunjhunwala Aug 31 '16 at 12:07 • So all tabs get replaced by spaces, and then only leading spaces get replaced by "comments"? – Geobits Aug 31 '16 at 13:45 • @Geobits yes that is a very clear way of putting it. – Rohan Jhunjhunwala Aug 31 '16 at 15:22 • this is genius, I should start using it. – Maltysen Aug 31 '16 at 17:55 • You should delete this. now that it's been posted. – James Sep 2 '16 at 0:09 ## What is my birthday? In the system of surreal numbers, every number has a birthday, which is used to resolve ties in the case of there being more than one surreal number that would otherwise satisfy an equation. The very first surreal number to be created is zero, written as {|}. Its birthday is therefore zero. Having created zero, the next two surreal numbers to be created are 1 and -1. Their birthdays are therefore both 1. Each subsequent day brings in twice as many surreal numbers as the previous day: 2ⁿ-2 numbers are obtained by taking the averages of all the consecutive pairs from all previous days, with the first and last numbers simply incrementing in absolute value. For example, on the second day, the previous surreal numbers are -1, 0 and 1, giving averages of -½ and ½, to which we also add -2 and 2, whilst on the third day the new numbers are -3, -1½, -¾, -¼, ¼, ¾, 1½ and 3. As you can see, all finite floating-point representations have a finite birthday. (Most real numbers have an infinite binary fraction and therefore an infinite birthday). Your task is to write a program or function that outputs the birthday for a given floating-point number (using your native floating-point format). Although the birthday is always an integer, you can return it as an integer valued floating-point number if you prefer (e.g. if you don't have an unlimited integer type). Test cases: Number Birthday 1 1 0.5 2 -21 21 6.5 8 -7.9375 12  This is , so the shortest program wins. • Could you perhaps please add how the number generation process works? – Sp3000 Sep 2 '16 at 11:13 • @Sp3000 The line beginning "In general" was supposed to explain that, although there was some spurious text on it that you may have found confusing. – Neil Sep 2 '16 at 11:31 • Hmm right, I see. Sorry it took me a while to get what it meant - maybe a quick example, e.g. saying the third day takes averages from 2, 1, ½, 0, -½, -1, -2? (to drive home the "all previous birthdays" part). But otherwise I think this looks pretty good. – Sp3000 Sep 2 '16 at 14:59 • Maybe you should give more examples from Knuth because, for instance, from your current explanation it is unclear why 1/3 should have a birthday of ω: it is not a finite sum of dyadic rationals. Or better give example inputs and expected outputs. – Andreï Kostyrka Sep 3 '16 at 1:10 • Consider adding these test cases: Input: 1, 0.5, -21, 6.5, -7.9375 and Output: 1, 2, 21, 8, 12. – Andreï Kostyrka Sep 3 '16 at 1:56 ## 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 # Handwriting Recognition I made a similar suggestion a month or so back which was deemed to be too similar to an existing one, so I've added something along the lines of a kolmogorov-complexity requirement. The MNIST dataset is a series of handwritten digits used as a standard testbed for machine learning, pattern recognition techniques. Each image is of a single digit, 0-9; as a 28x28 pixel grayscale matrix with values from 0-255. The challenge is to create a classifier for MNIST that scores an Error Rate of less than [TBD] in the least number of bytes possible. Your program must take a 784 element long array in whatever format is applicable for your language representing a single image and return a number between 0 and 9, guessing what the number is. For example, the input for the first digit might be: [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 18, 18, 18,126,136,175, 26,166,255,247,127, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30, 36, 94,154,170,253,253,253,253,253,225,172,253,242,195, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 49,238,253,253,253,253,253,253,253,253,251, 93, 82, 82, 56, 39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18,219,253,253,253,253,253,198,182,247,241, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 80,156,107,253,253,205, 11, 0, 43,154, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 1,154,253, 90, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,139,253,190, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11,190,253, 70, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 35,241,225,160,108, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 81,240,253,253,119, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 45,186,253,253,150, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 93,252,253,187, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,249,253,249, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 46,130,183,253,253,207, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 39,148,229,253,253,253,250,182, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24,114,221,253,253,253,253,201, 78, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 23, 66,213,253,253,253,253,198, 81, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18,171,219,253,253,253,253,195, 80, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 55,172,226,253,253,253,253,244,133, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,136,253,253,253,212,135,132, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]  Each algorithm will be tested over a set of 200 images and are expected to get [TBD]/200 correct. Of course, when developing any good classifier, you need to test how well it works with a completely unknown sample. The twist of the challenge, these are the 200 images I am going to test with right here: (a link to 200 images and their correct labels). You only need to make sure you can classify at least [TBD]/200 of these, your algorithm won't be run on anything else. As such, this can be considered a kolmogorov complexity challenge with an acceptable error rate. ## Conditions: • This is code golf. The shortest piece of code that meets the criteria wins. • The code must take a provided 784 element long input and attempt to classify it. • Testing will take place on my computer at 12pm AEST on Saturday the (date two weeks after the competition is published). I will run each classifier over the published set of 200 images. To be considered, it must correctly classify [TBD]/200 of them. If I can't get your code to run, it wont be counted, so help with loading the images in your language would be appreciated. • Standard loopholes are not permitted. # Questions for Sandbox • Overall thoughts on the challenge? • Any ideas on a good cutoff for the classifier? I was thinking around 60% correct. Very low when compared to existing solutions to MNIST, but should promote good code golfing. I was going to have a go at it myself to see what I could reasonably achieve. • Does the testing clause make sense? Is it reasonable? Should I put a limit on the languages so I know I'll be able to run them? • Since barrier to entry is a bit high (knowing how to get hold of the images, possibly some ML experience), is there anything extra I should do to make it easier to start the challenge. • This is a modification of my first suggestion for a challenge, is there anything I'm missing? • I recommend a time limit, especially if you intend to test them yourself. It can be generous, but without one then the requirement to golf will naturally give very long run times which you may not wish to commit your computer to... – trichoplax Oct 18 '16 at 12:09 • Do submissions need to be deterministic? That is, should the results be identical each run? – trichoplax Oct 18 '16 at 12:22 • For choosing the maximum error rate, think about what kinds of approaches you want to see. For a sufficiently high error rate, it may be possible to look only at a small number of pixels and ignore most of the image. If you want this kind of approach, try to choose an error rate that makes it challenging but possible. If you prefer more complex approaches, the error rate will need to be set a little lower. – trichoplax Oct 18 '16 at 12:33 # Classify Alternating Permutations An alternating permutation of [1, 2, 3, ..., n] is an arrangement such that each element is either greater than its previous and greater than the next, meaning p[i-1] < p[i] > p[i+1] or lesser than the previous and lesser than the next, meaning p[i-1] > p[i] < p[i+1]. In other words, this means that each run of three consecutive elements should never be strictly increasing or decreasing. There is a further distinction that an alternating permutation can be either UP or DOWN. For UP, this means that the alternating permutation begins with the first element being less than the second, and the opposite is true for DOWN. For example, there are 4! = 24 permutations of [1, 2, 3, 4] 1 2 3 4 1 2 4 3 1 3 2 4 Alternating UP since 1 < 3 > 2 < 4 1 3 4 2 1 4 2 3 Alternating UP since 1 < 4 > 2 < 3 1 4 3 2 2 1 3 4 2 1 4 3 Alternating DOWN since 2 > 1 < 4 > 3 2 3 1 4 Alternating UP since 2 < 3 > 1 < 4 2 3 4 1 2 4 1 3 Alternating UP since 2 < 4 > 1 < 3 2 4 3 1 3 1 2 4 3 1 4 2 Alternating DOWN since 3 > 1 < 4 > 2 3 2 1 4 3 2 4 1 Alternating DOWN since 3 > 2 < 4 > 1 3 4 1 2 Alternating UP since 3 < 4 > 1 < 3 3 4 2 1 4 1 2 3 4 1 3 2 Alternating DOWN since 4 > 1 < 3 > 2 4 2 1 3 4 2 3 1 Alternating DOWN since 4 > 2 < 3 > 1 4 3 1 2 4 3 2 1  The permutations left unmarked are NOT alternating. Your goal is take a permutation and output whether it is • alternating UP • NOT alternating • alternating DOWN ## Rules • This is so the shortest code wins. • You are allowed to modify the input be 0-indexed, 1-indexed, or a permutation of the English alphabet abcdefghijklmnopqrstuvwxyz in uppercase or lowercase. • The length of the input will be between 2 and 26. • You are allowed to choose your own output to represent the three classes but you must state what they are in your submission. ## Test Cases 1 2 UP 2 1 DOWN 1 2 3 NOT 1 3 2 UP 2 1 3 DOWN 2 3 1 UP 3 1 2 DOWN 3 2 1 NOT <more to be added...>  • The phrase "each element is greater than or less than the previous element" is not very clear (arguably, it just means that consecutive elements are distinct, which always holds in a permutation). I suggest something like "doesn't contain an increasing or decreasing run of three consecutive numbers", and then you can clarify that the permutation alternates between rising and falling pairs. – Zgarb Oct 20 '16 at 10:20 • @Zgarb I've tried to clarify the definition a bit more – miles Oct 20 '16 at 11:53 • Isn't "each element is either greater than its previous and lesser than the next or lesser than the previous and greater than the next" the exact opposite of what an alternating permutation is? It should be either greater than both the previous and the next, or lesser than both. – Emigna Oct 20 '16 at 13:11 • @Emigna Thanks, I got it backwards. – miles Oct 20 '16 at 18:13 • Can I adopt this abandoned proposal? – programmer5000 Jun 9 '17 at 12:38 Note: this is an attempt to fix up a currently closed question by someone else so that they can rescue it, not an attempt to steal their question. When implementing an algorithm for correcting aliased measurement data, I hit the need to implement following function. The function takes input bitstring on the left, and should produce the integer and list on the right:  1 => 1, [0] 10 => 1, [0] 100 => 1, [0] 101 => 2, [0, 1] 1000 => 1, [0] 1011 => 3, [0, 2, 1] ... more test cases at end of post ...  Note that it is guaranteed that the input bitstring is aperiodic. ## Physical background Consider a digital system that changes its output every N clock cycles. A measurement system doesn't know N, so it reads the output every M cycles, where M <= N. Now some of the measurement samples will be identical to the previous ones, which is represented as 0 in the bitstring and the sample is discarded. When the value changes, 1 is added to the bitstring and the sample is stored. However, the timestamp of the sample will be too late. The numbers in the output array represent a correction that must be applied. The output format expresses this correction as a fraction of the sample interval, where the standalone integer is the denominator and the array contains the numerators. As an example with N = 4 and M = 3: Clock cycle 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 Output A A A A B B B B C C C C D D D D E E E E Measurement A A B C D D E Bitstring 1 0 1 1 1 0 1 |---------------------| This is the period of the aliasing Timestamp | |---| |-| | |---| correction 0 2/3 1/3 0 2/3  With this example the input would be 1011 and the output would be 3, [0, 2, 1]. ## Here are a few observations to get you started: • The input sequence always begins with 1 and is aperiodic. • The output sequence length always equals the number of 1-bits in the input. • The output sequence array is always a permutation of 0 to M-1 and begins with 0. ## Test cases:  1 => 1, [0] 10 => 1, [0] 100 => 1, [0] 101 => 2, [0, 1] 1000 => 1, [0] 1011 => 3, [0, 2, 1] 10000 => 1, [0] 10010 => 2, [0, 1] 10101 => 3, [0, 1, 2] 10111 => 4, [0, 3, 2, 1] 100000 => 1, [0] 101111 => 5, [0, 4, 3, 2, 1] 1000000 => 1, [0] 1000100 => 2, [0, 1] 1001010 => 3, [0, 2, 1] 1010101 => 4, [0, 1, 2, 3] 1011011 => 5, [0, 3, 1, 4, 2] 1011111 => 6, [0, 5, 4, 3, 2, 1] 10000000 => 1, [0] 10010010 => 3, [0, 1, 2] 10101101 => 5, [0, 2, 4, 1, 3] 10111111 => 7, [0, 6, 5, 4, 3, 2, 1] 100000000 => 1, [0] 100001000 => 2, [0, 1] 100101010 => 4, [0, 3, 2, 1] 101010101 => 5, [0, 1, 2, 3, 4] 101110111 => 7, [0, 5, 3, 1, 6, 4, 2] 101111111 => 8, [0, 7, 6, 5, 4, 3, 2, 1] 1000000000 => 1, [0] 1000100100 => 3, [0, 2, 1] 1011011011 => 7, [0, 4, 1, 5, 2, 6, 3] 1011111111 => 9, [0, 8, 7, 6, 5, 4, 3, 2, 1] 10000000000 => 1, [0] 10000010000 => 2, [0, 1] 10001000100 => 3, [0, 1, 2] 10010010010 => 4, [0, 1, 2, 3] 10010101010 => 5, [0, 4, 3, 2, 1] 10101010101 => 6, [0, 1, 2, 3, 4, 5] 10101101101 => 7, [0, 3, 6, 2, 5, 1, 4] 10110111011 => 8, [0, 5, 2, 7, 4, 1, 6, 3] 10111101111 => 9, [0, 7, 5, 3, 1, 8, 6, 4, 2] 10111111111 => 10, [0, 9, 8, 7, 6, 5, 4, 3, 2, 1] 100101001010 => 5, [0, 3, 1, 4, 2] 101010110101 => 7, [0, 2, 4, 6, 1, 3, 5] 101111111111 => 11, [0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 111111111111 => 13, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 1000000100000 => 2, [0, 1] 1000010001000 => 3, [0, 2, 1] 1000100100100 => 4, [0, 3, 2, 1] 1001001010010 => 5, [0, 2, 4, 1, 3] 1001010101010 => 6, [0, 5, 4, 3, 2, 1] 1010101010101 => 7, [0, 1, 2, 3, 4, 5, 6] 1010110101101 => 8, [0, 3, 6, 1, 4, 7, 2, 5] 1011011011011 => 9, [0, 5, 1, 6, 2, 7, 3, 8, 4] 1011101110111 => 10, [0, 7, 4, 1, 8, 5, 2, 9, 6, 3] 1011111011111 => 11, [0, 9, 7, 5, 3, 1, 10, 8, 6, 4, 2] 1011111111111 => 12, [0, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 10000100001000 => 3, [0, 1, 2] 10010010010010 => 5, [0, 1, 2, 3, 4] 10101101101101 => 9, [0, 4, 8, 3, 7, 2, 6, 1, 5] 10111011110111 => 11, [0, 8, 5, 2, 10, 7, 4, 1, 9, 6, 3] 10111111111111 => 13, [0, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 100000001000000 => 2, [0, 1] 100010001000100 => 4, [0, 1, 2, 3] 100101010101010 => 7, [0, 6, 5, 4, 3, 2, 1] 101010101010101 => 8, [0, 1, 2, 3, 4, 5, 6, 7] 101101110111011 => 11, [0, 7, 3, 10, 6, 2, 9, 5, 1, 8, 4] 101111110111111 => 13, [0, 11, 9, 7, 5, 3, 1, 12, 10, 8, 6, 4, 2] 101111111111111 => 14, [0, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]  # Finding isomorphic elementary cellular automata An elementary cellular automaton is a one-dimensional cellular automaton with two possible states (labeled 0 and 1) and calculates the following state based on a cell and its two immediate neighbors. Each elementary cellular automaton has a rule attached to it that specifies the resulting state for each of the configurations of a cell and its immediate neighbors. The most common scheme for numbering these rules being the Wolfram code, where we assign each rule a number from 0 to 255 which has become standard. Each possible current configuration is written in order, 111, 110, ..., 001, 000, and the resulting state for each of these configurations is written in the same order and interpreted as the binary representation of an integer. This number is taken to be the rule number of the automaton. As an example, we look at rule 110: Cell configuration 111 110 101 100 011 010 001 000 Resulting state 0 1 1 0 1 1 1 0  Converting 01101110 back to decimal gives us 110. Not all rules are equal, of course. Of the 256 possible rules, many of these rules are trivially equivalent to each other up to a simple transformation of the underlying geometry. Each rule will have three isomorphic rules based on three transformations, though sometimes a rule will be isomorphic to itself under a particular transformation. The first such transformation is reflection through a vertical axis and the result of applying this transformation to a given rule is called the mirrored rule. These rules will exhibit the same behavior up to reflection through a vertical axis, and so are equivalent in a computational sense. For example, if the definition of rule 110 is reflected through a vertical line, the following rule (rule 124) is obtained: Cell configuration 111 110 101 100 011 010 001 000 Resulting state 0 1 1 1 1 1 0 0  We swap only those cell configurations that are different when reflected through a vertical axis. The result of 110 is swapped with the result of 011, and the result of 100 is swapped with the result of 001. Everything else remains in place, as they are symmetrical. The second such transformation is to exchange the roles of 0 and 1 in the definition. The result of applying this transformation to a given rule is called the complementary rule. For example, if this transformation is applied to rule 110, we get the following rule: Cell configuration 000 001 010 011 100 101 110 111 Resulting state 1 0 0 1 0 0 0 1  and, after reordering, we discover that this is rule 137: Cell configuration 111 110 101 100 011 010 001 000 Resulting state 1 0 0 0 1 0 0 1  Finally, the previous two transformations can be applied successively to a rule to obtain the mirrored complementary rule. For example, the mirrored complementary rule of rule 110 is rule 193. Of the 256 elementary cellular automata, there are 88 which are inequivalent under these transformations. The challenge • Your task is given an input rule number, determine which elementary cellular automata are isomorphic under these rules. • The output should be a list (or equivalent) that represents: • The smallest Wolfram rule that is isomorphic to the input, • Its mirrored rule, • Its complementary rule, and • Its mirrored complementary rule. • The output list may be reordered, though it should always be clear which rule is the smallest, the mirrored rule, and so on. Just sorting the list will not help here. • This is code golf. Smallest number of bytes wins. As always, if this challenge needs clarification or correction, let me know. Good luck and good golfing! Test cases All of the following test cases have the format [smallest, mirrored, complementary, mirrored complementary]: 110 [110, 124, 137, 193] 232 [232, 232, 232, 232] 0 [0, 0, 255, 255] 16 [2, 16, 191, 247] 42 [42, 112, 171, 241] 144 [130, 144, 190, 246]  # Sandbox questions • Can the specification be clearer or shorter? • Should I change this challenge from code golf to some other scoring system? • Should the input be different and challenge changed? If so, which of the following input systems should it be: • The input that is currently used: a single rule number, and the challenge is changed to only finding the isomorphisms. • The number of states of the automaton, where finding the complementary rules would be more complex (for 2 states, only two possible complements; for 3 states, six complements are possible). This would extend the definition of both the Wolfram code and the cellular automata. • Any other suggestions? • Wouldn't this be a kind of kolmogorov-complexity challenge, considering the fixed output? – LegionMammal978 Oct 22 '16 at 12:34 • @LegionMammal978 Nuts, you're right. Well, as the "Sandbox questions" section asks, what should the input be, in your opinion? – Sherlock9 Oct 22 '16 at 12:36 • Perhaps you could input a rule number, and the program should find the smallest isomorphic rule and then output its four-element list. – LegionMammal978 Oct 22 '16 at 12:39 • @LegionMammal978 Seems reasonable. I'd still like a challenge where you have to find the four-element list for all combinations, but perhaps that can be a sequel. I'll edit the challenge. – Sherlock9 Oct 22 '16 at 12:40 • Surely reflection through a vertical axis is reflection horizontally, not vertically? – Peter Taylor Oct 22 '16 at 18:33 • @PeterTaylor Thanks! Any other corrections or suggestions? – Sherlock9 Oct 22 '16 at 20:35 • That was the only thing I noticed. – Peter Taylor Oct 22 '16 at 21:31 ## Permutation-Tolerant Hello World Inspired by Fault-Tolerant Hello World (a.k.a. the Interview). ### Task Write a program that prints Hello World. Sounds easy, right? Ok, lets challenge up a bit : your (real) task is to maximum the number of permutations of the characters of your code that produce a code that when executed prints Hello World as well. Hmm, I even got myself confused with that last sentence, so let's see an example : Consider the following code (it's good enough to understand the principle, but as I'll explain later, the score of such a code will be pretty low) : (it's Perl code, and if you don't trust me when I say it works, you can run it with perl -e 'code' in your terminal) print+("Hello World")  When ran, it prints Hello World. Well, the following permutations of the code also print Hello World : +(print"Hello World") +print("Hello World") (print+"Hello World") ()+print"Hello World"  Note that only permutations that produce a code that differs from the previous ones should be considered. For instance, the original code where the two l have been swapped isn't a valid permutation. ### Scoring The score of your solution is the number of bytes of your code divided by the number of valid permutations. Lowest score wins. In case of draw, the earliest solution wins. For instance, my example above was 21 bytes long, and had 5 valid permutations (note that it includes the original code), so its score is 21/5 = 4.2. ### For the sandbox (1- Does it sound like a nice challenge? 2- Is it clear? ) 3- I don't really what tags to add... 4- I'm not sure about the scoring method. In particular, I wonder if just adding useless stuff around the "print hello world" part of the program (no matter the language) might allow a lot of permutations to be valid with some languages. I'd like the code where all permutations are valid and that is the longest possible to win. And I'm not sure my scoring method will produce such results. 5- Is a "print hello world" program the more relevant? Actually I think that the code could do anything : calculating oeis sequence, drawing rectangles or whatever, as long as all the permutations produces the same behavior. But then some people might play on internal behavior of languages such as "by default, this language prints 1", so every permutation of any source will print 1, or stuffs like this... Any thoughts? 6- I thought about making this challenge harder by actually changing "as much permutations as possible should be valid" to "all permutations should be valid". This will of course prevent a lot of languages to compete, but might result in creative and nice answers. • If I've read this challenge correctly, Unary is going to win with (astronomical number) divided by (astronomical number factorial). Of course, this could still be a good challenge in other languages regardless, but the scoring as is means that it's beneficial to pad the program as long as possible since the denominator grows factorially compared to the linear numerator - so yeah I think a different scoring method might be necessary (no good ideas off the top of my head though) – Sp3000 Oct 24 '16 at 23:07 • @Sp3000 Thanks for your comment. I think that this sentence Note that only permutations that produce a code that differs from the previous ones should be considered (which I wrote right after the examples) will prevent Unary to win since it will have 0 valid permutations. – Dada Oct 25 '16 at 7:30 • Oh right, jumped the gun and missed that sentence. In that case I think you can use Lenguage instead? (since it's basically Unary but you can choose the chars) – Sp3000 Oct 25 '16 at 10:49 • Something like print"Hello World";123456789123456789 still produces a huge number of permutations. – xnor Oct 25 '16 at 17:16 • @xnor indeed. I was worried (cf question 4 for the sandbox) that something like that could be possible, and it obviously is. So ask for all the possible permutations to be valid would be a better challenge? Or should I just drop that challenge? – Dada Oct 25 '16 at 17:18 • If using a language with nops, [hello world program][arbitrary number of nops] will be even worse than xnors example – Destructible Lemon Oct 26 '16 at 23:52 # Display an xkcd xkcd is everyone's favorite webcomic, and you will be writing a program that will bring a little bit more humor to us all. Your objective in this challenge is to write a program which will take a number as input and display that xkcd and its alt-text (mousover text). ## Input Your program will take an integer as input and display that xkcd: for example, an input of 1500 should display the comic "Upside-Down Map" at xkcd.com/1500, and then either print its alt-text to the console or display it with the image. Due to their proximity across the channel, there's long been tension between North Korea and the United Kingdom of Great Britain and Southern Ireland. Your program should also be able to function without any input, and perform the same task for the most recent xkcd found at xkcd.com, and it should always display the most recent one even when a new one goes up. You do not have to get the image directly from xkcd.com, you can use another database as long as it is up-to-date and already existed before this challenge went up. You may not display the entire webpage in an iframe or similar. You can handle the case that there isn't an image for a particular comic (i.e. it is interactive or the program was passed a number greater than the amount of comics that have been released) in any reasonable way you wish, including throwing an exception, or printing out an at least single-character string, as long as it somehow signifies to the user that there isn't an image for that input. This is a challenge, so the fewest bytes wins! • I think this is probably a duplicate of codegolf.stackexchange.com/q/91847/194 – Peter Taylor Oct 25 '16 at 18:29 • @PeterTaylor It's similar, however I think that it's different enough to warrant it's own question. That puzzle required the creation of a bot that will display any new xkcd that comes up, this one just displays one, but it can be any requested one. In addition, my puzzle also requires the title text to be displayed. – Pavel Oct 25 '16 at 19:23 ## Killer Sudoku Pro suggestions Regular Sudoku is just about creating a enhanced Latin square and features no arithmetic on the digits 1-9 which are traditionally used. Killer Sudoku goes further: the puzzle is tiled with polyominoes which are labelled with the sum of the cells which they cover. Additionally, no polyomino may cover two cells with the same digit, even though those digits would otherwise have been legal because they are not in the same row, column or square. It is therefore helpful to be aware of the inverse relationship: given a quantity of cells and a sum, calculate the possible values of the cells. This is also useful for solving Kakuro, which also features sums of distinct digits. Killer Sudoku Pro goes one further step: rather than being the sum of the cells, any of the four basic operations may be used. The digits in the cells must then satisfy that basic operation. Given a target, operator and number of cells, I would like you write a program or function to output sets of distinct digits that satisfy the arithmetic expression. To minimise the necessary output I only want distinct combinations of digits, rather than all the potential permutations. (Some puzzle creators will not allow all the permutations for subtraction and division, so taking that into account would unnecessarily complicate the question.) Examples (example input format: target, operator, (number of cells); output format: answers " or "-separated, digits operator-separated in descending order): 14+(4) -> 8+3+2+1 or 7+4+2+1 or 6+5+2+1 or 6+4+3+1 or 5+4+3+2 4-(3) -> 9-4-1 or 9-3-2 or 8-3-1 or 7-2-1 24×(3) -> 8×3×1 or 6×4×1 or 4×3×2 2÷(2) -> 8÷4 or 6÷3 or 4÷2 or 2÷1  I/O may be in any reasonable format as long as it is clear what is going on, so you can't encode the operations as specific integers, although using * and / or their Unicode code points instead is OK, and answers must use a different separator to the digits in each answer. This is , so the shortest solution in bytes wins. • Could be worth noting that the only numbers to be considered are 1-9 (or you could add a third input for 1-N) – Jonathan Allan Oct 31 '16 at 11:23 • @JonathanAllan I didn't realise 10 was a digit, but I guess I should specifically exclude 0. – Neil Oct 31 '16 at 12:57 • Oh, I didn't notice "digit" :) – Jonathan Allan Oct 31 '16 at 12:59 • I find the sentence begining "Some puzzle creators allow the digits from the polyomino to be used in any order" to be odd to the point of disruptive. It presupposes a "correct" order to the elements of the polyomino which isn't obvious, and the logical connection is weak. I suggest rewriting it along the lines of "You should only output one representative suggestion for each distinct set of digits; so e.g. one but not both of 9-4-1 and 9-1-4", possibly with a footnote to discuss variations between puzzle setters in whether order is significant. – Peter Taylor Oct 31 '16 at 21:48 • @PeterTaylor The justification is only 9-4-1 and 9-1-4 actually evaluate to 4, so some creators will only use 4- for those two permutations, but I decided the question needed editing anyway. – Neil Oct 31 '16 at 22:36 • My point about permutations was that if the polyomino is e.g. the X pentomino then the "natural" order of the cells is up for debate. But I think the new wording side-steps that concern. – Peter Taylor Nov 1 '16 at 8:03 # Cryptographically secure favicon. Create a cryptographically secure program which will take a string of up to 24 characters and create an image such that differing inputs can be "easily" distinguished visually. The goal being that the end image is visually appealling, and it is impossible to reverse engineer the string. The challenge • Create a program or function which takes an input string and output an image in any desired format. • Pick a secret password and post an image generated with that password along with your submission code. • Optionally post some sample inputs and outputs. OR • Try to post someone else's password (or just any existing collision with that password). The scoring • Out of the posts whose password has not been cracked the post with the most upvotes after an arbitrary time period set sometime in the significant future. Voters are encouraged to vote based on ingenuity and aesthetic appeal, but can vote for whatever posts they like. • This is essentially the same as codegolf.stackexchange.com/q/25443/194 and codegolf.stackexchange.com/q/95836/194 – Peter Taylor Oct 29 '16 at 21:32 • @PeterTaylor I think this challenge is fundamentally different in that the format of the output is not fixed, and the method of encoding the image should be interested. – Rohan Jhunjhunwala Oct 30 '16 at 4:05 • To be clear, unlike those two questions, the answers of this question should usually output visually distinguishable images for different secrets, instead of – jimmy23013 Oct 31 '16 at 12:40 • I'd call this too broad. On top of hashing, find a pleasing way to represent it is largely a question of art and aesthetics. Having different outputs be visually distinguishable happens is easy if the hash function already brings close inputs to far outputs. – xnor Nov 2 '16 at 3:56 • I have to agree with xnor here, as stated, this is too broad. However, I think the idea is interesting, although there will always be the issue of defining what cryptography is "too good" (and thereby already disallowed). Also, it might be that the good essence of this challenge is completely covered by the links from Peter – Liam Nov 3 '16 at 1:00 • @xnor we have had "art"challenges throughot the graphical output tag. – Rohan Jhunjhunwala Nov 3 '16 at 10:32 ## Table Math You should which side of a table is the oldest, from ASCII art. I think the best way to explain is with an example, so here is one. You have a table, made out of +, |, and -. Here is one. +--+ | | | | | | +--+  It will alway be a rectangle, just not always square (but it can be square). There will also be people around the table, marked by the letters A-Z. There will never be too many people on a side, or less than one. Just to make it harder, the people will not always be in order, like this:  P +--+ I| | O| |Q | |J +--+ U  There will never be anybody next to a plus sign(+). You will be given input on how old each member is, separated by a newline, from the first letter that appears alphabetically (I in this example) to the last letter that appears alphabetically (U in this example), like this: 20 8 31 56 6 56  As seen here, ties are allowed. You should then output the sides with their ages separated with a space, in order from oldest to youngest, like this. Top 56 Bottom 56 Left 51 Right 14  Note that for everything in this challenge, you can choose the capitalization of the letters, even the input. The winner is the submission with the shortest code. # Interpret Developers Developers is a joke language that parodies an incident at a Microsoft Developer's conference where Steve Ballmer is supposed to have chanted the word developers at least 14 times in a row. It is basically Brainfuck with a few extensions. It appeared briefly in the Wikipedia in the beginning of 2006, but it has not reappeared anywhere since its deletion. [source] Your job today is to ressurect this beautiful language, and create an interpreter in the fewest number of bytes. You will have to implement the following commands, which contain their Brainfuck and C equivalents: | Key | BF Equiv | C Equiv | |----------------|----------|-----------------| | "Developers" | + | ++*ptr; | | "Developers"*2 | - | --*ptr; | | "Developers"*3 | > | ++ptr; | | "Developers"*4 | < | --ptr; | | "Developers"*5 | , | *ptr=getchar(): | | "Developers"*6 | . | putchar(*ptr); | | "Developers"*7 | [ | while (*ptr) { | | "Developers"*8 | ] | } |  As this is standard , the aim of the game is to create the shortest interpreter possible. # Specification Your interpreter should behave accordingly: • Developers/Developerz commands are separated by any whitespace. • Anything that is not a valid command should be ignored. • There will never be any more than 8 Developers (or 3 Developerz) present in the program that are not separated by whitespace. • Input can be interactive or provided at runtime. # Bonus If you would like to earn bonus points, you can also implement the following three extensions to the Developers language. These do not have a Brainfuck equivalent. | Key | C Equiv | |----------------|----------------------------------| | "Developerz" | Sleep(strlen(buffer)*10); | | "Developerz"*2 | system("cls");||system("clear"); | | "Developerz"*3 | *p = rand() & 0xFF; |  If the goal of these is not clear: • Developerz should sleep the program for 10ms for ever character in an input string • DeveloperzDeveloperz should clear the screen. • DevelopersDeveloperzDeveloperz should assign the currently pointed to cell to a random integer between 0 and 255. For each command you implement, you may multiply your score by 0.75. Thus, by implementing all three, your score would be 42.1875% of the byte count. • That's a pretty big bonus for implementing the three extensions. That's probably either such a hard task no one will go for it or such a huge bonus everyone will <i>have</i> to go for it. – Pavel Nov 8 '16 at 3:56 • @Pavel I had made it that much because I felt that these bonuses would only benefit languages that were verbose enough that they probably wouldn't beat a Jelly/Python/05AB1E answer (except for the random number functionality), and I dont think the shorter languages tend to have sleep functions or system calls available to them. – Kade Nov 8 '16 at 11:11 • This seems like a dupe of "Interpret BF" to me. – Peter Taylor Nov 8 '16 at 14:34 # Regex Crossword ## Challenge Write the shortest program that outputs a valid solution to a regex crossword. A regex crossword is a crossword that has regular expressions for the clues, like in this Puzzling SE puzzle: The Prognosticator. ### Terminology your program needs to know (simplified from here) Quantifiers: x* 0 or more of x (any group instruction) x+ 1 or more of x x? 0 or 1 of x x{y} Exactly y of x x{y,} y or more of x x{,y} y or less of x Groups: . Any char except \n (x|y) Strings x or y (may be multichar), indexed from 1 from the start of clue (xyz) Multichar string literal, indexed from 1 from the start of clue [xyz] Any of characters x, y or z [^xyz] Not the characters x, y or z [^x|y] Not x or y (may be multichar) [B-N] Letters between B and N inclusive (any letters, caps or not) [3-6] Numbers between 3 and 6 inclusive (any digits) [B-NR-Z] Multiple ranges (could be digit ranges as well) Escape sequences: \7 Get the result of the bracketed instruction indexed 7 (any num) \r Literal r where r is a character used in an instruction above \\ Literal backslash \W a-z, A-Z, 0-9, _ (underscore) \w Not a character in \W \d A digit \D Not a digit \s Space \S Not a space  ## Test Cases Input can be any format, examples use: Width Length Top down clues from left to right Bottom down clues from left to right (if they don't exist, newline) Left across clues from top to bottom Right across clues from top to bottom (if they don't exist, newline) Output must be the completed grid. Sample input (from here): Input 1: 2 2 [^SPEAK]+ (EP|IP|EF) (HE|LL|O)+ [PLEASE]+ Output 1: HE LP Input 2: 2 2 [COBRA]+ (AB|O|OR)+ (.)+\1 [^ABRC]+ Output 2: OO OO Input 3: 2 2 .?.+ .+ [*]+ /+ Output 3: ** // Input 4: 3 4 (.)\1(.)\2 [C\sOU]+ [^PU\sH]+ [PIF]+ .*[OWE]* (TN|LF|TF)+ .[LUH]+ (P|K)[^U]+ .*C+[TIF] (NO|ONE|ION)* .*(L)+ [PUF\s]* [TIC]* [NOI\sE]+ Output 4: PUL P F ICT ION Input 5: 3 7 [^ro\se]*(whe|who) [are](.)[saint]+\1(v) .{2}[st\sel]+ [^vys]+ .(\ssai).* (le|\st|s|or)+ (rr|fro)* [^saint]+ [\sush]* [a\si]+ [with]* [hel\s]+ .* [fr\so]+ (m\s|sm)[rose] (s|us)+ [^aw](a).* [^hear]+ .*[fil] (ve|o|vo)+ Output 5: fro m r uss ia wit h l ove  This is , so the shortest answer in bytes wins! Standard loopholes apply, and no built-ins for regex testing or matching. Your program must terminate in a reasonable amount of time. You may assume that each input has exactly one solution. • 1. "No built-ins" means "You may not answer this question". Every program uses built-ins except zero-byte ones in the languages which support them. "No built-ins for regex testing or matching" would, on the other hand, not be unreasonable. 2. There's currently no constraint requiring the answers to complete the test cases before the heat death of the universe. Is this intentional? – Peter Taylor Nov 8 '16 at 21:05 • @PeterTaylor Thanks for that, I've added your suggestions in. I'm new to code golf. – boboquack Nov 8 '16 at 21:38 # Balancing Act Edit: Challenge Live here A see-saw (supposedly from the French 'ci-ça', meaning 'this-that') forms a third of the holy trinity of playground equipment, along with the similarly ubiquitous slide and swing. A see-saw is in perfect balance if, and only if, the sum of the moments on each side are equivalent. A see-saw can therefore be balanced by adding a specific quantity of weight to the side with the lower moment sum; achieving this is your goal for this challenge. # Challenge Your challenge is to take a depiction of a see-saw as input and output it again, with weight added to one end of the see-saw to balance it. Input Your program must take, in any reasonable format, an ASCII see-saw such as the following: 100 100 ------------------- ^  The first line contains two numbers, each representing weights on the see-saw. Exactly one weight is present on each side, each acting on the very end of its side of the plank. Weights are guaranteed to be integers, and always align with their corresponding end of the plank. These numbers will never overlap the fulcrum (^). The second line represents the 'plank' of the see-saw. Each dash (-) represents an equal length to each other dash, with the sole exception of the dash directly over the fulcrum (^), which has no length. The third line represents the fulcrum of the see-saw. This fulcrum is marked by the only character that is not a space on this line, a circumflex ('^'). The fulcrum can be positioned anywhere along the length of the plank in a valid input so long as enough space is left so that the numbers representing weights do not overlap the fulcrum in either the input or the output. The input is guaranteed to have three lines, and have no white-space prior to or after the characters that constitute the see-saw (excepting, of course, the third line, which requires it). Output For output, the same see-saw depiction should be printed to stdout, but with one (and only one) of the weights replaced with a larger weight, so as to balance the see-saw. Inputs are guaranteed to make this possible using integers alone. Therefore, weights must be shown without decimal points or any other similar notations. If your language does not use stdout you should go by community / meta consensus on output. Trailing newlines are fine but any other changes to the depiction format are probably not OK. # Exemplification Test Inputs and Corresponding Outputs Input 1 12 22 -------------------- ^  Output 1 12 26 -------------------- ^  Input 2 42 42 ----------- ^  Output 2 42 42 ----------- ^  Input 3 3 16 ---------------- ^  Output 3 14 16 ---------------- ^  Input 4 1 56 ------------------- ^  Output 4 196 56 ------------------- ^  Reference Implementation - Python 3 # Takes a list of strings as input def balance_seesaw(lines): weights = [int(w.strip()) for w in lines[0].split()] length = len(lines[1]) pivot = lines[2].find("^") left_length = pivot right_length = length - 1 - pivot left_torque = weights[0] * left_length right_torque = weights[1] * right_length if left_torque > right_torque: weights[1] = left_torque // right_length elif right_torque > left_torque: weights[0] = right_torque // left_length weights = [str(w) for w in weights] string_gap = " " * (length - sum(len(w) for w in weights)) lines[0] = weights[0] + string_gap + weights[1] print("\n".join(lines)) balance_seesaw(["1 56", "-------------------", " ^ "])  # Rules • This is , so the shortest code wins counted in bytes. Check meta if counting bytes is awkward in your language. • Standard rules/loopholes apply. • Input must be taken in a reasonable format. A non-exhaustive list of appropriate formats are given as follows: • A single string with lines separated by newline characters • A list of strings, each string represented a line • A 2D Array or Matrix of characters ## Sandbox Notes Please comment on any parts of the spec, especially input / output requirements, that you find confusing or ambiguous. I haven't written a challenge before so I'm open to the fact that there's quite a bit I've missed. Any and all feedback welcome. Some users in the comments have rightly pointed out similarities between this challenge and others; please weigh in as to if you think this is a dupe or a unique challenge in its own right. Thanks! • Welcome to PPCG! A pretty decent first challenge. It's pretty similar to this one, but yours is, in my opinion, different enough to not be a duplicate. It's also pretty close to this one posted in the Sandbox a few posts down. I think that all three are different enough to not be dupes, but I'll hold off on final judgment to hear what others say. – AdmBorkBork Nov 10 '16 at 20:57 • @TimmyD thanks for the welcome! Looks like I need to up my searching game! I understand if this is deemed a duplicate but it seems to differ in a fair few ways from the others at least. – FourOhFour Nov 10 '16 at 21:01 • Welcome! For me, a nice challenge and well explained with clear examples. I'll also hold back on the dupe side but agree with TimmyD that it may be different enough. Well done for using the Sandbox anyway. It' a shame that more contributors don't. I'm going to +1 just for that. – ElPedro Nov 10 '16 at 21:10 • @ElPedro thanks, appreciate the feedback and the vote. – FourOhFour Nov 10 '16 at 21:13 • Having read (again) through the examples mentioned by @TimmyD I would not say this is a dupe. Possibly mention that it is related though. – ElPedro Nov 10 '16 at 21:34 # Find the optimal sorting network Sorting networks are an abstract model of "wires" carrying numbers, which outputs them sorted. A comparator in a sorting network works as follows: This is the optimal sorting network for 4 numbers: Since there are two kinds of "optimal" sorting networks people care about, we are going for the least number of comparators (those vertical lines). Given a non-negative integer n (so yes, 0 and 1 need to be supported), output a list of comparators which designates an optimal sorting network for n inputs. The "comparators" are a pair of indices which say which indices in the working array to compare / swap. The indices must be 0-based. So for the example sorting network, this would be a valid output (viewing 0 as the top wire): (0, 2), (1, 3), (0, 1), (2, 3), (1, 2)  As would this: (0, 2), (1, 3), (2, 3), (0, 1), (1, 2)  Additionally, any whitespace is ignored (except for tokenizing), and any non-digit is considered whitespace, so this is also a valid output: 0 2 1 3 2 3 0 1 1 2  And also: (0, 2) (1 3) ((2, 3, 0), 1) (1, 2)  Furthermore, functions may simply return some iterable that - when flattened - gives the list of numbers in the correct order. • I have an algorithm to do this; it's O((n^2)! n! n), so very very slow. It might compute size 3, but not size 4. – Justin Nov 19 '16 at 7:04 • I think it's worth giving an example of a sorting network in action on some input. – xnor Nov 19 '16 at 7:12 • What are the bounds on n? Obviously it doesn't make sense to have n < 0, but do answers need to handle n=0 and n=1? – Peter Taylor Nov 19 '16 at 13:00 • @Justin are you still planning to release this challenge? I'm asking because I wanted to make a very similar challenge that would probably be considered a dupe. – flawr Jul 18 '19 at 6:53 • @flawr No, go for it – Justin Jul 18 '19 at 12:16 # ROT-13? More like ROT-Rand! This challenge is to take the following list of characters (ASCII 32 to 126):  !"#%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}~


Randomly shuffle it:

wypP+]=3&IJ6*xAh{zi_l4Y#k~S F?-oReU;(0m,Z5'trs!aLCQ/g}OjM<u[qE2)BTVb$>19%c:HW@8."nD\Nf7dXKv^|G  Take in an input string: ROT-Rand!  Then replace the characters in the string, with their new shuffled equivalents: C!/*CB@by  Using this methodology on large ASCII-based/dictionary based texts would result in something that is decipherable using much trial and error and would be a decent way to encode a long message.  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}~
wypP+]=3&IJ6*xAh{zi_l4Y#k~S F?-oReU;(0m,Z5'trs!aLCQ/g}OjM<u[qE2)BTVb\$>19%c:HW@8."nD\Nf7dXKv^|G
^           ^                                    ^              ^  ^         ^^    ^
!           -                                    R              a  d         no    t


# Rules

1. Your only input is the text to be "encrypted".
2. Your output is the encrypted string.
3. The ASCII list must be randomly shuffled, built-ins are allowed.
4. , shortest in bytes wins.
• 1. I'm guessing from context that "their new shuffled equivalents" means that we're generating a random substitution cipher, but I don't see any actual definition of the equivalence. 2. If I'm correct, this is pretty boring, but could be made more interesting with the (justifiable) modification that the substitution should be a random derangement rather than just a random permutation. That will probably force most languages to do more than just apply two built-ins. – Peter Taylor Nov 26 '16 at 22:44
• @PeterTaylor derangement? – Magic Octopus Urn Nov 27 '16 at 15:50
• en.wikipedia.org/wiki/Derangement – Peter Taylor Nov 27 '16 at 16:05

# Rules

1. Animation should contain at least two frames.

2. Delay between frames is up to you, but rotation of airscrews should be visible.

3. Helicopter could be very simple (simpler than standard roflcopter showed below) but it should leave no doubt what is it. All ASCII chars are allowed.

4. No caption below needed.

5. Printing animation to file would be hard, although all standard output destinations are allowed.

6. This is , so etc.

I believe I can fly.

• You should probably place the ASCII of each frame of the Roflcopter in the challenge. Also, is the ROFL COPTER!!! at the end necessary? – clismique Nov 24 '16 at 8:43
• +1 For caption necessity or not, I updated question. In my opinion providing frames will make challenge too easy. – paldir Nov 24 '16 at 8:48
• So will the design of the Roflcopter be the same for all submissions, with the same plane body, rotors and stuff? – clismique Nov 24 '16 at 9:09
• It's up to users, how exactly it will look, but it should be helicopter-like. Ok, I think you're right, this task is too ambiguous. I will try with another question. – paldir Nov 24 '16 at 9:12
• You can just standardise the copter itself, and it shouldn't be ambiguous... – clismique Nov 24 '16 at 9:18

# Hexasweep: A two-part challenge

## Part 1: The solver code-golf

A Hexasweep puzzle is set out on a grid of diamonds arranged in hexagonal shapes, of which the board looks like a hexagon, like so:

         _____
/\    \
_____/ X\____\_____
/\    \  / XX /\    \
/X \____\/____/X \____\
\ X/ XX /\    \ X/    /
\/____/  \____\/____/
/\    \  / X  /\    \
/  \____\/____/  \____\
\  / XX /\    \  / XX /
\/____/  \____\/____/
\ X/    /
\/____/


The above image is composed of 7 hexagons (21 diamonds), and is thus a Hexasweep puzzle of size 2. If you want to expand it, cover the current Hexasweep puzzle with more hexagons (so that there are 19 hexagons - that will make a Hexasweep puzzle of size 3).

Each diamond can contain 0, 1 or 2 "bombs", with bombs depicted as X above.

The above image would be read from top to bottom, starting from the left:

2,0,0,2,0,2,1,0,1,0,2,0,1,0,0,2,0,0,0,0,2


That is now the "condensed form" of the puzzle.

Numbers are marked on "intersection points", to show how many bombs are on the diamonds which are touching those intersection points - the intersection points of this grid are shown below using O.

         _____
/\    \
_____/  OO___\_____
/\    \  OO   /\    \
/  OO___OO___OO  OO___\
\  OO   OO   OO  OO   /
\/___OO  OO___OO____/
/\   OO  OO   OO    \
/  OO___OO___OO  OO___\
\  OO   OO   OO  OO   /
\/____/  OO___\/____/
\  OO   /
\/____/


As you can see, there are two "types" of intersection points - those with 3 diamonds touching it, and those with 6 (the one that are touching the edge of the board aren't counted):

  _____
/\  XX\
/X OO___\
\ XOO   /
\/____/

/\
_____/X \_____
\ XX \ X/    /
\____OO____/
/ XX OO  X \
/____/  \____\
\ X/
\/


The two intersections would be marked with 4 and 8 respectively.

In the original Hexasweep puzzle above, the intersection numbers would be:

   3
4 5 4 2
2 1 3
2 4 1 2
1


Which would be condensed to:

3,4,5,4,2,2,1,3,2,4,1,2,1


Given an input in this "condensed form", you must output the original puzzle, in "condensed form" (see above).

### Specs:

• Any delimiter for the "condensed form" as input are allowed (it doesn't have to be , separating the numbers).
• You may output a list, or a string with any delimiter.
• Your program must be generalised: it must be able to solve Hexasweep puzzles of any size (at least up to size 4).
• If there is more than 1 possible answer, your program must output the single character N.

This is , so shortest code in bytes wins!

If there is a tie, the earlier post is declared the winner.

## Part 2: The maker meta-golf

Your task is to generate the smallest Hexasweep puzzle with a single solution that encodes a binary number.

Because any diamond in a Hexasweep puzzle can have either 1 or 2 bombs (if the diamond has bombs), you can encode binary numbers into it. In this puzzle (condensed form):

2,0,0,2,0,2,1,0,1,0,2,0,1,0,0,2,0,0,0,0,2


The only digits that matter are the non-zero digits, so this turns into:

2,2,2,1,1,2,1,2,2


Decrement each number by 1:

111001011


Which is equal to 459.

Your task is to make a program that generates that Hexasweep puzzle in the smallest grid with a single solution.

### Specs:

• You must output the condensed form of the Hexasweep puzzle.
• You can output either an array of numbers, or a string with any delimiter.
• You will be tested on all positive integers from 10,000 to 15,000, and your program is expected to return a value for any integer in 10 minutes.

Your final score is the total size grid for every test integer added together (so if you get a size 3 grid for every number, your final score would be 15,000). The lowest score is declared the winner.

If there is a tie, the earlier post is declared the winner.

## Meta:

• Should this be one challenge or two? If it's one challenge, should the score just be added up for both programs?
• Any improvements in explanation?
• Is this a dupe?
• Can I post this abandoned proposal? – programmer5000 Jun 9 '17 at 12:24

Please do my Martian homework posted

This was originally conceived of as two related challenges; Please do my Martian homework and Please grade my Martian homework.

Though the task itself is different, the basic description of the task (that is, what is a Martian essay) is the same (though I may edit it later anyway), but just to avoid confusion:

• Please do my Martian homework was posted

## History

Around the turn of the 20th century, spiritualist Catherine-Elise Müller allegedly communicated with Martians. During somnambulatory trances, she would write out Martian scripts. Psychologist Théodore Flourney discovered her Martian writings were very similar to her native French, and in his book "From India to the Planet Mars", he documented Catherine's Martian alphabet. The following is loosely based on that alphabet with an extended mythos.

## Problem Description

The Martian language has 21 characters, shown here next to each Latin equivalent:

Unfortunately, there's no Unicode for Martian (despite Mars being part of the universe), so we're stuck using Latin characters.

Whereas in English our phonemes break out into two major types (consonants/vowels) which we loosely map to letters, Martian has three letter types:

• The vowels: a e i m n o u
• The hard consonants: b c d g k p t
• The soft consonants: f h l r s v z

In addition to this, the Martian language contains a single punctuation mark--the period.

A Martian word is a set of 3 to 9 letters. All Martian words have at least one vowel, one hard consonant, and one soft consonant (in any arrangement). For example, fng, cdaz, vpi, and pascal are Martian words.

A Martian sentence is a set of 3 to 9 Martian words delimited by spaces and followed by a period.

A Martian paragraph is a set of 3 to 9 Martian sentences, delimited by spaces, and followed by a newline.

A Martian essay is a collection of Martian paragraphs that contains no contiguous word repetitions.

A contiguous word repetition is any construct S S where S is a contiguous set of words. Note that this definition ignores sentence and paragraph boundaries.

## Challenge

The Martian homework assignment is to write an essay between 729 and 810 words. The essay is graded on a pass/fail basis; pass simply means it's a valid Martian essay according to the above definitions, and fail means not pass.

Your challenge is to write a function or program that accepts data as input, and returns a truthy value if that data is a valid Martian essay between 729 and 810 words, or a falsey value if it is not. (Don't forget that you must fail the input if there is a contiguous repetition).

This is code golf. Shortest code in bytes wins. Standard loopholes disallowed.

## TBD

Post link to examples in first challenge? Repeat examples? Should second challenge still have word counting?

• Whoops; most of the post is almost identical so I thought it was the same, but the task is indeed different. I've deleted my original comment. – user62131 Dec 5 '16 at 0:22