Help, I'm trapped in a Sierpinski triangle!

Python 2, 208 205 200 bytes

A=lambda n:n and A(~-n/3)+[-n%3]or[]
f=lambda x,y:f(A(x),A(y))if x<[]else["SSNEW"[m::3]for m in
y[len(x):]]if x==y[:len(x)]else min([["NNSWE"[m::3]]+f(x[:~x[::-1].index(m)],y)for
m in set(x)],key=len)

A function, f, taking a pair of node numbers, and returning the shortest path as a list of strings.

Explanation

We start by employing a different addressing scheme for the triangles;
the address of each triangle is a string, defined as follows:

The address of the central triangle is the empty string.
The addresses of the north, south-west, and south-east children of each triangle are formed appending 0, 1, and 2, respectively, to the address of the triangle.

Essentially, the address of each triangle encodes the (shortest) path from the central triangle to it.
The first thing our program does is translating the input triangle numbers to the corresponding addresses.

Click the image for a larger version.

The possible moves at each triangle are easily determined from the address:

To move to the north, south-west, and south-east children, we simply append 0, 1, and 2, respectively, to the address.
To move to the south, north-east, and north-west ancestors, we find the last (rightmost) occurrence of 0, 1, and 2, respectively, and trim the address to the left of it.
If there is no 0, 1, or 2 in the address, then the corresponding ancestor doesn't exist.
For example, to move to the north-west ancestor of 112 (i.e., its parent), we find the last occurrence of 2 in 112, which is the last character, and trim the address to the left of it, giving us 11;
to move to the north-east ancestor, we find the last occurrence of 1 in 112, which is the second character, and trim the address to the left of it, giving us 1;
however, 112 has no south ancestor, since there is no 0 in its address.

Note a few things about a pair of addresses, x and y:

If x is an initial substring of y, then y is a descendant of x, and therefore the shortest path from x to y simply follows the corresponding child of each triangle between x and y;
in other words, we can replace each 0, 1, and 2 in y[len(x):] with N, SW, and SE, respectively.
Otherwise, let i be the index of the first mismatch between x and y.
There is no path from x to y that doesn't pass through x[:i] (which is the same as y[:i]), i.e., the first common ancestor of x and y.
Hence, any path from x to y must arrive at x[:i], or one of its ancestors, let's call this triangle z, and then continue to y.
To arrive from x to z, we follow the ancestors as described above.
The shortest path from z to y is given by the previous bullet point.

If x is an initial substring of y, then the shortest path from x to y is easily given by the first bullet point above.
Otherwise, we let j be the smallest of the indices of the last occurrences of 0, 1, and 2 in x.
If j is greater than, or equal to, the index of the first mismatch between x and y, i, we simply add the corresponding move (S, NE, or NW, respectively) to the path, trim x to the left of j, and continue.
Things get trickier if j is less than i, since then we might get to y fastest by ascending to the common ancestor x[:j] directly and descending all the way to y, or we might be able to get to a different common ancestor of x and y that's closer to y by ascending to a different ancestor of x to the right of i, and get from there to y faster.
For example, to get from 1222 to 1, the shortest path is to first ascend to the central triangle (whose address is the empty string), and then descend to 1, i.e., the first move takes us to the left of the point of mismatch.
however, to get from 1222 to 12, the shortest path is to ascend to 122, and then to 12, i.e., the first move keeps us to the right of the point of mismatch.

So, how do we find the shortest path?
The "official" program uses a brute-force-ish approach, trying all possible moves to any of the ancestors whenever x is not an initial substring of y.
It's not as bad as it sounds!
It solves all the test cases, combined, within a second or two.

But then, again, we can do much better:
If there is more than one directly reachable ancestor to the left of the point of mismatch, we only need to test the rightmost one,
and if there is more than one directly reachable ancestor to the right of the point of mismatch, we only need to test the leftmost one.
This yields a linear time algorithm, w.r.t. the length of x (i.e., the depth of the source triangle, or a time proportional to the logarithm of the source triangle number), which zooms through even much larger test cases.
The following program implements this algorithm, at least in essence—due to golfing, its complexity is, in fact, worse than linear, but it's still very fast.

Python 2, 271 266 261 bytes

def f(x,y):
 exec"g=f;f=[]\nwhile y:f=[-y%3]+f;y=~-y/3\ny=x;"*2;G=["SSNEW"[n::3]for
n in g];P=G+f;p=[];s=0
 while f[s:]:
    i=len(f)+~max(map(f[::-1].index,f[s:]));m=["NNSWE"[f[i]::3]]
    if f[:i]==g[:i]:P=min(p+m+G[i:],P,key=len);s=i+1
    else:p+=m;f=f[:i]
 return P

Note that, unlike the shorter version, this version is written specifically not to use recursion in the conversion of the input values to their corresponding addresses, so that it can handle very large values without overflowing the stack.

Results

The following snippet can be used to run the tests, for either version, and generate the results:

def test(x, y, length):
    path = f(x, y)
    print "%10d %10d  =>  %2d: %s" % (x, y, len(path), " ".join(path))
    assert len(path) == length

#         x           y        Length
test(          0,          40,    4   )
test(         66,          67,    5   )
test(         30,           2,    2   )
test(         93,           2,    2   )
test(        120,          61,    8   )
test( 1493682877,           0,    4   )
test(          0,   368460408,   18   )
test( 1371432130,     1242824,   17   )
test(     520174,  1675046339,   23   )
test(  312602548,   940907702,   19   )
test( 1238153746,  1371016873,   22   )
test(  547211529,  1386725128,   23   )
test( 1162261466,  1743392199,   38   )

Golfed Version

         0         40  =>   4: N N N N
        66         67  =>   5: S SW N N N
        30          2  =>   2: NE SW
        93          2  =>   2: NE SW
       120         61  =>   8: NW NW NW NW N SE SW N
1493682877          0  =>   4: S S NW NW
         0  368460408  =>  18: SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE
1371432130    1242824  =>  17: NW NW NE NW N SE SW SW SW SE SE SW N N N N SW
    520174 1675046339  =>  23: NE NE NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW
 312602548  940907702  =>  19: NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW
1238153746 1371016873  =>  22: NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N
 547211529 1386725128  =>  23: S S S S NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N
1162261466 1743392199  =>  38: NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE

Efficient Version

         0         40  =>   4: N N N N
        66         67  =>   5: S SW N N N
        30          2  =>   2: NW NW
        93          2  =>   2: NE SW
       120         61  =>   8: NW NW NW NW N SE SW N
1493682877          0  =>   4: NE S NW NW
         0  368460408  =>  18: SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE
1371432130    1242824  =>  17: NW NW NE NW N SE SW SW SW SE SE SW N N N N SW
    520174 1675046339  =>  23: NE NW NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW
 312602548  940907702  =>  19: NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW
1238153746 1371016873  =>  22: NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N
 547211529 1386725128  =>  23: S S S S NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N
1162261466 1743392199  =>  38: NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE


Python 2, 196 bytes

x=Q=input()
l=len(x)
k=(l+1)/2
q=l+k
x=[[' ']*(q+1)+list(y)for y in x]
for i in range(k):x[i+l/2][i]='\\'
for j in range(l):x[j][q-j-1]='/'
print'\n'.join([' '*q+'_'*(2+len(Q[0]))]+map(''.join,x))

Try it online!

-2 bytes thanks to Step Hen

-13 bytes thanks to Jonathan Allan


Find a multiple of a given number whose decimal representation looks like binary

Python 2, efficient solution, 99

n=input()
d={n:0}
k=1
while min(d):[d.setdefault((x+k)%n,d[x]+k)for x in set(d)];k*=10
print d[0]/n

Thanks Sp3000 for some golfing tips.
I challenge everybody else to post (in their own answers) how long it takes to get the result for input 72 or 99 :) If those are really fast, try something like 79992 next (still <1 sec here).
Explanation:
I thought this wasn't necessary (since the code is fairly readable), but I got a request, so here it goes:
The first idea is that a binary-looking number is a sum of 1 or more different powers of 10. Therefore, we can try to add various powers of 10 in different ways until we get remainder 0.
If we do that naively, it's the same as generating all binary-looking numbers and testing them. But a lot of remainders will be the same. A better way is to record only the smallest number that gave a certain remainder, and successively add greater powers of 10 to numbers we recorded. That's what the program does.
d is a dictionary/map where keys are remainders and values are binary-looking numbers with that remainder. The initial n:0 is a special case: it's supposed to be 0:0 so we can start adding powers to it, but the algorithm stops when finding key 0, so I used n instead, which is guaranteed to have the same effect and not interfere with the other values.
Then we start adding powers of 10 (stored in k) to all existing numbers and recording the remainders. We add k to the remainder: (x+k)%n and to the number: d[x]+k, and record it only if it's a new remainder: d.setdefault(…), then go to the next power: k*=10 and repeat until we get key 0: while min(d)
At the end, d[0] gives the binary-looking number that has remainder 0 mod n, so we divide it by n to get the solution.
Note: the program can be made more efficient by avoiding large numbers (recording exponents rather than powers of 10, and calculating remainders of powers from previous values), but it's code golf, so...
In fact, here, I wrote a faster version:
n=input()
d={n:0}
k=1
b=0
while 0not in d:
 for x in list(d):d.setdefault((x+k)%n,b)
 k=(k*10)%n;b+=1
x=10**d[0]
while x%n:x+=10**d[n-x%n]
print x/n


MATLAB - 109 Bytes
Try it online
function n=E(s)
i=2;k=1;n=0;while i<numel(s)
k=mod(k,4)+1;n=n+s(i)*((k==1)-(k==3)/2);i=i+s(i)+1+(k<2);end

ungolfed:
function n=E(s)             % function def, input 2 and output n
i=2;                        % sequence index
k=1;                        % 1=sub,2=equivalent,3=super,4=part
n=0;                        % initialized output
while i<numel(s)            % Loop through sequence
k=mod(k,4)+1;               % if k==4, then a new set has started, so back to 1.
n=n+s(i)*((k==1)-(k==3)/2); % s(i) represents n,m,p,q
                            % If k==1, then s(i)=q, so add s(i) to n.
                            % If k==3, s(i)=m, so subtract s(i)/2 from n.
i=i+s(i)+1+(k<2);           % Advance index by (n,m,p,q) and 1 if k==1 (aka k<2) to skip set number definition.
end                         % end

Explanation:
This may be a naive approach, but from what I see, the only way to have a perimter intersection is when you have a set as a part of another.
For super/subsets, there will be no perimeter intersections, since they will be concentric.
For sets that match exactly, there will only be one shape that represents two sets, so there are no perimeter crossings between them.
Therefore, the only time you can have an overlap is for parts. From there it is simple: every crossing includes two points, since by the nature of overlapping rectangles, there will be two and only two intersections of the perimeters. And since the sets that contain parts of another must reference each other (i.e. if set 1 and 2 overlap, set 1 will have 2 in its part input, and 2 will have 1), there will be 2*(number of sets that are part of another). However, sets that are exactly equal only produce one shape, so any crossings between this shape and another must be reduced according to the number of sets that are equivalent. Thus, the sum of the number of elements that fall into the "parts" category across all sets equals the number intersections.
Mathematically,
For \$k\$  sets
\$ n_{crossings} = \displaystyle \sum_{i=1}^k(q_i - m_i/2) \$


Prolog (SWI), 91 80 bytes

0-indexed.

X*L:-atom_length(X,L),
     between(0,L,Y),
     numlist(0,Y,B),
     atomic_list_concat(B,X)
     ;L=0.

Newlines added for readability.

Try it online!


APL (Dyalog Extended), 47 46 48 bytes

{x←0⋄⍵{x≡|x⊢←⍺-⍨⊥(1@1)∘⌽∘⍉⍣4⊢0×⍵:x⋄⍺∇⍵⍪0}⊤⍵+~×⍵}

Try it online!
A dfn which takes a vector as its right argument.
Outputs a list of 0's if the input is already a binary-box.
+2 bytes after a fix.(Thanks, Arnauld)
Explanation
{x←0⋄⍵{x≡|x⊢←⍺-⍨⊥(1@1)∘⌽∘⍉⍣4⊢0×⍵:x⋄⍺∇⍵⍪0}⊤⍵+~×⍵}
 x←0                                             set var x to 0(required for extended)
      {x≡|x⊢←⍺-⍨⊥(1@1)∘⌽∘⍉⍣4⊢0×⍵:x⋄⍺∇⍵⍪0}        call the following recursive function with
                                          ⍵+~×⍵  add !(signum(input)) to itself
                                                 (special casing for [0])
                                         ⊤       converted to binary matrix
     ⍵                                           and the input list as right arg
                                :                If:
                             0×⍵                 the matrix converted to zeroes
                 (1@1)∘⌽∘⍉⍣4⊢                    with 1s added on each side
                ⊥                                convert from binary
             ⍺-⍨                                 subtract from the input
          x⊢←                                    assign to x
       x≡|                                       if x matches its absolute value
                                 x               then return x
                                  ⋄⍺∇⍵⍪0         otherwise add a row of zeroes, and try again


CS-Script - 306 bytes

var c=new string(' ',342).ToCharArray();var r=new Random();int e=18,i,j,w;for(;i<e;i++){c[i*e+e]='\n';w=i<5?i:i<10?i-2:i<16?i-6:2;for(j=1;j++<w*2;)c[i*e+8-w+j]='#';}for(i=0;i<10;){j=37+r.Next(288);if(c[j]=='#'&c[j+1]<42&c[j-1]<42&c[j+e]<42&c[j-e]<42)c[j]=i++<5?'J':'O';}c[8]='^';c[27]='|';Console.Write(c);

Once more with formatting and comments:

// create 'char bitmap' filled with spaces
var c=new string(' ',342).ToCharArray();
// Random for placing ornaments
var r=new Random();
int e=18,i,j,w;
// once for each row
for(;i<e;i++)
{
    // add new lines
    c[i*e+e]='\n';
    // determine width of tree for this row
    w=i<5?i:i<10?i-2:i<16?i-6:2;
    for(j=1;j++<w*2;)
        // add leaves
        c[i*e+8-w+j]='#';
}
for(i=0;i<10;)
{
    // select random location
    j=37+r.Next(288);
    if( // check we have a leaf
        c[j]=='#' &
        // check surrounding to be leaf/space/new-line
        c[j+1]<42 & c[j-1]<42 & c[j+e]<42 & c[j-e]<42)
        // add ornament if location is valid
        c[j]=i++<5?'J':'O';
}
// light candle
c[8]='^';
c[27]='|';
// print
Console.Write(c);

It's basically C#, but using CS-Script allows me to skip all the boiler-plate.

Try it here!

Notes:

This currently outputs another line of white spaces below the tree to make sure the that 'checking for existing ornaments below' does not throw an IndexOutOfBoundsException. Other solutions would be:

Checking if it is the last line before checking below (adds a few more character)
Not adding ornaments to the 'stem' of the tree (Same byte count, but seems to me to be against rules)

I'll leave it to the OP if this should be changed.

Lastly, this is my first golf, so any feedback is appreciated. ;)


JavaScript (ES6), 53 bytes

n=>(g=(o,d=N=n+o)=>N%--d?g(o,d):d-1?g(o<0?-o:~o):N)``

Try it online!
Commented
n => (            // n = input
  g = (           // g = recursive function taking:
    o,            //   o = offset
    d =           //   d = current divisor, initialized to N
    N = n + o     //   N = input + offset
  ) =>            //
    N % --d ?     // decrement d; if d is not a divisor of N:
      g(o, d)     //   do recursive calls until it is
    :             // else:
      d - 1 ?     //   if d is not equal to 1 (either N is composite or N = 1):
        g(        //     do a recursive call with the next offset:
          o < 0 ? //       if o is negative:
            -o    //         make it positive (e.g. -1 -> +1)
          :       //       else:
            ~o    //         use -(o + 1) (e.g. +1 -> -2)
        )         //     end of recursive call
      :           //   else (N is prime):
        N         //     stop recursion and return N
)``               // initial call to g with o = [''] (zero-ish)


APL, 44 bytes

{1=≡⍺⍵:⍺+⍵⋄=/∆←|≡¨⍺⍵:⊃∇¨/↓↑⍺⍵⋄</∆:⍺∘∇¨⍵⋄⍵∇⍺}

APL's + distributes over arrays as well, but in a different enough manner that this can't really be used. However, there is a built-in depth function (≡).

Explanation:

1=≡⍺⍵:⍺+⍵: if the depths of ⍺ ⍵ are both zero (and therefore the depth of ⍺ ⍵ is 1), add them.
∆←|≡¨⍺⍵: take the absolute of the depth of both ⍺ and ⍵ and store them in ∆. (≡ gives a negative value if not all elements have the same depth.)
=/∆: if they have the same depth:

↓↑⍺⍵: pad the shortest array with zeroes to match the longer array
⊃∇¨/: distribute the function over both arrays

</∆: if the depth of ⍺ is less than that of ⍵:

⍺∘∇¨⍵: bind ⍺ and then map over ⍵

⍵∇⍺: if nothing else (so ⍵ is deeper than ⍺), swap the arguments and try again.


APL (Dyalog Unicode), 44 34 bytesSBCS

crossed out 44 is still regular 44 ;(

Hats off to @Bubbler, @ngn and @TesselatingHeckler as they managed to shave some bytes off of my solution, more or less independently but coming up with the same simplifications.

{1∊(l↓⍵)⍷⍨a/⍨∨⌿' '≠a←⊖⍵↑⍨l←2÷⍨≢⍵}⍉

Try it online!

Now I'll explain how it works:

{                                   }⍉  ⍝ We define a monadic function that we apply right after transposing (⍉) the input [this means we will be operating on columns instead of rows]
                              2÷⍨≢⍵    ⍝ Start by finding how many  columns the input has (≢),split that in half (2÷⍨)
                            l←          ⍝   and assign that to l (l←) ...
                        ⍵↑⍨            ⍝ Using it right away to take (↑⍨) l columns from the original input ⍵
                       ⊖               ⍝   which we then reverse (⊖) [effectively flipping the columns upside down]
                     a←                 ⍝   and assign to a (a←)
                 ' '≠                   ⍝ We then compare each character in a to ' '
               ∨⌿                       ⍝   and we "interleave" the logical OR (∨) over the columns (⌿) [to find columns where at least one character is different from ' ']
           a/⍨                          ⍝   finally selecting those columns from a (a/⍨)
         ⍷⍨                             ⍝ Now we superimpose that piece of the original character matrix over all possible locations
   (l↓⍵)                               ⍝   of the columns of ⍵ that remain after we drop (↓) the first l columns [i.e. we take the second half of the columns]
 1∊                                    ⍝   and we look for matches by checking if there is a 1 (Truthy) in any position (∊)


Perl 5, 36 bytes

1while s/	/$"x($^I-length($`)%$^I)/e

Try it online!

Tab length is controlled with -i command-line parameter.


Quickly find length of n-th term of the look-and-say sequence

GolfScript, 300 chars

~8-:m;'!5?HZi " A 9 "$??HLTZ^`eik 5Z`e <^ $k H ,Sds ?LT /5@MUav I " i ? "5i G  !#+.4;>@K]_cdhjy{| *HCRJD@:64122/42.,,*860-40-0.+9?B<862//?D<7=@:420-/5:60.-20.+./384/162.-HCRJD@:64122/42.,,*)! !""$&&('{32-}/]1,/~:&;:L;:T;]:S;0m>{&m=}{L,,{.49=\71=+}%:V{,(,{).V=\T?S={(V=+}/}%0+:V}m*,,0\{.V=\L=8-*+}/}if

Here's a slightly shorter entry.  Reads a number m from stdin, writes the length of the m-th term in the look-and-say sequence to stdout.

For example, input 50 produces output 894810, while input 1000 produces (after a few seconds):

21465050086246039983937316427688400486337379416867195943208935654503780844828013651860410256502890125611856727316762

I'll post a more detailed explanation of the code later, but basically this also works by repeatedly multiplying a vector with a sparse matrix, encoded as an ASCII string.  Some clever compression tricks, such as leaving out the all-ones superdiagonal of the matrix, are employed.

Ps. Here's a link to an online demo.  The server has been pretty slow lately, though, so if you see an error message about a timeout, try again (or just download the interpreter and run it yourself).

Addendum:  Here's the promised detailed explanation.  First, let me repost the code with whitespace and comments added:

# Parse input, subtract 8, save in variable m:
~ 8- :m;

# This long string encodes all the constants used by the program (I'll describe it below):
'!5?HZi " A 9 "$??HLTZ^`eik 5Z`e <^ $k H ,Sds ?LT /5@MUav I " i ? "5i G  !#+.4;>@K]_cdhjy{| *HCRJD@:64122/42.,,*860-40-0.+9?B<862//?D<7=@:420-/5:60.-20.+./384/162.-HCRJD@:64122/42.,,*)! !""$&&('

# Parse the data string:
# The data consists of several arrays of positive integers, encoded as printable ASCII
# characters and separated by spaces.  (Note that this means that the range of possible
# data values starts from 1, which requires some adjustment below.  Also, the values in
# L are actually shifted up by 8 to avoid having single quotes in the data string.)

{32-}/   # Subtract 32 (ASCII code of space) from each char and dump result on stack.
]        # Collect numbers from stack into an array.
1,/ ~    # Split array on zeros (formerly spaces) and dump pieces on stack.
:&;      # Save topmost piece (canned responses for inputs 1-7) in var &.
:L;      # Save second piece (element lengths) in var L.
:T;      # Save third piece (nonstandard decay targets) in var T.
]:S;     # Collect remaining pieces (nonstd decay sources) in array and save it in S.

# If m < 0, return a precomputed response from &, else run the indented code below:
0 m > { & m = } {
  # Set V to be the initial element abundance vector (1 Hf + 1 Sn):
  # (Note: both L and V have an extra sentinel 0 at the end to avoid overruns below.)
  L,, { . 49= \ 71= + } % :V
  # Update the element abundances m times:
  {
    # Run the following block for all numbers i from 0 to length(V)-2,
    # collecting the results in an array:
    ,(, {
      # Start with the abundance of element i+1 in V (all elements except H decay
      # downwards; the extra 0 at the end of V is needed to avoid a crash here):
      ).V=\
      # If this element is one of the decay targets listed in T, find the corresponding
      # list of source elements in S and add their abundances from V to the total:
      # (If this element is not in T, we just loop over an empty array at the end of S.)
      T? S= { ( V= + } /
    } %
    # Append a new sentinel 0 to the end of the array and save it as the new V:
    0+:V
  } m *
  # Multiply the element abundances from V with their lengths from L and sum them:
  ,,0\{.V=\L=8-*+}/
} if

The key fact that allows this code to work is that, as the look-and-say transformation is repeatedly applied to any string, it eventually splits into substrings which evolve independently, in the sense that we can obtain all the following elements of the look-and-say sequence starting from that string by taking each of the substrings, applying the look-and-say transformation to each of them independently n times and concatenating the results.

Furthermore, in his 1986 article "The Weird and Wonderful Chemistry of Audioactive Decay" (which basically introduced the look-and-say sequence to the world), John Conway proved a remarkable (and, for this challenge, crucial) result which he called the "cosmological theorem":

  Cosmological theorem (Conway): There is a set of 92 finite strings of numbers 1–3 (which Conway named after the chemical elements; see table here), and two infinite families of strings each consisting of a fixed prefix followed by some number higher than 3 (these can only appear if the initial string contained number higher than 3 or sequences of more than 3 identical numbers), such that, after at most 24 applications of the look-and-say transformation, any string splits into a chain of such elements, each of which thereafter evolves independently (and splits into further elements).

Thus, to determine the length of a string sufficiently far in the look-and-say sequence, it's sufficient to know how many times each element appears in it.  And, since each element evolves independently, knowing these "elemental abundances" is also sufficient for calculating the corresponding abundances of the next string in the sequence, and so on.

As it happens, the look-and-say sequence starting from the string 1 splits into two Conway elements (Hf72 = 11132 and Sn50 = 13211) after just seven iterations.  Thus, thereafter, we only need to keep track of the abundances of the 92 "common" elements (as the two families of "transuranic" elements cannot arise from common elements).

Mathematically, we can treat the elemental abundances as a vector of length 92.  Calculating the abundances in the next step of the look-and-say sequence is then just equivalent to multiplying this vector with a 92 × 92 matrix, which is what r.e.s.'s solution does literally.

In fact, r.e.s.'s solution actually tracks the abundance of each element multiplied with its length (i.e. the "total mass" of that element in the string), adjusting the matrix accordingly, so that the total length of the string is given simply by adding the numbers in the abundance vector together.  However, I did not find that a particularly convenient representation for code golf.  (It was convenient for Nathaniel Johnston's derivation of Conway's polynomial, since it encodes the lengths into the matrix and thus gives the right eigenvalue for the asymptotic growth rate, but we don't care about that here.)

Instead, I just track the raw abundances of the elements, and only multiply them with the lengths at the end.  This has, combined with the convenient fact that none of the decay products of any element contain more than one copy of any element, means that the entries of the transition matrix are just zeros and ones.  Also, by far most of them are, in fact, zeros (in math jargon, the matrix is sparse), so I can save a lot of space by only storing the indices of those entries which are ones.

Also, in his article, Conway ordered the elements such that (except for H1 = 22, which is a fixed point of the look-and-say transformation), each element decays to the next lower element in the sequence (and possibly some others).
In fact, most elements decay only to the next lower elements.  Thus, by using Conway's ordering of the elements, I can hardcode this "standard decay" as part of the iteration, so that I only need to store the matrix entries corresponding to the other, "nonstandard" decays, saving even more space.

(In fact, what I actually do, for reasons mostly to do with how GolfScript's array operations work, is store one array listing the matrix rows containing non-zero entries (i.e. the elements which are produced in nonstandard decays) and another array of arrays listing, for each of these rows, the columns where the non-zero entries occur (i.e. the elements which produce these elements in such decays).  See the code and comments above for how these arrays are actually used to calculate the updated element abundances.)

The final space-saving trick I used was to encode all these arrays as strings of ASCII characters.  Conveniently, there are 95 printable ASCII characters from space (32) to ~ (126), and the largest value that appears in any of the arrays is 92, so they fit very well.  One extra tweak I made was to shift the values in the element length array (which only go up to 42 anyway) up by 8 so that I could avoid the character ' (39) and thus store my data in a single quoted string without having to add any backslash escape characters.

There are some other minor optimizations too, but those are just standard GolfScript coding tricks.  I should note that the actual code is not all that carefully optimized — it's quite possible that it could be golfed down further.

In any case, despite the inherent slowness of a double-interpreted language like GolfScript, the code runs quite fast and scales well: computing the length of the 10,000th string in the look-and-say sequence takes about 1.5 minutes on my computer.

Conveniently, GolfScript stores all numbers as arbitrary-length integers (bignums), so I didn't have to do anything special to make it produce exact results even for large inputs.
The expected time complexity of this program is O(n log n) (as the element abundances grow linearly with n, and bignum addition takes O(log n) time), and the actual runtime seems to fit that prediction pretty well, as the graph below shows:

(Time is in seconds; for what it's worth, the green curve is given by y = (a x log(b + x) + c) / x, where a = 0.00106462026133545, b = 2720.25843721031 and c = -0.0401630789530016.  The spike on the left mainly comes from the roughly constant runtimes for n < 8, which become relatively large when divided by small n.  I did not include it in the curve fit.)


Ruby, 96 69 bytes

->s{/^[^aeiou]/=~(r=s.tr'zb-yadehinotu','b-zefijopuva')?$'+$&+'ay':r}

Try it online!

Fun fact of the day: tr() matches strings right-to-left. I always assumed it was left-to-right.


Funciton, 4322 − 50% = 2161

Not really trying to golf here. Going more for the beauty angle. I think the main program looks really neat, a perfect rectangular box tucked away on the right.

As always, you can get a better rendering by executing $('pre').css('line-height',1) in your browser console.

                 ┌─────────────────────────┐
               ┌─┴─╖                     ┌─┴─╖
      ┌────────┤ · ╟─────────────────────┤ · ╟─────────────┐    ╔═════════╗   ╔════╗  ╔════╗
      │        ╘═╤═╝     ╔═════════╗     ╘═╤═╝ ╓───╖       │    ║ 1257283 ║ ┌─╢ 40 ║  ║ 25 ║
      │          │       ║ 2097151 ║       ├───╢ ʫ ╟───┐   │    ║ 6456094 ║ │ ╚════╝  ╚══╤═╝
    ┌─┴─╖        │       ╚════╤════╝     ┌─┴─╖ ╙─┬─╜ ┌─┴─╖ │    ║ 8219021 ║ │  ┌───╖   ┌─┴─╖
┌───┤ · ╟────────┴────┐       └─────┬────┤ · ╟───┴───┤ · ╟─┤    ║ 4660190 ║ └──┤ × ╟───┤ % ║
│   ╘═╤═╝             │            ┌┴┐   ╘═╤═╝       ╘═╤═╝ │    ╚════════╤╝    ╘═╤═╝   ╘═╤═╝
│     │               │            └┬┘     │           │   │    ╔═══╗  ┌─┴─╖  ┌──┴─╖   ╔═╧═╗
│     │  ╔═══╗ ┌────╖ │           ┌─┴─╖ ┌┐ │           │   │    ║ 8 ╟──┤ ʫ ╟──┤ >> ║   ║   ║
│     │  ║ 1 ╟─┤ >> ╟─┘       ┌───┤ ? ╟─┤├─┤           │   │    ╚═══╝  ╘═╤═╝  ╘══╤═╝   ╚═══╝
│     │  ╚═══╝ ╘══╤═╝         │   ╘═╤═╝ └┘ │           │   │    ╔════════════════╧═════════╗
│     │         ┌─┴─╖ ┌───╖ ┌─┴─╖ ┌─┴─╖  ╔═╧═╗         │   │    ║ 609678112368778425678534 ║
│   ┌─┴─────────┤ ʫ ╟─┤ ‼ ╟─┤ · ╟─┤ ‼ ║  ║ 1 ║         │   │    ║ 616189712722605554111376 ║
│   │           ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝  ╚═══╝         │   │    ║ 461573643915077926310571 ║
│   │             │     │     │   ╔═╧══╗               │   │    ║ 355541007599150245813976 ║
│   │   ╔══════╗  │     │     └───╢ 45 ║               │   │    ║ 426564826002362964111793 ║
│   │   ║ 2097 ║  │   ┌─┴─╖ ┌───╖ ╚════╝               │   │    ║ 714054902293682079346275 ║
│   │   ║ 1565 ║  └───┤ · ╟─┤ ♭ ╟─┐                    │   │    ║ 663973372550500581508544 ║
│   │   ╚═╤════╝      ╘═╤═╝ ╘═══╝ ├────────────────────┘   │    ║ 874263187322344354338195 ║
│   │   ┌─┴─╖         ┌─┴─╖       │                        │    ║ 642609790172899326178321 ║
│   │   │ ‼ ╟─────────┤ ? ╟───────┘                        │    ║ 071643306454414932126243 ║
│   │   ╘═╤═╝         ╘═╤═╝                                │    ║ 308860823981077902637848 ║
│ ┌─┴─╖ ┌─┴─╖ ╔═══╗   ┌─┴─╖                                │    ║ 322657399386789617074176 ║
└─┤ · ╟─┤ ʫ ╟─╢ 8 ║ ┌─┤ ? ╟────────────────────────────────┘    ╚══════════════════════════╝
  ╘═╤═╝ ╘═╤═╝ ╚═══╝ │ ╘═╤═╝
    │ ┌───┴╖ ╔════╗ │ ╔═══╗
    └─┤ >> ╟─╢ 21 ║ └─╢ 0 ║
      ╘════╝ ╚════╝   ╚═══╝

Continuing in the tradition of giving Funciton functions names consisting of a single, strange, rarely-used Unicode character, I thought about what could best represent this challenge, and it occurred to me that Link and Zelda (or, if you want, Legend of Zelda) give you LZ, so the lower-case digraph ʫ (U+02AB, ʟᴀᴛɪɴ sᴍᴀʟʟ ʟᴇᴛᴛᴇʀ ʟᴢ ᴅɪɢʀᴀᴘʜ) seems appropriate.

Explanation

As explained in the esolangs article, the Funciton program receives the input encoded as what I would call “UTF-21”, but as a single humongous integer. If I wanted to use this number as a key to a hashmap (dictionary, associative array), I’d need a hash function that satisfies two criteria: one, it’s simple enough to implement in Funciton, and two, all of the 13 expected input strings give a different hash value. The simplest hash function I could think of was input % m for some value of m. Therefore, I tried m = 13, 14, 15, etc. until I got to the smallest integer for which all the hash values are unique. Turns out this number is 25.

The hash values are:

zel =  6
sas = 19
eps = 10
sos = 22
sot =  1
sst =  9
mof = 14
bof =  3
sow = 13
nos = 17
ros = 21
pol = 16
scs = 23

We encode each song by having one bit represent the presence or absence of a note. For example, Zelda's Lullaby would be encoded as follows:

---^-----^------- = 01001000
-<-----<--------- = 10010000
----->----->----- = 00100100
----------------- = 00000000
----------------- = 00000000

except that the bits are in the opposite order; the top left cell is in the least significant bit. This means every song is 40 bits long.

We thus create a (moderately sparse) hash table by taking a 40×25 = 1000-bit number and placing the bit pattern for each song in the right place according to its hash value. The monstrous number in the program is exactly this hash table.

Here’s what each of the remaining numbers mean:

45 = 0x2D is the Unicode for -.
1257283645609482190214660190: This is the string ^<>VA in UTF-21. In hindsight I could have used 7 bits per character here, making the number shorter, but UTF-21 is so deeply traditional in Funciton that it simply didn’t occur to me.
2097151 = 0x1FFFFF = (1 << 21) − 1. Used to get the first character from the above string.
20971565: This is the string -\n, which is appended to the end of each line.

It may seem curious that this number and the previous look so similar, but if you think about it, it’s because we’re using decimal and the Unicode for \n happens to be 10. That last number is (10 << 21) + 45.

The program now proceeds as follows:

The main program calls ʫ with the following 3 parameters:

B: The hash table, shifted right by 40 bits times the hash value of the input. The song we want to output is now in the 40 least significant bits.
c: The string ^<>VA.
a: The number 8.

In each iteration of ʫ,

if c is not empty,

if a is not zero, look at the bottom bit of B. Output -, followed by another - if it is zero or the first character of c otherwise. Shift right B by one to remove one bit and decrement a.
if a is zero, output -\n, then chop off the first character from c and start another loop with a = 8.

if c is empty, we are done.


Python 3, 27 bytes

h=lambda n:n and 1/n+h(n-1)


Python 3, 77 bytes

def f(n,e):r=range(n);all(any(m-pow(m,e*d,n)for m in r)or print(d)for d in r)

Try it online!

Direct translation of the requirement. any(...) becomes false when the smallest correct d is found, and print(d) returns None, making all(...) stop running.

76 bytes, if unlimited memory is allowed

def f(n,e):r=range(n);all(any(m**(e*d)%n-m for m in r)or print(d)for d in r)

Try it online!


Python 2, 54 bytes

i=n=input()
while i:i-=1;print((' '*~-2**i+'#')*n)[:n]

Try it online!

Prints with lots of leading whitespace. Each row i counting down from n repeats a pattern of 2**i-1 spaces followed by a #. This pattern is repeated up to the width of the ruler, which is the input n. This is done by multiplying the pattern string by n and taking the first n characters with [:n].

The pattern can be made by string formatting for an equal length alternative.

i=n=input()
while i:i-=1;print('%%%ds'%2**i%'#'*n)[:n]

A cute slicing method is longer.

n=input();s=~-2**n*' '+'#'
exec"s=s[1::2]*2;print s[:n];"*n


Generate a 6 character string from a 15 character alphabet

CJam (23 + 14 + 10 = 47 bytes)

Arbitrary alphabet: 23 bytes (online demo)

{"ABC123!@TPOI098"mR}6*

Hexadecimal alphabet: 14 bytes (online demo)

{FmrAbHb'0+}6*

Custom alphabet: ABCDEFGHIJKLMNO, 10 bytes (online demo)

{Fmr'A+}6*

Dissection

The hexadecimal one is the interesting one:

{      e# Loop...
  Fmr  e#   Select a random number from 0 to 14
  AbHb e#   Convert to base 10 and then to base 17
       e#   (i.e. add 7 if the number is greater than 9)
  '0+  e#   Add character '0' (i.e. add 48 and convert from integer to character)
       e#   Note that 'A' - '0' = 17
}6*    e# ...six times

The six characters are left on the stack and printed automatically.


Japt -P, score: 255 (2 bytes)

ff

f => filter, second f => everything but 'f'

Try it online!

Japt, score: 255 (2 bytes)

From @Shaggy

oo

o => remove everything but, second o => 'o'

Try it online!


Ruby, 1000 - 303 299 337 - 50 373 - 170 382 - 170 - 140 379 - 170 - 140 chars = 697 701 713 797 928 931

I'm sure there are many improvements to be made.

(This requires Nokogiri)

require'open-uri'
require'nokogiri'
x="/wiki/"+gets.chomp
r=[n=i=0]
until x=~/\/Philosophy/
d=Nokogiri.HTML open"http://en.wikipedia.org#{x}"
x=d.css('p a').select{|a|t=a.xpath('preceding::text()').map(&:text)*'';t.count('(')==t.count(')')&&a.attr('href')=~/^.wiki[^:]+$/}[i].attr'href'
i=0
puts r.index(x)?"#{$><<'i=';i=($*[0]||gets).to_i;''}": r.push(x)[-1][6..-1]
n+=1
end
p n

Example run:

c:\a\ruby>wikipedia_crawl_philosophy
Latin (note: this is my input)
Classical_antiquity
History
Umbrella_term
Terminology
Word
Linguistics
Science
Knowledge
Fact
Proof_(truth)
Argument
Logic
Reasoning
Consciousness
Quality_(philosophy)
Property_(philosophy)
Modern_philosophy
Philosophy
18

Sample one where I had to go to a different link

c:\a\ruby>wikipedia_crawl_philosophy
Snow
Precipitation_(meteorology)
Meteorology
Atmospheric_physics
Synoptic_scale_meteorology
i=2 // I put the 0-indexed number of the link I wanted to go to (so, the third link)

Weather
Atmosphere
Gas
State_of_matter#The_four_fundamental_states
Physics
Natural_science
Sciences
Knowledge
Fact
Proof_(truth)
Argument
Logic
Reasoning
Consciousness
Quality_(philosophy)
Property_(philosophy)
Modern_philosophy
Philosophy
25

Tricks I used:

I used the selector p a to only get non-italic links, because all links in the actual article that are not italics are always in paragraph elements in Wikipedia.


The cyclic sequence of even digits, with odds in between

Haskell, 50 46 bytes

1#cycle[0,2..8]
n#r=1:take n r++(n+1)#drop n r

Try it online!

1#cycle[0,2..8] returns the sequence as infinite list.

-4 bytes thanks to Ørjan Johansen!


Python 2, 64 bytes

def f(n):d=0x1211252b5375>>2*n-4&3;print"nwes"[d];f(n+d*3+d%2-5)

Try it online!

A function that prints one direction per line, terminating with error.

The constant 0x1211252b5375 encodes in base 4 the direction d we travel from each room number as a number 0 through 3. The extraction digit >>2*n-4&3 is also designed to give a negative shift error when n=1, terminating the code. We update the room number n via an offset that's computed from the direction d as d*3+d%2-5, which maps:

d   d*3+d%2-5
0  -> -5
1  -> -1
2  ->  1
3  ->  5


CJam, 21 bytes

l~_,\2/f-l:~fm>:.+Af%

Test it here.

Explanation

l~   e# Read and evaluate N.
_,   e# Duplicate and turn into range [0 1 ... N-1]
\2/  e# Swap with other copy and (integer) divide by 2.
f-   e# Subtract this from each element in the range to get
     e# [-(N-1)/2 ... -1 0 1 ... (N-1)/2]
l:~  e# Read string and evaluate each digit separately.
fm>  e# Make one copy of the result for each element i in the range, shifting the array
     e# i cells to the right, cyclically.
:.+  e# Sum the columns of the resulting matrix.
Af%  e# Take each of those sums modulo 10.


Lead your team to win the wrestlers world championship!

Python 2, 59 57 bytes
-2 bytes thanks to @dingledooper!

lambda a,b:sum(b.sort()<b<[x]>b.pop(0)for x in sorted(a))

Try it online!
A function that takes 2 lists as arguments, and returns the maximum number of matches that can be won.
Approach
For each opponent (from weakest to strongest), match that opponent with the weakest available member of my team that can win.
For example, let's say the strength of 2 teams (sorted) are as follow:
No.       1  2  3  4  5
Me       [2, 2, 4, 5, 8]
Opponent [3, 6, 7, 7, 9]

The 1st opponent has strength 3, so we need to match that with our 3rd team member.
The 2nd opponent has strength 6, so we match that with our 5th.

We cannot win any more match. So in total we can win at most 2 matches.
Ungolfed code
a,b=map(sorted,input())  # sorted strength of my team and opponent team
s = 0                    # number of matches that can be won
for x in a:              # loop through my team, in order of increasing strength
  if x > b[0]:             # if current member can beat the weakest opponent left
    s += 1                   # then match those two
    b.pop(0)                 # and remove the weakest opponent
                           # (otherwise, current member is useless)
print s


Tampio, Cracked

m:n tulos on luvun funktio tulostettuna m:ään, missä luku on x:n kerrottuna kahdella seuraaja, kun x on luku m:stä luettuna
x:n funktio on luku sadalla kerrottuna sadalla salattuna, missä luku on x alempana sadan seuraajaa tai nolla
x:n seuraajan edeltäjä on x
x:n negatiivisena edeltäjä on x:n seuraaja negatiivisena
nollan edeltäjä on yksi negatiivisena
x salattuna y:llä on örkin edeltäjä, missä örkki on x:n seuraajan seuraaja jaettuna y:llä korotettuna kahteen
sata on kiven kolo, missä kivi on kallio katkaistuna maanjäristyksestä
kallio on yhteenlasku sovellettuna mannerlaatan jäseniin ja tulivuoren jäseniin
tulivuori on nolla lisättynä kallioon
mannerlaatta on yksi lisättynä mannerlaattaan
maanjäristys on kallion törmäys
a:n lisättynä b:hen kolo on yhteenlasku kutsuttuna a:lla ja b:n kololla
tyhjyyden kolo on nolla
x:n törmäys on x tutkittuna kahdellatoista, missä kaksitoista on 15 ynnä 6
x ynnä y on y vähennettynä x:stä

Run with:

python3 suomi.py file.suomi --io

The instructions for installing the interpreter are included in the Github page. Please tell if you have any difficulties running this.

   The program in pseudocode. The program performs very slowly because my interpreter is super inefficient. Also, I didn't use any opt-in optimizations available, which can reduce the evaluation time from several minutes to about 10 seconds.


Convert a string of digits from words to an integer

PHP, 74 bytes

foreach(explode(' ',$argn)as$w)$n.='793251_8640'[crc32($w)%20%11];echo+$n;

Try it online!

Tried to get a solution which doesn't copy existing answers. I get cyclic redundancy checksum polynomial of 32-bit lengths (crc32) for each word and then do a mod 20 and mod 11 on it to get mixed up unique values from 0 to 10 (missing 6) for each digit. Then using that unique value I find the actual digit.

| Word  | CRC32      | %20 | %11 | Equivalent digit |
|-------|------------|-----|-----|------------------|
| zero  | 2883514770 | 10  | 10  | 0                |
| one   | 2053932785 | 5   | 5   | 1                |
| two   | 298486374  | 14  | 3   | 2                |
| three | 1187371253 | 13  | 2   | 3                |
| four  | 2428593789 | 9   | 9   | 4                |
| five  | 1018350795 | 15  | 4   | 5                |
| six   | 1125590779 | 19  | 8   | 6                |
| seven | 2522131820 | 0   | 0   | 7                |
| eight | 1711947398 | 18  | 7   | 8                |
| nine  | 2065529981 | 1   | 1   | 9                |

Another 74 bytes CRC32 alternative using %493%10: Try it online!

Another 74 bytes CRC32 alternative using %2326%11: Try it online!

PHP, 74 bytes

foreach(explode(' ',$argn)as$w)$n.=strpos(d07bfe386c,md5($w)[21]);echo+$n;

Try it online!

Another alternative with same length, takes 22nd character in the md5 of the word (only character which gives a unique value for each word) and then uses that character to map to a digit.


This code errors on *this* and *that*, is it really written in them?

Python 2 / Python 3, 60 bytes

print("This program errors out in Python %d :P"%(3/2*2))*1;a

Python 2 got NameError: name 'a' is not defined
Python 3 got unsupported operand type(s) for *: 'NoneType' and 'int'

Python 2:

/ is integer division, 3 / 2 got 1; int(3 / 2 * 2) is 2.
print is a statement, so the first statement read as print((...)*1), here *1 means repeating the string once.
second statement referenced a non-existing variable, which caused the error.
Try it online!

Python 3:

'/' is floating number division, 3 / 2 got 1.5; int(3 / 2 * 2) is 3.
print is a function, so the first statement read as (print(...))*1.
function print returns None; Multiplication do not work on None x int, so it report "unsupported operand".
Try it online!


Write a function to decrypt Feynman Challenge Cipher #1

Golfscript, 10 chars

n--1%5/zip

Takes input from stdin. It may be separated by newlines, as in the question presentation, or not, as many answers assume. (Stripping the newlines is necessary anyway given that it's likely to arrive with one on the end, which messes up the blocks of 5). If we assume that the input arrives with precisely one newline, being the last character, we can shave one character to

)!(%5/zip


JavaScript (ES6),  89 85 83  81 bytes
Takes input as a set. Returns either \$0\$ or \$1\$.
Note: Although it doesn't make sense from a theoretical perspective, the set is expected to be defined in ascending order so that the highest value appears at the end once it's converted back to an array.

f=(s,n=~[...s].pop(),b,t=0,g=i=>--i>n?b^f(s,i,!b,t-i)||g(i):0)=>~n?b^g``:s.has(t)

Try it online!
Commented
  f = (         // f is a recursive function taking:
    s,          //   s = input set
    n = ~[...s] //   n = opposite of the value played by the previous player,
        .pop(), //       or -(maximum value of the set + 1) for the first iteration
    b,          //   b = flag telling whether it's Bob's turn
    t = 0,      //   t = sum of all (positive) values played so far
    g = i =>    //   g is a recursive function taking a counter i <= 0
      --i > n ? //     decrement i; if i is greater than n:
        b ^     //       invert the result of the following call if it's Bob's turn
        f(      //       recursive call to g:
          s,    //         pass s unchanged
          i,    //         pass the new value of i
          !b,   //         invert the flag b
          t - i //         subtract i from the sum
        )       //       end of recursive call
        || g(i) //       if the above result is falsy, try a recursive call to g
      :         //     else:
        0       //       stop recursion
  ) =>          //
    ~n ?        // if n is not equal to -1:
      b ^ g``   //   invoke g with i = [''] (zero'ish)
                //   and invert the result if it's Bob's turn
    :           // else:
      s.has(t)  //   return true if t is in s (Alice wins), or false otherwise


Evaluating the score based from a chess FEN string

><>, 64 57 56 53 bytes

"QRBNP"013359v
$0p4}:{:v?=1l<p4+' '{-
g4v?(0:i<+
n~<;

(-7 bytes with some inspiration from @El'endiaStarman's answer, -3 bytes thanks to @randomra)

Explanation

The program uses the codebox as a lookup table. Out-of-range puts/gets don't work with the online interpreter, so this only works with the official Python interpreter.

The first line pushes the pieces, followed by the piece values. It also pushes an initial 0 to kick off the total for the third line.

The second line then puts the appropriate positive or negative value at the corresponding piece cell, e.g. -1 is placed at ('p', 4) and 1 is placed ('P', 4). The length of the stack is checked to make sure the loop runs 5 times.

After the loop is over, the stack consists of our single zero from the first line. For each char we perform a lookup at the corresponding cell in the table and add it to our total. By default, uninitialised cell values are 0, which is perfect for our purposes.

The last line merely prints the result.


C, 250 bytes
#define h x=(j+x-1+d%3)%j,i=(j+i+(d=='v')-(d==94))%j
char a[999],b[999];x,i,d=2,k,f;main(j){for(;gets(a+j*i);)j=strlen(a+j*i++);for(x=strchr(a,65)-a,i=x/j,x=x%j;!k*d;h)k|=b[f=j*i+x]&1<<d%5,b[f]|=1<<d%5,(f=a[f])&16?d=f:f&4?h:f&2?d=0:0;putchar(48+!k);}

This also requires that the input is padded with spaces.
Ungolfed:
#define h x=(j+x-1+d%3)%j,i=(j+i+(d=='v')-(d==94))%j
char a[999],b[999];x,i,d=2,k,f;
main(j){
 for(;gets(a+j*i);)j=strlen(a+j*i++); //read lines and determine line length
 for(x=strchr(a,65)-a,i=x/j,x=x%j;    //the current position is 'A'
 !k*d; //as long as we have not arrived at 'B'
       //and not travelled through the same cell and in the same direction twice
 h)    //advance one in the current direction
   k|=b[f=j*i+x]&1<<d%5,b[f]|=1<<d%5,  //if we have already travelled
                                       //through this cell in this direction
   (f=a[f])&16?d=f //change direction if this cell is one of <>^v
   :f&4?h          //if this cell is '&', advance one in the current direction
   :f&2?d=0:0;     //if we have reached 'B'
 putchar(48+!k);
}


Bash, 978 708 675 673 650 636 632 631 598 594

211 bytes for the program and 382 bytes for the data.

Input is on STDIN, output is on STDOUT. WARNING: creates files called g and a, if they exist, they will be overwritten!

zcat y>g 2>a
s=(`sed 's/[A-Z][a-z]*/& /g;q'<g`)
p=1.008
v=`sed 's/[0-9]\+/*&/g;s/(/+(0/g'`
r=(`tail -1 g`)
for n in {0..91};{
p=`bc<<<$p+${r[n]}`
v=${v//${s[n]}/+$p}
}
o=`bc<<<0$v 2>a`
echo ${o:-Invalid formula}

Data file

This requires a file called y, which is the zopfli-compressed form of this data (no trailing newline). zopfli is a gzip-compatible compression algorithm and can be decompressed with standard gzip tools. It was run with 1024 iterations (this is probably too much). The last 8 bytes were then removed.

HHeLiBeBCNOFNeNaMgAlSiPSClKArCaScTiVCrMnFeNiCoCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbITeXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcPaThU
0 2.995 2.937 2.072 1.798 1.201 1.996 1.992 2.999 1.182 2.81 1.315 2.677 1.103 2.889 1.086 3.39 3.648 .850 .130 4.878 2.911 3.075 1.054 2.942 .907 2.848 .24 4.613 1.834 4.346 2.904 2.292 4.038 .944 3.894 1.670 2.152 1.286 2.318 1.682 3.054 2.04 3.07 1.836 3.514 1.448 4.543 2.407 3.892 3.050 5.144 .696 3.693 1.612 4.422 1.578 1.211 .792 3.334 .758 5.36 1.604 5.286 1.675 3.575 2.43 2.329 1.675 4.120 1.913 3.523 2.458 2.892 2.367 4.023 1.987 2.867 1.883 3.625 3.788 2.82 1.78 .02 1 12 1 3 1 4.036 1.002 5.991

The base64 of y is (use base64 -d to reproduce the original file):

H4sIAAAAAAACAwTB226DMAwA0G9LvEJQIbVi70LfHPBoJAiSaR729zsnBB2LVw/x0UWNMm1up4IE
+90ZCC1cvsCm2mkscEJ71l56dRept7ulTDY/Lebp5CW19MLVbbAOlSrlgfVH4fIyCihaXPGg49b6
lfPHXzhvxsecxxZ+Wb6TPq7B8O1a2HjH7Aue7p1qZ0ncgsKvz/8WxuRGoigGgfcfxYvA8r7kn9iA
ei6ohAt/+lzuihmD1PFnMrdIV0PeNfOczh3Ylrw8hnHaM6w1WC8V3X4hcYjOfbKlTyz0pewsP5nh
plOUK9mkPzkd4HLiCbktIGyQI5uaUvZzNBrwLhOf9hJij+Jo5WBf6mHLfh2OFqeaxOHbaGAZl5mL
h5UBI3Hlx99GX4llPumDjgw+NIee7uCaRbrZkzluIhJYi2E0ZU2gb5OnYBTSJQMRfv91irmCz4KK
B5Va5J7T7IGjHnR22PeAd+m3F3KW/voz4BMFPGNgxHE0Loq65M6+Pw==

The md5sum is d392b0f5516033f2ae0985745f299efd.

Explanation

The numbers in the file are increments of relative atomic mass (so the relative atomic mass of lithium is 1.008 + 0 + 2.995 + 2.937).

This script works by converting the chemical formula into an arithmetical expression with + and *, replacing each symbol with its relative atomic mass, then feeding the expression to bc. If the formula contains invalid symbols, bc will give a syntax error and output nothing to STDOUT; in that case, the output is Invalid formula.

If STDIN is empty, the output is 0. Nested brackets are supported.

zcat y>g 2>a # Unzip the file y and output result to the file g. Send standard error to file a (there will be an error because the last 8 bytes are missing)
s=(`sed 's/[A-Z][a-z]*/& /g;q'<g`)  # Read from g to sed; append a space after any capital letter optionally followed by a lowercase letter; exit at the end of the first line so the atomic masses are not processed in this way; parse result as space-separated array and save to variable $s
p=1.008 # In the upcoming loop, $p is the value obtained in the previous iteration
v=`sed 's/[0-9]\+/*&/g;s/(/+(0/g'` # Read from standard input to sed; prepend a * after any sequence of digits; replace ( with +(0; save to $v
r=(`tail -1 g`) # Get the last line of file g; parse as space-separated array; save to $r
for n in {0..91};{ # Loop once for each number from 0 to 91; set $n to the current number each iteration
p=`bc<<<$p+${r[n]}` # Concatenate $p, + and the next number from $r; send to bc and evaluate as arithmetic expression; save to $p (i.e. add the next increment from the file to $p)
v=${v//${s[n]}/+$p} # Replace every occurence of the current element symbol with + and $p (i.e. replace each symbol with a + and its relative atomic mass
} # end loop
o=`bc<<<0$v 2>a` # Prepend 0 to $v; send to bc and evaluate as arithmetic expression; redirect any errors on standard error to the file a; save result to $o
echo ${o:-Invalid formula} # If $o is empty (if there was a syntax error), output Invalid formula; otherwise output $o

Example

C6H2(NO2)3CH3  #input
C*6H*2+(0NO*2)*3CH*3  #after line 3
+12.011*6+*1.008*2+(0+14.007+15.999*2)*3+12.011+1.008*3  #after the loop in lines 4-6
0+12.011*6+*1.008*2+(0+14.007+15.999*2)*3+12.011+1.008*3  #given to bc in line 7
227.132 #output as evaluated by bc


Produce the most digits of an irrational number with only 64 KB of memory

Python - 10157831 digits

import sys

sys.stdout.write("0.")
a = 0
while True:
    a += 1
    sys.stdout.write(str(a))

Prints 0.1234567891011121314151617181920..., which is the Champernowne constant in base 10, until the program runs out of memory.

When the program's counter a reaches a specific number x, it has printed out at least x digits (as every number has at least one digit), and more on the order of x log x digits. For x = 1010000, the binary data required to represent a would be about 4.1 kilobytes, which is well below the allotted limit.

Interesting to note - any computer running this program would run out of total memory long before it ever printed off even 10100 digits (let alone 1010000), due to there only being about 1080 particles in the observable universe and only about 1021 bytes of memory available for storage on all of Earth's data computing devices.

Wolfram Alpha says that the total number of digits printed is actually about 4.09776347957... × 10157831, assuming we can get all the way to 2524288 - 1 without running into memory issues with the bignum storage.


APL (66)

{∊⍉⍵⍪⍉⍪(¯1+⌈?2×⍵∊',.!?')/¨{' ',⍵,⍨'''kay',⍨'mM'[1+⍵≠',']/⍨?3}¨⍵}⍣≢

Result of 10 runs:

      ↑ ({∊⍉⍵⍪⍉⍪(¯1+⌈?2×⍵∊',.!?')/¨{' ',⍵,⍨'''kay',⍨'mM'[1+⍵≠',']/⍨?3}¨⍵}⍣≢)¨ 10/⊂'Test, test. Test! Test?'
Test, m'kay, test. Test! Test?
Test, test. M'kay. Test! MMM'kay! Test? M'kay?
Test, mm'kay, test. Test! MM'kay! Test? MM'kay?
Test, mmm'kay, test. Test! Test? M'kay?
Test, mm'kay, test. Test! Test? M'kay?
Test, test. MM'kay. Test! Test? MMM'kay?
Test, test. MMM'kay. Test! MMM'kay! Test? M'kay?
Test, test. Test! MM'kay! Test?
Test, mm'kay, test. M'kay. Test! Test?
Test, test. MM'kay. Test! MM'kay! Test?

Explanation:

{...}⍣≢: apply the function to the input until the value changes

Generate a M'kay for each character:
{...}¨⍵: for each character in the input:

'mM'[1+⍵≠',']/⍨?3: generate 1 to 3 ms or Ms depending on whether the character was a comma or not.
'''kay',⍨: append the string 'kay.
⍵,⍨: append the character
' ',: prepend a space.

(¯1+⌈?2×⍵∊',.!?')/¨: for each M'kay', if its corresponding character is one of .,!?, select it with 50% chance, otherwise select it with 0% chance.
⍉⍵⍪⍉⍪: match each selection with its character,
∊: list all the simple elements (characters) in order.


Octave, 32 bytes

@(L)L(x=3:3:end)(diff(L)(x-2)<0)

Try it online!
or
Verify test cases!
L3 = L(3:3:end)  %extract last elements of groups
d= diff(L)       % first difference of the list
y=d(1:3:end)     %extract first elements of each subgroup of the difference
idx = y<0        %check for negative numbers
result = L3(idx)


Python 2, 117 113 108 107 106 105 bytes

from random import*
def f(n):a=['']*5;exec"i=randint(0,(n>44)+(n>59)<<1);a[i]=(a[i]or 0)+1;"*1000;print a

Try it online!

Returns a reversed list (bottom first)

Version inspired by the stackoverflow answer in the comments (edgecases are more likely):

Python 2, 129 bytes

from random import*
def f(n):a=sorted([1000]*5+sample(range(1001)*5,(n>44)+(n>59)<<1));print[y-x or''for x,y in zip([0]+a,a)[:5]]

Try it online!


Python 3, 215 bytes

m,v,*d=-1,[],
L,*l=0,
for c in input():
	if c>"[":a=v.pop();l.pop()*a and exit(1);d.pop();d or exit(0);v[m]=v[m]*(d[m]%2)+a;d[m]=1
	elif c>"Z":l+=[L and v[m]];v+=0,;d+=0,
	else:v[m]=v[m]if d[m]else 1;d[m]=2
	L=c<"A"

Try it online!
Exit code 0 if it will halt, 1 otherwise.
This is just a naive implementation of the interpreter, but golfed down. Here's a ungolfed version with debug output.
+12 bytes to fix a bug
-8 bytes thanks to Unrelated String


Python 3, Score: 81, Cracked
X =  abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&'*,./:;<=>?@[]^_`{|}~
Not terribly interesting since it has such a high score, but this should be somewhat difficult to crack...
Clarification: This is in fact a full Python 3 program, running it locally with python3 print_x_out.py produces the above output for me. Likewise, the below verifier script produces no output:
with open("print_x_out.py") as file:
    source = file.read()

output = """ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&'*,./:;<=>?@[\]^_`{|}~"""

for c in output:
    if c in source:
        print(f"Failed verifier check for '{c}'")

Edit: Well, that was faster than expected...


Haskell, 67 64 bytes

(>>=(==))>>=until$p.show is an unnamed function taking an integer as input and returning its powertrain.

Saved 3 bytes thanks to Zgarb

p(x:y:r)=p[x]^p[y]*p r;p[]=1;p x=read x
(>>=(==))>>=until$p.show


J, 49 47 22 bytes
[:I.1(-:\:~i.])/@|:\.]

Try it online!
-14 bytes after reading xigoi's idea of comparing the first index matches to the ranks.
Thanks to tsh for a test case showing that we needed "length not equal to 1" rather than "length greater than 1" as the failure criterion.
Returns 0-based index if exactly one liar is found, and 0 or multiple values otherwise.  Takes "length" by 2 matrix with 0-indexed rank list as left column, score list as right column.

1...\.] For each 1-item outfix (list with item removed), apply the verb...
(...)/@|: Transpose and put the verb in parens between the two rows, so that the rank list is its left arg, and the score list is its right arg.
-:\:~i.] Does the rank list match -: the first index of the score list i.] within the score list sorted descending \:~?  We now have a 0-1 list, where 1 indicates a liar.
[:I. Return the indexes of all ones.


APL (72)

Not entirely serious, but I couldn't resist. The names are generated from a subset of the APL charset. The names are between 5 and 14 characters long.

{'Greetings Earthfolk, I am'⍺'of the planet'⍵}/{⎕AV[186+{?25}¨⍳4+?9]}¨⍬⍬

Example output:

Greetings Earthfolk, I am  ⌹⍒|⍟∩⊤∩⍉⊂⊥⌽  of the planet  ∩⌹⍱⍎∪≢⊂∩
Greetings Earthfolk, I am  ⍕≡|⍕⍋!⍟⌹  of the planet  ⊂⊤⊤⌽⍟⊖⍱⊤⊤⍟⊥
Greetings Earthfolk, I am  ≢⍉⊂⍫⊂  of the planet  ⍋⌽!⍟⍉⊂∪≢


JavaScript (ES6), 190 bytes

(m,n)=>m.map((a,r)=>a.map((_,c)=>f(r,c,[0],0)),o=f=(x,y,s,t)=>s[n]?o>t?0:o=t:s.indexOf(w=x+","+y)<0&&m[y]&&(v=m[y][x])<1/0&&f(x+1,y,s=[...s,w],t+=v)+f(x,y+1,s,t)+f(x-1,y,s,t)+f(x,y-1,s,t))|o

Explanation

Takes the matrix as an array of arrays.

Starts from each square then uses a recursive function to test every possible combination. This is a brute-force approach, but it finishes almost instantly for the first test case on my machine.

(m,n)=>
  m.map((a,r)=>                 // for each row
    a.map((_,c)=>               // for each column
      f(r,c,[0],0)              // start checking paths from the coordinate of the square
    ),
    o=                          // o = output number (max total)
    f=(x,y,s,t)=>               // recursive function f, x & y = current square, t = total
                                // s = array of used squares (starts as [0] so length = +1)
      s[n]?                     // if we have used n squares
        o>t?0:o=t               // set o to max of o and t
      :s.indexOf(w=x+","+y)<0&& // if the square has not been used yet
      m[y]&&(v=m[y][x])<1/0&&   // and the square is not out of bounds
                                // ( if value of square is less than Infinity )

        // Check each adjacent square
        f(x+1,y,
          s=[...s,w],           // clone and add this square to s
          t+=v                  // add the value of this square to the total
        )
        +f(x,y+1,s,t)
        +f(x-1,y,s,t)
        +f(x,y-1,s,t)
  )
  |o                            // return output

Test

var solution = (m,n)=>m.map((a,r)=>a.map((_,c)=>f(r,c,[0],0)),o=f=(x,y,s,t)=>s[n]?o>t?0:o=t:s.indexOf(w=x+","+y)<0&&m[y]&&(v=m[y][x])<1/0&&f(x+1,y,s=[...s,w],t+=v)+f(x,y+1,s,t)+f(x-1,y,s,t)+f(x,y-1,s,t))|o
<textarea rows="7" cols="40" id="Matrix">10 -7 11 7 3 31
33 31 2 5 121 15
22 -8 12 10 -19 43
12 -4 54 77 -7 -21
2 8 6 -70 109 1
140 3 -98 6 13 20</textarea>

N = <input type="number" id="N" value="6" />

<button onclick="result.textContent=solution(Matrix.value.split('\n').map(x=>x.split(' ').map(z=>+z)),N.value)">Go</button>


MMIX assembly (28 Bytes)

64 bit numbers

rbit:
    SETH $1,#0102 # load matrix in 16-byte steps
    ORMH $1,#0408
    ORML $1,#1020
    ORL  $1,#4080
    MOR  $0,$1,$0 # multiplication 1
    MOR  $0,$0,$1 # multiplication 2
    POP  1,0      # return

This assembles to:

rbit:
    E0010102 # SETH $1,#0102
    E9010408 # ORMH $1,#0408
    EA011020 # ORML $1,#1020
    EB014080 # ORL  $1,#4080
    DC000100 # MOR  $0,$1,$0
    DC000001 # MOR  $0,$0,$1
    F8010000 # POP  1,0

How does it work?

The MOR instruction performs a matrix multiplication on two 64-bit quantities used as two 8x8 matrices of booleans. A boolean number with digits abcdefghklmnopqr2 is used as a matrix like this:

/ abcd \
| efgh |
| klmn |
\ opqr /

The MOR instruction multiplies the matrices represented by their arguments where multiplication is and and addition is or. It is:

/ 0001 \      / abcd \      / opqr \
| 0010 |  \/  | efgh |  --  | klmn |
| 0100 |  /\  | klmn |  --  | efgh |
\ 1000 /      \ opqr /      \ abcd /

and furthermore:

/ opqr \      / 0001 \      / rqpo \
| klmn |  \/  | 0010 |  --  | nmlk |
| efgh |  /\  | 0100 |  --  | hgfe |
\ abcd /      \ 1000 /      \ dcba /

which is the reverse order of bits of the original number.

32 bit numbers

If you just want the reverse of a 32 bit number instead of a 64 bit number, you can use this modified method:

rbit:
    SETL   $1,#0408 # load first matrix in two steps
    ORML   $1,#0102
    MOR    $1,$1,$0 # apply first matrix
    SLU    $2,$1,32 # compile second matrix
    16ADDU $1,$2,$1
    MOR    $1,$0,$1 # apply second matrix
    POP    1,0      # return

assembled:

rbit:
    E3010408 # SETL   $1,#0408
    EA010102 # ORML   $1,#0102
    DC010001 # MOR    $1,$1,$0
    3B020120 # SLU    $2,$1,32
    2E010201 # 16ADDU $1,$2,$1
    DC010001 # MOR    $1,$0,$1
    F8010000 # POP    1,0

The first matrix multiplication basically works like this:

/ 0000 \      / 0000 \      / 0000 \
| 0000 |  \/  | 0000 |  --  | 0000 |
| 0001 |  /\  | abcd |  --  | efgh |
\ 0010 /      \ efgh /      \ abcd /

the corresponding octabyte is #0000000001020408 which we load in the first two instructions. The second multiplication looks like this:

/ 0000 \      / 0001 \      / 0000 \
| 0000 |  \/  | 0010 |  --  | 0000 |
| efgh |  /\  | 0100 |  --  | hgfe |
\ abcd /      \ 1000 /      \ dcba /

The corresponding octabyte is #0102040810204080 which we create from the first matrix like this:

SLU $2,$1,#32   # $2 = #0102040800000000
16ADDU $1,$2,$1 # $2 = $2 + $1 << 4
                     = $2 + #0000000010204080
                #    = #0102040810204080

The second multiplication is business as usual, the resulting code has the same length (28 bytes).


CJam, 25

L{\_l~(>1<lN+a@+`@"_~"}_~

Try it online

Explanation:

L      push an empty array (this is the array of previous strings)
{…}    push this block
_      duplicate the block
~      execute the 2nd copy (the stack contains the array and the block)

The block:

\      swap the array with the block
_      duplicate the array
l      read a line from the input (containing the integer n)
~(     evaluate n and decrement it
>      slice the array starting at that position
1<     slice the resulting array to keep only the first string (if any)
l      read the 2nd line from the input (containing the string)
N+     append a newline
a      wrap in an array
@      bring the previous array to the top
+      concatenate the arrays, thus prepending the new string
`      convert the array to its string representation
@      bring the block to the top
"_~"   push this string

At the end, the requested string (if any), the array's representation, the block and the string "_~" are printed automatically.


Retina 0.8.2, 25 bytes
0|7
_#
^.{5}\w.{6}\w.{4}$

Try it online! Link includes test cases. Explanation:
0|7
_#

Expand 0 and 7 into two syllables.
^.{5}\w.{6}\w.{4}$

Check that neither the 6th nor the 13th syllable is the second such syllable.


Haskell, 27 26 bytes

([z|k<-[1..],z<-[1..k]]!!)

Try it online!

Thanks @DanD. for -1 byte!

This is an anonymous function, creating the infinite sequence an just returning the n-th element thereof: [[1..k]| k<-[1..]] produces an infinite list of list: [[1],[1,2],[1,2,3],[1,2,3,4],...]. To concatenate these we can write [z|k<-[1..],z<-[1..k]] which results in [1,1,2,1,2,3,1,2,3,4,...] and finally (...!!) accepts the input n (pointless notation) and returns the n-th term (0-based).


Length of Longest Non-Repeating Substring

Jelly, 6 bytes
ẆQƑƇṪL

A monadic link accepting a list of characters (or whatever), which yields the length.
Try it online!
How?
ẆQƑƇṪL - Link: list
Ẇ      - all sublists (ordered by length)
   Ƈ   - filter keep those which are:
  Ƒ    -   invariant under:
 Q     -     deduplication
    Ṫ  - tail
     L - length


Jelly, 3 bytes

Ḣs×

Input is taken as s, n.

Try it online!

How it works

Ḣs×  Main link. Argument: s, n

Ḣ    Head; yield s.
     This pops the list, leaving [n] as the main link's argument.
 s   Split s into chunks of length n.
  ×  Multiply each chunk by [n], repeating its first element n times.


APL (36)

{⍵≡⍬:⍬⋄(∇z/m),p,∇m/⍨~z←(p←⊃⍵)≥m←1↓⍵}

It's quicksort:

⍵≡⍬: if the list is equal to the empty list
:⍬: then return the empty list
⋄: otherwise:

m←1↓⍵: m is the list minus its first element
p←⊃⍵: p (pivot) is the first element
z←(p←⊃⍵)≥m: z is a bitmask of those values of m that are smaller than p.
∇m/⍨~z select the inverse of z from m (= larger numbers) , and sort it recursively
p,: pivot
∇z/m: select z from m (= smaller or equal numbers) and sort it recursively


Minimize Least Used Binary Bits in Fractions

Node.js, Score = 7873
This is both naive and rather long...

Code size = 129 bytes
Total penalty = 2336
Score = round(1291/4 * 2336) = 7873

Takes input as [p, q]. Returns [p', q', f(p, q)].

f=(a,r=[k=6e3])=>k--?f(a,(i=Math.max(...a.map(n=>(g=n=>n?g(n>>1,n&1?++o:++z):o<z?o:z)(a=(p=a,n*k),o=z=0))))>r[2]?r:[p,a,i],k--):r

Try it online! for the test cases
or compute the total penalty by processing the whole test set

Alternate version, Score = 8426
A modified version to reach a total penalty of 2330. But it's not worth it...

Code size = 171 bytes
Total penalty = 2330
Score = round(1711/4 * 2330) = 8426

Same I/O format as the main version.
f=(a,r=[k=5e3])=>k--?f(a,(i=Math.max(...a.map(n=>(g=n=>n?g(n>>1,n&1?++o:++z):o<z?o:z)(a=(p=a,n*([7007,7901,16239,32695,130527,261599][k]||k-5)),o=z=0))))>r[2]?r:[p,a,i]):r

Try it online!
It includes some hardcoded values for the highest multipliers. They were found by generating all bitmasks m with up to 32 bits and no more than 5 0's, keeping the values for which m mod p = 0, checking the score of q * m / p and finally doing the same operation with the inverted bitmask of m of the same length (no more than 5 1's with all other bits set to 0).


GolfScript, 4 characters

{+}*

Simply uses the fold operator (*) to add up all the characters.

If it has to work with the empty string, 9 chars:

{{+}*}0if

Thanks to @PeterTaylor for providing an alternative 6-char version that works with empty string:

0\{+}/


Bash

An actual pokémon? Ok. I present the Voltorb, seen from behind.

#!/bin/bash
echo -e '\e[31m'    # escape character for red font
s=6
for i in `seq 8 2 16`; do
    if [ $i -ne 10 ]; then
        for j in `seq $s`; do
            echo -n ' '
        done
        for j in `seq $i`; do
            echo -n '#'
        done
        echo
    fi
    s=`expr $s - 1`
done
echo -e -n '\e[97m'    # escape character for white font
s=2
for i in `seq 16 -2 8`; do
    if [ $i -ne 10 ]; then
        for j in `seq $s`; do
            echo -n ' '
        done
        for j in `seq $i`; do
            echo -n '#'
        done
        echo
    fi
    s=`expr $s + 1`
done
echo -e '\e[0m'    # escape character for default font color

Output:


How many IP addresses are in a given range?

GolfScript, 20 bytes

~]7/${2%256base}/)\-

Try it online.

Test cases

$ echo 0.0.0.0 255.255.255.255 | golfscript range.gs
4294967296
$ echo 255.255.255.255 0.0.0.0 | golfscript test.gs
4294967296
$ echo 1.2.3.4 1.2.3.4 | golfscript test.gs
1
$ echo 56.57.58.59 60.61.62.63 | golfscript test.gs
67372037

How it works

~]        # Evaluate and collect into an array.
          #
          # “.” duplicates, so for "5.6.7.8 1.2.3.4", this leaves
          # [ 5 5 6 6 7 7 8 1 1 2 2 3 3 4 ] on the stack.
          #
7/        # Split into chunks of length 7: [ [ 5 5 6 6 7 7 8 ] [ 1 1 2 2 3 3 4 ] ]
$         # Sort the array of arrays: [ [ 1 1 2 2 3 3 4 ] [ 5 5 6 6 7 7 8 ] ]
{         # For each array:
  2%      # Extract every second element. Example: [ 1 2 3 4 ]
  256base # Convert the IP into an integer by considering it a base 256 number.
}/        #
)         # Add 1 to the second integer.
\-        # Swap and subtract. Since the integers were sorted, the result is positive.


05AB1E, 13 12 bytes

[¼DSO‰0Kθ©#®

Try it online!

Explanation

[               # start loop
 ¼              # increment counter
  D             # duplicate current value
   SO           # sum the digits in the copy
     ‰          # divmod the current value by its digit-sum
      0K        # remove 0 from the resulting list
        θ       # pop the last element
         ©      # store a copy in register
          #     # if the current value is 1, break
           ®    # push the copy from register
                # implicitly output counter


Generate ordered binary combinations without repetitions


Pyth, 10 bytes

!uscG`T.BQ

Try this test suite in the Pyth Compiler.

How it works

              (implicit) Store the evaluated input in Q.
       .BQ    Return the binary string representation of Q.
 u            Reduce w/base case; set G to .BQ and begin a loop:
     `T         Return str(10) = "10".
   cG           Split G (looping variable) at occurrences of "10".
  s             Join the pieces without separators.
              Set G to the returned string.
              If the value of G changed, repeat the loop.
              This will eventually result in either an empty string or a
              non-empty string without occurrences of "10".
!             Return (and print) the logical NOT of the resulting string.


Traverse all numbers with only one bit flip per step

Python 3:

for i in range(2**n):i^i//2

(Doh. Overlooked that this solutions is already known. Would delete it if stackexchange allowed it)


JavaScript (ES6), 147 bytes

s=>s.replace(/./g,c=>(q=p,p="AHOVBIPWCJQXDKRYELSZFMY.GNU ".indexOf(c),"<<<>>>".substring(3,((p>>2)+10-(q>>2))%7)+["","v","vv","^"][p-q&3]+"."),p=0)

An interesting behaviour of substring is that it exchanges the arguments if the second is less than the first. This means that if I calculate the optimal number of left/right presses as a number between -3 and 3, I can add 3, and take the substring of <<<>>> starting at 3 and I will get the correct number of arrows. Meanwhile the down/up presses are simply handled by looking up an array using a bitwise and of the difference in rows with 3; this way is slightly shorter as there are fewer array elements.


Here's my first ever shot at code golf:

Python 3, 167 bytes

167 bytes if tabs or single spaces are used for indentation

def f(n):
 B=bin(n)[2:];L=len(B);M=L//2
 if'1'*L==B:return 1
 S=str(int(B[:M])+int(B[:-M-1:-1]))
 return 0if(~L%2==0and'0'==B[M])or'2'in S else{S}=={'1'}or f(int(S,2))

Edit: Thanks to everyone's help below, the code above has been reduced from an original size of 232 bytes!


A long long time ago, in a galaxy ... right here


ES6, 83 81 bytes

x=>(e=s=>s.replace(/e\+?/,'x10^'),z=e(x.toExponential()),y=e(''+x))[z.length]?z:y

Probably fails for some edge cases where toString insists on exponential format.

Edit: Saved 2 bytes thanks to @user81655.


Python 184 bytes

from random import*
h,s,v=random()*6,.5,243.2
for i in range(input()):
 h+=3.708;print'#'+'%02x'*3%((v,v-v*s*abs(1-h%2),v-v*s)*3)[5**int(h)/3%3::int(h)%2+1][:3]
 if i%5/4:s+=.1;v-=51.2

The HSV ⇒ RGB conversion is taken directly from wikipedia.

A few implementation notes.

h is defined as its proper value times 6, which simplifies region determination.
v is defined as its proper value times 256, which propagates through to all three RGB values.
6/Φ  (approximately ~3.708) is used instead of 1/Φ, in agreement with the scaling of h. Similarly, the decrement value for v is also scaled by 256.
The bit of magic
((v,v-v*s*abs(1-h%2),v-v*s)*3)[5**int(h)/3%3::int(h)%2+1][:3]
is logically equivalent to
c=v*s;m=v-c;x=c-c*abs(1-h%2)+m;c+=m;[(c,x,m),(x,c,m),(m,c,x),(m,x,c),(x,m,c),(c,m,x)][int(h)%6]

Sample usage:

$ echo 3 | python color-set.py
#f37994
#79b8f3
#dbf379

$ echo 8 | python color-set.py
#d2f379
#f079f3
#79f3cc
#f3a979
#8579f3
#62c04c
#c04c84
#4ca6c0

$ echo 15 | python color-set.py
#7984f3
#a8f379
#f379cb
#79eff3
#f3d379
#804cc0
#4cc05e
#c04c5c
#4c7dc0
#9fc04c
#8b2a8c
#2a8c6f
#8c522a
#352a8c
#3b8c2a

A visualization of the values for n = 15:

and the corresponding html.


Ruby, 589 512 510 499 493 characters
R=0..7
a=->b{o=[];R.map{|r|R.map{|c|v=Hash[?K,[6,7,8,11,13,16,17,18],?R,s=[157,161,163,167],?B,t=[156,158,166,168],?Q,s+t,?N,[1,3,5,9,15,19,21,23],?P,[32,181,183]][z=b[r][c]];v&&v.map{|s|k=2!=l=s/25+1;u=r;v=c;l.times{u+=s/5%5-2;v+=s%5-2;R===u&&R===v||break;t=b[u][v];j=t<?.&&l<8;(j||t=~/[a-z]/&&k)&&o<<=(h=b.map &:swapcase;h[u][v]=h[r][c];h[r][c]=?-;[z+"%c%d"%[97+v,8-u],h.reverse]);j&&(k||r==6)||break}}}};o}
a[$<.map{|l|l}].map{|m,b|a[b].any?{|f,x|a[x].all?{|g,y|y*""=~/K/}}||$><<m[/[^P]+/]}

Input is given via stdin, e.g.:
> ruby mateinone.rb
--------
--------
--------
-k------
b-------
-N-P----
--------
-----K-Q
^Z
Qb7

The output is not just one move that forces a mate in one but every move that does so.
Edit 1: The function e was used only once so I inlined it. Second, the encoding now is based on number 5 instead of 10. And refactoring the cloning of the board saved quite a few chars.
Edit 2: Still not as much improvement as I wanted. Changing the hash from {a=>b,c=>d} to Hash[a,b,c,d]. This costs 4 characters but saves one per key-value pair.
Edit 3: Only minor reductions: inlining M (4 characters), t==?- -> t<?. (2), removing Pawn in algebraic notation at the end (2), replaced puts (3). The program is now less than 500 characters.
Edit 4: It is interesting how much one can still find in such a program. Moved an invariant outside the loop and found another duplicate calculation.


C – 584 bytes
Non-competing (obviously), but to serve as inspiration:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
char*f(int z){static char r[8];char*l[]={"","I","II","III","IV","V","VI","VII","VIII","IX"},*h[]={"","X","XX","XXX","XL","L"};if(!z)return"N";sprintf(r,"%s%s",h[z/10],l[z%10]);return r;}int main(int c,char**v){char*s="";int i,j,z[10],k=60;long x;double d,y;y=modf(atof(v[1]),&d);x=d;for(i=4;i>=0;i--){z[i]=x%k;x/=k;}for(i=5;i<=9;i++){z[i]=(y*=k);y-=z[i];}for(i=0;!z[i]&&i<4;i++);for(;i<5;i++){printf("%s%s",s,f(z[i]));s="*";}for(j=9;!z[j]&&j>=i;j--);if(i<=j)printf("*E");for(;i<=j;i++)printf("*%s",f(z[i]));printf("\n");return 0;}

Save as fs.c, build with gcc -o fs fs.c -lm, and run as ./fs <arg>.
Test cases:
$ ./fs 0
N
$ ./fs 1
I
$ ./fs 60
I*N
$ ./fs 0.1
N*E*VI
$ ./fs 3600
I*N*N
$ ./fs 10.5
X*E*XXX
$ ./fs 16777215
I*XVII*XL*XX*XV
$ ./fs 3.1415926536
III*E*VIII*XXIX*XLIV*N*XLVII

Largest mantissa and fraction:
$ ./fs 777599999
LIX*LIX*LIX*LIX*LIX
$ ./fs 0.999999998713992
N*E*LIX*LIX*LIX*LIX*LIX

I'm using double as the working type, so the largest mantissa and fraction combined exceeds the native accuracy of that type. If I used long double instead it could handle it.


AutoHotKey, 7 bytes

a::vk14

// Is this valid? This really do what OP want -- replace a by CapsLock (vk14).

Run this program, and type the input from keyboard..


Python 3, 109 99 104 101 bytes

This is a simple answer that uses complex numbers, with input as a space-separated string or a newline-separated string. Golfing suggestions welcome!

Edit: -13 bytes thanks to Labo. +5 bytes for converting to an int.

d=p=0
for r in input().split():d+=1-2*(r<'R');p+=1j**d*int(r[1:])
print(int(abs(p.real)+abs(p.imag)))

Ungolfing

def manhattan_rotation(seq, nsew=0, pos = 0):
    for rot in seq.split():
        # change direction
        if rot[0] == "L":
            nsew += -1
        else:
            nsew += 1
        # move in that direction rot[1:] times
        pos += 1j ** nsew * int(rot[1:])
    return int(abs(pos.real)+abs(pos.imag))


Python 2, 62 61 bytes

lambda s:eval(re.sub('(\d*)(.)',r'+1*\1*1*"\2"',s))
import re

Try it online!

The regex substitution expands 3<2+- into the string:

+1*3*1*"<"+1*2*1*"+"+1**1*"-"

which is then evaled. (Note how when \1 is empty, we get 1**1 = 1.) The first + is a unary operator which binds to the first number, and the other +s are string concatenation. This beats the more obvious

lambda s:re.sub('(\d+)(.)',lambda m:int(m.group(1))*m.group(2),s)
import re

by 14 bytes. Ordinarily "\2" wouldn’t always work, but thankfully \ and " aren’t brainfuck commands.

xnor saved a byte, supplying the 1*\1*1 trick. Previously I had \1L in the regex, and defined L=1 as a lambda argument, which is also pretty cool: 3L is a long int literal and L is a variable.


JavaScript (ES6),  202 194 187  183 bytes
Takes input as a matrix with \$2\$ for red, \$4\$ for yellow and \$0\$ for empty. Returns a string of 0-indexed moves (or an empty string if there's no solution). Reds start the game.

m=>(p=[...'5555555'],g=(c,s=o='')=>/2|4/.test(m)?['',0,2,4].some(n=>m.join``.match(`(1|3)(.{1${n}}\\1){3}`))?o:p.map((y,x)=>m[m[y][x]--^c||p[g(c^6,s+x,p[x]--),x]++,y][x]++)&&o:o=s)(2)

Try it online!
How?
The recursive function \$g\$ attempts to replace all \$2\$'s and \$4\$'s in the input matrix with \$1\$'s and \$3\$'s respectively.
While doing so, it makes sure that we don't have any run of four consecutive odd values until all even values have disappeared (i.e. if a side wins, it must be the last move).
The row \$y\$ of the next available slot for each column \$x\$ is stored in \$p[x]\$.
Commented
m => (                            // m[] = input matrix
  p = [...'5555555'],             // p[] = next row for each column
  g = (c,                         // g = recursive function taking c = color,
          s = o = '') =>          //     s = current solution, o = final output
    /2|4/.test(m) ?               // if the matrix still contains at least a 2 or a 4:
      ['', 0, 2, 4]               //   see if we have four consecutive 1's or 3's
      .some(n =>                  //   by testing the four possible directions
        m.join``                  //   on the joined matrix, using
        .match(                   //   a regular expression where the number of characters
          `(1|3)(.{1${n}}\\1){3}` //   between each occurrence is either 1, 10, 12 or 14
        )                         //   (horizontal, diagonal, vertical, anti-diagonal)
      ) ?                         //   if we have a match:
        o                         //     abort and just return the current value of o
      :                           //   else:
        p.map((y, x) =>           //     for each cell at (x, y = p[x]):
          m[                      //
            m[y][x]--             //       decrement the value of the cell
            ^ c ||                //       compare the original value with c
            p[                    //       if they're equal:
              g(                  //         do a recursive call with:
                c ^ 6,            //           the other color
                s + x,            //           the updated solution
                p[x]--            //           the updated row for this column
              ),                  //         end of recursive call
              x                   //         then:
            ]++,                  //         restore p[x]
            y                     //         and restore m[y][x]
          ][x]++                  //         to their initial values
        ) && o                    //     end of map(); yield o
    :                             // else:
      o = s                       //   we've found a solution: copy s to o
)(2)                              // initial call to g() with c = 2


I got more than enough answers without reversing both abs calls, so I skipped that.  They'd be trivial to add back if really needed.  I'm not even taking long overflow into account, but that'd let you insert most any word you like in the greater hashes.  As if that was needed to get collisions.

import Data.Char
import Data.Bits
import Control.Monad

printables = [32..95]

reverseModShift11 x = do
  let zeros = head $ filter (testBit x) [0..]
  b <- [0 .. zeros]
  let h = x `shiftR` b
  guard $ (h `mod` 11) == (fromIntegral b)
  return h

reverseBase p m n | m < 13    = []
                  | n <  0    = []
                  | n == 0 && m == 13 = return p
                  | otherwise = do
  let r = n `mod` m
  c <- filter (\x -> x `mod` m == r) printables
  reverseBase (chr c:p) (m-1) ((n-c) `div` m)

reverseBases = join . ap (map (reverseBase "") [14..29]) . return

breakHash = reverseModShift11 >=> reverseBases

Sample use:

*Main> breakHash 224443104
["]#'!'","\\2'!'","[A'!'","ZP'!'","Y_'!'",
  (...)
"[?EAK","ZNEAK","Y]EAK",
  (...)
"] TQ]","\\/TQ]","[>TQ]","ZMTQ]","Y\\TQ]"]


Vigil
Finally a usecase for Vigil!
def main():
  raise Exception()

Excerpt from the "language specification":

It goes without saying that any function that throws an exception which isn't caught is wrong and must be punished.
...
If an oath is broken, the offending function [...] will be duly punished.
How?
Simple: it will be deleted from your source code.
The only way to ensure your program meets its requirements to absolutely forbid code that fails to do so. With Vigil, it will do this for you automatically.

There are other ways to do this, because Vigil provides the keywords implore and swear which are basically oaths to adhere to certain pre- and post-conditions:
def main():
  swear 0 > 1


Write the implementation to pass this test

Ummm, simply provide an implementation of AssertTrue that doesn't throw anything?

void addOne(int a){}

void AssertTrue(bool b) { }

You never specified what testing framework is used here. It looks like MSTest, but I fired up a new test project and AssertTrue doesn't exist, so I took the liberty of implementing it myself.

EDIT

This solution might be what you were fishing for:

void addOne(int x)
{
  unsafe
  {
    int* i = &x;
    i += 4;
    *i += 1;
  }
}

I feels pretty fragile, but it works on my box consistently. It probably depends heavily on the compiler, so hopefully it is reproducible elsewhere.


Regex in reverse - decompose regular expressions

Python v2.7 1069 1036 950 925 897 884 871 833 822

This answer seems rather long for a code golf, but there are a lot operators that need to be handled and I know what purpose each byte in this answer does. Since there is no existing answer I submit this as a target for other users to beat. See if you can make a shorter answer :).

The two main functions are f which parses the regex starting at the ith character, and d which generates the matching strings, using r the sub-regexes we can recursed into, 'a' the array representing the part of the current sub-regex not yet processed, and a string suffix s which represents the part of the string generated so far.

Also check out the sample output and a test harness.

import sys;V=sys.argv;n=int(V[2]);r=V[1];S=len;R=range;C=R(32,127)
Z=[];z=-1;D='d(r,p,';F='for j in '
def f(i,a):
 if i>=S(r):return a,i
 c=r[i];x=0;I="|)]".find(c)
 if c in"([|":x,i=f(i+1,Z)
 if I+1:return([c,a,x],[a],[c,a])[I],i
 if'\\'==c:i+=1;x=c+r[i]
 return f(i+1,a+[x or c])
def d(r,a,s):
 if S(s)>n:return
 while a==Z:
        if r==Z:print s;return
        a=r[z];r=r[:z]
 e=a[z];p=a[0:z]
 if'|'==a[0]:d(r,a[1],s);d(r,a[2],s)
 elif']'==a[0]:
        g=a[1];N=g[0]=='^';g=(g,g[1:])[N];B=[0]*127;O=[ord(c[z])for c in g]
        for i in R(0,S(g)):
         if'-'==g[i]:exec F+'R(O[i-1],O[i+1]):B[j]=1'
         else:B[O[i]]=1
        for c in C:N^B[c]<1or d(r,Z,chr(c)+s)
 elif' '>e:d(r+[p],e,s)
 else:c=p[:z];exec{'.':F+'C:'+D+'chr(j)+s)','?':D+'s);d(r,p[:z],s)','*':F+'R(0,n+1):d(r,c,s);c+=[p[z]]','+':"d(r,p+['*',p[z]],s)"}.get(e,D+'e[z]+s)')
d(Z,f(0,Z)[0],"")

Note that tabs in the original solution have been expanded. To count the number of characters in the original use unexpand < regex.py | wc.


Pyth, 60 57 58 bytes

.[K`.Rchu,eGsGQjT7e.ftPZQ)Je/u+/*GHhyHy^TQr^T3ZZT\0+xK\.hJ

Test harness

It's pretty straightforward - calculate pi, the fibonacci series and the composites, round to C(n) digits, pad to C(n) digits plus the location of the decimal point digits, done.

A(n): hu,eGsGQjT7

B(n): e.ftPZQ)

C(n): e/u+/*GHhyHy^TQr99ZZT

60 -> 57: Cleaned up the n = 1 special case in the pi calculation.

57 -> 58: Wasn't using high enough precsion for pi for the entire input range - increased 99 iterations to 1000 iterations.

Note on rounding: This uses Python's "nearest even" rounding system, rather than the OP specified "towards infinity" system. However, the difference only matters if the digits immediately following the rounding point are 5000..., e.g. 1.25 rounded to 1 digit. I checked the input range, and this never happens, so the correct result is alway returned.


R, 50 37 bytes

-33 bytes thanks to digEmAll! -13 bytes thanks to rturnbull!

x=scan(se=",");if(any(diff(x)))max(x)

Try it online!


C

Didn't bother counting, but here's a fun example:

f(n){return n<4?1:f(--n)+f(--n);}
main(a,b){for(scanf("%d",&b);a++<=b;printf("%d ",f(a)));}

Proof it works.

I'm quite proud of this: I got bored, so I rearranged my code (with a few small additions) to make it where each line represents a value in the Fibonacci sequence.

                         #                                // 1
                         f                                // 1
                         //                               // 2
                        (n)                               // 3
                       {/**/                              // 5
                      return n                            // 8
                    <2 ? 1:f(--n)                         // 13
                +f(--n); } main(a, b)                     // 21
          {a = 0, b = 0;scanf("%d",&b); for(              // 34
;a < b; a+=1) { int res = f(a); printf("%d ", res); } }   // 55

Proof it works.


Dutch Burgerservicenummer (BSN) eleven-test


C, non-golfed

The idea is to have to pointers p1 and p2 that traverse the list. p2 moves twice as fast as p1. If p2 reaches p1 at some point then there is a loop. Here is the C code (not tested, though).

struct node
{
  void *value;
  struct node *next;
};

int has_loops(struct node *p)
{
  struct node *p1 = p, *p2 = p->next;
  if (!p2) return 0;

  while (p1 != p2) {
    // p1 goes one step
    p1 = p1->next;
    if (!p1) return 0;

    // p2 goes two steps
    p2 = p2->next;
    if (!p2) return 0;
    p2 = p2->next;
    if (!p2) return 0;
  }

  return 1;
}


Python 2, 172 202 bytes

def f(n):
 D=set();A=[];R=randint
 while n:
	n-=1;w,d=R(1,52),R(1,5)
	if R(0,364)>104:D|={(w,d)};A+=[w]*(R(0,2)>1)
 return next((a for a in sorted(A)if[w for w,d in D].count(a)>1),0)
from random import*

Try it online!

oops! Missed a requirement; cost 30 bytes.

It is given by the OP that your birthday is not 29 February.

If your birthday is 30 December, it will not fall in any ISO week of 2019, so in any case you cannot be a Very Angry ISO week of 2019.

That leaves 364 other birthdays to consider you being Very Angry about. 104 of these fall on weekends when we have stipulated that you won't get Very Angry about it. So we only care about you 260/365 of the time; i.e., when R(0,364)>104 (randint's range is inclusive). Given that constraint, it is equiprobable that your weekday birthday falls in any of the 52 ISO weeks of 2019, and any weekday of that week; and, independently, that you are 1 in 3 likely to be a Very Angry person.

D is then a set of (weeknum,weekday) so that if a potentially Angry person shares an actual birthday, then there's no need to be Amgry unless there's yet another person having a birthday that week.

0 is returned if no Very Angry people manifest during any ISO 2019 week; otherwise, the ISO week number of the earliest meltdown is returned.


Longest non-repeating Game-of-Life sequence

C++ up to N=6

3x3 answer 3: 111 000 000
4x4 answer 10: 1110 0010 1100 0000
5x5 answer 52: 11010 10000 11011 10100 00000
6x6 answer 91: 100011 010100 110011 110100 101000 100000

This technique is centered around a fast next state function.  Each board is represented as a bitmask of N^2 bits, and bit-twiddly tricks are used to compute the next state for all cells at once.  next compiles down to about 200 100 assembly instructions for N <= 8.  Then we just do the standard try-all-states-until-they-repeat and pick the longest one.

Takes a few seconds up to 5x5, a few hours for 6x6.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

#define N 6

typedef uint64_t board;

// board is N bits by N bits, with indexes like this (N=4):
//  0  1  2  3
//  4  5  6  7
//  8  9 10 11
// 12 13 14 15

#if N==3
#define LEFT_COL (1 + (1<<3) + (1<<6))
#define RIGHT_COL ((1<<2) + (1<<5) + (1<<8))
#define ALL 0x1ffULL
#elif N==4
#define LEFT_COL 0x1111ULL
#define RIGHT_COL 0x8888ULL
#define ALL 0xffffULL
#elif N==5
#define LEFT_COL (1ULL + (1<<5) + (1<<10) + (1<<15) + (1<<20))
#define RIGHT_COL ((1ULL<<4) + (1<<9) + (1<<14) + (1<<19) + (1<<24))
#define ALL 0x1ffffffULL
#elif N==6
#define LEFT_COL (1 + (1<<6) + (1<<12) + (1<<18) + (1<<24) + (1ULL<<30))
#define RIGHT_COL ((1<<5) + (1<<11) + (1<<17) + (1<<23) + (1<<29) + (1ULL<<35))
#define ALL 0xfffffffffULL
#else
#error "bad N"
#endif

static inline board north(board b) {
  return (b >> N) + (b << N*N-N);
}
static inline board south(board b) {
  return (b << N) + (b >> N*N-N);
}
static inline board west(board b) {
  return ((b & ~LEFT_COL) >> 1) + ((b & LEFT_COL) << N-1);
}
static inline board east(board b) {
  return ((b & ~RIGHT_COL) << 1) + ((b & RIGHT_COL) >> N-1);
}

board next(board b) {
  board n1 = north(b);
  board n2 = south(b);
  board n3 = west(b);
  board n4 = east(b);
  board n5 = north(n3);
  board n6 = north(n4);
  board n7 = south(n3);
  board n8 = south(n4);

  // add all the bits bitparallel-y to a 2-bit accumulator with overflow
  board a0 = 0;
  board a1 = 0;
  board overflow = 0;
#define ADD(x) overflow |= a0 & a1 & x; a1 ^= a0 & x; a0 ^= x;

  a0 = n1; // no carry yet
  a1 ^= a0 & n2; a0 ^= n2; // no overflow yet
  a1 ^= a0 & n3; a0 ^= n3; // no overflow yet
  ADD(n4);
  ADD(n5);
  ADD(n6);
  ADD(n7);
  ADD(n8);
  return (a1 & (b | a0)) & ~overflow & ALL;
}
void print(board b) {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      printf("%d", (int)(b >> i*N+j & 1));
    }
    printf(" ");
  }
  if (b >> N*N) printf("*");
  printf("\n");
}

int main(int argc, char *argv[]) {
  // Somewhere in the starting pattern there are a 1 and 0 together.  Using translational
  // and rotational symmetry, we can put these in the first two bits.  So we need only consider
  // 1 mod 4 boards.

  board steps[10000];
  int maxsteps = -1;
  for (board b = 1; b < 1ULL << N*N; b += 4) {
    int nsteps = 0;
    board x = b;
    while (true) {
      int repeat = steps + nsteps - find(steps, steps + nsteps, x);
      if (repeat > 0) {
        if (repeat == 1 && nsteps > maxsteps) {
          printf("%d: ", nsteps);
          print(b);
          maxsteps = nsteps;
        }
        break;
      }
      steps[nsteps++] = x;
      x = next(x);
    }
  }
}


rot13 (1)

i'm surprised nobody came up with this before :)

Y

and as a bonus, a very simple perl solution

Perl (252)

s//LoremIpsumDolorSitAmet,ConsectetuerAdipiscingElit,SedDiamNonummyNibhEuismodTinciduntUtLaoreetDoloreMagnaAliquamEratVolutpat. UtWisiEnimAdMinimVeniam,QuisNostrudExerciTationUllamcorperSuscipitLobortisNislUtAliquipExE/;s,([^ ])([A-Z]),$1$"\l$2,g;print


Generate lists in which every sublist has a unique element

GolfScript (20 18 chars)

{,{.)^2base,}%}:f;

This is a simple binary ruler function, A001511.

Equivalently

{,{).~)&2base,}%}:f;
{,{~.~)&2base,}%}:f;
{,{).(~&2base,}%}:f;
{,{{1&}{2/}/,)}%}:f;

Thanks for primo for saving 2 chars.


Python 2, 81 bytes

t=[]
i=65
for c in input():t+=[' ']*26;t[ord(c)-i]=c;i-=1
print`t`[2::5].rstrip()

Try it online!


Descending dungeons of positional systems

Jelly, 9 bytes
Ż+⁵ṚDḅ¥@/

A monadic Link accepting a non-negative integer which yields a non-negative integer.
Try it online! Or see the test-suite.
How?
Ż+⁵ṚDḅ¥@/                  e.g. 5
Ż         - zero-range          [0,1,2,3,4,5]
  ⁵       - ten                 10
 +        - add                 [10,11,12,13,14,15]
   Ṛ      - reverse             [15,14,13,12,11,10]
        / - reduce by:          f(f(f(f(f(15,14),13),12),11),10)
       @  -   using swapped arguments:         e.g. f(y=15,x=14)
      ɗ   -     last two links as a dyad
    D     -       decimal (x)                       [1,4]
     ḅ    -       convert (that) from base (y)      19
                           i.e. f(f(f(f(f(15,14),13),12),11),10)
                              = f(f(f(f(19,13),12),11),10)
                              = f(f(f(22,12),11),10)
                              = f(f(24,11),10)
                              = f(25,10)
                              = 25


The Programming Language Quiz, Mark II - Robbers


Python (output-length: 18 or 19, mean 18.80)

#list of the 24 possible words
Lbase = ['GTAC','GTCA','GATC','GACT','GCTA','GCAT','TGAC',\
'TGCA','TAGC','TACG','TCGA','TCAG','AGTC','AGCT','ATGC',\
'ATCG','ACGT','ACTG','CGTA','CGAT','CTGA','CTAG','CAGT','CATG']

#base-64 alphabet (used only in the output string-representation)
alph = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/'

#change a bijective list-representation base from b to newb
def chg_bij_base(L, b, newb):
    n = sum([L[i]*b**i for i in range(len(L))])
    L = []
    while n > 0:
        L.append(1+(n-1)%newb)
        n = (n-1)//newb
    return L

#convert a bijective list-repr. to base-64 string-repr.
def list_to_str(Lin):
    L24 = [Lbase.index(w)+1 for w in Lin]
    L64 = chg_bij_base(L24,24,64)
    return ''.join([alph[i-1] for i in L64])

#convert a base-64 string to the corresponding base-64 list-repr.
def str_to_list(s):
    L64 = [alph.index(c)+1 for c in s]
    L24 = chg_bij_base(L64,64,24)
    return [Lbase[i-1] for i in L24]

Test run:

Lin = ["GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT"]

#convert input list to a base-64 string
lts = list_to_str(Lin)

#convert the base-64 str back to the list
stl = str_to_list(lts)

print(len(lts))
print(lts)
print(stl == Lin)

Test output:

18
acFZIBuiiZJ+dwUn2V
True

This uses bijective numeration (which has no 0 digit) to get invertibility.

NB: When using base-64 with this method, all output strings for the above problem are either 18 or 19 characters. (A million random inputs gave an average of 18.80.) The same method works with other bases:

base         output-length
---------    -------------
56 - 58      19
59 - 69      18 or 19
70 - 73      18
74 - 88      17 or 18
89 - 96      17
...          ...
233 - 256    14


Python 2, 117 Bytes

def f(h,v):r="+"+"+".join("-"*i for i in h)+"+\n";print r+r.join(("|"+"|".join(" "*i for i in h)+"|\n")*i for i in v)+r

Try it on ideone.

Not expecting too much from this. Really simple, just uses python joins and string multiplication to pull everything together.


BBC Basic, 207 bytes

BBC Basic allows you to abbreviate keywords by ending them with a period (e.g., PRINT ↠ PRI., REPEAT ↠ REP.). I should really be using a named procedure here instead of a function declaration, but abbreviating DEF PROC_whatever to DEF PRO. just isn't going to work.

The rules make it impossible to use an IF statement, so instead I'm calculating the target line of a GOTO statement based on the result of a comparison. (In BBC Basic, true has a value of –1, so 101-ZIP is equal to 102 if ZIP is true, and 101 otherwise.)

The last line (103=000) ends the function definition and returns a value of zero.

Tested on BeebEm3. Lines 10–60 are excluded from the byte count.

10 READ X,N : IF X=0 THEN END
20 PRINT "x=";X;", n=";N
30 A = FNX(X,N)
40 GOTO 10
50 DATA 5,1,8,1,23,1,15,2,111,2,819,3,0,0
60 REM -------------------
100 DEF FNX(FOO,BAR)BAZ=004:REP.BAT=000:QUX=FOO:REP.XXD=QUX MOD BAZ:ZAP=XXD=003:BAT=BAT-ZAP:QUX=QUX-XXD:QUX=QUX/BAZ:UNT.QUX=000:ZIP=BAT<BAR:ZIP=101-ZIP:GOT.ZIP
101 PRI.BAZ
102 BAZ=BAZ+001:UNT.BAZ=FOO
103=000


Mathematica, 197 193 chars
Brute force.
Min[Length/@Select[Join[{1},#,{n},Reverse@#2]&@@@Tuples[Subsets@Range[3,n=Length[i=FromDigits/@StringSplit@InputString[]]]-1,2],{}⋃#==Sort@#∧And@@Thread[i[[#]]≥Abs[#-Rest@#~Append~1]]&]]/.∞->-1