I'm done

mail@pastecode.io avatar
unknown
python
3 years ago
5.1 kB
3
Indexable
Never
# 2. skuska: zacarovane ulice
# autor: Benjamin Bergstrom
# datum: 24.6.2021

class ZacarovaneUlice:
    def __init__(self, meno_suboru):
        self.graph = []
        self.start = ''
        self.ends = set()

        names = set()
        with open(meno_suboru, 'r') as file:
            for line in file:
                line = line.split()
                # initialize graph without edges
                for item in line:
                    if item not in names and not self.wrappedInQuotes(item):
                        names.add(item)
                        self.graph.append((item, dict()))

        with open(meno_suboru, 'r') as file:
            for line in file:
                line = line.split()

                for item in line:
                    # add edges
                    self.ends.add(line[-1])
                    for i in range(0, len(line) - 2, 2):
                        if i == 0:
                            self.start = line[i]

                        for graphItem in self.graph:
                            if graphItem[0] == line[i]:
                                graphItem[1][line[i + 2]] = line[i + 1]
                                break

        del names

    def wrappedInQuotes(self, item):
        return item[0] == '"' and item[-1] == '"'

    def vrcholy(self):          # vráti množinu všetkých vrcholov
        return set([item[0] for item in self.graph])

    def start_ciel(self):       # vráti meno štartu a množinu cieľov
        return self.start, self.ends

    def hrana(self, v1, v2):    # pre dva vrcholy vráti magické slovo alebo None, ak nie je ulica
        for graphItem in self.graph:
            if graphItem[0] == v1:
                if v2 not in graphItem[1].keys():
                    return None
                return graphItem[1][v2][1:-1]
        return None

    def findVertexByName(self, name):
        for graphItem in self.graph:
            if graphItem[0] == name:
                return graphItem

    def trasa(self, postupnost_slov, ciel=None):
        # trivial case
        if postupnost_slov == '':
            return [self.start]

        # initialize starter values for backtracking
        self.exit = ciel
        self.path = []
        self.finalPath = []
        self.amount = 0
        self.words = postupnost_slov.split('-')

        self.backtracking(self.start)
        if self.finalPath == [] or self.finalPath[-1] in self.ends:
            return self.finalPath

        # continue if we did not end in one of the ends
        self.amount = 0
        self.visited = set()

        foundNamelessEdge = False
        for fuckingHell in self.graph:
            for bashingMyHeadOnTheWall in fuckingHell[1].items():
                if bashingMyHeadOnTheWall[0] in self.ends and bashingMyHeadOnTheWall[1][1:-1] == '':
                    thatOneEnd = bashingMyHeadOnTheWall[0]
                    foundNamelessEdge = True
                    break

        if not foundNamelessEdge:
            return []

        self.backtracking2(self.finalPath[-1], thatOneEnd)

        return self.finalPath

    def backtracking(self, v1, i=0):
        if self.amount > 0:
            return

        self.path.append(v1)

        graph = self.findVertexByName(v1)

        if i == len(self.words):
            self.amount += 1
            self.finalPath = []
            if self.exit == self.path[-1] or self.exit == None:
                self.finalPath.extend(self.path)
        else:
            neighbours = graph[1].items()
            for name, value in neighbours:
                value = self.removeQuotes(value)
                nextLevelNeighbours = self.findVertexByName(name)[1].values()
                print(nextLevelNeighbours)

                if self.words[i] == value:
                    self.backtracking(name, i + 1)
                elif value == '':
                    self.backtracking(name, i + 0)

        self.path.pop()

    def removeQuotes(self, string):
        if (string[0] == '"' and string[-1] == '"'):
            return string[1:-1]

        raise Exception('String does not contain quotes!')

    def backtracking2(self, v1, v2):
        if self.amount > 0:
            return

        self.path.append(v1)
        self.visited.add(v1)

        if v1 == v2:
            self.amount += 1
            self.finalPath += self.path[1:]
        else:
            graph = self.findVertexByName(v1)

            for v in graph[1]:
                if v not in self.visited:
                    self.backtracking2(v, v2)

        self.path.pop()
        self.visited.remove(v1)


if __name__ == '__main__':
    z = ZacarovaneUlice('subor2.txt')
    # print(z.trasa('abraka-dabra', 'k3'))
    # print(z.trasa('abraka-dabra-dabra', 'k3'))
    # print(z.trasa('abraka-abraka-abraka-dabra-dabra-dabra-dabra'))
    # print(z.graph)
    # print(z.start, z.ends)
    print(z.trasa('a'))