title: Interlocking Brackets

text:
# Question
Title: Interlocking Brackets
Write a program or function that takes in an eight byte string containing one of each of the characters `()[]{}<>` arranged in any way such that the four respective bracket types match. For example, `]<([){}>` is invalid input because the square brackets don't match (though all the others do).

Print or return an integer from `0` to `6` that denotes how many of the six possible pairings of the four bracket types are interlocked. Bracket type pairs are considered interlocked if exactly one bracket of one type occurs between the brackets of the other type. So `([)]` and `[(])` are interlocked but `()[]`, `[]()`, `([])`, and `[()]` are not.

The shortest code in bytes wins.

**Input/Output Examples**

```
()[]{}<> : 0
([{<>}]) : 0
<>{[]}() : 0
{<>([])} : 0
<(>)[{}] : 1
<[({)}]> : 1
[{<}]>() : 2
{<>([}]) : 2
<{(>})[] : 3
[(]<){>} : 3
<([>{)}] : 4
(<{[>})] : 4
(<[{)>}] : 5
<{[(>})] : 5
[{<(]}>) : 6
(<{[)>}] : 6

```

# Answer
# CJam, 18

```
l7~f&_f{\/~;&}s,2/

```

Thanks isaacg for some golfing ideas :)
Try it online or try all examples

**Explanation:**

```
l         read a line of input
7~f&      clear the lowest 3 bits of each character
           the goal is to convert brackets of the same type to the same char
_         duplicate the resulting string, let's call it S
f{…}      for each character in S, and S (the char and S are pushed every time)
  \       swap the character with S
  /       split S around that character, resulting in 3 pieces:
           before, between, after
  ~       dump the pieces on the stack
  ;       pop the last piece
  &       intersect the first 2 pieces
          after the loop, we have an array of strings
          containing the chars interlocking to the left with each char of S
s         join all the string into one string
,         get the string length
2/        divide by 2, because S has duplicated characters

```
> 18 votes

# Answer
# Python 2, 163 bytes

```
def f(b,e='([{<)]}>',q=range(4)):
 b=[b[b.index(e[j])+1:b.index(e[j+4])]for j in q]
 print sum(sum(abs(b[k].count(e[j])-b[k].count(e[j+4]))for j in q)for k in q)/2

```

This looks at the stuff between each pair of matching brackets and counts the number of individual left or right brackets present. The sum of these divided by two is the output.

I'm sure it could be golfed a lot more by better golfers than me.
> 11 votes

# Answer
# GNU sed -r, 147

Output is in unary as per this meta-answer.

```
y/([{</)]}>/
s/.*/\t& & & & /
:b
y/)]}>/]}>)/
s/\S*>(\S*)>\S* /\1\t/
t
s/\S* //
:
s/(\t\S*)(\S)(\S*)\2(\S*\t)/\1\3\4/
t
s/\S *$/&/
tb
s/\s//g
s/../1/g

```

Note: Replace `\t` with actual `tab` characters to get the correct score. However, the program will work either way with GNU sed.

Try it online.
> 4 votes

# Answer
# Retina, ~~128~~ ~~108~~ ~~64~~ ~~62~~ 55 bytes

```
(T`)]>}`([<{
(\D)(.*)\1(.*)
\n$2\n$3
(?=(\D).*\n.*\1)
1
\n
<empty>

```

Where `<empty>` represents an empty trailing line. For counting purposes, put each line in a separate file, and replace the `\n` with actual linefeed characters. For convenience, you can use this equivalent code with the `-s` flag from a single file:

```
(T`)]>}`([<{
(\D)(.*)\1(.*)
#$2#$3
(?=(\D)[^#]*#[^#]*\1)
1
#
<empty>

```

Output is unary.

## Explanation

The first `(` tells Retina to execute the entire code in a loop until an iteration stops changing the string. In this case, it will always iterate four times, once for each bracket type.

```
T`)]>}`([<{

```

This simply turns each closing bracket into the corresponding opening bracket, so that we can match corresponding brackets with a simple backreference later on. (This stage becomes a no-op after the first iteration. It's only included in the loop, because the `T` already required a backtick, so adding `(` cost only one instead of two bytes.)

```
(\D)(.*)\1(.*)
\n$2\n$3

```

This replaces the left-most pair of brackets with newlines. We use `\D` to distinguish brackets from the `1`s we add later in the loop for counting. The `(.*)` at the end ensures that only one pair is replaced (because matches cannot overlap).

```
(?=(\D).*\n.*\1)
1

```

The entire regex is in a lookahead, so this matches a *position*. More specifically it matches one position for each pair of brackets which has been separated by the other brackets we just turned into newlines. A `1` is inserted into each of these positions. We can just leave the `1`s there, because they don't affect any of the other regexes (because the `\D`s ensure that we don't match them accidentally).

```
\n
<empty>

```

Finally, we remove the newlines (i.e. the placeholders for the current type of brackets) - this means that we've reduced the remaining problem to a string of length 6 containing only 3 types of brackets, but otherwise it works exactly the same.

At the end, only the `1`s we inserted will be left, and their amount corresponds exactly to the number of interlocking brackets.
> 3 votes

# Answer
# Perl, 77 bytes

76 code + 1 switch

```
perl -pe 'y/)]}>/([{</;for$x(/./g){$h{$x="\\$x"}++&&s!$x(.*)$x!$z+=length$1,$1!e}$_=$z'

```

Takes input from STDIN and the program must be started fresh for every input.

**Explanation**

1. Replace all closing brackets with their open counterparts (`y/.../.../`).
2. Then, for every character in the input string (`for$x...`), increment a counter for the character (`$h{$x}++`).
3. If this is the second time we're seeing the character, get the distance between the two occurances (`length $1`) and remove both occurances of this character from the string. For example, if the string was `([{([{<<`, there are two characters `[` and `{` between the two `(`s. After the `(`s are processed, the string becomes `[{[{<<` and we add 2 to the total number (`$z`) of interlocking brackets.
4. The result is taken from `$z` (`$_=$z`)
> 3 votes

# Answer
# Python 3, 107

```
t=0
s=""
for x in input():s+=chr(ord(x)&~7)
for x in s:a=s.split(x);t+=len(set(a[0])&set(a[1]))
print(t//2)

```

Loosely based on my CJam solution.
> 3 votes

# Answer
# Pyth, 20 bytes

```
JmC/CdTzlsm@FPcsJd{J

```

Test suite

`JmC/CdTz`: First, this converts each symbol pair to a single character by map each input character to its character code (`Cd`) divided by 10 (`/ T`), which is the same for each pair but different between all pairs. The resultant number is converted back into a character for purposes to be revealed later (`C`). The resultant list of characters is saved to `J`.

`lsm@FPcsJd{J`: Now, we map over the unique characters in `J` (`{J`). We start by chopping the string formed by concatenating `J` using the current character as the delimeter (`csJd`). A pair of brackets overlaps the current pair if it appears in the second group and either the first or third group. To avoid double counting, we'll just count the first and second group case. So, we remove the third group (`P`) and take the intersection of the remaining groups (`@F`). Finally, we concatenate the overlap characters (`s`) and print the length of the resut (`l`).
> 3 votes

# Answer
# JavaScript (ES7), ~~121~~ 117 bytes

```
x=>(a=b=0,[for(c of x)for(d of'1234')(e=c.charCodeAt()/26|0)==d?a^=1<<d:b^=(a>>d&1)<<d*4+e],f=y=>y&&y%2+f(y>>1))(b)/2

```

Wow. That was fun. I sketched out an answer idea when this challenge first came out, but it was over 150 bytes long and I didn't want to put in the effort to golf it. I ran across this idea in my notebook yesterday and decided I wouldn't stop thinking about it until I had fully golfed it. I ended up writing out two entirely new algorithms, the first of which ended up several bytes shorter after golfing off around 25 bytes with tons of bit-hacking.

### How it works

First we set variables `a` and `b` to `0`. `a` is a 4-bit binary array of which bracket pairs we are currently inside, and `b` is a 16-bit binary array of which bracket pairs are linked together.

Next, we loop through each character `c` in `x`, and each char `d` in `'0123'`. First we determine what type of bracket `c` is with `e=c.charCodeAt()/26-1|0`. The decimal char codes of each bracket type are as follows:

```
() => 40,41
<> => 60,62
[] => 91,93
{} => 123,125

```

By dividing by 26, subtracting 1, and flooring, we map these to 0, 1, 2, and 3, respectively.

Next we check if this number is equal to the current value of `d`. If it is, we are either entering or exiting the `d`th bracket type, so we flip the `d`th bit in `a` with `a^=1<<d`. If it's not, but we *are* inside the `d`th bracket type, we need to flip the `e`th bit in the `d`th 4-bit section of `b`. This is done like so:

```
b^=(a>>d&1)<<d*4+e

```

`(a>>d&1)` Returns the `d`th bit in `a`. If we are inside the `d`th bracket type, this returns 1; otherwise, it returns 0. Next, we shift this left by `d*4+e` bits, and XOR `b` by the result. If we are inside the `d`th bracket type, this XORs the `d*4+e`th bit of `b`; otherwise, it does nothing.

At the end of all the looping, `b` will contain a number of 1-bits equal to twice the desired return value. But we still need to figure out how many bits this is. That's where the sub-function `f` comes in:

```
f=y=>y&&y%2+f(y>>1)

```

If `y` is 0, this simply returns 0. Otherwise, it takes the last bit of `y` with `y%2`, then adds the result of running all but the last bit `y` through the function again. For example:

```
f(y)         => y && y%2 + f(y>>1)
f(0b1001101) =>       1  + f(0b100110) = 4
f(0b100110)  =>       0  + f(0b10011)  = 3
f(0b10011)   =>       1  + f(0b1001)   = 3
f(0b1001)    =>       1  + f(0b100)    = 2
f(0b100)     =>       0  + f(0b10)     = 1
f(0b10)      =>       0  + f(0b1)      = 1
f(0b1)       =>       1  + f(0b0)      = 1
f(0b0)       => 0                      = 0

```

We run `b` through this function and divide the result by 2, and there is our answer.
> 2 votes

# Answer
# Oracle SQL 11.2, 206 bytes

```
WITH v AS(SELECT b,MIN(p)i,MAX(p)a FROM(SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p FROM DUAL CONNECT BY LEVEL<9)GROUP BY b)SELECT COUNT(*)FROM v x,v y WHERE x.i<y.i AND x.a<y.a AND y.i<x.a;

```

Un-golfed :

```
WITH v AS( -- Compute min and max pos for each bracket type
           SELECT b,MIN(p)i,MAX(p)a
           FROM   ( -- replace ending brackets by opening brakets and split the string
                    SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p
                    FROM DUAL
                    CONNECT BY LEVEL<9
                  )
           GROUP BY b
         )
SELECT COUNT(*)
FROM   v x,v y
WHERE  x.i<y.i AND x.a<y.a AND y.i<x.a -- Apply restrictions for interlocking brackets

```
> 1 votes

---
Tags: code-golf, balanced-string
---


# Question
Title: Beat Pure Regular Expressions at Validating ISO 8601 Dates
In ValiDate ISO 8601 by RX, the challenge was to use only standard regular expressions to **validate standard date formats *and* values** (the former is a common job for RX, the latter was unusual). The winning answer used 778 bytes. This challenge is to beat that using any language of your choosing, but **without special date functions or classes**.

# Challenge

Find the shortest code that

1. validates every possible date in the *Proleptic* Gregorian calendar (which also applies to all dates before its first adoption in 1582),
2. does not match any invalid date and
3. does not use any predefined functions, methods, classes, modules or similar for handling dates (and times), i.e. relies on string and numeric operations.

## Output

Output is truthy or falsey. It’s not necessary to output or convert the date.

## Input

Input is a single string in any of 3 expanded ISO 8601 date formats – no times.

The first two are `±YYYY-MM-DD` (year, month, day) and `±YYYY-DDD` (year, day). Both need special-casing for the leap day. They are naively matched separately by these extended RXs:

```
(?<year>[+-]?\d{4,})-(?<month>\d\d)-(?<day>\d\d)
(?<year>[+-]?\d{4,})-(?<doy>\d{3})

```

The third input format is `±YYYY-wWW-D` (year, week, day). It is the complicated one because of the complex leap week pattern.

```
(?<year>[+-]?\d{4,})-W(?<week>\d\d)-(?<dow>\d)

```

# Conditions

A **leap year** in the Proleptic Gregorian calendar contains the **leap day** `…-02-29` and thus it is 366 days long, hence `…-366` exists. This happens in any year whose (possibly negative) ordinal number is divisible by 4, but not by 100 unless it’s also divisible by 400. **Year zero** exists in this calendar and it is a leap year.

A **long year** in the ISO week calendar contains a 53rd week `…-W53-…`, which one could term a “**leap week**”. This happens in all years where 1 January is a Thursday and additionally in all leap years where it’s a Wednesday. `0001-01-01` and `2001-01-01` are Mondays. It turns out to occur every 5 or 6 years usually, in a seemingly irregular pattern.

A year has at least 4 digits. Years with more than 10 digits do not have to be supported, because that’s close enough to the age of the universe (ca. 14 billion years). The leading plus sign is optional, although the actual standard suggests it should be required for years with more than 4 digits.

Partial or truncated dates, i.e. with less than day-precision, must not be accepted. Separating hyphens `-` are required in all cases. (These preconditions make it possible for leading `+` to be always optional.)

# Rules

This is code-golf. The shortest code in bytes wins. Earlier answer wins a tie.

# Test cases

## Valid tests

```
2015-08-10
2015-10-08
12015-08-10
-2015-08-10
+2015-08-10
0015-08-10
1582-10-10
2015-02-28
2016-02-29
2000-02-29
0000-02-29
-2000-02-29
-2016-02-29
+2016-02-29
200000-02-29
-200000-02-29
+200000-02-29
2016-366
2000-366
0000-366
-2000-366
-2016-366
+2016-366
2015-081
2015-W33-1
2015-W53-7
+2015-W53-7
+2015-W33-1
-2015-W33-1
 2015-08-10

```

The last one is optionally valid, i.e. leading and trailing spaces in input strings may be trimmed.

## Invalid formats

```
-0000-08-10     # that's an arbitrary decision
15-08-10        # year is at least 4 digits long
2015-8-10       # month (and day) is exactly two digits long, i.e. leading zero is required
015-08-10       # year is at least 4 digits long
20150810        # though a valid ISO format, we require separators; could also be interpreted as a 8-digit year
2015 08 10      # separator must be hyphen-minus
2015.08.10      # separator must be hyphen-minus
2015–08–10      # separator must be hyphen-minus
2015-0810
201508-10       # could be October in the year 201508
2015 - 08 - 10  # no internal spaces allowed
2015-w33-1      # letter ‘W’ must be uppercase
2015W33-1       # it would be unambiguous to omit the separator in front of a letter, but not in the standard
2015W331        # though a valid ISO format we require separators
2015-W331
2015-W33        # a valid ISO date, but we require day-precision
2015W33         # though a valid ISO format we require separators and day-precision
2015-08         # a valid ISO format, but we require day-precision
201508          # a valid but ambiguous ISO format
2015            # a valid ISO format, but we require day-precision

```

## Invalid dates

```
2015-00-10  # month range is 1–12
2015-13-10  # month range is 1–12
2015-08-00  # day range is 1–28 through 31
2015-08-32  # max. day range is 1–31
2015-04-31  # day range for April is 1–30
2015-02-30  # day range for February is 1–28 or 29
2015-02-29  # day range for common February is 1–28
2100-02-29  # most century years are non-leap
-2100-02-29 # most century years are non-leap
2015-000    # day range is 1–365 or 366
2015-366    # day range is 1–365 in common years
2016-367    # day range is 1–366 in leap years
2100-366    # most century years are non-leap
-2100-366   # most century years are non-leap
2015-W00-1  # week range is 1–52 or 53
2015-W54-1  # week range is 1–53 in long years
2016-W53-1  # week range is 1–52 in short years
2015-W33-0  # day range is 1–7
2015-W33-8  # day range is 1–7

```

# Answer
# JavaScript (ES6), 236

236 bytes allowing negative 0 year (`-0000`). Returns true or false

```
s=>!!([,y,w,d]=s.match(/^([+-]?\d{4,})(-W?\d\d)?(-\d{1,3})$/)||[],n=y%100==0&y%400!=0|y%4!=0,l=((l=y-1)+8-~(l/4)+~(l/100)-~(l/400))%7,l=l==5|l==4&!n,+d&&(-w?d>`0${2+n}0101001010`[~w]-32:w?(w=w.slice(2),w>0&w<(53+l)&d>-8):d[3]&&d>n-367))

```

Adding the check for negative 0 cut 2 bytes but adds 13. Note that in javascript the numeric value `-0` exists, and it is special cased to be equal to 0, but `1/-0` is `-Infinity`. This versione returns 0 or 1

```
s=>([,y,w,d]=s.match(/^([+-]?\d{4,})(-W?\d\d)?(-\d{1,3})$/)||[],n=y%100==0&y%400!=0|y%4!=0,l=((l=y-1)+8-~(l/4)+~(l/100)-~(l/400))%7,l=l==5|l==4&!n,+d&&(-w?d>`0${2+n}0101001010`[~w]-32:w?(w=w.slice(2),w>0&w<(53+l)&d>-8):d[3]&&d>n-367))&!(!+y&1/y<0)

```

**Test**

```
Check=
  s=>!! // to obtain a true/false
  (
    // parse year in y, middle part in w, day in d
    // day will be negative with 1 or 3 numeric digits and could be 0
    // week will be '-W' + 2 digits
    // month will be negative with2 digits and could be 0
    // if the date is in format yyyy-ddd, then w is empty
    [,y,w,d] = s.match(/^([+-]?\d{4,})(-W?\d\d)?(-\d{1,3})$/) || [],
    n = y%100==0 & y%400!=0 | y%4!=0, // n: not leap year
    l = ((l=y-1) + 8 -~(l/4) +~(l/100) -~(l/400)) % 7,
    l = l==5| l==4 & !n, // l: long year (see http://mathforum.org/library/drmath/view/55837.html)
    +d && ( // if d is not empty and not 0
     -w // if w is numeric and not 0, then it's the month (negative)
     ? d > `0${2+n}0101001010`[~w] - 32 // check month length (for leap year too)
      : w // if w is not empty, then it's the week ('-Wnn')
        ? ( w = w.slice(2), w > 0 & w < (53+l) & d >- 8) // check long year too
        : d[3] && d > n-367 // else d is the prog day, has to be 3 digits and < 367 o 366
    )
  )

console.log=x=>O.textContent += x +'\n'

OK=['1900-01-01','2015-08-10','2015-10-08','12015-08-10','-2015-08-10','+2015-08-10'
,'0015-08-10','1582-10-10','2015-02-28','2016-02-29','2000-02-29'
,'0000-02-29','-2000-02-29','-2016-02-29','+2016-02-29','200000-02-29'
,'-200000-02-29','+200000-02-29','2016-366','2000-366','0000-366'
,'-2000-366','-2016-366','+2016-366','2015-081','2015-W33-1'
,'2015-W53-7','+2015-W53-7','+2015-W33-1','-2015-W33-1','2015-08-10']

KO=['-0000-08-10','15-08-10','2015-8-10','015-08-10','20150810','2015 08 10'
,'2015.08.10','2015–08–10','2015-0810','201508-10','2015 - 08 - 10','2015-w33-1'
,'2015W33-1','2015W331','2015-W331','2015-W33','2015W33','2015-08','201508'
,'2015','2015-00-10','2015-13-10','2015-08-00','2015-08-32','2015-04-31'
,'2015-02-30','2015-02-29','2100-02-29','-2100-02-29','2015-000'
,'2015-366','2016-367','2100-366','-2100-366','2015-W00-1'
,'2015-W54-1','2016-W53-1','2015-W33-0','2015-W33-8']

console.log('Valid')
OK.forEach(x=>console.log(Check(x)+' '+x))
console.log('Not valid')
KO.forEach(x=>console.log(Check(x)+' '+x))
```

```
<pre id=O></pre>
```
> 2 votes

---
Tags: code-golf, date
---


title: What's being surrounded

text:
# Question
Title: What's being surrounded
I've always wanted to surround some text with `#`s, but I have trouble figuring out what I surrounded so in this challenge you'll be writing a program to do just that

## Examples

Input / Outputs are separated by a newline.

```
###
#a#
###

a

```

```
 #
#a#
 #

a

```

```
  ###
 # a #
# b c #
#######

  a
 b c

```

```
ABCDHIJ
E####GK
F# M #L
#   N#O
P####

  M
   N

```

```
###A###
#C#B#o#
#d###e#
 # go#
  ###

C   o
d   e
  go

```

## Spec

* `#`s are what "surround" a block of text
* `#` will always be adjacent to one another (including diagonally)
* `#` will always form a closed shape
* There will only be one `#` shape
* In the event of a concave shape, holes should be filled with spaces.

* Whitespace **must** be preserved in the output

# Answer
> 6 votes
# Perl, ~~144~~ ~~138~~ ~~132~~ ~~129~~ ~~128~~ ~~127~~ ~~126~~ 124 bytes

Includes +2 for `-p0`

The code assumes `\0` is not a valid input character (at least inside the `#`).

Run with the input on STDIN:

```
surround.pl < surround.txt

```

`surround.pl`:

```
#!/usr/bin/perl -p0
/^#[^#\0]/m&&s/^|[^#\n\0]\0/\0\0/mg,s%.%s/.(.*)/$+\0/g;/#/&&reverse"\n",/^./mg%seg until$?++<$$_++;y/\0/#/;s/^#*\n|#+$|^#//mg;y;#;

```

The code works as is, but replace the `\0` and `\n` by their literal versions for the claimed score. Notice there is a space  at the end of the line. The code loops way too many times, so you may have to wait 30 seconds or so for output.

## Explanation

I am going to do a floodfill with `\0` stopped by `#` from the outside in the orthogonal directions. After that I will slice off the `#` sides and replace all that is left by spaces. To avoid having to handle all directions in the floodfill I will repeatedly rotate the target area and only floodfill from right to left

```
/^#[^#\0]/m                   The rotation is written such that it slices
                              off the first column. That is ok unless the
                              first column contains a # that is followed by
                              something that could be the inside. There is
                              no newline inside the [] because short lines
                              will get extended during the rotation and
                              the character following the # will end
                              up as a \0 and match in a later round
    &&s/^|[^#\n\0]\0/\0\0/mg  In case the # could be an interior border I
                              will add two columns of \0's in front. One
                              will be a sacrifice for the rotation, the
                              other column will end up at the end of the area
                              after two rotations and function as seed for the
                              floodfill. This regex also does one step of
                              the floodfill from the back to the front.
                              After a certain number of loops we are certain
                              to get to a first column that must not be
                              dropped so at some point the last column is
                              guaranteed to consist of only \0. And we only need
                              to fill backward since the rotations will make
                              any direction backward at some point

s%.%  process column  %seg    I will replace each character (including \n)
                              in the string by the next column in reversed
                              order or an empty string if there are no more
                              interesting columns. This is therefore a right
                              rotation. There are less columns than
                              characters so this loop is long enough

    s%.%s/.(.*)/$+\0/g        Remove the next (now first) character from each
                              row (so remove the column). Because the
                              original area is not necessarily a rectangle
                              add a \0 at the end of the row so we won't run
                              out out of columns (this would cause shorter
                              rows to have no entry in the new rotated row)
                              This will not do anything for empty lines so
                              they DO get squeezed out. But that is not a
                              problem since the problem statement says there
                              will be only one # shape so any empty lines
                              are can be safely dropped (this would not be
                              so if there could be multiple # shapes because
                              that could create a new surrounded area

    /#/                       Check if any of the remaining columns still
                              has a #. If not all remaining columns are on
                              the outside and can be dropped
       &&reverse"\n",/^./mg   Collect the column and add a \n to its reverse

 until$?++<$$_++              Keep doing this until we get to a multiple of
                              65536 rotations when $? waraps back around to 0
                              (this is a multiple of 4 so the area is left
                              unrotated) and an area we have seen before
                              ($$_ >= 1)
                              (so all slicing and flood filling is finished)
                              $_ having been seen in a previous rotations is
                              not a problem (though rather tricky to prove)

```

At this point e.g.

```
AB##J
E####GK
F# M #L
#   N#O
P####

```

will have been replaced by:

```
0000000
0####00
0# M #0
#   N#0
0####00

```

Basically all columns and rows that are not directly bordering the inside have been sliced off. Any outside characters left has been replaced by \0. At the top and right there is an extra layer of \0. So all that is left is cleanup:

```
y/\0/#/                       Replace any outside that is left by #
s/^#*\n|#+$|^#//mg            Removes the first two and last line (the only
                              lines that can consist of purely #)
                              Removes any trailing #
                              Removes the first column of #
y;#; \n;                      Replace any remaining # by space since they
                              are needed to fill the concave parts
                              The final \n; is not written since it is implicit
                              in the -p loop

```

# Answer
> 4 votes
# Javascript, 485 464 427 417 396 390 bytes

```
s='indexOf';k='lastIndexOf';h="#";t=b=>b[0].map((x,i)=>b.map(x=>x[i]));i=>{m=i.split`
`;for(h of m){m[m[s](h)]=h.split``;}for(y=0;y<m.length;y++){for(z=x=0;x<m[y].length;x++){if(m[y][x]==h)break;if(m[y][s](h)<x&&m[y][k](h)>x)z++;q=t(m);if(q[y][s]h)<x&&m[y][k](h)>x)z++;if(z>2)m[y][x]=h}}for(p of m){v=p.join``.match(/\S/);e=v?p.join``:'';m[m[s](p)]=e;}m=m.join`
`;return m.replace(#/g," ")}
```

Yes. I tried. And, although I am at 485 bytes, I am winning because no-one else felt like answering this question. So, hah!
And also, I am well aware that I could golf this loads, I just am tired at the moment... **well now I'm at 396** Thanks to Conor for most of the golfing... :D

---
Tags: code-golf, string
---


title: Bracket balancing

text:
# Question
Title: Bracket balancing
You will be given a (possibly empty) string containing brackets (`[{()}]`) and any other characters (`A`-`Z`, `a`-`z`, `0`-`9`, punctuation). You need to check if it adheres to the following rules:

* Non-bracket characters are ignored.
* Every open bracket `[{(` has a closing bracket `)}]`. So `[](` is not allowed.
* Brackets are nested properly. `[(])` is not allowed.
* Curly brackets cannot contain square brackets within them. Simple brackets cannot contain either curly or square brackets within them. So `[({})]`, `[{[]}]` and `({})` are not allowed. Brackets can be nested with similar brackets, so `[[{((()))}{{(())}}]()]{()}` is allowed.

Output is a single truthy/falsey value as per your choice.

**Shortest code wins.**

---

**Test cases**

`b[[a{(/)}(())+={{}-}],]` -\> Valid

`([h][e][l][l][o])` -\> Invalid

`[///[{(\/(arg()))}1{{((-)-2)}}]()]{()}` -\> Valid

`hi` -\> Valid

# Answer
> 5 votes
## Retina, 84 bytes

```
^([^][}{)(]|()\(|(?<-2>)\)|(?!\2)((){|(?<-4>)}|(?!\4)(()\[|(?<-6>)])))*$(?!\2|\4|\6)

```

Try it online.

This is a fairly straight-forward (but golfed) extension of the basic parentheses-checking .NET regex.

While this is quite possible with balancing groups, Perl's recursion definitely has the edge here. However, either approach is beaten by ditching the elegance of a single regex match in favour of reducing the input gradually via repeated substitutions, as Digital Trauma's sed answer does. This can be implemented in 34 bytes in Retina, but I'm hesitant to post the code myself, as I didn't come up with the idea.

# Answer
> 5 votes
# Retina, 34

Firstly, credit where credit is due:

I independently (later) came up with the same approach in sed, so I hope I'm not treading on any toes (big or otherwise) by posting this:

```
[^][(){}]

+`\(\)

+`{}

+`\[]

^$

```

So now with a `sudo apt-get install mono-complete` and `git clone https://github.com/mbuettner/retina.git` I have a working retina on my Ubuntu VM. Here's the test output:

```
$ while read; do echo "Input: \"$REPLY\", Ouput: $( mono Retina.exe -s brbal.ret <<< "$REPLY" )" ; done < ../brbal.txt
Input: "[[{((()))}{{(())}}]()]{()}", Ouput: 1
Input: "b[[a{(/)}(())+={{}-}],]", Ouput: 1
Input: "[///[{(/(arg()))}1{{((-)-2)}}]()]{()}", Ouput: 1
Input: "hi", Ouput: 1
Input: "", Ouput: 1
Input: "", Ouput: 1
Input: "([h][e][l][l][o])", Ouput: 0
Input: "[](", Ouput: 0
Input: "[(])", Ouput: 0
Input: "[({})]", Ouput: 0
Input: "[{[]}]", Ouput: 0
Input: "({})", Ouput: 0
$

```

# Answer
> 3 votes
# , 43 chars / 62 bytes

```
!Մ(Մ(Մ(ïċ/⁅⬮[\]{}]⌿),`⬮`,⬯),`{}`,⬯),`[]`,⬯)

```

`Try it here (Firefox only).`

Nope.

---

However, if I use newly implemented features, I can get down to 28 chars / 47 bytes:

```
!ïċ/⁅⬮[\]{}]⌿)ė`⬮”ė`{}”ė`[]”

```

# Answer
> 3 votes
# Sed, 53

```
s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc

```

Here I am claiming that since `sed` does not really have a concept of truthy/falsey, then I am defining the empty string to mean truthy and all other strings to mean falsey.

If that is not acceptable, then we can add a couple of lines, thus:

# Sed, 66

```
s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc
/./c0
/^$/c1

```

This outputs 0 for false and 1 for true.

# Answer
> 3 votes
# CJam, ~~27~~ 26 bytes

```
"(){}[]"q1$f&_,@2/e*{/s}/!

```

This prints **1** (truthy) or **0** (falsy). Try it online! or verify all test cases.

### How it works

```
"(){}[]"                    Push that string.
        q                   Read all input and push it on the stack.
         1$                 Copy the bracket string.
           f&               Intersect each input character with the bracket string.
                            This pushes an array of singleton and empty strings.
             _,             Get the length of the array (L), i.e., the number of
                            characters in the original input.
               @            Rotate the bracket string on top of the stack.
                2/          Split it into ["()" "{}" "[]"].
                  e*        Repeat each character pair L times.
                    {  }/   For each character pair.
                     /      Split the string on the stack at occurrences of that
                            character pair. This dosn't work properly the first
                            time, since there's a string array on the stack.
                      s     Flatten the resulting array of strings.
                         !  Apply logical NOT.

```

# Answer
> 2 votes
# Japt, ~~42~~ 37 bytes

*Saved 5 bytes with a feature I didn't realize my own language had... Thanks for adding it, @Downgoat!*

Japt really needs better RegExp support...

```
!Uo"()[\\]\{}" e"\\(\\)" e"\{}" e"\\[]

```

Try it online!

### How it works

```
               // Implicit: U = input string
Uo"()[\\]\{}"  // Remove all non-bracket.
e"\\(\\)"      // Recursively remove all pairs of simple brackets.
e"\{}"         // Recursively remove all pairs of curly brackets.
e"\\[]         // Recursively remove all pairs of square brackets.
!              // Return the Boolean NOT of the result.
               // (true for empty string, false for anything else)
               // Implicit: output last expression

```

# Answer
> 2 votes
# C99, ~~226~~ ~~208~~ 207 Bytes

This is my first time ever trying to golf something

```
#define S s[i]
t(s,i)char*s;{int a[]={['[']=0,['{']=0,['(']=0};for(i=0;S*!(S=='{'&a['(']|S=='['&(a['(']|a['{'])|S==']'&(a['(']|a['{'])|S=='}'&a['(']);i++)a[S]++,a[S-S/90-1]--;return !(a['[']+a['{']+a['(']);}

```

Readable:

```
int t(char* s){
    int a[265]={['[']=0,['{']=0,['(']=0};
    for(int i=0;s[i]&&!((s[i]=='{'&a['(']>0)|(s[i]=='['&(a['(']>0|a['{']>0))|(s[i]==']'&(a['(']>0|a['{']>0))|(s[i]=='}'&a['(']>0));i++){
        a[s[i]]++;
        a[s[i]-(s[i]/90+1)]--;
    }
    return !(a['[']+a['{']+a['(']);
}

```

There is a buffer overflow but it doesnt seem to affect anything - I believe this is due to alignment.

# Answer
> 1 votes
# Python 3, ~~196~~ ~~170~~ ~~160~~ 154 bytes

Awkwardly long, thanks to Mego for saving 6 bytes:

```
d=y=""
for C in input():
 for a in "[](){}":y+=C*(C==a)
 y=y.replace("()",d)
x=y
for r in y:x=x.replace("{}",d)
for s in y:x=x.replace("[]",d)
print(x==d)

```

# Answer
> 1 votes
## Perl, 50 + 1 = 51 bytes

```
$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/

```

Requires the `-p` flag and prints `1` for truthy and nothing for falsy results. I'm counting `-p` as one, because it can be combined with `-e`:

```
> perl -pe '$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/'

```

The code is basically just a plain regex match against the input, using Perl's nifty recursive regex feature.

Thanks to Dennis for helping me test this and golf the Perl boilerplate.

# Answer
> 1 votes
# Python 3 : 120 bytes

Building on @Adnan's answer, re proved shorter to use:

```
import re
x=re.sub('[^[\](){}]','',input())
for i in('()','{}','[]'):
 while x.find(i)>=0:x=x.replace(i,'')
print(x=='')

```

---
Tags: code-golf, string, decision-problem, balanced-string
---


title: Create a pie chart

text:
# Question
Title: Create a pie chart
The challenge is simple:

**Create a pie-chart based on a number of input values.**

The input will be a list of positive numbers, decimal or integers, and the output will be a pie-chart where each of the input values are represented by separate colors, and a percentage value outside each of the areas.

**Rules:**

* The colors must be visually distinguishable (the exact colors are optional)
* There will be at least two, and maximum 10 input values
* The radius of the circle must be in the range `[100 300]` pixels
    + Vector graphics are OK as long as the default output gives a radius of `[100, 300]` pixels
* The percentage values shall be integers
    + There is no strict rule saying where the percentage value shall be placed, but it must be easily seen which area it belongs to
    + The distance between the closest character and the outer edge of the circle must be in the range `[5, 40]` pixels
    + The font is optional
* The plot may or may not have black lines separating each region
* Functions made for creating pie charts, for instance, MATLAB: `pie`, Python: `matplotlib.pyplot.pie` and Mathematica: `PieChart` are not allowed
* Normal rounding rules (up if it's `(1.00, 0.5]`, down if it's `(0.5, 0.00)`)
* If the percentage value of a slice is smaller than `0.5%`, output `0%`. The slice must still be included in the plot.
* Please provide plots for examination (or a link to an interpreter). It's enough to show only the plot with 10 input values (to avoid very long answers)

**Examples**

Please use the example values below. You can convert the lists to an appropriate format using a numeric list converter, for instance this 27 byte one by jimmy23013.

```
x = [0.3, 1.2]

```

```
x = [3, 6, 2, 10]

```

```
x = [0.4387, 0.3816, 0.7655, 0.7952, 0.1869, 0.4898, 0.4456, 0.6463, 0.7094, 0.7547]

```

# Answer
> 12 votes
# Mathematica, ~~186~~ ~~183~~ 164 bytes

```
Graphics[{Hue@#,Disk[{0,0},{1,1},a=2Pi{##}],Black,Text[ToString@Round[100(#2-#)]<>"%",5Through@{Cos,Sin}@Mean@a/4]}&@@@Partition[Accumulate[#/Tr@#]~Prepend~0,2,1]]&

```

Could be golfed further. Currently generates a `Graphics` object. Test cases:

---

---

# Answer
> 7 votes
# JavaScript (ES6), ~~311~~ ~~310~~ ~~302~~ 298 bytes

```
a=>{with(Math)document.write(`<svg height=300>`+a.map(n=>`<path fill=#${(p*4e3|0).toString(16)} d=M135,150L${c(o=100,v=0)}A${[o,o,0,(v=n/=s)+.5|0,0,c(o)]}Z /><text x=${(z=c(135,v/=2))[0]} y=${z[p+=n,1]}>${n*o+.5|0}%</text>`,c=r=>[sin(d=PI*2*(v+p))*r+135,cos(d)*r+150],p=s=0,a.map(n=>s+=n)).join``)}

```

*Saved a byte with help from @Neil!*

## Explanation

Writes some SVG to the HTML of the current page. Builds the chart with centre point `135 x 150` of radius `100px` and text at a radius of `135px` from the centre.

```
var solution =

a=>{
  with(Math)
  document.write(       // write to HTML body
    `<svg height=300>`+ // create 300px x 300px SVG canvas (width defaults to 300px)
    a.map(n=>           // for each number

      // Get the hex colour by multiplying the current position by (roughly) 0xfff
      `<path fill=#${(p*4e3|0).toString(16)

      // Calculate the path of the pie slice
      } d=M135,150L${c(o=100,v=0)}A${[o,o,0,(v=n/=s)+.5|0,0,c(o)]

      // Text
      }Z /><text x=${(z=c(135,v/=2))[0]} y=${z[p+=n,1]}>${n*o+.5|0}%</text>`,

      // Returns [ x, y ] for a certain radius at position v around the pie
      c=r=>[sin(d=PI*2*(v+p))*r+135,cos(d)*r+150],
      p=s=0,             // p = current position around pie (0 - 1)
      a.map(n=>s+=n)     // s = sum of all numbers
    ).join``

    +`</svg>` // <- this is just here for the test, so multiple charts can be displayed
  )
}

// Test
;[
  [0.3, 1.2],
  [3, 6, 2, 10],
  [0.4387, 0.3816, 0.7655, 0.7952, 0.1869, 0.4898, 0.4456, 0.6463, 0.7094, 0.7547]
].map(c=>solution(c));
```

# Answer
> 6 votes
# Python + PIL, ~~365~~ 355

```
from math import*;from random import*
from PIL import Image,ImageDraw
L,a,r=256,0,0.8;l,p,c=L/2,L/6,(L,L,L);I=Image.new('RGB',(L,L),c);D=ImageDraw.Draw(I)
x=input()
for i in x:b=a+ceil(360.0*i/sum(x));D.pieslice((p,p,L-p,L-p),int(a),int(b),tuple(map(randrange,c)));t=(a+b)*0.00872;D.text((l+cos(t)*l*r,l+sin(t)*l*r),str(int((b-a)/3.6))+'%',0);a=b
I.show()

```

Result for the largest example list :

---
Tags: code-golf, graphical-output
---


title: What's the voltage over each component?

text:
# Question
Title: What's the voltage over each component?
The picture below shows a RLC circuit. A RLC circuit is an electrical circuit consisting of a resistor (R), an inductor (L), and a capacitor (C), connected in series or in parallel. (1)

In order to simplify computations, it's common to work in the frequency (Laplace) domain instead of the time domain.

Your task is:

**Take the values `R`, `L` and `C` as input, and return the voltages `VR`, `VL` and `VC`**

The conversion to the Laplace domain is as follows:

```
R = R
XL = j*w*L      // OK, XL = w*L, and ZL = j*XL, but don't mind this here.
XC = 1/(j*w*C)  // I haven't ruined physics, it's only a minor terminology tweak

```

where `j = sqrt(-1)`, and `w = 2*pi*50` (The frequency is 50 Hz).

The combined impedance, when the components are in series is `Z = R + XL + XC`. You might remember `U = R*I` from high school physics lectures. It's almost the same, but a bit more *complex* now: `VS = Z*I`. The current is calculated by dividing the voltage `VS` by the total impedance `Z`. To find the voltage over a single component, you need to know the current, then multiply it by the impedance. For simplicity, the voltage is assumed to be `VS = 1+0*j`.

Equations you might need are:

```
XL = j*w*L
XC = 1/(j*w*C)
Z = R + XL + XC   // The combined impedance of the circuit
I = VS / Z         // The current I (Voltage divided by impedance)
VR = I * R        // Voltage over resistance (Current times resistance)
VL = I * XL       // Voltage over inductor (Current times impedance)
VC = I * XC       // Voltage over capacitor (Current times impedance)

```

The input is from either STDIN or as function arguments. The output/result must be three complex numbers, in a list, string or whatever is most practical in your language. It's not necessary to include names (ex `VR = ...`), as long as the results are in the same order as below. The precision has to be at least 3 decimal points for both the real and imaginary part. The input and output/results can be in scientific notation if that's default in your language.

`R` and `L` are `>= 0`, and `C > 0`. `R, L, C <= inf` (or the highest possible number in your language).

A simple test case:

```
R = 1, L = 1, C = 0.00001

VR = 0.0549 + 0.2277i
VL = -71.5372 +17.2353i
VC = 72.4824 -17.4630i

```

For the results above, this could be one (of many) valid ouput format:

```
(0.0549 + 0.2277i, -71.5372 +17.2353i, 72.4824 -17.4630i)

```

Some valid ouput formats for one voltage value are:

```
1.234+i1.234,   1.23456+1.23456i,   1.2345+i*1.2345,   1.234e001+j*1.234e001.

```

This list is not exclusive, so other variants can be used, as long as the imaginary part is indicated by an `i` or a `j` (common in electrical engineering as `i` is used for current).

To verify the result for other values of R,L and C, the following must be true for all results: `VR + VL + VC = 1`.

The shortest code in bytes win!

By the way: Yes, it's voltage *over* a component, and current *through* a component. A voltage has never gone through anything. =)

# Answer
# Pyth, 30 29 28 bytes

```
L*vw*100.l_1)K[Qy0c1y1)cRsKK

```

Try it online.
> 7 votes

# Answer
# Mathematica, 33 bytes

*So* close to Pyth...

```
l/Tr[l={#,#2(x=100Pi*I),1/x/#3}]&

```

This is an unnamed function, which takes `R`, `L` and `C` as its three arguments and returns a list of complex numbers as the result (in the required order `VR`, `VL`, `VC`). Example usage:

```
l/Tr[l={#,#2(x=100Pi*I),1/x/#3}]&[1, 1, 0.00001]
(* {0.0548617 + 0.22771 I, -71.5372 + 17.2353 I, 72.4824 - 17.463 I} *)

```
> 9 votes

# Answer
# Octave / Matlab, ~~53~~ 51 bytes

```
function f(R,L,C)
k=-.01j/pi;Z=[R L/k k/C];Z/sum(Z)

```

Try it online

Thanks to @StewieGriffin for removing two bytes.
> 3 votes

# Answer
# APL (Dyalog Unicode), ~~27~~ 24 bytesSBCS

Full program. Prompts for `C`, `L`, `R` in that order.

```
(⊢÷+/)(⎕,⎕∘÷,÷∘⎕)÷○0J100

```

Try it online!

`0J100` 100 *i*

π times that

`÷` reciprocal of that

`(``)` apply the following tacit function:

`÷∘⎕` divide the argument by input (`C`)

`⎕∘÷,` prepend input (`L`) divided by the argument

`⎕,` prepend input (`R`)

`(``)` apply the following tacit function:

`+/` sum the arguments

`⊢÷` divide the arguments by that
> 3 votes

# Answer
# Octave, 41 bytes

```
@(R,L,C)(Z=[R L/(k=-.01j/pi) k/C])/sum(Z)

```

`1/(100*j*pi)` can be shortened to `-.01j/pi` which is a lot shorter. By assigning it to the variable `k` inline, the variable can be used twice. Assigning the entire vector to the variable `Z` costs 4 bytes, but allows us to divide by `sum(Z)`, which is 5 bytes shorter than `(R+L/k+k/C)`.
> 2 votes

---
Tags: code-golf, complex-numbers, electrical-engineering, physics
---


# Question
Title: Where will the cat go? (orbital mechanics)
A nearly massless cat is dropped in space (don't worry, with a space suit and everything) at the point `(x, y, z)` with velocity `(vx, vy, vz)`. There is an fixed, infinitely dense planet (with volume of 0) at the point `(0, 0, 0)` and it attracts objects at distance `r` with acceleration `1/r^2`. According to Newtonian gravity, where does the object go after time `t`?

Nearly massless in this case means you are outputting the value of `lim (mass --> 0) <position of cat>`. The mass is affected by the planet's gravity, but the planet is not affected by the cat's gravity. In other words, the central body is fixed.

This is somewhat similar to Code Golf: What is the spaceship's fate? \[floating point version\], but this is different because it is measuring accuracy.

You may implement a solution based on a simulation, which must run in less than 3 seconds, OR you may implement a program that gives an exact value (must also run in less than 3 seconds). See scoring details below. If you implement a simulation, it does not have to be exact, but your score will be lower because of the inaccuracy.

**Input**: `x y z vx vy vz t`, not necessarily integers representing x, y, z coordinates, velocity in the x, y, and z directions and time respectively. It is guaranteed that the speed of the cat is strictly less than the escape velocity at that altitude. Input may be taken from anywhere, including parameters to a function. The program must run in less than three seconds on my laptop for `t < 2^30`, which means, if you are running a simulation, you must adjust your timestep accordingly. If you are planning on hitting the 3 second limit for every test case, make sure there is a tuneable parameter that can make it more accurate/less accurate for speed gains, so that I can make it run in three seconds on my computer.

**Output**: `x y z`, the position after time `t`.

Since the two-body problem can be solved perfectly, it is in theory possible to get a perfect, correct answer.

**Scoring**: For any test case, the error is defined to be the distance between your output and the "true" output. The true output is defined to be the one that the test case snippet generates. If the error is less than `10^(-8)`, the error is rounded down to zero. Your score is the average error on 100 (or more) random test cases. If you write a perfectly accurate answer, you should get a score of 0; lowest score wins, and ties will be broken by code length.

**Test cases**:

```
1 0 0 0 -1 0 1000000000 --> 0.83789 -0.54584 0

```

In this case , the orbit is perfectly circular with period 2\*pi, so after circling 159154943 times, the cat ends up at approximately (0.83789, -0.54584). This isn't a test case your code will be tested on; if you submit a perfectly accurate answer, however, you may want to test it on this.

The snippet below generates random additional test cases and will be used to judge submissions; let me know if there is a bug with this:

```
var generateTestCase = function() {
  var periapsis = Math.random() * 10 + 0.5;
  var circularVelocity = Math.sqrt(1 / periapsis);
  var escapeVelocity = Math.sqrt(2) * circularVelocity;
  var v = Math.random() * (escapeVelocity - circularVelocity) + circularVelocity;
  var a = 1 / (2 / periapsis - v * v);
  var ecc = (a - periapsis) * (2 / periapsis - v * v);
  var semiLatus = a * (1 - ecc * ecc);
  var angM = Math.sqrt(semiLatus);
  var period = 2 * Math.PI * a * Math.sqrt(a);
  var getCoordAfterTime = function(t) {
    var meanAnomaly = t / (a * Math.sqrt(a));

    function E(e, M, n) {
      var result = M;
      for (var k = 1; k <= n; ++k) result = M + e * Math.sin(result);
      return result;
    }
    var eAnomaly = E(ecc, meanAnomaly, 10000);
    var radius = a * (1 - ecc * Math.cos(eAnomaly));
    var theta = Math.acos((semiLatus / radius - 1) / ecc);
    if (t > period / 2) theta = -theta;
    return {
      r: radius,
      t: theta,
      x: radius * Math.cos(theta),
      y: radius * Math.sin(theta)
    };
  }
  var t1 = Math.random() * period;
  var p1 = getCoordAfterTime(t1);
  var v1 = Math.sqrt(2 / p1.r - 1 / a);
  var velocityAngle1 = Math.acos(angM / p1.r / v1);
  var horizontal = Math.atan(-p1.x / p1.y);
  if (t1 < period / 2) {
    velocityAngle1 *= -1;
    horizontal += Math.PI;
  }
  var vx = v1 * Math.cos(horizontal + velocityAngle1);
  var vy = v1 * Math.sin(horizontal + velocityAngle1);
  var t2 = Math.random() * period;
  var p2 = getCoordAfterTime(t2);
  var v2 = Math.sqrt(2 / p2.r - 1 / a);
  var dummyPeriods = Math.floor(Math.random() * 100) * period + period;
  var rotate = function(x, y, z, th1, th2, th3) {
    var x1 = x * Math.cos(th1) - y * Math.sin(th1);
    var y1 = x * Math.sin(th1) + y * Math.cos(th1);
    var z1 = z;
    var x2 = x1 * Math.cos(th2) + z1 * Math.sin(th2);
    var y2 = y1;
    var z2 = -x1 * Math.sin(th2) + z1 * Math.cos(th2);
    var x3 = x2;
    var y3 = y2 * Math.cos(th3) - z2 * Math.sin(th3);
    var z3 = y2 * Math.sin(th3) + z2 * Math.cos(th3);
    return [x3, y3, z3];
  }
  var th1 = Math.random() * Math.PI * 2,
    th2 = Math.random() * 2 * Math.PI,
    th3 = Math.random() * 2 * Math.PI;
  var input = rotate(p1.x, p1.y, 0, th1, th2, th3)
    .concat(rotate(vx, vy, 0, th1, th2, th3))
    .concat([t2 - t1 + dummyPeriods]);
  var output = rotate(p2.x, p2.y, 0, th1, th2, th3);
  return input.join(" ") + " --> " + output.join(" ");
}
var $ = function(x) {
  return document.querySelector(x);
}
$("#onetestcase").onclick = function() {
  $("#result1").innerHTML = generateTestCase();
}
$("#huntestcases").onclick = function() {
  var result = [];
  for (var i = 0; i < 100; ++i) result.push(generateTestCase());
  $("#result100").innerHTML = result.join("\n");
}
```

```
<div>
  <button id="onetestcase">Generate</button>
  <pre id="result1"></pre>
</div>
<div>
  <button id="huntestcases">Generate 100 test cases</button>
  <pre id="result100"></pre>
</div>
```

# Answer
# Python 3.5 + NumPy, exact, 186 bytes

```
from math import*
def o(r,v,t):
 d=(r@r)**.5;W=2/d-v@v;U=W**1.5;b=[0,t*U+9]
 while 1:
  a=sum(b)/2;x=1-cos(a);y=sin(a)/U;k=r@v*x/W+d*y*W
  if a in b:return k*v-r*x/W/d+r
  b[k+a/U-y>t]=a

```

This is an exact solution, using a formula I engineered based on Jesper Göranssonhis, “Symmetries of the Kepler problem”, 2015. It uses a binary search to solve the transcendental equation Ax + B cos x + C sin x = D, which has no closed-form solution.

The function expects the position and velocity to be passed in as NumPy arrays:

```
>>> from numpy import array
>>> o(array([1,0,0]),array([0,-1,0]),1000000000)
array([ 0.83788718, -0.54584345,  0.        ])
>>> o(array([-1.1740058273269156,8.413493259550673,0.41996042044140003]),array([0.150014367067652,-0.09438816345868332,0.37294941703455975]),7999.348650387233)
array([-4.45269544,  6.93224929, -9.27292488])

```
> 6 votes

# Answer
# Javascript

This is just to get the ball rolling, since no one seems to be posting answers. Here is a very naive, simple way that can be improved a lot:

```
function simulate(x, y, z, vx, vy, vz, t) {
  var loops = 1884955; // tune this parameter
  var timestep = t / loops;
  for (var i = 0; i < t; i += timestep) {
    var distanceSq = x*x + y*y + z*z; // distance squared from origin
    var distance = Math.sqrt(distanceSq);
    var forceMag = 1/distanceSq; // get the force of gravity
    var forceX = -x / distance * forceMag;
    var forceY = -y / distance * forceMag;
    var forceZ = -z / distance * forceMag;
    vx += forceX * timestep;
    vy += forceY * timestep;
    vz += forceZ * timestep;
    x += vx * timestep;
    y += vy * timestep;
    z += vz * timestep;
  }
  return [x, y, z];
}

```

Testing:

```
simulate(1, 0, 0, 0, -1, 0, Math.PI*2) --> [0.9999999999889703, -0.0000033332840909716455, 0]

```

Hey, that's pretty good. It has an error of about 3.333\*10^(-6) which isn't enough for it to be rounded down... it's close.

Just for fun:

```
console.log(simulate(1, 0, 0, 0, -1, 0, 1000000000))
--> [-530516643639.4616, -1000000000.0066016, 0]

```

Oh well; so it's not the best.

And on a random test case from the generator:

```
simulate(-1.1740058273269156,8.413493259550673,0.41996042044140003,0.150014367067652,-0.09438816345868332,0.37294941703455975,7999.348650387233)
-->    [-4.528366392498373, 6.780385554803544, -9.547824236472668]
Actual:[-4.452695438880813, 6.932249293597744, -9.272924876103785]

```

With an error of only approximately 0.32305!

This can be improved a lot by using something like Verlet integration or some fancy algorithm. In fact, those algorithms may even get perfect scores, despite being simulations.
> 2 votes

---
Tags: code-challenge, math
---


title: Generate the minimal remainder sequence

text:
# Question
Title: Generate the minimal remainder sequence
Every number can be represented using an infinitely long remainder sequence. For example, if we take the number 7, and perform `7mod2`, then `7mod3`, then `7mod4`, and so on, we get `1,1,3,2,1,0,7,7,7,7,....`.

However, we need the *shortest* possible remainder subsequence that can still be used to distinguish it from all lower numbers. Using 7 again, `[1,1,3]` is the shortest subsequence, because all of the previous subsequences don't start with `[1,1,3]`:

```
0: 0,0,0,0...
1: 1,1,1,1...
2: 0,2,2,2...
3: 1,0,3,3...
4: 0,1,0,4...
5: 1,2,1,0...
6: 0,0,2,1...

```

Note that `[1,1]` *doesn't* work to represent 7, because it can also be used to represent 1. However, you should output `[1]` with an input of 1.

# Input/Output

Your input is a non-negative integer. You must output a sequence or list of the minimal-length sequence of remainders as defined above.

# Test cases:

```
0: 0
1: 1
2: 0,2
3: 1,0
4: 0,1
5: 1,2
6: 0,0,2
7: 1,1,3
8: 0,2,0
9: 1,0,1
10: 0,1,2
11: 1,2,3
12: 0,0,0,2
30: 0,0,2,0
42: 0,0,2,2
59: 1,2,3,4
60: 0,0,0,0,0,4
257: 1,2,1,2,5,5
566: 0,2,2,1,2,6,6
1000: 0,1,0,0,4,6,0,1
9998: 0,2,2,3,2,2,6,8,8,10
9999: 1,0,3,4,3,3,7,0,9,0

```

Here are the first 10,000 sequences, in case you are interested (the line numbers are off by 1).

This is a , so make it as short as you can in your favorite language. Fake bonus points for any answers that are fast!

# Answer
# Jelly, 14 bytes

```
‘Ræl\>iṠ2»2r⁸%

```

This uses the fact a the solution (if any) of a system of linear congruences is unique modulo the LCM of the moduli. Try it online! or verify all test cases.

### How it works

```
‘Ræl\>iṠ2»2r⁸%  Main link. Argument: n

‘               Increment; yield n+1.
 R              Range; yield [1, ..., n+1].
  æl\           Cumulatively reduce by LCM.
                This yields [LCM(1), ..., LCM(1, ..., n+1)].
     >          Compare all LCMs with n.
      iṠ        Find the first index of sign(n).
                This yields the first m such that LCM(2, ..., m) > n if n > 0, and
                0 if n == 0.
        2»      Take the maximum of the previous result and 2, mapping 0 to 2.
          2r    Yield the range from 2 up to and including the maximum.
            ⁸%  Compute n modulo each integer in that range.

```
> 6 votes

# Answer
## Mathematica, ~~60~~ 53 bytes

```
#~Mod~FirstCase[2~Range~#&/@Range[#+2],x_/;LCM@@x>#]&

```

*Somewhat* fast (it handles 10000 in ~0.1 second, but will likely run out of memory for 100000).

The code throws an error but computes the result correctly.

### Explanation

We've found earlier in chat that the required divisors can always be determined as the shortest list `{1, 2, ..., n}` whose least common multiple exceeds the input. A short argument for why that is: if the LCM is less than the input, then subtracting the LCM from the input would leave all the divisors unchanged, so the representation is not unique. However, for all inputs less than the LCM, the remainders will be unique, otherwise the difference between two numbers with equal remainders would be a smaller multiple of all divisors.

As for the code... as usual the reading order of golfed Mathematica is a bit funny.

```
Range[#+2]

```

This gets us a list `[1, 2, 3, ..., n+2]` for input `n`. The `+2` is to ensure that it works correctly for `0` and `1`.

```
2~Range~#&/@...

```

Map `2~Range~#` (syntactic sugar for `Range[2,#]`) over this list, so we get

```
{{}, {2}, {2,3}, ..., {2,3,...,n+2}}

```

These are candidate divisor lists (of course in general that's a lot more than we'll need). Now we find the first one of them whose LCM exceeds the input with:

```
FirstCase[...,x_/;LCM@@x>#]

```

More syntax: `x_` is a pattern which matches any of the lists and calls it `x`. The `/;` attaches a condition to that pattern. This condition is `LCM@@x>#` where `@@` *applies* the function to the list, i.e. `LCM@@{1,2,3}` means `LCM[1,2,3]`.

Finally we simply get all the remainders, making use of the fact that `Mod` is `Listable`, i.e. it automatically maps over a list if one of the arguments is a list (or if both of them are lists of the same length):

```
#~Mod~...

```
> 5 votes

# Answer
# MATL, 24 bytes

*Thanks to @nimi for pointing out an error in a previous version of this answer (now corrected)*

```
Q:qtQ!\t0Z)tb=YpsSP2):Q)

```

This runs out of memory in the online compiler for the two largest test cases (but it works on a computer with 4 GB RAM).

**Try it online!**

### Explanation

This applies the definition in a straightforward manner. For input `n` it computes a 2D array containing `mod(p,q)` with `p` from `0` to `n` and `q` from `1` to `n+1`. Each `p` is a column, and each `q` is a row. For example, with input `n=7` this array is

```
0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1
0 1 2 0 1 2 0 1
0 1 2 3 0 1 2 3
0 1 2 3 4 0 1 2
0 1 2 3 4 5 0 1
0 1 2 3 4 5 6 0
0 1 2 3 4 5 6 7

```

Now the last column, which contains the remainders of `n`, is element-wise compared with each column of this array. This yields

```
1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1
0 1 0 0 1 0 0 1
0 0 0 1 0 0 0 1
0 0 1 0 0 0 0 1
0 1 0 0 0 0 0 1
1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1

```

where `1` indicates equality. The last column is obviously equal to itself and thus contains all ones. We need to find the column that has the *largest number of initial ones*, other than the last column, and take note of that number of initial ones, `m`. (In this case it's the second column, which contains `m=3` initial ones). To this end, we compute the cumulative product of each column:

```
1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1
0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1

```

then the sum of each column

```
1 3 1 2 1 2 1 8

```

and then sort non-increasingly and take the second value, which is `3`. This is the desired `m`, which indicates how many remainders we need to pick.

```
Q:q    % take input n implicitly. Generare row array [0 1 ... n]
tQ!    % duplicate. Transform into column array [1; 2; ...; n-1]
\      % modulo, element-wise with broadcast. Gives the 2D array
t0Z)   % duplicate. Take last column
tb     % duplicate, bubble up
=      % test for equality, element-wise with broadcast
Yp     % cumumative product of each column
s      % sum of each column. This gives the number of initial coincidences
SP2)   % sort in decreasing order and take second value: m
:Q     % generate range [2 3 ... m+1]
)      % apply as index into array of remainders of n. Implicitly display

```
> 5 votes

# Answer
# Jelly, ~~13~~ 11 bytes

```
r¬µ%€R‘$ḟ/Ṫ

```

This won't win any velocity brownie points... Try it online! or verify the smaller test cases.

### How it works

```
r¬µ%€R‘$ḟ/Ṫ  Main link. Argument: n

r¬           Range from n to (not n).
             This yields [n, ..., 0] if n > 0 and [0, 1] otherwise.

  µ          Begin a new, monadic chain. Argument: A (range)

       $     Combine the previous two links into a monadic chain:
     R         Range; turn each k in A into [1, ..., k] or [] if k == 0.
      ‘        Increment to map k to [2, ..., k+1].
   %€        Take each k in A modulo all the integers in the 2D list to the right.
        ḟ/   Reduce by filter-not; sequentially remove all remainder sequences of
             n-1, ..., (not n) from the remainder sequences of n.
          Ṫ  Tail; take the last remainder sequence.
             This gives the shortest sequence for descending A and the longest one
             (i.e., [0]) for ascending A.

```
> 4 votes

# Answer
## Haskell, ~~66~~ ~~60~~ ~~51~~ 50 bytes

```
f i=mod i<$>[2..2+sum[1|l<-scanl1 lcm[2..i],l<=i]]

```

Usage example: `f 42`-\> `[0,0,2,2]`. It's the algorithm described in @Martin Büttner's answer.

I'll keep the previous version for reference, because it's pretty fast:

### Haskell, 51 bytes

```
f i=mod i<$>[[2..x]|x<-[2..],foldl1 lcm[2..x]>i]!!0

```

It takes 0.03s for `f (10^100)` on my five year old laptop.

Edit: @xnor found a byte to save. Thanks!
> 3 votes

# Answer
# Python 3.5, 117 95 78 bytes

```
import sympy
r=lambda n,m=2,M=1,*l:M>n and l or r(n,m+1,sympy.lcm(m,M),*l,n%m)

```

Requires Python 3.5 and sympy (`python3 -m pip install --user sympy`). Credit to @Dennis to notify me that Python 3.5 allows the `*l` trick with default arguments.
> 3 votes

# Answer
# Python 2, 73 70 69 65 bytes

```
i=l=1
n=input()
while l<=n|1:
 i+=1;a=l;print n%i
 while l%i:l+=a

```

A full program. @Dennis saved 4 bytes by improving the way zero is handled.
> 3 votes

# Answer
# Pyth, ~~51 Bytes~~ 66 Bytes

```
IqQZ[Z).q)IqQ1[1))IqQ2,0 1))FdhhQJu/*GHiGHtUd1I>JQVQ aY%QhN)<tYd.q

```

Try it out!

**Much** higher speed 39 byte version (does not work for 0-2):

```
FdhhQJu/*GHiGHtUd1I>JQVtd aY%QhN)<tYd.q

```

It seems to work for absurdly large numbers like 10103

~~Note: this answer does not work for 0, 1, and 2.~~ Fixed!
> 2 votes

# Answer
## JavaScript (ES6), ~~81~~ 77 bytes

```
f=(n,r=[n%2],l=i=2,g=(j,k)=>j?g(k%j,j):k)=>l>n?r:f(n,[...r,n%++i],i/g(i,l)*l)

```

This recursively builds up the answer until the LCM exceeds the original number. The GCD is also calculated recursively, of course.

Edit: Saved 4 bytes thanks to @user81655.
> 2 votes

# Answer
# Julia, ~~36~~ 33 bytes

```
\(n,k=2)=lcm(2:k)>n?n%(2:k):n\-~k

```

Try it online!
> 2 votes

# Answer
# Ruby, 52 bytes

```
->n{m=t=1;a=[];(a<<n%m)until n<t=t.lcm(m+=1);a<<n%m}

```

This solution checks every possible `m` starting from 2 that be the remainder that makes the sequence unique. What makes the last `m` unique is not the remainder itself, but that the `m` is the last member of the smallest range `(2..m)` where the least common multiple (LCM) of that range is greater than `n`. This is due to the Chinese Remainder Theorem, where to uniquely determine what number `n` is with a number of remainders, the LCM of those remainders must be greater than `n` (if selecting `n` from `(1..n)`; if selecting `n` from `a..b`, the LCM needs only be greater than `b-a`)

**Note:** I put `a<<n%m` at the end of the code because `until n<t=t.lcm(m+=1)` short-circuits before `a` has received the last element to make it unique.

If anyone has any golfing suggestions, please let me know in the comments or in PPCG chat.

**Ungolfing:**

```
def remainder_sequence(num)
  # starting with 1, as the statements in the until loop immediately increments divisor
  divisor = 1
  # starts with 1 instead of 2, as the statements in the until loop
  # immediately change product to a new lcm
  product = 1
  remainders = []

  # this increments divisor first then checks the lcm of product and divisor
  # before checking if num is less than this lcm
  until num < (product = product.lcm(divisor = divisor + 1))
    remainders << num % divisor
  end

  # until always short circuits before the last element is entered
  # so this enters the last element and returns
  return remainders << num % divisor
end

```
> 2 votes

# Answer
# Python 3.5, 194 181 169 152 149 146 bytes:

(*Thanks to @Sherlock9 for 2 bytes!*)

```
def r(o,c=0):
 y=[[j%i for i in range(2,100)]for j in range(o+1)]
 while 1:
  c+=1;z=y[-1][:c]
  if z not in[f[:c]for f in y[:-1]]:break
 print(z)

```

Works perfectly, and is also pretty quick. Calculating for the minimal remainder sequence of `100000` outputs `[0, 1, 0, 0, 4, 5, 0, 1, 0, 10, 4, 4]` and took only about 3 seconds. It was even able to calculate the sequence for the input `1000000` (1 million), output `[0, 1, 0, 0, 4, 1, 0, 1, 0, 1, 4, 1, 8, 10, 0, 9]`, and took about 60 seconds.

# Explanation

Basically what this function does is firstly create a list, `y`, with all `j mod i` where `j` is every integer in the range `0=>7` (including 7) and `i` is every integer in the range `0=>100`. The program then goes into an infinite `while` loop and compares the same number of contents of each sublist within the first through second-to-last sublists of `y` (`y[:-1:]`) with the same number of items in the last sublist (`y[-1]`) of list `y`. When sublist `y[-1]` is *different* than any other sublist, the loop is broken out of, and the correct minimal remainder sequence is returned.

For instance, if the input is 3, `y` would be:

```
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], [1, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]

```

Then, when it enters into the while loop, it compares each sublist in list `y[:-1:]` with the same number of items in sublist `y[-1]`. For example, it would first compare `[[0],[1],[0]]` and `[1]`. Since the last sublist is in the rest of `y`, it would continue on and then compare `[[0,0],[0,1],[0,2]]` and `[1,0]`. Since `[1,0]` is now NOT in the rest of `y` *in that specific order*, that is the minimal reminder sequence, and therefore, `[1,0]` would be correctly returned.
> 1 votes

# Answer
# C89, 105 bytes

```
g(a,b){return b?g(b,a%b):a;}main(n,m,M){scanf("%d",&n);for(m=M=1;(M=++m*M/g(m,M))<=n;)printf("%d ",n%m);}

```

Compiles (with warnings) using `gcc -std=c89`. Takes a single number on stdin, and outputs the sequence of remainders separated by spaces on stdout.
> 0 votes

# Answer
# C, 89 bytes

```
a,i=2;main(l,n){for(n=atoi(gets(n))?:!puts(n);n/l;printf("%d ",n%i++))for(a=l;l%i;l+=a);}

```

Compile with gcc. Try it online: n=59, n=0.
> 0 votes

---
Tags: code-golf, number, sequence, arithmetic, number-theory
---


title: Minifying math statements

text:
# Question
Title: Minifying math statements
# The Challenge

You are the owner of an amazing service called *Coyote Beta*, which magically answers math questions its users send to it over the internet.

But it turns out, bandwidth is expensive. You have two choices, either create a "*Coyote Beta* Pro" or find some way to solve this. Just recently, someone queried `(x + 2)`. Couldn't the client send `x+2`, and the user would see no difference?

# The Task

Your task is to "minify" math expressions. Given an input expression, you must get rid of whitespace and parentheses until it gives a minimal representation of the same input. The parentheses around associative operations need not be preserved.

The only operators given here are `+`, `-`, `*`, `/`, and `^` (exponentiation), with standard mathematical associativity and precedence. The only whitespace given in the input will be actual space characters.

# Sample Input/Output

```
Input       | Output
------------|--------------
(2+x) + 3   | 2+x+3
((4+5))*x   | (4+5)*x
z^(x+42)    | z^(x+42)
x - ((y)+2) | x-(y+2)
(z - y) - x | z-y-x
x^(y^2)     | x^y^2
x^2 / z     | x^2/z
- (x + 5)+3 | -(x+5)+3

```

# Scoring

Input/output can use any preferred method. The smallest program in bytes wins.

**Exact bits**

Exponentiation is right associative and also follows standard math precedence (being the highest). A valid numeric literal is `/[0-9]+/`, and a valid variable literal is `/[a-z]+/`. A single variable literal represents a single value even when its character length is longer than 1.

What is meant by "the parentheses around associative operations need not be preserved" is that the output should consist of an expression that results in an identical parse tree, with the exception that associative operations can be rearranged.

# Answer
# C#, ~~523~~ ~~519~~ 504 bytes

Check the in-code comments to see how it works!

---

## Golfed

```
using System;using System.Collections.Generic;namespace n{class p{static void Main(string[]a){foreach(String s in a){String r=s.Replace(" ","");List<int>l=new List<int>();for(int i=0;i<r.Length;i++){if(r[i]=='('){l.Add(i);continue;}if(r[i]==')'){switch(r[Math.Max(l[l.Count-1]-1,0)]){case'+':case'(':switch(r[Math.Min(i+1,r.Length-1)]){case'+':case'-':case')':r=r.Remove(Math.Max(l[l.Count-1],0),1);r=r.Remove(Math.Min(i,r.Length)-1,1);i-=2;break;}break;}l.RemoveAt(l.Count-1);}}Console.WriteLine(r);}}}}

```

---

## Ungolfed

```
using System;
using System.Collections.Generic;

namespace n {
    class p {
        static void Main( string[] a ) {
            // Loop every String given for the program
            foreach (String s in a) {
                // Get rid of the spaces
                String r = s.Replace( " ", "" );

                // A little helper that will have the indexes of the '('
                List<int> l = new List<int>();

                // Begin the optimizatio process
                for (int i = 0; i < r.Length; i++) {
                    // If char is an '(', add the index to the helper list and continue
                    if (r[ i ] == '(') {
                        l.Add( i );
                        continue;
                    }

                    // If the char is an ')', validate the group
                    if (r[ i ] == ')') {
                        // If the char before the last '(' is an '+' or '(' ...
                        switch (r[ Math.Max( l[ l.Count - 1 ] - 1, 0 ) ]) {
                            case '+':
                            case '(':
                                // ... and the char after the ')' we're checking now is an '+', '-' or ')' ...
                                switch (r[ Math.Min( i + 1, r.Length - 1 ) ]) {
                                    case '+':
                                    case '-':
                                    case ')':
                                        // Remove the '()' since they're most likely desnecessary.
                                        r = r.Remove( Math.Max( l[ l.Count - 1 ], 0 ), 1 );
                                        r = r.Remove( Math.Min( i, r.Length ) - 1, 1 );

                                        // Go two steps back in the loop since we removed 2 chars from the String,
                                        //   otherwise we would miss some invalid inputs
                                        i -= 2;
                                        break;
                                }

                                break;
                        }

                        // Remove the last inserted index of '(' from the list,
                        //   since we matched an ')' for it.
                        l.RemoveAt( l.Count - 1 );
                    }
                }

                // Print the result
                Console.WriteLine( r );
            }
        }
    }
}

```

---

## Side notes

1. Fixed some typos and renamed some vars.
2. Nested an switch to get rid of an unnecessary variable. Also, fixed a bug that would render some solutions invalid, reported by Anders Kaseorg.

---

***P.S.:*** *If you have a tip or found a bug, please let me know in the comments and I'll try to fix it ( I'll then add a note about the bug fix with your name ;) )*
> 1 votes

# Answer
## C++, 284 bytes

**Golfed**

```
#include<iostream>
#include<algorithm>
int main(){std::string e;std::getline(std::cin,e);e.erase(std::remove_if(e.begin(),e.end(),isspace),e.end());for(int x=0;x<e.length();x++){if(e[x]=='('&&e[x+1]=='('){e.erase(x,1);}if(e[x]==')'&&e[x+1]==')'){e.erase(x,1);}}std::cout<<e;return 0;}

```

**Ungolfed**

```
#include<iostream>
#include<algorithm>

int main()
{
    std::string e;
    std::getline(std::cin, e);
    e.erase(std::remove_if(e.begin(), e.end(), isspace), e.end());
    for(int x = 0; x < e.length(); x++) {
        if (e[x] == '(' && e[x+1] == '('){
            e.erase(x, 1);
        }
        if (e[x] == ')' && e[x+1] == ')'){
            e.erase(x, 1);
        }
    }
    std::cout<<e;
    return 0;
}

```
> 0 votes

---
Tags: code-golf, math, parsing, optimized-output
---