P1 2021/22 - 07 marsovci v vrsto - resitev Starc Aljaz¶
from math import sqrt, pi
"""
polmeri(krogi) vrne množico, ki vsebuje vse različne
polmere krogov iz seznama,
"""
def polmeri (krogi):
return set(r for _, _, r in krogi)
"""
veliki(r0, krogi) vrne množico koordinat krogov, katerih
polmer je enak ali večji od r0,
"""
def veliki (r0, krogi):
return { (x, y) for x, y, r in krogi if r >= r0 }
"""
obsegi(krogi) vrne vsoto obsegov krogov,
"""
def obsegi (krogi):
return 2 * pi * sum(r for _, _, r in krogi)
"""
najlevo(krogi) vrne koordinato x najbolj levo točko, ki
se je dotikajo krogi (namig: od koordinate središča je
potrebno odšteti polmer!),
"""
def najlevo (krogi):
return min({ x - r for x, _, r in krogi })
"""
povrsina(krogi) vrne površino pravokotnika, ki se razteza
med najbolj levo in najbolj desno ter najbolj zgornjo in
najbolj spodnjo točko, ki jo pokrivajo krogi. Z drugimi
besedami, če bi morali kroge pokriti s pravokotnikom, ki
bi ga postavili vzporedno z osmi (torej: brez vrtenja)
- kako velik bi bilo?
"""
def povrsina (krogi):
return (max({ x + r for x, _, r in krogi }) - najlevo(krogi)) * (max({ y + r for _, y, r in krogi }) - min({ y - r for _, y, r in krogi }))
"""
ocisti_slovar(d) prejme nek slovar d in vrne nov slovar,
ki vsebuje samo tiste pare (ključ, vrednost), pri katerih
je vrednost resnična. "Neresnične" vrednosti so False, 0
in 0.0 ter prazen seznam, množica, niz ali terka.
"""
def ocisti_slovar (d):
return {i: d[i] for i in d if d[i]}
"""
znotraj(x0, y0, r0, krogi) vrne seznam tistih krogov iz
seznama krogi, ki se nahajajo znotraj kroga s središčem (x0, y0)
in polmerom r0. (Krog mora biti strogo znotraj - ni dovolj,
da sovpada. Krog (0, 0, 5) ne leži znotraj kroga (0, 0, 5).)
"""
def znotraj (x0, y0, r0, krogi):
return [k for k in krogi if r0 > k[2] and r0 > sqrt(pow(x0 - k[0], 2) + pow(y0 - k[1], 2))]
"""
vsebovanost(krogi) vrne slovar, katerega ključi so krogi,
vrednosti pa so seznami krogov, ki so znotraj teh krogov, ki
jih opisuje ključ. Če kak krog ne vsebuje nobenega drugega
kroga, naj se tudi med ključi ne pojavi; z drugimi besedami,
med vrednostmi naj ne bo nobenega praznega seznama. (Pomemben
namig: uporabljaj funkcije, ki jih že imaš!)
"""
def vsebovanost (krogi):
return ocisti_slovar({ k: znotraj(*k, krogi) for k in krogi })
"""
notranjost(krogi) vrne množico vseh krogov, ki so znotraj
katerega izmed drugih krogov.
approach from: https://stackoverflow.com/a/952952/11276254
"""
def notranjost (krogi):
return { inner for inners in vsebovanost(krogi).values() for inner in inners }
"""
ptici0(vsebovani, notranji) prejme slovar, kakršnega vrača
funkcija vsebovanost in množico, kakršno vrača notranjost.
Vrniti mora množico vseh ptičev.
"""
def ptici0 (vsebovani, notranji):
return { krog[:2] for krog in vsebovani if \
krog not in notranji and \
len(vsebovani[krog]) == 2 and \
{ i for i in vsebovani[krog] if i in vsebovani } == set() }
"""
ptici(krogi) prejme kroge in vrne ptiče.
"""
def ptici (krogi):
return { p for p in ptici0(vsebovanost(krogi), notranjost(krogi))}
def letala0(vsebovani, notranji):
return { krog[:2] for krog in vsebovani if \
krog not in notranji and \
len(vsebovani[krog]) == 1 or len(vsebovani[krog]) > 2 and \
{ i for i in vsebovani[krog] if i in vsebovani } == set() }
def letala (krogi):
return { p for p in letala0(vsebovanost(krogi), notranjost(krogi))}
def sumljivi0(krogi, vsebovani, notranji):
return { krog[:2] for krog in krogi if \
krog not in notranji and \
(
krog not in vsebovani or \
{k for k in vsebovani[krog] if znotraj(*k, krogi) != []} != set()
)}
def sumljivi (krogi):
return { p for p in sumljivi0(krogi, vsebovanost(krogi), notranjost(krogi))}
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 ast
import unittest
from math import pi
class TestOneLineMixin:
functions = {
elm.name: elm
for elm in ast.parse(open(__file__, "r", encoding="utf-8").read()).body
if isinstance(elm, ast.FunctionDef)}
def assert_is_one_line(self, func):
func
body = self.functions[func.__code__.co_name].body
self.assertEqual(len(body), 1, "\nFunkcija ni dolga le eno vrstico")
self.assertIsInstance(body[0], ast.Return, "\nFunkcija naj bi vsebovala le return")
def test_nedovoljene_funkcije(self):
dovoljene_funkcije = {
"polmeri", "veliki", "obsegi", "najlevo", "povrsina",
"znotraj", "ocisti_slovar", "vsebovanost", "notranjost",
"ptici0", "ptici", "letala0", "letala", "sumljivi0", "sumljivi"}
for func in self.functions:
self.assertIn(func, dovoljene_funkcije, f"\nFunkcija {func} ni dovoljena.")
class TestOgrevanje(unittest.TestCase, TestOneLineMixin):
def test_polmeri(self):
self.assert_is_one_line(polmeri)
self.assertEqual({50.8}, polmeri(krogi[:1]))
self.assertEqual({50.8, 45.6, 58.4}, polmeri(krogi[:4]))
def test_veliki(self):
self.assert_is_one_line(veliki)
self.assertEqual({(391, 229.4), (428, 89)}, veliki(55, krogi))
self.assertEqual({(428, 89)}, veliki(60, krogi))
self.assertEqual(
{(391, 229.4), (428, 89), (59.2, 182.8),
(150.3, 245.5), (164.4, 136.8)},
veliki(50, krogi))
def test_obsegi(self):
self.assert_is_one_line(obsegi)
self.assertAlmostEqual(2 * pi * 50.8, obsegi(krogi[:1]))
self.assertAlmostEqual(2 * pi * (50.8 + 50.8 + 45.6), obsegi(krogi[:3]))
self.assertAlmostEqual(4033.1766486785764, obsegi(krogi))
def test_najlevo(self):
self.assertEqual(1, najlevo([(3, 0, 1), (5, 10, 4)]))
def test_povrsina(self):
self.assert_is_one_line(povrsina)
self.assertEqual(10 * 10, povrsina([(0, 0, 5)]))
self.assertEqual(10 * 10, povrsina([(0, 0, 5), (0, 0, 1)]))
self.assertEqual((23 - (-5)) * 10, povrsina([(0, 0, 5), (20, 0, 3)]))
self.assertEqual((23 - (-5)) ** 2, povrsina([(0, 0, 5), (20, 20, 3)]))
self.assertAlmostEqual((2 * 50.8) ** 2, povrsina(krogi[:1]))
self.assertAlmostEqual(66464.0, povrsina(krogi[:3]))
self.assertAlmostEqual(139770.59999999998, povrsina(krogi))
class TestObvezna(unittest.TestCase, TestOneLineMixin):
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_znotraj(self):
self.assertEqual([], znotraj(-100, -100, 5, krogi))
self.assertEqual([], znotraj(-100, -100, 5, krogi))
self.assertEqual([], znotraj(59.2, 182.8, 50,krogi))
self.assertEqual([(59.2, 182.8, 50.8)], znotraj(59.2, 182.8, 51, krogi))
self.assertEqual([], znotraj(59.2, 182.8, 50.8, krogi))
self.assertEqual(krogi, znotraj(0, 0, 10000, krogi))
self.assertEqual({(99.6, 43.1, 17.2),
(99.6, 43.1, 10.6),
(69.8, 46.5, 10.6)},
set(znotraj(88.6, 44.3, 37.5, krogi)))
def test_vsebovanost(self):
self.assertEqual({(88.6, 44.3, 37.5): {(69.8, 46.5, 10.6),
(99.6, 43.1, 17.2),
(99.6, 43.1, 10.6)},
(99.6, 43.1, 17.2): {(99.6, 43.1, 10.6)},
(144.3, 243.6, 38.8): {(127.3, 245.5, 7.5),
(161.3, 245.5, 7.5)},
(150.3, 245.5, 50.8): {(144.3, 243.6, 38.8),
(127.3, 245.5, 7.5),
(161.3, 245.5, 7.5)},
(164.4, 136.8, 50.8): {(139.6, 138, 10.6),
(185, 138, 10.6)},
(259.9, 186, 47.6): {(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, 17.2): {(267.4, 51.7, 10.6)},
(282.8, 71.5, 45.6): {(267.4, 51.7, 17.2),
(267.4, 51.7, 10.6)},
(391, 229.4, 58.4): {(371.6, 233.6, 10.6),
(408.7, 210.5, 8.9)},
(428, 89, 63.2): {(398.1, 95.5, 13),
(449.5, 99.6, 13.6),
(455.4, 66.5, 12.4)}},
{k: set(v) for k, v in vsebovanost(krogi).items()})
def test_ptici(self):
self.assert_is_one_line(ptici)
self.assert_is_one_line(ptici0)
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)]))
class TestDodatna(unittest.TestCase, TestOneLineMixin):
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_letala(self):
self.assert_is_one_line(letala)
self.assert_is_one_line(letala0)
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)]))
def test_sumljivi(self):
self.assert_is_one_line(sumljivi)
self.assert_is_one_line(sumljivi0)
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