Optimize paper folding to mitigate inkblots

Python

Exhaustively tries different combinations of folds for the first few folds, then does the rest of the folds using a greedy approach.

The exhaustive approach is bounded within a reasonable range of folds in the center, such that it won't take forever, while not ignoring too many possible folds to yield a good minimum.

Ran using pypy on my macbook air.

Answers:

20*20D9R15R6D11R10R9D10R11
40*20D6D13D9R19R21R20D11D10
40*40D21R21R11D19R23R20D23D15
20*80D33D47D40R10D39D41R9R11

Outputs:

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.2
Time taken: 4.016076s
Score: 7.91125
20*20D9R15R6D11R10R9D10R11

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.2
Time taken: 28.529278s
Score: 16.34375
40*20D6D13D9R19R21R20D11D10

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.25
Time taken: 98.430465s
Score: 42.13
40*40D21R21R11D19R23R20D23D15

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.25
Time taken: 234.873787s
Score: 32.30875
20*80D33D47D40R10D39D41R9R11

Total Score: 7.91125 + 16.34375 + 42.13 + 32.30875 = 98.69375

Code:

import time, math
from collections import deque

numberOfFolds = 8 # Total number of folds

startTime = time.clock()

exec "grid = ("+"""
1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1
1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1
0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0
0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1
0 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0
1 0 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 1
0 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0
1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1
1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 0
0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1
0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 0
0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1
0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1
1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1
0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0
0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0
0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 1 1 1 1
""".replace(" ",",").replace("\n","],[")[2:-2]+")"

def getAverage(grid):
    count = total = 0
    for j in grid:
        for i in j:
            count += 1
            total += i
    return total/float(count)

def getScore(grid, average):
    score = 0
    for j in grid:
        for i in j:
            score += abs(average-i)
    return score

def downFoldedGrid(grid, row, width, height, copy=True):
    if copy: grid = [r[:] for r in grid]
    foldRange = min(row, height-row)
    for j in xrange(foldRange):
        rowRef1 = grid[row+j]
        rowRef2 = grid[row-1-j]
        for i in xrange(width):
            rowRef1[i] = rowRef2[i] = (rowRef1[i] + rowRef2[i]) * .5
    return grid

def downFoldedScore(grid, score, average, row, width, height):
    foldRange = min(row, height-row)
    average2  = 2*average
    for j in xrange(foldRange):
        rowRef1 = grid[row+j]
        rowRef2 = grid[row-1-j]
        a = b = c = 0
        for i in xrange(width):
            a = rowRef1[i]
            b = rowRef2[i]
            c = a+b
            score += abs(average2-c) - abs(average-a) - abs(average-b)
    return score

def rightFoldedGrid(grid, column, width, height, copy=True):
    if copy: grid = [r[:] for r in grid]
    foldRange = min(column, width-column)
    for j in xrange(height):
        rowRef = grid[j]
        for i in xrange(foldRange):
            a = column+i
            b = column-1-i
            rowRef[a] = rowRef[b] = (rowRef[a] + rowRef[b]) * .5
    return grid

def rightFoldedScore(grid, score, average, column, width, height):
    foldRange = min(column, width-column)
    average2 = 2*average
    for j in xrange(height):
        rowRef = grid[j]
        a = b = c = 0
        for i in xrange(foldRange):
            a = rowRef[column+i]
            b = rowRef[column-1-i]
            c = a+b
            score += abs(average2-c) - abs(average-a) - abs(average-b)
    return score

def bestFoldsGreedy(grid, average, maxFolds, width, height):
    score  = getScore(grid, average)
    folds  = []
    append = folds.append
    for z in xrange(maxFolds):
        bestFold      = 0
        bestFoldScore = score
        bestFoldGrid  = grid
        for i in xrange(1, width): #Try all right folds
            foldScore = rightFoldedScore(grid, score, average, i, width, height)
            if foldScore < bestFoldScore:
                bestFold      = i
                bestFoldScore = foldScore
        for i in xrange(1, height): #Try all down folds
            foldScore = downFoldedScore(grid, score, average, i, width, height)
            if foldScore < bestFoldScore:
                bestFold      = -i
                bestFoldScore = foldScore
        if bestFold:
            append(bestFold)
            score = bestFoldScore
            if bestFold > 0: rightFoldedGrid(grid, bestFold, width, height, False)
            else:            downFoldedGrid(grid, -bestFold, width, height, False)
    return score, folds

# Get the height and width
height  = len(grid)
width   = len(grid[0])

# Transpose the grid if height > width for better locality of reference
transposed = False
if height > width:
    grid = [[grid[i][j] for i in range(height)] for j in range(width)]
    transposed = True
    height, width = width, height

# The exhaustive grids and folds attempted
exhaustiveGridsAndFolds = deque([(grid,[])])
popleft = exhaustiveGridsAndFolds.popleft
append  = exhaustiveGridsAndFolds.append

# Set the bounds to exhaustively test for
exhaustiveLevels   = 3
prunePadding       = [0.2, 0.25][width*height > 1000]
leftBound          = int(max(width*prunePadding, 1))
rightBound         = int(width*(1.0-prunePadding))
topBound           = int(max(height*prunePadding, 1))
bottomBound        = int(height*(1.0-prunePadding))

# Populate the exhaustive grids and folds
while 1:
    grid, folds = popleft()
    if len(folds) == exhaustiveLevels:
        append((grid, folds))
        break
    for i in xrange(leftBound, rightBound):
        if i not in folds:
            append((rightFoldedGrid(grid, i, width, height), folds+[i]))
    for i in xrange(topBound, bottomBound):
        if -i not in folds:
            append((downFoldedGrid(grid, i, width, height), folds+[-i]))

# Test all the exhaustive grids and folds greedily
average             = getAverage(grid)
bestFinalScore      = getScore(grid, average)
bestFinalFolds      = []
numberOfGreedyFolds = numberOfFolds-exhaustiveLevels
while exhaustiveGridsAndFolds:
    grid, exhaustiveFolds = popleft()
    finalScore, greedyFolds = bestFoldsGreedy(grid, average, numberOfGreedyFolds, width, height)
    if finalScore <= bestFinalScore:
        bestFinalScore = finalScore
        bestFinalFolds = exhaustiveFolds + greedyFolds

# Repeat the last fold till the total number of folds if needed
if len(bestFinalFolds) < numberOfFolds:
    bestFinalFolds += [bestFinalFolds[-1]]*(numberOfFolds-len(bestFinalFolds))

# Print the best result
foldsString = ""
down  = "D"
right = "R"
if transposed:
    down,  right  = right,  down
    width, height = height, width
for fold in bestFinalFolds:
    if   fold > 0: foldsString += right+str(fold)
    elif fold < 0: foldsString += down+str(-fold)
print "Exhaustive folds levels: " + str(exhaustiveLevels)
print "Percentage pruned from sides from exhaustive folds: " + str(prunePadding)
print "Time taken: " + str(time.clock()-startTime) + "s"
print "Score: " + str(bestFinalScore)
print str(width) + "*" + str(height) + foldsString


Cheap, Fast, Good - Common Factor (Greatest)

C
It's cheap and fast. You get gcd in the blink of an eye. However the guy who did it had no clue about that "Bézier co-something" so he simply divided a and b by gcd.
(to make things worse, at that point a and b are pretty far from their initial value because of the algorithm he wisely chose)
int main(int argc, char **argv){
    unsigned int a, b, tmp;
    a = (unsigned int)atoi(argv[1]);
    b = (unsigned int)atoi(argv[2]);
    for (tmp = 0; ((a | b) & 1) == 0; ++tmp){
        a >>= 1;
        b >>= 1;
    }
    while ((a & 1) == 0)
        a >>= 1;
    do {
        while ((b & 1) == 0)
            b >>= 1;
        if (a > b){
            unsigned int t = b;
            b = a;
            a = t;
        }
        b = b - a;
    } while (b != 0);
    tmp = a << tmp;
    printf("%u, (%u,%u)", tmp, a/tmp, b/tmp);
    return 0;
}


Neim, 2 bytes

q

Explanation:

q      Push an infinite list of squares
      Is the input in that list?

When I say 'infinite' I mean up until we hit the maximum value of longs (2^63-1). However, Neim is (slowly) transitioning to theoretically infinitely large BigIntegers.

Try it!


Haskell, 114

main=getLine>>=putStrLn.f.p;f x=head$[a|(a,b)<-x,a==b]++["0"]
p[]=[([],[])];p(x:y)=do(a,b)<-p y;[(x:a,b),(a,x:b)]

Ungolfed:

main :: IO ()
main = getLine >>= putStrLn . findMatch . partitions

-- | Find the first partition where the two subsequences are
-- equal. If none are, return "0".
findMatch :: [(String, String)] -> String
findMatch ps = head $ [a | (a,b) <- ps, a == b] ++ ["0"]

-- | Return all possible partitions of the input into two
-- subsequences. Preserves the order of each subsequence.
--
-- Example:
-- partitions "AB" == [("AB",""),("B","A"),("A","B"),("","AB")]
partitions :: [a] -> [([a], [a])]
partitions []     = [([], [])]
partitions (x:xs) = do (a, b) <- partitions xs
                       [(x:a, b), (a, x:b)]

Explanation:

Most of the work is being done in the partitions function. It works by
recursively generating all partitions (a, b) of the tail of the list,
and then using the list monad to prepend the initial element x to each of
them and gather all the results.

findMatch works by filtering this list so that only partitions where the
subsequences are equal remain. It then returns the first subsequence in the first
partition. If none remain, the list is empty, so the "0" appended at the
end gets returned instead.

main just reads the input, feeds it through these two functions and prints it.


Jelly, 9 bytes
^ị“½¥¢‘İP

Try it online!
Takes input as 2376 instead of acgt respectively. The Footer does this for you
-1 byte thanks to Jonathan Allan!
How it works
^ị“½¥¢‘İP - Main link. Takes the first input on the left and the second on the right
^         - XOR the corresponding elements
  “½¥¢‘   - Yield [10, 4, 1]
 ị        - Index into this array, 1-indexed and modularly
       İ  - Take the inverse of each
        P - Take the product

Why this works

Characters
As integers
XOR
1-index into [10,4,1]
Inverse

aa
2, 2
\$0\$
\$1\$
\$1\$

cc
3, 3
\$0\$
\$1\$
\$1\$

gg
7, 7
\$0\$
\$1\$
\$1\$

tt
6, 6
\$0\$
\$1\$
\$1\$

ac
2, 3
\$1\$
\$10\$
\$0.1\$

ag
2, 7
\$5\$
\$4\$
\$0.25\$

at
2, 6
\$4\$
\$10\$
\$0.1\$

cg
3, 7
\$4\$
\$10\$
\$0.1\$

ct
3, 6
\$5\$
\$4\$
\$0.25\$

gt
7, 6
\$1\$
\$10\$
\$0.1\$


ES6, 71 65 bytes

a=>a.sort((b,c)=>r(b)>r(c)||-1,r=s=>s.replace(/[^A-z]*$/,"z$&,"))

By inserting a z after the letters and suffixing a , we just have to sort the strings lexically.

Edit: Saved 6 bytes thanks to @user81655.


Brachylog (2), 9 characters

{⊇.+0∧}ᵘb

Try it online!

{⊇.+0∧}ᵘb
 ⊇           subset
   +0        that sums to 0
  .  ∧       output the subset
{     }ᵘ     take all unique solutions
        b    except the first (which is the empty solution)


JavaScript (SpiderMonkey 30+), 74 bytes

s=>[for(b of'o0x')if((c=+(0+b+s))>31&c<127)String.fromCharCode(c)].join` `


Pyth: 37 29 28 bytes

um?d|-lHl{sHsmg{kdH-dsHGtyQQ

Input is a list of lists like [[1,2], [2,3], [1,3], [1,2,3,4]]. Try it online: Pyth Compiler/Executor

Explanation:

um?d|-lHl{sHsmg{kdH-dsHGtyQQ
u                          Q  G = input array
u                       tyQQ  For each H in powerset(input):
 m                     G        G = [            ...        for d in G]
  ?d               -dsH             [d if ... else d-sum(H) for d in G]
     -lHl{sH                        len(H)-len(set(sum(H)))!=0
    |                                     or
            smg{kdH                 sum(d is subset of k for k in H)>0


Jelly, 12 8 bytes

RÆṪSḤ’÷²

Try it online!

The following binary code works with this version of the Jelly interpreter.

0000000: 52 91 b0 53 aa b7 9a 8a  R..S....

Idea

Clearly, the number of pairs (j, k) such that j ≤ k and j and k are co-prime equals the number of pairs (k, j) that satisfy the same conditions. Also, if j = k, j = 1 = k.

Thus, to count the number of co-prime pairs with coordinates between 1 and n, it suffices to calculate the amount m of pairs (j, k) such that j ≤ k, then compute 2m - 1.

Finally, since Euler's totient function φ(k) yields the number integers between between 1 and k that are co-prime to k, we can calculate m as φ(1) + … + φ(n).

Code

RÆṪSḤ’÷²    Input: n

R           Yield [1, ..., n].
 ÆṪ         Apply Euler's totient function to each k in [1, ..., n].
   S        Compute the sum of all results.
    Ḥ       Multiply the result by 2.
     ’      Subtract 1.
      ÷²    Divide the result by n².


Output quater-imaginary base numbers in binary

JavaScript (ES6), 340 bytes

f=x=>[0,...x.toString(16)].reverse().map(d=>s=d<'.'?s:d<`0`?d+s.slice(0,-1):`${(c=+`0x${d}`+(c>>4)+m^m)>>2&3}${c&3}`+s,c=s='.',m=x<0?3:12)&&s
g=(s,t,n=s.indexOf`.`,m=t.indexOf`.`)=>n<m?g(0+s,t):n>m?g(s,0+t):t[s.length]?g(s+0,t):s.replace(/\d/g,(c,i)=>`${t[i]>>1}${t[i]&1}${c>>1}${c&1}`).replace(/^0+(\d)|\.?0*$/g,'$1')
(r,i)=>g(f(r),f(i/2))

f converts a number into base -4 (with trailing . if the number is an integer). g takes two base -4 numbers, pads them at both ends to the same length and . position, shuffles the digits together, converts everything from base 4 to base 2, then finally strips leading and trailing zeros.

Explanation: To represent the given complex number in modified-base 2i we need to represent the real part and half of the complex part (i.e. dividing the imaginary part by 2i) in base 2i² (i.e. -4), shuffle the digits together, and then convert them from base 4 to base 2. To represent a real number in base -4 we start with the base 4 conversion. Alternate digits have the correct sign (in the case of a positive number, these are the digits in the even positions; in the case of a negative number, these are the digits in the odd positions) but the remaining digits have the wrong sign and a correction needs to be applied. Examples:

 0 -> 000 -> 000 (no correction needed)
 4 -> 010 -> 130 }
 8 -> 020 -> 120 } (correction includes carry)
12 -> 030 -> 110 }

As you can see, the correction is 8 minus the original digit, mod 8. However a slightly more convenient calculation is the original digit, plus 3, xor 3 (indeed in 32-bit integer arithmetic we could simply write +0xCCCCCCCC^0xCCCCCCCC to convert the entire number in one go). Finally as the correction applies to alternate digits it is simpler to do an initial conversion to base 16 which automatically picks up pairs of base 4 digits, then correct using a factor of either 3 or 0xC as appropriate. It just remains to ignore the - sign.


Brainfuck, 30 27 bytes

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

Try it online!

How it works

+ changes the initial cell to 1. After this step, we enter the following, nested loop.

[        While the current cell is non-zero:
  [        While the current cell (C) is non-zero:
    >++      Increment the cell to C's right twice.
    <<+      Increment the cell to C's left.
    >-       Decrement C.
  ]
  >        Advance to the cell to C's right.
]

This computes consecutive powers of 2 until the the value 256 = 0 (mod 256) is reached. When the outer loop finishes, the tape is in the following state.

                                     v
001 002 004 008 016 032 064 128 000 000 000

<<<++ retrocedes three cells and increments twice, leaving the tape as follows.

                         v
001 002 004 008 016 032 066 128 000 000 000

Now we're ready to print the actual output. As a stop condition, we increment the cell above twice each time we print and increment the cell to its left. Since 66 + 95 × 2 = 256 = 0 (mod 256), we stop after printing all 95 printable ASCII characters. We achieve this as follows.

[      While the current cell (C) is non-zero:
  <      Retrocede to the cell to C's left.
  .+     Print its content and increment.
  >++    Increment C twice.
]


32 30 29 28 27 Instructions

Changed my algorithm so we're not all trying to implement the same thing, and it's a little smaller than my earlier attempt. The code repeatedly searches through the input array, finding the smallest value, and replacing it with 0xfffffffd. It then tests if the found value is prime and outputs it if so. The code exits when the input has been completely replaced with 0xfffffffd.

    pushad
    mov     ecx, 0              ; zero output count and position
    mov     esi, [esp + 8+32]   ; load output array
find_smallest:
    mov     eax,-3              ; 0xfffffffd is larger than any valid input
    mov     edi, [esp + 4+32]   ; load input array
find_smallest_loop:
    scasd
    jbe     find_smallest_loop
    xchg    eax,[edi-4]          ; swap ecx with values that are smaller, values
                                 ; get replaced with 0xfffffffd as they are used
    cmp     eax,1
    je      find_smallest        ; skip inputs of 1
    ja      find_smallest_loop   ; exit loop if a 0 is reached
    xchg    eax,[edi-4]          ; swap 0 with lowest value found
    mov     [esi+ecx*4],eax      ; store value in next output position
    mov     ebx,2                ; ebx is divisor, start it at 2
test_next_divisor:               ; primality test
    mov     eax,[esi+ecx*4]
    cdq
    idiv    ebx                  ; use signed division
    cmp     eax,ebx
    cmovb   edx,[edi-4]          ; zero edx if prime to exit loop later on
    adc     ecx,0                ; increment output & count if prime
    inc     ebx
    test    edx,edx
    jz      find_smallest
    jns     test_next_divisor    ; exit if remainder is negative
exit_function:
    mov     [esp+28],ecx         ; move count to eax position
    popad
    ret 8


Alternative to String.fromCharCode
... if you are happy with a lowercase only alphabet.

for(i=9,a='';++i<36;)a+=i.toString(36) // 38, cannot be used in an expression
[...Array(26)].map(_=>(++i).toString(36),i=9).join`` // 52 directly returnig the string desired
[...Array(26)].map(_=>a+=(++i).toString(36),a='',i=9) // 53 assign to a variable
(i=9,[for(_ of Array(26))(++i).toString(36)].join``) // 52 ES7 direct return
i=9,a='',[for(_ of Array(26))a+=(++i).toString(36)] // 51 ES7 assign to a variable


Print out the first N characters of your code

Python 2, 61 bytes

def f(n):a='def f(n):a=%r;print(a%%a*n)[:n]';print(a%a*n)[:n]

Try it online!


R, 68 bytes

function(M,m,n,A=M){while(any(A%*%M%%m!=diag(n)))A[]=rpois(n^2,9)
A}

Try it online!

Strikingly slow. Will most likely time out for all test cases on TIO, but is guaranteed to give an answer eventually.

Works by rejection sampling: generates random matrices A, with each value taken from a \$Poisson(9)\$ distribution, until a solution is found.

Note that to get A of the correct dimensions, it is 6 bytes shorter to initialize it as A=M and then replace all the values with A[]=rpois(n^2,9) than to create it directly with A=matrix(rpois(n^2,9),n).


APL (Dyalog Unicode), 43 bytes

(1+∘÷⍣=1){'LS'[∪2</⍺|(⍺×(⍳÷⊢)2*⍵)∘.+⍳⍵]}1∘+

Try it online!
This uses the alternative formulation (actually the first one) shown in the linked paper: the closest integer staircase to the line \$y = x/\phi\$, where \$\phi\$ is the golden ratio \$\frac{\sqrt5+1}{2}\$.
Given the initial vertical offset from the line \$h\$ (which can be positive or negative), the next term (one of LS) can be determined by the following rule:

If \$h<0\$ (below the line), \$h←h+1\$ and emit S.
Otherwise (over the line), \$h←h-(\phi-1)\$ and emit L.

Since \$h-(\phi-1) = h+1-\phi\$, we can always increment and take modulo \$\phi\$ of it. Then the condition \$h<0\$ changes to \$h<\phi-1\$, but it doesn't affect the resulting sequence of terms.
Then the problem becomes to sample enough values for initial \$h\$ so that we can get all possible sequences of SL for any given length \$n\$. I choose \$2^{n+1}\$ points uniformly spaced over the interval \$[0,\phi)\$, which works for small \$n\$, and the gap size reduces faster than that induced by the collection of lines \$y=x/\phi+c\$, each passing through some lattice point inside \$0 \le x \le n\$.
Finally, I determine the actual SL terms by checking each consecutive pair: S if left < right, L otherwise, and take unique sequences.
(1+∘÷⍣=1){'LS'[∪2</⍺|(⍺×(⍳÷⊢)2*⍵)∘.+⍳⍵]}1∘+  ⍝ Input: n
(1+∘÷⍣=1){...}1∘+  ⍝ Pass n+1 and phi to the inner dfn...
⍳⍵            ⍝ Range 0..n
∘.+           ⍝ Outer product by addition...
(⍺×(⍳÷⊢)2*⍵)  ⍝ 2^(n+1) uniformly separated numbers in [0,phi)
⍺|            ⍝ Modulo phi
2</           ⍝ Pairwise comparison in row direction
              ⍝ (1 if right is higher, 0 otherwise)
∪             ⍝ Take unique rows
'LS'[...]     ⍝ Map 0, 1 to L, S


Write a function that returns an iterable object of all valid points 4-directionally adjacent to (x, y)

Python 2, 66 bytes

lambda m,n,x,y:[(x-1,y),(x+1,y)][~x:m-x]+[(x,y-1),(x,y+1)][~y:n-y]

Try it online!

Lists the four neighbors, then uses list slicing to remove those that are out-of-bounds.

Python 2, 71 bytes

lambda m,n,x,y:[(k/n,k%n)for k in range(m*n)if(k/n-x)**2+(k%n-y)**2==1]

Try it online!

Instead of checking which of the four neighbors are in-bounds, we do it the slower way of checking all in-bounds points for those that are neighbors, that is have Euclidian distance exactly 1 from (x,y). We also use the classic div-mod trick to iterate over a grid, saving the need to write two loops like for i in range(m)for j in range(n).

I tried using complex arithmetic to write the distance condition, but it turned out longer to write abs((k/n-x)*1j+k%n-y)==1.

Python 2, 70 bytes

lambda m,n,x,y:[(x+t/3,y+t%3-1)for t in-2,0,2,4if m>x+t/3>=0<y+t%3<=n]

Try it online!


Jelly, 20 15 bytes

P:ṭ×¥Ɱ"Ɗ,€"ẎṢṪ€

Try it online!

A dyadic link taking a list of initiative scores as its left argument and a list of characters as its right and returning a list of the characters in movement order.

Jelly, 14 bytes

İṭ×¥Ɱ"$,€"ẎṢṪ€

Try it online!

This version is one bytes shorter but I expect may sometimes get the order wrong because of inaccuracies in floating point calculations.


Do everything in one line.
Don't read number of test cases, scanf will return -1 on EOF
Don't include anything, pow(-1,i) can be replaced by 1-i%2*2
Do the sum loop in reverse to save a variable.

Here is my 102 bytes code

main(n){gets(&n);for(double s;s=scanf("%d",&n)>0;printf("%.15f\n",s))while(--n)s+=(1-n%2*2)/(1.+2*n);}


JavaScript (ES6), 63 bytes

(x,y,a)=>a.map(P=(v,i)=>v-y?v-x?0:a=i:1/(p=a)?P=+P||i:0)&&[P,p]

Try it online!

Commented

(x, y, a) =>          // given the two integers x, y and the array a[]
  a.map(P =           // initialize P to a non-numeric value
            (v, i) => // for each value v at position i in a[]:
    v - y ?           //   if v is not equal to y:
      v - x ?         //     if v is not equal to x:
        0             //       do nothing
      :               //     else (v = x):
        a = i         //       save the current position in a
    :                 //   else (v = y):
      1 / (p = a) ?   //     update p to a (last position of x); if p is numeric (>= 0):
        P = +P || i   //       unless P is also already numeric, update it to i
                      //       (if P is numeric, it's necessarily greater than 0 because
                      //       we've also seen x before; that's why +P works)
      :               //     else:
        0             //       do nothing
  )                   // end of map()
  && [P, p]           // return [P, p]

Alternate versions

Using JS built-ins, a more straightforward answer is 79 bytes:

(x,y,a)=>[a.indexOf(y,a.indexOf(x)),a.slice(0,a.lastIndexOf(y)).lastIndexOf(x)]

which can be slightly compressed to 75 bytes:

(x,y,a)=>[a.indexOf(y,a.indexOf(x)),a.slice(0,a[L='lastIndexOf'](y))[L](x)]

Try it online!

Edit: @Neil managed to reduce it to a very nice 67-byte:

(x,y,a,f=s=>a[z=y,y=x,x=z,s+=`ndexOf`](x,a[s](y)))=>[f`i`,f`lastI`]

Try it online!


Pen Pineapple Apple Pen... with your own pens, pineapples and apples


Print/Output all positive numbers in which every multi-digit substring in its decimal representation is also prime.

Brachylog, 18 bytes

9719⟦₁{sᶠℕ₁₀ˢṗᵐ&}ˢ

Try it online!

So...am I ready for the "bounty"? :D


MATL, 30 28 27 bytes

t:P"@:s:@/Xk&+@+8MPt&(]30+c

Try it online!

Bonus features:

For 26 bytes, the following modified version produces graphical output:

t:P"@:s:@/Xk&+@+8MPt&(]1YG

Try it at MATL Online!
The image is begging for some colour, and it only costs 7 bytes:

t:P"@:s:@/Xk&+@+8MPt&(]1YG59Y02ZG

Try it at MATL Online!
Or use a longer version (37 bytes) to see how the character matrix is gradually built:

t:P"@:s:@/Xk&+@+8MPt&(t30+cD9&Xx]30+c

Try it at MATL Online!

Example outputs

For input is 8, the following shows the basic version, graphical output, and colour graphical output.

Explanation

General procedure

A numeric matrix is built from outer to inner layers in N steps, where N is the input. Each step overwrittes an inner (upper-left) part of the previous matrix. At the end, the numbers in the obtained matrix are changed to characters.

Example

For input 4 the first matrix is

10 10  9  9  9  9  8  8  8  8
10 10  9  9  9  9  8  8  8  8
 9  9  8  8  8  8  7  7  7  7
 9  9  8  8  8  8  7  7  7  7
 9  9  8  8  8  8  7  7  7  7
 9  9  8  8  8  8  7  7  7  7
 8  8  7  7  7  7  6  6  6  6
 8  8  7  7  7  7  6  6  6  6
 8  8  7  7  7  7  6  6  6  6
 8  8  7  7  7  7  6  6  6  6

As a second step, the matrix

7 7 7 6 6 6
7 7 7 6 6 6
7 7 7 6 6 6
6 6 6 5 5 5
6 6 6 5 5 5
6 6 6 5 5 5

is overwritten into the upper half of the latter. Then the same is done with

6 5 5
5 4 4
5 4 4

and finally with

3

The resulting matrix is

3 5 5 6 6 6 8 8 8 8
5 4 4 6 6 6 8 8 8 8
5 4 4 6 6 6 7 7 7 7
6 6 6 5 5 5 7 7 7 7
6 6 6 5 5 5 7 7 7 7
6 6 6 5 5 5 7 7 7 7
8 8 7 7 7 7 6 6 6 6
8 8 7 7 7 7 6 6 6 6
8 8 7 7 7 7 6 6 6 6
8 8 7 7 7 7 6 6 6 6

Lastly, 30 is added to each entry and the resulting numbers are interpreted as codepoints and converted to characters (thus starting at 33, corresponding to !).

Construction of the intermediate matrices

For input N, consider decreasing values of k from N to 1. For each k, a vector of integers from 1 to k*(k+1) is generated, and then each entry is divided by k and rounded up. As an example, for k=4 this gives (all blocks have size k except the last):

1 1 1 1 2 2 2 2 3 3

whereas for k=3 the result would be (all blocks have size k):

1 1 1 2 2 2

This vector is added, element-wise with broadcast, to a transposed copy of itself; and then k is added to each entry. For k=4 this gives

6  6  6  6  7  7  7  7  8  8
6  6  6  6  7  7  7  7  8  8
6  6  6  6  7  7  7  7  8  8
6  6  6  6  7  7  7  7  8  8
7  7  7  7  8  8  8  8  9  9
7  7  7  7  8  8  8  8  9  9
7  7  7  7  8  8  8  8  9  9
7  7  7  7  8  8  8  8  9  9
8  8  8  8  9  9  9  9 10 10
8  8  8  8  9  9  9  9 10 10

This is one of the intermediate matrices shown above, except that it is flipped horizontally and vertically. So all that remains is to flip this matrix and write it into the upper-left corner of the "accumulated" matrix so far, initiallized to an empty matrix for the first (k=N) step.

Code

t       % Implicitly input N. Duplicate. The first copy of N serves as the
        % initial state of the "accumulated" matrix (size 1×1). This will be
        % extended to size N*(N+1)/2 × N*(N+1)/2 in the first iteration
 :P     % Range and flip: generates vector [N, N-1, ..., 1]
"       % For each k in that vector
  @:    %   Push vector [1, 2, ..., k]
  s     %   Sum of this vector. This gives 1+2+···+k = k*(k+1)/2
  :     %   Range: gives vector [1, 2, ..., k*(k+1)/2]
  @/    %   Divide each entry by k
  Xk    %   Round up
  &+    %   Add vector to itself transposed, element-wise with broadcast. Gives
        %   a square matrix of size k*(k+1)/2 × k*(k+1)/2
  @+    %   Add k to each entry of the this matrix. This is the flipped
        %   intermediate matrix
  8M    %   Push vector [1, 2, ..., k*(k+1)/2] again
  Pt    %   Flip and duplicate. The two resulting, equal vectors are the row and
        %   column indices where the generated matrix will be written. Note that
        %   flipping the indices has the same effect as flipping the matrix
        %   horizontally and vertically (but it's shorter)
  &(    %   Write the (flipped) intermediate matrix into the upper-left
        %   corner of the accumulated matrix, as given by the two (flipped)
        %   index vectors
]       % End
30+     % Add 30 to each entry of the final accumulated matrix
c       % Convert to char. Implicitly display


Ruby, 58 bytes

This is a straightforward implementation of the algorithm in Releasing Helium Nuclei's C answer.

g=->m,n{n>m ?g[n,m]:m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6}

I have been investigating why this formula works, with limited success. It's easy to confirm that the number of upright rectangles is equal to (m+1)*m/2 * (n+1)*n/2, the number of diagonal rectangles is a little more elusive.

Neil has confirmed for m==n that the number of tilted rectangles in an n*n square is (4*n**4-n*n-3*n)/6 and that when m>n you need to add an additional (m-n)(n*(4*n*n-1)/3) (related to OEIS A000447), though this does not explain where those two formulas came from. I have found part of the answer.

For m==n, the shape inside the grid is an Aztec diamond.

The number of rectangles in an Aztec diamond is the sum of number of large rectangles superimposed to make it (for the fourth diamond, which is found in a 5x5 grid, 2x8, 4x6, 6x4, and 8x2) minus the number of the rectangles counted twice (the number of rectangles in the previous Aztec diamond).

The formula here is (TeX to be added later):

# superimposed rectangles, 2x(2n-2), 4*(2n-4), ...
f = lambda n: sum( (2*k)*(2*k+1)/2 * (2*n-2*k)*(2*n-2*k+1)/2 for k in range(1, n) )
aztec_rect = f(n) - f(n-1)

According to Wolfram Alpha, the closed form for f is 1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9) and the closed form for aztec_rect is, as Neil discovered, 1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n).

I have yet to discover why (m-n)(n*(4*n*n-1)/3) works, though I suspect that it is because one definition of A000447 is binomial(2*n+1, 3). I will keep you posted.

Update: I have reason to believe that the function of the number of rectangles in an extended Aztec diamond m>n is related to the number of superimposed 2k*2(n-k) rectangles in the diamond minus F(m-1,n-1). More results when I have them.

Update: I tried a different route and ended up with another formula for extended Aztec diamonds that is mostly explainable but has one term that I don't yet understand. Huzzah! :D

def f(m,n):
 if n > m:
     return f(n,m)
 if n == 0:
     return 0
 else:
     return(m-n+1)*(4*n**4-n*n-3*n)/6-f(m-1,n-1)+(m-n)*2+(m-n)*(n-2)-(m-n-1)*f(n-1,n-1)

A quick breakdown of that last formula:

(m-n+1)*(4*n**4-n*n-3*n)/6 is the number of superimposed Aztec diamonds of size n in the structure, as f(n,n) = (4*n**4-n*n-3*n)/6. f(7,3) has 5 superimposed Aztec diamonds size 3, while f(3,3) has only 1 diamond.
-f(m-1,n-1) removes some of the duplicate rectangles from the middle of the superimposed diamonds.
+(m-n)*2 accounts for 2 extra 2-by-(2n-1) rectangles for each extra diamond.
+(m-n)*(n-2) accounts for an extra n-by-n square for each extra diamond.
-(m-n-1)*f(n-1,n-1) This is the new puzzling term. Apparently I have not accounted for some extra squares in my counting, but I haven't figured out where they are in the extended diamond.

Note: when m==n, m-n-1 = -1, meaning that this last term adds squares to the counting. I might be missing something in my regular formula. Full disclosure, this was only meant to be a patch to an earlier draft of this formula that just happened to work. Clearly, I still need to dig into what's going on, and it may be that my formula has some bugs in it. I'll keep you posted.

Russell, Gary and Weisstein, Eric W. "Aztec Diamond." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/AztecDiamond.html


C

Since input is limited to positive integers between 1 and 1010, I can use a well-known fast inverse square root algorithm to find the inverse square root of the reciprocal of the input.

I'm not sure what you mean by "only Xfce and the program and a terminal running" but since you stated that functions are acceptable, I provide a function in C that will take an integer argument (that will be casted to float automatically) and outputs a float as the result.

float f(float n) {
    n = 1.0f / n;
    long i;
    float x, y;

    x = n * 0.5f;
    y = n;
    i = *(long *)&y;
    i = 0x5f3759df - (i >> 1);
    y = *(float *)&i;
    y = y * (1.5f - (x * y * y));

    return y;
}

The following is a program that makes uses of the function above to calculate the square roots of the given test cases and compares them to the values given by the sqrtf function in math.h.

Ideone


Score an asynchronous prisoner's dilemma game

Haskell, 139 134 bytes

g=filter
(n!m)(a,b)=(a+n,b+m)
f s=init$tail$show$foldr id(0,0)$zipWith(#)(g(>'a')s)$g(<'E')s
'c'# 'C'=1!1
'c'#_=3!0
_# 'D'=2!2
_#_=0!3

Usage example: f "cDCddDDCcCc" ->  "9,6"

15 bytes just to get the output format right, i.e. turning a pair of numbers (x,y) into a string "x,y".

How it works:

               g(>'a')s        -- extract all lowercase letters
                     g(<'E')s  -- extract all uppercase letters
         zipWith(#)            -- combine both lists element wise with function #
                               -- # calls ! depending on the combination of c/d/C/D
                               -- ! takes 2 numbers a and b and returns a function
                               -- that takes a pair (x,y) and returns (x+a,y+b)
                               -- now we have a list of such functions
    foldr id(0,0)              -- apply those functions starting with (0,0)
init$tail$show                 -- format output

Edit: @Zgarb helped me saving 5 bytes. Thanks!


Decomposition of a matrix in \$ SL_2(\mathbb{Z}) \$

JavaScript (ES6), 68 bytes
This is using xnor's method -- but obviously without complex numbers.
Takes the input matrix \$\begin{pmatrix}a&b\\c&d\end{pmatrix}\$ as 4 distinct parameters a,b,c,d.
Returns a string of digits (\$0\$ for \$S\$, \$1\$ for \$T\$).

f=(a,b,c,d)=>b|c|a-1|d-1?a*c>-b*d?1+f(a-c,b-d,c,d):0+f(c,d,-a,-b):''

Try it online!

JavaScript (ES6),  114 110  108 bytes
Takes the input matrix \$\begin{pmatrix}a&b\\c&d\end{pmatrix}\$ as a 4-element vector [a,b,c,d].
Returns a string of digits (\$0\$ for \$S\$, \$1\$ for \$T\$).
Brute forces a solution, which is guaranteed to be as short as possible, except for the identity matrix.

f=(M,i=0)=>(F=(a,b,c,d,s='')=>s[i]?a+[,b,c,d]==M&&s:F(a,a+b,c,c+d,s+1)||F(b,-a,d,-c,s+0))(1,0,0,1)||f(M,i+1)

Try it online!
Commented
f = (                      // f = wrapper function taking:
  M,                       //   M[] = input vector
  i = 0                    //   i   = maximum number of iterations (-1)
) => (                     //
  F = (                    // F is a recursive function taking:
    a, b, c, d,            //   the current matrix as 4 distinct parameters
    s = ''                 //   s = output string
  ) =>                     //
    s[i] ?                 // if we've reached the maximum length:
      a + [, b, c, d] == M //   if [a, b, c, d] matches the input matrix:
        && s               //     return s
    :                      // else:
      F(                   //   try a first recursive call
        a,                 //     where the matrix is multiplied by T
        a + b,             //     [ a b ]   [ 1 1 ]   [ a a+b ]
        c,                 //     [ c d ] x [ 0 1 ] = [ c c+d ]
        c + d,             //
        s + 1              //     append '1' to s
      ) ||                 //
      F(                   //   try a second recursive call
        b,                 //     where the matrix is multiplied by S
        -a,                //     [ a b ]   [ 0 -1 ]   [ b -a ]
        d,                 //     [ c d ] x [ 1  0 ] = [ d -c ]
        -c,                //
        s + 0              //     append '0' to s
      )                    //
)(1, 0, 0, 1)              // initial call to F with the identity matrix
|| f(M, i + 1)             // if it fails, try again with i + 1


Retina, 19 + 2 = 21 bytes

Retina strikes again! The code for this program consists of two files:

i`([b-z-[eiou]])o.

$1

This reads the input on STDIN and prints the output to STDOUT.

If you call the files pattern.rgx and replacement.rpl, you can run the program simply like

echo "hohelollolo" | ./Retina pattern.rgx replacement.rpl

Explanation

As for the previous answer, if Retina is invoked with 2 files it is automatically assumed to operate in "Replace mode", where the first file is the regex and the second file is the pattern.

Retina can be configured (which includes RegexOptions and other options) by prepending the regex with ` and a configuration string. In this case I'm only giving it i which is the normal regex modifier for case insensitivity.

The pattern itself is a bit more interesting this time. It still uses .NET's character class subtraction to match any consonant in the ASCII range, but then it also matches the following o as well as the character after it (i.e. the copy of the consonant). The replacement then just writes the captured consonant back.

You might be wondering why this is not ambiguous in a case like lololol -> lol. The trick is that matches cannot overlap and are always found from left-to-right. So whenever I encounter a consonant, I include the next two character in the match and replace all of them - the search continues after this. It's quite easy to convince yourself that this kind of greedy algorithm will always decode the input correctly. In fact the pattern could even have been

i`([b-z-[eiou]])..


Java and C#, 62 bytes

Object f(String s,int n){return n<1?s:new Object[]{f(s,n-1)};}

Should work without modification in both Java and C#.


Ruby, 88 bytes
Port from the Python answer by @Blue with a few modifications because it's still the shortest way to do things in Ruby as well...
->s{o=e='  ';(s[x=rand(s.size-2),2]==o[-2,2]?o+=s[x+2]:0)while o.size<100||o[-2,2]!=e;o}

Alternate version using selection and sampling, 99 bytes
->s{o=e='  ';o+=s[(0..s.size-2).select{|i|s[i,2]==o[-2,2]}.sample+2]while o.size<100||o[-2,2]!=e;o}


Python 2, 224 bytes
from difflib import SequenceMatcher
def similar(a, b):
    return SequenceMatcher(None, a, b).get_matching_blocks()
a=raw_input()
b=raw_input()
for start, _, size in similar(a, b):
 if(size > 9):
  print a[start:start+size]

Copied from this answer:
from difflib import SequenceMatcher
def similar(a, b):
    return SequenceMatcher(None, a, b).

get_matching_blocks() is copied from this answer
a=raw_input()
b=raw_input()

is copied from this question
for start, _, size in is copied from this answer and the second occurence of similar(a, b) is copied from the same place as the first.
if(size > 9) is copied from this question.
:
    print

is copied from this question
a[start: is copied from this answer.
and finally, start+size] is copied from this questipn
Finally answered after one and a half years ...


Extrude the faces of a cube symmetrically along XYZ

JavaScript (ES6),  525 ... 475 471  459 bytes
Saved 13 bytes thanks to @Neil
Takes input as an array [X,Y,Z]. Returns a matrix of characters.
a=>([X,Y,Z]=a,m=[],W=X*6+Z*2,'1uol9h824lsqpq17de52u1okgnv21dnjaww111qmhx1gxf4m50xg6pb42kzijq21xyh34t0h2gueq0qznnza2rrimsg3bkrxfh3yrh0em').replace(/.{7}/g,s=>[[c,x,A,y,B,w,C,h,D,t]=parseInt(s,36)+s,Y*W,Z,X,Y|!W,Z*X,X*Y*!Z,X*Z*!Y,Y*Z*!X][c]&&(g=H=>V<h&&((m[r=y-(3-B)*p+(t>1?H-V:V)+Y*3+Z*2]=m[r]||Array(W*2+9).fill` `)[x-2*(3-A)*p+(t>1?V:H-V*t)+W]=` ${c>5?'  + ':t>1?'|-':'-|'}+/+`[(H%~-w?0:+t?4:2)|!(V%~-h)],g(++H<w?H:!++V)))(V=0,p=a[c%3],w-=-3*C*p,h-=-D*p))&&m

Try it online!
How?
Drawing steps
The output consists of 15 sides, drawn in a specific order.

Implementation
The drawing function is \$g\$. It works with the following parameters:

\$(x, y)\$: where to start drawing
\$w\$: width
\$h\$: height
\$t\$: type of side

The vertices are always drawn. Depending on the value of another parameter \$c\$, the edges are either drawn or erased.
If \$t=0\$, the function draws a front side:
...........      ...........
..+-----+..      ..+     +..
..|     |..  or  ..       ..
..|     |..      ..       ..
..+-----+..      ..+     +..
...........      ...........

If \$t=1\$, it draws a top side:
...........      ...........
...+-----+.      ...+     +.
../     /..  or  ..       ..
.+-----+...      .+     +...
...........      ...........

If \$t=2\$, it draws a right side:
......+....      ......+....
...../|....      .....  ....
....+ |....  or  ....+  ....
....| +....      ....  +....
....|/.....      ....  .....
....+......      ....+......

The coordinates \$(x,y)\$ and the size \$(w,h)\$ of each side either have a constant value or depend on exactly one of the input variables: \$X\$, \$Y\$ or \$Z\$. Besides, each side is drawn if and only if a specific condition is met.
Both the input variable to use and the condition to check are identified with the parameter \$c \in[1..8]\$.
To summarize, a side is fully described with:
$$\begin{cases}
c\\
t\\
x=o_x+m_x\times P\\
y=o_y+m_y\times P\\
w=o_w+m_w\times P\\
h=o_h+m_h\times P
\end{cases}
$$
where \$P\$ is the input variable deduced from \$c\$.
Therefore, we need to store the following 10 parameters for each side:
$$[c, o_x, m_x, o_y, m_y, o_w, m_w, o_h, m_h, t]$$
Below are the parameters of the 15 sides that need to be drawn:
$$\begin{array}{|c|c|}
\hline
\text{side} & c & o_x & m_x & o_y & m_y & o_w & m_w & o_h & m_h & t\\
\hline
0 & 4 & 0 & 0 & 2 & -3 & 7 & 0 & 4 & 6 & 0\\
1 & 4 & 6 & 0 & 2 & -3 & 4 & 6 & 3 & 0 & 2\\
2 & 2 & 6 & -2 & 2 & 2 & 4 & 0 & 3 & 4 & 2\\
3 & 3 & 6 & 6 & 2 & 0 & 4 & 0 & 3 & 0 & 2\\
4 & 3 & 0 & -6 & 2 & 0 & 7 & 12 & 4 & 0 & 0\\
5 & 2 & 2 & 2 & 0 & -2 & 7 & 0 & 3 & 4 & 1\\
6 & 3 & 2 & -6 & 0 & 0 & 7 & 12 & 3 & 0 & 1\\
7 & 2 & 0 & -2 & 2 & 2 & 7 & 0 & 4 & 0 & 0\\
8 & 5 & 6 & -2 & 2 & 2 & 4 & 0 & 1 & 2 & 2\\
9 & 4 & 2 & 0 & 0 & -3 & 7 & 0 & 3 & 0 & 1\\
10 & 1 & 0 & 0 & 2 & -3 & 7 & 0 & 1 & 3 & 0\\
11 & 1 & 6 & 0 & 2 & -3 & 1 & 3 & 3 & 0 & 2\\
12 & 6 & 0 & 0 & 2 & 0 & 7 & 0 & 4 & 0 & 0\\
13 & 7 & 2 & 0 & 0 & 0 & 7 & 0 & 3 & 0 & 1\\
14 & 8 & 6 & 0 & 2 & 0 & 4 & 0 & 3 & 0 & 2\\
\hline
\end{array}$$
We force all values into the range \$[0..9]\$ by applying the following operations:
$$m_x\gets (m_x+6)/2\\
m_y\gets m_y+3\\
m_w\gets m_w/3$$
It results in 15 numbers of exactly 10 decimal digits, which are stored as 15 groups of 7 digits in base 36.
For instance, the first side is encoded as 4032070460 and stored as 1uol9h8.


APL (Dyalog Unicode), 72 bytes
{⍵=1:⍳2⋄(2*⌈⍵÷2)(⌷⌹⍉⍤↑)⍉L↑⍉↑,¨+.×\(L←2*⍵)⍴⊂∘.((0∊+)⍱1∊2|×≢¨⍤⊆⊣)⍨⍸1⍴⍨⍵⍴2}

Try it online! (uses a polyfill for ⍤ since TIO is not updated to 18.0 yet)
Requires ⎕pp←2 (implicit rounding of output) and ⎕IO←0 (0-indexing).
We compute a transition matrix, then use the approach listed in S. Białas and M.Białas to find the minimum polynomial and hence the recurrence relation.
Defining the Transition Matrix
Each possible binary fill of a column of \$m\$ cells is one state, so there are \$2^m\$ states.
For m=3, one example state (1 0 0) is
█
▒
▒

The first cell is filled (it is the right side of a horizontal domino sticking out from the previous column), but the second and third cells are empty. This could occur e.g. as the second column in the following tiling (n=4, 3×4 grid):
━━┃┃
┃┃┃┃
┃┃━━

When considering state transitions, we have to be careful to avoid double counting.
My approach is to require full horizontal dominos to be placed whenever possible, then vertical dominos can optionally be placed in the next state's column.
For example, if the current state is 1 0 0:
█
▒
▒

then we force horizontal dominos on the bottom two rows
█▒
━━
━━

so the next state would have to be 0 1 1:
▒
█
█

This rule guarantees the current column to be filled in completely. In addition, it avoids double-counting transitions because it never places vertical dominos in the current column.
Vertical dominos go in the next column. There is no space for vertical dominos in the past example. As an example where vertical dominos can be placed, take the current state to be 1 1 1:
█▒
█▒
█▒

One possibility would be to place no vertical dominos at all, so 1 1 1 → 0 0 0 is a valid state transition.
In addition, a vertical domino can be placed in either of two positions:
█┃        █▒
█┃   or   █┃
█▒        █┃

so 1 1 1 → 1 1 0 and 1 1 1 → 0 1 1 are valid state transitions.
Obtaining the Recurrence from the Transition Matrix.
The paper describes the approach well, but I modified it a little while golfing.
As given, the problem is to find coefficients \$a_i\$ for a given recurrence order \$k\$ such that, for all \$n\$¸
$$a_0 D_m(n) + a_1 D_m(n+1) + \cdots + a_{k-1}D_m(n+k-1) = D_m(n+k)$$
With regards to powers of the transition matrix \$A\$, this can be rewritten as finding coefficients $c_i$ such that
$$c_1 A^1 + c_2 A^2 + \cdots + c_k A^k = A^{k+1}$$
(the paper starts with \$A^0=I_L\$, but that is expensive in terms of bytes)
Let \$L=2*m\$ be the width (and height) of the transition matrix \$A\$. Denoting the entries of \$A^i\$ as \$a_{11}^{(i)}, a_{12}^{(i)}, \ldots a_{LL}^{(i)}\$, we can rewrite the recurrence as \$L^2\$ equations
$$
\begin{align*}
c_1 a_{11}^{(1)} + c_2 a_{11}^{(2)} + &\cdots + c_k a_{11}^{(k)} = a_{11}^{(k+1)} \\
c_1 a_{12}^{(1)} + c_2 a_{12}^{(2)} + &\cdots + c_k a_{12}^{(k)} = a_{12}^{(k+1)} \\
&\;\;\,\vdots \\
c_1 a_{LL}^{(1)} + c_2 a_{LL}^{(2)} + &\cdots + c_k a_{LL}^{(k)} = a_{LL}^{(k+1)}
\end{align*}
$$
Treating \$a_{hi}^{(j)}\$ as constants (since we know \$A\$), this is a system of \$L^2\$ equations in \$k\$ variables \$c_i\$.
Let \$B\$ be the augmented matrix for this massive system of equations for \$k=L\$. Solving the full \$B\$ would give a recurrence of order \$L=2^m\$, but we need a smaller recurrence.
To find a smaller recurrence, we simple use a smaller \$k\$. The bulk of the paper is in proving that the minimum possible \$k\$ is the rank of \$B\$. However, for this specific problem, the minimum \$k\$ is \$k_0=2^{\lceil \frac{m}{2} \rceil}\$ (Source --- floor since the row \$k\$ has \$m=k-1\$). Thus we can take the \$k_0 \times (k_0+1)\$ submatrix at the top left of \$B\$ and solve it to find the \$k_0\$ coefficients of a useful recurrence.
{⍵=1:⍳2⋄(2*⌈⍵÷2)(⌷⌹⍉⍤↑)⍉L↑⍉↑,¨+.×\(L←2*⍵)⍴⊂∘.((0∊+)⍱1∊2|×≢¨⍤⊆⊣)⍨⍸1⍴⍨⍵⍴2}
{...} ⍝ Dfn with right argument m
⍵=1:⍳2⋄ ⍝ Special case m=1: return [0 1]
⍝ Compute the transition matrix A:
 ⍸1⍴⍨⍵⍴2  ⍝ All 2^m states: cartesian m-th power of [0 1]
            ⍝ (m=1 yields a vector of scalars rather than vectors, which is why we need a special case for m=1)
 ∘.{...}⍨ ⍝ Outer product with itself (all current→next state pairs) using function:
  ⍱         ⍝ Neither of the following are true:
  (0∊+)       ⍝ 0→0 in mapping (invalid since we require a horizontal domino when the current state has a 0)
  1∊2|×≢¨⍤⊆⊣  ⍝ Some run of 1→1 has odd length (requires a half vertical domino, impossible)
⍝ Compute the minimal polynomial of A
 +.×\(L←2*⍵)⍴⊂ ⍝ Produce matrix powers of A: A, A*2, ... A*L, where L=2*m
 ↑,¨           ⍝ B: Ravel each (Vec A*k) and join into single (L×L) × L matrix
 ⍉L↑⍉          ⍝ B': Trim to first L rows (for numerical stability in later gauss-jordan elimination)
 (2*⌈⍵÷2) ⍝ Rank r
 ⌷⌹⍉⍤↑ ⍝ Compute recurrence coefficients α←first r entries of b˜÷B̃
  ⍉⍤↑   ⍝ B̃: columns 0 to r-1, inclusive, of B' (taller than B̃ in paper)
  ⌷     ⍝ b˜: r-th column of B' (taller than b˜ of paper)
  ⌹     ⍝ matrix divide b˜÷B̃ to get coefficients


How much reputation does a steam user have?

Python 3, 73 bytes

I'm sure this answer is garbage and will be beaten soon, but there's no other python answers yet

lambda x:sum(["- +".index(i[0])-1for i in x.split('\n')if i[1:4]=="rep"])

Use like this:

f = lambda x:sum(["- +".index(i[0])-1for i in x.split('\n')if i[1:4]=="rep"])
print(f("PUT INPUT HERE"))

Fetching from steam

Here's some sample code which fetches the first 100 comments from KennyS' profile and calculates his rep.

import requests
from bs4 import BeautifulSoup

# Kenny's profile as Steam ID 64
# You can adjust this to whatever numbers you want
STEAM_PROFILE_URL = "76561198024905796"
payload =  {"start" : 0, "count" : 100}
r = requests.post("http://steamcommunity.com/comment/Profile/render/{}/-1/".format(STEAM_PROFILE_URL), payload)

# Comments are html inside a json object
soup = BeautifulSoup(r.json()["comments_html"], "html.parser")

# Get raw text for every comment.
# The " ".join() strips out the newlines and tabs which are part of html
comments = [" ".join(s.text.split()) for s in soup.find_all("div", {"class" : "commentthread_comment_text"})]

calculateRep = lambda x:sum(["- +".index(i[0])-1for i in x.split('\n')if i[1:4]=="rep"])

print(calculateRep("\n".join(comments)))


SVG

1kB? Luxury. I can even pretty-print the output rather than removing all unnecessary whitespace. (The indentation does, of course, use tabs, which Markdown converts to spaces, so that's why the char count might seem higher than the actual 977. Removing unnecessary whitespace drops it to 861).

The overlaps are handled correctly by drawing the rings in one direction, then applying a clip and drawing them in the other direction. The colours and ratios are extracted from an official document which for some reason uses Bézier curves rather than circles.

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="504" height="228">
    <defs>
        <clipPath id="t">
            <rect width="504" height="114" />
        </clipPath>
    </defs>
    <g fill="none" stroke-width="12">
        <g id="u" transform="translate(82,82)" stroke="#0b8ed8">
            <g id="O">
                <circle r="72" stroke="#fff" stroke-width="20" />
                <circle r="72" />
            </g>
        </g>
        <g id="y" transform="translate(167,146)" stroke="#f9a91f">
            <use xlink:href="#O" />
        </g>
        <g id="k" transform="translate(252,82)" stroke="#231f20">
            <use xlink:href="#O" />
        </g>
        <g id="g" transform="translate(337,146)" stroke="#009e59">
            <use xlink:href="#O" />
        </g>
        <g transform="translate(422,82)" stroke="#ee2049">
            <use xlink:href="#O" />
        </g>
        <g clip-path="url(#t)">
            <use xlink:href="#g" />
            <use xlink:href="#k" />
            <use xlink:href="#y" />
            <use xlink:href="#u" />
        </g>
    </g>
</svg>


Python 2, 275 268 267 bytes

d=['']*256
d[48:58]='zero one two three four five six seven eight nine'.split()
d[9]=d[10]=d[32]='white_large_square'
d[65:90]=d[97:122]=map(lambda c:'regional_indicator_'+chr(c),range(97,122))
print' '.join((':%s:'%d[ord(c)])*(d[ord(c)]!='')for c in input()).strip()

It creates a large list of strings, iterates through the input string's characters and gets the string from the list using the character's ord value.
Works for ascii characters only. Replaces space, tab and newline only; any other whitespace will be discarded.

It did leave whitespaces in front so I had to strip it in the end.

I also tried doing it with regex, turned out to be longer (286 bytes):

import re
print re.sub('([ \t\n])|([a-z])|(\d)',lambda m:':'+['white_large_square','regional_indicator_'+m.group(m.lastindex),'zero one two three four five six seven eight nine'.split()[(ord(m.group(m.lastindex))-68)%10]][m.lastindex-1]+': ',re.sub('[^a-z0-9 \t\n]','',input().lower()))


Python 2, 67 62 60 59 bytes

n=input()
try:print bin(int(n,n[1]<'x'))[2:]
except:print 0

Try it online!

Version that errors on invalid input (27 bytes):

lambda n:bin(int(n,16))[2:]

Try it online!


Binary representation of a number is palindrome or not?

Python - 46 chars

n=bin(input())[2:]
print'YNEOS'[n!=n[::-1]::2]


Collatz sequence on a two counter machine

18 instructions

I was a bit disappointed that I arrived late on scene, as the minimalistic nature of the problem and the language make there (seemingly) only one general approach for a good answer. I got a 19-instruction answer fairly quickly, but I didn't feel like it brought enough to the table to post it. But after much head scratching, my hacky z80 assembly experience came through and I found a way to save an instruction by reusing a block of code for a purpose it wasn't meant for!

# Let N be the previous number in the Collatz sequence.

# Print N, and if N==1, halt.
# X=N, Y=0
Main:           PRINTX          # Print N.
                DJZX Done       # X=N-1 (N shouldn't be zero, so this never jumps)
                DJZX Done       # If N-1==0, halt. Otherwise, X=N-2.

# Find the parity of N and jump to the proper code to generate the next N.
# X=N-2, Y=0
FindParity:     INCY
                DJZX EvenNext   # If N%2==0, go to EvenNext with X=0, Y=N-1.
                INCY
                DJZX OddNext    # If N%2==1, go to OddNext with X=0, Y=N-1.
                JMP FindParity

# Find the next N, given that the previous N is even.
# X=0, Y=N-1
EvenNext:       INCX
                DJZY Main       # Y=Y-1 (Y should be odd, so this never jumps)
                DJZY Main       # If Y==0, go to Main with X=(Y+1)/2=N/2, Y=0.
                JMP EvenNext

# Find the next N, given that the previous N is odd.
# X=0, Y=N-1
OddNext:        INCX
                INCX
                INCX
                DJZY EvenNext   # If Y==0, go to EvenNext with X=(Y+1)*3=N*3, Y=0.
                JMP OddNext     # ^ Abuses EvenNext to do the final INCX so X=N*3+1.

# Halt.
Done:           HALT


Write the shortest program that generates the most compiler warnings and errors

GCC, score 2200 / 36 ≈ 4.5 × 1058

#include __FILE__
#include __FILE__

I have not actually finished compiling this code, but based on testing and simple mathematics, it should produce a total of 2200 #include nested too deeply errors.

Of course, the program is trivially extensible.  Adding a third line brings the score up to 3200 / 54 ≈ 4.9 × 1093.  Four lines give 4200 / 72 ≈ 3.6 × 10118, and so on.


Python 2, 5 bytes (cracked by tsh)

bin()

Try it online!
Banned: all characters except alphanumeric characters
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789

So, you're allowed the above characters and nothing else (in addition to bin() itself).
(This idea isn't mine, I remember it from an earlier challenge, but I don't remember who deserves credit for it.)


J, 37 bytes
Brute forces through the possible sets, outputs the bit mask.
((-&.#.+./@,)[(e.~+/~)/.*:@#\)^:_@#&1

Try it online! (Also outputs list as numbers for easier comparison.)
How it works
((-&.#.+./@,)[(e.~+/~)/.*:@#\)^:_@#&1
                                  #&1 convert to list of N 1's
(                            )^:_     do until list does not change
                        *:@#\         right: convert to 1,4,9…,N^2
             [                        left: the bit mask
                      /.              partition left based on right, for each set:
                  +/~                 make M*M addition table
               e.~                    any element of that in the same set?
       +./@,                          OR all answers: 1 on conflict, 0 if finished
  -&.#.                               list: from base 2, subtract that^, to base 2


Recreate an xkcd graph procedurally with your favorite plotting tool

Here's a stab.

Postscript

[Count deleted because this isn't a golf question.]

Added a "style" section to make it look more hand-drawn.

Edit: Helvetica responds better than Courier. Tweaked and enhanced this "style" section. And added comments.

%!

%futz with a coordinate pair
/f { 2 { rand 100 mod 100 div 1.47 mul
        dup .4 mul sub add
        exch } repeat } def

/op 2 array def %original point
/cp 2 array def %current point
/setcp { 2 copy cp astore pop } def %set current point
/difcp { cp aload pop %x' y' x y   %diff between cp and point on stack
    3 2 roll exch sub %x' x y'-y
    3 1 roll sub %y'-y x'-x
    exch %dx dy
} def
/scale2 { /n exch def  %scale two values
    n mul exch n mul exch
} def
/add2 {
    3 2 roll add
    3 1 roll add exch
} def
%futz with a path
/fpath {
    2 {
    %flattenpath
    % replace lines with curves
    [ { setcp cp op copy pop /moveto cvx }
        {
            %cp aload pop 4 2 roll 2 copy
            2 copy difcp %x3 y3 x30 y30
            2 copy 1 4 div scale2 %x3 y3 x30 y30 (1/3)x30 (1/3)y30
            cp aload pop add2 %x3 y3 x30 y30 x1 y1
            4 2 roll 3 4 div scale2 %x3 y3 x1 y1 (2/3)x30 (2/3)y30
            cp aload pop add2 %x3 y3 x1 y1 x2 y3
            6 4 roll %x1 y1 x2 y2 x3 y3
            setcp
            /curveto cvx }
        { setcp /curveto cvx }
        { op cp copy pop /closepath cvx } pathforall ] cvx newpath exec
    % chop the curves
    flattenpath
    % futz all the points
    [ { f
        /moveto cvx }
        { f
            /lineto cvx }
        { %f
            f 6 2 roll
            f 6 2 roll
            f 6 2 roll
            2 copy
            /curveto cvx
            3 1 roll
            3{f}repeat /lineto cvx % extra triple-futz'd line after each curve
        }
        { /closepath cvx } pathforall ] cvx newpath exec
    } repeat
} def

%futz with strokes
/oldstroke /stroke load def
/stroke { fpath oldstroke } def

%futz with fills
/oldfill /fill load def
/fill { fpath oldfill } def

%make sure rectstroke doesn't bypass being futzed with
/rectstroke {
    4 2 roll moveto
    1 index 0 rlineto
    0 exch rlineto
    neg 0 rlineto
    closepath
    stroke
} def

%futz with strings
%by making sure show uses our futz'd fill
/show { gsave currentpoint newpath moveto dup
    false charpath 1{fpath}repeat fill grestore stringwidth rmoveto } def

%fatter lines
1 setlinejoin %round joins
currentlinewidth 1.9 mul setlinewidth
%chop curves very small so there's lots of points for futzing
currentflat 6 div setflat

/Helvetica 10 selectfont

<<
/in{72 mul}
>>begin
1 in 1 in translate

0 0 6 in 4 in rectstroke
1 in 3 in moveto (WALKING BACK TO MY) show
1 in 2.8 in moveto (FRONT DOOR AT NIGHT:) show

36 3.5 in moveto
0 -2.8 in rlineto
5 in 0 rlineto
3.45 in .55 in moveto
0 20 rlineto
4.05 in .55 in moveto
0 20 rlineto
2.7 in .40 in moveto
(YARD  STEPS DOOR  INSIDE ) show
0 .05 in rmoveto
.4 in 0 rlineto
currentpoint
stroke
moveto
-10 3 rlineto
0 -6 rlineto fill

2.6 in .45 in moveto
-2 in 0 rlineto
currentpoint
stroke
moveto
10 3 rlineto
0 -6 rlineto fill

(FEAR) .9 in 2.3 in moveto show
(THAT THERE'S) .9 in 2.1 in moveto show
(SOMETHING) .9 in 1.9 in moveto show
(BEHIND ME) .9 in 1.7 in moveto show
1.8 in 1.86 in moveto
2 -26 rlineto
stroke

(FORWARD) 2.2 in 2.1 in moveto show
(SPEED) 2.2 in 1.9 in moveto show
2.75 in 2 in moveto
3 -13 rlineto
stroke

(EMBARRASSMENT) 4.5 in 2.5 in moveto show
4.6 in 2.65 in moveto
-2 20
-5 22
-27 25 rcurveto
stroke

.6 setgray %gray
40 1.6 in moveto
2.7 in 0
2.9 in 20
3.2 in 1.5 in rcurveto
10 20
20 20
30 0 rcurveto
15 -1.7 in
30 -1.8 in
1.4 in -2 in rcurveto
stroke

0 0 1 setrgbcolor %blue
40 1.2 in moveto
.9 in 27
.8 in 20
1.4 in 21 rcurveto
1 in -20
1.2 in 6
1.3 in 1.6 in rcurveto
    10 20
    20 20
    30 0 rcurveto
15 -1.8 in
30 -1.9 in
1.8 in -2.1 in rcurveto
stroke

1 0 0 setrgbcolor %red
40 .9 in moveto
3.3 in 0
3.5 in 20
3.6 in 1.5 in rcurveto
10 72
20 80
30 80 rcurveto
.7 in -10
.3 in -35
1.1 in -40 rcurveto
stroke

%thank you for scrolling all the way down to here. :)


JavaScript (ES6), 345 342 bytes

Saved 2 bytes thanks to @StephenLeppik

n=>[...'lmnopqsuvwxyz{}~'].reduce((s,c)=>(x=s.split(c)).join(x.pop()),` p{{yyvu{ xvs${(n&&n<60?n+'':(k=n||new Date/6e4|0,k/60%(n?k:12)|0||(n?0:12))+':'+('0'+k%60).slice(-2)).padEnd(9)}xoup__uuxx{~zzn1s2s3wn4s5s6wn7s8s9wuuq 0sStartmy_~ { oxp__zxllx{|x
|p{_|{y_|qox}}}uzs}uuuuu {yyy__z|u y___s|wm|y~zzv
|}}}}xu  sx q~|p{{{ox
znzq m qy|ylx}|xv`)

Test cases

let f =

n=>[...'lmnopqsuvwxyz{}~'].reduce((s,c)=>(x=s.split(c)).join(x.pop()),` p{{yyvu{ xvs${(n&&n<60?n+'':(k=n||new Date/6e4|0,k/60%(n?k:12)|0||(n?0:12))+':'+('0'+k%60).slice(-2)).padEnd(9)}xoup__uuxx{~zzn1s2s3wn4s5s6wn7s8s9wuuq 0sStartmy_~ { oxp__zxllx{|x
|p{_|{y_|qox}}}uzs}uuuuu {yyy__z|u y___s|wm|y~zzv
|}}}}xu  sx q~|p{{{ox
znzq m qy|ylx}|xv`)

O.innerText = [100, 59, 60, 120, 59999999, 1, 0].map(f).join('\n');


Python 3, 66 61 bytes

lambda x:Fraction(x).limit_denominator
from fractions import*

Try it online!
The above function takes a floating point number and returns a bound function Fraction.limit_denominator which, in turn, takes the upper bound for the denominator to return a simplified, approximated fraction as requested.
As you can tell, I’m more of an API reader than a golfer.

minus 5 bytes thanks to ovs


Python (2), 167 156 155 142 141 bytes

from time import*
def f(s):
 try:return 1>sum(int(i)*(ord(j)-48)for i,j in zip("43276504321",s))%11;strptime(s[:6],"%d%m%y")
 except:return 0

tried to do the date validation without the library, but it's 168 bytes:

lambda s:sum(int(i)*(ord(j)-48)for i,j in zip("43276504321",s))%11==0 and int(s[0:2])<([0,32,(29,30)[int(s[4:6])%4==0],32]+[31,32]*2+[32,31]*2+[32]+[0]*99)[int(s[2:4])]

-12 bytes thanks to @GáborFekete

-14 bytes thanks to @RootTwo


Python 2, 71 57 54 53 bytes

-15 bytes thanks to ovs! -3 bytes thanks to Rod.

lambda l:[i.strip("'")+" '"[len(i):]for i in l[::-1]]

Try it online!

String I/O, 70 bytes

lambda s:' '.join(i.strip("'")+"'"*(len(i)<2)for i in s.split()[::-1])

Try it online!


Python 2.7 - 154 147 134 128 bytes

l=r=p=0
exec"exec raw_input('%s->','p+=r+1;r=0%s<-','p-=l+1;l=0%s>','r+=1;p+=1%s<','l+=1;p-=1;')"%((";').replace('",)*4)
print p

Serious changes have been made to the way this program works. I've removed the old explanation, which can still be found in this answer's edit history.

This one's gross.

It works pretty much the same way as other answers for this question, replacing the characters in the input with valid statements in that language and executing them. There's one major difference, though: replace is a long word. Screw that.

@ProgrammerDan in chat came up with the idea of using a tuple with the string ;').replace(' in it 4 times, to use the pre-str.format() method of formatting text. Four instances of %s are in the string on the second line, each one taking its value from the associated element of the tuple at the end. Since they're all the same, each %s is replaced with ;').replace('. When you perform the operations, you get this string:

exec raw_input(';').replace('->','p+=r+1;r=0;').replace('<-','p-=l+1;l=0;').replace('>','r+=1;p+=1;').replace('<','l+=1;p-=1;')

This is now valid python code that can be executed with exec. That's right, baby: Nested execs let me use string operations on code that needs to perform string operations on code. Someone please kill me.

The rest of it is pretty straightforward: Each command is replaced with code that keeps track of three variables: The current position, the number of rights since the last ->, and the same for lefts and <-. The whole thing is run and the position is printed.

You'll notice that I do raw_input(';'), using ';' as a prompt, rather than raw_input() which has no prompt. This saves characters in an unintuitive way: If I did raw_input(), I'd have to have the tuple filled with ).replace(', and every instance of %s would have ';\'' before it except the first one. Having a prompt creates more redundancy so I can save more characters overall.


Jelly, 2 bytes

PS

Try it here!

If I encode an image like so:

0000111111111100000
0000000111111111000
0000000001111100000
0000000011111000000
0001111111111111100
0000001111110000000
0000000111111110000
0000111111111100000

Into a nested array like this:

[[0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0],...]

Then P takes the element-wise product of all of the row vectors, and S sums all of the ones in the result, yielding the length of the vertical slice. (This works only because there’s guaranteed to be only one contiguous slice.) In our case, the answer is 3.


(KevinC's) Triangular DeciDigits Sequence

Mathematica, 42 bytes

#&@@RealDigits[1/#,10,#,-1].(#-Range@#+1)&

or

#&@@RealDigits[1/#,10,#,-1].Range[#,1,-1]&

or

Tr@Accumulate@#&@@RealDigits[1/#,10,#,-1]&

Explanation

Take the example from the challenge spec. We want to compute:

  1+4+2+8+5+7+1
+ 1+4+2+8+5+7
+ 1+4+2+8+5
+ 1+4+2+8
+ 1+4+2
+ 1+4
+ 1

Rearranging, this is:

  1*7 + 4*6 + 2*5 + 8*4 + 5*3 + 7*2 + 1*1
= (1, 4, 2, 8, 5, 7, 1) . (7, 6, 5, 4, 3, 2, 1)

where . is the scalar product of two vectors.

That's pretty much all the solution does.

#&@@RealDigits[1/#,10,#,-1]

This gets us the first N decimal digits of 1/N (the #&@@ extracts the first element of the RealDigits result because that also returns the offset of the first digit which we don't care about).

Then we get the list from N down to 1 either using (#-Range@#+1) or Range[#,1,-1], both of which are shorter than Reverse@Range@#, and take the scalar product.

The alternative solution instead uses Accumulate to compute a list of all prefix sums and then adds up those prefix sums with Tr.

Since this is really fast even for large inputs, here is a scatter plot of the sequence up to N = 100,000 (doing all of them and plotting them took a while though):

Click for larger version.

The blue line is the naive upper bound of 9 N (N+1) / 2 (if all the decimal digits were 9) and the orange line is exactly half of that. Unsurprisingly this is right inside the main branch of the plot since, statistically, we'd expect the average digit to be 4.5.

The thin line of plot points which you can see below the main branch are fractions which end in ...3333..., as they all lie very close to 3 N (N+1) / 2.


Use the compression creator

Here is a new, buggy but mostly working online JavaScript compression creator. There, in each line enter a part of the string on each line which closest matches one of:

custom dictionary string - this will find the different characters used in the part, store them and store a number in the base of the amount of characters. This is effective for strings like niooaaoasoioaiaaaoiineeaei where there aren't a lot of different characters. It also works well for just a single character repeated. This has a limit of 98+(different characters used), and the compressor (currently) doesn't auto-split those.
boxstrings - strings with only the characters /\|_- and \n. Practically the same as custom dictionary strings, but more efficient. Note that this is chooses whether to use / and \ with the same bit, so then custom strings will be used. This has a limit the same as custom dictionary strings.
english - this has two word dictionaries, one of length 256 and another of ±65500. This only contains lowercase words and automatically adds spaces between words. To get something like spaceface do two parts of space and face. Each english part has a max of 4 words. If a 4-word part is followed by more english, it adds a space between. Trough the compressor will automatically split the input for you.
Note: the dictionary contains only lowercase versions of strings (except I, I've, and a couple others), so you must correctly case if after usage (using the characters ⁽ - uppercase 1st letter, ⁾ - sentence-case, ū - every words 1st letter).
ascii - Plain ascii - each part is 1-18 long (trough 1 and 2 are done differently) and auto-splits for you. Approx. 87% compression ratio.

Other stuff:

It's always useful to try different combinations and see which is smaller. At the end, it gives you the original and ending byte count and compression ratio. This might be automated sometime in the future.
For example, -_-_\_/_-       is shorter than
-_-_\_/_- and
       as different parts

An example input would be

row
,
row
,
row your boat
,¶"

, which outputs "π¾⌡īk#S)G⁶⁷λ7&[¶⁶āΡn‘, after which I can put uppercase 1st letter and remove the starting quote and get π¾⌡īk#S)G⁶⁷λ7&[¶⁶āΡn‘⁽ for Row, row, row your boat,\n"


Pyth, 47 46 45 36 30
FNs.zx=Z}N"\/L"aY|}N"\/V"yZ;sY

Explanation:
FNs.z            For every character in input, except newlines...
  x=Z}N"\/L"     Swap state if /, \, or L.
  aY|}N"\/V"yZ;  Append 1 if /, \, or V, else 2 times the state to Y.
sY               Sum Y and print.

We have two states, "in the polygon", and "out of the polygon". The following characters each do the following when reading them from top-left to bottom-right:
/ \     swap state, add one to area
V                   add one to area
_ space             if in polygon, add two to area
L       swap state, if in polygon, add two to area

Note that "add one to area" and "if in polygon, add two to area" are mutually exclusive.


Javascript ES6

Score: 0.245663Length: 1000 bytesPredicts: 5

(I guess the question is due for an unexpected avalanche of downvotes. :P)

Minified

E="ABCDEFGHIJKLMNOPQRSTUVWXYZ";E=E+E.toLowerCase()+"0123456789!@#$%;*()";P="RCRHIFMGPGIDQKHMJLLRMLFJGKHEqHPOgJNKGPCHPJNUPOSGJQKKKMELMIJHLKIKNcKDOfSJLFHDILGKIOUKLMLLKMKIHGHJGIIJDGJKIHIIFIGMTIHFJMIKDJGQJKGMKJHPRJPLMGIOPIIIIPBYFMGLEIKIMMRUKFLFGJFKFTHPFODEQTGTHKIJDHNJGDGiHKNYLHHDLJHGILOEViKNEKGQZfHJMIISIJFRHKLJMLPIFJILKKKJKKJESHNLLIKIGKGJJJHKJRGULLSLRONJNEeLKIQGGPQIHPLEIHHIDXjQHNBKOGWWIENRbYoHINHNMKTNKHTGMIPXFJLLMLIHPPLDJJKFUMIQMOKJLJJKIJKNLHRILJIAIbJEZOGIELGHGLOINDPJMJeJWRIIJHSOZDOsOFRRIOIOTIJSGGJKFUIDOINGOcLQEJFEITLMNIIGIGIMG7LPSNLKVOKIFGHJITGOFUJIIRN";K={};"99r1501vz076mip077myv0733it280exx081gt9118i1g279dyx102uho203ejd07433z087uje097kdg1567ft2088rk275dmu1203ez106lih1763ei126f6q101aax084owh088aid161i9y179gvn236ptn3338vf132i55080fke101l4z3789ai281ulm081blm124euz074o5m07513z14117l095qdn092gl30757n5153".replace(/(...)(...)/g,(_,a,b)=>K[a]=1*b);D=40655;N=479;H=(s,T)=>(h=7,[...s].map(c=>h=~~(h*T+c.charCodeAt(0))),h);S=s=>(y=H(s,31),K[((y%D+D)%D).toString(36)]||E.indexOf(P[(H(s,48)%N+N)%N]));

Expanded

E = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
E = E + E.toLowerCase() + "0123456789!@#$%;*()";
K = {};
P = "RCRHIFMGPGIDQKHMJLLRMLFJGKHEqHPOgJNKGPCHPJNUPOSGJQKKKMELMIJHLKIKNcKDOfSJL" +
    "FHDILGKIOUKLMLLKMKIHGHJGIIJDGJKIHIIFIGMTIHFJMIKDJGQJKGMKJHPRJPLMGIOPIIIIP" +
    "BYFMGLEIKIMMRUKFLFGJFKFTHPFODEQTGTHKIJDHNJGDGiHKNYLHHDLJHGILOEViKNEKGQZfH" +
    "JMIISIJFRHKLJMLPIFJILKKKJKKJESHNLLIKIGKGJJJHKJRGULLSLRONJNEeLKIQGGPQIHPLE" +
    "IHHIDXjQHNBKOGWWIENRbYoHINHNMKTNKHTGMIPXFJLLMLIHPPLDJJKFUMIQMOKJLJJKIJKNL" +
    "HRILJIAIbJEZOGIELGHGLOINDPJMJeJWRIIJHSOZDOsOFRRIOIOTIJSGGJKFUIDOINGOcLQEJ" +
    "FEITLMNIIGIGIMG7LPSNLKVOKIFGHJITGOFUJIIRN";

   ("99r1501vz076mip077myv0733it280exx081gt9118i1g279dyx102uho203ejd07433z087u" +
    "je097kdg1567ft2088rk275dmu1203ez106lih1763ei126f6q101aax084owh088aid161i9" +
    "y179gvn236ptn3338vf132i55080fke101l4z3789ai281ulm081blm124euz074o5m07513z" +
    "14117l095qdn092gl30757n5153").
        replace( /(...)(...)/g, (_,a,b) => K[a] = 1*b );

D = 40655;
N = 479;
H = (s,T) => (
    h = 7,
    [...s].map( c => h = ~~(h*T + c.charCodeAt(0)) ),
    h
);

S = s => (
    y = H( s, 31 ),
    K[((y%D + D)%D).toString( 36 )] || E.indexOf( P[(H( s, 48 )%N + N)%N] )
);

The function S accepts a string (title) and returns its score.

Notes on Behaviour:

≤ 70 vote titles are handled separately from > 70 vote titles
≤ 70 vote titles are sorted into bins using a highly sophisticated holonomic keyword tracking potential optimization algorithm that in no way resembles a string hash function
after a bit of happy calculus it turns out that the optimal guess for each bin is simply the geometric average of the (votes + 20)'s for all titles in the bin, minus 20
the optimal guesses for all 479 bins are then encoded as a 479-character base-70 string
for > 70 vote titles, the titles are assigned unique 3-digit base-36 codes generated using a state-of-the-art hashing technique that guarantees no collisions with other > 70 vote titles and no false detections of ≤ 70 vote titles. This state-of-the-art technique in no way resembles trying random bin counts until one produces no collisions.
the > 70 vote title codes and their vote counts are encoded in a string (6 bytes per title), which is converted to a simple lookup table. The routine therefore has zero error for all > 70 vote titles.


Ruby,  119  112 bytes / score 17

puts ["%x"%(("!\#&+,-01245:;<>?@ABDEFIJKLNOQRUVWXYZ`dflqnry{|}"=~/$/)^"s8j9bePwGp7SgMTCvznH".to_i(36))].pack'h*'

Try it online!


PowerShell: test connection in as few characters as possible

PowerShell v2+, 63 bytes

You can use a different constructor to create the object and connect in one go.

(new-object Net.Sockets.TcpClient('192.168.5.5',445)).Connected

I've verified this works in v2 on my Windows 8.1 machine. That constructor is supported by .NET 2.0, so this should be v2 compatible.


Is there a shorter way to assign one of two variables in Python?

12 chars/assignment + 9 chars of overhead

V=vars()     # do once at the start of the program
V["xy"[b]]=z

Note that this only works at global scope, it does not work inside a function.


SVG (462 460 454 429 384 365 bytes)

I know it isn't a programming language, but I thought this will at least be useful to anyone generating SVG output...

This is based on Peter Taylor's SVG.

By using the original coords, and optimizing the paths a little, I managed to shrink the SVG down.  I also fixed the colours.

<svg><g stroke-linecap=round stroke-linejoin=round stroke-width=26><path d=M54,13,13,36V75H151V36L110,13 stroke=#1f1a1a /><path d=M21,84V36H37A91,91,0,0,1,127,36h16V84z stroke=#404040 /><path d=M30,36v48h104V36z stroke=#58585c fill=#58585c /></g><circle cx=82 cy=60 r=23 fill=#ffca57 stroke=#ff1c22 stroke-width=5 /><path d=M82,43,92,74,66,55H98L72,74z fill=#ff1c22

Update: Fixed flaw pointed out by Peter Taylor and position of rects and saved 2 more bytes.

Update 2: Incorporated another fix and suggestions from Peter (-6 bytes)

Update 3: Just noticed the instructions now specify all radii are 13, so taking advantage of that, and optimizing the paths a bit more, I saved another 25 bytes. More readable fiddle here.

Update 4: Since I am already assuming the SVG is embedded in HTML (standalone SVGs need the namespace declaration), I can actually squeeze this more. (a) I don't need the  width and height attributes because the size of the SVG is smaller than the default size browsers give to objects whose size is indeteminate (300x150), and (b) the HTML parser is forgiving about attributes which don't have quotes, so some of them can be removed (idea from Squeamish Ossifrage).  Saves another 45 bytes.

Update 5: Using hsl's tricks for de-quoting the colours and dropping the trailing end tags.  We saved another 19 bytes.  The latter seemed a bit cheaty to me at first, but since it works in all browsers, I changed my mind. :)  Thanks hsl!


NodeJS

Edit
The algorthim is much faster now!
There is definitely no solution for the given example!

I tried some algorithms to generate a time table and I am pretty sure that your example has no solution.
So I changed the example to
students.json:

[
{"name":"Sarah","subjects":["physics","it","biology","history","art","business studies","french"]},
{"name":"Jim","subjects":["history","business studies","biology","computer science","geography","chemistry"]},
{"name":"Mary","subjects":["it","computer science","biology","physics","chemistry","art"]},
{"name":"Chris","subjects":["biology","chemistry","physics","french","computer science","geography"]}
]

(I only deleted the pe)
which generates this timeTable.json

 {
 "mon":
   [["Bi"],["Bi"],["Ar","Gg"],["La"],["La"],["Ch"],["Ch"],["CS"],["CS"],["Ph"]],
 "tue":
   [["Tu"],["Bi"],["Ar","Gg"],["Ma"],["Ma"],["Ch"],["CS"],["Ph"],["Ph"],["Bu"]],
 "wed":
   [["Bi"],["Ar","Gg"],["Ar","Gg"],["Li"],["Li"],["Fr"],["Fr"],["IT"],["IT"],["Hi"]],
 "thu":
   [["Li"],["Ma"],["Ch"],["CS"],["Bu"],["Ph"],["Fr"],["IT"],["Hi"],["Ac"]],
 "fri":
   [["Li"],["Ma"],["Fr"],["Bu"],["Bu"],["IT"],["Hi"],["Hi"],[],["Tu"]]
 }

And yes my programm is very long but I think code which is shortened afterwards makes it really hard to read and nowadays it isn't important to save bytes but time!
If you have any suggestions or you found a bug => comment!
You can start the file (timeTable.js) with node timeTable.js students.js

    var fs = require('fs');

console.log('Timetable');
var json = JSON.parse(fs.readFileSync(process.argv[2], 'utf8'));

var backTracks = 0;
var lessons =
    ["art","biology","business studies","chemistry","computer science","french","geography","history","it","mandarin","music","pe","physics","spanish"];
var abbr = ["Ar","Bi","Bu","Ch","CS","Fr","Gg","Hi","IT","Cn","Mu","PE","Ph","Sp"];
var single = [2,2,2,2,2,2,2,2,2,2,2,2,2,2];
var double = [1,1,1,1,1,1,1,1,1,1,1,1,1,1];

var days = ["mon","tue","wed","thu","fri"];
var nrOfStudents = json.length;
var q = 0;

// convert json into correct position
for (var i = 0; i < json.length; i++) {
    var subjects = json[i].subjects;
    for (var s = 0; s < subjects.length; s++) {
        var pos = lessons.indexOf(subjects[s].toLowerCase());
        if (pos >= 0) {
            subjects[s] = pos;
        }
    }
}

// Special lessons
var timeTable = {"mon":[],"tue":[],"wed":[],"thu":[],"fri":[]};
timeTable.tue[0] = ["Tu"];
timeTable.fri[9] = ["Tu"];
timeTable.thu[9] = ["Ac"];
// one english double (Monday 4-5)
timeTable.mon[3] = ["La"];
timeTable.mon[4] = ["La"];
// one double two single for math and literature (Tue 4-5,Wed 4-5,Thu 1,2,Fri 1,2)
timeTable.tue[3] = ["Ma"];
timeTable.tue[4] = ["Ma"];
timeTable.wed[3] = ["Li"];
timeTable.wed[4] = ["Li"];
timeTable.thu[0] = ["Li"];
timeTable.thu[1] = ["Ma"];
timeTable.fri[0] = ["Li"];
timeTable.fri[1] = ["Ma"];

var timeTableBackup = {0:[],1:[],2:[],3:[],4:[]};

for (var i = 0; i < 5; i++) {
    var day = timeTable[days[i]];
    for (var j = 0; j < 10; j++) {
        if (!(j in day) || !Array.isArray(day[j])) {
            day[j] = [];
        }
    }
}

// sort subjects
var sortedSubs = [];
// 14 subjects
for (var i = 0; i < 14; i++) {
    sortedSubs[i] = {t:0,students:[],n:i};
}

for (var i = 0; i < json.length; i++) {
    var subjects = json[i].subjects;
    var student = json[i].name;
    for (var s = 0; s < subjects.length; s++) {
        sortedSubs[subjects[s]].t ++;
        sortedSubs[subjects[s]].n = subjects[s];
        sortedSubs[subjects[s]].students.push(student);
    }
}
console.log(sortedSubs);

sortedSubs = sortByKey(sortedSubs,"t");

var k = sortedSubs.length-1;
// remove all subs that weren't choosen by anyone
while(sortedSubs[k].t == 0) {
    var sub = sortedSubs.pop();
    single[sub.n] = 0;
    double[sub.n] = 0;
    k--;
}

var goBack = false;
var start = false;
var d = 0;
while (d < 5) {
    // 10 lessons per day
    var l = 0;
    while(l < 10) {
        var day = timeTable[days[d]];
        // if there is no subject
        if (day[l].length == 0) {
            var next = false;
            var s = start === false ? 0 : start;
            var firstChoice = false;
            while (!next && s < sortedSubs.length) {
                if (possibleToAdd(day,l,s)) { // different lessons on one day and possiblity to add lesson
                    goBack = false;
                    next = true;
                    if (!firstChoice) firstChoice = s;
                    // get the number of students that don't have this lesson
                    var except = nrOfStudents - sortedSubs[s].t;
                    if (except > 0) {
                        // get the first lesson which none of the students have
                        var breaked = false;
                        var tempL;
                        for (var ss = s+1; ss < sortedSubs.length; ss++) {
                            if (sortedSubs[ss].t <= except && possibleToAdd(day,l,ss)) {
                                var intersection = arrIntersect(sortedSubs[s].students,sortedSubs[ss].students);
                                // no student has both classes
                                if (intersection.length == 0) {
                                    if (!breaked) { // fill the current lesson (s) only once
                                        tempL = addLesson(day,l,s);
                                    }
                                    tempL = addLesson(day,l,ss);
                                    breaked = true;
                                }
                            }
                        }

                        if (breaked) {
                            l = tempL;
                        } else { // it wasn't possible to have two classes at this time
                            next = false;
                            var found = false;
                            // maybe there are other lessons which can be added => found = true
                            for (var z = s+1; z < sortedSubs.length; z++) {
                                if (possibleToAdd(day,l,z)) {
                                    found = true;
                                    break;
                                }
                            }
                            // otherwise fill this lesson with the first choice
                            if (!found) {
                                l = addLesson(day,l,firstChoice);
                            }
                        }
                    } else {
                        // everyone has this lesson :)
                        // on day lesson no. l: subject no. s
                        l = addLesson(day,l,s);
                    }
                } else {
                    if (start) goBack = true;
                }
                s++;
            }
            start = false;
        }
        // Friday last lesson
        if ((d == 4 && l == 9) || goBack) {
            // how many lessons are missing?
            var sum = double.reduce(function(pv, cv) { return pv + cv; }, 0)*2 + single.reduce(function(pv, cv) { return pv + cv; }, 0);
            if (sum > 0) {
                remove = removeLesson(d,l);
                if (remove) {
                    backTracks++;
                    if (backTracks % 50000 == 0) {
                        console.log('backTracks: '+backTracks+'...');
                    }
                    d = remove.back.day;
                    l = remove.back.lesson;
                    start = remove.start;
                } else {
                    console.log('I could not find a solution for this problem :( ');
                    console.log('backtracks: '+backTracks);
                    process.exit();
                    l = 10;
                    d = 5;
                }
            } else {
                l = 10;
                d = 5;
            }
        } else {
            l++;
        }
    }
    d++;
}

function removeLesson(d,l) {
    var day = timeTable[days[d]];
    var back = true;
    // what is the latest subject
    var latestSub = sortedSubs[sortedSubs.length-1].n;

    // backtrack
    while(back) {
        // if there is no lesson before => back to the last lesson the day before
        if (l == -1) {
            if (d == 0) {
                return false; // not possible at all
            }
            d--;
            day = timeTable[days[d]];
            l = day.length-1;
        }

        // if there is a non default lesson
        if (day[l].length > 0 && parseInt(day[l][0]) == day[l][0]) {
            // if the latestSub isn't part of this lesson we don't need to backtrack more
            if (day[l].indexOf(latestSub) < 0) { back = false; }
            var intersection = [];
            // if we are not in the first lesson => get double lessons
            if (l > 0) {
                intersection = arrIntersect(day[l],day[l-1]);
            }
            // if there are double lessons
            if (intersection.length > 0) {
                for (var i = 0; i < day[l].length; i++) {
                    // check if current lesson is a double lesson
                    if (intersection.indexOf(day[l][i]) >= 0) {
                        double[day[l][i]]++;
                    } else {
                        single[day[l][i]]++;
                    }
                }
                // remove all single lessons the lesson before
                for (var i = 0; i < day[l-1].length; i++) {
                    if (intersection.indexOf(day[l-1][i]) < 0) {
                        single[day[l-1][i]]++;
                    }
                }
                day[l] = [];
                l--;
            } else {
                for (var i = 0; i < day[l].length; i++) {
                    single[day[l][i]]++;
                }
            }
            // delete the day if the current lesson was the least possible solution
            if (back) {
                day[l] = [];
            }
        } else {
            l--;
        }
    }
    var start = false;
    // get start subject for this lesson d,l
    for (var s = 0; s < sortedSubs.length-1; s++) {
        if (day[l].indexOf(sortedSubs[s].n) >= 0) {
            start = ++s;
            day[l] = [];
            break;
        }
    }
    if (!start) {
        console.log('there is a bug');
        process.exit();
    }
    return {back:{day:d,lesson:l},start:start};
}

function addLesson(day,l,s) {
    // is a double lesson possible?
    if (double[sortedSubs[s].n] > 0 && l != 2 && l != 4 && l+1 < 10 && (day[l+1].length == 0 || parseInt(day[l+1][0]) == day[l+1][0])) {
        double[sortedSubs[s].n]--;
        for (var i = l; i <= l+1; i++) {
            if (Array.isArray(day[i])) {
                day[i].push(sortedSubs[s].n);
            } else {
                day[i] = [sortedSubs[s].n];
            }
        }
        l++;
    } else if (single[sortedSubs[s].n] > 0) { // put it into a single lesson
        single[sortedSubs[s].n]--;
        if (Array.isArray(day[l])) {
            day[l].push(sortedSubs[s].n);
        } else {
            day[l] = [sortedSubs[s].n];
        }
    } else {
        console.log('ERROR');
        process.exit();
    }
    return l;
}

function possibleToAdd(day,l,s) {
    // it is not allowed to have the same lesson twice on a day
    var notSet = true;
    for (var i = 0; i < l; i++) {
        if (day[i].indexOf(sortedSubs[s].n) >= 0) {
            notSet = false;
            break;
        }
    }
    if (!notSet) return false;

    // no double lesson 3+4 and (starting with 1)
    if (double[sortedSubs[s].n] > 0 && l != 2 && l != 4 && l+1 < 10 && (day[l+1].length == 0 || parseInt(day[l+1][0]) == day[l+1][0])) {
        return true;
    } else if (single[sortedSubs[s].n] > 0) {
        return true;
    } else {
        return false;
    }
}

function arrIntersect(array1,array2) {
    return array1.filter(function(n) {
        return array2.indexOf(n) != -1
    });
}

function sortByKey(array, key) {
    return array.sort(function(a, b) {
        var x = a[key];
        var y = b[key];
        return ((x < y) ? 1 : -1);
    });
}

// convert lesson numbers into abbr
for (var d = 0; d < 5; d++) {
    var day = timeTable[days[d]];
    // 10 lessons per day
    for (var l = 0; l < 10; l++) {
        for (var ll = 0; ll < day[l].length; ll++) {
            if (parseInt(day[l][ll]) == day[l][ll]) {
                day[l][ll] = abbr[day[l][ll]];
            }
        }
    }
}

console.log(timeTable);
console.log('Backtracks: '+backTracks);

fs.writeFile("timeTable.json", JSON.stringify(timeTable), function(err) {
    if(err) {
        console.log(err);
    } else {
        console.log("The file was saved (timeTable.json)!");
    }
});


JavaScript (ES6), 72 bytes
f=x=>x%17^2?['doko ','zun '][j=Math.random()*2|0]+f(x<<7|j):'ki-yo-shi!'

Try it online!
How?
We keep track of the last 5 words in a 32-bit integer stored in \$x\$ (which is initially undefined). At each iteration, we left-shift it by 7 positions and set the LSB to \$0\$ for doko or \$1\$ for zun.
The sequence zun, zun, zun, zun, doko results in:
x = 10000001000000100000010000000
or \$270549120\$ in decimal, which is the only value for which we have \$x\equiv 2\pmod{17}\$, as shown in this table. This is our halt condition.


C#, 244 bytes

string F(int d,int c,string t){var w=t.Substring(1).Split(' ');t=""+t[0];for(int i=0,x=c,y=0;i<w.Length;x+=w[i++].Length+1)t+=(1>(x=x+w[i].Length>c?0:x)?"\n"+(y++<d?(y<d?"| ":"' ").PadLeft(x=d+1,y<d?'.':'~'):""):" ")+w[i];return t.Remove(1,2);}

Indentation, new lines and comments for clarity:

string F(int d,int c,string t){
    var w=t.Substring(1).Split(' ');
    t=""+t[0];
    for(int i=0,x=c,y=0;i<w.Length;x+=w[i++].Length+1)
        t+=(1>(x=x+w[i].Length>c?0:x)?"\n"+(y++<d?(y<d?"| ":"' ").PadLeft(x=d+1,y<d?'.':'~'):""):" ")+w[i];
    return t.Remove(1,2);
}


MATL, 8 bytes

tn:IXQ&D

Input is a column vector, with ; as separator (for example [2;2;2]). Output is the string representation of a cell array of row vectors (for example {[]; [1 2 3]}). A row vector of a single element is the same as a number (so {1; 2; 3} would be output instead of {[1]; [2]; [3]}).

Try it online! Or verify all test cases.

Explanation

t     % Implicit input, say x. Duplicate
n     % Number of elements, say N
:     % Range: [1 2 ... N]
IXQ   % accumarray(x, [1 2 ... N], [], @(x){sort(x).'})
&D    % String representation

Most of the work is done by Matlab's higher-order function accumarray, which groups elements in the second input according to matching values in the first, and applies a specified function to each group. The function in this case is @(x){sort(x).'}, which outputs the sorted elements in each group and causes the results for all groups to be packed in a cell array.


Mathematica, HP(80) in ~0.88s

NestWhile[
  FromDigits[
    Flatten[IntegerDigits /@
      ConstantArray @@@ FactorInteger[#]]] &, #, CompositeQ] &

Anonymous function. Takes a number as input and returns a number as output.


C, 81 78 bytes

l,i;f(n){for(l=i=0;l<n;l+=++i%3?i%5?snprintf(0,0,"%d",i):4:i%5?4:8);return i;}

68 bytes if you don't mind converting to double and back:

l,i;f(n){for(l=i=0;l<n;l+=++i%3?i%5?log10(i)+1:4:i%5?4:8);return i;}


Python ~451 digits

This is part of the library I wrote for a semiprime factorization problem, with unnecessary functions removed. It uses the Baillie-PSW primality test, which is technically a probabilistic test, but to date, there are no known pseudoprimes – and there's even a cash reward if you're able to find one (or for supplying a proof that none exist).

Edit: I hadn't realized that Python has built-in modular exponentiation. Replacing my own for the built-in results in a performance boost of about 33%.

my_math.py

# legendre symbol (a|m)
# note: returns m-1 if a is a non-residue, instead of -1
def legendre(a, m):
  return pow(a, (m-1) >> 1, m)

# strong probable prime
def is_sprp(n, b=2):
  d = n-1
  s = 0
  while d&1 == 0:
    s += 1
    d >>= 1

  x = pow(b, d, n)
  if x == 1 or x == n-1:
    return True

  for r in range(1, s):
    x = (x * x)%n
    if x == 1:
      return False
    elif x == n-1:
      return True

  return False

# lucas probable prime
# assumes D = 1 (mod 4), (D|n) = -1
def is_lucas_prp(n, D):
  P = 1
  Q = (1-D) >> 2

  # n+1 = 2**r*s where s is odd
  s = n+1
  r = 0
  while s&1 == 0:
    r += 1
    s >>= 1

  # calculate the bit reversal of (odd) s
  # e.g. 19 (10011) <=> 25 (11001)
  t = 0
  while s > 0:
    if s&1:
      t += 1
      s -= 1
    else:
      t <<= 1
      s >>= 1

  # use the same bit reversal process to calculate the sth Lucas number
  # keep track of q = Q**n as we go
  U = 0
  V = 2
  q = 1
  # mod_inv(2, n)
  inv_2 = (n+1) >> 1
  while t > 0:
    if t&1 == 1:
      # U, V of n+1
      U, V = ((U + V) * inv_2)%n, ((D*U + V) * inv_2)%n
      q = (q * Q)%n
      t -= 1
    else:
      # U, V of n*2
      U, V = (U * V)%n, (V * V - 2 * q)%n
      q = (q * q)%n
      t >>= 1

  # double s until we have the 2**r*sth Lucas number
  while r > 0:
      U, V = (U * V)%n, (V * V - 2 * q)%n
      q = (q * q)%n
      r -= 1

  # primality check
  # if n is prime, n divides the n+1st Lucas number, given the assumptions
  return U == 0

# primes less than 212
small_primes = set([
    2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
   31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
   73, 79, 83, 89, 97,101,103,107,109,113,
  127,131,137,139,149,151,157,163,167,173,
  179,181,191,193,197,199,211])

# pre-calced sieve of eratosthenes for n = 2, 3, 5, 7
indices = [
    1, 11, 13, 17, 19, 23, 29, 31, 37, 41,
   43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
   89, 97,101,103,107,109,113,121,127,131,
  137,139,143,149,151,157,163,167,169,173,
  179,181,187,191,193,197,199,209]

# distances between sieve values
offsets = [
  10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6,
   6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4,
   2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
   4, 2, 4, 6, 2, 6, 4, 2, 4, 2,10, 2]

max_int = 2147483647

# an 'almost certain' primality check
def is_prime(n):
  if n < 212:
    return n in small_primes

  for p in small_primes:
    if n%p == 0:
      return False

  # if n is a 32-bit integer, perform full trial division
  if n <= max_int:
    i = 211
    while i*i < n:
      for o in offsets:
        i += o
        if n%i == 0:
          return False
    return True

  # Baillie-PSW
  # this is technically a probabalistic test, but there are no known pseudoprimes
  if not is_sprp(n): return False
  a = 5
  s = 2
  while legendre(a, n) != n-1:
    s = -s
    a = s-a
  return is_lucas_prp(n, a)

# next prime strictly larger than n
def next_prime(n):
  if n < 2:
    return 2
  # first odd larger than n
  n = (n + 1) | 1
  if n < 212:
    while True:
      if n in small_primes:
        return n
      n += 2

  # find our position in the sieve rotation via binary search
  x = int(n%210)
  s = 0
  e = 47
  m = 24
  while m != e:
    if indices[m] < x:
      s = m
      m = (s + e + 1) >> 1
    else:
      e = m
      m = (s + e) >> 1

  i = int(n + (indices[m] - x))
  # adjust offsets
  offs = offsets[m:]+offsets[:m]
  while True:
    for o in offs:
      if is_prime(i):
        return i
      i += o

A sample test script:

from time import clock
from my_math import *

n = i = 317**79
while True:
  i *= 317
  time1 = clock()
  n, o = next_prime(i), n
  span = clock()-time1
  if span > 10:
    break
  print(len(str(n)), span)
print(o)

A factor of 317 was chosen, because it's approximately the square root of 10000, adding roughly 2.5 digits per iteration (and because doubling was too slow to sit through). Output shows the current number of digits, and the time taken.

Sample results:

201 0.13121248650317288
203 0.059535499623555505
206 0.9157767258129175
208 0.2583420518529589
211 0.15367400046653978
213 0.32343915218274955
216 1.3962866788935466
218 0.5986165839513125
221 0.973842206202185
223 2.346910291671148
...
428 0.932809896229827
431 4.345940056627313
433 9.511724255457068
436 6.089835998709333
438 1.3793498894412721
441 4.290633027381972
443 3.5102506044762833
446 3.1629148397352083
448 3.364759208223404
451 7.34668009481652
1551197868099891386459896063244381932060770425565921999885096817830297496627504652115239001983985153119775350914638552307445919773021758654815641382344720913548160379485681746575245251059529720935264144339378936233043585239478807971817857394193701584822359805681429741446927344534491412763713568490429195862973508863067230162660278070962484418979417980291904500349345162151774412157280412235743457342694749679453616265540134456421369622519723266737913

All code is now python 3 compatible.