AMCAT Automata Question Bank | Set 1 – Practice & Solutions

In this article, we explore two essential problem-solving techniques—Lattice Multiplication for fast calculations and a Maze Pathfinding Algorithm to solve grid-based puzzles. These techniques are widely used in competitive programming, interviews, and real-world applications.

Problem 1: Cell Competition Simulation

Understanding the Problem Statement

A colony of 8 cells is arranged in a straight line. Every day, each cell competes with its neighboring cells. The rules of competition are:

• A cell becomes inactive (0) if both of its adjacent cells are either active (1) or inactive (0).
• Otherwise, it becomes active (1) the next day.
• The two boundary cells have only one adjacent neighbor, and the other is considered always inactive.

Function Definition

Write a function cellCompete(int* cells, int days) that takes:

1. An 8-element array of integers representing the current state of the cells.
2. An integer representing the number of days to simulate.
3. Returns the final state of the cells after the given number of days.

Test Cases

Example 1:

Input: [1,0,0,0,0,1,0,0], 1
Expected Output: [0,1,0,0,1,0,1,0]

Example 2:

Input: [1,1,1,0,1,1,1,1], 2
Expected Output: [0,0,0,0,0,1,1,0]

Optimized Solution in C++

#include <iostream>
using namespace std;

void cellCompete(int cells[], int days) {
    int temp[8];

    while (days--) {
        for (int i = 0; i < 8; i++) {
            int left = (i == 0) ? 0 : cells[i - 1]; 
            int right = (i == 7) ? 0 : cells[i + 1];
            temp[i] = (left == right) ? 0 : 1;
        }
        for (int i = 0; i < 8; i++) {
            cells[i] = temp[i];
        }
    }
}

int main() {
    int cells[] = {1, 0, 0, 0, 0, 1, 0, 0};
    int days = 1;

    cellCompete(cells, days);

    cout << "Final state: ";
    for (int i = 0; i < 8; i++) {
        cout << cells[i] << " ";
    }

    return 0;
}

Key Takeaways

• Uses an auxiliary array to store new values while iterating.
• Handles boundary conditions effectively.
• Runs in O(n × days) time complexity, where n = 8.

Problem 2: Maze Pathfinding Algorithm (Mooshak the Mouse)

Understanding the Problem Statement

Mooshak, the mouse, needs to find a path to a huge chunk of cheese in a maze represented as a 2D grid.

• 0 represents walls (Mooshak cannot pass).
• 1 represents valid paths.
• 9 represents the cheese (goal).
• Mooshak starts at (0,0) and can only move up, down, left, or right.

Function Definition

Write a function isPath(int** grid, int m, int n) that returns:

• 1 if Mooshak can reach the cheese.
• 0 if there is no valid path.

Test Cases

Example 1:

Input:

[[1, 1, 1],
 [9, 1, 1],
 [0, 1, 0]]

Output: 1
Explanation: Mooshak can move (0,0) → (1,0) or (0,0) → (0,1) → (1,1) → (1,0).

Example 2:

Input:

luaCopyEdit[[0, 0, 0],
 [9, 1, 1],
 [0, 1, 1]]

Output: 0
Explanation: Mooshak cannot move as (0,0) is blocked by walls.

Optimized Solution in C++ (Using DFS)

#include <iostream>
using namespace std;

#define N 8

bool isPathHelper(int maze[N][N], int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= N || maze[x][y] == 0) {
        return false;
    }

    if (maze[x][y] == 9) {
        return true;
    }

    maze[x][y] = 3; // Mark as visited

    if (isPathHelper(maze, x - 1, y)) return true; // Move up
    if (isPathHelper(maze, x, y + 1)) return true; // Move right
    if (isPathHelper(maze, x + 1, y)) return true; // Move down
    if (isPathHelper(maze, x, y - 1)) return true; // Move left

    maze[x][y] = 1; // Unmark if path not found
    return false;
}

bool isPath(int maze[N][N]) {
    return isPathHelper(maze, 0, 0);
}

int main() {
    int maze[N][N] = {
        {1, 0, 1, 1, 1, 0, 0, 1},
        {1, 0, 0, 0, 1, 1, 1, 1},
        {1, 0, 0, 0, 0, 0, 0, 0},
        {1, 0, 1, 0, 9, 0, 1, 1},
        {1, 1, 1, 0, 1, 0, 0, 1},
        {1, 0, 1, 0, 1, 1, 0, 1},
        {1, 0, 0, 0, 0, 1, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1}
    };

    cout << "Is path available: " << isPath(maze) << endl;
    return 0;
}

Key Takeaways

• Uses Depth-First Search (DFS) to explore paths recursively.
• Marks visited nodes to prevent infinite loops.
• Time complexity: O(N^2), where N is the size of the grid.

Conclusion

Both Cell Competition Simulation and Maze Pathfinding Algorithm are powerful problem-solving techniques commonly used in technical interviews and competitive programming.