TopCoder problem "Unjumpers" used in SRM 376 (Division I Level Three)



Problem Statement

    

Unjumpers is a puzzle played on a board consisting of 100 squares in a straight line. Pawns are placed in a certain pattern on the board, and your goal is to see which other patterns can be created starting from that position. There are 3 legal moves in Unjumpers:

  1. Jump: A pawn jumps over an adjacent pawn and lands in the square immediately beyond the jumped pawn (in the same direction). The jumped pawn is removed from the board. To perform this move, there must be an adjacent pawn to jump, and the square in which the pawn lands must be unoccupied.
  2. Unjump: A pawn jumps over an adjacent empty space and lands in the square immediately beyond that space (in the same direction). A new pawn appears in the square that was jumped (between the starting and ending squares). To perform this move, both the middle and ending squares must be unoccupied.
  3. Superjump: A pawn moves 3 squares in one direction. To do this move, the target square must be empty. The two jumped squares may or may not have pawns - and they are not affected by the move.

Only one pawn can move at a time, and pawns may never move off of the board.

You are given a String start containing the initial layout of the board. Each character of the string describes one square, with the first character describing the leftmost square. In the string, '.' represents an empty space while '*' represents a pawn. You are also given a String[] targets, each element of which is a target layout formatted in the same way. The board is always 100 squares wide. The Strings given will specify up to 50 of the first (leftmost) squares of the layout. You must assume that the remaining squares are all empty, both when considering the the start position and when considering the various target positions.

For each target layout, evaluate whether that layout is reachable using any number of legal moves starting at the initial layout each time. Return the number of target layouts that can be reached.

 

Definition

    
Class:Unjumpers
Method:reachableTargets
Parameters:String, String[]
Returns:int
Method signature:int reachableTargets(String start, String[] targets)
(be sure your method is public)
    
 

Constraints

-start will contain between 1 and 50 characters, inclusive.
-start will contain only '*' and '.' characters.
-targets will contain between 1 and 50 elements, inclusive.
-Each element of targets will contain between 1 and 50 characters, inclusive.
-Each element of targets will contain only '*' and '.' characters.
 

Examples

0)
    
"**."
{
"..*",
"*.**",
".*.*"}
Returns: 3
Each of the 3 target layouts can be reached in one move - the first is one jump, the second is one unjump, and the third is one superjump.
1)
    
"..***"
{
"..****..*",
"..***....",
"..****"}
Returns: 2
The first layout is reachable with a little ingenuity. The second layout doesn't require any moves (it's the same position, just with some extra blank spaces shown). The third is unreachable.
2)
    
"*..*"
{
"*..*......",
"*.....*...",
"...*.....*",
"...*..*...",
"*........*",
"*...***..*"}
Returns: 6
All of these layouts can be reached.
3)
    
"...***" 
{
"***...",
"..****",
"**....**",
".*.*.*"}
Returns: 3
Only the second layout shown is unreachable.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8288

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10796&pm=8288

Writer:

jmzero

Testers:

PabloGilberto , Olexiy , misof , ivan_metelsky

Problem categories:

Greedy