from typing import Any
import uuid
import math


def _get_program_id(program: Any):
    """Get a program id from program.program_id.

    This is not an actual attribute of cirq.Circuit, but thanks to the magic
    of python, it can be! If your circuit does not have a program_id,
    this function will return a uuid4().

    Program ids can only contain alphanumeric and -_ so we replace
    "/" and ":" which are common in our data collection idioms.
    Program ids must be unique and sometimes you need to re-try a particular
    experiment, so we append a random component.

    Program ids can only be 64 characters. The following
    compression is performed: the program id is split according to `/`
    and the middle part of each resulting string is omitted to get the
    length below 64. The parts are joined back with _ since `/` is not
    allowed. If your program id is *really* long, we give up and return
    a uuid4().
    """
    if not hasattr(program, 'program_id'):
        return str(uuid.uuid4())

    program_id: str = program.program_id
    program_id = program_id.replace(':', '')
    parts = program_id.split('/')
    parts.append(str(uuid.uuid4()))
    chars_per_part = math.floor(64 / len(parts)) - 1
    if chars_per_part < 3:
        print("Program id too long!")
        return str(uuid.uuid4())

    parts = [p if len(p) <= chars_per_part
             else p[:chars_per_part // 2] + p[-chars_per_part // 2:]
             for p in parts]
    return '_'.join(parts)