Finding Exclusive Area in Circle Intersections

Python 2, 631 bytes

from cmath import*
C=input()
O,R=C[0]
def I(p,r,q,s):
 try:q-=p;d=abs(q*q);x=(r*r-s*s+d)/d/2;return[p+q*(x+z*(r*r/d-x*x)**.5)for z in-1j,1j]
 except:return[]
S=sorted
V=S(i.real for p,r in C for c in C for i in[p-r,p+r]+I(p,r,*c)if-R<=(i-O).real<=R)
A=pi*R*R
for l,r in zip(V,V[1:]):
 H=[]
 for p,t in C:
    try:
     for s in-1,1:a,b=[p.imag+s*(t*t-(p.real-x)**2)**.5for x in l,r];H+=[a+b,a,b,s,t,p],
    except:0
 a,b=H[:2];H=S(H[2:]);n=0;c=a
 for d in H:
    s=d[3];z=.5;H*=d<b
    for q,w,e,_,t,y in(c,min(d,b))*(n-s<(a<d)or[0]*n>H):\
g=phase((l+w*1j-y)/(r+e*1j-y));A-=abs(g-sin(g)).real*t*t/2-z*q*(r-l);z=-z
    n-=s
    if(a<d)*s*n==-1:c=d
print A

Line-breaks preceded by \ are for easy reading, and aren't counted in the score.

Reads input through STDIN as a list of (center, radius) pairs, where center is a complex number in the form X+Yj.
The first circle in the list is A (whose center doesn't have to be at the origin), and the rest of the list is B.
Prints the result to STDOUT.

Example

Input:  (0+0j, 138),  (100+0j, 100), (-50+-86j, 100), (-93+135j, 50)
Output: 18969.6900901

Explanation

This is a (longer, and much uglier :P) variation on my solution to Martin Büttner's Area of a Self-Intersecting Polygon challenge.
It uses the same trick of breaking the problem down into small-enough pieces, for which it becomes more manageable.

We find the points of intersection between all pairs of circles (considering both A, and the circles in B), and pass a vertical line through each of them.
Additionally, we pass all the vertical lines tangent to any of the circles.
We throw away all the lines that don't intersect A, so that all the remaining lines are between the left and right tangents of A.

We're looking for the area of the intersection of A and the union of the circles in B—the dark red area in the illustration above.
This is the area that we have to subtract from A to get the result.

Between each pair of consecutive vertical lines, this area can be broken down into a set of vertical trapezoids (or triangles, or line segments, as special cases of trapezoids), with an "excess" arc segment next to each leg.
The fact that we pass as many vertical lines as we do guarantees that the bounded area is indeed no more complicated than that, since otherwise there would have to be an additional point of intersection, and hence an additional vertical line, between the two lines in question.

To find these trapezoids and arc segments, for each pair of consecutive vertical lines, we find the arc segments of each of the circles that properly lie between these two lines (of course, some circles may have no arc segment between a given pair of lines.)
In the illustration below, these are the six (bright and dark) yellow arc segments, when considering the two red vertical lines.
Note that, since we pass all vertical lines tangent to the circles, if a circle has an arc segment between the two lines, it necessarily intersects both lines, which simplifies the rest of the algorithm.

Not all of these arcs are relevant; we're only interested in the ones that are on the boundary of the intersection between A and the union of B.
To find those, we sort the arcs top-to-bottom (note that the arcs may not properly intersect each other, since this would imply the existence of another vertical line between the two we're considering, and so it makes sense to talk about an arbitrary arc being above, or below, any other one.)

We traverse the arcs, in order, while keeping count of the number of B circles we're currently inside, n.
If n changes from 0 to 1 while we're inside A, or if we're at the top arc of A while n is nonzero, then the current arc corresponds to one leg of a trapezoid.
If n changes from 1 to 0 while we're inside A, or if we're at the bottom arc of A while n is nonzero, then the current arc corresponds to the other leg of the same trapezoid.
Once we find such a pair of arcs (the two bright yellow arcs in the above illustration), we calculate the area of the corresponding trapezoid, and of the two arc segments, and add it to the total area to be subtracted from A.

Calculating the area of A, as well as the areas of the trapezoids, is fairly straight forward.
The area of each arc segment is the area of the corresponding circular sector, minus the area of the triangle whose vertices are the two endpoints of the arc segment, and the center of the corresponding circle.


Make two programs communicate with each other

C and PERL communicating via keyboard status lights
My friend and I got inspired by this one last night.
We use Perl for the sender program and C for the receiver.
The medium of exchange was the keybord status lights!
Three virtual signal lines were used: Caps Lock, Num Lock and Scroll lock, being used as Clock, Serial Data, and Start Of Byte signals.

The sender program pulses those keyboard lights and the receiver polls them and checks the state.  Data is sent serially as binary, in 8 bit bytes.
You can see the transmitter and receiver programs in operation, in the attached video, as well as the flashing of the lights during the transmission.
Video of operation
Source for both programs is attached. Given the question requirements, we didn't try to minimize the size like we would in a normal golfing attempt.
C Code (receiver)
#include <X11/Xlib.h>
#include <stdio.h>
#include <unistd.h>

int main(void)
{
    Display* dpy = XOpenDisplay(":0");
    XKeyboardState x;
    char keys_return[32];
    int b = 0;
    while (1) {
        unsigned char output = 0;
        printf(" \b");
        fflush(stdout);
        while (XQueryKeymap(dpy, keys_return)) //wait for start signal
            if (keys_return[9] == 64) {
                break;
            }
        for (b = 0; b < 8; b++) {
            do {
                XGetKeyboardControl(dpy, &x);
            } while (!(x.led_mask & 1)); //wait for clock to be high
            if (x.led_mask & 2)
                output |= 128;
            if (b != 7)
                output >>= 1;
            do {
                XGetKeyboardControl(dpy, &x);
            } while ((x.led_mask & 1)); //wait for clock to be low
        }
        printf("%c", output);
    }
    XCloseDisplay(dpy);
    return 0;
}

PERL code (transmitter)
use X11::Xlib ':all';
use strict;
use warnings;
use feature 'say';
use Time::HiRes qw(sleep);

use constant {
    DATA  => 77,
    START => 78,
    CLOCK => 66
};

my $display = X11::Xlib->new;

sub transmit_str {
    my ($str) = @_;
    foreach my $char ( split( //, $str ) ) {
        my $ordchar = ord($char);
        for my $i ( 0 .. 7 ) {
            for my $j ( 0 .. 1 ) {
                if ( $i == 0 ) {
                    $display->fake_key( START, !($j) );
                }
                if ( $ordchar & 1 ) {
                    $display->fake_key( DATA, 1 );
                    $display->fake_key( DATA, 0 );
                }
                $display->flush;
                sleep(0.025) if(!$j);
                $display->fake_key( CLOCK, 1 );
                $display->fake_key( CLOCK, 0 );
                $display->flush;
                sleep(0.05);
            }
            $ordchar >>= 1;
        }
    }
}
while ( my $stdin = <STDIN> ) {
    transmit_str($stdin);
}


Perl, 41 bytes

#!perl -p0
1while s/( *).*\K:((
\1 .*)+)/ {\2
\1}/

Counting the shebang as two, input is taken from stdin. A command line argument need not be provided. Any valid nesting context can be determined (and matched) without knowing the indentation size.

Regex Break-Down

( *)                   # as many spaces as possible (\1)
    .*                 # as many non-newline characters as possible \
                         (greediness ensures this will always match a full line)
      \K               # keep all that (i.e. look-behind assertion)
        :              # colon at eol (newline must be matched next)
         (
          (
           \n\1        # newline with at least one more space than the first match
                .*     # non-newlines until eol
                  )+   # as many of these lines as possible
                    )  # grouping (\2)

Sample Usage

in1.dat

public class Test:
    public static void main(String[] args):
        System.out.println("Java is verbose...");

Output

$ perl py2java.pl < in1.dat
public class Test {
    public static void main(String[] args) {
        System.out.println("Java is verbose...");
    }
}

in2.dat

main():
  printf("Hello World");

Output

$ perl py2java.pl < in2.dat
main() {
  printf("Hello World");
}

in3.dat

def generic_op(the_stack, func):
    # Generic op handling code
    b = the_stack.pop()
    if isinstance(b, list):
        if b:
            return
        top = b.pop(0)
        while b:
            top = func(top, b.pop(0))
        the_stack.push(top)
    else:
        a = the_stack.pop()
        return func(a, b)

Output

$ perl py2java.pl < in3.dat
def generic_op(the_stack, func) {
    # Generic op handling code
    b = the_stack.pop()
    if isinstance(b, list) {
        if b {
            return
        }
        top = b.pop(0)
        while b {
            top = func(top, b.pop(0))
        }
        the_stack.push(top)
    }
    else {
        a = the_stack.pop()
        return func(a, b)
    }
}


SWI-Prolog, 536 4411 bytes

1 UNIX line ending, final new line not counted

The version with all optimizations removed (441 bytes):

:-[library(clpfd)].
m(G,L):-maplist(G,L).
l(L,A):-length(A,L).
y(A,E,(X,Y)):-nth1(X,A,R),nth1(Y,R,F),var(F),F=E.
a(A,S):-l(L,A),X#>0,X#=<L,Y#>0,Y#=<L,h(S,(X,Y),A).
h(0,_,_).
h(L,(X,Y),A):-(B=A;transpose(A,T),B=T),y(B,s,(X,Y)),M#=L-1,Z#=Y+1,h(M,(X,Z),B).
e([],_,[]).
e([H|R],I,O):-J#=I+1,e(R,J,P),l(H,Q),Q ins I,append(P,Q,O).
r(R):-m(c,R),nl.
c(E):-var(E)->put(@);put(E).
g(L,H,S):-l(L,A),m(l(L),A),m(y(A,\),S),e(H,1,G),!,m(a(A),G),!,m(r,A).

Since the code is changed to minimize the number of bytes, it will no longer accept a list of shots that have duplicates.

The version with basic optimization, fully golfed (536 → 506 bytes)

:-[library(clpfd)].
m(G,L):-maplist(G,L).
l(L,A):-length(A,L).
x(A,I,E):-X=..[a|A],arg(I,X,E).
y(A,E,(X,Y)):-x(A,X,R),x(R,Y,E).
a(A,S):-l(L,A),X#>0,X#=<L,Y#>0,Y#=<L,(B=A;transpose(A,T),B=T),h(S,(X,Y),B).
h(0,_,_).
h(L,(X,Y),A):-y(A,E,(X,Y)),var(E),E=s,M#=L-1,Z#=Y+1,h(M,(X,Z),A).
e([],_,[]).
e([H|R],I,O):-J#=I+1,e(R,J,P),l(H,Q),Q ins I,append(P,Q,O).
r(R):-m(c,R),nl.
c(E):-var(E)->put(@);put(E).
g(L,H,S):-l(L,A),m(l(L),A),sort(S,T),m(y(A,\),T),e(H,1,G),!,l(E,T),sumlist(G,D),L*L-E>=D,m(a(A),G),!,m(r,A).

I implement some basic checks (count number of ship blocks necessary) to make the code exits faster for clearly impossible cases. The code is also immune to duplicate in the list of shots so far.

Below is the (somewhat) readable version, with detailed comments:

:-[library(clpfd)].

% Shorthand for maplist, which works like map in high order function
m(G,L):-maplist(G,L).

% Creating a square matrix A which is L x L
board(L,A):-l(L,A),m(l(L),A).

% Shorthand for length, with order of parameters reversed
l(L,A):-length(A,L).

% Unification A[I] = E
x(A,I,E):-X=..[a|A],arg(I,X,E).

% Unification A[X][Y]=E
idx2(A,E,(X,Y)):-x(A,X,R),x(R,Y,E).

% Mark positions that have been shot
markshot(A,S):-m(idx2(A,\),S).

% Place all ships on the board
placeships(H,A):-m(placeship(A),H).

% Place a length S ship horizontal/vertical forward on the board
placeship(A,S):-
    l(L,A), % Get length
    X#>0,X#=<L,Y#>0,Y#=<L, % Constraint X and Y coordinates
    transpose(A,T), % Transpose to work on columns
    (placeship_h(S,(X,Y),A) ; placeship_h(S,(Y,X),T)).

% Place ship horizontal, forward at (X,Y)
placeship_h(0,_,_).
placeship_h(L,(X,Y),A):-
    idx2(A,E,(X,Y)),var(E),E=s, % Make sure position is unassigned, then mark
    L2#=L-1,Y2#=Y+1, % Do this for all blocks of the ship
    placeship_h(L2,(X,Y2),A).

% Expand the list of ships
% e.g. [2,3,1] --> [3,2,2,2,1,1]
shipexpand(S,O):-shipexpand(S,1,O).

shipexpand([],_,[]).
shipexpand([H|R],I,O):-
    I2#=I+1,shipexpand(R,I2,O2), % process the rest
    l(H,O1),O1 ins I, % duplicate current ship size H times
    append(O2,O1,O). % larger ship size goes in front

% Print the result
pboard(A):-m(prow,A).
prow(R):-m(pcell,R),print('\n').
pcell(E):-var(E)->print(@);print(E).

game(L,H,S):-
    board(L,A), % create board
    sort(S,SS), % remove duplicates
    markshot(A,SS), % mark positions that have been shot
    shipexpand(H,HH),!, % make a list of ships
    l(SC,SS),sumlist(HH,BC),L*L-SC>=BC, % check to speed-up, can be removed
    placeships(HH,A),!, % place ships
    pboard(A). % print result

Query format:

game(Board_Size, Ships_List, Shots_List).

Sample query (using the sample in the question):

?- game(4,[1,1,1],[(2,1),(3,2),(3,3),(4,1),(4,3),(4,4)]).
ssss
\ss@
@\\@
\@\\
true.

?- game(4,[2,2,0,1],[(2,1),(3,2),(3,3),(4,1),(4,3),(4,4)]).
ssss
\sss
s\\s
\s\\
true.


Find the largest and the smallest number in an array

JavaScript (ES6), 54 56
Edit 2 bytes saved thx @Neil
Note: x===+x is true if and only if x is a number
a=>[Math.max(...a=a.filter(x=>x===+x)),Math.min(...a)]


Python 2, 67 63 65 bytes

x=""
while 1:x="x=%r\nwhile 1:x='print%%r;'%%x;exec x;"%x;print x

Try it online!
Use the same strategy as @UnrelatedString's answer, be sure to check out and upvote his answer!
Repeatedly print out programs with ordinal \$0, \omega, \omega2, \omega3,\ldots \$. The programs are separated by the string ";\n" (a semi-colon and a new line).
68 bytes to separate programs by a blank line.
Explanation
A program with ordinal \$n+1\$ is created by adding a print statement around an \$n\$-ordinal program:
print <escaped string of ordinal-n program>

A program with ordinal \$\omega(n+1)\$ is created by repeatedly printing out programs with ordinal \$\omega n, \omega n+1,\omega n+2,\ldots\$
x = <string of omega*n program>
while 1:
  x = 'print %r' % x
  exec x

Note the use of %r, which escapes the given string x. This way, we don't have to worry about quote and new line characters.
Finally, a program with ordinal \$\omega^2\$ is created by repeatedly printing out programs with ordinal \$0, \omega, \omega 2,\omega 3,\ldots\$:
# string of program to go from omega*n to omega*(n+1)
s = "x=%r\nwhile 1:x='print%%r'%%x;exec x"
# current omega*n program, start with n=0
x = ""
while 1:
  # create the omega*(n+1) program from omega*n
  x = s % x
  # print it out
  print x


R, 23 bytes

function(o,v)mean(o!=v)

Try it online!

The challenge boils down to computing the proportion of values in v different from o (i.e. mean(xor(o,v))). We can therefore avoid using abs.


Python2 - 21 (or 15) (or 1)

Sets should be in the format set([element1, element2, element3...])

print input()|input()

If running from the interactive prompt is allowed, remove the print.

Note: If the Mathematica answer qualifies as being 1 character, then in the Python interactive prompt this should also qualify as 1 character:

set(['a','b','d','z'])|set(['c','z','d','a','k','a'])

Sample input:

set(['a','b','d','z'])
set(['c','z','d','a','k','a'])

Sample output:

set(['a', 'c', 'b', 'd', 'k', 'z'])


Undocumented, but works in every version I've run into for legacy sh backwards compatibility:

for loops allow you to use { } instead of do done.  E.g. replace:

for i in {1..10};do echo $i; done

with:

for i in {1..10};{ echo $i;}


R, 202 192 184 182 162 154 bytes + 0 errors

function(x)c("U","T","B","E","G")[which.max(lapply(list(dunif(x),sapply(x,function(y)max(0,2-4*abs(.5-y))),dbeta(x,.5,.5),dexp(x,2),dgamma(x,3,6)),prod))]

This is based on the Bayesian formula P(D=d|X=x) = P(X=x|D=d)*P(D=d)/P(X=x), where D is the distribution and X is the random sample. We pick the d such that P(D=d|X=x) is greatest of the 5.

I assume a flat prior (i.e. P(D=di) = 1/5 for i in [1,5]), which means that P(D=d) in the numerator is the same in all cases (and the denominator would be the same in all cases anyways), so we can golf away everything but the P(x=X|D=d), which (except for the triangular distribution) simplify to native functions in R.

ungolfed:

function(x){
  u=prod(dunif(x))
  r=prod(sapply(x,function(y)max(0,2-4*abs(.5-y))))
  b=prod(dbeta(x,.5,.5))
  e=prod(dexp(x,2))
  g=prod(dgamma(x,3,6))
  den=.2*u+.2*r+.2*b+.2*e+.2*g
  c("U","T","B","E","G")[which.max(c(u*.2/den,r*.2/den,b*.2/den,e*.2/den,g*.2/den))]
}

Note that the ungolfed version is not exactly equivalent to the golfed version because getting rid of the denominator avoids the case of Inf/Inf which occurs if you allow the beta distribution to be over the closed interval [0,1] instead of (0,1) - as the sample data does. An additional if statement would handle that but since it's for illustrative purposes only it's probably not worth adding the complexity that is not at the heart of the algorithm.

Thanks @Alex A. for additional code reductions. Especially for which.max!


Encrypt a string using vigenere techniques

Jelly, 9 bytes

2 bytes thanks to Dennis.

ṁ⁹,OS‘ịØA

Try it online!

How it works

ṁ⁹,OS‘ịØA            arguments: "KEYA", "STRING"

ṁ⁹         reshape   "KEYAKE"
  ,        pair      ["KEYAKE","STRING"]
   O       codepoint [[75,69,89,65,75,69],[83,84,82,73,78,71]]
    S      sum       [158,153,171,138,153,140]
     ‘     add 1     [159,154,172,139,154,141]
      ịØA  index ØA  "CXPIXK"
           where ØA is "ABCDEFGHIJKLMNOPSRQTUVWXYZ"


PARI/GP (10)

In gp (and some other languages) x%1 gives the decimal part of x:

f(x)=x-x%1

NOTE: For negative x, x%1 returns (1 - abs(decimal part of x)), so the above works both for positive and negative numbers.


Determine sets of associatively equivalent permutations of commutative operations

Every parenthesis has in it two elements, either a terminal symbol, or another parenthesis. These two elements have two possible permutations, ab and ba.

This means that the expression forms a binary tree, and every node inside the tree has two possible permutations. So the total output is always 2n where n is the number of parenthesis pairs. This means that an asymptotical algorithm will always do this amount of work.

For this optimal algorithm we will parse the expression, then recursively generate possibilities, 2 for each parenthesis pair. As seen in the paragraph above, this is optimal.

def parse(inp):
    c = inp.pop(0)
    while c == ")": c = inp.pop(0)

    if c == "(":
        return [parse(inp), parse(inp)]

    return c

def possibs(tree):
    if len(tree) == 2:
        for left_possib in possibs(tree[0]):
            for right_possib in possibs(tree[1]):
                yield left_possib + right_possib
                yield right_possib + left_possib
    else:
        yield tree

tree = parse(list("((ab)(cd))"))

for possib in possibs(tree):
    print(possib)


Ruby, 150 bytes

See revisions for previous byte counts.

->a,b,c,d,e,f,g,h,i,j{l=->s,t=c{Math.log(s,t)};y,z=l[l[g,b]]-d**e+l[h]*i**=j,l[l[a,f]*b**c,g];a>1?f<2?1:b<2||g<2?z>h:c<2||d<2?l[z,h]>i:y==0?a>f:y<0:p}

-10 bytes thanks to @ValueInk

+16 bytes thanks to @RosLuP for bugs.

Try it online.

Compare different base powers-towers (of 'height' five)?

Ungolfed code:

-> a, b, c, d, e, f, g, h, i, j {
    l =-> s, t = c {Math.log(s, t)}
    i **= j
    y = l[l[g, b]] - d ** e + l[h] * i
    z = l[l[a, f] * b ** c, g]
    if a == 1
        return p
    elsif f == 1
        return 1
    elsif b == 1 || g == 1
        return z > h
    elsif d == 1 || c == 1
        return l[z, h] > i
    elsif y == 0
        return a > f
    else
        return y < 0
    end
}

Code breakdown:

l =-> s, t = c {Math.log(s, t)}

This is the base t logarithm, which will be used to reduce the size of the numbers we are comparing. It defaults to base c when only one argument is given.

i **= j
y = l[l[g, b]] - d ** e + l[h] * i
z = l[l[a, f] * b ** c, g]

This updates i = i ** j since i never gets used on it's own, and y is the result of logging b^c^d^e == g^h^i(^j) twice and moving everything to one side. We then let z = l[a, f] * b ** c as the log base g of the log base f of a ** b ** c.

if a == 1
    return p
elsif f == 1
    return 1

1^b^c^d^e = 1 is never greater than f^g^h^i^j, and likewise, a^b^c^d^e is always greater than 1^g^h^i^j = 1 if a != 1. Note that return p returns nil, which is falsey, and return 1 returns 1, which is truthy.

elsif b == 1
    return z > h

If b == 1 or g == 1, then this reduces to comparing a ** b ** c to f ** g ** h, which is done with two logs to both sides.

elsif d == 1 || c == 1
    return l[z, h] > i

This compares a ** b ** c with f ** g ** h ** i by rearranging it as log[log[b ** c * log[a, f], g], h] compared to i. (Recall that i **= j in the beginning and z = log[b ** c * log[a, f], g].)

elsif y == 0
    return a > f
else
    return y < 0
end

This compares the 4 highest powers after logging both sides twice. If they are equal, it compares the base.


Jelly, 26 bytes

bȷ2ḅ60
³ÇạÇ,
9Rẋ€4R¤ḌFÇ€ṂṪ

Explanation:

bȷ2ḅ60             f(x) = x tobase 100 frombase 60
³ÇạÇ,              g(x) = (abs(f(arg) - f(x)), x)
9Rẋ€4R¤            main(arg) = [1..9] repeat each with [1..4],
       ḌF           then get digits and flatten,
         Ç€         then map g,
           Ṃ        then minimum,
            Ṫ       then last element.

Try it online!


Python 3, 33 25 18 15 bytes

Thanks @jurjen-bos for the __mod__ tip.

'%.32d'.__mod__

Try it online!


Wolfram Language (Mathematica), 20 bytes
Perimeter[#~Disk~#]&

Try it online!
-2 bytes from @Roman (see comments)


Outputs to STDERR
Outputting to STDERR is now at +33/-21 as an allowed default, which is positive but contested. This is a CW answer to collect answers that just invoke an error in a language where error messages includes the language name.
Haskell, 1 byte
1

Error:
Parse error: naked expression at top level
Perhaps you intended to use TemplateHaskell

Lua, 1 byte
1

Error:
lua: .code.tio:1: syntax error near <eof>

(file name is unimportant)
Batch, 1 byte
~

Error:
'~' is not recognized as an internal or external command,
operable program or batch file.

tinylisp, 5 bytes
(c()1

Error:
Error: cannot cons to Int in tinylisp

R, 1 byte
)

Error:
Error: unexpected ')' in ")"

Java bytecode, 0 bytes
Error:
Exception in thread "main" java.lang.ClassFormatError: Truncated class file

Groovy, 1 byte
a

Note that a can be replaced with any other character
Error:
groovy.lang.MissingPropertyException: No such property: a ...

MATLAB, 1 byte
\

Error:
Error: Unexpected MATLAB operator.

PHP, 3 bytes
<?=

Error:
PHP Parse error:  syntax error, unexpected end of file in /home/runner/.code.tio on line 1

CJam, 1 byte
/

Error:
/
^
RuntimeException: The stack is empty
Java exception:
java.lang.RuntimeException: The stack is empty
    at net.aditsu.cjam.CJam.pop(CJam.java:75)
    at net.aditsu.cjam.Op2.run(Op2.java:10)
    at net.aditsu.cjam.Block.run(Block.java:304)
    at net.aditsu.cjam.CJam.runCode(CJam.java:210)
    at net.aditsu.cjam.CJam.main(CJam.java:240)

Twig, 2 bytes
Twig is a template language written in PHP. It's possible that this is a polyglot.
{{
{%
{#

Error:
PHP Fatal error:  Uncaught exception 'Twig_Error_Syntax' with message [...] in [...][...]:n:
Stack trace:
#0 [...]

The message varies depending on which program you choose.
[S.I.L.O.S], 2 bytes
x+

[Try it online!]
[S.I.L.O.S]: https://github.com/rjhunjhunwala/S.I.L.O.S
[Try it online!]: https://tio.run/nexus/silos#@1@h/f8/AA "S.I.L.O.S – TIO Nexus"
Trivially invokes undocumented behavior. Silos is the name of the language.
Python, 6 bytes
pYTHON

As the character restriction is case insensitive, and the output doesn't have to be in the correct case, this is a valid answer. The error message it produces is something like this:
Traceback (most recent call last):
  File ".code.tio", line 1, in <module>
    pYTHON
NameError: name 'pYTHON' is not defined

Try it online! (outputs to 'debug' tab)
JavaScript, 10 bytes
jAVAsCRIPT

This produces the following error message or similar in all environments:
ReferenceError: jAVAsCRIPT is not defined

QBIC, 6 bytes
?b(12)

In 6 bytes, we can put QBIC encountered error: 9 on the screen, signifying an out-of-bounds error.
ForceLang, 2 bytes
()

Error produced:
Exception in thread "main" lang.exceptions.IllegalInvocationException: null is not a function.
    at lang.ForceLang.parse(ForceLang.java:99)
    at lang.ForceLang.main(ForceLang.java:129)

Pip, 5 bytes
1~`[`

(Note: this works in the current version as of this writing, 0.17.09.01. No guarantees the interpreter won't change to handle this error differently in the future.)
Tries to regex match with a syntactically invalid pattern. The error produced will look something like this:
Traceback (most recent call last):
  File "/opt/pip/pip.py", line 221, in <module>
    pip(interactive=False)
  File "/opt/pip/pip.py", line 206, in pip
    state.executeProgram(tree, args)
  File "/opt/pip/execution.py", line 56, in executeProgram
    returnVal = self.functionCall(mainFunction, cmdLineArgs)
  File "/opt/pip/execution.py", line 368, in functionCall
    returnVal = self.getRval(returnExpr)
  File "/opt/pip/execution.py", line 235, in getRval
    expr = self.evaluate(expr)
  File "/opt/pip/execution.py", line 213, in evaluate
    result = opFunction(*args)
  File "/opt/pip/execution.py", line 1134, in FIRSTMATCH
    matchObj = regex.asRegex().search(str(string))
  File "/opt/pip/ptypes.py", line 175, in asRegex
    self._compiled = re.compile(pyRegex)
  File "/usr/lib64/python3.6/re.py", line 233, in compile
    return _compile(pattern, flags)
  File "/usr/lib64/python3.6/re.py", line 301, in _compile
    p = sre_compile.compile(pattern, flags)
  File "/usr/lib64/python3.6/sre_compile.py", line 562, in compile
    p = sre_parse.parse(p, flags)
  File "/usr/lib64/python3.6/sre_parse.py", line 855, in parse
    p = _parse_sub(source, pattern, flags & SRE_FLAG_VERBOSE, 0)
  File "/usr/lib64/python3.6/sre_parse.py", line 416, in _parse_sub
    not nested and not items))
  File "/usr/lib64/python3.6/sre_parse.py", line 765, in _parse
    p = _parse_sub(source, state, sub_verbose, nested + 1)
  File "/usr/lib64/python3.6/sre_parse.py", line 416, in _parse_sub
    not nested and not items))
  File "/usr/lib64/python3.6/sre_parse.py", line 523, in _parse
    source.tell() - here)
sre_constants.error: unterminated character set at position 8

Stax, 2 bytes
0u

Error:
Stax runtime error: rational divide by zero

zh also works.
###ink, 1 byte
~

~ at the start of a line marks that the line is a statement to be executed, rather than text to be printed. As of whichever version of inklecate TIO is using, if there's nothing after the ~, the interpreter crashes with the following error:
System.NullReferenceException: Object reference not set to an instance of an object
  at Ink.InkParser.LogicLine () [0x000b1] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.StringParser.ParseObject (Ink.StringParser+ParseRule rule) [0x00012] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.StringParser.OneOf (Ink.StringParser+ParseRule[] array) [0x0000a] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.InkParser.StatementAtLevel (Ink.InkParser+StatementLevel level) [0x00009] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.InkParser+<>c__DisplayClass134_0.<StatementsAtLevel>b__0 () [0x00000] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.StringParser.ParseObject (Ink.StringParser+ParseRule rule) [0x00012] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.StringParser.Interleave[T] (Ink.StringParser+ParseRule ruleA, Ink.StringParser+ParseRule ruleB, Ink.StringParser+ParseRule untilTerminator, System.Boolean flatten) [0x00040] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.InkParser.StatementsAtLevel (Ink.InkParser+StatementLevel level) [0x0004f] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.InkParser.Parse () [0x00000] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.Compiler.Compile () [0x00033] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.CommandLineTool..ctor (System.String[] args) [0x001a3] in <d64e27e7788347b2a5377c9e19bbdcab>:0
  at Ink.CommandLineTool.Main (System.String[] args) [0x00000] in <d64e27e7788347b2a5377c9e19bbdcab>:0
[ERROR] FATAL UNHANDLED EXCEPTION: System.NullReferenceException: Object reference not set to an instance of an object
  at Ink.InkParser.LogicLine () [0x000b1] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.StringParser.ParseObject (Ink.StringParser+ParseRule rule) [0x00012] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.StringParser.OneOf (Ink.StringParser+ParseRule[] array) [0x0000a] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.InkParser.StatementAtLevel (Ink.InkParser+StatementLevel level) [0x00009] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.InkParser+<>c__DisplayClass134_0.<StatementsAtLevel>b__0 () [0x00000] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.StringParser.ParseObject (Ink.StringParser+ParseRule rule) [0x00012] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.StringParser.Interleave[T] (Ink.StringParser+ParseRule ruleA, Ink.StringParser+ParseRule ruleB, Ink.StringParser+ParseRule untilTerminator, System.Boolean flatten) [0x00040] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.InkParser.StatementsAtLevel (Ink.InkParser+StatementLevel level) [0x0004f] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.InkParser.Parse () [0x00000] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.Compiler.Compile () [0x00033] in <b1e5e74f4ee842fc961297862cf23e07>:0
  at Ink.CommandLineTool..ctor (System.String[] args) [0x001a3] in <d64e27e7788347b2a5377c9e19bbdcab>:0
  at Ink.CommandLineTool.Main (System.String[] args) [0x00000] in <d64e27e7788347b2a5377c9e19bbdcab>:0


28 25 24 keystrokes

:se ri<CR>^qqct <C-r>"<Esc>f l@qq@q

Recursive macro, I assume that Ctrl-r counts as one keystroke.

The hardest part was to make sure the macro stays on the same line and does not destroy the rest of the file.


Python 2.7, 325 chars

R=['S','SaSb']
I='aaabbb'

L=len(I)
def P(x,y,n):
 if n<3:return[[x,y]][:n>1or x==y]
 return[[x]+w for z in range(x,y+1)for w in P(z,y,n-1)]
S={(i,i+1,c):1for i,c in enumerate(I)}
T=0
while S!=T:
 T=dict(S)
 for r in R:
  for a,x,y,b in P(0,L,4):
   if any(all(t in S for t in zip(p,p[1:],r[1:]))for p in P(x,y,len(r))):S[x,y,r[0]]=1
print(0,L,'S')in S

The rules are listed in R and the input is in I.

The code uses dynamic programming, similar to the Earley algorithm.  S contains tuples (i,j,N) if the symbol N can generate the input from indexes i to j.  We iterate through all rules and indexes looking for new entries we can put in S.

P is a helper function that calculates all possible partitions of the range [x,y] into n-1 ranges (assigning one symbol in the rule to each).  For instance, P(0,7,4) contains, among many others, [0,3,6,7].

The run time is exponential in the longest rule, but shouldn't be too bad in the number of rules and length of the input.


Python 2, 32 28 25 bytes

lambda n:(~-n|1)**2/8+n%2

Try it online!

Returns the n-th number (0-indexed)


Partially Solve the halting problem for brainf***

Python, ungolfed spaghetti code

Oh dear.

def will_it_halt(instructions):
    tape_length = 1
    LOOP_BOUND = 1000
    registry = [0] * tape_length
    pos = 0

    jumpbacks = []
    reached_states = set()

    pos_instructions = 0
    while True:
        letter = instructions[pos_instructions]
        if letter == "+":
            registry[pos] = (registry[pos] + 1) % 256
        elif letter == "-":
            registry[pos] = (registry[pos] - 1) % 256
        elif letter == ">":
            pos += 1
            if pos >= tape_length:
                registry += [0]*tape_length
                tape_length = len(registry)
        elif letter == "<":
            pos -= 1
            if pos <= 0:
                registry = [0]*tape_length+registry
                tape_length = len(registry)
                pos += tape_length
        elif letter == "[":
            if registry[pos] == 0:
                nests = 1
                while nests:
                    pos_instructions += 1
                    if instructions[pos_instructions] == "[": nests += 1
                    elif instructions[pos_instructions] == "]": nests -= 1

                if jumpbacks == []:
                    reached_states.clear()

            else:
                jumpbacks.append(pos_instructions-1)

        elif letter == "]":
            stripped_registry = [str(x) for x in registry if x != 0]
            translated_pos = pos - (len(registry) - len(stripped_registry))
            state = (translated_pos, pos_instructions, ".".join(stripped_registry))
            if state in reached_states: return "Does not halt"
            elif len(reached_states) > LOOP_BOUND: return "Unknown"
            else:
                reached_states.add(state)
                pos_instructions = jumpbacks.pop()
        pos_instructions += 1
        if pos_instructions >= len(instructions): break
    return "Halts"

Pretty brute-forcey solution to the problem: just run the bf code. We assume the tape length is arbitrarily long and that individual cells wrap at 256. At the end of every loop, we store the state of the tape with a set. States are of the form (our position on the tape, our position on the instructions, what the tape looks like with leading 0's stripped).

If we store the same state twice, then we're somewhere in an infinite loop, so the program does not halt. If we store over 1,000 states, then cut losses and return unknown. Once we leave a loop we check to see if we aren't in any larger loops. If not, we're never seeing any of the previous states ever again (at the very least, the instruction position will always be different!) so we can clear the set of states.

This should accurately determine any BF program who's loops aren't longer than 1,000 iterations, as well as many programs that repeat a state before 1,000 iterations in a loop. Not all of them, though: something like "{1 million +'s here}[-]>+[+-]" eventually repeats a state, but the [-] loop passes 1,000 iterations first.

Some examples:

>+>->+>-

No loops, so it reaches the end and halts.

+[+]

Loop ends after 256 iterations, so it reaches the end and halts.

+[+-]

Eventually repeats the state (0,5,"1"), so it does not halt.

+[->+]

This doesn't repeat any states but the loop never ends, so it should print "unknown". But the program kind of cheats here. Instead of storing the position on the tape, it adds an offset between the original registry and the stripped one. If all a loop does is translate the tape by some spaces, then it will continue translating it indefinitely (like a life glider), so we can say it does not halt.

+[>+]

Doesn't translate, doesn't repeat any states, prints unknown.

+++++++++++[-]

This does halt, but it would print "unknown" if LOOP_BOUND was 10.

There's a couple of ways to make this smarter. You could obviously increase LOOP_BOUND to reduce the number of unknowns. You could have smarter handling of nested loops. You could probably do something fancy with BB numbers and the size of loops to better detect if something should halt, but I'm not good enough at CS nor at Python to be able to do that yet.


C# (.NET Core), 48 47 46 bytes, input as char array

s=>{for(int i=0;s[++i]==++s[0];);return s[0];}

Try it online!

Explanation: the first element in the array is incremented as well as a pointer iterating the following elements. When both the first element and the current element are different, it returns the first element.

C# (.NET Core), 58 56 50 bytes, input as string

s=>{var c=s[0];while(s.IndexOf(++c)>=0);return c;}

Try it online!

Previous 58-byte solution (referenced in the first comment):

s=>{for(int i=1;;i++)if(s[i]-s[0]>i)return(char)(s[i]-1);}

Algorithms using System.Linq

The following algorithms must add using System.Linq; (18 bytes) to the byte count and therefore are longer.

I quite liked this one (52+18 bytes):

s=>{int i=0;return(char)(s.First(c=>c-s[0]>i++)-1);}

And you also have a one-liner (45+18)-byte solution:

s=>(char)(s.Where((c,i)=>c-s[0]>i).First()-1)

And a very clever (37+18)-byte solution, courtesy of Ed'ka:

s=>s.Select(e=>++e).Except(s).First()


Python 3, 30 bytes

lambda l:sum(n**3&6for n in l)

Try it online!

(test cases shamelessly borrowed from xnor's answer)

How?

Given \$1\le n\le6\$, the number of petals can be computed with:

$$p=n^{2k+1} \operatorname{and}6,\:k\in\mathbb{N}^*$$

where \$\operatorname{and}\$ is a bitwise operator.

This can also be written as:

$$p=2\times\left\lfloor\frac{n^{2k+1}\bmod 8}{2}\right\rfloor$$

And is based on the fact that, for any \$k\ge1\$:

$$n^{2k+1}\bmod 8=\cases{
n&\text{if $n$ is odd ($1$, $3$ or $5$)}\\
0&\text{if $n$ is even ($2$, $4$ or $6$)}
}$$

More specifically, choosing \$k=1\$:

$$p=n^3 \operatorname{and}6$$

As Python code, the resulting expression is just as long as the nice n%-2%n found by xnor. But because it ends with a digit, we can get rid of the space just before the for, saving a byte.

 n | n**3 | as binary  | AND 6
---+------+------------+-------
 1 |    1 | 00000 00 1 |   0
 2 |    8 | 00001 00 0 |   0
 3 |   27 | 00011 01 1 |   2
 4 |   64 | 01000 00 0 |   0
 5 |  125 | 01111 10 1 |   4
 6 |  216 | 11011 00 0 |   0


05AB1E, 29 bytes

<ÝDâJU[X¹ä»,XÐÙg#Jþ2ô.R„  :)U

Try it online!

Space chosen as the char for the removed numbers (as it looks nice), but it could be replaced with any char without affecting byte-count.

Explanation

                                # implicit input n
<ÝDâ                            # cartesian product of [0..n-1] and [0..n-1]
    JU                          # join pairs and store in X
      [     XÐÙg#               # loop until there's only spaces left in X
       X¹ä                      # split X into n pieces
          »,                    # join rows by space and columns by newlines and print
                 Jþ             # join X to string and remove all non-digits
                   2ô.R         # split in pieces of 2 and pick a pair at random
                       „  :)    # replace this pair with 2 spaces
                            U   # and store in X


sed, 35

Raising the bar a bit with a postage-stamp sed meditation.

s/> / >/
s/ </< /
s/0</0>/
s/>1/<1/

The meditation is enjoyed on stdin/stdout on two computers, not necessarily connected by a network.  The meditation begins in the state

0         <       1

with guru zero on the left and one on the right.  The angle bracket moves left and right, and if a guru maneuvers their number to contact the cursor as it comes to their side, their score is increased by one, and they become elated with joy.

The meditation is initiated by typing the above state into sed -f medi.sed, and the computer responds with the next state.  The dutiful guru types that state into the meditation, reading aloud the next key they will press, with both gurus pressing the holy key to enter the future at the same time.  The dutiful computer replies with the next state.  This, in turn, is read aloud while typed in unison as with the last.  Continue advancing into the future until infinite bliss is achieved.

Gurus desiring a challenge may play 'turbo' mode, wherein the gurus attempt to collaboratively predict the computer's next state, and typing it into the prompt instead of the current state.  Gurus will have the wisdom to verify agreement between their predictions before entering the future.


Consistent Overhead Byte Stuffing (COBS)


JavaScript (ES6),  172 171  169 bytes
The output is 0-indexed.

a=>a.map((_,i)=>(D=m=>+m||m.reduce((s,[v],i)=>s+(i&1?-v:v)*D(m.map(([,...r])=>r).filter(_=>i--)),0))(a.map((v,y)=>a.map((_,x)=>x-i?x-~-Math.abs(y%(2*x)-x):v)))&&(j=i))|j

Try it online!
How?
This is essentially an implementation of Cramer's rule, except that the denominator is not computed.
Given the input vector of length \$n\$, we define \$W_n\$ as the matrix holding the waves, stored column-wise.
Example:
$$W_5=\begin{pmatrix}
1&1&1&1&1\\
1&2&2&2&2\\
1&1&3&3&3\\
1&2&2&4&4\\
1&1&1&3&5\end{pmatrix}$$
We compute all values \$v_i=\det(M_i)\$ with \$0\le i<n\$, where \$M_i\$ is the matrix formed by replacing the \$i\$-th column of \$W_n\$ with the input vector.
Example:
For the 5th test case and \$i=3\$, this gives:
$$v_3=\det(M_3)=\begin{vmatrix}
1&1&1&\color{red}1&1\\
1&2&2&\color{red}3&2\\
1&1&3&\color{red}3&3\\
1&2&2&\color{red}3&4\\
1&1&1&\color{red}1&5\end{vmatrix}=0$$
We return the highest index \$j\$ such that \$v_j\neq0\$.
Commented
The helper function \$D\$ uses Laplace expansion to compute the determinant:
D = m =>                     // m[] = matrix
  +m ||                      // if the matrix is a singleton, return it
  m.reduce((s, [v], i) =>    // otherwise, for each value v at (0, i):
    s                        //   take the previous sum s
    + (i & 1 ? -v : v)       //   based on the parity of i, add either v or -v
    * D(                     //   multiplied by the result of a recursive call:
      m.map(([, ...r]) => r) //     pass m[] with the 1st column removed
      .filter(_ => i--)      //     and the i-th row removed
    ),                       //   end of recursive call
    0                        //   start with sum = 0
  )                          // end of reduce()

The matrix \$M_i\$ is computed with:
a.map((v, y) =>         // for each value v at position y in the input vector a[]:
  a.map((_, x) =>       //   for each value at position x in the input vector a[]:
    x - i ?             //     if this is not the i-th column:
      x -               //       compute the wave of power x+1 at position y:
      ~-Math.abs(       //         x - (|y mod (2*x) - x| - 1)
        y % (2 * x) - x //         (where y mod 0 is coerced to 0)
      )                 //
    :                   //     else:
      v                 //       append the value a[y] of the input vector
  )                     //   end of inner map()
)                       // end of outer map()


Lex + C, 156 124 bytes
%{
p(b){putchar(strtol(yytext,0,b));}
%}
%option noyywrap
%%
0[01]{7} {p(2);}
[01].. {p(8);}
.. {p(16);}
%%
main(){yylex();}

Compile with:
lex mixed_base.l
cc -o mixed_base lex.yy.c


Python 2.7, 2013 score
This program can be used as reference, and you are allowed to take the following code and modify it and then post it in your own solutions.
In hindsight, I maybe should have used regex for the quote handling too, but I think in its current state it may be enough to jump-start people into the problem.
Why I chose Python 2.7:  I thought it would be easier to test to see if I made the program crash via the exec keyword.
This code intakes the program as in.txt.
I figured I should at least get the ball rolling for whoever want to participate by writing a quote parser (that also happens to handle comments) and a brief example on how regex, when combined with the quote parser can really change the game in terms of complexity of this problem.
Note: there is still plenty of room for improvement in this minifier.  Like you could play around with indentation, variable names, and removing the parenthesis when they're being used my keywords, like print or yield.
import re

with open("in.txt","r") as fi:
    code = fi.read()

class QuoteHandler():
    def __init__(self):
        pass
    def loadCode(self,code):
        quoteFlag = False
        currentQuoteChar = ""
        ignoreNext = False
        inEndLineComment=False
        startLocation = 0

        self.reAddStrings = []

        outStr = ""

        for i, character in enumerate(code):
            if ignoreNext:
                ignoreNext = False
            elif inEndLineComment:
                if character in "\r\n":
                    inEndLineComment=False
            elif character == "#" and not quoteFlag:
                inEndLineComment = True
            elif character in "'\"" and (currentQuoteChar == character or not quoteFlag):
                if quoteFlag:
                    self.reAddStrings.append(code[startLocation+1:i])
                else:
                    currentQuoteChar = character
                    startLocation = i
                quoteFlag = not quoteFlag
            elif character == "\\":
                ignoreNext = True

            if not inEndLineComment and not quoteFlag:
                outStr+=character
        return outStr

    def find_all_locations(self,substr,code):
        return [m.start() for m in re.finditer(substr, code)]

    def unloadCode(self,code):
        temp = self.reAddStrings[::-1]
        for i, location in enumerate(list(self.find_all_locations('"',code))[::-1]):
            code = code[:location] + "\"" + temp[i] + code[location:]
        return code

def applyRegexes(code):#\w here?
    operatorRegexCleaner = ["([\d\/*\-\"=,'+{}:[\](\)])","[ \t]+","(\w)"]
    regexes = [
        [''.join(operatorRegexCleaner),r"\1\2"],
        [''.join(operatorRegexCleaner[::-1]),r"\1\2"],#removes whitespace between operators
        ["\n\s*\n","\n"]#removes empty lines
    ]
    for regex in regexes:
        code = re.sub(regex[0],regex[1],code)
    return code

qh = QuoteHandler()
code = qh.loadCode(code)
code = applyRegexes(code)
code = qh.unloadCode(code)
print(code)
exec(code)

Output of program:
def factor(factor_number):
    for n in range(2,factor_number):
        if factor_number % n==0:
            yield(n)
def gcd(a,b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
         a,b=b,a%b
    return a
class Apricot:
    def __init__(self):
        self.mold=False
    def get(self):
        return self.mold
    def update(self):
        self.mold=not self.mold
    def blue(self):return5
def tell_me_about_these_numbers(*a):
    print("%d is the first number!" % a[0])
    print("{} / 3 is {}".format(a[0],a[0]/3.))
    myFavorate=Apricot()
    for number in a:
        print list(factor(number))
        myFavorate.update()
    print[gcd(a,b)for a,b in zip(a[:-1],a[1:])]
    print(myFavorate.get())
tell_me_about_these_numbers(5,6,9,45,200)
print"Let's play with scope!"
a,b=10,9
def randomFunction(a):
    print(a)
randomFunction(b)
print(a)
for a in range(100):
    b+=a
print(a)
print(b)
li=[]
for i in range(10):
 li.append(i*2)
print(li)
print([i*2for i in range(10)])
a=c=b=d=e=f=g=h=i=j=k=l=m=n=o=p=q=r=s=t=u=v=w=x=y=z=5
print(a)
a-=1
print(a)
g=10
print(str(10**g+5)[::-1])
def blue_fish(a):
    def blue_fish(a):
        def blue_fish(a):
            return a
        a+=1
        return blue_fish(a)
    a-=1
    return blue_fish(a)
print(blue_fish(10))
def blue_fish(a):
    if a==0:
        return"0"
    return"1" +blue_fish(a-1)
print(blue_fish(5))
blue_fish=lambda a,b,c:a*b*c
print(blue_fish(1,2,3))
blue_fish=lambda*a:reduce(lambda a,b:a*b,a)
print(blue_fish(1,2,3))
print(max([[6,1],[5,2],[4,3],[3,4],[2,5],[1,6]],key=lambda a:a[1]))
print(zip(*[[1],[2],[3],[4],[5]]))
print"Now let's test to see if you handle quotes correctly:"
print"test \'many diffent\' \"types of \" quotes, even with \' \" trailing quotes"
print"""

Multi line quotes are great too!

"""
a=""" ::
one more multi-line quote won't hurt
"""
print a


APL 1.0986122886681098
3⍟⎕

⎕ Requests numerical screen input. Examples of use:
      3⍟⎕
      10
2.0959032742893844

      3⍟⎕
      1E1
2.0959032742893844

      3⍟⎕
      ○1
1.041978045992186

In the last example ○1 represents pi.


JavaScript (ES6), 90 88 bytes

Takes input as an array of 6 digits. Returns a string describing a possible solution (such as '54*3==162') or exits with a 'too much recursion' error if (and only if) there's no solution.

f=(a,k=1)=>eval(s='01*2==345'.replace(/\d/g,n=>a[n],a.sort(_=>(k=k*2%3779)&2)))?s:f(a,k)

How it works

This is a deterministic algorithm.

The primes P=2 and Q=3779 were chosen in such a way that the sort callback (k = k * P % Q) & 2 is guaranteed to generate all 720 possible permutations of the input array over time. More precisely, all permutations are covered after 2798 sorts -- which should be within the recursion limit of all browsers.

We inject each permutation in the expression 01*2==345 by mapping the digits to the corresponding entries in the array.

We evaluate this expression and do recursive calls until it's true.

Test

f=(a,k=1)=>eval(s='01*2==345'.replace(/\d/g,n=>a[n],a.sort(_=>(k=k*2%3779)&2)))?s:f(a,k)

console.log(f([1,2,3,4,5,6])); // 54*3==162
console.log(f([2,3,4,5,6,7])); // 52*7==364
console.log(f([1,2,3,4,6,7])); // 73*2==146


Jelly, 6 bytes

n⁶Sċ2Ẓ

Try it online!

Explanation:

n⁶Sċ2Ẓ  args: z (e.g. [['/', 'o', '\\'], [' ', '-']] => 0)
        implicit return value: z ([['/', 'o', '\\'], [' ', '-']])
n⁶      dyad-nilad pair ([[1, 1, 1], [0, 1]])
 ⁶       4th command-line argument or space [4th CLA assumed absent] (' ')
n        vectorized inequality ([[1, 1, 1], [0, 1]])
  S     reduction by addition with base case 0 ([1, 2, 1])
   ċ2   dyad-nilad pair (1)
    2    literal (2)
   ċ     number of occurrences of right in left (1)
     Ẓ  primality (0)


Haskell, 62 bytes

f takes a list of integers and returns an integer.

f l=maximum[x+sum m-sum n|x:m<-t l,y:n<-t m,x==y]
t=scanr(:)[]

Try it online!

How it works

t is the standard "get all suffixes of a list without importing Data.List.tails" function.
In f l, the list comprehension iterates through all the non-empty suffixes of the argument list l, with first element x and remainder m.
For each, it does the same for all nonempty suffixes of m, selecting first element y and remainder n.
If x and y are equal, the list comprehension includes the sum of the elements between them. This sublist is the same as x:m with its suffix n stripped off, so the sum can be calculated as x+sum m-sum n.


Number of distinct non-empty subsequences of binary expansion

Python 3, 95 bytes  83 bytes

[-12 bytes thanks to Mr.XCoder :)]

def f(x):
 v=[2,1];c=1
 for i in bin(x)[3:]:k=int(i);c+=v[k];v[1-k]+=v[k]
 return c

Try it online!

A note on the algorithm.
The algorithm computes the increment in unique subsequences given by the bit at a given position t.
The increment for the first bit is always 1. The algorithm then runs over the sequence of bits s(t) and adds the increment v[s(t)]. At each step, the increment for the complement of s(t), v[1 - s(t)] is updated to v[1]+v[0].
The final number is the sum of all increments.

It should run in O(log2(n)), where n is the input number.


Multiples of 67 in a constructed array of arrays?

Haskell - 86 chars

98 → 92: Use list comprehensions and sum instead of filter and length.

92 → 86: Convert nested list comprehensions into one, and change ==0 to <1 (thanks st0le).

f s=zipWith(+)s$tail s
main=print$sum[1|r<-take 50$iterate f[1,3..99],n<-r,n`mod`67<1]

Ungolfed:

initialRow :: [Integer]
initialRow = [1,3..99]

nextRow :: (Num a) => [a] -> [a]
nextRow xs = zipWith (+) xs (tail xs)

triangle :: [[Integer]]
triangle = takeWhile (not . null) $ iterate nextRow initialRow

main = print $ length $ filter ((== 0) . (`mod` 67)) $ concat triangle


Pyth, 34

FNyUz#aYmv:zhdedC,+0N+NlzB)efqSTTY

Try it online here. Notice, this has a time (and space) complexity of O(n). Therefore the test case 12345678901234567890 takes too long in the online compiler. Use the offline one instead (1 minute on my laptop).

This is only my first attempt. There might be some room for improvements.

First some ideas how my algorithm works.

I interpret the input as string and not as a number.
Then I create all possible subsets of [0, 1, 2, ..., len(n-1)]
For each of these subsets (lets take [1, 4, 5]), I split the input string into part using these numbers. [input[0:1], input[1, 4], input[4,5], input[5,len(input)]].
Afterwards I try to convert these numbers into strings. There can be two problems. Pyth (or Python) throws an exception for an empty string, and for a string of numbers starting with 0. Therefore I use a try - catch block (actually infinity loop with an immediate break). If converting was successfully, I add the result to a list Y.
After I handled all subsets, I filter the list Y for results, that are already sorted and print the last one (the last one has the most groups).

Now the detailed explanation:

                            Implicit: z = input() (z is a String!)
                                      Y = empty list
FNyUz                       for each subset N of [0, 1, 2, ..., len(z)-1]:

     #                         start try-catch block (actually an infinite loop,
                               but the Python implementation uses a try catch.

      aY                          append to Y:
                C,+0N+Nlz            zip([0] + N, N + [len(z)])
        m                            map each element d to
          :zhded                     z[d[0]:d[-1]]
         v                           evaluated
                         B        if this didn't throw an exception already, end the infinite loop
                          ) end for loop

 f    Y      filter Y for elements T, for which
  qSTT           sorted(T) == T
e            and print the last one (the subsets generated with yUz are sorted
             by length, so the last one has the most groups)


Python, 1,291 1,271 1,225 bytes

As Martin noted, this problem can be largely reduced to his excellent rubber band challenge.
Using that challenge's terminology, we can take as the second set of nails the points of intersection between the circles on the boundary of the enclosed area:

As the rubber band we can take any path P between the two endpoints that runs inside the enclosed area.
We can then invoke a solution to the rubber-band problem to produce a (locally) minimal path.
The challenge is, of course, to find such a path P, or more precisely, to find enough paths so that at least one of them produces the globally minimal path (note that in the first test-case we need at least one path to cover all possibilities, and in the second test-case at least two.)

A naive approach would be to just try all possible paths:
For every sequence of adjacent (i.e. intersecting) circles that connects the two endpoints, take the path along their centers (when two circles intersect, the segment between their centers is always within their union.)
Though this approach is technically correct, it can lead to a ridiculously large number of paths.
While I was able to solve the first test-case using this approach within a few seconds, the second one took forever.
Still, we can take this method as a starting point and try to minimize the number of paths we have to test.
This is what follows.

We construct our paths by basically performing a depth-first search on the graph of circles.
We're looking for a way to eliminate potential search directions at each step of the search.

Suppose that at some point we're at a circle A, that has two adjacent circles B and C, which are also adjacent to each other.
We can get from A to C by visiting B (and vice versa,) so we might think that visiting both B and C directly from A is unnecessary.
Unfortunately, this is wrong, as this illustration shows:

If the points in the illustration are the two endpoints, we can see that by going from A to C through B we get a longer path.

How about this one: if we're testing both the moves A→B and A→C, then it's unnecessary to test A→B→C or A→C→B, since they can't result in shorter paths.
Wrong again:

The point is that using purely adjacency-based arguments is not going to cut it; we have to use the geometry of the problem as well.
What the two above examples have in common (as well as the second test-case on a larger scale,) is that there's a "hole" in the enclosed area.
It manifests itself in the fact that some of the points-of-intersection on the boundary—our "nails"—are within the triangle △ABC whose vertices are the circles' centers:

When this happens, there's a chance that going from A to B and from A to C will result in different paths.
More importantly, when it doesn't happen (i.e. if there wasn't a gap between A, B and C) then it's guaranteed that all paths starting with A→B→C and with A→C and which are otherwise equivalent will result in the same locally minimal path, hence if we visit B we don't need to also visit C directly from A.

This leads us to our elimination method:
When we're at a circle A, we keep a list H of the adjacent circles we've visited.
This list is initially empty.
We visit an adjacent circle B if there are any "nails" in all the triangles formed by the centers of A, B and any of the circles in H adjacent to B.
This method dramatically drops the number of paths we have to test to just 1 in the first test-case and 10 in the second one.

A few more notes:

It's possible to decrease the number of paths we test even further, but this method is good enough for the scale of this problem.
I used the algorithm from my solution to the rubber-band challenge.
Since this algorithm is incremental it can be pretty easily integrated into the path-finding process, so that we minimize the path as we go along.
Since many paths share a starting-segment, this can significantly improve performance when we have lots of paths.
It can also hurt performance if there are much more dead-ends than valid paths.
Either way, for the given test-cases performing the algorithm for each path separately is good enough.
There's one edge-case where this solution may fail:
If any of the points on the boundary is the point of intersection of two tangent circles then under some conditions the result can be wrong.
This is due to the way rubber-band algorithm works.
With some modifications it's possible to handle these cases as well, but, hell, it's already long enough.

# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}
# Second test case
#I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.),((180.,230.),39.),((162.,231.),39.),((157.,281.),23.),((189.,301.),53.),((216.,308.),27.),((213.,317.),35.),((219.,362.),61.),((242.,365.),42.),((288.,374.),64.),((314.,390.),53.),((378.,377.),30.),((393.,386.),34.)}

from numpy import*
V=array;X=lambda u,v:u[0]*v[1]-u[1]*v[0];L=lambda v:dot(v,v)
e=V([511]*2)
N=set()
for c,r in I:
 for C,R in I:
  v=V(C)-c;d=L(v)
  if d:
    a=(r*r-R*R+d)/2/d;q=r*r/d-a*a
    if q>=0:w=V(c)+a*v;W=V([-v[1],v[0]])*q**.5;N|={tuple(t)for t in[w+W,w-W]if all([L(t-T)>=s**2-1e-9 for T,s in I])}
N=map(V,N)
def T(a,b,c,p):H=[X(p-a,b-a),X(p-b,c-b),X(p-c,a-c)];return min(H)*max(H)>=0
def E(a,c,b):
 try:d=max((X(n-a,b-a)**2,id(n),n)for n in N if T(a,b,c,n)*X(n-b,c-b)*X(n-c,a-c))[2];A=E(a,c,d);B=E(d,c,b);return[A[0]+[d]+B[0],A[1]+[sign(X(c-a,b-c))]+B[1]]
 except:return[[]]*2
def P(I,c,r,A):
 H=[];M=[""]
 if L(c-e)>r*r:
    for C,R in I:
     if L(C-c)<=L(r+R)and all([L(h-C)>L(R+s)or any([T(c,C,h,p)for p in N])for h,s in H]):v=V(C);H+=[(v,R)];M=min(M,P(I-{(C,R)},v,R,A+[v]))
    return M
 A+=[e]*2;W=[.5]*len(A)
 try:
  while 1:
    i=[w%1*2or w==0for w in W[2:-2]].index(1);u,a,c,b,v=A[i:i+5];A[i+2:i+3],W[i+2:i+3]=t,_=E(a,c,b);t=[a]+t+[b]
    for p,q,j,k in(u,a,1,i+1),(v,b,-2,i+len(t)):x=X(q-p,c-q);y=X(q-p,t[j]-q);z=X(c-q,t[j]-q);d=sign(j*z);W[k]+=(x*y<=0)*(x*z<0 or y*z>0)*(x!=0 or d*W[k]<=0)*(y!=0 or d*W[k]>=0)*d
 except:return[sum(L(A[i+1]-A[i])**.5for i in range(len(A)-1)),id(A),A]
print V(P(I,e*0,0,[e*0]*2)[2][1:-1])

Input is given through the variable I as a set of tuples ((x, y), r) where (x, y) is the center of the circle and r is its radius.
The values must be floats, not ints.
The result is printed to STDOUT.

Example

# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}

[[   0.            0.        ]
 [ 154.58723733  139.8329183 ]
 [ 169.69950891  152.76985495]
 [ 188.7391093   154.02738541]
 [ 325.90536774  109.74141936]
 [ 382.19108518  109.68789517]
 [ 400.00362897  120.91319495]
 [ 511.          511.        ]]


Resolve doubling and tripling actions in Dominion

GolfScript (29 26 bytes)

](1/{\1+(3&@*.23-\1$-@+}/;

Online demo

Dissection

This slightly abuses the loose typing of GolfScript. The stack of how many times to repeat subsequent actions starts out as an array and later turns into a string - but 1+ appends a 1 and (3& pops the first value and correctly puts it in the range 0 to 3 regardless of the type change.

](         # Push an empty array under the input string to serve as rep stack
1/{        # Loop over the input string as a series of 1-char strings
           #   Stack is ... reps ch
           #   where the ... covers zero or more strings which will be output
  \        #   Bring the rep stack to the top
  1+(      #   Push a `1` on the bottom of it to avoid underflow and then pop
  3&       #   Coerce to correct range, because if rep stack is a string then
           #   we just got an ASCII value
  @*       #   Apply repetition to the 1-char string: it's now an n-char string
  .23-     #   Duplicate it and remove chars '2' and '3': this becomes output
  \1$-     #   Get the original copy and remove the output string's chars
           #   So the stack is now ... reps output non-output
           #   where non-output is either an empty string or a string of '2's
           #   or '3's
  @+       #   Push non-output onto the repetition stack
}/         # Loop
;          # Pop whatever's left of the repetition stack


05AB1E, 7 bytes

b0Ü‚DíQ

Try it online!
or as a Test Suite

Explanation

b         # convert input to binary
 0Ü       # remove trailing zeroes
   ‚      # pair with input
    D     # duplicate
     í    # reverse each (in the copy)
      Q   # check for equality


Charcoal, 21 bytes

≔Φ⪪⍘Ｎ²1ιθＩ×Ｌθ⬤θ№θ×0⊕κ

Try it online! Link is to verbose version of code. Outputs 0 for irrelevant numbers. Happens to output 1 for 0 as per the OEIS sequence. Explanation:

≔Φ⪪⍘Ｎ²1ιθ

Convert the input to binary, split on 1s, and remove empty elements.

Ｉ×Ｌθ⬤θ№θ×0⊕κ

Check that the array contains all lengths of 0s and output its length if it does or 0 if it does not.


Cause maximal disruption to a Straw Poll

Mathematica, 19 44 bytes
...(loud complaining)
(x=Median@#[[;;Mod[Length@#,2]-3]];#≤x&/@#)&

Test:
{Test, data, goes, here};
(x=Median@#[[;;Mod[Length@#,2]-3]];#≤x&/@#)&
%%+Boole/@%


Ruby 1.9 + SDL (341 324 316)

Here's a first attempt at a Ruby version using the SDL library.  I can save 6 characters if I'm allowed to load the SDL library using -rsdl on the command line instead of the require statement.

require'sdl'
f=o=d=3
s=SDL::Screen.open l=32,l,0,0
r=*0..l*l
loop{f==o ?f=(r-$*).sample: $*.shift
/yU/=~"#{e=SDL::Event.poll}"&&(v=e.sym%4)&&d+v!=3&&d=v
$><<"Score #{$*.size}"&&exit if$*.index(n=o+[-1,-l,l,1][d])||n<0||n>=l*l||d%3<1&&n/l!=o/l
$*<<o=n
r.map{|i|s[i%l,i/l]=[[f,*$*].index(i)?0:255]*3}
s.flip
sleep 0.1}

The snake segments and food pieces are represented using black pixels, the grid size is currently 32*32.  You can control with the arrow keys (or any keys really, the keycode mod 4 indexes the direction array [LEFT, UP, DOWN, RIGHT]).  I think there's definitely room for improvement here, especially in the death-checking IF statement.

I've vastly improved this over the previous version, hopefully it more closely matches the spirit of the question now.  There's one thing I need to fix to comply with the spec, which is that food can currently spawn inside the tail. Fixed!

Prints the score to stdout after the game is completed.


Choose 3 strings and output the exact minimum Hamming distance between any pair

Pari/GP, 92 90 bytes

2 bytes saved thanks to @Nicolas!

n->sum(a=0,n,sum(b=0,n-a,sum(c=0,n-a-b,n!/a!/b!/c!/(n-a-b-c)!*min(a+b,min(a+c,b+c)))))/4^n

Try it online!

$$ f(n) = \frac{1}{4^n} \sum_{\substack{a+b+c+d=n\\a,b,c,d\geq 0}} \binom{n}{a,b,c,d}\min(a+b,a+c,b+c)$$

A more direct brute force approach may be shorter in some languages, but I'm not sure if that's true for Pari. Anyway, it's a shame that Pari's min only accepts two arguments.

I can avoid the min and be about 6 times faster, but the compensating additional code makes it longer. Maybe in another language this is the shorter way. And maybe it is possible to simplify further and get rid of the innermost sum.

n->sum(a=0,n,sum(b=a,n-a,sum(c=b,n-a-b,n!/a!/b!/c!/(n-a-b-c)!*(a+b)*6/(1+(a==b)+(b==c))!)))/4^n

Try it online!


Python, 42 bytes

from math import*
lambda x,n:sin(x+pi/2*n)

Uses the fact that differentiating shifts the function by pi/2 left.


Compute 30000 Digits of Pi (π), as Fast as Possible

Python 2 (Spigot Algorithm)

This is just Jeremy Gibbon's algorithm implemented in python. Definitely will be faster once someone else implements this in another language. Other methods might be faster too since I started working on this when the rules stated that I could only use integers. I originally tried doing this without string conversion and joining, but it was actually slower..

def p():
 q,r,t,j=1,180,60,2
 while True:
    u,y=3*(3*j+1)*(3*j+2),(q*(27*j-12)+5*r)//(5*t);yield y;q,r,t,j=10*q*j*(2*j-1),10*u*(q*(5*j-2)+r-y*t),t*u,j+1
p=p()
print''.join(str(p.next())for x in[1]*30000)

Completes on my work machine in about 53 seconds.


Zero Information Bot
function ZeroInformationBot(people, bots, data) {
    if (!data) {
        data = {
            botData: [],
            knaves: [],
            guess: "",
            newKnaves: false,
            attestations: Array(36).fill(0),
            threshold: -5,
        };
    }
    let newResponses = [];
    readResponses().forEach(res => {
        if (!data.botData[res.uid][res.index]){
            newResponses.push(res);
            data.botData[res.uid][res.index] = res.char;
        }
    });
    newResponses.forEach(res => {
        if (people.find(p => (p[0].index == res.index && p[0].char == res.char) || (p[1].index == res.index && p[1].char == res.char))){
            people.forEach((p, i) => {
                if ((p[0].index == res.index && p[0].char == res.char) || (p[1].index == res.index && p[1].char == res.char)) data.attestations[i] += 2;
                if ((p[0].index == res.index && p[0].char != res.char) || (p[1].index == res.index && p[1].char != res.char)) data.attestations[i] -= 1;
                if (data.attestations[i] < -1 && !data.knaves.find(i)) {
                    data.knaves.push(i);
                    data.newKnaves = true;
                }
            });
        }
    });
    viewRequests().forEach(req => {
        if (!data.botData[req.uid]){
            data.botData[req.uid] = Array(36).fill([]);
        } else if (!data.botData[req.uid][req.index]) {
            sendRequest(req.uid, req.index);
            data.botData[req.index] = "-"
        } else if (data.botData[req.uid][req.index] != "-") {
            replyRequest(req.uid, req.index, data.botData[req.uid][req.index]);
        }
    });
    if (!data.newKnaves && data.guess) return data.guess;
    data.newKnaves = false;
    let detected = true;
    let loop = false;
    let possibilities;
    while (detected){
        detected = false;
        possibilities = Array(36).fill(new Set());
        let examined = [], chargroups = [];
        people.forEach((p, i) => {
            if (data.knaves.find(i)) return;
            possibilities[p[0].index].add(p[0].char);
            possibilities[p[1].index].add(p[1].char);
            let first = examined.find(e => e.index == p[0].index && e.char == p[0].char);
            let second = examined.find(e => e.index == p[1].index && e.char == p[1].char);
            if (first && !second){
                chargroups[first.group].push(p[1]);
                examined.push({index: p[1].index, char: p[1].char, group: first.group});
            } else if (!first && second){
                chargroups[second.group].push(p[0]);
                examined.push({index: p[0].index, char: p[0].char, group: second.group});
            } else if (!first && !second){
                examined.push({index: p[0].index, char: p[0].char, group: chargroups.length});
                examined.push({index: p[1].index, char: p[1].char, group: chargroups.length});
                chargroups.push(p);
            } else if (first && second && first.group != second.group){
                chargroups[first.group].push(...chargroups[second.group]);
                examined = examined.map(e => {
                    if (e.group == second.group) e.group = first.group;
                    return e;
                });
                chargroups.splice(second.group, 1);
            }
        });
        possibilities.forEach((p, i) => {
            if (p.size == 1) {
                let char = Array.from(p)[0];
                chargroups.forEach(c => {
                    if (c.find(ch => ch.index == i && ch.char != char)) {
                        people.forEach((person, j) => {
                            if (data.knaves.find(j)) return;
                            // We don't need to check both characters; if one's in the group they both are.
                            if (c.find(ch => ch.index == person[0].index && ch.char == person[0].char)) {
                                data.knaves.push(j);
                                detected = true;
                            }
                        });
                    }
                });
            } else if (p.size == 0) {
                // Uh oh... need to reset.
                data.knaves = [];
                data.attestations.forEach((a, i) => {
                    if (a <= data.threshold) data.knaves.push(i);
                });
                detected = true;
                // Don't get stuck in a loop.
                if (loop) data.threshold--;
                loop = true;
            }
        });
    }
    data.guess = possibilities.map(p => Array.from(p)[0]).join("");
    return data.guess;
}

This bot lets out exactly zero information.  Whenever it's asked about something, it responds by first asking what that bot thinks, and then it replies with that data.
It counts up the number of times that other bots have given it one of the values of one of the people, and uses that to give a rough confidence score to each person, tentatively marking someone as a knave if they hit -2.  If it hits a paradox, it resets who it's considering as a knave, but only automatically re-marks someone as a knave if they have a score of -5 or worse.
Because this bot doesn't aggressively attempt to solve, it's quite possible it'll get stuck on one or two people for a long time; I'm interested in how well it will do.  I haven't tested it yet, as it seems the controller is still (slightly) in flux.


JavaScript (Node.js), 54 bytes

x=>g(g(x))<2;g=(x,i=1,j=1)=>j>x?x&&g(x-i)+1:g(x,j,i+j)

Try it online!


Matlab/Octave Eratosieve using minimal big-O iterations

Here's my solution
The loop clearly runs O(logn) times and it's easy to see that the number of operations is bounded above by the normal number of operations for SOE(2n) so it's within O(nlog(logn)) big-O running time

function [primes] = eratosieve(n)
    isprime = ones(n, 1);
    isprime(1) = false;
    m = 1;
    while(m ^ 2 < n)
        nprimes = find(isprime(m + 1 : m * 2)) + m;
        mult = (m + 1) : (n/(m + 1));
        a = nprimes * mult;
        isprime(a(a<=n)) = false;
        m *= 2;
    end
    primes = find(isprime);
endfunction


Haskell 310 bytes

w i=putStr$unlines$reverse$b i 0 0[][]
b 0 _ _ w r=e w r
b c l 0 w r=b c(l+1)l(e w r)[]
b c l p w r=b(c-1)l(p-1)w(n(++)["  ||    ","  ||    ","///\\\\\\  "," //\\\\   ","  /\\    "]r)
e w r=t++n(n d)(map(\t->"    "++t)w)c where(t,c)=splitAt 2 r
n f(a:c)(b:d)=f a b:n f c d
n _ a[]=a
n _ _ a=a
d d ' '=d
d _ d=d

Call it with w 5, for example.

Here the uncompressed code:

-- TreeTree
-- by Gerhard
-- 12 February 2017

module TreeTree (wood,test) where

type Tree = [String]

-- Test cases
test = do
 wood 0
 wood 1
 wood 2
 wood 3
 wood 4
 wood 5

-- build wood
wood :: Int -> IO ()
wood i = printTree $ buildWood i 0 0 [] []

-- Prints the trees
printTree :: Tree -> IO ()
printTree = putStr . unlines . reverse

-- build wood
buildWood :: Int -> Int -> Int -> Tree -> Tree -> Tree
buildWood 0 _ _ w r = concatTree w r
buildWood c l 0 w r = buildWood c (l+1) l (concatTree w r) []
buildWood c l p w r = buildWood (c-1) l (p-1) w (addTree r)

-- indent definition
space :: String
space = "    "

-- tree definition
tree :: Tree
tree = reverse [
 "  /\\    ",
 " //\\\\   ",
 "///\\\\\\  ",
 "  ||    ",
 "  ||    "]

-- Add a Tree on the left side
addTree :: Tree -> Tree
addTree = match (++) tree

-- add tree row at the bottom of the wood
concatTree :: Tree -> Tree -> Tree
concatTree w r = trunk ++ matched
 where
  wood = grow w
  (trunk, crown) = splitAt 2 r
  matched = matchTree wood crown

-- elnarge forrest on the left side to match next tree line
grow :: Tree -> Tree
grow = map (\t -> space ++ t)

-- match
match :: (a -> a -> a) -> [a] -> [a] -> [a]
match f (a:az) (b:bz) = f a b : match f az bz
match _ a [] = a
match _ _ a  = a

-- match trees
matchTree :: Tree -> Tree -> Tree
matchTree = match matchLine

-- match lines
matchLine :: String -> String -> String
matchLine = match matchChar

-- match chars
matchChar :: Char -> Char -> Char
matchChar c ' ' = c
matchChar _ c   = c

-- End


R, 16/30 = 0.53333...

Edit:
Here is a version that has been golfed down to 259 bytes. I am sure a much better bytecount is possible. This version takes advantage of the fact that T is a global variable in R which can be treated as having a value of 1. If T has been reassigned in your R environment, results may differ.
The code produces some warnings, but they can be ignored.

f=function(A){L=function(p){q=1-p;z=.1*p%o%q;x=z+t(z)+.3*(p%o%p+q%o%q);c(sum(log(x^A*(1-x)^(1-A))),(A/x-(1-A)/(1-x))%*%(2*p-1))};x=tanh(rnorm(100))/2+.5;for(i in x){t=.5+tanh(atanh(2*x-1)+T*2*(L(x)[2:101]>0)-T)/2;if(L(t)>L(x)){x=t;T=2*T}else{T=T/2}};round(x)}

If the adjacency matrix of your graph is saved as a 100x100 matrix A in R, then the vector of communities is f(A). It will probably make less than one mistake!

Explanation
It treats the problem as fitting a statistical model (it helps that it knows the values 0.3 and 0.1) and fits it using a sort of gradient ascent algorithm. The community membership vector is treated as containing values in [0,1], rather than just zeroes and ones. This enables the model to be fitted using a sort of gradient ascent. (Ascent and descent is actually by a fixed amount delta in each coordinate, to avoid various problems. If a step of gradient ascent fails, delta is adjusted down.) It's quite fast and does pretty well.
I used today's date as the random seed.
LL <- function(p, A){
# log-lieklihood of the model
  q <- 1-p
  x <- 0.1*(p %o% q) + 0.1*(q %o% p) + 0.3*(p %o% p) + 0.3*(q %o% q)
  sum(A*log(x) + (1-A)*log(1-x))
}

expit <- function(x) exp(x)/(1+exp(x))

gradLL <- function(p, A){
# (scalar multiple of) the gradient of the log-likelihood
  q <- 1-p
  x <- 0.1*(p %o% q) + 0.1*(q %o% p) + 0.3*(p %o% p) + 0.3*(q %o% q)
  drop((A/x - (1-A)/(1-x)) %*% (0.4*p - 0.2))
}

fit_model <- function(A, N=100){
# gradient ascent
  x <- rnorm(100)
  score <- LL(expit(x), A)
  delta <- 1
  for (i in 1:N){
    grad <- gradLL(expit(x), A)
    test <- x + delta*((grad > 0) - (grad < 0))

    test_score <- LL(expit(test), A)
    if (test_score > score){
      score <- test_score
      x <- test
      #print(score)
      delta <- (1/0.7)*delta
    } else {
      delta <- 0.7*delta
    }
  }
round(expit(x))
}

generate_A <- function(){
# generate a matrix for testing
  comms <- sample(0:1, 100, replace=T)
  A <- matrix(rep(0, 100^2), nc=100)
  for (i in 1:(nrow(A)-1)){
    for (j in (i+1):ncol(A)){
      prob <- ifelse(comms[i]==comms[j], 0.3, 0.1)
      if (runif(1) < prob) A[i,j] <- 1
    }
  }
  A <- (A + t(A))/2
  list(A=A, comms=comms)
}

test <- function(){
# test the fitting function once
  dat <- generate_A()
  fit <- fit_model(dat$A)
  sum(fit==dat$comms)
}

### performance ###

strings <- readLines("community-graphs.txt", 30)

total <- 0

set.seed(011215) # note that output is random!

for (i in 1:30){
  str_data <- strsplit(strings[i], ";")[[1]]
  comms <- as.numeric(strsplit(str_data[1], "")[[1]])
  A_str <- strsplit(str_data[2], ",")[[1]]
  A <- matrix(rep(0, 100^2), nc=100)
  for (r in 1:100){
    A[r,] <- as.numeric(strsplit(A_str[r], "")[[1]])
  }
  out <- fit_model(A)
  total <- total + min(sum(out==comms), sum(out!=comms))
}

total # 16


Code Golf Christmas Edition: How to print out a Christmas tree of height N

Brainfuck, 240 characters

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

Not yet done.  It works, but only with single-digit numbers.

EDIT: Done!  Works for interpreters using 0 as EOF.  See NOTEs in commented source for those with -1.

EDIT again: I should note that because Brainfuck lacks a standard method for reading command line arguments, I used stdin (standard input) instead.  ASCII, of course.

EDIT a third time: Oh dear, it seems I stripped . (output) characters when condensing the code.  Fixed...

Here's the basic memory management of the main loop.  I'm sure it can be heavily optimized to reduce the character count by 30 or so.

Temporary
Copy of counter
Counter (counts to 0)
Space character (decimal 32)
Asterisk character (decimal 42)
Number of asterisks on current line (1 + 2*counter)
Temporary
New line character
Temporary?
Total number of lines (i.e. input value; stored until the very end, when printing the trunk)

Condensed version:

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

And the pretty version:

ASCII to number
,>
++++++++[-<------>]  = 48 ('0')

Second digit (may be NULL)
,
NOTE:   Add plus sign here if your interpreter uses negative one for EOF
[ NOTE: Then add minus sign here
 >++++++++[-<------>]
 <<[->++++++++++<]>>  Add first digit by tens
]

Duplicate number
<[->+>+>>>>>>>+<<<<<<<<<]>>

Space char
>>++++++++[-<++++>]

Asterisk char
>++++++[-<+++++++>]

Star count
+

New line char
>>>++[-<+++++>]<<<

<<<

Main loop
[
Print leading spaces
-[>.<-]

Undo delete
<[-<+>>+<]
<[->+<]
>>

Print stars
>>>[-<.>>+<]

Add stars and print new line
>[-<+>]
>.<
<++

<<<

-<->
End main loop
]

Print the trunk
>>>>>>>
-[-<<<<<<.>>>>>>]
<<<<<.

Merry Christmas =)


V, 27 bytes
ÎdW40|D
Í üî
Ó../<C-v><C-v>x&
éiD@"

Try it online!
Note that <C-v> represents the unprintable character 0x16.
Explanation
This answer is pretty fun because it's about modifying the input into V code and then executing that code. I'll explain each command one at a time
Î                " On every line:
 dW              "   Delete a word
   40|           "   Move to the 40th column
      D          "   Delete everything after this

Í                " Remove all occurrences of
                 " A space
  üî             " or a newline

Now the buffer looks like this:
1f8b080849202258000370696c6c6f772e74787400d3d707821810d02799c545ba9641a1994c7d60d650d53c44a38a22cd4334aa28d23c44a38a22cd4334aa28d20c00fd512d46b8050000

The command to insert a character by its hex value is
<C-v>x<hex-value>

Here is where we start transforming it into actual V code.
Ó                " Replace
 ..              "   Two characters
   /             "   with
    <C-v><C-v>x  "   the text "<C-v>x"
               & "   And the two characters we just matched

<C-v>x1fi<C-v>x8bi<C-v>x08i<C-v>x08i<C-v>x49...

But the command has to be in insert mode. So we insert an 'i' at the beginning.
éi               " Insert an 'i'
  D              " Delete this line
   @"            " And evaluate it as V code


MATL, 10 bytes

-jowXncUX>

This uses version (9.2.1) of the language/compiler, which is earlier than this challenge.

It takes three inputs from stdin in this order: string length, number of removed characters, string.

Example

>> matl
 > -jowXncUX>
 >
> 7
> 4
> 1789823
983

EDIT: Try it online! (the code in the link has XN instead of Xn to conform to changes in the language after this challenge; also, o is not needed anymore)

Explanation

(This still costs 2 bytes more than it should due to Octave's and Matlab's nchoosek function behaving differently. Fixed in the next release of the compiler.)

-        % implicitly input two numbers, and subtract them
jo       % input string, and convert to ASCII codes
wXn      % swap inputs. Generate all combinations, each in a row
c        % convert to char array
U        % convert each row to a number
X>       % get maximum. Implicitly display

Answer to original challenge (stricter input requirements): 16 bytes

jYbZ)b-wowXncUX>

Uses current version (9.2.1) of the language/compiler.

Example

>> matl jYbZ)b-wowXncUX>
> 4 1789823 7
983

Explanation

(This should have been 4 bytes less, but I need that wow...c because Octave's nchoosek function, unlike Matlab's, doesn't work with character input. Will be fixed for next release of the compiler.)

j              % input string
YbZ)           % split at spaces into strings
b-             % subtract first and third (1-digit) strings
wow            % convert middle string into ASCII codes
Xn             % get all combinations, each in a row
c              % convert to char array
U              % convert each row to a number
X>             % get maximum. Implicitly display


Python 2, 163 130 127 121 115 99 96 bytes

i=input() ###
print(i+i[-2:0:-1]+i)[:len(i)*(len(i)%3%2or 3):3]

#'p lr+yi  n'ottk(ca'eyPf'er)

Try it online!

Outputs:

int #rt+-01i:n)l(%2 :
print('Perfect' + # 33o3ie*(l)]:2i(i
#(p=iu)#pni[:-+[ei(n)%r)]
'ly okay')


Haskell, 87 80 89
s%[]=s
(x:a)%q|x<=q!!0=x:a%q
p%q=q%p
j(x:y:s)=x%y:j s
j a=a
r[x]=x
r s=r$j s
s=r.map(:[])

This is merge sort, implemented from the bottom up.
first we package every element into it's own list, and then merge them two-by-two, and again merge them two-by-two, until we're left with one list.
(%) is the merge function
j merges pairs in a list of lists
r merges a complete list of lists
s is the sorting function.
Usage:
Run an interpreter, and enter s [3,5,2,6,7].
Edit:
the way I was merging things before wasn't the right order, So to fix it I needed 9 more characters.