| |
| """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 = ( |
| "eNrtV3k01vu6N4QyRcZMiQzZ5jLzvr/n8ypECUWUKVEhRXPsNhmKiMwliQgVmkklGUoaFGmguVQ0" |
| "StGg3PZ71mmdu/a9a+9z7/3jrLvOH8/6ves7vM/0+TzP881SqsY95EC2NBIRO8pRpp+GKSuyYWhf" |
| "iB6ffPx2sQyV1dmoLUtByJc0eHpvRO2iCCw+twVPdK2ws2gG1toCKq6GSEr0g9oCgN1sivfsqXhe" |
| "JYuyPVPxq7YhlDuGqSlMFRPfisEyZCIuhbJhFSWH7x1s1OZPwYFZxlhtOQkn5wlgQ68pNgfPRkyb" |
| "BK649NLxlHv01eM+tdfcpLWvRmN/YDwllGoxTnvrmR5bTzJo2MN0CSgQS6OU3T5xHLPaZxy7iURo" |
| "WWEszT0iTV8DeeicIR/dWXyeec5nQGvTUklH1ZNuG2+wiYhwsZBzvcIq25rO8rUZtBh51q3/u0im" |
| "OTAWY1VZIqZ1TCtbiHybVcn2VD/zdWcsMyE/hBILt1Hqio+kWieNgrlasOy0wjhLK4iazsEAny+G" |
| "2sPgru0D75454E93hZmWH3asigC/diKuzg1CllAQHgR4QkCJjcN683CVby7sP05BvNOPWIoLoVZ+" |
| "KlRnGEOh6xvFvrpO/EviiCftGCXsH4WDrd9JQEgMtRnaSJn0ndaFjIWArRm8Ylk4kuqP4uMGuHtc" |
| "CP1p6uCkfSFzJUMEsDSQtmkM+GYIQlq3gw4dv0k5Uv3UGnmS8LWBvmxMom89DL3OjSRdgShy0Yuj" |
| "GepJNF1ShExGu1Jk7nQabtlE7tGlFKB0jMxEMmhleDjle6VSo1gVCfkl0fMp8dS0T4iOOU6ikcfu" |
| "VNzaSMLTy6hiKJNopz69nB1PN06l09GgDiqsukx+3S0U4LSFfNwbqcFziGxixuHVHh3cUlZAzE1B" |
| "lCZKI09bC5IVDlgr6Ar2VFfIx7tA8ZIrDHy8YejjhGdJcyBxxArL5ylhUsQY1MpJQk5eHpsLJLHJ" |
| "9zF5x5yly4szfujeS1eFS2hnfxnNH7pMlasy6YzABZqy5AMNJPRT5XYhOJWKookRxAvxF2RsLo4W" |
| "8/FY/EwKEjLimKgwQPqx/OgT76K8EGHIXuDBBI+95KlVQg0tK+jxcAQd9DlNci8yiJ8dRQqzPCge" |
| "0uT3eCZpt8qQtKkR9acb0eZfLrPVN15mdn78wFh/ZcgjPpUOjnGjkyYTyPGFFVk9cqSiUQdpQWo9" |
| "CVakkcqiUhqZk0zhbofJ7MZjKog/Rv6PS6goIJ5kn0+nwOZqmh94nFgP35LD5l4qv9ZLjV9GKGO5" |
| "IipZavjOb424uUb48uPbmGwPeeVpUMtYiQXWi7H0oAdsls1Cm5gq1nSaI17UCPWFKkjdrYs1+8ZA" |
| "IVwMfqMmYkaAAp7ETII7rziE4/sp/50A7suOxjVFVZhVaYHpVkToEQn8kiMJsfNqmHZQHc2uesjI" |
| "UULpVFWMvauK5FOWKLfzgpQ6G1pLHLA4UhuJShNRcFoTSROUsWuOIpo/viLDsjqqmZFGV+PjSfBZ" |
| "KDFd2yhtbSfTNK+Oda39CSsw5YzNhSOmdD95Gm1cHE03jERpvZw7ZbM20/Wjl2gq7wV615hDH+4n" |
| "0DqlSLI1Okpxx7uInj4j6/5m8vqUTxecdxGvbj3Z1z4nfsk35NLHjzGlPVSEsZh6SwXNUXqYJcfC" |
| "jfUaOJCniURtVag80cSzSBs4x7AgvN4GfVkWSHzrhOCSKbjx0Ac+Qg6oe20HxcG52NhpDMXZ7ri8" |
| "fjYCN7tgyt7pkHNQgfF6eVRqiaHNXhh9vGPwtEMC24L5oFM0Fm6QwmUdVdgLmuH1MyO8+85C7VQd" |
| "TI+djUm6S5BTtgaP0tahKjIMMZZ+2DLdCc+LAnBy/0yE2ZlBsWYStn+WguATMRTGa2LMOjUMKL+h" |
| "rjv3Kdv5KHm0DRBnzgVKNztJu6SryDyllOKGimjpqFPEe+USya8rIrbYWYpQ3Ef8D8vJL7OLeKU/" |
| "UbyBIgYeSUP5hAHEzY0xPYjByGQ37BvnjdfX5iDadxZaK2dD7oAvhCYvwEXlQDif9sbW1/bYWEhw" |
| "22KLntppKDsfDMdvHlAYnAcpf0+M+P2GndpJaM9JgLzDBlz5GoF5/hGoOb8ezgMr4aCyBbEO/kjO" |
| "XYqNSiHQXL8Wm5VcIJrCRnfpZNTWa8GIZYR5cQ6wiDNBLv9MWA064WKUCTgDhOPbDTDTSAPzOWw4" |
| "+RrjSpMdmFUOKC//UTPcgsE7Mg/jkvyQJuuEqpgfeNzDxjs/B1xvnA2J8cbIXW2K7dfFsWipLI4I" |
| "15OuRj7hXhptCjZh5EzWWv7eI8aVlZmIZhczB85dYPQdE9l7NNOsFm8SIHEDe7qoFUFK+Umk/vQa" |
| "SY+cp295qrB8+Jk83sggYoMKNt4UgfqCiUgRUMODgnEotJgEP0UNWP7Ia9dYWyiQDoys7HB/oSUe" |
| "vTKErCwblz9qYbeRHso9gbAVtug46YitOcuhdDoMB++GQ8DUD7Vbp4EvMACDNWGQLIiEj24unskk" |
| "o/u3rcgb2Yw7whvhrj4fZqd9IPrFCtuC7FHMYwGRwBnY0LEAA3U2sHNcBv9sZ/CXsXCiyRwzun2g" |
| "rBmD3OP+EH7pA8X0WLhGpEKqMxpy/AHgv6YL2ycqaDzgj+rZJoiYqIjU7XywHq+Hp7/ept9jpft0" |
| "ounfe+s/K1vu8TNu47zp4puttPz6Ynp7qYZWlm0hb5NMwpYU4kk/TS/GdjJ31iyi28sFqW6uIGOU" |
| "sJcqHnUx2wLD6MtKecxKa6A5PhX0vH48SW9pY2JHGilIQRQPjK2RO9hDcbflULLYADXqTym0Rhki" |
| "xvdIVUqJpsWuZtv1HmG2sM4zhtdiiMeNyG1sEXPoWQklqJbTyB5FqD4zhk35USpOGaRRYvqYYK+D" |
| "Wj4fLHoXjqE1kyFiZIBPm9XgoQF8KnpJ0uqC2HlAmjkk2sdcYZ2lRhkJxjs6nxunG3kzSbaxjXa3" |
| "lZD9ZxEkuxhBP28ujO6tQ2f2ejSM2QD56btgZ12OcaENuB1TgW/J+yH0Wz70ow5gVOg+0EA1zh5q" |
| "QPWBgzAebsRqux24fiEeb6sCMS49Gw8UPDHhyAFGIkwWn/j2YPWoaFQbT0DMylCapxdML+WzsWjt" |
| "HkZVCayBRGW48bzj2la50hY2+y3BU6aBYYMh+vZFC1HlV0m7UwwdoQOkp7uHHq3gRej+e7TNVx9f" |
| "1ytAKp4HqsG1pHO/k94cjqXEh/EkVpDPnjyPmILwAtJuliXTl0PsIPEomzHtsczOyjomf5UVdw47" |
| "0h/A2D8vZdYkNpP1MSVyWJjB/BlWNO5eZ87XttLekCbGMCQL3sZZ8OV3ho59IB2fn871w/3RYia0" |
| "MY2YGyK0/NcA1t/vRjppMm93hbMv3SiG7K2TcOKLAn/XBqqtM/2p9yGrhYmTyGS0HJ8zwRccqLHn" |
| "NRNje5oeFSbRJ5scUsN8qnY+wBy5/5a5a1XCfNTaThpPQ5jpDZJc3W5rZGx+/0p82WftomhMY/a3" |
| "MEmLZKhG+BBzPmCI6c+1oIzi3ewgQSP6pViX+r2ukfuNu0y7VTTjeaiA/fvdntRl7L/bk/Hr5J+2" |
| "FXi5cde/C5xiL03PYTKVGObuHCWu3ttrrKiln0MiykS5q10ZX9YMhjXLgymou858m3+JPWl7Ovd/" |
| "nBLWWpirZjEKPk9+6hixPMj6n3L3d0kdxWP5UkzU4q+cfTjqq9lfOXe/sd6i6uh2VoOCN71pcCf5" |
| "6HTSkX3HiPOEMCGDkfSLoxI9aOnj+iCV38ksPM1DV+bu/+lT35VcchZQoydKQjDfHkpSRnvI3eAy" |
| "lQQ+oKmtv+CLWRu9PLucHCVuksWuIKpvHiZhKzmI1u2kQMVjDPtyDb0yPEwzzwjhoxtD4Qru9KDH" |
| "inERDaO90Z9ooFUDwQ1PSSv3EZ1IOUddjkdp6ukL1GD/jmz1ikjcuZ5E5BzJZXs1mXtJ0SLWUdI6" |
| "kEI5Srdp55diSt5zh7SSL5L3w0ZqO9tOCfJ7Sav1Jg3/0kJqFmeoXaWKAnoLSeisDzWEt5CLXwV5" |
| "ND6gvRpXmCnVe2jx1S2kNEEAkifE0c3Li/cjR2gzyeDU91c0tnQS+EUe046hDuLXXUFZghfo88UC" |
| "shPvpwbspNinZhScZU3Nk+MYg7OHad1wMqX23aTZcYdJtKSZjGdUElXeooaNGVR/5cdskZ9K1eLl" |
| "JF8VT9Las2hGfgmVd3hTnbQDta+fS1kSSfT1JIseKJdRYctWYnXn0vjt+eR3p5RK5Fspa2Ye/epd" |
| "SrK1JTSmv4ImnjhFOz71UPfMVFonEUG8PZqUdqGePlfGUd+js+TyYiG1tXpRzaoqyu76SnO9X9HL" |
| "8Z3026adZN67jc4GvqO0Ha9IUr6BDqlnknjSCeaOfDkZV+6l/LsHyDZThgxdxUlULouMVlXQ/dUt" |
| "FBd0hPI+F9L6R+dpzIMGkmW/IPmIO6Shk0uftbNpnHImBUQkUspvFXTl0EIK4t1ODU/lybBqJa1a" |
| "tpTK2peQj34Ofe7MoFae1RRsXEXnXowhk7ufqGlAn4Y+nCTe5GmM0Osoqr+9kJn7Yw69+SGU6bTz" |
| "ZU5OVmA/vl3LRGnlMzmCE2lbrwwTudPdfK1uANXqnLBZfn06lcteYWIfVrD3Kd5h2L/Z/cCqKcl+" |
| "4uNyO5ff8GcN0Ht3jTFJec2WvqptvvepDLuAdx53LxGx9I/8mVMtSlXfZxKvSCFTyb+b2TDpI5cb" |
| "Sxxf2PxvuP5v+deT++U5NtUvOs3ERqezH42TY/4VbPJKHM/+szMuPGHs/fPesT6wimntmy6Scn5B" |
| "SuP3UHufFNCjg8MbZpNvvjKONB1nMpWzia2VQuy9ZtQ90kZLEppIJOMxVQ+MwbQBdUwMC8fDWy54" |
| "kxOKL/52+DLExgeRDZjQYouNHXE4csobGpOek5j6LLA6pZB0u5KZrOQEkzPWyBedhij2e9JykcX1" |
| "hUnwCJ+Ca46lkM6LQSnvCjjdC8H19SugEeaB2w+jYftmOZqF7CE0aIWaVndU796Fc/xr8btPp/Mk" |
| "sbpvHv14RcL2SjC65bbBoPcU5Lyq8LS2BKkPz8GsLxmZv9ZC7UwfWfpFwsL7x1slyw7u1zvR61wH" |
| "mYzd2H82Ac67wslc24fJDNJFju1hnEEmlDedg59jCNbPuo0rVSpoaUzHUmEZqN+SwRIRTyr+Vsiu" |
| "LDv2n2rB8M1Wbn+/O0MWmhkj+LSOl7NaTZTTUDSVo3iq+OdZ68IKUjNQx7WONdDIXY1n79vwdeM0" |
| "uCeugXxvPlz7s3A6+g7Kf2nEypW6GNukQ4J9BJllLrjRL4y6q8mU483D+PLHkOfrKNxy0qM4/35a" |
| "tnw8dJOVmAHxBAjsGwXBayKQaI8z+e9wUbHCm7uXF8THZEu+sww+lEpuS1aie/Z4hq9Qjdn36gUV" |
| "tTaQs70iS3H0lj/gzF/vxh9mke0Hb/2ccXqEvuP9bi/2hOZqJkpBkhPmNoZjwjiSV8sC7Ni1ES9H" |
| "b+Jy6NC0aG5sXIe3/YwR6uRxb8ENmta7j7sWHjzMnM58QmETlUhFzYvRh6f1m2g2+Wb/Ef/+C7ws" |
| "/4wTLwcOsEV8uum16HLsoGYqsbtuE9ZaDfGHdrBccRRntMRRs0cdCUppiFIJwt2VwN2zPFCT5UDZ" |
| "WJNRd/pACYveU3HuF/bxwPFI61mOcv1t6PLIQIN2C50IPE+FIUuo9Jk8Wt8dw9aFsSgVcsTo+iFm" |
| "fkYBVSwMwlwpT6zLS4dBSgMxmr7oLlPBQIgDIC6Pf7Q1bJ+m5YlX1fTI25OSgj+SyW0ZLHs4B7M6" |
| "xGF/sZ0c3eQoUdwMzVLTwXPcGjYvOdhV1GCzKsyRGzt/jQYy2uLH/a183pf084u5OTr0aAVd7NYm" |
| "gVAtCi6Opr9Sby65r7O4HRnAzbvVGi2LO22dTIxlHmnqbeferzXbxv7/UOtDR9dxMRTFu495PVqA" |
| "9SFKklTnbv0Zo6miZUy4zRMb+Ty+f7oPrBW/YBk1EEIyQbbm/yr+jlbptvx3j//nxXx5PEvRtuMn" |
| "Bja2FrOj7F0Zra8P/xQXrpra5lbb3v077v+NWCw1NEtzOW8u1XKEzl6c/oNvXn/j3w6P/zK2epwa" |
| "CsiJs7LOHOTuO4pXmHIE2yktbB77g0WcjX2wPncmnySSg1Om6tw61VGsSVdHf6PABTY236fEosdi" |
| "kDldtZurx8BInaRbDlD7cAw5r4ji3j14eQ0rQaeTVvVtp9tLOilyfC/3rNLox6TZEU+3RHWwLDsA" |
| "pu6jER49FXodWUzMYDzzYtzf3g22r89SUM0jdkr8XXKeUcXkv2v5mX9hk0+UkHmIbM+b4PM0YbAf" |
| "zIb7vfd0UmiE5ZETwNX/8X2teZO84r8x8xfE8WsB1uzdDZbUC7TsTsOCLbkYuVjJ7a0bHDZhdk0/" |
| "Nyda7lOIKSizCdHpMvm/0v1rvT9r+LoFS/9cjNm2+c7WGoNTaEhDj1VnasIxLzbnBLe+RqW7Kaf+" |
| "x5xqa9uHQKnJnKqmTkiWHMJLpWxk1Zog+cZbeEvchN3IRM4z9jcmxknBZuEGD4ZPowguwoNINbxo" |
| "KnkpCxWDxhBQ1ONo7g3nXKq14VzqO2zDFPTigupodLTpcWbeMuNohZ7+OVNMG16Gc7FNaOIM0KoT" |
| "ftz1XutetnLvF1r2RhbT27Q5uk11EJs1g8O6840bo4m8IQzvR/WfvHvpGmg1e4Kk9WaBIfS6mHPy" |
| "1mZzIjZlYKPHMPzXqXBs9ncxIyc0LRvGK/yBq5Of1XF1BkVZc5ZtfcDZsczX9j8AVrxl9A==" |
| ) |
|
|
|
|
| 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()] |
|
|
|
|
| |
|
|
