Mathematica, 17 bytes

+##/(1+##/9*^16)&

An unnamed function taking two integers and returning an exact fraction.

Explanation

This uses two nice tricks with the argument sequence ##, which allows me to avoid referencing the individual arguments u and v separately. ## expands to a sequence of all arguments, which is sort of an "unwrapped list". Here is a simple example:

{x, ##, y}&[u, v]

gives

{x, u, v, y}

The same works inside arbitrary functions (since {...} is just shorthand for List[...]):

f[x, ##, y]&[u, v]

gives

f[x, u, v, y]

Now we can also hand ## to operators which will first treat them as a single operand as far as the operator is concerned. Then the operator will be expanded to its full form f[...], and only then is the sequence expanded. In this case +## is Plus[##] which is Plus[u, v], i.e. the numerator we want.

In the denominator on the other hand, ## appears as the left-hand operator of /. The reason this multiplies u and v is rather subtle. / is implemented in terms of Times:

FullForm[a/b]
(* Times[a, Power[b, -1]] *)

So when a is ##, it gets expanded afterwards and we end up with

Times[u, v, Power[9*^16, -1]]

Here, *^ is just Mathematica's operator for scientific notation.


C++11
Done at last. And it only took me most of the day.
Before I list the code and sample output, some quick notes:
Things this program does support

Any number of terms, each with any number of inputs
Reusing inputs
Omitting AND/OR gate representation when only one input would be present
Use of both codepage 437 line-drawing characters and 7-bit ASCII-friendly characters (use -DCP437 or whatever your compiler's equivalent is for codepage 437 support)

Things this program does not support

Grouping with parentheses (because, seriously?)
Multiple NOTing
Any whitespace that isn't a plain ASCII space
Proper golfification (although I did remove all the comments in spirit)
Sane coding practices
Making eye contact with the input parsing code
Portable, Unicode line-drawing characters. I couldn't support Unicode because the rendering logic relies on being able to draw "down" a two-dimensional char buffer.

Code
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <stdexcept>
#include <set>
#include <map>
#include <valarray>
#include <cmath>

using namespace std;

vector<string> split(const string str, const string delim)
{
    vector<string> v;

    set<char> d;
    for (char c : delim) d.insert(c);

    string current {};
    for (char c : str)
    {
        if (d.find(c) != d.end())
        {
            v.push_back(current);
            current = "";
        }
        else
        {
            current += c;
        }
    }
    v.push_back(current);

    return v;
}

using Input = string;
struct TermInput
{
    Input name;
    int ypos;
    bool neg;
};
using Term = vector<TermInput>;
using Expr = vector<Term>;

#ifdef CP437
constexpr char VERT    = '\xB3';
constexpr char HORIZ   = '\xC4';
constexpr char RBRANCH = '\xC3';
constexpr char LUP     = '\xD9';
constexpr char LDOWN   = '\xBF';
constexpr char RUP     = '\xC0';
constexpr char RDOWN   = '\xDA';
#else
constexpr char VERT    = '|';
constexpr char HORIZ   = '-';
constexpr char RBRANCH = '}';
constexpr char LUP     = '\'';
constexpr char LDOWN   = '.';
constexpr char RUP     = '`';
constexpr char RDOWN   = ',';
#endif

string repeat(string s, int n)
{
    stringstream ss;
    for (int i = 0; i < n; i++)
    {
        ss << s;
    }

    return ss.str();
}
string repeat(char c, int n)
{
    stringstream ss;
    for (int i = 0; i < n; i++)
    {
        ss << c;
    }

    return ss.str();
}

enum class Direction
{
    RIGHT,
    DOWN
};

void matrixPut(char *matrix, int h, int w, int x, int y, const string s, Direction dir)
{
    if (x >= w || y >= h)
    {
        stringstream ss;
        ss << "matrixPut: point (" << x << ", " << y << ") out of matrix bounds!";
        throw new out_of_range(ss.str());
    }

    char *ins = matrix + (y * w) + x;
    char *end = matrix + (h * w);
    for (char c : s)
    {
        if (ins >= end) break;
        *ins = c;

        if (dir==Direction::RIGHT)
        {
            ins++;
        }
        else
        {
            ins += w;
        }
    }
}

void matrixPrint(char *matrix, int h, int w)
{
    for (int i = 0; i < (h * w); i++)
    {
        cout << matrix[i];
        if ((i+1)%w == 0) cout << endl;
    }
}

int main (int argc, char *argv[])
{
    string expression;

    if (argc == 1)
    {
        cout << "Enter expression:" << endl;
        getline(cin, expression);
    }
    else
    {
        expression = argv[1];
    }

    expression.erase(remove(expression.begin(), expression.end(), ' '), expression.end());

    Expr expr {};
    auto inputs = set<Input>();
    auto termInputs = multimap<Input, TermInput>();

    int inputYPos = 0;

    auto e = split(expression, "+");
    for (string term : e)
    {
        Term currTerm {};

        auto t = split(term, "*");
        for (string in : t)
        {
            bool neg = false;
            if (in.back() == '\'')
            {
                in.pop_back();
                neg = true;
            }

            Input currInput {in};
            inputs.insert(currInput);

            TermInput ti {currInput, inputYPos, neg};
            currTerm.push_back(ti);

            termInputs.insert(pair<Input, TermInput>{in, ti});
            inputYPos++;
        }

        expr.push_back(currTerm);
        inputYPos++;
    }

    int height = inputs.size() + termInputs.size() + expr.size() - 1;

    int width = 0;

    width += max_element(inputs.begin(), inputs.end(), [](Input a, Input b){ return a.length() < b.length(); })->length() + 2;
    int inputWidth = width;
    width += inputs.size()*2;

    int notAndStart = width;

    width += 7;
    width += expr.size()+1;

    int orStart = width;

    width += 4;

    width += 4;

    width += expression.length();

    char matrix[height * width];
    for (int i = 0; i < height*width; i++) matrix[i] = ' ';

    int  baseY = inputs.size();

    {
        int x = width - 4 - expression.length();
        int y = baseY + ((height-baseY) / 2);
        matrixPut(matrix, height, width, x, y, repeat(HORIZ, 4) + expression, Direction::RIGHT);
    }

    {
        int x = orStart;
        int y = baseY + (height-baseY)/2 - expr.size()/2;

        if (expr.size() == 1)
        {
            matrixPut(matrix, height, width, x, y, repeat(HORIZ, 4), Direction::RIGHT);
        }
        else {
            matrixPut(matrix, height, width, x  , y, repeat(HORIZ, expr.size()), Direction::DOWN);
            matrixPut(matrix, height, width, x+1, y, repeat(VERT , expr.size()), Direction::DOWN);
            matrixPut(matrix, height, width, x+2, y, repeat('O'  , expr.size()), Direction::DOWN);
            matrixPut(matrix, height, width, x+3, y, repeat('R'  , expr.size()), Direction::DOWN);
        }
    }

    {
        int x = notAndStart;
        int y = baseY;
        for (Term t : expr)
        {
            string layer[7];
            for (TermInput ti : t)
            {
                layer[0] += HORIZ;
                layer[1] += (ti.neg ? '>' : HORIZ);
                layer[2] += (ti.neg ? 'o' : HORIZ);
                layer[3] += HORIZ;
                layer[4] += (t.size() > 1 ? VERT : HORIZ);
                layer[5] += (t.size() > 1 ? '&' : HORIZ);
                layer[6] += (t.size() > 1 ? '&' : HORIZ);
            }

            for (int i = 0; i < 7; i++)
            {
                matrixPut(matrix, height, width, x+i, y, layer[i], Direction::DOWN);
            }

            y += t.size() + 1;
        }
    }

    {
        int x = 0;
        int y = 0;

        for (Input i : inputs)
        {
            string str = i + ": ";
            str += repeat(HORIZ, inputWidth - str.length());

            matrixPut(matrix, height, width, x, y, str, Direction::RIGHT);

            y++;
        }
    }

    {
        int x = inputWidth;
        int num = 0;
        int offset = inputs.size() * 2 - 1;

        for (Input in : inputs)
        {
            int y = 0;
            int len = inputs.size() * 2 - 1;
            auto it = inputs.find(in);
            while (it != inputs.begin())
            {
                it--;
                y++;
                len -= 2;
            }
            matrixPut(matrix, height, width, x, y, repeat(HORIZ, len) + LDOWN, Direction::RIGHT);
        }

        for (Input in : inputs)
        {
            auto yBreakRange = termInputs.equal_range(in);
            valarray<int> yBreaks(termInputs.count(in));
            int idx = 0;
            for (auto ti = yBreakRange.first; ti != yBreakRange.second; ti++)
            {
                yBreaks[idx++] = baseY + ti->second.ypos;
            }

            for (int y : yBreaks)
            {
                matrixPut(matrix, height, width, x+offset, y, repeat(HORIZ, inputs.size()*2 - offset), Direction::RIGHT);
            }

            int y = num + 1;
            int maxBreak = yBreaks.max();
            string branch = repeat(VERT, maxBreak - y + 1);

            for (int i : yBreaks)
            {
                branch[i-y] = RBRANCH;
            }
            branch.back() = RUP;

            matrixPut(matrix, height, width, x+offset, y, branch, Direction::DOWN);

            offset -= 2;
            num++;
        }
    }

    {
        int x = notAndStart + 7;
        int outY = baseY + (height-baseY)/2 - expr.size()/2;
        int breakx = expr.size()/2;

        for (Term t : expr)
        {
            int inY = baseY + (t.front().ypos + t.back().ypos) / 2;

            matrixPut(matrix, height, width, x, inY, repeat(HORIZ, abs(breakx)+1), Direction::RIGHT);

            matrixPut(matrix, height, width, x+abs(breakx)+1, outY, repeat(HORIZ, expr.size()-abs(breakx)), Direction::RIGHT);

            if (inY < outY)
            {
                string branch = LDOWN + repeat(VERT, outY-inY-1) + RUP;
                matrixPut(matrix, height, width, x+abs(breakx)+1, inY, branch, Direction::DOWN);
            }
            else if (inY > outY)
            {
                string branch = RDOWN + repeat(VERT, inY-outY-1) + LUP;
                matrixPut(matrix, height, width, x+abs(breakx)+1, outY, branch, Direction::DOWN);
            }

            outY++;
            breakx--;
        }
    }

    cout << endl;
    matrixPrint(matrix, height, width);
    cout << endl;
}
Sample output
$ ./gates "A'*B'+B*C"

A: -----.
B: ---. |
C: -. | |
    | | `->o-|&&--.
    | }--->o-|&&  `-|OR
    | |          ,--|OR----A'*B'+B*C
    | `------|&&-'
    `--------|&&

$ ./gates "A*B'*C+B*D'+F*C'*D+G*E*A'+F"

A: -------------.
B: -----------. |
C: ---------. | |
D: -------. | | |
E: -----. | | | |
F: ---. | | | | |
G: -. | | | | | |
    | | | | | | }----|&&
    | | | | | }--->o-|&&---.
    | | | | }--------|&&   |
    | | | | | | |          |
    | | | | | `------|&&--.|
    | | | }------->o-|&&  ||
    | | | | |   |         |`---|OR
    | }--------------|&&  `----|OR
    | | | | `----->o-|&&-------|OR----A*B'*C+B*D'+F*C'*D+G*E*A'+F
    | | | `----------|&&  ,----|OR
    | | |       |         |,---|OR
    `----------------|&&  ||
      | `------------|&&--'|
      |         `->o-|&&   |
      |                    |
      `--------------------'
Sample output (with CP437 enabled)
A: ─────────────┐
B: ───────────┐ │
C: ─────────┐ │ │
D: ───────┐ │ │ │
E: ─────┐ │ │ │ │
F: ───┐ │ │ │ │ │
G: ─┐ │ │ │ │ │ │
    │ │ │ │ │ │ ├────│&&
    │ │ │ │ │ ├───>o─│&&───┐
    │ │ │ │ ├────────│&&   │
    │ │ │ │ │ │ │          │
    │ │ │ │ │ └──────│&&──┐│
    │ │ │ ├───────>o─│&&  ││
    │ │ │ │ │   │         │└───│OR
    │ ├──────────────│&&  └────│OR
    │ │ │ │ └─────>o─│&&───────│OR────A*B'*C+B*D'+F*C'*D+G*E*A'+F
    │ │ │ └──────────│&&  ┌────│OR
    │ │ │       │         │┌───│OR
    └────────────────│&&  ││
      │ └────────────│&&──┘│
      │         └─>o─│&&   │
      │                    │
      └────────────────────┘


Wolfram Language (Mathematica), 51 bytes

outputs the n value
"...program that does not stop and will eventually output all..."

PrimeQ[10^c*666+1+100^++c]~If~Print[c-2]~Do~{c,∞}

Try it online!

thanks to @DanTheMan for saving 4 bytes
and also to @mypronoun -7 bytes


Retina, 22 21 20 17

O#^`[b-z-[eiouy]]

Try it online!

1 byte thanks to Leaky Nun!

4 bytes thanks to Martin!

O means sort, and # means to sort by numeric value. Since none of the matched characters will ever have a numeric value, all letters have the same weight: 0. ^ means to reverse the order of the sorted values, which thanks to stable sorting means the values are reversed.

The -[...] means to do the setwise difference between the outer character class and this inner class. This is part of .NET and you can read more at the MSDN.


x86_64 machine code (System V ABI), 28 27 bytes

-1 byte thanks to @Cody Gray, thanks!

A constant-time algorithm!

_cullen:
   0:   0f bd cf    bsrl    %edi, %ecx
   3:   0f bd c1    bsrl    %ecx, %eax
   6:   89 ca       movl    %ecx, %edx
   8:   29 c2       subl    %eax, %edx
   a:   0f bd c2    bsrl    %edx, %eax
   d:   29 c1       subl    %eax, %ecx
   f:   d3 e1       shll    %cl, %ecx
  11:   ff c1       incl    %ecx
  13:   31 c0       xorl    %eax, %eax
  15:   39 f9       cmpl    %edi, %ecx
  17:   0f 94 c0    sete    %al
  1a:   c3          retq

Explanation:

Let y an integer and x=y*2^y + 1.
Taking logs, we have y + log2(y) = log2(x-1), thus y=log2(x-1)-log2(y). Plugging back the value of y, we get y=log2(x-1)-log2(log2(x-1)-log2(y)). Doing this one more time, we obtain: y=log2(x-1)-log2[log2(x-1)-log2(log2(x-1)-log2(log2(x-1)-log2(y)))].

Let us remove the last terms (of the order of log2(log2(log2(log2(x)))), this should be safe!), and assume that x-1≈x, we obtain:
y≈log2(x)-log2[log2(x)-log2(log2(x))]

Now, letting f(n) = floor(log2(n)), it can be verified manually that y can be exactly retrieved by:
y=f(x)-f[f(x)-f(f(x))],
for y < 26, and thus x ⩽ 10^9, as specified by the challenge(1).

The algorithm then simply consists of computing y given x, and verify that x == y*2^y + 1.
The trick is that f(n) can simply be implemented as the bsr instruction (bit-scan reverse), which returns the index of the first 1-bit in n, and y*2^y as y << y.

Detailed code:

_cullen:                                 ; int cullen(int x) {
   0:   0f bd cf    bsrl    %edi, %ecx   ;  int fx = f(x);
   3:   0f bd c1    bsrl    %ecx, %eax   ;  int ffx = f(f(x));
   6:   89 ca       movl    %ecx, %edx
   8:   29 c2       subl    %eax, %edx   ;  int a = fx - ffx;
   a:   0f bd c2    bsrl    %edx, %eax   ;  int ffxffx = f(a);
   d:   29 c1       subl    %eax, %ecx   ;  int y = fx - ffxffx;
   f:   d3 e1       shll    %cl, %ecx    ;  int x_ = y<<y;
  11:   ff c1       incl    %ecx         ;  x_++;
  13:   31 c0       xorl    %eax, %eax
  15:   39 f9       cmpl    %edi, %ecx
  17:   0f 94 c0    sete    %al
  1a:   c3          retq                 ;  return (x_ == x);
                                         ; }

(1)In fact, this equality seems to hold for values of y up to 50000.


Pylons, 7 5 4 bytes

Picked a random language on TIO used it

46vt

Explanation:

Try it Online!

46    # Stack is [4, 6]

v     # Reverse the stack [6, 4]

t     # take top of stack 4

Doubled:

4466   # Stack is [4, 4, 6, 6]

vv     # Reverse the stack twice so it's the same [4, 4, 6, 6]

tt     # take top of stack 6 and again which is 6 again

Saved 2 bytes thanks to  officialaimm

Saved 1 bytes thanks to  Veedrac


Given a string, calculate the number of the column it corresponds to

Perl 6, 17 bytes

{:26[.ords X-64]}

Try it online!

Anonymous code block that subtracts 64 from each byte value and converts from base 26 with Z overflowing to the next column.


APL (Dyalog Unicode), 318 317 319 bytesSBCS

∨/{(4=⊃⍵)>≢⊃1⌽⍵}¨{1=≢⍵:⍵⋄⊃,/(⊂⍵)∇{⊃,/,(⍺⍺⍵↑⍺)∘.{c←⊃¨⍺⍵⋄w←⊃,/⊃¨u v←1↓¨⍺⍵
(⊂c)∊t←↓10 2⍴⎕A⍳'AOBAJACKANEADMLDJDGK':⊂(2,u)(1w 0)(3,v)(1u 0)(5(⊃u)⍬)(4w⍬)(6,u)(4,v)(7,v)(4,u)⊃⍨t⍳⊂c
6 4≡c:⊂4,u,¨v
9 1≡c:(2⊃v)↑⊂8,v
8 4≡c:(a∊3⊃⍵)↓⊂4(a~⍨⊃v)((3⊃⍵),a←⊃u)
⍬}⍺⍺⍵↓⍺}¨⍳¯1+≢⍵}{⌈/c←(⊃⍵)∊¨¯1⌽'()!',↓4 3⍴' &|=<>+* AE':8+⊃⍸c⋄1(⊂⍵)1}¨' '(≠⊆⊢)⍞

Try it online!

-1 byte thanks to @Adám.

+2 bytes because the code wrongly accepted E ( a ) a = a. Fixed by adding a "simple" flag to the Num node, which is 1 right after tokenization but becomes 0 after any kind of merging. TQuant Num -> Quant rule is accepted only if "simple" is 1.

Full program. Takes a line of input (each symbol separated with a space) from stdin, and prints 1 if it can be parsed successfully, 0 otherwise.

How it works: the grammar & parsing

I manually dissected all the grammar rules into two-branch rules, e.g. the parenthesizing rule

"(" Num ")" -> Num

became two rules

"(" Num -> NumP
NumP ")" -> Num

with NumP being a new node type. Also, I omitted the last part of the Num node, as it is always an empty set.

(Num ids,?) [+*] -> (NumR ids)
(NumR ids) (Num ids2,?) -> (Num (ids+ids2),0)
"(" (Num ids,?) -> (NumP ids)
(NumP ids) ")" -> (Num ids,0)
(Num ids,?) [=<>] -> (BoolN ids,[])
(BoolN ids,ids3) (Num ids2,?) -> (Bool (ids+ids2),ids3)
(Bool ids,ids2) [&|] -> (BoolR ids,ids2)
(BoolR ids,ids3) (Bool ids2,ids4) -> (Bool (ids+ids2),(ids3+ids4))
"!" (Bool ids,ids2) -> (Bool ids,ids2)
"(" (Bool ids,ids2) -> (BoolP ids,ids2)
(BoolP ids,ids2) ")" -> (Bool ids,ids2)
[EA] (Num id,1) -> (Quant id)
(Quant id) (Bool ids,ids2) -> (Bool (ids-id),(ids2+id)) if id not in ids2

Using these rules, I could tackle the ambiguous parsing problem as follows:

Split the given list of tokens into two chunks.
Recursively get all possible parses for the two chunks.
Test all combinations of parses to gather all possible derived parses.
Repeat 1-3 for all possible splits, and gather all results.

The algorithm is exponential in the number of tokens, so the two longest test cases are excluded from the tests.

Original version with comments

⍝ Constants to classify the grammar node type
Num NumR NumP Bool BoolN BoolR BoolP Quant TQuant TParenL TParenR TNot TBool2 TCmp TNum2←⍳15

⍝ Split given string by spaces, and convert to a list of grammar nodes
tokenize←{
  words←(' '∘≠⊆⊢)⍵  ⍝ split by spaces
  {
    class←(⊃⍵)∊¨'AE' '(' ')' '!' '&|' '=<>' '+*'
    ⌈/class: 8+⊃⍸class  ⍝ Single-char tokens into respective nodes
    Num(⊂⍵)1  ⍝ An identifier is a Num node
  }¨words  ⍝ wrap each word into tokens
}

⍝ Takes two nodes, and gives a new node if valid, ⍬ otherwise
match←{
  class←⊃¨⍺⍵
  Num TNum2≡class: ⊂NumR(2⊃⍺)
  NumR Num≡class: ⊂Num((2⊃⍺),2⊃⍵)0
  TParenL Num≡class: ⊂NumP(2⊃⍵)
  NumP TParenR≡class: ⊂Num(2⊃⍺)0
  Num TCmp≡class: ⊂BoolN(2⊃⍺)⍬
  BoolN Num≡class: ⊂Bool((2⊃⍺),2⊃⍵)⍬
  Bool TBool2≡class: ⊂BoolR(2⊃⍺)(3⊃⍺)
  BoolR Bool≡class: ⊂Bool((2⊃⍺),2⊃⍵)((3⊃⍺),3⊃⍵)
  TNot Bool≡class: ⊂Bool(2⊃⍵)(3⊃⍵)
  TParenL Bool≡class: ⊂BoolP(2⊃⍵)(3⊃⍵)
  BoolP TParenR≡class: ⊂Bool(2⊃⍺)(3⊃⍺)
  ⍝ Valid only if "simple" flag of Num node is 1
  TQuant Num≡class: (3⊃⍵)↑⊂Quant(2⊃⍵)
  ⍝ Valid only if quantified variable is not already quantified
  Quant Bool≡class: (~(2⊃⍺)∊3⊃⍵)↑⊂Bool((2⊃⍵)~2⊃⍺)((3⊃⍵),2⊃⍺)
  ⍬
}

⍝ Given a list of tokens, returns an array of possible parses
⍝ Split in all possible ways and check for at least one split is valid
parse←{
  ⍝ Single token: no need to parse
  1=≢⍵:⍵
  splits←⍳¯1+≢⍵
  ⍝ Concatenate parses based on all possible splits
  ⊃,/(⊂⍵)∇{
    left←⍺⍺ ⍵↑⍺
    right←⍺⍺ ⍵↓⍺
    ⍝ Test all possible combinations of left/right parses
    ⊃,/,left ∘.match right
  }¨splits
}

⍝ Test if one of the parses is Bool with no free variables
test←{
  ∨/{
    Bool≠⊃⍵:0
    0=≢2⊃⍵
  }¨⍵
}

⍝ The solution is the chain of three functions defined above
test∘parse∘tokenize

Try it online!


Collatz Paths: Forwards and Backwards along the Collatz Conjecture

Haskell, 170 158 157 146 143 137 135 112 109 108 106 100 99 bytes
a!b=length$fst$break(elem b)$iterate(>>= \n->2*n:cycle[div n 2,n*3+1]!!n:[div(n-1)3|mod n 6==4])[a]

I did not expect that my original version was so much more golfable, this is also the work of @nimi @Lynn and @Laikoni!
Thanks @Laikoni for a byte, @Lynn for 11 14 20 21 bytes, @nimi for 8 bytes!
This expands the the tree of visited numbers (beginning by a) step by step, and checks in each step whether we arrived at the given number b.


Decompose a number into a sum of repdigits


Python, 310 302 287 278 277 260
Not radically different than the existing Python post, but has one or two noteworthy tricks, I think.
It also handles "non-terminating" input, such as 1>1. EDIT: Oops! emitters block lasers.
def t(b):
 w=len(b[0])+1;B=list('@'*w+'@'.join(b));i=l=len(B);C="<>^v@"
 while i:
    j=l-i;i-=1;d=C.find(B[j]);c='.'
    while c not in C:
     if'+'>c:B[j]='.'
     if'0'<c<C:j=(B*2).index(c,j+1)%l
     elif'.'<c:d^=2+(c<C)
     j-=[1,-1,w,-w,j][d];c=B[j%l]
 return'*'not in B

t takes a list of strings (the input lines) and returns a boolean result.
Here's a nice gif of the code being golfed down:

EDIT: Awsome gif courtesy of Will. Thanks Will!


Jelly, 21 19 15 bytes
ị“£ṅ@kṃżF’b3¤BX

Try it online!
-4 bytes after inspiration from @Neil's Charcoal Answer (binary!).
Try all testcases listed out in a grid (each row is one input tested multiple times).
How?
ị“£ṅ@kṃżF’b3¤BX     # Main link
 “©½B.ọṅc’                # The integer 1719989029560350
          b3              # to base 3: [1,1,2,0,0,2,2,1,1,1,1,2,0,0,0,1,1,1,2,0,0,0,0,2,0,1,2,2,0,0,0,1]
                          # (2 => R; 1 => 1; 0 => 0)
ị           ¤             # Index the input into the base 3 list above
                            # (1-indexed, and 0 gives the last element)
             B            # convert to binary: 2 => [0,1], 1 => [1], 0 => [0]
              X           # Pick a random element from that list

19 byte version
(I personally like this one more because it uses special properties of ị and X)
Try it online!
Try all testcases.
ị“©½B.ọṅc’b3¤Hị1,0X     # Main link
 “©½B.ọṅc’                # The integer 1719989029560350
          b3              # to base 3: [2,2,1,0,0,1,1,2,2,2,2,1,0,0,0,2,2,2,1,0,0,0,0,1,0,2,1,1,0,0,0,2]
                          # (2 => 1; 1 => R; 0 => 0)
ị           ¤             # Index the input into the base 3 list above
                            # (1-indexed, and 0 gives the last element)
             H            # Halve: [2,1,0] => [1,0.5,0]
              ị1,0        # Index into 1,0 (again 1-indexed)
                            # 1 gives 1, and 0 gives 0
                            # 0.5 gives [0,1]; since it is a fractional index, it gives both the element corresponding to floor(0.5) and ceil(0.5)
                  X       # Random; 3 different functions
                            # 0 => 0
                            # 1 => random integer from 1 to 1 => 1
                            # [0,1] => random element of [0,1]


When does Santa enter the basement? (AOC Day 1)

Jelly, 8 7 bytes

O-*+\i-

Thanks to @Sp3000 for golfing off 1 byte!

Try it online!

How it works

O-*+\i-    Main link. Input: s (string)

O          Ordinal; replace each character with its code point.
           This maps "()" to [48, 49].
 -*        Apply x -> (-1) ** x.
           This maps [48, 49] to [1, -1].
   +\      Compute the cumulative sum, i.e., the list of partial sums.
     i-    Find the first index of -1.


Python 3, 51 bytes

lambda s:s[0].lower()+s.title().replace('_','')[1:]

Try it online!

-4 bytes thanks to ReinstateMonica


R, 156 bytes

function(n){g=function(h)c(0,cumsum(h((4*(0:(n+2)^2)+1)^.5%%4%/%1/2)))
x=g(sinpi)
y=g(cospi)
a=x[n]
b=y[n]
which(x==a&(y==b+1|y==b-1)|y==b&(x==a+1|x==a-1))}

Try it online!

posted another R answer since it's a slightly different approach than @ngn
1-indexed
neighbours are always sorted by ascending value
saved 6 bytes removing round and using cospi(x)/sinpi(x) which are more precise than cos(x*pi)/sin(x*pi) in case of half numbers (0.5, 1.5 etc...)
saved another byte removing the minus on y coordinates since the result is the same (just up/down neighbours are reversed)

Explanation :

If we look at the matrix coordinates of the values, considering the first value 0 placed at x=0, y=0, they are :

x = [0,  1,  1,  0, -1, -1, -1,  0,  1,  2,  2,  2,  2,  1,  0, ...]
y = [0,  0,  1,  1,  1,  0, -1, -1, -1, -1,  0,  1,  2,  2,  2, ...]

The x coordinates follow the A174344 OEIS sequence with the recursive formula :

a(1) = 0, a(n) = a(n-1) + sin(mod(floor(sqrt(4*(n-2)+1)),4)*pi/2)

The same formula holds for y matrix coordinates, but with cos instead of sin and negated :

a(1) = 0, a(n) = a(n-1) - cos(mod(floor(sqrt(4*(n-2)+1)),4)*pi/2)

So, in R we can translate the formula to this function, taking sinpi/cospi as parameter :

g=function(h)c(0,cumsum(h((4*(0:(n+2)^2)+1)^.5%%4%/%1/2)))

and we generate the two coordinates vectors (we don't negate the y coords since we'll get the same result, just with up/down neighbours reversed) :

x=g(sinpi)
y=g(cospi)

Note that we have generated (n+2)^2 coordinates, which are more than the minimum necessary coordinates containing both n and their neighbours (a tighter bound would be (floor(sqrt(n))+2)^2 but unfortunately is less "golfy").

Therefore, now that we have all the coordinates, we first search the coordinates a,b corresponding to our n :

a=x[n]
b=y[n]

finally we select the positions of their neighbours, i.e. :

the up/down neighbours where x == a and y == b+1 or b-1
the right/left neighbours where y == b and x == a+1 or a-1

using :

which(x==a&(y==b+1|y==b-1)|y==b&(x==a+1|x==a-1))


JavaScript, 84 79 bytes

i=>{I=i;for(x=-1;i>=999.5;x++)i/=1e3;return I<1e4?I:+i.toPrecision(3)+'KMB'[x]}

Try it online!

(Takes inputs as numbers)

Special cases the first one where if i < 1000, the number itself is always one of the shortest ways, if not the only shortest way.

Otherwise, it divides it by 1000 until dividing it would make it have no sigificant figures above 1, and chooses a suffix based on how many divisions were done.


Operation Flashpoint scripting language, 263 195 bytes

f={r="                   ";t="---------------------\n";s=" ___________________\n/"+r+"\\n"+t+"|"+r+"|\n"+t+"|"+r+"|\n"+t+"\__________    _____/\n           |  /\n           | /\n           |/";s}

Not the right tool for the job.

Call with:

hint call f;

Output:

The formatting fails, because the font is not monospaced.


SOGL V0.12, 19 bytes
1¹.{³³┼┼≥:10ŗ;┼┼⁴++

Try it Here!
1¹                   push [1]
  .{                 input times do
    ³³                 duplicate top of stack 4 times, resulting in 5 total copies in the stack
      ┼┼               join the last 3 copies horizontally together
        ≥              put the joined at the bottom of the stack
         :             duplicate top of stack again
          10ŗ          replace 1 with 0 only in the top item
             ;         swap the top 2 items
              ┼┼       join the top 3 items horizontally together
                ⁴      copy the item one below top of stack
                 ++    add together vertically


Python 3, 130 bytes
Thanks to @Rod for pointing out a bug
from random import*
def f(x):l=10**len(x);k=str(randint(0,l-1)+l)[1:];print(''.join(chr(ord(i)+int(j))for i,j in zip(x,k))+'\n'+k)

A function that takes input via argument as a string and prints to STDOUT.
How it works
from random import*  Import everything from the random module
def f(x):            Function with input string x
l=10**len(x)         Define l for later use as 10^length(x)
randint(0,l-1)+l     Generate a random integer in the range [0, l-1] and add l, giving a
                     number with l+1 digits...
k=str(...)[1:]       ...convert to a string and remove the first character, giving a key of
                     length l that can include leading zeroes, and store in k
for i,j in zip(x,k)  For each character pair i,j in x and k:
chr(ord(i)+int(j))    Find the UTF-8 code-point (same as ASCII for the ASCII characters),
                      add the relevant key digit and convert back to character
''.join(...)         Concatenate the characters of the ciphertext
print(...+'\n'+k)    Add newline and key, then print to STDOUT

Try it on Ideone


Haskell, 101 characters

import Data.Hash.MD5
main=interact$ \m->head.filter((==m).md5s.Str)$iterate([' '..'~']:)[]>>=sequence

Use it like so:

& ghc -O2 -o brute 42043-BruteForce.hs
& echo -n c-g | md5
bc098aea57599de26c8f17a9edbd492e
& echo -n bc098aea57599de26c8f17a9edbd492e | ./brute
c-g

This requires the common package MissingH.


Shortest program that demonstrates a language's complete syntax

Jot (2 chars)

10

http://semarch.linguistics.fas.nyu.edu/barker/Iota/#Goedel


CJam (8 bytes)

{m*:$_&}

Online demo

Dissection

{    e# Declare block (anonymous function); parameters are n k
  m* e# Cartesian product, which implicitly lifts n to [0 1 ... n-1]
  :$ e# Sort each element of the Cartesian product, to give them canonical forms
  _& e# Deduplicate
}


Mathematica, 66 bytes

(For[z=1,Last@Nest[Abs@*Differences,Array[Prime,z+#],#]<3,z++];z)&

Pure function taking a positive integer as argument and returning a 1-indexed integer. Nest[Abs@*Differences,Array[Prime,z+#],#] computes the #th iterated absolute difference list of the list of the first z+# primes. For[z=1,Last@...<3,z++] loops this computation until the last element of the resulting list is at least 3, and then z is output. (Note that the correctness of the algorithm assumes Gilbreath's conjecture!)


Write a program for splitting the string with alternative spaces

Ruby, 84 81 characters

i=gets.chop
puts (a=(1..i.size).map{|n|i.scan(/.{0,#{n}}/)*' '})+a.reverse[1..-1]

The magic is in the regex: i.scan(/.{0,#{n}}/). Since Ruby does regex interpolation too, it will become

i.scan(/.{0,1}/)
i.scan(/.{0,2}/)
...

This means it will grab as many characters as it can, limited to n. n progressively gets bigger, and is used to generate the first half of the output.

Then I just call reverse to generate the second half. I had to use [1..-1] in order to avoid repeating the middle line (what that does is basically chop off the first element of the array).

Sample run:

c:\a\ruby>spacesplitgolf.rb
CodeGolfStackExchange         // (this is the input)
C o d e G o l f S t a c k E x c h a n g e
Co de Go lf St ac kE xc ha ng e
Cod eGo lfS tac kEx cha nge
Code Golf Stac kExc hang e
CodeG olfSt ackEx chang e
CodeGo lfStac kExcha nge
CodeGol fStackE xchange
CodeGolf StackExc hange
CodeGolfS tackExcha nge
CodeGolfSt ackExchang e
CodeGolfSta ckExchange
CodeGolfStac kExchange
CodeGolfStack Exchange
CodeGolfStackE xchange
CodeGolfStackEx change
CodeGolfStackExc hange
CodeGolfStackExch ange
CodeGolfStackExcha nge
CodeGolfStackExchan ge
CodeGolfStackExchang e
CodeGolfStackExchange
CodeGolfStackExchang e
CodeGolfStackExchan ge
CodeGolfStackExcha nge
CodeGolfStackExch ange
CodeGolfStackExc hange
CodeGolfStackEx change
CodeGolfStackE xchange
CodeGolfStack Exchange
CodeGolfStac kExchange
CodeGolfSta ckExchange
CodeGolfSt ackExchang e
CodeGolfS tackExcha nge
CodeGolf StackExc hange
CodeGol fStackE xchange
CodeGo lfStac kExcha nge
CodeG olfSt ackEx chang e
Code Golf Stac kExc hang e
Cod eGo lfS tac kEx cha nge
Co de Go lf St ac kE xc ha ng e
C o d e G o l f S t a c k E x c h a n g e


Mathematica  61 66 51
Three methods are shown.  Only the first approach meets the time requirement.

1-FindInstance (51 char)
This returns a single solution the equation.
FindInstance[a^2 + b^2 + c^2 + d^2 == #, {a, b, c, d}, Integers] &

Examples and timings
FindInstance[a^2 + b^2 + c^2 + d^2 == 123456789, {a, b, c, d}, Integers] // AbsoluteTiming

{0.003584, {{a -> 2600, b -> 378, c -> 10468, d -> 2641}}}

FindInstance[a^2 + b^2 + c^2 + d^2 == #, {a, b, c, d}, Integers] &[805306368]

{0.004437, {{a -> 16384, b -> 16384, c -> 16384, d -> 0}}}

2-IntegerPartitions
This works also, but is too slow to meet the speed requirement.
f@n_ := Sqrt@IntegerPartitions[n, {4}, Range[0, Floor@Sqrt@n]^2, 1][[1]]

Range[0, Floor@Sqrt@n]^2 is the set of all squares less than the square root of n (the largest possible square in the partition).
{4} requires the integer partitions of n consist of 4 elements from the above-mentioned set of squares.
1, within the function IntegerPartitions returns the first solution.
[[1]] removes the outer braces; the solution was returned as a set of one element.

f[123456]

{348, 44, 20, 4}

3-PowerRepresentations
PowerRepresentations returns all of the solutions to the 4 squares problem.  It can also solve for sums of other powers.
PowersRepresentations returns, in under 5 seconds,  the 181 ways to express 123456789 as the sum of 4 squares:
n= 123456;
PowersRepresentations[n, 4, 2] //AbsoluteTiming

However, it is far too slow for other sums.


Golf Script

1

It took a long time to optimise this code to its most pure, and dare I say it - beautiful form. Such elegance of the language does not come without years of dedicated practice. The program that, without a Zero-Instruction-Set-Computer can literally never be compressed any further. My entire code golf career has been leading to this moment.

I am free. I am alive.

I see the code that underlies the universe.


Pyth, 14 13
jbf!-jQTU2tSQ

Thanks to Jakube for pointing out the new S function.
Try it here.
The online version is too slow to do 1234321. This simply converts the input to each base from 2 to itself and discards the results that contain values other than 0 and 1.
Explanation:
                           : Q=eval(input) (implicit)
jb                         : join on newlines the list...
  f!                       : filter away nonempty values (impliticly named T)
    -jQTU2                 : sewtise difference of number converted to base and range(2)
     jQT                   : convert Q to base T
        U2                 : range(2)
          tSQ              : over the range [2 Q+1)

In addition, this is a (not well golfed now well golfed, again thanks to Jakube) bonus version (20 * .75 = 15):
VQI!-JjQK+2NU2pdKjkJ

Try it here


Jelly, 37 34 bytes

“¢ ¬9£Hæz¥{çb¤S®!‘ṃ€“¡&¦»
¢iµ’,‘ị¢

Try it online!

Takes lowercase input.

-2 thanks to Jonathan Allan.
-1 since it turns out this is valid as a function :)

Thanks to Jonathan Allan (and Dennis), now you can remove the €. Unfortunately, that would be non-competing here.

Detailed algorithm explanation:

We usually start explaining from the bottom (main) link, going down, but here I feel like it's more appropriate to explain from the top.

First, we simply load up the list [1, 32, 7, 57, 2, 67, 17, 92, 3, 94, 19, 119, 4, 109, 9, 34]. This looks like random numbers huh? Well, this is actually a list of base-5-compressed numbers, so we base-5-decompress it. Now it looks like [[1], [1, 1, 2], [1, 2], [2, 1, 2], [2], [2, 3, 2], [3, 2], [3, 3, 2], [3], [3, 3, 4], [3, 4], [4, 3, 4], [4], [4, 1, 4], [1, 4], [1, 1, 4]]. Still random-looking stuff, but this is actually an NESW-mapped list of the sixteen coordinates, so we're not far away from completing the list (Jelly is 1-indexed). Doing the final mapping, we get [['N'], ['N', 'N', 'E'], ['N', 'E'], ['E', 'N', 'E'], ['E'], ['E', 'S', 'E'], ['S', 'E'], ['S', 'S', 'E'], ['S'], ['S', 'S', 'W'], ['S', 'W'], ['W', 'S', 'W'], ['W'], ['W', 'N', 'W'], ['N', 'W'], ['N', 'N', 'W']], which is the complete list we want (Jelly strings are in the form [char1, char2, char3, ...].)

Since we've now built the coordinate list, we work with it. The main link comes into play. First, we load up the list we've built, and then take the index that the input (as command-line argument) coordinate resides in. Then, we pair its predecessor and its successor into a list, and we use them as modular indices into the same list of coordinates to take the coordinate to the left and right of the input respectively. You'd now think we're finally done, but there's in fact one more thing, the separator. This is valid as a function, since 1) You can call it using <integer>Ŀ 2) You're allowed to define other functions as well (like importing modules). Now, we are done. As a full program, this doesn't have a separator, but that's OK, since it works as a function.

Link-by-link code explanation:

¢iµ’,‘ị¢K Main link. Arguments: z = cmd0
¢         Run the helper link niladically (i.e. load the coordinate list).
 i        Find the index of z in the list.
  µ       Start a new monadic chain. Arguments: z = list_index.
   ’      Decrement z.
     ‘    Increment z.
    ,     Pair x and y into [x, y].
       ¢  Run the helper link niladically.
      ị   Take the elements of y at the indices in x.

“¢ ¬9£Hæz¥{çb¤S®!‘ṃ€“¡&¦» Helper link. Arguments: [1, 32, 7, 57, 2, 67, 17, 92, 3, 94, 19, 119, 4, 109, 9, 34]
“¢ ¬9£Hæz¥{çb¤S®!‘        Generate the integer list (the argument).
                    “¡&¦» Literal "newsy".
                  ṃ€      Base-length(y)-decompress every integer in x, then index into y.


Python 3.6, 799 791 bytes

7 bytes saved by Jonathan Frech and motavica

B=frozenset
M=min
X={}
T=lambda s:((x,y)for y,x in s)
N=lambda s:B((x-M(s)[0],y-M(T(s))[0])for x,y in s)
G=lambda s:{(x,y):s&{(x-1,y),(x+1,y),(x,y-1),(x,y+1)}for(x,y)in s}
C=lambda g,s,i=0:i<=len(g)and(len(g)==len(s)or C(g,s.union(*map(g.get,s)),i+1))
F=lambda s:N([(-x,y)for x,y in s])
P=lambda s,i=4:M([N(s),F(s),P(F(T(s)),i-1)],key=list)if i else s
S=lambda s,t=B(),i=0:t|S(s,B().union(u|{p}for u in t for p in s-u if C(G(u|{p}),{p}))if i else B([B([next(iter(s))])]),i+1)if-~i<len(s)else t
def U(s):
 k=P(s)
 if k in X:return
 j=[t for t in S(k)if C(G(k-t),{next(iter(k-t))})];X[k]={P(t):B()for t in j}
 for t in j:X[k][P(t)]|=B([B(P(k-t))]);U(t);U(k-t)
V=lambda s,t:1+M(V(v,w)for u in B(X[s])&B(X[t])for v in X[s][u]for w in X[t][u])if s^t else 1
A=lambda s,t:U(s)or U(t)or V(P(s),P(t))

Try it online!

Usage

A(s, t) takes in two shapes where each shape is given by a list of x, y grid positions.

A helper function to convert the graphical representation to a list of positions is below:

def H(g):
 g=g.split("\n")
 return[(x,y)for x in range(len(g[0]))for y in range(len(g))if"#"==g[y][x]]

Example:

case1_1 = \
""".....
.###.
.#.#.
.###.
....."""

case1_2 = \
"""###..
..#..
..#..
..###
....."""

print(A(H(case1_1), H(case1_2))) # Prints 2

Explanation

The algorithm used here is a little better than brute force by caching sub-shapes. For a given shape, it caches all the ways to split that shape into two contiguous shapes, I then normalise these shapes (shift the coordinates so it starts at the origin, then find a rotation/reflection of it which is used in the cache) and store them in the cache to look up quickly later. All sub-shapes then have their sub-shapes cached as well until it gets to the single block shape.

These sub-shapes are generated by converting it to a graph adjacency list and using a BFS to generate all sub-graphs. We can then filter these subgraphs to ones where the vertices which weren't included are a connected component. Determining whether the graph is connected is done with another BFS.

After the cache is complete, the solution is found by comparing the two shapes to find the sub-shapes that it has in common. Once it has these list of sub-shapes, it takes the pair of sub-shapes left over after removing the common shape and recursively applies the same algorithm again to find the minimum number of blocks needed to reconstruct the shape. This then returns the sub-shape with the minimum of all those values and we have our solution.

I've put an annotated version below to kinda explain what each line is doing.

B=frozenset
M=min
# Shapes are stored as a frozenset of tuples where each tuple represents an (x, y) position
# Cache of shape partitions. This is a two-level dictionary where the outer key is a shape, and the inner key is a sub-shape where the value is a list of the shapes left when the sub-shape is removed.
# there may be multiple shapes in the inner-most list if the sub-shape appears multiple times
X={}
# Transpose list of coords (flip around diagonal axis)
T=lambda s:((x,y)for y,x in s)
# Translate shape so its upper-left corner is at the origin
N=lambda s:B((x-M(s)[0],y-M(T(s))[0])for x,y in s)
# Convert shape to graph in adjacency list form
G=lambda s:{(x,y):s&{(x-1,y),(x+1,y),(x,y-1),(x,y+1)}for(x,y)in s}
# Check if graph is connected given a set of nodes, s, known to be connected
C=lambda g,s,i=0:i<=len(g)and(len(g)==len(s)or C(g,s.union(*map(g.get,s)),i+1))
# Flip shape around vertical axis
F=lambda s:N([(-x,y)for x,y in s])
# Converts shape to the minimal reflection or rotation. rotation is equivalent to transpose then flip.
P=lambda s,i=4:M([N(s),F(s),P(F(T(s)),i-1)],key=list)if i else s
# returns all the contiguous sub-shapes of s that contain the first pos, given by next(iter(s))
S=lambda s,t=B(),i=0:t|S(s,B().union(u|{p}for u in t for p in s-u if C(G(u|{p}),{p}))if i else B([B([next(iter(s))])]),i+1)if-~i<len(s)else t
# updates the sub-shape cache, X, recursively for an input shape s
def U(s):
 k=P(s)
 if k in X:return
 j=[t for t in S(k)if C(G(k-t),{next(iter(k-t))})];X[k]={P(t):B()for t in j}
 for t in j:X[k][P(t)]|=B([B(P(k-t))]);U(t);U(k-t)
# Gets the minimum number of partitions for two shapes
V=lambda s,t:1+M(V(v,w)for u in B(X[s])&B(X[t])for v in X[s][u]for w in X[t][u])if s^t else 1
# The function to run, will update the cache for the two input shapes then return the minimum number of partitions
A=lambda s,t:U(s)or U(t)or V(P(s),P(t))


Matrix property X revisited (or the Joy of X)


Python 2, 19 bytes

lambda t:t-t/100*40

Try it online!


jQuery + JavaScript, 85 bytes

$.get("//api.stackexchange.com/posts/82610?site=codegolf",d=>alert(d.items[0].score))
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

History

-6 bytes because I was using the var data instead of d.
-3 bytes thanks to @msh210
-13 bytes thanks to @CᴏɴᴏʀO'Bʀɪᴇɴ
-4 bytes thanks to @user6188402
-5 bytes thanks to @Suever
-4 bytes thanks to @RobW

Recommended usage

Run snippet.
Upvote.
Run snippet, and be amazed as the number magically increases.

Bonus!!

Who doesn't like a bonus?

$.getJSON("//api.stackexchange.com/posts/" + prompt() + "?site=codegolf",d=>alert(d.items[0].score));
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

Enter the ID into the bonus and it will tell you the score.

Even more bonus!! Run this snippet to automatically run the program, upvote, and run again! (Requires rep > 15, auth). If it doesn't work, please tell me.


I Rot-13 the source code, you Rot-19 the output!

JavaScript (Node.js), 50 bytes

a=>01+"$25hYYXeya=>z!`TcyV01yV~$'zv,'|&&z|xx-$"&&a

Try it online!
Both versions are a function which takes a string as input and returns a string.
ROT13 code:
nJK=>8/1?Buffer(nJK).map(c=>(c-14)%94+33)+'':1/33n

Explanation
Hides tricky characters used in the ROT19 logic inside a string. The quotes map to / characters so it's just a matter of finding where to put them to make it work.


Retina 0.8.2, 61 bytes

+1`(\(((\()|(?<-3>\))|[^()])+(?(3)$)\)|[^()]){2}(?=[^)])
($&)

Try it online! Link includes test cases. Explanation: I'd really like to use a recursive regex (([^()]|\((?1)\)){2})(?=[^)]) here, but .NET only has balancing groups, so it's a bit verbose.

+1`

Repeatedly replace the first match each time. This ensures left-associativity.

(           Either
 \(          Match outer `(`
 (           Either
  (\()        Capture a `(` into $3
 |           Or
  (?<-3>\))   A `)` if it matched an earlier `(`
 |           Or
  [^()]       Something else
 )+          Match as much of the above as possible
 (?(3)$)     But don't leave `(`s unmatched
 \)          Match outer `)`
|           Or
 [^()]       Match something else
){2}        Match the above twice
(?=[^)])    Followed by a non-`)`

Either, a ( followed by a string containing balanced ()s,  followed by a ), or a non-(), twice, followed by a non-). This represents an ambiguous match.

($&)

Wrap the match in disambiguating parentheses.


Haskell, 104 102 99 98 97 95 91 bytes

p x=product[2..x-1]^2`mod`x>0
f[]=1>0
f x|y<-zip[0..]x=or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

Try it online!

Explanation

First we set up a primality test

p x=product[2..x-1]^2`mod`x>0

This uses Wilson's Theorem to determine the primality of an input.

We then declare a base case, which will assert that the empty string is truthy.

f[]=1>0

Now we define the actual function

f x|y<-zip[0..]x=or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

We use a pattern guard to bind zip[0..]x to y, because we need to use it twice later.  We then assert the answer is

or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

[[snd b|b<-y,b/=a]|a<-y] is all of the numbers that are a digit removed from our input.  So we are asserting that at least one of these numbers is truthy for f.  In order to ensure that composite numbers are falsy we add in prime$read x.  If the number is not prime the list will become empty and the any of a empty list is false.


Python 2 (PyPy), O(1) operations

def cmod(a1, a2, b1, b2):
	# Compute p = a * conj(b)
	p1 =   a1 * b1 + a2 * b2
	p2 = - a1 * b2 + a2 * b1

	# Compute the norm-squared of b
	b_nsq = b1 ** 2 + b2 ** 2
	b_nsq_half = b_nsq // 2

	# Do a symmetric mod of d1 and d2 by b_nsq
	# That is, into the interval [-b_nsq_half, +b_nsq_half)
	d1 = (p1 + b_nsq_half) % b_nsq - b_nsq_half
	d2 = (p2 + b_nsq_half) % b_nsq - b_nsq_half

	# Compute r = d / b
	r1 = (d1 * b1 - d2 * b2) // b_nsq
	r2 = (d1 * b2 + d2 * b1) // b_nsq

	return r1, r2

Try it online!

Uses pure integer arithmetic, with no loops or branching or built-in complex numbers. This should easily complete the benchmark of 100,000 random inputs within a small fraction of a second. Porting this to a faster language would be straightforward and likely improve performance.

One possible low-level optimization is the Karatsuba algorithm trick to do complex multiplication using 3 rather than 4 integer multiplications. But, this might not be worth it for such "small" values.


SWI-Prolog, 62 47 41 bytes

X*Y:-X+Y;Y+X;X==Y.
X?Y:-not(X*Y),X*Z,Y*Z.

Prolog isn't too often useful, but when it is it's just beautiful. We'll use a+b to notate that a is friends with b, a*b that a knows b and a?b that b should be suggested to a or not. The first line simply says that X*Y is true if either X+Y, Y+X or X == Y is true. This implements the symmetry of knowing eachother. Asking if there should be a suggestion is incredibly simple. We just ask if there is a Z such that X*Y is false and X*Z and Y*Z is true. Exactly as described in the challenge.

If you save this as a file (e.g. friends.pl) and open SWI-Prolog with this file (prolog -l friends.pl) you get dropped into a REPL.

You can assert friendships like this:

assert('a' + 'b').
assert('a' + 'c').
assert('b' + 'd').

You can check if people know eachother or suggestion should be made:

'a'*'b'.
'a'?'d'.


22 operations

itx = 1/(1+a+b)     #4
nx = -1/(itx+itx)   #4
c = -( 1/(itx + itx + 1/(1+nx)) + 1/(1/(a+nx) + 1/(b+nx)) ) #14

Try it online!

The ops are 10 additions, 7 inverses, 2 negations, and 3 assignments.

So, how did I get this? I started with the promising-looking template of the sum of two double-decker fractions, a motif that had appeared in many previous attempts.

c = 1/(1/x + 1/y)  +  1/(1/z + 1/w)

When we restrict the sum to x+y+z+w=0, a beautiful cancellations occur, giving:

c = (x+z)*(y+z)/(x+y),

which contains a product. (It's often easier to get t*u/v rather than t*u because the first has degree 1.)

There's a more symmetric way to think about this expression. With the restriction x+y+z+w=0, their values are specified by three parameters p,q,r of their pairwise sums.

 p = x+y
-p = z+w
 q = x+z
-q = y+w
 r = x+w
-r = y+z

and we have c=-q*r/p. The sum p is distinguished as being in the denominator by corresponding to the pairs (x,y) and (z,w) of variables that are in the same fraction.

This is a nice expression for c in p,q,r, but the double-decker fraction is in x,y,z,w so we must express the former in terms of the latter:

x = ( p + q + r)/2
y = ( p - q - r)/2
z = (-p + q - r)/2
w = (-p - q + r)/2

Now, we want to choose p,q,r so that c=-q*r/p equals a*b. One choice is:

p = -4
q = 2*a
r = 2*b

Then, the doubled values for q and r are conveniently halved in:

x = -2 + a + b
y = -2 - a - b
z =  2 + a - b
w =  2 - a + b

Saving 2 as a variable t and plugging these into the equation for c gives a 24-op solution.

#24 ops
t = 1+1   #2
c = 1/(1/(-t+a+b) + 1/-(t+a+b))  +  1/(1/(-b+t+a) + 1/(-a+b+t)) #1, 10, 1, 10

There's 12 additions, 6 inverses, 4 negations, and 2 assignments.

A lot of ops are spent expressing x,y,z,w in terms of 1,a,b. To save ops, instead express x in p,q,r (and thus a,b,1) and then write y,z,w in terms of x.

y = -x + p
z = -x + q
w = -x + r

Choosing

p = 1
q = a
r = b

and expressing c with a negation as c=-q*r/p, we get

x = (1+a+b)/2
y = -x + 1
z = -x + a
w = -x + b

Unfortunately, halving in x is costly. It needs to be done by inverting, adding the result to itself, and inverting again. We also negate to produce nx for -x, since that's what y,z,w use. This gives us the 23-op solution:

#23 ops
itx = 1/(1+a+b)     #4
nx = -1/(itx+itx)   #4
c = -( 1/(1/(-nx) + 1/(1+nx))  +  1/(1/(a+nx) + 1/(b+nx)) ) #15

itx is 1/(2*x) and nx is -x. A final optimization of expressing 1/x as itx+itx instead of the templated1/(-nx) cuts a character and brings the solution down to 22 ops.


CJam, 3165 / 10³ = 3.165

{
"Do not repeat yourself"]sX/z_&
6)H7+G0+B8+H7+E8+G0+D8+9)C8+9)A7+E8+G0+B9+H7+K7+D8+J7+9)A8+I6+]{c}/
"Do not repeat yourself"]sZ/z_&

"Do not repeat yourself"]s3D&3D&3D&3D&3D&/z_&

"Do not repeat yourself"]s1F&1F&1F&1F&1F&1F&1F&/z_&

"Do not repeat yourself"]sB/z_&

"Do not repeat yourself"]sD/z_&

"Do not repeat yourself"]sF/z_&

"Do not repeat yourself"]sH/z_&

"Do not repeat yourself"]sJ/z_&
}`1>W<N/
e# Uncomment this line to count total length:
e# ee{~,*}%:+p [L]
ri\1$=f*

Works for inputs 1, 2, 3, 5, 7, 11, 13, 15, 17, 19.

Total length is 3165.

The program for input 2 is from here, credits to Super Chafouin.

Example: output for 11

"""""""""""DDDDDDDDDDDooooooooooo           nnnnnnnnnnnooooooooooottttttttttt           rrrrrrrrrrreeeeeeeeeeepppppppppppeeeeeeeeeeeaaaaaaaaaaattttttttttt           yyyyyyyyyyyooooooooooouuuuuuuuuuurrrrrrrrrrrssssssssssseeeeeeeeeeelllllllllllfffffffffff"""""""""""]]]]]]]]]]]sssssssssssBBBBBBBBBBB///////////zzzzzzzzzzz___________&&&&&&&&&&&

Explanation:

"""""""""""..."""""""""""    Push five empty strings, a long string,
                                and five more empty strings.
]]]]]]]]]]]sssssssssss       Collect them all in a list. Put that list in
                             10 more layers of list, for good measure.
                             Convert this to a string, to just get the long one.
BBBBBBBBBBB///////////       Split into chunks of size
                                11/(11/(.../(11/(11/11))))) = 11.
                             This gets us:
                                ["DDDDDDDDDDD" "ooooooooooo" ...]
zzzzzzzzzzz                  Transpose eleven times, i.e. once. We now have:
                                ["Do not..." "Do not..." ... "Do not..."]
___________&&&&&&&&&&&       Push eleven more copies, and get the unique elements.
                             This gets us:
                                ["Do not..."]


All possible ways to interleave two strings

Haskell, 53 48 bytes

a%""=[a]
a%b=[x:t|(x:y,z)<-[(a,b),(b,a)],t<-y%z]

Defines a function % for which a%b with strings a,b gives a list of strings.
Given two strings, we choose one of the two to take the first character from. We then recurse on the remainder of two strings, prepending that character to each result.
When one of the string is empty, the only possible result is the other string. ""%""=[""] would also suffice, but's it's longer.

53 bytes:
a@(b:c)%d@(e:f)=((b:)<$>c%d)++((e:)<$>a%f)
a%d=[a++d]

Defines a function % for which a%d with strings a,d gives a list of strings.
The function is defined recursively. If we take a character from the first string, then it must be prepended to each result of the recursive call on the remained of the first string with the second string. Symmetrically for the other string.
For the base case, if one of the strings is empty, the result is a single-element list of their concatenation. This is shorter than two cases for each string being empty.


R, 938 896  858 952 bytes

function(N,M,m){U="We tried...
"
L=length
A=matrix
W=which
K=sum
S=sample
G=unique
H=function(s,p=s-1){Y=S(c(s-j,s+j,p*(p%%j>0),(s+1)*(s%%j>0)))
Y[Y>0&Y<=k]}
C=function(v,z=W(r==v))K(z%%j<2,z-j<0,(z+j)>k)
m=A(strsplit(m,"")[[1]],1)
i=W(m<0)[1]-1
m=((t(A(m,i+1))[,1:i]>0)-.5)*2
if((K(m)<M&(N-M)<1)|K(m>0)<(3*M))cat(U) else{j=max(1,nrow(m))
k=i*j;w=g=T
while(w<9&g){Z=R=N;Q=M;b=0
r=A(0,j,i)
while(b<9&g){s=W(r<1)
s=s[S(L(s))][1:min(L(s),R)]
r[s]=1:L(s);a=0
while(K(r<1)>0&a<(k^2)){a=a+1
s=S(W(r>0&r<=R),1);p=r[s]
Y=H(s)
Y=Y[r[Y]<1]
if(L(Y)){Y=Y[order(m[Y])]
if(K(m[r==p]>1))r[Y[1]]=p else r[Y[L(Y)]]=p}}
if(a<(k^2)){for(v in 1:R){if(K(m[r==v])>0){r[r==v]=max(k,max(r))+1
Q=Q-1;Z=Z-1}}
if(Q<1){g=F
for(v in 1:R)r[r==v]=max(k,max(r))+1
for(v in G(c(r)))g=g|(K(r==v)<4)|(L(G(r[H(W(r==v))]))+C(v))<3}}
b=b+1;r[r<=R]=0;R=Z}
w=w+1}
if(g)cat(U) else{u=G(c(r))
for(v in 1:L(u))r[r==u[v]]=v
cat(paste(apply(A(LETTERS[r],j,i),1,paste,collapse=""),collapse="
"))}}}

Try it online!

A massive >900 >800 (nope!) >900 bytes solution.
The code works as follows. Let N be the number of electoral districts and M the minimum number of district where 1 wishes to have a majority.

First, the code randomly assigns N districts to different groups. Next, it randomly expands them, i.e. adds a district to a randomly selected group, ensuring that the district is next to a district already belonging to that group. In the expansion process, it gives precedence to a district with a 1 majority, if the district group is not yet a full 1 majority; if the group is already a certain 1 majority, then it gives precedence to a 0 district. It continues until all districts have been assigned.

Every group where there is a majority for the 1 party is stored, and its districts are locked. If there are at least M groups with a majority of 1, then everything is good and we can print the result we can check whether there are at least 4 districts in each group. If the cutoff of 4 districts is met, then we can happily print the result. Otherwise, the code tries to reassign the districts that are not locked to as many groups as available, i.e. N - #stored-groups.

The codes tries a few times (9 times). If it fails, it resets everything and starts again. It does so for other 9 times before giving up and printing "we tried...".

If the code does not succeed at first, try again a few times. I tuned the number of repetitions such that it can run in TIO under a minute. However if there is a solution, this code can (eventually) find it. The randomness part of the algorithm gives a non-zero probability that, if there is a solution, it can find it. The limited number of trials is the only limiting factor to success.

EDIT: added the control that no district group can be fully surrounded by just another one, unless the district group has districts on the edge of the given square. I think I missed it at first.


Write two single line functions to encode and decode base64

Python 2, 437 characters

As a first improvement to your Python solution, you can cut down on the references to the long string of characters 'abc...ABC...0123456789+/':

def fromb64(m):
    return (lambda A:''.join([chr(int(w,2)) for w in [(''.join([''.join([bin(A.index(x))[2:].zfill(6) for x in m if x in A])[y:y+8] for y in range(0,len(''.join([bin(A.index(x))[2:].zfill(6) for x in m if x in A])),8)])+'a')[:-(len(m)-len(m.replace('=','')))*2-1][z:z+8] for z in range(0,len(''.join([bin(A.index(x))[2:].zfill(6) for x in m if x in A])),8)] if len(w)==8]))('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/')

This is just (lambda A: {{what you did, but with that string replaced by A}})(that string).


Mathematica 450
Date[] calls for the current date and time. [[{4,5}]] returns the hour and minutes
f[]:=f[Date[][[{4,5}]]];
f[{h_,m_}]:=Module[{p,w,s},
p@h1_:=Which[0<h<12," in the morning.",12<h<18," in the afternoon.",18<h<24, " in the evening."];
s[t_]:=WolframAlpha["spell "<>ToString@t,{{"Result",1},"Plaintext"}];
w=s[h~Mod~12]<>p@h;
Which[
m==0, Switch[h,12, "noon", 0|24,"midnight",_,s[h~Mod~12]<>p@h],
m==15,"a quarter past "<>w,
m==30,"half past "<>w,
m==45,"a quarter to "<>s[h~Mod~12+1]<>p@h,
m<30,s@m<>" minutes after "<>w,
m>29,s[60-m]<>" minutes before "<>s[h~Mod~12+1]<>p@h]]

Current Time
f[]

"ten minutes past three in the afternoon."

Specific times
f[{4, 45}]
f[{10, 30}]
f[{11, 0}]
f[{12, 0}]
f[{13, 15}]
f[{15, 0}]
f[{22, 17}]
f[{24, 0}]

"a quarter to five in the morning."
"half past ten in the morning."
"eleven in the morning."
"noon"
"a quarter past one in the afternoon."
"three in the afternoon."
"seventeen minutes past ten in the evening."
"midnight"


Python 3, 80 bytes

y=lambda d,s=0,p=[],f=0:f in p and s or min(y(d,s+d[f][t],p+[f],t)for t in d[f])

Try it online!

Takes input as a dictionary keyed by node id.  The entries are a dictionary of neighbors and the number of people on the track between a node and the neighbor.  E.g., for the first test case:

{0: {1: 0}, 1: {2: 5, 3: 1}, 2: {2: 0}, 3: {3: 0}}

0 is the start node, 1 is node 'a', 2 is node 'b', etc.


Ninja Assassins - which ninja stays alive?

Python 2, 30 bytes

lambda n:int(bin(n)[3:]+'1',2)

Takes the binary expansion of n and moves the initial 1 to the end.


Write a pluralization function for Russian

Python 2, 36 bytes

lambda n:'5521'[n%~9/-3>>n/10%~9/-9]

Try it online!

Same length arithmetically:

lambda n:5/(n%~9/-3>>n/10%~9/-9or 1)

Let's first look at simpler code that doesn't account for teens.

lambda n:'5521'[n%~9/-3]

Here, we want a mapping of the one's digit to an output that works like

[5, 1, 2, 2, 2, 5, 5, 5, 5, 5][n%10]

But, rather than take n modulo 10 (%10), we can do n%-10, which maps to the intervals [-9..0] to give remainders:

> [n%~9 for n in range(10)]
[0, -9, -8, -7, -6, -5, -4, -3, -2, -1]

This is promising because the first two entries 0 and -9 are far apart, and they need to be sent to different outputs. Also, -10 can be shortened to ~9.

From here, floor-dividing by /-3 gives chunks of 3 with the right starting spot

> [n%~9/-3 for n in range(10)]
[0, 3, 2, 2, 2, 1, 1, 1, 0, 0]

To get the desired output, we now just need to map 0->5, 1->5, 2->2, 1->1, which we do with the string selection '5521'[_].

Now, we also need numbers ending in 11 to 15 to always give 5. We first do this by detecting whether then tens digit is 1. Taking n/10 to remove the last digit, we then apply %~9 as before to get the outcomes

[0, -9, -8, -7, -6, -5, -4, -3, -2, -1]

for respective final digits. The digit of 1 that we want to detect is mapped to the extremal value -9. Floor-dividing by -9 turns it to 1 and everything else to 0.

> [k%~9/-9 for k in range(10)]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

Finally, we make this indicator being 1 always give output 5. This is done by bit-shifting the result of n%~9/-3 right by the indicator. The result of 0,1,2,3 always bit-shifts right to 0 or 1, which gives an output of 5 as desired.


Determine the cyclical shift your program is in

brainfuck, 3 bytes

.++

Try it online!

how it works: it's really simple, actually. The internal memory is initialized at 0 so we output (with .) the original cell and we get 0. By shifting the program, we are shifting memory increments (done with +) to before the output, so each byte shifted corresponds to one more increment, and hence we increase the counter.


Using ".. .."wd instead of {".."".."}

If you need a Block of Strings such as {"abc" "def"} it is shorter to use the words built-in: "abc def"wd.

Using ra to parse fail-safe

ps will fail if the input is not properly formated or might produce unwanted results. In such cases, using ra is better.

blsq ) "5,"ra
5
blsq ) "5,"ps
{5 ,}
blsq ) "5a"ps
{ERROR: (line 1, column 3):
unexpected end of input}
blsq ) "5a"ra
5

Using , to drop stdin

, is defined as a pop instruction if and only if there is exactly one element on the stack. It's used to pop STDIN from the stack when it's not needed but there (such as for example is the case on anarchy golf).

Abusing the way mo is defined

mo is defined as 1R@\/?* and is used to generate a Block containing multiples of N:

blsq ) 3mo9.+
{3 6 9 12 15 18 21 24 27}

Yet due to side effects of ?* you can do some nasty things with it if you don't provide a number:

blsq ) "1"mo9.+
{"11" "21" "31" "41" "51" "61" "71" "81" "91"}

blsq ) {1 2 3 4}mo9.+
{1 4 9 16}


MATL, 5 bytes
EGqXn

Try it online, or verify all test cases!
Explanation:
E       #Double the input
 Gq     #Push "input - 1"
   Xn   #Calculate "nchoosek" on the two numbers


Python 3, 590 639 characters

from itertools import count as C
D=lambda n,t='1':bin(n).count(t)
Y=range
def O():
 for n in C(0):yield from bin(n)[2:]
def B():
 s=i=0
 while 1:
  i+=s
  for j in Y(i,i+s+1):yield j
  s+=2;i+=s-1
def s(i):return D(i)==1
def F():
 a=[1]*3
 for n in C(3):a+=[a[n-a[n-1]]+a[n-a[n-2]]];yield a[-1]
L,R=input().split()
J=[x for x,U in zip([F(),(n for n in C(0)if s(D(n,'0')-1)and s(D(n))),B(),(i for i,c in enumerate(O())if'1'>c)],"{0:04b}".format(int(L)))if U>'0']
X=[set()for _ in J]
M=[]
Z=int(R);K=1
while len(M)<Z:
 for x,j in zip(X,J):x.add(next(j))
 for _ in Y(K):X[0].add(next(J[0]));K+=1
 M=X[0]
 for x in X:M=M&x
print(sorted(M)[:Z])

This is the straight-forward solution: use generators to define each of the infinite sequences, and so long as the intersection isn't large enough, add a step to each sequence.

To account for the non-monotonically-increasing Hofstadter sequence: at each step I generate twice as many for that sequence, e.g. 1, then 2, 4, 8, 16, 32, etc. I think that satisfies the bound stated in the question, and it's still fast enough for all the test cases presented there.


Vim, 37 bytes
3iLa <esc>snd<esc>gs:s/./&<C-v>u336/g
A Moonlight

A fairly straightforward solution.
Here is an animation of it running:


Print the difference in the Thue-Morse sequence

Python 3 2, 104 92 88 84 bytes

This is a pretty rudimentary solution based on building a ternary Thue-Morse sequence from scratch. This sequence is identical to the one being asked, though someone else will have to write a more thorough explanation of why that is. At any rate, this sequence is only a trivial modification of this one, A036580.

Edit: Changed the for loop into a list comprehension, changed from a function to a program, and changed the whole thing to Python 2. Thanks to Dennis for golfing help.

n=input()
s="2"
while len(s)<n:s="".join(`[1,20,210][int(i)]`for i in s)
print s[:n]


CJam, 142
You didn't ask for an optimal, deterministic or fast solution, so here you go:
qN%Sf%::c_s_&:Aff#:E;{A{;[DmrDmr]2f*}%:C;E{Cf=~.-:*}%0m1{E{Cf=$~1$.-_:g:T\:+,1>\ff*\f.+T0="-|"=f+~}%CA.++:L2f<__&=!}?}gS25*a25*L{~2$4$=\tt}/N*

Try it online
This generates random coordinates for each letter and tests if the layout is acceptable (edge letters lining up and no intersections), until it is. It gets mind-numbingly slow as you add more edges.
The two D letters in the code specify the maximum x and y coordinates; I picked D (=13) because I think it should be sufficient for all cases, feel free to prove me wrong. But you can change them to other values to speed up the program, e.g. the 2nd example should finish within a minute or two if you use 3 and 4 instead.


CJam, 17 16 bytes

{`"_~"+Wq~g#%}_~

Test it here.

A fairly straight-forward modification of the standard quine. Other solutions for 17 bytes:

{`"_~"+q~{W%}&}_~
{`"_~"+q~!2*(%}_~

If I can assume that the input is only 0 or 1 (as a stand-in for a boolean, which there is no dedicated type for in CJam), I get 15 by omitting the g:

{`"_~"+Wq~#%}_~

Explanation

{`"_~"+  e# Standard generalised quine framework. Leaves the source code on the stack.
  W      e# Push a -1.
  q~     e# Read and evaluate input.
  g      e# signum, turning truthy values into 1 (leaving 0 unchanged).
  #      e# Power. -1^0 == 1, -1^1 == -1.
  %      e# Select every Nth element: a no-op for 1 and reverses the string for -1.
}_~


Haskell, 203 bytes

Nobody had done this by implementing a small regex engine yet, and I felt like it had to be done. This obviously won't win. but I'm hoping it will inspire someone to write an even more golfed regex engine.

I've rewritten my solution to avoid directly parsing the regular expression into its AST. Instead, the parsing process constructs a function that is used to match a string against the input regex.

The main function is (&) :: String -> String -> Bool which takes a string representation of a regex and a string to test, returning a boolean value. This calls to the next function which handles most of the work in parsing the regex and matching the string.

Function p :: String -> ([String] -> [String], String) takes a string representation of a regex and returns as the first element of a tuple a function that returns a list of all possible unmatched suffixes of strings in the input list after satisfying the regex parsed from the input string. The regex fully matches the string if the empty string is contained in the list of possible unmatched suffixes.

r&s=elem""$fst(p r)[s]
p(c:t)|c>'`'=t% \s->[t|h:t<-s,c==h]|c>'^'=t%id|(l,o:t)<-p t,(r,_:u)<-p t=u%last(r.l:[\s->r s++l s|o>'+'])
m#s=s++filter(`notElem`s)(m s)
('*':t)%m=t%until(\s->s==m#s)(m#)
s%m=(m,s)

Try it online!

To get rid of one byte, I replaced import Data.List; m#s=nub$s++m s with m#s=s++filter(`notElem`s)(m s). These functions aren't equivalent if there are duplicate elements in either s of m s. The new function does, however, remove all elements from m s that already exist in s, so until still terminates once no new suffixes are discovered by the application of m.

Ungolfed Code

import Data.List

match :: String -> String -> Bool
match r s =elem ""$(fst $ parseRegex r)[s]

parseRegex :: String -> ([String] -> [String], String)
parseRegex ('_':t) = parseKleene id t
parseRegex (c:t) | c >= 'a' = parseKleene (>>=p) t
  where p (c':t')| c==c' = [t']
        p _ = []
parseRegex ('(':t) =
  let (l, (o:t')) = parseRegex t in
  let (r, (_:t'')) = parseRegex t' in
  parseKleene (if o=='+' then (r.l) else (\ss-> (r ss)++(l ss))) t''

parseKleene :: ([String] -> [String]) -> String -> ([String] -> [String], String)
parseKleene p ('*':t) = parseKleene p' t
  where
    p' ss
      | ss' <- nub$ p ss,
        ss /= ss' = ss ++ (p' ss')
      | otherwise = ss
parseKleene p s = (p,s)

GolfScript, 198 bytes

I was able to beat my Haskell solution by implementing the first algorithm I tried in GolfScript instead of Haskell. I don't think it's interesting enough for a separate answer, so I'll just leave it here. There are likely some golfing opportunities since I learned GolfScript just for this.

This solution is in the form of a block that expects the test string on the top of the stack followed by the regex string.

{[.;]\1+{(.96>{0[\]}{2%0{r\(\r\:s;[@]s(;\}i}{if}:i~\{(.3%}{;\2[\]\}until[.;]\+\}:r~\;{.{(.{.4%{2%{)@\m\)\;m}{)\;{.@.@m 1$|.@={\;}{\o}i}:o~}i}{;)@.@m@@\)\;m|}i}{;(:c;;{,},{(\;c=},{(;}%}i}{;}i}:m~""?}

Try it online!


Python 2, 92 91 89 88 bytes

a=()
i=0
exec"x=0\nwhile set(`x`)&set(`i`)or x in a:x+=1\na+=x,;i+=1;"*-~input()
print a

Try it online!

Prints a list of the first n+1 numbers

Different approach, which is a lot faster:

Python 2, 96 bytes

n=input()
r=range(9*n)
i=0
exec"x=0\nwhile set(`r[x]`)&set(`i`):x+=1\nprint r.pop(x),;i+=1;"*-~n

Try it online!


Sort a list of numbers on the λ-calculus

I've managed to beat my own mark:

sort = λabcd.a(λef.f(λghi.g(λj.h(λkl.kj(ikl)))(hi))e(λgh.h))
       (λe.d)(λe.b(λf.e(f(λghi.hg)(λgh.cfh))))

There is a caveat, though - this term must receive an additional argument with the maximum size of naturals that are considered. For example, sort 4 [1,7,3,6,5] will return [1,3], ignoring anything above or equal 4. Of course, you could just give infinity (i.e., the Y-combinator):

sort = λbcd.(λfx.f(x x))(λfx.f(x x))(λef.f(λghi.g(λj.h(λkl.kj(ikl)))
       (hi))e(λgh.h))(λe.d)(λe.b(λf.e(f(λghi.hg)(λgh.cfh))))

And it would sort any list of natural numbers, but this term obviously doesn't have a normal form anymore.


Python 3, 100 99 bytes

a recursive solution

f=lambda s:s[0]+s[-1]+min(2*s[1],s[0]+s[-2])+f(s[:-2])if s.sort()or 3<len(s)else sum(s[len(s)==2:])

Thanks to @xnor for this paper

Thanks to @lirtosiast save 2 bytes,  @movatica save 1 bytes and to @gladed pointing at that my previous solution doesn't work

use the following trick to evaluate something in lambda function s.sort() or s  here we compute sort and return the result of the test s.sort()or len(s)>3

Ungolfed

def f(s):
    s.sort()                                   # sort input in place
    if len(s)>3:                               # loop until len(s) < 3
        a = s[0]+s[-1]+min(2*s[1],s[0]+s[-2])  # minimum time according to xnor paper
        return  a + f(s[:-2])                  # recursion on remaining people
    else:
        return sum(s[len(s)==2:])              # add last times when len(s) < 3

Results

>>> f([3, 1, 6, 8, 12])
29
>>> f([1, 2, 5, 8])
15
>>> f([5])
5
>>> f([1])
1
>>> f([1, 3, 4, 5])
14


LaTeX, 269 bytes
\input tikz.tex\let\s\pgfmathsetmacro\pgfmathsetseed{\number\pdfrandomseed}\def\u#1{\uppercase{#1}}\def\f
How do I #1?{\s\n{random(0,9)}\s\m{int(\n+1)}How to #1 in \m~easy
step\ifnum\m>1s!\\\\\foreach\i in{1,...,\n}{Step \i~- Do not #1.\\}\else!\\\\\fi
Step \m~- \u#1.}

Random numbers aren't very nice to handle in LaTeX.
Example output:


Brachylog, 12 bytes

{^a₀.&b~b^}ᶜ

Try it online!

Explanation

{^a₀.&b~b^}ᶜ
{         }ᶜ  Count the number of ways the following can succeed:
  a₀            A prefix of
 ^                the first {input} to the power of the second {input}
    .&          produces the same output with the same input as
       ~b         any number
         ^        to the power of
      b           all inputs but the first (i.e. the second input)


Find the fastest swim relay (shortest path of unique nodes and types)

Meh, I'm no Python programmer by any stretch of the imagination. Hell, some would even hesitate to call me a programmer. But as nobody else has answerred this, why not post my solution? If anything else, it was fun just to brush up on the very Python basics:

swimmers = [{'Fly': 10, 'Breast': 48.26, 'Free': 28.43, 'Back': 34},
{'Fly': 47.51, 'Breast': 24, 'Free': 28.47, 'Back': 10},
{'Fly': 26, 'Breast': 46.44, 'Free': 10, 'Back': 30},
{'Fly': 37.81, 'Breast': 10, 'Free': 24, 'Back': 49},
{'Fly': 38.31, 'Breast': 29, 'Free': 20, 'Back': 10}]

bestTime = float('inf')

for fly in range(len(swimmers)):
    for breast in range(len(swimmers)):
        for free in range(len(swimmers)):
            for back in range(len(swimmers)):
                if len(set([fly,breast,free,back])) > 3:
                    current = swimmers[fly]['Fly'] + swimmers[breast]['Breast'] + swimmers[free]['Free'] + swimmers[back]['Back']
                    if current < bestTime:
                        bestTime = current

print bestTime


Python 3, 672 bytes

e=enumerate;H='H';F='F'
def f(m):
	q=m[0];h=len(m);w=len(q);o=0;g=lambda m,c:{(k,l)for i,r in e(m)for j,v in e(r)for k in range(i-1,i+2)for l in range(j-1,j+2)if v==c and k>=0and k<h and l>=0and l<w};n=lambda m,c,d:[[c if(k,l)in g(m,c)-g(m,d)else m[k][l]for(l,v)in e(r)]for(k,r)in e(m)];s=lambda m:H in[q]+[m[h-1]]+[r[0]for r in m]+[r[w-1]for r in m];l=lambda m:all(H not in r for r in m)
	while 1:
		a=m
		while not(s(a)or l(a)):a=n(n(a,H,F),F,1)
		if l(a):return o
		else:o+=1;z(m,a,h,w)
def z(m,a,h,w):
	for i in(0,h-1):
		for j,v in e(a[i]):
			if v==H:m[i][j+(h-1)//2]=F;return
	for j in(0,w-1):
		for i,v in e(r[j] for r in a):
			if v==H:m[i+(w-1)//2][j]='F';return

Try it online!

It's very long (I've done my best to golf it), and the solution is not optimal. Here is the general idea:

First, let's see if the farmer burns in the original situation. The matrix a is filled with Fs when the fire grows and with Hs if the farmer can reach a position (a=n(n(a,H,F),F,1)).
If the farmer escapes (s(a)), look a the border of a. There must be at least a H. It takes (h-1)/2 ticks to reach the top or the bottom, and (w-1)/2 ticks to reach the left or right border. As soon as we find a H on the top, we put a fire at (h-1)/2 cases on its left. In (h-1)/2 ticks, an F will be there and it may also "burn" other Hs. The same applies for the left and right borders.

The solution is not optimal because:

there are some edge cases, in particular when a fire will burn two borders of the field.
considering top and bottom borders before right and left borders is not necessarily the best solution
going from left to right and top to bottom to find a H is not necessarily the best solution.


Multiple, Lit Plume, Mute Pill and so on

Python 2, 48 bytes

lambda k,N:[k*(10**N**k+10**i)for i in range(N)]

Try it online!

For example, k=12,n=4 produces this list of numbers, written out in lines for clarity, with the ...'s hiding a big string of zeroes:

1200...0000012
1200...0000120
1200...0001200
1200...0012000

So, we have a prefix of k, followed by another k in a position that moves one place left each time, and the rest zeroes. We need the prefix because leading zeroes aren't allowed for the anagrams, so we make it so that all the outputs have the same number of digits.

We leave enough zeroes to ensure that the right string to never bump into the left one. N**k zeroes more than suffices for this, giving extremely big numbers; N+k or even N+log_10(k) would be enough. Note that Python right-associates 10**N**k as 10**(N**k).

Unfortunately this variable bound doesn't lend well to recursive solutions that update k as they go. An upper bound on how big k can be, even if enormous, would simplify this.


Pyth, 28 bytes
jbc*\#Qho.a,,N*NJ_/_QN,JQ_SQ

Try it online.
The crux is that I sort potential m on the following property:
(m - ceil(k/m))^2 + (m*ceil(k/m) - k)^2

Note the total absence of n. The total shape is defined merely by m. Then I transform the above property once more, and my final sorting weight is defined as the Euclidean distance between the following two points:
(m, m*ceil(k/m)) and (ceil(k/m), k)

This changes the weight values, but not their ordering.


Python 2, 23 22 bytes

Thanks @xnor for figuring out a really cool way to convert the seed to -1 or -2, which saved 1 byte.

lambda s,n:`n+9`[2/~s]

Try it online!

Input: The seed s (non-negative) and an index n (positive).
Output: The element at the nth index (the sequence is one-indexed)

If the seed is positive, the sequence is 0123456789 repeated infinitely.
If the seed is 0, the sequence is: 1111111111 2222222222 ... 9999999999 0000000000 (where each digit repeats 10 times) repeated infinitely.

How

`n+9` creates a string from a number that has at least 2 digits.
2/~s evaluates to -2 if s is 0, or -1 if s is positive
Thus `n+9`[2/~s] takes the last digit (unit digit) of \$n+9\$ if s is positive, or the second to last digit (ten digit) if s is 0.


Python 2, 63 bytes

p=s='print-'
for x in input():s+='*+-'[cmp(x,p)]+`x`;p=x
exec s

Constructs and evals the expression string. The arithmetic symbol is chosen by comparing the previous number p to the current one x. The symbol is appended followed by the current number.
The first number is handled with a clever trick from Sp3000. The initial value of p is set to a string, which is bigger than any number and therefore causes a - before the first number. But, s is initialized to print- at the same time that makes the result start with print-- (thanks to xsot for saving 2 bytes by initializing with print.)


Maximal number of regions obtained by joining n points around a circle by straight lines

Mathematica, 23 bytes
Tr@Binomial[#,{0,2,4}]&

Uses the formula in the question.


JavaScript (ES6), 105 102 101 bytes

c=>/[~`0-9!@#-&^(-+_=-]/.test(c)+/[asdfghjkl;:'"\n]/i.test(c)*3+/[zxcvbnm,<.>/?]/i.test(c)*4||++c*7^2

Explanation

In JavaScript test returns a boolean which acts the same as 1 or 0 so I multiply them by their row. Testing for row 2 took the most bytes so I used that one as the default if no others matched.

c=>
  /[~`0-9!@#-&^(-+_=-]/.test(c)   // row 1 regex
  +/[asdfghjkl;:'"\n]/i.test(c)*3 // row 3 regex
  +/[zxcvbnm,<.>/?]/i.test(c)*4   // row 4 regex
  ||++c                           // space ++ = 1, any character on row 2 ++ = NaN
    *7^2                          // 7 XOR 2 = 5, NaN XOR 2 = 2

Test

var solution = c=>/[~`0-9!@#-&^(-+_=-]/.test(c)+/[asdfghjkl;:'"\n]/i.test(c)*3+/[zxcvbnm,<.>/?]/i.test(c)*4||++c*7^2
<textarea id="input">-</textarea>

<button onclick="result.textContent=solution(input.value)">Go</button>


APL(Dyalog), 16/20

Losing to GS again...

'⍞,⍨⊂⎕UCS',⎕UCS⍞

This may break the "no cryptography" rule. ⎕UCS is a function to convert characters to unicode code points and back.

Example
First input: Hello
First output: ⍞,⍨⊂⎕UCS 72 101 108 108 111
Second input: John
Second output: Hello John (Note the space before "Hello")

'⎕AV[','],⊂⍞',⍨⎕AV⍳⍞

Similar idea with the cryptography is manually implemented: Convert to/from index of some pre-defined character array (⎕AV) which includes all upper and lower alphabets.


Find the maximum determinant for each size Toeplitz matrix

J

Update: Improved code to search over half the values. Now calculates n=12 comfortably within 120 seconds (down from 217s to 60s).

You will need the latest version of J installed.

#!/usr/bin/jconsole

dim =: -:@>:@#
take =: i.@dim
rotstack =: |."0 1~ take
toep =: (dim (|."1 @: {."1) rotstack)"1
det =: -/ . * @: toep
ps =: 3 : ',/(0 1 ,"0 1/ ,.y)'
canonical =: #. >: [: #. |. " 1

lss =: 3 : 0
  shape =. (2^y), y
  shape $ ,>{;/(y,2)$0 1
)

ls =: (canonical@:lss) # lss
ans =: >./ @: det @: ls @: <: @: +:

display =: 3 : 0
echo 'n = ';y;'the answer is';ans y
)
display"0 (1 + i.13)
exit''

Run this and kill when two minutes are up. My results (MBP 2014 - 16GB of RAM):

┌────┬─┬─────────────┬─┐
│n = │1│the answer is│1│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬─┐
│n = │2│the answer is│1│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬─┐
│n = │3│the answer is│2│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬─┐
│n = │4│the answer is│3│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬─┐
│n = │5│the answer is│5│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬─┐
│n = │6│the answer is│9│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬──┐
│n = │7│the answer is│32│
└────┴─┴─────────────┴──┘
┌────┬─┬─────────────┬──┐
│n = │8│the answer is│56│
└────┴─┴─────────────┴──┘
┌────┬─┬─────────────┬───┐
│n = │9│the answer is│125│
└────┴─┴─────────────┴───┘
┌────┬──┬─────────────┬───┐
│n = │10│the answer is│315│
└────┴──┴─────────────┴───┘
┌────┬──┬─────────────┬────┐
│n = │11│the answer is│1458│
└────┴──┴─────────────┴────┘
┌────┬──┬─────────────┬────┐
│n = │12│the answer is│2673│
└────┴──┴─────────────┴────┘

Total run time = 61.83s.

Just for fun

┌────┬──┬─────────────┬────┐
│n = │13│the answer is│8118│
└────┴──┴─────────────┴────┘

This took approximately 210 seconds on its own.


R, 47 bytes

function(v,a=v[v>0],b=sort(a))all(v[a]==b&a!=b)

Try it online!

Unrolled code and explanation :

f=
function(v){          # v vector of tunnel indexes (1-based) or values <= 0

  a = v[v>0]          # get the tunnel positions

  b = sort(a)         # sort the tunnel positions ascending

  c1 = v[a]==b        # get the values of 'v' at positions 'a'
                      # and check if they're equal to the sorted positions 'b'
                      # (element-wise, returns a vector of TRUE/FALSE)

  c2 = a != b         # check if positions 'a' are different from sorted positions 'b'
                      # (to exclude tunnels pointing to themselves, element-wise,
                      #  returns a vector of TRUE/FALSE)

  all(c1 & c2)        # if all logical conditions 'c1' and 'c2' are TRUE then
                      # returns TRUE otherwise FALSE
}


The shortest way to find one unique value when all other values are the same

Python 3, 27 bytes

lambda x:min(x,key=x.count)

Try it online!


05AB1E, score 0.5 / 1000!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

bug fix thanks to FryAmTheEggman

+1 ! thanks to ExpiredData

 [₄!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!LΩ#¼]¾D±)Ω

(dont't) Try it online! (will timeout).

Try it online without the factorials

[           ]            # loop:
 ₄                       #  1000
  !!...!                 #  take the factorial, 88 times
        LΩ               #  pick a random number from 1 to that many
          #              #  if the number was 1, exit the loop
           ¼             #  increment counter_variable
             ¾           # after the loop: push counter_variable
              D±         # push its bitwise negation
                )        # wrap the two in a list
                 Ω       # pick a random element of that list

Any integer would work instead of 1000!!...!, so this approach could score as low as 0.5 / BB(89), where BB is 05AB1E's Busy Beaver function.


Haskell, 43 bytes

f n=map=<<flip(map.max)$show.(10^)=<<[1..n]

Try it online!

A clever approach by Ørjan Johansen outputting with 0's and 1's, generating each 10...00 part as the string representation of a power of 10.

111111111
101001000
111111111
101001000
101001000
111111111
101001000
101001000
101001000

Haskell, 49 bytes

f n=map=<<flip(map.max)$[0^i|x<-[1..n],i<-[0..x]]

Try it online!

Generates a pattern like [1,0,1,0,0,1,0,0,0,...], then makes a 2D by taking the min of pairs. The pointfree weirdness saves 2 bytes over the more readable:

f n|l<-do x<-[1..n];0:(1<$[1..x])=[[a*b|a<-l]|b<-l]

Try it online!


Clean -  Complexity Unknown
Currently works, explanation and further optimization in progress
module main
import StdEnv, StdLib, System.IO

:: Position :== [Int]
:: Positions :== [Position]
:: Digit :== (Char, Int)
:: Digits :== [Digit]
:: Number :== ([Char], Positions)
:: Numbers :== [Number]
:: Complete :== (Numbers, Positions)

decouple =: snd o unzip

//lcouple :: (.a -> .b) (.a, .c) -> (.b, .c)
lcouple fn (arg, oth) :== (fn arg, oth)

getCases :: Int *World -> ([(String, [[Char]])], *World)
getCases n world
    # (range, world)
        = evalIO getLine world
    # range
        = fromString range
    # spacePos
        = elemIndex ' ' range
    | isNothing spacePos
        = abort "invalid input, expected space in range\n"
    # (a, b)
        = splitAt (fromJust spacePos) range
    # (a, b)
        = (toInt (toString a), toInt (toString (tl b)))
    # numbers
        = [(fromString o toString) number \\ number <- [a..(b-1)]]
    # (string, world)
        = evalIO getLine world
    | n > 1
        # (cases, world)
            = getCases (n - 1) world
        = ([(string, numbers) : cases], world)
    = ([(string, numbers)], world)

singletonSieve :: Complete -> Complete
singletonSieve (list, sequence)
    | sequence_ == sequence
        = reverseSieve (list, sequence)
    = (list_, sequence_)
where
    singles :: Positions
    singles
        = [hd pos \\ (_, pos) <- list | length pos == 1]
    list_ :: Numbers
    list_
        = map (app2 (id, filter notInOtherSingle)) list
    where
        notInOtherSingle :: Position -> Bool
        notInOtherSingle pos
            = not (isAnyMember pos (flatten (filter ((<>) pos) singles)))
    sequence_ :: Positions
    sequence_
        = foldr splitSequence sequence singles

reverseSieve :: Complete -> Complete
reverseSieve (list, sequence)
    | sequence_ == sequence
        = (list, sequence)
    = (list_, sequence_)
where
    singles :: Positions
    singles
        = [hd pos \\ pos <- [[subSeq \\ subSeq <- sequence | isMember subSeq p] \\ (_, p) <- list] | length pos == 1]
        //= [hd pos \\ pos <- | length pos == 1]
    list_ :: Numbers
    list_
        = map (app2 (id, filter (\b_ = (notInOtherSingle b_) && (hasContiguousRun b_)))) list
    where
        notInOtherSingle :: Position -> Bool
        notInOtherSingle pos
            = not (isAnyMember pos (flatten (filter ((<>) pos) singles)))
        hasContiguousRun :: Position -> Bool
        hasContiguousRun pos
            //= any (any (isPrefixOf pos) o tails) sequence_
            = and [isMember p (flatten sequence_) \\ p <- pos]

    sequence_ :: Positions
    sequence_
        = foldr splitSequence sequence singles

splitSequence :: Position Positions -> Positions
splitSequence split sequence
    = flatten (map newSplit (map (span (not o ((flip isMember) split))) sequence))
where
    newSplit :: (Position, Position) -> Positions
    newSplit ([], b)
        # b
            = drop (length split) b
        | b > []
            = [b]
        = []
    newSplit (a, b)
        # b
            = drop (length split) b
        | b > []
            = [a, b]
        = [a]

indexSubSeq :: [Char] Digits -> Positions
indexSubSeq _ []
    = []
indexSubSeq a b
    # remainder
        = indexSubSeq a (tl b)
    | isPrefixOf a (map fst b)
        = [[i \\ (_, i) <- take (length a) b] : remainder]
        //= [[i \\ _ <- a & (_, i) <- b] : remainder]
    = remainder

missingNumber :: String [[Char]] -> [[Char]]
missingNumber string numbers
    # string
        = [(c, i) \\ c <-: string & i <- [0..]]
    # locations
        = [(number, indexSubSeq number string) \\ number <- numbers]
    # digits
        = [length (indexSubSeq [digit] [(c, i) \\ c <- (flatten numbers) & i <- [0..]]) \\ digit <-: "0123456789-"]
    # missing
        = flatten [repeatn (n - length i) c \\ n <- digits & (c, i) <- [(digit, indexSubSeq [digit] string) \\ digit <-: "0123456789-"]]
    # (answers, _)
        = until (\e = e == singletonSieve e || length [(a, b) \\ (a, b) <- fst e | length b == 0 && isMember a (candidates missing)] > 0) singletonSieve (locations, [indexList string])
    # answers
        = filter (\(_, i) = length i == 0) answers
    = filter ((flip isMember)(candidates missing)) ((fst o unzip) answers)
where
    candidates :: [Char] -> [[Char]]
    candidates chars
        = moreCandidates chars []
    where
        moreCandidates :: [Char] [[Char]] -> [[Char]]
        moreCandidates [] nums
            = removeDup (filter (\num = isMember num numbers) nums)
        moreCandidates chars []
            = flatten [moreCandidates (removeAt i chars) [[c]] \\ c <- chars & i <- [0..]]
        moreCandidates chars nums
            = flatten [flatten [moreCandidates (removeAt i chars) [ [c : num] \\ num <- nums ]] \\  c <- chars & i <- [0..]]

Start world
    # (number, world)
        = evalIO getLine world
    # (cases, world)
        = getCases (toInt number) world
    =  flatlines[flatten(intersperse [', '] (missingNumber string numbers)) \\ (string, numbers) <- cases]

Try it online!


Haskell, 67 bytes

a#b|h<-a/2,c<-sqrt$(1+h)^2-b,c>0=h+c:[h-c|h>c]|l<-(a/2)#sqrt b=l++l

Try it online!
Based on this solution of Delfad0r, who also saved 1 byte off this
We first try to find a two-element solution with \$r_1+r_2=a\$ and \$(r_1+1)(r_2+1)=b\$, which we do by solving a quadratic equation. If we get real solutions, we're done. (If one solution is zero, we remove it and output a singleton.)
If this quadratic isn't solvable in the reals, we replace \$a \to a/2\$ and \$b \to \sqrt{b}\$ and solve from there. If we find a solution to this, then duplicating the list (that is, repeating each element a second time) gives a solution to the original problem, since this doubles the sum and squares the product of numbers-plus-one. We recursively make these substitutions until we simplify \$(a,b)\$ to ones that give a two-element solution.
We show that this process always reaches a solution. For the problem to be solvable, we must have \$b < e^a\$, which follows directly from \$\sum r_i=a\$ and \$\prod\left(r_i+1\right)=b\$ along with \$e^{r_i}>r_i+1\$. Since \$e^a\$ is the increasing limit of \$(1+a/N)^N\$ as \$N \to \infty\$, the bound \$b < e^a\$ implies that \$b < (1+a/N)^N\$, or equivalently that \$b^{1/N} < 1+a/N\$, for sufficiently large \$N\$. By choosing \$N=2^n\$ as a large power of \$2\$, doing \$n-1\$ steps of the substitution \$a \to a/2\$ and \$b \to \sqrt{b}\$ gives us \$a' = 2a/N\$ and \$b' = b^{2/N}\$, which we've shown satisfy \$\sqrt{b'} < 1 + a'/2\$.
This is exactly what we need to have real solutions for \$r_1+r_2=a\$ and \$(r_1+1)(r_2+1)=b\$, which gives a quadratic with discriminant \$(1+a/2)^2-b\$. It solutions are $$r  = a/2 \pm \sqrt{(1+a/2)^2-b}$$


Bash, 52 47 (49-2) bytes
EDITS:

Saved 5 bytes, by starting with 1 instead of 0. Thanks @Leo !

Golfed
A=$[1+0]
echo $A
sed -ri "s/\w+\+(\w+)/\1+$A/" $0

Test
>for i in `seq 10`
> do
> ./fibo
> done
1
1
2
3
5
8
13
21
34
55


zsh, 19

rm -f /**/.DS_Store

(Make that 16 if it's ok to leave out -f.)


R, 95 bytes

function(m,a=c(1,3),r=range){plot(0,,"n",r(m[a,]),r(m[-a,]));segments(m[1,],m[2,],m[3,],m[4,])}

Try it online!

Here's a graphical solution as an appetizer while I'm working on a full-blown solution.
TIO link will not plot anything.


*, 0 bytes

Since * has no way of reading input, the default rules allow specifying that the input must be given by concatenating it onto the program.

(... I think. There's an "at least twice as many upvotes as downvotes" condition that I don't have the rep to verify).


Python 2, 84 81 80 79 bytes

-1 byte thanks to ovs

lambda x:g(x,1)|g(x,0)
g=lambda x,a:len(set(x[a::2]))==(x[a<1::2]in"123456789")

Try it online!

Python 3, 82 79 78 77 bytes

lambda x:g(x,1)|g(x,0)
g=lambda x,a:len({*x[a::2]})==(x[a<1::2]in"123456789")

Try it online!

Slightly shorter in Python 3, but I didn't think it deserved its own answer.

Explanation

We set up a function g that takes string and an index (either 1 or 0).  g then returns whether or not len(set(x[a::2])), that is the number of unique digits in every other position, is equal to (x[a==0::2]in"123456789"), whether or not the other digits are in ascending order.  If the digits are in ascending order this returns whether or not they are all the same, if not it will ask if the set is empty, which it cannot be, thus always returning false.


Bash, 46 bytes

ImageMagick scales image to one pixel which contains average of the colors in the image then outputs it as text.

convert $1 -scale 1x1\! txt:-|egrep -o '#\w+'


05AB1E, 47 bytes

4"D34çýSDεXD<X>ŸΩU}W-úζ»"D34çýSDεXD<X>ŸΩU}W-úζ»

Try it online!


Python 2, 126 121 120 114 100 bytes

lambda s:findall(' (.=)',s)[0]+sub('if.(.*?)\)(.=)?',r'\1?',sub('.{5} (.=)?',':',s))
from re import*

Try it online!

Saved:

-1 byte, thanks to Kevin Cruijssen


Find the Needle in the Haystack (Robbers)

JavaScript, 85 bytes (ES6)

Cracks Arnauld's answer

f=(k=b=x=35)=>x--?f(k*4853461&268435455):k&2?'N'+(k^12408877).toString(b):'Haystack'

"Needle" demo

f=(k=b=x=35)=>x--?f(k*4853461&268435455):k&2?'N'+(k^12408877).toString(b):'Haystack'

console.log(f())

Explanation

The original function was:

f=(k=b=x=35)=>x--?f(k*74837258394056219&268435455):k&2?'N'+(k^124038877).toString(b):'Haystack'

which is more readable as:

f = (k=b=x=35) => {
    if (x--) {
        return f(k*74837258394056219&268435455);
    } else {
        if (k&2) {
            return 'N'+(k^124038877).toString(b);
        } else {
            return 'Haystack';
        }
    }
}

Note that when n=21625674, then n.toString(35) is 'eedle'.

The 35 in the input probably cannot be changed to a subset (because we want a base large enough to contain all the letters 'del', so we need a base that's at least 22). So the numbers to change are 74837258394056219, 268435455, and 124038877. We want to replace them with numbers a, b, c, each formed with a subset of the digits of the original numbers, such that the function g(k) = (k * a & b), starting with k=35 and iterated 35 times, and then XORed with c, gives 21625674.

For this one, after thinking a bit, as the lengths are small (the maximal a has length 17, b and c have length 9), I just used brute-force :-) Wrote a C++ program to generate all possible numbers a, b, c formed as subsets of the original numbers, iterate through all a and b, and check whether the required c was in the set. Runs in about 15 seconds, and the only output is a=4853461, b=268435455, c=12408877 (turns out the number b doesn't need to be changed). I'm not sure whether there's a more clever way of inverting this function.


JavaScript (ES7), Neil

_26_=>_26_**6.25**.5

The hard part, of course, was figuring out what to do with all the extra characters.  (And also not posting this solution in the wrong thread, like I accidentally did at first.  Oopsie...)


C, 171 146
i,b;main(int c,char**v){for(;c=v[1][i];)b|=c/65<<c*2%7+v[1][++i]%2*7;for(i=12;i--;)b&(1016056>>i)||printf("Dorian scale in %c%c",65+i*3%7,(i<5)*35);}

Parsing strings in C is not that easy, so I went for a more mathematical approach.
I take advantage of the Circle of Fifths. If we arrange the notes in the following order based on counting up 7 semitones at a time (known as a "fifth"), we find that all the notes permitted in any given scale form a consecutive block of 7 notes and all the prohibited notes form a consecutive block of 5 notes.
F C G D A E B F# C# G# D# A#

(it's a circle, it wraps back around to F at the end.)
The position of a natural note in the above sequence can be calculated as (ASCII code) * 2 % 7. Then if the next character is odd (applies to # but not comma, space or zero byte) we add 7 to make it sharp. We store a bitmap of the notes that have been used.
The number 243 (binary 11111000) corresponds to the notes prohibited in the scale of A# Dorian. I multiplied this by (1<<12)+1=4097 to give the magic number 1016056. This is rightshifted to check (by ANDing) if the melody contains prohibited notes for each of the 12 scales in turn. If the melody does not contain prohibited notes, the scale is printed.
For the output we need to print the scale name encoded in the reverse order to cycle of fifths above, remember we are going backwards because we are rightshifting.) The ASCII sequence ADGCFBEADGCF is generated by 65+i*3%7. For the first five of these a sharp must also be printed.
Ungolfed code
i,b;
main(int c,char**v){
  for(;c=v[1][i];)                          //for each character in first commanline argument v[1]
                                               //if it is a letter (assume uppercase, ASCII 65 or over)
   b|=c/65<<c*2%7+v[1][++i]%2*7;               //convert to position in the circle of fifths.
                                               //Add 7 if the next character is odd (ASCII'#')
                                               //leftshift 1 by this number and OR this with the contents of b.

  for(i=12;i--;)b&(1016056>>i)||printf         //if melody includes no prohibited notes for the scale i, print
   ("Dorian scale in %c%c",65+i*3%7,(i<5)*35); //the scale letter, and a # (ASCII 35) if required, otherwise an ASCII 0.
}

Invalid input behaviour: If insufficient notes are supplied to unambiguously determine the scale, it will output all possible scales. If an impossible combination of notes is supplied, it will output nothing. Notes must be delimited by a comma (or other non-whitespace character with an even ASCII code <= 64.) Spaces cannot be used as everything after the first space would be considered a different argument. ASCII codes >64 will be interpreted as notes in the manner described.


Output a program that outputs a program ... that outputs PPCG

12 languages, 64 bytes
Charcoal -> tinylisp -> Python 3 -> /// -> Python 2 -> Perl -> QBasic -> Pip -> V -> Retina -> Pyth -> GolfScript
Charcoal
Ｐ(q(print('/x/print/x"""x q<?"`i.*":?CHR$(34)+"\'PPCG\'`">"""'*1

Any run of printable ASCII is a string literal in Charcoal. Ｐ can be used for multidirectional printing, but in this case it simply prints the string going rightward.
tinylisp
(q(print('/x/print/x"""x q<?"`i.*":?CHR$(34)+"\'PPCG\'`">"""'*1

The only reserved characters in tinylisp (as of this writing) are parentheses and whitespace. Any other run of characters is a token, even something like +"\'PPCG\'`">"""'*1. Parentheses define lists. The q (quote) builtin returns its argument unevaluated--in this case, the nested list (print ('/x/print/x"""x q<?"`i.*":?CHR$ (34) +"\'PPCG\'`">"""'*1)). (Missing parentheses at the end are autocompleted.)
Python 3
(print ('/x/print/x"""x q<?"`i.*":?CHR$ (34) +"\'PPCG\'`">"""'*1))

Since print is a function in Python 3, we can wrap it in parentheses with no problem. In Python 2, where it's a statement, this is a syntax error. Unfortunately, Perl is fine with the parentheses, so we also do *1 (string repetition in Python, cast to int and multiply in Perl).
///
/x/print/x"""x q<?"`i.*":?CHR$ (34) +"'PPCG'`">"""

/x/print/ changes x to print in the rest of the program, which has no slashes and therefore is output with no further changes.
Python 2
print"""print q<?"`i.*":?CHR$ (34) +"'PPCG'`">"""

No parentheses after print, doesn't work in Python 3. Perl doesn't like the triple quotes.
Perl
print q<?"`i.*":?CHR$ (34) +"'PPCG'`">

Perl's various ways of quoting a string are helpful, and distinct from other languages. Here we use q<...>.
QBasic
?"`i.*":?CHR$ (34) +"'PPCG'`"

A couple of print statements (abbreviated as ?), using CHR$(34) to get a double quote.
Pip
`i.*
"'PPCG'`

A single Pattern (regex) literal in backticks.
V
i.*
"'PPCG'

Switch to insert mode, add some text.
Retina
.*
"'PPCG'

Match anything and replace it with the second line.
Pyth
"'PPCG'

Pyth quotes don't need to be matched (which makes this not a valid program in Pip).
GolfScript
'PPCG'


Create icy avatar images for the winter season

Python 2 - 326 339 358
Takes input from the user. File first, then n.
from PIL.Image import*;from random import*
a,N=input()
i=open(a)
d=list(i.getdata())
x,y=i.size
R=range(x*y)
m=lambda p,n,r:[p[i]for i in R if abs(n%x-i%x)+abs(n/y-i/y)<=r]
k=d[:]
for p in R:t=map(lambda x:sum(x)/len(x),zip(*m(k,p,N)));d[p]=t[0],t[1],min(255,t[2]*3/2)
i.putdata([choice(m(d,p,N/2))for p in R])
i.save('t.png')

This could probably be golfed much more :P Thanks to @SP3000 for golf ideas!
Sample input:
(Windows)
"C:/Silly/Optimizer/Trix/Are/For/Kids.png",7

Edit: Bug fixed where blue was being propagated (Martin with n=20 is no longer a river ;_; )
Martin with n=2:

Martin with n=10:

Martin with n=20:


CJam - 66

ria{_{:XmF{1=1>},La\{a1$\f++}/La-{XI{~#}%:*/I{si}%:**}fI}%|}1e3*$p

Try it at http://cjam.aditsu.net/

Explanation:

ria                       read token, convert to integer and wrap in array
{…}1e3*                   repeat 1000 times
    _                     duplicate array
    {…}%                  transform each array item (number) using the block
        :X                store the number in X
        mF                factorize with exponents
        {1=1>},           keep only the factors with exponent > 1
        La\{a1$\f++}/     get all the subsets (*)
        La-               remove the empty subset
        {…}fI             for I = each subset of prime factors with exponent > 1
            XI{~#}%:*/    divide X by all the factors in I
            I{si}%:**     multiply with the primes from I
                          concatenated with their exponents
    |                     add the new numbers to the array, removing duplicates
$                         sort
p                         print the final array

(*) Thanks Martin