import copy
import importlib
import os
from fractions import Fraction
import math
import random
import unittest
PACKAGE = os.environ.get("MANUAL_IMPL", "solutions")
for _alias,_name in {"calc":"calculus_bridge","dag_paths":"dag_paths","memory_models":"memory_models",
"dual":"dual","simulation":"simulation","graphics":"graphics","dfa":"dfa_compare"}.items():
globals()[_alias]=importlib.import_module(f"{PACKAGE}.{_name}")
class WorkshopTests(unittest.TestCase):
def test_quadratic_identity(self):
for a in range(-2,3):
for b in range(-2,3):
f=calc.Quadratic(a,b,4)
for x in (-2,0,3):
for h in (Fraction(-1,3),Fraction(1,10),2):
self.assertEqual(f.average_rate(x,h),2*a*x+b+a*h)
slope,intercept=f.tangent(x)
self.assertEqual(slope*x+intercept,f.value(x))
def test_quotient_domain(self):
f=calc.Quadratic(3,2,-4)
self.assertEqual(f.tangent(-1),(-4,-7))
with self.assertRaises(ValueError):f.average_rate(0,0)
with self.assertRaises(TypeError):f.value(.1)
def test_dag_negative_edges(self):
d,p,o=dag_paths.shortest_paths(4,[(0,1,2),(0,2,5),(2,1,-4),(1,3,2)],0)
self.assertEqual(d,[0,1,5,3]);self.assertEqual(dag_paths.path(p,0,3),[0,2,1,3])
with self.assertRaises(ValueError):dag_paths.shortest_paths(2,[(0,1,1),(1,0,-2)],0)
def test_dag_against_relaxation(self):
rng=random.Random(41)
for n in range(2,12):
edges=[(i,j,rng.randrange(-4,8)) for i in range(n) for j in range(i+1,n) if rng.random()<.3]
d,_,_=dag_paths.shortest_paths(n,edges,0)
oracle=[None]*n;oracle[0]=0
for _ in range(n-1):
for u,v,w in edges:
if oracle[u] is not None and (oracle[v] is None or oracle[u]+w<oracle[v]):oracle[v]=oracle[u]+w
self.assertEqual(d,oracle)
def test_virtual_translation(self):
self.assertEqual(memory_models.translate(0x2345,{2:7}),0x7345)
with self.assertRaises(KeyError):memory_models.translate(0,{})
def test_cache_conflict(self):
self.assertEqual([x['hit'] for x in memory_models.direct_mapped([0,64,0,64])],[False]*4)
self.assertEqual([x['hit'] for x in memory_models.direct_mapped([0,32,0,32])],[False,False,True,True])
def test_dual_chain(self):
x=dual.Dual(.7,1)
out=dual.exp(dual.sin(x*x))
expected=math.exp(math.sin(.49))*math.cos(.49)*1.4
self.assertAlmostEqual(out.tangent,expected)
loss=(dual.Dual(2,1)*2+1-3)*(dual.Dual(2,1)*2+1-3)/2
self.assertEqual((loss.value,loss.tangent),(2,4))
def test_dual_domain_and_quotient(self):
x=dual.Dual(2,1);self.assertEqual((1/x).tangent,-.25)
with self.assertRaises(ValueError):dual.log(dual.Dual(0,1))
with self.assertRaises(ZeroDivisionError):_ = x/0
def test_verlet_scale_rejection(self):
with self.assertRaises(ValueError): simulation.verlet(x=1e308,steps=0)
with self.assertRaises(ValueError): simulation.exact(1e308,omega=1e308)
def test_verlet_convergence(self):
errors=[]
for n in (10,20,40):
t,x,v,e=simulation.verlet(dt=1/n,steps=n)[-1]
a,b=simulation.exact(t);errors.append(math.hypot(x-a,v-b))
self.assertTrue(3.5<errors[0]/errors[1]<4.5)
self.assertTrue(3.5<errors[1]/errors[2]<4.5)
def test_verlet_initial_and_invalid(self):
self.assertEqual(simulation.verlet(steps=0),[(0.,1.,0.,.5)])
with self.assertRaises(ValueError):simulation.verlet(dt=0)
def test_barycentric_reconstruction(self):
a,b,c=(0,0),(4,0),(0,4);p=(1,1)
w=graphics.barycentric(p,a,b,c);self.assertEqual(w,(.5,.25,.25))
self.assertEqual(tuple(sum(q[k]*weight for q,weight in zip((a,b,c),w)) for k in range(2)),p)
with self.assertRaises(ValueError):graphics.barycentric(p,a,a,c)
def test_perspective(self):
self.assertAlmostEqual(graphics.perspective([.5,.25,.25],[1,2,4],[[0],[8],[16]])[0],32/11)
self.assertEqual(graphics.perspective([1,0,0],[1,2,4],[[2],[8],[16]]),[2.])
def test_dfa_witness_and_equivalence(self):
even={'states':2,'start':0,'accept':{0},'transition':{(0,'a'):1,(1,'a'):0,(0,'b'):0,(1,'b'):1}}
all_words={'states':1,'start':0,'accept':{0},'transition':{(0,'a'):0,(0,'b'):0}}
w=dfa.distinguishing_word(even,all_words)
self.assertEqual(w,'a');self.assertNotEqual(dfa.accepts(even,w),dfa.accepts(all_words,w))
self.assertIsNone(dfa.distinguishing_word(even,copy.deepcopy(even)))
def test_dfa_empty_and_invalid(self):
a={'states':1,'start':0,'accept':{0},'transition':{(0,'a'):0}}
b={**a,'accept':set()}
self.assertEqual(dfa.distinguishing_word(a,b,('a',)),'')
with self.assertRaises(ValueError):dfa.distinguishing_word(a,b)
if __name__=='__main__':unittest.main()