Dungeon Game

class CircularQueue {
public:
    CircularQueue(int size) {
        this->size = size;
        this->end = 0;
        this->data = vector<int>(size);
    }

    void insert(int element) {
        this->data[this->end] = element;
        this->end = (this->end + 1) % this->size;
    }

    int retrieve(int idx) { return this->data[idx % this->size]; }

private:
    vector<int> data;
    int end;
    int size;
};

class DungeonSolver {
public:
    int calculateMinimumHealth(vector<vector<int>>& dungeon) {
        int rows = dungeon.size();
        int cols = dungeon[0].size();
        CircularQueue healthQueue(cols);
        int infinite = numeric_limits<int>::max();

        auto calcMinHP = [&](int currVal, int prevRow, int prevCol) -> int {
            if (prevRow < 0 || prevCol < 0) return infinite;

            int index = cols * prevRow + prevCol;
            int nextVal = healthQueue.retrieve(index);
            return max(1, nextVal - currVal);
        };

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                int currVal = dungeon[rows - row - 1][cols - col - 1];
                int rightHP = calcMinHP(currVal, row, col - 1);
                int downHP = calcMinHP(currVal, row - 1, col);
                int nextHP = min(rightHP, downHP);

                int minHP;
                if (nextHP != infinite) {
                    minHP = nextHP;
                } else {
                    minHP = currVal >= 0 ? 1 : 1 - currVal;
                }

                healthQueue.insert(minHP);
            }
        }

        return healthQueue.retrieve(cols - 1);
    }
};

The provided C++ solution implements a dynamic programming approach to solve the "Dungeon Game" problem, which requires calculating the minimum initial health needed for a player to navigate through a dungeon represented by a grid of rooms, each with positive (health bonus) or negative (damage) values.

• Class Design:
  • CircularQueue: Manages a circular queue data structure to store health values dynamically. This class supports insertion and retrieval of elements in a circular manner to optimize space usage.
    • insert(int element): Adds a new health value to the queue and updates the end pointer.
    • retrieve(int idx): Retrieves the health value at a specified index, adjusted for circular indexing.
  • DungeonSolver:
    • calculateMinimumHealth(vector<vector<int>>& dungeon): Calculates the minimum health required to start in the dungeon so that the player can reach the princess (or the endpoint) alive.
• Dynamic Programming Calculation:
  • A helper lambda function calcMinHP calculates the minimum health required at a given cell, considering the health needed on the right and downward paths.
  • The health values are calculated in reverse (starting from the bottom-right corner of the grid and moving to the top-left), which allows the solver to determine the minimum health required at each step based on the decisions (moving right or down) that will follow.
  • To achieve efficient state management during the calculation, the algorithm uses a circular queue that stores the health requirement dynamically for the last processed row, thus optimizing memory usage and enabling direct access to required states.
• Result Retrieval:
  • After computing all states, the required initial health at the dungeon entrance (top-left corner) is obtained from the circular queue.

This approach ensures that the solution is both time-efficient, due to dynamic programming avoiding redundant calculations, and space-efficient, due to using a circular queue instead of a full 2D array to store intermediate results.

class CircularBuffer {
    protected int maxSize;
    protected int endIdx;
    public int[] buffer;
    
    public CircularBuffer(int size) {
        this.buffer = new int[size];
        this.endIdx = 0;
        this.maxSize = size;
    }

    public void insert(int element) {
        this.buffer[this.endIdx] = element;
        this.endIdx = (this.endIdx + 1) % this.maxSize;
    }

    public int retrieve(int idx) {
        return this.buffer[idx % this.maxSize];
    }
}

class Algorithm {
    int infinity = Integer.MAX_VALUE;
    CircularBuffer healthDP;
    int rowCount, columnCount;

    public int computeMinHealthRequired(int currentHealth, int newRow, int newCol) {
        if (newRow < 0 || newCol < 0) return infinity;

        int position = columnCount * newRow + newCol;
        int health = this.healthDP.retrieve(position);
        return Math.max(1, health - currentHealth);
    }

    public int minInitialHealth(int[][] dungeon) {
        this.rowCount = dungeon.length;
        this.columnCount = dungeon[0].length;
        this.healthDP = new CircularBuffer(this.columnCount);

        int cell, healthRight, healthBelow, requiredHealth, minimumHealth;
        for (int row = 0; row < this.rowCount; ++row) {
            for (int col = 0; col < this.columnCount; ++col) {
                cell = dungeon[rowCount - row - 1][columnCount - col - 1];

                healthRight = computeMinHealthRequired(cell, row, col - 1);
                healthBelow = computeMinHealthRequired(cell, row - 1, col);
                requiredHealth = Math.min(healthRight, healthBelow);

                if (requiredHealth != infinity) {
                    minimumHealth = requiredHealth;
                } else {
                    minimumHealth = cell >= 0 ? 1 : 1 - cell;
                }
                this.healthDP.insert(minimumHealth);
            }
        }

        return this.healthDP.retrieve(this.columnCount - 1);
    }
}

In the provided code for the "Dungeon Game," a Java solution calculates the minimum initial health required for a character to traverse through a dungeon represented as a 2D grid. This grid has cells containing positive values, which increase the character's health, or negative values, representing damage. The goal is to determine the least amount of health needed to navigate from the grid’s top-left to the bottom-right corner, ensuring the character's health never drops to zero or below at any point.

The solution utilizes a CircularBuffer class for efficient memory management by recycling space when calculating minimum health requirements at each cell. The buffer's size equals the number of columns in the dungeon grid. The buffer ensures constant time complexity for inserting and retrieving health values.

Key points of the solution:

• The minInitialHealth method calculates required health per cell in reverse order, from the bottom-right to the top-left. This approach allows for dynamic programming using only current state information.

• Two major health calculations are performed:

  • healthRight: Minimum health required if moving right from the current cell.
  • healthBelow: Minimum health required if moving downward from the current cell.

• To determine the overall health required to leave any cell, the algorithm uses the smaller of the two values above, accounting for immediate right and below paths. If neither path is available, it computes based on the cell's value alone, ensuring that the character always has at least 1 health.

• The algorithm employs a helper method computeMinHealthRequired that calculates the adjusted health requirements considering current cell value and pre-saved health states using modular arithmetic to retrieve correct entries from the buffer.

Through this methodical reversal and evaluation, the function finally retrieves and returns the computed minimum health from the buffer, which represents the necessary starting health for the top-left cell. This approach efficiently spreads out the computation across the dungeon map, ensuring only necessary data is stored and accessed in each step.

#define LIMIT_MAX 2147483647

typedef struct CircularQueue {
    int size;
    int lastIdx;
    int* data;
} CircularQueue;

CircularQueue* createCircularQueue(int size) {
    CircularQueue* queue = (CircularQueue*)malloc(sizeof(CircularQueue));
    queue->data = (int*)malloc(sizeof(int) * size);
    queue->lastIdx = 0;
    queue->size = size;
    return queue;
}

void enqueue(CircularQueue* queue, int element) {
    queue->data[queue->lastIdx] = element;
    queue->lastIdx = (queue->lastIdx + 1) % queue->size;
}

int getCircularQueueElement(CircularQueue* queue, int idx) {
    return queue->data[idx % queue->size];
}

int minimumHealth(int curr, int nextR, int nextC, int maxR, int maxC,
                 CircularQueue* queue) {
    if (nextR < 0 || nextC < 0) return LIMIT_MAX;

    int pos = maxC * nextR + nextC;
    int next = getCircularQueueElement(queue, pos);
    // Ensure the hero survives with at least 1 health point
    return (1 > next - curr) ? 1 : next - curr;
}

int calculateMinHealth(int** dungeon, int dungeonRows, int* dungeonCols) {
    int rows = dungeonRows;
    int cols = (*dungeonCols);
    CircularQueue* queue = createCircularQueue(cols);

    int cell, rightH, downH, nextH, minH;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            cell = dungeon[rows - i - 1][cols - j - 1];

            rightH = minimumHealth(cell, i, j - 1, rows, cols, queue);
            downH = minimumHealth(cell, i - 1, j, rows, cols, queue);
            nextH = (rightH < downH) ? rightH : downH;

            if (nextH != LIMIT_MAX) {
                minH = nextH;
            } else {
                minH = (cell >= 0) ? 1 : 1 - cell;
            }
            enqueue(queue, minH);
        }
    }

    // Get the last processed element as the dungeon entry point health requirement
    return getCircularQueueElement(queue, cols - 1);
}

In the provided C code, you tackle the "Dungeon Game" problem using a data structure and algorithm approach. The goal is to determine the minimum initial health required to navigate a grid representing a dungeon where positive integers represent health pickups and negative integers represent health damage.

Here's how the solution is structured:

• A circular queue is implemented using a struct CircularQueue which holds the queue data, its maximum size, and the last index filled. This helps manage the dynamic elements of the solution efficiently within fixed memory constraints. Such a structure is useful when the positioning of elements needs to be periodically overwritten in a fixed-size storage system.

• Essential functions for the circular queue, such as createCircularQueue, enqueue, and getCircularQueueElement, initialize, add elements to, and retrieve elements from the circular queue, respectively.

• The minimumHealth function calculates the required health at each step to ensure survival. It considers boundaries by checking if the suggested next cell is outside the grid. If it is, it defaults to a very high value (LIMIT_MAX) to ensure it's not chosen as a path.

• The main function, calculateMinHealth, initializes the circular queue for a single row storage since only one row is needed at a time due to re-computation from the bottom-right to top-left of the matrix (dynamic programming). For each cell in the matrix, it calculates and updates the minimum health required based on the right and downward cells using the minimumHealth. The dynamic aspect is that it fills the queue from the last cell towards the first, and each cell is calculated based on the future cell, which would have already been calculated and stored in the queue.

• The solution ends by returning the value from the circular queue representing the minimal initial health needed at the dungeon's entrance (top-left cell after iterative backward computation).

This algorithm effectively manages space by using a circular queue that only updates needed values and optimally computes the required health by dynamically adjusting from the grid's end towards the start, ensuring the solution remains within bounds and efficiently uses the computed health requirements.

class CircularQueue {
    constructor(size) {
        this.elements = new Array(size);
        this.end = 0;
        this.size = size;
    }

    push(value) {
        this.elements[this.end] = value;
        this.end = (this.end + 1) % this.size;
    }

    getValue(index) {
        return this.elements[index % this.size];
    }
}

var calculateMinHP = function (dungeon) {
    const rowCount = dungeon.length;
    const colCount = dungeon[0].length;
    const healthQueue = new CircularQueue(colCount);

    const calcMinHealth = (current, adjRow, adjCol) => {
        if (adjRow < 0 || adjCol < 0) return Infinity;
        const idx = colCount * adjRow + adjCol;
        const nextValue = healthQueue.getValue(idx);
        return Math.max(1, nextValue - current);
    };

    for (let r = 0; r < rowCount; r++) {
        for (let c = 0; c < colCount; c++) {
            const currentCell = dungeon[rowCount - r - 1][colCount - c - 1];
            const healthRight = calcMinHealth(currentCell, r, c - 1);
            const healthDown = calcMinHealth(currentCell, r - 1, c);
            const requiredHealth = Math.min(healthRight, healthDown);

            let minimumHealth;
            if (requiredHealth !== Infinity) {
                minimumHealth = requiredHealth;
            } else {
                minimumHealth = currentCell >= 0 ? 1 : 1 - currentCell;
            }

            healthQueue.push(minimumHealth);
        }
    }

    return healthQueue.getValue(colCount - 1);
};

This JavaScript implementation solves the "Dungeon Game" problem using dynamic programming combined with a circular queue to efficiently manage memory. The CircularQueue class is defined first, providing basic queue functionalities tailored to the solution's needs, including push for adding values and getValue for retrieving them based on an index.

The calculateMinHP function calculates the minimum initial health required for a character to navigate through a dungeon grid where each cell has a value that either damages (negative value) or heals (positive value). The dungeon is represented as a 2D array.

The core algorithm assesses the necessary health starting from the dungeon's bottom-right corner and works its way back to the top-left corner. For each cell, it calculates the minimal health required to step into either the right or downward cell, or to survive on the current cell if it is the bottom-right. This involves:

• Using the custom circular queue to store the minimal health required at each position, ensuring that the solution manages memory usage efficiently.
• A helper function, calcMinHealth, computes the minimum health needed based on the value of the current cell and the health required for adjacent cells (either to the right or below).

Finally, the health at the starting point (top-left corner) required to ensure survival through to the dungeon's end is derived from the CircularQueue. This health value is the answer returned by calculateMinHP. This approach ensures that the solution is both time-efficient and space-optimized, using a linear amount of extra space relative to the dungeon's width.

class CircularQueue:
    def __init__(self, max_size: int) -> None:
        self.data = [0] * max_size
        self.end = 0
        self.max_size = max_size

    def enqueue(self, element: int) -> None:
        self.data[self.end] = element
        self.end = (self.end + 1) % self.max_size

    def element_at(self, position: int) -> int:
        return self.data[position % self.max_size]

class DungeonSolver:
    def minInitialHealth(self, dungeonArea: List[List[int]]) -> int:
        total_rows, total_cols = len(dungeonArea), len(dungeonArea[0])
        queue = CircularQueue(total_cols)

        def health_needed(cellValue: int, prevRow: int, prevCol: int) -> int:
            if prevRow < 0 or prevCol < 0:
                return float("inf")
            pos_index = total_cols * prevRow + prevCol
            health = queue.element_at(pos_index)
            return max(1, health - cellValue)

        for row in range(total_rows):
            for col in range(total_cols):
                cellValue = dungeonArea[total_rows - row - 1][total_cols - col - 1]

                right_health = health_needed(cellValue, row, col - 1)
                down_health = health_needed(cellValue, row - 1, col)
                required_health = min(right_health, down_health)

                if required_health != float("inf"):
                    min_health_req = required_health
                else:
                    min_health_req = 1 if cellValue >= 0 else (1 - cellValue)

                queue.enqueue(min_health_req)

        return queue.element_at(total_cols - 1)

Here's a solution summary for the "Dungeon Game" problem implemented in Python:

• CircularQueue Class:

  • The CircularQueue class facilitates a circular buffer of a specified maximum size, useful for holding health values in the dungeon grid. It supports insertion (enqueue) and retrieval (element_at) of elements based on their position.

• DungeonSolver Class:

  • The central method minInitialHealth in DungeonSolver calculates the minimum health needed to start from the bottom-right corner of the dungeon grid and reach the top-left corner alive.
  • The dungeon grid has rows and columns, and each cell can have a negative or positive value, affecting the player's health as they traverse.
  • A local function health_needed is used to determine the least health required upon visiting a cell, considering the previous visited cell's health.

• Algorithm Approach:

  1. Traverse the dungeon grid starting from the bottom-right to the top-left using double loops.
  2. For each cell, determine the minimum required health from two possible next moves: right or down.
  3. Store the computed health requirements in a CircularQueue to efficiently manage the space instead of a 2D list.
  4. health_needed uses the CircularQueue to get the health at previous positions and adjusts it based on the current cell's value.
  5. The final result, or the minimum initial health needed, is obtained by looking up the health stored for the last processed cell (the original dungeon's top-left).

• Final Output:

  • The output is the minimum health value that ensures the player can start at the bottom-right corner and successfully reach the top-left corner without the health dropping to zero or below at any point. This value is retrieved from the CircularQueue.