Statistics

Problem Statement for "FiveStarPatterns"

Problem Statement

Starting with an empty grid (empty spaces denoted by '.'), you must create the pattern shown in layout by adding lines of 5 '*' characters. Lines may be horizontal or vertical, must stay completely within the grid, and may overlap. Here is an example pattern:


.*....
.*****
.*....
*****.
.*....

This pattern would require 2 horizontal lines and 1 vertical line, for a total of 3 lines. The grid will not be taller than 5 rows or wider than 10 columns. Return the minimum number of lines required to create the pattern shown in layout. If a given pattern cannot be created, return -1.

Definition

Class:
FiveStarPatterns
Method:
leastLines
Parameters:
String[]
Returns:
int
Method signature:
int leastLines(String[] layout)
(be sure your method is public)

Constraints

  • layout will contain between 1 and 5 elements, inclusive.
  • Each element of layout will contain between 1 and 10 characters, inclusive.
  • Each element of layout will contain the same number of characters.
  • Each element of layout will contain only '.' and '*' characters.

Examples

  1. { ".*....", ".*****", ".*....", "*****.", ".*...." }

    Returns: 3

    The example from the problem statement.

  2. { "...*****..", "..*******.", ".*********" }

    Returns: 5

    Note that the lines can overlap. The above example is all horizontal lines: 1 for the first row, 2 for the second row, and 2 more for the third.

  3. { "......", ".****.", ".****.", ".****.", ".****." }

    Returns: -1

    You can't draw lines shorter than 5 '*'s, so there's no way to make this pattern.

  4. { "**********", "**********", "**********", "**********", "*********." }

    Returns: 10

  5. {"."}

    Returns: 0

  6. {"*"}

    Returns: -1

  7. { "**********", "**********", "**********", "**********", "**********"}

    Returns: 10

    10 verticals.

  8. { "...*****..", "**********", "**********", "**********", "**********"}

    Returns: 9

    Best solution uses just horizontals.

  9. { "**********", "**********", "****..****", "**********", "**********"}

    Returns: 12

    8 verticals, plus 4 horizontals.

  10. { "**********", "**********", "****.*****", "**********", "**********"}

    Returns: 10

    verticals in columns 0,1,2,3,9 - then fill with horizontals.

  11. { "*.********", "*.********", "*.********", "*.********"}

    Returns: -1

  12. { "*********", "*********", "*....****", "*********", "*********"}

    Returns: 9

  13. {"....****"}

    Returns: -1

  14. { "...*****", "*****...", "...*****" }

    Returns: 3

  15. { "****..." }

    Returns: -1

  16. { "****" }

    Returns: -1

  17. { "*....", "*....", "*....", "*...."}

    Returns: -1

  18. { "*...*", "*****", "*...*", "*****", "*...*"}

    Returns: 4

  19. { "*****", ".*.*.", ".*.*.", ".*.*.", "*****"}

    Returns: 4

  20. { "*********.", "*...*.***.", "*.*******.", "*****.***.", "*...******"}

    Returns: 9

    verticals at 0,4,6,7,8

  21. { "**********", "********.*", "**********", "*.********", "**********"}

    Returns: 12

  22. { "*.........", "**********", "**********", "**********", "*........."}

    Returns: 7

  23. { "**..*..*..", "********..", "**..*..*..", "**..*****.", "**..*....."}

    Returns: -1

  24. { "**..*..*..", "********..", "**..*..*..", "**..*****.", "**..*..*.."}

    Returns: 6

  25. { "**********", ".*********", "**********", "**********", "*********." }

    Returns: 10

  26. { "**********", ".****.****", "**********", "**********", "*********." }

    Returns: -1

  27. { "..*......*", "..******.*", "..******.*", "..******.*", "..*......*"}

    Returns: 5

  28. { "........*.", "...******.", "...******.", "...******.", "........*."}

    Returns: 4

  29. { "..........", "..**...**.", ".....*....", "..*.....*.", "..*******."}

    Returns: -1

  30. {"*****.*", "**....*", "**....*", "**....*", "**....*" }

    Returns: 4

  31. {".**.******", "*****..*.*", ".**.******", "**********", "******.*.*" }

    Returns: 11

  32. {"**********", "**********", "****..****", "**********", "**.*****.*" }

    Returns: -1

  33. {"**********", "**********", "**********", "**********", "*******.*." }

    Returns: 11

  34. {"*.******.*", "*.******.*", "*.******.*", "*.******.*", "*.******.*" }

    Returns: 8

  35. {"**********", "**********", "****.*****", "**********", "**********" }

    Returns: 10

  36. {"**********", "**********", "****..****", "**********", "**********" }

    Returns: 12

  37. {"******", "******", "******", "******", "******" }

    Returns: 6

  38. {"*********.", ".******.*.", ".*.******.", "**********", ".*..*****." }

    Returns: 9

  39. {"**********", "**********", "**********", "**********", "*********." }

    Returns: 10

  40. {"......", ".****.", ".****.", ".****.", ".****." }

    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: