Decode the Coding Interview in C++: Real-World Examples/

...

/

Feature #3: Power Up the Station

Feature #3: Power Up the Station

Implementing the "Power Up the Station" feature for our "Cellular Operator" project.

We'll cover the following...

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 you 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. You want to power up the system in the minimum number of dial turns by avoiding the dead states.

Solution

There are 10,000 digits starting from 0000 to 9999. We have to reach a target number in a minimum number of dial turns. We can consider the 10,000 digits to be nodes in a graph. If two nodes differ in one digit (wrapping around, so 0 and 9 also differ by 1) and both nodes are not dead states, there will be an edge between them. We can use BFS here to find the shortest path from the starting node 0000 to the target node.

We implement the BFS using a queue and a visited set. The main part will be generating the new nodes from the current one. Each digit on the dial can be moved forward or backward, so eight new states can be generated from a single state. We’ll keep adding the new states into the queue if they have not already been visited or explored. The new states should only be generated from nodes that are not part of the dead states.

The eight states will be generated by moving each of the four digits forward and backward once. Usually, we can simply subtract or add 1 to each number to get a new one, but the wrapping around between 0 and 9 is allowed. Therefore, we need to do something else.

We can explicitly check for the condition: if we are subtracting from 0, 9 should be returned. Similarly, if we are adding to 9, 0 should be returned.

Let’s look at the code for the solution:

std::vector<std::string> neighbors(std::string& str) {
    std::vector<std::string> res;
    for (int i = 0; i < str.length(); i++) {
        // Calculate the new state by moving the current number in 
        // opposite direction
        res.push_back(str.substr(0, i) + std::to_string(str[i] == '0' ? 9 :  str[i] - '0' - 1) + str.substr(i+1));
        
        // Calculate the new state by moving the current number in 
        // forward direction
        res.push_back(str.substr(0, i) + std::to_string(str[i] == '9' ? 0 :  str[i] - '0' + 1) + str.substr(i+1));
    }
    return res;
}
int powerUp(std::vector<std::string>& deadStates, std::string& target) {
    std::queue<std::string> q;
    std::unordered_set<std::string> visited(deadStates.begin(), deadStates.end());
    int depth = -1;
    q.push("0000");
    while(!q.empty()) {
        depth++;
        int size = q.size();
        for(int i = 0; i < size; i++) {
            std::string node = q.front();
            q.pop();
            if(node == target)
                return depth;
            if(visited.find(node) != visited.end())
                continue;
            visited.insert(node);
            auto neighbor = neighbors(node);
            for(auto n : neighbor){
                q.push(n);
            }
        }
    }
    return -1;
}
int main() {
    // Driver code
    std::vector<std::string> deadStates = {"0201","0101","0102","1212","2002"};
    std::string target = "0202";
    std::cout << "The system will power up in " + std::to_string(powerUp(deadStates, target)) + " dial turns\n";
    
}
Power up the station

Complexity measures

Time complexity Space complexity
O(n2∗an+d)
...