Compute the maximum number of runs possible for as large a string as possible [This question is a follow up to Compute the runs of a string ]

  A period p of a string w is any positive integer p such that w[i]=w[i+p]
  whenever both sides of this equation are defined. Let per(w) denote
  the size of the smallest period of w . We say that a string w is
  periodic iff per(w) <= |w|/2.

So informally a periodic string is just a string that is made up from another string repeated at least once.  The only complication is that at the end of the string we don't require a full copy of the repeated string as long as it is repeated in its entirety at least once.

For, example consider the string x = abcab. per(abcab) = 3 as x[1] = x[1+3] = a, x[2]=x[2+3] = b and there is no smaller period. The string abcab is therefore not periodic.  However, the string ababa is periodic as per(ababa) = 2.

As more examples, abcabca, ababababa and abcabcabc are also periodic.

For those who like regexes, this one detects if a string is periodic or not:

\b(\w*)(\w+\1)\2+\b

The task is to find all maximal periodic substrings in a longer string.  These are sometimes called runs in the literature.

  A substring w is a maximal periodic substring (run) if it is periodic and neither w[i-1] = w[i-1+p] nor w[j+1] = w[j+1-p].  Informally, the "run" cannot be contained in a larger "run"
  with the same period.

Because two runs can represent the same string of characters occurring in different places in the overall string, we will represent runs by intervals. Here is the above definition repeated in terms of intervals.

  A run (or maximal periodic substring) in a string T is an interval
  [i...j] with j>=i, such that

  T[i...j] is a periodic word with the period p = per(T[i...j])
  It is maximal. Formally, neither T[i-1] = T[i-1+p] nor T[j+1] = T[j+1-p].  Informally, the run cannot be contained in a larger run
  with the same period.

Denote by RUNS(T) the set of runs in string T.

Examples of runs

The four maximal periodic substrings (runs) in string T = atattatt are T[4,5] = tt, T[7,8] = tt, T[1,4] = atat, T[2,8] = tattatt.
The string T = aabaabaaaacaacac contains the following 7 maximal periodic substrings (runs):
T[1,2] = aa, T[4,5] = aa, T[7,10] = aaaa, T[12,13] = aa, T[13,16] = acac, T[1,8] = aabaabaa, T[9,15] = aacaaca.
The string T = atatbatatb contains the following three runs. They are:
T[1, 4] = atat, T[6, 9] = atat and  T[1, 10] = atatbatatb.

Here I am using 1-indexing.

The task

Write code so that for each integer n starting at 2, you output the largest numbers of runs contained in any binary string of length n.

Score

Your score is the highest n you reach in 120 seconds such that for all k <= n, no one else has posted a higher correct answer than you.  Clearly if you have all optimum answers then you will get the score for the highest n you post. However, even if your answer is not the optimum, you can still get the score if no one else can beat it.

Languages and libraries

You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.

Example optima

In the following: n, optimum number of runs, example string.

2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011

What exactly should my code output?

For each n your code should output a single string and the number of runs it contains.

My Machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor.  This also means I need to be able to run your code.

Leading answers

49 by Anders Kaseorg in C. Single threaded and run with L = 12 (2GB of RAM).
27 by cdlane in C.

C

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

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

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

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

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

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

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

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

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

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

Output:

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

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

A remarkable nearly-optimal sequence

The prefixes of the infinite fractal sequence

1010010110100101001011010010110100101001011010010100101…

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

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

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


Parse a nested parentheses Objective
Mimic Haskell's reads :: ReadS ().
Or in other words, parse nested parentheses. Since the target type is () (the type with one possible value), "parsing" means discarding a leading nested parentheses.
Valid Input
"Nested parentheses" means (), (()), ((())), and so on. That is, leading nonzero (s and trailing )s of the same number.
But there's a twist. The parser must munch also leading or intercalated whitespaces. So for example, the following strings are valid to be munched:

( )
 ()
  (  ()    )

Note that trailing whitespaces are not to be munched.
Whitespaces
The following ASCII characters are always considered a whitespace:

\t U+0009; Horizontal Tab
\n U+000A; Line Feed
\v U+000B; Vertical Tab
\f U+000C; Form Feed
\r U+000D; Carriage Return
  U+0020; Space

For each of the following Unicode characters, it is implementation-defined to consider it a whitespace:

U+0085; Next Line
U+00A0; No-Break Space
U+1680; Ogham Space Mark
U+2000; En Quad
U+2001; Em Quad
U+2002; En Space
U+2003; Em Space
U+2004; Three-Per-Em Space
U+2005; Four-Per-Em Space
U+2006; Six-Per-Em Space
U+2007; Figure Space
U+2008; Punctuation Space
U+2009; Thin Space
U+200A; Hair Space
U+2028; Line Separator
U+2029; Paragraph Separator
U+202F; Narrow No-Break Space
U+205F; Medium Mathematical Space
U+3000; Ideographic Space

All other characters are never considered a whitespace.
Error
If the string doesn't start with a nested parentheses, the parser shall fall in an erroneous state. Ways that indicates an error include:

Monadic failing
Returning an erroneous value
Raising/Throwing an error

Output
When the parser successfully munched a nested parentheses, the parser shall output the unmunched part of string.
Examples
Valid example

When given (), the output is an empty string.
When given  ( ) Hello, the output is  Hello. Note the leading whitespace of the output.
when given ((())))), the output is )).

Erroneous example

Empty string
((()
(()())
(H)
Hello, world!

Ungolfed solution
C
Returns a null pointer for an error.
#include <stdbool.h>
#include <stdlib.h>

char *readMaybeUnit(char *str) {
    bool p = false;
    unsigned c = 0;
    while (*str != '\0') {
        switch (*str) {
        case '(':
            p = true;
            ++c;
            // FALLTHRU
        case '\t': case '\n': case '\v': case '\f': case '\r': case ' ':
            break;
        default:
            goto parseRightParentheses;
        }
        ++str;
    }
    parseRightParentheses: while (*str != '\0') {
        switch (*str) {
        case ')':
            if (1 >= c) {
                if (1 == c)
                    ++str;
                c = 0;
                goto returnReadMaybeUnit;
            }
            --c;
            // FALLTHRU
        case '\t': case '\n': case '\v': case '\f': case '\r': case ' ':
            break;
        default:
            goto returnReadMaybeUnit;
        }
        ++str;
    }
    returnReadMaybeUnit: return p && 0 == c ? str : NULL;
}

Retina 0.8.2, 32 31 bytes
^(\s*\()+(?<-1>\s*\))+(?(1)$.)

Try it online! Link includes test cases. Returns the original string on error. Considers the given control characters as white space, plus any Unicode characters (such as space) in the Separator group, plus U+0085. If only the minimal white space is desired, this can be achieved by prefixing e`. Explanation:
^(\s*\()+

Match some open parentheses at the start of the string.
(?<-1>\s*\))+

Match some close parentheses.
(?(1)$.)

Check that the same number of open and close parentheses were matched.

Delete the matched parentheses.
Alternative solution, also 31 bytes:
r`^(?<-1>\s*\()+(\s*\))+(.*)
$2

Try it online! Link includes test cases. If only the minimal white space is desired, this can be achieved by prefixing e. Explanation:
r`

Start matching at the end of the string and work backwards (like a lookbehind would).
(.*)

Match as much result as possible.
(\s*\))+

Match some close parentheses.
^(?<-1>\s*\()+

Match the open parentheses at the start of the string. The number of close parentheses must be at least as many as the number of open parentheses for the balancing group to succeed, but it can't be more because the (.*) ensures that as few close parentheses are matched as possible.
$2

Keep everything except the matched parentheses.
Previous 32-byte solution that returns the empty string on error:
1!`(?<=^(?<-1>\s*\()+(\s*\))+).*

Try it online! Link includes test cases. If only the minimal white space is desired, this can be achieved by prefixing e. Explanation:
1!`

Output the matched part of the first match.
(?<=^(?<-1>\s*\()+(\s*\))+)

Ensure that the match starts after balanced parentheses. Note that this is a lookbehind, so the match is processed right-to-left - the )s are matched first, then a ( can be matched for each ). There can't be too many )s because the lookbehind would have matched earlier, meaning that this is no longer the first match.
.*

Match the rest of the string. This actually counts as part of the match, and therefore becomes the resulting output.


Sort useless characters This challenge is inspired by this very nice answer by TidB.

In TidB's answer, every eight character is in the correct order: gnilwoB edoC (Code Bowling backwards). The other strings however are were in a strange, random order.

Your challenge is to fix this.

Take a (non-empty) string and a positive integer n as input. The string will contain ASCII characters in the range: 32-126 (space to tilde).

You must sort the string in ascending order (seen from the left, based on the ASCII-code value), but skip every nth character, starting from the end of the string. As an example, let's take the string abcdABC123 as input, and n=4, then we'll get:

abcdABC123   <- Input string. (n=4)
_b___B___3   <- These will not be sorted (every 4th starting from the end)
1_2AC_acd_   <- The remaining characters, sorted
1b2ACBacd3   <- The final string (the output)

Another example:

9876543210   <- Input string (n=2)
_8_6_4_2_0   <- These will not be sorted
1_3_5_7_9_   <- The remaining characters, sorted
1836547290   <- The final string (the output)

The input string can be taken on an optional format (string, list of characters, list of single character strings ...). The input integer can also be taken on an optional format.

Test cases:

The format will be n=__, followed by the input string on the next line. The output is on the line below.

n=1   (All elements will stay in place)
nafgaksa1252#"%#
nafgaksa1252#"%#

n=214  (The last character will stay in place. All other are sorted.
&/lpfAVD
&/AVflpD

n=8
g7L9T E^n I{><#ki XSj!uhl y= N+|wA}Y~Gm&o?'cZPD2Ba,RFJs% V5U.W;1e  0_zM/d$bH`@vKoQ 43Oq*C
g       n !#$%&'i*+,./01l234579;w<=>?@ADoEFGHIJKBLMNOPQR STUVWXYeZ^_`abcdhjkmqsuovyz{|}~C

MATL, 15 14 bytes
ttfiX\qgP)S5M(

Inputs are a string enclosed in single quotes and a number. Single-quote symbols in the string should be escaped by duplicating (as in MATLAB and Octave).
Try it online! Or verify all test cases.
Explanation
Consider inputs 'abcdABC123' and 4.
tt     % Implicitly input string. Duplicate twice
       % STACK: 'abcdABC123', 'abcdABC123', 'abcdABC123'
f      % Find: indices of nonzero elements: gives [1 2 ... n] where n is input length
       % STACK: 'abcdABC123', 'abcdABC123', [1 2 3 4 5 6 7 8 9 10]
i      % Input n
       % STACK: 'abcdABC123', 'abcdABC123', [1 2 3 4 5 6 7 8 9 10], 4
X\     % 1-based modulo
       % STACK: 'abcdABC123', 'abcdABC123', [1 2 3 4 1 2 3 4 1 2 3 4]
qg     % Subtract 1, convert to logical: gives true (1) for 1, false (0) otherwise
       % STACK: 'abcdABC123', 'abcdABC123', [0 1 1 1 0 1 1 1 0 1]
P      % Flip
       % STACK: 'abcdABC123', 'abcdABC123', [1 0 1 1 1 0 1 1 1 0]
)      % Use as logical index into the string
       % STACK: 'abcdABC123', 'acdAC12'
S      % Sort
       % STACK: 'abcdABC123', '12ACacd'
5M     % Push logical index again
       % STACK: 'abcdABC123', '12ACacd', [1 0 1 1 1 0 1 1 1 0]
(      % Write into original string as specified by the index. Implicitly display
       % STACK: 1b2ACBacd3

1-based modulo means that mod([1 2 3 4 5], 3) gives [1 2 3 1 2] instead of the usual (0-based) [1 2 0 1 2]. This is needed here to handle the case n=1 adequately.


One hundred passwords I have one hundred vaults, each one within another. Each vault has a password, consisting of a single number.

  95  43  81  89  56  89  57  67  7   45  34  34  78  88  14  40  81  23  26  78  46  8   96  11  28  3   74  6   23  89  54  37  6   99  45  1   45  87  80  12  92  20  49  72  9   92  15  76  13  3   5   32  96  87  38  87  31  10  34  8   57  73  59  33  72  95  80  84  11  4   11  11  37  71  77  91  49  21  52  48  43  11  77  52  64  3   9   21  38  65  69  84  96  78  7   71  80  78  3   97

It's too hard to memorize all these passwords, and it's not safe to keep the passwords on a piece of paper. The only solution I can think of is to use a program with exactly one hundred characters. The password to the nth vault will be found by treating the first n characters of the code as a program.

Thus, the first character of the program, if run as a program by itself, must output 95. The first two characters by themselves must output 43. The entire program must output 97.

I admit that this is really hard. So just do your best. Try to make your program work for as many vaults as possible, and I'll memorize the passwords to the rest.

Rules

If there is a tie, the winner is the earliest submission.
Standard loopholes forbidden. That includes reading from other files or from the Internet.
You have a few options for the code:

A full program which prints the correct number
A function which returns or prints it
An expression which evaluates to it (e.g. in C, 4+3 evaluates to 7)

You may assume a REPL environment
You may use different techniques for each value of n. For example, you can use different languages for each n, or sometimes use a full program and sometimes a function.

Note: This scenario is completely fictional. If you have a similar issue, do not post your passwords online.

><> (Fish), 95

Starting after the '  puts all characters onto the stack and at the end of the line it wraps around; closes the string with the same '; outputs the top of the stack as a number (n) and finish execution (;).

Characters for 13 and 10 were changed to space to not ruin the layout of the code (as fish is a 2D language.)

Some non-printable ASCII disappears in the answer. Correct program here.

'n;Y8Y9C-""NX(QN.`JY6%c--WP\1H  \LX `W&WX"9I;!H_PT%GM[140+M4@   &AET`NGPNa

Thanks for Martin Büttner and Sp3000 for improvements of 2 and 5 bytes.

Hex dump:

0000000: 276e 3b59 3859 3943 072d 2222 4e58 0e28  'n;Y8Y9C.-""NX.(
0000010: 5117 1a4e 2e08 600b 1c03 4a06 1759 3625  Q..N..`...J..Y6%
0000020: 0663 2d01 2d57 500c 5c14 3148 095c 0f4c  .c-.-WP.\.1H.\.L
0000030: 5803 0520 6057 2657 1f58 2208 3949 3b21  X.. `W&W.X".9I;!
0000040: 485f 5054 0b04 0b0b 2547 4d5b 3115 3430  H_PT....%GM[1.40
0000050: 2b0b 4d34 4003 0915 2641 4554 604e 0747  +.M4@...&AET`N.G
0000060: 504e 0361                                PN.a


Mid-Autumn Festival gambling game Tomorrow is the Mid-Autumn festival, and in the spirit of that holiday, I will introduce a gambling game that we (people from Xiamen) play during the holiday!
Rules
The game is played with six 6-sided dice. Different combinations of numbers have different ranks, with a special emphasis on fours and ones. Your job is to write a program/function that will rank the hand, given a roll of 6 dice. Here are the ranks (I've modified/simplified the rules a bit):

 I guess only Chinese people can do this challenge!  Okay, fine, here are some English explanations.

0: 4 fours and 2 ones.
1: 6 fours.
2: 6 ones.
3: 6 of any kind except fours and ones.
4: 5 fours.
5: 5 of any kind except for fours.
6: 4 fours.
7: Straight. (1-6)
8: 3 fours.
9: 4 of any kind except 4.
10: 2 fours.
11: 1 four.
12: Nothing.

Input
6 numbers, an array of 6 numbers, or a string of 6 numbers that represent the values of the 6 dice rolls from 1-6
Output
Your program/function may return/output anything to indicate the rank, as long as each rank is indicated by one output and vice versa. Ex. Using the numbers 0-12, 1-13, etc.
Examples(Using 0-12 as the outputs)
[1,1,1,1,1,1]->2
[1,4,4,4,1,4]->0
[3,6,5,1,4,2]->7
[1,2,3,5,6,6]->12
[3,6,3,3,3,3]->5
[4,5,5,5,5,5]->5

This is code-golf, so shortest byte count wins!

JavaScript (ES6), 88 bytes

a=>a.map(o=n=>[x=o[n]=-~o[n],6,,,21,9,8^o[1]][a=x<a?a:x])[5]|[,1,4,5,o[1]&2|8,2,4][o[4]]

Try it online!
or Test all possible rolls!

Outputs an integer according to the following mapping:

 Rank | Output       Rank | Output
------+--------     ------+--------
   0  |  31            7  |   7
   1  |  12            8  |   5
   2  |  14            9  |  21
   3  |   8           10  |   4
   4  |  11           11  |   1
   5  |   9           12  |   0
   6  |  29

How?

Method

The output is computed by performing a bitwise OR between:

a bitmask based on \$F\$: the number of 4's
a bitmask based on \$M\$: the maximum number of occurrences of the same dice

Exceptions:

When \$F=4\$: we use a special bitmask \$4b\$ when the two other dice are 1's, or a default bitmask \$4a\$ otherwise.
When \$M=6\$: we use a special bitmask \$6b\$ when we have a six-of-a-kind of 1's, or a default bitmask \$6a\$ otherwise.

Table

Valid combinations of \$F\$ and \$M\$ are highlighted in bold and blue in the following table.

$$\begin{array}{c|c|cccccccc}
&F&0&1&2&3&4a&4b&5&6\\
\hline
M&\text{OR}&0&1&4&5&8&10&2&4\\
\hline
1&6&\color{grey}{6}&\color{blue}{\textbf{7}}&\color{grey}{6}&\color{grey}{7}&\color{grey}{14}&\color{grey}{14}&\color{grey}{6}&\color{grey}{6}\\
2&0&\color{blue}{\textbf{0}}&\color{blue}{\textbf{1}}&\color{blue}{\textbf{4}}&\color{grey}{5}&\color{grey}{8}&\color{grey}{10}&\color{grey}{2}&\color{grey}{4}\\
3&0&\color{blue}{\textbf{0}}&\color{blue}{\textbf{1}}&\color{blue}{\textbf{4}}&\color{blue}{\textbf{5}}&\color{grey}{8}&\color{grey}{10}&\color{grey}{2}&\color{grey}{4}\\
4&21&\color{blue}{\textbf{21}}&\color{blue}{\textbf{21}}&\color{blue}{\textbf{21}}&\color{grey}{21}&\color{blue}{\textbf{29}}&\color{blue}{\textbf{31}}&\color{grey}{23}&\color{grey}{21}\\
5&9&\color{blue}{\textbf{9}}&\color{blue}{\textbf{9}}&\color{grey}{13}&\color{grey}{13}&\color{grey}{9}&\color{grey}{11}&\color{blue}{\textbf{11}}&\color{grey}{13}\\
6a&8&\color{blue}{\textbf{8}}&\color{grey}{9}&\color{grey}{12}&\color{grey}{13}&\color{grey}{8}&\color{grey}{10}&\color{grey}{10}&\color{blue}{\textbf{12}}\\
6b&14&\color{blue}{\textbf{14}}&\color{grey}{15}&\color{grey}{14}&\color{grey}{15}&\color{grey}{14}&\color{grey}{14}&\color{grey}{14}&\color{grey}{14}\\
\end{array}$$

All other combinations (in gray) can't possibly happen. For instance, if we have three 4's, we must have \$M\ge3\$. But because there are only 3 other remaining dice in such a roll, we also have \$M\le3\$. So, there's only one possible value of \$M\$ for \$F=3\$.

Example

If we have a straight, each dice appears exactly once. So we have \$M=1\$ and \$F=1\$. Using the bitmasks described in the above table, this leads to:

$$6 \text{ OR } 1 = 7$$

There is another \$7\$ in the table, but it's invalid. Therefore, a straight is uniquely identified by \$7\$.

Commented

a =>                   // a[] = input array, reused as an integer to keep track of the
  a.map(               //       maximum number of occurrences of the same dice (M)
    o =                // o = object used to count the number of occurrences of each dice
    n =>               // for each dice n in a[]:
    [                  //   this is the lookup array for M-bitmasks:
      x =              //     x = o[n] = number of occurrences of the current dice
        o[n] = -~o[n], //     increment o[n] (we can't have M = 0, so this slot is not used)
      6,               //     M = 1 -> bitmask = 6
      ,                //     M = 2 -> bitmask = 0
      ,                //     M = 3 -> bitmask = 0
      21,              //     M = 4 -> bitmask = 21
      9,               //     M = 5 -> bitmask = 9
      8 ^ o[1]         //     M = 6 -> bitmask = 14 for six 1's, or 8 otherwise
    ][a =              //   take the entry corresponding to M (stored in a)
        x < a ? a : x] //   update a to max(a, x)
  )[5]                 // end of map(); keep the last value
  |                    // do a bitwise OR with the second bitmask
  [                    // this is the lookup array for F-bitmasks:
    ,                  //   F = 0 -> bitmask = 0
    1,                 //   F = 1 -> bitmask = 1
    4,                 //   F = 2 -> bitmask = 4
    5,                 //   F = 3 -> bitmask = 5
    o[1] & 2 | 8,      //   F = 4 -> bitmask = 10 if we also have two 1's, 8 otherwise
    2,                 //   F = 5 -> bitmask = 2
    4                  //   F = 6 -> bitmask = 4
  ][o[4]]              // take the entry corresponding to F (the number of 4's)


2D Array Middle Point Given dimensions of a 2D array, except 1xn, that results in an odd number of elements, find the midpoint index.
Example: Input is 3x5, representing the 2D array

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

The midpoint index is [1,2]
Input

3
5

Output

1 , 2

Rules

Standard code-golf rules, fewest bytes wins
Either full program or function is permitted
When input is either 1xn or the corresponding array would have an even number of elements, output must be [0,0]
nx1 should be treated like any other array

APL (Dyalog Classic), 20 19 15 13 bytes

⌊÷∘2×2|×/×1≠⊃

Try it online!


Find the Inverse Neighbor Pairs Definition

We say a pair of integers \$(a,b)\$, where \$0<a<b<N\$ and \$N\$ is an integer larger than 4, is an inverse neighbor pair respect to \$N\$ if \$ab\equiv1\text{ }(\text{mod }N)\$ and \$1\le b-a\le\log_2{N}\$. There may be no such pairs respect to some integers \$N\$.

To illustrate the definition, consider \$N=14\$. \$(3,5)\$ is an inverse neighbor pair respect to \$N\$ because \$3\times 5=15\equiv1\text{ }(\text{mod }14)\$ and \$1\le 5-3=2\le\log_2{14}\approx 3.807\$. Another pair is \$(9,11)\$.

On the other hand, consider \$N=50\$. \$(13,27)\$ is not an inverse neighbor pair because although \$13\times 27=351\equiv1\text{ }(\text{mod }50)\$, their distance \$27-13=14\$ is too large to be "neighbors". In fact, there are no inverse neighbor pairs respect to this \$N\$, since there are no such pairs that both \$ab\equiv1\text{ }(\text{mod }50)\$ and \$1\le b-a\le\log_2{50}\approx 5.643\$ can be fulfilled.

Challenge

Write a program or function, that given an integer input \$N>4\$, outputs or returns all inverse neighbor pairs respect to \$N\$ without duplicate. You may output them in any reasonable format that can be clearly interpreted as distinct pairs by a human, e.g. two numbers per line, or a list of lists, etc.

The algorithm you use must in theory vaild for all integers \$N>4\$, although practically your program/function may fail or timeout for too large values.

Sample I/O

For inputs without any inverse neighbor pairs, the word empty in the output column means empty output, not the word "empty" literally.

Input  -> Output
5      -> (2,3)
14     -> (3,5), (9,11)
50     -> empty
341    -> (18,19), (35,39), (80,81), (159,163), (178,182), (260,261), (302,306), (322,323)
999    -> (97,103), (118,127), (280,289), (356,362), (637,643), (710,719), (872,881), (896,902)
1729   -> empty
65536  -> (9957,9965), (15897,15913), (16855,16871), (22803,22811), (42725,42733), (48665,48681), (49623,49639), (55571,55579)
65537  -> (2880,2890), (4079,4081), (10398,10406), (11541,11556), (11974,11981), (13237,13249), (20393,20407), (26302,26305), (39232,39235), (45130,45144), (52288,52300), (53556,53563), (53981,53996), (55131,55139), (61456,61458), (62647,62657)
524287 -> (1023,1025), (5113,5127), (59702,59707), (82895,82898), (96951,96961), (105451,105458), (150800,150809), (187411,187423), (192609,192627), (331660,331678), (336864,336876), (373478,373487), (418829,418836), (427326,427336), (441389,441392), (464580,464585), (519160,519174), (523262,523264)

Winning Condition

This is a code-golf challenge, so shortest valid submission of each language wins. Standard loopholes are forbidden by default.

05AB1E, 17 14 13 bytes
Thanks to @KevinCruijssen and @Grimmy for the fix and inspiration from Kevin's now deleted answer
-1 byte further thanks to @Grimmy
L.ÆʒRÆo@}ʒPI%

Try it online!

Explanation
L.Æ                    - Combinations of [1..N] with 2 elements
    ʒ     }            - Filter this when ...
     RÆo               - 2^(The difference of each pair) is...
        @              - <= the input
           ʒPI%        - Then filter this list further where the product modulo input is 1


The Back-and-Forth Sequence Imagine a path made up of < and > and ending in a @, e.g.

><>@

A walker starts on the left-most cell. He will traverse the path as follows:

If the walker is on a @ cell, he's reached the goal and is done.
If the walker is on a > cell, the entire path shifts one step to the right, cyclically, taking the walker with it.
If the walker is on a < cell, the entire path shifts one step to the left, cyclically, taking the walker with it.
Afterwards, the walker takes a single step. If he's at either end of the path, he moves away from the end. Otherwise he keeps moving in the direction he moved on the last step (ignoring the rotation), walking right initially.

Let's work through the above example. The walker's position is marked with ^:

><>@   --rotate-->  @><>
^                    ^
step right (first step):
@><>   --rotate-->  ><>@
  ^                  ^
step right:
><>@   --rotate-->  @><>
  ^                    ^
step left (dead end):
@><>   --rotate-->  ><>@
  ^                  ^
step left:
><>@   --rotate-->  @><>
^                    ^
step left:
@><>   Goal reached!
^

The walker visited 6 cells in the process (including the starting cell as well as the @, and counting each cell as often as it's visited).

Here is a small example, where the walker is transported across the edges by a rotation:

>>@   --rotate-->  @>>
^                   ^
step right (first step):
@>>   --rotate-->  >@>
  ^                ^
step right (dead end):
>@>   Goal reached!
 ^

This time the walker visited 3 cells.

We can easily turn this into an integer sequence:

You're given a positive integer N, e.g. 9.
You compute the the binary representation of this integer, e.g. 1001.
Then turn 1 into > and 0 into < and append a @: ><<>@.
We associate with N the number of cells visited by the walker in the number constructed this way.

The first few elements of the resulting sequence are:

2, 3, 3, 4, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6,
6, 10, 6, 10, 8, 8, 6, 10, 8, 8, 6, 6, 6, 6, 7, 7

This may seem quite arbitrary, but the resulting sequence actually turns out to have a lot of structure:

For reference, you can find the first 2048 numbers of the sequence in this pastebin.

The Challenge

You guessed it: you're to compute the above sequence. You can do that one of three ways:

You can produce an infinite sequence (while memory permits), either by continuously outputting (separated by non-numeric characters) values or by using some form of infinite generator in languages that support them. If you print an infinite stream to STDOUT, you don't have to print the numbers one by one, but make sure that every number would be printed after a finite amount of time (and in order). If you use this option, you should not take any input.
You can take an integer N as input and produce the Nth term of the sequence.
You can take an integer N as input and produce everything up to the Nth term of the sequence, either as a list or string using an unambiguous separator.

Since I don't want to penalise languages which can't easily convert between bases, instead of the integer N you may instead take the binary representation of N, using 0s and 1s as usual (as a list or string), with the most-significant bit first.

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

Standard code-golf rules apply.

Background

This actually computes the number of "ticks" a straight-forward interpreter of my esoteric programming language Labyrinth would need to interpret the "path" as source code. In that case, the "walker" is simply the instruction pointer (which has a position and a direction), the @ command terminates the program and < and > are source-code modification commands.


Converting rational numbers to an “alien” data format For a story I'm writing, I needed to convert 101⅐ (101 + 1/7 if that doesn’t show up for you) into base 47.

Expressing an integer in some base brings back memories of first learning how to program back in the days of 8-bit systems; it’s a fairly easy exercise. Doing so using a floating-point format is a bit harder, though. The final twist, identifying the repeating digits, is more challenging to do elegantly.

So I thought I’d do it in a different language from what I’m used to, just for fun and learning the new dialect.  And I thought it would be good to share, so here I am.  The vast majority of the posts here are (char or byte of source) code golf, but I’m more interested in an elegant expression in the target language.  Cyclomatic complexity isn’t a category, but atomic-code-golf is pretty close.

The program should take a rational number in a natural way, such as supplying three integers on the command line of the script invocation or standard input.  This does not count towards the score (nor does the error checking and defaults if you give it one value only).  The function (or part that is counted for score) should receive the three values; e.g. 101,1,7 for the example above.

The output is a sequence of code points that are transliterated into text output as follows:

digits 0 through 9 inclusive:  ‘0’ through ‘9’ in the normal way
digits 10 through 46: express as ‘[10]’ through ‘[46]’
negative sign: the normal ASCII ‘-’
separator: ‘:’
prefix: ‘#’

A number starts with the prefix ‘#’ and has up to three parts, separated by ‘:’.  Leading parts are omitted if zero.

The basic natural number (BNN) is encoded using the digits in base 47, outputted in little-endian.  That is, 99181 = 11×470 + 42×471 + 44×472 so the digits, in order output, are [11][42][44].

The last (possibly only) part of a number is an integer, which is a leading ‘-’ if the value is negative, followed by the digits of the BNN.  So, 99181 would be encoded as #[11][42][44] and −99181 would be encoded as #-[11][42][44].

The middle part, if needed, is an exponent as for scientific notation.  It states which power of the base (position) is the first digit listed.  In the case of integers, this is 470 so the 0-valued part is omitted.

Suppose you divide that by 47, shifting the radix point by one.  That is, 99181 ÷ 47 is the same digits but starting with 47−1; that is, 11×47−1 + 42×470 + 44×471, and the output becomes #-1:[11][42][44].  There are two parts, the first is the encoding for the integer −1, and the second is the digits as before.

Now it comes out so neat only if you divide by some power of 47.  Normally, a rational number made of small components will end up with a repeating sequence of digits.  In decimal, for example, ⅓ is .3333… and ⅐ (1/7) is .142857142857142857…  in the first case one digit repeats, in the second case 6 digits repeat.

In the alien real number format, the first part, if present, states how many digits are to be repeated.  So, the number 8½ would have a single digit [23] repeating forever, so we just encode one of them and state that 1 repeats: #1:-1:[23]8.  The first part is 1 (the encoded BNN for the value 1) which means that one digit is to be repeated.  The second part (negative sign and BNN) indicates that the first digit given is the 47-1 position.  The third part is the two digits needed: 26×47-1 + 8×470.

Somebody should check my results, but I think the correct output for (101 1 7) is:
#6:-6:[20][13][40][26][33]672.

Batch, 531 bytes

@echo off
set q=
set s=
set m=
if %1 lss 0 set m=-
set/ai=%m%%1,n=%2,d=%3,p=0
:i
set/ar=i%%47,i/=47
if %r% gtr 9 set r=[%r%]
set s=%s%%r%
if %i% gtr 0 goto i
:p
if %n%==0 goto n
set/ao=n,g=d%%47
if %g% gtr 0 goto g
set/ap+=1,d/=47,r=n/d,n%%=d
if %r% gtr 9 set r=[%r%]
set s=%r%%s%
goto p
:g
set/aq+=1,p+=1,r=n*47/d,n=n*47%%d
if %r% gtr 9 set r=[%r%]
set s=%r%%s%
if %n% neq %o% goto g
if %q% gtr 9 set q=[%q%]
set q=%q%:
:n
if %p% gtr 9 (set q=%q%-[%p%]:)else if %p% gtr 0 set q=%q%-%p%:
echo #%q%%m%%s%

Takes three parameters, whole number, numerator, denominator representing a mixed number in its lowest terms.


Imperfections dans mon français To conjugate a verb in l'imparfait, one needs to perform the following steps:

Find the "stem" of the word; this is achieved by omitting the -ons from the nous-conjugated form of the word. For example, vivre is nous vivons; removing -ons from vivons yields viv-.
Take the stem and add an appropriate ending, according to the subject. Here are the endings:

je         -ais
tu         -ais
il/elle    -ait

nous       -ions
vous       -iez
ils/elles  -aient

Objective Given a verb and a subject, output the imperfect form of that verb with respect to the subject. The input format can be in any format convenient to your language. Your submission can either be a program, snippet, or function. (Note that the verb does not have to be a real verb.)

You can assume that the verb is a regular verb, i.e, items like avoir would be treated as an -ir verb, not an irregular one. The only verb you have to quantify as irregular is être; it is conjugated as such:

j'étais
tu étais
il/elle était

nous étions
vous étiez
ils/elles étaient

Here are the conjugations for -er, -re, and -ir verbs in the nous forms

-ER => (e)ons           ; e is added after a 'g'
-RE => ons
-IR => issons

Anything that does not end with such does not have to be handled.

(Note that je merges with the next vowel, if there is one. E.g., je acheter -> j'achetais. h will be considered a vowel for our purposes.)

Example IOs

input: tu vivre
output: tu vivais

input: elles nager
output: elles nageaient

input: je morter
output: je mortais     ; incorrect in real life, but correct for our purposes

input: vous finir
output: vous finissiez

input: il croire
output: il croiait

input: nous jouer
output: nous jouions

Bonuses

-5N bytes for all N extra irregular verb handled.
-10% if you also output every conjugation of the verb in the imperfect tense.

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

Haskell, 366 362 352 bytes

s#v=m++g++d++t
 where
 m|v=="être"="ét"|i/="rio"&&i/="erd"&&i/="eri"=r 2 v|otherwise=r 3 v
 g=if(last m=='g'&&head t/='i')then"e"else""
 d|init i=="ri"="iss"|i=="eri"="y"|otherwise=""
 t|s=="je"||s=="tu"="ais"|elem s["il","elle","on"]="ait"|s=="nous"="ions"|s=="vous"="iez"|s=="ils"||s=="elles"="aient"
 r i=reverse.drop i.reverse
 i=take 3$reverse v

You can compile this in ghci and use it like so "je"#"choisir" to get "choisissais".

This code works with some irregular verbs. It can conjugate croire (je croyais, tu croyais…) or prendre as well as all its derivatives (apprendre, comprendre, etc.).

I couldn't find a short way to conjugate other verbs ending in -ire (such as lire, rire, dire, etc.) or in -dre (such as craindre, soudre, etc.).


Distinct subsets that sum to a given number Write a function that gets as an input a sorted array of positive numbers A, and an additional number n. The Task is to print out all distinct subsets of A, that sum to n.

Example:

Input:
A = [1,2,2,4,4]
n = 9

Output:
[1,2,2,4]
[1,4,4]

Bonus:
-50% if your code doesn't store duplicate subset (the same subset but in different order) intern. The function will not store more than one duplicate subset in memory at a time.

Shortest code in bytes wins.

Pyth, 6

@yE./Q

Try it online

We get all of the subsets of the given list with yE, and then ./Q gets all of the integer partitions (lists of integers that add up to it) of the other input. @ Finds the intersection of the two sets.


Simulate an instant runoff election It's the election! The area which we are in implements the system of voting called instant runoff (sometimes called alternative vote or preferential voting). Each voter orders each candidate from most preferred to least preferred, marking a "1" for their most preferred candidate,
a "2" for their second candidate, and so forth until each candidate is numbered. I'll let this friendly koala explain the rest:

(Image modified from original by Patrick Alexander, used under the CC BY-NC-SA 3.0 AU licence).

If you prefer your instant runoff explanation in text form, there's also the Wikipedia article.

(Note: It's also possible, although unlikely, for there to be two or more candidates with the least votes. In these situations, choose one of them randomly at equal probabilities and eliminate them.)

In this challenge, the first line of input is a list of strings, which are the names of the candidates for the election. In these examples I've used pipe delimited values, although feel free to adjust the input format to suit your language.

The Omitted Anti-neutrino|Placazoa|Alexander the Awesome|Tau Not Two|Semolina Sorcerer

Following that are n lines of input which are also lists of strings, each which represents a single vote. The first entry represents that votes #1 preference, the next the #2 preference, etc. For example:

Alexander the Awesome|Semolina Sorcerer|Tau Not Two|Placazoa|The Omitted Anti-neutrino

would mean that that particular vote has Alexander as their first preference, Semolina Sorcerer as their second, Tau Not Two as their third, etc. You can assume that every vote will contain every candidate, and that there will be no blank or incomplete votes.

Given the votes as input, your program or function should then output the winner of the election. You can find an ungolfed reference implementation in Python 3 here.

Example Inputs and Outputs

Input

Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Portal Butter|Alexander the Awesome|Dionysius|Red Trainmen
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Portal Butter|Red Trainmen|Alexander the Awesome|Dionysius
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Alexander the Awesome|Red Trainmen|Portal Butter|Dionysius
Red Trainmen|Alexander the Awesome|Dionysius|Portal Butter
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Red Trainmen|Dionysius|Portal Butter|Alexander the Awesome
Alexander the Awesome|Dionysius|Red Trainmen|Portal Butter
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Alexander the Awesome|Red Trainmen|Dionysius|Portal Butter

Output

Alexander the Awesome

Input

Depressed Billy|Sighted Citrus|Frosty Fox|Electronic Accident
Frosty Fox|Sighted Citrus|Electronic Accident|Depressed Billy
Frosty Fox|Depressed Billy|Sighted Citrus|Electronic Accident
Depressed Billy|Electronic Accident|Sighted Citrus|Frosty Fox
Depressed Billy|Sighted Citrus|Electronic Accident|Frosty Fox
Depressed Billy|Electronic Accident|Sighted Citrus|Frosty Fox
Electronic Accident|Frosty Fox|Depressed Billy|Sighted Citrus
Sighted Citrus|Frosty Fox|Electronic Accident|Depressed Billy
Frosty Fox|Depressed Billy|Sighted Citrus|Electronic Accident
Sighted Citrus|Electronic Accident|Frosty Fox|Depressed Billy
Frosty Fox|Electronic Accident|Depressed Billy|Sighted Citrus
Sighted Citrus|Frosty Fox|Depressed Billy|Electronic Accident

Output

Sighted Citrus or Frosty Fox (randomly)

Input

You can get the last input set here. It is one of the voting areas of a recent Australian election, and consists of 63 428 votes.

Output

Ross HART

Pyth - 30 bytes
Will refactor it. Infers first line from rest of input.
WgclQ2leKlD.gkhMQ=Q-RhhJKQ;hhJ

Test Suite.


Simulate my keyboard wave light! (The word frame in the following text does not mean an actual frame, it is used as a placeholder for an undefined time unit)
The task
Imagine you have a keyboard layout with only letters like so:
q w e r t y u i o p
 a s d f g h j k l
  z x c v b n m

Whenever you press a key, for example f, the keyboard lights up the keys around it each frame like this (unordered, each line is a separate frame):
F
RTGVCD
YHBXSE
UJNWAZ
IKMQ
OL
P

As you can see, each frame lights up the keys around the ones that were lit previously, but not the ones that have already been lit up before.
After you have determined which keys need to be pressed each frame, you need to visualise them. For each frame, you print out the default keyboard layout (with all of the whitespace), but with the lit up keys uppercased. In our example:
q w e r t y u i o p
 a s d F g h j k l
  z x c v b n m

q w e R T y u i o p
 a s D f G h j k l
  z x C V b n m

q w E r t Y u i o p
 a S d f g H j k l
  z X c v B n m

q W e r t y U i o p
 A s d f g h J k l
  Z x c v b N m

Q w e r t y u I o p
 a s d f g h j K l
  z x c v b n M

q w e r t y u i O p
 a s d f g h j k L
  z x c v b n m

q w e r t y u i o P
 a s d f g h j k l
  z x c v b n m

Rules

Input will be a single letter, you can choose whether it will be capitalised or not.

Output can be either:
a. An array of multiline strings representing each second of the visualised keyboard
b. A single multiline string with each frame of the visualised keyboard separated by at least one newline

You can output a trailing newline or/and the final keyboard visualisation when no keys are lit anymore

Test cases
Input: F
Output:
q w e r t y u i o p
 a s d F g h j k l
  z x c v b n m

q w e R T y u i o p
 a s D f G h j k l
  z x C V b n m

q w E r t Y u i o p
 a S d f g H j k l
  z X c v B n m

q W e r t y U i o p
 A s d f g h J k l
  Z x c v b N m

Q w e r t y u I o p
 a s d f g h j K l
  z x c v b n M

q w e r t y u i O p
 a s d f g h j k L
  z x c v b n m

q w e r t y u i o P
 a s d f g h j k l
  z x c v b n m

Input: Q
Output:

Q w e r t y u i o p
 a s d f g h j k l
  z x c v b n m

q W e r t y u i o p
 A s d f g h j k l
  z x c v b n m

q w E r t y u i o p
 a S d f g h j k l
  Z x c v b n m

q w e R t y u i o p
 a s D f g h j k l
  z X c v b n m

q w e r T y u i o p
 a s d F g h j k l
  z x C v b n m

q w e r t Y u i o p
 a s d f G h j k l
  z x c V b n m

q w e r t y U i o p
 a s d f g H j k l
  z x c v B n m

q w e r t y u I o p
 a s d f g h J k l
  z x c v b N m

q w e r t y u i O p
 a s d f g h j K l
  z x c v b n M

q w e r t y u i o P
 a s d f g h j k L
  z x c v b n m

Input: Z
Output:
q w e r t y u i o p
 a s d f g h j k l
  Z x c v b n m

q w e r t y u i o p
 A S d f g h j k l
  z X c v b n m

Q W E r t y u i o p
 a s D f g h j k l
  z x C v b n m

q w e R t y u i o p
 a s d F g h j k l
  z x c V b n m

q w e r T y u i o p
 a s d f G h j k l
  z x c v B n m

q w e r t Y u i o p
 a s d f g H j k l
  z x c v b N m

q w e r t y U i o p
 a s d f g h J k l
  z x c v b n M

q w e r t y u I o p
 a s d f g h j K l
  z x c v b n m

q w e r t y u i O p
 a s d f g h j k L
  z x c v b n m

q w e r t y u i o P
 a s d f g h j k l
  z x c v b n m

Haskell, 229 bytes

e=zip[0..]
x!y=abs$x-y
k=e["Q W E R T Y U I O P"," A S D F G H J K L","  Z X C V B N M"]
f c=filter(any(<"a").words)[unlines[[[z..]!!sum[32|z>'@',max(2*y!i)(y!i+x!j)/=d*2]|(x,z)<-e m]|(y,m)<-k]|(i,l)<-k,(j,h)<-e l,c==h,d<-[0..9]]

Try it online!
f takes an uppercase char argument and returns a list of multiline strings.
It loops over the keyboard layout looking for (i,j), the position of the given character. When it finds it, for each d<-[0..9] it generates a string (unlines[…]) of the keyboard with all letters not d hex-steps away lowercased. It never takes longer than 10 steps for the wave to leave the keyboard, so this is OK. Finally, strings that don't contain any uppercase letters are filtered away from the result.
I calculate the hex distance between two points on the keyboard as: \$ \max\left(2|y_1-y_2|, |x_1-x_2|+|y_1-y_2|\right)\$. Here are some distances around a point under this metric:
   6666666                                 6 6 6 6
  654444456                               6 4 4 4 6
 65432223456                             6 4 2 2 4 6
6543210123456  --> on staggered grid:   6 4 2 0 2 4 6
 65432223456                             6 4 2 2 4 6
  654444456                               6 4 4 4 6
   6666666                                 6 6 6 6


Trump needs your help to stop the Starman! A man from the stars has come to Earth! Luckily the president of the United States, Donald Trump, has an infinity-sided die. Using this die, he can conjure up a number which you, the mayor of Podunk, must use to determine who should be sent to stop the invader! But be careful, you can only send a limited amount of bytes on the back of your frog!
Given a user input (which will be a positive integer), you must return a string depending on what category the number is in.

If the number is a Fibonacci number, you must output Ness.
If the number is a Lucas number, you must output Lucas.
If the number is both a Lucas number and a Fibonacci number, you must output Travis.
If the number is neither a a Lucas number nor a Fibonacci number, you must output Pippi.

Examples
Here are a bunch of test cases:

1 => Travis
2 => Travis
3 => Travis
4 => Lucas
5 => Ness
6 => Pippi
7 => Lucas
8 => Ness
610 => Ness
722 => Pippi
843 => Lucas

Rules

This is code-golf, the shortest answer in bytes wins.
You program may be a full program or a(n anonymous) function.

Bonuses
There are a couple bonuses that you can use to help your frog get the data to President Trump faster:

For -15 bytes: If the input number is 2016, you must output Trump, as he is at the peak of his presidency.

Julia, 146 142 121 120 bytes

n->split("Pippi Lucas Ness Travis")[2any(isinteger,sqrt([5n^2+4,5n^2-4]))+(n∈[2;[(g=golden)^i+(-g)^-i for i=1:n]])+1]

This creates an unnamed function that returns a boolean. To call it, give it a name, e.g. f=n->....

Ungolfed:

function trump(n::Integer)
    # Determine if n is a Fibonacci number by checking whether
    # 5n^2 ± 4 is a perfect square
    F = any(isinteger, sqrt([5n^2 + 4, 5n^2 - 4]))

    # Determine if n is a Lucas number by generating Lucas
    # numbers and testing for membership
    # golden is a built-in constant containing the golden ratio
    L = n ∈ [2; [golden^i + (-golden)^-i for i = 1:n]]

    # Select the appropriate Earthbound charater using array
    # indexing on a string split into an array on spaces
    return split("Pippi Lucas Ness Travis")[2F+L+1]
end

Fixed an issue and saved 7 bytes thanks to Glen O!


What's the shortest way to define an anonymous recursive function in Octave? I love functional programming in Octave, but it's rather unwieldy in practice. I'm wondering about the shortest way to define an anonymous recursive function.

I have some ideas, but I'm wondering if there is a way to combine these ideas to make them even shorter (or equally short but more versatile). For the sake of this question, let's recursively count down to zero (just to keep the payload as simple as possible).

If my reasoning is correct, none of the variable names I used in the following examples should overlap. The desired function is q(n), which should always return zero. i is used as a counter variable, f is the recursive function which I have called g in the local scope of f.

44 bytes, "inline definition of f"

q=@(n)(f=@(g,i){@()g(g,i-1),i}{~i+1}())(f,n)

44 bytes, "argument list definition of f"

q=@(n,f=@(g,i){@()g(g,i-1),i}{~i+1}())f(f,n)

44 bytes, "separate definition of f"

f=@(i,g){@()g(i-1,g),i}{~i+1}();q=@(n)f(n,f)

41 bytes, "desired function as a return value"

f=@(g)@(n){@()g(g)(n-1),n}{~n+1}();q=f(f)

The current 'winner' is inspired by this answer by flawr. However, given the large range of different ways to do this, perhaps someone can think of an even shorter combination of methods.

The goal is of course to get it below 39 bytes for a "full" function, Try it online!


Find the n-th perfect power! A perfect power is a number of the form \$a^b\$, where \$a>0\$ and \$b>1\$.
For example, \$125\$ is a perfect power because it can be expressed as \$5^3\$.
Goal
Your task is to write  a program/function that finds the \$n\$-th perfect power, given a positive integer \$n\$.
Specs

The first perfect power is \$1\$ (which is \$1^2\$).
Input/output in any reasonable format.
Built-ins are allowed.

Further information

OEIS A001597

Scoring
This is code-golf. Shortest solution in bytes wins.
Testcases
input  output
1      1
2      4
3      8
4      9
5      16
6      25
7      27
8      32
9      36
10     49

Jelly, 11 bytes
µÆE;¬g/’µ#Ṫ

Try it online!.
Background
Every positive integer \$k\$ can be factorized uniquely as the product of powers of the first \$m\$ primes, i.e., \$k=p_1^{\alpha_1}\cdots p_m^{\alpha_m}\$, where \$\alpha_m>0\$.
We have that \$a^b\$ (\$b>1\$) for some positive integer \$a\$ if and only if \$b\$ is a divisor of all exponents \$\alpha_j\$.
Thus, an integer \$k > 1\$ is a perfect power if and only if \$\gcd(α_1, ⋯, α_m) ≠ 1\$.
How it works
µÆE;¬g/’µ#Ṫ  Main link. No arguments.

µ            Make the chain monadic, setting the left argument to 0.
        µ#   Find the first n integers k, greater or equal to 0, for which the
             preceding chain returns a truthy value.
             In the absence of CLAs, n is read implicitly from STDIN.
 ÆE          Compute the exponents of the prime factorization of k.
   ;¬        Append the logical NOT of k, i.e., 0 if k > 0 and 1 otherwise.
             This maps 1 -> [0] and [0] -> [1].
     g/      Reduce the list of exponents by GCD.
             In particular, we achieved that 1 -> 0 and 0 -> 1.
       ’     Decrement; subtract 1 from the GCD.
             This maps 1 to 0 (falsy) and all other integers to a truthy value.
          Ṫ  Tail; extract the last k.


The Government has a Limited Supply of Walls Introduction

Knowledgeable code golfers prepared us for the doomsday flood. Areas at risk were evacuated, and the population moved to high ground.

We underestimated the flood (or perhaps there was a bug in @user12345's code). Some high-ground areas are rapidly approaching sea level. Walls must be erected in order to ensure the survival of the now densely populated encampments. Sadly, the government has a limited supply of walls.

Problem

Our doomsday scenario is described by two numbers on a single line, n and m. Following that line are n lines with m values per line, separated only by a single space. Each value will be one of four characters.

x Impassable. Water cannot flow here. Walls cannot be erected here.
- Unstable. Water can flow through this here. Walls cannot be erected here.
. Stable. Water can flow through here. Walls can be erected here.
o Encampment. Water can flow through here. If it does, everyone dies. Walls cannot be built here.

Water will flow from all edges of the map, unless the edge is impassable or a wall is constructed on the tile. Write a program that can output the minimum number of walls required to protect an encampment.

Example Input

 6 7
 x . . x x x x
 x . . x - - x
 x . x x - - x
 x . o o o - .
 x . o o o - .
 x x x x x x x

Example Output

3

Assumptions

Water only flows orthogonally
Encampments only exist as one orthonagonally contiguous block per scenario
A solution will always exist (although it may require copious amounts of walls)
Encampments cannot be located on an edge, as the scenario would then have no solution
2 < n < 16
2 < m < 16
Input may be provided from stdin, read from "city.txt", or accepted as a single argument

Shortest code wins!

Mathematica, 257 253 chars
d="city.txt"~Import~"Table";g=EdgeAdd[#,∞<->Tr@#&/@Position[VertexDegree@#,2|3]]&@GridGraph@d[[1,{2,1}]];{o,x,s}=Tr/@Position[Join@@d[[2;;]],#]&/@{"o","x","."};Catch@Do[If[Min[GraphDistance[VertexDelete[g,x⋃w],∞,#]&/@o]==∞,Throw@Length@w],{w,Subsets@s}]

Input is read from "city.txt".
Explanation:
Mathematica has many functions to deal with graphs.
First, I read the data from "city.txt".
d="city.txt"~Import~"Table";

Then I construct a grid graph with 'm'*'n' vertices (GridGraph@d[[1,{2,1}]]), and add to it a "vertex at infinity" which is connected to every vertex on the "edges" of the graph. This vertex is where the water flow from.
g=EdgeAdd[#,∞<->Tr@#&/@Position[VertexDegree@#,2|3]]&@GridGraph@d[[1,{2,1}]];

And o, x and s denote the positions of "o", "x" and "." respectively.
{o,x,s}=Tr/@Position[Join@@d[[2;;]],#]&/@{"o","x","."};

Then for any subset w of s (the subsets are sorted by length), I delete the vertices in x and w from g (VertexDelete[g,x⋃w]), and find the length of the shortest path from the "vertex at infinity" to the encampment o. If the length is infinity, then the encampment will be safe. So the length of the first such w is the minimum number of walls required to protect an encampment.
Catch@Do[If[Min[GraphDistance[VertexDelete[g,x⋃w],∞,#]&/@o]==∞,Throw@Length@w],{w,Subsets@s}]


String Bit Manipulation- There and Back Again Your job is to encrypt a string using a number key.

Your program will receive 2 strings: one containing a sequence of characters to encrypt, and another one containing an even amount of digits (1-9, never 0).

The encrypting will work like this:

take the string to be encrypt and decode it to binary (ISO-8859-1)
for every pair of numbers x and y in the number string do:
for every character in the string of zeroes and ones, starting from the first one, if the bit is 0 toggle the xth bit in front of the bit you are reading right now. If the bit is 1, toggle the yth bit in front of the bit you are reading right now. If the bit to be toggled is out of bounds, do not toggle anything.

Other than that:

This is a code golf challenge, shortest code wins. Standard Loopholes apply.

Here's a more graphic explanation of what happens:

inputs: "a", "23"
"a" =BIN> "01100001"
"01100001" //first bit is a 0, get the first number in the key, 2.
 - ^       //toggle the bit 2 steps in front
"01000001" //next bit is 1, get second number in the key, 3.
  -  ^     //toggle the bit 3 steps in front
"01001001" //0 bit, toggle the bit that is 2 steps in front.
   - ^
"01000001" //etc
    - ^
"01000101"
     - ^
"01000111"
      -  ^ //no change, out of bounds.
"01000111"
       -  ^
"01000111"
        -  ^
"01000111" =ASCII> "G"

So: a, 23 = G. Then, running G, 23 should be a because this process is perfectly reversible. To decrypt a string encrypted using key 12438135, reverse the ordering of the pairs, 35814312 and run the encrypted string through a similar program that performs the operations in reverse order (starting at the end, approaching the beginning) using that key. (thanks to Martin Büttner for pointing that out)

Good luck and have fun! (My first challenge, tell me if i missed anything :))

Ruby, 230 191 181 178 175 173 171 159 bytes

i,n=$*
s=i.gsub(/./){|c|"%08b"%c.ord}
n.scan(/(.)(.)/){s.size.times{|i|s[j=i+(s[i]==?0?$1:$2).to_i]&&s[j]=s[j]==?0??1:?0}}
$><<s.gsub(/.{8}/){|c|c.to_i(2).chr}

It's just a very naive implementation of the spec. Input via command-line arguments, output to STDOUT.

# Read ARGV into i and n
i,n = $*
# Turn each character into a string of eight 0s and 1s using a format string.
s = i.gsub(/./){|c|"%08b"%c.ord}
# For each pair of characters in n
n.scan(/(.)(.)/){
    # For each index into s
    s.size.times{|i|
        # Determine the index that is to be toggled. $1 and $2 refer to the captures
        # of /(.)(.)/.
        j=i+(s[i]==?0?$1:$2).to_i
        # Using short-circuiting, toggle s[j] if it isn't nil.
        s[j]&&s[j]=s[j]==?0??1:?0
    }
}
# Convert each group of 8 characters back to a single character and print
$><<s.gsub(/.{8}/){|c|c.to_i(2).chr}


Weakened Binary Walls Inspired by Create a binary wall

Given a list of positive integers, we can write them out all above each other like so, for [2, 6, 9, 4] as an example:

0010
0110
1001
0100

We can imagine this as a wall:

..#.
.##.
#..#
.#..

However, this is a very weak wall, and it has collapsed! Each 1 (#) falls down until it hits the "ground" or another 1 (#). The 0s (.s) are present in spots left by moved 1s.

This becomes the following:

....
....
.##.
####

Which translates back to:

0000
0000
0110
1111

Which, as a list of numbers, is [0, 0, 6, 15].

Another test case

[10, 17, 19, 23]

This becomes:

01010
10001
10011
10111

which becomes:

00000
10011
10011
11111

translating back to:

[0, 19, 19, 31]

Challenge

Given a list of positive integers, apply this transformation to the list. Input/Output as lists of positive integers in any reasonable format. Standard loopholes apply.

This is a code-golf, so the shortest answer in bytes wins!

MATL, 4 bytes
BSXB

Try it at MATL Online
Explanation
    % Implicitly grab input as an array
    %   STACK: [10, 17, 19, 23]
B   % Convert each element to binary where each decimal number results in a row
    %   STACK: [0 1 0 1 0;
    %           1 0 0 0 1;
    %           1 0 0 1 1;
    %           1 0 1 1 1]
S   % Sort each column, placing all of the 1's at the bottom of each column
    %   STACK: [0 0 0 0 0;
    %           1 0 0 1 1;
    %           1 0 0 1 1;
    %           1 1 1 1 1]
XB  % Convert each row from its binary representation to its decimal number
    %   STACK: [0, 19, 19, 31]
    % Implicitly display the result


Happy Birthday, let's have some cake! It's my friend's birthday soon and since he is a programmer and ASCII art lover, I thought I'd make him some ASCII cake!

Sadly, I keep forgetting his current age, so I would like to have a program for my ASCII oven, that bakes a cake with a specified number of candles, so I don't have to do it myself again if I am wrong with his age.

ASCII ovens only have limited memory and storage capacity, so it should use the fewest bytes possible.

Your Task:

Write a program that outputs a birthday cake to the console, with as many candles as the input specifies.

Cake requirements are:

It has to have a border, built up of horizontal - and vertical | lines, and vertices +.
Atleast 5 characters wide (including cake border |)
Atleast 5 characters high (including cake border -)
There has to be a whitespace character  between the cake border and the first candle-base (not the flame), on each side, except if there is a flame in that space. A flame or candle-base should not be able to overlap the cake borders.
The maximum width of the cake is 9 characters, so there is a maximum of 5 candles per row.
Since we don't want our cake to be 2-dimensional, it has to be an extra 2 rows high, to give it some volume. Add another border at the bottom and connect the vertices with the ones above them, again using the ASCII characters from above (-, | and +).

Candle requirements are:

Consists of the base | and the flame *, with the flame stacked on top of the base.
Candles may not be directly adjacent to eachother, except diagonally.
Candles are placed left-to-right, then top-to-bottom, with 5 in one line at maximum.
(Note: If there were 5 candles in the previous row, the next row can't possibly have 5 aswell, since then they would be adjacent.)

Additional notes:

The cake width depends on the number of candles in the first row, but it has to be a minimum of 5 characters and a maximum of 9 characters wide.
The candles are filled starting in the top-most row, going left to right. Once one row if full the next one should start in the row below the first one.

Input:

You may accept a number in (reasonable) format you like.

For this challenge you may assume that the number is between 0 and 231 (not including 0), even though I don't acknowledge someone who is this old.

Output:

You can either return a string or directly write the resulting cake into the output console.

Rules:

Standard loopholes are forbidden.
This is code-golf, so shortest code in bytes, in any language, wins.

Examples:

Input: 8

+-----------+
| * * * * * |
| |*|*|*| | |
|  | | |    |
|           |
+-----------+
|           |
+-----------+

Input: 2

+-----+
| * * |
| | | |
|     |
+-----+
|     |
+-----+

Input: 12

+-----------+
| * * * * * |
| |*|*|*|*| |
| *|*|*| |  |
| | | |     |
|           |
+-----------+
|           |
+-----------+

Good luck!

Charcoal, 76 71 70 66 46 bytes

ＮθＦ=+Ｂ⁺³⌊⟦χ⁺θθ⟧÷⁺℅ι⁺θθ⁹↘↘Ｆθ«↑|*¶¶¿‹⁶﹪⁺ιι⁹«Ｍ⁹←↓

Try it online! Link is to verbose version of code. Edit: Saved 1 byte thanks to @ASCII_Only. Saved a massive 20 bytes by discovering a neat way of drawing the candles. Explanation:

ＮθＦ=+Ｂ⁺³⌊⟦χ⁺θθ⟧÷⁺℅ι⁺θθ⁹

Calculate the size both of the whole cake including extra volume and just the top of the cake so that they can be drawn. ((= = ASCII 61) = (+ = ASCII 43) + 9 * 2 for the extra volume.)

↘↘Ｆθ«

Move the cursor to the first row of 5 candles. Loop through each candle.

↑|*¶¶

Print a candle and move right two characters for the next candle.

¿‹⁶﹪⁺ιι⁹«

However after the (zero-indexed) 4th, 8th, 13th, 17th, 22nd etc. candles (that are at the end of a row),

Ｍ⁹←↓

move the cursor to the first candle on the next row. This works on both odd and even rows!


A simple DNA simulator Your code is going to generate a very simple ASCII-art representation of DNA, forever. It will take two numbers as input in any format you want: as a list, as arguments to a function, on stdin, etc.

A floating-point interval I in seconds between 0.0 and 1.0 (inclusive)
A zoom level Z as an integer from 1 to 64 (inclusive)

Your code will print one line to stdout or its equivalent every I seconds, producing an infinite output that looks something like this (for zoom level 4):

    A
 T-----a
G-------c
 G-----c
    g
 t-----A
a-------T
 c-----G
    T
 A-----t
C-------g
...

Specifically, our representation of DNA is a pair of sine waves connected by hyphens, one consisting of the characters a, c, g, and t, the other of the characters A, C, G, and T. If x is the 0-indexed number of the line we're currently printing, the 0-based position of the character in the lowercase wave is given by (sin(πx / Z) + 1) * Z, and in the uppercase wave is given by (-sin(πx / Z) + 1) * Z, both rounded (not floored) to the nearest integer. Further details:

In cases where the two waves overlap, you need to alternate which wave is in the front, starting with the uppercase wave. (Starting with the lowercase wave would give us a double helix that does not exist!)
Ignoring case, A always pairs with T and C always pairs with G, as in real DNA. The pairs themselves should be randomly chosen with a uniform distribution over the four possibilities. It does not matter if the choice of pairs is the same or different on successive runs of your code. The statistical quality of your random choices is not an issue as long as the output has no obvious pattern and a period at least in the billions (flawed PRNGs like RANDU are fine.)
You must either have no trailing spaces or pad every line to the maximum position of the waves at that zoom level (in the example above, nine characters.) Zoom level 1 may have one optional additional trailing space for mathematical reasons.

Because DNA is small, your code will need to be as short as possible.

More examples:

Zoom level 8:

        T
     C-----g
  A-----------t
 C-------------g
G---------------c
 T-------------a
  T-----------a
     T-----a
        c
     g-----C
  t-----------A
 g-------------C
a---------------T
...

Zoom level 2:

  A
T---a
  c
g---C
  G
A---t
  c
a---T
...

Zoom level 1 (note the leading space):

 G
 a
 C
 t
...

Ruby, Rev B 171 161 bytes

Fixing the output for z=1 cost 10 bytes. It's a special case: the helix is really 3 characters wide if you looked at it at 90 degrees, but as we look at it at 0 degrees it looks only 1 character wide. zero leading spaces on z=1 no longer required

Some savings by eliminating brackets and by multiplying y.abs by 2 before truncation when calculating the number of - characters needed.

Finally, I avoided the include Math (required for sin and PI) by using complex number arithmetic with powers of the number i. The imaginary part of the complex number is equivalent to sin x, except that it repeats with period 4 instead of period 2*PI. Saving for this change was either 1 or 0 bytes.

->z,i{x=0
loop{y=z*("i".to_c**x).imag
s=(?-*(y.abs*2)).center z*2+1
s[z-y+0.5]='TGAC'[r=rand(4)]
x!=0&&s[z+y+0.5]='actg'[r]
puts s
sleep i
x+=2.0/z
x>3.99&&x=0}}

Ruby, Rev A 165 bytes

This is way longer than expected. There are a few potential golfing opportunities to be explored.

include Math
->z,i{x=0
loop{y=z*sin(x)
s=('--'*(y.abs+h=0.5)).center(z*2+1)
s[z+h-y]='TGAC'[r=rand(4)]
x!=0&&s[z+h+y]='actg'[r]
puts s
sleep(i)
x+=PI/z
x>6.28&&x=0}}

Commented in test program

include Math
f=->z,i{x=0
  loop{y=z*sin(x)
    s=('--'*(y.abs+h=0.5)).center(z*2+1)  #make a space-padded string of z*2+1 characters, containing enough - signs
    s[z+h-y]='TGAC'[r=rand(4)]            #insert random capital letter, saving index in r
    x!=0&&s[z+h+y]='actg'[r]              #insert small letter. This will normally go on top of the capital as it is done second, but supress for x=0 to make helix
    puts s
    sleep(i)
    x+=PI/z                               #increment x
    x>6.28&&x=0                           #reset x if equal to 2*PI (this proofs against loss of floating point precision, making correct output truly infinite.)
  }
}

Z=gets.to_i
I=gets.to_f
f[Z,I]


What golfing languages are better suited as an object for genetic programming? I see GolfScript, Pyth, CJam and similar languages can make compex-ish algorithms in few bytes. This terseness makes think about genetic programming applications (using said languaes as the thing being mutated).

I assume that to make a good GP language, it should have following characteristics:

Programs are typically short;
Random bytes should have high change of being a well-formed program;
Programs should compile and run fast;
Typical programs should not fall into endless loop often, or such loops should be early-detectable in most cases;
Contatenations, extraction of substrings, small modifications should often lead to something related to the original program;
Program should be easy to put in a sandbox (i.e. should not crash the interpreter);
Be turing-complete or near it.

How much languages typically used for golfing suit for genetic programming?

I would be surprised if any golfing languages were appropriate for genetic programming. Pyth, at least, is very unlikely to form a valid program with random bytes, and I believe the same is true of most golfing languages. This, if nothing else, probably invalidates them as genetic programming languages.


Is this a Smith number? Challenge description

A Smith number is a composite number whose sum of digits is equal to the sum of sums of digits of its prime factors. Given an integer N, determine if it's a Smith number or not.

The first few Smith numbers are 4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438 (sequence A006753 in OEIS).

Sample input / output

18: False (sum of digits: 1 + 8 = 9; factors: 2, 3, 3; sum of digits of factors: 2 + 3 + 3 = 8)
22: True
13: False (meets the digit requirement, but is prime)
666: True (sum of digits: 6 + 6 + 6 = 18; factors: 2, 3, 3, 37; sum of digits of factors: 2 + 3 + 3 + 3 + 7 = 18)
-265: False (negative numbers can't be composite)
0: False (not composite)
1: False (not composite)
4937775: True

Notes

Your code can be a function (method) or a full working program,
Instead of words like True and False, you can use any truthy and falsy values, as long as it's clear what they are,
This is a code-golf challenge, so make your code as short as possible!

Python 2, 122 115 110 106 bytes

n=m=input()
s=0
for d in range(2,n):
 while n%d<1:n/=d;s+=sum(map(int,`d`))
print n<m>s==sum(map(int,`m`))

Saved 4 bytes thanks to Dennis

Try it on ideone.com

Explanation

Reads a number on stdin and outputs True if the number is a Smith number or False if it is not.

n=m=input()                  # stores the number to be checked in n and in m
s=0                          # initializes s, the sum of the sums of digits of prime factors, to 0
for d in range(2,n):         # checks all numbers from 2 to n for prime factors
 while n%d<1:                # while n is divisible by d
                             #   (to include the same prime factor more than once)
  n/=d                       # divide n by d
  s+=sum(map(int,`d`))       # add the sum of the digits of d to s
print                        # print the result: "True" if and only if
      n<m                    #   n was divided at least once, i.e. n is not prime
      >                      #   and m>s (always true) and
      s==sum(map(int,`m`))   #   s is equal to the sum of digits of m (the input)


Outsmart the boffins at New Scientist (string rotation) The brainiacs at New Scientist tweeted this morning that "The word STABLE has the neat property that you can cycle the first letter to the end to make a new word: TABLES. And you can do it again to make ABLEST." (https://twitter.com/newscientist/status/1379751396271124480)
This is of course correct. It is not, however, unique. Let us demonstrate that we can use computational force to match their linguistic cleverness.
You are to write a program that generates two sets of outputs based on the dictionary words revealed when rotating the letters of another dictionary word. Using the dictionary at https://gist.githubusercontent.com/wchargin/8927565/raw/d9783627c731268fb2935a731a618aa8e95cf465/words,

find all the dictionary words with more than two characters for which every possible rotation yields another dictionary word. Show only one example of each rotation set (so, for example, show only one of "car", "arc", and "rca").
find the words for which the largest number of valid rotations exist. You should find multiple words that tie with the same number of valid rotations. As above, show only one member of each set.

Additional rules:

You can assume that the dictionary has been downloaded outside your code, and can be passed to your code as input or in a variable.

If you need to process the word list to put it in a format more
natural for your programming language (a list for example), you may
exclude this code from your byte count. However this process should
not remove any words; any bytes associated with, for example,
removing two-letter and one-letter words from the dictionary must be
included in your byte total.

Anything in the words list counts as a word, even if we know it's
really an acronym, or contains punctuation marks, or is not English (e.g. "AOL" or "Abdul's"). Treat all characters as letters.

Treat all letters as identically cased (so "India" and "india" are
the same, and "eAt" is a valid word).

No shortcuts based on already knowing the answer, or knowing the maximum number of rotations. Your code needs to actually solve for that.

Using these rules and some ungolfed Wolfram Language, I found four completely rotateable words and 15 words tied at the level of maximum rotateability. This is a code golf challenge, and I imagine it won't be hard to do it more concisely than I did. I plan to call out any particularly creative solutions as well, regardless of length.
--
Intended output (assuming I coded it correctly)
completely rotatable words: aol, arc, asp, eat
(each of these words can be presented with the letters in any rotation)
maximum rotatable words: all of the words above, plus
ablest, alan, ales, anal, ankh, aver, emit, ernst, errant, evan, evil
(each of this latter group also has two valid rotations)

Python 3, 269 266 bytes

def f(a,m=0,b=[],c=[]):
 a=[k.lower()for k in a]
 while a:
  w,k,u=a[0],[],1
  for i in range(len(w)):
   x=w[i:]+w[:i]
   u,k=x in a and(u,k+[x])or(0,k)
  p=len(k)
  for j in{*k}:a.remove(j)
  if u and len(w)>2:c+=[w]
  if p==m:b+=[w]
  if p>m:m,b=p,[w]
 return b,c

Try it online!
Takes a list of words as input. First convert all words to lowercase, then for each word check all it's rotations and if they are valid, remove them from the list. Outputs two lists containing maximum rotatable words and completely rotatable words respectively.
Needless to say this is not optimal at all and takes several minutes to execute for the provided input.
Output I got for the given dictionary: (['aol', 'alan', 'alar', 'ernst', 'evan', 'hank', 'lesa', 'levi', 'rca', 'terran', 'vera', 'ablest', 'asp', 'ate', 'emit'], ['aol', 'rca', 'asp', 'ate'])
-3 bytes thanks to pxeger


What have I got in my pocket? Synopsis: Find characters that are enclosed by MYPOCKET.

Example Input

MYPHEIF
YFOCKVH
MBNDEIF
TEUFTMY
ESNDUWP
KBOVUVO
CENWFKC
OPYMTEB

Example Output

F
BND
EUF
SNDUW
BOVUV
ENWF

Huh? How did we get that as an output? The "pocket" can sometimes be difficult to see. This will make it clearer:

MYPHEIF
YFOCKVH
MBNDEIF
TEUFTMY
ESNDUWP
KBOVUVO
CENWFKC
OPYMTEB

The letters in bold indicate a ring of characters connected orthogonally to each other consisting of the string MYPOCKET repeated over and over again. Your program should output the characters that are within that ring.

Notes:

There will only be one "pocket".
Trailing new lines or spaces after lines are allowed.
The rest of the grid may also contain characters from MYPOCKET, but not in a way that makes the shape of the ring ambiguous.
The M is not always in the top-right corner.
The "pocket" can move in either a clockwise or a counter-clockwise direction.
The "pocket" won't move in diagonal directions -- that is, each letter is connected left, right, up, or down to the next.

Here's another input you can test your program with.

Example Input

EKCYMOPD
KCOPHAYM
EKNDSEST
JETHACKE
KRMYPOBN

Example Output

  HA
NDSES
 HA

Python 2.7 571 542 509

import sys
o,l,v,k,w="MYPOCKET",[list(e)for e in sys.stdin],[],enumerate,len
def f(z,q,t):
 for r,c in(z,q+1),(z,q-1),(z+1,q),(z-1,q):
  if w(l)>r>=0 and 0<=c<w(l[r])and o[t]==l[r][c]:
    v.append((r,c))
    if f(r,c,(t+1)%w(o)):return 1
    else:v.pop()
 if z==1 and(0,q)in v or z==0 and(z,q+1)in v:return 1
for i,x in k(l[0]):
 v=[(0,i)]
 if x==o[0]and f(0,i,1):break
for i in range(1,w(l)-1):b=[y for x,y in sorted(v)if x==i];print"".join(["".join(e)if w(e)>0 else" "for e in[l[i][b[j-1]+1:y]for j,y in k(b)][1:]])

Works as a program(banking on a recursive function) and accepting input from stdin.
Demo here.Testing it (ex1.txt and ex2.txt are the examples from the question)-

$ python pockets.py < ex1.txt
F
BND
EUF
SNDUW
BOVUV
ENWF
$ python pockets.py < ex2.txt
  HA
NDSES
 HA

Ungolfed version with comments -

s="""
EKCYMOPD
KCOPHAYM
EKNDSEST
JETHACKE
KRMYPOBN
"""
li2=[list(e.strip()) for e in s.split("\n") if e.strip()!='']
buf=[]
def find_precious(row, col, c_ind):
    for r,c in[(row,col+1),(row,col-1),(row+1,col),(row-1,col)]:
        if len(li2)>r>=0 and 0<=c<len(li2[r]) and seq[c_ind]==li2[r][c]:
            if (r,c)in buf:return True
            buf.append((r,c))
            if find_precious(r,c,(c_ind+1)%len(seq)):return True
            else:buf.pop()
    if row==1 and (row-1,col) in buf or row==0 and (row,col+1) in buf:return True
    return False

for i,x in enumerate(li2[0]):
    if x==seq[0]:
        buf=[(0,i)]
        if find_precious(0,i,1):break
if len(buf)==1:
    exit("Failed")

#Calculate the middle men
for i in range(1,len(li2)-1):
    b=[y for x,y in sorted(buf)if x==i]
    print "".join(["".join(e)for e in [li2[i][b[j-1]+1:y]for j,y in enumerate(b)][1:]if len(e)>0])

Let me know, if I did something stupid or something can be done better.
I know it's looong, but it's the best I could do :P


Build a twisted "Hello world!" Your job is quite simple, write a program that prints Hello, world!, that when twisted creates a program that prints Twister!.

How strings are twisted

The twisting algorithm is very simple. Each column is shifted down by its index (col 0 moves down 0, col 1 moves 1, ...). The column shift wraps to the top. It kinda looks like this:

a
ba
cba
----
 cba
  cb
   c

With everything under the line wrapping to the top. Real example:

Original:
\\\\\\\\\\\\
............
............
............

Twisted:
\...\...\...
.\...\...\..
..\...\...\.
...\...\...\

(Further examples and a twisters in your favorite language are here)

Scoring

Your program must be a padded rectangle. This is code-golf so lowest byte count wins!

Rules

Your first program must print Hello, world!. Only one trailing newline is allowed.
Your first and second programs must be in the same language.
Your second program must print Twister!. Only one trailing newline is allowed.
Your program must have at least 2 rows and 2 columns.

Python 2, 59 bytes
print "  Hello, world!"[ 2::]
#rint "T w i s t e r !"[ ::2]

Twisted:
print "T weils,twerrd!"[ ::2]
#rint "  H l o   o l !"[ 2::]

Basically, puts the Twister! data in the odd indices of the string and then changes from removing the first two (padding) characters to removing every other character instead.


Length of Longest Non-Repeating Substring Your task is to take as input a single string (or list of characters, list of code points, etc.) and return the length of the longest substring with no character appearing more than once.
Aside: This challenge is similar to Longest Non-Repeating Substring, but without the source restriction ranking submissions by their own longest non-repeating substring.

Assumptions

You may assume that the input contains only lowercase letters and is non-empty (ie. the input will match the regex (a-z)+).

This challenge will use the following definition for substring: "A contiguous sequence of characters contained in the input string"

By "non-repeating" I mean that no letter of the substring is repeated more than once

Examples
If the input is abcdefgabc then the longest substrings with no repeating characters are abcdefg and bcdefga (their positions in the string are [abcdefg]abc and a[bcdefga]bc). The length of these substrings is 7, so the output would be 7.
If the input is abadac then the longest substrings with no repeating characters are bad (a[bad]ac) and dac (aba[dac]) so the output is 3.
If the input is aaaaaa then the longest substring with no repeating characters is a so the output is 1.
If the input is abecdeababcabaa then the longest substrings with no repeating characters are abecd ([abecd]eababcabaa)
and cdeab (abe[cdeab]abcabaa). The output is thus 5.
Test Cases
abcdefgabc -> 7
aaaaaa -> 1
abecdeababcabaa -> 5
abadac -> 3
abababab -> 2
helloworld -> 5
longest -> 7
nonrepeating -> 7
substring -> 8
herring -> 4
abracadabra -> 4
codegolf -> 6
abczyoxpicdabcde -> 10

Scoring
This is code-golf. Shortest answer in bytes for each language wins

Jelly, 6 bytes
ẆQƑƇṪL

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


First and last prime numbers with prime digits of range Challenge

For a given positive integers range, find the first and last prime number entirely composed of prime number digits, exceptionally including 0 (for the digits, a range of 0-2 should output 2-2). The range is inclusive. If no number is found, the expected output is 0. If there is only one such number, the expected output is that number twice.

Examples

For the range 1–100, the first prime number is 2 and the last is 73 (7 and 3 are prime numbers).
For the range 70–80, the first prime number is 73 and the last is also 73 (Since there is only one correct number in the given range, we return it twice).
For the range 190–200, there is no correct answer, so you return 0.
For the range 2000-2100, the first prime number is 2003 and the last is 2053 (we omit the digit 0, but all the other digits are prime)

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

All standard loopholes apply.

Input

You are free to accept two integers as input however you may see fit, stack, function argument(s), CLI argument, stdin.
You must only receive two integers.

Output

You must either return the result (a tuple, an array, multi-return if your language supports it), leave it on the stack, or print it (in this case, they must be separated somehow).
The order of the outputs is irrelevant.
You are allowed leading/trailing brackets and newlines.
You must return two numbers, if there is an answer, even if they are the same.
You must return 0 if there is no answer.

Python 2, 123 bytes

def f(a,b):r=[i for i in range(a,b+1)if(set(`i`)<=set('02357'))>any(i%k<1for k in range(3,i))];return len(r)and(r[0],r[-1])

Try it online!


Number in overlapping range You are given two integers between lets say 1 and 12, one and two
and a integer between lets say 0 and 4 which is called range.  The challange is to decide if one is inside or equal the range from two ± range.   The range is restarting with 1 after 12 and vise versa.

For example, if one = 2, two = 11 and range = 3, the result is true, as one is the the range [8, 9, 10, 11, 12, 1, 2].

The input has to be 3 seperated integers, the order doesn't matter. Input via string with seperators possible. But the Input has to consist of numbers reading as '10' and not 'A' e.g.

Test cases:

one=7  two=6  range=0   result=false
one=5  two=6  range=1   result=true
one=8  two=11 range=3   result=true
one=1  two=11 range=3   result=true
one=2  two=10 range=3   result=false
one=11 two=1  range=2   result=true
one=6  two=1  range=4   result=false
one=12 two=1  range=3   result=true

Shortest valid answer in bytes wins.

Jelly, 10 8 10 bytes

ŒR’+%12‘Ɠe

Try it online!

Saved 2 bytes thanks to Mr. Xcoder

+2 bytes due a bug if one = 12

I believe this meets the criteria. Takes one from STDIN, range as left argument and two as right argument


Animate Adve the Adventurer The challenge

Your task is to animate Adve the Adventurer moving through a creepy (i.e. Halloween) maze. Adve is a •; he's character fluid, though, so he does not mind being represented by a different character.

To animate Adve, you print out each frame; a frame is the map with his current location in it. Adve moves one space forward every turn and never backtracks. He starts in the first row and ends in the last.

Input

Any reasonable format like a string with a delimiter or string array. You can assume the input will be a map greater than 3*3, containing only one possible path. The only characters present will be # and .

Output

The frames.

Example maze (ok... labyrinth)

Here is a map without Adve in it; the first and last frames are this empty map (this map is 9x15):

### #####
##  #####
## ######
##      #
####### #
#   ### #
# # #   #
# #   ###
# #######
#    ####
#### ####
####  ###
##### ###
##### ###
##### ###

This is code-golf, so shortest code in bytes wins!

The exact output for this can be found here (37 frames).

This is code-golf, so shortest code in bytes wins!

Perl, 84 bytes
Thanks @Ton Hospel for guiding me to the right direction to golf out around 30 bytes!
Bytecount includes 82 bytes of code and -0p flags.
/.*/;say y/A/ /r;s/&(.{@{+}})? /A$1&/s||s/ (.{@{+}})?&/&$1A/s||s/ /&/?redo:y;A&;

Note that there are two final spaces, and no final newline (it won't work otherwise).
Takes the maze as input as outputs all the needed frames for Adve to get out of it. Note that Adve is a & rather than a •, since the latter isn't utf8 (and perl doesn't use utf8 by default). Run it with -0pE flags :
perl -0pE '/.*/;say y/A/ /r;s/&(.{@{+}})? /A$1&/s||s/ (.{@{+}})?&/&$1A/s||s/ /&/?redo:y;A&;  ' <<< "### #####
##  #####
## ######
##      #
####### #
#   ### #
# # #   #
# #   ###
# #######
#    ####
#### ####
####  ###
##### ###
##### ###"

Just for the eyes, I also made this animated version, that is a little bit longer, but will clear the terminal between each print and sleep 0.15 sec, so it will look like Adve is actually moving :
perl -0nE 'system(clear);/.*/;say y/A/ /r;select($,,$,,$,,0.15);s/&(.{@{+}})? /A$1&/s||s/ (.{@{+}})?&/&$1A/s||s/ /&/?redo:say"\e[H",y/A&/  /r' <<< "### #####
##  #####
## ######
##      #
####### #
#   ### #
# # #   #
# #   ###
# #######
#    ####
#### ####
####  ###
##### ###
##### ###"


Help me do my washing Help! My Completely Automated Lights From Darks Separator V3001.01 broke! :(
Guidelines

Task
Write a program that will take an input of an array (or a list in some languages) of any amount of strings that are either the letter L or the letter  D (representing lights or darks) and output an array that contains two arrays, one with all the L's, and one with all the D's.

Rules

It's code golf so the shortest answer in bytes wins
Input will only ever contain capitals
There must be the same number of L's in the output as there is in the input, same goes for the D's
The input may only have one element (or maybe even zero elements)
If one or both of the output arrays contain no elements, output an empty list (in some languages this may mean you need to output a string)
Always have the first array be the array of L's

Example output:
["L","D","L","D","D"] -> [["L","L"],["D","D","D"]]
["L","L","L"] -> [["L","L","L"],[]]
["D","D"] -> [[],["D","D"]]
[] -> [[],[]]

Python 3, 37 bytes

lambda a:[[c]*a.count(c)for c in"LD"]

Try it online!


Calculating Parabolic Curves in 3D Space Task

Write a program or function that will determine if a point in 3D space lies on a 2D parabolic curve.

Input

3 points in 3D space

vertex of a 2D parabolic curve
arbitrary point on the curve
arbitrary point in space

Input may be taken in any form (string, array, etc.) provided no other data is passed.

You may assume

the axis of a parabola will be parallel to the z axis
the vertex of a parabola has the maximal z value
parabolae will never degenerate
point values will be whole numbers that are ≥ -100 and ≤ 100

Output

A truthy/falsey value representing whether the third point given lies on the parabolic curve of the first two points.

Examples

Input:

(2, 1, 3)
(1, 0, 1)
(4, 3, -5)

Output:

1

Input:

(16, 7, -4)
(-5, 1, -7)
(20, 6, -4)

Output:

0

Walkthrough (Example #1)

Find a third point on the curve. To do this, mirror the arbitrary point (on the curve) over the vertex. Here is a visual (each blue line is √6 units):

Find the parabolic curve between the three. This is easiest on a 2D plane. Here is the 3D graph, translated to a 2D graph (each blue line is √6 units):

Graph the third given point and solve.

Jelly, 13 11 bytes
_÷/µḢ²=A;$P

The input format is a bit strange; it takes P1 as the second argument, and (P3,P2) as the first argument, where each point is expressed in the form ((x+yj),z).
We first normalize the points so that the vertex is on the origin, and then make sure that P1 and P2 are on the same line, and also that the ratio of their z distances is equal to the ratio of their x distances.
_÷/             Helper link. Inputs: (P3,P2) on left, P1 on right.
_                  Subtract right from left. (P3-P1,P2-P1).
 ÷/                Fold division. (P3-P1)/(P2-P1). P2-P1 is nonzero in both x+yi and z.
   µ               Push the chain onto the stack, and start a new monadic link.
    Ḣ²=A;$P     Hook; main link. Calculates whether w² = a and a is nonnegative.
                Input: The result of the helper link. Call it [w,a].
    Ḣ²              Pop w and square it. Now the list is [a].
       A,$          Concatenate a to its absolute value.
      =             Fork; is w equal to [a,abs(a)]? Returns 2 element list of 0 or 1
          P         Product; that is, true if w was equal to both a and abs(a).

Try it here.


Rectangular difference In this challenge, you are given two overlapping rectangles, and you need to calculate the rectangles created by removing one from the other.
For example, if you remove the red rectangle from the black one:

You end up with one of the following two rectangle sets:

You'll also need to handle the following:

To be more explicit:

You will input the coordinates of two rectangles, A and B.
You need to output the fewest non-overlapping rectangles that cover all of the area of A without B.  Any possible covering is allowed
Rectangular coordinates are passed as 4 integers.  You can pass them in two pairs (representing the two corner points), or as a tuple/list of 4 integers.  Your inputs and outputs need to be consistent.
A and B will not necessarily overlap or touch, and each will have an area of at least 1

Test cases:
[(0 0) (5 5)] [(3 4) (8 7)]   -> [(0 0) (5 4)] [(0 4) (3 5)] # or [(0 0) (3 5)] [(3 0) (5 4)]
[(2 4) (10 11)] [(5 5) (6 6)]  -> [(2 4) (10 5)] [(2 5) (5 6)] [(6 5) (10 6)] [(2 6) (10 11)]    #Other sets of 4 rectangles are possible
[(3 3) (8 8)] [(0 1) (10 8)]   ->    #No rectangles should be output
[(0 0) (5 5)] [(1 1) (10 2)]   -> [(0 0) (1 5)] [(1 0) (2 1)] [(2 0) (5 5)]  #Other sets of 3 rectangles are possible
[(1 5) (7 8)] [(0 0) (1 10)]   -> [(1 5) (7 8)]  #Only possible output
[(4 1) (10 9)] [(2 5) (20 7)]   -> [(4 1) (10 5)] [(4 7) (10 9)]  #Only possible output
[(1 1) (8 8)] [(0 6) (9 9)]     -> [(1 1) (8 6)]   #Only possible output

This is a code-golf, so make your code as short as possible!

Python 2, 375 360 345 343 bytes

from itertools import*;P=product
def f(S,M):(l,t),(r,b)=S;(L,T),(R,B)=M;u,v,x,y=(L>=r)+(l<L),(T>=b)+(t<T),(R>=r)+(l<R),(B>=b)+(t<B);return[S]if v==y!=1or u==x!=1else[list(p(p(*zip(*(S+M))),repeat=2))[[43,197,6,199,9,231,142,229,53,189,134,181][int(i,36)]]for i in '38,491,258,2058,8,4B,28,208,7,41,27,461,,4,2,4A'.split(',')[u+2*v+4*x+8*y-12]]

Try it online!

EDITS: -15 from suggestions from @notjagan; another -15 by re-encoding the array of solution rectangles to int36 format and a short lookup table; another -2 by replacing product with p as per @musicman.

A function that takes two rectangles, each rect being a tuple of ((left,top), (right,bottom)); returns a list of the resulting rectangles.

The basic strategy:

     |     |
 0,0 | 1,0 | 2,0
-----A-----+-----
     |     |
 0,1 | 1,1 | 2,1
-----+-----B-----
     |     |
 0,2 | 1,2 | 2,2
     |     |

In the above diagram, the points A and B are the upper left and lower right, respectively, of the 'Source' rectangle (the first rect).

We find the placement of each of the the upper left (u,v) and lower right (x,y) of the 'Mask' rectangle in that grid.

If both these points are in the first or last column; or first or last row; then there is no overlap; and we can return just the Source rect.

Otherwise, there are 16 cases remaining; for example, the OP's first example is the case we can label (1,1),(2,2). Each case can be mapped to a set of resulting rectangles whose corners are always coordinates with horizontal values in either Source rectangles left,right, or the Mask rectangles left,right; and similarly for the vertical values, the Source's top,bottom or the masks.

For example, for the (1,1),(2,2) case, the rectangles would be ((l,t),(T,r)) and ((l,T),(R,b)), where l,t,r,b and L,T,R,B are the left, top, right and bottom of the Source and Mask rectangles, respectively.

So we can create a lookup table that maps the coordinates to the set of all such possible combinations (which is what the product(product(*zip(*))) bit is about) to a set of rectangles that should be provided for each of the cases (which, after some golfy-decompression, is what the rest of the list stuff is about).