JavaScript (ES6), 87 bytes

As noticed by TFeld, my original formula was overcomplicated. We can just do:

_=>['Zzz','Good morning','Good afternoon','Good evening'][new Date().getHours()%20/6|0]

Try it online!

Or test this version that takes the hour as parameter.

JavaScript (ES6), 90 bytes

_=>['Zzz','Good morning','Good afternoon','Good evening'][new Date().getHours()*7%20%7>>1]

Try it online!

Or test this version that takes the hour as parameter.

Formula

Given the current hour \$h\$, we find the appropriate greeting index \$i\$ with:

$$i=\left\lfloor\frac{((7\times h) \bmod 20) \bmod 7}{2}\right\rfloor$$

A good thing about this formula is that it does not require any parenthesis once converted to JS:

h * 7 % 20 % 7 >> 1

Table

 Hour |  *7 | mod 20 | mod 7 | >> 1
------+-----+--------+-------+------
   0  |   0 |    0   |   0   |   0
   1  |   7 |    7   |   0   |   0
   2  |  14 |   14   |   0   |   0
   3  |  21 |    1   |   1   |   0
   4  |  28 |    8   |   1   |   0
   5  |  35 |   15   |   1   |   0
   6  |  42 |    2   |   2   |   1
   7  |  49 |    9   |   2   |   1
   8  |  56 |   16   |   2   |   1
   9  |  63 |    3   |   3   |   1
  10  |  70 |   10   |   3   |   1
  11  |  77 |   17   |   3   |   1
  12  |  84 |    4   |   4   |   2
  13  |  91 |   11   |   4   |   2
  14  |  98 |   18   |   4   |   2
  15  | 105 |    5   |   5   |   2
  16  | 112 |   12   |   5   |   2
  17  | 119 |   19   |   5   |   2
  18  | 126 |    6   |   6   |   3
  19  | 133 |   13   |   6   |   3
  20  | 140 |    0   |   0   |   0
  21  | 147 |    7   |   0   |   0
  22  | 154 |   14   |   0   |   0
  23  | 161 |    1   |   1   |   0


Slip, 18 + 3 = 21 bytes

>? ( +(X|$^)<<){2}

Run with the flags no (hence the +3), and uses space/X instead of space/#. Annoyingly this is longer than CJam/Pyth, but I guess Slip wasn't designed to be particular golfy...

Try it online. Note that the first example is missing spaces on a few lines.

Explanation

>?           Optionally turn right, hence matching either horizontally or vertically
[space]      Match a space
(    ){2}    Group, twice:
[space]+       Match 1+ spaces
(X|$^)         Either an X or the boundary of the grid
<<             Reverse the match pointer by turning left twice

The n flag makes output print the number of matches, and the o flag enables overlapping matches starting from the same square. The reason for the back-and-forth is because Slip tries matches starting from every square, and we want to make sure we only match a full row rather than a partial one. Slip only returns unique matches, even if they started from different positions.

Note: Originally I had >?(  +(X|$^)<<){2}, with the first space on the inside. This would miss some cases with 2 space long words at the edge, since the pointer would go like this:

XXX       XXX       XXX       XXX
X>        X >       X<        <
XXX       XXX       XXX       XXX

[sp]    [sp]+$^    <<[sp]    [sp]+   (uh oh match fails)


C++, 498 482 457 bytes
If this function is just called once, it can be 455 bytes.
I found that almost every online GCC compilers (including TIO) forbids me to omit the type of the function f. However, the GCC on my computer allows that, and I don't know why.
This one can handle large inputs if a slot can contain that number of items (though needs a larger array and will probably run out of time).
#import<bits/stdc++.h>
#define t N.first
#define X n.erase(n.find
#define p(c){if(c==r)return l;if(L.emplace(w={n,c},l).second)Q[U++]=w;}
#define T(S,C)n.insert(S);p(C)X(S));
using m=std::multiset<int>;using s=std::pair<m,int>;s Q[99999];int x,l,B,U;int f(int a,int r){if(!r)return 0;std::map<s,int>L;s f({a},B=0),w,N;L[Q[U=1]=f];for(;;){l=L[N=Q[B++]]+1;x=N.second;t.insert(0);for(int i:t){m n=t;X(i));if(x){T(i+x,0)T(i+1,x-1)}if(!x&&i){p(i)T(i/2,i-i/2)}}}}

Ungolfed:
#include <map>
#include <set>
#include <queue>
#include <iostream>

using namespace std;

struct state {
    multiset<int> t; int q;
    bool operator<(const state& i) const { return make_pair(t, q) < make_pair(i.t, i.q); }
};

int f(int a, int target) {
    if (target == 0) return 0;

    map<state, int> len;
    queue<state> qu;
    state first = {{a}, 0};
    qu.push(first);
    len[first] = 0;

    #define push(c) { state a = {n, c}; auto t = len.insert({a, l + 1}); if (t.second) { \
        if (a.q == target) return l + 1; qu.push(a); \
    } } // push new state into queue and check for termination
    #define next(stk, cur) { n.insert(stk); push(cur); n.erase(n.find(stk)); }
    // insert new stack, push new state, erase the stack (for another use)

    while (qu.size()) { // BFS cycle
        state now = qu.front();
        qu.pop();

        int q = now.q;
        int l = len[now];

        multiset<int> n(now.t);
        for (int i : now.t) { // click on non-empty stack
            n.erase(n.find(i));
            if (!q) { // nothing on cursor
                push(i); // click left
                next(i / 2, (i + 1) / 2); // click right
            }
            else { // item on cursor
                next(i + q, 0); // click left
                next(i + 1, q - 1); // click right
            }
            n.insert(i);
        }
        if (q) { // click on empty stack
            next(q, 0); // click left
            next(1, q - 1); // click right
        }
    }
}


What is a short code for generating this matrix in R?

R, 24 23 22 20 bytes

diag(0,6)+c(!-1:4,1)

Try it online!

Just use R's recycling! This does give a warning, but otherwise is fine.

Thanks to Robin Ryder for the 2 byte golf.


Python, 274 chars

S=7
D=-1j

R=[0,4,7,1+1j,3+1j,1+3j,4+3j,7j,3+7j,7+7j,8j,3+8j]
Z={}
for i in range(4096):
 d=D;p=R[S];L=[]
 while len(L)<12:
  p+=d;P=[(abs(r-p),r)for r in R if r-p==abs(r-p)*d]
  if not P:break
  p=min(P)[1];d*=1j**(i>>R.index(p)&1);L+=[p]
  if p==R[S]:Z[tuple(L)]=1;break
print len(Z)

The code I'm counting starts at the R=[..., the initial two lines are "input" which I didn't count.

R is the set of rock coordinates, listed using complex number coordinates.  S is the starting rock.  D is the starting direction, again using complex numbers (1=right,-1=left,1j=up,-1j=down).

The code tries all of the 2^12=4096 possibilities for go straight/turn left for each rock, then walks from the starting rock until it gets back to the starting rock, or there is no more rock on the path, or the path gets too long (it loops).  It saves the path in Z if it is successful.


Exploit comment symbols

A simple way to create a two-language polyglot is to have the code divided in two parts as follows:

The first part does the actual work in language A, is harmless in language B (no errors), and ends in a language-A comment symbol, which hides the second part to language A.
The second part does the actual work in language B.

Thus

Language A sees the first part, which does the job, and then a comment.
Language B sees a useless first part and then the second part, which does the job.

The only difficult part here is finding a set of statements (first part) that do the job in language A while not giving errors in language B. Some suggestions for this:

Most stack-based languages allow displaying only the top of the stack at the end of the program (sometimes this is even default, as in 05AB1E).
Some languages ignore undefined statements (for example Golfscript).

A simple example that uses these guidelines can be found here. Languages A and B are MATL and 05AB1E respectively.


Generate MathJax for the Golden Ratio Continued Fraction

Python, 70 68 67 bytes

lambda n:"$$\\varphi=1+\%sdots%s$$"%("cfrac1{1+\\"*n+"d"[:n],"}"*n)

This defines an anonymous function which just uses simple string multiplication and string formatting.

(Thanks to @xnor for pointing out that \\c can just be written as \c, since c can't be escaped. Unfortunately this doesn't hold true for \\v, since \v is ASCII 11.)

Previous attempts:

lambda n:"$$\\varphi="+"1+\\cfrac1{"*n+"1+\\"+"ddots"[n<1:]+"}"*n+"$$"
lambda n:r"$$\varphi=%s1+\%s$$"%("1+\cfrac1{"*n,"ddots"[n<1:]+"}"*n)


Give me the Gray Code list of bit width n

JavaScript (77)

for(i=0;i<1<<n;)alert((Array(n*n).join(0)+(i>>1^i++).toString(2)).substr(-n))

More browser-friendly version (console.log and prompt()):

n=prompt();for(i=0;i<1<<n;)console.log((Array(n*n).join(0)+(i>>1^i++).toString(2)).substr(-n))


The Rule of Thumb for Title Capitalization

Python 2, 118 bytes

Look ma, no regex!

for w in`input()`.split():print[w.title(),w][`w`in"'a'an'and'as'at'the'by'but'for'nor'in'of'on'or'to'up'"].strip("'"),

Input must be wrapped in quotes. Output has a trailing space and no trailing newline (I assume that's okay). Verify all test cases on Ideone.

Explanation

Let's take the input a or an as our example.

Using Python 2's `x` shortcut for repr, we wrap the input in single quotes: 'a or an'. Then we split on whitespace and iterate over the words.

Inside the loop, we take the repr again. For the first and last words, this gives "'a" and "an'". For other words, it gives 'or'. We want to avoid capitalizing words if they fit the latter pattern and are in the short-words list. So we can represent the word list as the string "'a'an'...'up'" and know that the repr of any short word will be a substring.

`w` in "..." gives a boolean value, which we can treat as 0 or 1 for the purposes of indexing into the list [w.title(), w]. In short, we title-case the word if it is at the beginning, at the end, or not in the list of short words. Otherwise, we leave it alone. Fortunately, title() still works as expected with input like 'a.

Finally, we strip any single quotes from the word and print it with a trailing space.


Perl, 8+1 = 9 bytes

say"#$."

Run with -p (1 byte penalty). (Note to people unfamiliar with PPCG rules; you also need to specify a modern version of Perl syntax using -M5.010, but we decided that options to select language versions are free and don't incur a byte penalty, so I didn't mention it in the original version of this post.)

-p places the program into an implicit loop; it basically causes the program to become a filter that processes each line separately (i.e. the entire program is run on the first line, then the second, then the third, and so on). Perl also keeps track of a line number, called $., that records how many lines of input have been read. So all the program's doing is letting -p read a line of input; output a #, the current line number ($.), and a newline (say adds a newline by default, which is helpful in this case, and is also shorter than the more commonly seen print); and then letting -p output the original line of code that it read (typically a program using -p would do some sort of processing on the input, but because we didn't, it's just output unchanged). Comments in Perl run from # to a newline (the # in the program itself doesn't start a comment because it's inside a string literal), so what we're basically doing is taking the opportunity to write comment lines into the file as we process it, without disturbing the "natural" read and write cycle of -p.


Replace letters by their rank, keeping punctuation intact

Ruby 2.0, 41+1 characters

There, now it complies with the updated rules and makes prettier output.

gsub(/\w+/){$&.chars.map{|c|c.ord&31}*?-}

Run with -p switch:

ruby -p ord.rb <<< "ABC! Defghi, jklmnopqr stuvwxyz"
1-2-3! 4-5-6-7-8-9, 10-11-12-13-14-15-16-17-18 19-20-21-22-23-24-25-26


Bash + coreutils, 116
Here's a shell script to get the ball rolling.  Pretty sure there'll be shorter answers:
n=`cmp <(echo $1) <(echo $2)|grep -Po "\d+(?=,)"`
printf -vs %`grep -o /<<<${1:n-1}|wc -l`s
echo ${s// /../}${2:n-1}

Output:
$ ./rel.sh /usr/share/geany/colorschemes /usr/share/vim/vim73/ftplugin
../vim/vim73/ftplugin
$ ./rel.sh /usr/share/geany/colorschemes/ /usr/share/vim/vim73/ftplugin/
../../vim/vim73/ftplugin/
$ ./rel.sh /usr/share/vim/vim73/ftplugin /usr/share/geany/colorschemes
../../geany/colorschemes
$

Note there is no way for the script to tell if the string ftplugin is a file or a directory.  You may explicitly provide a directory by appending it with an / as in the example above.
Won't handle paths containing whitespace or other funny characters.  Not sure if that is a requirement or not.  Just a few extra quotes would be needed.


Python 3, 39 bytes

def f(x,y,z):
	for x[z%len(x)]in y:z+=1

Try it online!
-5 bytes thanks to ovs for spotting the trick with cleverly using python's for loop specifics


Swift 3, 310 bytes

import Foundation;var n=String(describing:Date());var k=n.startIndex;print(Int(n[n.index(k,offsetBy:5)...n.index(k,offsetBy:6)])!*60+Int(n[n.index(k,offsetBy:8)...n.index(k,offsetBy:9)])!+720<=Int(n[n.index(k,offsetBy:11)...n.index(k,offsetBy:12)])!*60+Int(n[n.index(k,offsetBy:14)...n.index(k,offsetBy:15)])!)

Check it out!
This prints true and false, for truthy and falsy respectively.

NOTE: This only works until the year 9999, at 11:59:59 PM, because it uses Strings to compare the dates.


Jelly, 9 8 bytes
ṙ1×æ.Ɱ⁵Ḥ

Try it online!
Takes input as [z, y, x] as allowed by OP.
-1 byte thanks to Nick Kennedy
We calculate
$$2\left( \begin{matrix} z\times y \\ y\times x \\ x\times z\end{matrix} \right) \cdot \left( \begin{matrix} i \\ 1 \\ 1 \end{matrix} \right) = 2(yzi + yx+xz)$$
for each \$1 \le i \le 10\$
How it works
ṙ1×æ.Ɱ⁵Ḥ - Main link. Takes [z, y, x] on the left
ṙ1       - Rotate once left; [y, x, z]
  ×      - Product; [yz, xy, xz]
      ⁵  - Yield 10
     Ɱ   - For each integer 1 ≤ i ≤ 10:
   æ.    -   Dot product. Pad to [i, 1, 1] and calculate
              [yz, xy, xz] . [i, 1, 1] = yzi+xy+xz
       Ḥ - Double each


Anagramming Stack Exchange question titles into programs

Golfscript, 3 lines with no added characters

"Questions Tags Users Badge"'exception SLSATE[HY000][1049]eymfny incnue while pn chma afte intallin FOSBundl'or
"s Unanswered Ask "'Reoccurring error The current idetity(NT THORITY\NETWORK SERVICE)oe ot have it cc toC:\WINDOWS\Microsoft.NET\Framewor\v2.0.50727\Tempary ASP.NET Files'or
"Question""D he 'S'  SL stand f standard or strctured?"or

I hit StackOverflow, since it probably had the most (useful) posts. A lot of Qs could be found in jQuery and SQL.

Bibliography:

exception "SQLSTATE[HY000] [1049] Base 'symfony' inconnue" while updating schema after installing FOSUserBundle
Reoccurring error "The current identity (NT AUTHORITY\NETWORK SERVICE) does not have write access to 'C:\WINDOWS\Microsoft.NET\Framework\v2.0.50727\Temporary ASP.NET Files'"
Does the 'S' in SQL stand for "standard" or "structured"?

Uses two strings each line, and takes the first one with or. I don't know any proper Golfscript, but I tested it here.

It's possible to get the necessary quotes in two lines, but you'll need a language that lets you dump chars.


Python 3, 82 87 88

Thanks to @JonathanAllan for +1 score

print("g!#$%&'*n+,./012i34579;<l=>?@ADEwFGHIJKLoMNOPQRSBTUVWXYZ ^_`abchejkmqsuvdyz{|}~ \x6f       C"[::-8])

Try it online!

Nothing special, just slicing and skipping characters. The string is reversed so you can't remove characters and have the original string being printed.


C#, 418 313 305 271 bytes

s=>{var a="lawn clippings,lime,mucus,pear|rotten eggs,buttered popcorn|toothpaste,blue berry|vomit,peach|canned dog food,chocolate|stinky socks,tutti-frutti,baby diapers,coconut".Split('|')["eluaoi".IndexOf(s[2])].Split(',');return a[new System.Random().Next(a.Length)];}

Too long even for C# but I can't see how to get it any shorter.

Full/Formatted version:

using System;

class P
{
    static void Main()
    {
        Func<string, string> f = s =>
        {
            var a = "lawn clippings,lime,mucus,pear|rotten eggs,buttered popcorn|toothpaste,blue berry|vomit,peach|canned dog food,chocolate|stinky socks,tutti-frutti,baby diapers,coconut"
                    .Split('|')["eluaoi".IndexOf(s[2])].Split(',');

            return a[new System.Random().Next(a.Length)];
        };

        Console.WriteLine(f("green"));
        Console.WriteLine(f("yellow"));
        Console.WriteLine(f("blue"));
        Console.WriteLine(f("orange"));
        Console.WriteLine(f("brown"));
        Console.WriteLine(f("white"));

        Console.ReadLine();
    }
}


JavaScript, 25

document.bgColor=prompt()

You'll have to specify the three components in hexadecimal. This is code golf, so no commas or whitespace.


MATL, 48 44 42 37 33 bytes

Quite a few bytes saved thanks to rahnema1's idea (Octave answer) of collapsing two convolutions into one

t5BQ4B&vX^Z+*ssGt3Y6Z+1=*&fdwdYy/

This takes the input as a binary matrix, with ; as row separator. 1 corresponds to hash and 0 to space.

Try it online! Or verify all test cases.

Here's a format converter that takes inputs as 2D char arrays (again, with ; as separator) and produces string representations of the corresponding binary matrices.

Explanation

This was fun! The code uses three two 2D-convolutions, each for a different purpose:

To detect vertical and horizontal neighbours, which contribute a distance of 1, the required mask would be

0 1 0
1 0 1
0 1 0

But we only want each pair of neighbours to be detected once. So we take half the mask (and the last row of zeros can be removed):

0 1 0
1 0 0

Similarly, to detect diagonal neighbours, which contribute a distance of sqrt(2), the mask would be

1 0 1
0 0 0
1 0 1

but by the same reasoning as above it becomes

1 0 1
0 0 0

If this mask is multiplied by sqrt(2) and added to the first, the two convolutions can be replaced by one convolution with the combined mask

sqrt(2) 1  sqrt(2)
1       0        0

Start and end points are, by definition, the points with only one neighbour. To detect them we convolve with

1 1 1
1 0 1
1 1 1

and see which points give 1 as result.

To produce the combined mask of item 1 it's shorter to generate its square and then take the square root. The mask in item 2 is a predefined literal.

t     % Take input matrix implicitly. Duplicate
5B    % 5 in binary: [1 0 1]
Q     % Add 1; [2 1 2]
4B    % 4 in binary: [1 0 0]
&v    % Concatenate vertically
X^    % Square root of each entry
Z+    % 2D convolution, maintaining size
*     % Multiply, to only keep results corresponding to 1 in the input
ss    % Sum of all matrix entries. This gives total distance
Gt    % Push input again. Duplicate
3Y6   % Predefined literal. This gives third mask
Z+    % 2D convolution, maintaining size
1=    % Values different than 1 are set to 0
*     % Multiply, to only keep results corresponding to 1 in the input
&f    % Push array of row indices and array of column indices of nonzeros
d     % Difference. This is the horizontal difference between start and end
wd    % Swap, difference. This is the vertical difference between start and end
Yy    % Hypothenuse. This gives total distance in straight line
/     % Divide. Display implicitly


Python 2, 145 bytes

print'i am now tiny @ @s##s#ed#act#acts#@#@s#@ed#@ing#arguments#accusation#accusations#advertisings'.replace('#',' counter').replace('@','check')

Try it online!

Prints these words, separated by spaces:

i
am
now
tiny
check
checks
counter
counters
countered
counteract
counteracts
countercheck
counterchecks
counterchecked
counterchecking
counterarguments
counteraccusation
counteraccusations
counteradvertisings


Plant trees in a park - As fast as you can!

JavaScript (ES6), 271 bytes

Takes input as an array of arrays of characters. Returns an array of bitmasks (integers) describing the position of the trees on each row, where the least significant bit is the leftmost position.

f=(a,p=0,r=[S=y=0],w=a.length)=>a.some((R,y)=>a.some((_,x)=>r[y]>>x&1&&(o[k=R[x]]=-~o[k])>2),o=[])?0:y<w?[...Array(1<<w)].some((_,n)=>(k=n^(x=n&-n))<=x*2|k&-k^k|n&(p|p/2|p*2)||r.some((A,i)=>r.some((B,j)=>A&B&n&&i<y&j<i))?0:(w=r[y],f(a,r[y++]=n,r),r[--y]=w,S))&&S:S=[...r]

Formatted and commented

f = (                                           // given:
  a,                                            //   - a = input matrix
  p = 0,                                        //   - p = previous bitmask
  r = [                                         //   - r = array of tree bitmasks
        S = y = 0 ],                            //   - S = solution / y = current row
  w = a.length                                  //   - w = width of matrix
) =>                                            //
  a.some((R, y) => a.some((_, x) =>             // if there's at least one area with more
    r[y] >> x & 1 && (o[k = R[x]] = -~o[k]) > 2 // than two trees:
  ), o = []) ?                                  //
    0                                           //   abort right away
  :                                             // else:
    y < w ?                                     //   if we haven't reached the last row:
      [...Array(1 << w)].some((_, n) =>         //     for each possible bitmask n:
        (k = n ^ (x = n & -n)) <= x * 2 |       //       if the bitmask does not consist of
        k & - k ^ k |                           //       exactly two non-consecutive bits,
        n & (p | p / 2 | p * 2) ||              //       or is colliding with the previous
        r.some((A, i) => r.some((B, j) =>       //       bitmask, or generates more than two
          A & B & n && i < y & j < i            //       trees per column:
        )) ?                                    //
          0                                     //         yield 0
        :                                       //       else:
          (                                     //
            w = r[y],                           //         save the previous bitmask
            f(a, r[y++] = n, r),                //         recursive call with the new one
            r[--y] = w,                         //         restore the previous bitmask
            S                                   //         yield S
          )                                     //
      ) && S                                    //     end of some(): return false or S
    :                                           //   else:
      S = [...r]                                //     this is a solution: save a copy in S

Test cases

This snippet includes an additional function to display the results in a more readable format. It is too slow to solve the last test case.

Expected runtime: ~5 seconds.

f=(a,p=0,r=[S=y=0],w=a.length)=>a.some((R,y)=>a.some((_,x)=>r[y]>>x&1&&(o[k=R[x]]=-~o[k])>2),o=[])?0:y<w?[...Array(1<<w)].some((_,n)=>(k=n^(x=n&-n))<=x*2|k&-k^k|n&(p|p/2|p*2)||r.some((A,i)=>r.some((B,j)=>A&B&n&&i<y&j<i))?0:(w=r[y],f(a,r[y++]=n,r),r[--y]=w,S))&&S:S=[...r]

format = (a, w) => a.map(n => [...('0'.repeat(w) + n.toString(2)).slice(-w)].reverse().join('')).join('\n')

console.log(format(f([
  [..."aabbbbbcc"],
  [..."adddbbbcc"],
  [..."adeeecccc"],
  [..."adddefgcc"],
  [..."hhhdifggg"],
  [..."hdddifffg"],
  [..."hhhiifffg"],
  [..."hihiifffg"],
  [..."iiiiiiggg"]
]), 9));

console.log(format(f([
  [..."aaabbbccc"],
  [..."aaaabbccc"],
  [..."aaaddbcce"],
  [..."ffddddcce"],
  [..."ffffddeee"],
  [..."fgffdheee"],
  [..."fggfhhhee"],
  [..."iggggheee"],
  [..."iiigggggg"]
]), 9));

console.log(format(f([
  [..."aaaaabccdd"],
  [..."aeaabbbccd"],
  [..."aeaabfbgcd"],
  [..."eeeaafggcd"],
  [..."eeeaafghcd"],
  [..."eeeiifghcd"],
  [..."ieiiigghcd"],
  [..."iiijighhcd"],
  [..."jjjjighhcd"],
  [..."jjjggghhdd"]
]), 10));


CJam, 11 bytes

q__1m>.{er}

Test it here.

Explanation

q__    e# Read input and make two copies.
1m>    e# Rotate the second copy one character to the right.
.{er}  e# For each pair of characters from the second and third string,
       e# replace occurrences of the first with the second.


Can you calculate the average Levenshtein distance exactly?

Rust, score ≈ 22

This uses a dynamic programming approach (I’ve added an explanation here) whose running time seems to scale as approximately \$\tilde O(2^{1.5n})\$, rather than the \$\tilde O(2^{2n})\$ of a brute-force search.  On my Ryzen 7 1800X (8 cores/16 threads), it gets through \$1 \le n \le 21\$ in 1.7 minutes, \$1 \le n \le 22\$ in 5.1 minutes.

Now using SIMD for the inner loop.

src/main.rs

use fxhash::FxBuildHasher;
use itertools::izip;
use rayon::prelude::*;
use std::arch::x86_64::*;
use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::mem;
use typed_arena::Arena;

#[global_allocator]
static ALLOC: mimallocator::Mimalloc = mimallocator::Mimalloc;

type Distance = i8;
type Count = u32;
type Total = u64;

#[derive(Debug)]
struct Distances(__m128i);

impl PartialEq for Distances {
    fn eq(&self, other: &Distances) -> bool {
        unsafe {
            let x = _mm_xor_si128(self.0, other.0);
            _mm_testz_si128(x, x) != 0
        }
    }
}

impl Eq for Distances {}

impl Hash for Distances {
    fn hash<H: Hasher>(&self, state: &mut H) {
        unsafe {
            _mm_extract_epi64(self.0, 0).hash(state);
            _mm_extract_epi64(self.0, 1).hash(state);
        }
    }
}

fn main() {
    let splat0 = unsafe { _mm_set1_epi8(0) };
    let splat1 = unsafe { _mm_set1_epi8(1) };
    let splatff = unsafe { _mm_set1_epi8(!0) };
    let splat7f = unsafe { _mm_set1_epi8(0x7f) };
    let seq = unsafe { _mm_set_epi8(15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0) };
    let grow0 = unsafe {
        _mm_set_epi8(
            -0x80, 0, 0x20, 0, 0x8, 0, 0x2, 0, 0, 0x40, 0, 0x10, 0, 0x4, 0, 0x1,
        )
    };
    let grow1 = unsafe {
        _mm_set_epi8(
            0, 0x40, 0, 0x10, 0, 0x4, 0, 0x1, -0x80, 0, 0x20, 0, 0x8, 0, 0x2, 0,
        )
    };

    for n in 1 as Distance.. {
        if n > 31
            || (n as Count).leading_zeros() < n as u32
            || (n as Total).leading_zeros() < 2 * n as u32
        {
            break;
        }

        let total: Total = (0u32..1 << (n - 1))
            .into_par_iter()
            .map(|a| {
                let mut a_sym = a.reverse_bits();
                a_sym ^= (a_sym >> 31).wrapping_neg();
                a_sym >>= 32 - n as usize;
                if a_sym < a {
                    return 0;
                }

                let arena = Arena::<Distances>::new();
                let stride = (n as usize + 16) / 16 * 16;
                let idx = |i: Distance, j: Distance| i as usize + stride * j as usize;
                let both = |[x, y]: [Distance; 2]| x.max(y);
                let mut worst = vec![[stride as Distance; 2]; idx(0, n + 1)];
                for j in 0..=n {
                    worst[idx(n, j)] = [n - j; 2];
                }
                for i in (0..n).rev() {
                    worst[idx(i, n)] = [n - i; 2];
                    let good = (a >> i & 1) as usize;
                    let bad = good ^ 1;
                    for j in (0..n).rev() {
                        worst[idx(i, j)][good] = both(worst[idx(i + 1, j + 1)]);
                        worst[idx(i, j)][bad] = 1 + worst[idx(i + 1, j)][bad]
                            .min(both(worst[idx(i, j + 1)]))
                            .min(both(worst[idx(i + 1, j + 1)]));
                    }
                }
                let worst: &[Distances] = arena.alloc_extend(
                    worst
                        .into_iter()
                        .map(both)
                        .collect::<Box<[Distance]>>()
                        .chunks(16)
                        .map(|chunk| {
                            Distances(unsafe {
                                _mm_loadu_si128(chunk as *const [i8] as *const __m128i)
                            })
                        }),
                );

                let mut states: HashMap<&[Distances], Count, FxBuildHasher> = HashMap::default();
                let mut new_states = HashMap::default();

                states.insert(
                    arena.alloc_extend(
                        (0..n + 1)
                            .step_by(16)
                            .map(|i| Distances(unsafe { _mm_add_epi8(_mm_set1_epi8(i), seq) })),
                    ),
                    1,
                );

                let bvs: Vec<_> = [a, !a]
                    .iter()
                    .map(|b| {
                        arena.alloc_extend((0..n + 1).step_by(16).map(|i| unsafe {
                            let x = _mm_set1_epi16(((b << 1) >> i) as i16);
                            Distances(_mm_xor_si128(
                                _mm_cmpeq_epi8(
                                    _mm_or_si128(
                                        _mm_and_si128(x, grow0),
                                        _mm_and_si128(_mm_alignr_epi8(x, x, 1), grow1),
                                    ),
                                    splat0,
                                ),
                                splatff,
                            ))
                        }))
                    })
                    .collect();

                for j in 1..=n {
                    new_states.reserve(2 * states.len());
                    let worst_slice = &worst[idx(0, j) / 16..idx(0, j + 1) / 16];
                    for (state, count) in states.drain() {
                        for bv in &bvs {
                            let mut x = j;
                            let mut y = n.into();
                            let mut bound = n;

                            let new_state: &mut [Distances] =
                                arena.alloc_extend(izip!(&**bv, state, worst_slice).map(
                                    |(&Distances(bc), &Distances(yc), &Distances(wc))| unsafe {
                                        let o = _mm_min_epi8(
                                            _mm_add_epi8(yc, splat1),
                                            _mm_sub_epi8(
                                                _mm_insert_epi8(_mm_slli_si128(yc, 1), y, 0),
                                                bc,
                                            ),
                                        );
                                        y = _mm_extract_epi8(yc, 15);
                                        let o = _mm_sub_epi8(o, seq);
                                        let o = _mm_min_epi8(o, _mm_set1_epi8(x));
                                        let o = _mm_sub_epi8(splat7f, o);
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 1));
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 2));
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 4));
                                        let o = _mm_max_epu8(o, _mm_slli_si128(o, 8));
                                        let o = _mm_sub_epi8(splat7f, o);
                                        x = _mm_extract_epi8(o, 15) as i8 + 16;
                                        let o = _mm_add_epi8(o, seq);
                                        let z = _mm_add_epi8(o, wc);
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 1));
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 2));
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 4));
                                        let z = _mm_min_epi8(z, _mm_srli_si128(z, 8));
                                        bound = bound.min(_mm_extract_epi8(z, 0) as i8);
                                        Distances(o)
                                    },
                                ));

                            let bound = unsafe { _mm_set1_epi8(bound) };
                            for (i, Distances(x)) in (0..).step_by(16).zip(&mut *new_state) {
                                *x = unsafe {
                                    _mm_min_epi8(
                                        *x,
                                        _mm_sub_epi8(
                                            bound,
                                            _mm_abs_epi8(_mm_add_epi8(_mm_set1_epi8(i - j), seq)),
                                        ),
                                    )
                                };
                            }

                            *new_states.entry(&*new_state).or_insert(0) += count;
                        }
                    }
                    mem::swap(&mut states, &mut new_states);
                }

                let control = unsafe { _mm_insert_epi8(splatff, (n % 16).into(), 0) };
                Total::from(
                    states
                        .into_iter()
                        .map(|(state, count)| unsafe {
                            count
                                * _mm_extract_epi8(
                                    _mm_shuffle_epi8(state[n as usize / 16].0, control),
                                    0,
                                ) as Count
                        })
                        .sum::<Count>(),
                ) * if a_sym == a { 1 } else { 2 }
            })
            .sum();

        let shift = total.trailing_zeros();
        println!(
            "{} {}/{}",
            n,
            total >> shift,
            (1 as Total) << (2 * n as u32 - 1 - shift),
        );
    }
}

Cargo.toml

[package]
name = "levenshtein"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"

[profile.release]
lto = true
codegen-units = 1

[dependencies]
fxhash = "0.2.1"
itertools = "0.8.2"
mimallocator = "0.1.3"
rayon = "1.3.0"
typed-arena = "2.0.0"

Running

RUSTFLAGS='-C target-cpu=native' cargo build --release
target/release/levenshtein

Output

(With cumulative timing data prepended by ts -s %.s.)

0.000008 1 1/2
0.000150 2 1/1
0.000219 3 47/32
0.000282 4 243/128
0.000344 5 1179/512
0.000413 6 2755/1024
0.000476 7 12561/4096
0.000538 8 56261/16384
0.000598 9 124329/32768
0.000660 10 2175407/524288
0.000721 11 589839/131072
0.000782 12 40664257/8388608
0.000843 13 174219279/33554432
0.006964 14 742795299/134217728
0.068070 15 1576845897/268435456
0.310136 16 13340661075/2147483648
1.062122 17 14062798725/2147483648
3.586745 18 59125997473/8589934592
11.265840 19 123976260203/17179869184
33.691822 20 259354089603/34359738368
101.514674 21 8662782598909/1099511627776
307.427106 22 72199426617073/8796093022208
956.299101 23 150173613383989/17592186044416
3077.477731 24 1247439983177201/140737488355328
10276.205241 25 5173410986415247/562949953421312
34550.754308 26 5356540527479769/562949953421312

Static core2 build for Anush


Optimize Compiler for simple Reverse Polish Notation Programming Language

Wolfram Language (Mathematica), 733 728 690 564 516 506 513 548 bytes

j=Integer;f=Flatten;s=SequenceReplace;A=FixedPoint[f@s[#,{{x_j,p,y_j,t}->{y,t,x*y,p},{x_j,y_j,p}->x+y,{x_j,y_j,t}->x*y,{x_j,p,y_j,p}->{x+y,p},{x_j,t,y_j,t}->{x*y,t},{0,p}|{1,t}->{},{0,t}->{d,0}}]//.{a___,Except[i|o]}->{a}&,#]&;B=Expand@Check[f@FoldPairList[f/@Switch[#2,i,{{i},{#,i@c++}},o,{{Last@#},#},d,{{},Most@#},p,{{},{#[[;;-3]],Tr@#[[-2;;]]}},t,{{},{#[[;;-3]],#[[-2]]*Last@#}},_,{{},{##}}]&,c=0;{},#],x]&;F=MinimalBy[w=A@f[#/.m->{-1,t,p}];z=B@w;s[#,{-1,t,p}->m]&/@A/@Select[Permutations@Join[w,Cases[z /.i@_->i,_j,∞]],B@#==z&],Length][[1]]&

Try it online!

This is a four-step tour-de-force that (1) replaces "-" with "-1 * +" so that we don't have to deal with subtractions, (2) simplifies the list of commands a bit, (3) makes a list of all permutations of this list of commands and picks out those that give the same result when parsed (executed), and (4) simplifies these lists of commands a bit and picks the shortest, after converting certain operations back to subtractions.

This code is terribly inefficient because it goes through the list of all permutations of the input code. For long input codes I don't recommend running this code; but as I read it there are no runtime or memory restrictions in this challenge.

This code does the optimization step after converting all "-" operations to "+" operations with signs flipped, and only at the end re-introduces the "-" operator when converting code back to strings. This implies for example that "i -1 i * + o" is correctly optimized to "i i - o".

As the i/o format requirement is quite loose, this code takes and returns code as lists, where the symbols "+", "-", "*" are represented by p, m, t, tokens respectively. The conversion from and to strings is done in the wrapper function given on TIO:

G[S_] := StringReplace[{"p" -> "+", "m" -> "-", "t" -> "*"}]@StringRiffle@
         Quiet@F@
         ToExpression[StringSplit[S] /. {"+" -> p, "-" -> m, "*" -> t}]

Un-golfed version, including the string-format wrapper and minimizing the final code string length instead of the number of tokens, and including a few more transformation niceties:

(* convert code string to list of operators *)
inputfilter[s_] := ToExpression[Flatten[StringSplit[s] /.
  {"i" -> i, "o" -> o, "d" -> d, "+" -> p, "-" -> {-1, t, p}, "*" -> t}]]

(* convert list of operators to code string *)
outputfilter[s_] := StringReplace[StringRiffle@Flatten@SequenceReplace[s,
  {{-1, t, p} -> m,                         (* convert "-1 t p" back to "-"             *)
   {x_ /; x < 0, p} -> {-x, m},             (* convert "y x +" to "y -x -" when x<0     *)
   {x_ /; x < 0, t, p} -> {-x, t, m}}],     (* convert "y x * +" to "y -x * -" when x<0 *)
  {"m" -> "-", "p" -> "+", "t" -> "*"}]     (* backsubstitution of symbols              *)

(* simplify a list of operators somewhat *)
simplifier[s_] := FixedPoint[Flatten@SequenceReplace[#,
  {{x_Integer, p, y_Integer, t} -> {y, t, x*y, p},  (*  "x + y *" -> "y * (xy) +"       *)
   {x_Integer, y_Integer, p} -> x + y,              (*  "x y +" -> "(x+y)"              *)
   {x_Integer, y_Integer, t} -> x*y,                (*  "x y *" -> "(xy)"               *)
   {x_Integer, p, y_Integer, p} -> {x + y, p},      (*  "x + y +" -> "(x+y) +"          *)
   {x_Integer, t, y_Integer, t} -> {x*y, t},        (*  "x * y *" -> "(xy) *            *)
   {0, p} | {1, t} -> {},                           (*  "0 +" and "1 *" are deleted     *)
   {x_Integer, i, p} -> {i, x, p},                  (*  "x i +" -> "i x +"              *)
   {x_Integer, i, t} -> {i, x, t},                  (*  "x i *" -> "i x *"              *)
   {0, t} -> {d, 0}}] //.                           (*  "0 *" -> "d 0"                  *)
  {a___, Except[i | o]} -> {a} &, s]                (* delete trailing useless code     *)

(* execute a list of operators and return the list of generated outputs *)
parse[s_] := Expand@Quiet@Check[Flatten@FoldPairList[  (* stack faults are caught here     *)
  Function[{stack, command},                        (* function called for every command*)
    Flatten /@ Switch[command,                      (* code interpretation:             *)
    i, {{i}, {stack, i[inputcounter++]}},           (* output "i" and add input to stack*)
    o, {{stack[[-1]]}, stack},                      (* output top of stack              *)
    d, {{}, Most[stack]},                           (* delete top of stack              *)
    p, {{}, {stack[[;; -3]], stack[[-2]] + stack[[-1]]}},  (* add two stack elements    *)
    t, {{}, {stack[[;; -3]], stack[[-2]]*stack[[-1]]}},    (* multiply two stack elements*)
    _, {{}, {stack, command}}]],                    (* put number onto stack            *)
    inputcounter = 0; {},                           (* start with zero input counter and empty stack*)
    s],                                             (* loop over code list              *)
  x]                                                (* return "x" if an error occurred  *)

(* the main function that takes a code string and returns an optimized code string *)
F[s_] := Module[{w, q},
  w = simplifier@inputfilter@s;      (* convert input to useful form *)
  q = parse[w];                      (* execute input code *)
  MinimalBy[
    outputfilter@*simplifier /@      (* simplify and stringify selected codes          *)
      Select[Permutations[w],        (* all permutations of code list                  *)
             parse[#] == q &],       (* select only those that give the correct output *)
    StringLength] // Union]          (* pick shortest solution by length               *)

Thanks to @redundancy for catching a bug: The parser needs a Expand applied to the output in order to handle distributive equivalence. 506→513

update

Now also optimizes 1 o 1 + o to 1 o 2 o. This was a surprisingly difficult case and made the code much slower. 513→548


How do I split a string??? Help plz? (code trolling)

C

  My homework assignment is take a string and split it into pieces at every new line. I have no idea what to do! Please help!

Tricky problem for a beginning C programming class!  First you have to understand a few basics about this complicated subject.

A string is a sequence made up of only characters.  This means that in order for programmers to indicate an "invisible" thing (that isn't a space, which counts as a character), you have to use a special sequence of characters somehow to mean that invisible thing.

On Windows, the new line is a sequence of two characters in the string: backslash and n (or the string "\n")
On Linux or OS/X Macs, it is a sequence of four characters: backslash, n, backslash, and then r: (or "\n\r").

(Interesting historical note: on older Macintoshes it was a different sequence of four characters: "\r\n"... totally backwards from how Unix did things!  History takes strange roads.)

It may seem that Linux is more wasteful than Windows, but it's actually a better idea to use a longer sequence.  Because Windows uses such a short sequence the C language runtime cannot print out the actual letters \n without using special system calls.  You can usually do it on Linux without a system call (it can even print \n\ or \n\q ... anything but \n\r).  But since C is meant to be cross platform it enforces the lowest common-denominator.  So you'll always be seeing \n in your book.

(Note: If you're wondering how we're talking about \n without getting newlines every time we do, StackOverflow is written almost entirely in HTML...not C.  So it's a lot more modern.  Many of these old aspects of C are being addressed by things you might have heard about, like CLANG and LLVM.)

But back to what we're working on.  Let's imagine a string with three pieces and two newlines, like:

"foo\nbaz\nbar"

You can see the length of that string is 3 + 2 + 3 + 2 + 3 = 13.  So you have to make a buffer of length 13 for it, and C programmers always add one to the size of their arrays to be safe.  So make your buffer and copy the string into it:

/* REMEMBER: always add one to your array sizes in C, for safety! */
char buffer[14];
strcpy(buffer, "foo\nbaz\nbar");

Now what you have to do is look for that two-character pattern that represents the newline.  You aren't allowed to look for just a backslash.  Because C is used for string splitting quite a lot, it will give you an error if you try.  You can see this if you try writing:

char pattern[2];
strcpy(pattern, "\");

(Note: There is a setting in the compiler for if you are writing a program that just looks for backslashes.  But that's extremely uncommon; backslashes are very rarely used, which is why they were chosen for this purpose.  We won't turn that switch on.)

So let's make the pattern we really want, like this:

char pattern[3];
strcpy(pattern, "\n");

When we want to compare two strings which are of a certain length, we use strncmp.  It compares a certain number of characters of a potentially larger string, and tells you whether they match or not.  So strncmp("\nA", "\nB", 2) returns 1 (true).  This is even though the strings aren't entirely equal over the length of three... but because only two characters are needed to be.

So let's step through our buffer, one character at a time, looking for the two character match to our pattern.  Each time we find a two-character sequence of a backslash followed by an n, we'll use the very special system call (or "syscall") putc to put out a special kind of character: ASCII code 10, to get a physical newline.

#include "stdio.h"
#include "string.h"

char buffer[14]; /* actual length 13 */
char pattern[3]; /* actual length 2 */
int i = 0;

int main(int argc, char* argv[]) {
    strcpy(buffer, "foo\nbar\nbaz");
    strcpy(pattern, "\n");

    while (i < strlen(buffer)) {
       if (1 == strncmp(buffer + i, pattern, 2)) {
           /* We matched a backslash char followed by n */
           /* Use syscall for output ASCII 10 */
           putc(10, stdout);
           /* bump index by 2 to skip both backslash and n */
           i += 2;
       } else {
           /* This position didn't match the pattern for a newline */
           /* Print character with printf */
           printf("%c", buffer[i]);
           /* bump index by 1 to go to next matchable position */
           i += 1;
       }
    }

    /* final newline and return 1 for success! */
    putc(10, stdout);
    return 1;
}

The output of this program is the desired result...the string split!

foo
baz
bar

\t is for \trolling...

   Absolutely incorrect from the top to the bottom.  Yet filled with plausible-sounding nonsense that has scrambled information like what's in the textbook or Wikipedia.  Program logic appears transparent in the context of the misinformation, but is completely misleading.  Even global variables and returning an error code, for good measure...

...

   Of course, there's only one character in the C string representation of the two-character source literal sequence \n.  But making a buffer larger is harmless, as long as strlen() is used to get the actual length to operate on.

...

   We try to convince the reader that strncmp is a boolean operation that either matches (1) or doesn't (0).  But it actually has three return values (-1 matching less, 0 for equal, 1 for matching greater).  Our two character "pattern" being compared is not [\, n], but rather [\n, \0]...picking up the implicit null terminator.  As that sequence slides through the string it will never be greater than a two-character sequence it's compared to...at best it will be zero if there is a terminating newline in the input string.

...

   So all this does is loop through the string and print it one character at a time.  The top branch never runs.  (Though you could get it to if your string had lower-than \n codes in it, say tab...which could be used to mysteriously omit characters from the output :-P)


JS ES6, 360 bytes

f=(i,p=1,d=[])=>fetch(`https://api.stackexchange.com/2.2/users/${i}/reputation?site=codegolf&pagesize=100&page=${p}`).then(x=>x.json()).then(j=>(q=d.concat(j.items),j.has_more?f(i,p+1,q):(r=[],q.map(s=>(r[d=new Date(s.on_date*1000),i=d.getDate()+d.getMonth()*32+d.getYear()*365]?r[i]+=s.reputation_change:r[i]=s.reputation_change)),r.filter(x=>x>200).length)))

Call it like f(user id). Returns a promise that resolves with the number of days that rep was lost.

Ungolfed:

f=(i,p=1,d=[])=>fetch(`https://api.stackexchange.com/2.2/users/${i}/reputation?site=codegolf&pagesize=100&page=${p}&key=kAc8QIHB*IqJDUFcjEF1KA((`).then(x=>x.json()).then(j=>{
    return (q=d.concat(j.items),
    j.has_more?
        f(i,p+1,q)

        :(r=[],
            q.map(s=>(r[d=new Date(s.on_date*1000),
                i=d.getDate()+d.getMonth()*32+d.getYear()*365]?
                    r[i]+=s.reputation_change

                    :r[i]=s.reputation_change)),
            r.filter(x=>x>200).length
        )
    )
});


How many of each pill to take to achieve the total daily dose

R, 53 38 bytes

function(x)c(x%/%5,2*x%%1,(x<20)*x%%5)

Try it online!
Output is in the order (5mg, 2.5mg, 1mg).
For the 2.5mg pills:

if the dose is an integer, we need 0 such pills. Indeed, 1 pill of 2.5 mg would not give an integer, and 2 pills of 2.5 mg can be replaced by a single 5mg pill
if the dose x is not an integer, we need exactly 1 such pill (similar argument), and then we call the function with the integer x-2.5.

The number of 5 mg pills is the integer division of the input by 5.
Note that because the input is restricted, the 1 mg pills are never needed when the input is ≥20. If the input is <20, the number of 1mg pills is given by taking the input modulo 5.


Code close to the challenge: Sum of integers

Python, distance 3

#Given a set of integers, find the
sum#of all integers in it.

This gives the built-in function sum, which can sum a set like sum({3,5,7})==17. The remaining parts are commented. This has distance 3, with 3 edits:

Add the initial #
Add a newline
Replace the space after sum with #


Python 3, 31
Saved 1 byte thanks to xnor.
Only one byte away from ES6. :/ Stupid Python and its long anonymous function syntax.
Hooray for one liners!
lambda x,y:x*"AB"or"AC"+"ED"[y]

Test cases:
assert f(1, 1) == "AB"
assert f(1, 0) == "AB"
assert f(0, 1) == "ACD"
assert f(0, 0) == "ACE"


Python 2, 43 39 bytes

f=lambda n,i=2:n/i and n*2-n%i+f(n,i*2)

Try it online!

How?

Each call of the recursive function calculates a single dilution. The position of the inserted 0 is log2(i). The function recurses until i gets bigger than n and the insertion would be on the left of the number. If i>n, n/i evaluates to 0, which is a falsy value in Python.

n*2 shifts the entire number one binary digit left, n%i or n % 2**(position of insertion) calculates the value of the part that should not be shifted left. This value gets subtracted from the shifted number.

Example (n=7)

call       n/i          bin(n)  n*2     n%i   dilution       return value

f(7, i=2)  3 => truthy  0b111   0b1110  0b1   0b1101 = 13    13 + f(7, 2*2) = 13 + 11 = 24
f(7, i=4)  1 => truthy  0b111   0b1110  0b11  0b1011 = 11    11 + f(7, 4*2) = 11 + 0 = 11
f(7, i=8)  0 => falsy                                        0


Create an application that restarts itself after n-seconds once

Batch, 34 28 bytes

timeout/t %1
if %1 neq [] %0

Input time in seconds as the first argument. If no argument is present, as well as after restarting, it spews out error messages (follow both commands with 2>NUL to get rid of them). The new instance opens in the same window (OP said it's allowed).


Language : Java
Score : 555 533
I just went for trying to brute force a solution by iterating over the shapes in order of decreasing area (perimeter in case of tie) and trying out all packing possibilities until a valid packing is found for that shape at which point the shape's position is fixed and the algorithm goes on to the next shape. In order to hopefully improve the quality of the result when searching for a valid packing first all possible positions are tried with the shape rotated such that it is taller than it is wider.
Note: this assumes that the input image(s) have all of the shapes separated by white space. It takes the maximum width of the output as the first argument and a list of shape images as the other arguments (each shape image can have one or more shape separated by at least one line of white pixels)
import java.awt.Color;
import java.awt.Graphics;
import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import javax.imageio.ImageIO;

public class Packer {
    public static void main(String[] args) throws Exception {
        long t1 = System.currentTimeMillis();

        int width = Integer.valueOf(args[0]);
        List<Item> itemList = new ArrayList<Item>();
        for (int i = 1; i < args.length; i++) {
            itemList.addAll(getItems(ImageIO.read(new File(args[i]))));
        }

        File outputFile = new File("output.png");
        if (outputFile.exists()) {
            outputFile.delete();
        }
        outputFile.createNewFile();

        ImageIO.write(pack(itemList, width), "PNG", outputFile);
        long t2 = System.currentTimeMillis();
        System.out.println("Finished in " + (t2 - t1) + "ms");
    }

    private static BufferedImage pack(List<Item> itemList, int width) {
        System.out.println("Packing " + itemList.size() + " items");
        Collections.sort(itemList, new Comparator<Item>() {

            @Override
            public int compare(Item o1, Item o2) {
                return o1.area < o2.area ? 1 : (o1.area > o2.area ? -1
                        : (o1.perimiter < o2.perimiter ? 1
                                : (o1.perimiter > o2.perimiter ? -1 : 0)));
            }
        });
        Packing packing = new Packing(width);
        PackedItem.Rotation[] widthRots = { PackedItem.Rotation.ZERO,
                PackedItem.Rotation.ONE_EIGHTY };
        PackedItem.Rotation[] heightRots = { PackedItem.Rotation.NINETY,
                PackedItem.Rotation.TWO_SEVENTY };
        int count = 0;
        for (Item item : itemList) {
            count++;
            int minSize = Math.min(item.width, item.height);
            int maxSize = Math.max(item.width, item.height);
            int x = 0;
            int y = 0;
            int rot = 0;
            PackedItem.Rotation[] rots = widthRots;
            if (item.width > item.height) {
                rots = heightRots;
            }
            boolean rotsSwitched = false;

            PackedItem packedItem = new PackedItem(item, rots[rot], x, y);
            System.out.format("Packing item %d which is %d by %d\n", count,
                    item.width, item.height);
            while (!packing.isValidWith(packedItem)) {
                if (rot == 0) {
                    rot = 1;
                } else {
                    rot = 0;
                    if (x + minSize >= width) {
                        x = 0;
                        y++;
                        if (!rotsSwitched
                                && y + maxSize > packing.height) {
                            rotsSwitched = true;
                            if (item.width > item.height) {
                                rots = widthRots;
                            } else {
                                rots = heightRots;
                            }
                            y = 0;
                        }
                    } else {
                        x++;
                    }
                }
                packedItem.set(x, y, rots[rot]);
            }
            packing.addItem(packedItem);
            System.out.format("Packed item %d\n", count);
        }
        return packing.getDrawing();
    }

    private static List<Item> getItems(BufferedImage image) {
        List<Item> itemList = new ArrayList<Item>();
        boolean[][] pointsProcessed = new boolean[image.getWidth()][image
                .getHeight()];

        for (int i = 0; i < image.getWidth(); i++) {
            for (int j = 0; j < image.getHeight(); j++) {
                if (pointsProcessed[i][j]) {
                    continue;
                }
                ImagePoint point = ImagePoint.getPoint(i, j, image);
                if (point.getColor().equals(Color.WHITE)) {
                    pointsProcessed[point.x][point.y] = true;
                    continue;
                }
                Collection<ImagePoint> itemPoints = new ArrayList<ImagePoint>();
                Queue<ImagePoint> pointsToProcess = new LinkedList<ImagePoint>();
                pointsToProcess.add(point);
                while (!pointsToProcess.isEmpty()) {
                    point = pointsToProcess.poll();
                    if (pointsProcessed[point.x][point.y]) {
                        continue;
                    }
                    pointsProcessed[point.x][point.y] = true;
                    if (point.getColor().equals(Color.WHITE)) {
                        continue;
                    }
                    itemPoints.add(point);
                    pointsToProcess.addAll(point.getNeighbors());
                }
                itemList.add(new Item(itemPoints));
            }
        }

        return itemList;
    }

    private interface Point {
        int getX();

        int getY();

        Color getColor();
    }

    private static final class ImagePoint implements Point {
        private static final Map<BufferedImage, Map<Integer, Map<Integer, ImagePoint>>> POINT_CACHE = new HashMap<BufferedImage, Map<Integer, Map<Integer, ImagePoint>>>();
        private final int x;
        private final int y;
        private final Color color;
        private final BufferedImage image;
        private Collection<ImagePoint> neighbors;

        private ImagePoint(int x, int y, BufferedImage image) {
            this.x = x;
            this.y = y;
            this.image = image;
            this.color = new Color(image.getRGB(x, y));
        }

        static ImagePoint getPoint(int x, int y, BufferedImage image) {
            Map<Integer, Map<Integer, ImagePoint>> imageCache = POINT_CACHE
                    .get(image);
            if (imageCache == null) {
                imageCache = new HashMap<Integer, Map<Integer, ImagePoint>>();
                POINT_CACHE.put(image, imageCache);
            }
            Map<Integer, ImagePoint> xCache = imageCache.get(x);
            if (xCache == null) {
                xCache = new HashMap<Integer, Packer.ImagePoint>();
                imageCache.put(x, xCache);
            }
            ImagePoint point = xCache.get(y);
            if (point == null) {
                point = new ImagePoint(x, y, image);
                xCache.put(y, point);
            }
            return point;
        }

        Collection<ImagePoint> getNeighbors() {
            if (neighbors == null) {
                neighbors = new ArrayList<ImagePoint>();
                for (int i = -1; i <= 1; i++) {
                    if (x + i < 0 || x + i >= image.getWidth()) {
                        continue;
                    }
                    for (int j = -1; j <= 1; j++) {
                        if ((i == j && i == 0) || y + j < 0
                                || y + j >= image.getHeight()) {
                            continue;
                        }
                        neighbors.add(getPoint(x + i, y + j, image));
                    }
                }
            }
            return neighbors;
        }

        @Override
        public int getX() {
            return y;
        }

        @Override
        public int getY() {
            return x;
        }

        @Override
        public Color getColor() {
            return color;
        }
    }

    private static final class Item {
        private final Collection<ItemPoint> points;
        private final int width;
        private final int height;
        private final int perimiter;
        private final int area;

        Item(Collection<ImagePoint> points) {
            int maxX = Integer.MIN_VALUE;
            int minX = Integer.MAX_VALUE;
            int maxY = Integer.MIN_VALUE;
            int minY = Integer.MAX_VALUE;
            for (ImagePoint point : points) {
                maxX = Math.max(maxX, point.x);
                minX = Math.min(minX, point.x);
                maxY = Math.max(maxY, point.y);
                minY = Math.min(minY, point.y);
            }
            this.width = maxX - minX;
            this.height = maxY - minY;
            this.perimiter = this.width * 2 + this.height * 2;
            this.area = this.width * this.height;
            this.points = new ArrayList<ItemPoint>(points.size());
            for (ImagePoint point : points) {
                this.points.add(new ItemPoint(point.x - minX, point.y - minY,
                        point.getColor()));
            }
        }

        private static final class ItemPoint implements Point {
            private final int x;
            private final int y;
            private final Color color;

            public ItemPoint(int x, int y, Color color) {
                this.x = x;
                this.y = y;
                this.color = color;
            }

            @Override
            public int getX() {
                return x;
            }

            @Override
            public int getY() {
                return y;
            }

            @Override
            public Color getColor() {
                return color;
            }
        }
    }

    private static final class PackedItem {
        private final Collection<PackedPoint> points;
        private Rotation rotation;
        private int x;
        private int y;
        private AffineTransform transform;
        private int modCount;

        PackedItem(Item item, Rotation rotation, int x, int y) {
            this.set(x, y, rotation);
            this.points = new ArrayList<PackedPoint>();
            for (Point point : item.points) {
                this.points.add(new PackedPoint(point));
            }
        }

        void set(int newX, int newY, Rotation newRotation) {
            modCount++;
            x = newX;
            y = newY;
            rotation = newRotation;
            transform = new AffineTransform();
            transform.translate(x, y);
            transform.rotate(this.rotation.getDegrees());
        }

        void draw(Graphics g) {
            Color oldColor = g.getColor();
            for (Point point : points) {
                g.setColor(point.getColor());
                g.drawLine(point.getX(), point.getY(), point.getX(),
                        point.getY());
            }
            g.setColor(oldColor);
        }

        private enum Rotation {
            ZERO(0), NINETY(Math.PI / 2), ONE_EIGHTY(Math.PI), TWO_SEVENTY(
                    3 * Math.PI / 2);

            private final double degrees;

            Rotation(double degrees) {
                this.degrees = degrees;
            }

            double getDegrees() {
                return degrees;
            }
        }

        private final class PackedPoint implements Point {
            private final Point point;
            private final Point2D point2D;
            private int x;
            private int y;
            private int modCount;

            public PackedPoint(Point point) {
                this.point = point;
                this.point2D = new Point2D.Float(point.getX(), point.getY());
            }

            @Override
            public int getX() {
                update();
                return x;
            }

            @Override
            public int getY() {
                update();
                return y;
            }

            private void update() {
                if (this.modCount != PackedItem.this.modCount) {
                    this.modCount = PackedItem.this.modCount;
                    Point2D destPoint = new Point2D.Float();
                    transform.transform(point2D, destPoint);
                    x = (int) destPoint.getX();
                    y = (int) destPoint.getY();
                }
            }

            @Override
            public Color getColor() {
                return point.getColor();
            }
        }
    }

    private static final class Packing {
        private final Set<PackedItem> packedItems = new HashSet<PackedItem>();
        private final int maxWidth;
        private boolean[][] pointsFilled;
        private int height;

        Packing(int maxWidth) {
            this.maxWidth = maxWidth;
            this.pointsFilled = new boolean[maxWidth][0];
        }

        void addItem(PackedItem item) {
            packedItems.add(item);
            for (Point point : item.points) {
                height = Math.max(height, point.getY() + 1);
                if (pointsFilled[point.getX()].length < point.getY() + 1) {
                    pointsFilled[point.getX()] = Arrays.copyOf(
                            pointsFilled[point.getX()], point.getY() + 1);
                }
                pointsFilled[point.getX()][point.getY()] = true;
            }
        }

        BufferedImage getDrawing() {
            BufferedImage image = new BufferedImage(maxWidth, height,
                    BufferedImage.TYPE_INT_ARGB);
            Graphics g = image.getGraphics();
            g.setColor(Color.WHITE);
            g.drawRect(0, 0, maxWidth, height);
            for (PackedItem item : packedItems) {
                item.draw(g);
            }
            return image;
        }

        boolean isValidWith(PackedItem item) {
            for (Point point : item.points) {
                int x = point.getX();
                int y = point.getY();
                if (y < 0 || x < 0 || x >= maxWidth) {
                    return false;
                }
                boolean[] column = pointsFilled[x];
                if (y < column.length && column[y]) {
                    return false;
                }
            }
            return true;
        }
    }
}

The solution this produces (takes about 4 minutes 30 seconds on my machine) is:

Looking at this picture it seems like the result can be improved by iterating over all of the shapes post packing and trying to move them all up a bit. I might try doing that later.


Jelly, 4 bytes

S=|/

Try it online!

Test whether the sum is equal to the bitwise-or-sum (i.e. a+b+c == a|b|c).


Python 2, 56 53 50 bytes

q=[]
for i in input():q=[[i]+q,q[:i]][i<0]
print q

Try it Online!

Dequeue is -1. This trick allows easy pythonic slicing of the queue.


Integer goes back and forth through time


Perl, 150 149 146 145 141 140 138 136 135 133 130 126 125 124

Added +7 for -F -Xn0i

An initial attempt.

Run with the map on STDIN and the directions after the -i option, e.g.

perl -F -Xn0iRL incomplete.pl
.....A
.#.###
B....C
##.#.#
D....E
##F###

Close STDIN with ^D or ^Z or whatever works on your operating system.

incomplete.pl:

%P=0;$^I=~s``{%;=!/
/;%P=map{$_|=$F[$^H=$_+=(1,@+,-1,"-@+")[$d&3]]=~/(\w)|#|^$/*~!\$;{$1}}(%P)x@F}$d-=B&$'^u`eg;print%

Replace the ^H by the literal control character to get the given score

Bonus question:

There is no input that results in only I
The shortest input that results in only U is RLLRRLLRLRLRRLRRLRLRLRRLLR
The longest input needed to result in a unique set is RLLRRRLRLRLLLRRLRLLLLLRRRLLRRRLLLLLLLRRLRRRR which gives B O R


Wolfram Language (Mathematica), 55 bytes

0&@@Area@BooleanRegion[And,Simplex[{0{,}}~Join~#]&/@#]&

Try it online!

Shaved a few bytes off the trivial answer.

%@{{{5, 1}, {1, 3}}, {{3, 4}, {4, -3}}} yields 46375/10296 or 4.504176379

Replacing Area with DiscretizeRegion will show the intersection.

By the way, this will work with any simplexes, not just triangles.

-1 Byte thanks to JungHwan Min

@user202729's suggestion added 4 bytes but makes it yield 0 for degenerate triangles


Reproportioning a population by adding fixed sized groups

C

void reproportion(
        const unsigned int n,
        const unsigned int *const starting_population,
        const unsigned int *const reproportion_goal,
        unsigned int *const new_population)
{
    unsigned int unit = 1U;

    for(unsigned int i = 0U; i != n; ++i) {
        unit *= starting_population[i];
    }

    for(unsigned int i = 0U; i != n; ++i) {
        new_population[i] = reproportion_goal[i] * unit;
    }
}

This assumes that the original subpopulation sizes are greater than zero. starting_population = { 0, 1, 2 } and reproportion_goal = { 0, 50, 50 } would give the incorrect result of new_population = { 0, 0, 0 }. If the original subpopulation size can be zero, unit *= starting_population[i]; should be preceded by if(starting_population[i] != 0U).

Call this function from within your program like so:

#include <stdio.h>

int main(void)
{
    unsigned int starting_population[] = { 1, 2, 31, 4 };
    unsigned int reproportion_goal[] = { 25, 25, 40, 10 };
    unsigned int new_population[4];

    reproportion(4, starting_population, reproportion_goal, new_population);

    for(int i = 0; i < 4; ++i) {
        printf("%d ", new_population[i]);
    }
}


Smallest n-digit prime containing only these digits

Bash + bsd-games package, 28 bytes

18 bytes saved thanks to @Dennis.

primes 1|egrep -wm1 [$2]{$1}

Input given at the command-line as n followed by k as a non-delimited list of digits.
Try it online.


How to write a C program for multiplication without using the * and + operators?

Always use recursion

Recusion is the right way!

int inc(int x) {
    return x&1?inc(x>>1)<<1:x|1;
}

int dec(int x) {
    return x&1?x^1:dec(x>>1)<<1|1;
}

int add(int x, int y) {
    return x?add(dec(x),inc(y)):y;
}

int mul(int x, int y) {
    return x?x^1?add(y,mul(dec(x),y)):y:0;
}

int main() {
    int a, b;
    scanf("%i\n%i", &a, &b);
    printf("%i", mul(a,b));
}


Python 3
I am giving this entry the name The Differ.
Code:
import urllib.request, gzip, re, json, difflib, sys
API_URL = "https://api.stackexchange.com/"
qurl = input()
qid = int(re.search("\d+",qurl).group(0))
def request(url,wrapper=False,**params):
    params.setdefault("filter","withbody")
    params.setdefault("site","codegolf")
    url = API_URL + url + "?"+"&".join([str(k)+"="+str(v) for k,v in params.items()])
    compressed_response = urllib.request.urlopen(url)
    response = gzip.decompress(compressed_response.read()).decode("utf8")
    response_object = json.loads(response)
    if wrapper:
        return response_object
    else:
        return response_object["items"]
question = request("questions/%s"%qurl)[0]
tags = ";".join(question["tags"])
title = question["title"]
escaped = title.replace(" ","%20")
related = request("similar",title=escaped,pagesize=100)
hasmore = False
length = sys.maxsize
for tag in question["tags"]:
    result = request("search",tagged=tag,
                     wrapper=True,
                     filter="!-*f(6rc.cI8O",
                     pagesize=100)
    if result["total"] < length:
        length = result["total"]
        related.extend(result["items"])
        hasmore = result["has_more"]
        besttag = tag
related.extend(best)
if length < 1500:
    for page in itertools.count(2):
        if not hasmore:
            break
        response = request("search",
                           tagged=besttag,
                           page=page,
                           pagesize=100,
                           filter="!-*f(6rc.cI8O",
                           wrapper=True)
        hasmore = response["has_more"]
        related.extend(result["items"])
matcher = difflib.SequenceMatcher(None, question["body"], None)
titlematcher = difflib.SequenceMatcher(None, question["title"], None)
seen = set()
seen.add(question["question_id"])
for possible in related:
    matcher.set_seq2(possible["body"])
    titlematcher.set_seq2(possible["title"])
    score = matcher.ratio()+titlematcher.ratio()
    qid = possible["question_id"]
    if score > .85 and qid not in seen:
        print(qid)
        seen.add(qid)
print("end")

The filter "!-*f(6rc.cI8O" included the total parameter on the global wrapper object and the body parameter on questions.
This entry makes two API requests plus one per tag on the question plus one per hundred questions in its least used tag. If it hits an api throttle (which it doesn't check for), it will raise an urllib.error.HTTPError: HTTP Error 400: Bad Request


Ruby, 327 bytes

(scroll to the bottom)

Mathematica, bonus answer

I'm only going for the graphical submission right now. I might port this to Ruby later and golf it if I feel like it.

(* This function tests for an intersection between the laser beam
   and a mirror. r contains the end-points of the laser, s contains
   the end-points of the mirror. *)
intersect[r_, s_] := Module[
   {lr, dr, nr, ds, ns, \[Lambda]},
   (* Get a unit vector in the direction of the beam *)
   dr = r[[2]] - r[[1]];
   lr = Norm@dr;
   dr /= lr;
   (* Get a normal to that vector *)
   nr = {dr[[2]], -dr[[1]]};

   (* The sign of dot product in here depends on whether that end-point
      of the mirror is to the left or to the right of the array. Return
      infinity if both ends of s are on the same side of the beam. *)
   If[Apply[Times, (s - {r[[1]], r[[1]]}).nr] > 0,
    Return[\[Infinity]]];

   (* Get a unit vector along the mirror. *)
   ds = s[[2]] - s[[1]];
   ds /= Norm@ds;
   (* And a normal to that. *)
   ns = {ds[[2]], -ds[[1]]};
   (* We can write the beam as p + λ*dr and mirror as q + μ*ds,
      where λ and μ are real parameters. If we set those equal and
      solve for λ we get the following equation. Since dr is a unit
      vector, λ is also the distance to the intersection. *)
   \[Lambda] = ns.(r[[1]] - s[[1]])/nr.ds;
   (* Make sure that the intersection is before the end of the beam.
      This check could actually be slightly simpler (see Ruby version). *)
   If[\[Lambda] != 0 && lr/\[Lambda] < 1, Infinity, \[Lambda]]
   ];

(* This function actually does the simulation and generates the plot. *)
plotLaser[L_, t_, distance_, M_] := Module[
   {coords, plotRange, points, e, lastSegment, dLeft, \[Lambda], m, p,
     d, md, mn, segments, frames, durations},

   (* This will contain all the intersections along the way, as well
      as the starting point. *)
   points = {L};
   (* The tentative end point. *)
   e = L + distance {Cos@t, Sin@t};
   (* This will always be the currently last segment for which we need
      to check for intersections. *)
   lastSegment = {L, e};
   (* Keep track of the remaining beam length. *)
   dLeft = distance;

   While[True,
    (* Use the above function to find intersections with all mirrors
       and pick the first one (we add a small tolerance to avoid
       intersections with the most recent mirror). *)
    {\[Lambda], m} =
     DeleteCases[
       SortBy[{intersect[lastSegment, #], #} & /@ M, #[[1]] &],
       i_ /; i[[1]] < 1*^-10][[1]];
    (* If no intersection was found, we're done. *)
    If[\[Lambda] == \[Infinity], Break[]];
    (* Reduce remaining beam length. *)
    dLeft -= \[Lambda];
    (* The following lines reflect the beam at the mirror and add
       the intersection to our list of points. We also update the
       end-point and the last segment. *)
    p = lastSegment[[1]];
    d = -Subtract @@ lastSegment;
    d /= Norm@d;
    md = -Subtract @@ m;
    md /= Norm@md;
    mn = {md[[2]], -md[[1]]};
    AppendTo[points, p + \[Lambda]*d];
    d = -d + 2*(d - d.mn*mn);
    e = Last@points + dLeft*d;
    lastSegment = {Last@points, e};
    ];
   (* Get a list of all points in the set up so we can determine
      the plot range. *)
   coords = Transpose@Join[Flatten[M, 1], {L, e}];
   (* Turn the list of points into a list of segments. *)
   segments = Partition[points, 2, 1];
   (* For each prefix of that list, generate a frame. *)
   frames = Map[
     Graphics[
       {Line /@ M,
        Red,
        Point@L,
        Line /@ segments[[1 ;; #]]},
       PlotRange -> {
         {Min@coords[[1]] - 1, Max@coords[[1]] + 1},
         {Min@coords[[2]] - 1, Max@coords[[2]] + 1}
         }
       ] &,
     Range@Length@segments];
   (* Generate the initial frame, without any segments. *)
   PrependTo[frames,
    Graphics[
     {Line /@ M,
      Red,
      Point@L},
     PlotRange -> {
       {Min@coords[[1]] - 1, Max@coords[[1]] + 1},
       {Min@coords[[2]] - 1, Max@coords[[2]] + 1}
       }
     ]
    ];
   (* Generate the final frame including lastSegment. *)
   AppendTo[frames,
    Graphics[
     {Line /@ M,
      Red,
      Point@L,
      Line /@ segments,
      Line[lastSegment],
      Point@e},
     PlotRange -> {
       {Min@coords[[1]] - 1, Max@coords[[1]] + 1},
       {Min@coords[[2]] - 1, Max@coords[[2]] + 1}
       }
     ]];

   (*Uncomment to only view the final state *)
   (*Last@frames*)

   (* Export the frames as a GIF. *)
   durations = ConstantArray[0.1, Length@frames];
   durations[[-1]] = 1;
   Export["hardcoded/path/to/laser.gif", frames,
    "GIF", {"DisplayDurations" -> durations, ImageSize -> 600}];

   (* Generate a Mathematica animation form the frame. *)
   ListAnimate@frames
   ];

You can call it like

plotLaser[{1, 1}, 7.50492, 95, {
  {{4.8, 5.3}, {6.2, 4.3}}, {{1.5, 4.8}, {3.5, 6}}, {{6.3, 1.8}, {7.1, 3}},
  {{5, 1}, {4, 3}}, {{7, 6}, {5, 6.1}}, {{8.5, 2.965}, {8.4, 2}},
  {{8.5, 3.035}, {8.6, 4}}, {{8.4, 2}, {10.5, 3}}, {{8.6, 4}, {10.5, 3}}
}]

That will give you an animation in Mathematica and also export a GIF (the one at the top for this input). I've slightly extended the OPs example for this, to make it a bit more interesting.

More examples

A tube with slightly diverging walls but a closed end:

plotLaser[{0, 0}, 1.51, 200, {
  {{0, 1}, {20, 1.1}},
  {{0, -1}, {20, -1.1}},
  {{20, 1.1}, {20, -1.1}}
}]

An equilateral triangle and an initial direction that is almost parallel to one of the sides.

plotLaser[{-1, 0}, Pi/3 + .01, 200, {
  {{-2.5, 5 Sqrt[3]/6}, {2.5, 5 Sqrt[3]/6}},
  {{0, -5 Sqrt[3]/3}, {-2.5, 5 Sqrt[3]/6}},
  {{0, -5 Sqrt[3]/3}, {2.5, 5 Sqrt[3]/6}}
}]

One more:

plotLaser[
 {0, 10}, -Pi/2, 145,
 {
   {{-1, 1}, {1, -1}}, {{4.5, -1}, {7.5, Sqrt[3] - 1}},
   {{11, 10}, {13, 10}}, {{16.5, Sqrt[3] - 1}, {19.5, -1}},
   {{23, -1}, {25, 1}}, {{23, 6}, {25, 4}}, {{18, 6}, {20, 4}}, {{18, 9}, {20, 11}},
   {{31, 9}, {31.01, 11}}, {{24.5, 10.01}, {25.52, 11.01}}, {{31, 4}, {31, 6}}, {{25, 4.6}, {26, 5.6}}, {{24.5, 0.5}, {25.5, -0.5}},
   {{31, -1}, {33, 1}}, {{31, 9}, {33, 11}}, {{38, 10.5}, {38.45, 9}}
 }
]

Ruby, golfed answer

x,y,t,p,*m=gets.split.map &:to_f
u=q=Math.cos t
v=r=Math.sin t
loop{k=i=p
u=x+q*p
v=y+r*p
m.each_slice(4){|a,b,c,d|((a-u)*r-(b-v)*q)*((c-u)*r-(d-v)*q)>0?next: g=c-a
h=d-b
l=(h*(x-a)-g*(y-b))/(r*g-q*h)
f=(g*g+h*h)**0.5
t,k,i=g/f,h/f,l if l.abs>1e-9&&l/i<1}
i==p ?abort([u,v]*' '): p-=i
x+=q*i
y+=r*i
n=q*k-r*t
q-=2*n*k
r+=2*n*t}

This is basically a direct translation of the Mathematica solution to Ruby, plus some golfing and making sure it meets the I/O criteria.


JavaScript (ES7), 57 bytes

Saved 1 byte thanks to @WallyWest

s=>n=>[n,n-1].map(x=>.707**x*{A:841,B:1e3,C:917}[s]+.2|0)


Japt, 304 264 162 points

Saved 40 points thanks to @ConorO'Brien

;î"历锋㫿鮹㿬崴ꨜꎋΞ"csG

Test it online!

In order to save as many points as possible, the entire string is condensed into 9 Unicode chars by interpreting each run of 3 letters as a base-36 number, then converting to a code point. The program itself takes this compressed string (which costs 110 points, including the quotes) and maps each charcode by converting it to a string in base-36 (G after the ; at the beginning). î takes the first {input} chars of this, which is implicitly printed.


Would this number make a good 2048 combo?

Python: 457 422 characters
z=range
def c(n):
 for x in z(1,12):
  if int(n)==2**x:return 1
 return 0
def p(s):
 if s=='':return[]
 for i in z(len(s),0,-1):
  if c(s[:i])>0and p(s[i:])!=1:return [int(s[:i])]+p(s[i:])
 return 1
def r(a):
 if len(a)==1:return 1
 i,t=1,a[:1]
 while i<len(a):
  if a[i]==t[-1]:t[-1]*=2
  else:t+=[a[i]]
  i+=1
 if len(t)==len(a):return 0
 return r(t)
def f(s):
 if p(s)==1or r(p(s))==0:print('bad')
 else:print('good')

The function f(s) gets a string of digits and outputs 'good' or 'bad' accordingly.
I chose not to use 0 as spaces because spaces are meaningless in the game and they create ambiguity when parsing strings (is 22048 good or bad?). This only uses numbers up to 2048, but that can be changed without adding characters.
At the cost of 10 characters or so I can also print all the steps of combining the numbers.
And I realize that this code isn't golfed enough yet; don't worry, edits are coming.


brainfuck - 617 616 604 bytes
+>>>>,[>++++[<-------->-]<[>>>>],]<<<<[>+<<+<+>>-]<[>+<-]+<+<<[>+>-<<-]>[<+>-]>[,+++++[>+++++<-]>>[<->-]<[>>>>>[>>>>]+[<<<<]<-]>>[<+>-]<<<]>[>>[,<]<<+++++++++<]<<<[-[+>>-<]>[>>[<+<+>>-]<<<<[>+>-<<-]>[<+>-]>[<<[<<<<]>>>>[[<<<<+>>>>-]>>>>]<<<<+>>-]>[>+<-]]<<<[-[+>]+<<<<]>>>>-<<<<<]>>>>>+++++[>----<-]>->[<+>>+<-]<[<<<[<<<<]+[>>>>]<-]>>[<+>-]<[<<<<]>>>++++[<-------->-]>[-[,+++>]+>>>[<<<->>]>]<<<<<[>-]>[>>]>>+[<++++[<++++++++>-]<]>>[+++++++++++++>>>>]<<<<----<+++[<<+<<[<<+<<]+[>>>>]<<<<-]<<<<[-<<<<]>[.,>>]<<<<<[<<<<]<++++++++++<<.<+<<+<<+<<+<<+<[.,>>]<<<<<[<<]>++++++++++<+<<+<<+<..<+<[.,>>]<[<<]<...<<.

This took me the better part of two days. I think it was worth it. There's probably parts that can be golfed more by changing what cell something is stored in or whatever, but right now I'm just happy I got it working.
This program would have to be completely different if the question didn't specify that the input would be sorted. The way this works is by constructing a list of 10 pins around the ones that are input. That's kind of confusing but maybe this will explain it better:
If you input these pins:           [2, 3, 6, 8, 9]
First, the program does this:      [2, 3, 6, 8, 9] + [10]
Then this:                         [2, 3, 6] + [7] + [8, 9, 10]
Then this:                         [2, 3] + [4, 5] + [6, 7, 8, 9, 10]
Finally, this:                     [1] + [2, 3, 4, 5, 6, 7, 8, 9, 10]
To build this:                     [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

While it's doing that, it remembers which of the pins the user put there and which ones it put there. This strategy would be very difficult to use if the input wasn't sorted.
Another thing that the sorting make easier is detection of the number 10. Since brainfuck deals with individual bytes, not "numbers" per se, it could have been a pain in the ass, but the sorted input made it much easier for me to deal with. The reason for that has to do with how I stored data in the program. I take the input one character at time and subtract 32 from the result. If the cell is non-zero after that, I move forward 4 cells. before repeating. This means that I get a non-space byte of input every 4 cells, and I effectively store pins as their number + 16. However, 10 takes two bytes to type, so I had to special case it. If the input wasn't sorted, I'd have to look through the pins, but since it is sorted it will always be the last pin if it appears. I check if the (last byte of input + 1) == (the second last byte of input) and if so, it must be 10. I get rid of the last byte and set the second last one to what my system understands as "10". The characters '1' and '0' don't fit in a single byte, but the number 26 sure does!
Coming up with tricks just to make something work at all is my favourite part of using this language. :)
If you're interested in how this program works in more detail, you can see the program with the comments I used while writing it to make sure I remembered what everything did. Even writing comments in brainfuck is hard, since there's no comment syntax. Instead, every character except those in <[+.,-]> are no-ops. It's easy to introduce bugs by accidentally including . or , in your comments! That's why the grammar is so wonky and semicolons are everywhere.
EDIT: As an example of how easy this is to screw up: I used "non-space" in one of the comments! When I stripped all the non-bf characters from the source, the program I used to do that kept in the -. Luckily it didn't break anything, but now I've removed it to save a byte. :)
EDIT II: It's been a while since I touched this one, haha. In another brainfuck answer on this site, I noticed that I accidentally used a comma in the commented version. Since the input had already been exhausted, it set the current cell to 0 (this is implementation dependant, but in my experience it's the most common behaviour). I fixed the bug, but it got me thinking. The idiomatic way to set a cell to 0 is [-] (roughly while (*p) { *p--; }), which is two bytes longer. Any time all the input has been read, I can use , instead. This saved me 2 bytes in that answer, and 12 in this one!
one flag at the very left; will be important later
+>>>>

all nonspace bytes of input separated by 3 empty cells; pin number `n` stored with value `n` plus 16
,[>++++[<-------->-]<[>>>>],]<<<<

test if last pin is 10
[>+<<+<+>>-]<[>+<-]+<+<<[>+>-<<-]>[<+>-]>

[
    if not: find 10 minus the number it is; put that many placeholder pins (cells with value 1) at the end
    ,+++++[>+++++<-]>>[<->-]<[>>>>>[>>>>]+[<<<<]<-]>>[<+>-]<<<
]>

[
    if so: get rid of '0' byte; convert '1' byte to 26 (10 plus 16)
    >>[,<]<<+++++++++<
]<<<

pointer now sitting on the cell with the second greatest pin that was inputted (ie not a placeholder)

;;;;;;;

[
    check for flag placed at the very beginning of the program; if present: break
    -[+>>-<]>
    [
        find ((pin to our right) minus 1) minus pin to our left
        move all pins left of us 4*(that value) cells and insert placeholder pins
        >>[<+<+>>-]<<<<[>+>-<<-]>[<+>-]>[<<[<<<<]>>>>[[<<<<+>>>>-]>>>>]<<<<+>>-]>[>+<-]
    ]

    find first non placeholder pin to our left
    there has to be one because we haven't hit the flag yet
    <<<[-[+>]+<<<<]>>>>-<<<<<
]>>>>>+

we have now added placeholder pins at the end and in the middle; all that's left is the beginning

subtract 17 from lowest pin and put that many placeholders to the left
++++[>----<-]>->[<+>>+<-]<[<<<[<<<<]+[>>>>]<-]>>[<+>-]

subtract 32 from an empty cell 2 to the left of the lowest pin; will be useful later
<[<<<<]>>>++++[<-------->-]>

placeholder pins have the value 1; real pins have a value somewhere between 17 and 26
normalize it by stepping through and setting every pin with value != 1 to 3 (0's ascii code is 2 higher than period so this will make it easier to print later)
[-[,+++>]+>>>[<<<->>]>]<<<<<[>-]>[>>]>>

start writing 32s across the board; hitting every second cell
that's every pin and the cell 2 to the right of each pin
this is done in such a way that it will only halt if adding 32 to a cell sets it to 0; which is why we subtracted 0 from an empty cell earlier
it will catch us and prevent an infinite loop
+[<++++[<++++++++>-]<]

now write 13 to each pin; this adds up to 46 or 48; which are exactly the ascii values we want
>>[+++++++++++++>>>>]

we happen to have made a 14; turn it into a 10 for a newline
<<<<----

we're so close now; i can taste it
we have a list of 10 pins; each one with the ascii value that needs to be written
we have 32 everywhere because we'll need spaces
we even have a newline

the only problem now is that our list looks like this:
;;;;;;;;;;;;;;;;;;;;;;;;
;;1 2 3 4 5 6 7 8 9 10;;
;;;;;;;;;;;;;;;;;;;;;;;;

and we need to print in this order:
;;;;;;;;;;;;;;;;;;;;;;;;
;;7 8 9 10 4 5 6 2 3 1;;
;;;;;;;;;;;;;;;;;;;;;;;;

it's a pretty simple fix
once we print a pin we obviously don't need to remember it any more
so we simply print the last 4 pins on the list; destroying them on the way
then we print the last 3; which have become the ones we want
then two; then one
<+++[<<+<<[<<+<<]+[>>>>]<<<<-]<<<<[-<<<<]

print pins 7 8 9 10
>[.,>>]

print pins 4 5 6
<<<<<[<<<<]<++++++++++<<.<+<<+<<+<<+<<+<[.,>>]

print pins 3 2
<<<<<[<<]>++++++++++<+<<+<<+<..<+<[.,>>]

print the final pin!! :)
<[<<]<...<<.


Create a basic autocorrecting spell checker

CJam, 90 87 bytes

qelN%Sf%~f{1$:W,,_:_2ewWf{\~e\}\Wf{' t_S-}W,),Wf{1$m<S\+m>}++Sf/26,'af+\ff*:+\&\a+0=}S*

Try it online in the CJam interpreter.


a and m work on strings too

Though it isn't explicitly stated in the spec, a (add) and m (multiply), at least in the official Ruby interpreter, also work on strings.

Say you had two cells with strings in them at the end of the tape, and wanted to concatenate and print them. You could do it with c:

c{{P

However, as long as you don't want to preserve the original value of your first cell, you could append the second string directly onto the first with a and avoid having to go to the end of the tape:

aP

Now let's say you want to print 20 spaces. The naive way to do it would be to simply hardcode them:

`                    `P

As long as the cell to the right is free, though, you can save 11 instructions by using m:

` `{`20`n}mP

Note, however, that due to the way Ruby works, you cannot do this with the order of the cells reversed (i.e. multiply a number by a string); that causes an error.


Python, 172 168 743 characters - 1796 bonus = -1053

Updated to take the stem-changing challenge.

p,v=raw_input().split()
y="aee";z=y+'n'
x=["ooo",y+'s',y,y,y,"aeimos","ae\x00is",z,z]["YoTuElEaUdNsVsEsUs".index(p[0]+p[-1])/2]
s=v[:-2]
X=v='eJw1UuHS5CAIe1aqrNsZhR6w/tj5Hv4Sv7uODRYDxEzlylKTplHS3xrS/3yIm4kntCTVSipkazaZ\n+AA32h3tY1ut+VL7NreXxsEEsgSheGynlJv/GNVvsPs9CIl2hoCSV+gYfuH7rdAyIQdr3+x92yCg\n2g7WEp4vMfTKgogyHabbL4z1l1p/1PLBCF4o9AjtmJBc6wpOTJykM+O0Ib2Y+FyCAuv5wcwCd+Ks\n4+XCdSwhqMIf/eJOFPMjV/rc0jw6IEvm8vjKdBuy/JryMPmEXwIiDInhtK01n1iDPrGu6/A5uy4/\nkBVd89R1OjvHCXbSnoDyaB23nhseElHosf45rzYC1zOevyDojQ548fjGCGg8M5aD8EAmB9GqgFHk\nBzRwDwJ6EcgK5aSDZ2/4TSAjKOMXd3gPh6sTq/+GApG0wkSYdzSBz/AXclUQ+g=='.decode('base64').decode('zip')
if s in X:
 j=X.index(s)<326
 s=(s.replace('oe'[j],'ui'[j]+'e'),s)[p[0]in'NV']
print s+x["aei".index(v[-2])]+x[3:]

Usage:

$ echo "Ellas querer" | python conj_golf2.py
quieren

Test on non-stem-changing inputs:

Yo ensenar -> enseno
Yo escribir -> escribo
Tu ensenar -> ensenas
Tu escribir -> escribes
El ensenar -> ensena
El escribir -> escribe
Ella ensenar -> ensena
Ella escribir -> escribe
Usted ensenar -> ensena
Usted escribir -> escribe
Nosotros ensenar -> ensenamos
Nosotros escribir -> escribimos
Vosotros ensenar -> ensenais
Vosotros escribir -> escribis
Ellos ensenar -> ensenan
Ellos escribir -> escriben
Ellas ensenar -> ensenan
Ellas escribir -> escriben
Ustedes ensenar -> ensenan
Ustedes escribir -> escriben

Stem-changing input examples:

It does both e->ie changes and o->ue changes, properly avoiding the nostros + vostros cases:

$ echo "Yo abstenir"|python conj_golf2.py
abstieno
$ echo "Nostros abstenir"|python conj_golf2.py
abstenimos
$ echo "Tu almorzar"|python conj_golf2.py
almuerzas
$ echo "Vostros almorzar"|python conj_golf2.py
almorzais

Here is how the bonus was determined and the data string generated, from which you can deduce the verbs on which it works:

e="absten.acert.adher.adquer.advert.apret.asent.atraves.calent.cerr."+\
  "circunven.comenz.confer.confes.consent.conten.contraven.conven.convert."+\
  "difer.diger.discern.disent.freg.gobern.hed.hel.her.herv.infer.inger."+\
  "invern.invert.malher.manifest.ment.neg.nev.obten.ofend.pens.perd."+\
  "quer.recomend.reg.seg.sembr.sent.serr.sosegsosten.soterr.subarrend."+\
  "suger.tembl.tend.ten.tent.transfer.tropez.ven.vert"

u="absolv.acord.acost.almorz.along.amobl.apost.aprob.asol.avergonz."+\
  "coc.col.colg.cont.cost.degoll.demol.demostr.desaprob.descolg.descontr."+\
  "desos.destorc.devolv.disolv.dol.dorm.encontr.engros.envolv.forz.holg."+\
  "holl.llov.mol.mor.mostr.mov.ol.pobl.prob.record.reforz.remord.remov.renov."+\
  "repobl.resolv.resoll.reson.retorc.revolc.revolv."+\
  "rod.rog.sol.sold.sol.solt.son.torc.tost.tron.vol.volc.volv"

words = e.split(".") + u.split(".")
bonus = 0
for word in words:
    bonus += (len(word)+2)*2
print "Bonus: %d from %d stem-changing verbs" % (bonus, len(words))

s=(e+"|"+u).replace(".","")
zipped = s.encode('zip')
b64 = zipped.encode('base64')
print "The separator is at index %d" % s.index("|")
print "Uncompressed: %d chars, %d repr" % (len(s), len(`s`))
print "Compressed: %d chars, %d repr" % (len(zipped), len(`zipped`))
print "Comp+B64: %d chars, %d repr" % (len(b64), len(`b64`))

print "v="+`b64`

Which gives:

$ python conj_help.py
Bonus: 1796 from 127 stem-changing verbs
The separator is at index 326
Uncompressed: 645 chars, 647 repr
Compressed: 331 chars, 1015 repr
Comp+B64: 450 chars, 458 repr
v='eJw1UuHS5CAIe1aqrNsZhR6w/tj5Hv4Sv7uODRYDxEzlylKTplHS3xrS/3yIm4kntCTVSipkazaZ\n+AA32h3tY1ut+VL7NreXxsEEsgSheGynlJv/GNVvsPs9CIl2hoCSV+gYfuH7rdAyIQdr3+x92yCg\n2g7WEp4vMfTKgogyHabbL4z1l1p/1PLBCF4o9AjtmJBc6wpOTJykM+O0Ib2Y+FyCAuv5wcwCd+Ks\n4+XCdSwhqMIf/eJOFPMjV/rc0jw6IEvm8vjKdBuy/JryMPmEXwIiDInhtK01n1iDPrGu6/A5uy4/\nkBVd89R1OjvHCXbSnoDyaB23nhseElHosf45rzYC1zOevyDojQ548fjGCGg8M5aD8EAmB9GqgFHk\nBzRwDwJ6EcgK5aSDZ2/4TSAjKOMXd3gPh6sTq/+GApG0wkSYdzSBz/AXclUQ+g==\n'


Javascript, 92 88 86 characters
t=prompt()
for(b=c=1;c<t[l='length'];c=a+b)a=b,b=c
alert(c==t[l]&b==t.match(/\d/g)[l])

I hope you don't mind I've hard-coded the the first three Fibonacci numbers.


Verbose, 1362 bytes
GET A ROMAN NUMERAL TYPED IN BY THE CURRENT PERSON USING THIS PROGRAM AND PUT IT ONTO THE TOP OF THE PROGRAM STACK
PUT THE NUMBER MMMM ONTO THE TOP OF THE PROGRAM STACK
MOVE THE FIRST ELEMENT OF THE PROGRAM STACK TO THE SECOND ELEMENT'S PLACE AND THE SECOND ELEMENT OF THE STACK TO THE FIRST ELEMENT'S PLACE
DIVIDE THE FIRST ELEMENT OF THE PROGRAM STACK BY THE SECOND ELEMENT OF THE PROGRAM STACK AND PUT THE RESULT ONTO THE TOP OF THE PROGRAM STACK
PUT THE NUMBER V ONTO THE TOP OF THE PROGRAM STACK
GET THE FIRST ELEMENT OF THE PROGRAM STACK AND THE SECOND ELEMENT OF THE PROGRAM STACK AND IF THE SECOND ELEMENT OF THE PROGRAM STACK IS NOT ZERO JUMP TO THE INSTRUCTION THAT IS THE CURRENT INSTRUCTION NUMBER AND THE FIRST ELEMENT ADDED TOGETHER'S RESULT
PUT THE NUMBER I ONTO THE TOP OF THE PROGRAM STACK
GET THE TOP ELEMENT OF THE STACK AND OUTPUT IT FOR THE CURRENT PERSON USING THIS PROGRAM TO SEE
PUT THE NUMBER III ONTO THE TOP OF THE PROGRAM STACK
GET THE FIRST ELEMENT OF THE PROGRAM STACK AND THE SECOND ELEMENT OF THE PROGRAM STACK AND IF THE SECOND ELEMENT OF THE PROGRAM STACK IS NOT ZERO JUMP TO THE INSTRUCTION THAT IS THE CURRENT INSTRUCTION NUMBER AND THE FIRST ELEMENT ADDED TOGETHER'S RESULT
PUT THE NUMBER NULLA ONTO THE TOP OF THE PROGRAM STACK
GET THE TOP ELEMENT OF THE STACK AND OUTPUT IT FOR THE CURRENT PERSON USING THIS PROGRAM TO SEE

Outputs I for valid roman numerals in the range I-MMMCMXCIX and NULLA (0) or informs user input is not a valid roman numeral otherwise.


JavaScript (ES6), 123 121 120 bytes

f=(s,v)=>(p=n=>--n-1?s%n&&p(n):1)(s)||[...s].map((_,i)=>!(n=i&&(a=f(s.slice(0,i)))&&(b=f(s.slice(i)))&&a+b)|n>v?0:v=n)|v

Saved a byte thanks to @Neil!

Explanation

Takes a single string as input. Due to the prime checking method (recursive trial division), the greatest number that can be safely checked is 13840. Some numbers above this will fail due to the maximum call stack size being exceeded. It does, however, finish instantly for every case it can handle.

f=(s,v)=>
  (p=n=>--n-1?s%n&&p(n):1)(s) // if s is prime, return 1
  ||[...s].map((_,i)=>        // else for each index in s, split s into 2
    !(n=i&&                   // v = return value (initialised to undefined)
      (a=f(s.slice(0,i)))&&
      (b=f(s.slice(i)))&&
      a+b
    )|n>v?0:v=n               // if i, a, b and n are all > 0 and !(n > v), v = n
  )|v                         // cast v to an integer and return it

// Test
var testCases = [ "252", "235", "92", "3149", "24747" ];
document.write("<pre>" + testCases.map(c => c + ": " + f(c)).join("\n"));


Perl 6, 40 37 bytes

{"In Soviet Russia, {.words[1,0]} you!"}

{~[R,] «you! $_ Russia, Soviet In»}

It works because the « » "word list quote" recursively splits everything on whitespace.

Some other answers require the input words to be passed as two separate arguments. I think that's cheating, but for the record, it would make this solution 34 bytes long (and really boring):

{"In Soviet Russia, $^b $^a you!"}


Decode a UTF-8 string to character byte counts

Python 3, 135 bytes

def f(b):
	B=b.decode(errors="ignore")[:1].encode();l=len(B)
	if B and b[:l]!=B:return"�"+f(b[1:])
	return str(l)+f(b[l:])if b else''

Try it online!

Explanation:

def f(b):
	B=b.decode(errors="ignore")[:1].encode();l=len(B)
	 # B is the UTF-8-encoded version of the first Unicode character in the given bytes
	 # (Or the Nth, if the first N-1 bytes were invalid Unicode bytes)
	if B and b[:l]!=B:return"�"+f(b[1:])
	 # If the two encoded byte-strings don't match,
	 # then the first byte in b is invalid,
	 # so append "�" to the returned string, and recurse
	return str(l)+f(b[l:])if b else''
	 # If the byte-string is not empty,
	 #  append the length of the first character and recurse.
	 # Else (the input is empty) return the empty string (recursion base case)


JavaScript (Node.js), 39 bytes
I/O: Unicode codepoints as integers.
n=>Buffer("99944,777I")[n/543%62&15]<<9

Try it online!
How?
Step 1
We first look for some divisor \$d\$ such that the following element sets \$S_k\$ are disjoint:
$$S_k=\left\{\left\lfloor\dfrac{n}{d}\right\rfloor,\:C_{min}(k)\le n\le C_{max}(k)\right\}$$
where \$C_{min}(k)\$ and \$C_{max}(k)\$ are the codepoint bounds of the \$k\$-th element.
Because the Unicode range of Water (U+6C34 to U+706A) is immediately followed by the Unicode range of Fire (U+706B to U+7229), there are not many possible options for \$d\$: it must be a proper divisor of \$28779\$ (0x706B), i.e. \$d\in\{1, 3, 53, 159, 181, 543, 9593\}\$. The best value in there that actually works is \$d=543\$.
Step 2
We then look for some modulo chain that takes \$n\$ as input and turns it into an index corresponding to the counterpart element, using \$n/543\$. Instead of rounding the result towards zero, we force the last operation to a bitwise AND rather than a modulo.
A quick brute-force search leads to:
$$f(n)=((n/543)\bmod 62)\operatorname{and}15$$
Step 3
Finally, we look for some multiplier \$m\$ such that there exists some \$q_k\$ for each \$k\$ that satisfies:
$$C_{min}(k)\le q_k\times m\le C_{max}(k)$$
One possible golf-friendly value is \$m=512\$, leading to the following table:
 element | hexa range      | q  | q*512 | as hexa
---------+-----------------+----+-------+---------
  Soil   | 0x571F - 0x58EA | 44 | 22528 | 0x5800
  Wood   | 0x6728 - 0x6B1F | 52 | 26624 | 0x6800
  Water  | 0x6C34 - 0x706A | 55 | 28160 | 0x6E00
  Fire   | 0x706B - 0x7229 | 57 | 29184 | 0x7200
  Metal  | 0x91D1 - 0x9484 | 73 | 37376 | 0x9200

The values of \$q\$ are encoded as the ASCII codes of ,479I.


JavaScript (ES6), 266 308 317 334 341
A function returning a string.
Edit Found an arithmetic solution for function M (at last!)
F=(n,x=[],M=(a,b,t=-a-b)=>(a-b)%3?a<3&b<3?3+t:a>5&b>5?21+t:12+t:9+t+a%3*3)=>
[for(a of z='012345678')for(b of z)for(c of z)for(d of z)
a-b&&c-a&&c-b&&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c)&&(
f=M(c,e=M(b,d)),g=M(a,e),g<f?[f,g]=[g,f]:0,r=a+b+c+d+e,x.push(r+f+g,r+g+f))]
&&x[n]

Very naive , it can be shortened in many ways. It simply enumerates all the possible legal values and returns what find at place n.
The M function returns the position in between two cells, that is the mandatory move to block an opposite player.
More readable
F=(n,x=[],
  M=(a,b,t=-a-b)=>(a-b)%3?
     a<3&b<3?
       3+t // first row
       :a>5&b>5?
          21+t // last row
          :12+t // middle row and diags
     :9+t+a%3*3 // columns
  )=>
  [for(a of z='012345678') // enumerate the first 4 moves
     for(b of z)
       for(c of z)
         for(d of z)
           a-b&&c-a&&c-b // avoid duplicates
           &&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c) // and check if d must block a-c or it's free
           &&(
             e=M(b,d), // forced to block b-d
             f=M(c,e),g=M(a,e),g<f?[f,g]=[g,f]:0, // f and g could be in the wrong order
             r=a+b+c+d+e, // start building a return string
             x.push(r+f+g,r+g+f) // store all values in x
  )]&&x[n] // return value at requested position