Evaluate the number of possible strings a regex can match

Python 3370
I got this to be about as functional as I could, and even got alternation to work (with correct double-count checking!). As far as I know this works for everything except lookarounds (because that would be crazy).
For anyone writing their own solution feel free to use/improve my methods as much as you like.
Code:
R=range;L=len;E=enumerate;I=int;F="Infinity";S=sum;H=chr;D=ord;J=lambda l:''.join(l);U=lambda s:J([H(i)if H(i) not in s else''for i in R(1,128)]);s=' \n\t';c=J((H(i)if H(i)not in s else'')for i in R(1,32));d,l,u=[J(H(i)for i in R(*n))for n in [[48,59],[97,123],[65,91]]];p='`~!@#$%^&*()-_=+[{]}\\|;:\'",<.>/?';Y={'\\s':s,'\\S':c+s+p+u+l+d,'\\d':d,'\\D':U(d),'\\w':u+l+'_','\\W':U(u+l+'_'),'[:alnum:]':u+l+d,'[:alpha:]':u+l,'[:ascii:]':U(''),'[:blank:]':' \t','[:cntrl:]':c,'[:digit:]':d,'[:graph:]':p+d+l+u,'[:lower:]':l,'[:print:]':p+d+l+u+s,'[:punct:]':p,'[:space:]':s,'[:upper:]':u,'[:word:]':l+u+'_','[:xdigit:]':d+'ABCDEF'};C=lambda l,n:[d+[l[i]]for i in R(L(l))for d in C(l[i+1:],n-1)]if n>0 else[[]];O=lambda x:S([all((c in s)for s in [(e[1]if any(e[1] not in Y for e in x)else Y[e[1]])if e[0]=='e'else(e[1]if e[0]=='t'else((Y[e[1]]if e[1]in Y else B(e[1]))if e[0]=='['else''))for e in x])for c in Y['[:ascii:]']])
def X(r):
 x=[];l=0;c=''
 for h in r:
    l+=I(h in'([')-I(h in')]')
    if l<1 and'|'==h:x+=[c];c=''
    else:c+=h
 x+=[c]
 if L(x)>1:
    o=0;m=[];u=[]
    for e in x:
     p,b=X(e)
     if p==F:return F,[]
     o+=p;m+=[('(',b)];u+=[b]
    return o-S([(-1)**(i%2)*T(s) for i in R(2,L(u)+1)for s in C(u,i)]),[('|',m)]
 u=[];o=[];m=[];w=1
 while r!='':
    h=r[0];z=0
    if h in'([{':
     l=1;i=1
     while l>0:k=r[i];l+=(k==h)-(k=={'(':')','[':']','{':'}'}[h]);i+=1
     u+=[(h,r[1:i-1])];z=i
    elif h=='\\':u+=[('e','\\'+eval("'\\%s'"%r[1]))]if r[1]in'nt'else[('e','\\'+r[1])];z=2
    elif h in ['*','+','?']:u+=[('{',h)];z=1
    elif h in'^$':return 0
    elif h=='.':u+=[('[','[:ascii:]')];z=1
    else:u+=[('t',h)];z=1
    r=r[z:]
 for t,g in u:
    if t=='(':p,b=X(g);o+=[p];m+=[('(',b)]
    elif t=='e':o+=[L(Y[g])]if g in Y else[1]
    elif t=='[':o+=[N(g)]
    elif t=='{':
     n=o[-1]
     try:o[-1]=S([n**r for r in Q(g)])
     except:return F,[]
    elif t=='t':o+=[1]
    if t!='(':m+=[(t,g)]
 for c in o:
    if c==F:return F,[]
    w*=c
 return w,m
def N(s):
 if s in Y:return L(Y[s])
 if(s[0],s[-1])==('[',']'):return 1
 n=(s[0]=='^');a=0
 if n:s=s[1:]
 while s!='':
    if L(s)>=3 and s[1]=='-':a+=D(s[2])-D(s[0])+1;s=s[3:];continue
    a+=1;s=s[1:]
 return 256*n+(-1)**n*a
def Q(s):
 if s=='?':return[0,1]
 if s[0]in'*+':return None
 if ','in s:
    l,h=s.split(',')
    return None if h==''else R(I(l),I(h)+1)
 return[I(s)]
def B(s):
 n=(s[0]=='^')
 if n:s=s[1:]
 a='';w=''
 while s!='':
    h=s[0]
    if 3<=L(s)and'-'==s[1]:
     for i in R(D(s[0]),D(s[2])+1):a+=H(i)
     s=s[3:];continue
    a+=h;s=s[1:]
 return J([c*(c not in a)for c in Y['[:ascii:]']])if n else a
def T(x):
 if all(e==[] for e in x):return 1
 for i,e in E(x):
    if L(e)>=2 and e[1][0]=='{':return S([T([[e[0]]*n+e[2:]]+x[:i]+x[i+1:])for n in Q(e[1][1])])
    if L(e)>=1:
     if e[0][0] == '(':return T([e[0][1]+e[1:]]+x[:i]+x[i+1:])
     if e[0][0]== '|':
        t=S(T([[s]+e[1:]]+x[:i]+x[i+1:])for s in e[0][1])
        u=[[s]for s in e[0][1]]
        return t-S((-1)**(j%2)*T(b)for j in R(2,L(u)+1)for b in C(u,j))
 if any(e==[]for e in x):return 0
 return O([e[0]for e in x])*T([e[1:]for e in x])
r=raw_input();e=[];l=0;c=''
for h in r:
 l+=I(h in'([')-I(h in')]')
 if l<1 and'|'==h:e+=[c];c=''
 else:c+=h
e+=[c];o=[];x=[]
for f in e:
 if '^'!=f[0]or'$'!=f[-1]:print F;quit()
 n,m=X(f[1:-1])
 if n==F:print F;quit()
 o+=[n];x+=[m]
print S(o)-S([(-1)**(i%2)*T(s) for i in R(2,L(x)+1)for s in C(x,i)])

Ungolfed:
controlchars = ''
for i in range(1,32):
    if chr(i) not in '\t\n':
        controlchars += chr(i)

CLASSES={
'\\s':' \t\n',
'\\S':controlchars+'!"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~',
'\\d':'0123456789',
'\\D':controlchars+'\n\t !"#$%&\'()*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~',
'\\w':'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_',
'\\W':controlchars+'\n\t !"#$%&\'()*+,-./:;<=>?@[\\]^`{|}~',
'[:alnum:]':'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',
'[:alpha:]':'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ',
'[:ascii:]':controlchars+'\n\t !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~',
'[:blank:]':' \t',
'[:cntrl:]':controlchars,
'[:digit:]':'0123456789',
'[:graph:]':'!"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~',
'[:lower:]':'abcdefghijklmnopqrstuvwxyz',
'[:print:]':'\n\t !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~',
'[:punct:]':'`~!@#$%^&*()-_=+[{]}\\|;:\'",<.>/?',
'[:space:]':' \t\n',
'[:upper:]':'ABCDEFGHIJKLMNOPQRSTUVWXYZ',
'[:word:]':'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_',
'[:xdigit:]':'0123456789ABCDEF'
}

DELIMIT = {
'(':')',
')':'(',
'[':']',
']':'[',
'{':'}',
'}':'{'
}

def combos(lst,num):
    if num == 0:
        return [[]]
    combs = []
    for i in range(len(lst)):
        for c in combos(lst[i+1:],num-1):
            combs.append([lst[i]]+c)
    return combs

def count_regex(regex):
    exprs = []
    level = 0
    current = ''
    for char in regex:
        if char in '([':
            level += 1
        if char in ')]':
            level -= 1
        if char == '|' and level == 0:
            exprs.append(current)
            current = ''
        else:
            current += char
    exprs.append(current)

    comps = []
    expanded = []
    for e in exprs:
        if (e[0] != '^' or e[-1] != '$'):
            return 'Infinity'
        num,member = count_expr(e[1:-1])
        if num == 'Infinity':
            return 'Infinity'
        comps.append(num)
        expanded.append(member)

    total = sum(comps)
    for i in range(2,len(expanded)+1):
        for subset in combos(expanded,i):
            if i % 2 == 0:
                total -= count_doubles(subset)
            else:
                total += count_doubles(subset)
    return total

def count_expr(expr):
    exprs = []
    level = 0
    current = ''
    for char in expr:
        if char in '([':
            level += 1
        if char in ')]':
            level -= 1
        if char == '|' and level == 0:
            exprs.append(current)
            current = ''
        else:
            current += char
    exprs.append(current)

    if len(exprs) != 1:
        comps = 0
        members = []
        sub = []
        for e in exprs:
            comp,memb = count_expr(e)
            if comp == 'Infinity':
                return 'Infinity',[]
            comps += comp
            members.append(('(',memb))
            sub.append(memb)

        for i in range(2,len(sub)+1):
            for subset in combos(sub,i):
                if i % 2 == 0:
                    comps -= count_doubles(subset)
                else:
                    comps += count_doubles(subset)

        return comps,[('|',members)]

    sub = []
    while expr != '':
        char = expr[0]
        if char in ['(','[','{']:
            level = 1
            i = 1
            while level > 0:
                nchar = expr[i]
                if nchar == char: level += 1
                if nchar == DELIMIT[char]: level -= 1
                i += 1
            sub.append((char,expr[1:i-1]))
            expr = expr[i:]
        elif char == '\\':
            if expr[1] == 'n':
                sub.append(('e','\\'+'\n'))
                expr = expr[2:]
            elif expr[1] == 't':
                sub.append(('e','\\'+'\t'))
                expr = expr[2:]
            else:
                sub.append(('e','\\'+expr[1]))
                expr = expr[2:]
        elif char in ['*','+','?']:
            sub.append(('{',char))
            expr = expr[1:]
        else:
            if char in '^$':
                return 0
            if char == '.':
                sub.append(('[','[:ascii:]'))
                expr = expr[1:]
            else:
                sub.append(('t',char))
                expr = expr[1:]

    components = []
    members = []
    for t,string in sub:
        if t == '(':
            comp,memb = count_expr(string)
            components.append(comp)
            members.append(('(',memb))
        elif t == 'e':
            if string in CLASSES:
                components.append(len(CLASSES[string]))
            else:
                components.append(1)
        elif t == '[':
            components.append(count_class(string))
        elif t == '{':
            num = components[-1]
            try:
                components[-1] = sum([num**r for r in count_quantifier(string)])
            except TypeError:
                return 'Infinity',[]
        elif t == 't':
            components.append(1)

        if t != '(':
            members.append((t,string))

    total = 1
    for c in components:
        if c == 'Infinity':
            return 'Infinity',[]
        total *= c
    return total,members

def count_class(string):
    if string in CLASSES:
        return len(CLASSES[string])
    if string[0] == '[' and string[-1] == ']':
        return 1
    negate = (string[0] == '^')
    if negate: string = string[1:]
    avail_count = 0
    while string != '':
        char = string[0]
        if len(string) >= 3:
            if string[1] == '-':
                first,last = string[0],string[2]
                avail_count += ord(last)-ord(first)+1
                string = string[3:]
                continue
        avail_count += 1
        string = string[1:]
    if negate:
        return 256-avail-count
    return avail_count

def count_quantifier(string):
    if string == '?':
        return [0,1]
    if string[0] in '*+':
        return None
    if ',' in string:
        low,high = string.split(',')
        if high == '':
            return None
        return range(int(low),int(high)+1)
    return [int(string)]

def bracket_string(string):
    negate = (string[0] == '^')
    if negate: string = string[1:]
    avail = ''
    while string != '':
        char = string[0]
        if len(string) >= 3:
            if string[1] == '-':
                first,last = string[0],string[2]
                for i in range(ord(first),ord(last)+1):
                    avail += chr(i)
                string = string[3:]
                continue
        avail += char
        string = string[1:]
    if negate:
        new = ''
        for c in CLASSES['[:ascii:]']:
            if c not in avail:
                new += c
        return new
    return avail

def overlap(es):
    chars=['' for i in range(len(es))]
    for i,e in enumerate(es):
        if e[0] == 'e':
            if any(e[1] not in CLASSES for e in es):
                chars[i] = e[1]
            else:
                chars[i] = CLASSES[e[1]]

    for i,e in enumerate(es):
        if e[0] == 't':
            chars[i] = e[1]

    for i,e in enumerate(es):
        if e[0] == '[':
            if e[1] in CLASSES:
                chars[i] = CLASSES[e[1]]
            else:
                chars[i] = bracket_string(e[1])

    total = 0
    for c in CLASSES['[:ascii:]']:
        has = True
        for chs in chars:
            if c not in chs:
                has = False
                break
        if has:
            total += 1
    return total

def count_doubles(exprs):
    if all(e==[] for e in exprs):
        return 1

    for i,expr in enumerate(exprs):
        if len(expr) >= 2 and expr[1][0] == '{':
            rng = count_quantifier(expr[1][1])
            total = 0
            for n in rng:
                total += count_doubles([ [expr[0]]*n+expr[2:] ] + exprs[:i] + exprs[i+1:])
            return total

    for i,expr in enumerate(exprs):
        if len(expr) >= 1 and expr[0][0] == '(':
            return count_doubles([ expr[0][1]+expr[1:] ] + exprs[:i] + exprs[i+1:] )

    if any(e==[] for e in exprs):
        return 0

    for i,expr in enumerate(exprs):
        if expr[0][0] == '|':
            total = 0
            subs = []
            for sub_expr in expr[0][1]:
                subs.append([sub_expr])
                total += count_doubles([ [sub_expr]+expr[1:] ] + exprs[:i] + exprs[i+1:])

            for j in range(2,len(subs)+1):
                for subset in combos(subs,j):
                    if j % 2 == 0:
                        total -= count_doubles(subset)
                    else:
                        total += count_doubles(subset)

            return total

    over = overlap([e[0] for e in exprs])
    if over == 0:
        return 0
    return  over * count_doubles([e[1:] for e in exprs])

reg = raw_input('Regex: ')
print count_regex(reg)

Here are some relevant test cases I have confirmed:
Regex: ^[A-Za-z0-9]{8}$
218340105584896

Regex: ^([a-b]*)$
Infinity

Regex: ^([0-9]|[a-e])([a-e]|[A-E])$|^[a-f]{2}$
161

Regex: ^[a-z]{2}$|^[0-9]?[a-z]{2,3}$|^a[a-z]?$
200773

Regex: ^([a-z]|[a-e]|[A-E]|[3-4]|[D-G])$
35

Regex: ^\(.)\(.)\2\1$
16129*

Regex: ^(a)\1?$
2

Regex: ^[[:space:]]$|^\t$
3

*This is actually different in the golfed and ungolfed due to a one character difference in what is defined as valid ascii. I believe the golfed is the more correct one.
To confirm its accuracy further tests could be done, please let me know of any errors (I honestly would not be surprised if there were quite a few).


Python 2, 52 bytes

x=input().split('\n')
print{len(x)}==set(map(len,x))

Try it online! or Try all test cases


Bash, 21 19 bytes
lp<<<Hello,\ World!

And there it is.
2 bytes saved thanks to Dennis!


Foo, Python, JavaScript, Retina, ><>: 166 148 bytes

1//1;print('Sheldon Lee Cooper');"""
alert`Howard Joel Wolowitz`

// Rajesh Ramayan Koothrapali
//!??

//\"Leonard Leakey">o<'Penny'" Hofstadter"""

The trailing newline is significant.

Foo outputs Leonard Leakey Hofstadter

Python outputs Sheldon Lee Cooper

JavaScript outputs Howard Joel Wolowitz

Retina outputs Rajesh Ramayan Koothrapali

><> outputs Penny Hofstadter

Explanations

Foo

In Foo, any text written inside double quotes is sent to STDOUT. So it outputs Leonard Leakey and Hofstadter. It also prints it with a leading newline. Honestly I'm really not sure about how it parses strings, but it works as-is. It also tries to do some other operations (/ is divide, parentheses form loops, etc.), but all of that just causes errors and prints to STDERR without affecting the main output in any way.

Python

1//1 is 1 integer divided by 1. In a statement by itself, that does nothing relevant. Then it prints Sheldon Lee Cooper, and the rest is in a triple quoted string, which is basically a block comment.

JavaScript

JavaScript sees most lines as either empty or commented (//). The first statement is 1 by itself which, like in the Python part, does nothing. Then it alerts Howard Joel Wolowitz.

Retina

1//1;print('Sheldon Lee Cooper');"""
alert`Howard Joel Wolowitz`

First all matches of 1//1;print('Sheldon Lee Cooper');""" in the input are replaced with alert`Howard Joel Wolowitz`. Seeing as the input is empty, nothing happens.

// Rajesh Ramayan Koothrapali

Then the empty input is replaced with // Rajesh Ramayan Koothrapali.

//!??

Then all matches of // optionally followed by a ! are replaced with nothing. This deletes the initial //, leaving one leading space (which is allowed).

//\"Leonard Leakey">o<'Penny'" Hofstadter"""

Then all matches of the regex above are replaced with nothing. This regex doesn't match anything in the working string, so nothing happens.

The working string is then output implicitly.

><>

The IP starts in the top-left, initially moving right. It first pushes 1, then bounces around on mirrors (/ and \) for a while (looping around when it goes out of bounds). The 1 will be popped when it hits ?.

Eventually it will be on the right side of the second last line moving left. On this line, it sees an empty string "", pushing nothing. Then it encounters two strings, " Hofstadter" and 'Penny', pushing the characters from each as it sees them. When it hits >o<, it repeatedly pops and prints the top of the stack as a character, until there's nothing left to pop. It exits with an error.


HTML + JS, 913 857 675 bytes

(Line breaks are added for readability)

<body><script>
function O(X,x,y,R){X.beginPath();X.arc(x,y,R,0,M.PI*2,true);X.closePath();X.fill()}
Z=300,P=3,H=Z/2,$=+prompt(),M=Math;for(S=3;S<$;S++){for(C=1;C<30;C++){if(S*C*C+S*C+2==$*2){
V=document.createElement("canvas");V.width=V.height=Z;document.querySelector("body").appendChild(V);X=V.getContext("2d");
O(X,H,H,P);for(R=1;R<=C;R++){
D=[],A=R*(H-P)/C,G=0;X.beginPath();X.moveTo(H+A,H);D.push([H+A,H]);for(s=1;s<S;s++){x=M.cos(G+=M.PI*2/S)*A,y=M.sin(G)*A;X.lineTo(H+x,H+y);D.push([H+x,H+y])}X.closePath();X.stroke();
for(j=0;j<D.length;j++){x=D[j][0],y=D[j][1],q=D[(j+1)%S][0]-x,w=D[(j+1)%S][1]-y;O(X,x,y,P);for(k=0;k<R-1;k++)O(X,x+=q/R,y+=w/R,P)}
}break}}}
</script></body>

This is working jsfiddle example, and ungolfed source. It gets input from prompt(). You can adjust output size by adjusting sz = 300, and dot size by pt = 3 (in pixels).

Example (31 dots)


HTML 21 7 chars (1 char if I'm cheeky...)

&#8238;n

replace n with your number


4

This is cheeky and a cheat. I wrote this script about a year ago based off of this comic (tad of profanity).

The idea goes like this. Given any number as a string, adding the number of characters will eventually condense to 4. Four itself is 4 letters long and thus the end of the line.

For example:

10 -> 'ten'
'ten' -> 3 (letters long)
3 -> 'three'
'three' -> 5 (letters long)
5 -> 'five'
'five' -> 4 (letters long)

I verified up to 100,000. Very hacky but got the job done:

to20 = [
        'zero'
        ,'one'
        ,'two'
        ,'three'
        ,'four'
        ,'five'
        ,'six'
        ,'seven'
        ,'eight'
        ,'nine'
        ,'ten'
        ,'eleven'
        ,'twelve'
        ,'thirteen'
        ,'fourteen'
        ,'fifteen'
        ,'sixteen'
        ,'seventeen'
        ,'eighteen'
        ,'nineteen'
        ]

by10s = ['twenty'
         ,'thirty'
         ,'forty'
         ,'fifty'
         ,'sixty'
         ,'seventy'
         ,'eighty'
         ,'ninety'
         ]

by10powers = [
             'hundred'
             ,'thousand'
             ]

def cosmetize(number):

    # the number is too damn high!
    if number >= 100000:
        return "Too high"

    numstr = str(number)

    # Do ones
    if number < 10:
        return to20[number]

    # Pshh.. who needs zero anymore?
    to20[0] = ''

    # Do tens
    numstr10 = numstr[-2:]
    if int(numstr10) < 20:
        numstr10 = to20[int(numstr10)]
    else:
        numstr10 = by10s[int(numstr10[0])-2] + to20[int(numstr10[1])]
    if number < 100:
        return numstr10

    # Do hundreds
    numstr100 = numstr[-3]
    if numstr10 == '':
        numstr10 = ""
        numstr100 = to20[int(numstr100)] + by10powers[0]
    elif int(numstr[-2:]) > 19:
        numstr100 = to20[int(numstr100)] + by10powers[0]
        numstr100 += 'and'
    else:
        numstr100 = 'and'
    if number < 1000:
        return numstr100 + numstr10

    # Do thousands
    numstr1000 = numstr[:-3]
    if numstr100 == 'hundred':
        numstr100 = ""
    if int(numstr1000) < 20:
        numstr1000 = to20[int(numstr1000)] + by10powers[1]
    else:
        numstr1000 = by10s[int(numstr1000[0])-2] + by10powers[1]

    return numstr1000 + numstr100 + numstr10

i = 0
mx = []
z = 0
while i < 100000:
    length = cosmetize(i)
    x = [length]
    while not len(length) == 4:
        length = cosmetize(len(length))
    i += 1

# No inifinite loop? what magic is this?
print "OMG"


Perl 5, 62 61 bytes
@randomdude999 pointed out a space I could remove to save a byte.

sub f{(map{map$$_[rand@$_],@_}1..pop),"(Now read bottom up)"}

Try it online!
A function which takes in the sets of statements as a reference to an array for each type of statement and the number of stanzas.  Returns an array of strings, one element for each line of the poem.


05AB1E, 11 bytes

F²γN>×J}».C

Uses the 05AB1E encoding. Try it online!


Programming Praxis - Survive like Flavius Josephus

Python 2 (85 Bytes):

Thanks to bitpwner we have this solution:

def j(m,n):
    a,b,c=range(m),0,[]
    while a:b=(b+n-1)%len(a);c+=[a.pop(b)]
    return c

To use this in Python 3 you have to cast a to a list, this comes with the cost of another 6 bytes.

Python 3 (114 bytes):

This was my first thought, but I think this is a good but no perfect solution:

def j(m,n):
    a,b=__import__("collections").deque(range(m)),[]
    while a:a.rotate(-n);b.append(a.pop())
    return b

I was not happy with the use of the deque, but I couldn't think of any other solution. At least I could save 5 bytes with __import__.

This function works as described above, a are the people and b is the execution order. As long as there are still people left (while a:), it rotates the deque/the people by n and appends the current man (a.pop()) to the execution list.


Translate Morse code based on tone duration

APL (Dyalog), 65 62 60 57 bytes

-3 thanks to ngn.

Tacit prefix function.

⎕CY'dfns'
morse'/|[-.]+'⎕S'&'∘(⊃∘'/. -'¨6|'1+|(00)+'⎕S 1)

Try it online! Header, f←, and Footer are just to allow calling the function from Input while retaining TIO's byte count. In a normal APL session (corresponding to TIO's Input field), it would not be needed.

⎕CY'dfns' copy the dfns workspace (library)

(…) apply this tacit function:
 '1+|(00)+'⎕S 1 PCRE Search 1-runs and even-length 0-runs and return matches' lengths
 6| division remainder when divided by 6
 ⊃∘'/. -'¨ for each match length, pick the corresponding character from this string
'/|[-.]+'⎕S'&'∘ PCRE Search slashes and dash/dot-runs and return those
morse translate from Morse code to regular text


Multi-level marketing "legs" investment rule

Jelly,  12  9 bytes

ṢṚ×J$ṫ⁵<Ṃ

A full program which accepts x T M and prints 0 if the peer is rewarded and 1 if not.

Try it online!

How?

ṢṚ×J$ṫ⁵<Ṃ - Main Link: list of numbers, x; number, T   e.g. [100, 50, 77, 22, 14, 45], 180
Ṣ         - sort x                                          [ 14, 22, 45, 50, 77,100]
 Ṛ        - reverse                                         [100, 77, 50, 45, 22, 14]
    $     - last two links as a monad:
   J      -   range of length                               [  1,  2,  3,  4,  5,  6]
  ×       -   multiply                                      [100,154,150,180,110, 84]
     ṫ    - tail from index:
      ⁵   -   5th argument (3rd input), M   (e.g. M=3)      [        150,180,110, 84]
       <  - less than T?                                    [          1,  0,  1,  1]
        Ṃ - minimum                                         0


Optimal Minesweeper on the Largest Board

Python, 4x5 board, 5 mines.

This is the reference implementation, I just thought I'd put it here to help give people ideas.

This implementation uses dynamic programming to prevent duplication of work, exploits mirror symmetries, and maintains a fist of all possible boards with a given revealed square status to check for guaranteed safe squares.

# Minesweeper solver
# Class just contains partially revealed boards that all look the same
# from the outside

# This is a branch, that uses strings.

# Boards have every cell revealed.
# Revealed is partially revealed. Boards must match revealed on every
# cell that is revealed.

# Meanings:
# '0'-'8': Safe square with that # of surrounding mines
# '*'    : Mine
# '_'    : Unrevealed
import copy
import itertools
import time
import pickle
import random
import math
import cProfile
import sys

class Position:
    def __init__(self, dimensions, revealed, boards):
        self.dim_r,self.dim_c=dimensions
        self.rev=revealed
        self.boards=boards
        assert len(revealed)==self.dim_r*self.dim_c

    def click(self,loc):
        # Takes a location, returns all possible revealed positions, with boards
        # split up accordingly
        try:
            assert self.rev[loc]=='_'
        except AssertionError:
            print(self,loc,self.rev)
            assert self.rev[loc]=='_'
        # Create all possible new boards, split up by revealed item.
        board_dict={}
        for board in self.boards:
            clicked_cell=board[loc]
            if clicked_cell in board_dict:
                board_dict[clicked_cell].append(board)
            else:
                board_dict[clicked_cell]=[board]
        new_positions=[]
        for rev_cell in board_dict.keys():
            # Make the new board without copying
            new_rev=''.join([self.rev[:loc],rev_cell,self.rev[loc+1:]])
                new_pos=Position((self.dim_r,self.dim_c),new_rev,board_dict[rev_cell])
            new_positions.append(new_pos)
        return new_positions

    def someBestClick(self):
        click_list=[]
        # Set of boards is all we know when outputting, may be smaller than
        # complete set
        # If we've clicked on a bomb, no way to win, no best click.
        if '*' in self.rev:
            return 0,[]
        unrevealed = [loc for loc in range(len(self.rev)) if self.rev[loc]=='_']
        # If there is only 1 possible board, you're done. The click list is every
        # unrevealed square on the board without a bomb under it.
        if len(self.boards)==1:
            return 1,[loc for loc in unrevealed if self.boards[0][loc]!='*']

        # If there is an unrevaled locaiton on the board that is bomb free in
        # every sub-board, use it.
        for loc in unrevealed:
            if all(board[loc]!='*' for board in self.boards):
                return sum(pos.memoBestClick()[0] for pos in self.click(loc)),[loc]

        # The broadest test - try everywhere.
        click_list=[]
        most_wins=0
        for loc in unrevealed:
            wins=sum(pos.memoBestClick()[0] for pos in self.click(loc) if pos.rev[loc]!='*')
            if wins>=most_wins:
                if wins>most_wins:
                    click_list=[]
                    most_wins=wins
                click_list.append(loc)
        return most_wins,click_list

    def memoBestClick(self):
        global memo
        global memo_counter
        memo_counter +=1
        if not self.rev in memo:
            # These lines check for mirror images of the board being in the memo table

            vert_reversed_memo_str=                                         \
            ''.join([self.rev[y*self.dim_c:(y+1)*self.dim_c]
                     for y in range(self.dim_r)][::-1])

            if vert_reversed_memo_str in memo:
                vert_reversed_output=memo[vert_reversed_memo_str]
                return vert_reversed_output[0],                             \
                        [(self.dim_r-1-loc//self.dim_c)*self.dim_c+loc%self.dim_c
                         for loc in vert_reversed_output[1]]

            horiz_reversed_memo_str=                                        \
            ''.join(self.rev[y*self.dim_c:(y+1)*self.dim_c][::-1]
                    for y in range(self.dim_r))

            if horiz_reversed_memo_str in memo:
                horiz_reversed_output=memo[horiz_reversed_memo_str]
                return horiz_reversed_output[0],                            \
                        [(loc//self.dim_c)*self.dim_c+
            both_reversed_memo_str=self.rev[::-1]
            if both_reversed_memo_str in memo:
                both_reversed_output=memo[both_reversed_memo_str]
                return both_reversed_output[0],                             \
                        [len(self.rev)-1-loc
                         for loc in both_reversed_output[1]]

            global restart_counter
            global restart_memo

            if len(self.rev)-self.rev.count('_') <= restart_max:
                restart_memo[self.rev]=self.someBestClick()
                memo[self.rev]=restart_memo[self.rev]
                return restart_memo[self.rev]
            # Needed because of memory issues
            if len(memo)>5*10**6:
                memo=copy.deepcopy(restart_memo)
                restart_counter+=1
            memo[self.rev]=self.someBestClick()
        return memo[self.rev]

def makeBlankPosition(dimensions,mines):
    dim_r,dim_c=dimensions
    # Makes all locations on the board
    all_loc=itertools.product(range(dim_c),range(dim_r))
    # Makes all possible distributions of mines
    all_mine_layouts=itertools.combinations(all_loc,mines)
    boards=[]
    for mine_layout in all_mine_layouts:
        boards.append(makeBoardFromMines(dimensions,mine_layout))
    return Position(dimensions, '_'*dim_c*dim_r, boards)

def makeBoardFromMines(dimensions,mine_layout):
    dim_r,dim_c=dimensions
    def mineNum(loc):
        if (loc%dim_c,loc//dim_c) in mine_layout:
            return '*'
        return str(sum(((loc%dim_c+dif[0],loc//dim_c+dif[1]) in mine_layout) for dif in
                   [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]))
    return ''.join(map(mineNum,(loc for loc in range(dim_r*dim_c))))

def makePosition(dimensions,mines,revealed):
    blank_pos=makeBlankPosition(dimensions,mines)
    boards_subset=[]
    for board in blank_pos.boards:
        if all(revealed[cell_num]==board[cell_num] or revealed[cell_num]=='_' for cell_num in range(len(board))):
            boards_subset.append(board)
    return Position(dimensions, revealed, boards_subset)

def winRate(dimensions,mines,revealed):
    pos=makePosition(dimensions,mines,revealed)
    global memo
    memo={}
    wins=pos.memoBestClick()
    return wins[0],len(pos.boards),wins[1],memo

global memo_counter
memo_counter=0
global restart_counter
restart_counter=0
global restart_memo
restart_memo={}
global restart_max
restart_max=6
dimensions, mines, revealed = eval(input())
start_time=time.clock()
wins, total_boards, moves, memo = winRate(dimensions, mines, revealed)
move_points=[(move//dimensions[1],move%dimensions[1]) for move in moves]
print("""Best moves are %s.\n%i wins out of %i boards. Ratio of %f. %i
positions searched.\n%f seconds taken."""%(move_points, wins, total_boards,
wins/total_boards, len(memo),time.clock()-start_time))


Jelly,  17 11  10 bytes

-1 Thanks to Dennis (use count to remove the need to tie atoms together with any quick)

Œ!ŒṖ€§Ẏċ€Ṁ

A dyadic link accepting a list and an integer which yields the maximal count, \$k\$.

Try it online! Or see the test-suite -- it's too slow for the larger test cases :(

How?

Œ!ŒṖ€§Ẏċ€Ṁ - Link: list L, integer I
Œ!         - all permutations
  ŒṖ€      - for €ach: all partitions (all ways to slice up each permutation)
     §     - sum each (vectorises at depth 1, so this gets the sums of the parts of
           -           each of the partitions for each permutation)
      Ẏ    - tighten  (to get a list of the sums of the parts of each possible partition)
       ċ€  - for €ach count occurrences of I
         Ṁ - maximum


Avoid horizontal gaps
Often, code will leave largs gaps of whitespace to the left hand side of the program, like so.
abc
  d
  e

This adds 4 bytes, when this could be avoided by left aligning.
cde
b
a

If you need to use large gaps of whitespace, try to make them vertical, instead of horizontal.
########
#      #
#      #
#      #

vs
####
#
#
#
#
#
#
####


Game Maker Language (GM 8.0), 10262 10228 10152 10115 8746 1 + 8699 = 8700 bytes

We define a script named X (1 byte). Each question is labelled with an integer. X takes such an integer, prompts the user with the corresponding question, and either returns the appropriate message or calls the next question. At each question, the user is prompted for an integer corresponding to the possible options. If the user does not match any of the options, then the prompt is exited.

A=argument1 Y="##YES (1), NO (2)"I="IS THERE A BIG LAKE IN THE MIDDLE OF "H="HOW MANY "switch argument0{case H:return show_message(A)break
case I:return get_integer(A,1)break
case 1:switch X(I,"ISTANBUL OR CONSTANTINOPLE##CONSTANTINOPLE (1), NEITHER (2), ISTANBUL(3)"){case 1:X(2)break case 2:X(19)break case 3:X(74)}break
case 2:switch X(I,"DO ANY OF THESE EXIST?#- INDEPENDENT CANADA#- US TERRITORY OF ALASKA#- TOKYO"+Y){case 2:X(3)break case 1:X(11)}break
case 3:switch X(I,"THE HOLY ROMAN EMPIRE?"+Y){case 1:X(H,"1805 OR EARLIER (BEFORE THIS POINT, THE MODERN IDEA OF A COMPLETE POLITICAL MAP OF THE WORLD GETS HARD TO APPLY.)")break case 2:X(4)}break
case 4:switch X(I,"THE UNITED STATES?"+Y){case 2:X(H,"HOW SURE ARE YOU THAT THIS MAP IS IN ENGLISH")break case 1:X(5)}break
case 5:switch X(I,"TEXAS IS...##PART OF MEXICO (1), INDEPENDENT (2), PART OF THE US (3)"){case 1:X(6)break case 2:X(H,"1834-45")break case 3:X(9)}break
case 6:switch X(I,"FLORIDA IS PART OF...##SPAIN (1), THE US (2)"){case 1:X(7)break case 2:X(8)}break
case 7:switch X(I,"PARAGUAY?"+Y){case 2:X(H,"1806H0")break case 1:X(H,"1811H7")}break
case 8:switch X(I,"VENEZUELA AND/OR ECUADOR?"+Y){case 2:X(H,"1818-29")break case 1:X(H,"1830-33")}break
case 9:switch X(I,"DOES RUSSIA BORDER THE SEA OF JAPAN?"+Y){case 2:X(10)break case 1:X(H,"1858-67")}break
case 10:switch X(I,"THE US'S SOUTHERN BORDER LOOKS...##WEIRD (1), NORMAL (2)"){case 1:X(H,"1846-53")break case 2:X(H,"1854-56")}break
case 11:switch X(I,"SOUTH AFRICA?"+Y){case 2:X(12)break case 1:X(16)}break
case 12:switch X(I,"RHODESIA?"+Y){case 2:X(13)break case 1:X(15)}break
case 13:switch X(I,"IS BOLIVIA LANDLOCKED?"+Y){case 2:X(14)break case 1:X(H,"1884-95")}break
case 14:switch X(I,'"BUDA" AND "PEST" OR "BUDAPEST"?##BUDA AND PEST (1), BUDAPEST (2)'){case 1:X(H,"1868-72")break case 2:X(H,"1873-83")}break
case 15:switch X(I,"IS NORWAY PART OF SWEDEN?"+Y){case 1:X(H,"1896H905")break case 2:X(H,"1906-09")}break
case 16:switch X(I,"AUSTRIA-HUNGARY?"+Y){case 1:X(17)break case 2:X(18)}break
case 17:switch X(I,"ALBANIA?"+Y){case 2:X(H,"1910H2")break case 1:X(H,"1913H8")}break
case 18:switch X(I,"LENINGRAD?"+Y){case 2:X(H,"1919-23")break case 1:X(H,"1924-29")}break
case 19:switch X(I,"DOES THE OTTOMAN EMPIRE EXIST?"+Y){case 1:X(2)break case 2:X(20)}break
case 20:switch X(I,"THE SOVIET UNION?"+Y){case 2:X(21)break case 1:X(63)}break
case 21:switch X(I,"NORTH KOREA?"+Y){case 2:X(22)break case 1:X(56)}break
case 22:switch X(I,"SAINT TRIMBLE'S ISLAND?"+Y){case 2:X(23)break case 1:X(H,"NO, I MADE THAT ONE UP.")}break
case 23:switch X(I,"IS JAN MAYEN PART OF THE KINGDOM OF NORWAY?##NOT YET (1), WHAT? (2), YES (3)"){case 1:X(2)break case 2:X(24)break case 3:X(49)}break
case 24:switch X(I,"CAN YOU SEE THE FAMILIAR CONTINENTS?"+Y){case 1:X(25)break case 2:X(31)}break
case 25:switch X(I,"THIS SOUNDS LIKE A PHYSICAL MAP OR SATELLITE PHOTO.##YES, THAT'S IT (1)"){case 1:X(26)}break
case 26:switch X(I,"IS LAKE CHAD MISSING?"+Y){case 2:X(27)break case 1:X(30)}break
case 27:switch X(I,"HOW FAR EAST DO THE AMERICAN PRAIRIES REACH?##INDIANA (1), THE MISSISSIPPI (2), NEBRASKA (3), WHAT PRAIRIES? (4)"){case 1:X(H,"BEFORE 1830")break case 2:X(H,"1830s-80s")break case 3:X(28)break case 4:X(29)}break
case 28:switch X(I,I+"SOUTHERN CALIFORNIA? (CREATED BY MISTAKE)"+Y){case 2:X(H,"1860sH900s")break case 1:X(H,"1910s")}break
case 29:switch X(I,I+"GHANA? (CREATED ON PURPOSE)"+Y){case 2:X(H,"1920s-50s")break case 1:X(H,"1960s-70s")}break
case 30:switch X(I,"IS THE ARAL SEA MISSING?"+Y){case 2:X(H,"1970s-90s")break case 1:X(H,"2000s+")}break
case 31:switch X(I,'RIVERS "SIRION" OR "ANDUIN"?'+Y){case 1:X(32)break case 2:X(36)}break
case 32:switch X(I,"MORDOR?"+Y){case 2:X(33)break case 1:X(34)}break
case 33:switch X(I,"BELERIAND?"+Y){case 1:X(H,"FIRST AGE")break case 2:X(H,"EARLY SECOND AGE")}break
case 34:switch X(I,"NÚMENOR?"+Y){case 1:X(H,"LATE SECOND AGE")break case 2:X(35)}break
case 35:switch X(I,"THE FOREST EAST OF THE MISTY MOUNTAINS IS...##GREENWOOD THE GREAT (1), MIRKWOOD (2), THE WOOD OF GREENLEAVES (3)"){case 1:X(H,"EARLY THIRD AGE")break case 2:X(H,"LATE THIRD AGE")break case 3:X(H,"FOURTH AGE")}break
case 36:switch X(I,"CAIR PARAVEL?"+Y){case 1:X(37)break case 2:X(41)}break
case 37:switch X(I,"CALORMEN?"+Y){case 2:X(38)break case 1:X(40)}break
case 38:switch X(I,"LOTTA ISLANDS?"+Y){case 2:X(39)break case 1:X(H,"DAWN TREADER")}break
case 39:switch X(I,"BERUNA##FORD (1), BRIDGE (2)"){case 1:X(H,"THE LION, THE WITCH, AND THE WARDROBE")break case 2:X(H,"PRINCE CASPIAN")}break
case 40:switch X(I,"WEIRD RECURSIVE HEAVEN?"+Y){case 2:X(H,"ONE OF THE RANDOM LATER BOOKS")break case 1:X(H,"THE LAST BATTLE")}break
case 41:switch X(I,"MOSSFLOWER?"+Y){case 1:X(H,"REDWALL")break case 2:X(42)}break
case 42:switch X(I,"IS THE WORLD ON THE BACK OF A TURTLE?"+Y){case 1:X(H,"DISCWORLD")break case 2:X(43)}break
case 43:switch X(I,"ARE YOU SURE THIS IS A MAP?"+Y){case 1:X(44)break case 2:X(46)}break
case 44:switch X(I,"DID YOU MAKE IT YOURSELF?##YES (1)"){case 1:X(45)}break
case 45:X(I,"IT'S VERY NICE.##THANK YOU! (1)")break
case 46:switch X(I,"IS IT TRYING TO BITE YOU?"+Y){case 2:X(47)break case 1:X(48)}break
case 47:switch X(I,"IS IT LARGER THAN A BREADBOX?"+Y+", ABOUT THE SAME (3)"){case 1:X(H,"TUBA")break case 2:X(H,"STAPLER")break case 3:X(H,"BREADBOX")}break
case 48:switch X(I,"IF YOU LET IT GO, WHAT DOES IT DO?##HISSES AND RUNS AWAY (1), SCREECHES AND FLAPS AROUND THE ROOM BREAKING THINGS (2)"){case 1:X(H,"CAT")break case 2:X(H,"SEAGULL")}break
case 49:switch X(I,"PAKISTAN?"+Y){case 2:X(50)break case 1:X(52)}break
case 50:switch X(I,H+"GERMANYS ARE THERE?##ONE (1), ONE, BUT IT'S HUGE (2), TWO (3)"){case 1:X(51)break case 2:X(H,"1941-45")break case 3:X(H,"1946-47")}break
case 51:switch X(I,"PERSIA OR IRAN?##PERSIA (1), IRAN (2)"){case 1:X(H,"1930-34")break case 2:X(H,"1935-40")}break
case 52:switch X(I,"CAMBODIA?"+Y){case 2:X(53)break case 1:X(55)}break
case 53:switch X(I,"ERITREA IS A PART OF...##ITALY (1), ETHIOPIA (2)"){case 1:X(54)break case 2:X(H,"1952-53")}break
case 54:switch X(I,"CANADA IS...##MISSING A PIECE (1), FINE (2)"){case 1:X(H,"1948")break case 2:X(H,"1949-52")}break
case 55:switch X(I,"THE UNITED ARAB REPUBLIC?"+Y){case 2:X(H,"1954-57")break case 1:X(H,"1958-60")}break
case 56:switch X(I,'ZAIRE? OR: "HONG KONG (UK)"'+Y){case 1:X(H,"1992-96")break case 2:X(57)}break
case 57:switch X(I,"SERBIA AND MONTENEGRO ARE...##ONE COUNTRY (1), TWO COUNTRIES (2)"){case 1:X(58)break case 2:X(59)}break
case 58:switch X(I,"EAST TIMOR?"+Y){case 2:X(H,"1997-2001")break case 1:X(H,"2002-06")}break
case 59:switch X(I,H+"SUDANS ARE THERE?##ONE (1), TWO (2)"){case 1:X(H,"2007H1")break case 2:X(60)}break
case 60:switch X(I,"IS CRIMEA DISPUTED?"+Y){case 1:X(61)break case 2:X(H,"2012H3")}break
case 61:switch X(I,'"COLORADO" OR "DANGER-RADIOACTIVE EXCLUSION ZONE-AVOID"?##COLORADO (1), DANGER (2)'){case 1:X(H,"2014-21")break case 2:X(62)}break
case 62:switch X(I,"DOES THE WARNING MENTION THE SPIDERS?"+Y){case 2:X(H,"2022")break case 1:X(H,"2023 OR LATER")}break
case 63:switch X(I,"SAUDI ARABIA?"+Y){case 2:X(H,"1922-32")break case 1:X(64)}break
case 64:switch X(I,"IS MOST OF WEST AFRICA A GIANT FRENCH BLOB?"+Y){case 1:X(49)break case 2:X(65)}break
case 65:switch X(I,H+"VIETNAMS ARE THERE?##TWO (1), ONE (2)"){case 1:X(66)break case 2:X(69)}break
case 66:switch X(I,"BANGLADESH?"+Y){case 2:X(67)break case 1:X(H,"1972-75")}break
case 67:switch X(I,"IS THE AREA SOUTH OF LAKE VICTORIA...##BRITISH (1), TANGANYIKA (2), TANZANIA (3)"){case 1:X(68)break case 2:X(H,"1961-64")break case 3:X(H,"1965-71")}break
case 68:switch X(I,"THE TOWN ON I-25 BETWEEN ALBUQUERQUE AND EL PASO IS...##HOT SPRINGS (1), TRUTH OR CONSEQUENCES (2)"){case 1:X(H,"1948-49")break case 2:X(H,"1950-52")}break
case 69:switch X(I,"JIMMY CARTER IS...##BEING ATTACKED BY A GIANT SWIMMING RABBIT (1), FINE (2)"){case 1:X(H,"APRIL 20, 1979")break case 2:X(70)}break
case 70:switch X(I,"THE SINAI IS PART OF WHAT COUNTRY?## ISRAEL (1), MOSTLY ISRAEL (2), MOSTLY EGYPT (3), EGYPT (4)"){case 1:X(H,"1976-79")break case 2:X(H,"1980")break case 3:X(H,"1981")break case 4:X(71)}break
case 71:switch X(I,"WHAT'S THE CAPITAL OF MICRONESIA?## KOLONIA (1), PALIKIR (2)"){case 1:X(72)break case 2:X(73)}break
case 72:switch X(I,"REPUBLIC OF THE UPPER VOLTA OR BURKINA FASO?## UPPER VOLTA (1), BURKINA FASO (2)"){case 1:X(H,"1982-84")break case 2:X(H,"1985-88")}break
case 73:switch X(I,"(NUMBER OF YEMENS)+(NUMBER OF GERMANYS)=?## FOUR (1), THREE (2), TWO (3)"){case 1:X(H,"1989-EARLY 1990")break case 2:X(H,"MIDH990")break case 3:X(H,"LATE 1990H991")}break
case 74:switch X(I,"DOES THE SOVIET UNION EXIST?"+Y){case 1:X(64)break case 2:X(56)}break}

# is the newline character.

How to run

New .gmk file
Create a script X with contents as above
Create an object O with Create Event: execute code: X(1)
Create a room R and put one instance of O in it
Run the game

Golfing

The option YES now always precedes NO, and we define the string Y="##YES (1), NO (2)" for reuse.
"IS THERE A BIG LAKE IN THE MIDDLE OF " and "HOW MANY " are long enough and occur sufficiently many times for abbreviation to pay off. They are assigned to I and H.
In Game Maker, any user-defined function usually must be done in a separate script. The consensus on the policy for counting bytes for multi-file programs, was that "If files are reused ... count the contents of that file as many times as you use it". As such, we use X itself, rather than a separate script, to abbreviate get_integer and show_message. Explicitly,

If X is called with zeroth argument H, then it returns show_message of the first argument.
If X is called with zeroth argument I, then it returns get_integer of the first argument, showing default input 1.

Ungolfed, with options in the original order and no abbreviations at all:

// script X, takes node number, prompts question and returns message or calls X with next node number

switch argument0
{
case 1: switch get_integer("ISTANBUL OR CONSTANTINOPLE##CONSTANTINOPLE (1), NEITHER (2), ISTANBUL(3)",1)
  {
    case 1: X(2); break;
    case 2: X(19); break;
    case 3: X(74); break;
  }; break;
case 2: switch get_integer("DO ANY OF THESE EXIST?#- INDEPENDENT CANADA#- US TERRITORY OF ALASKA#- TOKYO##NO (1), YES (2)",1)
  {
    case 1: X(3); break;
    case 2: X(11); break;
  }; break;
case 3: switch get_integer("THE HOLY ROMAN EMPIRE?##YES (1), NO (2)",1)
  {
    case 1: show_message("1805 OR EARLIER (BEFORE THIS POINT, THE MODERN IDEA OF A COMPLETE POLITICAL MAP OF THE WORLD GETS HARD TO APPLY.)"); break;
    case 2: X(4); break;
  }; break;
case 4: switch get_integer("THE UNITED STATES?##NO (1), YES (2)",1)
  {
    case 1: show_message("HOW SURE ARE YOU THAT THIS MAP IS IN ENGLISH"); break;
    case 2: X(5); break;
  }; break;
case 5: switch get_integer("TEXAS IS...##PART OF MEXICO (1), INDEPENDENT (2), PART OF THE US (3)",1)
  {
    case 1: X(6); break;
    case 2: show_message("1834-45"); break;
    case 3: X(9); break;
  }; break;
case 6: switch get_integer("FLORIDA IS PART OF...##SPAIN (1), THE US (2)",1)
  {
    case 1: X(7); break;
    case 2: X(8); break;
  }; break;
case 7: switch get_integer("PARAGUAY?##NO (1), YES (2)",1)
  {
    case 1: show_message("1806-10"); break;
    case 2: show_message("1811-17"); break;
  }; break;
case 8: switch get_integer("VENEZUELA AND/OR ECUADOR?##NO (1), YES (2)",1)
  {
    case 1: show_message("1818-29"); break;
    case 2: show_message("1830-33"); break;
  }; break;
case 9: switch get_integer("DOES RUSSIA BORDER THE SEA OF JAPAN?##NO (1), YES (2)",1)
  {
    case 1: X(10); break;
    case 2: show_message("1858-67"); break;
  }; break;
case 10: switch get_integer("THE US'S SOUTHERN BORDER LOOKS...##WEIRD (1), NORMAL (2)",1)
  {
    case 1: show_message("1846-53"); break;
    case 2: show_message("1854-56"); break;
  }; break;
case 11: switch get_integer("SOUTH AFRICA?##NO (1), YES (2)",1)
  {
    case 1: X(12); break;
    case 2: X(16); break;
  }; break;
case 12: switch get_integer("RHODESIA?##NO (1), YES (2)",1)
  {
    case 1: X(13); break;
    case 2: X(15); break;
  }; break;
case 13: switch get_integer("IS BOLIVIA LANDLOCKED?##NO (1), YES (2)",1)
  {
    case 1: X(14); break;
    case 2: show_message("1884-95"); break;
  }; break;
case 14: switch get_integer('"BUDA" AND "PEST" OR "BUDAPEST"?##BUDA AND PEST (1), BUDAPEST (2)',1)
  {
    case 1: show_message("1868-72"); break;
    case 2: show_message("1873-83"); break;
  }; break;
case 15: switch get_integer("IS NORWAY PART OF SWEDEN?##YES (1), NO (2)",1)
  {
    case 1: show_message("1896-1905"); break;
    case 2: show_message("1906-09"); break;
  }; break;
case 16: switch get_integer("AUSTRIA-HUNGARY?##YES (1), NO (2)",1)
  {
    case 1: X(17); break;
    case 2: X(18); break;
  }; break;
case 17: switch get_integer("ALBANIA?##NO (1), YES (2)",1)
  {
    case 1: show_message("1910-12"); break;
    case 2: show_message("1913-18"); break;
  }; break;
case 18: switch get_integer("LENINGRAD?##NO (1), YES (2)",1)
  {
    case 1: show_message("1919-23"); break;
    case 2: show_message("1924-29"); break;
  }; break;
case 19: switch get_integer("DOES THE OTTOMAN EMPIRE EXIST?##YES (1), NO (2)",1)
  {
    case 1: X(2); break;
    case 2: X(20); break;
  }; break;
case 20: switch get_integer("THE SOVIET UNION?##NO (1), YES (2)",1)
  {
    case 1: X(21); break;
    case 2: X(63); break;
  }; break;
case 21: switch get_integer("NORTH KOREA?##NO (1), YES (2)",1)
  {
    case 1: X(22); break;
    case 2: X(56); break;
  }; break;
case 22: switch get_integer("SAINT TRIMBLE'S ISLAND?##NO (1), YES (2)",1)
  {
    case 1: X(23); break;
    case 2: show_message("NO, I MADE THAT ONE UP."); break;
  }; break;
case 23: switch get_integer("IS JAN MAYEN PART OF THE KINGDOM OF NORWAY?##NOT YET (1), WHAT? (2), YES (3)",1)
  {
    case 1: X(2); break;
    case 2: X(24); break;
    case 3: X(49); break;
  }; break;
case 24: switch get_integer("CAN YOU SEE THE FAMILIAR CONTINENTS?##YES (1), NO (2)",1)
  {
    case 1: X(25); break;
    case 2: X(31); break;
  }; break;
case 25: switch get_integer("THIS SOUNDS LIKE A PHYSICAL MAP OR SATELLITE PHOTO.##YES, THAT'S IT (1)",1)
  {
    case 1: X(26); break;
  }; break;
case 26: switch get_integer("IS LAKE CHAD MISSING?##NO (1), YES (2)",1)
  {
    case 1: X(27); break;
    case 2: X(30); break;
  }; break;
case 27: switch get_integer("HOW FAR EAST DO THE AMERICAN PRAIRIES REACH?##INDIANA (1), THE MISSISSIPPI (2), NEBRASKA (3), WHAT PRAIRIES? (4)",1)
  {
    case 1: show_message("BEFORE 1830"); break;
    case 2: show_message("1830s-80s"); break;
    case 3: X(28); break;
    case 4: X(29); break;
  }; break;
case 28: switch get_integer("IS THERE A BIG LAKE IN THE MIDDLE OF SOUTHERN CALIFORNIA? (CREATED BY MISTAKE)##NO (1), YES (2)",1)
  {
    case 1: show_message("1860s-1900s"); break;
    case 2: show_message("1910s"); break;
  }; break;
case 29: switch get_integer("IS THERE A BIG LAKE IN THE MIDDLE OF GHANA? (CREATED ON PURPOSE)##NO (1), YES (2)",1)
  {
    case 1: show_message("1920s-50s"); break;
    case 2: show_message("1960s-70s"); break;
  }; break;
case 30: switch get_integer("IS THE ARAL SEA MISSING?##NO (1), YES (2)",1)
  {
    case 1: show_message("1970s-90s"); break;
    case 2: show_message("2000s+"); break;
  }; break;
case 31: switch get_integer('RIVERS "SIRION" OR "ANDUIN"?##YES (1), NO (2)',1)
  {
    case 1: X(32); break;
    case 2: X(36); break;
  }; break;
case 32: switch get_integer("MORDOR?##NO (1), YES (2)",1)
  {
    case 1: X(33); break;
    case 2: X(34); break;
  }; break;
case 33: switch get_integer("BELERIAND?##YES (1), NO (2)",1)
  {
    case 1: show_message("FIRST AGE"); break;
    case 2: show_message("EARLY SECOND AGE"); break;
  }; break;
case 34: switch get_integer("NÚMENOR?##YES (1), NO (2)",1)
  {
    case 1: show_message("LATE SECOND AGE"); break;
    case 2: X(35); break;
  }; break;
case 35: switch get_integer("THE FOREST EAST OF THE MISTY MOUNTAINS IS...##GREENWOOD THE GREAT (1), MIRKWOOD (2), THE WOOD OF GREENLEAVES (3)",1)
  {
    case 1: show_message("EARLY THIRD AGE"); break;
    case 2: show_message("LATE THIRD AGE"); break;
    case 3: show_message("FOURTH AGE"); break;
  }; break;
case 36: switch get_integer("CAIR PARAVEL?##YES (1), NO (2)",1)
  {
    case 1: X(37); break;
    case 2: X(41); break;
  }; break;
case 37: switch get_integer("CALORMEN?##NO (1), YES (2)",1)
  {
    case 1: X(38); break;
    case 2: X(40); break;
  }; break;
case 38: switch get_integer("LOTTA ISLANDS?##NO (1), YES (2)",1)
  {
    case 1: X(39); break;
    case 2: show_message("DAWN TREADER"); break;
  }; break;
case 39: switch get_integer("BERUNA##FORD (1), BRIDGE (2)",1)
  {
    case 1: show_message("THE LION, THE WITCH, AND THE WARDROBE"); break;
    case 2: show_message("PRINCE CASPIAN"); break;
  }; break;
case 40: switch get_integer("WEIRD RECURSIVE HEAVEN?##NO (1), YES (2)",1)
  {
    case 1: show_message("ONE OF THE RANDOM LATER BOOKS"); break;
    case 2: show_message("THE LAST BATTLE"); break;
  }; break;
case 41: switch get_integer("MOSSFLOWER?##YES (1), NO (2)",1)
  {
    case 1: show_message("REDWALL"); break;
    case 2: X(42); break;
  }; break;
case 42: switch get_integer("IS THE WORLD ON THE BACK OF A TURTLE?##YES (1), NO (2)",1)
  {
    case 1: show_message("DISCWORLD"); break;
    case 2: X(43); break;
  }; break;
case 43: switch get_integer("ARE YOU SURE THIS IS A MAP?##YES (1), NO (2)",1)
  {
    case 1: X(44); break;
    case 2: X(46); break;
  }; break;
case 44: switch get_integer("DID YOU MAKE IT YOURSELF?##YES (1)",1)
  {
    case 1: X(45); break;
  }; break;
case 45: switch get_integer("IT'S VERY NICE.##THANK YOU! (1)",1)
  {
    case 1: break;
  }; break;
case 46: switch get_integer("IS IT TRYING TO BITE YOU?##NO (1), YES (2)",1)
  {
    case 1: X(47); break;
    case 2: X(48); break;
  }; break;
case 47: switch get_integer("IS IT LARGER THAN A BREADBOX?##YES (1), NO (2), ABOUT THE SAME (3)",1)
  {
    case 1: show_message("TUBA") break;
    case 2: show_message("STAPLER") break;
    case 3: show_message("BREADBOX") break;
  }; break;
case 48: switch get_integer("IF YOU LET IT GO, WHAT DOES IT DO?##HISSES AND RUNS AWAY (1), SCREECHES AND FLAPS AROUND THE ROOM BREAKING THINGS (2)",1)
  {
    case 1: show_message("CAT") break;
    case 2: show_message("SEAGULL") break;
  }; break;
case 49: switch get_integer("PAKISTAN?##NO (1), YES (2)",1)
  {
    case 1: X(50); break;
    case 2: X(52); break;
  }; break;
case 50: switch get_integer("HOW MANY GERMANYS ARE THERE?##ONE (1), ONE, BUT IT'S HUGE (2), TWO (3)",1)
  {
    case 1: X(51); break;
    case 2: show_message("1941-45") break;
    case 3: show_message("1946-47") break;
  }; break;
case 51: switch get_integer("PERSIA OR IRAN?##PERSIA (1), IRAN (2)",1)
  {
    case 1: show_message("1930-34") break;
    case 2: show_message("1935-40") break;
  }; break;
case 52: switch get_integer("CAMBODIA?##NO (1), YES (2)",1)
  {
    case 1: X(53); break;
    case 2: X(55); break;
  }; break;
case 53: switch get_integer("ERITREA IS A PART OF...##ITALY (1), ETHIOPIA (2)",1)
  {
    case 1: X(54); break;
    case 2: show_message("1952-53"); break;
  }; break;
case 54: switch get_integer("CANADA IS...##MISSING A PIECE (1), FINE (2)",1)
  {
    case 1: show_message("1948"); break;
    case 2: show_message("1949-52"); break;
  }; break;
case 55: switch get_integer("THE UNITED ARAB REPUBLIC?##NO (1), YES (2)",1)
  {
    case 1: show_message("1954-57"); break;
    case 2: show_message("1958-60"); break;
  }; break;
case 56: switch get_integer('ZAIRE? OR: "HONG KONG (UK)"##YES (1), NO (2)',1)
  {
    case 1: show_message("1992-96"); break;
    case 2: X(57); break;
  }; break;
case 57: switch get_integer("SERBIA AND MONTENEGRO ARE...##ONE COUNTRY (1), TWO COUNTRIES (2)",1)
  {
    case 1: X(58); break;
    case 2: X(59); break;
  }; break;
case 58: switch get_integer("EAST TIMOR?##NO (1), YES (2)",1)
  {
    case 1: show_message("1997-2001"); break;
    case 2: show_message("2002-06"); break;
  }; break;
case 59: switch get_integer("HOW MANY SUDANS ARE THERE?##ONE (1), TWO (2)",1)
  {
    case 1: show_message("2007-11"); break;
    case 2: X(60); break;
  }; break;
case 60: switch get_integer("IS CRIMEA DISPUTED?##YES (1), NO (2)",1)
  {
    case 1: X(61); break;
    case 2: show_message("2012-13"); break;
  }; break;
case 61: switch get_integer('"COLORADO" OR "DANGER-RADIOACTIVE EXCLUSION ZONE-AVOID"?##COLORADO (1), DANGER (2)',1)
  {
    case 1: show_message("2014-21"); break;
    case 2: X(62); break;
  }; break;
case 62: switch get_integer("DOES THE WARNING MENTION THE SPIDERS?##NO (1), YES (2)",1)
  {
    case 1: show_message("2022"); break;
    case 2: show_message("2023 OR LATER"); break;
  }; break;
case 63: switch get_integer("SAUDI ARABIA?##NO (1), YES (2)",1)
  {
    case 1: show_message("1922-32"); break;
    case 2: X(64); break;
  }; break;
case 64: switch get_integer("IS MOST OF WEST AFRICA A GIANT FRENCH BLOB?##YES (1), NO (2)",1)
  {
    case 1: X(49); break;
    case 2: X(65); break;
  }; break;
case 65: switch get_integer("HOW MANY VIETNAMS ARE THERE?##TWO (1), ONE (2)",1)
  {
    case 1: X(66); break;
    case 2: X(69); break;
  }; break;
case 66: switch get_integer("BANGLADESH?##NO (1), YES (2)",1)
  {
    case 1: X(67); break;
    case 2: show_message("1972-75"); break;
  }; break;
case 67: switch get_integer("IS THE AREA SOUTH OF LAKE VICTORIA...##BRITISH (1), TANGANYIKA (2), TANZANIA (3)",1)
  {
    case 1: X(68); break;
    case 2: show_message("1961-64"); break;
    case 3: show_message("1965-71"); break;
  }; break;
case 68: switch get_integer("THE TOWN ON I-25 BETWEEN ALBUQUERQUE AND EL PASO IS...##HOT SPRINGS (1), TRUTH OR CONSEQUENCES (2)",1)
  {
    case 1: show_message("1948-49"); break;
    case 2: show_message("1950-52"); break;
  }; break;
case 69: switch get_integer("JIMMY CARTER IS...##BEING ATTACKED BY A GIANT SWIMMING RABBIT (1), FINE (2)",1)
  {
    case 1: show_message("APRIL 20, 1979"); break;
    case 2: X(70); break;
  }; break;
case 70: switch get_integer("THE SINAI IS PART OF WHAT COUNTRY?## ISRAEL (1), MOSTLY ISRAEL (2), MOSTLY EGYPT (3), EGYPT (4)",1)
  {
    case 1: show_message("1976-79"); break;
    case 2: show_message("1980"); break;
    case 3: show_message("1981"); break;
    case 4: X(71); break;
  }; break;
case 71: switch get_integer("WHAT'S THE CAPITAL OF MICRONESIA?## KOLONIA (1), PALIKIR (2)",1)
  {
    case 1: X(72); break;
    case 2: X(73); break;
  }; break;
case 72: switch get_integer("REPUBLIC OF THE UPPER VOLTA OR BURKINA FASO?## UPPER VOLTA (1), BURKINA FASO (2)",1)
  {
    case 1: show_message("1982-84"); break;
    case 2: show_message("1985-88"); break;
  }; break;
case 73: switch get_integer("(NUMBER OF YEMENS)+(NUMBER OF GERMANYS)=?## FOUR (1), THREE (2), TWO (3)",1)
  {
    case 1: show_message("1989-EARLY 1990"); break;
    case 2: show_message("MID-1990"); break;
    case 3: show_message("LATE 1990-1991"); break;
  }; break;
case 74: switch get_integer("DOES THE SOVIET UNION EXIST?## YES (1), NO (2)",1)
  {
    case 1: X(64); break;
    case 2: X(56); break;
  }; break;
}

Numbering system

Version 1: before reordering of YES, NO options to save bytes
Version 2 (current): (reordered option numbers in black)


What's the ugliest line of R code that still parses?

72 96 characters.

`c`<-function(...){list(...)[[-1]];}->>`c`;`[`=0;`]`=10;c(c,c)(c,c)(c,invisible)(`[`[]:`]`[])[];

Ugliness:

Reusing a standard function name
Using symbols as variable names
Global assignment
Right assignment
Self-redefinition of function
Unnecessary trailing semicolon(s)
Unnecessary sub-scripting numbers
Unnecessary quoting of variable name
Leaves the workspace in a state which will almost certainly break any subsequent code run

Generates the sequence 0-10 (thanks to Andrie for the idea to do that).

output:

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


Perl

fork || do {sleep(1) while(1)}

Each time you run this program, it halts and doesn't halt.


Jelly, 41 bytes
e/€S;eḲ1ịⱮƊ}¥/€;=Ḣ¥/€µS
LØAœ!ż€³Œu¤ÇÐṀẎḢ€

Try it online!
This is really messy and also O(26^n) lol.
Explanation: literally just brute forces it ._.
-6 bytes thanks to caird coinheringaahing


Find highest scoring matrix without property X

16/9 20/11 22/12 28/15 30/16 32/17 34/18 36/19 (Java)

This uses a number of ideas to reduce the search space and cost. View the revision history for more details on earlier versions of the code.

It's clear that wlog we can consider only circulant matrices in which the first row is a Lyndon word: if the word is non-prime then it must have property X, and otherwise we can rotate without affecting the score or property X.
Based on heuristics from the observed short winners, I'm now iterating through the Lyndon words starting at the ones with 50% density (i.e. the same number of 0 and 1) and working out; I use the algorithm described in A Gray code for fixed-density necklaces and Lyndon words in constant amortized time, Sawada and Williams, Theoretical Computer Science 502 (2013): 46-54.
An empirical observation is that the values occur in pairs: each optimum Lyndon word that I've found scores the same as its reversal. So I get about a factor of two speedup by only considering one half of each such pair.
My original code worked with BigInteger to give an exact test. I get a significant speed improvement, at the risk of false negatives, by operating modulo a large prime and keeping everything in primitives. The prime I've chosen is the largest one smaller than 257, as that allows multiplying by the base of my notional vector representation without overflowing.
I've stolen Suboptimus Prime's heuristic that it's possible to get quick rejections by considering subsets in increasing order of size. I've now merged that idea with the ternary subset meet-in-the-middle approach to test for colliding subsets. (Credit to KennyTM for suggesting trying to adapt the approach from the integer subset problem; I think that xnor and I saw the way to do it pretty much simultaneously). Rather than looking for two subsets which can include each column 0 or 1 times and have the same sum, we look for one subset which can include each column -1, 0, or 1 times and sum to zero. This significantly reduces the memory requirements.
There's an extra factor of two saving in memory requirements by observing that since each element in {-1,0,1}^m has its negation also in {-1,0,1}^m it's only necessary to store one of the two.
I also improve memory requirements and performance by using a custom hashmap implementation. To test 36/19 requires storing 3^18 sums, and 3^18 longs is almost 3GB without any overhead - I gave it 6GB of heap because 4GB wasn't enough; to go any further (i.e. test 38/20) within 8GB of RAM would require further optimisation to store ints rather than longs. With 20 bits required to say which subset produces the sum that would leave 12 bits plus the implicit bits from the bucket; I fear that there would be too many false collisions to get any hits.
Since the weight of the evidence suggests that we should look at 2n/(n+1), I'm speeding things up by just testing that.
There's some unnecessary but reassuring statistical output.

import java.util.*;

// Aiming to find a solution for (2n, n+1).
public class PPCG41021_QRTernary_FixedDensity {
    private static final int N = 36;
    private static int density;
    private static long start;
    private static long nextProgressReport;

    public static void main(String[] args) {
        start = System.nanoTime();
        nextProgressReport = start + 5 * 60 * 1000000000L;

        // 0, -1, 1, -2, 2, ...
        for (int i = 0; i < N - 1; i++) {
            int off = i >> 1;
            if ((i & 1) == 1) off = ~off;
            density = (N >> 1) + off;

            // Iterate over Lyndon words of length N and given density.
            for (int j = 0; j < N; j++) a[j] = j < N - density ? '0' : '1';
            c = 1;
            Bs[1] = N - density;
            Bt[1] = density;
            gen(N - density, density, 1);
            System.out.println("----");
        }

        System.out.println("Finished in " + (System.nanoTime() - start)/1000000 + " ms");
    }

    private static int c;
    private static int[] Bs = new int[N + 1], Bt = new int[N + 1];
    private static char[] a = new char[N];
    private static void gen(int s, int t, int r) {
        if (s > 0 && t > 0) {
            int j = oracle(s, t, r);
            for (int i = t - 1; i >= j; i--) {
                updateBlock(s, t, i);
                char tmp = a[s - 1]; a[s - 1] = a[s+t-i - 1]; a[s+t-i - 1] = tmp;
                gen(s-1, t-i, testSuffix(r) ? c-1 : r);
                tmp = a[s - 1]; a[s - 1] = a[s+t-i - 1]; a[s+t-i - 1] = tmp;
                restoreBlock(s, t, i);
            }
        }
        visit();
    }

    private static int oracle(int s, int t, int r) {
        int j = pseudoOracle(s, t, r);
        updateBlock(s, t, j);
        int p = testNecklace(testSuffix(r) ? c - 1 : r);
        restoreBlock(s, t, j);
        return p == N ? j : j + 1;
    }

    private static int pseudoOracle(int s, int t, int r) {
        if (s == 1) return t;
        if (c == 1) return s == 2 ? N / 2 : 1;
        if (s - 1 > Bs[r] + 1) return 0;
        if (s - 1 == Bs[r] + 1) return cmpPair(s-1, t, Bs[c-1]+1, Bt[c-1]) <= 0 ? 0 : 1;
        if (s - 1 == Bs[r]) {
            if (s == 2) return Math.max(t - Bt[r], (t+1) >> 1);
            return Math.max(t - Bt[r], (cmpPair(s-1, t, Bs[c-1] + 1, Bt[c-1]) <= 0) ? 0 : 1);
        }
        if (s == Bs[r]) return t;
        throw new UnsupportedOperationException("Hit the case not covered by the paper or its accompanying code");
    }

    private static int testNecklace(int r) {
        if (density == 0 || density == N) return 1;
        int p = 0;
        for (int i = 0; i < c; i++) {
            if (r - i <= 0) r += c;
            if (cmpBlocks(c-i, r-i) < 0) return 0;
            if (cmpBlocks(c-i, r-1) > 0) return N;
            if (r < c) p += Bs[r-i] + Bt[r-i];
        }
        return p;
    }

    private static int cmpPair(int a1, int a2, int b1, int b2) {
        if (a1 < b1) return -1;
        if (a1 > b1) return 1;
        if (a2 < b2) return -1;
        if (a2 > b2) return 1;
        return 0;
    }

    private static int cmpBlocks(int i, int j) {
        return cmpPair(Bs[i], Bt[i], Bs[j], Bt[j]);
    }

    private static boolean testSuffix(int r) {
        for (int i = 0; i < r; i++) {
            if (c - 1 - i == r) return true;
            if (cmpBlocks(c-1-i, r-i) < 0) return false;
            if (cmpBlocks(c-1-i, r-1) > 0) return true;
        }
        return false;
    }

    private static void updateBlock(int s, int t, int i) {
        if (i == 0 && c > 1) {
            Bs[c-1]++;
            Bs[c] = s - 1;
        }
        else {
            Bs[c] = 1;
            Bt[c] = i;
            Bs[c+1] = s-1;
            Bt[c+1] = t-i;
            c++;
        }
    }

    private static void restoreBlock(int s, int t, int i) {
        if (i == 0 && (c > 0 || (Bs[1] != 1 || Bt[1] != 0))) {
            Bs[c-1]--;
            Bs[c] = s;
        }
        else {
            Bs[c-1] = s;
            Bt[c-1] = t;
            c--;
        }
    }

    private static long[] stats = new long[N/2+1];
    private static long visited = 0;
    private static void visit() {
        String word = new String(a);

        visited++;
        if (precedesReversal(word) && testTernary(word)) System.out.println(word + " after " + (System.nanoTime() - start)/1000000 + " ms");
        if (System.nanoTime() > nextProgressReport) {
            System.out.println("Progress: visited " + visited + "; stats " + Arrays.toString(stats) + " after " + (System.nanoTime() - start)/1000000 + " ms");
             nextProgressReport += 5 * 60 * 1000000000L;
        }
    }

    private static boolean precedesReversal(String w) {
        int n = w.length();
        StringBuilder rev = new StringBuilder(w);
        rev.reverse();
        rev.append(rev, 0, n);
        for (int i = 0; i < n; i++) {
            if (rev.substring(i, i + n).compareTo(w) < 0) return false;
        }
        return true;
    }

    private static boolean testTernary(String word) {
        int n = word.length();
        String rep = word + word;

        int base = 1;
        for (char ch : word.toCharArray()) base += ch & 1;

        // Operating base b for b up to 32 implies that we can multiply by b modulo p<2^57 without overflowing a long.
        // We're storing 3^(n/2) ~= 2^(0.8*n) sums, so while n < 35.6 we don't get *too* bad a probability of false reject.
        // (In fact the birthday paradox assumes independence, and our values aren't independent, so we're better off than that).
        long p = (1L << 57) - 13;
        long[] basis = new long[n];
        basis[0] = 1;
        for (int i = 1; i < basis.length; i++) basis[i] = (basis[i-1] * base) % p;

        int rows = n / 2 + 1;
        long[] colVals = new long[n];
        for (int col = 0; col < n; col++) {
            for (int row = 0; row < rows; row++) {
                colVals[col] = (colVals[col] + basis[row] * (rep.charAt(row + col) & 1)) % p;
            }
        }

        MapInt57Int27 map = new MapInt57Int27();
        // Special-case the initial insertion.
        int[] oldLens = new int[map.entries.length];
        int[] oldSupercounts = new int[1 << 10];
        {
            // count = 1
            for (int k = 0; k < n/2; k++) {
                int val = 1 << (25 - k);
                if (!map.put(colVals[k], val)) { stats[1]++; return false; }
                if (!map.put(colVals[k + n/2], val + (1 << 26))) { stats[1]++; return false; }
            }
        }
        final long keyMask = (1L << 37) - 1;
        for (int count = 2; count <= n/2; count++) {
            int[] lens = map.counts.clone();
            int[] supercounts = map.supercounts.clone();
            for (int sup = 0; sup < 1 << 10; sup++) {
                int unaccountedFor = supercounts[sup] - oldSupercounts[sup];
                for (int supi = 0; supi < 1 << 10 && unaccountedFor > 0; supi++) {
                    int i = (sup << 10) + supi;
                    int stop = lens[i];
                    unaccountedFor -= stop - oldLens[i];
                    for (int j = oldLens[i]; j < stop; j++) {
                        long existingKV = map.entries[i][j];
                        long existingKey = ((existingKV & keyMask) << 20) + i;
                        int existingVal = (int)(existingKV >>> 37);

                        // For each possible prepend...
                        int half = (existingVal >> 26) * n/2;
                        // We have 27 bits of key, of which the top marks the half, so 26 bits. That means there are 6 bits at the top which we need to not count.
                        int k = Integer.numberOfLeadingZeros(existingVal << 6) - 1;
                        while (k >= 0) {
                            int newVal = existingVal | (1 << (25 - k));
                            long pos = (existingKey + colVals[k + half]) % p;
                            if (pos << 1 > p) pos = p - pos;
                            if (pos == 0 || !map.put(pos, newVal)) { stats[count]++; return false; }
                            long neg = (p - existingKey + colVals[k + half]) % p;
                            if (neg << 1 > p) neg = p - neg;
                            if (neg == 0 || !map.put(neg, newVal)) { stats[count]++; return false; }
                            k--;
                        }
                    }
                }
            }
            oldLens = lens;
            oldSupercounts = supercounts;
        }

        stats[n/2]++;
        return true;
    }

    static class MapInt57Int27 {
        private long[][] entries;
        private int[] counts;
        private int[] supercounts;

        public MapInt57Int27() {
            entries = new long[1 << 20][];
            counts = new int[1 << 20];
            supercounts = new int[1 << 10];
        }

        public boolean put(long key, int val) {
            int bucket = (int)(key & (entries.length - 1));
            long insert = (key >>> 20) | (((long)val) << 37);
            final long mask = (1L << 37) - 1;

            long[] chain = entries[bucket];
            if (chain == null) {
                chain = new long[16];
                entries[bucket] = chain;
                chain[0] = insert;
                counts[bucket]++;
                supercounts[bucket >> 10]++;
                return true;
            }

            int stop = counts[bucket];
            for (int i = 0; i < stop; i++) {
                if ((chain[i] & mask) == (insert & mask)) {
                    return false;
                }
            }

            if (stop == chain.length) {
                long[] newChain = new long[chain.length < 512 ? chain.length << 1 : chain.length + 512];
                System.arraycopy(chain, 0, newChain, 0, chain.length);
                entries[bucket] = newChain;
                chain = newChain;
            }
            chain[stop] = insert;
            counts[bucket]++;
            supercounts[bucket >> 10]++;
            return true;
        }
    }
}

The first one found is

000001001010110001000101001111111111

and that's the only hit in 15 hours.

Smaller winners:

4/3:    0111                       (plus 8 different 8/6)
9/6:    001001011                  (and 5 others)
11/7:   00010100111                (and 3 others)
13/8:   0001001101011              (and 5 others)
15/9:   000010110110111            (and 21 others)
16/9:   0000101110111011           (and 1 other)
20/11:  00000101111011110111       (and others)
22/12:  0000001100110011101011     (and others)
24/13:  000000101011101011101011   (and others)
26/14:  00000001101110010011010111 (and others)
28/15:  0000000010000111100111010111 (and others)
30/16:  000000001011001110011010101111 (and probably others)
32/17:  00001100010010100100101011111111 (and others)
34/18:  0000101000100101000110010111111111 (and others)


Find the shortest representation of a number in Modular SNUSP

Oracle SQL 11.2, 341 262 bytes

WITH e AS(SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4),n(s,v,p,c,i)AS(SELECT'#',0,0,e,1 FROM e UNION ALL SELECT c||s,DECODE(c,'+',1,'@',p,0)+v,v,e,i+1 FROM n,e WHERE i<11)CYCLE s SET y TO 1 DEFAULT 0 SELECT s FROM n WHERE:1=v AND rownum=1;

Old version

WITH e AS(SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4),n(s,v,p,c) AS(SELECT'#',0,0,e FROM e UNION ALL SELECT s||c,CASE c WHEN'+'THEN 1 WHEN'='THEN 0 WHEN'@'THEN p ELSE 0 END+v,v,e FROM n,e WHERE LENGTH(s)<10)CYCLE s SET y TO 1 DEFAULT 0 SELECT MIN(REVERSE(s))KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s))FROM n WHERE v=:1;

:1 the number to represent in Modular SNUSP

Un-golfed :

WITH e AS (SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4),
n(s,v,p,c,i) AS
(
  SELECT '#',0,0,e,1 FROM e
  UNION ALL
  SELECT s||c
       , DECODE(c,'+',1,'@',p,0)+v
       , v
       , e
       , i+1
  FROM n,e
  WHERE i<11
) CYCLE s SET y TO 1 DEFAULT 0
SELECT s FROM n WHERE:1=v AND rownum=1;

First create a view with 3 lines, one for each symbol used to represent numbers, minus # which is only used at the end of the string :

SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4;

Then the recursive view n generates every string possible with those 3 symbols, concatenates them to # and evaluates them.

The parameters are :

s : the Modular SNUSP representation of the number being evaluated
  v : the decimal value of s computed by the previous iteration
  p : v computed by the i-2 iteration
  c : the next symbol to concatenate to s
  i : the length of s, only needed to get rid of two LENGTH() for golfing purpose

DECODE(c,'+',1,'@',p,0)+v

If the last symbol is + then add 1
If it is @ add the value of the i-2 iteration
Else the symbol is either # or =. v is initialised with 0 in the init part of the recursive view, so the new v is equal to the previous v in either case.

WHERE i<11

Every string possible with the 3 symbols is computed, this part insure that the request does not run until the big crunch.

CYCLE s SET y TO 1 DEFAULT 0

Since there is no rule to the construction of the strings, duplicates are bound to arise. Being in a recursive view Oracle interprets those duplicates as cycles and throw an error if the case is not explicitly taken care of.

SELECT s FROM n WHERE:1=v AND rownum=1;

Returns the first Modular SNUSP representation that evaluate to the decimal number entered as parameter :1

In my tests that first line is always one of the shortest representations.

In the case your database would not act in the same way, then that last clause should be replaced with

SELECT MIN(s)KEEP(DENSE_RANK FIRST ORDER BY i)FROM n WHERE:1=v


Add comments to a Python script and make it a bilingual Python/C++ “program”

Score 119
(Thx @Linus for the byte count)
(1 byte saved thx @Conor O'Brien)
(1 byte saved thx @PieCot)
Counting bytes again by hand, I found 113. Maybe it's right this time. No it's not
#include <cstdio>
#define def main(){0?
#define print(x) puts(x);}
#define greet()

Notes: stdio and puts are still alive and kicking in C++. The missing int type is valid in C++ 4. Test


Dyalog APL, 1 byte
?

Just a builtin. Try it here.


Dyalog APL, 7 bytes

⌈/⌈/-⌊/

Test it on TryAPL.

How it works

⌈/⌈/-⌊/  Dyadic chain. Left argument: d. Right argument: v

     ⌊/  Reduce v by d-wise minimum, yielding the minima of all slices of length d.
  ⌈/     Reduce v by d-wise maximum, yielding the maxima of all slices of length d.
    -    Subtract, yielding the ranges of all slices of length d.
⌈/       Take the maximum.


Get a random n digit number with distinct digits and first not a 0

Python 2, 77 bytes

from random import*
r=range(10)
while[1]>r:shuffle(r)
print`r`[1:input()*3:3]

Try it online!

Shuffles the list of 10 digits until it doesn't start with 0, then makes a number with the first n digits listed.


Wolfram Language, 63 bytes

#//.{{I,x_}->x,{{K,x_},y_}->x,{{{S,x_},y_},z_}->{{x,z},{y,z}}}&

Try it online!

God, I love pattern matching in Wolfram Language. Represents (xy) as {x,y} (a list of two elements).

Alternatively, if we represent (xy) with x>y, we can do it in 55 bytes.

#//.{I>x_->x,(K>x_)>y_->x,((S>x_)>y_)>z_->(x>z)>(y>z)}&

Try it online!


Python, 47 34 33 bytes

lambda s:s[-1:]*s[-1]==s[-s[-1]:]

s[-1] is the last member of the list s. Checks that the last s[-1] members of the input array s are the same as an array of s[-1] repeated that many times.

Takes input as an array of integers. This is a lambda expression; to use it, assign it by prefixing lambda with f=.

Try it on Ideone!

To test:

>>> f=lambda s:s[-1:]*s[-1]==s[-s[-1]:]
>>> f([27, 33, 54, 65, 97, 33, 52, 55, 60, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10])
True
>>> f([50, 39, 94, 105, 49, 29, 74, 102, 2, 106, 44, 7, 7, 7, 7, 7, 7])
False

Saved 13 bytes thanks to Leaky Nun!

Saved a byte thanks to Dennis!


Python 2, 81 bytes

x=0
exec"print'%05.2f.2017'%(x%30.99+1.01);x+=7+'0009ANW'.count(chr(x/7+40));"*53

Try it online!

No date libraries, computes the dates directly. The main trick is to treat the dd.mm as a decimal value. For example, 16.04.2017 (April 16) corresponds to the number 16.04. The number is printed formatted as xx.xx with  .2017 appended.

The day and month are computed arithmetically. Each week adds 7 days done as x+=7. Taking x modulo 30.99 handles rollover by subtracting 30.99 whenever the day number gets too big. This combines -31 to reset the days with +0.01 to increment the month.

The rollover assumes each month has 31 days. Months with fewer days are adjusted for by nudging x upwards on certain week numbers with +[8,8,8,17,25,38,47].count(x/7). These list is of the week numbers ending these short months, with 8 tripled because February is 3 days short of 31.

This list could is compressed into a string by taking ASCII values plus 40. The shift of +40 could be avoided by using unprintable chars, and could be accessed shorter as a bytes object in Python 3.


87 bytes, 5 flavours, (87+10)/25 = 3.88

^(((?=W)[[:word:]&&]art|Ho(?=a)\ar|Bre(?=ez)[]e]\z|E(?=dg)[[d]]g)y|(?=Da)[D-[E]]apper)$

I've gone with the easy to test flavours for now, which are:

Regex101: PCRE (PHP), Javascript, Python
Regex Storm: .NET
Rubular: Ruby

The general structure is ^((...)y|...)$, i.e. factoring out the trailing ys and adding anchors.

Warty (PCRE)

(?=W)[[:word:]&&]art

In PCRE and Ruby, [[:word:]] is a POSIX character class matching a word character — in other flavours you get a [[:word:] character class then literal &&], which fails the (?=W) assert. To make Ruby fail, && is used to intersect the POSIX class with nothing, whereas in PCRE && has no special meaning.

Hoary (Javascript)

Ho(?=a)\ar

For whatever reason, Javascript is the only flavour out of the bunch where \a is a literal a — in other flavours it matches the bell character (ASCII 7).

Breezy (Python)

Bre(?=ez)[]e]\z

In Python and Javascript, \z is a literal z — in the other flavours it is equivalent to the $ end of string anchor. To make Javascript fail we use the char class []e], which is an empty char class [] then literal e] in Javascript, and a two-char class []e] in Python.

Dapper (.NET)

(?=Da)[D-[E]]apper

In .NET, [D-[E]] is a set difference, removing the set [E] from [D]. In PCRE, Javascript and Python, we have the class [D-[E] then a literal ]. Ruby's a little different, but for some reason it parses as a class [D-[E]] which only matches E, and I have yet to figure out why...

Edgy (Ruby)

E(?=dg)[[d]]g

Ruby allows char classes inside char classes, so [[d]] is actually equivalent to [d], or just d. In the other flavours, we have [[d] then a literal ].


MATL, 4 bytes

W4YL

Try it online!

How it works:

W       % Push 2 raised to (implicit) input
4YL     % (Walsh-)Hadamard matrix of that size. Display (implicit)

Without the built-in: 11 bytes

1i:"th1M_hv

Try it online!

How it works:

For each Walsh matrix W, the next matrix is computed as [W W; W −W], as is described in the challenge. The code does that n times, starting from the 1×1 matrix [1].

1       % Push 1. This is equivalent to the 1×1 matrix [1]
i:"     % Input n. Do the following n times
  t     %   Duplicate
  h     %   Concatenate horizontally
  1M    %   Push the inputs of the latest function call
  _     %   Negate
  h     %   Concatenate horizontally
  v     %   Concatenate vertically
        % End (implicit). Display (implicit)


Find the line guaranteed by Sylvester-Gallai

Python 2, not golfed

Sure, they say there's a worst case O(n*log(n)) algorithm, but who cares about the worst case? It's the average case we usually care about, and this simple random algorithm runs in expected linear time on arbitrary inputs!

(By comparison, the deterministic brute force algorithm can be fed carefully constructed inputs to force it to run in quadratic time at least.)

import random,math
def radical_to_normal(x,y): return (x[1]**(1./x[0]),y[1]**(1./y[0]))

def distance_to_line(p1,p2,p3):
 dx = p2[0] - p1[0]
 dy = p2[1] - p1[1]
 return abs(dy*p3[0] + dx*p3[1] + p2[0]*p1[1] - p2[1]*p1[0]) / math.sqrt(dy*dy + dx*dx)

points = input() #input as list of pairs
c = True
while c:
    c = False
    p1,p2 = random.sample(set(points), 2)
    for p3 in points:
        if distance_to_line(radical_to_normal(*p1), radical_to_normal(*p2), radical_to_normal(*p3)) < 0.00001:
            c = True
print p1,p2

Example run:

➤ python sylvester.py
[((1,0),(1,0)),((1,1),(1,0)),((1,2),(1,0)),((1,0),(1,1)),((1,1),(1,1)),((1,2),(1,1)),((1,0),(1,2)),((1,1),(1,2)),((1,2),(1,2))]
((1, 2), (1, 2)) ((1, 0), (1, 1))

How it works

It's been proved (Csima and Sawyer 1993) that roughly 6/13 of all lines in any set are ordinary (only involve 2 points from the set) except when n=7. As the number of points goes to infinity, the lower bound goes to 1/2 of the lines (Green and Tao 2013). Therefore, we expect to have to test around 2-3 pairs of points on average before finding an ordinary line if we sample pairs of points at random.

This simple program just selects a random pair of points, then checks the distance from the line they form to a third point, which ranges over all points in the set. All three points are converted from radical root form to floats by radical_to_normal() before the distance is calculated by distance_to_line(). If the distance is below a threshold (indicating they are collinear), we set a sentinel to try again. Until every point tested passes above the threshold, we try, try again. (This threshold could be made much smaller and still work, of course.)

Since we test an expected constant number of point pairs, and we test n points for each pair, the algorithm runs in expected time O(n).


solve puzzle with a tweet? javascript (fun challenge)


JavaScript (ES6), 177 175 bytes

a=>a.map((n,i)=>[n,l=i]).sort((a,b)=>a[0]-b[0]).reduce((P,x,i,a)=>(v=a.reduce((p,c,j)=>j<i?p:p+Math.min(c[0],x[0]+1),0))>m?[...Array(m=v)].map((_,k)=>a[l-k%(l+1-i)][1]):P,m=0)

Formatted and commented

a => a                              // given an array a:
.map((n, i) => [n, l = i])          // map it to [value, index] arrays / set l = length - 1
.sort((a, b) => a[0] - b[0])        // sort it by values in ascending order
.reduce((P, x, i, a) =>             // for each reference entry x at position i:
  (v = a.reduce((p, c, j) =>        //   for each entry c at position j:
    j < i ?                         //     if c is before x:
      p                             //       keep the previous sum (which is 0)
    :                               //     else:
      p + Math.min(c[0], x[0] + 1), //       add minimum(value[j], value[i] + 1)
    0                               //   initialize the sum at 0
  )) > m ?                          //   if the new sum v is better than our current best m:
    [...Array(m = v)].map((_, k) => //     update m to v and update the result to an array
      a[l - k % (l + 1 - i)][1]     //     of length m filled with indices picked repeatedly
    )                               //     between i and l
  :                                 //   else:
    P,                              //     keep the previous result
  m = 0                             // start with best score m = 0
)                                   // the final result is returned by the outer reduce()

Used formula

Below is a table showing how the formula F(i, j) = minimum(value[j], value[i] + 1) is working, here with i = 0 and the input [ 5, 2, 2 ].

This formula can be interpreted as follows: for each Skittle type, we can select no more than the number of the least available type plus one.

 j | Sorted    | value[j] | F(0, j) | Selected        | Output
   | input     |          |         | Skittles        | (starting from bottom left)
---+-----------+----------+---------+-----------------+-----------------------------
 0 | 2 2       |     2    |    2    | [2] [2]         | \
 1 | 1 1       |     2    |    2    | [1] [1]         |  > 0 1 2 0 1 2 0
 2 | 0 0 0 0 0 |     5    |    3    | [0] [0] [0] 0 0 | /

Test cases

let f =

a=>a.map((n,i)=>[n,l=i]).sort((a,b)=>a[0]-b[0]).reduce((P,x,i,a)=>(v=a.reduce((p,c,j)=>j<i?p:p+Math.min(c[0],x[0]+1),0))>m?[...Array(m=v)].map((_,k)=>a[l-k%(l+1-i)][1]):P,m=0)

console.log(JSON.stringify(f([ 1                ]))); // 0
console.log(JSON.stringify(f([ 4                ]))); // 0 0 0 0
console.log(JSON.stringify(f([ 4, 1             ]))); // 0 0 0 0
console.log(JSON.stringify(f([ 3, 1             ]))); // 0 1 0
console.log(JSON.stringify(f([ 5, 2, 2          ]))); // 0 2 1 0 2 1 0
console.log(JSON.stringify(f([ 2, 3, 5          ]))); // 2 1 0 2 1 0 2 1
console.log(JSON.stringify(f([ 2, 4, 5          ]))); // 2 1 2 1 2 1 2 1 2
console.log(JSON.stringify(f([ 3, 4, 5          ]))); // 2 1 0 2 1 0 2 1 0 2 1
console.log(JSON.stringify(f([ 1, 1, 1, 1, 1, 6 ]))); // 5 4 3 2 1 0 5
console.log(JSON.stringify(f([ 1, 1, 1, 1, 1, 8 ]))); // 5 5 5 5 5 5 5 5
console.log(JSON.stringify(f([ 2, 4, 6, 8       ]))); // 3 2 1 3 2 1 3 2 1 3 2 1 3 2