Shift right by half a bit The challenge is to implement a program or function (subsequently referred to as "program") that takes a nonnegative integer \$n\$ as input and returns \$n\over\sqrt{2}\$ (the input divided by the square root of two) as output, rounded to a nonnegative integer.

You may take your input and output in any reasonable format; for example stdin/stdout, files, or arguments/return values would all be acceptable.

You are required to use, at minimum, the largest fixed-size integer type offered by your language, and if an unsigned variant of this is available, you must use it. If your language has no built-in integer type (e.g. JavaScript) you are allowed to use its default numerical type (e.g. floating point); for languages with no concept of a number (e.g. regex), input and output can be e.g. the length of a string.

It is not required to reject negative integers; a submission that returns correct answers for negative inputs is allowed, but not required. Undefined behavior with negative inputs is allowed.

You are allowed and encouraged to use arbitrary-precision integer types if you so desire, but the type must either be a built-in, part of a standard library, or implemented from scratch in your program. As such, there are two categories of competition in this challenge:

Precision limited by built-in types (fixed-size integer, floating point, etc.)
Arbitrary precision (recursion and memory allocation, if used, can be assumed to be unlimited, where appropriate to the language in question)

Despite what the title might imply, you may use any rounding algorithm you want (floor, ceiling, nearest half up, nearest half even, arbitrary, or even random), as long as the difference between the integer returned value and the theoretical exact (irrational) value is always less than \$1\$ for all inputs that fit in your chosen integer type (but exactly 0 for an input of 0). All inputs up to the maximum representable value must return a correct output.

In a way, the job of this program is to calculate the irrational number \$\sqrt{2}\$ to the requested precision, presenting it in the form of an integer. This is why solutions using arbitrary-precision types are encouraged, but not required.

This is a code-golf challenge. Standard loopholes are denied. The program with the least number of bytes wins. That said, this challenge is not only about which answer wins overall; it's also about seeing how concisely the challenge can be solved in each language, seeing how each language "prefers" to handle rounding, and how hard it is to solve in esoteric languages. And for those submissions that choose to use arbitrary precision, it's about seeing how concisely this can be done in the language.

Test cases

Within the Precision-limited category, only the cases that are in range of the language's capability are required to pass.

If your solution is too slow to demonstrably pass the larger inputs (or runs out of memory/stack), it becomes all the more important to explain it sufficiently well, so that it can be understood that it would pass.

Input → Floor or Ceiling
0 → 0 (this is the only input that can only result in one valid output)
1 → 0 or 1
2 → 1 or 2
3 → 2 or 3
4 → 2 or 3
5 → 3 or 4
10 → 7 or 8
32 → 22 or 23
500 → 353 or 354
1000 → 707 or 708
1000000 → 707106 or 707107
186444716 → 131836322 or 131836323
1000000000 → 707106781 or 707106782
2147483647 → 1518500249 or 1518500250
3037000499 → 2147483647 or 2147483648
4294967295 → 3037000499 or 3037000500
4503599627370496 → 3184525836262886 or 3184525836262887
9223372036854775807 → 6521908912666391105 or 6521908912666391106
18446744073709551615 → 13043817825332782211 or 13043817825332782212
10000000000000000000000000000000000000 → 7071067811865475244008443621048490392 or 7071067811865475244008443621048490393
956287480911872131784896176254337633353980911149964074434383 → 676197362516585909969655173274459790030028262421622111830069 or 676197362516585909969655173274459790030028262421622111830070

Regex (ECMAScript+(?*)), 1169 929 887 853 849 708 bytes
-141 bytes by using the second form of shortened division, where \$A^2 > C\$
Regex was never designed to do mathematics. It has no concept of arithmetic. However, when input is taken in the form of bijective unary, as a sequence of identical characters in which the length represents a natural number, it is possible to do a wide range of operations, building up from the simple primitives available, which basically amount to addition, comparison, multiplication by a constant, and modulo. Everything must fit inside the input; it isn't possible to directly operate on numbers larger than that.
In ECMAScript regex, it's especially difficult (and therefore interesting) to do even some of the simplest of operations, because of the limitation that all backrefs captured in a loop are reset to empty at the beginning of each iteration – which makes it impossible to count anything directly. It's nevertheless possible to match prime numbers, powers of N, Nth powers, arbitrary multiplication and exponentiation, Fibonacci numbers, factorial numbers, abundant numbers, and more, much of which is demonstrated in my other answers.
One of the operations that turns out to be far more verbose than the rest is to "calculate an irrational number". I initially discussed this with teukon back in 2014. The only known way to do this is to emulate operations on numbers larger than the input, and probably the simplest way to do this is by working in a number base chosen based on what can fit into the input.
It wasn't until late 2018 that I finally set about to implementing the theory I had sketched in 2014. Implementing it involved adapting the multiplication algorithm to work with factors of 0, which turned out to golf rather elegantly. (The underlying multiplication algorithm is explained in this post.) The basic algorithm is this:
For input \$N\$, we want to calculate \$M=\lfloor{N\over\sqrt2}\rfloor\$. So we want the largest \$M\$ such that \$2M^2\le N^2\$.
If we take the "number base" to be \$k=\lceil\sqrt N\rceil\$ or \$\lfloor\sqrt N\rfloor\!+\!1\$, all multiplication operations \$m\cdot n\$ on \$0\leq m,n<k\$ are guaranteed to fit in the available space.
So if \$N=A k+B\$, where \$0\leq A,B\lt k\$, we can calculate \$N^2\$:
$$N^2=(A k+B)^2=A^2 k^2+2 A B k+B^2$$
We must then do division, modulo, and carry to bring \$A^2\$, \$2 A B\$, and \$B^2\$ back into the range of a base \$k\$ "digit". A similar operation is then done to calculate \$2 M^2\$ iterated over the decreasing consecutive possible values of \$M\$, using digit-by-digit comparison to test for \$2M^2\le N^2\$, until the first \$M\$ is found that passes the test.
So while the basic concept is simple enough, it adds up to a lot of calculations, and the regex is huge! And this is probably the simplest calculation of an irrational number that can be done in ECMAScript regex. (It is still unknown whether it's possible to calculate a transcendental number to arbitrary precision in regex.)
This regex uses molecular lookahead, a.k.a. non-atomic lookahead, represented as (?*...). Without this feature, it would be much harder (or at least much more verbose) to implement.
A choice I made early on, to depart from pure code golf by going for mathematical aesthetics, turned out to be a very interesting. I chose to use \$k=\lceil\sqrt N\rceil\$ because it has the very neat property of making the calculations fit perfectly into \$N\$ if \$N\$ is a perfect square, whereas \$k=\lfloor\sqrt N\rfloor\!+\!1\$ is basically chaotic for all inputs. They both yield the same final outputs, but the former is just cleaner. A few golfs later, this choice ended up net increasing the total length of the regex by 8 bytes, so I figured it was worth it. (This change is in the git version history.) But another golf later that day, unbeknownst to me, was actually dependent on that decision! The skipping of a divisibility check in a division calculation makes \$N=25\$ return the incorrect output of \$M=11\$ instead of \$M=17\$ if \$k=\lfloor\sqrt N\rfloor\!+\!1\$, but works perfectly for all inputs if \$k=\lceil\sqrt N\rceil\$. So the actual net change in byte length was zero! It was a purely aesthetic decision for over two years.
At the time I did not understand why that division optimization worked, but this is now fully explained thanks to H.PWiz. The shortened form of division used at the beginning of the calculation of \$M^2\$ gives the correct quotient \$B\$ when \$A+2 < 4B\$, where \$C\$ is the dividend and \$A\$ is the divisor. Previously I believed that it was only guaranteed to work when \$A \le B\$. [This is no longer used, due to the number base switch.]
And now, with the discovery of a second shortened form of division that gives the correct quotient when \$A^2 > C\$, I found a major opportunity to use it in this regex! It only works when \$k=\lfloor\sqrt N\rfloor\!+\!1\$, so now I've switched back to that number base. It's saving 141 bytes! It's oddly convenient that this just happened to exist and works perfectly for this exact use.
(?=(x(x*)).*(?=\1*$)\2+$)(?=(x\1)+(x?(x*)))(?=\4(x(x*?))\1+$)(?=.*(?=(?=\4*$)\4\5+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\9))(?=.*(?=(?=\4*$)(?=\6*$)(?=\4\7+$)\6\5+$|$\4)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\13))(?=.*(?=\12\12\9$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\17))(?*.*?(?=((?=\3*(x?(x*)))\21(x(x*?))\1+$)))(?=.*(?=\23*$)(\23\24+$))(?=.*(?=(?=\21*$)\21\22+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\27))(?=.*(?=(?=\21*$)(?=\23*$)(?=\21\24+$)\23\22+$|$\21)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\31))(?=.*(?=\30\30\27$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\35))(?=.*(?=\26\26)(?=\3*(x*))(\1(x)|))(?=.*(?=\34\34\40)(?=\3*(x*))(\1(x)|))(?=(?=(.*)\13\13\17(?=\6*$)\6\7+$)\44(x+|(?=.*(?!\16)\41|(?!.*(?!\38)\8).*(?=\16$)\41$))(\25\31\31\35){2}\43$)\20|xx?\B|
Try it on repl.it
This regex is on GitHub with a full version history.
# Given an input number N in the domain ^x*$, this regex returns floor(N / sqrt(2))
(?=
    (x(x*))                    # \1 = will be the square root of the main number, rounded down; \2 = \1 - 1
    .*(?=\1*$)
    \2+$
)

# Step 1: Calculate N*N in base floor(sqrt(N))+1. Thanks to this choice of number base to work in, we'll be able to use the
# second shortened form of division in all places where the number base is the divisor, because it's guaranteed to give the
# correct quotient when the dividend is less than the squared divisor, and N itself is less than this. This form of division
# can be recognized by its lazy rather than greedy matching of the quotient, and only one divisibility test following that.

(?=(x\1)+(x?(x*)))             # \3 = \1+1 = floor(sqrt(N))+1, the number base to work in; \4 = N % \3; \5 = \4-1, or 0 if \4==0
(?=
    \4
    (x(x*?))                   # \6 = floor(N / \3); \7 = \6-1
    \1+$
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \4
        \4\5+$
    )
    (x*?)(?=\3*$)              # \8 =       (\4 * \4) % \3, the base-\3 digit in place 0 of the result for N*N
    (x?(x*?))                   # \9 = floor((\4 * \4) / \3); \10 = \9-1, or 0 if \9==0
    (
        \1+$
    |
        $\9                    # must make a special case for \9==0, because \1 is nonzero
    )
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \6; must do symmetric multiplication, because \4 is occasionally 1 larger than \6
        (?=\6*$)
        (?=\4\7+$)
           \6\5+$
    |
        $\4                    # must make a special case for \4==0, because \6 might not be 0
    )
    (x*?)(?=\3*$)              # \12 =       (\4 * \6) % \3
    (x?(x*?))                  # \13 = floor((\4 * \6) / \3); \14 = \13-1, or 0 if \13==0
    (
        \1+$
    |
        $\13                   # must make a special case for \13==0, because \1 is nonzero
    )
)
(?=
    .*(?=\12\12\9$)            # tail =       2 * \12 + \9
    (x*?)(?=\3*$)              # \16 =       (2 * \12 + \9) % \3, the base-\3 digit in place 1 of the result for N*N
    (x?(x*?))                  # \17 = floor((2 * \12 + \9) / \3); \18 = \17-1, or 0 if \17==0
    (
        \1+$
    |
        $\17                   # must make a special case for \17==0, because \1 is nonzero
    )
)                              # {\6*\6 + 2*\13 + \17} = the base-\3 digit in place 2 of the result for N*N, which is allowed to exceed \3 and will always do so;
                               # Note that it will be equal to N iff N is a perfect square, because of the choice of number base.

# Step 2: Find the largest M such that 2*M*M is not greater than N*N

# Step 2a: Calculate M*M in base \3
(?*
    .*?                        # Determine value of M with backtracking, starting with largest values first
    (?=
        (                      # \20 =       M
            (?=\3*(x?(x*)))\21 # \21 =       M % \3; \22 = \21-1, or 0 if \21==0
            (x(x*?))           # \23 = floor(M / \3); \24 = \23-1
            \1+$
        )
    )
)
(?=
    .*
    (?=\23*$)
    (\23\24+$)                 # \25 = \23 * \23
)
(?=
    .*
    (?=
        (?=\21*$)              # tail = \21 * \21
        \21\22+$
    )
    (x*?)(?=\3*$)              # \26 =       (\21 * \21) % \3, the base-\3 digit in place 0 of the result for M*M
    (x?(x*?))                  # \27 = floor((\21 * \21) / \3); \28 = \27-1, or 0 if \27==0
    (
        \1+$
    |
        $\27                   # must make a special case for \27==0, because \1 is nonzero
    )
)
(?=
    .*
    (?=
        (?=\21*$)              # tail = \21 * \23; must do symmetric multiplication, because \21 is occasionally 1 larger than \23
        (?=\23*$)
        (?=\21\24+$)
           \23\22+$
    |
        $\21                   # must make a special case for \21==0, because \23 might not be 0
    )
    (x*?)(?=\3*$)              # \30 =       (\21 * \23) % \3
    (x?(x*?))                  # \31 = floor((\21 * \23) / \3); \32 = \31-1, or 0 if \31==0
    (
        \1+$
    |
        $\31                   # must make a special case for \31==0, because \1 is nonzero
    )
)
(?=
    .*(?=\30\30\27$)           # tail =       2 * \30 + \27
    (x*?)(?=\3*$)              # \34 =       (2 * \30 + \27) % \3, the base-\3 digit in place 1 of the result for M*M
    (x?(x*?))                  # \35 = floor((2 * \30 + \27) / \3); \36 = \35-1, or 0 if \35==0
    (
        \1+$
    |
        $\35                   # must make a special case for \35==0, because \1 is nonzero
    )
)                              # {\25 + 2*\31 + \35} = the base-\3 digit in place 2 of the result for M*M, which is allowed to exceed \3 and will always do so

# Step 2b: Calculate 2*M*M in base \3
(?=
    .*
    (?=\26\26)                 # tail =       2*\26
    (?=\3*(x*))                # \38 =       (2*\26) % \3, the base-\3 digit in place 0 of the result for 2*M*M
    (\1(x)|)                   # \40 = floor((2*\26) / \3) == +1 carry if {2*\26} does not fit in a base \3 digit
)
(?=
    .*
    (?=\34\34\40)              # tail =       2*\34 + \40
    (?=\3*(x*))                # \41 =       (2*\34 + \40) % \3, the base-\3 digit in place 1 of the result for 2*M*M
    (\1(x)|)                   # \43 = floor((2*\34 + \40) / \3) == +1 carry if {2*\34 + \40} does not fit in a base \3 digit
)                              # 2*(\25 + 2*\31 + \35) + \43 = the base-\3 digit in place 2 of the result for 2*M*M, which is allowed to exceed \3 and will always do so

# Step 2c: Require that 2*M*M <= N*N

(?=
    (?=
        (.*)                   # \44
        \13\13\17
        (?=\6*$)               # tail = \6 * \6
        \6\7+$
    )
    \44                        # tail = {\6*\6 + 2*\13 + \17}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
    (
        x+
    |
        (?=
            .*(?!\16)\41       # \41 < \16
        |
            (?!.*(?!\38)\8)    # \38 <= \8
            .*(?=\16$)\41$     # \41 == \16
        )
    )
    (\25\31\31\35){2}\43$      # 2*(\25 + 2*\31 + \35) + \43
)

\20

|xx?\B|                        # handle inputs in the domain ^x{0,4}$

Regex (ECMAScript 2018), 861 720 bytes
This is a direct port of the 849 708 byte molecular lookahead version, using variable length lookbehind.
(?=(x(x*)).*(?=\1*$)\2+$)(?=(x\1)+(x?(x*)))(?=\4(x(x*?))\1+$)(?=.*(?=(?=\4*$)\4\5+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\9))(?=.*(?=(?=\4*$)(?=\6*$)(?=\4\7+$)\6\5+$|$\4)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\13))(?=.*(?=\12\12\9$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\17))(?=.*?(?=((?=\3*(x?(x*)))\21(x(x*?))\1+$))(?<=(?=(?=.*(?=\23*$)(\23\24+$))(?=.*(?=(?=\21*$)\21\22+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\27))(?=.*(?=(?=\21*$)(?=\23*$)(?=\21\24+$)\23\22+$|$\21)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\31))(?=.*(?=\30\30\27$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\35))(?=.*(?=\26\26)(?=\3*(x*))(\1(x)|))(?=.*(?=\34\34\40)(?=\3*(x*))(\1(x)|))(?=(?=(.*)\13\13\17(?=\6*$)\6\7+$)\44(x+|(?=.*(?!\16)\41|(?!.*(?!\38)\8).*(?=\16$)\41$))(\25\31\31\35){2}\43$))^.*))\20|xx?\B|
Try it online!
This regex is on GitHub.
# Given an input number N in the domain ^x*$, this regex returns floor(N / sqrt(2))
(?=
    (x(x*))                    # \1 = will be the square root of the main number, rounded down; \2 = \1 - 1
    .*(?=\1*$)
    \2+$
)

# Step 1: Calculate N*N in base floor(sqrt(N))+1. Thanks to this choice of number base to work in, we'll be able to use the
# second shortened form of division in all places where the number base is the divisor, because it's guaranteed to give the
# correct quotient when the dividend is less than the squared divisor, and N itself is less than this. This form of division
# can be recognized by its lazy rather than greedy matching of the quotient, and only one divisibility test following that.

(?=(x\1)+(x?(x*)))             # \3 = \1+1 = floor(sqrt(N))+1, the number base to work in; \4 = N % \3; \5 = \4-1, or 0 if \4==0
(?=
    \4
    (x(x*?))                   # \6 = floor(N / \3); \7 = \6-1
    \1+$
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \4
        \4\5+$
    )
    (x*?)(?=\3*$)              # \8 =       (\4 * \4) % \3, the base-\3 digit in place 0 of the result for N*N
    (x?(x*?))                  # \9 = floor((\4 * \4) / \3); \10 = \9-1, or 0 if \9==0
    (
        \1+$
    |
        $\9                    # must make a special case for \9==0, because \1 is nonzero
    )
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \6; must do symmetric multiplication, because \4 is occasionally 1 larger than \6
        (?=\6*$)
        (?=\4\7+$)
           \6\5+$
    |
        $\4                    # must make a special case for \4==0, because \6 might not be 0
    )
    (x*?)(?=\3*$)              # \12 =       (\4 * \6) % \3
    (x?(x*?))                  # \13 = floor((\4 * \6) / \3); \14 = \13-1, or 0 if \13==0
    (
        \1+$
    |
        $\13                   # must make a special case for \13==0, because \1 is nonzero
    )
)
(?=
    .*(?=\12\12\9$)            # tail =       2 * \12 + \9
    (x*?)(?=\3*$)              # \16 =       (2 * \12 + \9) % \3, the base-\3 digit in place 1 of the result for N*N
    (x?(x*?))                  # \17 = floor((2 * \12 + \9) / \3); \18 = \17-1, or 0 if \17==0
    (
        \1+$
    |
        $\17                   # must make a special case for \17==0, because \1 is nonzero
    )
)                              # {\6*\6 + 2*\13 + \17} = the base-\3 digit in place 2 of the result for N*N, which is allowed to exceed \3 and will always do so;
                               # Note that it will be equal to N iff N is a perfect square, because of the choice of number base.

# Step 2: Find the largest M such that 2*M*M is not greater than N*N

# Step 2a: Calculate M*M in base \3
(?=
    .*?                            # Determine value of M with backtracking, starting with largest values first
    (?=
        (                          # \20 =       M
            (?=\3*(x?(x*)))\21     # \21 =       M % \3; \22 = \21-1, or 0 if \21==0
            (x(x*?))               # \23 = floor(M / \3); \24 = \23-1
            \1+$
        )
    )
    (?<=
        (?=
            (?=
                .*
                (?=\23*$)
                (\23\24+$)                 # \25 = \23 * \23
            )
            (?=
                .*
                (?=
                    (?=\21*$)              # tail = \21 * \21
                    \21\22+$
                )
                (x*?)(?=\3*$)              # \26 =       (\21 * \21) % \3, the base-\3 digit in place 0 of the result for M*M
                (x?(x*?))                  # \27 = floor((\21 * \21) / \3); \28 = \27-1, or 0 if \27==0
                (
                    \1+$
                |
                    $\27                   # must make a special case for \27==0, because \1 is nonzero
                )
            )
            (?=
                .*
                (?=
                    (?=\21*$)              # tail = \21 * \23; must do symmetric multiplication, because \21 is occasionally 1 larger than \23
                    (?=\23*$)
                    (?=\21\24+$)
                       \23\22+$
                |
                    $\21                   # must make a special case for \21==0, because \23 might not be 0
                )
                (x*?)(?=\3*$)              # \30 =       (\21 * \23) % \3
                (x?(x*?))                  # \31 = floor((\21 * \23) / \3); \32 = \31-1, or 0 if \31==0
                (
                    \1+$
                |
                    $\31                   # must make a special case for \31==0, because \1 is nonzero
                )
            )
            (?=
                .*(?=\30\30\27$)           # tail =       2 * \30 + \27
                (x*?)(?=\3*$)              # \34 =       (2 * \30 + \27) % \3, the base-\3 digit in place 1 of the result for M*M
                (x?(x*?))                  # \35 = floor((2 * \30 + \27) / \3); \36 = \35-1, or 0 if \35==0
                (
                    \1+$
                |
                    $\35                   # must make a special case for \35==0, because \1 is nonzero
                )
            )                              # {\25 + 2*\31 + \35} = the base-\3 digit in place 2 of the result for M*M, which is allowed to exceed \3 and will always do so

            # Step 2b: Calculate 2*M*M in base \3
            (?=
                .*
                (?=\26\26)                 # tail =       2*\26
                (?=\3*(x*))                # \38 =       (2*\26) % \3, the base-\3 digit in place 0 of the result for 2*M*M
                (\1(x)|)                   # \40 = floor((2*\26) / \3) == +1 carry if {2*\26} does not fit in a base \3 digit
            )
            (?=
                .*
                (?=\34\34\40)              # tail =       2*\34 + \40
                (?=\3*(x*))                # \41 =       (2*\34 + \40) % \3, the base-\3 digit in place 1 of the result for 2*M*M
                (\1(x)|)                   # \43 = floor((2*\34 + \40) / \3) == +1 carry if {2*\34 + \40} does not fit in a base \3 digit
            )                              # 2*(\25 + 2*\31 + \35) + \43 = the base-\3 digit in place 2 of the result for 2*M*M, which is allowed to exceed \3 and will always do so

            # Step 2c: Require that 2*M*M <= N*N

            (?=
                (?=
                    (.*)                   # \44
                    \13\13\17
                    (?=\6*$)               # tail = \6 * \6
                    \6\7+$
                )
                \44                        # tail = {\6*\6 + 2*\13 + \17}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
                (
                    x+
                |
                    (?=
                        .*(?!\16)\41       # \41 < \16
                    |
                        (?!.*(?!\38)\8)    # \38 <= \8
                        .*(?=\16$)\41$     # \41 == \16
                    )
                )
                (\25\31\31\35){2}\43$      # 2*(\25 + 2*\31 + \35) + \43
            )
        )
        ^.*
    )
)
\20
|xx?\B|                        # handle inputs in the domain ^x{0,4}$

Regex (ECMAScript)
I have not yet ported this algorithm to basic ECMAScript. One way to do it would be to use \$k=\lceil\sqrt[\uproot{1}3]N\rceil\$ as the number base, and calculate:
$$N^2=(A k^2+B k+C)^2=A^2 k^4 + 2 A B k^3 + (2 A C + B^2)k^2 + 2 B C k + C^2$$
Another way would be to stick with \$k=\lceil\sqrt N\rceil\$, capture \$M\$ encoded into two or more backrefs, and emulate the existing calculations within the smaller available space. I'm not sure which way would be more concise. Either way, I expect the regex would roughly double in length.


When I grow up I want to be ASCII Task

Your task is to take a character in:

AÁÀÃÂBCÇDEÉÊFGHIÍJKLMNOÕÓÔPQRSTUÚVWXYZaáàãâbcçdeéêfghiíjklmnoõóôpqrstuúvwxyz

and turn it into a characters in:

AAAAABCCDEEEFGHIIJKLMNOOOOPQRSTUUVWXYZaaaaabccdeeefghiijklmnoooopqrstuuvwxyz

by the obvious operation: dropping the accents in the letters.

Input

A character in any sensible format, including but not limited to:

A string with only one character;
A unicode codepoint.

Output

The transformed char in any sensible format, which includes:

A string with only one char;
A unicode codepoint.

Test cases

'A' -> 'A'
'Á' -> 'A'
'À' -> 'A'
'Ã' -> 'A'
'Â' -> 'A'
'B' -> 'B'
'C' -> 'C'
'Ç' -> 'C'
'D' -> 'D'
'E' -> 'E'
'É' -> 'E'
'Ê' -> 'E'
'F' -> 'F'
'G' -> 'G'
'H' -> 'H'
'I' -> 'I'
'Í' -> 'I'
'J' -> 'J'
'K' -> 'K'
'L' -> 'L'
'M' -> 'M'
'N' -> 'N'
'O' -> 'O'
'Õ' -> 'O'
'Ó' -> 'O'
'Ô' -> 'O'
'P' -> 'P'
'Q' -> 'Q'
'R' -> 'R'
'S' -> 'S'
'T' -> 'T'
'U' -> 'U'
'Ú' -> 'U'
'V' -> 'V'
'W' -> 'W'
'X' -> 'X'
'Y' -> 'Y'
'Z' -> 'Z'
'a' -> 'a'
'á' -> 'a'
'à' -> 'a'
'ã' -> 'a'
'â' -> 'a'
'b' -> 'b'
'c' -> 'c'
'ç' -> 'c'
'd' -> 'd'
'e' -> 'e'
'é' -> 'e'
'ê' -> 'e'
'f' -> 'f'
'g' -> 'g'
'h' -> 'h'
'i' -> 'i'
'í' -> 'i'
'j' -> 'j'
'k' -> 'k'
'l' -> 'l'
'm' -> 'm'
'n' -> 'n'
'o' -> 'o'
'õ' -> 'o'
'ó' -> 'o'
'ô' -> 'o'
'p' -> 'p'
'q' -> 'q'
'r' -> 'r'
's' -> 's'
't' -> 't'
'u' -> 'u'
'ú' -> 'u'
'v' -> 'v'
'w' -> 'w'
'x' -> 'x'
'y' -> 'y'
'z' -> 'z'

You can check here for a Python reference implementation without regexes.

This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

JavaScript (Node.js), 39 bytes
A port of my CP-1610 answer.
I/O format: a Unicode code point.
n=>n>>7?Buffer("ACEIOOU")[n/4&7]^n&32:n

Try it online!

JavaScript (Node.js), 44 bytes
I/O format: a string with only one character.
c=>'oeaUICuic?OEA'[Buffer(c)[1]*13%59%13]||c

Try it online!
How?
When passed into Buffer(), the accented letters used in the challenge are turned into two bytes \$(b_0,b_1)\$, corresponding to their UTF-8 encoding. The non-accented letters are turned into a single byte \$b_0\$ corresponding to their regular ASCII code (or 1-byte UTF-8 encoding).
Examples:
Buffer('À') // --> <Buffer c3 80>
Buffer('B') // --> <Buffer 42>

Try it online!
We use the following formula to convert the 2nd byte of accented letters to an index \$n\$ into a 13-character lookup string of non-accented letters:
$$n=((b_1\times13)\bmod 59)\bmod 13$$
This results in NaN for non-accented letters, which are simply left unchanged.
  c  |   UTF-8    | 2nd byte | * 13 | mod 59 | mod 13 | output
-----+------------+----------+------+--------+--------+--------
 'À' | 0xC3, 0x80 |    128   | 1664 |   12   |   12   |  'A'
 'Á' | 0xC3, 0x81 |    129   | 1677 |   25   |   12   |  'A'
 'Â' | 0xC3, 0x82 |    130   | 1690 |   38   |   12   |  'A'
 'Ã' | 0xC3, 0x83 |    131   | 1703 |   51   |   12   |  'A'
 'Ç' | 0xC3, 0x87 |    135   | 1755 |   44   |    5   |  'C'
 'É' | 0xC3, 0x89 |    137   | 1781 |   11   |   11   |  'E'
 'Ê' | 0xC3, 0x8A |    138   | 1794 |   24   |   11   |  'E'
 'Í' | 0xC3, 0x8D |    141   | 1833 |    4   |    4   |  'I'
 'Ó' | 0xC3, 0x93 |    147   | 1911 |   23   |   10   |  'O'
 'Ô' | 0xC3, 0x94 |    148   | 1924 |   36   |   10   |  'O'
 'Õ' | 0xC3, 0x95 |    149   | 1937 |   49   |   10   |  'O'
 'Ú' | 0xC3, 0x9A |    154   | 2002 |   55   |    3   |  'U'
 'à' | 0xC3, 0xA0 |    160   | 2080 |   15   |    2   |  'a'
 'á' | 0xC3, 0xA1 |    161   | 2093 |   28   |    2   |  'a'
 'â' | 0xC3, 0xA2 |    162   | 2106 |   41   |    2   |  'a'
 'ã' | 0xC3, 0xA3 |    163   | 2119 |   54   |    2   |  'a'
 'ç' | 0xC3, 0xA7 |    167   | 2171 |   47   |    8   |  'c'
 'é' | 0xC3, 0xA9 |    169   | 2197 |   14   |    1   |  'e'
 'ê' | 0xC3, 0xAA |    170   | 2210 |   27   |    1   |  'e'
 'í' | 0xC3, 0xAD |    173   | 2249 |    7   |    7   |  'i'
 'ó' | 0xC3, 0xB3 |    179   | 2327 |   26   |    0   |  'o'
 'ô' | 0xC3, 0xB4 |    180   | 2340 |   39   |    0   |  'o'
 'õ' | 0xC3, 0xB5 |    181   | 2353 |   52   |    0   |  'o'
 'ú' | 0xC3, 0xBA |    186   | 2418 |   58   |    6   |  'u'


Turn over a new leaf You're given a tree, which in computer science tradition, has the root at the top and leaves at the bottom. The leaf nodes are labelled with numbers. Your goal is to take the special leaf marked -1 and move it up to be the new root.

[3, [[16], -1], [4]]  -->  [[[[4], 3], [16]]]

You can imagine rotating the special leaf to the top and letting the rest of tree hang off of it. Keeping the tree in the plane while rotating it to get the correct left-to-right order of all the branches.

The new tree has all the leaves of the original tree except for -1.

Input:

A tree whose leaves are distinct positive integers, except for one leaf of -1. The root of the tree will have at least two branches coming off.

The input is given as a nested list like [3, [[16], -1], [[4]]] or its string representation. Delimiters are optional and up to you, but adjacent numbers need to be separated.

Output:

Output or print the flipped tree in the same format as your input. The order of the list entries must be correct. In-place modification is fine.

If your input/output is a data type, it must be one that prints in the required format by default. Built-ins that basically do the task for you are not allowed.

Test cases:

>> [3, [[16], -1], [4]]
[[[[4], 3], [16]]]

>> [2, -1]
[[2]]

>> [44, -1, 12]
[[12, 44]]

>> [[[[-1]]], [[[[4]]]]]
[[[[[[[[[4]]]]]]]]]

>> [[1, 2, 3], [4, -1, 6], [7, 8, 9]]
[[6, [[7, 8, 9], [1, 2, 3]], 4]]

>> [9, [8, [7, [6, -1, 4], 3], 2], 1]
[[4, [3, [2, [1, 9], 8], 7], 6]]

CJam, 24 24 22 bytes
l~{):T]{s$}$(+T1+}gW<p

Try it online.
Thanks Dennis for removing 2 bytes.
Explanation
l~          e# Read the input.
{           e# Do:
    ):T     e# Save the last item to T.
    ]       e# Wrap everything else (as an array) and the last item into an array,
    {s$}$   e#   where the one with -1 (having "-" if stringified) is the first item.
    (+      e# Insert the second array into the first array as the first item,
            e#   or just move the -1 to the end if the first item is already -1.
    T1+     e# Check if the array before this iteration ended with -1.
}g          e# Continue the loop if it did't.
W<p         e# Remove the -1 and print.


Federal income tax calculator for procrastinators Today is Tax Day!

Oops.

Well, today is tax day if you are a resident of Maine or Massachusetts.

So you're probably still completing your return and need a calculator for when you get to Line 44.

Given an input of taxable income (US$, accurate to 2 decimal places) and a string representing filing status, output the amount of tax (also US$ to 2 decimal places).

Filing status will be one of S, MFJ, QW, MFS, or HH for Single, Married Filing Jointly, Qualified Widow(er), Married Filing Separately or Head of Household, respectively.

Tax will be calculated according to the official tables in IRS Revenue Procedure 2014-61, section .01 Tax Rate Tables, Tables 1-4.  I have added these tables at the bottom of the question.
You may choose whatever rounding method you like, as long as the result is accurate to 2 decimal places.

Example Inputs:

0.00 S
10000.00 MFJ
100000.00 MFS
1000000.00 QW

Example Outputs corresponding to above inputs:

0.00
1000.00
21525.75
341915.90

Summary of tax tables.

Married Filing Jointly and Qualified Widow(er)

  Income Interval       Tax
  [     $0,  $18450]                 10%
  ( $18450,  $74900]      $1845    + 15%   of the excess over  $18450
  ( $74900, $151200]     $10312.50 + 25%   of the excess over  $74900
  ($151200, $230450]     $29387.50 + 28%   of the excess over $151200
  ($230450, $411500]     $51577.50 + 33%   of the excess over $230450
  ($411500, $464850]    $111324    + 35%   of the excess over $411500
  ($464850,      $∞]    $129996.50 + 39.6% of the excess over $464850

Head of Household

  Income Interval       Tax
  [     $0,  $13150]                 10%
  ( $13150,  $50200]      $1315    + 15%   of the excess over  $13150
  ( $50200, $129600]      $6872.50 + 25%   of the excess over  $50200
  ($129600, $209850]     $26722.50 + 28%   of the excess over $129600
  ($209850, $411500]     $49192.50 + 33%   of the excess over $209850
  ($411500, $439000]    $115737    + 35%   of the excess over $411500
  ($439000,      $∞]    $125362    + 39.6% of the excess over $439000

Single

  Income Interval       Tax
  [     $0,   $9225]                 10%
  (  $9225,  $37450]       $922.50 + 15%   of the excess over   $9225
  ( $37450,  $90750]      $5156.25 + 25%   of the excess over  $37450
  ( $90750, $189300]     $18481.25 + 28%   of the excess over  $90750
  ($189300, $411500]     $46075.25 + 33%   of the excess over $189300
  ($411500, $413200]    $119401.25 + 35%   of the excess over $411500
  ($413200,      $∞]    $119996.25 + 39.6% of the excess over $413200

Married Filing Separately

  Income Interval       Tax
  [     $0,   $9225]                 10%
  (  $9225,  $37450]       $922.50 + 15%   of the excess over   $9225
  ( $37450,  $75600]      $5156.25 + 25%   of the excess over  $37450
  ( $75600, $115225]     $14693.75 + 28%   of the excess over  $75600
  ($115225, $205750]     $25788.75 + 33%   of the excess over $115225
  ($205750, $232425]     $55662    + 35%   of the excess over $205750
  ($232425,      $∞]     $64998.25 + 39.6% of the excess over $232425

Python 3, 427 382 317 309 308 275 bytes

-45 bytes by figuring ternary expression out (wow that's a long line); thanks Maltysen

-65 bytes, now with iteration for DRYer code!

-8 bytes by in-lining tuple variables; thanks Majora

-1 byte by using a dict rather than ternary chain; thanks again Maltysen

-33 bytes by reusing MFS step as half of MFJ/QW and calculating tax an order of magnitude larger; thanks Neil

def f(i,s):
 t=i;k={'MFS':(9225,28225,38150,39625,90525,26675),'S':(9225,28225,53300,98550,222200,1700),'HH':(13150,37050,79400,80250,201650,27500)}
 for x in range(6):
  i-=k[s][x]if s in k else k['MFS'][x]*2
  if i>0:t+=(.5,1,.3,.5,.2,.46)[x]*i
 return'{:.2f}'.format(t*.1)

If I had been thinking I would have made the function signature t(a,x), but I guess I'll stick with function(income, status).

When code is barely undertstood by the writer, is that when you win at golf?


A queen's walk across a spiral In a far-off kingdom, a chess queen takes a daily walk across a spiral path, numbered from 1 to n, not caring to follow the spiral itself, but simply making queen's moves as she would on a chessboard. The queen is beloved by her subjects, and they make a note of every square she visits on her path. Given that the queen can start her walk on any square and ends it on any square, what is the shortest queen's walk that she can take?

The challenge

Given a spiral of integers on a rectangular grid, write a function that returns one of the shortest possible paths (counted by number of cells travelled) between two numbers on this spiral grid using a chess queen's moves.

For example, from 16 to 25:

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

Some possible paths include 16, 4, 2, 10, 25 and 16, 5, 1, 9, 25.

Rules

The input will be any two positive integers.
The output will be a path of integers (including both endpoints) across the spiral using only orthogonal and diagonal moves.
The length of a path is counted by the number of cells travelled.
Your answer may be a program or a function.
This is code golf, so the smallest number of bytes wins.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

Test cases

>>> queen_spiral(4, 5)
4, 5
>>> queen_spiral(13, 20)
13, 3, 1, 7, 20
>>> queen_spiral(14, 14)
14
>>> queen_spiral(10, 3)
10, 11, 3
>>> queen_spiral(16, 25)
16, 4, 2, 10, 25
>>> queen_spiral(80, 1)
80, 48, 24, 8, 1

APL (Dyalog Unicode), 59 57 bytesSBCS

{v⍳+\v[⍺],↓⍉↑(|⍴¨×)⊃⍵⍺-.⊃⊂v←9 11∘○¨+\0,0j1*{⍵/⍨⌈⍵÷2}⍳⍺⌈⍵}

Try it online!

-2 bytes thanks to @ngn.

Anonymous function that accepts two endpoints as left and right arguments.

Ungolfed & how it works

The queen moves diagonally first, so it is sufficient to pre-compute the coordinates of each number up to max(start,end).

The coordinate-generating algorithm is inspired from several answers on the related challenge, but is slightly different from any of the existing answers:

Given the necessary bound of 10
Generate the 1-based range r=1 2 3 4 5 6 7 8 9 10
Take the ceiling of half of each number n=1 1 2 2 3 3 4 4 5 5
Replicate each item of r by n. 1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10
Take the cumulative sum of power of imaginary unit, with starting point of 0. (this part is common to various Python solutions to the linked challenge)

Then, once the vector of coordinates v is ready, we can easily convert between the spiral index and coordinates using v[i] and v⍳coord (finding the first index of coord in v).

⍝ Define a function; ⍺=start, ⍵=end
f←{
  ⍝ Construct a vector of spiral coordinates v
  v←9 11∘○¨+\0,0j1*{⍵/⍨⌈⍵÷2}⍳⍺⌈⍵
                             ⍺⌈⍵  ⍝ max of start, end
                            ⍳     ⍝ range of 1 to that number
                   {⍵/⍨⌈⍵÷2}  ⍝ for each number n of above, copy itself ceil(n/2) times
               0j1*  ⍝ raise imaginary unit to the power of above
           +\0,      ⍝ prepend 0 and cumulative sum
                     ⍝ (gives vector of coordinates as complex numbers)
    9 11∘○¨  ⍝ convert each complex number into (real, imag) pair
  v←         ⍝ assign it to v

  ⍝ Extract start and end coordinates
  a w←(⍺⊃v)(⍵⊃v)

  ⍝ Compute the path the Queen will take
  v⍳+\(⊂a),↓⍉↑(|⍴¨×)w-a
                    w-a  ⍝ coordinate difference (end-start)
              (|⍴¨×)     ⍝ generate abs(x) copies of signum(x) for both x- and y-coords
                         ⍝ e.g. 4 -> (1 1 1 1), ¯3 -> (¯1 ¯1 ¯1)
           ↓⍉↑  ⍝ promote to matrix (with 0 padding), transpose and split again
                ⍝ (gives list of steps the Queen will take)
    +\(⊂a),     ⍝ prepend the starting point and cumulative sum
                ⍝ (gives the path as coordinates)
  v⍳  ⍝ index into the spiral vector (gives the spiral numbers at those coordinates)
}


Get the closest value to number In this code golf, you need to get the closest number from another one in a list.

The output may be the closest number to the input.

Example:

value: (Input) 5 --- [1,2,3] --- 3

And, the program may work with negative numbers.

Example:

value: (Input) 0 --- [-1,3,5] --- -1

value: (Input) 2 --- [1, 5, 3] --- 1 (Because it gives priority to lower numbers)

RULES:

As mentioned before, it has to work with negative numbers.

If there are two answers (Example: 0 -- [5,-5]), the program gives priority to the lowest number. (-5)

This is code golf so the shortest code wins!

Pyth, 6 bytes

haDQSE

Test suite

Input in the following form on STDIN:

num
array

Explanation:

haDQSE
          Implicit: Q = eval(input()) (num)
     E    Evaluate input (array)
    S     Sort (smaller values to the front)
 aDQ      Sort by absolute difference with Q.
h         Take the first element of the sorted list, the min.
          Print implicitly.


Print a layered cake Challenge

Given an input n, print an ASCII art cake n layers tall, viewed from the side, with two candles on top. Refer to the examples below for details.

Output

>> cake(1)

 _|_|_
|     |
+-----+

>> cake(3)

     _|_|_
    |     |
  +---------+
  |         |
+-------------+
|             |
+-------------+

...and so on.

Rules

Standard loopholes prohibited
Please make an attempt at a clever solution
This is code-golf, so shortest answer in bytes wins. However, the answer will not be selected.

Have fun!


Choose The Powerball Numbers! Powerball is an American lottery that has recently gained attention because the current jackpot (as of January 11, 2016) is the largest lotto prize in history, at about $1.5 billion (USD).
Powerball players choose 5 distinct numbers from 69 numbered white balls, and 1 one "Powerball" number from 26 numbered red balls. They win the jackpot if their five white ball choices match what was drawn in any order, and if they chose the correct "Powerball" number.
So the chances of winning the jackpot are 1 in (69 choose 5)*(26 choose 1) or ((69*68*67*66*65)/(5*4*3*2*1))*26, which is 1 in 292,201,338
No one won the jackpot in the most recent drawing on January 9, 2016, but perhaps someone will win the next drawing on January 13, 2016, 10:59 pm ET.
Challenge
Write a program or function that simulates a Powerball drawing, taking no input but outputting 5 distinct random numbers from 1 to 69 inclusive, and then one random "Powerball" number from 1 to 26 inclusive (which could be a repeat of one of the 5 initial numbers).
The "Powerball" number should always be the last number in the output, but otherwise the order of the first 5 numbers does not matter.
The 6 numbers should be output in decimal, either space separated or newline separated, with an optional single trailing newline. Commas, brackets, and other characters are not allowed in the output.
So these would be  valid outputs (using the numbers from the last drawing):
32 16 19 57 34 13
32
16
19
57
34
13
All 292201338 possible outcomes should be possible with uniform probability. You may use built-in pseudo-random number generators and assume they meet this standard.
Here is an ungolfed reference implementation that works in Python 2 or 3:
import random
print(' '.join(map(str, random.sample(range(1,70), 5) + [random.randint(1, 26)])))

The shortest code in bytes wins.

Note that I have no affiliation with Powerball and don't really suggest that you play. But if you win anything from numbers generated by one of the programs here, I'm sure we'd love to hear about it. :D

Dyalog APL, 10 bytes
(5?69),?26

Dyadic ? is ⍺ distinct random numbers in [1,⍵], and monadic ? is a single random number.
Try it here.


String Equivalence: Counting Substrings Background

Two strings s and t are called k-Abelian equivalent (shortened to k-equivalent in the following) for a positive integer k if the following conditions hold:

The length-k-1 prefixes of s and t are equal.
The length-k-1 suffixes of s and t are equal.
The strings s and t have the same multisets of length-k contiguous substrings.
In other words, every string of length k occurs an equal number of times in s and t.
Overlapping occurrences are counted as distinct.

Note that k-equivalent strings are always k-1-equivalent if k > 1, and the third condition implies that s and t have the same length.
It is also known, and possibly useful, that the three conditions above are equivalent to the following one:

Every non-empty string of length k or k-1 occurs an equal number of times in s and t.

An Example

For example, consider the strings s = "abbaaabb" and t = "aabbaabb".
Because the strings have the same number of each character, 4 of a and 4 of b, they are 1-equivalent.
Consider then 2-equivalence.
Their first and last characters are the same (both strings begin with a and end with b), so the first two conditions are satisfied.
The length-2 substrings of s are aa (occurs twice), ab (twice), ba (once), and bb (twice), and those of t are exactly the same.
This means that the strings are 2-equivalent.
However, since their second letters are different, the strings are not 3-equivalent.

Input

Two alphanumeric strings s and t of the same length n > 0.

Output

The largest integer k between 1 and n (inclusive) such that s and t are k-equivalent.
If no such k exists, the output is 0.
In the above example, the correct output would be 2.

Rules

You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Crashing on malformed input is perfectly fine.

Test Cases

"abc" "def" -> 0
"abbaabbb" "aabbbaab" -> 0
"abbaaabb" "aabbbaab" -> 2
"abbaaabb" "aabbaabb" -> 2
"aaabbaabb" "aabbaaabb" -> 3
"aaabbaabb" "aaabbaabb" -> 9
"abbabaabbaababbabaababbaabbabaab" "abbabaabbaababbaabbabaababbabaab" -> 9
"yzxyxx" "yxyzxx" -> 2
"xxxxxyxxxx" "xxxxyxxxxx" -> 5

CJam, 51 49 47 41 34 bytes
WqN/:Q0=,,{Qf{_,,\f>\)f<$}~=},+W=)

Just to get something started. This can surely be golfed a lot. Looking at a different algorithm too.
Input goes as the two strings without quotes on separate lines.
Example:
aaabbaabb
aabbaaabb

Output:
3

Try it online here


Lazy brainfuck programmer Background

Joe is working on his new Brainfuck answer on Codegolf. The algorithm he's using to solve the challenge is a bit complicated, so Joe came up with idea of simplifying his Brainfuck notation to make programming easier and faster.

The challenge

Let's look at snippet written by Joe a moment ago:

0+++++1+++++0[3+0-]+1[3-2+1-]2[1+2-]3[0-3[-]]

This program was meant to check for equality of #0 and #1 cells in memory. Your task is to create a preprocessor for Joe, that will replace single digits from input with '>' and '<' characters, so the memory pointer will slide to cell specified.

Input

You may take input from any source - function parameter, standard input, or any other device. The input might be in form of a stream, string, or a byte array.

The input may contain characters from all over the ASCII range, but can't contain brainfuck memory pointer instructions (< & >).

All the digits you see in the input are expected to be placed here just for your program.

Output

As Joe didn't write his preprocessor yet, he had to make the code interpretable by hand. That's the result he got:

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

There are pretty much no restrictions on output - if the input has braces unbalanced, just copy them over in unbalanced amount to the output.

Bonus tasks

If you think the challenge is too boring in current form, you might want to complete these tasks aswell for slight byte count reduction, and more fun obviously:

Optimize out nonsense related to memory operations, like digits at the end of input or clustered digits (just take the last one) - 20% of byte amount when completed
Minify Brainfuck output (remove clustered +-, ><, non-brainfuck, comments and other kind of stuff) - 20% of byte amount when completed

Rules

Standard loopholes are forbidden by default
Default I/O rules apply
Programs are scored by their size in bytes.
Solving additional tasks reduces the score.
If anything is unclear, please let me know down in the comments
Scoring of bonus tasks may increase (but not decrease!) in the future.

Opening bid - C, 144 bytes

p,c,x;void g(v){x=v?'<':'>';if(v<0)v*=-1;while(v--)putchar(x);}main(){while((c=getchar())!=-1)if(isdigit(c)){c-=48;g(c-p);p=c;}else putchar(c);}

This program should make pretty much everything clear on the input and output side of this challenge, it doesn't implement any bonus tasks though.

Jelly, 18 bytes
V©_¥®N,$Ø<xµ¹e?ØD)

A full program. Assumes (like everyone else has) that no actual Brainfuck evaluation has to be made (no balancing of unbalanced brackets)
Try it online!
How?
V©_¥®N,$Ø<xµ¹e?ØD) - Main Link: list of characters, s
                 ) - for each character, c, in s:
               ØD  -   digits = "0123456789"
              ?    -   if...
             e     -   ...condition: (c) exists in? (digits)
           µ       -   ...then: monadic link:
    ®              -            recall from register (initially 0)
   ¥               -            last two links as a dyad i.e. f(c, ®):
V                  -              evaluate (c)
 ©                 -              (copy to the register)
  _                -              subtract (®)  i.e. x = value(c) - register
       $           -            last two links as a monad i.e. f(x):
     N             -              negate (x)
      ,            -              pair with (x)  -> [-x,x]
        Ø<         -            list of characters = "<>"
          x        -            repeat (vectorises) - negatives act like 0
            ¹      -   ...else: identity - i.e. f(c) -> c
                   - implicit (smashing) print


How much time will I need to unlock my Android phone? Scenario

I am using pattern matching lockscreen and I sadly forgot my pattern. I would like to know how much time I will need to unlock it. Here are the specifications of Google's lock screen, that we will use for this challenge.

Every 5 wrong code, the user has to wait 30 seconds before any further entry.
A pattern must, at least, consist in 4 points (see below)
A point can be only used once, but you can go over it several times (see image right below):

Here, the center point is only used once, even if we go over it again for this particular pattern.

Hypothesis & Facts

We'll assume we're superheroes and that we can draw any pattern in 1 second, we never need to eat or sleep. Yeah, we're superhumans.

I'm a very unlucky person. "Worst case scenario" is my daily life so the pattern I will attempt last will be the right one.

What do we have to pwn?

For those who don't know it, Android (and other phones now) offers the ability of unlocking the phone through drawing a pattern on a 9-point matrix. This matrix can be described as follow :

C(A)  M(B)  C(C)
M(D)  X(E)  M(F)
C(G)  M(H)  C(I)

C standing for "corner point"
M for "middle point"
X for "center point"
I have given identifiers to the points to make it easier

The permitted direct connections are as follows :

Corner point :

Middle point :

Center point :

However, as pointed out by steveverrill, "once the centre has been used (and therefore becomes unavailable) a direct connection between the bottom left and top right corner becomes unambiguous and therefore possible". Same goes for every "middle point", if e.g. the point B has already been counted, then a direct connection between A and C is possible. If e.g. F has already been counted, then a direct connection between C and I is possible. Etc...

Rules

The point of this challenge is to return how much time (in human readable form, aka year/day/month/hour/whatever the time you find) I will need to unlock this damn phone.
You can't hardcode the number of possible valid patterns (don't even Google it, you fool), calculate it (that's actually the fun part, isn't it ?)
Shortest piece of code wins
Good luck !

Rebmu: 197 175 168 167 characters

Generates combinations as a series of numbers (ex. 12369 is top-left to top-right to bottom-right), checks if combination is valid, and increments a counter if it is. This might take a while* to run. Returns the number of seconds needed to unlock the phone.

B[[2 13][4 17][6 39][8 79][5 19][5 28][5 37][5 46][a 0]]Fdz[Q1feCb[st[a]paStsC/1 Qa^Qa^e?NNfiAtsC/2 e?NNfiArvTSc/2]]rpJ987653088[StsADj1233iA^e?SuqSf[++K]]adKmp30dvK 5

Unmushed and commented:

; for each subarray c:
; the sequences c/2 and c/3 are invalid before the point c/1 is pressed
; a 0 - a is never in the sequence, therefore 0 is always invalid
b: [[2 13] [4 17] [6 39] [8 79] [5 19] [5 28] [5 37] [5 46] [a 0]]
; checks (most) conditions of validity
f: dz[
    ; set q to 1
    q: 1
    ; foreach array in b as c
    fe c b [
        ; set a to be portion of s before c/1
        st [a] pa s ts c/1
        ; q = q and (a does not contain c/2) and (a does not contain reverse of c/2)
        q: a^ q
           a^ e? nn fi a ts c/2
              e? nn fi a ts rv c/2
    ]
]
; repeat 98765308 times, with j = 1 to 98765308
; 987653088 = 987654321 (largest valid combination) - 1234 (smallest valid combination) + 1
rp j 987653088 [
    ; set s to j+1233 (smallest valid combination - 1) as a string
    s: ts ad j 1233
    ; if f returns trues and s does not contain duplicates, increment k
    i a^ e? s uq s
          f
     [++ k]
]
; print k (number of combinations) + 30 * (k/5) -> number of seconds needed
ad k mp 30 dv k 5

The program loops from 1 to (987654321-1233), checking 1233+loop counter (therefore checking 1234 to 987654321).

If the number 987653088 is replaced with, 9876-1233 or 8643, then the program will find the time taken for all 4-point combinations.

Output for 9876-1233=8643 (4-point combinations):

>> rebmu %combinations.rebmu
== 11344

Output for 98765-1233=97532 (4 and 5-point combinations):

>> rebmu %combinations.rebmu
== 61426

Output for 987654-1233=986421 (4,5,6-point combinations):

>> rebmu %combinations.rebmu
== 243532

*4/5-point took me about 8 seconds to run; 4-6 took about 77 seconds. It might take ~24 hours or longer depending on who runs this to calculate number of combinations for 4-9 point combinations.


Python workarounds for assignment in lambda This is a tips question for golfing in Python.

In Python golfing, it's common for a submission to be a function defined as a lambda. For example,

f=lambda x:0**x or x*f(x-1)

computes the factorial of x.

The lambda format has two big advantages:

The boilerplate of f=lambda x:... or lambda x:... is shorter than the def f(x):...return... or x=input()...print...
A recursive call can be used to loop with little byte overhead.

However, lambdas have the big drawback of allowing only a single expression, no statements. In particular, this means no assignments like c=chr(x+65). This is problematic when one has a long expression whose value needs to be referenced twice (or more).

Assignments like E=enumerate are possible outside the function or as an optional argument, but only if they don't depend on the function inputs. Optional arguments like f=lambda n,k=min(n,0):... fail because input n hasn't been defined when k is evaluated at definition time.

The result is that sometimes you suck up repeating a long expression in a lambda because the alternative is a lengthy non-lambda.

lambda s:s.strip()+s.strip()[::-1]
def f(s):t=s.strip();print t+t[::-1]

The break even point is about 11 characters (details), past which you switch to a def or program. Compare this to the usual break-even point of length 5 for a repeated expression:

range(a)+range(b)
r=range;r(a)+r(b)

print s[1:],s[1:]*2
r=s[1:];print r,r*2

Other languages have workarounds, Octave for example. There are known tricks for Python, but they are long, clunky, and/or limited-use.  A short, general-purpose method to simulate assignment in a lambda would revolutionize Python golfing.

What are ways for a Python golfer to overcome or work around this limitation? What potential ideas should they have in mind when they see a long expression repeated twice in a lambda?

My goal with this tips question is to dive deep into this problem and:

Catalog and analyze golfing workarounds to fake assignment inside a lambda
Explore new leads for better methods

Each answer should explain a workaround or potential lead.

Assignment expressions in Python 3.8

Python 3.8 (TIO) introduces assignment expressions, which use := to assign a variable inline as part of expression.

>>> (n:=2, n+1)
(2, 3)

This can be used inside a lambda, where assignments are not ordinarily allowed. Compare:

lambda s:(t:=s.strip())+t[::-1]
lambda s:s.strip()+s.strip()[::-1]
def f(s):t=s.strip();return t+t[::-1]

See this tip for more.


Inverse Look-and-Say Background

The Look and Say Sequence is built up by reading off the digits of previous entries in the sequence, counting the number of digits in groups of the same digit. For example:

1 => 11 # (one 1)
11 => 21 # (two 1s)
21 => 1211 # (one 2, then one 1)
1211 => 111221 # (one 1, then one 2, then two 1s)

This sequence was the subject of various previous challenges. A simple Python 3 implementation of the generating function is:

>> from itertools import groupby
>> def look_and_say(obj):
      return "".join(f"{len(list(group))}{digit}" for digit, group in groupby(str(obj)))

Try it online!

Challenge

The purpose of this challenge is to implement an inverse Look and Say function. Given a Look and Say representation of a non-negative integer, your code should return the smallest non-negative integer for which the input is its Look and Say. Note that this is not the same as general Run Length Decoding, since the output must encode back precisely to the input: see the examples below for some of the subtleties involved.

This is code-golf, so shortest code in bytes wins, with all the standard loopholes forbidden. Input can be passed in (or returned) as either an integer or a string.

Test cases

10 => 0 # (1 zero)
12 => 2 # (1 two)
123 => 333333333333 # (12 threes)
1234 => 2444 # (1 two, 3 fours)
1232 => 222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222 # (123 twos, since 2222 would return 42 not 1232)
2019 => 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 # (201 nines, since the only non-negative starting with 0 is 0)
2109 => 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 # (210 nines, since 11 would return 21 not 2109)
123456 => 244466666
123454 => 333333333333444444444444444444444444444444444444444444444 # (12 threes, 45 fours)
124234 => 2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222444 (124 twos, 3 fours, which is smaller than the alternatives)

Invalid inputs

Since there are no integers which have the following Look and Say representations, the behaviour for these inputs is undefined:

1
3
20
100
1010
10010

05AB1E, 11 bytes

∞<ÅΔÅγs.ιJQ

Try it online!

Computes the look and say of all integers until finding one that matches the input. Will timeout for large outputs.


Make your country proud! You are from the tiny country of Que-Wopistan. The Que-Wopistonion's are a proud people, and every Que-Wopistonian dreams of making their country proud by representing their country in the Olympics.

You have been given the incredible honor of competing in the 100-meter-dash. You are the nations sole representative, so there is a huge amount of pressure on you to do well. Unfortunately though, Que-Wopistan's training program is awful! Absolutely terrible. You can't work with this, so you decide to train yourself.

You try a few practice runs. On the first run, you make it 0.3 meters forward, and then fall on your face. You are dedicated though, so you get up and try again. This time, you actually go backwards -1.7 meters, before falling on your face again. You try again. And again. And agin. And again, but every time you fall on your face before making even 2 meters forward. You just aren't coordinated enough to run. Or walk. Or even-- not fall on your face.

This is where your programming expertise comes in handy.

The challenge

In case you haven't realized yet, I am talking about the game QWOP. Once you have wasted 60 minutes, mashed your face into the keyboard, and now returned to this page after rage-quitting (don't worry, I did the same thing), here is your challenge. You must write a program that uses simulated key-presses to play the game of QWOP for you. The following actions do not have to be done by your program (you can do them manually yourself)

Opening the web browser and going to the correct page.
Starting and re-starting the game.
Make a screen recording.

Everything else must be automated by your program.

Judging criteria

The winner of this contest will be the program that makes it the farthest. In the unlikely event of a tie (Which will happen if anyone actually makes it 100 meters), the winner will be decided by who made it there quicker. This is not code-golf, byte-count makes no difference.

If your program automatically detects the game being over (the game ends if you fall on your face or make it 100 meters) and exits, you will get a +10 meter bonus.

AutoHotkey, 100.5 m

After running the following script, it can be activated by pressing Windows+H (yes, it only works on Windows). It can be stopped by pressing Escape.
#SingleInstance force

Esc::ExitApp

#h::
    Loop,5 {
        Send, {w down}
        Sleep, 300
        Send, {w up}
        Sleep, 300
    }
    Loop,9999 {
        Loop, 23 {
            Send, {q down}
            Sleep, 200
            Send, {q up}
            Sleep, 400
            Send, {w down}
            Sleep, 350
            Send, {w up}
            Sleep, 400
        }
        Loop,6 {
            Send, {w down}
            Sleep, 250
            Send, {w up}
            Sleep, 400
        }
    }
return

This particular code reached the finish line the first time it was run. I don't want to test it again now, because it takes forever and I can't do anything else while running it (Please comment if you figure out how to send keys to the Flash player without it being in focus). Caveat: At around 30 m, no keys were sent for a few seconds because a Windows pop-up jacked the focus. It was tested in Chrome browser.
When the script reached the obstacle at 50 m, the script somehow jumped over it right away, which may be a lucky and unusual occurrence. As for the time, the game irritatingly does not tell you how long the run took, but it does have a built-in tiebreaker by allowing you to jump as far as possible beyond the finish line at the end.
Also, this game's code does not seem very robust:

Huh?


Given a string, calculate the number of the column it corresponds to In Excel, the columns range from A-Z, AA,AB,AZ,BA,..,BZ and so on. They actually each stand for numbers, but rather are encoded as alphabet strings.

In this challenge, you will be given a string of alphabets, and you must calculate the column it corresponds to.

Some tests:

  'A' returns 1 (meaning that it is the first column)

  'B' returns 2

  'Z' returns 26

  'AA' returns 27

  'AB' returns 28

  'AZ' returns 52

  'ZZ' returns 702

  'AAA' returns 703

You can assume that capital letters will be given only.

Shortest bytes win.

Good luck!

Perl 6, 17 bytes

{:26[.ords X-64]}

Try it online!

Anonymous code block that subtracts 64 from each byte value and converts from base 26 with Z overflowing to the next column.


Generate the names of the keys on a piano On a standard 88 key piano, each key has a scientific name.

The first three keys are A0, B♭0, and B0. The keys then proceed through C1, D♭1, D1, E♭1, E1, F1, G♭1, G1, A♭1, A1, B♭1, B1, and start over again at C2. This continues up through B7, and the final key is C8.

Any flat can instead be written as a sharp of the preceding note, e.g. D♭4 can also be written C♯4. If necessary, you can write "D♭4" as "Db4".

Your program should build an ordered sequence (array, list, vector, etc.) containing the key names (as strings, symbols, or some similar data structure) in order.

Program length should be measured in characters, to avoid penalizing people who properly generate ♯ or ♭ rather than # or b. However, Unicode recoding is forbidden.

Bash shell script (58)

echo {8..0}{B,♭B,A,♭A,G,♭G,F,E,♭E,D,♭D,C}|rev|cut -b40-410

If you do not have rev, you can instead use tac -rs. at a cost of five characters.

Bending the rules, I can subtract thirteen characters (for a score of 45):

echo {8..0}{B,♭B,A,♭A,G,♭G,F,E,♭E,D,♭D,C}|rev

If you really need a bash array, add six characters to the score (for a score of 64):

a=(`echo {8..0}{B,♭B,A,♭A,G,♭G,F,E,♭E,D,♭D,C}|rev|cut -b40-410`)


Simulate Bitwise Cyclic Tag Challenge

Given two strings in any default I/O format, do the following:

NOTE: The challenge will refer to the first string as the "data" and the second referred to as the "program".

Change the program to an infinite string which is just the program repeated infinitely (e.g. 10 --> 1010101010...). The challenge will refer to this as the "infinite program"
While the data is non-empty, do the following while looping over the infinite program:

a. If the current command is "0", delete the left-most bit in the data. If the data is empty, "0" does not do anything.

b. If the current command is "1", append the next character in the program to the data if the left-most bit in the data is a one.

c. If the data is not empty now, output the data.

Test Cases

Data is the left side of the input and the program is the right side.

100, 0 --> 00, 0
1111, 1 --> 11111, 111111, 1111111, ...
10, 011 --> 0, 0, 0
1110, 011 --> 110, 1101, 11010, 1010...

Notes

The data and program will consist of only 0s and 1s
For data/programs that do not halt, your program does not need to halt.
The data and program will not be empty in the input.
You may have multiple trailing and leading newlines
Standard Loopholes are forbidden
You can use any convenient I/O format

As always with code-golf, shortest code wins!

Haskell, 77 71 62 bytes

f@(d:e)#(p:q)=f:[e,f++take d q]!!p#q
_#_=[]
a!b=tail$a#cycle b

Try it online!

Edit: -9 bytes thanks to @xnor.


Convert JSON string to Key / Value Arrays Convert JSON (key/value pairs) to two native arrays, one array of keys and another of values, in your language.

var X = '{"a":"a","b":"b","c":"c","d":"d","e":"e","f":"f9","g":"g2","h":"h1"}';

The value array could be an array of strings or integers.

So we need two functions keys & vals, returning native arrays on input of JSON string.

In above example the output would be:

keys : ["a", "b", "c", "d", "e", "f", "g", "h"]
vals : ["a", "b", "c", "d", "e", "f9", "g2", "h1"]

Here is my attempt at this using javascript:

keys : (53 Chars)

function keys(X){return X.match(/[a-z0-9]+(?=":)/gi)}

vals : (56 Chars)

function vals(X){return X.match(/[a-z0-9]+(?="[,}])/gi)}

Can other languages challenge this??

Python, 27/30

To actually comply with the rules:

keys=lambda x:list(eval(x))
vals=lambda x:eval(x).values()

Python, 30

Just using one function:

lambda x:zip(*eval(x).items())

This will separate the keys from the values and return them in a list.

Python, 7

If returning a dictionary is allowed, then this is all you need:

eval(x)


Triangles in a tetrahedron The goal of this challenge is to extend the OEIS sequence A334581.

Number of ways to choose \$3\$ points that form an equilateral triangle from the \$\binom{n+2}{3}\$ points in a regular tetrahedral grid of side length \$n\$.

The sequence begins 0, 0, 4, 24, 84, 224, 516, 1068, ...
Example
For example, if we take side lengths of \$n=4\$, as in the example below, there are \$\binom{4+2}{3} = 20\$ vertices and \$\binom{20}{3} = 1140\$ ways to choose three of them. Of these, there are \$84\$ ways to choose \$3\$ vertices that form an equilateral triangle:

Challenge
This fastest-code challenge will have you compute as many terms of the sequence [A334581(0), A334581(1), ...] that you can in ten minutes, as measured on my machine.

Rust, \$A(1), \dotsc, A(1375)\$ in 10 minutes

Unofficial score on Ryzen 7 1800X (8 cores/16 threads).  Build with cargo build --release and run with time target/release/tetrahedron n to compute \$A(1), \dotsc, A(n)\$.

This runs in \$O(n^4)\$ time.  (So to estimate a good value of \$n\$ for your CPU, first time it for some smaller \$n\$, then multiply that \$n\$ by a factor of \$\left(\frac{600\,\mathrm{s}}{t}\right)^{1/4}\$.)

How it works

Any triangle that fits inside a tetrahedron of minimal side \$k \le n\$ may be translated inside a tetrahedron of side \$n\$ in exactly \$\binom{n - k + 3}{3}\$ ways.  This means we only need to find it in one position, leaving six free parameters.  Two of these parameters may be computed from the other four (up to a sign choice) if the triangle is to be equilateral, so we only need to loop over an \$O(n^4)\$ space.

src/main.rs

use rayon::prelude::*;

fn get_counts(n: i64, a0: i64) -> Vec<i64> {
    let mut c = vec![0; n as usize];
    let a0a0 = a0 * a0;
    for a1 in if a0 == 0 { 1 } else { -n + 1 }..n {
        let d = a0a0 + a1 * a1;
        let m = n - a0.abs() - a1.abs();
        for a2 in if m > 0 {
            -n + 2 - (m & 1)..n
        } else {
            -n - m + 2..n + m
        }
        .step_by(2)
        {
            let d = d + a2 * a2;
            let r = 2 * (a0a0 - d);
            if r == 0 {
                continue;
            }
            for b0 in a0..n {
                let pp = d * (3 * d - 4 * (a0a0 + b0 * (b0 - a0)));
                if pp < 0 {
                    break;
                }
                let p = (pp as f64).sqrt() as i64;
                if p * p != pp {
                    continue;
                }
                let q = 2 * a0 * b0 - d;
                let mut check = |p: i64| {
                    let b1r = p * a2 + q * a1;
                    if b1r % r != 0 {
                        return;
                    }
                    let b1 = b1r / r;
                    let b2r = -p * a1 + q * a2;
                    if b2r % r != 0 {
                        return;
                    }
                    let b2 = b2r / r;
                    if (b0, b1, b2) <= (a0, a1, a2) || b0 + b1 + b2 & 1 != 0 {
                        return;
                    }
                    let t = 0.max(a0 + a1 + a2).max(b0 + b1 + b2)
                        + 0.max(-a0 - a1 + a2).max(-b0 - b1 + b2)
                        + 0.max(-a0 + a1 - a2).max(-b0 + b1 - b2)
                        + 0.max(a0 - a1 - a2).max(b0 - b1 - b2);
                    if t >= 2 * n {
                        return;
                    }
                    c[t as usize / 2] += 1;
                };
                check(p);
                if p != 0 {
                    check(-p);
                }
            }
        }
    }
    c
}

fn add_vec(c0: Vec<i64>, c1: Vec<i64>) -> Vec<i64> {
    c0.into_iter().zip(c1).map(|(x0, x1)| x0 + x1).collect()
}

fn main() {
    let n = std::env::args().skip(1).next().expect("missing argument");
    let n = n.parse().expect("not an integer");
    let counts = (0..n)
        .into_par_iter()
        .map(|a0| get_counts(n, a0))
        .reduce(|| vec![0; n as usize], add_vec);
    let (mut d0, mut d1, mut d2, mut d3) = (0, 0, 0, 0);
    for (i, x) in (1..).zip(counts) {
        d3 += x;
        d2 += d3;
        d1 += d2;
        d0 += d1;
        println!("{} {}", i, d0);
    }
}

Cargo.toml

[package]
name = "tetrahedron"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"

[dependencies]
rayon = "1.3.0"

Try it online!  (Parallelism removed for TIO.)


Pen Pineapple Apple Pen... with your own pens, pineapples and apples Prelude:

This challenge is different from "another cat program".
There's literal tons of different twists, why can't I have my own, people?
Unique things:

It isn't reading direct input to output.
It is manipulating the string in a way that for sure isn't a straight-up cat.

Challenge:

Given 3 inputs (or one input, separated however you like) get three objects (words) that we're going to substitute for pens, pineapples and apples in the lyrics and output.

Output format (according to lyrics found on AZLyrics):

Assuming (replace values with brackets with these):

A, B, C with input words (ex. apple)
UA, UB, UC with input words with uppercase first letters (if not uppercase already) (ex. Apple)
FUA, FUB, FUC with respectively first uppercase letters: (ex. A)
a/an with article respective to first letter vowel/consonant (ex. an)

[FUA]-[FUB]-[FUC]-[FUA]

I have [a/an] [A], I have [a/an] [C].
Uh! [UC]-[UA]!

I have [a/an] [A], I have [a/an] [B].
Uh! [UB]-[UA]!

[UC]-[UA], [UB]-[UA].
Uh! [UA]-[UB]-[UC]-[UA].
[UA]-[UB]-[UC]-[UA]!

Test case:

Test with pen, pineapple and apple:

P-P-A-P

I have a pen, I have an apple.
Uh! Apple-Pen!

I have a pen, I have a pineapple.
Uh! Pineapple-Pen!

Apple-Pen, Pineapple-Pen.
Uh! Pen-Pineapple-Apple-Pen.
Pen-Pineapple-Apple-Pen!

Rules:

If input doesn't start with a letter, assume consonant (a) and first uppercase the first character (ex. 123 -> 1).
code-golf, lowest amount of characters wins!


Keep nonzeros and their neighbours Taken from this question at Stack Overflow. Thanks also to @miles and @Dada for suggesting test inputs that address some corner cases.

The challenge

Given an array of integer values, remove all zeros that are not flanked by some nonzero value.

Equivalently, an entry should be kept either if it's a nonzero or if it's a zero that is immediately close to a nonzero value.

The entries that are kept should maintain in the output the order they had in the input.

Example

Given

[2 0 4 -3 0 0 0 3 0 0 2 0 0]

the values that should be removed are marked with an x:

[2 0 4 -3 0 x 0 3 0 0 2 0 x]

and so the output should be

[2 0 4 -3 0 0 3 0 0 2 0]

Rules

The input array may be empty (and then the output should be empty too).

Input and output formats are flexible as usual: array, list, string, or anything that is reasonable.

Code golf, fewest best.

Test cases

[2 0 4 -3 0 0 0 3 0 0 2 0 0] -> [2 0 4 -3 0 0 3 0 0 2 0]
[] -> []
[1] -> [1]
[4 3 8 5 -6] -> [4 3 8 5 -6]
[4 3 8 0 5 -6] -> [4 3 8 0 5 -6]
[0] -> []
[0 0] -> []
[0 0 0 0] -> []
[0 0 0 8 0 1 0 0] -> [0 8 0 1 0]
[-5 0 5] -> [-5 0 5]
[50 0] -> [50 0]

JavaScript (ES6), 35 bytes

a=>a.filter((e,i)=>e|a[i-1]|a[i+1])

Works on floats too for two extra bytes.


On the Subject of Keypads Keep Talking and Nobody Explodes is a local multiplayer game where one player has control over a virtual "bomb", and has to be guided by another player, the "expert", who has access to a bomb defusal manual. One of the modules to be disarmed in the game is the keypad module, which is what we'll be dealing with in this challenge.

The task

Input will start with a single line of printable ASCII characters except space (0x21 to 0x7E). These represent the keypad buttons visible to you.

The next few lines will represent "keys" – only one line will contain all of the characters of the first line, not necessarily in order. Your task is to output the keypad characters, in the order of the matching key line.

For example, if the input was

5~Fy
HrD7K!#}
Ui%^fHnF
)Tf;y~I5
~Fi(&5gy
,'Xd#5fZ

then the keypad buttons are 5, ~, F and y. Only the 4th key line ~Fi(&5gy contains all of these characters, so we output the keypad characters in the order in which they appear, i.e. ~F5y.

Rules and clarifications

Input must be a single multiline string, with the keypad buttons and key lines on separate lines.
There will be exactly one key line which contains all of the keypad characters.
Every line, i.e. the initial keypad line and following key lines, will have no duplicate characters.
Unlike the game, you may not assume anything about the number of keypad characters, the length of each key line or the number of key lines. However, all key lines are guaranteed to be the same length.
The output may contain a single optional trailing newline. Similarly you may assume either way about an optional trailing newline in the input, but please specify in your answer if you need the assumption.
Although this already seems to be common practice, I'll state explicitly: terminating with an error is okay for this challenge, as long as STDOUT output is correct (if this is your chosen form of output). Hopefully this will make handling input easier.

Test cases

7
4?j01C3"ch
KP.OG>QB)[
z#)Kn"I2&.
]#,D|sBFy5
Qzj*+~7DLP

Output: 7. Only the last line contains a 7.

0b~
Ob+hy{M|?;>=dtszPAR5
*8rCfsw|3O9.7Yv^x>Hq
$ip.V@n}|La:TbIt^AOF
jZ[Ec4s0|%b*$id',~J6
z*#b}-x$Ua&!O2;['T+?
NVj_X8rlhxfnS\.z}];c
bykscf.w^dnWj+}-*2g_
VP`AJH|&j5Yqmw/"9IMc

Output: 0b~. The 4th key line already contains the characters in the right order.

MTuz
bIAr>1ZUK`s9c[tyO]~W
oMGIi/H&V"BeNLua%El=
j*uYbplT:~);BM|_mPZt
Q}z5TC@=6pgr<[&uJnM%
YOA(F~_nH6T{%B7[\u#5
y&t"8zQn{wo5[Idu4g:?
[0tZG"-fm!]/|nqk,_2h
dA&C.+(byo6{7,?I}D@w

Output: zTuM. The key line is the 4th one, although the 3rd key line is a close miss.

o@nj<G1
f]?-<I6h2vS*%l=:}c8>LK5rMdyeon,;sE[@m(73
ibhp+2Hq6yKzIf_Zo}EO3-[*0/e&Fvd]wQU=|%`C
;}>d'cg~CPtQG&%L\)MUl419bkTZ7@]:[*H"RyYj
L^<:zXJ#kj$EFlwN%B`Dd,Cs?]xRZ*K9-uQ.@&f+
i1v'7:90R-l}FMxj`,DTWK+(n32Z4Vs[p@%*eS!d
B|^Ti/ZG$}ufL9*wE[AVt]P7CrX-)2JpD<sYxd6O
ex.$4#KarS^j+'_!B"]H[\83:(DCXUgI*Lct?qAR
^GXQoy*KW&v}n']Em~\N9)fxP(qC=7#4sRdcD6%5
;inr[&$1j_!F~@pzo#blv]}<'|fRds6OW%tEg"G2
e;0T#gfo^+!:xHDN&4V=In?AwhEv$2Fd~ZLz_\81

Output: n1j@o<G. The key line is the second last line.

Scoring

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

CJam, 13 12 bytes

qN/(f&{,}$W=

Test it here.

Explanation

q     e# Read all input.
N/    e# Split into lines.
(     e# Pull off the keypad buttons.
f&    e# Take the set intersection of each key line with the keypad, preserving the order
      e# order in the key line.
{,}$  e# Sort the results by length.
W=    e# Pick the last (longest) one.


Euler's Geometry Puzzle Today (or tomorrow, depending on your timezone, by the time of posting) is the birthday of the great mathematician and physicist Leonhard Euler. To celebrate his birthday, this challenge is about one of his theorems in geometry.

For a triangle, we define its incircle to be the largest circle inside the triangle and its circumcircle to be the circle that passes through all of the traingle's vertices.

Consider a triangle in a plane, we plot the center of its incircle I (sometimes called incenter) and the center of its circumcircle O (sometimes called circumcenter). Let \$r\$ be the radius of the incircle, \$R\$ be the radius of circumcircle, \$d\$ be the distance between I and O. Euler's theorem in geometry states that \$d^2=R(R-2r)\$.

The challenge

In the spirit of this theorem, your task, is for a triangle given by the lengths of its three sides, output \$d\$ (the distance between incenter I and circumcenter O described above).

Your code needs to take only the length of the three sides of triangle and output \$d\$. Inputs and outputs can be in any reasonable format.
The absolute error or relative error from your output and correct answer must be no greater than \$10^{-2}\$.
It's guaranteed that the three side lengths are positive integers and can form a non-degenerate triangle.
Standard loopholes are forbidden.

Since this is a code-golf, the shortest code in bytes wins!

Examples

In the samples, the outputs are rounded to 3 decimal places. You, however, are free to round them to more decimal places.

[a,b,c]       -> d
[2,3,4]       -> 1.265
[3,4,5]       -> 1.118
[3,5,7]       -> 3.055
[7,9,10]      -> 1.507
[8,8,8]       -> 0.000
[123,234,345] -> 309.109

List of sample inputs:

[[2,3,4],[3,4,5],[3,5,7],[7,9,10],[8,8,8],[123,234,345]]

JavaScript (ES7),  80 74 66  65 bytes

(a,b,c)=>(s=a+b+c,(p=a*b*c/s)*p/4*(s/=2)/(s-a)/(s-b)/(s-c)-p)**.5

Try it online!
How?
This is derived from:

The semiperimeter \$s\$ of the triangle:
$$s=\frac{a+b+c}{2}$$

The circumradius \$R\$ of the triangle:
$$R=\frac{abc}{4\sqrt{s(s-a)(s-b)(s-c)}}$$

The product of the inradius \$r\$ and the circumradius:
$$rR=\frac{abc}{2(a+b+c)}=\frac{abc}{4s}$$

Euler's theorem:
$$d=\sqrt{R(R-2r)}=\sqrt{R^2-2rR}=\sqrt{R^2-\frac{abc}{2s}}$$


Phibonacci - Relation between Phi and Fibonacci You want to see how quickly the ratio of two consecutive Fibonacci numbers converges on φ.
Phi, known by the nickname "the golden ratio" and written as \$φ\$, is an irrational number, almost as popular as π and e. The exact value of \$φ\$ is \$\frac {1 + \sqrt 5} 2 = 1.618...\$
The Fibonacci sequence is a recursive series of integers calculated by
$$F_n = F_{n-1} + F_{n-2} \\
F_0 = 0 \\
F_1 = 1$$
Calculate \$φ\$'s value and the ratio \$\frac {F_n} {F_{n-1}}\$. How closely does \$φ\$ match the ratio?
Examples
\$n = 2\$, ratio: \$\frac 1 1 = 1.000\$, compared to \$1.618...\$, 0 decimal spots match
\$n = 5\$, ratio: \$\frac 5 3 = 1.666...\$, compared to \$1.618...\$, 1 decimal spot matches
Input
1 integer \$n\$ to calculate \$\frac{F_n}{F_{n-1}}\$
\$ n >= 5\$
Output
1 integer \$x\$, indicating the number of decimal places that match the value of \$φ\$
It is acceptable that the program only works accurately until the float precision limit of the language.
Test Cases
Input -> Output

5 -> 1
10 -> 2
12 -> 2
15 -> 5
20 -> 7
23 -> 7
25 -> 9
50 -> 18
100 -> 39

Tips
Do not round the ratio of \$\frac{F_n}{F_{n-1}}\$
Rounding will give you errors.
Let's look at \$n = 5\$ again.
\$1.666...\$ rounds to \$1.7\$ and \$1.618...\$ rounds to \$1.6\$, so 0 is the wrong answer.
Useful information and math.
The limit of the ratios of the consecutive Fibonacci terms as  \$n\$  tends to infinity is the golden number \$φ\$. The inverse of this ratio is \$\frac 1 φ\$ which equals to \$φ−1\$.
\$\frac 1 φ = φ -1 \$
\$ \lim_{n \to \infty} \frac{F_n}{F_{n-1}} = φ\$
Winning criterion
Code Golf.

JavaScript (ES7),  77 75 69  67 bytes

n=>(g=p=>--n>1?g(q,q+=p):(1+5**.5)/2*(m*=10)^q/p*m?0:1+g(p))(q=m=1)

Try it online!
Commented
n => (            // main function, taking n
  g = p =>        // g is a recursive function taking p which, along with q,
                  // is used to compute the Fibonacci sequence
  --n > 1 ?       // decrement n; if it's still greater than 1:
    g(q, q += p)  //   do a recursive call with (p, q) = (q, q + p)
  :               // else:
    (1 + 5 ** .5) //   compute the golden ratio
    / 2           //
    * (m *= 10)   //   multiply m by 10 and multiply the golden ratio by m
    ^             //   xor (forces the decimal places to be discarded)
    q / p         //   compute q / p (last Fibonacci term / penultimate one)
    * m           //   multiply by m
    ?             //   if the above values are not equal:
      0           //     stop
    :             //   else:
      1 + g(p)    //     increment the final result and do a recursive call
)(q = m = 1)      // initial call to g with p = q = m = 1


Strange ways to keep an endless high CPU usage There are some ways which cause an endless high CPU usage such as catching recursion exception. e.g. the following script in Python causes that problem:

def main():
    try:
        main()
    except:
        main()

main()

This is an obvious and simple example, but there might be some strange ways to arise such problems.

JavaScript

Even JavaScript beginners should understand the code below!

// JavaScript for Beginners
// Variables, for loops

// The line below will set a global variable called "x" to 90
// Note: never use this style of code. It is evil!
х = 90;

// The line below will set a local variable called "x" to 90
var x = 90;

for (var х=0; х<10; x++) {
  console.log('JS for beginners: this is iteration #' + х);
}

Warning

   It produces an infinite loop
 Don't run it in your browser unless you know how to kill the tab/process or restart the machine :)

How does it work?

   There are two kinds of variable names in the code:
 1. the normal 'x' which can be found on the keyboard
 2. a cyrillic 'х': http://en.wikipedia.org/wiki/%D0%A5


Generate Dennis Numbers This challenge is a tribute to PPCG user Dennis for winning the robbers' part of The Programming Language Quiz.
Looking at Dennis' PPCG profile page we can see some pretty impressive stuff:

He currently has over sixty-eight thousand reputation, making him second in rep overall, surpassing third place by almost thirty thousand. He recently won our election for a new moderator and got a shiny new diamond next to his name. But I personally think the most interesting part about Dennis is his PPCG user ID number: 12012.
At first glance 12012 almost looks like a palindrome, a number that reads the same when reversed, but it's a little off. It can become the palindrome 21012 if we swap the positions of the first 1 and 2, and it can become the palindrome 12021 if we swap the last 1 and 2. Also, following the convention that leading zeroes in a number are not written, swapping the first 1 and the 0 results in 02112 or rather 2112 which is another palindrome.
Let's define a Dennis number as a positive integer that is not palindromic itself but can be made into a palindrome by swapping the positions of at least one pair of any two digits. The order of a Dennis number is the number of distinct pairs of digits that can be swapped to make a (not necessarily distinct) palindrome.
So the order of 12012 is 3 since 3 distinct pairs of its digits (12012, 12012, 12012) can be swapped around to produce palindromes. 12012 happens to be the smallest order 3 Dennis number.
10 is the smallest Dennis number and has order 1 because switching around the 1 and 0 gives 01 a.k.a. 1 which is a palindrome.
The imaginary leading zeroes of a number don't count as switchable digits. For example, changing 8908 to 08908 and swapping the first two digits to get the palindrome 80908 is invalid. 8908 is not a Dennis number.
Non-Dennis numbers could be said to have order 0.
Challenge
Write a program or function that takes in a positive integer N and prints or returns the Nth smallest Dennis number along with its order in some reasonable format such as 12012 3 or (12012, 3).
For example, 12012 is the 774th Dennis number so if 774 is the input to your program, the output should be something like 12012 3. (Curiously, 774 is another Dennis number.)
The shortest code in bytes wins.
Here is are the first 20 Dennis numbers and their orders for reference:
N       Dennis  Order
1       10      1
2       20      1
3       30      1
4       40      1
5       50      1
6       60      1
7       70      1
8       80      1
9       90      1
10      100     1
11      110     2
12      112     1
13      113     1
14      114     1
15      115     1
16      116     1
17      117     1
18      118     1
19      119     1
20      122     1

Here is the same list up to N = 1000.

CJam, 45 bytes

0{{)_s:C,2m*{~Ce\is_W%=},,2/:O!CCW%=|}g}ri*SO

Try it online!

How it works

0          e# Push 0 (candidate).
{          e# Loop:
  {        e#   Loop:
    )_     e#     Increment the candidate and push a copy.
    s:C    e#     Cast to string and save in C.
    ,      e#     Get the length of C, i.e., the number of digits.
    2m*    e#     Push all pairs [i j] where 0 ≤ i,j < length(C).
    {      e#     Filter:
      ~    e#       Unwrap, pushing i and j on the stack.
      Ce\  e#       Swap the elements of C at those indices.
      is   e#       Cast to int, then to string, removing leading zeroes.
      _W%= e#       Copy, reverse and compare.
    },     e#     Keep the pairs for which = returned 1, i.e., palindromes.
    ,2/    e#     Count them and divide the count by 2 ([i j] ~ [j i]).
    :O     e#     Save the result (the order) in O.
    !      e#     Negate logically, so 0 -> 1.
    CCW%=  e#     Compare C with C reversed.
    |      e#     Compute the bitwise NOT of both Booleans.
           e#     This gives 0 iff O is 0 or C is a palindrome.
  }g       e#   Repeat the loop while the result is non-zero.
}ri*       e# Repeat the loop n times, where n is an integer read from STDIN.
           e# This leaves the last candidate (the n-th Dennis number) on the stack.
SO         e# Push a space and the order.


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

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.


Simplificate an array Input
An array that can contain arrays or positive, consecutive, ascending integers. The arrays can have any number of arrays inside of them, and so on and so forth. No arrays will be empty.
Output
This array simplificated
How to simplificate an array
We will use the array, [1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]] as our example.
First, we check how deep the values are nested. Here are the depths and the numbers at those depths:
0  1
1  2 3 9
2  4 7
3  5 6
5  8

We construct the output array by taking the numbers in the original array, grouping them by how deep they are nested, and then nesting the groups at depths of the original depths of their  elements. Arrange the numbers in ascending order and ascending depth.
So, our output is [1, [2, 3, 9], [[4, 7]], [[[5, 6]]], [[[[[8]]]]]]
Examples
[1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]] -> [1, [2, 3, 9], [[4, 7]], [[[5, 6]]], [[[[[8]]]]]]
[[[1]], [2, [3]], 4, [5, [6, [7, [8], [9, [[10]]]]]]] -> [4, [2, 5], [[1, 3, 6]], [[[7]]], [[[[8, 9]]]], [[[[[[10]]]]]]]
[1] -> [1]
[1, [2], [[3]], [[[4]]], [[[[5]]]]] -> [1, [2], [[3]], [[[4]]], [[[[5]]]]]
[1, [[[[2], 3]]], [[4]]] -> [1, [[4]], [[[3]]], [[[[2]]]]]

Perl, 52 bytes

Just a recursive subroutine. (unusual for a Perl answer, I know..)

sub f{say"@{[grep!ref,@_]}";@_&&f(map/A/?@$_:(),@_)}

Call it like that :

$ perl -E 'sub f{say"@{[grep!ref,@_]}";@_&&f(map/A/?@$_:(),@_)}f(1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9])'
1
2 3 9
4 7
5 6

8

Each line of the output corresponds to a depth level of the array (hence the empty line in the example above).

It can be turned into a full program for just a few more bytes : add -n flag and an eval (inside @{ } to transform the input into an array and not an arrayref) to transform the input into a Perl array :

perl -nE 'sub f{say"@{[grep!ref,@_]}";@_&&f(map/A/?@$_:(),@_)}f(@{+eval})' <<< "[1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]]"

My previous approach was slightly longer (65 bytes), but still interesting, so I'll let it here :

perl -nE '/\d/?push@{$;[$d-1]},$_:/]/?$d--:$d++for/\[|]|\d+/g;say"@$_"for@' <<< "[1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]]"


Solve the Magic Hexagon A magic hexagon is a hexagon where every row and every diagonal add up to the same value. In this case the value is 38. Each number from 1 to 19 must be used exactly once.

This image shows a solution but I want a program that derives this result.

Your challenge is to solve the magic hexagon as fast as possible. You must derive the result yourself, no hard-coding.


Dead code elimination Dead code sits there doing nothing, staring at us knowing it will never be executed... but today we can take revenge.
Specification
The input will be a multiline string.
Each line may either be an assignment or an expression .
Assignment
An assignment is of the form <name> = number where name is a sequence of letters, underscores and numbers, but not starting with a number.
Variables may be assigned any number of times.
Expression
An expression is of the form <var_name OR number> <operation> <var_name OR number> ...
An expression may be any combination of:

Variables already defined
Basic arithmetic operators +-*/
Numbers (integers)

Expected output
You should output the string with redundant assignments, assignments that are never used by any of the expressions following it, removed. Please note that assignments can also be made redundant if an additional assignment to the same variable is performed before an expression using the variable is executed.
Test cases
in
a = 10
a * 3

out
a = 10
a * 3

in
foo = 8
2 - 1
a = 18

out
2 - 1

in
a = 10
a = 8
b = 4
ab = 72
b / 6
b + 1

out
b = 4
b / 6
b + 1

in
a = 1
a = 2
a + 1

out
a = 2
a + 1

in
FooBar1 = 0
Fuz__ = 8
Fuz__ / 1

out
Fuz__ = 8
Fuz__ / 1

in
a = 1
a + 1
a = 2
a + 1

out
a = 1
a + 1
a = 2
a + 1

in
a = 1
1 / 5 * 8 + 4

out
1 / 5 * 8 + 4

in
a = 1
a + 1
a = 1
a + 1

out
a = 1
a + 1
a = 1
a + 1

in
a = 7
5 / a

out
a = 7
5 / a

PHP - 197 bytes

The function works by analysing each line, in the reverse order and one after the other, and maintaining an array of the used variables.

If there is an equal character = in the line, it's an assignment.

It the variable is used, the assignment is useful, and the line is printed, but the variable isn't considered used any more.
Otherwise, do nothing.

Otherwise, the line is an expression. We split the line after each space, and add each symbol to the list of used variables. Numbers (1, 2, …) and operators (+, -, …) will be added too, but since they aren't valid variables names, it's not a problem. The line is then of course printed.

function($c){$u=[];foreach(array_reverse(split('
',$c))as$l){if($p=strpos($l,'=')){if(!isset($u[$x=substr($l,0,$p-1)]))continue;
unset($u[$x]);}else$u+=array_flip(split(' ',$l));$f="
$l$f";}echo$f;}

Here is the ungolfed version:

function removeDeadCode($code)
{
    $usedVariables = [];
    $finalCode = '';

    foreach (array_reverse(explode("\n", $code)) as $line)
    {
        if ($equalPosition = strpos($line, '='))
        {
            $variable = substr($line, 0, $equalPosition - 1);
            if (isset($usedVariables[$variable]))
            {
                $finalCode = "\n" . $line . $finalCode;
                unset($usedVariables[$variable]);
            }
        }
        else
        {
            $usedVariables += array_flip(explode(' ', $line));
            $finalCode = "\n" . $line . $finalCode;
        }
    }

    echo $finalCode;
}


Lined up circle, n points Draw lines between every pair of distinct points for n points arranged in a circle, producing something like the below result. Shortest code (in bytes) wins! Your lines don't have to be transparent, but it looks better that way. The output must be a vector graphic, or be an image at least 600 pixels by 600 pixels (either saved to a file or displayed on the screen). To complete the challenge you must draw at least 20.

Mathematica, 13 bytes

CompleteGraph

Looks like this only fails to give a circular embedding for n=4, but the question states n>=20