# Sandbox for Proposed Challenges

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

Sandbox FAQ

## Posting

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

## Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

• Parts of the challenge you found unclear
• Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

## Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Get the Sandbox Viewer to view the sandbox more easily!

Goal

The goal is to stitch several ordered lists of numbers into a single list that contains each of those lists as a contiguous sublist, with the numbers in the same order without gaps. The resulting list should be as short as possible.

Input

n ordered lists of numbers between -2^63 and 2^63-1

Ouput

A minimum-length list so that each input list appears within that list with its elements in the same order without gaps

Example

Input:

[1, 2, 3] [3, -38, 23424, 292] [0, 1, 2] [-38]


Output:

[0, 1, 2, 3, -38, 23424, 292]


The output contains each of the input lists:

[0, 1, 2, 3, -38, 23424, 292]
[1, 2, 3]
[3, -38, 23424, 292]
[0, 1, 2]
[-38]

• Many languages have built-ins both for flattening a list of lists and for removing duplicates, giving them a straightforward solution. I think that makes this too easy overall. The removing duplicates part is like this challenge, though it uses characters and requires preserving order.
– xnor
Oct 30, 2015 at 21:26
• But it is not only about removing duplicates, but also about finding the perfect combination of lists, so you have to figure out in which order you want to put the input lists together. Also it might be necessary to have duplicates in the output to be able to have all input lists in there. Oct 31, 2015 at 7:13
• Oh, my mistake, I didn't realize the lists had to appear as contiguous subsequences. Let me edit that to try to make it clearer.
– xnor
Oct 31, 2015 at 7:18
• Out of curiosity, I found notes about this as an algorithmic problem, and it's NP-hard, so solutions are going to be exponential time. It would do good to include some test cases that a greedy algorithm would get wrong.
– xnor
Oct 31, 2015 at 7:29
• Looks like we already have this challenge.
– xnor
Oct 31, 2015 at 8:53
• Good catch. It's indeed the same problem. Thanks for pointing that out! Oct 31, 2015 at 9:03

# Hello, World! Fitted in cases.

Your task is to take a line of input and print Hello,world! multiple times fitted to length of input. The cases of that character is fitted to input in same position(except shifted from deletion). If the corresponding character is non-alphabeth, you must use default case(lowercase except for "h" that is uppercase). And for punctuations, if the corresponding character is not punctuation, it will deleted. And if the corresponding character is space, the the ouput is space but it doesn't skip the "Hello,world" writing.

## Example

Hello, world!
Hello, world!


About punctuation deletion and space insertion

I have a dog. I name it Underdog.
H ello w orld H ello wo Rldhellow


Explanation

Ihaveadog.InameitUnderdog.
Hello,worlD!hello,world!hellow
Helloworld!hello,World!hellow
HelloworldHello,wOrld!hellow
HelloworldHellowoRld!hellow
HelloworldHellowoRldhellow


Other examples

.....&^&%&*%&(&)^$#()&#()&@#)*%)#1- Hello,world!Hello,world!Hello,world UPPERCASES HELLOWORLD lowercases helloworld Abdeg,fGhiJ. Hello,wOrlD!  ## Example Program Here is ungolfed version of example program in Python. If there is error, correct me. p=readline() h="Hello, world" i=0 k="" for a in xrange(len(p)): if p[a]==" ": k=k+" " continue if isUpper(p[a]): if isAlpha(h[i]): k=k+upper(h[i]) i=i+1 continue if isLower(p[a]): if isAlpha(h[i]): k=k+lower(h[i]) i=i+1 continue k=k+h[i] i=i+1  ## Sandbox Question This language is surely need to be fixed. # How am I doing? My boss is a flashy sort of fellow. He likes all things animated. He's asked me to write a progress bar to show the completeness of our super-secret project. Now with me being me, I'm getting you to write this for me and showing the best one to my boss. ## Task • Output a progress bar to stdout. • Whenever a newline is sent to stdin, increase the percentage on the percentage bar by 1% • If not already enabled and if possible in your language, set the terminal mode to non-echoing (stdin doesn't automatically get shown, think like when your typing in your password for sudo) • You may not assume the cursor is in a certain position, it must produce a progress bar relative to where you started the program (no absolute jumps) To help you, you may use ANSI escape codes, ANSI colour codes and any UTF-32 unicode points. The winner is the entry with the most upvotes. ### Sandbox Notes: • Is this too broad? - I'm sticking to ANSI only but I'm not saying anything else about what it looks like. • Anyone care to say why this is worth a downvote? – Blue Nov 2, 2015 at 17:12 • Popularity contests tend to attract them (even the good ones). Nov 3, 2015 at 19:47 • This doesn't seem very tightly defined. Generally, the broader a popularity contest is, the more I expect it to gather downvotes. Nov 3, 2015 at 19:48 • Also, a simple requirement means most of the popularity of an answer will come from optional extras rather than meeting the spec. See the line between art and programming for other's thoughts on this. Nov 3, 2015 at 19:50 • Thanks for the link, I think I'll just let this question die here (I'm not sure if I should delete it or not, I'm going with not deleting it unless someone else says otherwise) – Blue Nov 3, 2015 at 19:57 • I usually delete my challenges once I know for certain I will not post them, but for ones I (or someone else) might be able to salvage in future I leave them around. Nov 3, 2015 at 19:59 • I don't think this one is ready for main, but remember that here (as on main) a lone downvote doesn't really mean anything. It could be anyone for any reason - rational or otherwise. Nov 3, 2015 at 20:00 # Kaprekar Transformation Kaprekar Transformation is an transformation a number by following that instruction: 1. Take n-digit integer. 2. Sort it anscending and descending. 3. Subtract the largest number and smallest number. Your program have to do this: 1. Take 1 number, x. 2. Output all possible cycle and fixnums for doing repeated x-digit Kaprekar Transformation on all possible input. Rotation is considered same. So it is invalid to print: [00],[09,81,63,27,45],[81,63,27,45,09] The output is a list consisting of list representing the cycle. You may using any style of list and even intermix it with restriction that it should not be ambigous. For example, comma separated item with item using comma separated item with enclosing bracket is OK, but not comma separated item with item using comma separated item without enclosing bracket. Example: 8 >[00000000],[43208766,85317642,75308643,84308652,86308632,86326632,64326654],[63317664],[64308654,83208762,86526432],[97508421]  Or >[00000000],[[43208766,85317642,75308643,84308652,86308632,86326632,64326654],[63317664],[64308654,83208762,86526432],[97508421]]  • I'm afraid this is a duplicate: codegolf.stackexchange.com/q/2762/8478 ... also, for future reference, requiring one specific list format is bound to put an arbitrary set of languages at a massive advantage (those which can just use their native string format), while all others may have to do some non-trivial string processing which distracts from the (interesting) core of the challenge. Nov 2, 2015 at 12:56 • @MartinBüttner No, it is the generalization. You have to handle arbitrary digit this time. And you have to detect cycle and find all cycle given a digit. Btw, there is typo. 2 39 is different example. Nov 2, 2015 at 13:04 • Task one seems to be identical. The fact that the other challenge only has to work with 4-digit numbers doesn't seem substantial. I'm pretty sure almost any answer there can be adapted to a variable number of digits in a couple of bytes. As for Task 2, I did overlook that. You could simply reduce the challenge to just task 2 (I'm not even sure why you'd combine two independent tasks into a single challenge?). Even task 2 can be solved by simply looping the solution to task 1 over all possible X-digit numbers, but there might be other ways to golf this one. Nov 2, 2015 at 13:07 • @MartinBüttner Then, why it isn't duplicate of codegolf.stackexchange.com/questions/1255/hitting-495-kaprekar ? Nov 2, 2015 at 13:14 • Because it has been overlooked, I suppose. Fixed. Nov 2, 2015 at 13:15 • @MartinBüttner Maybe add time limit make this different enough. Nov 2, 2015 at 13:15 • I don't know. Since you have to output the entire list anyway, there is not much you can optimise beyond actually applying the transform until you hit a cycle. If you limited the challenge to the second task, a time limit might make more sense, but then again the second task might be different enough not to be a duplicate in the first place. Nov 2, 2015 at 13:17 • @MartinBüttner Then remove task 1 and it won't be duplicate? And add speed limit. Nov 2, 2015 at 13:29 • I don't even think a time limit is necessary for part 2. Nov 2, 2015 at 13:30 • @MartinBüttner Is Task 1 still have to deleted. And please, don't discuss in the Chat, because I can't access that. Better use my email: christianirwanhw@gmail.com Nov 2, 2015 at 13:57 • As I said above, I don't see why you would want to squeeze both tasks into a single challenge in the first place. (How would you score answers? Sum of the two solutions?) And if you split them up, then the first answer is certainly a duplicate, but the second is fine (and if you didn't split them up, I don't see why you'd redo the same challenge as part of another challenge either). Nov 2, 2015 at 13:59 • The cycle identification is borderline duplicate of codegolf.stackexchange.com/q/26578/194 Nov 2, 2015 at 14:32 # Stupid leaks Considering how immensely successful my last two challenges have been, I'll do a different style this time. Drip, drip, drip, drip... It's the year 3000. Due to clean air shortages, a system was created that turns water into air. However, that caused a water shortage (don't you love progress?). Therefore, a new (expensive!) system was created to convert the air back into water. All that to say that water prices have skyrocketed. And yet, here you are, stuck with a leaky faucet. Plumbers are expensive, but if you do it yourself, you have to order the parts online and wait for them to get here. You need a way to determine what is cheaper: calling a plumber and getting it fixed in a day, or buying the parts online but having water leak until they get here. ## The input You need to take seven positive numbers as input: • The price of water per gallon g. • The number of drops leaking per hour d. • The number of gallons wasted per drop z. This will always be a floating-point number less than 1. • The price of calling a plumber to fix it p. • The price of ordering the parts online o. • The number of hours it takes for the plumber to fix the leak l. • The number of hours it takes for the parts to get here s. Only g, z, p, and o can be floats; all the rest will be counting numbers (integers greater than 0). ## The task The gallons of water wasted per hour from the leak is d*z*g. For the sake of brevity, let's call that rate R. If R*l+p is less than R*s+o, then you should print/return DIY!. If greater than, print/return Call the plumber!. If equal, print/return Whatever.... ## Precision Floating-point precision through calculations is very...weird. Basically, your program can use whatever your language's default is. If you're using a language where the default floating-point type has infinite precision. If your language's default floating-point type can lose precision throughout calculations (like in Python, where .1+.1+.1+.1+.1+.1+.1+.1 != .8), then that works, too. Short version: floating-point semantics and precision are however your language is by default. ## Scoring Code-golf. Shortest wins. Standard loopholes banned. • What is a "counting number"? Does it include 0? You also might want to specify at what precision the equality will be checked (presumably hundredths?), and how rounding should be handled for the "Whatever..." case. Nov 2, 2015 at 18:24 • @FryAmTheEggman Is this better? Nov 2, 2015 at 21:03 • My language doesn't support floating point at all, so can I always just output Whatever...? More seriously, I'm failing to see the point of this question. Do some trivial arithmetic and then output one of three strings which between them take up 90% of the code? Nov 2, 2015 at 21:15 • I think it is better, but I think you do have to spend a bit addressing Peter's comment about languages that don't support floats. Nov 2, 2015 at 23:55 # Show How a Regex Is Matched What your program or function should do: 1. Accept input of two strings; let's call them r and s. 2. Determine whether r is a valid regular expression (you can use any common definition of regex for this purpose, or any common definition of regexes but with lookahead and lookbehind removed; indicate which you're using). Otherwise, don't output. 3. If so, determine whether s matches r as a regex. Otherwise, don't output. 4. If so, output/print, in order, the part of r matched by each character of s, and also the part of s that matches it. Note: You may use your language's regex-matching library for this. Example: Using PCRE; my inputs and outputs are r first and then s. ^.el*(o.*)*d\b and Hello, world! ^.ello......d\b and Hello, world .\1\W and 800-555-1212 ..\W and 00- \b and a \b and empty string \d and a no output (it doesn't match) First floated in chat. Not a dupe of Compile Regexes (which asks you to match regexes whereas this allows you to use the resources of your language to do so). • 1. It sure looks like a dupe to me: what's your argument for it not being a trivial transformation of the previous question? 2. In your examples, you seem to try to draw a distinction between outputting the empty string and not outputting anything. How does that work? 3. What exactly is the output format? E.g. the first example and the second example don't seem to be consistent in their treatment of metacharacters. Nov 5, 2015 at 22:49 • @PeterTaylor 1. It's not a dupe at all: the older question asks you to match regexes whereas this allows you to use the resources of your language to do so; also, the older question outputs a means of determining matching, without regard to how it's matched, whereas this requires an output of the latter. 2. This question is OBE because of the edit I'm doing to fix #3. 3. Yeah, I messed up an example: I'll fix that immediately. Nov 5, 2015 at 23:05 • 1. With respect to the second half, see "simple transformation". But the first half is relevant, and worth editing in to the "Not a dupe" sentence. 3. I still can't figure out the output format from the examples. Obviously you want to ensure that it's not as trivial as asking the regex engine for group 0, but I think you need to first write a clear spec for the output and then write the examples (or, better, write a reference implementation to generate the examples). Nov 6, 2015 at 7:27 • @PeterTaylor, yeah, I'll have to work on it some more. If anyone else has ideas, please chime in! Nov 6, 2015 at 9:24 # Python assembler Python is a hybrid interpreted language. It first gets compiled into byte-code and then gets interpreted. What does this byte-code look like you may ask? The dis module disassembles python code. Source code for dis module here print "Hello, World!"  Gets disassembled into the following assembly.  1 0 LOAD_CONST 0 ('Hello, World!') 3 PRINT_ITEM 4 PRINT_NEWLINE 5 LOAD_CONST 1 (None) 8 RETURN_VALUE  The output is divided in the following columns: 1. the line number, for the first instruction of each line 2. a labelled instruction, indicated with >>, 3. the address of the instruction, 4. the operation code name, 5. operation parameters, and 6. interpretation of the parameters in parentheses. The disassembly of a basic for loop for i in range(10): print i  gives  1 0 SETUP_LOOP 25 (to 28) 3 LOAD_NAME 0 (range) 6 LOAD_CONST 0 (10) 9 CALL_FUNCTION 1 12 GET_ITER >> 13 FOR_ITER 11 (to 27) 16 STORE_NAME 1 (i) 2 19 LOAD_NAME 1 (i) 22 PRINT_ITEM 23 PRINT_NEWLINE 24 JUMP_ABSOLUTE 13 >> 27 POP_BLOCK >> 28 LOAD_CONST 1 (None) 31 RETURN_VALUE  ## Your task: Given some python code that has been disassembled, recreate the original code object as close as you can. You can take the disassembled code through any method you chose. Your program will output all the arguments to recreate a python code object That is to say your program will output the following 0, 0, nlocals, stacksize, 0, codestring, consts, names, varnames, "a string here", "another string here", 0, lnotab, (), ()  You can work out the variables listed above but you have to output it all, even the constants. • nlocals - The number of local variables • stacksize - The maximum number of values held on the stack at once • codestring - A binary containing all the opcodes and their arguments • consts - A tuple of constants • names - A tuple of global variables • varnames - A tuple of local names (length of nlocals) • lnotab - A tuple containing a map of bytecode positions to line numbers You may use the following code to disassemble a .pyc file: import sys, dis, marshal with open(sys.argv[1], "rb") as code_f: code_f.read(8) # Magic number and modification time code = marshal.load(code_f) dis.dis(code)  This is code-golf, the shortest code in bytes wins ## Sandbox notes Wow that was a long one. Perhaps too long? Is the spec completely tight? Should I explain anything further? Am I making it too hard for non-python entries to take part? Should I only make it a requirement to reassemble code without any functions/classes? I'm pretty sure dis doesn't show all that. • For one thing, yes this looks very hard for non-Python entries to me. For another, I think there's too much going on at once (there's a lot to output), and you don't explain much about how to output each specific component (ideally the post should be self-contained enough to work out what to do without knowing too much about Python/dis) Nov 9, 2015 at 15:41 # Print a sourcecode Given 2 inputs(First input is truthy/falsy, second input is program in same language as submission): 1. If the first input is truthy then transform the second input into same program but printing the source code(After modification) first. 2. If the first input is falsy then transform the second input into same program but after the program finished it prints the source code(After modification). If the program doesn't halt, you may or may not modify the program. It's code-golf, so the shorter answer is the winner. For example in CJam, I don't write the program to do this. (> means output) 0 q >{"_~"q}_~ 0 0 1{_@+}11*; >{"_~"0 0 1{_@+}11*;}_~ 1 q > {q](\o"_~"}_~  • Sorry, I'm not quite sure what this question is asking. Would it be okay if you posted examples? Nov 5, 2015 at 14:29 • @Sp3000 Please undo your downvote. The example is fixed. Nov 7, 2015 at 7:39 • I didn't downvote though... Nov 7, 2015 at 8:13 # Vigenère Cipher Write a program that is capable of breaking a text encyripted using Vigenère cipher encyription. ### Goals: • Take encripted text from STDIN and write plaintext to STDOUT. ### Limits • Keyword will always be 3 letters in length. • Plaintext will always be in between 5-10 letters in length (inclusive). • All Plaintexts, Keywords and Encyripted Texts will be in English. ### Scoring: This is a . Shortest code in bytes wins. I'm not sure if this is a valid and solvable question, so any suggestions are welcomed. • Dupe – user45941 Nov 10, 2015 at 18:19 • I'm not sure this can actually be done without having a big dictionary for such a short piece of text. (Also, what does "encrypted texts will be English" mean?) Nov 15, 2015 at 15:01 • @PaŭloEbermann It means they will only contain english characters, no special letters from other languages. Nov 15, 2015 at 15:12 • Then write "consist of the letters A-Z" instead (or similar if you allow spaces and punctuation – though that needs more specification). Nov 15, 2015 at 15:14 • For Vigenere, in general you can either try a "plaintext dictionary attack" (which means you'll have a list of valid plaintext words, like in the question linked by Mego – that would be a plain duplicate), or you try analysis of character frequencies or repetitions, which need a lot longer ciphertext in order to analyze anything useful. (Or you just output all possible plaintexts, and let the task of recognizing the correct one to some human.) Nov 15, 2015 at 15:19 # List Style Converter [code:golf] ## Task Given a list, format it into list of the choice of the input. The list will be list of item defined below, but it can be multidimensional. ## List Styles There is 2 list separators: 1. Space 2. Comma For one dimensional list, only one separator is accepted. Space and only space between item is considered as separator. It is impossible to have more than 2 dimension without enclosing list of second dimension or third dimension. when parsing list, comma takes lower precedence and it is parsed with least dimension as possible. Space is optional between ] with [; } with {; and ) with ( There is 3 list enclosure: 3. [...] 4. (...) 5. {...} Closing bracket must be present. ## Item There is 2 types of item, another list or those following regex [0-9a-zA-Z]* or everything enclosed with single quote or double quote. If enclosed with single quote, it can contains double quote and vice versa. There is no zero-length item Here is valid non-list item 98Az Helloworld "Hello, world!" "It's house."  Here is the list Hello, World! Space then it is list ()  Here is invalid item. !$%#%^$*%%^&%^&$%#:;,./<>?
Helloworld!


## Input

The input consist of string of number then space then list as defined above. The number indicates the output format.

There are n digit of number where n is dimension of the input array. each number correspond with this one. (Table formatting needed). The dimension is counted from outer into inner. You may assume that there is no two 0 or 1 without being separated by 2 - 7.

1. 0 = unenclosed comma list
2. 1 = unenclosed space list
3. 2 = parantheses enclosed comma list
4. 3 = parantheses enclosed space list
5. 4 = square bracket enclosed comma list
6. 5 = square bracket enclosed space list
7. 6 = curly bracket enclosed space list
8. 7 = curly bracket enclosed space list

## Output

A identical list but with formatting changed according to input (i.e. each item it list is identical). Space not between list is allowed

## Test cases

> denotes output # denotes comment

6 Hello, world
> {Hello world}
5 (1, 1, 2, 3, 5, 8, 13, 21)
> [1, 1, 2, 3, 5, 8, 13, 21]
#Alternatively
> [1,1,2,3,5,8,13,21]
#Or
> [ 1,1, 2,3, 5,8, 13,21 ]
#But it is invalid
> [1,1, 2,3, 5,8, 1 3,2 1]
#Also
> [1,1,2,3,5,8,13,21,]
10 Hello, I am doctor
#Parsing rules that space separator bound tighter
> Hello I,am,doctor
01 Hello, I am doctor
> Hello, I am doctor
0 "Not to be confused be space or comma in a quoted item"
> "Not to be confused be space or comma in a quoted item"
51 [1,2] [3,4]
> [1 2,3 4]
51 [1,2][3,4]
> [1 2,3 4]


## Sandbox Question.

The format needs helps. Needs pointing when there is ambiguity.

• I'm not sure that I fully understand this. To take a couple of your examples, Hello, World! appears to have two separators (a comma and a space): is it a one-dimensional three-element list, or a two-dimensional list? Is () a one-dimensional list or a two-dimensional list? And in the input, which order are the dimensions listed in, and what constraints are there on which formats can be used at which levels? (E.g. 00 is clearly not going to work, but I'm not sure whether 010 is permitted). Nov 16, 2015 at 23:20
• @PeterTaylor That's why I post the challenge here, because this challenge is nontrivial to writing. It is one dimensional comma separated list. Only space between item is list separator. Comma (except inside quote) isn't valid part of item. The input order is from outer into inner. You can assume that 00 and 010 isn't never entered. Nov 17, 2015 at 8:35
• () is one-dimensional list since you have to it is parsed with least dimension as possible Nov 17, 2015 at 8:43
• I'm afraid that I'm even more confused than before about spaces and commas. You seem to be saying that in the example 6 Hello, world a (comma plus space) makes a single separator in a one-dimensional list, whereas in 10 Hello, I am doctor a (comma plus space) is two distinct separators in a two-dimensional list. Do you have a reference implementation which we might be able to use to reverse-engineer the spec while the question is still in the sandbox? Nov 17, 2015 at 16:55
• In "Hello, world", "Hello" and "World" can be 1-item space separated list, however, lowest dimension takes precedence. In "Hello, I am a doctor" It is list containing 2 item. One is 1-item list, other is 4-item list. Nov 18, 2015 at 9:56

# Triangularity

This is a challenge where you have to work out the length of a given w and h.

To qualify as a correct solution:

1. The program uses STDIN to get the values of w and h.
2. The program uses STDOUT to output the value of a in the above diagram.

The shortest code in bytes wins.

Tags: code-golf, maths

• What's the formula? Unless it's very complicated, I expect it will be totally straightforward to golf.
– xnor
Nov 18, 2015 at 11:45
• @xnor, a = w/2 * sin(atan(h/w)). The diagram throws in some irrelevancies and omits a relevant line, but it's not an interesting problem. Nov 18, 2015 at 13:02
• @Peter Should I post this or do you think it's too easy? Nov 18, 2015 at 21:31
• @Tobsta I think it's too straightforward. Languages with trig will use the formula Peter gave, and the rest will do something like h*w/sqrt(h*h+w*w)/2.
– xnor
Nov 18, 2015 at 21:58
• @xnor Ok, got it Nov 18, 2015 at 22:54

# Introduction

I've read this problem long time ago somewhere but I still don't know what's the best solution, so I'm posting it here. I don't remember the original author or wording so here is all in my own words.

This is different from regex golf because only two wildcards, * (equivalent to the regex .*) and ? (equivalent to the regex .), are allowed.

# Challenge

You are given two lists of strings. You need to generate the shortest wildcard that matches all strings in the first list (the wanted-list) and none in the second list (the unwanted-list). In the wildcard, you can use * to match 0 or more chars and use ? to match any one char.

For simplicity we can assume that inputs only have lowercase English characters and each string won't be longer than 100 characters. But the list can be very long (like several thousand), so speed of your program is important.

The correct answer that has the lowest average-case theoretic time complexity wins. In a tie, an easier-to-read answer wins.

# Example Input and Output

Input:

• Unwanted list: alien, african, atom

One possible output: a?a*

I'd also like to hear about how to approach this problem, and how to prove the theoretic lower bound of time/space complexity.

I'm new to this so comments are welcome. I'm not sure if my winning criteria is clear and practical. Also I don't know what tags I should put there. This is not a code-golf question.

• Nov 17, 2015 at 21:46
• Thanks for pointing it out @peter-taylor. This challenge is different in terms of using wildcards, not regex. So you think it is not worthy to post? Nov 17, 2015 at 22:06
• Ah, I thought you were using wildcard as a synonym of regex. I take the point that removing alternation does make quite a different problem. Although it has the downside that there are insoluble cases (e.g. I don't think your wildcards can separate a wanted list of a and abba from an unwanted list of aba), so you'd need to specify how those cases should be handled. Nov 17, 2015 at 22:16
• Thanks! I'll edit and clarify these concerns. Nov 17, 2015 at 22:18

# C++ Expression Matching

So, I like C++. And I like regex matching puzzles (heck, "regex golf" is what first got me lurking on this site). Might as well try to sort of combine the two!

# Rules

Write a full program that takes as input two lists of zero to five integers in the range [1, 127], and outputs a string representation of a C expression that evaluates to nonzero / true for all integers in the first list, and zero / false for all integers in the second list. Input can be taken in any convenient form.

As a special case, if the second list is empty, then the expression returned must evaluate to true for only the integers in the first list, and false for all other integers in the range [1, 127]. Likewise, if the first list is empty, it should evaluate to false for the integers in the second list, and true for all others in that range.

The program will not receive two empty lists as input. If both lists are non-empty, there are no requirements on the result of the output when evaluated with an integer not in the input. (any return value is fine, as is undefined behavior, division by 0, etc).

The following tokens may be used in the expression:

• Integer literals in decimal, hex, or octal, with optional U and/or LL suffix to denote unsigned / long long ints.
• A single int variable, which will contain each of the integers from the input in turn. The variable can have any legal variable name.
• Any of the unary operators + - ! ~
• Any of the binary operators + - * / % << >> < > <= >= == != & | ^ && || ,
• The ternary operator ?:
• Parentheses.
• Operators that mutate their arguments (++ --, = += -= etc.) are not allowed.
• Character literals ('a', '_', '\0', etc.) are not allowed.

Some examples of possible outputs:

true            false           sample expression
[1, 3, 5, 7],   [2, 4, 6, 8]    c%2
[5, 6, 10],     [2, 8, 16]      t&~-t
[7, 14, 21],    []              22>x&!(x%7)


(TODO: Specify undefined / implementation-defined behavior details? My test program assumes 32-bit ints / longs, 64-bit long longs, and "nice" two's-complement signed overflow / conversion.)

This challenge is ; your score is determined by the total number of characters in the outputs for these ten randomly-generated inputs: (TODO).

Bonus: Subtract 15 from your score if the output expression evaluates to 1, not just nonzero, for all 'true' inputs.

## Sandbox Questions

Welp, turns out my "Round Fractions" question from earlier is pretty much a subset of "Closest fraction". So here's another idea I've been tossing around since the one challenge I answered in C a while back (Area of an ASCII Polygon).

This is still very much a work-in-progress spec, though; some questions I have:

• I believe this could be tagged as C rather than C++; the only difference I'm aware of is the ternary conditional's precedence, and given that no assignment operators are allowed, it might not make a difference.
• I'm not sure what tags would go best on this (is it if the output isn't fixed?)
• I imagine there should probably be some additional constraint to prevent theoretically optimal but impossibly slow brute-force searches.
• The range [1, 127] is kind of arbitrary; my thought is that it should be able to handle anything in ASCII range + whitespace characters, but not much more than that, so as to make the special cases less restrictive.
• Would there be a way to spin this off as , if establishing run-time conditions is too arbitrary?

I'm mostly done writing a program to test the output expressions; just need to do a bit more testing.

That's pretty much it; hopefully this is enough to work with for feedback. Thoughts / comments?

• Interesting challenge. I think a time-limited code-challenge is a better fit than code-golf, because there's a lot of complexity with that many operators and golfed code would be hideous. I think the random test cases should be supplemented with some which are designed to favour different operators, so that deciding to leave some out for speed becomes a real trade-off. There's only one integer literal which anyone would want to use in octal, so you could make a special case for 0. If you're going to allow LL in tokens then you really should be explicit about type widths. Nov 26, 2015 at 21:01

# Typographic Chemistry

Inspired by this: https://xkcd.com/1442/

You must make a program or function that take input a string from STDIN and output the possible allowed reactions (1 point per unique reaction, see also "Score" below)

## Rules

A chemical reaction is allowed if all the "legs" of the elements are used, i.e., there are no unpaired "legs". A "leg" is just the end of a curve in the typographic print of the chemical symbol (see the comic and it should be clear). So for example:

Carbon - C - 2 legs

Oxygen - O - 0 legs

Hydrogen - H - 4 legs

Nitrogen - N - 2 legs

Potassium - K - 4 legs

Phosphorus _ P 1 leg

An element can be rotated, reflected but not stretched in any way, so that the only possible bonds are (here I don't know how to rotate the chars, if somebody can help it would be welcome):

$$CH \;\mathrm{(with\;the\;C\;on\;top\;or\;bottom\;rotated\;by\;90\;degrees)}\\CK \;\mathrm{(with\;the\;C\;on\;top\;or\;bottom\;rotated\;by\;90\;degrees\;or\;to\;the\;right\;rotated\;by\;180)}\\ HK\;\mathrm{(on\;top\;of\;each\;other\;or\;on\;the\;side\;rotating\;one\;by\;180)}\\ NN\;\mathrm{(with\;one\;reflected\;has\;two\;legs\;on\;top\;and\;two\;diconnected\;legs\;on\;bottom)}\\ P\;\mathrm{(with\;anything)}\\ O\;\mathrm{doesn't\;bond}$$

These are the only possible elements passed from STDIN. Notice that the difference between H and K is that K can bond also laterally with a C.

### Extra Rule

If no reaction is possible, the output should be equal to the input

## Score

1 point per reaction. Bonus: X3 the score if you can print the reaction diagramatically, i.e. print the shape of the molecule (like in the comic)

## Example

$$Input \rightarrow Output\\ C\,C \rightarrow (C_2)\\ N \, N \rightarrow N \, N\\ C\,N \, N\,P\,P \rightarrow (C N_2 P_2)\\ C\,C\,K \, H\,H\rightarrow (KC_2H_2)\\ C\,H\,O\rightarrow C\,H\,O$$

• Your rules seem to be imposing extra grid-alignment constraints on the letters (e.g. you don't seem to permit the hydrogen crystal from the xkcd). Does that mean that although P can bond with anything except O, the positions in which it can do so are restricted? Nov 24, 2015 at 19:05
• Hi, I don't want to impose necessarily the extra grid alignment, thanks for noticing it. Yes, P can bond with anything, I added it so that it is easier to have "allowed" reactions. Nov 25, 2015 at 15:01
• So does that mean e.g. that CP_2 is possible? Nov 25, 2015 at 15:12
• yes it is, although I have no idea how you could print it. Do you have any good way to state the rules simply and effectively? Nov 25, 2015 at 15:39
• This is so far from the truth of chemistry that you really need some decent drawings to show what's acceptable. The number of bonds an atom can make is in reality determined by its column in the periodic table: K=1 (except the bond is usually ionic not covalent), H=1, C=4, N=3, P=3 (sometimes 5), O=2. Nov 25, 2015 at 23:25
• Hi, I have prepared an image, but I can't upload it because I don't have enough reputation. Can you help me? Nov 26, 2015 at 16:06
• The easiest solution I can see is to remove entirely the list of possible bonds and the bonus and to effectively convert it into a question of whether there exists a graph with the desired degree sequence. IMO that's still an interesting question, and one which hasn't been asked here before. Nov 26, 2015 at 21:08

Note: I think the question is fine. I just need some more testcases for it.

You are given the priority order of alleles for a particular trait. For example,

A B
O


means that A and B are equally dominant and O is recessive to both of them. An organism has exactly two alleles, but only the dominant trait(s) is/are expressed. So an organism with gene AO will express only A but an organism with gene AB will express both A and B. An organism with two same alleles will express that allele only.

Each offspring will receive two alleles - one from the mother and the other from the father. So if the initial parents are AB and AO, the offspring formed will be:

AA - 25%
AO - 25%
AB - 25%
BO - 25%


Expressed traits will be

A - 50%
AB - 25%
B - 25%


Offspring of one generation may breed only with a single member of the opposite sex in the same generation during its lifetime. Assume for the sake of this challenge that every male finds a random female in the same generation and has exactly two children - one male and one female. Siblings may interbreed. Note that, except for the first generation, we can ignore the sex of the individuals as their sex chromosomes assort independently of their other characteristics.

Input

• Priority order of all alleles (may include unnecesary alleles)
• Genotype of every organism in initial generation
• Number of generations created
• Any one allele
• (Optional) Number of lines of input for priority order (for languages like C++)

Output

• Probability of the specified allele existing in a randomly selected individual in the specified generation (accurate to three decimal places)

Challenge

• Once two/three answers are posted, I'll use the same testcases in all of them to see which of them are faulty.
• After a week (or I could prolong the deadline) I will upload a lengthy test case in a few days. The code that solves it in the fastest time wins.

Sample data (Some simple testcases)

#1

A
B
C
Male(s) - AA
Female(s) - AB
5
C


Output 0

#2

A
B
C
Male(s) - AA
Female(s) - AB
2
A


Output 0.75

#3

A B
C D
Male(s) - AC,BD
Female(s) - AC,BC
1
C


Output 0.125

• "Once two/three answers are posted, I'll use the same testcases in all of them to see which of them are faulty" You should have a way to verify answers without using other answers. Dec 1, 2015 at 17:35
• @FryAmTheEggman I am abandoning this Q, anyone else is free to post it themselves. Dec 2, 2015 at 9:47

# Cops and Robbers - Find the Formula

Cops will write a function that takes numerical inputs and produces numerical outputs (note - outputs can be any base and may contain letters). They will post the language, the number of bytes it takes to write the code (up to 128), rounded up to the nearest power of 2, as well as a minimum of 2 test cases. The robbers will try to write a program that takes the same numerical inputs as the test cases and produces identical outputs.

Note - PRNG's, hashing, and other forms of encryption are not allowed.

Scoring

Cops (if safe)

The floor of the product of:

• 128 divided by the power of two rounded up for the bytes
• The natural logarithm of the number of test cases

If cracked, -10 points.

Robbers

The floor of the quotient of

• Half the number rounded up to by the cops
• The natural logarithm of the number of test cases
• Say I have a function f(x) that returns x when x<2 and 3*x ᴏtherwise. Would the robber's function only have to match the given test cases, or have to match all test cases? Nov 27, 2015 at 3:06
• @CᴏɴᴏʀO'Bʀɪᴇɴ The given test cases only. Nov 27, 2015 at 3:16
• Is there a maximum of test cases? Nov 27, 2015 at 3:24
• @CᴏɴᴏʀO'Bʀɪᴇɴ I'm not sure if there should be. If there were, I'd say maybe 10 or 12. Nov 27, 2015 at 3:25
• I think the scoring algorithm might be a bit complex. Nov 27, 2015 at 3:41
• @CᴏɴᴏʀO'Bʀɪᴇɴ I want to do something that awards points depending on the number of test cases because that makes it more likely that the robber found the intended solution and is "more" right. Nov 27, 2015 at 5:03
• The cops-and-robbers lesson which everyone should have learnt by now is that built-in crypto functions should be banned because otherwise the cops have an easy time. Nov 27, 2015 at 13:49
• ^ That should include hashing and PRNGs. Although it's really hard to rule them out conclusively. My personal goal is still to come up with more CnRs that aren't susceptible to stuff like that in the first place (like my Programming Language Quiz). Nov 27, 2015 at 14:00
• @MartinBüttner Given that I've explicitly disallowed hashing, PRNGs, and encryption, what do you think of this challenge? Nov 27, 2015 at 22:15
• @Eridan It's still susceptible to arbitrary base conversions or expmod (just check out any CnR-submission by Dennis to see some examples). People can just throw together a quasi-random program in a golfing-language without having to understand it and just run some numbers through it to generate test cases. Nov 27, 2015 at 22:36
• @MartinBüttner I didn't realize those were bad for CnR challenges (I even mentioned base conversion above). Is there a specific way I could describe methods like those to disallow them? Nov 27, 2015 at 22:50
• @Eridan none I can think of. That's why I meant that this is an inherent problem of any CnR that lets participant choose what their program does. In CnRs where the programs need to solve a specific task, this is not such a big issue, because the cops actually need to find a convoluted but working implementation themselves. Nov 27, 2015 at 23:07
• Even with crypto banned, numerical functions make for boring CnR challenges since it's much more likely to be about finding parameters rather than guessing the structure of the code.
– xnor
Nov 28, 2015 at 9:57
• A problem: Anyone can just write an interpolating polynomial. Nov 28, 2015 at 13:49

# Quiddler

Quiddler is a card game where you try to create words from letter cards drawn from a deck. A word is defined as being more than 2 cards in length. Sometimes letters are combined on cards in this game, however that will not be the case in this challenge.

Your mission is to write a program which creates words from the letters read in on standard input. Your dictionary of words is the words file on any standard unix system. You may assume that all strings this file is all lowercase.

## Input

The string of letters you can use to create words is read in on standard input. This string will be all lowercase, and will not have any spaces in it.

Valid examples are:

actlj
jactl
ljdkj
jjabc


Invalid are:

jklKLJKKJLKUIU
klj kljklj djkas;


## Output

The list of all possible results from said string each string. Remember you can produce multiple words in the same answer.

Examples of valid output include. Please remember that I came up with these off the top of my head, and may not be complete. Input is left aligned and the output is presented as the indented lines. The -> is for your benefit.

tacb  ->
cat
act
bat
tab

fivquedrr ->
five qud
quid five
river
quiver


The order of the solutions output does not need to be in any specific order.

# The environment

This program must run in a standard UNIX-like environment. This means that you may use any standard shell (bash, ksh, csh, zsh, fish), and you have access to all the standard tools. This challenge is restricted to the shell scripting languages.

The path to the dictionary file in the environment variable, DICT, the path to the file should not be in any valid solution. Use $DICT as the path to the dictionary. This is included so that you can provide testing instructions for your program. # Winner The winner is the one with the fewest bytes of code that produces the correct output. • In the example output, I'm not sure why for the first input the output is newline-separated, but for the second it's space-separated. I also don't understand the second paragraph in the section "The environment". Nov 27, 2015 at 21:30 • @PeterTaylor In quiddler you can have multiple words per possible solution. I'll add a second example to demo. Nov 27, 2015 at 21:53 • So is this basically a variant on Countdown where the dictionary is amplified by including its Cartesian power? Nov 28, 2015 at 8:08 • @PeterTaylor: Pretty much, except I did not know that existed. Also, for each answer you can only use each answer once. Nov 28, 2015 at 16:43 # Ancient Language Translator <insert a silly story here> ## Task: Write a program that takes an English sentence and translates it into the Ancient Language. You have to implement at least 42 words. For the purpose of this challenge, you do not have to care about special rules such as "(may be shortened to al when used as a prefix, as in albitr)". ## Input: An English sentence. ## Output: A translated version of the input, simply replace the English words with the Ancient ones. ## Examples: To be added. ## Scoring: Suggestions? • This might be considered as too broad as there is no specific words to implement. For scoring a code-challenge might work with the score being something like the sum of the length of all words implemented. code-golf might also work. Kind of related challenge. The title is also possibly misleading, so I'd suggest putting "Ancient Language" in quotes Nov 29, 2015 at 16:55 • I think this would be uninteresting just because it's just replacement, not actual translation. – cat Nov 30, 2015 at 3:07 • @sysreq Translating English into the "Ancient Language" is just replacement as far as I know... Nov 30, 2015 at 17:24 • @Downgoat Oh, ok! So, what words should have to be included? A selection of) the most common words: en.wikipedia.org/wiki/Most_common_words_in_English Nov 30, 2015 at 17:26 # Nested Header List The goal of this challenge is to complete a list of consecutive nested header numbers when given a start and an end. When given 1.1.1 and 1.1.5 you should generate 1.1.1, 1.1.2, 1.1.3, 1.1.4, 1.1.5 Specific Rules 1. Your entry must take in a start, end, and multiple optional range parameters. Parameters can be taken form STDIN (or nearest equivalent) or a file. 2. Your entry may assume valid input 3. Input will be of the following format: 1. start and end will be strings of . delimited integers of the same length 2. start and end will have three segments; (1) set values, (2) iterator, (3) trailing values. • The iterator is the first value which differs between start and end. • The set values are the values before the iterator. These values never change • The trailing values are the values after the iterator. These values iterate up as determined by the range parameter(s). All trailing values will be 1. 3. range will be a list of integers with a length corresponding to the number of trailing values. When there are no trailing values, range is not specified. The value of range corresponding to each trailing value determines the inclusive upper bound which that entry iterates to. 4. Output will be to STDOUT (or closest alternative) and will show each value separated by at least one delimiter. Delimiter can by any character or string of characters, but it must be consistent. Output must be sorted correctly Examples start = '1.1.5.1', end = '1.1.6.1', range = [5] Output: 1.1.5.1, 1.1.5.2, 1.1.5.3, 1.1.5.4, 1.1.5.5, 1.1.6.1 ^ previous value is iterated only when iterating value limit set by range start = '1.1.5.1', end = '1.1.7.1', range = [5] Output: 1.1.5.1, 1.1.5.2, 1.1.5.3, 1.1.5.4, 1.1.5.5, 1.1.6.1, 1.1.6.1, 1.1.6.2, 1.1.6.3, 1.1.6.4, 1.1.6.5, 1.1.7.1 start = '1.5.1.1', end = '1.6.1.1', range = [5,2] Output: 1.5.1.1, 1.5.1.2, 1.5.2.1, 1.5.2.2, 1.5.3.1, 1.5.3.2, 1.5.4.1, 1.5.4.2, 1.5.5.1, 1.5.5.2, 1.6.1.1  This is code golf so shortest code by bytes wins. Bonuses 1. Allow trailing values to be values other than 1 in end parameter - 12.5% off 2. Handle incorrect number of values in range parameter - 12.5% off 3. Handle end less than start by producing list in reverse - 50% off # Count the Connect Four Positions Connect Four is a two-player game on a rectangular board. The board is m spaces wide and n spaces tall, and players alternate placing pieces in columns. A placed piece always fills the lowest empty space in a column, and a player may not move in a full column. In the standard game, m=7 and n=6. The game ends when one player completes a row of four pieces vertically, horizontally, or diagonally, or all m columns are full. The edges of the board do not wrap. ## Challenge Write a program or function to determine the number of distinct, legal m by n Connect Four boards after p plies. (A ply is one move by one player.) A legal position is one reachable from the empty board through a sequence of moves in which no player had already won. (A position in which one player has just won is legal.) ## Rules You may assume that 0<=p<=m*n, m<=8 and n<=8. As usual, hardcoding is not allowed. Your code should be at most 1024 bytes in length, and use at most 16 GB of memory. Related: Determine winner of Connect 4 ## Test cases [need to add; include OEIS] Relevant links: # Compile from Brainfuck The professors at Brainfuck University realized their jobs are horrible, because all they do is discuss quantum mechanics using Brainfuck, so they decided to take their programs and compile them to a better language. Because of the randomness of quantum particles, their program needs to be small so it has a smaller chance of being disrupted in the Higgs Field. Your task is to get a Brainfuck program from any input and output that program transcompiled into another language. Here is an example: ++-->><< Compiles to the C program: #include <stdio.h> #include <stdlib.h> int main(int argc, char **argv) { unsigned char *cell = calloc(30000, 1); unsigned char *cells = cell; if (!cell) { fprintf(stderr, "Error allocating memory.\n"); return 1; } //actual program ++*cell; ++*cell; --*cell; --*cell; --cell; --cell; ++cell; ++cell; free(cells); return 0; }  ## Score Your score is the size of your program added to the size of the output. ### Bonuses • Dupe – user45941 Dec 5, 2015 at 9:55 Logic Puzzle Solver/Inference Engine Your goal is to take the clues and other facts given in a grade-school logic grid puzzle such as these and solve the puzzle. To keep things simple, your program will only solve specific logic problems about which it can make the assumptions you wish to hard-code in, but the program need not perform any checks to see if those assumptions can be made. You may not use: • A declarative language • Any function provided - by an external dependency - for the solving of a logic puzzle. Input Your program will take input from the command line. After gathering assumptions, the program will ask for facts written as such: subject.verb object  for all true facts. For false facts: !subject.verb object  Examples: If Chad bought donuts, Chad.bought donuts  If he didn't: !Chad.bought donuts.  If Nancy's last name isn't Wesley, !Nancy.is Wesley.  Output Your program will output its conclusions as such: subject verb object.  So, if your program determines that Chad bought donuts and Nancy's last name is Wesley, then it will output: Chad bought donuts. Nancy's last name is Wesley.  • The "these" link goes to a login page. I'm not going to create an account on some random site just to find out what the spec is. Dec 15, 2015 at 22:24 • "You may not use a declarative language" :-( Dec 16, 2015 at 12:59 • Does "is" always refer to someone's last name? If not, how can our code know the difference between Nancy.is Wesley and Nancy.is chef? – Luke Dec 16, 2015 at 14:49 New user to Programming Puzzles! Spades CHALLENGE!!! I would like a king of the hill challenge for bots playing the game of spades. Spades is a card game. The rules are shown on wikipedia. Scoring rules: • Nils allowed, with 50 points for completion (not 100). -50 for losing. • 10 points a hand, with sandbagging allowed. • Partnership Playing • Sum of all four players hands cannot equal 13! Winner is first to 500 points. The bot will be paired with all other bots entered into the competition. The pair of winners will be crowned with +10 meta-points (Mpoints), losers will get -1 Mpoints. Whoever has the most Mpoints wins - ties based upon sum of points earned in the games. Gameplay: • The bot with the lowest Mpoints bids first. Bidding proceeds from down until reaching 4th slot, then goes back to first slot and continues. Play starts with this player. • The bot will be given a string of cards - AS for Ace of Spades, JC for Jack of Clubs, 2D for 2 of Diamonds, 8H for 8 of hearts, randomly dealt from a single 52-card deck. Each will be comma separated: AS,JC,2D,8H,4C,5S,8D,3D,3S,JS,10S • The bot will get the bids from the other bots before making the bid. • Upon winning a hand, the bot gets to continue making plays until someone else wins the hand. • Hands are scored at the end using the scoring rules. If a team's score is less than 500, gameplay continues with a new hand. Unfortunately, I do not know how to setup the servers or any of that stuff. I just think the challenge will be interesting. If anyone can help with that, run with it. I like to watch these challenges unfold - but I'm too much of an engineer and not enough of a programmer to make these kinds of programming happen. • You should fully list out the rules in the body of the question - it's considered poor form for challenges to require exterior resources to be fully understood. – user45941 Dec 22, 2015 at 22:56 I was thinking about a challenge on wrapping time. I am a member here for 34 days now. I would have expected for the date to wrap to 1 month. ### Rules: • starting with hours from the joining date to now. • first wrapping happens when you go over 24 hours, the count will be in days now. • second wrapping happens after reaching 30 or 31 days, you can decide, to months. • third wrapping really wraps when a year is reached, it shall be displayed as i.e. 2 years 3 month. • round to neares full unit, i.e. 43 days = 1 month, 50 days = 2 month • take either a build in function to get the current time or hardcode it to ´2015-12-19-11´ <- time when challenge will be posted. If hardcoding it is shorter you may take the bytecount from the hardcoded version. • Dates after the current or hardcoded date can do whatever. ### Input The joining date and hour like ´YYYY-MM-DD-HH´ the delimeter does not have to be a - choose whatever you like. ### Output The time according to the rules above. ### Example: In: 2015-12-10 Out: 9 Days In: 2015-10-28 Out: 2 Month  • I believe I saw a challenge about wrapping 24-hour time that may be related, but not a duplicate. Also, what date are we calculating the difference from? Dec 18, 2015 at 17:05 • that would be the date right now or a set date if no build in is available Dec 19, 2015 at 8:19 • I think it should be either a built-in date or another date given from input for all languages, to make things fair. Dec 19, 2015 at 16:02 • I wanted it to be non input, how would you suggest doing that? Dec 19, 2015 at 20:01 • Use a built-in date such as 01-01-2015 (or 01-01-2000, depending on what the date range should be). The program should not be required to accept dates before that. Dec 20, 2015 at 21:14 # Browser identifier There are three major browsers at the moment, Internet Explorer, Google Chrome and Firefox. Sometimes, the JavaScript engines inside of these browsers work a bit differently, and that can break some applications. Therefore, we need a way to identify what browser the user is currently using! Your answer should be a JavaScript program or function, that when run on the latest version of a browser, should output a string representing that browser. The string outputed could be anything, as long as it stays the same every time you run it. Output should go to a HTML paragraph with id O, console.log, or as return value. Please put your answer in a snippet, along with <p id="o"></p> in the HTML section if your answer uses it. (scoreboard snippet goes here) • I believe Javascript has a builtin for this. It may be best to forbid using it. Dec 22, 2015 at 17:34 • @SuperJedi224 Well, I did some searching before, and I found this thread on SO, and the highest voted answer was a big mess, and no answer was very short and reliable. There is this other thread, and it has some that could be golfed a bit, but there isn't really one function / builtin that checks the browser. Dec 23, 2015 at 2:56 • You might need to freeze the version numbers of the 3 browsers, or else require that answers specify version numbers. Dec 29, 2015 at 15:54 # Parse a tree for pruning Windows supplies users with tree: a neat little tool that converts a directory tree to ASCII-CP437 art. It's a very human-readable format. However, it's a bit useless if you want the directory tree of an entire drive, or even just the Windows folder, as it's very hard to prune the parts you don't want. Hence this challenge. ## Task Your task is to produce a function or program that will convert the tree from one or both of the input formats into one or more of the output formats. The smaller your code, the more of a head start you have. ## Input There are two types of input that you might be given: ### CP437 This is the default. Folder PATH listing for volume Main Drive Volume serial number is 00F3-F586 C:\WINDOWS │ explorer.exe │ notepad.exe │ virus.dll │ WLXPGSS.SCR │ write.exe │ ├───Boot │ │ BootDebuggerFiles.ini │ │ │ ├───DVD │ │ your.txt │ │ │ ├───EFI │ │ pc.txt │ │ │ ├───Fonts │ │ has.txt │ │ │ ├───PCAT │ │ been.txt │ │ │ └───Resources │ wrecked.txt │ ├───System └───System32 cmd.exe conhost.exe winlogon.cmd winlogon.exe  ### ASCII This will be easier to parse for many languages. Folder PATH listing for volume Main Drive Volume serial number is 00F3-F586 C:\WINDOWS | explorer.exe | notepad.exe | virus.dll | WLXPGSS.SCR | write.exe | +---Boot | | BootDebuggerFiles.ini | | | +---DVD | | your.txt | | | +---EFI | | pc.txt | | | +---Fonts | | has.txt | | | +---PCAT | | been.txt | | | \---Resources | wrecked.txt | +---System \---System32 cmd.exe conhost.exe winlogon.cmd winlogon.exe  ## Output There are several possible types of output you can return, each suited to a different type of language. ### Array / List hierarchy of strings The first element of each array / list is the name, the rest are the contents. Files should be represented by strings, empty folders should be represented by a single-length array containing one string. Note: This should be returned from a function as an array / list, not printed as a string. ["C:\WINDOWS", "explorer.exe", "notepad.exe", "virus.dll", "WLXPGSS.SCR", "write.exe", ["Boot", "BootDebuggerFiles.ini", ["DVD", "your.txt"], ["EFI", "pc.txt"], ["Fonts", "has.txt"], ["PCAT", "been.txt"], ["Resources", "wrecked.txt"]], ["System"], ["System32", "cmd.exe", "conhost.exe", "winlogon.cmd", "winlogon.exe"]]  ### Object / Dictionary Similar to array / list, but a little more intuitive. Folders should have the value of their contents as another object / dictionary. Files should have the value "FILE". {"C:\WINDOWS":{"explorer.exe":"FILE","notepad.exe":"FILE","virus.dll":"FILE","WLXPGSS.SCR":"FILE","write.exe":"FILE","Boot":{"BootDebuggerFiles.ini":"FILE","DVD":{"your.txt":"FILE"},"EFI":{"pc.txt":"FILE"},"Fonts":{"has.txt":"FILE"} [...] } [...] } [...] }  ### Lisp-style string Similar to array / list, where the head of the list is the directory name and the tail is the contents. An empty directory is a list with no tail, and a file is a string. No WAY am I putting an example. No way. I've spent half the time on this question creating the examples. No way. Ok, maybe later.  ### Bonus If you satisfy none of these bonuses, your submission is still valid. But its score shall infinite, so it is non-competitive. These bonuses are to multiply your score by. Bonuses stack by multiplication. These bonuses must all be achieved consistently to be awarded. • 100% Allow at least one input mode and output mode • 50% Allow both input modes • 90% Output in exactly two ways • 50% Output in one of two ways depending on parameters • 80% Output in exactly three ways • 25% Output in one of three ways depending on parameters # Identifying spies in "Resistance" This is still very rough, but I think it has the makings of an interesting challenge. Please help me improve it. What do I need to add? What do I need clarify? Resistance is a party game that pits "resistance members" against "imperial spies" on a series of missions. A very important aspect of the game is that the resistance members do not know who the spies are, whereas the spies do know who is who. How the game works The relevant details of the game will be added here. For now, just check the Wikipedia page linked in the title. Challenge your challenge is to write a program that takes as input the details of every round and outputs who it thinks is a spy after each round. There are 5 rounds (missions) in a game of resistance, so the program/function will take in all the data for the first round, which includes 1. Each proposed team to go on the mission 2. Each public vote following each proposal 3. The final team to go on the mission 4. The outcome of the mission (i.e. how many passes and how many fails) It will then output who it thinks is a spy. It will then do the same for each subsequent round. Important Details We will be playing resistance for (6?) people, A, B, C, D, E, and F. Input format is flexible. It may be done round by round or all at once. However, since ach submission is outputting something for each of the five rounds, the submission may not use information from future rounds (if all information is given at once) in judging the current round. Here is an example of possible input format: Since the first mission requires two people, and person A is the first mission planner, the only thing input would be two letters in {A,B,C,D,E,F} indicating his selection. Then the votes of each person, in order, would be input. This continues until a mission team is accepted. Then the votes given on the mission would be input, in no/any particular order. The program would then output the letters of the two people it thinks are spies (there are 2 spies in a 6 person game). Here is an example A B # A selects A and B for first mission P P P F F F # Everyone votes, mission team is not accepted (lacks majority pass) B F # B selects B and F for first mission P P P P P F # Mission team is accepted (majority pass) P F # Mission fails (there is at least one fail vote). Note that the order does not matter here.  The bot would then output two people, the people it thinks are most likely to be the spies based on all the information it has up to this point. B F # Any two person subset is acceptable  Input then continues for the next 4 rounds, until the game is over. Scoring I will write several hundred test cases (from actual games played online). Then each output will be scored in the following way: • 1 point for each correctly guessed spy. • 1 point for guessing both spies correctly. The submission's total score will be the sum of all scores on all rounds in all games. The program will never be told who is a spy (unless it is used to self-score and does not factor into the actual guessing) but this information will be available with the test cases for scoring purposes. Tie break is code golf. Meta: I think I'm going to remove output after the first round, because very rarely do people ever fail the first mission. So it will likely just be pure chance. # Nth Regex This challenge('s explanation) is simple: given a number n and a regex r, output the nth string that matches r! The regex r uses the syntax used in Python, described here. The regex will be for the whole string, meaning the regex will be implicitly wrapped in ^$.

The only valid strings are printable ASCII characters, and they count up like base 95 (ASCII codes 32-126).

To prevent people from brute-forcing it, I was thinking of making it .

• I still think you mean "bijective base 95". otherwise, there are no strings with leading spaces (because if count up in base 10, there are no numbers with leading zeroes). Dec 29, 2015 at 14:09
• I'm not a fan of using a specific real-world flavour, because that gives an advantage to Python over all other languages. I also think it contains way too many features to be fun to tackle (which don't really add anything interesting to the challenge). I think the challenge would be interesting and hard enough for a simplified regex flavour containing only simple quantifiers, alternation and character classes. Dec 29, 2015 at 14:11
• I'm quite sure that some regexes are hard to solve. codegolf.stackexchange.com/questions/39829/… Dec 29, 2015 at 15:54
• I absolutely don't get the challenge, any example input/output ? Dec 30, 2015 at 14:31
• Do you mean nth string lexicographically?
– xnor
Dec 30, 2015 at 18:45

# Robots on ice

## Part 1 - The basic

You are helping a robot R on an iced island. R can go up/down/left/right. But since the island is made of ice, it cannot move only 1 square at a time, but instead moves in straight line. Your task is to help R reach G.

### Input

The input (file, stdin, input, whatever suits you) is an n×m matrice with the following characters:

• R The robot
• G The goal
• # An obstacle that stops the robot
•   Ice

The island is surrounded by a wall: the edges of the matrice always consist of #.

### Output

A list of instructions consisting of U/D/L/R, corresponding to up/down/left/right.

The list should be the shortest possible. The distance traveled by the robot doesn't count.

The output should be the map with the instructions on it, with each instruction at the right coordinates. Each of RG#  should be displayed if not overriden by an instruction (that will always be the case for R)

# Example

Input:

##########
# #      #
#        #
#  G #   #
#        #
#    R#  #
#        #
##########


Output: Since D,R,U,L,D is one possible solution, the output should be:

##########
# #D    L#
#        #
#  G #   #
#        #
#    D#  #
#    R  U#
##########


Another solution, U,R,U,L,D, should be output as:

##########
# #D    L#
#        #
#  G #   #
#    R  U#
#    U#  #
#        #
##########


Input:

####################
###R             ###
#  ######          #
#      #####       #
##                G#
###              ###
####################


Output:

####################
###R            D###
#RD######          #
#U L   #####       #
##R               G#
###U            L###
####################


You can assume that the puzzle always has at least 1 solution

## Part 2 - New options

The pitch is the same, but new characters can be displayed:

### Input

The input (file, stdin, input, whatever suits you) is an n×m matrice with the following characters:

• R The robot
• G The goal
• # An obstacle that stops the robot
•   Ice
• W Some water. Robot doesn’t like water
• B a Box. Robot can push the box 1 square at a time, in front of him (not on the side), if the next square is  . It cannot be pushed into the water, through the goal… Robot cannot push 2 boxes at once. When pushing, the robot stays in place.
• 1 a numbered teleportation door. Always in pair. When entering a teleportation door, Robot will continue sliding in the same direction through the other door. Can be used more than 1 time.

The island will this time be surrounded by water.

### Output

A list of instructions consisting of U/D/L/R, corresponding to up/down/left/right.

The list should be the shortest possible. The distance traveled by the robot doesn't count.

This time the output won't be displayed on the map, but on stdout. The format doesn't matter:

UDRL


or

U
D
R
L


are accepted

### Example

Input:

WWWWWWWWWW
W W      W
W        W
W  G 1   W
W        W
W    1R  W
W        W
WWWWWWWWWW


Output:

L


Input:

WWWWWWWWWW
W W      W
W    #   W
W  G     W
W        W
W    BR  W
W        W
WWWWWWWWWW


Output:

LLUL


The first L moves the box (but not the Robot) 1 square:

WWWWWWWWWW
W W      W
W    #   W
W  G     W
W        W
W   B R  W
W        W
WWWWWWWWWW


Input:

WWWWWWWWWWWWW
W         # W
W G 2       W
W           W
W   B 1     W
W#2         W
W   # 1R   #W
W          #W
W    #     #W
WWWWWWWWWWWWW


Output:

L #entering teleportation 1
L #pushing the box to the left
L #going to the box
U #entering teleportation 2


The solution RULU is also valid

Input:

WWWWWWWWWWWWW
W #         W
W     #     W
W#   1      W
W           W
W           W
W    1 R    W
W           W
W    G      W
WWWWWWWWWWWWW


Output:

L #entering teleportation 1
U #going to the wall
R #going to the wall
D #entering teleportation 1


In this situations, Robot cannot moves to the left:

W  GBR   W

W  #BR   W

W  BBR   W

W  WBR   W

W    R   W


You can assume that the puzzle always has at least 1 solution

## Part 3 - With help

Same as part 2 but with others robots:

### Input

The input (file, stdin, input, whatever suits you) is an n×m matrice with the following characters:

• R The robot
• G The goal
• # An obstacle that stops the robot
•   Ice
• W Some water. Robot doesn’t like water
• B a Box. Robot can push the box 1 square at a time, in front of him (not on the side), if the next square is  . It cannot be pushed into the water, through the goal… Robot cannot push 2 boxes at once. When pushing, the robot stays in place.
• 1 a numbered teleportation door. Always in pair. When entering a teleportation door, Robot will continue sliding in the same direction through the other door. Can be used more than 1 time.
• abcde up to 5 robots that can move the same as Robot. They cannot go through other robots, including R, and can pass through the Goal. They can be sacrified by going into the water. They can be used more than 1 time.

The island is surrounded by water.

### Output

A list of instructions consisting of U/D/L/R, corresponding to up/down/left/right, prefixed by the name of the robot moving.

The list should be the shortest possible. The distance traveled by the robot doesn't count.

As usual, theformat doesn't matter:

a:UDR
R:LU


or

aU
aR
RL
RU


are accepted

### Example

Input:

WWWWWWWWWWWWWWWWWW
W        a     # W
W   G            W
W                W
W                W
W                W
W             R  W
W                W
W       #        W
W             #  W
W                W
WWWWWWWWWWWWWWWWWW


Output:

a:R
R:UL


The answer DLUL is valid but not the shortest

Input:

WWWWWWWWWWWWWWWWWW
W                W
W                W
W                W
W                W
W  G    a    R   W
W                W
W                W
W                W
W                W
W                W
WWWWWWWWWWWWWWWWWW


Output:

a:U
R:L


Input:

WWWWWWWWWWWWWWWWWW
W           #    W
W                W
W  #             W
W           G    W
W                W
W                W
W           b    W
W   R       a    W
W                W
W                W
WWWWWWWWWWWWWWWWWW


Output:

b:U
a:UL
R:UR


Input:

WWWWWWWWWWWWWWWWWW
W                W
W           #    W
W          B     W
W  #             W
W     G          W
W                W
W  #             W
W   e       R#   W
W                W
W           a    W
WWWWWWWWWWWWWWWWWW


Output:

e:R
R:U
a:UL
R:LLDLUR


Input:

WWWWWWWWWWWWWWWWWW
W                W
W         G #    W
W   b            W
W                W
W           a    W
W   c            W
W           #    W
W   R            W
W                W
W          #     W
WWWWWWWWWWWWWWWWWW


Output:

a:U
b:RD
a:D
C:RD
R:RU


Input:

WWWWWWWWWW
W    G   W
W aBbBR  W
WWWWWWWWWW


Output:

a:L
b:LL
R:LLU


In this situations, Robot and b cannot move to the left:

W  GaRb  W

W  #b#R  W

W aBbBR  W


You can assume that the puzzle always has at least 1 solution

## Sandbox Questions

Has it been done before?

What do you think? Is it understandable? Should I do 3 separated challenges (and in the sandbox)? More, less? Which part needs more examples? What part is unclear?

I would like to go with shortest-code win. Should I use kolmogorov instead?

• Sep 23, 2015 at 13:35
• Related, but not duplicate: codegolf.stackexchange.com/questions/23238/… Sep 23, 2015 at 13:41
• Well… that's too similar :( Too bad! Sep 23, 2015 at 16:37
• The fourth example for part 2 should have output LLLU no? Dec 30, 2015 at 5:30
• @quintopia Yep, it's edited. Thanks! Dec 30, 2015 at 11:14

Pi is the most popular transcedental number. As a result, pi has been thoroughly studied. This challenge is in spirit of 9-Hole challenge.

## 1. Digits of PI

Given n and k, output n'th digit after the decimal point in the base-k representation. For example, the 5th digit of PI base 10 is 9.

5 10
9
10 2
0
6 16
10


If the base is more than 10, output like in the last test case

## 2. Continued fraction of PI

Given n, output n'th number in continued fraction of Pi.

5
292
7
1


## 3. Closest to PI

Given a positive integer d, output the integer n such that n/d is closest to pi. For example, 17/5 is closer to pi than any other n/5.

 5
17
7
22
21
66


## 4. Closest to PI 2

Given a positive integer n, output the integer d such that n/d is closest to pi.

5
2
7
2
20
6


# Restriction.

1. You should not have any floating-number buildin, only integer, including PI constants.
2. Standard loophole is disallowed.
3. The program may be 4 program or a program that reads challenge number.

# Sandbox Question

Originally, I have 5 challenge, 4 more required. Now, one of them is dupe. 5 more required.

• This does look suspiciously like lot of questions rolled into one. +1 and you could split it up into loads of challenges. Dec 30, 2015 at 12:10
• Also, you could add more clarification on what a "9-Hole challenge" is. Dec 30, 2015 at 12:12
• @LegionMammal978 codegolf.stackexchange.com/q/16707/46245 Dec 30, 2015 at 12:38
• The spirit is more than one challenge in one question. Dec 30, 2015 at 12:48
• Are you looking for 4 more sub-challenges, or a catchy name for a 5 component question? Dec 30, 2015 at 16:17
• Quintessential pi question? Dec 30, 2015 at 16:18
• A. I believe that the "many small holes in one question" model is considered a failed experiment. B. I don't understand the spec for part 1 at all. Part 2 is inadequately specified. Part 3 is a dupe. Parts 4 and 5 look almost completely trivial (or completely trivial for languages with a pi built-in). Dec 30, 2015 at 18:39
• Added that pi build-in is not allowed Dec 31, 2015 at 4:08
• What about getting pi via inverse trig? Complex logs? Evaluating integrals? Banning the built in value still lets languages express it via math, and it's tricky to draw the line.
– xnor
Dec 31, 2015 at 5:16
• Also, why does every question need to use pi? If you want a challenge about, say, rational approximations, you can use arbitrary inputs or square roots or anything all langs have access to roughly equally.
– xnor
Dec 31, 2015 at 5:18
• @xnor 1. trigonometry, log, etc. is useless without floating point number. And any uses of floating point number isn't allowed (Even if it just uses addition only). However, I am afraid of integrals, too. 2. Just because. Dec 31, 2015 at 5:52
• In the revised version, I think that if these were posted separately then part 1 would be closed as a dupe of part 3. Also, part 2 is still inadequately specified. You need to at minimum explain the indexing convention, and ideally specify what a continued fraction is (since some answers may use generalised continued fractions and confuse people who aren't familiar with them). Dec 31, 2015 at 11:12
• @PeterTaylor I don't understand how part 1 is dupe of part 3. For part 2 I uses simple continued fraction and what is indexing convention? Dec 31, 2015 at 11:17
• A. Part 3 says "Given d, find n such that (n-0.5)/d < pi < (n+0.5)/d". Part 1 is essentially (since there isn't a general Plouffe formula for all bases) "Given k and n, find b such that b / k^n < pi < (b+1) / k^n and then return b % k". The core problem is almost identical. B. It's not enough for you to know that you're using simple continued fractions: the question has to make it clear. The indexing convention is whether you count the initial 3 + ... as index 0 or 1. Dec 31, 2015 at 11:34
• @PeterTaylor A. The insight clears my mind. Thanks. I don't think as far as that. B. 1. But I don't know how to explain that. Please add yourself. Dec 31, 2015 at 11:43