Beginner's Knight's tour in Python (BFS)

Question

I wanted to implement this as short and effective as I could without using anything that is not basics, in order to improve my skills.

I would appreciate input about things like memory leaks I missed, simpler way of doing things instead reinventing the wheel, methods I should have used / implemented / not implemented (could have used built-ins and defaults...) and styling. In general, does this implementation follows common best practices?

import random as r
import itertools as it
import numpy as np

class P:

    up = 8
    down = 0

    def __init__(self,x=0,y=0,parent=None, random = False):
        self.x = x if not random else r.randint(P.down,P.up-1)
        self.y = y if not random else r.randint(P.down,P.up-1)
        self.parent = parent

    def __str__(self):
        return '({},{})'.format(self.x,self.y)

    def __repr__(self):
        return '({},{} [{},{}])'.format(self.x,self.y,self.parent.x if self.parent else '-',self.parent.y if self.parent else '-')

    def __eq__(self,other):
        return self.x == other.x and self.y == other.y

# for np.unique
    def __gt__(self,other):
        return self.x + self.y > other.x + other.y
# for np.unique
    def __lt__(self,other):
        return self.x + self.y < other.x + other.y

    def __hash__(self):
        return hash((self.x, self.y))

    def valid_moves(self):
        def valid(*num):
            # a better way to check if all number in num return True?
            # this seems nice and short to me, but I guess there is a better way
            return sum([n >= P.down and n < P.up for n in num]) // len(num)

        a,b = [1,-1,],[2,-2]
        # is there a way to shorten this list construction?
        t = [P(self.x + i, self.y + j, self) for i in a for j in b if valid(self.x+i,self.y+j)] + [P(self.x + i, self.y + j, self) for i in b for j in a if valid(self.x+i,self.y+j)]
        return np.unique(t)


s = P()
e = P(random = True)
print('findint shortest path from {} to {}'.format(s,e))

ls = s.valid_moves()

while True:
    if e in ls or e == s:
        print('found end node...')
        #find the end node that has parents - not the
        #original "e" that has no parents andt herefore
        #cannot be used to generate path
        curr = ls.pop(ls.index(e)) 
        path = [curr]
        print('generating path...')
        while curr != s:
            curr = curr.parent
            path += ['->']
            path += [curr]

        print('path: ',path)
        break

    tmp = [p.valid_moves() for p in ls]
    # flatten tmp into 1-d list
    ls = list(it.chain(*tmp))
    # Do I have any memory leaks?
    del tmp

Answer 1

For a beginner this is pretty good, there are some serious styling issues though which I would like to point out.

Review

• imports

  • .Only import what you need, ==> from random import randint
  • Doing import random as r does not help readability IMO

• Constants should be UPPERCASE, rename UP and DOWN accordingly

  See PEP8#constants

def valid(*num):

• This could be made simpler with the all() keyword

  return all(n in range(P.DOWN, P.UP) for n in num)

  Here all() checks if all points are in range and will return True if it is, else it will return False

t = [P(self.x + i, self.y + j, self) ...

• This list comprehension is way too long, and you actually repeat yourself

  A few fixes are needed

  • It is good to split up your lines for better readability like this:

    [P(...)
     for i in a
     for j in b
     ...]
    

  • You loop over [-1, 1], [2, -2] with 2 contatinated list comprehensions you could do this in one turn. By having a constant of all possible directions for instance, this will make it look a little better.

    I end up with this:

    DIRECTIONS = ((1, 2), (1, -2), (-1, 2), (-1, 2), (2, -1), (2, 1), (-2, 1), (-2, -1))
    paths = [P(self.rank + delta_rank,
               self.file + delta_file,
               self)
             for delta_rank, delta_file in P.DIRECTIONS
             if valid(self.rank + delta_rank, self.file + delta_file)]
    

• Always guard your code!

• There is the issue of naming. You have many unmeaningfull names

  class P() What is P? Point?

  a, b This doesn't say much

  e, s I would rename to end, start

  etc (t, ls, ...)

  In chess x is called a RANK and y is called a FILE

  When writing good code, it helpfull to give your variables and instances good names, where it is clear on first sight what they do. So when you revisit your code, or let other people use your code they know what is what.

Revised code

from random import randint
from itertools import chain
import numpy as np


class P:
    UP = 8
    DOWN = 0
    DIRECTIONS = ((1, 2), (1, -2), (-1, 2), (-1, 2), (2, -1), (2, 1), (-2, 1), (-2, -1))

    def __init__(self, rank=0, file=0, parent=None, random=False):
        self.rank = rank if not random else randint(P.DOWN, P.UP-1)
        self.file = file if not random else randint(P.DOWN, P.UP-1)
        self.parent = parent

    def __str__(self):
        return '({},{})'.format(self.rank, self.file)

    def __repr__(self):
        return '({},{} [{},{}])'.format(self.rank,
                                        self.file,
                                        self.parent.rank if self.parent else '-',
                                        self.parent.file if self.parent else '-')

    def __eq__(self, other):
        return self.rank == other.rank and self.file == other.file

    def __gt__(self, other):
        return self.rank + self.file > other.rank + other.file

    def __lt__(self, other):
        return self.rank + self.file < other.rank + other.file

    def __hash__(self):
        return hash((self.rank, self.file))

    def valid_moves(self):
        def valid(*num):
            return all(n in range(P.DOWN, P.UP) for n in num)

        paths = [P(self.rank + delta_rank,
                   self.file + delta_file,
                   self)
                 for delta_rank, delta_file in P.DIRECTIONS
                 if valid(self.rank + delta_rank, self.file + delta_file)]

        return np.unique(paths)

def find_path(start, end):    
    valid = start.valid_moves()
    while True:
        if end in valid or end == start:
            curr = valid.pop(valid.index(end)) 
            path = [curr]

            while curr != start:
                curr = curr.parent
                path += ['->']
                path += [curr]

            return path

        tmp = [p.valid_moves() for p in valid]
        valid = list(chain(*tmp))

if __name__ == '__main__':
    start, end = P(), P(random=True)
    print('Finding shortest path from {} to {}'.format(start, end))
    print('Path ', find_path(start, end))