Gallery creative solution for Count Inversions by veky - python coding challenges

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

Gallery solution in Creative category for Count Inversions by veky

count_inversion = lambda s: sum(a > b for i, b in enumerate(s) for a in s[:i])

Sept. 5, 2014

Comments:

sndnyang on Sept. 5, 2014, 1:13 p.m.
yeah, though the enumerate function is a builtin function, it seems that I'm not familiar with python even the "builtin" module. A good solution. I got it.

veky on Sept. 5, 2014, 2:27 p.m.
There are many builtins people don't know about. <a href="https://docs.python.org/3.5/library/functions.html">Look</a>. :-) BTW builtins is not a real module. But this doesn't matter much here. :-)

acman on Sept. 5, 2014, 5:13 p.m.
really, better solution use enumerate than range

veky on Sept. 6, 2014, 1:38 a.m.
Whenever you see range(len(, you should probably use enumerate. It's a nice rule of thumb with very broad applicability. ;-)

metallidog on Jan. 23, 2015, 12:21 p.m.
This statement just made it click for me on enumerate. Thanks!

veky on Jan. 24, 2015, 9:21 a.m.
I'm glad it did. :-)

jkibbe on March 14, 2015, 4:01 a.m.
When you read a problem like this, do solutions just pop into your head without much thought, or is there some sort of process that occurs (pencil/paper, multiple iterations, etc.)? I'm just curious how much thought you put into your elementary one-liners! :) Thanks! Jason

veky on March 14, 2015, 3:10 p.m.
It depends a lot. Some of them, I really do massage quite a bit, usually when I'm trying to squeeze out that last character of length. :-) But not pencil/paper... usually it involves a Python interpreter, but if I'm not at the computer, I can do it all in my head (slower). What usually pops into my head first, thought not the shortest possible code, is really short. I think it's just a consequence of a huge experience with various methods of solving a problem (which I get from many hours of tutoring children) combined with "best practices" about what works (since I code Python professionally). Also, I shun code repetition and boilerplate code vigorously, since my experience shows it's the most frequent cause of bugs and hard to read code. That also helps with length. Concretely, I think this one was recent enough that I remember how I thought: first, "a function receiving ..." is `lambda ...:`. "count how many ... satisfy `cond`" is just sum of bools: `sum(cond for ...)`. Now I need a product, that's just two nested `for`s: `for a in s for b in s`. But I need indices for comparison too, so `for i, a in e for j, b in e` where `e = enumerate(s)`. Now I need a statement, so I either use a `def` or make another trivial `for` to bind `e`. And that's the solution. It works and is reasonably short. But it can be made shorter. First, I don't need to iterate through all the square of possible indices, just one triangle in it. That eliminates the need for indices for comparison (`i < j` is always `True`), but I still need one of them for slicing that makes the triangle of indices. If I slice from something, j should go from i+1, which is not so nice because of offset. But if I slice till something, j goes till i and I can just say `for b in s[:i]`. And since I don't need two indices anymore, I don't need to extract enumerate(s) separately, I can inline it. And that's the solution I published. :-)

jkibbe on March 14, 2015, 4:59 p.m.
Thanks for providing some insight into your thinking process. I always enjoy checking out your solutions and appreciate your contributions to this site!

prlombaard on Aug. 23, 2015, 12:36 p.m.
ditto, thank you for the explanation I also find it very inspiring to read through how you got to the solution. I assume most people can arrive at a solution using the clear way of getting to the answer. But to condense the solution into a one-liner does require lots of experience. Big up. Keep up the good work.

veky on Aug. 23, 2015, 1:09 p.m.
You're making just one technical mistake. There is no (single) "the clear way of getting to the answer". It's extremely subjective, and depends greatly on the previous background one has. Someone coming to Python from C will have practically orthogonal "clear ways of getting to the answer" than someone coming from LISP. And that's ok, because Python is neither of those. It has its own idioms, and everyone has to learn (and unlearn) something. You could almost say that people who learn Python as a first programming experience are at an advantage, because they don't have to unlearn anything. :-) It's practically the same as "simple English" fallacy. Usually people think there is a well defined subset of English someone should learn first, upon which they can build the language knowledge further. But in fact, the subset of English that Japanese people consider simple is almost disjoint to the subset of English that Croatian people consider simple. :-) It just depends too much on a previous language experience.

Czarinov on Aug. 11, 2016, 9:34 a.m.
I guess I did similar, though I wonder if your solution is better :P <pre class='brush: python'>count_inversion = lambda s: sum(x>y for x in s for y in s[s.index(x):]) </pre>

veky on Aug. 11, 2016, 10:47 a.m.
"better" is subjective. One thing that goes in favor of my solution is that .index traverses s again in search of x, so complexity of your algorithm is worse (enumerate tracks index together with element). But for sequences of <200 elements, it's no big deal.

Czarinov on Aug. 11, 2016, 11:17 a.m.
I guess my solution is also be slower due to traversing. However in your solution there is a need to create an enumerate object... I wonder, are numbers of enumerate created dynamically according to the rules (prev+=1), as you move forward "through" the object? Or is enumerate object available as whole, so accessing data at certain index is faster? Or am I completely wrong about how this all works and just wrote some nonsence? :D

veky on Aug. 11, 2016, 5:36 p.m.
Yes, but enumerate object is created only once (and it's valid for one full iteration through its argument). Your traversing happens for every x separately, every time again from the start of the list. See "<a href="http://c2.com/cgi/wiki?ShlemielThePainter">Schlemiel the painter algorithm</a>" for a detailed explanation of that phenomenon. [A curiosity: .index does have an additional argument which says where to start, but for that you'd need to cache the previous value, and if you had it, it's much simpler to just add 1 to it every time.:] Indices themselves (the numbers that enumerate generator generates) are "constructed" each by each, but that "construction" has three footnotes, ordered by sophistication: 1) The construction time is logarithmic, with a very large base. On a modern (64bit) machine, for all numbers up to 18e18 or something, the cost is constant and practically negligible. [And it's purely academical, since you can't really have a list with more than 18e18 elements.:] 2) The most frequently used Python implementation, CPython, "cheats" by having small integers pre-constructed and cached, so they can be returned without any construction at all. [They are reused, but it isn't a problem because ints are immutable.] On normal (non-embedded) systems, that strategy is used for `range(-5, 257)`, so every possible index here (from 0 to 200) is included in that. 3) Even if there was a non-negligible cost in constructing that index, that still wouldn't mean your solution is any better, because it also needs to do the same thing! The return value of your .index call is precisely that number, which needs to be constructed. Accessing the data at a given index (<18e18:) is constant-time, because it's just a pointer addition and a dereference (in CPython). Addition doesn't care how big the address and the offset are, as long as the result fits inside the memory. On the other hand, .index is linear-time, since you need to look at each element at a position in the given range of positions, to see which is (the first) equal to your argument. If you need a lot of searches, that's usually solved by inverting the list mapping (by hashing or smart trees or something similar) in advance, but that's obviously an overkill here since you only need those indices in order, and for that purpose enumerate works nicely. If there are any more questions, feel free to ask. [Here is a Pythonic enumerate, if you want to know the algorithm: <pre class='brush: python'>def enumerate(iterable, start=0): for element in iterable: yield start, element start += 1 </pre> Or simply, `enumerate(a) := zip(range(len(a)), a)`.:]

Czarinov on Aug. 12, 2016, 8:32 a.m.
Much thanks! I skimmed through the reply, looks very interesting. Will read up after work and ask back if something.

Czarinov on Aug. 16, 2016, 11:44 a.m.
<blockquote> CPython, “cheats” by having small integers pre-constructed and cached, so they can be returned without any construction at all. </blockquote> Please correct me if I misundrestood. When CPython is installed it creates and saves small ints to an address range in orderly fashion so it can be fast accessed by certain functions which read int+1 from address of add(int)+1 ("knowing" it will be there). Right? Thank you, Veky, for the detailed explanation!

veky on Aug. 16, 2016, 2:24 p.m.
Almost. First, no, not when it's installed. :-o That wouldn't do much good, since those numbers reside in RAM, and surely you're going to shut the machine down between installation and running Python at least once. :-) This happens when the interpreter is started. Still much less often than you write some number in the code. :-) Second, by "certain functions" I assume you don't mean Python functions. They have nothing to do with this. It is just evaluating some number literal (a bunch of digits) that makes an integer object. For example, when you evaluate 523 * 831 + 276, it happens three times. And third, there is no need for them to be at consecutive addresses (as you seem to imply). You just need to have all their addresses in some array, so you can easily get to each of them. But since they are allocated in a loop, they probably do end up consecutively in memory.

Czarinov on Aug. 18, 2016, 10:24 p.m.
<ol> <li>So basically preconstruction only helps if I access same numbers more than once?</li> <li>By "certain functions" I meant exactly special Python functions like enumerate, which make use of iterating over a range. So I'm quite confused when you say Py funcs have nothing to do with that. When I type "a=1056" does it use the table for preconstructed numbers or does it create a new number and assigns a to the new address?</li> <li>Here I guess that enumerate just iterates over table of addresses to get the numbers spread over RAM cells.</li> </ol>

veky on Aug. 19, 2016, 1:38 a.m.
<ol> <li>Yes. But you do. :-) Even if you don't, Python startup surely does. What do you think, how many times number 1 appears in various settings and startup code? :-] Of course, we don't have to guess, we can check: Python 3.6.0a1 (v3.6.0a1:5896da372fb0, May 17 2016, 16:21:39) [MSC v.1900 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. <blockquote> <blockquote> <blockquote> import sys sys.getrefcount(1) 1003 | </blockquote> </blockquote> </blockquote></li> </ol> Of course, other numbers are used a bit less. But still many times. <ol> <li>They have nothing to do directly with this, but they just use that machinery like everything else. When you write `a = 1056`, CPython constructs 1056 from scratch ("assigns a to its address" is a bit confusing since `a` is a Python name, not a C variable, but yes, somehow it does wrap a Py_Object pointer in a structure associated with the string "a" in the current namespace, which is a hash table from the perspective of C) since 1056 is too big. When you write `a = 24`, it uses a precomputed number. But note that you haven't invoked a Python function in any of these cases. (You might say you invoked a `setitem` on a current `vars()`, but this is not really a Python function in most usual cases, and it's invoked implicitly.)</li> </ol> Again, when `enumerate` constructs a new number, it is by executing `start += 1` statement quoted above. `start.iadd(1)` is executed, and the logic for adding Python integers constructs a new number. `enumerate` just relies on that mechanism. (Since `enumerate` is a builtin function, it probably cheats too, by constructing a new cell, and incrementing it from C directly. In fact, we can check that too.:) <pre class='brush: python'>class TracedInt(int): def __iadd__(self, other): print('__iadd__', self, other) return TracedInt(int(self) + int(other)) def __add__(self, other): print('__add__', self, other) return TracedInt(int(self) + int(other)) def __index__(self): print('__index__', self) return self def MyEnumerate(iterable, start=0): for element in iterable: yield start, element start += 1 >>> *MyEnumerate([2,3], start=TracedInt(0)), __iadd__ 0 1 __iadd__ 1 1 ((0, 2), (1, 3)) >>> *enumerate([2,3], start=TracedInt(0)), ((0, 2), (1, 3)) </pre> <ol> <li>I don't think it's just that simple. As we've seen above, enumerate probably does assume all these indices will be less than 18e18 (fast-tracking their increments without going through Python), but it cannot really assume all the indices will be precomputed, since you can have an iterable with 258 elements. :-)</li> </ol> No, "`int.new`" is probably called every time (from C). It's just that that function branches on whether its argument is between -5 and 256 (in which case it returns a precomputed int), or not (in which case it really constructs a new int and returns it).

Czarinov on Aug. 23, 2016, 9:04 p.m.
<ol> <li>True, makes sense :)...</li> <li><ol> <li>Thank you very much, it's gotten much clearer for me! You're awesome!</li> </ol></li> </ol>

List, list and list again

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!