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

• How are tags added to questions? – guest271314 Jan 9 at 7:51
• @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] – DJMcMayhem Aug 29 at 15:19
• Why no featured anymore? Can't we have it auto-added or something? – JL2210 Sep 26 at 15:57
• @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary – caird coinheringaahing Sep 29 at 13:43

# Squaring the circle

## Background

This is a generalization of this question on puzzling.SE. Essentially, it asks you to generate a circular array of integers such that any two adjacent integers add to a perfect square, and that the integers are a permutation of those from 1 to 50. The original question gave you a part of the array, and asked you to solve it. I wish to generalize this problem.

## Problem Description

Given an integer n, generate a circular array of numbers from 1 to n such that any two adjacent integers sum to a perfect square, without repeats of any number.

## Input

Input is limited to positive integers greater than or equal to two.

## Output

If there is no possible array (as can be manually proven to be the case for n=4), then your function should gracefully handle the error and exit.

Otherwise, it should output a representation of that array for that n as a string of delimited integers, such that, if the string were concatenated into a long integer, it would be the minimum possible string. To illustrate:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1


Of these six representations, only 1 2 3 is in minimal form.

You may delimit your string in any consistent, parsable way you choose.

## Example I/O

For n<32, there are no valid arrays (And I can prove it, if necessary.) The smallest n with a valid array is n=32, and it is structured:

=>01 08 28 21 04 32 17 19
15                       30
10                       06
26                       03
23                       13
02                       12
14                       24
22                       25
27                       11
09 16 20 29 07 18 31 05


The output to n=32, would therefore be 1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15

## Example code

Because code is clearer than words, here's a (purposefully) very naive and inefficient routine for this in Python (2.7):

import math, itertools
def main(n):
def test_if_a_given_list_is_a_ring(input_list):
is_a_square = lambda value: math.sqrt(value).is_integer()
output_flag = True
for index in range(len(input_list)):
if is_a_square(input_list[index]+input_list[index-1]):
continue
else:
output_flag = False
#end if
#end for
return output_flag
#end test_if_a_given_list_is_correct
def turn_it_into_a_string(input_list):
temp_list = []
for i in input_list:
temp_list.append(str(i))
#end for
output_string = ''
for i in temp_list:
output_list += ' '+ i
#end for
return output_list[1:]
#end turn_it_into_a_string
lowest = string(n)*n

for perm in itertools.permutations(range(n,0,-1)):
if test_if_a_given_list_is_correct(perm):
flag = True
for perm_character,lowest_character in zip(turn_it_into_a_string(perm),lowest):
if int(lowest_character) < int(perm_character):
flag = False
break
#end if
#end for
if flag:
lowest = turn_it_into_a_string(perm)
#end if
#end if
#end for
return lowest
#end main


If you're gonna golf this code... I'd highly recommend optimizing it first.

## Scoring

Programs will be scored based on: 1. Asymptotic complexity 2. Average runtime 3. Byte count 4. Runtime when the byte count is fed into the program as input

(I can't decide which of these scoring systems to use. Note that I've manually worked out that when n<=31, there are no arrays. At n=31, there is a valid double loop system, but no valid single loops.)

• your example is not a valid ring, is it? I only see two perfect squares, 11+5=16 and 1+8=9 – Luca H Dec 1 '17 at 9:18
• No, it isn't. As of ten minutes ago, I constructed (By hand) the ring for n=32, so I'll post that. – Jakob Lovern Dec 1 '17 at 18:56
• (1) "ring" has a specific meaning (an algebraic structure with multiplication and addition subject to certain rules), which is distracting. How about changing it to circular array? (2) In my opinion, "generate a [circular array] of numbers from 1 to n" does not impose a restriction on the length of the array or on the impossibility of repeats. For me the clearest way to add the restrictions which I infer from the linked question would be to say that it's a permutation of the numbers from 1 to n. – Peter Taylor Dec 1 '17 at 21:02
• (3) "This is a two part question": I only see one part. If you intend a follow-up, maybe worth including it so that you can get opinions on whether it would be closed as a dupe of the first part. – Peter Taylor Dec 1 '17 at 21:03
• @PeterTaylor I was originally intending to ask the question twice, but score using different conditions. I expect that code which would minimize asymptotic complexity wouldn't look at all similar to code which minimizes size. I wanted to see the difference. You made a good point on the dupe problem, though, as the two questions are essentially similar to each other. – Jakob Lovern Dec 1 '17 at 21:44
• So what's the scoring? If byte-count gets fed to the program no solutions that are < 31 bytes & if it's gonna be an average runtime based scoring you should choose large enough values such that it becomes about complexity and include how you measure. – ბიმო Dec 3 '17 at 3:10
• That's exactly why I was asking for input on my various ideas for scoring. I don't expect that there's going to be any programs that small that can successfully answer the question, but it could happen. I'm leaning towards asymptotic complexity or byte count. – Jakob Lovern Dec 5 '17 at 18:01

k-combinations for a set of size n represent in what different ways one can pick k elements out of a set of n elements. There is a natural representation of such a pick as an integer with n bits, of which exactly k are set.

Define next[n, k] :: Pick(n, k) -> Pick(n, k) to be the group action that takes each pick to the next one, wrapping around. More formally: Let r be an n-bit integer with k bits set. Then next[n, k](r) will return the smallest integer > r that also has k bits set. If there exists no such integer, the smallest integer with k bits is returned. Example: next[4, 2](0b0011) = 0b0101, next[4, 2](0b1100) = 0b0011.

[- Annotation: if k = 0, then there is only one unique integer with zero bits set. next[n, 0](r) = 0. -]

You will be given a pick r and a positive integer step. Output (next[n, k]^step)(r), that is, apply next[n, k] step times to r.

### Rules

• You will be given 4 integers n k r step. Output (next[n, k]^step)(r)
• 1 <= n can be assumed to be small enough to represent picks as integers naturally in your language
• 0 <= k <= n
• r will always be a valid pick of k out of n.
• 0 <= step <= C(n, k) can be relatively large. As an example, C(32, 12) = 225,792,840

### Criteria

Return the correct output for all valid inputs.

This is code-golf, shortest code wins.

### Examples

4   2 0b1001 2  => 0b1100
16 10 0xF11F 10 => 0bF15E
4   2 0b1100 2  => 0b0101

• Nice challenge! But what if k = n = 0? And maybe specify formally how next works. – ბიმო Dec 3 '17 at 5:38

# Best Yahtzee score

Yahtzee is a game played with five six-sided dice and a score sheet with thirteen different boxes to fill a score in. Each box has its own scoring rules:

• 1s, 2s, 3s, 4s, 5s, 6s all score points equal to the sum of the respective dice (that is, a roll of [3, 2, 3, 1, 5] scored as 3s would be awarded 6 points - 3 for each 3).
• 3-of-a-kind and 4-of-a-kind (as they sound, three or four dice rolled the same) score points equal to the sum of all five dice.
• Full house (two dice show one value, the other three show another) scores 25 points
• Small straight (four consecutive values) scores 30 points
• Large straight (all consecutive values) scores 40 points
• Yahtzee (all dice show the same value) scores 50 points

The thirteenth (chance) makes sense in-game, but not so much for this challenge; additionally the game has bonuses for extra Yahtzees which make no sense here. Because the challenge is...

Given five dice as input (five integers 1-6, input however is convenient), output the highest score that roll can score as well as what box it's being score under. The score should be output as its decimal numeric value, whether that's an integer or a string representation thereof, whatever. It should be immediately recognizable as a number. How you identify boxes is up to you so long as they are all unique and any given roll that will be scored in a given box always returns the same value. Please specify in your answer how boxes are identified. Order ([score, box] or [box, score]) does not matter. If you're outputting to STDOUT or otherwise not returning two values from a function, please separate score and box with at least one non-alphanumeric character of your choosing.

Code golf, so shortest answer in a given language wins. Standard loopholes apply.

Test cases, using , as separator, and 123456kKfsly for the box names (respective of their order above):

in: 1 5 4 3 2
out: 40
in: 1 1 4 3 1
out: 10
in: 1 1 6 5 3
out: 6


## Sandbox/meta

• I saw one existing Yahtzee challenge, but IIRC it boiled down to scoring a whole game. I did the 'given five dice, what is the best score' exercise once and felt like there were some interesting challenges to be found in optimizing it.
• Better ways to express I/O? I want it to be flexible but relatively readable...
• My first potential submission, I'm sure I'm forgetting something...
• IMO, multi parts output is pretty much a party killer. In that specific question, I think the score itself is enough to constitute a nice challenge. The box value is drived by conditional programming, which (of the challenge goes well) might not be present in some answers. – Uriel Dec 6 '17 at 22:58
• Anyway, for that wide range of possibilities, you should add at least one test case to cover collisions, multiple scorings and at least one of each box type (again, as I see challenges here) – Uriel Dec 6 '17 at 23:00
• @Uriel Thanks for the input — I planned to fill in more test cases, I guess I could've mentioned that in the meta section. I'm not trying to be difficult, but I'm curious if you could expand on your other point w/ the score itself being enough. The score is (I believe?) entirely dependent on the box being determined, and spitting something box-related out seems programmatically like a small challenge vs. the 'reward' of the output. This was why I wanted that output to be very flexible. Part of me thinks you're right, part of me thinks I'm right… so if you have more to say, please do… – brhfl Dec 7 '17 at 2:37
• my point is, in order to get the right score the user necessarily went through the right box (and not even print it, but also did a somewhat-more-complex calculation with it) - so it's kinda like letting them output twice. – Uriel Dec 7 '17 at 10:02
• @Uriel Makes sense, and I was leaning that way the more I thought about it last night. Cutting it also eliminates the need to address collisions. I think it's out... Thanks! – brhfl Dec 7 '17 at 13:35

# Google Doodle Kids Coding-style simulator

One input is a list of commands. There are three action commands and a loop construct. There is some flexibility as to the command format:

• As a string or equivalent: The loop construct should use a pair of matching brackets. The direction commands should be < and > or L and R (either case). The motion command should be ^ or F.
• As a list of characters: The loop construct should be a sublist. The other commands should be individual characters in the list, specified as above.
• As a list of integers: The direction commands should be -1 and 1 while the motion command should be 0.

The other input is the starting position. This consists of an two-dimensional array in any suitable format (including a newline-separated string). Background values should be represented using 0 or spaces. Carrots should be represented using -1, ^ or V (either case). The starting square should be represented using 1, @, or R (either case).

Optionally, the starting direction can be an input (one of <>V^ or an angle in degrees or turns), or it can be hard-coded (please specify the default starting direction in this case).

Command rules:

• Loops always execute four times
• The direction commands rotate the rabbit in place
• The motion command moves the rabbit one square in the current direction

The rabbit wins if it eats all of the carrots.

The rabbit dies if:

• It runs out of commands
• It walks out of bounds
• It walks onto the background

The starting square and carrot squares are all safe.

Your output should be a consistent truthy value if the rabbit wins, and a consistent falsy value if it dies. This can also be achieved by exception or error exit.

This is , so the shortest program or function that breaks no standard loopholes wins!

• Related – Emigna Dec 8 '17 at 11:51
• What's the background? – user202729 Dec 8 '17 at 12:07
• 1) exception exit is already a standard way to output a falsey value, and 2) in the actual Google doodle you don't lose if you try to walk off the edge of the map, it just does nothing. – Nissa Dec 8 '17 at 14:02
• @StephenLeppik It's not meant to exactly simulate the Doodle. – Neil Dec 8 '17 at 14:32
• By "background" I means as in "It walks onto the background". – user202729 Dec 9 '17 at 10:04
• @user202729 The background is any square whose value is 0 or space depending on your input format. – Neil Dec 9 '17 at 10:55
• Ready to post to main? – user202729 Dec 11 '17 at 5:48
• Don't abandon this... :( – user202729 Dec 18 '17 at 15:43

# Background

Many people visit webpages, which require special browsers because of lack of compatibility. So you have to write a script (client sided or server sided), which just prints the name of the browser. Because not everyone has fast internet, the script has to be as short as possible.

# Rules

1. You have to print the name of the browser loading the page without any version number etc. to STDOUT or equivalent. Leading or trailing spaces are allowed.
2. You can assume the browser is Firefox, Chrome, Edge, Safari or Opera, so only those browsers will be tested. Don't print "Chromium", this does NOT count.
3. The script may be server sided with CGI (in any language), ruby on rails, jsp and similar. Client sided scripts may be written in JavaScript, TypeScript, and any other versions of ECMAScript, it just has to run in all five browsers.
4. If your language has no offline interpreter for CGI, assume it's saved in /usr/bin/i, the shebang at the beginning does not add bytes to the count.
5. this is a , so the shortest answer wins!

# Meta

• Does this question have important loopholes?
• Is there any language which cannot be programmed in? (CGI should work always, even Java or bf could be done with a shebang, lol)
• About the "Is there any language which cannot be programmed in?" --- that's actually a very good question. Let me try. – user202729 Dec 10 '17 at 14:37
• About the background... "fast internet" doesn't matter if the script is server-side. – user202729 Dec 10 '17 at 14:38
• @user202729 This is a joke, lol, just like those other joke reasons the program has to be short. Is it a good question though? – Mega Man Dec 10 '17 at 14:49
• Probably. But the fact is, not everyone is familiar with writing a server, so you may not get a lot of answers. – user202729 Dec 11 '17 at 6:03

# Coin Game: Shoot It Out!

In Shoot It Out, we will play with coins on a table.

# Basic Idea

Shoot It Out is a 6-player game. The players will be split into two teams of 3 players, one offensive, and one defensive.

Initially, every player has a coin on the table. Additionally, there is a target coin. Players take turns to shoot their coin. However, the shots will not be very accurate.

The offensive team will try to shoot the target coin out of the table, while the defensive team tries to prevent the target coin from being shot out. You should make a bot that can play as both offensive and defensive team, and try to maximize the winning rate.

# Rules

### Playing Order

• Every player has its player ID. ID 1, 3, 5 are on the offensive team; ID 0, 2, 4 are on the defensive team.

• Playing order is the same as ID. After the turn of ID 5 is ID 0's turn. If a player is removed, simply go to the next player.

• When it is a player's turn, they will shoot their coin once. After every coin stopped moving, the turn ends.

### Elimination in a Game

• If a player shoots their own coin out of the table, the player is removed from the game. If the target coin moves out of the table in the same turn, it will be placed back to the previous position.

• If a player shoots another player's coin out of the table, both players are removed from the game.

(Note that these two can occur in the same turn.)

### Winning Conditions

• Defensive team wins when both conditions below are satisfied:

• The target coin is in the table area.
• All players on the offensive team are removed, or 18 turns have been played (skipped turn is not counted).
• Offensive team wins when one of the conditions below are satisfied:

• The target coin is out of the table area.
• All players on the defensive team are removed.
• There is one exception: if all players are removed at the end of a turn, the defensive team wins.

### Table Settings / Parameters

• The table is a circular area of radius 100 cm. The radius of every coin is 1 cm. A coin is out of table iff its center is out of the circular area.

• For convenience, we set the coordinate of the center of the table to (0, 0), and denote the position of a coin by the coordinate of its center.

• The coefficient of restitution between coins is 0.9.

• The maximum intended speed of a shot is 240 cm/s.

• When a coin is moving, it will have an acceleration of -240 cm/s^2 (due to friction).

• When the game starts, the target coin is located at (0, 0), while the coin of ID x is located at (2.5 cos(f(x)*pi/3), 2.5 sin(f(x)*pi/3)). The values of f(x) are:

x f(x)
0 0
1 3
2 1
3 4
4 5
5 2


Here is a picture of initial positions.

# Errors

Each player's shot has two parameters: angle and initial speed. Programs will output the two parameters representing its intended shot. However, the actual shot won't be the same of what is intended: errors will be added into parameters.

Specifically, if the angle (in radians) and initial speed (in cm/s) of the intended shot are θ, v, then:

• The actual angle will be θ+R(pi/70).

• The actual initial speed will be v*exp(R(1/12)). (Note that it may exceed the maximum speed.)

Where R(x) is a random variable with Gaussian distribution of standard deviation x and average 0.

# Scoring

Since only 6 players can play in one game, the controller will randomly assign players to a game.

Lots of games will be held until each player has played both defensive and offensive team in more than 10000 games.

The final score of your program will be y/x+z/(1-x), where:

• x is the average winning rate of offensive team in all games.

• y is the winning rate of your program when on the offensive team.

• z is the winning rate of your program when on the defensive team.

# Input / Output

Your program will be run once per game. It should receive inputs from stdin and output to stdout.

At the beginning of a game, it will receive a line of input a, where a is the player ID (thus indicating which team you should play in).

When a turn starts, you will receive input like this:

3
0 3.798 3.332
1 12.656 3.666
3 18.652 7.913
4 8.004 7.132
6 -3.187 -9.553


The first line indicates the player of this turn. Each remaining line contains information of a coin: The first number is the player ID of the coin's owner (or 6 if it is the target coin). The remaining two numbers are x and y coordinates of the center of the coin.

If it is your turn, you should output two numbers, separated by a newline or space, representing the intended angle (in radians, 0 is +x, pi/2 is +y) and initial speed (in cm/s). You should flush stdout after output. (If it is not your turn, you should not output anything.)

You needn't to handle the termination of your program. When the game ends (or you are removed), the controller will send SIGKILL to your program to terminate it.

# Specifications

• Your program should be able to be compiled into an executable, or be executed like an executable (for example, add shebang if you use interpreted languages). If your program need to be compiled to run, you should also specify how to compile your program.

• Your program should not access files, or anything that stores information between games.

• Your program should be deterministic. You can use random number generators, but you should make sure that the generator you use is based on a fixed seed, and will not use random devices (such as RDRAND or /dev/random), system time, etc.

• All "random" numbers (while generating errors and assigning players) used by the controller are generated in a deterministic way. However, your program should not take any advantage of it.

• The total response time of your program in a game should not exceed 0.1 second.

• You can submit multiple programs, but they should not team up against the others.

# Controller & Sample Bots

(Still working on them...)

# The 64 | 64 Color Selector

All colour selector tools suck. Let us make another one that sucks also, but in a different way.

• two squares, of 64x64 "pixels" each one. Pixels do not need to be strictly pixels, but anything where the user can have 64 possible selections in each direction, vertical or horizontal, representing all the possible different RGB colors.

• a third element of the interface that will represent the color selected with user has selected based picked on squares.

• a fourth element which represents the 6 digit hexadecimal RGB hex-code (example: #FFBF32). You can divide it in three elements, but you have to make clear which component is what from RGB.

• a fifth element which represent the decimal RGB code (example RGB(127,33,43)). You can also divide it in three elements, but you have to make clear which component is what from RGB.

When the two squares are at the top left corner, selected color must be RGB(0,0,0); and when the two squares at the bottom right corner must be RGB(255,255,255).

You must have the the pixels in the square sorted by increasing order; I don't care what direction, vertical or horizontal, you choose for increasing one-by-one, but the two squares must have the same pattern.

When the user picks a "pixel" in the first square, the colours of the second must be updated and reflect all possible values under the second pixel.

When the user picks a "pixel" in the second square, 3rd, 4th and 5th elements must be updated to reflect new color selection.

• Your specifications seem a bit too loosely-defined to me, though unfortunately I don't have any suggestions for improvement at the current moment – HyperNeutrino Dec 11 '17 at 15:32
• I assume that your first requirement should state 'Pixels do not need to be strictly pixels...' – brhfl Dec 11 '17 at 18:34
• @brhfl Yes. Thanks. Fixed. – sergiol Dec 11 '17 at 18:50
• Is there any requirement on the ordering of selections in the first two elements, or is it fine as long as every RGB color could be expressed as a coordinate pair on the first element plus a coordinate pair on the second element? – Kamil Drakari Dec 11 '17 at 19:21
• @KamilDrakari: Yes. Thanks. Updated. – sergiol Dec 12 '17 at 11:09
• @HyperNeutrino: better now? – sergiol Dec 12 '17 at 11:10
• It looks good, you may want to point out that you want a 1:1 color conversion. I was looking at it and I think that's what you want since 64^4 = 256^3. – Neil Dec 13 '17 at 4:03
• "You must have the the pixels in the square sorted by increasing order" is nonsense unless you address the issue that HyperNeutrino raised about the specifications not truly being specifications. – Peter Taylor Dec 13 '17 at 9:41

## Sheet music exact transposition

As we're limited to ASCII here, I'll just refer to the notes by name A-G, although obviously real sheet music has a range of about an octave and a half even before you take ledger lines into account.

Notes are written on sheet music in two ways. Most of the time, notes have their own position on the stave, but no accidental is indicated; this means that the note gains the accidental corresponding to the key signature. For example, the scale of A is ABCDEFGA; the C, F and G are played sharp because of the key signature. These notes are easy to transpose, because you simply need to shift them by the appropriate number of note names; the accidental is taken care of by the key signature. For example, the scale of A is simply ABCDEFGA; if you transpose down two notes, you get the scale of F, FGABCDEF; in this case the C, F and G become natural and the B becomes flat, but there's nothing extra for you to do here because the key signature takes care of it. This works even if the key itself contains accidentals; transposing the scale DEFGABCD from D♭ to D♯ simply results in DEFGABCD again.

For notes that are not available in the key signature, an accidental needs to be applied. This is either the ♮, indicating that an accidental in the key signature (or previously used for that note, but that's not relevant here) should be ignored, or one or more of either ♭ or ♯, indicating how many semitones the note should be adjusted. (Although an accidental exists for ♯♯, we will ignore this to simplify the challenge).

You can't just throw accidentals around, otherwise you end up with the scale of E written as F♭E♯♯A♭A♮C♭B♯♯F♭♭E which is ridiculous. It is therefore essential when you transpose a note that the note name is transposed identically no matter how many accidentals the note may have.

However, there is a caveat: the named intervals are not regular. The interval between B and C and that between E and F are just one semitone, while the other intervals are two. This means that you might have to adjust the accidental if the number of semitones between your original and transposed note differ from that of the original and transposed key. The number of accidentals in the key must also be taken into account, of course.

Take the example of transposing the note D from the key of A to the key of F. Because F is five notes above A, the note D transposes to the note B; the key signature takes care of making the B flat. However, if we were transposing the note D♯, we would have to calculate that the final note needs to be B♮ in order for the number of semitones to be correct (F - A = 8, B♮ - D♯ = 9 - 1 = 8; the ♯ increase the number of semitones while the ♭ decreases it, but of course subtracting a ♯ results in a decrease too).

Conveniently, the output has an accidental of some sort (including ♮) if and only if the input note does, which should simplify the challenge.

Your challenge is to write a program which will accept three notes as arguments. Two of the notes will represent the original and transposition key of the transposition, while one of the notes will represent the note to be transposed. You must then output the result of the transposition. Examples:

Note    From    To      Result
G♮      A♭      B♭      A♮ (not A)
C♯      B       D       E♮ (not E)
B       F       D       G
B♭      C       G       F♮
B       B       A       A
B       E       B       F (not F♯)
D♭      E       G♭      F♭♭ (not E♭ or D♯)
G♭      E       G       B♭♭ (not A or A♮)
E♭      G♭      C♯      A♮ (not A)
C       F       D       A
G♯      C       G       D♯ (not E♭)


This is , so the shortest program wins. However, since there does not appear to be an ASCII character that can represent ♮, I will allow any of the three UTF-8 characters ♭, ♮ or ♯ to count as a single byte.

# Simultaneous Selection

In the game Risk of Rain there is a game mode where you can select which items you want out of dropped boxes. The only problem is that when you open two boxes at the same time your movements in one box effect your movements in another. Now this can be a problem since you may want to retrieve a particular item from one of the boxes. However there is a solution.

Since the boxes have different shapes and you are not permitted to move your cursor outside of the box you can desynchronize the two cursors.

For example if we have the two boxes

S.F...    S.....
......    ...F..
....      .....


Where F is the goal and S is the starting location, we can get the cursor to the goal by moving the cursor

Right 4 times
Down 3 times
Up 1 time
Left 1 time


Still working on it ...

## Input

As input you will receive two 2 dimensional boolean containers, representing the shapes of the boxes. In these boolean arrays true means that square exists in the box false means square does not exist. You may assume that your input will be padded with false values such that no true values touches the edge of the array.

You will also receive two coordinate pairs representing the start and end locations.

## Output

You should output a ordered container of "moves" such that when performed on both boxes the cursor will arrive at the end point. A "move" may be one of 4 chosen values each representing one of the 4 cardinal directions. For example you might choose: [N,S,E,W], [1,2,3,4] or [(1,0),(0,1),(-1,0),(0,-1)]. Your program must be self consistent in these values across multiple sessions.

If no solution is possible for the given boxes you must output a value that is distinct from any possible sequence of moves, for example a list containing a 5th value that cannot represent a move, or a non list item.

Still working on it ...

• How do we take input? As two separate strings or can it be arrays, etc... – Neil Dec 17 '17 at 5:20
• @Neil Its going to be boolean arrays, true means square exists false means square does not exist, and coordinates for start and end locations. I've been a little lazy in finishing this question. – Wheat Wizard Dec 17 '17 at 5:22

# Demolish a string! v2

A modified version of Demolish a String; since the original question involved randomness, the challenge was too complex and there were not many answers. This challenge removes the criterion and allows flexibility by the answerer, which should invite responses in languages without randomness built-ins.

# Challenge

Given a string input, output the demolished version of it.

# The Process

P
r      Pr       r
o       o       o
g       g       g
r       r       r      rogr         r
a  ->   a  ->   a  ->     a  ->     a  ->           ->           ->           ->           ->
m       m       m         m         m
m       m       m         m         m         mmar         m
i       i       i         i         i         i            i           mi           m
n       n       n         n        gn        gn           gn           gn           gni         mgni
g       g      Pg        Pg      roPg      roPg         roPgmar      roPgmar      roPgmar      roPgmar


Place the string vertically. Repeat the following steps until they are impossible:

1. Take any column of characters that can be demolished (explained below)
2. Select some integer between 1 and (height of the column of characters) - 1 and some direction (left or right).
3. Rotate that number of characters in that direction (only if those spaces are unoccupied; if not, go back to step 3).
4. Let those characters fall due to gravity.

At the end, the output should be a string whose heights of consecutive columns differ by at most one.

Note: the choice of integers and the direction is up to the answerer

If there are space characters in the input, demolish those first, all at once.

C
o

d
e  ->     oC  ->         ->  ...
de
G        G          G
o        o          o
l        l          l
f        f        defoC


## Rules

• Standard loopholes are forbidden.
• Trailing and leading newlines are allowed.
• Your program may either print or return a string/equivalent.
• Please explain the demolition algorithm (# of characters and direction) in your answer.

## Some test cases to try

A
Programming
Code Golf
The quick brown fox jumps over the lazy dog


This is , so the submissions with the smallest byte counts in their languages win!

# Program an Uncircularness Score

derivative of this challenge

## Meta:

This is just a rough idea for a slightly different challenge. I have no idea how successfull it would be in the current state, so feel free to share your opinions and suggestions.

Your task is to program a mathematical function s, that takes a finite set A of points in the 2D plane, and outputs an uncircularity score s(A) that satisfies following properties:

1. positive definiteness: If there is a circle or a straight line that contains all points of A, then s(A) = 0. Otherwise s(A) > 0
2. It is surjective to the nonnegative real numbers, that means for every nonnegative real number r there is a finite subset A of the plane such that s(A) = r.

### Scoring

You get one point for every of the following properties that your function (provably) has.

• Translation Invariance: s is translation invariant if s(A) = s(A + v) for every vector v and for all A.
• Scale Invariance: s is scale invariant, if s(A) = s(A * t) for every t≠0 and for all A.
• Monotony: s is monotonous if s(A) ≤ s(B) for all A,B where A ⊆ B.
• Circle Inversion Invariance: s is circle inversion invariant, if s(A) = s(f(A)) for all A with 0 ∉ A, where f(x,y) = (x/(x^2+y^2), y/(x^2+y^2)) is the circle inversion. (Here (x,y) represent the cartesian coordinates of a point in the plane.)
• Triangle inequality: s satisfies the "triangle inequality" if s(A ∩ B) ≤ s(A) + s(B) for all A,B. (This is implied by Monotony.)
• Reverse triangle inequality: s satisfies the "reverse triangle inequality" if s(A) + s(B) ≤ s(A ∪ B) for all A,B.
• Continuity. s is said to be continuous if the function f(p) := s(A ∪ {p}) (mapping the a point p to a real number) is continuous using the standard absolute value on the real numbers, and the standard euclidean norm on the points of the plane.
• More to come...
• Perhaps you should change the "non-negative real number" to "non-negative rational number" or "non-negative algebraic number" in part 2. If these functions are being produced by code it seems quite unreasonable to expect numbers that cannot be represented in computer memory to be output. – Wheat Wizard Aug 26 '17 at 17:13
• @WheatWizard That's an interesting thought. Personally I quite like the idea of these properties working over the real numbers in theory, and the code implementing it to a desired accuracy of approximation, but I'm not sure if that's easier or harder to score/judge valid. – trichoplax Aug 26 '17 at 17:18
• @trichoplax I will admit I am opposed to any "code must work in theory" rules in challenges. However any code that works in theory must also work on the reals or algebraics which allows us to have code that works not just in theory. – Wheat Wizard Aug 26 '17 at 17:22
• @WheatWizard I agree that asking for testable solutions is much more satisfactory than "works in theory". – trichoplax Aug 26 '17 at 17:30
• I guess "provably" needs to be defined in the context of the challenge. Will there be a defined method of testing or does this require a mathematical proof (in which case it leans more towards puzzling's scope). – trichoplax Aug 26 '17 at 17:32
• @WheatWizard That is a good point that I did not think about. But I'd allow for limited precision implementations (i.e. floating point), because everything else would probably almost make the challenge impossible. – flawr Aug 26 '17 at 18:58
• @trichoplax You'd need a lot of testcases to be convincing, but I think the participants should be able (they don't have to write down proofs) to provide good arguments for why a certain property is satisfied, just as we require any program to be actually doing what it is supposed to do. (we don't require proof of correctness either) – flawr Aug 26 '17 at 19:01
• I think trichoplax makes a good point. I'm not sure how much this is really about code. It might be a better idea to post this on puzzling as a math puzzle where you need only define a function rather than some code. – Wheat Wizard Aug 26 '17 at 19:03
• @WheatWizard Thanks. I think this could be made into a code-challenge (or code-golf), but it could also be made into a mathematical function challenge like you suggest. I can't guess which would be more interesting (or easier to define objectively) though. I suppose there's nothing stopping it being two challenges, one on each site... – trichoplax Aug 26 '17 at 20:18
• Translation and scale invariance are easily added: translate to put the centroid at the origin and then if there's more than two points scale so that the furthest point from the origin is at distance 1 from the origin; then apply the original function. It might be possible to deliberately construct a noncircularity function such that this would destroy the surjectivity, but in practice I don't think the question would be harmed by assuming that all answers will be affine-invariant and simplifying the scoring system appropriately. – Peter Taylor Aug 27 '17 at 17:09

# Squeeze Out a Square Quine

...the bigger the better.

Write a full program that is a proper quine (a piece of code that outputs itself without reading its source code). To make things more difficult, your code (and obviously the output) has to be in a form of a square, meaning that your code must consist of n lines of length n (not counting the newline to the line length).

### Scoring

Your answer's score will be n, the side length of the square. The largest square quine wins. To avoid answers being padded to create arbitrarily large squares, your code must fail to be a proper quine if any single non-newline character is replaced by some other character that appears in the code. There must be, at minimum, two different non-newline characters in the code.

For example, if your code was...

abc
def
ghi


...and would output itself, your answer would be valid and its score would be 3.

A single trailing newline in the output is allowed.

• Replace single character at one places or multiple characters at multiple places? – user202729 Dec 27 '17 at 3:27
• @user202729 I was thinking of single character at one place, but I'm not sure if it's sufficient. – Steadybox Dec 27 '17 at 3:31
• If it's a quine then surely it should be a trailing newline in the code – Jo King Dec 27 '17 at 10:38
• In that case it should be "the source code and the output may differ at the trailing newline". Also, if the restriction is "multiple character at multiple places" then it would be near impossible, because it's likely that there are multiple valid programs for each square size. – user202729 Dec 29 '17 at 6:13
• I like the challenge but at a certain size, checking a solution for its validity will be impossible. What if someone posts a solution and failed to notice some weird replacement that would render that submission invalid? – ბიმო Dec 30 '17 at 14:13
• @BruceForte Yeah, it's pretty problematic a challenge. I'm not sure what to do with it. Perhaps it would work better as code-golf. – Steadybox Jan 3 '18 at 6:00

# Shortest Path Distance

Uh oh! You want to get to the point (10,10) from the origin, but there are a whole bunch of boxes in the way! What is the length of the shortest path which avoids all of them?

## Input

Your program should take a set of rectangles, defined by the coordinates of two opposite corners, as input; the format is up to you.

For example, a possible input might look like

[[(1,3), (5,2)], [(5,4), (7,5)]]


But you could also take it as

[(1,3), (5,2)]
[(5,4), (7,5)]


Or anything else, as long as it allows for unambiguous input.

These inputs would define the rectangles shown below:

You can assume that all rectangles will have integer coordinates with x,y between 1 and 9 inclusive, which guarantees a possible path. You can also assume that no rectangles intersect in any way (that means no shared edges or vertexes).

## Output

Your program/function must return the value of the shortest path from the origin to (10,10), have the absolute error at most 10-2 and measured using the euclidean metric.

In the example given above, 14.564 and 14.56 would be accepted, while 14.55 and 14.57 would not.

## Example I/O

[[(1,3), (5,2)], [(5,4), (7,5)]] -> 11.40
[] -> 14.14
[[(1,1), (2,9)], [(9,2), (3,1)]] -> 14.28
[[(2,2), (1,1)], [(9,3), (8,5)], [(1,9), (2,8)]] -> 14.28 (Note: rounded up)
[[(9,1), (1,9)]] -> 18.11


## Other Rules

• The taxicab (Manhattan) distance is always 20. I don't know Taxi PL, but I suppose it is not too hard to write. – user202729 Nov 15 '17 at 4:58
• @user202729 Not true in the case that backtracking is required. – Esolanging Fruit Nov 15 '17 at 5:30
• Using taxicab distance instead of manhattan distance makes the challenge slightly easier and more accessible to languages that can't handle floating-point well. – Esolanging Fruit Nov 15 '17 at 5:31
• @Challenger5 Why does output 20 require backtracking??? – user202729 Nov 15 '17 at 9:18
• @user202729 If backtracking is required (e.g. the blocks form a spiral shape), then the taxicab distance will be >20. – Esolanging Fruit Nov 15 '17 at 16:56
• @Challenger5 No, all rectangles will have integer coordinates with x,y between 1 and 9 , which means that you can always move (0, 0) → (0, 10) → (10, 10), which have taxicab distance = 20. – user202729 Nov 16 '17 at 1:13
• Ready for posting to main? – user202729 Jan 7 '18 at 13:22
• Alternatively, you could ask not for the length of the shortest path but for the actual path! – flawr Jan 8 '18 at 13:21
• @flawr ... Isn't that harder? I don't know... – user202729 Jan 10 '18 at 10:50
• @user202729 How else would you calculate the length of a shortest path if not by explicitly finding a shortest path? – flawr Jan 10 '18 at 10:53
• What if we have two rectangles that touch eachother but do not share edges or vertices, like [(0,0),(2,1)] and [(1,1),(3,2)]? Also: Can we e.g. assume a certain representation of the rectangles (i.e. always first the top left vertex, then the bottom right)? – flawr Jan 10 '18 at 10:56
• @flawr Unfortunately, it seems that the OP abandoned this... Also, Dijkstra algorithm. (it calculates the shortest distance from source to all points, so by triangle inequality you can deduce the path, but it definitely takes more code than just outputting the distance) – user202729 Jan 10 '18 at 11:00

# Easy Incenter

The incenter of a triangle is the intersection of the triangle's angle bisectors. This may sound complicated, but the coordinate formula for incenter is somewhat simple (reference). The specifics of the formula do not matter much for this challenge.

The formula requires lengths of sides, so it can be very messy for most triangles with integer coordinates because lengths of sides tend to be square roots. For example, the incenter of the triangle with vertices (0,1), (2,3), and (1,5) is ((2*sqrt(17)+2*sqrt(2))/3,(sqrt(5)+3*sqrt(17)+10*sqrt(2))/3).

A triangle with integer coordinates has an incenter with rational coordinates in a few cases. One of these cases is when the side lengths are all integers.

# Challenge

Given a positive integer input n, your program may either:

• output the n-th ordered pair of points A,B which meet the "easy incenter" condition.
• output the first n ordered pairs of points A,B which meet the "easy incenter" condition.

where the "easy incenter" conditition (sufficient, but may not necessary (I(user202729) didn't try to prove it), for the incenter of the triangle OAB to have rational coordinates) is:

• point A meets x>y>0.
• point B meets y>x>0
• points A and B have integer coordinates.
• If O is the origin, the distances OA, OB, and AB are integers.

The pairs of points may be generated in any order.

# Example

The points B(24, 7) and A(12,16) work because:

• point A meets x>y>0 because 24>7>0
• point B meets y>x>0 because 16>12>0
• points A and B have integer coordinates
• OA = 20, OB = 25, and AB = 15, so the three distances are integers.

### Note

Not all solutions yield right triangles OAB. One example is A(32, 24), B(27, 36).

Not all solutions have A and B on the same horizontal/vertical line. One counter-example is B(12, 16), A(24, 7)

# Input/Output

Input and Output is flexible as usual.

The input is a non-negative integern.

The output is either

• a representation of a list of the first n pairs of points
• a representation of the n-th pair of points

The ordering based on n may be done in any manner, as long as it outputs all possible points "eventually" given "infinite" time.

# Example Output:

Given an input n=10, a program may output

(15, 8),(6, 8)
(8, 6),(8, 15)
(16, 12),(5, 12)
(12, 5),(12, 16)
(35, 12),(5, 12)
(12, 5),(12, 35)
(16, 12),(7, 24)
(24, 7),(12, 16)
(16, 12),(9, 12)
(12, 9),(12, 16)


# Sandbox

• Is the problem statement clear?
• Does the ordering flexibility make sense to readers?
• ... each point may only be generated once? Can you allow output infinite sequence? – user202729 Jan 10 '18 at 11:26
• That is, if there are two pairs (A,B) and (A',B') have the same incenter (with O), should they appear in the sequence once or twice? – user202729 Jan 10 '18 at 11:27

Any comments for improvement would be appreciated.
Should I choose a harder function? (maybe "Is this binary number prime?")
Or maybe not harder, but some other decision problem suggestion?

# Majority function, a non-uniform computing challenge

Non-uniform computing is a class of computing where a different procedure can be specified for each input size of a problem. This allows discussing complexity of languages that are only straight line computations (no looping constructs), yet which are powerful enough to compute any fixed input size function a Turing machine can compute. It also allows taking advantage of algorithms that may work well if only you could tweak a parameter for each size (even if the parameter is difficult to compute) or where there are only a small number of exceptions in each input size (so checking those exceptions then using the algorithm succeeds).

# Goal:

Write a program or function which, given an input length, outputs an If-Then-Else sequence (defined below) which determines if greater than half the inputs are 1 (the majority function).

This is . Your score will be:

G20 + 4*G5 + 10*G2 + L


Where L is the size of your submission in bytes, and G20 is the length of the generated If-Then-Else sequence for size=20 (length being defined as number of If-Then-Else statements). Similarly G5 and G2 are the lengths for the generated programs for size=5 and size=2 respectively. The lowest score wins.

This is in some sense an "inception" code golf. You will be judged on the length of your program as well as the length of the programs it generates.

To prevent submissions that just loop over all possible ITE sequences till it finds the smallest one that works, entries need to provide the G20, G5, G2 values along with the code submission for it to be a valid entry. As the number of possible sequences quickly becomes infeasible to search, this should eliminate raw brute forcing.

### If-Then-Else "programs"

An If-Then-Else (ITE) statement is a logical statement of the form:

if A then B else C


The logical value of this statement is referred to as the "output", and the values A, B, and C are the "inputs" of the statement. To turn this into a formatted language, a file (or string) describing an ITE program will be a series of lines that contain:

<input_term> <space> <input_term> <space> <input_term>


Where an input_term is one of:

• '0'
• '1'
• 'I' <decimal_number>
• 'Q' <decimal_number>

The values 0 and 1 are Boolean false and true respectively. The value of I(number) is the value of the input at index 'number'; for example I3 = Input #3 (input numbering starts at zero). The value of Q(x) is the result of ITE statement number 'x' (again, numbering starts at zero).

The result of an ITE program is the output of its last statement.

### Example ITE program

Here is a simple interpreter for ITE programs, written in python: ite.py

This interpreter has some additional features like comments (start a line with #) and custom output names (start line with <name>:) which are useful when playing with some ideas by hand. If you choose to utilize those features in your generated ITE programs, that's fine, although I'm not sure how that would help. This will be considered the defacto standard for the ITE language for this competition.

Here is an example program: parity4.ite

I0 0 1
I1 Q0 I0
Q1 0 1
I2 Q2 Q1
Q3 0 1
I3 Q4 Q3


As its name suggests, this is the parity function for input size 4. It returns 1 if the 4 inputs bits have an odd number of 1s, otherwise it returns 0. Here is an example of testing it on some values.

$python ite.py parity4.ite 0110 0$ python ite.py parity4.ite 0111
1

• Welcome to PPCG, this is a great challenge! I haven't put much thought into it but what's the reason for such a high weight on G2? G2 could become a special case for some clever approaches (just a guess) in which case it would be quite a hefty penalty (or they would have to hardcode its output). – ბიმო Jan 17 '18 at 15:06
• @BMO I think the required number of statements may scale roughly proportional to the number of inputs. So I was trying to "weight" them evenly. Now that you mention it, G2=1 is possible, so maybe that is not a good one. – PPenguin Jan 17 '18 at 16:59
• I was hoping to test both a "small" input size (easy to solve by hand), "medium" input size (hopefully possible to at least follow by hand), and "large" input size (probably too big to follow by hand). I guess G2 is too small. Maybe it would be better to just check G20 and G5? – PPenguin Jan 17 '18 at 17:04
• I haven't tried it yet, so it's difficult to say but G2 is not very interesting and it has quite a significant weight. I didn't mean that you should exclude it, but maybe it's a good idea or at least change the weights - maybe using G3 would be an option as well, I think it's a good idea to use small ones that are verifiable by hand. Tbh. finding out a good weighting system is not easy, maybe others with experience could help you out there? – ბიმო Jan 17 '18 at 18:06

# Solve the Square-Sum problem

Based on these (very good) Numberphile videos:

### The Problem:

Given a list of integer numbers [1,n] where n≥15; n≠18, 19, 20, 21, 22, 24, your task is to arrange those numbers in a way such that the sum of two consecutive numbers is a square number.

Example for n=15:

Original sequence: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Square-sum of it: 8 1 15 10 6 3 13 12 4 5 11 14 2 7 9
| |  |  | | |  |  | | |  |  | | |
3² 4² 5² 4²3²4² 5² 4²3²4² 5² 4²3²4²


This problem can be solved by creating a graph of every sum of two numbers in the sequence that result in a square number:

From that graph, it's possible to find its Hamiltonian Path:

This path, if existing, is the solution to the square-sum problem.

### Rules:

---Under Construction---

### Sandbox:

• Suggestions?
• Dupe?
• Test cases are under construction
• – Mr. Xcoder Jan 12 '18 at 15:42

A word ladder is a puzzle where the aim is to create the smallest sequence of steps between two fixed words (a starting word and a target word), where each step changes one letter to produce a new word. All the intermediate words must be recognised in a dictionary (which will be supplied).

If the target word is longer than the starting word, a step may add a letter at any position instead of changing one; if it's shorter than the starting word, a step may remove a letter instead of changing one.

Examples:

HAND
BAND
BOND
FOND
FOOD
FOOT

FINGER
FINER
FINE
TINE
TONE
TOE

EYES
EYED
DYED
DEED
TEED
TEND
TENT
TENTH
TEETH


## The challenge

Write a program or function which accepts a dictionary of words and the two fixed words (i.e. a starting word and a target word), and produces an ordered list of intermediate words following the rules above. You may choose to output the starting word, the target word, both, or neither.

You may use any of the standard methods of input and output, and must not bypass the rules with any of the standard loopholes.

## Scoring

(I need some help with this part).

The score is the number of dictionary lookups your program makes during a test run (or average of several test runs, if it's not deterministic) on a set of inputs with a simple English dictionary. Q: does this test set need to be prepared and included in the question?

# Sandbox questions

I don't really want to make this a , as we'll just end up with simple brute-force algorithms; I really want to see creative use of the dictionary, either by pre-processing or perhaps by ordering candidate words.

Is there a way we can define a "dictionary lookup" and somehow separate the word generation/validation from knowledge of the fixed words, without making assumptions that the language has functions or other methods of isolating code?

Can we require the dictionary to be a separate process, and provide a reference implementation? I don't think we can, without excluding languages without reasonable inter-process communication (I'm thinking of PostScript, possibly JavaScript, and microcomputer BASIC).

• I think this could be a test-battery challenge, with both different words and different dictionaries as tests. Different dictionaries are needed to avoid languages searching in a build-in English dictionary and only validating their finds in the provided dict. – Laikoni Jan 18 '18 at 14:33
• I mentioned English because I would like entries to be able to use heuristics to choose a good way to search first - perhaps simple vowel/consonant rules, perhaps something more sophisticated (digraph tables?). Promising an arbitrary dictionary would prevent that kind of thinking, especially if there's nothing to say that "XYQQZ" won't be in it. @Laikoni, could your concern be addressed by a rule to outlaw built-in dictionaries? ("You must use only the supplied dictionary", for example) – Toby Speight Jan 18 '18 at 14:42
• I see your point and also like the idea to incentive some form of language processing. However banning built-in dictionaries comes with the general problem of banning built-ins, namely what counts as a built-in dictionary. Just from the top of my head, if the scoring is only about look-ups in a provided English dictionary and built-in dicts as well as adding a dict in to your code are a banned, how about assessing built-in texts to sample a rough dictionary? I know that some languages can asses their own documentation from within the language itself. – Laikoni Jan 18 '18 at 14:52
• Altogether, it might be a good idea to make the score a weighted combination of code length and the number of lookups. – Laikoni Jan 18 '18 at 14:53
• How would you define "dictionary lookup"? A program may "copy" the dictionary and count that as one dictionary lookup. A check whether a word is in the dictionary? /// Also for the problem of built-in dictionary the solution is really simple: scramble the letters, and use different languages, or just use a random dictionary. For example bunny with the scramble b->x, u->y, n->q, y->z may well become xyqqz, and of course it won't change the challenge. /// What if there is no solution? – user202729 Jan 20 '18 at 4:48
• The core question is essentially codegolf.stackexchange.com/q/2478/194 so as code-golf I would vote to close this as a dupe. But with the current rules (and in particular the requirement to produce the smallest sequence of steps) I'm not sure how viable the proposed scoring system is. Basically answers will have to be equivalent to A* and there aren't that many admissible heuristics. In particular, heuristics for whether something is a word or not would only meet spec if they encode the entire dictionary. – Peter Taylor Jan 20 '18 at 9:07
• Thanks @Peter and others. I didn't manage to find the code-golf version, so the link is useful. I obviously need to think a bit further about the rules and scoring (in fact, I posted to Sandbox hoping to garner further ideas). I'm starting to agree that the dictionary can be abstract if the answer is allowed to generate heuristics from it before processing inputs. If I get any better ideas, I'll come back to this and update it. – Toby Speight Jan 22 '18 at 8:47
• The obvious way to address the A* issue is to not require it to be a shortest path, but then you have to balance path length vs dictionary queries in the score, which is going to be messy. – Peter Taylor Jan 22 '18 at 18:32
• About "dictionary lookup"... check if a word in the dictionary using a black-box function seems good enough. Hopefully it won't make programs take awfully long time to run. / Restrict to a-z? Adding Unicode would be impossible to guess. – user202729 Jan 23 '18 at 7:34

### Objective

Given a 2D array (of x by x size), write a program or function to alternatively shift elements of the array along the anti-diagonals. (anti-diagonals are right to left, top to bottom). (first anti-diagonal moves down second anti-diagonal moves up with elements wrapping when they reach the end of the anti-diagonal)

### Example

a b c d
e f g h
i j k l
m n o p


Will become:

a e i g
b c j n
f m h o
d k l p


**edited for user202729 suggestion

• Should it be "antidiagonals"? – user202729 Jan 22 '18 at 13:58
• Dupe? – Peter Taylor Jan 23 '18 at 8:22
• @PeterTaylor im trying to shift the anti-diagonals not reverse them – Karan Shishoo Jan 23 '18 at 8:55
• So is the question I linked. – Peter Taylor Jan 23 '18 at 9:22
• @PeterTaylor look at the 4x4 test case and compare it with mine. I have a different result for that case. I am asking people to shift the elements along the anti diagonals, not to rotate the anti diagonals themselves. – Karan Shishoo Jan 23 '18 at 9:39
• Although the specification of this proposal is not especially clear, I think that the only difference is that the question I linked rotates all anti-diagonals in the same direction whereas this rotates them alternately in one direction and the other. – Peter Taylor Jan 23 '18 at 12:18
• @PeterTaylor i will again clarify i am not rotating them i am shifting them. for example if an anti diagonal was say - 1 2 3 4 5 6 my outcome would be: 6 1 2 3 4 5 (or 2 3 4 5 6 1 depending on which antidiagonal it was) instead of 6 5 4 3 2 1 (which is the rotation of that antidiagonal) – Karan Shishoo Jan 23 '18 at 12:27
• Shifting and rotating are different words for the same thing: the only difference is that rotating makes it clearer that it wraps round rather than losing one element from one end and introducing a new one at the other end. You're thinking of reversal. – Peter Taylor Jan 23 '18 at 12:38
• @peter Taylor your right... I goofed up while matching the arrays thanks for the catch – Karan Shishoo Jan 23 '18 at 13:03

# Shape sequence sums

### 0. DEFINITIONS

For the purposes of this challenge, a sequence refers to a list of numbers whose absolute values increment in steps of 1. A sequence begins with a value of 1, 0, or -1.
A positive sequence refers to the natural numbers: 1, 2, 3, 4, and so on.
A negative sequence refers to the additive inverses of the natural numbers: -1, -2, -3, -4, and so on.

### 1. CHALLENGE

Given an integer n, return a list of sequences such that the sum of all the numbers in the list is equal to n. Sequences must alternate in sign (see test cases). Solutions must produce the list with the fewest sequences; that is, the sign should change a minimal number of times. (Read: Don't do 1, 2, -1 over and over again.) The resulting list must be flat, not nested. The shortest working solution wins.

### 2. TEST CASES

 17: 1, 2, 3, 4, 5, 6, -1, -2, -3, 1, 2, -1
18: 1, 2, 3, 4, 5, 6, -1, -2
19: 1, 2, 3, 4, 5, 6, -1, -2, 1
21: 1, 2, 3, 4, 5, 6
-21: -1, -2, -3, -4, -5, -6
-5: -1, -2, -3, 1
0: 0 or [] (null set)


You may choose to begin each sequence with 0 instead of 1 or -1. However, if you do this, every sequence must begin with a zero, not just the positives, the negatives, the first sequence, or any other strict subset. This also means that input 0 requires a list containing a single 0.

 17: 0, 1, 2, 3, 4, 5, 6, 0, -1, -2, -3, 0, 1, 2, 0, -1
0: 0

• Is there any requirement that answers provide an output with the smallest number of sequences, the fewest total numbers, or just any list of numbers which can be partitioned into alternating positive and negative sequences? I might recommend some restriction else repeating 1, 2, -1 will eventually reach any number – Kamil Drakari Jan 23 '18 at 20:48
• Can the output for 0 be [], ie. is the empty sequence a sequence? – ბიმო Jan 23 '18 at 20:49
• @Kamil & BMO: Thanks, I've updated to address these. Also added requirement that list be flat. – Joe Jan 23 '18 at 21:49
• Why do you require flatness? – CalculatorFeline Jan 24 '18 at 1:07
• Idk, I just feel like it. I like flat lists :P – Joe Jan 24 '18 at 2:32
• Title suggestion: "Shape sequence sums" – Esolanging Fruit Jan 24 '18 at 5:31
• 1. I think that this question would be a lot simpler to understand if it were rewritten in terms of triangle numbers rather than sequences. 2. Most of the test cases are wrong. Every integer can be produced with just two sequences. – Peter Taylor Jan 24 '18 at 12:57

# Different tasks, same characters, level 2

In this challenge, you need to solve 3 different tasks using the same set of characters. You can rearrange the characters, but you can't add or remove characters.

The winner will be the submission that solves all tasks using the smallest number of characters. All tasks must be solved in the same language.

Note that it's the smallest number of characters, not the smallest number of unique characters.

Twist: If one or more characters can be removed from a script without breaking it, then your submission is disqualified. This means that comments are out of the picture, as well as long variable names to get the character counts to match up.

You do not have to prove that it's impossible to remove characters and still have a functioning script, but you should try to make it impossible. If nobody bothers to look at it, then your submission is valid. If nobody sees a way to remove one or more characters, then your submission is valid. If however, someone looks at your post and sees something that can be removed without breaking it, then your submission is invalid.

So, what do you think about the idea?

• I don't think the twist is going to be easily enforceable. For any program longer than a dozen bytes the computation time on checking that it fits this requirement becomes immense. – Wheat Wizard Nov 28 '17 at 22:53
• I think I'll let the burden of disproof (is that a thing?) lie with the viewers. Those posting answers will do their best to make it impossible to remove fluff without breaking it. If someone finds a way to do it, then the submission is invalid. If every character is there for a reason (it has a function) then it should be fairly hard to find something that can be removed that OP wouldn't already know of (for instance reversing something twice). It's not CNR, but if people find ways to golf an answer without breaking it, then it's invalid. – Stewie Griffin Nov 29 '17 at 7:22
• If nobody bothers to look at it, then your submission is valid. If nobody sees a way to remove one or more characters, then your submission is valid. If however, someone looks at your post and sees something that can be removed without breaking it, then you submission is invalid. – Stewie Griffin Nov 29 '17 at 7:27
• I think that would be generally effective; in practical languages with longer code, fluff is easier to spot in the syntax, and in recreational golfing languages the shorter code will be easier to manually check. – FlipTack Nov 29 '17 at 8:17
• So if there exists a subsequence of the original program that also do the task the original program does (not necessarily equivalent), and there is someone point it out, the submission is invalid? – user202729 Nov 29 '17 at 13:32
• Do the removed characters need to be contiguous? – AdmBorkBork Nov 29 '17 at 14:41
• @AdmBorkBork no. It's to avoid stuff like unnecessary long variable names etc. And then you'd need to remove character multiple places... – Stewie Griffin Nov 29 '17 at 15:53
• Cool! I've had an idea like this, but using different languages to solve the same task (with the exact same twist) – Sanchises Jan 25 '18 at 21:15
• @Sanchises you may go ahead and post it if you'd like! Either this version or a polyglot version. :) Interested? – Stewie Griffin Jan 25 '18 at 21:35
• Oh you may have this one. I'm still stuck on thinking of one task.... – Sanchises Jan 25 '18 at 21:36
• You have a very nice track record when it comes to challenges, so I'd like to see it :) – Stewie Griffin Jan 25 '18 at 21:37

# What's in an ISBN?

Given an ISBN-10 code starting with 0 or 1, extract the registration group, registrant, publication, and checksum numbers.

## Background

We've talked about International Standard Book Numbers before, including converting them and calculating their checksums. Now let's talk about parsing their data.

An ISBN-10 code has four parts; in order from left to right: registration group, registrant, publication, and checksum. We're only going to consider registration group numbers 0 and 1, which represent English-speaking areas. Take a look at these two ISBN-10 codes, shown with their parts separated:

• 0-307-45547-5 – This book, from registration group 0, is printed by publishing giant Penguin Random House. Penguin prints thousands of books, so it's assigned ISBN blocks with few digits for registrar (307 here), leaving many digits for publication (45547). The checksum is 5.

• 1-940696-27-5 – This book, from registration group 1, is printed by indie poetry press Wave Books, which prints just a few books each year, so its ISBN blocks have many digits for registrant (940696 here) and just a few for publication number (27). The checksum is also 5.

## Specification

Write a program or function that takes a non-separated ISBN-10 code and return its four parts as distinct values.

ISBN-10 codes in registration groups 0 and 1 are separated according to the following scheme, where xx… is registrant number and y is checksum.

From            to                 From            to
-------------   -------------      -------------   -------------
0-00-xxxxxx-y … 0-19-xxxxxx-y      1-00-xxxxxx-y … 1-09-xxxxxx-y
0-200-xxxxx-y … 0-699-xxxxx-y      1-100-xxxxx-y … 1-399-xxxxx-y
0-7000-xxxx-y … 0-8499-xxxx-y      1-4000-xxxx-y … 1-5499-xxxx-y
0-85000-xxx-y … 0-89999-xxx-y      1-55000-xxx-y … 1-86979-xxx-y
0-900000-xx-y … 0-949999-xx-y      1-869800-xx-y … 1-998999-xx-y
0-9500000-x-y … 0-9999999-x-y      1-9990000-x-y … 1-9999999-x-y


For example, 0307455475 lies in the range 0-200-xxxxx-y … 0-699-xxxxx-y, so we know it has three digits for registrant and five for publication and the program, given this input, should return 0, 307, 45547, and 5.

Likewise, 1940696275 is in the range 1-869800-xx-y … 1-998999-xx-y, so the program should return 1, 940696, 27, and 5.

### Input

• Input may be in any convenient format, e.g. a string, list of characters, or list of numbers.
• The input must be 10 or fewer characters or numbers, plus an optional trailing newline. Leading zeroes are optional.
• In ISBN-10 codes the checksum 10 is represented with an X. If your program takes input as a list of numbers, the number 10 may be used. If it takes input as a string or list of characters, a single non-digit character of your choosing (e.g. X or x) must be used.
• Otherwise, standard input rules apply.

### Output

• Output may be in any convenient format, as long as each part is easily distinguishable from the next, e.g. a delimited string, a list of four numbers, or a list of four lists of numbers.
• If the checksum is 10, it may be 10 (as a number or string) or a single non-digit character of your choosing. For example, both 0 8044 2957 X and 0 8044 2957 10 are valid.
• Otherwise, standard output rules apply.

## Winning

This is ; the solution with the fewest bytes wins.

Standard loopholes are forbidden.

## Test cases

Input       Output
0000000000  0-00-000000-0
0144751605  0-14-475160-5
0393765621  0-393-76562-1
0763320041  0-7633-2004-1
0859056018  0-85905-601-8
0906789222  0-906789-22-2
0958171947  0-9581719-4-7
0999999999  0-9999999-9-9
099999999X  0-9999999-9-X
1000000000  1-00-000000-0
1080925818  1-08-092581-8
1149092167  1-149-09216-7
1457721261  1-4577-2126-1
1578424693  1-57842-469-3
1973088617  1-973088-61-7
1999973361  1-9999733-6-1
1999999999  1-9999999-9-9
199999999X  1-9999999-9-X


## Sandbox questions

1. What are good tags for this?

2. Is the description of the separation scheme clear?

3. Any test cases missing (or wrong)?

Programs are competing in a game of "basketball". They are given a 5x6 (Minus the top center character) grid on which to put either /, \, or ^. The programs can place two symbols every tick on the grid. If the programs try and place a symbol at the same place at the same time, neither symbol is placed.

On the first tick, a 'ball', o, is spawned at (3,6) on the grid. The ball falls by one character every tick. If the ball encounters a \ while falling, it moves to the right. If it encounters a /, it moves to the left. If the ball hits a ^, it moves back to the top of the grid at that x position. The ball only moves once every tick, and does not effect the map on it's own.

When the ball is on the bottom row, if it's on the left, it gives a point to the first program and respawns, if it's on the right, it gives a point to the second program and respawns. If it's in the center, it simply respawns without giving points to anyone.

If the ball tries to move off the map, it simply stays in place.

The grid is rotated when transfered to the contending programs so that it always appears that the left is that program's goal.

## Program I/O

Programs use Standard Input and Standard Output to communicate to the contest framework. The program is sent a 30 byte buffer containing a map and a 2 byte buffer containing the position of the ball.

The program must send two 3 byte buffers in response with the character to put on the map, it's x position, and it's y position.

The framework gives each program 5 seconds to perform there action. If they fail to be within this 5 second window three times, they automatically lose to prevent the round from going on too long.

## Competition

Programs will compete in pairs of two. The winner of each pair will move on to the next round, and be paired up with another winner.

Sandbox questions

1. How can this be improved?

2. What actions should I take to make sure rounds are fair?

3. How should invalid data be handled when sent to the framework?

• The execution of time is unclear here: What happens if a ball falls down on the following line: \\\\\  ? Does it move all the way across in a single move or does each step take a single move? Does the ball remove symbols that it hit? – Nathan Merrill Feb 5 '18 at 21:02
• I think your IO is a bit cumbersome: Simply feed them all of the info at the start, and wait for them to output the two new symbols. – Nathan Merrill Feb 5 '18 at 21:05
• I'll clear that up. The ball will move across one step at a time. Symbols are not removed, to prevent it from being the same thing each round. – moonheart08 Feb 5 '18 at 21:06
• More questions: What happens if both programs place on the same square? If the ball is currently on a \  and I place a / on the square it currently is on, which action does it follow? – Nathan Merrill Feb 5 '18 at 21:10
• Cleared that up as well. The write is canceled out. In terms of the ball, it follows the new symbol the next tick. – moonheart08 Feb 5 '18 at 21:14
• Just making sure I understand: If two players write on the same square, nothing happens. If a ball is on (3,6) and the square is a / , but I write a \ , the ball won't be affected, because my symbol only affects things the next tick. – Nathan Merrill Feb 5 '18 at 21:17
• Finally, (and the issue I don't see easily resolved): I feel like this has a really small search space, and very little room for different strategies. Technically, there are 7830 moves a turn, but most of the squares and moves are irrelevant and can be ignored. In essence, this game feels like a tug-of-war where both sides are equally as strong. Any push to the right is easily countered by a push to the left. – Nathan Merrill Feb 5 '18 at 21:21
• Precisely. The programs make their changes after the ball has made it's move for that tick. – moonheart08 Feb 5 '18 at 21:22
• @NathanMerrill I've been thinking that too. The grid space can be fairly easily expanded. The game is a game of "skill" between the two programs. They (The programmers) have to try and be inventive to force intresting situations and possibly win. If i do expand the grid space, how large should it be? – moonheart08 Feb 5 '18 at 21:24
• – moonheart08 Feb 5 '18 at 21:25

You're recruiting your local neighborhood for your Jr Basketball team. However, the opposing team also is recruiting!

• You both stand at the end of the street of 100 houses. Each house has a kid with a unique, random height from 1 to 100. Taller is better.

• Actions take different amounts of time. Your opponent may have a different turn order, or may even have more/less turns than you.

• If you have spent less than or equal time than your opponent, then your turn is next (turns can be simultaneous)

On your turn you perform one of the following actions:

• Recruit the kid at the Nth house. This takes N Time.
• If you both recruit the same kid, you get into argument, and he decides not to play basketball this year. (Nobody gets him)
• Once recruited, a kid won't switch sides.
• Disqualify the kid at the Nth house. There are myriads of rules to Jr Basketball, and you know just which rules he's breaking. This takes 10 time.
• You cannot disqualify a kid that has been recruited or is in the process of recruitment.
• If you try to disqualify a kid on the same turn your opponent tries to recruit him, the disqualification fails.

After all of the boys have been recruited, been disqualified, or lost interest, we play the big game:

1. We place the teams into two lines from shortest to tallest.
2. Each pair of boys play each other.
3. The taller one wins, and gives his team 1 point.
4. If a team has more boys than the other, they get 1 point for each extra boy.
5. The team with the most points wins.

Now, your goal is to become the top recruiter. This means you need to win as many games as possible. You will face many other recruiters at random until a clear victor is decided.

• what happens if you recruit more people than your opponent? – Destructible Lemon Feb 6 '18 at 0:39
• Oh, I totally forgot to add that to the post. Thanks! – Nathan Merrill Feb 6 '18 at 0:43
• One thing I immediately notice is that recruiting more boys can be detrimental, if they're not as good as some other boys on the team: example: team 1: 3 5 7 9 11 vs team 2: 2 4 6 8 10. team 1 recruiting a boy of height 1 would cause team 1 to lose – Destructible Lemon Feb 6 '18 at 0:57
• That sounds like a feature, not a problem :) – Nathan Merrill Feb 6 '18 at 1:14
• I didn't say it was a problem, it was an observation. maybe i should have been clearer – Destructible Lemon Feb 6 '18 at 1:28

# Fortnightly Challenge #8: A new kind of "asynchronous" KOTH

This is a placeholder for the challenge spec. You can discuss this challenge in a special chat room.

Ordinary KOTHs require that a single user take up the job of hosting the competition: running the whole competition at once by themselves. Everything is dependent on them, and they can only run so many competitions or update ever so frequently. I think this can be improved... somehow.

Here are some ideas, many of which would require an encryption scheme or something to ensure correctness.

• Anybody can run the tournament and add their results to the current leaderboard somehow. This could be accomplished by some sort of cryptographic scheme to verify the results. Ideally the controller will be implemented via stack snippet to allow ordinary people to run it without downloading a controller.

• When a bot is added/updated, only the new pairs of contestants should be tried, and nearly anyone can update the leaderboard by themselves. (Assuming a deterministic KOTH, which it will probably need to be in order to prevent people from simply uploading the results that occurred in their favor.)

# Chain up the cops!

Thanks to Magic Octopus Urn for the original idea!

This is a combination between a and a challenge.

## Cops

Your task is to create a program that, when run in language A outputs a program, that when run in language B outputs a program which runs in language C and so on, until the final program, which outputs the string Game Over!*. You may use as many languages as you like, but each language may only be used once. Different versions of languages, or different compilers, do not count as different languages, i.e. Python 2 and Python 3 are the same language.

If using languages with different code pages, you should output the bytes that make up that program, not the characters. You should create a program that runs in at least 2 distinct languages. Languages must be free (as in beer) and be publicly available for anyone to use without paying.

Cops, you are to reveal the following things:

• The number of languages used
• The bytecounts of each program+
• The code to be run in language A, but not language A

If your answer has not been completely cracked after 14 days, it is safe and you should reveal the remaining languages and the codes in said languages. The submission which is safe and uses the most amount of distinct languages wins!

## Robbers

Your aim is to find out the languages the cops used. You can crack just one of the languages, or you can aim to find out the complete set of languages for any one cop, or anything in between. When cracking an answer, there are three possibilities:

• You crack the first layer: Create a new robbers post as a Community Wiki and edit in the first solution, along with your username, in the below format. Link the post to the Cops post.
• You crack an intermediary layer: edit your solution, and username, into the corresponding Robbers post and make sure that the cops is aware of the crack
• You crack the final layer: Notify the cop, and edit in your crack into the Robbers post, with the notice that it is the final program and that cops' run is over.

Each robber will have a score, defined somewhat as a league table. You get one point for every layer you crack, including the start and end cracks. However, if you singlehandedly crack an answer, you get one point for each language, plus 3 points. So, if you, by yourself, crack an answer with 4 languages, you get 7 points.

## Valid cracks

Meta notice: I'm having trouble deciding whether cracks have to be in the intended language or not. Thoughts?

When a robber crack a layer, they should comment below the cops post with the language, along with a way to test the current code. If the output is the same, but the language is different to the intended one, the crack is still valid (to prevent answers going in unintended directions). Obviously, if the language is correct, the crack is valid. However, a crack is only valid if the cop confirms it. I'm going to trust cops to not abuse this rule and turn down every guess and hope that the community will help deal with anyone who does.

## Formatting

# [N] languages

<code>

<Byte counts of the programs>


And, when a corresponding Robbers post is created and linked, please edit in

<link to Robbers post>


If your answer is safe, edit this into the title, along with the complete list of intended languages. Your program(s) can still be cracked until you do.

## [N]. [Language], cracked by [username]

<code>

<Try It Online/interpreter>

<anything else>


Where N is the current depth of the cracks. The first crack should be that same, but have

# [Cop's programs](link)


at the top of the answer.

## Example

Let's walk through a quick example:

I create the following program that runs in Python:

print("""'"!revO emaG"'>o<""")


When run in Python (3), this outputs

'"!revO emaG"'>o<


This can be run in ><> and outputs

"Game Over!"


Which, when executed by Foo, outputs the desired phrase, Game Over!. All I reveal to the Robbers however, are the number of languages (3), the original code (print("""'"!revO emaG"'>o<""")) and the byte counts of the 3 submissions (30, 18 and 12).

The robbers then guess that the first language is Python, so I'd edit that in, and change the code to the output of the Python program. The next guess is Perl, which I tell them is incorrect, before they quickly guess that the answers were ><> and Foo, and my answer has been completely cracked.

My cop answer, at this point would look lien the following:

# 3 languages, [completed](link)

## Python

print("""'"!revO emaG"'>o<""")

## ><>

'"!revO emaG"'>o<

## Foo

"Game Over!"

*anything else*


And the Robbers post would look like this:

# [Cop's post](link), done

## Python, cracked by user1

*code/explanation/TIO*

## ><>, cracked by user2

*code/explanation/TIO*

## Foo, cracked by user1

*code/explanation/TIO*


# Meta

*: Should I change the final task? I chose the phrase as I doubt many languages have this as a builtin.

+: Thoughts on revealing the intended bytecounts? I feel as though it is a good way for robbers to verify their guesses without the cops, before commenting.

Any other questions/clarifications/dupe targets?

• So the robber who cracks the first level gets the upvotes belonging to the robbers who crack all the subsequent levels? – Peter Taylor Feb 15 '18 at 8:25
• @PeterTaylor I had thought CW posts don't garner reputation? – AdmBorkBork Feb 15 '18 at 14:51
• @AdmBorkBork, I missed that the robber posts were to be CW, but that's not much better. Robbers get no rep at all? I mean, sure, the incentives of fake Internet points are bad, but I'm not sure that removing them completely is an improvement. – Peter Taylor Feb 15 '18 at 14:55
• @PeterTaylor AdmBorkBork is correct, the robbers posts are to be CW. I don't think that no rep reward will be a massive incentive for people to not compete, and if it is to them, then let them abstain. – caird coinheringaahing Feb 15 '18 at 16:25
• I think that the final program should output a distinct phrase, and that the phrase should be given at the start as well. So if your final program outputs "Hello, world!" you'd need to state that at the start. Shouldn't limit it to Game Over! – Magic Octopus Urn Feb 15 '18 at 17:22
• I just posted a [answer-chaining] [cops-and-robbers] sandbox draft, thinking it was an original idea, and then I scroll up the page in the Sandbox and see this... – Esolanging Fruit Feb 17 '18 at 21:52
• "Thoughts on revealing the intended bytecounts?" I'd say that secure hashes would be better. – NieDzejkob Mar 5 '18 at 14:04

# Generate a maximal binary Gray code

Given an input integer n, find an n-bit gray code where the sum of the absolute difference between each adjacent pair of bits converted to decimal is maximized.

For example, if n = 3, there are 96 possible gray codes, and the maximal sum of deltas in decimal of those is 21. Out of the 96 total, only 8 have maximal deltas.

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0 0 0│0 0 1│0 1 0│0 1 1│1 0 0│1 0 1│1 1 0│1 1 1│
│1 0 0│1 0 1│1 1 0│1 1 1│0 0 0│0 0 1│0 1 0│0 1 1│
│1 1 0│1 1 1│1 0 0│1 0 1│0 1 0│0 1 1│0 0 0│0 0 1│
│0 1 0│0 1 1│0 0 0│0 0 1│1 1 0│1 1 1│1 0 0│1 0 1│
│0 1 1│0 1 0│0 0 1│0 0 0│1 1 1│1 1 0│1 0 1│1 0 0│
│1 1 1│1 1 0│1 0 1│1 0 0│0 1 1│0 1 0│0 0 1│0 0 0│
│1 0 1│1 0 0│1 1 1│1 1 0│0 0 1│0 0 0│0 1 1│0 1 0│
│0 0 1│0 0 0│0 1 1│0 1 0│1 0 1│1 0 0│1 1 1│1 1 0│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘


Checking the first result, the decimal values are

0 4 6 2 3 7 5 1


and the deltas of each adjacent pair are

4 2 4 1 4 2 4


and the sum of that is 21.

## Rules

• The input will be an integer n > 0.
• You may output either one or all possible gray codes that satisfy the condition.
• Can we output the decimal values instead of the binary? – user202729 Feb 17 '18 at 15:18
• "the sum of the absolute difference between each adjacent pair of bits converted to decimal" doesn't make much sense. Decimal is irrelevant (a number's value does not depend on its representation) and mentioning it only serves to make the sentence harder to parse. And looking at the example, it's not about adjacent pairs of bits but adjacent numbers in the sequence. – Peter Taylor Feb 19 '18 at 11:25

# The Euler Masheroni Constant

The Euler Masheroni constant is a very interesting number. It is defined to be and appears seemingly everywhere in number theory. Famously, it is unknown whether it is rational, irrational, or transcendental.

# The Challenge:

Pretty simple one here: Given N, your program should calculate the Euler Macaroni constant to at least N decimal places of prescision. Your score will be the maximum value of N for which the program is accurate, and ties will be won by the shortest code.

For refrence, the Euler Macaroni constant to 50 places is

0.57721566490153286060651209008240243104215933593992


Be sure to check out the wikipedia page for more formulas for the Oily Macaroni constant!

https://en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant

• s/Macaroni/Mascheroni/g and s/Oily/Euler/g – Beefster Feb 19 '18 at 20:37
• Mmmm. Oily Macaroni. Definitely doesn't stick together that way. – Beefster Feb 19 '18 at 20:50
• The easy way to calculate this constant will definitely timeout for very small n, and I guess most programs will be infinite anyway. – user202729 Feb 20 '18 at 4:06
• You can use MathJax now: $$\gamma = \lim_{n\to\infty}\left(-\ln n + \sum_{k=1}^n\frac 1 k\right)$$ – wastl Jun 26 '18 at 12:25

# Design a language and golf its interpreter

Your task is to design a language and write an interpreter for it. Your language must have the following properties:

• Its source code will consist of strings of two characters. I will write them as ( and ) and refer to them as parentheses, but you can choose whichever two distinct characters you like. You can choose whether to ignore other characters.

• Valid programs will consist of any string in which the parentheses are balanced, such as ()() or (()(()())). The empty string is a valid program. You may assume the input will be a valid program.

• Programs will take an input and return an output. Valid inputs and outputs are of the same form as source code: they must be balanced strings of parentheses. This input and output may be accomplished by any method you like, e.g. command-line arguments or STDIN/STDOUT. You may assume your program's input will always be valid.

• Your program must be Turing complete. That means that for every computable function from balanced strings to balanced strings, there must be a program in your language that computes it. Your answer must include a proof of Turing completeness, otherwise it is not a valid answer.

This is . Your score will be the size of your interpreter's implementation, measured in bytes. The lowest score wins.

Here are some additional rules and clarifications:

• Your interpreter must be a complete program

• You must include a description of your language's semantics. This is needed in order to prove that it's Turing complete.

• Your interpreter must correctly implement these semantics. (Or at least, it must be able to in principle, given infinite machine resources.) If someone finds a bug in your interpreter, your answer becomes invalid until it's fixed.

• You may not assume numerical types are of unlimited precision unless they actually are - be careful of integer overflow!

Here is the precise grammar for programs as well as input and output strings:

<expr> ::= "(" <expr_list> ")"
<expr_list> ::= "" | <expr_list> <expr>.
<program> ::= <expr_list>


You can optionally replace the last line with

<program> ::= <expr>


which means there must always be an enclosing pair of parentheses. (So ()() and the empty string would not be valid programs, for example.) If you do this, you must do it for input and output strings, as well as programs.

As mentioned above, ( and ) may be replaced with any two distinct characters.

Sandbox notes

I've been obsessed with designing a simple and elegant language with these properties for some time, but I've never come up with one that really satisfied me. It occurred to me that "source code size of the interpreter" might work as a proxy for simplicity and elegance, so I thought I'd give this a try. Suggestions for a better winning criterion (making it a ) would be welcome.

I'd also welcome suggestions for a snappier title.

• What prevents us from trivially decoding balanced parentheses to an existing programming language, evaluating, and then encoding the result back to balanced parentheses? Try it online! – Adám Feb 19 '18 at 17:56
• Must all strings of balanced parentheses be valid inputs and programs, or can some of them result in errors? – Zgarb Feb 19 '18 at 20:31
• i feel like requiring the program to have to be covered in parentheses to work sort of adds an unnecessary step. i would like it if that were removed, or if it was an option whether or not it counts as invalid to have ()() etc. – Destructible Lemon Feb 19 '18 at 22:15
• @Adám unfortunately nothing really prevents this. I'd realised that a while after posting this. I'm not sure how to resolve that currently, so I probably won't post this challenge unless I figure out a good way. – Nathaniel Feb 19 '18 at 23:54
• @Zgarb I intended it that every balanced string is a valid program. (But one could always just return the empty string if there's an error. This is another thing I don't like but don't have an easy way to fix.) – Nathaniel Feb 19 '18 at 23:55
• what if you had to implement the language in two distinct languages or something? actually now that i think about it, a bunch of golf languages have python eval... – Destructible Lemon Feb 20 '18 at 2:00
• @DestructibleLemon that's not a bad idea, but the languages would need to be sufficiently different in order for it to work. I wonder how we could specify that? – Nathaniel Feb 20 '18 at 4:27
• it might be a better idea, in fact, to go to the esolangs room, design a language, then make the challenge be implementing that. perhaps as a bonus, you could have spec options (features or syntax or something which is optional or can be from different choices, with the stipulation that the chosen version of the language has to be as functional as the normal version of the languge) – Destructible Lemon Feb 20 '18 at 6:40
• @DestructibleLemon I really want language design to be the focus of the challenge, though. (By the way I changed the grammar spec according to your suggestion.) – Nathaniel Feb 20 '18 at 7:35
• "Your program must be Turing complete. That means that for every computable function from balanced strings to balanced strings, there must be a program in your language that computes it" Does it? Turing completeness implies the ability to compute any computable function, but the ability to compute a subset of computable functions does not in general imply Turing completeness. – Peter Taylor Feb 20 '18 at 12:08
• Moreover, Turing completeness doesn't say anything about representation. Minsky register machines are TM-complete, and their state could be put into bijection with balanced strings generated by the grammar <n> ::= "(" ")" | "(" <n> ")" <state> ::= <n> | <state> <n> giving a Turing-complete system which only computes computable functions from restricted balanced strings to restricted balanced strings. – Peter Taylor Feb 20 '18 at 12:08
• "Your interpreter must correctly implement these semantics. If someone finds a bug in your interpreter, your answer becomes invalid until it's fixed. Be careful of integer overflow!" is just asking the impossible. No physical implementation can have access to unbounded memory, so strictly speaking no physical implementation can be Turing complete. – Peter Taylor Feb 20 '18 at 12:09
• @PeterTaylor your second comment answers the question in your first comment. Do you think I should change anything or is it fine how it is? For your third comment I meant given infinite resources of course - I've amended the text. – Nathaniel Feb 20 '18 at 12:31
• I think my second comment answers the question in my first comment in the negative, meaning that this question would incorrectly disqualify an implementation along the lines sketched in the second comment. BTW I'm pretty sure there are existing languages meeting some of these criteria, if not all, with single combinators. And if there aren't, it's a straightforward thing to do. – Peter Taylor Feb 20 '18 at 12:40
• I can't think of an objective measure for elegance, that's fairly subjective and considering the issue Adám pointed out, code-golf won't do very well. What's your reasons against making it a popcon? – ბიმო Feb 20 '18 at 19:19

### Meta:

I don't know whether there are any known algorithms for solving this problem, that also means I'm not sure whether this is an interesting challenge. EDIT: Ok it is probably equally hard as the graph isomorphism problem.

Inspired by this puzzle

Given two isomorphic directed (unweighted) graphs with labelled nodes, find an isomorphism between the two graphs.

### Details

• You have to provide a working implementation of your algorithm.
• You have to provide the complexity expressed in the number of nodes, edges (or possibly other numbers?)
• The graphs can be represented as an adjecency matrix, as set of pairs that represent edges, as an adjecency list or as a native graph type etc.
• The output can be a function that maps the labels of one graph to the labels of the other, as a list as a graph etc.
• If necessary, you can assume that there are no edges with the same start as end node.

### Examples

• (What if it's unknown-complexity? Some heuristics can be quite fast in practice but formally reason about the complexity can be very hard) – user202729 Feb 22 '18 at 2:31

# Assemble an XOISC program

Tags: , ,

Recently I solved this challenge, for which I created XOISC - a very low-level functional language. To compile a program (written in the absurdly high-level lambda calculus programming language) it must first be translated into an expression consisting only of X combinators and from there it can be translated to the "machine language".

There's an initially empty stack and the program only consists of a stream of integers. For each integer the following happens:

Pop N elements f1,...,fN and push X (f1 (..(fN-1 fN)..)) - ie. it right-folds function application and applies this to another X.

Eventually we'll end up with a stack of functions which gets left-folded with function application. That's it.

## How does it work?

When parsing such an expression, one thing to keep in mind is that function application is left-associative - meaning that X (X X) X is read as (X (X X)) X rather than X ((X X) X).

If we have an expression f g with sub-expressions f and g (in the code below App f g - eg. X (X X) X would be f = X (X X) and g = X), there's a simple recursive algorithm to assemble it:

-- Base case: We simply need to pop the accumulated functions
asm' n X         = [n]
-- Recurse: First build the left function, then the right one.
--          Incrementing n ensures that we leave (f g) on stack
asm' n (App f g) = asm' 0 f ++ asm' (n+1) g

asm expr = asm' 0 expr


• this algorithm assumes an already parsed expression in the form of of a binary tree (the definition of the data structure would be data Exp = X | App Exp Exp where X would be a leaf and App f g would be a node with children f and g that are Exps as well)*
• asm' n exp does a case distinction by matching a pattern on exp:
• if the expression is X (ie. exp = X) it's the base case and just returns a singleton list containing n (an integer)
• else it's of the form f g (with f,g some sub-expressions) which is expressed as App f g, so it will recursively build the list for f and append the list of g
• to assemble an expression exp we begin initialize the recursive algorithm with n = 0 (asm' 0 exp)

Note: Since a lot of people here know Python, you can find a horrible but very well documented Python reference implementation here which does the parsing as well as the assembling!

* The | means that an Exp type can be constructed of either the left constructor (X) or of the right one (App Exp Exp where the two Exp are Exp two sub-expressions).

For example the expression X (X X) X would be expressed as App (App X (App X X)) X.

## Example

Having an expression X (X X) X, it helps to think of the implicit parentheses: (X (X X)) X

Translating this with the above algorithm:

• Assemble (X (X X)):
• Assemble X:
• Base case => 0
• Now Assemble X X, making sure it gets applied to the previous one (+1)
• The first X gives us a 0
• The second one gives us 0 + 1 + 1 = 2 (apply to X and previous one)
• So the left (X (X X)) gave us [0,0,2], assembling the right X:
• This gives us 0 + 1 (apply to the previous one)

And we end up with the program [0,0,2,1].

Note: While this algorithm ensures that there's a program for every expression, there can be other solutions too. For example [0,0,1,0] would be a valid one for X (X X) X as well.

## Challenge

Given an expression consisting of X combinators, translate it to the XOISC machine language:

• Input will be a string encoding such an expression
• The input will be a valid expression and non-empty
• You may choose to require an input string that contains no spaces
• You may choose the characters encoding parentheses and the combinator itself (as long as it's consistent, eg. using [,],x instead of (,),X)
• You're guaranteed that there are no unnecessary parentheses (eg. (X X) X would result in undefined behaviour)
• Output can be a list of integers, a string separated by new-lines or whitespaces

## Testcases

These testcases assume that the input contains whitespaces and choose X to encode the combinator.

Note that there may be multiple valid outputs, you're free to choose one* - I'll only show the solution resulting from the above algorithm:

X -> [0]
X X X -> [0,1,1]
X (X X) -> [0,0,2]
X (X X) X -> [0,0,2,1]
X (X (X (X X X))) -> [0,0,0,0,1,4]
X (X X) (X X) (X X) -> [0,0,2,0,2,0,2]
X (X X X (X X)) -> [0,0,1,1,0,3]
X (X (X X) (X X)) -> [0,0,0,2,0,3]
X X (X X (X (X (X (X (X X X)))) X) X) -> [0,1,0,1,0,0,0,0,0,1,5,2,2]
X (X (X X) X (X X X)) X (X (X (X X) X)) -> [0,0,0,2,1,0,1,3,1,0,0,0,2,3]
X (X (X (X (X X) X X) X X X) X X X X) X X X X X -> [0,0,0,0,0,2,1,2,1,1,2,1,1,1,2,1,1,1,1,1]
X (X (X X (X X) (X X) (X X) X) X (X X) X) X (X X X) X -> [0,0,0,1,0,2,0,2,0,2,2,1,0,2,2,1,0,1,2,1]


* Here's a program to validate alternative solutions

### Sandbox

• I already posted this to main, but apparently I did a bad job of explaining it.. It's hard to tell what's missing, I'd be happy for feedback (feel free to edit this)!
• I think you need to move away from Haskel syntax and jargon. Just as one example: I have no idea what the point of "Having an expression X (X X) X, it helps to think of the implicit parentheses: (X (X X)) X" is. The whole explanation seems reliant on an understanding of concepts I personally don't usually think about. Also it's confusing having an example as code that is only thinking about the problem in one way and outputting only a single solution of many possible while trying to understand what the possibilities are. Since I can't understand it it is hard for me to help make it clearer :( – Jonathan Allan Feb 23 '18 at 22:12
• @JonathanAllan: Thanks a lot for the feedback! It's not necessarily Haskell jargon, but I think I see what you mean. I'll rewrite this completely, it's probably the easiest way. – ბიმო Feb 23 '18 at 22:22