The kind of function you describe is useful, too, of course. You can build something like them out of almost any modern encryption method:

Encryption methods have to be reversible, so you can decrypt; and they are expected not to betray anything about their inputs, so there are probably some that have this avalanche property, or can be patched to have it fairly simply.

We know the structure of SHA256, so we could actually answer that question.

https://en.wikipedia.org/wiki/Preimage_attack says that pre-image attacks on hash function in general only take 2^n time (ie you don't need to look for passwords longer than 256 bits), but I don't see how they conclude that.