Find the largest root of a polynomial with a neural network The challenge

Find the smallest feedforward neural network such that, given any 3-dimensional input vector \$(a,b,c)\$ with integer entries in \$[-10,10]\$, the network outputs the largest (i.e., "most positive") root of the polynomial \$x^3+ax^2+bx+c\$ with error strictly smaller than \$0.1\$.

Admissibility

The notion of admissibility in my previous neural net golfing challenge seemed a bit restrictive, so for this challenge, we are using a more liberal definition of feedforward neural network:

A neuron is a function \$\nu\colon\mathbf{R}^n\to\mathbf{R}\$ that is specified by a vector \$w\in\mathbf{R}^{n}\$ of weights, a bias \$b\in\mathbf{R}\$, and an activation function \$f\colon\mathbf{R}\to\mathbf{R}\$ in the following way:

$$ \nu(x) := f(w^\top x+b), \qquad x\in\mathbf{R}^n. $$

A feedforward neural network with input nodes \$\{1,\ldots,n\}\$ is a function of \$(x_1,\ldots,x_n)\in\mathbf{R}^n\$ that can be built from a sequence \$(\nu_k)_{k=n+1}^N\$ of neurons, where each \$\nu_k\colon\mathbf{R}^{k-1}\to\mathbf{R}\$ takes inputs from \$(x_1,\ldots,x_{k-1})\$ and outputs a scalar \$x_k\$. Given some specified set \$S\subseteq\{1,\ldots,N\}\$ of output nodes, then the output of the neural network is the vector \$(x_k)_{k\in S}\$.

Since activation functions can be tuned for any given task, we need to restrict the class of activation functions to keep this challenge interesting. The following activation functions are permitted:

Identity. \$f(t)=t\$
ReLU. \$f(t)=\operatorname{max}(t,0)\$
SoftPlus. \$f(t)=\ln(e^t+1)\$
Sigmoid. \$f(t)=\frac{e^t}{e^t+1}\$
Sinusoid. \$f(t)=\sin t\$

Overall, an admissible neural net is specified by input nodes, a sequence of neurons, and output nodes, while each neuron is specified by a vector of weights, a bias, and an activation function from the above list. For example, the following neural net is admissible, though it does not meet the performance goal of this challenge:

Input nodes: \$\{1,2\}\$
Neurons: \$\nu_k(x_1,\ldots,x_{k-1}):=x_{k-2}+x_{k-1}\$ for \$k\in\{3,\ldots,10\}\$
Output nodes: \$\{5,9,10\}\$

This network consists of 8 neurons, each with zero bias and identity activation. In words, this network computes the generalized Fibonacci sequence generated by \$x_1\$ and \$x_2\$ and then outputs the 5th, 9th, and 10th numbers from this sequence, in that order.

Scoring

Given a real number \$x\$ with terminating decimal expansion, let \$p(x)\$ be the smallest nonnegative integer \$p\$ for which \$10^{-p}\cdot |x|<1\$, and let \$q(x)\$ be the smallest nonnegative integer \$q\$ for which \$10^q \cdot x\$ is integer. Then we say \$p(x)+q(x)\$ is the precision of \$x\$.

For example, \$x=1.001\$ has a precision of \$4\$, whereas \$x=0\$ has a precision of \$0\$.

Your score is the sum of the precisions of the weights and biases in your neural network.

(E.g., the above example has a score of 16.)

Verification

While the roots can be expressed in terms of the cubic formula, the largest root is perhaps most easily accessed by numerical means. Following @xnor's suggestion, I computed the largest root for every choice of integers \$a,b,c\in[-10,10]\$, and the results can be found here. Each line of this text file is of the form a,b,c,root. For example, the first line reports that the largest root of \$x^3-10x^2-10x-10\$ is approximately \$10.99247140445449\$.

Edit: The original file I posted had errors in cases where the polynomial exhibited a multiple root. The current version should be free of such errors.

14,674,000,667 5,436,050 5,403,448 10,385 5,994 4,447  3,806 total precision

For a baseline, I investigated the following approach: Select \$M,\delta,\epsilon>0\$ such that if we sample the polynomial \$p(x)=x^3+ax^2+bx+c\$ at

$$ S:=\{-M,-M+\delta,-M+2\delta,\ldots,M\}, $$

then the largest sample point \$s^\star\in S\$ satisfying \$p(s^\star)<\epsilon\$ necessarily exists and necessarily resides within \$0.1\$ of the largest root of \$p\$. One can show that for our collection of polynomials, one may take \$M=11\$, \$\delta=0.1\$, and \$\epsilon=10^{-4}\$.

To design a neural net that implements this logic, we start with a layer of neurons that sample the polynomial on \$S\$. For each \$s\in S\$, we take

$$ x_{1,s} = s^2\cdot a + s\cdot b + 1\cdot c + s^3. $$

Next, we identify which of these are less than \$\epsilon=10^{-4}\$. It turns out that for \$s\in S\$, it holds that \$p(s)<10^{-4}\$ only if \$p(s)\leq 0\$. As such, we can use relu activations to exactly identify our samples:

$$ \frac{\mathrm{relu}(10^{-4}-t) - \mathrm{relu}(-t)}{10^{-4}} = \left\{\begin{array}{cl}1&\text{if }t\leq 0\\0&\text{if }t\geq 10^{-4}.\end{array}\right.$$

We implement this with a few layers of neurons:

$$ \begin{aligned}
x_{2,s} &= \mathrm{relu}(-1\cdot x_{1,s}+10^{-4}), \\
x_{3,s} & = \mathrm{relu}(-1\cdot x_{1,s}), \\
x_{4,s} &= 10^{4}\cdot x_{2,s}-10^{4}\cdot x_{3,s}. \end{aligned}$$

At this point, we have \$x_{4,s}=1\$ when \$p(s)<10^{-4}\$, and otherwise \$x_{4,s}=0\$. Recall that we seek the largest \$s^\star\$ for which \$x_{4,s^\star}=1\$. To this end, we label \$x_{4,M}\$ as \$x_{5,M}\$ (for notational convenience), and for each \$k\geq 1\$, we iteratively define

$$ x_{5,M-k\delta} = 1\cdot x_{4,M-k\delta}+2\cdot x_{5,M-(k-1)\delta} = \sum_{j=0}^k 2^{k-j}x_{4,M-j\delta}. $$

Thanks to this transformation, every \$x_{5,s}\$ is a nonnegative integer, and \$s^\star\$ is the unique \$s\$ for which \$x_{5,s}=1\$. We may now identify \$s^\star\$ by another application of relu activations:

$$ \mathrm{relu}(t-2)-2\cdot\mathrm{relu}(t-1)+t = \left\{\begin{array}{cl}1&\text{if }t=1\\0&\text{if }t\in\mathbf{Z}_{\geq 0}\setminus\{1\}.\end{array}\right.$$

Explicitly, we define neurons by

$$ \begin{aligned}
x_{6,s} &= \mathrm{relu}(1\cdot x_{5,s} - 2), \\
x_{7,s} &= \mathrm{relu}(1\cdot x_{5,s} - 1), \\
x_{8,s} &= 1\cdot x_{6,s} - 2\cdot x_{7,s} + 1\cdot x_{5s}.
\end{aligned} $$

Then \$x_{8,s}=1\$ if \$s=s^\star\$ and otherwise \$x_{8,s}=0\$. We linearly combine these to produce our output node:

$$ x_9 = \sum_{s\in S} s\cdot x_{8,s} = s^\star. $$

For the score, each layer has neurons with different levels of precision:
(1) \$6+3+1+9=19\$, (2) \$1+4=5\$, (3) \$1\$, (4) \$5+5=10\$, (5) \$1+1=2\$, (6) \$1+1=2\$, (7) \$1+1=2\$, (8) \$1+1+1=3\$, (9) \$3|S|\$. Furthermore, all but two of the layers have \$|S|=221\$ neurons; layer 5 has \$|S|-1\$ neurons and layer 9 has \$1\$ neuron.

Edit: Improvements: (1) We can sample the polynomial much more efficiently using finite differences. (2) We can bypass layers 2 through 4 by instead using a sigmoid activation. (3) The overflow issues in layer 5 can be averted (and subsequent layers can be combined) by more carefully applying relu activations. (4) The final sum is cheaper with summation by parts.

What follows is the MATLAB code. To be clear, prec is a function (found here) that computes the precision of a vector of weights or biases.

function sstar = findsstar2(a,b,c)

relu = @(x) x .* (x>0);

totprec = 0;

% x1 samples the polynomial on -11:0.1:11
x1=[];
for s = -11:0.1:11
    if length(x1) < 5
        w1 = [s^2 s 1];
        b1 = s^3;
        x1(end+1,:) = w1 * [a; b; c] + b1;
        totprec = totprec + prec(w1) + prec(b1);
    else
        w1 = [-1 4 -6 4];
        x1(end+1,:) = w1 * x1(end-3:end,:);
        totprec = totprec + prec(w1);
    end
end

% x4 indicates whether the polynomial is nonpositive
w4 = -6e5;
b4 = 60;
x4=[];
for ii=1:length(x1)
    x4(end+1) = sigmf(w4 * x1(ii) + b4, [1,0]);
    totprec = totprec + prec(w4) + prec(b4);
end

% x6 indicates which entries are less than or equal to sstar
x5 = zeros(size(x1));
x6 = zeros(size(x1));
x5(end) = 0;
x6(end) = 0;
for ii = 1:length(x5)-1
    w5 = [-1 -1];
    b5 = 1;
    x5(end-ii) = relu(w5 * [x4(end-ii); x6(end-ii+1)] + b5);
    totprec = totprec + prec(w5) + prec(b5);
    w6 = -1;
    b6 = 1;
    x6(end-ii) = w6 * x5(end-ii) + b6;
    totprec = totprec + prec(w6) + prec(b6);
end

% a linear combination produces sstar
w7 = 0.1*ones(1,length(x1));
w7(1) = -11;
sstar = w7 * x6;

%disp(totprec) % uncomment to display score

end


Dancing arrays. Output them with some forward-backward moves The task is to create a program (or a function), which outputs array elements  in the order, determined by two numbers F and B. F is number of elements to print, B is the rollback distance (from last printed element). Each element must be printed on separate line and blank line must be inserted after each rollback. Run till the end of array. If endless loop or backward progression requested, program should print nothing and exit. Same for empty arrays.

F and B cannot be negative numbers. Be positive while dancing!

For example, if given:

array is 2, 3, 5, 7, 11, 101, 131;
F is 4;
B is 1;

then output must be:

2
3
5
7

5
7
11
101

11
101
131

Init array, F and B as you like.

Shortest code wins. Imperative beauty will be enjoyed.

Test cases:

Empty array.
Any F.
Any B.

Produces no output (array is empty).

Array: [42]
F = 0;
B = 1;

Produces no output (zero elements to print).

Array: [42, 17, 84]
F = 2;
B = 1;

Produces no output (endless printing).

Array: [7, 16, 65]
F = 2;
B = 3;

Produces no output (will be moving backward to negative indices).

Array: [7, 16, 65]
F = 2;
B = 0;

Output:

7
16

16
65

Array: [7, 16, 65]
F = 3;
B = 2;

Output:

7
16
65

(no rollback, end of array is reached).

Array: [7, 16, 65]
F = 17;
B = 15;

Output:

7
16
65

(run till the end)

Array: [7, 16, 65]
F = 17;
B = 16;

Output:

7
16
65

Whole array can be printed in first iteration, run till the end is working, even if F and B form endless-loop condition.

Python 2, 135 128 126 bytes

Pretty naive solution:

a,f,b=input()
b+=1
l=len(a)
i=0
e=min(l,f)
while f>b:
    print'\n'.join(map(str,a)[i:e])+'\n';i=e-b
    if e==l:f=b
    e=min(l,e+f-b)

Try it online!

Input format is [array], F, B except you can also use (). (You can't use {} because that's unordered; thanks to Felipe Batista for pointing that out because I forgot).
Output format is as specified in the challenge, with a single trailing newline at the end of all output and no leading whitespace.

-7 bytes by changing if f>b: while 1: to while f>b
-2 bytes by changing break to f=b because that causes the while loop to exit.


Number of distinct non-empty subsequences of binary expansion A subsequence is any sequence that you can get from another by deleting any amount of characters. The distinct non-empty subsequences of 100 are 0, 1, 00, 10, 100. The distinct non-empty subsequences of 1010 are 0, 1, 00, 01, 10, 11, 010, 100, 101, 110, 1010.

Write a program or function that given a positive integer n returns the number of distinct non-empty subsequences of the binary expansion of n.

Example: since 4 is 100 in binary, and we saw that it had five distinct non-empty subsequences above, so f(4) = 5. Starting from n = 1, the sequence begins:

1, 3, 2, 5, 6, 5, 3, 7, 10, 11, 9, 8, 9, 7, 4, 9, 14, 17, 15, 16, 19, 17, 12

However, your program must work for any n < 250 in under a second on any modern machine. Some large examples:

f(1099511627775) = 40
f(1099511627776) = 81
f(911188917558917) = 728765543
f(109260951837875) = 447464738
f(43765644099) = 5941674

Python 3, 95 bytes  83 bytes

[-12 bytes thanks to Mr.XCoder :)]

def f(x):
 v=[2,1];c=1
 for i in bin(x)[3:]:k=int(i);c+=v[k];v[1-k]+=v[k]
 return c

Try it online!

A note on the algorithm.
The algorithm computes the increment in unique subsequences given by the bit at a given position t.
The increment for the first bit is always 1. The algorithm then runs over the sequence of bits s(t) and adds the increment v[s(t)]. At each step, the increment for the complement of s(t), v[1 - s(t)] is updated to v[1]+v[0].
The final number is the sum of all increments.

It should run in O(log2(n)), where n is the input number.


Roll my D&D character's ability scores In Dungeons and Dragons, some of the most important atributes of a character are the ability scores. There are 6 ability scores, for the six abilities. The abilities are Strength, Dexterity, Constitution, Intelligence, Wisdom and Charisma.

When determining the scores for a character, I use the following procedure: Roll 4d6, drop the lowest, in any order. What this means is that I roll 4 six sided dice, ignore the lowest result, and sum the other 3. This is done 6 times. The resulting numbers are assigned to the abilities in any way I please.

The system I use for assigning scores to abilities is to assign the highest score to my character's most important skill, which depends on my character's class, assign the second highest score to Constitution, since everyone needs Constitution, and assign the other four scores arbitrarily.

Here's a table of the most important skills for various classes:

Bard - Charisma
Cleric - Wisdom
Druid - Wisdom
Fighter - Stregth
Monk - Wisdom
Paladin - Charisma
Rogue - Dexterity
Sorcerer - Charisma
Wizard - Intelligence

Challenge: I'll give you (as input) the first letter of my character's class (In uppercase). I'd like you to roll the abilities scores and assign them to the abilities as described above, and then output them in the order Strength, Dexterity, Constitution, Intelligence, Wisdom, Charisma.

Example:

Input: R
Rolls: 4316 3455 3633 5443 2341 6122
Scores: 13 14 12 13 9 10
Ordering: Highest goes to dexterity. Second goes to Constitution.
Output: 13 14 13 12 9 10
or
Output: 9 14 13 10 12 13
or etc.

Output may be given in any format where the numbers are clearly separated and in the proper order.

Shortest code in bytes wins. Standard loopholes banned.

CJam, 43 41 40 bytes

{6a4*:mr$0Zt:+}6*]$2m<"FRXWCDM"r#4e<3e\p

Thanks to @Sp3000 for golfing off 1 byte.

Try it online in the CJam interpreter.

How it works

{             }6*                       e# Repeat 6 times:
 6a4*                                   e#   Push [6 6 6 6].
     :mr                                e#   Replace each six with a pseudo-randomly
                                        e#   generated integer in [0 ... 5].
        $                               e#   Sort the results.
         0Zt                            e#   Replace the lowest result by 3.
            :+                          e#   Add all four integers
                ]                       e# Wrap the 6 generated integers in an array.
                 $                      e# Sort.
                  2m<                   e# Rotate 2 units to the left to assign the
                                        e# second highest result to Constitution.
                     "FRXWCDM"          e# Push that string.
                              r#        e# Find the index of the input.
                                        e# The string doesn't contain B, P or S, so
                                        e# those push -1.
                                4e<     e# Truncate the index at 4. This way, C, D
                                        e# M all push 4.
                                   3e\  e# Swap the integer at that index with the
                                        e# one at index 3, i.e., the highest one.
                                      p e# Print.


Smallest Narcissistic Number Given a natural numbers n>1, find the smallest narcissistic number of n digit.
A narcissistic number is a number which is the sum of its own digits, each raised to the power of the number of digits.
For example, for n=3 (3 digits) the out put should be 153:
1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153
For n=4 (4 digits) the out put should be 1634:
1^4 + 6^4 + 3^4 + 4^4 = 1 + 1296 + 81 + 256 = 1634
For n=5 (5 digits) the out put should be 54748:
5^5 + 4^5 + 7^5 + 4^5 + 8^5 = 54748
If there is no such numbers, like for example n = 2 or n = 22 output any special output (a negative number, an exception, an error, empty,...).
Winning Criteria
This is code-golf, so shortest answer in bytes by language wins.
OEIS A005188

05AB1E, 16 15 bytes

Very inefficient.
Empty output if there is no solution.

°LʒDSImOQ}ʒgQ}н

Try it online!


Recreate the ASCII-table as an ASCII-table Frequently while I'm code-golfing, I'll want to know what the ASCII value of a certain character is. One of my favorite resources for quickly looking up all of the printable ASCII characters is ASCIItable.com. This has a really nice image that not only shows the printable ASCII characters and their values, but also the unprintable and extended characters, and the values in hexadecimal, octal, and HTML:

Today's challenge is to recreate that ASCII table as an ASCII table instead of an image. To keep things simpler, we will not use control-characters (characters below 32) and we'll only show the decimal value and the character. In other words, your challenge is to write either a full-program or a function that prints or returns the following text:

Dec  Chr   | Dec  Chr   | Dec  Chr
----------------------------------
32   Space | 64   @     | 96   `
33   !     | 65   A     | 97   a
34   "     | 66   B     | 98   b
35   #     | 67   C     | 99   c
36   $     | 68   D     | 100  d
37   %     | 69   E     | 101  e
38   &     | 70   F     | 102  f
39   '     | 71   G     | 103  g
40   (     | 72   H     | 104  h
41   )     | 73   I     | 105  i
42   *     | 74   J     | 106  j
43   +     | 75   K     | 107  k
44   ,     | 76   L     | 108  l
45   -     | 77   M     | 109  m
46   .     | 78   N     | 110  n
47   /     | 79   O     | 111  o
48   0     | 80   P     | 112  p
49   1     | 81   Q     | 113  q
50   2     | 82   R     | 114  r
51   3     | 83   S     | 115  s
52   4     | 84   T     | 116  t
53   5     | 85   U     | 117  u
54   6     | 86   V     | 118  v
55   7     | 87   W     | 119  w
56   8     | 88   X     | 120  x
57   9     | 89   Y     | 121  y
58   :     | 90   Z     | 122  z
59   ;     | 91   [     | 123  {
60   <     | 92   \     | 124  |
61   =     | 93   ]     | 125  }
62   >     | 94   ^     | 126  ~
63   ?     | 95   _     | 127  DEL

Trailing spaces on each line, and a trailing newline are permitted. Since this is a kolmogorov-complexity challenge, your submission may not take any input, or access any external resources (such as a file or the web), and your goal is to compress the code to output this text as much as possible.

Standard loopholes apply, and the shortest answer in bytes wins. Happy golfing!

Python 2 3.6, 185 183 175 159 156 bytes

Saved 8 bytes thanks to FlipTack!

Still quite new to golfing in Python.

for a in["Dec  Chr   | "*3,"-"*39]+["".join(f"{l:<5}{('Space',chr(l),'DEL')[(l>32)+(l>126)]:<6}| "for l in(i,32+i,64+i))for i in range(32,64)]:print(a[:-5])

Uses a nested list comprehension to generate the table body.

Ungolfed:

lines =   \
  ["Dec  Chr   | "*3, "-"*39] +                      # first two lines
    ["".join(                                        # join 3 parts of each line
      f"{l:<5}{('Space',chr(l),'DEL')[(l>32)+(l>126)]:<6}| "
        for l in (i,32+i,64+i)                       # generate 3 parts of a line
      )
      for i in range(32,64)]

for line in lines: print line[:-5]

Update: apparently using f-string here is shorter than the % operator.

Old attempt, 185 183 175 bytes

print("Dec  Chr   | "*3)[:-5]+"\n"+"-"*34
a=lambda x:('Space',chr(x),'DEL')[(x>32)+(x>126)]
for l in range(32,64):print("%-5d%-6s| "*3%(l,a(l),l+32,a(l+32),l+64,a(l+64)))[:-5]

Ungolfed:

print ("Dec  Chr   | "*3)[:-5] + "\n" + "-"*34
def a(x):
    return "Space" if x==32 else "DEL" if x==127 else chr(x)
for line in range(32,64):
    print ("%-5d%-6s| "*3 % (line, a(line), line+32, a(line+32),
      line+64, a(line+64))) [:-5]


Numbers as Circular Graphics First, study this puzzle to get a feel for what you will be producing.

Your challenge is to write a program or function which will output a circular graphic like the ones from the puzzle, given a (base 10) number between 1 and 100 (inclusive). This is similar to this challenge, except that you will be producing a graphic rather than roman numerals. The following circles represent the numbers 1-10, from left to right:

As the answer to the puzzle states, your graphic should read like a roman numeral from the inside-out, where the line thickness represents the roman numeral symbols and the entire graphic represents the number. For your reference, here are the line thicknesses which you will need. Each line should have a 3px padding between it and the next.

Number  Roman Numeral   Line Width
1       I               1px
5       V               3px
10      X               5px
50      L               7px
100     C               9px

Please post a sample or two of your output. Assume input is correct, standard loopholes, etc and so forth. This is code golf, so fewest bytes win. In the event of a tie, most votes win. Good luck!

Mathematica - 166 181 bytes

A bit more concise than the other Mathematica answer, thanks in part to a more point-free style.

c = Characters; r = Riffle;
Graphics[r[{0, 0}~Disk~# & /@ Reverse@Accumulate[
    l = {3} ~Join~ r[2 Position[c@"IVXLC", #][[1, 1]] - 1 & /@
        c@IntegerString[#, "Roman"], 3]], {White, Black}],
    ImageSize -> 2 Total@l] &

All whitespace is for clarity only. This defines an anonymous function which returns the desired graphic.

Animation

Generating an animated GIF of the number circles is trivial in Mathematica, which has built-in functions for animating and exporting sequences of arbitrary objects. Assuming the above code has just been executed,

Table[Show[%@n, PlotRange -> {{-100, 100}, {-100, 100}},
    ImageSize -> 200], {n, 1, 399, 1}];
Export["animcircles.gif", %]

Example Output


Interlaced Rotations Challenge

Given a square matrix of characters (single-byte printable ASCII characters), rotate each "ring" of the matrix in opposite directions.

Let's take an example:

1 2 3 4 5
6 7 8 9 A
B C D E F
G H I J K
L M N O P

Then, the outermost ring is rotated clockwise 90 degrees, like so:

1 2 3 4 5    L G B 6 1
6       A    M       2
B       F => N       3
G       K    O       4
L M N O P    P K F A 5

The second ring is rotated counterclockwise 90 degrees:

7 8 9    9 E J
C   E => 8   I
H I J    7 C H

The final ring is rotated clockwise 90 degrees, but since it is a single number (letter in our example), then it is not really affected.

The final result is:

L G B 6 1
M 9 E J 2
N 8 D I 3
O 7 C H 4
P K F A 5

If the matrix has an even side length, the innermost ring will be a 2x2 square and should still be rotated.

Input

A list of lists in any reasonable standard format. For example, a newline-delimited space-delimited string or a list of space-delimited strings is acceptable, but a list of the values as rings around the matrix is not acceptable.
The characters are not necessarily unique.

Output

A list of lists in any reasonable standard format. Same rules as the input.

Test Cases

1 2 3    7 4 1
4 5 6 => 8 5 2
7 8 9    9 6 3

1 2 3 4 5 6    Y S M G A 1
A B C D E F    Z E K Q W 2
G H I J K L => ! D O I V 3
M N O P Q R    @ C P J U 4
S T U V W X    # B H N T 5
Y Z ! @ # $    $ X R L F 6

Credits

Heavily inspired by a related challenge that rotates each element counterclockwise one position (not by 90 degrees).

Haskell, 94 bytes

An anonymous function taking and returning a list of Strings.

Use as (cycle[t.r,r.t,r.t,r.t]?)["123", "456", "789"].

(cycle[t.r,r.t,r.t,r.t]?)
(g:h)?(a:b)=g$a:h?t(r b)
_?a=a
r=reverse;t=zipWith(:)`foldr`repeat[]

Try it online!

How it works

r is reverse. t is one byte shorter than importing Data.List.transpose. t.r rotates a list of lists 90 degrees clockwise, and r.t rotates it counterclockwise.
The operator ? takes two arguments, a list of functions and a matrix as a list of strings.

An empty matrix is just returned.
Otherwise, ? strips the first function f off the list of functions, and the first line a off the matrix.
Then it rotates the remainder b of the matrix clockwise, and recurses with that and the remaining functions. This gradually strips the matrix from the outside in, one ring each four steps.
Then it prepends the original line a to the result, and applies the function f to it to adjust the orientation of the matrix.

The anonymous function calls ? with the input matrix as a list of strings, and an infinite list of functions, which repeats cyclically every four steps.

For most of the steps the function is counterclockwise rotation, which undoes the implicit clockwise rotation done by ? when recursing.
However, the first step and every fourth step afterwards is instead clockwise rotation.

This function is applied when a ring of the matrix is complete, causing each ring to be 180 degrees rotated with respect to the next one.
By luck, this is also the correct transformation to apply to the final, completed matrix to get the final result.


Help, I'm trapped in a Sierpinski triangle! Drawing the Sierpinski triangle has been done to death. There's other interesting things we can do with it though. If we squint hard enough at the triangle, we can view upside-down triangles as nodes of a fractal graph. Let's find our way around that graph!

First, let's assign a number to each node. The largest upside-down triangle will be node zero, and then we just go down layer by layer (breadth-first), assigning consecutive numbers in the order top-left-right:

Click for larger version where the small numbers are a bit less blurry.

(Of course, this pattern continues ad infinitum inside the blue triangles.) Another way to define the numbering is that the centre node has index 0, and the children of node i (adjacent triangles of the next-smaller scale) have indices 3i+1, 3i+2, and 3i+3.

How do we move around this graph? There are up to six natural steps one can take from any given triangle:

One can always move through the midpoint of one of the edges to one of the three children of the current node. We'll designate these moves as N, SW and SE. E.g. if we're currently on node 2, these would lead to nodes 7, 8, 9, respectively. Other moves through the edges (to indirect descendants) are disallowed.
One can also move through one of the three corners, provided it doesn't touch the edge of the triangle, to either the direct parent or one of two indirect ancestors. We'll designate these moves as S, NE and NW. E.g. if we're currently on node 31, S would lead to 10, NE would be invalid and NW would lead to 0.

The Challenge

Given two non-negative integers x and y, find the shortest path from x to y, using only the six moves described above. If there are several shortest paths, output any one of them.

Note that your code should work for more than just the 5 levels depicted in the above diagram. You may assume that x, y < 1743392200. This ensures that they fit inside a 32-bit signed integer. Note that this corresponds to 20 levels of the tree.

Your code must process any valid input in less than 5 seconds. While this rules out a brute force breadth-first search, it should be a fairly loose constraint — my reference implementation handles arbitrary input for depth 1000 in half a second (that's ~480-digit numbers for the nodes).

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

The output should be a flat, unambiguous list of the strings N, S, NE, NW, SE, SW, using any reasonable separator (spaces, linefeeds, commas, ","...).

Standard code-golf rules apply.

Test Cases

The first few test cases can be worked out by hand using the diagram above. The others ensure that answers are sufficiently efficient. For those, there may be other solutions of the same length that are not listed.

0 40                    => N N N N
66 67                   => S SW N N N
30 2                    => NW NW -or- NE SW
93 2                    => NE SW
120 61                  => NW NW NW NW N SE SW N
1493682877 0            => S S NW NW
0 368460408             => SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE
1371432130 1242824      => NW NW NE NW N SE SW SW SW SE SE SW N N N N SW
520174 1675046339       => NE NW NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW
312602548 940907702     => NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW
1238153746 1371016873   => NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N
547211529 1386725128    => S S S NE NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N
1162261466 1743392199   => NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE

Python 2, 208 205 200 bytes

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

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

Explanation

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

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

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

Click the image for a larger version.

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

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

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

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

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

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

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

Python 2, 271 266 261 bytes

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

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

Results

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

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

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

Golfed Version

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

Efficient Version

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


Hexadecimal, octal, binary, oh my! This is a code golf puzzle: shortest byte count wins. The program should do the following (standard loopholes obviously forbidden):

Input a hexadecimal number
Convert to octal
Then interpret the digits as if in decimal (765 octal -> 765 decimal)
Divide the number by two
Convert to hexadecimal

Example:
Input: 4a3d
Output: 5809.8
4a3d -> 45075 -> 45075 -> 22537.5 -> 5809.8

Javascript,56 53 52 bytes
-3 bytes thanks to @ovs
-1 byte thanks to @Arnauld
p=parseInt,a=>(p(p(a,16)[s='toString'](8))/2)[s](16)

toString on an integer converts the integer to a string in that base.
Try it online!


Queueing With Friends You're with your best bud, Jim, at the amusement park and as your favorite ride comes into view, you and Jim exchange glances. Naturally you race to get in line. Unfortunately he wins because you're a golfer and he plays a real sport (sorry friends). In fact, you're so far behind that you and Jim are separated by x people. Assuming the line is length n and you're at the back and the line zigs and zags every j people, at what positions in the line will you and Jim be in the same column allowing you to chat (only one row apart)?

Input

3 Integers

n - The length of the line. This number will always be greater than  or equal to j and will be in the form y * j where y is a positive integer (the number of rows in the queue).
j - The number of people in one row of the line (the number of columns in one row). This number will always be greater than 0.
x - The number of people between you and Jim such that 0 <= x < 2j - 1. Hint: If this number is odd, then your output should be empty.

Output

A list of integer positions in the line at which Jim is in the same column as you.

1 These integers can be 0 or 1-indexed as long as you specify in your answer.

2 These integers can assume you start at position 0 or position n-1 as long as you specify in your answer.

Example

In this example, the input would be n = 9, j = 3, x = 0. The output should be 2, 5 because your position is 2 or 5 when you're in the same column as Jim

Test Cases

[9, 3, 0] -> [2, 5]
[12, 3, 0] -> [2, 5, 8]
[9, 3, 1] -> []
[9, 3, 2] -> [1, 4]
[14, 7, 10] -> [1]
[24, 4, 6] -> [0, 4, 8, 12, 16]

Scoring

This is code-golf, so the shortest answer (in bytes) wins.

Python 2, 45 41 40 37 bytes

lambda n,j,x:range(j-x/2,x%2or n-x,j)

Pretty much the trivial solution. I just quickly scanned for patterns and found a pattern. 1-indexed, 1 is at the back of the queue.

-4 bytes by avoiding ternaries and using an array for the values instead
-1 byte thanks to some inspiration from @DeadPossum, by using and instead of ternaries or array selectors
-3 bytes by switching to or in the opposite order. Only works because of 1-indexing

Also, crossed out 4 is still 4 on all of the 4s :(

Try it online!


Where did Jill end up? Jill lives in the (magnetic) north pole. One day, Jill decided to go for a walk, travelling in the four directions (north, east, west, south) for some lengths, with the help of a compass. Your task is to find whether Jill ended up where Jill lives, i.e. the magnetic north pole.

Only south is defined at the north pole. Walking north or south changes the latitude, while walking east or west changes the longitude. The longitude is not defined at the north pole. As a result, Jill would have ended up at the north pole if and only if the distances Jill walked to the south sum up to be equal to the sum of the distances Jill walked to the north, and the distance Jill walked east and west do not matter.

Input

A list of pairs of (direction, amount). The input shall be valid. The amounts will be integers. Acceptable formats include:

"N200"
"200N"
200i (complex number)
(0, 200) (0123 for NESW)
(200,0) (the above reversed)

Output

Two consistent values, one for the case that Jill did end up in the magnetic north pole, and one for the case that Jill did not.

Testcases

Truthy inputs:

S100, E50, N50, W50, N50
S10, E1000, S30, W400, S10, W10, N50
S30, N30
S10, E50, E50, N10

Falsey inputs:

S100
S10, E314, N5
S300, W135, S10, E35, N290

Scoring

This is code-golf. Shortest answer in bytes wins. Standard loopholes apply.

Jelly, 3 bytes

SĊṆ

Input is in form of complex numbers, which will be real or purely imaginary.

Try it online!

How it works

SĊṆ  Main link. Argument: A (array of directions)

S    Take the sum of A.
 Ċ   Get the imaginary part of the sum.
  Ṇ  Take the logical NOT of the imaginary part.


Find all the Anagrams, and the Subanagrams too! This question is heavily based off this question, but should pose a number of additional difficulties.
Your Task
You must write a program or function that, when receiving a string, prints out all possible anagrams of it.  For the purpose of this question, an anagram is a string that contains the same character as the original string, but is not the original string.  A subanagram is an anagram of a substring of an inputted string.  Anagrams and subanagrams do not have to be or contain actual words.
Input
You may accept a string, which may be of any length > 0, by any standard input method.  It may contain any ASCII characters.
Output
You may output all of the possible anagrams and subanagrams of the inputted string in any standard way. You must not output the same string twice, or output a string equal to the input.
Other Rules
Standard Loopholes are disallowed
Scoring
This is code-golf, least bytes wins.

Brachylog (2), 7 bytes

{sp}ᶠdb

Try it online!

Explanation

{sp}ᶠdb
{  }ᶠ    Find all
  p        permutations of
 s         a substring of {the input}
     d   Remove duplicates (leaving the list otherwise in the same order)
      b  Remove the first (the input itself)


Convert Between Percentages and Decimal I, uh....honestly can't believe we don't have this one yet.

Challenge

Write two functions or programs that:

Convert from decimal to percentage
Convert from percentage to decimal

You may also write a single program that does both of the above.

Format

Percentages must be taken and returned with a percent sign. (In many languages, this means they will be strings.) They may be integers or floating point numbers.

Decimals are just floating point numbers.

You do not need to handle rounding errors involving very large or very small floating point numbers.

In cases where the numbers are integers (such as 56.0) you may return 56, 56., or 56.0. (This is intended to make I/O more flexible.)

Test Cases

    0.0% <-> 0.0
  100.0% <-> 1.0
   56.0% <-> 0.56
  123.0% <-> 1.23
  -11.0% <-> -0.11
-214.91% <-> -2.1491

Scoring

This is code-golf, so the shortest answer in each language wins. If you write two separate programs, add their sizes for your score.

Mathematica, 34+20=54
to Decimal
ToExpression@StringDrop[#,-1]/100&

to Percentage
ToString[100#]<>"%"&


Write a time machine quine Write a program that takes as input a string and an integer n, and outputs:

The string that was passed to the program n times ago;
A new program that will be used for the next invocation.

You cannot store any data outside of the program, and your program cannot call previous programs in the chain. If the string does not exist, output an empty string (but still output the next program).

Example run, where I use the notation program_n for each successive program (Of course, [This text is the nth program] would be replaced with actual code.)

$ program_1 "One" 1
[This text is the second program]
$ program_2 "Two" 1
One
[This text is the third program]
$ program_3 "Three" 2
One
[This text is the fourth program]
$ program_4 "Four" 2
Two
[This text is the fifth program]
$ program_5 "Five" 1
Four
[This text is the sixth program]

CJam, 25

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

Try it online

Explanation:

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

The block:

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

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


Convert ciphered Roman numerals to Arabic decimals Write an algorithm to interpret a sequence of letters as a Roman numeral. (see roman numeral rules below)

Each distinct letter has a matching Arabic decimal value, no maximum.  But you don't have the key beforehand, so {A=10, I=1, X=5, ... Z=1000000} is decided by your interpretation.

Challenge

Read input via STDIN or equivalent and write output via STDOUT or equivalent
Valid inputs are combinations of uppercase and lowercase letters i.e. matching \[a-zA-Z]+\
Input should be validated to see if the letter sequence can be interpreted as valid Roman numeral
If the input passes validation, valid output should be the lowest Arabic decimal interpretation and the key used i.e. Aa is interpreted as 4 {a=5, A=1} not 6 {A=5, a=1} or 9 {a=10, a=1}

Roman Numeral Rules

Only letters representing powers of ten can be repeated, maximum of three times successively and four times in total e.g. II III XXXIX
If one or more letters are placed after another letter of greater value, add that amount

AAaa   => 22 {A=10, a=1}          (20 + 2 = 22)
bbAAaa => 222 {b=100, A=10, a=1}  (200 + 20 + 2 = 222)

If a letter is placed before another letter of greater value, subtract that amount

Aa    => 4 {a=5, A=1}                 (5 – 1 = 4)
AaA   => 19 {A=10, a=1}               (10 + 10 – 1 = 19)
BbBaA => 194 {B=100, b=10, A=5, a=1}  (100 + 100 - 10 + 5 - 1 = 194)

Several rules apply for subtracting amounts from Roman numerals:

Only subtract powers of ten i.e. 1, 10, 100... not 5, 50, 500...
No double subtraction therefore 18 is written as XVIII not IIXX (10 + 10 - 1 - 1)
Do not subtract a number from one that is more than ten times greater.
You can subtract 1 from 5 or 10 but not from 50, 100, 500...

Example

Input:

Aa
BAa
CCCXLVII
MMMCDVII
ABADDF
XVVX
FAASGSH
DXCCDA
AaBbcDEf

Output:

4 {a=5, A=1}
14 {B=10, a=5, A=1}
347 {C=100, L=50, X=10, V=5, I=1}
347 {M=100, D=50, C=10, V=5, I=1}
1921 {A=1000, B=100, D=10, F=1}
'XVVX' failed Roman numeral test
7191 {F=5000, A=1000, S=100, G=10, H=1}
'DXCCDA' failed Roman numeral test
4444 {a=5000, A=1000, b=500, B=100, D=50, c=10, f=5, E=1}

Python 2, 415 444 440 419 416 bytes

There aren't all that many Roman numerals, after all. This script creates all of them and checks all permutations of the input, then returns the smallest match.

a=raw_input()
g=range
b=list(set(a))+[' ']*9
from itertools import*
c=[]
s={}
u=1000
for i in g(10*u):
 t,f=(10*u,9*u,5*u,4*u,u,900,500,400,100,90,50,40,10,9,5,4,1),i;r=""
 for j in g(17):k=i/t[j];r+=('W MW Q MQ M CM D CD C XC L XL X IX V IV I').split()[j]*k;i-=t[j]*k
 s[r]=f
for i in permutations(b[:9]):
 r=''
 for j in a:r+='IVXLCMQWE'[i.index(j)]
 if r in s:c+=[s[r]]
print c and min(c)or'%s failed Roman numeral test'%a


"Sorry, young man, but it's Turtles all the way down!" Execute a Lindenmayer System

A Lindenmayer System (or L-system) is related to Thue and Post systems, and is used in botanical modeling and fractal generation.

An L-system is described by string-rewriting where a symbol from the symbol-alphabet is mapped to a replacement sequence of symbols. A collection of these mappings constitutes the L-system proper.

The graphical output method as devised by Prusinkiewicz interprets the resulting sequence after the mappings have been applied to an initial sequence for a specified number of iterations, as Turtle-Drawing commands: forward, backward, left, right, that kind of stuff. This may require extra code to control the scale of the drawing as different iteration counts may produce drastically differently-sized images.

Your task is to execute an L-system in the fewest number of characters. Your program must be able to render both the Dragon Curve and the Branching Stems from the Wikipedia page by providing appropriate input (file, command-line, but external to the source, please).

This is code golf.

Edit: Here are some examples I've posted around town. answer to SO/rotate-to-north {Where I first discovered the L-system}, answer to SO/how-to-program-a-fractal, answer to SO/recursion-in-postscript, comp.lang.postscript discussion/recital, postscript l-system collection, codegolf.SE/draw-a-sierpinski-triangle {origin of the competition between myself and thomasW}.

Mathematica 200 198 188 171 168

Spaces added for clarity:

f[i_, b_, h_, j_, r_, n_] :=
 (a = h; p = j; s = k = {}; t = Flatten;
  (Switch[#,
      6, s = {a, p, s},
      8, {a, p, s} = s,
      _C, k = {k, Line@{p, p += {Cos@a, Sin@a}}}];
     If[# < 9, a += I^# b ]) & /@ t@Nest[# /. r &, i, n];
  Graphics@t@k)

Where:

  i : Initial state;
  b : rotation angle
  h : initial angle
  j : initial position
  r : production rules
  n : iterations

Production rules grammar:

  2 = Turn Left (-);
  4 = Turn Right (+);
  6 = Push and Turn Left  ("[");
  8 = Pop  and Turn Right ("]");
  C[i] = Draw (Any number of symbols)
  Any other symbol = Do Nothing, just use it in producing next state (Any number of symbols)

The {2,4,6,8} sequence is there because I'm using I^n (I = imaginary unit) to make turns.

Examples:

f[{C[1], X}, Pi/2, 0, {0, 0}, {X -> {X, 4, Y, C[1]}, Y -> {C[1], X, 2, Y}}, 10]

f[{C@1}, Pi/2, 0, {0,0}, {C@1->{C@1, 2, C@1, 4, C@1, 4, C@1, 2, C@1}}, 6]

f[{C[1]}, Pi/4, Pi/2, {0, 0}, {C[2] -> {C[2], C[2]}, C[1] -> {C[2], 6, C[1], 8, C[1]}}, 10]

f[{C[1]}, Pi/3, 0, {0, 0}, {C@1 -> {C@2, 4, C@1, 4, C@2}, C@2 -> {C@1, 2, C@2, 2, C@1}}, 10]

f[{X},5/36 Pi, Pi/3, {0,0},{X->{C@1, 4, 6, 6, X, 8, 2, X, 8, 2, C@1, 6, 2, C@1, X, 8, 4, X},
                            C@1->{C@1, C@1}}, 6]


A function to take three integers and return a list of integers and alphabet-letters Challenge
We take three positive integers a, b, and c as input. Using these integers, first create a sequence in the range [0, c] (inclusive on both ends), in steps of b. For example, for a=4, b=2, c=100, the sequence would be [0,2,4,...,96,98,100].
For every number in this sequence which is divisible by a, replace it with the next letter in the lowercase alphabet, starting with the letter 'a' and  wrapping back around to 'a' after you reach 'z'.
Example:
Input: a=4, b=2, c=100
Output: a2b6c10d14e18f22g26h30i34j38k42l46m50n54o58p62q66r70s74t78u82v86w90x94y98z
Challenge rules:

You can assume that a, b, and c are positive integers only, where b ≤ a ≤ c.
You can assume a is a multiple of b.
You can assume c is divisible by b.
The preferred output is a single concatenated string as above, but a list/array is acceptable as well.

Test cases:
Input: a=4, b=2, c=100
Output:
a2b6c10d14e18f22g26h30i34j38k42l46m50n54o58p62q66r70s74t78u82v86w90x94y98z

Input: a=9, b=3, c=174
Output:
a36b1215c2124d3033e3942f4851g5760h6669i7578j8487k9396l102105m111114n120123o129132p138141q147150r156159s165168t174

Input: a=10, b=2, c=50
Output:
a2468b12141618c22242628d32343638e42444648f

Input: a=25, b=1, c=25
Output:
a123456789101112131415161718192021222324b

Input: a=6, b=6, c=48
Output:
abcdefghi

Input: a=6, b=3, c=48
Output: a3b9c15d21e27f33g39h45i

Input: a=2, b=1, c=100
Output: a1b3c5d7e9f11g13h15i17j19k21l23m25n27o29p31q33r35s37t39u41v43w45x47y49z51a53b55c57d59e61f63g65h67i69j71k73l75m77n79o81p83q85r87s89t91u93v95w97x99y

I'd really like to see an answer in PHP, but this challenge is open to any language. This is codegolf, so the answer should be as short as possible. Standard rules apply for functions/programs and default loopholes are forbidden.

PHP, 67 bytes

First of all, thanks for posting such a cool challenge! I really enjoyed solving it :) Now, here's my 67 byte solution:

<?for(;$i<=($p=$argv)[3];$i+=$p[2])echo$i%$p[1]?$i:chr($l++%26+97);

To run it:

php -n <filename> {a} {b} {c}

Or Try it online!

Here's the same solution ungolfed and with explanation comments:

$a      = $argv[1];
$b      = $argv[2];
$c      = $argv[3];
$letter = 'a';
for ($i = 0; $i <= $c; $i += $b) {
    if ($i % $a) { // If $i is divisible by $a, the modulo (%) operator will return a remainder of 0, which PHP sees as a falsey value.
        echo $i;
    } else {
        $letter++;
        $letter %= 26; // Wrap $letter around to `a` after it gets to `z`.
        echo chr($letter + 97); // Use PHP's chr function to get the character. 97 is the index of `a`. http://php.net/manual/en/function.chr.php
    }
}

I did a 60 byte solution, but it doesn't wrap around :(

<?for($l=a;$i<=($p=$argv)[3];$i+=$p[2])echo$i%$p[1]?$i:$l++;

Try it online!


Generate me a QFP chip! Generate me a QFP chip!
From the sandbox!
QFP is a type of form factor for an electrical component where pins come out the sides of a chip.  Here are is a picture of a typical QFP component:

you can see that the general formula is to have 4 sides of equal numbers of pins.
Your challenge is to create a program that takes in an integer, thich represents the number of pins on one side, and creates an ASCII QFP component with numbered pins.
Input:
a single integer which represents the number of pins on one side
Output:
An ASCII QFP chip with an apropriate pinout.
Example:
input:1

  4
 ┌┴┐
1┤ ├3
 └┬┘
  2

input:2

  87
 ┌┴┴┐
1┤  ├6
2┤  ├5
 └┬┬┘
  34

input:12

   444444444333
   876543210987
  ┌┴┴┴┴┴┴┴┴┴┴┴┴┐
 1┤            ├36
 2┤            ├35
 3┤            ├34
 4┤            ├33
 5┤            ├32
 6┤            ├31
 7┤            ├30
 8┤            ├29
 9┤            ├28
10┤            ├27
11┤            ├26
12┤            ├25
  └┬┬┬┬┬┬┬┬┬┬┬┬┘
   111111122222
   345678901234

Rules:

all QFP chips must be enclosed and sealed as well as ascii provides. spacing is of utmost importance. Dust inside a microprocessor is bad stuff!
pin numbering must be done as in the examples (Read left to right, top to bottom, numbered counter clockwise)
You may start numbering at 0, but this must not affect the chip (an input of 12 still needs 12 pins per side)
The only valid characers in your output are 1,2,3,4,5,6,7,8,9,0,┌,┴,┐,├,┘,┬,└,┤, spaces, and newlines.
all encodings for languages are allowed, but your output MUST be consistent with the rules above.

This is a codegolf, and as such, The code with the least number of bytes wins! Good Luck!

Kotlin, 397 393 bytes

Unnamed lambda.

You can try it here, but you'll have to paste the source in yourself because the editor doesn't seem to save programs in UTF-8 encoding. The ungolfed version is a full program, so you should be able to use that in its entirety.

Golfed

{n:Int->operator fun String.mod(x:Int){(1..x).map{print(this)}};val l={s:String->s.padStart(n/10+2)};var s=(1..n).map{"${n*4+1-it}".reversed()};val z={i:Int->l(" ")%1;s.map{print(it.getOrElse(i,{' '}))};"\n"%1};(s[0].length-1 downTo 0).map(z);l("┌")%1;"┴"%n;"┐\n"%1;(1..n).map{l("$it┤")%1;" "%n;"├${n*3+1-it}\n"%1};l("└")%1;"┬"%n;"┘\n"%1;s=(1..n).map{"${n+it}"};(0..s.last().length-1).map(z)}

(Sort of) Ungolfed

fun main(args: Array<String>) {
    var q = { n: Int ->
        operator fun String.mod(x: Int) {
            (1..x).map { print(this) }
        }

        val l = { s: String ->
            s.padStart(n / 10 + 2)
        }

        var s = (1..n).map { "${n * 4 + 1 - it}".reversed() }

        val z = { i: Int ->
            l(" ")%1
            s.map { print(it.getOrElse(i, { ' ' })) }
            "\n"%1
        }

        (s[0].length - 1 downTo 0).map(z)

        l("┌")%1
        "┴"%n
        "┐\n"%1

        (1..n).map { l("$it┤") % 1;" " % n;"├${n * 3 + 1 - it}\n" % 1 }

        l("└")%1
        "┬"%n
        "┘\n"%1

        s = (1..n).map { "${n + it}" }
        (0..s.last().length - 1).map(z)
    }

    q(30)
}

Saved a bunch of bytes by overloading the % operator and using it to print. I'll probably revisit this later - I think I can save quite a few bytes if I use mod or some other operator as a concatenation function. More interpolation and less print calls.


Matching ABACABA-type patterns (This challenge is related to the challenge "Generate the Abacaba sequence.")
Zimin words (also called "sesquipowers") are an important idea in the subject of "combinatorics on words". This is because every Zimin word is "unavoidable", meaning that every sufficiently long word over a finite alphabet has a substring that is an "instance" (defined below) of the Zimin word. Remarkably, every binary word of length 29 has a substring that is an instance of the pattern \$ABACABA\$.
Definitions
Zimin words are recursively defined:

\$Z_1 = A\$
\$Z_2 = ABA\$
\$Z_3 = ABACABA\$
\$Z_4 = ABACABADABACABA\$
\$\vdots\$
\$Z_{n+1} = Z_n X Z_n\$

It's a little tricky to formally define what it means to be an "instance" for a word without talking about free monoids and homomorphisms, but it's easy enough to see from some examples.
At a hand-wave-y level, a word \$w\$ is said to be an "instance" of a pattern if there's a way to assign a (non-empty) string to each letter of the pattern and recover \$w\$.
Examples
Consider the word "11211212211221" on two letters.

It has \$105\$ substrings that are instances of the Zimin word \$Z_1 = A\$ because every substring is an instance of \$A\$.
It has \$54\$ substrings that are instances of the Zimin word \$Z_2 = ABA\$—for example, the substring "212211221": $$
  11211\underbrace{21}_A\underbrace{22112}_B\underbrace{21}_A.
$$
It has \$1\$ substring that is an instance of the Zimin word \$Z_3 = ABACABA\$: $$
11 \underbrace{2}_A \underbrace{11}_B \underbrace{2}_A \underbrace{12}_C \underbrace{2}_A \underbrace{11}_B \underbrace{2}_A 21.
$$
It has \$0\$ substrings that are instances of the Zimin word \$Z_4 = ABACABADABACABA\$.

Thus if you are given "11211212211221", you should return [105, 54, 1].
Challenge
This code-golf challenge will give you a word as an an input, and asks you to output a list of the number of substrings that are instances \$Z_1, Z_2, \cdots, Z_n\$ until there are not any substrings that are instances. That is, your program should never output 0.
You can take the word in any reasonable way: as a string, as a list of strings, as a list of appropriately coded integers, as a pair of integers \$(b,i)\$ where \$i\$ is base-\$b\$ encoded integer, etc.
Test Data
word                           | zimin_counts(word)
-------------------------------+-------------------
""                             | []
"P"                            | [1]
"MOM"                          | [6,1]
"alfalfa"                      | [28, 8]
"aha aha!"                     | [36, 9, 1]
"xxOOOxxxxxOOOxxx"             | [136, 64, 9]
"3123213332331112232"          | [190, 55, 1]
"2122222111111121221"          | [190, 80, 3]
"13121311213121311212"         | [210, 114, 25, 2]
"344112222321431121114"        | [231, 48]
"141324331112324224341"        | [231, 49]
"344342224124222122433"        | [231, 61, 1]
"331123321122132312321"        | [231, 74]
"11221112211212122222122"      | [276, 149, 4]
"2222222112211121112212121"    | [325, 166, 6]
"AAAaaAAAAAAAaAaAAaAaAAAAA"    | [325, 198, 30]
"1100000010010011011011111100" | [406, 204]
"1111221211122111111221211121" | [406, 261, 56, 2]

J, 63 58 53 52 51 47 bytes
_1}.1#.a:~:[:([#~[e.&,(],,)&.>/)^:a:~@;<@(<\)\.

Try it online!
-2 bytes thanks to Bubbler
-3 bytes thanks to FrownyFrog for golfier way to create all substrings of a string.
how
We'll use MOM as our example:

[:...;<@(<\)\. All substrings of the input, boxed.
┌─┬─┬─┬──┬──┬───┐
│M│O│M│MO│OM│MOM│
└─┴─┴─┴──┴──┴───┘

(...)^:a:~ Using the substrings as both the left and right args ~,
apply the verb in parens until a fixed point, keeping track of each iteration's
results ^:a:.

(...(],,)&.>/) To create the next "level" of candidates, create all possible
combinations that look like <level_n><orig substring><level_n> where
level_n is any element from the current level, and <orig substring> is
one of the original input substrings (level 0).  Then the 1st level looks like:
┌─────┬─────┬─────┬───────┬───────┬─────────┐
│MMM  │OMO  │MMM  │MOMMO  │OMMOM  │MOMMMOM  │
├─────┼─────┼─────┼───────┼───────┼─────────┤
│MOM  │OOO  │MOM  │MOOMO  │OMOOM  │MOMOMOM  │
├─────┼─────┼─────┼───────┼───────┼─────────┤
│MMM  │OMO  │MMM  │MOMMO  │OMMOM  │MOMMMOM  │
├─────┼─────┼─────┼───────┼───────┼─────────┤
│MMOM │OMOO │MMOM │MOMOMO │OMMOOM │MOMMOMOM │
├─────┼─────┼─────┼───────┼───────┼─────────┤
│MOMM │OOMO │MOMM │MOOMMO │OMOMOM │MOMOMMOM │
├─────┼─────┼─────┼───────┼───────┼─────────┤
│MMOMM│OMOMO│MMOMM│MOMOMMO│OMMOMOM│MOMMOMMOM│
└─────┴─────┴─────┴───────┴───────┴─────────┘

[#~[e.&,... Check if each original substring is an element of this candidate
list [e.&,, and use that to filter the original substrings [#~.  In the above
example, only MOM passes.

After the above process iterates to its fixed point (no more matches), the result
is:
┌───┬─┬─┬──┬──┬───┐
│M  │O│M│MO│OM│MOM│
├───┼─┼─┼──┼──┼───┤
│MOM│ │ │  │  │   │
├───┼─┼─┼──┼──┼───┤
│   │ │ │  │  │   │
└───┴─┴─┴──┴──┴───┘

a:~: Since we don't want to count empty boxes, we perform an elementwise
test for "not equal to the empty box a:", giving us a 0-1 matrix:
1 1 1 1 1 1
1 0 0 0 0 0
0 0 0 0 0 0

1#. Sum rows:
6 1 0

_1}. And kill the last element:
6 1


Indentation-based Sort Given an ordered list of same-case letter strings (a-z XOR A-Z) where each string is preceded by 0 or more space ( ) characters, output the same list but with the strings sorted at each level of indentation. Indentation depths under different parents count as distinct lists for sorting purposes.

Example

If your input is:

bdellium
  fox
  hound
  alien
aisle
  wasabi
    elf
    alien
  horseradish
    xeno
irk
wren
tsunami
djinn
      zebra

your output should be

aisle
  horseradish
    xeno
  wasabi
    alien
    elf
bdellium
  alien
  fox
  hound
djinn
      zebra
irk
tsunami
wren

If you like, think of it like a directory listing, and you need to sort the names within each directory.

Minutiae

An item may be indented by any number of spaces. If it is indented by the same number of spaces as the previous item it belongs in the same sort hierarchy as the previous item. If it is indented by more spaces it is the start of a new sub-hierarchy.
If a line is indented by fewer spaces than the line above it, it links up to the closest sub group above it with the same # or fewer spaces before it (like horseradish in the above example, which links onto the wasabi group above it because wasabi is the first item above it to not have more spaces than horseradish)
You must preserve the indenting level of each input item in your output
Tabs in the output are disallowed
The first line of the input will never be indented
Your program must handle at least one of all-uppercase and all-lowercase strings; it doesn't have to handle both.

Scoring

This is a code-golf, so the answer which uses the fewest bytes wins.

Python 2, 117 bytes

lambda S:[s[-1]for s in sorted(reduce(lambda t,s:t+[[v for v in t[-1]if v.count(' ')<s.count(' ')]+[s]],S,[[]]))[1:]]

Try it online!

Takes as input a list of strings; and outputs a list of strings, sorted as required.

The idea is to turn each element into a list which contains the "absolute path" as a list; and then let Python handle the sorting. E.g. if the input is:

[
 'a',
 ' c',
 '  d',
 ' b'
]

Then via the reduce(), we convert to a list of lists:

[
 ['a'],
 ['a',' c'],
 ['a',' c', '  d'],
 ['a',' b']
]

which gets sorted as:

[
 ['a'],
 ['a',' b']
 ['a',' c'],
 ['a',' c', '  d'],
]

and then output the last element of each list in the list-of-lists to get:

[
 'a',
 ' b'
 ' c',
 '  d',
]


Backwards and forwards polyglot quine! You must make a polyglot that outputs its source code in one language and its source code backward in another. Unlike the normal rules, you are allowed to read the current file or use a builtin to get the source code of your submission and reverse that in one language. Your source code cannot be a palindrome.

For example, if your source code is abcxyz, it must output abcxyz in one language and zyxcba in another. If your code is abcxyzyxbca, it's invalid because it's a palindrome.

Good luck!

Batch / bash + tac, 39 bytes

:;tac -r -s '.\|'$'\n' $0;exit
@type %0

Outputs forwards in Batch. Explanation: Batch sees the first line as a label and ignores it, while the second line simply copies the source file to STDOUT. (Note that you need to invoke the file including extension, or change %0 to %~f0.) bash sees four commands:

: does nothing (same as true)
tac -r -s '.\|'$'\n' $0

-r puts tac into regex mode
-s specifies a regex
'.\|'$'\n' is the regex, composed of

. any character except newline
\| or
$'\n' a newline

The upshot is that tac splits the file into characters rather than lines.

exit stops the script, ignoring the fourth command
@type %0 (ignored)


Inverse permutation index Introduction

The lexicographical permutations of a list with n elements can be numbered from 0 to n! - 1. For example, the 3! = 6 permutations of (1,2,3) would be (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

When a permutation is applied to a list, its elements are ordered in the same order as the numbers in the permutation. For example, applying the permutation (2,3,1) to l = (a,b,c) yields (l[2],l[3],l[1]) = (b,c,a).

The inverse of a permutation is defined as the permutation that reverses this operation, i.e. applying a permutation and then its inverse (or vice versa) does not modify the array. For example, the inverse of (2,3,1) is (3,1,2), since applying that to (b,c,a) yields (a,b,c).

Also, a permutation's inverse applied to the permutation itself yields the integers 1…n. For example, applying (3,1,2) to (2,3,1) yields (1,2,3).

We now define the function revind(x) as the index of the inverse permutation of the permutation with index x. (This is A056019, if you're interested.)

Since a permutation with index i only modifies the last k items of the list iff 0 ≤ i < k!, we can add any number of elements to the start of the list without affecting revind(i). Therefore the length of the list does not affect the result.

Challenge

Your task is to implement revind(x). You will write a full program or function that takes a single nonnegative integer x as input/argument and outputs/returns the result as a single nonnegative integer.

The input and output may be 0-indexed or 1-indexed, but this must be consistent between them.

Builtins that generate permutations by index, return the index of a permutation or find the inverse permutation are banned. (Builtins that generate all permutations or the next permutation are allowed.)

Standard code-golf rules apply.

Examples

The examples below are 0-indexed.

Input    Output
0        0
1        1
2        2
3        4
4        3
5        5
6        6
13       10
42       51
100      41
1000     3628
2000     3974
10000    30593
100000   303016

Reference implementation (Python 3)

def revind(n):
    from math import factorial
    from itertools import permutations, count
    l = next(filter(lambda x: factorial(x) > n, count(1)))
    pms = list(permutations(range(l)))
    return [k for k in range(len(pms)) if tuple(pms[n][i] for i in pms[k]) == pms[0]][0]

Mathematica, 74 bytes
Max@k[i,Flatten@Outer[i=Permutations[j=Range@#];k=Position,{i[[#]]},j,1]]&

Uses 1-indexing. Very inefficient. (uses ~11GB of memory when the input is 11)
Explanation
j=Range@#

Generate a list from 1 to N. Store that in j.
i=Permutations[...]

Find all permutations of j. Store that in i.
k=Position

Store the Position function in k. (to reduce byte-count when using Position again)
Flatten@Outer[...,{i[[#]]},j,1]

Find the inverse permutation of the N-th permutation.
Max@k[i,...]

Find the k (Position) of the inverse permutation in i (all permutations)
Using built-ins, 46 43 bytes
a[(a=Ordering)/@Permutations@Range@#][[#]]&

1-indexed.


Rock, Paper, Scissors, Lizard, Spock Create a function that will take two strings as input and return a single output for the result.  Most popular answer wins.

The rules of Rock-paper-scissors-lizard-Spock are:

Scissors cut paper
Paper covers rock
Rock crushes lizard
Lizard poisons Spock
Spock smashes scissors
Scissors decapitate lizard
Lizard eats paper
Paper disproves Spock
Spock vaporizes rock
Rock breaks scissors

The output for every possible input case is:

winner('Scissors', 'Paper') -> 'Scissors cut Paper'
winner('Scissors', 'Rock') -> 'Rock breaks Scissors'
winner('Scissors', 'Spock') -> 'Spock smashes Scissors'
winner('Scissors', 'Lizard') -> 'Scissors decapitate Lizard'
winner('Scissors', 'Scissors') -> 'Scissors tie Scissors'
winner('Paper', 'Rock') -> 'Paper covers Rock'
winner('Paper', 'Spock') -> 'Paper disproves Spock'
winner('Paper', 'Lizard') -> 'Lizard eats Paper'
winner('Paper', 'Scissors') -> 'Scissors cut Paper'
winner('Paper', 'Paper') -> 'Paper ties Paper'
winner('Rock', 'Spock') -> 'Spock vaporizes Rock'
winner('Rock', 'Lizard') -> 'Rock crushes Lizard'
winner('Rock', 'Scissors') -> 'Rock breaks Scissors'
winner('Rock', 'Paper') -> 'Paper covers Rock'
winner('Rock', 'Rock') -> 'Rock ties Rock'
winner('Lizard', 'Rock') -> 'Rock crushes Lizard'
winner('Lizard', 'Spock') -> 'Lizard poisons Spock'
winner('Lizard', 'Scissors') -> 'Scissors decapitate Lizard'
winner('Lizard', 'Paper') -> 'Lizard eats Paper'
winner('Lizard', 'Lizard') -> 'Lizard ties Lizard'
winner('Spock', 'Rock') -> 'Spock vaporizes Rock'
winner('Spock', 'Lizard') -> 'Lizard poisons Spock'
winner('Spock', 'Scissors') -> 'Spock smashes Scissors'
winner('Spock', 'Paper') -> 'Paper disproves Spock'
winner('Spock', 'Spock') -> 'Spock ties Spock'

Extra challenge suggested by @Sean Cheshire: Allow custom lists, such as those from this site. With the n-item list, the item loses to the (n-1)/2 previous, and wins over the (n-1)/2 following

APL

vs←{
    n←'Scissors' 'Paper' 'Rock' 'Lizard' 'Spock'
    x←n⍳⊂⍺ ⋄ y←n⍳⊂⍵ ⋄ X←⍺ ⋄ Y←⍵ ⋄ r←{X,⍵,⊂Y}
    x=y:     r (-x=0)↓'ties'
    y=5|1+x: r x⌷'cut' 'covers' 'crushes' 'poisons' 'smashes'
    y=5|3+x: r x⌷'decapitate' 'disproves' 'breaks' 'eats' 'vaporizes'
    ⍵∇⍺
}

Output exactly as required in all cases, including tie/ties. No lookup table, except for the actual words.

You can try it on http://ngn.github.io/apl/web/

'Spock' vs 'Paper'
Paper  disproves  Spock

APL just knows!


Generate a "GitHub" Avatar Background / Description

Note: as @HelkaHomba points out, the actual GitHub identicons are not actually random but based on the hash of a username

The default GitHub avatar is a 5x5-pixel image. A color is picked randomly, and then random pixels are filled in on one side (right or left, 2x5 size) using that color. Then that side is copied & flipped to the other side, across the y-axis. The pixels left over that are not filled in are #F0F0F0, or rgb(240,240,240).

The center column's pixels (1x5 size) are then randomly filled in, using the same color as previously.

Output

Note: for this challenge we will ignore the space that encloses the GitHub avatars

The program should output a 5x5 pixel image file. See http://meta.codegolf.stackexchange.com/a/9095/42499 for specifics

Examples

Note: these were obviously scaled up from 5x5 so you can see them

Good luck!

Pyth - 27 bytes
.wC+Kc3O^Cm,240O256 3 15_PK

Obviously doesn't work online, but you can have it print color codes here.


Draw some expanding arrows This challenge is about printing a series of growing ASCII-art arrows. I'll describe the pattern in words, but it might be easier to look at what the start of this series looks like:

>
<
->
<-
-->
<--
--->
<---
---->
<----
----->
<-----
------>
<------
...

An arrow with length n contains an arrowhead (< or >) and n-1 dashes (-). A right-facing arrow has the dashes first, then a >. A left-facing arrow starts with <, and is followed by the dashes. The series consists of a length n right-facing arrow followed by a length n left-facing arrow, with n from 1 to infinity.

To complete the challenge, write a program or function that takes one input, an integer i >= 1, and outputs the first i arrows. Arrows are individual, not in right-left pairs, so for i=3 you should output:

>
<
->

You can return a list of strings, or print them one after the other. If printing, the arrows must be delimited by some consistent delimiter, which doesn't have to be a newline as in the example.

This is code-golf, so fewest bytes wins.

Canvas, 10 bytes

⇵-×<ｎ¹［↔｝］

Try it here!


Protect my walls from these pesky doors Doorknobs are great and all, but when you open a door, it always dents the walls around it. I need you to take input of ASCII art of a room, like this:

+---------+--X  --X    --+-----+
|       \     \   |\     |   \ |
|        \     \  | \    |    \|
|         X       |  \   |     X
|      /  |       |   \  X
|     /   |     \       /
|    /    |      \     /       |
+---X   --+-------X------+-----+

And output the room with doorstops, like this:

+---------+--X  --X    --+-----+
|       \  .  \   |\     |   \.|
|        \     \  | \   .|    \|
|         X       |  \   |     X
|      /  |       |.  \  X
|     /  .|     \       /
|.   /    |     .\     /       |
+---X   --+-------X------+-----+

Specification:

The ASCII room (input) will consist of +, -, and |. These characters are purely cosmetic; they could all be +s but that would look horrible. It will also contain hinges (X) and doors (/ or \).
Doors are made up of / or \. Starting from the "hinge" character, which is X, they will go directly diagonally (change of 1 in x and 1 in y) for 2 or more units (characters).
To find where to put the doorstop for a door (there is always only one doorstop per door), find the doorway for the door. The doorway will always start at one hinge, and go the same amount of spaces as the door's length up, down, left, or right from there. The next space after that will always be a wall. For example, in this door, the doorway is marked by Ds:

   \
    \
---DDX-----

One the doorway is found, find out whether you need to go clockwise or counterclockwise to reach the door. For example, in that example door above, you have to go clockwise, and in this one, you must go counterclockwise:

   \ <-
    \  )
-----X  ---

Once you know which way to go, keep going that way (ignoring the door) until you reach a wall.

Here's a visualization of that for the example door above:

The blue is the doorway, the orange is finding that you must go clockwise, and the red is continuing to go clockwise until a wall is reached.

Once you reach a wall, go (the door's length) spaces from the hinge (X) on that wall, move one space away from the wall towards the door (so you don't place the doorstop right on the wall), and insert a . there. Here's the same example door showing how the doorstop is placed:

   \
    \  .
---DDX12---

Repeat for every door, and output the result! Use the example input at the top of this post as a test case to check if your program is valid.

Note that you do not have to handle doors that don't fit on their walls, such as:

|     /
|    /
|   /
|  /
+-X    --

Or:

     /
    /
   /
+-X   --
|
|

This is code-golf, so the shortest code in bytes will win.

Scala, 860 bytes

Golfed:

    object D extends App{val s=args(0)split("\n")
    val r=Seq(P(1,0),P(1,-1),P(0,-1),P(-1,-1),P(-1,0),P(-1,1),P(0,1),P(1,1))
    var m=r(0)
    val e=s.map(_.toCharArray)
    case class P(x:Int,y:Int){def u=x==0||h
    def h=y==0
    def p(o:P)=P(x+o.x,y+o.y)
    def o="\\/".contains(c)
    def w="-|+".contains(c)
    def c=try s(y)(x) catch {case _=>'E'}
    def n=r.filter(!_.u).map(d => d.j(p(d))).sum
    def j(t:P):Int=if(t.o)1+j(p(t))else 0
    def q=if(c=='X'){m=this
    r.filter(_.u).map{d=>if(p(d).c==' '&&p(P(d.x*(n+1),d.y*(n+1))).w)d.i}}
    def i:Unit=Seq(r++r,(r++r).reverse).map(l=>l.drop(l.indexOf(this)+1)).map(_.take(4)).filter(_.exists(a=>a.p(m)o))(0).grouped(2).foreach{p=>if(p(1)p(m)w){p(0)add;return}}
    def add=if(r.filter(_.h).map(p(_)p(m)).exists(_.w))e(y*m.n+m.y)(x+m.x)='.'else e(y+m.y)(x*m.n+m.x)='.'}
    val f=args(0).size
    Array.tabulate(f,f){(i,j)=>P(i,j)q}
    e.map(_.mkString).map(println)}

Un-golfed:

    object DoorknobCleanVersion extends App {
            val s = args(0) split ("\n")

            val r = Seq(P(1, 0), P(1, -1), P(0, -1), P(-1, -1), P(-1, 0), P(-1, 1), P(0, 1), P(1, 1))
            val HorizontalDirections = r.filter(_.isHorizontal)

            var hinge = r(0)
            val result = s.map(_.toCharArray)

            type I = Int
            case class P(x: Int, y: Int) {
                    def isCardinal = x == 0 || isHorizontal
                    def isHorizontal = y == 0

                    override def toString = x + "," + y

                    def p(o: P) = P(x + o.x, y + o.y)

                    def isDoor = Seq('\\', '/').contains(charAt)
                    def isWall = Seq('-', '|', '+').contains(charAt)

                    def charAt = try s(y)(x) catch { case _ => 'E' }

                    def doorLength = r.filter(!_.isCardinal).map(d => d.recursion2(p(d))).sum

                    def recursion2(currentPosition: P): Int =
                            if (currentPosition.isDoor)
                                    1 + recursion2(p(currentPosition))
                            else
                                    0

                    def findDoorway =
                            if (charAt == 'X') {
                                    hinge = this
                                    r.filter(_.isCardinal).map { d =>
                                            if (p(d).charAt == ' ' && p(P(d.x * (doorLength + 1), d.y * (doorLength + 1))).isWall)
                                                    d.getCorrectRotation2
                                    }
                            }

                    def getCorrectRotation2: Unit = Seq(r ++ r, (r ++ r).reverse).map(l => l.drop(l.indexOf(this) + 1))
                            .map(_.take(4))
                            .filter(_.exists(a => a.p(hinge)isDoor))(0)
                            .grouped(2)
                            .foreach {
                                    p =>
                                            if (p(1) p (hinge)isWall) {
                                                    p(0)add;
                                                    return
                                            }
                            }

                    def add =
                            if (HorizontalDirections.map(p(_) p (hinge)).exists(_.isWall))
                                    result(y * hinge.doorLength + hinge.y)(x + hinge.x) = '.'
                            else
                                    result(y + hinge.y)(x * hinge.doorLength + hinge.x) = '.'

            }

            val size = args(0).size
            Array.tabulate(size, size) { (i, j) => P(i, j).findDoorway }

            result.map(_.mkString).map(println)
    }

Using OOP was definitely the wrong approach here, in hindsight. If I could do it again I would definitely go with a bunch of hardcoded truth tables.


Make me a metasequence Background
For this challenge, a 'metasequence' will be defined as a sequence of numbers where not only the numbers themselves will increase, but also the increment, and the increment will increase by an increasing value, etc.
For instance, the tier 3 metasequence would start as:
1 2 4 8 15 26 42 64 93 130 176
because:
    1 2 3  4  5  6  7  8   9       >-|
      ↓+↑ = 7                        | Increases by the amount above each time
  1 2 4 7  11 16 22 29 37  46  >-| <-|
                                 | Increases by the amount above each time
1 2 4 8 15 26 42 64 93 130 176 <-|

Challenge
Given a positive integer, output the first twenty terms of the metasequence of that tier.
Test cases
Input: 3 Output: [ 1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160 ]
Input: 1 Output: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ]
Input: 5 Output: [ 1, 2, 4, 8, 16, 32, 63, 120, 219, 382, 638, 1024, 1586, 2380, 3473, 4944, 6885, 9402, 12616, 16664 ]
Input: 13 Output: [ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16383, 32752, 65399, 130238, 258096, 507624 ]
As you may realise, the first \$t+1\$ items of each sequence of tier \$t\$ are the first \$t+1\$ powers of 2...
Rules

Standard loopholes apply
This is code-golf, so shortest answer in bytes wins

Wolfram Language (Mathematica), 34 bytes

0~Range~19~Binomial~i~Sum~{i,0,#}&

Try it online!

The tier \$n\$ metasequence is the sum of the first \$n+1\$ elements of each row of the Pascal triangle.


The ten hundred most common words This question is written because "Thing Explainer" is fun to read, and gave me an idea.

Write "stuff that makes computer do things" that reads/takes a set of letters, numbers and things like this "#%|? and returns True / 1 if all words are part of this set.

If all words are not part of that set, return the words that were not a part of it.

This website can be considered correct in all cases. The rules are written to follow the specs on that site.

Examples:

Truthy:

The code should return a truthy value if the entire text above the first horizontal line is pasted as input.

The following lines should return a truthy value (input is separated by ###)

This returns "Hello, World!"
###
tHiS rEtUrNs TrUe...
###
Thing Explainer is a book written by a man.
The man writes books with simple words.
###
This set of stuff "#!^{>7( must return true

Falsey:

In the following examples, input and output are separated by ***. Different test cases are separated by ###.

This code doesn't return "Hello, World!"
***
code
###
tHiS rEtUrN"s false...
***
s
false

More detailed rules:

You can use this to test your code.
Non-letters are interpreted as spaces by the code, except for words like 'wasn't'. The words with apostrophes that returns true are included in the list

For instance: foo123bar should return foo and bar, since they are not part of the list, and 123 can be interpreted as spaces

The input will only contain printable ASCII code points [10, 32-126].
Words can contain mixed case letters. See second test case.
The list of words

should be taken as input (STDIN, function argument or equivalent)
can be modified (words can be separated by newline, comma etc., and you might sort the list)
Note that you can not use this list (it's not identical)

The output can be on any format you like
The output can be upper, lower or mixed case (optional)
There shall be no symbols in the output

For the record, Jonathan Allan found a strange corner case:  the implementation on XKCD will actually ignore any letters after an apostrophe up to the next non-[A-Z][a-z]['] - for example find's found, and find'qazxswedc found' both return nothing, whereas find'qazx.swedc found returns swedc.

You can choose if you want to return nothing for find'qazxswedc found', or return qazxswedc. Returning qazx, swedc for find'qazx.swedc is also OK.

PowerShell v3+, 105 92 bytes

param($a,$b)$x=@();-split($b-replace"[^a-zA-Z']",' ')|%{if($_-notin$a){$x+=$_}};($x,1)[!$x]

Takes simple words like $a, and words like $b. Makes helper $x. Take each word in $b and get rid of any bad not letters, then check each one |{...}. If that word is not in $a, then we add it to $x. At the end, we choose $x or 1 by not $x. That is sent out, either words or 1.

Some words to try

PS C:\Tools\Scripts\golfing> ('This returns "Hello, World!"','tHiS rEtUrNs TrUe...','Thing Explainer is a book written by a man.
The man writes books with simple words.','This set of stuff "¤!^¤>7\ must return true'|%{"$_";(.\ten-hundred-most-common-words.ps1 (gc .\ten-hundred-most-common-words.txt) $_)})-join"`n###`n"
This returns "Hello, World!"
###
1
###
tHiS rEtUrNs TrUe...
###
1
###
Thing Explainer is a book written by a man.
The man writes books with simple words.
###
1
###
This set of stuff "¤!^¤>7\ must return true
###
1

PS C:\Tools\Scripts\golfing> ("This code doesn't returns Hello, World!",'tHiS rEtUrN"s false...'|%{"$_`n***`n"+(.\ten-hundred-most-common-words.ps1 (gc .\ten-hundred-most-common-words.txt) $_)})-join"`n###`n"
This code doesn't returns Hello, World!
***
code
###
tHiS rEtUrN"s false...
***
s false


Is this a losing square? There is a game called Get Home that is played on the a chess board.  In this game there is a single piece that is moved by both players in turns.  There are some rules to how the piece can be moved.  On a turn a player must make one of the following moves for positive n.

n spaces up
n spaces to the left
n spaces up and to the left (a diagonal)

The player who moves the piece into the top left corner of the board wins the game.

Now we will define the concept of a losing square.  In this video (from where I got the idea) a losing square is defined as a square on which, any player starting their turn will be forced to make a move allowing their opponent to force a win.  The simplest example of a losing square would be the square at (1,2).  A piece at (1,2) can move to any of the following places.

All of which have a direct path to victory for the next player.

It also follows that any square that has a one move path to a losing square  allows the player starting on that square to force a win.  This means that any square that is not one move away from a losing square is also a losing square.

This brings us to this rather neat definition of a losing square:

A losing square is a square from which no move can arrive on another losing square and (0,0) is a losing square.

Task

Given the coordinates of a square on an arbitrarily sized chess board determine if it is a losing square.  Output two values one for losing squares and one for others.

This is code-golf so answers will be scored in bytes with less bytes being better.

Test Cases

Here are all the losing squares on a regular 8 by 8 chess board (marked with 0).

0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0
1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1

Here is an image of a 100 by 100 board with losing squares marked in black (each square is 2 pixels by 2 pixels).

Python 3, 112 50 46 42 bytes

-4 bytes thanks to Jonathan Allan!

-2 bytes thanks to xnor!

lambda r,c:abs(r-c)*(3+5**.5)//2==max(r,c)

Try it online!

Based on the formula for cold positions in Wythoff's game and making some modifications in order to produce an explicit formula. Explanation inbound once I actually finish a proper methodology for the derivation of the formula.


Double run-length encoding Everyone knows what run-length encoding is. It has been the subject of many code-golf challenges already. We'll be looking at a certain variation.
Example
Normal: 11222222222222222222233333111111111112333322
Run-length: 112(19)3(5)1(11)2333322

The number in parentheses specifies the number of times the previous symbol occurred. In the example, only runs of 5 or more characters were encoded. This is because encoding runs of 4 or less doesn't improve the character count.
Challenge
Write a function/program that implements this variation of run-length encoding, but can also encode runs of two symbols. The runs of two symbols must also be enclosed in parentheses. A group will also be enclosed in parentheses. Your program must accept a string as input, and output the modified string with modifications that shorten the string.
Example
Normal: 111244411144411144411167676767222222277777222222277777123123123123
Double run-length: 1112((444111)(3))67676767((2(7)7(5))(2))123123123123

Notes

111 was not encoded because encoding it (1(3)) is not shorter.
The string 444111 occurs 3 times so it is encoded.
676767 was not encoded because ((67)(4)) is longer than before.
222222277777222222277777 was not encoded as ((222222277777)(2)). Why? Because 222222277777 itself can be reduced to 2(7)7(5).
123123123123 isn't encoded because your program is supposed to handle runs of two symbols, not three.

This is code-golf so shortest code wins. Tie-breaker is early submission.

If I missed anything, or if you are unsure of anything please notify me in the comments.


Solving Three Open Problems with a Halting Oracle You are given the functions: h1(f,*args) and h2(f,*args)

Both are methods which are already defined for you (here the asterisk indicates a variable number of arguments)

f is a function, *args is a list of parameters to be passed to that function

h1 returns a boolean value: True if the function f ever halts when called on *args and False if it doesn't (assuming the machine running it has infinite time and memory and that the interpreter/compiler for the language you're writing in knows how to handle infinite time and memory).

If f(*args) would ever make a call to h1 or h2, h1 throws an exception

h2 behaves exactly like h1 except that if f makes calls to h1, then h2 will not throw an exception

In as few characters as possible, write a program which takes no input and should output:

The Collatz Conjecture is {True/False}
Goldbach's Conjecture is {True/False}
The Twin Primes Conjecture is {True/False}

based on the validity of each of those conjectures.

Here are wikipedia links explaining each of the conjectures:

http://en.wikipedia.org/wiki/Collatz_conjecture

http://en.wikipedia.org/wiki/Goldbach%27s_conjecture

http://en.wikipedia.org/wiki/Twin_prime

You may assume any big integer library in whatever language you choose to use will successfully represent arbitrary large integers. In other words, we'll assume any language/library which is capable of expressing 3**(3**10) is also capable of expressing 3**(3**(3**10)) on a sufficiently beefy machine.

Obviously since it's impossible to run your program, please provide an explanation of how it works along with the code

Haskell, 242
p n=and[rem n r>0|r<-[2..n-1]]
c 1=1
c n|odd n=c$3*n+1|0<1=c$div n 2
s!f=putStr(s++" Conjecture is ")>>print(not$h2$all(h1.f)[4..])
main=do"The Collatz"!c;"Goldbach's"! \n->or[p$n-r|r<-[2..n-2],p r];"The Twin Primes"! \n->or[p$r+2|r<-[n..],p r]

because in Haskell variables can contain not only values, but computations (this is called laziness) I let myself make h1, h2 take a single argument and return weather or not it's evaluation will halt.
somewhat ungolfed code:
h1 = undefined
h2 = undefined

prime n=and[rem n r>0|r<-[2..n-1]]
collatz 1=1
collatz n
    |odd n=collatz (3*n+1)
    |0<1  =collatz (div n 2)

s!f=do
    putStr (s++" Conjecture is ")
    print$not$h2$all(h1.f)[4..]

main=do
    "The Collatz"!c                                         --collatz
    "Goldbach's"! \n->or[prime (n-r)|r<-[2..n-2],prime r]   --goldbach
    "The Twin Primes"! \n->or[prime (r+2)|r<-[n..],prime r] --twin primes

a bit of explanation:
when all is applied to an infinite list, it will halt iff one of the elements of the list is False, due to laziness (short-circuiting, for all non-Haskell folks out there). we use this to compute the collatz conjecture and the twin primes conjecture.
! packages this trickery along with printing.
the result is True when f terminates on all the numbers 4... (this doesn't matter for the collatz conjecture or the twin primes conjecture, because we already know they are true for such small numbers).
the code for the collatz conjecture is "The Collatz"!c. it prints "The Collatz Conjecture is " and the result, which is weather c terminates on all numbers 4...
the code for the goldbach conjecture is "Goldbach's"! \n->or[p$n-r|r<-[2..n-2],p r].
\n->or[p$n-r|r<-[2..],p r,r<n+1] is a function which given n, if it is a sum of two primes, returns True, but otherwise loops indefinitely. thus, if it halts for every 4.. goldbach's conjecture is true.
the code for the twin primes conjecture is "The Twin Primes"! \n->or[p$r+2|r<-[n..],p r].
\n->or[p$r+2|r<-[n..],p r] is a function which given n, if there are twin primes greater than n, returns True, but otherwise loops indefinitely. thus, if it halts for every 4.. the twin prime conjecture is true.


Make two programs communicate with each other Task:

Your task is to create two programs in different languages that can communicate one-way to each other. Your sending (tx) program will take input, for either stdin or a query, and send it along to the receiving (rx) program. Your rx program will then print out the data that it receives.

Rules:

The two programs must communicate one way from the tx to the rx side, so anything typed in tx will appear in rx.
They will be running on the same computer, in different shells/windows.
They will be running in separate instances, and you are not allowed to chain them (in bash, prog1 | prog2)
The programs must be written in different languages.
They can use any data transfer method, but you must be able to transfer ASCII text.
This is a popularity-contest, so the most up voted answer wins.

Note to voters: look for creativity!

C and PERL communicating via keyboard status lights
My friend and I got inspired by this one last night.
We use Perl for the sender program and C for the receiver.
The medium of exchange was the keybord status lights!
Three virtual signal lines were used: Caps Lock, Num Lock and Scroll lock, being used as Clock, Serial Data, and Start Of Byte signals.

The sender program pulses those keyboard lights and the receiver polls them and checks the state.  Data is sent serially as binary, in 8 bit bytes.
You can see the transmitter and receiver programs in operation, in the attached video, as well as the flashing of the lights during the transmission.
Video of operation
Source for both programs is attached. Given the question requirements, we didn't try to minimize the size like we would in a normal golfing attempt.
C Code (receiver)
#include <X11/Xlib.h>
#include <stdio.h>
#include <unistd.h>

int main(void)
{
    Display* dpy = XOpenDisplay(":0");
    XKeyboardState x;
    char keys_return[32];
    int b = 0;
    while (1) {
        unsigned char output = 0;
        printf(" \b");
        fflush(stdout);
        while (XQueryKeymap(dpy, keys_return)) //wait for start signal
            if (keys_return[9] == 64) {
                break;
            }
        for (b = 0; b < 8; b++) {
            do {
                XGetKeyboardControl(dpy, &x);
            } while (!(x.led_mask & 1)); //wait for clock to be high
            if (x.led_mask & 2)
                output |= 128;
            if (b != 7)
                output >>= 1;
            do {
                XGetKeyboardControl(dpy, &x);
            } while ((x.led_mask & 1)); //wait for clock to be low
        }
        printf("%c", output);
    }
    XCloseDisplay(dpy);
    return 0;
}

PERL code (transmitter)
use X11::Xlib ':all';
use strict;
use warnings;
use feature 'say';
use Time::HiRes qw(sleep);

use constant {
    DATA  => 77,
    START => 78,
    CLOCK => 66
};

my $display = X11::Xlib->new;

sub transmit_str {
    my ($str) = @_;
    foreach my $char ( split( //, $str ) ) {
        my $ordchar = ord($char);
        for my $i ( 0 .. 7 ) {
            for my $j ( 0 .. 1 ) {
                if ( $i == 0 ) {
                    $display->fake_key( START, !($j) );
                }
                if ( $ordchar & 1 ) {
                    $display->fake_key( DATA, 1 );
                    $display->fake_key( DATA, 0 );
                }
                $display->flush;
                sleep(0.025) if(!$j);
                $display->fake_key( CLOCK, 1 );
                $display->fake_key( CLOCK, 0 );
                $display->flush;
                sleep(0.05);
            }
            $ordchar >>= 1;
        }
    }
}
while ( my $stdin = <STDIN> ) {
    transmit_str($stdin);
}


New Neighbour Sequence The non-negative integers are bored of always having the same two* neighbours, so they decide to mix things up a little. However, they are also lazy and want to stay as close as possible to their original position.

They come up with the following algorithm:

The first element is 0.
The \$n^{th}\$ element is the smallest number which is not yet present in the sequence and which is not a neighbour of the \$(n-1)^{th}\$ element.

This generates the following infinite sequence:

0,2,4,1,3,5,7,9,6,8,10,12,14,11,13,15,17,19,16,18,20,22,24,21,23,25,27,29,26,28 ...

0 is the first element. 1 is the smallest number not yet in the sequence, but it is a neighbour of 0. The next smallest number is 2, so it is the second element of the sequence. Now the remaining numbers are 1,3,4,5,6,..., but as both 1 and 3 are neighbours of 2, 4 is the third member of the sequence. As 1 is not a neighbour of 4, it can finally take its place as fourth element.

The Task

Write a function or program in as few bytes as possible which generates the above sequence.

You may

output the sequence infinitely,
take an input \$n\$ and return the \$n^{th}\$ element of the sequence, or
take an input \$n\$ and return the first \$n\$ elements of the sequence.

Both zero- or one-indexing is fine in case you choose one of the two latter options.

You don't need to follow the algorithm given above, any method which produces the same sequence is fine.

Inspired by Code golf the best permutation. Turns out this is A277618.
* Zero has literally only one neighbour and doesn't really care.