Size of the largest connected component in a grid in Python
Given an R x C grid of 1s and 0s (or True and False values), I need a function that can find the size of the largest connected component of 1s. For example, for the following grid,
grid = [[0, 1, 0, 1],
[1, 1, 1, 0],
[0, 1, 0, 0],
[0, 0, 0, 1]]
The answer is 5.
Here is my implementation:
def largest_connected_component(nrows, ncols, grid):
"""Find largest connected component of 1s on a grid."""
def traverse_component(i, j):
"""Returns no. of unseen elements connected to (i,j)."""
seen[i][j] = True
result = 1
# Check all four neighbours
if i > 0 and grid[i-1][j] and not seen[i-1][j]:
result += traverse_component(i-1, j)
if j > 0 and grid[i][j-1] and not seen[i][j-1]:
result += traverse_component(i, j-1)
if i < len(grid)-1 and grid[i+1][j] and not seen[i+1][j]:
result += traverse_component(i+1, j)
if j < len(grid[0])-1 and grid[i][j+1] and not seen[i][j+1]:
result += traverse_component(i, j+1)
return result
seen = [[False] * ncols for _ in range(nrows)]
# Tracks size of largest connected component found
component_size = 0
for i in range(nrows):
for j in range(ncols):
if grid[i][j] and not seen[i][j]:
temp = traverse_component(i, j)
if temp > component_size:
component_size = temp
return component_size
Feel free to use the following code to generate random grids to test the function,
from random import randint
N = 20
grid = [[randint(0,1) for _ in range(N)] for _ in range(N)]
Problem: My implementation runs too slow (by about a factor of 3). Since I wrote this as a naive approach by myself, I am guessing there are clever optimizations that can be made.
Context: This is for solving the Gridception problem from Round 2 of Google Codejam 2018. My goal is to solve the problem in Python 3. As a result, there is a hard constraint of using only the Python 3 standard library.
I have figured out that this particular portion of the full solution is my performance bottleneck and thus, my solution fails to clear the Large Input due to being too slow.
Thank you so much!
python performance algorithm python-3.x
asked 9 mins ago
XYZT
1062
New contributor
XYZT 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 |
Given an R x C grid of 1s and 0s (or True and False values), I need a function that can find the size of the largest connected component of 1s. For example, for the following grid,
grid = [[0, 1, 0, 1],
[1, 1, 1, 0],
[0, 1, 0, 0],
[0, 0, 0, 1]]
The answer is 5.
Here is my implementation:
def largest_connected_component(nrows, ncols, grid):
"""Find largest connected component of 1s on a grid."""
def traverse_component(i, j):
"""Returns no. of unseen elements connected to (i,j)."""
seen[i][j] = True
result = 1
# Check all four neighbours
if i > 0 and grid[i-1][j] and not seen[i-1][j]:
result += traverse_component(i-1, j)
if j > 0 and grid[i][j-1] and not seen[i][j-1]:
result += traverse_component(i, j-1)
if i < len(grid)-1 and grid[i+1][j] and not seen[i+1][j]:
result += traverse_component(i+1, j)
if j < len(grid[0])-1 and grid[i][j+1] and not seen[i][j+1]:
result += traverse_component(i, j+1)
return result
seen = [[False] * ncols for _ in range(nrows)]
# Tracks size of largest connected component found
component_size = 0
for i in range(nrows):
for j in range(ncols):
if grid[i][j] and not seen[i][j]:
temp = traverse_component(i, j)
if temp > component_size:
component_size = temp
return component_size
Feel free to use the following code to generate random grids to test the function,
from random import randint
N = 20
grid = [[randint(0,1) for _ in range(N)] for _ in range(N)]
Problem: My implementation runs too slow (by about a factor of 3). Since I wrote this as a naive approach by myself, I am guessing there are clever optimizations that can be made.
Context: This is for solving the Gridception problem from Round 2 of Google Codejam 2018. My goal is to solve the problem in Python 3. As a result, there is a hard constraint of using only the Python 3 standard library.
I have figured out that this particular portion of the full solution is my performance bottleneck and thus, my solution fails to clear the Large Input due to being too slow.
Thank you so much!
python performance algorithm python-3.x
asked 9 mins ago
XYZT
1062
New contributor
XYZT 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 |
Given an R x C grid of 1s and 0s (or True and False values), I need a function that can find the size of the largest connected component of 1s. For example, for the following grid,
grid = [[0, 1, 0, 1],
[1, 1, 1, 0],
[0, 1, 0, 0],
[0, 0, 0, 1]]
The answer is 5.
Here is my implementation:
def largest_connected_component(nrows, ncols, grid):
"""Find largest connected component of 1s on a grid."""
def traverse_component(i, j):
"""Returns no. of unseen elements connected to (i,j)."""
seen[i][j] = True
result = 1
# Check all four neighbours
if i > 0 and grid[i-1][j] and not seen[i-1][j]:
result += traverse_component(i-1, j)
if j > 0 and grid[i][j-1] and not seen[i][j-1]:
result += traverse_component(i, j-1)
if i < len(grid)-1 and grid[i+1][j] and not seen[i+1][j]:
result += traverse_component(i+1, j)
if j < len(grid[0])-1 and grid[i][j+1] and not seen[i][j+1]:
result += traverse_component(i, j+1)
return result
seen = [[False] * ncols for _ in range(nrows)]
# Tracks size of largest connected component found
component_size = 0
for i in range(nrows):
for j in range(ncols):
if grid[i][j] and not seen[i][j]:
temp = traverse_component(i, j)
if temp > component_size:
component_size = temp
return component_size
Feel free to use the following code to generate random grids to test the function,
from random import randint
N = 20
grid = [[randint(0,1) for _ in range(N)] for _ in range(N)]
Problem: My implementation runs too slow (by about a factor of 3). Since I wrote this as a naive approach by myself, I am guessing there are clever optimizations that can be made.
Context: This is for solving the Gridception problem from Round 2 of Google Codejam 2018. My goal is to solve the problem in Python 3. As a result, there is a hard constraint of using only the Python 3 standard library.
I have figured out that this particular portion of the full solution is my performance bottleneck and thus, my solution fails to clear the Large Input due to being too slow.
Thank you so much!
python performance algorithm python-3.x
asked 9 mins ago
XYZT
1062
New contributor
XYZT is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Given an R x C grid of 1s and 0s (or True and False values), I need a function that can find the size of the largest connected component of 1s. For example, for the following grid,
grid = [[0, 1, 0, 1],
[1, 1, 1, 0],
[0, 1, 0, 0],
[0, 0, 0, 1]]
The answer is 5.
Here is my implementation:
def largest_connected_component(nrows, ncols, grid):
"""Find largest connected component of 1s on a grid."""
def traverse_component(i, j):
"""Returns no. of unseen elements connected to (i,j)."""
seen[i][j] = True
result = 1
# Check all four neighbours
if i > 0 and grid[i-1][j] and not seen[i-1][j]:
result += traverse_component(i-1, j)
if j > 0 and grid[i][j-1] and not seen[i][j-1]:
result += traverse_component(i, j-1)
if i < len(grid)-1 and grid[i+1][j] and not seen[i+1][j]:
result += traverse_component(i+1, j)
if j < len(grid[0])-1 and grid[i][j+1] and not seen[i][j+1]:
result += traverse_component(i, j+1)
return result
seen = [[False] * ncols for _ in range(nrows)]
# Tracks size of largest connected component found
component_size = 0
for i in range(nrows):
for j in range(ncols):
if grid[i][j] and not seen[i][j]:
temp = traverse_component(i, j)
if temp > component_size:
component_size = temp
return component_size
Feel free to use the following code to generate random grids to test the function,
from random import randint
N = 20
grid = [[randint(0,1) for _ in range(N)] for _ in range(N)]
Problem: My implementation runs too slow (by about a factor of 3). Since I wrote this as a naive approach by myself, I am guessing there are clever optimizations that can be made.
Context: This is for solving the Gridception problem from Round 2 of Google Codejam 2018. My goal is to solve the problem in Python 3. As a result, there is a hard constraint of using only the Python 3 standard library.
I have figured out that this particular portion of the full solution is my performance bottleneck and thus, my solution fails to clear the Large Input due to being too slow.
Thank you so much!
python performance algorithm python-3.x
python performance algorithm python-3.x
asked 9 mins ago
XYZT
1062
New contributor
XYZT is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 mins ago
XYZT
1062
New contributor
XYZT is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 mins ago
XYZT
1062
New contributor
XYZT is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 mins ago
XYZT
1062
asked 9 mins ago
XYZT
1062
1062
New contributor
XYZT is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
XYZT is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
XYZT 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 |
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
});
}
});
XYZT 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%2f210641%2fsize-of-the-largest-connected-component-in-a-grid-in-python%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
XYZT is a new contributor. Be nice, and check out our Code of Conduct.
XYZT is a new contributor. Be nice, and check out our Code of Conduct.
XYZT is a new contributor. Be nice, and check out our Code of Conduct.
XYZT 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f210641%2fsize-of-the-largest-connected-component-in-a-grid-in-python%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
