10
\$\begingroup\$

I would be really thankful for review of this homework. I'm trying to write better code in terms of readability and design patterns.

This program solves the classic 15 slider puzzle with A* search. The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle. If the size is 3×3 tiles, the puzzle is called the 8-puzzle or 9-puzzle, and if 4×4 tiles, the puzzle is called the 15-puzzle or 16-puzzle named, respectively, for the number of tiles and the number of spaces. The object of the puzzle is to place the tiles in order (see diagram) by making sliding moves that use the empty space.

https://en.wikipedia.org/wiki/15_puzzle

# python3.5

import heapq
import itertools
import numpy as np


class Board:
    def __init__(self, board):
        self.goalconfig = list(range(1, 16)) + [0]
        self.board = board
        self.distancefromstart = 0
        self.parent = None
        self.distance = self.calculate_distance()

    def __repr__(self):
        return ('\nBoard: \n{} \nDistance: {}\nFrom start:{}'.
                format(np.matrix(self.board).reshape(4, 4),
                       self.getdistance(), self.distancefromstart))

    def __gt__(self, board2):
        return self.gettotaldistance() > board2.gettotaldistance()

    def __lt__(self, board2):
        return self.gettotaldistance() < board2.gettotaldistance()

    def calculate_distance(self):
        """
        :return: Sum of taxicab distances between board and goal
        """
        distance = 0
        for index, tile in enumerate(self.board):
            if tile is not self.goalconfig[index]:
                distance += self.taxicabdistance(index,
                                                 self.goalconfig.index(tile))

        return distance

    def getdistance(self):
        return self.distance

    def gettotaldistance(self):
        return self.distance + self.distancefromstart

    def taxicabdistance(self, index1, index2):
        y1, x1 = divmod(index1, 4)
        y2, x2 = divmod(index2, 4)
        return abs(x2 - x1) + abs(y2 - y1)

    def swapwithindex(self, index):
        """
        :swaps index and empty cell.
        :return: Board object
        """
        tempboard = self.board[:]
        index0 = tempboard.index(0)
        tempboard[index0], tempboard[index] = tempboard[index], tempboard[
            index0]
        return Board(tempboard)

    def allpositions(self):
        """
        :return: List of possible boards that could be generated from instance board
        """
        import random
        empty = self.board.index(0)
        movable = [index for index in range(16) if
                   self.taxicabdistance(empty, index) == 1]
        boards = []
        for move in movable:
            boards.append(self.swapwithindex(move))
        random.shuffle(boards)
        return boards


def solver(board):
    """
    :board: Board object
    :closed: processed nodes
    :distancesdict: hashtable of proc.nodes
    :return: List of boards leading to solution
    """

    def pushpositions(board, queue, closed, distancesdict):
        """
        pushes all position of the board to priority queue
        :param queue: priority queue list
        :param board: Board object
        """
        if board.getdistance() == 0:
            return board
        for childboard in board.allpositions():
            childboard.parent = board
            childboard.distancefromstart = board.distancefromstart + 1
            if childboard.getdistance() == 0:
                return childboard
            try:
                if distancesdict[
                    str(childboard.board)] > childboard.gettotaldistance():
                    heapq.heappush(queue, childboard)
                    distancesdict[
                        str(childboard.board)] = childboard.gettotaldistance()
            except KeyError:
                heapq.heappush(queue, childboard)
                distancesdict[
                    str(childboard.board)] = childboard.gettotaldistance()

    open = []
    closed = []
    distancesdict = {str(board.board): 0}
    result = None
    heapq.heappush(open, board)
    while open:
        top = heapq.heappop(open)
        result = pushpositions(top, open, closed, distancesdict)
        if result:
            # todo Refactor when result found
            return result
        distancesdict[str(top.board)] = top.gettotaldistance()
        closed.append(top)

board = Board([1, 2, 3, 4, 5, 6, 7, 8, 13, 9, 10, 12, 14, 11, 15, 0])

result = solver(board)

while True:
    print(result)
    if result.parent:
        result = result.parent
    else:
        break
\$\endgroup\$
4
\$\begingroup\$

I'll focus on the readability part of your code:

  1. Don't import modules you're not using. (import itertools)
  2. Don't import modules in the middle of your code. All the imports should be called at the beginning of the script (import random). This will make your code easier to read.
  3. Use _ to split the name of your methods.
getdistance()      -> get_distance()
gettotaldistance() -> get_total_distance()
taxicabdistance()  -> taxi_cab_distance()
swapwithindex()    -> swap_with_index()
allpositions()     -> all_positions()
pushpositions()    -> push_positions()
  1. The same rule as above goes for your variable names.
  2. I'd rather stick with PyCharm suggestion of keeping the line length < 120 characters, but that's rather a matter of preference
  3. Add if __name__ == '__main__' directive which will allow you you to have that code execute only when you want to run the module as a program, and not have it execute when someone just wants to import your module and call your functions themselves

Revised code:

import heapq
import numpy as np
import random


class Board:
    def __init__(self, board):
        self.goal_config = list(range(1, 16)) + [0]
        self.board = board
        self.distance_from_start = 0
        self.parent = None
        self.distance = self.calculate_distance()

    def __repr__(self):
        return ('\nBoard: \n{} \nDistance: {}\nFrom start:{}'.
                format(np.matrix(self.board).reshape(4, 4), self.get_distance(), self.distance_from_start))

    def __gt__(self, board2):
        return self.get_total_distance() > board2.get_total_distance()

    def __lt__(self, board2):
        return self.get_total_distance() < board2.get_total_distance()

    def calculate_distance(self):
        """
        :return: Sum of taxicab distances between board and goal
        """
        distance = 0
        for index, tile in enumerate(self.board):
            if tile is not self.goal_config[index]:
                distance += self.taxi_cab_distance(index, self.goal_config.index(tile))

        return distance

    def get_distance(self):
        return self.distance

    def get_total_distance(self):
        return self.distance + self.distance_from_start

    def taxi_cab_distance(self, index1, index2):
        y1, x1 = divmod(index1, 4)
        y2, x2 = divmod(index2, 4)
        return abs(x2 - x1) + abs(y2 - y1)

    def swap_with_index(self, index):
        """
        :swaps index and empty cell.
        :return: Board object
        """
        temp_board = self.board[:]
        index0 = temp_board.index(0)
        temp_board[index0], temp_board[index] = temp_board[index], temp_board[index0]
        return Board(temp_board)

    def all_positions(self):
        """
        :return: List of possible boards that could be generated from instance board
        """
        empty = self.board.index(0)
        movable = [index for index in range(16) if
                   self.taxi_cab_distance(empty, index) == 1]
        boards = []
        for move in movable:
            boards.append(self.swap_with_index(move))
        random.shuffle(boards)
        return boards


def solver(board):
    """
    :board: Board object
    :closed: processed nodes
    :distances: hashtable of proc.nodes
    :return: List of boards leading to solution
    """

    def push_positions(board, queue, closed, distances):
        """
        pushes all position of the board to priority queue
        :param queue: priority queue list
        :param board: Board object
        """
        if board.get_distance() == 0:
            return board
        for childboard in board.all_positions():
            childboard.parent = board
            childboard.distance_from_start = board.distance_from_start + 1
            if childboard.get_distance() == 0:
                return childboard
            try:
                if distances[str(childboard.board)] > childboard.get_total_distance():
                    heapq.heappush(queue, childboard)
                    distances[
                        str(childboard.board)] = childboard.get_total_distance()
            except KeyError:
                heapq.heappush(queue, childboard)
                distances[str(childboard.board)] = childboard.get_total_distance()

    open, closed, distances, result = [], [], {str(board.board): 0}, None
    heapq.heappush(open, board)
    while open:
        top = heapq.heappop(open)
        result = push_positions(top, open, closed, distances)
        if result:
            # todo Refactor when result found
            return result
        distances[str(top.board)] = top.get_total_distance()
        closed.append(top)


if __name__ == '__main__':
    board = Board([1, 2, 3, 4, 5, 6, 7, 8, 13, 9, 10, 12, 14, 11, 15, 0])

    result = solver(board)

    while True:
        print(result)
        if result.parent:
            result = result.parent
        else:
            break
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.