Julia, 97 chars

s(k)=while any([k[j]>k[j-1]||j>6&&k[j]>k[j-6] for j=2:36]);i,j=rand(1:36,2);k[[i,j]]=k[[j,i]];end

Checks if the array is in an acceptable final state state, if not, randomly flips two entries. It's super slow, which I find highly amusing. Does an in place alteration on the input array k. InterferesWith is implemented as >.

As I said, it's really slow.  I tested it with more frequencies and smaller boards with 3 frequencies, but it hasn't returned in over 30 mins on the actual problem. I suspect that it won't return overnight, but I'll update if it does. Update: Yes it did finish in less than 12 hours, and yielded an answer that I added to the gist.

Gist with commented code, and includes 3x3 test case that finishes fast: https://gist.github.com/ggggggggg/8679916


05AB1E, 60 59 bytes
„:;S¡D€gÆI„()SkàĀ-dUv">)]|"')NXQ×K©.ºDysÃk®g<-X·<*yĀ*}I';åO

Try it online or verify all test cases.
Explanation:

„:;S              # Push string ":;", and convert it to a list of characters: [":",";"]
    ¡             # Split the (implicit) input-string on these characters
     D            # Duplicate the pair
      €g          # Get the length of each part
        Æ         # Reduce by subtracting
I                 # Push the input again
 „()S             # Push string "()", and convert it to a list of characters: ["(",")"]
     k            # Get the 0-based index of these characters in the string
                  # (or -1 if it isn't present)
      à           # Pop and push the maximum
       Ā          # Check that this is NOT 0 (0 if 0; 1 if -1, 1, 2, or 3)
-                 # Subtract the two from one another
 d                # Check that this is non-negative (>=0)
  U               # And pop and store this result in variable `X`
                  # (X=1 for faces where the mouth is left; X=0 for faces where the
                  # mouth is right or where we couldn't determine mouth/eyebrows)
v                 # Loop over the parts `y` in the pair we duplicated after the split:
 ">)]|"           #  Push string ">)]|"
         N        #  Push the 0-based loop-index
          XQ      #  Check if it's equal to variable `X` (1 if N==X, 0 if N!=X)
       ')   ×    '#  Repeat ")" that many times (")" if N==X, "" if N!=X)
             K    #  Remove that from string ">)]|"
              ©   #  Store this string in variable `®` (without popping)
               .º #  Mirror it with overlap: ">)]|"→">)]|[(<" or ">]|"→">]|[<"
 D                #  Duplicate this mirrored string
  y               #  Push the current part
   s              #  Swap so the copy of the mirrored string is at the top
    Ã             #  Keep only those characters in the part (removes noses "^"/"-")
     k            #  Get the 0-based index of the character in the mirrored string
      ®g          #  Push string `®`, and pop and push its length
        <         #  Decrease it by 1
         -        #  And subtract this from the index
 X                #  Push variable `X`
  ·               #  Double it
   <              #  Decrease it by 1
    *             #  And multiply the top two values
                  #  (negates the current value if X==0, or leaves it as is if X==1)
 y                #  Push the current part again
  Ā               #  Check that it's NOT empty (0 if empty; 1 otherwise)
   *              #  And multiply that as well, so empty parts become 0
}I                # After the loop, push the input again
  ';å            '# Check if it contains a ";" (1 if truthy; 0 if falsey)
O                 # And sum all values on the stack
                  # (after which the result is output implicitly)


Jelly,  12 10 8  7 bytes

-1 thanks to dylnan (use of repeat, ¡, as a replacement of if, ?, saving the need for identity, ¹.)

ḲṚṫ¡€5K

A monadic link taking and returning lists of characters.

Try it online!

How?

ḲṚṫ¡€5K - Link: list of characters
Ḳ       - split at spaces (gets words)
     5  - literal five
    €   - for €ach word:
   ¡    -   repeat:
  ṫ     -   ...number of times: tail (5th character on, if empty falsey->0, else truthy->1)
 Ṛ      -   ...action: reverse
      K - join with spaces

Previous 8: ḲṚ¹ṫ?€5K

Previous 10: ḲµṚ¹ṫ?5µ€K

Previous 12s: ḲµUµL€>4Tµ¦K and ḲµṚ¹L>¥?4µ€K


CJam, 626 397 325 218 168 134 93 55 54 53 bytes

8A#{[_8b3394241224Ab?A0e[A,]ze~__,f#:+s_$@s=*~}%$1>N*

Execution takes roughly four and a half hours on my machine. One Armstrong number is hardcoded, the remaining ones are computed.

Computing all Armstrong numbers is theoretically possible in 24 hours, but the approach

9A#{_9b8 9erA0e[A,]ze~__,f#:+s_$@s=*~}%$1>N*

drives the garbage collector nuts. So far, all settings I've tried resulting either in a GC error message or too much memory consumption.

How it works

8A#              e# Compute 8¹⁰ = 1,073,741,824.
{                e# Map the following block over all I in [0 ... 1,073,741,824].
  [              e#   Begin an array.
    _8b          e#     Copy I and convert the copy to base 8.
    3394241224Ab e#     Push [3 3 9 4 2 4 1 2 2 4], the representation of the
                 e#     Armstrong number 1122763285329372541592822900204593.
    ?            e#     If I is non-zero, select the array of base 8 digits.
                 e#     Otherwise, select the hardcoded representation.
    A0e[         e#     Left-pad the digit array with 0's to length 10.
    A,           e#     Push [0 1 2 3 4 5 6 7 8 9].
  ]              e#   End the array.
  ze~            e#   Transpose and perform run-length decoding, repeating the
                 e#   digit n k times, where k in the n-th entry of the repr.
                 e#   This is a potential Armstrong number, with sorted digits.
  _              e#   Push a copy.
  _,             e#   Compute the length of yet another copy.
  f#             e#   Elevate all digits to that power.
  :+s            e#   Add the results and cast to string.
  _$             e#   Push a sorted copy.
  @s             e#   Stringify the sorted digits.
  =*             e#   Compare for equality and repeat the string that many times.
                 e#   This pushes either the representation of an Armstong number
                 e#   or an empty string.
  ~              e#   Evaluate, pushing the number or doing nothing.
}%               e#
$1>              e# Sort and remove the lowest number (0).
N*               e# Join, separating by linefeeds.


brainfuck, 66 bytes

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

Input is the encrypted string. Assumes infinite sized cells and 0 on EOF.

How it Works:

,[>>>+<[-<+>>-<]<[->+<],] Gets input and the number of characters divided by 2
>[<<,>>[-<+>]<-]<<< Remove the second half of the string (the multiplication part)
[>[-<->>+<]<<] Subtract each character from the previous one, while keeping a copy of the previous one.
>.>>[.>] Print the characters


The shortest way of repeating something is with Seq.fill.

1 to 10 map(_=>println("hi!")) // Wrong!
for(i<-1 to 10)println("hi!") // Wrong!
Seq.fill(10)(println("hi!")) // Right!


80386 machine code, 98

The code:

60 8b f1 8b f9 b0 0a f2 ae 8b ef 2b ee b0 00 f2
ae 2b fe 83 ef 02 2b fd 72 41 03 f7 2b f5 33 c9
8a 7c 6e fc 8a 1c 6e b1 02 33 d2 8b c7 f7 f5 83
fa 02 75 03 b7 00 41 8a 66 fc 8a 06 3b fd 7d 02
33 c0 23 c3 0a c4 22 df 0b c3 f6 44 2e fe 01 74
04 d1 e8 73 06 2b f1 2b f9 73 c5 61 d1 d0 83 e0
01 c3

The code scans the ASCII art from the end to the beginning, jumping 2 characters at a time. This does twice the needed checks (it would be enough to jump 4 characters), but simplifies the logic.

Checking starts at the next-to-last row of characters (no need to check the last line). At each line, it starts 3 characters from the right (no need to check too far to the right). For each character, it checks 4 surrounding characters:

A...B
..X..
C...D

There is a bunch of logical conditions to check:

If A and C are brick characters, X is supported
If B and D are brick characters, X is supported
If C and D are brick characters, X is supported
If X is a brick character, it has to be supported; otherwise the structure is unstable

It's a lucky coincidence that all brick characters [_] have their LSB set; all other characters .\n have it clear. In addition, the 80386 instruction set has these handy "high" and "low" registers (ah, al, etc), which help parallelize the checks a bit. So all the checking amounts to some obscure bit fiddling.

I started from the following C code:

int check(const char* ptr)
{
    int width, result = 0, pos;

    width = strchr(ptr, '\n') - ptr + 1;
    pos = strlen(ptr) - 1 - width; // pos points to the B character
    ptr += pos - width;

    while (pos >= 0)
    {
        int a = ptr[-4];
        int c = ptr[-4 + 2 * width];
        int b = ptr[0];
        int d = ptr[0 + 2 * width];
        int ab = a << 8 | b;
        int cd = c << 8 | d;
        if (pos < width)
            ab = 0; // A and B don't exist; set them to 0
        int jump = 2; // distance to next brick
        if (pos % width == 2) // leftmost brick?
        {
            cd &= 0xff; // C doesn't exist; set it to 0
            ++jump;
        }
        int support_v = ab & cd;
        support_v = support_v | support_v >> 8; // data in LSB
        int support_h = cd & cd >> 8; // data in LSB
        int support = (support_v | support_h) & 1;
        if (!support & ptr[-2 + width])
            goto UNSTABLE;
        ptr -= jump;
        pos -= jump;
    }
    return 1;
UNSTABLE:
    return 0;
}

I translated the code to assembly language (it's mostly one-to-one), including a golfed implementation of strchr and strlen. The following source code is translated by MS Visual Studio to the machine code at the top of my post.

__declspec(naked) int __fastcall check(const char* ptr) // MS Visual Studio syntax
{
    _asm
    {
        pushad;

        // ecx = ptr
        mov esi, ecx; // esi = ptr
        mov edi, ecx
        mov al, 10;
        repne scasb;
        mov ebp, edi;
        sub ebp, esi; // ebp = width

        mov al, 0;
        repne scasb;
        sub edi, esi;
        sub edi, 2;
        sub edi, ebp; // edi = pos
        jc DONE;

        add esi, edi;
        sub esi, ebp;

        xor ecx, ecx; // ecx = jump

    LOOP1:
        mov bh, [esi - 4 + 2 * ebp]; // bh = C
        mov bl, [esi + 2 * ebp]; // bl = D
        // bx = CD
        mov cl, 2;
        xor edx, edx
        mov eax, edi
        div ebp;
        cmp edx, 2;
        jne LABEL2;
        mov bh, 0
        inc ecx;
    LABEL2:

        mov ah, [esi - 4]; // ah = A
        mov al, [esi]; // al = B
        // ax = AB
        cmp edi, ebp;
        jge LABEL3;
        xor eax, eax;
    LABEL3:

        and eax, ebx; // ax = support_v
        or al, ah; // al = support_v
        and bl, bh; // bl = support_h
        or eax, ebx; // eax = support
        test byte ptr[esi - 2 + ebp], 1;
        jz LABEL4; // not a brick character - nothing to check
        shr eax, 1; // shift the LSB into the carry flag
        jnc DONE;
    LABEL4:
        sub esi, ecx;
        sub edi, ecx;
        jnc LOOP1;

    DONE:
        // here, the result is in the carry flag; copy it to eax
        popad;
        rcl eax, 1;
        and eax, 1;
        ret;
    }
}


Code Golf: Mix the nuts so that none of the same kind are touching

GolfScript, 42 41 37 38 characters
~.`{\`{=}+%1-,}+$.,)2//zip[]*.2<..&=*p

The code expects input on STDIN and prints result to STDOUT, e.g.:
> ["walnut" "walnut" "walnut" "macadamia" "pistachio"]
["walnut" "macadamia" "walnut" "pistachio" "walnut"]

> ["walnut" "walnut" "walnut" "macadamia" "walnut"]
[]

The script became longer than expected but I suppose there is room for improvement.
Edit: The case of a list with a single item costs me 1 character (the best comparison I could come up with is the same as Peter's).


Densely packed decimal (DPD) to decimal, with logic gates

45 NANDs (or 43)
45 seems to be the absolute minimum, but it is possible to reach 43 NANDs by a trick: By assuming that the largest numbers are correctly encoded.
888, 889, 898, 899, 988, 989, 998, 999 are to be encoded
with the 2 MSB as 00, requiring just 43 NANDs for decoding.
However, in the specification for decoding, they are specified to be ignored, meaning they can be anything. It is a reasonable assumption that this freer specification could require even fewer gates, but the opposite is true. 45 gates are required for this. This saving could give real benefits for real circuits.
I also found circuits that were significantly more efficient and faster, containing a few more gates.
No pencil drawn image of the circuit this time. Perhaps later.
The circuit is presented in obvious Verilog code, ready for running with test included.
Verilog code:
// Densely packed decimal (DPD) to decimal, circuit in Verilog.
// 45 NANDs only, which seems to be minimal.
//
// By Kim Øyhus 2019 (c) into (CC BY-SA 3.0.)
// This work is licensed under the Creative Commons Attribution 3.0
// Unported License. To view a copy of this license, visit
// https://creativecommons.org/licenses/by-sa/3.0/
//
// This is my entry to win this Programming Puzzle & Code Golf
// at Stack Exchange:
// https://codegolf.stackexchange.com/questions/176557/densely-packed-decimal-dpd-to-decimal-with-logic-gates
//
// TASK:
// 3 decimal digits are stored in 10 bits in the DPD format,
// and this circuit transforms them into 3 decimal digits in
// 4 bits each, BCD format.
//
// 45 gates seem to be the smallest possible NAND circuit there is
// for this task, but I can get even lower by a trick, to 43:
// I assume that the largest numbers are correctly encoded.
//   888, 889, 898, 899, 988, 989, 998, 999 are to be encoded
// with the 2 MSB as 00, requiring just 43 NANDs for decoding.
//
//   However, in the specification for decoding, they are specified
// to be ignored, meaning they can be anything. It is a reasonable
// assumption that this freer specification could require even fewer
// gates, but the opposite is true. 45 gates are required for this.
// This saving could give real benefits for real circuits.
//
//   This DPD format seems to be used a lot for storing decimal numbers
// in computers and IO for ALUs, even though it is stored as 12 bits
// per 3 digits inside the ALUs and for other calculations.
// It is also used in many patents.

module decode1000 ( in_000, in_001, in_002, in_003, in_004, in_005, in_006, in_007, in_008, in_009, out000, out001, out002, out003, out004, out005, out006, out007, out008, out009, out010, out011 );
  input  in_000, in_001, in_002, in_003, in_004, in_005, in_006, in_007, in_008, in_009;
  output out000, out001, out002, out003, out004, out005, out006, out007, out008, out009, out010, out011;
  wire   wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017, wir018, wir019, wir020, wir021, wir022, wir023, wir024, wir025, wir026, wir027, wir028, wir029, wir030, wir031, wir032;

  nand gate000 ( wir000, in_007, in_007 );
  nand gate001 ( wir001, in_003, in_001 );
  nand gate002 ( wir002, in_002, in_003 );
  nand gate003 ( wir003, wir001, in_006 );
  nand gate004 ( wir004, wir002, in_001 );
  nand gate005 ( wir005, wir001, wir001 );
  nand gate006 ( wir006, in_005, in_001 );
  nand gate007 ( wir007, wir006, in_003 );
  nand gate008 ( out008, wir000, wir000 );
  nand gate009 ( wir008, wir004, wir007 );
  nand gate010 ( wir009, wir005, in_006 );
  nand gate011 ( wir010, wir007, wir007 );
  nand gate012 ( wir011, wir009, in_002 );
  nand gate013 ( wir012, wir011, wir009 );
  nand gate014 ( wir013, wir011, wir011 );
  nand gate015 ( wir014, in_008, wir013 );
  nand gate016 ( wir015, in_009, wir013 );
  nand gate017 ( wir016, wir010, wir014 );
  nand gate018 ( wir017, wir014, wir005 );
  nand gate019 ( wir018, wir015, wir015 );
  nand gate020 ( wir019, wir011, wir008 );
  nand gate021 ( wir020, wir019, wir006 );
  nand gate022 ( wir021, wir010, wir018 );
  nand gate023 ( wir022, wir020, wir004 );
  nand gate024 ( wir023, wir016, wir008 );
  nand gate025 ( out001, wir023, wir023 );
  nand gate026 ( out003, wir022, wir022 );
  nand gate027 ( wir024, wir005, wir008 );
  nand gate028 ( wir025, wir012, wir002 );
  nand gate029 ( wir026, wir019, in_003 );
  nand gate030 ( wir027, in_004, in_004 );
  nand gate031 ( out007, wir024, wir009 );
  nand gate032 ( out011, wir026, wir026 );
  nand gate033 ( wir028, wir017, in_005 );
  nand gate034 ( wir029, in_000, in_000 );
  nand gate035 ( wir030, wir026, in_008 );
  nand gate036 ( out005, wir028, wir028 );
  nand gate037 ( out009, wir030, wir030 );
  nand gate038 ( out000, wir029, wir029 );
  nand gate039 ( wir031, wir026, in_009 );
  nand gate040 ( out004, wir027, wir027 );
  nand gate041 ( out010, wir031, wir031 );
  nand gate042 ( wir032, out003, wir018 );
  nand gate043 ( out006, wir003, wir032 );
  nand gate044 ( out002, wir025, wir021 );
endmodule

module test;
   reg  [ 9:0] AB; // input DPD
   wire [11:0] C; // output BCD

  decode1000 U1 (
  .in_000 (AB[ 0]),
  .in_001 (AB[ 1]),
  .in_002 (AB[ 2]),
  .in_003 (AB[ 3]),
  .in_004 (AB[ 4]),
  .in_005 (AB[ 5]),
  .in_006 (AB[ 6]),
  .in_007 (AB[ 7]),
  .in_008 (AB[ 8]),
  .in_009 (AB[ 9]),
  .out000 ( C[ 0]),
  .out001 ( C[ 1]),
  .out002 ( C[ 2]),
  .out003 ( C[ 3]),
  .out004 ( C[ 4]),
  .out005 ( C[ 5]),
  .out006 ( C[ 6]),
  .out007 ( C[ 7]),
  .out008 ( C[ 8]),
  .out009 ( C[ 9]),
  .out010 ( C[10]),
  .out011 ( C[11])
  );

   initial  AB=0;  //unary=0;  binary=0
  always  #1  AB = AB+1;
  initial  begin
    $display("\t\ttime,\tinn 10bit   \tout 3x4bit");
    $monitor("%d,\t%b %b %b\t%b %b %b\t %d%d%d",$time, AB[9:7],AB[6:4],AB[3:0], C[11:8], C[7:4], C[3:0],  C[11:8], C[7:4], C[3:0]);
  end
  initial  #1023  $finish;
endmodule

// How I run and test it:
// iverilog -o decode1000 decode1000.v
// vvp decode1000


CJam, 33 32 20 19 17 bytes

Revised version, with massive support from @Sp3000 and @MartinBüttner:

qN/_z]{:e`z,3<}/|

Try it online

Contributions

@Sp3000 suggested a critical simplification to my original algorithm.
@MartinBüttner applied his mad golfing skills to the revised approach, which almost certainly resulted in shorter code than I would have come up with even after considering the simplification.

Algorithm and Proof

The following explains the criteria for the puzzle sliding apart horizontally. The vertical case can be determined by looking at columns instead of rows, or transposing the character matrix and looking at the rows again.

I'll use the term "stretch" for a maximum sequence of the same letters. For example, the following rows have 1, 2, and 3 stretches respectively:

AAAAAAAA
BBBAAAAA
AABBBAAA

I'll also use the term "interlocked" for a row/puzzle that cannot slide apart.

The key observation is that the puzzle can slide apart if and only if all rows have at most 2 stretches. Or reversed, it is interlocked if and only if there is any row with more than 2 stretches.

The following might not qualify as a strict mathematical proof, but I believe that it makes for a convincing explanation why this has to be the case.

It is easy to see that the puzzle is interlocked if it has rows of more than 2 stretches. Looking at a row with 3 stretches:

BBBAAB

it is clear that it prevents the puzzle from sliding apart because the A stretch is locked between the B stretches. This means that the row is interlocked, which in turn makes the whole puzzle interlocked.

The opposite direction of the proof is not quite as obvious. We need to show that there are no interlocked puzzles where all rows have only 1 or 2 stretches. Starting with a couple of observations:

Rows with only 1 stretch do not contribute to a puzzle being interlocked, since they can slide in either direction without any collisions.
If all rows with 2 stretches have the same order of A and B, the puzzle is clearly not interlocked. In this case, all A cells are left of all B cells, or vice versa, and there are no collisions when sliding the two pieces apart.

The only tricky case would be puzzles where we have rows with 2 stretches of different order. I'm going to show that such puzzles do not exist under the given specifications. To show this, let's look at a partial puzzle that does have this configuration, where . are wildcards:

.......
AAABBBB
.......
BBAAAAA
.......

Now, the specification says that both the A and B cells are simply connected in all valid puzzles. To make the A cells connected in the partial puzzle above, we have two options:

We loop around one of the stretches of B, for example:

..AAAAAA
AAABBBBA
.......A
BBAAAAAA
........

To do this, we unavoidably extend one of the rows to have 3 stretches, so this will never give us a valid puzzle where all rows have at most 2 stretches.
We connect them on a direct path:

.......
AAABBBB
..A....
BBAAAAA
.......

The A cells are now simply connected, and there are still no rows with more than 2 stretches. However, the B cells also need to be simply connected. The direct path is now blocked by the connected A cells, and the only way to connect the B cells is to loop around one of the stretches of A cells. This leads back to case 1, where we can't do that without creating rows of 3 stretches.

To count the stretches, the implementation uses the CJam RLE operator.

Explanation of Code

qN/     Get input and split at newlines.
_z      Make a transposed copy.
]       Wrap the original and transposed puzzle in an array so that we can
        loop over the two.
{       Start of loop over original and transposed puzzle.
  :e`     Apply RLE to all rows.
  z,      Transpose the matrix with the RLE rows, and take the element count of the
          result. Or in other words, take the column count. This will be the length
          of the longest row after RLE.
  3<      Check the length for less than 3.
}/      End of loop over original and transposed puzzle.
|       Or the results of the two.


Build a multiplying machine using NAND logic gates

60 55 50 48 gates

The original (60 gates) was the systematic approach - multiply each digit with each, and then sum them together. Namely, see Wallace trees and Dadda trees

The top half is the multiplication network - multiply each digit with each, and group output digits with the same weight. Some bits have been left inverted to save gates.

The second half is the adder network. Each box represents a single adder - either a half-adder (5 gates - 1x XOR and an inverter), or a full adder (9 gates - 2x XOR and NAND the inverted carry bits). The top are inputs, the bottom output is the sum, the left output is the carry-out.  see the previous challenge

The 2x2 multiplier has then been hand-optimised to a custom-built 13-gate network, which is the optimal size as found by @boothby. Thanks!

Pasting it into the low-bit corner and reoptimising the adder tree saves five gates (see revision #2). Pasting it into the high-bit corner as well, however, produces overlap. A little bit of math tells us, however, that dropping the low-bit of the high multiplier solves the overlap and what's left to do is to add the remaining two bits and sum up stuff.

This alone, unfortunately, does not provide any savings, but it does open two optimisations. First, the two multipliers have two gates in common, and can be fused together. At this point, we're back at 55. Second, in the addition network, we don't need a half-adder because we know its carry will be zero. We can replace it with an OR. An OR is a NAND with its inputs inverted. This produces us with two 2-chains of NOTs on each branch, which can then be removed, for a total saving of five gates. Unfortunately, the half-adder at C16 still carries, so we cannot do the same there. Third, a full adder has a useful property: if you invert its inputs and its outputs, it still behaves the same. Since all its inputs are already inverted, we can just as well move the inverters behind it. Twice. We could have done the same in the original, but... oh well. We still have a half-adder with two inverted inputs. I want optimise this part more, but I doubt I can.

Since we're pulling out a NOT from inside a component, we have to signify that somehow. We have obtained a half-adder with inverted carry (AKA tapped XOR) at a cost of four gates.

In the meantime, we have also redrawn the diagram significantly.


Use the most recent possible java. Java 8 lets you use lambda expressions, so use it if you need anything even like functional objects.
Define shortened functions for things you use a lot. For instance, you have a hundred calls to exampleClassInstance.doSomething(someParameter), define a new function void d(ParameterType p){exampleClassInstance.doSomething(p)} and use it to save yourself some characters.
If you are using a particular long class name more than once, like

MyEventHandlerProxyQueueExecutorServiceCollectionAccessManagerFactory

instead define a new class:

class X extends MyEventHandlerProxyQueueExecutorServiceCollectionAccessManagerFactory{}

If you are only using one particular method of that class (but still need to instantiate it), you can define a shortened version inside the new class at the same time.
Use function type parameters to shorten things, where possible, like this:

<T>void p(T o){System.out.println(o);}

Use for(;;) instead of while(true).
Do not use access modifiers unless absolutely necessary.
Do not use final for anything.
Never put a block after a for loop (but a foreach loop for(x:y) is different). Additional statements should be placed inside the for statement itself, like for(int i=0;i<m;a(i),b(++i))c(i);.
Use inline assignment, incrementation, instantiation. Use anonymous inline classes where appropriate. Use lambdas instead if possible. Nest function calls. Some functions are guaranteed to return their parent object, these ones are actually even meant to be chained together.
Your main method throws Exceptions, not catches them.
Error is shorter than Exception. If for some reason you really need to throw messages up the stack, use an Error, even if it is perfectly normal situation.
If some condition would require immediate termination, use int a=1/0; rather than throw null; or System.exit(0);. At run time, this throws an ArithmeticException.  If you already have a numeric variable in your code, use it instead. (If you already have import static java.lang.System.*;, go with exit(0);.)
Instead of implementing interfaces, like List<E>, extend an immediate (or not-so-immediate, if there is any advantage to doing so at all) child class, like AbstractList<E>, which provides default implementations of most of the methods, and requires only the implementation of a few key pieces.
Write your code out in longhand first, with newlines, indentation, and full variable names. Once you have working code, then you can shorten names, move declarations around, and add shortcut methods. By writing it out long to start, you give yourself more opportunity to simplify the program as a whole.
Compare alternative optimizations to a piece of code, because the most optimal strategy can change dramatically with very small changes to the code. For instance:

If you have only up to two calls to Arrays.sort(a), the most efficient way to is to call it with its fully qualified name, java.util.Arrays.sort(a).
With three or more calls, it is more efficient to instead add a shortcut method void s(int[]a){java.util.Arrays.sort(a);}. This should still use the fully-qualified name in this case. (If you need more than one overload, you are probably doing it wrong.)
However, if your code needs to also copy an array at some point (usually done with a short for loop in golfing, in the absence of an easily-accessible library method), you can take advantage of Arrays.copyOf to do the task. When more than one method is used, and there are 3 or more calls, doing import static java.util.Arrays.*; is the most efficient way of referring to those methods. After that, only if you have more than 8 separate calls to sort should you be using a shortcut method for it, and only at 5 or more calls is a shortcut warranted for copyOf.

The only real way of performing such analysis on code is to actually perform potential modifications on copies of the code, and then compare the results.
Avoid using someTypeValue.toString(); method, instead just append someTypeValue+"".
If you do need windows, don't use Swing, use AWT (unless you really need something from Swing). Compare import javax.swing.*; and import java.awt.*;. Additionally, components in Swing have a J prepended to their name (JFrame, JLabel, etc), but components in AWT don't (Frame, Label, etc)


Equivalence classes on the Transitive Closure of a Reflexive Relation

Pyth, 50 29 bytes

JchQ1FNeQAmf/@JTd0N XGJ.(JH;J

Input is expected to be a list of two elements where the first element is a list of all the objects in S, and the second element is a list of all the members in ≅, represented as lists. So for the first example, the input is

[["A", "B", "C", "D", "E", "F", "G", "H"], [["A", "B"], ["B", "C"], ["B", "E"], ["D", "G"], ["E", "H"]]]

Explanation:

                               Implicit assignment of Q to input, so head(Q) is S and end(Q) is ≅
JchQ1                          Assign J to chop(head(Q),1) e.g. [1,2,3] => [[1],[2],[3]]
     FNeQ                      For N in end(Q)
         A                       Assign [H,G] to following list
          m       N                Map following function over N
           f     0                   Return first T where following function of T starting at 0,1,2... is truthy
            /@JTd                      lambda d: true if d is J[T]
                    XGJ.(JH;     Append J[H] to J[G] and pop J[H]
                            J  Print J

Note that if transitive or reflexive members (i.e. redundant) members of ≅ are included, my code should output junk.

You can try it out here.


Brachylog, 90 bytes

;Ṡ{hhH↰₂gB&hb~c[A,B,C]&tT;C↔↰U∧" under ",H,T;A↔↰,U|tT&hh,TgJ&hb;T↰Q∧J,Q|h}
~↰₃|↰₃
∧"un";?c

I made this while being under the impression that this could be recursive and multiple unders could be stacked. Probably not optimized. Also as this is bracylog, plumbing takes quite some bytes.

Try it online!


CJam, 77 95 bytes

I think this can be golfed a bit more, but here goes:

q~$<_{{:X;]{[X\]z::-~mhW*}$~:Y{_)Y1{_@=X@=}:B~-g-{+__X=!\}:C~1B=!&}g{_(Y0B-g-\C0B=!&}g}*]_&}L?p

Input goes like N <Array of coordinate array>. For example:

4 [[0 0] [1 5] [2 1] [0 3] [5 0] [5 5]]

Output:

  [[0 5] [1 5] [0 4] [0 3] [0 0] [0 2] [0 1] [1 1] [2 1]]

Algorithm:

The algorithm is pretty straight forward and goes like:

Sort the input coordinate array. This makes the coordinates sorted first by row and then by column.
Now we pick first N points
Now we reduce on these N points. The destination is the last point and the source is the closes point to that last point.
Then we start with the top-left most point, walk right (or left) till its on or directly above the next point.
Then we walk down to reach the next point.
It is guaranteed that there will be no uncovered point left to the above point in the same row. This ensures that we do not touch any other point that the chosen N. Choosing the closes point also ensures that second rule is held true.

Try it online here


Ruby,87
->c,z{a=g=3-5**0.5
10.times{x=(c*="i".to_c**0.4).real
z=-z
a&&=z<1+x*g&&x*4>g-4+g*z}
a}

An anonymous function taking the x and y coordinates as a complex number and the z coordinate as a real. (The question says "any reasonable" format which is a bit vague. If the format is not acceptable I can change it.)
Explanation
Below you can see a view looking down the z axis at the icosahedron's vertices. (for simplicity I have just drawn 2 pentagons that are perpendicular to the z axis.)
I have labelled all the points with positive z with their approximate coordinates. I have given the exact coordinates sqrt 0.8, 0, sqrt 0.2 for the point with positive z that lies in the xz plane (y=0), and I have also labelled the opposing point.
It can be seen that there is an edge parallel to the y axis whose equation is approximately z=0.4472, x=-0.7236. This edge is common to two faces of the icosahedron. I will describe these as a polar face and an equatorial face.
The equation of the polar face is z=1+x*g where g=3-sqrt(5) (this value was arrived at by studying Wikipedia and Wolfram Alpha, plus a bit of my own maths.) So z must be less than 1+x*g if the point is inside the icosahedron.
The equation of the equatorial face is x*4=g-4+g*z so x*4 must be greater than
g-4+g*z if the point is inside the icosahedron.
We could rotate these faces through 72 degrees to test if the point is inside the icosahedron, but it is easier to rotate the point about the origin. In order to cover both the top and bottom of the icosahedron, the symmetry operation applied to the point is a rotation of 36 degrees combined with a reflection in the xy plane (flip the z axis.) This operation is applied 10 times to cover all possibilities.

Ungolfed in test program
f=->c,z{
  a=g=3-5**0.5                    #g is slope of polar face. It is truthy, so can also be used to initialize a
  10.times{                       #generate 10 images of the point
    x=(c*="i".to_c**0.4).real     #rotate the point 36 degrees, assign the real value to x
    z=-z                          #flip the z axis
    a &&= z<1+x*g && x*4>g-4+g*z  #check the point is inside the two test planes and update a if necessary
  }
a}                                #return a true or false

p f["0+0i".to_c,0]                     #true
p f["1+i".to_c,1]                      #false
p f["-0.152053-0.46797i".to_c,0.644105]#false
p f["-0.14609-0.449618i".to_c,0.618846]#true

p f["-0.8944+0i".to_c,-0.4472]         #true, just inside vertex
p f["-0.8944+0i".to_c,0.4472]          #false, outside midpoint of an edge
p f["-0.8945+0i".to_c,-0.4473]         #false, just outside vertex


Smalltalk 497
|b R M s g a|
b:=Stdin nextLine.R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)(1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)(6 1)(4 6 1)(4 6 1)(4 1)).
s:=Set new.q:=OrderedCollection new.
a:=[:p :m|(s includes:p)ifFalse:[s add:p.q add:p->m]].
a value:b value:''.
[|x i n p|
x:=q removeFirst.p:=x key.i:=(p indexOf:$_).
(M at:i)do:[:m||v|
n:=p copy.n at:i put:(p at:i+m-5);at:i+m-5put:$_.
v:=(x value,(R at:m)).
(n to:4)=(n from:9)ifTrue:[
v printCR.(n splitForSize:4)map:#printCR.^self].
a value:n value:v]]loop.

Input:
YRGYB_BRRYYR

Output:
DLURRULDDLLU
YBYR
RGR_
YBYR

Exec. Time (bytecode, not jitted): 100ms
Input:
RRRRBG_BYYYY

Output:
DRRUULLDLURDDRRULULD
YBRR
GY_Y
YBRR

Exec. Time 2s unjitted; 0.8s jitted (most time spent in collection code)
Here is an ungolfed version for readability:
|b R M s g add|
b:=Stdin nextLine.
R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)
     (1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)
     (6 1)(4 6 1)(4 6 1)(4 1)).
s := Set new.
queue := OrderedCollection new.

add := [:p :m |
  (s includes:p) ifFalse:[
    s add:p.
    queue add:(p->m).
  ]].

add value:b value:''.

[
  |x i n p|

  x := queue removeFirst.
  p := x key.
  i := (p indexOf:$_).
  (M at:i) do:[:m |
    |v|
    n := p copy.
    n at:i put:(p at:i+m-5); at:i+m-5 put:$_.
    v:=(x value,(R at:m)).
    (n to:4)=(n from:9) ifTrue:[
      v printCR.
      (n splitForSize:4) map:#printCR.
      ^ self
    ].
    add value:n value:v]
] loop.


JavaScript + HTML, 271 250 232 bytes
Apparantly you can use Dates as pseudo-random numbers. I stole this from Shaggy's answer.
(Only uses about 4 of your quota)

q=[]
g=f=>fetch('//api.stackexchange.com/questions/unanswered?site=codegolf&page='+f).then(r=>r.json().then(j=>(q=[...q,...j.items])^j.has_more?g(f+1):document.write(`<pre>${(q=q[new Date%q.length]).title}
${q.tags}
`+q.link)))
g(1)

It makes an array q, then calls g(1), which fetches the first page of results and adds it to q. Then, if the request says it has_more, then it calls g(f+1), which fetches the next page, until it reaches the end and writes out to the HTML document (Which will automatically unescape the response)
If we don't care about all of the unanswered questions, just the most recent 30 (Only uses 1 of your quota):
JavaScript + HTML, 213 196 179 bytes

fetch`//api.stackexchange.com/questions/unanswered?site=codegolf`.then(r=>r.json().then(j=>document.write(`<pre>${(j=j.items[new Date%j.items.length]).title}
${j.tags}
`+j.link)))


Pyth, 28 27 bytes

VQI}KhNsMyJf!%KTSNI!@JYeaYK

1 byte thanks to @Jakube

Demonstration.

VQI}KhNsMyJf!%KTSNI!@JYeaYK
                                Implicit:
                                Y = []
                                Q = eval(input())
VQ                              for N in range(Q):
    KhN                         K = N+1
           f    SN              filter T over range(1, N)
            !%KT                the logical not of K%T.
                                This is the list of divisors of K.
          J                     Store the list in J.
         y                      Create all of its subsets.
       sM                       Map each subset to its sum.
  I}K                           If K is in that list: (If K is semiperfect)
                  I!@JY         If the intersection of J (the divisors)
                                and Y (the list of primitive semiperfect numbers)
                                is empty:
                        aYK     Append K to Y
                       e        And print its last element, K.


Brachylog, 19 17 bytes
∧≜;1⟨∋{+|-}∋⟩ᵃ⁽?t

Try it online!
I guess I shouldn't be too surprised, but funnily enough this produces the exact same outputs as xash's solution--up to \$n = 13\$ after which both time out. Takes input through the output variable and outputs through the input variable.
   1                 Starting with 1,
             ᵃ       repeat on the list of previous results
∧≜;           ⁽      as few times as necessary:
       +             add
      { |-}          or subtract
    ⟨∋     ∋⟩        one element and another (not necessarily distinct),
               ?     such that the final list of results is the input variable
                t    and its last element is the output variable.


JavaScript (Node.js), 24 bytes

Saved 2 bytes thanks to @Grimy

Assumes that the returned string is printed on a terminal that supports ANSI escape codes. Contains the unprintable character ESC, which is escaped (no pun intended) as \x1B below.

a=>`\x1B[2J\x1B[H`+a.join`\x1B[H`

This doesn't work on TIO, but you can Try it online! to see the raw output instead.

How?

The CSI sequences used are:

ED (Erase in Display):

ESC[2J

where \$2\$ means "clear entire screen"
CUP (Cursor Position):

ESC[H

which means "moves the cursor to row \$n\$, column \$m\$" where both \$n\$ and \$m\$ are omitted and implicitly set to \$1\$ (top-left corner of the screen).

Example output


MATL, 7 bytes
BJ*Y'^s

Try it online!
How it works
Consider input 4538 for example.
B     % Implicit input. Convert to binary
      % STACK: [1 0 0 0 1 1 0 1 1 1 0 1 0]
J*    % Multiply by 1i
      % STACK: [1i 0 0 0 1i 1i 0 1i 1i 1i 0 1i 0]
Y'    % Run-length encoding
      % STACK: [1i 0 1i 0 1i 0 1i 0], [1 3 2 1 3 1 1 1]
^     % Power, element-wise
      % STACK: [1i 0 -1 0 -1i 0 1i 0]
s     % Sum of array. Implicit display
      % STACK: -1+1i


I am passive aggressive and want to insult my boss without him finding out

CJam, 56 53 bytes

q_"DIEIINAAGGREASEFFIRE"{S@:A+S@+#:BA<AB>}%(!B)*\N*@?

Try it online!

How it works

q_                     Read all input from STDIN and push a copy.
"DIEIINAAGGREASEFFIRE" Push the characters we're searching for in form of a
                       string. We'll try to prepend a linefeed to all of them.
                       Some characters are duplicated to prepend two linefeeds.
{                      For every character C in that string:
  S@                   Push ' ' and rotate the string on the stack on top of it.
  :A                   Save the string (initially the input) in A.
  +                    Prepend the space to A.
  S@+                  Construct the string " C".
  #                    Compute the index of " C" in the modified A.
  :B                   Save the index in the variable B.
  A<                   Push the substring of A up to the index.
  AB>                  Push the substring of A after the index.
}%
(                      Shift the first element of the resulting array.
!                      Compute the logical NOT. This pushes 1 if and only if the
                       array's first element is an empty string, which is true
                       if and only if the input string started with a D.
B)                     Push the last value of B and increment. If the last match
                       was successful and, therefore, all matches were successful,
                       B != -1, so B + 1 != 0.
*                      Compute the product of the two topmost items on the stack.
\                      Swap the resulting Booleanr with the array of substrings.
N*                     Join the array, separating by linefeeds.
@                      Rotate the input string on top of the stack.
?                      Select the joined array if the Boolean is 1 and the input
                       string otherwise.


Tips for Creating/Maintaining a Golfing Language

Here are some suggestions. Sorry that this partially overlaps with other answers, which have been posted as I was writing this.
Design process

One possibility (by all means not the only one) to decide which features (functions, data types, etc.) your language L should have is to base it on another language B that you have been using for long. That way you already have a good idea which functions of B are used most often, and therefore should be included in your language L, and you can assign shorter names in L to functions that are commonly used in B.

Examples:

L = MATL: B = MATLAB/Octave.
L = Pyth: B = Python.
L = Japt: B = JavaScript.
L = Brachylog: B = Prolog.
L = Husk: B = Haskell.
L = ShortC: B = C.
L = V: B = Vim.

Decide which "paradigm" your language will use. Some examples are

Stack-based (Cjam, MATL, 05AB1E);
Tacit (Jelly);
Prefix notation (Pyth);
Infix notation (Pip, Japt);
Fixed arity (Pyth);
Variable arity (CJam, MATL, Japt).

These decisions are quite independent from item 1. For example, MATL's function f has the same functionality as MATLAB's find, but is used differently in that it pops its inputs from the stack and pushes its outputs onto it, whereas MATLAB uses normal function arguments which can be stored in variables.

Incorporate functions from other golfing languages that you find useful. Don't let item 1 (if applicable) limit language L's definition.

Be prepared to add functions in the future. As you (or others) use the language, you will find things it would be nice to add. So reserve some of the "namespace" for future expansion. For example, don't use up all your single-character names at once.

Implementation

Write the compiler (or interpreter) for your language L in a language C that you know well (often C = B).
The compiler is most often actually a transpiler into another language T (which can be the same as B or C). Language T should have a free implementation. That way it is viable to have an online compiler for your language. The compiler will be a program in C that takes source code in L to produce transpiled code in T, and then calls T's compiler/interpreter to run the transpiled code.

A natural choice is C = T. Examples:

L = Japt: B = C = T = JavaScript.
L = Jelly: C = T = Python (and Jelly is inspired by J; but perhaps not so much as to claim that B = J).
L = MATL: B = C = T = MATLAB/Octave.

Community engagement

Host your compiler/interpreter in a public repository such as GitHub, so people can easily download it, create bug reports, suggest new features or even contribute with code.
Write good documentation. That helps users understand your language better. Besides, I found that task more rewarding than I expected. I recommend writing the specification while you are designing the language, not at the end. That way consistency between language behaviour and its specification is ensured.
Ideally the documentation should include some quick reference (table or summary), so experienced users don't have to go to the full documentation simply because they have forgotten the name or the syntax of a function they know.
Create an esolangs page with basic information about your language.
Create a chat room where people can ask and discuss about the language. Visit it often.
Answer questions in your language, with explanations about how the code works. You'll want to do that anyway (it's your language, you will find it fun to use), but this also helps get people curious about your language, and shows some of the language's properties, which might get people interested.
If you chose to base your language L on a language B (see item 1) that is general-purpose and well known, users of B will find it easy to switch to L, which will allow them to provide short answers (in L) with minimal effort (coming from B).


Charcoal, 62 43 39 bytes

ＮβＦ³«Ｆ⁻β‹ι²« / \¶|   |¶ \ /Ｍ×²ι↑¿⁻¹ιＭ⁶←

Try it online! Edit: Saved some bytes thanks to @ASCII-only (not sure exactly how many as I also saved another 6 10 bytes but then needed to spend 4 bytes on a bugfix). Now using nested loops, which is what this should have been all along.


The shortest code to tell if a number is even or odd

47 bytes (2 less)

main(i){scanf("%d",&i);puts("dispari"-~i%2*3);}

For a positive i, ~i is negative, so ~i%2 is 0 or -1.


Jelly, 23 bytes

Ṛ⁹,2⁶v$Ṡ$e⁵$?¥þị“/ \-”Y

Try it online!

Arguments: Y, X, U, f

f is a Python string containing Jelly code. Be sure to quote it appropriately, otherwise you may encounter errors.

Also, f takes a pair [x, y] as its argument, not two arguments x and y.


Electrostatic potential of a simple system

CJam, 51 chars

Counting all pairs, filtering Inf/NaN out and dividing by two:

q_N#:L;N-" +"f#ee2m*{z~:*\Lfmd2/:.-:mh/}%{zL<},:+2/

Alternatively, filtering coordinates first so we count each pair once and don't run into Inf/NaN:

q_N#:L;N-" +"f#ee2m*{0f=:<},{z~:*\Lfmd2/:.-:mh/}%:+

Explanation (old)

q                        Get all input.
 _N#:L;                  Store the line width in L.
       N-                Flatten it into one long line.
         :i              Get all ASCII values.
           :(3f%:(       Map space to 0, + to 1, - to -1.
                  ee     Enumerate: list of [index, sign] pairs.
                    2m*  Get all possible pairs.

{                        }%     For each pair:
 e_~                              i1 s1 i2 s2
    @*                            i1 i2 s        (multiply signs)
      \aa@aa+                     s [[i2] [i1]]  (put indices in nested list)
             Lffmd                s [[x2 y2] [x1 y1]]  (divmod by L)
                  :.-             s [xD yD]      (point diff)
                     :mh          s d            (Euclidean dist.)
                        /         s/d            (divide)

{zL<},                   Filter out infinite results.
      :+2/               Sum all charges, and divide by two.
                           (We counted each pair twice.)


APL (73)

{⊃,/,⌿↑(⊂2∘↓¨Z⊂G),⊂{'c'0≡⍵,∊⊃⍺:⎕UCS⍺⋄⍕⍺}/⍵,⍪⌷∘G¨1↓1+(Z←G='%')/⍳⍴G←'%!',⍺}

Some tests:

      'a:%c b:%s c:%d'{⊃,/,⌿↑(⊂2∘↓¨Z⊂G),⊂{'c'0≡⍵,∊⊃⍺:⎕UCS⍺⋄⍕⍺}/⍵,⍪⌷∘G¨1↓1+(Z←G='%')/⍳⍴G←'%!',⍺} 65 'foo' 67
a:A b:foo c:67

      printf←{⊃,/,⌿↑(⊂2∘↓¨Z⊂G),⊂{'c'0≡⍵,∊⊃⍺:⎕UCS⍺⋄⍕⍺}/⍵,⍪⌷∘G¨1↓1+(Z←G='%')/⍳⍴G←'%!',⍺}
      '1:%s 2:%s 3:%d 4:%c 5:%c' printf 'foo' 'bar' 100 110 'z'
1:foo 2:bar 3:100 4:n 5:z
      'The %s brown %c%c%c jumps over the %s dog.' printf 'quick' 102 111 'x' 'lazy'
The quick brown fox jumps over the lazy dog.

Explanation:

G←'%!',⍺: prefix a dummy specifier to the string (for easier processing)
(Z←G='%')/⍳⍴G: find the indices of all the % characters in the string; also store a bitmask in Z
⌷∘G¨1↓1+: select all the characters next to the %s, and drop the dummy.
⍵,⍪: match up each specifier with its value from the right argument.
{...}/: run the following function on each pair:

'c'0≡⍵,∊⊃⍺: if the argument is a number and the specifier is c:
:⎕UCS⍺: then return the unicode value of the argument,
⋄⍕⍺: otherwise, return the string representation of the argument.

⊂: enclose
⊂2∘↓¨Z⊂G: split the string on the %s and then remove the first two characters of each substring (this is where the dummy comes in), and enclose the result of that.
↑: make a matrix out of the two enclosed arrays, matching up each substring with the value that should follow it.
,⌿: join each substring with its value.
⊃,/: then join the resulting strings.


Python 2, 47, 46
It's not as short as using regex, but I thought it was entertainingly obscure.
i=int(('0%sx'%s)[:~len(s.lstrip(str(1<<68)))])

-1 due to KSab – str with some large integer works better than the repr operator since it does not put an L on the end.


Python, 198 178 161 chars

V=eval('input(),'*4)
A=0
for i in range(4):F=V[:i]+V[i+1:];a,b,c=map(lambda e:sum((a-b)**2for a,b in zip(*e)),zip(F,F[1:]+F));A+=(4*a*b-(a+b-c)**2)**.5
print A/4

The input format is as given in the question.

It calculates the length of the edges adjacent to each of the faces and then uses Heron's formula.


Python 3, 67 55 bytes

f=lambda x,*l:x and-~f(*l[x%3-1::1-x//3*2],0,*l[x%2:1])

Try it online!

Use @Leo's idea of keeping the current player at a fixed index and transforming the list instead. Be sure to check out and upvote his answer!

If the current list is [x, a, b, c, d], where x is the move of the current player, then we want to rotate the list appropriately, and replace x with 0:

If x == 1, the new list is [a, b, c, d, 0]
If x == 2, the new list is [b, c, d, 0, a]
If x == 3, the new list is [d, c, b, a, 0]
If x == 0, this player has already been visited, thus we stop the algorithm.

Python 2, 90 85 bytes

f=lambda l,d=1,p=0,*t:(p in t)^1and-~f(l,[d,-d][l[p]>2],(-~l[p]%4*d-d+p)%len(l),p,*t)

Try it online!

Not every elegant, but does the job.

This recursive function keeps track of the current direction d, the position p, and the list of seen position t.


Simulate the Wireworld cellular automaton

APL, Dyalog (131)

{h t c←1↓⍵∘=¨F←' htc'⋄⎕SM∘←1 1,⍨⊂N←F[1+⊃+/H h(t∨c≠H←c∧S↑1 1↓1 2∊⍨⊃+/+/K∘.⊖(K←2-⍳3)∘.⌽⊂¯1⌽¯1⊖h↑⍨2+S←25 79)×¨⍳3]⋄∇N⊣⎕DL÷4}↑{79↑⍞}¨⍳25

The output is displayed in the ⎕SM window. The simulation runs endlessly. The grid is 79x25 because that's the default size of the ⎕SM window. The electron head is h, tail is t, copper is c. The program reads the starting configuration from the keyboard as 25 lines.

Explanation:

↑{79↑⍞}¨⍳25: read the 79x25 grid
h t c←1↓⍵∘=¨F←' htc': get three matrices, one with the heads, one with the tails and one with the copper. Also set F to the string ' htc'.
⎕SM∘←1 1,⍨⊂N←F[1+⊃+/...×¨⍳3]: The "..." part is a vector of length three, where the elements are matrices showing the new heads, tails, and copper respectively. The heads are multiplied by 1, the tails by 2, and the copper by 3, then we sum these matrices together and add one, giving a matrix of indices into F. N becomes the new state, in the same format as the input, and it is shown on the ⎕SM screen starting from the top-left corner.
¯1⌽¯1⊖h↑⍨2+S←25 79: Add a border of blanks to h by growing it by two rows and columns, then rotating it one right and one down.
⊃+/+/K∘.⊖(K←2-⍳3)∘.⌽⊂: Rotate the matrix in all eight directions and then sum the resulting matrices together, giving the amount of neighbours that are heads on each position.
1 2∊⍨: Set only those positions to 1 which have 1 or 2 neighbours.
S↑1 1↓: Remove the border we added earlier.
H←c∧: The new heads are all those copper cells that have 1 or 2 head neighbours.
t∨c≠H: The new copper cells are all old tails, and all old copper cells that have not become heads.
H h(...): The new heads are H as calculated above, the new tails are the old heads, and the new copper cells are as calculated above.
∇N⊣⎕DL÷4: Wait 1/4th of a second, then run the function again on N.


05AB1E, 14 11 bytes

-3 bytes thanks to Kevin Cruijssen

EžN¸žMšNèΩJ

Try it online!


TikZ (pdfTeX 3.14159265-2.6-1.40.17), 85 79 74 24 22 21 bytes
A bunch of bytes saved thanks to wchargin
One byte saved thanks to Chris H
\input tikz
\tikz\pic

I actually encountered this one by accident when I was working on homework.  I spent quite a while waiting for it to compile before I realized what was happening.
This has two parts:
\input tikz

This loads the TikZ package
and:
\tikz\pic

This starts a \tikz environment and a draw command.
What is going on
The pdflatex compiler has trouble with \tikz\pic, and enters interactive mode causing it to stall indefinitely.


JavaScript (ES6),  22  21 bytes

A=>A.map(x=>A=x||~~A)

Try it online!
Commented
A =>          // A[] = input array
  A.map(x =>  // for each value x in A[]:
    A =       //   update A to:
      x ||    //     either x, if it's not equal to 0
      ~~A     //     or A coerced to an integer otherwise
  )           // end of map()

Because we're re-using the input array \$A[\:]\$ to store the last non-zero value, two special cases arise if the 2nd part of the condition is executed on the 1st iteration:

if \$A[\:]\$ is a singleton array containing \$0\$, ~~A is equal to ~~0
if \$A[\:]\$ is an array of several elements (starting with \$0\$), ~~A is equal to ~~NaN

which gives the expected \$0\$ in both cases.


Approximate floating point number with n-digit precision

JavaScript, O(10p) & 72 bytes

r=>p=>{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b<r?a++:b++);return[a,b]}

It is trivial to prove that the loop will be done after at most O(10p) iterations.

f=
r=>p=>{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b<r?a++:b++);return[a,b]}
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow>
    <mn>0.<input type="text" id="n" value="" oninput="[p,q]=f(+('0.'+n.value))(n.value.length);v1.value=p;v2.value=q;d.value=p/q" /></mn>
    <mo>=</mo>
    <mfrac>
      <mrow><mn><output id="v1">0</output></mn></mrow>
      <mrow><mn><output id="v2">1</output></mn></mrow>
    </mfrac>
    <mo>=</mo>
    <mn><output id="d">0</output></mn>
  </mrow>
</math>

Many thanks to Neil's idea, save 50 bytes.


Pyth, 21 20 bytes

VQ=k+.>k-}NG}Nr1GN)k

Try it here

Explanation

VQ=k+.>k-}NG}Nr1GN)k
VQ                )      For each N in the input...
     .>k                 ... rotate k (initially '')...
        -}NG}Nr1G        ... by (N is lowercase) - (N is uppercase)...
    +            N       ... then append N...
  =k                     ... and update k.
                   k     Output the result.


JavaScript (ES6),  95 93 86  82 bytes
Expects (r)(m).

r=>F=(m,x=r)=>r?(g=k=>!k||g(--k)*(k-x)/~k)(r)>m?[...F(m-g(r--,--x)),x]:F(m,x+1):[]

Try it online!
How?
Helper function
The helper function \$g\$ is used to compute:
$$\binom{x}{r}=\frac{x(x-1)\dots(x-r+1)}{r!}=\prod_{k=1}^{r}\frac{x-k+1}{k}$$
(g = k =>     // g is a recursive function taking k
  !k          // if k = 0, stop the recursion and return 1
  ||          // otherwise:
    g(--k)    //   decrement k and do a recursive call with the updated value
    * (k - x) //   multiply the result by k - x
    / ~k      //   divide by -k - 1
              //   which is equivalent to g(k - 1) * (x - k + 1) / k
)(r)          // initial call to g with k = r

Main function
r =>                      // r = requested number of combinations
F = (m, x = r) =>         // F is a recursive function taking the target number m
                          // and a counter x, initialized to r
  r ?                     // if r is not equal to 0:
    g(r) > m ?            //   if C(x, r) is greater than m:
      [ ...F(             //     append the result of a recursive call to F:
          m - g(r--, --x) //       with m - C(x - 1, r) and r - 1
        ),                //     end of recursive call
        x                 //     append x (which was decremented above)
      ]                   //
    :                     //   else:
      F(m, x + 1)         //     increment x until C(x, r) > m
  :                       // else:
    []                    //   stop the recursion


Retina, 210 161 156 133 bytes (ISO 8859-1 encoding)

Completely remade, doesn't care about input anymore.

s`.+
3r41t¶2/43\¶1:15,13,5:¶1/10 e\¶|5_,e |¶|5#'e |¶1\4#5 e/¶1:4"10'13'5:¶2\43/¶3L19 10$*#11j
e
3~11~4
~
|6$*#|
,
6$*_
'
6$*"
\d+
$*

There is a trailing space at the end of last line. Also, a trailing newline is included in the output. If you want to suppress it, change the second last line to \`\d+

Old version, which uses parts of input in output:

( {3})(.+¶){3}.{10}( +)\S+( +).¶.( +)(.+¶){5}.+?(#+).+
$1rq te /q$1\e:pf,p$1,f:e/p$4~$3~$4\¶|f,_$1~$3~f|¶|f#'$1~$3~f|e\$4#$4f~$3~$4/e:$4"p'p$1'f:e \q$1/¶$1Lpp$7$3j
~
|6$*#|
,
6$*_
'
6$*"
q
pppp
p
ff
e
¶
f
5$*

Try it online! (210-byte version)
Try it online! (161-byte version)
Try it online! (156-byte version)
Try it online! (133-byte version)


The group of sequential positive numbers with the highest sum?

APL, 35 characters

i←⎕⋄⌈/{{+/⍵/⍨∧\⍵>0}⍵↓i}¨0,(i≤0)/⍳⍴i

I used Dyalog APL for this. ⎕IO should be set to its default of 1.

Example (note that high-minus, ¯, must be used instead of regular minus):

      i←⎕⋄⌈/{{+/⍵/⍨∧\⍵>0}⍵↓i}¨0,(i≤0)/⍳⍴i
⎕:
      12 2 35 ¯1 20 9 76 5 4 ¯3 4 ¯5 19 80 32 ¯1
131

Explanation (roughly right-to-left for each expression):

First, we get (and evaluate) the input: i←⎕. (⋄ separates expressions in a single statement.)
(i≤0)/⍳⍴i is an idiom to get the list of the locations of elements of i that are ≤0.

i≤0 returns a vector of binary values, where each element is 1 if the corresponding element in i is ≤0, and 0 otherwise.
⍳⍴i returns a list of integers, from 1 to the shape (length) of i.
The replication function, /, replicates each value in its right argument n times, where n is the corresponding element in its left argument. Because we have a binary list, this just includes or excludes elements (replicating them 0 or 1 times).
We tack a 0 on the beginning, using the concatenation operator (,).

Now, using the example input, we have the vector 0 4 10 12 16. We use the each operator, ¨, to map a function (its left operand) to each element of this list.
The function is a direct function (basically, an anonymous function), and its definition is surrounded with curly braces. Its right argument is represented by the omega symbol, ⍵.
For each element of our vector:

The outermost function, {{ ... }⍵↓i}, returns the vector i, with ⍵ elements dropped (↓) from the beginning. This is then fed to...
The innermost function, {+/⍵/⍨∧\⍵>0}, in slightly less golfed form is {+/(∧\⍵>0)/⍵}.
(∧\⍵>0)/⍵ is similar to the aforementioned idiom. First we generate a list of elements in ⍵ that are above 0. Then, we use the scan operator, \, along with the bitwise-AND function, ∧, to return the list (⍵1 , ⍵1 ∧ ⍵2 , ⍵1 ∧ ⍵2 ∧ ⍵3 , ...). In other words, this list consists of 1's up until the first non-positive element, where it is then all 0's. We use replication as before.
We now use the reduction operator, (also) represented by /, along with the addition function, +, to fold all positive elements in the current list, up to (but not including) the first non-positive one.

Lastly, we fold again, this time with the maximum function, ⌈.

Here are snapshots showing the results of some stages:

      i≤0
0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1

      ⍳⍴i
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

      0,(i≤0)/⍳⍴i
0 4 10 12 16

      {⍵↓i}¨0,(i≤0)/⍳⍴i
 12 2 35 ¯1 20 9 76 5 4 ¯3 4 ¯5 19 80 32 ¯1  20 9 76 5 4 ¯3 4 ¯5 19 80 32 ¯1  4 ¯5 19 80 32 ¯1  19 80 32 ¯1

      {{(∧\⍵>0)}⍵↓i}¨0,(i≤0)/⍳⍴i
 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0  1 1 1 1 1 0 0 0 0 0 0 0  1 0 0 0 0 0  1 1 1 0

      {{(∧\⍵>0)/⍵}⍵↓i}¨0,(i≤0)/⍳⍴i
 12 2 35  20 9 76 5 4  4  19 80 32

      {{+/(∧\⍵>0)/⍵}⍵↓i}¨0,(i≤0)/⍳⍴i
49 114 4 131 0

Hopefully some of this makes a bit of sense!


Python 2, 128 bytes

w,h,d=input();i=d
while-i<h:c='|/'[i>0];print' '*i+c+'- _'[(d>i!=0)+(h+i<2)]*(w-2)+c+' '*min(d-i,h-1,w+1,h-1+i)+'/|'[d-i<h];i-=1

Prints row by row. The row indices i count down from d to -h+1.


R, 184 bytes

Golfed, could probably be golfed by a few bytes

function(m){e=min;f=max;l=length;v=which(m!=" ",T);a=v[,1];n=l(v[a==1,2]);u=(v[a==e(a),2]);all(u==v[a==f(a),2])&all(c(e(d<-v[a==ceiling(f(v[,1])/2),2]),f(d))==c(u[1]-n+1,u[l(u)]+n-1))}

Ungolfed, very messy, more like half way golfed

f=function(m) {
  v = which(m!=" ",T)
  a = v[,1]
  n = length(v[a==1,2])
  u=(v[a==min(a),2])
  c1 = all(u==v[a==max(a),2])
  d = v[a==ceiling(max(v[,1])/2),2]
  c2 = all(c(min(d), max(d))==c(u[1]-n+1,u[length(u)]+n-1))
  c1 & c2
}

Since the input format is unspecified, Input needs to be specified in an R array format, looking something like this.

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

Here is a generator function that generates the input. The generator doesn't generate an object that is fed into hexagon check function, but rather the code specifying the array (effectively the same thing). So this should not count as parsing the text. Remember that I'm not inputting text, but rather an array structure.

generate = function(x) {
  s = strsplit(strsplit(x, "\n")[[1]], "")
  m = max(sapply(s, length))
  dput(do.call(rbind, lapply(s, function(x) c(x, rep(" ", m-length(x))))))
}

For example, the generated code would be: structure(c(" ", " ", "2", " ", " ", " ", "8", " ", "7", " ", "5", " ", "3", " ", "1", " ", "9", " ", "8", " ", "6", " ", "4", " ", "2", " ", "0", " ", "9", " ", "7", " ", "5", " ", "3", " ",
"1", " ", "0", " ", " ", " ", "6", " ", " "), .Dim = c(5L, 9L
)) which is identical to array(c(" ", " ", "2", " ", " ", " ", "8", " ", "7", " ", "5", " ", "3", " ", "1", " ", "9", " ", "8", " ", "6", " ", "4", " ", "2", " ", "0", " ", "9", " ", "7", " ", "5", " ", "3", " ", "1", " ", "0", " ", " ", " ", "6", " ", " "), dim = c(5, 9))

Hopefully this input method is in compliance with the rules.

Here are the test cases

x1 =
"  5 6 7
 8 9 0 1
2 3 4 5 6
 7 8 9 0
  1 2 3"

x2 =
" # _
+ + +
 9 :"

x3 =
"    t h i s
   i       s
  a         h
 e           x
  a         g
   o       n
    ! ! ! !"

x4 ="    5 6 7
   8 9 0 1
  2 3 4 5 6
   7 8 9 0
    1 2 3"

x5 = "r e c t a
n g l e s"

x6 = "  h e l l o
  w o r l d s
t h i s i s b
 e t a d e c
  a y n o w"

x7 ="  *
 * *
* * *"

x8 ="   .....
  .......
.........
  .......
   ....."

Generate input arrays

sapply(mget(paste("x", 1:8, sep = "")), generate)

Test for hexagon

sapply(.Last.value , f)

   x1    x2    x3    x4    x5    x6    x7    x8
 TRUE  TRUE  TRUE  TRUE FALSE FALSE FALSE FALSE


Spaces after keywords are optional because of tokenisation. For example:

INPUT answer$
PRINT answer$
IF answer$ = 'Hi' THEN
  PRINT 'Hi!'
ENDIF

Can be shortened to

INPUTanswer$
PRINTanswer$
IFanswer$='Hi'THEN
  PRINT'Hi!'
ENDIF

The corollary of this is, a variable name cannot start with a keyword. So PRINTa is not a valid variable name. However printa is.

Spaces before keywords can be more tricky. Variable names can end with a keyword, so if variable name and keyword are run together they will be interpreted as a variable name.

For example the following gives a "no such variable" error because the variable aPRINT is not defined:

  a=7
  IF7=aPRINT"seven"

By rearranging this can be avoided:

  a=7
  IFa=7PRINT"seven"

This is a trivial example, but frequently rearranging an expression to end in a number or bracket instead of a variable name will enable you to eliminate a trailing space.


Compute the maximum number of runs possible for as large a string as possible

C

This does a recursive search for optimal solutions, heavily pruned using an upper bound on the number of runs that could be finished by the unknown remainder of the string.  The upper bound computation uses a gigantic lookup table whose size is controlled by the constant L (L=11: 0.5 GiB, L=12: 2 GiB, L=13: 8 GiB).

On my laptop, this goes up through n = 50 in 100 seconds; the next line comes at 142 seconds.

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define N (8*sizeof(unsigned long long))
#define L 13
static bool a[N], best_a[N];
static int start[N/2 + 1], best_runs;
static uint8_t end_runs[2 << 2*L][2], small[N + 1][2 << 2*L];

static inline unsigned next_state(unsigned state, int b)
{
    state *= 2;
    state += b;
    if (state >= 2 << 2*L) {
        state &= ~(2 << 2*L);
        state |= 1 << 2*L;
    }
    return state;
}

static void search(int n, int i, int runs, unsigned state)
{
    if (i == n) {
        int r = runs;
        unsigned long long m = 0;
        for (int p = n / 2; p > 0; p--) {
            if (i - start[p] >= 2*p && !(m & 1ULL << start[p])) {
                m |= 1ULL << start[p];
                r++;
            }
        }
        if (r > best_runs) {
            best_runs = r;
            memcpy(best_a, a, n*sizeof(a[0]));
        }
    } else {
        a[i] = false;
        do {
            int r = runs, bound = 0, saved = 0, save_p[N/2], save_start[N/2], p, s = next_state(state, a[i]);
            unsigned long long m = 0;
            for (p = n/2; p > i; p--)
                if (p > L)
                    bound += (n - p + 1)/(p + 1);
            for (; p > 0; p--) {
                if (a[i] != a[i - p]) {
                    if (i - start[p] >= 2*p && !(m & 1ULL << start[p])) {
                        m |= 1ULL << start[p];
                        r++;
                    }
                    save_p[saved] = p;
                    save_start[saved] = start[p];
                    saved++;
                    start[p] = i + 1 - p;
                    if (p > L)
                        bound += (n - i)/(p + 1);
                } else {
                    if (p > L)
                        bound += (n - (start[p] + p - 1 > i - p ? start[p] + p - 1 : i - p))/(p + 1);
                }
            }
            bound += small[n - i - 1][s];

            if (r + bound > best_runs)
                search(n, i + 1, r, s);
            while (saved--)
                start[save_p[saved]] = save_start[saved];
        } while ((a[i] = !a[i]));
    }
}

int main()
{
    for (int n = 0; n <= N; n++) {
        if (n <= 2*L) {
            for (unsigned state = 1U << n; state < 2U << n; state++) {
                for (int b = 0; b < 2; b++) {
                    int r = 0;
                    unsigned long long m = 0;
                    for (int p = n / 2; p > 0; p--) {
                        if ((b ^ state >> (p - 1)) & 1) {
                            unsigned k = state ^ state >> p;
                            k &= -k;
                            k <<= p;
                            if (!(k & ~(~0U << n)))
                                k = 1U << n;
                            if (!((m | ~(~0U << 2*p)) & k)) {
                                m |= k;
                                r++;
                            }
                        }
                    }
                    end_runs[state][b] = r;
                }
                small[0][state] = end_runs[state][0] + end_runs[state][1];
            }
        }

        for (int l = 2*L < n - 1 ? 2*L : n - 1; l >= 0; l--) {
            for (unsigned state = 1U << l; state < 2U << l; state++) {
                int r0 = small[n - l - 1][next_state(state, 0)] + end_runs[state][0],
                    r1 = small[n - l - 1][next_state(state, 1)] + end_runs[state][1];
                small[n - l][state] = r0 > r1 ? r0 : r1;
            }
        }

        if (n >= 2) {
            search(n, 1, 0, 2U);
            printf("%d %d ", n, best_runs);
            for (int i = 0; i < n; i++)
                printf("%d", best_a[i]);
            printf("\n");
            fflush(stdout);
            best_runs--;
        }
    }
    return 0;
}

Output:

$ gcc -mcmodel=medium -O2 runs.c -o runs
$ ./runs
2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011
23 17 00100101001011010010100
24 18 001001100100110110011011
25 19 0010011001000100110010011
26 20 00101001011010010100101101
27 21 001001010010110100101001011
28 22 0010100101101001010010110100
29 23 00101001011010010100101101011
30 24 001011010010110101101001011010
31 25 0010100101101001010010110100101
32 26 00101001011010010100101101001011
33 27 001010010110100101001011010010100
34 27 0001010010110100101001011010010100
35 28 00100101001011010010100101101001011
36 29 001001010010110100101001011010010100
37 30 0010011001001100100010011001001100100
38 30 00010011001001100100010011001001100100
39 31 001001010010110100101001011010010100100
40 32 0010010100101101001010010110100101001011
41 33 00100110010001001100100110010001001100100
42 35 001010010110100101001011010110100101101011
43 35 0001010010110100101001011010110100101101011
44 36 00101001011001010010110100101001011010010100
45 37 001001010010110100101001011010110100101101011
46 38 0010100101101001010010110100101001011010010100
47 39 00101101001010010110100101101001010010110100101
48 40 001010010110100101001011010010110101101001011010
49 41 0010100101101001010010110100101101001010010110100
50 42 00101001011010010100101101001011010110100101101011
51 43 001010010110100101001011010110100101001011010010100

Here are all optimal sequences for n ≤ 64 (not just the lexicographically first), generated by a modified version of this program and many hours of computation.

A remarkable nearly-optimal sequence

The prefixes of the infinite fractal sequence

1010010110100101001011010010110100101001011010010100101…

that is invariant under the transformation 101 ↦ 10100, 00 ↦ 101:

  101   00  101   101   00  101   00  101   101   00  101   101   00  …
= 10100 101 10100 10100 101 10100 101 10100 10100 101 10100 10100 101 …

seem to have very nearly optimal numbers of runs—always within 2 of optimal for n ≤ 64. The number of runs in the first n characters divided by n approaches (13 − 5√5)/2 ≈ 0.90983. But it turns out this is not the optimal ratio—see comments.


JavaScript (ES7), 51 48 bytes

Saved 3 bytes thanks to @Arnauld

f=i=>i?f[f[q=f(i-1),r=f[i]||q+1]=(i>1)<<i,i]=r:1

Takes in n and outputs the n'th item in the sequence.

JavaScript (ES7), 70 68 64 bytes

f=(n,a=[],q=1)=>n?f(n-1,a,(n=2**a.indexOf(a.push(q)))<++q?q:n):a

A recursive function that takes in x and returns the first x items of the sequence as an array.

How it works

The array a is procedurally generated, one item at a time, until it reaches the desired length. (A port of the infinite technique used in xnor's excellent Python answer would likely be shorter.)

We can make the following observation for each index i (0-indexed):

If i exists as an item in a at index j (a[j] = i), then a[i] needs to be at least 2j.

This is true because f(f(j)) needs to be at least 2j, and f(f(j)) is equivalent to a[a[j]], which is in turn equivalent to a[i].

Normally the correct option is exactly 2j. However, for the singular case i = 2, 2 exists in the array at index j = 1, which means that 2j would be 2—but this means that we would have 2 at both a[1] and a[2]. To get around this, we take the maximum of 2j and a[i-1] + 1 (one more than the previous item), which gives 3 for i = 2.

This technique also happens to take care of deciding whether or not j exists—if it doesn't, JS's .indexOf() method returns -1, which leads to taking the max of a[i-1] + 1 and 2-1 = 0.5. Since
all items in the sequence are at least 1, this will always return the previous item plus one.

(I'm writing this explanation late at night, so please let me know if something is confusing or I missed anything)


Pyth, 48 bytes

-jdm?td(.*dhdJ.bmOSYNmm.xsk100cd\dcz))\,jdsMJssJ

Test Suite

Tricks / golfs in this code:

Everything that's not a number will be treated as 100, not just %.
To get the parentheses, I make the list into a tuple, then subtract out the commas.
This is the first time I've used .b, the binary map, which was added 3 days ago.
The code contains 6 different map functions.


Remove each integer from a string and multiply them all!

Red, 109 bytes

func[s][p: 1 d: charset"0123456789"parse s[any[to d copy t[any d ahead[" "|"!"|"?"]](p: p * to p t)| skip]]p]

Try it online!


JavaScript (ES6),  57  51 bytes
Returns a Set of words in lower case.
NB: In JS, the elements of a Set are guaranteed to appear in insertion order. In this case, this  is the order defined in the sorted array the Set is built from.

s=>new Set(s.toLowerCase().match(/[a-z]+/g).sort())

Try it online!


Tcl with SQLite, score less than 0.05

Shove the lines into an SQL database, then make SQLite do the work.  Requires the Tcl bindings for SQLite 3, OpenBSD package sqlite3-tcl, Ubuntu package libsqlite3-tcl.

Usage: tclsh filter.tcl <input.txt >output.txt

package require sqlite3

sqlite3 db ""
db eval {
    begin transaction;
    create table lines(i integer primary key,
               a integer, b integer, t integer);
}
while {[gets stdin line] >= 0} {
    lassign [split $line] a b t
    db eval {insert into lines values(null,$a,$b,$t)}
}
db eval {
    create view pairs as
      select first.i, second.i as j
      from lines as first, lines as second
      where first.a == second.b and
        first.t - second.t between 0 and 99 and
        first.i != second.i;
    select a, b, t from lines
      where i in (select i from pairs union select j from pairs);
} {
    puts "$a $b $t"
}
db close

Comparison of time

The motto of SQLite is, "Small. Fast. Reliable. Choose any three," but my SQL query is not fast. My program took more than six hours with my slow hard disk. I compare times for three programs:

cfilter is the large-memory C program by Keith Randall
hfilter is the large-memory C program by James_pic
filter.tcl is my small-memory Tcl program

With 50 million lines of input, cfilter and hfilter both crash because my data size limit is only 1 GB. (The default limit in OpenBSD is 512 MB.) If I raise my limit to 8 GB with ulimit -Sd 8388608, then I can run both cfilter and hfilter. I also lower my physical memory limit with -m 3000000 so that other programs stay in RAM, not in swap space. I have only 4 GB of RAM.

$ ulimit -Sd 8388608 -m 3000000
$ time ./cfilter input.txt >output.txt
    0m9.03s real     0m5.17s user     0m1.97s system
$ ln -sf input.txt test.file
$ time ./hfilter >output2.txt
    0m25.62s real     0m22.08s user     0m2.04s system
$ time tclsh8.6 filter.tcl <input.txt >output3.txt
^Z  371m19.57s real     0m0.00s user     0m0.00s system
[1] + Suspended            tclsh8.6 filter.tcl < input.txt > output3.txt

I suspended filter.tcl after more than 6 hours. top shows that filter.tcl used less than 15 MB of memory and less than 12 minutes of processor time. Most of the 6 hours went to wait for my slow hard disk (5400 rpm).

For score, 10 seconds for cfilter, divided by more than 6 hours for filter.tcl, times 100, equals less than 0.05.

Comparison of results

The different filters do not select the same lines!  Consider these 6 lines of input:

$ cat example.txt
1 801 33
802 1 33
2 803 499
804 2 400
805 2 400
3 3 555

My filter.tcl outputs five lines, all except 3 3 555.

$ tclsh8.6 filter.tcl <example.txt
1 801 33
802 1 33
2 803 499
804 2 400
805 2 400

But cfilter only outputs three lines:

$ ./cfilter example.txt
804 2 400
805 2 400
2 803 499

cfilter seems to have a bug when T - U == 0. It fails to output the lines 1 801 33 and 802 1 33, though I believe them to be a matching pair.

Now for hfilter and the Scala program by the same author:

$ ln -sf example.txt test.file
$ ./hfilter
804 2 400
2 803 499
805 2 400
2 803 499
3 3 555
3 3 555
$ scala Filterer example.txt /dev/stdout
804 2 400
2 803 499
802 1 33
1 801 33
805 2 400
2 803 499
3 3 555
3 3 555

hfilter also misses the lines 1 801 33 and 802 1 33, but the Scala version finds them. Both programs output 2 803 499 twice (because it is in two matching pairs), but I might ignore such duplication. Both programs also output 3 3 355. This line is in a pair with itself because A = B. This is only correct if the phrase "another input line" includes the same line.

When the input is the random 50 million lines from the Python script, these differences might disappear. The probability that any matching pair has T - U = 0, or any line has A = B, is close to zero when the input has random numbers up to 50 million.


05AB1E, 80 77 bytes

“¢ã,¢ã,¢ã€žžÄ,““èî„‹€€šæ.“"merrily, "4×¨“‚ì€ˆ€³€…žâ.“'-35×Ð)€ª.B3FDÁ})øvy'|ý,

Try it online!

Work in progress.


Jelly, 30 bytes

JŒ!³,$€
Çµy⁴VIAµ€Q⁼$€TðḢịø³JŒ!

Try it online! (Use GṄ³çG as footer to make output prettier. )

Inputs similar to example, e.g. abcdef and [d,a],[a,b],[a,g],[b,c],[b,e],[e,f]

Outputs the list e.g. a,b,c,d,e,f in order.

Note: My program produces different values than the test cases as there are several possibilities which are all valid.

Explanation

JŒ!³,$€                - helper function, generates all possible numberings, input is e.g. 'abcd'
J                      - range(len(input)). e.g. [1,2,3,4]
 Œ!                    - all permutations of the range.
   ³,$                 - pair the input with ...
      €                - each permutation. Sample element e.g. ['abcd',[3,1,2,4]]

Çµy⁴VIAµ€Q⁼$€TðḢịø³JŒ! - main dyadic link, input is e.g. 'abcd' and '[a,b],[b,c],[b,d]'
 µy                    - use a numbering as an element-wise mapping e.g. 'abcd'->[3,1,2,4]
   ⁴                   - apply this to the list of edges. e.g. '[3,1],[1,2],[1,4]'
    V                  - turn this into an internal list.
     IAµ€              - find absolute difference on each edge
         Q⁼            - Is this invariant under deduplication? Returns 1 if the numbering is valid; 0 otherwise.
Ç          $€          - apply this to all possible numberings
             Tð        - return the indices of all valid numberings
               Ḣ       - choose the first one and
                ị      - get the element corresponding to its index in
                 ø³JŒ! - all possible numberings

Save 1 byte by showing all possible solutions:

JŒ!³,$€
Çµy⁴VIAµ€Q⁼$€Tðịø³JŒ!

Try it online! (Use GṄ³çG⁷³G as a footer to make output prettier)

Use converter to copy-paste test case into an input list.


Is 7 l8r than 9? (Is seven later than nine?)

Pyth - 11 bytes
Easy, uses ._ sign to get the sign and C to get char codes.
._-F_CMcz\-

Try it online here.
Test suite.
._               Sign of number
 -F              Fold subtraction (this finds difference of a tuple)
  _              Reverse list to get correct order of operands when subtracting
   CM            Map char, already treats strings as digits of base256 number
    c \-         Split by "-"
     z           Input


Python 2, 30 bytes

lambda n:(2*n^2*n+3)**2==8*n+9

Try it online!

Note that 2*n^2*n+3 is the bitwise xor of 2*n and 2*n+3, because that's Python's operator precedence.


Jelly, 8 bytes

S0rṗLSÞi

Try it online!

Brute-force solution. The first test case is too much for TIO, but I've verified it locally on my laptop. The second test case requires too much RAM, even for my desktop computer.

How it works

S0rṗLSÞi  Main link. Argument: A (array)

S         Compute the sum s of A.
 0r       Create the range [0, ..., s].
    L     Yield the length l of A.
   ṗ      Cartesian power; yield the array of all l-tuples over [0, ..., s], in
          lexicographical order.
     SÞ   Sort the l-tuples by their sums. The sorting mechanism is stable, so
          l-tuples with the same sum are still ordered lexicographically.
       i  Find the index of A in the generated array of tuples.


Python 2, 66 59 bytes

lambda n,k:sum(a%n*(n-a%n)==a/n*(k-a/n)for a in range(n*k))

Try it online!
Each possible rectangle inside the \$n \times k\$-rectangle can be specified by two integers, \$0 \le a \lt n\$ and \$0 \le b \lt k\$:

To verify a rectangle given \$a\$ and \$b\$, it suffices to check if one angle is a right angle. To do this I take the dot product of \$\binom{b}{0}-\binom{0}{a}=\binom{-b}{a}\$ and \$\binom{k-b}{n}-\binom{0}{a}=\binom{k-b}{n-a}\$ to check whether the angle at \$\binom{0}{a}\$ is a right angle:
$$
  \langle \left( \begin{matrix}
-b \\
a \\
\end{matrix}\right), \left(\begin{matrix}
k-b \\
n-a \\
\end{matrix} \right) \rangle = 0 \\\Leftrightarrow a\cdot(n-a)-b\cdot(k-b)=0
\\\Leftrightarrow a\cdot(n-a)=b\cdot(k-b)
$$


C, 32-bit Windows, 987 bytes

#include <windows.h>
#define A CreateCompatibleDC(c)
#define F z=GetPixel(d,x,y);r=z;g=z>>8;b=z>>16
#define C(X,Y) (X<0||Y<0||X>=s[2]||Y>=s[3]||!GetPixel(e,X,Y))
#define D ((C(x-1,y)||C(x+1,y)||C(x,y-1)||C(x,y+1))&&!C(x,y))
#define E(X,Y) ((Z+X-Y)*(Z+X-Y)<2501)
main(int a,int*n){HDC c,d,e,f,w;int x,y,s[9],z,*o,m,t,Z;unsigned char r,g,b,R,G,B;c=GetDC(w=GetDesktopWindow());d=A;e=A;SelectObject(d,f=LoadImage(0,n[1],0,0,0,16));SelectObject(e,LoadImage(0,n[2],0,0,0,16));GetObject(f,24,s+1);o=LocalAlloc(64/*Fixed,ZeroInit*/,8*s[2]*s[3]);for(x=t=Z=s[1]=s[0]=0;x<s[2];x++)for(y=0;y<s[3];y++)if D{F;for(m=0;m<t&&o[m]!=z;m+=2);o[m]=z;o[m+1]++;t+=2*(m>=t);}for(x=y=1;x<t;x+=2)if(o[x]>o[y])y=x;z=o[y-1];R=z;G=z>>8;B=z>>16;for(x=0;x<s[2];x++)for(y=0;y<s[3];y++){F;SetPixel(c,x,s[3]-y-1,(C(x,y)||(E(r,R)&&E(g,G)&&E(b,B)))?0x232323:0x1B0DFC);}SelectObject(c,CreateFont(-(s[2]>>2),0,0,0,400,0,0,0,0,0,0,0,0,"Arial"));SetBkMode(c,1);SetTextColor(c,0xFFFFFF);DrawText(c,"-1",2,s,37);ReleaseDC(w,c);}

The file is saved with LF as line end, not with CR+LF to save some bytes.
The program is written in a way that compiler warnings are generated to save some more bytes.
The file will probably not compile as 64-bit program because the array "s[]" is used to do some implicit castings...
The program takes two images (file names are given via command line):

The first image (first command line argument) is the R/G/B image in Windows .BMP format
The second image is the Alpha channel (black means: 0%, any other colour means: not 0%); the file is also in .BMP format and must have the same size or be larger than the first image

The output image is displayed in the left upper corner of the screen
I couldn't reproduce the boy with the yellow hair. Yellow seems to be too far away (> 50) from white!

Ungolfed version:

#include <windows.h>

/*
 * Although this line costs us 32 bytes
 * Replacing "CreateCompatibleDC(c)" we'll
 * save 42 bytes in the golfed version later
 * so we save 10 bytes using this define!
 */
#define A CreateCompatibleDC(c)

/*
 * Macro: Get a pixel value at (x,y) to z
 * Also get r, g, b
 */
#define F z=GetPixel(d,x,y); \
    r=z; \
    g=z>>8; \
    b=z>>16

/*
 * Macro checking if a pixel is a
 * transparent colour or lies outside the
 * image
 */
#define C(X,Y) (X<0 || Y<0 || X>=s[2] || Y>=s[3] || !GetPixel(e,X,Y))

/*
 * Macro checking if a pixel at (x,y) is a border pixel
 */
#define D ((C(x-1,y) || C(x+1,y) || C(x,y-1) || C(x,y+1)) && !C(x,y))

/*
 * Macro checking if the difference between X and Y is less than 50
 * The variable "Z" must be type "int" and zero. It is used to
 * perform an implicit cast from "BYTE" to "int".
 */
#define E(X,Y) ((Z+X-Y)*(Z+X-Y)<2501)

/*
 * Note that the second argument is "char **",
 * not "int *".
 * We ignore resulting compiler warnings...
 */
main(int a, int * n)
{
    HDC c, d, e, f, w;
    int x, y, s[9], z, *o, m, t, Z;
    unsigned char r, g, b, R, G, B;

    /*
     * Get the HDC handle to the
     * screen (allowing us to create HDCs
     * for accessing bitmap files as well as
     * drawing directly to the screen!)
     */
    c=GetDC(w=GetDesktopWindow());
    /*
     * Create two virtual HDCs for accessing
     * the bitmap files.
     */
    d=A; /* Macro */
    e=A; /* Macro */
    /*
     * Load the two images:
     * The first argument is the image file with
     * the R/G/B channel
     * The second argument is the image file
     * containing the mask defined by the Alpha
     * channel:
     *   Black means = Alpha=0
     *   White means = Alpha>0
     *   (Any other colour means: Alpha>0)
     *
     * Note that "f" is of the type "HBITMAP",
     * not "HDC". We save 4 bytes in the golfed
     * version using HDC instead of HBITMAP and
     * compile the C file with compiler warnings
     * switched off!
     *
     * The second image should have the same size
     * as the first one. However it may be larger
     * than the first one. It must not be smaller!
     */
    SelectObject(d,f=LoadImage(0,n[1],0,0,0,16 /* 16=LR_LOADFROMFILE */));
    SelectObject(e,LoadImage(0,n[2],0,0,0,16));
    /*
     * Get the image information (size)
     */
    GetObject(f,24,s+1);
    /*
     * Search all background colours
     */
    o=LocalAlloc(64 /* Fixed, ZeroInit */,8*s[2]*s[3]);
    for(x=t=Z=s[1]=s[0]=0;x<s[2];x++)
        for(y=0;y<s[3];y++)
            if D
    {
        F; /* Macro */
        for(m=0;m<t && o[m]!=z;m+=2);
        o[m]=z;
        o[m+1]++;
        t+=2*(m>=t);
    }
    /*
     * Search the most common one
     */
    for(x=y=1;x<t;x+=2) if(o[x]>o[y]) y=x;
    z=o[y-1];
    R=z;
    G=z>>8;
    B=z>>16;
    /*
     * Draw the image directly to the screen
     */
    for(x=0;x<s[2];x++)
        for(y=0;y<s[3];y++)
    {
        F; /* Macro */
        /* C and E are macros: */
        SetPixel(c,x,s[3]-y-1,(C(x,y) ||
            (E(r,R) && E(g,G) && E(b,B)))?
            0x232323:0x1B0DFC);
    }
    /*
     * Draw the text over the image
     */
    SelectObject(c,CreateFont(-(s[2]>>2),0,0,0,400,0,0,0,0,0,0,0,0,"Arial"));
    SetBkMode(c,1 /* TRANSPARENT */);
    SetTextColor(c,0xFFFFFF);
    DrawText(c,"-1",2,s,37 /* center, vcenter, singleline */);
    /*
     * Unfortunately DrawText() won't work
     * when not doing this!
     */
    ReleaseDC(w,c);
}


Bubblegum, 165 164 163 162 161 160 bytes

00000000: 1dc6 410a 0231 0c00 c0bf b50a c22a 880a  ..A..1.......*..
00000010: e231 b4c1 0697 6449 5aa5 bede c4cb 303b  .1....dIZ.....0;
00000020: 2046 5bc2 5b1b 0ead 2b59 5a07 f72c 5eb6   F[.[...+YZ..,^.
00000030: bdb2 f9c5 c75f 4ac8 8c7d 09eb cc60 1818  ....._J..}...`..
00000040: c5b5 12bb 1bea a964 886f d425 2b6c cef8  .......d.o.%+l..
00000050: 5e4b 83ee 4aef 49e5 c3d9 23ae f20c 5fa8  ^K..J.I...#..._.
00000060: f759 9193 4894 4a08 ca7f 15f9 e092 1d04  .Y..H.J.........
00000070: df71 3370 7b69 572f 5ec8 625c 51ed 8c3d  .q3p{iW/^.b\Q..=
00000080: 84b1 ded0 bc59 4a53 e093 0443 1566 727d  .....YJS...C.fr}
00000090: 5b9b 4784 0017 e2e7 05b1 3e64 789c 6a3f  [.G.......>dx.j?

Try it online!

Output

  DainesKaineThuneTillisBluntCollinsErnstCoonsEnziBennetKennedyCaseyCassidyCardinCarperMcCainCapitoCrapoCruzSchatzScottBrownCottonCornynCorkerWydenBookerWickerWarnerWarrenHarrisHoevenHassanHatchSasseRischSandersPetersPaulTesterCochranMoranMurrayBurrMurphyLeahyLeeKingReedYoungRounds

How I generated this

Previous versions were generated by simulated annealing, but now I’ve switched strategies to late acceptance hill-climbing.  I’m not sure whether it’s fundamentally better or I just got luckier this time, but I do appreciate that LAHC has fewer parameters to tweak to get good results.

from __future__ import print_function
import random
import zlib

try: range = xrange
except NameError: pass

senators = b'Alexander, Baldwin, Barrasso, Bennet, Blumenthal, Blunt, Booker, Boozman, Brown, Burr, Cantwell, Capito, Cardin, Carper, Casey, Cassidy, Cochran, Collins, Coons, Corker, Cornyn, Cortez Masto, Cotton, Crapo, Cruz, Daines, Donnelly, Duckworth, Durbin, Enzi, Ernst, Feinstein, Fischer, Flake, Franken, Gardner, Gillibrand, Graham, Grassley, Harris, Hassan, Hatch, Heinrich, Heitkamp, Heller, Hirono, Hoeven, Inhofe, Isakson, Johnson, Kaine, Kennedy, King, Klobuchar, Lankford, Leahy, Lee, Manchin, Markey, McCain, McCaskill, McConnell, Menendez, Merkley, Moran, Murkowski, Murphy, Murray, Nelson, Paul, Perdue, Peters, Portman, Reed, Risch, Roberts, Rounds, Rubio, Sanders, Sasse, Schatz, Schumer, Scott, Shaheen, Shelby, Stabenow, Strange, Sullivan, Tester, Thune, Tillis, Toomey, Udall, Van Hollen, Warner, Warren, Whitehouse, Wicker, Wyden, Young'.split(b', ')
assert len(senators) == 100

random.shuffle(senators)
score = 9999
best = score
recent = 65536 * [score]
recent_index = 0

while True:
    old_score = score
    step = random.randrange(2)
    if step == 0:
        i, j = 100, 100
        while i >= 51 and j >= 51:
            i, j = random.sample(range(100), 2)
        senators[i], senators[j] = senators[j], senators[i]
    else:
        i, j, k = 100, 100, 100
        while i >= 51:
            i, j, k = sorted(random.sample(range(101), 3))
        senators[i:k] = senators[j:k] + senators[i:j]

    bound = max(old_score, recent[recent_index])

    z = zlib.compressobj(9, zlib.DEFLATED, -zlib.MAX_WBITS, 9)
    sin = b''.join(senators[:51])
    sout = bytearray(z.compress(sin) + z.flush())
    score = len(sout) * 8
    if score - 7 <= bound:
        for bit in range(7):
            sout[-1] ^= 128 >> bit
            try:
                if zlib.decompress(bytes(sout), -zlib.MAX_WBITS) == sin:
                    score -= 1
                else:
                    break
            except zlib.error:
                break

    if score > bound:
        if step == 0:
            senators[i], senators[j] = senators[j], senators[i]
        else:
            j = i + k - j
            senators[i:k] = senators[j:k] + senators[i:j]
        score = old_score
    elif score < recent[recent_index]:
        recent[recent_index] = score
        if score < best:
            best = score
            print(score, b''.join(senators[:51]).decode())
    recent_index = (recent_index + 1) % len(recent)


Python 2, 1033 1007 924 879 829 787 713 699 692 691 688 687 672 670 664 659 654 648 643 642 630 625 623 620 570 560 554 545 518 514 513 510 505 492 476 454 451 443 bytes
6 bytes saved thanks to Riley
6 bytes saved thanks to Adnan

Since this question is over a year old and still has no answers I thought I'd give it a try.
n,i,o,u="\nI _";R=lambda x:range(1,x-1)
b=open(i).read()
s=b.split(n)
z=max(map(len,s))+3
a=[list(i+x.ljust(z,i))for x in[i]+s+[i]]
for x in R(len(a))*len(b):
 A=a[x];B=a[x+1];C=a[x-1]
 for y in R(z):
    D=A[y-1:y+2];k=B[y];j=A[y+1]
    if(i in[C[y],k]+D+(k==u)*B[y-1:y+2]or"V"==j)&(A[y]==o):A[y]=i
    if"|"==A[y]==C[y]:A[y]={i:"|",j:">",A[y-1]:"<"}[i]
    if[u]*3==D:A[y],B[y]={i:u+k,C[y]:"^"+k,k:" V"}[i]
print n.join(`y`[2::5]for y in a).replace(i,o)

Try it online!
The program reads the table a file named I and prints the table with its chairs to std::out.  I was not sure about a bunch of the edge cases so I took my best judgement (whatever took the least effort) but it seems to pass all the test cases.  Some of the outputs don't match exactly but they all have the same number of chairs.
Explanation
The first line pretty simply sets up some definitions that will save us bytes in the future:
(I will unpack these macros for readability in future lines)
n,i,o="\nI ";R=lambda x:range(1,x-1)

Then we will open a file named I because we already have a variable that is short for that so it saves a few bytes.
b=open("I").read().split("\n")

We split along newlines to create a list of strings (The rows of the image)
s=b.split(n)

I then find the length of the longest line so that I can pad all lines to that length.  (I also add 3 because we need a bit of additional padding)
 z=max(map(len,s))+3

Then we perform the actual padding and create a border of I characters around the edge.  This is because we will need to tell the difference between the inside and the outside of the shape later on.  We will also change the data type from a list of strings to a list of list of characters (length 1 strings).
a=[list("I"+x.ljust(z,"I"))for x in["I"]+s+["I"]]

The next line is just another byte saving definition.
(I will also unpack this one)
B=R(len(a))

Now we want to spread I characters to everywhere outside of the shape.  We can do this with a pseudo-cellular automaton.  Each I will spread to any adjacent   characters.  We could loop until the automaton stabilizes however this cannot take more iterations than there are characters so we just loop through every character in b (the original input)
for _ in b:

For each iteration we want to pass over every character in the 2D list (excluding the outermost padding)
 for x in range(1,len(a)-1):
    A=a[x]  #<--Another definition I will fill in for clarity
    for y in range(1,z-1):

For each position we run the following code:
if("I" in[a[x+1][y],a[x-1][y]]+a[x][y-1:y+2])&(a[x][y]==" "):a[x][y]=" "

Lets break this down.
We have an if with two conditions separated by a & (bitwise and)
The first one simply checks if there is an I in any of the adjacent cells and the second one just checks if the current cell is a " ".  If we pass those conditions we set the current cell to be an I.

Now that we have determined the outside and inside of the shape we can start to place the chairs around the table.
Once again we loop through all of the cells (and set some more shorthands)
for x in range(1,len(a)-1):
 A=a[x]
 for y in range(1,z-1):
        k=a[x+1][y]

Now here's my favorite part.  If you have trudged through my boring, mostly definition based, golfing so far I am going to reward you with a nice tidbit of clever golfing (if I do say so myself).
A little background in python:
In Python if you attempt to assign an dictionary key twice it asigns the latter one.  For example
>>> {1:"a",1:"b"}[1]
'b'

We will abuse this property to assign the current cell to a particular character.
The first condition is
if["_"]*3==a[x][y-1:y+2]:a[x][y],a[x+1][y]={"I":"_"+a[x+1][y],a[x-1][y]:"^ ",a[x+1][y]:" V"}["I"]

If the cell is in the middle of an edge of 3 _ characters we will reassign the current cell and the cell below it.  We will assign it to the result of indexing an overloaded dictionary by I.  We first set our default with the pair "I":"_"+a[x+1][y] this means if there is no change we will assign the two cells back to their original values.  Next we add the pair a[x-1][y]:"^ ".  This wont do anything (important) unless the cell above the current one (a[x-1][y]) is filled with an I.  If it has an I in it it will override the default telling us to place a chair at the current cell.  Next we move on to the cell below the current cell if that cell is I we again override to place an upwards facing chair below the current spot.
The next condition is a tad simpler
if"|"==a[x][y]==a[x-1][y]:a[x][y]={"I":"|",A[y+1]:">",A[y-1]:"<"}["I"]

We check if the current cell and the cell above it are both |.  If so we set up a dictionary.
The first pair in the dictionary "I":"|" sets the default.  Since we are going to access the key I if I does not get reassigned it will default back to | (the character it already is) and do nothing.
We the add the two keys A[y+1]:">",A[y-1]:"<" If either of the two cells to the left and right are I then it will reassign the current cell to a chair pointing in the direction of the outside.

Now we just have to output.  However we can't just print,  there are a couple of housekeeping things we have to do first.  We have to convert back to a string and remove all of the Is we created.  This is done in one line.
print "\n".join(`y`[2::5]for y in a).replace("I"," ")


JavaScript (ES6) 42 74
n=>(n-~(n+'').replace(/./g,8)+'').slice(1)

Test in FireFox console
;[0,1,10,11,42,100,800,1060,10270,100501]
.forEach(x => console.log(x +" -> '" + S(x) + "'"))

Output
0 -> ''
1 -> '0'
10 -> '9'
11 -> '00'
42 -> '31'
100 -> '89'
800 -> '689'
1060 -> '949'
10270 -> '9159'
100501 -> '89390'

How did I think of this?
Given a fixed number of digits, the output sequence is simply ascending, so there is a fixed delta between input and output. Have a look:
  1..10 -> 0..9 (delta -1)
 11..110 -> 00..99 (delta -11)
111..1110 -> 000..999 (delta -111) mmm there's a pattern here...

But the leading 0s are difficult to manage, so I have a standard trick, add a first digit and work modulo (that is, cut the first digit in output). Then -1-> +9, -11 -> +89, -111 -> +889 and so on.
Last step: I don't care what the first digit is, so there is no need to check if the iinput number is < or > than 111... (honestly I found this by trial and error)
Test

var F=
n=>(n-~(n+'').replace(/./g,8)+'').slice(1)

function update()
{
  var i=+I.value
  O.textContent = F(i)
}

update()
<input id=I value=99 type=number oninput='update()'>


Tension on a Graph, Part I: A Wavy String

Python + Pycairo, 727 708 608, + PyLab, 383
from pylab import*
def f(N):
 def P(u,w,N):
    T=lambda v,p:(C(v-u,p-u)>0)==(C(w-v,p-v)>0)==(C(u-w,p-w)>0);M=[(i,n)for i,n in enumerate(N)if T(V([n[0],sin(pi*n[0])+sin(3*pi*n[0])/2]),n)]
    if M:i,n=max(M,key=lambda n:C(n[1]-u,w-u)**2);M=P(u,n,N[:i])+[n]+P(n,w,N[i+1:])
    return M
 V=array;C=cross;a=V([3,0]);plot(*zip(*([-a]+P(-a,a,map(V,sorted(N)))+[a])));N and scatter(*zip(*N));show()

Example
f([(-2.8,-0.7),(-2.5,-0.9),(-1.2,0.2),(-0.5,0.8),(0.5,0.4),(1.2,-0.9),(1.5, -0.6),(1.8, -0.8)])

How it works

 Suppose we know that the taut string passes through two points A and
 B (we can always start with  A = (-3, 0) and B = (3, 0).) As we pull the string, it "wants" to take the shortest path possible between
 A and B, that is, ideally, the segment AB. However, if there are any nails in the area bounded by the function (sin πx + ...)
 and AB, then at least one of them must block the string. In
 particular, the nail(s) farthest away from AB within the said area
 must block the string. Hence, if C is this nail, we know that the
 taut string must pass through C, in addition to A and B. We can
 now repeat the process for the segments AC and CB, and continue in
 this fashion until eventually there are no more intervening nails.

 This is a binary divide-and-conquer algorithm with a linear scan in
 each step, so it has a best-case complexity of O(n log n) and
 worst-case complexity of O(n2).