fork download
copy 
  1. x = {
  2.      "algorithm": "Greedy construction ordering numbers by increasing endpoint degree (fewest possible 3\u2011APs), followed by a bounded pair\u2011swap local search that tries to replace 1 or 2 existing elements with up to 3 new compatible elements to enlarge the set.}\n\n```python\nimport numpy as np\nfrom typing import List, Union, Set, Tuple\n\ndef _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:\n    if isinstance(rng, np.random.Generator):\n        return rng\n    return np.random.default_rng(0 if rng is None else int(rng))\n\n\ndef _can_add(val: int, cur: Set[int]) -> bool:\n    \"\"\"Return True iff val can be added to cur without creating a 3\u2011AP.\"\"\"\n    for y in cur:\n        # val as outer term\n        if (val + y) % 2 == 0 and ((val + y) // 2) in cur:\n            return False\n        # val as middle term\n        if (2 * val - y) in cur or (2 * y - val) in cur:\n            return False\n    return True\n\n\ndef heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> Tuple[int, ...]:\n    \"\"\"\n    Return a large 3\u2011AP\u2011free subset of {1,\u2026,n}.\n    Deterministic for the same (n, rng) pair.\n    \"\"\"\n    if n <= 0:\n        return tuple()\n\n    gen = _make_rng(rng)\n\n    # ------------------------------------------------------------\n    # 1. Greedy build using endpoint degree as priority.\n    # ------------------------------------------------------------\n    # degree = number of possible symmetric partners that would\n    # form an AP with the element (i.e. min(val-1, n-val))\n    candidates = list(range(1, n + 1))\n    candidates.sort(key=lambda v: min(v - 1, n - v))  # smallest degree first\n\n    S: Set[int] = set()\n    for v in candidates:\n        if _can_add(v, S):\n            S.add(v)\n\n    # ------------------------------------------------------------\n    # 2. Short local\u2011improvement phase (pair\u2011swap).\n    # ------------------------------------------------------------\n    all_numbers = set(range(1, n + 1))\n    outside = list(all_numbers - S)\n    gen.shuffle(outside)               # deterministic random order\n\n    max_trials = 5000\n    failures = 0\n\n    while failures < max_trials and outside:\n        # choose whether to remove 1 or 2 elements\n        rem_sz = 1 if gen.random() < 0.6 else 2\n        if len(S) < rem_sz:\n            failures += 1\n            continue\n\n        to_remove = gen.choice(list(S), size=rem_sz, replace=False)\n        base_set = S.difference(to_remove)\n\n        # collect up to rem_sz+1 new elements that fit\n        added: List[int] = []\n        for cand in outside:\n            if cand in base_set:\n                continue\n            if not _can_add(cand, base_set):\n                continue\n            # also compatible with already chosen new elements\n            ok = True\n            for a in added:\n                if not _can_add(cand, {a}) or not _can_add(a, {cand",
  3.      "code": "import numpy as np\nfrom typing import List, Union, Set, Tuple\n\ndef _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:\n    if isinstance(rng, np.random.Generator):\n        return rng\n    return np.random.default_rng(0 if rng is None else int(rng))\n\n\ndef _can_add(val: int, cur: Set[int]) -> bool:\n    \"\"\"Return True iff val can be added to cur without creating a 3\u2011AP.\"\"\"\n    for y in cur:\n        # val as outer term\n        if (val + y) % 2 == 0 and ((val + y) // 2) in cur:\n            return False\n        # val as middle term\n        if (2 * val - y) in cur or (2 * y - val) in cur:\n            return False\n    return True\n\n\ndef heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> Tuple[int, ...]:\n    \"\"\"\n    Return a large 3\u2011AP\u2011free subset of {1,\u2026,n}.\n    Deterministic for the same (n, rng) pair.\n    \"\"\"\n    if n <= 0:\n        return tuple()\n\n    gen = _make_rng(rng)\n\n    # ------------------------------------------------------------\n    # 1. Greedy build using endpoint degree as priority.\n    # ------------------------------------------------------------\n    # degree = number of possible symmetric partners that would\n    # form an AP with the element (i.e. min(val-1, n-val))\n    candidates = list(range(1, n + 1))\n    candidates.sort(key=lambda v: min(v - 1, n - v))  # smallest degree first\n\n    S: Set[int] = set()\n    for v in candidates:\n        if _can_add(v, S):\n            S.add(v)\n\n    # ------------------------------------------------------------\n    # 2. Short local\u2011improvement phase (pair\u2011swap).\n    # ------------------------------------------------------------\n    all_numbers = set(range(1, n + 1))\n    outside = list(all_numbers - S)\n    gen.shuffle(outside)               # deterministic random order\n\n    max_trials = 5000\n    failures = 0\n\n    while failures < max_trials and outside:\n        # choose whether to remove 1 or 2 elements\n        rem_sz = 1 if gen.random() < 0.6 else 2\n        if len(S) < rem_sz:\n            failures += 1\n            continue\n\n        to_remove = gen.choice(list(S), size=rem_sz, replace=False)\n        base_set = S.difference(to_remove)\n\n        # collect up to rem_sz+1 new elements that fit\n        added: List[int] = []\n        for cand in outside:\n            if cand in base_set:\n                continue\n            if not _can_add(cand, base_set):\n                continue\n            # also compatible with already chosen new elements\n            ok = True\n            for a in added:\n                if not _can_add(cand, {a}) or not _can_add(a, {cand}):\n                    ok = False\n                    break\n            if ok:\n                added.append(cand)\n                base_set.add(cand)\n            if len(added) >= rem_sz + 1:   # max gain we try for\n                break\n\n        # accept only if we strictly increased the size\n        if len(added) > rem_sz:\n            S = base_set\n            outside = [v for v in all_numbers if v not in S]\n            gen.shuffle(outside)\n            failures = 0\n        else:\n            failures += 1\n\n    # Return a sorted, immutable tuple for reproducibility\n    return S",
  4.      "objective": -103.05,
  5.  
  6. }# your code goes here
  7. print(x['code'])
Success #stdin #stdout 0.13s 14108KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
import numpy as np
from typing import List, Union, Set, Tuple

def _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:
    if isinstance(rng, np.random.Generator):
        return rng
    return np.random.default_rng(0 if rng is None else int(rng))


def _can_add(val: int, cur: Set[int]) -> bool:
    """Return True iff val can be added to cur without creating a 3‑AP."""
    for y in cur:
        # val as outer term
        if (val + y) % 2 == 0 and ((val + y) // 2) in cur:
            return False
        # val as middle term
        if (2 * val - y) in cur or (2 * y - val) in cur:
            return False
    return True


def heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> Tuple[int, ...]:
    """
    Return a large 3‑AP‑free subset of {1,…,n}.
    Deterministic for the same (n, rng) pair.
    """
    if n <= 0:
        return tuple()

    gen = _make_rng(rng)

    # ------------------------------------------------------------
    # 1. Greedy build using endpoint degree as priority.
    # ------------------------------------------------------------
    # degree = number of possible symmetric partners that would
    # form an AP with the element (i.e. min(val-1, n-val))
    candidates = list(range(1, n + 1))
    candidates.sort(key=lambda v: min(v - 1, n - v))  # smallest degree first

    S: Set[int] = set()
    for v in candidates:
        if _can_add(v, S):
            S.add(v)

    # ------------------------------------------------------------
    # 2. Short local‑improvement phase (pair‑swap).
    # ------------------------------------------------------------
    all_numbers = set(range(1, n + 1))
    outside = list(all_numbers - S)
    gen.shuffle(outside)               # deterministic random order

    max_trials = 5000
    failures = 0

    while failures < max_trials and outside:
        # choose whether to remove 1 or 2 elements
        rem_sz = 1 if gen.random() < 0.6 else 2
        if len(S) < rem_sz:
            failures += 1
            continue

        to_remove = gen.choice(list(S), size=rem_sz, replace=False)
        base_set = S.difference(to_remove)

        # collect up to rem_sz+1 new elements that fit
        added: List[int] = []
        for cand in outside:
            if cand in base_set:
                continue
            if not _can_add(cand, base_set):
                continue
            # also compatible with already chosen new elements
            ok = True
            for a in added:
                if not _can_add(cand, {a}) or not _can_add(a, {cand}):
                    ok = False
                    break
            if ok:
                added.append(cand)
                base_set.add(cand)
            if len(added) >= rem_sz + 1:   # max gain we try for
                break

        # accept only if we strictly increased the size
        if len(added) > rem_sz:
            S = base_set
            outside = [v for v in all_numbers if v not in S]
            gen.shuffle(outside)
            failures = 0
        else:
            failures += 1

    # Return a sorted, immutable tuple for reproducibility
    return S
https://ideone.com/PrzHzB
language:
Python 3 (python  3.12)
created:
16 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!