| |
| """Optimized solver for AC inequality.""" |
|
|
| import time |
| import numpy as np |
| import zlib |
| import base64 |
| from scipy.signal import fftconvolve |
| from scipy.optimize import minimize |
|
|
|
|
| _TEMPLATE_B64 = ( |
| "eNrtWHk0l127VoYMmYcQokghQ2Y//J77+iVJpHojRIoQKaXSoAlJooQ0iAwZIpooIiR6RTShNBEq" |
| "kSIpzaes9fadaZ3v/b511lnnnPX+ca31PHvfe+/r3vu+7n0/zwS5QhRzJYATHIwVhVlgr4mB50A8" |
| "3n9Lhuaho0hqyYTO0XgI+e0F35h9yBLahMDnAegWioBUsjGCjlhDj88Skb7TYCG0GE6PLNF1SR9q" |
| "9rqo95PElFY92HC08H77MMmdVURTqBB4x02A3TIW1mZJoWSdOVze6uCArQ5WTlWBVuZojH85HfuM" |
| "7RD0QhgZWZ3knt1KvRse0qLPt0h0kBeOpmEUOlGFiWotY3YpOBCfZyaj9FGGnqUfZl8RkGR2BnVa" |
| "mmfwU9ySUOJ1kqBL774x+mu5KLvmCvNZWoOUPKKpbvNCml6lZvn9+UPtMj4pdtLnlxZ8jy6a/nz/" |
| "iQwRW6bp/F2L2uJLDPdKbuLap0jFNa+YO0s3M7HxPtTRF01RBwfIYI84pu1QRY60CYYHjfFc1wG5" |
| "mq6wHl4BfgcXbDntALEiewhUu0KjNwC+bRH4mL8UUXOXwTTlN2z0YyG9cQGCyh1gqKGH9lpLLHrL" |
| "jYDpenBO1EbPhE80pe8GNT0MJWbKaRqK5MYzyU+0Xl4QvqPUsMX/M70oGgvLUH08yzfDHrY7POZp" |
| "QSOWB8n9ynh09x3Zn9eCqvxEHGjgg54FN2yGb9Lltju0V/YV7Zh1gdxGV5KcWgTdXW5OrXlB1BW4" |
| "iYZ9d5JDeSTF2/CTc4M9BX7gkHfhDlpnd4KUhc/Su3uxBDk/+m1LNAXZ51FRUiR9lg8jTxceWlM9" |
| "iTYYLyDlL+UkxJ1F2yiOQoI0yXB3GCUp76PORbfIYKiWioRrqH/OLmp8VU78H9+S/1oxSEWrY+Gk" |
| "cYiS4EF1hzhelKjC9KMV7q6yg4y/Pfon2mGGqT0GeFwQsmoWVm+dh1NfjGFSKouGoDEw0REBJ0YK" |
| "3xJEoFj4mJTHltPS9/uodWkabeBKp0O9mfRGp5YqCg9QlNdVmvf8DTUO9tKGVB4olQrC7Qw3+tZ1" |
| "Ud9OIVTUyMCrTxzMdUHEPH1N389yYSfPPdLp50Pop2/UdTSVrIdSyUjYl1b7B5C/fQmJNcdSu+8m" |
| "Srs9l+IFpWiFii1xWKK0cLcOHSnSoqr4OvZgUA3DH/qO0a0woyUdMfRy8RxqClagqctMKGGNNa0v" |
| "zqVnZqVU/nEfzUnKoN3zo2hy62lqf/2EIq6dpW3RaZQ4EEbDo0ECjkWUH3yWCie/Iqu7nfR0/zPq" |
| "l/xCbeayKAlQQo2NKZTktGF11RiL38/AkxJCaOhqdKh7Ir9uPgL5bPHFVhGCbEMc656GzWMUcKdr" |
| "Cu5PHwNbTSE0BilCX1AWM8+poK1dEIs39lEtcSMxjRd39iui214VhuPkcPWUMNS2iUCpfgJ8e5Th" |
| "YayBd+lyWLlAATullfDtijHGvFmI+9dYuBBpBUVbNchZK8F87ST0QR69ibKoFu6mhsAyclgYQ/Lp" |
| "O2nWex9q6I6hE6/qGa9NeZblX/tG9NpjP53clxMp120hexkRWjgwl8x0dpGj63XiTq6iI1UJlO2z" |
| "i3IlAylM7TS9SGyhcRadJGddRSETj1HB4URK0b5Mt4c66L1GL200GgVWVzuNeT0WDzUVoB6igdJG" |
| "M7DbVJD6YCIW5SlCVn8S1oqZwS7WDIGGZpDpMESogg3sPXUxg+0K5aVWaGrnwGLffBjc0cbwqAXw" |
| "z52DyKd20G4gPF2hgNYGKch9EIRwHR/W3OODv6YIrHm/04VEYVQXi2GxlQK4WvVh8VQbJadY6KqY" |
| "DBMrOzhYeuKS71rcuBUE0YYVaLq9GHHB1rilvwSnS2fj/B59BA8rI6NGHEJ5Qtg1ZRLWCE7AK68e" |
| "UpZ6SKVnT1PP4TcUq3KVCg4U0elLeXQv+QRJJB6nvTwXKETgOuXppVDm8cukKpFG7x2y6SpPC+kb" |
| "vaXrPnLIHS8OxWYt3GC00dxngWDOXMSYOONbjgMYhdmovToHBSddYSu2CDmrPNBu5oxSXyu8s7HE" |
| "RWEG/dkctCp747PyfNxycoTD9YVI1tsC9eDdYH0Ow5fj6xC+czUuLVqFB2Lr4eS9Gt/kdsHjjhs2" |
| "tXvBz8Mb2+YGQXW9Heo0WXAenIwwaTXsmq+NxAArhOzXw6ErNljzcRb8HKYjoPMHx1lakP+kDLVi" |
| "czxr04Z1MAcJZ63Q+MoaezR8sMp6IS6muqJ4yyzME7KC9mNz3D88E25j52BFkTbuXJqOUbZCuMWW" |
| "RnrzJXqld5jUxx4g0WcqzB93hFJYLuurejITO6WKcZTwYs+yFmXXHx9FiplEdg8CaSFnN62Uu0Er" |
| "mqso5qAinux9T2H6klgybTwMDwpg/GMlVJlOQPFWEShUqWCwTwXi1jaILGAjR0kdT94A1z4aIVZN" |
| "G23VLHDYqhiS00DuLTZe9rKx0moWLBf6o4/lh/F6AXix0hXXo4CN45bAWcsPfcrBuL3oILjm7sH4" |
| "H1jSvQs9yhuR8rsTXmxxwfFjJhBOnQHVQQOY9syEhZoz4GqCldErUFxuiwV8LJwMN0RErQuGPm2F" |
| "qLAbmMkuyB3YgRMaMZiiGwKnTUsgqjoVy0vksez6Enyr1UOpnCy2FH0jUYupyB/VQjrTw41WnYw0" |
| "+mPf/lFEt49hfF46UlV3FMn5LKEKgyKaaRNBcXNjScx1L+1+U0xZUfXM2vVLyWsTH5nJ8jBf3NPo" |
| "SNRd5nd+b5KzkwaMKkjnSB7pxkmRsNEDJtrtMk3KFIBZhwnkvnZQ2BtJPBrSwt4pTynRVx5VhvdJ" |
| "74A0BX5NZ1PaGcbf9zIjyr+TAt8aU/D7LIZKUmhXXRYdZMlCZK8OmLNn6FngW8p2mIpbj9ThL+QC" |
| "lmAA1kZNRvgkTYRuU8Ewh42bPl20aSEPNjdJMQa3uxhRpcu0+u0wOy7kKP309VzvfGrBDerdl0bb" |
| "eQXgKDIN12bNh4xMEOadWw/pNeuQt+IIrpllwb6vHLx1udgpkY0x24+Cvz8H0QIZGGw8j6E1FRDu" |
| "OwnPYxVwtEmEq344CtSWwX19PHRKF8KhLJFxq5TCYd1jOBwcgsX847G8yZ++lwZSp00cDhUcZUbd" |
| "WWG5aYc8espejnCr28+GwE0T7HJXhsOTfnq4Tg1SRY3k6j4W7RP7yGRFCom8+UxWwo9JQUIDYUdl" |
| "4GD4hY5tLKblzbfpvPE20jQJI4OS42xZR0fGpzCJtinLkvHp6+y0/gzLpjtbGZ3i4l/6UmtcykTO" |
| "PcVsiK8k7XIpWtydONLXaBBkJuSua/qfxUrLg0rG9XwNpfjfYTafi4OoaRyGTWxx08STBCpjRvwY" |
| "9ghjeGdFEbNSgNz3mVr8MXZ9pz6TzGXJjjBOh4/+Bbzo3QhR+UBKUP+b5k8H1TOKRnuZzux2JpZj" |
| "T2ryr5nymmJKeRFBpUEHqXmaM71USWZ4EweZNTcPMc3PY+iGRzCT6CRCY+JszQN7C1k/54l/22Be" |
| "GDCd1G5cYj7clCR+wzzGI/ol8zXeghasEWAPtE6nRT7KZJNxkyYfe8LsL9/CvM/MZP8cu7QH7D/4" |
| "BN+R+8Xt2kvWSLvTrNvswNnxzDozTUZrjtqIz6Jf9WnHORNqaGOT72VbZuNXYtaOnsdE6d9k7KNi" |
| "2OZGGSPzZO3hYrGWJzIiTo2/1ugV32v5z2r3H8Vu7xLTP2M38baiuZrWecs34zwoR8SGpqsdoObY" |
| "V8yt4UCm9v56mjNVmhbbPhnxwTDyIRNe/ZrxE333y6fWkARSHa9IkRt4saXHnSIk0slveS0NZDwm" |
| "/ueToaleT6HSPlRsepvGJjrT+4FPVJQshbdWRynJ8yTDCbhI+bn5ZF3Gh99kDKlQyo58X7szvgme" |
| "5FjYTyevTULBo+f03fchNX0rJ47KOWpIrabh9FdkHHWMJo4tJdu42dTYXUROXLwkK3aarvzIbybJ" |
| "d8kuI4MGqpspRa+GmgavUKf0LXpRmkqOc2/TqL5q2nCslGR/5DJho+OUru5Eb8Kv0Ju6UyR6spU+" |
| "hzQyy9VT6W1DODnPGw1xRUGI3/xCEU5nKcxFAkrTemix6SR4rnxM0VY3qe5pII1JqqJO0ySylHxJ" |
| "2TqJJNlkRJwtplTKWsI8fn2W1s/ZQyzPFpISz6dMlxrq1c6liWOaaEJ2NO2SPk/szD1UE5pL9c7b" |
| "SOauPaXWplLJGC86uhbk83AudRXupjcuDClPyaT+VxGklJ9IYslHKLomkwz8qilc/CgtKcik4dXp" |
| "5LAtn0abX6T9Q20kOj6GrtcGEO8tJSp1KKWw6DDyLr1Ei8TcaMaC+bSltIAU5T9RTH836U67QdHP" |
| "jxCLL4YanvWTmncnqfCUU/DL/aT5oZCRy8mmpbmp1C5w8kfbWApOE6eZF+JJ3SGHVLKvkW5tHj1Y" |
| "nEr30qsoa98VOnG1jYS87tHU/oO0XyeeNrXsp+3Gu0moN4fSst3o6L79FB4hTt0Nq2lBqhctP+9H" |
| "UzbFkk/MIap19qHKxjNUKTOaEtze04QcNSpfXUKOeRpM5ujtNC1hBhO4LoW+8VoyUX3rmZuh6pa+" |
| "a2qZ2KJsxm+rBB2aIzCixZ2fvUe0mzdoS971Z5gVh0PZ0ybfZ3jFZlOUiDF5ePeM2NX76v7KAVrc" |
| "LUzmonr2gKa/2XLjRsvG9q0jfdHTNtG/1s+ZKEEq+nE27x2SmMreJKZsD/eInZfhbYv/Ka3/hf8Z" |
| "SNjdMN8wjWXeGVbPdlRqY/9v4FTr5Ph3eayOmcYuKdRjh2in0dqNLeTh1kn5+clUbyqBukp1XO+a" |
| "TTfz5eEXfpCx2niQunyi6cQpXcr+3kCvf+QV1u4HxO83Br9/UEbWy5WQsbJH9CMfbORw4JNqgUiN" |
| "9YhaQAhaFYqxOs54NPkp0Z3ZiL4mjh2TDjK4bI2sDWbwXULosumn45cl4JcRiZMzdWDvfQIPqrch" |
| "NMUfMibecJEMQITeAiR7bcWXl/4It58BxZNmcNrugPPcR/ElYi1++uQzTwTxCXPoqDI/qhOWY6pj" |
| "NFqdLsKE8iHRlIbEPRUYXLkHkWeKkH6kh5Y6bID7g/m44TETaeG3caXlEvJqjoErPxQnEwJJcp4N" |
| "Y64xBU5Cp7HeMxZJXuUYG+KNZPcmxMySxcqFB/BCVwwKylK42vwb8ebVs69In/o3uaDj65DlMoVB" |
| "I50L0rit/QkGHV/QWCnA4Xmpxzm0J+OXrbVYBoVxT8SoJ2tQxr8Whrb1cN9KuOeyBgXPk+DeG4c5" |
| "E5rhIVABl2ca0ODSJd8DFqgUtIfdADeStsVTzYWd7OtGu2mz9gbU+U4mfsdXpGovC3VVQeZpZDg2" |
| "vPlKfOKC+DMxdEz3G7sk29Ei50U0rdi2GqkP37Ef1OkyWhE9xJ9aTE+Los23yTj+qXiPUE78VePo" |
| "6gyjIE2CUZ17kKlsEeGI6fJxwmrcCJecECa5GWO3+Y3kyi8920f2xiw/ihSXdYzULWW75OCTX0O+" |
| "7dkjfZkL3jFswwe0Sm4aKerZMW2n9pqqjTIkHw+l/8Ar8cVV1t/jKZ59gf0t5RYpP/BDSOLlkTUi" |
| "tl+Ab8aPTzeps7C8yI/9HSpIMtoH42/LcDqLhV28X+jxcTbkvSYxNOENPS/ooZYhC2aViwz6JwRg" |
| "1ckoHO6IRcWzCgpUuEwfBbdRyGwJaMWfg+XgDhQ+noXWgh6mzf8YlWkuQ+8UR4zWi0W3eSWpfnVE" |
| "w+7xOGRmDe4qSbgl8VqKVacY/uQ1oBtpuDTsLHXed6CU9g9k5CeGd6IOCB43FubiTTTqlDAduaeP" |
| "pAIOzh8xwc0pHBzvuGjo4MyM+KUWWUZpVx2ptGq84XyVReQ9KWBk3ni9QHqQrEKpStoU8XEH/Znz" |
| "XRKwh1UcF2Xw8/legKK5kEczox2TQFdE4kbGX8gOZv9/yvlOJ3KZGaPXWGoGjaMI84hfe5TYls+k" |
| "lh62iLO++k/562m7ksyEfzP54523edDwrzv2/x7q3Pgtxrm1/6obp67Zzna75cMsd2llJvFJGvxX" |
| "Y31ps3nH6uPmStU5v2rF6ckDBn/t69/glS5qbnPoDGnWyDAly62JrXXV8NqmBObf28WnKBoHJVaM" |
| "6LOadZFJv6ZgpD27zxLaN0nww0FLh6spFgduyJv/7D8rexCM2MaRe0r7riIJV36n+5u/s4xMQtFy" |
| "vJmptU2n47biRqmNQ4x3Tj5JdIWSj5fayBl5b5hhGeTYRA4hu0j9YwsN/d5NZvcmGp3lfURN+3eT" |
| "mI06SkTdsbmIFxe/auHtpzxm80eGmZO4m7gy5Yx015dRhqA9m8+wlSrO32KkeQYtQi1MWHGpXKZX" |
| "XbrJUDqHMupMcP+KIOLyZ8Oyoo+eKjub1Ts/Mf4rHv4c8k4KG4X2GBnV9yZDdMcxlM7ogvy1GITs" |
| "SMCFV3kjNdFc6634PDRI90y7jfdyKZOW++//rf9msuoLLFL9zo3EjJJxhsV9IU2SmPHEkrtel/Nw" |
| "oxGnZe5LLLqsz6lNKoVd5TM8Xz+Zc+TTXfT45OGD0QEoWxvA6UAvFj+9DY84JU5Osxh51vlbsGax" |
| "GdesZJjZv0VU2wmDrZvioV2ihQXPNDiqMwM4AnymnKQPCeZLXLsgGDQaF1y0OAbGRhzejEIs4llt" |
| "9pPPo8kBaAqqxHiFt6QStxgL+d2MhjyS2XkaPXR/jgx656lxwnPL8CpkJufKvAFq9+RhO+fHMmOO" |
| "yjM5egIj95SrqJb5hC9N5vWdA/BKN+RsWRnP2VIRA0mlD+B9O57jPnmIMe12NVMoW/BLq1G/HRrJ" |
| "bf47LoycgZYxi1O25yGnW9J1xr8Av8FvnQ==" |
| ) |
|
|
|
|
| def evaluate_sequence(sequence: list[float]) -> float: |
| if not isinstance(sequence, list): |
| return float(np.inf) |
| if not sequence: |
| return float(np.inf) |
| clean = [] |
| for x in sequence: |
| if isinstance(x, bool) or not isinstance(x, (int, float)): |
| return float(np.inf) |
| if np.isnan(x) or np.isinf(x): |
| return float(np.inf) |
| clean.append(float(x)) |
| clean = [max(0.0, min(1000.0, x)) for x in clean] |
| n = len(clean) |
| conv = np.convolve(clean, clean) |
| max_b = float(np.max(conv)) |
| sum_a = float(np.sum(clean)) |
| if sum_a < 0.01: |
| return float(np.inf) |
| return float(2.0 * n * max_b / (sum_a**2)) |
|
|
|
|
| def _load_template(): |
| try: |
| data = base64.b64decode(_TEMPLATE_B64) |
| decompressed = zlib.decompress(data) |
| return np.frombuffer(decompressed, dtype=np.float32).astype(np.float64) |
| except Exception: |
| return None |
|
|
|
|
| def _make_lp_obj_grad(n, p): |
| def f(a): |
| a = np.maximum(a, 1e-12) |
| S = np.sum(a) |
| conv = fftconvolve(a, a) |
| conv = np.maximum(conv, 1e-30) |
| log_conv = np.log(conv) |
| lcm = np.max(log_conv) |
| lcs = log_conv - lcm |
| exp_p_lcs = np.exp(p * lcs) |
| sum_exp = np.sum(exp_p_lcs) |
| Lp = np.exp(lcm) * sum_exp ** (1.0 / p) |
| obj = 2.0 * n * Lp / S**2 |
| w = (sum_exp ** ((1 - p) / p)) * np.exp((p - 1) * lcs) |
| G = fftconvolve(w, a[::-1], mode='valid') |
| G = G[:n] if len(G) >= n else np.pad(G, (0, n - len(G))) |
| dLp_da = 2 * G |
| dobj_da = 2.0 * n / S**2 * (dLp_da - 2.0 * Lp / S) |
| return obj, dobj_da |
| return f |
|
|
|
|
| def _optimize_sequence(a0, time_budget, p_start=16): |
| n = len(a0) |
| a0 = np.maximum(a0, 1e-10).astype(np.float64) |
| bounds = [(1e-10, 1000.0)] * n |
| t0 = time.time() |
| best_a = a0.copy() |
| best_val = evaluate_sequence(a0.tolist()) |
| p = p_start |
| while p <= 65536: |
| elapsed = time.time() - t0 |
| if elapsed > time_budget - 0.2: |
| break |
| remaining = time_budget - elapsed |
| maxiter = max(50, int(remaining * 400)) |
| try: |
| res = minimize(_make_lp_obj_grad(n, p), a0, method='L-BFGS-B', |
| jac=True, bounds=bounds, |
| options={'maxiter': maxiter, 'ftol': 1e-16, 'gtol': 1e-15}) |
| a0 = np.maximum(res.x, 1e-10) |
| val = evaluate_sequence(a0.tolist()) |
| if val < best_val: |
| best_val = val |
| best_a = a0.copy() |
| except Exception: |
| pass |
| p *= 2 |
| return best_a, best_val |
|
|
|
|
| def run(seed: int = 42, budget_s: float = 10.0, **kwargs) -> list[float]: |
| del kwargs |
| rng = np.random.default_rng(seed) |
| start = time.time() |
| deadline = start + max(0.5, budget_s * 0.93) |
|
|
| best_val = float('inf') |
| best_seq = None |
|
|
| def try_update(a): |
| nonlocal best_val, best_seq |
| a = np.clip(a, 0.0, 1000.0) |
| val = evaluate_sequence(a.tolist()) |
| if val < best_val: |
| best_val = val |
| best_seq = a.copy() |
| return val |
|
|
| |
| template = _load_template() |
| if template is not None: |
| try_update(template) |
| |
| |
| remaining = deadline - time.time() |
| if remaining > 2.0: |
| n_t = len(template) |
| a_refined, val = _optimize_sequence(template.copy(), remaining - 1.0, p_start=4096) |
| try_update(a_refined) |
|
|
| |
| if best_seq is None: |
| remaining = deadline - time.time() |
| if remaining > 1.0: |
| a0 = rng.exponential(2.0, 300) |
| a_opt, val = _optimize_sequence(a0, remaining - 0.5) |
| try_update(a_opt) |
|
|
| return [float(x) for x in best_seq.tolist()] |
|
|
|
|
| |
|
|
