[C++ Solution] Roman Numeral Conversion and Skyscraper Puzzle

Roman to Integer

1. Code

class Solution {
public:
    int romanToInt(string s) {
        std::unordered_map<char, int> roman_to_int = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        };
        int total = 0;
        int temp = 0;

        for (auto item = s.rbegin(); item != s.rend(); ++item) {
            int value = roman_to_int[*item];

            if (value < temp) {
                total -= value;
            } else {
                total += value;
            }
            temp = value;
        }
        return total;
    }
};

Reviews

1. int value = roman_to_int[*item] : Dereferencing

• * operator is used to dereference an iterator

• Map Access: roman_to_int[*it] uses the character obtained from dereferencing the iterator as the key to access the corresponding value in the unordered_map.

• Example Without Dereferencing:

  1. Imagine it as a bookmark in a book (the iterator)

  2. *it is the actual page where the bookmark is placed (the character in the string)

  3. You need the page (character) to look up information in a map, not the bookmark itself

2. auto keyword

• allow the compiler to automatically deduce the type of a variable from its initializer

• If I didn’t use auto, then

     for (std::string::reverse_iterator item = s.rbegin(); item != s.rend(); ++item)
  

• So, This keyword makes the code more readable by reducing clutter

Combined of Pointers

1. Code

#include <iostream>

int main() {
    int a = 10;        // Normal variable
    int *p = &a;       // Pointer variable, holding the address of 'a'

    std::cout << "Address of a (reference): " << &a << std::endl;
    std::cout << "Value of p (address of a): " << p << std::endl;
    std::cout << "Value of a: " << a << std::endl;
    std::cout << "Value of *p (dereference p): " << *p << std::endl;

    // Changing the value using the pointer
    *p = 20;
    std::cout << "New value of a after *p = 20: " << a << std::endl;

    return 0;
}

Reviews

1. reference (&) AND dereference (*)

• &a is the reference to a, giving us its address

• *p is the dereference of p, giving us the value stored at the address p holds, which is the value of a

Skyscraper

1. Code

#include <iostream>
#include <vector>
#include <algorithm>

// Function to check if placing height at (row, col) is valid
bool isValid(const std::vector<std::vector<int>>& grid, int row, int col, int height, const std::vector<int>& rowCluesLeft, const std::vector<int>& rowCluesRight, const std::vector<int>& colCluesTop, const std::vector<int>& colCluesBottom) {
    int n = grid.size();
    
    // Check if height already exists in the current row or column (remove duplicate values)
    for (int i = 0; i < n; i++) {
        if (grid[row][i] == height || grid[i][col] == height) {
            return false;
        }
    }
    
    // Check row clues if the row is fully filled
    if (std::find(grid[row].begin(), grid[row].end(), 0) == grid[row].end()) {
        // Check left clue
        int visible = 0, max_height = 0;

        // If the value in the current cell is greater than max_height, update max_height and increment visible by 1. This calculates the number of buildings visible from the left
        for (int i = 0; i < n; i++) {
            if (grid[row][i] > max_height) {
                max_height = grid[row][i];
                visible++;
            }
        }
        if (rowCluesLeft[row] != 0 && rowCluesLeft[row] != visible) {
            return false;
            // back to bool solveSkyscraper function, reset it to 0
        }
        
        // Check right clue
        visible = 0, max_height = 0;

        for (int i = n - 1; i >= 0; i--) {
            if (grid[row][i] > max_height) {
                max_height = grid[row][i];
                visible++;
            }
        }
        if (rowCluesRight[row] != 0 && rowCluesRight[row] != visible) {
            return false;
            // back to bool solveSkyscraper function, reset it to 0
        }
    }

    // Check column clues if the column is fully filled
    // The std::all_of function checks if the value in the specified column (col) is not 0 in all rows (r)
    if (std::all_of(grid.begin(), grid.end(), [&](const std::vector<int>& r) { return r[col] != 0; })) {
        // Check top clue
        int visible = 0, max_height = 0;

        for (int i = 0; i < n; i++) {
            if (grid[i][col] > max_height) {
                max_height = grid[i][col];
                visible++;
            }
        }
        if (colCluesTop[col] != 0 && colCluesTop[col] != visible) {
            return false;
        }
        
        // Check bottom clue
        visible = 0, max_height = 0;

        for (int i = n - 1; i >= 0; i--) {
            if (grid[i][col] > max_height) {
                max_height = grid[i][col];
                visible++;
            }
        }
        if (colCluesBottom[col] != 0 && colCluesBottom[col] != visible) {
            return false;
        }
    }
    return true;
}

// Backtracking function to solve the Skyscraper puzzle
bool solveSkyscraper(std::vector<std::vector<int>>& grid, const std::vector<int>& rowCluesLeft, const std::vector<int>& rowCluesRight, const std::vector<int>& colCluesTop, const std::vector<int>& colCluesBottom) {
    int n = grid.size(); // the number of rows 
    
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            if (grid[row][col] == 0) {
                for (int height = 1; height <= n; height++) {
                    if (isValid(grid, row, col, height, rowCluesLeft, rowCluesRight, colCluesTop, colCluesBottom)) {
                        grid[row][col] = height;
                        // Recursively call the function to determine if the remaining puzzle can be solved
                        if (solveSkyscraper(grid, rowCluesLeft, rowCluesRight, colCluesTop, colCluesBottom)) {
                            return true;
                        }
                        // if it is not, remove the height value and reset it to 0
                        grid[row][col] = 0;
                        // and then moves to next height value
                    }
                }
                return false;
            }
        }
    }
    return true;
}

int main() {
    int n = 4; // for example, make 4 x 4
    std::vector<std::vector<int>> grid(n, std::vector<int>(n, 0));

    std::vector<int> rowCluesLeft = {2, 2, 1, 3};
    std::vector<int> rowCluesRight = {1, 2, 2, 2};
    std::vector<int> colCluesTop = {3, 2, 2, 1};
    std::vector<int> colCluesBottom = {1, 2, 3, 2};

    // Print result matrix (n X n)
    if (solveSkyscraper(grid, rowCluesLeft, rowCluesRight, colCluesTop, colCluesBottom)) {
        for (const auto& row : grid) {
            for (int height : row) {
                std::cout << height << " ";
            }
            std::cout << std::endl;
        }
    } else {
        std::cout << "No solution found." << std::endl;
    }

    return 0;
}

Reviews

**1. std::vector<std::vector> grid(n, std::vector(n, 0))**

• Creates a 2-dimensional vector (matrix) of size n x n, with each element initialized to 0

     [
         [0, 0, 0, 0],
         [0, 0, 0, 0],
         [0, 0, 0, 0],
         [0, 0, 0, 0]
     ]
  

2. std::vector combines the advantages of array and list in C++, contiguous memory block and dyanmic resizing

• Use Vector to storing the clues as it offers sequential access and dynamic resizing

3. for (int height : row)

• Using the variable int height to print the values is that it is useful when you need to access each element individually or process each element one by one

4. Backtracking

• Explore all possible cases to solve a problem, if it is an incorrect path, it goes back and explores other paths

5. In this code, I use this algorithm

• Recursive call

  The recursive call if (solveSkyscraper(grid, rowCluesLeft, rowCluesRight, colCluesTop, colCluesBottom)) checks if the remaining puzzle can be solved

  This recursive call is the core of backtracking. It moves forward from the current state to the next possible state and tries until it solves the problem

• Backtracking

  The line grid[row][col] = 0; reverts the current height value if it does not solve the problem and tries other possible height values. This process is the essence of backtracking.