Applied Problem Solving

Recently I had some free time and decided to checkout a few questions from LeetCode.

Struggled and relearned a few insights during this experiment so writing them down for my future self.

The idea is to document the unfiltered process, revisit what worked and what did not to improve problem solving skills.

Here’s how it went down along with some relevant commentary.

Picked a medium level problem about rotating a box that may contain stone(s), stationary object(s), obstacle(s) or empty space. The details:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
You are given an m x n matrix of characters box representing a side-view of a box. Each cell of the 
box is one of the following:
    A stone '#'
    A stationary obstacle '*'
    Empty '.'
The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each 
stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity 
does not affect the obstacles' positions, and the inertia from the box's rotation does not affect 
the stones' horizontal positions.
It is guaranteed that each stone in box rests on an obstacle, another stone, or the bottom of the 
box.

Return an n x m matrix representing the box after the rotation described above.
Input: box = [["#",".","#"]]
Output: [["."],
         ["#"],
         ["#"]]
         
         
Input: box = [["#",".","*","."],
              ["#","#","*","."]]
Output: [["#","."],
         ["#","#"],
         ["*","*"],
         [".","."]]
         
Input: box = [["#","#","*",".","*","."],
              ["#","#","#","*",".","."],
              ["#","#","#",".","#","."]]
Output: [[".","#","#"],
         [".","#","#"],
         ["#","#","*"],
         ["#","*","."],
         ["#",".","*"],
         ["#",".","."]]
         
Constraints:
    m == box.length
    n == box[i].length
    1 <= m, n <= 500
    box[i][j] is either '#', '*', or '.'         
*/

Chapter 1 - I can do it

Dove into LeetCode editor and started coding; assumed that I could figure things out along the way, did not get far. Then I remembered a wise man talking about syncing to paper. Not surprisingly, this is the strategy that Cracking the Code Interview book suggests. Great minds think alike eh?

Chapter 2 - Boxes and Lines

Started drawing the arrays to frame the problem. A few themes appeared. Need a rotated box (transformed array) and a way to transfer the items from the original box to the rotated box. Tried to do both, got quickly overwhelmed by edge cases.

Chapter 3 - Break it down

Decided to break down the problem into smaller pieces.

  • Create a rotated box
  • Move items from the original box to the rotated box
  • Apply gravity to move the stones above empty spaces

Chapter 4 - Progress!

Tackling the first problem using the drawings some patterns emerged.

  • Last row in the original box becomes the first column in the rotated box
  • Second to last row in the original box becomes the second column in the rotated box
    …

Ignoring the contents of the original box (array) wrote a function to simply rotate the box (array) and tested with different row/column sizes.

1
2
3
4
5
6
7
8
9
10
11
12
const createRotatedBox = (rowLength, columnLength, box) => {
    const rotatedBox = [];
    for(let r = 0; r < rowLength; r++){
        const rowArray = [];
        for(let c = 0; c < columnLength; c++){
            rowArray.push("X") //contents don't matter
        }
        rotatedBox.push(rowArray)
    }

    return rotatedBox
}

Chapter 5 - Moving Day

It’s time to move the items from the original box to the rotated box. I found it difficult to map the coordinates in the original box to the coordinates in the rotated box. My plan was to write a function that would say:

  • the item in (0, 2) in the original box will go into (2, 2) in the rotated box

so I created another visual to help tease out the pattern(s)

This made it easier to see the source and target coordinates of each item at a glance. That led to the following simple (in hindsight) function to get the target coordinates from the source coordinates.

1
2
const getRotatedBoxIndex = (rowIndex, columnIndex, rowLength) => 
    ({rowIndex: columnIndex, columnIndex: rowLength - 1 - rowIndex})

Chapter 6 - Gravity

The last small problem to solve was applying gravity and swapping the location of the stones if there is/are space(s) below them.

My strategy was to iterate over the columns, look at the contents and swap items accordingly. Started writing down the conditions when gravity would apply

  • if there is a stone in the column and
  • if there is a empty space below the stone
  • what if there is another empty space below that
  • …

I reluctantly had to admit that recursion may be needed in this scenario i.e. for each column start from the top and swap each stone and the empty space below it.

It’s crucial to determine the exit conditions when dealing with recursive functions. A light bulb went off in my head while thinking about when the code should stop applying gravity (swapping items) to the column.
If the code iterated through all the items in the column AND did not swap anything,
then we’re done with that column
else applyGravity again (recurse)

Behold the applyGravity function that is tested separately from the rest of the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const applyGravity= (items) => {
    let swapped = false
    for(let i = 0; i < items.length; i++){
        if(items[i] === "#" && items[i+1] === "."){
            swapped = true
            let temp = items[i]
            items[i] = items[i+1]
            items[i+1] = temp
        }
    }

    if(swapped) return applyGravity(items)
    
    return items
}

Now we have a function that can take an array of items in a column and applyGravity to that column swapping items if necessary. Therefore, the remaining steps are:

  • Get the columns (array of items in the column) from the rotated/populated box
  • Call applyGravity passing the items in that column (swapping items if necessary)
  • After calling applyGravity on each column, put the columns back together (rebuilding the rotated box)

Chapter 7 - AI all the things!

You have been waiting patiently to see when an LLM would come into play. Well, here it is.

Claude prompt:

1
2
javascript function that returns an array of columns for a two dimensional array

response:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function extractColumns(array) {
    // Check if the input is a valid 2D array
    if (!Array.isArray(array) || array.length === 0 || !Array.isArray(array[0])) {
        return [];
    }

    // Get the number of columns based on the first row's length
    const numColumns = array[0].length;
    
    // Initialize an array to store columns
    const columns = Array.from({ length: numColumns }, () => []);
    
    // Iterate through each row
    for (const row of array) {
        // Ensure the current row has the same length as the first row
        if (row.length !== numColumns) {
            throw new Error('All rows must have the same length');
        }
        
        // Add each element to its corresponding column
        for (let colIndex = 0; colIndex < numColumns; colIndex++) {
            columns[colIndex].push(row[colIndex]);
        }
    }
    
    return columns;
}

Claude prompt:

1
now write a function to return a two dimensional array from a columns array

response:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*I'll create a complementary function that converts an array of columns back into a two-dimensional array.*/

function extractColumns(array) {
    // Check if the input is a valid 2D array
    if (!Array.isArray(array) || array.length === 0 || !Array.isArray(array[0])) {
        return [];
    }

    // Get the number of columns based on the first row's length
    const numColumns = array[0].length;
    
    // Initialize an array to store columns
    const columns = Array.from({ length: numColumns }, () => []);
    
    // Iterate through each row
    for (const row of array) {
        // Ensure the current row has the same length as the first row
        if (row.length !== numColumns) {
            throw new Error('All rows must have the same length');
        }
        
        // Add each element to its corresponding column
        for (let colIndex = 0; colIndex < numColumns; colIndex++) {
            columns[colIndex].push(row[colIndex]);
        }
    }
    
    return columns;
}

I know exactly what these two functions are doing but I’m too lazy to write it myself.

Chapter 8 - Will it work?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var rotateTheBox = function(box) {
    // In the rotatedBox array
    // box's length will be column length
    // subarray's length will be row length
    const rotatedColumnLength = box.length
    const rotatedRowLength = box[0].length


    const rotatedBox = createdRotatedBox(rotatedRowLength, rotatedColumnLength)

    // populate rotatedBox
    for(let r = 0; r < box.length; r++){
        for(let c = 0; c < box[0].length; c++){
            const rotatedBoxIndices = getRotatedBoxIndex(r, c, box.length)
            const rowIndexInRotatedBox = rotatedBoxIndices.rowIndex
            const colIndexInRotatedBox = rotatedBoxIndices.columnIndex

            rotatedBox[rowIndexInRotatedBox][colIndexInRotatedBox] = box[r][c]
        }
    }

    const colsInRotatedBox = getColumns(rotatedBox)
    const colsAfterGravity = colsInRotatedBox.map(c => applyGravity(c))
    const boxAfterGravity = columnsToArray(colsAfterGravity)

    return boxAfterGravity

};

Not bad for the first iteration.

Afterword

I noticed that simply breaking down the problem enabled working on each one separately reducing the mental load. The functions in the solutions are easy to read (if I may say so myself) and self-contained. Despite mutating state I think the overall solution is comprised of pure functions.

A happy side-effect of this strategy is that in a bigger team we can write unit tests for each of these functions and have multiple developers work on them at the same time going forward.