Search code examples
pythonalgorithmgraphgraph-algorithmweighted-graph

Python Algorithm Problem | How to find a path of desire weight in a connected graph?

Problem

So imagine you are given a m * n matrix like this:

Grid = 4 * 4

1 1 1 1    
2 2 2 2    
3 3 3 3    
4 4 4 4

You want to connect from the top left corner to the bottom right corner and you can only go right or down. In addition, you want to find the operations needed to get the desired sum.

For example:

enter image description here

Script found in Text Book, not clear

def move(m, n, sum):
  count = m + n - 1
  max_val = m
  s = sum
  r = []
  while max_val > 0:
    if count <= 0:
      return False, r
    least = max_val * ((max_val - 1) / 2)
    r.append(max_val)
    s -= max_val
    count -= 1
    while ((count > 0) and (s > least + (count - (max_val - 1)) * (max_val - 1))):
      r.append(max_val)
      s -= max_val
      count -= 1
    if s < least:
      return False, r
    max_val -= 1
  return True, r


def combine(m, n, sum):
  result, new_res = move(m, n, sum)
  new_res.reverse()
  for i in range(1, len(new_res)):
    if new_res[i] == new_res[i - 1]:
      print("R")
    else:
      print("D")

combine(4, 4, 16)

I don't quite understand the solution.

Can someone explain the Algorithm?

Especially in the function move where it does this check in the while loop:

while ((count > 0) and (s > least + (count - (max_val - 1)) * (max_val - 1))):

Questions

  1. What is the name of this algorithm?
  2. How does this Script Work?
  3. What's the run time (Time complexity)?

Thank you!

Solution

  • So the script isn't well written nor follow best practices, having say that I re adjust it and hopefully is more clear

    Source Code

    NOTE: I've added to my GitHub Algorithm-Complete-Guide which is under construction, feel free to use it

    def move(m, n, weight_limit):

    # ==== < CONFIG VARIABLES > ==== #
    step_counter = m + n - 1
    max_val = m         # NOTE: It starts from the last Value (4) and Goes Backwards
    path = []           # NOTE: Stores the path (need to reverse it afterwards)
    while max_val:
        if step_counter <= 0:   # NOTE: starting Node so it break Not need to return
            break
        least = max_val * ((max_val - 1) / 2)
        path.append(max_val)
        weight_limit -= max_val
        step_counter -= 1
        if weight_limit < least:  # NOTE: Moved it up here because makes more sense to check this first and break
            break
        # ==== < ROW CHECK | CAN IT GO TO THE LEFT? > ==== #
        if step_counter:     # NOTE: Moved it as makes it more clear
            check_row = least + (step_counter - (max_val - 1)) * (max_val - 1)
            while weight_limit > check_row:  # FAQ: 1 Footnotes
                path.append(max_val)
                weight_limit -= max_val
                step_counter -= 1

        max_val -= 1
    return path


def combine(m, n, sum):
    path = move(m, n, sum)
    path.reverse()  # NOTE: Reverse the result Path
    result = []
    for i in range(1, len(path)):
        if path[i] == path[i - 1]:   # NOTE: Check if next Value is the same then it moved it to the Right
            result.append((path[i], 'Right'))
        else:
            result.append((path[i], 'Left'))
    return result


def prettify_result(res):
    for value in res:
        print(f'V={value[0]}) {value[1]} |-> ', end='')


if __name__ == '__main__':
    path = combine(4, 4, 16)
    prettify_result(path)

    Explanation

    1. I first thought was a Rat in a Maze problem solved with Backtracking technique of the Algorithm Depth-first_search that runs at Time Complexity: O(2^(n^2)) but after a review I doubt it, and it seems more a kind of Dijkstra's algorithm but I may be wrong. I don't think is Backtracking simple because is not recursive (and never backtracks..) but because it checks for the Node's Weight it seem a Dijkstra's with a given Max-Weight.

    2. Important note, the Maze is solved Upside down, from bottom to top! So It starts at Value 4 and runs backwards! Hence in reality is checking:

      • Direction UP with more priority.
      • Direction LEFT is checking at every step (I left a big comment in the script) all the time, if can't go (because costs too much) Then it goes up (going up costs one less because it goes 4, 3, 2, 1)

    3. "function move, what is least + (count - (max_val - 1)) * (max_val - 1)" this I had some hard time to understand as well, basically is just a Math trick and I added it in a variable called check_row to make it more explicit, but basically what it does it check if can go to the Left or not.

    4. At the end of the Algorithm it reverse the list backwards, so that looks like it went from Top to Bottom.

    Consideration

    1. The function move()returns always 2 value, first of which if False and stores is in variable result but is not even used. It is pretty weird (seems not got programming practice) and not used anyway so I just removed and replace it with a breakstatements. That's because makes more sense to break in a while loop rather than return. The Function then takes care to return pathat the end.

    2. I remove many while max_val > 0 or similar bool checks against the 0 because is completely redundant and not Pythonic, as Guide realpython.com/python-conditional-statements/

    Online Documentations

    BACKTRACKING

    Depth-first search

    Dijkstra's algorithm