Total 36,757,269,913 cycles

830B assembled

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

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

main:
    call read
    call factor
    halt 0

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

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

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

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

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


write an "operating system" that dims Num Lock

I haven't tested this (VirtualBox doesn't pass through its virtual keyboard LEDs onto the physical keyboard, and I'm not on a PC I can reboot currently). But I think it should probably work and is probably quite minimal.

There may be some additional setup that needs to be done on the keyboard controller for these commands to work. If so it would be essentially trivial to add to the code below...

[bits 16]
[org 0x7c00]
mov al, 0xed
out 0x60, al
mov al, 0x07
out 0x60, al
mov al, 0xed
out 0x60, al
mov al, 0x00
out 0x60, al
jmp $$
times 510 - ($ - $$) db 0
dw 0xaa55

Compile with nasm -f bin -o floppy.img numlock.asm.

Will give this a real test and tweak accordingly later (if someone else wants to try and/or tweak it feel free).


APL, 32 bytes

{1=≡⍺:⎕←⍺,⍨⍵↑1↓⍵/'->'⋄⍺∇¨⍵+1}∘0

Test:

      r
┌────┬─────────────────────────────────────────────────────────────────────────────────────────┐
│Atom│┌──────┬──────────────────────────────┬───────┬────────────────────────────────┬────────┐│
│    ││Proton│┌────────┬────────┬──────────┐│Neutron│┌────────┬──────────┬──────────┐│Electron││
│    ││      ││Up Quark│Up Quark│Down Quark││       ││Up Quark│Down Quark│Down Quark││        ││
│    ││      │└────────┴────────┴──────────┘│       │└────────┴──────────┴──────────┘│        ││
│    │└──────┴──────────────────────────────┴───────┴────────────────────────────────┴────────┘│
└────┴─────────────────────────────────────────────────────────────────────────────────────────┘
      {1=≡⍺:⎕←⍺,⍨⍵↑1↓⍵/'->'⋄⍺∇¨⍵+1}∘0 ⊢ r
>Atom
->Proton
-->Up Quark
-->Up Quark
-->Down Quark
->Neutron
-->Up Quark
-->Down Quark
-->Down Quark
->Electron

Explanation:

{...}∘0: run the following function with 0 bound to ⍵:

1=≡⍺:: if the input has depth 1 (i.e. an array that does not contain other arrays):

⍵/'->': create a string containing ⍵ -s and ⍵ >s,
1↓: drop the first element,
⍵↑: and take the first ⍵ elements. This results in a string containing ⍵-1 dashes and one >.
⍺,⍨: append the input to it,
⎕←: and output that to the screen

⋄: otherwise,

⍺∇¨⍵+1: add 1 to ⍵ and apply the function to each nested array


JavaScript (ES6),  228 195 192  185 bytes
Expects a matrix of characters as input.
This can be quite slow on some inputs, such as the last test case.
m=>m.map((r,Y)=>r.map((_,X)=>n+=(g=(x,y,z,q=z&2,r=m[y],v=r&&r[x])=>v?(v|=64+(v>{})+!++v)^(r[x]|=v|4<<z)?g(x+--q*~z%2,y-q*z%2,z^2)&g(x,y,v&3?z^=v&2|1:z+1&3)|!(r[x]=v):1:0)(X,Y,0)),n=0)|n

Try it online!
How?
Grid encoding
We divide each cell into 4 areas as follows:

The current position is encoded as \$(x,y,z)\$, where \$(x,y)\$ is the position in the matrix and \$z\$ is the ID of the area.
The characters in the original matrix are converted on the fly to 7-bit integers as they are visited:
+---------> a marker to tell that this tile has been converted (always 1)
|      +--> 4 bits to tell whether a given area has been visited
|      |
|      |      +-----> set to 1 if the cell contains an anti-slash
|  ____|____  |  +--> set to 1 of the cell contains a slash
| /         \ |  |
1 z3 z2 z1 z0 AS S

The conversion is done with:
v |= 64 + (v > {}) + !++v

The expression (v > {}) is only true for '\' and !++v is true for either '/' or '\'. If v is already an integer, it is left unchanged.
Algorithm
Evaluating the area enclosed by slashes is equivalent to counting the number of cells from which we can't escape from the grid, starting from a given area ID. We arbitrary start from area #0, but that would work with any of them as long as it is consistent.
We iterate on all possible starting points and process some kind of flood-filling that takes the area IDs into account.
For each visited cell, we try to move to an adjacent cell (left figure) and  to another area within the same cell (right figure).

The recursion stops either when we escape the grid or when we get trapped.


Perform basic operations on complex numbers in a language without native support for complex numbers

APL (33 + 16 + 1 + 1 + 14 + 17 = 82)

APL does have support for complex numbers if you use it (of the format 5J6, like Python's 5+6j), but it is of course not used.

I represent complex numbers as a 2-tuple of regular numbers, (A B) where A is the real part and B is the imaginary part. This means I can use APL's + and - operators directly, as they can be used on multidimensional types. (i.e. 1+2 3 4 gives 3 4 5 and 1 2+20 10 gives 21 12).

An APL function is represented as {body}. Functions are first-class objects. I have counted the function body without the braces, except for + and - which I've counted as 1 each.

read  ← {⎕ML←3⋄(1,1-2×'-'∊⍵)×⍎¨⍵⊂⍨⍵∊'.',⎕D} ⍝ 33 chars
print ← {⍕(⊃⍵)'+'(⊃⌽⍵)'i'}                   ⍝ 16 chars
add   ← +                                      ⍝ 1 char
sub   ← -                                      ⍝ 1 char
mul   ← {(-/⍺×⍵),+/⍺×⌽⍵}                      ⍝ 14 chars
div   ← {⍺mul 1 ¯1×⍵÷+/⍵*2}                   ⍝ 17 chars

Usage:
(clarification: APL is evaluated right-to-left so this is actually calculating 8+9i ÷ 5+6i.)

      print (read⍞) div (read⍞)
5 + 6i
8 + 9i
1.540983607 + ¯0.04918032787 i


JavaScript ES6, 210 208 202 bytes

s=>` 0
8(213)9
4(6)5
 (7)`.replace(/\d/g,p=>`_===_1 ___
 .....1  _
  /_\\1 ___
 (_*_)1,1.1_11.1o101-1.1o101-1<11/11>11\\11 : 1] [1> <1   1 : 1" "1___1   11\\11 11/11 `.split(1)[s[p>7?p-4:p]-1+p*4]||' ')

This is an anonymous function; you use it by executing ([function code])('42232124'). The most aggravating part of this was the arms, which take up 2 lines, so I had to include code for both top and bottom.

The Stack Snippet below has ungolfed, un-ES6-ified, commented code. And you can use it to easily test the code and try out different combinations. Edit: I'm having way too much fun with this. I've added several new features, including a way to generate a random snowman.

Thanks to Yair Rand for saving six bytes.

var f=function(s){
  return' 0\n8(213)9\n4(6)5\n (7)' // Start with a placeholder string with all the static components
    .replace(/\d/g,function(p){ // Go through each placeholder number to replace it with its value
    // The massive string below holds all the possible body parts, separated by 1 for easy splitting.
    // The two at the end are for the top of the arms
    return'_===_1 ___\n .....1  _\n  /_\\1 ___\n (_*_)1,1.1_11.1o101-1.1o101\
-1<11/11>11\\11 : 1] [1> <1   1 : 1" "1___1   11\\11 11/11 '.split(1)
    [s[p>7?p-4:p]-1 // Get the value from the input string. If the current body part
                    // is the top of the two-line arms (8 or 9), drop it down to 4 or 5
                    // Subtract 1 to account for the 0-indexed array.
     +p*4] // multiply by 4 to skip to the relevant code
     ||' ' // To save bytes in the above string, spaces are empty strings, so replace them here
  })
}

// Code for the interactive version follows
// http://codepen.io/hsl/pen/bdEgej
function updateRadios(){$('input[type="radio"]').each(function(){if($(this).is(":checked")){var t=$(this).data("p"),i=$(this).data("v");input[t]=i}}),inputS=input.join(""),update()}var input=[],inputS=$("#code").val(),update=function(){$("#p").text(f(inputS)),$("#code").val(inputS)};$('input[type="radio"]').change(updateRadios),$("#code").keyup(function(){inputS=$(this).val(),update()}),updateRadios(),$("#random").click(function(){for(var t=0;8>t;t++)$("div:eq("+t+") input:eq("+Math.floor(4*Math.random())+")").prop("checked",!0);updateRadios()});
body{font-family:sans-serif}h2{font-size:18px;font-weight:400}label{display:block}div{display:inline-block;margin:0 10px}#code{width:70px}

Hat
<input type="radio" name="p1" data-p="1" data-v="1"> Straw hat<input type="radio" name="p1" data-p="1" data-v="2"> Mexican hat<input type="radio" name="p1" data-p="1" data-v="3"> Fez<input type="radio" name="p1" data-p="1" data-v="4" checked> Russian hat

Nose/mouth
<input type="radio" name="p2" data-p="2" data-v="1"> Normal<input type="radio" name="p2" data-p="2" data-v="2" checked> Dot<input type="radio" name="p2" data-p="2" data-v="3"> Line<input type="radio" name="p2" data-p="2" data-v="4"> None

Left eye
<input type="radio" name="p3" data-p="3" data-v="1"> Dot<input type="radio" name="p3" data-p="3" data-v="2" checked> Bigger dot<input type="radio" name="p3" data-p="3" data-v="3"> Biggest dot<input type="radio" name="p3" data-p="3" data-v="4"> Closed

Right eye
<input type="radio" name="p4" data-p="4" data-v="1"> Dot<input type="radio" name="p4" data-p="4" data-v="2"> Bigger dot<input type="radio" name="p4" data-p="4" data-v="3" checked> Biggest dot<input type="radio" name="p4" data-p="4" data-v="4"> Closed

Left arm
<input type="radio" name="p5" data-p="5" data-v="1"> Normal<input type="radio" name="p5" data-p="5" data-v="2" checked> Upwards<input type="radio" name="p5" data-p="5" data-v="3"> Downwards<input type="radio" name="p5" data-p="5" data-v="4"> None

Right arm
<input type="radio" name="p6" data-p="6" data-v="1" checked> Normal<input type="radio" name="p6" data-p="6" data-v="2"> Upwards<input type="radio" name="p6" data-p="6" data-v="3"> Downwards<input type="radio" name="p6" data-p="6" data-v="4"> None

Torso
<input type="radio" name="p7" data-p="7" data-v="1"> Buttons<input type="radio" name="p7" data-p="7" data-v="2" checked> Vest<input type="radio" name="p7" data-p="7" data-v="3"> Inward arms<input type="radio" name="p7" data-p="7" data-v="4"> None

Base
<input type="radio" name="p8" data-p="8" data-v="1"> Buttons<input type="radio" name="p8" data-p="8" data-v="2"> Feet<input type="radio" name="p8" data-p="8" data-v="3"> Flat<input type="radio" name="p8" data-p="8" data-v="4" checked> None

<button id="random">Randomize</button>

<input type="text" id="code">


Stuck, 4 Bytes

I'm amazed Stuck finally is winning something! The inclusive range function checks to see if the top of the stack is a list of length 2, and uses it for the parameters of the range function if so.

t]R+

Input is | separated, as t takes a bunch of inputs separated by |s and places them on the stack. ] just wraps the elements in a list, and lets the range function do it's job.

If that still falls in the penalty, then this works (5 Bytes): ii]R+


Write a program with infinite expected output

R, 9 bytes

rf(1,1,1)

Try it online!
Outputs a realization of the \$F(1,1)\$ distribution. The \$F(d_1,d_2)\$-distribution has infinite mean for \$d_2 \leq 2\$.
One way of defining the \$F(1,1)\$ distribution is as follows: let \$X_1,X_2\$ be independent \$\mathcal N(0,1)\$ random variables. Then \$\frac{X_1^2}{X_2^2}\sim F(1,1)\$.
Using the \$F\$ distribution comes out 1 byte shorter than the 2 more obvious solutions 1/runif(1) and rcauchy(1).
The plot below shows the evolution of the sample mean, for sample size ranging from 1 to 1e6; you can see that it diverges.

Alternate solution for the same byte count:
rt(1,1)^2

which outputs the square of a realization of Student's distribution \$t(1)\$. It has infinite expected value, since the \$t(1)\$ distribution has infinite variance. The square is needed to guarantee that the output is positive; without it, the expected value is undefined, since the realizations are often enough arbitrarily large positive or negative numbers.


Print a specific value in the infinite Walsh matrix

GolfScript (18 15 14 bytes)

~&2base-1\0-,?

Takes input space-separated; outputs to stdout. Thanks to Howard for pointing out that the space in the 15-char solution was removable.

The way I reasoned to this solution is quite simple. Take the highest set bit of x|y: this tells you the size of the smallest Walsh matrix which contains the relevant index. Then clearing that bit in both x and y drops us down to the top-left quadrant, and we need to multiply by -1 if we were previously in the bottom-right quadrant: i.e. if the bit was set in both x and y. By induction down the bit sequence, we just need to count the number of bits set in x&y.


XOISC

This OISC is based on Fokker's X-combinator which is defined as follows:

$$ X = \lambda f\ . f\ (\lambda g\ h\ x\ . g\ x\ (h\ x))\ (\lambda a\ b\ c\ . a) $$

If we acknowledge the fact that the SKI-calculus is Turing complete the above \$X\$-combinator is Turing complete as well. This is because \$S\$, \$K\$ and \$I\$ can be written in terms of \$X\$, like this:

$$
  \begin{align}
      S &= X\ (X\ X) \\
      K &= X\ X \\
      I = S\ K\ K &= X\ (X\ X)\ (X\ X)\ (X\ X)
  \end{align}
$$

How XOISC works

Internally XOISC has an (initially empty) stack, from there the instruction taking \$n\$ as an argument does the following:

Pop \$n\$ elements (functions \$ f_1 \dots f_N\$) from the stack, push \$f_1\ (f_2\ (\dots (f_N\ X) \dots ))\$

Once there are no more instructions left XOISC will push all command-line arguments (if any) to the stack, for example:

$$
  [ \underbrace{s_1, \dots,\ s_M}_{\text{stack before}}
  ,\ \underbrace{a_1, \dots,\ a_N}_{\text{arguments}}
  ]
$$

The final computation will be \$(\dots ((\dots (s_1\ s_2) \dots)\ s_M)\ a_1) \dots) a_N \$.

Since the one instruction in XOISC takes only one argument (memory offset) there is no reason to even use a name for that instruction. So a valid source file will constitute solely of integers separated by newlines or whitespaces, like for example:

0 0 2 0 1 0 1

Try it online!

Example

Let's take the above example (stack growing to the right):

$$
  \begin{align}
& \texttt{0} & \text{pop 0 and apply (ie. push single } X \text{)}:
  & \quad [X] \\
& \texttt{0} & \text{again simply push } X:
  & \quad [X,\ X] \\
& \texttt{2} & \text{pop 2 (} a,b \text{) and push } a\ (b\ X):
  & \quad [X\ (X\ X)] \\
& \texttt{0} & \text{simply push } X:
  & \quad [X\ (X\ X),\ X] \\
& \texttt{1} & \text{pop 1 (} a \text{) and push } a\ X:
  & \quad [X\ (X\ X),\ X\ X] \\
& \texttt{0} & \text{simply push } X:
  & \quad [X\ (X\ X),\ X\ X,\ X] \\
& \texttt{1} & \text{pop 1 (} a \text{) and push } a\ X:
  & \quad [X\ (X\ X),\ X\ X,\ X\ X]
  \end{align}
$$

Finally evaluate the stack: \$((X\ (X\ X))\ (X\ X))\ (X\ X)\$ or with less parentheses \$X\ (X\ X)\ (X\ X)\ (X\ X)\$ which we recognize as the good old \$S\ K\ K\$ identity function.

Turing completeness

Proof idea

For XOISC to be Turing complete we need to be able to translate any (valid) interleaving of parentheses and \$X\$ combinators. This is possible because when popping, applying and pushing it does so in a right-associative manner (function application is left-associative).

To translate any such \$X\$ expression there is an easy way to do so: Always pop as many elements such that from the beginning of the current level of parentheses there will only be one element left.

As an example, the previously used expression: \$((X\ (X\ X))\ (X\ X))\ (X\ X)\$

to get \$X\$, we simply need a 0
next we're in a new level of parentheses, so we again only need a 0
now two parentheses close, so we need to pop 2 elements: 2
again we're in a new level of parentheses, so we need a 0
two parentheses, close so again a 2
and the same again

So we end up with a different (yet semantically equivalent) XOISC-program:

0 0 2 0 2 0 2  Try it online!

If we stay with this strategy we can easily transform any expression consisting of \$X\$ combinators to an XOISC program which only leaves a single function on the stack.

Formal proof

Given that the SKI-calculus is Turing complete, we need to show two things:

the \$X\$-combinator is a basis for the SKI-calculus
XOISC is able to represent any expression formed with the \$X\$ combinator

The first part - proving the three equalities in the introduction - is very tedious and space consuming, it's also not very interesting. So instead of putting it in this post, you can find here*.

The second part can be proven by structural induction, though it's easier to prove a slightly stronger statement: Namely, for any expression formed by \$X\$-combinators there is a program that will leave that expression as a single expression on the stack:

There are two ways of constructing such an \$X\$ expression, either it's \$X\$ itself or it's \$f\ g\$ for some expressions \$f\$ and \$g\$:

The former one is trivial as 0 will leave \$X\$ on the stack as a single expression. Now we suppose that there are two programs (\$\texttt{F}_1 \dots \texttt{F}_N\$ and \$\texttt{G}_1 … \texttt{G}_K\$) that will leave \$f\$ and \$g\$ as a single expression on the stack and prove that the statement holds for \$f\ g\$ as well:

The program \$\texttt{F}_1 \dots \texttt{F}_N\ \texttt{G}_1 \dots \texttt{G}_{K-1}\ (\texttt{G}_K + 1)\$ will first generate \$f\$ on the stack and then it will generate \$g\$ but instead of only popping parts of \$g\$ it will also pop \$f\$ and apply it, such that it leaves the single expression \$f\ g\$ on the stack. ∎

Interpreter

Inputs

Since the untyped lambda calculus requires us to define our own data types for everything we want and this is cumbersome the interpreter is aware of Church numerals - this means when you supply inputs it will automatically transform numbers to their corresponding Church numeral.

As an example here's a program that multiplies two numbers: Try it online!

You can also supply functions as arguments by using De Bruijn indices, for example the S combinator \\\(3 1 (2 1)) (or λλλ(3 1 (2 1))). However it also recognizes the S, K, I and of course X combinator.

Output

By default the interpreter checks if the output encodes an integer, if it does it will output the corresponding number (in addition to the result). For convenience there's the -b flag which tells the interpreter to try matching a boolean instead (see the last example).

Assembler

Of course any low-level language needs an assembler that converts a high-level language to it, you can simply use any input (see above) and translate it to a XOISC-program by using the -a flag, try it online!**

* In case the link is down, there's a copy as HTML comment in this post.

** This results in a program that tests for primality, try it online!


Java 8, 68 57 53 52 bytes

n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}

-5 bytes thanks to @OlivierGrégoire.
Try it online.
Explanation:
n->{                 // Method with integer as both parameter and return-type
  for(int i=0;i<n;)  //  Loop `i` in the range (1,n)
    i-=(i*2^i)==n?   //   If `i*2` XOR-ed with `i` equals `n`
        n=i          //    Set `n` to `i`, and set `i` to 0 to reset the loop
       :             //   Else:
        -1;          //    Increase `i` by 1 to go to the next iteration
  return n;}         //  Return `n` after the entire loop


Martin vs Dennis - Round 1: Who has more rep?

05AB1E, 65 64 bytes
Code:
•в=6{•5ôvy’ƒËŠˆ.Â‚‹º.ŒŒ/†š/ÿ’.w’„Ö="Âˆ"’¡1èт£þ}})ZQā*O<“D M·‡“#è

Uses the 05AB1E encoding.

Explanation:
•в=6{• converts the number в=6{ from base 255 to base 10, resulting in 1201208478. The first half being the ID of Dennis (12012) and the second half being the ID of Martin (8478). Split into pieces of 5 using 5ô to get the following array:
['12012', '08478']

Luckily, we can leave the leading zero from Martin's ID, since this will still work (check the link before clicking to see the leading zero).
We now loop through this array using vy and construct the following string from this 05AB1E code:
’ƒËŠˆ.Â‚‹º.ŒŒ/†š/ÿ’  -->  codegolf.stackexchange.com/users/ÿ

Whereas ÿ is the current element of the iterator (using string interpolation) Try it online!
After constructing the link, .w reads all data from the link, resulting into a huge amount of text. To scrape the reputation from this, we need to split on the string title="reputation". Or in a more compressed version: ’„Ö="Âˆ"’. Split on this piece of string (with ¡) and get the second element (with 1è) and keep the first 100 characters (with т£).
Now, our scraped text looks a bit like this:
>
        139,883 reputation

<div class="ba

This part is easy, we just remove anything but digits to remain the reputation number, for which we have a builtin (þ). We end the loop and wrap everything into an array }}).
Finally, we can go on to processing the reputation numbers:
ZQā*O<“D M·‡“#è   -   On stack: an array in the format [Dennis rep, Martin rep]

Z                 # Get the maximum of the array
 Q                # Check for equality with the array
  ā*              # Multiply by it's index (1-indexed)
    O<            # Sum and decrement by 1
      “D M·‡“#    # Push the array ['D', 'M', 'tie']
              è   # Get the element on the index of the sum

Which results in either D, M or tie.


CJam, 52 bytes

F,ri*"s@;b6(MBZF,fu"128b6b"_
|-—"f=N/ff=zN*

Includes a bunch of unprintable ASCII characters. The hexdump of the first string literal pushed is:

01 73 06 40 3B 62 36 28 1E 4D 07 42 5A 14 1B 46 2C 66 75

Try it here!

Explanation

The above hexdump is interpreted as a base-128 number, then converted to base 6, to get this list:

[1 1 1 1 0 0 1 1 1 0 0 2
 1 1 1 3 1 1 3 0 3 1 1 3 2
 0 0 0 3 1 1 1 1 1 1 1 3 2
 4 1 1 1 2
 1 4 2
 4 1 2
 5]

To this, we apply the mapping 0 → _, 1 → space, 2 → \n, 3 → |, 4 → -, 5 → —. This gets us the string:

    __   __
   |  |_|  |
___|       |
-
 -
-
—

It consists of the "period" of each line; i.e. we can cycle the fifth line " -" to get " - - - - - - - ".

Then, we execute this subprogram:

N/               Split into lines.
  Ff*            Repeat each line 15 times (to cycle it).
     Ff<         Take the first 15 chars of each line.
        rif*     Repeat these chars input() times.
            N*   Join lines.

(The new version does this in a slightly different way that I actually can't wrap my head around myself very well, because it uses ff=.)


Python 2, 53 bytes
f=lambda l,c=1:c*l if l<[]else-min(f(x,-c)for x in l)

The main question is how to alternate between max and min each layer. Using the fact that max(l) == -min([-x for x in l]), we instead negate every second layer and recurse with -min. To negate every second layer, we pass down a multiplier c that alternates +1 and -1, and when we reach a leaf, we adjust its value by the multiplier. We recognize being at a leaf via the condition l<[], since Python 2 treats numbers as less than lists.
It's hard to shorten the else/if ternary because either branch could give a Truthy (nonzero) or Falsey (zero) value.


MATL, 29 bytes
ljU"1@_hX+]tn:Pqv'+%gx^%g'wYD

Input is an array with the roots.
EDITS:

(May 20, 2016): the X+ function has been removed, as Y+ includes its functionality. So in the above code replace X+ by Y+.
(September 29, 2017): due to changes in the YD function, w in the above code should be removed.

The following link includes those changes.
Try it online!
Explanation
This applies repeated convolution with terms of the form [1, -r] where r is a root.
l          % push number 1
jU         % take input string. Convert to number array
"          % for each root r
  1        %   push number 1
  @_       %   push -r
  h        %   concatenate horizontally
  X+       %   convolve. This gradually builds array of coefficients
]          % end for each
tn:Pq      % produce array [n-1,n-2,...,0], where n is the number of roots
v          % concatenate vertically with array of coefficients
'+%gx^%g'  % format string, sprintf-style
w          % swap
YD         % sprintf. Implicitly display


APL (Dyalog Unicode), 57 bytes

¯1~⍨,1↓∘⍉∘⌽⍣4⊢{2 2⌷⍵:2⊥(~¯9↑5↑1)/,⍵⋄¯1}⌺3 3⊢⍉∘(¯1∘↑⍪⊢⍪1∘↑)⍣2⊢'X'=⎕

Try it online!
A full program which takes a binary matrix through STDIN, returns an array of codepoints.
Explanation
x¯1~⍨,1↓∘⍉∘⌽⍣4⊢{2 2⌷⍵:2⊥(~¯9↑5↑1)/,⍵⋄¯1}⌺3 3⊢⍉∘(¯1∘↑⍪⊢⍪1∘↑)⍣2⊢'X'=⎕
⎕ take input
'X'=  boolean matrix where 'X's are 1s
⍉∘(...)⍣2⊢ do the following twice:
¯1∘↑⍪⊢⍪1∘↑ pad each row with its wraparound on both sides
⍉∘ and transpose
{...}⌺3 3⊢ then, do the following for each 3x3 window:
2 2⌷⍵: if the middle element is 1:
2⊥(~¯9↑5↑1)/,⍵ decode the rest of the window as binary
⋄¯1 Otherwise, return ¯1.
⍣4⊢ Do the following 4 times:
1↓∘⍉∘⌽ rotate 90°, drop first row (remove the border cells)
, flatten into a simple array
¯1~⍨ remove all ¯1s


ArnoldC, 308 298 bytes

IT'S SHOWTIME
HEY CHRISTMAS TREE x
YOU SET US UP 0
GET YOUR ASS TO MARS x
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY
GET TO THE CHOPPER x
HERE IS MY INVITATION x
GET UP 99
HE HAD TO SPLIT 100
ENOUGH TALK
TALK TO THE HAND x
YOU HAVE BEEN TERMINATED

Try it online!

This seemed a challenge easy enough to try to write my first answer in ArnoldC...


Display number of occurrences for every character in an input string

PHP - 68 (or 39) bytes

<?foreach(count_chars(fgets(STDIN),1)as$k=>$v)echo chr($k)." : $v
";

Output for the example text:

  : 15
. : 1
T : 1
a : 10
c : 1
d : 4
e : 8
f : 2
g : 3
h : 3
i : 10
m : 1
n : 10
o : 4
p : 3
q : 1
r : 2
s : 5
t : 6
u : 1
x : 1
y : 1

If the exact output is not required, this would work for 39 bytes:

<?print_r(count_chars(fgets(STDIN),1));

Sample output:

Array
(
    [32] => 15
    [46] => 1
    [84] => 1
    [97] => 10
    [99] => 1
    [100] => 4
    [101] => 8
    [102] => 2
    [103] => 3
    [104] => 3
    [105] => 10
    [109] => 1
    [110] => 10
    [111] => 4
    [112] => 3
    [113] => 1
    [114] => 2
    [115] => 5
    [116] => 6
    [117] => 1
    [120] => 1
    [121] => 1
)

where each numerical index refers the ordinal value of the character it represents.

I suspect very strongly that using an in-built function that does exactly what the problem states will soon be disallowed.


Insert parens into a free-form SKI calculus expression


Perl/Bash 54 40+1 = 41 bytes

perl -pe's:(\D*\d*)(\d):"\$1=~s/./\$&x$2/egr":ege'

It's basically a regex within a regex. And a bit of magic.

Explanation

The outer regex /(\D*\d*)(\d)/g extracts each run-length encoded group. We capture the stuff to repeat in $1 and the number of repetitions in $2. Now we substitute each such group with the expansion of that group. For that, we evaluate the code "\$1=~s/./\$&x$2/egr" two times (as by the /ee flag on the outer substitution).

The first evaluation will only interpolate the number of repetitions into the string – the other variables are protected by a backslash. So assuming the input a14, we would now have the code $1=~s/./$&x4/egr, which will be evaluated again.

This will apply the substitution to the contents of $1 (the stuff to repeat a1). The substitution matches each character .. The $& variable holds the whole match, which we repeat x4 times. We do this /globally for each match and /return the substituted string rather than modifying the $1 variable (which is read-only). So the result of the inner substitution is aaaa1111.

The -p flag applies the substitution to each input line and prints out the result.


C++
Comments indicate how code works.
#include<iostream>
#include<vector>
using namespace std;

int main(){
    // input stores input, sum_values stores the sum of values in the valid range after multiplying
    vector<double>input;
    vector<double>sum_values;

    // stores input, and ends of range
    double num, lower, higher;

    cout<<"Enter the array of values, use 0 to exit: ";

    // input
    while(1){
        cin>>num;
        if(num==0)break;
        input.push_back(num);
    }

    cout<<"Enter the mimimum and maximum values: ";

    cin>>lower>>higher;

    // if array is empty or lower is greater than higher, print 1 and exit
    if(lower>higher||input.size()==0){cout<<"1";return 0;}

    // iterate through all values between .0001 and .9999
    for(double d=.0001;d<1;d+=.0001){

        // check each d for valid ranges
        for(int i=0,valid=0;i<input.size();i++){

            // check if input * d is in valid range
            if(d*input[i]>=lower&&d*input[i]<=higher)valid++;

            // store final number
            if(i==input.size()-1)sum_values.push_back(valid);
        }
    }

    // iterate through compiled sum of ranges and find highest
    int position=0, biggest=-.1;
    for(int i=0;i<sum_values.size();i++){

        // return value closest to 1 for equal values
        if(sum_values[i]>=biggest){
            biggest=sum_values[i];
            position=i;
        }
    }

    // print value
    cout<<(double)position*.0001;

    return 0;
}


Haskell, 39 bytes
until(((==).head>>=all).show)(+1)>>=(-)

Try it online


print "Hello, world!" without using literals


C

cat >a.c <<.
#define _(a...) {return({a;});}
#define F(i,x,n,a...) for(I i=(x),n_=(n);i<n_;i++){a;}
#define i(a...) F(i,0,a)
#define j(a...) F(j,0,a)
#define k(a...) F(k,0,a)
#define I(a...) F(i,a)
#define S static
#define O const
#define mc __builtin_memcpy
#define sl __builtin_strlen
typedef void V;typedef char C;typedef int I;

#include<sys/syscall.h>
#define M1(x) #x
#define M2(x) M1(x)
#define h(x,a...) ".globl "#x";"#x":"a"mov $"M2(SYS_##x)",%rax;syscall;ret;"
asm(".globl _start;_start:pop %rdi;mov %rsp,%rsi;call main;"h(write)h(exit));I write(I,C*,I);V exit(I);
V*memcpy(V*x,O V*y,I n)_(C*a=x;O C*b=y;i(n,a[i]=b[i])a)I strlen(O C*s)_(I r=0;while(*s++)r++;r)

S O C A0=32,A1=126+1,AN=A1-A0;S C o0[1<<20],*o=o0;
S V rpt(C*a,I n,I m){m*=n;while(2*n<m){mc(a+n,a,n);n+=n;}mc(a+n,a,m-n);}
S I fd(C*s,I n,I p)_(i(p,j(n,*o++=s[j+(i<=j)]))p)
S I fc(C*s,I n,I p)_(mc(o,s,n+1);rpt(o,n+1,p*AN);I(A0,A1,j(p,o[j]=i;o+=n+1))p)
S I fi(C*s,I n,I p)_(p++;i(p,j(n+2,o[i*(n+2)+j]=s[j-(i<j)]))rpt(o,p*(n+2),AN);I(A0,A1,j(p,o[j]=i;o+=n+2))p)
I main(I c,C**v)_(S C s[32];I n=sl(v[1]);mc(s,v[1],n);s[n]=10;S typeof(fd)*f[]={fd,fc,fi};
 i(3,o=o0;I g=f[i](s,n,n);j(g*(i?AN:1),C*b=o;k(3,f[k](o0+(n+i)*j,n+i-1,j%g))write(1,b,o-b);o=b))
 exit(0);0)
.
clang -O3 -march=native -nostdlib -ffreestanding a.c && strip a.out -R .comment
time ./a.out abcdefghijklmnop >/dev/null

Try it online!
for the record, here's why this answer didn't win the bounty: https://chat.stackexchange.com/transcript/message/56646474#56646474


Find all unambiguous prefixes of a set of strings

Python 2.7 - 146 141 bytes

l=raw_input().split(',')
for w in l:
 for a in range(len(w)):
    e=w[:a+1]
    if e==w or len(filter(lambda b:b.startswith(e),l))==1:print e+':'+w

Note that the indentation on lines 4 and 5 is not 4 spaces, that's a side effect of SE's markdown interpreter. That's a literal tab character, so only one byte.

This is not technically up to spec, but I'll change it if Doorknob clarifies. It uses newlines instead of commas to separate the output. For example:

$ python2 abbreviations.py <<< code,golf,golfing
c:code
co:code
cod:code
code:code
golf:golf
golfi:golfing
golfin:golfing
golfing:golfing

New: I was able to get rid of 5 characters by assigning the string that I'm checking to a variable e. This means that I only have to type e instead of w[:a] three times. It also means I save characters by doing e=w[:a+1] and changing ...range(1,len(w)+1) to range(len(w)).

Explanation:

l=raw_input().split(',') # Gets a line of input from stdin and splits it at every ',' to make a list
for w in l: # For each word in that list...

 for a in range(1,len(w)+1): # For each number a from 1 to the length of that word...

    if (w[:a]==w # w[:a] gets the string w up to the ath index. For example, 'aeiou'[:3] == 'aei'.
                 # We're testing every possible w[:a] to see if it's a unique abbreviation.
                 # However, a word is always its own abbreviation, so we hardcode that in by testing
                 # if w[:a] is the same as w.

or len(filter( # filter takes a function and an iterable as an argument, and returns a list of every
               # element of that iterable where that_function(that_element) returns a True-y value

lambda b:b.startswith(w[:a]),l) # We define an anonymous function that returns True for any string
                                # that begins with our current w[:a]. We filter for words that return
                                # True.

)==1): # If exactly one word returns True for this, it's a unique abbreviation!

     print w[:a]+':'+w # Print the abbreviation, a colon, and the full word.


MATLAB/Octave, 143 bytes

function [v,x,y]=d(x,y)R=S=zeros(max(y+3),max(x+3));i=sub2ind(size(S),y+2,x+2);S(i)=1;while nnz(S=imerode(S,strel('disk',1,0)))R+=S;end;v=R(i);

Ungolfed

function [v,x,y]=d(x,y)
  R=S=zeros(max(y+3),max(x+3));
  i=sub2ind(size(S),y+2,x+2);
  S(i)=1;
  while nnz(S=imerode(S,strel('disk',1,0)))
    R+=S;
  end;
  v=R(i);

Explanation

Create Source and Result matrices of appropriate size, filled with zeros.

R=S=zeros(max(y+3),max(x+3));

Calculate the linear indices that correspond to the xy-pairs, with one element padding at the borders.

i=sub2ind(size(S),y+2,x+2);

Draw the structure.

S(i)=1;

S is shown here for Example 2:

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

Remove all border elements by image erosion

S=imerode(S,strel('disk',1,0))

using the structuring element disk with radius 1:

0   1   0
1   1   1
0   1   0

If diagonal movement was allowed, we would instead use the rectangle:

1   1   1
1   1   1
1   1   1

Then, increment the result for all non-border elements

R+=S;

and loop until the image is completely eroded.

while nnz(S)

Return the result for each xy-pair.

v=R(i);


Jelly, 16 bytes

ḟṚṁṣj
z-ç€-ZFḟ-ṁ

Try it online! or verify all test cases.

How it works

z-ç€-ZFḟ-ṁ  Main link. Argument: M (matrix / 2D array)

z-          Zip the rows of M, using -1 as filler.
  ç€-       Map the helper link over the result, with right argument -1.
     Z      Zip the rows of the result.
      F     Flatten the resulting matrix.
       ḟ-   Filterfalse -1; remove all occurrences of -1.
         ṁ  Mold; shape the result like M.

ḟṚṁṣj       Helper link.
            Left argument: A (row / 1D array). Right argument: -1

ḟ           Filterfalse; remove all occurrences of -1.
 Ṛ          Reverse the resulting vector.
   ṣ        Split A at occurrences of -1.
  ṁ         Mold; shape the vector to the left like the 2D array to the right.
    j       Join the resulting 2D array, separating by -1.


MATL, sequence A005206. Cracked by SamYonnou

voOdoO

Try it online!

The hidden string has 8 bytes.


05AB1E, 4 bytes

Ÿ.RÒ

Explanation:

Ÿ       Create a list [a .. b]
 .R     Pick a random element
   Ò    Prime factors.

Try it online!


Jelly,  5  4 bytes

Ḋ²ḋṖ

Try it online!

How?

Implements  \$\sum_{i=2}^n{(i^2(i-1))}\$...

Ḋ²ḋṖ - Link: non-negative integer, n
Ḋ    - dequeue (implicit range)       [2,3,4,5,...,n]
 ²   - square (vectorises)            [4,9,16,25,...,n*n]
   Ṗ - pop (implicit range)           [1,2,3,4,...,n-1]
  ḋ  - dot product                    4*1+9*2+16*3+25*4+...+n*n*(n-1)


Is there a shorter way to get user input in python?

If prompting the user doesn't matter, this is slightly shorter than eval for 3 or more:

a,b,c=map(input,[1]*3)
a,b,c=map(input,'111')

It's also shorter even if prompting is not ok:

a,b,c=map(input,['']*3)

Sadly, xnor's idea doesn't save anything for 2 inputs as it is still longer (19 bytes). However if you have some string (or appropriate iterable) with the appropriate length already (because magic?) then it could be shorter.

xnor found an example of a magic string for 3 inputs in Python 2 only:

a,b,c=map(input,`.5`)

This also requires that the prompts not be important, though.

This trick actually helps to save bytes for large numbers of inputs by using 1eX notation (getting x+3 inputs):

 a,b,c,d,e,f=map(input,`1e3`)

Explanation:

Python's map function performs the function it is passed on each element of the iterable that is also passed to it, and returns the list (or map object) containing the results of these calls. For the first example, the map could be decomposed to:

[input(1), input(1), input(1)]


GolfScript, 12 bytes

{`'.~'+:n}.~

Try it online!

Explanation

This combines ideas from the standard GolfScript quine:

{'.~'}.~

And my recently discovered quine:

":n`":n`

The main idea is again to use n which is printed implicitly at the end of the program in order to get the additional copy of the quine. Since assigning the variable doesn't change anything when it's done again in subsequent copies, this will only add one copy. Here's a breakdown of the code:

{        # Standard quine framework. This pushes the block, duplicates it and runs the
         # second copy, such that it can process the first copy to create a quine.
  `      # Convert the block to its string representation.
  '.~'+  # Append the string '.~' to make a complete quine. This is simply left on the
         # stack to be printed at the end.
  :n     # Store the string in n such that one more copy is printed at the end.
}.~


V, 31, 30 bytes

êuòIRed -
IBlack -
òñFRdH

Try it online!

Hexdump:

00000000: 16ea 75f2 4952 6564 202d 201b 0a49 426c  ..u.IRed - ..IBl
00000010: 6163 6b20 2d20 1b0a f2f1 4652 6448       ack - ....FRdH

This is trivial in V, but the edge case of odd inputs makes it tricky because V doesn't really have conditionals. Thankfully, we can handle this at the relatively small cost of +6 bytes.


Program which behaves differently in/out of a debugger

x86 and x64_64 machine language on Linux and OSX, 1 byte

0x0:  CC    int3

Try it online!

int 3 throws a SIGTRAP which will cause a debugger to stop as if it encountered a breakpoint. Outside of a debugger, the kernel terminates the process (thanks to @Ruslan for the correction).

C (gcc) (x86 Linux and OSX), 14 11 9 bytes

main=204;

Try it online!

The integer 204 corresponds to the int 3 instruction; the TIO link is the same as above.


Python 3, 431 bytes

Not very golfed right now, but I figure I'd get the ball rolling with an answer. Try it here, g() is the main function.

import re,itertools as H
def g(i):
 y=re.sub(r'\W','',''.join(set(i)).upper());l=i.split()
 def e(s):
  def f(a):
   for v,w in a:exec(v+'='+w)
   return eval(re.sub('[^A-Z()]+',lambda x:{'v':' or ','^':'*','<->':'==','->':'<=','-':'not '}[x.group()],s))
  return[c for c in H.product("01",repeat=len(y))if f(zip(y,c))]
 for n in range(len(l),-1,-1):
  for q in H.combinations(l,n):
   if e('('+')^('.join(q)+')'):return' '.join(q)


Matrix trace for any matrix through... Bresenham’s line rasterisation

Jelly, 25 bytes

ZXL>LƲ¡µLḶ÷’Ɗ×XL’Ɗær0ị"OS

Try it online!


Python 2, 133 130 127 bytes

def f(l):r=range(len(l));v,c=zip(*l);print min((v[j]-v[i],r[i:j+1])for i in r for j in r if s(*c)==s(*c[i:j+1]))[1]
s={0}.union

Try it online!


Python 3.8, 95 bytes

import re
lambda x:[((t:=re.match(r'\[(\w*)\]',s)or t)[1],s.split(t[0])[-1].strip())for s in x]

Try it online!
(Expanded TIO example with input)
Explanation:
Python 3.8 is required for the := operator. This takes a list of strings as input, and outputs a list of (tag, body) tuples. First, it uses a Regex match to get the tag:
t:=re.match(r'\[(\w*)\]',s)or t)

This matches any initial sequence of word characters (alphanumeric + underscore) enclosed in square brackets, with the words as a capturing group. If the string does match this regex, t will be a match object with two elements: the full match and the group. For example, if the string is [tag] body, the match will have the elements [tag] and tag.
If the string does not match this regex, then re.match() returns None. The code becomes t = None or t, which is just t = t, so the tag keeps its value from the previous line. If the first line didn't have a match, this would cause an error, but we don't need to worry about that!
The code then constructs the tuple t[1], s.split(t[0])[-1].strip(), where t[1] is the capturing group (the tag without square brackets) and t[0] is the tag with square brackets. Splitting the string on the full tag isolates the body, whether or not the tag actually exists in the string.


LabVIEW, 166 LabVIEW Primitives

First of all i did not create 2 seperate programms because Labview does dataflow so theres really no need.

Saves the histogramm with first element = ascii code of first letter rest from 1-26 go by amount. Lenght simply gets saved in an array.

The first word has 3 checks, first letter, lenght and available letters in histogram. The first letter check stops after the first word.

I check the histogram by decrementing it for every letter and checking if it would fall below 0.

If i found my Nth word and there are no words that are buildable from the left over letters i will start deleting words from the dictonary and redo the Nth word and so on until i have found a solution.

This might or might not work for sentences there are, since that would take forever to compute (my example took a few seconds already).

What i tried

In: Zulus win.
Out: Zulus win.

In: Dovecot flagships oleander.
Out: Dolphin advocates forelegs.

In: Abash abel mammal test.
Out: Amass abbe hamlet malt.


MATL, 9 bytes
&)i:&)bwv

This solution accepts an array of T (true) and F (false) values as the second input. Also for the first test case, with empty arrays, it produces no output.
Try it Online! and a slightly modified version for all test cases.
Explanation
    % Implicitly grab the first two inputs
&)  % Index into the first array using the boolean, places two items on the stack:
    % 1) The values where the boolean is TRUE and 2) the values where it is FALSE.
i   % Explicitly grab the third input (N)
:   % Create an array from 1...N
&)  % Index into the FALSE group using this array as an index. Puts two items on the stack:
    % 1) The first N elements of the FALSE group and 2) other members of the FALSE group
b   % Bubble the TRUE members up to the top of the stack
w   % Flip the top two stack elements to get things in the right order
v   % Vertically concatenate all arrays on the stack
    % Implicitly display the result


Python 2, 73

n=input()
e=10**(len(`n`)/2)-1
N=n/e+n%e*2/e;N-=N>e+1
print n==N*e or N*e

A six-digit pseudo-cyclic number like 637362 is pseudo-cyclic exactly if it's a multiple of 999, except for 999999. So, we're looking for the multiple of 999 nearest to the input n. In general, replace 999 with e, which is one less that 10**(num_digits/2).

The nearest multiple below can n be found with integer division as n/e*e. We check whether to round up with n%e*2/e, which is 1 if n%e is closer to e, and 0 if it's closer to 0. In the latter case, we add e. We also handle the 999999 case by subtract if N is too large.

Finally, before printing, we check if the original number was a multiple of e and thus already pseudo-cyclic.


ProtectiveBot

A bunch of ideas rolled together to form something. There are a number of states that it can enter. Firstly, if there is no-one around them, it will build itself a cocoon which is just about indestructible, and sit in it for a while, killing anyone it can.

If there is someone close during startup, there is less then 200 turns left, or there is only one enemy bot remaining, the bot will enter a aggressive mode, which is essentially an enhanced pathfinder, attempting to trick its opponents. This mode uses a flood style pathfinding system at close range, and the same technique in the provided pathfinding example at long range.

If there are multiple instances of this bot in game, the bots will refrain from killing each other until the end.

Its big as well, weighing in at 527 741 lines. Compiling against Java 8. Also, have a graphic renderer of the battle system: https://github.com/j-selby/RobotBattleController

  I've reached the limit for how big these posts can be, see bot src at
  https://github.com/j-selby/RobotBattleController/blob/master/src/main/java/ProtectiveBot.java.
  Sorry...

Rev 3:

Threaded pathfinding. No more timeouts!
Detection of stalemates. TODO: Do something about them.
Full A* pathfinding. No more dumb stuff.
Checks OTHER bots positions for unfair play (trapping themselves in completely).

Rev 2:

Stopped bot being killed at corners
Smarter building logic
Will never do any move that could endanger us, excluding against other instances of ProtectiveBot.


TeX - 38 bytes Cracked(ish)
This is worth a shot, because I can't imagine anyone on a site about writing short pieces of code would know TeX:
\read16to\x\message{Hello, World!}\bye

To run it, you should get a hold of some form of TeX that allows interactive mode. Save this to a file, and run TeX (or pdfTeX, XeTeX, etc.) on it.
Edit: I'm currently considering this semi-cracked. The intended solution uses input from stdin, but TeXnically input from the way the program is invoked is valid. I'll be adding more devious TeX answers if someone gets the intended method.
Here's the intended solution:

 ^C Ia - The first key is control-c, which causes an error. Then, you press I (capital i) to input a command. Then you type a (or anything else to be typeset). Normally, the message that was printed to stdout would be followed by a space and then a ')'. When you typeset something, it causes the font information to be output after the message. That means that a newline is thrown in, and the ')' gets moved later.

That may be underhanded, but should still be within the rules of the game.


C, 650 600

n=8,t=65,s,f,x,y,p,e,u=10,w=32,z=95;char a[95],b[95]="RNBKQBNR";v(){p=a[s]&z;y=f/u-s/u;x=f-s-y*u;e=x*x+y*y;n=s%u/8|f%u/8|a[s]/w-t/w|a[f]/w==t/w|!(p==75&e<3|p>80&x*y==0|p%5==1&x*x==y*y|p==78&e==5|p==80&x*(z-t)>0&(a[f]-w?e==2:e==1|e==4&s%5==1));if(!n&&p-78)for(e=(f-s)/abs(x*x>y*y?x:y),x=s;(x+=e)-f;)n|=a[x]-w;}main(){for(a[93]=40;n--;a[92]=47)sprintf(a,"%s%cP    p%c \n",a,b[n],b[n]+w);for(;1;){puts(a);for(n=1;n;){putchar(t);scanf("%d%d",&s,&f);v();memcpy(b,a,z);if(!n){a[f]=p-80|f%u%7?a[s]:t+16;a[s]=w;a[f]&z^75||(a[z-t/w]=f);f=a[z-t/w];t^=w;for(n=1,s=80;n&&s--;)v();if(n=!n)memcpy(a,b,z),t^=32;}}}}

To reduce the code for initializing the board, the display has White (uppercase) playing from left to right and Black (lowercase) playing from right to left. Input is in the form of two 2-digit decimal numbers (start position and finish position), giving file(0-7) and rank(0-7). For a bit of extra code (subtract 11 from each input), input could be made to comply with http://en.wikipedia.org/wiki/ICCF_numeric_notation (digits 1-8)
Here's a sample screenshot where Black has just advanced his Rook's Pawn. White tries various illegal moves with his queen, before finally capturing the pawn. Turn indicators are a for Black and A for White.

An interesting feature of my validation is the use of the square of the Euclidean distance. For the knight this is always 1^2+2^2=5, but I also use it for the King and the pawn.
Test for Check is done by backing up the board, carrying out the players move, and scanning all 64 possible opponent's moves.
The program has to be ended with Ctrl-C. I cant think of a more gracious way of doing it, other than putting in a special move to end the program. A game of chess actually ends when one player is unable to move on his turn (checkmate or stalemate) and that requires a lot of tests that arent required by the spec.
Commented code
n=8,t=65,s,f,x,y,p,e,u=10,w=32,z=95;                 // 8,10 height and width of board. w=ASCII space, also difference between ucase and lcase
                                                     // 95 is bitmask for conversion lowercase to uppercase, but also used as length of array, etc.
char a[95],b[95]="RNBKQBNR";                         // a is main board, b is backup board (but used at start to hold 1st row data.)

v(){                                                 // validate move in all aspects except check
  p=a[s]&z;                                          // p=uppercase(character on start square)
  y=f/u-s/u;                                         // signed distance in y direction
  x=f-s-y*u;                                         // and x direction
  e=x*x+y*y;                                         // square of Euclidean distance
  n=s%u/8|f%u/8|                                     // n=true if 2nd digit of input out of bounds OR
  a[s]/w-t/w|a[f]/w==t/w|                            // start sq not friendly piece OR finish sq is friendly piece (also eliminates case where start=finish)
  !(                                                 // OR NOT geometry valid
    p==75&e<3|                                       // 'K'(ASCII75) AND euclidean distance squared =1 or 2 OR
    p>80&x*y==0|                                     // 'Q'or'R' AND x or y = 0 OR
    p%5==1&x*x==y*y|                                 // 'Q'or'B' AND abs(x)=abs(y)
    p==78&e==5|                                      // 'N' AND euclidean distance squared = 5
    p==80&x*(z-t)>0&(a[f]-w?e==2:e==1|e==4&s%5==1)   // 'P'(ASCII80):x direction must correspond with case of player (z-t)
  );                                                 // if capturing e=2. Otherwise e=1 (except on start rows 1 and 6, e can be 4)
  if(!n&&p-78)                                       // if not yet invalid and piece not 'N'(ASCII78)
    for(e=(f-s)/abs(x*x>y*y?x:y),x=s;(x+=e)-f;)      // Set e to the numeric difference to travel 1 square in right direction. Set x to start square
       n|=a[x]-w;                                    // and iterate x through all intervening squares, checking they are blank
}

main(){

  for(a[93]=40;n--;a[92]=47)                         // iterate n through 8 rows of board. vacant spaces in bracket are use to assign start positions of kings to a[92&93]
    sprintf(a,"%s%cP    p%c \n",a,b[n],b[n]+w);      // build up start position, each row 10 squares wide, including filler space the end and newline

  for(;1;){                                          // loop forever
    puts(a);                                         // display board
    for(n=1;n;){                                     // loop while move invalid
      putchar(t);                                    // display prompt 'A' for white 'a' for black
      scanf("%d%d",&s,&f);                           // get input
      v();                                           // validate move
      memcpy(b,a,z);                                 // backup board (and king position metadata)
      if(!n){                                        // if move not yet invalid
        a[f]=p-80|f%u%7?a[s]:t+16;                   // if not a pawn on last row, content of finish square = start square, ELSE queen of correct case (t+16)
        a[s]=w;                                      // start square becomes blank (ASCII32)
        a[f]&z^75||(a[z-t/w]=f);                     // if finish square king, update king position metadata
        f=a[z-t/w];                                  // to begin scanning to see if king in check, set f to current king position
        t^=w;                                        // and change colour
        for(n=1,s=80;n&&s--;)v();                    // for s=79..0 search for valid opponent move to capture king (stops with n=0)
        if(n=!n)memcpy(a,b,z),t^=32;                 // valid opponent threat on king means invalid player move. Invert n, recover board from backup and change colour back.
      }
    }
  }
}


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

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

\AR

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

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

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

Without it:

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

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

1R1+R

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

Example output:

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

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

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

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

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

Old: 5 bytes (with the -t flag)

1R1R

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

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

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

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


Ruby, 629 bytes
s=gets
p=c=0
'PETeRborOuGh
NORWich
IPSwicH
BIRMiNGHam
CARdiff
SWANsea
BAngOr
CHEsTer
SHREWsbURY
CHELmSFOrd
NOTTInGHAm
LInCOlN
MAIDStone
BRIgHtON
BOURNEMoUth
PORTSMoUth
ISLE OF WIGHt
PORtSmOUtH
BOREHAMwoOD
NORTHAmPton
WIMBLeDoN
BOREHAMwOoD
SIdcup
MANChESTer
NEWCAstle
STOcKtON
oXFOrd
PReStON
CArlISlE
ReADIng
GLAsGoW
EDINBUrGh
DUNdEe
ABERDEen
INvErNEsS
WORcESTer
EXeTeR
TRUro
BRiStoL
PERSONAL eXPOrt
LeEds
SHEFFiElD
BEVERLEY'.split($/).map{|w|c<s[0,2].to_i(35)&&p=w;d=0;w.bytes{|b|d+=d+b/95};c+=d}
y=(?1+s[2,9]).to_i-1
puts p.capitalize+", 1/%d/20%02d to %d/%d/20%02d"%[z=3+y%100/50*6,1+y%=50,z<4?31:y%4==2?29:28,(z+5)%12,1+y+z/9]

The first two letters are interpreted as a base 35 number and then looked up to find the correct town. The quantity of addresses assigned to each town is encoded (run-length encoding) in the captialization of each town in binary, where uppercase=0 and lowercase=1.
In order to handle the Y age indicator for the first half of 2001, a 1 is prepended to the age. Thus 1 Y is interpreted by .to_i as 1, and 1 02 is interpreted as 102. 1 is subtracted (to handle the wraparound for 2050) and taken modulo 100 to decide which half of the year we are in. It is then taken modulo 50 (and the 1 added on again) to find the year.


Ruby, 79
->n{1.upto(n*=3){|i|puts (' '*(n-i)).ljust(n+i,'/__\_\/\ \__/_/\/ '[i%3*6,6])}}

A. (-4 bytes, -1 +1) changed from 0-indexed (.times) to 1-indexed (1.upto)
B. (-5 bytes) changed from array of three 6-char strings to selection of 6-char substring of 18-char string.
C. (-1 byte) m=n*3 -> n*=3
D. (-5 bytes) reduced all five double backslashes to single backslashes (partly made possible by reordering of string required for point A)
Ruby, 94
->n{(m=n*3).times{|i|puts (' '*(m-i-1)).ljust(m+i+1,[ '/\\ \\__','/_/\\/ ','/__\\_\\'][i%3])}}

explanation
The basic unit is a 3x6 diamond as follows (last character on each row duplicated for clarity:)
    /\ \__/
   /_/\/ /
  /__\_\/

All we need to do is display a suitable window of this pattern. Ruby's ljust allows you to pad with any string, not just spaces. Normally ljust would be used to pad a string of printable characters by adding spaces at the end, but here we use it in reverse: to pad a string of spaces by adding printable characters at the end.
ungolfed in test program
f=->n{
  (m=n*3).times{|i|                  #for each line of the triangle
    puts (' '*(m-i-1)).              #print m-i-1 spaces,
      ljust(m+i+1,[ '/\\ \\__',      #left justified and padded to total length m+i+1
                   '/_/\\/ ',        #by one of these three strings
                  '/__\\_\\'][i%3])
  }
}

f[gets.to_i]


Haskell, 63 bytes

f(a:b:c)|s<-[a,b..last c],all(`elem`s)c=s
f a=r$f$r a
r=reverse

Try it online!

Basically works by trying to build the result from the front and, if that fails, from the back. This uses the fact that the first and last members of the input will always be correct, the fact that deleted members have to be consecutive, and the fact that there will always be at least three items in the input. All I have to do is assume that the second or second-to-last members are accurate and check if it works. Luckily Haskell has really beautiful syntax for creating arithmetic series.

EDIT: thanks to @xnor for pointing out a bug and providing a solution!


Mathematica, 192 bytes

This type of challenge (nontrivial mathematical computation together with high-level graphics output) is what Mathematica is made for!

(d=#;r_~t~n_:=r{Sin[#],Cos[#]}&[6.3n/d];m=Mod[10#,d]&;Graphics@{Array[#~Text~t[9,#]&,d,0],Array[Arrow@{t[9,#+1/7],t[9,#+6/7]}&,d],Array[Arrow@BezierCurve@{t[8,#+1/9],{0,0},t[8,m@#-1/9]}&,d]})&

Expanded and explained:

[1] (
[2] d = #; r_~t~n_ := r {Sin[#], Cos[#]} &[6.3 n/d]; m = Mod[10 #, d] &;
[3] Graphics@{
[4]   Array[#~Text~t[9, #] &, d, 0],
[5]   Array[Arrow@{t[9, # + 1/7], t[9, # + 6/7]} &, d],
[6]   Array[Arrow@BezierCurve@{t[8, # + 1/9], {0, 0}, t[8, m@# - 1/9]} &, d]
[7]          }
[8] ) &

Lines 1 and 8 delimit an unnamed function of one argument. Lines 3 and 7 delimit several commands that output graphics.

Lines 2 stores the input as d; defines a binary function t giving the coordinates of a point n/d of the way around the circle of radius r, clockwise from the top (in the spirit of this site, I saved a byte by rounding 2π to 6.3!); and defines a unary function m calculating the destination of the arrow starting at its argument.

Line 4 renders the numbers 0 to d–1 equally spaced around the circle of radius 9 (the exact radius unimportant, chosen to maximize aesthetics subject to fitting in one byte).

Line 5 renders the clockwise straight arrows around the circumference of the circle. The 1/7 and 6/7 leave enough space to read the numbers.

Line 6 renders the curved arrows from each number to (10 times the number modulo d). BezierCurve automatically draws a Bézier curve using the given control points. Fortunately, using the origin as a single interior control point produces reasonable output.

Sample output (note that the cases 9, 10, and 11 are trivial in different ways):

d = 7

d = 8

d = 9

d = 10

d = 11

d = 12

d = 13

d = 37

This last input was chosen because 37 divides 10^3–1, and so the interior arrows (not counting the obligatory self-arrow from 0 to 0) form lots of triangular cycles.


Imaginary Parts of Non-Trivial Riemann Zeroes

Mathematica, 23 bytes

⌊Im@ZetaZero@#+.5⌋&

Unfortunately, Round rounds .5 to the nearest even number, so we have to implement rounding by adding .5 and flooring.


Shortest self-avoiding path given a sequence of turns

Prolog, 284 bytes

e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
n(X):-X=0;n(Y),X#=Y+1.
p(S,L):-n(L),length(X,L),e([0|S],X),c(X,_,_).

This is a pretty straightforward statement of the algorithm, and fairly inefficient (not all the test cases ran in reasonable time, although most did). It works via generating all possible lengths for the output from 1 upwards (n); generating all possible sequences of left/forward/right of that length which are consistent with the input (implemented in e; the new path is called X); then checking for the first such path that's valid (c, which calls into v to handle the effects of left and right turns on the x and y deltas). The return length is the first output seen in L. (+2 penalty if you want to prevent the function returning other possible outputs for the length if you backtrack into it; it's never quite clear how Prolog's idiosyncratic function returns should be counted.)

There isn't much in the way of golfing tricks here, but there is some. n was implemented with a constraint solver because it allows more whitespace to be removed without confusing the parser; this might require GNU Prolog to be used, not sure on that. (I couldn't do the same in c as it needs to handle negative numbers.) The implementation of e is considerably less efficient than it needs to be, via matching a list in multiple ways; the more efficient e([],[]). would be six bytes longer (it'd allow the S=X; on line 2 to be removed, but that's only a gain of four compared to a loss of ten). To allow me to match coordinates and directions as a whole, or just part, I represent them as X/Y (i.e. an unevaluated AST, which can be matched on), allowing me to use infix notation.

Prolog, 256 bytes, too inefficient to easily test

Of course, because this is Prolog, many of the functions are reversible, e.g. c can be used to generate all paths from the origin to a particular coordinate pair. Additionally, c naturally generates from shortest to longest. This means that instead of asking for a minimum length explicitly, we can just get c to generate all paths that go anywhere, then look for the first one that's consistent with the input:

e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
p(S,L):-c(X,_,_),length(X,L),e([0|S],X).

This has exponential performance (O(3n), where n is the output). However, I did manage to verify it on some of the smaller tests (it takes around 7 seconds to output 14, and around 20 to output 15, on my computer).


Python 2, 69 67 bytes

a,b=x=[[],[]];k=0
for n in input():x[n>0]+=n*n,n*k>0;k=n
print a==b

Try it online!


JavaScript (ES6), 107
As an anonymous method with no parameters
Note 1483228800000 is Date.UTC(2017,0)
_=>` _     __    __
  |   |  | |   |
  |_  |__| |   |
`.repeat((Math.abs(new Date-14832288e5)+36e5-1)/36e5)

Test This keeps updating every 1 minute, but you'll need a lot of patience to see the output change.

F=_=>`_     __    __
 |   |  | |   |
 |_  |__| |   |
`.repeat((Math.abs(new Date-14832288e5)+36e5-1)/36e5)

update=_=>O.textContent=F()

setInterval(update,60000)

update()


CJam, 53

'[,73>qf{1$e=s':+\+~}:+3*I+O-SZ-JO+m0e>ZS-LO+-e>2+3/-

Try it online

The idea is: assign each of the I, J, ..., Z variables to be the number of occurences of that letter, and calculate string length * 3 + I - O. Then count the number of non-compensated S's or Z's: an S can be compensated by Z, J or O, and a Z can be compensated by S, L or O, and subtract ceil(that number/3), as we lose 1 unit for every 3 S's or Z's.


Python 2, 73 72 69 bytes
-1 byte thanks to dingledooper!
-3 bytes thanks to Sisyphus!
Prints the rows indefinitely.

c=a=[0]
b=[1]
while 1:print b;a,b=b,map(sum,zip(c*2+a,a+c*2,c+b,b+c))

Try it online!


Haskell, 141 characters

c('\\':a:z)s=a&s>>=c z
c(a:z)s=a%s>>=c z
c[]s=[null s]
p&(a:z)|a==p=[z]
_&_=[]
'?'%(a:z)=[z]
'*'%a=a:'+'%a
'+'%(a:z)='*'%z
l%a=l&a
g=(or.).c

Works for all input, both patterns and strings to match against. Handles trailing backslash in the pattern as a literal match (behavior was unspecified.)

This can be run with the following test driver:

main = do
    globtest "abc" "abc"    True
    globtest "abc" "abcdef" False
    globtest "a??" "aww"    True
    globtest "a*b" "ab"     True
    globtest "a*b" "agwijgwbgioeb" True
    globtest "a*?" "a"      False
    globtest "?*" "def"     True
    globtest "5+" "5ggggg"  True
    globtest "+" ""         False
    globtest "a\\*b" "a*b"  True
  where
    globtest p s e =
      if g p s == e
        then putStrLn "pass"
        else putStrLn$"fail: g " ++ show p ++ " " ++ show s ++ " /= " ++ show e

Update: I wrote a blog post about this particular answer, as I think it shows off well how Haskell so easily encodes the problem.

Edit: (181 -> 174) replaced d and m with operators
Edit: (174 -> 151) inlined r into c
Edit: (151 -> 149) removed an unnecessarily generated option in the + case
Edit: (149 -> 141) removed an unnecessary clause for %, which was handled by &


Shortest Uniquely Identifying Substrings

Jelly,  12  9 bytes

Ẇ€ŒpẇþÞ⁸Ḣ

Try it online! Or see the test-suite (takes ~35s)


bash and friends (168 167 chars)

T=ANBYCODUEPFXGQHVIRJZKSLWMT
while read x&&[ "$x" != "DONE" ]
do
[ "$x" \> "E" ]
for((z=1+$?*58;z;z--))do
x=$(tr a-zA-Z `tr A-Z a-z<<<$T`$T<<<$x)
done
echo ${x:6}
done

The magic number isn't so magic: it's obtained by solving a set of simultaneous modular identities obtained from the cycle structure of the permutation.


Common Lisp, 99

The following 99 bytes solution is a CL version of the nice Scheme answer.

(defun g(l n &optional(o'l))(if(eql n l)o(and(consp l)(or(g(car l)n`(car,o))(g(cdr l)n`(cdr,o))))))

I originally tried to make use of position and position-if, but it turned out to be not as compact as I would have liked (209 bytes):

(lambda(L x &aux(p'l))(labels((f(S &aux e)(cons(or(position x S)(position-if(lambda(y)(if(consp y)(setf e(f y))))S)(return-from f()))e)))(dolist(o(print(f L))p)(dotimes(i o)(setf p`(cdr,p)))(setf p`(car,p)))))

Expanded

(lambda
  (l x &aux (p 'l))
  (labels ((f (s &aux e)
             (cons
              (or (position x s)
                  (position-if
                   (lambda (y)
                     (if (consp y)
                         (setf e (f y))))
                   s)
                  (return-from f nil))
              e)))
    (dolist (o (print (f l)) p)
      (dotimes (i o) (setf p `(cdr ,p)))
      (setf p `(car ,p)))))

Example

(funcall *fun* '(4 5 (1 2 (7) 9 (10 8 14))) 14)

The list is quoted, but if you really want, I can use a macro.
The returned value is[1]:

(CAR (CDR (CDR (CAR (CDR (CDR (CDR (CDR (CAR (CDR (CDR L)))))))))))

For tests, I used to generate a lambda form where l was a variable:

(LAMBDA (#:G854) (CAR (CDR (CDR (CAR (CDR (CDR (CDR (CDR (CAR (CDR (CDR #:G854))))))))))))

Calling this with the original list returns 14.

[1] (caddar (cddddr (caddr l))) would be nice too


Javascript, Score = 1663.46768

function X($){S=Math.sqrt;function J(A){return A.join("")}function M(A,B){return A.length<B.length?A:B}function D(q){var w="",e,r,t,y;for(e=9;e>1;e--){r=~~(q/e);t=r*e-q;if(t==0)y=J([G(r),e,"*"]);else y=J([G(r),e,"*",G(-t),"+"]);if(w=="")w=y;w=M(w,y)}return w}function Q(a){var s=~~S(a),d=a-s*s,f=J([G(s),">*",G(d),"+"]),g;s=Math.ceil(S(a));d=s*s-a;g=J([G(s),">*",G(d),"-"]);return M(f,g)}function G(z){var x,c,v,b,n,m;if(z==0)return"22-";if(z==1)return"22/";if(z>1&&z<10)return""+z;if(z>9&&z<19){x=~~(z/2);c=z-x;return J([x,c,"+"])}for(v=9;v>1;v--){b=~~(z/v);if(b>1&&b<10&&b*v==z)return J([v,b,"*"])}n=S(z);if(~~n==n)return J([G(n),">*"]);return M(D(z),Q(z))}return G($)}

This is my attempt for my question, and this is output. Code size is 671, and output size is 1304. Score is 1663.46768 (rounded up to 5 decimal places).


CJam, 18 15 bytes

{1$#)}q~2$,@$p;

Try it online in the CJam interpreter.

I/O

Input:

"mig" ["imig" "mig" "migd" "do" "Mig"]

Output:

["mig" "migd" "imig"]

How it works

      q~        e# Read and evaluate the input from STDIN.
                e# Pushes a needle and an array of haystacks.
{    }          e# Define a code block:
 1$             e#   Copy the needle.
   #            e#   Compute the index of the needle in the haystack.
    )           e#   Add 1 to the index.
        2$      e# Copy the block.
          ,     e# Filter: Keep only haystacks for which the code block
                e#         pushed a non-zero value.
           @    e# Rotate the block on top of the stack.
            $   e# Sort: Arrange the haystacks according to the values
                e#       pushed by the code block.
             p  e# Print the filtered and sorted haystacks.
              ; e# Discard the needle.


Python 3, 30 28 bytes

lambda m:len({*m})+1==len(m)

Try it online!

{*m} casts the list to a set object, an unordered list of items without duplicates. Doing this will always decrease the length of the list by the number of duplicates in it. By computing how much the length has changed, we can easily tell if the list had a single duplicate and return the result of the test.

-2 bytes thanks to ovs.


Check if 2 arrays contain the same element

Actually, 1 byte
∩

Try it online!
This is merely the set intersection built-in. The resultant value is the intersection of the two sets - a non-empty list (which is a truthy value) if there is an intersection, and an empty list (which is a falsey value) otherwise.
Complexity
According to the Python Wiki, set intersection has a worst-case time complexity of O(N*M) (where N and M are the lengths of the two sets). However, the time complexity is only that bad when the two sets contain distinct objects that all have the same hash value (for example, {"some string"} & {hash("some string")}). Since the set elements are only integers in this case (and no two integers hash to the same value unless they are equal), the actual worst-case complexity is O(min(N, M)) (linear in the length of the smaller of the two sets). The construction of each set is O(N) (linear in the number of elements), so the overall complexity is O(max(N, M)) (the complexity is dominated by the construction of the larger set).


Print out a shape in printable ASCII art based on a specific number of sides provided by the user

Java, 1887 1866 bytes
Try in on Ideone
Saved 21 bytes due to unneeded "public" headers (Thanks to @Bálint!)
Not exactly a golfing challenge, but hey, why not?
I feel Java might actually be the best language for this challenge because no esolang could handle this, and many others don't have as good list manipulation (although Java's takes way more bytes).
Golfed:
import java.util.*;public class A{public static void main(String[]args){System.out.print((new P()).b(Integer.parseInt((new Scanner(System.in)).next())).s());}}class P{S p;public S b(int w){p=new S(w);int j=-1,k=-1,f=(w%2)*2,t,y,x;for(x=0;x<w/2-2+w%2;x++){t=r();y=r();if(j==t|k==y|t==y){x--;continue;}g(t,true,2);g(y,false,2-f);f=0;j=t;k=y;}while(1>0){t=r();y=r();if(w<4&t<1&y<1)continue;if(j==t|k==y|t==y|j==y){x--;continue;}g(t,true,3);g(y,false,3+(w<4?0:(w%2)*2));break;}return p;}void g(int w,boolean b,int h){if(w<1)p.u(h,b);else if(w<2)p.r(h,b);else p.l(h,b);}int r(){return (int)(Math.random()*3);}}class S{List<List<Character>>q,a;int h,s,u,o,e,r,b,t,g,n,m,x,y;public S(int d){s=d;h=s+s%2-1;u=h;o=h;b=s>3?(int)(Math.random()*3*s)+1:0;q=new ArrayList<List<Character>>();a=new ArrayList<List<Character>>();for(x=0;x<h;x++){q.add(new ArrayList<Character>());a.add(new ArrayList<Character>());}i(0,q);i(0,a);e=1;r=1;t=0;g=0;n=0;m=0;}public String s(){String p="";for(x=0;x<e+b+r;x++)p+=x>t+(s<4?1:0)&x<e+b+g?'_':' ';p+="\n";for(y=0;y<h;y++){for(x=0;x<e;x++)p+=y>h-2&x>n?'_':q.get(y).get(x);for(x=0;x<b;x++)p+=y>h-2?'_':' ';for(x=0;x<r;x++)p+=y>h-2&x<m-1?'_':a.get(y).get(x);p+="\n";}return p;}void i(int i,List<List<Character>>z){for(List<Character>l:z)l.add(i,' ');if(z==q){e++;if(i<=t)t++;if(i<=n)n++;}else{r++;if(i<=g)g++;if(i<=m)m++;}}void u(int v,boolean i){if(i){u-=v;for(y=0;y<v;)q.get(u+y++).set(t,'|');}else{o-=v;for(y=0;y<v;)a.get(o+y++).set(g,'|');}}void l(int v, boolean i){if(i){x=v-t;while(x-->0)i(0,q);t=x>0?0:t-v;u-=v;for(y=0;y<v;)q.get(y+u).set(t+y++,'\\');}else{x=v-g;while(x-->0)i(0,a);g=x>0?0:g-v;o-=v;for(y=0;y<v;)a.get(y+o).set(g+y++,'\\');}}void r(int v,boolean i){if(i){t+=v;y=t;while(e<=y)i(e,q);t=y-1;u-=v;for(y=0;y<v;)q.get(u+y).set(t-y++,'/');}else{g+=v;y=g;while(r<=y)i(r,a);g=v<1?g:y-1;o-=v;for(y=0;y<v;)a.get(o+y).set(g-y++,'/');}}}

Must be in file called A.java (for obvious reasons). To run:

In the terminal, type javac A.java
Then, if it gives you no errors, type java A
Finally, type the number of sides. This program actually supports side lengths up to 65536

As you can see in the example output below, the corners tend to be more open, and the sides not as smooth, as compared to the polygons in the examples. Also, it cannot produce a square, but still follows the official guidelines. If there are any problems I can change the answer to fix them.
Sample output:
3

  / |
 /  |
/___|

4
   ____
  /    \
 /      \
/________\

5
   _________
  /         |
 /          |
/           |
\           |
 \ _________|

6
  ____________
 |            \
 |             \
 |              \
 /               |
/_______________ |

7
 _____________________
\                     /
 \                   /
  \                 /
   |               /
   |              /
   \              \
    \ _____________\

8
 _______________
\               /
 \             /
  \           /
   |          \
   |           \
   /            |
  /____________ |

9
 __________
\          /
 \        /
  \      /
   |    /
   |   /
   /   \
  /     \
  |      |
  |_____ |

10
   ____
  /    \
 /      \
/        \
|         /
|        /
\        |
 \       |
  /      \
 /________\

EDIT: Finally! the ungolfed code is here! It's a bit long, but you probably already guessed that...
I will get to the explanation soon.
import java.util.*;
public class ASCII_Polygon_Driver
{
   public static void main(String[] args)
   {
      System.out.print(P.b(Integer.parseInt((new Scanner(System.in)).next())));
   }
}
class P
{
   static S p;
   public static S b(int w)
   {
      p = new S(w);
      int l1=-1,l2=-1,f=(w%2)*2,r1,r2,x;
      for(x=0;x<w/2-2+w%2;x++)
      {
         r1=r();
         r2=r();
         if(l1==r1){x--;continue;}
         if(l2==r2){x--;continue;}
         if(r1==r2){x--;continue;}
         g(r1,true,2);
         g(r2,false,2-f);
         f=0;
         l1=r1;
         l2=r2;
      }
      while(true)
      {
         r1=r();
         r2=r();
         if(w<4&r1<1&r2<1)continue;
         if(l1==r1|l2==r2|r1==r2|l1==r2){x--;continue;}
         g(r1,true,3);
         g(r2,false,3+(w<4?0:(w%2)*2));
         break;
      }
      return p;
   }
   static void g(int w,boolean b,int h)
   {
      if(w<1)p.goUp(h,b);
      else if(w<2)p.goRight(h,b);
      else p.goLeft(h,b);
   }
   static int r()
   {
      return (int)(Math.random()*3);
   }
}
class S
{
   public List<List<Character>> area1;
   public List<List<Character>> area2;
   private int wid1;
   private int wid2;
   private int spcb;
   public int hght;
   private int top1;
   private int top2;
   private int bot1;
   private int bot2;
   private int mid1;
   private int mid2;
   public int sides;
   private int x;
   private int y;
   public int y1;
   public int y2;
   public S(int numSides)
   {
      sides = numSides;
      hght = sides+sides%2-1;
      y1=hght;
      y2=hght;
      spcb = sides>3?(int)(Math.random()*3*sides)+1:0;
      area1 = new ArrayList<List<Character>>();
      area2 = new ArrayList<List<Character>>();
      for(x=0;x<hght;x++)
      {
         area1.add(new ArrayList<Character>());
         area2.add(new ArrayList<Character>());
      }
      insertCollum1(0);
      insertCollum2(0);
      wid1 = 1;
      wid2 = 1;
      top1 = 0;
      top2 = 0;
      bot1 = 0;
      bot2 = 0;
   }
   public String toString()
   {
      String out ="";

      for(x=0; x<wid1+spcb+wid2; x++)
      {
         out+=x>top1+1&x<wid1+spcb+top2?'_':' ';
      }
      out+="\n";
      for(y=0; y<hght; y++)
      {
         for(x=0; x<wid1; x++)out+=y>hght-2&x>bot1?'_':area1.get(y).get(x);
         for(x=0; x<spcb; x++)out+=y>hght-2?'_':' ';
         for(x=0; x<wid2; x++)out+=y>hght-2&x<bot2-1?'_':area2.get(y).get(x);
         out+="\n";
      }
      return out;
   }
   private void insertCollum1(int index)
   {
      for(List<Character> line : area1)
      {
         line.add(index,' ');
      }
      wid1++;
      if(index<=top1)top1++;
      if(index<=bot1)bot1++;
   }
   private void insertCollum2(int index)
   {
      for(List<Character> line : area2)
      {
         line.add(index,' ');
      }
      wid2++;
      if(index<=top2)top2++;
      if(index<=bot2)bot2++;
   }
   /*private void setChar1(int x, int y, char character, List<List<Character>> which)
   {
      which.get(y).set(x,character);
   }*/
   public void goUp(int howMany, boolean is1)
   {
      if(is1)
      {
         y1-=howMany;
         for(y=0;y<howMany;)
         {
            area1.get(y1+y++).set(top1,'|');
         }
      }
      else
      {
         y2-=howMany;
         for(y=0;y<howMany;)
         {
            area2.get(y2+y++).set(top2,'|');
         }
      }
   }
   public void goLeft(int howMany, boolean is1)
   {
      if(is1)
      {
         x = howMany-top1;
         while(x-->0)insertCollum1(0);
         top1 = Math.max(0,top1-howMany);
         y1-=howMany;
         for(y=0;y<howMany;)
         {
            area1.get(y+y1).set(top1+y++,'\\');
         }
      }
      else
      {
         x = howMany-top2;
         while(x-->0)insertCollum2(0);
         top2 = Math.max(0,top2-howMany);
         y2-=howMany;
         for(y=0;y<howMany;)
         {
            area2.get(y+y2).set(top2+y++,'\\');
         }
      }
   }
   public void goRight(int howMany,boolean is1)
   {
      if(is1)
      {
         top1+=howMany;
         y=top1;
         while(wid1<=y)insertCollum1(wid1);
         top1=y-1;
         y1-=howMany;
         for(y=0;y<howMany;)
         {
            area1.get(y1+y).set(top1-y++,'/');
         }
      }
      else
      {
         top2+=howMany;
         y=top2;
         while(wid2<=y)insertCollum2(wid2);
         top2=howMany<1?top2:y-1;
         y2-=howMany;
         for(y=0;y<howMany;)
         {
            area2.get(y2+y).set(top2-y++,'/');
         }
      }
   }
}


Haskell, 25 bytes

pred.until(<2)(/2).(+0.5)

Try it online!

Outputs decimals, one-indexed without the initial zero term.

Adds 0.5 to the input, then halves until the results is below 2, then subtracts 1. Using a pointfree expression saves 1 bytes over

f n=until(<2)(/2)(n+0.5)-1


CJam, 20 bytes

q':/~La+@~/(@@_{];}|

Try it online in the CJam interpreter.

How it works

q':/                e# Read all input and split it at colons.
    ~                e# Dump index, pattern and word on the stack.
     La+             e# Append the array [""] to the word.
                     e#   This increases the word's length by 1 (to deal with the
                     e#   highest index possible index) without affecting output.
        @~           e# Rotate the index on top and evaluate it.
          /          e# Split the word into chunks of that length.
           (         e# Shift out the first chunk.
            @@       e# Rotate pattern and remaining chunks on top.
              _      e# Copy the array of remaining chunks.
                     e#   This array will be empty if the index was too high.
               {];}| e# If the array if falsy, clear the stack.


JavaScript (ES7), 44 43 36 bytes

f=n=>--n?(f(n)**2+f).slice(0,4):1111

This is a great example of abusing type coercion: ** converts both its arguments to numbers, and + converts both its arguments to strings unless they're both numbers. This means that f(n)**2+f first converts f(n) to a number and squares it, then concatenates the result with the string representation of f. We can then use .slice to retrieve the first 4 chars of the string.

Here are a few alternate approaches that don't use strings:

f=(n,x=1111)=>x<1e4?--n?f(n,x*x):x:f(n,x/10|0)
f=n=>--n?(x=f(n))*x/(x>3162?1e4:1e3)|0:1111

Test snippet

let f=n=>--n?(Math.pow(f(n),2)+f).slice(0,4):1111
<input id=I type="number" step="1" min="1" value="1"><button onclick="console.log(f(I.value))">Run</button>

Note: this uses Math.pow because ** isn't supported in all browsers.


Get rid of whitespace on otherwise empty lines

Retina, 5 bytes

%G`\S

Try it online!

A not so obvious approach rewards us with a better score :)

Explanation

G indicates this as a Grep stage, keeping only those lines where a match to the regex given (\S, matches non-space characters) can be found. If it wasn't for the starting % this would completely remove lines instead of just "emptying" them.

The % is a modifier which applies the stage once to each line and then joins the results with newlines: in our case this means that the empty string returned by Grep for whitespace-only lines will become an empty line in the result.


Retina, 150 bytes
[ÀÁÂàáâ]
a
[ÉÊéê]
e
Í|í
i
[ÓÔóô]
o
[ÚÜúü]
u
T`L`l
ão|õe
im
[ck][aou]|qu[ei]|ke
ki
ç[aeiou]|ce
ci
g[aou]|gue
gui
j[aeou]|g[ei]
ji
(gu)i|[aeou]
$1i
ii
i

Try it online!
This is my first Retina program, so there's probably a lot of improvements to make. Suggestions are welcome.
Thanks to Martin for correcting some mistakes and for some golfing suggestions.
Explanation
I'm going to break up the explanation into 3 sections, to make it easier on me.
Section 1: Preprocessing
[ÀÁÂàáâ]
a
[ÉÊéê]
e
Í|í
i
[ÓÔóô]
o
[ÚÜúü]
u
T`L`l

The first 5 rules replace any accented vowel with the corresponding unaccented version. It's shorter to list out the matches in character classes (or, in the third case, as two options) than to use the culture-invariance and case-insentivity options each time. The last rule converts all ASCII letters to lowercase.
Section 2: Mimimification
ão|õe
im
[ck][aou]|qu[ei]|ke
ki
ç[aeiou]|ce
ci
g[aou]|gue
gui
j[aeou]|g[ei]
ji

These rules simply apply the substitutions specified.
Section 3: Cleanup
(gu)i|[aeou]
$1i
i+
i

The first rule matches any vowel except for the u in gui, and replaces them with is. The second rule removes repeated is.


Find the largest number of distinct integers that sum to n

05AB1E, 4 bytes

ÅTg<

Try it online!

Perfect tool for the job.

ÅT yields the list of Åll Triangular numbers up to and including N (unfortunately includes 0 too, otherwise it would be 3 bytes), g< gets the length and decrements it.


Fission, 7 bytes

'!+!NR"

A rather simple modification of the shortest Fission quine I have found so far: I'm simply using the non-destructive ! instead of O and added an N for newline.

So all in all, here is how it works: control flow starts at the R with a right-going atom. " toggles string mode, which means everything until the next " is printed: in this case '!+!NR. That leaves the " and the newline to be printed. '! sets the atom's mass to 33, + increments it to 34 (the character code of ") and ! prints the quote. N prints a newline, and R is now a no-op in this case, so the loop starts over.

The following 7-byte solution also works:

"NR'!+!


Python, 86 bytes

I should be sent to prison.

x=lambda c: ["happy","sad"][c[0]+c[-1:]in open(__file__).read(88)[::-1]]#<][><:>{:}(:)

The shortest I could come up with was equivalent to Martin's CJam answer, so I decided I'd hide all the sad emojis (minus the middle character if any) in the reverse of my code and use Python's __file__ quine cheat.

Muahahaha.


Perl 6, 31 bytes

{$^a;first {$a**$_~~/$a/},2..*}

Try it online!


mdahmoune, added Ruby, Levenshtein = 10
#include<stdio.h>
#define print(a) main(){int z[1];if(sizeof(0,z)==4)printf("C(gcc)");else printf("Perl5");}
print($=?"Ruby":"C++(gcc)")

Cycle is C -> Perl5 -> Ruby -> C++ -> C
I don't really know what I did (and I really don't know why it's valid in C and C++), I just ripped it off this answer.
C (gcc): Try it online!
Perl5: Try it online!
Ruby: Try it online!
C++ (gcc): Try it online!


C#, 1016 992 916 chars

Takes 4 seconds for me on the large test set; performance can easily be improved a lot by making X a HashSet<s> rather than a List<s>.

using System;using System.Collections.Generic;using System.IO;using System.Linq;using
s=System.String;class D<T>:Dictionary<s,T>{}class E:D<int>{static void Main(s[]x){s
S="",T=">",l;s[]b;D<E>R=new D<E>(),P=new D<E>();R[S]=new E();R[T]=new E();foreach(s L in
File.ReadAllLines(x[0])){b=L.Split('"');s f=b[1];R[T][f]=0;R[f]=new E();P[f]=new
E();R[f][T]=int.Parse(b[0].Trim());}foreach(s L in File.ReadAllLines(x[1])){b=L.Split('"');s
f=b[1],t=b[3],v=f+t;R[v]=new
E();R[v][S]=R[f][v]=R[t][v]=0;P[f][t]=R[S][v]=R[v][f]=R[v][t]=1;}for(;;){List<s>X=new
s[]{S}.ToList(),A=X.ToList();w:while((l=A.Last())!=T){foreach(s t in
R[l].Keys){if(!X.Contains(t)&R[l][t]>0){X.Add(t);A.Add(t);goto
w;}}A.RemoveAt(A.Count-1);if(!A.Any())goto q;}l=S;foreach(s n in
A.Skip(1)){R[l][n]--;R[n][l]++;l=n;}}q:if(R[S].Values.Contains(1))return;foreach(s
f in P.Keys)foreach(s t in P[f].Keys)Console.WriteLine(f+", "+t+", "+"ba"[R[f][f+t]]);}}

This uses the reduction to max flow which I hinted at earlier in comments. The vertices are

A newly generated source S and sink T.
The partnerships.
The cities.

The edges are

From the source to each partnership with flow capacity 1.
From each partnership to each city in the partnership with flow capacity 1.
From each city to the sink with flow capacity equal to that city's budget.

The algorithm is Ford-Fulkerson with DFS. It is obvious a priori that each augmenting path will increase the flow by 1, so the golfing optimisation of removing the computation of the path's flow has no negative effect on performance.

There are other possible optimisations by making assumptions such as "The names of the input files will never be the same as the names of the cities", but that's a bit iffy IMO.


Calculate the last digits of Graham's Number

dc - 21 chars

[3z202>xO200^|]dsxxrp

This takes about a minute on my computer, and would take lots longer for values larger than 200. It doesn't output leading zeroes.

Here's a slightly longer but faster version (26 chars):

[3rAz^|dz205>x]dsxxAz6-^%p
3[3rAz^|dz202>x]dsxxAz3-^%p # or an extra character for a few less iterations


Mathematica, 27 22 bytes

Range@#~GCD~#~Count~1&

An unnamed function that takes and returns an integer.

Not much to explain here, except that @ is prefix notation for function calls and ~...~ is (left-associative) infix notation, so the above is the same as:

Count[GCD[Range[#], #], 1] &


Jelly, 36 bytes

ạþE€Ṁ
®Œcç€®Ạ
A½×Ṡ×1,ıSµ€©œc3ñ€®Ṁ¬¢,

A full program printing the representation of a list of two ones/zeros.

This relies on theoretical infinite-precision floating point arithmetic, which is, of course, not the case. So here is a (43 byte) version which uses a 1e-10 leeway for the pair-wise distance comparisons it makes:

ạþI€×ȷ10ỊẠ€Ṁ
®Œcç€®Ạ
A½×Ṡ×1,ıSµ€©œc3ñ€®Ṁ¬¢,

Try It Online!

How?

(I'll include the replacement code used in place of E - equals to allow the leeway here)

ạþI€×ȷ10ỊẠ€Ṁ - Link 1: any all-equal distance complex numbers?: list of lists; list
ạþ           - outer-product with absolute difference
  I€         - incremental differences for €ach
    ×ȷ10     - multiply by 10^10
        Ị    - insignificant (abs(z)<=1) (vectorises)
         Ạ€  - all? for €ach
           Ṁ - maximum

®Œcç€®Ạ - Link 2: isBalanced? no-arguments (requires register to be populated - see Main)
®       - recall from register (the points as a list of complex numbers)
 Œc     - pairs
     ®  - recall from register (the points as a list of complex numbers)
   ç€   - call the last link (1) as a dyad for €ach pair
      Ạ - all truthy?

A½×Ṡ×1,ıSµ€©œc3ñ€®Ṁ¬¢, - Main link: list of (x, y) inputs
         µ€            - for €ach (x,y) pair, p:
A                      -   absolute value of p (vectorises)
 ½                     -   square root (vectorises)
   Ṡ                   -   sign of p (vectorises)
  ×                    -   multiply (vectorises)
     1,ı               -   literal [1, 0+1i]
    ×                  -   multiply (vectorises)
        S              -   sum
           ©           - (copy the result to the register)
            œc3        - combinations of length 3
                 ®     - recall from register
               ñ€      - call the next link (1) as a dyad for €ach triple
                  Ṁ    - maximum (1 if any triple has a centre)
                   ¬   - not (0 if any triple has a centre - hence isCentreFree?)
                    ¢  - call the last link as a nilad
                     , - pair with the calculated isCentreFree?
                       - implicit print


05AB1E, 7 bytes
Code:
.r².r)ø

Try it online
Following the input/output spec strictly (16 bytes):
.r².r)øvy`r?':?,

Explained:
.r                # radomize first input
  ².r             # randomize second input
     )ø           # merge the lists to an array of pairs cutting out extras
       vy`r?':?,  # format output

Try it online


Python 3, 208 188 187 184 180 177 171 bytes

lambda n:sum(all(i-j&1or(x<a<y)==(x<b<y)for(i,(a,b)),(j,(x,y))in d(enumerate(map(sorted,zip((0,)+p,p+(n,)))),2))for p in d(range(n)))
from itertools import*;d=permutations

Try it online!

Now 1-indexed (was previously 0-indexed but 1-indexing saved a byte due to a lucky quirk regarding the behavior of meanders).

Explanation

This may be the same as the link posted by Jenny_mathy, but I didn't end up reading the paper, so this is just the logic behind my method.

I will be using the following illustration provided on OEIS in order to visualize the results.

Each valid meander may be described entirely by the order of the intersection points it visits. This may be trivially observed in the image; the entry segment is always on the same side (otherwise the number would be double). We can represent the tendency of both the entry and exit segments to their respective infinities by simply adding to every order a point on either side - that is to say, the order (2, 1, 0) would become (-1, 2, 1, 0, 3).

With this in mind, the task is to find the number of orders, or permutations of the range up to n, which do not intersect with themselves. Intersections are only an issue between pairs of points for which the connecting segment lies on the same side. For any two pairs of consecutive points in a permutation whose segments share a side, whether or not they intersect is equivalent to whether one, and only one, of the points of one pair is between the two elements of the other pair. As such, we can determine if an order is valid by whether there are no pairs with one point contained by another pair with a segment on the same side.

Finally, having determined the validity of each permutations, the output of the function comes down to the number of permutations found to be valid.


Befunge, 871 836 798 bytes

&00p45*:10p20p030p240p050p060p9010gp9110gp1910gp1-91+10gpv
<v-g03+g06*2g041g055_v#!:%6:p06p05+p04g05g06:g04<p*54+292<
->10g:1\g3+:70p110gv >:5- #v_550g:01-\2*40g+1-30g
/\110:\-g03:\1:g055 _v#!-4:<vp01:-1g01-g03-1\-
^1<v07+1:g07< p08p < >:1-#v_550g:01-\40g+60g+1-30g-50g>v
 _0>p80gp:5-|v1\+66\:p\0\9:$<:p02:+1g02-g03+g06-\g04\1:<
0v|-g00:+1$$<>\p907^>p:!7v>3-#v_550g:30g+:30p1\0\-
1>10g+::0\g3-:70p\0^^07<v<>50#<g::30g+:30p-1-01-\
v >\$0gg> :1+10gg1- #v_^>0g10gg*+\:!2*-70g2+10gv>:#->#,"_"$#1_:1#<p
+1+g03$_^#`gg011+3:+3<g07\+*2+*`0:-\gg01+5g07:g<>1#,-#*:#8>#4_$#:^#
>55+,p30g40p10gg10g1>#v_
#v:#p0$#8_:$#<g!#@_0^ >
 >>:180gg`>>#|_:2+80gg:!v
3+^g\0p08:<vgg08+2::+3<$_100p1-v>g,\80gg+\80gp:2+90g:!01p\80gp
!#^_80g:1+^>\180gg`+!#^_20g80g`
5*g10!g09p04-1-\0\+g04:gg08:p09<^3`0:gg08+1:::$$_1#!-#\\:,#\<g

Try it online!

As is often the case with Befunge, the trick is coming up with an algorithm that allows us to render the pattern from top to bottom, since it's just not feasible to render it into memory first with the limited space available.

The way this works is by first building up a simple data structure representing the edges needed to draw the spiral. The second stage then parses that structure from top to bottom, rendering the edge fragments required for each line of output.

Using this technique, we can support up to n=15 in the reference implementation before we start having overflow issue in the 8-bit memory cells. Interpreters with a larger cell size should be able to support up to n=25 before running out of the memory.


JavaScript (Node.js), 40 bytes

Thanks to @Neil for saving 5 bytes on this version and 2 bytes on the BigInt version

Takes input as (t)(base), where \$t\$ is 1-indexed.

n=>g=(b,x=11)=>--n?g(b,+x.toString(b)):x

Try it online!

JavaScript (Node.js), 48 bytes (BigInt version)

Takes input as (t)(base), where \$t\$ is 1-indexed. Returns a BigInt.

n=>g=(b,x=11n)=>--n?g(b,BigInt(x.toString(b))):x

Try it online!


Jelly, 8 bytes

Z¬Þ€UZṚḌ

Try it online!

How it works

Z¬Þ€UZṚḌ  Main link. Argument: M (2D array / matrix)

Z         Zip; transpose M by reading columns as rows.
 ¬Þ€      Sort each row of the transpose by logical NOT, pushing 0's to the end.
    U     Upend; reverse all sorted rows of the transpose.
     Z    Zip again, restoring rows from columns. Overhangs rise to the top.
      Ṛ   Reverse the order of the rows.
       Ḍ  Decimal; convert the rows from base 10 to integer.