Не могу понять, где эта рекурсия ломается

Question

Это для Появления Кодекса, День 17 *. 1002 * По сути, у вас есть карта «контейнеров» и «воды», которая течет вниз от y = 0. (Давление воды не применяется.) ВыВы должны выяснить, сколько ячеек сетки будет "водой" к тому времени, как это будет сделано, заполняя все контейнеры, в которые он может добраться.

Я буквально заставил его ПОЧТИ работать через пять минут, но потом он победил 'не заканчиваю ... Я возился с этим большую часть дня и до сих пор не могу понять.Размещайте операторы печати после каждой строки, чтобы следить за происходящим (пробовал PythonTutor, но способ, которым вы должны прокручивать около пяти минут, чтобы увидеть вывод, особенно для длинного рекурсивного кода, после каждой итерации немного раздражает).Затем попытался сдвинуть возврат после почти каждой строки и внутри каждой петли.Все еще ничего ... Я ненавижу, как выглядит простая рекурсия, но тогда вы просто начинаете путать себя (по крайней мере, я ...) Теперь я просто устал и растерян.Любая помощь приветствуется.

coor = [(495, 2), (495, 3), (495, 4), (495, 5), (495, 6), (495, 7), (495, 7), (496, 7), (497, 7), (498, 7), (499, 7), (500, 7), (501, 7), (501, 3), (501, 4), (501, 5), (501, 6), (501, 7), (498, 2), (498, 3), (498, 4), (506, 1), (506, 2), (498, 10), (498, 11), (498, 12), (498, 13), (504, 10), (504, 11), (504, 12), (504, 13), (498, 13), (499, 13), (500, 13), (501, 13), (502, 13), (503, 13), (504, 13)]

cx, cy = zip(*coor)
minx, maxx = min(cx), max(cx)
miny, maxy = min(cy), max(cy)

water = []

def flow(water, pt):
  if pt not in water:
    water.append(pt)
  x,y = pt
  if y < maxy:
    while (x, y+1) not in coor:
      if y+1 > maxy:
        return
      plotW(water)
      water.append((x,y+1))
      y += 1

    collect(water, (x, y))
  else:
    return


def collect(water, pt):
  x,y = pt
  if minx <= x <= maxx and y < maxy:
    i = x - 1
    j = x + 1

    # fills container half to the left of the stream
    while (i, y) not in coor:
      if y >= maxy: break
      plotW(water)
      if (i, y+1) in coor or (i, y+1) in water:
        if (i, y) not in water:
          water.append((i, y))
          i -= 1
      else:
        flow(water, (i, y))
        break

    # fills container half to the right of the stream
    while (j, y) not in coor:
      if y >= maxy: break
      plotW(water)
      if (j, y+1) in coor or (j, y+1) in water:
        if (j, y) not in water:
          water.append((j, y))
          j += 1
      else:
        flow(water, (j, y))
        break

    collect(water, (x, y-1))

def plotW(water):
  wx, wy = zip(*water)

  fig = plt.figure(figsize = (2,2.5))
  plt.xlim(minx-1, maxx+1)
  plt.ylim(miny-1, maxy)
  plt.scatter(cx, cy, marker = 's', color = 'r')
  plt.scatter(wx, wy)
  plt.gca().invert_yaxis()
  plt.axes().set_aspect('equal', 'datalim')
  plt.show()

flow(water, (500, 0))

последние два шага выглядят так: (должны были остановиться на втором изображении)

Answer 1

ПОЛУЧИЛ это ПОЧТИ, работающее через пять минут, но затем оно не прекратит работу

Я изменил его, чтобы завершить (на описываемой вами стадии) посредством более строгого контроляy координата.Вам нужно решить, имеют ли эти изменения смысл в контексте того, что вы делаете:

import matplotlib.pyplot as plt

coordinates = [
    (495, 2), (495, 3), (495, 4), (495, 5), (495, 6), (495, 7), (495, 7), (496, 7),
    (497, 7), (498, 7), (499, 7), (500, 7), (501, 7), (501, 3), (501, 4), (501, 5),
    (501, 6), (501, 7), (498, 2), (498, 3), (498, 4), (506, 1), (506, 2), (498, 10),
    (498, 11), (498, 12), (498, 13), (504, 10), (504, 11), (504, 12), (504, 13),
    (498, 13), (499, 13), (500, 13), (501, 13), (502, 13), (503, 13), (504, 13)
]

cx, cy = zip(*coordinates)
min_x, max_x = min(cx), max(cx)
min_y, max_y = min(cy), max(cy)

water = []

def flow(water, point):
    if point not in water:
        water.append(point)
        plotW(water)

    x, y = point

    if y < max_y:
        while (x, y + 1) not in coordinates:
            if y + 1 > max_y:
                return y

            water.append((x, y + 1))
            plotW(water)
            y += 1

        y = collect(water, (x, y))

    return y

def collect(water, point):
    x, y = point

    if min_x <= x <= max_x and y < max_y:
        i, j = x - 1, x + 1

        # fills container half to the left of the stream
        while (i, y) not in coordinates:
            if y >= max_y:
                break

            plotW(water)

            if (i, y + 1) in coordinates or (i, y + 1) in water:
                if (i, y) not in water:
                    water.append((i, y))
                    i -= 1
            else:
                _ = flow(water, (i, y))
                break

        # fills container half to the right of the stream
        while (j, y) not in coordinates:
            if y >= max_y:
                break

            plotW(water)

            if (j, y + 1) in coordinates or (j, y + 1) in water:
                if (j, y) not in water:
                    water.append((j, y))
                    j += 1
            else:
                y = flow(water, (j, y))
                break

        if y < max_y:
            y = collect(water, (x, y-1))

    return y

def plotW(water):
    wx, wy = zip(*water)

    plt.figure(figsize=(2, 2.5))
    plt.xlim(min_x - 1, max_x + 1)
    plt.ylim(min_y - 1, max_y)
    plt.scatter(cx, cy, marker='s', color='r')
    plt.scatter(wx, wy)
    plt.gca().invert_yaxis()
    plt.axes().set_aspect('equal', 'datalim')
    plt.show()

flow(water, (500, 0))