API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 15th, 2019
87
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 11.16 KB | None | 0 0
raw download clone embed print report
  1. # -*- coding: utf-8 -*-
  2. #Jack Granite and Emily Coghlan
  3.  
  4. # -*- coding: utf-8 -*-
  5. from cisc106 import assertEqual
  6. import time
  7. from tkinter import *
  8. DEBUG = True
  9. # A grid is a 2D list containing ones or zeros. A "shape" is an
  10. # object containing a nested tuple, where the real world shape is
  11. # represented as True values. For example, an "L" shape could be
  12. # represented as
  13. #
  14. # ((False, False, True),(True, True, True))
  15. #
  16. # Read a sequence of letters from a string (later from a text
  17. # file). Each letter represents a shape: T, L, or Z (all 2x3), or I
  18. # (1x4). Use functions to find a place on the grid where
  19. # the next shape in the sequence doesn't overlap any ones. Rotate the
  20. # shape to find the "best" fit. Then modify the grid to show the
  21. # shape in place, and repeat with the next shape in the sequence.
  22. # We will add the graphics and high level functions in the next part.
  23.  
  24. class Grid:
  25.     """
  26.    Has attributes numRows, numCols, and squares (a 2D list containing True/False).
  27.    """
  28.     def __init__(self,rows,cols,squares):
  29.         self.numRows = rows
  30.         self.numCols = cols
  31.         self.squares = squares if squares else [cols * [0] for r in range(rows)]
  32.     def updateGrid(self, shape):
  33.         """
  34.        Top-level def for placing a single shape on grid. Finds best
  35.        position and rotation for shape, update grid squares (mutates).
  36.        Calls: find_max_score_location
  37.        Returns boolean: fits or not
  38.        """
  39.     def print(self):
  40.         """
  41.        Print the grid, using an asterisk for each true square, underscore for false.
  42.        Use a newline after each row, and no spaces in rows.
  43.        """        
  44.         for rowi in range(self.numRows):
  45.             print("\t")
  46.             for coli in range(self.numCols):
  47.                 if self.squares[rowi][coli]:
  48.                     print('*', end = '')
  49.                 else:
  50.                     print('_', end = '')
  51.                  
  52. class Shape:
  53.     """
  54.    A "shape" is a nested tuple, where the real world shape is
  55.    represented as ones. For example, an "L" shape could be
  56.    represented as
  57.    ((False, False, True),(True, True, True))
  58.    Has attributes x, y, letter, squares (a nested list of type boolean),
  59.    color, num_rotations
  60.    """
  61.     def __init__(self, letter, squares, color):
  62.         self.x = 0 # will be modified later to indicate position
  63.         self.y = 0 # will be modified later to indicate position
  64.         self.letter = letter
  65.         self.squares = squares
  66.         self.color = color
  67.         self.num_rotations = 0
  68.    
  69.     def rotate90(self):
  70.         """
  71.        Rotates this shape 90 degrees clockwise (direction
  72.        matters). Mutates squares and num_rotations
  73.        Returns None
  74.        """
  75.         self.squares = self.squares[::-1]
  76.         a = len(self.squares[0])
  77.         b = len(self.squares)
  78.         new_shape_grid = [[0]*b for num in range(a)]
  79.         for row in range(len(self.squares)):
  80.             for col in range(len(self.squares[0])):
  81.                 new_shape_grid[col][row] = self.squares[row][col]
  82.         self.squares = new_shape_grid
  83.         self.num_rotations = self.num_rotations + 1
  84.        
  85. def get_shape(letter):
  86.     if letter == 'L':
  87.         return Shape('L', [[False, False, True], [True, True, True]], 'blue')
  88.     if letter == 'I':
  89.         return Shape('I', [[True, True, True, True]], 'pink')
  90.     if letter == 'T':
  91.         return Shape('T', [[True, True, True], [False, True, False]], 'green')
  92.     if letter == 'Z':
  93.         return Shape('Z', [[True, True, False], [False, True, True]], 'purple')  
  94.     """
  95.    Returns the Shape corresponding to the letter parameter: I
  96.    for a line; T for a T; L for an L on its back, foot to right; Z
  97.    for a Z. More may be added.
  98.    """
  99.    
  100. def fits(location, grid, shape):
  101.     row,col = location
  102.     test_matrix = []
  103.     for x in range(len(shape.squares)):
  104.         test_matrix = test_matrix + [grid.squares[row+x][col:(len(shape.squares[0]) + col)]]
  105.     for i in range(len(test_matrix)):
  106.         for j in range(len(test_matrix[i])):
  107.             if test_matrix[i][j] == True:
  108.                 if shape.squares[i][j] == True:
  109.                     return False
  110.     return True
  111. def generate_all_locations(grid, shape):
  112.     """
  113.    Takes a single shape in one position and finds all the places it could fit on the
  114.    grid, given its dimensions.
  115.    Returns: a list of row,col tuples
  116.    """
  117.     l = []
  118.     for row in range(len(grid.squares)-len(shape.squares)+1):
  119.         grid_column = grid.squares[row]
  120.         shape_column = shape.squares[0]
  121.         for column in range(len(grid_column)-len(shape_column)+1):
  122.             l = l + [(row,column)]
  123.     return l    
  124.  
  125. grid1 = Grid(3,5,[[0,0,1,0,0],[0,1,0,0,0],[0,1,1,0,1]])
  126.  
  127. assertEqual(generate_all_locations(grid1, get_shape('T')), [(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)])
  128. assertEqual(generate_all_locations(grid1, get_shape('I')), [(0,0),(0,1),(1,0),(1,1),(2,0), (2,1)])
  129.  
  130.  
  131. def get_valid_locations(location_list, grid, shape):
  132.     """
  133.    Returns list of locations where shape does not overlap shapes
  134.    already on grid. Assumes that all locations in parameter list are
  135.    potential fits for this shape.
  136.    Calls: fits
  137.    """
  138.     valid_locations_list = []
  139.     for location in location_list:
  140.         if fits(location, grid, shape):
  141.             valid_locations_list += [location]
  142.     return valid_locations_list
  143.  
  144. grid2 = Grid(4,4,[[0,0,0,0],[0,0,1,1],[1,0,0,1],[0,0,0,1]])
  145. assertEqual(get_valid_locations([(0,0),(1,0)], grid2, get_shape('Z')), [(1,0)])
  146. assertEqual(get_valid_locations([(1,0),(2,0)], grid2, get_shape('L')), [(2,0)])
  147. assertEqual(get_valid_locations([(0,0),(0,1),(2,0)], grid2, get_shape('T')), [(0,0)])
  148. '''assertEqual(get_valid_locations([(0,0), (0,1), (1,0)], grid2, get_shape('I')), [(0,0)])'''
  149.  
  150.  
  151. def get_score(location, grid, shape):
  152.     """
  153.    Computes the score for a shape placed at a single location on grid.
  154.    Scores are positive, higher is better. For now, code the heuristic discussed in class.
  155.    location: row,col tuple
  156.    Returns: number
  157.    """
  158.     row,col = location
  159.     score = 0
  160.     for i in range(len(shape.squares)):
  161.         lrow = i + row
  162.         for j in range(len(shape.squares[0])):
  163.             lcol = j + col
  164.             if shape.squares[i][j] == False:
  165.                 if grid.squares[lrow][lcol] == True:
  166.                     score += 1
  167.     return score
  168.    
  169. def get_max_score(location_list, grid, shape):
  170.     cscore = 0
  171.     clocation = (0,0)
  172.     for location in location_list:
  173.         score = get_score(location, grid, shape)
  174.         if cscore < score:
  175.             cscore = score
  176.             clocation = location
  177.         elif cscore == score:
  178.             if location[1] > clocation[1]:
  179.                 clocation = location
  180.             elif location[0] > clocation[0]:
  181.                 clocation = location
  182.     return clocation, cscore
  183.  
  184. def find_max_score_location(grid, shape):
  185.     """
  186.    Takes a single shape, finds best position on grid. Tries original
  187.    and three possible 90 degree rotations. Mutates shape for each rotation.
  188.    When scores are equal, the lowest row (highest row number), right end (highest
  189.    column) should be preferred.
  190.    Returns tuple: (fits numberRotations location)
  191.    fits: bool
  192.    maxScoreRow, maxScoreCol: upper left coordinates of best position for shape on grid
  193.    numberRotations: 0-3 rotations required for best fit.
  194.    Calls: rotate90, generate_all_locations, get_valid_locations, get_max_score
  195.    """
  196.     location_list = generate_all_locations(grid,shape)
  197.     valid_list = get_valid_locations(location_list, grid, shape)
  198.     #print(valid_list)
  199.     final_list = [get_max_score(valid_list, grid, shape)]
  200.     #print(final_list)
  201.    
  202.     shape.rotate90()
  203.    
  204.     location_list = generate_all_locations(grid,shape)
  205.     valid_list = get_valid_locations(location_list, grid, shape)
  206.     #print(valid_list)
  207.     final_list += [get_max_score(valid_list, grid, shape)]
  208.     #print(final_list)
  209.    
  210.     shape.rotate90()
  211.    
  212.     location_list = generate_all_locations(grid,shape)
  213.     valid_list = get_valid_locations(location_list, grid, shape)
  214.     #print(valid_list)
  215.     final_list += [get_max_score(valid_list, grid, shape)]
  216.     #print(final_list)
  217.    
  218.     shape.rotate90()
  219.    
  220.     location_list = generate_all_locations(grid,shape)
  221.     valid_list = get_valid_locations(location_list, grid, shape)
  222.     #print(valid_list)
  223.     final_list += [get_max_score(valid_list, grid, shape)]
  224.     print(final_list)
  225.    
  226.     shape.rotate90()
  227.  
  228.     max_tupe = final_list[0]
  229.     for tupe in final_list[1:]:
  230.         print (max_tupe, tupe)
  231.         if tupe[1] > max_tupe[1]:
  232.             max_tupe = tupe
  233.         if tupe[1] == max_tupe[1]:
  234.             if tupe[0][0] > max_tupe[0][0]:
  235.                 max_tupe = tupe
  236.             elif tupe[0][1] > max_tupe [0][1]:
  237.                 max_tupe = tupe
  238.         else:
  239.             max_tupe = max_tupe
  240.    
  241.     if max_tupe == final_list[0]:
  242.        num_rotations = 0
  243.     elif max_tupe == final_list[1]:
  244.         num_rotations = 1
  245.     elif max_tupe == final_list[2]:
  246.         num_rotations = 2
  247.     else:
  248.         num_rotations = 3
  249.    
  250.     for r in range(num_rotations):
  251.         shape.rotate90()
  252.  
  253.     return (fits(max_tupe[0], grid, shape), num_rotations, max_tupe[0])
  254.      
  255. assertEqual(fits((0,0), Grid(3,4,[[0,0,0,0],[0,0,1,0],[0,0,0,1]]), get_shape('I')), True)
  256. assertEqual(fits((1,0), Grid(3,4,[[0,0,0,0],[0,0,1,0],[0,0,0,1]]), get_shape('I')), False)
  257. assertEqual(fits((0,0), Grid(3,4,[[0,0,0,0],[0,0,1,0],[0,0,0,1]]), get_shape('T')), True)
  258. assertEqual(fits((0,1), Grid(3,4,[[0,0,0,0],[0,0,1,0],[0,0,0,1]]), get_shape('T')), False)
  259. assertEqual(fits((1,0), Grid(3,4,[[0,0,0,0],[0,0,1,0],[0,0,0,1]]), get_shape('Z')), True)
  260. assertEqual(fits((0,1), Grid(3,4,[[0,0,0,0],[0,0,1,0],[0,0,0,1]]), get_shape('Z')), False)
  261. assertEqual(fits((0,2), Grid(5,5,[[0,0,1,0,0],[0,1,0,0,0],[0,1,1,0,1],[0,0,0,0,0],[1,0,0,1,0]]), get_shape('L')), True)
  262. assertEqual(fits((1,2), Grid(5,5,[[0,0,1,0,0],[0,1,0,0,0],[0,1,1,0,1],[0,0,0,0,0],[1,0,0,1,0]]), get_shape('T')), True)
  263. assertEqual(fits((3,1), Grid(5,5,[[0,0,1,0,0],[0,1,0,0,0],[0,1,1,0,1],[0,0,0,0,0],[1,0,0,1,0]]), get_shape('I')), True)
  264. assertEqual(fits((3,0), Grid(5,5,[[0,0,1,0,0],[0,1,0,0,0],[0,1,1,0,1],[0,0,0,0,0],[1,0,0,1,0]]), get_shape('Z')), True)
  265. assertEqual(fits((3,2), Grid(5,5,[[0,0,1,0,0],[0,1,0,0,0],[0,1,1,0,1],[0,0,0,0,0],[1,0,0,1,0]]), get_shape('Z')), False)
  266.  
  267.  
  268.    
  269. if DEBUG:
  270.    
  271.     assertEqual(generate_all_locations(Grid(2,4,[]), get_shape('L')), [(0,0),(0,1)])
  272. assertEqual(get_max_score([(0,0),(0,1)], Grid(2,4,[]), get_shape('L')), ((0,1),0))
  273. assertEqual(get_valid_locations([(0,0),(0,1)], Grid(2,4,[]), get_shape('L')),[(0,0),(0,1)])    
  274. b = [[1,0,0],[0,0,0]]
  275. assertEqual(get_valid_locations([(0,0)], Grid(2,3,b), get_shape('L')), [(0,0)])
  276. assertEqual(find_max_score_location(Grid(2,4,[]), get_shape('L')), (True, 0, (0,1)))
  277. assertEqual(find_max_score_location(Grid(3,4,[[0,0,0,0],[0,0,0,0],[0,1,1,1]]),get_shape('L')), (True, 2, (1,0)))
  278. g = Grid(2,4,[[True,False,False,False],[False,False,False,False]])
  279. assertEqual(find_max_score_location( g, get_shape('L')), (True, 0, (0,0)))
  280. g.print()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!