TCHS-6-900

Problem Statement

We are given a maze which is a cube of NxNxN cells. We start at (1,1,1) and we move to (N,N,N), in each move visiting one of the three adjacents cells in the positive x, y or z directions. Each cell of the maze contains either a '(', ')' or '.'. A path is the sequence of cells visited during the journey. We intend to find the number of such paths that produce a valid parenthesized expression.

Periods can occur freely in an expression, and must be ignored while checking if an expression is properly paranthesized or not. A paranthesized expression is said to be valid only if it adheres to the following grammar (quotes for clarity): <expr> ::= empty-string | "("<expr>")" | <expr>"." | <expr><expr>

e.g., "(())", "....", ".()." and "().(.)" are valid parathesized expressions.
The maze is given in a String[] which, when concantenated, represents the cube encoded in the following manner. The characters of maze correspond to the following cube coordinates, in order: (1,1,1), (1,1,2), ..., (1,1,N), (1,2,1), (1,2,2), ..., (1,N,N), (2,1,1), ..., (N,N,N)

Given the String[] maze return an int representing the number of possible paths forming valid parenthesized expressions. If there are more than 1,000,000,000 paths, return -1 instead.

Definition

Class:	BracketMaze
Method:	properPaths
Parameters:	String[], int
Returns:	int
Method signature:	int properPaths(String[] maze, int N)
(be sure your method is public)

Constraints

-

maze will contain between 1 and 50 elements, inclusive.

-

Each element of maze will contain between 1 and 50 characters, inclusive.

-

The maze when concatenated will contain exactly N^3 characters.

-

Each character in maze will be '(', ')', or '.'.

-

N will be between 1 and 13, inclusive.

Examples

0)

{"()()()()"}

2

Returns: 2

There are two paths in this 2x2x2 cube. From the 3 possible moves in the beginning, you cannot go right directly which completes a "()" but all it's neighbours are ')', hence lead to an invalid expression. The other two possible moves lead to unique valid paths.

1)

{")()()()("}

2

Returns: 0

2)

{ "..........................." }

3

Returns: 90

3)

{"..(....)"}

2

Returns: 2

4)

{ "(.........................)"}

3

Returns: 90

import java.util.Arrays;

public class BracketMaze {

	String s = "";
	int n;
	long[][][][] memo;

	long dfs(int x, int y, int z, int p) {
		char c = s.charAt(x * n * n + y * n + z);
		if (x==y && y==z && z==n-1)
			return (p==0 && c=='.' || p==1 && c==')') ? 1 : 0;
		if (memo[x][y][z][p] != -1)
			return memo[x][y][z][p];
		long ret = 0;
		int p1 = p;
		if (c == '(')
			p1++;
		else if (c == ')')
			p1--;
		if (p1 >= 0) {
			if (x < n - 1)
				ret += dfs(x + 1, y, z, p1);
			if (y < n - 1)
				ret += dfs(x, y + 1, z, p1);
			if (z < n - 1)
				ret += dfs(x, y, z + 1, p1);
		}
		return memo[x][y][z][p] = ret;
	}

	public int properPaths(String[] maze, int N) {
		for (int i = 0; i < maze.length; i++)
			s += maze[i];
		n = N;
		memo = new long[N][N][N][3*N];
		for (long[][][] mmm : memo)
			for (long[][] mm : mmm)
				for (long[] m : mm)
					Arrays.fill(m, -1);
		long count = dfs(0, 0, 0, 0);
		return (count > 1e9) ? -1 : (int) count;
	}

}