fork download 
  1. # your code goes here
  2. M = {
  3.      "algorithm": "Greedy construction ordering numbers by their participation count in 3\u2011APs (low\u2011degree first) with a seeded random tie\u2011break, optionally repeated from several seeds and keeping the largest resulting 3\u2011AP\u2011free set.}  \n\n```python\nimport numpy as np\n\ndef heuristic(n, rng=None):\n    \"\"\"\n    Return a large 3\u2011AP\u2011free subset of {1,\u2026,n",
  4.      "code": "import numpy as np\n\ndef heuristic(n, rng=None):\n    \"\"\"\n    Return a large 3\u2011AP\u2011free subset of {1,\u2026,n}.\n    The algorithm is deterministic for a given (n, rng) pair.\n    \"\"\"\n    # ------------------------------------------------------------------\n    # deterministic RNG handling\n    if rng is None:\n        rng = np.random.default_rng(0)\n    elif isinstance(rng, (int, np.integer)):\n        rng = np.random.default_rng(int(rng))\n    else:                     # assume numpy Generator\n        rng = np.random.default_rng(rng.integers(0, 2**63 - 1))\n\n    # ------------------------------------------------------------------\n    # pre\u2011compute a simple \u201cdegree\u201d = how many 3\u2011AP triples each number belongs to\n    # (within the whole universe).  This is O(n^2) but n\u22641100 is tiny.\n    degree = np.zeros(n + 1, dtype=int)        # 1\u2011based indexing\n    for a in range(1, n + 1):\n        max_d = (n - a) // 2                   # a, a+d, a+2d must stay \u2264 n\n        for d in range(1, max_d + 1):\n            b = a + d\n            c = a + 2 * d\n            degree[a] += 1\n            degree[b] += 1\n            degree[c] += 1\n\n    # ------------------------------------------------------------------\n    # helper: try a single greedy run with a given ordering seed\n    def greedy_one(seed):\n        local_rng = np.random.default_rng(seed)\n        candidates = list(range(1, n + 1))\n        # random tie\u2011break before the degree sort\n        local_rng.shuffle(candidates)\n        candidates.sort(key=lambda x: degree[x])\n\n        in_set = np.zeros(n + 1, dtype=bool)\n        S = []\n\n        for x in candidates:\n            # check whether adding x would close a 3\u2011AP with any already chosen y\n            conflict = False\n            for y in S:\n                # x as the left element: (x, y, z) with z = 2*y - x\n                z = 2 * y - x\n                if 1 <= z <= n and in_set[z]:\n                    conflict = True\n                    break\n                # x as the right element: (z, y, x) with z = 2*y - x (same formula)\n                # x as the middle element: (a, x, c) with a = 2*x - c\n                z = 2 * x - y\n                if 1 <= z <= n and in_set[z]:\n                    conflict = True\n                    break\n            if not conflict:\n                S.append(x)\n                in_set[x] = True\n\n        return S\n\n    # ------------------------------------------------------------------\n    # run a few independent greedy tries (different random seeds) and keep the best\n    best_S = []\n    num_trials = 12                       # modest number, still fast for n\u22481100\n    for t in range(num_trials):\n        trial_seed = rng.integers(0, 2**63 - 1, dtype=np.uint64)\n        S = greedy_one(trial_seed)\n        if len(S) > len(best_S):\n            best_S = S\n\n    # ------------------------------------------------------------------\n    # return a sorted list for reproducibility\n    return S",
  5.      "objective": -128.0,
  6. }
  7. print(M['code'])
Success #stdin #stdout 0.12s 14024KB
comments (?)
stdin 
Standard input is empty
stdout 
import numpy as np

def heuristic(n, rng=None):
    """
    Return a large 3‑AP‑free subset of {1,…,n}.
    The algorithm is deterministic for a given (n, rng) pair.
    """
    # ------------------------------------------------------------------
    # deterministic RNG handling
    if rng is None:
        rng = np.random.default_rng(0)
    elif isinstance(rng, (int, np.integer)):
        rng = np.random.default_rng(int(rng))
    else:                     # assume numpy Generator
        rng = np.random.default_rng(rng.integers(0, 2**63 - 1))

    # ------------------------------------------------------------------
    # pre‑compute a simple “degree” = how many 3‑AP triples each number belongs to
    # (within the whole universe).  This is O(n^2) but n≤1100 is tiny.
    degree = np.zeros(n + 1, dtype=int)        # 1‑based indexing
    for a in range(1, n + 1):
        max_d = (n - a) // 2                   # a, a+d, a+2d must stay ≤ n
        for d in range(1, max_d + 1):
            b = a + d
            c = a + 2 * d
            degree[a] += 1
            degree[b] += 1
            degree[c] += 1

    # ------------------------------------------------------------------
    # helper: try a single greedy run with a given ordering seed
    def greedy_one(seed):
        local_rng = np.random.default_rng(seed)
        candidates = list(range(1, n + 1))
        # random tie‑break before the degree sort
        local_rng.shuffle(candidates)
        candidates.sort(key=lambda x: degree[x])

        in_set = np.zeros(n + 1, dtype=bool)
        S = []

        for x in candidates:
            # check whether adding x would close a 3‑AP with any already chosen y
            conflict = False
            for y in S:
                # x as the left element: (x, y, z) with z = 2*y - x
                z = 2 * y - x
                if 1 <= z <= n and in_set[z]:
                    conflict = True
                    break
                # x as the right element: (z, y, x) with z = 2*y - x (same formula)
                # x as the middle element: (a, x, c) with a = 2*x - c
                z = 2 * x - y
                if 1 <= z <= n and in_set[z]:
                    conflict = True
                    break
            if not conflict:
                S.append(x)
                in_set[x] = True

        return S

    # ------------------------------------------------------------------
    # run a few independent greedy tries (different random seeds) and keep the best
    best_S = []
    num_trials = 12                       # modest number, still fast for n≈1100
    for t in range(num_trials):
        trial_seed = rng.integers(0, 2**63 - 1, dtype=np.uint64)
        S = greedy_one(trial_seed)
        if len(S) > len(best_S):
            best_S = S

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