The**time it takes to move** from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers.**Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order**. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave -**you can move to and from the bulkhead to pick up additional bunnies if time permits**.

In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is**each time a path is traversed, the same amount of time is used or added**.

In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and**add time back to the clock**. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it**triggers the bulkhead to reopen**. Therefore, it might be possible to walk in a circle and keep gaining time: that is**each time a path is traversed, the same amount of time is used or added**.

Write a function of the form solution(times, time_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size,**return the set of bunnies with the lowest prisoner IDs (as indexes) in sorted order**. The bunnies are represented as a sorted list by prisoner ID, with the**first bunny being 0**.There are at most**5 bunnies**, and time_limit is a non-negative integer that is at most***999**.

Time Limit: 1

Answer: Bunnies 1, 2

Start End Delta Time Status

- 0 - 1 // Bulkhead initially open

Time Limit: 3

Answer: Bunnies 0, 1

Start End Delta Time Status

- 0 - 3 Bulkhead is open

0 1 2 2 Rescuebunny one

1 2 1 1 Rescuebunny two

2 4 0 0 Exit. We can go directly to 4 as it takes 1 time to open the bulkhead.

0 1 2 2 RescueFirst Bunny.

1 2 1 1 RescueSecond Bunny.

2 4 0 0 Exit.

If we wanted to rescue third bunny then we needed to add more time, which is slows the process, so we skip them as the requirement to the problem was to be fast! But there could have been another solution to rescue 0,3 0r 1,3 bunny as well as every rescure needs exactly same time.

-[ ] Understand and implement the finding number 3.

-[ ] Reviewhttps://iq.opengenus.org/blossom-maximum-matching-algorithm

-[ ] Reviewhttps://www.informit.com/articles/article.aspx?p=169575&seqNum=8

Went back to the problem and update the description to the given examples above.

Adjacency Matrix is a n-by-n matrix with A uv = 1 if (u, v) is an edge.

- Two representations of each edge.

- Space proportional to n 2 .

- Checking if (u, v) is an edge takes Θ(1) time.

- Identifying all edges takes Θ(n 2 ) time.

Adjacency Lists is a node-indexed array of lists.

- Two representations of each edge.

- Space is Θ(m + n).

- Checking if (u, v) is an edge takes O(degree(u)) time. degree = number of neighbors of u.

- Identifying all edges takes Θ(m + n) time.

Cycles: A cycle is a path v 1 , v 2 , ..., v k in which v 1 = v k and k ≥ 2.

Trees: An undirected graph is a tree if it is connected and does not contain a cycle.

Shortest path problem. Given two nodes s and t, what is the length of a shortest path between s and t?

**In our problem we intend to return the nodes which can be reached with the time we have.**

Breadth-first search: Explore outward from s in all possible directions, adding nodes one “layer” L at a time.

BFS algorithm.

- L0 = {s}

- L1 = all neighbors of L0

- L2 = all nodes that do not belong to L0 or L1 , and that have an edge to a node in L1

- Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li

BFS runs in O(m + n) time if the graph is given by an adjacency representation.

Connected component. Find all nodes reachable from a point.

**This kind of represents our problem** - Which nodes can can we reach from start with the limited time constraints.

- Directed reachability. Given a node s, find all nodes reachable from s.

- Directed s↝t shortest path problem. Given two nodes s and t, what is the length of a shortest path from s to t?

- Graph search. BFS extends naturally to directed graphs.

- Def. Nodes u and v are mutually reachable if there is both a path from u to v and also a path from v to u.

- Def. A graph is strongly connected if every pair of nodes is mutually reachable.

- Def. A DAG is a directed graph that contains no directed cycles.

- Def. A topological order of a directed graph G = (V, E) is an ordering of its nodes as v 1 , v 2 , ..., v n so that for every edge (v i , v j ) we have i < j.

Def. A path is a sequence of edges which connects a sequence of nodes.

Def. A cycle is a path with no repeated nodes or edges other than the starting and ending nodes.

Def. Given a connected, undirected graph G = (V, E) with edge costs ce, a minimum spanning tree (V, T ) is a spanning tree of G such that the sum of the edge costs in T is minimized.

In graph theory, an arborescence is a directed graph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph. Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist. Every arborescence is a directed acyclic graph, but not every DAG is an arborescence. An arborescence can equivalently be defined as a rooted digraph in which the path from the root to any other vertex is unique.

- Greed: Process the input in some order, myopically making irrevocable decisions.

- Divide-and-conquer: Break up a problem into independent subproblems; Solve each subproblem; Combine solutions to subproblems to form solutionto original problem.

- Dynamic programming: Break up a problem into a series of overlapping subproblems; Combine solutions to smaller subproblems to form solution to large subproblem.Dynamic programming is a fancy name for caching intermediate results in a table for later reuse.

INF=float('inf')

defBellmanFord(edges,source,time):

cost= [time]*N

cost[source]=0

for_inrange(N-1):

for (u,v,w)inedges:

ifcost[u]!=timeandcost[u]+w<cost[v]:

cost[v]=cost[u]+w

for (u,v,w)inedges:

ifcost[u]!=timeandcost[u]+w<cost[v]:

defMakeEdge(adjMatrix):

edges= []

forvinrange(N):

foruinrange(N):

ifadjMatrix[v][u]andadjMatrix[v][u]!=time:

edges.append((v,u,adjMatrix[v][u]))

if__name__=='__main__':

adjMatrix= [

[0,1,1,1,1],

[1,0,1,1,1],

[1,1,0,1,1],

[1,1,1,0,1],

[1,1,1,1,0]

]

edges=MakeEdge(adjMatrix)

foriinrange(N):

ifBellmanFord(edges,i,time):

print("Negative Weight Cycle Found!!")

defconvert_to_path(perm):

perm=list(perm)

perm= [0]+perm+ [-1]

path=list()

foriinrange(1,len(perm)):

path.append((perm[i-1],perm[i]))

defsolution(time,time_limit):

rows=len(time)

path=convert_to_path(perm)

forstart,endinpath:

total_time+=time[start][end]

iftotal_time<=time_limit:

returnsorted(list(i-1foriinperm))

defconvert_to_path(perm):

perm=list(perm)

perm= [0]+perm+ [-1]

path=list()

foriinrange(1,len(perm)):

path.append((perm[i-1],perm[i]))

classTestSolution(unittest.TestCase):

cases= [

[

[[0,1,1,1,1],

[1,0,1,1,1],

[1,1,0,1,1],

[1,1,1,0,1],

[1,1,1,1,0]],

[3],

[[0,1]]

],

[

[[0,2,2,2,-1],

[[1,2]]

],

[

[

[0,1,1,1,1,1,1],

[1,0,1,1,1,1,1],

[1,1,0,1,1,1,1],

[1,1,1,0,1,1,1],

[1,1,1,1,0,1,1],

[1,1,1,1,1,0,1],

[1,1,1,1,1,1,0]

],[3],[[0,1]]

],

[

[

[0,3,1,8,1],

[2,0,9,4,2],

[-5,1,0,3,-2],

[3,2,1,0,1],

[1,3,2,0,0]

], [10], [[0,1,2]]

]

]

deftest_solution(self):

p=itertools.permutations(a)

forjinlist(p):

print(j)

print([xforxinrange(5)])

forxinself.cases[:]:

got=solution(x[0],x[1][0] )

self.assertEqual(got,x[2][0] )