fork download
copy 
  1. x = {
  2.      "algorithm": "Greedy randomly\u2011ordered insertion of numbers followed by a bounded random\u2011swap local\u2011search that removes conflicting elements and optionally adds up to two new ones, accepting moves that improve or probabilistically accept worsening moves.}  \n\n```python\nimport numpy as np\nfrom typing import List, Set, Union\n\n\ndef _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:\n    \"\"\"Create a deterministic RNG from None, an int seed or a Generator.\"\"\"\n    if rng is None:\n        return np.random.default_rng(0)\n    if isinstance(rng, np.random.Generator):\n        # copy state to avoid side\u2011effects\n        state = rng.bit_generator.state\n        return np.random.Generator(np.random.PCG64(state))\n    return np.random.default_rng(int(rng))\n\n\ndef _conflicts(x: int, S: Set[int]) -> bool:\n    \"\"\"True iff adding x to S creates a 3\u2011AP with two elements already in S.\"\"\"\n    for y in S:\n        # x as middle term\n        if (x + y) % 2 == 0 and ((x + y) // 2) in S:\n            return True\n        # x as an endpoint\n        if (2 * x - y) in S or (2 * y - x) in S:\n            return True\n    return False\n\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\n\ndef _make_rng(rng: Union[None, int, np.random.Generator]) -> np.random.Generator:\n    \"\"\"Create a deterministic RNG from None, an int seed or a Generator.\"\"\"\n    if rng is None:\n        return np.random.default_rng(0)\n    if isinstance(rng, np.random.Generator):\n        # copy state to avoid side\u2011effects\n        state = rng.bit_generator.state\n        return np.random.Generator(np.random.PCG64(state))\n    return np.random.default_rng(int(rng))\n\n\ndef _conflicts(x: int, S: Set[int]) -> bool:\n    \"\"\"True iff adding x to S creates a 3\u2011AP with two elements already in S.\"\"\"\n    for y in S:\n        # x as middle term\n        if (x + y) % 2 == 0 and ((x + y) // 2) in S:\n            return True\n        # x as an endpoint\n        if (2 * x - y) in S or (2 * y - x) in S:\n            return True\n    return False\n\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    The algorithm performs a greedy randomized construction and a short\n    random\u2011swap local improvement phase.\n    \"\"\"\n    if n <= 0:\n        return []\n\n    gen = _make_rng(rng)\n\n    # ---------- 1. Greedy randomized construction ----------\n    all_numbers = np.arange(1, n + 1, dtype=int)\n    gen.shuffle(all_numbers)                     # random order, deterministic\n    S: Set[int] = set()\n    omitted: Set[int] = set()\n\n    for x in all_numbers:\n        if not _conflicts(int(x), S):\n            S.add(int(x))\n        else:\n            omitted.add(int(x))\n\n    # ---------- 2. Local improvement (random swaps) ----------\n    # Budget proportional to sqrt(n) * n to stay fast for a few thousand.\n    budget = int(3 * n * np.sqrt(n))\n    temperature_start = 1.0\n    temperature_end = 0.001\n\n    omitted = set(range(1, n + 1)) - S  # recompute after greedy phase\n\n    for step in range(budget):\n        # linear cooling\n        T = temperature_start + (temperature_end - temperature_start) * (step / budget)\n\n        if not omitted:\n            break\n\n        # pick a random element not in S\n        x = int(gen.choice(list(omitted)))\n\n        # collect elements of S that would conflict with x\n        conflicting: List[int] = []\n        for y in S:\n            if (x + y) % 2 == 0 and ((x + y) // 2) in S:\n                conflicting.append(y)\n            elif (2 * x - y) in S or (2 * y - x) in S:\n                conflicting.append(y)\n\n        # If no conflict we could simply add, but that was already checked.\n        # Try a replace\u2011one\u2011with\u2011up\u2011to\u2011two move.\n        if not conflicting:\n            continue\n\n        # remove one conflicting element (randomly)\n        to_remove = int(gen.choice(conflicting))\n        S.remove(to_remove)\n        omitted.add(to_remove)\n\n        # attempt to insert x and possibly another non\u2011conflicting omitted element\n        added: List[int] = []\n        candidates = [x] + list(omitted)\n        gen.shuffle(candidates)\n\n        for y in candidates:\n            if y == to_remove:\n                continue\n            if not _conflicts(y, S):\n                S.add(y)\n                omitted.remove(y)\n                added.append(y)\n                if len(added) == 2:\n                    break\n\n        net_gain = len(added) - 1   # removed one, added len(added)\n\n        # Acceptance test (accept if gain > 0, else Metropolis)\n        if net_gain > 0 or gen.random() < np.exp(net_gain / max(T, 1e-12)):\n            # keep the move (already applied)\n            pass\n        else:\n            # revert\n            for y in added:\n                S.remove(y)\n                omitted.add(y)\n            S.add(to_remove)\n            omitted.remove(to_remove)\n\n    # Return as a sorted list for reproducibility\n    return S",
  4.      "objective": -95.98843,
  5. }
  6. print(x['code'])
Success #stdin #stdout 0.07s 14116KB
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:
    """Create a deterministic RNG from None, an int seed or a Generator."""
    if rng is None:
        return np.random.default_rng(0)
    if isinstance(rng, np.random.Generator):
        # copy state to avoid side‑effects
        state = rng.bit_generator.state
        return np.random.Generator(np.random.PCG64(state))
    return np.random.default_rng(int(rng))


def _conflicts(x: int, S: Set[int]) -> bool:
    """True iff adding x to S creates a 3‑AP with two elements already in S."""
    for y in S:
        # x as middle term
        if (x + y) % 2 == 0 and ((x + y) // 2) in S:
            return True
        # x as an endpoint
        if (2 * x - y) in S or (2 * y - x) in S:
            return True
    return False


def heuristic(n: int, rng: Union[None, int, np.random.Generator] = None) -> List[int]:
    """
    Return a large 3‑AP‑free subset of {1,…,n}.
    The algorithm performs a greedy randomized construction and a short
    random‑swap local improvement phase.
    """
    if n <= 0:
        return []

    gen = _make_rng(rng)

    # ---------- 1. Greedy randomized construction ----------
    all_numbers = np.arange(1, n + 1, dtype=int)
    gen.shuffle(all_numbers)                     # random order, deterministic
    S: Set[int] = set()
    omitted: Set[int] = set()

    for x in all_numbers:
        if not _conflicts(int(x), S):
            S.add(int(x))
        else:
            omitted.add(int(x))

    # ---------- 2. Local improvement (random swaps) ----------
    # Budget proportional to sqrt(n) * n to stay fast for a few thousand.
    budget = int(3 * n * np.sqrt(n))
    temperature_start = 1.0
    temperature_end = 0.001

    omitted = set(range(1, n + 1)) - S  # recompute after greedy phase

    for step in range(budget):
        # linear cooling
        T = temperature_start + (temperature_end - temperature_start) * (step / budget)

        if not omitted:
            break

        # pick a random element not in S
        x = int(gen.choice(list(omitted)))

        # collect elements of S that would conflict with x
        conflicting: List[int] = []
        for y in S:
            if (x + y) % 2 == 0 and ((x + y) // 2) in S:
                conflicting.append(y)
            elif (2 * x - y) in S or (2 * y - x) in S:
                conflicting.append(y)

        # If no conflict we could simply add, but that was already checked.
        # Try a replace‑one‑with‑up‑to‑two move.
        if not conflicting:
            continue

        # remove one conflicting element (randomly)
        to_remove = int(gen.choice(conflicting))
        S.remove(to_remove)
        omitted.add(to_remove)

        # attempt to insert x and possibly another non‑conflicting omitted element
        added: List[int] = []
        candidates = [x] + list(omitted)
        gen.shuffle(candidates)

        for y in candidates:
            if y == to_remove:
                continue
            if not _conflicts(y, S):
                S.add(y)
                omitted.remove(y)
                added.append(y)
                if len(added) == 2:
                    break

        net_gain = len(added) - 1   # removed one, added len(added)

        # Acceptance test (accept if gain > 0, else Metropolis)
        if net_gain > 0 or gen.random() < np.exp(net_gain / max(T, 1e-12)):
            # keep the move (already applied)
            pass
        else:
            # revert
            for y in added:
                S.remove(y)
                omitted.add(y)
            S.add(to_remove)
            omitted.remove(to_remove)

    # Return as a sorted list for reproducibility
    return S
https://ideone.com/dMlO8G
language:
Python 3 (python  3.12)
created:
3 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!