Breadth First Search for a Slider Puzzle Solver

Question

I plan to implement a few other solvers (depth first search, A*, etc), hence why I'm using the abstract base class (which is new to me). I'm using Python 3.6, so you'll see f-string literals. I would appreciate any positive feedback (yay!) or, even more importantly, constructive (yay!) criticism.

import abc
from argparse import ArgumentParser
from collections import deque
from math import sqrt
from resource import getrusage, RUSAGE_SELF
from time import time

import numpy as np


class Board:
    def __init__(self, tiles: str, hole: str = '0', sz: int = None):
        board_ = tiles.split(',')
        self._sz = sz or int(sqrt(len(board_)))
        self._sorted_tokens = [str(x) for x in range(self._sz ** 2)]
        self._goal = np.reshape(self._sorted_tokens, (self._sz, -1))
        self._state = np.reshape(board_, (self._sz, -1))
        self._hole = hole

    def __repr__(self):
        return str(self._state)

    @property
    def goal(self):
        return ','.join(self._sorted_tokens)

    @property
    def string(self):
        return self.stringify(self._state)

    @property
    def state(self):
        return self._state

    @staticmethod
    def stringify(state):
        return ','.join(state.flatten())

    def hole_pos(self):
        pos = np.where(self._state == self._hole)
        return pos[0][0], pos[1][0]

    def tile(self, pos):
        if pos[0] < 0 or pos[1] < 0:
            raise ValueError('Tile out of bounds!')
        return self._state[pos]

    def act(self, action):
        hole = self.hole_pos()
        lut = {
            'Up': (hole[0] - 1, hole[1]),
            'Down': (hole[0] + 1, hole[1]),
            'Left': (hole[0], hole[1] - 1),
            'Right': (hole[0], hole[1] + 1)
        }
        pos = lut[action]
        board_ = self.swap(pos)
        return board_

    def actions(self):
        """
        find neighboring tiles to hole position
        """
        hole = self.hole_pos()
        actions_ = []
        if hole[0] - 1 >= 0:
            actions_.append('Up')
        if hole[0] + 1 < self._sz:
            actions_.append('Down')
        if hole[1] - 1 >= 0:
            actions_.append('Left')
        if hole[1] + 1 < self._sz:
            actions_.append('Right')
        return actions_

    def swap(self, pos):
        """
        position is tuple (R,C) of neighboring tile to hole
        """
        try:
            hole = self.hole_pos()
            tile = self.tile(pos)
            temp_state = self._state.copy()
            temp_state[pos[0]][pos[1]] = self._hole
            temp_state[hole[0]][hole[1]] = tile
            return Board(self.stringify(temp_state),
                         hole=self._hole,
                         sz=self._sz)
        except ValueError:
            return None


class Node:
    def __init__(self, state=None, action=None, path_cost=None, parent=None):
        self._state = state
        self._action = action
        self._path_cost = path_cost
        self._parent = parent

    def __repr__(self):
        return str({'state': self._state.state,
                    'action': self._action,
                    'path_cost': self._path_cost,
                    'parent': self.parent})

    def __iter__(self):
        node = self
        while node:
            yield node
            node = node._parent

    @property
    def state(self):
        return self._state

    @property
    def action(self):
        return self._action

    @property
    def path_cost(self):
        return self._path_cost

    @property
    def parent(self):
        return self._parent

    @property
    def depth(self):
        return sum(1 for _ in self) - 1  # to account for 0 indexing


class Solver(metaclass=abc.ABCMeta):
    def __init__(self, start_board: Board, depth: int = 4):
        self._goal = start_board.goal
        self._start_board = start_board
        self._frontier = deque()
        self._explored = set()
        self._path_cost = 0
        self._nodes_expanded = 0
        self._fringe_sz = 0
        self._max_fringe_sz = 0
        self._search_depth = 0
        self._max_search_depth = 0
        self._running_time = 0
        self._depth_limit = depth

    @property
    def nodes_expanded(self):
        return self._nodes_expanded

    @property
    def fringe_size(self):
        return self._fringe_sz

    @property
    def max_fringe_size(self):
        return self._max_fringe_sz

    @property
    def search_depth(self):
        return self._search_depth

    @property
    def max_search_depth(self):
        return self._max_search_depth

    @property
    def running_time(self):
        return self._running_time

    def update_fringe_size(self):
        self._fringe_sz = len(self._frontier)
        if self._fringe_sz > self._max_fringe_sz:
            self._max_fringe_sz = self._fringe_sz

    @abc.abstractmethod
    def solve(self):
        """
        To be implemented by detailed search strategies
        """
        return


class DFS(Solver):
    def solve(self):
        pass


class AST(Solver):
    def solve(self):
        pass


class IDA(Solver):
    def solve(self):
        pass


class BFS(Solver):
    def solve(self):
        start_time = time()
        root = Node(state=self._start_board,
                    path_cost=self._path_cost)
        self._frontier.append(root)
        if root.state.string == self._goal:
            self._search_depth = root.depth
            self._running_time = time() - start_time
            return root
        while True:
            if len(self._frontier) == 0:
                self._running_time = time() - start_time
                raise ValueError('Goal not found.')
            node = self._frontier.popleft()
            if node.depth > self._depth_limit:
                raise RuntimeError
            if node.state.string == self._goal:
                self.update_fringe_size()
                self._search_depth = node.depth
                self._running_time = time() - start_time
                return node
            self._nodes_expanded += 1
            self._explored.add(node.state.string)
            actions = node.state.actions()
            for action in actions:
                state = node.state.act(action)
                child = Node(state=state,
                             action=action,
                             path_cost=1,
                             parent=node)
                if child.depth > self._max_search_depth:
                    self._max_search_depth = child.depth
                if (child.state.string not in self._explored) and (child not in self._frontier):
                    self._frontier.append(child)
                    self.update_fringe_size()


class Summary:
    def __init__(self, child: Node):
        self._child = child

    def path_cost(self):
        return sum(n.path_cost for n in self._child)

    def actions(self):
        return list(reversed([n.action for n in self._child]))[1:]

    def search_depth(self):
        return self._child.depth


if __name__ == "__main__":
    try:
        parser = ArgumentParser()
        parser.add_argument("solver", help="algorithm (bfs | dfs)")
        parser.add_argument("board", help="board string (0,1,2,3...)")
        args = parser.parse_args()
        board = Board(tiles=args.board)
        print("***STARTING STATE***")
        print(board.state)
        algorithms = {
            'bfs': BFS(board, depth=100),
            # 'dfs': DFS(board, depth=100),
            # 'ast': BFS(board, depth=100),
            # 'ida': BFS(board, depth=100)
        }

        search = algorithms[args.solver]
        res = search.solve()
        print("***SOLUTION STATE***")
        print(res.state)
        print(f"nodes expanded {search.nodes_expanded}")
        summary = Summary(res)
        print(f"path cost {summary.path_cost()}")
        print(f"actions {summary.actions()}")
        print(f"fringe size: {search.fringe_size}")
        print(f"max_fringe_size: {search.max_fringe_size}")
        print(f"search depth {search.search_depth}")
        print(f"max search depth {search.max_search_depth}")
        print(f"running time {search.running_time}")
        print(f"memory usage {getrusage(RUSAGE_SELF)[2]}")
    except TypeError as e:
        print(e)
        exit(1)

Answer 1

Here is a high-level overview without diving into the implementation details:

• the solve() of your BFS class is not readable and quite lengthy - split it into multiple methods and/or add meaningful comments
• overall the program is long - see if you can split it into multiple importable modules
• I would also extract the "reading command-line arguments" and "reporting the results" code blocks into separate functions
• the last set of print() calls can be replaced with a single print() call and a multi-line string
• the Solver class may be rewritten using the attrs package making the code more readable avoiding the boilerplate parts
• according to the Docstring Convention, you should start your docstring with a capital letter and have a dot at the end of sentences. And, if a docstring fits a single line, define it on a single line.
• memory profile your program - it might be that, when you are creating new Board instances, the previous instances will be "hanging" and not garbage collected resulting into potential memory leaks