A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, R, S, T, U, V = "ABCDEFGHIJKLMNOPRSTUV"

# Pazi, ta zemljevid se spodaj predela v obliko, ki je opisana v navodilih naloge!
zemljevid = {
    (A, B): "gravel trava",
    (A, V): "pešci lonci",
    (B, C): "bolt lonci",
    (B, V): "",
    (C, R): "stopnice pešci lonci",
    (D, F): "stopnice pešci",
    (D, R): "pešci",
    (E, I): "trava lonci",
    (F, G): "trava črepinje",
    (G, H): "črepinje pešci",
    (G, I): "avtocesta",
    (H, J): "robnik bolt",
    (I, M): "avtocesta",
    (I, P): "gravel",
    (I, R): "stopnice robnik",
    (J, K): "",
    (J, L): "gravel bolt",
    (K, M): "stopnice bolt",
    (L, M): "robnik pešci",
    (M, N): "rodeo",
    (N, P): "gravel",
    (O, P): "gravel",
    (P, S): "",
    (R, U): "trava pešci",
    (R, V): "pešci lonci",
    (S, T): "robnik trava",
    (T, U): "gravel trava",
    (U, V): "robnik lonci trava"
}

zemljevid = {k: set(v.split()) for k, v in zemljevid.items()} | {k[::-1]: set(v.split()) for k, v in zemljevid.items()}


import unittest


class Ocena_06_07(unittest.TestCase):
    def test01_vrednost_povezave(self):
        self.assertEqual(5, vrednost_povezave((V, R)))
        self.assertEqual(10, vrednost_povezave((G, I)))
        self.assertEqual(4, vrednost_povezave((R, D)))
        self.assertEqual(0, vrednost_povezave((S, P)))
        self.assertEqual(11, vrednost_povezave((C, R)))

    def test_02_najboljsa_povezava(self):
        self.assertEqual((A, B), najboljsa_povezava("ABC"))
        self.assertEqual((C, R), najboljsa_povezava("ABCRDF"))
        self.assertEqual([P, S], sorted(najboljsa_povezava("SPSPSP")))

    def test_03_vrednost_poti(self):
        self.assertEqual(8, vrednost_poti("ABC"))
        self.assertEqual(33, vrednost_poti("ABCRDF"))
        self.assertEqual(0, vrednost_poti("SPSPSP"))
        self.assertEqual(0, vrednost_poti("M"))

        self.assertIsNone(vrednost_poti("ABCVABC"))


class Ocena_07_08(unittest.TestCase):
    def test_01_enkratna_vrednost_poti(self):
        self.assertEqual(8, enkratna_vrednost_poti("ABC"))
        self.assertEqual(18, enkratna_vrednost_poti("ABCRDF"))
        self.assertEqual(0, enkratna_vrednost_poti("SPSPSP"))
        self.assertEqual(0, enkratna_vrednost_poti("M"))
        self.assertEqual(14, enkratna_vrednost_poti("DFGFG"))

        self.assertIsNone(enkratna_vrednost_poti("ABCVABC"))

    def test_02_mozna_pot(self):
        # Ni povezave I->A
        self.assertFalse(mozna_pot("DFGIAB", set("stopnice avtocesta pešci trava črepinje rodeo".split())))
        # Ta se da
        self.assertTrue(mozna_pot("DFGI", set("stopnice avtocesta pešci trava črepinje rodeo".split())))
        # Ne zna čez črepinje (F->G)
        self.assertFalse(mozna_pot("DFGI", set("stopnice avtocesta pešci trava rodeo".split())))
        # Dvakrat po travi
        self.assertFalse(mozna_pot("DFGIE", set("stopnice avtocesta pešci trava črepinje rodeo".split())))
        # Dvakrat med peščci
        self.assertFalse(mozna_pot("RDFGI", set("stopnice avtocesta pešci trava črepinje rodeo".split())))
        # Ne zahteva veščin
        self.assertTrue(mozna_pot("SP", set()))
        # Pot dolžine 0 je seveda možna
        self.assertTrue(mozna_pot("T", set()))
        self.assertTrue(mozna_pot("T", set("stopnice avtocesta pešci trava črepinje rodeo gravel lonci".split())))

        self.assertTrue(mozna_pot("SPNMIE", set("stopnice avtocesta pešci trava črepinje rodeo gravel lonci".split())))
        self.assertTrue(mozna_pot("SPNMIE", set("stopnice avtocesta pešci trava črepinje rodeo gravel lonci robnik".split())))
        # Dvakrat po travi
        self.assertFalse(mozna_pot("TSPNMIE", set("stopnice avtocesta pešci trava črepinje rodeo gravel lonci robnik".split())))


class Ocena_08_09(unittest.TestCase):
    def test_01_do_nagrade(self):
        self.assertEqual(R, do_nagrade("ABCRIMNPSTU", 20))
        self.assertEqual(I, do_nagrade("ABCRIMNPSTU", 30))
        self.assertEqual(N, do_nagrade("ABCRIMNPSTU", 39))
        self.assertEqual(S, do_nagrade("ABCRIMNPSTU", 40))
        self.assertEqual(U, do_nagrade("ABCRIMNPSTU", 50))

        # ni povezave A -> C
        self.assertEqual(A, do_nagrade("ACRIMNPSTU", 50))

        self.assertEqual(M, do_nagrade("MNPOPNMKJHGFDRCBA", 1))
        self.assertEqual(O, do_nagrade("MNPOPNMKJHGFDRCBA", 6))
        self.assertEqual(J, do_nagrade("MNPOPNMKJHGFDRCBA", 20))
        self.assertEqual(C, do_nagrade("MNPOPNMKJHGFDRCBA", 58))
        self.assertEqual(A, do_nagrade("MNPOPNMKJHGFDRCBA", 100))


class Ocena_09_10(unittest.TestCase):
    def test_01_sosede(self):
        self.assertEqual(
            [(E, {"avtocesta", "stopnice", "bolt"}),
             (G, {"trava", "lonci", "stopnice", "bolt"}),
             (M, {"trava", "lonci", "stopnice", "bolt"})
             ],
            sorted(sosede(I, {"avtocesta", "trava", "lonci", "stopnice", "bolt"})))

        self.assertEqual(
            [(E, {"avtocesta", "stopnice", "bolt", "gravel"}),
             (G, {"trava", "lonci", "stopnice", "bolt", "gravel"}),
             (M, {"trava", "lonci", "stopnice", "bolt", "gravel"}),
             (P, {"avtocesta", "trava", "lonci", "stopnice", "bolt"})
             ],
            sorted(sosede(I, {"avtocesta", "trava", "lonci", "stopnice", "bolt", "gravel"})))

        self.assertEqual(
            [(B, {'bolt', 'avtocesta', 'lonci', 'stopnice'})],
            sorted(sosede(A, {"avtocesta", "trava", "lonci", "stopnice", "bolt", "gravel"})))

        self.assertEqual(
            [(c, set()) for c in "INO"],
            sorted(sosede(P, {"gravel"})))

        self.assertEqual(
            [],
            sorted(sosede(P, set())))

    def test_02_dosegljive(self):
        self.assertEqual(
            {G, K, E, I, M, P, N},
            dosegljive(I, {"avtocesta", "trava", "lonci", "stopnice", "bolt", "gravel", "rodeo"})
        )

        self.assertEqual(
            {P, L, N, J, U, K, R, D, E, V, I, M, G},
            dosegljive(I, {"avtocesta", "trava", "lonci", "stopnice", "bolt", "gravel", "rodeo", "robnik", "pešci"})
        )

        self.assertEqual(
            {I, G, M},
            dosegljive(I, {"avtocesta"})
        )

        self.assertEqual(
            {"I"},
            dosegljive(I, set())
        )


if "__main__" == __name__:
    unittest.main()