Feature #3: Power Up the Station

Description

AT&T just acquired a cellular company in a small town that owns four base stations. The company they acquired owned vintage equipment with dials that must be rotated clockwise or counterclockwise by hand to power up the base stations. There’s one dial for each of the base stations. Each dial has numbers from 0 to 9 and does not stop at either extreme; this means we can rotate clockwise at 9 to go back to 0 or counterclockwise at 0 to go to 9.

Each position on a dial represents a particular state for the corresponding base station. To power up the base stations, the dials must be taken from state 0000 to a target state, say abcd, where a, b, c, and d are digits between 0 and 9. The constraints are that only one dial may be turned (clockwise or counterclockwise) one position at a time and certain dead states are prohibited and must be avoided at all costs. The system will get stuck and fail if we land in a dead state.

We’ll be provided with a list of dead states that we need to avoid and a target state that we need to reach. We want to power up the system in the minimum number of dial turns by avoiding the dead states.