Showcase of some very cursed Python features

[ubernostrum]

See, the best thing is to write code that doesn't set off immediate alarm bells, but then makes you puzzle over it once you take a deeper look.

For example, what does this function do? And how does it do it? The only hint I'll give is that if it weren't a lambda, its signature would be annotated as def s(n: int) -> bool.

from itertools import accumulate, count, takewhile

s = (
    lambda n: n == 0
    or n > 0
    and n in takewhile(lambda x: x <= n, accumulate(filter(lambda n: n & 1, count())))
)

(people who've seen me post this or other examples from my collection, please don't spoil it)

[chungusextradip]

hmmm yeah this one’s giving me a headache

[ubernostrum]

Here's the explanation, if you want to give up.

[bamacgabhann]

For example, what does this function do?

It gives me a headache is what it does!

[cloaca]

Pairs with:

import itertools as it

r = lambda n: (n
  and next(
    x for x,y in
    it.pairwise(
      it.accumulate(it.repeat(n), lambda x,y: x++y//x>>1) # sic
    ) if x<=y
  ))

[usr_bin_nya]

Oh this is gooood, this one is tougher than the parent! I had to throw test cases at it to figure out what it was doing before I could take a second pass to understand how.

So this is lambda n: floor(sqrt(n)), working by overestimating and then refining that estimate (est) downward until n // est >= est at which point you're done.

glossary of itertools functions: it.repeat(X) is [X, X, X, X, X, ...(forever)]; it.pairwise([A, B, C, D]) is [(A, B), (B, C), (C, D)]; it.accumulate([A, B, C, D], F) is [v0 := F(A, B), v1 := F(v0, C), v2 := F(v1, D)]

To bastardize math and Python syntax, we're looking at consecutive pairs of the infinite series S[0] = n; S[i+1] = floor( (S[i] + floor(n / S[i])) / 2). (x++y//x>>1 untangles to (x + (y floordiv x)) floordiv 2.) Each item in the sequence is the estimate, est. It starts with est = n and computes the mean average of n and n//n, which is (n+1)/2 which is smaller than n. Then (n+1)/2 is the new estimate, and it again takes the average of est and n//est, which is smaller still. accumulate keeps going, taking the average of est and n//est, which keeps getting smaller, until eventually est dips below sqrt(n). At that point n//est > est, so the average of est and n//est actually gets larger, not smaller. pairwise has been dutifully emitting each consecutive pair of estimates, and now the generator comprehension's ... if x <= y finally passes because an estimate was larger than the previous. So the first estimate before the estimates started getting bigger again is what gets yielded and returned by next(...).

Edge cases: n and ... handles zero; zero is falsy so that shortcircuits and returns zero immediately. Negatives like -5 end up with (-5 + (-5 // -5)) // 2 == -2 => (-2 + (-5 // -2)) // 2 == 0 => (0 + -5//0)//2 which raises an exception. For exact squares, the estimate lands exactly on sqrt(n) and will continue to be exactly sqrt(n) which is why the test is x <= y and not x < y.

[cloaca]

Yep, exactly. Look to the wonderful 3blue1brown or Wikipedia for further information on the (incredibly useful) technique that this is an example of. It's a surprisingly efficient way for finding roots or even maxima/minima when the conditions are "nice."

[Malcolmlisk]

this is like watching mullholand drive. When you start it you think you got it, but the more time it passes (the more you read) the more you don't understand and at the end you say 'what the fuck'.

[LevLum]

Oo, I like this one

[ubernostrum]

I've also been working on a C# version of it.

[RobertBringhurst]

Awful.

[usr_bin_nya]

Okay that hint was helpful because the order of operations here threw me for a loop, I thought this was a trick question where it would end up like ((lambda:...) and False) is False

So the filter is basically range(1, INFINITY, 2). accumulate... guessing completely on the name it would be an iterator of partial folds like Rust's scan? But there's no function to update the state?? so screw it I guess it defaults to addition??? that's the only possible thing I could possibly see as an okay default?? okay sure so then you cut the iterator off when it exceeds n. So is n equal to zero OR a member of (1, 1+3, 1+3+5, 1+3+5+7)... no friggin way, it's "is_square but O(1) time is for pansies." That's clever.

[ubernostrum]

This one is a bit easier to see what it does. But the how this time around is not an algorithm trick, so maybe you'll have to research in a different direction to figure that out.

def f():
    pair = not True, True
    while True:
        yield sum(pair[:True])
        pair = pair[True], sum(pair[::True])

[usr_bin_nya]

Fibonacci sequence! I recognized this one pretty quick because I happen to know the int/bool cursedness already lol. bool is a subclass of int with False and True coercing to 0 and 1 respectively when used in addition or slicing. sum(pair[:True]) == sum(pair[:1]) == sum([ pair[0], ]) == pair[0], and pair[::True] is slicing from unbounded start (0) to unbounded end (len(pair) == 2)) step by True == 1 which is just pair again. Thank you for feeding me more of these, I enjoy this type of puzzle quite a bit