How to use conflict method in backstopjs

Best JavaScript code snippet using backstopjs

savedworkingastar.py

Source:savedworkingastar.py

1"""2Python example for this Rosetta Code task:3http://rosettacode.org/wiki/15_puzzle_solver4Using A* Algorithm from Wikkipedia:5https://en.wikipedia.org/wiki/A*_search_algorithm6Need to use heuristic that guarantees a shortest path7solution.8"""9import heapq10import copy11# Hopefully this is larger than any fscore or gscore12integer_infinity = 100000000013class Position(object):14    """Position class represents one position of a 15 puzzle"""15    def __init__(self, tiles):16        """17        Takes a tuple of tuples representing the tiles on a 4x4 puzzle board18        numbering 1-15 with 0 representing an empty square. For example:19        20        (( 1,  2,  3,  4),21         ( 5,  6,  7,  8),22         ( 9, 10, 11, 12),23         (13, 14, 15,  0))24         25        Converts list of lists representation into tuple of tuples.26        """27        if type(tiles) == type(list()):28            t = tiles29            self.tiles = ((t[0][0], t[0][1], t[0][2], t[0][3]),30                          (t[1][0], t[1][1], t[1][2], t[1][3]),        31                          (t[2][0], t[2][1], t[2][2], t[2][3]),        32                          (t[3][0], t[3][1], t[3][2], t[3][3]))33        else:34            self.tiles = tiles35            36        # fields for A* algorithm37        38        self.fscore = integer_infinity39        self.gscore = integer_infinity40        41        self.cameFrom = None42                        43    # setup for Priority Queue based on fscore44        45    def __lt__(self, other):46        return self.fscore < other.fscore47    48    def __le__(self, other):49        return self.fscore <= other.fscore50                51    def __gt__(self, other):52        return self.fscore > other.fscore53    54    def __ge__(self, other):55        return self.fscore >= other.fscore56       57    def __eq__(self, other):58        # compare two sets of tile positions59        if other == None:60            return False61            62        return (self.tiles == other.tiles)63                64    def __hash__(self):65        return hash(self.tiles)        66            67    def copy_tiles(self):68        """ returns list of lists version """69        t = self.tiles70        71        return [[t[0][0], t[0][1], t[0][2], t[0][3]],72                [t[1][0], t[1][1], t[1][2], t[1][3]],        73                [t[2][0], t[2][1], t[2][2], t[2][3]],        74                [t[3][0], t[3][1], t[3][2], t[3][3]]]        75        76    def neighbors(self):77        """78        returns a list of neighbors79        returns a list position objects with their80        directiontomoveto set to the direction that the81        empty square moved.82        83        tiles is 4x4 tuple of tuples with84        0,0 as top left.85    86        tiles[y][x]87        """88        89        # find 0 - blank square90        91        x0 = None92        y0 = None93        94        for i in range(4):95            for j in range(4):96                if self.tiles[i][j] == 0:97                    y0 = i98                    x0 = j99        if x0 == None or y0 == None:100            return []101            102        neighbor_list = []103            104        # move 0 to the right105        if x0 < 3:106            new_tiles = self.copy_tiles()107            temp = new_tiles[y0][x0+1]108            new_tiles[y0][x0+1] = 0109            new_tiles[y0][x0] = temp110            new_pos = new_position(new_tiles)111            neighbor_list.append(new_pos)112        # move 0 to the left113        if x0 > 0:114            new_tiles = self.copy_tiles()115            temp = new_tiles[y0][x0-1]116            new_tiles[y0][x0-1] = 0117            new_tiles[y0][x0] = temp118            new_pos = new_position(new_tiles)119            neighbor_list.append(new_pos)120        # move 0 up121        if y0 > 0:122            new_tiles = self.copy_tiles()123            temp = new_tiles[y0-1][x0]124            new_tiles[y0-1][x0] = 0125            new_tiles[y0][x0] = temp126            new_pos = new_position(new_tiles)127            neighbor_list.append(new_pos)128        # move 0 down129        if y0 < 3:130            new_tiles = self.copy_tiles()131            temp = new_tiles[y0+1][x0]132            new_tiles[y0+1][x0] = 0133            new_tiles[y0][x0] = temp134            new_pos = new_position(new_tiles)135            neighbor_list.append(new_pos)136            137        return neighbor_list138        139    def __repr__(self):140        # printable version of self141        142        return str(self.tiles[0])+'\n'+str(self.tiles[1])+'\n'+str(self.tiles[2])+'\n'+str(self.tiles[3])+'\n'143# takes tuple of tuples tiles as key, Position object for that tiles as value144all_positions = dict()145def new_position(tiles):146    """ returns a new position or looks up existing one """147    global all_positions148    if type(tiles) == type(list()):149        t = tiles150        tuptiles =   ((t[0][0], t[0][1], t[0][2], t[0][3]),151                      (t[1][0], t[1][1], t[1][2], t[1][3]),        152                      (t[2][0], t[2][1], t[2][2], t[2][3]),        153                      (t[3][0], t[3][1], t[3][2], t[3][3]))154    else:155        tuptiles = tiles156        157    if tuptiles in all_positions:158        return 	all_positions[tuptiles]159    else:160        new_pos = Position(tiles)161        all_positions[tuptiles] = new_pos162        return new_pos163                164def reconstruct_path(current):165    """ 166    Uses the cameFrom members to follow the chain of moves backwards167    and then reverses the list to get the path in the correct order.168    """169    total_path = [current]170    while current.cameFrom != None:171        current = current.cameFrom172        total_path.append(current)173        174    total_path.reverse()175    176    return total_path177        178class PriorityQueue(object):179    """180    Priority queue using heapq.181    elements of queue are (fscore,tiles) for each position.182    If element is removed from queue and fscore doesn't match183    then that element is discarded.184    """185    def __init__(self, object_list):186        """ 187        Save a list in a heapq.188        Assume that each object only appears once189        in the list.190        """191        self.queue_length = 0192        self.qheap = []193        for e in object_list:194            self.qheap.append((e.fscore,e.tiles))195            self.queue_length += 1196        heapq.heapify(self.qheap)197        198    def push(self, new_object):199        """ save object in heapq """200        heapq.heappush(self.qheap,(new_object.fscore,new_object.tiles))201        self.queue_length += 1202        203    def pop(self):204        """ remove object from heap and return """205        if self.queue_length < 1:206            return None207        fscore, tiles = heapq.heappop(self.qheap)208        self.queue_length -= 1209        global all_positions210        pos = all_positions[tiles]211        if pos.fscore == fscore:212            return pos213        else:214            return self.pop()215                216    def __repr__(self):217        # printable version of self218        strrep = ""219        for e in self.qheap:220          fscore, tiles = e221          strrep += str(fscore)+":"+str(tiles)+"\n"222        223        return strrep224        225conflict_table = None226def build_conflict_table():227    global conflict_table228    conflict_table = dict()229    230    # assumes goal tuple has up to 231    # for the given pattern it the start position232    # how much to add for linear conflicts233    # 2 per conflict - max of 6234    235    # goal tuple is ('g0', 'g1', 'g2', 'g3')236    237    conflict_table[('g0', 'g1', 'g2', 'g3')] = 0238    conflict_table[('g0', 'g1', 'g2', 'x')] = 0239    conflict_table[('g0', 'g1', 'g3', 'g2')] = 2240    conflict_table[('g0', 'g1', 'g3', 'x')] = 0241    conflict_table[('g0', 'g1', 'x', 'g2')] = 0242    conflict_table[('g0', 'g1', 'x', 'g3')] = 0243    conflict_table[('g0', 'g1', 'x', 'x')] = 0244    conflict_table[('g0', 'g2', 'g1', 'g3')] = 2245    conflict_table[('g0', 'g2', 'g1', 'x')] = 2246    conflict_table[('g0', 'g2', 'g3', 'g1')] = 4247    conflict_table[('g0', 'g2', 'g3', 'x')] = 0248    conflict_table[('g0', 'g2', 'x', 'g1')] = 2249    conflict_table[('g0', 'g2', 'x', 'g3')] = 0250    conflict_table[('g0', 'g2', 'x', 'x')] = 0251    conflict_table[('g0', 'g3', 'g1', 'g2')] = 4 252    conflict_table[('g0', 'g3', 'g1', 'x')] = 2253    conflict_table[('g0', 'g3', 'g2', 'g1')] = 4254    conflict_table[('g0', 'g3', 'g2', 'x')] = 2255    conflict_table[('g0', 'g3', 'x', 'g1')] = 2256    conflict_table[('g0', 'g3', 'x', 'g2')] = 2257    conflict_table[('g0', 'g3', 'x', 'x')] = 0258    conflict_table[('g0', 'x', 'g1', 'g2')] = 0259    conflict_table[('g0', 'x', 'g1', 'g3')] = 0260    conflict_table[('g0', 'x', 'g1', 'x')] = 0261    conflict_table[('g0', 'x', 'g2', 'g1')] = 2262    conflict_table[('g0', 'x', 'g2', 'g3')] = 0263    conflict_table[('g0', 'x', 'g2', 'x')] = 0264    conflict_table[('g0', 'x', 'g3', 'g1')] = 2265    conflict_table[('g0', 'x', 'g3', 'g2')] = 2266    conflict_table[('g0', 'x', 'g3', 'x')] = 0267    conflict_table[('g0', 'x', 'x', 'g1')] = 0268    conflict_table[('g0', 'x', 'x', 'g2')] = 0269    conflict_table[('g0', 'x', 'x', 'g3')] = 0270    conflict_table[('g1', 'g0', 'g2', 'g3')] = 2271    conflict_table[('g1', 'g0', 'g2', 'x')] = 2272    conflict_table[('g1', 'g0', 'g3', 'g2')] = 4 273    conflict_table[('g1', 'g0', 'g3', 'x')] = 2274    conflict_table[('g1', 'g0', 'x', 'g2')] = 2275    conflict_table[('g1', 'g0', 'x', 'g3')] = 2276    conflict_table[('g1', 'g0', 'x', 'x')] = 2277    conflict_table[('g1', 'g2', 'g0', 'g3')] = 4 278    conflict_table[('g1', 'g2', 'g0', 'x')] = 4279    conflict_table[('g1', 'g2', 'g3', 'g0')] = 6 280    conflict_table[('g1', 'g2', 'g3', 'x')] = 0281    conflict_table[('g1', 'g2', 'x', 'g0')] = 4282    conflict_table[('g1', 'g2', 'x', 'g3')] = 0283    conflict_table[('g1', 'g2', 'x', 'x')] = 0284    conflict_table[('g1', 'g3', 'g0', 'g2')] = 4 285    conflict_table[('g1', 'g3', 'g0', 'x')] = 4286    conflict_table[('g1', 'g3', 'g2', 'g0')] = 6 287    conflict_table[('g1', 'g3', 'g2', 'x')] = 0288    conflict_table[('g1', 'g3', 'x', 'g0')] = 4289    conflict_table[('g1', 'g3', 'x', 'g2')] = 2290    conflict_table[('g1', 'g3', 'x', 'x')] = 0291    conflict_table[('g1', 'x', 'g0', 'g2')] = 2292    conflict_table[('g1', 'x', 'g0', 'g3')] = 2293    conflict_table[('g1', 'x', 'g0', 'x')] = 2294    conflict_table[('g1', 'x', 'g2', 'g0')] = 4295    conflict_table[('g1', 'x', 'g2', 'g3')] = 0296    conflict_table[('g1', 'x', 'g2', 'x')] = 0297    conflict_table[('g1', 'x', 'g3', 'g0')] = 4298    conflict_table[('g1', 'x', 'g3', 'g2')] = 2299    conflict_table[('g1', 'x', 'g3', 'x')] = 0300    conflict_table[('g1', 'x', 'x', 'g0')] = 2301    conflict_table[('g1', 'x', 'x', 'g2')] = 0302    conflict_table[('g1', 'x', 'x', 'g3')] = 0303    conflict_table[('g2', 'g0', 'g1', 'g3')] = 4304    conflict_table[('g2', 'g0', 'g1', 'x')] = 4305    conflict_table[('g2', 'g0', 'g3', 'g1')] = 4306    conflict_table[('g2', 'g0', 'g3', 'x')] = 2307    conflict_table[('g2', 'g0', 'x', 'g1')] = 4308    conflict_table[('g2', 'g0', 'x', 'g3')] = 2309    conflict_table[('g2', 'g0', 'x', 'x')] = 2310    conflict_table[('g2', 'g1', 'g0', 'g3')] = 4311    conflict_table[('g2', 'g1', 'g0', 'x')] = 4312    conflict_table[('g2', 'g1', 'g3', 'g0')] = 6313    conflict_table[('g2', 'g1', 'g3', 'x')] = 2314    conflict_table[('g2', 'g1', 'x', 'g0')] = 4315    conflict_table[('g2', 'g1', 'x', 'g3')] = 2316    conflict_table[('g2', 'g1', 'x', 'x')] = 2317    conflict_table[('g2', 'g3', 'g0', 'g1')] = 4318    conflict_table[('g2', 'g3', 'g0', 'x')] = 4319    conflict_table[('g2', 'g3', 'g1', 'g0')] = 6320    conflict_table[('g2', 'g3', 'g1', 'x')] = 4321    conflict_table[('g2', 'g3', 'x', 'g0')] = 4322    conflict_table[('g2', 'g3', 'x', 'g1')] = 4323    conflict_table[('g2', 'g3', 'x', 'x')] = 0324    conflict_table[('g2', 'x', 'g0', 'g1')] = 4325    conflict_table[('g2', 'x', 'g0', 'g3')] = 2326    conflict_table[('g2', 'x', 'g0', 'x')] = 2327    conflict_table[('g2', 'x', 'g1', 'g0')] = 4328    conflict_table[('g2', 'x', 'g1', 'g3')] = 2329    conflict_table[('g2', 'x', 'g1', 'x')] = 2330    conflict_table[('g2', 'x', 'g3', 'g0')] = 4331    conflict_table[('g2', 'x', 'g3', 'g1')] = 4332    conflict_table[('g2', 'x', 'g3', 'x')] = 0333    conflict_table[('g2', 'x', 'x', 'g0')] = 2334    conflict_table[('g2', 'x', 'x', 'g1')] = 2335    conflict_table[('g2', 'x', 'x', 'g3')] = 0336    conflict_table[('g3', 'g0', 'g1', 'g2')] = 6337    conflict_table[('g3', 'g0', 'g1', 'x')] = 4338    conflict_table[('g3', 'g0', 'g2', 'g1')] = 6339    conflict_table[('g3', 'g0', 'g2', 'x')] = 4340    conflict_table[('g3', 'g0', 'x', 'g1')] = 4341    conflict_table[('g3', 'g0', 'x', 'g2')] = 4342    conflict_table[('g3', 'g0', 'x', 'x')] = 2343    conflict_table[('g3', 'g1', 'g0', 'g2')] = 6344    conflict_table[('g3', 'g1', 'g0', 'x')] = 4345    conflict_table[('g3', 'g1', 'g2', 'g0')] = 6346    conflict_table[('g3', 'g1', 'g2', 'x')] = 4347    conflict_table[('g3', 'g1', 'x', 'g0')] = 4348    conflict_table[('g3', 'g1', 'x', 'g2')] = 4349    conflict_table[('g3', 'g1', 'x', 'x')] = 2350    conflict_table[('g3', 'g2', 'g0', 'g1')] = 6351    conflict_table[('g3', 'g2', 'g0', 'x')] = 4352    conflict_table[('g3', 'g2', 'g1', 'g0')] = 6353    conflict_table[('g3', 'g2', 'g1', 'x')] = 4354    conflict_table[('g3', 'g2', 'x', 'g0')] = 4355    conflict_table[('g3', 'g2', 'x', 'g1')] = 4356    conflict_table[('g3', 'g2', 'x', 'x')] = 2357    conflict_table[('g3', 'x', 'g0', 'g1')] = 4358    conflict_table[('g3', 'x', 'g0', 'g2')] = 4359    conflict_table[('g3', 'x', 'g0', 'x')] = 2360    conflict_table[('g3', 'x', 'g1', 'g0')] = 4361    conflict_table[('g3', 'x', 'g1', 'g2')] = 4362    conflict_table[('g3', 'x', 'g1', 'x')] = 2363    conflict_table[('g3', 'x', 'g2', 'g0')] = 4364    conflict_table[('g3', 'x', 'g2', 'g1')] = 4365    conflict_table[('g3', 'x', 'g2', 'x')] = 2366    conflict_table[('g3', 'x', 'x', 'g0')] = 2367    conflict_table[('g3', 'x', 'x', 'g1')] = 2368    conflict_table[('g3', 'x', 'x', 'g2')] = 2369    conflict_table[('x', 'g0', 'g1', 'g2')] = 0370    conflict_table[('x', 'g0', 'g1', 'g3')] = 0371    conflict_table[('x', 'g0', 'g1', 'x')] = 0372    conflict_table[('x', 'g0', 'g2', 'g1')] = 2373    conflict_table[('x', 'g0', 'g2', 'g3')] = 0374    conflict_table[('x', 'g0', 'g2', 'x')] = 0375    conflict_table[('x', 'g0', 'g3', 'g1')] = 2376    conflict_table[('x', 'g0', 'g3', 'g2')] = 2377    conflict_table[('x', 'g0', 'g3', 'x')] = 0378    conflict_table[('x', 'g0', 'x', 'g1')] = 0379    conflict_table[('x', 'g0', 'x', 'g2')] = 0380    conflict_table[('x', 'g0', 'x', 'g3')] = 0381    conflict_table[('x', 'g1', 'g0', 'g2')] = 2382    conflict_table[('x', 'g1', 'g0', 'g3')] = 2383    conflict_table[('x', 'g1', 'g0', 'x')] = 2384    conflict_table[('x', 'g1', 'g2', 'g0')] = 4385    conflict_table[('x', 'g1', 'g2', 'g3')] = 0386    conflict_table[('x', 'g1', 'g2', 'x')] = 0387    conflict_table[('x', 'g1', 'g3', 'g0')] = 4388    conflict_table[('x', 'g1', 'g3', 'g2')] = 2389    conflict_table[('x', 'g1', 'g3', 'x')] = 0390    conflict_table[('x', 'g1', 'x', 'g0')] = 2391    conflict_table[('x', 'g1', 'x', 'g2')] = 0392    conflict_table[('x', 'g1', 'x', 'g3')] = 0393    conflict_table[('x', 'g2', 'g0', 'g1')] = 4394    conflict_table[('x', 'g2', 'g0', 'g3')] = 2395    conflict_table[('x', 'g2', 'g0', 'x')] = 2396    conflict_table[('x', 'g2', 'g1', 'g0')] = 4397    conflict_table[('x', 'g2', 'g1', 'g3')] = 2398    conflict_table[('x', 'g2', 'g1', 'x')] = 2399    conflict_table[('x', 'g2', 'g3', 'g0')] = 4400    conflict_table[('x', 'g2', 'g3', 'g1')] = 4401    conflict_table[('x', 'g2', 'g3', 'x')] = 0402    conflict_table[('x', 'g2', 'x', 'g0')] = 2403    conflict_table[('x', 'g2', 'x', 'g1')] = 2404    conflict_table[('x', 'g2', 'x', 'g3')] = 0405    conflict_table[('x', 'g3', 'g0', 'g1')] = 4406    conflict_table[('x', 'g3', 'g0', 'g2')] = 4407    conflict_table[('x', 'g3', 'g0', 'x')] = 2408    conflict_table[('x', 'g3', 'g1', 'g0')] = 4409    conflict_table[('x', 'g3', 'g1', 'g2')] = 4410    conflict_table[('x', 'g3', 'g1', 'x')] = 2411    conflict_table[('x', 'g3', 'g2', 'g0')] = 4412    conflict_table[('x', 'g3', 'g2', 'g1')] = 4413    conflict_table[('x', 'g3', 'g2', 'x')] = 2414    conflict_table[('x', 'g3', 'x', 'g0')] = 2415    conflict_table[('x', 'g3', 'x', 'g1')] = 2416    conflict_table[('x', 'g3', 'x', 'g2')] = 2417    conflict_table[('x', 'x', 'g0', 'g1')] = 0418    conflict_table[('x', 'x', 'g0', 'g2')] = 0419    conflict_table[('x', 'x', 'g0', 'g3')] = 0420    conflict_table[('x', 'x', 'g1', 'g0')] = 2421    conflict_table[('x', 'x', 'g1', 'g2')] = 0422    conflict_table[('x', 'x', 'g1', 'g3')] = 0423    conflict_table[('x', 'x', 'g2', 'g0')] = 2424    conflict_table[('x', 'x', 'g2', 'g1')] = 2425    conflict_table[('x', 'x', 'g2', 'g3')] = 0426    conflict_table[('x', 'x', 'g3', 'g0')] = 2427    conflict_table[('x', 'x', 'g3', 'g1')] = 2428    conflict_table[('x', 'x', 'g3', 'g2')] = 2429        430def linear_conflicts(start_list,goal_list):431    """432    calculates number of moves to add to the estimate of433    the moves to get from start to goal based on the number434    of conflicts on a given row or column. start_list435    represents the current location and goal_list represnts436    the final goal.437    """438    439    # Find which of the tiles in start_list have their goals on this line440    # build a pattern to use in a lookup table of this form:441    # g0, g1, g3, g3 fill in x where there is no goal for this line442    443    # all 'x' until we file a tile whose goal is in this line444    445    goal_pattern = ['x', 'x', 'x', 'x']446    447    for g in range(4):448        for s in range(4):449            start_tile_num = start_list[s]450            if start_tile_num == goal_list[g] and start_tile_num != 0:451                goal_pattern[s] = 'g' + str(g) # i.e. g0452                                453    global conflict_table454    455    tup_goal_pattern = tuple(goal_pattern)456    457    if tup_goal_pattern in conflict_table:458        return conflict_table[tuple(goal_pattern)]459    else:460        return 0461    462class lcmap(dict):463    """ 464    Lets you return 0 if you look for an object that465    is not in the dictionary. 466    """467    def __missing__(self, key):468        return 0469def listconflicts(goal_list):470    """ 471    list all possible start lists that will have at least472    one linear conflict.473    474    Possible goal tile configurations475    476    g g g g477    g g g x478    g g x g479    g x g g480    x g g g481    g g x x482    g x g x483    g x x g484    x g g x485    x g x g486    x x g g487        488    """489    490    all_tiles = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]491    492    non_goal_tiles = []493    494    for t in all_tiles:495        if t not in goal_list:496            non_goal_tiles.append(t) 497            498    combinations = lcmap()499    # g g g g500    501    for i in goal_list:502        tile_list2 = goal_list[:]503        tile_list2.remove(i)504        for j in tile_list2:505            tile_list3 = tile_list2[:]506            tile_list3.remove(j)507            for k in tile_list3:508                tile_list4 = tile_list3[:]509                tile_list4.remove(k)510                for l in tile_list4:511                    start_list = (i, j, k, l)512                    conflictadd = linear_conflicts(start_list,goal_list)513                    if conflictadd > 0:514                        combinations[start_list]=conflictadd    515    516    # g g g x517    518    for i in goal_list:519        tile_list2 = goal_list[:]520        tile_list2.remove(i)521        for j in tile_list2:522            tile_list3 = tile_list2[:]523            tile_list3.remove(j)524            for k in tile_list3:525                for l in non_goal_tiles:526                    start_list = (i, j, k, l)527                    conflictadd = linear_conflicts(start_list,goal_list)528                    if conflictadd > 0:529                        combinations[start_list]=conflictadd  530    # g g x g531    532    for i in goal_list:533        tile_list2 = goal_list[:]534        tile_list2.remove(i)535        for j in tile_list2:536            tile_list3 = tile_list2[:]537            tile_list3.remove(j)538            for k in non_goal_tiles:539                for l in tile_list3:540                    start_list = (i, j, k, l)541                    conflictadd = linear_conflicts(start_list,goal_list)542                    if conflictadd > 0:543                        combinations[start_list]=conflictadd544    # g x g g545    546    for i in goal_list:547        tile_list2 = goal_list[:]548        tile_list2.remove(i)549        for j in non_goal_tiles:550            for k in tile_list2:551                tile_list3 = tile_list2[:]552                tile_list3.remove(k)553                for l in tile_list3:554                    start_list = (i, j, k, l)555                    conflictadd = linear_conflicts(start_list,goal_list)556                    if conflictadd > 0:557                        combinations[start_list]=conflictadd558    # x g g g559    560    for i in non_goal_tiles:561        for j in goal_list:562            tile_list2 = goal_list[:]563            tile_list2.remove(j)564            for k in tile_list2:565                tile_list3 = tile_list2[:]566                tile_list3.remove(k)567                for l in tile_list3:568                    start_list = (i, j, k, l)569                    conflictadd = linear_conflicts(start_list,goal_list)570                    if conflictadd > 0:571                        combinations[start_list]=conflictadd572    # g g x x573    for i in goal_list:574        tile_list2 = goal_list[:]575        tile_list2.remove(i)576        for j in tile_list2:577            tile_list3 = tile_list2[:]578            tile_list3.remove(j)579            for k in non_goal_tiles:580                tile_list4 = non_goal_tiles[:]581                tile_list4.remove(k)582                for l in tile_list4:583                    start_list = (i, j, k, l)584                    conflictadd = linear_conflicts(start_list,goal_list)585                    if conflictadd > 0:586                        combinations[start_list]=conflictadd 587                        588    # g x g x589    for i in goal_list:590        tile_list2 = goal_list[:]591        tile_list2.remove(i)592        for j in non_goal_tiles:593            tile_list3 = non_goal_tiles[:]594            tile_list3.remove(j)595            for k in tile_list2:596                for l in tile_list3:597                    start_list = (i, j, k, l)598                    conflictadd = linear_conflicts(start_list,goal_list)599                    if conflictadd > 0:600                        combinations[start_list]=conflictadd    601                        602    # g x x g603    for i in goal_list:604        tile_list2 = goal_list[:]605        tile_list2.remove(i)606        for j in non_goal_tiles:607            tile_list3 = non_goal_tiles[:]608            tile_list3.remove(j)609            for k in tile_list2:610                for l in tile_list3:611                    start_list = (i, j, k, l)612                    conflictadd = linear_conflicts(start_list,goal_list)613                    if conflictadd > 0:614                        combinations[start_list]=conflictadd     615    616    # x g g x617    for i in non_goal_tiles:618        tile_list2 = non_goal_tiles[:]619        tile_list2.remove(i)620        for j in goal_list:621            tile_list3 = goal_list[:]622            tile_list3.remove(j)623            for k in tile_list3:624                for l in tile_list2:625                    start_list = (i, j, k, l)626                    conflictadd = linear_conflicts(start_list,goal_list)627                    if conflictadd > 0:628                        combinations[start_list]=conflictadd      629    630    # x g x g631    632    for i in non_goal_tiles:633        tile_list2 = non_goal_tiles[:]634        tile_list2.remove(i)635        for j in goal_list:636            tile_list3 = goal_list[:]637            tile_list3.remove(j)638            for k in tile_list3:639                for l in tile_list2:640                    start_list = (i, j, k, l)641                    conflictadd = linear_conflicts(start_list,goal_list)642                    if conflictadd > 0:643                        combinations[start_list]=conflictadd      644      645    # x x g g646    647    for i in non_goal_tiles:648        tile_list2 = non_goal_tiles[:]649        tile_list2.remove(i)650        for j in tile_list2:651            for k in goal_list:652                tile_list3 = goal_list[:]653                tile_list3.remove(k)654                for l in tile_list3:655                    start_list = (i, j, k, l)656                    conflictadd = linear_conflicts(start_list,goal_list)657                    if conflictadd > 0:658                        combinations[start_list]=conflictadd      659      660    return combinations661class HeuristicObj(object):662    """ Object used to preprocess goal position for heuristic function """663    def __init__(self, goal):664        """665        Preprocess goal position to setup internal data structures666        that can be used to speed up heuristic.667        """668        669        build_conflict_table()670        671        self.goal_map = []672        for i in range(16):673            self.goal_map.append(i)    674        675        self.goal_lists = goal.tiles676        677        # preprocess for manhattan distance678        679        for row in range(4):680            for col in range(4):681                self.goal_map[goal.tiles[row][col]] = (row, col)682                683        # preprocess for linear conflicts684        685        self.row_conflicts = []686        for row in range(4):687            t = goal.tiles[row]688            conf_dict = listconflicts([t[0],t[1],t[2],t[3]])689            self.row_conflicts.append(conf_dict)690            691        self.col_conflicts = []692        for col in range(4):693            col_list =[]694            for row in range(4):695                col_list.append(goal.tiles[row][col])696            conf_dict = listconflicts(col_list)697            self.col_conflicts.append(conf_dict)698    def heuristic(self, start):699        """ 700        701        Estimates the number of moves from start to goal.702        The goal was preprocessed in __init__.703        704        """705        706        distance = 0707        708        # calculate manhattan distance709        710        for row in range(4):711            for col in range(4):712                start_tilenum = start.tiles[row][col]713                if start_tilenum != 0:714                    (grow, gcol) = self.goal_map[start_tilenum]715                    distance += abs(row - grow) + abs(col - gcol)716                                        717        # add linear conflicts 718        719        for row in range(4):720            curr_row = start.tiles[row]721            distance += self.row_conflicts[row][curr_row]722       723        for col in range(4):724            col_list =[]725            for row in range(4):726                col_list.append(start.tiles[row][col])727            col_tuple = tuple(col_list)728            distance += self.col_conflicts[col][col_tuple]729          730        return distance731        732# global variable for heuristic object733hob = None734        735def a_star(start_tiles, goal_tiles):736    """ Based on https://en.wikipedia.org/wiki/A*_search_algorithm """737    738    start = new_position(start_tiles)739    goal = new_position(goal_tiles)740    741    # Process goal position for use in heuristic742    743    global hob744    hob = HeuristicObj(goal)745    746    # The set of currently discovered nodes that are not evaluated yet.747    # Initially, only the start node is known.748    # For the first node, the fscore is completely heuristic.749    750    start.fscore = hob.heuristic(start)751    openSet = PriorityQueue([start])752 753    # The cost of going from start to start is zero.754    755    start.gscore = 0756    757    num_popped = 0758    759    while openSet.queue_length > 0:760        current = openSet.pop()761        if current == None: # tried to pop but only found old fscore values762            break763        num_popped += 1764        if num_popped % 100000 == 0:765            print(str(num_popped)+" positions examined")766        767        if current == goal:768            return reconstruct_path(current)769            770        for neighbor in current.neighbors():771            # The distance from start to a neighbor772            # All nodes are 1 move from their neighbors773            774            tentative_gScore = current.gscore + 1775            776            # update gscore and fscore if this is shorter path777            # to the neighbor node778            if tentative_gScore < neighbor.gscore: 779                neighbor.cameFrom = current780                neighbor.gscore = tentative_gScore781                neighbor.fscore = neighbor.gscore + hob.heuristic(neighbor)782                openSet.push(neighbor) # add to open set every time783                784def find_zero(tiles):785    """ file the 0 tile """786    for row in range(4):787        for col in range(4):788            if tiles[row][col] == 0:789                return (row, col)790def path_as_0_moves(path):791    """792    Takes the path which is a list of Position793    objects and outputs it as a string of rlud 794    directions to match output desired by 795    Rosetta Code task.796    """797    strpath = ""798    if len(path) < 1:799        return ""800    prev_pos = path[0]801    p_row, p_col = find_zero(prev_pos.tiles)802    for i in range(1,len(path)):803        curr_pos = path[i]804        c_row, c_col = find_zero(curr_pos.tiles)805        if c_row > p_row:806            strpath += 'd'807        elif c_row < p_row:808            strpath += 'u'809        elif c_col > p_col:810            strpath += 'r'811        elif c_col < p_col:812            strpath += 'l'813        # reset for next loop814        prev_pos = curr_pos815        p_row = c_row816        p_col = c_col817    return strpath...

astar.py

Source:astar.py

1"""2Python example for this Rosetta Code task:3http://rosettacode.org/wiki/15_puzzle_solver4Using A* Algorithm from Wikkipedia:5https://en.wikipedia.org/wiki/A*_search_algorithm6Need to use heuristic that guarantees a shortest path7solution.8"""9import heapq10import copy11# Hopefully this is larger than any fscore or gscore12integer_infinity = 100000000013class Position(object):14    """Position class represents one position of a 15 puzzle"""15    def __init__(self, tiles):16        """17        Takes a tuple of tuples representing the tiles on a 4x4 puzzle board18        numbering 1-15 with 0 representing an empty square. For example:19        20        (( 1,  2,  3,  4),21         ( 5,  6,  7,  8),22         ( 9, 10, 11, 12),23         (13, 14, 15,  0))24         25        Converts list of lists representation into tuple of tuples.26        """27        if type(tiles) == type(list()):28            t = tiles29            self.tiles = ((t[0][0], t[0][1], t[0][2], t[0][3]),30                          (t[1][0], t[1][1], t[1][2], t[1][3]),        31                          (t[2][0], t[2][1], t[2][2], t[2][3]),        32                          (t[3][0], t[3][1], t[3][2], t[3][3]))33        else:34            self.tiles = tiles35            36        # fields for A* algorithm37        38        self.fscore = integer_infinity39        self.gscore = integer_infinity40        41        self.cameFrom = None42                                    43    def copy_tiles(self):44        """ returns list of lists version """45        t = self.tiles46        47        return [[t[0][0], t[0][1], t[0][2], t[0][3]],48                [t[1][0], t[1][1], t[1][2], t[1][3]],        49                [t[2][0], t[2][1], t[2][2], t[2][3]],        50                [t[3][0], t[3][1], t[3][2], t[3][3]]]        51        52    def neighbors(self):53        """54        returns a list of neighbors55        returns a list position objects with their56        directiontomoveto set to the direction that the57        empty square moved.58        59        tiles is 4x4 tuple of tuples with60        0,0 as top left.61    62        tiles[y][x]63        """64        65        # find 0 - blank square66        67        x0 = None68        y0 = None69        70        for i in range(4):71            for j in range(4):72                if self.tiles[i][j] == 0:73                    y0 = i74                    x0 = j75        if x0 == None or y0 == None:76            return []77            78        neighbor_list = []79            80        # move 0 to the right81        if x0 < 3:82            new_tiles = self.copy_tiles()83            temp = new_tiles[y0][x0+1]84            new_tiles[y0][x0+1] = 085            new_tiles[y0][x0] = temp86            new_pos = new_position(new_tiles)87            neighbor_list.append(new_pos)88        # move 0 to the left89        if x0 > 0:90            new_tiles = self.copy_tiles()91            temp = new_tiles[y0][x0-1]92            new_tiles[y0][x0-1] = 093            new_tiles[y0][x0] = temp94            new_pos = new_position(new_tiles)95            neighbor_list.append(new_pos)96        # move 0 up97        if y0 > 0:98            new_tiles = self.copy_tiles()99            temp = new_tiles[y0-1][x0]100            new_tiles[y0-1][x0] = 0101            new_tiles[y0][x0] = temp102            new_pos = new_position(new_tiles)103            neighbor_list.append(new_pos)104        # move 0 down105        if y0 < 3:106            new_tiles = self.copy_tiles()107            temp = new_tiles[y0+1][x0]108            new_tiles[y0+1][x0] = 0109            new_tiles[y0][x0] = temp110            new_pos = new_position(new_tiles)111            neighbor_list.append(new_pos)112            113        return neighbor_list114        115    def __repr__(self):116        # printable version of self117        118        return str(self.tiles[0])+'\n'+str(self.tiles[1])+'\n'+str(self.tiles[2])+'\n'+str(self.tiles[3])+'\n'119# takes tuple of tuples tiles as key, Position object for that tiles as value120all_positions = dict()121def new_position(tiles):122    """ returns a new position or looks up existing one """123    global all_positions124    if type(tiles) == type(list()):125        t = tiles126        tuptiles =   ((t[0][0], t[0][1], t[0][2], t[0][3]),127                      (t[1][0], t[1][1], t[1][2], t[1][3]),        128                      (t[2][0], t[2][1], t[2][2], t[2][3]),        129                      (t[3][0], t[3][1], t[3][2], t[3][3]))130    else:131        tuptiles = tiles132        133    if tuptiles in all_positions:134        return 	all_positions[tuptiles]135    else:136        new_pos = Position(tiles)137        all_positions[tuptiles] = new_pos138        return new_pos139                140def reconstruct_path(current):141    """ 142    Uses the cameFrom members to follow the chain of moves backwards143    and then reverses the list to get the path in the correct order.144    """145    total_path = [current]146    while current.cameFrom != None:147        current = current.cameFrom148        total_path.append(current)149        150    total_path.reverse()151    152    return total_path153        154class PriorityQueue(object):155    """156    Priority queue using heapq.157    elements of queue are (fscore,tiles) for each position.158    If element is removed from queue and fscore doesn't match159    then that element is discarded.160    """161    def __init__(self, object_list):162        """ 163        Save a list in a heapq.164        Assume that each object only appears once165        in the list.166        """167        self.queue_length = 0168        self.qheap = []169        for e in object_list:170            self.qheap.append((e.fscore,e.tiles))171            self.queue_length += 1172        heapq.heapify(self.qheap)173        174    def push(self, new_object):175        """ save object in heapq """176        heapq.heappush(self.qheap,(new_object.fscore,new_object.tiles))177        self.queue_length += 1178        179    def pop(self):180        """ remove object from heap and return """181        if self.queue_length < 1:182            return None183        fscore, tiles = heapq.heappop(self.qheap)184        self.queue_length -= 1185        global all_positions186        pos = all_positions[tiles]187        if pos.fscore == fscore:188            return pos189        else:190            return self.pop()191                192    def __repr__(self):193        # printable version of self194        strrep = ""195        for e in self.qheap:196          fscore, tiles = e197          strrep += str(fscore)+":"+str(tiles)+"\n"198        199        return strrep200        201conflict_table = None202def build_conflict_table():203    global conflict_table204    conflict_table = dict()205    206    # assumes goal tuple has up to 207    # for the given pattern it the start position208    # how much to add for linear conflicts209    # 2 per conflict - max of 6210    211    # goal tuple is ('g0', 'g1', 'g2', 'g3')212    213    conflict_table[('g0', 'g1', 'g2', 'g3')] = 0214    conflict_table[('g0', 'g1', 'g2', 'x')] = 0215    conflict_table[('g0', 'g1', 'g3', 'g2')] = 2216    conflict_table[('g0', 'g1', 'g3', 'x')] = 0217    conflict_table[('g0', 'g1', 'x', 'g2')] = 0218    conflict_table[('g0', 'g1', 'x', 'g3')] = 0219    conflict_table[('g0', 'g1', 'x', 'x')] = 0220    conflict_table[('g0', 'g2', 'g1', 'g3')] = 2221    conflict_table[('g0', 'g2', 'g1', 'x')] = 2222    conflict_table[('g0', 'g2', 'g3', 'g1')] = 4223    conflict_table[('g0', 'g2', 'g3', 'x')] = 0224    conflict_table[('g0', 'g2', 'x', 'g1')] = 2225    conflict_table[('g0', 'g2', 'x', 'g3')] = 0226    conflict_table[('g0', 'g2', 'x', 'x')] = 0227    conflict_table[('g0', 'g3', 'g1', 'g2')] = 4 228    conflict_table[('g0', 'g3', 'g1', 'x')] = 2229    conflict_table[('g0', 'g3', 'g2', 'g1')] = 4230    conflict_table[('g0', 'g3', 'g2', 'x')] = 2231    conflict_table[('g0', 'g3', 'x', 'g1')] = 2232    conflict_table[('g0', 'g3', 'x', 'g2')] = 2233    conflict_table[('g0', 'g3', 'x', 'x')] = 0234    conflict_table[('g0', 'x', 'g1', 'g2')] = 0235    conflict_table[('g0', 'x', 'g1', 'g3')] = 0236    conflict_table[('g0', 'x', 'g1', 'x')] = 0237    conflict_table[('g0', 'x', 'g2', 'g1')] = 2238    conflict_table[('g0', 'x', 'g2', 'g3')] = 0239    conflict_table[('g0', 'x', 'g2', 'x')] = 0240    conflict_table[('g0', 'x', 'g3', 'g1')] = 2241    conflict_table[('g0', 'x', 'g3', 'g2')] = 2242    conflict_table[('g0', 'x', 'g3', 'x')] = 0243    conflict_table[('g0', 'x', 'x', 'g1')] = 0244    conflict_table[('g0', 'x', 'x', 'g2')] = 0245    conflict_table[('g0', 'x', 'x', 'g3')] = 0246    conflict_table[('g1', 'g0', 'g2', 'g3')] = 2247    conflict_table[('g1', 'g0', 'g2', 'x')] = 2248    conflict_table[('g1', 'g0', 'g3', 'g2')] = 4 249    conflict_table[('g1', 'g0', 'g3', 'x')] = 2250    conflict_table[('g1', 'g0', 'x', 'g2')] = 2251    conflict_table[('g1', 'g0', 'x', 'g3')] = 2252    conflict_table[('g1', 'g0', 'x', 'x')] = 2253    conflict_table[('g1', 'g2', 'g0', 'g3')] = 4 254    conflict_table[('g1', 'g2', 'g0', 'x')] = 4255    conflict_table[('g1', 'g2', 'g3', 'g0')] = 6 256    conflict_table[('g1', 'g2', 'g3', 'x')] = 0257    conflict_table[('g1', 'g2', 'x', 'g0')] = 4258    conflict_table[('g1', 'g2', 'x', 'g3')] = 0259    conflict_table[('g1', 'g2', 'x', 'x')] = 0260    conflict_table[('g1', 'g3', 'g0', 'g2')] = 4 261    conflict_table[('g1', 'g3', 'g0', 'x')] = 4262    conflict_table[('g1', 'g3', 'g2', 'g0')] = 6 263    conflict_table[('g1', 'g3', 'g2', 'x')] = 0264    conflict_table[('g1', 'g3', 'x', 'g0')] = 4265    conflict_table[('g1', 'g3', 'x', 'g2')] = 2266    conflict_table[('g1', 'g3', 'x', 'x')] = 0267    conflict_table[('g1', 'x', 'g0', 'g2')] = 2268    conflict_table[('g1', 'x', 'g0', 'g3')] = 2269    conflict_table[('g1', 'x', 'g0', 'x')] = 2270    conflict_table[('g1', 'x', 'g2', 'g0')] = 4271    conflict_table[('g1', 'x', 'g2', 'g3')] = 0272    conflict_table[('g1', 'x', 'g2', 'x')] = 0273    conflict_table[('g1', 'x', 'g3', 'g0')] = 4274    conflict_table[('g1', 'x', 'g3', 'g2')] = 2275    conflict_table[('g1', 'x', 'g3', 'x')] = 0276    conflict_table[('g1', 'x', 'x', 'g0')] = 2277    conflict_table[('g1', 'x', 'x', 'g2')] = 0278    conflict_table[('g1', 'x', 'x', 'g3')] = 0279    conflict_table[('g2', 'g0', 'g1', 'g3')] = 4280    conflict_table[('g2', 'g0', 'g1', 'x')] = 4281    conflict_table[('g2', 'g0', 'g3', 'g1')] = 4282    conflict_table[('g2', 'g0', 'g3', 'x')] = 2283    conflict_table[('g2', 'g0', 'x', 'g1')] = 4284    conflict_table[('g2', 'g0', 'x', 'g3')] = 2285    conflict_table[('g2', 'g0', 'x', 'x')] = 2286    conflict_table[('g2', 'g1', 'g0', 'g3')] = 4287    conflict_table[('g2', 'g1', 'g0', 'x')] = 4288    conflict_table[('g2', 'g1', 'g3', 'g0')] = 6289    conflict_table[('g2', 'g1', 'g3', 'x')] = 2290    conflict_table[('g2', 'g1', 'x', 'g0')] = 4291    conflict_table[('g2', 'g1', 'x', 'g3')] = 2292    conflict_table[('g2', 'g1', 'x', 'x')] = 2293    conflict_table[('g2', 'g3', 'g0', 'g1')] = 4294    conflict_table[('g2', 'g3', 'g0', 'x')] = 4295    conflict_table[('g2', 'g3', 'g1', 'g0')] = 6296    conflict_table[('g2', 'g3', 'g1', 'x')] = 4297    conflict_table[('g2', 'g3', 'x', 'g0')] = 4298    conflict_table[('g2', 'g3', 'x', 'g1')] = 4299    conflict_table[('g2', 'g3', 'x', 'x')] = 0300    conflict_table[('g2', 'x', 'g0', 'g1')] = 4301    conflict_table[('g2', 'x', 'g0', 'g3')] = 2302    conflict_table[('g2', 'x', 'g0', 'x')] = 2303    conflict_table[('g2', 'x', 'g1', 'g0')] = 4304    conflict_table[('g2', 'x', 'g1', 'g3')] = 2305    conflict_table[('g2', 'x', 'g1', 'x')] = 2306    conflict_table[('g2', 'x', 'g3', 'g0')] = 4307    conflict_table[('g2', 'x', 'g3', 'g1')] = 4308    conflict_table[('g2', 'x', 'g3', 'x')] = 0309    conflict_table[('g2', 'x', 'x', 'g0')] = 2310    conflict_table[('g2', 'x', 'x', 'g1')] = 2311    conflict_table[('g2', 'x', 'x', 'g3')] = 0312    conflict_table[('g3', 'g0', 'g1', 'g2')] = 6313    conflict_table[('g3', 'g0', 'g1', 'x')] = 4314    conflict_table[('g3', 'g0', 'g2', 'g1')] = 6315    conflict_table[('g3', 'g0', 'g2', 'x')] = 4316    conflict_table[('g3', 'g0', 'x', 'g1')] = 4317    conflict_table[('g3', 'g0', 'x', 'g2')] = 4318    conflict_table[('g3', 'g0', 'x', 'x')] = 2319    conflict_table[('g3', 'g1', 'g0', 'g2')] = 6320    conflict_table[('g3', 'g1', 'g0', 'x')] = 4321    conflict_table[('g3', 'g1', 'g2', 'g0')] = 6322    conflict_table[('g3', 'g1', 'g2', 'x')] = 4323    conflict_table[('g3', 'g1', 'x', 'g0')] = 4324    conflict_table[('g3', 'g1', 'x', 'g2')] = 4325    conflict_table[('g3', 'g1', 'x', 'x')] = 2326    conflict_table[('g3', 'g2', 'g0', 'g1')] = 6327    conflict_table[('g3', 'g2', 'g0', 'x')] = 4328    conflict_table[('g3', 'g2', 'g1', 'g0')] = 6329    conflict_table[('g3', 'g2', 'g1', 'x')] = 4330    conflict_table[('g3', 'g2', 'x', 'g0')] = 4331    conflict_table[('g3', 'g2', 'x', 'g1')] = 4332    conflict_table[('g3', 'g2', 'x', 'x')] = 2333    conflict_table[('g3', 'x', 'g0', 'g1')] = 4334    conflict_table[('g3', 'x', 'g0', 'g2')] = 4335    conflict_table[('g3', 'x', 'g0', 'x')] = 2336    conflict_table[('g3', 'x', 'g1', 'g0')] = 4337    conflict_table[('g3', 'x', 'g1', 'g2')] = 4338    conflict_table[('g3', 'x', 'g1', 'x')] = 2339    conflict_table[('g3', 'x', 'g2', 'g0')] = 4340    conflict_table[('g3', 'x', 'g2', 'g1')] = 4341    conflict_table[('g3', 'x', 'g2', 'x')] = 2342    conflict_table[('g3', 'x', 'x', 'g0')] = 2343    conflict_table[('g3', 'x', 'x', 'g1')] = 2344    conflict_table[('g3', 'x', 'x', 'g2')] = 2345    conflict_table[('x', 'g0', 'g1', 'g2')] = 0346    conflict_table[('x', 'g0', 'g1', 'g3')] = 0347    conflict_table[('x', 'g0', 'g1', 'x')] = 0348    conflict_table[('x', 'g0', 'g2', 'g1')] = 2349    conflict_table[('x', 'g0', 'g2', 'g3')] = 0350    conflict_table[('x', 'g0', 'g2', 'x')] = 0351    conflict_table[('x', 'g0', 'g3', 'g1')] = 2352    conflict_table[('x', 'g0', 'g3', 'g2')] = 2353    conflict_table[('x', 'g0', 'g3', 'x')] = 0354    conflict_table[('x', 'g0', 'x', 'g1')] = 0355    conflict_table[('x', 'g0', 'x', 'g2')] = 0356    conflict_table[('x', 'g0', 'x', 'g3')] = 0357    conflict_table[('x', 'g1', 'g0', 'g2')] = 2358    conflict_table[('x', 'g1', 'g0', 'g3')] = 2359    conflict_table[('x', 'g1', 'g0', 'x')] = 2360    conflict_table[('x', 'g1', 'g2', 'g0')] = 4361    conflict_table[('x', 'g1', 'g2', 'g3')] = 0362    conflict_table[('x', 'g1', 'g2', 'x')] = 0363    conflict_table[('x', 'g1', 'g3', 'g0')] = 4364    conflict_table[('x', 'g1', 'g3', 'g2')] = 2365    conflict_table[('x', 'g1', 'g3', 'x')] = 0366    conflict_table[('x', 'g1', 'x', 'g0')] = 2367    conflict_table[('x', 'g1', 'x', 'g2')] = 0368    conflict_table[('x', 'g1', 'x', 'g3')] = 0369    conflict_table[('x', 'g2', 'g0', 'g1')] = 4370    conflict_table[('x', 'g2', 'g0', 'g3')] = 2371    conflict_table[('x', 'g2', 'g0', 'x')] = 2372    conflict_table[('x', 'g2', 'g1', 'g0')] = 4373    conflict_table[('x', 'g2', 'g1', 'g3')] = 2374    conflict_table[('x', 'g2', 'g1', 'x')] = 2375    conflict_table[('x', 'g2', 'g3', 'g0')] = 4376    conflict_table[('x', 'g2', 'g3', 'g1')] = 4377    conflict_table[('x', 'g2', 'g3', 'x')] = 0378    conflict_table[('x', 'g2', 'x', 'g0')] = 2379    conflict_table[('x', 'g2', 'x', 'g1')] = 2380    conflict_table[('x', 'g2', 'x', 'g3')] = 0381    conflict_table[('x', 'g3', 'g0', 'g1')] = 4382    conflict_table[('x', 'g3', 'g0', 'g2')] = 4383    conflict_table[('x', 'g3', 'g0', 'x')] = 2384    conflict_table[('x', 'g3', 'g1', 'g0')] = 4385    conflict_table[('x', 'g3', 'g1', 'g2')] = 4386    conflict_table[('x', 'g3', 'g1', 'x')] = 2387    conflict_table[('x', 'g3', 'g2', 'g0')] = 4388    conflict_table[('x', 'g3', 'g2', 'g1')] = 4389    conflict_table[('x', 'g3', 'g2', 'x')] = 2390    conflict_table[('x', 'g3', 'x', 'g0')] = 2391    conflict_table[('x', 'g3', 'x', 'g1')] = 2392    conflict_table[('x', 'g3', 'x', 'g2')] = 2393    conflict_table[('x', 'x', 'g0', 'g1')] = 0394    conflict_table[('x', 'x', 'g0', 'g2')] = 0395    conflict_table[('x', 'x', 'g0', 'g3')] = 0396    conflict_table[('x', 'x', 'g1', 'g0')] = 2397    conflict_table[('x', 'x', 'g1', 'g2')] = 0398    conflict_table[('x', 'x', 'g1', 'g3')] = 0399    conflict_table[('x', 'x', 'g2', 'g0')] = 2400    conflict_table[('x', 'x', 'g2', 'g1')] = 2401    conflict_table[('x', 'x', 'g2', 'g3')] = 0402    conflict_table[('x', 'x', 'g3', 'g0')] = 2403    conflict_table[('x', 'x', 'g3', 'g1')] = 2404    conflict_table[('x', 'x', 'g3', 'g2')] = 2405        406def linear_conflicts(start_list,goal_list):407    """408    calculates number of moves to add to the estimate of409    the moves to get from start to goal based on the number410    of conflicts on a given row or column. start_list411    represents the current location and goal_list represnts412    the final goal.413    """414    415    # Find which of the tiles in start_list have their goals on this line416    # build a pattern to use in a lookup table of this form:417    # g0, g1, g3, g3 fill in x where there is no goal for this line418    419    # all 'x' until we file a tile whose goal is in this line420    421    goal_pattern = ['x', 'x', 'x', 'x']422    423    for g in range(4):424        for s in range(4):425            start_tile_num = start_list[s]426            if start_tile_num == goal_list[g] and start_tile_num != 0:427                goal_pattern[s] = 'g' + str(g) # i.e. g0428                                429    global conflict_table430    431    tup_goal_pattern = tuple(goal_pattern)432    433    if tup_goal_pattern in conflict_table:434        return conflict_table[tuple(goal_pattern)]435    else:436        return 0437    438class lcmap(dict):439    """ 440    Lets you return 0 if you look for an object that441    is not in the dictionary. 442    """443    def __missing__(self, key):444        return 0445def listconflicts(goal_list):446    """ 447    list all possible start lists that will have at least448    one linear conflict.449    450    Possible goal tile configurations451    452    g g g g453    g g g x454    g g x g455    g x g g456    x g g g457    g g x x458    g x g x459    g x x g460    x g g x461    x g x g462    x x g g463        464    """465    466    all_tiles = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]467    468    non_goal_tiles = []469    470    for t in all_tiles:471        if t not in goal_list:472            non_goal_tiles.append(t) 473            474    combinations = lcmap()475    # g g g g476    477    for i in goal_list:478        tile_list2 = goal_list[:]479        tile_list2.remove(i)480        for j in tile_list2:481            tile_list3 = tile_list2[:]482            tile_list3.remove(j)483            for k in tile_list3:484                tile_list4 = tile_list3[:]485                tile_list4.remove(k)486                for l in tile_list4:487                    start_list = (i, j, k, l)488                    conflictadd = linear_conflicts(start_list,goal_list)489                    if conflictadd > 0:490                        combinations[start_list]=conflictadd    491    492    # g g g x493    494    for i in goal_list:495        tile_list2 = goal_list[:]496        tile_list2.remove(i)497        for j in tile_list2:498            tile_list3 = tile_list2[:]499            tile_list3.remove(j)500            for k in tile_list3:501                for l in non_goal_tiles:502                    start_list = (i, j, k, l)503                    conflictadd = linear_conflicts(start_list,goal_list)504                    if conflictadd > 0:505                        combinations[start_list]=conflictadd  506    # g g x g507    508    for i in goal_list:509        tile_list2 = goal_list[:]510        tile_list2.remove(i)511        for j in tile_list2:512            tile_list3 = tile_list2[:]513            tile_list3.remove(j)514            for k in non_goal_tiles:515                for l in tile_list3:516                    start_list = (i, j, k, l)517                    conflictadd = linear_conflicts(start_list,goal_list)518                    if conflictadd > 0:519                        combinations[start_list]=conflictadd520    # g x g g521    522    for i in goal_list:523        tile_list2 = goal_list[:]524        tile_list2.remove(i)525        for j in non_goal_tiles:526            for k in tile_list2:527                tile_list3 = tile_list2[:]528                tile_list3.remove(k)529                for l in tile_list3:530                    start_list = (i, j, k, l)531                    conflictadd = linear_conflicts(start_list,goal_list)532                    if conflictadd > 0:533                        combinations[start_list]=conflictadd534    # x g g g535    536    for i in non_goal_tiles:537        for j in goal_list:538            tile_list2 = goal_list[:]539            tile_list2.remove(j)540            for k in tile_list2:541                tile_list3 = tile_list2[:]542                tile_list3.remove(k)543                for l in tile_list3:544                    start_list = (i, j, k, l)545                    conflictadd = linear_conflicts(start_list,goal_list)546                    if conflictadd > 0:547                        combinations[start_list]=conflictadd548    # g g x x549    for i in goal_list:550        tile_list2 = goal_list[:]551        tile_list2.remove(i)552        for j in tile_list2:553            tile_list3 = tile_list2[:]554            tile_list3.remove(j)555            for k in non_goal_tiles:556                tile_list4 = non_goal_tiles[:]557                tile_list4.remove(k)558                for l in tile_list4:559                    start_list = (i, j, k, l)560                    conflictadd = linear_conflicts(start_list,goal_list)561                    if conflictadd > 0:562                        combinations[start_list]=conflictadd 563                        564    # g x g x565    for i in goal_list:566        tile_list2 = goal_list[:]567        tile_list2.remove(i)568        for j in non_goal_tiles:569            tile_list3 = non_goal_tiles[:]570            tile_list3.remove(j)571            for k in tile_list2:572                for l in tile_list3:573                    start_list = (i, j, k, l)574                    conflictadd = linear_conflicts(start_list,goal_list)575                    if conflictadd > 0:576                        combinations[start_list]=conflictadd    577                        578    # g x x g579    for i in goal_list:580        tile_list2 = goal_list[:]581        tile_list2.remove(i)582        for j in non_goal_tiles:583            tile_list3 = non_goal_tiles[:]584            tile_list3.remove(j)585            for k in tile_list2:586                for l in tile_list3:587                    start_list = (i, j, k, l)588                    conflictadd = linear_conflicts(start_list,goal_list)589                    if conflictadd > 0:590                        combinations[start_list]=conflictadd     591    592    # x g g x593    for i in non_goal_tiles:594        tile_list2 = non_goal_tiles[:]595        tile_list2.remove(i)596        for j in goal_list:597            tile_list3 = goal_list[:]598            tile_list3.remove(j)599            for k in tile_list3:600                for l in tile_list2:601                    start_list = (i, j, k, l)602                    conflictadd = linear_conflicts(start_list,goal_list)603                    if conflictadd > 0:604                        combinations[start_list]=conflictadd      605    606    # x g x g607    608    for i in non_goal_tiles:609        tile_list2 = non_goal_tiles[:]610        tile_list2.remove(i)611        for j in goal_list:612            tile_list3 = goal_list[:]613            tile_list3.remove(j)614            for k in tile_list3:615                for l in tile_list2:616                    start_list = (i, j, k, l)617                    conflictadd = linear_conflicts(start_list,goal_list)618                    if conflictadd > 0:619                        combinations[start_list]=conflictadd      620      621    # x x g g622    623    for i in non_goal_tiles:624        tile_list2 = non_goal_tiles[:]625        tile_list2.remove(i)626        for j in tile_list2:627            for k in goal_list:628                tile_list3 = goal_list[:]629                tile_list3.remove(k)630                for l in tile_list3:631                    start_list = (i, j, k, l)632                    conflictadd = linear_conflicts(start_list,goal_list)633                    if conflictadd > 0:634                        combinations[start_list]=conflictadd      635      636    return combinations637class HeuristicObj(object):638    """ Object used to preprocess goal position for heuristic function """639    def __init__(self, goal):640        """641        Preprocess goal position to setup internal data structures642        that can be used to speed up heuristic.643        """644        645        build_conflict_table()646        647        self.goal_map = []648        for i in range(16):649            self.goal_map.append(i)    650        651        self.goal_lists = goal.tiles652        653        # preprocess for manhattan distance654        655        for row in range(4):656            for col in range(4):657                self.goal_map[goal.tiles[row][col]] = (row, col)658                659        # make access faster by changing to a tuple660        661        self.goal_map = tuple(self.goal_map)662                663        # preprocess for linear conflicts664        665        self.row_conflicts = []666        for row in range(4):667            t = goal.tiles[row]668            conf_dict = listconflicts([t[0],t[1],t[2],t[3]])669            self.row_conflicts.append(conf_dict)670            671        self.col_conflicts = []672        for col in range(4):673            col_list =[]674            for row in range(4):675                col_list.append(goal.tiles[row][col])676            conf_dict = listconflicts(col_list)677            self.col_conflicts.append(conf_dict)678    def heuristic(self, start):679        """ 680        681        Estimates the number of moves from start to goal.682        The goal was preprocessed in __init__.683        684        """685        686        distance = 0687        688        # local variables for instance variables689        690        t = start.tiles691        g = self.goal_map692        rc = self.row_conflicts693        cc = self.col_conflicts694        695        # calculate manhattan distance696        697        for row in range(4):698            for col in range(4):699                start_tilenum = t[row][col]700                if start_tilenum != 0:701                    (grow, gcol) = g[start_tilenum]702                    distance += abs(row - grow) + abs(col - gcol)703                                        704        # add linear conflicts 705        706        for row in range(4):707            curr_row = t[row]708            distance += rc[row][curr_row]709       710        for col in range(4):711            col_tuple = (t[0][col], t[1][col], t[2][col], t[3][col])712            distance += cc[col][col_tuple]713          714        return distance715        716# global variable for heuristic object717hob = None718        719def a_star(start_tiles, goal_tiles):720    """ Based on https://en.wikipedia.org/wiki/A*_search_algorithm """721    722    start = new_position(start_tiles)723    goal = new_position(goal_tiles)724    725    # Process goal position for use in heuristic726    727    global hob728    hob = HeuristicObj(goal)729    730    # The set of currently discovered nodes that are not evaluated yet.731    # Initially, only the start node is known.732    # For the first node, the fscore is completely heuristic.733    734    start.fscore = hob.heuristic(start)735    openSet = PriorityQueue([start])736 737    # The cost of going from start to start is zero.738    739    start.gscore = 0740    741    num_popped = 0742    743    while openSet.queue_length > 0:744        current = openSet.pop()745        if current == None: # tried to pop but only found old fscore values746            break747        num_popped += 1748        if num_popped % 100000 == 0:749            print(str(num_popped)+" positions examined")750        751        if current == goal:752            return reconstruct_path(current)753            754        for neighbor in current.neighbors():755            # The distance from start to a neighbor756            # All nodes are 1 move from their neighbors757            758            tentative_gScore = current.gscore + 1759            760            # update gscore and fscore if this is shorter path761            # to the neighbor node762            if tentative_gScore < neighbor.gscore: 763                neighbor.cameFrom = current764                neighbor.gscore = tentative_gScore765                neighbor.fscore = neighbor.gscore + hob.heuristic(neighbor)766                openSet.push(neighbor) # add to open set every time767                768def find_zero(tiles):769    """ file the 0 tile """770    for row in range(4):771        for col in range(4):772            if tiles[row][col] == 0:773                return (row, col)774def path_as_0_moves(path):775    """776    Takes the path which is a list of Position777    objects and outputs it as a string of rlud 778    directions to match output desired by 779    Rosetta Code task.780    """781    strpath = ""782    if len(path) < 1:783        return ""784    prev_pos = path[0]785    p_row, p_col = find_zero(prev_pos.tiles)786    for i in range(1,len(path)):787        curr_pos = path[i]788        c_row, c_col = find_zero(curr_pos.tiles)789        if c_row > p_row:790            strpath += 'd'791        elif c_row < p_row:792            strpath += 'u'793        elif c_col > p_col:794            strpath += 'r'795        elif c_col < p_col:796            strpath += 'l'797        # reset for next loop798        prev_pos = curr_pos799        p_row = c_row800        p_col = c_col801    return strpath...

coast.py

Source:coast.py

1"""2Ð Ð°ÑÑÐµÑ ÑÑÐ¾Ð¸Ð¼Ð¾ÑÑÐ¸ (Ð´Ð¸ÑÑÐ°Ð½ÑÐ¸Ð¸/ÐºÐ¾Ð»Ð¸ÑÐµÑÑÐ²Ð° ÑÐ°Ð³Ð¾Ð²) Ð¿ÑÑÐ¸ Ð¾Ñ Ð¿Ð¾Ð·Ð¸ÑÐ¸Ð¸ node Ð´Ð¾ node_result3ÐÑÐ¾Ð´:4sizeH, sizeV - sizeH, sizeV - ÑÐ°Ð·Ð¼ÐµÑ Ð¿Ð¾Ð»ÐµÐ¹ Ð¿Ð¾ Ð³Ð¾ÑÐ¾Ð¸Ð·Ð¾Ð½ÑÐ°Ð»Ð¸ Ð¸ Ð²ÐµÑÑÐ¸ÐºÐ°Ð»Ð¸5node ÑÑÐ°ÑÑÐ¾Ð²Ð°Ñ Ð¿Ð¾Ð·Ð¸ÑÐ¸Ñ6node_result - ÐºÐ¾Ð½ÐµÑÐ½Ð°Ñ Ð¿Ð¾Ð·Ð¸ÑÐ¸Ñ7ÐÑÑÐ¾Ð´:8distance - ÑÐ°ÑÑÐ¸ÑÐ°Ð½Ð½Ð°Ñ Ð´Ð¸ÑÑÐ°Ð½ÑÐ¸Ñ9"""10def coast(node, node_result, sizeH, sizeV):11    assert len(node) == len(node_result)12    distance = 013    for i in range(len(node)):                         # Ð Ð°ÑÑÐµÑ Ð¼Ð°Ð½ÑÐµÑÐ¾Ð½Ð½Ð¾Ð²ÑÐºÐ¾Ð³Ð¾ ÑÐ°ÑÑÑÐ¾ÑÐ½Ð¸Ñ Ð² Ð½Ð¾Ð´Ð°Ñ14        distance = distance + abs(node[i][0]-node_result[i][0]) + abs(node[i][1]-node_result[i][1])15    if (distance != 0) and (sizeV > 2) and (sizeH > 2):16        for i in range(sizeV):                         # ÐÐ¾Ð±Ð°Ð²Ð»ÐµÐ½Ð¸Ðµ Ð² ÑÐ»ÑÑÐ°ÑÑ Ð½Ð°Ð»Ð¸ÑÐ¸Ñ Ð»Ð¸Ð½ÐµÐ¹Ð½ÑÑ ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑÐ¾Ð²17            a = sizeH*i18            if i != sizeV-1:                           # ÐÐµ Ð´Ð»Ñ Ð¿Ð¾ÑÐ»ÐµÐ´Ð½ÐµÐ¹ ÑÑÑÐ¾ÑÐºÐ¸19                distance += checkLinearConflict(i, node[int(a):int(a+sizeH)])20            else:21                # Ð Ð¿Ð¾ÑÐ»ÐµÐ´Ð½ÐµÐ¹ ÑÑÑÐ¾ÑÐºÐµ, Ð½Ðµ ÑÑÐ¸ÑÑÐ²Ð°ÐµÐ¼ Ð¿Ð¾ÑÐ»ÐµÐ´Ð½ÐµÐµ Ð·Ð½Ð°ÑÐµÐ½Ð¸Ðµ22                distance += checkLinearConflict(i, node[int(a):int(a+sizeH-2)])23        for i in range(sizeH):                          # ÐÐ¾Ð±Ð°Ð²Ð»ÐµÐ½Ð¸Ðµ Ð² ÑÐ»ÑÑÐ°ÑÑ Ð½Ð°Ð»Ð¸ÑÐ¸Ñ ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑÐ¾Ð² Ð² ÑÑÐ¾Ð»Ð±ÑÐ°Ñ24            column = []25            if i != sizeH-1:26                for j in range(sizeV):27                    column.append(node[i+j*sizeH])28            elif sizeV > 3:29                for j in range(sizeV-1):30                    column.append(node[i+j*sizeH])31            distance += checkColumnConflict(i, column)32        # print(node[(sizeH-1)*sizeV-1], [sizeV-2, sizeH-1], node[sizeH*sizeV-2], [sizeH-1, sizeV-1])33        # ÐÐ¾Ð±Ð°Ð²Ð»ÐµÐ½Ð¸Ðµ Ð² ÑÐ»ÑÑÐ°Ðµ ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑÐ° Ð¿Ð¾ÑÐ»ÐµÐ´Ð½ÐµÐ³Ð¾ ÑÐ¾Ð´Ð°34        if (node[(sizeH-1)*sizeV-1] != [sizeV-2, sizeH-1]) or (node[sizeH*sizeV-2] != [sizeH-1, sizeV-1]):35            distance += 236# ÐÑÐ¾Ð²ÐµÑÐºÐ° ÑÐ³Ð»Ð¾Ð²ÑÑ ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑÐ¾Ð²37    if node[1] == [0, 1] and node[sizeH] == [1, 0] and node[0] != [0, 0]:38        # ÐÑÐ¾Ð²ÐµÑÐºÐ° Ð½Ð° ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑ Ð² Ð»ÐµÐ²Ð¾Ð¼ Ð²ÐµÑÑÐ½ÐµÐ¼ ÑÐ³Ð»Ðµ39        # print('Destrust Angle conflict left/top')40        # print(node[1], node[sizeH], node[0])41        # l = [node[sizeV], node[2 * sizeV]]42        # print(node[1:3], l)43        if checkLinearConflict(0, node[1:3]) != 2:44            if checkColumnConflict(0, [node[sizeV], node[2 * sizeV]]) != 2:45                distance += 246        # isConflict = isConflict + int(self.checkLinearConflict(1, node[7:9]))47                    #print ('Is Conflict - ', isConflict)48                    #print ('Node - 4,8', [node[4],node[8]])49                    #print ('Node - 2,5', [node[1],node[5]])50#                    isConflict = isConflict + int(self.checkColumnConflict(0, [node[4],node[8]]))51#                    isConflict = isConflict + int(self.checkColumnConflict(1, [node[1],node[5]]))52#                    if (isConflict==0):53                        #print ('Angle conflict', node)54#                        distance = distance + 255                        #print (distance)56#                if (node[2]==[0, 2])&(node[7]==[1, 3])&(node[3]!=[0, 3]):57                    #print ('Destrust Angle conflict')58                    #print ('Node -' , node )59                    #print ('Node 2-3 two - ', node[1:3])60                    #print ('Node 6-7- ', node[6:8])61#                    isConflict = 062#                    isConflict = isConflict + int(self.checkLinearConflict(0, node[1:3]))63#                    isConflict = isConflict + int(self.checkLinearConflict(1, node[6:8]))64                    #print ('Is Conflict - ', isConflict)65                    #print ('Node - 3,7', [node[2],node[6]])66                    #print ('Node - 8,12', [node[7],node[11]])67#                    isConflict = isConflict + int(self.checkColumnConflict(2, [node[2],node[6]]))68#                    isConflict = isConflict + int(self.checkColumnConflict(3, [node[7],node[11]]))69#                    if (isConflict==0):70                        #print ('Angle conflict', node)71#                        distance = distance + 272                        #print (distance)73#                if (node[8]==[3, 0])&(node[13]==[3, 1])&(node[12]!=[3, 0]):74                    #print ('Destrust Angle conflict')75                    #print ('Node -' , node )76                    #print ('Node 9-10 - ', node[8:9])77                    #print ('Node 14-15- ', node[13:15])78#                    isConflict = 079#                    isConflict = isConflict + int(self.checkLinearConflict(2, node[8:9]))80#                    isConflict = isConflict + int(self.checkLinearConflict(3, node[13:15]))81                    #print ('Is Conflict - ', isConflict)82                    #print ('Node - 4,8', [node[4],node[8]])83                    #print ('Node - 10,14', [node[9],node[13]])84#                    isConflict = isConflict + int(self.checkColumnConflict(0, [node[4],node[8]]))85#                    isConflict = isConflict + int(self.checkColumnConflict(1, [node[9],node[13]]))86#                    if (isConflict==0):87                        #print ('Angle conflict', node)88#                        distance = distance + 289                        #print (distance)90            #print ('checkLinearConflict', distance)91    return int(distance)92def coast2(node, node_result):93    # ÐÐ»Ñ Ð¿ÑÐ¾Ð²ÐµÑÐºÐ¸ ÑÑÐ¾Ð¸Ð¼Ð¾ÑÑÑ Ð¾Ñ Ð½Ð°ÑÐ°Ð»ÑÐ½Ð¾Ð³Ð¾ ÑÐ¾ÑÑÐ¾ÑÐ½Ð¸Ñ (Ð±ÐµÐ· ÑÑÐµÑÐ° ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑÐ¾Ð²)94    # ÐÐ½Ð°Ð»Ð¾Ð³Ð¸ÑÐ½Ð¾ ÑÑÐ½ÐºÑÐ¸Ð¸ coast, Ð½Ð¾ Ð±ÐµÐ· ÑÑÐµÑÐ° ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑÐ¾Ð²95    if len(node) == len(node_result):96        distance = 097        for i in range(len(node)-1):98            # i -ÑÐ°Ð·Ð¼ÐµÑÐ½Ð¾ÑÑÑ Ð¿ÑÐ¾Ð²ÐµÑÑÐµÐ¼Ð¾Ð¹ Ð½Ð¾Ð´Ñ, Ð¿Ð¾Ð¿ÑÐ¾Ð±ÑÐµÐ¼ Ð½Ðµ ÑÑÐ¸ÑÑÐ²Ð°ÑÑ ÑÐµÐ½Ñ Ð¼Ð°ÑÑÑÑÑÐ° Ð´Ð»Ñ Ð¿Ð¾ÑÐ»ÐµÐ´Ð½ÐµÐ¹ ÑÑÐµÐ¹ÐºÐ¸ (Ð¿ÑÑÑÐ¾Ð¹)99            distance = distance + abs(node[i][0]-node_result[i][0]) + abs(node[i][1]-node_result[i][1])100    return int(distance)101def checkLinearConflict(index, line):102    # ÐÑÐ¾Ð²ÐµÑÐºÐ° Ð»Ð¸Ð½ÐµÐ¹Ð½Ð¾Ð³Ð¾ ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑÐ°103    # ÐÑÐ¾Ð´:104    # line - ÑÑÑÐ¾ÐºÐ° Ñ ÐºÐ¾Ð¾ÑÐ´Ð¸Ð½Ð°ÑÐ°Ð¼Ð¸ Ð´Ð»Ñ Ð¿ÑÐ¾Ð²ÐµÑÐºÐ¸105    # index - Ð¸Ð½Ð´ÐµÐºÑ Ð´Ð°Ð½Ð½Ð¾Ð¹ Ð»Ð¸Ð½Ð¸Ð¸ Ð² Ð¿Ð°Ð·Ð»Ðµ106    # ÐÑÑÐ¾Ð´:107    # isConflict - Ð½Ð°Ð»Ð¸ÑÐ¸Ðµ ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑÐ° ÐÐ°/ÐÐµÑ108    isConflict = 0109    for i in range(len(line)-1):110        a = line[i]111        b = line[i+1]112        if a[0] == index:                               # ÐºÐ¾Ð½ÑÑÐ¾Ð»Ð¸ÑÑÐµÐ¼ ÑÐ¾Ð»ÑÐºÐ¾ ÑÐ²Ð¾Ñ Ð»Ð¸Ð½Ð¸Ñ113            if (a[0] == b[0]) and (a[1]-b[1] == 1):114                isConflict = 2115                break116    return isConflict117def checkColumnConflict(index, line):118    # ÐÑÐ¾Ð²ÐµÑÐºÐ° Ð»Ð¸Ð½ÐµÐ¹Ð½Ð¾Ð³Ð¾ ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑÐ° Ð² ÑÑÐ¾Ð»Ð±ÑÐµ119    # ÐÑÐ¾Ð´:120    # line - ÑÑÑÐ¾ÐºÐ° Ñ ÐºÐ¾Ð¾ÑÐ´Ð¸Ð½Ð°ÑÐ°Ð¼Ð¸ Ð´Ð»Ñ Ð¿ÑÐ¾Ð²ÐµÑÐºÐ¸121    # index - Ð¸Ð½Ð´ÐµÐºÑ Ð´Ð°Ð½Ð½Ð¾Ð³Ð¾ ÑÑÐ¾Ð»Ð±ÑÐ° Ð² Ð¿Ð°Ð·Ð»Ðµ122    # ÐÑÑÐ¾Ð´:123    # isConflict - Ð½Ð°Ð»Ð¸ÑÐ¸Ðµ ÐºÐ¾Ð½ÑÐ»Ð¸ÐºÑÐ° ÐÐ°/ÐÐµÑ124    isConflict = 0125    for i in range(len(line)-1):126        a = line[i]127        b = line[i+1]128        if a[1] == index:                               # ÐºÐ¾Ð½ÑÑÐ¾Ð»Ð¸ÑÑÐµÐ¼ ÑÐ¾Ð»ÑÐºÐ¾ ÑÐ²Ð¾Ð¹ ÑÑÐ¾Ð»Ð±ÐµÑ129            if (a[1] == b[1]) and (a[0]-b[0] == 1):130                isConflict = 2131                break...

resource.py

Source:resource.py

1# -*- coding: utf-8 -*-2from django.utils.module_loading import import_string3class StandardDeviceMeta(object):4    check = [{5        'get_conflict_obj': lambda resource: resource.model.objects.filter(name=resource.obj.name).first(),6        'conflict_consistency_check': lambda device, conflict_device: \7            device.role == conflict_device.role8            and device.role_type == conflict_device.role_type9            and device.wan_number == conflict_device.wan_number10            and device.lan_number == conflict_device.lan_number11            and device.image_type == conflict_device.image_type12            and device.system_type == conflict_device.system_type13            and device.source_image_name == conflict_device.source_image_name14            and device.disk_format == conflict_device.disk_format15            and device.meta_data == conflict_device.meta_data16            and device.flavor == conflict_device.flavor17            and device.access_mode == conflict_device.access_mode18            and device.access_port == conflict_device.access_port19            and device.access_connection_mode == conflict_device.access_connection_mode20            and device.access_user == conflict_device.access_user21            and device.access_password == conflict_device.access_password22            and device.init_support == conflict_device.init_support23    }]24    subsidiary = [{25        'force': {26            'tmp_vm_id': None,27            'create_user_id': 1,28            'modify_user_id': None,29        },30    }]31class EnvMeta(object):32    check = [{33        'get_conflict_obj': lambda resource: resource.model.objects.filter(34            status=resource.model.Status.TEMPLATE,35            name=resource.obj.name,36        ).first(),37        'conflict_consistency_check': lambda env, conflict_env: \38            env.type == conflict_env.type39            and env.file == conflict_env.file40            and env.json_config == conflict_env.json_config41    }]42    subsidiary = [{43        'force': {44            'user_id': 1,45            'team_id': None,46        },47    }]48class EnvNetMeta(object):49    check = [{50        'get_conflict_obj': lambda resource: resource.model.objects.filter(51            env=resource.obj.env,52            sub_id=resource.obj.sub_id,53        ).first(),54        'conflict_consistency_check': lambda envnet, conflict_envnet: \55            envnet.name == conflict_envnet.name56            and envnet.dns == conflict_envnet.dns57            and envnet.cidr == conflict_envnet.cidr58            and envnet.dhcp == conflict_envnet.dhcp59    }]60    belong_to = [{61        'root': 'common_env.models.Env',62        'parent': 'common_env.models.Env',63        'get': lambda self_model, env: self_model.objects.filter(env=env),64        'set': lambda self, env: setattr(self, 'env', env)65    }]66class EnvGatewayMeta(object):67    check = [{68        'get_conflict_obj': lambda resource: resource.model.objects.filter(69            env=resource.obj.env,70            sub_id=resource.obj.sub_id,71        ).first(),72        'conflict_consistency_check': lambda envgateway, conflict_envgateway: \73            envgateway.name == conflict_envgateway.name74            and envgateway.static_routing == conflict_envgateway.static_routing75            and envgateway.firewall_rule == conflict_envgateway.firewall_rule76    }]77    belong_to = [{78        'root': 'common_env.models.Env',79        'parent': 'common_env.models.Env',80        'get': lambda self_model, env: self_model.objects.filter(env=env),81        'set': lambda self, env: setattr(self, 'env', env)82    }]83    subsidiary = [{84        'subsidiary': {85            'nets': {86                'many_to_many': True,87                'get': lambda self: self.nets.all(),88                'set': lambda self, envnets: self.nets.set(envnets)89            },90        },91    }]92class EnvTerminalMeta(object):93    check = [{94        'get_conflict_obj': lambda resource: resource.model.objects.filter(95            env=resource.obj.env,96            sub_id=resource.obj.sub_id,97        ).first(),98        'conflict_consistency_check': lambda envterminal, conflict_envterminal: \99            envterminal.name == conflict_envterminal.name100            and envterminal.system_type == conflict_envterminal.system_type101            and envterminal.image_type == conflict_envterminal.image_type102            and envterminal.image == conflict_envterminal.image103            and envterminal.role == conflict_envterminal.role104            and envterminal.flavor == conflict_envterminal.flavor105            and envterminal.install_script == conflict_envterminal.install_script106            and envterminal.init_script == conflict_envterminal.init_script107            and envterminal.clean_script == conflict_envterminal.clean_script108            and envterminal.push_flag_script == conflict_envterminal.push_flag_script109            and envterminal.check_script == conflict_envterminal.check_script110            and envterminal.attack_script == conflict_envterminal.attack_script111            and envterminal.checker == conflict_envterminal.checker112            and envterminal.attacker == conflict_envterminal.attacker113            and envterminal.raw_access_modes == conflict_envterminal.raw_access_modes114            and envterminal.external == conflict_envterminal.external115            and envterminal.net_configs == conflict_envterminal.net_configs116    }]117    belong_to = [{118        'root': 'common_env.models.Env',119        'parent': 'common_env.models.Env',120        'get': lambda self_model, env: self_model.objects.filter(env=env),121        'set': lambda self, env: setattr(self, 'env', env)122    }]123    subsidiary = [{124        'subsidiary': {125            'image': {126                'get': lambda self: import_string('common_env.models.StandardDevice').objects.filter(name=self.image).first(),127            },128            'nets': {129                'many_to_many': True,130                'get': lambda self: self.nets.all(),131                'set': lambda self, envnets: self.nets.set(envnets)132            },133        },134    }]135class EnvAttackerMeta(object):136    check = [{137        'get_conflict_obj': lambda resource: resource.model.objects.filter(138            name=resource.obj.name,139        ).first(),140        'conflict_consistency_check': lambda envattacker, conflict_envattacker: \141            envattacker.type == conflict_envattacker.type142            and envattacker.file == conflict_envattacker.file143            and envattacker.json_config == conflict_envattacker.json_config144    }]145    subsidiary = [{146        'force': {147            'create_user_id': 1,148        },...

test_models.py

Source:test_models.py

1# coding: utf-82from datetime import timedelta, datetime3from django.test import TestCase4from django.conf import settings5from organizations.models import Facility6from scheduler.models import Shift, ShiftHelper7from tests.factories import ShiftFactory, UserAccountFactory, TaskFactory, \8    FacilityFactory9def create_shift(start_hour, end_hour, facility=None):10    """11    Tiny helper because setting time periods is awkward till we remove the FK relationship.12    """13    create_args = dict(14        starting_time=datetime(2015, 1, 1, start_hour),15        ending_time=datetime(2015, 1, 1, end_hour)16    )17    if facility:18        create_args['facility'] = facility19    return ShiftFactory.create(**create_args)20def assert_shift_conflict_count(shift, hard_conflict_count, soft_conflict_count, grace=settings.DEFAULT_SHIFT_CONFLICT_GRACE):21    hard_conflicting_shifts, soft_conflicting_shifts = ShiftHelper.objects.conflicting(shift=shift, grace=grace)22    assert hard_conflicting_shifts.count() == hard_conflict_count23    assert soft_conflicting_shifts.count() == soft_conflict_count24class ShiftTestCase(TestCase):25    """26    We have some logic to detect conflicting shifts. This test case tests a few basic27    cases.28    """29    def setUp(self):30        self.user_account = UserAccountFactory.create()31        self.morning_shift = create_shift(9, 12)32        ShiftHelper.objects.create(user_account=self.user_account,33                                   shift=self.morning_shift)34        self.evening_shift = create_shift(18, 21)35        ShiftHelper.objects.create(user_account=self.user_account,36                                   shift=self.evening_shift)37        self.short_shift = create_shift(1, 2)38        ShiftHelper.objects.create(user_account=self.user_account,39                                   shift=self.short_shift)40    def test_non_conflict_tight_fitting(self):41        shift = create_shift(12, 18)42        assert_shift_conflict_count(shift, 0, 0)43    def test_non_conflict_gap_after(self):44        shift = create_shift(12, 17)45        assert_shift_conflict_count(shift, 0, 0)46    def test_non_conflict_gap_before(self):47        shift = create_shift(13, 18)48        assert_shift_conflict_count(shift, 0, 0)49    def test_non_conflict_tight_fitting_no_grace(self):50        shift = create_shift(12, 18)51        assert_shift_conflict_count(shift, 0, 0, None)52    def test_non_conflict_gap_after_no_grace(self):53        shift = create_shift(12, 17)54        assert_shift_conflict_count(shift, 0, 0, None)55    def test_non_conflict_gap_before_no_grace(self):56        shift = create_shift(13, 18)57        assert_shift_conflict_count(shift, 0, 0, None)58    def test_non_conflict_gaps(self):59        shift = create_shift(13, 17)60        assert_shift_conflict_count(shift, 0, 0)61    def test_non_conflict_gaps_no_grace(self):62        shift = create_shift(13, 17)63        assert_shift_conflict_count(shift, 0, 0, None)64    def test_conflict_at_beginning(self):65        shift = create_shift(8, 11)66        assert_shift_conflict_count(shift, 1, 1)67    def test_conflict_at_beginning_no_grace(self):68        shift = create_shift(9, 11)69        assert_shift_conflict_count(shift, 1, 1, None)70    def test_conflict_at_end(self):71        shift = create_shift(10, 15)72        assert_shift_conflict_count(shift, 1, 1)73    def test_conflict_at_end_no_grace(self):74        shift = create_shift(11, 15)75        assert_shift_conflict_count(shift, 1, 1, None)76    def test_conflict_within(self):77        shift = create_shift(10, 11)78        assert_shift_conflict_count(shift, 1, 1)79    def test_conflict_within_no_grace(self):80        shift = create_shift(9, 12)81        assert_shift_conflict_count(shift, 1, 1, None)82    def test_conflict_around(self):83        shift = create_shift(8, 13)84        assert_shift_conflict_count(shift, 1, 1)85    def test_conflict_around_no_grace(self):86        shift = create_shift(8, 13)87        assert_shift_conflict_count(shift, 1, 1)88    def test_conflict_grace_equals_duration(self):89        shift = create_shift(9, 12)90        assert_shift_conflict_count(shift, 1, 1, shift.duration)91        assert_shift_conflict_count(self.short_shift, 1, 1)92    def test_conflict_soft_only(self):93        shift = create_shift(11, 13)94        assert_shift_conflict_count(shift, 0, 1)95class FacilityTestCase(TestCase):96    def test_shift_manager_for_facility(self):97        """98            checks that get_days_with_shifts() returns only dates later than datetime.now()99        """100        now = datetime.now()101        yesterday_start = now - timedelta(1)102        yesterday_end = yesterday_start + timedelta(hours=1)103        tomorrow_start = now + timedelta(1)104        tomorrow_end = tomorrow_start + timedelta(hours=1)105        facility = FacilityFactory.create()106        task = TaskFactory.create(facility=facility)107        yesterday_shift = ShiftFactory.create(facility=facility,108                                              task=task,109                                              starting_time=yesterday_start,110                                              ending_time=yesterday_end)111        tomorrow_shift = ShiftFactory.create(facility=facility,112                                             task=task,113                                             starting_time=tomorrow_start,114                                             ending_time=tomorrow_end)115        assert Facility.objects.count() == 1, "test case assumes that shifts have been created for the same facility, as the ShiftFactory indeed does at the time of writing of this test case"116        assert Facility.objects.get() == task.facility117        shifts = Shift.open_shifts.filter(facility=facility)118        assert shifts.count() == 1, "only 1 shift should be found with Shifts.open_shifts"119        shift = shifts.get()120        assert shift == tomorrow_shift, "wrong shift was found"...

procedure.py

Source:procedure.py

1import argumentationcan2from argumentationcan import Conflict3from argumentationcan.world import world_predicate4def solve_conflict(argumentation_world, conflict):5    print(('conflict on {0} with intensity {1}'.format(conflict.predicate, conflict.necessity)))6    if solution(argumentation_world, conflict):7        return True8    elif abduction(argumentation_world, conflict):9        return True10    elif not conflict.negation_phase:11        if negation(argumentation_world, conflict):12            return True13    elif revision(argumentation_world, conflict):14        return False15    else:16        give_up(conflict)17        return False18def start(argumentation_world):19    argumentationcan.plan = []20    argumentationcan.computed_necessities ={}21    conflict = argumentation_world.current_conflict()22    while conflict is not None:23        print('\n(Re)start procedure in argumentation_world {0}'.format(24            ' & '.join([str(p) for p in argumentation_world.model])))25        solve_conflict(argumentation_world, conflict)26        conflict = argumentation_world.current_conflict()27    print('\nno more conflicts')28def solution(argumentation_world, conflict):29    if conflict.necessity > 0:30        if argumentation_world.execute_action(conflict.predicate):31            print(('- solution {0} performed'.format(conflict.predicate)))32            argumentationcan.set_computed_necessity(conflict.predicate, conflict.necessity)33            argumentationcan.plan.append(conflict)34            return True35    return False36def abduction(argumentation_world, conflict):37    print(('abduction {0}'.format(conflict.predicate)))38    possible_causes = argumentation_world.abduction(conflict.predicate)39    mutable_causes = find_mutable_causes(possible_causes, conflict.necessity)40    for cause in mutable_causes:41        if solve_conflict(argumentation_world, Conflict(cause, conflict.necessity)):42            return True43    return False44def negation(argumentation_world, conflict):45    print(('negation {0}'.format(conflict.predicate.negate())))46    conflict.negation_phase = True47    return solve_conflict(argumentation_world, Conflict(conflict.predicate.negate(), -conflict.necessity, True))48def revision(argumentation_world, conflict):49    if conflict.predicate in argumentation_world.wanted_necessities \50            or conflict.predicate.negate() in argumentation_world.wanted_necessities:51        positive_version = world_predicate.positive_version(conflict.predicate)52        necessity = int(eval(get_input('? - revision - change necessity for {0}? current = {1}'.format(positive_version,53                                                                                                       argumentation_world.get_wanted_necessity(54                                                                                                           positive_version)))))55        argumentation_world.wanted_necessities.pop(conflict.predicate, None)56        argumentation_world.wanted_necessities.pop(conflict.predicate.negate(), None)57        argumentation_world.wanted_necessities[positive_version] = necessity58        return True59    return False60def give_up(conflict):61    print(('give up - predicate {0} stored with necessity {1}'.format(conflict.predicate, -conflict.necessity)))...

json_conflict_handler.py

Source:json_conflict_handler.py

1# --------------------------------------------------------------------------2# Source file provided under Apache License, Version 2.0, January 2004,3# http://www.apache.org/licenses/4# (c) Copyright IBM Corp. 2015, 20165# --------------------------------------------------------------------------67import json8from docplex.mp.constants import ConflictStatus91011class JSONConflictHandler(object):12    '''A class that provides utilities to process the JSON conflict from DOcplexcloud13    '''1415    # json keys16    JSON_LINEAR_CTS_KEY = 'linearConstraints'1718    row_conflict_by_status = {'excluded': ConflictStatus.Excluded,19                              'possible': ConflictStatus.Possible_member,20                              'member': ConflictStatus.Member}21    grp_conflict_by_status = row_conflict_by_status22    col_conflict_by_status = {'excluded': ConflictStatus.Excluded,23                              'possible': ConflictStatus.Possible_member,24                              'possible_lb': ConflictStatus.Possible_member_lower_bound,25                              'possible_ub': ConflictStatus.Possible_member_upper_bound,26                              'member': ConflictStatus.Member,27                              'member_lb': ConflictStatus.Member_lower_bound,28                              'member_ub': ConflictStatus.Member_upper_bound}2930    def __init__(self, conflict_string, grps_dict, has_conflict=None):31        """Initialize a new JSONConflictHandler3233        This handler is initialized with a json fragment with the CPLEXConflict.3435        Args:36            conflict_string: The json text containing a CPLEXSolution37            grps_dict: dictionary of groups provided to the DOcplexcloud job, with keys = groups index38            has_conflict: if set to True or False, forces the has_conflict status. If None, this39                is True if json is not None.40        """41        self.has_conflict = bool(conflict_string) if has_conflict is None else has_conflict42        if conflict_string is not None:43            self.json = json.loads(conflict_string, parse_constant='utf-8')['CPLEXConflict']44        else:45            self.json = None4647        #48        self._grps_dict = grps_dict49        # used to store data from the json50        self.__cols = None51        self.__rows = None52        self.__grps = None5354    def _get_grps(self):55        if self.__grps is None:56            self.__grps = self.json.get('grp', [])57        return self.__grps5859    def get_conflict_grps_list(self):60        all_grps = self._get_grps()61        conflict_grps_list = [(int(g['index']),62                               self._grps_dict[int(g['index'])],63                               self.grp_conflict_by_status.get(g['status'], None))64                              for g in all_grps]65        return conflict_grps_list6667    def _get_cols(self):68        if self.__cols is None:69            self.__cols = self.json.get('col', [])70        return self.__cols7172    def _get_rows(self):73        if self.__rows is None:74            self.__rows = self.json.get('row', [])
...

named_urls_conflict.py

Source:named_urls_conflict.py

1from django.urls import path, re_path2from .views import empty_view3urlpatterns = [4    # No kwargs5    path('conflict/cannot-go-here/', empty_view, name='name-conflict'),6    path('conflict/', empty_view, name='name-conflict'),7    # One kwarg8    re_path(r'^conflict-first/(?P<first>\w+)/$', empty_view, name='name-conflict'),9    re_path(r'^conflict-cannot-go-here/(?P<middle>\w+)/$', empty_view, name='name-conflict'),10    re_path(r'^conflict-middle/(?P<middle>\w+)/$', empty_view, name='name-conflict'),11    re_path(r'^conflict-last/(?P<last>\w+)/$', empty_view, name='name-conflict'),12    # Two kwargs13    re_path(r'^conflict/(?P<another>\w+)/(?P<extra>\w+)/cannot-go-here/$', empty_view, name='name-conflict'),14    re_path(r'^conflict/(?P<extra>\w+)/(?P<another>\w+)/$', empty_view, name='name-conflict'),...

Using AI Code Generation

1module.exports = {2    {3    }4  paths: {5  },6  engineOptions: {7  },8};9{10    {11    },12    {13    },14    {15    },16    {17    },18    {19    }20    {

Using AI Code Generation

1var backstop = require('backstopjs');2var config = require('./backstop.json');3backstop('test', { config: config })4  .then(function () {5    console.log('Done with backstopjs');6  })7  .catch(function (error) {8    console.log(error);9  });10{11    {12    },13    {14    },15    {16    }17    {18    }19  "paths": {20  },21  "engineOptions": {22  },23}

Using AI Code Generation

1var backstop = require('backstopjs');2var fs = require('fs');3var path = require('path');4var backstopConfigPath = path.join(__dirname, 'backstop.json');5var backstopConfig = JSON.parse(fs.readFileSync(backstopConfigPath, 'utf8'));6backstop('reference', {7}).then(function () {8  return backstop('test', {9  });10}).then(function () {11  return backstop('approve', {12  });13}).then(function () {14  return backstop('openReport', {15  });16}).catch(function (error) {17  console.log(error);18});19{20    {21    },22    {23    },24    {25    },26    {27    },28    {29    }30    {31    }32  "paths": {

Using AI Code Generation

1var backstopjs = require('backstopjs');2var config = require('./backstop.json');3backstopjs('test', {config: config})4.then(function (result) {5})6.catch(function (err) {7});8{9{10},11{12}13{14}15"paths": {16},17"engineOptions": {18},19}

Using AI Code Generation

1var backstop = require('backstopjs');2var config = require('./backstop.json');3backstop('test', { config: config })4.then(function (result) {5  console.log(result);6})7.catch(function (err) {8  console.log(err);9});10{11    {12    },13    {14    },15    {16    },17    {18    }19    {20    }21  "paths": {22  },23}

Using AI Code Generation

1module.exports = async function (page, scenario, vp) {2  await require("./clickAndHoverHelper")(page, scenario);3  await page.waitForSelector('.my-button', { visible: true });4  await page.click('.my-button');5};6module.exports = async function (page, scenario) {7  const hoverSelector = scenario.hoverSelectors || scenario.hoverSelector;8  const clickSelector = scenario.clickSelectors || scenario.clickSelector;9  if (hoverSelector) {10    await page.waitForSelector(hoverSelector, { visible: true });11    await page.hover(hoverSelector);12  }13  if (clickSelector) {14    await page.waitForSelector(clickSelector, { visible: true });15    await page.click(clickSelector);16  }17  if (postInteractionWait) {18    await page.waitFor(postInteractionWait);19  }20};21{22    {23    },24    {25    },26    {27    },28    {29    }30    {31    }32  "paths": {

Automation Testing Tutorials

Learn to execute automation testing from scratch with LambdaTest Learning Hub. Right from setting up the prerequisites to run your first automation test, to following best practices and diving deeper into advanced test scenarios. LambdaTest Learning Hubs compile a list of step-by-step guides to help you be proficient with different test automation frameworks i.e. Selenium, Cypress, TestNG etc.