问:
Residue Number System
In the vein of large number challenges I thought this one might be interesting.

In this challenge, we will be using the Residue Number System (RNS) to perform addition, subtraction, and multiplication on large integers.

What is the RNS

The RNS is one of many ways that people have developed to identify integers. In this system, numbers are represented by a sequence of residues (which are the results after a modulus operation (i.e. the remainder after integer division)). In this system, each integer has many representations. To keep things simple, we are going to limit things so that each integer is uniquely represented. I think it is easier to describe what is happening with a concrete example.

Let us look at the first three prime numbers: 2, 3, 5. In the RNS system, we can use these three numbers to uniquely represent any number that is less than 2*3*5 = 30 using residues. Take 21:

21 is less than 30, so we can represent it using the results after modding by 2, 3, and 5. (i.e. the remainder after integer dividing by 2, 3, and 5)

We would identify 21 with the following sequence of integers:

21 ~ { 21 mod 2, 21 mod 3, 21 mod 5 } = {1, 0, 1}

And so in our RNS system, instead of "21", we would use {1,0,1}.

In general given an integer n, we represent n as { n mod 2, ..., n mod p_k } where p_k is the smallest prime such that n is less than the product of all primes less than or equal to p_k.

Another example, say we have 3412. We need to use 2,3,5,7,11,13 here because 2*3*5*7*11*13=30030 whereas, 2*3*5*7*11=2310 which is too small.

3412 ~ { 3412 mod 2, 3412 mod 3, 3412, mod 5, ... , 3412 mod 13 } = { 0, 1, 2, 3, 2, 6 }

You notice that using this system we can represent very large numbers relatively painlessly. Using {1, 2, 3, 4, 5, 6, 7, 8, ... } residues, we can represent numbers up to {2, 6, 30, 210, 2310, 30030, 510510, 9699690 ...} respectively. ( Here is the series )

Our task

We will be using these residues to perform +, -, and * on large numbers. I will describe these processes below. For now here are the input and output specs.

Input

You will be given two (potentially very large) numbers via a stdin or function argument. They will be given as strings of base 10 digits.

For the purposes of outlining the problem further, we call the first input n and the second m. Assume n > m >= 0.

You will also be given + or - or * to indicate the operation to perform.

Output

Let x be an integer. We will use [x] to refer to the RNS representation described above of x.

You are to output [n] <operator> [m] = [result]

How to perform the operations in RNS

These operations are relatively simple. Given two numbers in RNS notation, to add, subtract, or multiply them, simply perform the given operations component-wise and then take the modulus.

i.e.

{ 1, 2, 3 } + { 1, 1, 4 } = { (1+1) mod 2, (2+1) mod 3, (3+4) mod 5 } = {0, 0, 2}

Note that if the number of residues used to represent two different numbers are not the same, when performing operations, you will need to extend the "shorter" number so that it has the same number of residues. This follows the same process. See the test cases for an example.

The same goes if the result requires more residues than either input. Then both inputs need to be "extended".

Important Details

We will be dealing with big numbers here, but not arbitrarily large. We will be responsible for numbers up to the product of the first 100 primes (see below). To this end, you are given the first 100 primes for free (no byte cost). You may stick them in an array called p or something idiomatic to your language and then subtract the number of bytes used to initiate this array from your final total. This of course means that they may be hard-coded or you may use a built-in to generate them.

If for someone reason this is the default integer representation used in your language. That is fine.

You may not use any Arbitrary Precision Integer type unless it is the default of your language. If it is the default, you may not use it to store integers that would not typically fit in 64 bits.

To be clear, each integer will always be represented with the fewest residues possible. This goes for both input and output.

I think the other specs should prevent this, but to be redundant: you may  not perform the given operation on the inputs and then and then change everything to RNS and then output. You must change the inputs to RNS and then perform the operations to produce the output.

Test Cases

Input:

```<code>n = 10
m = 4
+
</code>```

Output:

```<code>{ 0, 1, 0 } + { 0, 1 } = { 0, 2, 4 }
</code>```

Explanation:

First, change each number to its RNS representation as described above:

10 ~ {0,1,0} and 4 ~ {0,1}. Notice that when we want to do component-wise addition, that 10 has more components than 4. Therefore we must "extend" the shorter number. So we will briefly write 4 ~ {0,1} --> {0,1, 4 mod 5} = {0,1,4}. Now we proceed with addition and then take the modulus.

Input

```<code>n=28
m=18
+</code>```

Output:

```<code> [ 0, 1, 3 ] + [0, 0, 3 ] = [ 0, 1, 1, 4 ]</code>```

Input (me mashing my face on the keyboard)

```<code>n=1231725471982371298419823012819231982571923
m=1288488183
*</code>```

Output (broken onto separate lines for readability):

```<code>[1, 2, 3, 6, 2, 10, 2, 1, 12, 16, 7, 15, 34, 29, 31, 5, 55, 32, 66, 61, 3, 76, 52, 14, 65, 44, 99, 57 ]
*
[1, 0, 3, 3, 4, 8, 9, 10, 8, 0 ]
=
[1, 0, 4, 4, 8, 2, 1, 10, 4, 0, 17, 7, 27, 21, 44, 51, 56, 9, 6, 9, 12, 0, 52, 36, 43, 68, 99, 24, 96, 39, 96, 66, 125]
</code>```

n requires 28 primes. m requires 10. n*m requires 33.

Input

```<code>n=8709668761379269784034173446876636639594408083936553641753483991897255703964943107588335040121154680170867105541177741204814011615930342030904704147856733048115934632145172739949220591246493529224396454328521288726490
m=1699412683745170450115957274739962577420086093042490863793456500767137147999161679589295549397604032154933975242548831536518655879433595016
-</code>```

Output:

```<code>[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 509]
-
[0, 2, 1, 6, 1, 12, 11, 18, 14, 28, 21, 36, 37, 42, 16, 52, 41, 60, 16, 70, 49, 78, 80, 88, 49, 100, 13, 106, 4, 112, 68, 130, 36, 138, 37, 150, 0, 162, 8, 172, 163, 180, 18, 192, 129, 198, 135, 222, 78, 228, 90, 238, 57, 250, 36, 262, 87, 270, 206, 280, 193, 292, 253, 310, 224, 316, 57, 336, 48, 348]
=
[0, 1, 4, 1, 10, 1, 6, 1, 9, 1, 10, 1, 4, 1, 31, 1, 18, 1, 51, 1, 24, 1, 3, 1, 48, 1, 90, 1, 105, 1, 59, 1, 101, 1, 112, 1, 0, 1, 159, 1, 16, 1, 173, 1, 68, 1, 76, 1, 149, 1, 143, 1, 184, 1, 221, 1, 182, 1, 71, 1, 90, 1, 54, 1, 89, 1, 274, 1, 299, 1, 266, 1, 228, 1, 340, 1, 170, 1, 107, 1, 340, 1, 88, 1, 157, 1, 143, 1, 22, 1, 22, 1, 58, 1, 296, 1, 371, 1, 140]</code>```

n uses 100 primes. m uses 70 primes. n-m uses 99 primes.

I checked these using the ChineseRem built-in implementation of the Chinese Remainder theorem on GAP (which basically takes RNS numbers and changes them to base 10 integers). I believe they are correct. If something seems fishy, please let me know.

For those who care, the product of the first 100 primes is:

```<code>471193079990618495316248783476026042202057477340967552018863483961641533584503
422120528925670554468197243910409777715799180438028421831503871944494399049257
9030720635990538452312528339864352999310398481791730017201031090</code>```

This number is 1 larger than the maximal number we can represent using the given system (and 100 prime limitation).

Somewhat related

答:
GAP

Some Background: I will admit that when I created this question, so many months ago, I did not have a method for solving the hard part of this question: determining the correct number of primes to use. We have a lot of very intelligent people on this site, and I really expected that someone would figure out a way to do it fairly quickly. However, as this did not happen, I wasn't even sure that it was truly possible to solve this problem. So, I had to take the time to devise a method. I believe that what I have done does not break any of the rules in this challenge, of course I would love this to be fact checked.

I also slightly regret the choice of code-golf because the solutions are slightly more in depth than would usually fit the tag format. Having said this, to follow site rules, there is a "golfed" version of my solution at the bottom of this post.

Code

```<code>### The first 100 primes;
primes := Primes{[1..100]};

### In many of the functions below, the 'string' variable is a string of digits
###

### Returns the 'index' digit of 'string' as an integer
GetValueAsInt := function(string, index)
    return IntChar(string[index]) - 48;
end;

### Used in the 'modulus' function. See that comment for more information.
### Calculates the contribution to the modulus of a digit 'digit' in the 10^power place.
### 'integer' is the modulus
digit_contribution := function(digit, integer, power)
    local result, i;
    result := 1;
    for i in [0..power-1] do
        result := ( result * (10 mod integer) ) mod integer;
    od;
    result := (result * (digit mod integer) ) mod integer;
    return result;
end;

### This modulus function is used to calculate the modulus of large numbers without storing them
##### as large numbers.
### It does so by breaking them into digits, and calculating the contribution of each digit.
### e.g. 1234 mod 5 = (1000 mod 5)(1 mod 5) + (200 mod 5)(2 mod 5) + (10 mod 5)(3 mod 5) + (4 mod 5)
### It actually mods after every calculation to ensure that we never get a number larger
##### than the modulus ('integer') squared, which will never be even close to 10^64-1
modulus := function(string, integer)
    local i, result, digit, len;
    len := Length(string);
    result := 0;
    for i in [1..len] do
        digit :=  IntChar(string[i]) -48;
        result := ( result + digit_contribution(digit, integer, len-i) )  mod integer;
    od;
    return result;
end;

### This returns the product of the first i-1 primes (mod j). It must not (and does not)
##### ever store an integer larger than 2^64-1
phi_i := function(i,j)
    local index, result;
    result := 1;
    for index in [1..i-1] do
        result := ( result * primes[index] ) mod primes[j];
    od;
    return result;
end;

### Calculates the first residues of 'string' mod the first 100 primes
get_residues := function(string)
    local p, result;
    result := [];
    for p in primes do
        Add( result, modulus(string, p) );
    od;
    return result;
end;

### Gets the ith element in the partial_chinese array, given the previous elements
### See the explanation section and partial_chinese function for more info
get_partial_i := function( i, residues, previous_array )
    local index, result;
    result := residues[i];
    for index in [1..Length(previous_array)] do
        result := ( result - previous_array[index]*phi_i(index,i) ) mod primes[i];
    od;
    result := ( result / phi_i(i,i) ) mod primes[i];
    return result;
end;

### returns an array such that the sum of prod_primes(i)*array[i] is equal to the integer value
##### that is represented by the residues. (It basically just does the CRT without
##### actually summing everything.) prod_primes(i) is the product of the first i-1 primes
### See the explanation for a bit more info
### This is what allows us to determine the minimal number of primes to represent a RNS number
partial_chinese := function( string )
    local array, i, residues;
    residues := get_residues(string);
    array := [];
    for i in [1 .. Length(primes)] do
        Add( array, get_partial_i( i, residues, array ) );
    od;
    return array;
end;

### Same as partial_chinese but takes input in a different form.
partial_chinese_from_residues := function(residues)
    local array, i;
    array := [];
    for i in [1 .. Length(primes)] do
        Add( array, get_partial_i( i, residues, array ) );
    od;
    return array;
end;

### gives you the number of primes needed to represent an integer. Basically asks how
##### many trailing zeros there are in the chinese array.
get_size := function(string)
    local array, i, len, result;
    array := partial_chinese(string);
    len := Length(array);
    for i in [0..len-1] do
        if  not (array[len-i] = 0) then
            return len -i;
        fi;
    od;
    Print("ERROR: get_size().\n");
    return 0;
end;

### Same as above but with different input format
get_size_from_residues := function(residues)
    local array, i, len, result;
    array := partial_chinese_from_residues(residues);
    len := Length(array);
    for i in [0..len-1] do
        if  not (array[len-i] = 0) then
            return len -i;
        fi;
    od;
    Print("ERROR: get_size().\n");
    return 0;
end;

### the actual function. inputs are all strings
f := function(in1, in2, opperation)
    local residues_1, residues_2, residues_result, i;
    residues_1 := get_residues(in1);
    residues_2 := get_residues(in2);
    residues_result := [];
    if opperation = "+" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] + residues_2[i] ) mod primes[i]);
        od;
    elif opperation = "*" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] * residues_2[i] ) mod primes[i]);
        od;
    elif opperation = "-" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] - residues_2[i] ) mod primes[i]);
        od;
    fi;
    Print(residues_1{[1..get_size(in1)]}, " ", opperation, " ", residues_2{[1..get_size(in2)]}, " = ", residues_result{[1..get_size_from_residues(residues_result)]} );
end;
</code>```

Explanation:

To start off, we calculate all the 100 of the residues for both inputs. We do this with the modulus function in the code. I tried to be careful so that we use the built-in mod function after every step. This ensures that we never have a number that is larger than 540^2, which is 1 less than the 100th prime squared.

After we have all the residues, we can perform the given operation and mod each entry again. Now we have a unique designator for the result, but we need to determine the minimal number of entries that we have to use to represent the result and each of the inputs.

Figuring out how many residues we actually need is by far the hardest part of this problem. To determine this, we perform most of the steps of the Chinese Remainder Theorem (CRT). However, we obviously have to make modifications so that we don't end up with numbers that are too large.

Let prod(i) be the sum of the first i-1 primes. For example,

```<code>prod(1) = 1
prod(2) = 2
prod(3) = 6
prod(4) = 30
etc
</code>```

Let X be an integer. Let {r_i} be the residues of X, that is

```<code>r_i = X mod p_i
</code>```

Where p_i is the ith prime. This is for 1<i<=100 in our case.

Now we are going to use the CRT to find a sequence {u_i} such that the sum over i of prod(i) * u_i is equal to X. Note that each u_i is also technically a residue, as u_i < p_i. Furthermore, if X < prod(i) then u_i = 0. This is of critical importance. It means that by examining trailing zeros, we can determine how many of the residues r_i we actually need to represent X in the RNS.

If you care to examine some sequences of u_i, the partial_chinese function returns the u_i sequence.

By messing around with the CRT, I was able to find a recursive formula for the u_i values, solving the issue of determining how many residues we need.

The formula is:

```<code>u_i = [ r_i - SUM ] / prod(i)       (mod p_i)
</code>```

Where SUM is the sum over j in [1,i) of u_j * prod(i).

Of course, prod(i) cannot actually be calculated in some cases because it is too large. For this purpose, I used the phi_i function. This function returns prod(j) (mod p_i). It mods at every step, so we never actually calculate anything that is too large.

If you are curious where this formula comes from, I would recommend working a couple of CRT examples, which can be found on the wikipedia page.

Finally, for each input as well as our output, we calculate the u_i sequence and then determine the trailing zeros. Then we throw out that many r_i from the end of the residue sequences.

"Golfed" Code, 2621 bytes

```<code>primes:=Primes{[1..100]};GetValueAsInt:=function(string,index)return IntChar(string[index])-48;end;digit_contribution := function(digit, integer, power)local result, i;result:=1;for i in [0..power-1] do result := ( result * (10 mod integer) ) mod integer;od;result:=(result*(digit mod integer) ) mod integer;return result;end;modulus:=function(string, integer)local i,result,digit,len;len:=Length(string);result:=0;for i in [1..len] do digit:= IntChar(string[i])-48;result:=(result+digit_contribution(digit,integer,len-i)) mod integer;od;return result;end;phi_i:=function(i,j)local index,result;result:=1;for index in [1..i-1] do result:=(result*primes[index] ) mod primes[j];od;return result;end;get_residues:=function(string) local p,result;result:=[];for p in primes do Add(result,modulus(string,p));od;return result;end;get_partial_i:=function(i,residues,previous_array)local index,result;result:=residues[i];for index in [1..Length(previous_array)] do result:=(result-previous_array[index]*phi_i(index,i) ) mod primes[i];od;result:=(result/phi_i(i,i)) mod primes[i];return result;end;partial_chinese:=function(string)local array,i,residues;residues:=get_residues(string);array:=[];for i in [1 .. Length(primes)] do Add(array,get_partial_i(i,residues,array));od;return array;end;partial_chinese_from_residues:=function(residues)local array,i;array:=[];for i in [1..Length(primes)] do Add(array,get_partial_i(i,residues,array));od;return array;end;get_size:=function(string)local array,i,len,result;array:=partial_chinese(string);len:=Length(array);for i in [0..len-1] do if not (array[len-i] = 0) then return len-i;fi;od;Print("ERROR: get_size().\n");return 0;end;get_size_from_residues:=function(residues)local array,i,len,result;array:=partial_chinese_from_residues(residues);len:=Length(array);for i in [0..len-1] do if not (array[len-i]=0) then return len-i;fi;od;Print("ERROR: get_size().\n");return 0;end;f:=function(in1,in2,opperation)local residues_1,residues_2,residues_result,i;residues_1:=get_residues(in1);residues_2:=get_residues(in2);residues_result:=[];if opperation = "+" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]+residues_2[i] ) mod primes[i]);od;elif opperation = "*" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]*residues_2[i])mod primes[i]);od;elif opperation = "-" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]-residues_2[i]) mod primes[i]);od;fi;Print(residues_1{[1..get_size(in1)]}, " ", opperation, " ", residues_2{[1..get_size(in2)]}, " = ", residues_result{[1..get_size_from_residues(residues_result)]} );end;
</code>```

Title: Residue Number System

Body:
GAP

Some Background: I will admit that when I created this question, so many months ago, I did not have a method for solving the hard part of this question: determining the correct number of primes to use. We have a lot of very intelligent people on this site, and I really expected that someone would figure out a way to do it fairly quickly. However, as this did not happen, I wasn't even sure that it was truly possible to solve this problem. So, I had to take the time to devise a method. I believe that what I have done does not break any of the rules in this challenge, of course I would love this to be fact checked.

I also slightly regret the choice of code-golf because the solutions are slightly more in depth than would usually fit the tag format. Having said this, to follow site rules, there is a "golfed" version of my solution at the bottom of this post.

Code

### The first 100 primes;
primes := Primes{[1..100]};

### In many of the functions below, the 'string' variable is a string of digits
###

### Returns the 'index' digit of 'string' as an integer
GetValueAsInt := function(string, index)
    return IntChar(string[index]) - 48;
end;

### Used in the 'modulus' function. See that comment for more information.
### Calculates the contribution to the modulus of a digit 'digit' in the 10^power place.
### 'integer' is the modulus
digit_contribution := function(digit, integer, power)
    local result, i;
    result := 1;
    for i in [0..power-1] do
        result := ( result * (10 mod integer) ) mod integer;
    od;
    result := (result * (digit mod integer) ) mod integer;
    return result;
end;

### This modulus function is used to calculate the modulus of large numbers without storing them
##### as large numbers.
### It does so by breaking them into digits, and calculating the contribution of each digit.
### e.g. 1234 mod 5 = (1000 mod 5)(1 mod 5) + (200 mod 5)(2 mod 5) + (10 mod 5)(3 mod 5) + (4 mod 5)
### It actually mods after every calculation to ensure that we never get a number larger
##### than the modulus ('integer') squared, which will never be even close to 10^64-1
modulus := function(string, integer)
    local i, result, digit, len;
    len := Length(string);
    result := 0;
    for i in [1..len] do
        digit :=  IntChar(string[i]) -48;
        result := ( result + digit_contribution(digit, integer, len-i) )  mod integer;
    od;
    return result;
end;

### This returns the product of the first i-1 primes (mod j). It must not (and does not)
##### ever store an integer larger than 2^64-1
phi_i := function(i,j)
    local index, result;
    result := 1;
    for index in [1..i-1] do
        result := ( result * primes[index] ) mod primes[j];
    od;
    return result;
end;

### Calculates the first residues of 'string' mod the first 100 primes
get_residues := function(string)
    local p, result;
    result := [];
    for p in primes do
        Add( result, modulus(string, p) );
    od;
    return result;
end;

### Gets the ith element in the partial_chinese array, given the previous elements
### See the explanation section and partial_chinese function for more info
get_partial_i := function( i, residues, previous_array )
    local index, result;
    result := residues[i];
    for index in [1..Length(previous_array)] do
        result := ( result - previous_array[index]*phi_i(index,i) ) mod primes[i];
    od;
    result := ( result / phi_i(i,i) ) mod primes[i];
    return result;
end;

### returns an array such that the sum of prod_primes(i)*array[i] is equal to the integer value
##### that is represented by the residues. (It basically just does the CRT without
##### actually summing everything.) prod_primes(i) is the product of the first i-1 primes
### See the explanation for a bit more info
### This is what allows us to determine the minimal number of primes to represent a RNS number
partial_chinese := function( string )
    local array, i, residues;
    residues := get_residues(string);
    array := [];
    for i in [1 .. Length(primes)] do
        Add( array, get_partial_i( i, residues, array ) );
    od;
    return array;
end;

### Same as partial_chinese but takes input in a different form.
partial_chinese_from_residues := function(residues)
    local array, i;
    array := [];
    for i in [1 .. Length(primes)] do
        Add( array, get_partial_i( i, residues, array ) );
    od;
    return array;
end;

### gives you the number of primes needed to represent an integer. Basically asks how
##### many trailing zeros there are in the chinese array.
get_size := function(string)
    local array, i, len, result;
    array := partial_chinese(string);
    len := Length(array);
    for i in [0..len-1] do
        if  not (array[len-i] = 0) then
            return len -i;
        fi;
    od;
    Print("ERROR: get_size().\n");
    return 0;
end;

### Same as above but with different input format
get_size_from_residues := function(residues)
    local array, i, len, result;
    array := partial_chinese_from_residues(residues);
    len := Length(array);
    for i in [0..len-1] do
        if  not (array[len-i] = 0) then
            return len -i;
        fi;
    od;
    Print("ERROR: get_size().\n");
    return 0;
end;

### the actual function. inputs are all strings
f := function(in1, in2, opperation)
    local residues_1, residues_2, residues_result, i;
    residues_1 := get_residues(in1);
    residues_2 := get_residues(in2);
    residues_result := [];
    if opperation = "+" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] + residues_2[i] ) mod primes[i]);
        od;
    elif opperation = "*" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] * residues_2[i] ) mod primes[i]);
        od;
    elif opperation = "-" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] - residues_2[i] ) mod primes[i]);
        od;
    fi;
    Print(residues_1{[1..get_size(in1)]}, " ", opperation, " ", residues_2{[1..get_size(in2)]}, " = ", residues_result{[1..get_size_from_residues(residues_result)]} );
end;

Explanation:

To start off, we calculate all the 100 of the residues for both inputs. We do this with the modulus function in the code. I tried to be careful so that we use the built-in mod function after every step. This ensures that we never have a number that is larger than 540^2, which is 1 less than the 100th prime squared.

After we have all the residues, we can perform the given operation and mod each entry again. Now we have a unique designator for the result, but we need to determine the minimal number of entries that we have to use to represent the result and each of the inputs.

Figuring out how many residues we actually need is by far the hardest part of this problem. To determine this, we perform most of the steps of the Chinese Remainder Theorem (CRT). However, we obviously have to make modifications so that we don't end up with numbers that are too large.

Let prod(i) be the sum of the first i-1 primes. For example,

prod(1) = 1
prod(2) = 2
prod(3) = 6
prod(4) = 30
etc

Let X be an integer. Let {r_i} be the residues of X, that is

r_i = X mod p_i

Where p_i is the ith prime. This is for 1<i<=100 in our case.

Now we are going to use the CRT to find a sequence {u_i} such that the sum over i of prod(i) * u_i is equal to X. Note that each u_i is also technically a residue, as u_i < p_i. Furthermore, if X < prod(i) then u_i = 0. This is of critical importance. It means that by examining trailing zeros, we can determine how many of the residues r_i we actually need to represent X in the RNS.

If you care to examine some sequences of u_i, the partial_chinese function returns the u_i sequence.

By messing around with the CRT, I was able to find a recursive formula for the u_i values, solving the issue of determining how many residues we need.

The formula is:

u_i = [ r_i - SUM ] / prod(i)       (mod p_i)

Where SUM is the sum over j in [1,i) of u_j * prod(i).

Of course, prod(i) cannot actually be calculated in some cases because it is too large. For this purpose, I used the phi_i function. This function returns prod(j) (mod p_i). It mods at every step, so we never actually calculate anything that is too large.

If you are curious where this formula comes from, I would recommend working a couple of CRT examples, which can be found on the wikipedia page.

Finally, for each input as well as our output, we calculate the u_i sequence and then determine the trailing zeros. Then we throw out that many r_i from the end of the residue sequences.

"Golfed" Code, 2621 bytes

primes:=Primes{[1..100]};GetValueAsInt:=function(string,index)return IntChar(string[index])-48;end;digit_contribution := function(digit, integer, power)local result, i;result:=1;for i in [0..power-1] do result := ( result * (10 mod integer) ) mod integer;od;result:=(result*(digit mod integer) ) mod integer;return result;end;modulus:=function(string, integer)local i,result,digit,len;len:=Length(string);result:=0;for i in [1..len] do digit:= IntChar(string[i])-48;result:=(result+digit_contribution(digit,integer,len-i)) mod integer;od;return result;end;phi_i:=function(i,j)local index,result;result:=1;for index in [1..i-1] do result:=(result*primes[index] ) mod primes[j];od;return result;end;get_residues:=function(string) local p,result;result:=[];for p in primes do Add(result,modulus(string,p));od;return result;end;get_partial_i:=function(i,residues,previous_array)local index,result;result:=residues[i];for index in [1..Length(previous_array)] do result:=(result-previous_array[index]*phi_i(index,i) ) mod primes[i];od;result:=(result/phi_i(i,i)) mod primes[i];return result;end;partial_chinese:=function(string)local array,i,residues;residues:=get_residues(string);array:=[];for i in [1 .. Length(primes)] do Add(array,get_partial_i(i,residues,array));od;return array;end;partial_chinese_from_residues:=function(residues)local array,i;array:=[];for i in [1..Length(primes)] do Add(array,get_partial_i(i,residues,array));od;return array;end;get_size:=function(string)local array,i,len,result;array:=partial_chinese(string);len:=Length(array);for i in [0..len-1] do if not (array[len-i] = 0) then return len-i;fi;od;Print("ERROR: get_size().\n");return 0;end;get_size_from_residues:=function(residues)local array,i,len,result;array:=partial_chinese_from_residues(residues);len:=Length(array);for i in [0..len-1] do if not (array[len-i]=0) then return len-i;fi;od;Print("ERROR: get_size().\n");return 0;end;f:=function(in1,in2,opperation)local residues_1,residues_2,residues_result,i;residues_1:=get_residues(in1);residues_2:=get_residues(in2);residues_result:=[];if opperation = "+" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]+residues_2[i] ) mod primes[i]);od;elif opperation = "*" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]*residues_2[i])mod primes[i]);od;elif opperation = "-" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]-residues_2[i]) mod primes[i]);od;fi;Print(residues_1{[1..get_size(in1)]}, " ", opperation, " ", residues_2{[1..get_size(in2)]}, " = ", residues_result{[1..get_size_from_residues(residues_result)]} );end;


问:
Exploded view of a string
Don't you love those exploded-view diagrams  in which a machine or object is taken apart into its smallest pieces?

Let's do that to a string!

The challenge

Write a program or function that

inputs a string containing only printable ASCII characters;

dissects the string into groups of non-space equal characters (the "pieces" of the string);

outputs those groups in any convenient format, with some separator between groups.

For example, given the string

```<code>Ah, abracadabra!
</code>```

the output would be the following groups:

```
!
,
A
aaaaa
bb
c
d
h
rr
```

Each group in the output contains equal characters, with spaces removed. A newline has been used as separator between groups. More about allowed formats below.

Rules

The input should be a string or an array of chars. It will only contain printable ASCII chars (the inclusive range from space to tilde). If your language does not support that, you can take the input in the form of numbers representing ASCII codes.

You can assume that the input contains at least one non-space character.

The output should consist of characters (even if the input is by means of ASCII codes). There has to be an unambiguous separator between groups, different than any non-space character that may appear in the input.

If the output is via function return, it may also be an array or strings, or an array of arrays of chars, or similar structure. In that case the structure provides the necessary separation.

A separator between characters of each group is optional. If there is one, the same rule applies: it can't be a non-space character that may appear in the input. Also, it can't be the same separator as used between groups.

Other than that, the format is flexible. Here are some examples:

The groups may be strings separated by newlines, as shown above.

The groups may be separated by any non-ASCII character, such as  ¬. The output for the above input would be the string:

```<code>!¬,¬A¬aaaaa¬bb¬c¬d¬h¬rr
</code>```

The groups may be separated by n>1 spaces (even if n is variable), with chars between each group separated by a single space:

```<code>!  ,    A   a a a a a    b b  c       d   h  r r
</code>```

The output may also be an array or list of strings returned by a function:

```<code>['!', 'A', 'aaaaa', 'bb', 'c', 'd', 'h', 'rr']
</code>```

Or an array of char arrays:

```<code>[['!'], ['A'], ['a', 'a', 'a', 'a', 'a'], ['b', 'b'], ['c'], ['d'], ['h'], ['r', 'r']]
</code>```

Examples of formats that are not allowed, according to the rules:

A comma can't be used as separator (!,,,A,a,a,a,a,a,b,b,c,d,h,r,r), because the input may contain commas.

It's not accepted to drop the separator between groups (!,Aaaaaabbcdhrr) or to use the same separator between groups and within groups (! , A a a a a a b b c d h r r).

The groups may appear in any order in the output. For example: alphabetical order (as in the examples above), order of first appearance in the string, ... The order need not be consistent or even deterministic.

Note that the input cannot contain newline characters, and A and a are different characters (grouping is case-sentitive).

Shortest code in bytes wins.

Test cases

In each test case, first line is input, and the remaining lines are the output, with each group in a different line.

Test case 1:

```
Ah, abracadabra!
!
,
A
aaaaa
bb
c
d
h
rr
```

Test case 2:

```
\o/\o/\o/
///
\\\
ooo
```

Test case 3:

```
A man, a plan, a canal: Panama!
!
,,
:
A
P
aaaaaaaaa
c
ll
mm
nnnn
p
```

Test case 4:

```
"Show me how you do that trick, the one that makes me scream" she said
""
,
S
aaaaa
cc
dd
eeeeeee
hhhhhh
ii
kk
mmmm
n
ooooo
rr
ssss
tttttt
u
ww
y
```

答:
Java 8, <s>121</s> <s>120</s> <s>110</s> 103 Bytes

```<code>s->s.chars().distinct().filter(c->c!=32)
    .forEach(c->out.println(s.replaceAll("[^\\Q"+(char)c+"\\E]","")))
</code>```

Above lambda can be consumed with Java-8 Consumer. It fetches distinct characters and replaces other characters of the String to disassemble each character occurrence.

ContentLicense: CC BY-SA 3.0

Title: Exploded view of a string

Body:
Java 8, <s>121</s> <s>120</s> <s>110</s> 103 Bytes

s->s.chars().distinct().filter(c->c!=32)
    .forEach(c->out.println(s.replaceAll("[^\\Q"+(char)c+"\\E]","")))

Above lambda can be consumed with Java-8 Consumer. It fetches distinct characters and replaces other characters of the String to disassemble each character occurrence.


问:
Display a MIDI Track

Background

MIDI files are quite different from WAV or MP3 audio files. MP3 and WAV files contain bytes representing a "recording" of the audio, while MIDI files have a series of MIDI messages stored in MIDI events informing a MIDI synthesizer which virtual instrument to play or a MIDI sequencer the playback tempo that should be used. These messages are stored in tracks, and a collection of tracks makes up a MIDI sequence, whose events can be analyzed by a sequencer and have its messages transmitted from the sequencer to a synthesizer's receiver.

Most of the time the MIDI messages stored in MIDI events are Note On messages which tell the synthesizer to play a particular note, or Note Off messages which tell the synthesizer to stop playing the note. These messages contain two data bytes, the first of which informs the synthesizer of the velocity of the note (higher velocity results in a louder note), and the second of which tells the synthesizer the note to play (i.e. Middle C). The events themselves also contain ticks which serve the purpose of telling the sequencer when to send the messages.

The Challenge

The challenge is to write a full program or a function that analyzes a series of Note On and Note Off MIDI messages in a single-track MIDI sequence and outputs to STDOUT a chart showing when particular notes are on, when they are off, and the velocity of these notes. The vertical axis of the chart represents the note value and should be labeled as described below, and the horizontal axis represents time in MIDI ticks (though it should remain unlabeled to reduce complexity and spacing issues).

Your input may be four separate arrays or lists, each containing a series of integer values; a two-dimensional array or list containing four sub-arrays/sub-lists with a series of integer values; or any other convenient means; this represents the collection MIDI events with Note On and Note Off messages in the track. The values in the first of these arrays specifies the note, the second the velocity, the third the note on event tick, and the fourth the note off event tick. For instance, given four arrays such as these:

```<code>{60, 62, 64, 65,  67}
{20, 40, 60, 80, 100}
{ 0,  4,  8, 12,  16}
{ 2,  6, 10, 14,  18}
</code>```

Analyzing the first element of each array gives two events: an event at tick 0 with a message that has a Note On command, note 60 (Middle C), and note velocity of 20; and an event at tick 2 with a message that has a Note Off command with the same note and velocity.

Rules

The chart should feature the numbers 0 through 127 displayed in decreasing order on the left side (representing the note value), when the note starts, the duration of each note (Note Off tick minus Note On tick), and the note's velocity. The symbols representing the notes are dependent on their velocity:

0-15: O

16-31: =

32-47: #

48-63: -

64-79: @

80-95: +

96-111: 0

112-127: *

You can assume the following:

The values for note and velocity will be within the range [0, 127].

The lengths of each of the four arrays will always equal each other.

Here are a few examples:

```<code>{60, 62, 64, 65,  67}
{20, 40, 60, 80, 100}
{ 0,  4,  8, 12,  16}
{ 2,  6, 10, 14,  18}

127|
126|
125|
...
67 |                00
66 |
65 |            ++
64 |        --
63 |
62 |    ##
61 |
60 |==
59 |
...
2  |
1  |
0  |

{60, 48, 62, 47, 64, 45,  65,  43, 67, 41, 65, 43, 64, 45,  62, 47, 60, 48}
{63, 31, 75, 90, 12, 23, 122, 104, 33, 19, 57, 42,  5, 82, 109, 86, 95, 71}
{0,   0,  2,  2,  4,  4,   6,   6,  8,  8, 10, 10, 12, 12,  14, 14, 16, 16}
{2,   2,  4,  4,  6,  6,   8,   8, 10, 10, 12, 12, 14, 14,  16, 16, 18, 18}

127|
126|
...
68 |
67 |        ##
66 |
65 |      **  --
64 |    OO      OO
63 |
62 |  @@          00
61 |
60 |--              ++
59 |
...
49 |
48 |==              @@
47 |  ++          ++
46 |
45 |    ==      ++
44 |
43 |      00  ##
42 |
41 |        ==
40 |
...
1  |
0  |
</code>```

Here's an example that displays the first few notes of Ode to Joy:

```<code>{48, 55, 64, 64, 65, 67, 55, 67, 65, 64, 62, 52, 55,  60,  60,  62,  64,  55, 64, 62, 62}
{45, 45, 63, 63, 63, 63, 89, 66, 66, 66, 66, 30, 30, 103, 103, 103, 103, 127, 55, 55, 55}
{ 0,  0,  0,  4,  8, 12, 16, 16, 20, 24, 28, 32, 32,  32,  36,  40,  44,  48, 48, 54, 56}
{16, 16,  2,  6, 10, 14, 32, 18, 22, 26, 30, 48, 48,  34,  38,  42,  46,  64, 50, 55, 64}

127|
...
67 |            --  @@
66 |
65 |        --          @@
64 |--  --                  @@                  00  --
63 |
62 |                            @@          00            - --------
61 |
60 |                                00  00
59 |
58 |
57 |
56 |
55 |################++++++++++++++++================****************
54 |
53 |
52 |                                ================
51 |
50 |
49 |
48 |################
...
0  |
</code>```

You can reduce your score by 25% if your submission takes an actual MIDI sequence as input, analyzes the Note On and Note Off messages of any track of your choosing provided it contains at least four events with Note On and Note Off messages, and outputs a chart as described above.

This is code golf, so shortest code wins. Good luck!

答:
Ruby, 106 bytes

This was fun. I'm not sure why no one attempted it.

This function takes input as four array arguments and returns an array of strings, one for each line of the chart.

```<code>->a,*r{q=(0..z=127).map{|i|"%3d|"%(z-i)+" "*1e4}
a.zip(*r){|n,v,o,f|q[z-n][o+4]="O=#-@+0*"[v/16]*(f-o)}
q}
</code>```

Note: This arbitrarily assumes that there will be no more than 10,000 ticks. If you run it in your terminal I suggest piping it to less so you can scroll horizontally. You can change 1e4 if you want more ticks, all the way up to 9e9, but that will take a terabyte or two of RAM.

See it on repl.it: https://repl.it/Cx4I/1

Title: Display a MIDI Track

Body:
Ruby, 106 bytes

This was fun. I'm not sure why no one attempted it.

This function takes input as four array arguments and returns an array of strings, one for each line of the chart.

->a,*r{q=(0..z=127).map{|i|"%3d|"%(z-i)+" "*1e4}
a.zip(*r){|n,v,o,f|q[z-n][o+4]="O=#-@+0*"[v/16]*(f-o)}
q}

Note: This arbitrarily assumes that there will be no more than 10,000 ticks. If you run it in your terminal I suggest piping it to less so you can scroll horizontally. You can change 1e4 if you want more ticks, all the way up to 9e9, but that will take a terabyte or two of RAM.

See it on repl.it: https://repl.it/Cx4I/1


问:
Visible Buildings
This puzzle is derived from CodinGame SamSi's "Heart of the City" puzzle.

Description

You decide to take a walk in an n * n tile city and go to the center tile. All of the buildings are infinitely small, but you have super vision and can see everything close up and far away.

Constraints

n is always odd

You can see any building that is not directly obstructed by another one

Task

Mark each building visible with *. The building is visible iff it is not blocked by another building on the exact same line of vision.

In other words, if @ is the origin, the building is visible iff the x-coordinate and the y-coordinate are co-prime to each other.

Example input and output

Input:

```<code>7
</code>```

Output:

```<code> ** **
* * * *
*******
  *@*
*******
* * * *
 ** **
</code>```

* is a visible building,
 is an invisible building, and
@ is where you are.

Scoring

Remember, this is code-golf, so the answer with the least bytes wins.

var QUESTION_ID=91394,OVERRIDE_USER=59057;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}*{font-family:"Helvetica",sans-serif}</code>```

<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

答:
C, <s>147</s> <s>145</s> <s>135</s> 133 bytes

2 bytes thanks to Dennis.

10 bytes thanks to Arnauld.

2 bytes thanks to H Walters.

r,m,i,j;g(a,b){r=b?g(b,a%b):a;}main(n){scanf("%d",&n);for(m=n/2,i=-m;i<=m;putchar(r?r*r-1?32:42:64),i+=++j%n<1&&puts(""))g(i,j%n-m);}
```

Ideone it!

Golfing advice welcome as always.

Title: Visible Buildings

Body:
C, <s>147</s> <s>145</s> <s>135</s> 133 bytes

2 bytes thanks to Dennis.

10 bytes thanks to Arnauld.

2 bytes thanks to H Walters.

r,m,i,j;g(a,b){r=b?g(b,a%b):a;}main(n){scanf("%d",&n);for(m=n/2,i=-m;i<=m;putchar(r?r*r-1?32:42:64),i+=++j%n<1&&puts(""))g(i,j%n-m);}

Ideone it!

Golfing advice welcome as always.


问:
This isn't rocket science
Write a program or function that takes in a single-line string. You can assume it only contains printable ASCII. Print or return a string of an ASCII art rocket such as

```<code>  |
 /_\
 |E|
 |a|
 |r|
 |t|
 |h|
 |_|
/___\
 VvV
</code>```

with the input string written from top to bottom on the fuselage. In this case the input was Earth. The height of the rocket (including flames) is always the length of the string plus five.

Each line in the output may have up to two trailing spaces and there may be a single optional trailing newline. The shortest code in bytes wins.

More Examples:

```<code>[empty string]

  |
 /_\
 |_|
/___\
 VvV

a

  |
 /_\
 |a|
 |_|
/___\
 VvV

|0

  |
 /_\
 |||
 |0|
 |_|
/___\
 VvV

\/\

  |
 /_\
 |\|
 |/|
 |\|
 |_|
/___\
 VvV

 _ _ [note trailing space]

  |
 /_\
 | |
 |_|
 | |
 |_|
 | |
 |_|
/___\
 VvV

    [4 spaces]

  |
 /_\
 | |
 | |
 | |
 | |
 |_|
/___\
 VvV

SPACEY

  |
 /_\
 |S|
 |P|
 |A|
 |C|
 |E|
 |Y|
 |_|
/___\
 VvV
</code>```

Leaderboard

var QUESTION_ID=91182,OVERRIDE_USER=26997;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

Title: This isn't rocket science

Body:
Java 8, <s>132</s> <s>109</s> <s>107</s> 96 Bytes

i->"  |\n /_\\ \n"+i.chars().mapToObj(c->" |"+(char)c+"|")
                            .collect(joining("\n"))+"\n |_|\n/___\\\n VvV"


答:
Jelly, 16 bytes

```<code>:2ạḶgþ`«2ị“* @”Y
</code>```

Try it online!

How it works

```<code>:2ạḶgþ`«2ị“* @”Y  Main link. Argument: 2n + 1

:2                Perform integer division by 2, yielding n.
   Ḷ              Yield [0, ..., 2n].
 ạ                Take the absolute difference of the result to both sides.
                  This yields A := [n, ... 0, ... n].
      `           Call the quicklink to the left with left and right argument A.
     þ              Table; call the link to the left for all x in A and all y in A.
    g                 Yield the GCD of x and y.
       «2         Truncate the GCD at 2, leaving 0 for the origin, 1 for coprime
                  coordinates, and 2 otherwise.
         ị“* @”   Index into that string, mapping [1, 2, 0] to ['*', ' ', '@'].
               Y  Join, separating by linefeeds.
</code>```

Title: Visible Buildings

Body:
This puzzle is derived from CodinGame SamSi's "Heart of the City" puzzle.

Description

You decide to take a walk in an n * n tile city and go to the center tile. All of the buildings are infinitely small, but you have super vision and can see everything close up and far away.

Constraints

n is always odd

You can see any building that is not directly obstructed by another one

Task

Mark each building visible with *. The building is visible iff it is not blocked by another building on the exact same line of vision.

In other words, if @ is the origin, the building is visible iff the x-coordinate and the y-coordinate are co-prime to each other.

Example input and output

Input:

```<code>7
</code>```

Output:

```<code> ** **
* * * *
*******
  *@*
*******
* * * *
 ** **
</code>```

* is a visible building,
 is an invisible building, and
@ is where you are.

Scoring

Remember, this is code-golf, so the answer with the least bytes wins.

var QUESTION_ID=91394,OVERRIDE_USER=59057;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}*{font-family:"Helvetica",sans-serif}</code>```

<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

Body:
Jelly, 16 bytes

:2ạḶgþ`«2ị“* @”Y

Try it online!

How it works

:2ạḶgþ`«2ị“* @”Y  Main link. Argument: 2n + 1

:2                Perform integer division by 2, yielding n.
   Ḷ              Yield [0, ..., 2n].
 ạ                Take the absolute difference of the result to both sides.
                  This yields A := [n, ... 0, ... n].
      `           Call the quicklink to the left with left and right argument A.
     þ              Table; call the link to the left for all x in A and all y in A.
    g                 Yield the GCD of x and y.
       «2         Truncate the GCD at 2, leaving 0 for the origin, 1 for coprime
                  coordinates, and 2 otherwise.
         ị“* @”   Index into that string, mapping [1, 2, 0] to ['*', ' ', '@'].
               Y  Join, separating by linefeeds.


问:
Implement glob Matcher
Implement a function of pattern and string to be matched, return true if the pattern matches the WHOLE string, otherwise false.

Our glob pattern syntax is:

? matches any one character

+ matches one or more characters

* matches zero or more characters

\ escapes

Rules:

No eval, no converting into regular expression, no calling a system glob function.

I/O are not required: you can just write a function

Shortest wins

Examples:

```<code>glob('abc', 'abc') => true
glob('abc', 'abcdef') => false IMPORTANT!
glob('a??', 'aww') => true
glob('a*b', 'ab') => true
glob('a*b', 'agwijgwbgioeb') => true
glob('a*?', 'a') => false
glob('?*', 'def') => true
glob('5+', '5ggggg') => true
glob('+', '') => false
glob('a\*b', 'a*b') => true
</code>```

Here is a tip to get started: http://en.wikipedia.org/wiki/Backtracking

答:
Shorter Snappier Python 2.6 (272 characters)

golfed:

```<code>n=lambda p,s:p[0]==s[0]and m(p[1:],s[1:])
def m(p,s):
 q,r,t,u=p[0],p[1:],s[0],s[1:]
 return any((q=='?'and(t and m(r,u)),q=='+'and(t and(m(p,u)or m(r,u))),q=='*'and(m(r,s)or(t and m(p,u))),q=='\\'and n(r,s),q==t==0))or n(p,s)
glob=lambda*a:m(*[list(x)+[0]for x in a])
</code>```

ungolfed:

```<code>TERMINATOR = 0

def unpack(a):
    return a[0], a[1:]

def terminated_string(s):
    return list(s) + [TERMINATOR]

def match_literal(p, s):
    p_head, p_tail = unpack(p)
    s_head, s_tail = unpack(s)
    return p_head == s_head and match(p_tail, s_tail)

def match(p, s):
    p_head, p_tail = unpack(p)
    s_head, s_tail = unpack(s)
    return any((
        p_head == '?' and (s_head and match(p_tail, s_tail)),
        p_head == '+' and (s_head and(match(p, s_tail) or match(p_tail, s_tail))),
        p_head == '*' and (match(p_tail, s) or (s_head and match(p, s_tail))),
        p_head == '\\' and match_literal(p_tail, s),
        p_head == s_head == TERMINATOR,
    )) or match_literal(p, s)

def glob(p, s):
    return match(terminated_string(p), terminated_string(s))
</code>```

featuring:

lazily-evaluated logical mess!

C style strings!

cute multiple comparison idiom!

plenty of ugly!

credit to user300's answer for illustrating how things are simplified if you can get some kind of terminator value when popping the head from an empty string.

i wish the head/tail unpacking could be performed inline during the declaration of m's arguments. then m could be a lambda, just like its friends n and glob. python2 cannot do it, and after a bit of reading, it looks like python3 cannot either. woe.

testing:

```<code>test_cases = {
    ('abc', 'abc') : True,
    ('abc', 'abcdef') : False,
    ('a??', 'aww') : True,
    ('a*b', 'ab') : True,
    ('a*b', 'aqwghfkjdfgshkfsfddsobbob') : True,
    ('a*?', 'a') : False,
    ('?*', 'def') : True,
    ('5+', '5ggggg') : True,
    ('+', '') : False,
}
for (p, s) in test_cases:
    computed_result = glob(p, s)
    desired_result = test_cases[(p, s)]
    print '%s %s' % (p, s)
    print '\tPASS' if (computed_result == desired_result) else '\tFAIL'
</code>```

ContentLicense: CC BY-SA 2.5

Title: Implement glob Matcher

Body:
Shorter Snappier Python 2.6 (272 characters)

golfed:

n=lambda p,s:p[0]==s[0]and m(p[1:],s[1:])
def m(p,s):
 q,r,t,u=p[0],p[1:],s[0],s[1:]
 return any((q=='?'and(t and m(r,u)),q=='+'and(t and(m(p,u)or m(r,u))),q=='*'and(m(r,s)or(t and m(p,u))),q=='\\'and n(r,s),q==t==0))or n(p,s)
glob=lambda*a:m(*[list(x)+[0]for x in a])

ungolfed:

TERMINATOR = 0

def unpack(a):
    return a[0], a[1:]

def terminated_string(s):
    return list(s) + [TERMINATOR]

def match_literal(p, s):
    p_head, p_tail = unpack(p)
    s_head, s_tail = unpack(s)
    return p_head == s_head and match(p_tail, s_tail)

def match(p, s):
    p_head, p_tail = unpack(p)
    s_head, s_tail = unpack(s)
    return any((
        p_head == '?' and (s_head and match(p_tail, s_tail)),
        p_head == '+' and (s_head and(match(p, s_tail) or match(p_tail, s_tail))),
        p_head == '*' and (match(p_tail, s) or (s_head and match(p, s_tail))),
        p_head == '\\' and match_literal(p_tail, s),
        p_head == s_head == TERMINATOR,
    )) or match_literal(p, s)

def glob(p, s):
    return match(terminated_string(p), terminated_string(s))

featuring:

lazily-evaluated logical mess!

C style strings!

cute multiple comparison idiom!

plenty of ugly!

credit to user300's answer for illustrating how things are simplified if you can get some kind of terminator value when popping the head from an empty string.

i wish the head/tail unpacking could be performed inline during the declaration of m's arguments. then m could be a lambda, just like its friends n and glob. python2 cannot do it, and after a bit of reading, it looks like python3 cannot either. woe.

testing:

test_cases = {
    ('abc', 'abc') : True,
    ('abc', 'abcdef') : False,
    ('a??', 'aww') : True,
    ('a*b', 'ab') : True,
    ('a*b', 'aqwghfkjdfgshkfsfddsobbob') : True,
    ('a*?', 'a') : False,
    ('?*', 'def') : True,
    ('5+', '5ggggg') : True,
    ('+', '') : False,
}
for (p, s) in test_cases:
    computed_result = glob(p, s)
    desired_result = test_cases[(p, s)]
    print '%s %s' % (p, s)
    print '\tPASS' if (computed_result == desired_result) else '\tFAIL'


答:
J, 24 bytes

```<code>'@* '{~2<.[:+./~<.@-:-i.
</code>```

A port of Dennis' answer in Jelly.

Title: Visible Buildings

Body:
J, 24 bytes

'@* '{~2<.[:+./~<.@-:-i.

A port of Dennis' answer in Jelly.


问:
Extendable Train Swapping Problem

Extended Train Swapping Problem

Part 1: Normal Train Swapping Problem

In the 1996 CCC (Canadian Computing Competition), the first Stage 2 problem was a Train Swapping Problem. You can visit the link here. Essentially, you have a bunch of numbered trains, and you want to find out how many train swaps you need to get them in order, and each train swap operation allows you to swap two adjacent trains. Since train carriages can run either way, nobody cares about the fact that the train carriages face the other way when swapped. This is pretty easy; all you need to do is:

 Find the number of steps to bubble-sort it; it's the most efficient sorting algorithm when you can only make adjacent element swaps

So, I made a harder one.

Part 2: How this challenge works

Essentially, you can now swap more than just adjacent trains. With a longer rotating platform, you can swap the position of multiple trains. For example, with a rotating platform of length 4, you can swap both the inner and outer pairs at the same time, so 1 2 3 4 becomes 4 3 2 1. Here are some examples for different rotating platform sizes:

```<code>Length 2:
1 2 3 4 5
  ---
1 3 2 4 5

Length 3:
1 2 3 4 5
  -----
1 4 3 2 5

Length 4:
1 2 3 4 5
-------
4 3 2 1 5
</code>```

Essentially, you're just inverting a sublist of the entire train. To clarify, in each move, you can only swap exactly N trains.

Part 3: Specifications

Input

Your input must take in two things: the length of the rotating platform, and the order of the train carriages. You may also require the number of train carriages if you wish. The order of the train carriages is given by an ordered list of numbers (each number representing a train carriage), so you can read the input as space-separated integers, newline-separated integers, an array, etc.

Output

You must output the optimal (minimum) number of swaps needed to get the carriages all into the order 1 2 3 ... N. If there is no solution, output -1, No solution, or some other consistent message. You may not output to stderr.

Scoring

This is a code-golf challenge, so scoring is in bytes. The solution with the lowest number of bytes as of September 1st, 2016 will be the accepted one.

Examples

Problem 1
Input

```<code>4
2
1 3 2 4
</code>```

Output

```<code>1
</code>```

Explanation

This is pretty trivial; with a rotating platform of length 2, it's the same as the normal train swapping problem. Swap the 2 and the 3.

Problem 2
Input

```<code>4
3
1 3 2 4
</code>```

Output

```<code>No solution (or an equivalent consistent message).
</code>```

Problem 3
Input

```<code>9
3
1 4 5 6 3 8 7 2 9
</code>```

Output

```<code>4
</code>```

Explanation

```<code>1 4 5 6 3 8 7 2 9
          -----
1 4 5 6 3 2 7 8 9
      -----
1 4 5 2 3 6 7 8 9
    -----
1 4 3 2 5 6 7 8 9
  -----
1 2 3 4 5 6 7 8 9
</code>```

Standard loopholes apply

Good luck!

EDIT 1: Made the input format more flexible. Thanks to @Mego!

EDIT 2: Clarified that a rotating platform of length 4 swaps both the inner and outer pairs. Thanks to @TimmyD!

EDIT 3: Clarified that you must make permutations of length N exactly, not at most. Thanks to @Zgarb!

答:
Perl, 120 bytes

Includes +6 for -Xapi (- and space are counted too because both the -i and the $' in the code make it impossible to combine the options with -e)

Run with the input on STDIN and the platform length after the -i option, e.g.

```<code>perl -Xapi3 trains.pl <<< "1 4 5 6 3 8 7 2 9"
</code>```

Prints -2 if there is no solution

trains.pl:

```<code>1until$_=$n++*$z{pack"W*",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/s,keys%z,pack"W*",1..@F;$_--
</code>```

if N <= 9 then you can gain 5 more bytes:

```<code>1until$_=$n++*$z{join"",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/,keys%z,join"",1..@F;$_--
</code>```

Title: Extendable Train Swapping Problem

Body:
Perl, 120 bytes

Includes +6 for -Xapi (- and space are counted too because both the -i and the $' in the code make it impossible to combine the options with -e)

Run with the input on STDIN and the platform length after the -i option, e.g.

perl -Xapi3 trains.pl <<< "1 4 5 6 3 8 7 2 9"

Prints -2 if there is no solution

trains.pl:

1until$_=$n++*$z{pack"W*",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/s,keys%z,pack"W*",1..@F;$_--

if N <= 9 then you can gain 5 more bytes:

1until$_=$n++*$z{join"",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/,keys%z,join"",1..@F;$_--


问:
Print every printable ASCII character without using it
In a programming language of your choice, write 95 programs, each of which outputs a different one of the 95 printable ASCII characters without that character occurring anywhere in the program.

For example, if your language was Python, your program that outputs the character P might be

```<code>print(chr(80))
</code>```

because P has ASCII code 80. This program is valid because P never appears in the source code. However, for the program that outputs lowercase p, something like

```<code>print(chr(112))
</code>```

would be invalid because, while it does print p, p is present in the code. A valid program could be

```<code>exec(chr(112)+'rint(chr(112))')
</code>```

which prints p but does not contain p.

Your goal is to make each of your 95 programs as short as possible. Your score is the sum of the character lengths of all your programs.

If for any reason you are unable to write valid programs for some characters, you may mark those characters as "Did Not Program" or DNP, and omit programs for them entirely. This way syntactically strict languages will be able to compete.

The winning answer is the answer that has the lowest score of the set of answers that have the fewest DNP's.

Rules

The source code of all of your programs may only contain printable ASCII plus tabs and newlines, all of which are counted as one character. (Because in a different encoding it would be easy to omit characters that don't exist!)

Note: This rule seems necessary but there are many languages with different encodings and I'm sure it'd be cool to see the answers for them. Therefore you can break this rule, you can use whatever characters you want, but then your answer becomes non-competitive, it cannot win.

The programs must be actual, full programs, according to your language's standard conventions. Functions and REPL snippets are not allowed.

Each program's output should go to stdout or your language's accepted alternative.

Programs should not prompt for or require input. (If prompting for input is inherent to your language, that's ok.)

Programs should be deterministic, finite in run time, and independent. e.g. it shouldn't matter if one is run in a folder separate from the other programs.

A program's output should be the precise printable ASCII character it corresponds to, optionally followed by a single trailing newline, nothing more, nothing less.

Be sure to include information on all 95 (ideally) programs in your answer, as well as your score and any DNP's. You don't have to list all programs that follow a simple pattern like "print(chr(80)), print(chr(81)), print(chr(82))..." but make sure you're sure they all would work and that your score is added correctly.

For reference, here are the 95 printable ASCII your programs must output:

```<code> !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
</code>```

Body:
GNU sed, <s>587</s> <s>578</s> 572 characters

All 95 programs were possible. An input is absolutely required by sed in order to execute the code. Some programs need the extra n flag to avoid a second trailing \n in the output.

Run:

echo | sed -f program_filename

List of all programs with additional details:

Char	Program code		Size	n flag	Total size
 	c\\x20			6	0	6
!	c\\x21			6	0	6
"	c\\x22			6	0	6
#	c\\x23			6	0	6
$	c\\x24			6	0	6
%	c\\x25			6	0	6
&	c\\x26			6	0	6
'	c\\x27			6	0	6
(	c\\x28			6	0	6
)	c\\x29			6	0	6
*	c\\x2A			6	0	6
+	c\\x2B			6	0	6
,	c\\x2C			6	0	6
-	c\\x2D			6	0	6
.	c\\x2E			6	0	6
/	c\\x2F			6	0	6
0	c\\d48			6	0	6
1	=			1	1	2	*
2	c\\d50			6	0	6
3	c\\d51			6	0	6
4	c\\d52			6	0	6
5	c\\d309			7	0	7	*
6	c\\d54			6	0	6
7	c\\d55			6	0	6
8	c\\d56			6	0	6
9	c\\d57			6	0	6
:	c\\x3A			6	0	6
;	c\\x3B			6	0	6
<	c\\x3C			6	0	6
=	c\\x3D			6	0	6
>	c\\x3E			6	0	6
?	c\\x3F			6	0	6
@	c\\x40			6	0	6
A	c\\x41			6	0	6
B	c\\x42			6	0	6
C	c\\x43			6	0	6
D	c\\x44			6	0	6
E	c\\x45			6	0	6
F	c\\x46			6	0	6
G	c\\x47			6	0	6
H	c\\x48			6	0	6
I	c\\x49			6	0	6
J	c\\x4A			6	0	6
K	c\\x4B			6	0	6
L	c\\x4C			6	0	6
M	c\\x4D			6	0	6
N	c\\x4E			6	0	6
O	c\\x4F			6	0	6
P	c\\x50			6	0	6
Q	c\\x51			6	0	6
R	c\\x52			6	0	6
S	c\\x53			6	0	6
T	c\\x54			6	0	6
U	c\\x55			6	0	6
V	c\\x56			6	0	6
W	c\\x57			6	0	6
X	c\\x58			6	0	6
Y	c\\x59			6	0	6
Z	c\\x5A			6	0	6
[	c\\x5B			6	0	6
\	edc -e92P		9	0	9	*
]	c\\x5D			6	0	6
^	c\\x5E			6	0	6
_	c\\x5F			6	0	6
`	c\\x60			6	0	6
a	c\\x61			6	0	6
b	c\\x62			6	0	6
c	a\\x63			6	1	7
d	c\\x64			6	0	6
e	c\\x65			6	0	6
f	c\\x66			6	0	6
g	c\\x67			6	0	6
h	c\\x68			6	0	6
i	c\\x69			6	0	6
j	c\\x6A			6	0	6
k	c\\x6B			6	0	6
l	c\\x6C			6	0	6
m	c\\x6D			6	0	6
n	c\\x6E			6	0	6
o	c\\x6F			6	0	6
p	c\\x70			6	0	6
q	c\\x71			6	0	6
r	c\\x72			6	0	6
s	c\\x73			6	0	6
t	c\\x74			6	0	6
u	c\\x75			6	0	6
v	c\\x76			6	0	6
w	c\\x77			6	0	6
x	c\\d120			7	0	7
y	c\\x79			6	0	6
z	c\\x7A			6	0	6
{	c\\x7B			6	0	6
|	c\\x7C			6	0	6
}	c\\x7D			6	0	6
~	c\\x7E			6	0	6

Notes:

all entries are complete programs. Almost every one prints the character based on its ASCII code. Those that deviated are marked with an *.

to print 1 I used the = command, that prints the current input line number (in this case a single newline was the input)

to print \ I called a shell script using e (the only non pure sed program)


答:
Perl 6, 77 or 74 bytes

Full program (77 bytes):

```<code>my \h=Int(get/2);say |map {$_|$^j??2>$j gcd$_??'*'!!' '!!'@'},-h..h for -h..h
</code>```

(try it online)

If it is acceptable to return the output from a lambda as a list of lists of 1-character strings (74 bytes):

```<code>{my \h=$_ div 2;map {map {$^i|$_??2>$i gcd$_??'*'!!' '!!'@'},-h..h},-h..h}
</code>```

(try it online)

Title: Visible Buildings

Body:
Perl 6, 77 or 74 bytes

Full program (77 bytes):

my \h=Int(get/2);say |map {$_|$^j??2>$j gcd$_??'*'!!' '!!'@'},-h..h for -h..h

(try it online)

If it is acceptable to return the output from a lambda as a list of lists of 1-character strings (74 bytes):

{my \h=$_ div 2;map {map {$^i|$_??2>$i gcd$_??'*'!!' '!!'@'},-h..h},-h..h}

(try it online)


答:
Python 2, <s>163</s> <s>160</s> <s>156</s> 145 bytes

This is not the golfiest way to do it, but it was one of the simplest. If I could figure out how to replace parts of strings without turning them into lists, replacing, and turning them back into strings, that would be very helpful here. Golfing suggestions welcome.

Edit: 18 bytes thanks to Leaky Nun. Try it on Ideone!

a=input();z=[" "*max(a[3])]*128
for n,v,b,e in zip(*a):z[n]=z[n][:b]+"O=#-@+0*"[v/16]*(e-b)+z[n][e:]
for i in range(128)[::-1]:print"%3d|"%i+z[i]
```

Title: Display a MIDI Track

Body:
Background

MIDI files are quite different from WAV or MP3 audio files. MP3 and WAV files contain bytes representing a "recording" of the audio, while MIDI files have a series of MIDI messages stored in MIDI events informing a MIDI synthesizer which virtual instrument to play or a MIDI sequencer the playback tempo that should be used. These messages are stored in tracks, and a collection of tracks makes up a MIDI sequence, whose events can be analyzed by a sequencer and have its messages transmitted from the sequencer to a synthesizer's receiver.

Most of the time the MIDI messages stored in MIDI events are Note On messages which tell the synthesizer to play a particular note, or Note Off messages which tell the synthesizer to stop playing the note. These messages contain two data bytes, the first of which informs the synthesizer of the velocity of the note (higher velocity results in a louder note), and the second of which tells the synthesizer the note to play (i.e. Middle C). The events themselves also contain ticks which serve the purpose of telling the sequencer when to send the messages.

The Challenge

The challenge is to write a full program or a function that analyzes a series of Note On and Note Off MIDI messages in a single-track MIDI sequence and outputs to STDOUT a chart showing when particular notes are on, when they are off, and the velocity of these notes. The vertical axis of the chart represents the note value and should be labeled as described below, and the horizontal axis represents time in MIDI ticks (though it should remain unlabeled to reduce complexity and spacing issues).

Your input may be four separate arrays or lists, each containing a series of integer values; a two-dimensional array or list containing four sub-arrays/sub-lists with a series of integer values; or any other convenient means; this represents the collection MIDI events with Note On and Note Off messages in the track. The values in the first of these arrays specifies the note, the second the velocity, the third the note on event tick, and the fourth the note off event tick. For instance, given four arrays such as these:

```<code>{60, 62, 64, 65,  67}
{20, 40, 60, 80, 100}
{ 0,  4,  8, 12,  16}
{ 2,  6, 10, 14,  18}
</code>```

Analyzing the first element of each array gives two events: an event at tick 0 with a message that has a Note On command, note 60 (Middle C), and note velocity of 20; and an event at tick 2 with a message that has a Note Off command with the same note and velocity.

Rules

The chart should feature the numbers 0 through 127 displayed in decreasing order on the left side (representing the note value), when the note starts, the duration of each note (Note Off tick minus Note On tick), and the note's velocity. The symbols representing the notes are dependent on their velocity:

0-15: O

16-31: =

32-47: #

48-63: -

64-79: @

80-95: +

96-111: 0

112-127: *

You can assume the following:

The values for note and velocity will be within the range [0, 127].

The lengths of each of the four arrays will always equal each other.

Here are a few examples:

```<code>{60, 62, 64, 65,  67}
{20, 40, 60, 80, 100}
{ 0,  4,  8, 12,  16}
{ 2,  6, 10, 14,  18}

127|
126|
125|
...
67 |                00
66 |
65 |            ++
64 |        --
63 |
62 |    ##
61 |
60 |==
59 |
...
2  |
1  |
0  |

{60, 48, 62, 47, 64, 45,  65,  43, 67, 41, 65, 43, 64, 45,  62, 47, 60, 48}
{63, 31, 75, 90, 12, 23, 122, 104, 33, 19, 57, 42,  5, 82, 109, 86, 95, 71}
{0,   0,  2,  2,  4,  4,   6,   6,  8,  8, 10, 10, 12, 12,  14, 14, 16, 16}
{2,   2,  4,  4,  6,  6,   8,   8, 10, 10, 12, 12, 14, 14,  16, 16, 18, 18}

127|
126|
...
68 |
67 |        ##
66 |
65 |      **  --
64 |    OO      OO
63 |
62 |  @@          00
61 |
60 |--              ++
59 |
...
49 |
48 |==              @@
47 |  ++          ++
46 |
45 |    ==      ++
44 |
43 |      00  ##
42 |
41 |        ==
40 |
...
1  |
0  |
</code>```

Here's an example that displays the first few notes of Ode to Joy:

```<code>{48, 55, 64, 64, 65, 67, 55, 67, 65, 64, 62, 52, 55,  60,  60,  62,  64,  55, 64, 62, 62}
{45, 45, 63, 63, 63, 63, 89, 66, 66, 66, 66, 30, 30, 103, 103, 103, 103, 127, 55, 55, 55}
{ 0,  0,  0,  4,  8, 12, 16, 16, 20, 24, 28, 32, 32,  32,  36,  40,  44,  48, 48, 54, 56}
{16, 16,  2,  6, 10, 14, 32, 18, 22, 26, 30, 48, 48,  34,  38,  42,  46,  64, 50, 55, 64}

127|
...
67 |            --  @@
66 |
65 |        --          @@
64 |--  --                  @@                  00  --
63 |
62 |                            @@          00            - --------
61 |
60 |                                00  00
59 |
58 |
57 |
56 |
55 |################++++++++++++++++================****************
54 |
53 |
52 |                                ================
51 |
50 |
49 |
48 |################
...
0  |
</code>```

You can reduce your score by 25% if your submission takes an actual MIDI sequence as input, analyzes the Note On and Note Off messages of any track of your choosing provided it contains at least four events with Note On and Note Off messages, and outputs a chart as described above.

This is code golf, so shortest code wins. Good luck!


问:
The Letter A without A
Your task is to display the letter "A" alone, without anything else, except any form of trailing newlines if you cannot avoid them, doing so in a program and/or snippet. Code that returns (instead of printing) is allowed.

Both the lowercase and uppercase versions of the letter "A" are acceptable (that is, unicode U+0061 or unicode U+0041. Other character encodings that aren't Unicode are allowed, but either way, the resulting output of your code must be the latin letter "A", and not any lookalikes or homoglyphs)

You must not use any of the below characters in your code, regardless of the character encoding that you pick:

"A", whether uppercase or lowercase.

"U", whether lowercase or uppercase.

X, whether uppercase or lowercase.

+

&

#

0

1

4

5

6

7

9

Cheating, loopholes, etc, are not allowed.

Since this is code-golf, the shortest solution, in bytes, that follows all the rules, is the winner.

Validity Checker

This Stack Snippet checks to make sure your code doesn't use the restricted characters. It might not work properly for some character encodings.

var t = prompt("Input your code.");

if (/[AaUuXx+&#0145679]/.test(t)) {
  alert("Contains a disallowed character!");
} else {
  alert("No disallowed characters");
}```
</div>
</div>
</p>

<p><em>This Stack Snippet that makes sure you don't have a disallowed character is also available on JSFiddle.</em></p>

<h3>Leaderboard</h3>

<p><div class="snippet" data-lang="js" data-hide="true" data-console="false" data-babel="false">
<div class="snippet-code snippet-currently-hidden">
<pre class="snippet-code-js lang-js prettyprint-override"><code>var QUESTION_ID=90349,OVERRIDE_USER=58717;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;</code>```

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}```
<pre class="snippet-code-html lang-html prettyprint-override"><code><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td>Link</td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td>Link</td></tr></tbody> </table></code>```

答:
Bash, <s>14</s> 13 bytes

tr PQ @-B<<<Q
```
<p><strong>Output:</strong></p>
<pre class="lang-sh prettyprint-override"><code>A
</code>```

Title: The Letter A without A

Body:
Bash, <s>14</s> 13 bytes

tr PQ @-B<<<Q

Output:

A

ContentLicense: CC BY-SA 4.0


问:
Smallest palindrome divisible by the input
Given a positive integer N, output the smallest positive integer such that this number is a palindrome (i.e. is its own reverse) and is divisible by N.

The palindrome (i.e. the output) must not need a leading zero to be a palindrome, e.g. 080 is not the valid answer for 16.

The input will never be a multiple of 10, because of the previous reason.

Your program may take as much time as necessary, even if in practice it would be way too long to output the answer.

Inputs and outputs

You may take the input through STDIN, as a function argument, or anything similar.

You may print the output to STDOUT, return it from a function, or anything similar.

Inputs and outputs must be in the decimal base.

Test cases

```<code>N        Output
1        1
2        2
16       272
17       272
42       252
111      111
302      87278
1234     28382
</code>```

Scoring

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

答:
S.I.L.O.S, 109 bytes

```<code>readIO
n = 0
lbla
n + i
a = n
r = 0
lblb
m = a
m % 10
r * 10
r + m
a / 10
if a b
r - n
r |
if r a
printInt n
</code>```

Try it online!

Body:
S.I.L.O.S, 109 bytes

readIO
n = 0
lbla
n + i
a = n
r = 0
lblb
m = a
m % 10
r * 10
r + m
a / 10
if a b
r - n
r |
if r a
printInt n

Try it online!


答:
R, 104 bytes

Unlike the other R solution posted, this one takes input from stdin.

```<code>s=scan();sapply(1:s[2],function(i){j=i+s[1];if((all(i%%(3:i-1)!=0)|i==2)&all(j%%(3:j-1)!=0))cat(i," ")})
</code>```

Ungolfed:

```<code>s=scan();        # Read from stdin
sapply(1:s[2],   # For i from 1 to u,
    function(i){     # apply this function:
        j=i+s[1];                # Define i+k
        if((all(i%%(3:i-1)!=0)   # Test if i is prime
           | i==2)               # (i is prime if i==2)
           & all(j%%(3:j-1)!=0)) # Test if i+k is prime
        cat(i," ")               # If i and i+k are prime, print i
    }
)
</code>```

Title: Variable Prime "Twins"

Body:
I am 2/3 twins with my brother, i.e. born on the same day of the same month but twelve years later. When I was 5, he was 17, both primes; the last pair of ages we can reasonably count on is [71, 83] with both of us being alive and able to celebrate this coincidental jubilee.

Task

Create a code that

takes two integers as input: the difference between the counter and the "twin" as a positive integer k (well yes, I'm the younger) and the upper bound as a positive integer u (runtime consideration)

and gives output as an array or list of all i numbers lower than or equal u for which both i and i+k are primes. The output does not need to be sorted.

Test Cases

```<code>12, 1000 -> [5, 7, 11, 17, 19, 29, 31, 41, 47, 59, 61, 67, 71, 89, 97, 101, 127, 137, 139, 151, 167, 179, 181, 199, 211, 227, 229, 239, 251, 257, 269, 271, 281, 337, 347, 367, 389, 397, 409, 419, 421, 431, 449, 467, 479, 487, 491, 509, 557, 587, 601, 607, 619, 631, 641, 647, 661, 727, 739, 757, 761, 797, 809, 811, 827, 907, 929, 941, 971, 997]
2, 999 -> [3, 5, 11, 17, 29, 41, 59, 71, 101, 107, 137, 149, 179, 191, 197, 227, 239, 269, 281, 311, 347, 419, 431, 461, 521, 569, 599, 617, 641, 659, 809, 821, 827, 857, 881]
3, 1500 -> [2]
30, 1500 -> [7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 53, 59, 67, 71, 73, 79, 83, 97, 101, 107, 109, 127, 137, 149, 151, 163, 167, 181, 193, 197, 199, 211, 227, 233, 239, 241, 251, 263, 277, 281, 283, 307, 317, 337, 349, 353, 359, 367, 379, 389, 401, 409, 419, 431, 433, 449, 457, 461, 479, 491, 541, 547, 557, 563, 569, 571, 577, 587, 601, 613, 617, 631, 643, 647, 653, 661, 709, 727, 739, 743, 757, 797, 809, 823, 827, 829, 853, 857, 877, 881, 907, 911, 937, 941, 947, 953, 967, 983, 991, 1009, 1019, 1021, 1031, 1033, 1039, 1061, 1063, 1087, 1093, 1123, 1151, 1163, 1171, 1187, 1193, 1201, 1229, 1249, 1259, 1277, 1289, 1291, 1297, 1399, 1409, 1423, 1429, 1451, 1453, 1459, 1481, 1493]
</code>```

Edit

Since I failed to specify the upper bound, both inclusive and exclusive solutions are welcome.

Edit No. 2

The challenge ends on 1st September, one week from the start.

Looks like we have a winner but in case of a tie popularity is the tie-breaker; in this case the "second" will be compensated via bounty.

Body:
R, 104 bytes

Unlike the other R solution posted, this one takes input from stdin.

s=scan();sapply(1:s[2],function(i){j=i+s[1];if((all(i%%(3:i-1)!=0)|i==2)&all(j%%(3:j-1)!=0))cat(i," ")})

Ungolfed:

s=scan();        # Read from stdin
sapply(1:s[2],   # For i from 1 to u,
    function(i){     # apply this function:
        j=i+s[1];                # Define i+k
        if((all(i%%(3:i-1)!=0)   # Test if i is prime
           | i==2)               # (i is prime if i==2)
           & all(j%%(3:j-1)!=0)) # Test if i+k is prime
        cat(i," ")               # If i and i+k are prime, print i
    }
)


答:
Javascript (ES6), <s>114</s> <s>113</s> 105 bytes

This started as a port of Leaky Nun's C version and was then further optimized. Most optimizations are specific to JS.

```<code>n=>(r=j=>i<n?('*@*'[1+(g=(i,j)=>j?g(j,i%j):i)(i-m,j-m)]||' ')+(++j<n?'':(i++,`
`))+r(j%n):'')(i=0,m=n>>1)
</code>```

Example:

let f =
n=>(r=j=>i<n?('*@*'[1+(g=(i,j)=>j?g(j,i%j):i)(i-m,j-m)]||' ')+(++j<n?'':(i++,`
`))+r(j%n):'')(i=0,m=n>>1)

console.log(f(7))```

Title: Visible Buildings

Body:
Javascript (ES6), <s>114</s> <s>113</s> 105 bytes

This started as a port of Leaky Nun's C version and was then further optimized. Most optimizations are specific to JS.

n=>(r=j=>i<n?('*@*'[1+(g=(i,j)=>j?g(j,i%j):i)(i-m,j-m)]||' ')+(++j<n?'':(i++,`
`))+r(j%n):'')(i=0,m=n>>1)

Example:

let f =
n=>(r=j=>i<n?('*@*'[1+(g=(i,j)=>j?g(j,i%j):i)(i-m,j-m)]||' ')+(++j<n?'':(i++,`
`))+r(j%n):'')(i=0,m=n>>1)

console.log(f(7))


问:
Non-palindromic numbers
A strictly non-palindromic number N is a number that isn't a palindrome in any base (in bases 2 to N-2).  These numbers are listed on OEIS

For example, the number 19 in base 2,3,4,5,6,...17 is: 10011,201,103,34,31,...12.  None of these representations is palindromic, so the number is strictly non-palindromic.

For this challenge, you need to return a truthy value if the number is non-palindromic, otherwise a falsy value.

You may assume the number passed to you is greater than or equal to 0.

Your program should work for values up to your languages' integer size.

Test cases:

Truthy:

```<code>0
1
2
3
4
6
11
19
47
53
79
103
389
997
1459
</code>```

Falsy:

```<code>5
7
8
9
10
13
16
43
48
61
62
101
113
211
1361
</code>```

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

Title: Non-palindromic numbers

Body:
C, 77 bytes

h(n,b,k,z){for(z=0,k=n;z+=k%b,k/=b;z*=b);return b+3>n?1:z==n?0:h(n,++b,0,0);}

recursive exercise...i change (b+2>=n) with (b+3>n) whithout debugging...

main()
{int  v[]={0,1,2,3, 4, 6,11,19,47,53,79,103,389,997,1459},
  n[]={5,7,8,9,10,13,16,43,48,61,62,101,113,211,1361}, m;
    // 0 1 2 3  4  5  6  7  8  9 10  11  12  13   14
 for(m=0; m<15; ++m)
    printf("%u=%u\n", v[m], h(v[m],2,0,0));
 for(m=0; m<15; ++m)
    printf("%u=%u\n", n[m], h(n[m],2,0,0));
}

/*
 77
 0=1
 1=1
 2=1
 3=1
 4=1
 6=1
 11=1
 19=1
 47=1
 53=1
 79=1
 103=1
 389=1
 997=1
 1459=1
 5=0
 7=0
 8=0
 9=0
 10=0
 13=0
 16=0
 43=0
 48=0
 61=0
 62=0
 101=0
 113=0
 211=0
 1361=0
*/


问:
Brainf*ck Loop Problem
I have a problem for a cyber club that asks you to print:

```<code>ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!
</code>```

Using Brainf**k in 29 bytes or less without using the ',' character.

I have a working code:

```<code>++++++++++[>++++++>+++++++++<<-]>-->.<[>-.<-]
</code>```

However my loop is too long, sending me 16 bytes over the limit.

Is there a more efficient way to set the second and third cell to 58 and 90 so I can run my second loop? Or is there a better way to do this all together that I am just not seeing?

答:
<s>27</s> 24 bytes

```<code>++[<++[++<]>>>+]<[-<-.>]
</code>```

<s>Spent a whole day basically writing up a brute forcer and watching the results come in. Now I can get back to doing some actual work...</s> Another day of brute forcing later...

Try it online!

The component ++[<++[++<]>>>+] initialises the tape to

```<code>[130, 0, 0, 0, 91, 59, 0]
                       ^
</code>```

which is just perfect for what we need!

Title: Brainf*ck Loop Problem

Body:
<s>27</s> 24 bytes

++[<++[++<]>>>+]<[-<-.>]

<s>Spent a whole day basically writing up a brute forcer and watching the results come in. Now I can get back to doing some actual work...</s> Another day of brute forcing later...

Try it online!

The component ++[<++[++<]>>>+] initialises the tape to

[130, 0, 0, 0, 91, 59, 0]
                       ^

which is just perfect for what we need!


问:
The Burnt Pancake Problem
This challenge is related to Flipping Pancakes.

You may have heard of pancake sorting, where a stack of pancakes is sorted by size by inserting spatula into the stack and flipping all of the pancakes above the spatula, until the pancakes are sorted smallest to largest on the plate. The burnt pancake problem is slightly different. All pancakes now have one side that is burnt, and the burnt side of each pancake must face the plate once the sorting is completed.

For example, given the following stack (size of pancake on the left. 0 meaning burnt-side down and 1 meaning burnt-side up on the right):

```<code>1 0
3 1
2 1
</code>```

You may flip the whole stack to get 20 30 11, flip the top two to get 31 21 11 and flip the whole stack again to get 10 20 30, a sorted stack of burnt pancakes. This sequence of moves, flip 3, flip 2, flip 3, could be represented as 3 2 3.

The Challenge

Given an array of pancakes sizes (not necessarily unique) and their orientations, output any valid burnt pancake sorting sequence, that is, a sequence of flips that leads to the stack of pancakes being sorted from smallest to largest with burnt sides down.

Input and output may be any sane format with separators, but please specify which formats you use and state which end of your input format is the top of the stack (TOS).

Flipping zero pancakes is allowed.

Mixing separators in the input/output is allowed.

Test cases

For all of the following test cases, input is a list and output is a space-separated string, and TOS is on the left.

```<code>[[1, 0], [3, 1], [2, 1]]
"3 2 3"

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

[[5, 1], [3, 0], [3, 0], [1, 1]]
"4 3 2 3"
</code>```

As always, if anything is unclear or incorrect, please let me know in the comments. Good luck and good golfing!

答:
Python 2, 83

Input is expected to be the list of (size, orientation) tuples with the stack's top at the end. The output is a list of sizes to flip separated by various kinds of whitespace.

a=input()
while a:i=a.index(max(a));print len(a)-i,a[i][1],len(a),i;a=a[i+1:]+a[:i]
```

Title: The Burnt Pancake Problem


问:
Find the right path
Given a list of paths, output the correct path.

Example of path:

```<code>    /\
----+/
    |
</code>```

- and | are horizontal and vertical paths.

/ and \ are 90° turns.

+ is treated as a - or a | depending of the current direction.

Paths may go in any direction and a character may be used in multiple paths.

Input will be like this:

```<code>       /--\
A------+--+--#
B------/  \--:
C------------#
D------------#
</code>```

A, B, C and D are path starts

# is a wall (the path is bad)

: is the end (the path is correct)

So here the output will be B.

You can assume:

: and # will always be reached from the left.

The character at the right of the start of a path will always be -.

Paths will always be well formed.

# and : will always be in the same column.

There will always be only one : and 4 paths.

Test cases

```<code>A------#
B------#
C------#
D------:
=>
D
</code>```

```<code>A-\ /---:
B-+-/ /-#
C-+---+-#
D-+---/
  \-----#
=>
B
</code>```

```<code>  /-\
A-+\\---#
B-/\-\/-#
C----++-#
D----+/
     \--:
=>
A
</code>```

```<code>A-\
B-+\
C-++\/----#
D-+++//---:
  \++-//--#
   \+--//-#
    \---/
=>
A
</code>```

```<code>  /-\
A-+-/-\
B-+-+-\--#
C-+-/ |/-#
D-\---++-#
  \---+/
      \--:
=>
B
</code>```

Since this is code-golf, the shortest answer win.

答:
Slip, 47 bytes

```<code>`a(?,[`-+]*((`/<|`\>)[`|+]*(`/>|`\<)[`-+]*)*`:)
</code>```

Test it here.

Yay for undocumented features...

Explanation

Slip is basically a two dimensional regex syntax and by default Slip programs print the subset of the input that they matched. In this case I'm simply matching a valid path. To prevent printing the entire path, I'm usng the undocumented (?,...) groups which simply indicate that the characters matched inside should be omitted from the output.

As for the regex, unfortunately, there's some duplication because \ and / need to be treated differently depending on whether we're moving horizontally or vertically. On the plus side, since we know that the path starts and ends horizontally, we know that there's an even number of \ or / in every path, so that we can match two of them at a time.

```<code>`a             # Match a letter.
(?,            # Match but don't include in output...
  [`-+]*       #   Match a horizontal piece of path, consisting of - or +.
  (            #   Match 0 or more vertical segments...
    (`/<|`\>)  #     Match a / and turn left, or a \ and turn right.
    [`|+]*     #     Match a vertical piece of path, consisting of | or +.
    (`/>|`\<)  #     Match a / and turn right, or a \ and turn left.
    [`-+]*     #     Match a horizontal piece of path, consisting of - or +.
  )*
  `:           #   Match a : to ensure that this is the correct path.
)
</code>```

Title: Find the right path

Body:
Slip, 47 bytes

`a(?,[`-+]*((`/<|`\>)[`|+]*(`/>|`\<)[`-+]*)*`:)

Test it here.

Yay for undocumented features...

Explanation

Slip is basically a two dimensional regex syntax and by default Slip programs print the subset of the input that they matched. In this case I'm simply matching a valid path. To prevent printing the entire path, I'm usng the undocumented (?,...) groups which simply indicate that the characters matched inside should be omitted from the output.

As for the regex, unfortunately, there's some duplication because \ and / need to be treated differently depending on whether we're moving horizontally or vertically. On the plus side, since we know that the path starts and ends horizontally, we know that there's an even number of \ or / in every path, so that we can match two of them at a time.

`a             # Match a letter.
(?,            # Match but don't include in output...
  [`-+]*       #   Match a horizontal piece of path, consisting of - or +.
  (            #   Match 0 or more vertical segments...
    (`/<|`\>)  #     Match a / and turn left, or a \ and turn right.
    [`|+]*     #     Match a vertical piece of path, consisting of | or +.
    (`/>|`\<)  #     Match a / and turn right, or a \ and turn left.
    [`-+]*     #     Match a horizontal piece of path, consisting of - or +.
  )*
  `:           #   Match a : to ensure that this is the correct path.
)