fork download
copy 
  1. x = {
  2.      "algorithm": "Greedy construction ordered by minimal middle\u2011term potential followed by a bounded single\u2011swap hill\u2011climber using a deterministic RNG.}  \n\n```python\nimport numpy as np\nfrom typing import List, Set, Union\n\ndef _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:\n    \"\"\"Return a deterministic Generator 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        return rng\n    return np.random.default_rng(int(rng))\n\ndef _conflict_set(x: int, cur: Set[int]) -> Set[int]:\n    \"\"\"Return the subset of cur that would form a 3\u2011AP with x.\"\"\"\n    conflicted = set()\n    for y in cur:\n        s = x + y\n        if s % 2 == 0 and (s // 2) in cur:\n            conflicted.add(y)\n        if (2 * x - y) in cur:\n            conflicted.add(y)\n        if (2 * y - x) in cur:\n            conflicted.add(y)\n    return conflicted\n\ndef heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:\n    \"\"\"\n    Return a large 3\u2011AP\u2011free subset of {1,\u2026,n",
  3.      "code": "import numpy as np\nfrom typing import List, Set, Union\n\ndef _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:\n    \"\"\"Return a deterministic Generator 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        return rng\n    return np.random.default_rng(int(rng))\n\ndef _conflict_set(x: int, cur: Set[int]) -> Set[int]:\n    \"\"\"Return the subset of cur that would form a 3\u2011AP with x.\"\"\"\n    conflicted = set()\n    for y in cur:\n        s = x + y\n        if s % 2 == 0 and (s // 2) in cur:\n            conflicted.add(y)\n        if (2 * x - y) in cur:\n            conflicted.add(y)\n        if (2 * y - x) in cur:\n            conflicted.add(y)\n    return conflicted\n\ndef heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:\n    \"\"\"\n    Return a large 3\u2011AP\u2011free subset of {1,\u2026,n}.\n    1. Greedy addition of numbers sorted by low middle\u2011term potential.\n    2. Bounded hill\u2011climbing that may replace a single conflicting element.\n    \"\"\"\n    if n <= 0:\n        return []\n\n    gen = _make_rng(rng)\n\n    # ---------- 1. Greedy construction ----------\n    # static score = number of possible APs where the element is the middle term\n    scores = [(min(x - 1, n - x), x) for x in range(1, n + 1)]\n    # break ties randomly but deterministically\n    random_ties = gen.random(len(scores))\n    scores.sort(key=lambda t: (t[0], random_ties[t[1] - 1]))\n\n    S: Set[int] = set()\n    for _, x in scores:\n        # add if safe\n        if not _conflict_set(x, S):\n            S.add(x)\n\n    # ---------- 2. Local improvement (single\u2011swap hill\u2011climber) ----------\n    missing = [i for i in range(1, n + 1) if i not in S]\n    gen.shuffle(missing)\n\n    budget = int(2 * np.sqrt(n)) + 100          # number of unsuccessful attempts allowed\n    fails = 0\n    pos = 0\n    while fails < budget and missing:\n        x = missing[pos % len(missing)]\n        pos += 1\n\n        conflicted = _conflict_set(x, S)\n        if not conflicted:\n            S.add(x)\n            missing.remove(x)\n            fails = 0\n            continue\n\n        # allow replacement of a single conflicting element\n        replaced = False\n        for y in conflicted:\n            # check whether removing y eliminates all conflicts for x\n            temp = S.copy()\n            temp.remove(y)\n            if not _conflict_set(x, temp):\n                S.remove(y)\n                S.add(x)\n                missing.remove(x)\n                missing.append(y)          # y becomes a candidate again\n                fails = 0\n                replaced = True\n                break\n        if not replaced:\n            fails += 1\n\n    return S",
  4.      "objective": -102.04231,
  5. }
  6. print(x['code'])
Success #stdin #stdout 0.13s 14112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
import numpy as np
from typing import List, Set, Union

def _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:
    """Return a deterministic Generator 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):
        return rng
    return np.random.default_rng(int(rng))

def _conflict_set(x: int, cur: Set[int]) -> Set[int]:
    """Return the subset of cur that would form a 3‑AP with x."""
    conflicted = set()
    for y in cur:
        s = x + y
        if s % 2 == 0 and (s // 2) in cur:
            conflicted.add(y)
        if (2 * x - y) in cur:
            conflicted.add(y)
        if (2 * y - x) in cur:
            conflicted.add(y)
    return conflicted

def heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:
    """
    Return a large 3‑AP‑free subset of {1,…,n}.
    1. Greedy addition of numbers sorted by low middle‑term potential.
    2. Bounded hill‑climbing that may replace a single conflicting element.
    """
    if n <= 0:
        return []

    gen = _make_rng(rng)

    # ---------- 1. Greedy construction ----------
    # static score = number of possible APs where the element is the middle term
    scores = [(min(x - 1, n - x), x) for x in range(1, n + 1)]
    # break ties randomly but deterministically
    random_ties = gen.random(len(scores))
    scores.sort(key=lambda t: (t[0], random_ties[t[1] - 1]))

    S: Set[int] = set()
    for _, x in scores:
        # add if safe
        if not _conflict_set(x, S):
            S.add(x)

    # ---------- 2. Local improvement (single‑swap hill‑climber) ----------
    missing = [i for i in range(1, n + 1) if i not in S]
    gen.shuffle(missing)

    budget = int(2 * np.sqrt(n)) + 100          # number of unsuccessful attempts allowed
    fails = 0
    pos = 0
    while fails < budget and missing:
        x = missing[pos % len(missing)]
        pos += 1

        conflicted = _conflict_set(x, S)
        if not conflicted:
            S.add(x)
            missing.remove(x)
            fails = 0
            continue

        # allow replacement of a single conflicting element
        replaced = False
        for y in conflicted:
            # check whether removing y eliminates all conflicts for x
            temp = S.copy()
            temp.remove(y)
            if not _conflict_set(x, temp):
                S.remove(y)
                S.add(x)
                missing.remove(x)
                missing.append(y)          # y becomes a candidate again
                fails = 0
                replaced = True
                break
        if not replaced:
            fails += 1

    return S
https://ideone.com/vCWE39
language:
Python 3 (python  3.12)
created:
20 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!