find the celebrity
Great question, though unfortunately i ran into TLE as i was using a pretty brute-force solution. So, here's the official solution re-written in a more functional way.
1 from functools import lru_cache, reduce 2 3 class Solution: 4 def findCelebrity(self, n: int) -> int: 5 g = lru_cache(None)(knows) 6 c = reduce(lambda a, b: (a, b)[g(a, b)], range(1, n), 0) 7 return (-1, c)[all(c == j or (g(j, c) and not g(c, j)) for j in range(n))]
Faster than 95% of Python solutions
Now i know what you're thinking: "this is codegolf!" but given it runs faster than 95% of python solutions, and that some Python devs do actually use the functional tools... Ok.. it's codegolf.. but let's take a look anyway.
1 g = lru_cache(None)(knows)
A decorator is really just a function that takes another function as an argument, so why bother creating yet another wrapper function; might as well use
lru_cache to wrap
knows directly. This is good for speed.
Candidate Celebrity Hopping
1 c = reduce(lambda a, b: (a, b)[g(a, b)], range(1, n), 0)
This is our candidate search. The main logic is to make
b our candidate if they're known, else stick with
functools.reduce with a ternary handles this logic beautifully.
1 return (-1, c)[all(c == j or (g(j, c) and not g(c, j)) for j in range(n))]
Our final step is making sure our candidate is indeed a celebrity. This is easily done with
all handling the simple logic of being known to all, but knowing no-one.