On the Subject of Memory This challenge is from a game called Keep Talking And Nobody Explodes.
Memory is a fragile thing but so is everything else when a bomb goes off, so pay attention! – from the manual
The Objective
A number from 1–4 is given as the "display", along with scrambled numbers 1–4 as the "buttons."
The output must be the label of the correct "button." Repeat this process 5 times.
The Format
The input format must be:
<display #> <buttons #>

Repeated 5 times. As long as the numbers are distinguishable and the <display #> is dedicated separately, the input format and type don't matter. For any input that doesn't fit this format, the entire challenge falls in don't care situation.
The output format and type don't matter as long as the numbers are distinguishable.
Which button to press
Pressing a button means to output the label of the button.
The buttons are indexed from left to right, and are 1-indexed.
For the 1st line:
If the display is 1, press the button in the second position.
If the display is 2, press the button in the second position.
If the display is 3, press the button in the third position.
If the display is 4, press the button in the fourth position.
For the 2nd line:
If the display is 1, press the button labeled “4”.
If the display is 2, press the button in the same position as you pressed in line #1.
If the display is 3, press the button in the first position.
If the display is 4, press the button in the same position as you pressed in line #1.
For the 3rd line:
If the display is 1, press the button with the same label you pressed in line #2.
If the display is 2, press the button with the same label you pressed in line #1.
If the display is 3, press the button in the third position.
If the display is 4, press the button labeled “4”.
For the 4th line:
If the display is 1, press the button in the same position as you pressed in line #1.
If the display is 2, press the button in the first position.
If the display is 3, press the button in the same position as you pressed in line #2.
If the display is 4, press the button in the same position as you pressed in line #2.
For the last line:
If the display is 1, press the button with the same label you pressed in line #1.
If the display is 2, press the button with the same label you pressed in line #2.
If the display is 3, press the button with the same label you pressed in line #4.
If the display is 4, press the button with the same label you pressed in line #3.
An Example
Given the following input:
2 1432
4 3214
2 4213
1 4231
1 3214

For the 1st line, press the button in the second position, so output 4.
For the 2nd line, press the button in the same position as you pressed in line #1, so output 2.
For the 3rd line, press the button with the same label you pressed in line #1, so output 4.
For the 4th line, press the button in the same position as you pressed in line #1, so output 2.
For the last line, press the button with the same label you pressed in line #1, so output 4.
So the entire output is 42424, in any format and type.

JavaScript (ES6),  109 106 105  104 bytes
Takes input as a list of pairs [display, "buttons"]. Returns a list of pressed buttons.

a=>a.map(([d,b],i)=>a[i]=b[a[~i]=(n='_5567.848106.80990132'[i*4+d])>3?n>7?a[7-n]:n-4:b.search(a[n]||4)])

Try it online!
How?
The action for each line and each displayed value is encoded as a single character as follows (with 0-indexed lines and positions):

\$n=0\$ to \$3\$: press the button with the same label that we pressed in line \$n\$
\$n=4\$ to \$7\$: press the button in position \$n-4\$
\$n=8\$ or \$9\$: press the button in the same position as we pressed in line \$n-8\$
".": press the button labeled "\$4\$"

Translating the rules described in the challenge into these codes leads to the groups 5567, .848, 106., 8099 and 0132, which are concatenated into a single lookup string. The purpose of the leading "_" is just to deal with the 1-indexed input.
The input array \$a[\:]\$ is re-used to store both the labels that are pressed and their positions. For each line \$i\$, we store the label in \$a[i]\$ and its position in \$a[-i-1]\$.
Commented
a =>                              // a[] = input
  a.map(([d, b],                  // for each pair of displayed value d and buttons b
                 i) =>            // at position i in a[]:
    a[i] = b[                     //   save the label in a[i]
      a[~i] =                     //     save its position in a[-i-1]
        ( n =                     //       n = action code taken from ...
          '_5567.848106.80990132' //           ... our lookup string ...
          [i * 4 + d]             //           ... at position i * 4 + d
        ) > 3 ?                   //       if n is greater than 3:
          n > 7 ?                 //         if n is greater than 7:
            a[7 - n]              //           re-use the position used at line n - 8,
                                  //           stored in a[-(n-8)-1], i.e. a[7-n]
          :                       //         else:
            n - 4                 //           use the position n - 4
        :                         //       else:
          b.search(a[n]           //         look for the label used at line n
                        || 4)     //         or look for '4' if a[n] is undefined,
                                  //         which happens only when n is '.'
    ]                             //   end of button lookup
  )                               // end of map()


Words that Contain Digits A digit word is a word where, after possibly removing some letters, you are left with one of the single digits:
ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT or NINE (not ZERO).

For example, BOUNCE and ANNOUNCE are digit words, since they contain the digit one.

ENCODE is not a digit word, even though it contains an O, N and E, since they are not in order.

Write a program/function which takes a single (uppercase or lowercase -- you choose) word as input or a parameter and determines if it is a digit word. Make the code as short as possible.

If the word is not a digit word, you should return 'NO', 0 or any 'falsey' value (this may vary based on your language). If the word is a digit word, you should output the digit it contains, as a number.

You can assume that no words contain more than one digit, so you won't have anything like ONFIVE.

Test Cases

BOUNCE
1

ENCODE
NO

EIGHT
8

BLACKJACK
NO

FABULOUS
NO

EXERCISE
NO

DRIFTWOOD
2

SERVICEMAN
7

INSIGNIFICANCE
9

THROWDOWN
2

ZERO
NO

OZNERO
1

This challenge is taken from (and is a very slight modification of) Question 1 from BIO 2009. Most of the test cases are taken from the mark scheme.

Javascript (ES6), 101 99 bytes

f=
s=>-~'ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE'.split` `.findIndex(x=>s.match([...x].join`.*`))
<!-- snippet demo: -->
<input list=l oninput=console.log(f(this.value))>
<datalist id=l><option value=BOUNCE>
<option value=ENCODE>
<option value=EIGHT>
<option value=BLACKJACK>
<option value=FABULOUS>
<option value=EXERCISE>
<option value=DRIFTWOOD>
<option value=SERVICEMAN>
<option value=INSIGNIFICANCE>
<option value=THROWDOWN>
<option value=ZERO>
<option value=OZNERO>


Highest or Lowest Occurrences? Challenge:

Inputs:

A string containing printable ASCII (excluding spaces, tabs and new-lines)
A boolean †

Output:

The parts of the String are divided into four groups:

Lowercase letters
Uppercase letters
Digits
Other

Based on the boolean, we either output the highest occurrence of one (or multiple) of these four groups, or the lowest, replacing everything else with spaces.

For example:

Input: "Just_A_Test!"
It contains:
- 3 uppercase letters: JAT
- 6 lowercase letters: ustest
- 0 digits
- 3 other: __!

These would be the outputs for true or false:

true:   " ust    est "

// digits have the lowest occurrence (none), so everything is replaced with a space
false:  "            "

(Note: You are allowed to ignore trailing spaces, so the outputs can also be " ust    est" and "" respectively.)

Challenge rules:

The input will never be empty or contain spaces, and will only consist of printable ASCII in the range 33-126 or '!' through '~'.
You are allowed to take the input and/or outputs as character-array or list if you want to.
† Any two consistent and distinct values for the boolean are allowed: true/false; 1/0; 'H'/'L'; "highest"/"lowest"; etc. Note that these distinct values should be used (somewhat) as a boolean! So it's not allowed to input two complete programs, one that gives the correct result for true and the other for false, and then having your actual code only be <run input with parameter>. Relevant new default loophole I've added, although it can still use a lot of finetuning regarding the definitions..
If the occurrence of two or more groups is the same, we output all those occurrences.
The necessary trailing spaces are optional, and a single trailing new-line is optional as well. Necessary leading spaces are mandatory. And any other leading spaces or new-lines aren't allowed.

General rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, please add an explanation if necessary.

Test cases:

Inputs:                              Output:

"Just_A_Test!", true                 " ust    est "     (or " ust    est")
"Just_A_Test!", false                "            "     (or "")
"Aa1!Bb2@Cc3#Dd4$", either           "Aa1!Bb2@Cc3#Dd4$"
"H@$h!n9_!$_fun?", true              " @$ !  _!$_   ?"
"H@$h!n9_!$_fun?", false             "H     9        "  (or "H     9")
"A", true                            "A"
"A", false                           " "                (or "")
"H.ngm.n", true                      "  ngm n"
"H.ngm.n", false                     "       "          (or "")
"H.ngm4n", false                     "H.   4 "          (or "H.   4")

Jelly, 31 bytes
ØṖḟØBṭØBUs26¤f€³Lİ⁴¡$ÐṀFf
¹⁶Ç?€

Try it online!
The boolean values are 2 and 1 (or any other positive even/odd pair), which represent True and False respectively. I will try to add an explanation after further golfing.
Thanks to caird coinheringaahing for saving 2 bytes, and to Lynn for saving 4 bytes! Thanks to one of Erik's tricks, which inspired me to save 4 bytes!
How it works
Note that this is the explanation for the 35-byte version. The new one does roughly the same (but tweaked a bit by Lynn), so I won't change it.
ØBUs26f€³µ³ḟØBW,µẎLİ⁴¡$ÐṀF - Niladic helper link.
ØB                         - String of base digits: '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
                             abcdefghijklmnopqrstuvwxyz'.
  U                        - Reverse.
   s26                     - Chop into sublists of length 26, preserving shorter
                             trailing substrings.
      f€³                  - For each, keep the common characters with the input.
            ØB             - Base digits.
          ³ḟ               - Get the signs in the input. Filter the characters of the
                             input that aren't alphanumeric.
              W,µẎ         - Concatenate (wrap, two element list, tighten).
                       ÐṀ  - Keep the elements with maximal link value.
                  L        - Length.
                    ⁴¡     - Do N times, where N is the second input.
                   İ       - Inverse. Computes 1 ÷ Length. 2 maps to the length itself,
                             because 1 ÷ (1 ÷ Length) = length; 1 yields
                             (1 ÷ Length), swapping the maximal numbers with minimal ones.
                         F - Flatten.

¹⁶e¢$?€ - Main link.
      € - For each character.
   e¢?  - If it is contained by the last link (called niladically), then:
¹       - Identity, the character itself, else:
 ⁶      - A space.


Seqindignot sequence Title is made up, from 'Sequence Index Digit Not'.

Challenge:

Given an integer n which is >= 0, output the n'th number of the following sequence.
Here are the first 50 items, with it's (0-indexed) index above it:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
1 0 3 2 5 4 7 6 9 8 22 20 30 24 23 26 25 28 27 32 11 33 10 14 13 16 15 18 17 31 12 29 19 21 50 40 41 42 44 45 35 36 37 51 38 39 52 53 55 56 34

How does this sequence work?

The number at index n must be the first in order that does not have any digits in common with n, and hasn't occurred yet for previous indexes. So when we look at normal sequence like this from 0-60:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

We define the n'th values like this:

0: The first number (0) contains the same digit, so we look for the next (1), which does not contain the same digit. So n=0 outputs 1.
1: The first number (0) does not contain the same digit, so n=1 outputs 0.
2: We've already encountered 0 and 1, and the next digit (2) contains the same digit, so we look for the next (3), which does not contain the same digit. So n=2 outputs 3.
...
10: We've already encountered 0-9, so the next in line is 10. 10-19 contain the matching digit 1, 20 contains the matching digit 0, 21 contains the matching digit 1 again, 22 is valid, so n=10 outputs 22.
etc.

Challenge rules:

If your language is 1-indexed (or you choose to) you are allowed to start the sequence at 3 2 5 4 7 ... (skipping the 1 at n=0 and the 0 at n=1).
The minimum largest index you should support is 25,000. NOTE: The sequence stops at index 1,023,456,788, because the next index in line contains all 10 digits.
You are also allowed to output / return an array/list of the entire sequence up to and including index n if you want to.

General rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, please add an explanation if necessary.

Test cases:

This sequence actually created pairs regarding index and outputs. If index n outputs o, index o outputs n. So you can input either the left or right, and the output will be the other side:

0      <->  1       (this test case is optional)
2      <->  3
10     <->  22
12     <->  30
34     <->  50
89     <->  100
111    <->  200
112    <->  300
199    <->  322
2231   <->  4456
9605   <->  11118
19235  <->  46000
23451  <->  60668
25000  <->  13674

Here is a pastebin of the first 25,001 test cases if you want to try others.

Python 2, 92 91 89 88 bytes

a=()
i=0
exec"x=0\nwhile set(`x`)&set(`i`)or x in a:x+=1\na+=x,;i+=1;"*-~input()
print a

Try it online!

Prints a list of the first n+1 numbers

Different approach, which is a lot faster:

Python 2, 96 bytes

n=input()
r=range(9*n)
i=0
exec"x=0\nwhile set(`r[x]`)&set(`i`):x+=1\nprint r.pop(x),;i+=1;"*-~n

Try it online!


Add an integer to a set and take it back out Definition: a set is a datatype which allows testing of inclusion ("does set X contain element Y?") but does not have order. Its size is the number of distinct elements it contains.

Define an efficiently invertible injection from sets of k integers in the range 0 to 1000 inclusive to sets of k+1 integers in the range 0 to 1000 inclusive such that each set maps to a superset of itself. This is not possible for all k: indicate for what range of k your code works. An answer will not be accepted unless it works for at least one k > 4.

Equivalently, provide two functions:

f takes a set of integers between 0 and 1000 (inclusive), and outputs a set of integers in the same range. The output set contains all of the elements of the input set and exactly one element not in the input set.
g inverts f: that is to say, given the output of f it removes the element which f added, and gives back the input of f.

The winner: The encoder/decoder that can handle the longest input set for all permutations of a set of that length.

For sake of space, it is acceptable to post code for only the encoder or decoder, provided that it is clear that the other half the transcoder works.

Inspired by this question.

Edit:

This should be possible for sets of at least five.

Here is an example for a set of three (800 is an arbitrary number; the encoder's implementation and the actual input set will dictate what it is).

Input set: {78, 4, 5}
Output of f({78, 4, 5}): {78, 4, 5, 800}
Output of g({78, 4, 5, 800}): {4, 5, 78}

C#

void Encode(HashSet<int> set)
{
    set.Add((set.Single() + 1) % 1001);
}

void Decode(HashSet<int> set)
{
    set.Remove(set.Equals(new HashSet<int>() { 0, 1000 }) ? 0 : set.Max());
}

Works for a set of length 1.


Shorten an absolute path Sometimes a long absolute path, in e.g. a command-line parameter to a linux tool, can be shortened, using current working directory as reference:

$ pwd
/home/heh

$ cat /home/heh/mydir/myfile
my stuff

$ cat mydir/myfile
my stuff

In this challenge, you should make a function or a program that receives two parameters:

Absolute path, using the linux format (starts with /)
Current directory, using the same format

The output is the shorter of the following:

Input 1 unchanged
Relative path that refers to the same file/directory as the absolute path

Fine points:

If your operating system is compatible with linux, you can use the system's current directory instead of receiving it as input
You can assume the inputs contain only alphanumeric characters (and path separators)
You can assume the input absolute path doesn't have a path separator / at the end
You can assume the input current directory has a path separator / at the end
You cannot assume that the absolute path refers to an existing file, or that any part of it is an accessible directory; however, the current directory can be assumed valid
You can assume there are no symlinks anywhere near either path - because I don't want to require any special way of dealing with symlinks
No need to support the case where either of the inputs is the root directory
"The current directory" should be output as . (an empty string is not valid)

Test cases (input1, input2, output):

/home/user/mydir/myfile
/home/user
mydir/myfile

/var/users/admin/secret/passwd
/var/users/joe/hack
../../admin/secret/passwd

/home/user/myfile
/tmp/someplace
/home/user/myfile

/dir1/dir2
/dir1/dir2/dir3/dir4
../..

/dir1/dir2
/dir1/dir2
.

JavaScript (ES6), 107 106 bytes

Takes the absolute path a and the current path c in currying syntax (a)(c).

a=>c=>(A=a.split`/`,s='',c.split`/`.map(d=>!s&A[0]==d?A.shift():s+='../'),s+=A.join`/`)[a.length]?a:s||'.'

Test cases

let f =

a=>c=>(A=a.split`/`,s='',c.split`/`.map(d=>!s&A[0]==d?A.shift():s+='../'),s+=A.join`/`)[a.length]?a:s||'.'

console.log(f
  ('/home/user/mydir/myfile')
  ('/home/user')
);

console.log(f
  ('/var/users/admin/secret/passwd')
  ('/var/users/joe/hack')
);

console.log(f
  ('/home/user/myfile')
  ('/tmp/someplace')
);

console.log(f
  ('/dir1/dir2')
  ('/dir1/dir2/dir3/dir4')
);

console.log(f
  ('/dir1/dir2')
  ('/dir1/dir2')
);


Divisible by 1000003? Easy, just multiply the last digit by 300001 and add! Given a prime P greater than 10, your program or function must figure out its divisibility rule x, defined as the integer with smallest absolute value which yields a multiple of the original prime when multiplied by the last digit of the prime and added to the rest of the original prime.

Example

Given an input 31, the last digit is 1 and the rest of the number is 3. Thus your program must find the integer x with minimum absolute value such that 1*x + 3 is a multiple of 31. In this case, x=-3 works, so the program or function would return -3.

Given an input 1000003, the last digit is 3 and the rest of the number is 100000. Thus your program would find x=300001 because 3*300001+100000 = 1000003 which is a multiple of 1000003.

Mathematical Background

The value of x can be used as a divisibility test. If a number N is divisible by P, then adding x times the last digit of N to the rest of N will yield a multiple of P if and only if N is divisible by P in the first place.

For P=11, we get x=-1, which is equivalent to the well-known divisibility rule for 11: a number is divisible by 11 alternating difference of its digits is divisible by 11.

Rules

The output may be in any form that clearly encodes both the sign and value of the output.
The input prime will be between 10 and 2^30.
You do not need to handle if the input is not a prime or is not in the range.
You do not need to handle if both x and -x are valid outputs (should not happen).
Brute force is permitted, but more creative solutions are appreciated.
This is code-golf, so shortest code in each language wins! Do not let answers in golfing languages discourage you from posting in other languages.

Test Cases

Input   Output
11  -1
13  4
17  -5
19  2
23  7
29  3
31  -3
37  -11
41  -4
43  13
47  -14
53  16
59  6
61  -6
67  -20
71  -7
73  22
79  8
83  25
89  9
97  -29
101 -10
103 31
107 -32
109 11
113 34
127 -38
131 -13
1000003 300001
2000003 600001
2999999 300000
9999991 -999999

JavaScript (ES6), 32 25 23 bytes

f=
n=>(3/(n%5*2-5)*n+1)/10
<input type=number min=1 oninput=o.textContent=this.value%5*(this.value%2)?f(this.value):``><pre id=o>

3/(n%5*2-5) would be written 9/n(mod -10) if I had access to balanced modulo division. Edit: Saved 2 bytes thanks to @EgorSkriptunoff


Cops and Robbers: Redacted Primality (Cops' Thread) This challenge was originally sandboxed by Magic Octopus Urn; I adopted and posted it with his permission.

This is the cops' thread. The robbers' thread is here.

The challenge

Step One: Write a piece of code (function or full program) which checks for primality.
Step Two: Remove pieces of your code by replacing characters with the symbol █.
Step Three: Post the redacted code on the cops thread.
Step Four: Wait for your code to be cracked and try to crack other's code.

For example, the Groovy code {it.isPrime()} could become {██.is█████()}.
 (This one would be stupidly easy to crack; also, I know, .isPrime() is not a Groovy method.)

Scoring

You must include your program's score in its submission. The score is defined as the ratio of redacted characters to characters. So if your program had 20 characters and 5 were redacted, your score would be 0.25. The Groovy code above would have a score of 0.5.

Rules

Your program only needs to handle positive integers. It should output a truthy value if the number is prime and a falsy value otherwise. Please specify in your answer what it outputs.
Your code may not contain any comments or unnecessary whitespace.
No hashing or cryptographic obfuscation.
Your code may be no more than 50% redacted (at least 1/2 the characters must be shown). This means that the highest possible score is 0.5.
If your answer is not cracked within a week you may mark it safe and edit in the intended crack.

Winning

The winner will be the lowest-scoring uncracked answer within two weeks of posting. In the case of a tie, whichever has the most votes will win. This thread is always open to more submissions, but the winner chosen after two weeks will be permanent.

8086 DOS COM, 87 bytes, score 19/87 ~= 0.2183

Cracked by NieDzejkob

1└╣██1█╛ü ¼<█t<< u≈¼<█t█,0|/<██+ô≈ßô☺├δδâ√█|█╞█S█Y╣██9┘t█ë╪1╥≈±○╥t█Aδ∩╞█S█N┤█║S█═!├A
$

This is a COM program; expects number as a command line argument, outputs Y or N. Limit: 65535 because 16 bit processor (sizeof(int) would be 2). Newline is 0x0D 0x0A on this platform. Yes you count 20 █ instead of 19 █. One of them's a real █ and has not been substituted. Muhahaha.

The space in position 10 is actually a NUL byte. The symbol for NUL is the same as space in the old VGA font.


Remove entries from array to sort it and maximize sum of elements This challenge is from an admission test to a closed number cyber security course. Anyway it doesn't have to do with cyber security, it's just to test the students logical and coding skills.

Task

Write a program that removes entries from an array so that the remaining values are sorted in a strictly decreasing order and their sum is the maximized among all other possible decreasing sequences.

Input and Output

Input will be an array of integer values strictly greater than 0 and all different from each other.
You are free to choose whether to read input from file, command line or stdin.

Output will be a descending-sorted subarray of the input one, whose sum is greater than any other possible descending-sorted subarray.

Note: [5, 4, 3, 2] is a subarray of [5, 4, 1, 3, 2], even if 4 and 3 are not adjacent. Just because the 1 was popped.

Bruteforce solution

The simplest solution of course would be iterate among all possible combinations of the given array and search for a sorted one with the greatest sum, that would be, in Python:

import itertools

def best_sum_desc_subarray(ary):
    best_sum_so_far = 0
    best_subarray_so_far = []
    for k in range(1, len(ary)):
        for comb in itertools.combinations(ary, k):
            if sum(comb) > best_sum_so_far and all(comb[j] > comb[j+1] for j in range(len(comb)-1)):
                best_subarray_so_far = list(comb)
                best_sum_so_far = sum(comb)
    return best_subarray_so_far

Unfortunately, since checking if the array is sorted, and calculating the sum of it's elements is  and since this operation will be done  times for  from  to , the asymptotic time complexity will be

Challenge

Your goal is to achieve a better time complexity than the bruteforce above. The solution with the smallest asymptotic time complexity is the winner of the challenge. If two solutions have the same asymptotic time complexity, the winner will be the one with the smallest asymptotic spatial complexity.

Note: You can consider reading, writing and comparing atomic even on large numbers.

Note: If there are two or more solutions return either of them.

Test cases

Input:  [200, 100, 400]
Output: [400]

Input:  [4, 3, 2, 1, 5]
Output: [4, 3, 2, 1]

Input:  [50, 40, 30, 20, 10]
Output: [50, 40, 30, 20, 10]

Input:  [389, 207, 155, 300, 299, 170, 158, 65]
Output: [389, 300, 299, 170, 158, 65]

Input:  [19, 20, 2, 18, 13, 14, 8, 9, 4, 6, 16, 1, 15, 12, 3, 7, 17, 5, 10, 11]
Output: [20, 18, 16, 15, 12, 7, 5]

Input:  [14, 12, 24, 21, 6, 10, 19, 1, 5, 8, 17, 7, 9, 15, 23, 20, 25, 11, 13, 4, 3, 22, 18, 2, 16]
Output: [24, 21, 19, 17, 15, 13, 4, 3, 2]

Input:  [25, 15, 3, 6, 24, 30, 23, 7, 1, 10, 16, 29, 12, 13, 22, 8, 17, 14, 20, 11, 9, 18, 28, 21, 26, 27, 4, 2, 19, 5]
Output: [25, 24, 23, 22, 17, 14, 11, 9, 4, 2]

Haskell, \$O(n \log n)\$ time, \$O(n)\$ space

{-# LANGUAGE MultiParamTypeClasses #-}

import qualified Data.FingerTree as F

data S = S
  { sSum :: Int
  , sArr :: [Int]
  } deriving (Show)

instance Monoid S where
  mempty = S 0 []
  mappend _ s = s

instance F.Measured S S where
  measure = id

bestSubarrays :: [Int] -> F.FingerTree S S
bestSubarrays [] = F.empty
bestSubarrays (x:xs) = left F.>< sNew F.<| right'
  where
    (left, right) = F.split (\s -> sArr s > [x]) (bestSubarrays xs)
    sLeft = F.measure left
    sNew = S (x + sSum sLeft) (x : sArr sLeft)
    right' = F.dropUntil (\s -> sSum s > sSum sNew) right

bestSubarray :: [Int] -> [Int]
bestSubarray = sArr . F.measure . bestSubarrays

How it works

bestSubarrays xs is the sequence of subarrays of xs that are on the efficient frontier of {largest sum, smallest first element}, ordered from left to right by increasing sum and increasing first element.

To go from bestSubarrays xs to bestSubarrays (x:xs), we

split the sequence into a left side with first elements less than x, and a right side with first elements greater than x,
find a new subarray by prepending x to the rightmost subarray on the left side,
drop the prefix of subarrays from the right side with smaller sum than the new subarray,
concatenate the left side, the new subarray, and the remainder of the right side.

A finger tree supports all these operations in \$O(\log n)\$ time.


Tower building challenge I have recently thought of a wonderful relatively old mobile game, called Tower Bloxx. Alhough I'm not really old myself, but it reminded me of childhood and school :)

So this my challenge is a kind of a reference to that good game!

I have (hopefully) looked into any tower question on PPCG and this won't be a dupe.

Definition

Given N - number of blocks, build a tower of N blocks with the following pattern. The horizontal coordinate is changed with every block.

In order to avoid misinterpretations, here's the "table" of correlations between the n-th block and its horizontal coordinate.

There're no random things there, the coordinate for each block is strictly defined.

These horizontal coordinates are all listed relative to the first block and they are in fact just for readability of the following test cases.

N    X (coord)
------
1    0
2    2
3   -2
4    0
5   -2
6    2
7    goto N=1

On top of the last block, you must smash a roof.

Input

Positive integer (N).

Output:

N blocks stacked on top of each other and the roof. Each block is horizontally moved compared to the first block (to either -2, 0, or 2 points), as described in the table.

The block structure:

  *********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Once they are stacked together, the top of the lower block intersects with the bottom of the higher block:

    *********
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

The roof that should be stacked on top of the last, n-th block is:

      *
     ***
    ** **
   **   **

The block with the roof atop looks like this:

      *
     ***
    ** **
   **   **
  *********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Test cases below.

Input: 1. Output:

      *
     ***
    ** **
   **   **
  *********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Input: 2. Output:

        *
       ***
      ** **
     **   **
    *********
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Input: 3. Output:

    *
   ***
  ** **
 **   **
*********
* ----- *
* |   | *
* |   | *
* ----- *
*************
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Input: 4. Output:

      *
     ***
    ** **
   **   **
  *********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
***********
* ----- *
* |   | *
* |   | *
* ----- *
*************
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Input: 10. Output:

      *
     ***
    ** **
   **   **
  *********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
***********
* ----- *
* |   | *
* |   | *
* ----- *
*************
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  ***********
    * ----- *
    * |   | *
    * |   | *
    * ----- *
*************
* ----- *
* |   | *
* |   | *
* ----- *
***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
***********
* ----- *
* |   | *
* |   | *
* ----- *
*************
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Scoring

Code golf, shortest wins!

Trailing invisible stuff is allowed.

Charcoal, 48 bytes

ＦＮ«Ｍ×Ｘ±¹ιＩ§224ι←Ｂ⁹±⁶*↗↗↑↓²→⁵↖↑²←⁵↖»ＧＨ<⁵*Ｍ⁷←ＧＨ<⁴*

Try it online! Link is to verbose version of code. Explanation:

ＦＮ«

Draw N Blox.

Ｍ×Ｘ±¹ιＩ§224ι←

Adjust the horizontal position before drawing each Blox.

Ｂ⁹±⁶*

Draw the outer wall of the Blox.

↗↗↑↓²→⁵↖↑²←⁵↖»

Draw the inner wall of the Blox.

ＧＨ<⁵*Ｍ⁷←ＧＨ<⁴*

Raise the roof.


Tips for golfing in GolfScript What, this post doesn't exist yet?

Of course, GolfScript is made for golfing, so you might think that no specific tips are really needed.  But to make full use of GolfScript's features, you need to learn some non-obvious tricks.  This post is for collecting such helpful tips and tricks.

To start with, here are the official GolfScript reference pages.  You should really familiarize yourself with these first:

Tutorial
Syntax
Built-ins
Quick reference

In particular, I would very much suggest reading the pages in this order — the quick reference is of little use until you're already reasonably familiar with the built-ins, and the tutorial includes some important details that are not explained on the other pages.

Ps. For the sake of inspiration and personal interest, here are some questions I'd like to see nice answers to:

How to do limited transliteration in GolfScript?  {FROM?TO=}% works if you can be sure all the inputs are found in FROM (or don't mind them all being mapped to the last element of TO), but all the ways I've seen for leaving unmapped values unchanged have been more or less klugey.
How to best convert a string into an array of ASCII codes and back?  Which operations do this as a side effect?  What's the best way to dump the characters in a string onto the stack (like ~ does for arrays)?

Rational / Float / Complex

I've read so many times that GolfScript has only integers that I started to believe it. Well, it's not true.

2-1? # Raise 2 to the power of -1. Result: 0.5
4-1? # Raise 4 to the power of -1. Result: 0.25
+    # Add. Result: 0.75

The output is

3/4

with the standard GolfScript interpreter and

0.75

on Web GolfScript.

Similar hacks allow to cast to Rational, Float or even Complex:

{-2.?./*}:rational
{2.-1??./*}:float
{-2.-1??./*}:complex


Priority to the right Your task is to regulate traffic on a crossroads. There are 4 roads coming from north, east, south and west.

The input is a string representing the upcoming traffic on each road. For example, NNNWS indicates there is a total of 5 cars: three at the north, one at the west and one at the south. The order of characters has no importance here, NNNWS is equivalent to WNNSN.

You must output the order in which the cars should go, using the priority to the right rule: cars coming from the south must let cars coming from east go first, east gives way to north, north gives way to west and west gives way to south.

For example, with the input NNNWS, the south car should go first, then the west car, then the 3 north cars. The output should thus be SWNNN.

There are some indecidable cases, for example NS or NNWSE : you should then output the string stuck.

Test cases

N => N
NW => WN
NWS => SWN
SNW => SWN
SSSSS => SSSSS
ENNNNES => NNNNEES
NS => stuck
NNWSE => stuck

Perl, 65 bytes

Includes +2 for -lp

Give input on STDIN. Assumes the empty string is not a valid input

#!/usr/bin/perl -lp
s%.%'+(y/NESW/ESWN/*s/N(.*)W/W$1N/,/N/^/S/)'x4%gere+0or$_=stuck

If you don't mind the absence of a newline after stuck you can drop the l option


Does it oscillate periodically? Challenge

Given a list, determine if grouping the list into runs of increasing and decreasing elements will result in a list of equal-sized lists.

In other words, "turning points" of the list are spaced out evenly.

Example

Here's an example: 0, 3, 7, 5, 2, 3, 6

0, 3, 7 increases, 7, 5, 2 decreases, and 2, 3, 6 increases. Therefore this is truthy.

Another example: 1, 4, 6, 8, 5, 3, 5, 7, 9

1, 4, 6, 8 increases, 8, 5, 3 decreases, and 3, 5, 7, 9 increases. Therefore this is falsy.

Rules and Specifications

No adjacent elements will be equal
All numbers can be assumed to be within your language's reasonable number range
You may assume that all numbers are integers, if it helps you golf your submission
This is code-golf, so the shortest answer wins
Input as a list in any reasonable representation and output as any truthy/falsy value. The two values must be consistent.

Test Cases

Input -> Output
1, 3, 5, 8, 6, 4, 2, 3, 5, 7, 6, 4, 2, 5, 7, 9, 6, 4, 2 -> True
1, 3, 5, 7, 6, 4, 5, 7, 9, 8, 6, 4, 2, 3, 5 -> False
2, 3, 6, 4, 2, 3, 7, 5, 3, 4, 6 -> True
3, 6, 4, 8, 5, 7, 3, 5, 2 -> True
8 -> True
1, 3, 5, 7 -> True
4, 5, 7, 6, 8, 9 -> False
6, 4, 2, 3, 5, 4, 2 -> True
8, 5, 3, 2, 4, 6, 5, 3, 2, 5, 7 -> False

Note: You may not assume that all numbers are single digits (unless that is all your language is capable of handling); the test cases reflect that just because it's easier for me to type the cases this way :P Here are a few test cases with numbers outside of that range:

1, 5, 10, 19, 15, 13, 8, 13, 18, 23, 19, 18, 14 -> True
15, 14, 17, 16, 19, 18 -> True
12, 16, 19, 15, 18, 19 -> False

MATL, 10 9 bytes

dZS&Y'da~

Try it online!

Saved one byte thanks to Luis Mendo!

Explanation:

Assume the input is: [0, 3, 7, 5, 2, 3, 6]:

            % Implicit input:                                [0, 3, 7, 5, 2, 3, 6]
d           % Difference between adjacent elements:          [3, 4, -2, -3,  1,  3]
 ZS         % Sign of the differences:                       [1, 1, -1, -1, 1, 1]
   &Y'      % Length of runs of consecutive elements:        [2, 2, 2]
     d      % Difference between the lengths:                [0, 0]
      a     % Any non-zero elements:                         False
       ~    % Negate, to get a truthy value if all are zero: True


Golfing Python string literals Background

Python 3 has many types of string literals. For example, the string this 'is' an exa\\m/ple can be represented as:

'this \'is\' an exa\\\\m/ple'
"this 'is' an exa\\\\m/ple"
r"this 'is' an exa\\m/ple"
'''this 'is' an exa\\\\m/ple'''
"""this 'is' an exa\\\\m/ple"""
r'''this 'is' an exa\\m/ple'''
r"""this 'is' an exa\\m/ple"""

As you can see, using different delimiters for strings can lengthen or shorten strings by changing the escaping needed for certain characters. Some delimiters can't be used for all strings: r' is missing above (see later for explanation). Knowing your strings is very useful in code golf.

One can also combine multiple string literals into one:

'this \'is\' an ''''exa\\\\m/ple'''
"this 'is' an "r'exa\\m/ple'

Challenge

The challenge is, given a printable ASCII string, to output its shortest literal representation in Python.

Details on string mechanics

Strings can be delimited using ', ", ''' and """. A string ends when the starting delimiter is hit again unescaped.

If a string literal starts with ''' or """ it is consumed as the delimiter. Otherwise ' or " is used.

Characters can be escaped by placing a \ before them. This inserts the character in the string and eliminates any special meaning it may have. For example, in 'a \' b' the middle ' is escaped and thus doesn't end the literal, and the resulting string is a ' b.

Optionally, one of r or R may be inserted before the starting delimiter. If this is done, the escaping \ will appear in the result. For example, r'a \' b' evaluates to a \' b. This is why a ' b cannot be delimited by r'.

To escape ''' or """, one only needs to escape one of the characters.

These literals can be concatenated together, which concatenates their contents.

Rules

The input is the string to golf. Printable ASCII only, so no newlines or other special characters.
The output is the golfed string literal. If there are multiple solutions, output one.
To simplify the challenge, in non-r strings any escapes except for \\, \' and \" are considered invalid. They must not be used in the output, even though '\m' is equal to '\\m' in Python. This removes the need to process special escape codes such as \n.
Builtins for golfing Python strings are disallowed. Python's repr is allowed, since it's crappy anyway.
Standard code-golf rules apply.

Example inputs/outputs

I tried my best to verify these, but let me know if there are mistakes. If there are multiple valid outputs to the cases, they are all listed below the input.

test
 -> 'test'
 -> "test"
te\st
 -> 'te\\st'
 -> "te\\st"
 -> r'te\st'
 -> r"te\st"
te'st
 -> "te'st"
te"st
 -> 'te"st'
t"e"s't
 -> 't"e"s\'t'
te\'st
 -> "te\\'st"
 -> r'te\'st'
 -> r"te\'st"
te\'\"st
 -> r'te\'\"st'
 -> r"te\'\"st"
t"'e"'s"'t"'s"'t"'r"'i"'n"'g
 -> """t"'e"'s"'t"'s"'t"'r"'i"'n"'g"""
 -> '''t"'e"'s"'t"'s"'t"'r"'i"'n"'g'''
t"\e"\s"\t"\s'\t"\r"\i"\n"\g
 -> r"""t"\e"\s"\t"\s'\t"\r"\i"\n"\g"""
 -> r'''t"\e"\s"\t"\s'\t"\r"\i"\n"\g'''
t"""e"""s"""'''t'''s'''"""t"""r"""'''i'''n'''g
 -> 't"""e"""s"""'"'''t'''s'''"'"""t"""r"""'"'''i'''n'''g"
t\"""e\"""s\"""'''t'''s'''\"""t\"""r\"""'''i'''n'''g
 -> r"""t\"""e\"""s\"""'''t'''s'''\"""t\"""r\"""'''i'''n'''g"""
t"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\'\
 -> r't"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\'''\\'
 -> r't"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\''"\\"
"""t"'e"'s"'t"'s"'t"'r"'i"'n"'g'''
 -> """\"""t"'e"'s"'t"'s"'t"'r"'i"'n"'g'''"""
 -> '''"""t"'e"'s"'t"'s"'t"'r"'i"'n"'g''\''''

Thanks to Anders Kaseorg for these additional cases:

\\'"\\'\
 -> "\\\\'\"\\\\'\\"
''"""''"""''
 -> '''''"""''"""'\''''

Python 3, 264 262 bytes

f=lambda s,b='\\',r=str.replace:min(sum([['r'+d+s+d,d+r(r(s[:-1],b,b+b),d,d[1:]+b+d[0])+b*(s[-1:]in[b,d[0]])+s[-1:]+d][d in r(r(s+d[1:],b+b,'x'),b+d[0],b)or r(s,b+b,'')[-1:]==b:]for d in["'",'"',"'''",'"""']],[f(s[:k])+f(s[k:])for k in range(1,len(s))]),key=len)

Try it online!

This works but is very slow without memoization, which you can add with

import functools
f=functools.lru_cache(None)(f)

It found an improved solution for one of the test cases:

t"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\'\
 -> 't"e"s"t"s"t"r"i"n"g"'r"\'\'\'\'\'\'\'"'\\'
 -> r't"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\'''\\'

Previous versions of this answer returned incorrect results on the following, which could be added as test cases:

\\'"\\'\
 -> "\\\\'\"\\\\'\\"
''"""''"""''
 -> '''''"""''"""'\''''


Implement ROT-47... in ROT-47 Challenge: Implement ROT-47 in code that works as both itself and as the ROT-47 version of itself.
Scoring:
Your score is calculated as a percentage of used, ROT-47 eligible bytes in total of both versions of the program divided by total bytes (all characters) of both versions.
A used, ROT-47 eligible byte is any character that would be converted by the ROT-47 cipher that is not part of a comment or ignored by the compiler/interpreter. For example, any character in a brainfuck program that is not +-<>[],.  is not considered a used byte, and any character in a C program including and after // or inside /* */ is not considered a used byte. All special symbols in APL are not considered used, as are all characters in a Whitespace program (sorry).
Ties will be broken by the program with the most upvotes. If there is still a tie, then the shortest program wins.
Example scoring:
C: 62/64 = 96.875%
Notice there is a space in this program. Obviously also, this program is not a valid entry because it doesn't even compile, but I wanted to show how scoring works.
main(){printf("Hello World!");}

Ruby, 100% (74 characters)

Input on STDIN, output on STDOUT.

Vj=s=gets;puts(s.tr'!-~','P-~!-O');Vj;'lDl86EDjAFEDWD]ECVP\OV[V!\OP\~VXj;'

The second line is the first line ROT-47'd. Therefore, when ROT-47ing the whole program, it becomes:

';lDl86EDjAFEDWD]ECVP\OV[V!\OP\~VXj';jV=s=gets;puts(s.tr'!-~','P-~!-O');jV

My strategy here is based upon the fact that:

V is ' when ROT-47'd
j is ; when ROT-47'd
Therefore, Vj=...Vj; turns into ';l...';, which is essentially a no-op

Now you can create any arbitrary code that does anything normally and no-ops when ROT-47'd. This is because Vj=...Vj; can support running any code as you could do Vj=0;{INSERT ANY CODE};Vj;, and that will become '...'; when ROT-47'd. You just have to be careful not to use V in that code, since that will break it.

Similar logic can be used in reverse to produce the second half (jV instead of Vj)


High throughput Fizz Buzz Fizz Buzz is a common challenge given during interviews. The challenge goes something like this:

Write a program that prints the numbers from 1 to n. If a number is
divisible by 3, write Fizz instead. If a number is divisible by 5,
write Buzz instead. However, if the number is divisible by both 3 and
5, write FizzBuzz instead.

The goal of this question is to write a FizzBuzz implementation that goes from 1 to infinity (or some arbitrary very very large number), and that implementation should do it as fast as possible.
Checking throughput
Write your fizz buzz program. Run it. Pipe the output through <your_program> | pv > /dev/null. The higher the throughput, the better you did.
Example
A naive implementation written in C gets you about 170MiB/s on an average machine:
#include <stdio.h>

int main() {
    for (int i = 1; i < 1000000000; i++) {
        if ((i % 3 == 0) && (i % 5 == 0)) {
            printf("FizzBuzz\n");
        } else if (i % 3 == 0) {
            printf("Fizz\n");
        } else if (i % 5 == 0) {
            printf("Buzz\n");
        } else {
            printf("%d\n", i);
        }
    }
}

There is a lot of room for improvement here. In fact, I've seen an implementation that can get more than 3GiB/s on the same machine.
I want to see what clever ideas the community can come up with to push the throughput to its limits.
Rules

All languages are allowed.
The program output must be exactly valid fizzbuzz. No playing tricks such as writing null bytes in between the valid output - null bytes that don't show up in the console but do count towards pv throughput.

Here's an example of valid output:
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz

# ... and so on

Valid output must be simple ASCII, single-byte per character, new lines are a single \n and not \r\n. The numbers and strings must be correct as per the FizzBuzz requirements. The output must go on forever (or a very high astronomical number) and not halt / change prematurely.

Parallel implementations are allowed (and encouraged).

Architecture specific optimizations / assembly is also allowed. This is not a real contest - I just want to see how people push fizz buzz to its limit - even if it only works in special circumstances/platforms.

Scores
Scores are from running on my desktop with an AMD 5950x CPU (16C / 32T). I have 32GB of 3600Mhz RAM.

Also @Aiden4's submission - 3GiB/s. I lost the plotting code, might add it to the image once I find it
Also @Toby Speight's submission - 6.2-6.8GiB/s with OMP_NUM_THREADS=1

After much trial and error, with the goal of not resorting to Assembly while achieving the best single-threaded performance, this is my entry:
#include <unistd.h>

#define unlikely(e)      __builtin_expect((e), 0)
#define mcpy(d, s, n)    __builtin_memcpy((d), (s), (n))

#define CACHELINE 64
#define PGSIZE 4096
#define ALIGNED_BUF 65536
#define FIZZ "Fizz"
#define BUZZ "Buzz"
#define DELIM "\n"

typedef struct {
    unsigned char offset;
    char data[CACHELINE - sizeof(unsigned char)];
} counters_t;

static inline void os_write(int out, void *buf, unsigned int n)
{
    while (n)
    {
        ssize_t written = write(out, buf, n);

        if (written >= 0)
        {
            buf += written;
            n -= written;
        }
    }
}

int main(void)
{
    const int out = 1;

    __attribute__((aligned(CACHELINE))) static counters_t counter = {
        sizeof(counter.data) - 1, "00000000000000000000000000000000000000000000000000000000000000"
    };
    __attribute__((aligned(PGSIZE))) static char buf[ALIGNED_BUF + (sizeof(counter.data) * 15 * 3)] = { 0 };
    char *off = buf;

    for (;;)
    {
        // Write chunks of 30 counters until we reach `ALIGNED_BUF`
        while (off - buf < ALIGNED_BUF)
        {
            #define NN (sizeof(counter.data) - 2)

            // Hand-rolled counter copy, because with non-constant sizes the compiler
            // just calls memcpy, which is too much overhead.
            #define CTRCPY(i) do { \
                const char *src = end; \
                char *dst = off; \
                unsigned _n = n; \
                switch (_n & 3) { \
                case 3: *dst++ = *src++; \
                case 2: \
                    mcpy(dst, src, 2); \
                    dst += 2; src += 2; \
                    break; \
                case 1: *dst++ = *src++; \
                case 0: break; \
                } \
                for (_n &= ~3; _n; _n -= 4, dst += 4, src += 4) { \
                    mcpy(dst, src, 4); \
                } \
                mcpy(off + n, i DELIM, sizeof(i DELIM) - 1); \
                off += n + sizeof(i DELIM) - 1; \
            } while (0)

            // Write the first 10 counters of the group (need to separate the
            // first 10 counters from the rest of the chunk due to possible decimal
            // order increase at the end of this block)
            {
                const char *const end = counter.data + counter.offset;
                const unsigned int n = sizeof(counter.data) - counter.offset - 1;

                CTRCPY("1"); // 1
                CTRCPY("2"); // 2

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (3)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("4"); // 4

                mcpy(off, BUZZ DELIM FIZZ DELIM, sizeof(BUZZ DELIM FIZZ DELIM) - 1); // Buzz (5) Fizz (6)
                off += sizeof(BUZZ DELIM FIZZ DELIM) - 1;

                CTRCPY("7"); // 7
                CTRCPY("8"); // 8

                mcpy(off, FIZZ DELIM BUZZ DELIM, sizeof(FIZZ DELIM BUZZ DELIM) - 1); // Fizz (9) Buzz (10)
                off += sizeof(FIZZ DELIM BUZZ DELIM) - 1;

                // Carry handling on MOD 10
                for (unsigned d = NN; ; --d)
                {
                    if (counter.data[d] != '9')
                    {
                        ++counter.data[d];
                        break;
                    }
                    counter.data[d] = '0';
                }

                // Decimal order increases only when `counter MOD 30 == 10`
                if (unlikely(counter.data[counter.offset - 1] != '0'))
                {
                    if (unlikely(counter.offset == 1))
                    {
                        goto end;
                    }

                    --counter.offset;
                }
            }

            // Write the chunk's remaining 20 counters
            {
                const char *const end = counter.data + counter.offset;
                const unsigned int n = sizeof(counter.data) - counter.offset - 1;

                CTRCPY("1"); // 11

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (12)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("3"); // 13
                CTRCPY("4"); // 14

                mcpy(off, FIZZ BUZZ DELIM, sizeof(FIZZ BUZZ DELIM) - 1); // FizzBuzz (15)
                off += sizeof(FIZZ BUZZ DELIM) - 1;

                CTRCPY("6"); // 16
                CTRCPY("7"); // 17

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (18)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("9"); // 19

                mcpy(off, BUZZ DELIM FIZZ DELIM, sizeof(BUZZ DELIM FIZZ DELIM) - 1); // Buzz (20) Fizz (21)
                off += sizeof(BUZZ DELIM FIZZ DELIM) - 1;

                // Carry handling on MOD 10
                for (unsigned d = NN; ; --d)
                {
                    if (counter.data[d] != '9')
                    {
                        ++counter.data[d];
                        break;
                    }
                    counter.data[d] = '0';
                }

                CTRCPY("2"); // 22
                CTRCPY("3"); // 23

                mcpy(off, FIZZ DELIM BUZZ DELIM, sizeof(FIZZ DELIM BUZZ DELIM) - 1); // Fizz (24) Buzz (25)
                off += sizeof(FIZZ DELIM BUZZ DELIM) - 1;

                CTRCPY("6"); // 26

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (27)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("8"); // 28
                CTRCPY("9"); // 29

                mcpy(off, FIZZ BUZZ DELIM, sizeof(FIZZ BUZZ DELIM) - 1); // FizzBuzz (30)
                off += sizeof(FIZZ BUZZ DELIM) - 1;

                // Carry handling on MOD 10
                for (unsigned d = NN; ; --d)
                {
                    if (counter.data[d] != '9')
                    {
                        ++counter.data[d];
                        break;
                    }
                    counter.data[d] = '0';
                }
            }
        }

        os_write(out, buf, ALIGNED_BUF);
        mcpy(buf, buf + ALIGNED_BUF, (off - buf) % ALIGNED_BUF);
        off -= ALIGNED_BUF;
    }

end:
    os_write(out, buf, off - buf);

    return 0;
}

Compiled as clang -o fizz fizz.c -O3 -march=native (with clang 11.0.0 on my Ubuntu 20.10 installation, running kernel version 5.8.0-26.27-generic 5.8.14 on an Intel Core i7-8750H mobile CPU while plugged into the wall), this produces ~3.8GiB/s when run as ./fizz | pv > /dev/null (not very steady due to write blocking every once in a while, but there's nothing I can do about that when single-threaded, I guess).
EDIT: Optimised the carry handling a bit, and now I'm getting ~3.9GiB/s on my machine (same configuration as above).


Make a Number Expression Few years ago, an esoteric programming language named 아희(Aheui) was created. Well, actually you don't need to know about this language or Korean characters.

Aheui uses stacks and a queue, but this time we use one stack and ignore other stacks and queue. You can push a number between 2 and 9 into a stack. You can do arithmetic operations by popping two numbers and pushing result. And you can duplicate a top number.

So, when I need a big number in Aheui, making a number was not an easy work. Push, push, multiply, duplicate, push, multiply, push, add…. It takes too much time and sometimes waste of bytes. I need a shortest expressions.

Summary

Your task is to write a function or a program which takes a number n (0 <= n <= 1000000) and returns concatenation of tokens.

Tokens are basically a postfix notation. Tokens are consisted of

Number between 2 and 9, which means "push number into stack"
+, -, /, *, which means "pop two numbers from stack, do arithmetic operation, push the result into stack". All calculations are in integer.
>, which means "duplicate a top number"

Tokens will be concatenated with empty string, so 5 5 + will be 55+.

After calculations, n must be on the top of the stack.

Sample input and output

INPUT = 0
OUTPUT = 22-
(or 33-, 44-, whatever)

INPUT = 1
OUTPUT = 22/
(or 32-, 33/, whatever)

INPUT = 5
OUTPUT = 5
(We don't need calculations, just push)

INPUT = 64
OUTPUT = 88*
(or 8>*)

INPUT = 1337
OUTPUT = 75*2+>*48*-
(This may not be a shortest solution)

Scoring

This is a list of test cases. Test cases are seperated by a new line character. You may write a test script which converts those bunch of numbers to string of tokens, or you can do it by your hand.

Let

S = size of complete function or program
O = length of converted strings
I = size of test cases (In this case, I = 526)

Then your score will be S * (O / I). Sizes are in bytes.

S includes function declarations, #includes, imports, whatever. Test script is not counted.

Scoring example

Let S is 150.

Sample Test cases

0
1
5
64
1337

Sample Output

22-22/588*75*2+>*48*-

In this case, I = 9, and O = 21. So your score is 150 * (21 / 9) = 350.

Rules

Standard "loopholes" are forbidden.
Lowest score wins.
If there is a tie, smaller code size wins.
Winner will be selected after three weeks (2014-08-04).

I wrote a validator in Node.js. Put input.txt and output.txt in same directory, and run node validator.js.

And I found two-year-old similar question. But scoring is different (this question includes code size in score), and this question can't use 1. So I hope it's not a duplicate.

Javascript, Score = 1663.46768

function X($){S=Math.sqrt;function J(A){return A.join("")}function M(A,B){return A.length<B.length?A:B}function D(q){var w="",e,r,t,y;for(e=9;e>1;e--){r=~~(q/e);t=r*e-q;if(t==0)y=J([G(r),e,"*"]);else y=J([G(r),e,"*",G(-t),"+"]);if(w=="")w=y;w=M(w,y)}return w}function Q(a){var s=~~S(a),d=a-s*s,f=J([G(s),">*",G(d),"+"]),g;s=Math.ceil(S(a));d=s*s-a;g=J([G(s),">*",G(d),"-"]);return M(f,g)}function G(z){var x,c,v,b,n,m;if(z==0)return"22-";if(z==1)return"22/";if(z>1&&z<10)return""+z;if(z>9&&z<19){x=~~(z/2);c=z-x;return J([x,c,"+"])}for(v=9;v>1;v--){b=~~(z/v);if(b>1&&b<10&&b*v==z)return J([v,b,"*"])}n=S(z);if(~~n==n)return J([G(n),">*"]);return M(D(z),Q(z))}return G($)}

This is my attempt for my question, and this is output. Code size is 671, and output size is 1304. Score is 1663.46768 (rounded up to 5 decimal places).


Make the super number hyper-pyramid Challenge

Given a positive integer \$n\$, output the \$n\$-dimensional pyramidal list.

Example

\$n = 1\$:

Objects arranged in a 1D pyramid (line) with side length 1 is just by itself.

So, the output is {1}.

\$n = 2\$:

Objects arranged in a 2D pyramid (a triangle) with side length 2 would have one on the first row (cyan), and two on the second row (magenta).

Note, the first row is a 1D pyramid with side length 1 ({1}), and the second row is a 1D pyramid with side length 2 ({1, 1}).

So, the output is {{1}, {1, 1}}.

\$n = 3\$:

Objects arranged in a 3D pyramid with side length 3 would have 3 layers:

The first layer (cyan) is a 2D pyramid with side length 1. It has one row, which has one object. ({{1}})
The second layer (magenta) is a 2D pyramid with side length 2; It has two rows: the first row with one object and the second row with two objects. ({{1}, {1, 1}})
The third layer (yellow) is a 2D pyramid with side length 3; it has three rows: the first row with one object, second with two, and third with three. ({{1}, {1, 1}, {1, 1, 1}})

So, the output is {{{1}}, {{1}, {1, 1}}, {{1}, {1, 1}, {1, 1, 1}}}.

\$n = k\$

This is a \$k\$ dimensional pyramid with side length \$k\$. Each "layer" would be a \$k-1\$ dimensional pyramid, whose side length is its index (1-indexed).

Sample Outputs

n  output

1  {1}

2  {{1},
    {1, 1}}

3  {{{1}},
    {{1}, {1, 1}},
    {{1}, {1, 1}, {1, 1, 1}}}

4  {{{{1}}},
    {{{1}}, {{1}, {1, 1}}},
    {{{1}}, {{1}, {1, 1}}, {{1}, {1, 1}, {1, 1, 1}}},
    {{{1}}, {{1}, {1, 1}}, {{1}, {1, 1}, {1, 1, 1}},
     {{1}, {1, 1}, {1, 1, 1}, {1, 1, 1, 1}}}}

Rules

No standard loopholes as always.
The innermost values of your list may be anything (does not need to be consistent for all elements), as long as they are not lists.

This is code-golf, so shortest submissions in each language win!

Note: Graphics generated using Mathematica

Wolfram Language (Mathematica), 16 bytes

Ha! Of course it is biased towards Mathematica!

Nest[Range,#,#]&

Try it online!


Ode Golf - Letter Deletions Given a dictionary file (a text file containing a word or phrase on each line, with possible punctuation but no numbers; lines are alphabetized), you must output each combination of words where one letter can be removed from a word to make another; the removed letter should be encased in parentheses.

For example, the input

cat
cart
code
golf
ode
verify
versify

should give an output of

ca(r)t
(c)ode
ver(s)ify

Multiple ways to get the same pair must only be displayed once. You can output scra(p)ped or scrap(p)ed, but not both.

The output should be ordered alphabetically by the longer entry;

mart
mar
mat
ma

should have an output of

ma(r)
ma(t)
ma(r)t
mar(t)

and the latter two could be in either order.

The dictionary file may include capitalizations, spaces, hyphens, or apostrophes; these should be ignored. For instance,

inlay
in-play

should produce in(p)lay. Your output should all be in the same case. Extra whitespace is allowed.

Input can be STDIN or from a file; it is separated by newlines.
Output can be return value of a function or STDOUT (or written to a file if you wanted).

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

(This is my first challenge on PPCG - let me know if I've done anything wrong and I'll fix it.)

JavaScript (ES6), 225

A function with a string parameter, no input from file. I asked OP if this could be valid.

Test running the snippet in an EcmaScript 6 compliant browser (implementing arrow functions, template string, spread operator - Firefox, maybe Safari or MS Edge, not Chrome)

f=t=>t.split`
`.map(w=>(d[k=w.replace(/\W/g,'').toLowerCase()]={},k),d={},r=[]).map(w=>[...w].map((c,i,v)=>(d[v[i]='',x=v.join``]&&!d[x][w]&&r.push(d[x][w]=(v[i]=`(${c})`,v.join``)),v[i]=c)))&&r.sort((a,b)=>a.length-b.length)

// LESS GOLFED

Q=t=>{
  // convert to canonical form and put in a dictionary
  // each value in the dictionary is an hashtable tha will store the list
  // of words that can generate the current word, removing a letter
  d={},
  t=t.split`\n`.map(w=>(k=w.replace(/\W/g,'').toLowerCase(),d[k]={},k))
  r=[], // result array
  t.forEach(w =>
    [...w].forEach((c,i,v)=>( // for each letter in word, try to remove
      v[i]='', x=v.join``, // build string with missing letter
      v[i]='('+c+')', y=v.join``, // and build string with brackets
      v[i]=c, // restore the current letter
      d[x] && // if the word with removed letter is present in the dictionary
      !d[x][w] && // and not already from the same generating word
         r.push(d[x][w]=y) // update dictionary and add word to result array
    ))
  )
  return r.sort((a,b)=>a.length-b.length) // sort result by length
}

// TEST
function test() { R.innerHTML=f(I.value) }
textarea { height: 20em }
Test <button onclick="test()">-></button>

<textarea id=I>cat
cart
code
golf
node
scraped
scrapped
verify
versify
mart
mar
mat
ma</textarea>


Generate the k-ary necklaces of length n The set of necklaces is the set of strings, where two strings are considered to be the same necklace if you can rotate one into the other. Your program will take nonnegative integers k and n, and generate a list of the k-ary (fixed) necklaces of length n.

Necklaces will be represented by any representative string. So the necklace corresponding to the strings {ABC, BCA, CAB} can represented as ABC, BCA, or CAB.

The program will output a list of strings, such that each necklace is represented by exactly one string in the list. So for instance, outputting ABC and BCA would not be valid, since the same necklace was represented twice.

Some other details:

Your program may choose which k characters to use for the alphabet. If you prefer, you can instead choose k distinct values of any type, and have your program output lists (or some other sequence type) of those k values. (This might in fact be necessary if k is greater than the number of characters avaible in your language.) For example, if k=3, you could use {A,B,C}, {&, H, (}, or even {10, 11, 12} as your alphabet. The only restriction is that elements of your alphabet may not contain whitespace.
You may output any representative for each necklace. So for the necklace {ABC, BCA, CAB}, you may output ABC, BCA, or CAB. There is no "preferred" representative.

This is code-golf, so the shortest program wins!

Also, here is a useful test to see if your program is working. Given k and n, the list your program outputs have the length listed here. Here is an OEIS sequence corresponding to k=2.

Also, here are some examples and counterexamples. Note that these are not test cases, because any input has both an infinite number of correct and incorrect outputs. I will give inputs in the form (k,n).

Examples:

(2,2): [AA, BB, AB]
(2,2): [AA, BA, BB]
(2,2): [[1,0], [0,0], [1,1]]
(3,2): [AA, BB, CC, AB, BC, AC]
(2,3): [AAA, BBB, AAB, ABB]
(3,3): [AAA, BBB, CCC, AAB, AAC, ABB, ABC, ACB, ACC, BBC, BCC]
(0,n): [] (for positive integers n)
(k,0): [[]] (for nonnegative integers k)
(k,n): Search "necklaces with k colors and n beads" on wolfram alpha (for positive integers k and n)

Counterexamples:

(2,2): [AA, BB, AB, BA]
(2,2): [AA, BB]
(3,3): [AAA, BBB, CCC, AAB, AAC, ABB, ABC, ACC, BBC, BCC]
(3,3): [AAA, BBB, CCC, AAB, BAA, AAC, ABB, ABC, ACB, ACC, BBC, BCC]
(k,n): Any list whose length is different from this (for positive integers n)
(3,3): [AAA, BBB, CCC, AAB, BAA, AAC, ABB, ABC, ACC, BBC, BCC]

Jelly, 8 bytes

ṗṙJṂȯƲ€Q

A dyadic Link accepting the alphabet size, k, on the left and the necklace length, n, on the right which yields a list of the necklaces using the positive integers up to k as the alphabet.

Try it online!

How?

ṗṙJṂȯƲ€Q - Link: integer k, integer n
ṗ        - Cartesian power of [1,2,...,k] with n
         -   i.e. all n-length lists using alphabet [1,2,...,k]
     Ʋ€  - last four links as a monad for €ach list, L:
  J      -   range of length - i.e. [1,2,...,n]
 ṙ       -   rotate left by each of those values - i.e. get all rotations
   Ṃ     -   minimum
    ȯ    -   logical OR with L (since the minimum of an empty list is 0 not [])
      Q  - unique values the resulting list


Are all three integers distinct? You will be given 3 integers as input. The inputs may or may not be
 different from each other.
You have to output 1 if all three inputs
 are different from each other,
and 0 if any input is repeated more
 than once.

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

Python 3, 23 21 20 bytes

lambda*a:len({*a})>2

Try it online!


Write a brainfuck compiler Write a program that takes a brainfuck program and compiles it to executable machine code. You can target x86, x86_64, jvm (java bytecode) or armv6, and use one of the following executable formats: ELF, a.out, class file, exe, com. The executable should work in Linux or Windows (or Java on either).

Neither your program nor the generated executable may run any external program (such as another compiler, assembler or interpreter).

Shortest code wins.


Parsing text written the millitext font Reading the text of the millitext font

There is a font here that fits each character into a single, 1x5 pixel block. It does this (assuming you're using an LCD screen) by using the RGB channels of each pixel to expand the one pixel into three subcolumns, one for each channel. Your task is to take in a string of text encoded in this font and 'decode' it.

Millitext Alphabet

CHARACTER: 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
ENCODING:  WYWBMRRMMMWYWYWWWMWBMRMYGYGYCWMMMMMW
           MGBWMRRMMMMMRMRRRMGBMRWMMMMMRGMMMMMB
           MGWWWWWBWWWYRMWWMWGBYRWMMYMYGGMMWGGG
           MGRBBBMBMBMMRMRRMMGBMRMMMRWMBGMCWMGR
           WWWWBWWBWWMYWYWRWMWWMWMMGRCMYGWBMMGW

I've abbreviated each color to a one character symbol (R=red, G=green, B=blue, C=cyan, Y=yellow, M=magenta, W=white).

Input Format

The input format for this is pretty open. You can have the input be an array containing each column, an array containing each row, a char[][], or anything like that. You can also choose to use the full words "red", "green", "blue", with uppercase/lowercase of your choice (but it must be consistent for each word! You cannot use "RED" and also do "green" or "Blue").

If your language happens to support it, you can also have input be colors (however that might work, I don't know off-hand).

You can assume that the input will ONLY contain encoded characters in the alphabet above (in particular, there will be no spaces or punctuation in your output).

Output Format

You can either output a string or some sort of character array. You can chose whether the letters are uppercase or lowercase, but they must all have the same case.

Example

MWRRGMGYRY
MRRRMMMMRM
WWRRMWMYRM -> HELLOWORLD
MRRRMWMMRM
MWWWGMGMWY

Rules

This is code-golf, so shortest answer wins!

Test set

WMWGMWWMYYGMYWGMBMMYWYGMWYWMWRWWMYGW
GMRMMGRMMMMMMRMMBMWMRMMMRMGMRRMBMMMR
GWWMMGRYYYMWMWMGBMWYWMMMWYGWWRWGGMMM -> THEQUICKBROWNFOXJUMPEDOVERTHELAZYDOG
GMRWMGRMMMMWMRMMBMMRRMMCRMGMRRMRGMMM
GMWCWWWMYMGMMRGMWWMRWYGBWMGMWWMWGYGW

JavaScript (ES6),  103 100 93 92  90 bytes
Saved 9 bytes thanks to @ShieruAsakoto
Takes input as an array of columns. Returns an array of characters.

a=>a.map(s=>"H-L-D--VGQ87MR6TZ-KJ9WC05BUXF1YI2EON3S-A-P4"[parseInt(s,35)%1161%219%152%43])

Try it online!


Code-Golf: Permutations Write a function that takes as input a set of integers (can be a list, array or any other container with distinct numbers), and outputs the list of all its permutations.

Python (95 chars):

p=lambda s:s and sum(map(lambda e:map(lambda p:[e]+p,p(filter(lambda x:x!=e,s))),s),[]) or [[]]

It'd be nice to be beaten in the same language, but implementations in other languages are more than welcome!

Python, 52
Input is a set. Output is a list of lists.
f=lambda a:[p+[x]for x in a for p in f(a-{x})]or[[]]

This is shorter than the answer that does all the work with a builtin.


Pólya urn flip and roll Problem statement
Pólya is playing about with his urn again and he wants you to help him calculate some probabilities.
In this urn experiment Pólya has an urn which initially contains 1 red and 1 blue bead.
For every iteration, he reaches in and retrieves a bead, then inspects the colour and places the bead back in the urn.
He then flips a fair coin, if the coin lands heads he will insert a fair 6 sided die roll amount of the same coloured bead into the urn, if it lands tails he will remove half the number of the same colored bead from the urn (Using integer division - so if the number of beads of the selected colour is odd he will remove (c-1)/2 where c is the number of beads of that colour)
Given an integer n ≥ 0 and a decimal r > 0, give the probability to 2 decimal places that the ratio between the colours of beads after n iterations is greater than or equal to r in the shortest number of bytes.
An example set of iterations:
Let (x, y) define the urn such that it contains x red beads and y blue beads.
Iteration    Urn       Ratio
0            (1,1)     1
1            (5,1)     5        //Red bead retrieved, coin flip heads, die roll 4
2            (5,1)     5        //Blue bead retrieved, coin flip tails
3            (3,1)     3        //Red bead retrieved, coin flip tails
4            (3,4)     1.333... //Blue bead retrieved, coin flip heads, die roll 3

As can be seen the Ratio r is always ≥ 1 (so it's the greater of red or blue divided by the lesser)
Test cases:
Let F(n, r) define application of the function for n iterations and a ratio of r
F(0,5) = 0.00
F(1,2) = 0.50
F(1,3) = 0.42
F(5,5) = 0.28
F(10,4) = 0.31
F(40,6.25) = 0.14

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

JavaScript (ES7),  145 ... 129 124  123 bytes
Takes input as (r)(n). This is a naive solution that actually performs the entire simulation.

r=>g=(n,B=s=0,R=0,h=d=>++d<7?h(d,[0,d].map(b=>g(n,B/-~!!b,R/-~!b)&g(n,B+b,R+d-b))):s/24**-~n)=>n--?h``:s+=~B<=r*~R|~R<=r*~B

Try it online!
Too slow for the last 2 test cases.
Commented
r =>                    // r = target ratio
g = (                   // g is a recursive function taking:
  n,                    //   n = number of iterations
  B =                   //   B = number of blue beads, minus 1
  s = 0,                //   s = number of times the target ratio was reached
  R = 0,                //   R = number of red beads, minus 1
  h = d =>              //   h = recursive function taking d = 6-sided die value
    ++d < 7 ?           // increment d; if d is less than or equal to 6:
      h(                //   do a recursive call to h:
        d,              //     using the new value of d
        [0, d].map(b => //     for b = 0 and b = d:
          g(            //       do a first recursive call to g:
            n,          //         leave n unchanged
            B / -~!!b,  //         divide B by 2 if b is not equal to 0
            R / -~!b    //         divide R by 2 if b is equal to 0
          ) & g(        //       do a second recursive call to g:
            n,          //         leave n unchanged
            B + b,      //         add b blue beads
            R + d - b   //         add d - b red beads
          )             //       end of recursive calls to g
        )               //     end of map()
      )                 //   end of recursive call to h
    :                   // else (d > 6):
      s / 24 ** -~n     //   stop recursion and return s / (24 ** (n + 1))
) =>                    // body of g:
  n-- ?                 //   decrement n; if n was not equal to 0:
    h``                 //     invoke h with d = [''] (coerced to 0)
  :                     //   else:
    s +=                //     increment s if:
      ~B <= r * ~R |    //       either (-B-1) <= r*(-R-1), i.e. (B+1)/(R+1) >= r
      ~R <= r * ~B      //       or     (-R-1) <= r*(-B-1), i.e. (R+1)/(B+1) >= r


Write an interpreter for simplified 33 33 is a simple esolang I created. You may have seen me use it in a few questions. You're not going to be writing a full interpreter. The interpreter you will be writing is for a simplified version of 33.

This simplified 33 has two numeric registers: the accumulator and the counter. The accumulator holds all the post-arithmetic values, the counter is where numbers in the program come from. Both registers are initialized to 0.

0-9 | Appends the digit to the counter
a   | Adds the counter to the accumulator
m   | Subtracts the counter from the accumulator
x   | Multiplies the accumulator by the counter
d   | Divides the accumulator by the counter
r   | Divides the accumulator by the counter, but stores the remainder in the accumulator
z   | Sets the counter to 0
c   | Swaps the accumulator and counter
-----
p   | Outputs the current value of the accumulator as an ASCII character
o   | Outputs the current value of the accumulator as a formatted decimal number
i   | Outputs a newline character (0x0a)
-----
P   | Stores the ASCII value of the next character read in the accumulator
O   | Stores the next integer read into the accumulator
-----
n   | Skips the next instruction if the accumulator is not 0
N   | Skips the next instruction if the accumulator is 0
g   | Skips the next instruction if the accumulator is less than or equal to 0
G   | Skips the next instruction if the accumulator is greater than 0
h   | Skips the next instruction if the accumulator is greater than or equal to 0
H   | Skips the next instruction if the accumulator is less than 0

Test cases

Program / Input -> Output
2o          -> 0
25co        -> 25
1a0aoi      -> 11 (trailing newline)
Oo / 42     -> 42
Op / 42     -> *
1cNoo       -> 11
no          -> 0
Ogo / 2     -> 2
Ogoi / -4   -> (newline)
50a         -> (no output)
On12co / 12 -> 2

Clarifications

The input to your interpreter will be a valid simplified 33 program.
The input may be given in any acceptable format.
The output may be given in any acceptable format.
When dividing, truncate any decimal places.
A trailing newline is acceptable, but it must be consistent; as in, if there's an i at the end of the program, it should have two trailing newlines.
The accumulator and counter must be able to hold at least a signed byte (-128 to 127)
You may assume that the p instruction will never be given when the accumulator has an invalid ASCII character in it.
You may assume the O instruction will never be given unless there is a valid integer string (such as 3, -54, +23) left in the input.


An elementary challenge This challenge is inspired by this Oliver Sacks quote:

  “At 11, I could say ‘I am sodium’ (Element 11), and now at 79, I am
  gold.” ― Oliver Sacks

I want you you find numbers in a string and replace them with their corresponding elements' symbols. (1 is H, 2 is He, 3 is Li, etc.) There are a few rules to follow:

Single and double digits get replaced with their corresponding
elements as normal. Ignore 0s at the start of numbers. If there are just 0s in a number, ignore it. E.g. 1 01 10 0 00 becomes H H Ne 0 00
More than 2 digits together get divided into groups of 2. An odd
number of digits should have the extra single digit at the end. E.g. 0153 5301 153 would become HI IH PLi Because of this rule, you will only need to know the elements from 1 to 99
Numbers shall be treated the same no matter what characters surround
them and commas and decimal points are not parts of numbers. P90X
42,800 3.14159 would become PThX Mo,Hg0 Li.SiPF

Example Inputs/Outputs (I/O):

I: 32289216
O: GeNiUS

I: J08017 5811
O: JOHN CeNa

I: M18227 0592tt10r
O: MArTiN BUttNer

I: De072816
O: DeNNiS

I: D088r1907085
O: DOOrKNOB

I: 13ex A.
O: Alex A.

Input will be in the closest format to a string that your language has.

A periodic table for reference:

This is code-golf, so your program will be scored in bytes.

Mathematica, 96 94 89 bytes

StringReplace[#,n:DigitCharacter~Repeated~2/;(d=FromDigits@n)>0:>d~ElementData~"Symbol"]&

Mma has several datasets...


Evaluate polynomial expression string Create a function which takes a polynomial equation, a value for x and returns the result of the operation.

Example: given 4x^2+2x-5 and x=3 output 37. This is the result of 4(3)^2+2(3)-5

Assume all polynomials are valid
Polynomial format will always be coefficient(variable)^exponent => 4x^2 except :

When exponent is 1 it will be coefficient(variable) => 4x
When coefficient is 1 it will be (variable)^exponent => x^2

Polynomials are one variable only
Use of external libraries are forbidden
The coefficient and variable input can be positive and negative numbers.

Test cases

("3x^3-5x^2+2x-10", 5)          => 250
("10x^4-5x^3-10x^2+3x+50", 3)   => 644
("10x+20", 10)                  => 120
("-20x^2+20x-50", -8)           => -1490
("9", 5)                        => 9
("8x^2+5", 0)                   => 5

Update

Polynomial format will always be coefficient(variable)^exponent => 4x^2 except :

When exponent is 1 it will be coefficient(variable) => 4x
When coefficient is 1 it will be (variable)^exponent => x^2

Removed the rule of negative exponent. My mistake. A valid polynomial does not contain negative exponent
An exponent of 0 would be just coefficient
Added test case for input 0

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

JavaScript (ES7), 48 bytes

Based upon a suggestion from @RickHitchcock

Expects X in uppercase. Takes input in currying syntax (p)(X).

p=>X=>eval(p.replace(/[X^]/g,c=>c<{}?'*X':'**'))

Try it online!

JavaScript (ES7), 49 bytes

Same approach as @DeadPossum. Takes input in currying syntax (p)(x).

p=>x=>eval(p.split`x`.join`*x`.split`^`.join`**`)

Try it online!


Shortest Way of creating a basic Space Invaders Game in Python Your challenge is to create a basic version of Space Invaders in Python
Rules

Program must be not written in Py3K
All levels must be randomly generated
There must be a HUD showing the players score

The winner would be the answer which uses the least amount of code
Some Questions
Q: How detailed do the aliens and other elements have to be?
A: The aliens should be Block ASCII
Q: Can the bunkers be simplified to rectangles?
A: Yes, as long as they are filled
Q: How many enemies/bunkers do there have to be?
A: Number of Enemy's are chosen by random. 4 bunkers
Q: Do we need to implement the "mystery ship" that goes across the top of the screen?
A: No
Q:Do the symbols/characters that make up the laser cannon and the aliens need to be different?
A: Yes
Q: Do they need different shapes?
A: Yes
Q: Does it matter how fast the bullets/lasers travel?
A: No

3060 3031 characters

OKAY, this was fun. But I very highly doubt that my code is short enough to compete, or if it's basic enough. I'm new to code golf but regardless, I had fun and that's what matters. I'm too used to object-oriented programming so a lot of my code is probably just too much objects...
Game runs solely in the console, and I shortened most of the code with the exec''''''.replace() method. Complete with input of your name, random enemy firing, walls, aliens are randomly generated, worth 50 points each. each time you fire you lose one point so that you lose points if you just hold space in one spot to beat the level. Enemy speed increases each level, capped at every 0.2 seconds. Prints the level number, and game over at the bottom, your name,lives, and score at the top left. you have 3 lives. Ungolfed version is ~9500 characters, but I'll leave that out of here for now

instructions: fire with space, move with a and d, exit with x

let me know what think, if I can improve on anything

edit: forgot that msvcrt is Windows-Only. perhaps I can make a unix version too...

exec'''import threading as t
import msvcrt,Queue,time,random,os
u=raw_input('name:')
r=range
@Z:
$~(S):S.w=78;S.h=30;S.X();S.l='';S.Q=[];S.q=[];S.m=''
$J(S,x,y,c):S.q.append([x,y,c])
$X(S):S.s=[[' '^y in r(78)]^x in r(30)]
$V(S):
?s='';S.X()
?^x,y,z in S.q:S.s[y][x]=z
?S.q=[]
?^x in S.s:
? ^y in x:s+=y
? s+='\\n'
?s+=S.m.center(S.w)
?if s!=S.l:os.system('cls');S.l=s;print s
@E(Exception):pass
@C:
$~(S,g,c,p):S.g=g;S.c=c;S.p=p;S.s=[]
$M(S,a,d):
?if (a<0 and S.p[d]==0) or (a>0 and S.p[d]==(S.g.z.h if d else S.g.z.w)-1):raise E()
?S.p[d]+=a
$X(S):S.s.remove(S)
@A(C):
$~(S,g):C.~(S,g,'A',[39,28])
$M(S,a,d=0):
?try:C.M(S,a,d)
?except E:pass
@Y(A):
$~(S,g,p):C.~(S,g,'Y',p);S.s=g.a
@B(C):
$~(S,g,p,n):C.~(S,g,'|'if n<0 else'*',[p[0],p[1]+n]);S.s=g.b;S.d=n;S.a=0 if n<0 else 1
$M(S):
?try:C.M(S,S.d,1)
?except E:S.X()
$b(S):S.g.z.J(S.p[0],S.p[1],'X');S.g.z.V();S.X()
$co(S):
?^w in S.g.w:
? if S.p==w.p:S.b();w.X()
?if S.a:
? if S.p==S.g.p.p:S.b();S.g.d()
?else:
? ^a in S.g.a:
??if S.p==a.p:S.b();S.g.P(50);a.X()
@W(C):
$~(S,g,p):C.~(S,g,'#',p);S.s=g.w
@I(t.Thread):
$~(S,g):t.Thread.~(S);S.f=1;S.c={'a':g._g4,'d':g._g3,'x':g._X,' ':g._fi};S.start()
$run(S):
?while S.f:
? c=msvcrt.getch()
? if c in S.c:S.c[c]()
$X(S):S.f=0
@G:
$~(S):S.z=Z();S.x=3.0;S.c=0;S.b=[];S.Q=Queue.Queue();S.I=I(S);S.g2=0;S.g1=0;S.do=0;S.f=1;S.v=0;S.l=3;S.ti=[];S.G(1);S.O()
$O(S):
?while S.f:
? time.sleep(0.02)
? if not S.a:S.G(1)
? S.ch();S.B();S.u()
$u(S):
?S.z.X();S.P(0)
?s=u+' '+`S.l`
?^i in r(len(s)):S.z.J(i,0,s[i])
?^i in S.a+S.b+[S.p]+S.w:S.z.J(i.p[0],i.p[1],i.c)
?S.z.V()
$ch(S):
?try:
? while not S.Q.empty():S.Q.get_nowait()();S.Q.task_done()
?except Queue.Empty:pass
$cl(S):
?try:
? while not S.Q.empty():S.Q.get_nowait();S.Q.task_done()
?except Queue.Empty:pass
$_g4(S):
?if not S.g2:S.g2=1;S.Q.put(S.g4)
$g4(S):S.p.M(-1);S.g2=0
$_g3(S):
?if not S.g1:S.g1=1;S.Q.put(S.g3)
$g3(S):S.p.M(1);S.g1=0
$_X(S):S.I.X();S.Q.put(S.X)
$X(S):S.f=0;S.I.X();S.st()
$_fi(S):
?if not S.do:S.do=1;S.Q.put(S.fi)
$fi(S):S.b.append(B(S,S.p.p[:],-1));S.do=0;S.P(-1)
$_af(S):S.Q.put(S.af)
$af(S):c=random.choice(S.a);S.b.append(B(S,c.p[:],1));S.nt(random.uniform(0.1,2),S._af)
$nt(S,n,f):x=t.Timer(n,f);S.ti.append(x);x.start()
$st(S):
?^i in S.ti:i.cancel()
$G(S,n=0):
?S.st();S.cl();S.p=A(S);S.a=[];S.w=[];S.b=[]
?^x in[[i,o]^i in r(30)^o in r(3,10)]:
? if random.randint(0,99)%4==0:S.a.append(Y(S,x))
?S._m();S._af();f=[]
?^x in [6,27,46,65]:f+=[[z,y]^z in r(x,x+6)^y in r(23,26)]
?^i in f:S.w.append(W(S,i))
?S.v+=n;S.z.m='Level %s'%S.v;S.u()
?if S.x>0.2:S.x=1.6 - S.v*0.1
?S.m1=0;S.m2=0;S.k=1;time.sleep(3)
$_m(S):S.Q.put(S.m)
$m(S):
?x=0
?if S.m2:S.m2=0;S.m1=0;S.k=-S.k;x=1
?^i in S.a:i.M(*(abs(S.k),1)if x else(S.k,0))
?if S.m1==47:S.m2=1
?else:S.m1+=1
?S.nt(S.x,S._m)
$B(S):
?^i in S.b:i.M();i.co()
$d(S):
?S.l-=1
?if S.l==0:S.z.m='Game Over!';S.X();return
?S.G(0)
$P(S,n):
?S.c+=n if S.c+n>0 else 0;x=`S.c`
?^n in r(len(x)):S.z.J(n,1,x[n])
G()'''.replace('@','class ').replace('?','  ').replace('$',' def ').replace('^','for ').replace('~','__init__')

what the screen looks like:

Blazer 3
488            |

      YY  Y         YY  Y Y Y     Y
      YY  Y   YY  Y  Y           Y
      Y   Y    Y      Y    YY
                           Y   Y  Y
       YY Y   Y   Y Y             Y
           Y  YY YX Y Y
       Y       Y |                 Y

                   |

         *

                    |

      ####           |     ######             ######             ######
      ######               ######             ######             ######
      ######               ######             ######             ######

                     A

                                   Level 1

edit: managed to remove something I accidentally left in I wasn't using anymore


Find the longest rep digit Your task is to take a positive number as input, n, and output the length of the longest rep-digit representation of n in any base. For example 7 can be represented as any of the following

111_2
21_3
13_4
12_5
11_6
10_7
7_8

The rep-digits are 111_2 and 11_6, 111_2 is longer so our answer is 3.

This is a code-golf question so answers will be scored in bytes, with fewer bytes being better.

Test Cases

1   -> 1
2   -> 1
3   -> 2
4   -> 2
5   -> 2
6   -> 2
7   -> 3
8   -> 2
9   -> 2
10  -> 2
11  -> 2
26 -> 3
63  -> 6
1023-> 10

Sample implementation

Here is an implementation in Haskell that can be used to generate more test cases.

f 0 y=[]
f x y=f(div x y)y++[mod x y]
s x=all(==x!!0)x
g x=maximum$map(length.f x)$filter(s.f x)[2..x+1]

Try it online!

Jelly, 9 bytes

b‘Ḋ$EÐfZL

A monadic link accepting and returning numbers

Try it online! or see a test suite (inputs one to 32 inclusive).

How?

b‘Ḋ$EÐfZL - Link: number, n
   $      - last two links as a monad:
 ‘        -   increment = n+1
  Ḋ       -   dequeue (with implicit range build) = [2,3,4,...,n+1]
b         - convert to those bases
     Ðf   - filter keep if:
    E     -   all elements are equal
       Z  - transpose
        L - length (note:  length of the transpose of a list of lists is the length of the
          -                longest item in the original list, but shorter than L€Ṁ)

...or maybe I should have done:

bḊEÐfZLo1

For the Lo1z.


Compute the Discrete Cosine Transform Implement the Discrete Cosine Transform (DCT). This may implemented as either a function or a program and the sequence can be given as either an argument or using standard input. Your program must be able to handle sequences of any length (assuming a hypothetical version of your language which has no limits on things like memory and integer size).

There was a previous challenge for DFT, now lets compute DCT! ;-)

Use the DCT-II definition from Wikipedia:

Your program takes a sequence xn as input, and must produce the corresponding sequence Xk. In this formula, the cosine is in radians.

Rules

This is code-golf so the shortest solution wins.
Builtins that compute the DCT in forward or backward (also known as inverse) directions are not allowed.
Floating-point inaccuracies will not be counted against you.
You don't have to use the exact algorithm shown here, as long as you produce the same results.

Jelly, 15 bytes

LḶµ+.×þ÷L-*Ḟ³æ.

Try it online!

This uses the identity that cos(pi * x) = real(e^(i * pi * x)) = real((-1)^x)

Explanation

LḶµ+.×þ÷L-*Ḟ³æ.  Input: array A
L                Length
 Ḷ               Lowered range - [0, 1, ..., len(A)-1]
  µ              Begin a new monadic chain
   +.            Add 0.5
     ×þ          Outer product using multiplication
       ÷         Divide by
        L        Length
         -*      Compute (-1)^x
           Ḟ     Real part
             æ.  Dot product with
            ³    The first argument (A)


Remainder When N divided by 2^M Write the shortest code to find the remainder when an input number N is divided by 2^M. You cannot use /,* and % operator.

Input Specification
Number of test cases followed by a pair of integers on each line.

Sample Input
1
150 6

Sample Output
22

Limits
1<T<1000
1<N<2^31
1<B<31

Time Limit
1 Sec


Advent Challenge 3: Time to remanufacture the presents! << Prev Next >>

Unfortunately, Santa was not able to catch the elves in time! He has to go back to manufacturing presents now. Since the elves are definitely not Santa's slaves, he has to figure out the expenses for how much to pay them.

Challenge

Given some information for the presents, determine the cost of manufacturing all of them.

Each present is put in a cardboard box and wrapped with wrapping paper, with a ribbon wrapped around it at the very end. The wrapping paper is magical and requires no overlap, so the amount of wrapping paper used is precisely equivalent to the surface area of the box. All presents are rectangular prisms because that way Santa can store them more compactly. The ribbon goes around in all three directions (so the length of ribbon used for wrapping is equal to the sum of the three different perimeters).

The present itself has a known cost, fortunately. Cardboard costs $1 per square meter, and wrapping paper costs $2 per square meter. (Hint: You can just multiply the surface area by 3 :P). Ribbon costs $1 per meter.

Format Specifications

The input will be given as a list of presents where each present contains the cost of the actual item and the three dimensions of the present box. Your output should be the total cost required.

To be exact, the formula for the cost of a single present with item cost c and dimensions x, y, and z is c + 6 * (x * y + y * z + z * x) + 4 * (x + y + z).

Test Cases

[[7, 8, 6, 7], [7, 7, 5, 5], [8, 9, 6, 7], [6, 5, 10, 10], [5, 9, 6, 7], [9, 9, 10, 6], [8, 10, 10, 6], [6, 5, 7, 9], [7, 10, 8, 8], [5, 9, 9, 10]] -> 11866
[[5, 10, 8, 9], [8, 8, 5, 8], [8, 7, 7, 6], [5, 9, 9, 10], [9, 7, 5, 8], [9, 8, 9, 5], [7, 5, 6, 7], [5, 7, 6, 10]] -> 8854
[[9, 8, 8, 8], [10, 9, 8, 5], [10, 7, 5, 5], [10, 10, 6, 6], [8, 5, 8, 7]] -> 4853
[[7, 7, 8, 10], [8, 10, 7, 8], [9, 7, 7, 8], [8, 5, 10, 5], [6, 6, 6, 8], [8, 9, 7, 5], [8, 5, 6, 5], [7, 9, 8, 5], [10, 10, 10, 8]] -> 9717
[[5, 8, 9, 7], [5, 8, 7, 10], [5, 7, 7, 6], [5, 5, 5, 6], [9, 9, 5, 7], [5, 6, 7, 8], [8, 5, 8, 7], [6, 9, 5, 5], [10, 10, 9, 10]] -> 9418
[[9, 9, 7, 10], [5, 8, 7, 9], [5, 5, 9, 8], [10, 5, 9, 10], [8, 5, 10, 7], [8, 9, 5, 5], [5, 10, 6, 10]] -> 8178
[[5, 9, 5, 8], [7, 8, 10, 6], [7, 10, 7, 10], [8, 9, 7, 5], [5, 7, 8, 6], [9, 9, 6, 10], [6, 5, 9, 9], [7, 9, 9, 9]] -> 9766
[[7, 10, 5, 10], [8, 10, 8, 9], [8, 6, 7, 8], [6, 9, 8, 5], [6, 7, 10, 9], [7, 6, 5, 8]] -> 7118
[[10, 6, 7, 5], [5, 9, 5, 9], [9, 7, 8, 5], [6, 6, 9, 9], [9, 9, 6, 9], [10, 5, 8, 9], [7, 5, 6, 10], [9, 10, 5, 5]] -> 8007
[[8, 10, 7, 8], [9, 10, 5, 8], [6, 7, 5, 6], [10, 10, 9, 8], [7, 5, 8, 9], [10, 10, 6, 7], [10, 8, 9, 10], [5, 10, 5, 5]] -> 9331

Rules

Standard Loopholes Apply
The input and output may be given and presented in any reasonable format
You must take the input as a list of presents, not 4 lists of the attributes.
This is a code-golf, so the shortest answer in bytes wins
No answers will be accepted

Hopefully this challenge is easier than the previous ones :P

Note: I drew inspiration for this challenge series from Advent Of Code. I have no affiliation with this site

You can see a list of all challenges in the series by looking at the 'Linked' section of the first challenge here.


Rotational symmetry of string A rotation "is made by splitting a string into two pieces and reversing their order". An object is symmetrical under an operation if the object is unchanged after applying said operation. So, a "rotational symmetry" is the fact that a string remains unchanged after "rotation".

Given a non-empty string s consisting of only letters from a to z, output the highest order of the rotational symmetry of the string.

Testcases:

input        output
a            1
abcd         1
abab         2
dfdfdfdfdfdf 6

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

Retina, 15 bytes

(^.+?|\1)+$
$#1

Try it online!

Matches the entire string by repeating a substring (shorter substrings are prioritised due to the ungreedy .+?) and replaces the entire string with the number of repetitions we used.


Output the nth 'boring' number There are 9 main types of numbers, if you categorise them by the properties of their factors. Many numbers fall into at least one of these categories, but a few don't. The categories are as follows:

Prime - no integer divisors other than itself and one
Primitive abundant - A number \$n\$ whose factors (excluding \$n\$) sum to more than \$n\$, but for any factor \$f\$ of \$n\$, the sum of the factors of \$f\$ sum to less than \$f\$
Highly abundant - A number \$n\$ whose factors (including \$n\$) sum to more than that of any previous number
Superabundant - A number \$n\$, such that the sum of the factors of \$n\$ (including \$n\$) divided by \$n\$ is greater than the sum of factors of \$g\$ over \$g\$ for any value \$0<g<n\$
Highly composite - A number \$n\$ which has more factors than \$g\$, where \$g\$ is any number such that \$0<g<n\$
Largely composite - same as highly composite, but \$n\$ can have also have equally as many factors as \$g\$
Perfect - A number that is exactly equal to the sum of its factors (excluding itself)
Semiperfect - A number that can be made by summing up two or more of its factors (excluding itself)
Weird - A number \$n\$ that is not semiperfect, but which's divisors sum to more than \$n\$.

A so-called 'boring number' is any positive, non-zero integer which does not fit into any of these categories.

Your job is to create the shortest possible program which can, given a positive number \$n\$, outputs the \$n\$th boring number.

Note: I am aware there are more categories, but I wanted to avoid using mutually exclusive ones (such as deficient and abundant), because then every number would fall into one of them.

Rules

Standard loopholes apply; standard I/O methods apply.
All inputs will be positive, non-zero integers, a single output is expected.
n can be 0- or 1- indexed.
This is code-golf, so shortest answer in bytes wins.

Tests

The first 20 boring number are:

9, 14, 15, 21, 22, 25, 26, 27, 32, 33, 34, 35, 38, 39, 44, 45, 46, 49, 50

JavaScript (ES6),  226 220  209 bytes
Saved 11 bytes thanks to @HermanL
Input is 1-indexed.

f=(x,n=m=c=1,D=k=>k?n%k?D(k-1):[k,...D(k-1)]:[],S=a=>s=eval(a.join`+`))=>(S(a=D(n))>m?m=s:0)|(s=a.length)<3|(s<c?0:c=s)|a.reduce((a,x,i)=>i?[...a,...a.map(y=>[...y,x])]:a,[[]]).some(a=>S(a)>=n)||--x?f(x,n+1):n

Try it online!
Optimizations are based on the following properties:

All primitive abundant numbers are either semiperfect or weird.
All highly composite numbers are largely composite.
All superabundant numbers are highly abundant.


Stringsplode the String! The challenge is relatively simple, but will hopefully lead to some wonderfully creative answers. The task is to take a string as an input (via command line, function parameter etc.) and output/return a stringsploded version of it.

A stringsploded version of a string is its first letter followed by its first 2 letters, followed by its first 3 letters,... until you finally output the complete word.

You are guaranteed that the input will consist of printable ASCII characters and that the input will all be on one line (no new line characters).

Here are examples to clarify what stringsplosions are:

Input                 Output
==================================================================
"Code"       ---->   "CCoCodCode"
"name"       ---->   "nnanamname"
"harambe"    ---->   "hhaharharaharamharambharambe"
"sp aces?"   ---->   "sspsp sp asp acsp acesp acessp aces?"
"1234"       ---->   "1121231234"
"ss"         ---->   "sss"

This is code golf so shortest code wins + up votes for interesting uses of your respective language.

Good luck!

gs2, 1 byte

x

gs2 takes input from STDIN, and pushes it to the stack as a string.
x is the prefixes built-in, returning a list of all prefixes of the argument, in ascending-length order.
The resulting list of strings is implicitly printed one-by-one, without a delimiter, when the program terminates.


Reconstruct My Matryoshka Dolls Background

A matryoshka doll (or Russian nesting doll) is a set of dolls that fit inside of each other. I've accidentally mixed up my collection of matryoshka dolls and I don't remember which one goes inside which.

Objective

Given a list of unique strings, sort them into nested matryoshka dolls. Each string is an individual doll, and a matryoshka doll is a list of strings.

Rules

Let min(a,b) be the lexicographic min of strings a and b. Let a ⊂ b denote that a is a substring of b. Then,

The list of matryoshka dolls must be sorted lexicographically
String a can fit into string b if a ⊂ b
If a ⊂ b and a ⊂ c, then a will go inside min(b,c)
If both a ⊂ c and b ⊂ c, but a ⊄ b b ⊄ a, then only min(a,b) will go inside c
If both a ⊂ c and b ⊂ c, and also a ⊂ b, then only b will go inside c. I.e., superstrings go before substrings so that the matryoshka isn't prematurely terminated.

Examples

In:
hahaha, hah, lol, lololol, bahaha, bah, haha, ah

Out:
bahaha, bah, ah
hahaha, haha, hah
lololol, lol

In:
aa, aaaa, a, aaaaaaaaaa

Out:
aaaaaaaaaa, aaaa, aa, a

Python 2, 298 bytes

def f(x,E=enumerate):
 o=[]
 while any(x):
	for k,p in E(x):
	 e=0
	 if sum(i(p,j)for j in x)<1:
		for d,r in E(o):
		 if i(p,r[-1])*((r[-1]<e)or e==0):m,e=d,r[-1]
		if e:o[m]+=[p]
		else:o+=[[p]]
		x[k]=''
 print sorted(o)
i=lambda p,b:(b!=p)*any([p==b[j:j+len(p)]for j in range(len(b)-len(p)+1)])

Try it online!

-28 bytes with tips from @dylnan, bug find by @Dennis, and bug fix by @Mr.Xcoder