Challenge Question Question 9: Distributive property If you truly want to test your teeth on a difficult recursion, here is grist for your teeth. This question is worth just a few points, so that students can score well even without doing it. But if you are starving for a difficult question, here is one. This is difficult. Attempt at your own risk. Instructor is not responsible for the many hours you may end up spending on this problem. Please, do not ask for help about this question in office hours; let people who are doing the regular questions benefit from office hour time. Implement the apply_distributive_property function, which applies the distributive property to an expression to push down multiplication to the leaves as far as possible. The function should apply, recursively, the following transformations: f(gh) = fgfh (f Egh = fhgh until the multiplications cannot be moved down further in the expression tree. Hint: If you have e = ei e2, you first must apply distributivity to ej and e2, obtaining e' and ea. If 0 7 *, then you can just return eo ea. If O = *, then you must consider whether or ely has the form 91 +92. Assume el, does. This means your expression is e *(91 +92), and you need to apply distributivity: e* (91 +92) = (e{ *91) = (e4 * 92) The trick is that after you apply distributivity and obtain (*g) = (e * 92), you must again apply distributivity to both (e{*g), ( * 92) obtaining f1, f2, respectively. This step is necessary because ( *91) now has * as top operator, and you may need to "push it down" using distributivity, obtaining fi; similarly for (e'a * 92). Finally, you can return f + f2. [ ] ### Exercise: Implement apply_distributive def apply_distributive (e): *** Applies the distributive property to an expression ### YOUR CODE HERE e. [ ] ### Simple test for distributivity. 2 points. ### Simple test for distributivity. 2 points. a ## Here is definition of equality that disregards order. def is_distributed(exp): def is_plusminus(exp): return isinstance (exp, tuple) and exp[0] in '+ if isinstance (exp, tuple): OP el, e2 exp if and (is_plusminus (el) is_plusminus (e2)): return false return is_distributed(el) and is_distributed(e2) or import random def value_equality(el, e2): return True def applied_distributivity(f, g): return is_distributed(g) and value_equality(f, g) # Simple test f ('*', ('+', 1, 2), (?-?, 3, 4)) ('+', (?-?, (*', 1, 3), ('*', 1, 4)), (?-?, ('*", 2, 3), ('*", 2, 4))) applied_distributivity (apply_distributive(e), f) [ ] ### More complicated tests for distributivity. 2 points. More complex tests e = ("*, ('*', ('+', 1, 2), ('-', 3, 4)) e2 e, ('+', 5, 6)) f ('+', ('-', ('+', ('*, ('*', 1, 3), 5), ('*', ('*', 1, 3), 6)), ('+', (**, (*', 1, 4), 5), (**", (*', 1, 4), 6))), (?-?, ('+', ('*, ('*', 2, 3), 5), ('*', ('*', 2, 3), 6)), ('+', ('*', ('*, 2, 4), 5), ('*', ('*, 2, 4), 6)))) [] More complicated tests for distributivity. 2 points. # More complex tests e ('*', , {*','+', 1, 23,{'-', 3, 413 eg {+',5,63) f '+', '-', '+','*',''*', 1,31, 5},{'*',['*', 1,33,63), {'+','*','*', 1, 4,5),('*', {'*', 1,41,633), ('-', {+','*','*', 2, 31, 5),('*',{'*', 2, 3,63), {+',*,(*', 2,43,5),(*', {*,2,4), 6333) applied_distributivity (apply_distributive (e2), f) - e f - (*',{'*','+', 1,2),(-', 3, 4]),(*','-',5,6), '+', 7, 8) '+', {'-', {'-', ('+',{'*',{'*', 1, 3],{'*', 5, 73), (*','*', 1, 3],{'*',5,833), ('+','*','*', 1, 3, '*',6,7),'*','*', 1, 3, '*', 6, 8333}, {'-', {'+','*',{'*', 1, 4],{'*',5,71), (*',{'*', 1, 4],{'*',5,8))), {'+','*', '*', 1, 4], '*',6,73), ('*', '*', 1, 4], '*', 6, 8])))), '-', (T), {'+','*',{'*', 2,3},{'*',5,71), (*',{'*', 2,3},{'*',5,8))), '+','*',''*', 2,3,{'*', 6,73), ('*',''*', 2,33,'*', 6, 8333), {'-', {+','*',{'*', 2, 4],{'*',5,73), (*','*', 2, 4],{'*',5,833), '+',''*','*', 2, 4), '*', 6, 73),(*','*', 2, 4),(*',6,8))))) applied_distributivity (apply_distributive (e), f)