TopCoder Statistics - Problem Statement

Problem Statement

In a 4x4 frame you have 8 bricks of various sizes. Given an initial configuration of the bricks and a desired final configuration, find the least number of moves required to get from the initial configuration to the final configuration.

The 8 bricks will always be the following: four 1x1 bricks, three 1x2 bricks and one 2x2 brick. Some of the 1x2 bricks may be horizontally oriented, and some may be vertically oriented. Rotating a brick is not allowed, so if the initial and final configuration have a different number of horizontally oriented 1x2 bricks, clearly no solution exists.

14 of the 16 squares in the field will be occupied with bricks, the remaining two will be empty. A legal move requires moving one brick one square in either of the four directions up, down, left or right so at least one of the previous empty squares gets occupied by the moved brick. Note that moving the 2x2 brick in any direction (or the 1x2 brick in two of the four directions) will require that the empty squares are adjacent to each other.

A configuration will be described as a String[] containing 4 elements where each element will contain 4 characters. Possible characters are digits '1','2','3','4' marking where the four 1x1 bricks are, 'A','B','C' marking the three 1x2 bricks, '#' marking the 2x2 brick and '.' marking an empty square. A configuration is valid if it contains the correct number of bricks (four 1x1, three 1x2 and one 2x2) and no two different bricks use the same character in the description. For instance, a valid configuration could look like this:


{".##B",
 ".##B",
 "C42A",
 "C13A"}

Two configurations are considered to be identical if all bricks of the same size and orientation occupy the same positions in both configurations. Thus configurations 1) and 2) below are identical while configuration 3) is not identical with either 1) or 2).


1) {"AABC",   2) {"AACB",   3) {"AABB",
    "##BC",       "##CB",       "##CC",
    "##..",       "##..",       "##..",
    "1234"}       "4213"}       "1243"}

Create a class SlidingGame containing the method solve which takes a String[] initialconfig and a String[] finalconfig and returns an int, the minimal number of moves required to get from initialconfig into a configuration identical with finalconfig. If no solution exists, return -1.

Definition

Class:: SlidingGame
Method:: solve
Parameters:: String[], String[]
Returns:: int
Method signature:: int solve(String[] initialconfig, String[] finalconfig)
(be sure your method is public)

Notes

If no solution exists, return -1 (see example 2).
The total number of unique legal configurations is 24240.

Constraints

initialconfig and finalconfig will contain exactly 4 elements.
Each element in initialconfig and finalconfig will contain exactly 4 characters.
Both initialconfig and finalconfig will be a valid configuration of the bricks according to the description above.

Examples

{"AA12", "BB##", "C.##", "C.34"}

{"CC42", "AA##", "B.##", "B.13"}

Returns: 0

These two configurations are actually the same, so the method should return 0.
{"AA12", "B##C", "B##C", "34.."}

{"BAA1", "B..2", "3##C", "4##C"}

Returns: 8

The shortest solution requires 8 moves: "C" down, "2" down, "1" right, "A" right, "B" up, "3" up, "4" left and "#" down.
{"AA12", "BB.3", "C.##", "C4##"}

{"AA12", "BB.3", "##C.", "##C4"}

Returns: -1

It's not possible to reach the final configuration from the initial configuration, so the method should return -1.
{"AA##", "BB##", "1234", "CC.."}

{"1..2", "AA34", "##BB", "##CC"}

Returns: 70
{"AABB","CC##","12##","34.."}

{"BB##","AA##","CC..","1234"}

Returns: 11
{"AABB","CC12","34##","..##"}

{"ABC.","ABC.","34##","12##"}

Returns: -1
{"##AA","##1B","23CB","4.C."}

{"##12","##AA","3BC.","4BC."}

Returns: 73
{".##1","2##3","ABBC","A.4C"}

{"1##.","2##3","ABBC","A4.C"}

Returns: 94
{"1234","AABB","CC##","..##"}

{"12AA","BB34","CC##","..##"}

Returns: 15
{"1.2.","AA##","BC##","BC34"}

{"BCAA","BC..","1##2","3##4"}

Returns: 24
{"1.2.","AA##","BC##","BC34"}

{"12AA","BB34","CC##","..##"}

Returns: -1
{"AA##","BB##","CC12","34.."}

{".##1",".##2","AA34","BBCC"}

Returns: 102
{".##1",".##2","AA34","BBCC"}

{"AABB","12CC","3##.","4##."}

Returns: 123
{"A.BC","A.BC","12##","34##"}

{"12AB","34AB","##.C","##.C"}

Returns: 19
{"AA..","CBB1","C##2","3##4"}

{"AA12","BB.3","C.##","C4##"}

Returns: 10
{"A1..","A234","##BC","##BC"}

{"A##1","A##.","2BC.","3BC4"}

Returns: 67
{"A1..","A234","##BC","##BC"}

{".##1",".##2","A3BC","A4BC"}

Returns: 75
{"A1..","A234","##BC","##BC"}

{"##12","##A.","B.AC","B34C"}

Returns: 81
{"A1..","A234","##BC","##BC"}

{"##1A","##2A","B.C.","B3C4"}

Returns: 87
{"A1..","A234","##BC","##BC"}

{"##1A","##2A","B.C3","B4C."}

Returns: 88
{"AA..","1234","##BC","##BC"}

{"##AA","##B1","2.BC","34.C"}

Returns: 50
{"AA..","1234","##BC","##BC"}

{".AA1","##BC","##BC","2.34"}

Returns: 43
{"AA..","1234","##BC","##BC"}

{"##12","##AA","3B.C","4B.C"}

Returns: 34
{"AA..","1234","##BC","##BC"}

{"12B.","AAB.","##3C","##4C"}

Returns: 17
{"AA..","1234","##BC","##BC"}

{"12..","34AA","##BC","##BC"}

Returns: 9
{"AA..","1234","##BC","##BC"}

{".AA.","1234","##BC","##BC"}

Returns: 1
{"AA..","1234","##BC","##BC"}

{"BB..","1423","##AC","##AC"}

Returns: 0
{"AAC1","BBC2","##..","##34"}

{"AABB","##.1","##C2",".3C4"}

Returns: 9
{"AAC1","BBC2","##..","##34"}

{"12AA","34BB","##.C","##.C"}

Returns: 37
{"AAC1","BBC2","##..","##34"}

{".1AA","BB2.","3##C","4##C"}

Returns: 47
{"AAC1","BBC2","##..","##34"}

{".1AA","23BB","##C4","##C."}

Returns: 59
{"A1B3","A2B4","##CC","##.."}

{"AB13","AB24","##CC","##.."}

Returns: -1

Statistics

Problem Statement for "SlidingGame"

Problem Statement

Definition

Notes

Constraints

Examples