text:
Make this code explanation pretty again
Introduction
Most code-golfers here add explanations to their submissions, so it's easier to understand what's going on. Usually the codelines go on the left and the corresponding explanation to the right with some kind of separator. To make it look pretty, the separators are all on the same column. Also long explanation text is usually wrapped to the next line, so the readers don't have to scroll horizontally to read everything.
However, when you want to edit this explanation because you made some crazy golfs, you often end up spending time to make your explanation pretty again. Since this is a very repetitive task, you want to write a program for this.
The Challenge
Given several lines of code with explanation and a separator, output the nicely formatted code with explanation.
Example
Input

shM-crz1dc4."ANDBYOROF  # z = input

     rz1      # convert input to uppercase
    c   d        # split input on spaces
         c4."ANDBYOROF        # create a list of the words from a packed string which shall be ignored
   -          # filter those words out
 hM                # only take the first letter of all words
s                   # join them into one string

Output

shM-crz1dc4."ANDBYOROF     # z = input

     rz1                   # convert input to uppercase
    c   d                  # split input on spaces
         c4."ANDBYOROF     # create a list of the words from a packed string which shall be
                           # ignored
   -                       # filter those words out
 hM                        # only take the first letter of all words
s                          # join them into one string

One cookie for the first one who can find out what this code does.
The formatting algorithm

Find the longest code-line (excluding the explanation and the spaces between code and separator).
Add 5 spaces after this code-line and append the corresponding separator with explanation. This is now the reference line.
Adjust every other line to this reference line, so that the seperators are all in the same column.
Wrap all lines that are longer than 93 characters to a new line in the following way:

Find the last word which end is at column 93 or lower.
Take all words after this one and wrap them to a new line with the leading separator and the correct spacing. The space between those two words has to be deleted, so the first line ends with a word character and the second line starts with one after the separator.
If the resulting line is still longer than 93 characters do the same again until every line is below 94 characters.

Notes

A word consists of non-whitespace characters. Words are separated by a single space.
The word wrapping is always possible. This means that no word is so long that it would make the wrapping impossible.
The input will only contain printable ASCII and won't have any trailing whitespaces
The separator will only appear once per line.
While the explanation can have unlimited length, the separator and the code can only have a combined maximum length of 93 - 5 = 87 chars. The 5 chars are the spaces between code and separator. Code and separator will always be at least one character long.
The input may contain empty lines. Those will never contain any characters (except a newline if you take input as multiline string). Those empty lines have to be present in the output as well.
Every line will have some code, a separator and an explanation. Exceptions are empty lines.
You may take the input in any reasonable format, as long as it is not pre-processed. Make it clear in your answer which one you use.
Output can be a multiline string or a list of strings.

Rules

Function or full program allowed.
Default rules for input/output.
Standard loopholes apply.
This is code-golf, so lowest byte-count wins. Tiebreaker is earlier submission.

Test cases
Input format here is a list of string representing the lines and a single string for the separator. Both are separated by a comma. Output is a list of strings.

['shM-crz1dc4."ANDBYOROF  # z = input', '', '     rz1      # convert input to uppercase', '    c   d        # split input on spaces', '         c4."ANDBYOROF        # create a list of the words from a packed string which shall be ignored', '   -          # filter those words out', ' hM                # only take the first letter of all words', 's                   # join them into one string'], "# " -> ['shM-crz1dc4."ANDBYOROF     # z = input', '', '     rz1                   # convert input to uppercase', '    c   d                  # split input on spaces', '         c4."ANDBYOROF     # create a list of the words from a packed string which shall be', '                           # ignored', '   -                       # filter those words out', ' hM                        # only take the first letter of all words', 's                          # join them into one string']
['codecodecode   e#Explanation', 'sdf dsf sdf e#A Very very very very very very very very very long long long long long long long long long long long explanation and it keeps getting longer and longer', '', 'some more codee#  and some more explanation'], "e#" -> ['codecodecode       e#Explanation', 'sdf dsf sdf        e#A Very very very very very very very very very long long long long long ', '                   e#long long long long long long explanation and it keeps getting longer', '                   e#and longer', '', 'some more code     e# and some more explanation']

Happy Coding!

@Matt All seperators are always at column length of the longest code-line + 5. This also applied to lines which only contain an explanation, because they were wrapped.

Oh my god I have being doing this wrong this for the last 3 hours. I was trying to wrap long code and leaving the explanations long..... Well starting over. At least now it is easier. Thanks. You worded it fine.... I'm just silly.

Wrap all lines that are longer than 93 characters Does that mean the code, including leading spaces, will never be more than 87 characters long?

@Matt The code and the seperator together will never be longer than 87 characters since we need 5 spaces between code and seperator and one character for the explanation.

The Pyth code finds the abbreviation of any given string. I would know because that was an answer to my question.

Ruby, 245 237 220 216 212 209 205 bytes
Anonymous function. Pretty basic approach (find max length, add 5, then do processing on each line, with recursion to deal with wrapping) and there might be another approach that saves more bytes.
I deleted the answer earlier that didn't fulfill all the requirements; I didn't want to have a half-answered code as an answer (it was getting downvotes for being incomplete too) but it should do everything the question asks for, now.
->x,d{l,S=0," "
s=->n{m,q=n.size,94-l-d.size
m>q ?(i=n.rindex(S,q)
n[0,i]+"
"+S*l+d+s[n[i+1,m]]):n}
x.map{|n|c,t=n.split d
c=(c||S).rstrip
l=[l,5+c.size].max
[c,t]}.map{|c,t|c+S*(l-c.size)+d+s[t]if t}*"
"}

Changelog:

Saved some bytes by leveraging some of the promises in the input, especially the promise that all non-empty lines have the separator character and an explanation.
Managed to golf a little more by saving the split strings from the first map call and taking out some unnecessary strip functions based on the promise that the words in the explanation always have exactly one space between them. Also, " " is assigned to a constant now since I use it so much.
Chained both of the map calls together by leveraging the power of higher-order functions, meaning that the first map call will set the length variable l correctly even if it's called after the declaration of the helper function s. -4 bytes.
Abused multiline strings to replace \n with actual newlines, plus a little trick using if over ternary operators (when join is called on an array with nil values, they become empty strings)
.join can apparently be replaced with a *.

I think it should be fixed now?

how does this wrap at 94?

All right, now that I had more time to work on the code, it wraps properly.

" While the explanation can have unlimited length, the separator and the code can only have a combined maximum length of 93 - 5 = 87 chars. The 5 chars are the spaces between code and separator. Code and separator will always be at least one character long."
Your code section is way past the limit, with 97 characters, so the program has undefined behavior.

ah, well spotted, makes sense!

LiveScript, 243 236 233 228 219 225 bytes
f = (x,k,m+5)->l=(.length);x.=map(->it/"#k"=>..0-=/ +$/;m>?=5+l ..0);i=0;[..0&&..0+' '*(m- l ..0)+k+..1 for x]=>while i<(l ..),++i=>j=(s=..[i])lastIndexOf ' ' 93;(..splice i+1 0 ' '*m+k+s[j to]*'';s.=substr 0 j) if 94<l s;..[i]=s

How it works: mostly like the Java code. Start off by aliasing length (LiveScript allows to create a function from operators by using parentheses).
.= is a = a.b - which we use here to map.
=> blabla .. is the Smalltalk-ish cascade construct: the left side of => is accessible as .. for the rest of the block; and will be returned. Here, it's the element split on k. Note: I'm using string interpolation, because / only means "split" with a literal string.
LS allows us to use a-=/regexp/ in this lambda as well (also works with string literals): it's just sugar for a .replace call.
Finally, the >?= is the combinatory >?-assign operator, which returns the greater of two operands.
LS has Python/Haskell-style for comprehensions, with nothing fancy in them, except the "string * times" to repeat the space long enough.
This for comprehension serves as the topic (see the block about cascades anove).
We then loop into each element of the array (the one we just built with the comprehension), and if any line is bigger than 93chars, we find the last index of , split there, and push the separated line right after this current iteration's (... So that the next iteration will split again if the line's too big).
Only last thing fancy a[j to] is a range (from j to the end), but since it uses Array methods we have to join it back to a string, which we do using overloaded *: *''.
example
s = """this is kod # Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
d # y

efgh # z"""

f = (x,k,m=5)->l=(.length);x.=map(->it/"#k"=>..0-=/ +$/;m>?=5+l ..0);i=0;[..0&&..0+' '*(m- l ..0)+k+..1 for x]=>while i<(l ..),++i=>j=(s=..[i])lastIndexOf ' ' 93;(..splice i+1 0 ' '*m+k+s[j to]*'';s.=substr 0 j) if 94<l s;..[i]=s

console.log (f s / '\n', '#') * \\n

output:
this is kod     # Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod
                # tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim
                # veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea
                # commodo consequat. Duis aute irure dolor in reprehenderit in voluptate
                # velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat
                # cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id
                # est laborum.
d               # y

efgh            # z

to whoever downvoted: the answer is fixed.

When an explanation overflows, you need the new line(s) to align their separator characters with the rest, IIRC.

@KevinLau well spotted, fixed!

Can you update your example output as well?

@KevinLau done.

Java, 347 + 19 = 366 bytes
Requires
import java.util.*;

Thus the +19 bytes.
(c,s)->{int p=0,i=0,t;String l;for(;i<c.size();i++){l=c.get(i);l=l.replaceAll(" *"+s,s);p=Math.max(l.indexOf(s),p);c.set(i,l);}p+=5;for(i=0;i<c.size();i++){l=c.get(i);t=l.indexOf(s);while(t>-1&t<p)l=l.substring(0,t)+" "+l.substring(t++);t=93;if(l.length()>t){while(l.charAt(t)!=' ')t--;c.add(i+1,s+l.substring(t));l=l.substring(0,t);}c.set(i,l);}}

Takes in the format f.accept(List<String> code, String seperator). Formats in-place. A version that creates and returns a new List<String> would be trivial to implement but cost some bytes.
Indented + example usage:
static BiConsumer<List<String>, String> prettify = (code, seperator) -> {
    int space = 0, i=0, t;
    String line;
    for (; i<code.size(); i++) { // for each line
        line = code.get(i); // get line
        line = line.replaceAll(" *" + seperator, seperator); // strip space before seperator
        space = Math.max(line.indexOf(seperator), space); // save biggest space until seperator
        code.set(i, line); // save line
    }
    space += 5;
    for (i=0; i<code.size(); i++) { // for each line
        line = code.get(i); // get line
        t = line.indexOf(seperator); // get index of seperator
        while (t>-1&t<space) // while the seperator exists and is further left than desired
            line = line.substring(0,t) + " " + line.substring(t++); // move it right by adding a space before it
        t = 93; // get desired line length
        if (line.length()>t) { // if the line is longer than that
            while (line.charAt(t)!=' ') t--; // scan backwards for a space
            code.add(i+1, seperator + line.substring(t)); // add a line after this one with seperator and the rest of the line
                                                          // the next pass will space it correctly
            line = line.substring(0,t); // cut off this line at that point
        }
        code.set(i, line); // save edited line back to List
    }
};

public static void main(String[] args) {
    List<String> code = new ArrayList<>();
    code.add("shM-crz1dc4.\"ANDBYOROF  # z = input");
    code.add("");
    code.add("     rz1      # convert input to uppercase");
    code.add("    c   d        # split input on spaces");
    code.add("         c4.\"ANDBYOROF        # create a list of the words from a packed string which shall be ignored");
    code.add("   -          # filter those words out");
    code.add(" hM                # only take the first letter of all words");
    code.add("s                   # join them into one string");
    prettify.accept(code, "#");
    code.stream().forEach(System.out::println);
}

... I should probably run this through itself :P

If anyone can figure out why replace(" *"+s) isn't working but replaceAll(" *"+s) is I'd love to hear it -- I can't figure it out.

 replace uses strings but replaceAll uses regexes.

@CatsAreFluffy well, you're correct! Don't know how I didn't realize that :P

Can't you remove the newline?

Well the newline can be removed because of required semi:s (which should be .s but whatever)

@CatsAreFluffy The import was on a separate line to show that it was a separate component and the new line wasn't counted. As this wasn't clear enough I've edited the post to make it more .

You don't need parenthesis around the c,s->

@FlipTack I can't get it to compile as such with javac 1.8.0_91

That's odd, compiles fine for me (eclipse, java 8)

@FlipTack put your modified code in ideone and give me a link if it works there

@CAD97 I'll have a go when I get to a computer.

PowerShell, 224 217 235 bytes
param($d,$s)$d=$d-split"`r`n";$p="\s+\$([char[]]$s-join"\")\s";$m=($d|%{($_-split$p)[0].Length}|sort)[-1];$d|%{$l,$c=$_-split$p;$c=if($c){"$s "+(("$c "-split"(.{1,$(87-$m)})\s"|?{$_})-join"`n$(" "*($m+5))$s ")}$l.PadRight($m+5," ")+$c}

Updated the logic to determine the max code string length. Updated to allow multiple separators that include regex meta characters.

Little Explanation
This takes in a whole newline delimited string for input.
param($d,$s)
# $d is a newline delimited string. $s is the separator.
# Take the string and turn it into a string array. Stored as $d
$d=$d-split"`r`n"
# Save a regex pattern as it is used more than once
$p="\s+\$([char[]]$s-join"\")\s"
# Get the longest string of code's length
$m=($d|%{($_-split$p)[0].Length}|sort)[-1]
# Split each line again into code and comment. Write out each line with formatted explanations based on separator column position $m
$d|%{
# Split the line
$l,$c=$_-split$p
# Build the comment string assuming there is one.
$c=if($c){"$s "+(("$c "-split"(.{1,$(87-$m)})\s"|?{$_})-join"`n$(" "*($m+5))$s ")}
# Pad the right amount of space on the code and add the comment string.
$l.PadRight($m+5," ")+$c
}

Sample Output with some Lorem Ipsum
shM-crz1dc4."ANDBYOROF     # z = input

     rz1                   # convert input to uppercase
    c   d                  # split input on spaces
         c4."ANDBYOROF     # But I must explain to you how all this mistaken idea of
                           # denouncing pleasure and praising pain was born and I will give
                           # you a complete account of the system, and expound the actual
                           # teachings of the great explorer
   -                       # filter those words out
 hM                        # only take the first letter of all words
s                          # join them into one string

@nimi Hopefully the updates now make for a better solution.

@nimi Anything else you notice wrong? I apparently am having issues reading the last couple of days.

No. Now have a +1.

MATLAB, 270 265 262 bytes
function d=f(I,s);S=@sprintf;R=@regexprep;m=regexp(I,['\s*\',s]);L=max([m{:}])+4;a=@(x)S('%-*s%s',L,x,s);b=@(x)R(R(x,S('(.{1,%d}(\\s+|$))',93-L),S('$1\n%*s ',L+1,s)),['\n\s*\',s,' $'],'');c=R(I,['(.*?)\s*\',s,'\s*(.*$)'],'${a($1)} ${b($2)}');d=S('%s\n',c{:});end

The program accepts the input I in the form of a cell array of strings where each element of the cell array is a separate line of the input. It also accepts a second input which indicates what the comment character is (i.e. #). The function returns a multi-line string that is properly formatted.
Brief Explanation
function d = f(I,s)
    %// Setup some shortcuts for commonly-used functions
    S = @sprintf;
    R = @regexprep;

    %// Find the location of the space AFTER each code block but before a comment
    m = regexp(I, ['\s*\',s]);

    %// Compute the maximum column location of the code and add 4 (5 - 1)
    L = max([m{:}]) + 4;

    %// This is a callback for when we detect code
    %// It left justifies and pads the string to L width
    a = @(x)S('%-*s%s', L, x, s);

    %// This is a callback for when we detect a comment.
    b = @(x)R(...
            R(x, ...
                S('(.{1,%d}(\\s|$))', 93 - L), ... Regex for wrapping text to desired width
                S('$1\n%*s ', L+1, s)), ... Append a newline and padding for next line
            ['\n\s*\',s,' $'], ''); ... Remove the trailing newline (to be improved)

    %// Perform replacement of everything.
    c = R(I, ...
            ['(.*?)\s*\',s,'\s*(.*$)'], ... Match "code comment_char comment"
            '${a($1)} ${b($2)}');   ... Replace using the output of the callbacks

    %// Concatenate all of the strings together with a newline in between
    d=S('%s\n',c{:});
end

Example Input
I = {
    'shM-crz1dc4."ANDBYOROF  # z = input'
    ''
    '     rz1      # convert input to uppercase'
    '    c   d        # split input on spaces'
    '         c4."ANDBYOROF        # create a list of the words from a packed string which shall be ignored'
    '   -          # filter those words out'
    ' hM                # only take the first letter of all words'
    's                   # join them into one string'
};

disp(f(I,'#'));

Example Output
shM-crz1dc4."ANDBYOROF     # z = input

     rz1                   # convert input to uppercase
    c   d                  # split input on spaces
         c4."ANDBYOROF     # create a list of the words from a packed string which shall be
                           # ignored
   -                       # filter those words out
 hM                        # only take the first letter of all words
s                          # join them into one string

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Addition in base -1+i
Gaussian integers are complex numbers of the form a+bi where a and b are both integers. In base -1+i, all Gaussian integers can be uniquely represented using the digits 0 and 1, without the need for a symbol to denote sign.
For instance, 1100 in base -1+i represents the decimal number 2, since
1*(-1+i)^3 + 1*(-1+i)^2 + 0*(-1+i)^1 + 0*(-1+i)^0
= (2+2i) + (-2i) + 0 + 0
= 2

Input will be two Gaussian integers in base -1+i  represented using the digits 01. This can take one of the following forms:

Two separate digit strings,
Two decimal integers consisting of 01 representing the base -1+i numbers (e.g. 1100 for 2 in base -1+i),
Two binary integers representing the base -1+i numbers (e.g. decimal 12 or 0b1100 for 2 in base -1+i)
A single string separating two digit strings/binary integers by a single non-alphanumeric separator (e.g. 1100 1100 or 12,12 for 2+2)

Output the sum of the two Gaussian integers, also in base -1+i and represented using the digits 01 (in one of the formats allowed as input, not necessarily the same choice). The output is allowed to contain a finite number of leading zeroes.
Your function or program must terminate within 2 seconds for inputs of at most 30 digits each.
Additional clarifications

You may assume that the input contains no extraneous leading zeroes. For the special case of 0, you may choose either 0 or the empty string as the representation.

Test cases
0, 0 => 0                                      # 0 + 0 = 0
0, 1 => 1                                      # 0 + 1 = 1
1, 1 => 1100                                   # 1 + 1 = 2
1100, 1100 => 111010000                        # 2 + 2 = 4
1101, 1101 => 111011100                        # 3 + 3 = 6
110111001100, 1110011011100 => 0               # 42 + (-42) = 0
11, 111 => 0                                   # i + (-i) = 0
11, 110 => 11101                               # i + (-1-i) = -1
10101, 11011 => 10010                          # (-3-2i) + (-2+3i) = (-5+i)
1010100101, 111101 => 1110100000100            # (-19+2i) + (3-4i) = (-16-2i)

Longer test cases:
11011011010110101110010001001, 111100010100101001001010010101 => 0
111111111111111111111111111111, 111111111111111111111111111111 => 100100100100100100100100100100
101101110111011101110111011101, 101101110111011101110111011101 => 11101001010001000100010001000100011100
100100010101001101010110101010, 100010011101001011111110101000 => 110000110010101100001100111100010

No digit lists?

@CatsAreFluffy No digit lists, sorry.

@CatsAreFluffy: If you really want a list, you could just use an existing answer to repeatedly add 1.

You can save one byte by changing -1+i to i-1 in the title.

Now we need a conversion the other way around. :P

anybody who even attempts doing this in brainf*ck will get an upvote for all  that math they probably did.

There are 1100 types of people in the world. Those who understand binary, those who don't, those who confuse it with ternary, those who confuse it with base 4, those who confuse it with base 5, those who confuse it with base -1+i, those who confuse it with base 6, those who confuse it with base 7, those who confuse it with base 8, those who confuse it with base 9...

@wizzwizz4 ..., those who confuse it with base i.

Python 2, 98 97 91 84 bytes
s=input();L=1
for _ in`s`*8:s+=1098*int(str(s).translate('0011'*64));L*=10
print s%L

This does I/O in decimal. The integers have to be separated by the non-alphanumeric character +.
Thanks to @xnor for golfing off 2 bytes!
Try it on Ideone.
How it works
In Arithmetic in Complex Bases, the author shows how to add and multiply complex numbers in bases of the form -n + i.
For base -1 + i, addition is done similarly to regular, binary addition with carry, with two differences:

Instead of carrying 1 to the next higher position, we carry 110 to the next three.
Carry digits can propagate indefinitely. However, without leading zeroes, the sum a + b has at most eight digits more than the maximum of a and b.

We proceed as follows.

First, we add a and b as if their digits were decimal digits.
For a = 10101 and b = 11011, this gives 21112.
Next, we form a new number by replacing the digits larger than 1 with a 1, others with a 0.1
For the sum 21112, this gives 10001.
For each digit larger than 1, we have to subtract 2 from that digit and carry 110 to the next three higher positions. Since 1098 = 10 * 110 - 2, we can achieve this by multiplying the result from step 2 by 1098, then adding that product to the sum.2
For the sum 21112, this gives 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210.
We repeat steps 2 and 3 a total of d * 8 times, where d is the number of digits of a + b. 3
For the initial sum 21112, the results are
                      11002210
                      12210010
                    1220010010
                  122000010010
                12200000010010
              1220000000010010
            122000000000010010
          12200000000000010010
        1220000000000000010010
      122000000000000000010010
    12200000000000000000010010
  1220000000000000000000010010
122000000000000000000000010010
                             .
                             .
                             .

We take the final sum modulo 10d + 8, discarding all but the last d + 8 digits.
For the initial sum 21112, the final result is 10010.

1 This is achieved with translate. Repeating the string 0011 64 times makes one repetition line up with the sequence of ASCII characters 0123, achieving the desired replacement.
2 Note that the digits of this sum cannot exceed 3 (initial value 1 plus two 1's from carries).
3 This happens to work for d = 1, and d * 8 > d + 8 otherwise. The code may repeat the steps (d + 1) * 8 times, since s has a trailing L if s is a long integer.

This is deep magic. What format is input() expecting? (I get 21112 when I input 10101, 11011.)

Never mind; that was running a version translated (unsuccessfully, it seems) to Python 3. It works fine under Python 2.

...How. Please. Explain.

@QPaysTaxes I've edited my answer.

@Dennis Now could you explain why that works? For example, why d+8 and not, say, d+9? How????

@QPaysTaxes I took that from the paper I linked to. I haven't proved it myself.

@Dennis Oh, I see. I'm just reading through it now.

Pyth, 34 bytes
_shM.u,%J/eMeN\12-+PMeNm.B6/J2k,kQ

Try it online: Demonstration or Test Suite (takes quite a while). It should satisfy the time restriction though easily, since the online compiler is quite slow in comparison with the normal (offline) compiler.
Explanation:
My algorithm is basically an implementation of addition with carrying. But instead of carrying 1, I have to carry 110 (1100 in base -1+i is the same as 2 in base -1+i). This works mostly fine, but you can get stuck in an infinite loop printing zeros. For instance if you are adding 1 with 11 and currently have the carry 110. So I basically add until I get stuck in a loop and then stop. I think that a loop that a loop will always print zeros and therefore this should be fine.
_shM.u,%J/eMeN\12-+PMeNm.B6/J2k,kQ   implicit: Q = input list of strings
                               ,kQ   create the pair ["", Q]
    .u                               modify the pair N (^) until loop:
      ,                                replace N with a new pair containing:
            eN                           N[1] (the remaining summand)
          eM                             take the last digits of each summand
         /    \1                         count the ones
        J                                store the count in J
       %J       2                        J % 2 (this is the first element of the new pair)
                   PMeN                  remove the last digit of each summand
                  +    m   /J2           and add J / 2 new summand:
                        .B6                 with the value "110" (binary of 6)
                 -            k          remove empty summand
    .u                               returns all intermediate results
  hM                                 extract the digits
 s                                   sum them up to a long string
_                                    reverse

Jelly, 29 28 26 24 21 20 bytes
DBḅ1100ḌµDL+8µ¡Dṣ2ṪḌ

This does I/O in decimal. The integers have to be separated by the non-alphanumeric character +.
Try it online! or verify all test cases.
Background
In Arithmetic in Complex Bases, the author shows how to add and multiply complex numbers in bases of the form -n + i.
For base -1 + i, addition is done similarly to regular, binary addition with carry, with two differences:

Instead of carrying 1 to the next higher position, we carry 110 to the next three.
Carry digits can propagate indefinitely. However, without leading zeroes, the sum a + b has at most eight digits more than the maximum of a and b.

We proceed as follows.

First, we add a and b as if their digits were decimal digits.
For a = 10101 and b = 11011, this gives 21112.
For each digit larger than 1, we have to subtract 2 from that digit and carry 110 to the next three higher positions. We can achieve this by converting each decimal digit to binary, the resulting binary arrays from base 1100 to integer, and interpret the resulting list of 0's, 1's, 1100's and 1101's as a non-canonical base 10 number.1
For the sum 21112, this gives 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210.
We repeat steps 2 a total of d + 8 times, where d is the number of digits of a + b.
For the initial sum 21112, the results are
                      11002210
                      12210010
                    1220010010
                  122000010010
                12200000010010
              1220000000010010
            122000000000010010
          12200000000000010010
        1220000000000000010010
      122000000000000000010010
    12200000000000000000010010
  1220000000000000000000010010
122000000000000000000000010010

We discard all but the last d + 8 digits from the final result. This is achieved by discarding everything after the last 2.2
For the initial sum 21112, the final result is 10010.

How it works
DBḅ1100ḌµDL+8µ¡Dṣ2ṪḌ  Main link. Argument: a + b (implicit sum)

        µ    µ¡       Execute the chain before the first µ n times, where n is
                      the result of executing the chain before the second µ.
         D            Convert a + b to base 10.
          L           Length; count the decimal digits.
           +8         Add 8 to the number of digits.
D                     Convert the initial/previous sum to base 10.
 B                    Convert each digit (0 - 3) to binary.
  ḅ1100               Convert each binary array from base 1100 to integer.
       Ḍ              Interpret the resulting list as a base 10 number.
               D      Convert the final sum to base 10.
                ṣ2    Split at occurrences of 2.
                  Ṫ   Select the last chunk.
                   Ḍ  Convert from base 10 to integer.

1 Note that the digits of this sum cannot exceed 3 (initial value 1 plus two 1's from carries).
2 This works because the last digit that will cancel out cannot be a 3.

Python 2, 69 67 bytes
f=lambda a,b:a*a+b*b^58and 2*f(a*b%2*6,f(a/2,b/2))|a+b&1if a else b

I/O is done with base 2 integers.
-2 thanks @Dennis.

I take it a*a+b*b^58==0 when a and b are inverses? How does that work?

@xnor No, a*a+b*b==58 when one of them is 3 and the other is 7.

It's not obvious me to that (3,7) is the only pair that gives a cycle and needs special-casing. If it is true, then you only actually need to check (a,b)==(3,7) in that order, since (7,3) recurses to (3,7), and maybe there's a shorter expression for that.

Now this is guaranteed to confuse anyone who doesn't know (or forgets) that (a) ^ is XOR, not exponentiation, or (b) XOR has lower precedence than +.

Retina, 100 bytes
r+`(.*)(\d|(?!\4))( .*)(.?)
$2$4:$1$3
T` 0
+`1:11(1*:1*)11
:$1
^:*
:::
}`:(1*:1*:)11
1:1$1
(1)*:
$#1

This takes the input separated with a comma. The output always starts with three leading zeroes.
Try it online!
I really wonder if there's a shorter solution for the first stage...

No, no, the score is perfect as it is ;)

Nice score of -2i!

Wow. I did not see this solution when I posted mine... Much more superior than my solution.

@KennyLau I was just looking at it and thinking "hm, I guess I should've added an explanation at some point..."

...-2i? This is decimal but the program uses a base that not.

Python 3, 289 bytes
This performs digitwise addition from least to most significant digit (in other words, the exact same algorithm you were taught in primary school). The differences are that (a) it's in binary, not decimal, so you carry whenever a digit is 2 or more, and (b) 1 + 1 = 1100, not 10.
Actually, it's also necessary to note that 11 + 111 = 0, or else sums that should become zero will never terminate.
from collections import*
def a(*s,p=0):
 r=defaultdict(int,{0:0})
 for S in s:
  n=0
  for d in S[::-1]:r[n]+=d=='1';n+=1
 while p<=max(r):
  while r[p]>1:
   r[p]-=2
   if r[p+1]>1<=r[p+2]:r[p+1]-=2;r[p+2]-=1
   else:r[p+2]+=1;r[p+3]+=1
  p+=1
 return str([*map(r.get,sorted(r))])[-2::-3]

More golfing is surely possible.

How certain are you that your "zero detector" is sufficient?

@Yakk: On a scale of one to peer-reviewed-journal, maybe give it a no-counterexamples-yet?

JavaScript (ES6), 146 126 bytes
r=n=>n&&n%2-r(n>>=1)-i(n)
i=n=>n&&r(n>>=1)-i(n)
g=(x,y,b=(x^y)&1)=>x|y&&b+2*g(b-x+y>>1,b-x-y>>1)
(x,y)=>g(r(x)+r(y),i(x)+i(y))

g converts a Gaussian integer (real and imaginary parts) into base i-1, while r and i converts a base i-1 integer into a Gaussian integer (real and imaginary parts respectively). Once the conversions are in place, I just have to do the arithmetic.
Edit: Saved 20 bytes by calculating the real and imaginary parts separately.

C++ 416 bytes, plus #include <vector>\n#include <algorithm>\n (another 40)
using I=int;using v=std::vector<I>;void r(v&x){v r{rbegin(x),rend(x)};x=r;}v a(v L,v R){r(L);r(R);L.resize(std::max(L.size(),R.size()));for(int&r:R)L[&r-R.data()]+=r;while(1){L.resize(L.size()+3);auto it=find(rbegin(L),rend(L),2);if(it==rend(L))break;I i=-1+it.base()-begin(L);i&&L[i+1]&&L[i-1]/2?L[i+1]=L[i]=L[i-1]=0:(++L[i+2],++L[i+3],L[i]=0);}L.erase( std::find(rbegin(L),rend(L),1).base(),end(L));r(L);return L;}

or, with more whitespace:
using I=int;
using v=std::vector<I>;

void r(v&x){v r{rbegin(x),rend(x)};x=r;}
v a(v L,v R) {
  r(L);r(R);
  L.resize(std::max(L.size(),R.size()));
  for(int&r:R)
    L[&r-R.data()]+=r;
  while(1) {
    L.resize(L.size()+3);
    auto it=find(rbegin(L), rend(L), 2);
    if(it==rend(L)) break;
    I i=-1+it.base()-begin(L);
    i&&L[i+1]&&L[i-1]/2?
      L[i+1]=L[i]=L[i-1]=0
    :
      (++L[i+2],++L[i+3],L[i]=0);
  }
  L.erase( std::find(rbegin(L),rend(L),1).base(), end(L));
  r(L);
  return L;
}

Barely golfed.  It takes input as a vector of ints, and returns a vector of ints.
Live example.

Retina, 157 151 134 133 124 123 bytes
1 byte off thanks to Martin Büttner.
(.+),(.+)
$.1$*0$2,$.2$*0$1,
1
0x
+`(0x*)(,.*)0(x*),
$2,$1$3
{`,

(^|0x0xx0xx)
000
(0x*)(0x*)(0x*0)xx
$1x$2x$3
)`^0+
0
0x
1

Try it online!
Converts to unary, and then repeat the following replacements (shown here in decimal):
122 -> 000
0002 -> 1100 (this can also be 0012 -> 1110 and 1112 -> 2210 or even 2222 -> 3320 or even 3333 -> 4431)

Basically, when larger than two: take away two, add nothing in the previous digit, add one to the previous digit, then add one to the previous digit.
In pseudocode:
if(a[n]>2):
    a[n] -= 2;
    a[n-2] += 1;
    a[n-3] += 1;

Unary implementation:
Each digit (e.g. 3) is shown as the number of xs (e.g. xxx) and then prefixed with 0.
For example, 1234 would be expressed as 0x0xx0xxx0xxxx.
This leaves 0 unchanged, as 101 would be expressed by 0x00x.
Since initially and finally, there is only 0 and 1, the conversion could be easily done by 1->0x and 0x->1.
Click here to see every step.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Print arrays from the middle out
This is a code-golf question.
Given integers s and n the task is to output all arrays of length n which take values from -s to s.  The only twist is that you must output them in the following order.

The all zeros array of length n.
All arrays of length n with elements from -1 to 1 excluding any array you have outputted before.
All arrays of length n with elements from -2 to 2 excluding any array you have outputted before.
And so on until you get to all arrays of length n with elements from -s to s excluding any array you have outputted before.

You should output one array per line. They can be space or comma separated.
Here is some non-complying python code that outputs the arrays/lists/tuples in the right order.
import itertools

s =  3
n = 2

oldsofar = set()
newsofar = set()
for i in xrange(s):
    for k in itertools.product(range(-i,i+1), repeat = n):
        newsofar.add(k)
    print newsofar - oldsofar
    oldsofar = newsofar.copy()
    print "***"

Extra glory (and an upvote from me) for answers  that perform no set subtraction or equivalent.

Can we write a function that prints the result?

@LegionMammal978 I would prefer a complete program.  If this is deemed seriously controversial I will give in of course :)

Is there any required order within each of your bullet points?

@MartinBüttner No, not at all.

Jelly, 9 bytes
NRṗµAṀ€Ụị

No list subtraction was used in the making of this post. Try it online!
How it works
NRṗµAṀ€Ụị  Main link. Arguments: s, n

N          Negate; yield -s.
 R         Range; yield [-s, ..., s].
  ṗ        Cartesian power; push all vectors of length n of those elements.
   µ       Begin a new, monadic link. Argument: L (list of vectors)
    A      Compute the absolute values of all vector components.
     Ṁ€    Get the maximum component of each vector.
       Ụ   Sort the indices of A according to the maximal absolute value of the
           corresponding vector's components.
        ị  Retrieve the vectors of A at those indices.

Now it's just getting silly!

"No lists were harmed in the making of this post"

MATL, 18 bytes
_G2$:iZ^t!|X>4#SY)

First input is s, second is n
This works in current version (15.0.0) of the language.
Try it online!
Explanation
_      % take input s implicitly. Negate to obtain -s
G      % push input s again
2$:    % inclusive range from -s to s
i      % take input n
Z^     % Cartesian power. Gives 2D array, with each result on a row
t!     % duplicate and transpose
|      % absolute value
X>     % maximum of each column
4#S    % sort and push the indices of the sorting
Y)     % apply as row indices into the 2D array. Display implicitly

18 bytes is outrageous :)

Haskell, 61 60 bytes
n#s=[c|b<-[0..s],c<-mapM id$[-b..b]<$[1..n],any((b==).abs)c]

Usage example: 2#2-> [[0,0],[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1],[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,2],[0,-2],[0,2],[1,-2],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]].
How it works:
   b<-[0..s]                           -- loop b through 0 .. s
        c<-mapM id$[-b..b]<$[1..n]     -- loop c through all lists of length n
                                       -- made out of the numbers -b .. b
                                       -- ("[-b..b]<$[1..n]" is "replicate n [-b..b]";
                                       --  "mapM id" is "sequence")
[c|                 ,any((b==).abs)c]  -- keep c if it contains b or -b

Edit: @xnor pointed out that mapM id is sequence.

mapM id is shorter than sequence.

@xnor: True. Thanks!

Mathematica, 83 bytes
Print/@Select[Range[-#,b=#]~Tuples~a,Abs@#~MemberQ~b&]&/@Range[0,a=Input[];Input[]]

To use, put in a script and input n then s on separate lines. Prints each array as a curly-bracketed, comma-delimited list (e.g., {-1, 0, 1}). It works by taking every list of length n with numbers between [-cur..cur], and and printing those which include either -cur or cur. It then repeats this for all cur in [0..s]. (This post contains 19 ` characters!)

JavaScript (SpiderMonkey 30+), 134 bytes
(s,n)=>n?[for(a of f(s,n-1))for(i of Array(s*2+1).keys())[i-n,...a]].sort((a,b)=>g(a)-g(b),g=a=>Math.max(...a,-Math.min(...a))):[[]]

Uses the cartesian-power-and-sort approach, which I thought of separately, but I was recompiling SpiderMonkey at the time so I unable to answer this before @Dennis.


text:
Graph an equation!
Please note that this question is different from this question. This one asks for graphical output, while the other one asks for ascii art.
Objective
Help! Timmy's graphing calculator broke! His calculator cannot graph anymore. However, he has found a way to add new programs and functions to his calculator. Your job is to write a program/function that graphs equations.
Rules

Your program/function should take in a string in the form of "y = random equation involving x" and graph it on the coordinate grid.
Timmy's calculator doesn't have that much memory, so please try to make your code as short as possible.
The operations needed are addition (+), subtraction (-), multiplication (*), division (/), exponentiation(^) and grouping(())
Your program/function should be able to graph from x=-5 to x=5, and from y=-5 to y=5.
Color, axis labels, the grid, numbers, scale, and animation are optional.
The minimum size of the image should be 50x50 pixels.

Test Cases
Input
y = x ^ 2
Output

Input
y = 4 * x + 3
Output

Standard loopholes apply.
You may change the operators, but it adds +10% to your byte count.

What is the minimum size of the image to be output?

50x50 pixels minimum.

do you need anti-aliasing?

can we also represent operators as other characters (exponential as **)?

anti-aliasing is optional

Please try to stick to the operators listed above. If you want to change the operators, it is a +10% byte count.

Can it take only the x^2 part or do we need y = ..?

Desmos, 0 bytes? It has been defined as a programming language.

What does this mean: "Your program/function should be able to graph from x=-5 to x=5, and from y=-5 to y=5"? What should the boundaries be if y = 0.01*x? And what about y = 1000*x? Snould all boundaries be [-5, 5][-5, 5] regardless of what the function is?

What is the minimum step size for x?

I think you should ban plotting builtins. Those will lead to answers with just one function call.

@DenkerAffe, In many languages it's impossible to plot without plotting builtins...

@ANerd-I This is what I thought when I saw the question >_>

Boundaries should be [-5, 5][-5, 5] at all times. The maximum step size for x is 0.1. Plotting built-ins are allowed because many languages can't plot without them.

What should be done when y results in a complex number?

You can use a 3d plot, not plot the point at all, or just use undefined behavior.

Matlab, 35 bytes
ezplot(input(''));axis([-5 5 -5 5])

Input is a string like 'y=2*x^2'.

Maybe you should clarify that the string needs to include the quotation marks

Mathematica, 89 77 bytes
Plot[ToExpression[#~StringDrop~4],{x,-5,5},PlotRange->{-5,5},AspectRatio->1]&

Most of it is just formatting to make it look similar to the examples. Please inform me if something isn't required. Includes axis markers, which aren't explicitly disallowed.

The question says you do not need the axis markers. But if it reduces the byte count you can probably use them.

MATL, 40 * 1.1 = 44
K0h)5:p'(-5:.1:5)'XHYXUHUw2$XG-5,5hth1ZG

This works in current version (15.0.0) of the language. EDIT (June 15, 2017): You can try it at MATL Online!
.*, ./ and .^ are for multiplication, division and power (that is, add a dot in front).
The following shows an example result running on Matlab.

RPL/2 15*1.1 = 16.5
STEQ .5 *S DRAW

Timmy must key in the equation in capitals, e.g.'Y = X ^ 3', hence the 10% penalty.
The .5 is just luck: the default box is -10…10 × -10…10 with RPL/2.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Generate m-sequences
Introduction
Maximum-length sequences, usually known as m-sequences, are binary sequences with some interesting properties (pseudo-noise appeareance, optimal periodic autocorrelation) which make them suitable for many applications in telecommunications, such as spread-spectrum transmission, measurement of impulse responses of propagation channels, and error-control coding. As a specific example, they are the basis for the synchronization signals used in the (4G) LTE mobile communication system.
These sequences are best understood as generated by means of an L-stage binary shift register with linear feedback. Consider the following figure (from the linked Wikipedia article), which shows an example for L=4.

The state of the shift register is given by the content (0 or 1) of each stage. This can also be interpreted as the binary expansion of a number, with the most significant bit at left. The shift register is initiallized with a certain state, which we will assume to be [0 ... 0 1]. At each discrete-time instant, the contents are shifted to the right. The value of the rightmost stage is the output, and gets removed from the register. The successive values of the rightmost state constitute the output sequence. The leftmost part is filled with the result of the feedback, which is a modulo-2 (XOR) combination of certain stages of the register (in the figure they are the two rightmost stages). The stages that are actually connected to the modulo-2 adder will be referred to as the feedback configuration.
A sequence produced by a shift register is always periodic. Depending on the feedback configuration, different sequences result. For certain configurations the period of the resulting sequence is the maximum possible, that is, an m-sequence results. This maximum is 2L-1: the register has 2L states, but the all-zero state can't be part of the cycle because it is an absorbing state (once it is reached it is never abandoned).
A shift-register sequence is defined by the number of stages L and the feedback configuration. Only certain feedback configurations give rise to m-sequences. The example above is one of them, and the sequence is [1 0 0 0 1 0 0 1 1 0 1 0 1 1 1], with period 15.
It can be assumed that the last stage is always part of the feedback, otherwise that stage (and possibly some of the preceding) would be useless.
There are several ways to describe the feedback configuration:

As a binary array of size L: [0 0 1 1] in the example. As indicated, the last entry last will always be 1.
As a number with that binary expansion. But since it would not be possible to distinguish for example [0 1 1] and [0 0 1 1], a dummy leading 1 is added. In the example, the number defining the feedback configuration would be 19.
As a polynomial (over the field GF(2)). Again, a leading 1 coefficient needs to be introduced. In the example, the polynomial would be x4+x+1. The exponents increase to the left.

The description in terms of polynomials is interesting because of the following characterization: the sequence generated from the shift register will be an m-sequence if and only if the polynomial is primitive.
TL;DR / The challenge
Given a feedback configuration with L>0 stages, generate one cycle of the resulting sequence, starting from the 0···01 state as described above. The feedback configuration will always correspond to an m-sequence, so the period will always be 2L-1.
Input can be given by any means, as long as it is not pre-processed:

Binary array. In this case L is not explicitly given, because it is the length of the vector.
You can choose to include a dummy leading 1 in the above array (and then L is the length minus 1).
Number with dummy leading 1 digit in its binary expansion.
Number without that dummy 1 and a separate input explicitly giving L.
Strings representing any of the above.

...or any other reasonable format.
The input format used must be the same for all possible inputs. Please indicate which one you choose.
For reference, A058947 gives all possible inputs that give rise to m-sequences, in format 2 (that is, all primitive polynomials over GF(2)).
The output will contain 2L-1 values. It can be an array of zeros and ones, a binary string, or any other format that is easily readable. The format must be the same for all inputs. Separating spaces or newlines are accepted.
Code golf. Fewest best.
Test cases
Input in format 2, input in format 3, output as a string:
[1 1]
3
1

[1 0 0 1 1]
19
100010011010111

[1 0 1 0 0 1]
41
1000010101110110001111100110100

[1 0 0 0 0 1 1]
67
100000100001100010100111101000111001001011011101100110101011111

If input is in format 2, are the first and last bits always set, and is there at most one other bit set?

@Neil First: yes. Last: I hadn't thought of that, but also yes, otherwise the last stages would be useless. I've edited that into the challenge. Thanks!

can we shift to the left and therefore take the feedback configuration in reverse order, e.g. you second test case as [1,1,0,0,1]?

@nimi Yes, if you indicate that in your input format specification

Thanks, but I'm still unclear as to how many stages might be connected to the adder.

@Neil The connected stages are the last and optionally others, possibly all. In format 2 there's a dummy leading 1. So 31 would indicate there are 4 stages and all of them are connected (that configuration doesn't generate an m-sequence, though, so it's not a valid input)

@Neil These are all possible inputs in format 2 https://oeis.org/A058947

Would input format 4 with reversed digit order (1, 12, 18 and 48 for the test cases) be an acceptable input format?

@Dennis Sure it is!

Jelly, 18 bytes
æḟ2µ&³B^/+ḤµḤ¡BḣḤṖ

This takes a single integer, encoding a0 in its MSB and aL-1 in its LSB.
The test cases become 1, 12, 18 and 48 in this format. Try it online!
How it works
æḟ2µ&³B^/+ḤµḤ¡BḣḤṖ  Main link. Argument: n (binary-encoded taps)

æḟ2                 Round n down to k = 2 ** (L - 1), the nearest power of 2.
   µ                Begin a new, monadic link. Argument: r = k
    &³              Bitwise AND r with n.
      B             Convert to binary.
       ^/           Bitwise XOR all binary digits.
          Ḥ         Unhalve; yield 2r.
         +          Add the results to left and right.
           µ        Convert the previous chain into a single link.
            Ḥ       Unhalve; yield 2k = 2 ** L.
             ¡      Execute the link 2k times, updating r in each iteration.
              B     Convert the final value of r to binary.
               ḣḤ   Keep only the first 2k binary digits.
                 Ṗ  Pop; discard the last digit.

Haskell, 88 82 bytes
r@(h:t)%m=h:(t++[mod(sum[v|(v,1)<-zip r m])2])%m
l#x=take(2^l-1)$(1:(0<$[2..l]))%x

I'm using input method 1 (but in reverse order, because I'm shifting to the left) together with L as an explicit parameter.
Usage example (test case #2): 4 # [1,1,0,0] -> [1,0,0,0,1,0,0,1,1,0,1,0,1,1,1].
How it works: % does the work. First parameter is the content of the shift register, second parameter is the feedback configuration. # starts the whole process by building the initial register content, calling % and taking the first 2^L-1 elements.
main function #:

                1:0<$[2..l]      -- initial register content: one 1 followed
                                 -- by L-1 0s
                            %x   -- call the helper function with the
                                 -- feedback configuration
take(2^l-1)                      -- and take the first 2^L-1 elements

helper function % (bind r to the whole register set, h to the first register a0
and t to register a1..aL. Bind m to the feedback config):

h:                               -- next element is h, followed by
                         %m      -- a recursive call of %, where the new register is
   t++                           -- t followed by
           [v|(v,1)<-zip r m]    -- the elements of l, where the corresponding
                                 -- elements of m are "1"
      mod(sum ...          )2    -- xored

Pyth, 19 bytes
eM.u+xF*VQNPN+m0tQ1

Try it online: Demonstration or Test Suite
Explanation:
eM.u+xF*VQNPN+m0tQ1   implicit: Q = input list in format 1
              m0tQ    create a list with len(Q)-1 zeros
             +    1   and append a one at the end
                      this is the starting sequence
  .u                  apply the following statement repeatedly to the starting seq. N:
       *VQN              vectorized multiplication of Q and N
     xF                  xor all this values
    +      PN            remove the last value of N and prepend the new calculated one
                      .u stops, when it detects a cycle and returns a list of
                      all intermediate states of N
eM                    take the last element of each state and print this list

I've edited the challenge (following Neil's comment): the input list will always end in 1. Just in case it helps

MATL, 26 bytes
g`tGZ&Bs2\2GBnq^*+H#2\tq]x

This works in current version (15.0.0) of the language.
Input is a number describing the feedback configuration, using format 3 as described in the challenge. Output is separated by newlines.
Try it online!
Explanation
This uses numbers to represent the register contents, and a bitwise XOR operation to compute the feedback bit.
At each iteration the fed-back bit is introduced at an "extra stage" at the left of the leftmost stage. A divmod operation by 2 then gives the new contents (division quotient) and the output (division remainder). The stack holds the already produced output and the current state on top.
Instead of looping a fixed number (2L-1) of times, a "do...while" loop is used, which in this case requires fewer bytes. The loop exits when the 1 state is reached again.
g         % take input. Convert to logical: gives 1, because input is nonzero.
          % This is the initial state. The input has been copied into clipboard G
`         % do...while
  t       %   duplicate
  G       %   push input
  Z&      %   bitwise XOR
  Bs2\    %   convert to binary, sum, compute parity. The result is the feedback bit
  2GBnq^  %   compute next power of two that exceeds the register size. This is used
          %   for introducing the fed-back bit in a leftmost stage "outside" the
          %   register, which will be immediately shifted right
  *+      %   multiply by feedback bit and add to register state
  H#2\    %   divmod by 2. Gives output bit and new state on top
  tq      %   duplicate and subtract 1. This is falsey if state is 1 (loop will be
          %   exited in that case)
]         % end do...while. Exit if top of stack is falsey
x         % delete current state. Implicitly display sequence

Does MATL compile to Matlab?

@tac Yes, to Matlab or Octave. In the answer you have the link to the compiler and documentation

JavaScript (ES6), 100 bytes
(l,f)=>[...Array((1<<l)-1)].map((_,i)=>(v=i?(x=v&f,[1,2,4,8,16].map(n=>x^=x>>n),x&1)<<l-1|v>>1:1)&1)

Takes type 4 input (length and feedback without the leading 1; well, the 1 is optional.) Returns an array of 0s and 1s. The parity calculation is annoying; I wanted to use reduce but that turns out to be 2 bytes longer, because the precedence of << is wrong for my use case.

Kotlin, 93 bytes
(91 + len(str(Number)))
Input Number is hardcoded in the source, without leading 1 and in reverse bit order (like @Dennis' answer). Input L is not needed!
The test cases become 1, 12, 18, 48.
fun main(a:Array<String>){var v=1
do{print(v and 1)
v=(v shr 1)xor 48*(v and 1)
}while(v!=1)}

Try it online!
Result appears rotated left by L bits:
100001100010100111101000111001001011011101100110101011111100000

Compare with original:
      100001100010100111101000111001001011011101100110101011111100000
100000100001100010100111101000111001001011011101100110101011111

      1010111011000111110011010010000
 1000010101110110001111100110100

      100110101111000
  100010011010111

Hardcoding in the source code doesn't seem to be one of the accepted input methods. Also, the cyclic shift in the output amounts to starting the sequence in a different state, which is not allowed by the challenge


text:
How far from the exterior?
Take a 2D region of space divided into axis aligned unit square elements with their centers aligned at integer intervals. An edge is said to be internal if it is shared by two elements, otherwise it is an external edge.
Your goal is to find the minimum number of neighboring elements which must be traversed to reach an exterior edge starting from the center of each element, known as the traversal distance, or distance for short. You may only traverse through an edge (i.e. no corner cutting/diagonal movement). Note that "exterior elements" (elements which have at least one external edge) are considered to need to traverse 0 neighboring elements to reach an exterior edge..
Input
The input is a list of non-negative integer pair coordinates denoting the (x,y) of the center of all elements. It is assumed there are no overlapping elements (i.e. an x/y pair uniquely identifies an element).
You may not assume anything about the element input order.
You are welcome to transform the origin of the input to any location (e.g. 0,0 or 1,1, etc.).
You may assume that all input elements are connected, or in other words it is possible to travel from any one element to any other element using the rules above. Note that this does not mean that the 2D region is simply connected; it may have holes inside of it.
Example: the following is an invalid input.
0,0
2,0

error checking is not required.
The input may be from any source (file, stdio, function parameter, etc.)
Output
The output should be a list of coordinates identifying each element, and the corresponding integer distance traversed to get to an edge. The output may be in any element order desired (e.g. you need not output elements in the same order received as inputs).
The output may be to any source (file, stdio, function return value, etc.)
Any output which matches the coordinate of the element with it's exterior distance is fine, e.g. all of these are fine:
x,y: distance
...

[((x,y), distance), ...]

[(x,y,distance), ...]

Examples
Text example inputs are in the form x,y, with one element per line; you are welcome to reshape this into a convenient input format (see input format rules).
Text example outputs are in the format x,y: distance, with one element per line; again, you are welcome to reshape this into a convenient ouput format (see output format rules).
Graphical figures have the lower-left bound as (0,0), and the numbers inside represent the expected minimum distance traveled to reach an exterior edge. Note that these figures are purely for demonstration purposes only; your program does not need to output these.
Example 1
input:
1,0
3,0
0,1
1,2
1,1
2,1
4,3
3,1
2,2
2,3
3,2
3,3

Output:
1,0: 0
3,0: 0
0,1: 0
1,2: 0
1,1: 1
2,1: 0
4,3: 0
3,1: 0
2,2: 1
2,3: 0
3,2: 0
3,3: 0

graphical representation:

Example 2
input:
4,0
1,1
3,1
4,1
5,1
6,1
0,2
1,2
2,2
3,2
4,2
5,2
6,2
7,2
1,3
2,3
3,3
4,3
5,3
6,3
7,3
8,3
2,4
3,4
4,4
5,4
6,4
3,5
4,5
5,5

output:
4,0: 0
1,1: 0
3,1: 0
4,1: 1
5,1: 0
6,1: 0
0,2: 0
1,2: 1
2,2: 0
3,2: 1
4,2: 2
5,2: 1
6,2: 1
7,2: 0
1,3: 0
2,3: 1
3,3: 2
4,3: 2
5,3: 2
6,3: 1
7,3: 0
8,3: 0
2,4: 0
3,4: 1
4,4: 1
5,4: 1
6,4: 0
3,5: 0
4,5: 0
5,5: 0

graphical representation:

Example 3
input:
4,0
4,1
1,2
3,2
4,2
5,2
6,2
8,2
0,3
1,3
2,3
3,3
4,3
5,3
6,3
7,3
8,3
9,3
1,4
2,4
3,4
4,4
5,4
6,4
7,4
8,4
9,4
2,5
3,5
4,5
5,5
6,5
9,5
10,5
11,5
3,6
4,6
5,6
9,6
10,6
11,6
6,7
7,7
8,7
9,7
10,7
11,7

output:
4,0: 0
4,1: 0
1,2: 0
3,2: 0
4,2: 1
5,2: 0
6,2: 0
8,2: 0
0,3: 0
1,3: 1
2,3: 0
3,3: 1
4,3: 2
5,3: 1
6,3: 1
7,3: 0
8,3: 1
9,3: 0
1,4: 0
2,4: 1
3,4: 2
4,4: 2
5,4: 2
6,4: 1
7,4: 0
8,4: 0
9,4: 0
2,5: 0
3,5: 1
4,5: 1
5,5: 1
6,5: 0
9,5: 0
10,5: 0
11,5: 0
3,6: 0
4,6: 0
5,6: 0
9,6: 0
10,6: 1
11,6: 0
6,7: 0
7,7: 0
8,7: 0
9,7: 0
10,7: 0
11,7: 0

graphical representation:

Scoring
This is code golf. Shortest code in bytes wins. Standard loopholes apply. Any built-ins other than those specifically designed to solve this problem are allowed.

Can we output as [((1,0),0),...]?

@lirtosiast yes

In your examples, you don't explicitly state the inputs.

@DaleJohnson just take the first two columns of each text input for the x,y pairs. I didn't add a separate quote box for just the inputs since it seemed to be getting a bit long. Is there a way to add a quote box and manually limit it's vertical height?

find the minimum number of neighboring elements which must be traversed to reach an exterior edge Starting from where? And can you add the output in the test caes?

@DonMuesli updated. You should start from each element and find it's minimum travel length to an exterior edge.

@DonMuesli what do you mean by that?

Add 1 to all input numbers. The origin would be (1,1), not (0,0). In many languages that's more natural. Can we choose that format?

@DonMuesli ahh, originally I had intended on having the coordinates be signed integers, but looking at the creative solutions I've changed my mind. Yes, you are welcome to transform the origin to any arbitrary starting location.

@helloworld922 Thanks! That saves a few bytes

MATLAB/Octave, 143 bytes
function [v,x,y]=d(x,y)R=S=zeros(max(y+3),max(x+3));i=sub2ind(size(S),y+2,x+2);S(i)=1;while nnz(S=imerode(S,strel('disk',1,0)))R+=S;end;v=R(i);

Ungolfed
function [v,x,y]=d(x,y)
  R=S=zeros(max(y+3),max(x+3));
  i=sub2ind(size(S),y+2,x+2);
  S(i)=1;
  while nnz(S=imerode(S,strel('disk',1,0)))
    R+=S;
  end;
  v=R(i);

Explanation
Create Source and Result matrices of appropriate size, filled with zeros.
R=S=zeros(max(y+3),max(x+3));

Calculate the linear indices that correspond to the xy-pairs, with one element padding at the borders.
i=sub2ind(size(S),y+2,x+2);

Draw the structure.
S(i)=1;

S is shown here for Example 2:
0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   1   0   0   0   0   0
0   0   1   0   1   1   1   1   0   0   0
0   1   1   1   1   1   1   1   1   0   0
0   0   1   1   1   1   1   1   1   1   0
0   0   0   1   1   1   1   1   0   0   0
0   0   0   0   1   1   1   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0

Remove all border elements by image erosion
S=imerode(S,strel('disk',1,0))

using the structuring element disk with radius 1:
0   1   0
1   1   1
0   1   0

If diagonal movement was allowed, we would instead use the rectangle:
1   1   1
1   1   1
1   1   1

Then, increment the result for all non-border elements
R+=S;

and loop until the image is completely eroded.
while nnz(S)

Return the result for each xy-pair.
v=R(i);

MATL, 38 37 36 33 bytes
1Z?t"tX@<~5Bt!Z~2X53$Y+4=+]3#fqhh

This uses current version (15.0.0) of the language/compiler.
Input format is: one array with x values and one array with y values. Input and output are 1-based. So the test cases have the following inputs:
[2 4 1 2 2 3 5 4 3 3 4 4]
[1 1 2 3 2 2 4 2 3 4 3 4]

[5 2 4 5 6 7 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 3 4 5 6 7 4 5 6]
[1 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 6 6 6]

[5 5 2 4 5 6 7 9 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 3 4 5 6 7 10 11 12 4 5 6 10 11 12 7 8 9 10 11 12]
[1 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8 8]

Try it online!
Explanation
A matrix is initially built with 1 at the input positions and 0 otherwise. Then a convolution is applied with a "North, East, South, West" mask ([0 1 0; 1 0 1; 0 1 0]), and the result at each position is compared with 4. A result of 4 means that that position is surrounded by other points, and so has distance-to-exterior at least 1. The result (0 or 1 for each point) is added to the original matrix. Those positions now contain 2 (at the end of the process the matrix will be decremented by 1).
The convolution process is iterated. For the next iteration, the input of the convolution is the accumulated matrix thresholded with 2; that is, values lower than 2 are set to 0. The result of the convolution indicates which points have distance at least 2 (all their neighbours have distance 1).
The number of iterations is chosen, for convenience, as the number of columns of the input matrix. This is sufficient (in fact, the maximum required number of iterations is half the minimum matrix dimension). The last iterations may be useless, but do no harm (they do simply add 0 to all points).
At the end of the process, 1 is subtracted from the result, because positions with value k have distance k-1 to the exterior. The coordinates and values of all positions is extracted and displayed.
           % take x and y implicitly
1          % push 1
Z?         % build sparse matrix from that x, y indices with 1 as value
t          % duplicate
"          % for each column of that matrix
  t        %   duplicate
  X@       %   push iteration index
  <~       %   true for matrix entries that are >= iteration index
  5B       %   5 in binary: row vector [1 0 1]
  t!       %   duplicate and transpose into a column vector
  Z~       %   element-wise XOR with broadcast: gives desired mask,
           %   [0 1 0; 1 0 1; 0 1 0]
  2X53$Y+  %   2D convolution. Output has same size as input
  4=       %   compare with 4: are all neighbouring positions occupied?
  +        %   add to accumulated matrix from previous iteration
]          % end for each
3#f        % extract row index, column index and value for nonzero
           % entries. In this case all entries are nonzero
q          % subtract 1 to value to yield distance to exterior
hh         % concatenate vertically twice
           % display implicitly

Pyth, 26 bytes
V]MQNf>*4Nl=Nsmfq1.a,dYQN0

Example 2
The output format I used is:
[[4, 3]]
2

That is, a list containing the point, followed by the distance from the exterior.
The code works by using a currently reached set, for each point filtering the input for all points exactly distance 1 away from that point, and checking whether the resultant number of points is 4 times as many as the starting number, and repeating until it's not. When started at a given point, this gives how far that point is from the exterior.

Python 3, 180 166 160 bytes
def f(l,d=0):
 l=set(l);
 if l:i={(a,b)for a,b in l if all([x in l for x in[(a+1,b),(a-1,b),(a,b+1),(a,b-1)]])};return{(c,d)for c in l-i}|f(i,d+1)
 return set()

We know that if a coordinate has less than four neighbours, it must be on the "exterior". Therefore, we can repeatedly strip the exterior cells and assign to them a distance equal the the number of iterations/depth of recursion in this case.
Definitely think there's room for improvement - What's the best way of checking of adjacent neighbours?
edit: I should be allowed to accept a list of pairs as tuples.

PHP, 316 Bytes
<?preg_match_all("#^(\d+),(\d+)#m",$_GET[i],$t);foreach($t[1]as$k=>$v)$a[$v][$t[2][$k]]=0;function w($x,$y){global$a;return isset($a[$x][$y])?$a[$x][$y]:-1;};for(;$z++<max($t[2]);$o=$s,$s="")foreach($a as$x=>$b)foreach($b as$y=>$c)$s.="\n$x,$y: ".$a[$x][$y]=1+min(w($x+1,$y),w($x-1,$y),w($x,$y-1),w($x,$y+1));echo$o;

Online Version
Breakdown
preg_match_all("#^(\d+),(\d+)#m",$_GET[i],$t);
foreach($t[1]as$k=>$v)
$a[$v][$t[2][$k]]=0;  # make a 2 D array
function w($x,$y){global$a;return isset($a[$x][$y])?$a[$x][$y]:-1;};# check the neighbours
for(;$z++<max($t[2]);$o=$s,$s="") # stored the last loop string first run make possible to 1 and so on
foreach($a as$x=>$b) # x values
foreach($b as$y=>$c) # y values
$s.="\n$x,$y: ".$a[$x][$y]=1+min(w($x+1,$y),w($x-1,$y),w($x,$y-1),w($x,$y+1)); # concanate array item x+y+value
echo$o; #Output

Visualize as Ascii chars
ksort($a);
foreach($a as$x=>$b){
for($y=0;$y<=max($t[2]);$y++)
echo isset($a[$x][$y])?$a[$x][$y]:" ";
#The better way would be make a SVG and use the text element and use a factor
#echo '<text x="'.($x*$factor).'" y="'.($y*$factor).'">'.$a[$x][$y].'</text>';
echo"\n";}


text:
Use all your language's keywords, ideally minimally

Your program must contain all your language's keywords. Ideally, you should have each one exactly once (see Scoring). Of course, this means your language must actually have keywords, so esoteric languages are probably excluded, but just in case...
Any language used must have a dedicated Wikipedia article created more than one month ago.
The keywords in your program must be lexed as keywords and parsed as keyword statements or expressions (i.e. no containing them within strings or comments).

A "keyword" is defined according to the language's specification or documentation if it has no specification, and must additionally have a defined purpose within the language (Java programmers need not include goto and const). Your language might distinguish "keywords" from "reserved identifiers" or something similar; only those lexemes designated as keywords are required.
Scoring
So as not to punish languages with more keywords, your score is
l - k + 3r
Where l is the length of your program in bytes, k is the combined length of all the keywords you used, and r is the combined length of any keywords that occurred more than once. So if your language has only one keyword, for, and your solution is for for for, your score is 11 - 9 + 3(6) = 20.

This is trivial. If a program is just each keyword one time and exactly nothing else, that is a trival score of 0. It's also overly broad, since it doesn't specify what the program must do.

@MyHamDJ This is non-trivial, since few languages can simply paste all the keywords in order and have the program compile.

I believe the standard is "wikipedia, rosetta code, and/or esolang", why just wikipedia specificially?

@SuperJedi224 I dislike the use of esoteric languages on this site.

@EMBLEM But they are allowed, and disallowing them is frowned upon.

Python 3.4, 110
from os import*
def k(z):
 def c():return None;nonlocal z
class F:pass
global b
with open(devnull)as b:
 while b:
  if 1and 0is 0:continue
  elif 1:0
  else:
   for d in[]:yield not d;del d;break
 try:raise 1or False
 except:assert True
 finally:(lambda j:0)

Uses every keyword once. Note, in Python 3, exec and print are functions, not keywords.

Also, so as to not confuse people from the future, you might want to specify a particular Python 3 version just in case since async and await are slated to become keywords in 3.7

Brainfuck, 0
+-[]><,.

Score:
l = 8
k = 8
r = 0

l - k + 3r = 0

This program takes an input from the user and then prints it.

This language does not have keywords and is ineligible.

Depends what you mean by keyword.

@wizzwizz4 I clearly stated that keywords were defined according to the language specification. The word "keyword" appears nowhere on the Wikipedia or Esolangs page.

@EMBLEM The word "keyword" appears nowhere on most Esolangs pages.

@wizzwizz4 That's the idea.

@EMBLEM But what about the esolangs that have keywords, but don't call their keywords keywords, like Pig?

@wizzwizz4 The Esolangs.org page on Pig calls PIG a keyword.

@EMBLEM Sorry, autocorrect. I meant Doorspace.

Let us continue this discussion in chat.


text:
Length-encode a string
Suppose we use the following rules to pull a single string from another string, one containing only ASCII printable characters and called an *-string. If the string runs out before the process halts, that is an error, and the result of the process is undefined in that case:

Start with d=1, s=""
Whenever you encounter a *, multiply d by 2. Whenever you encounter another character, concatenate it to the end of s and subtract 1 from d. If now d=0, halt and return s

Defined Examples:
d->d
769->7
abcd56->a
*abcd56->ab
**abcd56->abcd
*7*690->769
***abcdefghij->abcdefgh

Undefined Examples: (note that the empty string would be one of these as well)
*7
**769
*7*
*a*b
*

Your job is to take a string and return the shortest *-string that produces that string.
Program Examples:
7->7
a->a
ab->*ab
abcd->**abcd
769->*7*69

Your program should handle any string containing at least one character and only non-* ASCII printable characters. You can never return strings for which the process is undefined, since by definition they cannot produce ANY strings.
Standard loopholes and I/O rules apply.

Can we assume the input doesn't contain *?

@DonMuesli "only non-* ASCII printable characters"

Pyth (36 27 bytes)
Thanks to Jakube for a 9 byte improvement!
Currently not as good as muddyfish's answer, but whatever
KlzJ1VzWgKyJp\*=yJ)pN=tK=tJ

Test Suite
Translation to python:
                            | z=input() #occurs by default
Klz                         | K=len(z)
   J1                       | J=1
     Vz                     | for N in z:
       WgKyJ                |   while K >= J*2:
            p\*             |     print("*", end="")
               =yJ          |     J=J*2
                  )         |     #end inside while
                   pN       |   print(N, end="")
                     =tK    |   K=K-1
                        =tJ |   J=J-1

Muddyfish's seems to have died...

JavaScript (ES6), 61 bytes
f=(s,d=2)=>s?d>s.length?s[0]+f(s.slice(1),d-2):'*'+f(s,d*2):s

Recursive function that does the following:

If d is less than or equal to remaining string length divided by 2:
Append * to output and multiply d by 2
Else:
Shift the string and append to output, subtract 1 from d.

See it in action:

f=(s,d=2)=>s?d>s.length?s[0]+f(s.slice(1),d-2):'*'+f(s,d*2):s

input.oninput = e => output.innerHTML = f(input.value);
<input id="input" type="text"/>

Save 2 bytes by working with double the value of d plus a futher byte by reversing the condition: f=(s,d=2)=>s?d>s.length?s[0]+f(s.slice(1),d-2):'*'+f(s,d*2):s

Pyth, 29 27 (Noticed broken) 27 26 25 bytes
+*\*sKllzXJ-^2.EKlzz?J\*k

Explanation to come.
Test Suite

C, 125 bytes
main(int q,char**v){++v;int i=1,n=strlen(*v);while(n>(i*=2))putchar(42);for(i-=n;**v;--i,++*v)!i&&putchar(42),putchar(**v);}

This takes advantage of the very regular pattern of star positions to output the correct encoding. Initially I tried a bruteforce recursive solution, but in retrospect it should have been obvious that there was a simpler mathematical solution.
Essentially you will always have 2^floor(log_2(length)) stars at the start of your output, and a final star after 2^ceil(log_2(length)) - length characters (if that works out to at least 1 character).
The (slightly) ungolfed version is as follows
main(int q,char**v){
   ++v;                         // refer to the first command line argument
   int i=1, n=strlen(*v);       // set up iteration variables

   while(n > (i*=2))            // print the first floor(log2(n)) '*'s
      putchar(42);

   for(i-=n;  **v;  --i, ++*v)  // print the string, and the final '*'
      !i&&putchar(42),putchar(**v);
}

JavaScript (ES6), 88 77 bytes
f=(s,l=s.length,p=2)=>l<2?s:p<l?"*"+f(s,l,p*2):s.slice(0,p-=l)+"*"+s.slice(p)

At first I thought that abcde had to be *a**bcde but it turns out that **abc*de works just as well. This means that the output is readily constructed using floor(log₂(s.length)) leading stars, plus an additional star for strings whose length is not a power of two.
Edit: Saved 8 bytes by calculating the number of leading stars recursively. Saved a further 3 bytes by special-casing strings of length 1, so that I can treat strings whose length is a power of 2 as having an extra leading star.

Haskell, 68 bytes
f d[]=""
f d xs|length xs>=d*2='*':f(d*2)xs
f d(x:xs)=x:f(d-1)xs

Same as the other answers, really. If EOF, output an empty string. If length remaining is more than twice d, output a star and double d. Otherwise, output the next character and subtract one from d.
Ungolfed:
f d (  [])                    = ""
f d (  xs) | length xs >= d*2 = '*' : f (d*2) xs
f d (x:xs)                    =  x  : f (d-1) xs

Ruby, 58 bytes
F=->a,s="",d=1{x,*y=a
d<1?s:x==?*?F[y,s,d*2]:F[y,s+x,d-1]}

Attempt This Online!


text:
Sort a nested list
You must write a program or function that sorts a nested list. Here are the rules for sorting a nested list:
Let's take this list as an example:
((5, 2), 2, 7, (2, 1, (3, 4)), 9)

Each element in this list has a "priority". An element counts as a number or a sublist. First, get the priority of each element at the same depth. If an element is just a number, its priority is the same as the number itself. If an element is a sublist, its priority is the sum of all the numbers in it, not including any sub-sublists.
So, the priorities of all the elements of depth 1 are:
 (  7 )  2  7  (    3       )  9
((5, 2), 2, 7, (2, 1, (3, 4)), 9)

Sort each element by priority. If there is a tie, you must keep the same order as the original list.
 2  (     3      )  (  7 )  7  9
(2, (2, 1, (3, 4)), (5, 2), 7, 9)

Repeat for every sublist. So on this sublist
(2, 1, (3, 4))

Our priorities look like:
 2  1  (  7  )
(2, 1, (3, 4))

So sorted, it looks like:
(1, 2, (3, 4))

(3, 4) is already sorted, so we're done. Repeat for (5, 2) which results in (2, 5) and we're done! Our final list is:
(2, (1, 2, (3, 4)), (2, 5), 7, 9)

Rules:

Highly doubtful, but just in case Mathematica has something for this, no nested list sorting builtins are allowed. Regular sorting functions are allowed.
I/O can be in any reasonable format.
Every sublist will contain at least one number or list. Also, sublists can be nested several levels deep. For example, in (1, 2, (((3)))) the (((3))) has a priority of 0, since it has only sublists in it.
Invalid lists (unmatched parentheses, non-numbers, wrong bracket types, negative numbers, etc.) result in undefined behavior.

Test I/O:
(1, 2, 3) ---> (1, 2, 3)

(1, 2, 6, 3, 9, 8) ---> (1, 2, 3, 6, 8, 9)

(4, 3, (2), (1)) ---> ((1), (2), 3, 4)

(4, 3, (2), ((1))) ---> (((1)), (2), 3, 4)

(5, (1, 2, (9, 8))) ---> ((1, 2, (8, 9)), 5)

(3, (1, 2), (2, 1)) ---> (3, (1, 2), (1, 2))

(3, (1, 2, (99)), (2, 1, (34))) ---> (3, (1, 2, (99)), (1, 2, (34)))

(7, 2, (1, (9, 12)), (4, 3, 2, (1, 2))) ---> ((1, (9, 12)), 2, 7, (2, 3, (1, 2), 4))

Shortest answer in bytes wins.

Can we assume the numbers are integers?

@isaacg Yes, you can.

Jelly, 13 bytes
fFSµ€Ụịß€µ¹<?

Try it online! or verify all test cases.
How it works
fFSµ€Ụịß€µ¹<?  Main link. Input: A (list)

   µ€          Apply the chain to the left to each item B in A.
 F             Flatten B.
f              Filter; intersect B with flattened B, yielding a list.
               This returns the numbers in B if B is a list, [B] if B is a number.
  S            Compute the sum of the resulting list.
     Ụ         Sort the indices of A according to the computed sums.
       ß€      Recursively apply the main link to each B in A.
      ị        Retrieve the items of the list (right) at those indices (left).
         µ     Convert the preceding chain into a single link.
            ?  If:
           <     A compared with itself is truthy:
                   Execute the link to the left.
          ¹      Else, apply the identity function to A.

Comparing (<) a number with itself yields 0 (falsy), but comparing a non-empty list with itself yields a list of 0's (truthy), so < can be used to distinguish numbers from lists.

0 is False, but a box of 0s is True, but an empty box is False. Interesting how Python works. :P

Looks like 25 bytes (when encoded in UTF-8) to me.

@Rotsor That sounds about right. However, Jelly uses custom code page that encodes all 256 characters it understands as single bytes.

Python 2, 114 101 78 73 62 bytes
k=lambda t:t*(t<[])or t.sort(key=k)or sum(z for z in t if[]>z)

I knew there was a better way to filter lists out.
Sorts a python list (and its sublists) in-place.
https://eval.in/540457
thanks @tac for letting me know in-place solutions are acceptable, and @xnor + @feersum for further optimizations!

Some more optimization: k=lambda t:t*(t<[])or sum(z for z in t if[t.sort(key=k)]>z).

@xnor I think that solution is not quite correct: https://eval.in/540447 . For this example, we recurse down to the first sublist and grab the initial z from it, 5. Then in the conditional, we sort the list we're iterating over(!), so when we grab the next z it is ALSO 5, leading to a sum of 10. We then sort the outer list with these keys and get [6, [1, 5]], which is incorrect as "If there is a tie, you must keep the same order as the original list." The interesting thing is we call sort on both lists twice, so this only happens on equal keys:if the sublist were less it would sort back.

Good catch. It's funny that the iteration continues with the now-sorted list. I feel like there should still be a shorter way to stick in the None output of t.sort(key=k), but I'm not seeing it.

False is 0 for the purposes of + and by extension, sum. Can't think of how that saves bytes, though.

@CatsAreFluffy list.sort returns None, not False.

Oh. But why do you need t*?

Have you considered sorted?

Lua, 172 bytes
function p(a)if type(a)~="table"then return a end s(a)local t=0 for i,v in next,a do t=t+p(v)end return t end
function s(t)table.sort(t,function(a,b)return p(a)<p(b)end)end

The function s sorts a Lua table (a data structure that serves as a list among other things in Lua) in place according to the rules.

I love how type(a) returns a string

Finally an answer using Lua.

Mathematica, 50 bytes
#0/@SortBy[#,Tr@Cases[#,_Integer,{0,1}]&]~Check~#&

Simple recursive method that uses SortBy. Ignore the messages.

Haskell, 160 151 135 bytes
import Data.List
data T=N Int|T[T]deriving Show
p(N x)=x
p(T t)=sum$[x|N x<-t]
f(N x)=N x
f(T t)=T$sortBy((.p).compare.p)$map f$t

The first problem is nested lists. Haskell requires that all elements of a list have the same type; in particular, an integer and a list of integers aren't the same type. In other words, a variable-nested list isn't a list, it's a rose tree!
So first, we have to define a data type for rose trees:
data T = N Int | T [T]

(Strictly, deriving Show is only necessary if you want to see the results. But that's a technicality.) With this definition in place, we can write a list such as (1, 2, (3, 4)) as
T [N 1, N 2, T [N 3, N 4]]

which is considerably less readable. But whatever; it's a trivial, mechanical translation. Prefix every number with N and every subtree with T.
Now we need to compute priorities. This would be easy if the priority of a subtree was simple the sum of all elements it contains. That would be a trivial recursive loop. But since it isn't, we need to define two functions: one which recurses, and one which does not.
p (N x) = x
p (T t) = sum $ map q t

q (N x) = x
q _     = 0

If we were to sum all subelements, then q would not need to exist, saving a huge number of characters. Oh well!
Edit: Actually, several commentors point out that you can avoid q using a list comprehension: [ x | N x <- t]. Good call, guys!
(In fact, p would not need to exist either; we could have the compiler auto-generate an Ord instance for us in a handful of characters, and this default implementation would match the spec.)
Finally, we need to recursive over all sub-trees and sort them:
f (N x) = N x
f (T t) = T $ sortBy (\ x y -> compare (p x) (p y)) $ map f $ t

That is, f sorts a tree by recursively applying itself to all elements (map f), and then calling the sortBy function to sort the top-level. The first line says that sorting a number does nothing, and is necessary to terminate the recursion.

sortBy (\ x y -> compare (p x) (p y)) is just sortOn p. Use the infix version of map in p: sum$q<$>t.

@nimi Where is sortOn defined? I've always wanted to know...

Data.List since 4.8.0.0.

@nimi Oh cool, so they finally added it to base? Neat. If I update GHC someday I'll look forward to that...

With LambdaCase, p can be golfed as (\case N x->x;T t->sum[x|N x<-t]), obviating the q. Also, (\ x y -> compare (p x) (p y)) is also ((.p).compare.p).

@WillNess Doesn't adding {-# LANGUAGE LambdaCase #-} negate the savings? Good point about comparing though...

ah, yes. those pesky rules of counting...

I'm always tempted to cheat and say I have all those settings and imports in my ghci.conf file anyway (I actually do), and so don't have to count them. (multi-line let definitions also work in GHCi...) It would drop the count down to 109 bytes (with Data.List autoloaded as well)! Pity.

you can still shave off some 16 bytes with the list comprehension trick, p(T t)=sum[x|N x<-t] and data T=N Int|T[T]deriving Show. :)

@WillNess: if you don't care about imports you can also use on from Data.Function for (compare`on`p).

@nimi tryhaskell.org has on already defined too, but there seems to be no way to feed it a data declaration. otherwise, yes, compare `on` p == comparing p == ((.p).compare.p) (comparing is from Data.Ord, tryhaskell  also has it already defined).

Incidentally: I had no idea that a pattern-match failure inside a list comprehension is not an error, just a guard. (Then again, I never use list comprehensions for any reason, so...)

have you included 2 bytes for each newline in your count? I think we're allowed to count them as singles. Also, there's no need for $ in sum$[x|N x<-t]. So, 135-5-1=129. :)

CLISP, 380 bytes
(defun q(L)(if(null L)L(append(append(q(car(s(cdr L)(car L))))(list(car L)))(q(cadr(s(cdr L)(car L))))))))(defun s(L E)(if(not(atom(car L)))(setq L(cons(q(car L))(cdr L))))(cond((null L)'(nil nil))((<(v(car L))E)(list(cons(car L)(car(s(cdr L)E)))(cadr(s(cdr L)E))))(T(list(car(s(cdr L)E))(cons(car L)(cadr(s(cdr L)E)))))))(defun v(L)(if(atom L)L(apply'+(remove-if-not #'atom L))))

Call the function q with a list.
I'm a lisp noob, please don't kill me^^

Haha, I was hoping somebody would do it in lisp!

Pyth, 15 bytes
L?sIbbossI#NyMb

Test suite
A recursive function, that works as follows:
L?sIbbossI#NyMb
L                  define y(b):
 ?sIb              If b is an integer:          (invariant under the s function)
     b             Return it.
            yMb    Else, apply y recursively to all of the elements of b,
      o            Then sort b by
        sI#N       For each element, the elements of that list that are integers.
                   This is luckily a nop on integers.
       s           Summed.

Java, 219 bytes
import java.util.*;List f(List l){l.sort(Comparator.comparing(o->{if(o instanceof Integer)return(Integer)o;f((List)o);return((List) o).stream().filter(i->i instanceof Integer).mapToInt(i->(Integer)i).sum();}));return l;}

With line breaks:
import java.util.*;
List f(List l){
    l.sort(Comparator.comparing(o -> {
        if (o instanceof Integer)
            return (Integer) o;
        f((List) o);
        return ((List) o).stream().filter(i -> i instanceof Integer).mapToInt(i -> (Integer) i).sum();
    }));
    return l;
}

There's a lot of casting going on which really racks up the byte count. :P
Integer values are fed into a Comparator, and nested lists are sorted first before the sum of only the integer values are given to the Comparator. These values are how the Comparator determines their position within the list when it is sorted.
Try it here.

Here is the same technique at 154 bytes int f(List l){l.sort(Comparator.comparing(o->o instanceof Integer?(int)o:f((List)o)));return l.stream().mapToInt(o->o instanceof Integer?(int)o:0).sum();}

I think there is a lot more to squeeze, too.

But there are a couple issues: you cannot explicitly convert Object to int like that, and the challenge seems to require that a list is output.

You actually save 1 byte by changing the instanceof to check for List instead of Integer. Integer is 7 bytes w/o curly braces, but List is 6 bytes with it.

@TNT You can cast an Object to a primitive in java 1.7 or higher. Of course if the Object is null you'll get a npe. I don't see any problem with sorting the list in place, the challenge doesn't seem to speak to the issue directly.

JavaScript (ES6), 86 bytes
f=a=>a.map?a.map(f).sort((a,b)=>p(a)-p(b),p=a=>a.map?a.map(a=>t+=a.map?0:a,t=0)|t:a):a

All that array checking :-(

map.map.map.map.map.map.map.map.map