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

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.update({(b, a): v for (a, b), v in zemljevid.items()})


mali_zemljevid = {(A, B): "robnik bolt",
                  (A, C): "bolt rodeo pešci",
                  (C, D): ""}
mali_zemljevid.update({(b, a): v for (a, b), v in mali_zemljevid.items()})

import unittest
import ast


class TestObvezna(unittest.TestCase):
    def test_1_mozna_pot(self):
        zna_vse = ["robnik", "pešci", "lonci", "rodeo", "gravel", "trava", "stopnice", "bolt", "avtocesta", "črepinje"]
        self.assertEqual("D", mozna_pot("ACD", zna_vse, mali_zemljevid))
        self.assertEqual("D", mozna_pot("ABACD", zna_vse, mali_zemljevid))
        self.assertEqual("B", mozna_pot("AB", zna_vse, mali_zemljevid))
        self.assertEqual("B", mozna_pot("ABD", zna_vse, mali_zemljevid))

        self.assertEqual("M", mozna_pot("ABCRVRIEIPNM", zna_vse ,zemljevid))
        self.assertEqual("H", mozna_pot("HJKMLJH", zna_vse, zemljevid))
        self.assertEqual("A", mozna_pot("AC", zna_vse, zemljevid))
        self.assertEqual("E", mozna_pot("ABCRVRIEPNM", zna_vse, zemljevid))
        self.assertEqual("A", mozna_pot("A", zna_vse, zemljevid))

        self.assertEqual("S", mozna_pot("RIPOPSTUVR", ["stopnice", "robnik", "gravel"], zemljevid))
        self.assertEqual("U", mozna_pot("RIPOPSTUVR", ["stopnice", "robnik", "gravel", "trava"], zemljevid))
        self.assertEqual("V", mozna_pot("RIPOPSTUVR", ["stopnice", "robnik", "gravel", "trava", "lonci"], zemljevid))
        self.assertEqual("R", mozna_pot("RIPOPSTUVR", ["stopnice", "robnik", "gravel", "trava", "lonci", "pešci"], zemljevid))

    def test__2_boljsa_pot(self):
        self.assertEqual("URI", boljsa_pot("UTSPI", "URI", zemljevid))
        self.assertEqual("URI", boljsa_pot("URI", "UTSPI", zemljevid))

        self.assertEqual("SPI", boljsa_pot("SPI", "NPI", zemljevid))
        self.assertEqual("NPI", boljsa_pot("NPI", "SPI", zemljevid))

        self.assertEqual("TS", boljsa_pot("TS", "POPIPNPNPNPNPNPNPN", zemljevid))
        self.assertEqual("TS", boljsa_pot("POPIPNPNPNPNPNPNPN", "TS", zemljevid))
        self.assertEqual("POPIPNPNPNPNPNPNPN", boljsa_pot("POPIPNPNPNPNPNPNPN", "SP", zemljevid))
        self.assertEqual("POPIPNPNPNPNPNPNPN", boljsa_pot("SP", "POPIPNPNPNPNPNPNPN", zemljevid))

        self.assertEqual("SP", boljsa_pot("SP", "KJKJKJ", zemljevid))
        self.assertEqual("KJKJKJ", boljsa_pot("KJKJKJ", "SP", zemljevid))

    def test_3_manjkajoce_vescine(self):
        zna_vse = ["robnik", "pešci", "lonci", "rodeo", "gravel", "trava", "stopnice", "bolt", "avtocesta", "črepinje"]
        self.assertEqual(0, manjkajoce_vescine("RIPOPSTUVR", zna_vse, zemljevid))
        self.assertEqual(3, manjkajoce_vescine("RIPOPSTUVR", ["stopnice", "robnik", "gravel"], zemljevid))
        self.assertEqual(3, manjkajoce_vescine("RIPOPSTUVRIPSTUVR", ["stopnice", "robnik", "gravel"], zemljevid))

    def test_4_skupni_podvig(self):
        self.assertEqual((1.5, 2.5),
                         skupni_podvig("RVABC",
                                       ["trava", "lonci", "bolt", "gravel", "stopnice"],
                                       ["bolt", "lonci", "pešci"],
                                       zemljevid))

        self.assertEqual((1.5, 2.5),
                         skupni_podvig("RVABCRD",
                                       ["trava", "lonci", "bolt", "gravel", "stopnice"],
                                       ["bolt", "lonci", "pešci"],
                                       zemljevid))

        self.assertEqual((3.5, 0.5),
                         skupni_podvig("EIMKJHG",
                                       ["trava", "lonci", "avtocesta", "stopnice", "bolt"],
                                       ["stopnice"],
                                       zemljevid))

        self.assertEqual((0.5, 3.5),
                         skupni_podvig("EIMKJHG",
                                       ["stopnice"],
                                       ["trava", "lonci", "avtocesta", "stopnice", "bolt"],
                                       zemljevid))

        self.assertEqual((0.5, 3.5),
                         skupni_podvig("EIMKJHG",
                                       ["stopnice", "robniki"],
                                       ["trava", "lonci", "avtocesta", "stopnice", "bolt"],
                                       zemljevid))

        self.assertEqual((0.5, 4.5),
                         skupni_podvig("EIMKJHG",
                                       ["stopnice"],
                                       ["trava", "lonci", "avtocesta", "stopnice", "bolt", "robnik"],
                                       zemljevid))

        self.assertEqual((1.5, 4.5),
                         skupni_podvig("EIMKJHG",
                                       ["stopnice", "črepinje", "pešci"],
                                       ["trava", "lonci", "avtocesta", "stopnice", "bolt", "robnik"],
                                       zemljevid))

        self.assertEqual((0.5, 4.5),
                         skupni_podvig("EIMKJHG",
                                       ["stopnice", "črepinje"],
                                       ["trava", "lonci", "avtocesta", "stopnice", "bolt", "robnik", "pešci"],
                                       zemljevid))

        self.assertEqual((0, 3),
                         skupni_podvig("EIMKIJHG",
                                       ["stopnice", "črepinje"],
                                       ["trava", "lonci", "avtocesta", "stopnice", "bolt", "robnik", "pešci"],
                                       zemljevid))


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