<jupyter_start><jupyter_text>Dynamic Programming Example Abstract the problemGiven an integer 1≤N≤20, an N×N grid of integers 1≤Gij≤10, and a target 1≤T≤200, find the path from top left to bottom right in the grid (moving right or down at each step) which, when subtracted from T, leaves the smallest remainder r≥0 (if any such path exists).<jupyter_code>from functools import lru_cache

def smallest_remainder(total, grid):
    """Return the smallest remainder from total after subtracting the
    numbers on a path from top left to bottom right of grid, or -1 if
    there is no path whose sum is less than or equal to total.

    >>> smallest_remainder(7, [[0, 2, 5], [1, 1, 3], [2, 1, 1]])
    0
    >>> smallest_remainder(12, [[0, 2, 5], [1, 1, 3], [2, 1, 1]])
    1

    """
    @lru_cache(maxsize=None)
    def r(t, i, j):
        # Smallest remainder from t after subtracting the numbers on a path
        # from top left to (i, j) in grid, or total + 1 if there is no
        # path whose sum is less than or equal to t.
        t -= grid[i][j]
        if i < 0 or j < 0 or t < 0:
            return total + 1
        elif i == j == 0:
            return t
        else:
            return min(r(t, i - 1, j), r(t, i, j - 1))

    remainder = r(total, len(grid) - 1, len(grid) - 1)
    return remainder if remainder <= total else -1
from random import randrange
N = 20
grid = [[randrange(1, 6) for _ in range(N)] for _ in range(N)]
T = 200
print(grid)
print(smallest_remainder(T, grid))
print("hoho")<jupyter_output>[[3, 4, 1, 1, 4, 4, 2, 4, 2, 4, 3, 1, 5, 5, 5, 5, 4, 5, 3, 2], [1, 4, 1, 4, 1, 2, 3, 2, 2, 1, 5, 3, 4, 5, 3, 5, 4, 1, 1, 5], [3, 2, 1, 4, 2, 3, 2, 1, 3, 1, 1, 3, 3, 3, 5, 1, 2, 5, 2, 4], [5, 3, 3, 1, 1, 4, 2, 4, 2, 1, 3, 4, 1, 5, 4, 1, 1, 3, 2, 1], [5, 2, 1, 4, 3, 5, 2, 2, 3, 3, 5, 5, 2, 5, 2, 2, 1, 2, 1, 5], [2, 4, 3, 2, 4, 1, 4, 1, 3, 5, 4, 4, 5, 1, 1, 4, 2, 1, 3, 4], [1, 3, 2, 2, 4, 4, 1, 5, 4, 2, 5, 5, 1, 3, 5, 1, 1, 5, 1, 3], [5, 3, 2, 5, 3, 2, 4, 4, 5, 3, 5, 2, 5, 4, 2, 5, 3, 3, 3, 5], [1, 2, 2, 1, 1, 2, 5, 4, 5, 5, 5, 3, 4, 5, 1, 1, 2, 4, 3, 2], [5, 4, 1, 1, 3, 3, 4, 4, 1, 2, 2, 3, 2, 1, 3, 1, 1, 2, 2, 2], [4, 4, 2, 2, 1, 3, 1, 4, 1, 2, 3, 1, 5, 1, 1, 2, 4, 3, 1, 4], [5, 5, 2, 2, 2, 5, 4, 4, 4, 3, 4, 2, 5, 1, 4, 3, 1, 5, 4, 4], [5, 2, 3, 5, 1, 1, 1, 4, 2, 1, 5, 3, 4, 2, 5, 2, 4, 5, 2, 4], [1, 4, 4, 1, 3, 2, 3, 4, 3, 2, 3, 1, 1, 1, 1, 1, 1, 4, 1, 5], [3, 4, 2, 4, 2, 5, 1, 5, 2, 4, 5, 3, 1, 4, 3, 4, 5, 3, 2, 2], [3, 3, 1, 4, 5, 4, 2, 5, 2, 5, 4, 3, 5, 3, 1, 2, 3, 1, 3, 2], [2, 1, [...]<jupyter_text>Other Example<jupyter_code>import unittest
import heapq

class Node:
    def __init__(self, food, position):
        self.food_remaining = food
        self.position = position

    def __lt__(self, other):
        return self.food_remaining < other.food_remaining

def ZombieGrid(food, grid):
    grid_height = len(grid)
    grid_width = len(grid[0])

    pq = []
    # Rabbit starts in the top-left corner: 0,0
    heapq.heappush(pq, Node(food, (0,0)))

    while len(pq) > 0:
        top = heapq.heappop(pq)

        # once we're in the bottom-right corner then we are done
        if top.position == (grid_height-1, grid_width-1):
            return top.food_remaining

        # try moving down
        if top.position[0] < grid_height-1:
            # will use the food up for the room below
            food_for_room_below = grid[top.position[0]+1][top.position[1]]
            # don't go to the room if we will get eaten!
            if top.food_remaining - food_for_room_below >= 0:
                heapq.heappush(pq, Node(top.food_remaining - food_for_room_below, (top.position[0] + 1, top.position[1]) ))

        # try moving right, same logic as for moving down
        if top.position[1] < grid_width-1:
            food_for_room_right = grid[top.position[0]][top.position[1]+1]
            if top.food_remaining - food_for_room_right >= 0:
                heapq.heappush(pq, Node(top.food_remaining - food_for_room_right, (top.position[0], top.position[1] + 1) ))


class UnitTests(unittest.TestCase):
    def test_first(self):
        self.assertEqual(0, ZombieGrid(7, [[0, 2, 5], [1, 1, 3], [2, 1, 1]]))
    def test_second(self):
        self.assertEqual(1, ZombieGrid(12, [[0, 2, 5], [1, 1, 3], [2, 1, 1]]))


tests = UnitTests()
tests.test_first()
tests.test_second()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.17473056638385692, 'fraction_numerical': 0.09722540701673928, 'mean_word_length': 2.596042868920033, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '407520', 'license': 'Apache-2.0', 'n_tokens_mistral': 2182, 'n_tokens_neox': 1789, 'n_words': 697, 'path': 'py_DynamicProg_lru_cache.ipynb', 'repo_name': 'tarunkp/Python_Tutuorial_QuickRef', 'size': '4361'}