SmartWordToy – TopCoder

SmartWordToy, TopCoder SRM 233 Div 1

This problem is not hard to understand. You can use BFS for this problem.
Let's briefly talk about what BFS is.
It is traversing technique in Graph theory. It traverse by breadth first, i.e., start with one node, and traverse all its immediate neighbor nodes, and so on.

In this tree, BFS will traverse 1-2-3-4-5-6-7.

Let's look at more complex example in topcoder.

Problem Statement
   
The toy company "I Can't Believe It Works!" has hired you to help develop educational toys. The current project is a word toy that displays four letters at all times. Below each letter are two buttons that cause the letter above to change to the previous or next letter in alphabetical order. So, with one click of a button the letter 'c' can be changed to a 'b' or a 'd'. The alphabet is circular, so for example an 'a' can become a 'z' or a 'b' with one click.  In order to test the toy, you would like to know if a word can be reached from some starting word, given one or more constraints. A constraint defines a set of forbidden words that can never be displayed by the toy. Each constraint is formatted like "X X X X", where each X is a string of lowercase letters. A word is defined by a constraint if the ith letter of the word is contained in the ith X of the contraint. For example, the constraint "lf a tc e" defines the words "late", "fate", "lace" and "face".  You will be given a String start, a String finish, and a String[] forbid. Calculate and return the minimum number of button presses required for the toy to show the word finish if the toy was originally showing the word start. Remember, the toy must never show a forbidden word. If it is impossible for the toy to ever show the desired word, return -1.

The key is to use BFS, and create huge array to save whether the state is already visited.
Also, forbidden has to saved into array so that when you compare every state, it doesn't compare every forbidden list every time.

Here is the code I wrote. It passed all of test cases.

import java.util.LinkedList;

public class SmartWordToy {
public int minPresses(String start, String finish, String[] forbid) {
boolean[][][][] steps = new boolean[26][26][26][26];
boolean[][][][] forbidden = new boolean[26][26][26][26];
State st = new State(start.charAt(0),start.charAt(1),start.charAt(2),start.charAt(3),0);
State fi = new State(finish.charAt(0),finish.charAt(1),finish.charAt(2),finish.charAt(3),0);
LinkedList forb = new LinkedList();
for (int i=0;i    String[] sp = forbid[i].split(" ");
   char[] ch1 = sp[0].toCharArray();
   char[] ch2 = sp[1].toCharArray();
   char[] ch3 = sp[2].toCharArray();
   char[] ch4 = sp[3].toCharArray();
   for (int j=0;j for (int k=0;k for (int m=0;m for (int n=0;n    if (!forbidden[ch1[j]-'a'][ch2[k]-'a'][ch3[m]-'a'][ch4[n]-'a']) {
    forbidden[ch1[j]-'a'][ch2[k]-'a'][ch3[m]-'a'][ch4[n]-'a'] = true;
forb.add(new State(ch1[j],ch2[k],ch3[m],ch4[n],0));
}
}
}
}
}
}

LinkedList q = new LinkedList();
q.add(st);
steps[st.a-'a'][st.b-'a'][st.c-'a'][st.d-'a'] = true;
while (q.size() > 0) {
State state = q.removeFirst();
if (state.equal(fi))
return state.step;
addNeighbors(state,forbidden,q,steps);
}

return -1;
}

public void addNeighbors(State state, boolean[][][][] forbidden, LinkedList q, boolean[][][][] steps) {
char[] chars = new char[4];
State temp = new State(nextCh(state.a),state.b,state.c,state.d, state.step + 1);

if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(prevCh(state.a),state.b,state.c,state.d, state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,nextCh(state.b),state.c,state.d, state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,prevCh(state.b),state.c,state.d, state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,state.b,nextCh(state.c),state.d, state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,state.b,prevCh(state.c),state.d, state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,state.b,state.c,nextCh(state.d), state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,state.b,state.c,prevCh(state.d), state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
}

public boolean canAddtoNeighbor(State state, boolean[][][][] forbidden, boolean[][][][] steps) {
if (!steps[state.a-'a'][state.b-'a'][state.c-'a'][state.d-'a'] && !forbidden[state.a-'a'][state.b-'a'][state.c-'a'][state.d-'a']){
return true;
}
return false;
}

public char nextCh(char ch) {
   if (ch == 'z')
    return 'a';
return (char)(ch + 1);
}

public char prevCh(char ch) {
if (ch == 'a')
return 'z';
return (char)(ch - 1);
}

class State {
char a;
char b;
char c;
char d;
int step;
public State(char aa, char bb, char cc, char dd, int s) {
a = aa;
b = bb;
c = cc;
d = dd;
step = s;
}

public boolean equal(State s) {
if (a == s.a && b == s.b && c == s.c && d == s.d)
return true;
return false;
}

public void print() {
System.out.println("State:" + a + "," + b + "," + c + "," + d + ",step:" + step);
}
}
}