fork download
copy 
  1. x = {
  2.      "algorithm": "This algorithm constructs a large Salem\u2013Spencer set by greedily adding numbers from 1 to n in a specific order based on their representation in base 3, ensuring the resulting set is 3-AP-free.",
  3.      "code": "import numpy as np\n\ndef heuristic(n, rng=None):\n    if rng is None or isinstance(rng, int):\n        rng = np.random.default_rng(rng)\n    else:\n        rng = rng  # Use the provided rng directly\n\n    S = set()\n    for i in range(1, n+1):\n        # Convert i to base 3 and count the number of 2s\n        num = i\n        base3 = []\n        while num > 0:\n            base3.append(num % 3)\n            num //= 3\n        count_2 = sum(1 for d in base3 if d == 2)\n\n        # Assign a score based on the count of 2s and the number itself\n        score = (count_2, -i)  # Prefer numbers with more 2s and larger numbers\n\n        # Store the number and its score\n        num_data = (i, score)\n\n        # Yield numbers in order of their score\n        yield num_data\n\n    # Sort numbers based on their score\n    nums = sorted([num_data for num_data in heuristic(n, rng)], key=lambda x: x[1])\n\n    # Greedily add numbers to S if they don't form a 3-AP\n    S = set()\n    for num, _ in nums:\n        is_AP_free = True\n        for s in S:\n            if 2*s - num in S or 2*num - s in S:\n                is_AP_free = False\n                break\n        if is_AP_free:\n            S.add(num)\n\n    return sorted(list(S))\n\n# Corrected version:\ndef heuristic(n, rng=None):\n    if rng is None or isinstance(rng, int):\n        rng = np.random.default_rng(rng)\n    S = set()\n    for i in range(1, n+1):\n        num = i\n        base3 = []\n        while num > 0:\n            base3.append(num % 3)\n            num //= 3\n        count_2 = sum(1 for d in base3 if d == 2)\n        score = (count_2, -i)\n        if not any(2*s - i in S or 2*i - s in S for s in S):\n            S.add(i)\n    return S",
  4.      "objective": -128.0,
  5. }
  6. print(x["code"])
  7.  
  8. x1 = {
  9.      "algorithm": "This algorithm constructs a large Salem\u2013Spencer set by greedily adding numbers from 1 to n, prioritizing those with a lower probability of forming a 3-term arithmetic progression, and utilizing a hash set for efficient membership checks.",
  10.      "code": "import numpy as np\n\ndef heuristic(n, rng=None):\n    if rng is None or isinstance(rng, int):\n        rng = np.random.default_rng(rng)\n    S = set()\n    candidates = list(range(1, n + 1))\n    # Prioritize numbers with fewer representations as part of an AP\n    candidates.sort(key=lambda x: sum(1 for y in S if 2*y-x in S or (x+y) % 2 == 0 and (x+y)//2 in S))\n    for x in candidates:\n        if not any(2*y - x in S for y in S) and x not in S:\n            S.add(x)\n    return S",
  11.      "objective": -128.0,
  12. }
  13. print("=" * 50)
  14. print(x1["code"])
Success #stdin #stdout 0.13s 14172KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
import numpy as np

def heuristic(n, rng=None):
    if rng is None or isinstance(rng, int):
        rng = np.random.default_rng(rng)
    else:
        rng = rng  # Use the provided rng directly

    S = set()
    for i in range(1, n+1):
        # Convert i to base 3 and count the number of 2s
        num = i
        base3 = []
        while num > 0:
            base3.append(num % 3)
            num //= 3
        count_2 = sum(1 for d in base3 if d == 2)

        # Assign a score based on the count of 2s and the number itself
        score = (count_2, -i)  # Prefer numbers with more 2s and larger numbers

        # Store the number and its score
        num_data = (i, score)

        # Yield numbers in order of their score
        yield num_data

    # Sort numbers based on their score
    nums = sorted([num_data for num_data in heuristic(n, rng)], key=lambda x: x[1])

    # Greedily add numbers to S if they don't form a 3-AP
    S = set()
    for num, _ in nums:
        is_AP_free = True
        for s in S:
            if 2*s - num in S or 2*num - s in S:
                is_AP_free = False
                break
        if is_AP_free:
            S.add(num)

    return sorted(list(S))

# Corrected version:
def heuristic(n, rng=None):
    if rng is None or isinstance(rng, int):
        rng = np.random.default_rng(rng)
    S = set()
    for i in range(1, n+1):
        num = i
        base3 = []
        while num > 0:
            base3.append(num % 3)
            num //= 3
        count_2 = sum(1 for d in base3 if d == 2)
        score = (count_2, -i)
        if not any(2*s - i in S or 2*i - s in S for s in S):
            S.add(i)
    return S
==================================================
import numpy as np

def heuristic(n, rng=None):
    if rng is None or isinstance(rng, int):
        rng = np.random.default_rng(rng)
    S = set()
    candidates = list(range(1, n + 1))
    # Prioritize numbers with fewer representations as part of an AP
    candidates.sort(key=lambda x: sum(1 for y in S if 2*y-x in S or (x+y) % 2 == 0 and (x+y)//2 in S))
    for x in candidates:
        if not any(2*y - x in S for y in S) and x not in S:
            S.add(x)
    return S
https://ideone.com/5etQOY
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!