Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitfd1dedf

Browse files
committed
Google code challenge solution.
Solved the problem with FordFulkerson and Dinic`s algorithms.Finding if other more efficient solutions can be found.
1 parent41740f1 commitfd1dedf

File tree

4 files changed

+566
-36
lines changed

4 files changed

+566
-36
lines changed

‎src/google/Level4/Challenge1/README.md‎

Lines changed: 0 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -981,27 +981,3 @@ Dequeue: Choose the first number from the sorted list = 1
981981
rt = 2 - 1 = 1
982982
Is rt - np > 0,
983983
Go to next step: nextIndex
984-
985-
986-
987-
988-
######Tabs On Brower
989-
-[ ]https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/
990-
-[ ]https://docs.ioin.in/writeup/www.auxy.xyz/_tutorial_Webkit_Exp_Tutorial_/index.html
991-
-[ ]https://tech.ebayinc.com/engineering/ou-online-analytical-processing/
992-
-[ ]https://www.linkedin.com/pulse/dos-donts-while-preparing-amazon-machine-learning-specialty-semaan/
993-
-[ ]https://www.infoq.com/podcasts/software-architecture-team-topologies
994-
-[ ]https://medium.com/awsblogs/ci-cd-with-kubernetes-3c29e8073c38
995-
-[ ]https://www.infoq.com/presentations/hotspot-graalvm-code-execution
996-
-[ ]https://medium.com/better-programming/modern-day-architecture-design-patterns-for-software-professionals-9056ee1ed977
997-
-[ ]https://www.linkedin.com/learning/cobol-essential-training/cobol-is-alive-and-well
998-
-[ ]https://mailchi.mp/5125b7b5305e/18-dear-architects
999-
-[ ]https://advocacy.vmware.com/member/post/1d9aff34-0610-42ed-9b90-21233cabc9ae?uc=113877&g=df4af070-be59-44be-b7f0-ea2387c55f98&f=2433965
1000-
-[ ]https://minimatech.org/from-postgresql-to-neo4j
1001-
-[ ]https://www.siddharthsarda.com/p/developer-progression-as-a-function
1002-
-[ ]https://www.infoworld.com/article/3563829/jamstack-the-static-website-revolution-upending-web-development.html
1003-
-[ ]https://apenwarr.ca/log/20201227 System design
1004-
-[ ]https://www.infoq.com/articles/database-audit-system-kafka
1005-
-[ ]https://increment.com/remote/committing-to-collaboration-version-control |https://increment.com/remote
1006-
-[ ]https://medium.com/neotiv-gmbh/5-design-patterns-every-software-engineer-should-know-470c8b6c0b54
1007-
-[ ]https://chromeisbad.com
Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
packagegoogle.Level4.Challenge2;
2+
3+
importjava.util.List;
4+
importjava.util.Collections;
5+
importjava.util.ArrayList;
6+
importjava.util.ArrayDeque;
7+
importjava.util.Queue;
8+
importjava.util.Arrays;
9+
10+
/**
11+
* Solution implements FordFulkerson algorithm.
12+
*
13+
* Source: https://vitaminac.github.io/Google-Foobar-Escape-Pods
14+
*/
15+
publicclassFordFulkersonImplThirdparty {
16+
privatestaticfinalintINF =Integer.MAX_VALUE;
17+
18+
privatestaticint[][]transform(int[]sources,int[]sinks,int[][]network) {
19+
// transform to a equivalent single-source, single-sink flow network
20+
intlength =network.length;
21+
intnewLength =length +2;
22+
int[][]newNetwork =newint[newLength][newLength];
23+
24+
for (inti =0;i <length;i++) {
25+
for (intj =0;j <length;j++) {
26+
newNetwork[i +1][j +1] =network[i][j];
27+
}
28+
}
29+
30+
for (intentrance :sources) {
31+
newNetwork[0][entrance +1] =INF;
32+
}
33+
34+
for (intexit :sinks) {
35+
newNetwork[exit +1][newLength -1] =INF;
36+
}
37+
38+
returnnewNetwork;
39+
}
40+
41+
privatestaticList<Integer>bfs(int[][]residual_network) {
42+
// find a path from s to t that every (u, v) in p satisfies c_f(u, v) > 0
43+
int[]parents =newint[residual_network.length];
44+
Arrays.fill(parents, -1);
45+
Queue<Integer>queue =newArrayDeque<>();
46+
queue.add(0);
47+
intu;
48+
for (; !queue.isEmpty() &&parents[parents.length -1] == -1; ) {
49+
u =queue.remove();
50+
for (intv =0;v <parents.length;v++) {
51+
if (residual_network[u][v] >0 &&parents[v] == -1) {
52+
queue.add(v);
53+
parents[v] =u;
54+
}
55+
}
56+
}
57+
List<Integer>path =newArrayList<>();
58+
u =parents[parents.length -1];
59+
while (u !=0) {
60+
if (u == -1)returnnull;
61+
path.add(u);
62+
u =parents[u];
63+
}
64+
Collections.reverse(path);
65+
returnpath;
66+
}
67+
68+
privatestaticintsolveWithFordFulkerson(int[][]residual_network) {
69+
70+
intmax_flow =0;
71+
List<Integer>path;
72+
while ((path =bfs(residual_network)) !=null) {
73+
// calculate residual capacity c_f(p)
74+
intresidual_capacity =INF;
75+
intu =0;
76+
for (intv :path) {
77+
residual_capacity =Math.min(residual_capacity,residual_network[u][v]);
78+
u =v;
79+
}
80+
// increment max flow
81+
max_flow +=residual_capacity;
82+
u =0;
83+
// update residual network
84+
for (intv :path) {
85+
residual_network[u][v] -=residual_capacity;
86+
residual_network[v][u] +=residual_capacity;
87+
u =v;
88+
}
89+
}
90+
returnmax_flow;
91+
}
92+
93+
publicstaticintsolution(int[]entrances,int[]exits,int[][]path) {
94+
returnsolveWithFordFulkerson(transform(entrances,exits,path));
95+
}
96+
97+
publicstaticvoidmain(String[]args) {
98+
int[]entrances =newint[]{0,1};
99+
int[]exits =newint[]{4,5};
100+
int[][]paths =newint[][]{
101+
{0,0,4,6,0,0},
102+
{0,0,5,2,0,0},
103+
{0,0,0,0,4,4},
104+
{0,0,0,0,6,6},
105+
{0,0,0,0,0,0},
106+
{0,0,0,0,0,0}
107+
};
108+
109+
System.out.print(solution(entrances,exits,paths));
110+
}
111+
}
112+

‎src/google/Level4/Challenge2/README.md‎

Lines changed: 186 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
#Problem
1+
es# Problem
22

33
Escape Pods
44
===========
@@ -67,10 +67,12 @@ Use verify [file] to test your solution and see how it does. When you are finish
6767

6868
#Solution
6969

70+
##Analysis
71+
###First Example
7072
For example, if you have:
71-
entrances =[0, 1]
72-
exits =[4, 5]
73-
path =[
73+
Entrances =[0, 1]
74+
Exits =[4, 5]
75+
Path =[
7476
0 1 2 3 4 5
7577
[0, 0, 4, 6, 0, 0], # Room 0: Bunnies
7678
[0, 0, 5, 2, 0, 0], # Room 1: Bunnies
@@ -82,7 +84,7 @@ path = [
8284
[0, 0, 0, 0, 0, 0], # Room 5: Escape pods
8385
]
8486

85-
Output:6
87+
Output:16
8688

8789
Then in each time step, the following might happen:
8890
0 sends 4/4 bunnies to 2
@@ -97,14 +99,186 @@ Then in each time step, the following might happen:
9799
3 sends 4/6 bunnies to 4
98100
3 sends 4/6 bunnies to 5
99101

102+
###Second Example
103+
Entrances =[0]
104+
Exists =[3]
105+
Path =[[0, 7, 0, 0],[0, 0 , 6, 0],[0, 0, 0, 8],[9, 0, 0, 0]]
106+
Output: 6
107+
108+
[0, 7, 0, 0] 0 # Room 0: Bunnies
109+
[0, 0, 6, 0] 1 # Room 1: Intermediate room
110+
[0, 0, 0, 8] 2 # Room 2: Intermediate room
111+
[9, 0, 0, 0] 3 # Room 3: Escape pods
100112

113+
0 sends 7/6 bunnies to 1
114+
1 sends 6/8 bunnies to 2
115+
2 sends 6/9 bunnies to 3
101116

102-
###Second Example
117+
The problem is related to finding the network flow.
103118

104-
[0],[3],[[0, 7, 0, 0],[0, 0 , 6, 0],[0, 0, 0, 8],[9, 0, 0, 0]]
105-
Output: 6
119+
###Theory
120+
-https://algs4.cs.princeton.edu/40graphs
121+
-[Network Flow Algorithms Starting Here](https://www.youtube.com/watch?v=LdOnanfc5TM&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=33&t=3s)
122+
-13. Incremental Improvement: Max Flow, Min Cut](https://www.youtube.com/watch?v=VYZGlgzr_As)
123+
-14.https://www.youtube.com/watch?v=8C_T4iTzPCU
124+
-https://www.youtube.com/watch?v=0CdxkgAjsDA
125+
-https://en.wikipedia.org/wiki/Flow_network
126+
-https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
127+
-https://en.wikipedia.org/wiki/Maximum_flow_problem
128+
-https://www.geeksforgeeks.org/cuts-and-network-flow
129+
-https://www.sciencedirect.com/science/article/pii/002200008590039X
130+
-https://stackoverflow.com/questions/36054690/how-to-use-dinics-algorithm-to-find-min-cut-edges-in-undireted-graph
131+
- Actual Complexity of Max Flow Algorithmshttps://codeforces.com/blog/entry/52714
132+
133+
Functional example:
134+
135+
```java
136+
137+
// Source: https://vitaminac.github.io/Google-Foobar-Escape-Pods/
138+
139+
importjava.util.List;
140+
importjava.util.Collections;
141+
importjava.util.ArrayList;
142+
importjava.util.ArrayDeque;
143+
importjava.util.Queue;
144+
importjava.util.Arrays;
145+
146+
147+
publicclassEscapePods {
148+
privatestaticfinalintINF=Integer.MAX_VALUE;
149+
150+
privatestaticint[][]transform(int[]sources,int[]sinks,int[][]network) {
151+
// transform to a equivalent single-source, single-sink flow network
152+
int length= network.length;
153+
int newLength= length+2;
154+
int[][] newNetwork=newint[newLength][newLength];
155+
for (int i=0; i< length; i++) {
156+
for (int j=0; j< length; j++) {
157+
newNetwork[i+1][j+1]= network[i][j];
158+
}
159+
}
160+
for (int entrance: sources) {
161+
newNetwork[0][entrance+1]=INF;
162+
}
163+
for (int exit: sinks) {
164+
newNetwork[exit+1][newLength-1]=INF;
165+
}
166+
return newNetwork;
167+
}
168+
169+
privatestaticList<Integer>bfs(int[][]residual_network) {
170+
// find a path from s to t that every (u, v) in p satisfies c_f(u, v) > 0
171+
int[] parents=newint[residual_network.length];
172+
Arrays.fill(parents,-1);
173+
Queue<Integer> queue=newArrayDeque<>();
174+
queue.add(0);
175+
int u;
176+
for (;!queue.isEmpty()&& parents[parents.length-1]==-1; ) {
177+
u= queue.remove();
178+
for (int v=0; v< parents.length; v++) {
179+
if (residual_network[u][v]>0&& parents[v]==-1) {
180+
queue.add(v);
181+
parents[v]= u;
182+
}
183+
}
184+
}
185+
List<Integer> path=newArrayList<>();
186+
u= parents[parents.length-1];
187+
while (u!=0) {
188+
if (u==-1)returnnull;
189+
path.add(u);
190+
u= parents[u];
191+
}
192+
Collections.reverse(path);
193+
return path;
194+
}
195+
196+
privatestaticintsolveWithFordFulkerson(int[][]residual_network) {
197+
// https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
198+
int max_flow=0;
199+
List<Integer> path;
200+
while ((path= bfs(residual_network))!=null) {
201+
// calculate residual capacity c_f(p)
202+
int residual_capacity=INF;
203+
int u=0;
204+
for (int v: path) {
205+
residual_capacity=Math.min(residual_capacity, residual_network[u][v]);
206+
u= v;
207+
}
208+
// increment max flow
209+
max_flow+= residual_capacity;
210+
u=0;
211+
// update residual network
212+
for (int v: path) {
213+
residual_network[u][v]-= residual_capacity;
214+
residual_network[v][u]+= residual_capacity;
215+
u= v;
216+
}
217+
}
218+
return max_flow;
219+
}
220+
221+
publicstaticintsolution(int[]entrances,int[]exits,int[][]path) {
222+
return solveWithFordFulkerson(transform(entrances, exits, path));
223+
}
224+
}
225+
```
226+
227+
###Understanding Dinic's
228+
-https://en.wikipedia.org/wiki/Dinic%27s_algorithm
229+
-https://www.youtube.com/watch?v=M6cm8UeeziI&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=42
230+
-https://github.com/ADJA/algos/blob/master/Graphs/Dinic.cpp
231+
-https://www.geeksforgeeks.org/dinics-algorithm-maximum-flow
232+
-https://www.hackerearth.com/practice/algorithms/graphs/maximum-flow/tutorial
233+
-https://www.geeksforgeeks.org/dinics-algorithm-maximum-flow
234+
-https://surajshetiya.github.io/Google-foobar/#round-4
235+
-https://github.com/nkapliev/google-foo.bar/blob/master/problems/4.2_escape_pods.py
236+
-http://www.cs.ust.hk/mjg_lib/Classes/COMP572_Fall07/Notes/index.htm
237+
238+
239+
240+
######Tabs On Brower
241+
-[ ]https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/
242+
-[ ]https://docs.ioin.in/writeup/www.auxy.xyz/_tutorial_Webkit_Exp_Tutorial_/index.html
243+
-[ ]https://tech.ebayinc.com/engineering/ou-online-analytical-processing/
244+
-[ ]https://www.linkedin.com/pulse/dos-donts-while-preparing-amazon-machine-learning-specialty-semaan/
245+
-[ ]https://www.infoq.com/podcasts/software-architecture-team-topologies
246+
-[ ]https://medium.com/awsblogs/ci-cd-with-kubernetes-3c29e8073c38
247+
-[ ]https://www.infoq.com/presentations/hotspot-graalvm-code-execution
248+
-[ ]https://medium.com/better-programming/modern-day-architecture-design-patterns-for-software-professionals-9056ee1ed977
249+
-[ ]https://www.linkedin.com/learning/cobol-essential-training/cobol-is-alive-and-well
250+
-[ ]https://mailchi.mp/5125b7b5305e/18-dear-architects
251+
-[ ]https://advocacy.vmware.com/member/post/1d9aff34-0610-42ed-9b90-21233cabc9ae?uc=113877&g=df4af070-be59-44be-b7f0-ea2387c55f98&f=2433965
252+
-[ ]https://minimatech.org/from-postgresql-to-neo4j
253+
-[ ]https://www.siddharthsarda.com/p/developer-progression-as-a-function
254+
-[ ]https://www.infoworld.com/article/3563829/jamstack-the-static-website-revolution-upending-web-development.html
255+
-[ ]https://apenwarr.ca/log/20201227 System design
256+
-[ ]https://www.infoq.com/articles/database-audit-system-kafka
257+
-[ ]https://increment.com/remote/committing-to-collaboration-version-control |https://increment.com/remote
258+
-[ ]https://medium.com/neotiv-gmbh/5-design-patterns-every-software-engineer-should-know-470c8b6c0b54
259+
-[ ]https://chromeisbad.com
260+
-[ ]https://vitaminac.github.io/Simple-Bootstrap-Linux-System/
261+
-[ ]https://hbr.org/2018/01/why-people-really-quit-their-jobs
262+
-[ ]https://play.picoctf.org/practice?category=6&page=1
263+
-[ ]https://architectelevator.com/architecture/famous-architects-sketch/
264+
-[ ]https://github.com/topjohnwu/Magisk
265+
-[ ]https://www.8bitmen.com/youtube-database-how-does-it-store-so-many-videos-without-running-out-of-storage-space/
266+
-[ ]https://github.com/facebook/zstd
267+
-[ ]https://github.com/topjohnwu/Magisk
268+
-[ ]https://tolisec.com/ssh-backdoor-botnet-with-research-infection-technique
269+
-[ ]https://www.infoq.com/articles/whats-the-next-step-for-data-management
270+
-[ ]https://opensource.com/
271+
-[ ]https://secret.club/2021/01/14/vbox-escape.html
272+
-[ ]https://www.linuxjournal.com/
273+
-[ ]https://www.weave.works/blog/the-gitops-pipeline
274+
-[ ]https://github.com/kubermatic/
275+
-[ ]https://github.com/open-telemetry/opentelemetry-go/contribute
276+
-[ ]https://github.com/SaturnsVoid/GoBot2
277+
-[ ]https://architectelevator.com/architecture/failure-doesnt-respect-abstraction/
278+
-[ ] Fast polynomial multiplication for programming contests (Java)https://www.davideisenstat.com/simplertimes
279+
-[ ]https://graphics.stanford.edu/~seander/bithacks.html |https://github.com/gibsjose/BitHacks
280+
-[ ]https://www.cs.cmu.edu/~15451-f18/lectures Download
281+
-[ ]https://www.vice.com/en/article/n7vqew/the-hacker-who-archived-parler-explains-how-she-did-it-and-what-comes-next
282+
-[ ]https://github.com/d0nk/parler-tricks
283+
-[ ]https://gist.github.com/Parler-Analysis/2c023fd2e053fba5bc85b09209f606eb
106284

107-
[0, 7, 0, 0] 0 Entrance/Bunny
108-
[0, 0, 6, 0] 1
109-
[0, 0, 0, 8] 2
110-
[9, 0, 0, 0] 3 Exit/Escape Pod

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp