<jupyter_start><jupyter_text>Every ring member has its own class and store its location , destination and its situation for example he is grabbed by gandalf or not<jupyter_code>class Orc:
    def __init__(self,x,y,rank,id):
        self.x = x 
        self.y = y
        self.rank = rank
        self.id = id
    
    def setOrcsInTable(self,table):
        global m,n

        table[self.x][self.y].orcIsHere()
        table[self.x][self.y].orcIdSet(self.rank)
        
        for i in range(self.y - self.rank, self.y + self.rank + 1):
            if i in range(0,n):
                temp = self.rank - abs(i - self.y)
                for j in range(-temp, temp + 1):
                    if (self.x + j) in range(0,m): 
                        table[self.x + j][i].rangeRank(self.rank)
                        table[self.x + j][i].orcIdSet(self.id)

        return table<jupyter_output><empty_output><jupyter_text>Every orc has its own information and our programm has a list of orcs as well as ring members and it update table in "setOrcTable" actually gives table orc location and orc's watch distance<jupyter_code>class Node:

    def __init__(self, x, y):

        self.x = x 
        self.y = y
        self.f = 0
        self.g = 0
        self.h = 0
        self.neighbors = []
        self.neighborsDirection = []
        self.previous = None
        self.orc = False
        self.rank = DEFAULT
        self.orcId = DEFAULT

    def orcIsHere(self):
            self.orc = True

    def rangeRank(self,rank):
        self.rank = rank
        
    def orcIdSet(self,id):
        self.orcId = id
    
    def getLoc(self):
        return self.x,self.y

    def addNeighbors(self, table, columns, rows):

        neighbor_x = self.x
        neighbor_y = self.y
    
        if neighbor_x < columns - 1:
            self.neighbors.append(table[neighbor_x+1][neighbor_y])
            self.neighborsDirection.append("D")
        if neighbor_x > 0:
            self.neighbors.append(table[neighbor_x-1][neighbor_y])
            self.neighborsDirection.append("U")
        if neighbor_y < rows -1:
            self.neighbors.append(table[neighbor_x][neighbor_y +1])
            self.neighborsDirection.append("R")
        if neighbor_y > 0: 
            self.neighbors.append(table[neighbor_x][neighbor_y-1])
            self.neighborsDirection.append("L")<jupyter_output><empty_output><jupyter_text>Every cell of table is a instance of Node class,it can collect its neighbors in itself<jupyter_code>class AStar:

    def __init__(self, cols, rows, start, end):

        self.cols = cols
        self.rows = rows
        self.start = start
        self.end = end
        

 
    def cleanOpenSet(openSet, currentNode):

        for i in range(len(openSet)):
            if openSet[i] == currentNode:
                openSet.pop(i)
                break

        return openSet

    def fillTable(table):
        for i in range(n):
            for j in range(m):
                table[i][j] = Node(i,j)
        for i in range(len(orcs)):
            table = orcs[i].setOrcsInTable(table)

        return table
 
    def heu(currentNode, end):

        distance =  abs(currentNode.x - end.x) + abs(currentNode.y - end.y)
        
        return distance

 
    def createTable(cols, rows):

        table = [[0 for i in range(rows)]
                    for j in range(cols)]
        
        return table



    def startPath(openSet, closeSet, currentNode, end ,startFlag):
        for i in range(1):
            global danger

            bestWay = 0
            for i in range(len(openSet)):
                if openSet[i].f < openSet[bestWay].f:
                    bestWay = i

            currentNode = openSet[bestWay]

            if(startFlag == False):
                if((currentNode.previous.orcId == currentNode.orcId) and (currentNode.rank > 0)):
                    danger = danger+1
                elif(currentNode.previous.orcId != currentNode.orcId) and (currentNode.rank > 0):
                    danger = 1
                else:
                    danger = 0
                

            final_path = []
            if currentNode == end:
                temp = currentNode
                final_path.append(end)
                while temp.previous:
                    final_path.append(temp.previous)
                    temp = temp.previous
                temp = None
                final_path.reverse()
                final_path.append(currentNode)
                break

            openSet = AStar.cleanOpenSet(openSet, currentNode)
            closeSet.append(currentNode)
            if len(currentNode.neighbors) == 0:
                currentNode.addNeighbors(table,n,m)

            for neighbor in currentNode.neighbors:
                if (neighbor in closeSet) or (neighbor.orc == True) or ((danger+1 == neighbor.rank and neighbor.rank!=1)):
                        continue
                else:
                    temp_g = currentNode.g + 1
                    control_flag = 0
                    for k in range(len(openSet)):
                        if neighbor.x == openSet[k].x and neighbor.y == openSet[k].y:
                            if temp_g < openSet[k].g:
                                openSet[k].g = temp_g
                                openSet[k].h= AStar.heu(openSet[k], end)
                                openSet[k].f = openSet[k].g + openSet[k].h
                                openSet[k].previous = currentNode
                            else:
                                pass
                            control_flag = 1
    
                    if control_flag == 1:
                        pass
                    else:
                        neighbor.g = temp_g
                        neighbor.h = AStar.heu(neighbor, end)
                        neighbor.f = neighbor.g + neighbor.h
                        neighbor.previous = currentNode
                        openSet.append(neighbor)
        return openSet, closeSet, currentNode, final_path<jupyter_output><empty_output><jupyter_text>AStar class creates table ,calculate heuristic and f(n) and execute A* algorithm on table<jupyter_code>def gandalfDistUpdate():
    for i in range(len(ringMembers)):
        start = Node(gandalfX,gandalfY)
        end = Node(ringMembers[i].x,ringMembers[i].y)
        heus = AStar.heu(start,end)
        ringMembers[i].heu = heus
    ringMembers.sort(key=lambda x:x.heu)<jupyter_output><empty_output><jupyter_text>This function update gandalf loc and calculate heuristic from current gandalf location to every ring members and sort list of ring members by theirs heuristics.<jupyter_code>def inputManager():
    global m, n ,ringMembers
    global gandalfX , gandalfY ,gandorX,gandorY,orcs
    n, m = map(int, input().split())
    gandalfX, gandalfY = map(int, input().split())
    gandorX, gandorY = map(int, input().split())
    k, l = map(int, input().split())

    for j in range(k):
        unique_id = str(uuid4())
        x, y, rank = map(int, input().split())
        orcs.append(Orc(x,y,rank,unique_id)) 
    
    for j in range(l):
        unique_id = str(uuid4())
        x, y = map(int, input().split())
        ringMembers.append(RingMembers(x,y,unique_id))

    for j in range(l):
        x, y = map(int, input().split())
        ringMembers[j].setDest(x, y)
    
    gandalfDistUpdate()


    return<jupyter_output><empty_output><jupyter_text>This function manage input and create orc and ring members lists.<jupyter_code>def main():
    global gandalfX, gandalfY,table,answerCount
    finished = False
    directions = []    
    inputManager()
    table = AStar.createTable(n, m)
    table = AStar.fillTable(table)
    startFlag = True
    openSet  = []
    closeSet  = []
    
    final_path  = []
    start = time.time()
    while  finished == False:

        openSet.clear()
        closeSet.clear()
        final_path.clear()
        currentNode = None
        openSet.append(table[gandalfX][gandalfY])
        openSet[0].previous = None
        if len(ringMembers) == 0:
            end =table[gandorX][gandorY]
        elif ringMembers[0].grabbed == True:
            end = table[ringMembers[0].endX][ringMembers[0].endY]    
        else:
            end = table[ringMembers[0].x][ringMembers[0].y]

        while len(openSet) > 0:
            openSet, closeSet, currentNode, final_path = AStar.startPath(openSet, closeSet, currentNode,end,startFlag)
            startFlag = False
            if len(final_path) > 0:
                startFlag = True
                break
        
        for i in range(len(final_path)-1):
            temp = final_path[i+1]
            gandalfX = final_path[i].x
            gandalfY = final_path[i].y
            for j in range(len(final_path[i].neighbors)):
                if temp == final_path[i].neighbors[j]:
                    directions.append(final_path[i].neighborsDirection[j])
                    answerCount = answerCount+1

                    break
        if len(ringMembers) != 0:
            if ringMembers[0].grabbed == True and gandalfX == ringMembers[0].endX and gandalfY == ringMembers[0].endY:
                ringMembers[0].succeed = True
                ringMembers.pop(0)
                gandalfDistUpdate()
            elif gandalfX == ringMembers[0].x and gandalfY == ringMembers[0].y:
                ringMembers[0].grabbed = True

        if (gandalfX == gandorX) and (gandalfY == gandorY):
            finished = True
            break
    end = time.time()                
    print(str(directions))
    print(answerCount)
    print(end-start)
main()<jupyter_output>['R', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'D', 'D', 'D', 'L', 'L', 'L', 'L', 'D', 'L', 'L', 'L', 'D', 'D', 'R', 'U', 'U', 'R', 'R', 'U', 'R', 'R', 'D', 'R', 'D', 'D', 'R']
0.00128173828125
{'fraction_non_alphanumeric': 0.110952623535405, 'fraction_numerical': 0.006928171166581763, 'mean_word_length': 1.736548647895177, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '605199', 'license': 'MIT', 'n_tokens_mistral': 3123, 'n_tokens_neox': 2954, 'n_words': 687, 'path': 'report.ipynb', 'repo_name': 'Aliw7979/AStar-search-with-Gandalf', 'size': '9815'}