Problem Statement
It's Christmas and that means presents!
Well, this sucks. Your baby brother got a brand new PS5 while you got new socks and a subscription to the Snake Enthusiast Quarterly.
Watching your baby brother unwrap and plug in the PS5 hurts. To get rid of those thoughts, you pull out your trusty Nokia 3310 and launch a game of snake. And soon you are distracted by a snake puzzle.
The game world, given in the
Example snake movement is shown below. The snake is given as the sequence of letters "abcdefgh", with 'a' being the head. (This exact format, generalized to an arbitrary length, will be used as the input format.) The head moved to the left.
........ ........ ....hg.. .....h.. ..ab.f.. .abc.g.. ...cde.. becomes ...def.. ........ ........ ........ ........ ........ ........ ........ ........
As a special case, the head is allowed to move into the cell currently occupied by the tail, as in the same movement the tail will leave that cell. (The head cannot move into another body cell, and it cannot attempt to leave the game world.)
We will call an empty cell clearly reachable if the head can reach that cell by a sequence of moves such that during the sequence the head only visits cells that are empty at this moment. (In other words, a clearly reachable cell would be reachable even if the snake grew after each move, which would mean that its tail remains in place.)
Your snake is currently in a fairly nice position:
- it doesn't touch the walls of the game world.
- A strict majority of empty cells in the game world are currently clearly reachable.
Find out whether there is a way to turn the snake around in at most 80 moves. If yes, return any one such sequence of moves. If not, return "impossible". Use 'N', 'S', 'E', 'W' to denote moves up, down, right, and left.
Definition
- Class:
- ChristmasSnake
- Method:
- turnAround
- Parameters:
- String[]
- Returns:
- String
- Method signature:
- String turnAround(String[] game)
- (be sure your method is public)
Notes
- There is no fruit anywhere in this problem. Hence, the snake never grows, it just moves.
- A snake is turned around when it occupies the same sequence of squares but in the opposite direction. Note that it isn't sufficient to occupy the same set of squares, the exact order in which the snake passes through them matters.
Constraints
- game will contain 8 elements.
- Each element of game will contain 8 characters.
- For some N (between 1 and 26, inclusive) game will contain each of the first N lowercase English letters exactly once.
- All other characters in game will be periods ('.').
- The letters in game will form a valid snake with the given properties.
Examples
{"........", "....hg..", "..ab.f..", "...cde..", "........", "........", "........", "........"}
Returns: "WSSSSENNNNESEENNW"
The sample snake from the problem statement. The first move of the sample solution corresponds to the move illustrated in the example above. After the next five moves the snake looks as follows: ........ ........ .fgh.... .e...... .d...... .c...... .ba..... ........
{"........", "........", "..a.....", "........", "........", "........", "........", "........"}
Returns: "WSNNSE"
Easiest game ever. Doing nothing was also a valid solution, but we do not have to minimize the length of the solution.
{"........", ".y.ghij.", ".x.fa.k.", ".w.eb.l.", ".v.dc.m.", ".u....n.", ".tsrqpo.", "........"};
Returns: "ESSSWWWNNNNNEEEEESSSSSSSWWWWWWWNNNNNNNEESSSSSEEENNNWSSWNNNEEESSSSSWWWWWNNNNN"
{"........", "..opqtu.", "..n.rsv.", "..m...w.", ".klab.x.", ".jgfc.y.", ".ihed.z.", "........"}
Returns: "NEESSSSWWWWWNNNNNNNEEEEEEESSSSSSSWWNNNNWWSESSWNWSWNNENNNEESENESSSSS"
{"........", ".abijkl.", ".dchyzm.", ".efgxwn.", "...tuvo.", "...srqp.", "........", "........"}
Returns: "NEEEEEESSSSSSSWWWWWWWNNNNNNNESESWSEENNEEESSSSWWWNEENWNE"
{"........", "........", "........", ".abcdef.", "........", "........", "........", "........"}
Returns: "WNNNEEEEEEESSSSSSSWWWWWWWNNNNEEEEEE"
{"........", ".tsrqpo.", ".a....n.", ".b....m.", ".c....l.", ".d....k.", ".efghij.", "........"}
Returns: "WNNEEEEEEESSSSSSSWWWWWWWNNNNNESSSSEEEEENNNNNWWWWW"
{"........", ".....qp.", "....sro.", ".abctmn.", "..edkl..", "..f.j...", "..ghi...", "........"}
Returns: "WNNNEEEEEEESSSSSSSWWWWWWWNNNNEEESWSSEENNENENNWSWS"
{"........", "........", "........", "........", "....ba..", "....cfg.", "....deh.", "........"}
Returns: "EESSSWWWWWWWNNNNNNNEEEEEEESSSSWWWSSENES"
{"........", ".ba.....", ".czwvu..", ".dyx.ts.", ".e.kl.r.", ".fijmnq.", ".gh..op.", "........"}
Returns: "NEEEEESSSSSSSWWWWWWWNNNNNNNEESWSSSSSENENESESENNNWNWWSWN"
{"........", ".nmlkhg.", ".op.jif.", ".rq...e.", ".sz...d.", ".tyx..c.", ".uvw.ab.", "........"}
Returns: "SWWWWWNNNNNNNEEEEEEESSSSSSSWWNENNNNNWSWNWWWSESWSSSEENWN"
{"........", ".....ef.", ".....da.", ".....cb.", "........", "........", "........", "........"}
Returns: "ESSSSSWWWWWWWNNNNNNNEEEEEEESSWSWNNE"
{"........", "..opcba.", "..nqd...", ".lmre...", ".ktsf...", ".jihg...", "........", "........"}
Returns: "NESSSSSSSWWWWWWWNNNNNNNEEEEEESWWSSSSWWWNNENNESSSW"
{"........", "..ed....", ".gfcb...", ".hi.a...", "..jk....", ".tulmn..", ".srqpo..", "........"}
Returns: "EEESSSSWWWWWWWNNNNNNNEEEEEEESSSWWWNWNWSWSESESEESWWWWNE"
{"........", "...efkj.", "...dghi.", "...cb...", "....a...", "........", "........", "........"}
Returns: "EEESSSWWWWWWWNNNNNNNEEEEEEESSSSWWWNWNNESEENW"
{"........", ".stab...", ".rudc...", ".qfe....", ".pgh....", ".o.ij...", ".nmlk...", "........"}
Returns: "NEEEESSSSSSSWWWWWWWNNNNNNNEEESESWSWSESESWWWNNNNNES"
{"........", ".ihgfab.", ".jk.edc.", "..lqrsv.", "..mp.tu.", "..no....", "........", "........"}
Returns: "NEESSSSSSSWWWWWWWNNNNNNNEEEEESESWWNWWWSESSSENNEESEN"
{"........", ".....lm.", ".....kn.", ".....jo.", ".a.efip.", ".bcdghq.", ".wvutsr.", "........"}
Returns: "WNNNNEEEEEEESSSSSSSWWWWWWWNNNESEENESENNNNESSSSSWWWWW"
{"........", ".ut..ab.", ".vs...c.", ".wr...d.", ".xq..fe.", ".ypmlgh.", ".zonkji.", "........"}
Returns: "NEESSSSSSSWWWWWWWNNNNNNNEEEEESESSSWSESWWNWSWNNNNNWSSSSS"
{"........", "..hgf...", "..i.e...", ".kj.dc..", ".lmnob..", ".uvqpa..", ".tsr....", "........"}
Returns: "EESSWWWWWWWNNNNNNNEEEEEEESSSSSWWNNWNNWWSSWSEEESWSWWNE"
{"........", ".mnop...", ".lsrq...", ".ktuvw..", ".jedcx..", ".ifaby..", ".hg..z..", "........"}
Returns: "SSWWWNNNNNNNEEEEEEESSSSSSSWWWWNNENWWSSWNNNNNEEESWWSEEESSS"
{"........", "...wvsr.", ".zyxutq.", "..lmnop.", ".jk..ba.", ".ihg.c..", "...fed..", "........"}
Returns: "ESSSWWWWWWWNNNNNNNEEEEEEESSSSWWSSWWNWWNENEEEENNWSWNWSWW"
{"........", ".fghijk.", ".edcbal.", "......m.", ".wxyz.n.", ".v....o.", ".utsrqp.", "........"}
Returns: "SWWWWWNNNEEEEEEESSSSSSSWWWWWWWNNNNEEEEENWWWWNEEEEESSSSSWWWWWNNEEE"
{"........", ".hijklm.", ".gfcban.", "..ed..o.", "......p.", ".xwvutq.", ".yz..sr.", "........"}
Returns: "SSWWWWWNNNNEEEEEEESSSSSSSWWWWWWWNNNEEEEENNWWSWNWNEEEEESSSSSWNWWWWSE"
{"........", ".tuvwxy.", ".s......", ".r.defg.", ".q.cbah.", ".p....i.", ".onmlkj.", "........" }
Returns: "SWWWNNNEEEEESSSSSWWWWWWWNNNNNNNEEEEEEESSWWWWWSSSEEENWWNEEESSSWWWWWNNNNNEEEEE"
{"........", "....z...", ".ji.yxw.", ".kh...v.", ".lg.abu.", ".mfedct.", ".nopqrs.", "........" }
Returns: "WNNNNEEEESSSSSSSWWWWWWWNNNNNNNEEESSSSEESWWWNNNWSSSSEEEEENNNNWWN"
{"........", "........", ".dcba...", ".efghij.", ".ponmlk.", ".qrstuv.", "...zyxw.", "........" }
Returns: "NNEEESSSSSSSWWWWWWWNNNNNNNEEEESSWWWSEEEEESWWWWWSEEEEESWWW"
{"........", "........", "..efghi.", "..d...j.", "..cba.k.", "......l.", ".rqponm.", "........" }
Returns: "SWWWWNNNNNEEEEEEESSSSSSSWWWWWWWNNEEEENWWNNEEEESSSSWWWWW"
{"........", "........", "..efgh..", "..da.i..", "..cb.j..", ".....k..", "........", "........" }
Returns: "ESSSSWWWWNNNNNNNEEEEEEESSSSSSSWWWNNNNWSWNNEEESSS"
{"........", ".lkjihg.", ".m....f.", ".n....e.", ".o....d.", ".p....c.", ".qrs.ab.", "........" }
Returns: "SWWWWWNNNNNNNEEEEEEESSSSSSSWWNENNNNNWWWWWSSSSSEE"
{"........", ".efgh...", ".da.i...", ".cb.j...", "........", "........", "........", "........" }
Returns: "ESSWWWNNNNEEEEEEESSSSSSSWWWWWWWNNNEEENNWSWNNEEESS"