5
\$\begingroup\$

I've tried to solve the kattis-challenge called Watchdog. My code works just fine, but it was 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 was also slower. And it's the speed that I'm having issues with.

Example input:

3
10 2
6 6
5 4
20 2
1 1
19 19
10 3
1 1
1 2
1 3

Example output:

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
\$\endgroup\$
9
  • 1
    \$\begingroup\$ To specifically answer your question, you'd need to use a profiler to look at the code and see how long it takes. Given there is no sample input with your code, I'm unable to demonstrate how you would do this yourself. Could you add it to your question? \$\endgroup\$
    – C. Harley
    Commented Apr 1, 2019 at 2:34
  • \$\begingroup\$ The sample-input is given right before my code, after "Example in:", or am I misunderstanding what you're asking for? I could use timeit to time the runtime of the code, and I have for myself, but every change I make gives very small differences in computing-time. Therefore I expect something to be obviously slower than an alternative, though I can't see it. \$\endgroup\$
    – RoyM
    Commented Apr 1, 2019 at 3:17
  • \$\begingroup\$ Oh yes sorry - so I run the program and paste the examples and nothing works. I type in a single line - and nothing works. How are you running the code? \$\endgroup\$
    – C. Harley
    Commented Apr 1, 2019 at 3:31
  • \$\begingroup\$ The example is taken directly form stdin. You have a file containing the code, e.g. a file distance.py containing everything from the section "My code" above. Then you have a separate file within the same folder containing the example, e.g. a file example.in containing everything from the section "Example in" above. Then from the command-line (on windows) you'd run python distance.py < Example.in \$\endgroup\$
    – RoyM
    Commented Apr 1, 2019 at 3:42
  • 1
    \$\begingroup\$ Please fix your indentation. The easiest way to post code is to paste it into the question editor, highlight it, and press Ctrl-K to mark it as a code block. \$\endgroup\$ Commented Apr 1, 2019 at 4:34

2 Answers 2

1
\$\begingroup\$

Your solution is right, but unfortunately the time limit enforces a certain optimization. The key of this is where it says:

If several such point print point with lowest x, if several points with equal x, print point with lowest y

In your case, you just append all possible candidate and then you have a very complicated way to find the lowest. First of all, this complicated way could have been reduced to sorting and returning first element.

If we think a bit further on how does itertools.product work, it will first iterate over x and then over y. This means that the first candidate we find, is the one with lowest x and lowest y of those x. This means 2 things: you don´t even need that sort, the answer will always be the first candidate.

Now if the answer is always the first candidate, why are we keeping all candidates? And why are we still calculating other possible candidates when we already have the answer? Keeping this in mind, the solution to your time limit is simple adding a break after the possibles.append((x, y)) line. This will make us stop processing when we find the answer, and will save enough time for the time limit.

This means all the elif len(possibles)>1: part is unnecessary, making it shorter and cleaner. Another simple optimization is changing hatch_list to a set instead of a list so that the if (x, y) not in hatch_list: takes less than O(n). Its a small change that only requires changing list() to set() and append to add.

There might be more optimization to make but the one of the break is the key to the problem and the expected optimization to make to be able to not have time limit.

\$\endgroup\$
5
  • \$\begingroup\$ Thank you very much for your contribution! Incidentally I've made the exact same realization on my own. The whole use of possible solutions is just a waste of computing time. So I have shortened my code quite a bit, and I also did break, and I added a boolean-flag to see if any solutions was found at all (if not poodle is printed). Still though, I get timed out on the very last test. But I have yet to try your suggestion of changing list to set. I will do that next. If you someone wouldn't mind: What is the preferred way of showing my "progress", I know I'm not supposed to update original. \$\endgroup\$
    – RoyM
    Commented Apr 1, 2019 at 18:09
  • \$\begingroup\$ @RoyM you may edit your question and add something like: Update: I have now updated the code to this but it is still giving me time out and show current code. Also I straight copied your code and added the break and submitted to kattis and got accepted before, are you submitting somewhere else? \$\endgroup\$
    – juvian
    Commented Apr 1, 2019 at 18:20
  • \$\begingroup\$ You did? Now I'm positively confused. I've been at this one for hours, having a much more minimized solution fail for several of them. I'll provide an update in my question giving my current code – which do fail at https://open.kattis.com/problems/watchdog. The only thing I can think of is some misspelling giving me an infinite loop, or an issue with using the "edit and resubmit"-function from an old subit that had the timeout. \$\endgroup\$
    – RoyM
    Commented Apr 1, 2019 at 19:28
  • \$\begingroup\$ @RoyM I have no idea why your current code gives time limit, but if you copy your old code posted here, add the break line after possibles.append and submit, you will get accepted \$\endgroup\$
    – juvian
    Commented Apr 1, 2019 at 19:45
  • \$\begingroup\$ Oh wow, it did. I still can't see why the improved version edited away from the OP doesn't. It has the same change, and several other improvements. I guess I'll find a rogue parentheses or the like if I just stare at it enough. But you've been a grat help. Thank you! \$\endgroup\$
    – RoyM
    Commented Apr 1, 2019 at 20:47
-2
\$\begingroup\$

To specifically answer your question, you'd need to use a profiler to look at the code and see how long it takes.

cprofilev 20190401a.py < 20190401a.txt 
     1273 function calls in 0.001 seconds

Ordered by: cumulative time

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    0.000    0.000    0.001    0.001 {built-in method builtins.exec}
    1    0.000    0.000    0.001    0.001 20190401a.py:1(<module>)
  593    0.000    0.000    0.000    0.000 20190401a.py:6(findmaxdist)
    1    0.000    0.000    0.000    0.000 {method 'readlines' of '_io._IOBase' objects}
  593    0.000    0.000    0.000    0.000 {built-in method math.sqrt}
    3    0.000    0.000    0.000    0.000 {built-in method builtins.print}
    2    0.000    0.000    0.000    0.000 /usr/lib/python3.5/codecs.py:318(decode)
    2    0.000    0.000    0.000    0.000 {built-in method builtins.min}
    1    0.000    0.000    0.000    0.000 20190401a.py:18(<listcomp>)
    1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:996(_handle_fromlist)
   22    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
    4    0.000    0.000    0.000    0.000 20190401a.py:48(<genexpr>)
    1    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
   11    0.000    0.000    0.000    0.000 {method 'rstrip' of 'str' objects}
   10    0.000    0.000    0.000    0.000 {method 'split' of 'str' objects}
    2    0.000    0.000    0.000    0.000 {built-in method _codecs.utf_8_decode}
   15    0.000    0.000    0.000    0.000 20190401a.py:47(<lambda>)
    1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    9    0.000    0.000    0.000    0.000 {built-in method builtins.len}

I ran cprofile a few times and the function call numbers are static. From the look of your code, we're seeing multiple requests to findmaxdist and math.sqrt, there might be an opportunity to clean that up.
There are 22 appends to a list object, which if we look at "Common Data Structure Operations" (see http://bigocheatsheet.com/), which might be an inefficient data structure for what you're trying to achieve.

Looking at your code, regardless of speed, having it all as one giant blob instead of neatly separated into functions (look up the Single Responsibility Principal) can make your code execute faster as functions compile down neatly and very efficiently - especially when written in a functional style of programming (no state maintained in the function after the function completes).

Other than streamlining the calls and changing your data structure, I don't think you'll see much speed improvement with the code as-in. I hope this helps somewhat?
Good luck!

\$\endgroup\$
6
  • \$\begingroup\$ Thank you, I'll try to make the suggested changes and see how it works! \$\endgroup\$
    – RoyM
    Commented Apr 1, 2019 at 4:28
  • \$\begingroup\$ LOL why the downvotes? Performance is a valid question criteria for Code Review, and profiling code is the first step towards removing performance hits. \$\endgroup\$
    – C. Harley
    Commented Apr 4, 2019 at 1:13
  • \$\begingroup\$ I don't know who downvoted you. I upvoted. Though, after the fact, I think it probably has to do with the fact that the main issue came from a missing break-point, and not the number of calls to each method. In that sense one could easily be sent on a wild goose-chase. Still, I think your post was helpful, as I've made many improvements based on it, and I don't think you should have been downvoted. But I also don't know how this site works, I'm still dumbfounded that I can't post an update to how the code has improved based on suggestions here. But oh well. \$\endgroup\$
    – RoyM
    Commented Apr 4, 2019 at 5:22
  • 1
    \$\begingroup\$ If you see some other posts, people recommend creating a new post/submission with links to the previous posting when the code has changed (perhaps that's covered under the Help in the footer?) But yeah, maybe "one day" we will be able to select different versions if they add git as part of the posting/submission process. \$\endgroup\$
    – C. Harley
    Commented Apr 4, 2019 at 6:20
  • \$\begingroup\$ I didn't downvote, but given that almost all of the timings are "0.000" it doesn't tell you where the performance problems are. \$\endgroup\$
    – Peilonrayz
    Commented Apr 16, 2019 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.