There are two new sheriffs in town – Identifying DJMcMego pairs!

C (gcc), 259 258 254 253 250 248 233 222 bytes

Thanks to Stan Strum for inspring a one byte golf.
Saved four bytes by juggling some variable initializations.
Saved a byte by golfing for(...;l++)b*=B[l]==-~B[l-1]; to for(...;b*=B[l]==-~B[~-l++]); (most likely relying on undefined behaviour, as it requires first evaluating B[l] followed by -~B[~-l++]).
Saved three five bytes.
Saved fifteen twenty-six bytes thanks to ceilingcat.

j,k,l,L,r,b;f(char*A,char*B){for(j=r=0;k=A[L=j];)A[j++]=-~abs(A[j]-B[j]);for(;k-L;k++)for(j=~0;L-++j;r|=!b)if(k-j)for(bcopy(B-~l,strcpy(B,A)+l,strlen(A+l)),bcopy(B+j,B-~j,L+~j),B[j]=A[k],l=b=0;B[++l];b|=B[l]+~B[~-l]);A=r;}

Try it online!

Explanation (248 byte version)

j,k,l,L,r,b;                            // global variables
f(char*A,char*B){                       // function takes two strings
 for(j=r=0;A[j];L=j)                    // loop through A, compute array length L
  A[j++]=-~abs(A[j]-B[j]);              // set every entry in A to the absolute
                                        // difference of A and B at that position
                                        /* Test out all possible movements of        *
                                         * characters and see if any one             *
                                         * results in a sorted list => DJMcMego pair */
 for(j=0;j-L;j++)                       // loop through array
  for(k=~0;L-++k;r|=!b)                 // loop through array
   if(j-k){                             // j is not equal to k
    for(l=0;A[l];B[l++]=A[l]);          // copy A to B
    for(l=j;A[l];B[~-l]=B[++l]);        // shift part of B
    for(l=L;l-k;B[-~l]=B[--l]);         // shift part of B
    B[k]=A[j];                          // insert character at correct position
    for(l=b=0;B[++l];b|=B[l]+~B[~-l]);} // test if B is sorted
 A=r;}                                  // return if there was a DJMcMego pair found

Try it online!


Python 2, 78 75 79 bytes

s=-1
for i in sorted(input()):
 if i/10^s:s=i/10;print'\n%d-'%s,
 print`i`[-1],

Try it online!


Checking a file contains only null bytes

Pyth, 6 5 bytes
!sCM'

Try it online!
Takes a filename from STDIN, opens and reads the file, converts it to a list of ints (think Python ord) sums the list (will return 0 iff file is all null bytes), and nots the result, printing it.

Hey,
This looks a lot like a general programming question. These belong on Stack Overflow. However, from the comments under the main post, I can see that this was not your intent. That said, I feel that the discussion has been unnecessarily hostile on both sides, so I've decided to pick up the slack and give you the proper PPCG welcome!
Generally, we ask that any challenges are first posted to our sandbox for proper feedback. You can take a look at the current submissions in there to see what format we prefer for challenges. Please give it a try next time!
Just in case we've all misunderstood you and you are looking for a general solution, here's a solution in Python 3:
def main(string):
    with open(string) as file:
        return not any(map(ord,file.read()))


TryAPL, 1 byteSBCS

Anonymous tacit prefix function. As TryAPL has no associative arrays, this takes a list of pairs as argument.

↑

Try APL!

↑ mix the list of pairs into a table


Know your looping constructs

QBasic has several looping constructs: FOR ... NEXT, WHILE ... WEND, and DO ... LOOP. You can also use GOTO or (in some situations) RUN to loop.

FOR ... NEXT is pretty good at what it does. Unlike in Python, it's almost always shorter than the equivalent WHILE or GOTO loop, even when it gets a little fancier:

FOR i=1TO 19STEP 2:?i:NEXT
i=1:WHILE i<20:?i:i=i+2:WEND
i=1:9?i:i=i+2:IF i<20GOTO 9

Note that you don't need to repeat the variable name after NEXT, and you can eliminate space between numbers and most following keywords.
WHILE ... WEND is good for when you have a loop that might need to execute 0 times. But if you know the loop will execute at least once, GOTO might be one byte shorter:

WHILE n>1:n=n\2:WEND
1n=n\2:IF n>1GOTO 1

I only use DO ... LOOP for infinite loops (except where RUN can be used instead). While it costs the same number of characters as an unconditional GOTO, it's a little more intuitive to read. (Note that "infinite loop" can include loops that you break out of using a GOTO.) The DO WHILE/DO UNTIL/LOOP WHILE/LOOP UNTIL syntax is too verbose; you're better off using WHILE or GOTO as appropriate.
GOTO is, as mentioned above, the shortest general way to write a do/while loop. Use single-digit line numbers instead of labels. Note that when a GOTO is the only thing in the THEN part of an IF statement, there are two equally terse shortcut syntaxes available:

IF x>y GOTO 1
IF x>y THEN 1

GOTO can also be used to create more complicated control flows. The naysayers refer to this as "spaghetti code," but this is code golf: unreadability is almost a virtue! GOTO pride!
RUN is useful when you need to jump to a fixed place in the program and you don't need to keep any of the variables' values. RUN by itself will restart the program from the top; with a label or line number, it will restart at that line. I've mainly used it to create stateless infinite loops.


Charcoal,  17  13 bytes

Thanks to @Neil for saving 4 bytes!

(↙↓⊖θＭ↑(→↗Ｎ‖Ｍ

Try it online!

Explanation:

(↙                // Print '(' and move one step down and to the left.
  ↓⊖θ             // Print n-1 '|'s downwards.
     Ｍ↑          // Move one step up.
        (→        // Print '(' and move one step to the right.
          ↗Ｎ      // Print n '/'s towards the upper right corner.
            ‖Ｍ    // Mirror the left half to produce the right half.


Compute the histogram entropy estimation of a string

Python 3.3+, 64 bytes

import math
lambda s:sum(math.log2(len(s)/s.count(c))for c in s)

Got math.log2 from mbomb007's solution.


MATL, 36 bytes
`nZ@[]etGg)GXz-yt!hs&ytXdwPXdhsh&-ha

The input is an \$ n \times n\$ matrix, with \$0\$ for the unknown numbers.
The code keeps generating random \$ n \times n\$ matrices formed by the numbers \$1, \dots, n^2\$ until one such matrix meets the required conditions. This procedure is guaranteed to finish with probability one.
This is a terrible approach, in that:

running time is random, and unbounded;
average running time increases as \$(n^2)!\$ (that's more than exponentially);
and so it very likely times out in the online interpreter.

... but hey, it's the shortest answer so far!
(Don't) try it online.
See below a sped-up animated GIF of an example run which happened to take about 2 minutes, here compressed to a few seconds.

Explanation
`         % Do...while
  n       %   Number of elements. This implictly takes the input in the first
          %   iteration, or uses the candidate solution from the previous iteration.
          %   Let this number be denoted as N
  Z@      %   Random permutation of integers 1, 2, ..., N
  []e     %   Reshape as a square matrix. This yields a candidate solution
  t       %   Duplicate
  Gg)     %   Push input, convert to logical, index: this produces a column vector
          %   of the entries of the candidate solution that correspond to nonzero
          %   entries in the input matrix
  GXz     %   Push input, take its nonzero elements. Gives a column vector
  -       %   Element-wise difference (*). This will be all zeros for a valid
          %   solution
  y       %   Duplicate second-top object from the stack, that is, the candidate
          %   solution
  t!      %   Duplicate, transpose
  h       %   Concatenate horizontally
  s       %   Sum of columns. This also gives the sum of rows, thanks to the
          %   concatenated, transposed copy. The result is a two-element row
          %   vector (**)
  &y      %   Duplicate third-top object from the stack: the candidate solution
  tXd     %   Duplicate, extract diagonal as a column vector
  wPXd    %   Swap, flip vertically, extract diagonal. This gives the anti-diagonal
          %   as a column vector
  h       %   Concatenate horizontally
  s       %   Sum of each column. This gives the sum of the diagonal and that
          %   of the anti-diagonal
  h       %   Concatenate horizontally with (**)
  &-      %   Matrix of all element-wise differences. This will be a matrix of
          %   zeros for a valid solution (***)
  h       %   Concatenate (*) and (***) horizontally. Since sizes do not match,
          %   both (*) and (***) are first linearized to row vectors, and the
          %   result is a row vector
  a       %   Any. This gives true if any element is non-zero
          % End (implicit). A new iteration is run if the top of the stack is true
          % Display (implicit). The candidate solution from the last iteration is
          % the valid solution


Haskell, 356 characters

main=interact$f.break null.lines;f(r,_:p)=unlines$map(foldr(g.w)(j"B"++)r)p
g[r,s,d,a,b]n x|and$zipWith3($)(cycle[k.('/'#),q.(':'#)])[s,a,d,b]$w x=j r++x|t=n x
k[y,z]x=y%z==x%z;y%z=foldl((.r).(+).(*256))0('.'#y)`div`2^(32-r z)
q["*"]x=t;q[y]x=x==y;q[a,b]x=r x>=r a&&r x<=r b
d#x=w$map(d?)x;d?x|d==x=' '|t=x;j"A"="ALLOW ";j"B"="BLOCK ";t=1<3;r=read;w=words


Python3, 49 47 bytes

def f(x):
 l=x**.5//1
 while x%l:l-=1
 return l

Explanation

l=x**.5//1 → Assign l the largest integer less than equal to the square root of x
while x%l:l-=1 → While l does not evenly divide x, decrement l.

Edits

Mention Python3, not Python2
Use ...//1 to save two bytes.  (Decimals are okay!  Thanks @Rod)


Briefest code to find vowels and print consonants

05AB1E, 62 bytes

Code:

”‡Á•Ë: ÿ”,”Vowelš‹: ”?"aeiou"©vy": "¹y¢««}", "ý,“«¶šÞ: “ª¹®-J,

Explanation:

There is a lot of string compression going on here. Here is a list of all strings that are compressed:

”‡Á•Ë” is equivalent to Enter String.
”Vowelš‹” is equivalent to Vowel Count.
“«¶šÞ“ª is equivalent to Remaining characters.

To see how the actual string compression works, see the Hello, World! answer, or an even more elaborate explanation at the bottom of the Code Review question. Without the string compression, the code looks like this:

"Enter String: ÿ","Vowel Count: "?"aeiou"©vy": "¹y¢««}", "ý,"Remaining characters: "¹®-J,

Or a more readable 3-part version:

"Enter String: ÿ",
"Vowel Count: "?"aeiou"©vy": "¹y¢««}", "ý,
"Remaining characters: "¹®-J,

Part 1:

We first push the string "Enter String: ÿ". The ÿ here is used for string interpolation. But since the stack is empty, implicit input is requested. The ÿ will be substituted with the user input. We print this with a newline using ,.

Part 2:

We first print the "Vowel Count: " string without a newline using ?. After that, we push the aeiou string, ©opy that to the register and map over the string using v and do the following:

vy": "¹y¢««}    # Mapping loop

v          }    # The loop itself
 y              # Push the current letter (which is a, e, i, o or u)
  ": "          # Push this string
      ¹         # Push the first input again
       y        # Push the letter again
        ¢       # Count the number of occurences of that letter in the input
         ««     # Concatenate to one single string, (e.g. "a: 4")

This leaves 5 different string onto the stack, the stack looks like this now:

stack: ['a: 0', 'e: 1', 'i: 0', 'o: 2', 'u: 0']

We join each element in the stack with ", " using ý. After this, we print it with a newline using ,.

Part 3:

We first push the string "Remaining characters: ". We push the first input again using ¹. We then push "aeiou" which we retrieve from the register using ®. After this, we remove all letters in aeiou using - and Join this with the Remaining characters-string. Finally, we output this with a newline using ,.

Uses CP-1252 encoding. Try it online!.


Mathematica, 177 173 128 124 120 bytes

c=Circle;Graphics@{{0,0}~c~3,Rotate[Table[If[-3<x-y<4,c[{√3x,-x+2y}/2,1,Pi/{6,2}]],{x,-3,2},{y,-4,2}],Pi/3#]&~Array~6}

The main idea is to compose the result from six rotated versions of this:

This in turn is a rectangular table of identical circle arcs with two corners cut off. If we remove the shearing and represent each circle center with a #, we basically want to distribute the circles in this pattern:

####
#####
######
######
 #####
  ####

These edges are cut off by imposing the condition -3 < x-y < 4 on the 2D indices (since the value of x-y is constant along diagonals) and the shearing comes from multiplying these x and y by non-orthogonal basis vectors which span the grid we're looking for.

This particular orientation of the unrotated arcs turns out to be the shortest since both ends of the arc evenly divide Pi so that the arc can be expressed as Pi/{6,2} (all other arcs would either require and additional minus sign or integers in the numerator).


JavaScript (ES7),  36  35 bytes
Similar to other answers. Using a Black Magic formula instead of a lookup table.

f=n=>n&&(n%10)**29%3571%4+f(n/10|0)

Try it online!
Here is a script that looks for \$(p,m)\$ pairs such that \$(n^p\bmod m)\bmod 4=a_n\$ for all \$n\in[0..9]\$.
It's worth noting that this code takes IEEE-754 precision errors into account. So the results are correct but the math is wrong.
With exact values, we could do instead:
$$\big((n \bmod 10)^{18}\bmod 4011\big)\bmod 4$$
Or better yet, as suggested by @dingledooper:
$$\big((n \bmod 10)^{55}\bmod 767\big)\bmod 4$$
For instance, in Python:
Python 2, 40 bytes

f=lambda n:n and(n%10)**55%767%4+f(n/10)

Try it online!

JavaScript (ES7), 71 bytes
Expects the amount as a string.
A naive recursive approach that subtracts one coin/bill at a time.

n=>(k=10**n.length,g=t=>+n?k>n?g(t,k/=~++i%3?2:2.5):g(t+1,n-=k):t)(i=0)

Try it online!


JavaScript (ES6), 180 bytes

x=>x.replace(/^([cpt](?!h)|d(?!d)|[bgm]|ll|rh)(.+)/,(_,y,z)=>({p:"b mh ph",t:"d nh th",c:"g ngh ch",b:"f m",d:"dd n",g:" ng",m:"f"}[y]||y[0]).split` `.map(b=>a.push(b+z)),a=[x])&&a

Outputs as an array of strings. This is my first try, so it's almost certainly not optimal.

Try it out

f=x=>x.replace(/^([cpt](?!h)|d(?!d)|[bgm]|ll|rh)(.+)/,(_,y,z)=>({p:"b mh ph",t:"d nh th",c:"g ngh ch",b:"f m",d:"dd n",g:" ng",m:"f"}[y]||y[0]).split` `.map(b=>a.push(b+z)),a=[x])&&a
<input id=A value="pobl"><button onclick="B.innerHTML=f(A.value).join('
')">Run</button>


Jelly, 20 19 18 bytes

S‘gṪ’ɗƇḟ¹Ṃṭ
1Ç¡>¹S

This is a full program.

Try it online!

How it works

1Ç¡>¹S       Main link. Argument: n (integer)

1            Set the return value to 1.
 Ç¡          Call the helper link n times.
   >¹        Compare the elements of the result with n.
     S       Take the sum, counting elements larger than n.

S‘gṪ’ɗƇḟ¹Ṃṭ  Helper link. Argument: A (array or 1)

S            Take the sum of A.
 ‘           Increment; add 1.
     ɗƇ      Drei comb; keep only elements k of [1, ..., sum(A)+1] for which the
             three links to the left return a truthy value.
  g              Take the GCD of k and all elements of A.
   Ṫ             Tail; extract the last GCD.
    ’            Decrement the result, mapping 1 to 0.
       ḟ¹    Filterfalse; remove the elements that occur in A.
         Ṃ   Take the minimum.
          ṭ  Tack; append the minimum to A.

Note that the generated sequence is \$[1, \mathbf{0}, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, \dots]\$. Since calling the helper link \$n\$ times generates a sequence of length \$n + 1\$, the \$0\$ is practically ignored.


Javascript ES6, 379 bytes

This solution was used to generate the example runs in the question.

f=(s,ls)=>{with(V=document.createElement`canvas`)with(getContext`2d`)with(Math)return(width=height=s,translate(s/=2,s),(S=(o,d=0,n=ls[d],i=(o-o*sin(PI/n))/(sin(PI/n)+1),r=0)=>{fillStyle=`rgba(0,0,0,${pow(d/ls.length,4)})`;beginPath(),arc(0,0,o,-PI,PI),fill();if(d++<ls.length){S(i,d,n);for(;r<n;++r){save();translate(0,(o+i)/2);S((o-i)/2,d);restore();rotate((2*PI)/n);}}})(s),V)}

Ungolfed:

f=(s,ls)=>{                                        // define function that accepts image dimensions and a list of orders
 with(V=document.createElement`canvas`)            // create canvas to draw on, bring its functions into current scope chain
 with(getContext`2d`)                              // bring graphics functions into current scope chain
 with(Math)return(                                 // bring Math functions into current scope chain
  width=height=s,                                  // set width and height of image
  translate(s/=2,s),                               // center the transform on image
   (S=(o,d=0,                                      // define recursive function that accepts outer radius, depth, and optionally order
       n=ls[d],                                    // default chain order to corresponding order in input list
       i=(o-o*sin(PI/n))/(sin(PI/n)+1),            // calculate inner base circle radius
       r=0)=>{                                     // initialize for loop var
    fillStyle=`rgba(0,0,0,${pow(d/ls.length,4)})`; // fill based on depth
    beginPath(),arc(0,0,o,-PI,PI),fill();          // draw circle
    if(d++<ls.length){                             // if within recursion limit
     S(i,d,n);                                     //   recurse on inner circle
     for(;r<n;++r){                                //   loop through all circles of the chain
      save();                                      //   save transform
      translate(0,(o+i)/2);                        //   translate origin to middle of the 2 base circles
      S((o-i)/2,d);                                //   recurse on chain circle
      restore();                                   //   restore transform
      rotate((2*PI)/n);                            //   rotate transform to next circle in chain
   }}})(s),                                        // begin the recursion
 V)}                                               // return the canvas

Note: f returns a canvas.

Example run (assumes there's a <body> to append to):

document.body.appendChild(f(600,[13,7,11,5,3]))

Should dump the following image to the page:


Jelly, 12 bytes

⁴Ḷ×þ`d⁴‘ịØhG

Try it online!

How it works

⁴Ḷ×þ`d⁴‘ịØhG  Main link. No arguments.

⁴             Set the return value to 16.
 Ḷ            Unlength; yield [0, ..., 15].
  ×þ`         Build the multiplication table of [0, ..., 15] and itself.
     d⁴       Divmod 16; yield [p : 16, p % 16] for each product p.
       ‘      Increment quotients and remainders (1-based indexing).
        ịØh   Index into the lowercase hexadecimal alphabet.
           G  Grid; join columns by spaces, rows by newlines.


Decode ascii and reversed words sentence

Use lambdas

def f(a,b):return c

can be shortened to

f=lambda a,b:c

(the f= can also be removed per CGCC site standards)

Remove excess []s

x.join([a for b in c])

can be

x.join(a for b in c)

since join can take a generator instead of a list

Split is on spaces by default

Thanks ElPedro for reminding me about this

So the split(' ')s can be shortened, which in turn means the s=' ' doesn't help (and it only broke even in the first place).

Take input from STDIN and output to STDOUT

print will automatically print arguments with space as a separator if you use * to unpacks the sequence/collection into positional arguments, and taking input via input() is shorter. Also, setting s to space doesn't actually save any bytes.

Altogether, this is 79 bytes:

print(*[w[::-1]for w in(''.join(chr(int(c))for c in input().split()).split())])

Try it online!

or, if you're dedicated to having a function, 82 bytes:

lambda m:' '.join(w[::-1]for w in(''.join(chr(int(c))for c in m.split()).split()))

Try it online!

plus seven or so characters if you really need the function to be called decode


Japt -x, 1 byte
Takes input as a string.
á

Try it

Explanation
á     :Get permutations
      :Implicitly reduce by addition and output


x86 machine code, 12 bytes
8c c8 83 f8 23 b0 20 75 02 00 c0 c3

Ungolfed:
getKernelBitness:
    mov eax,cs
    cmp eax,0x23 ; 32 bit process on 64 bit kernel has this selector in CS
    mov al,32
    jne kernelIs32Bit
    add al,al    ; return value in eax
kernelIs32Bit:
    ret

This function works in Linux when used in ELF32, following i386 SysV ABI, as well as in Windows/Wine when used in PE32, following stdcall calling convention.


Javascript, 22 bytes

n=>"\\/"[n%2].repeat(n)

Defines an anonymous function.

If only * repeated strings in Javascript. sighs


Caddyshack or: How to compress already-golfed code

Python 3 Caddy, interprets BrainF***

Score: \$\frac{38}{224}\approx0.17\$ (with newlines removed)

Program E

from textwrap import wrap

x = input('Code: ')
i = ['<', '>', '+', '-', '[', ']', '.', ',']
o = ''
for c in x:
    if c in i:
        o += str(i.index(c) + 1)
if o:
    d = wrap(o, 6)
    d = [int(x) for x in d]
    o = ''
    for c in d:
        o += chr(int(c) + 128)
print('Compressed: ', o)

The way this works is by converting every instruction in the input to a digit, then concatenating those digits to a number. Then it splits that number into 6-digit groups and converts each to a Unicode character. (A number higher than 6 could be used, by that would cause errors for large programs). Then it outputs it.

Program D

x = input('Compressed: ')
p = input('Input: ')
p = list(p)
d = ''
for c in x:
    c = ord(c) - 128
    d += str(c)
d = d.replace('-', '')
i = ['<', '>', '+', '-', '[', ']', '.', ',']
o = ''
for n in d:
    n = int(n) - 1
    o += i[n]
tape = [0] * 30000
head = 0
m = {}
m2 = {}
stack = []
for i in range(len(o)):
    char = o[i]
    if char == '[':
        stack.append(i)
    elif char == ']':
        begin = stack.pop()
        m[begin] = i + 1
        m2[i] = begin
i = 0
while i < len(o):
    char = o[i]
    if char == '<':
        head -= 1
        i += 1
    elif char == '>':
        head += 1
        i += 1
    elif char == '+':
        tape[head] += 1
        i += 1
    elif char == '-':
        tape[head] -= 1
        i += 1
    elif char == '[':
        if tape[head] == 0:
            i = m[i]
        else:
            i += 1
    elif char == ']':
        if tape[head] != 0:
            i = m2[i]
        else:
            i += 1
    elif char == '.':
        print(chr(tape[head]), end='')
        i += 1
    elif char == ',':
        try:
            tape[head] = ord(p.pop(0))
        except:
            tape[head] = 0
        i += 1

This is pretty simple, it just reverses the compression algorithm and evaluates the result.


Jelly, 13 12 bytes

³Ḥ6ẋX€+2/ṢŒr

A niladic link. Output format is a list of lists of [value, count].

(Zero rolls means no such entry is present in the output - e.g. an output of[[6, 12], [7, 74], [8, 14]] would identify that only sums of six, seven and eight were rolled.)

Try it online!

How?

³Ḥ6ẋX€+2/ṢŒr - Main link: no arguments
³            - 100
 Ḥ           - double = 200
  6          - 6
   ẋ         - repeat -> [6,6,6...,6], length 200
    X€       - random integer from [1,z] for €ach (where z=6 every time)
       2/    - pairwise reduce with:
      +      -   addition (i.e. add up each two)
         Ṣ   - sort
          Œr - run-length encode (list of [value, length] for each run of equal values)


R, 85 77 74 bytes

function(x,z=sapply(x,function(x)sum(x>0)+any(x<1)*13))abs(z-any(z>25)*26)

Unnamed function that takes an R-list as input. Works by counting the number of elements >0 and adds 13 if any element within each vector is <1 (i.e. queen of spades) and store as z.

If any element in z is >25, return 26-z, else return z.

Try it on R-fiddle


Demonstrate a lower bound for the Ramsey number R(4,4)


05AB1E, 28 bytes

-4 bytes + fix thanks to Kevin Cruijssen

"34çìD«s<©di®ì"34çìD«s<©di®ì

Try it online!

Explanation

This works by appending the remaining number to print to the front of the code, which means it's added to the stack the same way an input would be. In the base case of input of "0" it will not concatenate the 0 on the front.


Python 2, 109 99 98

n=input()
r=range(1,abs(n)+1)
l=r+r[~n|-2::-1]
for j in l:print[abs((n<0)*~-n+min(i,j))for i in l]

Create list

l = [1,2,3,4,5,4,3,2,1]

and play with it a little.

edit: new way of creating list + thx Lynn for two bytes


JavaScript (ES6), 177 bytes

g=
(w,h,f,b)=>`<svg${s=` width=${w} height=`+h}><rect${s} fill=${b} />`+[...Array(h)].map((_,i)=>`<line stroke=${f} stroke-dasharray=${h-i} x1=0 y1=${i} x2=${w} y2=${i} />`).join``
Width: <input id=w value=80 type=number min=1>
Height: <input id=h value=50 type=number min=1>
Foreground: <input id=f value=#000000>
Background: <input id=b value=#FFFF00>
<input type=button value=Go! onclick=o.innerHTML=g(+w.value,+h.value,f.value,b.value)>

Outputs an HTML5-compatibile SVG image.


J, 9 7 bytes

Thanks to @randomra for shaving off two characters:

?~2&,]

Previously I had:

?~($~2&,)

These are functions, you can apply them to an argument directly or store them in a variable and then use them:

   (?~2&,$]) 5
1 0 4 2 3
2 4 0 3 1
2 3 1 0 4
2 3 0 1 4
3 0 1 4 2

1 4 0 2 3
2 1 4 3 0
2 3 1 0 4
2 3 1 4 0
0 1 2 3 4

   f=.?~2&,$]
   f 5
4 2 3 0 1
3 4 1 0 2
3 4 0 2 1
1 2 4 3 0
2 0 4 1 3

2 1 3 0 4
1 3 4 2 0
2 4 1 3 0
3 2 1 0 4
3 0 4 2 1


Brachylog, 12 11 bytes
My first Brachylog answer
Take input as a string
{~cĊịᵐ-ȧ}ᶠ⌋

Try it online!
Explanation:
ᶠ will find all possible outputs for the predicate in {…} and store them in a list. ~c says that the output is a list that, when concatenated, is equal to the input. Next Ċ asserts that the the output of ~c has length 2.
ịᵐ converts both elements of the output into integers (this gets rid of leading 0s), -ȧ takes the absolute difference of the two elements.
Once we have our list of all possible outputs, we get the minimum element with ⌋


Python, 51

def f(n):r=int(str(n)[::-1]);return n-r and-~f(n+r)

For Python 2, backticks can't replace str() because of the L attached to long literals.

Here's an alternate version with score 64 * 0.85 = 54.4:

def f(n,c=262):r=int(str(n)[::-1]);return c*(n-r)and-~f(n+r,c-1)

And an alternate version for Python 3 with score 88 * 0.6 = 52.8:

def f(n,c=262):r=int(str(n)[::-1]);return c*(n-r)and-~f(n+r,print(n,'+',r,'=',n+r)or~-c)


Perl 6 Raku, 45 44 39 bytes

{+(1...{$_∈($^a,{$_+.flip}...*>$_)})}

Try it online!
Explanation:
{                                   }  # Anonymous code block
 +(1...                            )     # Find the first integer
       {                          }      # Where
        $_∈                              # The input is an element of
           (              ...    )         # A sequence defined by
            $^b,                           # The first element is the number we're checking
                {$_+.flip}                 # Each element is the previous element plus its reverse
                             *>$_          # The last element is larger than the input


Output the ŋarâþ crîþ alphabet song without using (m)any letters

7, 410 characters, 154 bytes in 7's encoding, 0 letters = score 154

55104010504200144434451510201304004220120504005434473340353241135014335450302052254241052253052244241052335452241114014241310052340435303052335442302052335500302052335430302052313340435303135014243241310335514052312241341351052302245341351525755102440304030434030421030442030424030455733413512410523142410523030523112411350143355142410523414252410523102410523002410523413342411145257551220304010420030455741403

Try it online!

In a challenge that dislikes using letters, what better language to use than one consisting only of digits?

This is a full program that exits via crashing, so there's extraneous output to stderr, but stdout is correct.

Explanation

A 7 program, on its first iteration, simply pushes a number of elements to the stack (because out of the 12 commands that exist in 7, only 8 of them can be represented in a source program, and those 8 are specialised for writing code to push particular data structures to the stack). This program does not use the 6 command (which is the simplest way to create nested structures, but otherwise tends not to appear literally in a source program), so it's only the 7 commands that determine the structure; 7 pushes a new empty element to the top of stack (whereas the 0…5 commands just append to the top of stack). We can thus add whitespace to the program to show its structure:

551040105042001444344515102013040042201205040054344 7

33403532411350143354503020522542410522530522442410523354522411140142413100523
40435303052335442302052335500302052335430302052313340435303135014243241310335
514052312241341351052302245341351525 7

55102440304030434030421030442030424030455 7

33413512410523142410523030523112411350143355142410523414252410523102410523002
41052341334241114525 7

551220304010420030455 7

41403

The elements near the end of the program are pushed last, so are on top of the stack at the start of the second iteration. On this iteration, and all future iterations, the 7 interpreter automatically makes a copy of the top of the stack and interprets it as a program. The literal 41403 pushes the (non-literal, live code) 47463 (7 has 12 commands but only 8 of them have names; as such, I use bold to show the code, and non-bold to show the literal that generates that code, meaning that, e.g. 4 is the command that appends 4 to the top stack element). So the program that runs on the second iteration is 47463. Here's what that does:

47463
4       Swap top two stack elements, add an empty element in between
 7      Add an empty stack element to the top of stack
  4     Swap top two stack elements, add an empty element in between
   6    Work out which commands would generate the top stack element;
        append that to the element below (and pop the old top of stack)
    3   Output the top stack element, pop the element below

This is easier to understand if we look at what happens to the stack:

… d c b a 47463 (code to run: 47463)
… d c b 47463 empty a (code to run: 7463)
… d c b 47463 empty a empty (code to run: 463)
… d c b 47463 empty empty empty a (code to run: 63)
… d c b 47463 empty empty "a" (code to run: 3)
… d c b 47463 empty (code to run: empty)

In other words, we take the top of stack a, work out what code is most likely to have produced it, and output that code. The 7 interpreter automatically pops empty elements from the top of stack at the end of an iteration, so we end up with the 47463 back on top of the stack, just as in the original program. It should be easy to see what happens next: we end up churning through every stack element one after another, outputting them all, until the stack underflows and the program crashes. So we've basically created a simple output loop that looks at the program's source code to determine what to output (we're not outputting the data structures that were pushes to the stack by our 0…5 commands, we're instead recreating what commands were used by looking at what structures were created, and outputting those). Thus, the first piece of data output is 551220304010420030455 (the source code that generates the second-from-top stack element), the second is 3341351…114525 (the source code that generates the third-from-top stack element), and so on.

Obviously, though, these pieces of source code aren't being output unencoded. 7 contains several different domain-specific languages for encoding output; once a domain-specific language is chosen, it remains in use until explicitly cleared, but if none of the languages have been chosen yet, the first digit of the code being output determines which of the languages to use. In this program, only two languages are used: 551 and 3.

551 is pretty simple: it's basically the old Baudot/teletype code used to transmit letters over teletypes, as a 5-bit character set, but modified to make all the letters lowercase. So the first chunk of code to be output decodes like this:

551  22 03 04 01 04 20 03 04  55
     c  a  SP e  SP n  a  SP  reset output format

As can be seen, we're fitting each character into two octal digits, which is a pretty decent compression ratio. Pairs of digits in the 0-5 range give us 36 possibilities, as opposed to the 32 possibilities that Baudot needs, so the remaining four are used for special commands; in this case, the 55 at the end clears the remembered output format, letting us use a different format for the next piece of output we produce.

3 is conceptually even simpler, but with a twist. The basic idea is to take groups of three digits (again, in the 0-5 range, as those are the digits for which we can guarantee that we can recreate the original source code from its output), interpret them as a three-digit number in base 6, and just output it as a byte in binary (thus letting us output the multibyte characters in the desired output simply by outputting multiple bytes). The twist, though, comes from the fact that there are only 216 three-digit numbers (with possible leading zeroes) in base 6, but 256 possible bytes. 7 gets round this by linking numbers from 332₆ = 128₁₀ upwards to two different bytes; 332 can output either byte 128 or 192, 333 either byte 129 or 193, and so on, up to 515 which outputs either byte 191 or 255.

How does the program know which of the two possibilities to output? It's possible to use triplets of digits from 520 upwards to control this explicitly, but in this program we don't have to: 7's default is to pick all the ambiguous bytes in such a way that the output is valid UTF-8! It turns out that there's always at most one way to do this, so as long as it's UTF-8 we want (and we do in this case), we can just leave it ambiguous and the program works anyway.

The end of each of the 3… sections is 525, which resets the output format, letting us go back to 551 for the next section.


Brachylog, 7 bytes
{|∧Ṣ}ᵐ⊇

Try it online!
I should not be surprised to learn that it's considerably faster if I put the ⊇ at the end. Takes the original marquee through the input and the target through the output.
{   }ᵐ     The input variable, with each element
 |         possibly
  ∧Ṣ       replaced by a space,
      ⊇    has the output variable as a subsequence.

Can also go the other way around, for another two bytes: {|Ṣ∧l₁}ᵐ⊆


Frink, distance 24

Calculate[the,Levenshtein]:=editDistance[the,Levenshtein]

To use this, you would call Calculate with the two strings, and since this is returning, you also need to surround the call with print[]. If this isn't allowed, my score is 30.

Example:

Calculate["kitten","spork"]        -> returns 6
print[Calculate["kitten","spork"]] -> prints 6.

You need to download Frink, as the web interpreter doesn't allow defining functions. It should run on all systems, considering it's a Java applet. Download instructions here..

Psst. Hey! Here's a Levenshtein implementation in Symbolic, something I'm working on: k=λ:Δ(ί,ί).


JavaScript (ES6), 44 bytes
Takes input as an array of integers.

a=>a.map(x=>s+=(t+=s>=x&&x)>s*-~s*2,t=s=1)|s

Try it online!
How?
The threshold \$T_s\$ to reach the size \$s+1\$ is given by:
$$T_s=2s(s+1)$$
We keep track of our current size in \$s\$ and of what we've eaten so far in \$t\$ (we start with \$t=1\$, so this is actually off by \$1\$).
For each fish \$x\$ in the shoal, assuming it's sorted from smallest to biggest:

we add \$x\$ to \$t\$ (i.e. we eat the fish) whenever we have \$s\ge x\$
we increment \$s\$ (i.e. we grow in size) if \$t > T_s\$


05AB1E, 14 bytes
∞v®yÒgm=Ox<.±,

Try it online!
My first non-trivial 05AB1E answer! Happy for suggestions to improve it.
The code prints two interleaved sign sequences, both related to the Pólya conjecture. In 1919, George Pólya conjectured that the majority (no less than half) of positive integers up to any finite limit \$\ge2\$ have an odd number of prime factors, counted with multiplicity. Mathematically, the summatory Liouville function \$L(n)\$ (A002819) was posited to satisfy the inequality
$$
L(n)=\sum_{k=1}^n\lambda(k)\le0\
$$
for all \$n\ge2\$, wherein
$$
\lambda(k)=(-1)^{\Omega(k)}=\begin{cases}-1,\ \text{$k$ has an odd number of prime factors}\\\phantom{-}1,\ \text{$k$ has an even number of prime factors}\end{cases}
$$
is the Liouville function (A008836), related to the parity of the number of prime factors of \$k\$, and \$\Omega(k)\$ is the prime-factor-counting omega function that respects multiplicity.
The Pólya conjecture was shown to be false in 1958 when Brian Haselgrove proved the existence of an enormous counterexample near \$n=\exp(831.847)\approx1.845\times10^{361}\$. Subsequently, it has been shown that the smallest counterexample is \$n=906\,150\,257\$, and that the conjecture fails for most values of \$n\$ in the range \$906\,150\,257\le n \le 906\,488\,079\$. It is also now known that \$L(n)\$ changes sign infinitely often.
The code prints two values for each integer \$n\ge1\$:
$$
\DeclareMathOperator{\sgn}{sgn}
\begin{gather}
\lambda(n), \tag{1} \\
\sgn\bigl[2L(n)-1\bigr]. \tag{2}
\end{gather}
$$
The first value is the \$n\$th term of A008836. The second value, chosen to avoid zeros in \$L(n)\$, is (arguably) more interesting. Given the results quoted above, we see that sequence \$(2)\$ alternates between \$-1\$ and \$1\$ infinitely often. However, of its first \$906\,150\,257\$ values, only two (the first and the last) are \$1\$; the intervening \$906\,150\,255\$ values are all \$-1\$.
Commented code
∞v             # iterate over all positive integers y
  ®            # push -1
   yÒ          # push list of prime factors of y (with duplicates)
     g         # length of this list; yields Ω(y)
      m        # exponentiate top two stack items; yields -1**Ω(y) = λ(y)
       =       # print λ(y), keeping it on the stack
        O      # sum the stack; yields L(y)
         x<    # push 2*L(y)-1, keeping L(y) on the stack
           .±, # print the sign


APL (Dyalog Extended), 34 32 bytes (SBCS)

Anonymous tacit prefix function. Requires ⎕IO←0 (zero-based indexing).
⌊/{⍺-1-⍸⌂life 0,∘⌽∘⍉⍣4⍸⍣¯1∧⍵-⍺}⊢

Try it online!
⌊/{…}⊢ call the following anonymous lambda with the smallest existing x and y coordinates as left argument (⍺) and the full list as right argument (⍵):
 ⍵-⍺ subtract smallest point from all points (scales so every number is non-negative)
 ∧ sort ascending
 ⍸⍣¯1 generate a Boolean matrix with 1s in those positions (lit. inverse of "ɩndices of 1s")
 0…⍣4 repeat four times with zero as left argument:
  …∘⍉ transpose, then
   …∘⌽ mirror, then (this constitutes a 90° clockwise turn)
    …, concatenate zeros to the left edge
 ⌂life compute the next Game of Life generation
 ⍸ ɩndices of 1s
 1- subtract those from 1
 ⍺- subtract those from the offset of the lowest x and y coordinates


C: 414298141056 draws found in about 5 2.5 minutes.
Just simple depth-first search with a symmetry-aware transposition table. We use the symmetry of attributes under permutation and the 8-fold dihedral symmetry of the board.
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef uint16_t u8;
typedef uint16_t u16;
typedef uint64_t u64;

#define P(i, j) (1 << (4 * (i) + (j)))

#define DIAG0 (P(0, 0) | P(1, 1) | P(2, 2) | P(3, 3))
#define DIAG1 (P(3, 0) | P(2, 1) | P(1, 2) | P(0, 3))

u64 rand_state;

u64 mix(u64 x) {
    u64 a = x >> 32;
    u64 b = x >> 60;
    x ^= (a >> b);
    return x * 7993060983890856527ULL;
}

u64 rand_u64() {
    u64 x = rand_state;
    rand_state = x * 6364136223846793005ULL + 1442695040888963407ULL;
    return mix(x);
}

u64 ZOBRIST_TABLE[(1 << 16)][8];

u16 transpose(u16 x) {
    u16 t = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (x & P(j, i)) {
                t |= P(i, j);
            }
        }
    }
    return t;
}

u16 rotate(u16 x) {
   u16 r = 0;
   for (int i = 0; i < 4; i++) {
       for (int j = 0; j < 4; j++) {
           if (x & P(3 - j, i)) {
                r |= P(i, j);
            }
       }
   }
   return r;
}

void initialize_zobrist_table(void) {
    for (int i = 0; i < 1 << 16; i++) {
        ZOBRIST_TABLE[i][0] = rand_u64();
    }
    for (int i = 0; i < 1 << 16; i++) {
        int j = i;
        for (int r = 1; r < 8; r++) {
            j = rotate(j);
            if (r == 4) {
                j = transpose(i);
            }
            ZOBRIST_TABLE[i][r] = ZOBRIST_TABLE[j][0];
        }
    }
}

u64 hash_board(u16* x) {
    u64 hash = 0;
    for (int r = 0; r < 8; r++) {
        u64 h = 0;
        for (int i = 0; i < 8; i++) {
            h += ZOBRIST_TABLE[x[i]][r];
        }
        hash ^= mix(h);
    }
    return mix(hash);
}

u8 IS_WON[(1 << 16) / 8];

void initialize_is_won(void) {
    for (int x = 0; x < 1 << 16; x++) {
        bool is_won = false;
        for (int i = 0; i < 4; i++) {
            u16 stride = 0xF << (4 * i);
            if ((x & stride) == stride) {
                is_won = true;
                break;
            }
            stride = 0x1111 << i;
            if ((x & stride) == stride) {
                is_won = true;
                break;
            }
        }
        if (is_won == false) {
            if (((x & DIAG0) == DIAG0) || ((x & DIAG1) == DIAG1)) {
                is_won = true;
            }
        }
        if (is_won) {
            IS_WON[x / 8] |= (1 << (x % 8));
        }
    }
}

bool is_won(u16 x) {
    return (IS_WON[x / 8] >> (x % 8)) & 1;
}

bool make_move(u16* board, u8 piece, u8 position) {
    u16 p = 1 << position;
    for (int i = 0; i < 4; i++) {
        bool a = (piece >> i) & 1;
        int j = 2 * i + a;
        u16 x = board[j] | p;
        if (is_won(x)) {
            return false;
        }
        board[j] = x;
    }
    return true;
}

typedef struct {
    u64 hash;
    u64 count;
} Entry;

typedef struct {
    u64 mask;
    Entry* entries;
} TTable;

Entry* lookup(TTable* table, u64 hash, u64 count) {
    Entry* to_replace;
    u64 min_count = count + 1;
    for (int d = 0; d < 8; d++) {
        u64 i = (hash + d) & table->mask;
        Entry* entry = &table->entries[i];
        if (entry->hash == 0 || entry->hash == hash) {
            return entry;
        }
        if (entry->count < min_count) {
            min_count = entry->count;
            to_replace = entry;
        }
    }
    if (to_replace) {
        to_replace->hash = 0;
        to_replace->count = 0;
        return to_replace;
    }
    return NULL;
}

u64 count_solutions(TTable* ttable, u16* board, u8* pieces, u8 position) {
    u64 hash = 0;
    if (position <= 10) {
        hash = hash_board(board);
        Entry* entry = lookup(ttable, hash, 0);
        if (entry && entry->hash) {
            return entry->count;
        }
    }
    u64 n = 0;
    for (int i = position; i < 16; i++) {
        u8 piece = pieces[i];
        u16 board1[8];
        memcpy(board1, board, sizeof(board1));
        u8 variable_ordering[16] = {0, 1, 2, 3, 4, 8, 12, 6, 9, 5, 7, 13, 10, 11, 15, 14};
        if (!make_move(board1, piece, variable_ordering[position])) {
            continue;
        }
        if (position == 15) {
            n += 1;
        } else {
            pieces[i] = pieces[position];
            n += count_solutions(ttable, board1, pieces, position + 1);
            pieces[i] = piece;
        }
    }
    if (hash) {
        Entry* entry = lookup(ttable, hash, n);
        if (entry) {
            entry->hash = hash;
            entry->count = n;
        }
    }
    return n;
}

int main(void) {
    TTable ttable;
    int ttable_size = 1 << 28;
    ttable.mask = ttable_size - 1;
    ttable.entries = calloc(ttable_size, sizeof(Entry));
    initialize_zobrist_table();
    initialize_is_won();
    u8 pieces[16];
    for (int i = 0; i < 16; i++) {pieces[i] = i;}
    u16 board[8] = {0};
    printf("count: %lu\n", count_solutions(&ttable, board, pieces, 0));
}

Measured score (@wvdz):
$ clang -O3 -march=native quarto_user1502040.c
$ time ./a.out
count: 414298141056

real    1m37.299s
user    1m32.797s
sys     0m2.930s

Score (user+sys): 1m35.727s


Jelly, (8?) 9 bytes

Ỵ=”|Sḟ0m2

A monadic link accepting a list of characters as specified and returning a list of integers.

Note: 8 bytes if a list of strings, one per line, was really intended to be an allowed input format - just remove the Ỵ.

Try it online!

How?

Ỵ=”|Sḟ0m2 - Link: list of characters, s
Ỵ         - split at newlines
  ”|      - literal '|'
 =        - equals (vectorises)
    S     - sum (vectorises, hence counts the number of '|' in every column)
     ḟ0   - filter out zeros (only keep the results from the sides of the towers)
       m2 - modulo index with 2 (keep only the left side measurements)


Print E=mc² or E=mc^2, by using the right side of this equation

C, 66 59 57 bytes
Ignore the compiler warnings. It should work OK as long as you compile it on a big little-endian machine. This code could probably be made a lot shorter on a 64-bit machine, but I'm unable to test:
main(){long long m=1130224008533LL,c=7,E=m*c*c;puts(&E);}

9 fewer characters thanks to @Adam Davis and @Michael :-)


Wolfram Language (Mathematica), 124 113 101 bytes
Flatten@{s=⌈2#⌉;q=Range[r=2s+1];g=Mod[q s-s,r];{Sort@g[[#+1;;]],g[[;;#]]}&~Array~r,Table[q,s^3]}&

Try it online!
NOTE: The TIO output is not the actual list because it would be very long. The wrapper function on TIO tells you the number of page faults for two cache capacities.
For the actual list: Try it online!
Related: arXiv:1003.1336
How?
Let's assume a situation where we have two cache capacities, 3 and 4.
Also, let's say the 3-cache has {4, 2, 5} paged, and 4-cache has {5, 4, 3, 2} paged. Then, let's try paging {1, 2, 3, 4, 5, 1, 2, 3, 4, 5}:
page  3-cache   4-cache
      {4,2,5}  {5,4,3,2}
  1   {1,4,2}  {1,5,4,3}
  2   {1,4,2}  {2,1,5,4}
  3   {3,1,4}  {3,2,1,5}
  4   {3,1,4}  {4,3,2,1}
  5   {5,3,1}  {5,4,3,2}
  1   {5,3,1}  {1,5,4,3}
  2   {2,5,3}  {2,1,5,4}
  3   {2,5,3}  {3,2,1,5}
  4   {4,2,5}  {4,3,2,1}
  5   {4,2,5}  {5,4,3,2}

The 3-cache had 5 page faults, while the 4-cache had 10. We also returned to our original state.
Here, if we repeat paging {1, 2, 3, 4, 5}, we would asymptotically reach the ratio of 2.
We can extend this phenomenon to higher cache capacities so that we can page {1, 2, 3, ... , 2n + 1} and end up with any ratio.


Integer triangles with perimeter less than n

Jelly, 28 27 25 23 bytes

pḶŒcÆḊÐfḅı;I$€AṢ€QS€<¹S

Try it online!

How it works

pḶŒcÆḊÐfḅı;I$€AṢ€QS€<¹S  Main link. Argument: n

 Ḷ                       Unlength; yield [0,...,n-1].
p                        Take the Cartesian product of [1,...,n] and [0,...,n-1].
  Œc                     Take all combinations of the resulting pairs.
                         The result are of the form [[a, b], [c, d]].
    ÆḊÐf                 Filter by determinant; keep only pairs of pairs for which
                         the determinant (ad - bc) is non-zero, i.e., those such
                         that [0, 0], [a, b], and [c, d] are not collinear.
        ḅı               Convert each pair [a, b] from base i (imaginary unit) to
                         integer, mapping it to ai + b.
             €           For each pair of complex numbers [p, q]:
          ;I$              append their forward differences, yielding [p, q, p-q].
              A          Take the absolute value of each resulting complex number.
               Ṣ€        Sort each resulting array of side lengths.
                 Q       Unique; remove duplicates.
                  S€     Take the sum of each array, computing the perimeters.
                    <¹   Compare them with n.
                      S  Take the sum of the resulting Booleans.


Jelly, 33 32 37 35 34 bytes

bug found, horrible fix +5 bytes, better fix - 2 bytes, using a trick of Adnan's I saw here for -1 more.

“({[<“)}]>”Z;@WœṣF¥/µÐLO‘&2µIṀ>0ȯQ

Return values:

prepends [2]
 appends [0]
    both [2,0]
 neither 1

(Invalid input returns spurious results, although valid Brain-flack, returns [].)

Try it online! - a test suite (prints mushed representations, so 20 for [2,0], and ignores lines containing any -).


C, 127 characters, a rather obvious solution:

main(int c,char**v){
#pragma omp parallel for num_threads(c)
for(int i=1;i<c;++i){int x=atoi(v[i]);sleep(x);printf("%d ",x);}}

(Compiled with gcc -std=c99 -fopenmp sort.c and ignoring all warnings.)


Drop of Chaos (Constructing a Minimally Aperiodic Sequence)

Retina, 86 bytes - 5 = 81

$
_
(r`^(?<-2>.)+_((.)+)\b$
$1!
\b$
0
3#
#
0#
1
1#
2
2#
3
)r`\1(?<-2>.)*((.)+)$
$0#
!
<empty>

Where <empty> represents an empty trailing line. You can run the above code from a single file with the -s flag.

The input should be given in unary, e.g. 111111. I haven't tested it for output on the order of thousands yet - two of the regexes might get a bit slow after a while - but it can easily handle a couple of hundred in a few seconds.

Explanation

This is a simple backtracking solution.

Append a 0.
While the current sequence is invalid, remove all trailing 3s and increment the last non-3.
Repeat until we have a valid sequence of the desired length.

This backtracking is implemented by a loop of regex substitutions which aborts once the string remains unchanged through one iteration.

$
_

This appends a _ to the input, which is used to separate the unary input from the sequence we're building.

(r`^(?<-2>.)+_((.)+)\b$
$1!

This is the first substitution in the loop (indicated by the leading ().  The regex matches if a) there is a word character (i.e. a digit) at the end the string (which means the string is valid - we'll see below that invalid sequences are marked with a trailing #) and b) there are at least as many characters in the sequence as in the input (this is checked using balancing groups). If that's the case, we remove the input and append a !. This ! serves to make all regexes in the loop fail, such that it terminates.

\b$
0

If there is a word character at the end (i.e. the sequence is valid, and the loop wasn't terminated by the previous step), append a 0.

3#
#

If (instead) the sequence had been marked invalid and ended in 3, we remove that 3 (but leave the sequence as invalid, because there's no possible continuation for the current prefix... so the next character needs to be backtracked as well).

0#
1
1#
2
2#
3

If the sequence is marked invalid and any digit other than 3 is at the end, we increment the digit and remove the marker.

)r`\1(?<-2>.)*((.)+)$
$0#

The last substitution in the loop (as indicated by the )). It checks whether the string ends in ABA (where B is not longer than A but potentially empty). The relative lengths of A and B are again checked using balancing groups, and the repetition of A is checked with a simple backreference.

If this regex matches, we mark the sequence invalid by appending #.

!
<empty>

Once the loop terminates, all we need to do is remove the ! and are then left with the desired output.


The most beautiful version, you say? Then, let's try this one in...

Shakespeare Programming Language

The Marvelously Insane FizzBuzzJazz Program.

Lady Capulet, an old bossy woman that loves to count.
The Archbishop of Canterbury, an old fart who adores to spit out letters.

          Act I: The only one of them.

          Scene I: The Archbishop of Canterbury is a bastard.

[Enter The Archbishop of Canterbury and Lady Capulet]

The Archbishop of Canterbury:
 You are nothing!

          Scene II: Count, Lady Capulet, count.

The Archbishop of Canterbury:
 You are as beautiful as the sum of yourself and a cat!

Lady Capulet:
 Am I worse than the square of the product of the sum of a warm gentle flower and a rose
 and my pretty angel?

The Archbishop of Canterbury:
 If not, let us proceed to Scene VIII.

          Scene III: Fizzing to no end!

The Archbishop of Canterbury:
 Is the remainder of the quotient between yourself and the sum of a happy cow and a
 chihuahua as good as nothing?

Lady Capulet:
 If not, let us proceed to Scene IV. Thou art as handsome as the sum of the sum of
 the sweetest reddest prettiest warm gentle peaceful fair rose and a happy proud kindgom
 and a big roman. Speak thy mind!

 Thou art as fair as the sum of thyself and a honest delicious cute blossoming peaceful
 hamster. Thou art as cunning as the sum of the sum of an embroidered King and a horse
 and thyself. Speak thy mind!

 Thou art as amazing as the sum of the sum of a good happy proud rich hero and a hair and
 thyself! Speak thy mind.

 Speak your mind!

          Scene IV: Milady, there is jazz in thy robe.

The Archbishop of Canterbury:
 Is the remainder of the quotient between yourself and a proud noble kingdom as good as
 nothing?

Lady Capulet:
 If not, let us proceed to Scene V. You are as charming as the sum of the sum of a noble
 cunning gentle embroidered brave mighty King and a big warm chihuahua and an amazing
 pony! Speak your mind!

 You are as prompt as the sum of yourself and a big black sweet animal. You are as noble
 as the sum of the sum of a gentle trustworthy lantern and yourself and a hog. Speak your
 mind!

 You are as bold as the sum of the sum of yourself and a good delicious healthy sweet
 horse and my smooth cute embroidered purse. You are as peaceful as the sum of a flower
 and yourself. Speak your mind.

 Speak your mind!

          Scene V: Buzz me up, Scotty!

The Archbishop of Canterbury:
 Is the remainder of the quotient between yourself and the sum of a gentle happy cow and a
 chihuahua as good as nothing?

Lady Capulet:
 If not, let us proceed to Scene VI. Thou art as handsome as the sum of the sweetest
 reddest prettiest warm gentle peaceful fair rose and a small town. Speak your mind!

 You are as prompt as the sum of yourself and a big healthy peaceful fair rich kingdom.
 You are as loving as the sum of the sum of an embroidered King and a horse and thyself.
 You are as amazing as the sum of yourself and a cute fine smooth sweet hamster. Speak
 your mind!

 You are as prompt as the sum of the sum of yourself and an amazing cunning Lord and a
 hair. Speak your mind.

 Speak your mind!

The Archbishop of Canterbury:
 Let us proceed to Scene VII.

          Scene VI: Output or die!

The Archbishop of Canterbury:
 Open your heart!

          Scene VII: Oh, to jump the line.

Lady Capulet:
 You are as handsome as the sum of a proud noble rich kingdom and a rural town. Speak your
 mind! You are as gentle as the sum of the sum of yourself and a green mistletoe and my
 father. Speak your mind!

The Archbishop of Canterbury:
 We must return to Scene II.

          Scene VIII: Goodbye, cruel world!

[Exeunt]

So, after my struggle with SPL here, I felt like I had to do at least one submission with it on any challenge. And this is it.

So, what's all this then?

So, first, we declare the variables we're going to use throughout the program, which must come from Shakespeare plays. Fed up of Romeo, Juliet, Ophelia and Othello, I went up with The Archbishop of Canterbury and Lady Capulet. Their descriptions, as well as the Acts'/Scenes' titles, are disgarded by the parser, so you can put there pretty much anything you like.

So, let's make some king of translation to something a little less gibberishy.

Act I, Scene I

Begin
Lady Capulet = 0;

Act I is pretty straightforward: we initialize our variable with 0.

Act I, Scene II

Lady Capulet += 1;
if(Lady Capulet < Math.pow((2*2*1+1)*(2*1),2))
continue;
else
goto Scene VIII;

We increment Lady Capulet's value and compare it with 100 (yes, that whole sentence serves solely to get the number 100); if it's not smaller, we jump to Scene VIII (the end); otherwise, we continue on to the next Scene.

Act I, Scene III

if(Lady Capulet % (2+1) == 0)
continue;
else
goto Scene IV;
The Archbishop of Canterbury = 2*2*2*2*2*2*1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2*2*2*2*1;
The Archbishop of Canterbury += 2*1+1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2*2*2*1+1;
System.out.print((char)The Archbishop of Canterbury);
System.out.print((char)The Archbishop of Canterbury);

First, we see if the modulus of the division by 3 is 0; if it's not, we jump to Scene IV; if it is, we begin doing arithmetic operations and storing them on the Archieperson, outputting them in character form once we find the one we're looking for. Yes, in the end, the idea is to get Fizz.

Act I, Scene IV

if(Lady Capulet % (2*2) == 0)
continue;
else
goto Scene V;
The Archbishop of Canterbury = 2*2*2*2*2*2*1+2*2*1+2*1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2*2*1;
The Archbishop of Canterbury += 2*2*1+(-1);
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2*2*2*1+2*2*2*1;
The Archbishop of Canterbury += 1;
System.out.print((char)The Archbishop of Canterbury);
System.out.print((char)The Archbishop of Canterbury);

First checks if the modulus of the division by 4 is 0, then continues as the same scene as before, for Jazz.

Act I, Scene V

if(Lady Capulet % (2*2+1) == 0)
continue;
else
goto Scene VI;
The Archbishop of Canterbury = 2*2*2*2*2*2*1+2*1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2*2*2*2*1;
The Archbishop of Canterbury += 2*1+1;
The Archbishop of Canterbury += 2*2*2*2*1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2+1;
System.out.print((char)The Archbishop of Canterbury);
System.out.print((char)The Archbishop of Canterbury);
goto Scene VII;

Functions like the previous two, checking if the modulus of the division by 5 returns 0, then attempts to write Buzz; the only difference is that, in the end, we skip a Scene.

Act I, Scene VI

System.out.print(Lady Capulet);

To reach this Scene, the number assumed by Lady Capulet must not have been neither Fizz nor Jazz nor Buzz; so, we output it in numeric form.

Act I, Scene VII

The Archbishop of Canterbury = 2*2*2*1+2*1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*1+1;
System.out.print((char)The Archbishop of Canterbury);
goto Scene II;

So, this is the only way I found to jump to the next line: output, first, a CR, then a LF; then, we return to Scene II, to that we can continue with the program.

Act I, Scene VIII

End.

Straightforward enough.

I'm still trying to see if I could show this running online, but I can't find an online compiler - the one I know doesn't seem to combine well with any program except the one already loaded, or maybe there's some kind of problem with the interface between the keyboard and the chair...

Update 1:

After mathmandan's comment, I edited the order of Jazz's and Buzz's scenes. It had to be done.


Tell me when the next post is... WebSockets!

Clojure with gniazdo, 126, 204, 203 bytes
+78 bytes to handle reacting to heartbeat messages
-1 byte by changing from indexing the string converted to a vector, to just using nth. I was expecting more of a gain from that :/

(use '[gniazdo.core])(fn[t](let[a(atom 0)s #(send-msg @a %)o(connect"ws://qa.sockets.stackexchange.com":on-receive #(if(=((vec %)11)\h)(s"hb")(println %)))](reset! a o)(s(str"1-questions-newest-tag-"t))))

An anonymous function that takes a string tag, and prints the raw JSON results as they're received, while responding to heartbeats.
To test if the received message is a heartbeat, I'm testing if the 12th character of the response is the character h. After looking over this page, it seems impossible for h to be the 12th character without the response being a heartbeat. If this isn't the case, I can try to figure out a workaround.
(ns bits.golf.web-sock
  (:require [gniazdo.core :as g]))

(defn new-tag-posts [^String tag]
  (let [; A mutable state to hold the sock.
        ; Necessary since the sock's callback requires a reference to the
        ;  sock itself
        sock-a (atom nil)

        ; Shortcut function to save bytes
        send #(g/send-msg @sock-a %)

        handler #(if (= (nth % 11) \h) ; If the 12th character (at index 11) is 'h'
                   (send "hb") ; respond to the heartbeat
                   (println %)) ; else print the JSON

        sock (g/connect "ws://qa.sockets.stackexchange.com"
                        :on-receive handler)]

    ; Set the mutable state to the created socket
    (reset! sock-a sock)

    ; Subscribe to the given tag
    (send (str "1-questions-newest-tag-" tag))))


Python 2, 123 bytes
c=map(input().count,"OWHUFXSGIQ")
i=4
for j in"71735539994":c[i*2]-=c[int(j)];i=-~i%5
s=""
for n in c:i+=1;s+=`i`*n
print s

A full program taking quoted input and printing John's number.
Try it online! or see a test-suite
How?
Let's work with the example "NEONSEXTOWNII" (to yield 1269, and be somewhat Leisure Suite Larry-esque!)
First c=map(input().count,"OWHUFXSGIQ") takes input and counts the number of each of OWHUFXSGIQ - these are letters that appear in each number in ascending order, with 2,4,6, and 8 having their "own" letters (WUXG), plus an extra letter, Q to append a zero to the the end and make the length of the resulting list even. For the example:
[2,1,0,0,0,1,1,0,2,0] <- c
 O W H U F X S G I Q  <- is the counts of these letters
 1 2 3 4 5 6 7 8 9 0  <- which "relate to" these digits in John's number
   2   4   6   8   0  <- these will be correct as the letters are unique to their words

The entries for 1, 3, 5, 7, and 9 need adjusting to correct the abundance of the other letters. This is performed by the next loop:
i=4
for j in"71735539994":c[i*2]-=c[int(j)];i=-~i%5

Note that the entries to adjust are alternate ones (1,3,5,7,9,1,3,5,...), so we can add two to an index variable at each step and modulo by 10 to stay in range if we need to traverse more than once (which we do). To save some bytes we can increment by one and modulo by 5 and use double the index.
Since the adjustments for 9 require the most work we start there - it resides at index 8 so we start at i=4.
The string "71735539994" then gives the indexes, j, of the values to remove at each stage (where we have ensured the ninth index will contain zero by using "Q" when creating c); c[i*2]-=c[int(j)] performs each individual adjustment and i=-~i%5 moves i to the next index (where -~i is -(-1-i) or i+1 saving parentheses (i+1)%5) keeping i*2 within the bounds of c.
Thus we first subtract the number at index j=7 from that at index i*2=8, subtracting the number of "G"s counted from the number of "I"s, adjusting the "NINE" count down by the (correct) number of "EIGHT"s (which also has an "I"). We then move onto i=0 (-~4%5 = (4+1)%5 = 0), referencing index i*2 = 0 which is for "ONE" and subtract the value found at index j=1 the entry counting "W" and hence "TWO", adjusting the count of "O"s down. By the end of the loop we have the corrected counts:
[1,1,0,0,0,1,0,0,1,0] <- c   (for 1223333448 it would be: [1,2,4,2,0,0,0,1,0,0])
 1 2 3 4 5 6 7 8 9 0

so all that remains is to print out what c now represents (1269). i is now back at 0, so we increment it at the start of the loop and use it as our digit:
s=""
for n in c:i+=1;s+=`i`*n
print s

The back ticks, `i`, are Python2 shorthand for repr(i) which gets a string representation of an object (the digit character in question as a string) and multiplying a string by a number creats a new string of that many repeats (here we only show n=0 turning `i` from say "5" to "" and n=1 turning keeping say "6" as "6", but it also works for larger positive integers, so "3"*4 becomes "3333" for example.)


GolfScript, 34 32 chars

44,{84+2base(;{'-#'=}/@\n.}%2/n*

Turns out that there are shorter solutions than simply generating all 64 patterns and filtering out the bad ones.  In fact, by suitably mapping bits to grid positions, it's possible to map all valid (non-empty) patterns to a consecutive range of numbers, as this program does.

Specifically, the mapping I use is:

5 4
3 1
2 0

where the numbers denote the bit position (starting from the least significant bit 0) mapped to that position in the grid.  With this mapping, the valid grids correspond to the numbers 20 to 63 inclusive.

This is almost the same as the obvious mapping obtained by writing out the 6-bit number in binary and adding line breaks between every second bit, except that the bits 1 and 2 are swapped — and indeed, that's exactly how my program computes it.  (I also add 64 to the numbers before converting them to binary, and then strip the extra high bit off; that's just to zero-pad the numbers to 6 bits, since GolfScript's base would otherwise not return any leading zeros.)

Ps. Online demo here. (Server seems overloaded lately; if you get a timeout, try again or download the interpreter and test it locally.)

Edit: Managed to save two chars by avoiding unnecessary array building and dumping.  Phew!


Vim, 7 bytes

1
2
3
4

Try it online!

As far as I can tell, this complies with all of the rules. In vim by default, the empty program prints out all of the input. Since

<N><CR>

Is a noop, nothing changes the input text, and since each input matches the desired output, this same approach works with any number of lines.


.NET flavor, score:2
Regex        Modifiers  Replacement  Repeat?
<empty>      <none>     9876543210   No
<see below>  x          <empty>      No

I'm not bothered to golf it yet, and x is just for ignoring whitespaces.
It firstly insert 9876543210 at each position, then delete the original characters and the characters those are not the current digit of the sum.
The big regex (1346 bytes without whitespaces and comments):
# If the length of the left number <= right number, delete every digit on the left.
.(?=.*,(?<=^(?<len>.)*,)(?<-len>.)*(?(len)(?!)))|

# Do the opposite if it is not the case.
.(?<=(?(len)(?!))(?<-len>.)*(?=(?<len>.)*$),.*)|

# Remove leading zeros.
(?<=(^|,).{9})0|

# Delete everything that is not the current digit of the sum.
.(?!
    # For digits in the left part:
    (?<cur>.){0,9}               # cur = the matched digit
    (?=(.{11})*,)                # and find the position before the next digit.
    (?<first>)                   # first = true
    (                            # Loop on the less significant digits:
        (?<cur>){10}             # cur += 10
        (?<=                     # cur -= the current digit in this number.
            (
                0|^|
                1(?<-cur>)|
                2(?<-cur>){2}|
                3(?<-cur>){3}|
                4(?<-cur>){4}|
                5(?<-cur>){5}|
                6(?<-cur>){6}|
                7(?<-cur>){7}|
                8(?<-cur>){8}|
                9(?<-cur>){9}
            )
            .{10}
        )
        (?=
            (?<pos>.{11})*,      # pos = which digit it is.
            .*$(?<=              # cur -= the current digit in the other number.
                (
                    0|,|
                    1(?<-cur>)|
                    2(?<-cur>){2}|
                    3(?<-cur>){3}|
                    4(?<-cur>){4}|
                    5(?<-cur>){5}|
                    6(?<-cur>){6}|
                    7(?<-cur>){7}|
                    8(?<-cur>){8}|
                    9(?<-cur>){9}
                )
                .{10}
                (?(pos)(?!))     # Assert pos = 0.
                                 # Skip pos input digits from the end.
                                 # But stop and set pos = 0 if the comma is encountered.
                ((?<-pos>\d{11})|(?<=(?>(?<-pos>.)*),.{10}))*
            )
        )
        (?(first)                # If first:
            (?>((?<-cur>){10})?) #  cur -= 10 in case there is no carry.
                                 #  Assert cur = 0 or 1, and if cur = 1, set cur = 10 as carry.
            (?(cur)(?<-cur>)(?(cur)(?!))(?<cur>){10})
            (?<-first>)          #  first = false
        |                        # Else:
                                 #  cur is 10 or 20 at the beginning of an iteration.
                                 #  It must be 1 to 11 to make the equation satisfiable.
            (?<-cur>)            #  cur -= 1
            (?(cur)              #  If cur > 0:
                                 #   cur -= max(cur, 9)
                (?(cur)(?<-cur>)){9}
                (?(cur)          #   If cur > 0:
                                 #    Assert cur = 1 (was 11) and set cur = 10.
                    (?<-cur>)(?(cur)(?!))(?<cur>){10}
                |                #   Else:
                    .*(?=,)      #    cur was 2 to 10, break from the loop.
                )
            )                    #  Else cur is 0 (was 1) and do nothing.
        )
        (.{11}|,)                # Jump to the next digit.
    )*(?<=,)(?(cur)(?!))         # End the loop if it is the last digit, and assert cur = 0.
|
    # Do the same to the right part. So the sum will be calculated two times.
    # Both are truncated to the original length of the number on that side + 1.
    # Only the sum on the longer side will be preserved in the result.
    (?<cur>\d){0,9}
    (?=(\d{11})*$)
    (?<first>)
    (
        (?<cur>){10}
        (?<=
            (
                0|,|
                1(?<-cur>)|
                2(?<-cur>){2}|
                3(?<-cur>){3}|
                4(?<-cur>){4}|
                5(?<-cur>){5}|
                6(?<-cur>){6}|
                7(?<-cur>){7}|
                8(?<-cur>){8}|
                9(?<-cur>){9}
            )
            .{10}
        )
        (?=
            (?<pos>.{11})*$
            (?<=
                (
                    0|^|
                    1(?<-cur>)|
                    2(?<-cur>){2}|
                    3(?<-cur>){3}|
                    4(?<-cur>){4}|
                    5(?<-cur>){5}|
                    6(?<-cur>){6}|
                    7(?<-cur>){7}|
                    8(?<-cur>){8}|
                    9(?<-cur>){9}
                )
                .{10}
                (?(pos)(?!))
                ((?<-pos>\d{11})|(?<=^.{10})(?=(?>(?<-pos>.)*)))*
                ,.*
            )
        )
        (?(first)
            (?>((?<-cur>){10})?)
            (?(cur)(?<-cur>)(?(cur)(?!))(?<cur>){10})
            (?<-first>)
        |
            (?<-cur>)
            (?(cur)
                (?(cur)(?<-cur>)){9}
                (?(cur)
                    (?<-cur>)(?(cur)(?!))(?<cur>){10}
                |
                    .*$(?<end>)
                )
            )
        )
        (.{11}|$(?<end>))
    )*(?<-end>)(?(cur)(?!))
)

This made me think of the final level of Manufactoria... But I think .NET regex, which is obviously no longer "regular", can solve any problems in PH. And this is just an algorithm in L.


Haskell, 64, 63, 56, 55 bytes

c is an infinite list of all strings composed of 97..122 in shortlex order.
\x y -> last$fst$span(/=x)y gives the predecessor of x in y

a b=last$fst$span(/=b)c
c=[]:[d++[e]|d<-c,e<-[97..122]]

Try it online!

1 byte saved by using code points: [97..122] vs. ['a'..'z']
9 bytes saved by ovs
1 bytes saved by Laikoni

Shortlex optimality

To get the lowest-ordered version of this code:

Each variable is chosen to be the smallest, front-to-back
The two lines are sorted (' ' < '=')


brainfuck, 32 bytes

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

Try it online!

I used @ as the operation, because its code point (64) is convenient.  U is also possible with the same byte count, using 3*85+1=256=0.

Explanation

The tape is used as a stack.  In each iteration of the main loop, the data pointer starts two cells right of the top of the stack.

,[                Take input and start main loop
  [->++++<<+>]    Push input, and compute 4*input
  >[              If 4*input is nonzero (and thus input is not @):
    [-]<<           Zero out this cell and move to top of stack
    [.[-]<]         Pop from stack and output until \0 is reached
  ]
  >,              Move pointer into the correct position.  If input was @, the earlier > pushed \0 onto the stack.
]


I want my book to be away from this table

Octave, 41 40 33 bytes
1 byte saved thanks to @Dennis

@(n)find(cumsum(.5./(1:9^n))>n,1)

Try it online!
Explanation
This uses the fact that harmonic numbers can be lower-bounded by a logarithmic function.
Also, the >= comparison can be replaced by > because harmonic numbers cannot be even integers (thanks, @Dennis!).
@(n)                                   % Anonymous function of n
                     1:9^n             % Range [1 2 ... 9^n]
                .5./(     )            % Divide .5 by each entry
         cumsum(           )           % Cumulative sum
                            >n         % Is each entry greater than n?
    find(                     ,1)      % Index of first true entry


C++ - somewhat random lines and then some

First some random lines

The first step of the algorithm randomly generates lines, takes for the target image an average of the pixels along this, and then calculates if the summed up square of rgb space distances of all pixels would be lower if we would paint the new line (and only paint it, if it is). The new lines color for this is chosen as the channel wise average of the rgb values, with a -15/+15 random addition.

Things that I noticed and influenced the implementation:

The initial color is the average of the complete image. This is to counter funny effects like when making it white, and the area is black, then already something as a bright green line is seen better, as it is nearer to black than the already white one.
Taking the pure average color for the line is not so good as it turns out to be unable to generate highlights by being overwritten by later lines. Doing a little random deviation helps a bit, but if you look at starry night, it fails if the local contrast is high at many places.

I was experimenting with some numbers, and chose L=0.3*pixel_count(I) and left m=10 and M=50. It will produce nice results starting at around 0.25 to 0.26 for the number of lines, but I chose 0.3 to have more room for accurate details.

For the full sized golden gate image, this resulted in 235929 lines to paint (for which it took a whopping 13 seconds here). Note that all images here are displayed in reduced size and you need to open them in a new tab/download them to view the full resolution.

Erase the unworthy

The next step is rather expensive (for the 235k lines it took about an hour, but that should be well within the "an hour for 10k lines on 1 megapixel" time requirement), but it is also a bit surprising. I go through all the previously painted lines, and remove those that do not make the image better. This leaves me in this run with only 97347 lines that produce the following image:

You probably need to download and compare them in an appropriate image viewer to spot most differences.

and start over again

Now I have a lot of lines that I can paint again to have a total of 235929 again. Not much to say, so here is the image:

short analysis

The whole procedure seems to work like a blurring filter that is sensitive to local contrast and object sizes. But it is also interesting to see where the lines are painted, so the program records these too (For each line, the pixel color will be made one step whiter, at the end the contrast is maximized). Here are the corresponding ones to the three colored above.

animations

And since we all love animations, here are some animated gifs of the whole process for the smaller golden gate image. Note that there is significant dithering due to gif format (and since creators of true color animation file formats and browser manufacturers are in war over their egos, there is no standard format for true color animations, otherwise I could have added an .mng or similar).

Some more

As requested, here are some results of the other images (again you might need to open them in a new tab to not have them downscaled)

Future thoughts

Playing around with the code can give some intresting variations.

Chose the color of the lines by random instead of being based on the average. You might need more than two cycles.
The code in the pastebin also contains some idea of a genetic algorithm, but the image is probably already so good that it would take too many generations, and this code is also too slow to fit into the "one hour" rule.
Do another round of erase/repaint, or even two...
Change the limit of where lines can be erased (e.g. "must make the image at lest N better")

The code

These are just the two main useful functions, the whole code doesn't fit in here and can be found at http://ideone.com/Z2P6Ls

The bmp classes raw and raw_line function do access pixels and lines respectively in an object that can be written to bmp format (It was just some hack lying around and I thought that makes this somewhat independent from any library).

The input file format is PPM

std::pair<bmp,std::vector<line>>  paint_useful( const bmp& orig, bmp& clone, std::vector<line>& retlines, bmp& layer, const std::string& outprefix, size_t x, size_t y )
{
        const size_t pixels = (x*y);
        const size_t lines = 0.3*pixels;
//      const size_t lines = 10000;

//      const size_t start_accurate_color = lines/4;

        std::random_device rnd;

        std::uniform_int_distribution<size_t> distx(0,x-1);
        std::uniform_int_distribution<size_t> disty(0,y-1);
        std::uniform_int_distribution<size_t> col(-15,15);
        std::uniform_int_distribution<size_t> acol(0,255);

        const ssize_t m = 1*1;
        const ssize_t M = 50*50;

        retlines.reserve( lines );

        for (size_t i = retlines.size(); i < lines; ++i)
        {
                size_t x0;
                size_t x1;

                size_t y0;
                size_t y1;

                size_t dist = 0;
                do
                {
                        x0 = distx(rnd);
                        x1 = distx(rnd);

                        y0 = disty(rnd);
                        y1 = disty(rnd);

                        dist = distance(x0,x1,y0,y1);
                }
                while( dist > M || dist < m );

                std::vector<std::pair<int32_t,int32_t>> points = clone.raw_line_pixels(x0,y0,x1,y1);

                ssize_t r = 0;
                ssize_t g = 0;
                ssize_t b = 0;

                for (size_t i = 0; i < points.size(); ++i)
                {
                        r += orig.raw(points[i].first,points[i].second).r;
                        g += orig.raw(points[i].first,points[i].second).g;
                        b += orig.raw(points[i].first,points[i].second).b;
                }

                r += col(rnd);
                g += col(rnd);
                b += col(rnd);

                r /= points.size();
                g /= points.size();
                b /= points.size();

                r %= 255;
                g %= 255;
                b %= 255;

                r = std::max(ssize_t(0),r);
                g = std::max(ssize_t(0),g);
                b = std::max(ssize_t(0),b);

//              r = acol(rnd);
//              g = acol(rnd);
//              b = acol(rnd);

//              if( i > start_accurate_color )
                {
                        ssize_t dp = 0; // accumulated distance of new color to original
                        ssize_t dn = 0; // accumulated distance of current reproduced to original
                        for (size_t i = 0; i < points.size(); ++i)
                        {
                                dp += rgb_distance(
                                                                                orig.raw(points[i].first,points[i].second).r,r,
                                                                                orig.raw(points[i].first,points[i].second).g,g,
                                                                                orig.raw(points[i].first,points[i].second).b,b
                                                                        );

                                dn += rgb_distance(
                                                                                clone.raw(points[i].first,points[i].second).r,orig.raw(points[i].first,points[i].second).r,
                                                                                clone.raw(points[i].first,points[i].second).g,orig.raw(points[i].first,points[i].second).g,
                                                                                clone.raw(points[i].first,points[i].second).b,orig.raw(points[i].first,points[i].second).b
                                                                        );

                        }

                        if( dp > dn ) // the distance to original is bigger, use the new one
                        {
                                --i;
                                continue;
                        }
                        // also abandon if already too bad
//                      if( dp > 100000 )
//                      {
//                              --i;
//                              continue;
//                      }
                }

                layer.raw_line_add(x0,y0,x1,y1,{1u,1u,1u});
                clone.raw_line(x0,y0,x1,y1,{(uint32_t)r,(uint32_t)g,(uint32_t)b});
                retlines.push_back({ (int)x0,(int)y0,(int)x1,(int)y1,(int)r,(int)g,(int)b});

                static time_t last = 0;
                time_t now = time(0);
                if( i % (lines/100) == 0 )
                {
                        std::ostringstream fn;
                        fn << outprefix + "perc_" << std::setw(3) << std::setfill('0') << (i/(lines/100)) << ".bmp";
                        clone.write(fn.str());
                        bmp lc(layer);
                        lc.max_contrast_all();
                        lc.write(outprefix + "layer_" + fn.str());
                }

                if( (now-last) > 10 )
                {
                        last = now;
                        static int st = 0;
                        std::ostringstream fn;
                        fn << outprefix + "inter_" << std::setw(8) << std::setfill('0') << i << ".bmp";
                        clone.write(fn.str());

                        ++st;
                }
        }
        clone.write(outprefix + "clone.bmp");
        return { clone, retlines };
}

void erase_bad( std::vector<line>& lines, const bmp& orig )
{
        ssize_t current_score = evaluate(lines,orig);

        std::vector<line> newlines(lines);

        uint32_t deactivated = 0;
        std::cout << "current_score = " << current_score << "\n";
        for (size_t i = 0; i < newlines.size(); ++i)
        {
                newlines[i].active = false;
                ssize_t score = evaluate(newlines,orig);
                if( score > current_score )
                {
                        newlines[i].active = true;
                }
                else
                {
                        current_score = score;
                        ++deactivated;
                }
                if( i % 1000 == 0 )
                {
                        std::ostringstream fn;
                        fn << "erase_" << std::setw(6) << std::setfill('0') << i << ".bmp";
                        bmp tmp(orig);
                        paint(newlines,tmp);
                        tmp.write(fn.str());
                        paint_layers(newlines,tmp);
                        tmp.max_contrast_all();
                        tmp.write("layers_" + fn.str());
                        std::cout << "\r i = " << i << std::flush;
                }
        }
        std::cout << "\n";
        std::cout << "current_score = " << current_score << "\n";
        std::cout << "deactivated = " << deactivated << "\n";

        bmp tmp(orig);

        paint(newlines,tmp);
        tmp.write("newlines.bmp");
        lines.clear();
        for (size_t i = 0; i < newlines.size(); ++i)
        {
                if( newlines[i].is_active() )
                {
                        lines.push_back(newlines[i]);
                }
        }
}


Javascript 838

The very first version, not optimized !
All rules are not fully observed, :-o

!function(){var f=require("readline").createInterface(process.stdin,process.stdout),g=[],h=function(){for(var b;!b||-1<g.indexOf(b);)b="A23456789TJQK".charAt(13*Math.random()|0)+"HDCS".charAt(4*Math.random()|0);g.push(b);return b},k=function(b){var a=0,d=0;for(z=b.length;z--;){var c=b[z].charAt(0);/[TJQK]/.test(c)?a+=10:/[2-9]/.test(c)?a+=+c:"A"==c&&(d++,a++)}for(;d--;)21>=a+10&&(a+=10);return a};(function(){var b=[],a=[],d=0,c=0;f.prompt();f.on("line",function(e){e=e.charAt(0);"H"==e&&(b.push(h()),
c=k(b),console.log("Your hand: "+b+" = "+c+" points"),21<c&&(console.log("LOSE"),process.exit(0)));if("S"==e){for(;17>(d=k(a));)a.push(h());console.log("My hand: "+a+" = "+d+" points");21<d||d<c?console.log("WIN"):d>c?console.log("LOSE"):console.log("DRAW");process.exit(0)}f.prompt()}).on("close",function(){process.exit(0)})})()}();

Execute it with nodeJS


Husk, 10 bytes
§ḟ¤≡ȯÖLgp→

Try it online!
Explantion
§ḟ       →     Find the first number starting from the input + 1 such that...
        p        The prime factorisation
       g         with equal elements grouped together
    ȯÖL          and sorted by length of groups
  ¤≡             has the same shape as the above applied to the input.


Python 3 (not 2)

Edit: I'll ungolf this in the morning, oops.

It's a perfectly normal A-star search. Right? Riiiiiiight?
Seems to work for all test cases.

def a(b,c,d):
    e,f,g=[],{},{}
    f[c]=0
    while f:
        h=sorted(f.keys(),key=lambda z:-f[z],reverse=True)[-1]
        if h==d:break
        e.append(h)
        for z in b[h]:
            if z in e:continue
            if z in f and f[z]>f[h]+b[z][h]:continue
            g[z]=h
            f[z]=f[h]+b[z][h]
        del f[h]
    i=[]
    j=d
    q=0
    while j!=c:
        i.append(j)
        q+=b[j][g[j]]
        j=g[j]
    return q,(i+[c])[::-1]
t,q=input().split(" ")
t=int(t)
q=q[:-1]
q=[i.split(",")for i in q.split(";")]
g={a:{}for a in __import__("functools").reduce(lambda zz,zy:zz+zy,[[v[0],v[2]]for v in q])}
for l in q:g[l[0]][l[2]]=g[l[2]][l[0]]=int(l[1])

r=a(g,'n','a')
print("time-good: %d, time-ours: %d" % (t, r[0]))
print("path: %s" % " -> ".join(r[1]))


JavaScript (ES6), 260 bytes

Takes input as an array of arrays of booleans. Returns a tree of 1-indexed majority gates or throws a recursion error (1) if no solution exists.

The main function f() recursively attempts to find a solution by calling the solver F() and incrementing the maximum nesting level m at each iteration.

(1) after a long time, and assuming infinite memory

f=(a,m)=>(F=(a,d,I=a[i=0].map(_=>++i),g=(a,b)=>b[1]?b.reduce((s,i)=>s+g(a,i),0)>1:a[b-1])=>I.find(i=>a.every(a=>g(a,i)))||d&&(I.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).some(b=>r=b.length==3&&F(a.map(a=>[...a,g(a,b)]),d-1,[...I,b]))&&r))(a,m)||f(a,-~m)

Demo

f=(a,m)=>(F=(a,d,I=a[i=0].map(_=>++i),g=(a,b)=>b[1]?b.reduce((s,i)=>s+g(a,i),0)>1:a[b-1])=>I.find(i=>a.every(a=>g(a,i)))||d&&(I.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).some(b=>r=b.length==3&&F(a.map(a=>[...a,g(a,b)]),d-1,[...I,b]))&&r))(a,m)||f(a,-~m)

test = a => console.log(JSON.stringify(f(a.split(',').map(s => [...s].map(c => c == 'T')))))

test('TFF')
test('TTF,TFT')
test('TTF,TFT,FTT')
test('TTTF,TTFT,TFTT,FTTT')
test('TTTFF,FTTFT,TFFFT')
test('TTTFFF,FTFTTF,TFFTFT')
test('TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT')

Example

Below is a validation table of the solution found for the last test case of the demo.

12345 | [5,[1,2,4],[3,4,[1,2,3]]]
------+-------------------------------------------------------------
TTTFF | [F,[T,T,F],[T,F,[T,T,T]]] --> [F,T,[T,F,T]] -> [F,T,T] --> T
TTFTF | [F,[T,T,T],[F,T,[T,T,F]]] --> [F,T,[F,T,T]] -> [F,T,T] --> T
TTFFT | [T,[T,T,F],[F,F,[T,T,F]]] --> [T,T,[F,F,T]] -> [T,T,F] --> T
TFTTF | [F,[T,F,T],[T,T,[T,F,T]]] --> [F,T,[T,T,T]] -> [F,T,T] --> T
TFTFT | [T,[T,F,F],[T,F,[T,F,T]]] --> [T,F,[T,F,T]] -> [T,F,T] --> T
TFFTT | [T,[T,F,T],[F,T,[T,F,F]]] --> [T,T,[F,T,F]] -> [T,T,F] --> T
FTTTF | [F,[F,T,T],[T,T,[F,T,T]]] --> [F,T,[T,T,T]] -> [F,T,T] --> T
FTTFT | [T,[F,T,F],[T,F,[F,T,T]]] --> [T,F,[T,F,T]] -> [T,F,T] --> T
FTFTT | [T,[F,T,T],[F,T,[F,T,F]]] --> [T,T,[F,T,F]] -> [T,T,F] --> T
FFTTT | [T,[F,F,T],[T,T,[F,F,T]]] --> [T,F,[T,T,F]] -> [T,F,T] --> T


JavaScript, 228 bytes

etInterval=stInterval=seInterval=setnterval=setIterval=setInerval=setIntrval=setInteval=setInteral=setIntervl=setInterva=top=>4

setInterval
`405>(i=this.i?i:1)?alert(i++):0`///`
setInterval
`405>(i=this.i?i:1)?alert(i++):0`///`

Explanation

Evaluating code in a setInterval allows the program to continue even if there is an error. We make sure that the code passed will error out if any single character is removed. Template string syntax can be abused to call setInterval with a constant string without parentheses. Luckily, even if the template string is on the next line it still parses as a function call with such syntax.

The first issue we run into is that setInterval is a function, and thus if a character is removed and the program tries to call setInteval instead, it errors out. Of course, since there are two indentical invocations of the setInterval, we don't have to worry about it actually functioning correctly as long as we avoid the error. So, the first line defines every possible "misspelling" of setTimeout to a valid function.

The first line works by assigning all of these "misspellings" to the function top=>4. Note the ES6 syntax, this simply takes a paramater named "top" and returns 4. Why "top"? Well, the first line must never throw an error even if a character is removed. If an = is removed to make top>4, this boolean expression will be valid since top is predefined in browsers, simply yielding false. If the 4 is removed, the function body simply becomes the first setInterval segment, and the second runs unharmed.

Now, all that is left to worry about is if a ` is removed.

If removed from the beginning, setInterval simply does nothing, evaluating to itself as its own expression. Then, the rest of the second line simply runs a single iteration of the loop, letting the other setInterval fragment finish the job. If removed from the end, the remaining backtick is picked up from the end of the comment.

The newlines are placed so that removal one will not affect program behavior, but they prevent errors in the case of some character removals such as the leading backtick.


Retina, 74 67 63 bytes

Byte count assumes ISO 8859-1 encoding.

.
 |
^
$.'$*----¶
\z
¶$` |
+`(.+\|) .+$
$&¶$1----
$
¶ |
  ¶
¶

Input is in unary, using any character except linefeeds as the digit.

Try it online!

Explanation

.
 |

We start by turning each unary digit into  |   (note the trailing spaces). This gives us the second line of the output (plus two trailing spaces if the input is at least 1).

^
$.'$*----¶

We match the beginning of the string in order to prepend the first line. This is done using some Retina-specific substitution features. $* repeats the character on the right as many times as its left arugment. $.' evaluates the number of characters to the right of the match. Since the match is only the beginning of the string this gives as many - as there are characters in the string and --- appends three more. The ¶ is an alias for a linefeed. So now we've got the first two lines.

\z
¶$` |

Now we append the next two lines. We do this by matching the end of the string and appending a linefeed, the entire string again and then  | to get the fourth line right.

+`(.+\|) .+$
$&¶$1----

Time for the applications. The leading + makes Retina repeat this stage until the output stops changing (in this case because the regex no long matches). The regex matches the entire last line, provided it contains a | follows by a space. We capture everything up to the | (which will be the second to last) in group 1. We write the line back with $&, a linefeed, then group 1 (thereby dropping the last |) and then ----.

$
¶ |

This just adds the final line containing only a single |.

  ¶
¶

Finally we need to get rid of the trailing spaces on the second line.


Python, 161 138 bytes

Credits for factorial.

g=lambda x:0**x or x*g(x-1)
f=lambda a,i,n=0,l=[]:(i<0)+(i>=len(a))and n or(0 if i in l else f(a,[a[i],i-a[i]][i and-g(i-1)%i],n+1,l+[i]))

Ideone it!

How it works

Wilson's theorem is used for prime checking.

Loop detection by storing seen indices to an array (l) and checking whether current index is in l.


Ostrich 0.7.0, 18 23 chars

Two solutions, identical in length:

:x;.,{;xR*C}%_+*\/o2/+F
\:x{.R*C\}*;]_+*x/o2/+F

Edit: +5 characters to each because I forgot to round to the nearest integer.

They both actually simulate rolling the dice (and thus have non-constant output), which seems to be the intent of the challenge.

Explanation of #1:

:x;     store the number of faces in x, pop from stack
.,      create range from 0 to [number of rolls] (while keeping #rolls on stack)
{...}%  map over that range...
  ;       discard the number
  xR*     generate a float between 0 and [number of faces]
  C       take ceil, which will make this an int between 1 and [#faces]
_+*     reduce by {+} (_ is the syntax for a single-instruction block) a.k.a. sum
\/      swap top two stack elements (bringing the number of rolls to the top),
          then divide, resulting in the average

Explanation of #2:

\       bring the number of rolls to the top
:x      store number of rolls in x, but don't pop from the stack
{...}*  that many times...
  .       duplicate the number of faces
  R*C     get the random number as described in #1
  \       stick that under the number of faces again, so [#faces] is still on top
;       discard the extra [#faces]
]_+*    wrap stack in an array, sum
x/      divide by [#rolls]


Python 3, 131
Now we're golfing with snakes!
Saved 18 bytes thanks to shebang.
Saved 4 more bytes thanks to DSM.
Saved a lot of bytes thanks to tzaman.
Many thanks to tzaman for his brilliant trick of abusing .find() returning -1 if it doesn't find a value.
Currently this assumes this drink format is exactly the way it's stated in the challenge, eg, only 1 digit worth of each drink.
w=input()
print(sum([6,50,4,100,.4]['BCGKS'.find(b)]*int(a)*int('1267730'['bhrtvw'.find(v)])for a,b,_,v in input().split())>int(w))


Python 2, Sampler

This entry is based on the same code for Keep your distance, Sampler entry. I hope it will do better here where the 1 and 999 advantages do not exist.

Out of a list of places, choose the one that is farthest away from recently used
numbers, ignoring the previous turn (because other entries may predict based on just the previous turn).

def choose(turn, players, history):
    sample = map(int, (' '.join( history[-5:-1] )).split())
    def distance(x):
        return sum(min(1000-abs(x-y), abs(x-y))**0.5 for y in sample)
    score, place = max((distance(x), x) for x in range(1000))
    return place


Python 2: 201 188 chars

def f(Q):c=lambda m:'rps'.index(m);l=len(Q);r=[0]*l;i=0;exec'p,q=i/l,i%l;m,n=c(Q[p][0]),c(Q[q][0]);exec"r[p]+=(p!=q)*(m+1-n)%3;m,n=c(Q[p][m*3+n+1]),c(Q[q][n*3+m+1]);"*7;i+=1;'*l*l;return r

The logic of the program: I convert the letters to number (r=0,p=1,s=2). m is the number of the first, n the number of the second person. Because the game is cyclic, (m-n)%3 already determines the result. And of course, I can shift the result by one f=(m+1-n)%3. Now f=0 means, second player q wins, f=1 means a tie, and f=2, first player p wins. It also is already the score for player 1. Therefore I only need to add all values (p!=q)*(m+1-n)%3 for each player.

Test it with print f(['rrpsrpsrps', 'rpppsprrpr', 'ssssssssss'])


Distinct Reversible Primitive Binary Necklaces

Python 2, 178 171 139 137 bytes

lambda n:sum(1-any(i>int(b[j::-1]+b[:j:-1],2)or j*(i>=int(b[j:]+b[:j],2))for j in range(n))for i in range(2**n)for b in[bin(i+2**n)[3:]])

Try it online! Edit: Saved 7 21 bytes thanks to @HalvardHummel.


Raku, 14 12 11 bytes

0+|*/.98334

Try it online!
Since we know the bounds of the input, we can substitute a constant operation and a floor on the input in base 60.  That number by the way is around 1358/1381, which is the maximum the input differs from the output in base 60. There may be a smaller constant, or at least a smaller way to represent it. For reference, the shortest constant you can multiply by, rather than divide, is 1.01694.


BQN, 1 byte
Anonymous tacit infix function. Order of arguments doesn't matter.
+

Try BQN!


Python, 112 bytes

d=lambda x,l,h:0if h<l else d(x,l+1,h-1)if x[l]==x[h]else-~min(d(x,l+1,h),d(x,l,h-1));e=lambda x:d(x,0,len(x)-1)

Very inefficient.

Try it online! You have to wait a minute for the last case to finish.

Call with e(<string>, 0, <length of string - 1>), like e("fishes", 0, 5)`.

Ungolfed (sort of) with explanation:

def minInsert(x, l, h):                # Declare func, arugments for x, l, h       # d=lambda x,l,h:
  if l >= h:                           # If l is the same or past h                #                 if h<l
    return 0                           #     then return 0                         #                0
  elif x[l] == x[h]:                   # If first and last character are the same  #                        else             if x[l]==x[h]
    return minInsert(x, l + 1, h - 1)  #     then return the min w/o first & last  #                             d(x,l+1,h-1)
  else:                                # If not, we shave off a character          #                                                      else
    a = minInsert(x, l, h - 1)         #     (last one)                            #                                                                d(x,l+1,h)
    b = minInsert(x, l + 1, h)         #     (first one)                           #                                                                           d(x,l,h-1)
    return min(a, b) + 1               #     and add one for the char we took off  #                                                          -~min(          ,          )


T-SQL - 291 277 267 217 199 191 166 158 153 145 142 128 117
After approaching this in a new way, I managed to get down to 145(142 after a couple minor tweaks), not too shabby. That means I might be able to compete for silver or bronze. ^^
DECLARE @ INT=100;WITH N AS(SELECT 1A UNION ALL SELECT A+1FROM N WHERE A<@)SELECT LEFT(A,LEN(A)-1+A%11)FROM N ORDER BY-A

This doesn't print a list, it selects the results. The question never gave specifics about output, so this should be fine. This still has the same limit of 100 on the input, partly because I'm abusing the fact that every 11th term under 100 loses a character and partly because of the default 100 recursion limit on common table expressions.
DECLARE @ INT=100;

WITH N AS
(
    SELECT 1A
    UNION ALL
    SELECT A+1
    FROM N
    WHERE A<@
)

SELECT LEFT(A,LEN(A)-1+A%11)
FROM N
ORDER BY-A


Java (JDK 10), 11 bytes

a->a.length

Try it online!