Alphys, the Underground's Royal Scientist, has finished a prototype for a new puzzle. However, she can't seem to find anyone willing to test it.
The rules of her puzzle are as follows:
The goal is to get to the right side, starting from the centermost tile on the left side. For puzzles with even-numbered heights, start on the lower of the two center tiles. (Examples: In a zero-indexed 4x4 array, the starting position would be [2,0] - row 2, column 0. In a zero-indexed 5x5 array the starting position would be [2,0] - row 2, column 0.)
Each colored tile has its own "sadistic" function:
- Pink and green tiles (represented as "P" and "G") do nothing
- Red and yellow tiles ("R", "Y") are impassable.
- Orange tiles ("O") make the player smell like oranges
- Purple tiles ("U") force the player to the next tile in the direction they are facing and make them smell like lemons
- Blue tiles ("B") are passable as long as the player does not smell like oranges.
To clarify the flavor mechanic, a player's smell will persist indefinitely or until overridden by a different-smelling tile, i.e. if a player steps on an orange tile they will smell like oranges until they step on a purple tile.
Additionally, a yellow tile placed vertically or horizontally adjacent to a blue tile will cause the blue tile to become impassable as well.
Your task is to write a program or function that accepts a 2-dimensional character array (or 1D string array, or some other valid format) representing the puzzle's layout as input and outputs both the original puzzle and the solved puzzle, with asterisks or some other character showing the correct path. Assume that the given puzzle is solveable.
Use this puzzle as an example:
BGYBG PGPBG PUBPB OUGYB PPOPP
Your program would output:
BGYBG PGPBG PUBPB OUGYB PPOPP BGYBG PGPBG ***** OUGYB PPOPP
Any puzzle used must be generated using this.
Standard code golf rules apply. Best answers will be the shortest for each language. Answers must contain the language, number of bytes, and three test cases. The first two can be any layout you choose, but the third must be:
RRRR RPPR PUOR RPBP