Boggle Solver

A facebook recruiter asked me to write the code for this particular problem. While I was able to suggest the algorithm correctly, I messed up my code. So here is the problem statement:

Given a 4×4 array with randomly selected letters in it and a dictionary of valid words, find which words can be made from this array by starting from any of the 16 letters and moving in any direction (the only constraint being that you cannot come to a node twice while making a word)

The first thing you should see here that this is clearly a Graph problem. The second noticeable aspect is that the maximum length of a word from such an array (with the constraint) can be 16 and the minimum length can be 1.

Since you have to look for all possible combinations starting from every point, Depth First Search comes to mind (why not Breadth First Search? Think about it). What you should do is apply DFS starting at each of the 16 nodes in the array. At every step, you add the newly formed word to a data structure meant to store strings (not allowing duplicates).

Once you have this data structure ready with you, all you need to do is search for each word in the dictionary that you have been provided.

Clear enough?

PS: Please code the DFS in the 4×4 array. It is not as simple as you assume it to be.

PPS: Does anyone have a better solution?

Shortest Path in Directed Acyclic Graphs

Problem Statement : Given a DAG, find the shortest path to a particular point from the given starting point.

This one is a famous problem that involves dealing with graphs. I assume everyone knows what a graph is. If you don’t, this is not the place for you to be. Please visit this wiki link for knowing more about Graphs. Let us get down to talking about DAGs (Directed Acyclic Graphs). Directed means that each edge has an arrow denoting that the edge can be traversed in only that particular direction. Acyclic means that the graph has no cycles, i.e., starting at one node, you can never end up at the same node.

Now that we are clear with what a DAG is, let us think about the problem. If we have the following DAG, what kind of algorithm would you use to solve this problem.

One thing you can do is apply an O(N*N) algorithm and find the shortest distance by calculating all the distances from each node to every other node. As you can guess, a better method exists. You should notice here that there is subproblem quality that exists here. If a particular node can be reached using two nodes, you can simply find the minimum of the values at the two nodes plus the cost for reaching to the node in question. So you are extending your previous solutions. Yes, Dynamic Programming.

The reason you are able to find such an optimal substructure here is because a DAG can be linearized (Topologically sorted). For example, the above DAG is linearized as follows,

Now if we want to find the minimum distance from start S to A. All we need to do is see the minimum distances to reach the nodes from which A can be reached. In this case, these nodes are S and C. Now the minimum of these minimum distances for previous nodes (till S=0, till C=2) added with the cost of reaching from these nodes (from S = 1, from C=4), is our answer.

So let me define the recursive relation for this case,

MinDist (S to A) = minimum ( MinDist(S to S) + Dist(S to A), MinDist(S to C) + Dist(C to A) )

Generalize this recurrence and you have a simple Dynamic Programming algorithm ready to solve the problem for you in linear time! Cheers!