JavaScript (ES6), 225

A function with a string parameter, no input from file. I asked OP if this could be valid.

Test running the snippet in an EcmaScript 6 compliant browser (implementing arrow functions, template string, spread operator - Firefox, maybe Safari or MS Edge, not Chrome)

f=t=>t.split`
`.map(w=>(d[k=w.replace(/\W/g,'').toLowerCase()]={},k),d={},r=[]).map(w=>[...w].map((c,i,v)=>(d[v[i]='',x=v.join``]&&!d[x][w]&&r.push(d[x][w]=(v[i]=`(${c})`,v.join``)),v[i]=c)))&&r.sort((a,b)=>a.length-b.length)

// LESS GOLFED

Q=t=>{
  // convert to canonical form and put in a dictionary
  // each value in the dictionary is an hashtable tha will store the list
  // of words that can generate the current word, removing a letter
  d={},
  t=t.split`\n`.map(w=>(k=w.replace(/\W/g,'').toLowerCase(),d[k]={},k))
  r=[], // result array
  t.forEach(w =>
    [...w].forEach((c,i,v)=>( // for each letter in word, try to remove
      v[i]='', x=v.join``, // build string with missing letter
      v[i]='('+c+')', y=v.join``, // and build string with brackets
      v[i]=c, // restore the current letter
      d[x] && // if the word with removed letter is present in the dictionary
      !d[x][w] && // and not already from the same generating word
         r.push(d[x][w]=y) // update dictionary and add word to result array
    ))
  )
  return r.sort((a,b)=>a.length-b.length) // sort result by length
}

// TEST
function test() { R.innerHTML=f(I.value) }
textarea { height: 20em }
Test <button onclick="test()">-></button>

<textarea id=I>cat
cart
code
golf
node
scraped
scrapped
verify
versify
mart
mar
mat
ma</textarea>


CJam, 139 bytes

Well this took many hours to come to something that feels done. It feels like the time it takes to aggressively optimize CJam code is something larger than O(n) with respect to the size of the code...

You can try it online, but for any input for which the best path is at least 6 operations or so, you should probably try it offline with a faster interpreter.

Squished:

q_'$-_'^-:T;'^#\'^-'$#W{)2$5Y$5b+{:D[L"_T<W%_N#)_@>N+N#X-Ue>+-"_"W%-U"--2'<t2'>t'++'(')]=~0e>T,e<D3/1$T<N\+W%N#X?:X;}/2$-}g5b{" ^v<>"=}%]W=

Expanded and commented:

q               "Read the input";
_'$-            "Remove the end marker";
_'^-:T;         "Remove the start marker and save the text";
'^#             "With only the end marker removed, locate the start marker";
\'^-'$#         "With only the start marker removed, locate the end marker";
W               "Initialize the path number to -1";
{               "Do...";
  )               "Increment the path number";
  2$              "Initialize the cursor position to that of the start marker";
  5Y$5b+          "Convert the path number to base 5, then add a leading 5
                   (the leading 5 will act to initialize the column memory)";
  {:D             "For each digit in the path digit string:";
    [               "Begin cases:";
      L               "0: Do nothing";
      "_T<W%_N#)_@>N+N#X-Ue>+-"
"REFS: [   1   ][  2  ][ 3 ]45
                       1: [1] Calculate the distance to the end of the previous
                              line (0 if no such line)
                          [2] Calculate the length of the previous line (0 if
                              no such line)
                          [3] Calculate the distance to move backwards in the
                              previous line as the maximum of the length of the
                              previous line minus the column memory and 0
                          [4] Calculate the total distance to move as the sum
                              of [1] and [3]
                          [5] Subtract [4] from the cursor position";
      _"W%-U"-        "2: Start with a base of the logic of case 1, but with a
                          few operations adjusted.";
      -2'<t2'>t       "   [1] Calculate the distance to the *start* of the
                              *next* line (0 if no such line)
                          [2] Calculate the length of the *next* line (0 if no
                              such line)
                          [3] Calculate the distance to move *forwards* in the
                              *next* line as the *minimum* of the length of the
                              *next line* and *the column memory*
                          [4] Calculate the total distance to move as the sum
                              of [1] and [3]";
      '++             "   [5] *Add* [4] *to* the cursor position";
      '(              "3: Decrement the cursor position";
      ')              "4: Increment the cursor position";
    ]=~             "Execute the case corresponding to the path digit mod 5";
    0e>T,e<         "Clamp the cursor position to [0, text length]";
    D3/             "Check if the path digit is not 0, 1, or 2...";
    1$T<N\+W%N#     "Calculate the current column";
    X?:X;           "If the above check succeeded, update the column memory";
  }/              "End for each";
  2$-             "Subtract the end marker position from the cursor position";
}g              "... While the above subtraction is nonzero";
5b              "Convert the path number to base 5";
{" ^v<>"=}%     "Map each digit in the path string to its operation symbol";
]W=             "Clean up";

Overall, this is a pretty straightforward solution. It "executes" the digits of the base-5 representation of a path number that is incremented every iteration, starting with 0, until a path works. The digits 1-4 map to the operations up, down, left, and right, and 0 does nothing. The first iteration using a path of just 0 catches the degenerate case. All other paths that contain a 0 are never selected because they're just versions of already-tested paths with added no-ops.

The state is modeled in as minimalistic of a way as possible: the text with start and end markers removed, the cursor position in the text, and the "column memory." Newlines are mostly treated like any other character, so there's no concept of a row, and the cursor position is just an index. This makes moving left and right dead simple, which are just implemented as decrement and increment (with clamping to the size of the text). Moving up and down is a bit trickier, but still manageable.

Code reuse was a pretty vital optimization tactic. Examples of this include:

Writing the code for moving up in a way such that it's smaller to generate the code for moving down at runtime than to write its own code. This is done by copying the code for moving up and removing/replacing a few characters.
Updating the "column memory" is done conditionally based on the path digit divided by 3 instead of it being coded into the logic of the operation. This also allows initialization of the column memory by adding a dummy 5 operation to the start of the path string, which also just so happens to use the 0 no-op logic due to circular array indexing and there being only 5 defined operations.

Overall, I'm very happy with how this came out. This is definitely the most work I've put into a code golf answer to date (for something that fits into a tweet!?). The run time is pretty abysmal, though. CJam isn't exactly the fastest language to begin with and this algorithm has a complexity of something like O(m*5n), where m is the size of the input and n is the size of the output. Good thing speed doesn't count!


Remove the mininum sum seam from an array

Haskell, 187 bytes

l=length
f a@(b:c)=snd$maximum$(zip=<<map(sum.concat))$map(zipWith((uncurry((.drop 1).(++)).).flip splitAt)a)$iterate((\e@(f:_)->[f-1:e,f:e,min(f+1)(l b-1):e])=<<)[[y]|y<-[0..l b-1]]!!l c

Usage example:

*Main> f [[1,4,3,5,2],[3,2,5,2,3],[5,2,4,2,1]]
[[4,3,5,2],[3,5,2,3],[5,4,2,1]]

*Main> f [[1],[2],[3]]
[[],[],[]]

*Main> f [[1,2,3,4,5]]
[[2,3,4,5]]

How it works, short version: build a list of all paths (1), per path: remove corresponding elements (2) and sum all remaining elements (3). Take the rectangle with the largest sum (4).

Longer version:

Input parameters, assigned via pattern matching:
a = whole input, e.g. [[1,2,4],[2,5,6],[3,1,6]]
b = first line, e.g. [1,2,4]
c = all lines, except first, e.g. [[2,5,6],[3,1,6]]

Step (1), build all paths:

iterate((\e@(f:_)->[f-1:e,f:e,min(f+1)(l b-1):e])=<<)[[y]|y<-[0..l b-1]]!!l c

     [[y]|y<-[0..l b-1]]           # build a list of single element lists
                                   # for all numbers from 0 to length b - 1
                                   # e.g. [[0],[1],[2]] for a 3 column input.
                                   # These are all possible start points

     \e@(f:_)->[f-1:e,f:e,min(f+1)(l b-1):e]
                                   # expand a list of paths by replacing each
                                   # path with 3 new paths (up-left, up, up-right)

     (...)=<<                      # flatten the list of 3-new-path lists into
                                   # a single list

     iterate (...) [...] !! l c    # repeatedly apply the expand function to
                                   # the start list, all in all (length c) times.

Step (2), remove elements

map(zipWith((uncurry((.drop 1).(++)).).flip splitAt)a)

     (uncurry((.drop 1).(++)).).flip splitAt
                                   # point-free version of a function that removes
                                   # an element at index i from a list by
                                   # splitting it at index i, and joining the
                                   # first part with the tail of the second part

      map (zipWith (...) a) $ ...  # per path: zip the input list and the path with
                                   # the remove-at-index function. Now we have a list
                                   # of rectangles, each with a path removed

Step (3), sum remaining elements

zip=<<map(sum.concat)             # per rectangle: build a pair (s, rectangle)
                                  # where s is the sum of all elements

Step (4), take maximum

snd$maximum                      # find maximum and remove the sum part from the
                                 # pair, again.


Javascript ES6, 138 chars

Function, 139

Takes string as an argument and writes output to console:

f=s=>(r=0,s.replace(/(\d\d?):(\d\d)(:(\d\d))?/g,(m,a,b,x,c)=>r+=x?+c+b*60+a*3600:+b+a*60),console.log("%dh %dm %ds",r/3600,r%3600/60,r%60))

Program, 138

prompt(r=0).replace(/(\d\d?):(\d\d)(:(\d\d))?/g,(m,a,b,x,c)=>r+=x?+c+b*60+a*3600:+b+a*60),console.log("%dh %dm %ds",r/3600,r%3600/60,r%60)

Test for function

f("View the Welcome video.\n\
Video: 10:37 min.\n\
View the video introduction to the course.\n\
Video: 3:30 min. View the video of how to use the Lesson Overview.\n\
Video: 9:13 min.\n\
View the video overview of how to use the Epsilen system to share your work.\n\
Video: 03:15 min.\n\
View the video to learn about the State of Texas Assessment of Academic Readiness (STAAR).\n\
Video: 1:05:26 min.")

Output

"1h 32m 1s"


PCRE .NET, 35 32 bytes

-3 bytes thanks to Martin Ender

Rock:

([*?]$)

Paper:

[)$]$+

Scissors:

[+?]$.*

Lizard:

[+$]$.?

Spock:

[*)]$

The idea here is to match characters at the end of other regexes which are reserved regex characters, but stop being treated as such when inside a character class.


Python 3, 72 69 bytes

-3 bytes thanks to Jitse!

Input includes @gmail.com.

f=lambda s:s[11:]and[s[0]+w+x for x in f(s[1:])for w in('.','')]or[s]

Try it online!


Python, 214 bytes

S=sorted
def M(L,X):
 H=[-1,0];R={}
 for a,b in S(L):
    while H[2:]and a*H[-3]+b>H[-2]*H[-3]+H[-1]:H=H[:-3]
    H+=[1.*(H[-1]-b)/(a-H[-2]),a,b]
 for x in S(X):
    while H[2:]and x>H[2]:H=H[3:]
    R[x]=H[0]*x+H[1]
 return R

Computes the convex hull by iterating through the input a,b in increasing a order.  The convex hull is recorded in H using the format -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bn where xi is the x coordinate of the intersection of a{i-1},b{i-1} and ai,bi.

Then I iterate though the input xs in sorted order, truncating the convex hull to keep up as I go.

Everything is linear except for the sorts which are O(n lgn).

Run it like:

>>> print M([[2,8],[4,0],[2,1],[1,10],[3,3],[0,4]], [1,2,3,4,5])
{1: 11, 2: 12, 3: 14, 4: 16, 5: 20}


J, 4 bytes

#@C.

This assumes that the permutation is 0-based. It uses the builtin C. which given a list representing a direct permutation outputs a list of cycles. Then # composed @ on that returns the number of cycles in that list.

Try it here.


Jelly, 4 bytes

ØDœc

Try it online!

Explanation

ØDœc  Double-builtin; main link
  œc  Number of combinations of          of length
ØD                              [digits]
                                                   <right argument>

Behavior for n > 10 is empty list.


Know your auto-assigning variables!

Jolf has many ways to "auto assign" variables. The standard one is γ, which takes the value of the next expression. Β is the same thing, but converts the next expression to a number.

Also, ζ (zeta) is a variable initialized to -1/12 (guess why), and can be re-assigned with Ζ (Zeta).

For example, let's say you want to compare I (the input string) to an operation over itself. For now, let's see if I + I = reverse(I + I). This is written as, conventionally:

=+II_+II

But this can be golfed down to:

=γ+II_γ


JavaScript (ES6), 79 70 bytes

a=>a.map(([s,f])=>"AA#BCC#DD#EFF#GG#".match(/.#?/g)[(s*7+(s>2)+f)%12])

Requires 1-based strings. Edit: Saved 9 bytes by directly calculating the string to fret conversion, based on @nimi's old answer.


JavaScript (ES6),  98  97 bytes
Returns an array [lenited, eclipsed].
s=>[(x=[...'2n1111gbnd1m1','bh',2][parseInt(c=s[0],30)*17%22])>'1'?c+'h'+s.slice(1):s,x>{}?x+s:s]

Try it online!
How?
We define the following lookup table:
A = [ ...'2n1111gbnd1m1', 'bh', 2 ]

//     0    1    2    3    4    5    6    7    8    9    10   11   12   13  14
A = [ '2', 'n', '1', '1', '1', '1', 'g', 'b', 'n', 'd', '1', 'm', '1', 'bh', 2 ]

where:

a single character (or the string "bh") is used for eclipsis; all letters that trigger eclipsis also trigger lenition
\$1\$ means that there's no eclipsis and no lenition
\$2\$ means that there's no eclipsis but there is lenition

The first letter of the input word is converted from Base30 to decimal, multiplied by \$17\$ and then reduced with a modulo \$22\$. The result is used to pick the correct value from \$A\$.
Any result above \$14\$ yields undefined, and so does any letter in the range u-z or any fada vowel. An undefined value is interpreted the same way as \$1\$ (no eclipsis, no lenition).
  1st letter | from Base30 | * 17 | mod 22 | A[n]
-------------+-------------+------+--------+-----------
      a      |      10     |  170 |   16   | undefined
      b      |      11     |  187 |   11   | 'm'
      c      |      12     |  204 |    6   | 'g'
      d      |      13     |  221 |    1   | 'n'
      e      |      14     |  238 |   18   | undefined
      f      |      15     |  255 |   13   | 'bh'
      g      |      16     |  272 |    8   | 'n'
      h      |      17     |  289 |    3   | '1'
      i      |      18     |  306 |   20   | undefined
      j      |      19     |  323 |   15   | undefined
      k      |      20     |  340 |   10   | '1'
      l      |      21     |  357 |    5   | '1'
      m      |      22     |  374 |    0   | '2'
      n      |      23     |  391 |   17   | undefined
      o      |      24     |  408 |   12   | '1'
      p      |      25     |  425 |    7   | 'b'
      q      |      26     |  442 |    2   | '1'
      r      |      27     |  459 |   19   | undefined
      s      |      28     |  476 |   14   | 2
      t      |      29     |  493 |    9   | 'd'
 u-z or fada |     NaN     |  NaN |  NaN   | undefined


New Order #5: where Fibonacci and Beatty meet at Wythoff

R, 143 130 124 123 bytes

function(n){k=0:n+1
`~`=rbind
m=k-1~(k*(1+5^.5)/2)%/%1
for(i in k)m=m~m[i,]+m[i+1,]
m=m[-1:-2,]
m[order(row(m)+col(m))][n]}

Try it online!

Uses the formula \$T(n,-1)=n-1; T(n,0)=\lfloor n\cdot\phi\rfloor;T(n,k)=T(n,k-1)+T(n,k-2)\$ to construct the array (transposed), then splits the array along antidiagonals. k merely exists to prevent forcing a drop=F argument in m[-1:-2,] for the case n=1.

Thanks to Neil for pointing out a 1 byte golf.

R, 150 138 132 bytes

function(n){T[2]=1
for(j in 2:n-1)T=c(T,T[j]+T[j+1])
m=T[-1]%o%((1:n*(.5+5^.5/2))%/%1)+T[-1-n]%o%(1:n-1)
m[order(row(m)+col(m))][n]}

Try it online!

Implements the formula \$T(n,k)=Fib(k+1)\cdot\lfloor n\cdot\phi\rfloor+Fib(k)\cdot(n-1)\$ to get generate the array, then splits along the antidiagonals and extracts the nth element.

Thanks to Robin Ryder for the T[2]=1 trick for generating the Fibonacci sequence.

Both solutions are highly inefficient, creating an nxn matrix of (most likely) doubles, as R promotes integer (32-bit signed) to double automatically when overflowing, but the second one should be quite a lot faster. Taking n as a bignum should work automatically, using the call gmp::as.bigz(n), should loss of precision under doubles be worrisome, and then the language would be R + gmp.


Add the Fibonnaci Sequence to the Lucas Sequence


Python, 83

The anonymous function on the 2nd line is my solution.

f=lambda l,i=0:sorted(f(l,j+1)for j,e in enumerate(l)if e==i)
lambda a,b:f(a)==f(b)

f returns a canonized form of a subtree which is a sorted list of its canonized children.  Then we must simply check if the canonized forms of each tree are equal.


Ruby, 32 28 23 bytes

->n,k{k.step(0,-n).sum}

Try it online!

Explanation

Let's visualize the sum as the area of a triangle, for example with n=3 and k=10:

*
*
*
**
**
**
***
***
***
****

Then we sum by column instead of row: the first column is k, then k-n, k-2n and so on.


Solve Any Motion Physics Problem (Equations Supplied)

Maple, 41 chars

s:=i->solve({v=u+a*t,s=(u+v)*t/2,op(i)}):

(Formulas used: #1 and #3.  These are sufficient to let Maple derive the rest.)

This defines a function s that takes in a set of initial conditions and solves the equations of motion for those initial values.  For example, the command:

> s({ u = 1, v = 2, t = 3 });

outputs:

                          {a = 1/3, s = 9/2, t = 3, u = 1, v = 2}

Notes:

You generally need to specify three initial values for a unique solution; if you don't provide enough, Maple will try to give you a partial solution:

> s({ u = 1, v = 2 });

                                        3 t
                          {a = 1/t, s = ---, t = t, u = 1, v = 2}
                                         2

(Yes, that's an ASCII art fraction there.  Even in text mode, Maple tries to typeset your math nicely.)

No solution is return for overspecified or otherwise unsolvable inputs; for example, s({ u = 1, v = 2, t = 0 }); outputs nothing.

If multiple solutions exist, Maple will generally try to return all of them:

> s({ u = 1, s = 0, a = -1 });

                          {a = -1, s = 0, t = 2, u = 1, v = -1},
                          {a = -1, s = 0, t = 0, u = 1, v = 1}

Sometimes, the output may contain RootOf() expressions, as in:

> s({ u = 10, s = 1, a = -1 });
                                                         2
                {a = -1, s = 1, t = RootOf(2 - 20 _Z + _Z , label = _L3), u = 10,
                                               2
                 v = 10 - RootOf(2 - 20 _Z + _Z , label = _L3)}

As far as Maple's concerned, this is a perfectly good solution, but if you want to turn it into something readable for us mere humans, use allvalues():

> allvalues(s({ u = 10, s = 1, a = -1 }));
                                            1/2                 1/2
                {a = -1, s = 1, t = 10 - 7 2   , u = 10, v = 7 2   },
                                            1/2                  1/2
                {a = -1, s = 1, t = 10 + 7 2   , u = 10, v = -7 2   }

Alternatively, you can specify the initial conditions as floating-point values, e.g. u = 10.0, which will cause Maple to return purely numerical solutions instead:

> s({ u = 10.0, s = 1, a = -1 });

                {a = -1., s = 1., t = 0.1005050634, u = 10., v = 9.899494937},
                {a = -1., s = 1., t = 19.89949494, u = 10., v = -9.899494937}

Finally, note that, since Maple is a computer algebra system, it allows you to specify arbitrary equations in the input.  For example, if we didn't care about the specific initial velocity, but only about the change in velocity, we could just specify e.g. v = u + 1 and get the partial solution:

> s({ v = u + 1 });

                {a = 1/t, s = t v - 1/2 t, t = t, u = v - 1, v = v}

We can even extend the physics model if we want, as in:

> s({ f = m * a, u = 0, f = 1, m = 10, t = 5 });

                {a = 1/10, f = 1, m = 10, s = 5/4, t = 5, u = 0, v = 1/2}


Python 2, 104 94 83 bytes

-10 bytes thanks to Mr. Xcoder
-11 bytes thanks to Jonathan Allan

i=0
while 1:
 if`i`==''.join(d*int(d)for c,d in zip(`-i`,`i`)if d!=c):print i
 i+=1

Try it online!


Python 3.8 (pre-release), 253 244 bytes

from itertools import*
f=lambda b,h,w:all(set(t:=[i%w+i//w*1jfor i,e in enumerate(b)if e])&set(s:=[*map(sum,zip(t,T))])or~any(abs(a-b)<2for a,b in combinations(s,2))+all(h>a.imag>-1<a.real<w for a in s)for T in product(*[[1,1j,-1,-1j]]*sum(b)))

Try it online!
-6 bytes thanks to @user202729 (chain comparisons)
-3 bytes thanks to @ovs (1jfor; …or a+1^b → …or~a+b for "implies" boolean operator)
# Itertools for combinations and product
from itertools import*
f=lambda b,h,w: all(
    # Test if a given set of tent position deltas works:
    # Positions are complex numbers: real part increasing to the right, imaginary part increasing down
    # (De Morgan shortened, so many expressions negated)
        # No tree is on a tent:
            # t:=Tree positions (1s)
            set(t:=[i%w+i//w*1j for i,e in enumerate(b)if e])
            # s:=Tent positions as sum of tree positions and deltas
            & set(s:=[*map(sum,zip(t,T))])
        # and difference between all distinct pairs oftrees is at least 2:
            or any(abs(a-b)<2for a,b in combinations(s,2))
        # and all trees are within rectangular boundary
            # (Using Python 2's quirky complex floordiv doesn't work since those return complex nums,
            # which don't have a total order.
            # Plus Python 38 has saves so much here; using 2 would be a waste anyway)
            >= all(h > a.imag > -1 < a.real < w for a in s)
    # For each possible delta (four directions, distance 1)
    # sum(b) is the number of tents since each tent contributes 1
    for T in product(*[[1,1j,-1,-1j]]*sum(b))
)


Evaluate the Riemann Zeta Function at a Complex Number

Python - 385

This is a straightforward implementation of Equation 21 from http://mathworld.wolfram.com/RiemannZetaFunction.html This uses Python's convention for optional arguments; if you want to specify a precision, you can pass a third argument to the function, otherwise it uses 1e-24 by default.

import numpy as N
def z(r,i,E=1e-24):
 R=0;I=0;n=0;
 while(True):
  a=0;b=0;m=2**(-n-1)
  for k in range(0,n+1):
   M=(-1)**k*N.product([x/(x-(n-k))for x in range(n-k+1,n+1)]);A=(k+1)**-r;t=-i*N.log(k+1);a+=M*A*N.cos(t);b+=M*A*N.sin(t)
  a*=m;b*=m;R+=a;I+=b;n+=1
  if a*a+b*b<E:break
 A=2**(1-r);t=-i*N.log(2);a=1-A*N.cos(t);b=-A*N.sin(t);d=a*a+b*b;a=a/d;b=-b/d
 print(R*a-I*b,R*b+I*a)


Like this?

PHP, 28 22

for(;;)echo rand(0,1);

For a better view:

<div style="width:800px;margin:0 auto;background-color:black;color:green;">
    <?php for(;;)echo rand(0,1); ?>
</div>


Python 3.5+, 77 46 44 41 bytes

lambda s:[a*s.count(a)for a in{*s}-{' '}]

Pretty simple. Goes through the unique characters in the string by converting it to a set (using Python 3.5's extended iterable unpacking), then uses a list comprehension to construct the exploded diagrams by counting the number of times each character occurs in the string with str.count. We filter out spaces by removing them from the set.

The order of the output may vary from run to run; sets are unordered, so the order in which their items are processed, and thus this answer outputs, cannot be guaranteed.

This is a lambda expression; to use it, prefix lambda with f=.

Try it on Ideone! Ideone uses Python 3.4, which isn't sufficient.

Usage example:

>>> f=lambda s:[a*s.count(a)for a in{*s}-{' '}]
>>> f('Ah, abracadabra!')
[',', 'A', 'aaaaa', 'd', '!', 'bb', 'h', 'c', 'rr']

Saved 3 bytes thanks to @shooqie!


Python 3, 261 bytes

lambda x,o="&",y="":("any"in x+y)*(o<"|")*-~-("never"in x+y)*"any"or(lambda r:r==31and"any"or"|".join("ubsnnnotuudormleliblfene iagr nn   e    d"[i::5]for i in range(5)if r&2**i)or"never")(eval(o.join(str(min(31,2**"dormlyv".find(k[2])%64))for k in[x,y or x])))

Try it online!
-1 byet thanks to ovs


Retina 0.8.2, 68 bytes (UTF-8)

\d+(.[ャュョ]?)
$1/$&$*1\
/1\b

/.
/
+`1(1*.)(.[ャュョ]?)
$2$1

Try it online! Link includes test cases. Explanation:

\d+(.[ャュョ]?)
$1/$&$*1\

Convert the number to unary, wrap it in /\, and insert it after the first mora.

/1\b

If the number was 1, then delete it and the /, leaving the \.

/.
/

Subtract 1 from the number, but in the case of 0, this deletes the \, leaving the /.

+`1(1*.)(.[ャュョ]?)
$2$1

Move the \ one mora to the right for each remaining 1.


Polyglot "Hello world" in Fortran and Lisp

Fortran (GFortran) -ffixed-form, 183 53+12=65 bytes

	;print*,"Hello world!"
	;end
*(print "Hello world!")

Try it online!

Common Lisp, 53 bytes

Try it online!


Longest word using a single row of the qwerty keyboard

Python 2, 84 bytes

lambda l:max(l,key=lambda w:(-len({"asdfghjklzxcvbnm".find(c)/9for c in w}),len(w)))

Finds the max of the input, comparing by fewer keyboard rows spanned, then in increasing length. The keyboard row value is extracted by "asdfghjklzxcvbnm".find(c)/9, which takes the middle row to 0, the bottom row to 1, and the top row, which is excluded, to -1, since find gives -1 for missing values.
Other attempts:
lambda l:max((-len({"asdfghjklzxcvbnm".find(c)/9for c in w}),len(w),w)for w in l)[2]
lambda l:max(l,key=lambda w:len(w)-1./len({"asdfghjklzxcvbnm".find(c)/9for c in w}))
lambda l:max([w for w in l if len({"asdfghjklzxcvbnm".find(c)/9for c in w})<2],key=len)


Generate a random point outside a given rectangle within a map

Python 2, 114 106 102 101 bytes

lambda w,h,X,Y,W,H:choice([(i%w,i/w)for i in range(w*h)if(W>i%w-X>-1<i/w-Y<H)<1])
from random import*

Try it online!


Solving variants of the blue-eyes puzzle

Python 2, 60 48 bytes

f=lambda b,r,c:all(map(eval,c))and-~f(b-1,r+1,c)

Try it online!

How it works

By induction:

If the island composition is (b, r) and it is known that (b − 1, r + 1) is not possible, then on day 1, the blue-eyed islanders, seeing (b − 1, r), will conclude that they are blue-eyed and leave.
If the island composition is (b, r) and it is known that the blue-eyed islanders would have left on day n if the composition were (b − 1, r + 1), then on day n + 1, the blue-eyed islanders, seeing (b − 1, r), will conclude that they are blue-eyed and leave.

This second inference fails if b = 1, but in that case, the blue-eyed islander would never leave if they hadn’t already, and the test case would be invalid.

Note that non-blue-eyed islanders will never leave, in this version of the puzzle, because even if they use similar logic to conclude that they are not blue-eyed, they still don’t know which non-blue color their eyes are.


05AB1E, 26 bytes

2ÝD5+«v4Fy',N·yÉ+„bry3‹èJ,

Try it online!

Explanation

2Ý                           # push [0,1,2]
  D5+                        # duplicate and add 5: [5,6,7]
     «                       # concatenate
      v                      # for each y in [0,1,2,5,6,7] do:
       4F                    # for each N in [0 ... 3] do:
         y                   # push y
          ',                 # push ","
            N·yÉ+            # push N*2+isOdd(y)
                 „br         # push "br"
                    y3‹è     # index into the string with y<3
                        J,   # join everything to a string and print


Given a string, Return its Cumulative Delta

Python 3, 71 bytes

s=input();k=r=0
for c in s:r=ord(c)-r*k/(len(s)-k);k+=1
print(round(r))

Test it on Ideone.

Alternate version, 58 bytes (inexact)

If an approximate result is enough – e.g., -904.9999999999993 ≈ -905 for input helloworld – then the following solution works as well.

f=lambda s,k=1:len(s)and-~-len(s)*f(s[1:],k+1)/k+ord(s[0])

Test it on Ideone.

Background

Proposition Let f be a variadic function that maps the code points s0, ⋯, sn to their cumulative delta with sign (-1)n, i.e.,

Then

Proof The statement is clearly true when n = 0. Suppose that it holds for n - 1, where n > 0.

By the recursive definition of f and the hypothesis,

By induction, the statement holds for all non-negative values of n.

How it works

Since

we can rewrite the proposition as follows.

The iterative implementation does precisely this. Numerators are computed by incrementing k, denominators by subtracting k from the length of the input string s, i.e., n+1.

Unfortunately, not all fractions will evaluate to integers, so the result is computed using floating point arithmetic and finally rounded to the nearest integer.

The recursive implementation does roughly the same, but it keeps track of the denominator via the auxiliary variable k and computes the numerator by subtracting 1 from the length of the remaining string (~-len(s)).


Haskell, 1068 1042 1012 bytes

-30, mostly from replacing if/then with guards. I'm sure it can be golfed more.

data W=W[W]Int deriving Show
f EQ y=y
f x _=x
m=1<0
k=1>0
[]#[]=EQ
[]#_=LT
_#[]=GT
(W x y:z)#(W a b:d)=f(x#a)$f(compare y b)$z#d
x?y=x#y>EQ
b x=break(\(W y _)->y#x/=GT)
x&[]=x
d&(x@(W v w):u)=case b v d of(y,W f m:_)|f#v>LT->y++(W v$m+w):u;(y,_)->y++x:u
x![]=x
d!(W v w:u)=case b v d of(_:_,_)->d;(_,W f m:g)->if w<m then(W f$m-w):g else g!u
[]%_=([],k)
x@(W g h:d)%b@(W e f:_)|b?x=([],m)|g!e?[]=(\(q,r)->([W(g!e)h]&q,r))$d%b|k=(\q->(q,(foldl(&)[]$t b<$>q)#x==EQ))[W[]$div h f]
t(W x y:z)(W[]n)=(W x$y*n):z
t(W x _:_)(W b n)=[W(x&b)n]
l=all(\(W e _)->e?[])
q=max
o[]=0
o(W e n:u)=q n$q(o e)$o u
v[]=0
v(W e n:u)=q(1+length u)$q(v e)$v u
d[]=0
d(W e n:u)=q(1+d e)$d u
e(W x _:[])(W y _:_)=x?y
e(_:x)y=e x y
g _ 0_ n=[[W[]x]|x<-[1..n]]
g m d s n|p<-g m(d-1)s n=fst$h s$filter(m?)$p++[[W x y]|x<-p,y<-[1..n]]
h 1z=(z,z)
h n z|(a,p)<-h(n-1)z,n<-[x++y|x<-z,y<-p,e x y]=(a++n,n)
r x=p x$g x(d x)(v x)$o x
p _[]="p"
p x(y:z)|(q,r)<-x%y,x?y&&x?q&&r&&(l y||not(l y&&l q||d y<2&&d q<2)||y#q<GT)=show y++"*"++show q|k=p x z

Try it online!

Or try a version that pretty-prints the inputs and outputs.

Input Format

The input format is Cantor normal form, written as \$\omega ^{\beta _{1}}c_{1}+\omega ^{\beta _{2}}c_{2}+\cdots+\omega ^{\beta _{k}}c_{k}\$, where \$k\$ is a natural number, \$ c_{1},c_{2},\ldots ,c_{k}\$ are positive integers, and \$ \beta _{1}>\beta _{2}>\ldots >\beta _{k}\geq 0 \$ are ordinal numbers.

Each term \$\omega ^{b}c\$ is written as W b c and terms are written as a list in [] separated by commas.

Examples:

[]\$ = 0\$

[W[]1]\$ = 1\$

[W[W[]1]1]\$ = \omega\$

[W[W[]1]1,W[]1]\$ = \omega + 1\$

[W[W[]2]3,W[]4] \$=\omega^2\cdot 3 + 4\$

[W[W[W[]2]1]1,W[]4] \$=\omega^{\omega^2} + 4\$

[W[W[W[]1]1,W[]1]1,W[]1]\$ = \omega^{\omega+1} + 1\$

Test Cases

Output from the main version:

[W [W [] 2] 1,W [] 1] => p
[W [W [W [] 1] 1] 1] => p
[W [W [W [W [] 1] 1] 1] 1] => p
[W [W [] 1] 1,W [] 100] => [W [] 2]*[W [W [] 1] 1,W [] 50]
[W [W [] 3] 1] => [W [W [] 1] 1]*[W [W [] 2] 1]
[W [W [W [] 1] 1,W [] 1] 1,W [] 2] => [W [] 2]*[W [W [W [] 1] 1,W [] 1] 1,W [] 1]
[W [W [W [] 1] 1,W [] 1] 1] => [W [W [W [] 1] 1] 1]*[W [W [] 1] 1]
[W [W [] 1] 2,W [] 1] => [W [W [] 1] 1,W [] 1]*[W [] 2]
[W [] 2903591] => [W [] 1699]*[W [] 1709]

Output from the pretty-print version:

[W [W [] 2] 1,W [] 1] == w^2 + 1 => p
[W [W [W [] 1] 1] 1] == w^w => p
[W [W [W [W [] 1] 1] 1] 1] == w^(w^w) => p
[W [W [] 1] 1,W [] 100] == w + 100 => (2)*(w + 50)
[W [W [] 3] 1] == w^3 => (w)*(w^2)
[W [W [W [] 1] 1,W [] 1] 1,W [] 2] == w^(w + 1) + 2 => (2)*(w^(w + 1) + 1)
[W [W [W [] 1] 1,W [] 1] 1] == w^(w + 1) => (w^w)*(w)
[W [W [] 1] 2,W [] 1] == w*2 + 1 => (w + 1)*(2)
[W [] 2903591] == 2903591 => (1699)*(1709)

Strategy

This is probably not the fastest solution, but I thought it might be relatively short for code golf. It works for all of the test cases and works well for natural numbers. For ordinals with many terms, this may take a very long time to run.

Generate a sequence of ordinals which may divide the input.
Test each ordinal in the sequence to determine whether it divides the input and meets the additional criteria. If it does, return a formatted string containing the divisor and quotient.
If the sequence was exhausted, return "p" for prime.

Implementation

I started with code I found online that implements ordinal addition and multiplication and uses the QuickCheck library to test that properties (theorems) are true for a large number of inputs.

I implemented left subtraction and then left division with remainder and verified that the operations were consistent with the following theorems.

Left subtraction: Let \$x\$ and \$y\$ be ordinals such that \$x \geq y\$. Then there exists a unique ordinal \$z\$ such that \$x = y + z\$.

Left division: Let \$x\$ and \$y\$ be ordinals. Suppose \$y\neq0\$. Then there exist unique ordinals \$z\$ and \$w\$ such that \$x=y\cdot z+w\$ and \$w < y\$.

Generated Sequences

To test whether an ordinal is prime, I generate a list of potential divisors. This would be easy for natural numbers, but infinite ordinals are greater than infinitely many ordinals.

I check the given ordinal to determine the depth, maximum number of terms (at each depth), and maximum coefficient.

I then recursively generate ordinals that are less than the given one and up to the given depth, term count, maximum coefficient. I don't have a proof that this is sufficient, but intuitively it seems like it would be.

Here are some examples.

Example 1: \$\omega^2\cdot 3 + 4\$. Depth: 2, Max term count: 2, Max coefficient: 4. Generated list of potential divisors, length 26: \$1, 2, \omega, \omega + 1, \omega + 2, \omega\cdot2, \omega\cdot2 + 1, \omega\cdot2 + 2, \omega^2, \omega^2 + 1, \omega^2 + 2, \omega^2 + \omega, \omega^2 + \omega + 1, \omega^2 + \omega + 2, \omega^2 + \omega\cdot2, \omega^2 + \omega\cdot2 + 1, \omega^2 + \omega\cdot2 + 2, \omega^2\cdot2, \omega^2\cdot2 + 1, \omega^2\cdot2 + 2, \omega^2\cdot2 + \omega, \omega^2\cdot2 + \omega + 1, \omega^2\cdot2 + \omega + 2, \omega^2\cdot2 + \omega\cdot2, \omega^2\cdot2 + \omega\cdot2 + 1, \omega^2\cdot2 + \omega\cdot2 + 2\$

Example 2: \$\omega^\omega\cdot3+4\$. Depth: 3, Max term count: 2, Max coefficient: 4. Generated terms list length: 151,994.
Since that list is generated lazily, the program still gives a fast answer.

As the depth and maximum term count increase, the lengths of the generated sequences increase very quickly.

Note

For the last given test case, \$\omega\cdot2+1=(\omega+1)\cdot2\$, I was unable to satisfy either of the two given additional criteria (\$_0\$ is a limit ordinal, \$_0 \leq r_1\$). However, I was able to satisfy the following criteria stated on Wikipedia, which is a slight variation of the given criteria:

Every limit prime occurs before every successor prime
If two consecutive primes of the prime factorization are both limits or both finite, then the second one is at most the first one.

If anyone is interested, I could provide a less golfed version of this code.


What is the reverse (binary) bit number?

Python, 29 bytes

lambda n:int(bin(n)[:1:-1],2)

Try it online!

This is an anonymous, unnamed function which returns the result.

First, bin(n) converts the argument to a binary string. We would ordinarily reverse this with the slice notation [::-1]. This reads the string with a step of -1, i.e. backwards. However, binary strings in Python are prefixed with an 0b, and therefore we give the slicing's second argument as 1, telling Python to read backwards terminating at index 1, thus not reading indexes 1 and 0.

Now that we have the backwards binary string, we pass it to int(...) with the second argument as 2. This reads the string as a base 2 integer, which is then implicity returned by the lambda expression.


Jelly, 3 bytes
o@\

Try it online!
How it works
o      Take the logical OR of its arguments.
 @     Reverse the argument order of the link to the left.
  \    Do a cumulative reduce, using the link to the left.


GS2, 2 bytes

Wd

Try it online!

How it works

W     Read all numbers.
      For input x, this executes map(int, re.findall(r'-?\d+', x)) internally.
 d    Compute their sum.


Brachylog (2), 4 bytes

ṇl₂ᵐ

Try it online!

Full program (because this is a decision-problem; Brachylog full programs output false. if there was an assertion failure, true. without one).

Explanation

ṇl₂ᵐ
ṇ     Split input into lines
   ᵐ  For each line:
 l₂     Assert that that line has length 2

Subscripts on l are one of Brachylog's newest features (although still older than the challenge), and this is a good challenge to use them on.


Husk, 12 14 15 bytes
+3 bytes for case [[1,1]]
Ṡḟȯ¬€Ṡ-uÖLṁȯtuQ

Try it online!
Explaination
          ṁ      -- map and concatenate
           ȯt    --   all but the first
             u   --   unique elements of
              Q  --   contiguous sublist
        ÖL       -- sort by length
Ṡḟ               -- find the first element satisfying this predicate
  ȯ¬€            --   not an element of
     Ṡ-          --   the list of sublists minus
       u         --   its unique elements

Note: Ṡ f g x = f (g x) x and this is hard to explain using the method above.


The making of "Spot It!": Finding almost unique sets

This should be a comment rather than an answer, but it's not going to fit in a comment.

One way of looking at this problem is to flip it around:

  Given that you have N distinct pictures, what's the largest deck of cards you can build each of which has n distinct pictures such that the intersection of any two cards is precisely one picture?

Another way of phrasing this flipped-round problem is:

  What is the maximal size of binary code of length N, constant weight n and exact pairwise Hamming distance 2(n-1)?

This is bounded by the maximal size of binary codes of length N, constant weight n, and minimal Hamming distance 2(n-1). The best resource for such bounds appears to be http://www.win.tue.nl/~aeb/codes/Andw.html although some values here are extracted from OEIS (specifically A001839).

 N \ n  0   1   2   3   4   5   6   7   8   9
 0      1   -   -   -   -   -   -   -   -   -
 1      1   1   -   -   -   -   -   -   -   -
 2      1   1   1   -   -   -   -   -   -   -
 3      1   1   3   1   -   -   -   -   -   -
 4      1   1   3   1   1   -   -   -   -   -
 5      1   1   4   2   1   1   -   -   -   -
 6      1   1   5   4   1   1   1   -   -   -
 7      1   1   6   7   2   1   1   1   -   -
 8      1   1   7   8   2   1   1   1   1   -
 9      1   1   8   12  3   2   1   1   1   1
 10     1   1   9   13  5   2   1   1   1   1
 11     1   1   10  17  6   2   2   1   1   1
 12     1   1   11  20  9   3   2   1   1   1
 13     1   1   12  26  13  3   2   2   1   1
 14     1   1   13  28  14  4   2   2   1   1
 15     1   1   14  35  15  6   3   2   2   1
 16     1   1   15  37  20  6   3   2   2   1
 17     1   1   16  44  20  7   3   2   2   2
 18     1   1   17  48  22  9   4   3   2   2
 19     1   1   18  57  25  12  4   3   2   2
 20     1   1   19  60  30  16  5   3   2   2
 21     1   1   20  70  31  21  7   3   3   2
 22     1   1   21  73  37  21  7   4   3   2
 23     1   1   22  83  40  23  8   4   3   2
 24     1   1   23  88  42  24  9   4   3   3
 25     1   1   24  100 50  30  10  5   3   3
 26     1   1   25  104 52  30  13  5   4   3
 27     1   1   26  117 54  31  14  6   4   3
 28     1   1   27  121 63  33  16  8   4   3
 29     1   1   28  134 65  ?   20  8   4   3
 30     1   1   29  140 ?   ?   25  9   5   4
 31     1   1   30  155 ?   ?   31  9   5   4
 32     1   1   31  160 ?   ?   31  10  5   4

There are some easy to prove properties, but from what I've read so far it seems that in general there's no better method known than brute force.

Note that for n > 2 these bounds appear to be loose for N > n^2 - n + 1 (certainly they are for the values of n in the table above), and tight for N <= n^2 - n + 1.

One useful result which handles the case that most interests you is as follows. (I could also write some code to wrap this up by using special cases and falling back to brute force, but I don't see the point).

  If N = n^2 - n + 1 then there is a nicely structured deck of N cards satisfying the required property.

The construction is quite simple:

(-1,-1) (x,0) (x,1) ... (x,n-2)                for x in 0..n-1
(0,y) (1,y+z % n-1) ... (n-1, y+(n-1)z % n-1)  for y in 0..n-2, z in 0..n-2

Each element appears in precisely n cards, which makes it optimal for decks in which more than one picture repeats.

Call the most frequent picture (selecting arbitrarily in case of a tie) f.

Lemma 1

  If f appears in more than n cards then it must appear in every card, and no other element repeats.

Proof: because each pairwise intersection contains precisely one element, all of the other elements in the cards containing f must be distinct. But then a card which doesn't contain f must have a non-trivial intersection with more than n disjoint sets despite having only n elements, which is impossible.

Corollary

  The largest possible deck in which f appears in more than n cards has size floor((N-1) / (n-1))

Excluding f from the N available pictures we get N-1 from which to draw disjoint sets of size n-1 to complete each card.

Lemma 2

  Any deck in which f appears in no more than n cards has at most n^2 - n + 1 cards.

Consider an arbitrary card containing f. By definition of f, none of the n elements of that card appears in more than n cards, and since each appears in that card the number of other cards is no more than n(n-1). Hence the deck cannot be larger than n(n-1) + 1.

Theorem

  The largest possible deck has an upper bound of max(n^2 - n + 1, floor((N-1) / (n-1))).

By combining the corollary and lemma 2.


Mathematica 16

Code

Subsets is native to Mathematica.

Column@Subsets@s

The code (without column) can be verified on WolframAlpha. (I had to use brackets instead of @; they mean the same thing.

Usage

s={1,2,3}
Column@Subsets@s

This method (55 chars) uses the approach suggested by @w0lf.

s #&/@Tuples[{0,1},Length@s]/.{0:>Sequence[]}//Column

Breakdown

Generate the tuples, composed of 0 and 1's of length Length[s]

Tuples[{0, 1}, Length@s]

  {{0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1,
     1, 0}, {1, 1, 1}}

Multiply the original list (vector) by each tuple:

s # & /@ Tuples[{0, 1}, Length@s]

  {{0, 0, 0}, {0, 0, 3}, {0, 2, 0}, {0, 2, 3}, {1, 0, 0}, {1, 0, 3}, {1,
     2, 0}, {1, 2, 3}}

Delete the 0's. % is shorthand for "the preceding output".

%/. {0 :> Sequence[]}

  {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}

Display in column:


Ruby, 55 or 39 characters
f=->n{(n>0?n-1:-n).to_s(2).tr'01',n>1?'LR':n<0?'RL':''}

The function returns the function sequence in composition order.
Usage:
puts f[21]     # RLRLL
puts f[-6]     # LLR

Edit: If we allow recursion (which violates the O(1) memory constraint but such does any function since the return value itself is O(lg n)) we can shrink the code to 39 characters.
f=->n{n<n*n ?f[(n-1)/2+1]+'RL'[n%2]:''}


Use ? in place of Print

Instead of using the Print command, ? may be used, as is the case in many BASIC languages - this means that the most simplest uBASIC Hello, World! program is as follows
0?"Hello, World!"

Rather than
10 Print "Hello, World!"

Try it Online!


How slow is Python really? (Or how fast is your language?)

Python2.7 + Numpy 1.8.1: 10.242 s

Fortran 90+: 0.029 s 0.003 s 0.022 s  0.010 s

Damn straight you lost your bet! Not a drop of parallelization here too, just straight Fortran 90+.

EDIT I've taken Guy Sirton's algorithm for permuting the array S (good find :D). I apparently also had the -g -traceback compiler flags active which were slowing this code down to about 0.017s. Currently, I am compiling this as

ifort -fast -o convolve convolve_random_arrays.f90

For those who don't have ifort, you can use

gfortran -O3 -ffast-math -o convolve convolve_random_arrays.f90

EDIT 2: The decrease in run-time is because I was doing something wrong previously and got an incorrect answer. Doing it the right way is apparently slower. I still can't believe that C++ is faster than mine, so I'm probably going to spend some time this week trying to tweak the crap out of this to speed it up.

EDIT 3: By simply changing the RNG section using one based on BSD's RNG (as suggested by Sampo Smolander) and eliminating the constant divide by m1, I cut the run-time to the same as the C++ answer by Guy Sirton. Using static arrays (as suggested by Sharpie) drops the run-time to under the C++ run-time! Yay Fortran! :D

EDIT 4 Apparently this doesn't compile (with gfortran) and run correctly (incorrect values) because the integers are overstepping their limits. I've made corrections to ensure it works, but this requires one to have either ifort 11+ or gfortran 4.7+ (or another compiler that allows iso_fortran_env and the F2008 int64 kind).

Here's the code:

program convolve_random_arrays
   use iso_fortran_env
   implicit none
   integer(int64), parameter :: a1 = 1103515245
   integer(int64), parameter :: c1 = 12345
   integer(int64), parameter :: m1 = 2147483648
   real, parameter ::    mi = 4.656612873e-10 ! 1/m1
   integer, parameter :: n = 6
   integer :: p, pmax, iters, i, nil(0:1), seed
   !integer, allocatable ::  F(:), S(:), FS(:)
   integer :: F(n), S(n+1), FS(2)

   !n = 6
   !allocate(F(n), S(n+1), FS(2))
   iters = 1000
   nil = 0

   !call init_random_seed()

   S = -1
   pmax = 2**(n+1)
   do p=1,pmax
      do i=1,iters
         F = rand_int_array(n)
         if(all(F==0)) then
            do while(all(F==0))
               F = rand_int_array(n)
            enddo
         endif

         FS = convolve(F,S)

         if(FS(1) == 0) then
            nil(0) = nil(0) + 1
            if(FS(2) == 0) nil(1) = nil(1) + 1
         endif

      enddo
      call permute(S)
   enddo

   print *,"first zero:",nil(0)
   print *," both zero:",nil(1)

 contains
   pure function convolve(x, h) result(y)
!x is the signal array
!h is the noise/impulse array
      integer, dimension(:), intent(in) :: x, h
      integer, dimension(abs(size(x)-size(h))+1) :: y
      integer:: i, j, r
      y(1) = dot_product(x,h(1:n-1))
      y(2) = dot_product(x,h(2:n  ))
   end function convolve

   pure subroutine permute(x)
      integer, intent(inout) :: x(:)
      integer :: i

      do i=1,size(x)
         if(x(i)==-1) then
            x(i) = 1
            return
         endif
         x(i) = -1
      enddo
   end subroutine permute

   function rand_int_array(i) result(x)
     integer, intent(in) :: i
     integer :: x(i), j
     real :: y
     do j=1,i
        y = bsd_rng()
        if(y <= 0.25) then
           x(j) = -1
        else if (y >= 0.75) then
           x(j) = +1
        else
           x(j) = 0
        endif
     enddo
   end function rand_int_array

   function bsd_rng() result(x)
      real :: x
      integer(int64) :: b=3141592653
      b = mod(a1*b + c1, m1)
      x = real(b)*mi
   end function bsd_rng
end program convolve_random_arrays

I suppose the question now is will you stop using slow-as-molasses Python and use fast-as-electrons-can-move Fortran ;).


JavaScript (ES6), 88 85 bytes

Takes input as an array of strings. Returns 0 for not free or 1 for free.

a=>a.map(s=>([a,b]=s.split` `,t+={e:+a,c:-a,t:x=t*a/100,d:-x}[(b||'e')[0]]),t=0)|t<=0

How it works

Each line is split on the space to get a = amount, b = type of operation. If there's no operation at all (which is the case on the first line), b is set by default to "e" for "extra".

To add the correct amount to the total t, we use an object whose keys are the first letter of the operation:

{
  e: +a,           // extra
  c: -a,           // coupon
  t: t * a / 100,  // tip
  d: -t * a / 100  // discount
}

Note: If the bill consisted of only one element, map() would return a single-element array which would be coerced to an integer when applied the | operator, making the final test fail. But the OP confirmed that this can't happen. (Arrays of 2 or more elements are coerced to 0.)

Demo

let f =

a=>a.map(s=>([a,b]=s.split` `,t+={e:+a,c:-a,t:x=t*a/100,d:-x}[(b||'e')[0]]),t=0)|t<=0

console.log(f([
'12.34',
'15 tip',
'25 discount',
'1.5 extra',
'2 coupon'
]))

console.log(f([
'10',
'20 tip',
'20 discount',
'2 coupon',
'2 coupon',
'1 coupon',
'50 discount',
'2.55 coupon'
]))


MATL, 12 bytes
tt:Z^tZPR>~z

Try it online!
Explanation
tt   % Implicit input n. Duplicate twice
     % STACK: n, n, n
:    % Range [1 2 ... n]
     % STACK: n, n, [1 2 ... n]
Z^   % Cartesian power. Gives an n^n × n matrix C where each row is a Cartesian tuple
     % STACK: n, C
t    % Duplicate
     % STACK: n, C, C
ZP   % Euclidean distance. Gives an n^n × n^n matrix D of pairwise distances
     % STACK: n, D
R    % Upper triangular part: sets elements below the main diagonal to 0. Call that U
     % STACK: n, U
>~   % Less than or equal? Element-wise. Gives a true-false matrix B
     % STACK: n, B
z    % Number of nonzeros. Implicitly display
     % STACK: number of entries in B that equal true


Given an integer, compute its Levenshtein code

Haskell, 70 bytes

b 0=[]
b n=b(div n 2)++[mod n 2]
f 0=[0]
f n|1:t<-b n=1:f(length t)++t

Defines a function f : Int -> [Int]. For example, f 5 == [1,1,1,0,0,0,1].


Python 2.7, 135 112 bytes

print sorted(list(input()))==sorted(list('\''*7+'\\'*3+'print sorted(list(input()))==sorted(list(*7+*3+*2))'*2))


VBScript - 1668 telephone keypresses (was 1708)

My entry is golfed a bit more - I realized (doh!) that the variable names should be characters that require less telephone keypresses (a,d,g,j,etc).

This program produces the output exactly as shown and takes the input as command line parameters.  If line endings are 1 byte there is no advantage to using : to put it all on one line (#0a vs #3a).  Run it with cscript script.vbs 8 10 replacing 8 and 10 with whatever values you want - it tries every combination in order to get the maximum string so it is SLOW.

I just have one question: if you needed a two numbers beside each other that were both on the same key isn't it a bit ambiguous.  Wouldn't the text a=e (22#333333) be the same keypresses as a>d (22#333333)?  How do you differentiate where the character boundaries are?  I didn't specifically check for every possible occurance of where things on the same key are beside themselves and I don't know what I would have done if I did notice it...

sub b(d,m)
p=true
a=len(m)
for g=1to a-1
p=p and instr(split("7890*1245*123456*2356*124578*123456789*235689*45780*4567890*56890","*")(mid(m,g,1)),mid(m,g+1,1))>0
next
if p and t<a then t=a
if d=""then exit sub
a=len(d)
for g=1to a
w=""
if g>1then w=left(d,g-1)
p=""
if g<a then p=mid(d,g+1)
b w+p,m+mid(d,g,1)
next
end sub
randomize
set m=wscript.arguments
for e=1to 2
d=""
j="Player "+cstr(e)+" rolled"
for t=1to mid(10000+m.item(0)*100+m.item(1),e*2,2)
w=cstr(int(rnd()*10))
j=j+" "+w
d=d+w
next
j=j+" with longest dialable number of"
t=0
b d,""
wscript.echo j+" "+cstr(t)
next

Ok, I am finally ready to score my entry - that of course means no more changes to it because of how long it takes to transform it to a score.  The transformed phone input is:

77777888222#20222#2833#2222266#29#02277#333887777888333#02222#3335555333666#2866#29#02233336666777
7#2044#3331886666#2022#2331#02277#33377#202266633#20444466677777887777#2877777775555444488#28#2278
90*1245*123456*2356*124578*123456789*235689*45780*4567890*56890#22#22222#22*#22#29#2866444433#2866
#2222244#222221#29#29#2222266444433#2866#2222244#22221#222221#29#29#33330#02266633399988#022444433
33#2077#202266633#2088#3222222#2088444333666#2088#33322#02244443333#2033#333#22#2288444333666#2033
3999444488#2077777888222#02222#3335555333666#2833#29#022333366667777#2044#3331886666#2022#02299#33
3#22#22#02244443333#2044#3333188444333666#2099#3335555333333388#2833#2222244#2331#29#02277#333#22#
22#02244443333#2044#3222222#2088444333666#2077#33366444433#2833#2222244#22221#29#022222#2099#22227
7#2222266#222266444433#2833#2222244#222221#29#02266633399988#02233366633#2077777888222#02277772266
633666666444499999333#0227777733388#2066#33399777772222777744447788#233322777744888663336668877777
#022333366667777#20333#3331886666#202#02233#333#22#22#02255#333#22#5055552299993337777#20#22#22222
22277777887777#28333#29#2222#22#20777766665555555533333#22#022333366667777#2088#3331886666#2066444
433#2810000#222266#233344448833366#280#29*100#222266#233344448833366#281#29#22222333*2#222222#29#0
2299#333222277777887777#28444466688#28777766633#28#29*10#29#29#02255#33355#2222#22#20#22#222299#02
233#33333#222299#02266633399988#02255#33355#2222#22#2099444488444#2055556666666443337777788#203344
44225555222225555333#20666888662223337777#2066663333#22#02288#3330#022222#2033#22222#22#22#0229977
7772222777744447788#233333322224446666#2055#2222#22#20#22#2222222277777887777#2888#29#022666333999
88


JavaScript (ES6), 102 bytes
Expects (book)(digits), where book is an array of strings and digits is an array of integers. Returns an array of strings.

b=>a=>b.filter(s=>eval(`/\\b[${a.map(i=>i+"01adgjmptw"[i]+"-"+"01cfilosvz"[i]).join`][`}]/i`).test(s))

Try it online!
How?
The sequence of digits is turned into a regular expression of the form:
/\b[Dx-y][Dx-y]...[Dx-y]/i

where D is the original digit and x-y is the letter range associated to it, or D-D for 0 or 1.
For instance, [2,7] becomes /\b[2a-c][7p-s]/i.
We walk through the phone book and keep only the names that are matched by this regular expression.
Commented
b => a =>             // b[] = book, a[] = integer sequence
b.filter(s =>         // for each string s in b[]:
  eval(               //   evaluate as JS code:
    "/\\b" +          //     regexp delimiter, followed by \b
    "[" +             //     followed by the first '['
    a.map(i =>        //     for each integer i in a[]:
      i +             //       append i
      "01adgjmptw"[i] //       append the first range character
      + "-" +         //       append a '-'
      "01cfilosvz"[i] //       append the second range character
    ).join`][` +      //     end of map(); join with ']['
    "]/i"             //     append the last ']' and '/i'
  )                   //   end of eval()
  .test(s)            //   keep s if it's matching the above regular expression
)                     // end of filter()


JavaScript (ES6) 77 83

(a,b,l,h=Math.sqrt(3)*l,x=a<0?-a:a,y=b<0?-b:b)=>y|x!=l?2*y<h&x/l+y/h<1?1:-1:0

Test

f=(a,b,l,h=Math.sqrt(3)*l,x=a<0?-a:a,y=b<0?-b:b)=>y|x!=l?2*y<h&x/l+y/h<1?1:-1:0

// TEST

function go() {
  C.width=400;C.height=300;
  var l=+I.value, x,y, cols={0:'#ff0',1:'#0f0','-1':'#888'},
  ctx = C.getContext("2d")
  ctx.translate(200,150)
  ctx.strokeStyle='#000'
  ctx.lineWidth=1;
  ctx.beginPath();
  ctx.moveTo(0,-150);ctx.lineTo(0,150);ctx.moveTo(-200,0);ctx.lineTo(200,0);
  ctx.stroke();
  ctx.strokeStyle='#f00'
  ctx.beginPath();
  ctx.moveTo(l*10,0);ctx.lineTo(l*5,l*Math.sqrt(3)*5);ctx.lineTo(-l*5,l*Math.sqrt(3)*5)
  ctx.lineTo(-l*10,0);ctx.lineTo(-l*5,-l*Math.sqrt(3)*5);ctx.lineTo(l*5,-l*Math.sqrt(3)*5)
  ctx.closePath();
  ctx.stroke();

  for(y=-14;y<15;y++)
    for(x=-19;x<20;x++) {
      ctx.beginPath();
      ctx.moveTo(x*10,y*10-3);ctx.lineTo(x*10,y*10+3);
      ctx.moveTo(x*10-3,y*10);ctx.lineTo(x*10+3,y*10);
      ctx.strokeStyle=cols[f(x,y,l)]
      ctx.stroke()
    }
}

go()
#C {
  border: 1px solid #000
}
L <input id=I value=15><button onclick="go()">GO</button>

<canvas id=C width=400 height=300></canvas>


Charcoal, 31 30 29 27 bytes

Ｆ²«Ｊι⁰↙χ↖↖⁵↙↙⁵↖↖²Ｐ↖χ↙↗χ↘↘¹²

Try it online! Link is to verbose version of code. Sadly Copy doesn't do what I want in this case, so I have to loop instead. Explanation:

Ｆ²«Ｊι⁰

Draw everything twice, but with the cursor starting one character to the right the second time.

   ↙χ↖↖⁵↙↙⁵↖↖²Ｐ↖χ

Draw the main W from right to left, but leave the cursor near the inverted V.

   ↙↗χ↘↘¹²

Draw the inverted V.


Python 2, 39 bytes

lambda x:x+len(`x`)+eval("+".join(`x`))

Test suite
Using the same eval-trick as in my Pyth-answer.


CJam, 27 24 23 22 bytes
q{i]_,+~3<-"1+2* "=~}/

Pretty straight forward. I use CJam's stack as the stack mentioned in the question ;)
Algorithm
First lets look at the ASCII code for . and :.
'.i ':ied

[46 58]

Since in CJam, index wraps around, lets see if we can use these values directly to get the desired operation ..
'.i4% ':i4%ed

[2 2]

So I cannot simply use the ASCII codes in a 4 length operation string. Lets try some other values
'.i 10% ':i 10%ed

[6 8]

which on a 4 length string boils down to

[2 0]

I can use this mod 10 operation but that will cost be 2 bytes. Lets try something else
'.i5% ':i5%ed

[1 3]

Nice!, now we just subtract 1 for the stack size condition to get the indexes 0, 1, 2 and 3 and use a 5 length array ("1+2* ") as a switch case. The last space is just a filler to make it of length 5. This is just 1 extra byte as compared to modding operation.
q{                  }/    e# parse each input character in this loop
  i]                      e# convert '. or ': into ASCII code and wrap everything
                          e# in stack in an array
    _,+                   e# Copy the stack array, take its length and add the length to
                          e# the stack array
       ~3<                e# unwrap the stack array and check if stack size is less than 3
                          e# 3 because either . or : is also on stack
          -               e# subtract 0 or 1 based on above condition from ASCII code
           "1+2* "        e# string containing the operation to perform
                  =~      e# chose the correct operation and evaluate it

Try it online here
1 byte saved thanks to cosechy


Pyth, 1 byte
X

Verify all the test cases.
Pyth has wonderful built-ins :-)

Pyth,  8  7 bytes
sm@_QxQ

Verify all the test cases.
How it works
This is the more interesting non-built-in approach.
sm@_QxQ  - Full program.

 m       - Map over the input.
  @_Q    - Get the index in the reversed input.
     xQ  - Of the first index of each character in the String.
s        - Join the list.


C99, 771 characters

#include <ncurses.h>
#include <string.h>
#define MIN(A,B) (A<B?A:B)
#define MAX(A,B) (A>B?A:B)
#define T(C,X,Y) case C:if((m[x+X][y+Y]==' ')||(m[x+X][y+Y]=='#'))x+=X,y+=Y;s++;break;
char m[24][81],M[24][81];int i,j,I=0,J,x,y,s=0;
int main(int c,char**v){FILE*f=fopen(v[1],"r");
for(I=0;fgets(m[I],80,f);I++)J=MAX(J,strlen(m[I]));
J--;f=fopen("/dev/random","r");do{x=fgetc(f)%I;y=fgetc(f)%J;}
while(m[x][y]!=' ');initscr();curs_set(0);do{
switch(c){T('e',0,1)T('n',-1,0)T('s',1,0)T('w',0,-1)}
for(i=MAX(0,x-1);i<MIN(x+2,I);i++)for(j=MAX(0,y-1);j<MIN(y+2,J);j++)M[i][j]=1;
for(i=0;i<I;i++)for(j=0;j<J;j++)mvaddch(i,j,M[i][j]?m[i][j]:'?');
mvaddch(x,y,'@');refresh();}while((m[x][y]!='#')&&(c=getch())!='q');
if(m[x][y]=='#')mvprintw(I,0,"Finished in %d steps!",s),getch();endwin();}

Requires and makes use of ncurses. Only one macroization for length, and the N and M macros are to replace the missing minimum and maximum opperators, and I don't think there is much more to do on that.

It assumes the input maze does not exceed 80 characters wide, and that the a maze filename has been passed on the command-line, and that the number of parameters is low enough that the initial value of c isn't a movement command.

Deviates from the standard in that it takes single character direction commands as the lowercase first letter of the ones suggested.
Does show unknown regions as '?'s.

More readable with comments:

#include <ncurses.h>
#include <string.h>

#define MIN(A,B) (A<B?A:B)/*unsafe,but short*/
#define MAX(A,B) (A>B?A:B)/*unsafe,but short*/
// #define MAX(A,B) ((_A=A)>(_B=B)?_A:_B) /* safe but verbose */
#define T(C,X,Y) case C:if((m[x+X][y+Y]==' ')||(m[x+X][y+Y]=='#'))x+=X,y+=Y;s++;break;
char m[24][81],M[24][81];/* [m]ap and [M]ask; NB:mask intialized by default */
int i,j, /* loop indicies over the map */
  I=0,J, /* limits of the map */
  x,y,   /* player position */
  s=0;   /* steps taken */
int main(int c,char**v){
  FILE*f=fopen(v[1],"r"); /* fragile, assumes that the argument is present */
  /* Read the input file */
  for(I=0;fgets(m[I],80,f);I++)J=MAX(J,strlen(m[I])); /* Read in the map */
  J--;
  /* note that I leak a file handle here */
  f=fopen("/dev/random","r");
  /* Find a open starting square */
  do{
    x=fgetc(f)%I; /* Poor numeric properties, but good enough for code golf */
    y=fgetc(f)%J;
  } while(m[x][y]!=' ');
  /* setup curses */
  initscr(); /* start curses */
  //  raw();     /* WARNING! intercepts C-c, C-s, C-z, etc...
  //          * but shorter than cbreak()
  //          */
  curs_set(0); /* make the cursor invisible */
  /* main loop */
  do {
    switch(c){
      T('e',0,1)
      T('n',-1,0)
      T('s',1,0)
      T('w',0,-1)
    }
    /* Update the mask */
    for(i=MAX(0,x-1);i<MIN(x+2,I);i++)
      for(j=MAX(0,y-1);j<MIN(y+2,J);j++)
    M[i][j]=1;
    /* draw the maze as masked */
    for(i=0;i<I;i++)
      for(j=0;j<J;j++)
    mvaddch(i,j,M[i][j]?m[i][j]:'?');
    /* draw the player figure */
    mvaddch(x,y,'@');
    refresh(); /* Refresh the display */
  } while((m[x][y]!='#')&&(c=getch())!='q');
  if(m[x][y]=='#')mvprintw(I,0,"Finished in %d steps!",s),getch();
  endwin();
}


Python 296
Not actually too inefficient, it only checks as many digits as it needs to.
n=raw_input();s=int(len(n)**.5);t=0
for i in range(s**2):
    l=[]
    while i not in l:l.append(i);c=n[i];i=(i%s+(-1 if c in'456'else 1 if c in'218'else 0))%s+((i/s+(-1 if c in'432'else 1 if c in'678'else 0))%s)*s
    t=t*9+len(l)-l.index(i)
print'EGL'[cmp(t,long(n,9))]

As for numbers equal to their strength, I think the only solutions are, for every N x N square up to N=8 a square containing N in every space. My thinking is that since every number in a loop must be the same number (the length of the loop) each loop would have to be all in one direction. This of course means that the loop's size must be N (and each element must be N). I'm pretty sure that this logic can be applied to squares and loops of any size, meaning there are no squares equal to their strength other than the first 8.


Python, 42 bytes

f=lambda x:x*0==[]and len(x)+sum(map(f,x))

For a non-list, output 0. For a list, output its length plus the sum of the recursive outputs for its elements.

Lists fall above numbers and below strings in the Python 2 ordering, requiring []<=x<''. Instead, we check x*0==[], whereas the result of 0 for a number or '' for a string.


Befunge

Whoa, that was a job, even with the editor I made for this challenge. Here's what I got, a nice 11x12 block:

v$,g6<6g,$v
v,$ _^_ $,v
1W>v\B\v>L1
~T+:1E1:-O~
+F00-F-02L+
>:|6gUg6|:>
{a@>^N^>@z`
>1+|@G$| +>
:^9< E<  ^1
~>7^@_,#:>:
 xD>65 ^=P~
v,-\+**<  v

It does a couple of things, sadly only for lowercase letters.

What it does

When run normally, it performs a Caesar cipher on the input.

abcxyz      -> bcdyza
exampletext -> fybnqmfufyu

When flipped horizontally, it reverses said cipher. This is the requirement for the challenge, but it doesn't end here.

bcdyza      -> abcxyz
fybnqmfufyu -> exampletext

When flipped vertically, it ciphers input with a reverse alphabet. This can be considered the opposite approach to the Caesar cipher.

abcxyz      -> zyxcba
exampletext -> vcznkovgvcg

Finally, when rotated 180 degrees, it reverses input. I have a feeling it has to be a reverse of something (hint: the input).

abcxyz      -> zyxcba
exampletext -> txetelpmaxe

How it works

The block basically consists of four semi-overlapping algorithms.

Caesar cipher encoder

v$,g6<
v,$ _^
1 >v\
~ +:1
+ 00-
>:|6g
{a@>^

Caesar cipher decoder (flipped horizontally)

v$,g6<
v,$ _^
1 >v\
~ -:1
+ 20-
>:|6g
`z@>^

Reverse alphabet cipher (flipped vertically)

v,-\+**<
   >65 ^
~>7^
:^9<
>1+|@
   >^

Text reverser (rotated 180 degrees)

v  <
~
:>:#,_@
1^  <
>+ |$
   >^


Try: http://tetris.muehe.org

Update There's a global high score. Enjoy beating it or - alternatively - hacking it :-)

CoffeeScript and HTML version, should fulfill the requirements to the best of my knowledge (and I have never really played Tetris).

$ make stats
4095

Github https://github.com/henrik-muehe/tetris

Features

Exponential scoring
Next piece indicator
Fair randomness
Rotation, move and drop down
Game over indication
Highscore with server backend that should not be that easily fakeable.


Python 2: 172

from itertools import*
d,n=input();S=[[1]]
for s in S:
 for v in range(1,n+1):
  if(v!=s[-1])*all(w[2:]!=w[:-2]for w in combinations(s+[v],d+1)):S.append(s+[v])
print S[-1]

Input is simply in the format 4, 3.

I iteratively create all sequences, which start with 1 and satisfy the two properties, and store them in S. Since I create them in sorted order (sorted by length [and by values]), the last entry has to be a Davenport-Schinzel-sequence. Uses the nice fact, that you can iterate over a list while appending to it.


MATL, 3 bytes
8#u

Input is a string enclosed with quotation marks (which is allowed by default)
Try it online!
Explanation
u is the unique function, which essentially removes duplicates. It can produce up to four outputs. The fourth output is the count of unique characters, identified in order of appearance.
8# specifies that the fourth output of u should be produced. In general, 2# means "produce two outputs", 3# means "produce three outputs" etc. When the maximum number of function outputs is reached, larger numbers mean "take the first output only", or "the second only" etc. Thus, since u has four possible outputs, 4# would produce all four outputs; 5# produces the first, 6# the second, etc.


Jelly, 3 bytes

®¬©

Try it online!

How it works

®¬©  Main link. No arguments.

®    Retrieve the value stored in the register.
 ¬   Negate it.
  ©  Copy the result to the register.


Mathematica 138 107 237 bytes
My first attempts were sloppy and unworthy. This should work generally, provided that the birth dates are given in order of earliest to latest, as in the test cases.
The test cases were well-chosen and difficult to implement correctly.
The code turned out way longer than I had hoped.
The general logic is to

Solve for x (in days) such that the distance from x to each date of birth sums to the target passage of time (e.g 100 years converted to days).
If the earliest date + x days > latest date of birth, remove the latest date of birth and repeat step (1), Else move to (3).
Return (earliest date + x days)

t_~f~d_:=If[DateDifference[a=DateObject[DatePlus[d[[1]],Solve[t 365.25==Tr@(x-Join[{0},
QuantityMagnitude@(DateDifference[d[[1]],#,"Day"]&/@Rest@d)]),{x}][[1,1,2]]]/.
{y_,m_,n_,h_}:>{y,m,n+1}],d[[-1]]]>Quantity[0,"Days"],f[t,Most@d],a]

Test Cases
f[10, {{2000, 1, 1}}]
f[100, {{1975, 3, 5}, {1978, 7, 23}, {2008, 11, 12}, {2012, 12, 20}}]
f[100, {{1975, 3, 6}, {1978, 7, 23}, {2008, 11, 12}, {2012, 12, 20}}]
f[100, {{1975, 3, 9}, {1978, 7, 23}, {2008, 11, 12}, {2012, 12, 20}}]
f[100, {{1975, 3, 10}, {1978, 7, 23}, {2008, 11, 12}, {2012, 12,  20}}]
f[3, {{1990, 8, 1}, {1995, 7, 2}}]
f[50, {{1975, 3, 5}, {1978, 7, 23}, {2008, 11, 12}, {2012, 12, 20}}]


CJam, 57 bytes

l_"+-":Pf&sN+\PSerS/.{'^-'x/2We]"11".e|:~~:Em!*"/s^"E)+@}

Try it online in the CJam interpreter.


JavaScript (Node.js), 113 108 102 bytes

-5 bytes because input will always be valid brainstract
-6 bytes thanks to Cows quack for regex function golfs

x=>{while(m=/({\w+)\s+(\W+)}/.exec(x))x=x.replace(eval(`/${m[1]}}/g`),m[2]).replace(m[0],'');return x}

Try it online!

TIO Link includes a test suite of all 4 "valid" test cases provided in the OP.
The invalid recursive macro test was ignored as, given it's undefined behavior and our program can whatever, there's no need to test it; the result is irrelevant.

Ungolfed Explanation:

fun = code => {
    // While there's a macro definition in the code
    while(match = /{(\w+)\s+(\W+)}/.exec(code)) {
        // Replace calls to the macro with the macro's code
        code = code.replace(eval(`/${m[1]}}/g`),m[2])
        // And remove the definition from the code
            .replace(m[0],'');
    }
    // Remove all spaces from the code and return
    return x;
}

The entire function relies on the regex: /{(\w+)\s+(\W+)}/
This should match any valid macro definition and include the macro name in Capture Group 1, and the macro's code in Capture Group 2.

Due to how JS's regex.exec() returns, m[0] is the whole matched string (the entire macro definition), m[1] is the string matched by Capture Group 1 (the macro name) and m[2] is the string matched by Capture Group 2 (the macro's code)

We can then replace all instances of {m[1]} with m[2], then remove the first instance of m[0] in order to remove the macro definition. This is required in part due to the way brainfuck would interpret the macro definition, and in part due to the way the while loop in this function works (it finds the first definition in the code, if we don't remove the definition after we've processed it, it'll keep finding the first definition over and over)

However, our first capture group m[1] also includes the opening brace { of the macro definition. This is so that when replacing {m[1]} with m[2], we actually only need to replace m[1]}, which saves a byte.

Unfortunately including a variable m[1] in a RegExp in JS is a bit costly, as we need to eval the regex, which adds 6 bytes.

There's probably quite a bit of golfing room in this answer, as there tends to me in my NodeJS answers.
If anybody has any suggestions for golfing, let me know in the comments.

However if your answer involves using an entirely different approach to mine, please post your own answer :)


CJam, 76 75 bytes

52,qN/{[~](52\-@/(\e_@{/(@+\e_}/\+}/2ew::m2f/0-,_!\26>-"weak trick fair"S/=

Try it online in the CJam interpreter.


Jelly, 14  11 bytes

-3 bytes thanks to Dennis (avoid a chain separation allowing some implicit actions; use a filter to avoid the two byte œ& multi-set intersection I was using.)

⁵ḶŒ!Ẇf¥ÐḟDL

Try it online! - the specified version is far too slow for the online interpreter, so this is a proof of concept test suite:
- it does the same thing for only 5 digits 01234,
- the first example is the empty list, yielding 120 as expected (5!),
- the last returns 1 as the only permutation still available to the professor is 04321,
- an offline run of the full version with input [18062,6042,35876] yielded 3622326 as expected.

How?

⁵ḶŒ!Ẇf¥ÐḟDL - Main link: list a
⁵           - literal 10
 Ḷ          - lowered range: [0,1,2,3,4,5,6,7,8,9]
  Œ!        - all permutations
         D  - decimal list (vectorises across a)
       Ðḟ   - filter discard (from the permutations) if: (note - non-empty is truthy)
      ¥     -   last two links as a dyadic operation:
    Ẇ       -     all sublists (of the current permutation)
     f      -     filter keep (if in the decimal list)
          L - length


JavaScript, 81 bytes

s=>s.replace(/./g,c=>(p=14>>c&!p)|c>3?eval(`"\\u302${c}"`):'〇一二三'[c],p=0)

Try it online!

Using 14>>c saves 3 bytes. Thanks to Arnauld.


Mathematica  1183 483 bytes (or 190) bytes
Approach 1
240-50 (bonus) = 190 bytes
The knight's tour can be represented as a graph.  So the issue becomes simply to find the shortest path from each knight to the pawn.  Mathematica offers both KnightTourGraph and FindShortestPath as built-in functions.
w@p_:=Characters@p/.{r_,s_}:>(ToCharacterCode[s][[1]]-65)*8+ToExpression@r
z@v_:=ToString@(v~Mod~8/.{0->8})<>FromCharacterCode[Quotient[v-1,8]+65]
p_~h~k_:=Row[SortBy[(z/@FindShortestPath[8~KnightTourGraph~8,#,w@p])&/@w/@k,Length][[1]],"->"]

Examples
h["5A",{"1C","2G"}]

1C -> 3B -> 5A

h["8G",{"1C","2G"}]

2G -> 3E -> 5D -> 7E -> 8G

Approach 2
(533-50 (bonus)= 483  bytes)
Here the knight's tour graph is constructed without using KnightTourGraph.
s@v_:=
Sort[{v,#}]/.{{a_, b_}:>UndirectedEdge[a,b]}&/@(
If[If[#4==1,Greater,Less][Mod[v-1,8]+1,#1]&&If[#5==1,Greater,Less][Quotient[v-1,8]+1,#2],v+#3,Nothing]&@@@{{1,2,-17,1,1},{8,2,-15,0,1},{2,1,-10,1,1},{7,1,-6,0,1},{2,8,6,1,0},{7,8,10,0,0},{1,7,15,1,0},{8,7,17,0,0}})
w@p_:=Characters[p]/.{r_,q_}:>(ToCharacterCode[q][[1]]-65)*8+ToExpression@r
z@v_:=ToString@(Mod[v,8]/.{0 -> 8})<>FromCharacterCode[Quotient[v-1,8]+65]
p_~f~k_:=Row[SortBy[(z/@FindShortestPath[Graph[Range@64,Union@Flatten[s/@Range@64]],#,w@p])&/@w/@k,Length][[1]],"->"]

Explanation
Below are two views of the chessboard.
On the left, each chessboard position corresponds to vertex bearing an integer name.   On the right, the positions have been labelled according to the convention suggested by the OP.
In both figures, White sits on the right, Black sits on the left.

Legal moves of a knight are paths along a knight tour graph.
The function, s, generates all 512 moves (as if each square allowed for 8 knight moves), eliminates inverses, and then weeds out the moves that would land off the board.  There are 168 edges on the graph.
edges consists of a list of elements of the form, UndirectedEdge[a,b]. For instance, the edge, UndirectedEdge[1,11]corresponds to the idea that a knight at vertex 1, that is, at "A1" in standard notation, may jump to vertex 11, or "B3", and vice-versa.
toVertex takes a position (see right board) and returns a vertex (see left board).  For instance toVertex["3H"] returns 59.
toChessPosition does the opposing conversion, namely from a vertex to a chess position.
vertexNames is a list of replacements: {1->"1A",2->"2A"...64->"8H"}.
This is only needed for the right chessboard figure shown above.
numberedKnightsTouris the graph displayed above on the left.
chessKnightsTouris the graph displayed above on the right.
The graphs are constructed using the above-defined vertices and edges.
findShortestPath receives the position of the pawn and a list of positions of the knights and finds the shortest path along the graph from a knight to the pawn.
    s@v_:=
Sort[{v,#}]/.{{a_, b_}:>UndirectedEdge[a,b]}&/@(
If[If[#4==1,Greater,Less][Mod[v-1,8]+1,#1]&&If[#5==1,Greater,Less]
edges=Union@Flatten[s/@Range@64];
toVertex[p_]:=Characters[p]/.{rank_,file_}:> (ToCharacterCode[file][[1]]-65)*8+ToExpression[rank]
toChessPosition[v_]:=ToString@(Mod[v,8]/.{0->8})<>FromCharacterCode[Quotient[v-1,8]+65]
vertexNames=Thread[Range@64->(toChessPosition[#]&/@Range[64])];
numberedKnightsTour=Graph[Range@64,edges,VertexLabels->"Name",GraphLayout->"SpringEmbedding"];
vertexNames=Thread[Range[64]->(toChessPosition[#]&/@Range[64])];
chessKnightsTour=Graph[Range@64,edges,ImageSize->Large,VertexLabels-> vertexNames,GraphLayout->"SpringEmbedding"];
GraphicsGrid[{{numberedKnightsTour,chessKnightsTour}},PlotLabel->"For each board below, \nWhite sits at Right, Black at Left\nNumbers refers to rank, letters refer to file",ImageSize->Large]
    findShortestPath[pawn_,knights_]:=Row[SortBy[(toChessPosition/@FindShortestPath[chessKnightsTour,#,toVertex@pawn])&/@toVertex/@knights,Length][[1]],"->"]


Select the word around the given index in a given string

V, 10, 9 7 bytes
À|diwVp

Try it online!
This answer uses 1-based indexing.
This could be shorter if we do exactly what the title says: "Select the word around the given index in a string". We could do
À|viw

Which literally selects the word, but unfortunately doesn't change the output at all. So we need a little workaround to make it work by cutting it into a register, deleting the rest of the text, then pasting the register back in.
Explanation:
À|          " Jump the position of argument 1
  diw       " (d)elete (i)nside this (w)ord.
     V      " Select this line
      p     " And replace it with the word we just deleted


Spotify Shuffle (music playlist shuffle algorithm)

JavaScript (Node.js),  125  124 bytes
Saved 1 byte thanks to @KevinCruijssen

a=>a.flatMap(a=>a.sort(_=>R()-.5).map(v=>[(o++-.1+R()/5)/a.length,v],o=R()),R=Math.random).sort(([a],[b])=>a-b).map(a=>a[1])

Try it online!
Commented
a =>                          // a[] = input
  a.flatMap(a =>              // for each category a[] in a[]:
    a.sort(_ => R() - .5)     //   shuffle a[]
    .map(v =>                 //   for each value v in a[]:
      [                       //     build a pair [position, value]:
        ( o++                 //       increment o
          - .1                //       subtract 1/10
          + R() / 5           //       add 2/10 * random value in [0,1)
        ) / a.length,         //       divide the result by the length of a[]
        v                     //       use v as the 2nd element
      ],                      //     end of pair
      o = R()                 //     start with o in [0,1)
    ),                        //   end of map()
    R = Math.random           //   R = alias for Math.random
  )                           // end of flatMap()
  .sort(([a], [b]) => a - b)  // sort by first element, in ascending order
  .map(a => a[1])             // keep only the 2nd element


Generate a valid sequence of numbers with specific rules

GolfScript (17 16 chars)

Assuming input on stdin and output on stdout.

~:^),(;{-2\^%?}$

Almost alphanumeric-free...


JavaScript (ES6), 32 bytes

f=(s,n=0)=>(s+n)[n]?f(s,n+1):s+n

How it works

f = (s, n = 0) =>   // given a string 's' and starting with n = 0:
  (s + n)[n] ?      // if the Nth character of (s + n) exists:
    f(s, n + 1)     //   try again with n + 1
  :                 // else
    s + n           //   return s + n

Starting with N=0, we test the Nth character (0-based) of the string made of the concatenation of the original input string and the decimal representation of N. We increment N until this character doesn't exist anymore.

Example:

N =  0 : abcdefghi0
         ^
N =  1 : abcdefghi1
          ^
N =  2 : abcdefghi2
           ^
...
N =  8 : abcdefghi8
                 ^
N =  9 : abcdefghi9
                  ^
N = 10 : abcdefghi10
                   ^
N = 11 : abcdefghi11    -> success
                    ^

Test cases

f=(s,n=0)=>(s+n)[n]?f(s,n+1):s+n

console.log(f("aaa"));       // -> aaa4
console.log(f(""));          // -> 1
console.log(f("aaaaaaaa"));  // -> aaaaaaaa9
console.log(f("aaaaaaaaa")); // -> aaaaaaaaa11
console.log(f("a1"));        // -> a13


MATLAB, 646 x 0.9 = 581.4 bytes
t=input('','s');p=char(960);s=regexprep(t,{p,'pi([a-zA-Z])','([a-zA-Z])pi','([\)e\d])([a-zA-Z])','([a-zA-Z])(([\(\d]|pi))','e^(\(.+?\))','e'},{'pi','pi*$1','$1*pi','$1*$2','$1*$2','exp($1)','exp(1)'});r=[s(regexp(s,'\<[a-zA-Z]\>')),'x'];r=r(1);e=0;try
I=int(sym(strsplit(s,' + ')),r);S=[];for i=I
S=[S char(i) ' + '];end
b=0;o=[];for i=1:nnz(S)
c=S(i);b=b+(c==40)-(c==41);if(c==42&&S(i+1)==r)||(b&&c==32)
c='';end
o=[o c];end
o=regexprep(char([8747 40 t ')d' r ' = ' o 67]),{'pi','exp\(1\)','exp','\^([^\(])',['1/' r]},{p,'e','e^','^($1)',[r '^(-1)']});catch
e=1;end
if e||~isempty(strfind(o,'log'))
disp(['Cannot integrate ' t]);else
disp(o);end

This is currently a work-in-progress using MATLABs built in symbolic integration capabilities. Currently the requirements have been updated so the format now matches the requirements. It also does qualify for the second -10% bonus.
If anyone wants to pitch in and suggest ways of correcting the output, or use this code as a basis for another answer, feel free :). If I can find the time, I'll keep playing with it and see if I can think how to reformat the output.
Update: Ok, so after a bit more work, here is how the code currently stands. It is still a work in progress, but now getting closer to matching the required output.
t=input('','s'); %Get input as a string
p=char(960); %Pi character
s=regexprep(t,{p,'pi([a-zA-Z])','([a-zA-Z])pi','([\)e\d])([a-zA-Z])','([a-zA-Z])(([\(\d]|pi))','e^(\(.+?\))','e'},{'pi','pi*$1','$1*pi','$1*$2','$1*$2','exp($1)','exp(1)'}); %Reformat input to work with built in symbolic integration
r=[s(regexp(s,'\<[a-zA-Z]\>')),'x'];r=r(1); %determine the variable we are integrating
e=0; %Assume success
try
    I=int(sym(strsplit(s,' + ')),r); %Integrate each term seperately to avoid unwanted simplificaiton
    S=[];
    for i=I
        S=[S char(i) ' + ']; %Recombine integrated terms
    end
    %Now postprocess the output to try and match the requirements
    b=0;o=[];
    for i=1:nnz(S)
        %Work through the integrated string character by character
        c=S(i);
        b=b+(c=='(')-(c==')'); %Keep track of how many layers deep of brackets we are in
        if(c=='*'&&S(i+1)==r)||(b&&c==' ') %If a '*' sign preceeds a variable. Also deblank string.
            c=''; %Delete this character
        end
        o=[o c]; %merge into new output string.
    end
    o=regexprep([char(8747) '(' t ')d' r ' = ' o 'C'],{'pi','exp\(1\)','exp','\^([^\(])',['1/' r]},{p,'e','e^','^($1)',[r '^(-1)']});
catch
    e=1; %failed to integrate
end
if e||~isempty(strfind(o,'log'))
    disp(['Cannot integrate ' t])  %bit of a hack - matlab can integrate 1/x, so if we get a log, we pretend it didn't work.
else
    disp(o)% Display it.
end

Here are some examples of what it currently produces. As you can see, it's not quite right, but getting closer.
Inputs:
x
-f^(-2)
(1/7)x^(1/7) + 5
πx^e
(f+1)^(-1)

Outputs:
∫(x)dx = x^(2)/2 + C
∫(-f^(-2))df = f^(-1) + C
∫((1/7)x^(1/7) + 5)dx = x^(8/7)/8 + 5x + C
∫(πx^(e))dx = (πx^(e+1))/(e+1) + C
Cannot integrate (f+1)^(-1)


Output nth term in Catalan type sequence

GolfScript (29 chars)

~([1]{.{.10*)\10%{.)}*}%|}9*=

This is a pretty naïve implementation, although reasonably fast.

~(         # Evaluate input, decrement to get a 0-based index
[1]        # Initial row of tree
{          # Loop: stack is the first n rows of the tree as an array
  .        # Duplicate the array
  {        # Map: extend each element of the array into its children
    .10*)  # Get the first child; stack is   rows x 10x+1
    \10%   # How many more children does x have?
    {.)}*  # Those children are found by successive incrementation
  }%       # End map
  |        # Add the new unique elements (i.e. the new bottom row) to the rows
}9*        # Repeat 9 times, so that the array has 23713 correct values and one incorrect
=          # Array lookup


x86-16 Machine Code, 62 bytes

Hex dump:

BC0100B101B07EBAFE0581EAE00080EA02B402CD1085E4750830E439C5750A30C0B40ACD1084C074094884D275E085D275D831C031E4CD1630E489C5EBC7

Assembly:

mov sp, 0x0001           ; Stack pointer is used as a flag; 0 - Print all characters, 1 - Delete specific character
mov cl, 0x01             ; Number of characters to print per interrupt call

printString:
  mov al, 0x7E           ; Last character to print
  mov dx, 0x05FE         ; Row: 0x05, Collumn: 0xFE
  printRow:
    sub dx, 0x00E0       ; Decrement row number + 2 extra characters
    printChar:
      sub dl, 0x02       ; Decrement collumn index + 1 space
      mov ah, 0x02       ; Prepare for interrupt call, 0x02 - Set cursor position
      int 0x10           ; BIOS interrupt

      test sp, sp        ; Are we printing all characters or removing specific character
      jnz print          ; In first case just print it and go on
      xor ah, ah         ; Otherwise reset the upper byte of ax (shorter than "and ax, 0x00FF")
      cmp bp, ax         ; Is the current character same as the input character
      jne after          ; If no, continue searching
      xor al, al         ; If yes, remove it

      print:
        mov ah, 0x0A     ; Prepare for print
        int 0x10         ; Print

      test al, al        ; If we found target character
      jz loop            ; then stop searching

      after:
        dec ax           ; Shorter than "dec, al"
        test dl, dl      ; Is it the last character in the row
        jnz printChar    ; If no, continue searching
    test dx, dx          ; Is it last char
    jnz printRow         ; If no, go to next row

loop:
  xor ax, ax             ; Remove "ah" cache
  xor sp, sp             ; Reset sp (it will never become 1 again)
  int 0x16               ; BIOS interrupt for reading keyboard input
  xor ah, ah             ; Again reset "ah", because BIOS may change it
  mov bp, ax             ; Save it in stack base pointer
  jmp printString        ; Remove the character from the list


How many Wazirs can be placed on an N×N Chessboard?

Whitespace, 45 bytes

Try it online!

By the way, here is a proof that the ⌈n²/2⌉ formula is correct.

We can always place at least ⌈n²/2⌉ wazirs: just lay them out in a checkerboard pattern! Assuming the top-left tile is white, there are ⌈n²/2⌉ white tiles and ⌊n²/2⌋ black tiles on the n × n board. And if we place wazirs on the white tiles, no two of them are attacking each other, as every wazir only “sees” black tiles.

Here’s how we place 13 wazirs on a 5 × 5 board (each W is a wazir).

We can’t do any better: let’s arbitrarily tile the checkerboard with 2 × 1 domino pieces, optionally using a 1 × 1 piece for the final corner of an odd-length chessboard, like so:

We need ⌈n²/2⌉ dominoes to cover the chessboard. Clearly, putting two wazirs on one domino makes it so that they can attack one another! So each domino can only contain at most one wazir, meaning we can’t possibly place more than ⌈n²/2⌉ wazirs on the board.


Bash + coreutils, 54

7 bytes saved thanks to @manatwork

grep -oE '#\w+'|sort|uniq -c|sort -nr|awk '$0=$2" "$1'

This assumes STDIN input of Imagemagick's .txt format.
Ideone.

If the above input format is too much of a stretch, then we can add Imagemagick conversion from any format:
Bash + coreutils + Imagemagick, 71
convert $1 txt:-|grep -oE '#\w+'|sort|uniq -c|sort -nr|awk '$0=$2" "$1'

Here, the input image filename is passed in as a command-line parameter.


Lua

print"four"

Highly optimized and golfed xkcd's random number generator

An actual solution, 380

x=math.random(0,150)m=math.floor print(x==0 and"zero"or((x>99 and"onehundred"or"")..(({"ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"})[x%100-9]or({[0]="",nil,"twenty","thirty","fourty","fifty","sixty","seventy","eighty","ninety"})[m(x/10)%10]..({[0]="","one","two","three","four","five","six","seven","eight","nine"})[x%10])))


Wolfram Language (Mathematica), 42 bytes
#&@@CellularAutomaton[{,{},0{,}},{#,0},0]&

Try it online!
Cellular automata are indeed the answer to life, the universe, and everything.1
How?
CellularAutomaton accepts an input array and an optional background value. Thus, {#,0} specifies that a cellular automaton rule should be applied to the input, assuming a background of 0s.
A neat thing here is that CellularAutomaton crops the output so that no border of background cells is present (because otherwise the output lies on an infinite plane).
The code applies the rule {Null, {}, {0, 0}} -- applying the head Null to the 0-radius neighbor of each cell (i.e. only the center: the cell itself) -- exactly 0 times. The result of this is the original input, but with background removed (i.e. cropping out surrounding 0s).

1. See the bytecount of my answer? ;)


About 200 ms
function mark() {
  var t = 0, tp = '';
  var c = [], i = { r: 0, p: '', c: 0 };
  var elements = document.body.getElementsByTagName('*');
  var length = elements.length, index, v;
  for (index = 0; index < length; ++index) {
    v = elements[index];
    switch (v.tagName) {
      case 'TH':
      case 'TD':
        v.className = i.p + i.c++;
        if (i.c == 10 && i.r == 10) {
          i = c.pop();
        }
        continue;
      case 'TR':
        v.className = i.p = i.t + i.r++;
        i.c = 0;
        i.p += '-col-';
        continue;
      case 'TABLE':
        v.className = tp = 'table-' + t++;
        tp += '-row-';
        c.push(i);
        i = { t: tp, r: 0, p: '', c: 0 };
    }
  }
}

If your code runs more than 2s, you must do something wrong. I believe.


JavaScript (ES6), 186 bytes

a=>a.map(([a,b,c,d])=>h.push([b,a,c],[d,a,c])&v.push([a,b,d],[c,b,d]),h=[],v=[])|h.map(([d,a,e])=>v.map(([c,f,b])=>a<c&c<e&b<d&d<f&t.every(([a,b])=>a-c|b-d)&&t.push([c,d])),t=[])|t.length

Splits each rectangle into its component lines, then intersects the horizontal and vertical lines, building up a list of intersections to avoid duplicates.


Write the longest program that prints the date of tomorrow

C# - ~500Kb -

Don't you love nested if's?
Used to work only for 2014 dates, but successfully refactored to work for any date :)

Cannot post code here, I just receive an error...

http://pastebin.com/azGr3JSz

(Will probably hang your browser, sorry)


Wolfram Language (Mathematica), 99 bytes
sPrint@@@Array[s[[4# #-2#+1-#2&@@If[Abs@#2<2#,!##,#-Abs@#2|-#2]]]/._@__->" "&,2{L=Tr[1^s],L},-L]

Try it online!
Directly computes the index of each position: in Cartesian coordinates,
\$\operatorname{index}(x,y)=\textit{offset}+\begin{cases}2y(2y+1)-x,&|x|<-2y\\
2\left(y+|x|\right)\left(2\left(y+|x|\right)+1\right)+x,&\text{else}\end{cases}\$
where \$\textit{offset}\$ is the index of the "first" character (1, in Mathematica).
Takes a list of characters as input.

Older approach, 123 122 109 107 bytes
Print@@@Normal@SparseArray[i=0;p=2Length@#;(p+=ReIm[I[2+I,1-I][[⌈2√i++⌉~Mod~4-1]]-1])->#&/@#,2p," "]&

Try it online!
The direction of the (1-indexed) ith character relative to the previous character can be computed with \$\Big\lceil2\sqrt i\Big\rceil\bmod 4\$:

1: ↗
2: ↘
3,0: ←


Retina 0.8.2, 63 bytes
(//.*|/\*(.|¶)*?\*/|¶)|.
$1
//(.*)|/\*((.|¶)*?)\*/|(¶)¶*
$1$2$4

Try it online! Link includes test cases, but the newline-collapsing rule means that they're not double-separated on output. Explanation:
(//.*|/\*(.|¶)*?\*/|¶)|.
$1

Delete anything not a newline or comment.
//(.*)|/\*((.|¶)*?)\*/|(¶)¶*
$1$2$4

Keep the content of comments and one newline of consecutive newlines.