from typing import Any
from typing import List


def agent_names_from(input:Any)->List[str]:
    """
    Attempts to extract a list of agent names from various input formats.
    The returned value is a list of strings.

    >>> ### From dict:
    >>> agent_names_from({"Alice":{"x":1,"y":2}, "George":{"x":3,"y":4}})
    ['Alice', 'George']
    >>> ### From list of dicts:
    >>> agent_names_from([{"x":1,"y":2}, {"x":3,"y":4}])
    ['Agent #0', 'Agent #1']
    >>> ### From list of lists:
    >>> agent_names_from([[1,2],[3,4]])
    ['Agent #0', 'Agent #1']
    >>> ### From list of valuations:
    >>> agent_names_from([AdditiveValuation([1,2]), BinaryValuation("xy")])
    ['Agent #0', 'Agent #1']
    >>> ### From list of agents:
    >>> agent_names_from([AdditiveAgent([1,2], name="Alice"), BinaryAgent("xy", name="George")])
    ['Alice', 'George']
    >>> d = {"Alice": 123, "George": 456}
    >>> agent_names_from(d.keys())
    ['Alice', 'George']
    """
    if hasattr(input, "keys"):
        return sorted(input.keys())
    elif hasattr(input, 'num_of_agents'):
        num_of_agents = input.num_of_agents
        return [f"Agent #{i}" for i in range(num_of_agents)]

    if len(input)==0:
        return []

    input_0 = next(iter(input))
    if hasattr(input_0, "name"):  
        return [agent.name() for agent in input]
    elif isinstance(input_0, int):
        return [f"Agent #{index}" for index in input]
    elif isinstance(input_0, str):
        return list(input)  # convert to a list; keep the original order
    else:
        return [f"Agent #{i}" for i in range(len(input))]