Possible for the people tower teaser

PossiblePeopleTowerSolution.py

from typing import *

class Athlete:
    def __init__(self, mass: float, strength: float):
        self.Mass = mass
        self.Strength = strength
    def __hash__(self):
        return hash((self.Mass, self.Strength))
    def __lt__(self, other):
        return (self.Mass, self.Strength) < (other.Mass, other.Strength)

Kg = NewType("Kg", int)

def hash_list(l: Sequence[Hashable]):
    return hash(tuple(l))

def hash_unordered_list(l: Sequence[Hashable]):
    return sorted(l)

def findMaxHeightTower(athletes: Sequence[Athlete]) -> List[Athlete]:
    def validTower(tower: List[Athlete]) -> bool:
        if len(tower) <= 1:
            return True
        total_mass = 0
        for i in tower[::-1]:
            if total_mass > i.Strength:
                return False
            total_mass += i.Mass
        return True

    _towerCache = dict()
    def findRec(atop: Athlete, ath: Sequence[Athlete]) -> Tuple[int, List[Athlete], Kg]:
        a_len = len(ath)
        assert a_len != 0
        if a_len == 1:
            stander = ath[0]
            if stander.Mass > atop.Strength:
                return 1, [atop], atop.Mass
            return 2, [atop, stander], atop.Mass + stander.Mass

        t_hash = hash_list([atop] + sorted(ath))#same top, but any order of standers
        if t_hash in _towerCache:
            return _towerCache[t_hash]

        tallest = None
        tallest_height = 0
        tallest_mass = 0
        for a in ath:
            (t_height, tower, t_mass) = findRec(a, list(s for s in ath if s is not a))
            if t_height < tallest_height or t_mass > atop.Strength:
                continue
            if tallest is None or t_height > tallest_height or (t_height == tallest_height and tallest_mass > t_mass):
                tallest = tower
                tallest_height = t_height
                tallest_mass = t_mass
                assert validTower(tallest)

        if tallest is None:
            val = (1, [atop], atop.Mass)
        else:
            val = (tallest_height + 1, [atop] + tallest, tallest_mass + atop.Mass)

        assert validTower(val[1])
        _towerCache[t_hash] = val
        return val

    choices = (findRec(bottom, list(s for s in athletes if s is not bottom)) for bottom in athletes)
    return max(choices, key=lambda choice: choice[0], default=[0, [], 0])[1]


assert len(findMaxHeightTower((Athlete(4, 10), Athlete(2, 2), Athlete(4, 3)))) == 3
assert len(findMaxHeightTower((Athlete(4, 4), Athlete(3, 4), Athlete(4, 3)))) == 2
assert len(findMaxHeightTower((Athlete(4, 8), Athlete(2, 2), Athlete(4, 3), Athlete(2, 2)))) == 3

My attempt at Question B on https://github.com/felipecao/amazon-coding-exercises, since the solution there appears to only test if the input order is a valid tower, nothing else of the problem's requirements (Neither of their solutions actually solved the problem given, for whatever reason).

I have a feeling this could be solved in O(N^2) or better, but I'll have to think about it more. Also, my memoisation could be vastly improved by being made less dependent on the exact maximum weight of the tower. Perhaps this could be done by registering a range of options, but this would make the lookup mechanism more complex.