Is this string valid FEN? The challenge

Write a program or function which takes a string input as a function parameter or from stdin and determines if it is a valid FEN string.

Input

You can assume the input will only ever include the following characters (case sensitive)
pkqrbnPKQRBN12345678/
The length of the input will always be a minimum of 1 character and a maximum of 100 characters

Output

Output should be a truthy/falsey value. These can be any values you wish as long as they are consistent (all truthy results have the same output, all falsey results have the same output). You should have exactly two distinct possible outputs.

What counts as valid

Lowercase letters represent black pieces, uppercase letters represent white pieces.
You should ensure it is possible in a game of chess for the pieces in the current position to exist.
Each player will always have exactly 1 king (k/K)
Each player may have no more than 8 pawns (p/P)
Each player will usually have no more than 1* queen (q/Q)
Each player will usually have no more than 2* rooks (r/R)
Each player will usually have no more than 2* knights (n/N)
Each player will usually have no more than 2* bishops (b/B)
* It is legal for a player to 'promote' a pawn to any of these four pieces.
The total of pawns, queens, rooks, knights and bishops for each player will never be more than 15

The total number of pieces plus empty squares (denoted by numbers) should always add up to exactly 8 for each rank. And there should always be exactly 8 ranks, separated by a forward slash.

Things you can ignore

You do not need to concern yourself with whether or not it is possible to play into the position denoted, or if the position is legal, only that the pieces can exist in the quantities given.
You can ignore further complexities of FEN strings such as player turn, castling rights and en passant.

This is code golf. Shortest program in bytes wins. Usual loopholes and rules apply.

Test Cases

Input rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR
Output True

Input 2br2k1/1p2n1q1/p2p2p1/P1bP1pNp/1BP2PnP/1Q1B2P1/8/3NR2K
Output True

Input r2r2k1/p3q2p/ppR3pr/rP4bp/3p4/5B1P/P4PP1/3Q1RK1
Output False
(black has 7 pawns and 4 rooks - impossible)

Input 6k1/pp3ppp/4p3/2P3b1/bPP3P1/3K4/P3Q1q1
Output False
(only 7 ranks)

Input 3r1rk1/1pp1bpp1/6p1/pP1npqPn/8/4N2P/P2PP3/1B2BP2/R2QK2R
Output False
(9 ranks)

Input 5n1k/1p3r1qp/p3p3/2p1N2Q/2P1R3/2P5/P2r1PP1/4R1K1
Output False
(2nd rank has 9 squares/pieces)

Input rnbqkbnr/pppppppp/8/35/8/8/PPPPPPPP/RNBQKBNR
Output True
Thanks to Feersum and Arnauld for clarifying this case (3+5=8)

What is FEN?

FEN is a standard notation for recording the position of the pieces on a chess board.

Image credit http://www.chessgames.com

JavaScript (ES6), 168 174 ... 155

This answer has been edited an embarrassing number of times. Hopefully, the current version is both reliable and decently golfed.

Returns a boolean.

s=>[...s].map(c=>++n%9?+c?n+=--c:a[i='pP/KkQqRrBbNn'.search(c),i&=i>4&a[i]>(i>6)||i]=-~a[i]:x+=c=='/',a=[x=n=0])&&!([p,P,s,k,K]=a,n-71|x-7|s|k*K-1|p>8|P>8)

Formatted and commented

s => [...s].map(c =>                  // for each character 'c' in the FEN string 's':
  ++n % 9 ?                           //   if we haven't reached the end of a rank:
    +c ?                              //     if the character is a digit:
      n += --c                        //       advance the board pointer by c - 1 squares
    :                                 //     else:
      a[                              //       update the piece counter array:
        i =                           //         i = piece identifier (0 to 12)
          'pP/KkQqRrBbNn'.search(c),  //             with special case: '/' --> 2
        i &=                          //         we count it as a promoted pawn instead if:
          i > 4 &                     //           it's a Q, R, B or N and we already have
          a[i] > (i > 6) ||           //           2 of them for R, B, N or just 1 for Q
          i                           //           else, we keep the identifier unchanged
      ] = -~a[i]                      //         '-~' allows to increment 'undefined'
  :                                   //   else:
    x += c == '/',                    //     check that the expected '/' is there
  a = [                               //   initialize the piece counter array 'a'
    x =                               //   initialize the '/' counter 'x',
    n = 0 ]                           //   initialize the board pointer 'n'
) &&                                  // end of map()
!(                                    // now it's time to perform all sanity checks:
  [p, P, s, K, k] = a,                //   copy the 5 first entries of 'a' to new variables
  n - 71 |                            //   have we reached exactly the end of the board?
  x - 7 |                             //   have we identified exactly 7 ends of rank?
  s |                                 //   have we encountered any unexpected '/' character?
  k * K - 1 |                         //   do we have exactly one king on each side?
  p > 8 |                             //   no more than 8 black pawns, including promotions?
  P > 8)                              //   no more than 8 white pawns, including promotions?

Test cases

let f =

s=>[...s].map(c=>++n%9?+c?n+=--c:a[i='pP/KkQqRrBbNn'.search(c),i&=i>4&a[i]>(i>6)||i]=-~a[i]:x+=c=='/',a=[x=n=0])&&!([p,P,s,k,K]=a,n-71|x-7|s|k*K-1|p>8|P>8)

console.log(f("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR")) // True
console.log(f("2br2k1/1p2n1q1/p2p2p1/P1bP1pNp/1BP2PnP/1Q1B2P1/8/3NR2K")) // True
console.log(f("r2r2k1/p3q2p/ppR3pr/rP4bp/3p4/5B1P/P4PP1/3Q1RK1")) // False (black has 7 pawns and 4 rooks - impossible)
console.log(f("6k1/pp3ppp/4p3/2P3b1/bPP3P1/3K4/P3Q1q1")) // False (only 7 ranks)
console.log(f("3r1rk1/1pp1bpp1/6p1/pP1npqPn/8/4N2P/P2PP3/1B2BP2/R2QK2R")) // False (9 ranks)
console.log(f("5n1k/1p3r1qp/p3p3/2p1N2Q/2P1R3/2P5/P2r1PP1/4R1K1")) // False (2nd rank has 9 squares/pieces)
console.log(f("rnbqkbnr/pppppppp/8/35/8/8/PPPPPPPP/RNBQKBNR")) // True
console.log(f("rnbqkbnr/pppppppp/8/9/7/8/PPPPPPPP/RNBQKBNR")) // False (additional test case suggested by Rick Hitchcock)
console.log(f("rnbqkbnr/pppp/ppp/8/8/8/8/PPPPPPPP/RNBQKBNR")) // False (additional test case)


List of possible birth years of living humans The Challenge

Output a list of years that starts with the current year and ends 120 years ago. The birth year of every living human would be included in this list.

Details

The list should be in descending order.

Every built-in function to manipulate arrays and/or lists is allowed.

Shortest code in bytes wins.

When run this year the output would be

2016, 2015, ..., 1897, 1896

When run next year the output would be

2017, 2016, ..., 1898, 1897

Etc.

Update

Some have asked about the format of the list. As most have guessed, it doesn't matter. Insert any separator between the numbers. Intuitively most inserted a comma or space or both, newline or output an array.
Quasi superhumans like Jeanne Calment are an exception to the rule stated in my question.

Pyke, 6 bytes
wC7m-

Try it here!
w     - 121
   m- - for i in range(^):
 C7   -  current_year-i

(After w, the codepoint for 153 is present but it isn't printable)


Implement an IEEE 754 64-bit binary floating point number through integer manipulation (I've tagged the question "C" for the time being, but if you're aware of another language that supports unions, you can also use that.)

Your task is to build the four standard mathematical operators + - * / for the following struct:

union intfloat{
    double f;
    uint8_t h[8];
    uint16_t i[4];
    uint32_t j[2];
    uint64_t k;
    intfloat(double g){f = g;}
    intfloat(){k = 0;}
}

such that the operations themselves only ever manipulate or access the integer part (so no comparing with the double anytime during the operation either), and the result is exactly the same (or functionally equivalent, in the case of non-numeric results such as NaN) as if the corresponding mathematical operation had been applied straight to the double instead.

You may choose which integer part to manipulate, perhaps even using different ones among different operators. (You can also choose to remove the "unsigned" from any of the fields in the union, although I'm not sure whether you'd want to do that.)

Your score is the sum of the length of code in characters for each of the four operators. Lowest score wins.

For those of us unfamiliar with the IEEE 754 specification, here is an article about it on Wikipedia.

Edits:

03-06 08:47 Added constructors to the intfloat struct. You are allowed to use them for testing, rather than manually setting the double / etc.

C++, ~1500 chars

Expands the floats into an 8000-binary-digit fixed-point representation, does the operations on that, then converts back.

// an "expanded" float.
// n is nan, i is infinity, z is zero, s is sign.
// nan overrides inf, inf overrides zero, zero overrides digits.
// sign is valid unless nan.
// We store the number in fixed-point, little-endian.  Binary point is
// at N/2.  So 1.0 is N/2 zeros, one, N/2-1 zeros.
#define N 8000
struct E {
  int n;
  int i;
  int z;
  long s;
  long d[N];
};
#define V if(r.n|r.i|r.z)return r
// Converts a regular floating-point number to an expanded one.
E R(F x){
  long i,e=x.k<<1>>53,m=x.k<<12>>12;
  E r={e==2047&&m!=0,e==2047,e+m==0,x.k>>63};
  if(e)m+=1L<<52;else e++;
  for(i=0;i<53;i++)r.d[2925+e+i]=m>>i&1;
  return r;
}
E A(E x,E y){
  int i,c,v;
  if(x.s>y.s)return A(y,x);
  E r={x.n|y.n|x.i&y.i&(x.s^y.s),x.i|y.i,x.z&y.z,x.i&x.s|y.i&y.s|~x.i&~y.i&x.s&y.s};V;
  if(x.s^y.s){
    c=0;
    r.z=1;
    for(i=0;i<N;i++){
      v=x.d[i]-y.d[i]-c;
      r.d[i]=v&1;c=v<0;
      r.z&=~v&1;
    }
    if(c){x.s=1;y.s=0;r=A(y,x);r.s=1;}
  }else{
    c=0;
    for(i=0;i<N;i++){
      v=x.d[i]+y.d[i]+c;
      r.d[i]=v&1;c=v>1;
    }
  }
  return r;
}
E M(E x, E y){
  int i;
  E r={x.n|y.n|x.i&y.z|x.z&y.i,x.i|y.i,x.z|y.z,x.s^y.s};V;
  E s={0,0,1};
  for(i=0;i<6000;i++)y.d[i]=y.d[i+2000];
  for(i=0;i<4000;i++){
    if(x.d[i+2000])s=A(s,y);
    y=A(y,y);
  }
  s.s^=x.s;
  return s;
}
// 1/d using Newton-Raphson:
// x <- x * (2 - d*x)
E I(E d){
  int i;
  E r={d.n,d.z,d.i,d.s};V;
  E t={};t.d[4001]=1;
  for(i=N-1;i>0;i--)if(d.d[i])break;
  E x={0,0,0,d.s};x.d[N-i]=1;
  d.s^=1;
  for(i=0;i<10;i++)x=M(x,A(t,M(d,x)));
  return x;
}
// Convert expanded number back to regular floating point.
F C(E x){
  long i,j,e,m=0;
  for(i=N-1;i>=0;i--)if(x.d[i])break;
  for(j=0;j<N;j++)if(x.d[j])break;
  if(i>0&x.d[i-53]&(j<i-53|x.d[i-52])){E y={0,0,0,x.s};y.d[i-53]=1;return C(A(x,y));}
  if(i<2978){e=0;for(j=0;j<52;j++)m+=x.d[j+2926]<<j;}
  else if(i<5024){e=i-2977;for(j=0;j<52;j++)m+=x.d[i+j-52]<<j;}
  else x.i=1;
  if(x.z)e=m=0;
  if(x.i){e=2047;m=0;}
  if(x.n)e=m=2047;
  F y;y.k=x.s<<63|e<<52|m;return y;
}
// expand, do op, unexpand
F A(F x,F y){return C(A(R(x),R(y)));}
F S(F x,F y){y.k^=1L<<63;return A(x,y);}
F M(F x,F y){return C(M(R(x),R(y)));}
F D(F x,F y){return C(M(R(x),I(R(y))));}

I'm too lazy to remove all the spaces and newlines to get an exact golfed count, but it is about 1500 characters.


Convert a string to its Rövarspråket equivalent Rövarspråket

Rövarspråket is a word game played by Swedish children, from the books about Kalle Blomkvist by Astrid Lindgren.

The basic rules are as follows (from Wikipedia):

Every consonant (spelling matters, not pronunciation) is doubled, and
an o is inserted in-between.
Vowels are left intact.

A few examples:

"hello" -> "hohelollolo"
"Min svävare är full med ål" -> "MoMinon sosvovävovarore äror fofulollol momedod ålol"

Swedish consonants are the same as the English ones, so the program should work with both Swedish and English entries.

The letter "y" is taken as a consonant in this case - as most of the time it is.

Your Task:

Write a program to convert a string of Swedish letters, inputted through a function or through stdin, into its Rövarspråket equivalent.  Shortest answer in bytes wins!

Retina, 14 + 5 = 19 bytes

Retina is a language that is essentially just .NET regex with as little overhead as possible. The code for this program consists of two files:

i`[b-z-[eiou]]

$0o$0

This reads the input on STDIN and prints the output to STDOUT.

If you call the files pattern.rgx and replacement.rpl, you can run the program simply like

echo "hello" | ./Retina pattern.rgx replacement.rpl

Explanation

This is pretty straightforward, but let me add some explanation anyway (mostly about how Retina works). If Retina is invoked with 2 files it is automatically assumed to operate in "Replace mode", where the first file is the regex and the second file is the pattern.

Retina can be configured (which includes RegexOptions and other options) by prepending the regex with ` and a configuration string. In this case I'm only giving it i which is the normal regex modifier for case insensitivity.

As for the regex itself, it uses .NET's character class subtraction to match any consonant in the ASCII range. The replacement then just writes the match back twice with an o in between.


Count the number of sides on a polygon Count the number of sides on a polygon
The polygon-side-counting robot has decided to travel the world without telling anyone before, but it is crucial that the process of polygon counting is not stopped for too long. So you have following task: Given a black and white image of a polygon, your program/functoin should return the number of sides.
The program will be fed to an old punch card computer, and as punchcards are very expensive nowadays, you better try to make your program as short as possible.
The edges are at least 10 pixels long, and the angles formed by two adjecent edges is at least 10° but no more than 170° (or again greater than 190°). The polygon is completely contained within the image, and the polygon as well as it's complement is connected (there are no isolated islands) so this input would not be valid:

Scoring
This is codegolf, that means the shortest submission in bytes wins, your submission has to find the correct number of edges for every test case. (And the submission should work for other cases as well, optimization for just those test cases is not allowed.)
If you want to submit a solution that does not find the correct number each time, you can submit that too, but it will be ranked behind all the submissions that perform better.
Please include the total number in your submission title. (The total error the sum of the absolute differences between the real number of sides and the each output).
Test cases
n=10

n=36

n = 7

n=5

This is not a test case, just out of curiosity: How many edges do you get for this input?

Python 2 + PIL, no error, 313 307 bytes

from Image import*
I=open(sys.argv[1])
w,h=I.size;D=I.getdata()
B={i%w+i/w*1j for i in range(w*h)if D[i]!=D[0]}
n=d=1;o=v=q=p=max(B,key=abs)
while p-w:
 p+=d*1j;e=2*({p}<B)+({p+d}<B)
 if e!=2:e%=2;d*=1j-e*2j;p-=d/1j**e
 if abs(p-q)>5:
    t=(q-v)*(p-q).conjugate();q=p;w=o
    if.98*abs(t)>t.real:n+=1;v=p
print n

Takes an image file name on the command line, and prints the result to STDOUT.

Gives the correct result for all tests, and n = 28 for the circle.

Explanation

The algorithm works by walking along the perimeter of the polygon, and counting the number of encountered vertices (detected as changes in direction).
We start at the pixel farthest away from the origin, o, which is guaranteed to be a vertex, and therefore, to be adjacent to an edge (i.e., a boundary between a foreground pixel and a background pixel).
We keep track of our position, p, the most recent vertex, v, and the most recent "checkpoint", q, all of which are initially equal to o.
We also keep track of the direction of the edge, d, relative to the current pixel; d initially points east, which is a safe direction, since we know there's an edge to the east of o, or else it wouldn't be farthest from the origin.
We move along the edge, in a direction perpendicular to d, such that d points to our left, i.e., in a clockwise direction.
Whenever we "fall off the edge", i.e., in any situation where p is outside the polygon, or where the pixel to our left (i.e., in the direction of d) is inside the polygon, we adjust p and d accordingly before resuming.

Every time the distance between p and the last checkpoint, q, gets bigger than 5, we try to determine whether we passed over a vertex between q and p:
We compare the angle between vq (i.e., the vector from v to q), which is the general direction of the side of the polygon we were walking along when we reached the last checkpoint, and qp, the displacement between the last checkpoint and the current position.
If the angle is greater than about 10°, we conclude that we're walking along a different side of the polygon, increase the vertex count, and set v, the current vertex, to p.
At each checkpoint, regardless of whether we detected a vertex or not, we update q, the last checkpoint, to p.
We continue in this fashion until we arrive back at o, the starting point, and return the number of vertices found (note that the vertex count is initially 1, since the starting point, o, is itself a vertex.)

The images below show the detected vertices.
Note that taking p, the current position at each checkpoint, as the position of the new vertex is not optimal, since the real vertex is probably somewhere between the last checkpoint, q, and p, along the perimeter.
As you can see, all the vertices other than the first one (generally, the bottom-right vertex) are a little off.
Fixing this would cost more bytes, but this seems to be working well enough as it is.
That being said, it's a little hard not to overfit with only four test cases.


Python: shortest way to interleave items from two lists I'm trying to get the shortest way (character possible) to obtain List 3.

List 1 and List 2 are already given to me as arguments and are the same length.

l1 = [1, 2, 3, 4, 5]
l2 = ['a', 'b', 'c', 'd', 'e']

And List 3 should look like (yes, it needs to be a list):

l3 = ['a', 1, 'b', 2, 'c', 3, 'd', 4, 'e', 5]

Zip and Sum

[*sum(zip(l2,l1),())]

Try it online!

Zips the two lists together then adds all the tuples to make one combined list. The zip only works if the lists are guaranteed to be the same size, otherwise it truncates the longer list.

Added the surrounding [*  ] to transform it into a list as FryAmTheEggman suggests.


Alphabet Between Encryption You must write a program that encrypts an input into a string of characters.

For every character i in the input up to the second to last character, take the i and i+1 characters and encode them by writing the letters of the alphabet, in order, that range in the same direction between those chosen characters.

For example: if the original string were bo then it would be encoded as cdefghijklmn, but if the string were boa then bo is encoded as cdefghijklmn and oa is encoded as nmlkjihgfedcb with the final encrypted string being cdefghijklmnnmlkjihgfedcb.

If the original string contain zero letters between two chosen characters, such as the string ab then you should encrypt it as aRb with R standing for what direction in the alphabet to go in determining the original characters. The encrypted string aRb represents ab but the encrypted string aLb represents ba (R = right, L = left).

If two chosen characters in the original string are the same, such as the string tt, then you should encrypt it as tZt with Z standing for zero letters in between.

Examples:

Input: att Output: bcdefghijklmnopqrstZt

Input: brep Output: cdefghijklmnopqqponmlkjihgffghijklmno

Input: Optimizer Output: oRpqrssrqponmlkjjkllkjjklmnopqrstuvwxyyxwvutsrqponmlkjihgffghijklmnopq

Rules:

You can write a program or a function.
Your input may contain uppercase letters, so you need to put them all to lowercase before encrypting.
You can ignore non-alphabet characters.
One character length strings are undefined.
Shortest code in bytes wins!

Pyth, 38 bytes

M|strFGjHGsm?>Fd_g_d\Lgd?qFd\Z\R.:rzZ2

Demonstration.

M|strFGjHGsm?>Fd_g_d\Lgd?qFd\Z\R.:rzZ2
                                          Implicit: z = input(), Z = 0
                                          g is a function of a 2 letter string
                                          and an insert letter.
M                                         def g(G, H): return
    rFG                                   Take the string range between the
                                          letters in G.
   t                                      Remove the first letter to get just
                                          the letters in between.
  s                                       Concatenate.
 |                                        Logical or (if nothing in between)
       jHG                                H.join(G)
                                  rzZ     Convert input to lowercase.
                                .:   2    Take 2 letter substrings.
           m                              Map d over the substrings
            ?>Fd                          If the first character of `d`
                                          is greater than the second,
                 _g_\L                    g(d[::-1], 'L')[::-1]
                      gd                  else, g(d,
                        ?qFd              if the letters of d are the same,
                            \Z            'Z'
                              \R          else 'R')
          s                               Concatenate and print.


Print number triangle Given a number N, output a NxN right angled triangle, where each row i is filled with numbers up to i.

Example

n = 0

(no output)

n = 4

1
1 2
1 2 3
1 2 3 4

n = 10

1
1 2
1 2 3
.
.
.
1 2 3 4 5 6 7 8 9 10

(no alignment needed)

n = N

1
1 2
1 2 3
.
.
.
1 2 3 4 .... N

There is no trailing space at the end of each line.

Least number of bytes wins, and standard loopholes are not allowed.

Joe, 5 3 bytes (+2 or +3 for -t flag)

Well, apparently I didn't utilize the full potential of Joe. This was possible back when I first posted this.

\AR

Here, R gives the range from 0 to n, exclusive. Then \A takes successive prefixes of it (A is the identity function). Examples:

With -t flag (note: this is now the standard output even without the flag):

   (\AR)5
0
0 1
0 1 2
0 1 2 3
0 1 2 3 4
   \AR5
0
0 1
0 1 2
0 1 2 3
0 1 2 3 4
   \AR2
0
0 1
   \AR1
0
   \AR0

Without it:

   \AR5
[[0], [0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 2, 3, 4]]
   (\AR)5
[[0], [0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 2, 3, 4]]
   \AR2
[[0], [0, 1]]
   \AR1
[[0]]
   \AR0
[]

The rules got changed a bit. My old code didn't behave correctly with N =0. Also, now output could be just a nested list, so -t can be dropped.

1R1+R

Now, Rn gives a range from 0 to n, exclusive. If given 0, it returns an empty list.  1+ adds 1 to every element of that range. 1R maps the values to ranges from 1 to x. Empty liats, when mapped, return empty lists.

Example output:

   1R1+R0
[]
   1R1+R5
[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5]]

Update: I just noticed something. The function automatically maps to rank 0 elements. The following example is run with -t flag.

   1R1+R3 5 8
1
1 2
1 2 3

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8

Old: 5 bytes (with the -t flag)

1R1R

This is an anonymous function which takes in a number, creates a list from 1 to N (1Rn) and maps those values to the preceding range, giving a range from 1 to x for each item of range 1 to N.

The -t flag gives output as a J-like table.

   1R1R5
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5

Note : the language is very new and not complete, but the latest version was released before this challenge.


Ways to get to the number Given the input of the first number and the second number (both positive integers, zero exluded), determine in how many ways could you make the second out of the first, using following actions: +1,+2 and *3. Operations are simply applied from left to right.

Examples:

Input: 1 2. Output: 1. I.e, you could only get 2 by doing +1, so one way.
Input: 1 3. Output: 3. I.e, you could get 3 by either doing +2 or +1+1, or *3
Input: 1 4. Output: 4.
Input: 2 6. Output: 6.
Input: 2 7. Output: 9.
Input: 1 10. Output: 84.

In case there're no ways, e.g. 100 100, or 100 80, output is 0.

You could also take input as an array, or string with any convenient separator.

The shortest solution wins.


Draw an ASCII oak tree (or a woman with curly hair?) Task

Your task is to draw these beautiful oak trees:

1 ->
 @@@
@@@@@
@|.|@
_|_|_

2 ->
   @@
 @@@@@@
@@@@@@@@
@@| .|@@
  |  |
__|__|__

3 ->
   @@@@@
 @@@@@@@@@
@@@@@@@@@@@
@@@|   |@@@
  @|  .|@
   |   |
___|___|___

4 ->
      @@
   @@@@@@@@
 @@@@@@@@@@@@
@@@@@@@@@@@@@@
@@@@|    |@@@@
  @@|   .|@@
    |    |
    |    |
____|____|____

5 ->
      @@@@@
   @@@@@@@@@@@
 @@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@
@@@@@|     |@@@@@
  @@@|    .|@@@
     |     |
     |     |
     |     |
_____|_____|_____

6 ->
      @@@@@@@@
   @@@@@@@@@@@@@@
 @@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@
@@@@@@|      |@@@@@@
  @@@@|      |@@@@
     @|     .|@
      |      |
      |      |
      |      |
______|______|______

(that one sandbox commenter felt were similar to women with curly hair!)

The trees are allowed to be surrounded by any extra whitespace your solution creates as long as that doesn't break the tree, of course.

Algorithm

As per the examples above, we take n to represent the width of the trunk and the specs of the tree will be given in terms of that.

Given n:

the height of the trunk is n + 1;
the width of the trunk in space characters is n;
the top row of the trunk is n times the character @, followed by |, n times the space character , another vertical pipe | and then n times @.
from the reference row up to the top of the crown, we only use @ as follows:

there is one row with the same width as the reference row and each subsequent row above is shortened by one @ than the previous shortening;

from the reference row downwards, we chop 2 @ from each side and then each row we go down, we chop one more @ than the previous row;
the last trunk row that is surrounded by a @ has a . immediately to the left of the right vertical pipe |;
the bottom most row has the underscore _ in all the tree width, except where the trunk vertical pipes | are.

JavaScript (ES8),  215 ... 199  197 bytes
f=(n,k=(W=3*n+2)**.5-.5|0,x=.5-k-(W-n)**.5,R=(n,k)=>S=''.padEnd(n,'.@_'[k]))=>k+n+2?(w=k*-~k/2,k<0?(x>0?s=R(n,k+n+3):R(w+=~k,s=R(n-1)+R(1,~~x))+R(n-w,1))+`|${s}|`+S:R(w)+R(W-w*2,1))+`
`+f(n,k-1):''

Try it online!
or Test it online! against an ungolfed, straightforward implementation
How?
We define \$H\$ as the height of the upper part of the crown (where the width is increasing) and \$h\$ as the height of the lower part (where the width is decreasing).
Example for \$n=6\$:

We have:
$$H_n=\left\lfloor\sqrt{3n+2}+\frac{1}{2}\right\rfloor$$
and:
$$h_n=\left\lfloor\sqrt{2n+2}-\frac{1}{2}\right\rfloor$$
By computing these values beforehand, we can draw the tree from top to bottom with a single loop, which is implemented here as a recursive function.
The total height of the tree is \$H_n+n+1\$. We use a counter \$k\$ going from \$H_n-1\$ to \$-n-1\$.
 3 | ......@@@@@@@@       | upper crown
 2 | ...@@@@@@@@@@@@@@    |
 1 | .@@@@@@@@@@@@@@@@@@  |
 0 | @@@@@@@@@@@@@@@@@@@@ |
---+----------------------+-------------
-1 | @@@@@@|      |@@@@@@ | lower crown
-2 | ..@@@@|      |@@@@   |
-3 | .....@|     .|@      |
---+----------------------+-------------
-4 |       |      |       | trunk only
-5 |       |      |       |
-6 |       |      |       |
---+----------------------+-------------
-7 | ______|______|______ | roots

The number of leading spaces for the upper part of the crown is the \$k\$-th triangular number:
$$T_k=\frac{k\times(k+1)}{2}$$
The number of leading spaces for the lower part of the crown is given by:
$$\frac{(k+1)\times(k-2)}{2}=T_k-k-1$$
Commented
f = (                         // f is a recursive function taking:
  n,                          //   n = input
  k = (W = 3 * n + 2)         //   W = 3n + 2 = total width of the tree
      ** .5 - .5 | 0,         //   k = counter, initialized to floor(sqrt(W) - 1/2)
  x = .5 - k - (W - n) ** .5, //   x = 1/2 - k - sqrt(W - n)
  R = (n, k) =>               //   R is a helper function returning and saving in S:
    S =                       //     a character identified with k ('.', '@', '_' or
      ''.padEnd(n, '.@_'[k])  //     a space) repeated n times
) =>                          //
  k + n + 2 ?                 // if k is not equal to -n - 2:
    ( w = k * -~k / 2,        //   initialize w to the k-th triangular number
      k < 0 ?                 //   if k is negative:
        ( x > 0 ?             //     if x is positive (trunk only or roots):
            s =               //       set s to:
              R(n, k + n + 3) //         '_' * n if k = -n - 1, or space * n otherwise
          :                   //     else (lower crown):
            R(                //       append ...
              w += ~k,        //         ... w - k - 1 spaces
              s = R(n - 1) +  //         and set s to n - 1 spaces followed by
                  R(1, ~~x)   //         '.' if floor(x) = 0, or another space otherwise
            ) +               //
            R(n - w, 1)       //       append '@' * (n - w)
        ) +                   //
        `|${s}|` +            //     append s surrounded by '|' characters
        S                     //     append S
      :                       //   else (upper crown):
        R(w) +                //     append w spaces
        R(W - w * 2, 1)       //     append '@' * (W - 2w)
    ) +                       //
    `\n` +                    //   append a line-feed
    f(n, k - 1)               //   append the result of a recursive call with k - 1
  :                           // else:
    ''                        //   stop recursion


Trucks in a parking lot There are P parking spaces in a parking lot, though some spaces are occupied by cars represented by octothorpes # while the free spaces are dots .. Soon there arrive T trucks, each of which will take up exactly L consecutive spaces. The trucks don't have to be parked next to each other.

Your task is to create a program that will find the smallest number of cars that need to be removed in order to park all of the trucks. There will always be enough spaces to fit all of the trucks, meaning T*L<P

Input

In the first row there will be three integers, P, T and L separated by spaces. In the second row there will be a string of P characters representing the parking lot in its initial state.

Output

In the first and only line your program should print out the smallest number of cars that need to be removed in order to park all of the trucks.

Test cases

Input:
6 1 3
#.#.##

Output: 1

Input:
9 2 3
.##..#..#

Output: 2

Input:
15 2 5
.#.....#.#####.

Output: 3

Shortest code wins. (Note: I'm particularly interested in a pyth implementation, if one is possible)

Python 2, 154 bytes
I,R=raw_input,range
P,T,L=map(int,I().split())
S=I()
D=R(P+1)
for r in R(P):D[1:r+2]=[min([D[c],D[c-1]+(S[r]<".")][c%L>0:])for c in R(1,r+2)]
print D[T*L]

A straightforward DP approach. A fair chunk of the program is just reading input.
Explanation
We calculate a 2D dynamic programming table where each row corresponds to the first n parking spots, and each column corresponds to the number of trucks (or parts of a truck) placed so far. In particular, column k means that we've placed k//L full trucks so far, and we're k%L along the way for a new truck. Each cell is then the minimal number of cars to clear to reach the state (n,k), and our target state is (P, L*T).
The idea behind the DP recurrence is the following:

If we're k%L > 0 spaces along for a new truck, then our only option is to have come from being k%L-1 spaces along for a new truck
Otherwise if k%L == 0 then we have either just finished a new truck, or we'd already finished the last truck and have since skipped a few parking spots. We take the minimum of the two options.

If k > n, i.e. we've placed more truck squares than there are parking spots, then we put ∞ for state (n,k). But for the purposes of golfing, we put k since this is the worst case of removing every car, and also serves as an upper bound.
This was quite a mouthful, so let's have an example, say:
5 1 3
..##.

The last two rows of the table are
[0, 1, 2, 1, 2, ∞]
[0, 0, 1, 1, 1, 2]

The entry at index 2 of the second last row is 2, because to reach a state of 2//3 = 0 full trucks placed and being 2%3 = 2 spaces along for a new truck, this is the only option:
  TT
..XX

But the entry at index 3 of the second last row is 1, because to reach a state of 3//3 = 1 full trucks placed and being 3%3 = 0 spaces along for a new truck, the optimal is
TTT
..X#

The entry at index 3 of the last row looks at the above two cells as options — do we take the case where we are 2 spaces along for a new truck and finish it off, or do we take the case where we have a full truck already finished?
  TTT            TTT
..XX.     vs     ..X#.

Clearly the latter is better, so we put down a 1.
Pyth, 70 bytes
JmvdczdKw=GUhhJVhJ=HGFTUhN XHhThS>,@GhT+@GTq@KN\#>%hT@J2Z)=GH)@G*@J1eJ

Basically a port of the above code. Not very well golfed yet. Try it online
Expanded
Jmvdczd              J = map(eval, input().split(" "))
Kw                   K = input()
=GUhhJ               G = range(J[0]+1)
VhJ                  for N in range(J[0]):
=HG                    H = G[:]
FTUhN                  for T in range(N+1):
 XHhT                    H[T+1] =
hS                                sorted(                                        )[0]
>                                                                 [            :]
,                                        (      ,                )
@GhT                                      G[T+1]
+@GTq@KN\#                                       G[T]+(K[N]=="#")
>%hT@J2Z                                                           (T+1)%J[2]>0
)=GH                   G = H[:]
)@G*@J1eJ            print(G[J[1]*J[-1]])

Now, if only Pyth had multiple assignment to >2 variables...


Recreate a simplified version of the card game L.L.A.M.A In LLAMA, you want to dump cards from your hand as quickly as you can, but you might not be able to play what you want.

Each player starts a round with six cards in hand; the deck consists of llama cards and cards numbered 1-6, with eight copies of each. On a turn, the active player can play a card or draw a card. To play a card, you must play the same number as the top card of the discard pile or one number higher (for simplicity, we will follow the rule that if you can play a card of the same number, you will play that card, if not, play the higher card). If a 6 is on the discard pile, you can play a 6 or a llama, and if a llama is on top, you can play another llama or a 1. If you cannot play any cards, you must draw a card.

The round ends when one player empties their hand, who is pronounced as the winner of that round.

Some specifications:
1. The llama cards may have any name, but must be stored as a string (e.g. simply using the value 7 as the llama card is not permitted)
2. If a player draws a card, they may not play the drawn card in the same round again, i.e. their turn ends after drawing a card.
3. We will play the game with four players.

The output should list the turns taken by each player in the following fashion:

1 - 1
2 - 1
3 - 1
4 - 2
1 - 3
2 - draw
3 - 3
4 - 4
.
.
.
1 - 6
2 - llama
game over, 2 wins.

As always in code-golf, the program with the lowest number of bytes wins.

Edits:

In response to the comments, here are a few additional specifications.

The output may have any format as long as it contains the player number and their action.
The llama card should be a string composed only of letters, no numbers allowed.
At the start of a game, there is a single card on the discard pile, i.e. player 1 cannot play any card.
If the draw deck is empty, the played cards should be reshuffled. As the official rules of the game do not specify what should happen if all cards are drawn and there are no cards in the discard pile, this case does not need to be accounted for.
There is no input, i.e. the shuffled deck and dealing the hand cards must all be done in the program.

Python 3.8 (pre-release), 401 \$\cdots\$ 347 345 bytes

from random import*
d=[*range(7)]*8
shuffle(d)
p=[[d.pop()for i in[1]*6]for j in[1]*4]
o=[*range(1,7)]+['l']
h=[]
s=d.pop()
def g(a):p[n].remove(a);h.append(s);print(f"{n+1}-{o[a]}")
n=3
while all(p):
 n=-~n%4
 if s in p[n]:g(s)
 elif(t:=-~s%7)in p[n]:g(t);s=t
 else:
  if not d:d=h;h=[];shuffle(d)
  p[n]+=[d.pop()];print(f"{n+1}-d")
print(n+1)

Try it online!

Prints player-card for each move.
player is 1 to 4.
card is 1 to 6 or l for llama or d for draw.
Simply prints winner's number at the end.


Should we be friends? Note this is a question primarily focusing on data-structures
Introduction
Bacefook wants people to be friendlier! As such, they are implementing a new system to suggest friends! Your task is to help Bacefook to implement their new suggesting system.
Specifications:
Your program must be a REPL (read-eval-print loop) supporting 3 types of command: FRIEND, SUGGEST and KNOW.
FRIEND X Y - Specifies that X and Y are friends in the social network.

If X is friends with Y, then Y is friends with X

Can, but doesn't have to have output

X is always friends with X

KNOW X Y - Output a truthy value if X and Y are friends, falsy otherwise

KNOW X X will always output a truthy value

SUGGEST X Y - Output a truthy value if X and Y should be friends, falsy otherwise. X and Y should be friends if:

X and Y are not friends

X and Y have at least 1 friend in common

You are allowed to replace FRIEND, SUGGEST and KNOW with your own strings, but you must mention what string you have replaced each command with.
Your program can take in input/produce output in any way desirable, as long as it is reasonably easy to recognize how it works.
The number of people in the social network N is between 1 and 100,000, but there may be any number of "friend links" (edges).

 If you haven't noticed yet, this is a graph searching problem. The (likely) easiest (and possibly fastest) data structure to implement this in would be an adjacency matrix.

Test cases
FRIEND A B
FRIEND A C
FRIEND B D
SUGGEST A B -> Falsy, as they are friends
SUGGEST A D -> Truthy, as they share B as a common friend
SUGGEST C D -> Falsy, they do not share a common friend
KNOW D B -> Truthy, they are friends
KNOW B C -> Falsy, not friends
=============
FRIEND Tom Tim
KNOW Tom Tim -> Truthy
KNOW Tim Tom -> Truthy
KNOW Tom Kit -> Falsy
=============
KNOW Tim Kit -> Falsy
FRIEND Tim Tom
KNOW Tim Kit -> Falsy
FRIEND Tom Kit
SUGGEST Tim Kit -> Truthy
=============
FRIEND X Y
SUGGEST X Y -> Falsy since X is friends with X

Here's some more test cases in image form
Win condition
This is code-golf, shortest code wins!

SWI-Prolog, 62 47 41 bytes

X*Y:-X+Y;Y+X;X==Y.
X?Y:-not(X*Y),X*Z,Y*Z.

Prolog isn't too often useful, but when it is it's just beautiful. We'll use a+b to notate that a is friends with b, a*b that a knows b and a?b that b should be suggested to a or not. The first line simply says that X*Y is true if either X+Y, Y+X or X == Y is true. This implements the symmetry of knowing eachother. Asking if there should be a suggestion is incredibly simple. We just ask if there is a Z such that X*Y is false and X*Z and Y*Z is true. Exactly as described in the challenge.

If you save this as a file (e.g. friends.pl) and open SWI-Prolog with this file (prolog -l friends.pl) you get dropped into a REPL.

You can assert friendships like this:

assert('a' + 'b').
assert('a' + 'c').
assert('b' + 'd').

You can check if people know eachother or suggestion should be made:

'a'*'b'.
'a'?'d'.


Just repeat yourself Write a program that outputs

Do not repeat yourself!

Your program code must respect the following constraints :

its length must be an even number
each character that is in position 2n (where n is an integer > 0) must be equal to the character in position 2n-1. The second character of the program is equal to the first, the fourth is equal to the third, etc.

Newlines count as characters!

This is code-golf, so the shortest code wins!

Examples

HHeellllooWWoorrlldd is a valid program

123 or AAABBB or HHeello are incorrect

Verification

You can use this CJam script to verify that your source code is valid. Simply paste your code into the "Input" box and run the script.

Hexagony, 166 126 124 bytes

\\;;;;33rr''22DD..));;;;;;oo;;}}eeoo\\@@nn;;;;ee;;;;aass&&;;uuoo;;;;..\\\\;;ttee..pp;;tt;;;;..rr;;''ll..'';;;;..;;}}ff..}}yy

Inserting the implicit no-ops and whitespace, this corresponds to the following source code:

       \ \ ; ; ; ; 3
      3 r r ' ' 2 2 D
     D . . ) ) ; ; ; ;
    ; ; o o ; ; } } e e
   o o \ \ @ @ n n ; ; ;
  ; e e ; ; ; ; a a s s &
 & ; ; u u o o ; ; ; ; . .
  \ \ \ \ ; ; t t e e . .
   p p ; ; t t ; ; ; ; .
    . r r ; ; ' ' l l .
     . ' ' ; ; ; ; . .
      ; ; } } f f . .
       } } y y . . .

I'm sure it's possible to shorten this even more, and maybe even solve it in side-length 6, but it's getting tricky...

How it works

Diagram generated with Timwi's Hexagony Colorer.

The code is completely linear. The \ right at the start redirects the IP into a diagonal, such that we don't need to worry about the doubled characters at all. The coloured paths are executed in the order orange/red, blue/grey, green, purple (when there are two paths of the same colour, the left-hand path is executed first, before wrapping around to the right-hand one).

If we ignore no-ops, mirrors and commands which are overridden by others, the linear code comes down to this:

D;o;&32;}n;o;t;';}r;e;p;e;a;t;';}y;o;u;r;s;e;l;f;');@

Letters in Hexagony just set the current memory edge's value to the letter's character code. ; prints the current memory edge as a character. We use & to reset the memory edge to 0 and print a space with 32;. } moves to a different edge, so that we can remember the 32 for further spaces. The rest of the code just prints letters on the new edge, and occasionally moves back and forth with ';} to print a space. At the end we move to the space edge again with ', increment the value to 33 with ) and print the exclamation mark. @ terminates the program.


Cook me a character meal Chef Avillez is about to cook us some really nice meal. He is just waiting for us to give him some ingredients and to request a meal.

Task

Given a list of ingredients (strings matching /[a-z]+/) and a requested meal (string matching /[a-z][a-z ]*/) output the integer amount of meals Chef Avillez can make.

Algorithm

Each letter ([a-z]) in the ingredient list contributes with one character for the soon-to-be-cooked meals. Each portion of our requested meal costs as many of each character as there are in the request string, excluding spaces.

For example, if our requested meal is "bacon" and the ingredients are "banana" and "coconut", the output is 1 because in "bananacoconut" there is only one b, and for each portion of "bacon" we need one "b".

Input

A list of ingredients in any reasonable format, like

a list of strings
a list of lists of characters
a (whatever-you-please)-separated list of ingredients, in a single string

and a requested meal in any reasonable format, like

a string
a list of characters

Output

A non-negative integer representing the amount of meals that can be cooked.

Test cases

A Python reference implementation is available.

['spam', 'spam', 'spam', 'spam', 'bacon', 'eggs', 'eggs', 'bacon', 'spam'], 'beans' -> 2
['bacon', 'bacon', 'bacon', 'bacon', 'bacon'], 'bacon' -> 5
['banana', 'coconut'], 'bacon' -> 1
['acon', 'bcon', 'baon', 'bacn', 'baco'], 'bacon' -> 4
['tomato', 'oregano', 'pizza', 'chocolate'], 'bacon' -> 0
['strawberries', 'figs', 'chocolate', 'sardines'], 'cod fish' -> 1
['these', 'are', 'some', 'random', 'words', 'wow'], 'or' -> 3
['some', 'more', 'delicious', 'ingredients', 'here'], 'bolognese' -> 0
['some', 'delicious', 'ingredients', 'here', 'are', 'bliss'], 'bolognese' -> 1
['some', 'bountiful', 'bagful', 'of', 'ingredients', 'here', 'are', 'bliss'], 'bolognese' -> 1

Python 2, 95 71 70 55 bytes

lambda i,m:min(i.count(c)/m.count(c)for c in m if" "<c)

Try it online!

Input: Ingredients i as a comma-separated string, and a meal m as a string.
Output: Max number of meals that can be made.

How: Divides the frequency of each character in the ingredient by its corresponding character in the meal, then takes the minimum.


Find the Maximal Prime Powers A prime power is a positive integer n that can be written in the form n = pk where p is a prime and k is a positive integer. For example, some prime powers are [2, 3, 5, 4, 9, 25, 8, 27, 125].

Next, consider prime powers of 2. These are [2, 4, 8, 16, ...] and can be written in the form 2k. They would all be included when considering prime powers beneath 20. However, 16 is the maximal prime power with a base prime of 2 in that range. A prime power pk is maximal in a range if it is the highest power of p in that range. We are only interested in the maximal prime power in each range so all lower prime powers must be excluded.

Your goal is to write a function or program that takes a positive integer n and outputs the maximal prime powers in the range [2, 3, 4, ..., n].

Thanks to @Peter Taylor for clarifying the definition of maximal prime power and more.

Rules

This is code-golf so make your code as short as possible.
The maximal prime powers may be output in any order but there must be no duplicates.

Test cases

n      result
1      []
2      [2]
3      [2, 3]
4      [3, 4]
5      [3, 4, 5]
6      [3, 4, 5]
7      [3, 4, 5, 7]
20     [5, 7, 9, 11, 13, 16, 17, 19]
50     [11, 13, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49]
100    [11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97]
10000  <1229 results>
       [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, ..., 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]

The full list of maximal prime powers for 10000 can be found here.

Jelly, 7 4 bytes

æḟÆR

Try it online!

How it works

æḟÆR  Main link. Argument: n

  ÆR  Prime range; yield all primes in [1, ..., n].
æḟ    Power floor; round n down to the nearest power of each prime in the range.


APL(Dyalog Unicode), 8 6 bytes SBCS
/⍨∘~∘≠

Try it on APLgolf!
A function submission which takes L1 on the left and L2 on the right.
-2 bytes from Bubbler.
Explanation
/⍨∘~∘≠
/⍨     remove elements from L! identified by:
   ~   the bitwise negation of
     ≠ unique mask of L2


Inverting lists of lists of indices Inspired by this StackOverflow post.
Introduction
Bob's job is to create spreadsheets and organize them.  The way he organizes them is known to very few except for Bob, but he creates a list of each of the spreadsheets that fall under the same group.  There's a bunch of data in the spreadsheet he creates, but there's only one piece of data that we're looking at right now: The number of days between the day he started this job and the day he made the spreadsheet.  The first day he created two spreadsheets, noted them both as 0 and sorted them in to their proper locations.
Now, his boss is asking for a review of what kinds of spreadsheet happened each day, and it's your job to write some code that will figure that out for Bob; he has far too many spreadsheets to do it by hand.
Input
Bob's info that he gives you comes in the form of a (0-or-1 indexed) jagged array where each datum is of the form x = a[i][j].  a is what I'm calling the jagged array itself, i is the type of spreadsheet, and x is the date the array was created.  j is unimportant.
The task
Given a jagged array of spreadsheet creation days organized by their type, return a jagged array of spreadsheet types organized by spreadsheet creation day.
Examples
Bob isn't going to just leave you with this abstract data. He's given me a subset of some of his spreadsheets to help you out with figuring out what everything is supposed to be.
Example input (0-indexed):
a = [
[3,2,5,0], # Bob doesn't necessarily sort his lists
[1,3],
[2,1,0,4],
[4,5,3],
[6,6]
]

Example output (with commentary, which of course is not required):
output = [
[0,2] # On day 0, Bob made one type 0 and one type 2 spreadsheet
[1,2] # On day 1, Bob made one type 1 and one type 2 spreadsheet
[0,2] # On day 2, Bob made one type 0 and one type 2 spreadsheet
[0,1,3] # On day 3, Bob made one type 0, one type 1, and one type 3 spreadsheet
[2,3] # On day 4, Bob made one type 2 and one type 3 spreadsheet
[0,3] # On day 5, Bob made one type 0 and one type 3 spreadsheet
[4,4] # On day 6, Bob made two type 4 spreadsheets
]

Note that Bob doesn't always make two spreadsheets every day, and so the output may be jagged as well. But he always makes at least one spreadsheet every day, so the output will never need to contain empty arrays - although if your output has empty arrays at the end, you don't need to remove them.
More test cases:
[[3,5,6,2],[0,0,0],[1,0,3,4]] -> [[1,1,1,2],[2],[0],[0,2],[2],[0],[0]]
[[-1]] -> Undefined behavior, as all input numbers will be non-negative integers.
[[0],[0],[],[0]] -> [[0,1,3]]

The output's inner lists do not need to be sorted.
As always, no standard loopholes, and of course shortest code wins.
(As this is my first question, please let me know of anything I can do to improve it.)

Jelly, 11 10 bytes

FṀ⁸ċþµJ€x"

Input and output are 1-based.

Try it online! or verify all test cases (0-based for easy comparison).


Anti-aliasing ASCII art Background

ASCII art is the practice of creating images by using ASCII text to form shapes.

Aliasing is the effect created by the large "pixels" of ASCII art, which are the size of characters. The image becomes blocky and hard to see. Anti-aliasing removes this effect by creating a gradient and by softening the hard edges of the ASCII art.

The Challenge

Your challenge is to write the shortest program possible that will take a piece of ASCII art and will output a version that has been anti-aliased.

What sort of anti-aliasing?

All of the ASCII art will consist of two types of symbols: Spaces and non-whitespace. For each non-whitespace character, your program must determine whether it is in a position where it need to be anti-aliased. If it is, then you need to replace it with the correct character. If it isn't, then the character stays the same.

How do you know if a character needs to be anti-aliased? The answer depends on the characters that are immediately above, below, left, and right of the character (not the diagonals). Here is a chart of when anti-aliasing is required, where ? and x can stand for any non-whitespace character.

 x? ->  d?
 ?      ?

?x  -> ?b
 ?      ?

 ?      ?
?x  -> ?F

 ?      ?
 x? ->  Y?

 x  ->  ;   Note: This character has been changed from _ to ;
 ?      ?

 ?      ?
 x  ->  V

?x  -> ?>

 x? ->  <?

 x  ->  @

Input (and example pre-anti-aliasing ASCII art)

First, there will be two lines of input (to STDIN), a number H followed by a number W. There will then be H lines of exactly W characters each (excluding the newline). These following lines will be the ASCII art that needs to be anti-aliased. Here is an example input (not beautiful, but a test):

7
9
  888888
 888888
999 98  7
 666666
  666666
   6666
    6

Output (and example anti-aliased art)

Your program should output to STDOUT the ASCII art (of the same dimensions), which has been anti-aliased. Here is the output for the above input. Notice how the the border characters are treated as bordering whitespace.

  d8888>
 d8888F
<99 98  @
 Y6666b
  Y6666>
   Y66F
    V

This might not look that good (due to the space between lines in the code block), it looks better with larger ASCII art, and the quality depends on the exact font used.

Another Example

Input

12
18
   xx  xxx  xxx
  xxxx  xxx  xxx
 xxxxxx  xxx  xxx
xxx  xxx  xxx  xxx
xxxx xxx  xxx  xxx
 xxxxxx  xxx  xxx
  xxxx  xxx  xxx
x  xx  xxx  xxx  x
xx    xxx  xxx  xx
xxx  xxx  xxx  xxx
xxxx  xxx  xxx  xx
xxxxx  xxx  xxx  x

Output

   db  <xb  <xb
  dxxb  Yxb  Yxb
 dxxxxb  Yxb  Yxb
dxx  xxb  xxb  xxb
Yxxb xxF  xxF  xxF
 YxxxxF  dxF  dxF
  YxxF  dxF  dxF
;  YF  dxF  dxF  ;
xb    dxF  dxF  dx
xxb  <xF  <xF  <xx
xxxb  Yxb  Yxb  Yx
Yxxx>  Yx>  Yx>  V

Rules, Restrictions, and Notes

Your program should be written in printable ASCII characters only, so that we can make art out of the programs. Other than that, the standard code-golf rules apply.

Ruby, 180 168 characters
gets
w=1+gets.to_i
f=*(readlines*"").chars
f.zip(f[1..-1]+s=[" "],s+f,s*w+f,f[w..-1]+s*w){|a,*b|$><<"@;V#{a}>bF#{a}<dY#{a*5}"[a>" "?(b.map{|y|y>" "?1:0}*"").to_i(2):3]}

Another Ruby implementation which takes a zip approach. You can see the second example running online.
Edit: Using readlines saves 12 characters.


Ray-trace a shiny sphere I downloaded POV-ray and rendered this shiny metal sphere 90s style:

Your task is to do the same thing, but to do it by implementing the rendering engine yourself in as few bytes as possible. You don't have to replicate this exact image - any image of a reflective sphere above an infinite checkerboard will do, as long as it meets the criteria below.

Rules:

The image must depict a reflective sphere hovering above an infinite checkerboard. Both the checkerboard itself and its reflection in the sphere must be shown in the image. It must be visually clear that this is what we're seeing. Beyond this, the details of the geometry, colours, material properties etc. are up to you.
There must be some lighting in the scene: parts of the sphere should be darker than other parts, and visually it should be possible to tell roughly where the light is coming from. Beyond that, the details of the lighting model are up to you. (You can invent your own simplified lighting model if you like.) The sphere doesn't have to cast a shadow.
The above two criteria - whether it really looks like a shiny sphere above a checkerboard illuminated by a light source - will be judged by the community using voting. Therefore, an answer must have a positive score in order to be eligible to win.
The output must be at least 300x300 pixels. It can be displayed on the screen or written to a file, either is fine.
Your code should run in less than an hour on a reasonable modern computer. (This is generous - POV-ray renders the above scene practically instantaneously.)
No built-in ray tracing functionality may be used - you must implement the renderer yourself.
This is code-golf, so the positive-scoring entry with the shortest code (in bytes) wins. However, you're also welcome to play the meta-game of getting the most votes by drawing a pretty picture (while keeping the code short of course).

This challenge might seem ridiculously hard, but since the geometry is fixed, the algorithm for rendering such a scene by ray tracing is pretty straightforward. It's really just a case of iterating over each pixel in the output image and evaluating a mathematical expression to see what colour it should be, so I'm optimistic that we'll see some good answers.

Python 2, 484 468 467 bytes

i=int;u=249.3
def Q(A,B):
 a=A*A+B*B+9e4;b=B*u+36e4;I=b*b-a*128e4
 if I>0:
    t=(-b+I**.5)/(5e2*a);F,G,H=A*t,B*t,u*t;J,K,M=F,G+.6,H+2.4;L=a**-.5;k=2*(A*J+B*K+u*M)*L;C,D,E=A*L-k*J,B*L-k*K,u*L-k*M;L=(C*C+D*D+E*E)**-.5;t=(-4e2-G)/D;return(D*D*L*L*u,((i(F+t*C)/200+i(H+t*E)/200)&1)*(u*D*L))[D>0]
 else:return(u*B*B/a,((i(-2e2/B*A)/200+i(-6e4/B)/100)&1)*u*B/a**.5)[B>0]
open("s.pgm","wb").write("P5 800 600 255 "+"".join(chr(i(Q(j%800-4e2,j/800-u)))for j in range(480000)))

Note: after if I>0: there is a newline followed by a single tab char before t=...

Running the program will create an 800x600 image named s.pgm

Started from a "real" ray tracer formulas (tweaked a bit for golfing).

Rendering takes about 3s on my dead old PC (0.7s with pypy).


Simulate Cookie Clicker Intro

Cookie Clicker is a popular browser game in which the player has to click a cookie to gain... Cookies!
The player can buy upgrades which will automatically farm cookies for you. Sometimes a golden cookie will enter the screen, which will provide a bonus upon clicking it.

Challenge

This challenge will not be about clicking a cookie. It will be about automating the cookie.
The player starts off with 0 cookies, and will gain cookies on every game tick. The goal of the challenge is to calculate the amount of ticks it takes to reach a certain amount of cookies.

Input

Your program or function will have 2 input parameters.
The first parameter is the goal, which is simply the amount of cookies you need to finish.
The second parameter is a list of upgrades the player can buy. The format of the list will be explained in further detail in the paragraph Upgrades - List format.
For sake of convenience, you may assume that the input is always in the correct format. You don't have to deal with bad input.

Output

Your program or function should print or return the amount of ticks it takes before the player has reached the goal amount of cookies.

Upgrades

Every game-tick will earn the player some cookies. These are based on the upgrades of the player. If a player has no upgrades, the cookie production will be 1 cookie per tick. Once the player reaches enough cookies to buy an upgrade, he will automatically purchase it (before the next tick happens).
When the player has enough cookies after a tick to buy multiple upgrades, he will attempt to buy all possible upgrades, starting with the cheapest.

List format

[[100, '+', 1],[1000, '*', 2],[10000, '*', 10]
This is an unordered list which contains 3 upgrades. The first parameter of an upgrade is the price of the upgrade. The second parameter is the effect of the upgrade and the third parameter is the effect amount.
The input list will contain no upgrades with the same price.
The only possible effects are + (addition) and * (multiplication).
[100, '+', 1] means that the cookie production will increase by 1 at a cost of 100 cookies.

Golden cookies

Every 1000 ticks, the player will find a golden cookie. When this happens, the player will receive a bonus of 10% (rounded down) of his cookie amount. If the player has 1000 cookies at tick 1000, he will have 1100 cookies before tick 1001 happens.

Order of events

After every tick a couple of actions can occur.

If the player has enough cookies, end the game
If the player has enough cookies, purchase upgrades
If the amount of ticks is a multiple of 1000; Golden cookie

Example input + output

(0    , [])                              -> 0
(100  , [])                              -> 100
(1    , [[10, '+', 1]])                  -> 1
(10   , [[10, '+', 1]])                  -> 10
(1000 , [[100, '*', 2], [10, '+', 1]])   -> 310
(10000, [[10, '+', 1], [100, '*', 2]])   -> 2263

Detailed example

(1000 , [[100, '*', 2], [10, '+', 1]])   -> 310

ticks: 8, cookies: 8, production: 1
ticks: 9, cookies: 9, production: 1
ticks: 10, cookies: 0, production: 2
ticks: 11, cookies: 2, production: 2
ticks: 58, cookies: 96, production: 2
ticks: 59, cookies: 98, production: 2
ticks: 60, cookies: 0, production: 4
ticks: 61, cookies: 4, production: 4
ticks: 70, cookies: 40, production: 4
ticks: 80, cookies: 80, production: 4
ticks: 260, cookies: 800, production: 4
ticks: 280, cookies: 880, production: 4
ticks: 300, cookies: 960, production: 4
ticks: 309, cookies: 996, production: 4
ticks: 310, cookies: 1000, production: 4 -- done

Disclaimer

I will not be held responsible for any addictions caused by this challenge.

Happy golfing!


Mutually Attacking Queens Let an 8x8 chessboard be represented by any two distinct values, with one value being an empty square and the other being a queen. In the following examples, I use 0s as the empty squares and 1s as queens. For example:

is given by

1 0 1 1 1 0 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 1
1 0 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 1

Consider the number of pairs of queens that are attacking each that are at least one square away (as a reminder, queens attack orthogonally and diagonally). In the above example, the following incredible ugly diagram shows all these pairs as arrows.

There are 43 pairs found above giving the following test case:

Input:
1 0 1 1 1 0 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 1
1 0 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 1
Output: 43

Challenge

Write a program that, given a board state represented by two distinct values, outputs the number of pairs of queens that attack each other with at least one square in between them.

You may input in whatever format is most convenient that uses two values to represent the empty squares and queens, e.g., a string of 64 "."s for empty squares and "Q"s for queens by rows from bottom to top, an 8x8 matrix of booleans, a list of list of integers 0 and 1 etc, as long as it is explained in your solution
Output is an integer
Standard I/O methods apply and standard loopholes forbidden
This is code golf so shortest answer in bytes wins

Test cases:

Using the 0 and 1 format, with 0 being empty squares and 1 being queens:

Input:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 0

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 0

Input:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 1

Input:
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0
Output: 10

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 4

Input:
1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 11

Python 2, 105 bytes

lambda b:sum(b[i+d::d][:(8,7-i%8,i%8)[d%8%5]].find('1')*int(c)>0for i,c in enumerate(b)for d in[1,7,8,9])

Try it online!

Explanation

We take the input as a string of 64 characters '0' or '1'. Using step slices, we cast four "lines of sight" from every queen we encounter. For example, when i = 10 and d = 7, marking the queen as ♥ and the tiles selected by b[i+d::d] as █:

1 0 1 1 1 0 0 0
1 0 ♥ 0 1 0 1 1
1 █ 1 0 1 1 0 1
█ 1 0 1 0 1 0 █
0 1 1 0 0 1 █ 1
1 0 0 0 1 █ 0 0
0 1 0 0 █ 1 1 1
0 1 1 █ 0 1 0 1

Clearly, we don't actually want vision to wrap around the board like this. So we compute how far away the edge of the board is in each direction, and view the tiles at b[i+d::d][:…].

For each tile-direction pair we count:

ray.find('1')*int(c)>0

This will fail whenever

c is not a queen; or
the queen this ray sees is too close (find returns 0); or
this ray sees no queen (find returns −1).

Each pair of queens is only checked once, since rays are always casted forward in reading order, from an "earlier" queen to a "later" one.


Use an editor to write "Hello, World" Objective
Use any editor or IDE (vim, emacs, IntelliJ, etc) to write a valid "Hello, World" program in any C-like language. The "!" is optional, but you get style points if you use it. You may use publicly available plugins, a publicly available vimrc, etc, but you may not write or make modifications to them specifically for this challenge.
Winning
Fewest key presses and mouse clicks and touchscreen taps :P wins (only counted when the key is pressed down).
Submission:
A valid submission requires the number of key presses, the editor used, the language used, a list of the keystrokes pressed, and the important parts of any vimrc, a list of plugins, or anything else required to replicate your result.

Vim with Ultisnips in C (gcc), 30 keystrokes

imaTabTabputs("Hello, World!");Esc:x

Explanation

To use the above you'll need the mentioned Plugin installed and g:UltiSnipsExpandTrigger and g:UltiSnipsJumpForwardTrigger bound to Tab, further you'll need this snippet in your g:UltiSnipsDir. This also makes the assumption that you opened a file which sets filetype=c:

ima: Change to Insert mode and enter ma
TabTab: Select and expand the main <snip>
puts("Hello, World!");: Insert the remaining characters
Esc: Change to Normal mode
:x: Write the file and exit

The resulting file looks like this:

int main(int argc, char *argv[])
{
  puts("Hello, World!");
  return 0;
}

Note: I couldn't just now find a complete vimrc but here's a StackOverflow post that mentions the relevant parts.


The longest period iterating quine As we know, a quine is a program that outputs its own source code. However, it's also possible to write a program that outputs another, different program, that outputs the first program again. For example, the Python 2 program

x = '''x = {}
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3'''
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3

will, when run, output the following text:

print """x = '''x = {}
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3'''
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3"""

When run as a Python program, this will output the original code again. This is called an iterating quine. Because you have to run it twice to get the original code back, we say it has period 2. But of course, much higher periods are possible.

Your challenge is to write an iterating quine with as long a period as you can, in 100 bytes or less, in the language of your choice. (Note that my example above doesn't fit this spec, as it's 119 bytes, including the trailing newline.)

Please note the following rules and clarifications:

The usual quine rules apply, i.e. your program can't use language features that would let it access its own source code directly.
The iterated outputs have to eventually loop back to exactly your original code, and you have to include a demonstration or proof that it will.
You must also include an explanation of why the cycle is as long as you say it is. This doesn't have to be at the level of a mathematical proof, but it should be convincing to someone familiar with your language. (This rule is here because I expect some of the answers to involve very, very large numbers.)
It's fine to say something like "at least 1,000,000 iterations" rather than giving the exact number, as long as you can prove that it is at least that long. In this case, your score would be 1,000,000. Otherwise, your score is the period of your quine.
The 100 byte limit only applies to your initial program - the programs it outputs can be longer, though of course they'll eventually have to get back down to 100 bytes in order to output your original code.
You can assume your machine has infinite RAM and infinite runtime, but you can't assume unlimited precision data types (such as integers) if your language doesn't have them. You can assume there is no limit to the length of input your parser can handle.
The highest score wins.

Please note: there is an existing challenge called Quit Whining; Start Quining that also involves iterating quines. However, aside from being based on the same concept, these are completely different types of challenge. The other one is straight up code golf, whereas this one is (intentionally!) really a busy beaver problem in disguise. The techniques needed to produce a good answer to this question are likely to be very different from what's needed to answer the other question, and this is very much by design.

PHP, period 2,100,000,000

Who would've thought that this is possible in PHP?! :-)

This is actually my first ever quine and it's 99 bytes long:

<?$i=1;$i*=21e8>$i;printf($a='<?$i=%d;$i*=21e8>$i;printf($a=%c%s%c,++$i,39,$a,39);',++$i,39,$a,39);

Although PHP supports bigger numbers than 2 * 10^8 by switching from integer to double, the increment no longer works (leads to an infinite loop) and I haven't found another solution which fits into the 100 bytes. Yet.

Proof is fairly simple, since it's just counting up on each iteration until it reaches the reset point at 2.1 billion.

Credits to dave, who posted the approach in pseudo code in the comments and to Bob Twells, from whom I copied the code for a minimal PHP quine.

Test program (sloooooow):

<?php
$o = file_get_contents('quine.php');
for ($i = 0; $i < 22e8; $i++) {
    if ($i%2==0) exec('php q > p'); else exec('php p > q');
    $a = file_get_contents(($i%2==0) ? 'p' : 'q');
    echo "\r" . str_pad($i,6,' ') . ":\t$a";
    if ($a == $o) {
        die;
    }
}

Well, at least I'm the first one to answer.


Factoring a 64-bit integer Write a GOLF assembly program that reads an integer from stdin (followed by a trailing newline), and outputs its prime factors seperated by newlines, followed by a trailing newline on stdout.
The prime factors need not be in a particular order. 1 is not a prime factor.
Your GOLF binary (after assembling) must fit in 8192 bytes.

Your program will be scored by running it 10 times, each with one of the following inputs:
8831269065180497
2843901546547359024
6111061272747645669
11554045868611683619
6764921230558061729
16870180535862877896
3778974635503891117
204667546124958269
16927447722109721827
9929766466606501253

These numbers are roughly sorted in terms of difficulty. The first one should easily be solvable by trial division.
Optimization towards this set of numbers is against the spirit of the question, I may change the set of numbers at any point. Your program must work for any positive 64-bit input number, not just these.
Your score is the sum of CPU cycles used to factor the above numbers.

Because GOLF is very new I'll include some pointers here. You should read the  GOLF specification with all instructions and cycle costs. In the Github repository example programs can be found. In particular look at the factorial example program, which demonstrates input/output.
Compile your program to a binary by running python3 assemble.py your_source.golf. Then run your program using python3 golf.py your_source.bin, this should print the cycle count as well. See the values of the register contents at program exit with the -d flag - use --help to see all flags.

Total 36,757,269,913 cycles

830B assembled

Number                Time (s)  Cycles
    8831269065180497       0.1         1148
 2843901546547359024      55.0      9535194
 6111061272747645669     351.4     60559378
11554045868611683619       0.8       135135
 6764921230558061729       1.0       155407
16870180535862877896   43067.5   7126449414
 3778974635503891117     148.7     22823483
  204667546124958269      87.4     13635943
16927447722109721827   16119.0   2739172134
 9929766466606501253  156158.3  26784802677

Factorization by trial division, with a few optimizations.
Probably not the fastest, but as no one else has posted yet, I'll kick it off.

main:
    call read
    call factor
    halt 0

# Prints factors. Pass number to be factored in register `a'.
factor:
    mov n, a # Write routine expects factor in `a', so we'll just keep it there.
    # Handle 2 specially
_factor_twos:               # do {
    geu b, n, 1
    jz _factor_ret, b   #   if (number <= 1) return
    and b, n, 1
    jnz _factor_rest, b #   if (number & 1 != 0) break
    mov a, 2
    call write          #   printf("%llu\n", 2)
    shr n, n, 1         #   number >>= 1
    jmp _factor_twos    # } while (0)
_factor_rest:
    mov a, 3            # factor = 3
_factor_rest_loop:          # do {
    cmp b, n, 1
    jnz _factor_ret, b  #   if (number == 1) return
    divu b, c, n, a     #   (quotient, remainder) = number / factor
    jnz _factor_not_divisible, c # if (remainder == 0) {
    call write                   #   printf("%llu\n", factor)
    mov n, b                     #   number = quotient
    jmp _factor_rest_loop
_factor_not_divisible:               # } else {
    leu c, b, a
    jnz _factor_print_last, c    #   if quotient < a, print n and return.
    add a, a, 2                  #   else a += 2 }
    jmp _factor_rest_loop # } while (0)
_factor_print_last:
    mov a, n
    call write # printf("%llu", n)
_factor_ret:
    ret

# Read stdin. Must be one decimal string, ending with a newline.
# Behavior on invalid input is unspecified.
# Return value stored in a.
read:
    mov a, 0
_read_loop_start:                # do {
    lw c, 0xffffffffffffffff #   c = getchar()
    sub b, c, ord('\n')
    jz _read_ret, b          #   if (c == '\n'), return
    sub c, c, ord('0')       #   c -= '0'
    mulu a, y, a, 10
    add a, a, c              #   a = 10*a + c
    jmp _read_loop_start     # } while (0)
_read_ret:
    ret a

# Write number in register a to stdout, followed by a newline.
# Fortunately, a 64-bit number has at most 20 digits, and we have 25 registers.
# So we can keep them in registers instead of pushing them onto the stack or heap,
# avoiding the fairly expensive read back.
write:
    divu a, b, a, 10
    jz _write_b, a
    divu a, c, a, 10
    jz _write_c, a
    divu a, d, a, 10
    jz _write_d, a
    divu a, e, a, 10
    jz _write_e, a
    divu a, f, a, 10
    jz _write_f, a
    divu a, g, a, 10
    jz _write_g, a
    divu a, h, a, 10
    jz _write_h, a
    divu a, i, a, 10
    jz _write_i, a
    divu a, j, a, 10
    jz _write_j, a
    divu a, k, a, 10
    jz _write_k, a
    divu a, l, a, 10
    jz _write_l, a
    divu a, m, a, 10
    jz _write_m, a
    divu a, n, a, 10
    jz _write_n, a
    divu a, o, a, 10
    jz _write_o, a
    divu a, p, a, 10
    jz _write_p, a
    divu a, q, a, 10
    jz _write_q, a
    divu a, r, a, 10
    jz _write_r, a
    divu a, s, a, 10
    jz _write_s, a
    divu a, t, a, 10
    jz _write_t, a
    add a, a, ord('0')
    sw 0xffffffffffffffff, a
_write_t:
    add t, t, ord('0')
    sw 0xffffffffffffffff, t
_write_s:
    add s, s, ord('0')
    sw 0xffffffffffffffff, s
_write_r:
    add r, r, ord('0')
    sw 0xffffffffffffffff, r
_write_q:
    add q, q, ord('0')
    sw 0xffffffffffffffff, q
_write_p:
    add p, p, ord('0')
    sw 0xffffffffffffffff, p
_write_o:
    add o, o, ord('0')
    sw 0xffffffffffffffff, o
_write_n:
    add n, n, ord('0')
    sw 0xffffffffffffffff, n
_write_m:
    add m, m, ord('0')
    sw 0xffffffffffffffff, m
_write_l:
    add l, l, ord('0')
    sw 0xffffffffffffffff, l
_write_k:
    add k, k, ord('0')
    sw 0xffffffffffffffff, k
_write_j:
    add j, j, ord('0')
    sw 0xffffffffffffffff, j
_write_i:
    add i, i, ord('0')
    sw 0xffffffffffffffff, i
_write_h:
    add h, h, ord('0')
    sw 0xffffffffffffffff, h
_write_g:
    add g, g, ord('0')
    sw 0xffffffffffffffff, g
_write_f:
    add f, f, ord('0')
    sw 0xffffffffffffffff, f
_write_e:
    add e, e, ord('0')
    sw 0xffffffffffffffff, e
_write_d:
    add d, d, ord('0')
    sw 0xffffffffffffffff, d
_write_c:
    add c, c, ord('0')
    sw 0xffffffffffffffff, c
_write_b:
    add b, b, ord('0')
    sw 0xffffffffffffffff, b
    sw 0xffffffffffffffff, ord('\n')
    ret
# End of write.

Full output from my timing loop, in case anyone wants to check the results and/or my copy-paste and math.

13
23
31
37
41
47
47
59
61
79
Execution terminated after 1148 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  0.09s user 0.02s system 94% cpu 0.115 total
2
2
2
2
3
3
107
1121707
164546579
Execution terminated after 9535194 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  55.03s user 0.07s system 99% cpu 55.136 total
3
3
3
7
7
7
13
50759273983933
Execution terminated after 60559378 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  351.38s user 0.32s system 99% cpu 5:51.89 total
7
7
7
13
2531
4091
250250521
Execution terminated after 135135 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  0.84s user 0.01s system 99% cpu 0.857 total
31
89
97
3881
18211
357653
Execution terminated after 155407 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  0.98s user 0.01s system 99% cpu 0.997 total
2
2
2
3
702924188994286579
Execution terminated after 7126449414 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  43067.49s user 86.38s system 99% cpu 12:04:12.58 total
7
103
727
7209485975851
Execution terminated after 22823483 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  134.60s user 0.13s system 99% cpu 2:14.83 total
66449
1604167
1920043
Execution terminated after 13635943 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  81.02s user 0.06s system 99% cpu 1:21.12 total
322255481
52528036667
Execution terminated after 2739172134 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  16119.02s user 12.31s system 99% cpu 4:29:03.61 total
9929766466606501253
Execution terminated after 26784802677 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  156158.25s user 186.81s system 49% cpu 88:35:03.65 total


Trifid Cipher (without keyword) Introduction:
I have loads of different ciphers stored in a document I once compiled as a kid, I picked a few of the ones I thought were best suitable for challenges (not too trivial, and not too hard) and transformed them into challenges. Most of them are still in the sandbox, and I'm not sure yet whether I'll post all of them, or only a few. Here is the second one (the Computer Cipher was the first one I posted).

For the Trifid Cipher (without using a keyword) the alphabet (and an additional wildcard) is divided into three 3 by 3 tables:
table 1:     table 2:     table 3:
 |1 2 3       |1 2 3       |1 2 3
-+-----      -+-----      -+-----
1|a b c      1|j k l      1|s t u
2|d e f      2|m n o      2|v w x
3|g h i      3|p q r      3|y z

A text we want to encipher is first character by character encoded into table-row-column numbers. For example, the text this is a trifid cipher becomes:
        t h i s   i s   a   t r i f i d   c i p h e r
table:  3 1 1 3 3 1 3 3 1 3 3 2 1 1 1 1 3 1 1 2 1 1 2
row:    1 3 3 1 3 3 1 3 1 3 1 3 3 2 3 2 3 1 3 3 3 2 3
column: 2 2 3 1 3 3 1 3 1 3 2 3 3 3 3 1 3 3 3 1 2 2 3

We then put everything after one another row by row in the table above in groups of three:
311 331 331 332 111 131 121 121 331 331 313 133 232 313 332 322 313 313 132 333 313 331 223

And those are transformed back to characters using the same tables:
s   y   y   z   a   g   d   d   y   y   u   i   q   u   z   w   u   u   h       u   y   o

One thing to note, the input-length should be coprime to 3. So if the length is a multiple of 3, we append one or two trailing spaces to make the input-length not a multiple 3 anymore.
Challenge:
Given a string sentence_to_encipher, encipher it as described above.
You only have to encipher given the sentence_to_encipher, so no need to create a deciphering program/function as well. I might make a part 2 challenge for the deciphering in the future however (although I have the feeling it's to trivial/similar to the enciphering process).
Challenge rules:

You can assume the sentence_to_encipher will only contain letters and spaces.
You can use either full lowercase or full uppercase (please state which one you've used in your answer).
You can choose to append either one or two trailing spaces when the input-length is 3 to make it not a multiple of 3 anymore.
I/O is flexible. Both input and output can be a string, list/array/stream of characters, etc.

General rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code (i.e. TIO).
Also, adding an explanation for your answer is highly recommended.

Test cases:
Input:            "this is a trifid cipher"
Output:           "syyzagddyyuiquzwuuh uyo"

Input:            "test"
Output:           "utbk"

Input:            "output"
Possible outputs: "rrvgivx" (one space) or "rrzcc lr" (two spaces)

Input:            "trifidcipher"
Possible output:  "vabbuxlzz utr" (one space) or "vabbyzv rx ie " (two spaces)

Charcoal, 39 bytes

≔Ｅ⁺θ× ¬﹪Ｌθ³⌕βιθ⭆⪪Ｅ⁺÷θ⁹⁺÷θ³θ﹪ι³¦³§⁺β ↨³ι

Try it online! Link is to verbose version of code. Explanation:

≔               Assign
   θ            Input string
  ⁺             Concatenated with
                Literal space
    ×           Repeated
         θ      Input string
        Ｌ       Length
       ﹪        Modulo
          ³     Literal 3
      ¬         Logical not
 Ｅ              Mapped over characters
             ι  Current character
           ⌕    Position found in
            β   Lowercase alphabet
              θ To variable

     θ                      List of positions
    ÷                       Vectorised integer divide by
      ⁹                     Literal 9
   ⁺                        Concatenated with
         θ                  List of positions
        ÷                   Vectorised integer divide by
          ³                 Literal 3
       ⁺                    Concatenated with
           θ                List of positions
  Ｅ                         Map over values
             ι              Current value
            ﹪               Modulo
              ³             Literal 3
 ⪪                          Split into
                ³           Groups of 3
⭆                           Map over groups and join
                   β        Lowercase alphabet
                  ⁺         Concatenated with
                            Literal space
                 §          Cyclically indexed by
                       ι    Current group
                     ↨      Converted from
                      ³     Base 3
                            Implicitly print


Estimate the mean minimum Hamming distance Task

Inputs \$b \leq 100\$ and \$n \geq 2\$.  Consider \$n\$ binary strings, each of length \$b\$ sampled uniformly and independently. We would like to compute the expected minimum Hamming distance between any pair.  If \$n = 2\$ the answer is always \$b/2\$.

Correctness

Your code should ideally be within \$\pm0.5\$ of the correct mean.  However, as I don't know what the correct mean is, for values of \$n\$ which are not too large I have computed an estimate and your code should be within \$\pm0.5\$ of my estimate (I believe my estimate is within \$\pm0.1\$ of the correct mean). For larger values than my independent tests will allow, your answer should explain why it is correct.

\$b = 99, n = 2^{16}.\$ Estimated avg. \$19.61\$.
\$b = 89, n = 2^{16}.\$ Estimated avg. \$16.3\$.
\$b = 79, n = 2^{16}.\$ Estimated avg. \$13.09\$.
\$b = 69, n = 2^{16}.\$ Estimated avg. \$10.03\$.
\$b = 59, n = 2^{16}.\$ Estimated avg. \$7.03\$.
\$b = 99, n = 2^{15}.\$ Estimated avg. \$20.67\$.
\$b = 89, n = 2^{15}.\$ Estimated avg. \$17.26\$.
\$b = 79, n = 2^{15}.\$ Estimated avg. \$13.99\$.
\$b = 69, n = 2^{15}.\$ Estimated avg. \$10.73\$.
\$b = 59, n = 2^{15}.\$ Estimated avg. \$7.74\$.
\$b = 99, n = 2^{14}.\$ Estimated avg. \$21.65\$.
\$b = 89, n = 2^{14}.\$ Estimated avg. \$18.23\$.
\$b = 79, n = 2^{14}.\$ Estimated avg. \$14.83\$.
\$b = 69, n = 2^{14}.\$ Estimated avg. \$11.57\$.
\$b = 59, n = 2^{14}.\$ Estimated avg. \$8.46\$.

Score

Your base score will be the number of the examples above that your code gets right within \$\pm0.5\$. On top of this you should add \$x > 16\$ for the largest \$n = 2^x\$ for which your code gives the right answer within \$\pm0.5\$ for all of \$b = 59, 69, 79, 89, 99\$ (and also all smaller values of \$x\$).  That is, if your code can achieve this for \$n=2^{18}\$ then you should add \$18\$ to your score. You only get this extra score if you can also solve all the instances for all smaller \$n\$ as well. The number of strings \$n\$ will always be a power of two.

Time limits

For a single \$n, b\$ pair, your code should run on TIO without timing out.

Rougher approximation answers for larger values of \$n\$

For larger values of \$n\$ my independent estimates will not be as accurate but may serve as a helpful guide nonetheless.  I will add them here as I can compute them.

\$b = 99, n = 2^{17}.\$ Rough estimate \$18.7\$.
\$b = 99, n = 2^{18}.\$ Rough estimate \$17.9\$.
\$b = 99, n = 2^{19}.\$ Rough estimate \$16.8\$.

Python 3, score = big(?)

from math import exp, log, log1p

def f(b, n):
    e = n * (n - 1) / 2
    m = 0
    c = 1
    s = 0
    t = 1 << b
    for k in range(b):
        s += c
        m += exp(e * (log1p(-s / t) if 2 * s < t else log((t - s) / t)))
        c = c * (b - k) // (k + 1)
    return m

Try it online!

The Hamming distance \$D_{x, y}\$ between any two of the strings (\$1 \le x < y \le n\$) is a random variable distributed as the Binomial distribution \$B{\left(b, \tfrac12\right)}\$:

$$
\Pr[D_{x, y} > k] = 1 - \frac{1}{2^b} \sum_{i=0}^k \binom bi.
$$

Furthermore, any (distinct) two of these \$\binom n2\$ random variables are independent.

If we make the incorrect but empirically useful assumption that all \$\binom n2\$ of these random variables are independent, then we can compute the distribution of their minimum \$D = \min_{1 \le x < y \le n} D_{x,y}\$ exactly:

$$
\begin{gather*}
\Pr[D > k] = \left(1 - \frac{1}{2^b} \sum_{i=0}^k \binom bi\right)^{\binom n2}, \\
\mathbb E[D] = \sum_{k=0}^{b-1} \Pr[D > k].
\end{gather*}
$$

This result can be computed extremely quickly and seems to be close enough.  Numerical evidence suggests that the absolute error is worst at \$b = 1, n = 3\$ (where we estimate the expected minimum as \$\tfrac18\$ when it is actually \$0\$), and drops off quickly to zero as \$b\$ and/or \$n\$ get large.


On the edges of the hypercube Your job will be to write a function or a program, that will take an integer n>0 as input and output a list of the edges of the n-dimensional hypercube. In graph theory an edge is defined as a 2-tuple of vertices (or corners, if you prefer), that are connected.

Example 1

A 1-dimensional hypercube is a line and features two vertices, which we will call a and b.

Therefore, the output will be:

[[a, b]]

Example 2

The 4-dimensional hypercube (or tesseract) consists of 32 edges and its graph looks like this

and the output could look like this

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

Rules

You may name the vertices any way you like, as long as the name is unique.
The edges are undirected, i.e. [a, b] and [b, a] are considered the same edge.
Your output must not contain duplicate edges.
The output may be in any sensible format.
Standard loopholes are forbidden.

Scoring

Shortest code wins.

Python 2, 54 56 62 bytes

lambda n:{tuple({k/n,k/n^1<<k%n})for k in range(n<<n)}

Duplicate edges are removed by making a set of sets, except Python requires that set elements are hashable, so they are converted to a tuples. Note that the sets {a,b} and {b,a} are equal and convert to the same tuple. xsot saved 2 bytes with n<<n.
This can be cut down to 49 bytes if strings of sets are an OK output format
lambda n:{`{k/n,k/n^1<<k%n}`for k in range(n<<n)}

which gives output like
set(['set([1, 3])', 'set([2, 3])', 'set([0, 2])', 'set([0, 1])'])

lambda n:[(k/n,k/n^1<<k%n)for k in range(n*2**n)if k/n&1<<k%n]

First, let's look at an older version of the solution.
lambda n:[(i,i^2**j)for i in range(2**n)for j in range(n)if i&2**j]

Each a number in the interval [0,2^n) corresponds to a vertex with coordinates given by its n-bit binary strings. To vertices are adjacent if they differ in a single bit, i.e. if one is obtained from the other by xor-ing a power of 2.
This anonymous function generates all possible edges by taking every vertex and every bit position to flip. To avoid duplicating an edge in both directions, only 1's are flipped to 0's.
In the more golfed solution, k is used to encode both i and j via k=n*i+j, from which (i,j) can be extracted as (k/n,k%n). This saves a loop in the comprehension. The powers of 2 are done as 1<< to have the right operator precedence.
An alternative approach of generating each pair of vertices and checking if they are a bit flip apart seems longer (70 bytes):
lambda n:[(i,x)for i in range(2**n)for x in range(i)if(i^x)&(i^x)-1<1]


Google Code Jam - New Lottery Game I was looking around on the web and I found this Google Code Jam Puzzle. I really liked it so I decided to post it here.

  New Lottery Game

  The Lottery is changing! The Lottery used to have a machine to
  generate a random winning number. But due to cheating problems, the
  Lottery has decided to add another machine. The new winning number
  will be the result of the bitwise-AND operation between the two random
  numbers generated by the two machines.

  To find the bitwise-AND of X and Y, write them both in binary; then a
  bit in the result in binary has a 1 if the corresponding bits of X and
  Y were both 1, and a 0 otherwise. In most programming languages, the
  bitwise-AND of X and Y is written X&Y.

  For example:    The old machine generates the number 7 = 0111.    The
  new machine generates the number 11 = 1011.    The winning number will
  be (7 AND 11) = (0111 AND 1011) = 0011 = 3.

  With this measure, the Lottery expects to reduce the cases of
  fraudulent claims, but unfortunately an employee from the Lottery
  company has leaked the following information: the old machine will
  always generate a non-negative integer less than A and the new one
  will always generate a non-negative integer less than B.

  Catalina wants to win this lottery and to give it a try she decided to
  buy all non-negative integers less than K.

  Given A, B and K, Catalina would like to know in how many different
  ways the machines can generate a pair of numbers that will make her a
  winner.

  Could you help her?

  Input

  The first line of the input gives the number of test cases, T. T lines
  follow, each line with three numbers A B K.

  Output

  For each test case, output one line containing "Case #x: y", where x
  is the test case number (starting from 1) and y is the number of
  possible pairs that the machines can generate to make Catalina a
  winner.

  Limits

  1 ≤ T ≤ 100. Small dataset

  1 ≤ A ≤ 1000. 1 ≤ B ≤ 1000. 1 ≤ K ≤ 1000. Large dataset

  1 ≤ A ≤ 109. 1 ≤ B ≤ 109. 1 ≤ K ≤ 109. Sample

Input                 Output
5                     Case #1: 10
3 4 2                 Case #2: 16
4 5 2                 Case #3: 52
7 8 5                 Case #4: 2411
45 56 35              Case #5: 14377
103 143 88

  In the first test case, these are the 10 possible pairs generated by
  the old and new machine respectively that will make her a winner:
  <0,0>, <0,1>, <0,2>, <0,3>, <1,0>, <1,1>, <1,2>, <1,3>, <2,0> and
  <2,1>. Notice that <0,1> is not the same as <1,0>. Also, although the
  pair <2, 2> could be generated by the machines it wouldn't make
  Catalina win since (2 AND 2) = 2 and she only bought the numbers 0 and
  1.

Here's the link for actual problem: https://code.google.com/codejam/contest/2994486/dashboard#s=p1

This is code-golf, so shortest code wins.
Good Luck

Ruby, 107

I expected this would be a much shorter program.

gets
loop{a,b,k=gets.split.map &:to_i
puts"Case ##{$.-1}: #{[*0...a].product([*0...b]).count{|x,y|x&y<k}}"}

Explanation

The first line of input can be ignored.
$. is the last read line number.
[*0...x] is a quick way to turn the Range into an Array. It uses the splat operator (*). Note that the Range is an exclusive one (... instead of ..).
Array#count takes a block. It will only count the elements for which the block returns a truthy value.


Creating Distinct Sums You should write a program or function which receives an integers as input and outputs or returns two integers whose sum is the first one.

There is one further requirement: no number can be part of the output for two different inputs.

Details

You should be able to handle inputs for at least the range -32768 .. 32767 (inclusive).
If your datatype can't handle arbitrary whole numbers, that is fine but your algorithm should work for arbitrary large and small numbers in theory.

Examples

Each block shows a part of a correct or incorrect solution in the format of input => output.

1 => 6 -5
2 => -2 4
15 => 20 -5

Incorrect, as `-5` is used in two outputs.

-5 => -15 10
0 => 0 0
1 => 5 6
2 => -5 7

Incorrect, as `5 + 6` isn't `1`.

-1 => -1 0
0 => 6 -6
2 => 1 1

Can be correct if other outputs doesn't collide.

This is code golf so the shortest entry wins.

Pyth, 8 bytes

_J^Q3+QJ

Demonstration. Equivalent to the Python 2 code:

Q=input()
J=Q**3
print -J
print Q+J

So, the output has form (-n**3, n+n**3)

Some outputs:

-5 (125, -130)
-4 (64, -68)
-3 (27, -30)
-2 (8, -10)
-1 (1, -2)
 0 (0, 0)
 1 (-1, 2)
 2 (-8, 10)
 3 (-27, 30)
 4 (-64, 68)
 5 (-125, 130)

These are distinct because cubes are far enough spaced that adding n to n**3 is not enough to cross the gap to the next cube :n**3 < n+n**3 < (n+1)**3 for positive n, and symmetrically for negative n.


Tips for golfing in Mini-Flak What general tips do you have for golfing in Mini-Flak? I'm looking for ideas which can be applied to code-golf problems and which are also at least somewhat specific to Mini-Flak (e.g. "remove comments" is not an answer).

Please post one tip per answer.

Mini-Flak is just Brain-flak without [], <...> or <> so tips for Mini-Flak are different for a large amount of problems. However the use of brackets like [...] are allowed.

Zero efficiently

The <...> from Brain-flak is missing so it is often required that you replace it with something else.

The two following snippets do just that:

(...)[{}]
[(...)]{}

However when you are zeroing it is important to select these properly, because there is a lot of golfing that can be done that can't be done with Brain-Flak's zeros.  For example the following Brain-Flak code:

({}[()]<({}())>)

Could be reconstituted as

({}[()](({}()))[{}])

However it is cheaper to do

({}[()(({}()))]{})

You should try to combine your negative with as many other negatives in the scope as possible.


Tension on a Graph, Part I: A Wavy String Let's plot a function f(x) = sin(πx) + 0.5 sin(3πx) over the domain [-3,3]. We can interpret this as a loose string lying on a board. Now let's drive n nails into the board at positions (x1, y1) to (xn, yn), where the xi ∈ (-3,3) and yi ∈ [-1,1]. Imagine that there are two eyelets at the end of the string, that is at positions (-3,0) and (3,0). We can now take the ends of string and pull the through the eyelets until the string is taut. This will deform our graph into a piecewise linear function.

Some pictures might help. Take 8 nails at (-2.8, -0.7), (-2.5, -0.9), (-1.2, .2), (-0.5, .8), (0.5, .4), (1.2, -0.9), (1.5, -0.6), (1.8, -0.8). The following three plots show the process described above:

For larger version: Right-click --> Open in new tab

And here is an animation of the string tightening if you have some difficulty visualising it:

The Challenge

Given a list of "nails" (which is not necessarily sorted), plot those nails and the taut string if it starts from the shape of the above function f.

You may write a program or function and take input via STDIN, ARGV or function argument. You can either display the result on the screen or save an image to a file.

If the result is rasterised, it needs to be at least 300 pixels wide and 100 pixels tall. The coordinate range from (-3,-1.1) to (3,1.1) must cover at least 75% of the horizontal and vertical extent of the image. The length scales of x and y do not have to be the same. You need to show the nails (using at least 3x3 pixels) and the string (at least 1 pixel wide). You may or may not include the axes.

Colours are your choice, but you need at least two distinguishable colours: one for the background and one for the nails and the string (those may have different colours though).

You may assume that all nails are at least 10-5 units away from f (so that you don't need to worry about floating-point inaccuracy).

This is code golf, so the shortest answer (in bytes) wins.

More Examples

Here are two more (simpler) examples:

{{-2.5, 1}, {-1.5, -1}, {-0.5, 1}, {0.5, -1}, {1.5, 1}, {2.5, -1}}

(The string coincides with the x-axis.)

{{-2.7, -0.5}, {-2.3, -0.5}, {-1.7, 0.5}, {-1.3, 0.5}, {-0.7, -0.5}, {-0.3, -0.5}, {0.5, 1}, {1.5, -1}, {2.5, 1}}

Want another Challenge?

Here is Part II!

Python + Pycairo, 727 708 608, + PyLab, 383
from pylab import*
def f(N):
 def P(u,w,N):
    T=lambda v,p:(C(v-u,p-u)>0)==(C(w-v,p-v)>0)==(C(u-w,p-w)>0);M=[(i,n)for i,n in enumerate(N)if T(V([n[0],sin(pi*n[0])+sin(3*pi*n[0])/2]),n)]
    if M:i,n=max(M,key=lambda n:C(n[1]-u,w-u)**2);M=P(u,n,N[:i])+[n]+P(n,w,N[i+1:])
    return M
 V=array;C=cross;a=V([3,0]);plot(*zip(*([-a]+P(-a,a,map(V,sorted(N)))+[a])));N and scatter(*zip(*N));show()

Example
f([(-2.8,-0.7),(-2.5,-0.9),(-1.2,0.2),(-0.5,0.8),(0.5,0.4),(1.2,-0.9),(1.5, -0.6),(1.8, -0.8)])

How it works

 Suppose we know that the taut string passes through two points A and
 B (we can always start with  A = (-3, 0) and B = (3, 0).) As we pull the string, it "wants" to take the shortest path possible between
 A and B, that is, ideally, the segment AB. However, if there are any nails in the area bounded by the function (sin πx + ...)
 and AB, then at least one of them must block the string. In
 particular, the nail(s) farthest away from AB within the said area
 must block the string. Hence, if C is this nail, we know that the
 taut string must pass through C, in addition to A and B. We can
 now repeat the process for the segments AC and CB, and continue in
 this fashion until eventually there are no more intervening nails.

 This is a binary divide-and-conquer algorithm with a linear scan in
 each step, so it has a best-case complexity of O(n log n) and
 worst-case complexity of O(n2).