fork download

copy

from time import monotonic_ns
import matplotlib.pyplot as plt
 
 
def main():
    b = []
    for i in range(100, 500):
        t = monotonic_ns()
        f = grid_traveler(i, i)
        t = monotonic_ns() - t
        c = t / (i*i)
        b.append(c)
    plt.plot(b)
    plt.show()
 
 
# Вычисляет, сколько путей есть из левого верхнего угла в правый нижний,
# при высоте n и ширине m. Двигаться можно только вправо и вниз единичными шагами
def grid_traveler(n: int, m: int, memo=None) -> int:
    if memo is None:
        memo = {}
    if n == 1 or m == 1:
        return 1
    if (key := (min(n, m), max(n, m))) not in memo:
        memo[key] = grid_traveler(n - 1, m, memo) + grid_traveler(n, m - 1, memo)
    return memo[key]
 
 
if __name__ == '__main__':
    main()
 

Traceback (most recent call last):
  File "/usr/lib/python3.7/py_compile.py", line 143, in compile
    _optimize=optimize)
  File "<frozen importlib._bootstrap_external>", line 791, in source_to_code
  File "<frozen importlib._bootstrap>", line 219, in _call_with_frames_removed
  File "./prog.py", line 24
    if (key := (min(n, m), max(n, m))) not in memo:
            ^
SyntaxError: invalid syntax

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/lib/python3.7/py_compile.py", line 147, in compile
    raise py_exc
py_compile.PyCompileError:   File "./prog.py", line 24
    if (key := (min(n, m), max(n, m))) not in memo:
            ^
SyntaxError: invalid syntax

Standard output is empty