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

Commit41740f1

Browse files
committed
Started Google code challenge level 4 challenge 2.
1 parentd1ecd86 commit41740f1

File tree

8 files changed

+364
-125
lines changed

8 files changed

+364
-125
lines changed

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

Lines changed: 125 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -68,6 +68,11 @@ Use verify [file] to test your solution and see how it does. When you are finish
6868

6969
#Solution
7070

71+
###Primary Resources
72+
-https://algs4.cs.princeton.edu/44sp
73+
-https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/06DynamicProgrammingII.pdf
74+
75+
7176
##First Analysis
7277

7378
###Provided Case 1: Time Added Back
@@ -622,7 +627,11 @@ time each time one is added.
622627
[8, 2, 2, 0, 0],
623628
[8, 2, 1, 1, 0]],
624629

625-
-[ ] Need to check with this theory.
630+
-[X] Need to check with this theory.
631+
This theory also does not work as from theory -
632+
https://algs4.cs.princeton.edu/44sp/
633+
https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/06DynamicProgrammingII.pdf:
634+
`Reweighting. Adding a constant to every edge length does not necessarily make Dijkstra’s algorithm produce shortest paths.`
626635

627636

628637
####More Theory
@@ -643,15 +652,6 @@ Summary:
643652
→ Johnson’s Algorithm
644653

645654

646-
Updated Algorithm
647-
2. Check if the time we have would be enough save a bunny that requires the same amount of time.
648-
3. If No, Check if there is a way to increase/add more time to save a bunny.
649-
4.3. If Yes, add time, and save the bunny.
650-
5.3. If No, return the number of bunnies saved.
651-
6. If Yes, Check if by saving that bunny we would still have more time to keep the Bulkhead.
652-
653-
654-
655655
https://medium.com/cantors-paradise/dijkstras-shortest-path-algorithm-in-python-d955744c7064
656656
http://theory.stanford.edu/~amitp/GameProgramming/
657657
https://www.geeksforgeeks.org/a-search-algorithm
@@ -843,8 +843,8 @@ def BellmanFord(edges, source, time, N, last):
843843

844844
```
845845

846-
Then the next idea was to use all the computed paths by
847-
completed Bellman-Ford.
846+
Then the next idea was to use all the computed
847+
paths bycompleted Bellman-Ford.
848848

849849
```python
850850

@@ -871,6 +871,119 @@ So I choose to use existing solution for submission.
871871
I choose Python as the programming language as the solutions and examples
872872
were better and more, and I use it as tooling language to validate ideas.
873873

874+
###Further analysis after submission
875+
The submitted solution was third-party and I wanted to find better
876+
optimium solution.
877+
878+
#####First Example:
879+
```python
880+
adjacencyMatrix= [
881+
[0,2,2,2,-1],# 0 = Start
882+
[9,0,2,2,-1],# 1 = Bunny 0
883+
[9,3,0,2,-1],# 2 = Bunny 1
884+
[9,3,2,0,-1],# 3 = Bunny 2
885+
[9,3,2,2,0],# 4 = Bulkhead
886+
]
887+
time=1
888+
```
889+
890+
The shortest paths are from 0, 1, 2 and 3 are:
891+
[0, 2, 1, 1, -1],[8, 0, 1, 1, -1],[8, 2, 0, 1, -1],[8, 2, 1, 0, -1]
892+
893+
Rough algorithm could be:
894+
895+
Find the miminum value.
896+
If there are more than one, put them in a queue, i.e. Here there is two 1's,
897+
Select the minimum value.
898+
Reduce the total time provided.
899+
900+
Move to next stage who's minimum value was selected.
901+
Select the next minimum value excluding the previous stage.
902+
903+
Check if the available time is enough to reach next stage.
904+
The remaining time must be greater than or equal to shortest time it takes to reach next level.
905+
906+
Steps taken based on the algorithm based on the shortest path:
907+
908+
Previous vertices pv = null
909+
Remaining time rt = 2
910+
911+
Step 1[0, 2, 1, 1, -1]
912+
Remove first and last index from the list, say AL, =[2, 1, 1]
913+
Sort =[1,1,2]
914+
Add sorted list to queue
915+
Dequeue: Choose the first number from the sorted list
916+
The next path np = Select the first index in AL = 2
917+
rt = 2 - 1 = 1
918+
Is rt - np > 0, go to next step.
919+
920+
921+
Step 2[8, 2, 0, 1, -1]
922+
Previous vertices:0
923+
Remove first, last index, self, and previous vertices index AL =[2, 1]
924+
This filtration might cause issue while selecting as the index are removed
925+
But we need it for sorting
926+
Sort =[1, 2]
927+
Add sorted list to queue
928+
Choose the first number from the sorted list
929+
The next path = Select the index in the shortest path whose value is dequeued
930+
[x, x, x, 1, x] = 3, the only option remaining
931+
Probable problem:
932+
rt = 1 - 1 = 0
933+
Is rt - np > 0, go to next step. No
934+
935+
936+
#####Second Example:
937+
Adjacency Matrix =[[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]]
938+
Time = 3
939+
Shortest Path sp =[[0, 1, 1, 1, 1],[1, 0, 1, 1, 1],[1, 1, 0, 1, 1],[1, 1, 1, 0, 1]]
940+
941+
942+
Previous vertices pv = null
943+
Remaining time rt = 3
944+
list = sp[0] =[0, 1, 1, 1, 1]
945+
946+
while i > 0:
947+
948+
Step 1[0, 1, 1, 1, 1]
949+
pv = null
950+
Remove first and last index from the list, say AL, =[1, 1, 1]
951+
Sort =[1,1,1]
952+
Add sorted list to queue
953+
Dequeue: Choose the first number from the sorted list = 1
954+
Choose the first index whose value is 1.
955+
nextIndex = sp[1]
956+
rt = 3 - 1 = 2
957+
Is rt - np > 0,
958+
Go to next step: nextIndex
959+
960+
961+
Step 2[1, 0, 1, 1, 1]
962+
pv = 0
963+
Remove first and last index from the list, say AL, =[1, 1, 1]
964+
Sort =[1,1,1]
965+
Add sorted list to queue
966+
Dequeue: Choose the first number from the sorted list = 1
967+
Choose the first index whose value is 1
968+
nextIndex = sp[1]
969+
rt = 2 - 1 = 1
970+
Is rt - np > 0,
971+
Go to next step: nextIndex
972+
973+
Step 3[1, 1, 0, 1, 1]
974+
pv = 1
975+
Remove first, last and previous index from the list, say AL, =[1]
976+
Sort =[1] // No need to sort if there's one one item
977+
Add sorted list to queue // No need
978+
Dequeue: Choose the first number from the sorted list = 1
979+
Choose the first index whose value is 1
980+
nextIndex = sp[1]
981+
rt = 2 - 1 = 1
982+
Is rt - np > 0,
983+
Go to next step: nextIndex
984+
985+
986+
874987

875988
######Tabs On Brower
876989
-[ ]https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/
434 Bytes
Binary file not shown.

‎src/google/Level4/Challenge1/bfs.py‎

Lines changed: 15 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -51,18 +51,20 @@ def BFS(self, s):
5151

5252
# Create a graph given in
5353
# the above diagram
54-
g=Graph()
55-
g.addEdge(0,1)
56-
g.addEdge(0,2)
57-
g.addEdge(1,2)
58-
g.addEdge(2,0)
59-
g.addEdge(2,3)
60-
g.addEdge(3,3)
61-
62-
print(g.graph)
63-
64-
print ("Following is Breadth First Traversal"
65-
" (starting from vertex 2)")
66-
g.BFS(0)
54+
g=Graph()
55+
56+
g.addEdge(1,0)
57+
g.addEdge(0,1)
58+
g.addEdge(0,2)
59+
g.addEdge(1,2)
60+
g.addEdge(2,0)
61+
g.addEdge(2,3)
62+
g.addEdge(3,3)
63+
64+
print(g.graph)
65+
66+
print ("Following is Breadth First Traversal"
67+
" (starting from vertex 0)")
68+
g.BFS(0)
6769

6870
# This code is contributed by Neelam Yadav

‎src/google/Level4/Challenge1/dfs.py‎

Lines changed: 18 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -13,9 +13,10 @@ def addEdge(self,v, w): # to add an edge to graph
1313
self.adj[v].append(w)# Add w to v’s list.
1414

1515

16-
# prints all not yet visited vertices reachable from s
17-
defDFS(self,s):# prints all vertices in DFS manner from a given source.
18-
# Initially mark all verices as not visited
16+
# prints all not yet visited vertices reachable from s
17+
# prints all vertices in DFS manner from a given source.
18+
defDFS(self,s):
19+
# Initially mark all verices as not visited
1920
visited= [Falseforiinrange(self.V)]
2021

2122
# Create a stack for DFS
@@ -24,7 +25,7 @@ def DFS(self,s): # prints all vertices in DFS manner from a given source.
2425
# Push the current source node.
2526
stack.append(s)
2627

27-
while (len(stack)):
28+
while (len(stack)):
2829
# Pop a vertex from stack and print it
2930
s=stack[-1]
3031
stack.pop()
@@ -44,18 +45,17 @@ def DFS(self,s): # prints all vertices in DFS manner from a given source.
4445
stack.append(node)
4546

4647

47-
4848
# Driver program to test methods of graph class
49-
50-
g=Graph(7);# Total 5 vertices in graph
51-
g.addEdge(1,0);
52-
g.addEdge(0,2);
53-
g.addEdge(2,1);
54-
g.addEdge(0,3);
55-
g.addEdge(3,4);
56-
g.addEdge(1,4);
57-
g.addEdge(4,5);
58-
g.addEdge(5,6);
59-
60-
print("Following is Depth First Traversal")
61-
g.DFS(0)
49+
if__name__=='__main__':
50+
g=Graph(7);# Total 5 vertices in graph
51+
g.addEdge(1,0);
52+
g.addEdge(0,2);
53+
g.addEdge(2,1);
54+
g.addEdge(0,3);
55+
g.addEdge(3,4);
56+
g.addEdge(1,4);
57+
g.addEdge(4,5);
58+
g.addEdge(5,6);
59+
60+
print("Following is Depth First Traversal")
61+
g.DFS(0)

‎src/google/Level4/Challenge1/solution.py‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -18,11 +18,13 @@ def solution(time, timeLimit):
1818
return [iforiinrange(bunnies)]
1919

2020

21-
# return carryBunnies(time, timeLimit, bunnies)
21+
print(time)
22+
23+
returncarryBunnies(time,timeLimit,bunnies)
2224

2325
# Testing other solution if it works?
2426
# It works!
25-
returnbfs(time,rows,timeLimit)
27+
#return bfs(time, rows, timeLimit)
2628

2729

2830
defnegativeCycleExists(time,rows):
@@ -44,8 +46,7 @@ def negativeCycleExists(time, rows):
4446
# Skip early if negative cycle is detected
4547
iftime[i][i]<0:
4648
returnTrue
47-
48-
49+
4950
defmakePath(bunniesList):
5051
'''Returns a list of list as path from 0 to -1 in the same order in the parameter.
5152

0 commit comments

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