Repository: sympy/sympy

Issue:
simplify sum/product of Piecewise functions
`piecewise_fold` might be able to simplify expressions containing products and sums of piecewise more compactly:

This product

``` python
>>> piecewise_fold(Piecewise((x,x>1),(2,True))*Piecewise((x,x>3),(3,True)))
Piecewise((Piecewise((x**2, x > 3), (3*x, True)), x > 1), (Piecewise((2*x, x > 3), (6, True)), True))
```

could be

```
Piecewise((x**2,x>3),(3*x,And(x>1,x<=3)),(6,True))
```

And this sum

``` python
>>> piecewise_fold(Piecewise((x,x>1),(2,True))+Piecewise((x,x>3),(3,True)))
Piecewise((Piecewise((2*x, x > 3), (x + 3, True)), x > 1), (Piecewise((x + 2, x > 3), (5, True)), True))
```

could be

```
Piecewise((2*x,x>3),(x+3,And(x>2,x<=3)),(5,True))
```


Discussion:

Patch:
diff --git a/sympy/functions/elementary/piecewise.py b/sympy/functions/elementary/piecewise.py
index d834bc6749..a72e543944 100644
--- a/sympy/functions/elementary/piecewise.py
+++ b/sympy/functions/elementary/piecewise.py
@@ -540,33 +540,24 @@ def piecewise_fold(expr):
     """
     if not isinstance(expr, Basic) or not expr.has(Piecewise):
         return expr
-    new_args = list(map(piecewise_fold, expr.args))
-    if expr.func is ExprCondPair:
-        return ExprCondPair(*new_args)
-    piecewise_args = []
-    for n, arg in enumerate(new_args):
-        if isinstance(arg, Piecewise):
-            piecewise_args.append(n)
-    if len(piecewise_args) > 0:
-        n = piecewise_args[0]
-        new_args = [(expr.func(*(new_args[:n] + [e] + new_args[n + 1:])), c)
-                    for e, c in new_args[n].args]
-        if isinstance(expr, Boolean):
-            # If expr is Boolean, we must return some kind of PiecewiseBoolean.
-            # This is constructed by means of Or, And and Not.
-            # piecewise_fold(0 < Piecewise( (sin(x), x<0), (cos(x), True)))
-            # can't return Piecewise((0 < sin(x), x < 0), (0 < cos(x), True))
-            # but instead Or(And(x < 0, 0 < sin(x)), And(0 < cos(x), Not(x<0)))
-            other = True
-            rtn = False
-            for e, c in new_args:
-                rtn = Or(rtn, And(other, c, e))
-                other = And(other, Not(c))
-            if len(piecewise_args) > 1:
-                return piecewise_fold(rtn)
-            return rtn
-        if len(piecewise_args) > 1:
-            return piecewise_fold(Piecewise(*new_args))
-        return Piecewise(*new_args)
+
+    new_args = []
+    if isinstance(expr, (ExprCondPair, Piecewise)):
+        for e, c in expr.args:
+            if not isinstance(e, Piecewise):
+                e = piecewise_fold(e)
+            if isinstance(e, Piecewise):
+                new_args.extend([(piecewise_fold(ei), And(ci, c))
+                    for ei, ci in e.args])
+            else:
+                new_args.append((e, c))
     else:
-        return expr.func(*new_args)
+        from sympy.utilities.iterables import cartes
+        folded = list(map(piecewise_fold, expr.args))
+        for ec in cartes(*[
+                (i.args if isinstance(i, Piecewise) else
+                 [(i, S.true)]) for i in folded]):
+            e, c = zip(*ec)
+            new_args.append((expr.func(*e), And(*c)))
+
+    return Piecewise(*new_args)
diff --git a/sympy/polys/polytools.py b/sympy/polys/polytools.py
index 2cf5e69329..9c12741236 100644
--- a/sympy/polys/polytools.py
+++ b/sympy/polys/polytools.py
@@ -255,7 +255,7 @@ def free_symbols(self):
         ========
 
         >>> from sympy import Poly
-        >>> from sympy.abc import x, y, z
+        >>> from sympy.abc import x, y
 
         >>> Poly(x**2 + 1).free_symbols
         {x}
@@ -263,17 +263,12 @@ def free_symbols(self):
         {x, y}
         >>> Poly(x**2 + y, x).free_symbols
         {x, y}
-        >>> Poly(x**2 + y, x, z).free_symbols
-        {x, y}
 
         """
-        symbols = set()
-        gens = self.gens
-        for i in range(len(gens)):
-            for monom in self.monoms():
-                if monom[i]:
-                    symbols |= gens[i].free_symbols
-                    break
+        symbols = set([])
+
+        for gen in self.gens:
+            symbols |= gen.free_symbols
 
         return symbols | self.free_symbols_in_domain
 
@@ -614,10 +609,7 @@ def reorder(f, *gens, **args):
 
     def ltrim(f, gen):
         """
-        Remove dummy generators from ``f`` that are to the left of
-        specified ``gen`` in the generators as ordered. When ``gen``
-        is an integer, it refers to the generator located at that
-        position within the tuple of generators of ``f``.
+        Remove dummy generators from the "left" of ``f``.
 
         Examples
         ========
@@ -627,23 +619,20 @@ def ltrim(f, gen):
 
         >>> Poly(y**2 + y*z**2, x, y, z).ltrim(y)
         Poly(y**2 + y*z**2, y, z, domain='ZZ')
-        >>> Poly(z, x, y, z).ltrim(-1)
-        Poly(z, z, domain='ZZ')
 
         """
         rep = f.as_dict(native=True)
         j = f._gen_to_level(gen)
-
         terms = {}
 
         for monom, coeff in rep.items():
+            monom = monom[j:]
 
-            if any(i for i in monom[:j]):
-                # some generator is used in the portion to be trimmed
+            if monom not in terms:
+                terms[monom] = coeff
+            else:
                 raise PolynomialError("can't left trim %s" % f)
 
-            terms[monom[j:]] = coeff
-
         gens = f.gens[j:]
 
         return f.new(DMP.from_dict(terms, len(gens) - 1, f.rep.dom), *gens)
@@ -664,7 +653,7 @@ def has_only_gens(f, *gens):
         False
 
         """
-        indices = set()
+        indices = set([])
 
         for gen in gens:
             try:
diff --git a/sympy/printing/latex.py b/sympy/printing/latex.py
index 517246efdb..15e4f2bad3 100644
--- a/sympy/printing/latex.py
+++ b/sympy/printing/latex.py
@@ -460,9 +460,6 @@ def _print_Pow(self, expr):
             and expr.exp.is_Rational \
                 and expr.exp.q != 1:
             base, p, q = self.parenthesize(expr.base, PRECEDENCE['Pow']), expr.exp.p, expr.exp.q
-            #fixes issue #12886, adds parentheses before superscripts raised to powers
-            if '^' in base and expr.base.is_Symbol:
-                base = r"\left(%s\right)" % base
             if expr.base.is_Function:
                 return self._print(expr.base, "%s/%s" % (p, q))
             return r"%s^{%s/%s}" % (base, p, q)
@@ -484,13 +481,9 @@ def _print_Pow(self, expr):
                     if tex[:1] == "-":
                         return tex[1:].strip()
                 tex = r"%s^{%s}"
-                #fixes issue #12886, adds parentheses before superscripts raised to powers
-                base = self.parenthesize(expr.base, PRECEDENCE['Pow'])
-                if '^' in base and expr.base.is_Symbol:
-                    base = r"\left(%s\right)" % base
-                exp = self._print(expr.exp)
 
-                return tex % (base, exp)
+                return tex % (self.parenthesize(expr.base, PRECEDENCE['Pow']),
+                              self._print(expr.exp))
 
     def _print_UnevaluatedExpr(self, expr):
         return self._print(expr.args[0])
diff --git a/sympy/solvers/polysys.py b/sympy/solvers/polysys.py
index bd7e538885..14d5bfb2a5 100644
--- a/sympy/solvers/polysys.py
+++ b/sympy/solvers/polysys.py
@@ -6,7 +6,7 @@
 from sympy.polys import Poly, groebner, roots
 from sympy.polys.polytools import parallel_poly_from_expr
 from sympy.polys.polyerrors import (ComputationFailed,
-    PolificationFailed, CoercionFailed, PolynomialError)
+    PolificationFailed, CoercionFailed)
 from sympy.simplify import rcollect
 from sympy.utilities import default_sort_key, postfixes
 
@@ -37,7 +37,10 @@ def solve_poly_system(seq, *gens, **args):
     if len(polys) == len(opt.gens) == 2:
         f, g = polys
 
-        if all(i <= 2 for i in f.degree_list() + g.degree_list()):
+        a, b = f.degree_list()
+        c, d = g.degree_list()
+
+        if a <= 2 and b <= 2 and c <= 2 and d <= 2:
             try:
                 return solve_biquadratic(f, g, opt)
             except SolveFailed:
@@ -76,16 +79,13 @@ def solve_biquadratic(f, g, opt):
     if len(G) != 2:
         raise SolveFailed
 
-    x, y = opt.gens
     p, q = G
-    if not p.gcd(q).is_ground:
-        # not 0-dimensional
-        raise SolveFailed
+    x, y = opt.gens
 
     p = Poly(p, x, expand=False)
-    p_roots = [ rcollect(expr, y) for expr in roots(p).keys() ]
-
     q = q.ltrim(-1)
+
+    p_roots = [ rcollect(expr, y) for expr in roots(p).keys() ]
     q_roots = list(roots(q).keys())
 
     solutions = []
@@ -161,7 +161,7 @@ def solve_generic(polys, opt):
     def _is_univariate(f):
         """Returns True if 'f' is univariate in its last variable. """
         for monom in f.monoms():
-            if any(m for m in monom[:-1]):
+            if any(m > 0 for m in monom[:-1]):
                 return False
 
         return True


Test patch:
diff --git a/sympy/functions/elementary/tests/test_piecewise.py b/sympy/functions/elementary/tests/test_piecewise.py
index 8205c94aca..19fccf6449 100644
--- a/sympy/functions/elementary/tests/test_piecewise.py
+++ b/sympy/functions/elementary/tests/test_piecewise.py
@@ -329,6 +329,10 @@ def test_piecewise_fold():
     assert integrate(
         piecewise_fold(p), (x, -oo, oo)) == integrate(2*x + 2, (x, 0, 1))
 
+    assert piecewise_fold(
+        Piecewise((1, y <= 0), (-Piecewise((2, y >= 0)), True)
+        )) == Piecewise((1, y <= 0), (-2, y >= 0))
+
 
 def test_piecewise_fold_piecewise_in_cond():
     p1 = Piecewise((cos(x), x < 0), (0, True))
@@ -338,16 +342,21 @@ def test_piecewise_fold_piecewise_in_cond():
     assert(p2.subs(x, 1) == 0.0)
     assert(p2.subs(x, -pi/4) == 1.0)
     p4 = Piecewise((0, Eq(p1, 0)), (1,True))
-    assert(piecewise_fold(p4) == Piecewise(
-        (0, Or(And(Eq(cos(x), 0), x < 0), Not(x < 0))), (1, True)))
+    ans = piecewise_fold(p4)
+    for i in range(-1, 1):
+        assert ans.subs(x, i) == p4.subs(x, i)
 
     r1 = 1 < Piecewise((1, x < 1), (3, True))
-    assert(piecewise_fold(r1) == Not(x < 1))
+    ans = piecewise_fold(r1)
+    for i in range(2):
+        assert ans.subs(x, i) == r1.subs(x, i)
 
     p5 = Piecewise((1, x < 0), (3, True))
     p6 = Piecewise((1, x < 1), (3, True))
-    p7 = piecewise_fold(Piecewise((1, p5 < p6), (0, True)))
-    assert(Piecewise((1, And(Not(x < 1), x < 0)), (0, True)))
+    p7 = Piecewise((1, p5 < p6), (0, True))
+    ans = piecewise_fold(p7)
+    for i in range(-1, 2):
+        assert ans.subs(x, i) == p7.subs(x, i)
 
 
 @XFAIL
@@ -363,12 +372,8 @@ def test_piecewise_fold_expand():
     p1 = Piecewise((1, Interval(0, 1, False, True).contains(x)), (0, True))
 
     p2 = piecewise_fold(expand((1 - x)*p1))
-    assert p2 == Piecewise((1 - x, Interval(0, 1, False, True).contains(x)),
-        (Piecewise((-x, Interval(0, 1, False, True).contains(x)), (0, True)), True))
-
-    p2 = expand(piecewise_fold((1 - x)*p1))
-    assert p2 == Piecewise(
-        (1 - x, Interval(0, 1, False, True).contains(x)), (0, True))
+    assert p2 == Piecewise((1 - x, (x >= 0) & (x < 1)), (0, True))
+    assert p2 == expand(piecewise_fold((1 - x)*p1))
 
 
 def test_piecewise_duplicate():
@@ -511,3 +516,27 @@ def test_issue_10258():
     assert Piecewise((0, x < 1), (1, True)).is_finite
     b = Basic()
     assert Piecewise((b, x < 1)).is_finite is None
+
+    # 10258
+    c = Piecewise((1, x < 0), (2, True)) < 3
+    assert c != True
+    assert piecewise_fold(c) == True
+
+
+def test_issue_10087():
+    a, b = Piecewise((x, x > 1), (2, True)), Piecewise((x, x > 3), (3, True))
+    m = a*b
+    f = piecewise_fold(m)
+    for i in (0, 2, 4):
+        assert m.subs(x, i) == f.subs(x, i)
+    m = a + b
+    f = piecewise_fold(m)
+    for i in (0, 2, 4):
+        assert m.subs(x, i) == f.subs(x, i)
+
+
+def test_issue_8919():
+    x, c_1, c_2, c_3, c_4 = symbols('x c_1:5')
+    f1 = Piecewise( (c_1, x < 1), (c_2, True))
+    f2 = Piecewise( (c_3, x < S(1)/3), (c_4, True))
+    assert integrate(f1*f2, (x, 0, 2)) == c_1*c_3/3 + 2*c_1*c_4/3 + c_2*c_4
diff --git a/sympy/polys/tests/test_polytools.py b/sympy/polys/tests/test_polytools.py
index 32d1780880..a1e517941e 100644
--- a/sympy/polys/tests/test_polytools.py
+++ b/sympy/polys/tests/test_polytools.py
@@ -468,8 +468,6 @@ def test_Poly_free_symbols():
     assert Poly(x**2 + sin(y*z)).free_symbols == {x, y, z}
     assert Poly(x**2 + sin(y*z), x).free_symbols == {x, y, z}
     assert Poly(x**2 + sin(y*z), x, domain=EX).free_symbols == {x, y, z}
-    assert Poly(1 + x + x**2, x, y, z).free_symbols == {x}
-    assert Poly(x + sin(y), z).free_symbols == {x, y}
 
 
 def test_PurePoly_free_symbols():
@@ -853,10 +851,9 @@ def test_Poly_reorder():
 def test_Poly_ltrim():
     f = Poly(y**2 + y*z**2, x, y, z).ltrim(y)
     assert f.as_expr() == y**2 + y*z**2 and f.gens == (y, z)
-    assert Poly(x*y - x, z, x, y).ltrim(1) == Poly(x*y - x, x, y)
 
     raises(PolynomialError, lambda: Poly(x*y**2 + y**2, x, y).ltrim(y))
-    raises(PolynomialError, lambda: Poly(x*y - x, x, y).ltrim(-1))
+
 
 def test_Poly_has_only_gens():
     assert Poly(x*y + 1, x, y, z).has_only_gens(x, y) is True
diff --git a/sympy/printing/tests/test_latex.py b/sympy/printing/tests/test_latex.py
index 662c0a8160..8a236e5bdb 100644
--- a/sympy/printing/tests/test_latex.py
+++ b/sympy/printing/tests/test_latex.py
@@ -1587,12 +1587,6 @@ def test_issue_10489():
     assert latex(s) == latexSymbolWithBrace
     assert latex(cos(s)) == r'\cos{\left (C_{x_{0}} \right )}'
 
-
-def test_issue_12886():
-    m__1, l__1 = symbols('m__1, l__1')
-    assert latex(m__1**2 + l__1**2) == r'\left(l^{1}\right)^{2} + \left(m^{1}\right)^{2}'
-
-
 def test_latex_UnevaluatedExpr():
     x = symbols("x")
     he = UnevaluatedExpr(1/x)
diff --git a/sympy/solvers/tests/test_polysys.py b/sympy/solvers/tests/test_polysys.py
index 23b89c2a85..4417b1a1e5 100644
--- a/sympy/solvers/tests/test_polysys.py
+++ b/sympy/solvers/tests/test_polysys.py
@@ -1,12 +1,9 @@
 """Tests for solvers of systems of polynomial equations. """
 
-from sympy import (flatten, I, Integer, Poly, QQ, Rational, S, sqrt,
-    solve, symbols)
+from sympy import flatten, I, Integer, Poly, QQ, Rational, S, sqrt, symbols
 from sympy.abc import x, y, z
 from sympy.polys import PolynomialError
-from sympy.solvers.polysys import (solve_poly_system,
-    solve_triangulated, solve_biquadratic, SolveFailed)
-from sympy.polys.polytools import parallel_poly_from_expr
+from sympy.solvers.polysys import solve_poly_system, solve_triangulated
 from sympy.utilities.pytest import raises
 
 
@@ -53,10 +50,10 @@ def test_solve_biquadratic():
 
     f_1 = (x - 1)**2 + (y - 1)**2 - r**2
     f_2 = (x - 2)**2 + (y - 2)**2 - r**2
-    s = sqrt(2*r**2 - 1)
-    a = (3 - s)/2
-    b = (3 + s)/2
-    assert solve_poly_system([f_1, f_2], x, y) == [(a, b), (b, a)]
+
+    assert solve_poly_system([f_1, f_2], x, y) == \
+        [(S(3)/2 - sqrt(-1 + 2*r**2)/2, S(3)/2 + sqrt(-1 + 2*r**2)/2),
+         (S(3)/2 + sqrt(-1 + 2*r**2)/2, S(3)/2 - sqrt(-1 + 2*r**2)/2)]
 
     f_1 = (x - 1)**2 + (y - 2)**2 - r**2
     f_2 = (x - 1)**2 + (y - 1)**2 - r**2
@@ -83,28 +80,8 @@ def test_solve_biquadratic():
     assert len(result) == 2 and all(len(r) == 2 for r in result)
     assert all(len(r.find(query)) == 1 for r in flatten(result))
 
-    s1 = (x*y - y, x**2 - x)
-    assert solve(s1) == [{x: 1}, {x: 0, y: 0}]
-    s2 = (x*y - x, y**2 - y)
-    assert solve(s2) == [{y: 1}, {x: 0, y: 0}]
-    gens = (x, y)
-    for seq in (s1, s2):
-        (f, g), opt = parallel_poly_from_expr(seq, *gens)
-        raises(SolveFailed, lambda: solve_biquadratic(f, g, opt))
-    seq = (x**2 + y**2 - 2, y**2 - 1)
-    (f, g), opt = parallel_poly_from_expr(seq, *gens)
-    assert solve_biquadratic(f, g, opt) == [
-        (-1, -1), (-1, 1), (1, -1), (1, 1)]
-    ans = [(0, -1), (0, 1)]
-    seq = (x**2 + y**2 - 1, y**2 - 1)
-    (f, g), opt = parallel_poly_from_expr(seq, *gens)
-    assert solve_biquadratic(f, g, opt) == ans
-    seq = (x**2 + y**2 - 1, x**2 - x + y**2 - 1)
-    (f, g), opt = parallel_poly_from_expr(seq, *gens)
-    assert solve_biquadratic(f, g, opt) == ans
-
-
-def test_solve_triangulated():
+
+def test_solve_triangualted():
     f_1 = x**2 + y + z - 1
     f_2 = x + y**2 + z - 1
     f_3 = x + y + z**2 - 1