CodeFights: A Simple Tetris Solver

Question

Long time no Codefights, link to the challenge Tetris game

Description

Let's play Tetris! But first we need to define the rules, especially since they probably differ from the way you've played Tetris before.

There is an empty field with 20 rows and 10 columns, which is initially empty. Random pieces appear on the field, each composed of four square blocks. You can't change the piece's shape, but you can rotate it 90 degree clockwise (possibly several times) and choose which columns it will appear within. Once you've rotated the piece and have set its starting position, it appears at the topmost row where you placed it and falls down until it can't fall any further. The objective of the game is to create horizontal lines composed of 10 blocks. When such a line is created, it disappears, and all lines above the deleted one move down. The player receives 1 point for each deleted row.

Your task is to implement an algorithm that places each new piece optimally. The piece is considered to be placed optimally if:

• The total number of blocks in the rows this piece will occupy after falling down is maximized;
• Among all positions with that value maximized, this position requires the least number of rotations;
• Among all positions that require the minimum number of rotations, this one is the leftmost one (i.e. the leftmost block's position is as far to the left as possible).

The piece can't leave the field. It is guaranteed that it is always possible to place the Tetris piece in the field.

Implement this algorithm and calculate the number of points that you will get for the given set of pieces.

Code

With unittests

import unittest

class Piece():
    def __init__(self, piece):
        self.piece = piece

    @property
    def width(self):
        return len(self.piece[0])

    @property
    def height(self):
        return len(self.piece)

    def rotate(self, times = 1):
        for i in range(times):
            self.piece = [row[::-1] for row in zip(*self.piece)]

    # Debugging purposes
    def __str__(self):
       return '\n'.join(''.join(line) for line in self.piece)

class Board():
    def __init__(self):
        self.max_height = 20
        self.max_width = 10
        self.board = [['.' for _ in range(self.max_width)] for __ in range(self.max_height)]

    def completed_line(self):
        for i, line in enumerate(self.board):
            if line.count('.') == 0:
                yield i

    def clear_line(self, index):
        del self.board[index]
        self.board.insert(0, ['.' for _ in range(10)])

    def drop(self, piece, offset):
        last_level = self.max_height - piece.height + 1
        for level in range(last_level):
            for i in range(piece.height):
                for j in range(piece.width):                    
                    if self.board[level+i][offset+j] == "#" and piece.piece[i][j] == "#":
                        return level - 1
        return last_level - 1

    def place_piece(self, piece, pos):
        level, offset = pos
        for i in range(piece.height):
            for j in range(piece.width):
                if piece.piece[i][j] == "#":
                    self.board[level+i][offset+j] = piece.piece[i][j]

    # Debugging purposes
    def __str__(self):
       return '\n'.join(''.join(line) for line in self.board)

def find_best_position(board, piece):
    result = []
    for rotation in range(4):
        for offset in range(board.max_width - piece.width + 1):        
            level = board.drop(piece, offset)
            blocks = sum([b.count('#') for b in board.board[level:level + piece.height]])
            result.append([blocks, rotation, offset, level])
        piece.rotate()

    result = list(filter(lambda x: x[0] == max(result, key = lambda x: x[0])[0], result))
    result = list(filter(lambda x: x[1] == min(result, key = lambda x: x[1])[1], result))
    result = list(filter(lambda x: x[2] == min(result, key = lambda x: x[2])[2], result))[0]
    return result


def tetrisGame(pieces):
    board = Board()
    score = 0
    for p in pieces:
        piece = Piece(p)
        _, rotate, offset, level = find_best_position(board, piece)

        piece.rotate(rotate)
        board.place_piece(piece ,(level, offset))

        for i in board.completed_line():
            board.clear_line(i)
            score += 1

    return score

class CodeFightsTest(unittest.TestCase):
    def test_1(self):
        pieces = [[[".","#","."],["#","#","#"]], 
                  [["#",".","."],["#","#","#"]], 
                  [["#","#","."],[".","#","#"]], 
                  [["#","#","#","#"]], 
                  [["#","#","#","#"]], 
                  [["#","#"],["#","#"]]]
        self.assertEqual(tetrisGame(pieces), 1)

    def test_2(self):
        pieces = [[["#","#"],["#","#"]], 
                  [["#","#"],["#","#"]], 
                  [["#","#"],["#","#"]], 
                  [["#","#"],["#","#"]], 
                  [["#","#"],["#","#"]], 
                  [["#","#"],["#","#"]]]
        self.assertEqual(tetrisGame(pieces), 2)

    def test_3(self):
        pieces = [[["#","#","#","#"]], 
                  [["#","#","#","#"]], 
                  [["#","#"],["#","#"]]]
        self.assertEqual(tetrisGame(pieces), 1)

    def test_4(self):
        pieces = [[[".","#","#"],["#","#","."]], 
                  [[".","#","."],["#","#","#"]], 
                  [["#","#","."],[".","#","#"]], 
                  [[".","#","."],["#","#","#"]], 
                  [["#","#","#","#"]], 
                  [["#",".","."],["#","#","#"]], 
                  [["#","#"],["#","#"]], 
                  [["#","#","#"],[".",".","#"]], 
                  [[".","#","#"],["#","#","."]], 
                  [[".","#","."],["#","#","#"]], 
                  [["#","#","."],[".","#","#"]], 
                  [[".","#","."],["#","#","#"]], 
                  [["#","#","#","#"]], 
                  [["#",".","."],["#","#","#"]], 
                  [["#","#"],["#","#"]], 
                  [["#","#","#"],[".",".","#"]]]
        self.assertEqual(tetrisGame(pieces), 3)

    def test_5(self):
        pieces = [[[".","#","."],["#","#","#"]], 
                  [[".",".","#"],["#","#","#"]], 
                  [["#","#","."],[".","#","#"]], 
                  [[".","#","."],["#","#","#"]], 
                  [[".",".","#"],["#","#","#"]], 
                  [["#","#","."],[".","#","#"]]]
        self.assertEqual(tetrisGame(pieces), 1)

    
if __name__ == "__main__":
    unittest.main()

Notes

• The way CodeFights thinks about optimal placements, is not what I would define as optimal. I had to break alot of stuff in my original implementation, to make the CodeFights testcases work.

• I made this in OOP, because I feel that is one of my weaker skilles, therefore would be interested in some OOP pointers.

• I am currently working on a better version of the AI, with my own ruleset. It is not part of the review, but just to let you all know, there might be a Part 2 comming up one day.

Answer 1

IMO your code is actually pretty good. However there are some things I'd change:

• You have white space on the end of some lines, which I'd suggest removing.

• Don't use spaces around the = sign when used to indicate a keyword argument or a default parameter value.

• You can change rotate to be more efficient if you use times % 4. As otherwise you could be looping unneededly.
• Board should take a width and height as parameters.

• Creating the 2D board can be simplified if you use [value] * amount:

  [['.'] * self.max_width for __ in range(self.max_height)]
  

• clear_line doesn't use self.max_width, but instead the magic number 10.

• I'd advise against using a list comprehension if you're passing the comprehension straight to a function. This is as you're forcing \$O(n)\$ memory usage, where \$O(1)\$ may be achieved.

• In find_best_position I'd suggest you change how you use the filter code, by:

  • Not using filter, it's deprecated by some, in favour of list comprehensions.

    I personally only use filter or map if I have a function. Such as:

    data = filter(bool, data)
    

  • It'd be better if you change your filters to be in a loop. This keeps to DRY.

  • I'd find the wanted value once, rather than on each iteration of the list.

And so I'd use:

class Piece():
    def __init__(self, piece):
        self.piece = piece

    @property
    def width(self):
        return len(self.piece[0])

    @property
    def height(self):
        return len(self.piece)

    def rotate(self, times=1):
        for i in range(times % 4):
            self.piece = [row[::-1] for row in zip(*self.piece)]

    # Debugging purposes
    def __str__(self):
       return '\n'.join(''.join(line) for line in self.piece)

class Board():
    def __init__(self, width, height):
        self.max_height = height
        self.max_width = width
        self.board = [['.']*width for __ in range(height)]

    def completed_line(self):
        for i, line in enumerate(self.board):
            if line.count('.') == 0:
                yield i

    def clear_line(self, index):
        del self.board[index]
        self.board.insert(0, ['.' for _ in range(self.max_width)])

    def drop(self, piece, offset):
        last_level = self.max_height - piece.height + 1
        for level in range(last_level):
            for i in range(piece.height):
                for j in range(piece.width):
                    if self.board[level+i][offset+j] == "#" and piece.piece[i][j] == "#":
                        return level - 1
        return last_level - 1

    def place_piece(self, piece, pos):
        level, offset = pos
        for i in range(piece.height):
            for j in range(piece.width):
                if piece.piece[i][j] == "#":
                    self.board[level+i][offset+j] = piece.piece[i][j]

    # Debugging purposes
    def __str__(self):
       return '\n'.join(''.join(line) for line in self.board)

def find_best_position(board, piece):
    result = []
    for rotation in range(4):
        for offset in range(board.max_width - piece.width + 1):
            level = board.drop(piece, offset)
            blocks = sum(b.count('#') for b in board.board[level:level + piece.height])
            result.append([blocks, rotation, offset, level])
        piece.rotate()

    for i, fn in enumerate([max, min, min]):
        key = fn(result, key=lambda x: x[i])[i]
        result = [x for x in result if x[i] == key]
    return result[0]

---

If I were to do this, I'd also make a generic base class. One like collectins.UserList, however with a different interface.

• You can move the 'debugging purposes' into the base function, and make things DRY.
• You can remove the need to use self.board by defining the magic methods you want to use on this base class.
• Using a base class doesn't help that much with code readability here, and so you may not want to use it.

And so the following may be something you want to do, if you expand on your code and make a Rev 2:

class _2DList:
    def __init__(self, list_=None):
        if list_ is None:
            list_ = []
        self.data = list(list_)

    def __getitem__(self, index):
        return self.data[index]

    def __setitem__(self, index, value):
        self.data[index] = value

    def __delitem__(self, index):
        del self.data[index]

    def __len__(self):
        return len(self.data)

    def __iter__(self):
        return iter(self.data)

    def __str__(self):
       return '\n'.join(''.join(line) for line in self.data)

    @property
    def width(self):
        return len(self.data[0])

    @property
    def height(self):
        return len(self.data)

    @staticmethod
    def new_board(self, fill, width, height):
        return [[fill]*width for __ in range(height)]


class Piece(_2DList):
    def rotate(self, times=1):
        for i in range(times):
            self.data = [row[::-1] for row in zip(*self)]


class Board(_2DList):
    def __init__(self, width, height):
        super().__init__(self.new_board('.', width, height))

    def completed_line(self):
        for i, line in enumerate(self):
            if line.count('.') == 0:
                yield i

    def clear_line(self, index):
        del self[index]
        self.data.insert(0, ['.'] * self.width)

    def drop(self, piece, offset):
        last_level = self.height - piece.height + 1
        for level in range(last_level):
            for i in range(piece.height):
                for j in range(piece.width):
                    if self.board[level+i][offset+j] == "#" == piece.piece[i][j]:
                        return level - 1
        return last_level - 1

    def place_piece(self, piece, pos):
        level, offset = pos
        for i in range(piece.height):
            for j in range(piece.width):
                if piece.piece[i][j] == "#":
                    self[level+i][offset+j] = piece.piece[i][j]