We provide the lecture notes for useful code you can use in this exercise.
When we want to solve a hard problem, it is good to start with the simplest possible problem.
So we will start with solving one equation with one variable of the form $ax = b$
In fact, we'll make our life even easier, and so we don't worry about reading the input for now So, our goal is to find a function solve1(a,b) that will solve equations of the form $ax + b =0$. For example $solve1(2,-4)=2$
def solve1(a, b): # solve xa + b =0
return -b/a
solve1(2, -3)
1.5
Let's now try to solve two equations, of the form $ax + by + c = 0 , dx + ey + f = 0$ So, $solve2(a,b,c,d,e,f)$ should return a list $[x,y]$ of the solution for $x$ and the solution for $y$.
The idea is the following: if $a \neq 0$, then we can divide the first equation by $a$ to get an equation of the form $1x + b'y + c' = 0$
Then we can subtract the first equation times $d$ from the second equation, to make the second equation have the form $e'y + f' = 0$.
But then the second equation is only over one variable, which we already know how to solve. So, we can get a solution for $y$, and then plug it into the first equation to get a solution for $x$.
def solve2(a, b, c, d, e, f): # solve xa+by+c = 0 , xd+ey+f = 0
if a: # True if a is not zero
# x = (-by-c)/a
# d(-by-c)/a+ey+f=0
y = solve1(-d*b/a+e, -d*c/a+f)
x = (-b*y-c)/a
return x, y
# x = (-ey-f)/d
# a(-ey-f)/d+by+c=0
y = solve1(-a*e/d+b, -f*a/d+c)
x = (-e*y-f)/d
return x, y
solve2(1, 1, -10, 1, -1, -4)
(7.0, 3.0)
Now we want to solve three equations of the form:
$ax + by + cz + dw + e = 0$
$fx + gy + hz + iw + j = 0$
$kx + ly + mz + nw + o = 0$
We are starting to run out of letters, so we will write this as:
$a_{0,0}x_0 + a_{0,1}x_1 + a_{0,2}x_2 + a_{0,3} = 0$
$a_{1,0}x_0 + a_{1,1}x_1 + a_{1,2}x_2 + a_{1,3} = 0$
$a_{2,0}x_0 + a_{2,1}x_1 + a_{2,2}x_2 + a_{2,3} = 0$
We will represent the input as a list of lists:
$[$
$[ a_{0,0} , a_{0,1} , a_{0,2} ,a_{0,3} ],$
$[ a_{1,0} , a_{1,1} , a_{1,2} ,a_{1,3} ],$
$[ a_{2,0} , a_{2,1} , a_{2,2} ,a_{2,3} ],$
$]$
Our solution will have the following form:
We will write a function $solve3(eqs)$ that given a list $eqs$ that contains three lists $eqs[0],eqs[1],eqs[2]$ where each of those corresponds to an equation, returns a list of three numbers that is the solution to the equations.
The approach would be as follows:
Make sure that the first equation has the first coefficient equal to one. That is, it should be of the form $1x_0 + a'_{0,1}x_1 + a'_{0,2}x_2 + a'_{0,3} = 0$ for some numbers $a'_{0,1},a'_{0,2},a'_{0,3}$.
Subtract a multiple of this first equation from all the rest of the equations, so that all the rest of the equations have the first coefficient equalling zero
Run $solve2$ on the second and third equations with 2 variables to get solution $(y,z)$
Compute $x = -a'_{0,3} - a'_{0,2}z - a'_{0,2}y$
Return $[x,y,z]$
def make_first_coeff_nonzero(eqs):
"""Switch order of equations so 1st coef of 1st equation is nonzero"""
if eqs[0][0]:
return
if eqs[1][0]:
eqs[0], eqs[1] = eqs[1], eqs[0]
return
if eqs[2][0]:
eqs[0], eqs[2] = eqs[2], eqs[0]
return
print("Oh oh! All first coefficients are zero - can't solve!")
return
# first solve using "wishful thinking"
def solve3(eqs):
make_first_coeff_nonzero(eqs) # make 1st coef of 1st equation nonzero
eqs[0] = multiply_equation(eqs[0], 1/eqs[0][0])
# make 1st coef of 1st equation equal to 1
for i in [1, 2]:
eqs[i] = add_equations(eqs[i], multiply_equation(eqs[0], -eqs[i][0]))
# zero out first coefficient in 2nd and 3rd equations
(y, z) = solve2(eqs[1][1], eqs[1][2], eqs[1][3],
eqs[2][1], eqs[2][2], eqs[2][3])
# solve 2nd and 3rd equations on 2nd and 3rd variables
x = -eqs[0][1]*y - eqs[0][2]*z - eqs[0][3]
# solve 1st variable given solutions for 2nd and 3rd variables
return (x, y, z)
def multiply_equation(eq, num):
"""Multiply all coefficients of equation eq by number num.
Return result"""
res = []
for x in eq:
res.append(x*num)
return res
def add_equations(eq1, eq2):
"""Add eq1 and eq2. Return result"""
res = []
for i in range(len(eq1)):
res.append(eq1[i]+eq2[i])
return res
# recalling the definition of solve3:
def solve3(eqs):
make_first_coeff_nonzero(eqs) # make 1st coef of 1st equation nonzero
eqs[0] = multiply_equation(eqs[0], 1/eqs[0][0])
# make 1st coef of 1st equation equal 1
for i in [1, 2]:
# zero out first coefficient in eqs 1,2
eqs[i] = add_equations(eqs[i], multiply_equation(eqs[0], -eqs[i][0]))
# make 1st coef of 2nd and 3rd equation equal zero
(y, z) = solve2(eqs[1][1], eqs[1][2], eqs[1]
[3], eqs[2][1], eqs[2][2], eqs[2][3])
# solve 2nd and 3rd equations for 2nd and 3rd variables
x = -eqs[0][1]*y - eqs[0][2]*z - eqs[0][3]
# solve 1st variable using solution for 2nd and 3rd variable
return (x, y, z)
solve3([[1, 1, 1, -6], [1, 1, -1, 0], [1, -1, 1, -2]])
(1.0, 2.0, 3.0)
# Library Function
def check(actual, expected):
if expected != actual:
print(
f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
Note: Make sure to run all the code above this line before starting on the exercises.
We wrote a function $solve1(a,b)$ that gets input coefficients for an equation $ax + b =0$ and outputs a solution for $x$.
But we can also write an equation in the form $cx=d$. Write a function $other\_solve1(c,d)$ that outputs the solution for $x$ such that $cx =d$.
Below are some examples for the output of other_solve1
def other_solve1(c, d):
# Your code below
return 0
# The tests for other_solve1
check(other_solve1(1.0, 1.0), 1.0)
check(other_solve1(1.0, 2.0), 2.0)
check(other_solve1(2.0, 1.0), 0.5)
check(other_solve1(3.0, -2.0), -2.0/3.0)
Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!
Write a similar function for solving 2 equations in 2 variables. $other\_solve2(a,b,c,d,e,f)$ should output two numbers $x,y$ such that $ax+by =c$ and $dx + ey = f$.
Below are some examples for the output of $other\_solve2$
def other_solve2(a, b, c, d, e, f):
# Your code here
return 0
# Tests for other_solve2
# TEST_CASE
# Note: if an error is given saying "check" is not defined, rerun the first code
# cell in this notebook.
check(other_solve2(1.0, 1.0, 3.0, 1.0, -1.0, 1.0), (2.0, 1.0))
check(other_solve2(0.0, 1.0, 2.0, 2.0, 3.0, 10.0), (2.0, 2.0))
Congratulations, the test case passed! Congratulations, the test case passed!
The final grade for Addiscoder in 2018 was based on two quizzes and one final exam. However, the assessments don't all count equally to the final grade.
Getu does not know the weighting of each assessment. However, he knows his friends exam and final scores:
In a table:
Student | Quiz 1 | Quiz 2 | Final Exam | Final Grade |
---|---|---|---|---|
Naomi | 60 | 79 | 95 | 80.65 |
Hermela | 75 | 90 | 85 | 84.25 |
Deko | 95 | 87 | 88 | 89.40 |
What is the weighting on the assessments?
Getu scored 99/100 on the first quiz, 84/100 on the second quiz. He lost his final exam paper, but knows that his final grade was 94.15/100. Can you find his score on the final exam?
Write a function $solve4(eqs)$ that solves four equations in four variables. The function will get a list of $4$ equations, each of them a list of $5$ numbers which correspond to the coefficients of an equation in variables $x_0,x_1,x_2,x_3$ of the form $a_0x_0 + a_1x_2 + a_2x_2+ a_3x_3 + a_4 = 0$.
That is, $solve4$ gets as input a list $\mathtt{eqs}$ such that $\mathtt{eqs} = [ \mathtt{eq}0, \mathtt{eq}1, \mathtt{eq}2 ,\mathtt{eq}3 ]$.
Each one of the $\mathtt{eq}i$'s is itself a list of 5 numbers corresponding the coefficients $a_{i,0},a_{1,1},\ldots,a_{i,4}$ in the equation $a_{i,0}x_0 + a_{i,1}x_1 + a_{i,2}x_2 = a_{i,3}x_3 + a_{i,4} = 0$.
The function should return $(x_0,x_1,x_2,x_3)$: the solution for the four variables.
For example:
def solve4(eqs):
# Your code here
return [0 for i in range(4)]
# Tests for solve4
# Note: if an error is given saying "check" is not defined, rerun the first code
# cell in this notebook.
check(solve4([[1, 1, 1, 1, -10], [1, 1, 1, -1, -2],
[1, 1, -1, 1, -4], [1, -1, 1, 1, -6]]), (1.0, 2.0, 3.0, 4.0))
Congratulations, the test case passed!
In lecture we saw the function make_first_coeff_nonzero(eqs)
that took 3 equations in 3 variables and ensured that the first coefficient of the first equation is nonzero.
Write a general version of this function that would work for every number of equations.
That is, make_first_coeff_nonzero_general(eqs)
will take a list of lists of numbers, and change its ordering so that the first number of the first list is nonzero. (You don't have to worry about the case that all lists have their first number zero.)
Here are examples of outputs:
L1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
# make_first_coeff_nonzero_general(L1) should return [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
L2 = [[0, 2, 3], [4, 5, 6], [7, 8, 9]]
# make_first_coeff_nonzero_general(L2) should return [[4, 5, 6], [0, 2, 3], [7, 8, 9]]
def make_first_coeff_nonzero_general(L):
# Your code here
return L
# Tests:
# Note: if an error is given saying "check" is not defined, rerun the first code
# cell in this notebook.
L1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
make_first_coeff_nonzero_general(L1)
check(L1, [[1, 2, 3], [4, 5, 6], [7, 8, 9]])
L2 = [[0, 2, 3], [4, 5, 6], [7, 8, 9]]
make_first_coeff_nonzero_general(L2)
check(L2, [[4, 5, 6], [0, 2, 3], [7, 8, 9]])
Congratulations, the test case passed! Congratulations, the test case passed!
Write a function solve(eqs)
that can solve $n$ equations in $n$ variables for every number $n$.
In particular it should be the case that if you have 3 equations in 3 variables then it would hold that solve(eqs)==solve3(eqs)
, if you have 4 equations in 4 variables then solve(eqs)=solve4(eqs)
and if you have 7 equations in 7 variables then solve(eqs)==solve7(eqs)
Hint: Use recursion: when given as input $n$ equations in $n$ variables solve
should work on these equations to reduce the task to solving $n-1$ equations on $n-1$ variables, at which point it can call itself to do so.
Here are some test examples:
def solve(eqs):
# Replace this with your code here.
return [0 for i in range(len(eqs))]
# Test for solve() -- Note: we add a round function since decimals may be slightly off.
def roundList(decimals):
for i in range(len(decimals)):
decimals[i] = round(decimals[i])
return decimals
check(roundList(solve([[-1, 1, -1, 1, 0, -2],
[-1, 0, 1, -1, 1, -1],
[1, -1, 0, 0, -1, -4],
[-1, 1, 0, -1, 0, 5],
[-1, -1, 0, -1, -1, -10]
])), [-7.0, -4.0, 9.0, 8.0, -7.0])
check(roundList(solve([[1, 1, 0, -1, 1, -1, -11],
[1, 1, -1, -1, -1, 1, -19],
[0, -1, -1, -1, -1, 1, -10],
[0, 0, 1, -1, 0, 0, 6],
[0, 1, 0, -1, 0, 1, -4],
[-1, 1, 1, 1, 1, -1, 13]
])), [3.0, 3.0, -10.0, -4.0, -2.0, -3.0])
Congratulations, the test case passed! Congratulations, the test case passed!