fork download
copy 
  1. x = {
  2.      "algorithm": "Begin with the full universe and iteratively delete the element that participates in the largest number of remaining 3\u2011APs (pruning phase), then apply a short random\u2011swap\u2011and\u2011refill local\u2011search to try to recover size, returning the final 3\u2011AP\u2011free set.}\n\n**Implementation**\n\n```python\nimport numpy as np\nfrom typing import List, Set, Union\n\ndef _to_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(rng)\n\n\ndef _conflict_set(v: int, S: Set[int]) -> Set[int]:\n    \"\"\"Elements of S that together with v would form a 3\u2011AP.\"\"\"\n    bad: Set[int] = set()\n    for a in S:\n        # v as middle term\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:\n            b = s // 2\n            if b in S:\n                bad.add(b)\n    return bad\n\n\ndef _static_degree(v: int, n: int) -> int:\n    \"\"\"Upper bound on the number of 3\u2011APs that involve v (used for refill order).\"\"\"\n    left, right = v - 1, n - v\n    mid = min(left, right)            # v as middle\n    left_end = (n - v) // 2           # v as left endpoint\n    right_end = (v - 1) // 2          # v as right endpoint\n    return mid + left_end + right_end\n\n\ndef heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:\n    \"\"\"Return a large Salem\u2013Spencer subset of {1,\u2026,n}.\"\"\"\n    gen = _to_rng(rng)\n\n    # -------------------------------------------------------------\n    # 1. Enumerate all 3\u2011AP triples in [1..n]     (O(n\u00b2))\n    # -------------------------------------------------------------\n    triples = []                     # list of (a,b,c)\n    for b in range(2, n):\n        max_d = min(b - 1, n - b)\n        for d in range(1, max_d + 1):\n            triples.append((b - d, b, b + d))\n\n    m = len(triples)\n    # for each element store the indices of triples it belongs to\n    elem_triples: List[List[int]] = [[] for _ in range(n + 1)]\n    for idx, (a, b, c) in enumerate(triples):\n        elem_triples[a].append(idx)\n        elem_triples[b].append(idx)\n        elem_triples[c].append(idx)\n\n    # -------------------------------------------------------------\n    # 2. Prune: repeatedly delete the element that belongs to the\n    #    most *still\u2011active* triples.\n    # -------------------------------------------------------------\n    active = [True] * (n + 1)                 # element status\n    triple_active = [True] * m                # triple status\n    # current participation count of each element\n    part_cnt = [0] * (n + 1)\n    for v in range(1, n + 1):\n        part_cnt[v] = len(elem_triples[v])\n\n    while True:\n        # find active element with maximal count\n        max_v = -1\n        max_c = -1\n        for v in range(1, n + 1):\n            if active[v] and part_cnt[v] > max_c:\n                max_c = part_cnt[v]\n                max_v = v\n        if max_c == 0 or max_v == -1:        # no remaining APs\n            break\n\n        # remove it\n        active[max_v] = False\n        for tid in elem_triples[max_v]:\n            if not triple_active[tid]:\n                continue\n            triple_active[tid] = False\n            a, b, c = triples[tid]\n            for w in (a, b, c):\n                if w != max_v and active[w]:\n                    part_cnt[w] -= 1\n\n    S: Set[int] = {v for v in range(1, n + 1) if active[v]",
  3.      "code": "import numpy as np\nfrom typing import List, Set, Union\n\ndef _to_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(rng)\n\n\ndef _conflict_set(v: int, S: Set[int]) -> Set[int]:\n    \"\"\"Elements of S that together with v would form a 3\u2011AP.\"\"\"\n    bad: Set[int] = set()\n    for a in S:\n        # v as middle term\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:\n            b = s // 2\n            if b in S:\n                bad.add(b)\n    return bad\n\n\ndef _static_degree(v: int, n: int) -> int:\n    \"\"\"Upper bound on the number of 3\u2011APs that involve v (used for refill order).\"\"\"\n    left, right = v - 1, n - v\n    mid = min(left, right)            # v as middle\n    left_end = (n - v) // 2           # v as left endpoint\n    right_end = (v - 1) // 2          # v as right endpoint\n    return mid + left_end + right_end\n\n\ndef heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:\n    \"\"\"Return a large Salem\u2013Spencer subset of {1,\u2026,n}.\"\"\"\n    gen = _to_rng(rng)\n\n    # -------------------------------------------------------------\n    # 1. Enumerate all 3\u2011AP triples in [1..n]     (O(n\u00b2))\n    # -------------------------------------------------------------\n    triples = []                     # list of (a,b,c)\n    for b in range(2, n):\n        max_d = min(b - 1, n - b)\n        for d in range(1, max_d + 1):\n            triples.append((b - d, b, b + d))\n\n    m = len(triples)\n    # for each element store the indices of triples it belongs to\n    elem_triples: List[List[int]] = [[] for _ in range(n + 1)]\n    for idx, (a, b, c) in enumerate(triples):\n        elem_triples[a].append(idx)\n        elem_triples[b].append(idx)\n        elem_triples[c].append(idx)\n\n    # -------------------------------------------------------------\n    # 2. Prune: repeatedly delete the element that belongs to the\n    #    most *still\u2011active* triples.\n    # -------------------------------------------------------------\n    active = [True] * (n + 1)                 # element status\n    triple_active = [True] * m                # triple status\n    # current participation count of each element\n    part_cnt = [0] * (n + 1)\n    for v in range(1, n + 1):\n        part_cnt[v] = len(elem_triples[v])\n\n    while True:\n        # find active element with maximal count\n        max_v = -1\n        max_c = -1\n        for v in range(1, n + 1):\n            if active[v] and part_cnt[v] > max_c:\n                max_c = part_cnt[v]\n                max_v = v\n        if max_c == 0 or max_v == -1:        # no remaining APs\n            break\n\n        # remove it\n        active[max_v] = False\n        for tid in elem_triples[max_v]:\n            if not triple_active[tid]:\n                continue\n            triple_active[tid] = False\n            a, b, c = triples[tid]\n            for w in (a, b, c):\n                if w != max_v and active[w]:\n                    part_cnt[w] -= 1\n\n    S: Set[int] = {v for v in range(1, n + 1) if active[v]}\n\n    # -------------------------------------------------------------\n    # 3. Short random\u2011swap\u2011and\u2011refill local search\n    # -------------------------------------------------------------\n    all_numbers = set(range(1, n + 1))\n    outsiders = list(all_numbers - S)\n    gen.shuffle(outsiders)\n\n    # ordering used for greedy refill (static degree, low to high)\n    refill_order = list(range(1, n + 1))\n    refill_order.sort(key=lambda v: (_static_degree(v, n), v))\n\n    max_iters = min(8 * n, 20000)\n    it = 0\n    while it < max_iters and outsiders:\n        cand = outsiders.pop()\n        blockers = _conflict_set(cand, S)\n\n        if not blockers:\n            S.add(cand)\n            outsiders = list(all_numbers - S)\n            gen.shuffle(outsiders)\n            it += 1\n            continue\n\n        trial = S.difference(blockers)\n        trial.add(cand)\n\n        # greedy refill\n        for w in refill_order:\n            if w not in trial and not _conflict_set(w, trial):\n                trial.add(w)\n\n        if len(trial) >= len(S):\n            S = trial\n            outsiders = list(all_numbers - S)\n            gen.shuffle(outsiders)\n\n        it += 1\n\n    # -------------------------------------------------------------\n    # 4. Final deterministic sweep (add any remaining safe numbers)\n    # -------------------------------------------------------------\n    for v in refill_order:\n        if v not in S and not _conflict_set(v, S):\n            S.add(v)\n\n    # Return a sorted list for reproducibility\n    return S",
  4.      "objective": -106.54231,
  5. }
  6. print(x['code'])
Success #stdin #stdout 0.09s 14180KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
import numpy as np
from typing import List, Set, Union

def _to_rng(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 _conflict_set(v: int, S: Set[int]) -> Set[int]:
    """Elements of S that together with v would form a 3‑AP."""
    bad: Set[int] = set()
    for a in S:
        # v as middle term
        c = 2 * v - a
        if c in S:
            bad.update((a, c))
        # v as endpoint
        s = a + v
        if (s & 1) == 0:
            b = s // 2
            if b in S:
                bad.add(b)
    return bad


def _static_degree(v: int, n: int) -> int:
    """Upper bound on the number of 3‑APs that involve v (used for refill order)."""
    left, right = v - 1, n - v
    mid = min(left, right)            # v as middle
    left_end = (n - v) // 2           # v as left endpoint
    right_end = (v - 1) // 2          # v as right endpoint
    return mid + left_end + right_end


def heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:
    """Return a large Salem–Spencer subset of {1,…,n}."""
    gen = _to_rng(rng)

    # -------------------------------------------------------------
    # 1. Enumerate all 3‑AP triples in [1..n]     (O(n²))
    # -------------------------------------------------------------
    triples = []                     # list of (a,b,c)
    for b in range(2, n):
        max_d = min(b - 1, n - b)
        for d in range(1, max_d + 1):
            triples.append((b - d, b, b + d))

    m = len(triples)
    # for each element store the indices of triples it belongs to
    elem_triples: List[List[int]] = [[] for _ in range(n + 1)]
    for idx, (a, b, c) in enumerate(triples):
        elem_triples[a].append(idx)
        elem_triples[b].append(idx)
        elem_triples[c].append(idx)

    # -------------------------------------------------------------
    # 2. Prune: repeatedly delete the element that belongs to the
    #    most *still‑active* triples.
    # -------------------------------------------------------------
    active = [True] * (n + 1)                 # element status
    triple_active = [True] * m                # triple status
    # current participation count of each element
    part_cnt = [0] * (n + 1)
    for v in range(1, n + 1):
        part_cnt[v] = len(elem_triples[v])

    while True:
        # find active element with maximal count
        max_v = -1
        max_c = -1
        for v in range(1, n + 1):
            if active[v] and part_cnt[v] > max_c:
                max_c = part_cnt[v]
                max_v = v
        if max_c == 0 or max_v == -1:        # no remaining APs
            break

        # remove it
        active[max_v] = False
        for tid in elem_triples[max_v]:
            if not triple_active[tid]:
                continue
            triple_active[tid] = False
            a, b, c = triples[tid]
            for w in (a, b, c):
                if w != max_v and active[w]:
                    part_cnt[w] -= 1

    S: Set[int] = {v for v in range(1, n + 1) if active[v]}

    # -------------------------------------------------------------
    # 3. Short random‑swap‑and‑refill local search
    # -------------------------------------------------------------
    all_numbers = set(range(1, n + 1))
    outsiders = list(all_numbers - S)
    gen.shuffle(outsiders)

    # ordering used for greedy refill (static degree, low to high)
    refill_order = list(range(1, n + 1))
    refill_order.sort(key=lambda v: (_static_degree(v, n), v))

    max_iters = min(8 * n, 20000)
    it = 0
    while it < max_iters and outsiders:
        cand = outsiders.pop()
        blockers = _conflict_set(cand, S)

        if not blockers:
            S.add(cand)
            outsiders = list(all_numbers - S)
            gen.shuffle(outsiders)
            it += 1
            continue

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

        # greedy refill
        for w in refill_order:
            if w not in trial and not _conflict_set(w, trial):
                trial.add(w)

        if len(trial) >= len(S):
            S = trial
            outsiders = list(all_numbers - S)
            gen.shuffle(outsiders)

        it += 1

    # -------------------------------------------------------------
    # 4. Final deterministic sweep (add any remaining safe numbers)
    # -------------------------------------------------------------
    for v in refill_order:
        if v not in S and not _conflict_set(v, S):
            S.add(v)

    # Return a sorted list for reproducibility
    return S
https://ideone.com/6Rs2Wz
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!