package com.tr.maze;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * Applies the DFS algirithm to solve the Maze. Uses stack data structure to keep a track of visited
 * blocks. Traverses the aisles recursively until reaches finish/ doesn't find a path to finish
 * 
 * @author Narain Mittal
 * 
 */
public class MazeSolverDfs implements IMazeSolver {

	private Maze maze;

	private final Deque<Block> stack = new ArrayDeque<>();

	private final Set<Block> visitedBlocks = new HashSet<>();

	private final Set<Block> solutionBlocks = new HashSet<>();

	@Override
	public boolean solve(Maze maze) {
		this.maze = maze;
		this.visitedBlocks.add(maze.getStart());
		this.solutionBlocks.add(maze.getStart());
		this.stack.push(maze.getStart());
		return solveDfs();
	}

	@Override
	public Block getNextTraversableAisle(Block block) {
		int x = block.getX();
		int y = block.getY();
		Block next = null;
		if (isValidAisle(x + 1, y)) {
			next = maze.getBlock(x + 1, y);
		}
		else if (isValidAisle(x, y + 1)) {
			next = maze.getBlock(x, y + 1);
		}
		else if (isValidAisle(x, y - 1)) {
			next = maze.getBlock(x, y - 1);
		}
		else if (isValidAisle(x - 1, y)) {
			next = maze.getBlock(x - 1, y);
		}
		return next;
	}

	/**
	 * Checks if the block at designated indices is an Aisle which is not visited yet.
	 * 
	 * @param x
	 * @param y
	 * @return true if valid, false otherwise
	 */
	private boolean isValidAisle(int x, int y) {
		try {
			Block b = maze.getBlock(x, y);
			return (b instanceof Aisle) && !isBlockVisited(b);
		} catch (ArrayIndexOutOfBoundsException e) {
			return false;
		}

	}

	private boolean solveDfs() {
		Block block = stack.peekFirst();
		if (block == null) {
			// stack empty and not reached the finish yet; no solution
			return false;
		} else if (block.equals(maze.getEnd())) {
			// reached finish, exit the program
			return true;
		} else {
			Block next = getNextTraversableAisle(block);
			if (next == null) {
				// Dead end, backtrack and chose alternate path
				Block discard = stack.pop();
				this.solutionBlocks.remove(discard);
			} else {
				// Traverse next block
				this.solutionBlocks.add(next);
				this.visitedBlocks.add(next);
				stack.push(next);
			}
		}
		return solveDfs();
	}

	@Override
	public boolean isBlockInSolution(Block block) {
		return solutionBlocks.contains(block);
	}

	@Override
	public boolean isBlockVisited(Block block) {
		return visitedBlocks.contains(block);
	}

}

@@ -94,16 +94,43 @@
 ashSet;%0A
+import java.util.Optional;%0A
 import j
@@ -1714,21 +1714,31 @@
 s() %7B%0A%09%09
+Optional%3C
 Block
+%3E
  block =
@@ -1738,16 +1738,36 @@
 block = 
+Optional.ofNullable(
 stack.pe
@@ -1775,24 +1775,25 @@
 kFirst()
+)
 ;%0A%09%09if (
 block ==
@@ -1788,21 +1788,26 @@
 if (
+!
 block
- == null
+.isPresent()
 ) %7B%0A
@@ -1904,16 +1904,22 @@
  (block.
+get().
 equals(m
@@ -2004,29 +2004,39 @@
 se %7B%0A%09%09%09
+Optional%3C
 Block
+%3E
  next = 
 getNextT
@@ -2027,16 +2027,32 @@
  next = 
+block.map(this::
 getNextT
@@ -2066,22 +2066,16 @@
 bleAisle
-(block
 );%0A%09%09%09if
@@ -2080,20 +2080,25 @@
 if (
+!
 next
- == null
+.isPresent()
 ) %7B%0A
@@ -2157,119 +2157,279 @@
 %09%09%09%09
-Block discard = stack.pop();%0A%09%09%09%09this.solutionBlocks.remove(discard);%0A%09%09%09%7D else %7B%0A%09%09%09%09// T
+backTrack();%0A%09%09%09%7D else %7B%0A%09%09%09%09// Traverse next block%0A%09%09%09%09traverseNextBlock(next.get());%0A%09%09%09%7D%0A%09%09%7D%0A%09%09return solveDfs();%0A%09%7D%0A%0A%09private Optional backTrack()%7B%0A%09%09this.solutionBlocks.remove(stack.pop());%0A%09%09return Optional.empty();%0A%09%7D%0A%0A%09private void t
 raverse
- next block%0A%09%09
+NextBlock(Block next)%7B%0A
 %09%09th
@@ -2459,18 +2459,16 @@
 ext);%0A%09%09
-%09%09
 this.vis
@@ -2489,18 +2489,16 @@
 (next);%0A
-%09%09
 %09%09stack.
@@ -2513,38 +2513,8 @@
 t);%0A
-%09%09%09%7D%0A%09%09%7D%0A%09%09return solveDfs();%0A
 %09%7D%0A%0A

Update logic with Java Optional