Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I coded the following program to solve the n-puzzle problem with n = 3. Are there any suggestions regarding readability and variable names?

import heapq
from random import shuffle
import math


n=3
fBoard = [1,2,3,
          4,5,6,
          7,8,0]

board = [i for i in range(9)]
shuffle(board)

print(board)
aStar()


class Board():

    def __init__(self,boardList,cost,parent):
        self._array = boardList
        self.heuristic = calcHeuristic(self._array)
        self.cost = cost
        self.totalCost = self.cost + self.heuristic
        self.parent = parent
        self.hashvalue = hash(tuple(self._array))

    def _printBoard(self):
        for var in range(len(self._array)):
            if var%3==0 and var!=0:
                print "\n",self._array[var],",",
            else:
                print self._array[var],",",

    def __hash__(self):
        return self.hashvalue

    def __eq__(self,other):
        return self._array == other._array

def aStar():
    pq = []
    cost = {}
    visited = {}
    start = Board(board,0,None)
    end = Board(fBoard,99,None)
    heapq.heappush(pq,(start.totalCost,start))
    while pq:
        tmp_tuple = heapq.heappop(pq)
        tmp_board = tmp_tuple[1]
        if tmp_board.heuristic == 0:
            end = tmp_board
            break

        index = tmp_board._array.index(0)
        x = index/3
        y = index%3
        listOfMoves = checkMove(x,y)

        for move in listOfMoves:
            moveBoard = tmp_board._array[:]
            moveIndex = move[0]*3 + move[1]
            moveBoard[index],moveBoard[moveIndex] = moveBoard[moveIndex],moveBoard[index]
            newBoard = Board(moveBoard,tmp_board.cost+1,tmp_board)
            new_cost = newBoard.totalCost
            if newBoard not in visited or new_cost < cost[newBoard]:
                cost[newBoard] = new_cost
                visited[newBoard] = 1
                newBoard.parent = tmp_board
                heapq.heappush(pq,(newBoard.totalCost,newBoard))

    var = end
    while var != start:
        print "\n"
        var._printBoard()
        var = var.parent

    print "\n"
    var._printBoard()

def manhattanDist(index,element):
    idx = fBoard.index(element)
    manhattan = 0
    fBoard_x = idx/3
    fBoard_y = idx%3
    x = index/3
    y = index%3
    manhattan += math.fabs(x-fBoard_x)
    manhattan += math.fabs(y-fBoard_y)
    return manhattan


def calcHeuristic(array):
    boardList = array
    heuristic = 0
    for var in boardList:
        x = var/3
        y = var%3
        if fBoard.index(var) != boardList.index(var):
            heuristic+=1
        heuristic+=manhattanDist(boardList.index(var),var)
    return heuristic


def checkMove(x,y):
    listOfMoves = [[x,y]]
    if(x+1<n):
        listOfMoves.append([x+1,y])
    if(x-1>=0):
        listOfMoves.append([x-1,y])
    if(y-1>=0):
        listOfMoves.append([x,y-1])
    if(y+1<n):
        listOfMoves.append([x,y+1])

    return listOfMoves
share|improve this question
    
See this question and its answer. –  Gareth Rees Feb 12 at 16:23

1 Answer 1

up vote 3 down vote accepted

Are there any suggestions regarding readability and variable names?

You should follow PEP8, the official Python coding style guide. For example:

  • Put spaces around operators. Instead of var%3==0, write as var % 3 == 0
  • Put spaces after commas separating parameters. Instead of Board(fBoard,99,None), write as Board(fBoard, 99, None)
  • Use snake_case for naming variables and methods instead of camelCase
  • Use PascalCase for naming classes

What is an fBoard? It's not easy to guess, so that's not a good name.

Don't execute code in global scope

These lines are executed immediately when the script is imported, which is not good:

n=3
fBoard = [1,2,3,
          4,5,6,
          7,8,0]

board = [i for i in range(9)]
shuffle(board)

print(board)
aStar()

It would be better to move them into a main function, and call that function from a if __name__ == '__main__' guard, like this:

def main():
    n=3
    fBoard = [1,2,3,
              4,5,6,
              7,8,0]

    board = [i for i in range(9)]
    shuffle(board)

    print(board)
    aStar()

if __name__ == '__main__':
    main()

This will make your script more reusable, and it will help you avoid some obscure bugs that can happen by variable shadowing.

Get ready for Python 3

It's not too difficult to make this script work with Python 3 too. All it takes is adapting your print statements a little bit. In some cases it's as trivial as adding (...), for example:

print "\n"

Rewrite as:

print("\n")

When you don't want the automatic newline, for example here:

print "\n",self._array[var],",",

You can add the end='' parameter:

print("\n",self._array[var],",", end='')
share|improve this answer
1  
The last example needs from __future__ import print_function at the top in Python 2. –  Janne Karila Feb 9 at 7:36
    
For Python 3 compatibility, integer division must use //. –  Janne Karila Feb 9 at 7:49
    
Thanks, any suggestions regarding design? use of classes and data structures? –  Deepak Feb 9 at 23:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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