fork download
copy 
  1. # # your code goes here
  2. # mydict = {
  3. #      "algorithm": "This algorithm constructs a 3-AP-free set by greedily adding numbers based on a score that prioritizes elements that are less likely to form an arithmetic progression with already chosen elements, specifically by favoring numbers with fewer potential arithmetic progression partners given the current set S.}\n\n```python\nimport numpy as np\n\ndef heuristic(n, rng=None):\n    if rng is None:\n        rng = np.random.default_rng()\n    elif isinstance(rng, int):\n        rng = np.random.default_rng(rng)\n\n    S = set()\n    S_list = []\n    \n    # Pre-calculate potential AP partners for efficiency\n    potential_partners = {i: set() for i in range(1, n + 1)}\n    for i in range(1, n + 1):\n        for j in range(i + 1, n + 1):\n            # Check for z such that (i, j, z) or (j, i, z)\n            z1 = 2 * j - i\n            if 1 <= z1 <= n:\n                potential_partners[i].add(z1)\n                potential_partners[z1].add(i)\n            z2 = 2 * i - j\n            if 1 <= z2 <= n:\n                potential_partners[j].add(z2)\n                potential_partners[z2].add(j)\n            \n            # Check for z such that (i, z, j)\n            if (i + j) % 2 == 0:\n                z3 = (i + j) // 2\n                if 1 <= z3 <= n:\n                    potential_partners[i].add(z3)\n                    potential_partners[z3].add(i)\n                    potential_partners[j].add(z3)\n                    potential_partners[z3].add(j)\n    \n    # Initialize scores: number of potential AP partners that are *not* yet in S\n    scores = {i: len(potential_partners[i]) for i in range(1, n + 1)",
  4. #      "code": "import numpy as np\n\ndef heuristic(n, rng=None):\n    if rng is None:\n        rng = np.random.default_rng()\n    elif isinstance(rng, int):\n        rng = np.random.default_rng(rng)\n\n    S = set()\n    S_list = []\n    \n    # Pre-calculate potential AP partners for efficiency\n    potential_partners = {i: set() for i in range(1, n + 1)}\n    for i in range(1, n + 1):\n        for j in range(i + 1, n + 1):\n            # Check for z such that (i, j, z) or (j, i, z)\n            z1 = 2 * j - i\n            if 1 <= z1 <= n:\n                potential_partners[i].add(z1)\n                potential_partners[z1].add(i)\n            z2 = 2 * i - j\n            if 1 <= z2 <= n:\n                potential_partners[j].add(z2)\n                potential_partners[z2].add(j)\n            \n            # Check for z such that (i, z, j)\n            if (i + j) % 2 == 0:\n                z3 = (i + j) // 2\n                if 1 <= z3 <= n:\n                    potential_partners[i].add(z3)\n                    potential_partners[z3].add(i)\n                    potential_partners[j].add(z3)\n                    potential_partners[z3].add(j)\n    \n    # Initialize scores: number of potential AP partners that are *not* yet in S\n    scores = {i: len(potential_partners[i]) for i in range(1, n + 1)}\n    \n    candidates = list(range(1, n + 1))\n    rng.shuffle(candidates) # Initial shuffle to break ties randomly\n\n    # Sort candidates based on scores (lower score is better)\n    candidates.sort(key=lambda x: scores[x])\n\n    for x in candidates:\n        is_ap_free = True\n        for y in S_list:\n            # Check for (y, x, z) or (z, x, y) where x is the middle term\n            z1 = 2 * x - y\n            if z1 in S:\n                is_ap_free = False\n                break\n\n            # Check for (x, y, z) or (z, y, x) where y is the middle term\n            z2 = 2 * y - x\n            if z2 in S:\n                is_ap_free = False\n                break\n\n            # Check for (x, z, y) or (y, z, x) where z is the middle term\n            if (x + y) % 2 == 0:\n                z3 = (x + y) // 2\n                if z3 in S:\n                    is_ap_free = False\n                    break\n        \n        if is_ap_free:\n            S.add(x)\n            S_list.append(x)\n            \n            # Update scores of other numbers:\n            # When x is added to S, any number 'k' that could form an AP with x\n            # now has one less potential partner that is NOT in S.\n            # This means scores[k] should decrease if k is one of x's potential partners.\n            # For elements in S, their potential partners *in S* are now irrelevant for AP checks.\n            # We can re-evaluate scores dynamically. A simpler approach is to remove x\n            # from the potential_partners sets of other numbers.\n            for partner in list(potential_partners[x]): # Iterate over a copy\n                if partner in scores: # If partner is still a candidate\n                    scores[partner] -= 1\n                    # Remove x from partner's consideration to avoid double counting\n                    if x in potential_partners[partner]:\n                        potential_partners[partner].remove(x)\n\n            # Remove x from the candidate pool and update scores of its partners that are not yet in S\n            # This dynamic re-sorting can be costly. A fixed order based on initial scores is simpler.\n            # For this heuristic, we rely on the initial sorted order of candidates.\n            \n    return S",
  5. #      "objective": -0.13086,
  6. #      "other_inf": None
  7. # }
  8.  
  9. # for k in mydict.keys():
  10. # 	print(mydict[k])
  11. # 	print("-" * 50)
  12. import numpy as np
  13.  
  14. def heuristic(n, rng=None):
  15.     if rng is None:
  16.         rng = np.random.default_rng()
  17.     elif isinstance(rng, int):
  18.         rng = np.random.default_rng(rng)
  19.  
  20.     S = set()
  21.     S_list = []
  22.  
  23.     # Pre-calculate potential AP partners for efficiency
  24.     potential_partners = {i: set() for i in range(1, n + 1)}
  25.     for i in range(1, n + 1):
  26.         for j in range(i + 1, n + 1):
  27.             # Check for z such that (i, j, z) or (j, i, z)
  28.             z1 = 2 * j - i
  29.             if 1 <= z1 <= n:
  30.                 potential_partners[i].add(z1)
  31.                 potential_partners[z1].add(i)
  32.             z2 = 2 * i - j
  33.             if 1 <= z2 <= n:
  34.                 potential_partners[j].add(z2)
  35.                 potential_partners[z2].add(j)
  36.  
  37.             # Check for z such that (i, z, j)
  38.             if (i + j) % 2 == 0:
  39.                 z3 = (i + j) // 2
  40.                 if 1 <= z3 <= n:
  41.                     potential_partners[i].add(z3)
  42.                     potential_partners[z3].add(i)
  43.                     potential_partners[j].add(z3)
  44.                     potential_partners[z3].add(j)
  45.  
  46.     # Initialize scores: number of potential AP partners that are *not* yet in S
  47.     scores = {i: len(potential_partners[i]) for i in range(1, n + 1)}
  48.  
  49.     candidates = list(range(1, n + 1))
  50.     rng.shuffle(candidates) # Initial shuffle to break ties randomly
  51.  
  52.     # Sort candidates based on scores (lower score is better)
  53.     candidates.sort(key=lambda x: scores[x])
  54.  
  55.     for x in candidates:
  56.         is_ap_free = True
  57.         for y in S_list:
  58.             # Check for (y, x, z) or (z, x, y) where x is the middle term
  59.             z1 = 2 * x - y
  60.             if z1 in S:
  61.                 is_ap_free = False
  62.                 break
  63.  
  64.             # Check for (x, y, z) or (z, y, x) where y is the middle term
  65.             z2 = 2 * y - x
  66.             if z2 in S:
  67.                 is_ap_free = False
  68.                 break
  69.  
  70.             # Check for (x, z, y) or (y, z, x) where z is the middle term
  71.             if (x + y) % 2 == 0:
  72.                 z3 = (x + y) // 2
  73.                 if z3 in S:
  74.                     is_ap_free = False
  75.                     break
  76.  
  77.         if is_ap_free:
  78.             S.add(x)
  79.             S_list.append(x)
  80.  
  81.             # Update scores of other numbers:
  82.             # When x is added to S, any number 'k' that could form an AP with x
  83.             # now has one less potential partner that is NOT in S.
  84.             # This means scores[k] should decrease if k is one of x's potential partners.
  85.             # For elements in S, their potential partners *in S* are now irrelevant for AP checks.
  86.             # We can re-evaluate scores dynamically. A simpler approach is to remove x
  87.             # from the potential_partners sets of other numbers.
  88.             for partner in list(potential_partners[x]): # Iterate over a copy
  89.                 if partner in scores: # If partner is still a candidate
  90.                     scores[partner] -= 1
  91.                     # Remove x from partner's consideration to avoid double counting
  92.                     if x in potential_partners[partner]:
  93.                         potential_partners[partner].remove(x)
  94.  
  95.             # Remove x from the candidate pool and update scores of its partners that are not yet in S
  96.             # This dynamic re-sorting can be costly. A fixed order based on initial scores is simpler.
  97.             # For this heuristic, we rely on the initial sorted order of candidates.
  98.  
  99.     return S
  100.  
  101. s = heuristic(n=82)
  102. print(s, len(s))
Success #stdin #stdout 1.09s 40716KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 69, 70, 72, 73, 78, 79, 81, 82} 20
https://ideone.com/F3tXQj
language:
Python 3 (python  3.12)
created:
8 days 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!