Colonizing Zombies

Introduction

 

In this article, you will learn about the Amazon interview question, 'How to find the turns needed for the zombies to colonize a 2-D matrix.'

 

Problem Statement

 

A matrix (2D array) has cells that are filled with one of three possible values, 0 implying the cell is empty, 1 implying the cell has a human in it and lastly, 2 implying the cell has a zombie in it. Every turn, the zombies infect any humans adjacent to them that might be up, down, left or right, and those humans become zombies. Those new zombies are then able to infect any humans next to then, and the cycle continues each turn. ​Given a matrix, to return the number of turns it takes until there are no humans left. And if any human survives, then return -1.

static void Main(string[] args)
{
    var colonize = new ColonizingZombies();
    var turnsTaken = colonize.FetchTurns(new int[,] {
        { 2, 1, 1 },
        { 0, 1, 1 },
        { 1, 0, 1 }
    });
    // turnsTaken is -1
    turnsTaken = colonize.FetchTurns(new int[,] {
        { 0, 2 }
    });
    // turnsTaken is 0
    turnsTaken = colonize.FetchTurns(new int[,] {
        { 2, 1, 1 },
        { 1, 1, 0 },
        { 0, 1, 1 }
    });
    // turnsTaken is 4
}

Solution

 

Our approach towards the problem will be using multiple BFS (Breadth-First Search). We will update the matrix each turn by infecting humans next to any zombies. ​However, there are two things we need to watch out for, we must infect humans on the correct turns and we don't want to traverse empty cells unnecessarily. With this in mind, we'll use a list to hold each zombie, and for each zombie in the list, we'll process it by allowing it to infect any humans adjacent to it, meaning pushing that newly created zombie onto the queue to be processed later. However, the part where our code is going to become easier to read is that each Zombie in our list will store their matrix position [x-cordtinate, y-coordinate] and the turn it got infected. To do this, we'll have a special class to store this extra info. Here is the algorithm for the approach:

1. Create a class named Zombie that stores integers Abscissa (x-coordinate), Ordinate (y-coordinate), and TurnInfected, and a list that holds Zombies.
2. Traverse the matrix and if we see a zombie, add it to the queue (where TurnInfected = 0).
3. Iterate over all the zombies in the list, update the current turn to be this zombie's TurnInfected and then infect any humans next to this zombie and add those new zombies to the list.
4. Traverse the matrix to check if any humans survived.
5. If any humans survived, return -1 or else, return the turns.

The C# pseudocode for this Amazon interview question is given below,

class ColonizingZombies
{
    public ColonizingZombies()
    {
        // create a list that holds zombies.
        Zombies = new List<Zombie>();
    }
    int[,] Grid;
    List<Zombie> Zombies;
    class Zombie
    {
        public int Abscissa;
        public int Ordinate;
        public int TurnInfected;
    }
    public int FetchTurns(int[,] grid)
    {
        Grid = grid;
        int turn = 0;
        // iterate the grid
        for (int i = 0; i < Grid.GetLength(0); i++)
        {
            for (int j = 0; j < Grid.GetLength(1); j++)
            {
                // if this cell has a zombie
                if (Grid[i, j] == 2)
                {
                    // infect its neighbors
                    AddZombieToQueue(i, j, 0);
                }
            }
        }

        // process each zombie in the queue by infecting any humans adjacent to it.
        foreach (var zombie in Zombies)
        {
            // update turn for last zombie
            turn = zombie.TurnInfected;

            // infecting any neighbors
            InfectNeighbors(zombie.Abscissa, zombie.Ordinate, zombie.TurnInfected + 1);
        }

        // check for any human survived
        bool humanSurvived = false;
        for (int i = 0; i < Grid.GetLength(0); i++)
        {
            for (int j = 0; j < Grid.GetLength(1); j++)
            {
                if (Grid[i, j] == 1)
                {
                    humanSurvived = true;
                    break;
                }
            }
            if (humanSurvived)
                break;
        }

        // if a human survived then return -1
        if (humanSurvived)
            return -1;

        // return the minute the last human got infected
        return turn;
    }
    void AddZombieToQueue(int x, int y, int turnInfected)
    {
        Grid[x, y] = 2;

        // Add this zombie
        Zombies.Add(new Zombie {
            Abscissa = x,
            Ordinate = y,
            TurnInfected = turnInfected
        });
    }

    void InfectNeighbors(int x, int y, int turnInfected)
    {
        // if found human, convert it to a zombie and add it to the queue.
        // for up
        if (x - 1 >= 0 && Grid[x - 1, y] == 1)
            AddZombieToQueue(x - 1, y, turnInfected);

        // for down
        if (x + 1 < Grid.GetLength(0) && Grid[x + 1, y] == 1)
            AddZombieToQueue(x + 1, y, turnInfected);

        // for left
        if (y - 1 >= 0 && Grid[x, y - 1] == 1)
            AddZombieToQueue(x, y - 1, turnInfected);

        // for right
        if (y + 1 < Grid.GetLength(1) && Grid[x, y + 1] == 1)
            AddZombieToQueue(x, y + 1, turnInfected);
    }
}