How Slow Is Python Really (Part II)? This is a follow up to How slow is Python really? (Or how fast is your language?).

It turns out it was a bit too easy to get a x100 speedup for my last question. For those who have enjoyed the challenge but want something harder where they can really use their low level skills, here is part II.  The challenge is to get a x100 speedup for the following python code as tested on my computer.

To make it more difficult I am using pypy this time. The current timing for me is 1 minute and 7 seconds using pypy 2.2.1.

Rules

The first person to submit code which I can run, is correct and is x100 times faster on my machine will be awarded a bounty of 50 points.
I will award the win to the fastest code after a week.

import itertools
import operator
import random

n = 8
m  = 8
iters = 1000

# creates an array of 0s with length m
# [0, 0, 0, 0, 0, 0, 0, 0]
leadingzerocounts = [0]*m

# itertools.product creates an array of all possible combinations of the
# args passed to it.
#
# Ex:
#   itertools.product("ABCD", "xy") --> Ax Ay Bx By Cx Cy Dx Dy
#   itertools.product("AB", repeat=5) --> [
#    ('A', 'A', 'A', 'A', 'A'),
#    ('A', 'A', 'A', 'A', 'B'),
#    ('A', 'A', 'A', 'B', 'A'),
#    ('A', 'A', 'A', 'B', 'B'),
#    etc.
#   ]
for S in itertools.product([-1,1], repeat = n+m-1):
    for i in xrange(iters):
        F = [random.choice([-1,0,0,1]) for j in xrange(n)]

        # if the array is made up of only zeros keep recreating it until
        # there is at least one nonzero value.
        while not any(F):
            F = [random.choice([-1,0,0,1]) for j in xrange(n)]

        j = 0
        while (j < m and sum(map(operator.mul, F, S[j:j+n])) == 0):
            leadingzerocounts[j] +=1
            j += 1
print leadingzerocounts

The output should be similar to

[6335185, 2526840, 1041967, 439735, 193391, 87083, 40635, 19694]

You must use a random seed in your code and any random number generator that is good enough to give answers close to the above will be accepted.

My Machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor.  This also means I need to be able to run your code.

Explanation of code

This code iterates over all arrays S of length n+m-1 that are made up for -1s and 1s. For each array S it samples 1000 non-zero random arrays F of length n made up of -1,0 or 1 with probability of 1/4, 1/2,/14 of taking each values. It then computes the inner products between F and each window of S of length n until it finds a non-zero inner product. It adds 1 to leadingzerocounts at each position it found a zero inner product.

Status

Perl. 2.7 times slowdown by @tobyink. (Compared to pypy not cpython.)
J. 39 times speedup by @Eelvex.
C. 59 times speed up  by @ace.
Julia. 197 times faster not including start up time by @one-more-minute. 8.5 times speed up including start up time (it's faster using 4 processors in this case than 8).
Fortran. 438 times speed up by @semi-extrinsic.
Rpython. 258 times speed up by @primo.
C++. 508 times speed up by @ilmale.

(I stopped timing the new improvements because they are too fast and iters was too small.)

It was pointed out that timings below a second are unreliable and also some languages have a start-up cost. The argument is that if you are to include that you should also include the compilation time of C/C++ etc. Here are the timings for the fastest code with the number of iterations increased to 100,000.

Julia. 42 seconds by @one-more-minute.
C++. 14 seconds by @GuySirton.
Fortran. 14s by @semi-extrinsic.
C++. 12s by @ilmale.
Rpython. 18s by @primo.
C++. 5s by @Stefan.

The winner is.. Stefan!

Follow-up challenge posted. How high can you go? (A coding+algorithms challenge) . This one is  harder.

C++ x150 x450 x530

Instead of array I used bits (and dark magic).
Thanks @ace for the faster random function.

How does it work:
the first 15th bits of the integer s represent the array S[15]; the zeroes represent -1, the ones represent +1.
The array F is build in a similar way. But with two bit for each symbol.

00 represent -1
01 and 10 represent 0
11 represent 1

Cause S and F have a different representation I have to interleave S with itself to be comparable with F.

0 (-1) became 00 (-1 in the representation of F)
1 (+1) became 11 (+1 in the representation of F)

Now we can simply use Carnot to compute the inner product.
Remember that one variable can only assume value 00 or 11

0 . 00 = 11 (-1 * -1 = +1)
0 . 01 = 10 (-1 *  0 =  0)
0 . 10 = 01 (-1 *  0 =  0)
0 . 11 = 00 (-1 * +1 = -1)
1 . 00 = 00 (+1 * -1 = -1)
1 . 10 = 10 (+1 *  0 =  0)
1 . 01 = 01 (+1 *  0 =  0)
1 . 11 = 11 (+1 * +1 = +1)

Looks like a not xor to me. :)

Sum the ones is just a game of shift and mask, nothing really complex.

#include <array>
#include <ctime>

// From standford bithacks
// http://graphics.stanford.edu/~seander/bithacks.html
inline int32_t interleaveBit(int32_t x)
{
   static const uint32_t B[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
   x = (x | ( x << 8)) & B[3];
   x = (x | ( x << 4)) & B[2];
   x = (x | ( x << 2)) & B[1];
   x = (x | ( x << 1)) & B[0];
   return x | (x << 1);
}

inline int32_t sumOnes(int32_t v)
{
   static int b[] = { 1, 0, 0, 1};
   int s = 0;
   for( int i = 0; i < 8; ++i)
   {
      const int a = 3&(v>>(i*2));
      s += b[a];
   }
   return s;
}

inline int32_t sumArray(int32_t v)
{
   static int b[] = { -1, 0, 0, 1};
   int s = 0;
   for( int i = 0; i < 8; ++i)
   {
      const int a = 3&(v>>(i*2));
      s += b[a];
   }
   return s;
}

uint32_t x, y = 24252, z=57768, w=1564; //PRNG seeds

int32_t myRand()
{
   uint32_t t;
   t = x ^ (x<<1);
   x = y;
   y = z;
   z = w;
   w = w ^ ( w >> 19) ^ t ^ (t >> 8);
   return w;
}

int main()
{
   std::array<int, 8> leadingZero{0};
   x = static_cast<int32_t>(time(nullptr)); // seed PRNG
   const int maxS = 1 << 15;
   for(int s = 0; s < maxS; ++s)
   {
      const int32_t x = interleaveBit(s);
      for(int i = 0; i < 1000; ++i)
      {
         int32_t random;
         do
         {
            random = 0xFFFF & myRand();
         }while(sumOnes(random) == 0);
         int j = 7;
         while( j >= 0 )
         {
            const int32_t h = (x >> (j*2));
            const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
            if(sumArray(l) == 0)
            {
               leadingZero[j]++;
            } else
            {
               break;
            }
            j--;
         }

      }
   }
   for(int i = 7; i >= 0; --i)
   {
      printf("%d ", leadingZero[i]);
   }
   printf("\n");
   return 0;
}

Here a sample output:

6332350 2525218 1041716 438741 192917 87159 41023 19908

real 0m0.372s
user 0m0.371s
sys  0m0.001s

The program has been compiled with:

gcc -std=c++11 -O3 -msse4.2 -Wall -lstdc++ 26371.cpp -o fastPy

on Fedora 20 with gcc 4.8.2
The Cpu is a i7 8core.

Probably I can gain some ms tweaking compiler parameters.

While this is the OP solution time on my machine:

time pypy 26371.py
[6330609, 2523914, 1040885, 439303, 192708, 86987, 40710, 19498]

real 0m53.061s
user 0m53.016s
sys  0m0.022s

Edit:

Just adding openmp and change the order of the for I have a x3 gain, leading to a x450 performance improvement against OP code. :D
In this case the leadingZero array must be atomic. The random global... are random, they will be more random.

 #pragma omp parallel for
 for(int i = 0; i < 1000; ++i)
 {
    int32_t random;
    do
    {
       random = 0xFFFF & myRand();
    }while(sumOnes(random) == 0);
    for(int s = 0; s < maxS; ++s)
    {
       const int32_t x = interleaveBit(s);
       int j = 7;
       while( j >= 0 )
       {
          const int32_t h = (x >> (j*2));
          const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
          if( sumArray(l) == 0 )
          {
             leadingZero[j]++;
          } else
          {
             break;
          }
          j--;
       }
    }
 }

need to add -fopenmp to the compiler flag

Edit:2
As suggester by user71404 I changed the sumOnes and sumArray functions and now it's uber fast.

real  0m0.101s
user  0m0.101s
sys   0m0.000s

With openmp is slower, cause the atomics add too much overhead.

real  0m0.253s
user  0m1.870s
sys   0m0.001s

Without atomics is even faster, but I get wrong result.

2137992 1147218 619297 321243 155815 70946 32919 15579

real   0m0.048s
user   0m0.338s
sys    0m0.001s

To understand sumArray consider that 16 bit represent and array of 8 numbers.
00 have no 1 and represent -1
01 and 10 have one 1 and represent 0
11 have two 1s and represent 1
So that built-in count the number of bit set to 1 [http://en.wikipedia.org/wiki/Hamming_weight] and to each group we remove 1. Cool.

sumOnes is just black magic.

Here the latest compile flags and code.

gcc -std=c++11 -mfpmath=sse -O3 -flto -march=native -funroll-loops -Wall -lstdc++

#include <cstdint>
#include <cstdio>
#include <ctime>

inline int32_t interleaveBit(int32_t x)
{
   static const uint32_t B[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
   x = (x | ( x << 8)) & B[3];
   x = (x | ( x << 4)) & B[2];
   x = (x | ( x << 2)) & B[1];
   x = (x | ( x << 1)) & B[0];
   return x | (x << 1);
}

inline int32_t sumOnes(int32_t v)
{
   /* 0xAAAA == 0b1010 1010 1010 1010 */
   return !!(0xAAAA & (v ^ ~(v << 1)));
}

inline int32_t sumArray(int32_t v)
{
   return __builtin_popcount(v) - 8;
}

uint32_t x, y = 24252, z = 57768, w = 1564; //PRNG seeds

int32_t myRand()
{
   uint32_t t;
   t = x ^ (x << 1);
   x = y;
   y = z;
   z = w;
   w = w ^ ( w >> 19) ^ t ^ (t >> 8);
   return w;
}

int main()
{
   int leadingZero[8] = { 0 };
   x = static_cast<int32_t>(time(nullptr)); // seed PRNG
   const int maxS = 1 << 15;
   for( int i = 0; i < 1000; ++i )
   {
      int32_t random;
      do
      {
         random = 0xFFFF & myRand();
      } while(sumOnes(random) == 0 );
      for( int s = 0; s < maxS; ++s )
      {
         const int32_t x = interleaveBit(s);
         int j = 7;
         while( j >= 0 )
         {
            const int32_t h = (x >> (j * 2));
            const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
            if( sumArray(l) == 0 )
            {
               leadingZero[j]++;
            } else
            {
               break;
            }
            j--;
         }
      }
   }
   printf("[%d, %d, %d, %d, %d, %d, %d, %d]\n",
      leadingZero[7], leadingZero[6],
      leadingZero[5], leadingZero[4],
      leadingZero[3], leadingZero[2],
      leadingZero[1], leadingZero[0]);
   return 0;
}


Digging quarry timelapse Do you love watching cool timelapses of constructions or other massive work done in minutes? Lets make one here.
We will be looking at an excavator digging quarry, making pictures each day to see whole progress. And your task is to show us this process!

Quarry is defined by the width of its first layer.
Excavator is defined by its capability to dig in one day.

Input

Width of quarry. Integer number, always >= 1.
Excavator dig speed. Integer number, always >= 1.

Output

Progress of digging quarry on each day.
Started with flat untouched ground and finished with completed quarry.

Rules

On the last day there may be less units to dig, than excavator is
capable of. Excessive work won't be used anywhere, so you should just
output fully dug quarry.
All days progress must be present in the output at once. You can't clear or overwrite previous day progress in the output.
Trailing and leading newlines for each day output are acceptable in any reasonable number.
This is code-golf, so make your code as compact as possible.

Clarifications

Work starts with a flat ground. Length of displayed ground is width of quarry + 2. So there always will be one underscore character on both sides of quarry.

__________

Dug quarry is looking like this for even width:

_        _
 \      /
  \    /
   \  /
    \/

And like this for odd width

_       _
 \     /
  \   /
   \ /
    V

Here are examples of quarry progress:

_ _______
 V          dug 1 unit

_  ______
 \/         dug 2 units

_     ___
 \___/      dug 5 units

_       _
 \   __/    dug 10 units
  \_/

Full progress example. Quarry width: 8. Excavator speed: 4 units per day.

__________

_    _____
 \__/

_        _
 \______/

_        _
 \    __/
  \__/

_        _
 \      /
  \  __/
   \/

_        _
 \      /
  \    /
   \  /
    \/

Cornercases

Excavator will need to dig on the last day exactly its capability (speed)

Width: 7, Speed: 3
Width: 10, Speed: 4

Retina 0.8.2, 163 156 bytes

.+
$*_
(_+)¶(_+)
$2¶$1¶$1
r`__\G
$%`$&
¶
;
(?<=(_+);.*)(?<=;_+;\1*)_
¶$`_
m`^_+;
__
+`(>*)_(_+)(_+<?;)\2
$1_$.2$* $3¶$1>$2<;
T`>\_` \\`>+_
T`\\\_;<`V/_`.<|;

Try it online! Explanation:

.+
$*_

Convert the inputs to unary. This gives us W¶S.

(_+)¶(_+)
$2¶$1¶$1

Swap the inputs and duplicate the width. This gives us S¶W¶W.

r`__\G
$%`$&

Calculate the volume of the quarry. This gives us S¶W¶V.

¶
;

Join the inputs into one line. This gives us S;W;V.

(?<=(_+);.*)(?<=;_+;\1*)_
¶$`_

Calculate the amount of progress for each day on its own line. Each day has the format S;W;D, where D is 0 on the first line and increments by S each day until it reaches V.

m`^_+;
__

Delete S and increase W by 2 on each line. This gives us G;D for each day.

+`(>*)_(_+)(_+<?;)\2
$1_$.2$* $3¶$1>$2<;

While D is nonzero, dig either D or G-2 from the line (so the first and last characters are always left), moving the depth to the next line. Each line is indented with one more > than the previous. Newly dug lines also include a <.

T`>\_` \\`>+_

Turn the indent into spaces and the following _ into a \.

T`\\\_;<`V/_`.<|;

If a < is following a \ then turn it into a V, if it's following a _ then turn it into a /. Delete all the <s and ;s.


yes is 91 lines long yes, from coreutils, is 91 lines long. Many of them are comments, but that is still WAY too long.

Edit from September 2019: the source file grew over the past five years and is now 126 lines long.

Write a program that imitates yes:

outputting to stdout an infinite stream of "y\n"'s
there must be an option to stop it other than killing the process with SIGKILL: but SIGINT and SIGPIPE are fine
you are not allowed to use "y" or "\n" or their ASCII values (121, 0x79, 0171, 10, 0xA or 012)

Shortest answer wins.

Bonus:

subtract 10 from your code length, if you can receive a phrase in stdin and print it out instead of "y" (but still including the line-break). The program doesn't have to print y on an empty input.

CJam, 13 bytes - 10 = 3

l_'x)?{_oNo}h

You'll need to use the Java interpreter for this, because the online interpreter only returns once the program terminates.

You can abort the program with SIGINT (by pressing Ctrl-C). It will read a line from STDIN, and print that line, or y if the input was empty.

Explanation

l             "Read line from STDIN.";
 _            "Duplicate.";
  'x          "Push character x.";
    )         "Increment to get y.";
     ?        "Ternary operator. Replaces line with y if it was empty.";
      {    }h "Repeat while true. Leaves condition on the stack, which is the output string.";
       _o     "Duplicate line and print.";
         No   "Push string with newline and print.";

After clarification of the OP, the following seems more to spec:

l{_o9c)o1}g

I'll wait with updating the submission until the OP replies to my comment, though.


Implement bzip2's run-length encoding Background

After applying the BWT (as seen in Burrows, Wheeler and Back) and the MTF (as seen in Move to the printable ASCII front), the bzip2 compressor applies a rather unique form of run-length encoding.

Definition

For the purpose of this challenge, we define the transformation BRLE as follows:

Given an input string s that consists solely of ASCII characters with code points between 0x20 and 0x7A, do the following:

Replace each run of equal characters by a single occurrence of the character and store number of repetitions after the first.
Encode the number of repetitions after the first occurrence of the character, using bijective base-2 numeration and the symbols { and }.

A non-negative integer n is encoded as the string bk…b0 such that n = 2ki(bk)+…+20i(b0), where i({) = 1 and i(}) = 2.

Note that this representation is always unique. For example, the number 0 is encoded as an empty string.
Insert the string of curly brackets that encodes the number of repetitions after the single occurrence of the corresponding character.

Step-by-step example

Input:  "abbcccddddeeeeeffffffggggggghhhhhhhh"
Step 1: "abcdefgh" with repetitions 0, 1, 2, 3, 4, 5, 6, 7
Step 2: "" "{" "}" "{{" "{}" "}{" "}}" "{{{"
Step 3: "ab{c}d{{e{}f}{g}}h{{{"

Task

Implement an involutive program or function that reads a single string from STDIN or as command-line or function argument and prints or returns either the BRLE or its inverse of the input string.

If the input contains no curly brackets, apply the BRLE. If the input contains curly brackets, apply its inverse.

Examples

INPUT:  CODEGOLF
OUTPUT: CODEGOLF

INPUT:  PROGRAMMING
OUTPUT: PROGRAM{ING

INPUT:  PUZ{LES
OUTPUT: PUZZLES

INPUT:  444488888888GGGGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
OUTPUT: 4{{8{{{G{{{{W{{{{{

INPUT:  y}}}{{
OUTPUT: yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

Additional rules

You cannot use any built-ins that compute the BRLE or its inverse of a string.
You can use built-ins that:

Compute the RLE or RLD of a string, as long as the number of repetitions is not stored in bijective base-2.
Perform base conversion of any kind.

Your code may print a trailing newline if you choose STDOUT for output.
Your code has to work for any input of 1000 or less ASCII characters in the range from 0x20 to 0x7A, plus curly brackets (0x7B and 0x7D).
If the input contains curly brackets, you may assume that it is a valid result of applying the BRLE to a string.
Standard code golf rules apply. The shortest submission in bytes wins.

CJam, 50 48 bytes
l_{}`:T&1${_T#)_(@a?)+}%{(\2b)*}%@e`{(2b1>Tf=}%?

Thanks for Dennis for saving 2 bytes.
Try it online.
Explanation
l_              e# Read and duplicate input.
{}`:T           e# T = "{}"
&               e# If the input has '{ or '}:
    1$          e# Input.
    {           e# For each character:
        _T#)    e# If it is '{ or '}:
            _(  e# Return 0 for '{ or 1 for '}.
            @a  e# Otherwise, convert the character itself to an array (string).
        ?
        )+      e# If it is a number, increment and append to the previous array.
                e# If it is a string with at least 1 character, do nothing.
    }%
    {(\         e# For each character and bijective base 2 number:
        2b)*    e# Repeat the character 1 + that many times.
    }%
                e# Else:
    @           e# Input.
    e`          e# Run-length encoding.
    {(          e# For each character and length:
        2b1>    e# Convert the length to base 2 and remove the first bit.
        Tf=     e# Map 0 to '{ and 1 to '}.
    }%
?               e# End if.


Build a Primitive Root Diffuser Introduction

When a room has bare, parallel walls, it can create unpleasant repeating acoustic reflections (echoes).  A diffuser is a device mounted on a wall which creates a blocky surface of many different heights.  This has the effect of breaking up the reflected sound into many smaller reflections (each with a different time delay).  The acoustic quality of the room is thought to be greatly enhanced.

Primitive Root Diffuser

The primitive root diffuser uses a grid of (typically wooden) posts, each with a different height (to obtain a different reflection delay time).  The heights of the posts are chosen according to successive powers of a primitive root G, modulo N (a prime number).

Here are some pictures of a primitive root diffuser.

Task

You must write a program or function which takes a prime number N > 2 as its only input.  It must then select a primitive root of N.  G is a primitive root of N if the successive powers of G modulo N generate all the integers from 1 to N-1.  A more formal definition of primitive roots can be found in the Wikipedia article.

Your code must then place these successive powers into an X-by-Y array (or matrix).  Because we want to hang this on the wall, the diffuser should be a convenient shape - as close to square as possible.  The number of entries in the array will be N-1, so its dimensions X and Y should be chosen such that X*Y = N-1, and X is near but not equal to Y (specifically, X and Y are coprime).  For convenience of display, the horizontal dimension should be greater than the vertical dimension.

The order of placement of successive powers of G (modulo N) should start at one corner of the array, then traverse diagonally through the array, wrapping around in both directions until all array positions are filled.  Then the function should return that array, or print it to stdout, whichever you prefer.

We won't concern ourselves with the measurement units used to actually cut the posts to length; we'll assume the units are appropriate for the range of audio frequencies we want to diffuse, and stick to integers.

There's an online calculator, in case you want to check your work.  However, the site appears to be down currently.

Example

Suppose we choose N = 41.  Our program should select one of the primitive roots of N, which are [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35].  Suppose our program selects the smallest primitive root, G = 6.

Our program then chooses the squarest dimensions X,Y for the array such that X*Y = N-1.  The clear choice is X=8 and Y=5.

Then our program populates the array with successive powers of G modulo N (starting with G^0), traversing diagonally.  The program then returns/prints the array:

1   14  32  38  40  27  9   3
18  6   2   28  23  35  39  13
37  26  36  12  4   15  5   29
10  17  33  11  31  24  8   30
16  19  20  34  25  22  21  7

Note how it begins with 6^0 mod 41 = 1, then 6^1 mod 41 = 6, then 6^2 mod 41 = 36, then 6^3 mod 41 = 11, etc.

To clarify, the sequence of powers of 6 modulo 41 is:

[1, 6, 36, 11, 25, 27, 39, 29, 10, 19, 32, 28, 4, 24, 21, 3, 18, 26, 33, 34, 40, 35, 5, 30, 16, 14, 2, 12, 31, 22, 9, 13, 37, 17, 20, 38, 23, 15, 8, 7]

Another Example

N = 31

Assuming the program selects G = 11, X = 6, Y = 5, the output is:

1   26  25  30  5   6
4   11  7   27  20  24
16  13  28  15  18  3
2   21  19  29  10  12
8   22  14  23  9   17

A Third Example

N = 37

Assuming the program selects G = 2, X = 9, Y = 4, the output is:

1   12  33  26  16  7   10  9   34
31  2   24  29  15  32  14  20  18
36  25  4   11  21  30  27  28  3
6   35  13  8   22  5   23  17  19

Scoring

Standard code golf rules - the fewest bytes of code producing correct output wins!


How much code would a codegolf golf if a codegolf could golf code? Write a function or program that takes two words as input and outputs variants of the popular English tongue-twister "How much wood would a woodchuck chuck if a woodchuck could chuck wood?".

The output will use the first word four times

How much wood would a woodchuck chuck if a woodchuck could chuck wood?

and the second word four times

How much wood would a woodchuck chuck if a woodchuck could chuck wood?

with the rest of the output being the same for any inputs.

How muchwoodwould awoodchuckchuckif awoodchuckcouldchuckwood?

The input and output can be in any format that your language reasonably recognizes as dealing with strings of text. The output must be exactly in the indicated format, including capitalization, spaces and lack thereof, and the ending question mark. An optional trailing newline is acceptable.

Ideally your code will handle input containing any printable ASCII characters. However, it is permitted to restrict the input to reasonable subsets of printable ASCII; just indicate this in your answer. Handling larger character sets is of course fine.

Example input-output pairs:

"wood", "chuck"
"How much wood would a woodchuck chuck if a woodchuck could chuck wood?"

"ground", "hog"
"How much ground would a groundhog hog if a groundhog could hog ground?"

"bar", "keep"
"How much bar would a barkeep keep if a barkeep could keep bar?"

"money", "belt"
"How much money would a moneybelt belt if a moneybelt could belt money?"

"rain", "fall"
"How much rain would a rainfall fall if a rainfall could fall rain?"

"hair", "cut"
"How much hair would a haircut cut if a haircut could cut hair?"

"green", "house"
"How much green would a greenhouse house if a greenhouse could house green?"

"jabber", "wock"
"How much jabber would a jabberwock wock if a jabberwock could wock jabber?"

"pine", "apple"
"How much pine would a pineapple apple if a pineapple could apple pine?"

"Rob", "Lowe"
"How much Rob would a RobLowe Lowe if a RobLowe could Lowe Rob?"

"code", "golf"
"How much code would a codegolf golf if a codegolf could golf code?"

"fish", ""
"How much fish would a fish  if a fish could  fish?"

"", "fish"
"How much  would a fish fish if a fish could fish ?"

"", ""
"How much  would a   if a  could  ?"

"  ", "     "
"How much    would a               if a         could         ?"

"would a", "how much"
"How much would a would a would ahow much how much if a would ahow much could how much would a?"

This is code-golf, so fewest bytes wins. Answers are welcome in all languages, even if some other language can do it in fewer bytes.

(Inspired by this meme, which uses one input pair better than this rigid pattern does....)

Python 3, 70 67 bytes

"How much {0} would a {0}{1} {1} if a {0}{1} could {1} {0}?".format

Try it online!

I mean, if the shoe fits..

Thanks to manatwork for catching a typo

Thanks to Remco Haszing for the excellent -3 bytes idea

I am running off of the assumption that this would still be a valid submission (because man, it's too cool not to try). If OP could clarify whether this is acceptable (because I haven't written a function, per se), that would be appreciated.

Update: Blessing received, all is good :)

Previous version:

lambda a,b:f"How much {a} would a {a+b} {b} if a {a+b} could {b} {a}?"


Will it halt? (Cops) This is the cops' thread. The robbers' thread is here.

Your challenge is to make a program that runs forever without halting1, unless it gets a particular input or inputs2. If it receives that input, it must terminate in a finite amount of time3. This is code-golf, so the shortest answer that has not been cracked by a robber within one week of posting wins. After the week has passed, please mark your answer as safe and show the halting input (in a > ! spoiler quote). If a robber cracks your submission, please mark it as cracked and show the halting input (in a > ! spoiler quote).

Submissions are preferred be runnable & crackable on TIO. Submissions not runnable or crackable on TIO are allowed, but please include instructions to download / run them.

Please make your input deterministic, and uniform across all runs. See this meta post for details.

Please, don't "implement RSA" or anything mean to the robbers. Use obscure languages and features, not boring encryption and hashing. I can't enforce this with rules, but you can expect torrential downvotes if all you do is sha(input) === "abcd1234".

1Assuming that the computer doesn't get shut down, break, get engulfed by the sun, overheat in the universe's heat death, or hit the TIO timeout of 60s.

2The program must halt on at least one input. As long as it loops forever on one input and halts on another, it works.

3This must be < 60 seconds, so that the code can be tested on TIO.

Looking for uncracked submissions?

fetch("https://api.stackexchange.com/2.2/questions/135363/answers?order=desc&sort=activity&site=codegolf&filter=!.Fjs-H6J36vlFcdkRGfButLhYEngU&key=kAc8QIHB*IqJDUFcjEF1KA((&pagesize=100").then(x=>x.json()).then(data=>{var res = data.items.filter(i=>!i.body_markdown.toLowerCase().includes("cracked")).map(x=>{const matched = /^ ?##? ?(?:(?:(?:\[|)([^\]]+)(?:\]|<\/a>)(?:[\(\[][a-z0-9/:\.]+[\]\)])?)|([^, ]+)).*[^\d](\d+) ?\[?(?:(?:byte|block|codel)s?)(?:\](?:\(.+\))?)? ?(?:\(?(?!no[nt][ -]competing)\)?)?/gim.exec(x.body_markdown);if(!matched){return;}return {link: x.link, lang: matched[1] || matched[2], owner: x.owner}}).filter(Boolean).forEach(ans=>{var tr = document.createElement("tr");var add = (lang, link)=>{var td = document.createElement("td");var a = document.createElement("a");a.innerHTML = lang;a.href = link;td.appendChild(a);tr.appendChild(td);};add(ans.lang, ans.link);add(ans.owner.display_name, ans.owner.link);document.querySelector("tbody").appendChild(tr);});});

Uncracked Submissions

Language	Author

Malbolge, 128 bytes, cracked by KBRON111

(=&r:#o=~l4jz7g5vttbrpp^nllZjhhVfddRb`O;:('JYX#VV~jS{Ql>jMKK9IGcFaD_X]\[ZYXWVsN6L4J\[kYEhVBeScba%_M]]~IYG3Eyx5432+rpp-n+l)j'h%B0

Have fun!

(Yes, I learned Malbolge just for this. Yes, it took an absurdly long time to finally get working. And yes, it was totally worth it.)

Wrapped, so you can see it in its full, er, "glory":

(=&r:#o=~l4jz7g5vttbrpp^nllZjhhV
fddRb`O;:('JYX#VV~jS{Ql>jMKK9IGc
FaD_X]\[ZYXWVsN6L4J\[kYEhVBeScba
%_M]]~IYG3Eyx5432+rpp-n+l)j'h%B0

I used this interpreter to test it; I'm not sure if it matters, but I figured I'd specify just in case.


Is this a Major Scale (or equivalent)? Sandbox

The major scale (or Ionian scale) is one of the most commonly used musical scales, especially in Western music. It is one of the diatonic scales. Like many musical scales, it is made up of seven notes: the eighth duplicates the first at double its frequency so that it is called a higher octave of the same note.

The seven musical notes are:

  C, D, E, F, G, A, B, C (repeated for example purposes)

A major scale is a diatonic scale. Take the previous succession of notes as a major scale (Actually, It is the scale C Major). The sequence of intervals between the notes of a major scale is:

  whole, whole, half, whole, whole, whole, half

where "whole" stands for a whole tone (a red u-shaped curve in the figure), and "half" stands for a semitone (a red broken line in the figure).

In this case, from C to D exist a whole tone, from D to E exist a whole tone, from E to F exist half tone, etc...

We have 2 components that affects the tone distance between notes. These are the Sharp symbol (♯) and the flat symbol (♭).

The Sharp symbol (♯) adds half tone to the note. Example. From C to D we mentioned that exists a whole tone, if we use C♯ instead C then from C♯ to D exists half tone.

The Flat symbol (♭) do the opposite of the Sharp symbol, it subtract half tone from the note. Example: From D to E we mentioned that exists a whole tone, if we use Db instead D then from Db to E exists a tone and a half.

By default, from Note to Note exist a whole tone except for E to F and B to C in where just half tone exists.

Note in some cases using enharmonic pitches can create an equivalent to a Major Scale. An example of this is C#, D#, E#, F#, G#, A#, B#, C# where E# and B# are enharmonic but the scale follows the sequence of a Major Scale.

Challenge

Given a scale, output a truthy value if it is a Major Scale or equivalent, otherwise output a falsey value.

Rules

Standard I/O method allowed
Standard code-golf rules apply
You don't need to take in consideration the 8th note. Assume the input will only consist of 7 notes
Assume double flat (♭♭), double sharp (♯♯) or natural sign (♮) don't exist

Test cases

C, D, E, F, G, A, B                 => true
C#, D#, E#, F#, G#, A#, B#          => true
Db, Eb, F, Gb, Ab, Bb, C            => true
D, E, Gb, G, A, Cb, C#              => true
Eb, E#, G, G#, Bb, B#, D            => true
-----------------------------------------------
C, D#, E, F, G, A, B                => false
Db, Eb, F, Gb, Ab, B, C             => false
G#, E, F, A, B, D#, C               => false
C#, C#, E#, F#, G#, A#, B#          => false
Eb, E#, Gb, G#, Bb, B#, D           => false

Perl 6, 76 65 63 59 bytes

-4 bytes thanks to Phil H

{221222==[~] (.skip Z-$_)X%12}o*>>.&{13*.ord+>3+?/\#/-?/b/}

Try it online!

Explanation

*>>.&{ ... }  # Map notes to integers
  13*.ord     # 13 * ASCII code:  A=845 B=858 C=871 D=884 E=897 F=910 G=923
  +>3         # Right shift by 3: A=105 B=107 C=108 D=110 E=112 F=113 G=115
              # Subtracting 105 would yield A=0 B=2 C=3 D=5 E=7 F=8 G=10
              # but isn't necessary because we only need differences
  +?/\#/      # Add 1 for '#'
  -?/b/       # Subtract 1 for 'b'

{                           }o  # Compose with block
            (.skip Z-$_)        # Pairwise difference
                        X%12    # modulo 12
         [~]  # Join
 221222==     # Equals 221222


Rosetta Stone Challenge: Gene Mapping The goal of a Rosetta Stone Challenge is to write solutions in as many languages as possible. Show off your programming multilingualism!

The Challenge

Your challenge is to implement a program that will map some genes using cross-over frequencies, in as many programming languages as possible. You are allowed to use any sort of standard library function that your language has, since this is mostly a language showcase.

What is "gene mapping?"

Gene mapping is the process of locating the relative position of genes on chromosomes. This is done by measuring the crossing-over frequency of pairs of genes, equal to the percent of offspring in which that the pair is not inherited together.  Distance is measured in map units with one map unit equal to one percent of crossing over.  For example, if genes C & D have a crossing-over frequency of 11%, then gene C is a distance of 11 map units away from gene D.

Gene mapping is performed with multiple pairs of genes to determine their relative order.  For example, the data (A,B,12) (D,B,7) (A,D,5) (D,H,2) (H,B,9) produces the following map:

A..H.D......B

You may have noticed that B......D.H..A is also a valid map.  This is true, because it is not possible to distinguish between mirror opposites.  Your program can pick which one to output.  Although the input may not include every possible pair, there will always be enough information to reconstruct the entire map (so there will never be more than 2 valid outputs).  In addition, the numbers will always work out (unlike actual biology), meaning that you won't have stuff like (A,B,3) (B,C,4) (A,C,13).

Input

Input will begin with a number n followed by a list of genes (uppercase letters).  There will then be n triplets of data.  Each set will consist of a pair of genes and their crossing over frequency (distance).

3,P,H,I
P,H,3
H,I,1
P,I,4

7,A,B,G,Q,U
B,Q,4
A,B,10
G,U,13
Q,U,10
A,G,9
G,Q,3
A,Q,6

Input is not rigidly defined, because different languages may have restrictions on what is feasible.  For example, you may change the delimiters to something other than commas and newlines.  Input formatting is largely up to you.

Output

Output will be a rendition of the gene map.  It will consist of the genes (capital letters) spaced out by periods such that the distances are accurately portrayed.  Here are the outputs for the above examples.

P..HI  *or*  IH..P

BG..Q.....A...U  *or*  U...A.....Q..GB

This also isn't a completely rigid requirement. For example you could use something other than periods, like commas or spaces.

The Objective Winning Criterion

As for an objective winning criterion, here it is: Each language is a separate competition as to who can write the shortest entry, but the overall winner would be the person who wins the most of these sub-competitions. This means that a person who answers in many uncommon languages can gain an advantage. Code-golf is mostly a tiebreaker for when there is more than one solution in a language: the person with the shortest program gets credit for that language.

Rules, Restrictions, and Notes

Your program can be written in any language that existed prior to December 20th, 2013. I will also have to rely on the community to validate some responses written in some of the more uncommon/esoteric languages, since I am unlikely to be able to test them.

Current Leaderboard

This section will be periodically updated to show the number of languages and who is leading in each.

AutoHotkey (632) - Avi
dj (579) - rubik

Current User Rankings

Avi (1): AutoHotkey (632)
rubik (1): dj (579)


How to print the below format in the fewest bytes? This challenge is inspired by this, now deleted question.

Take a positive integer N as input, and output a matrix with the numbers 1 .. N2 that follows the pattern below:

Fill in the first row with 1 .. N then fill the last row (row number N) with (N+1) .. 2N, then fill the second row with (2N+1) .. 3N and continue until you have filled all rows.

The output format is flexible, so list of lists etc. are accepted.

N = 1
1

N = 2
1  2
3  4

N = 3
1  2  3
7  8  9
4  5  6

N = 4
 1  2  3  4
 9 10 11 12
13 14 15 16
 5  6  7  8

N = 5
 1  2  3  4  5
11 12 13 14 15
21 22 23 24 25
16 17 18 19 20
 6  7  8  9 10

Standard rules apply. Shortest answer in bytes in each language wins. Explanations are encouraged as always.

05AB1E, 13 8 bytes

Saved 5 bytes thanks to Rod

nLôÂ«āÉÏ

Try it online!

Explanation

n           # push input^2
 L          # push range [1 ... input^2]
  ô         # split into pieces each the size of the input
   Â«       # append the reverse of this 2D-list
     ā      # push range [1 ... len(list)]
      É     # check each element for oddness
       Ï    # keep only the elements in the 2D list which are true in this list


Reverse your code, reverse the OEIS The task here is to write a program that takes an natural number, \$n\$, and produces the \$n\$th term of an OEIS sequence.  That sequence should have an identifier in the form of A followed by 6 digits.  Now when you take your source code and reverse the order of it's bytes to produce a new program, that program should also implement an OEIS sequence.  The new sequence should be identified by an A followed by the same 6 digits as last time but in reverse order (including leading zeros).

Now to keep things from being trivial neither the OEIS identifier number nor your program can be palindromes.  That is the sequences and programs should be different. You cannot choose a sequence for which it's reverse does not exist or is empty.

For each of your sequences you may choose to either use 0 or 1 indexing.  They do not have to use the same indexing. Since some OEIS sequences have a limited domain you need only output the correct numbers for the domain of the sequence.  Your required behavior is undefined outside of the domain (you can output 0, crash, order a pizza, etc.).

This is code-golf so answers will be scored in bytes with fewer bytes being better.

05AB1E, 9 4 bytes (A000040 and A040000)

Ø=>≠

Try it online!

!enilno ti yrT

Explanation:

Ø          # nth prime
 =         # output
  >≠       # ignored

:noitanalpxE

≠          # boolean negation (0 if n == 1, 1 otherwise)
 >         # increment
  =        # output
   Ø       # ignored


Euclidean Distance Between Two Matrices Your task is to write the shortest algorithm in a language of your choosing that accomplishes the following:

Given two matrices it must return the euclidean distance matrix. The euclidean distance between two points in the same coordinate system can be described by the following equation:
\$D = \sqrt{ (x_2-x_1)^2 + (y_2-y_1)^2 + ... + (z_2-z_1)^2 }\$

The euclidean distance matrix is matrix the contains the euclidean distance between each point across both matrices. A little confusing if you're new to this idea, but it is described below with an example.

Below is an example:

a = [ 1.0  2.0  3.0;
     -4.0 -5.0 -6.0;
      7.0  8.0  9.0] #a 3x3 matrix

b = [1. 2. 3.] #a 1x3 matrix/vector

EuclideanDistance(a, b)
[   0.0;
  12.4499;
  10.3923]] # a 3x1 matrix/vector see rules for relaxed scoring

In a typical matrix representation of data, or coordinates, the columns represent variables. These could by \$\text{X,Y,Z...,J}\$ coordinates. Most people think in terms of \$\text{XYZ}\$ for 3-D space(3 columns), or \$\text{XY}\$ for 2D space(2 columns). Each row of the matrix represents a different point, or object. The points are what is being compared.

Using the example, matrix b is a single point at positions \$X= 1,Y = 2\$ and \$Z = 3\$. Matrix a contains three points in the same set of coordinates. The first point in a is the same as the point contained in b so the euclidean distance is zero(the first row of the result).

Not to be confusing, but, the matrices can be of any size(provided they fit into RAM). So a 7 by 11 matrix being compared with a 5 by 11 matrix is possible. Instead of X,Y,Z we would then have 11 coordinates(or columns) in both input matrices. The output would either be a 7x5 or a 5x7 matrix (depending on what way the points are compared). Make sense? Please ask for further clarifications.

Here's a 4 dimensional matrix example

a = [ [1. 2. 3. 4.];
      [ -4. -5. -6. -7. ];
      [ 6. 7. 8. 9. ] ] #a 3x4 matrix
b = [ [1. 2. 3. 4.];
      [1. 1. 1. 1.] ] #a 2x4 matrix

EuclideanDistance(a, b)
[  0.0    3.74166;
 16.6132 13.1909;
 10.0    13.1909] #a 3x2 matrix

And another example for soundness:

a = [ [1.  2.];
     [ 3.3 4.4 ] ] #a 2x2 matrix

b = [ [5.5 6.6];
      [7.  8. ];
      [9.9 10.1] ] #a 3x2 matrix

EuclideanDistance(a, b)
[6.43506 8.48528 12.0341;
 3.11127 5.16236 8.72067] #a 2x3 matrix

Rules:

If this function is included in your base language you can use it. You can import the direct function to do this as well. But you sacrifice style and honor! You will not be evaluated on style or honor but your street cred. will be - your call :P .
Your submission should be evaluated in bytes. So save off your code to plain text and read the file size. Less bytes is best!
No printing necessary, just a function, lambda, whatever, that computes this operation.
Reasonable round-off error is fine, and the transpose of the correct solutions is also fine.
This must work for matrices!

Happy golfing!

Jelly, 5 bytes

_þ²§½

Try it online!

A dyadic link that takes a matrix as each argument and returns a matrix.

Explanation

_þ    | Outer table using subtract
  ²   | Square (vectorises)
   §  | Sum (vectorises)
    ½ | Square root (vectorises)


Variable length Fibonacci word Challenge
For any two non-empty strings A and B, we define the following sequence :
F(0) = A
F(1) = B
F(n) = F(n-1) + F(n-2)

Where + denotates the standard string concatenation.
The sequence for strings "A" and "B" starts with the following terms: A, B, BA, BAB, BABBA, ...
Create a function or program that, when given two strings A and B, and a positive integer I returns the I-th character of F(∞).
You may choose to use 0-indexing or 1-indexing for I, just specify it in your answer.
You may assume the strings contain only uppercase (or lowercase) letters.
This is a variation of Project Euler's Problem 230, where the two strings were strings of digits of equal length, which trivialize the problem.
Input/Output
You may choose any format for the input. The output should only contain the desired character, with trailing spaces/newlines allowed.
Test Cases
ABC, DEF, 1234567890 → A
ACBB, DEFGH, 45865 → B
A, B, 3 → B
ABC, DEF, 10 → E

This is code-golf, so the lowest byte count for each language wins!

Haskell, 15 bytes

a#b=b++b#(a++b)

Try it online!
Takes strings a and b as input, returns the whole infinite Fibonacci word, as is usually allowed in sequence challenges.
How?
Not much to say. This answer relies on the identity
$$
F(a,b)=b+F(b,a+b),
$$
where \$F(a,b)\$ is the infinite Fibonacci word with starting words \$a\$ and \$b\$.


What is the frequency of this note? Quick musical refresher:
The piano keyboard consists of 88 notes. On each octave, there are 12 notes, C, C♯/D♭, D, D♯/E♭, E, F, F♯/G♭, G, G♯/A♭, A, A♯/B♭ and B. Each time you hit a 'C', the pattern repeats an octave higher.

A note is uniquely identified by 1) the letter, including any sharps or flats, and 2) the octave, which is a number from 0 to 8. The first three notes of the keyboard, are A0, A♯/B♭ and B0. After this comes the full chromatic scale on octave 1. C1, C♯1/D♭1, D1, D♯1/E♭1, E1, F1, F♯1/G♭1, G1, G♯1/A♭1, A1, A♯1/B♭1 and B1. After this comes a full chromatic scale on octaves 2, 3, 4, 5, 6, and 7. Then, the last note is a C8.
Each note corresponds to a frequency in the 20-4100 Hz range. With A0 starting at exactly 27.500 hertz, each corresponding note is the previous note times the twelfth root of two, or roughly 1.059463. A more general formula is:

where n is the number of the note, with A0 being 1. (More information here)
The Challenge
Write a program or function that takes in a string representing a note, and prints or returns the frequency of that note. We will use a pound sign # for the sharp symbol (or hashtag for you youngins) and a lowercase b for the flat symbol. All inputs will look like (uppercase letter) + (optional sharp or flat) + (number) with no whitespace. If the input is outside of the range of the keyboard (lower than A0, or higher than C8), or there are invalid, missing or extra characters, this is an invalid input, and you do not have to handle it. You can also safely assume you will not get any weird inputs such as E#, or Cb.
Precision
Since infinite precision isn't really possible, we'll say that anything within one cent of the true value is acceptable. Without going into excess detail, a cent is the 1200th root of two, or 1.0005777895. Let's use a concrete example to make it more clear. Let's say your input was A4. The exact value of this note is 440 Hz. Once cent flat is 440 / 1.0005777895 = 439.7459. Once cent sharp is 440 * 1.0005777895 = 440.2542 Therefore, any number greater than 439.7459 but smaller than 440.2542 is precise enough to count.
Test cases
A0  --> 27.500
C4  --> 261.626
F#3 --> 184.997
Bb6 --> 1864.66
A#6 --> 1864.66
A4  --> 440
D9  --> Too high, invalid input.
G0  --> Too low, invalid input.
Fb5 --> Invalid input.
E   --> Missing octave, invalid input
b2  --> Lowercase, invalid input
H#4 --> H is not a real note, invalid input.

Keep in mind that you don't have to handle the invalid inputs. If your program pretends they are real inputs and prints out a value, that is acceptable. If your program crashes, that it also acceptable. Anything can happen when you get one. For the full list of inputs and outputs, see this page
As usual, this is code-golf, so standard loopholes apply, and shortest answer in bytes wins.

Japt, 41 37 35 34 bytes

I finally have a chance to put ¾ to good use! :-)

55*2pU¬®-1¾ª"C#D EF G A B"bZ /C} x

Try it online!

How it works

          // Implicit: U = input string, C = 12
U¬®    }  // Take U, split into chars, and map each item Z by this function:
-1¾       //  Subtract 1.75 from Z. This produces NaN for non-digits.
ª"..."bZ  //  If the result is falsy (NaN), instead return the index of Z in this string.
          //  C produces 0, D -> 2, E -> 4, F -> 5, G -> 7, A -> 9, B -> 11.
          //  # -> 1, and b -> -1, so we don't need to calculate them separately.
/C        //  Divide the index by 12.
x         // Sum.
2p        // Take 2 to the power of the result.
55*       // Multiply by 55.

Test cases

All the valid test cases come through fine. It's the invalid ones where it gets weird...

input --> output       (program's reasoning)
A0  --> 27.5           (Yep, I can do that for you!)
C4  --> 261.625565...  (Yep, I can do that for you!)
F#3 --> 184.997211...  (Yep, I can do that for you!)
Bb6 --> 1864.6550...   (Yep, I can do that for you!)
A#6 --> 1864.6550...   (Yep, I can do that for you!)
A4  --> 440            (Yep, I can do that for you!)
D9  --> 9397.27257...  (Who says that's too high?)
G0  --> 24.49971...    (I've heard that note before.)
Fb5 --> 659.25511...   (Wait, Fb isn't supposed to be a note?)
E   --> 69.295657...   (I'm gonna guess that the missing octave is 1¾.)
b2  --> 61.735412...   (I assume that b means Cb...)
H#4 --> 261.625565...  (H# is C!)


Squarefinder – Locating regular tetragons Imagine a bunch of rectangles drawn in the plane, each rectangle with its vertices at integer coordinates and its sides parallel to the axes:

The rectangles partition the plane into a number of disjoint regions, coloured red and blue below:

Your goal is to find the number of such regions which are perfect squares. In the example above, there are three:

Note that the big square in the middle is not counted as it is not a single region, but is instead made up of several smaller disjoint regions.

Input

You may write a function or a full program for this challenge.

Input will be 4n nonnegative integers defining n rectangles in the plane. Each rectangle is represented by two opposing vertices, e.g. 4 9 7 8 represents the rectangle with opposing vertices (4, 9) and (7, 8). Note that this rectangle could also be represented as 7 8 4 9 or 4 8 7 9.

The exact input format is flexible (e.g. space-separated string, comma-separated string, single array of integers, list of coordinate tuples, and so on) but please be reasonable and give an example of how to run your code in your post. You may not reorder the input.

For simplicity, you can assume that no two edges will be overlapping — this includes overlapping at a vertex. In particular, this implies that no two rectangles will be touching edge-to-edge or corner-to-corner, and the rectangles will have nonzero area.

Output

Your program should print or return a single integer, which is the number of square regions.

Scoring

This is code golf, so the code in the fewest bytes wins.

Test cases

Input:

0 0 5 5
6 8 10 4
14 16 11 13
19 1 18 2

Output:

4

This is simply four disjoint squares:

Input:

2 1 3 11
1 10 5 19
6 10 11 3
8 8 15 15
13 13 9 5
15 1 19 7
17 19 19 17

Output:

3

This is the example test case at the start of the post.

Input:

0 9 15 12
6 3 18 15
9 6 12 20
13 4 17 8

Output:

7

Input:

5 9 11 10
5 12 11 13
6 8 7 14
9 8 10 14
13 8 14 9
13 10 14 14

Output:

14

Input:

0 99999 100000 0

Output:

0

This is just one big rectangle.

Input:

0 99999 100000 0
2 1 142857 285714

Output:

1

Two big rectangles which overlap.

Python 2, 480 436 386 352 bytes

exec u"""s=sorted;H=[];V=[]
FRIinput():
 S=2*map(s,zip(*R))
 FiI0,1,2,3:
    c=S[i][i/2];a,b=S[~i]
    FeIs(H):
     C,(A,B)=e
     if a<C<b&A<c<B:e[:]=C,(A,c);H+=[C,(c,B)],;V+=[c,(a,C)],;a=C
    V+=[c,(a,b)],;H,V=V,H
print sum(a==A==(d,D)&c==C==(b,B)&B-b==D-d&1-any(d<X[0]<D&b<y<B Fy,XIH)Fb,aIH FB,AIH Fd,cIV FD,CIV)""".translate({70:u"for ",73:u" in ",38:u" and "})

Takes a list of coordinate pairs through STDIN in the format:

[  [(x, y), (x, y)],  [(x, y), (x, y)],  ...  ]

and prints the result to STDOUT.

The actual program, after string replacement, is:

s=sorted;H=[];V=[]
for R in input():
 S=2*map(s,zip(*R))
 for i in 0,1,2,3:
    c=S[i][i/2];a,b=S[~i]
    for e in s(H):
     C,(A,B)=e
     if a<C<b and A<c<B:e[:]=C,(A,c);H+=[C,(c,B)],;V+=[c,(a,C)],;a=C
    V+=[c,(a,b)],;H,V=V,H
print sum(a==A==(d,D) and c==C==(b,B) and B-b==D-d and 1-any(d<X[0]<D and b<y<B for y,X in H)for b,a in H for B,A in H for d,c in V for D,C in V)

Explanation

Instead of fiddling with complex polygons, this program deals with simple line segments.
For each input rectangle, we add each of its four edges to a collective segment list, individually.
Adding a segment to the list goes as follows:
we test each of the existing segments for intersection with the new segment;
if we find an intersection, we divide both segments at the point of intersection and continue.
To make things easier, we actually keep two separate segment lists: a horizonal one and a vertical one.
Since segments don't overlap, horizontal segments can only intersect vertical segments and vice versa.
Better yet, it means that all intersections (not considering the edges of the same rectangle) are "proper," i.e., we don't have T-shaped intersections, so "both sides" of each segment are truly divided.

Once we've constructed the segment list(s), we start counting squares.
For each combination of four segments (particularly, two horizontal segments and two vertical ones,) we test if they form a square.
Furthermore, we verify that no vertex lies within this square (which can happen if, for example, we have a small square inside a bigger one.)
This gives us the desired quantity. Note that even though the program tests each combination four times in different orders, the particular ordering of the segment coordinates guarantees that we count each square only once.


What's the current zodiac? Display the emoji of the eastern zodiac of given time, according to given country.

The eastern zodiac is a classification scheme that assigns an animal and its reputed attributes to each year in a repeating 12-year cycle. It is also assigned to hours.

Rules:

The country must be given as ISO 3166-1 alpha-3 code. The list is here.
The input format must be like this: <ISO code> HH:MM. The input must be a single string. Any input that doesn't fit this format falls in don't care situation.
If the given time lies in boundary of the chart given below, you can output either zodiac.
As this is a code golf, the shortest code in bytes wins.

The zodiacs:

The zodiacs without specified country are defaults.

The first zodiac (23:00 – 01:00):

Rat  (U+1F400)
Mouse  (U+1F401) in Persia (IRN)

The second zodiac (01:00 – 03:00):

Ox  (U+1F402)
Water Buffalo  (U+1F403) in Vietnam (VNM)
Cow  (U+1F404) in Persia

The third zodiac (03:00 – 05:00):

Tiger  (U+1F405)
Leopard  (U+1F406) in Persia

The fourth zodiac (05:00 – 07:00):

Rabbit  (U+1F407)
Cat  (U+1F408) in Vietnam

The fifth zodiac (07:00 – 09:00):

Dragon  (U+1F409)
Crocodile  (U+1F40A) / Whale  (U+1F40B) in Persia (you can output either)
Snail  (U+1F40C) in Kazakhstan (KAZ)

The sixth zodiac (09:00 – 11:00):

Snake  (U+1F40D)

The seventh zodiac (11:00 – 13:00):

Horse  (U+1F40E)

The eighth zodiac (13:00 – 15:00):

Ram  (U+1F40F)
Goat  (U+1F410) in Vietnam
Sheep  (U+1F411) in Persia

The ninth zodiac (15:00 – 17:00):

Monkey  (U+1F412)

The tenth zodiac (17:00 – 19:00):

Rooster  (U+1F413)
Chicken  (U+1F414) in Persia

The eleventh zodiac (19:00 – 21:00):

Dog  (U+1F415)

The twelfth zodiac (21:00 – 23:00):

Pig  (U+1F416)
Boar  (U+1F417) in Japan (JPN)
Elephant  (U+1F418) in Thailand (THA)

The code points are from here.

Example:

Given the following input:

KOR 19:42

The output must be:


Find the smallest prime from a substring In 1946 Erdos and Copeland proved that a certain number is a normal number, i.e. the digits in its decimal expansion are uniformly distributed.

Users will input a sequence of digits and you will find the smallest prime that contains that string in base 10.

Example:

input   -> output
"10"    -> 101
"03"    -> 103
"222"   -> 2221
"98765" -> 987659

Shortest code in bytes wins. I do know that some languages (mathematica, sage, pari-gp...) come with built-in functions related to primes. -50 bytes if your program doesn't rely on such functions. Don't try to cheat on this please, if your language already has a huge advantage don't claim the bonus.

Edit

According to a few comments below, the smallest prime that contains "03" is 3. Does this really make a difference? The only thing I can think of is that maybe numbers are easier to handle than strings.

In cases like "03" the preferred output would be 103. However, I don't consider it to be the fundamental part of your program, so you're free to ignore any leading zero if it grants you a lower byte count.

Golfscipt, 33 32 bytes = -18 score
2{:x,2>{x\%!},!!x`3$?)!|}{)}/;;x

Explanation:

2{...}{)}/ - starting with 2, while something is true, increment the top of the stack

;;x - discard the intermediate values collected by {}{}/ and the input, then put the last value tested there

:x,2> - store the value as x, then produce a list from 2 to x-1

{x\%!},!! - keep those that x is divisible by, then coerce to boolean (not empty)

x`3?)! - look up the input in the text form of x (-1 if not found), increment, negate.

| - or


Perl 6, 29 bytes

{bag(.grep(?*)X-1)⊆.squish}

Try it online!

Very nice challenge for Perl 6. Uses the subset operator on Bags (integer-weighted sets). Explanation:

{
    bag(           # Create bag of
        .grep(?*)  # non-zero elements,
        X- 1       # decremented by one.
    )
    ⊆              # Subset test.
    .squish        # "squish" removes repeated elements in each run.
                   # The result is implicitly converted to a bag
                   # counting the number of runs.
}


Convert height to US Men’s Jacket size In the US, clothing size sometimes has rough designations like M, L, XXL, etc. The US designation of the "men's jacket" category depends on the height of the person. So, in this challenge, you should implement this conversion, which is defined by the following table, taken from this site:

US size Body height (cm)
XXXS    160 - 164
XXS     162 - 166
XS      166 - 170
S       168 - 173
M       171 - 176
L       174 - 182
XL      180 - 186
XXL     184 - 189
3XL     187 - 193
4XL     191 - 194
5XL     193 - 198
6XL     197 - 200

* I chose the "men's jacket" category from there because it has the most variability
Input
Body height, in cm. As a number or a string.
Output
Size designation - as a return value or printed.
Additional rules

For some sizes, designation is uncertain (e.g. 174, 175 and 176 correspond to both M and L) - your converter should return one of these, deterministically or not
If it's easier, output fully spelled versions like XXXXL instead of 4XL; however, 2XL and 2XS are invalid (apparently they are used in real life, but I decided to forbid them because I thought they weren't)
Assume the input is valid, i.e. a whole number between 160 and 200

Python 2, 58 55 52 49 47 45 bytes
-13 bytes with great contributions from Arnauld (thanks!!!), xnor and xash.
Switched from Python 3 to Python 2 for an extra 2 bytes.
Tried to profit from the overlapping regions. You don't even need a size M, because the sizes of S and L don't have a gap between them. Luckily, the number of X's for S and L can be expressed as a linear integer expression.

lambda h:max(173-h>>2,h/3-60)*'X'+'SL'[h>173]

Try it online!
Just for fun (and for educational purposes) the original 58 bytes submission:

lambda h:(-h+173)//4*'X'+'S'if h<174else(h-180)//3*'X'+'L'


Irish Snap: Variant Rules Introduction

Recently, me and a couple of my friends decided to play some cards, and one of them suggested the game 'Irish Snap', which was the inspiration for this challenge. However, I later learnt that the game has a lot of different rules that you can play with, some of which are listed  here. The rules that are in this challenge aren't currently listed on that page, hence the name, 'Variant Rules'

The Challenge

Given an array of 3 cards, output a truthy or falsey value depending on if they make a valid snap in a game of Irish snap.

Input

The input will be an array of 3 numbers, ranging from 1-13 inclusive, with 1 representing an ace, 11 representing a jack, 12 representing a queen and 13 representing a king. The input can be in any order of top, middle, bottom.

Rules

The 4 different criteria for if cards make an Irish snap are:

The top and middle cards are the same
The top and middle cards have a difference of one
The top and bottom cards are the same
The top and bottom cards have a difference of one

If any of these criteria are met, you must output a truthy value. As well as this, for the two criteria that require the cards to have a difference of one, it 'wraps around', meaning that an ace and a king are considered to have a difference of one, and vice versa.

Test Cases

Input (Bottom, Middle, Top) -> Output
1 13 7 -> False
1 4 13 -> True
9 3 6 -> False
8 9 7 -> True
2 6 5 -> True
12 5 11 -> True
10 4 8 -> False
12 13 7 -> False
9 7 10 -> True
7 3 1 -> False
4 2 3 -> True

Perl 6, 16 bytes

3>(*-(*|*)+1)%13

Try it online!

Anonymous whatever lambda that takes input as top, middle, bottom and returns a Junction that evaluates to True or False


Generate a mantis's head (symmetrical triangle) Given guaranteed strictly positive integers \$w\$ and \$n\$, output

An equilateral triangle array with side length \$w\$, filled with two distinct, consistent values. I'll call these 0 and 1 but they do not have to be equal to 0 and 1.
The number of 1s inside this array must be equal to \$n\$.
The output triangle must be symmetrical, meaning that it is the same when flipped horizontally or diagonally (your choice).
An equilateral triangle array can be an array with \$w\$ elements where for \$1\$ to \$w\$ (inclusive), there is a sub-array with that number of elements inside of \$w\$ (for example, but it may be outputted via ascii-art, see below).

(\$n\$ values are guaranteed to fit in the triangle)
Examples
w=3, n=1
  1
 0 0
0 0 0

w=3, n=2
  0
 1 1
0 0 0

w=3, n=3
  1
 1 1
0 0 0

w=3, n=4
  0
 1 1
1 0 1

w=3, n=5
  0
 1 1
1 1 1

w=3, n=6
  1
 1 1
1 1 1

Valid Output Format List
In this case the distinct values are 1 and 0.
Possible output triangles (all considered equivalent) with 1s at their corners and center and a width of 4 are:
   1
  0 0
 0 1 0
1 0 0 1

1
00
010
1001

[[1],[0,0],[0,1,0],[1,0,0,1]]

1 0 0 1
 0 1 0
  0 0
   1

[[1],[0,0],[0,1,0],[1,0,0,1]]

1
0
00
11
00
0
1

1
 0
0 0
 1 1
0 0
 0
1

here is a test case validator in Jq, takes {"w": w, "n": n, "a": result you wish to check} (in the JSON array format like [[1],[0,0],[0,1,0],[1,0,0,1]])

Jelly, 15 bytes
RØ.ṗŒpFS=ɗƇUƑƇḢ

Try it online!
-1 byte thanks to caird coinheringaahing
RØ.ṗŒpFS=ɗƇUƑƇḢ  Main Link; accepts w as the left argument and n as the right argument
R                Range; [1, 2, ..., w]
 Ø.ṗ             [0, 1] ~ cartesian power ~ ^
    Œp           Cartesian Product of ^'s items - this gets all valid triangles of the right size
      ---ɗƇ      Keep elements where
       S         the sum of
      F          the triangle flattened
        =        equals (right argument)
             Ƈ   Keep elements where
            Ƒ    the element is the same when
           U     each sub-list is reversed
              Ḣ  Get the first such triangle


Rational decomposition Write functions \$x(a)\$, \$y(a)\$ and \$z(a)\$ such that for any rational \$a\$ all functions return rational numbers and
$$x(a) \times y(a) \times z(a) \times (x(a) + y(a) + z(a)) = a$$
You may assume \$a \ge 0\$
You do not need to use rational types or operations in your program, as long as your program is mathematically sound. E.g. if you use a square root in your answer you must show that its argument is always a square of a rational number.
You may write three named functions x, y, z or write three programs instead if functions are cumbersome or non-existent for your language. Alternatively you may also write a single program/function that returns three numbers \$x\$, \$y\$, \$z\$. Finally, if you so prefer you may input/output the rational numbers as a numerator/denominator pair. Your score is the total size of the three functions or three programs in bytes. Smallest score wins.
Brute forcing is not allowed. For any \$a = \frac p q\$ where \$p, q \le 1000\$, your program should run in under 10 seconds.

An example (this does not mean your decomposition has to give these numbers):
x = 9408/43615
y = 12675/37576
z = 1342/390
x*y*z*(x+y+z) = 1

CJam (59 bytes)

{[WZ~C24X8TT]f*[4XGYC6 4Y].+_0=!>2%Z65135Zb+:(3/.f#:.*)W*+}

This is an anonymous block (function) which takes an integer or double on the stack and produces an array with three doubles. It has two cases internally to handle all non-negative inputs, since with only one case it would break on either 0.25 or 4. It still breaks for inputs -12 and -1.3333333333333333, but the spec allows that...

The online demo executes it and then adds up the values, prints all four, and multiplies them to show that it gets the original value (modulo rounding error).

Mathematical background

Following Noam Elkies we define the auxiliary \$w = - x - y - z\$. Then \$x + y + z + w = 0\$ and \$-xyzw = a\$ or \$xyzw + a = 0\$. This has lots of symmetry; any solution will have four formulae and we can pick the three golfiest ones.

Elkies gives four families of sets of solutions. Euler's:

$$\begin{eqnarray*}
x & = & \frac{6ast^3(at^4-2s^4)^2}{(4at^4+s^4)(2a^2t^8 + 10as^4t^4 - s^8)} \\
y & = & \frac{3s^5(4at^4+s^4)^2}{2t(at^4-2s^4)(2a^2t^8+10as^4t^4-s^8)} \\
z & = & \frac{2(2a^2t^8+10as^4t^4-s^8)}{3s^3t(4at^4+s^4)} \\
w & = & \frac{-(2a^2t^8+10as^4t^4-s^8)}{6s^3t(at^4-2s^4)}
\end{eqnarray*}$$

One related to Euler's:

$$\begin{eqnarray*}
x & = & \frac{(8s^8+a^2)(8s^8-88as^4-a^2)}{12s^3(s^4-a)(8s^8+20as^4-a^2)}\\
y & = & \frac{(8s^8+a^2)(8s^8-88as^4-a^2)}{12s^3(8s^4+a)(8s^8+20as^4-a^2)}\\
z & = & \frac{192as^5(s^4-a)^2(8s^4+a)^2}{(8s^8+a^2)(8s^8-88as^4-a^2)(8s^8+20as^4-a^2)}\\
w & = & \frac{-3s(8s^8+20as^4-a^2)^3}{4(s^4-a)(8s^4+a)(8s^8+a^2)(8s^8-88as^4-a^2)}\\
\end{eqnarray*}$$

A simpler one:

$$\begin{eqnarray*}
x & = & \frac{(s^4-4a)^2}{2s^3(s^4+12a)} \\
y & = & \frac{2a(3s^4+4a)^2}{s^3(s^4-4a)(s^4+12a)} \\
z & = & \frac{s^5+12as}{2(3s^4+4a)} \\
w & = & \frac{-2s^5(s^4+12a)}{(s^4-4a)(3s^4+4a)} \\
\end{eqnarray*}$$

And one related to that one:

$$\begin{eqnarray*}
x & = & \frac{s^5(s^4-3a)^3}{2(s^4+a)(s^{12}+12as^8-3a^2s^4+2a^3)} \\
y & = & \frac{s^{12}+12as^8-3a^2s^4+2a^3}{2s^3(s^4-3a)(3s^4-a)} \\
z & = & \frac{2a(s^4+a)^2(3s^4-a)^2}{s^3(s^4-3a)(s^{12}+12as^8-3a^2s^4+2a^3)} \\
w & = & \frac{-2s(s^{12}+12as^8-3a^2s^4+2a^3)}{(s^4-3a)(s^4+a)(3s^4-a)}
\end{eqnarray*}$$

Observe that every family has at least two denominators of the form \$ps^4 - qa\$ for positive \$p\$ and \$q\$: since all the terms involved are rational, that means that there's some positive \$a\$ for which we get division by zero. Therefore we must use at least two sets of solutions which have their singularities at different values of \$a\$. Intuitively it's going to be golfiest to choose two sets from the same family. I've chosen the simplest family (the third one) with parameters \$s=1\$ and \$s=2\$.


Who's Going? Can you help me? If Abe goes, then Beth and Diana go. If Beth goes, then Catherine goes. If Catherine goes, then Diana goes. If Diana goes, then Ezra goes. Only three people go. Who goes?

Challenge

Given a list of several pairings of people, such that in each pairing the second person goes if the first person goes, and a positive integer number of people who go, determine one or all possibilities of who goes. You may output either, as long as the output is consistent.

The example above may be represented in input by [(A,B),(A,D),(B,C),(C,D),(D,E)],3, which can be represented as a graph visually as:

A -> B -> C -> D -> E
⤷-------------⤴

If A goes, then everyone must go, so at least 5 people go, which cannot be 3 people.

If B goes, then C, D, and E must go, so at least 4 people go, which cannot be 3 people.

Thus we are left with C, D, and E going, yielding a final output of [C,D,E].

The input [(0,1),(0,3),(1,2),(2,3),(3,4)],3 represents the same situation and is the format given in the test cases (with output [2,3,4]).

We assume that no people other than the people in at least one pairing should be considered. For example, there is no person 5 or F in this example.

I/O

Your program/function must input g, the list of pairings which represents a directed graph, and n, the number of people who will go. Input g may be taken in any format (such as an adjacency matrix) which does not encode additional information and can encode at least 25 people to consider (the example considered 5 people).

You may also (optionally) input p, the list of people, and/or c, the number of people to consider. List of people p given g (sorted). (append L to end to get number of people c).

Your program/function does not have to handle if:

the integer input is greater than the number of people considered.
the integer input is not positive
repeat pairings
reflexive pairings (e.g. (A,A) or (0,0))
impossible situations (e.g. [(A,B),(B,A)],1)

The output should be in any format which can represent a list from 1 to 24 people.

Test Cases

If the output of a test case has an OR in it, your program may return any one or all of the choices.

[(0,1),(1,2),(2,3),(2,5),(5,6),(6,3),(6,7),(7,4)], 1 => [3] OR [4]
[(0,1),(1,2)], 1 => [2]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 1 => [7]
[(1,2),(2,3)], 2 => [2,3]
[(1,2),(3,4)], 2 => [1,2] OR [3,4] OR [2,4]
[(0,1),(1,2),(1,8),(2,3),(3,4),(4,11),(5,4),(5,6),(6,13),(13,20),(13,12),(12,19),(20,19),(4,19),(19,18),(11,10),(10,3),(10,2),(10,9),(9,8),(8,1),(8,7),(18,17),(18,24),(17,24),(24,23),(17,16),(16,23),(24,18),(16,15),(23,22),(22,15),(22,21),(21,14),(14,15)], 1 => [7] OR [15]
[(0,1),(1,0),(0,2),(1,3)], 1 => [2] OR [3]
[(0,1),(1,0),(0,2),(1,3)], 2 => [2,3]
[(0,1),(1,2)], 3 => [0,1,2]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 4 => [8,9,4,7]
[(0,1),(1,0),(0,2),(1,3)], 4 => [0,1,2,3]
[(0,1),(1,2),(2,3),(2,5),(5,6),(6,3),(6,7),(7,4)], 5 => [3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 5 => [4,5,7,8,9]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 6 => [2,3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 7 => [1,2,3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 7 => [3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 8 => [2,3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 9 => [1,2,3,4,5,6,7,8,9]
[(0,1),(1,2),(1,8),(2,3),(3,4),(4,11),(5,4),(5,6),(6,13),(13,20),(13,12),(12,19),(20,19),(4,19),(19,18),(11,10),(10,3),(10,2),(10,9),(9,8),(8,1),(8,7),(18,17),(18,24),(17,24),(24,23),(17,16),(16,23),(24,18),(16,15),(23,22),(22,15),(22,21),(21,14),(14,15)], 9 => [14,15,16,17,18,21,22,23,24]

Husk, 14 10 bytes

~f`öΠFf†€Ṗ

Takes three inputs: number of people to go, 2-row matrix of the constraints, and list of all people involved, in this order.
Returns all possible lists of people who go.
If you want to output only one list, replace the leftmost f by ḟ.
Try it online!

Explanation

The idea is to loop over the size-n subsets of p and keep those that satisfy the condition imposed by g: if the first person in a pair goes, then the second person must go too.

~f`öΠFf†€Ṗ  Implicit inputs, say n=3, g=[[1,3,3],[4,1,4]] and p=[1,2,3,4]
         Ṗ  All n-element subsets of p: [[1,2,3],[2,3,4],[1,3,4],[1,2,4]]
~f          Keep those subsets (say q=[1,2,4]) for which
  `ö        this function gives a truthy (nonzero) result:
       †     Deep map over g:
        €    index in q, or 0 if doesn't occur: [[1,0,0],[3,1,3]]
     Ff      Fold by select (filter second row by truthiness on first row): [3]
    Π        Product: 3

This program is one of those where it's really hard to explain how the program arguments are passed to the correct functions, but I'll try.
First, n is the first argument, so it can be given to Ṗ directly, making it a function that takes a list and returns its n-subsets.
The next two inputs are g and p, and the program's shape at this point is ~(f)(`öΠFf†€)(Ṗn) with parentheses added for clarity.
The operator ~ gives g to `öΠFf†€ and p to Ṗn, and combines the results with f.
Ṗnp is just the n-subsets of p, so that's simple.
The operator ` causes öΠFf†€ to take its arguments in the reverse order, so g is actually the second argument of this function.
The first argument is an element q of Ṗnp, which is extracted by f (filter).
We give q as an argument to €, which becomes a function for testing membership in q, and deep map that over the second argument, which is g.
Then ΠFf are applied to the result.
The role of ö is just to compose ΠFf†€ into one function, which we can then pass on to ` and ~f.


Short Date into English Long Date Convert short date format into English long date in as few bytes as possible.
Input
Input will be in the form of a string with format, yyyy-mm-dd, with zero padding optional for all values. You can assume that this is syntactically correct, but not necessarily a valid date. Negative year values do not need to be supported.
Output
You must convert the date into the English long date format (e.g. 14th February 2017). Zero padding here is not allowed.
If the date is invalid (e.g. 2011-02-29), then this must be recognised in some way. Throwing an exception is allowed.
More examples can be seen below.
Test Cases
"1980-05-12" -> 12th May 1980
"2005-12-3"  -> 3rd December 2005
"150-4-21"   -> 21st April 150
"2011-2-29"  -> (error/invalid)
"1999-10-35" -> (error/invalid)

Python 3.6, 137 129 bytes

from datetime import*
def f(k):g=[*map(int,k.split('-'))];n=g[2];return f"{date(*g):%-d{'tsnrhtdd'[n%5*(n^15>4>n%10)::4]} %B %Y}"

Try it online!


Escape from the tarpit (Cops) This is a cops-and-robbers challenge based around defining languages and proving they are Turing complete.
This is the cops' thread. The robbers' thread is here.
Cops
As a cop, you will prepare two things:

A formal specification of a programming language, or other computational system. (Computational systems are defined below.)

A proof that your system is Turing complete, according to the somewhat strict definition below.

You will post your specification of your language, and the robbers will try to "crack" it by proving its Turing completeness. If your submission is not cracked within one week you can mark it as safe and post your proof. (Your answer can be invalidated if someone finds a flaw in your proof, unless you can fix it.)
This is a popularity-contest, so the winner will be the answer that has the most votes, and which is not cracked or invalidated. The challenge is open-ended - I won't be accepting an answer.
For the sake of this challenge, a computational system will be defined as four things:

A "program set" P. This will be a countably infinite set, e.g. strings, integers, binary trees, configurations of pixels on a grid, etc. (But see the technical restriction below.)

An "input set" I, which will also be a countably infinite set, and need not be the same set as P (although it can be).

An "output set" O, which similarly will be a countably infinite set, and may or may not be the same as P or I

A deterministic, mechanistic procedure for producing an output o from program p and input i, where p, i and o are members of P, I and O respectively. This procedure should be such that it could, in principle, be implemented on a Turing machine or other abstract model of computation. The procedure may, of course, fail to halt, depending on the program and its input.

The sets P, I and O must be such that you can express them as strings in a computable manner. (For most sensible choices this will not matter; this rule exists to prevent you from choosing strange sets, such as the set of Turing machines that don't halt.)
Turing completeness will be defined as the following:

For any computable partial function f from I to O, there exists a program p in P such that given p and input i, the output is f(i) if f(i) has a value. (Otherwise the program doesn't halt.)

The word "computable" in the above definition means "can be computed using a Turing machine".
Note that neither rule 110 nor bitwise cyclic tag are Turing-complete by this definition, because they don't have the required input-output structure. Lambda calculus is Turing complete, as long as we define I and O to be the Church numerals. (It is not Turing-complete if we take I and O to be lambda expressions in general.)
Note that you don't have to provide an implementation of your language, but you are welcome to include one in your answer if you like. However, you shouldn't rely on the implementation to define the language in any way - the spec should be complete in itself, and if there is a contradiction between the spec and the implementation this should be treated as a bug in the implementation.

Blindfolded Arithmetic

Possibly a fairly easy language to start off with, relatively
speaking.  (There are limits on how difficult a language I can make
because I have to prove it Turing-complete myself!)

For this language, the program set is the set of Blindfolded
Arithmetic programs as given in the section "program" below, the input
set is the set of positive integers, and the output set is the set of
integers (the entire set, not just the positive integers).

This language is fairly interesting – maybe even practically useful –
because it has a more or less total lack of control flow, being
entirely based on computations on numbers you can't see.  That makes
it potentially useful as a language for implementing programs inside
homomorphic encryption
systems.

Specification

Blindfolded Arithmetic is an esoteric programming language with the
following specifications:

Data storage

A state of a running Blindfolded Arithmetic program consists of six
variables, each of which can store an integer.  (There are no limits
on how large or small these integers can get; in particular, they can
go negative.)  The variables are called a, b, c, d, e, and
i.

At the start of the program, a to e inclusive are each initialised
to 0, and i is initialised to a positive integer taken from user
input.  (If no input is available, i is initialised to 1.)

If the program ceases execution (this can only occur due to division
by zero), the value of i immediately before the division was
attempted is used as the program's output.

Program

A Blindfolded Arithmetic program is a list of commands, each of which
has one of the following forms (where v can be replaced by any
variable name, potentially a different name each time it's used):

v = v + v
v = v - v
v = v * v
v = v / v

Note that each operand of the commands must be a variable; this
language does not allow the use of literal integers.

Execution of the program is performed by running each of the commands
in sequence, and then looping back to the start and continuing to run
the commands in sequence again, ad infinitum (or until there's an
attempt to divide by zero, which ends the program).

Each command has the same semantics as you'd expect from the notation,
which is no different from that used by most practical programming
languages: the values of the second and third variables metioned in
the command are taken, an arithmetic operation
(add/subtract/multiply/divide respectively for the four forms of
command) is applied to them, and the resulting value stored into the
first variable.  Division here is integer division, rounding
towards 0.

There is no control flow of any kind, other than program exit; the
commands always cycle in sequence, up until a division by zero (if
any) occurs and ends the program.  In particular, there's no way to
directly read variables, only to use them as a source of calculations
whose results impact the values assigned to other variables.


Trim elements from the ends of a list The aim is to trim elements in from the ends of a list, depending on if they are in a second list of "falsey" results.
For example, if the first list is [-1, 1, 2, 0, -1, 3, -1, 4, -1, -1] and the second is [-1], then we would remove all leading and trailing -1s from the first input, but not any -1s in the middle: [1, 2, 0, -1, 3, -1, 4]
You may take input in any allowed method and this is code-golf so the shortest code in bytes wins.

Haskell, 37 36 bytes

f v|g<-reverse.snd.span(`elem`v)=g.g

Try it online!

-1 byte thanks to xnor.

How?
f v                     -- define a function f that takes as input a list v of falsey values
  |g<-                  --   inside the definition, define a new function g that...
    reverse             --     reverses...
    .snd                --     the second element of...
    .span               --     a tuple (say (x,y)) where x is the longest prefix of elements that...
      (`elem`v)         --       belong to v...
                        --     and y is the rest of the list
  =g.g                  --   f is defined as the composition g.g (basically apply g twice)


Output the missing integer You will be given a string. It will contain 9 unique integers from 0-9. You must return the missing integer. The string will look like this:

123456789
 > 0

134567890
 > 2

867953120
 > 4

Python 2, 18 16 bytes

+beauty thanks to @Sarge Borsch

`99066**2`.strip

Try it online!

99066**2 is just a shorter way to generate a string that contains 0~9


Sum of Numbers of Array Given an array (N) of integers, check if it is possible to obtain a sum of S, by choosing some (or none) elements of the array and adding them.

Example #1

{1,2,3}
4

should output

1 (or true)

because 1 and 3 can be added to produce 4.

Example #2

{3,6,2}
0

should output

1 (or true)

because adding none of them together produces 0.

Example #3

{0,4,3,8,1}
6

should output

0 (or false)

because no combination of the elements in the array can be added to produce 6.

Example #4

{3, 2 ,0 ,7 ,-1}
8

should output

1

because 2+7+(-1)=8

Mathematica

This is easy in Mathematica. (1) Generate the subsets of your input list, using the Subsets[] command (I had originally used Permutations[], which works but produces redundant results), (2) sum the numbers in each subset by mapping the Total[] command across the list of subsets, then (3) check to see if the target sum S is represented among those sums with MemberQ[]. To be concise, I've shown this below implemented as a single nested command.

Put your inputs in the first line and execute this:

list = {0, 4, 3, 8, 1}; target = 6;
MemberQ[Total /@ Subsets[list], target]

Assuming one-character variable names, that's 28 bytes of code.


Regex that only matches itself There are some pretty cool challenges out there involving regex (Self-matching regex, Regex validating regex)

This may well be impossible, but is there a regex that will ONLY match itself?

NOTE, delimiters must be included:

for example /thing/ must match /thing/ and not thing. The only match possible for your expression must be the expression itself. Many languages allow the implementation of a string in the place of a regular expression. For instance in Go

package main

import "fmt"
import "regexp"

func main() {

    var foo = regexp.MustCompile("bar")
    fmt.Println(foo.MatchString("foobar"))
}

but for the sake of the challenge, let the expression be delimited (starting symbol, expression, ending symbol ex: /fancypantpattern/ or @[^2048]@), if you want to argue quotes as your delimiter, so be it. I think given the apparent difficulty of this problem it won't make much of a difference.

To help you along:

Quick hack I put together for rubular.com (a webpage for ruby regex editing):

var test = document.getElementById("test")
,regex = document.getElementById("regex")
,delimiter="/"
,options = document.getElementById("options")
,delay = function(){test.value = delimiter + regex.value + delimiter + options.value}
,update = function(e){
    // without delay value = not updated value
    window.setTimeout(delay,0);
}
regex.onkeydown = update;
options.onkeydown = update;

Even though this is technically 'code golf' I will be very impressed if anyone can find an answer/ prove it is impossible.

Link is now fixed. Sorry to all

Winning answer thus far: jimmy23013 with 40 characters

PCRE flavor, 261 289 210 184 127 109 71 53 51 44 40 bytes

Yes, it is possible!

<^<()(?R){2}>\z|\1\Q^<()(?R){2}>\z|\1\Q>

Try it here. (But / is shown to be the delimiter on Regex101.)

Please refrain from making unnecessary edits (updates) on the Regex101 page. If your edit doesn't actually involve improving, trying or testing this regex, you could fork it or create new ones from their homepage.

The version works more correctly on Regex101 (44 bytes):

/^\/()(?R){2}\/\z|\1\Q^\/()(?R){2}\/\z|\1\Q/

Try it here.

This is much simpler than the original version and works more like a traditional quine. It tries to define a string without using it, and use it in a different place. So it can be placed very close to one end of the regex, to reduce the number of characters needing more characters to define the matching pattern and repeated more times.

Explanations:

\Q^\/()(?R){2}\/\z|\1\Q matches the string ^\/()(?R){2}\/\z|\1\Q. This uses a quirk that \Q...\E doesn't have to be closed, and unescaped delimiters work in \Q. This made some previous versions work only on Regex101 and not locally. But fortunately the latest version worked, and I golfed off some more bytes using this.
\1 before the \Q matches the captured group 1. Because group 1 doesn't exist in this option, it can only match in recursive calls. In recursive calls it matches empty strings.
(?R){2} calls the whole regex recursively twice, which matches ^\/()(?R){2}\/\z|\1\Q for each time.
() does nothing but capture an empty string into group 1, which enables the other option in recursive calls.
^\/()(?R){2}\/\z matches (?R){2} with delimiters added, from the beginning to the end. The \/ before the recursive calls also made sure this option itself doesn't match in recursive calls, because it won't be at the beginning of the string.

51 bytes with closed \Q...\E:

/\QE\1|^\/(\\)Q(?R){2}z\/\E\1|^\/(\\)Q(?R){2}z\/\z/

Try it here.

Original version, 188 bytes

Thanks to Martin Büttner for golfing off about 100 bytes!

/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.\2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{11}$/

Try it here.

Or 210 bytes without \Q...\E:

/^(?=.{194}\\2\\.\)\{2}\.\{12}\$\/D$)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{194}\2\\\2\\2\2\\\2\\\2\.\2\\\2\)\2\\\2\{2}\2\\\2\.\2\\\2\{12}\2\\\2\$\2\\\2\/D\2\$\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{12}$/D

Try it here.

Expanded version:

/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)        # Match things near the end.
((?=(.2.|))                               # Capture an empty string or \2\ into group 2.
   \2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.
   \2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)      # 1st line escaped.
   \2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\) # 2nd line escaped.
){2}
.{11}$/x

Extensions like (?= and \1 have made the so-called "regular" expressions no longer regular, which also makes quines possible. Backreference is not regular, but lookahead is.

Explanation:

I use \2\ in place of \ to escape special characters. If \2 matches the empty string, \2\x (where x is a special character) matches the x itself. If \2 matches \2\, \2\x matches the escaped one. \2 in the two matches of group 1 can be different in regex. In the first time \2 should match the empty string, and the second time \2\.
\Q\2\)){2}.{11}$\E\/\z (line 1) matches 15 characters from the end. And .{11}$ (line 7) matches 11 characters from the end (or before a trailing newline). So the pattern just before the second pattern must match the first 4 or 3 characters in the first pattern, so \2\.\2\|\2\)\2\) must match ...\2\) or ...\2\. There cannot be a trailing newline because the last character should be ). And the matched text doesn't contain another ) before the rightmost one, so all other characters must be in the \2. \2 is defined as (.2.|), so it can only be \2\.
The first line makes the whole expression matches exactly 188 characters since everything has a fixed length. The two times of group 1 matches 45*2 characters plus 29 times \2. And things after group 1 matches 11 characters. So the total length of the two times \2 must be exactly 3 characters. Knowing \2 for the second time is 3 characters long, it must be empty for the first time.
Everything except the lookahead and \2 are literals in group 1. With the two times \2 known, and the last few characters known from the first line, this regex matches exactly one string.
Martin Büttner comes up with the idea of using lookahead to capture group 2 and make it overlap with the quine part. This removed the characters not escaped in the normal way between the two times of group 1, and help avoided the pattern to match them in my original version, and simplified the regex a lot.

Regex without recursions or backreferences, 85 bytes

Someone may argue that expressions with recursions or backreferences are not real "regular" expressions. But expressions with only lookahead can still only match regular languages, although they may be much longer if expressed by traditional regular expressions.

/(?=.*(\QE\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\E\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\z/

Try it here.

610 bytes without \Q...\E (to be golfed):

/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}(.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\(.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

Try it here.

The idea is similar.

/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)
((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)
(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}
  (.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}
    (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\
    (.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}
  (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}
  (.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}
  (.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

The basic regular expression

If lookahead is not allowed, the best I can do now is:

/\\(\\\(\\\\){2}/

which matches

\\(\\\(\\

If {m,n} quantifier is not allowed, it is impossible because nothing which can only match one string, can match a string longer than itself. Of course one can still invent something like \q which only matches /\q/, and still say expressions with that regular. But apparently nothing like this is supported by major implementations.


Does it match the digit pattern? Recently I had a Maths test and noticed that a certain number on the test matched an interesting pattern. The number (28384) matched a generic digit sequence that looks like this

(n)(x)(n+1)(x)(n+2)(x)(n+3) etc...

where n and x are single digit integers. The sequence can begin with either x or n and end with either x or n+y.

Your task is, given a multi digit positive integer, output a truthy or falsey value, depending on whether the input matches the pattern. The input will be between 4 and 18 digits long. You may take input as a string representation of the integer. The input will not begin with a 0 but can contain or end with 0s.

n+y will always be a single digit number (hence why the length limit is 18).

Test Cases

These should output a truthy value

182838485868788898
4344
85868
12223242526

And these should be falsey

12345
6724013635
36842478324836
1222232425
5859510511

As with all code golfs, shortest code wins! Good luck and may the odds, be ever in your favour!

Python 2, 84 81 80 79 bytes

-1 byte thanks to ovs

lambda x:g(x,1)|g(x,0)
g=lambda x,a:len(set(x[a::2]))==(x[a<1::2]in"123456789")

Try it online!

Python 3, 82 79 78 77 bytes

lambda x:g(x,1)|g(x,0)
g=lambda x,a:len({*x[a::2]})==(x[a<1::2]in"123456789")

Try it online!

Slightly shorter in Python 3, but I didn't think it deserved its own answer.

Explanation

We set up a function g that takes string and an index (either 1 or 0).  g then returns whether or not len(set(x[a::2])), that is the number of unique digits in every other position, is equal to (x[a==0::2]in"123456789"), whether or not the other digits are in ascending order.  If the digits are in ascending order this returns whether or not they are all the same, if not it will ask if the set is empty, which it cannot be, thus always returning false.


Arrow those variables! Challenge

Robin likes having his variables declaration in the shape of an arrow. Here's how he does it:

Input any number of strings
Order them by ascending length
Output them ordered by the middle to roughly form a negative arrowhead, like this (whichever order golfs the best):

5  or  4
3      2
1      1
2      3
4      5

Test Cases

Input:

bow
arrows
sheriffOfNottingham
kingRichard
maidMarian
princeJohn
sherwoodForest

Output:

sheriffOfNottingham
kingRichard
maidMarian
bow
arrows
princeJohn
sherwoodForest

Input:

a
bb
cc

Output (both are valid):

bb
a
cc

cc
a
bb

Input:

one
four
seven
fifteen

Possible output (the only other valid output is its vertical mirror):

seven
one
four
fifteen

Notes

The strings are in camelCase and have no numbers or special characters, only lowercase and uppercase letters.
The input can be anything you like: comma-separated as one string, array, ... Any I/O format is allowed.
Between strings with the same length, any order is accepted.

Python 2, 47 bytes

lambda l:l.sort(key=len)or l[1::2][::-1]+l[::2]

Try it online!


Mimic the X11 Primary selection Background
In X11 (a windowing system used by a lot of Unix-like OS), what you would call the clipboard behave a bit differently than on other OSes like MacOS or Windows. While the "traditional" clipboard using ctrl+v/ctrl+c works, there is also another clipboard, called PRIMARY selection, that behave as following:

when you select a piece of text, this selection is added to the clipboard
when you use the middle mouse button, the content of that selection is pasted where your mouse is.

Some more details for those who are interested : X11: How does “the” clipboard work?
Challenge
The input in this challenge is any representation of a binary input. In the following I will use 'S' for select and 'P' for paste.
Given the input, you must output the input after making the following changes :

put the content of the current output in the primary selection when you receive a select instruction
paste the content of the primary selection in the middle of the current output when you receive a paste instruction. If the current output is odd numbered, the middle is the length divided by 2 and truncated.

Example
Input is SPSP :
selection = ""
output = "SPSP"
 SPSP
↑

selection = "SPSP"
output = "SPSP"
 SPSP
 ↑

selection = "SPSP"
output = "SPSPSPSP"
 SPSP
  ↑

selection = "SPSPSPSP"
output = "SPSPSPSP"
 SPSP
   ↑

selection = "SPSPSPSP"
output = "SPSPSPSPSPSPSPSP"
 SPSP
    ↑

Final Output is SPSPSPSPSPSPSPSP
Test Cases
"" -> ""
"S" -> "S"
"P" -> "P"
"PS" -> "PS"
"SP" -> "SSPP"
"SPP" -> "SSPSPPPPP"
"SPSP" -> "SPSPSPSPSPSPSPSP"
"SPPSP" -> "SPSPPSPSPSPPSPPSPSPPSPPSPSPPSP"
"SPPSPSSS" -> "SPPSSPPSSPPSSPPSSPPSSPPSPSSSPSSSPSSSPSSSPSSSPSSS"

Reference Implementation
In Python 3 :
def clipboard(inp, select="S", paste="P"):
    out = inp
    primary_selection = ""
    for instruction in inp:
        if instruction is select:
            primary_selection = out
        if instruction is paste:
            out = out[:len(out)//2] + primary_selection + out[len(out)//2:]
    return out

Try it online!
Rules

You may assume that the input contains only the "paste" or "select" characters (you don't need to handle error cases)
You may take your input newline separated (e.g S\n P\n S\n)
You may use any kind of data representation (e.g binary data,\n(newline) as a select character and  (space) as a paste character, etc.)
Standard code-golf rules , shortest submission by bytes wins!

Python 2, 64 59 bytes
Input is a list of integers, 0 for select and 1 for paste. Outputs by modifying the input list.

def c(o,p=[]):
 for y in o*1:p=[o*1,p][y];o[len(o)/2:0]=p*y

Try it online!
Commented:

def c(o, p=[]):
    # o is the current output, p the current clipbord value
    # Iterate over a copy of the input list
    for y in o*1:
        # If y==0 (select) assign a copy of o to p
        p=[o*1,p][y]
        # Replace the empty slice at index len(o)/2 with:
        #  - a copy of p if y==1 (paste)
        #  - an empty list otherwise
        o[len(o)/2:0]=p*y

Try it online!