fork download
copy 
  1. x = {
  2.      "algorithm": "Construct an initial Salem\u2011Spencer set by selecting numbers whose base\u20113 representation contains only digits\u202f0\u202for\u202f1, then perform a simulated\u2011annealing hill\u2011climb that tries to insert random outsiders by discarding their minimal conflicting blockers, accepting strictly improving moves or probabilistically worsening moves under a cooling schedule.}\n\n```python\nimport numpy as np\nfrom typing import List, Set, Union\n\ndef _conflict_set(v: int, S: Set[int]) -> Set[int]:\n    \"\"\"Return the set of elements in S that would create a 3\u2011AP with v.\"\"\"\n    bad: Set[int] = set()\n    for a in S:\n        # v as middle element\n        c = 2 * v - a\n        if c in S:\n            bad.update((a, c))\n        # v as endpoint\n        s = a + v\n        if (s & 1) == 0:          # middle is integer\n            b = s // 2\n            if b in S:\n                bad.add(b)\n    return bad\n\n\ndef _rng_from_seed(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(rng)\n\n\ndef _ternary_01(v: int) -> bool:\n    \"\"\"True if all ternary digits of v are 0 or 1 (no digit 2).\"\"\"\n    while v:\n        if v % 3 == 2:\n            return False\n        v //= 3\n    return True\n\n\ndef heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:\n    \"\"\"\n    Build a large Salem\u2013Spencer set for 1..n.\n    Deterministic given (n, rng). Returns a list of distinct integers.\n    \"\"\"\n    gen = _rng_from_seed(rng)\n\n    # -------------------------------------------------\n    # 1. Base\u20113 0/1 seed (deterministic)\n    # -------------------------------------------------\n    S: Set[int] = {v for v in range(1, n + 1) if _ternary_01(v)",
  3.      "code": "import numpy as np\nfrom typing import List, Set, Union\n\ndef _conflict_set(v: int, S: Set[int]) -> Set[int]:\n    \"\"\"Return the set of elements in S that would create a 3\u2011AP with v.\"\"\"\n    bad: Set[int] = set()\n    for a in S:\n        # v as middle element\n        c = 2 * v - a\n        if c in S:\n            bad.update((a, c))\n        # v as endpoint\n        s = a + v\n        if (s & 1) == 0:          # middle is integer\n            b = s // 2\n            if b in S:\n                bad.add(b)\n    return bad\n\n\ndef _rng_from_seed(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(rng)\n\n\ndef _ternary_01(v: int) -> bool:\n    \"\"\"True if all ternary digits of v are 0 or 1 (no digit 2).\"\"\"\n    while v:\n        if v % 3 == 2:\n            return False\n        v //= 3\n    return True\n\n\ndef heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:\n    \"\"\"\n    Build a large Salem\u2013Spencer set for 1..n.\n    Deterministic given (n, rng). Returns a list of distinct integers.\n    \"\"\"\n    gen = _rng_from_seed(rng)\n\n    # -------------------------------------------------\n    # 1. Base\u20113 0/1 seed (deterministic)\n    # -------------------------------------------------\n    S: Set[int] = {v for v in range(1, n + 1) if _ternary_01(v)}\n\n    # -------------------------------------------------\n    # 2. Simulated\u2011annealing hill\u2011climbing\n    # -------------------------------------------------\n    all_nums = set(range(1, n + 1))\n    outsiders = list(all_nums - S)\n    gen.shuffle(outsiders)\n\n    max_iters = 20000\n    temperature = 1.0\n    cooling = 0.9995\n\n    it = 0\n    while it < max_iters and outsiders:\n        cand = outsiders.pop()\n        blockers = _conflict_set(cand, S)\n\n        trial = S.difference(blockers)\n        trial.add(cand)\n\n        # try to re\u2011add any safe numbers (single deterministic pass)\n        for y in range(1, n + 1):\n            if y not in trial and not _conflict_set(y, trial):\n                trial.add(y)\n\n        delta = len(trial) - len(S)\n\n        if delta > 0:\n            S = trial\n            outsiders = list(all_nums - S)\n            gen.shuffle(outsiders)\n        else:\n            prob = np.exp(delta / temperature) if temperature > 1e-12 else 0.0\n            if gen.random() < prob:\n                S = trial\n                outsiders = list(all_nums - S)\n                gen.shuffle(outsiders)\n\n        temperature *= cooling\n        it += 1\n\n    # -------------------------------------------------\n    # 3. Final deterministic sweep for any remaining safe numbers\n    # -------------------------------------------------\n    for v in range(1, n + 1):\n        if v not in S and not _conflict_set(v, S):\n            S.add(v)\n\n    return S",
  4.      "objective": -104.73077,
  5. }
  6. print(x['code'])
Success #stdin #stdout 0.09s 14084KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
import numpy as np
from typing import List, Set, Union

def _conflict_set(v: int, S: Set[int]) -> Set[int]:
    """Return the set of elements in S that would create a 3‑AP with v."""
    bad: Set[int] = set()
    for a in S:
        # v as middle element
        c = 2 * v - a
        if c in S:
            bad.update((a, c))
        # v as endpoint
        s = a + v
        if (s & 1) == 0:          # middle is integer
            b = s // 2
            if b in S:
                bad.add(b)
    return bad


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


def _ternary_01(v: int) -> bool:
    """True if all ternary digits of v are 0 or 1 (no digit 2)."""
    while v:
        if v % 3 == 2:
            return False
        v //= 3
    return True


def heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:
    """
    Build a large Salem–Spencer set for 1..n.
    Deterministic given (n, rng). Returns a list of distinct integers.
    """
    gen = _rng_from_seed(rng)

    # -------------------------------------------------
    # 1. Base‑3 0/1 seed (deterministic)
    # -------------------------------------------------
    S: Set[int] = {v for v in range(1, n + 1) if _ternary_01(v)}

    # -------------------------------------------------
    # 2. Simulated‑annealing hill‑climbing
    # -------------------------------------------------
    all_nums = set(range(1, n + 1))
    outsiders = list(all_nums - S)
    gen.shuffle(outsiders)

    max_iters = 20000
    temperature = 1.0
    cooling = 0.9995

    it = 0
    while it < max_iters and outsiders:
        cand = outsiders.pop()
        blockers = _conflict_set(cand, S)

        trial = S.difference(blockers)
        trial.add(cand)

        # try to re‑add any safe numbers (single deterministic pass)
        for y in range(1, n + 1):
            if y not in trial and not _conflict_set(y, trial):
                trial.add(y)

        delta = len(trial) - len(S)

        if delta > 0:
            S = trial
            outsiders = list(all_nums - S)
            gen.shuffle(outsiders)
        else:
            prob = np.exp(delta / temperature) if temperature > 1e-12 else 0.0
            if gen.random() < prob:
                S = trial
                outsiders = list(all_nums - S)
                gen.shuffle(outsiders)

        temperature *= cooling
        it += 1

    # -------------------------------------------------
    # 3. Final deterministic sweep for any remaining safe numbers
    # -------------------------------------------------
    for v in range(1, n + 1):
        if v not in S and not _conflict_set(v, S):
            S.add(v)

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