Regex (ECMAScript+(?*)), 1169 929 887 853 849 708 bytes
-141 bytes by using the second form of shortened division, where \$A^2 > C\$
Regex was never designed to do mathematics. It has no concept of arithmetic. However, when input is taken in the form of bijective unary, as a sequence of identical characters in which the length represents a natural number, it is possible to do a wide range of operations, building up from the simple primitives available, which basically amount to addition, comparison, multiplication by a constant, and modulo. Everything must fit inside the input; it isn't possible to directly operate on numbers larger than that.
In ECMAScript regex, it's especially difficult (and therefore interesting) to do even some of the simplest of operations, because of the limitation that all backrefs captured in a loop are reset to empty at the beginning of each iteration – which makes it impossible to count anything directly. It's nevertheless possible to match prime numbers, powers of N, Nth powers, arbitrary multiplication and exponentiation, Fibonacci numbers, factorial numbers, abundant numbers, and more, much of which is demonstrated in my other answers.
One of the operations that turns out to be far more verbose than the rest is to "calculate an irrational number". I initially discussed this with teukon back in 2014. The only known way to do this is to emulate operations on numbers larger than the input, and probably the simplest way to do this is by working in a number base chosen based on what can fit into the input.
It wasn't until late 2018 that I finally set about to implementing the theory I had sketched in 2014. Implementing it involved adapting the multiplication algorithm to work with factors of 0, which turned out to golf rather elegantly. (The underlying multiplication algorithm is explained in this post.) The basic algorithm is this:
For input \$N\$, we want to calculate \$M=\lfloor{N\over\sqrt2}\rfloor\$. So we want the largest \$M\$ such that \$2M^2\le N^2\$.
If we take the "number base" to be \$k=\lceil\sqrt N\rceil\$ or \$\lfloor\sqrt N\rfloor\!+\!1\$, all multiplication operations \$m\cdot n\$ on \$0\leq m,n<k\$ are guaranteed to fit in the available space.
So if \$N=A k+B\$, where \$0\leq A,B\lt k\$, we can calculate \$N^2\$:
$$N^2=(A k+B)^2=A^2 k^2+2 A B k+B^2$$
We must then do division, modulo, and carry to bring \$A^2\$, \$2 A B\$, and \$B^2\$ back into the range of a base \$k\$ "digit". A similar operation is then done to calculate \$2 M^2\$ iterated over the decreasing consecutive possible values of \$M\$, using digit-by-digit comparison to test for \$2M^2\le N^2\$, until the first \$M\$ is found that passes the test.
So while the basic concept is simple enough, it adds up to a lot of calculations, and the regex is huge! And this is probably the simplest calculation of an irrational number that can be done in ECMAScript regex. (It is still unknown whether it's possible to calculate a transcendental number to arbitrary precision in regex.)
This regex uses molecular lookahead, a.k.a. non-atomic lookahead, represented as (?*...). Without this feature, it would be much harder (or at least much more verbose) to implement.
A choice I made early on, to depart from pure code golf by going for mathematical aesthetics, turned out to be a very interesting. I chose to use \$k=\lceil\sqrt N\rceil\$ because it has the very neat property of making the calculations fit perfectly into \$N\$ if \$N\$ is a perfect square, whereas \$k=\lfloor\sqrt N\rfloor\!+\!1\$ is basically chaotic for all inputs. They both yield the same final outputs, but the former is just cleaner. A few golfs later, this choice ended up net increasing the total length of the regex by 8 bytes, so I figured it was worth it. (This change is in the git version history.) But another golf later that day, unbeknownst to me, was actually dependent on that decision! The skipping of a divisibility check in a division calculation makes \$N=25\$ return the incorrect output of \$M=11\$ instead of \$M=17\$ if \$k=\lfloor\sqrt N\rfloor\!+\!1\$, but works perfectly for all inputs if \$k=\lceil\sqrt N\rceil\$. So the actual net change in byte length was zero! It was a purely aesthetic decision for over two years.
At the time I did not understand why that division optimization worked, but this is now fully explained thanks to H.PWiz. The shortened form of division used at the beginning of the calculation of \$M^2\$ gives the correct quotient \$B\$ when \$A+2 < 4B\$, where \$C\$ is the dividend and \$A\$ is the divisor. Previously I believed that it was only guaranteed to work when \$A \le B\$. [This is no longer used, due to the number base switch.]
And now, with the discovery of a second shortened form of division that gives the correct quotient when \$A^2 > C\$, I found a major opportunity to use it in this regex! It only works when \$k=\lfloor\sqrt N\rfloor\!+\!1\$, so now I've switched back to that number base. It's saving 141 bytes! It's oddly convenient that this just happened to exist and works perfectly for this exact use.
(?=(x(x*)).*(?=\1*$)\2+$)(?=(x\1)+(x?(x*)))(?=\4(x(x*?))\1+$)(?=.*(?=(?=\4*$)\4\5+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\9))(?=.*(?=(?=\4*$)(?=\6*$)(?=\4\7+$)\6\5+$|$\4)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\13))(?=.*(?=\12\12\9$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\17))(?*.*?(?=((?=\3*(x?(x*)))\21(x(x*?))\1+$)))(?=.*(?=\23*$)(\23\24+$))(?=.*(?=(?=\21*$)\21\22+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\27))(?=.*(?=(?=\21*$)(?=\23*$)(?=\21\24+$)\23\22+$|$\21)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\31))(?=.*(?=\30\30\27$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\35))(?=.*(?=\26\26)(?=\3*(x*))(\1(x)|))(?=.*(?=\34\34\40)(?=\3*(x*))(\1(x)|))(?=(?=(.*)\13\13\17(?=\6*$)\6\7+$)\44(x+|(?=.*(?!\16)\41|(?!.*(?!\38)\8).*(?=\16$)\41$))(\25\31\31\35){2}\43$)\20|xx?\B|
Try it on repl.it
This regex is on GitHub with a full version history.
# Given an input number N in the domain ^x*$, this regex returns floor(N / sqrt(2))
(?=
    (x(x*))                    # \1 = will be the square root of the main number, rounded down; \2 = \1 - 1
    .*(?=\1*$)
    \2+$
)

# Step 1: Calculate N*N in base floor(sqrt(N))+1. Thanks to this choice of number base to work in, we'll be able to use the
# second shortened form of division in all places where the number base is the divisor, because it's guaranteed to give the
# correct quotient when the dividend is less than the squared divisor, and N itself is less than this. This form of division
# can be recognized by its lazy rather than greedy matching of the quotient, and only one divisibility test following that.

(?=(x\1)+(x?(x*)))             # \3 = \1+1 = floor(sqrt(N))+1, the number base to work in; \4 = N % \3; \5 = \4-1, or 0 if \4==0
(?=
    \4
    (x(x*?))                   # \6 = floor(N / \3); \7 = \6-1
    \1+$
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \4
        \4\5+$
    )
    (x*?)(?=\3*$)              # \8 =       (\4 * \4) % \3, the base-\3 digit in place 0 of the result for N*N
    (x?(x*?))                   # \9 = floor((\4 * \4) / \3); \10 = \9-1, or 0 if \9==0
    (
        \1+$
    |
        $\9                    # must make a special case for \9==0, because \1 is nonzero
    )
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \6; must do symmetric multiplication, because \4 is occasionally 1 larger than \6
        (?=\6*$)
        (?=\4\7+$)
           \6\5+$
    |
        $\4                    # must make a special case for \4==0, because \6 might not be 0
    )
    (x*?)(?=\3*$)              # \12 =       (\4 * \6) % \3
    (x?(x*?))                  # \13 = floor((\4 * \6) / \3); \14 = \13-1, or 0 if \13==0
    (
        \1+$
    |
        $\13                   # must make a special case for \13==0, because \1 is nonzero
    )
)
(?=
    .*(?=\12\12\9$)            # tail =       2 * \12 + \9
    (x*?)(?=\3*$)              # \16 =       (2 * \12 + \9) % \3, the base-\3 digit in place 1 of the result for N*N
    (x?(x*?))                  # \17 = floor((2 * \12 + \9) / \3); \18 = \17-1, or 0 if \17==0
    (
        \1+$
    |
        $\17                   # must make a special case for \17==0, because \1 is nonzero
    )
)                              # {\6*\6 + 2*\13 + \17} = the base-\3 digit in place 2 of the result for N*N, which is allowed to exceed \3 and will always do so;
                               # Note that it will be equal to N iff N is a perfect square, because of the choice of number base.

# Step 2: Find the largest M such that 2*M*M is not greater than N*N

# Step 2a: Calculate M*M in base \3
(?*
    .*?                        # Determine value of M with backtracking, starting with largest values first
    (?=
        (                      # \20 =       M
            (?=\3*(x?(x*)))\21 # \21 =       M % \3; \22 = \21-1, or 0 if \21==0
            (x(x*?))           # \23 = floor(M / \3); \24 = \23-1
            \1+$
        )
    )
)
(?=
    .*
    (?=\23*$)
    (\23\24+$)                 # \25 = \23 * \23
)
(?=
    .*
    (?=
        (?=\21*$)              # tail = \21 * \21
        \21\22+$
    )
    (x*?)(?=\3*$)              # \26 =       (\21 * \21) % \3, the base-\3 digit in place 0 of the result for M*M
    (x?(x*?))                  # \27 = floor((\21 * \21) / \3); \28 = \27-1, or 0 if \27==0
    (
        \1+$
    |
        $\27                   # must make a special case for \27==0, because \1 is nonzero
    )
)
(?=
    .*
    (?=
        (?=\21*$)              # tail = \21 * \23; must do symmetric multiplication, because \21 is occasionally 1 larger than \23
        (?=\23*$)
        (?=\21\24+$)
           \23\22+$
    |
        $\21                   # must make a special case for \21==0, because \23 might not be 0
    )
    (x*?)(?=\3*$)              # \30 =       (\21 * \23) % \3
    (x?(x*?))                  # \31 = floor((\21 * \23) / \3); \32 = \31-1, or 0 if \31==0
    (
        \1+$
    |
        $\31                   # must make a special case for \31==0, because \1 is nonzero
    )
)
(?=
    .*(?=\30\30\27$)           # tail =       2 * \30 + \27
    (x*?)(?=\3*$)              # \34 =       (2 * \30 + \27) % \3, the base-\3 digit in place 1 of the result for M*M
    (x?(x*?))                  # \35 = floor((2 * \30 + \27) / \3); \36 = \35-1, or 0 if \35==0
    (
        \1+$
    |
        $\35                   # must make a special case for \35==0, because \1 is nonzero
    )
)                              # {\25 + 2*\31 + \35} = the base-\3 digit in place 2 of the result for M*M, which is allowed to exceed \3 and will always do so

# Step 2b: Calculate 2*M*M in base \3
(?=
    .*
    (?=\26\26)                 # tail =       2*\26
    (?=\3*(x*))                # \38 =       (2*\26) % \3, the base-\3 digit in place 0 of the result for 2*M*M
    (\1(x)|)                   # \40 = floor((2*\26) / \3) == +1 carry if {2*\26} does not fit in a base \3 digit
)
(?=
    .*
    (?=\34\34\40)              # tail =       2*\34 + \40
    (?=\3*(x*))                # \41 =       (2*\34 + \40) % \3, the base-\3 digit in place 1 of the result for 2*M*M
    (\1(x)|)                   # \43 = floor((2*\34 + \40) / \3) == +1 carry if {2*\34 + \40} does not fit in a base \3 digit
)                              # 2*(\25 + 2*\31 + \35) + \43 = the base-\3 digit in place 2 of the result for 2*M*M, which is allowed to exceed \3 and will always do so

# Step 2c: Require that 2*M*M <= N*N

(?=
    (?=
        (.*)                   # \44
        \13\13\17
        (?=\6*$)               # tail = \6 * \6
        \6\7+$
    )
    \44                        # tail = {\6*\6 + 2*\13 + \17}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
    (
        x+
    |
        (?=
            .*(?!\16)\41       # \41 < \16
        |
            (?!.*(?!\38)\8)    # \38 <= \8
            .*(?=\16$)\41$     # \41 == \16
        )
    )
    (\25\31\31\35){2}\43$      # 2*(\25 + 2*\31 + \35) + \43
)

\20

|xx?\B|                        # handle inputs in the domain ^x{0,4}$

Regex (ECMAScript 2018), 861 720 bytes
This is a direct port of the 849 708 byte molecular lookahead version, using variable length lookbehind.
(?=(x(x*)).*(?=\1*$)\2+$)(?=(x\1)+(x?(x*)))(?=\4(x(x*?))\1+$)(?=.*(?=(?=\4*$)\4\5+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\9))(?=.*(?=(?=\4*$)(?=\6*$)(?=\4\7+$)\6\5+$|$\4)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\13))(?=.*(?=\12\12\9$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\17))(?=.*?(?=((?=\3*(x?(x*)))\21(x(x*?))\1+$))(?<=(?=(?=.*(?=\23*$)(\23\24+$))(?=.*(?=(?=\21*$)\21\22+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\27))(?=.*(?=(?=\21*$)(?=\23*$)(?=\21\24+$)\23\22+$|$\21)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\31))(?=.*(?=\30\30\27$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\35))(?=.*(?=\26\26)(?=\3*(x*))(\1(x)|))(?=.*(?=\34\34\40)(?=\3*(x*))(\1(x)|))(?=(?=(.*)\13\13\17(?=\6*$)\6\7+$)\44(x+|(?=.*(?!\16)\41|(?!.*(?!\38)\8).*(?=\16$)\41$))(\25\31\31\35){2}\43$))^.*))\20|xx?\B|
Try it online!
This regex is on GitHub.
# Given an input number N in the domain ^x*$, this regex returns floor(N / sqrt(2))
(?=
    (x(x*))                    # \1 = will be the square root of the main number, rounded down; \2 = \1 - 1
    .*(?=\1*$)
    \2+$
)

# Step 1: Calculate N*N in base floor(sqrt(N))+1. Thanks to this choice of number base to work in, we'll be able to use the
# second shortened form of division in all places where the number base is the divisor, because it's guaranteed to give the
# correct quotient when the dividend is less than the squared divisor, and N itself is less than this. This form of division
# can be recognized by its lazy rather than greedy matching of the quotient, and only one divisibility test following that.

(?=(x\1)+(x?(x*)))             # \3 = \1+1 = floor(sqrt(N))+1, the number base to work in; \4 = N % \3; \5 = \4-1, or 0 if \4==0
(?=
    \4
    (x(x*?))                   # \6 = floor(N / \3); \7 = \6-1
    \1+$
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \4
        \4\5+$
    )
    (x*?)(?=\3*$)              # \8 =       (\4 * \4) % \3, the base-\3 digit in place 0 of the result for N*N
    (x?(x*?))                  # \9 = floor((\4 * \4) / \3); \10 = \9-1, or 0 if \9==0
    (
        \1+$
    |
        $\9                    # must make a special case for \9==0, because \1 is nonzero
    )
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \6; must do symmetric multiplication, because \4 is occasionally 1 larger than \6
        (?=\6*$)
        (?=\4\7+$)
           \6\5+$
    |
        $\4                    # must make a special case for \4==0, because \6 might not be 0
    )
    (x*?)(?=\3*$)              # \12 =       (\4 * \6) % \3
    (x?(x*?))                  # \13 = floor((\4 * \6) / \3); \14 = \13-1, or 0 if \13==0
    (
        \1+$
    |
        $\13                   # must make a special case for \13==0, because \1 is nonzero
    )
)
(?=
    .*(?=\12\12\9$)            # tail =       2 * \12 + \9
    (x*?)(?=\3*$)              # \16 =       (2 * \12 + \9) % \3, the base-\3 digit in place 1 of the result for N*N
    (x?(x*?))                  # \17 = floor((2 * \12 + \9) / \3); \18 = \17-1, or 0 if \17==0
    (
        \1+$
    |
        $\17                   # must make a special case for \17==0, because \1 is nonzero
    )
)                              # {\6*\6 + 2*\13 + \17} = the base-\3 digit in place 2 of the result for N*N, which is allowed to exceed \3 and will always do so;
                               # Note that it will be equal to N iff N is a perfect square, because of the choice of number base.

# Step 2: Find the largest M such that 2*M*M is not greater than N*N

# Step 2a: Calculate M*M in base \3
(?=
    .*?                            # Determine value of M with backtracking, starting with largest values first
    (?=
        (                          # \20 =       M
            (?=\3*(x?(x*)))\21     # \21 =       M % \3; \22 = \21-1, or 0 if \21==0
            (x(x*?))               # \23 = floor(M / \3); \24 = \23-1
            \1+$
        )
    )
    (?<=
        (?=
            (?=
                .*
                (?=\23*$)
                (\23\24+$)                 # \25 = \23 * \23
            )
            (?=
                .*
                (?=
                    (?=\21*$)              # tail = \21 * \21
                    \21\22+$
                )
                (x*?)(?=\3*$)              # \26 =       (\21 * \21) % \3, the base-\3 digit in place 0 of the result for M*M
                (x?(x*?))                  # \27 = floor((\21 * \21) / \3); \28 = \27-1, or 0 if \27==0
                (
                    \1+$
                |
                    $\27                   # must make a special case for \27==0, because \1 is nonzero
                )
            )
            (?=
                .*
                (?=
                    (?=\21*$)              # tail = \21 * \23; must do symmetric multiplication, because \21 is occasionally 1 larger than \23
                    (?=\23*$)
                    (?=\21\24+$)
                       \23\22+$
                |
                    $\21                   # must make a special case for \21==0, because \23 might not be 0
                )
                (x*?)(?=\3*$)              # \30 =       (\21 * \23) % \3
                (x?(x*?))                  # \31 = floor((\21 * \23) / \3); \32 = \31-1, or 0 if \31==0
                (
                    \1+$
                |
                    $\31                   # must make a special case for \31==0, because \1 is nonzero
                )
            )
            (?=
                .*(?=\30\30\27$)           # tail =       2 * \30 + \27
                (x*?)(?=\3*$)              # \34 =       (2 * \30 + \27) % \3, the base-\3 digit in place 1 of the result for M*M
                (x?(x*?))                  # \35 = floor((2 * \30 + \27) / \3); \36 = \35-1, or 0 if \35==0
                (
                    \1+$
                |
                    $\35                   # must make a special case for \35==0, because \1 is nonzero
                )
            )                              # {\25 + 2*\31 + \35} = the base-\3 digit in place 2 of the result for M*M, which is allowed to exceed \3 and will always do so

            # Step 2b: Calculate 2*M*M in base \3
            (?=
                .*
                (?=\26\26)                 # tail =       2*\26
                (?=\3*(x*))                # \38 =       (2*\26) % \3, the base-\3 digit in place 0 of the result for 2*M*M
                (\1(x)|)                   # \40 = floor((2*\26) / \3) == +1 carry if {2*\26} does not fit in a base \3 digit
            )
            (?=
                .*
                (?=\34\34\40)              # tail =       2*\34 + \40
                (?=\3*(x*))                # \41 =       (2*\34 + \40) % \3, the base-\3 digit in place 1 of the result for 2*M*M
                (\1(x)|)                   # \43 = floor((2*\34 + \40) / \3) == +1 carry if {2*\34 + \40} does not fit in a base \3 digit
            )                              # 2*(\25 + 2*\31 + \35) + \43 = the base-\3 digit in place 2 of the result for 2*M*M, which is allowed to exceed \3 and will always do so

            # Step 2c: Require that 2*M*M <= N*N

            (?=
                (?=
                    (.*)                   # \44
                    \13\13\17
                    (?=\6*$)               # tail = \6 * \6
                    \6\7+$
                )
                \44                        # tail = {\6*\6 + 2*\13 + \17}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
                (
                    x+
                |
                    (?=
                        .*(?!\16)\41       # \41 < \16
                    |
                        (?!.*(?!\38)\8)    # \38 <= \8
                        .*(?=\16$)\41$     # \41 == \16
                    )
                )
                (\25\31\31\35){2}\43$      # 2*(\25 + 2*\31 + \35) + \43
            )
        )
        ^.*
    )
)
\20
|xx?\B|                        # handle inputs in the domain ^x{0,4}$

Regex (ECMAScript)
I have not yet ported this algorithm to basic ECMAScript. One way to do it would be to use \$k=\lceil\sqrt[\uproot{1}3]N\rceil\$ as the number base, and calculate:
$$N^2=(A k^2+B k+C)^2=A^2 k^4 + 2 A B k^3 + (2 A C + B^2)k^2 + 2 B C k + C^2$$
Another way would be to stick with \$k=\lceil\sqrt N\rceil\$, capture \$M\$ encoded into two or more backrefs, and emulate the existing calculations within the smaller available space. I'm not sure which way would be more concise. Either way, I expect the regex would roughly double in length.


Jelly, 2 bytes

_Ṣ

Try it online!

or Try all test cases

_   # Subtract from...
 Ṣ  # The input array sorted


Monday Mini-Golf #5: Don't DO try this at home

Pip, 138 140 bytes

Yeesh, that cannot/knot distinction is tricky.

x:"ca wo ai sha i'm you're"^sY"CAN0WILL0AM0SHALL0I AM0YOU ARE"^0OqR-`([\w']+)( no|n'|(?<=can)no)t\b`{++i"<s>".a."</s>".s.((yx@?LCb)|UCb)}s.i

Reads a line from stdin, outputs to stdout. The regex:

`([\w']+)( no|n'|(?<=can)no)t\b`

matches a word (including apostrophes) followed by one of three things:

 not
n't
not without a space, provided the first half of the word was can

The - operator on a regex makes it case-insensitive.

Matches are replaced with the result of the following function. (Note: within the function, a is the whole match and b is capture group 1.)

{++i"<s>".a."</s>".s.((yx@?LCb)|UCb)}
 ++i                                   Increment counter
    "<s>".a."</s>"                     Return entire match wrapped in HTML tags...
                  .s.(             )   plus space, plus the following:
                           LCb         Lowercase first capture group
                        x@?            Find its index in list x of special cases (nil if
                                         not in list)
                      (y      )        Use that as index into list y of replacements
                               |UCb    If it wasn't a special case, this is nil, and we
                                         instead use uppercase(b)

Once the modified string is done, we also output a space and the number of replacements i.


Python 2 + roman, 118 bytes

from roman import*
s=[]
for i in input().split():s+=[eval(s.pop(-2)+i+s.pop())if i in"+-/*"else`fromRoman(i)`]
print s

Demo
It cannot be tested online because of the module it makes use of, but you can see how  to run this here (a full program accepting input from STDIN – an expression with quotes – and printing the output to STDOUT – in the form of a list, the stack). Uses a slightly older version, because I won't bother to create a new GIF for only a few bytes:

To install the package, you can run the following in the Terminal / Command Line:
pip install roman


Smalltalk (Smalltalk/X), 29 27 chars
I am lucky - it is already in the String class:
'Today is a great day' rot:2
    -> 'Vqfca ku c itgcv fca'

adding I/O, this makes it:
(Stdin nextLine rot:2)print

in the spirit of doorknob's obfuscated example below, how about:
Parser evaluate:('(Uvfkp pgzvNkpg tqv:2)rtkpvPN' rot:-2)


Python 2, 338 337 335 331 325 bytes

x=y=s=0
for c in input():p='`1234567890-=`	qwertyuiop[]|`asdfghjkl;\'\n```zxcvbnm,./``````` ~!@#$%^&*()_+~~QWERTYUIOP{}\\~ASDFGHJKL:"\n~~~ZXCVBNM<>?~~~~~~~ '.find(c);S=[p>61,s][c in' \n'];p%=62;Y=p/14;X=[max(x,12),min(max(x,5),10),p%14]['\n '.find(c)];print'sS'[S]*(s^S)+'LR'[X>x]*abs(X-x)+'UD'[Y>y]*abs(Y-y)+'Pp';x,y,s=X,Y,S

Try it online!

Moves directly from each character to the next.

Explanation:

S=[c in K,s][c in' \n'], checks if the next character should be Upper- or lowercase. If c is a space or newline, the case remains the same.
X=[max(x,12),min(max(x,5),10),p%15]['\n '.find(c)]. If c is a space or newline, the closest x-coordinate to the current is chosen(as the keys span multiple columns)
print'sS'[S]*(s!=S)+'LR'[X>x]*abs(X-x)+'UD'[Y>y]*abs(Y-y)+'Pp', prints the case switch, the number of x-coordinate moves, the number of y-coordinate moves, and finally Pp, for each character

Shorter version, if the shortest path is not required:

Python 2, 294 293 291 287 281 bytes

x=y=s=0
for c in input():p='`1234567890-=`	qwertyuiop[]|`asdfghjkl;\'\n```zxcvbnm,./``````` ~!@#$%^&*()_+~~QWERTYUIOP{}\\~ASDFGHJKL:"\n~~~ZXCVBNM<>?~~~~~~~ '.find(c);S=[p>61,s][c in' \n'];p%=62;X,Y=p%14,p/14;print'sS'[S]*(s^S)+'LR'[X>x]*abs(X-x)+'UD'[Y>y]*abs(Y-y)+'Pp';x,y,s=X,Y,S

Try it online!


Python 2, 110 105 104 103 100 97 96 bytes

Saved five bytes thanks to Mr. Xcoder; removed unnecessary assignment, moved negation into available whitespace.
Saved a byte thanks to Mr. Xcoder; golfed [~-x:x+~-t] to [~-x:][:t].
Saved a byte; golfed ...range(1,-~b)))[:b] to ...range(b)))[1:-~b].
Saved three bytes; golfed [1:-~b][~-x:] to [:-~b][x:].
Saved three bytes; golfed [:-~b][x:] to [x:-~b].
Saved a byte thanks to Lynn; golfing the while loop to an exec statement.

b,t,x=input();S=x;exec"x+=sum(set(map(int,''.join(map(str,range(b)))[x:-~b][:t])));"*b;print-S+x

Try it online!


Definite integral of polynomial functions

Jelly, \$\frac {30} 7 = 4.29\$
÷J$ŻUḅI

Try it online!
Takes the polynomial as a list of coefficients in little-endian format (i.e. the example is 7,2,5,4). This can handle any (positive) degree you want, but I've limited it at 30 as the question states \$0 < N < 30\$
+2 bytes and a score of \$3.33\$ if the polynomial must be taken in big-endian format
How it works
÷J$ŻUḅI - Main link. Takes coeffs on the left and [a, b] on the right
  $     - To the coeffs:
 J      -   Yield [1, 2, 3, ..., N]
÷       -   Divide each coeff by the orders
   Ż    - Prepend 0
    U   - Reverse
     ḅ  - Calculate as polynomials, with x = a and x = b
      I - Reduce by subtraction


GolfScript, 24 23 21 20 18 chars

~{(}{3*).2%6\?/}/,

Assumes input on stdin. Online test


Golfscript - 26 chars

~:x,{:b;x,{b?x=b*}%+}*$-1>

Rough translation to Python

x=input()
acc = []
for b in range(x):
    for _ in range(x):
        acc.append((_**b==x)*b) # most of these are zeros
print max(acc)

So it loops way more times that necessary, but that often happens with golfed answers


Given a sequence of numbers, print out all possible sets such that the sum is less than a number


Generate list of numbers and their negative counterparts

Python 2, 33 bytes

def f(a,b):print-a,a;a<b<f(a+1,b)

Try it online!

A recursive function that prints in a two-column format. Based on ideas from Surculose Sputum.

In Python 3, we'd need 2 more bytes for print() needing parens.

Python 2, 37 bytes

lambda a,b:range(a,b+1)+range(-b,1-a)

Try it online!

Unfortunately for this challenge, Python's ranges are exclusive, so we have to add 1 to both upper endpoints.


Ruby, 204 191 172 characters

c,*r=gets.split
o=[0]*8
s=->x,y,p{y>14?o[x]+=p :(r.index("#{x},#{y+=1}")?(x<1?s[x+1,y,p]:(x>6?s[x-1,y,p]:(s[x-1,y,p*0.55]+s[x+1,y,p*0.45]))):s[x,y,p])}
s[4,0,1]
p o[c.to_i]

It recursively simulates all possibly outcomes while keeping track of each individual outcome's probability, then it adds that probability to a cumulative counter when y == 15.

Fancy tricks:

c,*r=gets.split - the "splat" operator (*) takes all the remaining elements of gets.split and sticks them in the r array
next {something} if {condition}: essentially equivalent to

if {condition}
    {something}
    return
end

"Discovered" by evolving from if condition; something; return; end to return something if condition to break something if condition, and then I figured I would try a shorter "loop operator" to see if it would work (which it did, of course).
Thanks to @MartinBüttner for suggesting to use chained ternary operators (which ended up becoming the enormous third line in the golfed code above) and eliminating the above point (which saved 19 (!) characters).

I did use a somewhat fancy trick with those, though: I realized that s[foo],s[bar] doesn't work in Ruby for two method calls in one statement. So at first I changed it to (_=s[foo],s[bar]) (a dummy variable), but then I realized I could just add and throw away the return values: s[foo]+s[bar]. This only works because calls to s will only ever "return" other calls to s or a number (o[x]+=p), so I don't have to worry about checking for nil.
Other various optimizations: p instead of puts for printing numbers, <1 instead of ==0 (since the canoe never leaves the river) and similar comparisons elsewhere, [0]*8 for initial probabilities as Ruby's numbers are always "pass by value"

Ungolfed:

column, *rocks = gets.chomp.split
outcomes = Array.new(8, 0)
simulate = -> x, y, probability {
    if y == 15
        outcomes[x] += probability
    elsif rocks.index("#{x},#{y + 1}")
        case x
        when 0 then simulate[x + 1, y + 1, probability]
        when 7 then simulate[x - 1, y + 1, probability]
        else
            simulate[x - 1, y + 1, probability * 0.55]
            simulate[x + 1, y + 1, probability * 0.45]
        end
    else
        simulate[x, y + 1, probability]
    end
}
simulate[4, 0, 1.0]
p outcomes
puts outcomes[column.to_i]


Freely available books for code golfing?

There are at least two books about golfing:

"Short Coding" by Ozy (only available in Japanese I think, search for it on www.amazon.co.jp)
The Perlgolf History book, available here.

Other recommended reading:

Andrew Savige's (eyepopslikeamosquito) articles on golf, accessible from his node on perlmonks
The language specific forums over on codegolf.com
The solutions to finished challenges on golf.shinh.org (look for "post-mortem").


Ruby

I tried to match the actual syntax of Ruby's regex flavor as much as possible, but there are a few quirks: it accepts a few lookbehinds that are actually invalid (like (?<=(?<!))), and it recognizes empty character ranges like D-A. The latter could be fixed for ASCII, but the regex is long enough as it is.

\A(?<main>
    (?!
        \{(\d+)?,(\d+)?\} # do not match lone counted repetition
    )
    (?:
        [^()\[\]\\*+?|<'] | # anything but metacharacters
        (?<cclass>
            \[ \^? (?: # character class
                (?: # character class
                    [^\[\]\\-] | # anything but square brackets,  backslashes or dashes
                    \g<esc> |
                    \[ : \^? (?: # POSIX char-class
                        alnum | alpha | word | blank | cntrl | x?digit | graph | lower | print | punct | space | upper
                    ) : \] |
                    - (?!
                        \\[dwhsDWHS]
                    ) # range / dash not succeeded by a character class
                )+ |
                \g<cclass> # more than one bracket as delimiter
            ) \]
        ) |
        (?<esc>
            \\[^cuxkg] | # any escaped character
            \\x \h\h? | # hex escape
            \\u \h{4} | # Unicode escape
            \\c . # control escape
        ) |
        \\[kg] (?:
            < \w[^>]* (?: > | \Z) |
            ' \w[^']* (?: ' | \Z)
        )? | # named backrefs
        (?<! (?<! \\) \\[kg]) [<'] | # don't match < or ' if preceded by \k or \g
        \| (?! \g<rep> ) | # alternation
        \( (?: # group
            (?:
                \?
                (?:
                    [>:=!] | # atomic / non-capturing / lookahead
                    (?<namedg>
                        < [_a-zA-Z][^>]* > |
                        ' [_a-zA-Z][^']* ' # named group
                    ) |
                    [xmi-]+: # regex options
                )
            )?
            \g<main>*
        ) \) |
        \(\?<[!=] (?<lbpat>
            (?! \{(\d+)?,(\d+)?\} )
            [^()\[\]\\*+?] |
            \g<esc>  (?<! \\[zZ]) |
            \g<cclass> |
            \( (?: # group
                (?:
                    \?: |
                    \? \g<namedg> |
                    \? <[!=]
                )?
                \g<lbpat>*
            ) \) |
            \(\?\# [^)]* \)
        )* \)
        |
        \(\? [xmi-]+ \) # option group
        (?! \g<rep> )
        |
        \(\?\# [^)]*+ \) # comment
        (?! \g<rep> )
    )+
    (?<rep>
        (?:
            [*+?] | # repetition
            \{(\d+)?,(\d+)?\} # counted repetition
        )
        [+?]? # with a possessive/lazy modifier
    )?
)*\Z

Unreadable version:

\A(?<main>(?!\{(\d+)?,(\d+)?\})(?:[^()\[\]\\*+?|<']|(?<cclass>\[\^?(?:(?:[^\[\]\\-]|\g<esc>|\[:\^?(?:alnum|alpha|word|blank|cntrl|x?digit|graph|lower|print|punct|space|upper):\]|-(?!\\[dwhsDWHS]))+|\g<cclass>)\])|(?<esc>\\[^cuxkg]|\\x\h\h?|\\u\h{4}|\\c.)|\\[kg](?:<\w[^>]*(?:>|\Z)|'\w[^']*(?:'|\Z))?|(?<!(?<!\\)\\[kg])[<']|\|(?!\g<rep>)|\((?:(?:\?(?:[>:=!]|(?<namedg><[_a-zA-Z][^>]*>|'[_a-zA-Z][^']*')|[xmi-]+:))?\g<main>*)\)|\(\?<[!=](?<lbpat>(?!\{(\d+)?,(\d+)?\})[^()\[\]\\*+?]|\g<esc>(?<!\\[zZ])|\g<cclass>|\((?:(?:\?:|\?\g<namedg>|\?<[!=])?\g<lbpat>*)\)|\(\?#[^)]*\))*\)|\(\?[xmi-]+\)(?!\g<rep>)|\(\?#[^)]*+\)(?!\g<rep>))+(?<rep>(?:[*+?]|\{(\d+)?,(\d+)?\})[+?]?)?)*\Z


Pixel-art, episode 1: display Super Mario

HTML/JS, 206 158 153 102

102

Trick used: save the compressed GIF file as an HTML file, and add  at the end

Thanks to this entry: https://codegolf.stackexchange.com/a/39926/10732 by @NiettheDarkAbsol

GIF87a  ¡ kŒÿã%jk±4%,       6„‡héj„Af-ÕdÎy\%    …R˜0”ŒÈJ³I©±²û“ú=ª$±p%i¸•¤

Demo: http://meuziere.free.fr/mario/gif.html

Older versions:

153

Trick used: save the compressed PNG file as an HTML file, and add  at the end

‰PNG

IHDR         _v”   PLTEjkkŒÿ±4%ã%ó’V   IIDAT×c[Êµj%C€ÍUŸ?|ìíœÿ02„ÿÿÊÐÊàÐÄÈÀ°ŠáÓë~†«ö3üZµž!jÚR‡P x( s6ïåÇ

158

Trick used: setting the trimmed dataURI of a compressed PNG as the SRC of an IMG tag and packing the whole thing in Unicode chars.

Execute that in your JS console:

document.write(unescape(escape('').replace(/uD./g,'')))

206

Unpacked (206b):

Demo

Tools used:

https://tinypng.com/
http://xem.github.io/miniURI/input.html
http://xem.github.io/obfuscatweet/


JavaScript (ES6), 40 bytes
All used characters appear exactly twice. Therefore, this returns either 0 or 2/40 = 0.05.

F=_=>(F+'+./02>cdeilnsu').includes(_)/20

Try it online!


Matlab, 140 136 128 124 bytes
Basically first starts with the middle section, and then prepends/appends the shortened/modified versions step by step.
a=input('');v=ones(nnz(a)*2-1,1)*a;v(2:2:end,:)=0;b=v;for k=a;v=v(2:end,1:end-1);v(end+1,:)=0;b=[v,b,v,''];end;b(~flip(b))=0

Thanks for 8 bytes @LuisMendo!
E.g. for MATLAB we get:
               MATLAB
          MATLA      MATLA
      MATL     MATLAB     MATL
   MAT    MATLA      MATLA    MAT
 MA   MATL     MATLAB     MATL   MA
M  MAT    MATLA      MATLA    MAT  M
 MA   MATL     MATLAB     MATL   MA
   MAT    MATLA      MATLA    MAT
      MATL     MATLAB     MATL
          MATLA      MATLA
               MATLAB


For SQL dialects that support recursive CTEs like sqlite, you can do something like the following:

WITH RECURSIVE f(x) AS
(
  SELECT 1 UNION ALL SELECT x + 1 FROM f LIMIT 1000000
)
SELECT x
FROM f;

This doesn't depend on any existing table and you can change the LIMIT clause as desired. I originally saw a variant of this on StackOverflow.


Javascript, 466 bytes

s=>(s=s.split(/\.[a-z\d]{1,6}$/i)[j=d=0],h=s[l='length']/2|0,m=[],g=r=>(++j,m=m.concat((s[n='match'](r)||[]).map(x=>[x,j]))),p='replace',g(/\d{9,}/g),g(/[\da-f]{16,}/ig),g(/[\da-z%+=]{12,}/ig),m.sort((x,y)=>y[0][l]-x[0][l]).every(x=>x[1]-1?x[1]-2?s=s[p](x[0],y=>y[n](/[a-z]/)&&y[n](/\d/)&&(y+'A')[n](/[A-Z]/g)[l]>y[l]/3|0?(d+=y[l],''):y):s=s[p](x[0],y=>!!y[n](/[A-F]/)^!!y[n](/[a-f]/)&&(y+'0')[n](/\d/g)[l]>y[l]/3|0?(d+=y[l],''):y):(s=s[p](z=x[0],''),d+=z[l])),d<=h)

Explaining:

f=s=>(                                 // f: take string s (filename) as input
    s=s.split(/\.[a-z\d]{1,6}$/i)[j=d=0],  // s: input without extension
                                           // d: combined rules' sum
                                           // j: combined rule-number step
    h=s[l='length']/2|0,                   // h: half string
                                           // l: length
    m=[],                                  // m: matches
    g=r=>(++j,                             // j: next combined rule number
        m=m.concat(                            // m: join
            (s[n='match'](r)||[]).map(             // new (r)egex-matches
            x=>[x,j])                              // mapped with its rule number
    )),p='replace',                        // p: replace
    g(/\d{9,}/g),                          // combined rules §1
    g(/[\da-f]{16,}/ig),                   // combined rules §2
    g(/[\da-z%+=]{12,}/ig),                // combined rules $3
    m.sort((x,y)=>y[0][l]-x[0][l])         // matches ordered by length
        .every(x=>x[1]-1?                      // for combined rule §1
            x[1]-2?                                // for combined rule §2
                s=s[p](x[0],y=>                        // for combined rule §3
                    y[n](/[a-z]/)&&y[n](/\d/)&&            // if lower and digit and
                    (y+'A')[n](/[A-Z]/g)[l]>y[l]/3|0?      // upper at least `total/3`
                (d+=y[l],''):y)                        // replace by empty and sum up `d`
            :s=s[p](x[0],y=>                       // replace if
                !!y[n](/[A-F]/)^!!y[n](/[a-f]/)&&      // (upper xor lower case) and
                (y+'0')[n](/\d/g)[l]>y[l]/3|0?         // digits: at least `total/3`
            (d+=y[l],''):y)                        // by empty and sum up `d`
        :(s=s[p](z=x[0],''),d+=z[l]))          // no treatment
    ,d<=h                                  // output if "no more than half of string"
);

["results_for__michael_greer.txt.zip",
"Georg Feuerstein - Connecting the Dots.pdf",
"M People - Search for the Hero-ntuqTuc6HxM.mp4",
"index.html?v=QTR4WGVTUzFsV3d8NHxvcmlnaW5hbHx8MTExMTAxBHxodHRwOi8vLCwsLHRyLDcsMA%3D%3D.html",
"ol2DCE0SIyQC(173).pdf",
"d41d8cd98f00b204e9800998ecf8427e.md5",
"12792331_807918856008495_7076645197310150318_o.jpg"]
.forEach(x=>document.body.innerHTML+='<pre>"'+x+'" => '+f(x)+'</pre>')


Java

Almost all of the current solutions assume that local/remote computer is not lying about a current time (would you believe T-600 as well?) .
Key point in time calculation is trusting a pure nature. This Android app asks user to take photo of the sky and it's predicting current time with outstanding precision:

public void onActivityResult(int requestCode, int resultCode, Intent data)
{
   if (resultCode == RESULT_OK)
   {
      Uri selectedImageUri = data.getData();
      this.imageView.setImageURI(selectedImageUri);

      TimeGuesser guesser = new TimeGuesser(this);
      String result = guesser.guessTimeFromImage(selectedImageUri);
      this.textView.setText(result);
   }
}

public class TimeGuesser {

    private Context context;
    public TimeGuesser(Context context)
    {
        super();
        this.context = context;
    }

    public String guessTimeFromImage(Uri uri) {
        Bitmap bitmap = null;
        try {
            bitmap = MediaStore.Images.Media.getBitmap(this.context.getContentResolver(), uri);
        } catch (IOException e) {
            return "There is no sky. Everyone's going to die";
        }

        float brightness = getBrightness(bitmap);

        if (brightness < 90.0)
        {
            return "It's sooo late";
        } else {
            return "It's sooo early";
        }
    }

    private float getBrightness(Bitmap bitmap)
    {
        float R, G, B;
        R = G = B = 0.0f;
        int pixelColor;
        int width = bitmap.getWidth();
        int height = bitmap.getHeight();
        int size = width * height;

        for (int x = 0; x < width; ++x) {
            for (int y = 0; y < height; ++y) {
                pixelColor = bitmap.getPixel(x, y);
                R += Color.red(pixelColor);
                G += Color.green(pixelColor);
                B += Color.blue(pixelColor);
            }
        }

        R /= size;
        G /= size;
        B /= size;

        float brightness =  (0.2126f*R ) + (0.7152f*G) + (0.0722f*B);
        return brightness;
    }
}

Results:


Find the number of ways to climb a stairway

JavaScript (ES6), 71 bytes
Expects (list)(n).

(a,t=0)=>g=n=>n>0?a.map(x=>--g[(g[x]=-~g[x])+~x|x<2&&g(n-x),x])|t:t+=!n

Try it online!
Commented
(a, t = 0) =>           // a[] = input list, t = output
g = n =>                // g is a recursive function taking the number of steps n
  n > 0 ?               // if n is positive:
    a.map(x =>          //   for each value x in a[]:
      --g[              //     decrement g[x] afterwards
        (g[x] = -~g[x]) //       increment g[x]
        + ~x |          //       if g[x] is not equal to x + 1
        x < 2 &&        //       or x = 1:
          g(n - x),     //         do a recursive call with n - x
        x               //       actual index to update g[x]
      ]                 //     end of entry update: this is guaranteed to be 0 on
                        //     the first iteration; therefore, .map() is coerced to
                        //     0 by the the bitwise OR even if a[] is a singleton
    ) | t               //   end of map(); yield t
  :                     // else:
    t += !n             //   increment t if n = 0


Make an ASCII bat fly around an ASCII moon

05AB1E, 69 62 60 bytes

Saved 2 bytes thanks to Adnan.

3ð×…^o^)U13FNV0379730vð5y>;ï-y_+×N(Y-12%_Xè'my×NY-12%_y&XèJ,

Try it online!

Explanation

3ð×…^o^)U stores the list ["   ","^o^"] in X for later use.

13FNV loops over the 13 stages [0 .. 12] and stores the current iteration index in Y.

0379730v loops over the rows of each stage,
where N is the row index and y is the current number of m's.

We start by adding floor(5/(y+1))-(y==0) spaces to each row with ð5y>;ï-y_+×.

We then determine if there should be a bat or 3 spaces before the m's.
If (-N-Y)%12 == 0 is true we add a bat, else 3 spaces.
This expression (N(Y-12%_Xè) will place bats in stages 0,6-12.

Then we place y m's with 'my×.

Now we determine if there should be a bat or 3 spaces after the m's.
The code NY-12%_y&Xè will place a bat if ((N-Y)%12 == 0) and y!=0 is true, else 3 spaces.
This will place the bats on stages 1-5.

Finally we join the whole row into a string and print with a newline: J,.


Help me procrastinate on my computer repairs!

JavaScript 287 (187+20*5) 295 (195 +20*5) 338 (198 + 20*7)

A function that check every possible combinations of the 6 allowed hex digits (0xA to 0xF) and the 3 allowed operators.
Output via popup and not returning a value, as requested.

I used [] to group comma separated expression but could not avoid 5 7 open brackets for loops and function calling.
To avoid digits there are variables A,B,C for 1,2,3 (this makes the code even more obscure)

Edit code revised focusing on avoiding '('. Removed ifs and explicit RegExp creation

Beware: this function is incredibly slow, it will exceed the time limit for a script in FireFox, even for small input like 90.

To enumerate all the possible expression, I use number starting at 3 and going up forever.  Digits encoding:
  0,1,2 are the operators +,-,/
  4 to 9 are the hex digits A..F
  3 is not allowed
Each number is checked with a regexp /3|[0-2]{2}/ to avoid the digit 3 and having 2 consecutive operators (the check also avoid traling and leading operators - see code)

The resulting string is something like 0xA + 0xA - 0xD that is valid javascript, so I use eval to evaluate it. Unfortunatley the '/' operator is floating point and not integer in JavaScript, so I'm not 100% sure that the result are correct event casting to integer the final result (but I am quite confident, given that a small rounding error can not be amplified by a '*')

F=x=>{
  for(A=-~0,B=A+A,i=C=A+B,j=0;j?x-~~eval(L):A;)
  {
    j=++i+'0',k=0+j;
    for(c of~k.search(C+'|[0-'+B+']{'+B+'}',L='',w='0x')?j='':j)
      c>C?w+=' ABCDEF'[c-C]:[L+=w,w=' '+'+-/'[c]+' 0x']
  }
  alert(L)
}

Something else

Now, something funnier. I used an oversimplified expressione parser to avoid the eval call and, amusingly, that turned out to be a lot faster.

The parser is really simplified, in a real parser V and O should be arrays containing the pending values stack and the pending operators stack. Here V is the single pending value (and also the return value) and O is a string with at most 2 characters. P contains the operators precedence table, for '-+/' => '112'

This scores 275 + 4*20 => 355

F=x=>{
  for(A=-~0,B=A+A,i=C=A+B,D=A+C,j=0,P=''+A+A+B;j?x-V:A;)
  {
    j=++i+'0',k=0+j;
    for(c of~k.search(C+'|[0-'+B+']{'+B+'}',v=V=O=L='',w='0x')?j='':j)
      c>C?
        w+='ABCDEF'[v<<=D,v+=D+A-~c,c-D]
      :[
          P[O[0]]>=P[c]?[v=O>A?V/v|0:O>0?V+v:V-v,O=c]:O=c+O,
          L+=w,w=' '+'-+/'[c]+' 0x',V=v,v=0
      ]
  }
  alert(L)
}

Test In Firefox/FireBug console, change alert with return (a lot more usable)

;[0, 1, 15, 255, 30].forEach(x=>console.log(x,F(x)))

  0 0xA - 0xA
  1 0xA / 0xA
  15 0xF
  255 0xFF
  30 0xF + 0xF

Just a little less obvious (but be patient)

;[16,40, 51, 62, 73, 84, 95].forEach(x=>console.log(x,F(x)))

  16 0xBA / 0xB
  40 0xA + 0xF + 0xF
  51 0xDD - 0xAA
  62 0xEA - 0xAC
  73 0xA + 0xEA - 0xAB
  84 0xFE - 0xAA
  95 0xA + 0xFF - 0xAA


convey, 34 bytes
}
/1:`%""{
^1"v4!<
+"+v}+1
^<","-}

Try it online!

Pushes n and n+1 to the right per loop.

For each value outputs i and i-pages+1.

Whenever the left loop passes through the top part, output a newline /}.
Allow n to pass the loop only pages % 4 times.


Python 3, 89 bytes

a='a=%r;b=%r;p=\\';b='print;p(a%(a,b));';p=\
print;p(a%(a,b));c='c=%r;p(b+c%%c)';p(b+c%c)

Try it online
The Levenshtein distance is 38, which is 86.36% of 44.
Explanation:
This is similar to the standard quine s='s=%r;print s%%s';print s%s. I had to try a lot of combinations and modifications in order to find my program. Creating the function p was used to make the second line shorter. The \ on the end of the first line is a line-continuation character.
a
a='a=%r;b=%r;p=\\'

A string template that results in the first line

b
b='print;p(a%(a,b));'

String that represents the first part of the 2nd line

p
p=\
print

Shorten stuff, change lengths

line 1
p(a%(a,b))

Print the first line

c
c='c=%r;p(b+c%%c)'

String representing itself plus the part after that prints b

line 2
p(b+c%c)

Outputs the second line


Pyth, 17 bytes
 Z.{rzZ.q.Zzr}.Z

Try it online here.
The leading space is necessary. I have counted it and the trailing space in the byte count.
Here's the breakdown:
     z            z is initialized to the input
    r Z           Z is initialized to 0, and r(string)0 converts the string to lowercase
  .{              .{ is pyth's builtin uniqueness test
       .q         .q terminates the program
         .Zzr}    This is just the program mirrored
              .Z  . requires a number to immediately follow it
                  If left blank the parser would throw an error
 Z                This is just mirrored from the end
                  The leading space suppresses the automatic printing of this 0
                  The trailing space mirrors the leading space


Python 3, 154 bytes (list of chars -> list of chars) (function) Cracked

[=o;]1-::[]:s[i,]1-::[]s:[i=R,L;2//)i(nel=s
:)i(r fed
*tropmi modR+L+o nruter
]:s[L,R=R,L;]s:[L=+o;))L(nel,1(tnidnar=s:R dna L elihw
]nar morf

I doubt this will be too hard to crack, especially since riffling once is rather ineffective (you can see entire program components in the output...). This is mostly just to get things rolling. There might be some whitespace (including newlines) that I didn't copy correctly. The SHA-384 hash of my  intended solution is
5924530418bf8cd603c25da04ea308b124fdddfc61e7060d78b35e50ead69a7fbde9200b5ee16635cc0ee9df9c954fa1.


CJam, 111 89 88 86 84 83 bytes

la9*~"{}qwertyuiop ;':asdfghjkl ,./<>?zxcvbnm"{_32^}%_'ÿ,^a\S%+{[f&s\e|__|]:,}$0=&

Try it online in the CJam interpreter.

How it works

la9*~     e# Push the input 9 times on the stack.

"{}qwertyuiop ;':<STX>asdfghjkl ,./<>?zxcvbnm"

{_32^}%   e# XOR a copy of each character with 32.
_'<DEL>,^ e# Push a string of all ASCII characters that are missing.
a\        e# Wrap it in an array.
S%+       e# Split the string at spaces and concatenate with the array.
{         e# Sort the chunks according to the following:
  [       e#
    f&s   e# Push the string of characters from the input that are in this chunk.
    \e|   e# If the result is empty, replace it with the input.
    __|   e# Push a copy with duplicates removed.
  ]       e# Collect both strings in an array.
  :,      e# Replace each string with its length.
}$        e#
0=        e# Retrieve the minimum.
&         e# Intersect it with the input.


MarioLANG, 23 bytes cracked

   >+
 :<":
>+^!<
===#=

Try it online!

produces the odd numbers A005408


Builtin
Husk:
…

Try it online!
I bet this builtin exists in more than one language, so I made this a community wiki, just add in more languages where this is a builtin if you know them!


JavaScript (ES6),  158 ... 145  144 bytes
Takes input as (a,b,c,n), with \$a\$, \$b\$ and \$c\$ 0-indexed.

(a,b,c,n)=>(g=x=>[(d=[...x+''],i+=C=![d[0]-x%10,d+''>d.sort(),/1/.test(x)][c])>n,x>=n,x>n&C][a]?a-1?x:C&x==n:g([y,x+y,x+3][b],y+=b||x))(i=0,y=1)

Try it online!
Commented
(a, b, c, n) => (              // given the challenge parameters ...
  g = x =>                     // g is a recursive function taking the current value x
    [                          // this is the array for A
      (                        //   a = 0:
        d = [...x + ''],       //     d[] = array of digits in x
        i += C =               //     increment i if C is true
          ![                   //     set C if the condition is false:
            d[0] - x % 10,     //       c = 0: the 1st and the last digits are not equal
            d + '' > d.sort(), //       c = 1: the digits are not in sorted order
            /1/.test(x)        //       c = 2: there's a '1' in x
          ][c]                 //     pick the relevant condition for C
      ) > n,                   //     exit if i is greater than n
      x >= n,                  //   a = 1: exit if x is greater than or equal to n
      x > n & C                //   a = 2: exit if x is greater than n and C is true
    ][a]                       // pick the relevant condition for A
    ?                          // if we're done:
      a - 1 ? x                //   if a is not equal to 1, return x
            : C & x == n       //   otherwise, test whether C is true and x is equal to n
    :                          // else:
      g(                       //   do a recursive call:
        [                      //     update x:
          y,                   //       b = 0: x = y (Fibonacci)
          x + y,               //       b = 1: x += y (triangular numbers)
          x + 3                //       b = 2: x += 3 (multiples of 3)
        ][b],                  //     pick the relevant update for B
        y += b || x            //     if b = 0, add x to y (for Fibonacci)
                               //     otherwise, add b to y (we actually just need to
                               //     add 1 for triangular numbers; for multiples of 3,
                               //     y is ignored anyway)
      )                        //   end of recursive call
)(i = 0, y = 1)                // initial call to g with x = i = 0 and y = 1


GNU sed + bc, 4336 5074.5 points, 64 75 %

Update: the OP gave a new way to calculate the score of the prediction for an individual test case. Using Wolfram Alpha, I plotted both sets of formulas to see the differences.

The current way brings a strong incentive to output actual probabilities, and not just the extremes, 0 and 1, for which the new formulas give the same maximum score as before. This is why the unchanged algorithm below, has now a better prediction rate, in fact a great rate given its simplicity.

However, there's also a drawback associated with the new formulas, as explained in 'Edit 1'.

This is a simple estimation based only on the material advantage / disadvantage, ignoring the actual placement of the pieces. I was curious how this will perform. The reason I use sed, and not some language that can do this in one line, is because it is my favorite esoteric language.

/:/d                                             # delete the two headers
s:.*,::                                          # delete board positions
s:$:;Q9,R5,B3,N3,P1,K0,q-9,r-5,b-3,n-3,p-1,k-0:  # add relative piece value table
:r                                               # begin replacement loop
s:([a-Z])((.*)\1([^,]+)):\4+\2:                  # table lookup: letter-value repl.
tr                                               # repeat till last piece
s:;.*::                                          # delete value table
s:.*:echo '&0'|bc:e                              # get material difference: bc call
/^0$/c0.5                                        # print potential draw score
/-/c0                                            # print potential black win score
c1                                               # print potential white win score

Standard piece values used:

9 - Queen
5 - Rook
3 - Knight
3 - Bishop
1 - Pawn
0 - King

I calculate the material for both sides and subtract black's material from that of white. The output for each test case is based on that difference as follows:

if difference > 0, then output = 1 (potential white win)
if difference = 0, then output = 0.5 (potential draw).

This is my only fractional output, hence the reason of the improvement as explained above.

if difference < 0, then output = 0 (potential black win)

The prediction rate for this method was 64 %. Now it is 75 % with the new formulas.

   I initially expected it to be higher, say 70 %, but as a chess player myself I can understand the result, since I've lost so many games when I was +1 / +2, and won that many when I was down in material. It's all about the actual position. (Well, now I got my wish!)

Edit 1: the drawback

The trivial solution is to output 0.5 for each test case, because this way you scored half a point regardless who won. For our test cases, this meant a total score of 3392.5 points (50 %).

But with the new formulas, 0.5 (which is an output you'd give if you're undecided who wins) is converted to 0.75 points. Remember that the maximum score you can receive for a test case is 1, for 100% confidence in the winner. As such, the new total score for a constant 0.5 output is 5088.75 points, or 75 %! In my opinion, the incentive is too strong for this case.

That score is better, though marginally, than my material advantage based algorithm. The reason for that is because the algorithm gives a probability of 1 or 0 (no incentive), assumed wins or losses, more times (3831) than it gives 0.5 (incentive), assumed draws (2954). The method is simple in the end, and as such it doesn't have a high percentage of correct answers. The boost from the new formula to constant 0.5, manages to reach that percentage, artificially.

Edit 2:

It is a known fact, mentioned in chess books, that it is usually better to have a bishop pair than a knight pair. This is especially true in the middle to end stage of the game, where the test cases are, since it's more likely to have an open position where a bishop's range is increased.

Therefore I did a second test, but this time I replaced the bishops's value from 3 to 3.5. The knight's value remained 3. This is a personal preference, so I didn't make it my default submission. The total score in this case was 4411 points (65 %). Only 1 percentage point increase was observed.

With the new formulas, the total score is 4835 points (71 %). Now the weighted bishop underperforms. But, the effect is explained because the weighted method now gives even more times assumed wins or losses (5089), than assumed draws (1696).


Brachylog, 2 bytes

.o

Try it online!

Explanation

.o
.   Assert that {the input} equals the output of the last command in the program
 o  Sort {the input}

As a full program, an assertion failure gives false., any successful run that doesn't violate any assertions gives true.


Calculate the nth term of Golomb's self-describing sequence

Jelly, non-competing

10 bytes This answer is non-competing, since the challenge predates the creation of Jelly.

’ßßạ¹ß‘µṖ¡

This uses the recursive formula a(1) = 1, a(n + 1) = 1 + a(n + 1 - a(a(n))) from the OEIS page.

Try it online!

How it works

’ßßạ¹ß‘µṖ¡ Main link. Input: n

’          Decrement; yield n - 1.
 ßß        Recursively call the main link twice, with argument n - 1.
   ạ¹      Take the absolute difference of a(a(n - 1)) and n.
     ß     Recursively call the main link, with argument n - a(a(n - 1)).
      ‘    Increment the result, yielding 1 + a(n - a(a(n - 1))).
       µ   Combine the chain to the left into a single link.
        Ṗ  Pop [1, ..., n]. This yields [] iff n == 1.
         ¡ Execute the chain iff Ṗ returned a non-empty array.


///, 12 bytes

  4
4 4

 4

A big thank you goes to @user23013, who suggested this improvement over my CJam code, outgolfing his own, highest-scoring answer in the process.

The characters are sorted by appearance. This code works in any language that just prints its own source code under the given circumstances (PHP, ASP, etc.).

CJam, 20 bytes

''S5N'5S5N'NS5N'SS5N

This approach doesn't use any built-in character counting.

Try it online in the CJam interpreter.

How it works

''S5N e# Push a single quote, a space, the integer 5 and a linefeed.
'5S5N e# Push the character 5, a space, the integer 5 and a linefeed.
'NS5N e# Push the character N, a space, the integer 5 and a linefeed.
'SS5N e# Push the character S, a space, the integer 5 and a linefeed.


Python 3, 215 bytes

def f(w):b=product(*[set("".join(w))]*16);return any(all(any(all(x-y in[1,-1,4,-4]for x,y in zip(q,q[1:]))for q in product(*[[x for x in range(16)if k[x]==c]for c in a]))for a in w)for k in b)
from itertools import*

Try it online!

This is never going to finish, so I can't really debug it or prove it works. I will try to find constant optimizations / test with reduced test cases, but if you spot a reason it would definitely fail, I will take it down / fix it.


JavaScript (ES6),  188 184  183 bytes

n=>{for(o=r=[],a=n;x=--a/n;)for(P=n;P;P--)for(p=P;y=--p/P;)for(Q=n;Q;)!(z=Q-x*Q-y*Q,g=(a,b)=>b?g(b,a%b):z%1||a>1)(a,n)&!o[k=[x,y,z/=Q--].sort()]&x+y>z&x+z>y&y+z>x?o[k]=++r:0;return+r}

Try it online!
How?
Given \$n\$, we look for all pairs \$(x,y)\$ defined as:
$$x=\dfrac{a}{n},\:1\le a <n$$
$$y=\dfrac{p}{P},\:1\le p < P \le n$$
For each pair \$(x,y)\$, we compute \$z=1-x-y\$.
The triplet \$(x,y,z)\$ is valid if all the following conditions are met:

\$a\$ and \$n\$ are coprime
there is some \$Q,\:1\le Q \le n\$ such that \$Qz\$ is an integer
we have \$x+y>z\$, \$x+z>y\$ and \$y+z>x\$

Commented
NB: this is the 184-byte version, which is slightly more readable
n => {                       // n = input
  for(                       // 1st loop:
    o = r = [],              //   o = lookup object, r = output counter
    a = n; x = --a / n;      //   go from a = n - 1 to 1
  )                          //   and define x = a / n
  for(                       // 2nd loop:
    P = n; P; P--            //   go from P = n to 1
  )                          //
  for(                       // 3rd loop:
    p = P; y = --p / P;      //   go from p = P - 1 to 1
  )                          //   and define y = p / P
  for(                       // 4th loop:
    Q = n; Q;                //   go from Q = n to 1
  ) (                        //
      z = Q - x * Q - y * Q, //   define z = Q(1 - x - y)
      g = (a, b) =>          //   g is a helper function which
        b ?                  //     recursively computes the GCD
          g(b, a % b)        //     of 2 given integers
        :                    //
          a < 2              //     and returns true if it equals 1
    )(a, n) &                //   use it to figure out if a and n are coprime
    !(z % 1) &               //   make sure that z is an integer
    !o[                      //   make sure that the key k ...
      k = [x, y, z /= Q--]   //     ... made of [ x, y, z / Q ] ...
          .sort()            //     ... and sorted (lexicographically)
    ] &                      //   was not already found
    x + y > z &              //   make sure that all triangle inequalities
    x + z > y &              //   are fulfilled
    y + z > x ?              //   if all of the above is true:
      o[k] = ++r             //     increment r and save the key in o
    :                        //   else:
      0;                     //     do nothing
  return +r                  // return the final result
}                            //


Ruby

Thought it would be interesting to extract the state abbreviations without writing any of the names or abbrevations explicitly. This one does not take misspelling of the input into consideration, because we don't care about such thing here on codegolf.SE, rihgt?

def f(s)
  [
    /(.).* (.)/,              # two words
    /^([CDGHKLPV]).*(.)$/,    # first and last letter
    /^(.).*([ZVX])/,          # unique letter
    /^([NFOUW])(.)/,          # two first letters
    /^(.)([DNR])/,            # unique second letter
    /^(.).*(L|N)\2/,          # double letters
    /^(.).SS(A|O)/,           # double S before the one used
    /^(.).*?[SNW](.)/,        # identified by the letters before them
    /(.)(.)/                  # two first letters

  ].find { |r| r =~ s.upcase }
  $1+$2
end

It took a conciderable time to figure out clever patterns to match all the states. The order of the patterns is important -- each consecutive pattern applies to the remaining states that were not matched by a previous pattern:

All states with two words in them use the initial letters of the two words:

  New Hampshire, New Jersey, New Mexico, New York, North Carolina, North Dakota, Rhode Island, South Carolina, South Dakota, West Virginia

All states beggining with any letter in {CDGHKLPV} use the first and last letter in the name:

  California, Colorado, Connecticut, Delaware, Georgia, Hawaii, Kansas, Kentucky, Louisiana, Pennsylvania, Virginia, Vermont

Of the remaining states, the letters {ZVX} are unique:

  Arizona, Nevada, Texas

All remaining states beginning with {FNOUW} use the two first letters.

  Florida, Nebraska, Ohio, Oklahoma, Oregon, Utah, Washington, Wisconsin, Wyoming

Then, {DNR} are unique as second letters:

  Arkansas, Indiana, Idaho

It's really getting hard to make general patterns, but...

Only three remaining states use double N or L, and the double letter is used in the state abbreviation:

  Tennessee, Minnesota, Illinois

A or O after double S is unique to

  Massachusetts and Missouri

Whenever {SNW} appear before other letters in the remaining state names, the letters after them are used in the abbreviations:

  Alaska, Maryland, Maine, Mississippi, Montana, Iowa

Two left. These use the two first letters:

  Alabama, Michigan

It can be golfed of course:

Ruby 2 – 191 165 154 characters

Another 26 characters off by uglifying the regexes a bit. Also, one of the original regexes turned out to be redundant!

gets;[/.* (.)/,/^[CDGHKLPV].*(.)$/,/.*([ZVX])/,/^[NFOUW](.)/,/^.([DNR])/,/.*(L|N)\1/,
/.*SS(A|O)/,/.*?[SNW](.)/,/.(.)/].find{|r|$_.upcase=~r}
puts $&[0]+$1


Python 2, 45 bytes
A mix of my initial solution and @ovs'.

lambda*a:map(lambda x,y:max(x,y)*-~(x==y),*a)

Try it online!
Python 2, 49 bytes

lambda x,y:[max(a,b)*-~(a==b)for a,b in zip(x,y)]

Try it online!
Python 2, 46 bytes
@ovs suggested this method to save 3 bytes.

lambda*x:[max(a,b)*-~(a==b)for a,b in zip(*x)]

Try it online!

How?
First off, we pair the corresponding elements, by using either * or zip(). That allows us to do our further golfing by working either with a map or a list comprehension.
The cool trick in this answer is this part: max(x,y)*-~(x==y). How does that work? - Well, as most of you already know, Python auto-converts bool values to integers when they are used in arithmetic operations. Hence, (x==y) gets evaluated as 1, if the condition is met. However, if the two values are not equal, it returns 0 instead. Then, the bitwise operation -~ increments the value returned from the bool by 1, giving us either 2 or 1. max(a,b) gives the maximum value of the pair and * multiplies it by the value returned above (so it gets multiplied by 2 only if they are equal, in which case max() returns the value of both).
This is based on the fact that the sum of two equal numbers is in fact either of them doubled, and kind of "abuses" Python's bool class being a subclass of int.


Dyalog APL, 5 bytes

(⊂,)⌸

Try it online!

,⌸ for 2 bytes almost works, but has trailing zeroes :/


Convert from postfix notation to infix notation

Clojure - 282 279 271 268 characters

(dorun(map pr((reduce(fn[s v](let[p '{e 2,* 1,/ 1,+ 0,- 0}[t z](rseq s)a
#(if(and(seq? %)(<=(p v)(p(nth % 1))))%`(~%))](if(p v)(conj(pop(pop s))
`(~@(a z)~({'e(symbol"^")}v v)~@(a t)))(conj s v))))[](map read-string
(re-seq #"\d+|[e+*/-]"(.replace(read-line)\^\e))))0)))

(line breaks are totally optional, only included for clarity, if removed ensure there is a single space between a and #( between the first two lines. all other spaces between the lines may be removed).

Assumes input will end after the first line, passes the example programs (outputs more spaces sometimes, but the right number of parentheses :)

Program can be tested here: http://ideone.com/gxykA

Ungolfed:

(defn stackify [s v]
  (let[p '{e 4,* 3,/ 3,+ 2,- 2}
       [t n] (rseq s)
       a #(if (and (coll? %) (<= (p v) (p (nth % 1)))) % `(~%))]
    (if (p v)
      (conj (pop (pop s))
            `(~@(a n) ~({'e(symbol"^")} v v) ~@(a t)))
      (conj s v))))

(defn read-postfix [s]
  "takes a string instead of reading from *in*"
  (->> (.replace s \^ \e)
       (re-seq #"\d+|[e+*/-]")
       (map read-string)
       (reduce stackify [])
       first
       (map pr)
       dorun))

(woo, first stackexchange post)


C 96

With I/O (which takes about 34 chars). Added a couple of newlines to make it readable.

main(a,b,c,d){scanf("%d,%d",&a,&b);
d=a-b;for(c=1;a>b;){c*=a--;}for(;d;)
{c/=d--;}printf("%d",c);}

Now if you'll excuse me, I have an ASCII n choose k rocket to catch.

    d;main(a
   ,         b
  ,           c
 )  int        a
 ;   {scanf    (
 (   "%d %d"   )
 ,   &a,  &b   )
 ;   d    =a   -
 b   +     b   -
 b   *     1   ;
 a             -
 a  ;for    (  c
 =  1;a>   b   ;
 )  {c=   c    *
 (  (a-- )     )
 ;  }for(      b
 =  b + 1      ;
 d  ;    )     {
 c  =     c    /
 (  d--    )   ;
  }           {
  }           {
   }         (
  printf("%d",c)
 )      ;       }
/*     *  *   * *\
 * * X   * 8 * * |
|     *      *    \
*/    //       *  */


JS

I know it's still being contested, but I thought I'd have a go:

          (function (){a='';
       a           ;         a=
     '             ';           h
    =             '#'            ;
   s             = ' '            ;
  s             ;  s  ;            s
 ;             s   ;   s            ;
s             ;    s    ;            s
;            s     ;     s           ;
s           ;      s      ;          s
;          s       ;       s         ;
 b        =       '';       s       ;
  s      ;      return(      a     +
   b    +     b+arguments[    b   +
    'ca'   +'llee'].toString   ( )
      .replace(/\S/g,h)+'###');s;
          s                 ;
               s;s;s})()

When run in Chrome's console produces:

Not 100% accurate, but I thought it was quite close. As intangible as the criteria were to begin with, I did like the idea of the challenge, despite how easy/difficult is in differing languages.


Python, j=2

The dynamic programming approach for j = 1 in my answer to the previous question does not need many modifications to work for higher j, but gets slow quickly. Table for reference:

n   p(n)

2   3/8
3   11/64
4   71/512
5   323/4096
6   501/8192
7   2927/65536
8   76519/2097152
9   490655/16777216
10  207313/8388608

And the code:

from time import*
from fractions import*
from collections import*

def main():
    N_MAX=50

    T=time()

    n=2
    Y=defaultdict(lambda:0)
    numer=0

    for a1 in [1]:
        for b1 in (1,0):
            for a2 in (1,-1):
                for b2 in (1,0,0,-1):
                    if not a1*b1+a2*b2 and not a2*b1+a1*b2:
                        numer+=1
                    Y[(a1,a2,b1,b2,a1*b1+a2*b2,a2*b1,0)]+=1

    thresh=N_MAX-1

    while time() <= T+60:
        print('%d %s'%(n,Fraction(numer,8**n/4)))

        if thresh<2:
            print('reached N_MAX with %.2f seconds remaining'%(T+60-time()))
            return

        n+=1
        X=Y
        Y=defaultdict(lambda:0)
        numer=0

        for a1,a2,b1,b2,s,t,u in X:
            if not ( abs(s)<thresh and abs(t)<thresh+1 and abs(u)<thresh+2 ):
                continue

            c=X[(a1,a2,b1,b2,s,t,u)]

            # 1,1

            if not s+1 and not t+b2+a1 and not u+b1+a1*b2+a2: numer+=c
            Y[(a1,a2,b2,1,s+1,t+b2,u+b1)]+=c

            # -1,1

            if not s-1 and not t-b2+a1 and not u-b1+a1*b2+a2: numer+=c
            Y[(a1,a2,b2,1,s-1,t-b2,u-b1)]+=c

            # 1,-1

            if not s-1 and not t+b2-a1 and not u+b1+a1*b2-a2: numer+=c
            Y[(a1,a2,b2,-1,s-1,t+b2,u+b1)]+=c

            # -1,-1

            if not s+1 and not t-b2-a1 and not u-b1+a1*b2-a2: numer+=c
            Y[(a1,a2,b2,-1,s+1,t-b2,u-b1)]+=c

            # 1,0

            c+=c

            if not s and not t+b2 and not u+b1+a1*b2: numer+=c
            Y[(a1,a2,b2,0,s,t+b2,u+b1)]+=c

            # -1,0

            if not s and not t-b2 and not u-b1+a1*b2: numer+=c
            Y[(a1,a2,b2,0,s,t-b2,u-b1)]+=c

        thresh-=1

main()

Here we are keeping track of the first two elements of A, the last two elements of B (where b2 is the last element), and the inner products of (A[:n], B), (A[1:n], B[:-1]), and (A[2:n], B[:-2]).


Strange ways to keep an endless high CPU usage

JavaScript

Even JavaScript beginners should understand the code below!

// JavaScript for Beginners
// Variables, for loops

// The line below will set a global variable called "x" to 90
// Note: never use this style of code. It is evil!
х = 90;

// The line below will set a local variable called "x" to 90
var x = 90;

for (var х=0; х<10; x++) {
  console.log('JS for beginners: this is iteration #' + х);
}

Warning

   It produces an infinite loop
 Don't run it in your browser unless you know how to kill the tab/process or restart the machine :)

How does it work?

   There are two kinds of variable names in the code:
 1. the normal 'x' which can be found on the keyboard
 2. a cyrillic 'х': http://en.wikipedia.org/wiki/%D0%A5


HTML + ES6, 241 244 237 bytes
Breakdown:

HTML: 16 bytes
JS function: 221 bytes

let f =

s=>setInterval(_=>o.innerHTML=[...s].map((c,i)=>([j,y]=[...Array(40)].map((_,k)=>[j=k%20,y,y+=77732>>j&1?k<20||-1:0],y=0)[(i+p)%40],a[y]=a[y]||[...s].fill` `)[x]=(x+=j!=9,c),x=0,a=[],p++)&&a.map(r=>r.join``).join`
`,p=30)

f("This is Programming Puzzles and Code Golf! Yay!")

How?
Building the path
The following code builds the path:
[...Array(40)].map((_, k) =>
  [
    j = k % 20,
    y,
    y += 77732 >> j & 1 ? k < 20 || -1 : 0
  ],
  y = 0
)

This gives an array of arrays [j, y, z] where j is the position modulo 20, y is the y-coordinate at this position and z is not used later (it just happens to be computed here to save some bytes).
Because the path is symmetric, we only need to encode the 20 first positions. We do that by using a binary number where each 1 bit means that y must be updated (+1 for the first half, -1 for the second half).
001
   001
      01
        1
         1
         1
          1
           01
             001
                000

With the first position being mapped to the least significant bit, this gives:
00010010111110100100 as binary = 77732 as decimal

Because this binary number is itself also symmetric, we can read it in the same order for the 2nd half.
Hence the formula:
y += (77732 >> j) & 1 ? (k < 20 ? 1 : -1) : 0

which can also be written as:
y += (77732 >> j) & 1 ? k < 20 || -1 : 0

where k is the position and j is the position modulo 20.
Updating x is much easier: we just have one special case to detect by comparing the position modulo 20 with 9.
Drawing the text
In the following code, the path building code described above has been replaced by a path variable for readability.
s => setInterval(                       // set a periodic timer:
  _ =>                                  //   with an anonymous callback
    o.innerHTML =                       //   which updates the content of 'o'
      [...s].map((c, i) => (            //   for each character c of the string s
          [j, y] = path[(i + p) % 40],  //     retrieve j and y from the path
          a[y] = a[y] || [...s].fill` ` //     initialize a[y] if it's undefined
        )[x] = (x += j! = 9, c),        //     update a[y][x] / update x
        x = 0,                          //     initialize x
        a = [],                         //     initialize a[]
        p++                             //     increment the phase
      ) &&                              //   end of map()
      a.map(r => r.join``).join`\n`,    //   join everything together
  p = 30                                //   initial phase = interval period = 30
)                                       // end of timer definition


Python 2, 98 97 91 84 bytes

s=input();L=1
for _ in`s`*8:s+=1098*int(str(s).translate('0011'*64));L*=10
print s%L

This does I/O in decimal. The integers have to be separated by the non-alphanumeric character +.

Thanks to @xnor for golfing off 2 bytes!

Try it on Ideone.

How it works

In Arithmetic in Complex Bases, the author shows how to add and multiply complex numbers in bases of the form -n + i.

For base -1 + i, addition is done similarly to regular, binary addition with carry, with two differences:

Instead of carrying 1 to the next higher position, we carry 110 to the next three.
Carry digits can propagate indefinitely. However, without leading zeroes, the sum a + b has at most eight digits more than the maximum of a and b.

We proceed as follows.

First, we add a and b as if their digits were decimal digits.

For a = 10101 and b = 11011, this gives 21112.
Next, we form a new number by replacing the digits larger than 1 with a 1, others with a 0.1

For the sum 21112, this gives 10001.
For each digit larger than 1, we have to subtract 2 from that digit and carry 110 to the next three higher positions. Since 1098 = 10 * 110 - 2, we can achieve this by multiplying the result from step 2 by 1098, then adding that product to the sum.2

For the sum 21112, this gives 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210.
We repeat steps 2 and 3 a total of d * 8 times, where d is the number of digits of a + b. 3

For the initial sum 21112, the results are

                      11002210
                      12210010
                    1220010010
                  122000010010
                12200000010010
              1220000000010010
            122000000000010010
          12200000000000010010
        1220000000000000010010
      122000000000000000010010
    12200000000000000000010010
  1220000000000000000000010010
122000000000000000000000010010
                             .
                             .
                             .

We take the final sum modulo 10d + 8, discarding all but the last d + 8 digits.

For the initial sum 21112, the final result is 10010.

1 This is achieved with translate. Repeating the string 0011 64 times makes one repetition line up with the sequence of ASCII characters 0123, achieving the desired replacement.

2 Note that the digits of this sum cannot exceed 3 (initial value 1 plus two 1's from carries).

3 This happens to work for d = 1, and d * 8 > d + 8 otherwise. The code may repeat the steps (d + 1) * 8 times, since s has a trailing L if s is a long integer.


Charcoal, 3 bytes

Ｓ‖Ｔ

Try it online! Link is to verbose version of code. Explanation: Ｓ reads the input and implicitly echos it, while ‖ is the mirroring operator, which normally just reverses the input, but the Ｔ modifies it to mirror the characters at the same time.


Brachylog, 26 bytes
{{|{|↔}~c₂l₁ʰ↰ᵗc}{+|×}ˡ}ᶜ¹

Try it online!
Times out on test cases of length 5 or greater.
It can probably be golfed further; the first half feels clunky.
Explanation
{…}ᶜ¹  Count unique outputs for predicate.

{|{|↔}~c₂l₁ʰ↰ᵗc}  First part: permute list by reversing and recursing.
{|             }  Either return input unchanged, or
  {|↔}            possibly reverse it,
      ~c₂         split it into two parts,
         l₁ʰ      check that the first part has length 1,
            ↰ᵗ    call this sub-predicate on the second part,
              c   and plug the first part back.

{+|×}ˡ  Second part:
{   }ˡ  left fold by
 +|×    addition or multiplication (chosen separately for each element).


Tcl, 675

eval [zlib i Ò×sgÆáB\nPÃïÿòpÁ\f0\fv®4\fBc!j¶%cluYbãdÃw¨)+½MB()zàõÍóÝ=\{vÏì®ÿ¢Ö¶\rk×áóUë\tÌÀOÖ)'*ð,ò¦Ì1\[¦y\v?e~oÀÛ\;¼3)ï*S!ïMgÀÜé¬0OVy_sÌÇï©³@ýa>ÀoïæCMl°7ÎG¸«£Æ'º6Ä\"e±³DÆX*#,Ãïd¹êª²Á&ü®Al±!¬Ì,KË³KÓØèÀ*tbU¶cCìÀöÓíc'VcæKl+¬(V\$µÇFI`ãtc#ô`ôbHbS¤°ú°~vã²ôãrìÁÀäD4!í%\$ÕÉcÃ°(E\\®În²vPÁÕ¨âSÃ5ØË°We?nÚ>Ê°1\"ãÄOyÆð»3Ë,²¯d7dº2)\{iÈ=ý|-w3¥\tÈGå(NÖ0ÙÏ1ä¸lpBý\}\t¾e¾E¾i¾<Y£)KCy~ÎÉçe\v2ÆEç¬rYV¸¢ç&¹*»¸¦\;¸.ÃÜ\]ÜnÉ\ ·ñùÄÇóÍ\ ?ãåøæîàÆøf»xEîá%¹WæÞ(¿é_àwíü7Æ:.ó¿3Ã_¸a©,ð·Ìó>Veÿ°\tëtOpxªS<ÃMð\\e/ð7Oñ7ÂÿzÍ4¯pé´lølÕjZÛV¯\]·råk]

Just a simple mapping between input and output. Decompressed it looks like

puts [string map { âº  â»  â¥  â¦  â£  â   â¢  â {  } â {
} â {} â {} â {
} âª  â«  â¼  âº  â  â  â¼  Â¶  Â§  â¬  â¨  â  â  â  â  â  â  â²  â¼  â  Ã  Ã¼  Ã©  Ã¢  Ã¤  Ã   Ã¥  Ã§  Ãª  Ã«  Ã¨  Ã¯  Ã®  Ã¬  Ã  Ã  Ã  Ã¦  Ã  Ã´  Ã¶  Ã²  Ã»  Ã¹  Ã¿  Ã  Ã  Â¢  Â£  Â¥  â§  Æ   Ã¡ ¡ Ã ¢ Ã³ £ Ãº ¤ Ã± ¥ Ã ¦ Âª § Âº ¨ Â¿ © â ª Â¬ « Â½ ¬ Â¼  Â¡ ® Â« ¯ Â» ° â ± â ² â ³ â ´ â¤ µ â¡ ¶ â¢ · â ¸ â ¹ â£ º â » â ¼ â ½ â ¾ â ¿ â À â Á â´ Â â¬ Ã â Ä â Å â¼ Æ â Ç â È â É â Ê â© Ë â¦ Ì â  Í â Î â¬ Ï â§ Ð â¨ Ñ â¤ Ò â¥ Ó â Ô â Õ â Ö â × â« Ø âª Ù â Ú â Û â Ü â Ý â Þ â ß â à Î± á Ã â Î ã Ï ä Î£ å Ï æ Âµ ç Ï è Î¦ é Î ê Î© ë Î´ ì â í Ï î Îµ ï â© ð â¡ ñ Â± ò â¥ ó â¤ ô â  õ â¡ ö Ã· ÷ â ø Â° ù â ú Â· û â ü â¿ ý Â² þ â  ÿ Â } [read stdin]]


How many languages can you use simultaneously in ONE functioning program in under 500 bytes

HTML, CSS, PHP, JavaScript, CoffeeScript, RegEx, sed, bash; 8 languages

Displays colors of the rainbow.

(Only 396 bytes) will try to add more languages

HTML + CSS is turning complete and counts as a valid language on PPCG. I've been told CoffeeScript is different enough as JavaScript to be counted as a separate language. And RegEx has been specifically allowed also.

PHP allows for addition of many languages especially with exec and shell_exec functions.

Golfed to fit inside byte limit (ES6)

Uses:

PHP to generate CSS
PHP, uses exec to run bash
sed to split color items for bash
CSS to specify text colors
JavaScript to generate elements
RegEx to split color items for JS
CoffeScript to print elements
HTML as a wrapper / output

Faster & Ungolfed (All modern browsers)


Perl 6, 47 bytes

{my$d=Date.new($_);map($d+*-$d.day-of-week,^7)}

Try it online!

The code is almost self-explanatory. First we make up a Date object $d from the string, which happens to be in the nice ISOwhatever format. We can perform arithmetic with the dates (adding an integer = adding that many days, the same with subtracting). So $d-$d.day-of-week is the last this (oh my god, week has always started with Monday for me :D) week's Sunday. (.day-of-week is 1 for Monday to 7 for Sunday.) We then map over 0 to 6 (^7) and add that to the Sunday, getting all the days in the week. The number we're mapping over appears in the place of the star *. This list is then returned.


Program touch-tone instructions for my fingers


Ruby, 1168 932
Corrected a mistake from last night, more golfing to do after clarifying.
This is (currently) a full program that accepts a number from stdin and outputs an svg file to stdout. I chose svg because I knew it was possible to meet all the requirements of the question, but it did have some issues. in particular SVG only supports arcs of circles as part of the path object, and does not define them in terms of their centre but rather the two endpoints.
Code
n=gets.to_i
r=64*w=0.75**0.5
m=1<<n-2
z=128*m/w
a=(s="<path style='fill:none;stroke:black;stroke-width:3.464102' transform='translate(%f %f)'
")%[0,r-r*m*8/3]+"d='M18.11943,-2A#{b=r-6*w-32} #{b} 0 0,0 #{-b} 0#{k='A%f %f 0 0 '%([58*w]*2)}0 0,38.71692
M28.58980,1.968882#{l='A%f %f 0 0 '%([70*w]*2)}0 #{c=r+6*w-32} 0A#{c} #{c} 0 0,0 #{-c} 0#{l}0 -9 44.65423'/>"
p=2
m.times{|i|(i*2+1).times{|j|(p>>j)%8%3==2&&a<<s%[128*(j-i),r*3+r*i*4-r*m*8/3]+
"d='M-55,44.65423#{k}0 11.5,25.11473#{l}1 35.41020,1.968882
M-64,51.48786#{l}0 20.5,30.31089#{k}1 36.82830,13.17993
M-82.17170,-2.408529#{l}1 -11.5,25.11473#{k}0 0,38.71692
M-81.52984 8.35435#{k}1 -20.5,30.31089#{l}0 -9,44.65423
M9,44.65423#{k}0 81.52984,8.35435
M0,51.48786#{l}0 91.17169,13.17993'/>"}
p^=p*4}
puts "<svg xmlns='http://www.w3.org/2000/svg' viewBox='#{-z} #{-z} #{e=2*z+1} #{e}' width='#{e}px' height='#{e}px'>"+
"<g transform='rotate(%d)'>#{a}</g>"*3%[0,120,240]+"</svg>"

Output N=4
rescaled by Stack exchange. Looks much better as original.

Explanation
At first I considered something like http://euler.nmt.edu/~jstarret/sierpinski.html where the triangle is broken down into three differently coloured strands, each of which forms a path from one corner to another. The incomplete circles are shown as incomplete hexagons there. inscribing circles inside the hexagons shows that the circle radius should be sqrt(3)/2 times the sidelength. The strands could be built up recursively as shown, but there is an added complication because the corners need to be rounded and it is difficult to know in which direction to curve, so I did not use this approach.
What I did was the following.
In the image below you can see there are horizontal twists belonging to the N=2 units (in green) arranged in a sierpinski triangle and additional bridging twists (in blue.)
It is common knowledge that the odd numbers on Pascal's triangle form a sierpinski triangle. A sierpinski triangle of binary digits can be obtained in an analogous manner by starting with the number p=1 and iteratively xoring it with p<<1.
I modified this approach, starting at p=2 and iteratively xoring with p*4. This gives a sierpinski triangle alternating with columns of zeros.
Now we can rightshift p and inspect the last three bits using %8. If they are 010 we need to draw a green twist belonging to an N=2 unit. if they are 101 we need to draw a blue, bridging twist. To test for both of these numbers together we find the modulo %3 and if this is 2 we need to draw the twist.
Finally, in additional to the horizontal twists, we make two copies rotated through 120 and 240 degrees to draw the diagonal twists and complete the picture. All that remains is to add the corners.
Commented code
n=gets.to_i

#r=vertical distance between rows
r=64*w=0.75**0.5

#m=number of rows of horizontal twists
m=1<<n-2

#z=half the size of the viewport
z=128*m/w

#s=SVG common to all paths
s="<path style='fill:none;stroke:black;stroke-width:3.464102' transform='translate(%f %f)'
"

#initialize a with SVG to draw top corner loop. Set k and l to the SVG common to all arcs of 58*w and 70*w radius
a=s%[0,r-r*m*8/3]+
"d='M18.11943,-2A#{b=r-6*w-32} #{b} 0 0,0 #{-b} 0#{k='A%f %f 0 0 '%([58*w]*2)}0 0,38.71692
M28.58980,1.968882#{l='A%f %f 0 0 '%([70*w]*2)}0 #{c=r+6*w-32} 0A#{c} #{c} 0 0,0 #{-c} 0#{l}0 -9 44.65423'/>"

#p is the pattern variable, top row of twists has one twist so set to binary 00000010
p=2

#loop vertically and horizontally
m.times{|i|
 (i*2+1).times{|j|

   #leftshift p. if 3 digits inspected are 010 or 101
   (p>>j)%8%3==2&&

   #append to a, the common parts of a path...
   a<<s%[128*(j-i),r*3+r*i*4-r*m*8/3]+

   #...and the SVG for the front strand and left and right parts of the back strand (each strand has 2 borders)
"d='M-55,44.65423#{k}0 11.5,25.11473#{l}1 35.41020,1.968882
M-64,51.48786#{l}0 20.5,30.31089#{k}1 36.82830,13.17993
M-82.17170,-2.408529#{l}1 -11.5,25.11473#{k}0 0,38.71692
M-81.52984 8.35435#{k}1 -20.5,30.31089#{l}0 -9,44.65423
M9,44.65423#{k}0 81.52984,8.35435
M0,51.48786#{l}0 91.17169,13.17993'/>"}

#modify the pattern by xoring with 4 times itself for the next row
p^=p*4}

#output complete SVG of correct size with three copies of the finished pattern rotated through 0,120,240 degrees.
puts "<svg xmlns='http://www.w3.org/2000/svg' viewBox='#{-z} #{-z} #{e=2*z+1} #{e}' width='#{e}px' height='#{e}px'>"+
"<g transform='rotate(%d)'>#{a}</g>"*3%[0,120,240]+"</svg>"


MATL, 2 bytes
dz

Try it online! Or verify all test cases.
Explanation
     % Implicit input
d    % Consecutive differences
z    % Number of nonzeros
     % Implicit display


String rotation - output string repeatedly moving first character to the end

Haskell, 27 bytes

scanl(\(a:b)_->b++[a])=<<id

Try it online!


Jelly, 12 bytes

»0Æf×Ṫ$-¦×2/

Try it online!

How it works

»0Æf×Ṫ$-¦×2/  Main link. Argument: n

»0            Take the maximum of n and 0.
              Jelly's prime factorization does weird things for negative numbers.
  Æf          Take the prime factorization of the maximum.
        ¦     Conditional application:
    ×Ṫ$         Pop the last element of the array and and multiply all elements
                of the remaining array with it.
       -        Replace the element at index -1 with the corresponding element in
                the result.
              This effectively multiplies the last two elements of the array.
         ×2/  Multiply the factors in non-overlapping pairs. If the last element
              does not have a partner, leave it unmodified.


Jelly, 9 bytes
ḤR>)FŒHṪS

A monadic Link accepting \$n\$ which yields \$a(n)\$.
Try it online! Or see the test-suite.
How?
We can think of \$S\$ as being built in blocks of length \$2i\$ where each block is a string of \$i\$ ones followed by \$i\$ zeros: 10 1100 111000 ....
If we stop at \$i=x\$ and call the result \$S_x\$ we know that \$S_x\$ necessarily contains an equal number of ones and zeros.
We also know that the length of \$S_x\$ will be  \$\sum_{i=1}^{x}2i = 2 \sum_{i=1}^{x}i = 2T(x)\$.
So the value of \$a(x)\$ is the count of ones in the first half of \$S_x\$.
An alternative way to get this same result is to subtract the count of the zeros in the first half of \$S_x\$ from \$T(x)\$, and since \$S_x\$ contains an equal number of ones and zeros this must also be the count of zeros in the second half of \$S_x\$. Therefore we can form the complement of \$S_x\$ and count the ones in its second half:
ḤR>)FŒHṪS - Link: integer, n
   )      - for each (i in [1..n]): e.g. i=3
Ḥ         -   double                       6
 R        -   range                        [1,2,3,4,5,6]
  >       -   greater than i?              [0,0,0,1,1,1]
    F     - flatten -> [0,1,0,0,1,1,0,0,0,1,1,1,...]
     ŒH   - split into two equal length parts
       Ṫ  - tail
        S - sum


BrainFuck: 21
>,[+<[->+>+<<]>.>+>,]

Assumes EOF=zero
echo -n 'My secret password is 123456!' | beef encrypt.bf
==> N{#wjiym}*{mv36HJLNPR>


sed, 46 byte compiler
s/</<</g
s/>/>[->[-]>[-]+<<]>/g
s/^/[-]>[-]+</

I didn't notice that the output was also supposed to be golf until after writing the program, so I will go for the short compiler. Also it was far too much work to test, so please notify if it does not function correctly :)


Decompose a range in aligned blocks of size 2^n

The following greedy algorithm works optimally:

  Choose the larges block allowed which is aligned with the lower bound
  and does not exceed the total range. Add this range to your result set
  and remove it from the search space. Loop until the entire range is
  covered.

In the following lines I took your example and simplified it to the interesting part, i.e. take the range 72-91:

0)  Range: 72 - 91 (Size 20)

1a) Largest block size allowed @72: 8
1b) Subrange #1: 72 - 79
1c) Remaining: 80 - 91 (Size 12)

2a) Largest  block size allowed @80: 16 (exceeds size) -> 8
2b) Subrange #2: 80 - 87
2c) Remaining: 88 - 91 (Size 4)

3a) Largest  block size allowed @88: 8 (exceeds size) -> 4
3b) Subrange #3: 88 - 91
3c) Remaining: empty

Result: (72-79) (80-87) (88-91)

The structure can be seen even better, if we express the numbers in binary format.

0)  Range: 01001000, Size 10100

1a) Largest block size allowed @01001000: 1000
1b) Subrange #1: 01001000, Size 1000
1c) Remaining: 01010000, Size 1100

2a) Largest block size allowed @01010000: 10000 (exceeds size) -> 1000
2b) Subrange #2: 01010000, Size 1000
2c) Remaining: 01011000, Size 100

3a) Largest  block size allowed @01011000: 1000 (exceeds size) -> 100
3b) Subrange #3: 01011000, Size 100
3c) Remaining: empty

A note for implementation: the block size for the subrange to be chosen corresponds either to the rightmost 1 bit of the lower bound or the leftmost 1 bit of the size of the range (whichever is smaller).


J, 21 25 bytes

0{0{(_2(_2-/ .*\|:)\])^:_

Usage:

   ]input=.(3,1,4,1),(5,9,2,6),(5,3,5,8),:(9,7,9,3)
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
   (0{0{(_2(_2-/ .*\|:)\])^:_) input
_1430

At every step we cut up the matrix to 2-by-2's and compute each ones determinant resulting in the next step's input matrix. We repeat this process until the result doesn't change (the final element is the determinant itself). We convert the final result to a scalar with 0{0{.

Try it online here.


Tikz, 175 bytes

Composition III in Black and White, 175 bytes

\documentclass[tikz]{standalone}\begin{document}\tikz{\def\b{;\draw[line width=}\def\a{)--(}\clip(1,1\a1,5\a5,5\a5,1)\b2mm](0,4\a6,4\a6,3\a4,3)\b1mm](4,0\a4,5);}\end{document}

Verify it in the Blogosphere

This is perhaps one of Mondrian's most minimalistic works and I am surprised no one has found it yet.  It is not however particularly interesting so I have included several other paintings in my answer.

Explanation

There is a bit of a wrapper that is associated with every tikz answer.  The wrapper is:

\documentclass[tikz]{standalone}\begin{document}\tikz{
}\end{document}

Once you get past the wrapper there are a few \def statements that save bytes but unfortunately obfuscate the code:

\def\b{;\draw[line width=}\def\a{)--(}

If we make all the proper substitutions our code comes out looking like:

\clip(1,1)--(1,5)--(5,5)--(5,1);
\draw[line width=2mm](0,4)--(6,4)--(6,3)--(4,3);
\draw[line width=1mm](4,0)--(4,5);

The first bit is a \clip and is very important, but we will skip over it for the time being.

Now we draw the first line on the blank canvas,  This line is rather thick so we use [line width=2mm] to set the thickness to 2mm:

\draw[line width=2mm](0,4)--(6,4)--(6,3)--(4,3);

This connects a couple of nodes and produces this shape:

Next we \draw a second stroke, however this stroke is thinner so we have to set the line thickness to 1mm:

\draw[line width=1mm](4,0)--(4,5);

Now our painting looks like:

This is close to the original but not quite, so here is where the \clip comes into play.  We use the \clip to remove all the extra lines from our canvas and set the canvas to the correct size.  With the canvas resized we get the image:

Composition With Yellow Patch, 214 bytes

\documentclass[tikz]{standalone}\begin{document}\tikz[line width=2mm]{\clip(1,1)rectangle(7,7);\draw(0,8)rectangle(4,3.5)rectangle(6.5,1.2)rectangle(4,0);\draw[fill=yellow](6.5,3.5)rectangle(8,2.5);}\end{document}

Evaluate it in CyberSpace

Explanation to come

Composition II in Blue and Yellow, 225 bytes

\documentclass[tikz]{standalone}\begin{document}\tikz[line width=2mm]{\clip(1,1)rectangle(7,10);\draw(8,9)rectangle(3,6)rectangle(0,0);\draw[fill=yellow](0,0)rectangle(3,2);\draw[fill=blue](0,11)rectangle(3,9);}\end{document}

Assess it over the Webbernetz!

Explanation to come

Composition B (No. 2) in Red, 232 bytes

\documentclass[tikz]{standalone}\begin{document}\tikz[line width=2mm]{\clip(1,1)rectangle(10,13);\draw[line width=1mm](1.2,5)--(1.2,9);\draw[fill=red](0,14)rectangle(5,9);\draw(0,9)rectangle(11,5)(7,0)rectangle(5,14);}\end{document}

Attempt it within the Internet!

Explanation

First here is the code with line breaks inserted to make it more readable:

\documentclass[tikz]{standalone}
\begin{document}
\tikz[line width=2mm]{
\clip(1,1)rectangle(10,13);
\draw[line width=1mm](1.2,5)--(1.2,9);
\draw[fill=red](0,14)rectangle(5,9);
\draw(0,9)rectangle(11,5)(7,0)rectangle(5,14);
}
\end{document}

The first command of interest is

\draw[fill=red](0,14)rectangle(5,9);

This draws a red rectangle with a black outline.  For the upper left hand corner of the painting.

We then draw two more rectangles with white interiors and black outlines to create the grid pattern on the painting

\draw(0,9)rectangle(11,5)(7,0)rectangle(5,14);

We then draw in a thin line

\draw[line width=1mm](1.2,5)--(1.2,9);

And crop the image to the proper size

\clip(1,1)rectangle(10,13);

Composition II in Red, Blue and Yellow, 251 bytes

\documentclass[tikz]{standalone}\begin{document}\tikz[line width=1mm]{\clip(1,1)rectangle(9,9);\draw[fill=yellow](8.5,6)--(0,6)--(8.5,6)--(8.5,2)rectangle(10,0);\draw[fill=red](3,3)rectangle(10,10);\draw[fill=blue](0,0)rectangle(3,3);}\end{document}

Test it upon the World Wide Web!

Explanation

First I will insert some line breaks to make my code readable

\documentclass[tikz]{standalone}
\begin{document}
\tikz[line width=1mm]{
\clip(1,1)rectangle(9,9);
\draw[fill=yellow](8.5,6)--(0,6)--(8.5,6)--(8.5,2)rectangle(10,0);
\draw[fill=red](3,3)rectangle(10,10);
\draw[fill=blue](0,0)rectangle(3,3);
}
\end{document}

The first line of importance is:

\draw[fill=yellow](8.5,6)--(0,6)--(8.5,6)--(8.5,2)rectangle(10,0);

This draws the following shape:

This strange shape is the yellow rectangle in the lower right corner and the two lines that are no the edge of a colored rectangle.  Next we insert the red square and cover up the extra lines made by the last shape:

\draw[fill=red](3,3)rectangle(10,10);

This comes out looking like:

Now we insert our blue square:

\draw[fill=blue](0,0)rectangle(3,3);

Now all that is left is to crop out all the unnecessary parts of the image using a \clip

\clip(1,1)rectangle(10,10);

Composition II, 308 bytes

\documentclass[tikz]{standalone}\begin{document}\tikz[line width=2mm]{\clip(1,1)rectangle(12.6,13);\draw(0,0)rectangle(10,4)rectangle(2,12)--(0,12);\draw[fill=red](10,1.6)rectangle(14,0);\draw[fill=yellow](6,12)rectangle(10,14);\draw[fill=blue](0,4)rectangle(2,8);\fill(10,10)rectangle(14,14);}\end{document}

Check it out on the Information-Super-Highway

Explanation to come


JavaScript (ES6) 164
B='teen-hundreds were a time',alert(B.replace(/./g,
"The eigh"+B+" for rum.\nThe nine"+B+" for fun.\nThe two-thousands are a time to run\na civilized classroom.\n"))

Test In FireFox/FireBug console.


Jelly, 13 bytes

OI’“¡ʂƁ»ṁ$€ż@

Try it online!

Explanation

OI’“¡ʂƁ»ṁ$€ż@ – Full program. Take a string as a command line argument.
O             – Ordinal. Get the ASCII values of each character.
 I’           – Get the increments (deltas), and subtract 1 from each.
          €   – For each difference I...
   “¡ʂƁ»ṁ$    – Mold the compressed string "tape" according to these values.
                Basically extends / shortens "tape" to the necessary length.
           ż@ – Interleave with the input.


Advent Challenge 5: Move the presents to the transport docks!


Jelly, 17 14 13 bytes

+13ḃ3Um0ị2/⁼/

Try it online! or verify all 27×27 cases.

How it works

+13ḃ3Um0ị2/⁼/  Main link. Argument: [f, g] (encoded as integers)

+13            Add 13 ([1, 1, 1] in base 3) to f and g.
   ḃ3          Convert f + 13 and g + 13 to bijective base 3.
               Bijective base 3 uses the digits 1 to 3 instead of 0 to 2.
               This yields [[f(2)+1, f(1)+1, f(0)+1], [g(2)+1, g(1)+1, g(0)+1]].
               The increments account for 1-based indexing.
     U         Reverse each digit array.
               This yields [[f(0)+1, f(1)+1, f(2)+1], [g(0)+1, g(1)+1, g(2)+1]].
      m0       Concatenate the list with a reversed copy of itself.
        ị2/    Split the result into pairs, and reduce each one by indexing.
               This computes g○f and f○g.
          ⁼/   Reduce by match; return 1 iff g○f = f○g.