fork download
copy 
  1. x = {
  2.      "algorithm": "Construct the Salem\u2013Spencer set by first taking all numbers \u2264\u202fn whose ternary representation contains no digit\u202f2 (the \u201cCantor\u201d construction), then apply a short weighted\u2011score local search that prefers removing middle\u2011role conflicts over outer\u2011role conflicts (weights\u202fw_outer=1,\u202fw_mid=2).} \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    \"\"\"Return a deterministic Generator from seed/int/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 _has_no_digit_two(x: int) -> bool:\n    \"\"\"True iff the base\u20113 representation of x contains no digit 2.\"\"\"\n    while x:\n        if x % 3 == 2:\n            return False\n        x //= 3\n    return True\n\n\ndef _conflict_sets(val: int, cur: Set[int]) -> Tuple[Set[int], Set[int]]:\n    \"\"\"\n    Return two sets of conflicts with `val` against the current set `cur`:\n      outer \u2013 members that together with `val` would be the two outer terms\n               of a 3\u2011AP whose middle is already in `cur`.\n      middle \u2013 members that would be the middle term of a 3\u2011AP with `val`\n               as one outer term.\n    \"\"\"\n    outer = set()\n    middle = set()\n    for y in cur:\n        s = val + y\n        if s % 2 == 0 and (s // 2) in cur:\n            outer.add(y)                 # y is the other outer term\n        if (2 * val - y) in cur:\n            middle.add(y)                # y is the other outer term, val middle\n        if (2 * y - val) in cur:\n            outer.add(y)                 # y is middle, val outer\n    return outer, middle\n\n\ndef _weighted_score(val: int, cur: Set[int],\n                    w_outer: int = 1, w_mid: int = 2) -> int:\n    \"\"\"Score = w_outer\u00b7|outer| + w_mid\u00b7|middle|; lower is better.\"\"\"\n    outer, middle = _conflict_sets(val, cur)\n    return w_outer * len(outer) + w_mid * len(middle)\n\n\ndef heuristic(n: int,\n              rng: Union[None, int, np.random.Generator] = None) -> List[int]:\n    \"\"\"\n    Build a large 3\u2011AP\u2011free subset of {1,\u2026,n}.\n    1. Initialise with the \u201cCantor\u201d set (no ternary digit\u202f2).\n    2. Perform a bounded local search that swaps out up to three conflicting\n       elements for a missing element, using a score that penalises middle\u2011role\n       conflicts twice as much as outer\u2011role conflicts.\n    Returns the final set as a sorted list.\n    \"\"\"\n    if n <= 0:\n        return []\n\n    rng = _make_rng(rng)\n\n    # -----------------------------------------------------------------\n    # 1. Base Cantor construction\n    # -----------------------------------------------------------------\n    S: Set[int] = {i for i in range(1, n + 1) if _has_no_digit_two(i)",
  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    \"\"\"Return a deterministic Generator from seed/int/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 _has_no_digit_two(x: int) -> bool:\n    \"\"\"True iff the base\u20113 representation of x contains no digit 2.\"\"\"\n    while x:\n        if x % 3 == 2:\n            return False\n        x //= 3\n    return True\n\n\ndef _conflict_sets(val: int, cur: Set[int]) -> Tuple[Set[int], Set[int]]:\n    \"\"\"\n    Return two sets of conflicts with `val` against the current set `cur`:\n      outer \u2013 members that together with `val` would be the two outer terms\n               of a 3\u2011AP whose middle is already in `cur`.\n      middle \u2013 members that would be the middle term of a 3\u2011AP with `val`\n               as one outer term.\n    \"\"\"\n    outer = set()\n    middle = set()\n    for y in cur:\n        s = val + y\n        if s % 2 == 0 and (s // 2) in cur:\n            outer.add(y)                 # y is the other outer term\n        if (2 * val - y) in cur:\n            middle.add(y)                # y is the other outer term, val middle\n        if (2 * y - val) in cur:\n            outer.add(y)                 # y is middle, val outer\n    return outer, middle\n\n\ndef _weighted_score(val: int, cur: Set[int],\n                    w_outer: int = 1, w_mid: int = 2) -> int:\n    \"\"\"Score = w_outer\u00b7|outer| + w_mid\u00b7|middle|; lower is better.\"\"\"\n    outer, middle = _conflict_sets(val, cur)\n    return w_outer * len(outer) + w_mid * len(middle)\n\n\ndef heuristic(n: int,\n              rng: Union[None, int, np.random.Generator] = None) -> List[int]:\n    \"\"\"\n    Build a large 3\u2011AP\u2011free subset of {1,\u2026,n}.\n    1. Initialise with the \u201cCantor\u201d set (no ternary digit\u202f2).\n    2. Perform a bounded local search that swaps out up to three conflicting\n       elements for a missing element, using a score that penalises middle\u2011role\n       conflicts twice as much as outer\u2011role conflicts.\n    Returns the final set as a sorted list.\n    \"\"\"\n    if n <= 0:\n        return []\n\n    rng = _make_rng(rng)\n\n    # -----------------------------------------------------------------\n    # 1. Base Cantor construction\n    # -----------------------------------------------------------------\n    S: Set[int] = {i for i in range(1, n + 1) if _has_no_digit_two(i)}\n    missing: List[int] = [i for i in range(1, n + 1) if i not in S]\n    rng.shuffle(missing)                     # deterministic tie\u2011breaker\n\n    # -----------------------------------------------------------------\n    # 2. Local improvement (swap \u22643 conflicting members for one missing)\n    # -----------------------------------------------------------------\n    budget = int(4 * np.sqrt(n)) + 200        # number of attempts\n    attempts = 0\n    idx = 0\n\n    while attempts < budget and missing:\n        x = missing[idx % len(missing)]\n        idx += 1\n        attempts += 1\n\n        # compute conflicts of x with current set\n        outer, middle = _conflict_sets(x, S)\n        all_conf = outer | middle\n\n        if not all_conf:\n            # x fits for free \u2013 just add it\n            S.add(x)\n            missing.remove(x)\n            attempts = 0\n            continue\n\n        # limit to at most three conflicting elements; otherwise skip\n        if len(all_conf) > 3:\n            continue\n\n        # enumerate all non\u2011empty subsets of size \u22643 of the conflicting set\n        conf_list = list(all_conf)\n        best_combo = None\n        for r in range(1, min(3, len(conf_list)) + 1):\n            # small numbers \u2192 simple bit\u2011mask enumeration\n            for mask in range(1 << len(conf_list)):\n                if bin(mask).count(\"1\") != r:\n                    continue\n                combo = tuple(conf_list[i] for i in range(len(conf_list))\n                               if (mask >> i) & 1)\n                temp = S.difference(combo)\n                if not _conflict_sets(x, temp)[0] and not _conflict_sets(x, temp)[1]:\n                    best_combo = combo\n                    break\n            if best_combo is not None:\n                break\n\n        if best_combo is None:\n            continue\n\n        # perform the swap\n        for y in best_combo:\n            S.remove(y)\n            missing.append(y)\n        S.add(x)\n        missing.remove(x)\n        attempts = 0\n\n        # after a successful swap, greedily insert any newly free numbers\n        filler = True\n        while filler:\n            filler = False\n            for y in list(missing):\n                if not _conflict_sets(y, S)[0] and not _conflict_sets(y, S)[1]:\n                    S.add(y)\n                    missing.remove(y)\n                    filler = True\n                    attempts = 0\n\n    # final deterministic ordering\n    return S",
  4.      "objective": -103.69615
  5. }
  6. print(x['code'])
Success #stdin #stdout 0.08s 14092KB
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:
    """Return a deterministic Generator from seed/int/Generator."""
    if isinstance(rng, np.random.Generator):
        return rng
    return np.random.default_rng(0 if rng is None else int(rng))


def _has_no_digit_two(x: int) -> bool:
    """True iff the base‑3 representation of x contains no digit 2."""
    while x:
        if x % 3 == 2:
            return False
        x //= 3
    return True


def _conflict_sets(val: int, cur: Set[int]) -> Tuple[Set[int], Set[int]]:
    """
    Return two sets of conflicts with `val` against the current set `cur`:
      outer – members that together with `val` would be the two outer terms
               of a 3‑AP whose middle is already in `cur`.
      middle – members that would be the middle term of a 3‑AP with `val`
               as one outer term.
    """
    outer = set()
    middle = set()
    for y in cur:
        s = val + y
        if s % 2 == 0 and (s // 2) in cur:
            outer.add(y)                 # y is the other outer term
        if (2 * val - y) in cur:
            middle.add(y)                # y is the other outer term, val middle
        if (2 * y - val) in cur:
            outer.add(y)                 # y is middle, val outer
    return outer, middle


def _weighted_score(val: int, cur: Set[int],
                    w_outer: int = 1, w_mid: int = 2) -> int:
    """Score = w_outer·|outer| + w_mid·|middle|; lower is better."""
    outer, middle = _conflict_sets(val, cur)
    return w_outer * len(outer) + w_mid * len(middle)


def heuristic(n: int,
              rng: Union[None, int, np.random.Generator] = None) -> List[int]:
    """
    Build a large 3‑AP‑free subset of {1,…,n}.
    1. Initialise with the “Cantor” set (no ternary digit 2).
    2. Perform a bounded local search that swaps out up to three conflicting
       elements for a missing element, using a score that penalises middle‑role
       conflicts twice as much as outer‑role conflicts.
    Returns the final set as a sorted list.
    """
    if n <= 0:
        return []

    rng = _make_rng(rng)

    # -----------------------------------------------------------------
    # 1. Base Cantor construction
    # -----------------------------------------------------------------
    S: Set[int] = {i for i in range(1, n + 1) if _has_no_digit_two(i)}
    missing: List[int] = [i for i in range(1, n + 1) if i not in S]
    rng.shuffle(missing)                     # deterministic tie‑breaker

    # -----------------------------------------------------------------
    # 2. Local improvement (swap ≤3 conflicting members for one missing)
    # -----------------------------------------------------------------
    budget = int(4 * np.sqrt(n)) + 200        # number of attempts
    attempts = 0
    idx = 0

    while attempts < budget and missing:
        x = missing[idx % len(missing)]
        idx += 1
        attempts += 1

        # compute conflicts of x with current set
        outer, middle = _conflict_sets(x, S)
        all_conf = outer | middle

        if not all_conf:
            # x fits for free – just add it
            S.add(x)
            missing.remove(x)
            attempts = 0
            continue

        # limit to at most three conflicting elements; otherwise skip
        if len(all_conf) > 3:
            continue

        # enumerate all non‑empty subsets of size ≤3 of the conflicting set
        conf_list = list(all_conf)
        best_combo = None
        for r in range(1, min(3, len(conf_list)) + 1):
            # small numbers → simple bit‑mask enumeration
            for mask in range(1 << len(conf_list)):
                if bin(mask).count("1") != r:
                    continue
                combo = tuple(conf_list[i] for i in range(len(conf_list))
                               if (mask >> i) & 1)
                temp = S.difference(combo)
                if not _conflict_sets(x, temp)[0] and not _conflict_sets(x, temp)[1]:
                    best_combo = combo
                    break
            if best_combo is not None:
                break

        if best_combo is None:
            continue

        # perform the swap
        for y in best_combo:
            S.remove(y)
            missing.append(y)
        S.add(x)
        missing.remove(x)
        attempts = 0

        # after a successful swap, greedily insert any newly free numbers
        filler = True
        while filler:
            filler = False
            for y in list(missing):
                if not _conflict_sets(y, S)[0] and not _conflict_sets(y, S)[1]:
                    S.add(y)
                    missing.remove(y)
                    filler = True
                    attempts = 0

    # final deterministic ordering
    return S
https://ideone.com/wyFJJ1
language:
Python 3 (python  3.12)
created:
2 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!