Stefan Pochmann

Python

Room rules: sopython.com/chatroom Code formatting guide: tinyu...
Mar 5, 2020 16:25
@AndrasDeak To me it sounded like it's a prefix of a tag, but apparently they mean prefix of the title.
Mar 5, 2020 16:23
@AndrasDeak Ah, got it. Apparently it's only rejected if I start the title with that. In the middle it got accepted.
Mar 5, 2020 16:19
Anyone know how I can write "[*a]" (without quotes) in a question title? The stupid system keeps rejecting it because "Title contains a [tag] prefix;".
Feb 7, 2018 19:10
@MooingRawr potatoes, not potatos
Feb 7, 2018 18:30
@MartijnPieters You have quite the fan :-) stackoverflow.com/users/5904928/jr-martijn-pieters
 
Dec 24, 2019 23:08
Finally done and it's indeed thousands of times faster than yours (although that's partly because you're using Fraction): stackoverflow.com/a/59474026/1672429
Dec 24, 2019 19:37
Gah... don't you love it when you're about to publish and then you find a bug...
Dec 23, 2019 18:05
Oh, I know... I should accuse you of not experimentally verifying your solution so that you then write some code to do that which I can then use.
Dec 23, 2019 18:01
I wish there were outputs. I feel uneasy not being able to compare outputs.
Dec 23, 2019 17:23
lol... I just reread the comments under the question and Patrick wrote "These numbers are irrational".
Dec 23, 2019 07:56
Simpler approach: For given ratio ab/c², find ratios pq/r² and xy/z² that add up to it like this: Let c=de where d is c's largest prime factor. Then d must also divide r or z. So go through all ratios pq/r² where c|r (that's probably very few), and look for ab/c² - pq/r² in a hash set. So it's similar to your solution but could be thousands of times faster.
Dec 23, 2019 05:12
If any of the above is faulty, I blame my sleep deprivation.
Dec 23, 2019 05:12
In otherwords, for a triple (a,b,c) with prime c we only need to look for a pair of numbers from the "class" c. Which is small. Composites I guess similar.
Dec 23, 2019 05:11
Patrick's limit 500000 leads to 79582 triples (a,b,c) with 45084 different c-values, of which 20731 are prime. And the composites don't seem to have many factors. Looks like I'd indeed get many small classes. If the c in target ab/c² is prime, then ab/c² = pq/r² + xy/z² = (pqz²+xyr²)/(rz)² can only be if w.l.o.g. r=c and I can cancel z² in the last term. But that means z²|(pqz²+xyc²) and thus z²|(xyc²) and thus z|c and thus z=c. So pq/r² and xy/z² are actually pq/c² and xy/c².
Dec 23, 2019 01:32
Just realized I might've sounded reproachful/angry/blaming there (can't find the right word). Not the case :-)
Dec 23, 2019 01:20
You get them when you're the author of the question/answer. Otherwise I think you shouldn't. Do you?
Dec 23, 2019 01:02
Btw, just in case you overlooked it, that's me in that complexity discussion and I'm not getting notifications...
Dec 22, 2019 22:45
With "good" meaning diverse, giving me small classes.
Dec 22, 2019 22:43
I'm thinking of Patrick's way. Let's say the current target is ab/c². Patrick would search for two numbers that add up to it. But he'd consider all numbers for it. But we want ab/c² = pq/r² + xy/z², so we're only interested in numbers from "classes" r and z such that rz=c (or something like rz|c, haven't thought cancellations through). You're right, I haven't explicitly exploited Pythagorean triples yet, although they might give me "good" denominators.
Dec 22, 2019 22:24
Wouldn't that make the numbers very large? Also, I think if you do that, you lose the advantage. The denominators give use classes that we could exploit. At least that's my gut feeling.
Dec 22, 2019 22:19
I suspect there's a smarter solution for that special 3SUM problem. I mean, the numbers are rather special, not random. The sum of x=ab/p² and y=cd/q² has denominator (pq)², so we could look for numbers with just that denominator. Something like that. I feel like it should be more efficient. If only one of us was a mathematician...
 
Feb 8, 2018 03:12
For a linear time algorithm, I often make it so that the test time is roughly constant, by using increasing powers of 2 for the size and decreasing powers of 2 for the number. Like this: ideone.com/GsE5ZY
Feb 8, 2018 03:01
Better use a smaller number than 10000 for the large arrays. When you're in the millions, number=1 is enough. The larger the array, the less often you have to do it.
Feb 8, 2018 02:50
Shouldn't take this long, how are you running it?
Feb 8, 2018 02:34
Hmm, that's quite small. I usually try powers of 2 from 2^10 to 2^24 or so, i.e., up to millions of values.
Feb 8, 2018 02:28
What array sizes have you tested?
Feb 8, 2018 02:18
No, they can differ by a constant factor. Like one always being 1.5 times as fast as the other.
Feb 8, 2018 02:07
No, that's not it. But the sorting is done by value, and all but one value are 2. So you have at most two runs, which Timsort will recognize and merge in O(n).
Feb 8, 2018 02:04
Yes, that's the one I mean, and yes, it's O(n).
Feb 8, 2018 02:04
Looks good, though something interesting is missing: That the sorting is O(n).
Feb 8, 2018 02:04
I think it would be good if you said how efficient it is.
 
Dec 28, 2017 23:28
Just tested "0 <= a <= b <= 255" and "0 <= a and b <= 255" with "a, b = 1, 2". The "and"-version was about factor 1.6 faster. But in practice with "a" and "b" being expensive computations it's insignificant, as you say. I vaguely remember testing this before. Not sure why I ended up using "<=". Maybe because it's shorter and because "and" feels meaningless compared to "<=". Or because I just can never get enough of chained comparisons, I love them so much :-)
Dec 28, 2017 23:00
Ah darn, I missed your second paragraph there...
Dec 28, 2017 22:54
But if 0 <= min(nums) fails then my version with <= in the middle will also stop right away and not do the rest.
Dec 28, 2017 22:42
Wait a moment... actually, why do you think that and should be better than <= there?
Dec 28, 2017 22:39
Or I guess min/max could check whether the given source is a range. But that would need extra code and would add a tiny amount of time to each call. And presumably people who are asking for the minimum/maximum of a range shouldn't be doing that in the first place :-)
Dec 28, 2017 22:35
@schwobaseggl Ha, well, if it were constant time, then it wouldn't be only twice as fast :-). Also, how would the range object speed that up? There's no __min__ and __max__ that min/max could use, is there?
Dec 28, 2017 22:35
About your "and should be better" and also about all having the advantage of being able to stop early: The reason I do this stuff is to catch mistakes in data for coding contests, to ensure that all test data is valid. Which means that I fully expect all values to be in the range and thus fully expect having to run all tests. And I suspect that's quite usual, not just for me and my use cases.
Dec 28, 2017 22:35
@schwobaseggl Here I did, yes. Python 3.6.1. Why?
Dec 28, 2017 22:35
@schwobaseggl Well, the iterations are simpler (only one comparison for each value), there's no generator overhead, and no Python code runs for each value. I just measured all([0 <= n for n in nums]) and that took 12.7 seconds.
 
Dec 6, 2017 17:47
Just do it. You're not going to unintentionally correlate with Mersenne Twister.
 
Oct 9, 2017 02:17
@PM2Ring (forgot the @... and can't seem to edit/delete anymore...)
Oct 9, 2017 02:14
Maybe what you have in mind is something like C++ coders seeing b = a with lists in Python and thinking that the entire contents are duplicated? That's what I've seen several times. Doesn't have anything to do with the term "variable", though, it's just that they don't know how Python uses references. And usually all it takes to fix their mind is to remind them of C++'s pointers.
Oct 9, 2017 02:14
Sure, if Python behaved differently to what I expect, that might be a problem. But I'd say it doesn't. I challenge you to show me an example concerning "variables" that surprises me :-P. And you even can use the "variable is a box" model, as b = a does copy the reference.
Oct 9, 2017 00:46
@PM2Ring I don't think there's anything wrong or problematic with calling them variables. Is there?
Oct 9, 2017 00:22
@PM2Ring Heh... your second link explicitly disagrees with your first link. Ned calls "Python has no variables" a "myth" and says "The truth is that Python has variables".
Oct 9, 2017 00:03
Maybe def f(x, prefix=['foo', 'bar']): return prefix + x then?
Oct 9, 2017 00:03
@BlenderBender So? I don't see the problem with that...
Oct 9, 2017 00:03
A much simpler way to do what your example does is simply def f(x): return ['foo', 'bar'] + x. Why not just do that?
Oct 9, 2017 00:03
@BlenderBender Stop lying. Your original "example" didn't demonstrate the thing at all, so the change didn't make it "better" but made it an actual example. Hence my correction of your statement.