460
\$\begingroup\$

What is the Sandbox?

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

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

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

The Sandbox works best if you sort posts by "active".

Add Proposal

Search the Sandbox

Browse your pending proposals

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]

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

2579 Answers 2579

0
\$\begingroup\$

Shh... Can you Split a Secret?

In Applied Cryptography by Bruce Schnieier (which I have been reading quite a lot recently), a protocol for splitting secrets is discussed. Here is a brief description:

  1. Trent generates a random string, R, the same length as the message, M.
  2. Trent XORS M with R to make S.
  3. He gives R to Alice and S to Bob.

Your task is to, given an input, split the input into the two outputs. One output should contain the random string; the other should contain the original input XOR'd with the random string. Input and output may be to/from files or to/from STDIN/STDOUT. Outputting to STDERR is also allowed.
There are a few restrictions, however:

  1. Your program must take 3 inputs, and output the random string and the original string XOR'd with that random string into the other.
  2. Your program must be cryptographically secure. All random number generators must be cryptographically secure. For example, /dev/random is fine, but the Mersenne Twister (usually randint(number,number) is not. Any random number generator must be explicitly cryptographically secure.
    • If you want to know anything more about what "cryptographically secure" means, check here.
  3. Standard rules and loopholes apply.

This is , so the code with the fewest bytes will win.
May the best coder prosper...

\$\endgroup\$
  • \$\begingroup\$ Is there a reason you are requiring input/output to be file-based? That removes a lot of languages out of the challenge. \$\endgroup\$ – Nathan Merrill Mar 18 '17 at 17:47
  • \$\begingroup\$ @NathanMerrill What should I change? \$\endgroup\$ – ckjbgames Mar 18 '17 at 17:48
  • \$\begingroup\$ @NathanMerrill I did kind of have file I/O in mind... \$\endgroup\$ – ckjbgames Mar 18 '17 at 17:48
  • \$\begingroup\$ Simply take in a single string as input (M), and have it output two strings (R and S). Writing/reading from a file is trivial in most languages, but in others its literally impossible. \$\endgroup\$ – Nathan Merrill Mar 18 '17 at 17:49
  • \$\begingroup\$ @NathanMerrill Thanks \$\endgroup\$ – ckjbgames Mar 18 '17 at 17:49
  • \$\begingroup\$ Also, I'm not very good at cryptography, so I may be wrong here, but I think that "cryptographically secure" is a bit too broad. Explaining to use /dev/random is great, but what other steps need to be taken to ensure it's cryptographically secure? \$\endgroup\$ – Nathan Merrill Mar 18 '17 at 17:52
  • \$\begingroup\$ @NathanMerrill See this. \$\endgroup\$ – ckjbgames Mar 18 '17 at 17:56
0
\$\begingroup\$

In an effort to improve things, I have split this challenge into two parts, both currently listed in this question for the sake of keeping them together.

NOTE: "Run a game of Flood" has now been posted.


Solve a game of Flood

This is a Code Challenge with Code Golf aspects.

Flood is a game in which the player is presented with a game board such as this: Initial Game Board

On each turn, you choose a colour (on the link above, by clicking a square containing that colour), and the cell in the top-left corner is filled with that colour - this colour will absorb all adjacent cells with the same colour. So, for example, the first turn might be Blue, which will cause the yellow cell in the top corner to turn blue, and merge with the existing blue cell. The next turn might be Purple, which will fill both of the first two cells purple, merging them with the two-cell purple area attached to them. Then you might go Red, then Orange. With this sequence, the board will end up as: After going Blue, Purple, Red, Orange

Your task is to write code that acts as a "solver" program/code, which reads in the initial/current state of the board, and determines the next move or the remaining moves. This code should make an effort to produce an efficient path to the solution, but you must balance this search for efficiency with the golfing effort.

Your code may make use of a simulator code (such as may be used in the "Run a game of Flood" challenge) that takes input of the current state of the board and a sequence of moves, and outputs the resulting state of the board after these moves - these must be the only inputs/outputs used by your code.

Your code must produce a solution for any initial board (not just the test boards, see below), and must be deterministic - that is, it must produce the same solution every time the same initial board is input (fixed-seed pseudorandom numbers are acceptable).

Scoring

As noted above, this is a combination Code Golf challenge. Your goal is to minimise your score, much of which is determined by the length of your code in bytes.

Your final score is b+2sum(n_i)+sum(d_i), where b is the total bytes of your code (simulator code does not count towards this value, but the call to simulator code does), n_i is the number of steps used by your solver program to solve each of the test boards (see below), and d_i is the maximal depth to which your code searches for each of the test boards before selecting a step.

The d_i value, here, is intended to punish those who use brute force to find the optimal solution. You need to find efficient solutions, cheaply.

Rules and Assumptions

Standard Loopholes are forbidden.

Code must be able to handle non-square boards, with each dimension being anywhere between 6 and 30 cells (more is fine, it must handle this range). It must be able to handle between 3 and 9 distinct colours or "colour" labels (numbers are fine).

You may assume that input is in simplest form - that is, if there are four colours, they will be labelled 1-4, or a-d, or any other similar system as appropriate. You will not need to handle situations such as incorrect inputs, unsimplified inputs (you won't have the numbers 1, 3, 6, and 9, without the others in between, unless it suits your code).

Your code may take input indicating details of the board such as dimensions and the set of valid "colours".

Your answer should include a description of formats, etc.

Code cannot treat the test boards as special cases - that is, you cannot have the code detect which test board it is, and if it doesn't match a test board, use a generic, low-quality code for solving.

Request: If you believe you have identified a non-standard loophole, and it's definitely a loophole and not in the spirit of the question, please comment to have the loophole closed, rather than posting an answer using it. This is not a rule, per se, but an effort to keep the challenge interesting.

Test Boards

7x6, 6 colours

Board 1

12x12, 6 colours

Board 2

12x12, 3 colours

Board 3

16x16, 9 colours

Board 4

Tags: Code-Challenge, Code-Golf, Optimization, Game

Not sure whether this should be labelled as Code-Challenge, Code-Golf, or both

\$\endgroup\$
  • 2
    \$\begingroup\$ The game itself is a nice challenge but I don't think it's a good idea to put both the simulation and the solver into the same challenge. They'd make perfectly decent separate challenges, especially since the scoring is mostly based on the solver, apart from the simulators byte count being added in. \$\endgroup\$ – Martin Ender Dec 13 '16 at 12:11
  • 1
    \$\begingroup\$ Also, there's this: codegolf.stackexchange.com/q/26232/8478 \$\endgroup\$ – Martin Ender Dec 13 '16 at 12:12
  • \$\begingroup\$ @MartinEnder - I'd considered having two separate challenges, but I realised that the solver code would likely require the simulation code or a variant of it, anyway. Or at least, there would be a lot of duplication between the two. Also, thanks for finding that past question - I did a quick search, but I didn't spot that particular question, for some reason (maybe I included the word "golf" in the search, I'm not sure) \$\endgroup\$ – Glen O Dec 13 '16 at 13:52
  • \$\begingroup\$ Given the issue with overlap between the two parts, what do you think - split them, leave the challenge as-is, or modify the question to merge the parts into a single code (so the code has to be able to take input, but will auto-solve for some input?) \$\endgroup\$ – Glen O Dec 13 '16 at 13:54
  • 2
    \$\begingroup\$ I'm definitely in favour of splitting. Especially since we've already done a solver challenge, I think just the simulation could be a really fun (and well-scoped) challenge. It could be as simple as "here is a grid and a list of moves, return whether the moves solve the grid". \$\endgroup\$ – Martin Ender Dec 13 '16 at 13:55
  • \$\begingroup\$ @GlenO I made the edit I did because as the challenge has already been posted, it shouldn't take up vertical space for no reason. \$\endgroup\$ – Okx Mar 20 '17 at 10:36
  • 1
    \$\begingroup\$ @Okx - I understood why you made the edit, but the thing is, there were two challenges, and only one had been posted. So I reverted, then removed the one I'd already posted and replaced it with a link. What remains is the unposted one. \$\endgroup\$ – Glen O Mar 20 '17 at 15:18
0
\$\begingroup\$

Block Puzzle

A popular brain teaser commonly known as a the "IQ Block Puzzle" is comprised of 8 colored shapes which can be rotated, moved and flipped on a 8x8 grid. The puzzle is known as a geometric magic square.

Block Puzzle

Challenge

The challenge is to generate and then output all 40 possible pattern combinations that the pieces can be placed in.

The output can be in any form, but must somehow represent the position of all pieces, for example:

Combination 1 of 40:

  11113333
  12213333
  12214444
  22555448
  22555448
  66657788
  66657788
  66777788

...

There will be a winner for both:

  • Shortest code in bytes
  • Fastest calculation of all shapes in ms
\$\endgroup\$
  • \$\begingroup\$ How can you beat a simple print statement? \$\endgroup\$ – Blue Mar 23 '17 at 19:45
  • \$\begingroup\$ That looks interesting but may require additional specifications. For instance, do the 40 patterns include symmetrical/rotated solutions? Including the actual shapes of the pieces as ASCII (or whatever) rather than relying on the picture alone would also help. Otherwise looks good! \$\endgroup\$ – Arnauld Mar 23 '17 at 19:47
  • \$\begingroup\$ I forgot: I don't think having two distinct winning criteria is a good idea. \$\endgroup\$ – Arnauld Mar 23 '17 at 20:00
  • \$\begingroup\$ It should be clarified that the shapes in the sample output are the actual shapes that the program should operate with. Also, this doesn't work as fastest-code; it's highly likely to be fastest to hardcode the output (with the only interesting part of the challenge being the fastest way to output a medium-length constant string, which is actually non-obvious). \$\endgroup\$ – user62131 Mar 24 '17 at 14:35
0
\$\begingroup\$

MCDI: Make and Change Directory into

Input: A string consisting of only alphanumeric characters, whose length does not exceed 255. It is given as string input, through STDIN on a single line, through ARGV, etc.

Effect: If a directory with the given name does not exist in the current directory, create it. Then, change the current directory to that directory. You can assume that no file with the given name exists.

Here is an example Batch script that does this (ungolfed, of course):

@ECHO OFF
IF NOT EXIST %1 MKDIR %1
CD %1
\$\endgroup\$
  • \$\begingroup\$ if it's possible but not normal to create directory names containing "/" or "\" in your environment, what should the script do when it encounters those? \$\endgroup\$ – Sparr Mar 24 '17 at 0:25
  • 1
    \$\begingroup\$ @Sparr A string consisting of only alphanumeric characters \$\endgroup\$ – Dennis Mar 24 '17 at 0:37
  • \$\begingroup\$ @Sparr Yeah, I didn't want to get into the nitty-gritty of file system's allowed characters (especially window's), so I restricted the domain to alphanumeric characters (as seen by the first sentence) \$\endgroup\$ – Conor O'Brien Mar 24 '17 at 0:40
  • \$\begingroup\$ Can we assume that there is no file with the same name? \$\endgroup\$ – Dennis Mar 24 '17 at 1:07
  • \$\begingroup\$ Also, what about full programs? I don't know how this works on Windows, but in Linux, you can only change the directory for the program itself. Once it finishes, you'll be back where you started. \$\endgroup\$ – Dennis Mar 24 '17 at 1:11
  • \$\begingroup\$ @Dennis Oh, hm. I suppose the batch script only works like that because it's windows. Perhaps I should add some sort of requirement, like, copy the original file to the location. Thoughts? \$\endgroup\$ – Conor O'Brien Mar 24 '17 at 1:19
  • \$\begingroup\$ @Dennis: that's not quite true. "/bin/cd" is a bit of a running joke in the esolangs community, because it's a fun absurd concept; it is possible to write, but it isn't possible to write in any sort of sane way. (When I wrote it myself, I had it attach a debugger to the parent process to change the current directory inside that process directly.) Without using debugger tricks, the program would need to run inside the parent process directly, which would basically limit the choice of language to sourced shellscripts (including the batch in the OP; that's a sourced language). \$\endgroup\$ – user62131 Mar 24 '17 at 14:27
  • \$\begingroup\$ Point taken, but I doubt the OP was expecting us to write something like that. \$\endgroup\$ – Dennis Mar 24 '17 at 14:30
0
\$\begingroup\$

Meta Code Golf

Late new year resolution: I'm finally cleaning up all my input and output files I used for code golf previously. Only problem is, I don't know which input and output files go to which code golf question on this site.

All problems used in this question should be posted on or before 31st December 2016 23:59:59 (GMT).

Input format:

The input would consist of an input and a correct output for the code golf question.

Each file can be accepted as an input file with a hardcoded filename, in the standard input, or as a function argument. The output can be a function return value, written to a file, or to standard output.

In the case both files are in standard input, you are allowed to define any arbitrary separator as long as it is consistent for all input files, and the separator is less than 16 bytes long.

You may assume that the separator is neither in the input file or in the output files. (All possible input files/output files with the separator in it are not used for scoring purposes.)

Output format:

Your code is required to output the ID of the question. Your code is allowed to have other non-numerical output.

For example, for this question:

https://codegolf.stackexchange.com/questions/64449/rearrangement-inequality

You can output any one of the following:

https://codegolf.stackexchange.com/questions/64449/rearrangement-inequality
64449
The question ID is 64449.
Just look at question 64449. You can find the question there.

Sandbox Meta: Scoring definitions

For each input-output pair, it may correspond to multiple questions. In that case, you may choose to output multiple answers, or only one answer. An input-output pair is considered to be correctly classified if it has at least one correct answer, and all provided answers are correct.

A question is considered correctly classified only if all input-output pairs corresponding to the question are correctly classified and the question ID is in the output for at least one of the input-output pairs corresponding to the question.

Sandbox Meta: Alternative definition

A question is considered correctly classified only if all input-output pairs with the question ID in the output are actual input-output pairs to the question, and all input-output pairs which do not correspond to the question do not have the question ID in the output.

Your score is the length of your code divided by the square of the number of correctly classified questions.

In the case the total number of questions you correctly classify is zero, you score positive infinity. Why am I even saying this? Of course it should work on at least one question.

Also, please claim the questions that your program correctly classified.

In the case that there are many ways the input and output for the question can be formatted, you are allowed to choose any one of them in the question, which is clearly allowed before 31st December 2016 23:59:59 GMT. You are allowed to choose different input/output formats for different questions.

It is guaranteed that none of the input-output pairs have infinite input or output. It is guaranteed that none of the input-output pairs have

I have some concerns:

As I may not have online access all the time, your code should not rely on looking at StackExchange to find the questions.

Finally:

This is , and the winner will be the person with the lowest score, in case of a tie, it would be tiebroken by submission time.

Sandbox Meta:

Lots of these questions might be difficult to encode the input, for example questions where the input is to a function.

\$\endgroup\$
  • \$\begingroup\$ What exactly is the input? A single test case, and the program should output a question for which the test case would pass? \$\endgroup\$ – Peter Taylor Mar 24 '17 at 11:38
  • \$\begingroup\$ @PeterTaylor The input consists of an input file, and a correct output for that question. The output would be the ID of the question. (Sorry if it wasn't clear.) \$\endgroup\$ – Element118 Mar 24 '17 at 11:40
0
\$\begingroup\$

Many Happy Returns!

I'm not sure whether to make this or .


Write a function that when it returns, it returns an extra frame up the stack. In other words, functions usually return directly to their callers; however, here the function should return directly to its caller's caller. To illustrate, consider this program:

#include <stdio.h>

int b(void) {
    int rc = 3;
    printf("%s(): returning from b()\n", __FUNCTION__);
    return rc;
}

int a(void) {
    int rc;
    rc = b();
    printf("%s(): returned from b()=%d\n", __FUNCTION__, rc);
    return 2;
}

int main(int argc, char *argv) {
    int rc;
    rc = a();
    printf("%s(): returned from a()=%d\n", __FUNCTION__, rc);
    return 0;
}

The output from this program is:

b(): returning from b()
a(): returned from b()=3
main(): returned from a()=2

An entry to this challenge would return from the innermost function c() in a special way such that the output is:

b(): returning from b()
main(): returned from a()=3

Note that the flow of execution goes directly from the return of b() back to the next line after where main() called a(). The returned from b() message is not output as this code never executes. It is not sufficient just to put this message in a conditional.

Rules

Assuming a template similar to this sample - i.e. main() calls a() calls b():

  • Entries are scored by the size of function b() in bytes - smallest wins.
  • Functions main() and a() must be provided, but are not included in the score
  • There must be no special logic in main() and a() that help. If the call to b() were replaced with a call to b1() (a normal function that returns normally), with no other modifications, then the returned from b() message would be observed.
  • You may assume that the return types of a() and b() are the same

I am aware that there are languages which make this very easy, but it is significantly more challenging (or maybe impossible) in other languages. I don't want to explicitly ban any languages, but I am most interested in the answers where the solution is non-trivial.

\$\endgroup\$
  • \$\begingroup\$ Your example is much longer and verbose than it needs to be, to the point that I think it's harder to follow than a minimal example would be. \$\endgroup\$ – Sparr Mar 24 '17 at 0:07
  • \$\begingroup\$ @Sparr I've shortened the example somewhat \$\endgroup\$ – Digital Trauma Mar 24 '17 at 5:31
  • \$\begingroup\$ What can be assumed about a(), particularly in terms of how many elements and of what type it will allocate on the stack? \$\endgroup\$ – Peter Taylor Mar 24 '17 at 11:40
0
\$\begingroup\$

Secret Santa

Goal: Given a list of names with public keys, assign each person a name, encrypt it with their public key and print the list of gifters with their encoded giftees.

Introduction

My family wanted to get a head start on Secret Santa (so they can shop sales though out the year). The problem was "how do we do this remotely?" Pubic key encryption, of course! My family is not very tech-savvy (or math-savvy). So after a several hours of phone calls, I was able to get everyone to generate public+private keys (by hand) and chat them to the group. Now I need to message back a gifter/giftee list.

Specification

  • Input
    • Flexible
    • A list of First Name, Last Name, Piece One of Key, Piece Two of Key tuples
    • So [ John, Smith, 351, 174 ] is an example tuple
    • n would be 351
    • e would be 174
    • Each name will be nonempty, capital and lowercase letters
    • Initials will be unique
  • Algorithm
    • For each tuple (i.e. gifter)
    • Randomly assign a giftee such that giftee != gifter
    • [NOTE] Each giftee should be assigned to exactly one gifter
    • Get the giftee's first initial and last initial
    • A or a = 1, B or b = 2, ..., Z or z = 26
    • Encrypt each initial
  • Encryption
    • The encryption of a number x is x^e % n
  • Output
    • Flexible
    • A list of gifters (first and last name) with the encrypted first and last initial of their giftee
  • Score
    • Shortest code in bytes wins

Test Cases

Input                         Middle Step                   Output
-----                         -----------                   ------
[Sherlock Holmes,1363,3]      Irene Adler => IA             [Sherlock Holmes,729,1]       
[John Watson,1763,11]         Mycroft Holmes => MH          [John Watson,281,935]         
[Mary Watson,1927,3]          John Watson => JW             [Mary Watson,1000,605]        
[Mycroft Holmes,1271,7]       Peter Jones => PJ             [Mycroft Holmes,256,1043]     
[Irene Adler,1073,5]          Mary Watson => MW             [Irene Adler,35,489]          
[Peter Jones,1073,5]          Sherlock Holmes => SH         [Peter Jones,688,578] 
\$\endgroup\$
  • \$\begingroup\$ "Assign a giftee such that giftee != gifter" seems to be lacking a constraint that each person should be giftee of exactly one gifter. \$\endgroup\$ – Peter Taylor Mar 23 '17 at 23:03
  • \$\begingroup\$ @PeterTaylor Good catch! I clarified that "Each giftee should be assigned to exactly one gifter" \$\endgroup\$ – NonlinearFruit Mar 24 '17 at 15:26
0
\$\begingroup\$

Simplify Brainf**k

We'll call a language BF equivalent if it emits a context-free substitution mapping to and from BF. For example, consider the hypothetical language SimpleBrain which is identical to BF except that it does not include + or >, but instead has }. It emits the following mapping to BF:

}: +>
<: <
-: -
.: .
,: ,
[: [
]: ]

And the following mapping from BF:

+: }<
>: -}
<: <
-: -
.: .
,: ,
[: [
]: ]

Challenge

Design a BF equivalent language. The language with the fewest commands wins (SimpleBrain, for example, has 7). In the event of a tie (which is likely) the language with the shortest representation with the mapping you provide of the following BF program wins:

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>
++.>+.+++++++..+++.>++.<<+++++++++++++++.>.
+++.------.--------.>+.>.

Sandbox Notes

There have been many efforts to "simplify" BF, but most of them shift complexity from the language to the interpreter. I've tried to formulate the rules in such a way that this cannot happen.

Are there interesting solutions to this challenge? I can only think of a few. I'd love to seem some creative answers to this problem. I am also looking for ways to better define context-free substitution mapping as what I have in mind clearly excludes trivial reductions like Braincrash because there is not a context-free mapping from Braincrash to BF, but I don't know if that's totally clear from the wording. By context-free substitution mapping, I mean substitution rules of the form:

a := b_1 b_2 ... b_n

where a is a single command in the source language and the RHS is any finite number of commands in the language we're mapping to (the LHS consists of a single symbol which is why I described it as context-free).

I also question whether this is exactly a programming puzzle per say. I am open to reformulating the challenge to make it better suited for the site if there is opposition.

\$\endgroup\$
  • \$\begingroup\$ esolangs seems to be down but if memory serves, there are 2-command or 1-command equivalents/analogs (Unary might count but I can't reference how it works) which already exist. Also I think an implication of Turing completeness implies that you can create a mapping to commands in another Turing complete language but I have not taken enough CS theory to back up that intuition. \$\endgroup\$ – cole Mar 25 '17 at 2:19
  • \$\begingroup\$ Yeah, Braincrash is the first 2-command example that comes to mind. There are also trivial equivalents that claim to reduce BF to two characters by using what amounts to a different encoding. But, as far as I can tell there isn't a mapping like the one I am trying to describe from any of these languages to BF (thus, they would not qualify). If you can find an example do let me know :) \$\endgroup\$ – Orby Mar 25 '17 at 4:05
  • \$\begingroup\$ Also, I agree with your intuition that there exist mappings between any two turing-complete languages, though I think they are usually not context-free. \$\endgroup\$ – Orby Mar 25 '17 at 4:07
  • \$\begingroup\$ One more comment: context-free is probably not the right word to use. I mean that the substitution rules are in the form A -> B_1B_2...B_n where LHS is a single command and RHS is any finite number of commands. \$\endgroup\$ – Orby Mar 25 '17 at 4:11
  • \$\begingroup\$ This is a code-challenge with metagolf as the tiebreak, so I'd say it's reasonable here. Also, it's going in a different direction from the typical BF minimizations on Esolang (although I've seen similar minimizations for other languages, like Underload); I like the requirement for the language to be compilable to and from BF by replacing each single character with a specific string, which puts hard limits on what sorts of cheating are allowed. I'd recommend that the equivalence be in terms of I/O behaviour, not values stored on the tape (so that the tape format can be changed). \$\endgroup\$ – user62131 Mar 26 '17 at 18:08
  • \$\begingroup\$ I like this challenge, but the simplest would only need two symbols a la Ook. \$\endgroup\$ – wizzwizz4 Dec 16 '17 at 19:53
0
\$\begingroup\$

Make a generated MIDI sound better

Being a crazy man, I sometimes listen to music made to midi trough a filter that makes it MIDI. It is a great experience, but I need to work a lot on it, because MIDI has a lot of instruments, and not every one sound good with every track

Challenge

Write a program that that finds which instrument represents the song the best

Input

A single .mid file

Output

A number representing MIDI instrument

Scoring

Score=Similarity/length by characters

Similarity is defined by executing Fourier transform and finding the percent of similarity between original and output sounds

Meta

Is this any good? and is scoring not exploitable?

\$\endgroup\$
  • 1
    \$\begingroup\$ You need to provide a lot more details on what task exactly is needed to perform. Also on how many test cases is the similarity mentioned in the scoring computed? Do you already have a program to measure similarity? \$\endgroup\$ – Laikoni Mar 26 '17 at 0:07
  • \$\begingroup\$ @Laikoni It's the part I'm working on now, so it may change a lot. I don't already have a program to measure similarity, but looks like it's preety easily done in Audacity. For test cases, i have some, but i don't have enough rep to add them. \$\endgroup\$ – Ignas Kiela Mar 26 '17 at 18:34
  • \$\begingroup\$ @ais523 I'm sure that it's difficult, it would already been done by now :) . For anti-brute-force restriction, i can't find a way to solve this puzzle that wouldn't be brute-forcing, so maybe adding a speed requirement would help? Or something that would require effective brute-forcing. \$\endgroup\$ – Ignas Kiela Mar 26 '17 at 18:38
  • \$\begingroup\$ restricted-complexity is probably the best way to add a speed requirement here (if you restrict it to quadratic, that means that doubling the length of the music to analyse can increase the runtime by no more than a factor of 4). That would allow pretty much all legitimate solutions, but disallow pretty much all brute force solutions \$\endgroup\$ – user62131 Mar 26 '17 at 22:14
0
\$\begingroup\$

Goodstein Sequences

From Wikipedia:

The Goodstein sequence G(m) of a number m is a sequence of natural numbers. The first element in the sequence G(m) is m itself. To get the second, G(m)(2), write m in hereditary base-2 notation, change all the 2s to 3s, and then subtract 1 from the result. In general, the (n + 1)-st term G(m)(n + 1) of the Goodstein sequence of m is as follows:

  1. Take the hereditary base-n + 1 representation of G(m)(n).
  2. Replace each occurrence of the base-n + 1 with n + 2.
  3. Subtract one. (Note that the next term depends both on the previous term and on the index n.)
  4. Continue until the result is zero, at which point the sequence terminates.

Example: The Goodstein sequence for 13 is:

  1. 2^(2+1)+2^2+2^0 = 13
  2. 3^(3+1)+3^3+3^0-1 = 3^(3+1)+3^3 = 108
  3. 4^(4+1)+4^4-1 = 4^(4+1)+3*4^3+3*4^2+3*4^1+3*4^0 = 1279
  4. 5^(5+1)+3*5^3+3*5^2+3*5^1+3*5^0-1 = 5^(5+1)+3*5^3+3*5^2+3*5^1+2*5^0 = 16092
  5. 6^(6+1)+3*6^3+3*6^2+3*6^1+2*6^0-1 = 6^(6+1)+3*6^3+3*6^2+3*6^1+6^0 = 280711

And so on

Your Task

Print the first 3 terms of the Goodstein sequence that starts on the input. If there are fewer than 3 terms, print out all the terms in the sequence (e.g. for input 1).

Example inputs and outputs:

Input: 1, Output: 1, 0

Input: 2, Output: 2, 2, 1

Input: 3, Output: 3, 3, 3

Input: 4, Output: 4, 26, 41

You may assume that the input will be a natural number from 1-200. Note that one of the challenges of this challenge is to support integers over 2^500.

Winning Criterion

This is , so shortest code wins! Answers from all languages are encouraged. The speed of the solution does not matter, as long as it eventually prints out the desired answer.

Fun Fact

All Goodstein sequences eventually converge to 0.

Tags: code-golf, math, sequence, number-theory, base-conversion

\$\endgroup\$
0
\$\begingroup\$

Darwin Fights

(code-challenge)

You are fighting a swarm of evolving enemies. Your goal is to outsmart them by turning evolution on its head.

The game consists of multiple rounds, starting with round 0. Every round n contains 5(n+1) enemies, so it starts out with 5, then 10, and so on. Each enemy has a couple statistics:

  1. Health -- the amount of health the enemy has left

  2. Attack -- the damage that the enemy can do

  3. Defense -- reduces damage done

  4. Reproduction -- controls the rate (chance) of reproduction

  5. Blur -- Makes the enemy seem weaker than it actually is.

The starting values for these numbers are taken from the previous round (details below), or if it is the first round, a mutated form of the enemy with health 1, attack 0, defense 0, reproduction 1, and blur 0. The player also has similar stats: health, attack, defense, and regeneration (how much health recovered per turn). You start off with 100 health, and the only condition on attack, defense, and regeneration is that their sum must be less than or equal to 10.

Details of turn order:

  1. All the enemies attack you, you lose health according to the damage formula below.

  2. You choose 3 enemies to attack or you nuke them (see below). It is advised to choose the 3 most powerful enemies to stop them from reproducing.

  3. All surviving enemies have the chance to reproduce. If r is their reproduction coefficient, their chance of reproducing is r/n where n is the total number of enemies. Thus, the expected number of new enemies is the average value of all the enemies' r-values.

  4. If there are no surviving enemies, the round is over. The next round starts and is populated with 5(n+1) enemies. Your health is restored. The next round's enemies' stats are determined by a weighted average of all the dead enemies' stats of the current round. They are weighted by the number of steps they survived in that round. Thus, it is important to eliminate strong enemies early in the round.

Damage: If the attacker has attack a and defender has defense d, the amount of health lost by the defender is a*(1-d/25). The minimum amount of damage is capped at a/4, so the value of d is essentially capped at 18.75 (it can be higher, but it wouldn't do any good).

Input You will get input in the following manner: a list of lists, each list containing the data for one enemy, in the order [health, attack, defense, reproduction]. Each of these values is reduced by a number uniformly chosen between 0 and blur. You will return the indices of the enemies you want to attack. If you return anything other than a list of 3 nonnegative integers (so e.g. an empty list), you choose to nuke the enemies.

Nuke: Nuking is just the ability to attack every enemy in a single turn. After nuking, you must wait 10 turns before being able to nuke again. Warning: since nuking attacks all enemies, it is common that a nuke will leave only strong enemies behind. Thus if there are survivors that reproduce, they will be the strongest. Use nukes carefully!

Reproduction: If an enemy is able to reproduce, it will choose a mate to mate with. The chance of being chosen as a mate is proportional to the attack power. It is possible the enemy's mate is itself (asexual), or that there is only one enemy left, in which case it is forced to reproduce asexually. The new enemy's traits is based on the average of the parents' traits, added to a mutation

Mutations: As soon as an organism is created, whether at the beginning of the round or from parents, its values are mutated. A normally distributed random number with mean 0 and standard deviation 0.3 is added to each one. A mutation will never cause the starting health or reproduction coefficient to go below 1, and will never cause the attack or defense to go below zero.

Score: Your score is the number of rounds you survive. Ties are broken by the amount of least health you had left at the end of any round before the last round. Scoring will be based off of taking your median run after running your code for a large number of times (to be determined, on the order of 100).

Controller: Currently written in python, available here: https://gist.github.com/prakol16/f0a306efd63a977a95c034b4b6e00ef1#file-darwin_main-py. To write your own class, extend the class Player and override the methods __init__ and get_attack

class ExamplePlayer(Player):
def __init__(self):
    # Should add up to 10
    super().__init__(attack=3, defense=0, regeneration=7)

def get_attack(self, enemies, round_num, nuke_recharge):
    if self.get_health() < 50 and nuke_recharge == 0:
        return [0]  # Nuke it!
    return [0, 1, 2]
\$\endgroup\$
0
\$\begingroup\$

Linear Chemistry

Input is a string representing a skeletal formula of a molecule, in a format similar to O=C-O-H. However as a lot of formulas contain carbon and hydrogen atoms, it is customary to skip them from the description and just signal their presence by only displaying the used bonds. We will call these atoms implicit atoms, while the ones that are shown explicitly in the formula explicit atoms.

Your job is to calculate the number of different atoms a specific skeletal formula contains.

The input is a one line string containing the following tokens:

  • -, =, symbolizing the bonds between the atoms
  • Any uppercase character followed by a number of lowercased characters symbolizing an atom of some sort (e.g. O, H, Br, Uub, etc.)

You have to output the number of different atoms this molecule contains in any sensible format.

Notes:

  • You can omit specifying the number of atoms if there is only one in the molecule
  • You may or may not merge the number of implicit and explicit atoms of C and H molecules (e.g. you can treat them as separate types).
  • You can output the atoms in any order

For example for the input string -OH valid output can be:

  • CH₃OH (preferred output)
  • CH3OH
  • CH4O
  • H4O1C1
  • {C:1,H:4,O:1}

Invalid outputs:

  • CHHHOH (you have to merge the same type of atoms into one)
  • CH2OH2 (you have to maintain the numbers for explicit and implicit C and H atoms properly if you didn't merge them)

You can use the following rules to parse the input:

  • For every explicit atom present in the input there will be one atom in the output. E.g. OOHOBrUub is O₃H₁Br₁Uub₁
  • Every bond token between two explicit atom tokens can be ignored. E.g. O-O, OO and O=O all mean the same thing: O₂
  • Two bond tokens following each other, or a bond token at any end of the string means an implicit C molecule and some amount of H molecules. The amount of H molecules will be 4 minus the amount of dashes in the bond tokens (1 for -, 2 for = and 3 for ). E.g. O--O means O₂CH₂, O-=O means O₂CH and O==O/O-≡O both mean CO₂.
  • You can always assume that there will be no invalid inputs where the number of implicit hydrogen atoms would be negative (e.g. ≡=, ≡≡, or =≡)

Examples:

-: C₂H₆
≡: C₂H₂
--: C₃H₈
==: C₃H₄
O==O: CO₂
-OH: CH₃OH (or CH₄O)
--OH: C₂H₅OH (or C₂H₆O)
-=-: C₄H₈
≡-≡: C₄H₂
=O≡-≡O=: C₄O₂H₄
Br-O-C-=Uub: BrOCCUubH (or BrOC₂UubH)

This is code golf, so shortest submission wins.

\$\endgroup\$
  • \$\begingroup\$ 1. The last test case seems to be missing two hydrogens from the explicit carbon. 2. I think that the detailed explanation of how implicit atoms work needs to be earlier. Most of the spec assumes that you understand it, but it comes right at the end. 3. I find it rather confusing that sometimes the bonds are omitted completely in the explanations (e.g. in OOHOBrUub), and even more so that none of the test cases cover this. \$\endgroup\$ – Peter Taylor Mar 28 '17 at 13:49
  • \$\begingroup\$ 1. You don't need to add hydrogens for the explicit atoms, I probably have to add this. 2. I wasn't sure where to put it exactly, I could swap the output spec with the input parsing 3. They're okay by the spec, and there are some examples (OH), but you are right I might need to add some more \$\endgroup\$ – SztupY Mar 28 '17 at 14:28
0
\$\begingroup\$

Let's play hide and seek.

The objective of this game is for the user to pick a spot on a grid (size given by user). For example, here is a 5x5 grid below.

--------------------------
| A1 |    |    |    |    |
|    |    |    |    |    | A
--------------------------
|    |    |    |    | B5 |
|    |    |    |    |    | B
--------------------------
|    | ME |    |    |    |
|    |    |    |    |    | C
--------------------------
|    | D2 |    |    |    |
|    |    |    |    |    | D
--------------------------
|    |    |    |    |    |
|    |    |    |    |    | E
--------------------------
  1    2    3     4    5

Each tile is identified by its cross section of letters and numbers, A1, D2, and B5 are shown above.

The user picks a random tile to hide in. I picked C2.

Now, you must build a program that will guess tiles.

If you are in the tile, you will respond with Y meaning the computer won.

Otherwise, you will give the direction from the guessed tile (N, NE, E, SE, S, SW, W, NW). So if the computer guesses D3, you would input NW.

Let me show you an example of what the program should look like.

Grid?
5x5

Pick: E2

Guess: C3?
SW
Guess: D2?
S
Guess: E2?
Y

The scoring for this program: The program will be tested for three different scenarios using the grid sizes: 5x5, 10x10, 20x10

The program should be able to guess the correct square in the minimum number of guesses.

Then, lowest bytes wins.

\$\endgroup\$
  • \$\begingroup\$ With your four scenarios I can get it in an average of 1.75. This is also an incredibly poor scoring system. \$\endgroup\$ – fəˈnɛtɪk Mar 30 '17 at 15:29
  • 1
    \$\begingroup\$ @fəˈnɛtɪk Should I make it a requirement to get the correct answer in the minimum number of guesses (and specify for each case)... and then just lowest bytes wins? \$\endgroup\$ – JKonowitz Mar 30 '17 at 15:33
  • 1
    \$\begingroup\$ Welcome to PPCG and thanks for posting in the sandbox! I like the premise of this challenge but as fəˈnɛtɪk has pointed out in the current form the scoring system is poorly defined. Also allowing larger board sizes might make for a harder challenge. \$\endgroup\$ – Laikoni Mar 30 '17 at 15:34
  • \$\begingroup\$ As a code challenge, this scoring system is incredibly bad because it will essentially allow you to pick and choose which answer will win. It would be better if you just made it a Code-golf challenge for code that will use the least moves on average to cover the entire board. \$\endgroup\$ – fəˈnɛtɪk Mar 30 '17 at 15:49
0
\$\begingroup\$

How far is this list from sorted?

Input: sequence of whitespace-separated base-10 integers (on stdin).

Output: minimal count (base-10 integer) of numbers which have to be moved to a different position in order to sort the list (to stdout).

Example

Input

0 1 2 4 5 6 3 9 7 8

becomes sorted by moving at least two numbers ‒ 3 and 9.

0 1 2 3 4 5 6 7 8 9

so the output would be 2.

  • For already sorted (including constant) or empty lists, the result is 0.
  • Shortest entry wins.
\$\endgroup\$
  • \$\begingroup\$ Can the input be a string or literary a list of numbers? \$\endgroup\$ – Anthony Pham Apr 2 '17 at 0:56
  • \$\begingroup\$ Seems like a duplicate of this, if I understand the task correctly. \$\endgroup\$ – Zgarb Apr 3 '17 at 7:47
  • \$\begingroup\$ @Zgarb No, that's something different. For sequence 1 7 2 2 4, the result of the task you linked would be 2 (the longest strictly increasing subsequence). In my task, it's 1 (you have to move 7 to the end to make it sorted). I think my task would be a bit more difficult than the other one. \$\endgroup\$ – kyrill Apr 3 '17 at 11:21
  • \$\begingroup\$ @kyrill, the result of the task Zgarb linked would be 3 because the longest strictly increasing subsequence is 1 2 4. Relax the strictly and it's asking for the length of the list minus the answer to your proposed question. I agree with Zgarb that it's a dupe. \$\endgroup\$ – Peter Taylor Apr 3 '17 at 11:30
  • \$\begingroup\$ @PeterTaylor Right, I didn't realize that. Duplicate it is. \$\endgroup\$ – kyrill Apr 3 '17 at 11:41
0
\$\begingroup\$

Route the phone calls

The challenge is to take the 3 ascii cities with 3 zones and (meta: in progress) and two phone numbers, you will return the cities with the phone lines that are used to connect the two calls replaced with a symbol of you choosing that is not used in the cities. (I will provide the cities at the end of this challenge post so you know).

Rules and notes

Everything must be the same except the phone lines (they will be the letter L)

Standard rules

The cities will be top down

Input

The cities shown as is without newlines (the cities will be connected together with phone lines :)

Two phone numbers (will be valid)in the format (xxxxxxxxxx)

Output

The cities with the connected calls

Meta

This is going to be a big project. I am not done writing the challenge for sure. I need cities and will start to make some but if anyone has cities or makes any I would be happy, a website with cities would also be pretty chill.

Any advice welcome

Also I am posting in sandbox as I have to get off the computer :P

\$\endgroup\$
0
\$\begingroup\$

Find the Least Conforming Word

Given a list of words, find which word follows Zipf's Law the least.

For each distinct word w in this list, we know the following two properties of w in this list:

  • Its frequency in the list (that is, the number of occurrences of it divided by the number of elements in the list), and
  • Its frequency rank; that is, the number of words that occur more often than it.

In the case that two words have the same frequency, we assume the one that comes first when sorted by lexicographical order is first.

If we plot a large list of words with regular natural language distribution on a logarithmic graph with these two properties as the x and y values, we see that the points form nearly a straight line with slope of approximately -1. This is known as Zipf's Law.

The Challenge

You will be given a list of words l. Imagine each distinct word being plotted this way on a logarithmic graph. Then, the line k is the Linear Regression Line for the data set. Then, for every point p except the top-most ranking and most frequent point, find the vertical distance to the line k, and let this distance be d. Then, we scale the vertical distance so that points in the middle of the line will be the most heavily weighted. We do this by the following. We find the x coordinate of the mid-point of the line (let this be x). Then, half of the horizontal span of the line is w, the width. If we let px be the x coordinate of the point p, then we multiply d by 1 - (x - px) / w. This value is the score.

Input

The input will be an unordered list of words in any reasonable format you wish.

Output

The output will be a single word indicating which word conforms the least to the "standard".

Test Case

Input: a a a a a a a a a a b b b b b b b c c c c c d d
Output: b
See an explanation here

\$\endgroup\$
  • 1
    \$\begingroup\$ 1. "Normal distribution" is a technical term: anyone who's studied statistics in English will immediately think of the distribution also known as Gaussian. IMO you should just call it Zipf's law. 2. The description given for the score is a) ambiguous and b) very odd. It's ambiguous because the question in general implies that the absolute difference should be what matters, but nothing explicitly says this. It's very odd because comparing gradients gives a massive bias towards the more frequent values. Why not vertical distance from the line? (And why not use the line of best fit?) \$\endgroup\$ – Peter Taylor Apr 4 '17 at 8:34
  • \$\begingroup\$ @PeterTaylor Thanks for the suggestions. Yes, I forgot that Normal Distribution is actually something. And yes, I should explicitly state absolute difference. The reason that I compare gradients is because vertical distance makes a larger difference near the ends of the line. So I will change the specs to compare vertical distance, but with a specific weighting. By the way, how is line of best fit calculated exactly? I can only find definitions where you draw a line that looks like it fits the system best. \$\endgroup\$ – user42649 Apr 4 '17 at 13:20
  • 1
    \$\begingroup\$ en.wikipedia.org/wiki/Linear_regression \$\endgroup\$ – Peter Taylor Apr 4 '17 at 13:31
  • \$\begingroup\$ @PeterTaylor Okay, thanks. I've adjusted the specs to include all of your suggestions. \$\endgroup\$ – user42649 Apr 4 '17 at 13:39
0
\$\begingroup\$

Lock the Language!

This is a challenge.

Cop's Thread:

Challenge:

  • Write a program that given two arbitrary integers adds those and prints them to STDOUT
  • In this Thread you post the fully working solution including language
  • The robbers will try to find any other language where an anagram of your source code will also add two integers
    • The language has to be a different one then yours
      • Different versions of the same language don't count as different languages
  • After 5 days you're code is safe and can't be cracked any more
  • If you're code is cracked you mark that in the header of the answer and add a link to the crack in the robbers thread

Winning criteria:

  • The shortest safe program (in bytes) wins.

Robber's Thread

  • The cops wrote an addition program you want to steal
  • Since the cops encrypted it so you can't use the same language as the cop you stole the program from used, so you have to use an different language
    • Different versions of the same language are count as the same language
  • You may use the cops character set in any order (anagram)

Winning criteria:

  • The robber with the most cracked answers wins.
\$\endgroup\$
  • \$\begingroup\$ Does it need to be a "proper" anagram or can I crack an answer by finding a language in which the solution is a polyglot? \$\endgroup\$ – Martin Ender Apr 4 '17 at 14:24
  • \$\begingroup\$ "After 5 days you're code is safe and can't be cracked any more." We usually require the cops to reveal their solution (after the period has passed) before they are considered safe. \$\endgroup\$ – Martin Ender Apr 4 '17 at 14:25
  • \$\begingroup\$ How does it work with languages using different encodings? Is it the actual characters that should be used for the anagram or the byte-values? \$\endgroup\$ – Emigna Apr 4 '17 at 14:26
  • \$\begingroup\$ Related. (Same idea, different task) \$\endgroup\$ – ETHproductions Apr 4 '17 at 14:27
0
\$\begingroup\$

Comment polyglot

From an original idea by Digital Trauma

The challenge

This challenge requires you to write a polyglot which contains a comment in as many languages as possible.

The comment must say This is a polyglot comment.

The program must do nothing at all.

The winner is whoever writes the polyglot with most languages!

The rules

Your submission should consist of a full program whose source contains the text "This is a polyglot comment".

For each language of the polyglot, your code executed in that language should:

  • Take no input
  • Generate no errors.
  • Produce either no output or the same output produced by the empty program in this language.
  • Still comply to the previous rules if any part of This is a polyglot comment is removed.

Addictionally, there can be no superflous code. This means that it should not be possible to remove a subset of characters (outside of the comment) and still have a submission that complies to the previous rules for all the languages of the polyglot.

Ok? Ok. Now please wait a minute before running to see how many languages you can find that use # for comments, because we have one more rule:

We define a character of your source as required for a language if removing that character makes the program change its behavior for that language (this could mean for example changing its output or producing an error). The sets of required characters for each language must all be distinct.

Example submission

#This is a polyglot comment

A polyglot in Python and Brainfuck for a score of 2.

The set of required characters for Brainfuck is empty. This is perfectly valid, as long as no other set is empty.

The set of required characters for Python is composed of just the first #. We can't add Bash to this submission because it would share the same set.

That's all, good luck and have fun!


Sandbox question:

  • Do you see any potential loopholes in the rules?
  • Should I add some other factors to the score (like code length for example) or is the number of languages enough?
  • Anything else I've missed?
\$\endgroup\$
  • \$\begingroup\$ I'm unsure about the definition of required. If I write ///This is a polyglot comment in a language which uses // for comments, is / a required character? If I remove one / nothing changes, but if I remove two then I get an error. Similarly, if my language has both # and // as comments, what is the required set for #///This is a polyglot comment ? \$\endgroup\$ – Peter Taylor Apr 5 '17 at 10:53
  • \$\begingroup\$ a character has to be required for at least one language I think it says \$\endgroup\$ – Destructible Lemon Apr 7 '17 at 3:12
  • \$\begingroup\$ @PeterTaylor you're right, this definition doesn't work. I'm having a hard time to come up with a correct one, I'll update this proposal if something suitable comes to my mind. \$\endgroup\$ – Leo Apr 8 '17 at 12:52
0
\$\begingroup\$

Operation Permutations

We're likely all familiar with the order of operations; the precedence rules that we use to govern basic arithmatic. Most schoolchildren are taught this order using an acronym such as "BODMAS", "BIDMAS", or "PEMDAS". There's no common consensus on the 'right' acronym to use, with the one that you learnt depending on the country you went to school in, or even the teacher who taught you. Your challenge is to determine the validity of an order of operations acronym (O3A), even if it's so unpronounceable that no-one would ever actually use it.

Challenge Specification

Input

Input for this program is guaranteed to be exactly six characters. Your program can require upper-case, require lower-case, or be case agnostic. You may accept this input in any manner that you please.

Each character is guaranteed to be one of the following: (B, P, I, O, E, D, M, A, S). Furthermore, each character is guaranteed to appear at most only once in the input.

The following characters correspond to the following operations:

| Characters | Operation      |
| ---------- | -------------- |
| (B, P)     | Brackets       |
| (I, O, E)  | Exponentiation |
| D          | Division       |
| M          | Multiplication |
| A          | Addition       |
| S          | Subtraction    |

Output

Your program must yield a truthy value for a valid O3A, and a falsy value for an invalid one. Your program is not expected to handle input not matching the above specification.

O3A Validity

The first character in a valid O3A must correspond to 'Brackets'. Likewise, the second character in a valid O3A must correspond to 'Exponentiation'. The next two characters must correspond to 'Division' and 'Multiplication', but either order is valid as these operations are on the same precedence level. The final two characters must correspond to 'Addition' and 'Subtraction', but again, either order is valid. Any other O3As are invalid.

Testing

Reference Implementation

The following Python 3 reference implementation is given for guidance. Note that while this reference implementation is case-agnostic, your program does not need to be.

def validate(acronym):
    acronym = acronym.upper()

    if acronym[0] not in {"B", "P"}:
        return False

    if acronym[1] not in {"I", "O", "E"}:
        return False

    if set(acronym[2:4]) != {"D", "M"}:
        return False

    if set(acronym[4:6]) != {"A", "S"}:
        return False

    return True

Test Input

BIDMAS => True
PEMDAS => True
PIDMSA => True
BOMDAS => True
BMIDAS => False
IBMDAS => False
BODAMS => False

Rules

  • This is , so the shortest code wins counted in bytes.
  • Standard rules and loopholes apply
  • Check meta for consensus

Sandbox Notes

My worry with this challenge is that it would be so trivially regex-able in something like Retina that it wouldn't be fun. I'd like feedback from others about this before going live.

\$\endgroup\$
  • 1
    \$\begingroup\$ So: test whether an input which is known to match [BPIOEDMAS]{6} also matches [BP][IOE](DM|MD)(AS|SA)? It's possible that there's a hash function which would be shorter than an actual check, but... If you're worried about boring answers then I suggest trying to find a solution which beats the boring regex in a language you know before posting. \$\endgroup\$ – Peter Taylor Apr 5 '17 at 11:53
  • \$\begingroup\$ @fəˈnɛtɪk I just checked, and no, it doesn't fail. \$\endgroup\$ – FourOhFour Apr 5 '17 at 12:09
  • \$\begingroup\$ @PeterTaylor I do believe that a shorter solution than a naive regex exists, but I also don't think I'm good enough at golfing to find it. Hence I posted on sandbox in the hope that more experienced golfers would be able to better judge the golf-ability of the challenge. \$\endgroup\$ – FourOhFour Apr 5 '17 at 12:10
  • 1
    \$\begingroup\$ @PeterTaylor You can actually shorten it slightly to ...[AS]+ since the input characters are also guaranteed to be unique (making it even harder to beat the regex solution). \$\endgroup\$ – Martin Ender Apr 5 '17 at 12:16
  • \$\begingroup\$ @MartinEnder, in fact that becomes [BP][IOE][MD]+[AS]+ applying the same reasoning. \$\endgroup\$ – Peter Taylor Apr 5 '17 at 14:58
  • \$\begingroup\$ @PeterTaylor Oh right, good catch. \$\endgroup\$ – Martin Ender Apr 5 '17 at 15:00
  • \$\begingroup\$ I've found a trick which lets me golf 3 chars off the regex-inspired solution in CJam (which doesn't have regexes). Perl will still beat it, but there's some non-trivial interest to the question. \$\endgroup\$ – Peter Taylor Apr 5 '17 at 15:19
  • \$\begingroup\$ @PeterTaylor I was hoping that it would still be an interesting challenge for CJam golfers etc... I might put it up live tomorrow on the basis that it's not completely trivial (so long as it's seen as an per-language challenge). \$\endgroup\$ – FourOhFour Apr 6 '17 at 0:08
0
\$\begingroup\$

Haiku detector in Haiku:

I found a haiku-w detector problem, and a popularity-contest challenge for writing factorial in haiku, but not the combination. Let's fix that:

Input: a string consisting of alphanumeric characters, standard punctuation, and |'s, where the | is used to indicate where the syllable splits are, and newlines (to indicate where the line splits are).

Output: a Truthy value if the string consists of zero or more triplets of lines where the first and third line have 4 |'s and the second line has 6 |'s.

Examples:

The|quick|brown|fox|jumps
O|ver|the|la|zy|dog|while
the|cat|eats|goat|cheese

--> True

This|is|not|a|hai|ku

--> False

A|B|C|d|E
1|2|3|4|5|6|7
A|B|C|D|E
Oops

--> False

Scoring: 1 Point for each triplet (so a whitespace answer will automatically win with a score of 0; I'm open to suggestions on how to mitigate this); this is code golf so lowest score wins.

Determining if code is valid haiku: Must consist of lines of code consisting of 5/7/5 syllables (with an optional empty line in between triplets)

Numbers and Variable names are read as written in standard English. If you want to get fancy and use a word that can be read as different number of syllables (e.g. coop as in chicken coop vs coop as in the short form of cooperative that isn't always rendered using an umlaut), have at it.

Special characters:

  ( is either 2,3 or 4 syllables (paren, left paren, open paren)
  ) is either 2, or 3 syllables (paren, right paren, close paren)
  ! is 1 or 5 syllables (bang, not, or exclamation point)
  . is 1 (dot)
  # is 1 (hash or pound)
  $ is 2 or 3 (dollar or dollar sign)
  % is 2 or 3 (percent or percent sign)
  - is 1 or 2 (dash, hyphen, minus)
  + is 1 or 2 (plus, plus sign)
  ^ is 2 (caret or xor)
  & is 3 (ampersand)
  * is 1 (star)
  [ is 2,3,4,5 (bracket, open bracket, left bracket, square bracket, open square bracket, etc.)
  ], {, and } are likewise 2,3,4,5
  _ is 3 (underscore)
  = is 2 (equals)
  : is 2 (colon)
  ; is 4 (semicolon)
  > is 2 or 3 (greater or greater than)
  < is 2 or 3
  --> is either combination of two -'s and one > or 2 (arrow)
  , is 2 (comma)
  / is 1 or 3 (slash or forward slash)
  \ is 2 (backslash)
  | is 1 or 4 (pipe or vertical bar)
  ? is 2 or 3 (question or question mark)
  @ is 1 (at)
  ~ is 2 (squiggle or tilde)
  ` is 2 (backtick)
  ' is 1 or 3 (quote or single quote)
  " is 3 (double quote)

Note that for everything but quote, if you use the same symbol 2 (or more times), you can instead say double symbol (or triple or whatever), e.g. && can be either 5 or 6 syllables)

I think that's all the punctuation... other unprintable characters are banned unless you can give a compelling argument on how many syllables it should be (and if I missed any pronounciation alternatives or other punctuation, let me know)

\$\endgroup\$
0
\$\begingroup\$

Golf the Stack Exchange code block

The standard Stack Exchange code block button / hot key prepends 4 spaces to each line, unless they all begin with 4 spaces, in which case it removes them. Additionally, it avoids changing the first or last lines if they are empty. But why stop at the first or last lines? Markdown is quite happy if intervening empty lines remain empty. As this saves bytes, I want you to write as short a program (or function) as you can that follows this enhanced behaviour:

  • All empty lines should remain unchanged
  • If all other lines begin with 4 spaces, then remove 4 spaces from them
  • Otherwise, prepend 4 spaces to each of them

This is , so the shortest program that breaks no standard loopholes wins.

Note that should your answer itself contain a blank line, you should ensure that there are no spaces on that line in your formatted code block.

\$\endgroup\$
  • \$\begingroup\$ Related (and currently active). I'd say this challenge should be explicitly described as a followup to that one, because it's basically "much the same task but harder". \$\endgroup\$ – user62131 Apr 9 '17 at 22:14
0
\$\begingroup\$

Swipe over the keyboard

(I'm not a native speaker so any good alternative for swipe is highly appreciated)

You have a keyboard in front of you and you swipe over the keyboard from left to right with your whole hand. Your task is to simulate the output. The keyboard is represented with 4 arrays (here is an example of a german keyboard layout, you are free to choose any other layout):

[1,2,3,4,5,6,7,8,9,0,ß,´]
[q,w,e,r,t,z,u,i,o,p,ü,+]
[a,s,d,f,g,h,j,k,l,ö,ä,#]
[<,y,x,c,v,b,n,m,,,.,-]

Now choose randomly one character of the first column [1,q,a,<]. Pop the chosen key and do the same with the newly created first column. For example the first key was q, the new first column will be [1,w,a,<]. The popped key will be printed out or skipped. Repeat it until your arrays are empty.

The rules are the following:

  • You can represent the keyboard with 4 arrays matching the 4 rows on your keyboard. For example [1,2,3,4,5,6,7,8,9,0,ß,´] would be my first row (german keyboard layout). Choose the keyboard layout you want, but it has to include all letters and numbers
  • There is no need to represent non-printable keys like tabulator, shift, backspace, ... so in general you won't hit the first and last column and the last row (you won't hit space too)
  • Since you are swiping from left to right, the probability to hit a previously located key is 0. So if the key 5 is pressed, the keys 1-4 won't be pressed anymore.
  • Each key needs to have a probability P!=0 to be pressed
  • Each key needs to have a probability P!=0 to be skipped
  • The rows are independent
  • There is no input

Open questions

  • Should I allow only one keyboard type?
  • Are there still rules that need to be added?
\$\endgroup\$
0
\$\begingroup\$

CRC Collision

Your task: Accept a string (one could also include symbols in the string, does not have to be only alphabets and numbers) of any length as input, calculate 16bit CRC for the given string. Output a string of same length which gives you the exact same CRC sum.

Example:

Input Text: Hello World!
Caclculated CRC : 0xF444

Output Text (with same CRC): DW=9Mzk?7P4y

You may use in-built CRC libraries to calculate.

Shortest code that fulfills the requirement wins!

\$\endgroup\$
  • \$\begingroup\$ What's the winning criterion? Can we use any 16-bit CRC or does it have to be a specific one? Which characters/bytes are allowed in input/output?What should happen if there isn't another string of the same length with the same checksum? \$\endgroup\$ – Dennis Apr 12 '17 at 15:53
  • \$\begingroup\$ @Dennis Any 16-bit CRC routine would do! It has to be a string i.e ASCII characters. The input string should be minimum 3 bytes long, there should be a collision right? \$\endgroup\$ – Abel Tom Apr 12 '17 at 16:06
  • \$\begingroup\$ I think so, yes, but I'm not sure if the output can only consist of ASCII characters. \$\endgroup\$ – Dennis Apr 12 '17 at 17:20
  • \$\begingroup\$ So i guess non ASCII characters are acceptable too! \$\endgroup\$ – Abel Tom Apr 13 '17 at 11:04
  • \$\begingroup\$ @Dennis Is there a suggestion to make it a little harder may be? Or can i put it like this as a challenge? \$\endgroup\$ – Abel Tom Apr 22 '17 at 16:55
0
\$\begingroup\$

Display a fractal maze

Based on this Puzzling.SE question: Alice and the Fractal Hedge Maze.

Given a description of a maze as input, output a [graphical / ASCII-art ?] representation of the maze.

Maze layout

For the purpose of this challenge, all inner mazes are assumed to be smaller copies of the original maze. So a top-down view of the above maze would look like this:

top-down view showing recursion

Input:

Input will be given as a list of connections between different ports of the same level of the maze and the inner sub-mazes.

One list of connections for the above maze would be the following:

1,12,a5,a12

This is because, in the maze, ports 1 and 12 are connected to each other, and they are also connected to ports 5 and 12 of sub-maze A.

A full description of the above example maze would be the following:

a3      (note that a connection by itself means this is the starting point)
1,12,a5,a12
2,8,10,a9,c4
3,b1,b4
4,b5,b6
5,d4,d5
6,d8
7,b7,d10
9,c7,c11
11,a10
b8,d1,d3
b11,b12
c2,c12
d11,d12

Flexibility:

You may take each port like above or as a tuple with numbers instead of letters, such as using 0 for the outer maze and numbering the inner mazes sequentially. So the following would all be acceptable for a line:

2,8,10,a9,c4
[2,8,10,(1,9),(3,4)]
[2,8,10,('A',9),('C',4)]
[(0,2),(0,8),(0,10),(1,9),(3,4)]
[(0,2),(0,8),(0,10),(-1,9),(-3,4)]

The starting point will be by itself. You can take it in the list as a port by itself, or as a separate parameter. The starting position will always be an entrance to a sub-maze. Each port will be listed at most once in the input. Note that not all ports have to be listed, as there are some dead ends.

Output:

Output a representation of the maze given. Note that mazes may require bridging of paths (crossing without connection).

Note: or ?

\$\endgroup\$
  • \$\begingroup\$ I think this challenge might be more interesting if it where about solving fractal mazes instead of displaying them. \$\endgroup\$ – Laikoni Apr 17 '17 at 8:51
  • \$\begingroup\$ That was going to be a second, separate challenge. \$\endgroup\$ – mbomb007 Apr 17 '17 at 13:29
0
\$\begingroup\$

Which answer is correct?

I've posted an earlier version of this question already; but now hoping to refine here before correcting the original post. Thanks all in advance for any advise.


I saw this elegant logic puzzle on Mathematics:

Which answer in this list is the correct answer to this question?

 1. All of the below.
 2. None of the below.
 3. All of the above.
 4. One of the above.
 5. None of the above.
 6. None of the above.

One user submitted a nice answer in code (quoted below), which inspired this puzzle.

Task:

Write code which determines the answer to the above logic puzzle according to standard Code Golf rules (i.e. a working solution with the minimum number of characters wins).

The input should be a sequence (i.e. ordered list / array) with each item in that sequence representing one of the given statements. Each items in the list should hold 2 values: - the first representing All, One, or None. - the second representing above, or below.

The result should be a list/array of the indices of any correct answers.

The following test scenarios are considered invalid; i.e. your code would not be expected to handle such data:

  • A statement is the first statement in the sequence and refers to the above, it evaluates to false.
  • A statement is the last statement in teh sequence and refers to the below, it evaluates to false.

We should be optimistic about results. i.e. given the following, the program would return 1, 2:

1. all of the below
2. one of the above

When contradictions occur, neither statement is correct. i.e. the following would return a blank string.

1. none of the below
2. none of the above

Code for Referenced Answer

// gcc ImpredictivePropositionalLogic1.c -o ImpredictivePropositionalLogic1.exe -std=c99 -Wall -O3

/*
Which answer in this list is the correct answer to this question?

(a) All of the below.
(b) None of the below.
(c) All of the above.
(d) One of the above.
(e) None of the above.
(f) None of the above.
*/

#include <stdio.h>
#define iff(x, y) ((x)==(y))

int main() {
  printf("a b c d e f\n");
  for (int a = 0; a <= 1; a++)
  for (int b = 0; b <= 1; b++)
  for (int c = 0; c <= 1; c++)
  for (int d = 0; d <= 1; d++)
  for (int e = 0; e <= 1; e++)
  for (int f = 0; f <= 1; f++) {
    int Ra = iff(a, b && c && d && e && f);
    int Rb = iff(b, !c && !d && !e && !f);
    int Rc = iff(c, a && b);
    int Rd = iff(d, (a && !b && !c) || (!a && b && !c) || (!a && !b && c));
    int Re = iff(e, !a && !b && !c && !d);
    int Rf = iff(f, !a && !b && !c && !d && !e);

    int R = Ra && Rb && Rc && Rd && Re && Rf;
    if (R) printf("%d %d %d %d %d %d\n", a, b, c, d, e, f);
  }
  return 0;
}

Test Cases

To represent the conditions in these test cases I've used the following convention:

  • [...] to represent the entire sequence
  • (match,direction) to represent each item where match and direction have values:

Match:

  • 0 - None of the
  • 1 - One of the
  • 2 - All of the

Direction:

  • 0 - below
  • 1 - above

1. The Original

[
    (2,0)  //all of the below
    ,(0,0) //none of the below
    ,(2,1) //all of the above
    ,(1,1) //one of the above
    ,(0,1) //none of the above
    ,(0,1) //none of the above
]

//expected answer is 5

2. Both

[
    (2,0)  //all of the below
    ,(1,1) //one of the above
]

//expected answer is 1, 2

3. Neither

[
    (0,0)  //none of the below
    ,(0,1) //none of the above
]

//expected answer is (nothing)

4. Simple

[
    (2,0)  //all of the below
    ,(0,1) //none of the above
]

//expected answer is 2
\$\endgroup\$
  • 2
    \$\begingroup\$ You should probably allow the output to be a list of possible answers, rather than requiring a string like you implicitly do at the moment. \$\endgroup\$ – user62131 Apr 13 '17 at 23:50
  • \$\begingroup\$ I believe you get only answer like this: sandbox.onlinephpfunctions.com/code/… First column the possible answer if only one is true as binary in decimal value second column is which answer are true also in binary as decimal value and in the third column only the answer where second column is equal to first column. I like this kind of problems \$\endgroup\$ – Jörg Hülsermann Apr 14 '17 at 1:11
  • \$\begingroup\$ Thanks @ais523; amended \$\endgroup\$ – JohnLBevan Apr 15 '17 at 8:36
0
\$\begingroup\$

Help me discover myself!

Hola, People call me file. At any point of time, all I know is how people compile me. Some use gcc some use gpp and some Java and some even csc. I couldn't really figure out who I am with just this info!

All I can do for you to help me is show a snippet inside me for you to find out the programming language. If you couldn't find with the snippet(the snippet will not have any incomplete line of code), only then can I share how programmers compile me.

And yes, you are brilliant enough to find out the language in which the program in me is written!

I may have...

Example1:

Input1:

int main(){return 0;}

Output1:

c|cpp

Input2:

gpp

Output2: c++

or

Input2:

gcc

Output2:

c

Example 2:

Input1:

#include<iostream>
int main(){return 0;}

Output1:

c++

Example3:

Input1:

main(){}

Output1:

c
  • the above example can't possibly be java because the mandatory return type for the method in java is missing.

Example4:

Input1:

#include<stdio.h>
main(){}

Output1:

c

Example5:

Input1:

class hola{public static void main(){}}

Output1:

java

Example6:

Input1:

class Hola{public static void Main(){}}

Output1:

c#

Oh yeah, I also know few things that might be helpful for you. The snippet that I'm allowed to share is only headers and the main function - first function that is called when program is executed.

And also, there are some conventions.

And then,

  • c - return type for main is not mandatory, standard header is stdio.h
  • c++ return type is mandatory, standard header is iosstream
  • c# - Main is a title - first letter is caps!

Input format Any code snippet it is more than enough if your answer identifies the above given six example snippet.

Output format programming language in which the snippet possibly fits in.

This is code golf and hence shortest code in each language wins!

\$\endgroup\$
  • \$\begingroup\$ How many languages - and which ones - do we need to support, and to which accuracy? Or, is it sufficient to hard-code the output for some given list of possible inputs? \$\endgroup\$ – John Dvorak Apr 17 '17 at 16:12
  • \$\begingroup\$ its enough if the answer supports the given input! And accuracy is 100% because, there is a certain restriction by languages and yeah I'll add that to the question \$\endgroup\$ – Keerthana Prabhakaran Apr 17 '17 at 16:18
  • \$\begingroup\$ I don't think I understand what the challenge is asking. "Assume the input is one of your choosing, and output the corresponding (single, hardcodeable) language"? \$\endgroup\$ – John Dvorak Apr 17 '17 at 16:20
  • \$\begingroup\$ one of six sample inputs and identify the language(c,c++,java or c# - yeah hardcodable). \$\endgroup\$ – Keerthana Prabhakaran Apr 17 '17 at 16:27
  • \$\begingroup\$ so, "hash the input and look up in a six-element table". Not fun. \$\endgroup\$ – John Dvorak Apr 17 '17 at 16:29
  • \$\begingroup\$ not really. There is a trick. If the input contains Class it goes without saying the the language is C# but if the input is int main the language can either be c or c++. It will a set of if and else'. \$\endgroup\$ – Keerthana Prabhakaran Apr 17 '17 at 16:39
  • 1
    \$\begingroup\$ Yeah, I could have a case statement with six regexes, but %w{c java c++ - - - python}[i.size%13] is much shorter. \$\endgroup\$ – John Dvorak Apr 17 '17 at 16:55
  • \$\begingroup\$ sorry I dont get what you mean by "input length % 13" \$\endgroup\$ – Keerthana Prabhakaran Apr 17 '17 at 16:56
  • \$\begingroup\$ I don't know what sources you've been reading about C#, but the capital Class will give a syntax error. \$\endgroup\$ – Peter Taylor Apr 17 '17 at 17:55
  • \$\begingroup\$ @PeterTaylor oh yeah you are right. I dunno why I ever typed that. Its been a while since I programmed using c#. I've edited the post. \$\endgroup\$ – Keerthana Prabhakaran Apr 17 '17 at 19:17
  • \$\begingroup\$ @JanDvorak you have edited your comment, but I still dont get it. \$\endgroup\$ – Keerthana Prabhakaran Apr 17 '17 at 19:21
  • \$\begingroup\$ Answer #1600... \$\endgroup\$ – programmer5000 Apr 17 '17 at 20:07
  • \$\begingroup\$ @programmer5000 don't get it. Can you please be more elaborate! \$\endgroup\$ – Keerthana Prabhakaran Apr 18 '17 at 1:14
  • \$\begingroup\$ @KeerthanaPrabhakaran oh, I was just remarking that we were on our #1600th sandbox submission. Now it's 1602... \$\endgroup\$ – programmer5000 Apr 18 '17 at 1:18
0
\$\begingroup\$

Generate a Voronoi Diagram

Challenge

Given a list of coordinates and colours of points, output a 300px by 300px Voronoi Diagram.

Winning

Shortest code in bytes wins.

To be expanded

\$\endgroup\$
  • 1
    \$\begingroup\$ output a what??? \$\endgroup\$ – Titus Apr 21 '17 at 17:15
  • \$\begingroup\$ @Titus A Voronoi Diagram. I'll add an explanation when I have time \$\endgroup\$ – Beta Decay Apr 21 '17 at 18:34
  • \$\begingroup\$ Five months later... \$\endgroup\$ – Gryphon - Reinstate Monica Sep 27 '17 at 4:38
  • \$\begingroup\$ @Gryphon It's a looong expansion ;) \$\endgroup\$ – Beta Decay Sep 27 '17 at 6:06
0
\$\begingroup\$

Google Autocomplete Fun

Your task is to create a program which, given an input string, will output the first Google autocomplete result for that search. The format of input/output is up to you.

Rules

  1. Your program must take 1 input, a string, and output the top Google autocomplete/auto-fill suggestions result. The format of input/output is up to you. Just be sure to mention what your I/O format is.
  2. Obviously, accessing the Internet is allowed.
  3. URL shorteners (like bit.ly, TinyURL, etc.) are strictly disallowed. You should fetch your autocomplete results from this URL: http://suggestqueries.google.com/complete/search?client=your_browser&q=your_query. You are allowed to assume any browser name for client. In the program I wrote, I assume Chrome. Any browser name or string should work.
  4. Please provide an explanation of how your program works. It is not mandatory, but I strongly advise it.
  5. All standard loopholes are strictly forbidden.

This is , so may the shortest code win and the best programmer prosper...

\$\endgroup\$
  • \$\begingroup\$ I think you technically need to allow internet access in the question. \$\endgroup\$ – Comrade SparklePony Apr 23 '17 at 20:51
  • \$\begingroup\$ @ComradeSparklePony You are so right. :) \$\endgroup\$ – ckjbgames Apr 23 '17 at 21:06
0
\$\begingroup\$

Calculate Call-Changes

Before learning to ring methods, novice bell-ringers usually first learn something called call-changes. This is basically a sequence of permutations (the changes), each one obtained from the previous by exchanging a pair of adjacent bells (the call).

The bells always begin in ascending pitch number order (which is actually descending pitch order). Each exchange (call) can be expressed in one of two different ways, depending on the whim of the conductor. Exchanges always use the bell's pitch number, regardless of the bell's current position.

  1. The exchange can be expressed as a pair of adjacent bell numbers in sequence. The first of the pair is always immediately before the second of the pair. The two bells simply exchange places, so the first of the pair ends up immediately after the second of the pair.

    • The exchange can be expressed as a bell number plus a second bell number which is two places before the first bell. The (unnamed) intervening bell and the first bell exchange places. This also results in the first input bell ending up immediately after the second input bell.
    • The above expression cannot be used to move a bell into first (lead) place, because there is no bell for it to end up after. You therefore need to accept an alternate way of expressing that the first two bells change places. Note that this must still refer to the pitch number of the bell in second place, but this might be achieved e.g. by having a sentinel value for the second bell, or by omitting it completely. (In real call-changes the call is "[number] lead!" rather than "[number] to [number]!".)

Your other input will be the number (not list) of bells in the sequence. You can assume that this will not be more than 9 (but supporting larger numbers may get you more upvotes). Here is a worked example showing the list of calls in both of the above formats and the desired output:

Call 1  Call 2  Output
(5 bells input  12345)
12      20*     21345
34      41      21435
14      42      24135
24      40*     42135
21      14      41235
41      10*     14235
42      21      12435
43      32      12345

*example representation.

Your program or function should output the result after each change. (Showing the initial permutation is permitted but not necessary.) Input and output can be any reasonable method, e.g. nested array of numbers or list of strings (note that if you use strings and want to support more than 9 bells then the next three bells are traditionally numbered 0, E and T). You can assume that all inputs follow the above pattern (or your custom representation for calling the seconds place bell into first place).

This is , so the shortest answer that breaks no standard loopholes wins!

\$\endgroup\$
  • \$\begingroup\$ I can't work out what the example is showing. Specifically: what input should the function/program take and what output should it produce? \$\endgroup\$ – Peter Taylor Apr 24 '17 at 8:48
  • \$\begingroup\$ @PeterTaylor Except for the first 12345 row, which is only there to try to help demonstrate the mechanics, the left column contains the result. However for each result there are two acceptable inputs (this is just a fact of life, not an attempt to make the question more complex); these are shown in the other two columns. \$\endgroup\$ – Neil Apr 24 '17 at 9:06
  • \$\begingroup\$ So e.g. the input is "42135", "24" and the output is "41235"? \$\endgroup\$ – Peter Taylor Apr 24 '17 at 9:58
  • \$\begingroup\$ No, the input is 5, "12", "34", "14", "24", "21", "41", "42", "43" and the output is "21345"..."42135", "41235"..."12345". \$\endgroup\$ – Neil Apr 24 '17 at 10:50
  • \$\begingroup\$ Could you edit the question to make that clearer? \$\endgroup\$ – Peter Taylor Apr 24 '17 at 13:51
  • \$\begingroup\$ @PeterTaylor Hopefully my rewrite is clearer now. \$\endgroup\$ – Neil Apr 26 '17 at 9:36
0
\$\begingroup\$

Excel NORMSINV function

Implement the excel NORMSINV function in your favourite language, shortest code wins

Build in functions and standard loopholes are not allowed

Loss of precision is also not allowed

Reference C Implementation

/*
 * Original C++ implementation found at http://www.wilmott.com/messageview.cfm?catid=10&threadid=38771
 * C# implementation found at http://weblogs.asp.net/esanchez/archive/2010/07/29/a-quick-and-dirty-implementation-of-excel-norminv-function-in-c.aspx
 *     Compute the quantile function for the normal distribution.
 *
 *     For small to moderate probabilities, algorithm referenced
 *     below is used to obtain an initial approximation which is
 *     polished with a final Newton step.
 *
 *     For very large arguments, an algorithm of Wichura is used.
 *
 *  REFERENCE
 *
 *     Beasley, J. D. and S. G. Springer (1977).
 *     Algorithm AS 111: The percentage points of the normal distribution,
 *     Applied Statistics, 26, 118-121.
 *
 *      Wichura, M.J. (1988).
 *      Algorithm AS 241: The Percentage Points of the Normal Distribution.
 *      Applied Statistics, 37, 477-484.
 */

#include <math.h>

double normsInv(double p, double mu, double sigma)
{
    if (p < 0 || p > 1)
    {
        printf("The probality p must be bigger than 0 and smaller than 1");
        exit(1);
    }
    if (sigma < 0)
    {
        printf("The standard deviation sigma must be positive");
        exit(1);
    }
    if (p == 0)
    {
        return -1e100;
    }
    if (p == 1)
    {
        return 1e100;
    }
    if (sigma == 0)
    {
        return mu;
    }

    double q, r, val;

    q = p - 0.5;

    /*-- use AS 241 --- */
    /* double ppnd16_(double *p, long *ifault)*/
    /*      ALGORITHM AS241  APPL. STATIST. (1988) VOL. 37, NO. 3
            Produces the normal deviate Z corresponding to a given lower
            tail area of P; Z is accurate to about 1 part in 10**16.
    */
    if (fabs(q) <= .425)
    {/* 0.075 <= p <= 0.925 */
        r = .180625 - q * q;
        val =
               q * (((((((r * 2509.0809287301226727 +
                          33430.575583588128105) * r + 67265.770927008700853) * r +
                        45921.953931549871457) * r + 13731.693765509461125) * r +
                      1971.5909503065514427) * r + 133.14166789178437745) * r +
                    3.387132872796366608)
               / (((((((r * 5226.495278852854561 +
                        28729.085735721942674) * r + 39307.89580009271061) * r +
                      21213.794301586595867) * r + 5394.1960214247511077) * r +
                    687.1870074920579083) * r + 42.313330701600911252) * r + 1);
    }
    else
    { /* closer than 0.075 from {0,1} boundary */

        /* r = min(p, 1-p) < 0.075 */
        if (q > 0)
            r = 1 - p;
        else
            r = p;

        r = sqrt(-log(r));
        /* r = sqrt(-log(r))  <==>  min(p, 1-p) = exp( - r^2 ) */

        if (r <= 5)
        { /* <==> min(p,1-p) >= exp(-25) ~= 1.3888e-11 */
            r += -1.6;
            val = (((((((r * 7.7454501427834140764e-4 +
                       .0227238449892691845833) * r + .24178072517745061177) *
                     r + 1.27045825245236838258) * r +
                    3.64784832476320460504) * r + 5.7694972214606914055) *
                  r + 4.6303378461565452959) * r +
                 1.42343711074968357734)
                / (((((((r *
                         1.05075007164441684324e-9 + 5.475938084995344946e-4) *
                        r + .0151986665636164571966) * r +
                       .14810397642748007459) * r + .68976733498510000455) *
                     r + 1.6763848301838038494) * r +
                    2.05319162663775882187) * r + 1);
        }
        else
        { /* very close to  0 or 1 */
            r += -5;
            val = (((((((r * 2.01033439929228813265e-7 +
                       2.71155556874348757815e-5) * r +
                      .0012426609473880784386) * r + .026532189526576123093) *
                    r + .29656057182850489123) * r +
                   1.7848265399172913358) * r + 5.4637849111641143699) *
                 r + 6.6579046435011037772)
                / (((((((r *
                         2.04426310338993978564e-15 + 1.4215117583164458887e-7) *
                        r + 1.8463183175100546818e-5) * r +
                       7.868691311456132591e-4) * r + .0148753612908506148525)
                     * r + .13692988092273580531) * r +
                    .59983220655588793769) * r + 1);
        }

        if (q < 0.0)
        {
            val = -val;
        }
    }

    return mu + sigma * val;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ A reference implementation is not a specification. \$\endgroup\$ – Peter Taylor Apr 26 '17 at 16:20
  • \$\begingroup\$ Yeah there are people who don't speak C. \$\endgroup\$ – Erik the Outgolfer Apr 26 '17 at 16:50
  • \$\begingroup\$ @Peter, do you have any suggestions on how I can create a specification for this? Do you think people will be interested or is this a dead end? \$\endgroup\$ – Johan du Toit Apr 26 '17 at 16:58
  • 1
    \$\begingroup\$ 1. Define the function: what are the inputs? What does the output mean? On the basis of some quick Googling I understand that it's an offset inverse of erf? But there seems to be disagreement about how many input parameters it takes. 2. Be explicit about the numerical analytic requirements. I'm not sure what "Loss of precision is also not allowed" means: that answers must avoid subtractions of values of similar magnitude? 3. With respect to interest, the thematically related codegolf.stackexchange.com/q/9070/194 got a few answers. \$\endgroup\$ – Peter Taylor Apr 27 '17 at 10:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .