fork download 
  1. # your code goes here
  2. print("import numpy as np\n\ndef heuristic(n, rng=None):\n    \"\"\"\n    Constructs a large Salem-Spencer set, a subset of {1, ..., n}\n    with no three-term arithmetic progressions.\n    \"\"\"\n    if n <= 2:\n        return list(range(1, n + 1))\n\n    local_rng = np.random.default_rng(rng)\n\n    def _is_safe_to_add(x, S_set, is_in_S_arr):\n        \"\"\"\n        Checks if adding element x to the 3-AP-free set S_set is safe.\n        A move is safe if S_set U {x} remains 3-AP-free.\n        The check is optimized assuming S_set is already 3-AP-free.\n        \"\"\"\n        # Case 1: x is the middle term (s1, x, s2).\n        for s1 in S_set:\n            if s1 >= x:\n                continue\n            s2 = 2 * x - s1\n            if 1 <= s2 <= n and is_in_S_arr[s2]:\n                return False\n\n        # Case 2: x is an endpoint (s1, s2, x) or (x, s2, s1).\n        for s1 in S_set:\n            if (s1 + x) % 2 == 0:\n                s2 = (s1 + x) // 2\n                if is_in_S_arr[s2]:\n                    return False\n        return True\n\n    memo_ternary_score = {}\n    def _get_ternary_score(k):\n        \"\"\"\n        Calculates a score for a number based on its ternary representation.\n        Numbers with fewer '2's in base 3 get a lower (better) score.\n        This is inspired by Behrend's construction. We use k-1 for a more\n        natural mapping from {1..n} to {0..n-1}.\n        \"\"\"\n        if k in memo_ternary_score:\n            return memo_ternary_score[k]\n        \n        val = k - 1\n        if val == 0:\n            return 0\n        \n        score = 0\n        temp_val = val\n        while temp_val > 0:\n            if temp_val % 3 == 2:\n                score += 1\n            temp_val //= 3\n        \n        memo_ternary_score[k] = score\n        return score\n\n    # --- Phase 1: Scored Greedy Construction ---\n    scores = np.array([_get_ternary_score(i) for i in range(1, n + 1)])\n    random_tiebreak = local_rng.random(n)\n    \n    candidates_with_scores = sorted(\n        zip(scores, random_tiebreak, range(1, n + 1))\n    )\n    \n    is_in_S_best = np.zeros(n + 1, dtype=bool)\n    S_best = set()\n\n    for score, _, x in candidates_with_scores:\n        if _is_safe_to_add(x, S_best, is_in_S_best):\n            S_best.add(x)\n            is_in_S_best[x] = True\n    \n    # --- Phase 2: Iterated Greedy Search (Destroy & Rebuild) ---\n    max_attempts = 200 # Fixed number of attempts for predictable performance\n    destruction_fraction = 0.2 # A different parameter setting\n\n    for _ in range(max_attempts):\n        if len(S_best) < 3:\n            break\n\n        S_current = S_best.copy()\n        is_in_S_current = is_in_S_best.copy()\n        \n        # a) Destroy: Remove a random subset from the current best solution\n        d_size = max(1, int(len(S_current) * destruction_fraction))\n        elements_to_remove = local_rng.choice(\n            list(S_current), size=d_size, replace=False\n        )\n        \n        for x in elements_to_remove:\n            S_current.remove(x)\n            is_in_S_current[x] = False\n\n        # b) Rebuild: Greedily add from a list of newly unblocked candidates\n        potential_adds = set(elements_to_remove)\n        for s_rem in elements_to_remove:\n            for s_other in S_current:\n                # AP: s_other, s_rem, p => p = 2*s_rem - s_other\n                p1 = 2 * s_rem - s_other\n                if 1 <= p1 <= n: potential_adds.add(p1)\n                \n                # AP: p, s_other, s_rem => p = 2*s_other - s_rem\n                p2 = 2 * s_other - s_rem\n                if 1 <= p2 <= n: potential_adds.add(p2)\n                \n                # AP: s_other, p, s_rem => p = (s_other + s_rem)/2\n                if (s_other + s_rem) % 2 == 0:\n                    p3 = (s_other + s_rem) // 2\n                    if 1 <= p3 <= n: potential_adds.add(p3)\n\n        potential_adds.difference_update(S_current)\n        rebuild_candidates = list(potential_adds)\n        local_rng.shuffle(rebuild_candidates)\n\n        for p in rebuild_candidates:\n            if _is_safe_to_add(p, S_current, is_in_S_current):\n                S_current.add(p)\n                is_in_S_current[p] = True\n        \n        # c) Acceptance Criterion: Only accept strictly larger solutions\n        if len(S_current) > len(S_best):\n            S_best = S_current\n            is_in_S_best = is_in_S_current\n\n    S = sorted(list(S_best))\n    return S")
Success #stdin #stdout 0.08s 14224KB
comments (?)
stdin 
Standard input is empty
stdout 
import numpy as np

def heuristic(n, rng=None):
    """
    Constructs a large Salem-Spencer set, a subset of {1, ..., n}
    with no three-term arithmetic progressions.
    """
    if n <= 2:
        return list(range(1, n + 1))

    local_rng = np.random.default_rng(rng)

    def _is_safe_to_add(x, S_set, is_in_S_arr):
        """
        Checks if adding element x to the 3-AP-free set S_set is safe.
        A move is safe if S_set U {x} remains 3-AP-free.
        The check is optimized assuming S_set is already 3-AP-free.
        """
        # Case 1: x is the middle term (s1, x, s2).
        for s1 in S_set:
            if s1 >= x:
                continue
            s2 = 2 * x - s1
            if 1 <= s2 <= n and is_in_S_arr[s2]:
                return False

        # Case 2: x is an endpoint (s1, s2, x) or (x, s2, s1).
        for s1 in S_set:
            if (s1 + x) % 2 == 0:
                s2 = (s1 + x) // 2
                if is_in_S_arr[s2]:
                    return False
        return True

    memo_ternary_score = {}
    def _get_ternary_score(k):
        """
        Calculates a score for a number based on its ternary representation.
        Numbers with fewer '2's in base 3 get a lower (better) score.
        This is inspired by Behrend's construction. We use k-1 for a more
        natural mapping from {1..n} to {0..n-1}.
        """
        if k in memo_ternary_score:
            return memo_ternary_score[k]
        
        val = k - 1
        if val == 0:
            return 0
        
        score = 0
        temp_val = val
        while temp_val > 0:
            if temp_val % 3 == 2:
                score += 1
            temp_val //= 3
        
        memo_ternary_score[k] = score
        return score

    # --- Phase 1: Scored Greedy Construction ---
    scores = np.array([_get_ternary_score(i) for i in range(1, n + 1)])
    random_tiebreak = local_rng.random(n)
    
    candidates_with_scores = sorted(
        zip(scores, random_tiebreak, range(1, n + 1))
    )
    
    is_in_S_best = np.zeros(n + 1, dtype=bool)
    S_best = set()

    for score, _, x in candidates_with_scores:
        if _is_safe_to_add(x, S_best, is_in_S_best):
            S_best.add(x)
            is_in_S_best[x] = True
    
    # --- Phase 2: Iterated Greedy Search (Destroy & Rebuild) ---
    max_attempts = 200 # Fixed number of attempts for predictable performance
    destruction_fraction = 0.2 # A different parameter setting

    for _ in range(max_attempts):
        if len(S_best) < 3:
            break

        S_current = S_best.copy()
        is_in_S_current = is_in_S_best.copy()
        
        # a) Destroy: Remove a random subset from the current best solution
        d_size = max(1, int(len(S_current) * destruction_fraction))
        elements_to_remove = local_rng.choice(
            list(S_current), size=d_size, replace=False
        )
        
        for x in elements_to_remove:
            S_current.remove(x)
            is_in_S_current[x] = False

        # b) Rebuild: Greedily add from a list of newly unblocked candidates
        potential_adds = set(elements_to_remove)
        for s_rem in elements_to_remove:
            for s_other in S_current:
                # AP: s_other, s_rem, p => p = 2*s_rem - s_other
                p1 = 2 * s_rem - s_other
                if 1 <= p1 <= n: potential_adds.add(p1)
                
                # AP: p, s_other, s_rem => p = 2*s_other - s_rem
                p2 = 2 * s_other - s_rem
                if 1 <= p2 <= n: potential_adds.add(p2)
                
                # AP: s_other, p, s_rem => p = (s_other + s_rem)/2
                if (s_other + s_rem) % 2 == 0:
                    p3 = (s_other + s_rem) // 2
                    if 1 <= p3 <= n: potential_adds.add(p3)

        potential_adds.difference_update(S_current)
        rebuild_candidates = list(potential_adds)
        local_rng.shuffle(rebuild_candidates)

        for p in rebuild_candidates:
            if _is_safe_to_add(p, S_current, is_in_S_current):
                S_current.add(p)
                is_in_S_current[p] = True
        
        # c) Acceptance Criterion: Only accept strictly larger solutions
        if len(S_current) > len(S_best):
            S_best = S_current
            is_in_S_best = is_in_S_current

    S = sorted(list(S_best))
    return S
https://ideone.com/xD7VfY
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!