Optimization of BFS for finding minimum distances between elements of a gridPrime factorization of a...
Checking for the existence of multiple directories
Does my logo design convey the right feelings for a University Student's Council?
Can pricing be copyrighted?
Quenching swords in dragon blood; why?
Why zero tolerance on nudity in space?
Would a National Army of mercenaries be a feasible idea?
dirname appears not to work with xargs
Can we use the stored gravitational potential energy of a building to produce power?
Reference on complex cobordism
Removing fractions without a particular variable
Recrystallisation of dibenzylideneacetone
Can a hotel cancel a confirmed reservation?
On infinite combinatorics of ultrafilters
Strange Sign on Lab Door
How would an AI self awareness kill switch work?
Does Windows 10's telemetry include sending *.doc files if Word crashed?
Why did the villain in the first Men in Black movie care about Earth's Cockroaches?
What is the wife of a henpecked husband called?
Why don't I see the difference between two different files in insert mode in vim?
How to avoid being sexist when trying to employ someone to function in a very sexist environment?
"Spread across" vs "Spread through"
Is it safe to try charging my laptop with a USB-C PD charger that has less wattage than recommended?
How can I deal with a significant flaw I found in my previous supervisor’s paper?
Placing an adverb between a verb and an object?
Optimization of BFS for finding minimum distances between elements of a grid
Prime factorization of a numbergoogle foo.bar max path algorithm puzzle optimizationFind the longest rectilinear path in a matrix with descending entriesSplit list of integers at certain value efficientlyNavigating over a square spiralGenerating locations based on a power-law distribution of distance from their originUsing Pythagoras' Theorem to Check Point DistanceCode to implement the Jaro similarity for fuzzy matching stringsGoogle FooBar “Prepare The Bunnies Escape”2-opt algorithm for the Traveling Salesman and/or SRO
$begingroup$
This is from HackerRank - Travel Diaries. Given a grid of 0s,1s and 2s we need to find minimum distance of each 1 from 2 going through 1s only. (See 1 as land, 0 as ocean, 2 as food, need to find closest food for each tile of land where boats dont exists)
Here's my code
class Queue:
def __init__(self):
self.items = []
def empty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
try:
return self.items.pop()
except: return False
def size(self):
return len(self.items)
n,m = map(int,input().split(' '))
grid = list()
distances = list()
tocheck = Queue()
for i in range(n):
grid.append(list(map(int,input().split(' '))))
toapp = []
for j in range(m):
if grid[i][j] == 2:
toapp.append(0)
tocheck.enqueue((i,j))
else: toapp.append(m*n + (grid[i][j]-1)*m*n-1)
distances.append(toapp)
c = tocheck.dequeue()
while c:
x,y = c
for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
if 0<=i<n and 0<=j<m and grid[i][j] == 1:
if distances[x][y]+1 < distances[i][j]:
distances[i][j] = distances[x][y] + 1
grid[i][j] = 2
tocheck.enqueue((i,j))
c = tocheck.dequeue()
maxi = 0
for i in distances:
for j in i:
if j > maxi: maxi = j
if maxi == m*n-1: maxi = -1
print(maxi)
Explanation: Firstly, a pretty standard class implementing queues (Can't use builting module for some reason). n,m = #rows, #cols
Next, a grid containing values and a grid containing distances is created. If the value is 2, then distance matrix contains 0. If value is 1, then distance is m*n-1 (larger than maximum possible distance). If value is 0, then distance is -1 (not possible). Also, every location containing 2 is also stored separately in a queue
Main BFS part: Dequeue a location. Check if all Neighbours all valid enteries in matrix containing 1. If the distance of this neighobour is strictly greater than the current locations distance + 1, then update the neighbour's value to 2, distance to current distance + 1 and queue it. Repeat till queue is empty.
Any suggestions for optimization? (I realize my code has 0 comments but then again I didn't know I'd spend over 4 hours on this)
python performance
asked 8 mins ago
AnvitAnvit
1011
New contributor
Anvit is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
This is from HackerRank - Travel Diaries. Given a grid of 0s,1s and 2s we need to find minimum distance of each 1 from 2 going through 1s only. (See 1 as land, 0 as ocean, 2 as food, need to find closest food for each tile of land where boats dont exists)
Here's my code
class Queue:
def __init__(self):
self.items = []
def empty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
try:
return self.items.pop()
except: return False
def size(self):
return len(self.items)
n,m = map(int,input().split(' '))
grid = list()
distances = list()
tocheck = Queue()
for i in range(n):
grid.append(list(map(int,input().split(' '))))
toapp = []
for j in range(m):
if grid[i][j] == 2:
toapp.append(0)
tocheck.enqueue((i,j))
else: toapp.append(m*n + (grid[i][j]-1)*m*n-1)
distances.append(toapp)
c = tocheck.dequeue()
while c:
x,y = c
for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
if 0<=i<n and 0<=j<m and grid[i][j] == 1:
if distances[x][y]+1 < distances[i][j]:
distances[i][j] = distances[x][y] + 1
grid[i][j] = 2
tocheck.enqueue((i,j))
c = tocheck.dequeue()
maxi = 0
for i in distances:
for j in i:
if j > maxi: maxi = j
if maxi == m*n-1: maxi = -1
print(maxi)
Explanation: Firstly, a pretty standard class implementing queues (Can't use builting module for some reason). n,m = #rows, #cols
Next, a grid containing values and a grid containing distances is created. If the value is 2, then distance matrix contains 0. If value is 1, then distance is m*n-1 (larger than maximum possible distance). If value is 0, then distance is -1 (not possible). Also, every location containing 2 is also stored separately in a queue
Main BFS part: Dequeue a location. Check if all Neighbours all valid enteries in matrix containing 1. If the distance of this neighobour is strictly greater than the current locations distance + 1, then update the neighbour's value to 2, distance to current distance + 1 and queue it. Repeat till queue is empty.
Any suggestions for optimization? (I realize my code has 0 comments but then again I didn't know I'd spend over 4 hours on this)
python performance
asked 8 mins ago
AnvitAnvit
1011
New contributor
Anvit is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
This is from HackerRank - Travel Diaries. Given a grid of 0s,1s and 2s we need to find minimum distance of each 1 from 2 going through 1s only. (See 1 as land, 0 as ocean, 2 as food, need to find closest food for each tile of land where boats dont exists)
Here's my code
class Queue:
def __init__(self):
self.items = []
def empty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
try:
return self.items.pop()
except: return False
def size(self):
return len(self.items)
n,m = map(int,input().split(' '))
grid = list()
distances = list()
tocheck = Queue()
for i in range(n):
grid.append(list(map(int,input().split(' '))))
toapp = []
for j in range(m):
if grid[i][j] == 2:
toapp.append(0)
tocheck.enqueue((i,j))
else: toapp.append(m*n + (grid[i][j]-1)*m*n-1)
distances.append(toapp)
c = tocheck.dequeue()
while c:
x,y = c
for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
if 0<=i<n and 0<=j<m and grid[i][j] == 1:
if distances[x][y]+1 < distances[i][j]:
distances[i][j] = distances[x][y] + 1
grid[i][j] = 2
tocheck.enqueue((i,j))
c = tocheck.dequeue()
maxi = 0
for i in distances:
for j in i:
if j > maxi: maxi = j
if maxi == m*n-1: maxi = -1
print(maxi)
Explanation: Firstly, a pretty standard class implementing queues (Can't use builting module for some reason). n,m = #rows, #cols
Next, a grid containing values and a grid containing distances is created. If the value is 2, then distance matrix contains 0. If value is 1, then distance is m*n-1 (larger than maximum possible distance). If value is 0, then distance is -1 (not possible). Also, every location containing 2 is also stored separately in a queue
Main BFS part: Dequeue a location. Check if all Neighbours all valid enteries in matrix containing 1. If the distance of this neighobour is strictly greater than the current locations distance + 1, then update the neighbour's value to 2, distance to current distance + 1 and queue it. Repeat till queue is empty.
Any suggestions for optimization? (I realize my code has 0 comments but then again I didn't know I'd spend over 4 hours on this)
python performance
asked 8 mins ago
AnvitAnvit
1011
New contributor
Anvit is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
This is from HackerRank - Travel Diaries. Given a grid of 0s,1s and 2s we need to find minimum distance of each 1 from 2 going through 1s only. (See 1 as land, 0 as ocean, 2 as food, need to find closest food for each tile of land where boats dont exists)
Here's my code
class Queue:
def __init__(self):
self.items = []
def empty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
try:
return self.items.pop()
except: return False
def size(self):
return len(self.items)
n,m = map(int,input().split(' '))
grid = list()
distances = list()
tocheck = Queue()
for i in range(n):
grid.append(list(map(int,input().split(' '))))
toapp = []
for j in range(m):
if grid[i][j] == 2:
toapp.append(0)
tocheck.enqueue((i,j))
else: toapp.append(m*n + (grid[i][j]-1)*m*n-1)
distances.append(toapp)
c = tocheck.dequeue()
while c:
x,y = c
for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
if 0<=i<n and 0<=j<m and grid[i][j] == 1:
if distances[x][y]+1 < distances[i][j]:
distances[i][j] = distances[x][y] + 1
grid[i][j] = 2
tocheck.enqueue((i,j))
c = tocheck.dequeue()
maxi = 0
for i in distances:
for j in i:
if j > maxi: maxi = j
if maxi == m*n-1: maxi = -1
print(maxi)
Explanation: Firstly, a pretty standard class implementing queues (Can't use builting module for some reason). n,m = #rows, #cols
Next, a grid containing values and a grid containing distances is created. If the value is 2, then distance matrix contains 0. If value is 1, then distance is m*n-1 (larger than maximum possible distance). If value is 0, then distance is -1 (not possible). Also, every location containing 2 is also stored separately in a queue
Main BFS part: Dequeue a location. Check if all Neighbours all valid enteries in matrix containing 1. If the distance of this neighobour is strictly greater than the current locations distance + 1, then update the neighbour's value to 2, distance to current distance + 1 and queue it. Repeat till queue is empty.
Any suggestions for optimization? (I realize my code has 0 comments but then again I didn't know I'd spend over 4 hours on this)
python performance
python performance
asked 8 mins ago
AnvitAnvit
1011
New contributor
Anvit is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 mins ago
AnvitAnvit
1011
New contributor
Anvit is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 mins ago
AnvitAnvit
1011
New contributor
Anvit is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 mins ago
AnvitAnvit
1011
asked 8 mins ago
AnvitAnvit
1011
1011
New contributor
Anvit is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Anvit is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Anvit is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Anvit is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f214612%2foptimization-of-bfs-for-finding-minimum-distances-between-elements-of-a-grid%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Anvit is a new contributor. Be nice, and check out our Code of Conduct.
Anvit is a new contributor. Be nice, and check out our Code of Conduct.
Anvit is a new contributor. Be nice, and check out our Code of Conduct.
Anvit is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f214612%2foptimization-of-bfs-for-finding-minimum-distances-between-elements-of-a-grid%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
