Fill the rows, columns, and diagonals of an NxN grid with 1 through N Task

Given input N, generate and output an NxN grid where each row, column and the two diagonals contain the numbers 1 to N (or 0 to N−1 if that's easier).

Input

The input is a positive integer N. It represents the number of columns and rows in the grid. For this problem, you can assume N will be a reasonable size, 4 ≤ N ≤ 8 or (1 ≤ N ≤ 8 if you go for the bonus below).

Output

The output will be the N×N grid. In the grid, each row only contains the numbers 1 to N, each column only contains the numbers 1 to N, and the two diagonals of length N (the one from (0,0) to (N-1,N-1) and the one from (0,N-1) to (N-1, 0)) only contain the numbers 1 to N. You can use the numbers 0 to N−1. For each N, there are many possible solutions, you only need to print the first one you find. You don't need to print spaces between the numbers.

Constraints

Your code should be able to repeatably produce results for N >= 7. That is, if you're able to actually run and get a solution for N = 7 from your code each time, you're good. In terms of an absolute limit, your code should be able to solve for N = 7 in under 10 minutes each time you run it (i.e., if you depend on random numbers, for the worst case, your code should still finish in under 10 minutes for N = 7).

Examples

Input: 4

One possible output:

1 2 3 4
3 4 1 2
4 3 2 1
2 1 4 3

Input: 5

One possible output:

1 2 3 4 5
5 3 1 2 4
2 5 4 3 1
4 1 2 5 3
3 4 5 1 2

Input: 8

One possible output:

1 2 3 4 5 6 7 8
2 3 1 5 4 8 6 7
4 1 2 3 7 5 8 6
6 4 7 8 1 2 3 5
7 5 8 2 6 3 4 1
5 8 4 6 2 7 1 3
8 7 6 1 3 4 5 2
3 6 5 7 8 1 2 4

Scoring

This is code-golf, so the shortest code in bytes wins, with one exception. For inputs N = 2, 3 there are no valid solutions. If your code can handles this (run to completion without outputting anything for these cases, or outputting an empty string), and still handles N = 1 (outputs 1 for it), take 20% off your byte count.

Funciton, non-competitive

UPDATE! Massive performance improvement! n = 7 now completes in under 10 minutes! See explanation at bottom!

This was good fun to write. This is a brute-force solver for this problem written in Funciton. Some factoids:

It accepts an integer on STDIN. Any extraneous whitespace breaks it, including a newline after the integer.
It uses the numbers 0 to n − 1 (not 1 to n).
It fills the grid “backwards”, so you get a solution where the bottom row reads 3 2 1 0 rather than where the top row reads 0 1 2 3.
It correctly outputs 0 (the only solution) for n = 1.
Empty output for n = 2 and n = 3.
When compiled to an exe, takes about 8¼ minutes for n = 7 (was about one hour before the performance improvement). Without compiling (using the interpreter) it takes about 1.5 times as long, so using the compiler is worth it.
As a personal milestone, this is the first time I wrote a whole Funciton program without first writing the program in a pseudocode language. I did write it in actual C# first though.
(However, this is not the first time I made a change to massively improve the performance of something in Funciton. The first time I did that was in the factorial function. Swapping the order of the operands of the multiplication made a huge difference because of how the multiplication algorithm works. Just in case you were curious.)

Without further ado:

            ┌────────────────────────────────────┐           ┌─────────────────┐
            │                                  ┌─┴─╖ ╓───╖ ┌─┴─╖   ┌──────┐    │
            │                    ┌─────────────┤ · ╟─╢ Ӂ ╟─┤ · ╟───┤      │    │
            │                    │             ╘═╤═╝ ╙─┬─╜ ╘═╤═╝ ┌─┴─╖    │    │
            │                    │               └─────┴─────┘   │ ♯ ║    │    │
            │                  ┌─┴─╖                             ╘═╤═╝    │    │
            │     ┌────────────┤ · ╟───────────────────────────────┴───┐  │    │
          ┌─┴─╖ ┌─┴─╖   ┌────╖ ╘═╤═╝ ┌──────────┐         ┌────────┐ ┌─┴─╖│    │
          │ ♭ ║ │ × ╟───┤ >> ╟───┴───┘        ┌─┴─╖       │ ┌────╖ └─┤ · ╟┴┐   │
          ╘═╤═╝ ╘═╤═╝   ╘══╤═╝          ┌─────┤ · ╟───────┴─┤ << ╟─┐ ╘═╤═╝ │   │
    ┌───────┴─────┘ ┌────╖ │            │     ╘═╤═╝         ╘══╤═╝ │   │   │   │
    │     ┌─────────┤ >> ╟─┘            │       └───────┐      │   │   │   │   │
    │     │         ╘══╤═╝            ┌─┴─╖   ╔═══╗   ┌─┴─╖ ┌┐ │   │ ┌─┴─╖ │   │
    │     │           ┌┴┐     ┌───────┤ ♫ ║ ┌─╢ 0 ║ ┌─┤ · ╟─┤├─┤   ├─┤ Ӝ ║ │   │
    │     │   ╔═══╗   └┬┘     │       ╘═╤═╝ │ ╚═╤═╝ │ ╘═╤═╝ └┘ │   │ ╘═╤═╝ │   │
    │     │   ║ 1 ╟───┬┘    ┌─┴─╖       └───┘ ┌─┴─╖ │   │      │   │   │ ┌─┴─╖ │
    │     │   ╚═══╝ ┌─┴─╖   │ ɓ ╟─────────────┤ ? ╟─┘   │    ┌─┴─╖ │   ├─┤ · ╟─┴─┐
    │     ├─────────┤ · ╟─┐ ╘═╤═╝             ╘═╤═╝   ┌─┴────┤ + ╟─┘   │ ╘═╤═╝   │
  ┌─┴─╖ ┌─┴─╖       ╘═╤═╝ │ ╔═╧═╕ ╔═══╗ ┌───╖ ┌─┴─╖ ┌─┴─╖    ╘═══╝     │   │     │
┌─┤ · ╟─┤ · ╟───┐     └┐  └─╢   ├─╢ 0 ╟─┤ ⌑ ╟─┤ ? ╟─┤ · ╟──────────────┘   │     │
│ ╘═╤═╝ ╘═╤═╝   └───┐ ┌┴┐   ╚═╤═╛ ╚═╤═╝ ╘═══╝ ╘═╤═╝ ╘═╤═╝                  │     │
│   │   ┌─┴─╖ ┌───╖ │ └┬┘   ┌─┴─╖ ┌─┘           │     │                    │     │
│ ┌─┴───┤ · ╟─┤ Җ ╟─┘  └────┤ ? ╟─┴─┐   ┌─────────────┘                    │     │
│ │     ╘═╤═╝ ╘═╤═╝         ╘═╤═╝   │   │╔════╗╔════╗                      │     │
│ │       │  ┌──┴─╖ ┌┐   ┌┐ ┌─┴─╖ ┌─┴─╖ │║ 10 ║║ 32 ║    ┌─────────────────┘     │
│ │       │  │ << ╟─┤├─┬─┤├─┤ · ╟─┤ · ╟─┘╚══╤═╝╚╤═══╝ ┌──┴──┐                    │
│ │       │  ╘══╤═╝ └┘ │ └┘ ╘═╤═╝ ╘═╤═╝     │ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖                  │
│ │     ┌─┴─╖ ┌─┴─╖  ┌─┴─╖  ┌─┴─╖ ╔═╧═╕     └─┤ ? ╟─┤ · ╟─┤ % ║                  │
│ └─────┤ · ╟─┤ · ╟──┤ Ӂ ╟──┤ ɱ ╟─╢   ├───┐   ╘═╤═╝ ╘═╤═╝ ╘═╤═╝                  │
│       ╘═╤═╝ ╘═╤═╝  ╘═╤═╝  ╘═══╝ ╚═╤═╛ ┌─┴─╖ ┌─┴─╖   │     └────────────────────┘
│         └─────┤      │            └───┤ ‼ ╟─┤ ‼ ║   │        ┌──────┐
│               │      │                ╘═══╝ ╘═╤═╝   │        │ ┌────┴────╖
│               │      │                      ┌─┴─╖   │        │ │ str→int ║
│               │      └──────────────────────┤ · ╟───┴─┐      │ ╘════╤════╝
│               │          ┌─────────╖        ╘═╤═╝     │    ╔═╧═╗ ┌──┴──┐
│               └──────────┤ int→str ╟──────────┘       │    ║   ║ │ ┌───┴───┐
│                          ╘═════════╝                  │    ╚═══╝ │ │ ┌───╖ │
└───────────────────────────────────────────────────────┘          │ └─┤ × ╟─┘
           ┌──────────────┐                                  ╔═══╗ │   ╘═╤═╝
╔════╗     │ ╓───╖ ┌───╖  │                              ┌───╢ 0 ║ │   ┌─┴─╖ ╔═══╗
║ −1 ║     └─╢ Ӝ ╟─┤ × ╟──┴──────┐                       │   ╚═╤═╝ └───┤ Ӂ ╟─╢ 0 ║
╚═╤══╝       ╙───╜ ╘═╤═╝         │                       │   ┌─┴─╖     ╘═╤═╝ ╚═══╝
┌─┴──╖ ┌┐ ┌───╖ ┌┐ ┌─┴──╖ ╔════╗ │                       │ ┌─┤   ╟───────┴───────┐
│ << ╟─┤├─┤ ÷ ╟─┤├─┤ << ║ ║ −1 ║ │                       │ │ └─┬─╜ ┌─┐ ┌─────┐   │
╘═╤══╝ └┘ ╘═╤═╝ └┘ ╘═╤══╝ ╚═╤══╝ │                       │ │   └───┴─┘ │   ┌─┴─╖ │
  │         └─┘      └──────┘    │                       │ └───────────┘ ┌─┤ ? ╟─┘
  └──────────────────────────────┘         ╓───╖         └───────────────┘ ╘═╤═╝
                               ┌───────────╢ Җ ╟────────────┐                │
      ┌────────────────────────┴───┐       ╙───╜            │
      │                          ┌─┴────────────────────┐ ┌─┴─╖
    ┌─┴─╖                      ┌─┴─╖                  ┌─┴─┤ · ╟──────────────────┐
    │ ♯ ║ ┌────────────────────┤ · ╟───────┐          │   ╘═╤═╝                  │
    ╘═╤═╝ │                    ╘═╤═╝       │          │     │              ┌───╖ │
┌─────┴───┘    ┌─────────────────┴─┐   ┌───┴───┐    ┌─┴─╖ ┌─┴─╖          ┌─┤ × ╟─┴─┐
│              │                 ┌─┴─╖ │   ┌───┴────┤ · ╟─┤ · ╟──────────┤ ╘═╤═╝   │
│              │ ┌───╖ ┌───╖  ┌──┤ · ╟─┘ ┌─┴─┐      ╘═╤═╝ ╘═╤═╝        ┌─┴─╖ │     │
│         ┌────┴─┤ ♭ ╟─┤ × ╟──┘  ╘═╤═╝   │ ┌─┴─╖ ┌───╖└┐ ┌──┴─╖      ┌─┤ · ╟─┘     │
│         │      ╘═══╝ ╘═╤═╝ ┌───╖ │     │ │ × ╟─┤ Ӝ ╟─┴─┤ ÷% ╟─┐    │ ╘═╤═╝ ┌───╖ │
│   ┌─────┴───┐     ┌────┴───┤ Ӝ ╟─┴─┐   │ ╘═╤═╝ ╘═╤═╝   ╘══╤═╝ │    │   └───┤ Ӝ ╟─┘
│ ┌─┴─╖ ┌───╖ │     │ ┌────╖ ╘═╤═╝   │   └───┘   ┌─┴─╖      │   │    └────┐  ╘═╤═╝
│ │ × ╟─┤ Ӝ ╟─┘     └─┤ << ╟───┘   ┌─┴─╖ ┌───────┤ · ╟───┐  │ ┌─┴─╖ ┌───╖ │    │
│ ╘═╤═╝ ╘═╤═╝         ╘══╤═╝   ┌───┤ + ║ │       ╘═╤═╝   ├──┴─┤ · ╟─┤ × ╟─┘    │
└───┤     └────┐ ╔═══╗ ┌─┴─╖ ┌─┴─╖ ╘═╤═╝ │ ╔═══╗ ┌─┴─╖ ┌─┴─╖  ╘═╤═╝ ╘═╤═╝      │
  ┌─┴─╖ ┌────╖ │ ║ 0 ╟─┤ ? ╟─┤ = ║  ┌┴┐  │ ║ 0 ╟─┤ ? ╟─┤ = ║    │     │ ┌────╖ │
  │ × ╟─┤ << ╟─┘ ╚═══╝ ╘═╤═╝ ╘═╤═╝  └┬┘  │ ╚═══╝ ╘═╤═╝ ╘═╤═╝    │     └─┤ << ╟─┘
  ╘═╤═╝ ╘═╤══╝ ┌┐     ┌┐ │     │     └───┘       ┌─┴─╖   ├──────┘       ╘═╤══╝
    │     └────┤├──┬──┤├─┘     ├─────────────────┤ · ╟───┘                │
    │          └┘┌─┴─╖└┘       │     ┌┐   ┌┐     ╘═╤═╝ ┌┐   ┌┐            │
    └────────────┤ · ╟─────────┘   ┌─┤├─┬─┤├─┐     └───┤├─┬─┤├────────────┘
                 ╘═╤═╝             │ └┘ │ └┘ │         └┘ │ └┘
                   └───────────────┘    │    └────────────┘

Explanation of the first version

The first version took about an hour to solve n = 7. The following explains mostly how this slow version worked. At the bottom I will explain what change I made to get it to under 10 minutes.

An excursion into bits

This program needs bits. It needs lots of bits, and it needs them in all the right places. Experienced Funciton programmers already know that if you need n bits, you can use the formula

which in Funciton can be expressed as

When doing my performance optimization, it occurred to me that I can calculate the same value much faster using this formula:

I hope you’ll forgive me that I didn’t update all the equation graphics in this post accordingly.

Now, let’s say you don’t want a contiguous block of bits; in fact, you want n bits at regular intervals every k-th bit, like so:

                                 LSB
                                  ↓
00000010000001000000100000010000001
                            └──┬──┘
                               k

The formula for this is fairly straight-forward once you know it:

In the code, the function Ӝ takes values n and k and calculates this formula.

Keeping track of used numbers

There are n² numbers in the final grid, and each number can be any of n possible values. In order to keep track of which numbers are permitted in each cell, we maintain a number consisting of n³ bits, in which a bit is set to indicate that a particular value is taken. Initially this number is 0, obviously.

The algorithm begins in the bottom-right corner. After “guessing” the first number is a 0, we need to keep track of the fact that the 0 is no longer permitted in any cell along the same row, column and diagonal:

LSB                               (example n=5)
 ↓
 10000 00000 00000 00000 10000
 00000 10000 00000 00000 10000
 00000 00000 10000 00000 10000
 00000 00000 00000 10000 10000
 10000 10000 10000 10000 10000
                             ↑
                            MSB

To this end, we calculate the following four values:

Current row: We need n bits every n-th bit (one per cell), and then shift it to the current row r, remembering every row contains n² bits:

Current column: We need n bits every n²-th bit (one per row), and then shift it to the current column c, remembering every column contains n bits:

Forward diagonal: We need n bits every... (did you pay attention? Quick, figure it out!)... n(n+1)-th bit (well done!), but only if we’re actually on the forward diagonal:

Backward diagonal: Two things here. First, how do we know if we’re on the backward diagonal? Mathematically, the condition is c = (n − 1) − r, which is the same as c = n + (−r − 1). Hey, does that remind you of something? That’s right, it’s two’s complement, so we can use bitwise negation (very efficient in Funciton) instead of the decrement. Second, the formula above assumes that we want the least significant bit to be set, but in the backward diagonal we don’t, so we have to shift it up by... do you know?... That’s right, n(n − 1).

This is also the only one where we potentially divide by 0 if n = 1. However, Funciton doesn’t care. 0 ÷ 0 is just 0, don’t you know?

In the code, the function Җ (the bottom one) takes n and an index (from which it calculates r and c by division and remainder), calculates these four values and ors them together.

The brute-force algorithm

The brute-force algorithm is implemented by Ӂ (the function at the top). It takes n (the grid size), index (where in the grid we’re currently placing a number), and taken (the number with n³ bits telling us which numbers we can still place in each cell).

This function returns a sequence of strings. Each string is a full solution to the grid. It’s a complete solver; it would return all solutions if you let it, but it returns them as a lazy-evaluated sequence.

If index has reached 0, we’ve successfully filled the whole grid, so we return a sequence containing the empty string (a single solution that covers none of the cells). The empty string is 0, and we use the library function ⌑ to turn that into a single-element sequence.
The check described under performance improvement below happens here.
If index has not yet reached 0, we decrement it by 1 to get the index at which we now need to place a number (call that ix).

We use ♫ to generate a lazy sequence containing the values from 0 to n − 1.

Then we use ɓ (monadic bind) with a lambda that does the following in order:

First look at the relevant bit in taken to decide whether the number is valid here or not. We can place a number i if and only if taken & (1 << (n × ix) << i) isn’t already set. If it is set, return 0 (empty sequence).
Use Җ to calculate the bits corresponding to the current row, column and diagonal(s). Shift it by i and then or it onto taken.
Recursively call Ӂ to retrieve all solutions for the remaining cells, passing it the new taken and the decremented ix. This returns a sequence of incomplete strings; each string has ix characters (the grid filled in up to index ix).
Use ɱ (map) to go through the solutions thusly found and use ‼ to concatenate i to the end of each. Append a newline if index is a multiple of n, otherwise a space.

Generating the result

The main program calls Ӂ (the brute forcer) with n, index = n² (remember we fill the grid backwards) and taken = 0 (initially nothing is taken). If the result of this is an empty sequence (no solution found), output the empty string. Otherwise, output the first string in the sequence. Note that this means it will evaluate only the first element of the sequence, which is why the solver doesn’t continue until it has found all solutions.

Performance improvement

(For those who already read the old version of the explanation: the program no longer generates a sequence of sequences that needs to be separately turned into a string for output; it just generates a sequence of strings directly. I’ve edited the explanation accordingly. But that wasn’t the main improvement. Here it comes.)

On my machine, the compiled exe of the first version took pretty much exactly 1 hour to solve n = 7. This was not within the given time limit of 10 minutes, so I didn’t rest. (Well, actually, the reason I didn’t rest was because I had this idea on how to massively speed it up.)

The algorithm as described above stops its search and backtracks every time that it encounters a cell in which all the bits in the taken number are set, indicating that nothing can be put into this cell.

However, the algorithm will continue to futilely fill the grid up to the cell in which all those bits are set. It would be much faster if it could stop as soon as any yet-to-be-filled-in cell already has all the bits set, which already indicates that we can never solve the rest of the grid no matter what numbers we put in it. But how do you efficiently check whether any cell has its n bits set without going through all of them?

The trick starts by adding a single bit per cell to the taken number. Instead of what was shown above, it now looks like this:

LSB                               (example n=5)
 ↓
 10000 0 00000 0 00000 0 00000 0 10000 0
 00000 0 10000 0 00000 0 00000 0 10000 0
 00000 0 00000 0 10000 0 00000 0 10000 0
 00000 0 00000 0 00000 0 10000 0 10000 0
 10000 0 10000 0 10000 0 10000 0 10000 0
                                       ↑
                                      MSB

Instead of n³, there are now n²(n + 1) bits in this number. The function that populates the current row/column/diagonal has been changed accordingly (actually, completely rewritten to be honest). That function will still populate only n bits per cell though, so the extra bit we just added will always be 0.

Now, let’s say we are halfway through the calculation, we just placed a 1 in the middle cell, and the taken number looks something like this:

                 current
LSB              column           (example n=5)
 ↓                 ↓
 11111 0 10010 0 01101 0 11100 0 11101 0
 00011 0 11110 0 01101 0 11101 0 11100 0
 11111 0 11110 0[11101 0]11100 0 11100 0    ← current row
 11111 0 11111 0 11111 0 11111 0 11111 0
 11111 0 11111 0 11111 0 11111 0 11111 0
                                       ↑
                                      MSB

As you can see, the top-left cell (index 0) and the middle-left cell (index 10) are now impossible. How do we most efficiently determine this?

Consider a number in which the 0th bit of each cell is set, but only up to the current index. Such a number is easy to calculate using the familiar formula:

What would we get if we added these two numbers together?

LSB                                               LSB
 ↓                                                 ↓
 11111 0 10010 0 01101 0 11100 0 11101 0           10000 0 10000 0 10000 0 10000 0 10000 0        ╓───╖
 00011 0 11110 0 01101 0 11101 0 11100 0     ║     10000 0 10000 0 10000 0 10000 0 10000 0            ║
 11111 0 11110 0 11101 0 11100 0 11100 0  ═══╬═══  10000 0 10000 0 00000 0 00000 0 00000 0  ═════   ╓─╜
 11111 0 11111 0 11111 0 11111 0 11111 0     ║     00000 0 00000 0 00000 0 00000 0 00000 0  ═════   ╨
 11111 0 11111 0 11111 0 11111 0 11111 0           00000 0 00000 0 00000 0 00000 0 00000 0          o
                                       ↑                                                 ↑
                                      MSB                                               MSB

The result is:

             OMG
              ↓
        00000[1]01010 0 11101 0 00010 0 00011 0
        10011 0 00001 0 11101 0 00011 0 00010 0
═════   00000[1]00001 0 00011 0 11100 0 11100 0
═════   11111 0 11111 0 11111 0 11111 0 11111 0
        11111 0 11111 0 11111 0 11111 0 11111 0

As you can see, the addition overflows into the extra bit that we added, but only if all the bits for that cell are set! Therefore, all that’s left to do is to mask out those bits (same formula as above, but << n) and check if the result is 0:

00000[1]01010 0 11101 0 00010 0 00011 0    ╓╖    00000 1 00000 1 00000 1 00000 1 00000 1         ╓─╖ ╓───╖
10011 0 00001 0 11101 0 00011 0 00010 0   ╓╜╙╖   00000 1 00000 1 00000 1 00000 1 00000 1        ╓╜ ╙╖    ║
00000[1]00001 0 00011 0 11100 0 11100 0   ╙╥╥╜   00000 1 00000 1 00000 0 00000 0 00000 0  ═════ ║   ║  ╓─╜
11111 0 11111 0 11111 0 11111 0 11111 0   ╓╜╙╥╜  00000 0 00000 0 00000 0 00000 0 00000 0  ═════ ╙╖ ╓╜  ╨
11111 0 11111 0 11111 0 11111 0 11111 0   ╙──╨─  00000 0 00000 0 00000 0 00000 0 00000 0         ╙─╜   o

If it is not zero, the grid is impossible and we can stop.

Screenshot showing solution and running time for n = 4 to 7.


Can this number be written in (3^x) - 1 format? Challenge:

Create a program that accepts a positive integer and checks if it can be written in the form of (3^x)-1, where X is another positive integer.

If it can, output X

If it can't, output -1 or a falsy statement.

Example inputs/outputs

Input:

2

It can be written as (3^1) - 1, so we output x which is 1

Output:

1

Input:

26

26 can be written as (3^3) - 1, so we output x (3)

Output:

3

Input:

1024

1024 can't be written in the form of (3^x) - 1, so we output -1

Output:

-1

This is code-golf so least amount of bytes wins

Related OEIS: A024023

Mathematica, 21 16 bytes

-1&@@Log[3,#+1]&

Makes use of Mathematica's symbolic computation. If #+1 is a power of three then Log[3,#+1] will compute an integer result which is an atomic value. Otherwise we'll get Log[#+1]/Log[3] as is. Since this is not an atomic value, it's an expression which is always of the form head[val1,val2,...]. In this case it's actually something like Times[Power[Log[3], -1], Log[#+1]].

We distinguish between the two cases by applying another function to the result. What applying really does is that it replaces the head part of an expression. Since integer results are atomic, applying any function to them does nothing at all. In particular f @@ atom == atom.

However, in the other case, the head does get replaced. The function we're using is -1& which is a simple function that ignores its arguments and returns -1. So we get something -1&[Power[Log[3], -1], Log[#+1]] in non-integer cases, which evaluates directly to -1. Special casing via magic.


The Bridge and Torch Problem The inspiration for this code golf puzzle is the Bridge and Torch problem, in which d people at the start of a bridge must all cross it in the least amount of time.

The catch is that at most two people can cross at once, otherwise the bridge will crush under their weight, and the group only has access to one torch, which must be carried to cross the bridge.

Each person in the whole puzzle has a specified time that they take to walk across the bridge. If two people cross together, the pair goes as slow as the slowest person.

There is no set number of people that must cross the bridge; your solution MUST work for any value of d.

You needn't use standard input for this problem, but for the sake of explaining the problem, I will be using the following input and output format for the explanation. The first number, d, is the number of people at the start of the bridge. Then, the code will scan for d numbers, each representing the speed of a person.

The code output will be the LEAST amount of time required to cross everyone from the start of the bridge to the end of the bridge, while meeting the criteria explained earlier.

Here are some input cases and output cases and the explanation for the first input case. It is up to you to derive an algorithm from this information to solve the problem in the fewest bytes of code possible.

input

4
1 2 5 8

output

15

To reach this output, the people must cross in the following way.

A and B cross forward (2 minutes)
A returns (1 minute)
C and D cross forward (8 minutes)
B returns (2 minutes)
A and B cross forward (2 minutes)

Here's another test case to guide you along your way.

input

5
3 1 6 8 12

output

29

Rules:

Assume that the input will not be sorted, and you must do so on your own (if you need to)
The number of people in the puzzle is not fixed at 4 (N >= 1)
Every group and individual crossing must have a torch. There is only one torch.
Each group must consist of a maximum of only 2 people!
No, you may not jump off the bridge and swim to the other side. No other tricks like this ;).

Python 3, 100 99 bytes

a recursive solution

f=lambda s:s[0]+s[-1]+min(2*s[1],s[0]+s[-2])+f(s[:-2])if s.sort()or 3<len(s)else sum(s[len(s)==2:])

Thanks to @xnor for this paper

Thanks to @lirtosiast save 2 bytes,  @movatica save 1 bytes and to @gladed pointing at that my previous solution doesn't work

use the following trick to evaluate something in lambda function s.sort() or s  here we compute sort and return the result of the test s.sort()or len(s)>3

Ungolfed

def f(s):
    s.sort()                                   # sort input in place
    if len(s)>3:                               # loop until len(s) < 3
        a = s[0]+s[-1]+min(2*s[1],s[0]+s[-2])  # minimum time according to xnor paper
        return  a + f(s[:-2])                  # recursion on remaining people
    else:
        return sum(s[len(s)==2:])              # add last times when len(s) < 3

Results

>>> f([3, 1, 6, 8, 12])
29
>>> f([1, 2, 5, 8])
15
>>> f([5])
5
>>> f([1])
1
>>> f([1, 3, 4, 5])
14


Non-idempotent Python Write a few lines of Python code, X, that does not reference any global variables, such that

def method():
    X
    print(a)

method()

prints 1 but

def method():
    X
    X
    print(a)

method()

prints 2.

So, I hate to be a stickler, but it seems like vars and locals are actually global variables in Python:

def test_global_1():
    global vars, locals
    vars = lambda: 2
    locals = lambda: 3

def test_global_2():
    print(vars())
    print(locals())

test_global_1()
test_global_2()

Also, it looks like people would like to see objective winning criteria for puzzles like this. Code length doesn't really feel right here so perhaps we could make a system of brownie points for various novel features of the code? I'm not sure exactly what these could be but here's a start:

+1 for really truly no globals (no vars or locals)
+1 for being the first to post a particular technique
+1 for the shortest solution posted
+1 for a solution involving only a single Python statement
+1 for interesting "hacks" like joining at lexical non-boundaries
+1 for not using exceptions

And if you can think of more you could edit this question to add to the list.

Can this problem be solved without using exceptions and without using globals like vars and locals? I suspect it can, though I haven't figured out exactly how yet...

def method():
    if 'a' not in vars():a=0
    a+=1
    if 'a' not in vars():a=0
    a+=1
    print(a)

Initializes the variable a to 0 only if it's not already initialized in the variables table. Then, increments it.

More briefly (thanks to histocrat for len):

def method():
    a=len(vars())+1
    a=len(vars())+1
    print(a)

If the two copies of X could be on the same line, we could do

a=0;a+=1;a

which doubles to

a=0;a+=1;aa=0;a+=1;a

with the "sacrificial lamb" aa eating up the second variable assignment.


Bubble sorting in progress Create a function or program that takes two inputs:

A list of integers that shall be sorted (less than 20 elements)
A positive integer, N, saying how many comparisons you should take

The function shall stop, and output the resulting list of integers after N comparisons. If the list is fully sorted before N comparisons are made, then the sorted list should be outputted.

The Bubble sort algorithm is well known, and I guess most people know it. The following Pseudo-code and animation (both from the linked Wikipedia-article) should provide the necessary details:
procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat
     swapped = false
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

The animation below shows the progress:

An example (taken directly from the linked Wikipedia article) shows the steps when sorting the list: ( 5 1 4 2 8 ):
First Pass
1: ( 5 1 4 2 8 ) ->  ( 1 5 4 2 8 ) // Here, algorithm compares the first two elements,
                                   // and swaps since 5 > 1.
2: ( 1 5 4 2 8 ) ->  ( 1 4 5 2 8 ) // Swap since 5 > 4
3: ( 1 4 5 2 8 ) ->  ( 1 4 2 5 8 ) // Swap since 5 > 2
4: ( 1 4 2 5 8 ) ->  ( 1 4 2 5 8 ) // Now, since these elements are already in order
                                   // (8 > 5), algorithm does not swap them.

Second Pass
5: ( 1 4 2 5 8 ) ->  ( 1 4 2 5 8 )
6: ( 1 4 2 5 8 ) ->  ( 1 2 4 5 8 ) // Swap since 4 > 2
7: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
8: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )

Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass
9: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
10:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
11:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
12:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )

Test cases:
Format: Number of comparisons (N): List after N comparisons
Input list:
5  1  4  2  8
Test cases:
1: 1  5  4  2  8
2: 1  4  5  2  8
3: 1  4  2  5  8
4: 1  4  2  5  8
5: 1  4  2  5  8
6: 1  2  4  5  8
10: 1  2  4  5  8
14: 1  2  4  5  8

Input list:
0: 15  18  -6  18   9  -7  -1   7  19  19  -5  20  19   5  15  -5   3  18  14  19
Test cases:
1: 15  18  -6  18   9  -7  -1   7  19  19  -5  20  19   5  15  -5   3  18  14  19
21: -6  15  18   9  -7  -1   7  18  19  -5  19  19   5  15  -5   3  18  14  19  20
41: -6   9  -7  15  -1   7  18  18  -5  19  19   5  15  -5   3  18  14  19  19  20
60: -6  -7  -1   9   7  15  18  -5  18  19   5  15  -5   3  18  14  19  19  19  20
61: -6  -7  -1   7   9  15  18  -5  18  19   5  15  -5   3  18  14  19  19  19  20
81: -7  -6  -1   7   9  15  -5  18  18   5  15  -5   3  18  14  19  19  19  19  20
119: -7  -6  -1  -5   7   9  15   5  15  -5   3  18  14  18  18  19  19  19  19  20
120: -7  -6  -1  -5   7   9  15   5  15  -5   3  18  14  18  18  19  19  19  19  20
121: -7  -6  -1  -5   7   9   5  15  15  -5   3  18  14  18  18  19  19  19  19  20
122: -7  -6  -1  -5   7   9   5  15  15  -5   3  18  14  18  18  19  19  19  19  20
123: -7  -6  -1  -5   7   9   5  15  -5  15   3  18  14  18  18  19  19  19  19  20
201: -7  -6  -5  -1  -5   3   5   7   9  14  15  15  18  18  18  19  19  19  19  20
221: -7  -6  -5  -5  -1   3   5   7   9  14  15  15  18  18  18  19  19  19  19  20

Yes, built-in Bubble sort algorithms are permitted.
No, you can not assume only positive integers, or unique integers.
The sorting must be in the order described above. You can't start at the end of the list

JavaScript (ES6), 102 82 80 86 80 bytes

Bug fix and 1 byte saved thanks to @edc65

(a,m)=>eval("for(i=0;m;a[j=i-1]>(b=a[i])?a[a[i]=a[j],j]=b:0)1/a[++i]?m--:i=0;a")

Recursion may not be is definitely not is probably the best approach, but I'm sticking with a loop for now.

Try it out:

f=(a,m)=>eval("for(i=0;m;a[j=i-1]>(b=a[i])?a[a[i]=a[j],j]=b:0)1/a[++i]?m--:i=0;a")
Enter your numbers:

<input id=A rows=10 value="5 1 4 2 8">

Enter the number of steps:

<input type="number" min=0 id=B rows=10 value="1">

<button onclick="C.innerHTML=f((A.value.match(/-?\d+/g)||[]).map(Number),B.value)">Run</button>


Solving a Jigsaw Puzzle! I've just bought a new jigsaw puzzle but, as a programmer, I'm too lazy to do it by myself. So I've devised a way to encode the pieces, and now I need a way to solve the puzzle itself.
Challenge
A puzzle piece will have from 2 to 4 connecting corners, defined by a letter; and a color, defined by a number.
  a
B 1 c
  D

a 2 b
  C

3 A
b

The challenge is to build the puzzle from the pieces according to the next rules:

Two pieces may only be adjacent if they have a matching connection in the corner where they are adjacent. If a piece doesn't have a connection in one of the sides, that side is a corner and can't be connected to another piece.

Lowercase letters are considered indents and uppercase letters are considered outdents. An uppercase letter connects with its lowercase pair.

The color of 4-adjacent pieces will differ at most by 1.

Every piece can and has to be used exactly once.

Input
Your program will receive a randomized list of the pieces, separated with newlines, as seen in the examples. The input pieces are in the right direction: you don't need to rotate them (there is a bonus for inputs with rotated pieces, see below).
Output
Your program should output a solution to the puzzle, with columns separated by blank space (space or tab are okay) and rows by newlines. It might not be unique, but only one possible solution is required.
1 2 3 4 3 4 5 4
1 1 2 3 4 4 4 5
2 1 1 2 3 4 5 6
3 2 2 3 4 5 6 7
2 3 3 4 5 6 7 8
3 4 4 5 6 7 8 9
3 4 5 6 7 8 9 10

Scoring
The shortest answer in bytes wins.
Bonus
The generator script provides options to randomize the rotation of the pieces, but since it may become more complex, a 50% bonus is awarded to whoever implements it (that is, your-byte-count * 0.5).
For that case, assume all the tiles in the input will have a randomized rotation, except the first one, which will have the rotation of the original grid (so as to avoid having at least 4 different solutions).
Test Cases
Test cases can be obtained using the following ruby scripts:
https://gist.github.com/rcrmn/2ba23845d65649c82ca8
The first one generates the solution grid. The second one generates the puzzle pieces from it. Note that they have optional arguments, described in each ruby file.
Following is an example. It's here because I made it by hand before writing the generator and I got attached to it:
http://pastebin.com/PA9wZHma
This test case should output:
1 2 3 4
2 3 4 5
3 4 5 6

As usual, common loopholes are not permitted.
Good luck!

Ruby, 1220

Wow that was something... I didn't think it would take THAT much to make this, but hey, only way to learn was try it. It's clear now why there weren't any answers to the question...

Well, I'm sure this is golfable, but It's been a whole job only to make it. Following is golfed code and then ungolfed with some explanations:

e=[[]]
while(a=gets)
if(a=a.chomp)==""
e.push []
else
e.last.push a.chomp
end
end
e.keep_if{|p|p!=[]}
e.map!{|p|m={}
t=p[0].strip
if t.length==1
m[:t]=t
l=p[1].split" "
b=p[2]
else
m[:t]=nil
l=t.split" "
b=p[1]
end
x=l[0]=~/\d/
m.merge!({l: !x ? l[0]:nil,v:(x ? l[0]:l[1]).to_i,r:x ? l[1]:l[2]})
m[:b]=b.nil? ? nil:b.strip
m}
w=e.select{|p|p[:t].nil?}.length
h=e.length/w
def c(j,p,l)
x=l[0]
y=l[1]
(x==0&&p[:l].nil?||x!=0&&(j[x-1][y].nil?||j[x-1][y][:r].swapcase==p[:l]&&(j[x-1][y][:v]-p[:v]).abs<2))&&(x==j.length-1&&p[:r].nil?||x!=j.length-1&&(j[x+1][y].nil?||j[x+1][y][:l].swapcase==p[:r]&&(j[x+1][y][:v]-p[:v]).abs<2))&&(y==0&&p[:t].nil?||y!=0&&(j[x][y-1].nil?||j[x][y-1][:b].swapcase==p[:t]&&(j[x][y-1][:v]-p[:v]).abs<2))&&(y==j[0].length-1&&p[:b].nil?||y!=j[0].length-1&&(j[x][y+1].nil?||j[x][y+1][:t].swapcase==p[:b]&&(j[x][y+1][:v]-p[:v]).abs<2))
end
def d(j,q,l)
f=[false,[]]
q.each_index{|i|p=q[i]
if c j,p,l
r=q.dup
r.delete_at i
j2=j.dup
j2[l[0]][l[1]] = p
if r.length==0
f = [true,j2]
break
else
n=l[0]+1
l2=[n%j.length, l[1]+n/j.length]
f = d(j2,r,l2)
break if f[0]
end
end}
f
end
j=[]
w.times{j.push [];h.times{j.last.push nil}}
s=d(j,e,[0,0])
h.times{|y|w.times{|x|print s[1][x][y][:v].to_s+" "}
puts''}

Ungolfed:

pieces=[[]]
while (a=gets) # Read the input and separate by pieces when finding an empty line
  if (a=a.chomp)==""
    pieces.push []
  else
    pieces.last.push a.chomp
  end
end
pieces.keep_if{|p|p!=[]} # Remove possible empty pieces
pieces.map!{|p| # Parse each piece
  m={}
  t=p[0].strip
  if t.length==1
    m[:t]=t
    l=p[1].split" "
    b=p[2]
  else
    m[:t]=nil
    l=t.split" "
    b=p[1]
  end
  x=l[0]=~/\d/
  m.merge!({l: !x ? l[0]:nil,v:(x ? l[0]:l[1]).to_i,r:x ? l[1]:l[2]})
  m[:b]=b.nil? ? nil:b.strip
  m
}
w=pieces.select{|p|p[:t].nil?}.length
h=pieces.length/w

def fits(j,p,l) # This function determines if a piece fits in an empty spot
  (l[0]==0&&p[:l].nil? || l[0]!=0 && (j[l[0]-1][l[1]].nil? || j[l[0]-1][l[1]][:r].swapcase==p[:l] && (j[l[0]-1][l[1]][:v]-p[:v]).abs<2)) &&
    (l[0]==j.length-1&&p[:r].nil? || l[0]!=j.length-1 && (j[l[0]+1][l[1]].nil? || j[l[0]+1][l[1]][:l].swapcase==p[:r] && (j[l[0]+1][l[1]][:v]-p[:v]).abs<2)) &&
    (l[1]==0&&p[:t].nil? || l[1]!=0 && (j[l[0]][l[1]-1].nil? || j[l[0]][l[1]-1][:b].swapcase==p[:t] && (j[l[0]][l[1]-1][:v]-p[:v]).abs<2)) &&
    (l[1]==j[0].length-1&&p[:b].nil? || l[1]!=j[0].length-1 && (j[l[0]][l[1]+1].nil? || j[l[0]][l[1]+1][:t].swapcase==p[:b] && (j[l[0]][l[1]+1][:v]-p[:v]).abs<2))
end

def rec(j,pl,l) # Recursive function to try every piece at every position it can fit
  found = [false,[]]
  pl.each_index{|i|
    p=pl[i]
    if fits(j,p,l) # Try the piece in the spot
      pl2=pl.dup
      pl2.delete_at i
      j2=j.dup
      j2[l[0]][l[1]] = p
      if pl2.length==0 # If we have spent all the pieces, then we have a complete puzzle
        found = [true,j2]
        break
      else             # Keep recurring until we use up all the pieces
        n=l[0]+1
        l2=[n%j.length, l[1]+n/j.length]
        found = rec(j2,pl2,l2)
        break if found[0]
      end
    end
  }
  found
end

j=[]
w.times { j.push []; h.times { j.last.push nil }}
solved = rec(j, pieces, [0,0])
h.times{|y|
  w.times{|x|
    print solved[1][x][y][:v].to_s + " "
  }
  puts ''
}


Who's that pokemon (based on its etymology)? As we all know, most Pokemon are created by combining some English (or Japanese) words; these words are the Pokemon's "etymology." For example, "charmander" is "char" and "salamander" put together.

Your task is, given a Pokemon's etymology and number, output the original Pokemon name. A short answer will be able to compress the 890 Pokemon into much fewer characters by exploiting the fact that the etymologies and the names themselves use mostly the same characters.

Input: The Pokemon number, and an array/list of etymologies, all lowercase

Output: The Pokemon's name, also lowercase

The full list of test cases can be found here: https://pastebin.com/B3rRdiPn. Each line is a test case with the format:

<pokemon number>;<comma separated etymology list>;<pokemon name>

This list was created from https://pokemondb.net/etymology by running the following code:

let collectedRows = [];
let rows = $(".data-table tr").slice(1)
let isOddPrev = false;
// Replacements due to typos, remove 'palindrome' since girafig doesn't come from the word 'palindrome', 'palindrome' is just a descriptor
var repl = {"anacondo": "anaconda", "armadilo": "armadillo", "[palindrome]": ""}
rows.each((_, row) => {
  let isOdd = row.classList.contains("odd");
  let etym = $(row).find(".cell-etym-word").text().toLowerCase();
  if (repl.hasOwnProperty(etym)) etym = repl[etym];
  if (isOdd !== isOddPrev) {
    collectedRows.push({name: $(row).find(".cell-name").text().toLowerCase(), etymology: [etym], num: parseInt($(row).find(".cell-num").text().replace(/\s/g, ''), 10)});
  } else {
    collectedRows[collectedRows.length - 1].etymology.push(etym);
  }

  isOddPrev = isOdd;
});

// Output:
collectedRows.map(pokemon => pokemon.num + ";" + pokemon.etymology.join(",").replace(/\,$/, '') + ";" + pokemon.name).join("\n")

Examples:

The full list of test cases can be found at the pastebin link, but here are some example inputs and outputs:

1, ['bulb', '-saur'] --> 'bulbasaur'
122, ['mr.', 'mime artist'] --> 'mr. mime'
29, ['nidoru' ,'rhino', '♀'] --> 'nidoran♀'
16, ['pigeon'] --> 'pidgey'
17, ['pigeon'] --> 'pidgeotto'
23, ['snake'] --> 'ekans'

Note that due to 'nidoran♀' and its family, you need to be able to handle input/output in UTF-8.

The winner is the entry with the highest accuracy, with ties broken by code length. In practice, this means that the challenge is code-golf -- you need to get 100% accuracy to be a competitive entry -- since you can trivially create a lookup table, but feel free to post a sub-100% accuracy answer if you think it does something creative (someone else might extend it to handle the edge cases).

If you wish, you may also include a data file, and the number of bytes of that file is added to your byte count. This is just if you want to keep your code and data separate.

JavaScript (Node.js 11.7+), 100%, 2094 bytes
Same as below, with the data file compressed with Brotli instead of zlib.
n=>a=>(require('zlib').brotliDecompressSync(require('fs').readFileSync('a'))+'').split`/`[n-1].replace(/\d.\d?/g,([i,p,l])=>a[i].substr(p,++l||9))

Try it online! (not working on TIO)

JavaScript (Node.js), 100%,  2176 2158  2151 bytes
This is similar to the self-contained version below but uses an external data file of 2010 bytes named 'a'. The TIO link generates a local copy of this file.
The final size was computed according to the rules for scoring multiple files:
$$2010+140+1=2151$$
n=>a=>(require('zlib').inflateRawSync(require('fs').readFileSync('a'))+'').split`/`[n-1].replace(/\d.\d?/g,([i,p,l])=>a[i].substr(p,++l||9))

Try it online!

JavaScript (Node.js), 100%,  2701 ... 2359  2356 bytes
Takes input as (id)([etymology0, etymology1, ...]).
The source contains many unprintable characters.
n=>g=(a,i=2,s="aZOEDQ]^4+24><e_<ZZ)aku[XdFyXdttoXdt|63a%}5ks/arbok_[__S♀E2a_S♂E_]]Sx_Sy`SytuffS[K~_SB]NO[h~[]?4PS@NB;2ZW)H~~pBR_]3!AA[r~?6G/@W@GA;5'dOOXel?3U~rXk~d,/!Z%~/@82arXix_S)ZD_~?3=I?3=CO;ak*@*@&tuV2)offHUXy`Xy`WseyWelaSs18/Ta*R[WyuWmie4~r/jyUS(~r[WosWkZXarados/lapras~eveeG_NXrT/omy/om(~~ps}5_XT3`[]*i&te[~P2Z[2efD/cyF(4]Q%NB4r>KW_/leledikXi([0Tu_$~f0,`Ye`Ye`/n/x`MXZ!ORR+22T3`oed[]]/ai!/2HV2^3~J_[_]W@+vXP]SarigWH2K3P+ce*&x/qwF`YzH2>Y(QW_M5]N+KW@]$NN`2K4XrT42OBR*@~um[M[y[2u~cZeWYSXgiho-ohWbiRWy,>E2^4C;3NBN^4%euFVM<17M]2|6XV4N3	SryD]Q/TtsJG+~8VA/U4,VE[ME]]2dEWH~]Q~[NOXVRRN<CQ5~leWn[Jse~lJQYvIQail`3aK]Z$NQ]B/3T3YnZ2e]2[/z=IO	],/corphH_[M3]Y2I?4ldo]2/4I/P4`)ec,XZ}7RMNSyut[KR]]2n/@eI]]{64/luv`XIQ{VC/P30TR__]_YiZYiZ)yogre_*zjir01Ss]K]_MO_KSy]XdZ2f|VCL6ZL6ZWx&oMO�NAA/buVZ]/H4Z{TnGXizC~zC?7{6{VW!Q[yO*iISkZ	M?2Uy_>N]Sjr.]]A/gZ@6$[E/=olu/luca=o~sE222kFuP2%_NA[N]MWa0b4[S&yXyV]SivZ]_]3__+Yo`XrT-zBB__/r0Im/uV$5/az`Ylgpalkia]3_QiphV~phyRYyminOni$[>WgMO/oshaw!*{TW=S<pDGQK###XnV2?5r222$~lYez,>[5aXggen3aXT2`	__�2Wr/guFr`3rDAWhawkMWlI]%>DJeeS4|VZ2Y0UIK5�)=ko=kL4C^3;niBM>~QEO|72ri18/tiFoPYF`WenWH3sXZ_YuaYoZYccV/ccV>QSt18DME2,]~Jite^3^3]aws`0UlH)FT3ZR/fooUYs{6�/alo0U0P&k^5GGLLL4ZXVkC3kkC222lgyem/beheeyem[D<Z~wYxHXxo24MQQ2rk~fooXZ3iTQOQRJlHRK^IWH3]/doQ?4F23]ENSkZWzZASZ$4am~kVm~ormM}53aR}53B�GRNK2ieD]Dby~sby^5AG<`RD[O];M3sQR+++OR]ENe<V&xNMK4XI^4kFVeMerQE>OBY082a?50aYv`[5X0TneRKYg`*LkiEMSa17�	M/xZ3eas/Z3lt25/zy`Yncie~aA/VRKW(<Z~pC3}5Xk2k_^3/yC3^52?7Wj(Xk(]R8Yc0PGO321_{T4iO[[|5OO3H/fo`ONW23RR~ul/!01_/H5072RaWey]D]GYos`/py=17@Vu~: `_D?2FIQ~de`Wkyu]K/d`4T-o-oL4-o3o~ V4iSg{UYg(]G]<V/xkH3eeaXrUNXcT2zC$[[_a=ka[7nYaZ	Qy/U5`_OK{7{6kwZB{6GG_lerO&t{VWW=/dF`Q;2VXIRFolQnRGRDWk{P07[2%>SskVB3<aSanremZ&@1]3~m`SgC/pZ2V]3%5'd~ riI~rig17K|Vmie/fF,Ym_RisP2eJT2%~f,A~zZWozZ~vZWovZAXVZQ/zaciU/za0UzTJtus~/}W1|Y1{S1`10_}0^J1]}1[|0Z11Y~3X~2W~4V12U0!03S~5R}2Q}3P04O|1N{1M|2L)01K|3J~6I13H05G{0FU2E{2D}4C14B{3A^1@20?/`>{4=0V<~7;YP,15+[4*[3)/k(a`&~i%|4$X`#/P3`_!2Ti`J`_3U3~eYk{5_4/T4~ `Z;20006/wa/09/s^2�}6_2	][16na/eanur~tWi")=>i<127?g(a,i+1,/[\r\n "'\--:\\a-z]/.test(c=Buffer([i]))?s:(l=s.split(c)).join(l.pop())):s.split`/`[n-1].replace(/\d.\d?/g,([i,p,l])=>a[i].substr('0x'+p,l||9))

Try it online!
How?
Each name is encoded as a sequence of sub-strings from the etymology words, with some possible hard-coded characters in between.
Example:
For the first name, we are given:
n = 1, a = ['bulb', '-saur']

The name bulbasaur is first encoded as 004a114, which is interpreted as:
'004' -> a[0].substr(0, 4) -> 'bulb'
'a'   -> hard-coded character 'a'
'114' -> a[1].substr(1, 4) -> 'saur'

But the length of the sub-string is omitted whenever this is possible without resulting in any ambiguity. When the length is omitted, the decoder assumes that the word must be read to its end.
Both lengths can be omitted in this case, so the final encoding is:
00a11

All the 890 encoding sequences are concatenated together, using / as a separator. This results in a string with a lot of repeated patterns which can be efficiently crushed:
00a11/00211/00412/00314/00313/00311/00514/00210324/00414/006e/00310/.../za001z03/005tus


Count from 1 to 100... in Roman Numerals Write a program that count from 1 to 100 in Roman Numerals and print these numbers by standard output. Each one of the numbers must be separated by spaces.

You cannot use any built in function to transform to roman numerals nor external application or library to do so.

The desired result is

I II III IV V VI VII VIII IX X XI XII XIII XIV XV XVI XVII XVIII XIX XX XXI XXII XXIII XXIV XXV XXVI XXVII XXVIII XXIX XXX XXXI XXXII XXXIII XXXIV XXXV XXXVI XXXVII XXXVIII XXXIX XL XLI XLII XLIII XLIV XLV XLVI XLVII XLVIII XLIX L LI LII LIII LIV LV LVI LVII LVIII LIX LX LXI LXII LXIII LXIV LXV LXVI LXVII LXVIII LXIX LXX LXXI LXXII LXXIII LXXIV LXXV LXXVI LXXVII LXXVIII LXXIX LXXX LXXXI LXXXII LXXXIII LXXXIV LXXXV LXXXVI LXXXVII LXXXVIII LXXXIX XC XCI XCII XCIII XCIV XCV XCVI XCVII XCVIII XCIX C

As it is a code golf challenge, shortest code wins.

Perl 69 bytes

s;.;y/XVI60-9/CLXVIX/dfor$a[$_].="32e$&"%72726;gefor 1..100;print"@a"

Works by way of magic formula. The expression "32e$&"%72726 transforms each digit in the following manner:
0⇒32, 1⇒320, 2⇒3200, 3⇒32000, 4⇒29096, 5⇒56, 6⇒560, 7⇒5600, 8⇒56000, 9⇒50918

After applying the translation y/016/IXV/, we have this instead:
0⇒32, 1⇒32I, 2⇒32II, 3⇒32III, 4⇒29I9V, 5⇒5V, 6⇒5VI, 7⇒5VII, 8⇒5VIII, 9⇒5I9X8

The rest of the digits (2-57-9) are removed. Note that this could be improved by one byte by using a formula which translates 012 instead of 016, simplifying /XVI60-9/ to /XVI0-9/. I wasn't able to find one, but maybe you'll have better luck.

Once one digit has been transformed in this manner, the process repeats for the next digit, appending the result, and translating the previous XVIs to CLX at the same time the translation for the new digit occurs.

Update
Exhaustive search didn't reveal anything shorter. I did, however, find an alternative 69 byte solution:

s;.;y/XVI0-9/CLXIXV/dfor$a[$_].="57e$&"%474976;gefor 1..100;print"@a"

This one uses a 0-2 substitution for IXV, but has a modulo that's one digit longer.

Update: 66 65 bytes

This version is notably different, so I should probably say a few words about it. The formula it uses is actually one byte longer!

Unable to shorten the formula any more than it is, I decided to golf down what I had. It wasn't long until I remembered my old friend $\. When a print statment is issued, $\ is automatically appended to the end of the output. I was able to get rid of the awkward $a[$_] construction for a two byte improvement:

s;.;y/XVI60-9/CLXVIX/dfor$\.="32e$&"%72726;ge,$\=!print$"for 1..100

Much better, but that $\=!print$" still looked a bit verbose. I then remembered an alternative, equal length formula I had found which didn't contain the number 3 in any of its digit transforms. So, it should be possible to use $\=2+print instead, and substitute the resulting 3 with a space:

s;.;y/XVI0-9/CLXIIX V/dfor$\.="8e$&"%61535;ge,$\=2+print for 1..100

Also 67 bytes, due to the necessary whitespace between print and for.

  Edit: This can be improved by one byte, by moving the print to the front:

$\=2+print!s;.;y/XVI0-9/CLXIIX V/dfor$\.="8e$&"%61535;gefor 1..100

  Because the substitution needs to evaluate completely before the print, the assignment to $\ will still occur last. Removing the whitespace between ge and for will issue a deprecation warning, but is otherwise valid.

But, if there were a formula which didn't use a 1 anywhere, $\=2+print becomes $\=print for another two bytes worth of savings. Even if it were one byte longer, it'd still be an improvement.

As it turns out, such a formula does exist, but it is one byte longer than the original, resulting in a final score of 65 bytes:

$\=print!s;.;y/XVI60-9/CLXXI V/dfor$\.="37e$&"%97366;gefor 1..100

Methodology

The question was asked how one might go about finding such a formula. In general, finding a magic formula to generalize any set of data is matter of probability. That is, you want to choose a form which is as likely as possible to produce something similar to the desired result.

Examing the first few roman numerals:

0:
1: I
2: II
3: III
4: IV
5: V
6: VI
7: VII
8: VIII
9: IX

there is some regularity to be seen. Specifically, from 0-3 and then again from 5-8, each successive term increases in length by one numeral. If we wanted to create a mapping from digits to numerals, we would want to have an expression that also increases in length by one digit for each successive term. A logical choice is k • 10d where d is the corresponding digit, and k is any integer constant.

This works for 0-3, but 4 needs to break the pattern. What we can do here is tack on a modulo:
k • 10d % m, where m is somewhere between k • 103 and k • 104. This will leave the range 0-3 untouched, and modify 4 such that it won't contain four Is. If we additionally constrain our search algorithm such that the modular residue of 5, let's call it j, is less than m / 1000, this will ensure that we also have regularity from 5-8 as well. The result is something like this:

0: k
1: k0
2: k00
3: k000
4: ????
5: j
6: j0
7: j00
8: j000
9: ????

As you can see, if we replace 0 with I, 0-3 and 5-8 are all guaranteed to be mapped correctly! The values for 4 and 9 need to be brute forced though. Specifically, 4 needs to contain one 0 and one j (in that order), and 9 needs to contain one 0, followed by one other digit that doesn't appear anywhere else. Certainly, there are a number of other formulae, which by some fluke of a coincidence might produce the desired result. Some of them may even be shorter. But I don't think there are any which are as likely to succeed as this one.

I also experimented with multiple replacements for I and/or V with some success. But alas, nothing shorter than what I already had. Here is a list of the shortest solutions I found (the number of solutions 1-2 bytes heavier are too many to list):

y/XVI60-9/CLXVIX/dfor$\.="32e$&"%72726
y/XVI0-9/CLXIXV/dfor$\.="57e$&"%474976
y/XVI0-9/CLXIVXI/dfor$\.="49e$&"%87971

y/XVI0-9/CLXIIXIV/dfor$\.="7e$&"%10606  #
y/XVI0-9/CLXIIXIV/dfor$\.="7e$&"%15909  # These are all essentially the same
y/XVI0-9/CLXIIXIV/dfor$\.="7e$&"%31818  #

y/XVI0-9/CLXIIX V/dfor$\.="8e$&"%61535  # Doesn't contain 3 anywhere

y/XVI60-9/CLXXI V/dfor$\.="37e$&"%97366 # Doesn't contain 1 anywhere


Tell me when the next post is... WebSockets! Background
I was working on a StackOverflow helper program (that sends me notifications) when I noticed something rather interesting in StackOverflow's Network tab:

StackOverflow uses WebSockets (not too surprising, but good to know)!  For this challenge, we will be conquering StackOverflow's web socket server.
This particular method could be transferred over to other domains related to StackExchange, but StackOverflow is very popular and a good example.  Feel free to lookup tags for other domains on StackExchange (feel free to connect to those instead, although I doubt it would reduce byte count since StackOverflow has id 1).
StackOverflow's Unofficial WebSocket API
There are two separate WebSocket servers you could use:

The secure, wss://qa.sockets.stackexchange.com/
Or the insecure, ws://qa.sockets.stackexchange.com/

Since we are code golfing and we aren't going to be sending any not-already-public-information, I suspect people will lean more toward the insecure option.
Next, in order to subscribe to our favorite tag, we need to send the following to the WebSocket to 'subscribe' to the tag's feed.
1-questions-newest-tag-javascript

You can replace javascript with any tag we're interested in.
The server will occasional send heartbeat requests.  You must reply with hb (so you can keep the connection alive).
A heartbeat requests looks as follows:
 {"action":"hb","data":"hb"}`

Here's a basic JavaScript-based socket (it may take a several minutes for there to be a new post, depending on time of day).  I used the most popular tag JavaScript to test with, but if you know of a more popular tag, go ahead and leave a comment.
Example:

var exampleSocket = new WebSocket("wss://qa.sockets.stackexchange.com/");
exampleSocket.onopen = function (event) {
  exampleSocket.send("1-questions-newest-tag-javascript");
};
exampleSocket.onmessage = function (event) {
  if (JSON.parse(event.data).data === "hb") {
    exampleSocket.send("hb")
  }
  console.log(event.data)
};

Specifications
Input: Any tag the user wants to receive updates about.
Output: Should be the first question (from when you connected to the WebSocket) and all consecutive available for said tag on StackOverflow.
Rules:

You must use WebSockets. Or, at least connect to sockets.stackexchange.com (including, ws://qa.sockets.stackexchange.com) and use it to receive updates for the inputted tag.  If you can find a better way of doing it (like not using the 1-questions-newest-tag-<tag> but still receive updates fo the inputted tag) by all means.  Or if you can write your own WebSocket equivalent in less bytes, even cooler.
Least number of bytes wins!

Language Compatibility
External libraries are encouraged. Many programming languages have a compatible library.

Clojure with gniazdo, 126, 204, 203 bytes
+78 bytes to handle reacting to heartbeat messages
-1 byte by changing from indexing the string converted to a vector, to just using nth. I was expecting more of a gain from that :/

(use '[gniazdo.core])(fn[t](let[a(atom 0)s #(send-msg @a %)o(connect"ws://qa.sockets.stackexchange.com":on-receive #(if(=((vec %)11)\h)(s"hb")(println %)))](reset! a o)(s(str"1-questions-newest-tag-"t))))

An anonymous function that takes a string tag, and prints the raw JSON results as they're received, while responding to heartbeats.
To test if the received message is a heartbeat, I'm testing if the 12th character of the response is the character h. After looking over this page, it seems impossible for h to be the 12th character without the response being a heartbeat. If this isn't the case, I can try to figure out a workaround.
(ns bits.golf.web-sock
  (:require [gniazdo.core :as g]))

(defn new-tag-posts [^String tag]
  (let [; A mutable state to hold the sock.
        ; Necessary since the sock's callback requires a reference to the
        ;  sock itself
        sock-a (atom nil)

        ; Shortcut function to save bytes
        send #(g/send-msg @sock-a %)

        handler #(if (= (nth % 11) \h) ; If the 12th character (at index 11) is 'h'
                   (send "hb") ; respond to the heartbeat
                   (println %)) ; else print the JSON

        sock (g/connect "ws://qa.sockets.stackexchange.com"
                        :on-receive handler)]

    ; Set the mutable state to the created socket
    (reset! sock-a sock)

    ; Subscribe to the given tag
    (send (str "1-questions-newest-tag-" tag))))


Determine which value represents which direction in a path Important edit: Earlier, there was an incorrect value in Example 1.  It has been fixed.

You are given a two-dimensional array in which each cell contains one of four values.

Examples:

1 2 2 2 2 1        @ . .        X X V
1 3 1 4 1 4        e . @        I C V
2 3 1 3 4 2        H H @        X I V
1 4 4 2 1 3                     V C C
2 2 2 3 2 3                     X X X

The four values represent directional arrows (up, down, left, and right), although you don't know which value represents which direction.

The directional arrows form an unbroken path that includes every cell in the array, although you don't know where the start or end points are.

Write some code that determines which direction each of the four values represents and where the start and end points are.

An acceptable return value for an array that contains the values A, B, C, and D would be something like:

{ up: A, down: C, left: D, right: B, start: [2, 0], end: [4, 2] }

Because you can traverse the path both ways (from start to end and from end to start), there will always be more than one correct solution, and there might be more than two.  Assume that the inputs you receive (as in the above examples) always have at least one correct solution.  In cases where there is more than one correct solution, returning just one of the correct solutions is sufficient.

Shortest code wins.  I'll pick the winner after 7 days or 24 hours without a new submission, whichever comes first.

I'm including solutions to the examples above, but I'd encourage you to only check them once you've written your code:

One:

   { up: 3, down: 1, left: 4, right: 2, start: [0,0], end: [2,5] }

Two:

   { up: '@', down: 'e', left: '.', right: 'H', start: [1,1], end: [0,0] }

Three:

   { up: 'I', down: 'V', left: 'C', right: 'X', start: [0,2], end: [4,2] }

C#

EDIT: Fixed a division and formatting. And added the helper class.

This is the golfed code, 807 chars

class M{public int c,x,y,u;}
void G(string[] z){
M K;int[]x={0,0,-1,1},y={-1,1,0,0},I={0,0,0,0};
string[]T={"Up","Down","Left","Right"};
int X,Y,R,n=0,H=z.Length,W=z[0].Length;W-=W/2;var D= string.Join(" ", z).Where(c=>c!=' ').Select(c=>new M(){c=c,x=n%W,y=n++/W}).ToList();n=0;var S=D.GroupBy(k=>k.c).ToDictionary(k=>k.Key,k =>n++);
for(;I[0]<4;I[0]++)for(I[1]=0;I[1]<4;I[1]++)for(I[2]=0;I[2]<4;I[2]++)for(I[3]=0;I[3]<4;I[3]++){
if ((1<<I[0]|1<<I[1]|1<<I[2]|1<<I[3])!=15)continue;
foreach (var Q in D){D.ForEach(p=>p.u=-1);R=1;K=Q;j:if((X=K.x+x[n=I[S[K.c]]])>=0&&X<W&&(Y=K.y+y[n])>=0&&Y<H&&(K=D[X+Y*W]).u<0){
K.u=1;if(++R==D.Count){Console.WriteLine("{4} Start({0}:{1}) End({2}:{3})",Q.x,Q.y,K.x,K.y,string.Join(", ",S.Select(k=>string.Format("{1}: '{0}'",(char)k.Key,T[I[k.Value]])).ToArray()));return;}goto j;}}}
}

Results for the three test cases:

  Down: '1', Right: '2', Up: '3', Left: '4' Start(0:0) End(5:2)
  Up: '@', Left: '.', Down: 'e', Right: 'H' Start(1:1) End(0:0)
  Right: 'X', Down: 'V', Up: 'I', Left: 'C' Start(0:2) End(2:4)

This is the raw code without "golf", almost 4,000 characters:

class Program
{
    static string[] input1 =  { "1 2 2 2 2 1",
               "1 3 4 4 1 4",
               "2 3 1 3 4 2",
               "1 4 4 2 1 3",
               "2 2 2 3 2 3"};

    static string[] input2 =  { "@ . .",
                                "e . @",
                                "H H @",
               };

    static string[] input3 =  { "0 0 1",
                                "0 0 1",
                                "3 2 2",
               };

    static void Main(string[] args)
    {
        Resolve(input1);
        Resolve(input2);
        Resolve(input3);
        Console.ReadLine();
    }

    class N { public int c; public int x, y, i, u; }

    static void Resolve(string[] input)
    {
        int[] ox = { -1, 1, 0, 0 }, oy = { 0, 0, -1, 1 }, I = { 0, 0, 0, 0 };
        string[] TXT = { "Left", "Right", "Up", "Down" };
        int X, Y, R, n = 0, H = input.Length, W = input[0].Length;
        W -= W / 2;
        N K = null;
        var data = string.Join(" ", input).Where(c => c != ' ').Select(c => new N() { c = c, x = (n % W), y = (n / W), i = n++, u = -1 }).ToList();
        n = 0;
       var S = data.GroupBy(k => k.c).ToDictionary(k => k.Key, k => n++);

        for (; I[0] < 4; I[0]++)
            for (I[1] = 0; I[1] < 4; I[1]++)
                for (I[2] = 0; I[2] < 4; I[2]++)
                    for (I[3] = 0; I[3] < 4; I[3]++)
                    {
                        if (((1 << I[0]) | (1 << I[1]) | (1 << I[2]) | (1 << I[3])) != 15) continue;
                        foreach(var Q in data)
                        {
                            data.ForEach(p => p.u = -1);
                            R = 0;
                            K = Q;
                            while (K != null)
                            {
                                n = I[S[K.c]];
                                X = K.x + ox[n];
                                Y = K.y + oy[n];
                                if (X >= 0 && X < W && Y >= 0 && Y < H)
                                {
                                    n = X + Y * W;
                                    if (data[n].u < 0)
                                    {
                                         data[n].u = K.i;
                                         K = data[n];
                                        R++;
                                        if (R == data.Count - 1)
                                        {
                                            Console.WriteLine();
                                            Console.WriteLine("Start({0}:{1}) End({2}:{3})", Q.x, Q.y, K.x, K.y);
                                            Console.WriteLine(string.Join(", ", S.Select(k => string.Format("'{0}': {1}", (char)k.Key, TXT[I[k.Value]])).ToArray()));
                                            Action<N> Write = null;
                                            Write = (k) =>
                                             {
                                                 if (k.u != -1)
                                                 {
                                                     Write(data[k.u]);
                                                 }
                                                 Console.Write(string.Format("({0}:{1}){2}", k.x, k.y, k == K ? "\n" : " => "));
                                             };

                                            Write(K);
                                            return;
                                        }
                                        continue;
                                    }
                                }
                                K = null;
                            }
                        }
                    }
        Console.WriteLine("Solution not found");
    }
 }
}

These are the results for the three examples:

  Solution not found

  Start(1:1) End(0:0) '@': Up, '.': Left, 'e': Down, 'H': Right

  (1:1) => (0:1) => (0:2) => (1:2) => (2:2) => (2:1) => (2:0) => (1:0) => (0:0)

  Start(0:0) End(1:1) '0': Right, '1': Down, '3': Up, '2': Left

  (0:0) => (1:0) => (2:0) => (2:1) => (2:2) => (1:2) => (0:2) => (0:1) => (1:1)


90° Self-Rotating Program Introduction
Write a complete program that rotates a rectangular block of ASCII characters 90 degrees clockwise. When the program itself is rotated 90 degrees clockwise, it rotates a block of ASCII characters 90 counterclockwise.
Rules

You many not use built-ins that rotate or transpose matrices. For example, in MATLAB/Octave rot90 and the transpose operator ' are not allowed.
You must write a complete program that uses STDIN and STDOUT or the closest equivalent.
Your program must be rectangular and assume the input is also rectangular.
The input and output are a newline separated strings and will not have trailing newlines.

When run with its source code as input, your program must rotate itself 90 degrees clockwise. The output must be a second program in the same language that rotates its input 90 degrees counterclockwise. When the rotated program is given its source code as input, it should output the source code of the original program.
Note: Both programs must work for any input, not just their own source code, so a one character quine is not allowed.
Example
Say the following is a valid program that rotates its input 90 degrees in a hypothetical language ExampleLang.
^f a2% 3
lk (^_^&
       v
D8 $4  /

When run with itself as input, it outputs another valid program that rotates its input counterclockwise:
D l^
8 kf

$ (a
4 ^2
  _%
  ^
/v&3

This second program, when given to itself as input, outputs the original program. Note that the blank line should have four spaces and there is a trailing space on the second to last line that cannot be rendered in markdown. To clarify:
$ examplelang program < program > rotProg
$ examplelang rotProg < rotProg > program1
$ diff -s program program1
Files program and program1 are identical

Shortest program wins. Standard loopholes are banned.

CJam, 26 25 21 bytes

WqN/":.+""\%"(~+N-~N*

Thanks to @MartinBüttner for golfing off 4 bytes!

Try it online in the CJam interpreter: original program | rotated program

This is the rotated program:

W
q
N
/
"
:
.
+
"
"
\
%
"
(
~
+
N
-
~
N
*

Idea

We can rotate the input a quarter turn clockwise by splitting it at linefeeds, reversing the order of the resulting rows, transposing rows with columns, and finally joining the rows, separated by linefeeds.

Likewise, we can rotate counterclockwise by transposing first, then reversing the rows.

Since the transposition built-in z is forbidden, we can use :.+ (reduce by vectorized character or string-character concatenation) to achieve the same effect.

:.+ is the only part of the source code that cannot be broken up. We push the strings "W%" and ":.+", conditionally reverse them if the second string contains a linefeed, concatenate, remove all linefeeds, and evaluate the result.

Code

W     e# Push -1.
qN/   e# Read all input at split it at linefeeds.
":.+" e# Push a string that, when evaluated, transposes rows and columns.
      e# As explained in the previous section, this does NOT use a built-in
      e# for matrix transposition.
"\%"  e# Push a string that, when evaluated, reverses the rows.
(~    e# Shift out the first character and evaluate it.
      e# For the original code, this evaluates '\', swapping the strings on
      e# the stack. For the rotated code, this evaluates `\n', doing nothing.
+N-   e# Concatenate and remove linefeeds.
      e# The stack now contains:   -1 input "%:.+"   or   -1 input ":.+\%"
~     e# Evaluate the string on top of the stack.
N*    e# Join the resulting array, separating by linefeeds.


Find arrays with distinct subarray sums Consider an array A of length n. The array contains only integers in the range 1 to s. For example take s = 6, n = 5 and  A = (2, 5, 6, 3, 1). Let us define g(A) as the collection of sums of all the non-empty contiguous subarrays of A. In this case g(A) = [2,5,6,3,1,7,11,9,4,13,14,10,16,15,17]. The steps to produce g(A) are as follows:

The subarrays of A are (2), (5), (6), (3), (1), (2,5), (5,6), (6,3), (3,1), (2,5,6), (5,6,3), (6,3,1),(2,5,6,3), (5,6,3,1), (2,5,6,3,1). Their respective sums are 2,5,6,3,1,7,11,9,4,13,14,10,16,15,17.

In this case all the sums are distinct.

However, if we looked at g((1,2,3,4)) then the value 3 occurs twice as a sum and so the sums are not all distinct.

Task

For each s from 1 upwards, your code should output the largest n so that there exists an array A  of length n with distinct subarray sums.

Your code should iterate up from s = 1 giving the answer for each s in turn. I will time the entire run, killing it after one minute.

Your score is the highest s you get to in that time.

In the case of a tie, the first answer wins.

Examples

The answers for s = 1..12 are n=1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 9.

Testing

I will need to run your code on my ubuntu machine so please include as detailed instructions as possible for how to compile and run your code.

Leaderboard

s = 19 by Arnauld in C

C (gcc), s = 19

This is basically a port of my Node.js answer. It goes one step further with the default compiler options and two steps further with -O2 or -O3.

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

void search(uint8_t * arr, int n, uint8_t * sum, int * max, char * str, int depth) {
  int i, j, k, s;
  char tmp[16];

  // do we have a better array?
  if(depth > *max) {
    for(str[0] = '\0', i = 0; i < depth; i++) {
      sprintf(tmp, "%d ", arr[i]);
      strcat(str, tmp);
    }
    *max = depth;
  }

  // try to append i = 1 to n to the current array
  for(i = 1; i <= n; i++) {
    // provided that doing so does not produce a sum that was already encountered
    if(!sum[i]) {
      for(sum[s = i] = 1, j = depth; j && !sum[s += arr[j - 1]]; j--) {
        sum[s] = 1;
      }
      if(!j) {
        // this is valid: set the value in arr[] and do a recursive call
        arr[depth] = i;
        search(arr, n, sum, max, str, depth + 1);
      }
      // whether the recursive call was processed or not, we have to clear the flags
      // that have been set above
      for(sum[s = i] = 0, k = depth - 1; k >= j; k--) {
        sum[s += arr[k]] = 0;
      }
    }
  }
}

int solve(int n, char * str) {
  int     max = 0;              // best length so far
  int     hi = n * (n + 1) / 2; // highest possible sum for n
  uint8_t sum[hi + 1];          // encountered sums
  uint8_t arr[n];               // array

  memset(sum, 0, (hi + 1) * sizeof(uint8_t));
  search(arr, n, sum, &max, str, 0);

  return max;
}

/////////////////////////////////////////////////////////////////////////////////////

void main() {
  char str[128];
  int  n, res;

  for(n = 1; n <= 19; n++) {
    res = solve(n, str);
    printf("N = %d --> %d with [ %s]\n", n, res, str);
  }
}

Try it online!


Compute the kangaroo sequence Backstory

Disclaimer: May contain made up information about kangaroos.

Kangaroos traverse several stages of development. As they grow older and stronger, they can jump higher and longer, and they can jump more times before they get hungry.

In stage 1, the kangaroo is very little and cannot jump at all. Despite this, is constantly requires nourishment. We can represent a stage 1 kangaroo's activity pattern like this.

o

In stage 2, the kangaroo can make small jumps, but not more than 2 before it gets hungry. We can represent a stage 2 kangaroo's activity pattern like this.

 o o
o o o

After stage 2 the kangaroo improves quickly. In each subsequent stage, the kangaroo can jump a bit higher (1 unit in the graphical representation) and twice as many times. For example, a stage 3 kangaroo's activity pattern looks like this.

  o   o   o   o
 o o o o o o o o
o   o   o   o   o

All that jumping requires energy, so the kangaroo requires nourishment after completing each activity pattern. The exact amount required can be calculated as follows.

Assign each o in the activity pattern of a stage n kangaroo its height, i.e., a number from 1 to n, where 1 corresponds to the ground and n to the highest position.
Compute the sum of all heights in the activity pattern.

For example, a stage 3 kangaroo's activity pattern includes the following heights.

  3   3   3   3
 2 2 2 2 2 2 2 2
1   1   1   1   1

We have five 1's, eight 2's, and four 3's; the sum is 5·1 + 8·2 + 4·3 = 33.

Task

Write a full program or a function that takes a positive integer n as input and prints or returns the nutritional requirements per activity of a stage n kangaroo.

This is code-golf; may the shortest answer in bytes win!

Examples

 1 ->     1
 2 ->     7
 3 ->    33
 4 ->   121
 5 ->   385
 6 ->  1121
 7 ->  3073
 8 ->  8065
 9 -> 20481
10 -> 50689

Coffeescript, 19 bytes

(n)->(n*n-1<<n-1)+1

Edit: Thanks to Dennis for chopping off 6 bytes!

The formula for generating Kangaroo numbers is this:

Explanation of formula:

The number of 1's in K(n)'s final sum is 2^(n - 1) + 1.

The number of n's in K(n)'s final sum is 2^(n - 1), so the sum of all the n's is n * 2^(n - 1).

The number of any other number (d) in K(n)'s final sum is 2^n, so the sum of all the d's would be d * 2^n.

Thus, the sum of all the other numbers = (T(n) - (n + 1)) * 2^n, where T(n) is the triangle number function (which has the formula T(n) = (n^2 + 1) / 2).

Substituting that in, we get the final sum

  (((n^2 + 1) / 2) - (n + 1)) * 2^n
= (((n + 1) * n / 2) - (n + 1)) * 2^n
= ((n + 1) * (n - 2) / 2) * 2^n
= 2^(n - 1) * (n + 1) * (n - 2)

When we add together all the sums, we get K(n), which equals

  (2^(n - 1) * (n + 1) * (n - 2)) + (2^(n - 1) + 1) + (n * 2^(n - 1))
= 2^(n - 1) * ((n + 1) * (n - 2) + n + 1) + 1
= 2^(n - 1) * ((n^2 - n - 2) + n + 1) + 1
= 2^(n - 1) * (n^2 - 1) + 1

... which is equal to the formula above.


Converting Numbers to a "Not quite place-value system" Lets create a system of numbers where the biggest digit in the nth place value (counting from right to left) of a number length m is always equal to m - n + 1. To give an example the largest 5 digit number expressible in this system is written 12345. Apart from the number of digits available to be used in a particular place being restricted, all other incrementation is standard. Namely when a digit is to surpass its digit limit we add one to the next digit.

Here is how counting would be represented in this system:

1; 10; 11; 12; 100; 101; 102; 103; 110; 111; 112; 113; 120; 121; 122; 123; 1000; 1001 ...

Your task is to write a function that takes a standard base 10 number and converts it to my numbering system.

Shorter code is preferable. Bonne Chance!

**If you need digits after 9 (you should) you can choose to use letters, or you can you return a 2 digit number as an element of a list.

Test Cases

10 -> 111
20 -> 1003
30 -> 1023
50 -> 1123
100 -> 10035
23116 -> 1234567
21977356 -> 123456789A

Last case may be incredibly slow to run depending on how you implemented. You don't need to run it if it takes too long or uses too much memory. However  note that there exist ways to have it run quickly and using little memory.

Mathematica, 64 bytes

Part[Join@@Array[Tuples@Join[{{1}},Array[Range,#-1,3]-1]&,#],#]&

Unnamed function taking a positive integer argument and returning a list of integers.

Join[{{1}},Array[Range,#-1,3]-1] returns the nested list { {1}, {0,1,2}, {0,1,2,3}, ..., {0,1,...,#} }. Then Tuples returns the (sorted) set of all tuples whose first element lies in {1}, whose second element lies in {0,1,2}, and so on; these are the #-digit numbers in this numbering system. Join@@Array[...,#] returns an array of all the numbers in this numbering system with at most # digits, and Part[...,#] extracts the #th such number.

This is hopelessly slow! It runs fine for the input up to 9. For larger input, test it by replacing the end ,#],#]& with ,Ceiling[0.9Log[#]]],#]&; this puts a more realistic cap on the number of digits necessary to go far enough in the numbering system to find the one we want.


Output an Anagram! No Not That One! Given a list of unique strings that are anagrams of each other, output an anagram of those words that is different from each word in the list.
The strings will be alphanumeric, and there is guaranteed to be a valid anagram.
The program or function can, but doesn't have to be non-deterministic, meaning given the same input, multiple running a of the code can yield different outputs, as long as every possible output is a valid one.
Test Cases
[Input] -> Possible output
-----------------
[ab] -> ba
[aba, aab] -> baa
[123, 132, 231, 312, 321] -> 213
[hq999, 9h9q9, 9qh99] -> 999hq
[abcde123, ab3e1cd2, 321edbac, bcda1e23] -> ba213ecd

Python 3, 64 bytes

lambda a:[*{*permutations(a[0])}-{*a}][0]
from itertools import*

Try it online!


1D Hopping Array Maze Inspired by We do tower hopping and related to 2D Maze Minus 1D
Introduction
Your task is to find the shortest path to get out of an array maze following specified rules.
Challenge
A 1D array a with n elements can be regarded as a maze composed of n points, where point with index k is connected to the points with k+a[k] and k-a[k] in a one-way manner. In other words, you can jump forward or backward exactly a[k] steps from the point with index k. Points with an index outside the bounds of the array are considered outside the maze.
To illustrate this, consider the following array,
[0,8,5,9,4,1,1,1,2,1,2]

If we are at the 5th element right now, since the element is 4, we can hop 4 steps forward to the 9th element, or 4 steps backward to the 1st element. If we do the latter, we end up with the element 0, which indicates no further moves are possible. If we do the former, since the 9th element is 2, we can choose to hop to the 11th element, which is again a 2, and then we can hop again to the "13th element", which is out of the bounds of the array and considered an exit to the maze.
So if we start from the element in the middle, one way to get out of the maze is hopping 1 step back, 4 steps forward, 2 steps forward and again 2 steps forward, which can be expressed as the array [-1,4,2,2]. Alternatively you can express it with the array [4,8,10,12] which records the zero-based index of all intermediate and final points (1-based index is also fine), or just the signs, [-1,1,1,1].
Escaping the maze from the low-index end is also OK.
Using the first notation and starting from the same element, [1,1,1,2,2] is also a solution but it is not optimal since there are 5 steps instead of 4.
The task is to find out the shortest path to get out of the array maze and output the path. If there are more than one optimal paths, you can output any or all of them. If there are no solution, you should output a falsy value chosen by you that is discernible from a valid path (producing no output at all is also OK).
For simplicity, the number of elements in the array is always an odd number and we always start from the element in the middle.
Test cases
The test cases illustrates various forms of output, but you are not limited to these.
Input
Output

[0,8,5,9,4,1,1,1,2,1,2]
[-1,4,2,2]

[2,3,7,1,2,0,2,8,9]
[2,9] (or [2,-5] or [[2,9],[2,-5]])

[0,1,2,2,3,4,4,4,3,2,2,3,0]
[1,-1,1,1]

[0,1,2,2,4,4,6,6,6,6,6,4,2,1,2,2,0]
[]

Specs

You may write a function or a full program.

The array only contains nonnegative integers.

You can take input and output through any standard form, but please specify in your answer which form you are using.

This is code-golf, the lowest number of bytes wins.

As usual, default loopholes apply here.

JavaScript (ES6), 117 bytes
Returns an array of 0-indexed intermediate and final points, or an empty array if no solution exists.
a=>(g=(x,p,d=a[x])=>1/d?[d,-d].map(d=>p.includes(X=x+d)||g(X,[...p,X])):o=o==''|o[p.length]?p:o)(a.length>>1,o=[])&&o

Try it online!
Commented
a =>                              // given the maze a[]
  (g = (                          // g = recursive function taking:
    x,                            //   x = current position
    p,                            //   p[] = list of visited cells
    d = a[x]                      //   d = value of current cell
  ) =>                            //
    1 / d ?                       // if d is defined:
      [d, -d].map(d =>            //   for d and -d:
        p.includes(X = x + d) ||  //     if the cell at X = x + d was not yet visited,
        g(X, [...p, X])           //     do a recursive call to g() at this position
      )                           //   end of map()
    :                             // else:
      o =                         //   update o:
        o == '' |                 //     if o was empty
        o[p.length] ?             //     or p is shorter than o:
          p                       //       set o to p
        :                         //     else:
          o                       //       let o unchanged
  )(a.length >> 1, o = [])        // initial call to g(), starting in the middle
  && o                            // return o


Crazy Blazin' DOM Injection Introduction
This problem is a challenge that has to do with DOM manipulation at scale and overcoming some issues that may be inherent in dealing with the DOM.

This challenge is interesting because limitations push us to think through things differently and lean on the strengths of languages different than what we usually use.
I created this challenge myself based on a real world problem I ran into myself (details can be provided if needed). If this challenge has any relation to a differently know problem, those similarities are coincidental.

This challenge will be scored based on fastest execution.
Challenge
You must render one of the challenge levels in the Chrome web browser (84.0.4147.89 for standardization purposes) (submissions will need to be JavaScript functions for timing purposes):

easy
medium
hard

Using JavaScript please complete the following:

Get each table displayed and add a class table-n to each table where n is a zero based index of order of the table on the screen. If a table is nested within a table the parent would be N and the child would be N+1 with the next table being N+2.
Get each row displayed in each table and add a class of table-n-row-r where r is a zero based index of rows in the table represented by table-n.
Get each cell displayed in each table and add a class of table-n-row-r-cell-c where c is a zero based index of cells in a row represented by table-n-row-r.

At the end of the challenge the web page should still be able to be interacted through in the browser, and a call to document.getElementsByClassName('table-n-row-r-cell-c'); should return one and only one cell from the DOM.
Any method available to you as valid as long as:

Access to one of the difficulty levels has been done through Chrome (84.0.4147.89)
The URL of the browser and the page displayed doesn't change
A call to document.getElementsByClassName('table-n-row-r-cell-c'); returns only one element

Output Examples
For this example we're using the easy level as input.
The abbreviated output in the DOM should be.
<!DOCTYPE html>

    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Code Golf Challenge</title>

                1
                ...

                11
                12
                ...

            ...

There are only  and  elements used as cell elements for the challenge.
As long as document.getElementsByClassName('table-n-row-r-cell-c'); returns an element with this class, we're good to go.
Qualifying Entries
All entries need to have an execution speed of under 40 seconds for at least one difficulty level to qualify.
Timing starts when your algorithm starts, but after the page has loaded completely as all elements must be available (the browser spinner has stopped spinning).
Calculate the runtime for your method by calling performance.now() before and and after your injection method, and subtracting the first from the second as in the example below.
let t0 = performance.now();
doSomething()   // <---- The function you're measuring time for
let t1 = performance.now();
let totalTime = t1 - t0;

Winner
The entry that handles the highest difficulty within 40 seconds wins. Ties are broken by execution time at that difficulty.

About 200 ms
function mark() {
  var t = 0, tp = '';
  var c = [], i = { r: 0, p: '', c: 0 };
  var elements = document.body.getElementsByTagName('*');
  var length = elements.length, index, v;
  for (index = 0; index < length; ++index) {
    v = elements[index];
    switch (v.tagName) {
      case 'TH':
      case 'TD':
        v.className = i.p + i.c++;
        if (i.c == 10 && i.r == 10) {
          i = c.pop();
        }
        continue;
      case 'TR':
        v.className = i.p = i.t + i.r++;
        i.c = 0;
        i.p += '-col-';
        continue;
      case 'TABLE':
        v.className = tp = 'table-' + t++;
        tp += '-row-';
        c.push(i);
        i = { t: tp, r: 0, p: '', c: 0 };
    }
  }
}

If your code runs more than 2s, you must do something wrong. I believe.


Calculate the Fermat Point of a Triangle This is somewhat similar to The centers of a triangle, but with a different point. The Fermat Point is the point P in triangle ABC such that the value of AP + BP + CP is minimized. There are two cases:

If there is an angle greater than 120 degrees, that vertex is the fermat point. Otherwise, draw equilateral triangles on each of the sides of ABC. Connect the far vertex of each equilateral triangle to the opposite vertex of triangle ABC. Doing this for each of the three equilateral triangles results in a single common point of intersection for all three lines, which is the Fermat Point.

It should run within 5 seconds on a reasonable machine.

Input: A set of 3 points, not necessarily integers. This can be taken as a nested array, string, list of tuples, etc. (whatever suits your language).

Output: The coordinates of the Fermat point, again, however your language best handles points. Floating point inaccuracies will not be counted against you.

Test Cases:

[[1, 1], [2, 2], [1, 2]] --> [1.2113248654051871, 1.788675134594813]
[[-1, -1], [-2, -1], [0, 0]] --> [-1, -1]
[[-1, -1], [1, -1], [0, 1]] --> [0, -0.42264973081037427]
[[0, 0], [0.5, 0.8660254037844386], [-5, 0]] --> [0, 0]
[[0, 0], [0, -5], [-0.8660254037844386, 0.5]] --> [0, 0]

This is code golf so shortest code wins!

Haskell, 346 291 285 bytes

infixl 5£
z=zipWith
(?)=z(-)
t[a,b]=[-b,a]
a¤b=sum$z(*)a b
a%b=t a¤b
r a b c=[c%b/a%b,c%a/a%b]
x£y=2*x¤y<= -sqrt(x¤x*y¤y)
f[a,b,c]|a?b£c?b=b|a?c£b?c=c|b?a£c?a=a|[n,m,p,o]<-c?k a b c++a?k b c a=r[m,o][n,p][c%[n,m],a%[p,o]]
k a b c=map(/2)$z(+)a b?map(signum((b?a)%(c?a))*sqrt 3*)(t$b?a)

The same code with some explanations

infixl 5£
z=zipWith

-- operator ? : difference of two vectors
(?)=z(-)

-- function t : rotate a vector by +90 degrees
t[a,b]=[-b,a]

-- operator ¤ : scalar product of two vectors ( a¤b = a0 * b0 + a1 * b1 )
a¤b=sum$z(*)a b

-- operator % : "cross product" of two vectors ( a%b = a0 * b1 - a1 * b0 )
--      this returns actually the z coordinate of the 3d cross vector
--      other coordinates are nul since a and b are in the xy plan
a%b=t a¤b

-- function r : solves the system of two linear equations with two variables x0,x1 :
--      a0*x0 - b0*x1 = c0
--      a1*x0 - b1*x1 = c1
r a b c=[c%b/a%b,c%a/a%b]

-- operator £ : returns true if the angle between two vectors is >= 120 degrees
--      x¤y = ||x|| * ||y|| * cos(xyAngle)
--      so xyAngle>=120° is equivalent to : x¤y / (||x|| * ||y||) <= -0.5
x£y=2*x¤y<= -sqrt(x¤x*y¤y)

-- function k : takes 3 points A B C of a triangle and constructs the point C'
--              of the equilateral triangle ABC' which is opposite to C:
--              C' = (A+B)/2 - ((+/-) sqrt(3)/2 * t(AB))
--
--      the sign +/- is given by the sign of the cross vector of AB an AC ((b?a)%(c?a))
--      which is >0 if the angle between AB and AC is positive
--      and <0 otherwise.
k a b c=map(/2)$z(+)a b?map(signum((b?a)%(c?a))*sqrt 3*)(t$b?a)

-- function f : returns the fermat point of a triangle
f[a,b,c]
    |a?b£c?b=b  -- return B if angle ABC >= 120°
    |a?c£b?c=c  -- return C if angle BCA >= 120°
    |b?a£c?a=a  -- return A if angle CAB >= 120°
    |[n,m,p,o]<-c?k a b c++a?k b c a= -- calculate the two segments C'C and A'A
        r[m,o][n,p][c%[n,m],a%[p,o]]  -- return their intersection

Tests:

main = do
    print $ f [[1, 1], [2, 2], [1, 2]]
    print $ f [[-1, -1], [-2, -1], [0, 0]]
    print $ f [[-1, -1], [1, -1], [0, 1]]
    print $ f [[0, 0], [0.5, 0.8660254037844386], [-5, 0]]
    print $ f [[0, 0], [0, -5], [-0.8660254037844386, 0.5]]

Output:

[1.2113248654051871,1.7886751345948126]
[-1.0,-1.0]
[0.0,-0.42264973081037427]
[0.0,0.0]
[0.0,0.0]


Fill a bowl with alphabet soup We seem to never get tired of alphabet-related challenges...

The recipe

Given

a string of letters S, and
two positive integers M, N,

produce an alphabet soup with the letters of S occupying random positions in a rectangular bowl of size M×N, framed by a non-alphabetic, non-space character to represent the rim of the bowl.

Positions not used by letters should be displayed as spaces. See the examples below.

Aditional rules

The size M×N refers to the interior of the bowl. The size including the rim is M+2×N+2.
Each character from S should appear once in the bowl, in a different position; that is, one character cannot overwrite another.
S may contain duplicates. For instance, if S is the string 'abcc', the soup must contain one a, one b, and two c (all in different positions).
The inputs will satisfy the restrictions M >= 1, N >= 1, 1 <= length(S) <= M*N.
The rim of the bowl can be any non-alphabetic, non-space character, consistent across program runs and input values.
Letter positions in the bowl are random, so the result may differ every time the program is run with the same inputs.
Given the input, every possible set of letter positions should have a non-zero probability. Since this cannot be checked from a few realizations of the program, please explain how your code fulfills this.
Leading or trailing whitespace around the rim is allowed.
S will contain are only uppercase letters. If wou wish, you can choose to take only lowercase letters.
Input and output are flexible as usual. For example, the output can be a string with newlines, a 2D character array, or a list of lines.
Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
The shortest code in bytes wins.

Examples

Inputs are shown as S, [M N], where M is number of rows and N is number of columns. The character # is used for the rim.

'O', [1 1]:

###
#O#
###

'HEY', [1 3]:

#####
#YHE#
#####

'HELLO', [4 11]:

#############
#  O        #
#         H #
#    LE     #
#   L       #
#############

'ADVNJSGHETILMVXERTYIOJKCVNCSF', [8 12]:

##############
#K  V  L   S #
# A   V  X H #
#T    M C    #
# I       O N#
#  YC        #
# G  I   R SE#
#   J      F #
#JT  D  V EN #
##############

'OOOOOOOOOOXXXXX', [13 31]:

#################################
#    X                          #
#                O              #
#                               #
#                  X            #
#                        O      #
#             X           O     #
#      O                        #
#         X                     #
#                        O      #
#       X                       #
#                    O          #
#  O      O      O              #
#                             O #
#################################

'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ', [11 41]

###########################################
#                                       JU#
#     Q         C M    G     R T U Y  H   #
#  KI          E   H    M   YO            #
#      V BW        I    JC                #
#     SV           D     P   B          U #
#           A     F    RF   J  KP E       #
#            E   N      TH        Z       #
#    N  BM  O     Q   I        AS N  WX   #
#   S     O  K       G L       P       Q  #
#Z     L T         R   L       A      F DD#
#      V   Y           WX   C       G XZ  #
###########################################

05AB1E, 20 18 16 15 14 bytes
*j.rS²ô2Føε8.ø

Takes three inputs in the order: height, width, string. Output as a 2D list of characters.
Uses 8 as border, but could be any digit.
-1 byte thanks to @Grimy.
Try it online or verify all test cases. (TIO contains }}J» in the footer to pretty-print the result; feel free to remove it to see the actual output 2D list of characters instead.)
Explanation:

*               # Multiply the (implicit) width and height inputs
 j              # Pad the (implicit) input-string with up to that amount of leading spaces,
                # so the total string-length is equal to that value
  .r            # Shuffle the characters in the string
    S           # Convert the string to a list of characters
                # (edge-case for the zip below with strings of size 1 with 1x1 dimensions)
     ²          # Push the width input again
      ô         # Split the list of characters into parts of that size
       2F       # Loop 2 times:
         ø      #  Zip/transpose the 2D list; swapping rows/columns
          ε     #  Inner map over each line:
           8.ø  #   And surround this line-list with a leading/trailing "8"
                # (after the loop, the result is output implicitly)


Tell me my screen resolution! Output the device's screen resolution in the specific format of [width]x[height](without the brackets). For example, an output could be 1440x900.

Here's an online tester that you can use to check your own screen resolution.

JavaScript (ES6), 32 bytes
(_=screen)=>_.width+"x"+_.height

Outputs as function return. Add f= at the beginning and invoke like f(). Uses parameter-initializing to initialize the parameter _ to screen object. The rest is self-explanatory.

f=(_=screen)=>_.width+"x"+_.height
console.log(f())

Note: Passing an argument to this function will cause it to fail.

JavaScript (Previous Solution), 35 bytes

with(screen)alert(width+"x"+height)

Never thought I will one day use with! I don't think this can be golfed further.


ASCII Meme Arrow Generator Specifications

Given a number n, output an ASCII "meme arrow" (greater-than symbol, >) of size n.

n will always be a positive integer, greater than 0.

Examples

n = 2

\
 \
 /
/

n = 5

\
 \
  \
   \
    \
    /
   /
  /
 /
/

Sample code

Here is a sample program, written in Crystal, that returns the correct results. Run it as ./arrow 10.

arrow.cr:

def f(i)
        i.times { |j|
                j.times { print ' ' }
                puts "\\"
        }
        i.times { |j|
                (i-j-1).times { print ' ' }
                puts '/'
        }
end

f(ARGV[0].to_i)

Rules

This is code-golf. The shortest answer wins. However, I will not select an answer, because the shortest answer may change over time.
Standard loopholes are not allowed.


Make a Valentine wish with your favourite language Write the most creative program to display your Valentine wish to your favorite programming language, in that language.

E.g.

#!/usr/bin/perl

use Modern::Perl;

say "I love Perl";

C/Python Polyglot/Polygamist

Monogamy isn't for everyone.
Based on my answer to Execute Prints Backwards.

#define def main(){0?
#define print printf(
#define return 0)));}

def main():
    print "Python",
    print ", I love you much more than ",
    print "C",
    return

main();

Output, when run as C:

C, I love you much more than Python

Output, when run as Python:

Python , I love you much more than  C


Sorting a List with a Another Sorted List Say i have a list (unorder):

Score = ['score1','score10','score6','score2','score22','score12']
Names = ['name1','name10','name6','name2','name22','name12']
email = ['email1','email10','email6','email2','email22','email12']

and then Score is sorted to be

ScoreSorted = ['score1','score2','score6','score10','score12','score22'].

The shortest code (in byte) to sort Name and Email with Score list wins

result of email and names list should be

EmailSorted = ['email1','email2','email6','email10','email12','email22'].
NamesSorted = ['name1','name2','name6','name10','name12','name22'].

Ruby 81 bytes

m=Score.each_index.sort_by{|i|Score[i]}
p m.map{|i|Names[i]}
p m.map{|i|Email[i]}

A golfed implemention of the algorithm below, assuming Score, Names, and Email are all already defined, and that only output of the post-sorted Names and Email is required.

Sample usage:

Score = ['score1','score10','score6','score2','score22','score12']
Names = ['name1','name10','name6','name2','name22','name12']
Email = ['email1','email10','email6','email2','email22','email12']

m=Score.each_index.sort_by{|i|Score[i]}
p m.map{|i|Names[i]}
p m.map{|i|Email[i]}

Sample output:

["name1", "name10", "name12", "name2", "name22", "name6"]
["email1", "email10", "email12", "email2", "email22", "email6"]

Ruby (with natural sort) 123 bytes

m=Score.each_index.sort_by{|i|Score[i].scan(/\d+|\D+/).map{|i|i=~/\d/?i.to_i: i}}
p m.map{|i|Names[i]}
p m.map{|i|Email[i]}

Correctly sorts strings with any number of digital groupings, as one would sort them 'naturally'. The only caveat is that all strings in the Score array must start with a digit, or all must start with a non-digit.

Sample output:

["name1", "name2", "name6", "name10", "name12", "name22"]
["email1", "email2", "email6", "email10", "email12", "email22"]

Python

Not a code-golf answer.

Find the inverse permutation of the list which is to be sorted in lexicographical order (in the problem description, this Scores array). This can be achieved in O(n log n) time (as the problem is analog to sorting), although the implementation below is O(n²).
Apply this permutation to each list. The permute function is O(n) complexity.

Sample implementation:

def get_inv_perm(items):
  size = len(items)
  perm = [0]*size
  for i in range(size):
    for j in range(size): perm[j] += items[j] > items[i]
  return perm

def permute(arr, perm):
  size = len(arr)
  out = [0] * size
  for i in range(size):
    val = perm[i]
    out[i] = arr[val]
  return out

if __name__ == "__main__":
  Score = ['score1','score10','score6','score2','score22','score12']
  Names = ['name1','name10','name6','name2','name22','name12']
  Email = ['email1','email10','email6','email2','email22','email12']

  perm = get_inv_perm(Score)

  print permute(Score, perm)
  print permute(Names, perm)
  print permute(Email, perm)

Sample output:

['score1', 'score10', 'score12', 'score2', 'score22', 'score6']
['name1', 'name10', 'name12', 'name2', 'name22', 'name6']
['email1', 'email10', 'email12', 'email2', 'email22', 'email6']

Because the sort is lexicographical, score10 and score12 appear directly after score1. The get_inv_perm function assumes the items list is unique. The remaining lists need not be.


Encode the date in Christmas Eve format The day this post was published was Christmas Eve. Tomorrow will be Christmas. Yesterday was Christmas Eve Eve. In two days it will be

Christmas Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve Eve

.

Your job is to take the date the program is run and encode it in Christmas Eve format.

If your program is run on Christmas, it should output the string "Christmas".
If your program is not run on Christmas, it should output the string "Christmas", followed by the string " Eve" repeated n times, where n is the number of days until Christmas.

Note that this must be based on the next Christmas. For example, if the day is April 26, 2019, you must do your calculation based on December 25, 2019, not any other Christmas.
Remember to count leap days.

Christmas is December 25th of every year.

This is code-golf, so the shortest code wins! Note though that the goal is not to find the shortest program in any language, but to find the shortest program in every particular language. For example, if you find the shortest C++ program, then it wins this contest for C++, even if someone finds a shorter program in Python.

SmileBASIC, 73 71 67 bytes
?"Christmas";
@L?" Eve"*(D!=P);
P=D
DTREAD OUT,M,D
IF M/D-.48GOTO@L

The program prints "Christmas", then prints " Eve" every time a day passes, until it is December 25th. (12/25 = 0.48)
May take up to a year to run.