So while reading about technical interviews recently, I have also been trying to practice my hand at solving problems that I have never seen before.

While I do a lot of practice on Exercism, I am now reasonable familiar with most of the problems and have solved them in at least one language (probably elixir or javascript or go). So I went on the hunt for new content. As a result I have been working through problems at leetcode.com on its free tier.

It lets you work through problems with your choice of language to write it in. So that was my first decision to make. I wanted to practice solving problems, not learn languages so I felt I should pick a language that I want to stick to so that I can write it well if I were to be called to do so in a session. At this point I chose Ruby just because of its rich standard library, focus on readability, and being able to then code in a variety of styles.

So on to the problem:

So imagine there is a box of oranges, and if a rotten orange is in the box, after a step of time, it causes oranges that are orthogonally adjacent to rot. How many steps until the rot has propagated to its maximum extent?

So a few things occurred to me:

  • I need to represent a grid (2d array)
  • I need to model a step of time (array)
  • I need to be able to halt after a step to make note of how many steps I’ve made and if more need to occur.

So my approach started with using a nested loop, with the outer loop representing the current step and the inner loop representing the rotten oranges propagating to the adjacent fresh orange.

def oranges_rotting(grid)
    # ...

    while _____ do # loop until all the oranges are rotten, or no more steps to perform
        while _____ do # rot fresh oranges if they are beside rotten oranges
        end
    end

    # ...
end

So I then decided that I would represent this with two stacks that I would exchange to represent this_step and next_step. when the program starts, next_step will be filled with all of the rotten oranges in the initial grid and this_step is empty. With each iteration next_step and this_step are exchanged, and then as each orange on the stack is processed, add them to the next_step stack.

def oranges_rotting(grid)
    # ...

   count = 0
    while !next_step.empty? do
        this_step, next_step = next_step, this_step

        while !this_step.empty? do
            # rot the adjacent fresh oranges, mark them for the next step
        end
        count += 1 if !next_step.empty?
    end

   # ...
end

I believe this is the crux of the problem, to find a way to compute each step without then taking a moment to determine how many steps have occurred. Propagating the rotting oranges became relatively trivial:

# Using coordinate notation, these are the four directions that a rotten orange can rot fresh oranges
def mutations
    [
        [-1, 0],
        [0, -1],
        [0, 1],
        [1, 0],
    ]
end

# for each orange at the coordinates {y, x} on the grid, check the adjacent spaces and add them to next step
def rot_surrounding(grid, y, x, next_step)
    height = grid.length
    width = grid[0].length
    mutations.each do |(dy, dx)|
        adj_x = x + dx
        adj_y = y + dy
        # Because of ruby's handy ability to handle negative array indices, a more verbose check was required here
        if (0...height).include?(adj_y) && (0...width).include?(adj_x) && grid[adj_y][adj_x] == FRESH_ORANGE
            grid[adj_y][adj_x] = ROTTEN_ORANGE
            next_step.push([adj_y, adj_x])
        end
    end
end

Lastly, a scan was needed at the start to find the rotten oranges in the grid, and at the end to determine if all fresh oranges were reachable by rotten oranges.

def scan_grid(grid, type)
    found = []
    grid.each_with_index do |row, y|
        row.each_with_index do |cell, x|
            found.push([y, x]) if cell == type
        end
    end
    found
end

The complete code can be found on my github gist here: