FIND PATH

Create algorithm which is able to find path from start position to target position in any given maze based on those rules:

1. maze is rectangular 2d grid of maze elements
2. maze element is free '.' or blocked '#'
3. maze contains one start position marker 'S'
4. maze contains target position 'X' Input into algorithm is maze data as described above. Output from algorithm is series of steps from position 'S' to reach position 'X' or error in case that there is no direct path between them. Allowed steps are one position up 'u', down 'd', left 'l', right 'r'. Diagonal steps are not allowed.

Deliverables

It is mandatory that implementation of this task is done in Java. Optionally, extra points are achieved if implementation:

• clean architecture, layer separation and API design
• is delivered as maven or gradle project, when is loaded into IDE (Eclipse or Intellij Idea).
• unit tests are implemented to test partial functionality as well as whole solution.
• is delivered as zipped git repository with clean history of commits.
• multi-threaded implementation is used
• shortest possible path is calculated
• performance tests are provided
• runs in java 9 or 10

Examples

input: .................................... ..S...#......................#...... ......#......................#...... .............................#...... .................................... .................................... ..............#..................... ............#....................... ..........#......................... .................................... .....................#..........#... .....................#....X.....#... .....................#..........#... .................................... output: d,d,d,d,d,d,d,d,d,d,d,d,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,u,u,u