8
\$\begingroup\$

In chess there are eight rows numbered from 1 to 8 and 8 columns a-h. Pawns which are on the lowest row are always in danger to be captured. The objective of the program is to calculate which pawns are saved.

Given the coordinates of seven pawns return the number of pawns which are safe.

For example:

  1. safe_pawns({"b4", "d4", "f4", "c3", "e3", "g5", "d2"}) == 6
  2. safe_pawns({"b4", "c4", "d4", "e4", "f4", "g4", "e5"}) == 1
  3. safe_pawns({"b4", "c4", "d4", "e4", "f4", "g4", "e3"}) == 2

enter image description here

The code:

def safe_pawns(pawns: set) -> int:
    row_numbers = []
    list_of_pawns = list(pawns)
    letters_string = "abcdefgh"
    safe_pawns_list = []

    #check if there are neighbors which protect you
    for pawn in list_of_pawns:
        if pawn[0] == "a":
            if letters_string[1] + str(int(pawn[1])-1) in list_of_pawns:
                safe_pawns_list.append(pawn)
        elif pawn[0] == "h":
            if letters_string[6] + str(int(pawn[1])-1) in list_of_pawns:
                safe_pawns_list.append(pawn)
        else:
            if ((letters_string[letters_string.index(pawn[0]) + 1] + str(int(pawn[1]) - 1))
            in list_of_pawns):
                 safe_pawns_list.append(pawn)
            elif (letters_string[letters_string.index(pawn[0]) - 1] + str(int(pawn[1]) - 1)
            in list_of_pawns):
                safe_pawns_list.append(pawn)

    #delete the pawns which belong to the lowest row number
    for pawn in list_of_pawns:
        row_numbers.append(pawn[1])

    lowest_row_indexes = []

    for i, row_number in enumerate(row_numbers):
        if row_number == min(row_numbers):
            lowest_row_indexes.append(i)

    for i, lowest_row_index in enumerate(lowest_row_indexes):
        del list_of_pawns[lowest_row_index - i]
        del row_numbers[lowest_row_index - i]

    return len(safe_pawns_list)

How could this be improved?

\$\endgroup\$
  • \$\begingroup\$ You're obviously solving the CheckiO Safe Pawns mission. Just publish your solution there, and you'll get your reviews (and then some;). \$\endgroup\$ – Veky May 25 at 8:58
3
\$\begingroup\$

Playing with the code a bit, give insight in how we can optimize your code.

Unused computation

Note that the following part has no effect on the return value and can be removed:

    #delete the pawns which belong to the lowest row number
    for pawn in list_of_pawns:
        row_numbers.append(pawn[1])

    lowest_row_indexes = []

    for i, row_number in enumerate(row_numbers):
        if row_number == min(row_numbers):
            lowest_row_indexes.append(i)

    for i, lowest_row_index in enumerate(lowest_row_indexes):
        del list_of_pawns[lowest_row_index - i]
        del row_numbers[lowest_row_index - i]

Integer and String conversions

The lookup in the loop is expensive, as each time we convert strings to integers and vice versa. We make a mapping to integer once, prior to the loop.

def safe_pawns(pawns: set) -> int:
    letters_string = "abcdefgh"
    safe_pawns_list = []

    pawns = list(map(lambda x: (letters_string.index(x[0]), int(x[1])), pawns))

    # check if there are neighbors which protect you
    for pawn in pawns:
        if pawn[0] == 0:
            if (letters_string[1], pawn[1] - 1) in pawns:
                safe_pawns_list.append(pawn)
        elif pawn[0] == 8:
            if (letters_string[6], pawn[1] - 1) in pawns:
                safe_pawns_list.append(pawn)
        else:
            if (pawn[0] + 1, pawn[1] - 1) in pawns:
                safe_pawns_list.append(pawn)
            elif (pawn[0] - 1, pawn[1] - 1) in pawns:
                safe_pawns_list.append(pawn)

    return len(safe_pawns_list)

Using Numpy

The following is less fast (at least for these small amounts of pawns), however the logic is arguably more clear.

def intersect2d(a1, a2):
    # https://stackoverflow.com/questions/8317022/get-intersecting-rows-across-two-2d-numpy-arrays
    rows, ncols = a1.shape
    dtype = {'names': ['f{}'.format(i) for i in range(ncols)],
             'formats': ncols * [a1.dtype]}

    a3 = np.intersect1d(a1.view(dtype), a2.view(dtype))

    # This last bit is optional if you're okay with "C" being a structured array...
    a3 = a3.view(a1.dtype).reshape(-1, ncols)
    return a3


def safe_pawns_np(pawns: set) -> int:
    letters_string = "abcdefgh"

    np_pawns = np.array(list(map(lambda x: (letters_string.index(x[0]), int(x[1])), pawns)))

    safe_spots_right = np_pawns.copy()
    safe_spots_right[:, 0] += 1
    safe_spots_right[:, 1] += 1

    safe_spots_left = np_pawns.copy()
    safe_spots_left[:, 0] -= 1
    safe_spots_left[:, 1] += 1

    safe_spots = np.vstack((safe_spots_right, safe_spots_left))

    return len(intersect2d(np_pawns, safe_spots))
\$\endgroup\$
3
\$\begingroup\$

Write doctests for your three given test cases.

None of the following code has anything to do with return len(safe_pawns_list), so it's dead code that can serve no purpose (except possibly to cause a crash):

#delete the pawns which belong to the lowest row number
for pawn in list_of_pawns:
    row_numbers.append(pawn[1])

lowest_row_indexes = []

for i, row_number in enumerate(row_numbers):
    if row_number == min(row_numbers):
        lowest_row_indexes.append(i)

for i, lowest_row_index in enumerate(lowest_row_indexes):
    del list_of_pawns[lowest_row_index - i]
    del row_numbers[lowest_row_index - i]

The remaining first half of the function is mainly about finding the diagonal neighbours of each pawn. That code is rather tedious, with lots of mentions of pawn[0] and pawn[1], with a bit of arithmetic and validation mixed in. That code can be made a lot more expressive by moving it into a Position class.

from collections import namedtuple

class Position(namedtuple('Position', 'file rank')):
    def __new__(cls, algebraic):
        file, rank = algebraic[0], int(algebraic[1])
        return super(Position, cls).__new__(cls, file, rank)

    def offset(self, file=0, rank=0):
        """
        Return a Position relative to this position (or None, if it's off the
        board).

        >>> Position('a3').offset(rank=-1) == Position('a2')
        True
        >>> Position('a3').offset(file=-1) is None
        True
        >>> Position('a2').offset(file=+1, rank=+2) == Position('b4')
        True
        """
        file = chr(ord(self.file) + file)
        rank += self.rank
        if 'a' <= file <= 'h' and 1 <= rank <= 8:
            return type(self)(file + str(rank))


def safe_pawns(pawns: set) -> int:
    """
    Count the number of pawns that are safe.

    >>> safe_pawns({"b4", "d4", "f4", "c3", "e3", "g5", "d2"})
    6
    >>> safe_pawns({"b4", "c4", "d4", "e4", "f4", "g4", "e5"})
    1
    >>> safe_pawns({"b4", "c4", "d4", "e4", "f4", "g4", "e3"})
    2
    """
    pawns = set(Position(p) for p in pawns)
    return sum(
        p.offset(file=-1, rank=-1) in pawns or
        p.offset(file=+1, rank=-1) in pawns
        for p in pawns
    )
\$\endgroup\$
2
\$\begingroup\$

To optimise your algorithm we want to remove the most costly operations, which are the loops.

At the moment your algorithm:

  1. Goes through the list of pawns, adds it to the safe pawn list if it is safe
  2. Goes through the list of pawns again, adding it to row_numbers
  3. Goes through row_numbers, to find the lowest row index
  4. Goes through the lowest row and removes the pawns from the safe list

Here you can see you have 4 very costly operations. Let's try and reduce this as much as we can, starting with trying to solve the problem with only 1 loop.

Looking at your problem, steps 2, 3, and 4, are all redundant. The pawns in the bottom row would've already been accounted for by step 1. This is because to be safe, you must have a pawn down-left or down-right of it. All pawns in the bottom row do not meet this condition, so are guaranteed not to be on the safe list.

This means that the solution can be solved using only 1 loop.

Now let's try to optimise it further.

Storing pawns in the new list and counting them is a costly loop operation, so we must question whether we can improve on this next. The answer is yes, we don't need to store the safe pawns at all. Instead, we can use an integer to store the number of safe pawns, starting 0. If another safe pawn is found, add 1. Return this number at the end of the algorithm.

This means that a more optimal solution to solve the problem with only one loop is:

Go through the list of pawns, for each one check whether there is one down-left or down-right of it, and add 1 to the safe count if so. Return the safe count

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