MATL, 11 10 9 7 bytes
3 Bytes saved thanks to @Luis!
:gyn&Z+

The first input is the size of the window and the second input is the array
Try it at MATL Online
Explanation
       % Implicitly grab the first input (n)
       %     STACK: { 3 }
:      % Create the array [1...n]
       %     STACK: { [1, 2, 3] }
g      % Convert it to a logical array, yielding an array of 1's of length n
       %     STACK: { [1, 1, 1] }
y      % Implicitly grab the second input and duplicate it
       %     STACK: { [2, 4, -3, 0, -4], [1, 1, 1], [2, 4, -3, 0, -4]}
n      % Determine the length of the array
       %     STACK: { [2, 4, -3, 0, -4], [1, 1, 1], 5}
&Z+    % Perform circular convolution
       %     STACK: { [-2, 2, 3, 1, -7] }
       % Implicitly display the result


Mathematica, 38

IntegerPartitions[n,5,Prime~Array~n,1]


JavaScript (ES6), 65 bytes

f=([s,t],[u,v])=>s<3^u<3?f(s+t,5-u+v)+2:s-u?t-+-v:t<v?++v-t:++t-v

for(i=1;i<5;i++)for(j=1;j<9;j++){let o=document.createElement("option");o.text=""+i+j;s.add(o);t.add(o.cloneNode(true));}

<select id=s></select><select id=t></select>
1

Takes input as strings.


Haskell, 38 bytes

l%n|n<1=l!!0|m<-n-1=l%m+tail(l++[0])%m

Try it online!

Improved from 39 bytes:

l%0=l!!0
l%n=l%(n-1)+tail(l++[0])%(n-1)

Recursively expresses the output l%n. Moving up corresponds to decrementing n, and moving right corresponds to taking tail l to shift all list elements one space left. So, the output l%n is the value above l%(n-1), plus the value above and to the right (tail l)%(n-1)

The base case n==0 is to take the first list element.

Ideally, the input would be padded with infinitely many zeroes to the right, since the derivatives of a polynomial eventually become zero. We simulate this by appending a 0 when we take the tail.

Weird alt 41:

(iterate(\q l->q l+q(tail l++[0]))head!!)


Surjective, Injective, Bijective, or Nothing?

Pyth - 10 9 13 bytes
im&{IdqSQSdE2

Takes domain and codomain separately as allowed by comments in OP.
Test Suite.


Generate a Pronounceable Nonsense Word \$n\$ syllables long


Jelly, 23 22 bytes

ŒṪạþ`§<4NA1¦A»/T$¦ÐLṪṀ

Try it online!

New version, which now efficiently handles moves backwards. Takes input as a boolean matrix (row major). Returns 1 for winnable and 0 for not.

Thanks to @AZTECCO for first suggesting using the indices of platforms, and @tsh for a test case that made me rethink my approach.

Explanation

ŒṪ                     | Multidimensional truthy indices of each
  ạþ`                  | Outer table using absolute difference and with the same argument on both sides:
     §                 | Sum innermost lists
      <4               | - Less than 4
        N              | Negate
         A1¦           | Absolute top row
                  ÐL   | Apply the following until no changes:
            A   $¦     | Absolute the rows indicated by the following:
             »/        | - Max of each column
               T       | - Truthy indices (i.e. where there’s a 1 in the column)
                    Ṫ  | Finally take the last row
                     Ṁ | Max

Step b step

(each matrix shown collapsed as a grid, with - = -1):

1. Input

0010
0001
1000
0010
0001
1000

2.ŒṪ

Multidimensional indices.

[[1, 3], [2, 4], [3, 1], [4, 3], [5, 4], [6, 1]]

3. ạþ`§<4N

Convert to initial outer table with -1 for possible moves between columns and 0 where no move possible.

--0-00
--0--0
00--0-
-----0
0-0--0
00-00-

4. A1¦A»/T$¦ÐL

Absolute first row, then iteratively take each column with at least one 1 in it, and absolute the rows at those indices; results after each iteration shown.

Absolute row 1 ->

110100
--0--0
00--0-
-----0
0-0--0
00-00-

-> Absolute rows 1, 2, 4 ->

110100
110110
00--0-
111110
0-0--0
00-00-

-> Absolute rows 1, 2, 3, 4, 5 ->

110100
110110
001101
111110
010110
00-00-

-> Absolute rows 1, 2, 3, 4, 5, 6 ->

110100
110110
001101
111110
010110
001001

5. ṪṀ

Finally, take the max of the last row

1

My previous 61 byte version has explanation in the edit history; thanks to @JonathanAllan for golfing 3 bytes off that one!


Retina 0.8.2, 8 bytes

.{51}

.

Try it online! Explanation:

.{51}

Delete the first 51 characters of each line. (Lines can only have between 52 and 67 characters, so this always matches once per line.)

.

Count the remaining non-newline characters.

7 bytes if empty input did not have to be supported:

.{52}

Try it online! Explanation:

.{52}

Delete the first 52 characters of each line. (Lines can only have between 52 and 67 characters, so this always matches once per line.)

Count 1 more than the number of remaining characters (including newlines).


CJam, 464 bytes

You thought CJam didn't have image manipulation functions? Well, you thought right! But I wasn't going to let that stop me.

"P3
690 690 4
"3a3*a690_@*a*qeuN/{0:U;{_'C<.5*:N;i[{XY+Z<[E8][9C]?XY<=}WWWW{XH<9F?}C{YC/[9FCF]=}{YC/3&9E?}{YH<9F?}{X29.5:R-zYR-z+H>FC?}{XA/1&9E?}{XH<FC?}{XR-_*YR-_*+F_*>E8?}{YK/(9F?}{XH<E9?}{XH<YH<^8E?}{XY+Z-A/XY-A/e&9F?}{XF/YF/^1&F9?}{XY<EC?}{XH-F/YH-F/|9F?}E{XHm6/YHm6/e&CE?}{XH-F/YH-F/|F9?}{XK/[CF9]=}{XH<YH<^FC?}{XY+Z-A/XY-A/e&FC?}{XR-zYR-ze>iA/[CF9]=}{XHm6/YHm6/e&F9?}{XY+F/1&CE?}]=:P~!!{60:Z{Z30:HYH-z-N*-{YV+_2$=XU+P2b1>4f*tt}fX}fY}*U90+:U;}/V90+:V;}/`"[]"-

This program outputs the image in the best way CJam can: as text that represents the image when saved as a PPM file. Don't even try running it with the online interpreter, by the way; you'll blow the stack. Run it with the Java interpreter and pipe the output to a file with a command like java -jar cjam-0.6.4.jar flags.cjam > flags.ppm. Once you've provided your input, send an EOF (may need to be immediately after a newline) with ctrl+D on Unix or ctrl+Z on Windows.

Sample

If it's really desired, I can try to paste the original ~3MB image source somewhere. But here's the result opened in GIMP and conerted to a PNG:

ABCDEFG
hijklmn
OPQRSTU
vwxyz z

Explanation

The image header, easily identifiable in the source, consists of the magic number, width, height, and maximum channel value. So the output is a 690*690 image (enough for 8*8 60px flags with 30px of spacing between them) with each R, G, and B value ranging from 0 to 4.

The image data is initialized as a 690*690*3 array filled with 3's, making the whole image light gray. Then the input is read, converted to uppercase, and split into lines. The lines are processed in a loop, incrementing the flag Y coordinate by 90 each iteration, and in each line, each character is processed in a loop, incrementing the flag X coordinate by 90 each iteration. Now the magic begins.

Each character is mapped to a flag's pixel function that, when called, returns the color of the pixel at the position (X, Y) on the flag. This is where most of the hard work went: concisely describing 26 images as mathematical functions. Each of these functions returns a color value from 8-15. This range takes advantage of the fact that, when converted to base 2, the resulting bit array can be interpreted as [1, R, G, B]. The first element can be removed and the rest multiplied by 4 to easily give a pixel value in the desired format that covers all the possible flag colors (as well as green, cyan, and magenta). It also works out nicely that there are one-character variables initialized to 10-15, and since varaibles don't need a space to syntactically separate them, any two colors besides black and blue can be entered next to each other without needing any spacing.

Once the function is retrieved, it's just a matter of iterating over both of X and Y from 0-60, calling the function at each step, and writing the result back to the image data array. An astute observer might notice that the color values returned by each flag function don't allow gray, though. So there's a bit of extra logic to skip spaces. But there are still the swallowtail cuts on 'A' and 'B'. So there's a bit of extra logic there, too. If the character value is less than 'C', a value is set such that the upper bound on the X loop varies correctly with respect to Y and the cut-out areas are never drawn.

Overall, I'm pretty happy with how this came out. It took a lot of work, but it was fun. Some flags don't perfectly match the reference image, but I think I got all the shapes to be within 1px of the target (if any are off by more than that, let me know and I'll fix them). And there's definitely still potential to optimize, as there's a fair amount of redundancy between the 26 flag functions.

Ineresting first attempt, 559 bytes

Altough I never quite finished this, I'll post it too, because it's pretty interesting. Instead of modelling each flag by a function of (X, Y) → color, flags are drawn as a composition of simple shapes. But I was worried about needing to write a substantial amount of rendering code for each different shape. After a lot of pondering, I realized I could render them all, with some clever overlapping and overdrawing, with just one pseudo-shape: all the points within a specified distance of a specified point, where the definition of "distance" is variable. Chessboard distance gives a square, Manhattan distance gives a diamond, and Euclidean distance gives a circle. This meant every shape had the same five parameters (color, distance mode, x, y, and max distance) and I only needed to write one shape data decoder and one rendering function with a small bit of distance mode logic.

"P3
690 690 4
"3a3*a690_@*a*qeuN/{0:U;{_'C<.5*:N;i[[8EX30:Q0Q9X60:ZQQCXQZQ]LLLL[F9TTQQ]Ca[9FTQ42QCTQ54QFTQ66Q9TQ78Q][E9TIQI9T42QI][9FTQZQ][FCXQQQ][E9T40QQET50QQ9TZQQET70QQ9T80QQ][FCTZQQ][E8YQQF][9FTQAQ9TQ9~Q][E9TZQQ][8ETTTQETZZQ][F9XQTK9XZQK9XQZK9XTQK][F4{4{JW^1&6*9+TJ)F*W)F*F}fJ}fW][CEX0ZZ][9FTQQF]Ea[E[TZ]_m*{CT@~24}/][F9TQQF][9FTAQQCT9~QQ][FCTTTQCTZZQ]C9$1>9a/Fa*+[9FTQQKCTQQA]9 6$1>Ca/Fa*+[C7{7\-_1&2*C+X@TT@F*}/]]=_!!{([TQQQ]+\+}*5/{~:R;.5-:H;.5-:G;:M;2b1>4f*:O;Z{ZQWQ-z-N*-{JG-{zM_!+#}:P~WH-PM{+}{e>}?RP<{WV+_2$=JU+Ott}*}fJ}fW}/U90+:U;}/V90+:V;}/`"[]"-


Pyth, 22 20 bytes

ql{m+=Z*=T^.j)hCdzlz

Try it yourself or run the testsuite.

Note the ASCII values of SRL, respectively 83, 76, 82. I abuse the fact that:

  i 83 + 1 = 1
  i 76 + 1 = i
  i 82 + 1 = -i

From here I just keep a variable for the current position and current direction. For every character I multiply the current direction with the above complex number, then add it to the current position.

At the end I check if all the visited positions are unique.


Python 2, 73 bytes

-3 bytes thanks to @Rod

C=map(input().count,'QDNP')
print C+[sum(map(int.__mul__,C,[25,10,5,1]))]

Try it online!


Python 2, 446 422 385 384 bytes

-1 byte thanks to @ovs

l=len
A=abs
s="""def v(O,N):
 def c():
 qp:
    qp:
        if(i!=j)*any(A(t-T)==1qiqj):i+=j;p.remove(j);c();return
 p=[[a]qO];c();r=C=p[:1];i=[sum(A(b-a)*A(c-b)qPqPqP)qp];N-=1
qC:
  if l(o)>5:r=0
 qp:C+=[P]*(1-all(A(a-b)-2**0.5qoqP)-(P in C))
 print(l(p)-l(C)+l(i)-l(set(i))==0)*any(k in Oq[0,N*1j,N+N*1j,N])*r,p>[]"""
exec eval("s"+".replace('q',' for %s in ',1)"*14%tuple("ijtTaabcPoPabk"))

The output format is a bit strange: it prints more than 7 characters for truthy output, and 7 or fewer characters for falsey output (7 characters is the length of "[] True". This may be stretching it, so the p>[] can be replaced by if p!=[] else 1 for +11 characters to give more traditional truthy/falsey output.

The input is a list of coordinates given as complex numbers, along with the dimension n.

Try it online!

All testcases

The invariant may be the most interesting part. Since it must be conserved on rotations and reflections, distance between corresponding tiles is just about the only thing that stays constant. Also, I could not rely on the order that the tiles are listed in the piece. Using the product/sum of distances between every tile led to collisions, but using triples of tiles worked well.

I used for _ in fourteen times (wow), so the exec/eval saves 37 bytes.

Ungolfed:

def invariant(piece):
    inv=1
    for a in piece:
        for b in piece:
            for c in piece:
                inv+=abs((b-a)*(c-b))
    return inv

def valid(occupied,n):
    # convert list of rows into coordinates of Xs
    if not len(occupied):
        return True
    # generate list of pieces (this takes care of rule #2)
    pieces = [[a] for a in occupied]
    def consolidate():
        for i in pieces:
            for j in pieces:
                # merge two pieces if they share an edge
                if i!=j and any(abs(tile1-tile2)==1 for tile1 in i for tile2 in j):
                    i += j
                    pieces.remove(j)
                    # this repeats consolidate until no change (nothing left to combine)
                    consolidate()
                    return
    consolidate()
    # get a connected component of pieces (for rule #3)
    connected = [pieces[0]]
    for connected_piece in connected:
        # eventually every piece should be connected if the board is otherwise valid, so
        # we can check for valid-size pieces in this outer loop
        # all polyominoes with at most 5 tiles are valid
        if len(connected_piece) > 5:
            return False
        for piece in pieces:
            if any(abs(a-b)==abs(1+1j) for a in connected_piece for b in piece) and piece not in connected:
                connected += [piece]
    # check that all pieces are only used once
    ids = [invariant(piece) for piece in pieces]
    used_once = len(ids) == len(set(ids))
    nm = n-1
    rule_1_met = any(k in occupied for k in [0, nm*1j, nm+nm*1j, nm])
    return used_once and rule_1_met and len(pieces) == len(connected)


JavaScript (V8), 271 bytes

f=(s,k='~!@#$%^&*()_+`1234567890-=\tQWERTYUIOP{}|\tqwertyuiop[]\\ASDFGHJKL:"\n\\asdfghjkl;\'ZXCVBNM<>?zxcvbnm,./')=>s.replace(/[^ ]/g,c=>k[k.indexOf(c)-1]).replace(/\\([^\\]*)\\?/g,(m,c)=>c.replace(/[a-zA-z]/g,l=>l>'Z'?l.toUpperCase():l.toLowerCase())).replace(/[?']/,"")

Try it online!
My first JavaScript code golf.
It could definitely be shorter, but I think this is a good start.
It basically finds each character in the k string and replaces it with the previous one, then swaps the case of everything between the A or a, and removes all occurences of Z or z (as shift key does nothing on its own).
This should be a normal QWERTY keyboard layout, but let me know if not.


Total number of cells in R numeric dataframe

My best two attempts so far only got me down to 11 characters. I'd love to see fewer than @Spacedman's 10!

>sum( `[<-`(x,,,1) )
[1] 15600

>sum(!(F&x))
[1] 15600

Got it!

sum(x^0)
[1] 15600


JavaScript (ES10),  179  155 bytes
Expects an array of arrays of frequencies, with the strongest broadcast in first position for each station.
Returns \$1\$ for cycle once, \$0\$ for cycle all, or \$3\$ if there's no solution at all.

a=>a.some(h=A=>a[(g=([x],C=q=>a.find(d=>d.includes(b[(b.indexOf(x)+q)%n])))=>!g[x]&&g(C(g[x]=1))-~g(C(n-1)))(A)],b=a.flat().sort(),n=b.length)|2*a.every(h)

Try it online!
How?
We first create an array b[] holding all frequencies sorted in lexicographical order. It means that the 80-99Mhz range will be put after the 100-110MHz range. But because the frequencies are wrapping around anyway, it doesn't matter. We also put the total number of frequencies in n.
b = a.flat().sort(), n = b.length

The helper function C takes a direction q and returns the sub-list corresponding to the station that is reached by moving towards q from the current leading frequency x.
C = q => a.find(d => d.includes(b[(b.indexOf(x) + q) % n]))

The callback function h takes the sub-list A of a station and walks through all connected stations, keeping track of the count (let's call it N). We use q = 1 to seek up and q = n - 1 to seek down. We eventually test a[N] to figure out whether all stations were reached.
h = A => a[(g = ([x], C = ...) => !g[x] && g(C(g[x] = 1)) - ~g(C(n - 1)))(A)]

This uses the helper function C described above and another recursive function g whose underlying object is also used to keep track of the stations that were already reached, using the leading frequency as the key.
We invoke h twice: once within a some() to detect cycle once and once within an every() to detect cycle all.


Write a function that takes (x, y) and return x to the power of y WITHOUT Loops

APL (7)

{×/⍵/⍺}

Left argument is base, right argument is exponent, e.g.:

     5 {×/⍵/⍺} 6
15625

Explanation:

⍵/⍺ replicates ⍺ ⍵ times, e.g. 5 {⍵/⍺} 6 -> 5 5 5 5 5 5
×/ takes the product, e.g. ×/5 5 5 5 5 5 -> 5×5×5×5×5×5 -> 15625


Evaluate an expression of minus and tilde

Python 2, 42 41 39 bytes

lambda s,x=0:'-x%+d'[len(s)%2:]%eval(s)

Try it online!


Python 2, 51 bytes

n,x,y=input()
c=n+y
while c%x:c+=y
print(c-n)/y,c/x

Try it online!
-8 bytes thanks to Jonathan Allan


Decompose words into other words (e.g., “afterglow” = “aft” + “erg” + “low”)

Python 186
a=open(raw_input()).read().split()
def W(r):
 if r:
    for i in range(1,len(r)+1):
     if r[:i]in a:
        for w in W(r[i:]):yield[r[:i]]+w
 else:yield[]
while 1:
 for f in W(raw_input()):print f

Not particularly efficient but actually not terrible slow. It just naively (I suppose it's possible, though I think unlikely that python does some clever optimizations) checks that sub-words are in the corncob dictionary and recursively finds as many words as it can. Of course this dictionary is pretty extensive and you could try one which doesn't include various abbreviations and acronyms (leading to things like bedridden: be dr id den). Also the linked dictionary did not seem to have 'A' or 'I' listed as words so I manually added them in.
Edit:
Now the first input is the filename of the dictionary to use, and every additional one is a word.


Perl, 48 45 43 bytes

Includes +4 for -Xlpi (-X can be left out but leaves ugly warnings on STDERR)

Run with the number after the -i option and the input on STDIN (supports multiple lines too). e.g. perl -Xlpi50 crunch.pl <<< "Duis commodo scelerisque ex, ac consectetur metus rhoncus."

crunch.pl:

s/.*\K[aeiou]|.*\K |.$// while pos=-$^I


05AB1E (legacy), 22 21 bytes

|εDgsðÛ©g-;LÅfOð*®J}»

Try it online.

21 bytes alternative using the formula \$Fib(\frac{n}{2}+2)-1\$ instead of \$\sum_{i=1}^{i=\frac{n}{2}}{Fib(i)}\$ :
(Credit to @JonathanAllan's Jelly answer for this formula.)

|εDgsðÛ©g-;ÌÅf<ð*®J}»

Try it online.

Explanation:

|                        # Take the input split by newlines
 ε                  }    # Map each line to:
  Dg                     #  Duplicate the line and take its length
    s                    #  Swap so the duplicated line is at the top of the stack again
     ðÛ                  #  Remove all leading spaces
       ©                 #  Store the result in the register (without popping)
        g                #  Take its length as well
         -               #  Subtract both lengths from each other
          ;              #  Halve it, because they are multiples of 2 indented spaces
           L             #  Create a list in the range [1, n]
            Åf           #  Get the i'th Fibonacci number for each
              O          #  And sum them together
               ð*        #  Have that many space characters
                 ®J      #  And join them with the saved string from the register
                    »    # And finally print the mapped list with new-lines


Write a program whose nontermination is independent of Peano arithmetic

Haskell, 838 bytes

“If you want something done, …”

import Control.Monad.State
data T=V Int|T:$T|A(T->T)
g=guard
r=runStateT
s!a@(V i)=maybe a id$lookup i s
s!(a:$b)=(s!a):$(s!b)
s@((i,_):_)!A f=A(\a->((i+1,a):s)!f(V$i+1))
c l=do(m,k)<-(`divMod`sum(1<$l)).pred<$>get;g$m>=0;put m;l!!fromEnum k
i&a=V i:$a
i%t=(:$).(i&)<$>t<*>t
x i=c$[4%x i,5%x i,(6&)<$>x i]++map(pure.V)[7..i-1]
y i=c[A<$>z i,1%y i,(2&)<$>y i,3%x i]
z i=(\a e->[(i,e)]!a)<$>y(i+1)
(i?h)p=c[g$any(p#i)h,do q<-y i;i?h$q;i?h$1&q:$p,do f<-z i;a<-x i;g$p#i$f a;c[i?h$A f,do b<-x i;i?h$3&b:$a;i?h$f b],case p of A f->c[(i+1)?h$f$V i,do i?h$f$V 7;(i+1)?(f(V i):h)$f$6&V i];V 1:$q:$r->c[i?(q:h)$r,i?(2&r:h)$V 2:$q];_->mzero]
(V a#i)(V b)=a==b
((a:$b)#i)(c:$d)=(a#i)c&&(b#i)d
(A f#i)(A g)=f(V i)#(i+1)$g$V i
(_#_)_=0<0
main=print$(r(8?map fst(r(y 8)=<<[497,8269,56106533,12033,123263749,10049,661072709])$3&V 7:$(6&V 7))=<<[0..])!!0

Explanation

This program directly searches for a Peano arithmetic proof of 0 = 1.  Since PA is consistent, this program never terminates; but since PA cannot prove its own consistency, the nontermination of this program is independent of PA.

T is the type of expressions and propositions:

A P represents the proposition ∀x [P(x)].
(V 1 :$ P) :$ Q represents the proposition P → Q.
V 2 :$ P represents the proposition ¬P.
(V 3 :$ x) :$ y represents the proposition x = y.
(V 4 :$ x) :$ y represents the natural x + y.
(V 5 :$ x) :$ y represents the natural x ⋅ y.
V 6 :$ x represents the natural S(x) = x + 1.
V 7 reprents the natural 0.

In an environment with i free variables, we encode expressions, propositions, and proofs as 2×2 integer matrices [1, 0; a, b], as follows:

M(i, ∀x [P(x)]) = [1, 0; 1, 4] ⋅ M(i, λx [P(x)])
M(i, λx [F(x)]) = M(i + 1, F(x)) where M(j, x) = [1, 0; 5 + i, 4 + j] for all j > i
M(i, P → Q) = [1, 0; 2, 4] ⋅ M(i, P) ⋅ M(i, Q)
M(i, ¬P) = [1, 0; 3, 4] ⋅ M(i, P)
M(i, x = y) = [1, 0; 4, 4] ⋅ M(i, x) ⋅ M(i, y)
M(i, x + y) = [1, 0; 1, 4 + i] ⋅ M(i, x) ⋅ M(i, y)
M(i, x ⋅ y) = [1, 0; 2, 4 + i] ⋅ M(i, x) ⋅ M(i, y)
M(i, S x) = [1, 0; 3, 4 + i] ⋅ M(i, x)
M(i, 0) = [1, 0; 4, 4 + i]
M(i, (Γ, P) ⊢ P) = [1, 0; 1, 4]
M(i, Γ ⊢ P) = [1, 0; 2, 4] ⋅ M(i, Q) ⋅ M(i, Γ ⊢ Q) ⋅ M(i, Γ ⊢ Q → P)
M(i, Γ ⊢ P(x)) = [1, 0; 3, 4] ⋅ M(i, λx [P(x)]) ⋅ M(i, x) ⋅ [1, 0; 1, 2] ⋅ M(i, Γ ⊢ ∀x P(x))
M(i, Γ ⊢ P(x)) = [1, 0; 3, 4] ⋅ M(i, λx [P(x)]) ⋅ M(i, x) ⋅ [1, 0; 2, 2] ⋅ M(i, y) ⋅ M(i, Γ ⊢ y = x) ⋅ M(i, Γ ⊢ P(y))
M(i, Γ ⊢ ∀x, P(x)) = [1, 0; 8, 8] ⋅ M(i, λx [Γ ⊢ P(x)])
M(i, Γ ⊢ ∀x, P(x)) = [1, 0; 12, 8] ⋅ M(i, Γ ⊢ P(0)) ⋅ M(i, λx [(Γ, P(x)) ⊢ P(S(x))])
M(i, Γ ⊢ P → Q) = [1, 0; 8, 8] ⋅ M(i, (Γ, P) ⊢ Q)
M(i, Γ ⊢ P → Q) = [1, 0; 12, 8] ⋅ M(i, (Γ, ¬Q) ⊢ ¬P)

The remaining axioms are encoded numerically and included in the initial environment Γ:

M(0, ∀x [x = x]) = [1, 0; 497, 400]
M(0, ∀x [¬(S(x) = 0)]) = [1, 0; 8269, 8000]
M(0, ∀x ∀y [S(x) = S(y) → x = y]) = [1, 0; 56106533, 47775744]
M(0, ∀x [x + 0 = x]) = [1, 0; 12033, 10000]
M(0, ∀y [x + S(y) = S(x + y)]) = [1, 0; 123263749, 107495424]
M(0, ∀x [x ⋅ 0 = 0]) = [1, 0; 10049, 10000]
M(0, ∀x ∀y [x ⋅ S(y) = x ⋅ y + x]) = [1, 0; 661072709, 644972544]

A proof with matrix [1, 0; a, b] can be checked given only the lower-left corner a (or any other value congruent to a modulo b); the other values are there to enable composition of proofs.

For example, here is a proof that addition is commutative.

M(0, Γ ⊢ ∀x ∀y [x + y = y + x]) = [1, 0; 6651439985424903472274778830412211286042729801174124932726010503641310445578492460637276210966154277204244776748283051731165114392766752978964153601068040044362776324924904132311711526476930755026298356469866717434090029353415862307981531900946916847172554628759434336793920402956876846292776619877110678804972343426850350512203833644, 14010499234317302152403198529613715336094817740448888109376168978138227692104106788277363562889534501599380268163213618740021570705080096139804941973102814335632180523847407060058534443254569282138051511292576687428837652027900127452656255880653718107444964680660904752950049505280000000000000000000000000000000000000000000000000000000]

You can verify it with the program as follows:

*Main> let p = A $ \x -> A $ \y -> V 3 :$ (V 4 :$ x :$ y) :$ (V 4 :$ y :$ x)
*Main> let a = 6651439985424903472274778830412211286042729801174124932726010503641310445578492460637276210966154277204244776748283051731165114392766752978964153601068040044362776324924904132311711526476930755026298356469866717434090029353415862307981531900946916847172554628759434336793920402956876846292776619877110678804972343426850350512203833644
*Main> r(8?map fst(r(y 8)=<<[497,8269,56106533,12033,123263749,10049,661072709])$p)a :: [((),Integer)]
[((),0)]

If the proof were invalid you would get the empty list instead.


Keg, 4 1 byte

This is in the documentation:

^

The mechanism is simple: Reverse the whole stack. The stack is in fact a string, and input will trivially be the items in the stack.

There isn't an online implementation; download the Python interpreter and run this program, with the input prepending the ^.


Count All Possible Unique Combinations of Letters in a Word

Python 2, 50 48 bytes

f=lambda s:s==''or len(s)*f(s[1:])/s.count(s[0])

Try it online!

No boring built-ins! To my surprise, this is even shorter than the brute force approach, calculating all of the permutations with itertools and taking the length.

This function uses the formula

\$\text{# of unique permutations} = \frac{\text{(# of elements)!}}{\prod_{\text{unique elements}}{\text{(# of occurences of that element)!}}}\$

and computes it on the fly. The factorial in the numerator is calculated by multiplying by len(s) in each function call. The denominator is a bit more subtle; in each call, we divide by the number of occurences of that element in what's left of the string, ensuring that for every character c, all numbers between 1 and the amount of occurences of c (inclusive) will be divided by exactly once. Since we divide only at the very end, we're guaranteed not to have any problems with Python 2's default floor division.


J - 77 char

Taking an approach that looks different from FUZxxl's answer but is actually very similar.

1!:2&4":2({.,|.@{.,@(256|$-0(0{[/:+`-/|@-])"1@|:(-#:1 2 3)|.!.0$)}.)0".1!:1]3

Some comments on the interesting bits.

1!:2&4": (...) 0".1!:1]3 - If J wasn't terrible about I/O and parsing, this could be refactored as to use &.".&.stdin'', to save 3 chars. But it is so we can't. Rest in peace, precious characters.
2 ({.,|.@{.,@( ... stuff using $ ... )}.) - This disassembles the input and reassembles the output. We use $ both as a reference to the input in stuff using $, and as an operation we need to perform on the input before running the stuff on it.
0( blah )"1@|: - Yes, that's a dyadic Transpose: we regroup the three rotation results as the innermost array axis, so that the Paeth logic can apply on each set separately with "1.
0{[/:+`-/|@-] - The Paeth logic: sort a,b,c by the magnitudes of (p minus each of a,b,c), and take the first.


Wolfram Language (Mathematica), 169 167 bytes
ConnectedGraphQ@Subgraph[Cases[#[v="StateAbbreviation"]&/@#@"BorderingStates"#@v&/@Interpreter["USState"]@#|"CA""HI"|"AK""WA"/."MI""MN"|"NY""RI"->0,a_ b_:>a<->b,3],#]&

Try it online!
TIO doesn't have data sets downloaded, so most of the footer is to ensure the code works as if they had been.
The BorderingStates properties differ from the given list of adjacencies in four ways: HI and AK do not border any other states, MI borders MN, and NY borders RI.
Interpreter["USStates"]@#           (* get Entitys corresponding to abbreviations *)
#@"BorderingStates"                 (* for each state, get a list of bordering states, *)
#[v="StateAbbreviation"]&/@ % #@v&  (* pair it (unordered) with each of those and convert back to abbreviations. *)
% /@ %%% |"CA""HI"|"AK""WA"         (* append CA-HI and AK-WA, *)
% /."MI""MN"|"NY""RI"->0            (* discard MI-MN and NY-RI, *)
Cases[ % ,a_ b_:>a<->b,3]           (* then get all pairs and convert them to edges. *)
ConnectedGraphQ@Subgraph[ % ,#]&    (* is the subgraph consisting of input states connected? *)

There's also GraphData["ContiguousUSAGraph"], which is missing AK-WA, AZ-CO, CA-HI, and NM-UT edges. Unfortunately, the vertices are numbered in what seems to be an arbitrary order.


Find random images from http://i.imgur.com/

HTML (152)

<img src=x
onload=console.log(s);g()
onerror=g=function(){s='http://i.imgur.com/'+Math.random().toString(36).substr(2,6)+'.png';event.target.src=s};g()>

This logs all found images on the JavaScript console using console.log(). Works in all tested browsers (Firefox, Chrome, IE9, Safari and Opera).

The fun part is that all sorts of funny images are flashing up for the blink of an eye :).

Try it! (jsFiddle wraps this into a more complete HTML page, but browsers also accept the single element.)

Props to the amazing random string method by doubletap!

Where can I see the JavaScript console and the logged images?

Firefox: Press Control-Shift-K (Command-Option-K on the Mac). Unselect the Net, CSS and JS buttons there, only select the Logging button.
Opera: Press Control+Shift+i, select the Console tab.
Chrome: Press Control+Shift+i, select the Console tab. On the bottom, select Logs.
Safari: Basically like Chrome, but make sure first that Safari's developer tools are activated. Then press Control+Alt+C (on Windows, not sure on the Mac) instead of Control+Shift+i, select the Console tab. On the bottom, select Logs.
IE: Press F12, select the console tab.


Pyth - 21 19 18 bytes
I wonder if there's a trick.
l{st#mP+Q^d3s_BMSE

Test Suite.
l                   Length
 {                  Uniquify
  s                 Combine divisor lists
   t#               Filter by if more than one element
     PM             Take prime factorization of each number
       +RQ          Add each num in list to input
          s_BM      Each num in list and its negative (with bifurcate)
              ^R3   Cube each num in list
                 SE Inclusive unary range - [1, 2, 3,... n] to input


JavaScript [160 bytes]

The following code seems to be 160 bytes unformatted.

   ('l2v2l6v2'+  'e1l1v3l2'+
 'v3e1v7e1v7e1v7e1l2v6e1l4v5'+
'e1l6v4e1l8v3e1l7l3v2e1l9l3v1')
 .replace(/[lve]\d/g,function
   (c){return Array(-~c[1]).
      join({l:' ',v:'Love'
         ,e:'\n'}[c[0
             ]])})

Simply run this in the browser console (e.g. in Firebug or Chrome Dev Tools).


Pyth, 14 bytes

smCi!M_jCd2 2z

Try it online.

How it works

 m           z  Map over the input with lambda d:
        Cd        Cast d to character.
       j  2       Convert to base 2.
      _           Reverse the resulting array.
    !M            Mapped logical NOT.
   i        2     Convert back to integer.
  C               Cast to character.
s               Concatenate the resulting characters.


MATL, 5 bytes
JYaZy

Try it online! Or verify all test cases.
Explanation
JYa   % Implicit input. Unpad matrix. This removes outer zeros
Zy    % Size. Implicit display


The GOLF CPU Golfing Challenge: Prime Partitions

Total cycles for examples: 477,918,603

Update 1: Updated to use Lemoine's conjecture.

Update 2: Updated to use the Sieve of Eratosthenes instead of naively finding the primes.

Run with:

python3 assemble.py 52489-prime-partitions.golf
python3 golf.py 52489-prime-partitions.bin x=<INPUT>

Example run:

$ python3 golf.py 52489-prime-partitions.bin x=10233
5
5
10223
Execution terminated after 194500 cycles with exit code 0.

Cycle count for example input:

Input    Cycles
9        191
12       282
95       1,666
337      5,792
1023749  21,429,225
20831531 456,481,447

We consider the first (N+1)*8 bytes of the heap, to be an array containing N+1 64-bit values. (As the heap is limited in size, this will only work for N < 2^57). The value of the entry at i*8 indicates wether i is a prime:

Value Description
-1    Not a prime
0     Unknown
1     The largest prime found
n > 1 This is a prime and the next prime is n

When we are done building the array it will look like [-1, -1, 3, 5, -1, 7, -1, 11, -1, -1, -1, 13, ...].

We use the Sieve of Eratosthenes to build the array.

Next the program does the following in pseudo-code:

if is_prime(x):
    print x
else:
    if is_even(x):
        for p in primes:
            if is_prime(x - p):
                print p, x - p
                exit
    else:
        if is_prime(x - 2):
            print 2, x - 2
        else:
            for p in primes:
                if is_prime(x - 2 * p):
                    print p, p, 2 * p
                    exit

This is guaranteed to work because of Lemoine's conjecture and Goldbach's weak conjecture. Lemoine's conjecture hasn't be proven yet, but it's probably true for numbers below 2^57.

    call build_primes

    mov q, x
    call is_prime

    jnz print_prime, a

    and b, x, 1
    jz find_pair, b

    # Check if x - 2 is a prime
    sub q, x, 2
    call is_prime
    jnz print_prime_odd2, a

# Input: x, b
find_pair:
    mov p, 2
find_pair_loop:
    mov d, p
    jz find_pair_even, b

    add d, d, p

find_pair_even:
    sub q, x, d

    call is_prime
    jnz print_prime2_or_3, a

    shl i, p, 3
    lw p, i
    jmp find_pair_loop

print_prime2_or_3:
    jz print_prime2, b

    mov x, p
    call write_int_ln

print_prime2:
    mov x, p
    call write_int_ln

    mov x, q
    call print_prime

print_prime_odd2:
    mov p, 2
    call print_prime2

print_prime:
    call write_int_ln
    halt 0

# Input: x
# Memory layout: [-1, -1, 3, 5, -1, 7, -1, 11, ...]
# x: max integer
# p: current prime
# y: pointer to last found prime
# i: current integer
build_primes:
    sw 0, -1
    sw 8, -1
    sw 16, 1
    mov y, 16

    mov p, 2

build_primes_outer:
    mulu i, r, p, p
    jnz build_primes_final, r

    geu a, i, x
    jnz build_primes_final, a

build_primes_inner:
    shl m, i, 3
    sw m, -1

    add i, i, p

    geu a, i, x
    jz build_primes_inner, a

build_primes_next:
    inc p
    shl m, p, 3
    lw a, m
    jnz build_primes_next, a

    sw y, p
    mov y, m
    sw y, 1

    jmp build_primes_outer

build_primes_final:
    inc p
    geu a, p, x
    jnz build_primes_ret, a

    shl m, p, 3
    lw a, m
    jnz build_primes_final, a

    sw y, p
    mov y, m
    sw y, 1

    jmp build_primes_final

build_primes_ret:
    ret

# Input: q
# Output: a
is_prime:
    shl m, q, 3
    lw a, m
    neq a, a, -1
    ret a

write_int:
    divu x, m, x, 10
    jz write_int_done, x
    call write_int
write_int_done:
    add m, m, ord("0")
    sw -1, m
    ret

write_int_ln:
    call write_int
    mov m, ord("\n")
    sw -1, m
    ret


05AB1E, 12 bytes
Code:
vDNúsÀ}\».B∞

Uses the 05AB1E encoding. Try it online!
Explanation:
v     }        # Length input times, do.. (N = iteration count)
 DNú           #   Duplicate and prepend N spaces
    sÀ         #   Swap and rotate one to the left
       \       # Discard the top of the stack
        »      # Join the stack by newlines
         .B    # Pad with spaces into a rectangle
           ∞   # Mirror the string


Haskell, 220 characters

import Data.Map;f""""=[empty]
f('{':b)d=[insert k m b|(k,('}':a))<-lex b,(m,c)<-[splitAt n d|n<-[0..length d]],b<-f a c,notMember k b||b!k==m]
f(x:b)(y:d)|x==y=f b d;f _ _=[];format1 x y=elems$mapKeys((0+).read)$f x y!!0

Breaks if you use multiple representations for the same pattern ({1} vs {01}) - doesn't enforce their equality, discarding matches for all but one representation instead.

19 characters can be saved by omiting mapKeys((0+).read)$ if proper ordering of matches above 10 patterns doesn't matter, or if padding to the same length may be required, or if string ordering of patterns is acceptable. In any case, if a pattern is omitted from the first argument, it is omitted from the result as well.

Removing !!0 from the end makes format1 return the list of all solutions, rather than just the first one.

before golfing:

import Data.Map
import Control.Monad

cuts :: [a] -> [([a],[a])]
cuts a=[splitAt n a | n <- [0..length a]]

f :: String -> String -> [Map String String]
-- empty format + empty parsed = one interpretation with no binding
f "" "" = [empty]
-- template-start format + some matched = branch search
f ('{':xs) ys = do
    let [(key, '}':xr)] = lex xs
    (match, yr) <- cuts ys
    b <- f xr yr
    guard $ notMember key b || b!key == match
    return $ insert key match b
-- non-empty format + matching parsed = exact match
f (x:xs) (y:ys) | x == y = f xs ys
-- anything else = no interpretation
f _ _ = []

deformat :: String -> String -> [String]
deformat x y = elems $ mapKeys ((0+).read) $ head $ f x y


Javascript (116)

Black magics here ! Gives a result in few milliseconds.
Only elementary math functions used : ln, pow, exponential

x=9;n=prompt(M=Math);for(i=1e4;i--;)x+=(n/M.exp(-x)/M.pow(x,x-.5)/2.5066/(1+1/12/x+1/288/x/x)-1)/M.log(x);alert(x-1)

Too bad LaTeX is not supported on codegolf but basically, I coded a newton solver for f(y)=gamma(y)-n=0 and x=y-1 (because x! is gamma(x+1)) and approximations for gamma and digamma functions.

Gamma approximation is Stirling approximation
Digamma approximation use Euler Maclaurin formula
The digamma function is the derivative of gamma function divided by gamma function : f'(y)=gamma(y)*digamma(y)

Ungolfed :

n = parseInt(prompt());
x = 9; //first guess, whatever but not too high (<500 seems good)

//10000 iterations
for(i=0;i<10000;i++) {

  //approximation for digamma
  d=Math.log(x);

  //approximation for gamma
  g=Math.exp(-x)*Math.pow(x,x-0.5)*Math.sqrt(Math.PI*2)*(1+1/12/x+1/288/x/x);

  //uncomment if more precision is needed
  //d=Math.log(x)-1/2/x-1/12/x/x+120/x/x/x/x;
  //g=Math.exp(-x)*Math.pow(x,x-0.5)*Math.sqrt(Math.PI*2)*(1+1/12/x+1/288/x/x-139/51840/x/x/x);

  //classic newton, gamma derivative is gamma*digamma
  x-=(g-n)/(g*d);
}

alert(x-1);

Test cases :

10 => 3.390062988090518
120 => 4.99999939151027
720 => 6.00000187248195
40320 => 8.000003557030217
3628800 => 10.000003941731514


Play a valid chess move, given a board on stdin

I'm not complaining about upvotes, but to be fair... my solution here isn't actually all that great. Ugoren's is better, apart from lacking unicode support. Be sure to look at all the answers before voting, if you've come across this question only now!Anyway.
Haskell, 1074 bytes (without castling)

χ=w⋈b;w="♙♢♤♔♕♖♗♘";b="♟♦♠♚♛♜♝♞"
μ=t⤀ζ++((\(x,y)->(x,-y))⤀)⤀μ;q c|((_,m):_)<-((==c).fst)☂(χ⋎μ)=m
t(x:y:l)=(d x,d y):t l;t _=[];d c=fromEnum c-78
ζ=["NM","NL","MMOM","MMMNMONMNOOMONOO",σ⋈δ,σ,δ,"MLOLPMPOOPMPLOLM"]
σ=l>>=(\c->'N':c:c:"N");δ=[l⋎l,reverse l⋎l]>>=(>>=(\(l,r)->[l,r]))
l="GHIJKLMOPQRSTU"
α c|c∊"♢♤"='♙'|c∊"♦♠"='♟'|c∊χ=c;π('♙':_)=6;π _=1
(⋎)=zip;(⤀)=map;(∊)=elem;(✄)=splitAt;(☂)=filter;(⋈)=(++)
φ r@(x,y)p a
 |x>7=φ(0,y+1)p a
 |y>7=[]
 |c<-a✠r=(c⌥r)p a y⋈φ(x+1,y)p a
(c⌥r)p a y
 |c==p!!0=(a☈r)c χ++const(y==π p)☂(a☈r)(p!!1)χ++(a☈r)(p!!2)('…':w)
 |c∊p=(a☈r)c χ
 |True=[]
a✠(x,y)=a!!y!!(x*2);o(x,y)=x>=0&&x<8&&y>=0&&y<8
(n➴a)(x,y)|(u,m:d)<-y✄a,(l,_:r)<-(x*2)✄m=u⋈(l⋈(n:r):d)
(a☈r@(x,y))c b=(α c➴('…'➴a)r)⤀((\r->o r&&not((a✠r)∊b))☂((\(ξ,υ)->(x+ξ,y+υ))⤀q c))
main=interact$unlines.uncurry((⋈).zipWith((⋈).(:" ║"))['8','7'..]
 .head.((all(any('♔'∊)).φ(0,0)b)☂).φ(0,0)w.(drop 3⤀)).(8✄).lines

Try it online!

When you have GHC installed (for instance as part of the Haskell platform) you can do just
$ runhaskell def0.hs < examplechessboard.txt
8 ║♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… ♘ … … ♟ … … …
4 ║… … … … … … … …
3 ║… … … … … … … …
2 ║♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙
1 ║♖ … ♗ ♕ ♔ ♗ ♘ ♖
——╚═══════════════
—— a b c d e f g h


Python, 53 bytes

f=lambda n,i=1:n*[f]and[i]+f(n-1,2*i)+i%2*f(n-1,i-~i)

Try it online!

The recursive function generates the sorted list as a pre-order walk down this tree (example with n=4):

      1
     / \
    2   3
   /   / \
  4   6   7
 /   /   / \
8   12  14  15

1 2 4 8 3 6 12 7 14 15

Left branches double the value, and right branches do i->i*2+1 and exist only for odd i. So, the pre-order walk for non-leaves is T(i)=[i]+T(i*2)+i%2*T(i*2+1).

The tree terminates at depth n, where n is the input. This is achieved by decrementing n with each step down and stopping when it is 0.

An alternative strategy would be to terminate on values that i exceeds 2**n, rather than tracking depth. I found this to be one byte longer:

f=lambda n,i=1:2**n/i*[f]and[i]+f(n,2*i)+i%2*f(n,i-~i)
f=lambda n,i=1:[f][i>>n:]and[i]+f(n,2*i)+i%2*f(n,i-~i)


Python 3, 88 \$\cdots\$ 54 43 bytes

lambda l:len({abs(sum(l)/4-z)for z in l})<2

Try it online!

How

Calculates the distances from the quadrilateral's centre of mass to all of its vertices and tests if they're equal.

Input The four vertices as a sequence of complex numbers in any order.
Output True/False


Compress 8 bits to 6 when certain bit patterns will never occur

Python, 60 bytes

l=[n^170for n in range(256)if n&n*2<1]
l.index,l.__getitem__

Try it online!

l.index compresses and l.__getitem__ decompresses. We just make a list l of all valid patterns as 8-bit numbers, except we ignore wrapping around, which still leaves 55 options which fits in 6 bits.

A useful idea is that if we flip the bits at even positions, which ^170 does, then the condition just becomes "no two 1's are (cyclically) adjacent". This is easy to check without wrapping around using the bit condition n&(n*2)==0, or shorter, n&n*2<1.

Fibonacci numbers

Binary strings with no adjacent ones have interesting connections to Fibonacci numbers. The number of such 8-bit numbers is 55, a Fibonacci number, following the general result. Moreover, Zeckendorf's Theorem tell us that each number can be uniquely expressed in the Fibonacci base without using a pair of adjacent ones, that is as a sum of distinct Fibonacci numbers without two consecutive ones, as these can be merged into the next Fibonacci number.

Perhaps a base conversion to the Zeckendorf Representation can be used for a less brute-force answer than the one here. We've had challenges to convert from and to the Zeckendorf representation, which could be used as the basis of a decoder-encoder pair.

Bonus: 64 bytes

For imaginary internet points, we can tweak the algorithm to accounts for cyclically adjacent ones, so as to limit the compression to 48 valid bit patterns from 55. We do this by modifying the bit check to n&n*2%255<1, at the cost of 4 extra bytes.

64 bytes

l=[n^170for n in range(256)if n&n*2%255<1]
l.index,l.__getitem__

Try it online!

The modulo 255 changes the bit-shift n*2 to a cyclic shift

abcdefgh -> bcdefgha

by moving the post-doubling place value of 256*a to just a. This is, except for n=255, which where n*2%255 is zero, giving a false positive at 255^170=85. But, since the bonus for imaginary internet points gives use one spare slot, with 48 slots for 47 values, we can just live with this hole.


CJam, 7 bytes

lg'"/5=

Test run

$ alias cjam
alias cjam='java -jar ~/.local/share/cjam-0.6.5.jar'
$ cjam unshorten.cjam <<< goo.gl/HaE8Au; echo
https://codegolf.stackexchange.com/
$ cjam unshorten.cjam <<< goo.gl/IfZMwe; echo
https://stackoverflow.com/
$ cjam unshorten.cjam <<< goo.gl/JUdmxL; echo
https://chat.stackexchange.com/rooms/240/the-nineteenth-byte

How it works

lg reads a line from STDIN and makes a GET request to that URL. The shortened URL issues a 301 redirect, which CJam doesn't follow. For the first test case, this pushes

<TITLE>Moved Permanently</TITLE>

Moved Permanently

The document has moved here.

on the stack. Finally, '"/ splits at double quotes, and 5= gets the sixth chunk. Output is implicit.


Python - 90 75 + 50 = 125
Use lower case letters.
for l in input():
 a=ord(l)-96
 if a<0:a=0
 print("⠀⠁⠃⠉⠙⠑⠋⠛⠓⠊⠚⠅⠇⠍⠝⠕⠏⠟⠗⠎⠞⠥⠧⠺⠭⠽⠵"[a],end="")

One-liner (thanks to ɐɔıʇǝɥʇuʎs)
for l in input():print("⠀⠁⠃⠉⠙⠑⠋⠛⠓⠊⠚⠅⠇⠍⠝⠕⠏⠟⠗⠎⠞⠥⠧⠺⠭⠽⠵"[max(0,ord(l)-96)],end="")


LOGO, 18 bytes

[map[?+sin 90*#]?]

There is no "Try it online!" link because all online LOGO interpreter does not support template-list.

That is a template-list (equivalent of lambda function in other languages).

Usage:

pr invoke [map[?+sin 90*#]?] [-4 3 0 1 7 9 8 -2 11 -88]

(invoke calls the function, pr prints the result)

prints [-3 3 -1 1 8 9 7 -2 12 -88].

Explanation (already pretty understandable):

 map[?+sin 90*#]?       map a function over all the items of the input
              #         the 1-based index of the element in the input
       sin 90*#         equal to the required wave
     ?                  looping variable
     ?+sin 90*#         add the wave to the input


Python, 193 168
Should work for any valid triangle...
def h(a,A,b,B,c,C):
 if A==B:b,B,c,C=c,C,b,B
 m=(a-b)/(B-A)
 return m,C-m*c
def f(a,A,b,B,c,C):
 m,q=h(a,A,b,B,c,C)
 k,z=h(c,C,b,B,a,A)
 x=(q-z)/(k-m)
 return (x,k*x+z)


Java, heuristic favouring the vertex which induces the largest graph: 1825 1855 1873

The code below runs in under 10 minutes and finds the following path:

[wad, wadis, dis, dismay, may, mayfly, flywheels, elsewhere, erecting, ingratiate, ateliers, ersatzes, zest, esthetic, tickled, ledger, germicide, idealizes, zestful, fulling, ingrains, institute, uterine, ineptness, essaying, ingeniously, slyness, essences, cessations, onshore, ores, resoundingly, glycerine, inertness, essay, say, saying, ingenuous, ousted, tediously, sly, slyest, estrogen, genuflecting, ingestion, ionizer, zeros, roses, sesames, mes, meshed, hedonist, isthmuses, sesame, amending, ingredient, entrapment, enthuses, session, ionosphere, erectness, essayist, isthmus, mustaches, hesitatingly, glycogen, generation, ions, onset, settable, blew, lewder, deriding, ingratiates, testicles, lessen, sensitization, ionization, ionizing, ingratiating, ingenious, ouster, terrorizing, ingest, estranges, gesticulating, ingrates, testis, tissue, sue, suede, edelweiss, issuing, ingraining, ingrown, owner, nerdiest, estimation, ionospheres, rescue, cue, cueing, ingesting, ingot, got, gotten, tensor, sorrowing, ingratiated, tedious, ousting, ingratiatingly, glycerin, ringside, identifiable, bleariest, ester, terminological, calibrator, torrent, entraps, apse, pseudonym, nymphomania, niacin, cinema, emailed, led, ledges, gesticulates, testicle, clement, entail, ail, ailment, enter, terrains, inspires, restaurateur, euros, rosiest, estimates, tester, termite, iterator, torture, urethras, raspiest, estimator, tore, oregano, anointment, enthuse, useful, fulfil, filmstrip, riposte, stereotyped, pedicure, urea, readmits, itself, elf, elfin, finagles, lesbians, answerable, bleat, eatery, erythrocytes, testosterone, one, ones, nest, esteemed, medicine, inextricable, blessed, sediment, entry, try, tryout, outsources, cesarians, answered, redressed, seducer, cervical, calumniates, test, establishment, entombment, enthusiastic, tickles, lessens, ensemble, blemishes, hesitant, antic, tick, ickiest, estimable, blemished, hedgehog, hogan, gantlet, letdown, own, ownership, hippest, estates, testates, testiest, establishes, hes, hesitates, testable, bleakest, esthetes, testament, entice, iceberg, erg, ergonomic, microscope, operatives, vestibules, lesser, serenade, adenoidal, dales, lest, estrangement, entrap, raptures, resourceful, fulsome, omen, menswear, earthliest, established, hedges, gestates, testy, styes, yeshivot, voter, terrible, blender, derides, descent, enticed, cedillas, lass, assailable, bleacher, hermit, mite, item, temperas, rash, ashtray, rayon, yonder, dermis, mismanage, agendas, dash, ashy, shy, shyster, terrapins, insatiable, bleeder, derives, vestment, entangle, glen, lengthens, ensconced, ceded, deduced, cedars, arsenic, nice, ice, iced, cedar, daredevil, villa, llamas, masseuse, use, useable, bleach, achievable, bleached, hedonistic, tic, ticker, kerchieves, vessel, sell, ell, elliptic, ticket, kettles, lessee, seeps, epsilon, longboat, oath, atherosclerosis, sisterhood, oodles, lesson, sonatas, tassel, selvage, age, agent, entranced, cedes, descender, deranges, gestures, restraint, interment, enthused, seduced, cedilla, llama, amalgam, gamut, mutable, blend, endear, earthy, thymus, mussel, seltzer, zero, erodes, despot, potful, fulfillment, enthrall, allot, lotus, tussle, sledgehammered, redolent, entrapped, pedestal, talk, alkalis, listen, tended, deductible, bleeped, pedigree, reentered, redistribute, uterus, rustproofed, fed, fedora, oranges, gesundheit, either, herdsman, manes, nestles, lessor, sorrowful, fullback, acknowledges, gestured, redoubtable, blended, deduces, cesareans, answer, werewolves, vesper, perseveres, restructures, reside, ideogram, rammed, meddlesome, omens, ensign, ignores, restrains, insolent, entanglement, entrenchment, enticement, entomological, calligraphy, physical, calico, iconoclast, astringent, entertainment, entrant, antennas, nasty, stymie, miens, enslave, averred, redefine, inexorable, blenched, hedgerow, rowboat, oat, oaten, tend, endears, arson, songwriter, terminable, blent, entreaty, atypical, calypso, psoriasis, sister, term, ermine, ineligible, bleaker, kerosene, enema, emancipator, tormentor, torrider, derailment, entertains, instil, tildes, destine, inelegant, anthropomorphic, hiccup, cupolas, lastingly, glycerol, rollback, acknowledgment, entombed, bedridden, denser, servicewomen, menopause, used, sedatives, vesicle, clearinghouse, user, servant, antipodes, descry, crystalline, inexpedient, enthusiast, astonishment, entirety, etymological, calendared, redbreast, astronomer, merinos, nosedove, overpay, pay, paymaster, termagant, antiaircraft, aftercare, ares, resentful, fulcrum, rumpus, pushcart, artiste, stethoscopes, pesetas, taste, steadfast, astride, ides, destitute, utensil, silvan, vanguard, ardent, entryway, waysides, despair, airdrop, ropes, pestered, redder, derangement, entered, redeemed, medullas, lasagnas, nasal, salsas, sashay, hay, haymow, mow, mowed, wedder, derringer, germane, anemic, microfilmed, media, diatom, tomboys, oyster, terminator, toreador, dorsal, salespeople, pleased, sedater, terabit, bitten, tentacle, clergyman, manifesto, stomach, achoo, hoopla, plaza, azalea, leaven, vendor, dormant, antiparticle, cleared, redraft, afterword, ordains, insufficient, entitlement, entomb, ombudsmen, men, mental, tallyhos, hospice, icecap, cape, aperitif, tiffed, fedoras, rasped, pediatric, rickshaw, hawker, keratin, tinctures, reset, setback, acknowledgement, enthronement, entwine, inexact, actor, torpedos, dosed, sedan, dancer, cerebrum, rumple, plea, leach, ache, cheaper, per, periscopes, pestilent, entreat, eater, terser, serape, ape, apes, pesky, skycap, capped, pederast, astuter, terrace, acetaminophen, henchmen, menopausal, saltcellar, lard, ardor, dormice, icebound, underbrush, ushered, redrew, rewound, underclass, assassin, sinew, newscast, astrologer, gerund, undertaken, ken, kens, ensnared, redcap, cappuccinos, nostrum, rum, rumored, redraw, rawhide, identical, calcine, inertia, tiara, arabesque, queerer, reruns, unsold, oldie, diesel, selectmen, mentored, redden, dental, talon, longhand, and, androgen, genome, omelet, lethal, hallucinogenic, nickname, amen, menhaden, denudes, despaired, redevelop, lope, operas, rasp, aspired, redskin, kindergartens, ensnares, resultant, anthropological, callus, lustful, fulcra, crammed, mediocre, crepes, pesticide, ideas, eastbound, under, derrières, respired, rediscovered, redundant, antihero, erode, ode, odes, described, bedevil, villager, gerrymander, deride, ideograph, aphid, hid, hides, describes, besides, despoil, oilskin, kingdom, dominant, ant, antipasti, stiffens, ensured, redeemer, merchant, antiwar, warped, pederasty, stylus, lush, usher, her, hereafter, terrapin, pinnacle, clerical, caliber, bereave, avenger, geriatric, rickshas, haste, stereoscopes, pester, termini, initiator, tortures, restorer, reran, ransomed, medulla, llanos, nostril, rill, illogical, calif, lifer, fervor, vortex, textures, resister, termed, medieval, valor, lord, ordered, rediscover, verbatim, times, mesdames, mescal, caliper, periscope, opera, erasures, restart, artichokes, kestrel, reliant, antebellum, lumbago, agog, goggle, gleeful, fulfill, illustrator, tor, torque, questionnaires, resumed, mediator, tort, orthodoxy, oxymora, oratorio, riot, iotas, taster, terrific, fiche, checkpoint, interloper, perfumes, mesas, sassafras, rasher, heraldry, drywall, all, allergens, ensnare, area, rearm, armchair, airman, manufactures, resurface, acerbic, bicycle, cleverer, rerun, runt, untidy, idyllic, lichens, ensures, resend, endemic, microchip, hippopotamus, muscatel, telecast, astronaut, autopilot, lot, loth, other, heros, rosin, single, gleamed, mediaeval, valet, lettered, redound, underside, ideological, calliper, perihelia, liaison, sonic, nicknames, messenger, germicides, descendant, antigen, genital, tall, allergen, gentleman, mangos, gossipped, pedicures, resistant, antlered, redeveloped, pedagogical, calligrapher, heroins, inside, idea, deafen, fen, fencer, cerebra, bravuras, rascal, calculus, lusher, herbivores, resins, instill, illicit, citric, ricochet, heterodoxy, oxygen, generic, rice, icebox, box, boxcar, cartography, physique, quell, ellipsis, sis, sisal, sallow, lowbrow, rowel, well, elliptical, calf, alfresco, scow, cow, cowboy, boy, boyfriend, end, endeared, red, redesign, ignoramus, musket, kettledrum, rump, umped, pedlar, larvas, vassal, salmonellas, last, astronomical, calfskin, kingfisher, hereupon, ponchos, hospital, talisman, mantel, telethon, honcho, chomped, pedant, antitoxins, instant, antipastos, tossup, superintend, endangered, redskins, instigator, torpor, portico, icon, conquistador, dormer, merganser, seraphic, hiccuped, pedagogue, guerrillas, laser, sera, eraser, seraph, aphasic, sickbed, bed, bedsores, resign, ignorant, anthropocentric, richer, herdsmen, menu, enures, resuscitator, tornado, ado, adobe, obeisant, anthill, illegal, gallon, longshoremen, menace, ace, acetylene, enemas, mas, mascot, cot, cotton, tonsures, restores, result, ultraviolet, letterbox, boxer, xerography, physiological, calmer, merchantmen, mentor, torus, russet, settee, teenager, gerbil, billfold, old, olden, denatures, resubmit, mitten, ten, tenon, nonchalant, antique, queasy, asymmetric, ricksha, shanghai, haircut, cutups, upsides, descriptor, torpid, pidgin, gins, instep, tepee, peeper, perturb, urbane, anemia, miasmas, mascaras, raspy, spy, spyglass, assures, resonator, tortilla, llano, anon, nontechnical, calabash, ashram, rampart, arthropod, podia, diagram, ramp, amp, amphitheatres, resistor, tortillas, lasagna, gnat, natal, talc, alcoholic, licensee, seemed, medical, calm, almanac, nacho, choreography, phylum, lumbar, barman, mannequins, insures, respires, resound, underarm, armatures, resides, desideratum, tumult, ultrasound, underdog, dogcatcher, herald, alderwoman, mandarins, insecticides, desires, respirator, torrid, rid, rides, descant, anticlimax, maximum, mum, mummer, meringue, guesser, sermon, monogram, ramrod, rodeo, deodorant, antelopes, peso, esophagus, gusset, setups, upshot, hotel, telescope, open, penicillin, lingos, gossip, sip, siphon, honor, normal, maltreat, eaten, tenet, nether, herpes, pesticides, descend, endow, downfall, alleyway, way, waylay, layman, manicures, reshuffle, flea, lea, leash, ashen, henchman, mandolin, linchpins, inscribes, bestow, townspeople, plectrum, rumbas, baste, sternum, numb, umbilici, icicle, cleaver, vertebra, brains, insouciant, antidepressant, anthem, hemoglobin, binocular, largos, gossamer, mermaid, aid, aides, desperado, adopt, opt, optima, imam, mambos, bosun, sun, sunspot, potpourris, risky, sky, skyscraper, perturbed, bedraggle, glee, lee, leech, echo, choreographer, heraldic, dictum, tumid, midday, day, daybed, bedsides, desktop, topknot, notepaper, periodical, calendar, dare, areas, easel, selfsame, amebas, basins, ins, insulin, linnet, nettlesome, omegas, gasp, aspartame, amend, endures, researcher, herbal, balsas, sass, assault, ultimatum, tumor, mortgagor, gores, resort, orthopaedic, dictatorship, hipper, person, sonar, narc, arc, archduke, ukelele, elegant, anther, hereabout, outfox, fox, foxtrot, rotogravures, restaurant, antechamber, beret, retriever, verbena, enamor, morsel, sellout, outmaneuver, vertical, call, allergenic, niche, chessman, mandolins, insipid, pidgins, install, allures, rescind, indignant, antithetical, calicos, cosmonaut, auto, utopia, piano, another, heretical, calk, alkali, alibi, ibis, bistro, troupe, upend, endorser, serviceman, mandarin, rind, inductee, teepee, pee, peekaboo, bootstrap, rape, apertures, resin, singular, larval, valiant, antiperspirant, antipasto, stop, topical, calisthenic, nicer, cervix, vixen, xenophobic, bicep, cephalic, licit, citizenship, hippopotami, amigos, gospel, pellet, letups, upstart, artificer, cerebellum, lumberman, manic, nicknamed, medic, dickie, kielbasas, sash, ash, ashcan, cannon, nonskid, kid, kidnaper, perjures, resolver, vernacular, larkspur, puree, reefer, ferret, retains, insofar, far, fart, artisan, sandbag, bagel, gelatin, tinsel, selectman, manacle, clever, versus, sustains, inscribed, bedpan, pandemic, microprocessor, sorbet, bet, betcha, char, harem, remodel, deli, elicit, citadel, deliver, verandas, dashikis, kisser, servicemen, menthol, holiday, daydreamer, merchantman, manikins, insane, anew, newsprint, interwove, overreach, achieve, even, venom, nomad, mad, madrigal, gala, alarm, armpit, pitchman, manor, northbound, underbid, bidet, detox, toxemia, miasma, smarten, tenderloins, insult, ultra, travel, velvet, veteran, random, domino, inopportune, uneconomic, microbes, bestir, tiro, ironware, arena, enamel, melodramas, mastodon, don, donut, nut, nutmeg, meg, megalopolis, lissom, sombre, breathe, therefrom, romper, performer, merman, mangrove, overshadow, downcast, astir, tiros, rostra, trachea, heaven, ventricle, clergywoman, maneuver, verbal, ballad, ladyship, hippie, pie, piebald, alderman, manatee, teethe, thereupon, poncho, choicer, ceramic, microscopic, picayune, uneaten, tendon, donor, northeast, astound, underpass, assessor, sorghum, hum, human, mantra, trainee, needlepoint, interplay, laywoman, mannikin, kinsman, mantillas, lassie, sieve, ever, verdigris, risen, sensor, sorrel, relabel, belabor, borsch, schlep, leprechauns, unsnap, nap, napkin, kin, kingpin, pinkeye, eyeglass, assemblyman, manikin, kingship, hip, hippos, postpartum, tumbrel, relic, lichee, heehaw, haw, hawser, servicewoman, many, anyhow, howsoever, vertex, text, extra, trap, rap, rapper, periwig, wigwag, wag, wagon, gonorrhea, heave, aver, vermin, minesweeper, perplex, lexicon, congas, gastronomic, microfiche, cheapen, pentathlon, longhair, air, aircraft, aft, aftertaste, stem, tempos, postwar, war, wart, article, clear, earshot, hotshot, hotbed, bedlam, lam, lambkin, kindergarten, tenser, serum, rumor, mortar, tarmac, macabre, breech, echos, hostel, telescopic, pickerel, relay, laypeople, pleas, east, astronomic, micra, crackpot, pot, potato, atom, tombed, bedbug, bugaboo, bootleg, leg, legato, atop, topple, plethora, orangutang, angora, orangutan, tan, tandem, democrat, rat, rattan, tang, angry, gryphon, honeybee, bee, beeswax, waxen, xenon, nonplus, lustre, trellis, lisle, sleepwear, earwig, wig, wigwam, wampum, pummel, melanomas, massacre, cretin, tin, tint, interviewee, wee, weeper, persimmon, monsignori, origin, gingham, ham, hamper, pericardia, diarrhea, heartthrob, rob, robes, besom, sombreros, rosebud, bud, budgerigar, garret, retrodden, denim, nimbus, bus, bushel, helmet, metaphor, horsefly, flypaper, peritonea, near, ear, earlobes, bestowal, wall, allay, layout, outlast, astrakhan, handicapper, perusal, saltpetre, tremor, moribund, undercut, cut, cutoff, off, offal, falcon, con, consul, sultan, tannin, ninepin, pinball, allegro, grommet, metro, trot, rot, rotten, tenpin, pineapple, plectra, transit, sitar, tar, taro, arousal, salmon, moneybag, bagpipe, ipecac, cache, checkout, outrun, runaround, undersea, sea, sear, earache, cherub, rub, rubicund, underpin, pin, pint, intagli, glib, lib, libel, bellyache, cherubim, bimbos, bosuns, unsound, undertow, tow, towel, wellington, ton, tonsil, silicon, concoct, octet, tetrahedra, drachmae, maestri, tripos, possum, sum, sumac, macro, crocus, custom, tom, tomcat, catsup, sup, superstar, tarpaulin, linchpin, pinpoint, intercom, comet, met, metacarpus, pussycat, catastrophe, phenomenon, nonverbal, ballpoint, interurban, bani, animal, malt, altar, tartar, tarot, rotund, undergrad, radio, diocesan, sandbar, bar, barren, renewal, walkout, outstrip, ripen, pen, pencil, cilantro, trout, outran, rancor, corncob, cob, cobra, bra, brag, rag, ragas, gas, gasohol, holdout, output, put, putsch, schwas, was, waste, stereo, reoccur, cur, curb, urban, ban, bantam, tam, tamp, ampul, pullout, outwit, wit, withal, halo, alohas, hasp, asparagus, gusto, stove, overlap, lapel, pelvis, visit, sit, sitcom, compendia, diadem, demigod, god, goddam, dam, dampen, pennon, non, noncom, compel, pelican, cancan, can, cancel, celesta, starlit, lit, litmus, muscat, cat, catnap, naphtha, than, handcar, carpel, pellagra, grammar, mar, mariachi, chichi, chi, chimp, imp, impel, pelvic, vicar, car, caribou, bourgeoisie, siesta, stab, tab, tabu, abut, but, butterfat, fat, fathom, homespun, pun, puns, unsheathe, the, theorem, remove, overtax, tax, taxicab, cab, cabal, balsam, sambas, basal, salamis, missal, salt, altho, tho, thou, housebound, underground, underclassman, man, mannikins, insectivores, resonant, antelope, operator, torn, ornamental, tallow, low, lowered, reddens, enshrine, inefficient, entertainer, nerves, vestiges, gesturing, ingested, tediousness, essentials]

Core ideas

In Approximating longest directed paths and cycles, Bjorklund, Husfeldt, and Khanna, Lecture Notes in Computer Science (2004), 222-233, the authors propose that in sparse expander graphs a long path can be found by a greedy search which selects at each step the neighbour of the current tail of the path which spans the largest subgraph in G', where G' is the original graph with the vertices in the current path deleted. I'm not sure of a good way to test whether a graph is an expander graph, but we're certainly dealing with a sparse graph, and since its core is about 20000 vertices and it has a diameter of only 15 it must have good expansion properties. So I adopt this greedy heuristic.

Given a graph G(V, E), we can find how many vertices are reachable from each vertex using Floyd-Warshall in Theta(V^3) time, or using Johnson's algorithm in Theta(V^2 lg V + VE) time. However, I know that we're dealing with a graph which has a very large strongly connected component (SCC), so I take a different approach. If we identify SCCs using Tarjan's algorithm then we also get a topological sort for the compressed graph G_c(V_c, E_c), which will be much smaller, in O(E) time. Since G_c is a DAG, we can compute reachability in G_c in O(V_c^2 + E_c) time. (I have subsequently discovered that this is hinted at in exercise 26-2.8 of CLR).

Since the dominant factor in the running time is E, I optimise it by inserting dummy nodes for the prefixes/suffixes. So rather than 151 * 64 = 9664 edges from words ending -res to words starting res- I have 151 edges from words ending -res to #res# and 64 edges from #res# to words starting res-.

And finally, since each search takes about 4 minutes on my old PC, I try to combine the results with previous long paths. This is much faster, and turned up my current best solution.

Code

org/cheddarmonk/math/graph/Graph.java:

package org.cheddarmonk.math.graph;

import java.util.Set;

public interface Graph<V> {
    public Set<V> getAdjacent(V node);
    public double getWeight(V from, V to);
}

org/cheddarmonk/math/graph/MutableGraph.java:

package org.cheddarmonk.math.graph;

import java.util.*;

public class MutableGraph<V> implements Graph<V> {
    private Map<V, Map<V, Double>> edgesBySource = new HashMap<V, Map<V, Double>>();

    public void addEdge(V from, V to, double weight) {
        if (!edgesBySource.containsKey(to)) edgesBySource.put(to, new HashMap<V, Double>());
        Map<V, Double> e = edgesBySource.get(from);
        if (e == null) edgesBySource.put(from, e = new HashMap<V, Double>());
        if (e.containsKey(to)) throw new IllegalArgumentException("There is already an edge between the vertices");
        e.put(to, weight);
    }

    @Override
    public Set<V> getAdjacent(V node) {
        Map<V, Double> e = edgesBySource.get(node);
        if (e == null) throw new IllegalArgumentException("node doesn't appear to be in the graph");
        return Collections.unmodifiableSet(e.keySet());
    }

    @Override
    public double getWeight(V from, V to) {
        Map<V, Double> e = edgesBySource.get(from);
        if (e == null) throw new IllegalArgumentException("from doesn't appear to be in the graph");
        if (!edgesBySource.containsKey(to)) throw new IllegalArgumentException("to doesn't appear to be in the graph");

        Double c = e.get(to);
        return c == null ? 0 : c.doubleValue();
    }
}

org/cheddarmonk/math/graph/StronglyConnectedComponents.java:

package org.cheddarmonk.math.graph;

import java.util.*;

/**
* A helper class for finding the strongly connected components of a graph using Tarjan's algorithm.
* http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
*/
public class StronglyConnectedComponents<V> {
    private final Graph<V> g;
    private List<Set<V>> topologicallySortedSccs = new ArrayList<Set<V>>();

    private final LinkedList<V> S = new LinkedList<V>();
    private final Set<V> S2 = new HashSet<V>();
    private final Map<V, Integer> index = new HashMap<V, Integer>();
    private final Map<V, Integer> lowlink = new HashMap<V, Integer>();

    private StronglyConnectedComponents(Graph<V> g) {
        this.g = g;
    }

    private void strongConnect(V v) {
        int idx = index.size();
        index.put(v, idx);
        lowlink.put(v, idx);

        S.push(v);
        S2.add(v);

        for (V w : g.getAdjacent(v)) {
            if (!index.containsKey(w)) {
                strongConnect(w);
                if (lowlink.get(w) < lowlink.get(v)) {
                    lowlink.put(v, lowlink.get(w));
                }
            }
            else if (S2.contains(w)) {
                if (index.get(w) < lowlink.get(v)) {
                    lowlink.put(v, index.get(w));
                }
            }
        }

        if (lowlink.get(v).equals(index.get(v))) {
            Set<V> scc = new HashSet<V>();
            V w;
            do {
                w = S.pop();
                S2.remove(w);
                scc.add(w);
            } while (!w.equals(v));

            topologicallySortedSccs.add(scc);
        }
    }

    public static <V> List<Set<V>> analyse(Graph<V> g, Set<V> sources) {
        if (g == null) throw new IllegalArgumentException("g");

        StronglyConnectedComponents<V> scc = new StronglyConnectedComponents<V>(g);
        for (V v : sources) {
            if (!scc.index.containsKey(v)) {
                scc.strongConnect(v);
            }
        }

        return scc.topologicallySortedSccs;
    }
}

org/cheddarmonk/ppcg/PPCG.java:

package org.cheddarmonk.ppcg;

import java.io.*;
import java.util.*;
import org.cheddarmonk.math.graph.*;

public class PPCG44922 {
    private static final String path = "/usr/share/dict/words";
    private static Set<String> allWords;
    private static Graph<String> fullGraph;

    public static void main(String[] args) {
        loadGraph();

        Random rnd = new Random();
        rnd.setSeed(8104951619088972997L);
        List<String> a = search(rnd);
        rnd.setSeed(-265860022884114241L);
        List<String> b = search(rnd);
        List<String> chain = spliceChains(a, b);
        System.out.println(chain.size());
        System.out.println(chain);
    }

    private static List<String> search(Random rnd) {
        List<String> chain = new ArrayList<String>();
        chain.add(selectOptimalReachabilityCount(fullGraph, allWords, rnd));
        while (true) {
            String tail = chain.get(chain.size() - 1);
            FilteredGraph g = new FilteredGraph(chain);

            // We know that tail only has one successor, so skip ahead.
            Set<String> candidates = new HashSet<String>(fullGraph.getAdjacent(suffix(tail)));
            candidates.removeAll(chain);
            if (candidates.isEmpty()) break;

            chain.add(selectOptimalReachabilityCount(g, candidates, rnd));
        }

        Iterator<String> it = chain.iterator();
        while (it.hasNext()) {
            if (it.next().charAt(0) == '#') it.remove();
        }
        return chain;
    }

    private static List<String> spliceChains(List<String> a, List<String> b) {
        Set<String> intersect = new HashSet<String>(b);
        intersect.retainAll(a);
        if (intersect.isEmpty()) return null;

        // Splice the longest bits. To avoid cycles, we look for intersection points which have the same set of reached intersection points.
        // Thus to get from one to the next we can take either route without violating the unique occurrence of each element in the spliced chain.
        Set<String> left = new HashSet<String>();
        Set<String> right = new HashSet<String>();
        List<String> newChain = new ArrayList<String>();

        // NB We assume that either a(0) and b(0) are the same or neither is in intersect.
        // This is a safe assumption in practice because they're both "wad".
        int idxA = 0, idxB = 0, nextA = 0, nextB = 0;
        while (idxA < a.size()) {
            nextA++;
            while (nextA < a.size() && !intersect.contains(a.get(nextA))) nextA++;
            String tailA = nextA < a.size() ? a.get(nextA) : "";
            left.add(tailA);

            nextB++;
            while (nextB < b.size() && !intersect.contains(b.get(nextB))) nextB++;
            String tailB = nextB < b.size() ? b.get(nextB) : "";
            right.add(tailB);

            if (left.equals(right) && tailA.equals(tailB)) {
                // We take the longer of idxA to nextA-1 or idxB to nextB - 1.
                if (nextA - idxA > nextB - idxB) newChain.addAll(a.subList(idxA, nextA));
                else newChain.addAll(b.subList(idxB, nextB));

                idxA = nextA;
                idxB = nextB;
            }
        }

        if (new HashSet<String>(newChain).size() == newChain.size()) return newChain;
        throw new IllegalStateException();
    }

    private static void loadGraph() {
        Set<String> words = new HashSet<String>();
        Set<String> prefixes = new HashSet<String>();
        Set<String> suffixes = new HashSet<String>();
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path), "UTF-8"));
            String line;
            while ((line = br.readLine()) != null) {
                if (line.length() >= 3) {
                    words.add(line);
                    prefixes.add(prefix(line));
                    suffixes.add(suffix(line));
                }
            }
            br.close();
        }
        catch (IOException ioe) {
            throw new RuntimeException(ioe);
        }

        // Filter down to a core with decent reachability.
        prefixes.retainAll(suffixes);
        MutableGraph<String> g = new MutableGraph<String>();
        Iterator<String> it = words.iterator();
        while (it.hasNext()) {
            String line = it.next();
            if (prefixes.contains(prefix(line)) && prefixes.contains(suffix(line))) {
                // In the interests of keeping the number of edges down, I insert fake vertices.
                g.addEdge(prefix(line), line, 1);
                g.addEdge(line, suffix(line), 1);
            }
            else it.remove();
        }

        fullGraph = g;
        allWords = Collections.unmodifiableSet(words);
    }

    private static String prefix(String word) {
        return "#" + word.substring(0, 3) + "#";
    }

    private static String suffix(String word) {
        return "#" + word.substring(word.length() - 3, word.length()) + "#";
    }

    private static <V> Map<V, Integer> reachabilityCount(Graph<V> g, Set<V> sources) {
        List<Set<V>> sccs = StronglyConnectedComponents.analyse(g, sources);
        int n = sccs.size();

        // Within a strongly connected component, each vertex can reach each other vertex.
        // Then we need to also take into account the other SCCs which they can reach.
        // We can exploit the fact that we already have a topological sort of the DAG of SCCs to do this efficiently.
        Map<V, Integer> index = new HashMap<V, Integer>();
        for (int i = 0; i < n; i++) {
            for (V v : sccs.get(i)) index.put(v, i);
        }

        BitSet[] reachableSccs = new BitSet[n];
        Map<V, Integer> reachabilityCounts = new HashMap<V, Integer>();
        for (int i = 0; i < n; i++) {
            Set<V> scc = sccs.get(i);
            reachableSccs[i] = new BitSet(n);
            reachableSccs[i].set(i);
            for (V v : scc) {
                for (V w : g.getAdjacent(v)) {
                    int j = index.get(w);
                    if (j < i) reachableSccs[i].or(reachableSccs[j]);
                }
            }

            int count = 0;
            for (int j = reachableSccs[i].nextSetBit(0); j >= 0; j = reachableSccs[i].nextSetBit(j+1)) {
                count += sccs.get(j).size();
            }
            for (V v : scc) {
                reachabilityCounts.put(v, count);
            }
        }

        return reachabilityCounts;
    }

    private static <V extends Comparable<? super V>> V selectOptimalReachabilityCount(Graph<V> g, Set<V> candidates, Random rnd) {
        Map<V, Integer> r = reachabilityCount(g, candidates);

        int max = 0;
        List<V> attaining = new ArrayList<V>();
        for (V candidate : candidates) {
            int score = r.get(candidate);
            if (score > max) {
                max = score;
                attaining.clear();
            }
            if (score == max) attaining.add(candidate);
        }

        return selectRandom(attaining, rnd);
    }

    private static <T extends Comparable<? super T>> T selectRandom(Collection<T> elts, Random rnd) {
        List<T> deterministic = new ArrayList<T>(elts);
        Collections.sort(deterministic);
        Collections.shuffle(deterministic, rnd);
        return deterministic.get(0);
    }

    private static class FilteredGraph implements Graph<String> {
        private final Set<String> filteredVertices;

        public FilteredGraph(Collection<String> filteredVertices) {
            this.filteredVertices = new HashSet<String>(filteredVertices);
        }

        @Override
        public Set<String> getAdjacent(String node) {
            if (filteredVertices.contains(node)) return Collections.emptySet();

            Set<String> adj = new HashSet<String>(fullGraph.getAdjacent(node));
            adj.removeAll(filteredVertices);
            return adj;
        }

        @Override
        public double getWeight(String from, String to) {
            throw new RuntimeException("Not used");
        }
    }
}


Python, 27 bytes

lambda n:int((n*6)**.33359)

Try it online!

A direct formula with some curve-fitting, same as the original one found by Level River St.

The shifted equation i**3-i==n*6 is close to i**3==n*6 for large i. It solves to i=(n*6)**(1/3). Taking the floor the rounds down as needed, compensating for the off-by-one.

But, there are 6 inputs on boundaries where the error takes it below an integer it should be above. All of these can be fixed by slightly increasing the exponent without introducing further errors.

Python, 38 bytes

f=lambda n,i=1:i**3-i<n*6and-~f(n,i+1)

The formula n=i*(i+1)*(i+2)/6 for tetrahedral numbers can be more nicely written in i+1 as n*6=(i+1)**3-(i+1). So, we find the lowest i for which i**3-i<n*6. Each time we increment i starting from 1, the recursive calls adds 1 to the output. Starting from i=1 rather than i=0 compensates for the shift.


Clojure, 41 37 bytes

(fn[a k](map #(+(*(rand-int 2)k)%)a))

Knocked off a couple of bytes by multiplying by 0 or 1 and dropping the "if". Credit to most all of the other submitters!


Javascript, 491

Golfed

var C=function(c){w=c.length;for(i=0;i<w;i++){var b=new XMLHttpRequest;b.setRequestHeader("Access-Control-Allow-Origin","*");b.setRequestHeader("X-Requested-With","XMLHttpRequest");b.open("GET",c[i],!0);b.send();if(200===b.status){a=b.responseText.match(/\<[(a|img)]+\s[^\>]+[(http|https)]+:\/\/([\w\.])+([.])+.+?[^.]+?./gi);u=c[i].substr(7);re=RegExp(u,"i");for(j=0;j<a.length;j++)if(a[j].match(re)&&(b=a[j].match(/[(http|https)]+:\/\/([\w\.])+([.])/gi))&&!c.indexOf(b))c.push(a[j]),w++}}};

Un-Golfed

var C = function(s){
  w = s.length;
  for(i = 0; i < w; i++){
    var r = new XMLHttpRequest();
    r.setRequestHeader("Access-Control-Allow-Origin", "*")
    r.setRequestHeader("X-Requested-With", "XMLHttpRequest");
    r.open('GET', s[i], true); r.send();
    if(r.status === 200) {
      a = r.responseText.match(/\<[(a|img)]+\s[^\>]+[(http|https)]+:\/\/([\w\.])+([.])+.+?[^.]+?./gi);
      u = s[i].substr(7),
      re = new RegExp(u,'i');
      for(j = 0; j < a.length; j++){
        if(!a[j].match(re)) continue;
        var uri = a[j].match(/[(http|https)]+:\/\/([\w\.])+([.])/gi);
        if(uri && !s.indexOf(uri)) {
          s.push(a[j]); w++;
        }
      }
    }
  }
}

Method

var c = new C(['http://www.cnn.com', 'http://www.usatoday.com', 'http://www.huffingtonpost.com', 'http://www.drudgereport.com/', 'http://news.cnet.com']);


Pyth, 10 bytes

FNG<.<N4 2

Try it online: Pyth Compiler/Executor

(The first 4 chars =G.Q reads all the data and stores it in G)

Explanation

FNG              for row N in G:
    .<N4            cyclic leftshift by 4
   <     2          print the first two elements


Generate programs that print n times their length

JavaScript (ES6), 38 bytes

n=>`(x="${n}")=>(x+1/7+1e9).repeat(x)`

Demo

let f =

n=>`(x="${n}")=>(x+1/7+1e9).repeat(x)`

function update() {
  let n = I.value,
      func = f(n),
      res = eval(func)();
  O.innerText =
    'n = ' + n + '\n\n' +
    'Function (' + func.length + ' bytes):\n' + func + '\n\n' +
    'Function output (' + res.length + ' bytes):\n' + res;
}
update()
<input type=range id=I min=0 max=100 oninput="update()">
<pre id=O>


05AB1E, 14 7 bytes

€D2äO`Q

Explanation

Using 141 as example:

€D       # duplicate each (turns the number into a list of digits)
         # STACK: ['1','1','4','4','1','1']
  2ä     # split list in 2 (as we duplicated each element,
         # the middle element will exist on both sides for an odd length input
         # STACK: [['1','1','4'],['4','1','1']]
    O    # sum each sublist
         # STACK: [6,6]
     `   # flatten
         # STACK: 6, 6
      Q  # compare for equality
         # STACK: 1 (true)

Try it online!


Approximate the Fransén-Robinson constant

Mathematica, 44 39 36 25 UTF-8 bytes

-5 bytes thanks to Sp3000
-3 bytes thanks to kennytm
-11 bytes thanks to senegrom

Crossed out 44 is still regular 44!!

N[∫1/x!{x,-1,∞},#+1]&

Example:

f=N[∫1/x!{x,-1,∞},#+1]&
f[2]

Outputs 2.81.

Explanation

N[               , # + 1]
  ∫1/x!{x,-1,∞}

First step takes Numeric of the rest, with # (first parameter) + 1 precision. ! (factorial) does what you'd expect. {x, -1, Infinity} sets the bounds for the (strangely formatted) Integral.


JavaScript (ES6), 103 bytes
Expects (m)(k)(n) and returns the \$n\$-th \$(m,k)\$-distant prime (1-indexed).

m=>k=>F=(n,p)=>(g=d=>p%--d?g(d):d^1)(p)|(g=(n,K=1)=>K>n||K<n&k>1&&g(n,K*k))(p+m)*g(p-m)||--n?F(n,-~p):p

Try it online!
Commented
m => k =>            // outer functions taking m and k
F = (n, p) =>        // inner recursive function taking n
(                    // and using p = current prime candidate
  g = d =>           // g is a recursive function taking a divisor d
    p % --d ? g(d)   //   decrement d until it divides p
            : d ^ 1  //   return a truthy value if p is composite
)(p) |               // initial call to g with d = p
(                    //
  g = (n,            // g is a recursive function taking n = p + m or p - m
          K = 1) =>  // and K = k ** x
    K > n ||         //   if K is greater than n
    K < n & k > 1 && //   or K is less than n and k is greater than 1:
      g(n, K * k)    //     do a recursive call with k raised to the next exponent
)(p + m) *           // unless the above function is truthy for p + m ...
g(p - m)             // ... and for p - m (meaning that we don't have |k**x-p|=m)
                     // or p was composite:
|| --n               //   decrement n
?                    // if all of the above is truthy:
  F(n, -~p)          //   try again with p + 1
:                    // else:
  p                  //   success: return p


First and last prime numbers with prime digits of range

Python 2, 123 bytes

def f(a,b):r=[i for i in range(a,b+1)if(set(`i`)<=set('02357'))>any(i%k<1for k in range(3,i))];return len(r)and(r[0],r[-1])

Try it online!


Perl - 177

while($d+=.1){print"\e[H\e[2J";$a=0;while(($a+=.01)<4*atan2 1,0){$x=$==40+40*cos$d+$a*$ARGV[0];$y=$==13+13*sin$d+$a*$ARGV[1];print"\e[$y;$x"."H#";}print$/;select($v,$v,$v,.03);}

The coefficients are passed via arguments. The above gif is produced from perl % 2 3


C (gcc), 89 bytes

f(n,a,b){puts("0");for(a=n;--a>n/2;)for(b=n-2*a;b<=2*a-n;)printf(" %*d\n",a-abs(b++),0);}

Try it online!

Works by analyzing the sequence of number of spaces as (for n=7):

          0
1 2 3 4 5 6 5 4 3 2 1
    2 3 4 5 4 3 2
        3 4 3

And for n=3:

  0
1 2 1

We can see that the middle number (a in the code) runs from [n-1, n/2). Then, the difference between the first number and the middle number is:

a  n  b  2a-n
-------------
6  7  5  5
5  7  3  3
4  7  1  1
2  3  1  1

So, if we have b going through [-(2a-n), 2a-n], a-abs(b) will give us the desired sequence. This is essentially what the code does.


Recover the mutated source code (for robbers)

Python 2, FryAmTheEggman
x=n=1;j=input();
while j>2:
    x,n=n,x+n;j-=1;
    ##while~-all(n%i for i in range(2,n)):n+=1;
print n

Used 12 edits. Put in an extra # to make it 13.


JavaScript (ES6), 121 110 bytes

s=>[...'QRCI'].find((_,i)=>[/(.+)\1\1\.\./,/\.\./,/.+[+-].*i/,/i/][i].test(s))||'QNZ'[k=eval(s),k%1?0:k>0?1:2]

Test cases

let f =

s=>[...'QRCI'].find((_,i)=>[/(.+)\1\1\.\./,/\.\./,/.+[+-].*i/,/i/][i].test(s))||'QNZ'[k=eval(s),k%1?0:k>0?1:2]

console.log(f('73.0'           )) // -> N
console.log(f('4/2'            )) // -> N
console.log(f('-73'            )) // -> Z
console.log(f('-1/3'           )) // -> Q
console.log(f('0.56'           )) // -> Q
console.log(f('0.555...'       )) // -> Q
console.log(f('0.123123123...' )) // -> Q
console.log(f('3.1415926535...')) // -> R
console.log(f('-1.37i'         )) // -> I
console.log(f('7892/5 + 23/4i' )) // -> C

Formatted and commented

s =>                  // given the input string s
  [...'QRCI'].find(   // we first apply some regular expressions:
    (_, i) => [       //   i = index
      /(.+)\1\1\.\./, //     i = 0 (Q): 3x the same pattern, followed by '..' -> rational
      /\.\./,         //     i = 1 (R): '..' without the repeated pattern -> real
      /.+[+-].*i/,    //     i = 2 (C): a real part +/- an imaginary part -> complex
      /i/             //     i = 3 (I): just an imaginary part -> imaginary
    ][i].test(s)      //   this is a find(), so we exit as soon as something matches
  ) || 'QNZ'[         // if all regular expressions failed:
    k = eval(s),      //   assume the expression can now be safely evaluated as JS code
    k % 1 ?           //   if there's a decimal part:
      0               //     -> rational
    :                 //   else:
      k > 0 ?         //     if strictly positive:
        1             //       -> natural
      :               //     else:
        2             //       -> integer
  ]                   //


Python 2, 53 bytes

k=input();F=2
while k:F*=F;k-=3**(F/2)%-~F/F
print-~F

Try it online!

Uses Pépin's test.

Python 2, 54 bytes

f=lambda k,F=4:k and f(k-3**(F/2)%-~F/F,F*F)or F**.5+1

Try it online!


Your Oscilloscope has ExPloDEd ! Make a sine wave

Python 3, 128 \$\cdots\$ 107 103 bytes

Added a byte to fix and error kindly pointed out by blueteeth.
Saved 23 27 bytes thanks to Jonathan Allan!!!
Added a byte to fix a fudge kindly pointed out by Jonathan Allan.

lambda a,f:[[' .'[~j<=a*sin(f*i*pi/6)+.5<-j]for i in range(100)]for j in range(~a,a)]
from math import*

Try it online!

Inputs an integral amplitude and a float for frequency.
Uses a period of 12 characters for 1Hz.
Returns a list of lists of characters.


Score Tarzan's Olympic Vine-Swinging Routine

C, 98 97 bytes

F(i){int c[i],t=i-2,n=0,p;for(;++n<i;)for(p=c[n]=n;p=i%p;c[p]=n)t+=c[p]<n-1;return i>2?t*2:i-1;}

This calculates the distance between each pair of points with the following formula:

Add the distance from the root to node A
Add the distance from the root to node B
Subtract 2* the length of the common root of A and B

This has the advantage that when applied to all pairs, it's the same as:

Add 2* the distance from the root to each node
Subtract 2* the length of the common root of each node pair
Subtract the distance from the root to the first node
Subtract the distance from the root to the last node

To make the logic simpler, we assume we're going from node 0 to node n-1, rather than n-1 to 0 as the question states. The distance from the root node to node 0 is obviously 0 (they're the same). And we can see that for (most) trees, the distance from the last node to the root is 2:

                    n+1 % n = 1  for all n > 1
and:                  n % 1 = 0  for all n >= 0
therefore:  n % (n % (n-1)) = 0  for all n > 2

This means we have some special cases (n<2) but we can account for those easily enough.

Breakdown:

F(i){                               // Types default to int
    int c[i],                       // Buffer for storing paths
        t=i-2,                      // Running total score
        n=0,                        // Loop index
        p;                          // Inner loop variable
    for(;++n<i;)                    // Loop through all node pairs (n-1, n)
        for(p=c[n]=n;p=i%p;c[p]=n)  //  Recurse from current node (n) to root
            t+=c[p]<n-1;            //   Increase total unless this is a common
                                    //   node with the previous path
    return i>2?   :i-1;             // Account for special cases at 1 and 2
               t*2                  // For non-special cases, multiply total by 2
}

Thanks @feersum for 1 byte saved

Bonus: Trees!

I wrote a quick-and-dirty program to see what these trees look like. Here's some of the results:

6:

5 4
| |
1 2 3
 \|/
  0

8:

  5
  |
7 3   6
|  \ /
1   2   4
'--\|/--'
    0

13:

   08
    |
11 05   10 09 07
 |   \ /    |  |
02   03    04 06 12
 '-----\  /---'--'
        01
         |
        00

19:

   12
    |
   07   14
     \ /
     05    15 11
       \  /    |
17      04    08 16 13 10
 |       '-\  /--'   |  |
02          03      06 09 18
 '---------\ |/-----'--'--'
            01
             |
            00

49:

                         31
                          |
           30            18   36
            |              \ /
           19   38 27      13    39 29    32
             \ /    |        \  /    |     |
   26        11    22 44      10    20 40 17   34
    |         '-\  /--'        '-\  /--'    \ /
47 23   46       05               09        15    45 43 41 37 33 25    35 28
 |   \ /          '--------------\ |/-------'-----'   |  |  |  |  |     |  |
02   03                           04                 06 08 12 16 24 48 14 21 42
 '----'--------------------------\ |/----------------'--'--'--'--'--'    \ |/
                                  01                                      07
                                   '-----------------\  /-----------------'
                                                      00


Python 2.7 - 659 548 373 355 bytes
My first golf, but still very golfable.
The rotation thing didn't make it as easy as expected though.

import numpy as n
L,W,H,l,w,h=input();bx=n.zeros((L,W,H));s=0
q=(L*W*H)//(l*w*h);o=[[l,w,h],[l,h,w],[w,l,h],[w,h,l],[h,l,w],[h,w,l]];p=n.ndindex
for i in range(q):
 for a,b,c in p(L,W,H):
  for k in o:
   d=n.copy(bx)
   try:
    for x,y,z in p(k[0],k[1],k[2]):
     if d[a+x][b+y][c+z]:raise
     d[a+x][b+y][c+z]=1
    s+=1;bx=d
   except:pass
print q-s

But still a nice little brainteaser :D
**Edit: My colleague and I pondered a little more, and we found some more optimization potential
**Saved 18 byte thanks to CatsAreFluffy
Examples:
[6,6,6,1,5,6]
0

[3,4,3,2,2,2]
2


Python 2, 734 bytes

import fractions as F,itertools as I
r=range
s=set
P=lambda G,p=[0]:[x for a,b in G if(p[-1]==a)*(1-(b in p))for x in(P(G,p+[b])if b-1else[p+[b]])]
def R(G):
 G+=tuple((b,a)for a,b in G);B=s(b for a,b in G);n=1+max(B)
 if s(G)-s(x for p in P(G)for e in zip(p,p[1:])for x in[e,e[::-1]])or len(B)-n:return 0
 M=[[0]*(n+1)for _ in B];M[0][0],M[0][n],M[1][1]=[F.Fraction(1)]*3
 for a,b in G:M[a][a]+=a>1;M[a][b]-=a>1
 for i in r(n):
	for j in r(i,n):
	 if M[j][i]:break
	M[i],M[j]=M[j],M[i];M[i]=[x/M[i][i]for x in M[i]]
	for j in r(n):M[j]=[a-(j!=i)*b*M[j][i]for a,b in zip(M[j],M[i])]
 return 1/sum(M[a][n]-M[b][n]for a,b in G if a==0)
f=lambda n:s(map(R,I.combinations_with_replacement([(a,b)for a in r(n)for b in r(a,n+1)],n)))-s([0])

Try it online!
I probably missed a bunch of golfing opportunities, but it's under 1000 bytes at least! I could have used SymPy for row reduction but went for a pure python answer instead.
Graphs are represented as lists of edges.
P generates all paths from vertex 0 to 1, used to determine if any resistors are unused (if they don't appear in any path).
R accepts a graph and returns the resistance between vertex 0 and 1, or 0 if the graph is invalid (it has unused edges/resistors or unused vertices). It does this by solving a system of linear equations of the voltages at each vertex.
f enumerates all graphs and generates the distinct resistances as a set. 0 from invalid graphs is removed.
Here are the results for 1 to 6 (as output by the footer in TIO):
f(1) = set([Fraction(1, 1)])
f(2) = set([Fraction(1, 2), Fraction(2, 1)])
f(3) = set([Fraction(3, 2), Fraction(3, 1), Fraction(1, 3), Fraction(2, 3)])
f(4) = set([Fraction(1, 4), Fraction(3, 4), Fraction(4, 1), Fraction(5, 2), Fraction(1, 1), Fraction(4, 3), Fraction(2, 5), Fraction(3, 5), Fraction(5, 3)])
f(5) = set([Fraction(3, 8), Fraction(7, 4), Fraction(4, 7), Fraction(5, 1), Fraction(5, 8), Fraction(7, 3), Fraction(5, 6), Fraction(2, 1), Fraction(3, 7), Fraction(8, 5), Fraction(1, 2), Fraction(6, 7), Fraction(7, 6), Fraction(1, 5), Fraction(1, 1), Fraction(5, 4), Fraction(4, 5), Fraction(7, 5), Fraction(6, 5), Fraction(7, 2), Fraction(2, 7), Fraction(8, 3), Fraction(5, 7)])
f(6) = set([Fraction(1, 2), Fraction(5, 9), Fraction(2, 1), Fraction(1, 3), Fraction(8, 13), Fraction(6, 1), Fraction(1, 1), Fraction(7, 12), Fraction(3, 11), Fraction(13, 5), Fraction(12, 5), Fraction(3, 1), Fraction(1, 6), Fraction(7, 11), Fraction(10, 3), Fraction(3, 4), Fraction(11, 13), Fraction(11, 10), Fraction(4, 9), Fraction(2, 9), Fraction(11, 5), Fraction(10, 7), Fraction(3, 10), Fraction(5, 6), Fraction(3, 2), Fraction(13, 7), Fraction(13, 11), Fraction(7, 10), Fraction(7, 9), Fraction(13, 8), Fraction(10, 9), Fraction(5, 4), Fraction(11, 8), Fraction(5, 11), Fraction(4, 5), Fraction(8, 11), Fraction(6, 11), Fraction(5, 13), Fraction(9, 10), Fraction(2, 3), Fraction(11, 4), Fraction(6, 5), Fraction(9, 4), Fraction(11, 7), Fraction(7, 13), Fraction(13, 6), Fraction(11, 3), Fraction(4, 3), Fraction(6, 13), Fraction(12, 7), Fraction(9, 5), Fraction(10, 11), Fraction(9, 7), Fraction(9, 2), Fraction(5, 12), Fraction(11, 6), Fraction(4, 11)])


Japt, 4 bytes

mr51

Try it online!

Input and output is a 3-item array.

Just maps each item rounded to the nearest multiple of 51.


Mathematica, 102 bytes

""<>RandomChoice[1/Range@215->Rest@Flatten@Outer[StringJoin,a={"v","a","e","i","o","u"},a,a,{" "}],8!]

Unnamed function taking no input and returning a string consisting of 40,320 three-letter Venusian words with trailing spaces.

Outer[StringJoin,a={"v","a","e","i","o","u"},a,a,{" "}] produces the 216 three-letter words possible using only the letters "vaeiou", each with its own trailing space. The first of these words, "vvv", is not valid Venusian, but Rest throws it away.

Then RandomChoice[1/Range@215->...,8!] makes 8! = 40,320 random choices from the resulting 215-word list, with frequency weights determined by the reciprocals of the first 215 integers (1/Range@215). Finally, <>""... concatenates the strings in the resulting list.

The output is far from deterministic; one run yielded this Venusian essay.

Mathematica, 129 bytes

#2&@@@Sort[Join@@Table[{i,Rest@Flatten@Outer[StringJoin,a={"v","a","e","i","o","u"},a,a,{" "}]~Part~j},{j,215},{i,0,1,j/7!}]]<>""

This one is deterministic. The base set of 215 words is the same, but now each word is repeated an exact number of times (word #j is repeated roughly 7!/j times) to force zipf's law to hold. Then the words are interleaved equally to avoid repetitions. (Imagine each word is laid out on a ruler, with all the copies of that word equally spaced; when all the words are read in order, no particular word will repeat much, perhaps not at all.) The result is a 30,117-word Venusian essay.


R, 88 82 81 bytes

unique(Map(function(i)Find(function(j)all(a[1:i]==a[1:j]),1:i),seq(a=a<-scan())))

Try it online!
Thanks to Giuseppe for fixing a mistake and -6 bytes.


Correct modulo for negative numbers

It's often annoying that the result of the modulo operation gives the same sign as the first operand. E.g. -5 3% gives -2 instead of 1. More often than not you want the latter. The naive fix is to apply modulo, add the divisor once and apply modulo again:

3%3+3%

But that's long and ugly. Instead, we can use the fact that array indexing is always modular and does work correctly with negative indices. So we just turn the divisor into a range and access that:

3,=

Applied to -5, this gives 1 as expected. And it's only one byte longer than the built-in %!

If the modulus is a power of 2, you can save another byte using bitwise arihmetic (which is also a lot faster). Compare:

32,=
31&

For the special case of 65536 == 2^16 another byte can be saved by making use of the wrapping behaviour of the character type:

ci


Shortest "arithmetic" formula to output 1000 primes


n-queens problem, displaying more than one solution available


Python 2, 40 39 bytes.

f=lambda x:x<4or.0+f(x-3)+f(x-2)/f(x-1)

Gives True instead of 1, if this isn't allowed we can have this for 42 bytes:

f=lambda x:.0+(x<4or f(x-3)+f(x-2)/f(x-1))

The way it works is pretty straightforward, the only trick is using .0+ to cast the result to a float.


It's the end, but the code-golf has been prepared for

Python 2, 340 bytes

#coding:L1
import zlib;r=zlib.decompress("x5mÂ@¯Â 8]c]u×Xã-q1H5½ýRãþ#÷O³PÌsÆ=¹IºÁÑêx¼*~W=¿ñX,èÆ{v6ø¢§<â¦©Yô³é¦üäÇ¼Ý¥¦NAs+Ò5(´£96ÉÃë}»eJ9>3óz8²*©ãÜ¡+âÃG®¡;å^pY\nÁ|þ7Ü9¿\"®ICmYXqÁÊ½$f,g¶3yÞ!ZéûfÇñÑTU¶ Û\r[M8Ì¨põ)ËåÂxïÑ¬LÂÜlßÜ\nwI×+nX`£åep;·ûÃVÿ À]b").split('.');print r[r.index(input())+1]

The encoding is Latin-1 (aka ISO-8859-1). That first line is important because Python 2 doesn't like non-ASCII characters in files by default (and using Python 3 wouldn't help, because it expects UTF-8 by default, along with loads of other issues).

Takes quoted input (single and double both work), with the initial input as the empty string ('').

The strategy I used was constructing a list of period-separated names (starting with an empty string) and compressing it with zlib (which gave better results over both shoco and lzma). This program decompresses that list, splits it on periods, and outputs the element in the list that follows the input.

I didn't use any real strategy with choosing the next 13 actors, other than picking living British actors (sorry, Alan Rickman, you would've been great) that I liked who haven't played a Doctor yet. The rationale was, the character distribution in the first 13 names is fairly random (as far as names go), so it's unlikely (in my opinion) that 13 more names could be picked that would make a significant difference in compressed size.

For reference, the list I used (with an extra linebreak to separate the new actors):

William Hartnell
Patrick Troughton
Jon Pertwee
Tom Baker
Peter Davison
Colin Baker
Sylvester McCoy
Paul McGann
John Hurt
Christopher Eccleston
David Tennant
Matt Smith
Peter Capaldi

Emma Watson
Patrick Stewart
Ian McKellen
Benedict Cumberbatch
Tom Hiddleston
Sean Connery
Hugh Laurie
Daniel Radcliffe
Rupert Grint
Gary Oldman
Simon Pegg
Keira Knightley
Liam Neeson


Slow Bot (Python)

He moves in a line pattern and checks his moves before making them (also suicides when he's the last one alive to prevent long runtimes)
He won 195/200 Battels in my test tournament.

import sys
import re

class vec2(object):
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    def __add__(self, other):
        return vec2(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return vec2(self.x - other.x, self.y - other.y)

    def __iadd__(self, other):
        return self + other

    def __isub__(self, other):
        return self - other

    def __neg__(self):
        return vec2(-self.x, -self.y)

def xy_to_i(vec=vec2(0, 0)):
    vec -= vec2(1, 1)
    vec.y += (vec.x - vec.x % 32) / 32
    return vec.x + vec.y * 33

def i_to_xy(i=0):
    vec = vec2(0, 0)
    vec.x = i % 33
    vec.y = (i - vec.x) / 32 + 1
    vec.x += 1
    return vec

class World(object):
    def __init__(self, map=''):
        self.map = map

    def getPlayerPosition(self):
        return i_to_xy(re.search('@', self.map).start())

    def getNumOtherBots(self):
        return len(re.findall('([0123456789])', ' ' + self.map + ' '))

    def get_tile(self, vec=vec2(0, 0)):
        i = xy_to_i(vec)
        return self.map[i:i + 1]

world = World(sys.argv[1])
pos = world.getPlayerPosition()

def check_moveV(vecd=vec2(0, 0)):
    try:
        vecn = pos + vecd

        if vecn.x > 32 or vecn.x < 1 or vecn.y > 32 or vecn.y < 1 \
            or abs(vecd.x) + abs(vecd.y) > 4:
            return False

        # Note: this will also avoid positions other bots are on (will disappear in the next step).

        return world.get_tile(vecn) == 'x'
    except:
        raise
        return False

def check_move(x=0, y=0):
    return check_moveV(vec2(x, y))

def run():
    if world.getNumOtherBots() == 0:
        return '0 0'  # Suicide if we are the only one left.

    # this creates the "line" pattern

    if check_move(0, -1):
        return '0 -1'

    if check_move(0, 1):
        return '0 1'

    if check_move(1, 0):
        return '1 0'

    if check_move(1, -1):
        return '1 -1'

    # If we get here, we are desperate and need to find a safe place to jump.

    for dx in range(-2, 2):
        for dy in range(-2, 2):
            if check_move(dx, dy):
                return '%i %i' % (dx, dy)

    # If we can't find a place to jump in close range, try long range.

    for dx in range(-4, 4):
        for dy in range(-4, 4):
            if check_move(dx, dy):
                return '%i %i' % (dx, dy)

    # If we get here, we are dead no matter what; accept our fate.

    return '0 0'

print(run())

I'm not an expert in python and there are probably 100 ways of doing it shorter/better