Statistics

Problem Statement for "Tetramino"

Problem Statement

In a well known computer game you drop tetramino pieces into a playfield. The goal of the game is to completely fill lines in the playfield. Given a partially filled playfield and a piece, you are to determine the maximum number of complete lines you can create by dropping this piece.

The playfield is between 4 and 10 tiles in width (inclusive) and between 4 and 20 tiles in height (inclusive). There are 7 different tetramino pieces, each occupying 4 tiles:


1) ###     2) ###    3)  ##   4)  ##    5)  ##    6)  ###   7)  ####
     #        #          ##      ##          ##        #

Before dropping a piece, you may rotate it 90, 180 or 270 degrees, or not at all. Then you select a horizontal position where you want to drop the piece. This rotation, and the selecting of the horizontal position, can be considered done above the playfield. Thus, there will never be a hindrance in the actual rotation or horizontal movement (see example 1). However, once the horizontal position and rotation have been decided, they can't be changed while the piece is being dropped (see example 0).

The final location of the piece after it has been dropped must be fully within the playfield. If it's not possible to drop a piece due to this rule, it is game over and you should return -1 (see example 2).

Create a class Tetramino which contains the method maxLines which takes a String[] playfield which is the partially filled playfield (element i in playfield corresponds to line i in the playfield - element 0 is the top line - and each line will only contain the characters '.', an empty spot, and '#', a filled spot), and a int piece representing the piece to be dropped (between 1 and 7, inclusive, using the system above), and returns an int with the maximum number of lines that can be completed, or -1 if it's not possible to drop the piece anywhere.

Definition

Class:
Tetramino
Method:
maxLines
Parameters:
String[], int
Returns:
int
Method signature:
int maxLines(String[] playfield, int piece)
(be sure your method is public)

Notes

  • It's not allowed to slide a piece. After the initial (optional) rotation and horizontal movement, it must be possible for the piece to fall straight down to its final location without additional horizontal movement or rotations.
  • A piece may not stay in midair. It must be dropped as far as possible, until it either hits the bottom of the playfield or an obstacle which blocks the dropping.
  • The piece will begin falling above the playfield.

Constraints

  • playfield will contain between 4 and 20 elements, inclusive.
  • The length of each element in playfield will be between 4 and 10, inclusive.
  • All elements in playfield will be of the same length.
  • Each element in playfield will only contain the characters '.' and '#'.
  • Each element in playfield will contain at least one '.'.
  • piece will be between 1 and 7, inclusive.

Examples

  1. {".......", "##..###", "#.....#", "#.....#", "##....#", "####..#", "####..#"}

    3

    Returns: 0

    Since it's not possible to move the piece to the right once it has passed the second line, it's not possible to complete any lines. Thus the method should return 0.

  2. {".####", ".#..#", ".##.#", "..###", ".####", ".####", ".####", ".####", ".####", ".##.#", ".####", ".####", "#.###", "####."}

    7

    Returns: 3

    It's possible to rotate and put the piece into the leftmost column. This will complete 3 lines, so the method should return 3.

  3. {"#.########", "##.#######", "######.###", "#....#####", "#...##.###"}

    2

    Returns: -1

    The playfield is almost filled and the piece can't be placed anywhere since it has to fall from above the playfield. The method should return -1.

  4. {".....", ".....", "###..", "###..", "####.", "####.", "####."}

    4

    Returns: 2

    By rotating and dropping the piece to the far right, it's possible to clear 2 lines.

  5. {".....", ".....", "###..", "###..", "####.", "####.", "####."}

    5

    Returns: 1

  6. {".#########","...#######","######....","..........","..........","..........",".........."}

    1

    Returns: -1

  7. {"##.######.","##.##.####","##.#######","##.#####.#","######.###","#########.","########.#","#######.##","######.###","#####.####","####.#####","###.######","##.#######","#.########",".#########","#.########","##.#######","###.######","####.#####","#####.####"}

    7

    Returns: 1

  8. {".......",".......","####...","######.","......."}

    1

    Returns: 2

  9. {".......",".......",".......",".......","####..."}

    1

    Returns: 1

  10. {".......",".......",".......",".......","#####.."}

    1

    Returns: 1

  11. {".......",".......","#####..","#......","#......"}

    1

    Returns: 1

  12. {".......",".......","####...","####.##","......."}

    2

    Returns: 2

  13. {".......",".......",".......",".......","####..."}

    2

    Returns: 1

  14. {".......",".......",".......",".......","#####.."}

    2

    Returns: 1

  15. {".......",".......","#####..","#......","#......"}

    2

    Returns: 1

  16. {".......",".......","###..##","###..##","...#..."}

    3

    Returns: 2

  17. {".......",".......",".......",".......","###..##"}

    4

    Returns: 1

  18. {".......",".......",".......","#####..","######."}

    4

    Returns: 2

  19. {".......",".......",".......","..#####",".######"}

    5

    Returns: 2

  20. {".......",".......",".......",".......","#####.."}

    5

    Returns: 1

  21. {".......",".......",".......",".......","###..##"}

    5

    Returns: 1

  22. {".......",".......",".......","#####..","######."}

    5

    Returns: 1

  23. {".......",".......",".......","..#####",".######"}

    4

    Returns: 1

  24. {".......",".......",".......",".......","#####.."}

    4

    Returns: 0

  25. {".......",".......",".......","###...#","......."}

    6

    Returns: 1

  26. {".......",".......","###...#",".......","......."}

    6

    Returns: 0

  27. {"........",".......#",".......#","#####..#","######.#"}

    6

    Returns: 2

  28. {".......",".......","##.....","##..###","##.####"}

    6

    Returns: 2

  29. {".......",".......",".......","##...##"}

    6

    Returns: 1

  30. {"........","........","........","........","##....##"}

    7

    Returns: 1

  31. {"........","........","........","##....##","........"}

    7

    Returns: 0

  32. {".###",".###",".###",".###"}

    7

    Returns: 4

  33. {"###.","#.#.",".##.","##.."}

    7

    Returns: 1

  34. {".###",".###",".###","###."}

    7

    Returns: -1

  35. {"###.","##.#","#.##",".###"}

    7

    Returns: -1

  36. {"....","#.##","#.##","#.##"}

    1

    Returns: 2

  37. {"....","#.##","#.##","#.##"}

    2

    Returns: 2

  38. {"....","#.##","#.##","#.##"}

    6

    Returns: 1

  39. {"#.##","#.##","#.##","#.##"}

    7

    Returns: 4

  40. {"......","......",".#..##","......","##..##"}

    4

    Returns: 0

  41. {"......","......",".#..##","......","##..##"}

    5

    Returns: 0

  42. {".....",".....",".....","....."}

    7

    Returns: 0

  43. {"....","....","....","...."}

    7

    Returns: 1

  44. {"#........#",".#......#.","..#....#..","...#..#...","....##....","....##....","...#..#...","..#....#..",".#......#.","#........#","#........#",".#......#.","..#....#..","...#..#...","....##....","....##....","...#..#...","..#....#..",".#......#.","#........#"}

    2

    Returns: 0

  45. {"#.........","#.########","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........",".........."}

    6

    Returns: -1

  46. {"..........","..........","..........","..........","..........","..........","..........",".######...","########..","########..","#########.","#.......#.",".#.....##.","..#...#.#.","...#.#..#.","....#...#.","...#.#..#.","..#...#.#.",".#.....##.","#.......#."}

    4

    Returns: 2

  47. {"..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........",".........."}

    6

    Returns: 0

  48. { "#.########", "##.#######", "######.###", "#....#####", "#...##.###" }

    2

    Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: