fork download
copy 
  1. # your code goes here
  2. mydict = {
  3.      "algorithm": "This heuristic greedily adds numbers to a Salem-Spencer set, prioritizing numbers with fewer forbidden arithmetic progressions, and then performs a limited local search to improve the set's size.}\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    # Precompute forbidden pairs for each number up to n\n    # forbidden_pairs[x] will be a set of numbers y such that x+y is even,\n    # and if x and y are in S, 2b = x+y implies b is forbidden.\n    forbidden_pairs = [set() for _ in range(n + 1)]\n    \n    # Generate candidates and sort them by a heuristic\n    # The heuristic is to prioritize numbers that participate in fewer potential APs\n    # with numbers already in S.\n    \n    candidate_scores = {}\n    for num in range(1, n + 1):\n        score = 0\n        # Estimate the number of potential APs this number could form with existing elements\n        # For a potential AP (a, b, c), if we consider adding 'num' as 'c', then 'a' would be 2b - num.\n        # If we consider adding 'num' as 'a', then 'c' would be 2b - num.\n        # If we consider adding 'num' as 'b', then 'a' and 'c' would be num-k and num+k for some k.\n        # A simpler heuristic is to count how many numbers 'x' and 'y' exist such that x + y = 2 * num.\n        # This is equivalent to x and y being symmetric around num.\n        \n        # This simple scoring counts how many pairs (x,y) exist such that x+y=2*num\n        # and x, y are in {1..n",
  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    # Precompute forbidden pairs for each number up to n\n    # forbidden_pairs[x] will be a set of numbers y such that x+y is even,\n    # and if x and y are in S, 2b = x+y implies b is forbidden.\n    forbidden_pairs = [set() for _ in range(n + 1)]\n    \n    # Generate candidates and sort them by a heuristic\n    # The heuristic is to prioritize numbers that participate in fewer potential APs\n    # with numbers already in S.\n    \n    candidate_scores = {}\n    for num in range(1, n + 1):\n        score = 0\n        # Estimate the number of potential APs this number could form with existing elements\n        # For a potential AP (a, b, c), if we consider adding 'num' as 'c', then 'a' would be 2b - num.\n        # If we consider adding 'num' as 'a', then 'c' would be 2b - num.\n        # If we consider adding 'num' as 'b', then 'a' and 'c' would be num-k and num+k for some k.\n        # A simpler heuristic is to count how many numbers 'x' and 'y' exist such that x + y = 2 * num.\n        # This is equivalent to x and y being symmetric around num.\n        \n        # This simple scoring counts how many pairs (x,y) exist such that x+y=2*num\n        # and x, y are in {1..n} and x < num < y.\n        for k in range(1, min(num, n - num + 1)):\n            if num - k >= 1 and num + k <= n:\n                score += 1\n        candidate_scores[num] = score\n\n    sorted_candidates = sorted(range(1, n + 1), key=lambda x: candidate_scores[x])\n\n    # Greedy phase\n    for num in sorted_candidates:\n        is_forbidden = False\n        for s_val in S:\n            diff = num - s_val\n            # Check if num can form an AP with two existing elements in S\n            # Case 1: s_val is the middle element (a, s_val, num) => a = 2*s_val - num\n            if 2 * s_val - num in S:\n                is_forbidden = True\n                break\n            # Case 2: num is the middle element (s_val, num, c) => c = 2*num - s_val\n            if 2 * num - s_val in S:\n                is_forbidden = True\n                break\n        \n        if not is_forbidden:\n            S.add(num)\n            S_list.append(num)\n\n    # Local improvement phase (limited budget)\n    # Try to swap elements from outside S with elements in S if it increases size.\n    # This is a very basic local search, can be expanded.\n    \n    current_size = len(S_list)\n    \n    # Try adding an element from outside S that was rejected\n    # and removing an element from S to maintain 3-AP-free property.\n    # This is computationally more expensive.\n\n    # A simpler local search: try to swap a few elements.\n    # For simplicity, we will just try to add elements that were skipped if possible,\n    # and then try to see if we can remove an element and add two others.\n    \n    # Let's stick to a simpler local improvement: try to add elements if they don't break 3-AP.\n    # This is more like an extension of the greedy phase.\n    # Re-sort candidates that are not in S\n    \n    remaining_candidates = sorted([x for x in range(1, n + 1) if x not in S], key=lambda x: candidate_scores.get(x, float('inf')))\n\n    for num in remaining_candidates:\n        is_forbidden = False\n        for s_val in S:\n            diff = num - s_val\n            if 2 * s_val - num in S:\n                is_forbidden = True\n                break\n            if 2 * num - s_val in S:\n                is_forbidden = True\n                break\n        \n        if not is_forbidden:\n            S.add(num)\n            S_list.append(num)\n            # Re-sort S_list to keep it somewhat ordered if needed for future steps\n            S_list.sort() \n    \n    return S",
  5.      "objective": -0.125,
  6.      "other_inf": None
  7. }
  8. print(mydict["algorithm"])
  9. print('-' * 50)
  10. print(mydict["code"])
  11. print('-' * 50)
  12.  
  13.  
  14. import numpy as np
  15.  
  16. def heuristic(n, rng=None):
  17.     if rng is None:
  18.         rng = np.random.default_rng()
  19.     elif isinstance(rng, int):
  20.         rng = np.random.default_rng(rng)
  21.  
  22.     S = set()
  23.     S_list = []
  24.  
  25.     # Precompute forbidden pairs for each number up to n
  26.     # forbidden_pairs[x] will be a set of numbers y such that x+y is even,
  27.     # and if x and y are in S, 2b = x+y implies b is forbidden.
  28.     forbidden_pairs = [set() for _ in range(n + 1)]
  29.  
  30.     # Generate candidates and sort them by a heuristic
  31.     # The heuristic is to prioritize numbers that participate in fewer potential APs
  32.     # with numbers already in S.
  33.  
  34.     candidate_scores = {}
  35.     for num in range(1, n + 1):
  36.         score = 0
  37.         # Estimate the number of potential APs this number could form with existing elements
  38.         # For a potential AP (a, b, c), if we consider adding 'num' as 'c', then 'a' would be 2b - num.
  39.         # If we consider adding 'num' as 'a', then 'c' would be 2b - num.
  40.         # If we consider adding 'num' as 'b', then 'a' and 'c' would be num-k and num+k for some k.
  41.         # A simpler heuristic is to count how many numbers 'x' and 'y' exist such that x + y = 2 * num.
  42.         # This is equivalent to x and y being symmetric around num.
  43.  
  44.         # This simple scoring counts how many pairs (x,y) exist such that x+y=2*num
  45.         # and x, y are in {1..n} and x &lt; num &lt; y.
  46.         for k in range(1, min(num, n - num + 1)):
  47.             if num - k >= 1 and num + k <= n:
  48.                 score += 1
  49.         candidate_scores[num] = score
  50.  
  51.     sorted_candidates = sorted(range(1, n + 1), key=lambda x: candidate_scores[x])
  52.  
  53.     # Greedy phase
  54.     for num in sorted_candidates:
  55.         is_forbidden = False
  56.         for s_val in S:
  57.             diff = num - s_val
  58.             # Check if num can form an AP with two existing elements in S
  59.             # Case 1: s_val is the middle element (a, s_val, num) =&gt; a = 2*s_val - num
  60.             if 2 * s_val - num in S:
  61.                 is_forbidden = True
  62.                 break
  63.             # Case 2: num is the middle element (s_val, num, c) =&gt; c = 2*num - s_val
  64.             if 2 * num - s_val in S:
  65.                 is_forbidden = True
  66.                 break
  67.  
  68.         if not is_forbidden:
  69.             S.add(num)
  70.             S_list.append(num)
  71.  
  72.     # Local improvement phase (limited budget)
  73.     # Try to swap elements from outside S with elements in S if it increases size.
  74.     # This is a very basic local search, can be expanded.
  75.  
  76.     current_size = len(S_list)
  77.  
  78.     # Try adding an element from outside S that was rejected
  79.     # and removing an element from S to maintain 3-AP-free property.
  80.     # This is computationally more expensive.
  81.  
  82.     # A simpler local search: try to swap a few elements.
  83.     # For simplicity, we will just try to add elements that were skipped if possible,
  84.     # and then try to see if we can remove an element and add two others.
  85.  
  86.     # Let's stick to a simpler local improvement: try to add elements if they don't break 3-AP.
  87.     # This is more like an extension of the greedy phase.
  88.     # Re-sort candidates that are not in S
  89.  
  90.     remaining_candidates = sorted([x for x in range(1, n + 1) if x not in S], key=lambda x: candidate_scores.get(x, float('inf')))
  91.  
  92.     for num in remaining_candidates:
  93.         is_forbidden = False
  94.         for s_val in S:
  95.             diff = num - s_val
  96.             if 2 * s_val - num in S:
  97.                 is_forbidden = True
  98.                 break
  99.             if 2 * num - s_val in S:
  100.                 is_forbidden = True
  101.                 break
  102.  
  103.         if not is_forbidden:
  104.             S.add(num)
  105.             S_list.append(num)
  106.             # Re-sort S_list to keep it somewhat ordered if needed for future steps
  107.             S_list.sort() 
  108.  
  109.     return S
  110.  
  111.  
  112. s = heuristic(n = 82)
  113. print(s, len(s))
Success #stdin #stdout 0.81s 41152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
This heuristic greedily adds numbers to a Salem-Spencer set, prioritizing numbers with fewer forbidden arithmetic progressions, and then performs a limited local search to improve the set's size.}

```python
import numpy as np

def heuristic(n, rng=None):
    if rng is None:
        rng = np.random.default_rng()
    elif isinstance(rng, int):
        rng = np.random.default_rng(rng)
    
    S = set()
    S_list = []
    
    # Precompute forbidden pairs for each number up to n
    # forbidden_pairs[x] will be a set of numbers y such that x+y is even,
    # and if x and y are in S, 2b = x+y implies b is forbidden.
    forbidden_pairs = [set() for _ in range(n + 1)]
    
    # Generate candidates and sort them by a heuristic
    # The heuristic is to prioritize numbers that participate in fewer potential APs
    # with numbers already in S.
    
    candidate_scores = {}
    for num in range(1, n + 1):
        score = 0
        # Estimate the number of potential APs this number could form with existing elements
        # For a potential AP (a, b, c), if we consider adding 'num' as 'c', then 'a' would be 2b - num.
        # If we consider adding 'num' as 'a', then 'c' would be 2b - num.
        # If we consider adding 'num' as 'b', then 'a' and 'c' would be num-k and num+k for some k.
        # A simpler heuristic is to count how many numbers 'x' and 'y' exist such that x + y = 2 * num.
        # This is equivalent to x and y being symmetric around num.
        
        # This simple scoring counts how many pairs (x,y) exist such that x+y=2*num
        # and x, y are in {1..n
--------------------------------------------------
import numpy as np

def heuristic(n, rng=None):
    if rng is None:
        rng = np.random.default_rng()
    elif isinstance(rng, int):
        rng = np.random.default_rng(rng)
    
    S = set()
    S_list = []
    
    # Precompute forbidden pairs for each number up to n
    # forbidden_pairs[x] will be a set of numbers y such that x+y is even,
    # and if x and y are in S, 2b = x+y implies b is forbidden.
    forbidden_pairs = [set() for _ in range(n + 1)]
    
    # Generate candidates and sort them by a heuristic
    # The heuristic is to prioritize numbers that participate in fewer potential APs
    # with numbers already in S.
    
    candidate_scores = {}
    for num in range(1, n + 1):
        score = 0
        # Estimate the number of potential APs this number could form with existing elements
        # For a potential AP (a, b, c), if we consider adding 'num' as 'c', then 'a' would be 2b - num.
        # If we consider adding 'num' as 'a', then 'c' would be 2b - num.
        # If we consider adding 'num' as 'b', then 'a' and 'c' would be num-k and num+k for some k.
        # A simpler heuristic is to count how many numbers 'x' and 'y' exist such that x + y = 2 * num.
        # This is equivalent to x and y being symmetric around num.
        
        # This simple scoring counts how many pairs (x,y) exist such that x+y=2*num
        # and x, y are in {1..n} and x < num < y.
        for k in range(1, min(num, n - num + 1)):
            if num - k >= 1 and num + k <= n:
                score += 1
        candidate_scores[num] = score

    sorted_candidates = sorted(range(1, n + 1), key=lambda x: candidate_scores[x])

    # Greedy phase
    for num in sorted_candidates:
        is_forbidden = False
        for s_val in S:
            diff = num - s_val
            # Check if num can form an AP with two existing elements in S
            # Case 1: s_val is the middle element (a, s_val, num) => a = 2*s_val - num
            if 2 * s_val - num in S:
                is_forbidden = True
                break
            # Case 2: num is the middle element (s_val, num, c) => c = 2*num - s_val
            if 2 * num - s_val in S:
                is_forbidden = True
                break
        
        if not is_forbidden:
            S.add(num)
            S_list.append(num)

    # Local improvement phase (limited budget)
    # Try to swap elements from outside S with elements in S if it increases size.
    # This is a very basic local search, can be expanded.
    
    current_size = len(S_list)
    
    # Try adding an element from outside S that was rejected
    # and removing an element from S to maintain 3-AP-free property.
    # This is computationally more expensive.

    # A simpler local search: try to swap a few elements.
    # For simplicity, we will just try to add elements that were skipped if possible,
    # and then try to see if we can remove an element and add two others.
    
    # Let's stick to a simpler local improvement: try to add elements if they don't break 3-AP.
    # This is more like an extension of the greedy phase.
    # Re-sort candidates that are not in S
    
    remaining_candidates = sorted([x for x in range(1, n + 1) if x not in S], key=lambda x: candidate_scores.get(x, float('inf')))

    for num in remaining_candidates:
        is_forbidden = False
        for s_val in S:
            diff = num - s_val
            if 2 * s_val - num in S:
                is_forbidden = True
                break
            if 2 * num - s_val in S:
                is_forbidden = True
                break
        
        if not is_forbidden:
            S.add(num)
            S_list.append(num)
            # Re-sort S_list to keep it somewhat ordered if needed for future steps
            S_list.sort() 
    
    return S
--------------------------------------------------
{1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 69, 70, 72, 73, 78, 79, 81, 82} 20
https://ideone.com/IB2F0T
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!