Minimum Cost Path Analysis (Python)

Multi-dimensional arrays and Matrices are popular interview topics in programming technical interviews. Although practical applications for such questions may be a stretch at times, such questions do test an interviewees ability to work with different data types, as well as the ability to consolidate code into concise chunks. One question in this group that I particularly like deals with the minimum cost path. Take the above example with the map, and roads in a grid format. If you were trying to get from point A to point B, you might think of each street in terms of distance or time. Thus, depending on your route from point A to point B, your time traveled and distanced traveled would likely vary. To complicate matters, if each road were a one way street, then you wouldn’t be able to travel backwards if you discovered that there was a lot of traffic on your chosen route. Determining the minimum cost path in this example would require examining the values of either distance or time in each leg, and calculating the route that would give you the minimum sum value. This is very similar to the idea behind the minimum cost path problems often asked in these technical interviews. Translating the example above to something that might look more familiar, consider this example: Instead of a map, you would typically see something like this. A grid of numbers. Our job, as developers, is to find the path from the top left to the bottom right, which will give us the minimum cost path, or minimum path sum. Typically, we would only be able to choose adjacent numbers, and only move in the direction of down, or right across the grid. Here’s how that might work: If, in this example, we chose a path that took us straight across and then down, we would add each value across the path, giving us a total path cost of 2707. However, the minimum cost path is likely much smaller. Let’s look at another, simplified example: In this visual, I’ve decreased the value of each number, and given reference points to each grid value. For example, the first grid item could be referenced by the coordinates (a,v). This will help us determine which value we are referencing. When we move from pseudo code to real code, we will probably use an array, and can reference values by indices instead. In this example, obviously we could simply calculate the minimum path probably in a matter of minutes, as the total paths are limited. However, imagine a grid of 20 x 20, or even 100 x 100. The number of possible paths would quickly become too large to calculate, even using programs. Even if we could calculate the value of each path, and compare, using brute force to determine the minimum path, such operations are usually quite memory intensive, and far less efficient than other methods. Let’s use this simple example to see a more efficient way to determine the minimum cost path. To start off, we will look at the first row and first column in our grid. Remember, we can only move either right or down to the ending value. Here, I have updated the new values in the first row and first column and given the equation that gives me that value. In the first row, we get the new value by adding the value of the current grid value to the value of the previous grid block. In the first column, we get the new value of that block by adding the current value to the value of the block above it. Now, we do something a little different for block (b,w). Because it has a block both above it and beside it to the left, we could add either block. Since we want the eventual minimum cost path, it makes sense that we will choose the block of the lesser value. In this case, it is block (a,w) with a value of 3. The updated value is 7, (3+4). Now, let’s do the same thing across the current row: Here, we have updated each value in the row, selecting the lowest value of each choice. If the value above the current block is lower, we will get the sum of the two blocks. But if the block to the left is a lesser value, we will use that sum instead for our updated value. Let’s fill out the remainder of our grid with the updated values. By adding all the minimum sums at each block, our ending block has a value of 18. If we trace our path backward, we can confirm that 18 is indeed our minimum cost sum. Now, this may seem somewhat trivial on this small example, but imagine again how much easier this method is, especially if our numbers were larger, or our grid had more values. Not to mention, this method is far more efficient than calculating and comparing each possible path. Now, let’s take a look at how this could translate into actual code. My goal isn’t to write a hardcoded script that will solve this one problem, but a function that will solve any grid of any size. To test my program, I’m going to start with the grid from before, but here, I’ve converted it into a single array: arr = [131, 673, 234, 103, 18, 201, 96, 342, 965, 150, 630, 803,746, 422, 111, 537, 699, 497, 121, 956, 805, 732, 524, 37, 331] Next, I’m going to define some variables. These variables will be very important in being able to reuse this exact code later on grids of different sizes. rows = 5columns = 5length = len(arr)l = range(length)firstColumn = l[5::rows]firstRow = range(1, columns) the rows variable defines the number of rows this grid has. I have 25 numbers in my array, but I could break it up differently in terms of rows and columns. This will help me stay organized. The columns variable does the same thing. Now, if I had a different array, say of 100, or 1000 numbers, I could change my rows and columns variables to reflect the new amount of rows and columns my new grid would have based on the array length. My length variable will help me set the following variables. Since the math for the first row and first column is different than all the other grid blocks, I won’t to be able to select these separately, and knowing the length of the array will help me do that. I define my firstColumn variable. Since the variable ‘l’ is now a list, containing a range of numbers that represents the length of my array, I’m using that range to determine this variable. In this example, since I have 5 rows, the index values I want will be 5, 10, 15 and 20. That would make up my first column. basically takes that list, starts at 5, and skips over the numbers and grabs every 5th subsequent value, giving me the indexes I need. If I later used a larger grid, I might start it at a different value, depending on how large my rows and columns were going to be. l[5::rows] My first row variable is a range. I could simply say ‘ ’, since those are the indexes I need. But again, I want this code to be as reusable as possible for the future. Because I don’t want the first value, , I’m starting at ‘1’, which will be the same, regardless of the grid size, and I’ll end with the variable column, which will remain the same. If I have a larger grid, once I’ve updated the variable and , then this line of code will automatically reflect that change, and I won’t have to update it elsewhere. 1, 2, 3 & 4 index 0 column row With my variables in place, I’ll now loop through my array/list using a for loop: for idx, val in enumerate(arr): Typically the for loop syntax in python looks like , but Python has a built in method called enumerate. This is really handy because, without it, if I grab the variable , it gives me the current value, not the index of that value. This may be confusing to some, as in JavaScript, calling i gives you the index instead of the value. Using this syntax though, I could do the following: for i in x: i print (idx, arr) and Python would return an array with the index and the value at that index. The indices are going to be very important here, as I’ll mainly be controlling what happens in the list through the indices. Let’s start with the first index, 0: if idx == 0: # Targets first list valueval == val # Leaves first value the same The first value doesn’t change, we we just set it to itself for good measure. Next, we’ll select and modify the values in the first row and first column of our list/array just as we did in the visual examples earlier. if idx in firstRow: # Targets values in first row after first valuearr[idx] = arr[idx] + arr[idx-1] # Adds all values in first row to the previous list valueif idx in firstColumn: # Targets all values in first columnarr[idx] = arr[idx] + arr[idx-rows] # adds value to the value above in previous row The basically checks to see if the current index is in the variable firstRow. Remember, firstRow contains not one number, but a range of numbers that represent all the first index values in our array excluding the first. If the current index we are looping through is included in that list/array, then we simply add it to the previous index value. The method could be comparable to the JavaScript includes method. idx in firstRow idx in We do the same thing with our columns, we use the to check if the index is also in that list. If so, instead of adding it to the previous index value, we look back using the variable . Doing this looks back to the previous row, and then gets the sum of those two values. I could do [idx-5] here, but [idx-rows] again allows my code to be more reusable in the future, as the only variable I’ll need to change if my grid is larger will be the rows and columns variable. in firstColumn rows Now that we’ve taken care of the first row and column in our grid, all that’s left are the remaining numbers. I don’t need to specify a row or a column. I can simply say, “if the current index isn’t in either of the other lists, then do something else”. if idx not in firstColumn and idx not in firstRow: # targes any other values not in first row or first columnif arr[idx] + arr[idx-1] < arr[idx] + arr[idx-rows]: # determine if value above or previous is smallerarr[idx] = arr[idx] + arr[idx-1] # sets valueelse:arr[idx] = arr[idx] + arr[idx-rows] # sets value In the previous example we took the value of the previous index, or the value of the index on the row above, depending if we were in the first row or first column of our grid. In these index values, we can choose either. So we’re using an if statement to determine if the value to the left of the current value, or the index value above the current value is smaller. We get the sum of whichever one is smaller, and set the current array value to the new value. If we print the array/list, then the value we want will be the second value from the end of the array. We can see here that the minimum cost path for this example is 2427, quite a bit smaller than the path we started off with, which was a sum of 2707. Here’s what the entire code block looks like in one piece: arr = [131, 673, 234, 103, 18, 201, 96, 342, 965, 150, 630, 803,746, 422, 111, 537, 699, 497, 121, 956, 805, 732, 524, 37, 331] rows = 5columns = 5length = len(arr)l = range(length)firstColumn = l[5::rows]firstRow = range(1, columns)for idx, val in enumerate(arr):if idx == 0: # Targets first list valueval == val # Leaves first value the sameif idx in firstRow: # Targets values in first row after first valuearr[idx] = arr[idx] + arr[idx-1] # Adds all values in first row to the previous list valueif idx in firstColumn: # Targets all values in first columnarr[idx] = arr[idx] + arr[idx-rows] # adds value to the value above in previous rowif idx not in firstColumn and idx not in firstRow: # targes any other values not in first row or first columnif arr[idx] + arr[idx-1] < arr[idx] + arr[idx-rows]: # determine if value above or previous is smallerarr[idx] = arr[idx] + arr[idx-1] # sets valueelse:arr[idx] = arr[idx] + arr[idx-rows] # sets valueprint arr # returns list Again, going back to technical interviews, a great thing about studying and becoming familiar with these grid, and multi-dimensional array problems, is that they build skills in consolidating code so that it can run more efficiently. Let me know if you have any feedback. Thanks!