P1 2021/22 - 06 Marsovci - resitev Aljaz Starc¶
from typing import Dict, Set, Tuple
from math import sqrt, pow
def createStructLvl1 (source: Set[Tuple[float, float, float]]) -> Dict[Tuple[float, float, float], Set[Tuple[float, float, float]]]:
"""
Returns a dict where
keys are Tuple[float, float, float] (circles) and
values are Set[Tuple[float, float, float]] other circles that the key contains
"""
parents = {k: set() for k in source}
notranji = set()
for k1 in source:
set2 = source.copy()
set2.remove(k1)
for k2 in set2:
if k1[2] > k2[2] and k1[2] > sqrt(pow(k1[0] - k2[0], 2) + pow(k1[1] - k2[1], 2)):
parents[k1].add(k2)
notranji.add(k2)
return parents, set(source) - notranji
def ptici (krogi: Set[Tuple[float, float, float]], struct = None) -> Set[Tuple[float, float]]:
if not struct:
struct = createStructLvl1(krogi)
parents, zunanji = struct
_ptici = set()
# ni vsebovan v nobenem drugem krogu
for krog in zunanji:
# torej okroglaste živali z dvema očesoma
#
# in vsebuje natančno dva kroga,
if len(parents[krog]) != 2:
continue
# ki ne vsebujeta drugih krogov.
for c in parents[krog]:
if parents[c] != set():
break
else:
_ptici.add(krog[:2])
return _ptici
def letala(krogi: Set[Tuple[float, float, float]], struct = None) -> Set[Tuple[float, float]]:
if not struct:
struct = createStructLvl1(krogi)
parents, zunanji = struct
letala_ = set()
# ni vsebovan v nobenem drugem krogu
for krog in zunanji:
# To so okroglasti predmeti z okni. Letalo je torej krog
# if krog does not container any circles, then it's not a plane
#
# vsebuje nekaj krogov (vendar ne dveh, saj gre v tem primeru za ptiča),
# if the circle containes exatcly two other circles in means that it's a bird
# and if one of the circles contains the second one, it's still not a plane
if parents[krog] == set() or len(parents[krog]) == 2:
continue
# krogi, ki jih vsebuje, ne vsebujejo drugih krogov.
#
# If any child has any children, it's not a plane
# return False
for child in parents[krog]:
if len(parents[child]):
break
else:
letala_.add(krog[:2])
return letala_
def sumljivi(krogi: Set[Tuple[float, float, float]]) -> Set[Tuple[float, float]]:
parents, zunanji = createStructLvl1(krogi)
sumljivi_ = set()
for krog in zunanji:
if parents[krog] == set():
sumljivi_.add(krog[:2])
else:
# ce vsebuje vsaj en krog, ki ni prazen, je sumljiv
for notranji in parents[krog]:
if parents[notranji] != set():
sumljivi_.add(krog[:2])
break
return sumljivi_
krogi = [(164.4, 136.8, 50.8),(59.2, 182.8, 50.8),(282.8, 71.5, 45.6),(391, 229.4, 58.4),(259.9, 186, 47.6),(428, 89, 63.2),(88.6, 44.3, 37.5),(371.6, 233.6, 10.6),(408.7, 210.5, 8.9),(398.1, 95.5, 13),(449.5, 99.6, 13.6),(455.4, 66.5, 12.4),(139.6, 138, 10.6),(185, 138, 10.6),(69.8, 46.5, 10.6),(267.4, 51.7, 17.2),(225.8, 187.3, 7.5),(242.8, 187.3, 7.5),(259.8, 187.3, 7.5),(276.7, 187.3, 7.5),(293.7, 187.3, 7.5),(267.4, 51.7, 10.6),(99.6, 43.1, 17.2),(99.6, 43.1, 10.6),(150.3, 245.5, 50.8),(144.3, 243.6, 38.8),(127.3, 245.5, 7.5),(161.3, 245.5, 7.5)]
import time
import unittest
class TestObvezna(unittest.TestCase):
def setUp(self):
self.zacetek = time.time()
def tearDown(self):
self.assertLess(time.time() - self.zacetek, 15,
"vsak test se mora končati hitreje kot v 15 sekundah")
def test_ptici(self):
self.assertEqual({(164.4, 136.8), (391, 229.4)}, ptici(krogi))
self.assertEqual(set(), ptici([(x, x, 0.5) for x in range(1000)]))
self.assertEqual(set(), ptici([(0, 0, x) for x in range(1000)]))
self.assertEqual(set(), ptici([(x, x, r)
for x in range(30 * 100, 100)
for r in range(30)]))
self.assertEqual({(-100, -100)},
ptici([(-100, -100, 10),
(-102, -100, 1),
(-99, -100, 1)] +
[(x, x, r)
for x in range(30 * 100, 100)
for r in range(50)]))
def test_letala(self):
self.assertEqual({(259.9, 186), (428, 89)}, letala(krogi))
self.assertEqual(set(), letala([(x, x, 0.5) for x in range(1000)]))
self.assertEqual(set(), letala([(0, 0, x) for x in range(1000)]))
self.assertEqual(set(), letala([(x, x, r)
for x in range(30 * 100, 100)
for r in range(30)]))
self.assertEqual({(0, 0), (100000, 0),},
letala([(0, 0, 10000),
(100000, 0, 1), (100000, 0, 0.5),
(200000, 0, 1)]
+ [(x, 0, 0.5) for x in range(1000)]))
self.assertEqual({(100000, 0)},
letala([(0, 0, 10000),
(100000, 0, 1), (100000, 0, 0.5),
(200000, 0, 1)]
+ [(x, 0, 0.5) for x in range(500)]
+ [(x, 0, 0.3) for x in range(500)]))
class TestDodatna(unittest.TestCase):
def setUp(self):
self.zacetek = time.time()
def tearDown(self):
self.assertLess(time.time() - self.zacetek, 15,
"vsak test se mora končati hitreje kot v 15 sekundah")
def test_sumljivi(self):
self.assertEqual({(59.2, 182.8),
(88.6, 44.3),
(150.3, 245.5),
(282.8, 71.5)},
sumljivi(krogi))
crta = [(x, x, 0.5) for x in range(1000)]
self.assertEqual({(x, y) for x, y, _ in crta}, sumljivi(crta))
self.assertEqual({(0, 0)}, sumljivi([(0, 0, x) for x in range(1000)]))
crta = {(x, x, 29) for x in range(30 * 100, 100)}
self.assertEqual(crta,
sumljivi([(x, x, r)
for x in range(30 * 100, 100)
for r in range(30)]))
self.assertEqual(crta,
sumljivi([(-100, -100, 10),
(-102, -100, 1),
(-99, -100, 1)] +
[(x, x, r)
for x in range(30 * 100, 100)
for r in range(50)]))
self.assertEqual({(200000, 0),},
sumljivi([(0, 0, 10000),
(100000, 0, 1), (100000, 0, 0.5),
(200000, 0, 1)]
+ [(x, 0, 0.5) for x in range(1000)]))
self.assertEqual({(0, 0), (200000, 0)},
sumljivi([(0, 0, 10000),
(100000, 0, 1), (100000, 0, 0.5),
(200000, 0, 1)]
+ [(x, 0, 0.5) for x in range(500)]
+ [(x, 0, 0.3) for x in range(500)]))
if __name__ == "__main__":
unittest.main()
Zadnja posodobitev:
May 7, 2022