Escape Pods

You've blown up the LAMBCHOP doomsday device and broken the bunnies out of Lambda's prison - and now you need to escape from the space station as quickly and as orderly as possible! The bunnies have all gathered in various locations throughout the station, and need to make their way towards the seemingly endless amount of escape pods positioned in other parts of the station. You need to get the numerous bunnies through the various rooms to the escape pods. Unfortunately, the corridors between the rooms can only fit so many bunnies at a time. What's more, many of the corridors were resized to accommodate the LAMBCHOP, so they vary in how many bunnies can move through them at a time.

You've blown up the LAMBCHOP doomsday device and broken the bunnies out of Lambda's prison - and now you need to escape from the space station as quickly and as orderly as possible! The bunnies have all gathered in various locations throughout the station, and need to make their way towards the seemingly endless amount of escape pods positioned in other parts of the station. You need to get the numerous bunnies through the various rooms to the escape pods. Unfortunately, the corridors between the rooms can only fit so many bunnies at a time. What's more, many of the corridors were resized to accommodate the LAMBCHOP, so they vary in how many bunnies can move through them at a time.

Given the starting room numbers of the groups of bunnies, the room numbers of the escape pods, and how many bunnies can fit through at a time in each direction of every corridor in between, figure out how many bunnies can safely make it to the escape pods at a time at peak.

For example, if you have:

Entrances =[0, 1]

Exits =[4, 5]

-[Network Flow Algorithms Starting Here](https://www.youtube.com/watch?v=LdOnanfc5TM&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=33&t=3s)

-[Network Flow Algorithms Starting Here](https://www.youtube.com/watch?v=LdOnanfc5TM&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=33)

-13. Incremental Improvement: Max Flow, Min Cut](https://www.youtube.com/watch?v=VYZGlgzr_As)

- Actual Complexity of Max Flow Algorithmshttps://codeforces.com/blog/entry/52714

Functional example:

return solveWithFordFulkerson(transform(entrances, exits, path));

}

}

From further research, a more efficient algorithm - Dinic's algorithm selected.

packagecom.williamfiset.algorithms.graphtheory.networkflow.examples;

import staticjava.lang.Math.min;

importjava.util.*;

publicclassDinicsExample {

privatestaticclassEdge {

publicint from, to;

publicEdge residual;

publiclong flow;

publicfinallong capacity;

publicEdge(intfrom,intto,longcapacity) {

this.from= from;

this.to= to;

this.capacity= capacity;

}

publicbooleanisResidual() {

return capacity==0;

}

publiclongremainingCapacity() {

return capacity- flow;

}

publicvoidaugment(longbottleNeck) {

flow+= bottleNeck;

residual.flow-= bottleNeck;

}

publicStringtoString(ints,intt) {

String u= (from== s)?"s": ((from== t)?"t":String.valueOf(from));

String v= (to== s)?"s": ((to== t)?"t":String.valueOf(to));

returnString.format(

"Edge %s -> %s | flow = %3d | capacity = %3d | is residual: %s",

u, v, flow, capacity, isResidual());

}

}

privateabstractstaticclassNetworkFlowSolverBase {

staticfinallongINF=Long.MAX_VALUE/2;

finalint n, s, t;

protectedboolean solved;

protectedlong maxFlow;

protectedList<Edge>[] graph;

publicNetworkFlowSolverBase(intn,ints,intt) {

this.n= n;

this.s= s;

this.t= t;

initializeEmptyFlowGraph();

}

@SuppressWarnings("unchecked")

privatevoidinitializeEmptyFlowGraph() {

graph=newList[n];

for (int i=0; i< n; i++) graph[i]=newArrayList<Edge>();

}

publicvoidaddEdge(intfrom,intto,longcapacity) {

if (capacity<=0)thrownewIllegalArgumentException("Forward edge capacity <= 0");

Edge e1=newEdge(from, to, capacity);

Edge e2=newEdge(to, from,0);

e1.residual= e2;

e2.residual= e1;

graph[from].add(e1);

graph[to].add(e2);

}

publicList<Edge>[]getGraph() {

execute();

return graph;

}

publiclonggetMaxFlow() {

execute();

return maxFlow;

}

privatevoidexecute() {

if (solved)return;

solved=true;

solve();

}

publicabstractvoidsolve();

}

privatestaticclassDinicsSolverextendsNetworkFlowSolverBase {

privateint[] level;

publicDinicsSolver(intn,ints,intt) {

super(n, s, t);

level=newint[n];

}

publicvoidsolve() {

int[] next=newint[n];

while (bfs()) {

Arrays.fill(next,0);

for (long f= dfs(s, next,INF); f!=0; f= dfs(s, next,INF)) {

maxFlow+= f;

}

}

}

privatebooleanbfs() {

Arrays.fill(level,-1);

Deque<Integer> q=newArrayDeque<>(n);

q.offer(s);

level[s]=0;

while (!q.isEmpty()) {

int node= q.poll();

for (Edge edge: graph[node]) {

long cap= edge.remainingCapacity();

if (cap>0&& level[edge.to]==-1) {

level[edge.to]= level[node]+1;

q.offer(edge.to);

}

}

}

return level[t]!=-1;

}

privatelongdfs(intat,int[]next,longflow) {

if (at== t)return flow;

finalint numEdges= graph[at].size();

for (; next[at]< numEdges; next[at]++) {

Edge edge= graph[at].get(next[at]);

long cap= edge.remainingCapacity();

if (cap>0&& level[edge.to]== level[at]+1) {

long bottleNeck= dfs(edge.to, next, min(flow, cap));

if (bottleNeck>0) {

edge.augment(bottleNeck);

return bottleNeck;

}

}

}

return0;

}

}

publicstaticvoidmain(String[]args) {

int n=11;

int s= n-1;

int t= n-2;

NetworkFlowSolverBase solver;

solver=newDinicsSolver(n, s, t);

solver.addEdge(s,0,5);

solver.addEdge(s,1,10);

solver.addEdge(s,2,15);

solver.addEdge(0,3,10);

solver.addEdge(1,0,15);

solver.addEdge(1,4,20);

solver.addEdge(2,5,25);

solver.addEdge(3,4,25);

solver.addEdge(3,6,10);

solver.addEdge(4,2,5);

solver.addEdge(4,7,30);

solver.addEdge(5,7,20);

solver.addEdge(5,8,10);

solver.addEdge(7,8,15);

solver.addEdge(6, t,5);

solver.addEdge(7, t,15);

solver.addEdge(8, t,10);

System.out.printf("Maximum flow: %d\n", solver.getMaxFlow());

}

}

The pain point then was to use understand the algorithm to make it usable.

The problem was to convert the adjacent graph into a graph with weighted

edges. The first solution did not do that and the concept of extra source

and sink nodes did not exits. Hence, to realize how to map the ends to

those end required more analysis.

Then, from going through the videos again and reviewing, it made more sense.

The source and sink could be any indexes as along as entrances were directed

from source and sink from the exits.

Another realization that was made was that the adjacent matrix with value 0

did not need to be converted into an edge. Only those with some value greater

than 0 was transformed as edges of the graph.

-[ ]https://apenwarr.ca/log/20201227 System design

-[ ]https://increment.com/remote/committing-to-collaboration-version-control |https://increment.com/remote

-[ ] Fast polynomial multiplication for programming contests (Java)https://www.davideisenstat.com/simplertimes

-[ ]https://graphics.stanford.edu/~seander/bithacks.html |https://github.com/gibsjose/BitHacks

-[ ]https://www.cs.cmu.edu/~15451-f18/lectures Download

The implementation was slightly modified as my implementation.