Closure creative solution for Building Visibility by veky - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Closure solution in Creative category for Building Visibility by veky

def checkio(b):
    def v(d,r=False,z={}):
        for x in range(d[0],d[2]):
            if d[4]>z.get(x,0): r,z[x]=True,d[4]
        return r
    return sum(map(v,sorted(b,key=lambda d: d[1])))

June 23, 2013

Comments:

AndriusMk on June 23, 2013, 1:45 p.m.
Mind blowing...

veky on June 24, 2013, 3:25 a.m.
I'm glad to be of your service. ;-))

AndriusMk on June 24, 2013, 10:46 a.m.
Keep doing what you're doing, my loyal servant

veky on June 24, 2013, 4:46 p.m.
This servant hopes other his solutions are also mind blowing, if it pleases his Master. ;-)

AndriusMk on June 25, 2013, 9:50 a.m.
<pre class='brush: python'>import sacred import eternal eternal.grant(sum(sacred.perform(spell) for spell in sacred.ritual[''], eternal.sociocomplex.construct), 'veky') </pre>

Vachenzo on June 25, 2013, 1:38 p.m.
Oh god I think I just shot coffee out my nose.

veky on June 26, 2013, 8:39 a.m.
"generator expression must be parenthesized if not sole argument" I think Python just shot coffee out of its nose too. :-P

Faibbus on June 23, 2013, 5:33 p.m.
You are only a few comments away from perfection... But anyway, that's impressive.

veky on June 24, 2013, 3:24 a.m.
I can write comments here, what do you want to know? :-) If I wanted to document everything that goes on there, comments would be longer than the code. :-]

AHrEJl on Aug. 13, 2013, 1:56 p.m.
Awesome)) Just awesome :)

veky on Aug. 14, 2013, 9:55 a.m.
Tnx. ;-)

nickie on Feb. 24, 2014, 12:52 a.m.
Well done! Just a comment: this solution is O(N*log(N)+N*W) where W is the maximum width of the buildings. IFAIK, there are two types of better solutions (but more complicated, unless Veky surprises us again): <ol> <li>O(N^2), using a pretty straightforward vertical scan line.</li> <li>O(N*log(N)), using an even more complicated data structure for keeping buildings along the scan line.</li> </ol>

veky on Feb. 24, 2014, 5:48 a.m.
Well, if it's important (I know it is to you:), b can be preprocessed so that verticals where nothing is happening are removed (buildings are squeezed to minimal width preserving ordering of beginnings and endings). Yes, then it'd be longer. But still shorter than yours. :-D BTW I acknowledge your "professional deformation" (same as you hopefully acknowledge mine:), but not everything in Python is susceptible to algorithmic class analysis in the style of classic 1970s. (I'm sure you know these things, but maybe somebody else reads this.:) First, there are two layers of implementation, Python and C (or Java...), and factor of speed between them is not constant, sometimes not even bounded (when compilers do weird things like optimizing away the loops, which Python can't do because of stricter semantics). Second, parallelization on a processor level is very hard, sometimes even nondeterministic, to capture in "counting the number of operations" or even worse "counting the number of ticks". Third, hashing, which pervades Python data structures, has abysmal worst case complexity, but wonderful practical one. It even has, in modern Pythons, a random component which differs from run to run. Practicality beats purity, in many ways, in Python philosophy. Fourth, "size of input", an essential notion when discussing complexity classes, is not really well defined here. In classical complexity, "size in bytes" and "size in problem domain units" was almost always diferring by a constant factor, since there are finitely many basic types and their size is bounded. In Python(3), even int is unbounded in size. Then what is your N - number of ints program processes, or sum of their lenghts? Fifth, Python is very lax with memory sometimes, especially when you use closures or customized classes. Too big data structures simply don't fit there, or Python isn't optimized to handle them. Much more often than in classic complexity, that famous N where g(N) finally overcomes f(N), is just so big that both f(N) and g(N) are completely unreasonable. And sixth, that whole business with complexity classes is what happens when mathematicians (I know, I am one:) model "real world situations". Then suddenly, transitivity of logical deductions becomes the first priority, and since "everything is equally possible", things are just turned upside down. Multiplicative constants don't matter, since we like to have just two symbols in the alphabet. Finitely many values of N don't matter, since enumerative combinatorics is much harder than asymptotic analysis. In fact, let's put all polynomials in one class, since we don't want to commit to any particular computing model. All of them, assumptions nice and shiny, but completely disconnected from reality. Nothing wrong with this per se, but results aren't really applicable in the real world, unless you have an enormous amount of background understanding. I know the theory, believe me. I've studied Sipser, even taught from it. :-) I just want to urge you to look at the bigger picture sometimes. Like Hague says in his wonderful "You don't want to think like a programmer": <blockquote> It's not that any of these things are truly bad on their own, but together they occupy your mind. You should be obsessing about the problem domain you're working in [...] and not endless software engineering concerns. </blockquote>

veky on Feb. 24, 2014, 6:03 a.m.
BTW I just knew our never-slepping ex-microoptimization convert admin will give this one a +5 the minute I click "Post comment". :-]]]

nickie on Feb. 24, 2014, 7:18 a.m.
I agree with everything you write, only I don't think that any of it can be used as an argument that "1970's complexity theory" is not relevant to Python or to CheckiO. In brief: (1), (2), (5) and (6) are true for a much wider context than Python. For (3) I am generally assuming that sets and dictionaries behave as O(1), which of course is not true but it's usually close to reality, as you say. For (4) I am usually expressing the size of input in terms of the input data as perceived by humans (integers, not bytes) and I agree that this is not always accurate (e.g., for bignums) but for most problems here this view does not change the result much. Especially for (6) I wrote <a href="http://www.checkio.org/mission/median/publications/nickie/python-3/on-select/#comment-outer-9146">a few words</a> some days ago and, as you may see there, I struggled rather hard to find the "famous N" for which the theoretically better O(N) algorithm for the median performs better than the theoretically inferior O(N*log(N)). I agree that, in practice, it may not even have been possible. But there we were comparing O(N*log(N)) and O(N), which are quite hard to tell apart for the reasons you explained. For the building visibility problem, changing the algorithm from your (excellent) six lines to O(N^2) by "omitting points where nothing happens", as you say, will have a tremendous effect on how fast this will work if your coordinates are large numbers, even for small values of N. And going to O(N*log(N)) will make this practically work in seconds, rather than hours, e.g., for N = 100000. So, let's agree that it's all a matter of how and where your code will be used. I'd much rather have your six lines over anything more complicated, if I knew that the test cases would be small. But, especially with Python, one tends to overlook the way his or her code will behave when the size of the problem increases.

veky on Feb. 24, 2014, 9:16 a.m.
<blockquote> it's all a matter of how and where your code will be used. </blockquote> Of course. The big problem here in CheckiO (it's not the problem for me, but it is for many people) is that tests are either not planned at all, just somebody haphazardly piled something up, or at best they are planned with much less effort than tasks themselves. I had a few ideas for fixing this in principle, but they would require big restructuring of CheckiO. So, we don't actually know how code will be used in that sense. Even worse, now they've started adding new tests to very old problems, where we've constructed many interesting solutions that use lack of tests in fascinating ways (see, for example, how bunnychai geniously solved "how much gold":). But what we do know is that code will be used socially: as a quality "meat" that so many social networks lack, as a campfire to gather around, to comment and tell stories (like these:), as a playground to playfully show off our skills, as a blackboard to teach everybody willing to learn, or even as proverbial "weather" to talk about when there's nothing else. And until CheckiO gets its testing in order, it might be all we have. It's not a small thing. :-)

HubSpot

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.