fork download
copy 
  1. x = {
  2.      "algorithm": "Greedy construction that orders all numbers by their total number of potential 3\u2011APs (as middle\u202f+\u202fas endpoint) and inserts them if they keep the set AP\u2011free, followed by a short random swap\u2011add local\u2011search with budget\u202f\u2248\u202f3\u00b7n\u00b7log\u2082n; main parameters are the scoring rule (total potential APs) and the improvement budget.}\n\n```python\nimport numpy as np\nfrom typing import List, Set, Tuple, Union\n\ndef _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:\n    \"\"\"Create a deterministic RNG from None, an int seed or an existing Generator.\"\"\"\n    if rng is None:\n        return np.random.default_rng(0)\n    if isinstance(rng, np.random.Generator):\n        # clone without side\u2011effects\n        state = rng.bit_generator.state\n        return np.random.Generator(np.random.PCG64(state))\n    return np.random.default_rng(int(rng))\n\ndef _potential_ap_count(x: int, n: int) -> int:\n    \"\"\"\n    Total number of distinct 3\u2011AP triples that would involve x\n    if the other two elements were arbitrarily chosen from {1..n}.\n    Counts both roles: x as middle and x as endpoint.\n    \"\"\"\n    cnt = 0\n    # x as middle: choose any y != x, then a = 2*x - y must be in range\n    # This is equivalent to count of y such that 1 <= 2*x - y <= n\n    # i.e. y in [2*x - n, 2*x - 1] intersect [1, n] and y != x\n    lo = max(1, 2 * x - n)\n    hi = min(n, 2 * x - 1)\n    cnt += max(0, hi - lo + 1)  # includes possible y = x, subtract later\n    if lo <= x <= hi:\n        cnt -= 1  # remove the case y == x\n\n    # x as endpoint: choose any y != x, then middle m = (x + y) // 2 must be integer and in range\n    # This happens exactly when x+y is even.\n    # For each possible middle m, the other endpoint is y = 2*m - x.\n    # m must be in [1, n] and y in [1, n] and y != x.\n    lo_m = max(1, (x + 1) // 2)          # smallest m making y >= 1\n    hi_m = min(n, (x + n) // 2)          # largest  m making y <= n\n    cnt += max(0, hi_m - lo_m + 1)\n    # remove the case y == x (which occurs only when m == x)\n    if lo_m <= x <= hi_m:\n        cnt -= 1\n    return cnt\n\ndef _new_ap_conflicts(x: int, S: Set[int]) -> bool:\n    \"\"\"Return True if adding x to S would create any 3\u2011AP.\"\"\"\n    for y in S:\n        # x as middle\n        a = 2 * x - y\n        if a in S:\n            return True\n        # x as endpoint\n        b = 2 * y - x\n        if b in S:\n            return True\n    return False\n\ndef _blockers_for(x: int, S: Set[int]) -> Tuple[int, ...]:\n    \"\"\"\n    Return up to two elements of S that together with x form a 3\u2011AP.\n    Used in the local\u2011search phase.\n    \"\"\"\n    blockers = []\n    for y in S:\n        a = 2 * x - y\n        if a in S:\n            blockers.append(y)\n        b = 2 * y - x\n        if b in S:\n            blockers.append(y)\n        if len(blockers) >= 2:\n            break\n    return tuple(blockers)\n\ndef heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:\n    \"\"\"\n    Construct a large 3\u2011AP\u2011free subset of {1,\u2026,n",
  3.      "code": "import numpy as np\nfrom typing import List, Set, Tuple, Union\n\ndef _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:\n    \"\"\"Create a deterministic RNG from None, an int seed or an existing Generator.\"\"\"\n    if rng is None:\n        return np.random.default_rng(0)\n    if isinstance(rng, np.random.Generator):\n        # clone without side\u2011effects\n        state = rng.bit_generator.state\n        return np.random.Generator(np.random.PCG64(state))\n    return np.random.default_rng(int(rng))\n\ndef _potential_ap_count(x: int, n: int) -> int:\n    \"\"\"\n    Total number of distinct 3\u2011AP triples that would involve x\n    if the other two elements were arbitrarily chosen from {1..n}.\n    Counts both roles: x as middle and x as endpoint.\n    \"\"\"\n    cnt = 0\n    # x as middle: choose any y != x, then a = 2*x - y must be in range\n    # This is equivalent to count of y such that 1 <= 2*x - y <= n\n    # i.e. y in [2*x - n, 2*x - 1] intersect [1, n] and y != x\n    lo = max(1, 2 * x - n)\n    hi = min(n, 2 * x - 1)\n    cnt += max(0, hi - lo + 1)  # includes possible y = x, subtract later\n    if lo <= x <= hi:\n        cnt -= 1  # remove the case y == x\n\n    # x as endpoint: choose any y != x, then middle m = (x + y) // 2 must be integer and in range\n    # This happens exactly when x+y is even.\n    # For each possible middle m, the other endpoint is y = 2*m - x.\n    # m must be in [1, n] and y in [1, n] and y != x.\n    lo_m = max(1, (x + 1) // 2)          # smallest m making y >= 1\n    hi_m = min(n, (x + n) // 2)          # largest  m making y <= n\n    cnt += max(0, hi_m - lo_m + 1)\n    # remove the case y == x (which occurs only when m == x)\n    if lo_m <= x <= hi_m:\n        cnt -= 1\n    return cnt\n\ndef _new_ap_conflicts(x: int, S: Set[int]) -> bool:\n    \"\"\"Return True if adding x to S would create any 3\u2011AP.\"\"\"\n    for y in S:\n        # x as middle\n        a = 2 * x - y\n        if a in S:\n            return True\n        # x as endpoint\n        b = 2 * y - x\n        if b in S:\n            return True\n    return False\n\ndef _blockers_for(x: int, S: Set[int]) -> Tuple[int, ...]:\n    \"\"\"\n    Return up to two elements of S that together with x form a 3\u2011AP.\n    Used in the local\u2011search phase.\n    \"\"\"\n    blockers = []\n    for y in S:\n        a = 2 * x - y\n        if a in S:\n            blockers.append(y)\n        b = 2 * y - x\n        if b in S:\n            blockers.append(y)\n        if len(blockers) >= 2:\n            break\n    return tuple(blockers)\n\ndef heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:\n    \"\"\"\n    Construct a large 3\u2011AP\u2011free subset of {1,\u2026,n}.\n    Deterministic for a given (n, rng). Returns a sorted list.\n    \"\"\"\n    rng = _make_rng(rng)\n\n    # -----------------------------------------------------------------\n    # 1. Compute the total potential\u2011AP score for every candidate.\n    # -----------------------------------------------------------------\n    scores = np.fromiter((_potential_ap_count(x, n) for x in range(1, n + 1)), dtype=int)\n\n    # -----------------------------------------------------------------\n    # 2. Random tie\u2011break, then order ascending by score.\n    # -----------------------------------------------------------------\n    order = np.arange(1, n + 1)\n    rng.shuffle(order)\n    order = order[np.argsort(scores[order - 1], kind='stable')]\n\n    # -----------------------------------------------------------------\n    # 3. Greedy insertion respecting the AP\u2011free condition.\n    # -----------------------------------------------------------------\n    S: Set[int] = set()\n    for x in order:\n        if not _new_ap_conflicts(x, S):\n            S.add(int(x))\n\n    # -----------------------------------------------------------------\n    # 4. Short random local\u2011improvement phase.\n    #    Try to add a random omitted element; if it conflicts,\n    #    attempt to replace a single blocker.\n    # -----------------------------------------------------------------\n    budget = int(3 * n * np.log2(max(2, n)))       # \u2248 n\u202flog\u202fn attempts\n    omitted = set(range(1, n + 1)) - S\n    omitted_list = list(omitted)\n\n    for _ in range(budget):\n        if not omitted_list:\n            break\n        x = rng.choice(omitted_list)\n        if not _new_ap_conflicts(x, S):\n            S.add(x)\n            omitted.remove(x)\n            omitted_list.remove(x)\n            continue\n\n        blockers = _blockers_for(x, S)\n        if not blockers:\n            continue\n\n        for y in blockers:\n            trial = S.copy()\n            trial.remove(y)\n            if not _new_ap_conflicts(x, trial):\n                S = trial\n                S.add(x)\n                omitted.remove(x)\n                omitted.add(y)\n                omitted_list = list(omitted)\n                break\n\n    return S",
  4.      "objective": -92.24157,
  5. }
  6. print(x['code'])
Success #stdin #stdout 0.07s 14176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
import numpy as np
from typing import List, Set, Tuple, Union

def _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:
    """Create a deterministic RNG from None, an int seed or an existing Generator."""
    if rng is None:
        return np.random.default_rng(0)
    if isinstance(rng, np.random.Generator):
        # clone without side‑effects
        state = rng.bit_generator.state
        return np.random.Generator(np.random.PCG64(state))
    return np.random.default_rng(int(rng))

def _potential_ap_count(x: int, n: int) -> int:
    """
    Total number of distinct 3‑AP triples that would involve x
    if the other two elements were arbitrarily chosen from {1..n}.
    Counts both roles: x as middle and x as endpoint.
    """
    cnt = 0
    # x as middle: choose any y != x, then a = 2*x - y must be in range
    # This is equivalent to count of y such that 1 <= 2*x - y <= n
    # i.e. y in [2*x - n, 2*x - 1] intersect [1, n] and y != x
    lo = max(1, 2 * x - n)
    hi = min(n, 2 * x - 1)
    cnt += max(0, hi - lo + 1)  # includes possible y = x, subtract later
    if lo <= x <= hi:
        cnt -= 1  # remove the case y == x

    # x as endpoint: choose any y != x, then middle m = (x + y) // 2 must be integer and in range
    # This happens exactly when x+y is even.
    # For each possible middle m, the other endpoint is y = 2*m - x.
    # m must be in [1, n] and y in [1, n] and y != x.
    lo_m = max(1, (x + 1) // 2)          # smallest m making y >= 1
    hi_m = min(n, (x + n) // 2)          # largest  m making y <= n
    cnt += max(0, hi_m - lo_m + 1)
    # remove the case y == x (which occurs only when m == x)
    if lo_m <= x <= hi_m:
        cnt -= 1
    return cnt

def _new_ap_conflicts(x: int, S: Set[int]) -> bool:
    """Return True if adding x to S would create any 3‑AP."""
    for y in S:
        # x as middle
        a = 2 * x - y
        if a in S:
            return True
        # x as endpoint
        b = 2 * y - x
        if b in S:
            return True
    return False

def _blockers_for(x: int, S: Set[int]) -> Tuple[int, ...]:
    """
    Return up to two elements of S that together with x form a 3‑AP.
    Used in the local‑search phase.
    """
    blockers = []
    for y in S:
        a = 2 * x - y
        if a in S:
            blockers.append(y)
        b = 2 * y - x
        if b in S:
            blockers.append(y)
        if len(blockers) >= 2:
            break
    return tuple(blockers)

def heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:
    """
    Construct a large 3‑AP‑free subset of {1,…,n}.
    Deterministic for a given (n, rng). Returns a sorted list.
    """
    rng = _make_rng(rng)

    # -----------------------------------------------------------------
    # 1. Compute the total potential‑AP score for every candidate.
    # -----------------------------------------------------------------
    scores = np.fromiter((_potential_ap_count(x, n) for x in range(1, n + 1)), dtype=int)

    # -----------------------------------------------------------------
    # 2. Random tie‑break, then order ascending by score.
    # -----------------------------------------------------------------
    order = np.arange(1, n + 1)
    rng.shuffle(order)
    order = order[np.argsort(scores[order - 1], kind='stable')]

    # -----------------------------------------------------------------
    # 3. Greedy insertion respecting the AP‑free condition.
    # -----------------------------------------------------------------
    S: Set[int] = set()
    for x in order:
        if not _new_ap_conflicts(x, S):
            S.add(int(x))

    # -----------------------------------------------------------------
    # 4. Short random local‑improvement phase.
    #    Try to add a random omitted element; if it conflicts,
    #    attempt to replace a single blocker.
    # -----------------------------------------------------------------
    budget = int(3 * n * np.log2(max(2, n)))       # ≈ n log n attempts
    omitted = set(range(1, n + 1)) - S
    omitted_list = list(omitted)

    for _ in range(budget):
        if not omitted_list:
            break
        x = rng.choice(omitted_list)
        if not _new_ap_conflicts(x, S):
            S.add(x)
            omitted.remove(x)
            omitted_list.remove(x)
            continue

        blockers = _blockers_for(x, S)
        if not blockers:
            continue

        for y in blockers:
            trial = S.copy()
            trial.remove(y)
            if not _new_ap_conflicts(x, trial):
                S = trial
                S.add(x)
                omitted.remove(x)
                omitted.add(y)
                omitted_list = list(omitted)
                break

    return S
https://ideone.com/4JsWVD
language:
Python 3 (python  3.12)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!