Advertisement
Guest User

Untitled

a guest
Sep 30th, 2018
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python2.7
  2.  
  3. import numpy as np
  4. import random
  5.  
  6. # activate for debugging to get the same random
  7. # numbers for every execution of the script
  8. # random.seed(0)
  9.  
  10. class Board(object):
  11.     '''models 3x3 sliding window game where the number 9 is the sliding component
  12.  
  13.    DEMO:
  14.  
  15.    >>> from board import Board
  16.    >>> b = Board.random_solvable_board()
  17.    >>> b
  18.    1 9 2
  19.    4 5 3
  20.    7 8 6
  21.    >>> b.apply_move('RIGHT')
  22.    >>> b
  23.    1 2 9
  24.    4 5 3
  25.    7 8 6
  26.    >>> b.heuristic()
  27.    4
  28.    >>> for move, result in b.possible_next_boards():
  29.    ...     print move
  30.    ...     print result
  31.    ...     print '---'
  32.    ...
  33.    DOWN
  34.    1 2 3
  35.    4 5 9
  36.    7 8 6
  37.    ---
  38.    LEFT
  39.    1 9 2
  40.    4 5 3
  41.    7 8 6
  42.    ---
  43.    '''
  44.  
  45.     # configuration of solved board
  46.     solution = np.array([[1, 2, 3],
  47.                          [4, 5, 6],
  48.                          [7, 8, 9]])
  49.  
  50.     # map name of move to delta values for row and column
  51.     moves = {'UP': (-1, 0),
  52.              'DOWN': (1, 0),
  53.              'LEFT': (0, -1),
  54.              'RIGHT': (0, 1)}
  55.  
  56.     def __init__(self, configuration):
  57.         '''Board(numpy array) -> Board instance
  58.  
  59.        example: my_board = Board(np.array([[2, 3, 9], [1, 5, 6], [4, 7, 8]]))'''
  60.         self.configuration = configuration
  61.         self.row_9, self.col_9 = np.where(self.configuration == 9)
  62.  
  63.     def __repr__(self):
  64.         return '\n'.join(' '.join(map(str, row)) for row in self.configuration)
  65.  
  66.     def __eq__(self, other):
  67.         return (self is other or
  68.                 np.array_equal(self.configuration, other.configuration))
  69.  
  70.     def is_solved(self):
  71.         'return whether configuration is equal to Board.solution'
  72.         return np.array_equal(self.configuration, Board.solution)
  73.  
  74.     def apply_move(self, move):
  75.         'mutates the board by applying a legal move, e.g. board.move("UP")'
  76.         delta_row, delta_col = Board.moves[move]
  77.         swap_row, swap_col = self.row_9 + delta_row, self.col_9 + delta_col
  78.  
  79.         if swap_row < 0 or swap_col < 0 or swap_row > 2 or swap_col > 2:
  80.             raise IndexError('illegal move, position ({}, {}) does not exist'
  81.                               .format(int(swap_row), int(swap_col)))
  82.  
  83.         swap_val = self.configuration[swap_row, swap_col]
  84.  
  85.         self.configuration[self.row_9, self.col_9] = swap_val
  86.         self.configuration[swap_row, swap_col] = 9
  87.  
  88.         self.row_9 = swap_row
  89.         self.col_9 = swap_col
  90.  
  91.     def apply_moves(self, movelist):
  92.         'applies all moves from movelist to board'
  93.         for move in movelist:
  94.             self.apply_move(move)
  95.  
  96.     def possible_next_boards(self):
  97.         'yields (move, resulting board) tuples for every possible move'
  98.         result_board = self.copy()
  99.  
  100.         for move in Board.moves:
  101.             try:
  102.                 result_board.apply_move(move)
  103.             except IndexError:
  104.                 continue
  105.  
  106.             yield (move, result_board)
  107.             result_board = self.copy()
  108.  
  109.     def heuristic(self):
  110.         '''sum of manhatten distances for each value to its target position on the board
  111.        (lower is better)'''
  112.         h = 0
  113.  
  114.         for row_idx, row in enumerate(self.configuration):
  115.             for col_idx, val in enumerate(row):
  116.                 target_row_idx = (val - 1)/3 # integer division!
  117.                 target_col_idx = (val - 1)%3
  118.                 dist = abs(row_idx - target_row_idx) + abs(col_idx - target_col_idx)
  119.                 h += dist
  120.  
  121.         return h
  122.  
  123.     def copy(self):
  124.         'returns a copy of the board'
  125.         return Board(self.configuration.copy())
  126.  
  127.     def to_tuple_repr(self):
  128.         '''returns immutable tuple representation of the board;
  129.        suitable for insertion into sets or usage as dictionary keys'''
  130.         return tuple(map(tuple, self.configuration))
  131.  
  132.     @staticmethod
  133.     def from_tuple_repr(tuple_repr):
  134.         '''constructs a full Board instance from tuple
  135.        representation returned by to_tuple_repr'''
  136.         return Board(np.array(tuple_repr))
  137.  
  138.     @staticmethod
  139.     def random_solvable_board(num_moves=10):
  140.         '''returns a random board that can be solved;
  141.        num_moves is the number of random moves applied to the solved starting board'''
  142.         moves = Board.moves.keys()
  143.         random_board = Board(Board.solution.copy())
  144.  
  145.         for _ in xrange(num_moves):
  146.             move = random.choice(moves)
  147.  
  148.             try:
  149.                 random_board.apply_move(move)
  150.             except IndexError:
  151.                 pass
  152.  
  153.         return random_board
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement