# What is the Sandbox?

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

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

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

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

# Bucket and Minimize

Post here

• @FryAmTheEggman thanks for the info. updated – scrawl Jan 21 at 9:40
• "floor(12%5)+1 into 12 mod 5 buckets, and floor(12%5) in the rest". Shouldn't those floor(12%5) be floor(12/5) based on your $\left\lfloor\frac{|L|}{N}\right\rfloor+1$ formula? – Kevin Cruijssen Jan 22 at 10:40
• @KevinCruijssen er, yes. keeping things conventional. in my preferred language (k4) % is float division. i'll update it to avoid confusion. thanks! – scrawl Jan 22 at 12:27
• Ah ok. In most languages I know % is modulo and / is division. :) I thought maybe % was integer-division in your language of choice, making the floor obsolete. But your edit is indeed clearer. – Kevin Cruijssen Jan 22 at 12:47
• I would recommend cleaning the body of this answer and linking to the actual challenge: codegolf.stackexchange.com/q/198406/75323 – RGS Feb 2 at 21:07
• @RGS cleaned up – scrawl Feb 2 at 23:55

Posted to main; thanks for input provided!

• this looks perfect for fastest-code. with fastest-algorithm it's difficult to do complexity analysis on the solutions. – ngn Jan 4 at 23:53
• @ngn thanks, I’ve amended the alternative suggestion – Nick Kennedy Jan 5 at 0:23
• it may be good to mention explicitly that all blocks must form a single connected component, otherwise 2 separate 1x1x2 pieces would technically satisfy rules 1-4 – ngn Jan 5 at 1:47
• Is this basically $a_n = \sum_{i=1}^n polyminoNumber(i)\cdot i^{n-i}$? – my pronoun is monicareinstate Feb 3 at 14:56
• @mypronounismonicareinstate no it's not, though it is related to the polyomino numbers. I've posted to main (sorry for not updating Sandbox post), so please see there for two implementations of code. – Nick Kennedy Feb 3 at 17:35

# Parse Iota

Iota is a simple programming language, considered the "sister" of the language Jot. More info can be found here Every Iota program consists of either an i, or a * followed by two Iota programs. In BNF, this is:

iota ::= i | *<iota><iota>


# Challenge

Your task is to, given any input, output a truthy or falsy value based on whether or not it is a valid Iota program.

• Your program may take input in any form agreed upon by the community here. It just has to be able to take input from the user in some form.
• The same rule goes for output. See the post above for valid output methods. Output may be any truthy or falsy value in your language, including integers, strings, arrays, or objects. If it can be converted to a Boolean, it is OK.

# Example I/O

Input: i
Output: 1

Input: hello
Output: 0

Input: *i*i*ii
Output: 1

Input: i*i
Output: 0

Input: ***
Output: 0

Input: *
Output: 0

Input: iiiiiiiii
Output: 0;

Input: i
Output: 1

Input: *ii
Output: 1

• Suggested test cases: *, ***, iiiiiiiiiii – 79037662 Feb 12 at 23:27
• Ok, I added those @79037662 – sugarfi Feb 13 at 0:37
• I don't get how i*i*i*ii is produced. If I understand the grammar right, this is equivalent to checking if parens are matched after removing the final i that must come at the end, using *i as (). – xnor Feb 13 at 7:12
• @xnor - sorry, my bad. i fixed that. – sugarfi Feb 13 at 12:02
• I think that despite the different presentation, this would be similar enough to checking paren matching to be a duplicate. – xnor Feb 14 at 11:22

# The uniquely solvable sudoku code-golfdecision-problem

Given a standard 9x9 sudoku board, output a Truthy value if that sudoku admits one and only one solution. Output a Falsy value if the sudoku has a number of solutions other than one. This means 0 solutions and two or more solutions.

# The input

The board can be given in any sensible format. Some come to mind, and I'll exemplify for a 4x4 sudoku.

• a 2D array with the state of the board, with any placeholder value for non-filled cells (including the digit 0, or no value at all if your language supports it): [[1,2,#,4],[#,4,1,2],[2,1,4,#],[4,#,2,1]]
• a string of the digits row by row or column by column, so "12#4#412214#4#21" or "1#24241##14242#1"

# The output

A Truthy value if the sudoku puzzle has a unique solution, Falsy otherwise.

# Test cases

### Falsy

• Hmm, I'm surprised this isn't a duplicate with the amount of Sudoku-related challenges we have. Closest related challenge I could find is perhaps this one. – Kevin Cruijssen Feb 18 at 16:21
• @KevinCruijssen Thanks for your search! I can link this one, but this is still a new challenge, right? :) – RGS Feb 18 at 17:44

## Square Deltas code-golfsequence

Given an strictly positive integer n, output all numbers in the sequence up to the index n. For the current test cases of the current challenge numbers are one-indexed. However, other formats are allowed as default.

## Base sequence

We start from this sequence:

1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, ...


The sequence is described as follows: 1, 2 (xN), 1 repeated arbitary times. There are 2 more 2's than the previous 2-set, and the 2-sequence starts at 1. i.e.:

1,       2,       1,
1,    2, 2, 2,    1,
1, 2, 2, 2, 2, 2, 1,
and so on ...


However, our point is not to output this sequence. For every item in this sequence, add the item by that item of that sequence.

Here's an example of adding the sequence. Here, our sequence starts with 0:

  The sequence
|
v
0 + 1 = 1
1 + 2 = 3
3 + 1 = 4
4 + 1 = 5
...

Our generated sequence is therefore

0, 1, 3, 4, ...



## Example test cases

Here is a sample program outputting the sequence up to the input.

3 -> [0, 1, 3]
10 -> [0, 1, 3, 4, 5, 7, 9, 11, 12, 13]


## Sandbox

• Can the challenge be clarified?
• Why is the task asking for infinite output after index n, rather than a standard sequence challenge? A "standard sequence challenge" usually allows several I/O formats in a single challenge, including "input n -> the number at index n", "input n -> first n numbers", "no input -> infinite output of the sequence". – Bubbler Mar 6 at 4:49
• No, you don't need to make it harder. And even if it is too easy, please don't try to fake up the difficulty by enforcing unnatural I/O requirements. – Bubbler Mar 6 at 4:56
• Are you sure that you want to override the default sequence IO? Do you actually have a good reason for doing so? – Jo King Mar 12 at 4:36

## Pendulum Encoding code-golfarray-manipulationsorting

Given an array as an input (which can be any acceptable/convenient format in your language), implement pendulum encoding.

## How do I do that?

The current iteration index starts at 0.

• If the iteration index is even, append the current item onto the output list.
• If the iteration index is odd, prepend the current item onto the output list.

## An example

The input is [a b c d e f g].
Note that the letters a-g are atoms, to prevent confusion from the iteration index.
N: the iteration index

N:0 Out:      [a]
N:1 Out:    [b a]
N:2 Out:    [b a c]
N:3 Out:  [d b a c]
N:4 Out:  [d b a c e]
N:5 Out:[f d b a c e]
N:6 Out:[f d b a c e g]


The output should be [f d b a c e g].

# Another example

The input is [u d l n u e m p].

N:0 Out:        [u]
N:1 Out:      [d u]
N:2 Out:      [d u l]
N:3 Out:    [n d u l]
N:4 Out:    [n d u l u]
N:5 Out:  [e n d u l u]
N:6 Out:  [e n d u l u m]
N:7 Out:[p e n d u l u m]


## Test cases

Here's a sample program doing this encoding.

Take note that the atoms in the list aren't always unique.

[a,b,c,d,e,f,g]   -> [f,d,b,a,c,e,g]
[]                -> []
[a]               -> [a]
[a,b,c,d]         -> [d,b,a,c]
[a,b]             -> [b,a]
[a,b,d]           -> [b,a,d]
[a,b,a,c,b,c]     -> [c,c,b,a,a,b]
[a,a,b,b,c,c]     -> [c,b,a,a,b,c]
[u,d,l,n,u,e,m,p] -> [p,e,n,d,u,l,u,m]

• I can't see any issues with this challenge apart from the usual "make sure that you specify that output and input can be taken in any reasonable and convenient format". – Lyxal Mar 18 at 0:00
• The "example" in the first paragraph is confusing. It seems to be example input, but it deson't have clear context. If feels very out of place. – Ad Hoc Garf Hunter Mar 20 at 15:16
• Are the "atoms" unique? If not, you should at least include a test case where they aren't. – FryAmTheEggman Mar 20 at 20:20
• Naming a generic array a, then redefining a as a generic atom and never referring to the original array is not very helpful in an explanation. – Jonathan Frech Mar 21 at 0:09

## Join by intersection code-golfstring

Given a list of strings, output these strings joined by their largest intersecting parts. Your output has to be optimal. Strings have to be joined in the order given.

## What is an intersection anyway?

Suppose you have two strings:

"abcbc" "bcbcd"


You extract all suffixes of the first string, as well as all prefixes of the second string:

["abcbc", "bcbc", "cbc", "bc", "c"]
["bcbcd", "bcbc", "bcb", "bc", "b"]


We trunctuate both of these lists to the length of the list of the smaller length (it's an identity in this current case).

Then, we find all items at the same index which are equal to the other item at the same index:

["bcbc", "bc"]
["bcbc", "bc"]


We return the longest string of the output. Therefore, the intersection is:

"bcbc"


## How to join two strings by the intersection

To join by the intersection you simply

1. Append the first string without the intersection to the output string
2. Append the intersection to the output string
3. Append the second string without the intersection to the output string

For example, in our example case:

"abcbc" "bcbcd"
(The intersection is "bcbc")

Step 1. Out:"a"
Step 2. Out:"abcbc"
Step 3. Out:"abcbcd"


## Reducing a join over a list

If you want to reduce a join over a list

["abc","bcd","rfh","hal"]


You connect them by their longest common substring:

abc
bcd
rfh
hal
=========
abcdrfhal


Therefore the expected output is abcdrfhal.

## Further walkdown

You cannot join two strings if their substring can be found in the middle. For example:

["aXc","bXd"]


If you try to match them by the middle substring:

aXc
bXd


You would realize that the other overlapping characters are not equal to each other. That is, a is not equal to b, and c is not equal to d. In that case you simply append the string in the join:

aXc
bXd
======
aXcbXd


Likewise, if either of these strings contain each other, but isn't equal to the other string, you should simply append the string. E.g.

["abcd","bc"]


would give

abcd
bc
======
abcdbc


Substrings can overlap past each other. E.g.

["abc","bcd","cde"]


would result in the following join:

abc
bcd
cde
=====
abcde


which would evidently make the output abcde.

Strings have to overlap as much as possible. That means, in this example:

["abcbc","bcbcd"]


This is not okay (even if they do overlap):

abcbc
bcbcd
========
abcbcbcd


abcbc
bcbcd
======
abcbcd


The join is consecutive based on the consecutive inputs. For example:

abcde
cde
abcde
==========
abcdeabcde


## Test cases

A program is worth a thousand words. Here 's a reference implementation that I use to check the test cases.

["abc","bcd","rfh","hal"] -> "abcdrfhal"
["mmm","qqq","rrr"] -> "mmmqqqrrr"
["abcbc","bcbcd"] -> "abcbcd"
["aXc","bXd"]    -> "aXcbXd"
["abc","bcd","cde"] -> "abcde"
["abcd","bc"] -> "abcdbc"
["abcde", "cde", "abcde"] -> "abcdeabcde"

• How would you join aXc and bXd? They have the common substring X in the middle. – Bubbler Mar 25 at 2:24
• Can strings overlap past each other like abc,bcd,cde->abcde? – xnor Mar 25 at 2:25
• Do strings have to overlap as much as possible, or just overlap any amount? For example, for abcbc and bcbcd, is either of abcbcd or abcbcbcd OK? – xnor Mar 25 at 4:43
• Do strings have to be joined in the order given? I feel like the answer is surely "yes", but the text doesn't say outright. Really, I think all these Sandbox questions come from the fact that the task is never actually stated precisely, and doing that would probably head off any further question. – xnor Mar 25 at 4:49
• Along these lines, what happens if one string contains another? Do we do abcd,bc->abcd? – xnor Mar 25 at 4:51
• Suggested test case: abcde, cde, abcde. – Jonathan Frech Mar 25 at 4:52
• @JonathanFrech Well, what's the expected output? I thought it was abcde in this case. – user92069 Mar 25 at 6:00
• I was not completely sure what the output would be. abcdeabcde does seem reasonable. – Jonathan Frech Mar 25 at 7:40
• I still don't actually understand how the task works precisely. A reference implementation isn't a replacement for a specification. – xnor Mar 25 at 23:09
• @xnor I've added back the spec, can you understand it now? – user92069 Mar 26 at 6:24
• Not really, sorry. I still wouldn't know what abcd,bc would give. – xnor Mar 26 at 6:29
• @xnor Are there any more test cases you don't understand? – user92069 Mar 26 at 6:35
• This seems to be related to the shortest superstring problem for two strings, but you don't have to handle the case where one of the strings is a substring of another, and the joining order is fixed. Is that correct? Just informing that the specification spans four pages on my laptop, with default browser font size. – my pronoun is monicareinstate Mar 26 at 6:55
• – my pronoun is monicareinstate Mar 26 at 6:58
• @mypronounismonicareinstate Ah, it's a duplicate. Thank you for the mention. – user92069 Mar 26 at 6:58

## Sum in 2540 Sums code-golfpristine-programmingcode-shuffleboard

This is my attempt to pair with .

You need to write a program that sums all codepoints of the input string.

## Rules

• The input will always be in printable ASCII.
• The sum of the codepoints of your source must be exactly 2540.

• You are allowed to use your language's own code page to calculate your program's codepoints.
• Null bytes (which don't contribute to your codepoint sum) are banned.

• The program must not work with any consecutive substring removed.
• This is . Your score is the length of your source code, the shorter being better.
• You defined the "base score" only to reference that term exactly once. It seems to be move confusing than helpful. Wouldn't "The sum of the codepoints of your source must be exactly 2540" be clearer and shorter? – Ad Hoc Garf Hunter Apr 9 at 21:18
• Although I am neither suggesting nor recommending against, this could also work as code-bowling if you either outlaw null bytes or sum up the (codepoints+1). – Ad Hoc Garf Hunter Apr 9 at 21:22
• @AdHocGarfHunter The rules are a lot simpler if it were code-golf, and we haven't paired codepoint sum with code golf before. Also I need to fullfill a goal to pair code-bowling with code-golf. This analysis says that there are 11 tags not paired with code-golf, I'm going to make it 10. – user92069 Apr 9 at 21:24
• As far as I know, [pristine-programming] is the tag for programming with the substring removal restriction here. (I think this would work as a [code-bowling] as well as well) – my pronoun is monicareinstate Apr 10 at 0:12
• @mypronounismonicareinstate So which side are you for? Code golf or code bowling? – user92069 Apr 10 at 0:53
• Probably code-golf. – my pronoun is monicareinstate Apr 10 at 1:07

# Will this simplified befunge-93 program terminate? code-golfdecision-problem

The challenge today is to solve the halting problem for simplified befunge-93.

Simplified befunge-93 has exactly four instructions - > v < ^ @. The program is restricted to a 80x24 grid. Each of the commands modifies the instruction pointer (so that, for instance > makes the instruction pointer start executing commands to the right), except of the @ instruction, which terminates the program.

When the instruction pointer reaches the end, it wraps around (imagine the snake game).

You may read input in form of a string or a two-dimensional array using any reasonable device. The output may be either a truthy value if the program terminates, or a falsy value if the program doesn't terminate.

## Example data

Input:
>v
^<

Output: Doesn't terminate.
----------------------------------------
Input:
> v
@
^ <

Output: Doesn't terminate.
----------------------------------------
Input:
v@
[23 newlines]
>v

Output: Terminates.
----------------------------------------
Input:
v @
[23 newlines]
>v

Output: Doesn't terminate.
----------------------------------------
Input:

Output: Doesn't terminate.

• Possibly dupe? – HighlyRadioactive Apr 27 at 8:47
• is the instruction ptr initially at 0 0 and moving to the right? – ngn Apr 27 at 8:55
• yes, I maybe forgot to state that. But it's most probably a dupe right now, so I don't think I should push it forward anymore :P – Szewczyk Apr 27 at 8:56
• For the sake of completion: can I give my output as a list of strings? – Lyxal Apr 29 at 23:02
• @Lyxal Seeing as that's a generally accepted I/O method, yes. – sporeball Apr 30 at 0:09

# Complete a sequence using its distances code-golfsequenceinteger

Given $$\A = (a_1,\dots,a_k)\ k\ge2 \$$ a nonrepetitive sequence of positive integers.
Starting from $$\i=2\$$, while $$\a_i\in A:\$$

• If $$\d=|a_i-a_{i-1}|\$$ is not already in $$\A\$$, append $$\d\$$ to $$\A\$$
• Increase $$\i\$$

Output the completed sequence.

## Example

In:  16 20 13 3

16 20 13 3 4
--^
16 20 13 3 4 7
--^
16 20 13 3 4 7 10
--^
16 20 13 3 4 7 10 1
--^
16 20 13 3 4 7 10 1
--^
16 20 13 3 4 7 10 1
--^
16 20 13 3 4 7 10 1 9
--^
16 20 13 3 4 7 10 1 9 8
--^
Out: 16 20 13 3 4 7 10 1 9 8


This is

• You could define the self-distances completion for a sequence of positive integers instead of a k-permutation. I believe it would be clearer that way. Also, is the input guaranteed to be duplicate-free? – Zgarb Jun 1 at 20:15
• @Zgarb Yes, you're right, for the purpose of this challenge refer to a sequence would be totally ok, I've copied this def from the linked challenge where since it's fundamental to consider the max in the input sequence, this number in the context of k-permutation of n - containing n - will naturally be n... But that's not a problem, a k permutation is also a sequence of positive integer. And yes, I forgot to require the input to be duplicate-free – Domenico Modica Jun 1 at 20:44
• @Zgarb what do you think about the name? Does it make sense? It's a bit too bulky? – Domenico Modica Jun 1 at 20:53
• "append d to (the end of) A" could be clearer to programmers than "prolong A with d". Using "the end of" is optional. – Hiatsu Jun 2 at 3:05
• The name could be "Complete a sequence using its distances" if you want to go for maximum clarity. – Zgarb Jun 2 at 8:08

## _

• @mathjunkie then the codepoints given are incorrect. – Lyxal May 24 at 22:43
• @Lyxal Why are they incorrect? I wrote a program to generate the codepoints. – user92069 May 25 at 8:15
• Oh wait. I thought they were in binary. – Lyxal May 25 at 8:18
• As in, you were using the binary representation of each ordinal value. – Lyxal May 25 at 8:19
• @Lyxal No. I was using the decimal expansion of the ord codes. I am going to clarify that. – user92069 May 25 at 8:19
• I cam see that now. I just assumed those numbers were base 2,rather than base 10 – Lyxal May 25 at 8:20
• Seems pretty clear, but would benefit from test cases with odd-length strings. For example, 'rim' (false) and 'rum' (true) illustrate the 'first half longer' splitting rule. (Truthiness for these two words would be swapped if the rule were second half longer.) – Dingus May 29 at 7:24

# Bot Duels KOTH king-of-the-hilljavascript

Obligatory blurb adding story fluff. Or, maybe a self-referential paragraph about meta-self-referential blurbs? Or: <announcer voice> Will your bot survive... The Arena? </announcer voice>. Yes, I think a good non-self-referential (such as this) short paragraph full of short sentences without run-ons or many, many, many, many commas will suffice.

## Overview

This is a King-of-the-Hill challenge. Bot with the most wins wins. You may submit multiple bots as long as they differ in strategy. Bots will play against every other bot. The bot who is currently playing against every other bot goes first, and goes second when their opponent is playing against every other bot. Bots will face off in an arena with x boundaries of 10 and -10 and y boundaries of 10 and -10. Bots will either start at (-5, 0) or (5, 0). Your goal is to defeat the other bot by reducing it's HP to 0 or less. Bots start with 20+armor modifier HP and do not regenerate health. Your bot defeats the other bots using weapons, which have damage, range, and cooldown. Armor has speed.

## Submissions

Submissions should be a JS function that takes the following parameters:

• curr_x - the current x coordinate of your bot
• curr_y - the current y coordinate of your bot
• enemy_x - the current x coordinate of your opponent's bot
• enemy_y - the current y coordinate of your opponent's bot
• enemy_armor - the armor that your enemy is wearing
• storage - a storage object you can use to store data between function calls

The function should return an array with 3 items (in the following order):

• desired x - the x coordinate you want to move to
• desired y - the y coord you want to move to
• use weapon? - if true, and desired x and desired y are Infinity, then you use your weapon

Submissions should be structured as

function definition
block


Explanation underneath, if any.

## Armor

(currently designing new weapons and armor) The types of armor available are:

• Light - increases HP by 3, has a speed of 3
• Medium - increases HP by 5, has a speed of 2
• Heavy - increases HP by 7, has a speed of 1

## Weapons

The types of weapons are:

• Laser - High-range, high-damage, low ROF. 5 points of damage, 5 rounds to cool down, and a range of 6 units
• Rifle - General-purpose weapon. 5 damage, range of 4, 3 rounds to cool down.
• Sword - High-ROF, high-damage spiky thing. 5 points of damage, really low range of 1, and a rather quick 2 rounds to cool down.

## Turns

On your turn, you can either move or use weapon (or do nothing, if that's what you really want to do).

• If you move, you can move a distance (computed using the Euclidean Distance formula) less-than or equal-to (<=) your armor's speed.
• If you choose to use weapon, and if the enemy is in range of your weapon, then you deal damage equal to your weapon's damage and the weapon goes into cooldown. A weapon in cooldown can't be used. Weapons can be used after a number of turns equal to their cooldown property has passed after being used.
• To do nothing, simply return your current x and y coordinates, like so: return [curr_x, curr_y, false].

## Rules

• If you try to use a weapon during cooldown, nothing happens and your turn ends
• If you try to use a weapon and your opponent is out of range, nothing happens and your turn ends.
• If you try to move more than your armor's speed, nothing happens and your turn ends
• If you try to move out-of-bounds, same thing
• If you move into another bot's space, then the bot with the lowest HP loses and the bot with the highest HP wins, making this a viable strategy.
• All standard loopholes (accessing controller, duplicate bots, suicide bots, etc.) are, of course, disallowed.

## Examples

TowerDefense Weapon: Laser
Armor: Heavy

function(curr_x, curr_y, enemy_x, enemy_y, enemy_armor, storage) {
let actions = [Infinity, Infinity, true];
return actions;
}


Just sits and shoots, lol. A perfectly viable strategy (and a rather strong one, too, while weapons are still being reworked). Takes the highest-hp armor available because it doesn't need to move at all.

## DumbBot

Weapon: Rifle
Armor: Medium

function(curr_x, curr_y, enemy_x, enemy_y, enemy_armor, storage) {
let actions = [curr_x, curr_y, false];
// if storage is empty
if (!storage.data) {
// then write our starting loc
storage.data = curr_x.toString() + " " + curr_y.toString();
}

// if we're starting at x = -5
if (storage.data.includes("-5")) {
if (curr_x < 3) {
// move right
actions[0] += 2;
actions[1] = curr_y;
}
// otherwise we must be close enough
else {storage.data = "shoot";}
}


Assumes enemy doesn't move (such as TowerDefense). Moves to the enemy's starting location, then shoots. As such, takes the Medium armor and the Rifle. Kind of a generic all-purpose bot, like the weapons and armor it uses.

## Controller

The controller can be found here. Run all current submissions here.

Best of luck, and, may the odds be ever in your favor (even though this is a 1v1 and not a FFA)

## Sandbox

• Are the rules explained thoroughly? Is anything unclear?
• Is the game (armor, weapons, punishment for breaking rules, etc.) balanced well? Are there any strategies that dominate?
• Would this KOTH be fun?
• Would you participate in the competition?
• Any obvious bugs in the (horribly messy) controller code?
• Create a simple submission similar to something that you would actually submit and test it against the example bots. Is the code still working?
• An arena that contains the points (-5, 0) and (5, 0) would be larger than 10x10. Isn't the heavy armor creating more health that can be removed in a turn? – my pronoun is monicareinstate Jun 15 at 17:07
• Armor adds health at beginning of game. It’s a one-time buff. And yes, I messed up the field size. It’s 20x20 – nope Jun 15 at 21:32
• If armor is one-time, then the Light armor is strictly better than Medium because both last only for one shot, leading to various weirdness. – my pronoun is monicareinstate Jun 16 at 1:41
• a) How much health does each bot start with? b) Are you sure the arena is supposed to be 20x20? Not 21x21 or 19x19? As it is one of the bots will have to start closer to the edge (and which one it is isn't specified as far as I can tell). c) Is there a reason why some disallowed actions cause an immediate forfeit while others only make the offending bot skip a turn? d) The "Stuff Not Allowed" and "Other viable strategies" are confusing. Namely, under the first one you list a viable strategy, and under the second - something that's disallowed. – Alion Jun 16 at 12:02
• b.2) On further inspection, is this game grid-based or played on a continuous arena? As in, can you move in fractions? In the second case, (b) becomes irrelevant. – Alion Jun 16 at 12:40
• e) What's the mysterious "Distance formula"? Plain old euclidean distance? Taxicab? Chebyshev? f.1) How do you "include [what weapon and armor your bot is using] in your submission"? f.2) More generally, is there a specific submission format? Or will anything human-readable do? g) Are bots allowed to act randomly with the help of Math.random, for example? h) Is it really necessary to override this loophole? – Alion Jun 16 at 13:06
• i) Have you considered adding more weapon types or modifying the current set? Currently the choice is pretty one-dimensional, since you avoid varying the damage property. – Alion Jun 16 at 13:07
• As for whether this KotH is fun or not - it seems okay, but I think it lacks variety. Addressing (i) would probably help with that. I would definitely give this challenge a try regardless if it hit main (perhaps as a result of me being a JS KotH junkie). – Alion Jun 16 at 13:18
• Just an observation: the table is almost antisymmetric reading top-down vs bottom-up. That is, if you split the table in half based on the value of A, then the X value in any row in the top half of the table is mostly the opposite of the X value in the same row (reading upwards from the bottom) in the bottom half. Whether that simplifies the problem at all, I'm not sure. – Dingus Jun 15 at 0:23
• I think the [kolmogorov-complexity] tag should apply here, and the [number] tag doesn't seem very helpful. – my pronoun is monicareinstate Jun 16 at 5:58

# Polyglot: Convert Case

Your task is to write a program that performs case conversion from plain text, and other case formats, into one of the specified formats below. Inputs will be either plain lowercase text, or one of the detailed cases below. You must remove non-alphabetic characters, except   (space), _ and -, split on these, or differences in case (e.g. bA), and either join on the desired chars or join on the empty string and capitalise the first char of each word (or not the first of doing camel case). Your program must be a polyglot in at least two different languages. For example, running your code in Python 2 transforms input to snake_case, running it in JavaScript transforms to kebab-case, Ruby transforms to PascalCase and 05AB1E transforms to camelCase.

The following case conversions must be completed:

### camelCase

this is a test         thisIsATest
camelCaseTest          camelCaseTest
PascalCaseTest         pascalCaseTest
snake_case_test        snakeCaseTest
kebab-case-test        kebabCaseTest
Testing!!one!!!1!!!    testingOne1
aBCDef                 aBCDef
ABCDef                 aBCDef
a_b_c_def              aBCDef
a-b-c-def              aBCDef


Try it online!

### PascalCase

this is a test         ThisIsATest
camelCaseTest          CamelCaseTest
PascalCaseTest         PascalCaseTest
snake_case_test        SnakeCaseTest
kebab-case-test        KebabCaseTest
Testing!!one!!!1!!!    TestingOne1
aBCDef                 ABCDef
ABCDef                 ABCDef
a_b_c_def              ABCDef
a-b-c-def              ABCDef


Try it online!

### snake_case

this is a test         this_is_a_test
camelCaseTest          camel_case_test
PascalCaseTest         pascal_case_test
snake_case_test        snake_case_test
kebab-case-test        kebab_case_test
Testing!!one!!!1!!!    testing_one_1
aBCDef                 a_b_c_def
ABCDef                 a_b_c_def
a_b_c_def              a_b_c_def
a-b-c-def              a_b_c_def


Try it online!

## UPPER_SNAKE_CASE

this is a test        THIS_IS_A_TEST
camelCaseTest         CAMEL_CASE_TEST
PascalCaseTest        PASCAL_CASE_TEST
snake_case_test       SNAKE_CASE_TEST
kebab-case-test       KEBAB_CASE_TEST
Testing!!one!!!1!!!   TESTING_ONE_1
aBCDef                A_B_C_DEF
ABCDef                A_B_C_DEF
a_b_c_def             A_B_C_DEF
a-b-c-def             A_B_C_DEF


Try it online!

### kebab-case

this is a test         this-is-a-test
camelCaseTest          camel-case-test
PascalCaseTest         pascal-case-test
snake_case_test        snake-case-test
kebab-case-test        kebab-case-test
Testing!!one!!!1!!!    testing-one-1
aBCDef                 a-b-c-def
ABCDef                 a-b-c-def
a_b_c_def              a-b-c-def
a-b-c-def              a-b-c-def


Try it online!

## Rules

• Your code should produce the same output as the linked examples.
• Entries with the most conversions win, with code length being a tie-breaker.

# Questions for sandbox

• Have I missed any other major naming schemes?
• in the example, at the start, you said python 2 and javascript, while below there are 4 conversions. Must you do all of them in a different language each? Also, do language versions (python 2 / python 3) count as different languages? – Command Master Jul 3 at 3:27
• @CommandMaster It was just a cut down example to explain the concept of a polyglot. I'm still unsure whether it makes sense to allow two or more languages or require all four. I feel like allowing two or more would enable more elegant solutions as snake Vs kebab is the same bar the delimiter and Pascal Vs camel is the same bar leading capitalisation. What're your thoughts? – Dom Hastings Jul 3 at 6:28
• Different language versions count as different languages (not sure of there's a relevant meta post. I'll try and look for it when I'm not on mobile.) – Dom Hastings Jul 3 at 6:29
• If the usual 'different command-line flags count as different languages' rule applies, then is there a risk that the snake vs kebab cases could be trivially solved using the command-line flag to specify the delimiter...? – Dominic van Essen Jul 6 at 11:23
• Yeah, I guess so. Something like Perl's -i flag could enable using \$^I to be either - or _. Although then doing the same would probably be tricky and potentially still at least a little ingenious. – Dom Hastings Jul 6 at 12:46
• "Have I missed any other major naming schemes?" Yes: Ada_Ninety_Five_Case, Title Case, and (jokingly) StRaNgEcAsE. What's wrong with UPPER_SNAKE_CASE? – fireflame241 Jul 9 at 5:55
• @fireflame241 I think that converting back from upper snake case might be slightly more tricky than just snake case, as checking for an underscore might not be enough to see if there's more transformation necessary, if for example there was already an underscore in normal text... I could state that isn't a problem though I guess? Adding more cases might make me lean towards mandating only a minimum of two transformations required as well and changing the scoring to number of transformations with code length as a tie-breaker... Thanks again, will think on this a bit. – Dom Hastings Jul 9 at 6:16
• If you restrict words to be composed only of letters, then you could avoid that issue, and a few others. For example, how would aB_Cd be handled? It could be snake case, where the _ separates the words, or camel case, where the _ is the start of the second word. I think right now there's too many test cases, too little explanation. – fireflame241 Jul 9 at 6:32
• @fireflame241 Yeah, I think you're right. Ok. I'll work on this. Thanks! – Dom Hastings Jul 9 at 6:45
• Re: flags as languages again. I was more thinking of a program 'checking' to see what flags had been used (even if they have no direct effect), and modifying its behaviour accordingly. For instance, perl -m foo + then checking whether foo is loaded. This would also be similar to language+library = different language. Worst cheat of all would be awk -v mode=1... – Dominic van Essen Jul 9 at 16:03
• Along the same lines, it would be important to specify that it isn't Ok to just run different versions of a language (which currently 'count' as different languages), and for the program to determine the version & modify its behaviour. – Dominic van Essen Jul 9 at 16:10
• I don't think it's possible to rule out different language versions for polyglot challenges, and using flags to classify as different languages might be questionable too. I guess if the answers aren't in the spirit of the task or are a little boring they'll be voted on accordingly. I'm open to more input on this though! Thank you for the feedback! – Dom Hastings Jul 9 at 21:13
• "polygot in at least two different languages" so we must write 4 programs, how can there be fewer than 4 languages? – qwr Jul 9 at 22:46
• @qwr I just amended the rules to allow 2 or more languages, you don't have to have all 5. I'm hoping this will allow some creative solutions. If I missed a reference to that I'm struggling to see it, but morning eyes... – Dom Hastings Jul 10 at 6:07
• For some reason I thought there were 4 programs. So to clarify, the minimum is two languages / two conversions? – qwr Jul 10 at 6:11

# Posted: Find the Block on the Extended Periodic Table Using the Diagonal Rule

• I would be more inclined to compete if all the elements were classified into the correct blocks. I know it's only a code-golf challenge, but somehow it seems annoying to deliberately give the wrong answer! I don't know whether there's a precedent for it, but is there any way to say, for instance "additional code to adjust the positions of elements (currently only 4: La, Ac, Lu & L4) that are exceptions to the diagonal rule will not be included in the byte-count"...? – Dominic van Essen Jul 10 at 6:22
• the real reason I made it require the wrong answer was because I do not quite know the behavior of the extended periodic table (are all group 3 elements in the d-block?) I will likely put the exceptions back, especially if I find the answer to that question @DominicvanEssen – golf69 Jul 10 at 6:33
• I think my guess about group 3 was correct. The best way to phrase the exceptions might be to say "all elements directly adjacent to an s-block element are in the d-block, and those directly adjacent to that block are also in that block" (phrasing tbd, as is that is way too ambiguous) @DominicvanEssen – golf69 Jul 10 at 6:56
• I like it if all the elements can be assigned in a rule-based way (rather than expermentally) to their correct positions. But, from the way you describe it, I get the impression that the 'diagonal rule' is more of a rule-of-thumb that breaks-down at tht 6th row... or have I misunderstood? – Dominic van Essen Jul 10 at 7:07
• A purely-cosmetic change could be to change the title to "Find the predicted block on the periodic table" and subtext as "as predicted by the Madelung_energy_ordering_rule". Then there'd be no exceptions (by definition), and nerds like me would be fooled into thinking that we're calculating 'correct' answers... – Dominic van Essen Jul 10 at 7:16
• The diagonal rule specifically breaks for the 3rd column (group 3). I like your idea of just changing the title, I will do that @DominicvanEssen – golf69 Jul 10 at 7:34
• I think it's still important to mention/highlight somewhere that the experimentally-measured periodic table deviates from that predicted by the diagonal rule at higher atomic numbers, and that this challenge is only to find the blocks predicted by the diagonal rule. Otherwise it could be confusing to understand what the intended output should be. – Dominic van Essen Jul 10 at 8:02
• Suggested testcase: 23:59 – fireflame241 Jul 13 at 17:11
• Can we take input base 60? – fireflame241 Jul 13 at 17:12
• 'in which you start both at exactly hh:mm:00' - should this rather say something like 'you start the timer when the clock shows exactly hh:mm:00'? – Dingus Jul 14 at 15:12
• @Third-party'Chef' Could you specify that handling unsolvable inputs is unnecessary? – fireflame241 Jul 14 at 15:57
• @fireflame241 Done. – user92069 Jul 15 at 13:24
• What's the upper limit of the output string Y? – user92069 Jul 25 at 5:24
• @Third-party'Chef' Y is a programming language not a string. – Ad Hoc Garf Hunter Jul 25 at 12:31
• Sorry, I meant X. – user92069 Jul 25 at 12:32
• @Third-party'Chef' I didn't put an upper limit, but its length is your score so longer means worse score. Is there some issue I am not seeing that means an upper limit is needed. – Ad Hoc Garf Hunter Jul 25 at 12:36

# Codington Crescent

Okay teams, it's now time to play the game called Codington Crescent. But first, I notice we have been swamped by a letter, which comes from a Mrs Trellis of North Wales. She writes "Dear Madam or Sir, Please make up your mind. Yours sincerely, Mrs Trellis". Okay, now on to the game

If you've ever listened to the radio program "I'm sorry, I haven't a clue", then you've probably heard of the game called "Mornington Crescent". For those who haven't, it's a game where players name random stations on the London Underground network. The first person to name "Mornington Crescent" wins the game.1

In the same sort of spirit as the classic radio game, I present to you Codington Crescent.

## The Challenge

The winner of this challenge is the first person to post a working program that prints the exact string Codington Crescent.

## The Rules

1. Each player has their own program that they will add/change characters. This is termed their running program.
2. Each answer (a turn) has to obey source restrictions defined by previous answers. These are called rules. Each varient lasts for 5 turns. Rules are in the style of either , or limiting of language names (but not both).
3. Running programs can change languages between turns.
4. Answerers (players) can either add or change (but not both) as many characters of their running program per turn as they like. Alternatively, they can choose to "pass", adding no new rules, and still counting as a turn.
5. At the end of each turn, the player declares a new rule that will span the next 5 turns. Rules must be objective, and a TIO verification program is highly recommended. Also, rules have to be able to be applied to every language (e.g. Programs must not error using Python 3.4.2 isn't a valid rule).
6. Play continues until a running program prints the target string.

## Starting Rules

As to kick off the game, the first 5 turns must follow these rules:

1. Turns may not print Codington Crescent.
2. Running programs must be irreducible.

## Example Rules

These are purely examples of what you could add as rules to the challenge. They do not apply unless someone decides to use them.

• Languages must have at least 3 characters in their name

• The first and last letter of the running program must be a space

• Running programs must have an even amount of bytes

• Languages must be in the practical category on TIO

• Running programs must not be more than 30 bytes

• You cannot answer twice in a row. Someone else needs to answer before you have another go.
• Languages need to be on Try It Online in order to be valid answers.

## Feedback

Do you think the game will ever reach an end. Also, have I explained the rules clearly enough?

1 The original game of Mornington Crescent doesn't really have rules... It's more of an activity that looks like it's a complicated game.

Written with StackEdit.

• I think that it will never. Assumes that it's easy to see whether the program is "two step away from being complete", the next user is never going to move it "one step away from being complete", since they can't win in that case. – user202729 Jul 24 at 16:36
• I agree with @user202729 that it will never terminate in its current state. It would be more likely to terminate if: languages could be changed every answer; answers could not remove 3 characters (or weaken to maybe remove 1 character; presently it allows loops); maybe allow for more characters added per answer – fireflame241 Jul 24 at 19:24
• @user202729 I've updated the rules to potentially avoid such loops – Lyxal Jul 25 at 7:14
• @fireflame241 I've updated the rules to potentially avoid such loops – Lyxal Jul 25 at 7:14
• Bonus for the first answer in Mornington Crescent? :-) – Luis Mendo Jul 25 at 10:07
• @LuisMendo sure, imaginary brownie points it is – Lyxal Jul 25 at 10:29
• All hail Lyxal, +1 – HighlyRadioactive Jul 25 at 11:04
• I think it will not complete until an Unary answer is produced because you can simply replace all characters that are not as with a. A long string of as is seldom a useful program. (that is, extending user202729's comment: you don't have to see the "two step away from being complete" state, it's sufficient to find a large class of programs that are definitely not "one step from being complete") – my pronoun is monicareinstate Jul 25 at 11:41
• @mypronounismonicareinstate I've completely changed the rules of the challenge to make it model a more plausible game. – Lyxal Jul 28 at 4:35

# Is this Chessboard Reachable?

The goal of this challenge is to determine, given the state of a chessboard, whether or not that chessboard can actually be reached in the course of standard play. Of course, doing this in general is a rather hard problem, so we'll be simplifying the problem to a set of a few rules which should approximate the "reachability" constraint.

Your input will be a chessboard, specifying what pieces are at what positions on the 8x8 board. At each position, there can be either nothing or a piece. If there is a piece, it is either a pawn, bishop, knight, rook, queen, or king, and it is either white or black. Input can be taken in any reasonable form. Your output should be truthy or falsy, indicating whether all of the below rules are satisfied.

For the below rules, I'll be using standard chess notation to refer to the squares on the board. That is, I'll be referring to squares on the board by their rank (1-8) and their file (a-h), as such

 8........
7........
6........
5........
4........
3........
2........
1........
abcdefgh


where the white player starts on ranks 1-2 and the black player starts on ranks 7-8. Obviously, you don't have to use the same notation, and if it's easier for you to take the board input flipped or rotated, that's fine too as long as you specify it in your answer.

For one of the rules, you have to distinguish between white and black squares on the board. The board is layered with a checkerboard pattern, so white squares are always immediately surrounded by black on all four sides, and vice versa. In typical chess, the a1 square is black, but that doesn't really matter for the below criteria.

## The Rules

In order for a board to be considered reachable, it must satisfy all of the following rules. This is , so you don't have to tell me which rule an unreachable board violated; all I expect of your output is a "yes" or a "no".

1. White and black each have exactly one king on the board: no more, no less.

2. Pawns cannot appear on rank 1 or rank 8.

3. Each player has a maximum of 16 pieces on the board total. These pieces must be a subset of the following: 2 bishops, 2 rooks, 2 knights, 1 queen, 1 king, and 8 wildcards. The "wildcard" pieces can be any piece they please (since we assume pawns could have been promoted).

4. For either player, if that player has at least two bishops, and those two bishops cannot have been promoted from pawns (i.e. they must be the "bishops" in rule 3, not the "wildcards"), then that player must have at least one bishop on a white square and at least one bishop on a black square.

5. All of a player's pawns must be able to reach the square they're occupying. More formally, for each player, there must be an assignment (an injective function) from the set of that player's surviving pawns to the files (a-h) they started on, such that each pawn can reach its current position from its starting position with only forward and forward-diagonal movements.

## Pawn Movements

Rule 5 may require some elaboration. Suppose a white pawn is on d5. Then it could have come from the following places (indicated by X)

 8........
7........
6........
5...♙....
4..XXX...
3.XXXXX..
2XXXXXXX.
1........
abcdefgh


So it could have started on a2, b2, c2, d2, e2, f2, or g2, but not h2. There must be an assignment of pawns to starting positions such that no two pawns started at the same position and every pawn can reach its current position from where it began. A black pawn follows the same rules but started on rank 7 and moves down rather than up. So a black pawn at the same position could have come from b7, c7, d7, e7, or f7, as follows.

 8........
7.XXXXX..
6..XXX...
5...♟....
4........
3........
2........
1........
abcdefgh


## Notes

• Only the rules above apply. Other complexities of a standard game of chess (in particular, castling or en passant) are not part of this problem and should not be considered.
• This is , so the shortest solution wins.
• Input can be taken in whatever form is most convenient. Output follows the usual rules, so any two distinct outputs for truthy/falsy are acceptable.
• This is an oversimplification of the reachability problem in chess. As such, an answer which provably enumerates every chessboard and tests for membership is not correct.

## Examples

Reachable chessboards (true):

 8♜♞♝♛♚♝♞♜
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1♖♘♗♕♔♗♘♖
abcdefgh

8........
7........
6........
5........
4........
3........
2..♚.....
1.....♔..
abcdefgh

8........
7.....♚..
6.♛......
5...♟....
4........
3.....♕..
2........
1...♔....
abcdefgh

8.....♚..
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1....♔...
abcdefgh

8.....♚...
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1....♔...
abcdefgh

8........
7.♚......
6...♕♕♕♕.
5..♕....♕
4..♕..♔.♕
3.......♕
2........
1........
abcdefgh

8........
7...♚.♟.♙
6.♙.♙..♙.
5.....♘..
4.♕..♕♘♗♖
3.....♘♗♖
2..♕....♖
1......♔.
abcdefgh

8♜..♛♚♜♜♜
7♟♟♟♟♟♟..
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1♖♘♗♕♔♗♘♖
abcdefgh

8♜♞♝♛♚♝♞♜
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙.
1♖♗♘♕♔♗♘♖
abcdefgh

8♛♛♛♛♛♛.♛
7........
6......♚.
5.♝.♝....
4.....♟..
3........
2..♖♖♖.♔.
1........
abcdefgh

8.....♚..
7........
6........
5........
4........
3.♙♙.....
2..♙♙♙♙♙♙
1.....♔..
abcdefgh

8.....♚..
7........
6........
5........
4........
3.....♙..
2...♙♙♙.♙
1.....♔..
abcdefgh

8.....♚..
7........
6.♟♟♟♟...
5.♟♟.....
4........
3........
2........
1.....♔..
abcdefgh


Unreachable chessboards (false):

(Rule 1: Not enough kings)

 8........
7........
6........
5........
4........
3........
2........
1........
abcdefgh


(Rule 1: Too many kings)

 8♚♚♚♚♚♚♚♚
7♚♚♚♚♚♚♚♚
6♚♚♚♚♚♚♚♚
5♚♚♚♚♚♚♚♚
4♚♚♚♚♚♚♚♚
3........
2........
1...♔....
abcdefgh


(Rule 2: Bad white pawn placement)

 8.....♚..
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2.♙♙♙♙♙♙♙
1♙...♔...
abcdefgh


(Rule 2: Bad black pawn placement)

 8.♟...♚..
7♟.♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1....♔...
abcdefgh


(Rule 3: Too many white queens)

 8........
7.♚......
6...♕♕♕♕.
5..♕....♕
4..♕..♔.♕
3..♕....♕
2........
1........
abcdefgh


(Rule 3: Too many black pieces)

 8♜♞♝♛♚♝♞♜
7♟♟♟♟♟♟♟♟
6......♟.
5........
4........
3........
2♙♙♙♙♙♙♙♙
1♖♘♗♕♔♗♘♖
abcdefgh


(Rule 3: Too many white pieces)

 8........
7...♚.♙.♙
6.♙.♙..♙.
5.....♘..
4.♕..♕♘♗♖
3.....♘♗♖
2..♕....♖
1......♔.
abcdefgh


(Rule 3: Too many black rooks)

 8♜..♛♚♜♜♜
7♟♟♟♟♟♟♟.
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1♖♘♗♕♔♗♘♖
abcdefgh


(Rule 4: White bishops are the same color)

 8♜♞♝♛♚♝♞♜
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1♖♗♘♕♔♗♘♖
abcdefgh


(Rule 4: Black bishops are the same color)

 8♛♛♛♛♛♛♛♛
7........
6......♚.
5.♝.♝....
4.....♟..
3........
2..♖♖♖.♔.
1........
abcdefgh


(Rule 5: White pawn placement is impossible)

 8.....♚..
7........
6........
5........
4........
3..♙.....
2.♙♙♙♙♙♙♙
1.....♔..
abcdefgh


(Rule 5: White pawn placement is impossible)

 8.....♚..
7........
6........
5........
4........
3.....♙.♙
2...♙♙♙.♙
1.....♔..
abcdefgh


(Rule 5: Black pawn placement is impossible)

 8.....♚..
7.♟♟♟♟...
6........
5.♟♟.....
4.♟♟.....
3........
2........
1.....♔..
abcdefgh


## Example Implementation (Python 3)

# Takes input from stdin in the form shown above (a grid of Unicode
# chess characters and dots). Prints True if reachable. Prints False
# and the first rule number which is violated if unreachable.

import sys
from collections import defaultdict, namedtuple

Piece = namedtuple('Piece', ['color', 'type'])

# Read in the data from stdin.
data = []
for line in sys.stdin:
chars = list(filter(lambda x: x in ".♟♙♝♗♞♘♜♖♛♕♚♔", line))
if chars:
data.append(chars)
if len(data) == 8:
break
assert len(data) == 8
for line in data:
assert len(line) == 8

# Parse it into a more convenient format.
translation = {
".": None,
"♟": Piece('black', 'pawn'),
"♙": Piece('white', 'pawn'),
"♝": Piece('black', 'bishop'),
"♗": Piece('white', 'bishop'),
"♞": Piece('black', 'knight'),
"♘": Piece('white', 'knight'),
"♜": Piece('black', 'rook'),
"♖": Piece('white', 'rook'),
"♛": Piece('black', 'queen'),
"♕": Piece('white', 'queen'),
"♚": Piece('black', 'king'),
"♔": Piece('white', 'king'),
}
for rank in data:
for i in range(8):
rank[i] = translation[rank[i]]

# Count the number of each piece that each player has, slotting
# necessary pawn promotions into their own category.
allowed = { 'bishop': 2, 'rook': 2, 'knight': 2, 'king': 999, 'queen': 1, 'pawn': 0 }
pieces = defaultdict(lambda: 0)
for rank in data:
for piece in rank:
if piece is None:
continue
if pieces[piece] >= allowed[piece.type]:
# Already have too many; it's a promoted pawn
pieces[Piece(piece.color, 'pawn')] += 1
else:
# Count it normally
pieces[piece] += 1

# Rule 1: Each color should have exactly one king.
if pieces[Piece('white', 'king')] != 1 or pieces[Piece('black', 'king')] != 1:
print(False, 1)
exit(0)

# Rule 2: Pawns cannot appear on rank 1 or rank 8.
for piece in data[0] + data[7]:
if piece is not None and piece.type == 'pawn':
print(False, 2)
exit(0)

# Rule 3: Since we already put any "overflow" pieces at the pawn key,
# we just need to make sure we have at most eight pawns.
for color in ['white', 'black']:
if pieces[Piece(color, 'pawn')] > 8:
print(False, 3)
exit(0)

# Rule 4: If we have both bishops and our pawns are all accounted for,
# then we have to have a bishop in each color.
for color in ['white', 'black']:
if pieces[Piece(color, 'bishop')] >= 2 and pieces[Piece(color, 'pawn')] >= 8:
squares = { 'white': False, 'black': False }
for y, rank in enumerate(data):
for x, piece in enumerate(rank):
square_color = 'white' if (x + y) % 2 == 0 else 'black'
if piece == Piece(color, 'bishop'):
squares[square_color] = True
if not (squares['white'] and squares['black']):
print(False, 4)
exit(0)

# Rule 5: All pawns must be able to get to where they are. I solve
# this here by brute force (simply trying every possible permutation),
# which is exponentially inefficient, but it'll do for this example.
def recursive_assign(taken, choices, i):
if i >= len(choices):
return True
current = choices[i]
for x in current:
if x not in taken:
if recursive_assign(taken + [x], choices, i + 1):
return True
return False

for color in ['white', 'black']:
starting_file = 6 if color == 'white' else 1
choices = []
for y, rank in enumerate(data):
for x, piece in enumerate(rank):
if piece == Piece(color, 'pawn'):
possibilities = range(8)
possibilities = filter(lambda i: abs(i - x) <= abs(y - starting_file), possibilities)
choices.append(list(possibilities))
if not recursive_assign([], choices, 0):
print(False, 5)
exit(0)

print(True)


## Sandbox Concerns

• I worry Rules 4 and 5 are still not clear enough. I tried to write them in a way that was as clear as possible while still being mathematically unambiguous.
• too long. try to combine rules or at least don't draw so many of them in a column – Noone AtAll Aug 4 at 9:06
• If you're going to use unicode chess symbols, use a double-wide filler character instead of .. The alignment in your examples is off, making it very distracting. I'd recommend switching them to ASCII letters using the typical KQRBNP convention. – Beefster Aug 4 at 16:40
• To add to Beefster's comment, in some fonts the chess symbols are not even double wide, they're somewhere in between. So double-wide fillers won't work either. +1 for ASCII notation. – Bubbler Aug 4 at 23:43
• if I recall correctly, you can have two bishops of the same color. Up to nine. By promoting pawns to bishops. Very rare indeed, but legal. I want this to main page, though. – V. Courtois 23 hours ago

In Britain, road identifiers use a scheme of a letter, followed by a 1-4 digit number.

From Most-Important to Least-Important, the letters are:

M
A
B
C
D
U

The numbers also represent further assumptions around the importance of the road, such that a 1-digit number is more important than a 4-digit number.

Thus, the M898 is less important than the M8, but more important than the A8.

interesting but not relevant for the challenge - Roads are also sorted into nine Zones, of equal importance. The first number in each road identifier gives the Zone that the road starts in (e.g. A8 starts in Zone 8 - although there are exceptions where one Motorway spurs off of another, e.g. M48 is so named because it is a spur of the M4 even though it is officially in Zone 5).

## The challenge

Given a pair of road identifiers, identify and output which is the most important road. Where there is no difference in importance by the above rules (e.g "B4063" and "B1234") then either output is acceptable.

Usual I/O rules apply, this is so lowest bytes wins. There will be two inputs, and no invalid inputs (i.e. they will follow the rules, although they may not be actual real-life roads).

If you say so in your answer, you may instead output the least significant road (i.e. as long as I know which it is, you can do either).

You may take the input as a string, array of strings, or array of strings and integers as follows:

"M123M223"
["M123","M223"]
["M",123,"M",223]

#SANDBOX# If there are input formats that you think should/n't be allowed, let me know.

## Examples

• A11,M2 -> M2(Motorways come before A roads)
• M823,M89 -> M89 (two-digit roads are more important than 3-digit roads, even though 89 alphabetically comes after 823)
• A1262,A150 -> A150
• U6340,D6340 -> D6340
• M1,M2 -> Either
• B100,C99 -> B100
• I'd suggest simplifying sorting to just comparing two distinct values. Or even, mapping a value to a number so that the comparisons are right. – xnor Aug 4 at 19:56
• @xnor sorry I'm not sure what you mean. Do you mean only ever have two inputs? – simonalexander2005 Aug 5 at 7:25
• Yes, like have a possible input be like f("A11","M2") with it being a decision problem to tell if the first or second one is more important. Or, just have us write a function g producing a number so that, say, g("A11")>g("M2"). – xnor Aug 5 at 21:11
• @xnor how's that? I've made it return the most (or least) significant road of a pair – simonalexander2005 Aug 6 at 7:34
• Looks good! I'm a bit worried about the "any sensible format" since counting digits is important. Like, would a length-four array padded with nulls for missing digits count as acceptable? I think this would be you compare the number parts as a direct list comparison in some languages. – xnor Aug 7 at 3:15

# Golf a Golfing Language (WIP)

Design a language and golf its interpreter so that it solves the following programming challenges in as few bytes as possible:

• Hello World
• 99 Bottles of Beer
• Quine
• cat
• List primes up to $$\n\$$ / first $$\n\$$ primes
• Fibonacci Sequence
• Sort a numerical list
• Balanced parentheses test
• <simple string parsing>
• Brainf*** interpreter (as a proof of Turing completeness; or simpler alternative)

# Rules and Scoring

• Programs written in your language can use any convenient IO method
• Hello World, 99 Bottles of Beer, cat, and the quine can output any amount of leading and trailing whitespace.
• The quine must be at least one byte long
• The full range of 32-bit signed integers must be supported, at minimum, for all numeric challenges

Score = <size of interpreter, in bytes> * 10 + <sum of size of all programs, in bytes>

It's better to have a smaller interpreter than short programs, making builtins potentially more costly than a smaller instruction set.

• isn't this better as a popularity contest? – Razetime 2 days ago
• So, I can submit a ZISC with no instructions. So no matter how much I write in my programs, my score will always be 0! – petStorm 2 days ago
• I support this challenge, but "unique instructions" is ill defined. Not all golfing languages are imperative. – HighlyRadioactive 2 days ago
• @HighlyRadioactive What I was trying to go for with the number of instructions is to make it costly to have builtins for "Hello World", cat, etc... There's probably a better way to do it without directly penalizing builtins. Any ideas? – Beefster yesterday
• @Razetime There are already challenges for designing golfing languages. None ask you to golf the interpreter itself. Golfing it also makes scoring objective, which is generally much better received in the community. – Beefster yesterday

# Count Syllables

The goal of this challenge is to write a program that can count the syllables in a word as accurately as possible.

## Input

On STDIN, your program will receive a number X followed by X lines, each containing a single word. Simple enough. (Should there be a limit on the size of X?) The words will come from this list.

4
challenge
to
count
syllables


## Output

Your output should be to STDOUT and have X lines. On each line should be the number of syllables counted in that word.

2
1
1
3


# Scoring

To score you program, it will receive a long secret list of words to test. All programs will receive the same list of words. For each word, the number of syllables that your program got wrong will be added to the score of the program. If it output a 4 or a 2 when the word had 3 syllables, then one point will be added. If it said a 15 instead of a 3, then 12 points will be added to the score. The lower the score, the better.

For example, if for the above input your program output 3 2 2 2 (which would be produced by a program that counts strings of vowels), then the program would receive a score of 2.

# Rules

Your program should not access any external files (such as the word list). Also, your program should be no more than 5,000 bytes long (is this a reasonable limit?).

The winner will be the person whose program has the lowest score, therefor the most accurate syllable counter. The deadline for submissions is [some time at least a month away].

# Suggestions

I am open to all constructive criticism. Is 5,000 bytes a reasonable limit for the program size? How long should the official scoring test be? How long should the deadline be?

• This has one major flaw: the output is subjective. How many syllables do these words have? Every; victory; hierarchy; desire; oil; hour; poem. The only real way I see to work around this is for you to produce a marked-up version of the word list. – Peter Taylor May 29 '12 at 20:40
• I was really worried about that, and I don't see a way around it. – PhiNotPi May 29 '12 at 20:42
• I personally would love to see more language processing challenges. I agree with @PeterTaylor on the difficulty of some words. Perhaps taking a specific text(s) and identifying explicitly in the challenge which words will have how many syllables? – Gaffi Jun 8 '12 at 3:34
• @PeterTaylor ...Or maybe you could filter ambiguous words out of the reference list? – user16991 Feb 8 '15 at 1:19
• What's the point of the first line of input? – msh210 Apr 27 '16 at 20:05
• If you provide a reference list, A hyphenated reference list, and hide a secret list which may or may not include members of the reference list, this would be a reasonable challenge – Rohan Jhunjhunwala Sep 17 '16 at 0:05
• Do you plan to post this? If not, I'd be happy to adopt it. (If you don't respond within two weeks, by community standards, I'm allowed to do so.) – MD XF Aug 18 '17 at 3:20
• The example of inaccurate program that would score 2 - did you mean to output 3 1 1 2 rather than 3 2 2 2? – Heimdall Nov 9 '17 at 18:31
• A reference list could be dynamic: potential contestants can ask for words of their choice to be added to the list. They won't know what's on the secret list but will try to make their programs as accurate as possible (according to your syllable count) so they should always be able to ask for specific words they are not sure about. Of course, you could make it in different language. In my language, Slovene, it's much clearer how many syllables words have. How about Solresol, haha! – Heimdall Nov 9 '17 at 18:38
• I am going to adopt this if you don''t respond – Christopher Dec 20 '17 at 16:48

## Play Simple 2-Dimensional Minecraft

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

## Details

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

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

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

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

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

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

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

## The challenge

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

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

## Suggestions?

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

Overview:

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

Objective:

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

Rules/Constraints:

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

Example I/O:

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

## Sandbox Questions:

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

• Not everyone says numbers the same way. Does the parser have to treat the following as equivalent? "negative one hundred five", "minus one hundred five", "negative one hundred and five", "minus one hundred and five", "negative a hundred five", "negative a hundred and five", ...? – Peter Taylor Jun 15 '12 at 15:12
• @PeterTaylor I had had a similar thought re: operators. ("plus" versus "add", etc.) I think it would be more interesting to account for all, but given the wide variety of possible inputs, it may generally be better to limit the options to a specifically defined set (which I have yet to define). – Gaffi Jun 15 '12 at 15:18
• @PeterTaylor I've added some of these details. Please let me know if there's anything unclear about them. – Gaffi Jun 15 '12 at 16:10
• I don't spot any ambiguities in the parser. There is still an ambiguity relating to decimals, though. What precision should be used? Also, I notice now that there's no winning condition. Is this intended to be code-golf? (Ugh - tons of strings which will have to be hard-coded in most languages. I expect Perl has a suitable parser already in CPAN, though...) – Peter Taylor Jun 19 '12 at 9:03
• @PeterTaylor I don't know where I went... I've updated the spec. re: decimal places and objective. – Gaffi Jun 29 '12 at 13:24
• @PeterTaylor metacpan.org/pod/Lingua::EN::Words2Nums – msh210 Apr 27 '16 at 20:37

# Huffman Decoding

Write a programm which takes two strings as input and prints a text.

The first argument is a Huffman Tree, serialized in the following format:

• every ascii character except ~ is always a leaf, if ~ is the first characater it is also a leaf.
• <tree0><tree1>~ is a tree where <tree0> is the left subtree and <tree1> is the right subtree.

Example: ab~cde~~~ generates this tree:

 ┌─┴─┐
┌┴┐ ┌┴─┐
a b c ┌┴┐
d e


where a would have the key 00, b 01, c 10, d 110 and e the key 111.

The second argument is a text that has been compressed with with the Huffman code that is defined by the first parameter. This bit-string can contain any bit sequence (also null-bytes and non-printable characters) and is not byte aligned, therefore it has been encoded with a variation of the standard Base64 encoding:

• the characters used for the encoding are the standard base64 characters: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
• the bitstring is broken up into 6-bit chunks and mapped to this characters
• if the last chunk is smaller than 6 bits, a character with this prefix is used, and padding characters are added to the string:
• - : the last chunk was five bits long
• = : the last chunk was four bits long
• =- : the last chunk was three bits long
• == : the last chunk was two bits long
• ==- : the last chunk was one bit long

Example:

bits:       1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1
chunks:    |1 1 1 1 0 1|1 0 1 0 0 1|1 1 0 1 0 1|0 0 0 1 1 0|1[0 0 0 0 0]|
characters:       9           p           1           G           g
base64:     9p1Gg==-


Your programm has to decode the text encoded in the second parameter and print it to stdout.

You have to provide your source code encoded in the way described above. The length of your encoded source code + the length of your serialized huffman tree will be the winning criterion.

TODO: example input

• It would be helpful to explicitly state the 64 characters used in the encoding. I presume they're A-Za-z0-9+/ but (especially if you're expecting people to implement that part explicitly) it's best to make the problem self-contained. – Peter Taylor Oct 8 '12 at 16:23
• Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) – programmer5000 Jun 9 '17 at 15:30

# Graphical Output -- Esoteric Artifacts -- The Glass Bead Game

## Draw the Cabalistic Tree of Life

Simply described, the Tree of Life is an undirected network of nodes representing the conduit between matter and higher forms of spiritual energy. It has an upper face arranged in a hexagon, and a lower fact built from equilateral triangles adjacent to the lower two edges of the upper face. Don't label the paths, paths may overlap however you wish, may be single (thick) lines, even. Code Golf. Bonus -100 for labels on the Sephiroth (nodes); Bonus -150 for Hebrew labels.

## Draw a Mandala for each Natural Number

Draw a circle with interesting visual patterns using the input N [ 1 .. \inf ) to determine the number of points around the circle to anchor figures whose shape is also modified by the input N. Actually, 12 seems like a good max: they're pretty much a blur after that no matter what.

//lotsoflines n = 1 ..12

(doesn't need to be this elaborate, This is >600 lines of showing-off.).

. . . need good images for these . . .

## Draw the Ptolemeic System of the Universe

All the stuff I could find is animated already. Maybe this one's done-to-death. :(

Update: Found good stuff on Alchemy. The "Keplar Platonic" model could be fun (3D and all). This one looks good, too. And this.

## Draw the Pythagorean Monochord

aka pre-classical nomogram. I misplaced my Pythagoras books, I know I've got a picture somewhere.

This is the one I was thinking of.

But I think this one's even cooler

## Draw the I-Ching Hexagrams in King Wen Sequence.

I suppose I need to implement this first to avoid copyright issues! :)

• The I-Ching one would have to be in standard order to be remotely interesting, and then becomes as much about kolmogorov-complexity as graphical-output – Peter Taylor Nov 22 '12 at 21:24
• For the others: images, please! – Peter Taylor Nov 22 '12 at 21:25
• I've emailed the owner of the Alchemy pages asking for permission to use his copyrighted images. Awaiting response. – luser droog Jan 28 '13 at 8:25

## DeCSS

It is known that the DVD Content Scrambling System can be deciphered with a rather short program (434 bytes of C, 472 bytes of Perl). Can you do better?

<< Test cases go here >>

I don't plan to include a more detailed spec, because it will just wind up duplicating some of the code. The test cases would be in the form of (key, link to data file, md5sum of the deciphered stream).

• And the winning criterion is who is the first to get post from the courts? – celtschk Oct 3 '15 at 20:18
• @celtschk, I think that would be unfair. Winning criteria shouldn't really depend on where people live... – Peter Taylor Oct 10 '15 at 20:56
• I think you should at least explain the general concept of the spec. – Rohan Jhunjhunwala Aug 2 '16 at 22:53
• This actually sounds interesting. @PeterTaylor Perhaps you could use (and link to) Charles Hannum's explanation of the algorithm and post this. (It would be fun to have it as a popularity contest for a program that looks like it's nothing DeCSS related, or a program that furthers the gallery's point about the text vs source code arbitrary distinction - but I don't know if popularity contests are popular any more!) – sundar - Reinstate Monica Jun 25 '18 at 8:25

## Code golfing problem: Surface classification

The task: Given a surface-word reply with the classification of what surface it is.

Example 1: Input: aba'b' ----> Output: 1T

Example 2: Input: aabcb'c' ----> Output: 3P

Bounds on the problem: Since there are only 26 letters, there will never be more than that many labels. Additionally output should be in the form S,nT,mP for n,m positive integers.

Background: In the study of algebraic topology students are often presented with diagrams such as the one below. The represent instructions for how to assemble a surface. The assembly is prescribed as: if there are two edges labeled with the letter x then glue them together so that the arrows point the same direction. To make our job easy, topologists have discovered an algorithmic way to classify surfaces using 'words' assembled from these 'plane gluing-diagrams'.

Choosing a corner arbitrarily (top right) and orientation (ccw) we read off the labels on the edges where an inverse appears wherever the arrow points against the orientation. In this case the 'word' that represents this plane model is given as abab.

A surface word is a string that contains the letters a,b,...,@ up to some letter @ and each letter is contained in it exactly twice. In the two occurrences of each letter: 0, 1, or 2 of them may be postfixed by a ' which I am considering using to represent 'inverse' (opposite orientation).

If in a surface word all letters appear twice: once without the ' and once with it (f.ex. ba'b'a) then we say that the surface the word represents is orientable. If a surface is orientable then it is necessarily the direct sum of n Tori for some non-negative integer n. If this condition doesn't hold (like in aab'b) then the surface represented is non-orientable: in this case it is the direct sum of m Projective Planes for some positive integer m.

Once you have found out if the reduced word is orientable or not, the final answer is given as follows. If orientable and number of unique letters in the reduced word is 1 then output should be S. Otherwise if the number of unique letters in an orientable word is n (it will be even) then the output should be sT where s = n/2. If the word is non-orientable then the output should be mP where m is the number of distinct letters in the reduced word.

The goal is to take as input some surface word, reduce it via reduction rules 1-6 and then classify it as a sphere, some number of connected tori, or some number of connected projective planes. Here are the 6 reduction rules where ~ represents 'reduces to':

Let M,A,B,C,D be surface words, x be a single letter, and juxtaposition represents concatenation:

1. Cycle Rule: If M = AB then M ~ BA
2. Flip Rule: M ~ M'
3. Sphere Rule: Axx'B ~ AB
4. Block Rule: ABC ~ ADC if B is a surface word and B ~ D by 1 or 2
5. Cylinder Rule: If M = AxBCx'D, then M ~ AxCBx'D
6. Möbius Rule: If M = AxBxC then M ~ AxxB'C ~ AB'xxC

I am looking for input on:

• should this be code-golf or programming-challenge?
• how would scoring work?
• ???

If I feel satisfied with the question in a few days I'll post it to the site.

• If, for each input, there is only one correct output, then it should probably be code-golf. The scoring criteria would then be source code length. – PhiNotPi Jun 8 '13 at 14:33
• Yes, this is the case. In general however there is not a unique series of applications of the reduction rules for any given instance. – Kaya Jun 8 '13 at 16:21
• I don't think the order of explanation is correct. You should explain reduction before talking about "the reduced word". And "reduce it via reduction rules" doesn't entirely make sense, because the rules are presented as equivalences rather than reductions, and most of them don't have a "natural" direction. – Peter Taylor Jun 10 '13 at 8:49
• It's also occurred to me that you haven't defined the notation M'. Does it just consist of toggling the orientation of each token, or does it also reverse the entire string? And do you have test cases which between them force implementation of all of the reduction rules? – Peter Taylor Jun 11 '13 at 8:32
• Good call on the string inverse, yes you have the right idea and I will make it clear. I have a lot of test cases from when I did a number of these computations by hand in a university course and (anecdotal experience) I am pretty sure that it is possible to force the use of all the reduction rules (except maybe 4 which is really just a meta-rule for convenience when doing proofs). Additionally you have alerted me to some concerns regarding the form of the proper output: it's definitely underspecified. I'll put some work into this today. – Kaya Jun 11 '13 at 14:04

I have no idea how to create a good code golf question!

See this description of a ray tracer with source code that fits on a business card. The author stopped when the code size was 1337 bytes.

• BTW--The one you linked can get a little bit more with #define Q return (R was already taken for the rand wrapper) and #define O operator. – dmckee --- ex-moderator kitten Oct 6 '13 at 17:33