Programming Challenge from Kattis: Watchdog The Next CEO of Stack Overflow
What was Carter Burke's job for "the company" in Aliens?
How to get the last not-null value in an ordered column of a huge table?
Why is information "lost" when it got into a black hole?
How to use ReplaceAll on an expression that contains a rule
What is the difference between "hamstring tendon" and "common hamstring tendon"?
Is there an equivalent of cd - for cp or mv
In the "Harry Potter and the Order of the Phoenix" video game, what potion is used to sabotage Umbridge's speakers?
Is a distribution that is normal, but highly skewed, considered Gaussian?
What difference does it make using sed with/without whitespaces?
Is it professional to write unrelated content in an almost-empty email?
How to Implement Deterministic Encryption Safely in .NET
Yu-Gi-Oh cards in Python 3
Traveling with my 5 year old daughter (as the father) without the mother from Germany to Mexico
Can you teleport closer to a creature you are Frightened of?
Can Sneak Attack be used when hitting with an improvised weapon?
Does higher Oxidation/ reduction potential translate to higher energy storage in battery?
Help understanding this unsettling image of Titan, Epimetheus, and Saturn's rings?
Small nick on power cord from an electric alarm clock, and copper wiring exposed but intact
Is there a difference between "Fahrstuhl" and "Aufzug"?
"Eavesdropping" vs "Listen in on"
Aggressive Under-Indexing and no data for missing index
Do scriptures give a method to recognize a truly self-realized person/jivanmukta?
What is the process for cleansing a very negative action
Redefining symbol midway through a document
Programming Challenge from Kattis: Watchdog
The Next CEO of Stack Overflow
$begingroup$
So I've tried to solve the kattis-challenge called Watchdog. My code works just fine, but it is too slow on the last test. I'm wondering if anyone sees any big algorithmic performance-issues.
A short description of the task: First line from .in states number of test-cases.
First line in each test-case gives length of a square and number of hatches respectively. For each hatch you'll have one line giving x and y-point of hatch respectively. The mission is to find a point x,y where the length from x,y to any hatch is not greater than the length from x,y to any point outside of the square. If no such point, print poodle
. If several such point print point with lowest x, if several points with equal x, print point with lowest y. Hatches and these points cannot overlap.
I think one issue might be extensive usage of lists, but I'm also not sure how to avoid them. Initially I started reading one and one line from stdin, using the data. That way things looked way more readable, but it also was slower. And it's the speed that I'm having issues with.
Example in:
3
10 2
6 6
5 4
20 2
1 1
19 19
10 3
1 1
1 2
1 3
Example out:
3 6
poodle
2 2
2 2
My code:
import sys
from math import sqrt
import itertools
def findmaxdist(x1, y1, list):
'''Finds the distance from x1, y1 to the most
distant point in the list.'''
dist = 0
for x2, y2 in list:
newdist = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)
if newdist>dist:
dist=newdist
return sqrt(dist)
fulltext = sys.stdin.readlines()
text = [w.rstrip('n') for w in fulltext]
cases = int(text[0])
i = 0
j = 1
while i < cases:
side, hatches = text[j].split()
side = int(side)
hatches = int(hatches)
j += 1
hatch_list = list()
for k in range(hatches):
x, y = text[j].split()
hatch_list.append((int(x), int(y)))
j += 1
possibles = list()
for x,y in itertools.product(range(side), range(side)):
if (x, y) not in hatch_list:
dist = findmaxdist(x, y, hatch_list)
if x+dist<=side and x-dist>=0:
if y+dist<=side and y-dist>=0:
possibles.append((x, y))
if len(possibles)==0:
print('poodle')
elif len(possibles)==1:
print(str(possibles[0][0])+' '+str(possibles[0][1]))
elif len(possibles)>1:
smallx = min(possibles, key = lambda t: t[0])[0]
semifinal = list((tuple for tuple in possibles if tuple[0] == smallx))
if len(semifinal)==1:
x,y = semifinal[0]
print(str(x)+' '+str(y))
elif len(semifinal)>1:
smally = min(semifinal, key = lambda t: t[1])[1]
final = list((tuple for tuple in semifinal if tuple[1] == smally))
if len(final)==1:
x,y = final[0]
print(str(x)+' '+str(y))
else:
print('Error: Wrong input-format?')
i+=1
performance python-3.x programming-challenge
New contributor
$endgroup$
add a comment |
$begingroup$
So I've tried to solve the kattis-challenge called Watchdog. My code works just fine, but it is too slow on the last test. I'm wondering if anyone sees any big algorithmic performance-issues.
A short description of the task: First line from .in states number of test-cases.
First line in each test-case gives length of a square and number of hatches respectively. For each hatch you'll have one line giving x and y-point of hatch respectively. The mission is to find a point x,y where the length from x,y to any hatch is not greater than the length from x,y to any point outside of the square. If no such point, print poodle
. If several such point print point with lowest x, if several points with equal x, print point with lowest y. Hatches and these points cannot overlap.
I think one issue might be extensive usage of lists, but I'm also not sure how to avoid them. Initially I started reading one and one line from stdin, using the data. That way things looked way more readable, but it also was slower. And it's the speed that I'm having issues with.
Example in:
3
10 2
6 6
5 4
20 2
1 1
19 19
10 3
1 1
1 2
1 3
Example out:
3 6
poodle
2 2
2 2
My code:
import sys
from math import sqrt
import itertools
def findmaxdist(x1, y1, list):
'''Finds the distance from x1, y1 to the most
distant point in the list.'''
dist = 0
for x2, y2 in list:
newdist = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)
if newdist>dist:
dist=newdist
return sqrt(dist)
fulltext = sys.stdin.readlines()
text = [w.rstrip('n') for w in fulltext]
cases = int(text[0])
i = 0
j = 1
while i < cases:
side, hatches = text[j].split()
side = int(side)
hatches = int(hatches)
j += 1
hatch_list = list()
for k in range(hatches):
x, y = text[j].split()
hatch_list.append((int(x), int(y)))
j += 1
possibles = list()
for x,y in itertools.product(range(side), range(side)):
if (x, y) not in hatch_list:
dist = findmaxdist(x, y, hatch_list)
if x+dist<=side and x-dist>=0:
if y+dist<=side and y-dist>=0:
possibles.append((x, y))
if len(possibles)==0:
print('poodle')
elif len(possibles)==1:
print(str(possibles[0][0])+' '+str(possibles[0][1]))
elif len(possibles)>1:
smallx = min(possibles, key = lambda t: t[0])[0]
semifinal = list((tuple for tuple in possibles if tuple[0] == smallx))
if len(semifinal)==1:
x,y = semifinal[0]
print(str(x)+' '+str(y))
elif len(semifinal)>1:
smally = min(semifinal, key = lambda t: t[1])[1]
final = list((tuple for tuple in semifinal if tuple[1] == smally))
if len(final)==1:
x,y = final[0]
print(str(x)+' '+str(y))
else:
print('Error: Wrong input-format?')
i+=1
performance python-3.x programming-challenge
New contributor
$endgroup$
add a comment |
$begingroup$
So I've tried to solve the kattis-challenge called Watchdog. My code works just fine, but it is too slow on the last test. I'm wondering if anyone sees any big algorithmic performance-issues.
A short description of the task: First line from .in states number of test-cases.
First line in each test-case gives length of a square and number of hatches respectively. For each hatch you'll have one line giving x and y-point of hatch respectively. The mission is to find a point x,y where the length from x,y to any hatch is not greater than the length from x,y to any point outside of the square. If no such point, print poodle
. If several such point print point with lowest x, if several points with equal x, print point with lowest y. Hatches and these points cannot overlap.
I think one issue might be extensive usage of lists, but I'm also not sure how to avoid them. Initially I started reading one and one line from stdin, using the data. That way things looked way more readable, but it also was slower. And it's the speed that I'm having issues with.
Example in:
3
10 2
6 6
5 4
20 2
1 1
19 19
10 3
1 1
1 2
1 3
Example out:
3 6
poodle
2 2
2 2
My code:
import sys
from math import sqrt
import itertools
def findmaxdist(x1, y1, list):
'''Finds the distance from x1, y1 to the most
distant point in the list.'''
dist = 0
for x2, y2 in list:
newdist = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)
if newdist>dist:
dist=newdist
return sqrt(dist)
fulltext = sys.stdin.readlines()
text = [w.rstrip('n') for w in fulltext]
cases = int(text[0])
i = 0
j = 1
while i < cases:
side, hatches = text[j].split()
side = int(side)
hatches = int(hatches)
j += 1
hatch_list = list()
for k in range(hatches):
x, y = text[j].split()
hatch_list.append((int(x), int(y)))
j += 1
possibles = list()
for x,y in itertools.product(range(side), range(side)):
if (x, y) not in hatch_list:
dist = findmaxdist(x, y, hatch_list)
if x+dist<=side and x-dist>=0:
if y+dist<=side and y-dist>=0:
possibles.append((x, y))
if len(possibles)==0:
print('poodle')
elif len(possibles)==1:
print(str(possibles[0][0])+' '+str(possibles[0][1]))
elif len(possibles)>1:
smallx = min(possibles, key = lambda t: t[0])[0]
semifinal = list((tuple for tuple in possibles if tuple[0] == smallx))
if len(semifinal)==1:
x,y = semifinal[0]
print(str(x)+' '+str(y))
elif len(semifinal)>1:
smally = min(semifinal, key = lambda t: t[1])[1]
final = list((tuple for tuple in semifinal if tuple[1] == smally))
if len(final)==1:
x,y = final[0]
print(str(x)+' '+str(y))
else:
print('Error: Wrong input-format?')
i+=1
performance python-3.x programming-challenge
New contributor
$endgroup$
So I've tried to solve the kattis-challenge called Watchdog. My code works just fine, but it is too slow on the last test. I'm wondering if anyone sees any big algorithmic performance-issues.
A short description of the task: First line from .in states number of test-cases.
First line in each test-case gives length of a square and number of hatches respectively. For each hatch you'll have one line giving x and y-point of hatch respectively. The mission is to find a point x,y where the length from x,y to any hatch is not greater than the length from x,y to any point outside of the square. If no such point, print poodle
. If several such point print point with lowest x, if several points with equal x, print point with lowest y. Hatches and these points cannot overlap.
I think one issue might be extensive usage of lists, but I'm also not sure how to avoid them. Initially I started reading one and one line from stdin, using the data. That way things looked way more readable, but it also was slower. And it's the speed that I'm having issues with.
Example in:
3
10 2
6 6
5 4
20 2
1 1
19 19
10 3
1 1
1 2
1 3
Example out:
3 6
poodle
2 2
2 2
My code:
import sys
from math import sqrt
import itertools
def findmaxdist(x1, y1, list):
'''Finds the distance from x1, y1 to the most
distant point in the list.'''
dist = 0
for x2, y2 in list:
newdist = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)
if newdist>dist:
dist=newdist
return sqrt(dist)
fulltext = sys.stdin.readlines()
text = [w.rstrip('n') for w in fulltext]
cases = int(text[0])
i = 0
j = 1
while i < cases:
side, hatches = text[j].split()
side = int(side)
hatches = int(hatches)
j += 1
hatch_list = list()
for k in range(hatches):
x, y = text[j].split()
hatch_list.append((int(x), int(y)))
j += 1
possibles = list()
for x,y in itertools.product(range(side), range(side)):
if (x, y) not in hatch_list:
dist = findmaxdist(x, y, hatch_list)
if x+dist<=side and x-dist>=0:
if y+dist<=side and y-dist>=0:
possibles.append((x, y))
if len(possibles)==0:
print('poodle')
elif len(possibles)==1:
print(str(possibles[0][0])+' '+str(possibles[0][1]))
elif len(possibles)>1:
smallx = min(possibles, key = lambda t: t[0])[0]
semifinal = list((tuple for tuple in possibles if tuple[0] == smallx))
if len(semifinal)==1:
x,y = semifinal[0]
print(str(x)+' '+str(y))
elif len(semifinal)>1:
smally = min(semifinal, key = lambda t: t[1])[1]
final = list((tuple for tuple in semifinal if tuple[1] == smally))
if len(final)==1:
x,y = final[0]
print(str(x)+' '+str(y))
else:
print('Error: Wrong input-format?')
i+=1
performance python-3.x programming-challenge
performance python-3.x programming-challenge
New contributor
New contributor
New contributor
asked 4 mins ago
RoyMRoyM
1
1
New contributor
New contributor
add a comment |
add a comment |
0
active
oldest
votes
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
);
);
RoyM 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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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%2f216615%2fprogramming-challenge-from-kattis-watchdog%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
RoyM is a new contributor. Be nice, and check out our Code of Conduct.
RoyM is a new contributor. Be nice, and check out our Code of Conduct.
RoyM is a new contributor. Be nice, and check out our Code of Conduct.
RoyM 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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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%2f216615%2fprogramming-challenge-from-kattis-watchdog%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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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