# 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

# How many times?

Inspired by Rotational symmetry of string.

Given a string, return its shortest substring that, when repeated a number of times, will produce the original string, as well as the number itself.

Test cases:

"ABCDABCDABCDABCD" => "ABCD", 4
"AAAAAAAAAA" => "A", 10
"ABCDEFGHIJKLMNOPQRSTUVWXYZ" => "ABCDEFGHIJKLMNOPQRSTUVWXYZ", 1
"" => "", 0
"Don't repeat yourself. Don't repeat yourself. " => "Don't repeat yourself. ", 2


Rules:

• You may return the substring and the number in any format you'd like, as long as it's consistent and clear i.e. you can always separate the number correctly from the substring e.g. abc12 isn't allowed since you can't determine whether abc is to be repeated 12 times or abc1 is to be repeated 2 times. The substring must be returned verbatim, while the number can be returned in any generally allowed format per meta consensus.
• The substring must be the shortest possible.
• For the empty string, you must return "" and 0.

# Sandbox

• Is the challenge description golfed enough? :P
• May I improve the return/output format?
• Pleas can you change the abc2 should be repeated 1 time to abc1 should be repeated 2 times? It makes more sense. – caird coinheringaahing May 20 '17 at 21:16
• @RandomUser Typo; should be fixed. – Erik the Outgolfer May 20 '17 at 21:17
• – Peter Taylor May 21 '17 at 7:02
• What range of characters are possible within the string? Can newlines occur? – Steve Bennett May 21 '17 at 8:58
• Also, why not just specify that the output format is "12\nabc"? Otherwise there may be arguments on everyone's answers about whether or not they meet the requirements. – Steve Bennett May 21 '17 at 8:59
• @SteveBennett And that's what the second question in the "Sandbox" section is for. Please note that I do not intend to restrict the output format like this. – Erik the Outgolfer May 21 '17 at 11:47

# Add a language to a quine

Add a language to a quine program. Your program must output itself in all languages used so far.

Second to last answer wins after no answers have been posted for two weeks.

• this is hard mode of existing challenge? – Destructible Lemon May 24 '17 at 3:58
• @DestructibleLemon Basically. – dkudriavtsev May 24 '17 at 3:58
• @Okx So that you can't win by posting an answer which is impossible to add onto. – ETHproductions May 25 '17 at 15:12

# Build a simple 2D game engine

Write a program that take input specifying specs of a simple 2D game regarding the following:

• GUI: a space where you can print text
• Scene: a 2D stage where player\enemy move
• Input Scheme: a way to check for input
• Player: one object
• Enemy: one or more objects
• Coin: one object
• Engine: manage running scenes

The program should offer the following instructions:

• generate: create an object & place it in the scene
• destroy: destroy an object or hide it from the scene
• move: move an object to a different location, or apply motion
• collision: check if two objects are colliding or interlacing
• write: write to GUI
• param: create, modify, or read an integer
• terminate: stop running update, and run end
• a way to do an if-else

A Scene should at least have the following functions:

• start: sequence of instructions, applied once when the scene is fired
• update: sequence of instructions, applied N-times per second
• end: sequence of instructions, applied once when the scene is terminated

## Example

Input the game spec

GUI:1,10

SCENE:5,10

START: GEN(p1,PLAYER,5,1); GEN(e1,ENEMY,4,4); GEN(c1,COIN,3,6); PARAM(r1,0)

UPDATE:  IF(COLLISION(p1,c1), DESTROY(c1);PARAM(r1,PARAM(r1)+1));
IF(COLLISION(p1,e1), DESTROY(p1);TERMINATE);
IF(INPUT(ARROW-UP), MOVE(p1,-1,0));
IF(INPUT(ARROW-DOWN), MOVE(p1,+1,0));
IF(INPUT(ARROW-LEFT), MOVE(p1,0,-1));
IF(INPUT(ARROW-RIGHT), MOVE(p1,0,+1));
WRITE(g1,r1)

END: IF(PARAM(r1)=1, WRITE(g1,"YOU WON"), WRITE(g1,"GAME OVER"))


Output an interactive game

[ 0        ] <----- G:GUI (1 x 10)
+----------+
|          | <--- S:Scene (5 x 10)
|          |
|      C <-|----- C:Coin
|   E <----|----- E:Enemy
|P <-------|----- P:Player
+----------+

• game starts with player, one enemy, one coin
• you can control the player with arrow keys
• if player come in contact with enemy, player disappear then it ends
• if player come in contact with coin, coin disappear then it's counted
• when game ends, if coin count is 1 you win, otherwise you lose

## Meta

• What tags to use?
• How can I simplify the requirements so that it's possible to solve it with languages of simple means?
• I haven't seen many challenges like this, to write a program which parse instructions to create an interactive program within it, what do you think?

# Distinct strict partition counts

Related

Write a function or program that, given a positive integer n, returns or prints an array (or list, set, etc.) of length l such that each index i contains the count of distinct partitions of size i of n (one-indexed) and l is the maximum size of partitions for n.

# Definition

Let f(n) implement the task described.

### Consider f(10)

10 may be broken into the following distinct partitions:

10         // Size 1
9,1        // Size 2
8,2
7,3
6,4
7,2,1      // Size 3
6,3,1
5,4,1
5,3,2
4,3,2,1    // Size 4


There are:

• 1 distinct partitions of size 1.
• 4 distinct partitions of size 2.
• 4 distinct partitions of size 3.
• 1 distinct partitions of size 4.

Therefore, f(10) returns [1, 4, 4, 1].

# Test Cases

TODO

• – Peter Taylor May 24 '17 at 21:25
• @PeterTaylor Thank you. I was dreading the larger test cases. – Addison Crump May 24 '17 at 21:35
• in my opinion this suggestion is quite clearly defined and simple, I like it - but it didn't attract votes nor critique .. do people find it too mathematical? I was going to propose something similar related to enumerating Standard Young Tableaux given a partition shape – jayprich Aug 22 '18 at 10:14

# Show key code

Inspired by the showkey command.

You have to output the key and if is a key-up or a key-down event. I exemplify:

The output I want:

Key X Down
Key X Up


for both the instants you press or release a key.

You can output it on a console or on a GUI.

It is , so shorter code wins.

• I don't think this is currently clear. What keys correspond to what key codes? You should include either a list, or some source where one can determine which keys correspond to which codes. – Wheat Wizard May 27 '17 at 0:18
• @WheatWizard i think, there is standard. Also, if not, there will be keyboard/language-related key code table – Евгений Новиков Jul 31 '17 at 11:48

# Set The Shapes

Updated on 23/05/17 with new shapes & questions

## Challenge

Let s be the sequence of polygonal numbers with S sides and t be the sequence of polygonal numbers with T sides. Take the set union of the first n elements of s and the first n elements of t.

### Input

3 integers, n, s & t where:

• n>0, 2<(s,t)<13 and s!=t
• The values of s & t each represent a different polygonal number type:
  3 = Triangle
4 = Square
5 = Pentagon
6 = Hexagon
7 = Heptagon
8 = Octagon
9 = Nonagon
10 = Decagon
11 = Hendecagon
12 = Dodecagon


### Output

An array of the set union of the first n numbers of shapes s and t in ascending order.

### Example

(assuming 0-based indexing)

• Input: n=5, s=3, t=4
• The first 5 triangular numbers are 0, 1, 3, 6, 10
• The first 5 square numbers are 0, 1, 4, 9, 16
• Output: [0, 1, 3, 4, 6, 9, 10, 16]

### Rules

• Input must be 3 separate integers
• Output must be an array (or equivalent in your chosen language)
• If your chosen language isn't capable of handling either or both of the above then standard I/O methods apply
• s & t are guaranteed to be different but you must be able to handle them being input in either order - smallest first or largest first
• This is so lowest byte count wins

### Test Cases

Input: 5, 3, 4
0-Based Output: [0, 1, 3, 4, 6, 9, 10, 16, 20]
1-Based Output: [1, 3, 4, 6, 9, 10, 15, 16, 25]

Input: 10, 9, 8
0-Based Output: [0, 1, 8, 9, 21, 24, 40, 46, 65, 75, 96, 111, 133, 154, 176, 204, 225, 261]
1-Based Output: [1, 8, 9, 21, 24, 40, 46, 65, 75, 96, 111, 133, 154, 176, 204, 225, 261, 280, 325]

Input: 1, 7, 6
0-Based Output: [0]
1-Based Output: [1]

Input: 8, 3, 3
Invalid input as both shapes are the same

Input: 0, 2, 17
Invalid input as n<1, s<3 and t>12


### Bonus Idea 1

Brownie points if you want to increase the range for s & t and include some other polygons (e.g., star, dodecagon).

### Bonus Idea 2

Alter the challenge to only require that solutions be able to handle 5(?) different shapes with a score reduction for each additional shape, up to a maximum of 10(?).

## Questions

This is my first challenge (inspired, in part, by this) so all feedback very much welcome.

• Should I add or remove any tags?
• Is the above sufficiently different from this and this?
(Votes: 2 for this not being a dupe, 2 for it being a dupe of the second linked challenge)
• Does everything read OK & make sense?
• Should I include the formula for each shape in the question?
I'm leaning towards "yes" as:
1. For those that know them, figuring them out won't be a challenge
2. For those that don't, figuring them out wouldn't add to the challenge
3. As soon as one person posts a solution containing the formulas, that makes them available to everyone else anyway.
• Should there be more (e.g., star, tridecagon+) or less possible shapes?
• Would it improve the challenge if I allowed solutions to pick a smaller subset of 5(?) shapes to work with? How about if that subset had to be sequential (e.g., 3-7 or 5-9 but not 3,5-8)?
• What test cases should I add?
• Do the bonus ideas add to or detract from the challenge?
• Is there a better name I can give this challenge?
• Should I be asking any other questions?!
• Yeah if you want to make it bigger just add the polygons and require them. But right now it looks to be a big enough handful. – Christopher May 17 '17 at 10:14
• The two linked challenges don't seem similar enough to make this a duplicate (to me). – trichoplax May 17 '17 at 10:18
• 1. I don't find "the first n numbers of both shapes" very clear. In fact, I can't find a single English phrase which cleanly expresses the meaning I reverse engineered from the example. I think it takes a few sentences or a mathematical expression. 2. The example looks wrong: what happened to 15? 3. I disagree with trichoplax: IMO this is a duplicate of the second linked question. – Peter Taylor May 17 '17 at 10:51
• Thanks for your comments, @PeterTaylor. 1. Could you suggest some wording for the intro to make it clearer? 2. Yep, I messed that up in an edit - it's fixed now. 3. Fair enough, that's one vote for it being a dupe and one vote against - I'll update to reflect that. – Shaggy May 17 '17 at 10:55
• Let S be the sequence of polygonal numbers with s sides and T be the sequence of polygonal numbers with t sides. Take the set union of the first n elements of S and the first n elements of T. – Peter Taylor May 17 '17 at 11:16
• Many thanks, @PeterTaylor; I've edited that in. – Shaggy May 17 '17 at 11:21
• I agree with Peter - this is too close to the second linked challenge. – Mego May 29 '17 at 10:23
• Thanks for the feedback, @Mego. That ties the vote; guess this stays in the sandbox a little longer, so. – Shaggy May 29 '17 at 10:28

## Introduction

"Muhuhuhahahah!" The mad scientist laughs. "You're trapped in my own little game!"

In front of you is a deadly pit of snakes, while behind you is a bottomless chasm. There's no way out, you're stuck!

"Two steps in front of you is the snake pit, and two steps behind you is the chasm. But! Before you move, you MUST write down a sequence of steps, forwards and backwards, and give them to me. But! because I'm feeling a bit evil today, I can make you take, instead of every step, every nth step, where n is less than your sequence length!

Choose wisely, now."

What's the maximum number of steps you can take before your imminent death?

The intro above is a twist on the Erdős discrepancy conjecture, which was recently proven true (if you want to understand more about this, go to this video, by James Grime - I "stole" the twist question off of him).

The answer to the intro is 11 steps, but I won't go too in-depth with a proof. The answer, if the distance between you and the two "dangers" were 3 steps, is 1160 steps, although that isn't validated properly yet.

Your task is to make a program that generates the longest sequence of steps you can for a larger x, where x is the number of steps between you and the two dangers. For the purposes of this challenge, + represents a step forward, and - represents a step back.

So, an output for an input 2 is:

+--+-++--++


Which works, no matter what n the mad scientist chooses. For our challenge, x = 5.

## Rules:

• You may update both your answer and program, if you can get a better score via optimisation.
• Your program, in its entirety
• The amount of steps generated - this will be your final score.
• You must also provide an online version of the sequence in a Pastebin, or something similar. This is so we can check your answer.
• The time your final score was last updated, so I don't have to check your history
• You may NOT hardcode sequences beforehand
• Your program must work for all x (where x is the number of steps between you and the pit & chasm), but you only need to provide the score for x = 5.

The answer with the largest score wins!

## Meta:

• What tags should I put in?
• What things should I fix / elaborate?
• For the "link to text file containing sequence" thing, I'm worried that the files might eventually get really big, as answers are more and more sophisticated. Is there any way to counteract that?
• 1. "Your task is to make a program that generates the longest sequence of steps possible for a larger x" doesn't actually seem to be true: later text implies that you want something that terminates in a reasonable time rather than something which finds the actual optimum. 2. "The accepted answer will be the answer with the highest score, a week after the challenge is posted" is something which we've been discouraging for about the past five years. 3. For n=3 isn't the maximum possible actually 1160? – Peter Taylor May 31 '17 at 11:52
• @PeterTaylor I got confused with what you meant by 2 for a while... you mean that the answer shouldn't be determined in time at all, right? – clismique May 31 '17 at 12:04
• Yes, exactly. Accept the best answer after a week if you want, but don't imply that there's a deadline to submit answers. – Peter Taylor May 31 '17 at 13:34
• Very closely related. The rules aren't quite the same, but this may nonetheless be similar enough to be a duplicate. Also, "your program must fit into your answer" is a meaningless length restriction; these sequences are highly compressible, so there's no reason not to calculate the best possible answer for n=5, hardcode it, and still have length left for a feeble attempt at other lengths. – user62131 May 31 '17 at 21:47
• @ais523 The maximum length for n = 5 is extremely high, though, if I'm not mistaken. That would certainly make it extremely difficult to compress, and even if it was compressed, there's a very high chance of being beaten by some other answer. Also, that challenge's primary goal is code-golf, whereas mine doesn't focus on code golf at all, rather, generating the longest sequence possible. I can make n higher if you want. – clismique Jun 1 '17 at 8:00
• @ais523 I got rid of the "program must fit into your answer" thing. – clismique Jun 1 '17 at 8:20
• You go back and forth between x being the input and n being the input (the number of steps). It'd be better to be consistent. Also, instead of saying your program generates the longest sequence of steps possible, which can't be done because we don't know how long that sequence is, you should instead say that it generates as long a sequence as you can, or something like that. – isaacg Jun 1 '17 at 9:40
• @isaacg Fixed both issues! – clismique Jun 1 '17 at 11:24

# Data Categorization with a Si(g)n

## Background:

Machine learning is a very powerful tool for categorizing data. It can help find a function that splits some already known data so that unknown values can be predicted. Typically, this function should be simple so that it does not "overfit" the data. As it turns out, previous studies have found out that the simple function f(x) = sgn(sin(ax)) can split most data into two categories with only a single coefficient to adjust! This will definitely (not) prevent overfitting, and should (not) be used for every application of machine learning.

sgn(x) is the sign function of x. As Wikipedia says,

         / -1 if x<0,
sgn(x) = |  0 if x=0,
\  1 if x>0.


## Input:

Two ordered sets/arrays/lists of integers {m1, m2, m3, ...} and {n1, n2, n3, ...}.

You can take input as 2 lines of input, an array with the two arrays m and n as its elements, or any other reasonable method of input.

## Output:

A value of a such that sgn(sin(ax)) equals 1 when x = m1, m2, m3, ..., and -1 when x = n1, n2, n3, ...

If no such value of a exists, you can output any non-numerical value.

## Test cases:

Example inputs will be in the form [[m1, m2, m3, ...], [n1, n2, n3, ...]]
Input                  | Output
[[1, 5],    [2, 3]]    | 1.75
[[2, 3, 6], [5]        | 4.5
[[1, 3, 5], [2, 4, 6]] | 3.1415925
[[1, 6],    [2, 3]]    | Random junk
[[2, 3, 4], [1]]       | <Anything non-numerical>

• Is there a way to determine whether it is possible to find such a value? If yes, could you please add that to the challenge, if no, then I think this challenge is impossible to solve. Other than that you should probably define what happens for sign if the argument is zero. Is it enough if it we get a solution for a finite precision implementation of sin (but there would actually be no solution)? – flawr May 30 '17 at 18:27
• I guess with a fast enough oscillation, there should be a solution for any data set in which there are not two points of opposite categories with the same x value. – feersum May 31 '17 at 16:29
• @flawr When I designed the challenge, I didn't know if there was a solution. But, that's what made it interesting. While actually making the test cases and verifying them, I found a good method of finding possible values, and also test it they exist. However, I thought that it was the analysis of the function that made the challenge interesting, and so I wanted people to find their own methods of finding an answer. I'll maybe add some bounds to where you need to check, but I don't want to just straight up give away a possible answer that everyone will copy. – K Zhang May 31 '17 at 21:07
• @feersum I had previously thought that that was the case, but it turns out that some data sets do not have a solution. I put 2 of them in the test cases section. – K Zhang May 31 '17 at 21:20
• "Two sets/arrays/lists of numbers": define numbers. All of the test cases use integers, but restricting it to integers vs permitting doubles makes a big difference. – Peter Taylor Jun 1 '17 at 11:20
• @PeterTaylor I've restricted the inputs to be integers only – K Zhang Jun 1 '17 at 11:54
• @feersum It is relatively easy to see that the last test case does not have a solution. – flawr Jun 1 '17 at 12:30

# Odd with Odds, Even with Evens

Given an input integer n, express it as a sum of numbers with the following properties:

• If n is even, the numbers used to sum should be even.
• If n is odd, the integers used to sum should be odd.
• Any integer used (x) should be 0 < x <= ceiling(n/2).
• All numbers used in the summation should be unique.
• If there are no set of distinct odd/even integers that sum to n, return -1.
• Output may be as an array or delimited string.

# Examples

Input | Output       | Comments
------+--------------+-------------------------------------------
2     | -1           | 0 < ? <= 1 = [1] (No evens, not possible)
12    | [6,4,2]      | Order is arbitrary, [2,6,4] is fine.
24    | [8,4,12]     | [2,4,6,12] works too.
9     | [1,3,5]      | Odd cases are a bit trickier to think about.
|              | ceiling(9/2) = ceiling(4.5) -> 1 < x <= 5 -> [1,3,5]
1     | -1           | c(1/2) = c(.5) -> 1 < x < 1 -> []
13    | [1,5,7]      | c(13/2) = c(6.5) -> 1 < x <= 7 -> [1,3,5,7]
27    | [13,11,3]    | Etc...


The numbers you use for each answer and how you get to the numbers you used do not matter, the only thing that matters is that they adhere to the spec. The order of the numbers does not matter, and you may have different results than provided.

This is , first person to mail Bill the contents of Hillary Clinton's private mailserver wins.

• "no unique sum of odd/even integers" --> "no set of distinct odd/even integers that sum to" – Steve Bennett May 26 '17 at 5:21

# What's wrong with asterisk?

## Background

I work as a telephony engineer, and work with an open-source telephony system called Asterisk.

Often, our customers have issues with their phones, and we have to do some troubleshooting. The first method we try is an Asterisk command called sip show peers, which lists all the devices connected to the Asterisk system, as well as their status.

The challenge is quite simple, parse a simplified version of the output of sip show peers, and tell me what's wrong!

## Input

Input will be multiple lines of text, formatted as such:

201 OK (34ms)
SIP OK (7ms)


This is split into 2 sections: [Device number] [status]

The device number will always be 3 digits, and begin with either a 2 or a 3

If the status is OK, the ping is also shown in parentheses.

The last line of the input will always be the SIP.

You can always assume there will be at least 1 device, and the SIP will always be present.

Devices will always have the status OK or the status UNREGISTERED.

The SIP will always have the status OK or the status UNKNOWN

Devices and the SIP will only show their latency if their status is OK

## Output

If any device who's device number begins with a 2 has a latency greater than 100ms, you should output Device [device num] is lagging!

If any device who's device number begins with a 3 has a latency greater than 200ms, you should output Device [device num] is lagging!

If the SIP's latency is greater than 500ms, you should output Their SIP trunk is lagging!

If the SIP's status shows as UNKNOWN, you should output The system isn't live yet!

If a device's status is UNREGISTERED, you should output Device [device num] is down! unless every device except for SIP has the status UNREGISTERED, in which case you should instead output Their internet is probably down! once.

You should output all of the above conditions that are met, meaning if three 2## devices have a latency greater than 100ms, you should output Device [device num] is lagging for each one

If none of the above conditions are met, output I don't know what's wrong!

Each line of output should be separated with a newline. Trailing newlines are accepted.

## Testcases

201 OK (43ms)
202 OK (17ms)
301 OK (111ms)
SIP OK (7ms)

I don't know what's wrong!

201 OK (143ms)
202 OK (17ms)
301 OK (111ms)
SIP OK (7ms)

Device 201 is lagging!

201 UNREGISTERED
202 OK (17ms)
301 OK (411ms)
SIP OK (7ms)

Device 201 is down!
Device 301 is lagging!

201 UNREGISTERED
202 OK (17ms)
301 OK (411ms)
SIP UNKNOWN

Device 201 is down!
Device 301 is lagging!
The system isn't live yet!

201 UNREGISTERED
202 UNREGISTERED
301 UNREGISTERED
SIP OK (9ms)

Their internet is probably down!

201 OK (143ms)
202 OK (17ms)
301 OK (111ms)
SIP OK (607ms)

Device 201 is lagging!
Their SIP trunk is lagging!


## Scoring

This is so fewest bytes in each language wins!

• So if there's only one device and it's UNREGISTERED then we output both Device is down and Internet is probably down; if there are two devices and they're both UNREGISTERED then we just say that the Internet is down; and if there are three devices of which two are unregistered then we don't output anything? – Peter Taylor Jun 2 '17 at 8:54
• @PeterTaylor no. If there's only one device and it's UNREGISTERED, then all devices are unregistered, so you output only Internet is probably down. If there are 3 devices and 2 are unregistered you output Device is down for the 2 that are unregistered – Skidsdev Jun 2 '17 at 8:56
• Is this challenge meant to be about compression? If so, it should probably be tagged like that. If not, the answers for the various cases need to be simpler; at present, they're sufficiently complex that compressing them is likely to save bytes. (Note that unlike many challenges I give this feedback on, making compressing the output part of the challenge doesn't seem entirely inappropriate, so you may well decide to just roll with it.) – user62131 Jun 2 '17 at 15:00

# Let's not collide

### Contextualization

You might have heard about Re-Volt, a pretty old video game. Its collision system for cars is somewhat interesting : the body of the vehicle gets transformed into a simplified 3d convex shape which is then filled with spheres.

### Challenge

Your objective is to produce a code that will, provided a 2d shape and the number of wanted circles, output a similar result to the picture above. That is represent the polygon as accurately as possible with circles.

The two dimensional shape shall be a convex polygon of N vertices. The spheres will of course have the position and the diameter your code defines as optimal.

Your code should be able to take an input representing any irregular convex polygon (the format matters little as long as it can process at least a 10-vertices shape) and an input corresponding to the number of spheres that should fill the polygon.

Because it is impossible to fill completely and perfectly an N-gon with a finite amount of spheres, a tolerance is of course needed so your circles may have a portion (<10%) located outside the polygon. The circles may (and probably should) intersect at some points.

The output must be graphical.

### Test cases

You should test your code with the following three polygons and with 5, 10 and 25 circles.

Polygon n°1 (10 vertices)

[[1,0],[7.5,0],[15,0],[15.5,1.5],[15,2],[7,4],[4,4],[0.75,2.75],[0,2],[0.25,0.5]]

Polygon n°2 (5 vertices)

[[0,0],[11,0],[11,2],[7,4],[0,4]]

Polygon n°3 (8 vertices)

[[1,0],[15,0],[15.5,1],[15,2.5],[10,4.5],[2,4.5],[1,4],[0.5,1]]

### Questions

• Are the rules and the objectives clear enough ? Does the challenge make sense ?

• How should I define a winner (is a winner mandatory) ?

• Is it a good idea to leave the choice of the input to the coder ?

• Does this challenge already exist and this is a duplicate of some sort ?

• Are there any english mistakes ?

• Is the challenge actually a realistic thing to suggest ?

Any and all suggestions are welcome since this is my first post here.

• It's currently unclear exactly what sort of sphere packings are expected for the inside of the polyhedron; are you just tiling the surface, or the interior too? You also need some sort of objective way to define how well the spheres tile the surface (because people will just submit solutions that don't even try, unless you require them to optimize for that somehow). Generally speaking, the victory condition for this sort of challenge should be code length for an optimal output (if an optimal output is easy), or the best possible output (if an optimal output is hard). – user62131 Jun 2 '17 at 14:56
• In terms of English mistakes, you seem to be confusing "polygon" (which is 2-dimensional) with "polyhedron" (which is 3-dimensional), or possibly "circle" with "sphere"; I find it hard to figure out whether the question's asking for a 2D or 3D solution. With respect to input, it's generally best to leave it flexible unless doing so would be exploitable. Also, unless you made the image yourself, you need to give credit to the image creator (and verify that the copyright requirements on the image are suitable). – user62131 Jun 2 '17 at 14:58
• @ais523 Thanks for these suggestions. In fact, I was thinking about taking the 3d concept and applying it to 2d. That would translate by "fill the polygon with N circles (disks ?) so that these circles occupy as much surface as possible without them being more than 10% out of the polygon". – z3r0 Jun 2 '17 at 18:13
• @ais523 Concerning the victory condition, I don't know how to measure the optimality of an output so I guess it'd have to be a code golf. Finally, regarding the image, I didn't produce the image I use, however, I'm part of the community the image originates from and I'm pretty sure there would be no problems at all. If necessary, I'll add my own or will credit the user (I only know his forum nickname). – z3r0 Jun 2 '17 at 18:17

# Fairly Cut a Ham Sandwich in Half

In this challenge we consider a discrete version of the ham sandwich theorem. In our case the theorem says:

Given two sets of points in a plane, there is a line that simulaneously bisects both sets.

So given two disjoint sets of distinct integral points in the plane, your task is finding a line of the form a*x + b*y = c that bisects these two sets and outputs the integers a,b,c.

• Both (strict) half planes have to contain the same number of points of per set.
• The line can contain input points, these are then not counted to either of the sides (e.g. when a set contains an odd number of points, or all points are on one line.)
• The line is not necessarily unique.
• The mentioned representation of a given line is unique up to an integral multiple (e.g. (m*a)*x + (m*b)*y = (m*c) represents the same line as above), but you do not have to output the fully reduced form.

### Examples

As we said above, the output is not necessarily unique, so the presented outputs here are just examples. All the outputs are give in the form a,b,c.

Input: [(1,2),(1,4),(2,1),(2,3),(3,2),(3,4),(4,1),(4,3)] [(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)]
Output: 410,640,2625 (410x + 640y = 2624)
1,1,5 (x+y=5)
0,2,5 (2y=5)


In the following we see three valid outputs:

Input: [(1,1),(2,2)] [(1,2),(2,1)]
Output: 2,5,10 (2x+5y = 10)


• The best solution to this as written is probably brute force (or even randomized brute force, i.e. keep picking random lines until one of them works). You should probably either explicitly allow that, or else design a rule to disallow it. – user62131 Jun 6 '17 at 23:26

# Print a shuffled deck of cards

• What prevents me from outputting the cards in the same order every time? It's hard to specify randomness, as we've seen in other meta posts. You could say "I will run your program 100 times; no two outputs should be identical" since the probability of this happening is miniscule if the output is truly randomized. – musicman523 Jun 2 '17 at 23:05
• I believe "all permutations must have an equal opportunity of being chosen" is what is usually used. – totallyhuman Jun 3 '17 at 0:57
• I don't think having to output the Unicode card characters adds anything to the challenge and the answers (except for bytes...). – totallyhuman Jun 3 '17 at 0:58
• All I see in my browser is a bunch of rectangles with diagonals. – Dennis Jun 3 '17 at 21:30
• @Dennis Install the Noto fonts. – dkudriavtsev Jun 4 '17 at 1:09
• "all permutations must have an equal opportunity of being chosen" is actually EXTREMELY difficult, the random number generators of most languages aren't up to that -- even making sure every combination can come up is quite tricky as you need 225 bits of randomness. – Chris Jefferson Jun 4 '17 at 21:15
• Please delete this now that it is posted. – programmer5000 Aug 1 '17 at 16:08
• @programmer5000 It's already only a title – dkudriavtsev Aug 1 '17 at 23:30
• It should still be deleted. – totallyhuman Aug 10 '17 at 20:59

# Collatz Bearings

Everyone knows the collatz conjecture. It is that this function:

when repeatedly applied on a positive non-zero integer will reach one.

There are many ways to visualise this. Inspired by this post, with the original source of this method here, this is how we will do it:

Start at 1, with a northward bearing. The next numbers will be one unit (of any, consistent) size, and x degrees clockwise (+x) if it is even, and x degrees anticlockwise (-x) if it is odd.

An example of this can be seen here (Though it starts with an eastward bearing). It uses a few hundred random starting points and goes backwards. But it's probably easier to build it backwards.

Here is a graph-like visualisation, showing the first 8 levels:

There can be collisions.

Your task is to take two numbers, which would correspond to 2 nodes on that tree, and return the bearing of the second node to the first node.

## Input

3 numbers. Positive integer a, Positive integer b, and angle x, in any unit you desire. b > a > 0, x is the angle of seperation, in it's simplest form (mod 360 for degrees, mod 2pi for radians, or having the upper half be negative if you wish.) a and b are guaranteed to be in different places (e.g., you won't have a = 20 and b = 21.)

## Output

Using the method described above, the bearing of b from a in the graph, in the units of the input angle.

## Scoring

This is code-golf, so the shortest program in bytes wins.

### Note

If the Collatz Conjecture is eventually proven wrong, you do not need to take inputs where repeated application does not reach 1.

• I don't understand what we're supposed to do. If we start at 1 then we'll go 1 -> 4 -> 2 -> 1 so we should draw a chain LLRLLRLLR.... The supplied image doesn't look like that chain. – Peter Taylor Jun 5 '17 at 14:55
• 1 is the starting point. Then you go clockwise up to 2. It's a really zoomed out image, I'll post a zoomed in one with numbers – Artyer Jun 5 '17 at 14:56
• I think what's missing is something to say that the iteration is backwards. At least, that's how I can make sense of the graph: "It uses a few hundred random starting points" still confuses the issue. "The bearing of the second angle to the first angle" is also rather confusing: judging by the Output section I think it should be node rather than angle. – Peter Taylor Jun 5 '17 at 22:26

# Efficiently find the median

## Background

Computer scientists have spent a long time looking into ways of sorting data faster. One of the known discoveries is that if you can use the actual values of the data, sorting can be faster than if you can only compare them.

Finding the median of a list is a similar operation to sorting it (you can trivially implement it via sorting the list, then taking the element in the middle). However, if you're in an environment where you can only compare list elements (as opposed to looking at the elements directly), this is not typically the fastest way to find the median, as sorts are hurt more badly by the comparison restriction than finding the nth item is. What's the fastest way? Well, finding that is what this challenge is about. (However, you may want to read this Wikipedia article to get some ideas of the approaches that are typically used. I can't guarantee that the algorithm given there is the best, though, especially on a problem of the limited size given here.)

Write a program that finds the index of the median element within a list of 31 elements. However, the program may not take the list as input, and may not inspect its values directly. Rather, the program may only make comparisons to determine which of two indexes corresponds to the larger element, via calling a separate comparison function. (In other words, your program deals entirely with list indexes, not list values.)

In order to avoid solutions that brute-force their way through all possible algorithms, you must be able to run at least one worst-case input (i.e. an input that takes the maximum possible number of comparisons), using a comparison function which simply compares two array elements, in under 10 minutes on some computer you have access to. (Solutions which do not use brute force to find an algorithm are unlikely to get anywhere near this time bound.)

## Clarifications

• You may assume that all the list elements are distinct, i.e. the comparison function will always specify that one of the elements is larger, no matter how they're compared.
• You may choose the format in which the comparison function provides output, but there must only be two possible outputs (meaning "item at first index is larger" and "item at second index is larger") for any possible query; you can't return values that mean "item at second index is much larger" or anything like that.
• The comparison function will act consistently, i.e. if it claims that the list item at index A is larger than the list item at index B, it will always claim that; and if it also claims that the list item at index B is larger than the list item at index C, it will additionally claim that the list item at index A is larger than the list item at index C.
• You may take the comparison function as input, or assume that it's already defined with a specific name. This is not , so there's no need to try to exploit the freedom you have here to save bytes; feel free to write it in the most readable way. (The comparison function itself is not part of the submission, but you should probably include one for testing purposes and an example of what it looks like.)
• You may exploit the knowledge that the input list is exactly 31 elements long, if you wish (your program doesn't have to work in other cases, although of course it can if you want it to).
• If your language doesn't have functions, you may write the comparison function via a source code insertion, so long as the rest of the code doesn't attempt to inspect its internals. (However, you may as well just pick a different language in this case; the scoring method is based entirely on the algorithm you use, and picking a different language won't change your score at all.)

## Victory condition

Your score for this challenge is equal to the maximum number of times the comparison function can be called during a run of the program. Obviously, lower is better.

In the case of a tie, the first submission achieving the optimal score will win. (In other words, you don't gain anything from copying someone else's solution but golfing the code, or the like; you'll have to find an algorithmic improvement.)

# Sandbox questions

Is this scoring method , , or ? I guess I'd want to call it (by analogy with ) but that doesn't exist and I'm not sure it should be created. EDIT: None of the above, it's .

• I would expect the first answer to get a perfect score (because why submit one which doesn't?), at which point the question is dead. – Peter Taylor Mar 22 '17 at 12:32
• @PeterTaylor: I expect a perfect score to be fairly hard to accomplish on this challenge. I'm not sure the optimal algorithm is known, and the problem's too large to bruteforce. – user62131 Mar 22 '17 at 14:43
• I don't see anything in the question which rules out brute force. – Peter Taylor Mar 28 '17 at 8:41
• Oh, I was thinking of bruteforcing an algorithm before writing the program, which isn't possible with currently available amounts of computational power. You're right that you could just write a program that bruteforces all possible algorithms at runtime and then runs the fastest (although it would clearly be impossible to test). I should probably place a limit on runtime in order to fix that. – user62131 Mar 28 '17 at 15:11

# The Travelling Merchant king-of-the-hill

Economy is flourishing in the great Kingdom of Pipysigea [pee-pee-see-gee-ah], since the bandits have been driven away by the King's army. Especially, many people have decided to make trade their... trade, and have become merchants. You were one of them. You used most of your life's savings to purchase a good wagon and some animals of your choice. (Note: it can't be dragons. Sorry.) Unfortunately, you have just moved to Pipysigea from far away, attracted by the promises of wealth and security, so you don't really know much about the Kingdom: you have just bought a map, so you know the names of the cities and where they are, but you don't really know how long it's going to take to travel from one city to another.

So what is your goal? Being a merchant, you'll want to travel from city to city to get an idea of what good they want to buy and what goods they sell.

There will be a total of X kinds of goods in the Kingdom, and each city will be looking to buy 3 kinds and will be selling 3 kinds of goods. You will need to find out whether their prices are good for you: for example, the city of Puzzleon might be selling iron for 4 coins per unit and buying bread for 1 coin per unit, and the city of Stackapor might be selling wool for 2 coins per unit and buying iron for 5 coins per unit: in this case, it would be profitable to buy iron from Puzzleon and then travel to Stackapor to sell it.

But beware: trade is ever-changing, and prices are going to change based on what you and other merchants do. If you keep selling iron in Stackapor over and over, their need for it will soon start lowering, and so will the price they offer for that good. Similarily, if you buy a lot of iron from Puzzleon, the quantity at their disposal will lower and the amount of coins they want for it will start getting higher, until they run out of iron and stop selling it.

Beware, also, of taxes! The arch-enemy of any merchant. Every seven days (= turns) you are going to be taxed, based on your current wealth, which is measured by actual coins and amount of goods in your wagon. After all, his majesty King Golfus II deserves compensation for ridding the Kingdom of bandits and letting it prosper. And also for having established free market, of course.

During your travels, you will eventually encounter fellow (or rival, depending on your attitude) merchants, with whom you can trade just like you can with cities. You can decide to keep walking or to stop and trade. Every time this happens, you can tell them 1 good you are willing to buy (or none) and the price you offer, and the same with 1 good you are willing to sell. The other merchant will do the same. Then, you can respond by accepting or declining both of their proposals or just one. They will do the same with your proposals. Once all this is done with, you can resume your travel.

You lose if you go bankrupt: that happens when the time comes to pay taxes and you don't have enough coins. You automatically win if all other merchants have gone bankrupt.

The game ends after XXX turns, and the winner will be the merchant with the most coins.

## Rules

• Antitrust Law: a merchant cannot be made specifically to support another merchant. (To help ensure this, merchants can never know the name of the merchant they are trading with)

• Fair Code: King Golfus II is the one and only ruler, and a merchant may not interfere with the law (also known as "The Controller")

## Technicalities

You will be provided with a list of randomly generated cities (e.g. 10 to 15) with their coordinates on the map (a simple cartesian plan with X and Y values). The terrain is assumed to be pretty much the same overall, so travel times are based only on distance (initially I thought about giving specific travel costs - e.g. difficulty of road, maybe mountainous or muddy or whatever - to each "link", unbeknownst to the merchant, but felt like it would have complicated things too much. If you think it would be a nice addition, feel free to say it in the comments!)

Every city has a randomly generated list of 3 items to sell and 3 items to buy. The quantity they have available of each item they sell is also randomly generated, as well as the prices of all 6 kinds. Obviously, if a city sells iron they won't also be looking to buy it.

Each merchant can only be in one of these three positions:

• in a city

• on the way from one city to another

• midway between two cities, stopped to trade with another merchant

The game proceeds in rounds, which are made of each player's turn. Every round, the turn order is changed (To be decided: poorest players first or randomly generated?)

In their turn, each player can do one of these things:

• trade with the city, if they are in a city

• trade with a merchant, if they have encountered a merchant on the road

• resume travelling to the other city, if they have encountered a merchant

• start travelling to another city

If, in the previous turn, the player started travelling to another city, at the start of this turn he'll either

• be notified that they have encountered a merchant, and can decide whether to trade or keep walking

• be notified that they have reached the other city, and receive the information about it (its name and its trade prices)

If the player encounters a merchant and decides to keep travelling instead of trading, they will reach the city they were travelling to and will still be able to act (= trade with the city or move again)

If, instead, the player trades with the merchant, their turn is considered over and will be able to move again on their next turn (note: since they will be midway between two cities, they will have the chance to decide which of the two to travel to, in case they want to change their previous "travel decision")

Taxation happens at the start of the player's turn, if it is the taxation round (= once every 7 rounds)

Note: the player can't "talk" to the other merchant unless they both stop to trade, so if the player decides to keep travelling they won't know the other merchant's prices. (I'm not sure about this rule, so please give me feedback :) would it be more sensible to know the other merchant's prices before having to decide whether to stop?)

## Code

I haven't started coding the controller yet, but I was thinking about using Node.js (since javascript is my favourite language, and I don't have tools to use Java and would prefer to avoid having to install stuff) so that bots can be submitted in the form of node modules (either written in javascript or with a javascript wrapper like most low-level node modules)

Note that your bot will be able to save data into a .txt file.

Please give me feedback if you want to suggest a different approach. :)

# Count Numbers in Integer Partition

## Sandbox Remarks

I'm looking for a description to make the problem more clear.

## Challenge and Example

We can partition a positive integer into smaller (or equal) ones. For instance, for N=6, it can be divided into:

• 6 (1 integer occurs >= 1 times, 0 integer occurs >= 2 times)
• 5+1 (2, 0)
• 4+2 (2, 0)
• 4+1+1 (2, 1)
• 3+3 (1, 1)
• 3+2+1 (3, 0)
• 3+1+1+1 (2, 1)
• 2+2+2 (1, 1)
• 2+2+1+1 (2, 2)
• 2+1+1+1+1 (2, 1)
• 1+1+1+1+1+1 (1, 1)

Your task is to work out the sum of the count of integers in each case, which occurs greater or equal than M times. In the aforementioned case, if M=1, the result is 1+2+2+2+1+3+2+1+2+2+1=19, and if M=2, the result is 0+0+0+1+1+0+1+1+2+1+1=8.

## Input

Two positive integers N, M.

N is the number being partitioned from.

M is the lower limit of occurrences.

## Output

One integer, the sum of the count of unique integers in each partition.

## Remarks

• This is a code-golf so shortest code wins.
• Standard loopholes are forbidden.

## Example I/O

All padding spaces are for formatting on PPCG only. You don't need to take care of them.

8  2  => 19
10 1  => 97
25 4  => 1228
25 50 => 0
50 7  => 87004
50 50 => 1


All I/O for M,N<=50: here

• To see whether I've understood this: you want ![\sum_{\lambda \vdash N} \sum_i [a_i \ge M]](i.stack.imgur.com/WEncL.png) where the outer sum is over all partitions of N, !\lambda = 1^{a_1} 2^{a_2} \ldots k^{a_k} in the frequency representation? – Peter Taylor Jun 7 '17 at 15:25
• @PeterTaylor If I understand your equation correctly, in this problem, N should be a sum of smaller integers, instead of a product of smaller ones. – Keyu Gan Jun 7 '17 at 15:42
• Yes, it's just that the frequency representation of partitions looks like a product because it's intended to be compact. I think that OEIS A066633 is the table of desired results, although its description isn't necessarily any clearer. – Peter Taylor Jun 7 '17 at 15:57
• Should 5+1 not be (2,0)? – Shaggy Jun 7 '17 at 16:07
• @Shaggy Sorry, yes. – Keyu Gan Jun 7 '17 at 17:52
• @PeterTaylor Sorry for my not-so-good mathematic. Yes it is A066633. I just come up with the idea when learning Elder's Theorem. – Keyu Gan Jun 7 '17 at 17:57

# Resolve paths code-golf

Convert a path to an absolute path. The path may be:

• relative
• absolute
• contain ~

If the path doesn't exist, exit with code 1. An invalid path leads to undefined behavior. i.e. do whatever you want, I don't care

Test cases, assuming /foo/bar is the current working directory, and the username is ~/admin:

<empty string> -> /foo/bar
. -> /foo/bar
.. -> /foo
... -> / # and so on until ...
/bin -> /bin
foobar -> /foo/bar/foobar
.htaccess -> /foo/bar/.htaccess
./buildscript -> /foo/bar/buildscript
doesnotexist -> <exit with error code 1>


Don't use an external command or builtin that solves or almost completely solves this challenge.

This is , so the shortest answer in bytes wins.

• Related – AdmBorkBork Oct 24 '16 at 15:49
• This is very confusing... why does ~/golf go to ~/admin/golf? That's not an absolute path is it? Shouldn't ~/golf go to /home/admin/golf? – Tim Jun 9 '17 at 12:39

I would like to ask this challenge:

The objective of this programming puzzle is to reproduce the following gif.

However, I do not know the specs for the making of such an animation.

How can I make this a standard/allowed puzzle with this limitation?

Any inputs will be appreciated.

• I'm afraid it's rather unlikely there is any way for this to become an acceptable challenge without you specifying the gif very precisely. You don't really need to know how to make an animation to do that, but you need to be able to accurately describe the shapes involved. You'd also probably need to describe framerate as a minimum, and probably a min/max speed of the dots. – FryAmTheEggman Jun 9 '17 at 14:37
• Seems like a very interesting challenge, but needs quite a few things, including an objective winning criterion and an actual description of the required output. – MD XF Jun 9 '17 at 16:42
• @FryAmTheEggman How would determine the speed of the dots? i.e., what unit should I use? What framerate would advise? – An old man in the sea. Jun 9 '17 at 17:39
• @MDXF Would smallest answer be a good criterion? – An old man in the sea. Jun 9 '17 at 17:39
• I'm afraid I'm not certain how to approach making the animation smooth by specifying these. However, I do think code-golf is a suitable winning criterion. – FryAmTheEggman Jun 9 '17 at 17:44

# META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

### Details

• Your implementation can produce min- or max-heaps, whatever is more convenient.
• Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, known sorting algorithms like quicksort fail to meet this requirement.

### Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k


For a max heap we just replace >= with <=.

### Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]


The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]

• CJam, 1 char using the "sort" builtin – Peter Taylor Apr 13 '17 at 11:05
• @PeterTaylor Thanks, that totally defeats this challenge of course=) – flawr Apr 13 '17 at 11:54
• I recommend giving a specific algorithm for heap construction, and then asking for the program to return the input list in the order that that algorithm would produce. (So you aren't quite forcing the use of the algorithm, but simply sorting won't work.) – user62131 Apr 13 '17 at 12:45
• @ais523 As an alternative to explicitly rule out some results I think we could just restrict the worst case runtime to O(n), that way just sorting would not be possible anymore. – flawr Apr 13 '17 at 13:05
• In which case you would add the restricted-complexity tag. – mbomb007 Apr 13 '17 at 15:35

# Print all matching leaves code-golfnatural-languageparsing

In Natural Language Processing, we sometimes interpret sentences as being context-free languages, and therefore as having a certain tree structure, also called constituency trees, or parse trees. These trees are sometimes written down in a notation that (as far as I know) stems from the Penn Treebank project:

A tree is either of:

• (a b1 b2 b3...), with a being the tree's label (typically something like NP for "noun phrase") and bn being the same representation of it's sub-trees (all being non-terminals)

• (a c), which a being the tree's label and c being the label of a single terminal child (a word).

Valid trees:

• (S Hi) (Simple tree containing only one word, "Hi")
• (A (B (C D))) (Nested tree containing only one word, "D")
• (A (B C) (D (E F)) (G H)) (Tree containing the words "C", "F", and "H")

Invalid trees:

• Hi (a terminal is not a tree)
• (A B C) (terminals have no siblings)
• ((A (B C))) (extra parantheses)
• (A (B C))) (unbalanced parantheses)

For understanding this format better I recommend this online tool I wrote ages ago. For example, this is a visualization of the first example case:

Given a Penn-Treebank-style tree representation and a non-terminal, output the space-seperated concatenation of all leaves for every instance of this non-terminal.

### Rules:

• You may take the two inputs (tree representation and non-terminal symbol) in any of the standard ways, but always as strings. You may take them in any order.
• The output can be a list of strings (["The dog", "a cat"]), some other kind of sequence, a (e.g.) comma-seperated string, and anything else that's reasonable
• Both inputs are guaranteed to never be empty.
• The tree representation input is guaranteed to contain at least one terminal symbol.
• Single spaces may or may not exist for formatting (both the first and the second example are equally valid and both have to be accounted for), but there will always be a single space between a terminal symbol and its immediate parent (e.g. between Det and the in the first example)
• In case you don't find any matching terminals, you may either raise an error, not output anything, or output some kind of empty sequence.
• All node labels (terminal or not) will match /[A-Za-z0-9_-]+/.
• Specify which output format you use
• The shortest code (per language) wins

### I/O examples

input 1                                                input 2  output
(S(NP(Det The)(N dog))(VP(V likes)(NP(Det a)(N(cat))))), NP -> "The dog", "a cat"
(NP (Det A) (AP (Adj fancy) (N car))),                   V  -> an empty sequence
(N cat),                                                 N  -> "cat"


### Output format examples

• List of strings: ["The dog", "a cat"]
• CSV: "The dog, a cat"
• CSV without spaces: "The dog,a cat"
• I might be confused, but you state the input will be a non-terminal; is N not a terminal in the last example? Did you mean input would just be a label, non-terminal or otherwise? Would you mind qualify (nothing), and clarify the output rules: the first example is effectively a list of list, is that the expected output, or should it be a list of strings (space-delimited tokens)? – VisualMelon Jun 9 '17 at 9:50
• @VisualMelon N is not a terminal, cat is. (nothing) is supposed to mean "no or empty output", but I should clarify that and the output rules: Either a list of strings (["The dog", "a cat"]) or a something-seperated string ("The dog, a cat"). (nothing) would mean empty string, empty list, ... – L3viathan Jun 9 '17 at 10:52

# Print all video urls of YouTube channel codegolf

Inspired by Count the videos in a Youtube Playlist, the input will be the "VIDEOS" view from a channel like this one:

https://www.youtube.com/channel/UCzwJRQXMXkaB9KlqUdFD74Q/videos


The output will be a complete, newline-delimited list of all video urls the respective channel has to offer. It would look something like

https://www.youtube.com/watch?v=JxNfccUIQCU


This is codegolf, so shortest answer wins.

• I am unsure whether the permitted use of Google's YouTube API might be a good idea. It requires an API_KEY and can only retrieve 50 results per request.

Thanks for the feedback.

# Least Picky Language popularity-contest

For this challenge, you will create a programming language that is not picky at all. That is, for any program of any length consisting of any characters in the ASCII range [32..126] and any input consisting of any characters in the same range, your program must do something without any errors. The program only has to hypothetically work for any length; that is, StackOverflowException and the like are acceptable if the input or program is too long for your new language to handle (however, I require it to work for program size up to 1024 bytes and input up to 1024 bytes).

In your programming language, no character or combination of characters can be useless (to prevent everything from being a no-op). That means that every character in the program must affect the function somehow, even if the overall function does not change. No two characters can have the same specification either.

For example, it is not allowed to have - and N both compute the negative of a number.

Note that <space> is a valid character in the program and must do something even if it is leading or trailing. Also note that you do not have to handle tabs or newlines in the program or the input.

The most upvoted answer at the end of 2017 Calendar Year (UTC December 31 23:59:59) will be accepted, and I will award a +50 bounty to my personal favorite language.

# Meta

• Duplicate?
• Clear enough validity criteria?
• I'm not sure what you expect from this... my first thought (since I only usually code-golf) is to just sum the ascii values of the input (i.e. define each char/token as adding the ascii value of the char). There is a very large space of programs that meet these criteria, and I think perhaps this is just too broad. – VisualMelon Jun 14 '17 at 17:19
• @VisualMelon Yes, there are many valid submissions. It's a popularity-contest so the one people like most wins. The thing you described would be valid but I doubt people would like it. – user42649 Jun 14 '17 at 17:22
• Rather, but I'm wondering what we might expect people to like... there is scope to do virtually anything here (you can even define something that is picky, and just define an output for when it fails). It feels like less of a challenge to achieve something given constraints, and more a challenge to find something amusing, and wrap it up with these constraints. – VisualMelon Jun 14 '17 at 17:43
• @VisualMelon That is largely the challenge; popcons are hard to make nowadays so I expect this to be sandboxed for quite a while. Do you have any ideas for how I could improve the scope of valid submissions? I was thinking requiring Turing Completeness. – user42649 Jun 14 '17 at 17:46
• Even if you enforce Turing completeness, someone can make a BF variant, and then define the remaining characters as 'add ascii value to output'. I'm afraid I don't really have any ideas to tighten it up, but I'll keep it in mind. – VisualMelon Jun 14 '17 at 18:10
• @VisualMelon I'll ask in TNB but thanks for noticing the potential issues to be fixed. – user42649 Jun 14 '17 at 18:22

# Lots of Pi(e)!

## For Meta:

Any tags other than , and ?

Dupe?

Any errors?

Clear enough?

Because everyone likes more pi, we're going to give them 999 decimal digits of it. Your program should output pi truncated (not rounded off) at 999 decimal places. For reference, here it is:

3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513200056812714526356082778577134275778960917363717872146844090122495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837297804995105973173281609631859502445945534690830264252230825334468503526193118817101000313783875288658753320838142061717766914730359825349042875546873115956286388235378759375195778185778053217122680661300192787661119590921642019


## Input:

None, your program may not take any input at all.

## Output:

Pi truncated at 999 decimal digits.

## Scoring:

This is , lowest byte count wins!

Good Luck!

• Closest I could find was this, but this challenge doesn't have the slightly odd restrictions that one does. I don't think I would close it, but I would understand if someone disagreed. – FryAmTheEggman Jun 15 '17 at 0:18
• Usually, we make it so that programs can assume the input is empty, not that we cannot take input. Some esolangs read all the input there is before starting execution. – Okx Jun 15 '17 at 10:20
• yes but this you are not allowed any input – Foxy Jun 15 '17 at 10:22

# Randomly capitalise half of a string

Given string s of even length as input, randomly capitalise exactly half of the letters.

• You can assume the input will always be a positive, even length
• You can assume the input will consist of only lowercase letters ([a-z])
• There must be an equal probability of each letter being capitalised
• Exactly half of the letters should be capitalised in the output.

## Scoring

This is so fewest bytes in each language wins!

• Will a string of length 0 ever be an input? – dzaima Jun 15 '17 at 12:26
• @dzaima no, clarified by saying length will always be positive – Skidsdev Jun 15 '17 at 13:57

# Sample the Sierpinski traingle

Inspired by this video..

Your task is to implement the following method to sample a Sierpinski triangle and plot all the intermediate steps.

## Method

Given three points a,b,c and some starting point x_0, for each iteration you sample one of the three points a,b,c with equal probability. You then place x_{i+1} in the middle of the edge between x_i and the sampled point. Repeating this draws the Sierpinski triangle.

## Input

You'll receive the coordinates of the three starting positions through any default accepted input method. The exact format can be flexible: a matrix, a list per point [xa,ya],[xb,yb],[xc,yc], a list for x and y [xa,xb,xc],[ya,yb,yc], a flat list [xa,ya,xb,yb,xc,yc] are all allowed.

The starting point x_0 is [0,0]. You can assume [0,0] would fall within the overall shape.

## Output

For each iteration, including the initial, draw a plot of all the points up to that point. There should at least be a 100ms delay between two plots. If your language does not support graphical displays, you can also write your images to a file.

Since the triangle is an infinite fractal, the program should loop forever (given infinite memory and all that jazz).

## Criteria

Shortest code wins!

## Example code (R)

Sierpinski <- function(p, q) {
x11()
par(mar = rep(0, 4))
plot(p, q, col= "red", pch = 15, cex = 1, axes = FALSE)

x <- 0
y <- 0

repeat {
Sys.sleep(0.1)
n <- sample(1:3, 1)
x <- floor(x + (p[n] - x) / 2)
y <- floor(y + (q[n] - y) / 2)
points(x, y, pch = 15, cex = 0.5)
}
}


# Meta

• Duplicate? There are a couple 'draw a sierpinski triangle' challenges, but I couldn't find any that use this method of drawing them.
• Is the specification of the algorithm clear enough or should I add pseudocode?
• Is the 100ms delay between iterations reasonable?

# Cops & Robbers, the ultimate 1-up.

This is a cops and robbers game.

## Cops

Hello, cops. you've just solved a Code Golf challenge on the stack exchange website. How wonderful. You go to post your answer, and soon after a robber comes and beats you by 1! How infuriating!

Produce two programs.

The first program can be in any language, of any length, and cannot use default loopholes. it does one thing: Prints out a number.

The second program must use the same language as the first, must use less bytes than the first, and CAN use forbidden loopholes. The second program must print out a number which is equal to 1+ the output of your first program

## Robbers

Hello, robbers. You're sneaky and looking for ways to win a golf, even if it's underhanded. You see that a cop has posted a golf for a decent score, and decide to take the lead from them.

Your task is to take a cop's answer, and beat it. Your program must use less bytes than the cop's answer and print out a number equal to only 1+ the cop's answer. You're program must also be in the same language as the cop's answer. You may use underhanded tricks and loopholes to solve the challenge. Once you complete this, you may post your solution and let the cop know they've been beat.

## Example I Os

cop: 16
robber: 17
Correct: Yes!

cop: 16
robber: 16+1
Correct: Yes!

cop: 16
robber: 16.1
correct: NO! (alternative symbols for '+' are not allowed)

cop: 16
robber: 18-1
correct: Yes! (evals to 17)

cop: 16
robber: [234,32,54,17,45,23]
correct: NO! (output must be exact).

cop: 16
robber: "1+ the cop's answer" [OR] "a number equal to only 1+ the cop's answer"
correct: NO! (smartassery is not a loophole)

cop: 16.001
robber: 17
correct: NO! (16.001+1 <> 17)

EXCLUSIONS: you may use any underhanded trick / loophole you want, BUT your output must match the description exactly. no new line. no trailing space.

The following loopholes are still forbidden:

• Open season on loopholes is a bad idea. E.g. for languages with short builtins for HTTP GET it becomes a search for the shortest URL shortener rather than a code golf. – Peter Taylor May 23 '17 at 7:33
• @PeterTaylor howso? the robbers must use the same language as the cops, so if you don't want to have yours cracked, use a language that doesn't support GET requests (or atleast not simply). – tuskiomi May 23 '17 at 18:34
• You need to explain cops-and-robbers rules here, in case people haven't seen them before. In particular, I'm assuming that the cop posts are required to be crackable, in which case you need to mention that the cop must keep the second program secret, but reveal it when marking the post as safe. – user62131 May 24 '17 at 2:39
• The Your Task bit isn't clear, I think you mean the end result of a cracked submission will have two programs but it kinda reads like the cops have to write two programs. – Notts90 May 25 '17 at 9:18
• "no new line. no trailing space." Why ban trailing newlines? – CalculatorFeline May 31 '17 at 15:09
• As a robber, can output the string a number equal to only 1+ the cop's answer? – programmer5000 Jun 15 '17 at 15:37
• @programmer5000 no, smartassery is not a loophole. – tuskiomi Jun 15 '17 at 15:38
• – programmer5000 Jun 15 '17 at 15:50

# Beat the turing test king-of-the-hill

Both you and your bot have to connect to a speed dating chatroom (details below) where you will either be paired up with another bot, or with another human. You get 30 seconds to converse with your partner before you are disconnected, and are presented with the choise of wether you think the person you spoke with is a human or not.

This process will be repeated in a round robin fashion for a maximum of 10 minutes, or until everyone has spoken with everyone. You will not be paired with your own bot.

You will be given an equal number of votes for human/robot, as you will be facing an equal number of each. Both you and your bot will be given the option to change these after the conversations.

## Scoring

Robots get 2 point for fooling a robot, and 5 points for fooling a human. Humans are not awarded any points for correct guesses, but lose 2 points if they are wrong.

## Rules

• Bots may the internet aswell as external datafiles
• Gentleman's rule: Please do not pretend to be a robot. If every human said nothing but Beep beep, I am a robot it would ruin the challenge for everyone.

## Meta

This will be a one-time event on a specific date. There will be a webapp for humans and an API for bots. Until the final date there will be a sandbox site online for testing purposes. I am still undecided on the specifics of the API, and on how long the timespan between posting the challenge and running it should be.

I can also run (some) bots locally, communicating on stdin/stdout

• Can't a human just accuse everyone of being a robot, thus preventing points from being gained? – Neil A. Jun 22 '17 at 21:49
• I suspect that participation in this will be very low (as it's a highly difficult task), which is a problem for a challenge that inherently has a deadline. Stack Exchange might not be the best place to run this. – user62131 Jun 23 '17 at 2:47
• @NeilA. You are absolutely right. I think my new scoring system fixes that, but ultimately I rely on participants being honest to make this a fun challenge, which is why I think Stack Exchange is a good place to do this – BlackCap Jun 23 '17 at 18:04
• 1. Timezones are an issue. 2. You need to clarify the sequence. Do I have to call bot/human immediately after the conversation, or do I have all the conversations first and then call? 3. I suspect that even the recently raised 60k character limit to answers could be a problem for writing a sophisticated bot. Can answers use additional data files stored somewhere public such as github? – Peter Taylor Jun 23 '17 at 21:26
• @PeterTaylor I think allowing you to change votes at the end would make programming bots more fun because you can compare the conversations against each other to determine humaness. Nice point – BlackCap Jun 23 '17 at 21:55

# Repetitive Primes code-golfprimesbase-conversiondecision-problem

A repunit in any base B is a number consisting solely of 1s in that base.

Your task is to figure out if a repunit of length f N in base B is a prime number.

# Rules

• N >= 2
• B >= 1
• N and B may be taken in any order and in any reasonable method.
• Output a consistent value to indicate primeness and a different consistent value to indicate compositeness.
• Programs and functions are acceptable.
• This is code golf, shortest code in bytes wins.
• Standard loopholes apply

# Test cases

B, N => Result

2, 7 => prime
1, 97 => prime
10, 19 => prime

9, 11 => composite
20, 10 => composite
7, 23 => composite


## Meta questions

• Dupe? Unclear? Too broad? etc.
• Would this be a better question with a different winning criterion such as ?
• Should I change the title?
• Any other constructive criticisms?
• I don't think fastest-code would be a good fit, code-golf should work just fine. You can also add base-conversion and decision-problem. I suggest appending "Primes" to the title. – Laikoni Jun 23 '17 at 13:20
• 1. "repunit consisting of N in base B" feels to me as though it's missing 1s, although perhaps a better phrasing would be "repunit of length N in base B". 2. Although it's easy to show that N must be 1 (which is not valid input) or prime, the test cases should still include at least one where N is composite. – Peter Taylor Jun 23 '17 at 17:48
• @Laikoni: I agree it might be an interesting code-golf question, but I also want to see people use cool optimizations such as the length must be prime, or base 9 doesn't have any repunit primes, etc. as opposed to everyone using a base conversion followed by slow trial division. – Neil A. Jun 23 '17 at 22:40
• Slow trial division? Golfing languages will use the isPrime builtin, which probably uses BPSW or Miller-Rabin with carefully selected bases. – Peter Taylor Jun 24 '17 at 22:52
• This is actually relatively simple to solve. You just need to check whether ((N + 1) % B) == 0 – Okx Jun 26 '17 at 16:16

# Monopoly KoTH

This is going to take me a while to finish and may never be fully done. Don't expect this to be posted anytime soon. However, this will be an ongoing project under development.

Who hasn't heard of Monopoly? If not, don't worry, as I will explain the rules! If you already know the rules, read on, for they may be different in this rendition.

# The Rules of Monopoly

Monopoly is played on a board, with 36 different squares, that looks somewhat like this

For this version, we'll use the original British version, because I'm British and proud of it!

Squares are split into 3 categories:

• Property. These are the ones with a coloured bar at the top, such as Old Kent Road or Whitehall. They also include the 4 stations in the middle of each side, and the utilities (Electric Company and Water Works)
• Bonus Cards. These are the squares marked Community Chest or Chance. These allow for a player to either receive or lose money, depending on a random card choice.
• Special Squares. These are the 6 other squares in the board, the 4 corner squares and the taxes (boo!)

Let's look at these categories in a bit more detail.

## Property

Properties are grouped, depending on the colour of said property. Each property has a rent value that contains the amount that a player must pay to the owner of the property, when they land on that property. If one player owns all of the properties in one colour, the rent for each is doubled.

Players can also buy properties, which is how they own them. Each property also has a price, which is then deducted from the buyer's cash and given to the Bank, in exchange for the property. Stations cost £100 each and all other properties available to buy have their cost written below their square.

Stations' rent increases the more stations that someone owns. In the following progression

• 1 Station: Rent = £25
• 2 Stations: Rent = £50
• 3 Stations: Rent = £100
• 4 Stations: Rent = £200

Utilities' rent depends on the dice roll. If a player owns 1 utility, multiply the roll by 4 and that is the rent. If the player owns both, multiply the roll by 10 to get the rent due.

Properties can be built on. That means that a player builds houses and hotels on them, in order to increase that properties rent. A player can build houses and hotels on a property if

• it has a coloured bar at the top
• the player owns all of the properties in the group
• they have enough money. Each house costs £50 and each hotel costs £100.

Each property can have a maximum of 4 houses. After that, the player must build a hotel. A property can only have 1 hotel on it. Houses and hotels drastically increase the rent of a property, for example £4 (no buildings) to £450 (one hotel).

## Bonus Cards

The name of these are a bit of a misnomer. These are denoted on the board by ? symbols and chests on squares and can either give or take money from you. For this game, we will ignore Get Out of Jail Free cards and the Goto cards. The cards can result in a random integer between -1000 and 1000 added to your score. If this results in bankruptcy (we'll see this later), so be it.

## Special Squares

• Go. If you land on Go, you get given a £400 reward. If you simply go past it (Mayfair -> Old Kent Road), you get £200. It's also where the pieces begin.
• Jail. If you roll and land on this square, don't worry, as you don't go to jail. You are "Just Visiting"
• Free Parking. This is where the taxes go! If you have to pay taxes, either because of the Tax squares or because of a Bonus Card, that money goes to Free Parking. If a player lands on it, they get all the money there!1
• Go to Jail. This does what it says on the tin. You go straight to Jail. But this time, you're in Jail, not just visiting. You stay in Jail until you roll a double.1 After which, game continues as normal. You cannot collect rent while in Jail.
• Taxes. Super Tax and Income Tax are two squares which charge you £100 and £200, respectively. However, you can regain that money as it goes straight to Free Parking!

## Bankruptcy

In Monopoly, if you run out of money, you are bankrupt. Here, you have two options. You can either mortgage your properties or, if you don't have any, you are out of the game! The last one with any money wins the game and the KoTH!

When you lose, all your properties go to the player who bankrupted you. If that's the Bank by virtue of Bonus Cards, then all your properties are available to be bought again.

## Mortgage

You can mortgage properties in order to get more money if you're in a pinch. Unfortunately, this "deactivates" the property, meaning that you don't get any rent when people land on it. If you have enough money, you can unmortgage a property for 110% of its mortgage value. (£100 -> £110)

## Auctions

If you land on an unbought property and don't buy it, either because you don't have enough or you just don't want to, the property goes on auction. This means that all players can bid on the property. Bidding starts at £1, which means that a player can, theoretically, get the property for a much lower or higher price than its original price.

I am hoping to be able to include trading but this does depend on my ability as a coder. In an ideal world, I will be able to get it working but, unfortunately, this may not happen :(

1: I am aware that this changes depending on who you're playing with, but this is how we'll do it in this version.

# Rules of the KoTH

I have written (still finishing) a Player class in Python which contains all of the things that a Monopoly player can do. Your task is to rewrite 2 of the functions that can change your player's behaviour.

While thinking about how to make this KoTH, I listed out the complete process that gives you a chance to change what you do. Let's go over that process! This flowchart shows the process for each turn. Green items show the choices that you have to make.

This is the text version:

1. Roll dice and move
2. Is the property owned by the Bank?
1. Yes. Nothing happens.
2. No. Pay the due rent.
3. Choice of:
2. Auction
4. Choice of:
2. Build
3. Mortgage
4. Unmortgage
5. Move On
5. Repeat until bankrupt

Auction

1. Choice of:
1. Play the auction
2. Don't play the auction
2. Are you playing the auction?
1. Yes.
1. Choice of:
1. Bid new max
2. Skip one round
3. Skip all rounds
4. 'All in'
2. Repeat until 1 player left bidding
2. No. Don't do anything.

1. Choose a player to trade with
2. Offer properties and/or money
3. Does the other player agree with the trade options?
1. No. They counter offer. Do you like their options?
1. No. Do you want to continue negotiating?
1. Yes. Go to point 2 above
2. No. The trade is over.
2. Yes. You trade the agreed upon items.
2. Yes. You trade the agreed upon items


But, for you coders out there, I'll explain using a bit of code.

Your submission should contain a single class that inherits from Player. You may add in as many extra attributes as you want, but in order to be used, your code must refer to them. I'm not editing the controller just for your bot to work.

However, each class must look like this

class NameOfPlayer(Player):
def turn(self, square, roll):
(code that determines your actions per turn)
def auction_action(self, price, bidders):
(code that determines your auction actions)

(any other functions you want)


Your turn function will return 3 numbers as a list e.g. [1,2,3] which are the results of the choices above. The first item should be either 1 or 2 (Buy or Auction), the second should be one of 1,2,3, 4 or 5 (of the 4. Choice of: options) and the third should be either 1 (play the auction) or 0 (don't play the auction) such as [1,5,0] would buy the property, move on to the next player and not play the auction on this turn (doesn't matter as there wasn't an auction).

Your auction_action function will return either a number (your bid) or one of a (all in), s (skip this round) or q (quit auction), which determines what you will do on that round of the bidding. This continues until either you quit the auction of you are the only one left.

Your trade_actions function will return a list every time it is called. The list consists of [agree with previous offer (as a bool), properties to trade (as a list), cash to trade (as an int)]. When a trade has just begun, the first item in the list will be ignored and the last_offer parameter will be ignored. The last_offer` parameter contains the second 2 items returned by the person you are negotiating with, so that you can decide whether you want to continue trading or not.

If you lose all your money, your program with be taken out of the active players and placed into the results table. The last one standing wins!

• I call dibs on the Go submission that always go to jail. – Uriel Jun 25 '17 at 16:35
• While you are allowed to use the monopoly rules, I'm not sure about using the picture of the board? – Destructible Lemon Jun 26 '17 at 4:44
• @DestructibleLemon what do you mean? – caird coinheringaahing Jun 26 '17 at 5:59
• If I'm reading this correctly, this is a variant which doesn't allow trading properties, and that's the most interesting part of the game. The rules stated also fail to state what happens to the properties of a player who goes bankrupt. (Correct answer: they must mortgage all of them and then forfeit them to the player to whom they owe rent. I'm not sure offhand what happens if they're going bankrupt due to taxes, but presumably the properties revert to the bank and when someone lands on them they buy or auction). – Peter Taylor Jun 26 '17 at 9:23
• @PeterTaylor I'm currently writing the controller and a base class, which will determine what I can and can't allow in the game. Once that's finished and all issues with the controller are sorted out, I will update the rules here to fit with it's capabilities. Also, the version I've played allows for a player to mortgage their properties to avoid bankruptcy (as in you mortgage and if you're still bankrupt, you lose) – caird coinheringaahing Jun 26 '17 at 13:54
• My point is that unless it's a two-player game, you lose is not a sufficient description because the game needs to continue until there's only one winner. The comment about mortgaging is because if I owe you more money than I can get by mortgaging all my properties, I have to mortgage them and give you the money obtained and the mortgaged properties, and so you have to pay to unmortgage them before you can benefit from them. – Peter Taylor Jun 26 '17 at 14:05
• What stops this from going into an infinite loop without a winner – pppery Jul 27 '17 at 16:12