TopCoder:SRM233:SmartWordToy

This entry is about SmartWordToy problem from the Single Round Match 233 of TopCoder Division 1 and it is a 500 point problem:

Have you visited the TopCoder Algorithm tutorials page? You must have seen the mention of BFS (Breadth First Search) there and probably started to try the first problem listed there: SmartWordToy. I started too.

It seemed an interesting problem: there are 4 letter blocks; each block contains 2 buttons; left makes the letter go the previous letter in the sequence; right button takes the letter one step forward; given a start, end and a set of disallowed combinations, what is the minimum number of button presses required to reach the end?

The sequence of letters are cyclic which means that if you are seeing 'a' and press the left button, you will see 'z'. Also, if you are at 'z' and press the right button, you will see 'a'. Every time a button is pressed, the total score adds up until the end is reached.

The first test case in the problem being:
start = "aaaa"
end = "zzzz"
forbidden = { "aaaz", "aaza", "azaa", "zaaa", "azzz", "zazz", "zzaz", "zzza"}

v0.1:
I created a graph that would generate 8 new strings (or state) from a given string (state). For instance:
aaaa = zaaa baaa azaa abaa aaza aaba aaaz aaab
This is the set that results from pressing 1 button (left or right) on each block.
The graph generation took about 9 seconds to finish and if i had submitted this version, it would say 'Time Limit Exceeded'. We will come to this problem later.

After this, I added the start state to the queue and started the BFS. Pick the first state from the queue, check if it the goal state, if not, add it to the visited states, get the 8 possible states from this state, add it to the queue. If it is the goal state, end.

Problems with this approach:
1. Graph has been generated taking really long time.
2. How do we count the button presses?
3. On looking at the program trace, you see that the path taken does not go towards the goal. Even if the goal state was reached, it is certainly not the optimal path. This raises the question: how do we really use BFS?

v1.0
1. Addressed the early graph creation by adding the start state to the queue. Picking the item off the queue, checking if it is present in the graph, if not, add it to the graph along with the set of states that it generates.
2. Added a cost to each state by computing the distance from a given state to the goal state. This was interesting because there are 2 possible costs: forward cost (distance from a to z is 25) and reverse cost (distance from a to z is 1)
3. Now, I used Dijkstra's min path algorithm to pick the state with the least cost and then go towards the goal.

This solution passed all the sample test cases for the problem and some of my own. With confidence, I submitted the solution and got 469 out of 500. I then ran the system tests and saw that one test case fails:
String start = "aaaa";
String finish = "xxxx";
String[] forbidden = { "xz xz xz z", "xa xa xa b" };
Expected = 12, my output is 14. Need to find the root cause and fix it.

Learnings:
1. Just in time execution
2. Go towards the goal :-)