Unjumpers

SRM 376 · 2007-11-14 · by jmzero

SRM 376 · 2007-11-14 · by jmzero · Greedy

Show categories

Class Name: Unjumpers

Return Type: int

Method Name: reachableTargets

Arg Types: (string, vector<string>)

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:

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.
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.
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.

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

"**."
{
"..*",
"*.**",
".*.*"}
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.

"..***"
{
"..****..*",
"..***....",
"..****"}
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.

"*..*"
{
"*..*......",
"*.....*...",
"...*.....*",
"...*..*...",
"*........*",
"*...***..*"}
Returns: 6

All of these layouts can be reached.

"...***"
{
"***...",
"..****",
"**....**",
".*.*.*"}
Returns: 3

Only the second layout shown is unreachable.

".................................................."
{"."}
Returns: 1

"*.."
{"*","*...","*.....","*.........",".*.....",".*"}
Returns: 4

Position A

"*..*"
{"*..*","***",
"************************************************",
"**...*",
"**....*",
"**.....*",
"...."
}
Returns: 4

Position E (first 4 are reachable)

"**************************************************"
{
"**********************************************.**.",
"******************************************..*.***.",
".*****************************************..*.***.",
".**.**.**.**.**.**.**.**.**.**.**.**.**....******.",
".***..************************************..*.***.",
".***..********************************************",
".**.**.**.**.**.**.**.**.**.**.**.**.**.**.**.****",
".**.**.**.**.**.**.**.**.**.**.**.**.**....*******",
".**.**.**.**.**.**.**.*..**.**.**.**.**....*******",
"**************************************************"
}
Returns: 7

Unreachable: 2,3 and 8

"****..........**.*..******..***..*"
{"*..*.*.*...****.*",
"**..**..*..****.*.*.**.....****.**",
"****.*.**.***...*...*...*....*..**.****..",
"..**..**.*.*****..*.*.**.***.*..*****...*...*",
"*.",
"..*.**.....****.*******.****",
"***.**...*",
"****....*.*.*.**......*..",
"**..**..**..**..*..**.**.*****..****..**......**",
"**.*..****......*.*",
".*..*.***.*..."
}
Returns: 4

Random lengths...

10)

"*******.*******..*.**********.****.*.***.*"
{"***************..**.****************.****",
"***************.***...**.*****.**.*.***.***..**",
"*.**.*******.*.****.*.***.**.****..****.*.*",
"****.******.**.**..*.***..******.*.********.***",
"***************.*****.*****.************..*.**.*",
"***.*.***..***.*..***.**********************.***",
"****.**********.*..****.*****.*..**.**..",
".***.**..*.**************..************.****.***",
"*****.***.*.**.***.*.**.*********.*...********",
"..*.****.********.*******.********.*********",
"*************.**..******..*.*********..******",
"**.***.*********.**************.********.**",
".***.********.*********..******..******.****",
"**.****.*****.*.*.**.****..******.*....*******",
"*.****.*.*.****.*****.*******.***************.****",
"***.*************.*******.*.***.*..********",
"***.*...********..****************.*****..*****",
"****.******.*********.**.***********.***..*...***",
"***********.*.******.*****.***.******.**.",
"*.***.******.*****.**.******.****.****.*.**",
"******.*.****.*******.******..**********.**..",
"*.***.***********.*******.********..**************",
".*****.****************.*********************",
"**..**.**.**..*.***.**.*******.****.******",
"**.*.*.******.*.**********.*.***********.**.*****",
".**.**.**..***....**********.*******.****.*.***.",
"*.******.**********************.*.******.*.*",
"**.**.***.****.**.*******.***.*.*********.***..**",
".******..****.***..*****.**.************.",
"..****.********.**.*.**.*.*.*********.*********",
"*.****************.*****************.***.",
".****..**.**.**.***..******.****.*****.*.******.*.",
"***.***.***..************.****.**.*****.*.*",
".****.***********.***.***.*.**********.*******",
"**.***.**..**.***.*******.****.**********.",
"********.**.***.******.****.****.*******.",
"********.*.**********.**.******.**.*************",
"*.****.**.**.*.**.****.*****.*******.*.*******..",
"*.*******.*********.***.*************..**.",
"**.********.***.*..************.*************..*",
"****...**.***.**********.*..*..*****.****",
".*******.**.*.**.************.*****...***.****",
"******.**..****.****.*..*.*..****************",
"**.*************************.***.********.",
"**.******.****.*.***..*.***********..***.****.*..*",
"**..*******.*.**.******.***********.******.**.",
".**********.*.********.*******.************..**",
"*.**.*****.***.**.**********.****.**.****.****",
"*****.*********.*.**.**.**.*..**.****.*.****",
".**.**.****.*..*.******.**.***.*****.******.**"}
Returns: 8

Dense

11)

"......*.....*..........................*......"
{"...*......................................*..",
".....*..*........*...................*.......*.",
".........****..............................*.",
".....*...........................................",
"..........*..........................*.......*....",
".....................*........................",
".............*....*.*........*................",
"...*.........*........*....................",
"..*..***.....................................",
"....*...................*..*.............",
".......................*............*...",
"............................*........*....*",
"............*..............................",
".............*.*...........................",
"*.*..*...*.*..........*..................",
"...........................................*..",
"....................*.......*.....*...........",
"....*............*..........................",
".......*..*...*.........*....................*...",
"......................*.......................",
"*..................*.....*.....................",
".....................*.........*...............",
"....................................*...*..",
".................*...........*....................",
"..........................................",
"...............*..................*...........",
".*...................*......................",
".....................................*....",
"...............................*...............",
"..*...................*.....***....*............",
"..............*.............................",
"........*.*..........*.*...........*......",
"............................*.......*........",
"..............................*.................",
".......*.*...................................",
"..*............................................",
".................*...............*........",
".......*...................*......*........",
"....*............................*...........*..",
".........*.......*.......................",
"..*..........................................",
"..................*.*........................",
"..........*........................*......",
"...............................................",
".................................*........",
"...........................................*.",
".............*..............*....**....*.....",
"...*....................*................**....",
"....*..............*........*.................",
".*....................................*.*....."}
Returns: 12

Sparse

15)

"*"
{"**..*.**",
"..*.**",
"*.*..*.**",
"***....*.",
"...**..."}
Returns: 0

Unlucky...

16)

".*"
{"**..*.**",
"..*.**",
"...*..*...*.***",
"***....*.",
"...*....*....."}
Returns: 5

All are "B"

17)

"*"
{"*********.***.******",
"***..***.*****.*.***",
"****.**********..**.",
"*****.********.*****",
"****.*.*******.****.",
"**.*******.*******.*",
"****.**********..***",
"..******.****.******",
"*****.********..****",
"********************"}
Returns: 2

Tests 17-20 are same targets, want to ensure all reachable. 2 "A"s

18)

".*"
{"*********.***.******",
"***..***.*****.*.***",
"****.**********..**.",
"*****.********.*****",
"****.*.*******.****.",
"**.*******.*******.*",
"****.**********..***",
"..******.****.******",
"*****.********..****",
"********************"}
Returns: 3

3 "B"s

19)

"..*"
{"*********.***.******",
"***..***.*****.*.***",
"****.**********..**.",
"*****.********.*****",
"****.*.*******.****.",
"**.*******.*******.*",
"****.**********..***",
"..******.****.******",
"*****.********..****",
"********************"}
Returns: 3

3 "C"s

20)

"***"
{"*********.***.******",
"***..***.*****.*.***",
"****.**********..**.",
"*****.********.*****",
"****.*.*******.****.",
"**.*******.*******.*",
"****.**********..***",
"..******.****.******",
"*****.********..****",
"********************"}
Returns: 2

2 "E"s - total of 10. Good.

25)

"**************************************************"
{
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"**************************************************",
"***********************.**.***********************",
"***********************************************...",
"...***********************************************"
}
Returns: 50

Perhaps solutions will find this mass of *s imposing or something.

Submissions are judged against all 38 archived test cases, of which 18 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Unjumpers with a public method int reachableTargets(string start, vector<string> targets) · 38 test cases · 2 s / 256 MB per case