class Verden:
    def __init__(self, rutenett):
        self._rutenett = rutenett

    def hoyde(self):
        return len(self._rutenett)

    def bredde(self):
        return len(self._rutenett[0])

    def er_gyldig_rute(self, y, x):
        if y < self.hoyde() and x < self.bredde() \
            and y >= 0 and x >= 0:
                return True
        return False

    def gyldige_naboer(self, y, x):
        # returnere en liste med koordinater til naboer som er
        # rundt (y, x)
        naboer = []
        for diff_x in [-1, 0, 1]:
            for diff_y in [-1, 0, 1]:
                ny_x = x + diff_x
                ny_y = y + diff_y

                if ny_x == x and ny_y == y:
                    continue

                # sjekk hj?rner
                if (abs(diff_x) + abs(diff_y)) % 2 != 0:
                    if self.er_gyldig_rute(ny_y, ny_x):
                        naboer.append((ny_y, ny_x))
        return naboer

    def hent(self, y, x):
        return self._rutenett[y][x]


class Pathfinder:
    def __init__(self, verden, fra, til):
        self._verden = verden
        self._fra = fra
        self._til = til
        self._aktive_ruter = {fra}
        self._sjekket = set()

    def sjekk_om_finnes_sti(self):
        # ideen er ? s?ke utover stegvis
        # vi starter med ? sjekke alle tilgjengelige ruter rundt "fra"
        # hver rute som er tilgjengelig legger vi i en mengde som skal sjekkes neste gang (self._aktive_ruter)
        # hvis det ikke er noen i mengden betyr det at vi har pr?vd ? s?ke utover og ikke funnet nye ruter
        # passer p? at man ikke kan g? tilbake til ruter som allerede er sjekket
        while len(self._aktive_ruter) > 0:
            sjekk_neste_gang = set()
            for aktiv_rute in self._aktive_ruter:
                self._sjekket.add(aktiv_rute)
                for rute_rundt in self._verden.gyldige_naboer(aktiv_rute[0], aktiv_rute[1]):
                    if self._verden.hent(rute_rundt[0], rute_rundt[1]) == 0:
                        continue

                    if rute_rundt in self._sjekket:
                        continue

                    if rute_rundt == self._til:
                        return True

                    sjekk_neste_gang.add(rute_rundt)

            if len(sjekk_neste_gang) == 0:
                return False

            self._aktive_ruter = sjekk_neste_gang


def eksempel():
    return [
        [1, 1, 1],
        [0, 0, 1],
        [1, 1, 1],
        [1, 1, 1]
    ]


def test_pathfinder():
    verden = Verden(eksempel())
    #finder = Pathfinder(verden, (3, 0), (0, 0))
    #assert finder.sjekk_om_finnes_sti()
    finder = Pathfinder(verden, (3, 0), (1, 0))
    assert not finder.sjekk_om_finnes_sti()


def test_opprett_verden():
    verden = Verden(eksempel())
    assert verden.hoyde() == 4
    assert verden.bredde() == 3
    print("Bra")


def test_gyldig_rute():
    verden = Verden(eksempel())
    assert verden.er_gyldig_rute(1, 1)
    assert verden.er_gyldig_rute(1, 2)
    assert not verden.er_gyldig_rute(1, 3)
    assert not verden.er_gyldig_rute(-1, 3)
    assert not verden.er_gyldig_rute(100, 100)


def test_gyldige_naboer():
    verden = Verden(eksempel())
    print(verden.gyldige_naboer(0, 0))
    assert len(verden.gyldige_naboer(0, 0)) == 2


test_opprett_verden()
test_gyldig_rute()
test_gyldige_naboer()
test_pathfinder()
#  (3, 0) -> (0, 0)