Identify the smallest possible tile in the matrix Challenge
Given a matrix of digits (0-9), find the smallest (in terms of area) rectangular matrix of digits where one or more copies of itself, possibly rotated, can tile the original matrix. Reflection is not allowed (think of a collection of tiles on a wall or floor).
Input can be taken in any reasonable ways to represent a matrix of integers or characters. Output format should be consistent with the input, but output in any orientation (out of four possible rotations) is allowed.
If there are multiple possible tiles of same area, you may output one or all of them. It is guaranteed to be solvable for any possible input, since the entire input matrix is always an option if no smaller tiles can cover it.
Standard code-golf rules apply. The shortest code in bytes wins.
Test cases
Input:
0 1 2 3 4
5 6 7 8 9
0 1 2 3 4
5 6 7 8 9
0 1 2 3 4
5 6 7 8 9
Output:
0 1 2 3 4
5 6 7 8 9
------------------
Input:
1 1 1
1 1 1
1 1 1
Output:
1
------------------
Input:
1 2 3
4 5 6
7 8 9
Output:
1 2 3
4 5 6
7 8 9
------------------
Input:
1 2 3 4 1
4 5 6 5 2
6 5 4 6 3
3 2 1 3 6
1 2 3 2 5
4 5 6 1 4
Output:
1 2 3
4 5 6
------------------
Input:
0 0 0 0
0 1 0 1
0 0 0 0
0 0 0 0
1 0 1 0
0 0 0 0
Valid Output 1:
0 0 0 0 1 0
Valid Output 2:
0 1 0
0 0 0
Invalid Output (because it is an L-shape, not a rectangular matrix):
0 1 0 0 0
0
------------------
Input: (a hard case, suggested by Arnauld)
1 2 1 2 1 1
1 1 2 1 2 2
2 1 1 2 1 2
1 2 2 1 2 1
2 1 2 1 2 2
Output:
1 2

JavaScript (ES6),  354 352 345  342 bytes
I/O: matrix of integers.
This is quite long but pretty fast -- at least with those test cases.

m=>m[b=P='map']((r,h)=>r[P]((_,w)=>(M=m.slice(~h)[P](r=>r.slice(~w)),a=~w*~h,g=(x,y,F)=>a>b|q.some((r,Y)=>r.some((v,X)=>~v?v^m[Y][X]:![x=X,y=Y]))?0:1/y?[...P+0][P](z=>(F=k=>!M[P]((r,Y)=>r[P]((v,X)=>k^1?q[y-Y][x-X]=v|k:(z|=~(q[y-X]||0)[x-Y],T[X]=T[X]||[])[Y]=v),T=[]))(1)&T.reverse(M=T)|z||g(F())|F(-1)):(o=M,b=a))(q=m[P](r=>r[P](_=>-1)))))&&o

Try it online!
How?
Whatever the tiling is, it is guaranteed that each corner of the matrix is also a corner of the tile that we're looking for. The two outer map() loops extract each possible tile \$M\$ from the bottom-right side of the input matrix \$m\$ and compute its area \$a\$.
m.map((r, h) =>           // for each row r[] at position h in m[]:
  r.map((_, w) =>         //   for each value at position w in r[]:
    (                     //
      M =                 //     build M[]:
        m.slice(~h)       //       keep the last h + 1 rows of m[]
        .map(r =>         //       for each of them:
          r.slice(~w)     //         keep the last w + 1 columns
        ),                //
      a = ~w * ~h,        //     area = (w + 1) * (h + 1)
      ...                 //     attempt to do a tiling with M
    )                     //
  )                       //   end of map()
)                         // end of map()

We build a matrix \$q\$ with the same dimensions as \$m\$, initially filled with \$-1\$.
q = m.map(r => r.map(_ => -1))

At each iteration of the recursive function \$g\$, we look for the position \$(x,y)\$ of the last cell in \$q\$ still set to \$-1\$, going from left to right and from top to bottom.
By definition, this cell has either a cell already set or a border on its right, and ditto below it. So it must be the bottom-right corner of a new tile, such as the cell marked with an 'x' below:

Simultaneously, we test whether there's a cell in \$q\$ whose value is not \$-1\$ and is different from the value in \$m\$ at the same position. If such a tile is found, we abort the recursion.
q.some((r, Y) =>          // for each row r[] at position Y in q[]:
  r.some((v, X) =>        //   for each value v at position X in r[]:
    ~v ?                  //     if v is not equal to -1:
      v ^ m[Y][X]         //       abort if v is not equal to M[Y][X]
    :                     //     else:
      ![x = X, y = Y]     //       set (x, y) = (X, Y)
  )                       //   end of some()
)                         // end of some()

If all cells of \$q\$ are matching the cells of \$m\$ and the area of \$M\$ is less than (or equal to) the best area found so far, we update the output \$o\$ to \$M\$.
Otherwise, we invoke the following code 4 times:
F(1) & T.reverse(M = T) | z || g(F()) | F(-1)

The behavior of the helper function \$F\$ depends on the parameter \$k\$:

If \$k=1\$, it computes the transpose \$T\$ of \$M\$ and checks whether all cells in \$q\$ between \$(x-w,y-h)\$ and \$(x,y)\$ are set to \$-1\$. The result of this test is saved in \$z\$.
If \$k\$ is undefined, it copies the content of \$M\$ to \$q\$ at \$(x-w,y-h)\$.
If \$k=-1\$, it cancels the previous operation by restoring all updated values to \$-1\$.

It is defined as follows:
F = k =>                  // k = parameter
  !M.map((r, Y) =>        // for each row r[] at position Y in M[]:
    r.map((v, X) =>       //   for each value v at position X in r[]:
      k ^ 1 ?             //     if k is not equal to 1:
        q[y - Y][x - X] = //       set q[y - Y][x - X]
          v | k           //       to v if k is undefined, or -1 if k = -1
      :                   //     else:
        ( z |=            //       update z:
            ~( q[y - X]   //         read q at (x - Y, y - X)
              || 0        //
            )[x - Y],     //         set z if it's not equal to -1
          T[X] =          //       compute T by writing v at the
            T[X] || []    //       relevant position
        )[Y] = v          //
    ),                    //   end of inner map()
    T = []                //   initialize T to an empty array
  )                       // end of outer map()

Therefore, the code block mentioned above can be interpreted as follows:
F(1)                      // compute the transpose T[] of M[] and test whether
&                         // M[] can be copied at (x-w, y-h) in q[]
T.reverse(M = T)          // reverse T[] and assign it to M[], which means
|                         // that M[] has been rotated 90° counterclockwise
z ||                      // if z = 0:
  g(F()) |                //   copy M[] to q[] and do a recursive call
  F(-1)                   //   restore q[] to its previous state


Raise integer x to power x, without exponentiation built-ins Task - The title pretty much sums it up: raise an integer x to power x, where 0<x.

Restrictions:

Use of exponentiation, exp(), ln(), and any other powers-related language built-ins, like pow(), x^x, x**x is forbidden.
You can assume that the given integer fits the limits of the programming language of your choice.

Test cases:

Input | Output
---------------
2     | 4
3     | 27
5     | 3125
6     | 46656
10    | 10000000000

This is code-golf, so the shortest program in bytes wins.

Python, 25 bytes

lambda n:eval('1'+'*n'*n)

Try it online!


Ordering an array of negatives, zero and positives integers with one iteration Take an array of integers containing negative numbers, positive numbers and zeros. Group it with one iteration and in place such that all of the negative numbers come first, followed by all of the zeros, followed by all of the positive numbers.

Example:

Input:  5, 3, 0, -6, 2, 0, 5
Output: -6, 0, 0, 3, 2, 5, 5

Note that the numbers do not need to be fully sorted: just sorted by sign.

So, the final array will look like this: -, -, ..., -, -, 0, 0, ..., 0, 0, +, +, ..., +, +

Rules

You may only use the input array and a constant amount of additional memory (i.e. you may not create any more arrays)
You may only use one loop, which may execute only as many times as the length of the array. You may not use built-in functions which conceal any kind of loop. This includes built-in sort functions.
The result should be in the format I described

The winner will be the person who will submit the shortest code (counted in bytes) that changes the initial array into a correct format (like described above).

C, 92
This could probably be reduced by at least 10 bytes; there are many expressions going to waste.
The first argument should point to the beginning of the array; the second should point after the end of the array.
*x;f(b,e)int*b,*e;{for(x=b;x<e;x++)*x>0&&--e-x?*x--^=*e^=*x^=*e:*x<0?b-x?*x^=*b=*x:0,b++:0;}

Ungolfed with random test generator:
*x;
f(b,e)int*b,*e;{
    for(x=b;x<e;x++) {
        if(*x<0) {
            if(b == x)
                b++;
            else
                *b++ = *x, *x=0;
        } else if(*x>0 && x != --e) {
            *x^=*e^=*x^=*e;
            x--;
        }
    }
}

int main()
{
    int a[999];
    srand(time(0));
    int n = rand() % 50;
    int i;
    for(i = 0; i < n; i++) printf("%d ", a[i] = rand() % 9 - 4);
    f(a, a+n);
    puts("");
    for(i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}


How many ACUs do I have? Posted from sandbox

The Intro

What is an ACU? This challenge is based on the concept of money and since this is an international community, we all use different currencies, so in keeping with our spirit of inclusiveness, I have invented a new currency called Arbitrary Currency Units (ACUs) specifically for this challenge. In reality, the challenge is the same whether we are using Dollars, Pounds, Euros, Bitcoins, Lao Kip or Baked Beans.

The Idea

It's New Year. We all have ideas about how we can improve things in the coming year. Mine is to save some money but randomly putting money aside quickly becomes uninteresting so I am following up on something I read on a news site last year. Each week, I put the amount of ACUs equal to the week number into a tin and after 52 weeks I will have saved ACU 1378. That's enough for a nice golfing holiday somewhere in 2021!

The Problem

I need an incentive to keep me going with this so I need to know how much I have or will have in the tin on any given date during 2020. For example, if I enter a date before today I want to know how much was in the tin on that date. For a date after today I want to know how much I will have if I stay with the plan.

The Challenge

Write a program or function which will, when given any date in 2020 (apart from 30-31 Dec - see "The Details"), output the number of ACUs that are in my tin.

The Details

Each week in 2020 consists of exactly 7 days.
The first week of the year starts on 1 January 2020.
We are considering only weeks that are completely within 2020. The last week ends on 2020-12-29 so there are exactly 52 weeks and 30/31 December are not included.
Each week I will put a number of ACUs equal to the week number into my tin on the first day of the week, that is on the 1st January I will put 1 ACU into the tin, on the 8th January I will put 2 ACUs, etc. I will at no point take any ACUs out of the tin.

The Rules

Program or function - your choice.
Input in whatever convenient format but it must be a date. I have a feeling that accepting a day-of-year input may trivialise this challenge but I am open to other opinions on this.
Output however you like but it must be a number of ACUs or a string representation of same.
We are only talking about complete weeks in 2020 so you can assume that the input will not include 30 or 31 December. It's up to you how you deal with it if it does.
Don't forget that in 2020 February has 29 days.
Usual loopholes barred and this is code golf so the shortest program/function in each language will be the winner. All languages welcome and I will not be accepting an answer as per current consensus. Upvotes will decide who wins.

A small Python script that generates the expected output for each week is available here Try it online!. The output can also be printed to stick on the side of your tin if you decide to do the same :)

APL (Dyalog Extended), 20 19 bytesSBCS

Anonymous tacit prefix function taking [year,month,day] as argument.

2!∘⌊7÷⍨43816-⍨⌂days

Try it online!

⌂days calculate the number of days since 1899-12-31

43816-⍨ subtract 43816; days since 2019 12 18, i.e 14 days weeks extra

7÷⍨ divide by 7; weeks since 2019 12 18, i.e two weeks extra

⌊ floor; whole weeks since 2019 12 18, i.e two weeks extra

∘

2! count the number of ways to choose 2 out of that many

In other words, if \$d(x)\$ is the number of days since 1899-12-31, then the answer is

$${\Big\lfloor{d(x)-43816\over7}\Big\rfloor\choose2}=
{\Big\lfloor{d(x)-43823\over7}\Big\rfloor-1\choose2}=
\sum_{n=1}^{\big\lfloor\frac{d(x)-43823}7\big\rfloor}n$$


Unfolding the Hexagony source code Introduction
If you're not familiar with Hexagony, it's an esoteric language created by Martin Büttner. The thing is that this language accepts multiple forms for the program. The following programs are all equivalent:
abcdefg

and
 a b
c d e
 f g

So basically, the code has been rolled up into a regular hexagon. But note that adding a new command to the code, which would be abcdefgh would result into the following program:
  a b c
 d e f g
h . . . .
 . . . .
  . . .

As you can see, the first step is rolling up the code into a hexagon, and after that the hexagon is filled in with no-ops (.) to the next centered hexagonal number.
Your task is simple, when given a string (the source code), output the full hexagon source code.
The rules

You may provide a program or a function.
Leading whitespace is allowed, but only when the hexagon doesn't get out of shape
Trailing whitespace is allowed.
Note that whitespace in the program are ignored. So a b c is equal to abc
Only the printable ASCII characters (32 - 126) are used, so only the regular Space character is ignored.
Assume that the length of the string is greater than 0.
This is code-golf, so the submission with the least amount of bytes wins!

Test cases
Input: ?({{&2'2':{):!/)'*/

Output:
  ? ( {
 { & 2 '
2 ' : { )
 : ! / )
  ' * /

Input: H;e;l;d;*;r;o;Wl;;o;*433;@.>;23<\4;*/

Output:
   H ; e ;
  l ; d ; *
 ; r ; o ; W
l ; ; o ; * 4
 3 3 ; @ . >
  ; 2 3 < \
   4 ; * /

Input: .?'.) .@@/'/ .!.>   +=(<.!)}    (  $>( <%

Output:
   . ? ' .
  ) . @ @ /
 ' / . ! . >
+ = ( < . ! )
 } ( $ > ( <
  % . . . .
   . . . .

Hexagony, 271 bytes

I present to you, the first 3% of a Hexagony self-interpreter...

|./...\..._..>}{<$}=<;>'<..../;<_'\{*46\..8._~;/;{{;<..|M..'{.>{{=.<.).|.."~....._.>(=</.\=\'$/}{<}.\../>../..._>../_....@/{$|....>...</..~\.>,<$/'";{}({/>-'(<\=&\><${~-"~<$)<....'.>=&'*){=&')&}\'\'2"'23}}_}&<_3.>.'*)'-<>{=/{\*={(&)'){\$<....={\>}}}\&32'-<=._.)}=)+'_+'&<

Try it online! You can also run it on itself, but it will take about 5-10 seconds.

In principle this might fit into side-length 9 (for a score of 217 or less), because this uses only 201 commands, and the ungolfed version I wrote first (on side-length 30) needed only 178 commands. However, I'm pretty sure it would take forever to actually make everything fit, so I'm not sure whether I'll actually attempt it.

It should also be possible to golf this a bit in size 10 by avoiding the use of the last one or two rows, such that the trailing no-ops can be omitted, but that would require a substantial rewrite, as one of the first path joins makes use of the bottom left corner.

Explanation

Let's start by unfolding the code and annotating the control flow paths:

That's still quite messy, so here is the same diagram for the "ungolfed" code which I wrote first (in fact, this is side-length 20 and originally I wrote the code on side-length 30 but that was so sparse that it wouldn't improve the readability at all, so I compacted it just a little bit to make the size a bit more reasonable):

Click for larger version.

The colours are exactly the same apart from a few very minor details, the non-control-flow commands are also exactly the same. So I'll be explaining how this works based on the ungolfed version, and if you really want to know how the golfed one works, you can check which parts there correspond to which in the larger hexagon. (The only catch is that the golfed code starts with a mirror so that the actual code begins in the right corner going left.)

The basic algorithm is almost identical to my CJam answer. There are two differences:

Instead of solving the centred hexagonal number equation, I just compute consecutive centred hexagonal numbers until one is equal to or larger than the length of the input. This is because Hexagony does not have a simple way to compute a square root.
Instead of padding the input with no-ops right away, I check later if I've already exhausted the commands in the input and print a . instead if I have.

That means the basic idea boils down to:

Read and store input string while computing its length.
Find the smallest side-length N (and corresponding centred hexagonal number hex(N)) which can hold the entire input.
Compute the diameter 2N-1.
For each line, compute the indent and the number of cells (which sum to 2N-1). Print the indent, print the cells (using . if the input is already exhausted), print a linefeed.

Note that there are only no-ops so the actual code starts in the left corner (the $, which jumps over the >, so the we really start on the , in the dark grey path).

Here is the initial memory grid:

So the memory pointer starts out on edge labelled input, pointing North. , reads a byte from STDIN or a -1 if we've hit EOF into that edge. Hence, the < right after is a conditional for whether we've read all the input. Let's remain in the input loop for now. The next code we execute is

{&32'-

This writes a 32 into the edge labelled space, and then subtracts it from the input value in the edge labelled diff. Note that this can never be negative because we're guaranteed that the input contains only printable ASCII. It will be zero when the input was a space. (As Timwi points out, this would still work if the input could contain linefeeds or tabs, but it would also strip out all other unprintable characters with character codes less than 32.) In that case, the < deflects the instruction pointer (IP) left and the light grey path is taken. That path simply resets the position of the MP with {= and then reads the next character - thus, spaces are skipped. Otherwise, if the character was not a space, we execute

=}}})&'+'+)=}

This first moves around the hexagon through the length edge until its opposite the diff edge, with =}}}. Then it copies the value from opposite the length edge into the length edge, and increments it with )&'+'+). We'll see in a second why this makes sense. Finally, we move the a new edge with =}:

(The particular edge values are from the last test case given in the challenge.) At this point, the loop repeats, but with everything shifted one hexagon northeast. So after reading another character, we get this:

Now you can see that we're gradually writing the input (minus spaces) along the northeast diagonal, with the characters on every other edge, and the length up to that character being stored parallel to the edge labelled length.

When we're done with the input loop, memory will look like this (where I've already labelled a few new edges for the next part):

The % is the last character we read, the 29 is the number of non-space characters we read. Now we want to find the side-length of the hexagon. First, there is some linear initialisation code in the dark green/grey path:

=&''3{

Here, =& copies the length (29 in our example) into the edge labelled length. Then ''3 moves to the edge labelled 3 and sets its value to 3 (which we just need as a constant in the computation). Finally { moves to the edge labelled N(N-1).

Now we enter the blue loop. This loop increments N (stored in the cell labelled N) then computes its centered hexagonal number and subtracts it from the input length. The linear code which does that is:

{)')&({=*'*)'-

Here, {) moves to and increments N. ')&( moves to edge labelled N-1, copies N there and decrements it. {=* computes their product in N(N-1). '*) multiplies that by the constant 3 and increments the result in the edge labelled hex(N). As expected, this is the Nth centered hexagonal number. Finally '- computes the difference between that and the input length. If the result is positive, the side-length is not large enough yet, and the loop repeats (where }} move the MP back to the edge labelled N(N-1)).

Once the side-length is large enough, the difference will be zero or negative and we get this:

First off, there is now the really long linear green path which does some necessary initialisation for the output loop:

{=&}}}32'"2'=&'*){=&')&}}

The {=& starts by copying the result in the diff edge into the length edge, because we later need something non-positive there. }}}32 writes a 32 into the edge labelled space. '"2 writes a constant 2 into the unlabelled edge above diff. '=& copies N-1 into the second edge with the same label. '*) multiplies it by 2 and increments it so that we get the correct value in the edge labelled 2N-1 at the top. This is the diameter of the hexagon. {=&')& copies the diameter into the other edge labelled 2N-1. Finally }} moves back to the edge labelled 2N-1 at the top.

Let's relabel the edges:

The edge we're currently on (which still holds the diameter of the hexagon) will be used to iterate over the lines of the output. The edge labelled indent will compute how many spaces are needed on the current line. The edge labelled cells will be used to iterate over the number of cells in the current line.

We're now on the pink path which computes indent. ('- decrements the lines iterator and subtracts it from N-1 (into the indent edge). The short blue/grey branch in the code simply computes the modulus of the result (~ negates the value if it's negative or zero, and nothing happens if it's positive). The rest of the pink path is "-~{ which subtracts the indent from the diameter into the cells edge and then moves back to the indent edge.

The dirty yellow path now prints the indentation. The loop contents are really just

'";{}(

Where '" moves to the space edge, ; prints it, {} moves back to indent and ( decrements it.

When we're done with that the (second) dark grey path searches for next character to print. The =} moves in position (which means, onto the cells edge, pointing South). Then we have a very tight loop of {} which simply moves down two edges in the South-West direction, until we hit the end of the stored string:

Notice that I've relabelled one edge there EOF?. Once we've processed this character, we'll make that edge negative, so that the {} loop will terminate here instead of the next iteration:

In the code, we're at the end of the dark grey path, where ' moves back one step onto the input character. If the situation is one of the last two diagrams (i.e. there's still a character from the input we haven't printed yet), then we're taking the green path (the bottom one, for people who aren't good with green and blue). That one is fairly simple: ; prints the character itself. ' moves to the corresponding space edge which still holds a 32 from earlier and ; prints that space. Then {~ makes our EOF? negative for the next iteration, ' moves a back a step so that we can return to the North-West end of the string with another tight }{ loop. Which ends on the length cell (the non-positive one below hex(N). Finally } moves back to the cells edge.

If we've already exhausted the input though, then the loop which searches for EOF? will actually terminate here:

In that case ' moves onto the length cell, and we're taking the light blue (top) path instead, which prints a no-op. The code in this branch is linear:

{*46;{{;{{=

The {*46; writes a 46 into the edge labelled no-op and prints it (i.e. a period). Then {{; moves to the space edge and prints that. The {{= moves back to the cells edge for the next iteration.

At this point the paths join back together and ( decrements the cells edge. If the iterator is not zero yet, we will take the light grey path, which simply reverses the MP's direction with = and then goes looking for the next character to print.

Otherwise, we've reached the end of the current line, and the IP will take the purple path instead. This is what the memory grid looks like at that point:

The purple path contains this:

=M8;~'"=

The = reverses the direction of the MP again. M8 sets the sets its value to 778 (because the character code of M is 77 and digits will append themselves to the current value). This happens to be 10 (mod 256), so when we print it with ;, we get a linefeed. Then ~ makes the edge negative again, '" moves back to the lines edge and = reverses the MP once more.

Now if the lines edge is zero, we're done. The IP will take the (very short) red path, where @ terminates the program. Otherwise, we continue on the purple path which loops back into the pink one, to print another line.

Control flow diagrams created with Timwi's HexagonyColorer. Memory diagrams created with the visual debugger in his Esoteric IDE.


Given N, output n-th element of ['A', 'B', 'AB', 'C', 'D', 'CD', 'ABCD', 'E', ...]? Consider the following list:

expected = [
'A',
'B',
'AB',
'C',
'D',
'CD',
'ABCD',
'E',
'F',
'EF',
'G',
'H',
'GH',
'EFGH',
'ABCDEFGH',
'I',
'J',
'IJ',
'K',
'L',
'KL',
'IJKL',
'M',
'N',
'MN',
'O',
'P',
'OP',
'MNOP',
'IJKLMNOP',
'ABCDEFGHIJKLMNOP',
...
]

Here's one way to look at it - you're learning how to write Chinese characters and want to learn increasingly big chunks of them, rehearsing them as you go. You start with A, then go with B, then there's already a sequence that is a pair of two so you combine it. Then you go with C and D, make another pair, practice it. Then you rehearse: ABCD. Then the same goes with E up to H, then rehearse: ABCDEFGH. The list is infinite.

The goal is to generate and print out an n-th element of this list, indexes going up from zero. Assume that after 'Z', you get 'A' again.

The winning criteria is source code length.

Python 2, 53 bytes

x,y=0,1
exec"x^=y-x;y+=x/y;"*input()
print range(x,y)

Try it online!

Similar to this construction with the transformation x = u-v, y = u


Analyzing Earthquakes Background

The Random Domino Automaton is a toy model for earthquakes, inspired by cellular automata.
In this challenge, your task is to simulate a simplified version of this model, and collect data out of it.

The automaton is defined on an array A of k bits, representing a fault line on which earthquakes may occur.
The array wraps around at its borders.
The condition A[i] = 0 means that position i is relaxed, and A[i] = 1 means that it's excited, or contains stored energy.
At each time step, one position of the array is chosen uniformly at random.
If that position is relaxed, it becomes excited (potential energy is added to the system).
If that position is already excited, it triggers an earthquake, and the chosen position and all excited positions connected to it are relaxed again.
The number of excited positions that become relaxed is the magnitude of the earthquake.

Example

Consider the array

100101110111

of length 12.
If the random process chooses the second bit from the left, the array is updated to

110101110111
 ^

since the chosen bit (marked with ^) was 0.
If we next choose the fourth bit from the left, which is an isolated 1, an eartquake of magnitude 1 is triggered, and the bit is set to 0 again:

110001110111
   ^

Next, we might choose the second bit from the right, which triggers an earthquake of magnitude 5:

000001110000
          ^

Note that all 1s in the same "cluster" as the chosen one were part of the quake, and the array wraps around at the border.

The Task

You shall take as inputs two positive integers k and t, and your task is to simulate the random domino automaton for t time steps, starting from an initial length-k array of all 0s.
Your output shall be a list L of k integers, where L[i] (with 1-based indexing) contains the number of earthquakes of magnitude i that occurred during the simulation.
You are allowed to drop trailing zeroes from the output.

For the inputs k = 15 and t = 1000, some representative outputs are

[117, 97, 45, 26, 10, 5, 3, 1, 3, 0, 0, 0, 0, 0, 0]
[135, 91, 58, 21, 8, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0]
[142, 63, 51, 31, 17, 4, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[106, 75, 45, 30, 16, 8, 5, 2, 2, 0, 0, 0, 0, 0, 0]
[111, 96, 61, 22, 3, 8, 3, 2, 0, 0, 0, 1, 0, 0, 0]

Rules

Both full programs and functions are allowed.
The shortest byte count wins, and standard loopholes are disallowed.

Note that you are not required to simulate the automaton using any particular implementation, only the output matters.

CJam, 57 55 bytes

{:K,K0a*@[{Kmrm<){_{_0#>W%K0e]}2*_)}1?+}*;]1fb2/::-fe=}

This is an anonymous function that pops k and t from the stack (k on top of t) and leaves the desired array in return.

Try it online in the CJam interpreter.

How it works

:K         e# Save the topmost integer (k) in K.
,          e# Push I := [0 ... K-1].
K0a*       e# Push J := [0 ... 0] (K elements).
@          e# Rotate the other integer (t) on top of the stack.
[{         e# Do t times:
  Kmr      e#   Pseudo-randomly select an integer between 0 and t-1.
  m<       e#   Rotate the array J than many units to the left.
  )        e#   Pop out the last element.
  {        e#   If it is 1:
    _      e#     Copy J.
    {      e#     Do 2 times:
      _0#  e#       Push the first index of 0 in J.
      >    e#       Discard the preceding elements.
      W%   e#       Reverse the array.
      K0e] e#       Pad it with zeroes to length K.
    }2*    e#
    _)     e#     Copy J and pop out the last element.
  }        e#
  1?       e#   Else: Push 1.
  +        e#   Push the integer on the stack on J.
}*         e#
;          e# Discard the last value of J.
]          e# Collect the intermediate values of J in an array.
1fb        e# Replace each array by the sum of its elements (number of ones).
2/         e# Split the array into chunks of length 2.
::-        e# Replace each chunk by the difference of its elements.
fe=        e# Count the occurrences of each integer in I.


Exploit "free whitespace" Suppose a codegolf challenge doesn't count whitespace in the length of your program.  Cheat this system by encoding your script into whitespace, and golf a script which decodes and executes embedded whitespace.

Example

My solution to JBernardo's Meta Golf Challenge was to encode Sage (or Python) code into whitespace, and golf the decoder.

s = ' '
for c in '<lots of whitespace>'.split(s):
    s+=chr(len(c))
exec s

The encoding is to take a script, prepend a newline, and for each character c in the script, output ord(c) tabs followed by a space.  Prepending a newline is necessary since I'm using Python and I start the script s with a space.

Scoring

A complete solution contains a description of the encoding you use (if it's complicated, provide a script), and a 'decode-and-execute' script.  Your score is the number of non-whitespace characters in the decode-and-execute script.

Whitespace (the language) is forbidden

Moreover, any language which has a complete set of operators which only use whitespace characters is not allowed: I'll accept the lowest nonzero score.

CPAN, 16

use Acme::Bleach;

CPAN has it all.  Or at least, just the right module.


What's the second non-repeating character? Based on this question from Code Review

Given a non-empty string of printable ASCII characters, output the second non-repeating character. For example, for input DEFD, output F.

Input

A single string, in any suitable format.

Output

The second character that doesn't repeat, when reading left-to-right, again in a suitable format.
The output character is case-insensitive.
If no such character exists (e.g., all characters repeat), output an empty string.

Rules

The algorithm should ignore case. That is, D and d count as the same character.
Either a full program or a function are acceptable.
The input string will be guaranteed non-empty (i.e., at least one character in length).
The input string is ASCII. Any valid character could repeat, not just alphanumeric (this includes spaces).
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

Input is on first line, output is on second line.

DEFD
F

FEED
D

This is an example input sentence.
x

...,,,..,,!@
@

ABCDefgHijklMNOPqrsTuVWxyz
B

AAAAAABBBBB

Thisxthis

This this.
.

MATL, 11 bytes
tk&=s1=)FT)

This exits with an error (allowed by default) if there is no second non-repeated character.
Try it online!
Explanation
t      % Implicitly take input string. Duplicate
k      % Convert to lowercase
&=     % 2D array of equality comparisons
s      % Sum of each column
1=     % True for entries that equal 1
)      % Apply logical index to the input string to keep non-repeated characters
TF)    % Apply logical index to take 2nd element if it exists. Implicitly display


Operational countdown Given a non negative integer number \$n\$ output how many steps to reach zero using radicals, divisions or subtractions.
The algorithm

Get digits count ( \$d\$ ) of  \$n\$.

Try the following operations in order:
$$\sqrt[d]{n}$$
$$n/d$$
$$n-d$$

Take the first integer result not equal to  \$n\$.
Floating point errors must be avoided !

Repeat the process with the value obtained until you reach 0.

Example
1500 -> 8
1500 -> 4 digits , ( / ) => 375 // step 1
375 -> 3 digits , ( / ) => 125 // step 2
125 -> 3 digits , ( √ ) => 5 // step 3
5 -> 1 digits , ( - ) => 4 // step 4
4 -> 1 digits , ( - ) => 3 // step 5
3 -> 1 digits , ( - ) => 2 // step 6
2 -> 1 digits , ( - ) => 1 // step 7
1 -> 1 digits , ( - ) => 0 // step 8

Input: a non negative integer number. You don't have to handle inputs not supported by your language (obviously, abusing this is a standard loophole)
Output: the number of steps to reach 0
Test cases
n -> steps

0 -> 0
1 -> 1
2 -> 2
4 -> 4
10 -> 6
12 -> 7
16 -> 5
64 -> 9
100 -> 19
128 -> 7
1000 -> 70
1296 -> 7
1500 -> 8
5184 -> 8
10000 -> 133
21550 -> 1000
26720 -> 100
1018080 -> 16
387420489 -> 10

Rules

Input/output can be given by any convenient method.
You can print it to STDOUT, return it as a function result or error message/s.
Either a full program or a function are acceptable.
Standard loopholes are forbidden.
Answers must not fail due to floating point errors.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Sandbox: https://codegolf.meta.stackexchange.com/a/20518/84844

R, 77 74 73 bytes
-3 bytes thanks to Giuseppe and -1 byte thanks to MarcMush.

f=function(n,d=nchar(n),k=1:n)`if`(d<2,n,1+f(match(n,c(k^d,k*d,k+d))%%n))

Try it online!
Recursive function; avoids floating point issues. The vector k contains all integers from 1 to n. Concatenate k^d, k*d and k+d (yielding a vector of length 3n) and find the position p of the first occurrence of n. Then \$f(n)=1+f(p \mod n)\$. The recursion is initialized by noting that \$f(n)=n\$ for all 1-digit integers (hence the conditioning on d<2).
Works for all the test cases (although 21550 could require you to increase the stack limit on some machines).


Amidakuji (阿弥陀籤) simplification If you have ever had any exposure to Japanese or East Asian culture you will have surely encountered the Amidakuji game:

As Wikipedia explains, it is a type of lottery drawn on paper and used to randomly select a permutation of N items.

For example, it may be used to randomly assign a starting sequence to N people, or N prizes to N people, and so on.

The trick to understanding why the game represents a permutation is to realize that every horizontal stroke (called a "leg") swaps its two items in place.

The same Wikipedia page also explains that each permutation P of N items corresponds to an infinite number of Amidakuji diagrams. The one(s) with the least number of horizontal strokes (legs) are called the "primes" of that particular permutation P.

Your task is to receive an Amidakuji diagram with 2 or more vertical lines (in this example they are 6) in this format (minus the letters):

A B C D E F
| | | | | |
|-| |-| |-|
| |-| |-| |
| | | | |-|
| |-| |-| |
| | |-| |-|
| | |-| | |
|-| | |-| |
|-| |-| | |
| |-| | |-|
| | | | | |
B C A D F E

And produce one of its primes (again, minus the letters):

A B C D E F
| | | | | |
|-| | | |-|
| |-| | | |
| | | | | |
B C A D F E

The first and last lines with the letters are not part of the format. I have added them here to show the permutation. It is also not required that the first or last lines contain no legs |-|, nor that the output be as compact as possible.

This particular input example is one of the (infinite) ASCII representations of the Amidakuji diagram at the top of the Wikipedia page.

There is one non-obvious rule about these ASCII diagrams: adjacent legs are forbidden.

|-|-|  <-  NO, this does not represent a single swap!

Wikipedia explains a standard procedure to obtain a prime from a diagram, called "bubblization", which consists of applying the following simplifications over and over:

1) Right fork to left fork:

| |-|      |-| |
|-| |  ->  | |-|
| |-|      |-| |

2) Eliminating doubles:

|-|        | |
|-|   ->   | |

I am not sure whether that explanation is unambiguous. Your code may use that technique or any other algorithm that produces the required primes.

Shortest code wins.

Standard rules and standard allowances apply. (If the input is not valid, your program may catch fire. Input/output formats may be stdin/stdout, string argument, list of lines, matrix of chars, whatever works best for you, etc.)

Python 2, 322 240 bytes

def f(X):
 X=[[c>' 'for c in s.split('|')]for s in X.split('\n')];h=L=len(X[0])-1;p=range(L)
 for x in X:p=[a-x[a]+x[a+1]for a in p]
 while h:h=i=0;exec"if p[i]>p[i+1]:print'|'+i*' |'+'-|'+(L-i-2)*' |';h=p[i],p[i+1]=p[i+1],p[i]\ni+=1\n"*~-L

Try it online!

A function which takes the string in the specified form, and prints out the reduced Amidakuji in that form as well.

The basic idea here is to first convert the input into a permutation (in the for x in X loop); and then in the while loop, perform a bubble sort of that permutation, since as the wikipedia article notes, this results in a 'prime' Amidakuji.


Most contributing rows Given a non-empty matrix of non-negative integers, answer which unique rows contribute most to the sum total of elements in the matrix.
Answer by any reasonable indication, for example a mask of the unique rows order of appearance (or sort order), or indices (zero- or one- based) of those, or a submatrix consisting of the rows (in any order) or some kind of dictionary construct… — but do explain it!
Examples
[[1,2,3],[2,0,4],[6,3,0],[2,0,4],[6,3,0],[2,0,4]]:
The unique rows are [1,2,3], [2,0,4], and [6,3,0] each respectively contributing 6, 6, and 9 each time they occur. However, they occur once, thrice and twice respectively, so all of their respective occurrences contribute 6, 18, and 18 to the total (42), so the latter two rows are the ones that contribute most. Valid answers are therefore:
[false,true,true] mask in appearance/sort order or
[1,2]/[2,3] zero/one-based indices of the above or
[[2,0,4],[6,3,0]] the actual rows
⋮

[[1,2],[3,1],[2,3],[1,2],[3,1],[2,3],[1,2]]
[false,false,true](appearance order) / [false,true,false](sort order)
[2]/[3](appearance order) / [1]/[2](sort order)
[[2,3]]
⋮

Jelly, 5 bytes

Ġị§§M

Try it online!

1-based indices of sorted unique elements of input.


Cut resistance of a list Background

Define a run in a list as a maximal contiguous subsequence of identical values. For example, the list

0 0 0 1 1 0 3 3 3 2 2

has five runs of lengths 3, 2, 1, 3, 2 respectively. (Think of run-length encoding.)

Then define a cut operation as removing one item from each run of a list. Applied to the list above, the result will be 0 0 1 3 3 2.

Finally, the cut resistance of a list is the number of cut operations needed to reduce it to an empty list. The cut resistance of the list above is 3:

0 0 0 1 1 0 3 3 3 2 2
0 0 1 3 3 2
0 3
(empty)

Note that the cut resistance can be higher than the maximal run length, since multiple runs may fuse in the way:

1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0
0 1 0 0 0
0 0
0
(empty)

Related OEIS sequence: A319416 (cut resistance of n written in binary)

Task

Given a (possibly empty) list of nonnegative integers, compute its cut resistance.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

0 0 0 1 1 0 3 3 3 2 2 => 3
1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 => 4
1 2 3 4 5 99 100 101 => 1
4 4 4 4 4 4 3 3 3 3 2 2 1 2 2 3 3 3 3 4 4 4 4 4 4 => 7
(empty) => 0

J, 20 bytes

1-~&#(#~2=/\_&,)^:a:

Try it online!

Using the 0 0 0 1 1 0 3 3 3 2 2 example:

(......_&,) Prepend infinity _:

_ 0 0 0 1 1 0 3 3 3 2 2

(..2=/....) Are consecutive pairs equal? Returns 0-1 list of same length as input:

_ 0 0 0 1 1 0 3 3 3 2 2  <-- Before
 0 1 1 0 1 0 0 1 1 0 1   <-- After

(#~.......) Apply the above mask as a filter to the input.  This drops the first member of every group:

0 0 1 3 3 2

^:a: Repeat until we reach a fixed point, returning all intermediate results (0-padded on the right):

0 0 0 1 1 0 3 3 3 2 2
0 0 1 3 3 2 0 0 0 0 0
0 3 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

1-~&# Subtract 1 from 1-~ the above result, after applying the "length of" verb to both lists &#.  Since the length of 1 is 1, it remains unchanged, while the result above becomes 4:

4 - 1
3


So... what is your StackOverflow score? This is a simple one. Given the input of a number, return the name and reputation score of the Stack Overflow user with that given ID. Your program can assume that it is always given a valid and existent user ID.

For example: given the input 764357 (which is my userID on StackOverflow) the program would return LegoStormtroopr 3,088 (approximately) it might change.

You get the URL: "https://stackoverflow.com/users/" or "http://api.stackexchange.com/2.1/users/" for free, so your score is length of your program - 31 or 39, depending on which URL you use - but declare which it is. This prevents people from abusing URL shorteners.

edit: And no calling a custom made API that query Stack Overflow, and returns just the name and score. But if you know of an offical API, then that is totally legitimate.

edit2: If you need an example input: I've given my ID below, feel free to add your own ID, username and score below to help others out. Note again, this is for the main Stack Overflow site.

764357   returns   LegoStormtroopr 3,088

Shell script: 64 51 characters
curl -sL http://stackoverflow.com/users/`cat`|grep -oPm2 'n">\K[0-9,]+|e">\K[^<]+'

Sample run:
bash-4.1$ curl -sL http://stackoverflow.com/users/`cat`|grep -oPm2 'n">\K[0-9,]+|e">\K[^<]+'
662504
manatwork
834

bash-4.1$ curl -sL http://stackoverflow.com/users/`cat`|grep -oPm2 'n">\K[0-9,]+|e">\K[^<]+'
764357
Lego Stormtroopr
3,087

(Note that you have to press ^D after typing in the input interactively. Or just pipe it to the command.)


Reduced Row-Echelon Form of a Matrix The goal of this challenge is to create a program that takes in a matrix and outputs its reduced row-echelon form.

  A matrix is in reduced row-echelon form if it meets all of the
  following conditions:

  If there is a row where every entry is zero,
  then this row lies below any other row that contains a nonzero entry.
  The leftmost nonzero entry of a row is equal to 1.
  The leftmost nonzero entry of a row is the only nonzero entry in its column.
  Consider any two different leftmost nonzero entries, one located in
  row i, column j and the other located in row s, column t. If s>i, then
  t>j.

  Source

The general process to transform the matrix is:

Deal with each row i from 1 to n in turn, and work across the columns j from 1 to m skipping any column of all zero entries.
Find the next column j with a nonzero entry.
Interchange rows, if necessary, so that the pivot element A(i,j) is nonzero.
Make the pivot equal to 1 by dividing each element in the pivot row by the value of the pivot.
Make all elements above and below the pivot equal to 0 by subtracting a suitable multiple of the pivot row from each other row.
Repeat for all rows.

If you want to read more on this type of matrix, view the Wikipedia article on it and a tool and article(steps above) that shows the steps to transform the matrix.

As for the actual challenge, here it goes:

The input can be given in any way you wish through STDIN or equivalent, just please explain it in your answer. The output will be the reduced row-echelon form of the input in the same form as the input through STDOUT or equivalent. Standard loopholes are not allowed and external libraries or functions that do this task are also not allowed (TI-BASIC's rref( command, for example). You may write a full program or function. This is code golf, lowest BYTES wins. Good luck!

Example Input: [[2,1,1,14][-1,-3,2,-2][4,-6,3,-5]]

Example Output: [[1,0,0,1][0,1,0,5][0,0,1,7]]

R, 232 bytes

function(M){p=1;R=nrow(M);C=ncol(M);for(r in 1:R){if(C<=p)break;i=r;while(M[i,p]==0){i=i+1;if(R==i){i=r;p=p+1;if(C==p)return(M)}};t=M[i,];M[i,]=M[r,];M[r,]=t;M[r,]=M[r,]/M[r,p];for(i in 1:R)if(i!=r)M[i,]=M[i,]-M[r,]*M[i,p];p=p+1};M}

This is just an implementation of the usual Gaussian elimination algorithm.

Ungolfed:

rref <- function(M) {
    p <- 1
    R <- nrow(M)
    C <- ncol(M)
    for (r in 1:R) {
        if (C <= p)
            break
        i <- r
        while (M[i, p] == 0) {
            i <- i + 1
            if (R == i) {
                i <- r
                p <- p + 1
                if (C == p)
                    return(M)
            }
        }
        t <- M[i, ]
        M[i, ] <- M[r, ]
        M[r, ] <- t
        M[r, ] <- M[r, ] / M[r, p]
        for (i in 1:R)
            if (i != r)
                M[i, ] <- M[i, ] - M[r, ] * M[i, p]
        p <- p + 1
    }
    M
}


Validating a CPR number Validating a CPR number

A Danish CPR number (Person Identification Number) is date of birth followed by 4 digits (the last one being a control digit): DDMMYY-XXXX

The final digit validates the CPR number using Modulo 11 by satisfying the following equation:

where the  are the ten digits of the complete ID number, and the coefficients (4, 3, 2, 7, …) are all nonzero in the finite field of order 11.

Input

A CPR number formatted like this DDMMYY-XXXX where YY indicates a year within the last 100 years (between 1917 and 2016).

Output

Indication whether CPR number is valid (1 or true) or invalid (0 or false)

Examples

  290215-2353 --> false
  140585-2981 --> true
  311217-6852 --> true
  121200-0004 --> false
  140322-5166 --> false
  111111-1118 --> true

Scoring

This is code-golf - fewest bytes win!

Date validation

All years refer to a period within the last 100 years. A valid date is a date that exists within it's calendar year.

290215 is not a valid date because 29/2 wasn't a date in 2015.

301216 is a valid date because 30/12 is a date in 2016.

Python (2), 167 156 155 142 141 bytes

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

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

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

-12 bytes thanks to @GáborFekete

-14 bytes thanks to @RootTwo


Fibonacci in +!()[]script Write a piece of JavaScript code that calls alert with an array containing the first 50 Fibonacci numbers in order. You may only use the following characters: +!()[].

As a reference, your code must be functionally equal to the following:

var fib = [], a = 1, b = 1;
for (var _ = 0; _ < 50; _++) {
    fib.push(a);
    var t = a; a = b; b = t + a;
}
alert(fib);

You may not assume any content on the webpage - your program will be run in the console on about:blank. Similarly, you may not 'cheat' and store any settings in cookies, settings or other data. Your solution must work on any fresh install of the latest Google Chrome or Firefox on any OS. When in doubt, try to remain as portable as possible.

Smallest source code in bytes wins.


Determine Tic-Tac-Toe winner (round based) Let's play some code-golf!

The challenge is to find the winner of a game of Tic-Tac-Toe.

This has been done many times by giving a board that has one clear winner but here is the twist:

The cells are numbered like this:

1|2|3
-+-+-
4|5|6
-+-+-
7|8|9

You get an array of exactly 9 moves like that:

{3, 5, 6, 7, 9, 8, 1, 2, 3}

This is parsed as follows:

Player 1 marks cell 3
Player 2 marks cell 5
Player 1 marks cell 6
Player 2 marks cell 7
Player 1 marks cell 9
Player 1 has won

Note: The game does not stop after one player has won, it may happen that the losing player manages to get three in a row after the winning player, but only the first win counts.

Your job is now to get 9 numbers as input and output the winning player and the round in which the win occured.
If no one wins, output something constant of your choice. You can receive input and provide output through any standard mean / format.

Have fun!

Some more examples as requested:

{2,3,4,5,6,7,1,8,9} => Player 2 wins in round 6
{1,2,4,5,6,7,3,8,9} => Player 2 wins in round 8
{1,2,3,5,4,7,6,8,9} => Player 2 wins in round 8

Retina, 114 bytes

(.)(.)
$1O$2X
^
123;;456;;789¶X
{`(.)(.*¶)(.)\1
$3$2
}`.*(.)(.)*\1(?<-2>.)*(?(2)(?!))\1.*¶(..)*
$1$#3
.*¶
T
T`d`Rd

Try it online! Based on my answer to Tic-Tac-Toe - X or O?. Outputs X<N> if the first player wins after N turns, O<N> if the second player wins, T if neither wins. Explanation:

(.)(.)
$1O$2X
^
123;;456;;789¶X

Creates an internal board, and also marks each move with the player whose move it is.

{`(.)(.*¶)(.)\1
$3$2

Applies a move.

}`.*(.)(.)*\1(?<-2>.)*(?(2)(?!))\1.*¶(..)*
$1$#3

Searches for a win, and if one is found, then replace the board with the winner and the number of remaining moves.

.*¶
T

If the moves are exhausted and nobody has won then the game is a tie.

T`d`Rd

Calculate the number of the round from the number of remaining moves.


Solve the 15 Puzzle (the tile-sliding puzzle) The 15 Puzzle is a famous puzzle involving sliding 15 tiles around on a 4x4 grid. Starting from a random configuration, the goal is to arrange the tiles in the correct order. Here is an example of a solved 15 Puzzle:

01 02 03 04
05 06 07 08
09 10 11 12
13 14 15

Each move on the puzzle is of the form Up/Down/Left/Right. The move "Down" consists of sliding the tile that is above the empty spot downward. The move "Right" consists of sliding a tile to the right, into the empty spot. Here is how the board looks after the moves Down and Right.

01 02 03 04
05 06 07 08
09 10    11
13 14 15 12

The goal of this challenge is to write a program that can output the series of moves needed to solve the 15 Puzzle. The winner is the program who solves the five test cases (below) in the fewest total moves. The generated solution does not need to be a perfect solution, it merely has to be better than the competitors. For each individual test case, the program should not take more than ten seconds on a reasonable machine.

Your program must be able to solve any puzzle that is solvable, I'm just using these five test cases as the scoring.

Your program will receive the unsolved 15 Puzzle as input in the format of a 2D array. The 2D array can be formatted according to the language used, or changed if the language does not have 2D arrays. The first element of the first sub-array will be the number in the upper left, and the last element of the first sub-array will be the number in the upper right. A 0 will be the empty space.

As output, your program should print a list of moves in the order that they need to be performed. Each step should be numbered in order to increase the usability of the results.

EDIT: Based on comments, I will allow output to be in either the form of Down/Up/etc or in the form of the coordinates of the piece to move. As this is not code golf, the most important part is to solve the puzzle.

Some other general rules involve no using an outside source, etc.

Test Case 1

([5,1,7,3],[9,2,11,4],[13,6,15,8],[0,10,14,12])

Example Output:

1: Down
2: Down
3: Down
4: Left
....

Test Case 2

([2,5,13,12],[1,0,3,15],[9,7,14,6],[10,11,8,4])

Test Case 3

([5,2,4,8],[10,0,3,14],[13,6,11,12],[1,15,9,7])

Test Case 4

([11,4,12,2],[5,10,3,15],[14,1,6,7],[0,9,8,13])

Test Case 5

([5,8,7,11],[1,6,12,2],[9,0,13,10],[14,3,4,15])

PyPy, 195 moves, ~12 seconds computation

Computes optimal solutions using IDA* with a 'walking distance' heuristic augmented with linear conflicts. Here are the optimal solutions:

 5  1  7  3
 9  2 11  4
13  6 15  8
 0 10 14 12
Down, Down, Down, Left, Up, Up, Up, Left, Down, Down, Down, Left, Up, Up, Up

 2  5 13 12
 1  0  3 15
 9  7 14  6
10 11  8  4
Left, Down, Right, Up, Up, Left, Down, Down, Right, Up, Left, Left, Down, Right, Right, Right, Up, Up, Left, Left, Down, Left, Up, Up, Right, Down, Down, Left, Up, Up, Right, Right, Right, Down, Left, Up, Right, Down, Down, Left, Left, Down, Left, Up, Up, Right, Up, Left

 5  2  4  8
10  0  3 14
13  6 11 12
 1 15  9  7
Left, Up, Up, Right, Right, Down, Left, Up, Left, Left, Down, Down, Right, Right, Up, Left, Left, Down, Down, Right, Right, Up, Right, Up, Left, Left, Up, Right, Down, Down, Right, Down, Left, Left, Up, Up, Left, Up

11  4 12  2
 5 10  3 15
14  1  6  7
 0  9  8 13
Down, Left, Down, Right, Up, Left, Left, Left, Down, Down, Right, Right, Right, Up, Left, Left, Left, Down, Right, Right, Up, Left, Up, Up, Left, Down, Down, Right, Down, Right, Up, Up, Right, Up, Left, Left, Left, Down, Right, Right, Right, Up, Left, Down, Left, Down, Left, Up, Up

 5  8  7 11
 1  6 12  2
 9  0 13 10
14  3  4 15
Up, Right, Down, Left, Left, Down, Left, Up, Right, Up, Right, Down, Down, Right, Up, Up, Left, Left, Left, Down, Down, Down, Right, Right, Up, Right, Down, Left, Up, Left, Up, Left, Down, Right, Down, Left, Up, Right, Down, Right, Up, Up, Left, Left, Up

And the code:

import random

class IDAStar:
    def __init__(self, h, neighbours):
        """ Iterative-deepening A* search.

        h(n) is the heuristic that gives the cost between node n and the goal node. It must be admissable, meaning that h(n) MUST NEVER OVERSTIMATE the true cost. Underestimating is fine.

        neighbours(n) is an iterable giving a pair (cost, node, descr) for each node neighbouring n
        IN ASCENDING ORDER OF COST. descr is not used in the computation but can be used to
        efficiently store information about the path edges (e.g. up/left/right/down for grids).
        """

        self.h = h
        self.neighbours = neighbours
        self.FOUND = object()

    def solve(self, root, is_goal, max_cost=None):
        """ Returns the shortest path between the root and a given goal, as well as the total cost.
        If the cost exceeds a given max_cost, the function returns None. If you do not give a
        maximum cost the solver will never return for unsolvable instances."""

        self.is_goal = is_goal
        self.path = [root]
        self.is_in_path = {root}
        self.path_descrs = []
        self.nodes_evaluated = 0

        bound = self.h(root)

        while True:
            t = self._search(0, bound)
            if t is self.FOUND: return self.path, self.path_descrs, bound, self.nodes_evaluated
            if t is None: return None
            bound = t

    def _search(self, g, bound):
        self.nodes_evaluated += 1

        node = self.path[-1]
        f = g + self.h(node)
        if f > bound: return f
        if self.is_goal(node): return self.FOUND

        m = None # Lower bound on cost.
        for cost, n, descr in self.neighbours(node):
            if n in self.is_in_path: continue

            self.path.append(n)
            self.is_in_path.add(n)
            self.path_descrs.append(descr)
            t = self._search(g + cost, bound)

            if t == self.FOUND: return self.FOUND
            if m is None or (t is not None and t < m): m = t

            self.path.pop()
            self.path_descrs.pop()
            self.is_in_path.remove(n)

        return m

def slide_solved_state(n):
    return tuple(i % (n*n) for i in range(1, n*n+1))

def slide_randomize(p, neighbours):
    for _ in range(len(p) ** 2):
        _, p, _ = random.choice(list(neighbours(p)))
    return p

def slide_neighbours(n):
    movelist = []
    for gap in range(n*n):
        x, y = gap % n, gap // n
        moves = []
        if x > 0: moves.append(-1)    # Move the gap left.
        if x < n-1: moves.append(+1)  # Move the gap right.
        if y > 0: moves.append(-n)    # Move the gap up.
        if y < n-1: moves.append(+n)  # Move the gap down.
        movelist.append(moves)

    def neighbours(p):
        gap = p.index(0)
        l = list(p)

        for m in movelist[gap]:
            l[gap] = l[gap + m]
            l[gap + m] = 0
            yield (1, tuple(l), (l[gap], m))
            l[gap + m] = l[gap]
            l[gap] = 0

    return neighbours

def slide_print(p):
    n = int(round(len(p) ** 0.5))
    l = len(str(n*n))
    for i in range(0, len(p), n):
        print(" ".join("{:>{}}".format(x, l) for x in p[i:i+n]))

def encode_cfg(cfg, n):
    r = 0
    b = n.bit_length()
    for i in range(len(cfg)):
        r |= cfg[i] << (b*i)
    return r

def gen_wd_table(n):
    goal = [[0] * i + [n] + [0] * (n - 1 - i) for i in range(n)]
    goal[-1][-1] = n - 1
    goal = tuple(sum(goal, []))

    table = {}
    to_visit = [(goal, 0, n-1)]
    while to_visit:
        cfg, cost, e = to_visit.pop(0)
        enccfg = encode_cfg(cfg, n)
        if enccfg in table: continue
        table[enccfg] = cost

        for d in [-1, 1]:
            if 0 <= e + d < n:
                for c in range(n):
                    if cfg[n*(e+d) + c] > 0:
                        ncfg = list(cfg)
                        ncfg[n*(e+d) + c] -= 1
                        ncfg[n*e + c] += 1
                        to_visit.append((tuple(ncfg), cost + 1, e+d))

    return table

def slide_wd(n, goal):
    wd = gen_wd_table(n)
    goals = {i : goal.index(i) for i in goal}
    b = n.bit_length()

    def h(p):
        ht = 0 # Walking distance between rows.
        vt = 0 # Walking distance between columns.
        d = 0
        for i, c in enumerate(p):
            if c == 0: continue
            g = goals[c]
            xi, yi = i % n, i // n
            xg, yg = g % n, g // n
            ht += 1 << (b*(n*yi+yg))
            vt += 1 << (b*(n*xi+xg))

            if yg == yi:
                for k in range(i + 1, i - i%n + n): # Until end of row.
                    if p[k] and goals[p[k]] // n == yi and goals[p[k]] < g:
                        d += 2

            if xg == xi:
                for k in range(i + n, n * n, n): # Until end of column.
                    if p[k] and goals[p[k]] % n == xi and goals[p[k]] < g:
                        d += 2

        d += wd[ht] + wd[vt]

        return d
    return h

if __name__ == "__main__":
    solved_state = slide_solved_state(4)
    neighbours = slide_neighbours(4)
    is_goal = lambda p: p == solved_state

    tests = [
        (5,1,7,3,9,2,11,4,13,6,15,8,0,10,14,12),
        (2,5,13,12,1,0,3,15,9,7,14,6,10,11,8,4),
        (5,2,4,8,10,0,3,14,13,6,11,12,1,15,9,7),
        (11,4,12,2,5,10,3,15,14,1,6,7,0,9,8,13),
        (5,8,7,11,1,6,12,2,9,0,13,10,14,3,4,15),
    ]

    slide_solver = IDAStar(slide_wd(4, solved_state), neighbours)

    for p in tests:
        path, moves, cost, num_eval = slide_solver.solve(p, is_goal, 80)
        slide_print(p)
        print(", ".join({-1: "Left", 1: "Right", -4: "Up", 4: "Down"}[move[1]] for move in moves))
        print(cost, num_eval)


Source code ecological footprint You've just been hired by a German car manufacturing company. Your first task, as an engineer, is to write a program that computes the ecological footprint of ASCII strings.

The ecological footprint of character is computed as follows:

  Write the character's ASCII code in binary, and count the number of 1's.

For example, A has a footprint of 2, but O is dirtier with a footprint of 5.

  The global footprint of a string is the sum of the footprints of its characters. An empty string has a footprint of zero.

Your program must accept an ASCII string as parameter (through command line or input), compute its ecological footprint, and output it. The program itself must be ASCII encoded.

There is a hiccup though. As your company wishes to enter a new market with stricter environmental rules, you need to tune your program so that it behaves differently in "test mode". Thus:

  The program should output 0 when it receives the string test as parameter.

Scoring

The source code with the smallest ecological footprint wins (and yes, the answer test is forbidden!)

CJam, 33 31

"",AA#b:c~

There are 11300000000950000000034000000011600000001010000000115000000011600000000340000000061000000003300000000420000000058000000010500000000500000000102000000009800000000490000000102000000009800000000490000000098 null bytes between the double quotes.

The code is equivalent to

11300000000950000000034000000011600000001010000000115000000011600000000340000000061000000003300000000420000000058000000010500000000500000000102000000009800000000490000000102000000009800000000490000000098
AA#b:c~

which can be tested online.

How this works

"",  e# Push the length of the string.
AA#  e# Push 10000000000.
b    e# Turn the length into the array of its base-10000000000 digits.
:c   e# Cast each digit to character. This pushes the following:
     e# q_"test"=!*:i2fb1fb1b
~    e# Evaluate the string.

How that works

q_     e# Read all input and push a copy.
"test" e# Push the string "test".
=!*    e# Check for inequality and repeat the string 0 or 1 times.
       e# This replaces input "test" with the empty string.
:i     e# Cast each character to integer
2fb    e# Replace each integer by the array of its base-2 digits.
1fb    e# Replace each array of base-2 digits by the sum of its digits.
1b     e# Add the sums of digits.

This source code has an ecological footprint of 75.


Golf a bijection \$\mathbb{N}^n\to\mathbb{N}\$ Your task is to write a program which implements a bijection \$\mathbb{N}^n\to\mathbb{N}\$ for \$n \ge 1\$. Your program should take \$n\$ natural numbers as input, in any acceptable method (including taking them as a single, \$n\$ element list/array) and output a unique natural number for all possible inputs.
In layman's terms, a bijection \$\mathbb{N}^n\to\mathbb{N}\$ means:

Take \$n\$ natural numbers as input
Map these \$n\$ natural numbers to a single natural number output
For every possible input, the output is provably unique
For every possible output, there exists an input which will give that output

For example, the Cantor pairing function \$\pi : \mathbb{N}^2\to\mathbb{N}\$ is a bijection that takes two natural numbers and maps each pair to a unique natural number.
You may implement whatever bijective function you wish, so long as it is proven to be bijective for all possible inputs. Please include this proof (either directly or through a link) in your answer. This is code-golf so the shortest code, in bytes, wins.
You may decide whether you'd like to use \$\mathbb{N} = \{1, 2, 3, \dots\}\$ or \$\mathbb{N} = \{0, 1, 2, \dots\}\$, so long as this is consistent for all \$n\$.

APL (Dyalog Unicode), 13 10 bytes

(⊢+1⊥∘⍳+)/

Try it online!
Similar to other answers, since the Cantor pairing is bijective, compositing \$n-1\$ Cantor pairings is bijective as well.
(       )/  ⍝ reduce the input with following function
       +    ⍝ left argument + right argument
      ⍳     ⍝ the first left+right positive integers
   1⊥       ⍝ convert those from base 1 (sum)
 ⊢+         ⍝ + right argument


Absolute Sums of Sidi Polynomial Coefficients Background
The Sidi polynomial of degree \$n\$ – or the \$(n + 1)\$th Sidi polynomial – is defined as follows.
$$S_n(x) = \sum^n_{k=0}s_{n;k}x^n \text{ where } s_{n;k} = (-1)^k\binom n k (k+1)^n$$
The Sidi polynomials have several interesting properties, but so do their coefficients. The latter form OEIS sequence A075513.
Task
Write a full program or a function that, given a non-negative integer \$n\$, prints or returns the absolute sum of the coefficients of the Sidi polynomial of degree \$n\$, that is
$$\Sigma_n = \sum^n_{k=0}|s_{n;k}|$$
These sums form OEIS sequence A074932.
If you prefer 1-based indexing, you can take a positive integer \$n\$ instead and compute the absolute sum of the coefficients of the \$n\$th Sidi polynomial.
Because this is code-golf, you must make your code as short as possible. All standard rules apply.
Test cases (0-based)
 n           Σ

 0           1
 1           3
 2          18
 3         170
 4        2200
 5       36232
 6      725200
 7    17095248
 8   463936896
 9 14246942336

Test cases (1-based)
 n           Σ

 1           1
 2           3
 3          18
 4         170
 5        2200
 6       36232
 7      725200
 8    17095248
 9   463936896
10 14246942336

Python 2, 43 bytes

f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)

Try it online!
A different approach
Ever since I posted this challenge, I tried to come up with a recursive solution to this problem. While I failed using nothing more than pen and paper, I managed to turn the formula to golf into a practical problem – at least for certain definitions of practical – which made it easier to analyze.
Imagine a game show with k + m candidates that works as follows.
In round 1, all candidates have to accomplish a certain task as fast as they can. The k candidates that accomplish the task the fastest win 1 k$ (one kilodollar) each and advance to round 3.
In round 2, the m remaining candidates get a second chance to join the other k. Each candidate is asked a question. If they answer the question correctly, they win 1 k$ and advance to round 3. However, if they fail to answer the question, they are eliminated from the game. This means round 3 will have between k and k + m candidates, depending on how many can answer their questions.
Round 3 consists of m more contests that are similar to round 1. In each contest, the participants have to accomplish a certain task. Unlike round 1, only one candidate receives a prize, but all candidates get to participate in the next contest. Each contests pay twice as much as the contest before it; the first one pays 2 k$ and the last one 2m k$.
Note that since all prizes are powers of two, knowing how much prize money a candidate earned means we know if they advanced to round 3 and which of the contests of round 3 they won.
Assume you're watching the game show and round 1 is already over, so you know which k candidates have already reached round 3 and which m candidates are still stuck in round 2. In how many ways can the remaining prize money be distributed?
Once we know which of the second round's m candidates have advanced to round 3, it's easy to calculate the possible outcomes for this specific scenario. If j candidates advance, there are k + j total candidates in round 3, and thus k + j possible outcomes for each contest. With m individual contests in round 3, this makes (k + j)m outcomes for all m contests.
Now, j can take any value between 0 and m, depending on which candidates answer correctly in round 2. For each fix value of j, there are mCj different combinations of j candidates that could have advanced to round 3. If we call the total number of possible outcomes for k round 3 candidates and m round 2 candidates g(m, k), we get the following formula.

If we fix k = 1, we get the following special case, which constitutes our new approach to solve the original problem.

A recursive formula
Now, assume that you fell asleep during the commercials after round 1, and woke up just in time to see who won the last contest of round 3 and thus the grand prize of 2m k$. You don't have any other information, not even how much prize money that candidate won in total. In how many ways can the remaining prize money be distributed?
If the winner was one of the m candidates of round 2, we already now that they must have advanced to round 3. Thus, we effectively have k + 1 candidates in round 3, but only m - 1 candidates in round 2. Since we know the winner of the last contest, there are only m - 1 contests with uncertain outcomes, so there are g(m - 1, k + 1) possible outcomes.
If the winner is one of the k candidates that skipped round 2, the calculation becomes slightly trickier. As before, there are only m - 1 rounds left, but now we still have k candidates in round 3 and m candidates in round 2. Since the number of round 2 candidates and the number of round 3 contests are different, the possible outcomes cannot be calculated with a simple invocation of g. However, after the first round 2 candidate has answered – rightly or wrongly – the number of round 2 candidates once again matches the m - 1 round 3 contests. If the candidate advances, there are k + 1 round 3 candidates and thus g(m - 1, k + 1) possible outcomes; if the candidate is eliminated, the number of round 3 candidates remains at k and there are g(m - 1, k) possible outcomes. Since the candidate either advances or not, there are g(m - 1, k + 1) + g(m - 1, k) possible outcomes combining these two cases.
Now, if we add the potential outcomes for all k + m candidates that could have won the grand prize, the result must match g(m, k). There are m round 2 contestants that lead to g(m - 1, k + 1) potential outcomes each, and k round 3 contestants that lead to g(m - 1, k + 1) + g(m - 1, k) ones. Summing up, we get the following identity.

Together with the base case

these two formulae characterize the function g completely.
A golfy implementation
While
g=lambda m,k=1:0**m or(m+k)*g(m-1,k+1)+k*g(m-1,k)

(49 bytes, 0**m yields 1 once m drops to 0) or even
g=lambda m,k=1:m<1 or(m+k)*g(m-1,k+1)+k*g(m-1,k)

(48 bytes, returns True instead of 1) would be valid solutions, there are still bytes to be saved.
If we define a function f that takes the number n of round 1 candidates instead of the number m of round 2 candidates as first argument, i.e.,

we get the recursive formula

with base case

Finally, we have

so the Python implementation
f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)

(k/n yields 1 once n = k) solves the task at hand with 1-based indexing.


They call me Inspector Morse Your mission, should you choose to accept it, is to decide whether a given input string is Dot-heavy, or Dash-heavy.

A string is dot-heavy when its morse representation contains more dots than dashes. For example, the letter E is a single dot, which means it is Dot-heavy.

Input

The input string will only contain characters in the range of [a-z] or [A-Z]. You can decide if they should all be upper case, or all lower case. AAA is fine, aaa is fine, aAa is not.
The input string will always be at least 1 character in length.
You may assume that input strings will never have an equal amount of dots and dashes.

Output

You should return Truthy for inputs that contain more dot characters.
You should return Falsy for inputs that contain more dash characters.
Edit: I will allow a positive value for dot and a negative value for dash as well.

Test cases

| input | morse representation | result          |
|------------------------------------------------|
| S     | ...                  | Truthy          |
| k     | -.-                  | Falsy           |
| HELLO | .... . .-.. .-.. --- | Truthy          |
| code  | -.-. --- -.. .       | Falsy           |

Reference

This is code-golf. Shortest code in bytes wins.

Java (JDK), 131 124 110 84 64 bytes

Interestingly, "dot" is dash-heavy and "dash" is dot-heavy.

Takes input in all caps as an IntStream (scroll down for a version with an actual String for an extra 8 bytes). I've had quite a lot of help golfing this one: Thanks to Expired Data for golfing 20 bytes, to Neil for golfing 26 bytes, to Olivier Grégoire for golfing 18 bytes and to Kevin Cruijssen for golfing 2 bytes.

Contains 26 unprintable characters inside the double quotes.

c->c.map(a->"".charAt(a-65)-4).sum()>0

Try it online!

Ungolfed:

c -> // lambda taking input as an IntStream in upper case and returning a boolean
  c.map(a -> "" // map each character's ASCII value to its net dot impact (unprintable characters here)
    .charAt(a - 65) // translate the ASCII code into a zero-based index into the above string (65 is 'A')
    - 4) // unprintables are > 0, this restores the proper values
  .sum() > 0 // add up all the values, positive sum indicates a dot-heavy input string

Java (JDK), 131 124 110 84 72 bytes

For purists; takes input as a String. Thanks to Expired Data for golfing 20 bytes, to Neil for golfing 26 bytes and to Olivier Grégoire for golfing 10 bytes.

s->s.chars().map(a->"".charAt(a-65)-4).sum()>0

Try it online.

Ungolfed:

s -> // lambda taking input as a String in upper case and returning a boolean
  s.chars() // convert to a stream of characters
  .map(a -> "" // map each character's ASCII value to its net dot impact (unprintable characters here)
    .charAt(a - 65) // translate the ASCII code into a zero-based index into the above string (65 is 'A')
    - 4) // unprintables are > 0, this restores the proper values
  .sum() > 0 // add up all the values, positive sum indicates a dot-heavy input string


Bad matrix multiplication that gives the right answer Executive summary:
Print NxN matrices \$A\$ and \$B\$ where \$ AB = 10A + B \$. Largest N wins!
Details:
Entrants in this challenge should choose an N. Submit a program that takes an input integer 'seed', and produces two full rank NxN matrices \$A\$ and \$B\$, where each element of \$A\$ and \$B\$ is an integer from 0 to 9, and \$AB = 10A + B\$. In addition, matrices A and B must have at least half of their elements nonzero. The output should always be the same for a given seed. Runtime of your program is not limited, however as evidence that it does finish you must post a sample seed, the output of your program given that seed, and the time taken to compute.
Input and output format is not restricted.
Scoring:
First, largest N wins. Second, ties are broken by earliest submission.
No hard coding:
In order to prevent hard coding, there must be at least 10 seeds that produce distinct outputs, where outputs are not distinct if they are equal after exchanging rows, exchanging columns, and or transposing the matrix. You don't need to worry about proving this for good faith solutions.
Math Background / No Rules Below This Line
First of all, for a given candidate A, B is fixed:
$$AB = 10A + B\\    A = 10AB^{-1} + I\\    I = 10B^{-1} + A^{-1}\\    B = 10(I - A^{-1})^{-1}\\    B = 10(I + (A - I)^{-1})$$
One approach is to take the eigendecomposition of A.
From before,
$$    A = Q \Lambda_A Q^{-1}\\    B = 10(I - A^{-1})^{-1}\\    B = 10(Q I Q^{-1} - Q \Lambda_A^{-1} Q^{-1})^{-1}\\    B = Q(\frac{10}{(I - \Lambda_A^{-1})})Q^{-1}\\$$
This shows that A, B share eigenvectors Q, and their eigenvalues are assosciated by
$$    \Lambda_A \Lambda_B = 10 \Lambda_A + \Lambda_B\\ $$
Interestingly, this proves that AB = BA, ie our matrices commute!
We can calculate the determinant of B as \$10^N \frac{1}{\Pi_i (1 - \frac{1}{\lambda_{A,i}})}\$
This is very suggestive, but doesn't immediately yield a way to pick a matrix A such that B is small positive integers.
Because A and B share eigenvectors, B can be written as a linear combination of \$(I, A, A^2 ... ~ A^{N-1})\$. For example,
$$A = \left(\begin{array}{rrr}1 & 2 & 4 \\1 & 1 & 3 \\1 & 1 & 1\end{array}\right), B = \left(\begin{array}{rrr}7 & 4 & 6 \\3 & 6 & 4 \\1 & 2 & 8\end{array}\right)$$
$$\Lambda_A = \left(\begin{array}{rrr}-\sqrt{6} + 2 & 0 & 0 \\0 & \sqrt{6} + 2 & 0 \\0 & 0 & -1\end{array}\right), \Lambda_B = \left(\begin{array}{rrr}-\sqrt{6} + 2 & 0 & 0 \\0 & \sqrt{6} + 2 & 0 \\0 & 0 & -1\end{array}\right)$$
We observe that \$\Lambda_B = \Lambda_A^2 - 2 \Lambda_A + 2I\$, so \$B = A^2 - 2A + 2\$. In this case B is forced to be an integer matrix because it is possible to write B as an integer polynomial of A. If we can find large matrices where \$10(I + (\Lambda_A - I)^{-1})\$ is an integer polynomial of \$\Lambda_A\$, then that might provide an efficient solution.
Finally, if we write \$A\$ as \$E + I\$, then we can see some simplifications.
\$B = 10 * (E^{-1} + I)\$, so B is an integer matrix as long as the determinant of E divides 10.
With this E representation, our problem can become to find an integer matrix E such that
$$    E + I \geq 0\\    E^{-1} + I \geq 0\\    |E| = \pm 10\\$$
(Occasionally this will fail if an entry of \$ E^{-1} + I > 9\$ )
This represents an improvement, because once we find a [0-9] matrix E with determinant \$\pm 10 \$ (such as by random search), then if there are only a small number of negative entries in \$E^{-1}\$ we can run determinant-preserving transformations on E such as permuting rows to move those negative entries onto the diagonal, where they are made positive by the \$+I\$
In addition, there is a name and wikipedia page for matrices like \$E^{-1}\$ where the off diagonal entries are all positive: A Metzler Matrix. Further literature search in that direction might bring up an efficient way to generate positive integer matrices with a determinant \$\pm 10\$ whose inverses are Metzler Matrices.

Python, N = 7
Using variable neighborhood search over elementary row and column operations.  Not every seed works quickly (or at all?), but seed 9 finds a solution for N = 7 in a few seconds.
$ time python3 search.py 7 9
[[0 3 6 6 1 6 6]
 [0 1 5 5 0 5 5]
 [1 3 1 2 1 8 1]
 [0 0 1 0 0 1 0]
 [1 7 9 9 0 9 9]
 [1 3 1 1 1 0 1]
 [0 0 1 1 0 1 1]]
[[5 5 1 1 0 4 0]
 [1 7 0 0 1 0 0]
 [0 0 9 4 0 1 5]
 [0 0 0 5 0 0 5]
 [2 2 1 1 7 4 0]
 [0 0 1 1 0 9 0]
 [0 2 0 0 0 0 0]]

real    0m4.909s
user    0m4.883s
sys     0m0.026s

Code
import itertools
import sys

import numpy as np

def search(depth, C, D, best):
    A = C + I
    B = D + 10 * I
    x = np.r_[A, B].flatten()
    score = (
        np.maximum(0, np.maximum(x - 9, 1 - x)).sum()
        - min((A == 0).sum(), -(-n * n // 2))
        - min((B == 0).sum(), -(-n * n // 2))
        + 2 * n
        - np.linalg.matrix_rank(A)
        - np.linalg.matrix_rank(B)
    )
    if best is None or score < best:
        return C, D, score
    if depth == 0:
        return None

    tried = {}
    for i in reversed(range(n * (n - 1) * 5)):
        j = rng.integers(i + 1)
        mutation, tried[j] = tried.get(j, j), tried.get(i, i)
        p, mutation = divmod(mutation, (n - 1) * 5)
        q, mutation = divmod(mutation, 5)
        q = (p + q + 1) % n
        C1 = C.copy()
        D1 = D.copy()

        if mutation == 0:
            C1[p, :] += C1[q, :]
            D1[:, q] -= D1[:, p]
        elif mutation == 1:
            C1[p, :] -= C1[q, :]
            D1[:, q] += D1[:, p]
        elif mutation == 2:
            C1[:, p] += C1[:, q]
            D1[q, :] -= D1[p, :]
        elif mutation == 3:
            C1[:, p] -= C1[:, q]
            D1[q, :] += D1[p, :]
        elif p < q:
            C1[[p, q], :] = C1[[q, p], :]
            D1[:, [p, q]] = D1[:, [q, p]]
        else:
            C1[:, [p, q]] = C1[:, [q, p]]
            D1[[p, q], :] = D1[[q, p], :]

        ret = search(depth - 1, C1, D1, best)
        if ret is not None:
            return ret

    return None

n, seed = map(int, sys.argv[1:])
rng = np.random.default_rng(seed)
I = np.eye(n, dtype=int)
score = None
k = rng.integers(0, 8, n)
C = np.diag(np.array([-10, -5, -2, -1, 1, 2, 5, 10])[k])
D = np.diag(np.array([-1, -2, -5, -10, 10, 5, 2, 1])[k])
depth = 1

while score != 0:
    ret = search(depth, C, D, score)
    if ret is not None:
        C, D, score = ret
        depth = 0
    depth += 1

A = C + I
B = D + 10 * I
assert (A @ B == 10 * A + B).all()
print(A)
print(B)


Find the inside of a Loop Task

Given a ASCII diagram of a loop

e.g.

....................
......@@@@@.........
......@...@.........
.....@@...@@@@@.....
....@@........@.....
....@........@@.....
....@@@@@@@@@@......
....................
....................

And a location on the loop

e.g.

(7,1)

You must find the inside and outside of the loop

e.g.

00000000000000000000
00000011111000000000
00000011111000000000
00000111111111100000
00001111111111100000
00001111111111100000
00001111111111000000
00000000000000000000
00000000000000000000

Specifications

You may take input for the diagram as a string separated by newlines or obvious equivalent
You will receive a coordinate on the loop (0 or 1 indexed) as part of your input.  You may place your origin at any place you wish.  You may take this coordinate in (<row>, <column>), (<column>, <row>) or as the linear position on the string.  You may receive these data in any reasonable method.  All characters on the loop will be the same as the character at that index.
Preferred output is a 2 dimensional array of truthy and falsy values, however strings of 1 and 0 separated by newlines or any obvious equivalent of the later two are accepted.  The inside and outside must have different truth values but it does not matter which is which.
A loop is defined as a group of characters such that they are all the same character (e.g. @) and so that every character in the loop has a path to the original character (The character at the coordinate of input) that only passes through that same character (Taxicab geometry No diagonals).
The inside is all the loop itself and the places that cannot reach the edge of the diagram without crossing the loop.
The outside is everywhere else
This is code-golf

Test Cases

PasteBin

MATLAB, 163 159 146 78 bytes
function m=f(m,y,x);[~,i]=bwfill(m~=m(y,x),x,y,8);m=m*0;m(i)=1;m=bwfill(m,'h')

Thanks @rahnema1 for -66 bytes!!!
Now it does work on Try it online! BUT a few adjustments were needed, as MATLAB and Octave are not entirely compatible.
Explanation
First we make a binary image that just masks all the characters that are equal to the initial character. Then we determine the connected component the initial character is in.
% determine the connected component that is contains initial character

[~,i]=bwfill(m~=m(y,x),x,y,8);     % i contains the indices of the connected component
m=m*0;m(i)=1;                      % create an image of the connected component

After that we create an image of that connected component and apply fill all the "holes" in the image.
m=bwfill(m,'h')


Digits Digging a Dungeon Edit: I will award a 100-reputation bounty for the first solver of the bonus puzzle at the end of the question!
I will add the bounty to the question only when the answer appears as this bounty has no deadline.

Given a non-decreasing list of one-digit positive integers, you should determine how deep dungeon the digits will dig.
███  ███  A dungeon with 5 blocks removed and a depth of 3.
███  ███
███ ████
████████

Before the start of the digging the ground is level.
Every digit can remove exactly one block of soil from below itself but it has to reach that position from outside the dungeon and after it removed the block has to leave the dungeon. While doing so a digit can't descend or ascend more than its numerical value at any horizontal step.
The digits use the following strategy for digging:

The digit with the smallest value digs firsts and after that the next digger is always the next smallest value from the rest of the digits.
The first digit can dig at any position. (All ground is the same.)
The following digits always dig at the leftmost already started column where they can go and come out. If no such column exists they start to dig a new column on the right side of the rightmost one.

For example the digits 1 1 1 2 3 3 would dig the following dungeon (step-by-step visualization with numbers marking which kind of digit dig out that position):
███1████    ███11███    ███11███    ███11███    ███11███    ███11███
████████    ████████    ███1████    ███1████    ███1████    ███13███
████████    ████████    ████████    ███2████    ███2████    ███2████
████████    ████████    ████████    ████████    ███3████    ███3████
████████    ████████    ████████    ████████    ████████    ████████

Explanation for the example:

The second 1 couldn't climb out of the only available column if it would deepen it to 2-deep so it digs right to it.
The third 1 can dig in the leftmost column creating a 2-deep column as it can move out into the 1-deep column and then to the ground level.
The next 2 and 3 both can dig in the leftmost column.
The last 3 can't dig in the leftmost column but can in the next one.

Input

A non-decreasing list of positive one-digit integers with at least one element.

Output

A single positive integer, the depth of the constructed dungeon.

Examples
Input => Output (with the depths of the columns of the dungeon from left to right as explanation which is not part of the output)
[3]  =>  1
(column depths are [1])

[1, 1, 1, 2, 3, 3]  =>  4
(column depths are [4, 2])

[1, 1, 1, 1, 1, 1, 1, 1]  =>  3
(column depths are [3, 2, 2, 1])

[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5]  =>  11
(column depths are [11, 6, 2])

[1, 1, 1, 1, 1, 2, 2, 9, 9, 9]  =>  7
(column depths are [7, 2, 1])

[2, 2, 2, 2, 2, 5, 5, 5, 7, 7, 9]  =>  9
(column depths are [9, 2])

[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5]  =>  10
(column depths are [10, 5])

[1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 9]  =>  13
(column depths are [13, 5])

[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]  =>  13
(column depths are [13, 5])

[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9]  =>  21
(column depths are [21, 12, 3])

This is code-golf so the shortest entry wins.
Bonus puzzle
Can you prove (or disprove) that the strategy described in the "The digits use the following strategy for digging" section always gives the deepest possible dungeon for the given digits?

Pyth, 21 bytes

huXf>+H@GhT@GT0G1Qm0Q

Try it online: Single Demonstration or Test Suite

Explanation:

                  m0Q   generate a list of zeros of length len(input)
                        This will simulate the current depths
 u               Qm0Q   reduce G, starting with G=[0,...,0], for H in input():
   f          0             find the first number T >= 0, which satisfies:
    >+H@GhT@GT                  H + G[T+1] > G[T]
  X            G1           increase the depth at this position by one
                            update G with this result
h                       print the first element in this list


Compute the height of a radix tree Introduction

A radix tree, also known as compressed trie or compressed prefix tree, is a tree-like data structure for storing a set of strings.
The edges of the tree are labeled by nonempty strings, and each node is either terminal or nonterminal.
The strings that the tree contains are exactly the labels of all paths from the root to a terminal node.
The tree must be in the normal form defined by the following conditions:

All nonterminal non-root nodes have at least two children.
For every node, all outgoing edges have different first characters.

For example, here is the radix tree containing the set ["test", "testing", "tested", "team", "teams", "technical", "sick", "silly"], with (N) representing a nonterminal node and (T) a terminal node:

-(N)-te-(N)-st-(T)-ing-(T)
  |      |      |
  |      |      +-ed-(T)
  |      |
  |      +-am-(T)-s-(T)
  |      |
  |      +-chnical-(T)
  |
  +-si-(N)-ck-(T)
        |
        +-lly-(T)

In this challenge, your task is to compute the height of the tree, given the strings as input.

Input

Your input is a non-empty list of strings of lowercase ASCII letters.
It will not contain duplicates, but it may be in any order.
It may contain the empty string.
You may take the input in any reasonable format.

Output

Your output shall be the length of the longest root-to-leaf path in the corresponding radix tree, measured in the number of nodes it contains.

In the above example, the correct output is 4, corresponding to the paths

(N)-te-(N)-st-(T)-ing-(T)
(N)-te-(N)-st-(T)-ed-(T)
(N)-te-(N)-am-(T)-s-(T)

which contain 4 nodes.

Further examples

Here are a couple more examples of radix trees:

[""]
-(T)

["","fuller"]
-(T)-fuller-(T)

["","full","fuller"]
-(T)-full-(T)-er-(T)

["full","fuller"]
-(N)-full-(T)-er-(T)

["full","filler"]
-(N)-f-(N)-ull-(T)
        |
        +-iller-(T)

Rules and scoring

You can write a full program or a function.
This is code golf, so the lowest byte count wins.

You can use any built-ins or libraries you want, but remember to include all imports etc. in your byte count.
Third-party libraries – those not included in the standard install of your language – are allowed, but must be listed in the header separately, e.g. Python + pytrie0.2, 60 bytes.

Test cases

[""] -> 1
["fuller"] -> 2
["","fuller"] -> 2
["","full","fuller"] -> 3
["full","fuller"] -> 3
["full","filler"] -> 3
["full","filler","filter"] -> 4
["full","filler","fi","filter"] -> 5
["test","testing","tested","team","teams","technical","sick","silly"] -> 4
["a","aaaa","aabbaa","aabbaab","abaaa","aab","aabbb","aabba"] -> 8
["dbdbaca","ab","a","caaabaaa","adbbabdb","dbdbdbaca","dbbadbacaba","db"] -> 4
["db","dbbdbb","dbaa","cabcacaa","","acaabcacab","b","abaaaca","bacaaaaa"] -> 3
["aabaabdbb","bacaabadbbdb","abb","aabaa","ab","bcadbb","adbbcaaadbbb","caaa","bbdbcacadbab","dbbdbdb"] -> 4
["bbcaaabbbabbcadbbacadbbdbdb","b","bbbbaaaaaababa","ca","bb","bdbbacadbbdbbdbbababaacaca","abbaabbabcabaaa","bbbacacacabcacacabaaabb","bbcaaaab","bbbbcaacaadbcaaa","babbabcadbdbacacabbcacab","abcabbbaacadbcadb","bbcabbcadbcacaacaadbadbcaadb","dbbbdbbdbacaabbacabcadbdbacaca","bbaabdbdb","cabcadbbbadbadbbaadbcaca","adbadbadbdbcacadbdbbcaadbcaca","abaabbcab","aaabcaabcaab","bacacabcacaacadbadbb"] -> 6

JavaScript (Firefox 30-57), 137 bytes

f=(a,b=["",...a],s=new Set(b.map(w=>w[0])))=>b.length>1?(s.size>1)+Math.max(...(for(c of s)f(a,[for(w of b)if(w&&w[0]==c)w.slice(1)]))):1

There must be something wrong with my algorithm as I seem to have to special-case an empty string parameter.


Settlers of Catan - Longest Road! This is an endgame board of Settlers of Catan:

Background:

The roads (the long stick pieces) and the settlements (and cities) are rendered by the little huts. We encode the placement of these pieces by using the following scheme: From the top, we have a row horizontal vertices and edges where a road can be placed. Then we have a column of only roads, and so forth. Using R for Red, O for Orange, and B for Blue, and _ for nothing, the pictured board would be encoded as:

________RR_R_
__R_
__RR_R_RRR_____R_
B___R
_B_________B__OO_OOR_
B__B_R
BB_BBB_____B____RR_R_
OBB_O
OO__BB_BB__OOO_OO
O_O_
_O_OOO_O_____

A board like this will be your input string. Any letter [A-Z] may indicate a player color, but there will at most four colors (including empty). Boards are otherwise guaranteed to be valid according to the rules of Settlers, which means:

Each color will have at most two contiguous road networks, which may or may not be broken apart by other players settlements / cities (vertex buildings). See the orange settlement breaking apart the red road on the right side of the sample image.

Each road network is guaranteed to have at least one settlement.

All settlements and cities are guaranteed to be at least two edges from the nearest other settlement / city (yours or otherwise)
One player may only have 15 roads on the game board.
For Catan enthusiasts: there is no distinction between settlements and cities for the purpose of this problem, so I don't distinguish in the input string.

All this is for the specification of the "input" string.

Longest Road:

In Settlers, players get two victory points for having the "longest road". This is defined to be: The longest contiguous single path (measured in roads) from start point to end point, that is not broken up by an opponents settlement or city. Cycles are okay, as long as you can trace the path from one particular start point to one particular end point. So, a loop of 6 roads plus one road branching off is length 7, but one with two branching off the 6 road loop on opposite sides is still only worth 7.

In the example map, the Red road on the right side is only worth 4, because he is cut off by an Orange settlement on the right side of the board (that's why settlements are included at all). Blue has a road of length 13, and Orange has a road of length 12. Red's top road is only worth 7, because it doesn't connect to the two single roads next to it.

Output:

All players that have a road of the longest length (it could be more than one if there are ties), followed by a whitespace and/or underscore delimited count in base 10 of how long that road is.

So the output for the example board would be:

B 13

The Problem statement:

You may write a program or function, receives the input board via STDIN or as a string argument to your function, which returns the output described above as a string or prints it to STDOUT (or closest alternative). You may optionally include a single trailing newline in the output.

This is code-golf, shortest program wins. Standard loopholes are banned, of course.

Python 2, 445 400 bytes
I'm a fan of Settlers, so this challenge was fun.
T="^"
Z=26
A=T*52
for i in range(11):A+=(T*(i%2)*3).join(x for x in raw_input()).center(Z,T)
A+=T*52
def f(c,p=0,l=0,B=A):
 b=l;C=B[0:p]+T+B[p+1:];n=(Z,1)[p%2]
 for i in(p<1)*range(390):
    if(i/Z%2<1&i%2>0)|(i/Z%2>0&i%2<1):b=max(b,f(c,i))
 for i in(p-n,p+n)*(B[p]==c):
    for j in(i-Z,i-1,i+1,i+Z)*(B[i]in c+"_"):b=max(b,f(c,j,l+1,C))
 return b
i=l=0
for x in A:
 if x<T:i=f(x)
 if i>l:c=x;l=i
print c,l

Score reflects replacing each occurrence of 4 spaces with a tab.
Explanation
The lines before the function definition read the input, and build a normalized board into a single string variable.  The process inserts "^" characters into the short lines representing the vertical road segments.  It also pads the board with "^" characters.
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^________RR_R_^^^^^^^
^^^^^^_^^^_^^^R^^^_^^^^^^^
^^^^__RR_R_RRR_____R_^^^^^
^^^^B^^^_^^^_^^^_^^^R^^^^^
^^_B_________B__OO_OOR_^^^
^^B^^^_^^^_^^^B^^^_^^^R^^^
^^BB_BBB_____B____RR_R_^^^
^^^^O^^^B^^^B^^^_^^^O^^^^^
^^^^OO__BB_BB__OOO_OO^^^^^
^^^^^^O^^^_^^^O^^^_^^^^^^^
^^^^^^_O_OOO_O_____^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^

When called with the default parameters, the function returns the length of a road of a given color.  The first loop is active only when the position (p) parameter was supplied.  It recursively finds the length of the road at each valid road position, and keeps track of the longest one.  When there is a road at the position parameter, the function recursively adds the length of adjacent roads of the same color.  The road is replaced with a "~" in the working copy of the board to ensure it doesn't recount segments that have already been counted.
The code following the function definition calls the function for each color in the board, and prints the highest scoring color and length.
Demo it here


Eye test - How many squares are in this picture? The picture:

Sick of the same old grid where the answer is simply a square pyramidal number?
Accept the challenge and write a program that given a positive integer \$n\$ counts how many squares are in the \$n^{\text{th}}\$ iteration of the Harter-Heighway dragon!

The sequence of squares of size 1 is A003230
Your code must count all the squares of any size (the first of size 2 show up in \$7^{\text{th}}\$ iteration)
This is code-golf

Here's the beginning of the resulting sequence:
0, 0, 0, 1, 4, 11, 30, 78, 205, 546, 1455, 4062, 11192, 31889, 88487, 254594

And my un-golfed reference program in Mathematica.

Charcoal, 96 bytes
Ｆ…¹Ｘ²Ｎ«Ｆ¬⁼ＫＫ#⊞υ⟦ⅉⅈ⟧##¿＆ι⊗＆ι±ι↷↶»↷≔⁰ζＦυ«Ｊ⊟ι⊟ι≔¹ηＷ⬤ur⁼№ＫＤ⊗η✳λ#⊗η≦⊕ηＦη¿κ«↗↗≧⁺⬤dl⁼№ＫＤ⊗κ✳λ#⊗κζ»»⎚Ｉζ

Try it online! Link is to verbose version of code. Explaantion:
Ｆ…¹Ｘ²Ｎ«

Loop over all the turns of the nᵗʰ iteration of the dragon.
Ｆ¬⁼ＫＫ#⊞υ⟦ⅉⅈ⟧

If we haven't visited this cell yet then record its position.
##

Print a segment of the dragon.
¿＆ι⊗＆ι±ι↷↶

Rotate appropriately for the next segment.
»↷

At the end of the dragon, rotate back to horizontal. (Clear() doesn't do this; maybe it should?)
≔⁰ζ

Start counting squares.
Ｆυ«Ｊ⊟ι⊟ι

Loop over and jump to each visited cell.
≔¹η

Start searching for squares.
Ｗ⬤ur⁼№ＫＤ⊗η✳λ#⊗η≦⊕η

While there are enough #s in both the upwards and rightwards directions increase the size of square being searched for.
Ｆη¿κ«

Check all sizes of squares from 1 to the largest potential size found.
↗↗≧⁺⬤dl⁼№ＫＤ⊗κ✳λ#⊗κζ

Move diagonally up and right two cells, then check downwards and leftwards for the other two sides of the square of this size and keep a running total of squares found.
»»⎚Ｉζ

Once all potential squares have been checked clear the canvas and output the final number found.


Find the largest value of power. Some numbers can be represented as perfect powers of other numbers. A number x can be represented as x = base^power for some integer base and power.

Given an integer x you have to find the largest value of power, such that base is also an integer.

Sample Input:
9
Sample Output:
2

Golfscript - 26 chars

~:x,{:b;x,{b?x=b*}%+}*$-1>

Rough translation to Python

x=input()
acc = []
for b in range(x):
    for _ in range(x):
        acc.append((_**b==x)*b) # most of these are zeros
print max(acc)

So it loops way more times that necessary, but that often happens with golfed answers


Peaceable coexisting armies In the game of chess, there is piece called the queen that may attack any other piece that is on the same row, column or diagonal. In chess there are typically two sides, black and white, with each piece belonging to one of the teams. Pieces may not attack pieces belong to the same team.

Your goal is to find out the largest peaceable coexisting armies for a square board. That is the largest number of black and white queens that can fit on the board such that no two queens can attack each other and the number of black queens is equal to the number of white queens.

You will receive as input the side length of a square board, and should output the number of size of the largest peaceable coexisting armies that can fit on that board.

This is code-golf so standard rules for the tag apply.

OEIS A250000

These test cases encompass all known answers. Your solution should be a generalized answer that, given enough computing power and time, can compute the solution for any input value.

1: 0
2: 0
3: 1
4: 2
5: 4
6: 5
7: 7
8: 9
9: 12
10: 14
11: 17
12: 21
13: 24