Scramble words while preserving their outlines

Jelly, 80 74 bytes

-2 bytes by moving from czar + vex + mow + sun to czar + vexes + unmown (the repeated es and ns are not a problem)
-1 byte using Tị rather than ȦÐf
-1 byte using Œle€Øa rather than i@€ØB>⁵
-2 bytes by reconfiguring the layout a little

Tị
TẊị⁹ż@œp
e€ç⁸F
W;“HọƊṘ€.`]HɲøƁḤ0ẉlfrøj⁷»Ḳ¤ç/
Ḣ,ṪjÇḟ0
Œle€Øað¬œpÇ€ÑżœpÑ¥

A full program taking a character list (or Python formatted string), which prints the result of the scrambling.

Try it online!

A huge amount of difficulty for Jelly here it seems (either that or I have missed a trick, which has been known to happen!) This will surely be beaten by languages with better string manipulation like Retina(no random functionality) or 05ab1e.

How?

Tị - Link 1, get truthy items: list a
T  - truthy indexes of a
 ị - index into a

TẊị⁹ż@œp - Link 2, selective shuffle: list a, list b
T        - truthy indexes of a (those indexes that may be shuffled in b)
 Ẋ       - random shuffle
   ⁹     - link's right argument, b
  ị      - index into (gets the shuffled values)
      œp - partition b at truthy indexes of a
    ż@   - zip with reversed @rguments (place shuffled values - yields a list of lists)

e€ç⁸F - Link 3, value selective shuffle: list a, list b
e€    - c exists in b? for €ach c in a (1s where b has shuffle-able characters, else 0s)
   ⁸  - link's left argument, a
  ç   - call the last link (2) as a dyad
    F - flatten the result (from the yielded list of lists to one list)

W;“HọƊṘ€.`]HɲøƁḤ0ẉlfrøj⁷»Ḳ¤ç/ - Link 4, perform all shuffles on a word's innards: list x
W                             - wrap x in a list
                          ¤   - nilad followed by link(s) as a nilad:
  “HọƊṘ€.`]HɲøƁḤ0ẉlfrøj⁷»     -   compression of s(bdfhkl)+d( czar)+d(vexes)+d(unmown)+s( gpqy)+d( ti)
                              -     where d() looks up a word in Jelly's dictionary and s() adds a string to the compressed output.
                         Ḳ    -   split on spaces: ["bdfhkl","czarvexesunmown","gpqy","ti"]
                           ç/ - reduce by last link (3) as a dyad (shuffles by each in turn)

Ḣ,ṪjÇḟ0 - Link 5, shuffle a word: list w
Ḣ       - head w (yields the leftmost character and modifies w)
  Ṫ     - tail w (yields the rightmost character and modifies w)
 ,      - pair
        -   Note: head and tail yield 0 when w is empty, so ['a'] -> ["a",0] and [] -> [0,0]
    Ç   - call the last link (4) as a monad (with the modified w)
   j    - join
     ḟ0 - filter discard zeros (thus single or zero letter words pass through unchanged)

Œle€Øað¬œpÇ€ÑżœpÑ¥ - Main link: list s
Œl                 - convert s to lowercase, say t
    Øa             - lowercase alphabet, say a
  e€               - c exists in a? for €ach c in t
      ð            - dyadic chain separation (call that u)
       ¬           - not (vectorises across u), say v
        œp         - partition s at truthy indexes of v (extract words, plus empty lists from within strings of non-alphabetic characters)
          Ç€       - call the last link (5) as a monad for €ach (shuffle their innards)
            Ñ      - call the next link (1) as a monad (only keep the actual words)
                 ¥ - last two links as a dyad:
              œp   -   partition s at truthy indexes of u (get the non-words, plus empty lists from within strings of alphabetic characters)
                Ñ  -   call the next link (1) as a monad (only keep actual non-words)
             ż     - zip together
                   - implicit print


HTML/CSS/JavaScript 207 183 180 161 152

Tested and working in the latest Firefox and Chrome browsers.

<body id=b onload=setInterval("b.innerHTML=b.bgColor=Date().replace(/.*(..):(..):(..).*/,'#$1$2$3')",0) text=#fff style=position:fixed;top:50%;left:47%>

Demo Here


Find the largest gap between good primes

Probably 4032, mixed Atkin-Bernstein sieve and "deterministic" Miller-Rabin

Wheel factorisation and good primes

It's highly obvious that with the exceptions of 2, 3, and 5, every prime is coprime to 2*3*5 = 60. There are 16 equivalence classes modulo 60 which are coprime to 60, so any primality test only needs to check those 16 cases.

However, when we're looking for "good" primes we can thin the herd even more. If gcd(x, 60) = 1, we find that in most cases gcd(x-1, 60) is either 6 or 10. There are 6 values of x for which it is 2:

17, 23, 29, 47, 53, 59

Therefore we can precompute the "good" primes of the form 2^a 3^b + 1 and 2^a 5^b + 1 and merge them into the result of a prime generator which only considers 10% of numbers as even potential primes.

Implementation notes

Since I already had a Java implementation of the Atkin-Bernstein sieve lying around, and that already uses a wheel as a key component, it seemed natural to strip out the unnecessary spokes and adapt the code. I originally tried using a producer-consumer architecture to exploit the 8 cores, but memory management was too messy.

To test whether a prime is a "good" prime, I'm using a "deterministic" Miller-Rabin test (which really means a Miller-Rabin test which someone else has pre-checked against a list generated deterministically). This can certainly be rewritten to also use Atkin-Bernstein, with some caching to cover the ranges corresponding to sqrt, cbrt, etc., but I'm not sure whether it would be an improvement (because it would be testing lots of numbers which I don't need to test), so that's an experiment for another day.

On my fairly old computer this runs to

987417437 - 987413849 = 3588
1123404923 - 1123401023 = 3900
1196634239 - 1196630297 = 3942
1247118179 - 1247114147 = 4032

in pretty much exactly 2 minutes, and then

1964330609 - 1964326433 = 4176
2055062753 - 2055058529 = 4224
2160258917 - 2160254627 = 4290

at 3:10, 3:20, and 3:30 respectively.

import java.util.*;

public class PPCG65876 {
    public static void main(String[] args) {
        long[] specials = genSpecials();
        int nextSpecialIdx = 0;
        long nextSpecial = specials[nextSpecialIdx];
        long p = 59;
        long bestGap = 2;

        for (long L = 1; true; L += B) {

            long[][] buf = new long[6][B >> 6];
            int[] Lmodqq = new int[qqtab.length];
            for (int i = 0; i < Lmodqq.length; i++) Lmodqq[i] = (int)(L % qqtab[i]);

            for (long[] arr : buf) Arrays.fill(arr, -1); // TODO Can probably get a minor optimisation by inverting this
            for (int[] parms : elliptic) traceElliptic(buf[parms[0]], parms[1], parms[2], parms[3] - L, parms[4], parms[5], Lmodqq, totients[parms[0]]);
            for (int[] parms : hyperbolic) traceHyperbolic(buf[parms[0]], parms[1], parms[2], parms[3] - L, Lmodqq, totients[parms[0]]);

            // We need to filter down to squarefree numbers.
            long pg_base = L * M;
            squarefreeMid(buf, invTotients, pg_base, 247, 1, 38);
            squarefreeMid(buf, invTotients, pg_base, 253, 1, 38);
            squarefreeMid(buf, invTotients, pg_base, 257, 1, 38);
            squarefreeMid(buf, invTotients, pg_base, 263, 1, 38);
            squarefreeMid(buf, invTotients, pg_base, 241, 0, 2);
            squarefreeMid(buf, invTotients, pg_base, 251, 0, 2);
            squarefreeMid(buf, invTotients, pg_base, 259, 0, 2);
            squarefreeMid(buf, invTotients, pg_base, 269, 0, 2);

            // Turn bitmasks into primes
            long[] page = new long[150000]; // TODO This can almost certainly be smaller
            long[] transpose = new long[6];
            for (int j = 0, off = 0; j < (B >> 6); j++) {
                // Reduce cache locality problems by transposing.
                for (int k = 0; k < 6; k++) transpose[k] = buf[k][j];
                for (long mask = 1L; mask != 0; mask <<= 1) {
                    for (int k = 0; k < 6; k++) {
                        if ((transpose[k] & mask) == 0) page[off++] = pg_base + totients[k];
                    }

                    pg_base += M;
                }
            }

            // Insert specials and look for gaps.
            for (long q : page) {
                if (q == 0) break;

                // Do we need to insert one or more specials?
                while (nextSpecial < q) {
                    if (nextSpecial - p > bestGap) {
                        bestGap = nextSpecial - p;
                        System.out.format("%d - %d = %d\n", nextSpecial, p, bestGap);
                    }

                    p = nextSpecial;
                    nextSpecial = specials[++nextSpecialIdx];
                }

                if (isGood(q)) {
                    if (q - p > bestGap) {
                        bestGap = q - p;
                        System.out.format("%d - %d = %d\n", q, p, bestGap);
                    }

                    p = q;
                }
            }

        }
    }

    static long[] genSpecials() {
        // 2^a 3^b + 1 or 2^a 5^b + 1
        List<Long> tmp = new LinkedList<Long>();
        for (long threes = 3; threes <= 4052555153018976267L; threes *= 3) {
            for (long t = threes; t > 0; t <<= 1) tmp.add(t + 1);
        }
        for (long fives = 5; fives <= 7450580596923828125L; fives *= 5) {
            for (long f = fives; f > 0; f <<= 1) tmp.add(f + 1);
        }

        // Filter down to primes
        Iterator<Long> it = tmp.iterator();
        while (it.hasNext()) {
            long next = it.next();
            if (next < 60 || next > 341550071728321L || !isPrime(next)) it.remove();
        }

        Collections.sort(tmp);
        long[] specials = new long[tmp.size()];
        for (int i = 0; i < tmp.size(); i++) specials[i] = tmp.get(i);

        return specials;
    }

    private static boolean isGood(long p) {
        long d = p - 1;
        while ((d & 1) == 0) d >>= 1;

        if (d == 1) return false;

        // Is d a prime power?
        if (d % 3 == 0 || d % 5 == 0) {
            // Because of the way the filters before this one work, nothing should reach here.
            throw new RuntimeException("Should be unreachable");
        }

        // TODO Is it preferable to reuse the Atkin-Bernstein code, caching pages which correspond
        // to the possible power candidates?
        if (isPrime(d)) return true;
        for (int a = (d % 60 == 1 || d % 60 == 49) ? 2 : 3; (1L << a) < d; a++) {
            long r = (long)(0.5 + Math.pow(d, 1. / a));
            if (d == (long)(0.5 + Math.pow(r, a)) && isPrime(r)) return true;
        }

        return false;
    }

    /*---------------------------------------------------
               Deterministic Miller-Rabin
    ---------------------------------------------------*/
    public static boolean isPrime(int x) {
        // See isPrime(long). We pick bases which are known to work for the entire range of int.
        // Special case for the bases.
        if (x == 2 || x == 7 || x == 61) return true;

        int d = x - 1;
        int s = 0;
        while ((d & 1) == 0) { s++; d >>= 1; } // TODO Can be optimised

        if (!isSPRP(2, d, s, x)) return false;
        if (!isSPRP(7, d, s, x)) return false;
        if (!isSPRP(61, d, s, x)) return false;
        return true;
    }

    private static boolean isSPRP(int b, int d, int s, int x /* == d << s */) {
        int l = modPow(b, d, x);
        if (l == 1 || l == x - 1) return true;
        for (int r = 1; r < s; r++) {
            l = modPow(l, 2, x);
            if (l == x - 1) return true;
            if (l == 1) return false;
        }

        return false;
    }

    public static int modPow(int a, int b, int c) {
        int accum = 1;
        while (b > 0) {
            if ((b & 1) == 1) accum = (int)(accum * (long)a % c);
            a = (int)(a * (long)a % c);
            b >>= 1;
        }
        return accum;
    }

    public static boolean isPrime(long x) {
        if (x < Integer.MAX_VALUE) return isPrime((int)x);

        long d = x - 1;
        int s = 0;
        while ((d & 1) == 0) { s++; d >>= 1; } // TODO Can be optimised

        // If b^d == 1 (mod x) or (b^d)^(2^r) == -1 (mod x) for some r < s then we pass for base b.
        // We select bases according to Jaeschke, Gerhard (1993), "On strong pseudoprimes to several bases", Mathematics of Computation 61 (204): 915–926, doi:10.2307/2153262
        // TODO Would it be better to use a set of 5 bases from http://miller-rabin.appspot.com/ ?
        if (!isSPRP(2, d, s, x)) return false;
        if (!isSPRP(3, d, s, x)) return false;
        if (!isSPRP(5, d, s, x)) return false;
        if (!isSPRP(7, d, s, x)) return false;
        if (x < 3215031751L) return true;
        if (!isSPRP(11, d, s, x)) return false;
        if (x < 2152302898747L) return true;
        if (!isSPRP(13, d, s, x)) return false;
        if (x < 3474749660383L) return true;
        if (!isSPRP(17, d, s, x)) return false;
        if (x < 341550071728321L) return true;

        throw new IllegalArgumentException("Overflow");
    }

    private static boolean isSPRP(long b, long d, int s, long x /* == d << s */) {
        if (b * (double)x > Long.MAX_VALUE) throw new IllegalArgumentException("Overflow"); // TODO Work out more precise page bounds

        long l = modPow(b, d, x);
        if (l == 1 || l == x - 1) return true;
        for (int r = 1; r < s; r++) {
            l = modPow(l, 2, x);
            if (l == x - 1) return true;
            if (l == 1) return false;
        }

        return false;
    }

    /**
     * Computes a^b (mod c). We assume c &lt; 2^62.
     */
    public static long modPow(long a, long b, long c) {
        long accum = 1;
        while (b > 0) {
            if ((b & 1) == 1) accum = prodMod(accum, a, c);
            a = prodMod(a, a, c);
            b >>= 1;
        }
        return accum;
    }

    /**
     * Computes a*b (mod c). We assume c &lt; 2^62.
     */
    private static long prodMod(long a, long b, long c) {
        // The naive product would require 128-bit integers.

        // Consider a = (A << 32) + B, b = (C << 31) + D. Different shifts chosen deliberately.
        // Then ab = (AC << 63) + (AD << 32) + (BC << 31) + BD with intermediate values remaining in 63 bits.
        long AC = (a >> 32) * (b >> 31) % c;
        long AD = (a >> 32) * (b & ((1L << 31) - 1)) % c;
        long BC = (a & ((1L << 32) - 1)) * (b >> 31) % c;
        long BD = (a & ((1L << 32) - 1)) * (b & ((1L << 31) - 1)) % c;

        long t = AC;
        for (int i = 0; i < 31; i++) {
            t = (t + t) % c;
        }
        // t = (AC << 31)
        t = (t + AD) % c;
        t = (t + t) % c;
        t = (t + BC) % c;
        // t = (AC << 32) + (AD << 1) + BC
        for (int i = 0; i < 31; i++) {
            t = (t + t) % c;
        }
        // t = (AC << 63) + (AD << 32) + (BC << 31)
        return (t + BD) % c;
    }

    /*---------------------------------------------------
                      Atkin-Bernstein
    ---------------------------------------------------*/
    // Page size.
    private static final int B = 1001 << 6;
    // Wheel modulus for sharding between binary quadratic forms.
    private static final int M = 60;

    // Squares of primes 5 < q < 240
    private static final int[] qqtab = new int[] {
        49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809,
        3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409, 10201, 10609, 11449, 11881,
        12769, 16129, 17161, 18769, 19321, 22201, 22801, 24649, 26569, 27889, 29929, 32041, 32761,
        36481, 37249, 38809, 39601, 44521, 49729, 51529, 52441, 54289, 57121
    };
    // If a_i == q^{-2} (mod 60) is the reciprocal of qq[i], qq60tab[i] = qq[i] + (1 - a_i * qq[i]) / 60
    private static int[] qq60tab = new int[] {
        9, 119, 31, 53, 355, 97, 827, 945, 251, 1653, 339, 405, 515,
        3423, 3659, 823, 4957, 977, 6137, 1263, 7789, 1725, 10031, 1945, 2099, 11683,
        2341, 2957, 16875, 3441, 18999, 21831, 22421, 4519, 4871, 5113, 5487, 31507, 32215,
        35873, 6829, 7115, 38941, 43779, 9117, 9447, 51567, 9953, 56169
    };

    /**
     * Produces a set of parameters for traceElliptic to find solutions to ax^2 + cy^2 == d (mod M).
     * @param d The target residue.
     * @param a Binary quadratic form parameter.
     * @param c Binary quadratic form parameter.
     */
    private static List<int[]> initElliptic(final int[] invTotients, final int d, final int a, final int c) {
        List<int[]> rv = new ArrayList<int[]>();

        // The basic idea is that we maintain an invariant of the form
        //     M k = a x^2 + c y^2 - d
        // Therefore we increment x in steps F such that
        //     a((x + F)^2 - x^2) == 0 (mod M)
        // and similarly for y in steps G.
        int F = computeIncrement(a, M), G = computeIncrement(c, M);
        for (int f = 1; f <= F; f++) {
            for (int g = 1; g <= G; g++) {
                if ((a*f*f + c*g*g - d) % M == 0) {
                    rv.add(new int[] { invTotients[d], (2*f + F)*a*F/M, (2*g + G)*c*G/M, (a*f*f + c*g*g - d)/M, 2*a*F*F/M, 2*c*G*G/M });
                }
            }
        }

        return rv;
    }

    private static int computeIncrement(int a, int M) {
        // Find smallest F such that M | 2aF and M | aF^2
        int l = M / gcd(M, 2 * a);
        for (int F = l; true; F += l) {
            if (a*F*F % M == 0) return F;
        }
    }

    public static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }

        return a;
    }

    // NB This is generalised somewhat from primegen's implementation.
    private static void traceElliptic(final long[] buf, int x, int y, long start, final int cF2, final int cG2, final int[] Lmodqq, final int d) {
        // Bring the annular segment into the range of ints.
        start += 1000000000;
        while (start < 0) {
            start += x;
            x += cF2;
        }
        start -= 1000000000;
        int i = (int)start;

        while (i < B) {
            i += x;
            x += cF2;
        }

        while (true) {
            x -= cF2;
            if (x <= cF2 >> 1) {
                // It makes no sense that doing this in here should perform well, but empirically it does much better than
                // only eliminating the squares once.
                squarefreeTiny(buf, Lmodqq, d);
                return;
            }
            i -= x;

            while (i < 0) {
                i += y;
                y += cG2;
            }

            int i0 = i, y0 = y;
            while (i < B) {
                buf[i >> 6] ^= 1L << i;
                i += y;
                y += cG2;
            }
            i = i0;
            y = y0;
        }
    }

    // This only handles 3x^2 - y^2, and is closer to a direct port of primegen.
    private static void traceHyperbolic(final long[] a, int x, int y, long start, final int[] Lmodqq, final int d) {
        x += 5;
        y += 15;

        // Bring the segment into the range of ints.
        start += 1000000000;
        while (start < 0) {
            start += x;
            x += 10;
        }
        start -= 1000000000;
        int i = (int)start;

        while (i < 0) {
            i += x;
            x += 10;
        }

        while (true) {
            x += 10;
            while (i >= B) {
                if (x <= y) {
                    squarefreeTiny(a, Lmodqq, d);
                    return;
                }
                i -= y;
                y += 30;
            }

            int i0 = i, y0 = y;
            while (i >= 0 && y < x) {
                a[i >> 6] ^= 1L << i;
                i -= y;
                y += 30;
            }
            i = i0 + x - 10;
            y = y0;
        }
    }

    private static void squarefreeTiny(final long[] a, final int[] Lmodqq, final int d) {
        for (int j = 0; j < qqtab.length; ++j) {
            int qq = qqtab[j];
            int k = qq - 1 - ((Lmodqq[j] + qq60tab[j] * d - 1) % qq);
            while (k < B) {
                a[k >> 6] |= 1L << k;
                k += qq;
            }
        }
    }

    private static void squarefreeMid(long[][] buf, int[] invTotients, final long base, int q, int dqq, int di) {
        int qq = q * q;
        q = M * q + (M * M / 4);

        while (qq < M * B) {
            int i = qq - (int)(base % qq);
            if ((i & 1) == 0) i += qq;

            if (i < M * B) {
                int qqhigh = ((qq / M) << 1) + dqq;
                int ilow = i % M;
                int ihigh = i / M;
                while (ihigh < B) {
                    int n = invTotients[ilow];
                    if (n >= 0) buf[n][ihigh >> 6] |= 1L << ihigh;

                    ilow += di;
                    ihigh += qqhigh;
                    if (ilow >= M) {
                        ilow -= M;
                        ihigh += 1;
                    }
                }
            }

            qq += q;
            q += M * M / 2;
        }

        squarefreebig(buf, invTotients, base, q, qq);
    }

    private static void squarefreebig(long[][] buf, int[] invTotients, final long base, int q, long qq) {
        long bound = base + M * B;
        while (qq < bound) {
            long i = qq - (base % qq);
            if ((i & 1) == 0) i += qq;

            if (i < M * B) {
                int pos = (int)i;
                int n = invTotients[pos % M];
                if (n >= 0) {
                    int ihigh = pos / M;
                    buf[n][ihigh >> 6] |= 1L << ihigh;
                }
            }

            qq += q;
            q += M * M / 2;
        }
    }

    // The relevant totients of M - those which only have one forced prime factor.
    static final int[] totients = new int[] { 17, 23, 29, 47, 53, 59 };
    private static final int[] invTotients;
    // Parameters for tracing the hyperbolic BQF used for 59+60Z.
    private static final int[][] hyperbolic = new int[][] {
        {5, 1, 2, -1}, {5, 1, 8, -2}, {5, 1, 22, -9}, {5, 1, 28, -14}, {5, 4, 7, -1}, {5, 4, 13, -3}, {5, 4, 17, -5}, {5, 4, 23, -9},
        {5, 5, 4, 0}, {5, 5, 14, -3}, {5, 5, 16, -4}, {5, 5, 26, -11}, {5, 6, 7, 0}, {5, 6, 13, -2}, {5, 6, 17, -4}, {5, 6, 23, -8},
        {5, 9, 2, 3}, {5, 9, 8, 2}, {5, 9, 22, -5}, {5, 9, 28, -10}, {5, 10, 1, 4}, {5, 10, 11, 2}, {5, 10, 19, -2}, {5, 10, 29, -10}
    };

    // Parameters for tracing the elliptic BQFs used for all totients except 11 and 59.
    private static final int[][] elliptic;
    static {
        invTotients = new int[M];
        Arrays.fill(invTotients, -1);
        for (int i = 0; i < totients.length; i++) invTotients[totients[i]] = i;

        // Calculate the parameters for tracing the elliptic BQFs from a table of the BQF used for each totient.
        // E.g. for 17+60Z we use 5x^2 + 3y^2.
        int[][] bqfs = new int[][] {
            {17, 5, 3}, {23, 5, 3}, {29, 4, 1}, {47, 5, 3}, {53, 5, 3}
        };
        List<int[]> parmSets = new ArrayList<int[]>();
        for (int[] bqf : bqfs) parmSets.addAll(initElliptic(invTotients, bqf[0], bqf[1], bqf[2]));
        elliptic = parmSets.toArray(new int[0][]);
    }
}

Save as PPCG65876.java, compile as javac PPCG65876.java, and run as java -Xmx1G PPCG65876.


J, 8 5 bytes
Same as this, but uses a build-in for rationals.
Argument is {a0,a1,a2,a3,...} as a list of J extended precision rational numbers. Result is the fraction as a J extended precision rational number.
(+%)/

(+%) the plus-the-reciprocal-of
/ reduction over
Try it online!
-3 thanks to miles.


MATLAB, 237 bytes

function A=r(A);n=size(A,1);p=@(a,v)permute(a,[v,3]);k=n/8;v=1:2;while k>=1;b=mod(0:n-1,4*k)<2*k;x=find(b);y=find(~b);c=[k+1:n,1:k;n-k+1:n,1:n-k];A=p(A,v);c=c(3-v,:);A(x,:,:)=A(x,c(1,:),:);A(y,:,:)=A(y,c(2,:),:);A=p(A,v);k=k/2;v=3-v;end

Took a little bit of guess work as I did not understand the procedure from the specs, but with the help of the image it worked.


Sieve of Sundaram (for finding prime numbers)

Pyth, 23 bytes

2j@JSQmhyd-Jm+sdy*Fd^J2

Demonstration

Really just implements the algorithm as given.


MATL, 28 bytes

`jYb0&)YOd.5+wgU13L/- 15XODT

Try it online!


Non-compliant ><> answer

You wanted ><>, I give you ><> !

I believe the only sane way to do this in ><> is by copying the input in the codespace and letting the interpreter decide by itself if the input leads somewhere. Since ><> doesn't implement threading anymore, that leaves us with a big problem : if the input has a loop, we'll get stuck into it.

These considerations taken into account, I decided to make a solution compatible with ><> online interpreter so that it would be possible to assert if the interpreter is stuck in the input or just taking ages to do everything. I also had to add trailing lines to the code so the online interpreter shows the added code and doesn't crash when trying to write to it.

Oh and since I'm clearly disqualified by now, I didn't bother with golfing the code.

Without further ado, the code in all its glory :

50i:0(?v   :"^"=?v:"v"=?v:">"=?v:"<"=?v:"/"=?v:"\"=?v:"|"=?v:"-"=?va=?v1+10.
>.!603f<         v"."~                                     <      <   >~1+010.
>.!01+1p}:$}:}v! <      <      <      <      <      <
  ;oooo"true" <<
              ^

To use it, copy it in the online interpreter, add enough trailing lines to handle your input, submit the code, give it the input as ;-separated lines and enjoy the ride.

A few tests :

  With

+--------------------+
|>\/  this way >\/>  | this one ends here
| v^            \/   |
| v^   ^.^           |
| \/\         >v     |
| /\/         ^<     |
+--------------------+`

  Final codespace :

50i:0(?v   :"^"=?v:"v"=?v:">"=?v:"<"=?v:"/"=?v:"\"=?v:"|"=?v:"-"=?va=?v1+10.
>.!603f<         v"."~                                     <      <   >~1+010.
>.!01+1p}:$}:}v! <      <      <      <      <      <
  ;oooo"true" <<
            ^
 ....................
.>\/           >\/>  .
. v^            \/   .
. v^   ^ ^           .
. \/\         >v     .
. /\/         ^<     .
 ....................

  Outputs "true" and stops.

  With

+--------+
|>>\ This|
|\\   is |
|  \\ a  |
| \ /trap|
+--------+

  Final codespace :

50i:0(?v   :"^"=?v:"v"=?v:">"=?v:"<"=?v:"/"=?v:"\"=?v:"|"=?v:"-"=?va=?v1+10.
>.!603f<         v"."~                                     <      <   >~1+010.
>.!01+1p}:$}:}v! <      <      <      <      <      <
  ;oooo"true" <<
            ^
 ........
.>>\     .
.\\      .
.  \\    .
. \ /    .
 ........

  Loops forever.


R, 7 bytes

fivenum

Try it online!

Obvious cheeky answer. ;-)

Interestingly, fivenum(x) is not equivalent to summary(x) even when x is numeric, as the quantiles are computed differently: fivenum averages at discontinuities, whereas summary interpolates. You can force summary to behave like fivenum with the option quantile.type, but this is still longer than

R, 51 bytes

function(x)quantile(x,(0:4)/4,t=2+5*!sum(!!x)%%4-3)

Try it online!

which computes the quantiles of order 0 (min), 0.25 (Q1), 0.5 (median), 0.75 (Q3) and 1 (max). The t=2 specifies how quantiles are defined: there are 9 possible types, and the challenge definition corresponds to type 2 in most cases, and to type 7 when \$n\equiv 3\pmod 4\$. Honestly, this choice of a definition of quantiles is a bit weird.

Note that the source code of the fivenum built-in is very different (and much longer).


Languages with built-in solutions

based on this proposal by xnor

APL (Dyalog Unicode), 1 byte

⍉

Try it online!

J, 2 bytes

|:

Try it online!

R, 5 bytes

aperm

Try it online!

Octave/MATLAB, 8 bytes

@permute

Try it online!

Wolfram Language (Mathematica), 9 bytes

Transpose

Try it online!

Julia, 11 bytes

permutedims

Try it online!


Exploit nested predicates to create new variables

Brachylog has lots of special syntax cases to make its two special variables, ? (input / left parameter) and . (output / right parameter), terser to use. This means that if you don't need to access your predicate's ? and ., but do need to use variables, you can often save bytes via creating a nested predicate to use its ? and ..

As a simple example, consider a program that looks like this:

… A … ∧A … B … B …

This is a pretty common shape for a longer program; after all, there are lots of gaps that could contain anything. Suppose we have no need for ? or . inside the centre three gaps. Then we could rewrite it like this:

… { … & … . … } …

Here, the nested predicate's ? is serving the role of A, and its . is serving the role of B. We can observe that this is a byte shorter than the original code; changing AABB to {?.} has no change in terms of bytes, but this allowed us to simplify ∧? to the abbreviation &.

A related trick is to change

∧. … ?∧

to

~{ … }

(which is one byte shorter), although note that it's nearly always cheaper to get the caller to exchange the arguments instead (unless the predicate is called from at least three different places in the program, which is rare in Brachylog).


C: 116 102 99 95 92 90

s(n){for(int c=-n,r=c;r<=n;c++)putchar(c>n?c=-c,r++,10:c?r?c-r?c+r?32:47:92:45:r?124:79);}

I think that I am getting fairly close to a minimal solution using this approach, but I can't stop feeling that there is a much better approach in C. Ungolfed:

void s(int n) {
  for(
    int c = -n, r = c;
    r <= n;
    c++
  )
    putchar(
      c > n
        ? c = -c, r++, '\n'
        : c
          ? r
            ? c - r
              ? c + r
                ? ' '
                : '/'
              : '\\'
            : '-'
          : r
            ? '|'
            : 'O'
    );
}


Don't Use Print...Use the Formatted Output

Here's an example fizzbuzz:

For(i=1,i<101,i++,s="";If(Mod(i,5)==0,s=s<>"Fizz");If(Mod(i,3)==0,s=s<>"Buzz");If(Mod(i,5)*Mod(i,3)!=0,s=s<>ToString(i));Print(s))

Now, this is alright, but it can be improved:

For(i=1,i<101,i++,If(Mod(i,5)==0,s=s<>"Fizz");If(Mod(i,3)==0,s=s<>"Buzz");If(Mod(i,5)*Mod(i,3)!=0,s=s<>ToString(i));s=s<>"\n");s

Sure, it's only two bytes shorter, but hey, it's two bytes shorter.

Just put all the output into a string and tack a ;<variable_name> onto the end and you'll have a shorter program (usually).


Pyth, 27 24 bytes

uf!f/h-FY3.:metsd`T2hGQ0

Demonstration.

Improvements to the original:

Using metd, instead of .r ... _UJ: 2 less bytes. 1 direct, 1 for not having to use J.
Using s and `T instead of JT10: 1 less byte.

We start with the string representation of a number: `T.

Then, we convert the string to a list of digits, and rotate the digits digits backwards by one, (9876543210) with metsd. Then, we take the 2 element subsequences with .: ... 2. These subsequences are filtered on /h-FY3. This expression corresponds to ((a-b)+1)/3, which is zero if and only if the difference between a and b is at most 1. Thus, the filtered list will be empty if and only if the number is keyboard friendly. With !, the result is true only if the number is keyboard friendly.

f ... hG filters upwards from G+1 until the result is true, giving the first keyboard friendly number at G+1 or above. u ... Q0 applies this function to its own output Q times, starting from 0, where Q is the input. This gives the Qth Keyboard Friendly Number, as desired.


Python 3, 109

This was certainly a deceptively hard challenge. There were many times writing the code that I found myself questioning my basic geometry abilities. That being said, I'm pretty happy with the result. I put no effort in to coming up with a complex algorithm for placing the triangles, and instead my code just blunders through always placing the smallest it can find. I hope I can improve this later on, or my answer will spurn others to find a better algorithm! All in all, a very fun problem, and it produces some interesting pictures.

Here's the code:

import time
import math

W = int(input("Enter W: "))
H = int(input("Enter H: "))

middle_x = math.floor(W/2)
middle_y = math.floor(H/2)

sides = [ # each side is in the format [length, [x0, y0], [x1, y1]]
    [3,[middle_x,middle_y],[middle_x+3,middle_y]],
    [4,[middle_x,middle_y],[middle_x,middle_y+4]],
    [5,[middle_x+3,middle_y],[middle_x,middle_y+4]]
    ]

triangles = [[0,1,2]] # each triangle is in the format [a, b, c] where a, b and c are the indexes of sides

used_triangles = [[3,4,5]] # a list of used Pythagorean triples, where lengths are ordered (a < b < c)

max_bounds_length = math.sqrt(W**2 + H**2)

def check_if_pyth_triple(a,b): # accepts two lists of the form [l, [x0,y0], [x1,y1]] defining two line segments
    # returns 0 if there are no triples, 1 if there is a triple with a right angle on a,
    # and 2 if there is a triple with the right angle opposite a
    c = math.sqrt(a[0]**2 + b[0]**2)
    if c.is_integer():
        if not sorted([a[0], b[0], c]) in used_triangles:
            return 1
        return 0
    else:
        if a[0] > b[0]:
            c = math.sqrt(a[0]**2 - b[0]**2)
            if c.is_integer() and not sorted([a[0], b[0], c]) in used_triangles:
                return 2
        return 0

def check_if_out_of_bounds(p):
    out = False
    if p[0] < 0 or p[0] > W:
        out = True
    if p[1] < 0 or p[1] > H:
        out = True
    return out

def in_between(a,b,c):
    maxi = max(a,c)
    mini = min(a,c)
    return mini < b < maxi

def sides_intersect(AB,CD): # accepts two lists of the form [l, [x0,y0], [x1,y1]] defining two line segments
    # doesn't count overlapping lines
    A = AB[1]
    B = AB[2]
    C = CD[1]
    D = CD[2]

    if A[0] == B[0]: # AB is vertical
        if C[0] == D[0]: # CD is vertical
            return False
        else:
            m1 = (C[1] - D[1])/(C[0] - D[0]) # slope of CD
            y = m1*(A[0] - C[0]) + C[1] # the y value of CD at AB's x value
            return in_between(A[1], y, B[1]) and in_between(C[0], A[0], D[0])
    else:
        m0 = (A[1] - B[1])/(A[0] - B[0]) # slope of AB
        if C[0] == D[0]: # CD is vertical
            y = m0*(C[0] - A[0]) + A[1] # the y value of CD at AB's x value
            return in_between(C[1], y, D[1]) and in_between(A[0],C[0],B[0])
        else:
            m1 = (C[1] - D[1])/(C[0] - D[0]) # slope of CD
            if m0 == m1:
                return False
            else:
                x = (m0*A[0] - m1*C[0] - A[1] + C[1])/(m0 - m1)
                return in_between(A[0], x, B[0]) and in_between(C[0], x, D[0])

def check_all_sides(b,triangle):
    no_intersections = True
    for side in sides:
        if sides_intersect(side, b):
            no_intersections = False
            break

    return no_intersections

def check_point_still_has_room(A): # This function is needed for the weird case when all 2pi degrees
    # around a point are filled by triangles, but you could fit in a small triangle into another one
    # already built around the point. Doing this won't cause sides_intersect() to detect it because
    # the sides will all be parallel. Crazy stuff.
    connecting_sides = []
    for side in sides:
        if A in side:
            connecting_sides.append(side)

    match_count = 0
    slopes = []
    for side in connecting_sides:
        B = side[1]
        if A == B:
            B = side[2]
        if not A[0] == B[0]:
            slope = round((A[1]-B[1])/(A[0]-B[0]),4)
        else:
            if A[1] < B[1]:
                slope = "infinity"
            else:
                slope = "neg_infinity"
        if slope in slopes:
            match_count -= 1
        else:
            slopes.append(slope)
            match_count += 1

    return match_count != 0

def construct_b(a,b,pyth_triple_info,straight_b_direction,bent_b_direction):
    # this function finds the correct third point of the triangle given a and the length of b
    # pyth_triple_info determines if a is a leg or the hypotenuse
    # the b_directions determine on which side of a the triangle should be formed
    a_p = 2 # this is the index of the point in a that is not the shared point with b
    if a[1] != b[1]:
        a_p = 1

    vx = a[a_p][0] - b[1][0] # v is our vector, and these are the coordinates, adjusted so that
    vy = a[a_p][1] - b[1][1] # the shared point is the origin

    if pyth_triple_info == 1:
        # because the dot product of orthogonal vectors is zero, we can use that and the Pythagorean formula
        # to get this simple formula for generating the coordinates of b's second point
        if vy == 0:
            x = 0
            y = b[0]
        else:
            x = b[0]/math.sqrt(1+((-vx/vy)**2)) # b[0] is the desired length
            y = -vx*x/vy

        x = x*straight_b_direction # since the vector is orthagonal, if we want to reverse the direction,
        y = y*straight_b_direction # it just means finding the mirror point

    elif pyth_triple_info == 2: # this finds the intersection of the two circles of radii b[0] and c
        # around a's endpoints, which is the third point of the triangle if a is the hypotenuse
        c = math.sqrt(a[0]**2 - b[0]**2)
        D = a[0]
        A = (b[0]**2 - c**2 + D**2 ) / (2*D)
        h = math.sqrt(b[0]**2 - A**2)
        x2 = vx*(A/D)
        y2 = vy*(A/D)
        x = x2 + h*vy/D
        y = y2 - h*vx/D

        if bent_b_direction == -1: # this constitutes reflection of the vector (-x,-y) around the normal vector n,
            # which accounts for finding the triangle on the opposite side of a
            dx = -x
            dy = -y
            v_length = math.sqrt(vx**2 + vy**2)
            nx = vx/v_length
            ny = vy/v_length

            d_dot_n = dx*nx + dy*ny

            x = dx - 2*d_dot_n*nx
            y = dy - 2*d_dot_n*ny

    x = x + b[1][0] # adjust back to the original frame
    y = y + b[1][1]

    return [x,y]

def construct_triangle(side_index):
    a = sides[side_index] # a is the base of the triangle
    a_p = 1
    b = [1, a[a_p], []] # side b, c is hypotenuse

    for index, triangle in enumerate(triangles):
        if side_index in triangle:
            triangle_index = index
            break

    triangle = list(triangles[triangle_index])
    triangle.remove(side_index)

    add_tri = False

    straight_b = construct_b(a,b,1,1,1)

    bent_b = construct_b(a,b,2,1,1)

    A = sides[triangle[0]][1]
    if A in a:
        A = sides[triangle[0]][2]

    Ax = A[0] - b[1][0] # adjusting A so that it's a vector
    Ay = A[1] - b[1][1]

    # these are for determining if construct_b() is going to the correct side
    triangle_on_side = (a[2][0]-a[1][0])*(A[1]-a[1][1]) - (a[2][1]-a[1][1])*(A[0]-a[1][0])
    straight_b_on_side = (a[2][0]-a[1][0])*(straight_b[1]-a[1][1]) - (a[2][1]-a[1][1])*(straight_b[0]-a[1][0])
    bent_b_on_side = (a[2][0]-a[1][0])*(bent_b[1]-a[1][1]) - (a[2][1]-a[1][1])*(bent_b[0]-a[1][0])

    straight_b_direction = 1
    if (triangle_on_side > 0 and straight_b_on_side > 0) or (triangle_on_side < 0 and straight_b_on_side < 0):
        straight_b_direction = -1

    bent_b_direction = 1
    if (triangle_on_side > 0 and bent_b_on_side > 0) or (triangle_on_side < 0 and bent_b_on_side < 0):
        bent_b_direction = -1

    a_ps = []
    for x in [1,2]:
        if check_point_still_has_room(a[x]): # here we check for that weird exception
            a_ps.append(x)

    while True:
        out_of_bounds = False
        if b[0] > max_bounds_length:
            break

        pyth_triple_info = check_if_pyth_triple(a,b)

        for a_p in a_ps:
            if a_p == 1: # this accounts for the change in direction when switching a's points
                new_bent_b_direction = bent_b_direction
            else:
                new_bent_b_direction = -bent_b_direction

            b[1] = a[a_p]
            if pyth_triple_info > 0:
                b[2] = construct_b(a,b,pyth_triple_info,straight_b_direction,new_bent_b_direction)

                if check_if_out_of_bounds(b[2]): # here is the check to make sure we don't go out of bounds
                    out_of_bounds = True
                    break

                if check_all_sides(b,triangle):
                    if pyth_triple_info == 1:
                        c = [math.sqrt(a[0]**2 + b[0]**2), a[3-a_p], b[2]]
                    else:
                        c = [math.sqrt(a[0]**2 - b[0]**2), a[3-a_p], b[2]]

                    if check_all_sides(c,triangle):
                        add_tri = True
                        break

        if out_of_bounds or add_tri:
            break

        b[0] += 1 # increment the length of b every time the loop goes through

    if add_tri: # this adds a new triangle
        sides.append(b)
        sides.append(c)
        sides_len = len(sides)
        triangles.append([side_index, sides_len - 2, sides_len - 1])
        used_triangles.append(sorted([a[0], b[0], c[0]])) # so we don't use the same triangle again

def build_all_triangles(): # this iterates through every side to see if a new triangle can be constructed
    # this is probably where real optimization would take place so more optimal triangles are placed first
    t0 = time.clock()

    index = 0
    while index < len(sides):
        construct_triangle(index)
        index += 1

    t1 = time.clock()

    triangles_points = [] # this is all for printing points
    for triangle in triangles:
        point_list = []
        for x in [1,2]:
            for side_index in triangle:
                point = sides[side_index][x]
                if not point in point_list:
                    point_list.append(point)
        triangles_points.append(point_list)

    for triangle in triangles_points:
        print(triangle)

    print(len(triangles), "triangles placed in", round(t1-t0,3), "seconds.")

def matplotlib_graph(): # this displays the triangles with matplotlib
    import pylab as pl
    import matplotlib.pyplot as plt
    from matplotlib import collections as mc

    lines = []
    for side in sides:
        lines.append([side[1],side[2]])

    lc = mc.LineCollection(lines)
    fig, ax = pl.subplots()
    ax.add_collection(lc)
    ax.autoscale()
    ax.margins(0.1)
    plt.show()

build_all_triangles()

Here's a graph of the output for W = 1000 and H = 1000 with 109 triangles:

Here is W = 10000 and H = 10000 with 724 triangles:

Call the matplotlib_graph() function after build_all_triangles() to graph the triangles.

I think the code runs reasonably fast: at W = 1000 and H = 1000 it takes 0.66 seconds, and at W = 10000 and H = 10000 it takes 45 seconds using my crappy laptop.


List of first n prime numbers most efficiently and in shortest code

Python (129 chars, O(n*log log n), score of 203.948)

I'd say the Sieve of Eratosthenes is the way to go. Very simple and relatively fast.

N=15485864
a=[1]*N
x=xrange
for i in x(2,3936):
 if a[i]:
  for j in x(i*i,N,i):a[j]=0
print [i for i in x(len(a))if a[i]==1][2:]

Improved code from before.

Python (191 156 152 chars, O(n*log log n)(?), score of 252.620(?))

I cannot at all calculate complexity, this is the best approximation I can give.

from math import log as l
n=input()
N=n*int(l(n)+l(l(n)))
a=range(2,N)
for i in range(int(n**.5)+1):
 a=filter(lambda x:x%a[i] or x==a[i],a)
print a[:n]

n*int(l(n)+l(l(n))) is the top boundary of the nth prime number.


JavaScript (Node.js), 50 bytes

f=(n,p=1e3)=>n<p?(n+p+'').slice(1):'#'+f(n-p,p/10)

Try it online!

TIO was based on Arnauld's answer. Show  as #.


Japt, 15 bytes

OvUr" +%d"_rS'(

Test it online!

How it works

This challenge was practically made for Japt. I shall attempt to explain how:

Japt is basically a shortened version of JavaScript. In fact, after making some changes to the code ("transpiling" to JS), it is evaluated directly as JavaScript. What comes in handy here is that a space in Japt becomes ) in JavaScript (a feature I occasionally regret adding, as it makes it hard to write "ungolfed" Japt code), and missing parentheses are automatically added.

What this all means for this challenge is that we can obtain the correct result simply by changing all spaces after an operator (before a number) to left-parentheses:

5*6  +  7*8   -3  *5    Original string
5*6  +((7*8   -3  *5    Japt code that evaluates to the correct number

When transpiled to JS, the changes mentioned above are made, which results in this:

     5*6  +((7*8   -3  *5    Japt code
(((((5*6))+((7*8)))-3))*5    transpiled JS code

The JS code is then evaluated, which gives the expected result.

OvUr" +%d"_rS'(    Implicit: U = input string
  Ur" +%d"         Replace each match of / +\d/ in U with
          _rS'(      the match with each Space replaced with a '('.
Ov                 Evaluate the result as Japt.
                   Implicit: output result of last expression


Convert English to a number without built-ins or libraries

C, 160 bytes

g(char*s){char i=1,r=0,*p="k^[#>Pcx.yI<7CZpVgmH:o]sYK$2";for(;*s^'-'&&*s;r+=*s++|9);r=r%45+77;for(;*p!=r;p++,i++);return((*s^'-')?0:g(s+1))+(i<21?i:10*(i-18));}

Test it

int main ()
{
    char* w[] = {"", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen", "twenty", "twenty-one", "twenty-two", "twenty-three", "twenty-four", "twenty-five", "twenty-six", "twenty-seven", "twenty-eight", "twenty-nine", "thirty", "thirty-one", "thirty-two", "thirty-three", "thirty-four", "thirty-five", "thirty-six", "thirty-seven", "thirty-eight", "thirty-nine", "forty", "forty-one", "forty-two", "forty-three", "forty-four", "forty-five", "forty-six", "forty-seven", "forty-eight", "forty-nine", "fifty", "fifty-one", "fifty-two", "fifty-three", "fifty-four", "fifty-five", "fifty-six", "fifty-seven", "fifty-eight", "fifty-nine", "sixty", "sixty-one", "sixty-two", "sixty-three", "sixty-four", "sixty-five", "sixty-six", "sixty-seven", "sixty-eight", "sixty-nine", "seventy", "seventy-one", "seventy-two", "seventy-three", "seventy-four", "seventy-five", "seventy-six", "seventy-seven", "seventy-eight", "seventy-nine", "eighty", "eighty-one", "eighty-two", "eighty-three", "eighty-four", "eighty-five", "eighty-six", "eighty-seven", "eighty-eight", "eighty-nine", "ninety", "ninety-one", "ninety-two", "ninety-three", "ninety-four", "ninety-five", "ninety-six", "ninety-seven", "ninety-eight", "ninety-nine", "one hundred"};

    int n;
    for (n = 1; n <= 100; n++)
    {
        printf ("%s -> %d\n", w[n], g(w[n]));
        if (n != g(w[n]))
        {
            printf ("Error at n = %d", n);
            return 1;
        }
    }
    return 0;
}

How it works

After some attempts, I found a function that maps the "exceptional" numbers one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety, one hundred, to the printable ASCII characters k, ., [, <, *, , c, K, w, y, e, (, S, _, -, C, ), 7, =, 4, &, o, ], s, Y, g, m, N, respectively.

This function is:

char hash (char* s)
{
    char r = 0;

    while (*s)
    {
        r += *s|9;
        s++;
    }

    return r%45+77;
}

The golfed program computes the hash function of the input until it reaches the end of the string or the character -. Then it searches the hash in the string k.[<* cKwye(S_-C)7=4&o]sYgmN and determines the corresponding number. If the end of the input string was reached the number is returned, if instead a - was reached, then it is returned the number plus the result of the golfed program applied to the rest of the input string.


Javascript function challenge add(1,2) and add(1)(2) both should return 3

JavaScript (as asked)
This is a "correct" way to do it but hardly the golfiest way. It's unclear if you're asking for shortest code (the question looks like it will be closed soon anyway.)
function add(a, b) {
    if(typeof b === "undefined")
        return function(c) { return a + c }
    return a + b
}


Bijection between binary strings and pairs thereof

Python, 183

Bijection is cached on disk.

x=raw_input()
try:d=eval(open('d').read())
except:d={'':'','1 ':'1 '}
t='1 '*not' 'in x
if x not in d:
 while t in d:t+=`(id(t)/9)%2`
 d[t]=x;d[x]=t
 open(*'dw').write(`d`)
print d[x]

edit: Oops, looks like this isn't the first smartassed answer.  Mine's consistent between runs!


Create a multi-level 5x5x5 Labyrinth with only one solution

C++ C, about 1000 670 643 395 297 248 chars

Sample output:

00111,10011,10111,00110,11000,
11001,01010,00100,11011,10101,
10111,10101,10001,01010,00101,
11001,11110,11100,11110,10101,
11100,10010,11001,10101,00000,

How it works: The program uses Brownian Motion to generate solutions. The start point is set. Then, a random point is selected and repeatedly moved randomly until it touches one and only one point on the start branch. The point is then set, and if it also touches the end point, the program exits and the matrix displayed. Since no point can join two branches, there is only one path through the labyrinth. The program uses the rand function, and a command line integer argument as the seed, so with a sufficient rand function it should be possible to eventually generate all valid labyrinths (this algorithm will not create unconnected areas however, so it won't generate all possible labyrinths).

Brownian motion was dropped since it turned out to be unneeded and it's removal simplifies the code significantly. I do think it made nicer labyrinths though. Likewise, the seed argument was dropped, since requiring a stateless random number generator makes more sense to me than a 128-bit seed.

It is possible for the program to get stuck in an infinite loop, since it is possible for situations where any point added to the branches would create multiple paths. This is fixable, but I think that it is rare enough to not be a concern for code golf.

#define M m[*p+1][p[1]][p[2]]
#define F(a,b)for(p[a]=5;p[a]--;putchar(b))
#define f for(i=3;i--;p[i]
p[]={4,4,4},h[3],m[7][6][6]={1};
main(i){
    for(M=2;h[1]^1||(M=1)^h[2];){
        f=rand()%5)
            h[i]=0;
        f++)
            p[i]++,
            h[M]++,
            p[i]-=2,
            h[M]++;
    }
    F(0,10)
        F(1,44)
            F(2,48+!M);
}

I've added newlines and indentation to the displayed code for readability.


Dyalog APL, 10 bytes
(5?69),?26

Dyadic ? is ⍺ distinct random numbers in [1,⍵], and monadic ? is a single random number.
Try it here.


Smallest Hamming distance to a palindrome containing a substring

Pyth, 19 bytes

hSmsnVQd/#z_I#^+Qzl

Demonstration

Extreme brute force approach. Generate all strings of the appropriate length with characters in either string, filter for palindromes and for containing the second input, map to hamming distance from first string, output smallest.

Explanation:

hSmsnVQd/#z_I#^+Qzl
hSmsnVQd/#z_I#^+QzlQ     Variable introduction
                         Q = string A, z = string B.
               +Qz       Concatenate A and B
              ^   lQ     Form every string of length equal to len(A)using
                         characters from the concatenation.
             #           Filter on
           _I            Invariance under reversal (palindrome)
         #               Filter on
        / z              Nonzero occurences of B
  m                      Map to
    nV                   !=, vectorized over
      Qd                 A and the map input
   s                     Sum (gives the hamming weight)
hS                       Min


Haskell, 94 bytes

An anonymous function taking and returning a list of Strings.

Use as (cycle[t.r,r.t,r.t,r.t]?)["123", "456", "789"].

(cycle[t.r,r.t,r.t,r.t]?)
(g:h)?(a:b)=g$a:h?t(r b)
_?a=a
r=reverse;t=zipWith(:)`foldr`repeat[]

Try it online!

How it works

r is reverse. t is one byte shorter than importing Data.List.transpose. t.r rotates a list of lists 90 degrees clockwise, and r.t rotates it counterclockwise.
The operator ? takes two arguments, a list of functions and a matrix as a list of strings.

An empty matrix is just returned.
Otherwise, ? strips the first function f off the list of functions, and the first line a off the matrix.
Then it rotates the remainder b of the matrix clockwise, and recurses with that and the remaining functions. This gradually strips the matrix from the outside in, one ring each four steps.
Then it prepends the original line a to the result, and applies the function f to it to adjust the orientation of the matrix.

The anonymous function calls ? with the input matrix as a list of strings, and an infinite list of functions, which repeats cyclically every four steps.

For most of the steps the function is counterclockwise rotation, which undoes the implicit clockwise rotation done by ? when recursing.
However, the first step and every fourth step afterwards is instead clockwise rotation.

This function is applied when a ring of the matrix is complete, causing each ring to be 180 degrees rotated with respect to the next one.
By luck, this is also the correct transformation to apply to the final, completed matrix to get the final result.


Inherit from class with inaccessible abstract members and all constructors inaccessible

Well, I have either to call a base constructor (which is not accessible) or an other constructor in the same class.

public abstract class Class1 : System.Globalization.EastAsianLunisolarCalendar {
    private Class1() : this(1) {}
    private Class1(int i) : this() {}
}

So let's call the constructors recursive. Not very useful, but who cares?


Connecting the Dots: Counting n²-gons in the n×n Grid

Python 3 + Z3, N=5
Not 100% sure if this is correct. Basically a standard SAT/SMT coding of the Hamiltonian cycle problem, with additional clauses to block intersecting diagonals and collinear segments. Each time a solution is found all of its distinct rotations/flips are blocked. I've run it up to N=6 (2120 solutions found), which took 30 minutes.
Edit: I just realized that this only allows edges between adjacent grid points, but this restriction wasn't intended by the challenge. Oh well, I'll leave it up for now.

import collections
import heapq
import itertools
import math
import random
import time
import sys
import z3

show_paths = len(sys.argv) >= 2 and 'show' in sys.argv[1]

if show_paths:
    import numpy as np
    import pylab as plt
    from matplotlib import collections  as mc

    def show_path(path):
        lines = list(zip(path, path[1:] + path[:1]))
        c = np.array([(1, 0, 0, 1), (0, 1, 0, 1), (0, 0, 1, 1)])
        lc = mc.LineCollection(lines, colors=c, linewidths=2)
        fig, ax = plt.subplots()
        ax.add_collection(lc)
        ax.autoscale()
        ax.margins(0.1)
        plt.show()

def compute_min_distances(C, distance_matrix, starting_points, banned):
    min_distances = collections.defaultdict(lambda: float('inf'))
    open_set = []
    for i in starting_points:
        state = (i, C[i])
        min_distances[state] = 1
        open_set.append((1, state))
    while open_set:
        d, state = open_set.pop()
        if d > min_distances[state]:
            continue
        i, delta = state
        x0, y0 = c0 = C[i]
        for j, _ in distance_matrix[i]:
            if j in banned:
                continue
            x1, y1 = c1 = C[j]
            delta1 = (x1 - x0, y1 - y0)
            if delta in (delta1, (x0 - x1, y0 - y1)):
                continue
            state = (j, delta1)
            if d + 1 < min_distances[state]:
                min_distances[state] = d + 1
                heapq.heappush(open_set, (d + 1, state))
    distance_array = [float('inf') for _ in distance_matrix]
    distance_array[0] = 0
    for (i, _), d in min_distances.items():
        distance_array[i] = min(distance_array[i], d)
    return distance_array

def point_orientations(p, n):
    for (x, y) in (p, p[::-1]):
        for x1 in (x, n - 1 - x):
            for y1 in (y, n - 1 - y):
                yield (x1, y1)

def path_orientations(path, n):
    orientations = list(zip(*map(lambda p: point_orientations(p, n), path)))
    for o in orientations:
        i = o.index((0, 0))
        if o[i - 1] == (0, 1):
            o = o[::-1]
            i = (len(o) - 1) - i
        if o[(i + 1) % len(o)] != (0, 1):
            continue
        yield o[i:] + o[:i]

start_time = time.time()
for N in itertools.count(2):
    print("starting n = %d..." % N)
    solver = z3.Solver()
    C = [(x, y) for x in range(N) for y in range(N)]
    C_inv = {c : i for i, c in enumerate(C)}
    bit_width = math.ceil(math.log(N * N + 1, 2))
    P = [z3.BitVec('P_%d' % i, bit_width) for i in range(N * N)]
    V = [z3.BitVec('V_%d' % i, bit_width) for i in range(N * N)]
    for v in V:
        solver.add(z3.ULT(v, N * N))
    A = [[] for _ in range(N * N)]
    for i, (x, y) in enumerate(C):
        for dx, dy in itertools.product(range(-1, 2), repeat=2):
            if not (dx or dy):
                continue
            try:
                A[i].append(C_inv[(x + dx, y + dy)])
            except KeyError:
                pass
    H = [[(j, z3.Bool('H_%d_%d' % (i, j))) for j in A[i]] for i in range(N * N)]
    start = C_inv[(0, 1)]
    min_distances = compute_min_distances(C, H, [start], {0})
    end0, end1 = C_inv[(1, 0)], C_inv[(1, 1)]
    min_distances_rev = compute_min_distances(C, H, [end0, end1], {0, start})
    for i, (d0, d1) in enumerate(zip(min_distances, min_distances_rev)):
        if i not in (0, start):
            solver.add(z3.UGE(P[i], d0))
            solver.add(z3.ULE(P[i], N * N - d1))
    H_t = [[] for _ in range(N * N)]
    for i, row in enumerate(H):
        x0, y0 = C[i]
        for j, v in row:
            H_t[j].append(v)
            if i == 0:
                e = P[j] == 1
            elif j == 0:
                e = P[i] == (N * N - 1)
            else:
                e = P[j] == (P[i] + 1)
            clauses = [V[i] == j, e]
            x1, y1 = C[j]
            dy = y1 - y0
            dx = x1 - x0
            blocked = []
            if dy and dx:
                x_m = min(x0, x1)
                y_m = min(y0, y1)
                if dy == dx:
                    blocked.append(((x_m + 1, y_m), (x_m, y_m + 1)))
                else:
                    blocked.append(((x_m, y_m), (x_m + 1, y_m + 1)))
                blocked.append(blocked[-1][::-1])
            x2 = x1 + dx
            y2 = y1 + dy
            if all(0 <= c < N for c in (x2, y2)):
                blocked.append(((x1, y1), (x2, y2)))
            for (c0, c1) in blocked:
                k = C_inv[c0]
                l = C_inv[c1]
                clauses.append(z3.Not(next(w for m, w in H[k] if m == l)))
            solver.add(z3.Implies(v, z3.And(*clauses)))
    solver.add(P[0] == 0)
    solver.add(P[start] == 1)
    for row in H_t:
        solver.add(z3.PbEq([(v, 1) for v in row], 1))
    solutions = set()
    old_len = 0
    while solver.check() == z3.sat:
        model = solver.model()
        successors = [int(str(model.eval(v))) for v in V]
        path = [0]
        while len(path) < N * N:
            path.append(successors[path[-1]])
        path = tuple(C[i] for i in path)

        if show_paths:
            show_path(path)

        orientations = set(path_orientations(path, N))
        assert not any(reoriented in solutions for reoriented in orientations)
        solutions.add(path)
        for reoriented in orientations:
            successor = {}
            for p0, p1 in zip(reoriented, reoriented[1:] + reoriented[:1]):
                successor[C_inv[p0]] = C_inv[p1]
            solver.add(z3.Not(z3.And(*[v == successor[i] for i, v in enumerate(V)])))
        s = "%d solutions found so far... (%.1f seconds elapsed)" % (len(solutions), time.time() - start_time)
        sys.stdout.write(s + max(0, old_len - len(s)) * ' ' + '\r')
        sys.stdout.flush()
        old_len = len(s)
    sys.stdout.write(' ' * old_len + '\r')
    sys.stdout.flush()
    end_time = time.time()
    print("%d solution%s found for n = %d in %.2g seconds" % (len(solutions), 's' * (len(solutions) != 1), N, end_time - start_time))
    start_time = end_time


Compare two integers in C or C++ without comparison operators

90 bytes

If we can use stdio, why not use its formatting capabilities to perform comparison?

main(a,b){scanf("%d%d",&a,&b);snprintf(&a,2,"%d",b-a);a&=63;putchar(51-!(a-45)-!!(a-48));}

Assumes ASCII-compatible encoding and little-endianness.

72 bytes

Quotients are rounded toward zero but right-shifts are (in practice) "rounded down". That's a dead giveaway.

main(a,b){scanf("%d%d",&a,&b);a-=b;putchar(a?a|=1,a/2-(a>>1)?60:62:61);}

65 79 bytes

Another distinguishing property of negative numbers is that they produce negative modulo.
This one doesn't depend on integer representation at all; it even works on my 8-bit excess-127 toaster!
Oh, and since we can use conio, why not save two bytes with putch? Now, if I could only find my copy of TurboC...

main(a,b){scanf("%d%d",&a,&b);long long d=a;d-=b;putch(d?d|=1,d%2-1?60:62:61);}

EDIT: Handle large differences assuming long long is wider than int.


A function to take three integers and return a list of integers and alphabet-letters

PHP, 67 bytes

First of all, thanks for posting such a cool challenge! I really enjoyed solving it :) Now, here's my 67 byte solution:

<?for(;$i<=($p=$argv)[3];$i+=$p[2])echo$i%$p[1]?$i:chr($l++%26+97);

To run it:

php -n <filename> {a} {b} {c}

Or Try it online!

Here's the same solution ungolfed and with explanation comments:

$a      = $argv[1];
$b      = $argv[2];
$c      = $argv[3];
$letter = 'a';
for ($i = 0; $i <= $c; $i += $b) {
    if ($i % $a) { // If $i is divisible by $a, the modulo (%) operator will return a remainder of 0, which PHP sees as a falsey value.
        echo $i;
    } else {
        $letter++;
        $letter %= 26; // Wrap $letter around to `a` after it gets to `z`.
        echo chr($letter + 97); // Use PHP's chr function to get the character. 97 is the index of `a`. http://php.net/manual/en/function.chr.php
    }
}

I did a 60 byte solution, but it doesn't wrap around :(

<?for($l=a;$i<=($p=$argv)[3];$i+=$p[2])echo$i%$p[1]?$i:$l++;

Try it online!


Find the best period in which to have invested in a S&P500 index fund

Jelly, 9 bytes

PÐƤ⁹L¤ƤḋM

A dyadic link which yields a list of all the maximal starting 1-based indices.

Try it online!

(or ṡL}PÐƤ€ḋM)

How?

PÐƤ⁹L¤ƤḋM - Link: list of returns, list of nominal investments
      Ƥ   - for infixes of (the returns)...
          - ...of length:
     ¤    -               nilad followed by links as a nilad:
   ⁹      -                 chain's right argument (nominals)
    L     -                 length
          - ...do:
 ÐƤ       -        for post-fixes:
P         -          product
       ḋ  - dot-product (each) with (the nominals)
        M - maximal indices


C (gcc),  44  43 bytes

f(x,y,z){z=x>y?x:y;z=z*z-~(z%2?y-x:x-y)-z;}

Try it online!

The spiral has several "arms":

12345
22345
33345
44445
55555

The position \$(x, y)\$ is located on arm \$\max(x, y)\$ (assigned to variable z). Then, the largest number on arm \$n\$ is \$n^2\$, which alternates between being in the bottom left and top right position on the arm. Subtracting \$x\$ from \$y\$ gives the sequence \$-n+1, -n+2, \ldots, -1, 0, 1, \ldots, n-1, n-2\$ moving along arm \$n\$, so we choose the appropriate sign based on the parity of \$n\$, adjust by \$n-1\$ to get a sequence starting at 0, and subtract this value from \$n^2\$.

Thanks to Mr. Xcoder for saving a byte.


Python 2, 53 bytes

lambda s:sum(3-"MWCUNZS_AVO".find(c)/2*4%7for c in s)

Try it online!


Print the nth Fibonacci number containing the nth Fibonacci number!

Haskell, 85 84 bytes

EDIT:

-1 byte: Laikoni shortened l.
Typo (x>=s for x<=s) in explanation.

f takes an Int and returns a String.

l=0:scanl(+)1l
m=show<$>l
f n|x<-m!!n=[y|y<-x:m,or[x<=s|s<-scanr(:)""y,x++":">s]]!!n

Try it online!

How it works

l is the infinite list of Fibonacci numbers, defined recursively as the partial sums of 0:1:l. It starts with 0 because lists are 0-indexed. m is the same list converted to strings.
In f:

n is the input number, and x is the (string of the) nth Fibonacci number.
In the outer list comprehension, y is a Fibonacci number tested for whether it contains x as a substring. The passing ys are collected in the list and indexed with the final !!n to give the output. An extra x is prepended to the tests to save two bytes over using !!(n-1) at the end.
To avoid counting ys several times, the tests of each y are wrapped in or and another list comprehension.
In the inner list comprehension, s iterates through the suffixes of y.
To test whether x is a prefix of s, we check whether x<=s and  x++":">s. (":" is somewhat arbitrary but needs to be larger than any numeral.)


Create a Muriel-like language and implementation

Python 3 and "The minimum TC subset of Underload but with the characters changed to 2019, reversed, and with a 0 on top", 156 129 bytes

c,n,*s=input(),0,[]
while c:
 i,*c=c;q="6">i
 if n:n+=q*int(i)-q;s[n and-1]+=i,
 elif q:n="1"<i;s+=s[-1]*(1-n),
 else:c=s.pop()+c

Try it online!
Explanations in the header, ungolfed code in the footer.


Minecraft 1.9.0+, 204 162 bytes +  58 36 28 24 20  blocks = 262 240 232 186 182 blytes
This solution is golfed down, and it can't be seen whole in one, or even two screenshots. Uses two glitches and abuses another two features of the game

This solution uses the same principles as the one below, just a 4 blocks more compact design.

Abuses the fact that Chain command blocks (green blocks) can't be powered by redstone, only by a singal from a impulse command block (orange).

Abuses the fact pistons take 0.30 seconds to extend completely, and redstone needs only 0.10s to register a signal.

Also abuses a twofold glitch to set the timer (TNT) off: the redstone next to the timer (TNT) gets not only powered, but also thinks the TNT is another redstone and powers it.

On top of all these abuses, the signal shortener (thing under the TNT) is one-use, after it gets powered it changes shape, allowing to pass signal through it to the "incrementer" (topmost orange block)

A bit of explanation on the functionality of it's different parts can be seen in older solutions (but best in the one just below). You can also Try it Offline! (simplified solution incrementing by 4, works only in 1.11+) by running this command in a command block.

Old solution, Minecraft 1.9.0+, 186 blytes:

Since TNT normally explode after 3.0s in Minecraft, this one has to be placed by a command (/setblock) with a specified fuse. Also uses a more compact design to remove redundant command block (containing 42 bytes) and redstone against the older versions. I'm sure this can't get any lower...
Older solution, Minecraft 1.9.0+, 232 blytes:
Oops, I found out these older solutions increment by 4...

Uses the 1.9 command block chain feature (green block thing) to save blocks. Also uses a more compact signal shortener then in the older solutions
Even older solution, Minecraft 1.7.0+, 240 blytes:

Uses a more compact timer (TNT) then the first solution (below).
Oldest solution, Minecraft 1.7.0+, 262 blytes:

This is so long because of the way Minecraft handles variables:

To define a variable (int): scoreboard objectives add <variable> dummy

To set a value to a variable (each entity including players has it's own variable value): scoreboard players set <entity> <variable> <value>

* can be used as <entity> to select all entities and save bytes.

only defined variables may be used

the value of the variable must be set to a number, not a variable

To increment var1 by var2: scoreboard players operation <entity> var1 += <entity> var2

<entity> must be a single entity, eg. @p, not *

Screenshots are of my own, dual licenced under WTFPL and what licence SE decides to use today (currently  cc by-sa 3.0 with attribution required) :-)


Python, 69 + 536 = 605 (lazy solution)

I took the liberty of not capitalizing the names of the elements. That allows me to shave off extra 41 bytes. zlib is most likely not the best compressor for plaintext, it takes 1292 bytes down to 536.

python file:

import zlib
print (eval(zlib.decompress(open('a').read())))[input()]

data file a (b64 encoded for web):

eJxNVNGS5CAI/Jd5vj+62gdUJlpDMIU6t9mvPzSQ2YetZVCbpmny9/H488hnkrohzxCpjF0DKj1f
UUA5ybKhSp3XIkhYAZfuT+v3eQVPGlUK4zzGdavVdL3fYWNsVww09sJX3AqVuK4euTb9k9FmetBz
yKyXySFBtuti7dAMKgJFA4rAVquXDgb/BgbLxix1dzK8gdKZqMX6qgGor77iC2lljgMnhZ/CUf9t
4FpsKLsXAGmoTyYBJLRkmJUW55ecR18FZIRiTJoqx/2Kz97lin6KqBBXzKUGo1rpDAn5agxjZrSX
Mnr2gpJd50NZeseq7Xt1ECFZ5+Wj0SQFSmOvfC5somFUiqIt+t/INnWfXQC7Q/o2w8UroiUPgYY1
nVaNf8WHaoLurAa74+CQepiukCq5MTqKSZDOpo+tfq5kgPd5z4NuMe8sje5KZXg6qJKe7pvh4K31
ZVu5dazNdRIf1kGgWl38KqU5EpQ4ZGmWb08QwjwLpe06l+VS8mlC6xNjCira4toUATbjio8LYr+b
1z24Zeu/Doa48RgPbcE5jn4XU3rFoKMPVDf55futK1OeVew6FlYVHP6pzjbfISc19NuK1XB/HuCf
4M19elAUzVpII/heI+gnY/OPRxYfhW/ujqWz+yaB7CpScmtX5L75UHQRUelaycGDfWWehFLfn/yB
vlZU1Pm7izjPmur1+VXj+vH1H5EjvoY=


GolfScript, 1 character

,

, means length...

Edit: You seem to have changed your question... please don't do that, but I still have a solution:

GolfScript, 12 7 characters (for multiline)

n%{,n}/

Thanks @Howard for reminding me about n to push newline and using separate strings instead of one, to save 5 chars ;)

Solutions that work with negative numbers:

GolfScript, 5 (for negative)

'-'-,

GolfScript, 11 (for multiline and negative)

n%{'-'-,n}/


The shortest code to invert bit-wise a binary string

J, 5 bytes
Assumes the input string is in variable b.
b='0'

This does not do what it would do in most languages...

 The J comparison operator is just = (=: and =. are global and local assignment, respectively). However, = doesn't work like the normal == operator: it compares item-by-item. Keep in mind that an array is formed like this: 0 2 3 2 3 1 2 3 4. 2 = 0 2 3 2 3 1 2 3 4 gives 0 1 0 1 0 0 1 0 0 for example. This is similar for a string: 'a'='abcadcadda' doesn't just return 0, it returns 1 0 0 1 0 0 1 0 0 1 (This can be extrapolated to mean 0 with */, which basically means all.) In this case however, this behavior is excelent, since we want a string of ones and zeros, or true's and false's. Since J's bools are 1 and 0, this results in an array of 1's and 0's (They aren't strings, and every other character other than 1 would also result in 0 in this array.) This doesn't need printing: J automatically prints the result of an expression. I hope this was adequate explanation, if not, please ask for something that isn't yet clear in the comments. This answer also could've been '0'&= (or =&'0'), but I felt that b='0' was clearer.


Haskell, 67 66 bytes

Thanks Damien for -1 byte.

This solution is in the form of an infix function, ?, of type (Integral b, RealFrac r) => [(r, r)] -> r -> b. The helper function, #, does the required calculations while ? serves to handle the IO specifications.

a?b=floor$reverse a#b
((m,p):r)#i|v<-min i m=p/100*(i-v)+r#v
_#_=0


Find the shortest pangrams from a word list

Ruby 159 (iterative)

Ruby 227 220 229 227 221 (recursive)

New iterative solution (based on the algorithm described by @Niel):

c={('A'..'Z').to_a=>""}
while l=gets
d=c.clone
c.map{|k,v|j=k-l.upcase.chars
w=v+" "+l.strip
d[j]=w if !c[j]||c[j].size<w.size}
c=d
end
x=c[[]]
p x[1..-1] if x

Old recursive solution:

W=[]
while l=gets
W<<l.strip
end
I=W.join(" ")+"!!"
C={[]=>""}
def o(r)if C[r]
C[r]
else
b=I
W.map{|x|s=r-x.upcase.chars
if s!=r
c=x+" "+o(s)
b=c if c.size<b.size
end}
C[r]=b
end
end
r=o ('A'..'Z').to_a
p r[0..-2] if r!=I

The byte measurement is based on leaving off the final newline in the file, which does not matter to ruby 2.3.1p112. The byte count went back up after fixing a small bug (adding .downcase .upcase for case-insensitivity as required by the problem statement).

Here is an earlier version from before shortening identifiers and such:

#!/usr/bin/env ruby

$words = [];

while (line=gets)
  $words << line[0..-2];
end

$impossible = $words.join(" ")+"!!";

$cache = {};

def optimize(remaining)
  return $cache[remaining] if ($cache[remaining]);
  return "" if (remaining == []);

  best = $impossible;

  $words.each{|word|
    remaining2 = remaining - word.chars;
    if (remaining2 != remaining)
      curr = word + " " + optimize(remaining2);
      best = curr if (curr.length < best.length);
    end
  };

  $stderr.puts("optimize(#{remaining.inspect})=#{best.inspect}");

  return $cache[remaining] = best;
end

result = optimize(('a'..'z').to_a);

puts(result[0..-1]);

How does it work? It basically maintains a set of characters still to cover and only recurses on a word if it would reduce the uncovered set. Additionally, the results of recursion are memoized. Each subset of 2^26 corresponds to a memoization table entry. Each such entry is calculated in time proportional to the size of the input file. So the whole thing is O(N) (where N is the size of the input file), albeit with a huge constant.


Detect what programming language a snippet is

234 text formats - Unix Shell
(not all of them languages - I need to count them carefully)
file $1

I hesitate to post this somewhat smart-a$$ answer, but I don't see anything in the rules banning it and the file shell utility really does do a good job of this.  e.g:
$ file golfscript.rb
golfscript.rb: Ruby module source, ASCII text
$ file template.c
template.c: ASCII C program text
$ file adams.sh
adams.sh: Bourne-Again shell script, ASCII text executable
$

Furthermore you can use the -k option to "keep going" when testing a polyglot:
 -k, --keep-going
         Don't stop at the first match, keep going.  Subsequent matches
         will be have the string ‘\012- ’ prepended.  (If you want a new‐
         line, see the -r option.)

Also, the -l option will give you an idea of how good the algorithm is for differing languages:

$ file -l | grep shell
unknown, 0: Warning: using regular magic file `/etc/magic'
Strength = 280 : shell archive text [application/octet-stream]
Strength = 250 : Tenex C shell script text executable [text/x-shellscript]
Strength = 250 : Bourne-Again shell script text executable [text/x-shellscript]
Strength = 240 : Paul Falstad's zsh script text executable [text/x-shellscript]
Strength = 240 : Neil Brown's ash script text executable [text/x-shellscript]
Strength = 230 : Neil Brown's ae script text executable [text/x-shellscript]
Strength = 210 : Tenex C shell script text executable [text/x-shellscript]
Strength = 210 : Bourne-Again shell script text executable [text/x-shellscript]
Strength = 190 : Tenex C shell script text executable [text/x-shellscript]
Strength = 190 : Bourne-Again shell script text executable [text/x-shellscript]
Strength = 180 : Paul Falstad's zsh script text executable [text/x-shellscript]
Strength = 150 : Tenex C shell script text executable [text/x-shellscript]
Strength = 150 : Bourne-Again shell script text executable [text/x-shellscript]
Strength = 140 : C shell script text executable [text/x-shellscript]
Strength = 140 : Korn shell script text executable [text/x-shellscript]
Strength = 140 : Paul Falstad's zsh script text executable [text/x-shellscript]
Strength = 130 : POSIX shell script text executable [text/x-shellscript]
Strength = 130 : Plan 9 rc shell script text executable []
$

This is file-5.09 (on Ubuntu 12.04)


V, 64 bytes

i/\
\/16ñH>GMÙXppjÄXppñ5O|³² |M3lR@HyperNeutrino Welcome back!

Try it online!

Hexdump:

00000000: 692f 5c0a 5c2f 1b31 36f1 483e 474d d958  i/\.\/.16.H>GM.X
00000010: 7070 6ac4 5870 70f1 354f 7cb3 b220 7c1b  ppj.Xpp.5O|.. |.
00000020: 4d33 6c52 4048 7970 6572 4e65 7574 7269  M3lR@HyperNeutri
00000030: 6e6f 2057 656c 636f 6d65 2062 6163 6b21  no Welcome back!

Explanation:

i                             " Insert:
 /\<cr>\/                     "   '/\<newline>\/'
         <esc>                " Return to normal mode
16ñ             ñ             " 16 times:
   H                          "   Move to the beginning of the buffer
    >G                        "   Indent every line
      M                       "   Move to the middle of the buffer (the last downward facing part)
       Ù                      "   Duplicate this line downwards
        X                     "   Delete one of the leading spaces
         pp                   "   And paste it between the slashes twice
           j                  "   Move down a line (the first upward facing part)
            Ä                 "   Duplicate this line upwards
             X                "   Delete one of the leading spaces
              pp              "   And paste it between the slashes twice
5O                            " On the five lines above us, insert:
  |³² |                       "   A bar followed by 32 spaces, followed by a bar
       <esc>                  " Return to normal mode
            M                 " Move to the middle line of the buffer
             3l               " Move 3 characters to the right
               R              " And write the following over the existing text:
@HyperNeutrino Welcome back!  "   Welcome back!


Charcoal, 48 bytes

ＦＮ«Ｍ×Ｘ±¹ιＩ§224ι←Ｂ⁹±⁶*↗↗↑↓²→⁵↖↑²←⁵↖»ＧＨ<⁵*Ｍ⁷←ＧＨ<⁴*

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

ＦＮ«

Draw N Blox.

Ｍ×Ｘ±¹ιＩ§224ι←

Adjust the horizontal position before drawing each Blox.

Ｂ⁹±⁶*

Draw the outer wall of the Blox.

↗↗↑↓²→⁵↖↑²←⁵↖»

Draw the inner wall of the Blox.

ＧＨ<⁵*Ｍ⁷←ＧＨ<⁴*

Raise the roof.


R, 34 42 Points

I think I have complied with all the rules and scored it correctly.
Edit  Turns out not complying with the rules in the first place was a bit of a bonus.
Use this formula to calculate pi (63/25)x((17+sqrt(5)*15)/(7+sqrt(5)*15))
# set up the required numbers
a<-5
b<-2
# Calculate 5^.5 * 15                    3 Operations 11 Bytes
c<-prod(sqrt(a),sum(a,a,a))
# Calculate (17 + c) / (7 + C)           3 Operations 7 Bytes
d<-sum(a,a,a,b,c)/sum(a,b,c)
# Calculate (63/25)*d                    3 Operations 19 Bytes
pi<-prod(as.double(paste0(b,'.',a,b)),d)
# Output pi showing all digits           1 Operations 5 Bytes
strwrap(pi)

Test run
> a<-5
> b<-2
> c<-prod(sqrt(a),sum(a,a,a))  # 3 Operations 11 Bytes
> d<-sum(a,a,a,b,c)/sum(a,b,c) # 3 Operations 7 Bytes
> pi<-prod(as.double(paste0(b,'.',a,b)),d) # 3 Operations 19 Bytes
> strwrap(pi)                    # 1 Operations 5 Bytes
[1] "3.14159265380569"


TikZ, 195 193 181 177 172 167 163 160 159 bytes

Thanks to David Carlisle for his helpful answer here

\documentclass[tikz]{standalone}\begin{document}\tikz\def~#1{\typein[#1];}~\a~\s~\d~\r\def\u{)--(\a+\d}\draw(,)--(\a,127\u,\s\u+64,\s\u+\r+64,);\end{document}

Yes, you heard right TikZ.

Explanation

This uses a couple of techniques to achieve its goal.  The first thing is input.  Most people might not know that LATEX can take input.  Well it can.  This is achieved with the command \typein.  This will halt the compiler and request input from the user as assign it to a variable.

The other main technique is the use of \def.  \def in Tikz is absurdly powerful.  It essentially defines a piece of code and pastes it everywhere you call the variable.  In this code we define two things \typein[#1]{} so that we can assign our variables golfily and )--(\a+\d because this code shows up a bunch of times in the ungolfed version.

Here are two versions of the code (without the wrapper):

Golfed:

\documentclass[tikz]{standalone}\begin{document}\tikz\def~#1{\typein[#1];}~\a~\s~\d~\r\def\u{)--(\a+\d}\draw(,)--(\a,127\u,\s\u+64,\s\u+\r+64,);\end{document}

Ungolfed:

\typein[\a]{}\typein[\s]{}\typein[\d]{}\typein[\r]{}\draw(0,0)--(\a,127)--(\a+\d,)--(\a+\d+64,)--(\a+\d+\r+64,0);

Image:

Since I cannot upload a pdf image directly, and converting it to any other format seems to cause the line to disappear altogether, here is what an image might look like when opened in Preview (input for this image is [64 64 64 64]):

As you can see it is very thin.  However because it is a PDF image and not a raster image does not have to comply with thickness requirements.


Ruby, 30 bytes

Simple and clean. Outputs a substring of the larger with the right offset because it seemed cheaper than any method I could think of that calculated it properly.

->o{"FEDCBA9801234567"[o+4,8]}

Try it online!


Sort digits by their first occurrence in pi

Python 3, 40 39 bytes

1 byte thanks to Jonathan Allan.

lambda s:sorted(s,key="145926870".find)

Try it online!


Scoring 6,5,4 (AKA Ship, Captain, and Crew)

05AB1E, 15 bytes

3ôO<O©3LsK_P®O*

Try it online! or Check out a test suite!

Uses the same trick as Chas Brown and Lynn use: decrementing each integer in each 3x3 sub-matrix rather than subtracting 15 at the end. Expects input in column format.

How it works

3ôO<OD3LsK_PsO* – Full program.
3ô              – Split the input in 3x3 matrices representing dice faces.
  O<O           – Sum each, subtract one and sum each again.
                  This works because after the first O there are 3 elements in each
                  list and there are 5 lists in total, so 3 * 5 = 15 = 4 + 5 + 6.
     ©          – Copy this to the register.
      3LsK      – Push [1, 2, 3] and perform set subtraction. In this scenario, we
                  have already subtracted 3 from each list, so [1, 2, 3] represent
                  the actual dice values [4, 5, 6]. If the resulting list is empty,
                   that means that those values do exist in our roll. Therefore:
          _P    – Produce a list of zeros of that length and take the product
                  (4,5,6 isn't in the dice roll if the list is empty
                  and this method assures that in this case the product is 1, else 0)
            ®O* – Sum what's in the register and multiply by that.


Does this Set Represent a Natural Number?

JavaScript (Node.js), 53 48 44 bytes

f=a=>(a=eval(a)).every(e=>a[e.length]&&f(e))

Try it online! Test cases mostly shamelessly stolen from @Arnauld's answer. Explanation: If a set represents a natural number, then the natural number it represents must be equal to the size of the set, and (given that the elements are guaranteed distinct) the elements must be the representations of the natural numbers less than it, and these must therefore have shorter lengths. This is trivially true of the empty set of course. Edit: Saved 5 bytes thanks to @Arnauld. Saved 4 bytes thanks to @Cowsquack.


Batch, 46 bytes

@echo Press any key to continue...
@pause>nul

Because pause's output contains a space before each ..


0xDEADBEEF is not tasty, but still 0xFEEDBEEF

Python 3, 121 bytes

I=open(0).read
p=print
x=i=I(1)
while i:p(end=x[:-4]);x=x[-4:];x!='Þ¾ï'or+p(end='þí¾ï');i=I(1);x+=i
p(end=x[:5])

Try it online!


MATL, 18 17 16 bytes
7Bi:"2:4PB@EX!Y*

Input is 0-based.
Try it online! Or verify all test cases.
Explanation
Given a row vector [a b c], the next vector is obtained post-matrix-multiplying it by either
[1 0 0;
 0 1 1;
 0 1 0]

or
[0 1 0;
 1 1 0;
 0 0 1]

depending on whether the iteration index is odd or even. For example, the matrix product [1 3 2]*[0 1 0; 1 1 0; 0 0 1] gives [3 4 2]. Then [3,4,2]*[1 0 0; 0 1 1; 0 1 0] gives [3 6 4], and so on.
Note also that the second matrix equals the first rotated 180 degrees, which can be exploited to save a few bytes.
7        % Push 7
B        % Convert to binary. Gives [1 1 1]. This is the initial level
i        % Take input n
:        % Push range [1 2 ... n]
"        % For each
  5      %   Push 5
  I:     %   Push range [1 2 3]
  -      %   Subtract, element-wise: gives [4 3 2]
  B      %   Convert to binary. This gives the matrix [1 0 0; 0 1 1; 0 1 0]
  @      %   Push current iteration index
  E      %   Multiply by 2. Gives 2 in the firt iteration, 4 in the second etc
  X!     %   Rotate matrix 90 degrees either 2 or 0 times
  Y*     %   Matrix multiply
         % End. Implicitly display


Shortest Program To Find Lowest Common Ancestor of Two Nodes in a Binary Tree

R with ape package, 12 bytes

ape::getMRCA

Built-in. Called as ape::getMRCA(tree, c(node1, node2)).


Python 2, 58 bytes

lambda a,b,A,B:(A-a)*(B-b)<(a-b)*(A-B)*((a+b)/5+(A+B)/5&1)

Try it online!
Outputs True/False reversed
59 bytes

lambda a,b,A,B:A*B+a*(b-A-B)<(b-a)*[A,B][(a+b)/5+(A+B)/5&1]

Try it online!
59 bytes

lambda a,b,A,B:A*B+b*a<[A*b+B*a,a*A+b*B][(a+b)/5+(A+B)/5&1]

Try it online!
62 bytes

a,b,A,B=input()
if(a+b)/5+(A+B)/5&1:a,b=b,a
print(A-a)*(B-b)<0

Try it online!


Golfed only, -23 bytes
ES6 supports default parameters.

Default function parameters allow formal parameters to be initialized
with default values if no value or undefined is passed.

So, we can replace y=y||x with just r=>(x,y=x).
(y*y-x)/(2*y) can be rewritten as y/2-x/2/y. And since this expression appears twice in the code, we can assign it to a new variable z.
We get:
r=(x,y=x)=>(z=y/2-x/2/y)>1e-15?r(x,y-z):y

As suggested by ETHproductions in the comments, we now can save 2 more bytes by multiplying z by 2:
r=(x,y=x)=>(z=y-x/y)>2e-15?r(x,y-z/2):y

r=(x,y=x)=>(z=y-x/y)>2e-15?r(x,y-z/2):y

console.log(r(37))

Alternate version, -26 bytes
To save more bytes, another approach is to just iterate enough times rather than using a test on the result.
That could be done that way:
r=(x,y=k=x)=>(k/=2)?r(x,y/2+x/2/y):y

r=(x,y=k=x)=>(k/=2)?r(x,y/2+x/2/y):y

console.log(r(37))

We start with k = x and divide it by 2 at each iteration. No matter the initial value of x, we will eventually reach 0 because of arithmetic underflow.
The good thing about this method is that the number of iterations doesn't heavily rely on the value of x. For instance, we'll get 1142 iterations for x = 1020 and 1009 iterations for x = 10 -20. In both cases, we iterate far too many times than necessary, without exceeding the default maximum number of iterations of common browsers.
Some more notes:

The error is negligible for x > 10 -215 and quickly grows below this bound.
For the same byte count and less iterations, we can divide by 9 instead. In that case, a safe bound is x > 10 -124.
Unlike Math.sqrt(), this method does not return NaN for negative numbers or ±Infinity (and neither does the original code).


Python 2, 32 bytes

lambda m,n:(m*n+abs(m%5-~n%5))/5

Try it online!

Adapts an idea from Arnauld. We estimate that \$1/5\$ of the \$mn\$ pairs will satisfy the mod-5 condition. Th actual value may be one higher depending on the mod-5 values of \$m\$ and \$n\$, and we bump up \$mn\$ a bit so that these make it pass the next multiple of 5.

34 bytes

lambda m,n:m*n/5+(0<-m%5*(-n%5)<5)

Try it online!

34 bytes

lambda m,n:m*n/5+(m*n%5+m%5+n%5)/9

Try it online!

36 bytes

lambda m,n:m*n/5+((5-m%5)*(5-n%5)<5)

Try it online!

36 bytes

lambda m,n:m*n/5+(abs(m%5+n%5*1j)>4)

Try it online!

36 bytes

lambda m,n:m*n/5+(m%5*5/4+n%5*5/4>5)

Try it online!

36 bytes

lambda m,n:m*n/5+(m%5+n%5+m*n%5/4>5)

Try it online!


Jelly, 9 bytes

ØAjṪ$Ƥż¹Y

Try it online!

How it works

ØAjṪ$Ƥż¹Y  Main link. No arguments.

ØA         Yield "ABCDEFGHIJKLMNOPQRSTUVWXYZ".
     Ƥ     Map the link to the left over all prefixes, i.e., ["A", "AB", ...].
    $        Combine the two links to the left into a chain.
   Ṫ           Tail; yield and remove the last letter of each prefix.
  j            Join the remainder, using that letter as separator.
      ż¹   Zip the resulting strings and the letters of the alphabet.
        Y  Separate the results by linefeeds.


Python 2, 94 bytes

g=lambda c,*p:lambda a,b:c in p or all(map(g((id(a),id(b)),c,*p),a,b))if a>[]<b else a==b
g(0)

Try it online!

An improvement on isaacg's very clever solution of storing the id pairs of lists being processed and declaring them equal if the same comparison comes up on a lower level.

The recursive step all(map(...,a,b)) says that a and b are equal if all corresponding pair of elements in them are equal. This works nicely to reject unequal-length because map pads the shortest list with None, unlike zip which truncates. Since none of the actual lists contain None, these padded lists will always be rejected.


Underhanded code contest: Not-so-quick sort

C

CleverSort

CleverSort is a state-of-the-art (i. e. over-engineered and sub-optimal) two-step string sorting algorithm.

In step 1, it starts by pre-sorting the input lines using radix sort and the first two bytes of each line. Radix sort is non-comparative and works very well for strings.

In step 2, it uses insertion sort on the pre-sorted list of strings. Since the list is almost sorted after step 1, insertion sort is quite efficient for this task.

Code

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Convert first two bytes of Nth line into integer

#define FIRSTSHORT(N) *((uint16_t *) input[N])

int main()
{
    char **input = 0, **output, *ptemp;
    int first_index[65536], i, j, lines = 0, occurrences[65536];
    size_t temp;

    // Read lines from STDIN

    while(1)
    {
        if(lines % 1000 == 0)
            input = realloc(input, 1000 * (lines / 1000 + 1) * sizeof(char*));

        if(getline(&input[lines], &temp, stdin) != -1)
            lines++;
        else
            break;
    }

    output = malloc(lines * sizeof(char*));

    // Radix sort

    memset(occurrences, 0, 65536 * sizeof(int));

    for(i = 0; i < lines; i++) occurrences[FIRSTSHORT(i)]++;

    first_index[0] = 0;

    for(i = 0; i < 65536 - 1; i++)
        first_index[i + 1] = first_index[i] + occurrences[i];

    memset(occurrences, 0, 65536 * sizeof(int));

    for(i = 0; i < lines; i++)
    {
        temp = FIRSTSHORT(i), output[first_index[temp] + occurrences[temp]++] = input[i];
    }

    // Insertion sort

    for(i = 1; i < lines; i++)
    {
        j = i;

        while(j > 0 && strcmp(output[j - 1], output[j]) > 0)
            ptemp = output[j - 1], output[j - 1] = output[j], output[j] = ptemp, j--;
    }

    // Write sorted lines to STDOUT

    for(i = 0; i < lines; i++)
        printf("%s", output[i]);
}

Platforms

We all know that big-endian machines are much more efficient than their little-endian counterparts. For benchmarking, we'll compile CleverSort with optimizations turned on and create randomly a huge list (just over 100,000 strings) of 4-byte lines:

$ gcc -o cleversort -Ofast cleversort.c
$ head -c 300000 /dev/zero | openssl enc -aes-256-cbc -k '' | base64 -w 4 > input
$ wc -l input
100011 input

Big-endian benchmark

$ time ./cleversort < input > /dev/null

real    0m0.185s
user    0m0.181s
sys     0m0.003s

Not too shabby.

Little-endian bechmark

$ time ./cleversort < input > /dev/null

real    0m27.598s
user    0m27.559s
sys     0m0.003s

Boo, little Endian! Boo!

Description

Insertion sort is really rather efficient for almost-sorted lists, but it is horribly inefficient for randomly sorted ones.

CleverSort's underhanded part is the FIRSTSHORT macro:

#define FIRSTSHORT(N) *((uint16_t *) input[N])

On big-endian machines, ordering a string of two 8-bit integers lexicographically or converting them to 16-bit integers and ordering them afterwards yields the same results.

Naturally, this is possible on little-endian machines as well, but the macro should have been

#define FIRSTSHORT(N) (input[N][0] | (input[N][1] >> 8))

which works as expected on all platforms.

The "big-endian benchmark" above is actually the result of using the proper macro.

With the wrong macro and a little-endian machine, the list is pre-sorted by the second character of every line, resulting in a random ordering from the lexicographical point of view. Insertion sort behaves very poorly in this case.


JavaScript (ES6), 57 bytes

Takes input in currying syntax (p)(s), where p is the list of points and s is the list of scores.

p=>s=>s.map(v=>s.reduce((t,x,i)=>x-v?t:t+p[n++,i],n=0)/n)

Test cases

let f =

p=>s=>s.map(v=>s.reduce((t,x,i)=>x-v?t:t+p[n++,i],n=0)/n)

points = [15,12,10,9,8,7,6,5,4,3,2,1];

console.log(JSON.stringify(f(points)([21,21,15,14,12,9,6,5,4,3,2,1])))
console.log(JSON.stringify(f(points)([20,15,15,15,10,9,8,7,6,5,4,3])))
console.log(JSON.stringify(f(points)([1,1,1,1,1,1,1,1,1,1,1,1])))
console.log(JSON.stringify(f(points)([20,20,20,20,10,10,10,9,8,7,6,5])))
console.log(JSON.stringify(f(points)([100,99,98,95,95,95,94,93,93,92,91,91])))


Do not doubt the power of m

Background: Fm calls the a specified line index in the current Vitsy class. (F is the line index you seek).

The m command (method) has saved me literally hundreds of bytes in the past. Any algorithm that uses repeated steps, or a common character sequence (such as D1M- (floor algorithm)).

This is extremely helpful in repetitive kolmogorov complexity challenges.

Instead of:

WD1M-(something else here)WD1M-(something different)WD1M-l\[NaO]

Use:

1m(something else here)1m(something different)1ml\[NaO]
WD1M-

(floor(prompt))

Also, you can return from method statements with ;, allowing for looping until condition(s) (over the general [  ] syntax, which isn't as powerful):

1mN
<;)

(loops through code until finding non-zero, popping it from the stack and returning to first line)


Javascript - 68 55 51

alert(/\n(.+)/.exec(eval(prompt().slice(0,-2)))[1])

Alternatively: (same length)

alert(/.+(?=\n})/.exec(eval(prompt().slice(0,-2))))

Runs in the console of your browser. Only guaranteed to work with code generated by jsfuck.com with the 'Eval Source' option ticked.

Ungolfed:

alert(
    /\n(.+)/.exec(                 // regex to extract code from inside outer function braces {}
        eval(prompt().slice(0,-2)) // remove the final set of parens () and evaluate the code
                                   // this results in a function, which will be converted to a string as 'exec' expects a string
    )[1]                           // get the first capture group
)


CJam, 57 55 bytes

{:K,K0a*@[{Kmrm<){_{_0#>W%K0e]}2*_)}1?+}*;]1fb2/::-fe=}

This is an anonymous function that pops k and t from the stack (k on top of t) and leaves the desired array in return.

Try it online in the CJam interpreter.

How it works

:K         e# Save the topmost integer (k) in K.
,          e# Push I := [0 ... K-1].
K0a*       e# Push J := [0 ... 0] (K elements).
@          e# Rotate the other integer (t) on top of the stack.
[{         e# Do t times:
  Kmr      e#   Pseudo-randomly select an integer between 0 and t-1.
  m<       e#   Rotate the array J than many units to the left.
  )        e#   Pop out the last element.
  {        e#   If it is 1:
    _      e#     Copy J.
    {      e#     Do 2 times:
      _0#  e#       Push the first index of 0 in J.
      >    e#       Discard the preceding elements.
      W%   e#       Reverse the array.
      K0e] e#       Pad it with zeroes to length K.
    }2*    e#
    _)     e#     Copy J and pop out the last element.
  }        e#
  1?       e#   Else: Push 1.
  +        e#   Push the integer on the stack on J.
}*         e#
;          e# Discard the last value of J.
]          e# Collect the intermediate values of J in an array.
1fb        e# Replace each array by the sum of its elements (number of ones).
2/         e# Split the array into chunks of length 2.
::-        e# Replace each chunk by the difference of its elements.
fe=        e# Count the occurrences of each integer in I.


Haskell, 249 246 bytes

(i#x)a=[head$[x|j==i]++[s]|(j,s)<-zip[0..]a]
(s%i)[]=i<2&&elem 2(concat s)
(s%i)((l,a):b)|l,[]<-s!!a=or[(a#[i,x]$s)%x$b|x<-[1..3]]|[]<-s!!a=(a#[i]$s)%i$b|[x]<-s!!a,x==i=s%i$b|[x]<-s!!a=s%(6-i-x)$b|u<-s!!a=mod(sum$i:u)3<1&&(s%i)b
f x=(x>>[[]])%1$x

Try it online!

Takes input as a Gauss Code, ([(Bool, Int)]) where False represents crossing over and True represents under

Explanation

This algorithm works by stepping though each intersection and trying to resolve the colors of that intersection.  It keeps track of what color the strand is and branches if multiple colors are possible at a given point.

The function that we build to do this is called r.  It takes, 3 arguments:

The Gauss Code of the knot we are working on (which it will consume in order)
A list of "intersections" and what colors we have already filled in
The color of the strand where we are currently processing.

Our intersections are represented as a list of colors (Int), which we know to be at that intersection.  There are three possible states for this:

It is empty, meaning we have not visited this intersection yet.
It has one element, meaning we visited the intersection going over.
It has two elements (possibly equal), meaning we visited the intersection going under.

We can't have 3 elements because when we visit an intersection the second time we don't have to add the third element since we are never coming back.  Since we don't have to and this is code-golf, we don't.

At each step of the way we can use a very simple case analysis to determine how to branch.  Here is a diagram showing each case and the possible outputs (no possible outputs is a contradiction and return False if we reach it).  Incoming color and location are indicated with the small arrow.

Here are some sample paths of execution on the granny knot and the figure 8 knot as shown in the question.  I skip over steps where we went over a unvisited intersection, since they are quite trivial and the diagrams are quite large even without them.

Since Haskell is lazy we only ever evaluate two of these paths, the left-most path, and when that fails because the result doesn't have two colors we evaluate the second left-most.  Since that one passes we exit without further evaluation.

Here the only branch that does not encounter an error colors everything the same way.

Here is my code ungolfed a bit and commented.  I will expand this a little bit shortly.

-- Update an element of a list
q i x a=[head$[x|j==i]++[s]|(j,s)<-zip[0..]a]
-- Perform the algorithm
-- Iterates through the intersections in order
-- It records colors at each intersection and searches for a contradiction
r[]s i=i<2&&elem 2(concat s)
r((l,a):b)s i
  -- If we reach a new intersection passing under
  -- Branch on the three possible colors
  -- label the intersection with the incoming and outgoing colors
  |l,[]<-s!!a=or[r b(q a[i,x]s)x|x<-[1..3]]
  -- If we reach a new intersection passing over
  -- label the intersection with the incoming color
  |[]<-s!!a=r b(q a[i]s)i
  -- If we reach an intersection going under where the over strand is the same color as the incoming
  -- The outgoing strand is the same color
  |[x]<-s!!a,x==i=r b s i
  -- If we reach an intersection going under where the over strand is different from the incoming
  -- The outgoing strand is the third color
  |[x]<-s!!a=r b s(6-i-x)
  -- If we reach an intersection going under
  -- Check that the three strands have either all the same or all different colors
  -- Since we use 1,2 and 3 for the colors this is the same as checking if their sum is divisible by 3
  |u<-s!!a=mod(sum$i:u)3<1&&r b s i
f x=r x(x>>[[]])1