Explain what this code does. Then, convert this recursive function to an iterative one, making explicit the cubic work that's being done. The functions should return exactly the same output but the iterative one should be faster. Call your function `solve_iterative` and match the type signature of the original function. @lru_cache(maxsize=None) def solve_dp(graph, lines_left, distance_since_last): if len(graph) < lines_left: return 1e9, [] if lines_left == 0 and len(graph) == 0: return 0, [] # option 1: don't take the line value = (1e9, []) if distance_since_last < 10: value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1)) # option 2: take the line if lines_left > 0: sub, how = solve_dp(graph[1:], lines_left-1, 0) sub += graph[0] + (distance_since_last-8)**2 value = min(value, (sub, how + [len(graph)])) return value
Explain what this code does. Then, convert this recursive function to an iterative one, making explicit the cubic work that's being done. The functions should return exactly the same output but the iterative one should be faster. Call your function `solve_iterative` and match the type signature of the original function. @lru_cache(maxsize=None) def solve_dp(graph, lines_left, distance_since_last): if len(graph) < lines_left: return 1e9, [] if lines_left == 0 and len(graph) == 0: return 0, [] # option 1: don't take the line value = (1e9, []) if distance_since_last < 10: value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1)) # option 2: take the line if lines_left > 0: sub, how = solve_dp(graph[1:], lines_left-1, 0) sub += graph[0] + (distance_since_last-8)**2 value = min(value, (sub, how + [len(graph)])) return value
Below is one acceptable answer. First, we explain what the original code does, and then we give an iterative version. ───────────────────────────── Explanation of the original code The recursive function (decorated with lru_cache for memoization) takes three parameters: • graph: a sequence (for example, a list of numbers) representing data from which we choose some “lines.” • lines_left: the number of “lines” we are allowed (or required) to take • distance_since_last: a counter that measures how far (or how many items) it has been since we last “took” a line Its goal is to “parse” the graph (by consuming its first element at each recursive call) deciding at each step whether to (1) skip (“don’t take”) the current item, or (2) take the current item as a new line. The function works as follows: 1. Base cases: – If there are fewer elements left in the graph than the number of lines we must still take (len(graph) < lines_left), it returns an “impossibly high” cost (1e9) and an empty list. This means that that branch is infeasible. – If there is nothing left (graph is empty) and we are done taking the required lines (lines_left == 0), then the total “cost” is 0 and no choices remain. 2. Two options are tried: (a) Option 1 (skip): If the “distance_since_last” is less than 10, we “skip” the current element. This is done by making a recursive call on graph[1:] (that is, the graph with the first element removed), keeping the same number of lines_left but incrementing distance_since_last (as we’ve walked past one more element). (b) Option 2 (take): If lines_left is positive (i.e. we are allowed to take a line), one may “take” the current element. In that case, we add the cost of this element (graph[0]) and add a quadratic penalty (distance_since_last–8)². (The idea is that if you wait too long before taking a line, you pay a penalty.) Then, a recursive call is made on the remainder of the graph, with one fewer line to take (lines_left–1) and resetting distance_since_last to 0. Notice that when “taking” the line, the function also records the “position” of the line by appending [len(graph)] to the “how” list (which is built up over the recursion). Finally, the function “minimizes” (compares by cost) between the two options and returns the best pair (total cost, list of choices). ──────────────────────────── Iterative version of the algorithm The idea behind the iterative version is to “simulate” the recursion by filling in a three‐dimensional DP table. In the recursion, we always work with the suffix of the graph graph = original_graph[i:] so it is natural to let i index the current position in the graph. The state in our DP is then (i, l, d) where • i is the current index (0 ≤ i ≤ n), • l is the number of lines still to “take” (0 ≤ l ≤ lines_left), and • d is the distance_since_last (we only allow choices when d is at most 10). The recurrence is exactly as in the recursive function: – If n – i < l then the situation is impossible. – Otherwise, if d < 10, you can “skip” the current element and the state goes to (i+1, l, d+1). – And if l > 0, you can “take” the element. In that case you pay: graph[i] + (d – 8)² plus the cost from state (i+1, l–1, 0). Also, you append the “position” [n – i] to the list of choices. Below is one acceptable implementation. ──────────────────────────── The Code Note that the function solve_iterative works exactly like solve_dp (it has the same type signature and returns the same kind of result) but fills in a DP table iteratively. (Also note that the “list‐append” here is done by list concatenation; if many lines are taken this may result in cubic work overall.) -------------------------------------------------- # iterative version of solve_dp def solve_iterative(graph, lines_left, distance_since_last): # Let n be the length of the graph. n = len(graph) INF = 1e9 # We allow distance values from 0 to 10 (inclusive). # dp[i][l][d] will store a tuple (cost, how) meaning: # starting from position i (i.e. the suffix graph[i:]), # with l lines still to take and current distance d, # the best (minimum) achievable cost and the corresponding list "how". # We need a table of size (n+1) x (lines_left+1) x 11. dp = [[[ (INF, []) for _ in range(11)] for _ in range(lines_left+1)] for _ in range(n+1)] # Base cases: at i == n (graph is empty) for l in range(lines_left+1): for d in range(11): if l == 0: dp[n][l][d] = (0, []) else: dp[n][l][d] = (INF, []) # Fill the table backwards (i from n-1 down to 0) for i in range(n-1, -1, -1): for l in range(lines_left+1): # if there are not enough elements to collect l lines then this state is infeasible. if n - i < l: for d in range(11): dp[i][l][d] = (INF, []) continue for d in range(11): best = (INF, []) # Option 1: skip the current line, if allowed. if d < 10: # When skipping, we just move to the next element and increase the distance. skip = dp[i+1][l][d+1] best = skip # best so far # Option 2: take the current line, if we have a line to use. if l > 0: cost_next, how_next = dp[i+1][l-1][0] take_cost = cost_next + graph[i] + (d - 8)**2 take = (take_cost, how_next + [n - i]) # Choose the option with the lower cost. if take[0] < best[0]: best = take dp[i][l][d] = best return dp[0][lines_left][distance_since_last] -------------------------------------------------- ──────────────────────────── How It Works • We use dp[i][l][d] to represent the solution for the “substring” of the input graph starting at index i, when we still must take l lines and the current distance_since_last is d. • Our base case is that when we’ve consumed the graph (i == n) we can only have a legal solution if l is zero. • For each state (i, l, d) we consider: – Option 1: If d < 10, we “skip” the current element; the answer then is dp[i+1][l][d+1]. – Option 2: If l > 0, we “take” the current element; we add its cost (graph[i]), add the penalty (d–8)², and then combine it with the answer from dp[i+1][l–1][0]. Also, we record our choice by adding the position (n-i). • We take whichever option has the lower cost. • Finally, dp[0][lines_left][distance_since_last] is exactly the answer for the original input. ──────────────────────────── Final Notes This iterative version “unrolls” the recursion into a triple‐nested loop (making the “cubic” work explicit via the state with indices i, l, and d and the list concatenation when building the answer). In many cases the iterative version will be faster because it avoids function call overhead and the overhead of maintaining the recursion stack, while still returning exactly the same solution (both cost and the list of choices) as the original solve_dp. Any solution that meets these requirements is acceptable.
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #!/usr/bin/env python3 # iterative version of solve_dp def solve_iterative(graph, lines_left, distance_since_last): # Let n be the length of the graph. n = len(graph) INF = 1e9 # We allow distance values from 0 to 10 (inclusive). # dp[i][l][d] will store a tuple (cost, how) meaning: # starting from position i (i.e. the suffix graph[i:]), # with l lines still to take and current distance d, # the best (minimum) achievable cost and the corresponding list "how". # We need a table of size (n+1) x (lines_left+1) x 11. dp = [[[ (INF, []) for _ in range(11)] for _ in range(lines_left+1)] for _ in range(n+1)] # Base cases: at i == n (graph is empty) for l in range(lines_left+1): for d in range(11): if l == 0: dp[n][l][d] = (0, []) else: dp[n][l][d] = (INF, []) # Fill the table backwards (i from n-1 down to 0) for i in range(n-1, -1, -1): for l in range(lines_left+1): # if there are not enough elements to collect l lines then this state is infeasible. if n - i < l: for d in range(11): dp[i][l][d] = (INF, []) continue for d in range(11): best = (INF, []) # Option 1: skip the current line, if allowed. if d < 10: # When skipping, we just move to the next element and increase the distance. skip = dp[i+1][l][d+1] best = skip # best so far # Option 2: take the current line, if we have a line to use. if l > 0: cost_next, how_next = dp[i+1][l-1][0] take_cost = cost_next + graph[i] + (d - 8)**2 take = (take_cost, how_next + [n - i]) # Choose the option with the lower cost. if take[0] < best[0]: best = take dp[i][l][d] = best return dp[0][lines_left][distance_since_last] |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #!/usr/bin/env python3 # iterative version of solve_dp def solve_iterative(graph, lines_left, distance_since_last): # Let n be the length of the graph. n = len(graph) INF = 1e9 # We allow distance values from 0 to 10 (inclusive). # dp[i][l][d] will store a tuple (cost, how) meaning: # starting from position i (i.e. the suffix graph[i:]), # with l lines still to take and current distance d, # the best (minimum) achievable cost and the corresponding list "how". # We need a table of size (n+1) x (lines_left+1) x 11. dp = [[[ (INF, []) for _ in range(11)] for _ in range(lines_left+1)] for _ in range(n+1)] # Base cases: at i == n (graph is empty) for l in range(lines_left+1): for d in range(11): if l == 0: dp[n][l][d] = (0, []) else: dp[n][l][d] = (INF, []) # Fill the table backwards (i from n-1 down to 0) for i in range(n-1, -1, -1): for l in range(lines_left+1): # if there are not enough elements to collect l lines then this state is infeasible. if n - i < l: for d in range(11): dp[i][l][d] = (INF, []) continue for d in range(11): best = (INF, []) # Option 1: skip the current line, if allowed. if d < 10: # When skipping, we just move to the next element and increase the distance. skip = dp[i+1][l][d+1] best = skip # best so far # Option 2: take the current line, if we have a line to use. if l > 0: cost_next, how_next = dp[i+1][l-1][0] take_cost = cost_next + graph[i] + (d - 8)**2 take = (take_cost, how_next + [n - i]) # Choose the option with the lower cost. if take[0] < best[0]: best = take dp[i][l][d] = best return dp[0][lines_left][distance_since_last] answer = 0 import random mylist = list(range(100)) random.shuffle(mylist) from functools import lru_cache @lru_cache(maxsize=None) def my_solve_dp(graph, lines_left, distance_since_last): if len(graph) < lines_left: return 1e9, [] if lines_left == 0 and len(graph) == 0: return 0, [] # option 1: don't take the line value = (1e9, []) if distance_since_last < 10: value = min(value, my_solve_dp(graph[1:], lines_left, distance_since_last+1)) # option 2: take the line if lines_left > 0: sub, how = my_solve_dp(graph[1:], lines_left-1, 0) sub += graph[0] + (distance_since_last-8)**2 value = min(value, (sub, how + [len(graph)])) return value answer = solve_iterative(tuple(mylist), len(mylist)//8, 4) expected = my_solve_dp(tuple(mylist), len(mylist)//8, 4) assert answer == expected, f'Wrong answer; got {answer} instead of {expected}' print('All tests passed') |
All tests passed
Testing if the previous output contains the string All tests passed: True
Resulting in output: True
Explain what this code does. Then, convert this recursive function to an iterative one, making explicit the cubic work that's being done. The functions should return exactly the same output but the iterative one should be faster. Call your function `solve_iterative` and match the type signature of the original function. @lru_cache(maxsize=None) def solve_dp(graph, lines_left, distance_since_last): if len(graph) < lines_left: return 1e9, [] if lines_left == 0 and len(graph) == 0: return 0, [] # option 1: don't take the line value = (1e9, []) if distance_since_last < 10: value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1)) # option 2: take the line if lines_left > 0: sub, how = solve_dp(graph[1:], lines_left-1, 0) sub += graph[0] + (distance_since_last-8)**2 value = min(value, (sub, how + [len(graph)])) return value
Explain what this code does. Then, convert this recursive function to an iterative one, making explicit the cubic work that's being done. The functions should return exactly the same output but the iterative one should be faster. Call your function `solve_iterative` and match the type signature of the original function. @lru_cache(maxsize=None) def solve_dp(graph, lines_left, distance_since_last): if len(graph) < lines_left: return 1e9, [] if lines_left == 0 and len(graph) == 0: return 0, [] # option 1: don't take the line value = (1e9, []) if distance_since_last < 10: value = min(value, solve_dp(graph[1:], lines_left, distance_since_last+1)) # option 2: take the line if lines_left > 0: sub, how = solve_dp(graph[1:], lines_left-1, 0) sub += graph[0] + (distance_since_last-8)**2 value = min(value, (sub, how + [len(graph)])) return value
We can explain the code as follows. (Note that “graph” here is simply a list of numbers; it isn’t a graph in the usual sense.) The recursive function solve_dp(graph, lines_left, distance_since_last) does dynamic programming with memoization (using Python’s lru_cache) over three “state” parameters: 1. The remaining “graph” (i.e. a list of numbers). In each recursive call the function “consumes” the first element (by doing graph[1:]) so that the length of the graph decreases. 2. The number of “lines” left (lines_left) that we are allowed to “take.” 3. A counter “distance_since_last” which is increased when we don’t take a line and reset to 0 when we do take one. There are two possibilities ("options") at each state: • Option 1 (“don’t take the line”): If the current distance_since_last is less than 10 then we can decide not to “take” the current line. In that case we simply recurse on the tail of the list (graph[1:]), keep the same number of lines_left, and increase distance_since_last by 1. (This option does no additional work.) • Option 2 (“take the line”): If we still have at least one “line” available (lines_left > 0), then we “take” the current line. That produces a cost of graph[0] (the number from the list) plus a penalty of (distance_since_last – 8)². (That penalty is quadratic in the “distance” from the last taken line.) Then we “consume” the first element of the list (graph[1:]) and reduce lines_left by 1, resetting distance_since_last to 0. In addition, the function builds up a list of “how” it made its choices – each time a line is taken it appends len(graph) (which is the number of items left in the current list, i.e. an index in a “reversed” sense) to the running output list. There are also two base cases: – If there aren’t enough elements left to allow “taking” lines_left many lines (if len(graph) < lines_left) we return a huge cost (1e9) and an empty list. – If we have exactly finished both the graph and used exactly the needed number of lines (lines_left == 0 and len(graph)==0), then the cost is 0 and the output list is empty. Thus, the recursive function is trying all possible ways to choose positions (subject to the constraint that you must “take” exactly as many lines as permitted and you may only “skip” a line if the “distance” has not yet reached 10) minimizing the overall cost. To “make explicit the cubic work” (that is, the three “dimensions” – the index into the graph, the lines_left, and the distance_since_last – are iterated over) we can build a bottom‐up dynamic programming table. Below is the iterative version, which we call solve_iterative. (It has the same type signature and returns exactly the same output as the original function, but avoids the recursive slicing overhead.) In our iterative solution we “index” the graph from 0 up to n – 1 (with n = len(graph)) and note that every recursive call “consumes” one element of the graph. Thus a state (graph, L, d) is equivalent to “what is the best cost (and corresponding list) from having processed i items already, with k lines remaining and a current distance d?” Since the recursive version calls solve_dp(graph, …) with graph[1:], we can define the equivalent state by letting i be the current index so that the size of the remaining list is (n – i) and the original “graph[0]” becomes graph[i]. (Also note that in the recursion the “line index” that is appended is len(graph) – and since len(graph) equals n – i, we use that when building our “how” list.) Here is the complete code: ------------------------------------------------------------ def solve_iterative(graph, lines_left, distance_since_last): # Define a very large cost for impossible cases. INF = 1e9 n = len(graph) L = lines_left # maximum number of lines we are allowed to take # We use a 3D DP table. # dp[i][k][d] = (cost, how) # where: # i in [0, n] indicates that we are at position i in the graph (so the next element is graph[i]) # k in [0, L] is the number of lines left to take # d in [0, 10] is the current distance_since_last (we never use values >10) # # In the recursion, note that if we take an element from graph, # we append len(graph) (i.e. the number of remaining items) to the list. # In our state, len(graph) is n - i. # Create and initialize dp as a 3D list with dimensions (n+1) x (L+1) x 11. dp = [ [ [(INF, []) for _ in range(11)] for _ in range(L+1) ] for _ in range(n+1) ] # Base case: when i == n (i.e. we have consumed the entire graph) for k in range(L+1): for d in range(11): if k == 0: dp[n][k][d] = (0, []) else: dp[n][k][d] = (INF, []) # Another necessary condition: if (n - i) < k then it is impossible to take k lines. # We incorporate that check in our loop. # Fill the table backwards: from i = n-1 downto 0. for i in range(n-1, -1, -1): for k in range(L+1): # If there are fewer items left than lines to take, this state is invalid. if (n - i) < k: for d in range(11): dp[i][k][d] = (INF, []) continue # skip to the next i for d in range(11): best_cost = INF best_how = [] # Option 1: Do not take the current line. # We may do this only if distance_since_last is less than 10. if d < 10: cost1, how1 = dp[i+1][k][d+1] if cost1 < best_cost: best_cost = cost1 best_how = how1 # Option 2: Take the current line. if k > 0: cost2, how2 = dp[i+1][k-1][0] # When taking the current line we incur a cost of: # graph[i] + (d - 8)^2 candidate_cost = cost2 + graph[i] + (d - 8) ** 2 if candidate_cost < best_cost: best_cost = candidate_cost # The original recursive code did: # how + [len(graph)] # and note that at state i, len(graph)==n-i. best_how = how2 + [n - i] dp[i][k][d] = (best_cost, best_how) # Finally, we return the answer corresponding to the original call: # i = 0, with the given lines_left (L) and the given distance_since_last. return dp[0][L][distance_since_last] # For example, suppose we call: if __name__ == '__main__': # A sample graph (list of numbers) sample_graph = [3, 1, 4, 1, 5, 9] lines = 3 init_distance = 0 result = solve_iterative(sample_graph, lines, init_distance) print("Result:", result) ------------------------------------------------------------ Explanation of the iterative code: 1. We first set up the 3-dimensional dp table. The three dimensions are: - i: the “position” (0 ≤ i ≤ n) in the graph (which corresponds to the current shortened list “graph[i:]” in the recursive version). - k: the number of lines left that we can take (0 ≤ k ≤ lines_left). - d: the current distance_since_last (values 0 through 10). 2. For the base case (i == n): - If k == 0, then we’ve successfully finished (cost 0, no further decisions). - If k > 0 it is impossible to take more lines (we assign cost INF = 1e9). 3. We then iterate backwards from i = n – 1 down to 0. For each state (i, k, d) we consider: - Option 1: Skip the current element (only allowed if d < 10). In that case the cost is whatever cost we obtain in state (i+1, k, d+1). - Option 2: Take the current element (only allowed if k > 0). This costs graph[i] plus a penalty (d – 8)² plus the cost in state (i+1, k – 1, 0). We also record that we took a line at this “position” by appending (n – i) to the list. 4. We take the minimum (by cost) of those two options and store the pair (cost, how). 5. Finally, the answer is dp[0][lines_left][distance_since_last] which exactly corresponds to the initial call in the recursive version. This iterative solution does exactly the same work as the recursive one but “unrolls” the recursion into an explicit three‐loop (over the length of the graph, the available lines, and the distance counter) and thus avoids the overhead of recursive calls and list slicing. The “cubic work” is made explicit by the three nested loops (even though the third loop is over only 11 possible values). Both functions will return a tuple (cost, how) where cost is the minimized total cost and how is the list (built in reverse order relative to the remaining length of the graph) that records where the “lines” were taken. This is our complete answer.
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #!/usr/bin/env python3 def solve_iterative(graph, lines_left, distance_since_last): # Define a very large cost for impossible cases. INF = 1e9 n = len(graph) L = lines_left # maximum number of lines we are allowed to take # We use a 3D DP table. # dp[i][k][d] = (cost, how) # where: # i in [0, n] indicates that we are at position i in the graph (so the next element is graph[i]) # k in [0, L] is the number of lines left to take # d in [0, 10] is the current distance_since_last (we never use values >10) # # In the recursion, note that if we take an element from graph, # we append len(graph) (i.e. the number of remaining items) to the list. # In our state, len(graph) is n - i. # Create and initialize dp as a 3D list with dimensions (n+1) x (L+1) x 11. dp = [ [ [(INF, []) for _ in range(11)] for _ in range(L+1) ] for _ in range(n+1) ] # Base case: when i == n (i.e. we have consumed the entire graph) for k in range(L+1): for d in range(11): if k == 0: dp[n][k][d] = (0, []) else: dp[n][k][d] = (INF, []) # Another necessary condition: if (n - i) < k then it is impossible to take k lines. # We incorporate that check in our loop. # Fill the table backwards: from i = n-1 downto 0. for i in range(n-1, -1, -1): for k in range(L+1): # If there are fewer items left than lines to take, this state is invalid. if (n - i) < k: for d in range(11): dp[i][k][d] = (INF, []) continue # skip to the next i for d in range(11): best_cost = INF best_how = [] # Option 1: Do not take the current line. # We may do this only if distance_since_last is less than 10. if d < 10: cost1, how1 = dp[i+1][k][d+1] if cost1 < best_cost: best_cost = cost1 best_how = how1 # Option 2: Take the current line. if k > 0: cost2, how2 = dp[i+1][k-1][0] # When taking the current line we incur a cost of: # graph[i] + (d - 8)^2 candidate_cost = cost2 + graph[i] + (d - 8) ** 2 if candidate_cost < best_cost: best_cost = candidate_cost # The original recursive code did: # how + [len(graph)] # and note that at state i, len(graph)==n-i. best_how = how2 + [n - i] dp[i][k][d] = (best_cost, best_how) # Finally, we return the answer corresponding to the original call: # i = 0, with the given lines_left (L) and the given distance_since_last. return dp[0][L][distance_since_last] |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | #!/usr/bin/env python3 def solve_iterative(graph, lines_left, distance_since_last): # Define a very large cost for impossible cases. INF = 1e9 n = len(graph) L = lines_left # maximum number of lines we are allowed to take # We use a 3D DP table. # dp[i][k][d] = (cost, how) # where: # i in [0, n] indicates that we are at position i in the graph (so the next element is graph[i]) # k in [0, L] is the number of lines left to take # d in [0, 10] is the current distance_since_last (we never use values >10) # # In the recursion, note that if we take an element from graph, # we append len(graph) (i.e. the number of remaining items) to the list. # In our state, len(graph) is n - i. # Create and initialize dp as a 3D list with dimensions (n+1) x (L+1) x 11. dp = [ [ [(INF, []) for _ in range(11)] for _ in range(L+1) ] for _ in range(n+1) ] # Base case: when i == n (i.e. we have consumed the entire graph) for k in range(L+1): for d in range(11): if k == 0: dp[n][k][d] = (0, []) else: dp[n][k][d] = (INF, []) # Another necessary condition: if (n - i) < k then it is impossible to take k lines. # We incorporate that check in our loop. # Fill the table backwards: from i = n-1 downto 0. for i in range(n-1, -1, -1): for k in range(L+1): # If there are fewer items left than lines to take, this state is invalid. if (n - i) < k: for d in range(11): dp[i][k][d] = (INF, []) continue # skip to the next i for d in range(11): best_cost = INF best_how = [] # Option 1: Do not take the current line. # We may do this only if distance_since_last is less than 10. if d < 10: cost1, how1 = dp[i+1][k][d+1] if cost1 < best_cost: best_cost = cost1 best_how = how1 # Option 2: Take the current line. if k > 0: cost2, how2 = dp[i+1][k-1][0] # When taking the current line we incur a cost of: # graph[i] + (d - 8)^2 candidate_cost = cost2 + graph[i] + (d - 8) ** 2 if candidate_cost < best_cost: best_cost = candidate_cost # The original recursive code did: # how + [len(graph)] # and note that at state i, len(graph)==n-i. best_how = how2 + [n - i] dp[i][k][d] = (best_cost, best_how) # Finally, we return the answer corresponding to the original call: # i = 0, with the given lines_left (L) and the given distance_since_last. return dp[0][L][distance_since_last] answer = 0 import random mylist = list(range(100)) random.shuffle(mylist) from functools import lru_cache @lru_cache(maxsize=None) def my_solve_dp(graph, lines_left, distance_since_last): if len(graph) < lines_left: return 1e9, [] if lines_left == 0 and len(graph) == 0: return 0, [] # option 1: don't take the line value = (1e9, []) if distance_since_last < 10: value = min(value, my_solve_dp(graph[1:], lines_left, distance_since_last+1)) # option 2: take the line if lines_left > 0: sub, how = my_solve_dp(graph[1:], lines_left-1, 0) sub += graph[0] + (distance_since_last-8)**2 value = min(value, (sub, how + [len(graph)])) return value answer = solve_iterative(tuple(mylist), len(mylist)//8, 4) expected = my_solve_dp(tuple(mylist), len(mylist)//8, 4) assert answer == expected, f'Wrong answer; got {answer} instead of {expected}' print('All tests passed') |
All tests passed
Testing if the previous output contains the string All tests passed: True
Resulting in output: True