4
\$\begingroup\$

I've implemented the sliding blocks puzzle in Python to solve it using different algorithms. I'd like to know if the class "Sliding_blocks" is nicely designed or if I am missing concepts of OOP.

I think that the indices of the blocks are a bit obfuscated, because I mix tuples, lists and arrays (arrays are better to add but then I have to convert them to tuples at some point).

I use the A* algorithm with the number of misplaced blocks as heuristic function. It's quite slow and I think's it's because I have to create many copies of objects.

I'm more concerned with best practices than speed.

The code is:

#!/usr/bin/env python 
# -*- coding: utf-8 -*-
from __future__ import division
import numpy as np
from copy import copy, deepcopy


class Sliding_blocks():

    def __init__(self):
        self.size = 4
        self.block = self.generate_block()


    def generate_block(self):
        """Goal state"""

        block = np.arange(1,self.size**2)
        block.resize(self.size,self.size)
        return block


    def move(self, piece):
        """Moves the piece with index "piece" to free place, if possible"""

        if list(piece) in self.find_moves():
            self.block[tuple( self.find_free() )] = self.block[tuple(piece)]
            self.block[tuple(piece)] = 0
            return "success"
        else:
            return "error"


    def find_free(self):
        """Returns array of indices of the free cell"""

        free_position = np.where(self.block == 0)
        free_position = np.array(free_position).flatten()
        return free_position


    def find_moves(self):
        """Returns list of allowed indices to move"""

        from itertools import product
        free_position = self.find_free()
        return [list(free_position+i) for i in [[0,1],[1,0],[-1,0],[0,-1]] if tuple(i+free_position) in product(range(self.size),repeat=2)]


    def shuffle(self):
        steps = 30
        for i in xrange(steps):
            self.rand_move()


    def rand_move(self):
        from random import choice

        self.move(choice(self.find_moves()))


    #The following functions are used to find the solution

    def isWin(self):
        return (self.block == self.generate_block()).all()


    def total_misplaced(self):
        return np.sum( self.block != self.generate_block() )


def tree_search():#
    Game = Sliding_blocks()
    Game.shuffle()

    frontier = [[Game]]
    explored = []

    while 1:
        if frontier==[]: return "Error"

        path, frontier = remove_choice(frontier)
        endnode = path[-1]
        explored.append(endnode)
        if endnode.isWin(): return path

        #Iterate over all possible actions at endnode
        for action in allactions(endnode):
            if not action in explored and not action in frontier or action.isWin():
                pathtem=copy(path)
                pathtem.append(action)
                frontier.append(pathtem)


def allactions(obj):
    possible = obj.find_moves()
    actions = []
    for i in range(len(possible)): 
        actions.append(deepcopy(obj))
        actions[i].move(possible[i])
    return actions


#A*
def a_star(frontier):
    #Calculates the cost (lenght + number misplaced cells)
    #of all paths in frontier, returns the frontier
    #without the least expensive path and also returns that path

    lengths = [f[-1].total_misplaced()+cost(f) for f in frontier]
    shortest=[i for i,l in enumerate(lengths) if l<=min(lengths)]
    return frontier.pop(shortest[0]), frontier 



def cost(path): return len(path)

if __name__ == "__main__":

    remove_choice = a_star
    sol = tree_search()
    for s in sol: 
        print s.block
        print "\n"
\$\endgroup\$
  • 1
    \$\begingroup\$ Hi, welcome to Code Review! This is a good first question and I hope you receive great answers! \$\endgroup\$ – Tunaki Apr 16 '16 at 20:48
4
\$\begingroup\$

Whether the code is well designed or not -- is hard to tell without using it. But I have several points:

  1. It's good that you have small functions/methods which do one thing and do well. It's good that you wrote docstrings and comments.

  2. shortest=[i for i,l in enumerate(lengths) if l<=min(lengths)] -- here you are calculating min(lengths) on each loop cycle. Calculate this and put into a variable.

  3. Comply with PEP-8. def cost(path): return len(path) -> have two different lines. np.arange(1,self.size**2) use one space after commas. Game = Sliding_blocks() -- only classes should named CamelCased -> game = SlidingBlocks(). Use pylint to see all warnings.

  4. Use enumerate:

    for i in range(len(possible)): 
        actions.append(deepcopy(obj))
        actions[i].move(possible[i])
    

Will become:

    for i, _possible in enumerate(possible): 
        action = deepcopy(obj)
        actions.append(action)
        action.move(_possible)
  1. Move the imports to the top of the file

    def rand_move(self):
        from random import choice
    
  2. Import module instead of objects from it.

    from itertools import product
    ...
    from random import choice
    

Will become:

import copy
import itertools
import random
  1. Using constants? Name them uppercase and make global. Is it a setting? Pass it as an argument with a default value or store as a class attribute.

    def shuffle(self):
        steps = 30
        for i in xrange(steps):
            self.rand_move()
    
  2. Fail early.

        if list(piece) in self.find_moves():
            self.block[tuple( self.find_free() )] = self.block[tuple(piece)]
            self.block[tuple(piece)] = 0
            return "success"
        else:
            return "error"
    

This can be rewritten as

        if list(piece) not in self.find_moves():
            return "error"
        ...
        return "success"

This will also reduce indentation.

return "error" -- this is a hardcoded string. Use a constant.

  1. Indeed, using tuples and lists is hard to read and is slow

    if list(piece) in self.find_moves():
        self.block[tuple( self.find_free() )] = self.block[tuple(piece)]
        self.block[tuple(piece)] = 0
    

You should rethink this.

\$\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.