Statistics

Problem Statement for "Digsaw"

Problem Statement

(Note: This problem statement contains images that should best be viewed in the arena applet.)

You are given N strips of paper. Each strip is a 5 by 1 rectangle, divided into 5 unit squares. Each unit square is either black or white.

Your goal is to arrange all of these strips into a bitmap of height 5 and width N in such a way that the largest possible number appears. Strips can be rotated, and each strip can be placed either horizontally or vertically. Obviously, no two strips may overlap.

We will now explain your goal in more detail. First, we will define the bitmap representations of all decimal digits. Each digit is a bitmap of width 3 and height 5. Below, letters X represent black squares and periods represent white squares. 

..X   XXX   XXX   X.X   XXX
..X   ..X   ..X   X.X   X..
..X   XXX   XXX   XXX   XXX
..X   X..   ..X   ..X   ..X
..X   XXX   XXX   ..X   XXX

XXX   XXX   XXX   XXX   XXX
X..   ..X   X.X   X.X   X.X
XXX   ..X   XXX   XXX   X.X
X.X   ..X   X.X   ..X   X.X
XXX   ..X   XXX   XXX   XXX

The bitmap representation of a multiple-digit number consists of the bitmap representations of its digits. Additionally, each pair of consecutive digits is separated by one column of white squares. For example, below is the bitmap representation of the number 47. 

X.X.XXX
X.X...X
XXX...X
..X...X
..X...X

The value of N will be one of 3, 7, 11, and 15. Your goal is to assemble a 1-digit number if N=3, a 2-digit number if N=7, a 3-digit number if N=11, or a 4-digit number if N=15. If the number you are trying to assemble has more than one digit, it must not have a leading zero.

You will be given a String[] pieces, describing the N strips of paper you have. Find and return the largest number that can be assembled from these pieces. If there is no such number, return -1 instead.

Definition

Class:
Digsaw
Method:
largestNumber
Parameters:
String[]
Returns:
int
Method signature:
int largestNumber(String[] pieces)
(be sure your method is public)

Constraints

  • pieces will contain exactly N elements, where N is one of 3, 7, 11, and 15.
  • Each element in pieces will have exactly 5 characters, and each of these characters will either be an uppercase letter X or a period.

Examples

  1. {"XXX.X","XXX.X","X.X.X"}

    Returns: 5

    Using these three strips, we can assemble either the digit 2 or the digit 5. We return the largest possible answer.

  2. {"XXX..","XXXX.","X..X."}

    Returns: -1

    No number can be assembled from these strips.

  3. {"XXXXX","XXXXX","XXXXX","XXXXX","X...X","X...X","....."}

    Returns: -1

    "00" is not a valid 2-digit number, and nothing else can be assembled.

  4. {"XXX..","XXXXX",".X.XX","...X.","XX...","...X.",".X..."}

    Returns: 47

    Using these seven strips we can assemble the number 47 as shown in the picture below:

  5. {"XXXXX","X...X","XXXXX"}

    Returns: 0

    Zero is a valid answer in case of one-digit numbers.

  6. {"XXXXX","X.X.X","XXXXX",".....","XXXXX","X.X.X","XXXXX",".....","XXXXX","X.X.X","XXXXX"}

    Returns: 888

  7. {"XXXXX","X.X.X","XXXXX",".....","XXXXX","X.X.X","XXXXX",".....","XXXXX","X.X.X","XXXXX",".....","XXXXX","X.X.X","XXXXX"}

    Returns: 8888

  8. {"XXXXX","X.X.X","XXXXX",".....","XXXXX","X.X.X","XXXXX",".....","XXXXX","X.X.X","XXXXX",".....",".XXX.","X.X.X","XXXXX"}

    Returns: -1

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

    Returns: -1

  10. {".....","XXXXX","....."}

    Returns: 1

  11. {"X.X.X","X.X.X","XXXXX"}

    Returns: 3

  12. {"XXXXX","..XXX","..X.."}

    Returns: 4

  13. {"XXXXX","XXX..","..X.X"}

    Returns: -1

  14. {"X....","XXXXX","....X"}

    Returns: 7

  15. {"X.X.X","XXXXX","XXXXX"}

    Returns: 8

  16. {"X.X.X","X.XXX","XXXXX"}

    Returns: 9

  17. {"XXXXX","XXXXX","XXXXX"}

    Returns: -1

  18. {"XXX.X","X.X.X","X.XXX","X.X..","X.X.X","X.X.X","XXXXX"}

    Returns: 60

  19. {"XXX.X","X.X.X","X.XXX","X.X..","X.X.X","X.X..","XXXXX"}

    Returns: -1

    "03" can be assembled but it is not valid.

  20. {"XXXXX","X.XXX","X.X..","X.XXX","XXX.X","X.X.X","..X.X"}

    Returns: 83

  21. {"XXXXX",".X.X.","XX.XX",".X.X.",".X.X.","X....","XX.X."}

    Returns: 70

  22. {"..X.X","X...X","X.X.X","XXX.X","X.XXX","X.XXX","XXXXX"}

    Returns: 90

  23. {"XXX.X","X...X","X....","X.XXX","..X.X","X....","X.XXX"}

    Returns: 75

  24. {"XXX.X","XX.XX",".X.X.","XXXXX","XX.XX",".X...","XX.XX"}

    Returns: 99

  25. {"XXXXX","....X",".....","XXXXX",".....",".....","....X"}

    Returns: 71

  26. {"X.X.X","..X.X","XXX.X","X.XXX","..X.X","XXX.X","X.XXX"}

    Returns: 92

  27. {"XXX.X","X.X.X","X.XXX","X.X.X","X.XXX","XXXXX","..X.."}

    Returns: 99

  28. {"...X.",".X.X.","XX.X.","....X","X.XXX",".X.XX","XX.XX"}

    Returns: 75

  29. {"X.XXX","X.XXX","X.XXX","X.XXX","X.X.X","X.X.X","X...X"}

    Returns: 99

  30. {".....","XXX.X","XX.XX","X.XXX","XXX.X","XX.XX",".....","XX.XX",".X.X.","X.XXX","X.X.X"}

    Returns: 552

  31. {"X.XXX","XXX.X","X.XXX",".....","XXXXX","..X.X",".....","X...X","X.X.X","XXXXX","....."}

    Returns: 901

  32. {"X.X.X","X.X.X","..X..","..X..","XXX.X","..X..","X.X.X","X.X.X","X.X.X","XXX.X","XXX.X"}

    Returns: 440

  33. {"XXX.X",".X.X.","XXXXX","XXXXX",".....","XX...","XX.X.","XX.XX","XXXXX",".X...","X.X.X"}

    Returns: 984

  34. {"X.X.X","X....","XXXXX","X....","XXXXX",".....","X.XXX","X.XXX","X.X.X","X.X.X","X.X.X"}

    Returns: 870

  35. {"XXXXX","XXXXX","XX.XX",".X.X.","XX.XX","XXXXX",".....","...X.","X.X.X","XXX.X","XX.XX"}

    Returns: 998

  36. {"....X","XXXXX","XXXXX",".....","XX.XX",".X.X.",".X.X.","....X","XXX.X","XX.XX","XX.XX"}

    Returns: 987

  37. {"X.X..","X...X","X.XXX","X...X","X.X..","XXX.X","..X.X","..X.X","X.XXX","XXX.X","..X.X"}

    Returns: 705

  38. {"..X..","..X.X","..X.X","XXX.X",".....","XXX.X","X.X.X","XXXXX","..X..","X.X..","..XXX"}

    Returns: 754

  39. {"X.XXX","X.XXX",".....","XXXXX","X.XXX","X.X.X","X.X.X","....X","XXXXX","X.XXX","X.X.X"}

    Returns: 862

  40. {"..X.X","X.XXX","XX.XX","XXX.X","XX.XX",".X.X.","XX.XX","XXX.X","XXXXX",".X.X.","X.X.."}

    Returns: 838

  41. {"XXXXX","XXX..","XXX..",".....","..X..","..X..","..X..","..X..","XXXXX",".....","..X.."}

    Returns: 714

  42. {"...X.",".X...","XXXXX",".X...","XXX.X","X.X.X","X.X.X","X.XXX","X.XXX","...X.","...X."}

    Returns: 915

  43. {"X...X","X.X.X","XXX.X","..X.X","..X.X","X.X..","..X.X","X.XXX","XXX.X","..X.X","..X.X"}

    Returns: 185

  44. {"X....","XXX.X","XXX.X","..X.X","X.X..","..X.X","XXX.X","XXX.X","X.XXX","X.X.X","X.XXX"}

    Returns: 925

  45. {"XXXXX","XXXXX","X....",".....","X....","X...X","XXX.X","XXXXX",".....","X.X.X","XXXXX"}

    Returns: 970

  46. {".X.X.",".X.X.","XXX.X","X.X.X",".X...",".X...","XXXXX","X.XXX","XXXXX","X.X.X",".XXX."}

    Returns: 949

  47. {"X.XXX","X.X.X",".....","X.XXX","X...X","X....","XXX.X","X.XXX","X.XXX","X.X.X","X.X.X","X.XXX",".....","XXXXX","X.X.X"}

    Returns: 5533

  48. {"X.X.X","XXX.X","XXX.X",".....","X.XXX","X.X.X","XXX.X","X....","XXXXX","X.X.X","XXX.X","X.X.X","X...X","X.X.X","....."}

    Returns: 9524

  49. {"....X","XXX..","X...X",".....","X...X","XXXXX","X...X","XXX.X","X....","..X..","XXXXX","X...X","X...X","X.XXX","XXX.."}

    Returns: 5770

  50. {"XXXXX","..X..","X...X","XXXX.","X....","XXXXX","....X","X...X","X...X","XXX.X","..XXX","XXX.X","X...X","X...X","....."}

    Returns: -1

  51. {"XX.X.","XXXXX","...X.",".X.XX",".....",".X.X.",".X.X.","...XX","XX.X.",".....","XX.XX","XXXXX","XXXXX",".X.X.",".X.X."}

    Returns: 8410

  52. {"XXXXX",".X.X.","XX.XX",".X.X.",".X.X.",".X...","XXXXX","XX.X.",".....","XX.X.","XXXXX",".X.X.",".X.X.",".....","...XX"}

    Returns: -1

  53. {"XX.XX","X....",".X.X.","XXXXX","XXXXX","X.XXX","XXX..",".....",".X.XX","..X..","XX.XX","X.XXX","..XXX","....X",".X..."}

    Returns: 5750

  54. {".X.X.","....X","XX.XX",".....","X.XXX","XXXXX","..X..","XXX..","...X.","XXXXX","XX.X.","XX.XX","..XXX","XXX..","X...."}

    Returns: -1

  55. {"XXXXX","X...X","X...X","X.XXX","X.XXX","X.X..","X...X","X...X","X...X","XXXXX","X.X.X","X...X","XXX.X","X.X.X","....."}

    Returns: 9810

  56. {"X...X","X.X..","X.XXX","X...X","X...X","X...X","X.X.X","XXXXX","XXXXX","X...X","X...X",".....","X.X.X","X.XXX",".XX.X"}

    Returns: -1

  57. {"..X.X","XXX.X","X....",".....","....X","X.X.X","X.X.X",".....","XXX.X",".....","X...X","X.XXX","X.XXX","X.X.X","X.XXX"}

    Returns: 7510

  58. {"X.X.X","X....","X.XXX","X.XXX","X.X.X","X.X..","X....","XXX.X",".XX.X",".....","X.XXX","X...X","X.X.X",".....","....."}

    Returns: -1

  59. {"X.XXX","X.X.X","X....","X.XXX","X....","XXXXX",".....",".....",".....","X.XXX","XXXXX","....X","..X.X",".....","XXXXX"}

    Returns: 7631

  60. {".....","XXXXX",".....","..X.X","X.XXX","X....","XXX.X","X....",".....","X.X.X",".....","....X","X.XX.","XXXXX","XXXXX"}

    Returns: -1

  61. {".XXX.","X.X.X","XXX.X",".X.X.","X....","X.XXX","XXX.X","XXXXX",".XXX.",".X.X.","X.X..","X....",".X.X.","XXXXX","....X"}

    Returns: 7063

  62. {"X.XXX","X....","X.XXX",".X.X.",".XXX.",".X.X.","XXXXX",".XXX.","XXXXX","X.X..","X.X.X","....X","....X",".X.X.","X.X.X"}

    Returns: -1

  63. {".XXX.","XXX.X",".XXX.",".....","XX.XX","XX.XX",".XXX.","XXXXX","X.X.X",".X.X.","...X.","XX.XX","XXXXX","XXXXX","...X."}

    Returns: 9963

  64. {"XX.XX","XX.XX",".X.X.",".....","XXX.X","X.X.X",".XXX.","XX.XX",".X.X.",".XXX.","XXXXX","...X.","XXXXX",".XXX.","XXXXX"}

    Returns: 9863

  65. {"....X","X...X","....X","X...X","XXXXX","X...X",".....","X....","X.XXX","X.X.X","X.X.X","XXXXX","X...X","XXXXX","....."}

    Returns: 9761

  66. {".....","X....","X...X","X...X","XXXXX","X.X.X","....X","X...X","....X","X.X.X","X....","XXXXX","XXXXX","X...X","XXX.X"}

    Returns: -1

  67. {"XXX..","XXXXX","X.XXX","XXX.X","..XXX",".....","XXX.X","..X..","X.X.X","..X..","X....","X....","XXX.X","XXX.X","X...X"}

    Returns: 5755

  68. {"XXX..","..X..",".....","X.XXX","X...X","XXX.X","X....","XXX..","X.XXX","XXX.X","X.X.X","XXXXX","X.XXX","X...X","..X.."}

    Returns: 9373

  69. {".....","X.XXX","XXXXX","X.X.X","XXX.X","XXXXX","XXXXX",".....","X....","X.XXX","XXXXX","X.X.X","X.X.X",".....","X...."}

    Returns: 9997

  70. {"XXXXX","XXXXX","....X",".....","XXX..","X.XXX","X.X.X","XXXXX",".....","XXXXX","X.XXX",".....","X.X.X","X....","X.X.X"}

    Returns: -1

  71. {"XXX.X","X.XXX","X.X.X","XXXXX","XXXXX",".....","X.X.X","X.X.X",".....","X.X.X","XXXXX","XXXXX","X...X","XXX.X","....."}

    Returns: 9530

  72. {"X.X.X",".....","XXXXX","X.X.X",".....",".....","XX..X","X.X.X","XXXXX","X.XXX","XXXXX","X...X","X.XXX","XXXXX","X.X.X"}

    Returns: -1

  73. {"X.X..","XXXXX","X.XXX","X.X.X","X...X","X.XXX","XXX.X","X....","XXXXX",".....","X.X.X",".....","....X","XXXXX","XXX.X"}

    Returns: 9907

  74. {"X.X.X","XXX.X",".....","XXXXX","XXXXX","X.XXX","XXX.X","XXX.X","X...X","....X","X....","..X..","XXXXX","..X.X","X.X.X"}

    Returns: -1

  75. {"X.X.X","X.X.X","X.X.X","X.X.X","XXXXX","XXX.X","X.X.X",".....","XXX.X","XXX.X","XXX.X","X.XXX",".....","X.X.X","X.X.X"}

    Returns: 9530

  76. {"X.X.X","XXX.X","X.X.X","X.X.X","X.XXX","XXXXX","X.XXX",".....","X.X.X","X...X","X.X.X","XXX.X",".....","X.X.X","X.XXX"}

    Returns: 5393

  77. {"X.X.X","XX.X.","XXX.X","X.XXX","X.X..","XXX.X","X.XXX","XX.XX","..X..",".....",".X.X.","XX.X.",".X.X.","XXX.X","..XXX"}

    Returns: 5346

  78. {".....","X.X.X","X.XX.","XXX.X","XX.XX","X.XXX","XX.X.","X.XXX","X.XXX",".X.X.","XXX..","..X..",".X.X.","X.X..",".X.XX"}

    Returns: -1

  79. {"X.XXX","XXXXX",".....","X.X.X","XXXXX","XXXXX","X.XXX","X.X.X","X.XXX",".....",".....","X.XXX","X.X.X",".....","....."}

    Returns: 9951

  80. {".....","XXXXX","X.X.X","XXXXX",".....",".....",".....","X.XXX","XXXXX","X.X.X","XXXXX","XXX.X",".....","X.X.X","XXX.X"}

    Returns: 9991

  81. {"X.X.X","X.XXX","XXX.X","X.X.X","XXXXX",".....","X....","X.XXX","....X",".....","X.X.X","XXXXX","X.X.X","X.X.X","XXXXX"}

    Returns: 9870

  82. {"X.X.X","....X","X...X",".....","X.X.X","X.X.X","XXXXX","X.X.X","X....","XXXXX","XXXXX","X.XXX",".....","XXX.X","XXX.X"}

    Returns: 9700

  83. {"X.XXX","X.X.X","....X","X.XXX","X.XXX",".....","..X..","X.X.X","X.X..","XXX.X","X....","XXX.X","XXX.X","X.XXX","X.X.X"}

    Returns: 9576

  84. {"X.XXX",".....","X.XXX","..X..",".....","X.XXX","X....","..X.X","XXX.X","X.XXX","X.X.X","X.X.X","X.X.X","XXX.X","X.XXX"}

    Returns: -1

  85. {"X.X.X",".....","..X..","X.XXX","X.X.X","XXX..","XXX.X",".....","X.X.X","X.X.X","XXXXX",".....","XXX.X","XXX.X","....."}

    Returns: 5410

  86. {"..XXX","X.X.X","XXXXX","X.X.X","XXX.X","X.X.X","X.XXX","XXXXX",".....","X.XXX",".....","..X..",".....","X.X.X","....."}

    Returns: 9410

  87. {"XX.XX","XX.XX",".....","X.X.X",".X...","X.XXX",".X.X.","XX.XX","XXX.X","XX.XX","XXXXX","XX.XX",".X.X.",".X...","XX.XX"}

    Returns: 9935

  88. {"XX.XX","XXX.X","XX.XX",".X.X.","XXXXX","XXX.X","...X.","XX.XX",".X...","XX.XX","XX.XX",".....","X...X",".X.X.","XX.XX"}

    Returns: -1

  89. {".X...","..X..","..X..","X.X.X","...X.","...X.","XXX.X","..X..","...X.","X...X","..X..","X...X","..X..","X.X.X",".X..."}

    Returns: 1114

  90. {"X.X.X","..X..",".X...","...X.","..X..","..X..","....X","..X..",".X...","X...X","XXX.X",".X...","...X.","X.X.X","..X.."}

    Returns: -1

  91. {"X...X","X.XXX",".....","X.XXX","X...X","X....",".....","XXXXX","XXXXX","X...X","XXX.X","X.X.X","X...X","X....","X.X.X"}

    Returns: 9977

  92. {"X...X",".....","XXX.X","XXXXX","X...X","X...X",".....","X.X.X","XXX.X","XXXXX","....X","X...X","X.XXX","X...X","X.X.X"}

    Returns: 5510

  93. {".X.X.","XX.XX","X.X..","X.X.X","XX.XX","X.X.X","XXX.X","...X.","..X.X","XX.XX","..X.X","X.XXX","X...X","X.X.X","X...X"}

    Returns: 4854

  94. {"X...X",".X.X.","XX.XX","..X.X","..X.X","XX.XX","X.X.X","XXX.X","..X.X","X.X.X","X.X..","X...X","X.XXX","...X.","XX.XX"}

    Returns: 7894

  95. {".X...","...X.","XXX.X","X.XXX","X.X..","X.XXX","XXXXX","X...X","XX...",".....","X.X.X","...XX","...XX","XXXXX","XXX.X"}

    Returns: 9815

  96. {"...XX","...X.","...XX","X...X","XXX.X",".....","X.X..","...X.","XXXXX","X.XXX","XX.XX","X.XXX","...XX","X.X.X","XXX.X"}

    Returns: -1

  97. {"XXX.X","XXX.X","X.X.X","X.XXX","X.X.X","X...X","XXX.X","X.XXX","XXXXX","X.X.X","X.X.X",".....","XXX.X","XXXXX","....."}

    Returns: 9999

  98. {"X...X","X.XXX","X...X","X.X.X","X.XXX",".....","X.XXX","XXX.X","XXX.X","XXXXX","XXX.X",".....","X.X.X","X.X.X","XXXXX"}

    Returns: 9993

  99. {"XXX.X","X.X.X",".....","XXXXX",".....","XXXXX","..X..","XXXXX",".....","X.X.X","XXX.X","X.XXX",".....",".....","XXX.."}

    Returns: 9541

  100. {"X.X.X",".....","X.XXX","XXXXX","X.XXX","X.XXX","XXXXX",".....","XXXXX","..X..","XXXX.",".....",".....",".....","X.X.X"}

    Returns: -1

  101. {"X.X.X","X.XXX","XXX.X","..X..","XXXXX","X.XXX","X.X.X",".....","XXX.X","X.X..","X.XXX",".....","XXXXX","XXX.X","X.X.X"}

    Returns: 9935

  102. {"XXXXX",".....",".....","X.XXX","XXX.X","XXXXX","X.XXX","X.X..","X.XXX","X.X.X","X.X.X","..X..","X..XX","X.X.X","XXX.X"}

    Returns: -1

  103. {"X.X..","X.X.X","X.X.X","XXXXX","X...X","X.XXX","XXX.X","XXXXX",".....","XXXXX","X.X.X","X.XXX",".....","X.XXX","X.X.X"}

    Returns: 9903

  104. {".....","X.XXX","X.XXX","XXX.X","XXXXX","X.X.X","X.X.X",".....","X.X.X","X...X","..X.X","X.XXX","XX.XX","X.X.X","XXXXX"}

    Returns: -1

  105. {"X.X.X","XX.X.","X.X.X","..X.X",".X...","XXX.X",".X.X.","..X..","X.X..","XX.XX","XX...","XXX.X","X.X.X","XXX.X","X.XXX"}

    Returns: 4946

  106. {"X.XXX","..X..","XX.XX","X.X..",".X.X.","X.X.X","XXX.X","XX.X.","X.XXX","XXX.X","XX...",".X...","X.X.X","X.XXX","..X.X"}

    Returns: -1

  107. {"XXXXX","XXXXX",".X.X.","XXXXX","....X","X.X.X",".....",".X...","XXXXX",".X.X.","X....",".....",".X...",".X.XX","....."}

    Returns: 8714

  108. {".X...",".X.X.","X....",".X.X.","XX.X.","XXXXX","XXXXX","X....",".....","X.X.X",".X...",".....","XXXXX","XXXXX","X...."}

    Returns: -1

  109. {"X.XXX","...X.","X.X..","XXX.X",".XXX.",".XXX.","X.X.X",".X...","X.XXX","X.X.X","X.XXX","XXXXX","XXXXX",".XXX.","X.X.X"}

    Returns: 9859

  110. {"XXX.X","...X.",".XXX.","XXXXX",".XXX.",".XXX.","X.X..","XXXXX","...X.","..X.X","X.X.X","XXX.X","X.XXX","X.XXX","X.X.X"}

    Returns: 9583

  111. {"XXXXX","XX.XX","XXX.X","X.XXX",".....",".....","XXX.X","XXXXX","X.XXX","X...X",".X.X.","XX.XX","X.X..","X.X.X","XX.XX"}

    Returns: 9620

  112. {"XXXXX","XX.XX","XXXXX","XX.XX",".X.X.","X...X","X.XXX","X.X..","XX.XX","X.XX.",".....","X.XXX",".....","X.XXX","X.X.X"}

    Returns: -1

  113. {"XXX.X", "XXX.X", "X.X.X" }

    Returns: 5

  114. {"XXX.X", "XX.XX", "X.XXX", "X....", ".X.X.", "X.X.X", "XXX..", ".X.XX", "X.XXX", "X.X..", ".X.X.", "X...X", "XXX..", ".X.XX", "X.XXX" }

    Returns: 6789

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: