fork download 
  1. """
  2. @file program_synthesis_search.py
  3. @brief Staged Genetic Programming Search for Register Swap Algorithm Synthesis
  4.  
  5. @version 2.4
  6. @author Grok (built by xAI)
  7. @date November 07, 2025
  8.  
  9. @details
  10. This program implements a staged genetic programming (GP) search to evolve a small
  11. program (as an Abstract Syntax Tree, AST) that swaps the values in two registers
  12. (R0 and R1) using a third scratchpad register (R2). The search uses a beam search
  13. with mutation and crossover operators, guided by a curriculum of fitness stages.
  14.  
  15. Key Features:
  16. - Lisp-style prefix notation for program representation (S-expressions).
  17. - VM interpreter for side-effectful execution (memory modifications via 'set').
  18. - Staged heuristics: First stage rewards partial correctness (one register right),
  19.   second requires full swap.
  20. - Post-evolution simplification using conservative higher-order logic pruning: recursive
  21.   rewrite rules for math identities (+/- with 0) on pure subtrees only (no side-effects or
  22.   data dependencies), progn flattening and single-child removal (preserving side-effects).
  23.   No intra-search simplification to avoid disrupting evolution; only post-search.
  24.  
  25. The evolved program is output in full Lisp syntax, suitable for direct use in a
  26. Lisp environment (with equivalents for 'set', 'get', 'progn', etc.).
  27.  
  28. Usage:
  29. python program_synthesis_search.py
  30.  
  31. @license MIT (or equivalent open-source)
  32. """
  33.  
  34. import math
  35. import heapq
  36. import copy
  37. import random
  38. from dataclasses import dataclass, field
  39. from typing import Callable, Optional, List, Tuple, Dict, Any
  40.  
  41. # Optional: For reproducibility
  42. # random.seed(42)
  43.  
  44. # ---
  45. # ## 1. The "World" (Memory)
  46. # ---
  47.  
  48. MEMORY_SIZE = 3  # R0, R1, R2 (In_0, In_1, Scratchpad)
  49.  
  50. # ---
  51. # ## 2. The "Gene Pool" and "Chromosome" (AST Node)
  52. # ---
  53.  
  54. @dataclass(frozen=True)
  55. class Gene:
  56.     """Gene definition for GP primitives."""
  57.     name: str
  58.     arity: int
  59.     complexity_cost: float
  60.     function: Callable[[List[float], Any, Any], float]
  61.  
  62. @dataclass
  63. class Node:
  64.     """AST node for program representation."""
  65.     gene: Gene
  66.     left: Optional['Node'] = None
  67.     right: Optional['Node'] = None
  68.  
  69.     def __str__(self):
  70.         if self.gene.arity == 0:
  71.             return self.gene.name
  72.         parts = [self.gene.name]
  73.         if self.left:
  74.             parts.append(str(self.left))
  75.         if self.right:
  76.             parts.append(str(self.right))
  77.         return "(" + " ".join(parts) + ")"
  78.  
  79. # ---
  80. # ## 3. The "Gene Pool" Definition (Instruction Set)
  81. # ---
  82.  
  83. def op_progn(mem: List[float], left_res: float, right_res: float) -> float:
  84.     """Sequential execution stub."""
  85.     return right_res
  86.  
  87. def op_set(mem: List[float], idx: float, val: float) -> float:
  88.     """Memory write operation."""
  89.     int_idx = int(round(idx))
  90.     if 0 <= int_idx < MEMORY_SIZE:
  91.         mem[int_idx] = val
  92.     return val
  93.  
  94. def op_get(mem: List[float], idx: float, _) -> float:
  95.     """Memory read operation."""
  96.     int_idx = int(round(idx))
  97.     if 0 <= int_idx < MEMORY_SIZE:
  98.         return mem[int_idx]
  99.     return 0.0
  100.  
  101. def op_add(mem: List[float], a: float, b: float) -> float:
  102.     return a + b
  103.  
  104. def op_sub(mem: List[float], a: float, b: float) -> float:
  105.     return a - b
  106.  
  107. def term_idx_0(mem, _, __): return 0.0
  108. def term_idx_1(mem, _, __): return 1.0
  109. def term_idx_2(mem, _, __): return 2.0
  110. def term_input_0(mem, _, __): return mem[0]
  111. def term_input_1(mem, _, __): return mem[1]
  112. def term_input_2(mem, _, __): return mem[2]
  113. def term_const_0(mem, _, __): return 0.0
  114.  
  115. GENE_POOL = [
  116.     # Control Flow
  117.     Gene("progn", 2, 0.05, op_progn),
  118.  
  119.     # Memory Operations
  120.     Gene("set", 2, 1.0, op_set),
  121.     Gene("get", 1, 0.5, op_get),
  122.  
  123.     # Math
  124.     Gene("+", 2, 1.0, op_add),
  125.     Gene("-", 2, 1.0, op_sub),
  126.  
  127.     # Terminals (Indices)
  128.     Gene("R0", 0, 0.1, term_idx_0),
  129.     Gene("R1", 0, 0.1, term_idx_1),
  130.     Gene("R2", 0, 0.1, term_idx_2),
  131.  
  132.     # Terminals (Values)
  133.     Gene("Val(R0)", 0, 0.2, term_input_0),
  134.     Gene("Val(R1)", 0, 0.2, term_input_1),
  135.     Gene("Val(R2)", 0, 0.2, term_input_2),
  136.     Gene("0.0", 0, 0.1, term_const_0),
  137. ]
  138.  
  139. TERMINAL_GENES = [g for g in GENE_POOL if g.arity == 0]
  140. NON_TERMINAL_GENES = [g for g in GENE_POOL if g.arity > 0]
  141.  
  142. # ---
  143. # ## 4. The "Interpreter" (VM) and Cost Functions
  144. # ---
  145.  
  146. def eval_tree(node: Node, memory: List[float]) -> float:
  147.     """Recursive VM for AST execution."""
  148.     try:
  149.         if node.gene.name == 'progn':
  150.             if node.left:
  151.                 eval_tree(node.left, memory)
  152.             if node.right:
  153.                 return eval_tree(node.right, memory)
  154.             return 0.0
  155.  
  156.         if node.gene.arity == 0:
  157.             return node.gene.function(memory, 0, 0)
  158.  
  159.         left_val = eval_tree(node.left, memory) if node.left else 0.0
  160.         right_val = eval_tree(node.right, memory) if node.right else 0.0
  161.  
  162.         return node.gene.function(memory, left_val, right_val)
  163.  
  164.     except (ValueError, OverflowError, IndexError, ZeroDivisionError):
  165.         return float('inf')
  166.  
  167. def get_complexity_score(node: Node) -> float:
  168.     """Recursive complexity calculation."""
  169.     if not node:
  170.         return 0.0
  171.     cost = node.gene.complexity_cost
  172.     if node.left:
  173.         cost += get_complexity_score(node.left)
  174.     if node.right:
  175.         cost += get_complexity_score(node.right)
  176.     return cost
  177.  
  178. # ---
  179. # ## 5. Tree Simplification (Higher-Order Logic Pruning)
  180. # ---
  181.  
  182. def has_side_effect_or_dependency(node: Node) -> bool:
  183.     """Check for side-effects or data dependencies in subtree."""
  184.     if not node:
  185.         return False
  186.     name = node.gene.name
  187.     if name in ['set', 'Val(R0)', 'Val(R1)', 'Val(R2)', 'get']:
  188.         return True
  189.     if name == 'progn':
  190.         return has_side_effect_or_dependency(node.left) or has_side_effect_or_dependency(node.right)
  191.     return has_side_effect_or_dependency(node.left) or has_side_effect_or_dependency(node.right)
  192.  
  193. def get_const_value(node: Node) -> Optional[float]:
  194.     """Extract constant value if subtree is pure constant, else None."""
  195.     if not node:
  196.         return None
  197.     name = node.gene.name
  198.     if name == '0.0':
  199.         return 0.0
  200.     if name in ['R0', 'R1', 'R2']:
  201.         return float(name[1])
  202.     if name in ['Val(R0)', 'Val(R1)', 'Val(R2)', 'get']:
  203.         return None
  204.     if name in ['+', '-']:
  205.         l = get_const_value(node.left)
  206.         r = get_const_value(node.right)
  207.         if l is not None and r is not None:
  208.             if name == '+':
  209.                 return l + r
  210.             return l - r
  211.     if name == 'progn':
  212.         return get_const_value(node.right)
  213.     return None
  214.  
  215. def simplify_tree(node: Node) -> Node:
  216.     """Apply higher-order logic pruning: flatten progn, fold constants, remove identities."""
  217.     if not node:
  218.         return node
  219.  
  220.     # Recurse on children
  221.     left = simplify_tree(node.left) if node.left else None
  222.     right = simplify_tree(node.right) if node.right else None
  223.  
  224.     new_node = Node(gene=node.gene, left=left, right=right)
  225.     name = new_node.gene.name
  226.  
  227.     # Flatten and reduce progn
  228.     if name == 'progn':
  229.         children = []
  230.         def flatten_progn(n: Optional[Node]):
  231.             if n and n.gene.name == 'progn':
  232.                 flatten_progn(n.left)
  233.                 flatten_progn(n.right)
  234.             elif n:
  235.                 children.append(n)
  236.  
  237.         flatten_progn(new_node)
  238.  
  239.         if not children:
  240.             return Node(gene=GENE_POOL[-1])
  241.         if len(children) == 1:
  242.             return children[0]
  243.         else:
  244.             # Binary chain rebuild
  245.             def build_chain(cs: List[Node]) -> Optional[Node]:
  246.                 if len(cs) == 1:
  247.                     return cs[0]
  248.                 mid = len(cs) // 2
  249.                 l = build_chain(cs[:mid])
  250.                 r = build_chain(cs[mid:])
  251.                 return Node(gene=GENE_POOL[0], left=l, right=r)
  252.             return build_chain(children)
  253.  
  254.     # Math identities (pure subtrees only)
  255.     if name in ['+', '-'] and not has_side_effect_or_dependency(new_node):
  256.         l_const = get_const_value(left)
  257.         r_const = get_const_value(right)
  258.         if name == '+':
  259.             if l_const == 0:
  260.                 return right
  261.             if r_const == 0:
  262.                 return left
  263.             if l_const is not None and r_const is not None:
  264.                 if l_const + r_const == 0:
  265.                     return Node(gene=GENE_POOL[-1])
  266.         elif name == '-':
  267.             if r_const == 0:
  268.                 return left
  269.             if l_const is not None and r_const is not None:
  270.                 if l_const - r_const == 0:
  271.                     return Node(gene=GENE_POOL[-1])
  272.  
  273.     # Constant folding (pure subtrees)
  274.     if not has_side_effect_or_dependency(new_node):
  275.         const_val = get_const_value(new_node)
  276.         if const_val is not None and abs(const_val) < 1e-6:
  277.             return Node(gene=GENE_POOL[-1])
  278.  
  279.     return new_node
  280.  
  281. # ---
  282. # ## 6. Staged Fitness Heuristic
  283. # ---
  284.  
  285. @dataclass
  286. class FitnessStage:
  287.     """Curriculum stage definition."""
  288.     name: str
  289.     target_error: float
  290.     heuristic_func: Callable[[Node, List[Tuple[List[float], List[float]]]], float]
  291.  
  292. def h_full_swap(program: Node, test_data: List[Tuple[List[float], List[float]]]) -> float:
  293.     """Full error on all registers."""
  294.     total_squared_error = 0
  295.     for input_list, target_list in test_data:
  296.         memory = [0.0] * MEMORY_SIZE
  297.         for i, val in enumerate(input_list):
  298.             if i < MEMORY_SIZE:
  299.                 memory[i] = val
  300.  
  301.         eval_tree(program, memory)
  302.  
  303.         for i, target_val in enumerate(target_list):
  304.             if i < MEMORY_SIZE:
  305.                 error = memory[i] - target_val
  306.                 total_squared_error += error * error
  307.  
  308.     return total_squared_error
  309.  
  310. def h_one_reg_correct(program: Node, test_data: List[Tuple[List[float], List[float]]]) -> float:
  311.     """Bonus if at least one register is correct."""
  312.     total_squared_error = 0
  313.     for input_list, target_list in test_data:
  314.         memory = [0.0] * MEMORY_SIZE
  315.         for i, val in enumerate(input_list):
  316.             if i < MEMORY_SIZE:
  317.                 memory[i] = val
  318.  
  319.         eval_tree(program, memory)
  320.  
  321.         errors = [abs(memory[i] - target_val) for i, target_val in enumerate(target_list) if i < MEMORY_SIZE]
  322.  
  323.         if any(e < 0.01 for e in errors):
  324.             total_squared_error += sum(e * e for e in errors if e >= 0.01)
  325.         else:
  326.             total_squared_error += sum(e * e for e in errors)
  327.  
  328.     return total_squared_error
  329.  
  330. # ---
  331. # ## 7. Genetic Operators
  332. # ---
  333.  
  334. def _find_nodes_by_type(node: Node, type_: str) -> List[Node]:
  335.     """Find nodes by type ('all', 'leaf', 'internal')."""
  336.     nodes = []
  337.     if not node:
  338.         return []
  339.  
  340.     is_leaf = (node.gene.arity == 0)
  341.     if type_ == 'all':
  342.         nodes.append(node)
  343.     elif type_ == 'leaf' and is_leaf:
  344.         nodes.append(node)
  345.     elif type_ == 'internal' and not is_leaf:
  346.         nodes.append(node)
  347.  
  348.     nodes.extend(_find_nodes_by_type(node.left, type_))
  349.     nodes.extend(_find_nodes_by_type(node.right, type_))
  350.     return nodes
  351.  
  352. def _generate_random_subtree(max_depth: int = 4) -> Node:
  353.     """Generate random subtree with depth limit."""
  354.     if max_depth <= 0:
  355.         return Node(gene=random.choice(TERMINAL_GENES))
  356.  
  357.     weighted_non_term = NON_TERMINAL_GENES * 3
  358.     weighted_all = weighted_non_term + TERMINAL_GENES
  359.     gene = random.choice(weighted_all)
  360.     if gene.arity == 0 or max_depth <= 0:
  361.         return Node(gene=gene)
  362.  
  363.     new_node = Node(gene=gene)
  364.     if gene.arity >= 1:
  365.         new_node.left = _generate_random_subtree(max_depth - 1)
  366.     if gene.arity == 2:
  367.         new_node.right = _generate_random_subtree(max_depth - 1)
  368.     return new_node
  369.  
  370. def _functional_replace(current: Node, target: Node, replacement: Node) -> Node:
  371.     """Replace subtree by identity."""
  372.     if current is target:
  373.         return copy.deepcopy(replacement)
  374.  
  375.     if current.gene.arity == 0:
  376.         return copy.deepcopy(current)
  377.  
  378.     new_node = Node(gene=current.gene)
  379.     if current.left:
  380.         new_node.left = _functional_replace(current.left, target, replacement)
  381.     if current.right:
  382.         new_node.right = _functional_replace(current.right, target, replacement)
  383.  
  384.     return new_node
  385.  
  386. def op_mutate_subtree(tree: Node) -> Node:
  387.     """Random subtree mutation."""
  388.     nodes = _find_nodes_by_type(tree, 'all')
  389.     if not nodes:
  390.         return tree
  391.  
  392.     node_to_replace = random.choice(nodes)
  393.     new_branch = _generate_random_subtree(max_depth=4)
  394.  
  395.     return _functional_replace(tree, node_to_replace, new_branch)
  396.  
  397. def op_crossover(tree1: Node, tree2: Node) -> Node:
  398.     """Subtree crossover."""
  399.     all_nodes1 = _find_nodes_by_type(tree1, 'all')
  400.     all_nodes2 = _find_nodes_by_type(tree2, 'all')
  401.  
  402.     if not all_nodes1 or not all_nodes2:
  403.         return tree1
  404.  
  405.     node_from_1 = random.choice(all_nodes1)
  406.     node_from_2 = random.choice(all_nodes2)
  407.  
  408.     return _functional_replace(tree1, node_from_1, node_from_2)
  409.  
  410. # ---
  411. # ## 8. The Search Engine (Staged Curriculum)
  412. # ---
  413.  
  414. @dataclass(order=True)
  415. class SearchState:
  416.     """State for beam search."""
  417.     f_cost: float
  418.     h_cost: float
  419.     g_cost: float
  420.     program: Node = field(compare=False)
  421.  
  422. def search_program(test_data: List[Tuple[List[float], List[float]]],
  423.                    stages: List[FitnessStage],
  424.                    beam_width: int,
  425.                    max_iterations_per_stage: int,
  426.                    lambda_complexity: float,
  427.                    p_mutate: float):
  428.  
  429.     pq: List[SearchState] = []
  430.  
  431.     print("--- Initializing Frontier with Terminals ---")
  432.     visited: Dict[str, float] = {}
  433.     h_func = stages[0].heuristic_func
  434.     for gene in TERMINAL_GENES:
  435.         program = Node(gene=gene)
  436.         prog_str = str(program)
  437.         g = get_complexity_score(program)
  438.         h = h_func(program, test_data)
  439.         f = (lambda_complexity * g) + h
  440.         if h == float('inf'):
  441.             continue
  442.         state = SearchState(f_cost=f, h_cost=h, g_cost=g, program=program)
  443.         heapq.heappush(pq, state)
  444.         visited[prog_str] = g
  445.         print(f"  Added: {prog_str:<8} (f={f:.2f}) [g={g:.1f}, h={h:.1f}]")
  446.  
  447.     for stage in stages:
  448.         print(f"\n\n--- Starting Stage: '{stage.name}' (Goal: h <= {stage.target_error}) ---")
  449.  
  450.         visited.clear()
  451.  
  452.         current_population = pq
  453.         pq = []
  454.         for state in current_population:
  455.             state.h_cost = stage.heuristic_func(state.program, test_data)
  456.             state.f_cost = (lambda_complexity * state.g_cost) + state.h_cost
  457.             heapq.heappush(pq, state)
  458.             visited[str(state.program)] = state.g_cost
  459.  
  460.         stage_solved = False
  461.         for i in range(max_iterations_per_stage):
  462.  
  463.             current_beam = heapq.nsmallest(beam_width, pq)
  464.             if not current_beam:
  465.                 print("Search failed: Frontier is empty.")
  466.                 return None
  467.  
  468.             best_in_beam = current_beam[0]
  469.  
  470.             print(f"\n  --- Stage '{stage.name}', Iter {i} ---")
  471.             print(f"    Best F={best_in_beam.f_cost:.2f} [g={best_in_beam.g_cost:.1f}, h={best_in_beam.h_cost:.1f}] Prog: {best_in_beam.program}")
  472.  
  473.             if best_in_beam.h_cost <= stage.target_error:
  474.                 print(f"  --- Stage '{stage.name}' SOLVED! ---")
  475.                 stage_solved = True
  476.                 pq = current_beam
  477.                 break
  478.  
  479.             next_gen_candidates: Dict[str, SearchState] = {}
  480.             for state in current_beam:
  481.                 next_gen_candidates[str(state.program)] = state
  482.  
  483.             for parent_state in current_beam:
  484.                 new_child_tree = None
  485.                 if random.random() < p_mutate:
  486.                     new_child_tree = op_mutate_subtree(parent_state.program)
  487.                 else:
  488.                     other_parent_state = random.choice(current_beam)
  489.                     new_child_tree = op_crossover(parent_state.program, other_parent_state.program)
  490.  
  491.                 prog_str = str(new_child_tree)
  492.                 g_new = get_complexity_score(new_child_tree)
  493.  
  494.                 if prog_str in visited and visited[prog_str] <= g_new:
  495.                     continue
  496.  
  497.                 h_new = stage.heuristic_func(new_child_tree, test_data)
  498.                 if h_new == float('inf'):
  499.                     continue
  500.  
  501.                 f_new = (lambda_complexity * g_new) + h_new
  502.                 visited[prog_str] = g_new
  503.  
  504.                 if prog_str not in next_gen_candidates or f_new < next_gen_candidates[prog_str].f_cost:
  505.                     next_gen_candidates[prog_str] = SearchState(f_new, h_new, g_new, new_child_tree)
  506.  
  507.             pq = list(next_gen_candidates.values())
  508.             heapq.heapify(pq)
  509.  
  510.         if not stage_solved:
  511.             print(f"Search failed: Max iterations reached for stage '{stage.name}'.")
  512.             return None
  513.  
  514.     print("\n--- All Stages Solved! ---")
  515.     final_solution = heapq.nsmallest(1, pq)[0]
  516.     return final_solution.program
  517.  
  518. # ---
  519. # ## 9. Main Execution
  520. # ---
  521.  
  522. if __name__ == "__main__":
  523.  
  524.     print("--- Starting Staged Algorithmic Search ---")
  525.     print(f"Goal: Find an algorithm to swap R0 and R1 (Memory Size={MEMORY_SIZE})")
  526.  
  527.     TEST_DATA = [
  528.         ([5.0, 10.0], [10.0, 5.0]),
  529.         ([1.0, 2.0], [2.0, 1.0]),
  530.         ([-5.0, 3.0], [3.0, -5.0]),
  531.     ]
  532.  
  533.     STAGES = [
  534.         FitnessStage(
  535.             name="Get One Register Right",
  536.             target_error=90.01,
  537.             heuristic_func=h_one_reg_correct
  538.         ),
  539.         FitnessStage(
  540.             name="Get Both Registers Right",
  541.             target_error=0.01,
  542.             heuristic_func=h_full_swap
  543.         )
  544.     ]
  545.  
  546.     LAMBDA_COMPLEXITY = 1.0  # Penalize bloat more
  547.     BEAM_WIDTH = 200
  548.     MAX_ITERATIONS_PER_STAGE = 200
  549.     P_MUTATE = 1.0
  550.  
  551.     solution = search_program(
  552.         test_data=TEST_DATA,
  553.         stages=STAGES,
  554.         beam_width=BEAM_WIDTH,
  555.         max_iterations_per_stage=MAX_ITERATIONS_PER_STAGE,
  556.         lambda_complexity=LAMBDA_COMPLEXITY,
  557.         p_mutate=P_MUTATE
  558.     )
  559.  
  560.     if solution:
  561.         # Post-search simplification
  562.         simplified_solution = simplify_tree(solution)
  563.  
  564.         print(f"\nRaw Final Program: {solution}")
  565.         print(f"Raw Complexity (g): {get_complexity_score(solution):.1f}")
  566.  
  567.         print(f"\nSimplified Final Program (Lisp Syntax): {simplified_solution}")
  568.         print(f"Simplified Complexity (g): {get_complexity_score(simplified_solution):.1f}")
  569.         print(f"Final Fitness Error (h): {h_full_swap(simplified_solution, TEST_DATA):.4f}")
  570.  
  571.         print("\n--- Test Results ---")
  572.         for in_list, target_list in TEST_DATA:
  573.             mem = [0.0] * MEMORY_SIZE
  574.             for i, val in enumerate(in_list):
  575.                 if i < MEMORY_SIZE:
  576.                     mem[i] = val
  577.  
  578.             print(f"Input:    {in_list}")
  579.             eval_tree(simplified_solution, mem)
  580.             print(f"Output:   {[round(m, 4) for m in mem[:len(target_list)]]}")
  581.             print(f"Target:   {target_list}\n")# your code goes here
Success #stdin #stdout 4.31s 29304KB
comments (?)
stdin 
Standard input is empty
stdout 
--- Starting Staged Algorithmic Search ---
Goal: Find an algorithm to swap R0 and R1 (Memory Size=3)
--- Initializing Frontier with Terminals ---
  Added: R0       (f=180.10) [g=0.1, h=180.0]
  Added: R1       (f=180.10) [g=0.1, h=180.0]
  Added: R2       (f=180.10) [g=0.1, h=180.0]
  Added: Val(R0)  (f=180.20) [g=0.2, h=180.0]
  Added: Val(R1)  (f=180.20) [g=0.2, h=180.0]
  Added: Val(R2)  (f=180.20) [g=0.2, h=180.0]
  Added: 0.0      (f=180.10) [g=0.1, h=180.0]


--- Starting Stage: 'Get One Register Right' (Goal: h <= 90.01) ---

  --- Stage 'Get One Register Right', Iter 0 ---
    Best F=180.10 [g=0.1, h=180.0] Prog: R0

  --- Stage 'Get One Register Right', Iter 1 ---
    Best F=180.10 [g=0.1, h=180.0] Prog: R2

  --- Stage 'Get One Register Right', Iter 2 ---
    Best F=145.70 [g=4.7, h=141.0] Prog: (- (+ Val(R1) (+ R1 (set R1 Val(R2)))) 0.0)

  --- Stage 'Get One Register Right', Iter 3 ---
    Best F=98.00 [g=7.0, h=91.0] Prog: (get (set (+ Val(R2) (set Val(R1) (get R1))) (set (+ 0.0 Val(R2)) Val(R1))))

  --- Stage 'Get One Register Right', Iter 4 ---
    Best F=95.05 [g=5.0, h=90.0] Prog: (+ (- (- Val(R0) (progn Val(R1) 0.0)) Val(R1)) (set 0.0 Val(R1)))
  --- Stage 'Get One Register Right' SOLVED! ---


--- Starting Stage: 'Get Both Registers Right' (Goal: h <= 0.01) ---

  --- Stage 'Get Both Registers Right', Iter 0 ---
    Best F=95.05 [g=5.0, h=90.0] Prog: (+ (- (- Val(R0) (progn Val(R1) 0.0)) Val(R1)) (set 0.0 Val(R1)))

  --- Stage 'Get Both Registers Right', Iter 1 ---
    Best F=95.05 [g=5.0, h=90.0] Prog: (+ (- (- Val(R0) (progn Val(R1) 0.0)) Val(R1)) (set 0.0 Val(R1)))

  --- Stage 'Get Both Registers Right', Iter 2 ---
    Best F=95.05 [g=5.0, h=90.0] Prog: (+ (- (- Val(R0) (progn Val(R1) 0.0)) Val(R1)) (set 0.0 Val(R1)))

  --- Stage 'Get Both Registers Right', Iter 3 ---
    Best F=73.85 [g=14.8, h=59.0] Prog: (- (set Val(R0) (progn (progn (set (- (get R2) (get R2)) Val(R1)) Val(R1)) (+ (- Val(R2) Val(R2)) (+ 0.0 Val(R0))))) (progn Val(R2) (- (set (progn R2 R1) R2) (progn (+ 0.0 Val(R0)) (- 0.0 Val(R2))))))

  --- Stage 'Get Both Registers Right', Iter 4 ---
    Best F=73.75 [g=14.8, h=59.0] Prog: (- (set Val(R0) (progn (progn (set (- (get R2) (get R2)) Val(R1)) Val(R1)) (+ (- Val(R2) Val(R2)) (+ 0.0 Val(R0))))) (progn Val(R2) (- (set (progn R2 R1) R2) (progn (+ 0.0 R1) (- 0.0 Val(R2))))))

  --- Stage 'Get Both Registers Right', Iter 5 ---
    Best F=56.65 [g=23.6, h=33.0] Prog: (- (set (get R2) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) R2)) Val(R1)) Val(R2))) (progn R2 R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 6 ---
    Best F=56.65 [g=23.6, h=33.0] Prog: (- (set (get R2) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) R2)) Val(R1)) Val(R2))) (progn R2 R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 7 ---
    Best F=56.65 [g=23.6, h=33.0] Prog: (- (set (get R2) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) R2)) Val(R1)) Val(R2))) (progn R2 R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 8 ---
    Best F=56.65 [g=23.6, h=33.0] Prog: (- (set (get R2) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) R2)) Val(R1)) Val(R2))) (progn R2 R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 9 ---
    Best F=56.65 [g=23.6, h=33.0] Prog: (- (set (get R2) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) R2)) Val(R1)) Val(R2))) (progn R2 R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 10 ---
    Best F=56.65 [g=23.6, h=33.0] Prog: (- (set (get R2) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) R2)) Val(R1)) Val(R2))) (progn R2 R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 11 ---
    Best F=56.65 [g=23.6, h=33.0] Prog: (- (set (get R2) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) R2)) Val(R1)) Val(R2))) (progn R2 R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 12 ---
    Best F=56.65 [g=23.6, h=33.0] Prog: (- (set (get R2) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) R2)) Val(R1)) Val(R2))) (progn R2 R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 13 ---
    Best F=56.65 [g=23.6, h=33.0] Prog: (- (set (get R2) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) R2)) Val(R1)) Val(R2))) (progn R2 R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 14 ---
    Best F=55.45 [g=42.5, h=13.0] Prog: (- (set (get R2) (set R2 (set Val(R0) (+ (get R2) R2)))) (set (+ (get R0) (progn R2 R1)) (set (+ R0 (- (set (- R1 (set Val(R1) Val(R0))) (get R2)) R1)) (- (progn (+ (get R2) (+ (set R0 (progn (- (set (- Val(R2) Val(R0)) (- Val(R0) Val(R1))) (set Val(R1) (+ (get (progn Val(R1) R0)) (- (+ R2 0.0) (set R2 (set (- (progn Val(R1) R1) (set R2 R2)) (+ (progn R1 Val(R2)) (+ R0 R2)))))))) Val(R1))) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 15 ---
    Best F=55.45 [g=42.5, h=13.0] Prog: (- (set (get R2) (set R2 (set Val(R0) (+ (get R2) R2)))) (set (+ (get R0) (progn R2 R1)) (set (+ R0 (- (set (- R1 (set Val(R1) Val(R0))) (get R2)) R1)) (- (progn (+ (get R2) (+ (set R0 (progn (- (set (- Val(R2) Val(R0)) (- Val(R0) Val(R1))) (set Val(R1) (+ (get (progn Val(R1) R0)) (- (+ R2 0.0) (set R2 (set (- (progn Val(R1) R1) (set R2 R2)) (+ (progn R1 Val(R2)) (+ R0 R2)))))))) Val(R1))) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 16 ---
    Best F=54.95 [g=42.0, h=13.0] Prog: (- (set (get R2) (set R2 (set Val(R0) (+ (get R2) R2)))) (set (+ (get R0) (progn R2 R1)) (set (+ R0 (- (set (- R1 (set Val(R1) Val(R0))) (get R2)) R1)) (- (progn (+ 0.0 (+ (set R0 (progn (- (set (- Val(R2) Val(R0)) (- Val(R0) Val(R1))) (set Val(R1) (+ (get (progn Val(R1) R0)) (- (+ R2 0.0) (set R2 (set (- (progn Val(R1) R1) (set R2 R2)) (+ (progn R1 Val(R2)) (+ R0 R2)))))))) Val(R1))) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 17 ---
    Best F=54.95 [g=42.0, h=13.0] Prog: (- (set (get R2) (set R2 (set Val(R0) (+ (get R2) R2)))) (set (+ (get R0) (progn R2 R1)) (set (+ R0 (- (set (- R1 (set Val(R1) Val(R0))) (get R2)) R1)) (- (progn (+ 0.0 (+ (set R0 (progn (- (set (- Val(R2) Val(R0)) (- Val(R0) Val(R1))) (set Val(R1) (+ (get (progn Val(R1) R0)) (- (+ R2 0.0) (set R2 (set (- (progn Val(R1) R1) (set R2 R2)) (+ (progn R1 Val(R2)) (+ R0 R2)))))))) Val(R1))) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 18 ---
    Best F=54.60 [g=21.6, h=33.0] Prog: (- (set (get R2) (set R2 (set Val(R0) R2))) (set (+ 0.0 (progn Val(R2) R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (progn (get (get (get (progn (+ Val(R2) R0) Val(R1))))) Val(R0)))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 19 ---
    Best F=54.55 [g=41.6, h=13.0] Prog: (- (set (get R2) (set R2 (set Val(R0) (+ (get R2) R2)))) (set (+ (get R0) (progn R2 R1)) (set (+ R0 (- (set (- R1 (set Val(R1) Val(R0))) (get R2)) R1)) (- (progn (+ 0.0 (+ (set R0 (progn (- (set (- Val(R2) Val(R0)) (- Val(R0) Val(R1))) (set Val(R1) (+ (get (progn Val(R1) R0)) (- (+ R2 0.0) (set R2 (set (- (progn Val(R1) R1) (set R2 R2)) (+ (progn R1 Val(R2)) (+ R0 R2)))))))) Val(R1))) Val(R0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 20 ---
    Best F=52.05 [g=43.1, h=9.0] Prog: (- (set (get R2) (set R2 (set Val(R0) (+ (get R2) R2)))) (set (+ (get R0) (progn R2 R1)) (set (+ R0 (- (set (- R1 (set Val(R1) Val(R0))) (get R2)) R1)) (- (progn (+ (get R2) (+ (set R0 (progn (- (get (+ (get (- R0 R1)) (get (get Val(R1))))) (set Val(R1) (+ (get (progn Val(R1) R0)) (- (+ R2 0.0) (set R2 (set (- (progn Val(R1) R1) (set R2 R2)) (+ (progn R1 Val(R2)) (+ R0 R2)))))))) Val(R1))) (get 0.0))) (set R2 (- Val(R0) (progn Val(R0) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 21 ---
    Best F=37.05 [g=35.0, h=2.0] Prog: (- (set (+ (progn (progn Val(R2) (progn 0.0 R0)) 0.0) (progn R1 (get Val(R2)))) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) (- (- (progn R2 Val(R1)) Val(R2)) (get 0.0)))) Val(R1)) Val(R2))) (progn Val(R2) R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (progn (get (get (get (progn (+ Val(R2) R0) Val(R1))))) Val(R0)))) (set R2 (- Val(R0) (progn (progn (- R0 (set Val(R0) (set Val(R0) 0.0))) Val(R1)) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 22 ---
    Best F=37.05 [g=35.0, h=2.0] Prog: (- (set (+ (progn (progn Val(R2) (progn 0.0 R0)) 0.0) (progn R1 (get Val(R2)))) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) (- (- (progn R2 Val(R1)) Val(R2)) (get 0.0)))) Val(R1)) Val(R2))) (progn Val(R2) R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (progn (get (get (get (progn (+ Val(R2) R0) Val(R1))))) Val(R0)))) (set R2 (- Val(R0) (progn (progn (- R0 (set Val(R0) (set Val(R0) 0.0))) Val(R1)) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 23 ---
    Best F=37.05 [g=35.0, h=2.0] Prog: (- (set (+ (progn (progn Val(R2) (progn 0.0 R0)) 0.0) (progn R1 (get Val(R2)))) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) (- (- (progn R2 Val(R1)) Val(R2)) (get 0.0)))) Val(R1)) Val(R2))) (progn Val(R2) R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (progn (get (get (get (progn (+ Val(R2) R0) Val(R1))))) Val(R0)))) (set R2 (- Val(R0) (progn (progn (- R0 (set Val(R0) (set Val(R0) 0.0))) Val(R1)) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 24 ---
    Best F=37.05 [g=35.0, h=2.0] Prog: (- (set (+ (progn (progn Val(R2) (progn 0.0 R0)) 0.0) (progn R1 (get Val(R2)))) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) (- (- (progn R2 Val(R1)) Val(R2)) (get 0.0)))) Val(R1)) Val(R2))) (progn Val(R2) R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (progn (get (get (get (progn (+ Val(R2) R0) Val(R1))))) Val(R0)))) (set R2 (- Val(R0) (progn (progn (- R0 (set Val(R0) (set Val(R0) 0.0))) Val(R1)) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 25 ---
    Best F=37.05 [g=35.0, h=2.0] Prog: (- (set (+ (progn (progn Val(R2) (progn 0.0 R0)) 0.0) (progn R1 (get Val(R2)))) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) (- (- (progn R2 Val(R1)) Val(R2)) (get 0.0)))) Val(R1)) Val(R2))) (progn Val(R2) R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (progn (get (get (get (progn (+ Val(R2) R0) Val(R1))))) Val(R0)))) (set R2 (- Val(R0) (progn (progn (- R0 (set Val(R0) (set Val(R0) 0.0))) Val(R1)) Val(R2))))) R1))))

  --- Stage 'Get Both Registers Right', Iter 26 ---
    Best F=34.95 [g=35.0, h=0.0] Prog: (- (set (+ (progn (progn Val(R2) (progn 0.0 R0)) 0.0) (progn R1 (get Val(R2)))) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) (- (- (progn R2 Val(R1)) R1) (get 0.0)))) Val(R1)) Val(R2))) (progn Val(R2) R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (progn (get (get (get (progn (+ Val(R2) R0) Val(R1))))) Val(R0)))) (set R2 (- Val(R0) (progn (progn (- R0 (set Val(R0) (set Val(R0) 0.0))) Val(R1)) Val(R2))))) R1))))
  --- Stage 'Get Both Registers Right' SOLVED! ---

--- All Stages Solved! ---

Raw Final Program: (- (set (+ (progn (progn Val(R2) (progn 0.0 R0)) 0.0) (progn R1 (get Val(R2)))) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) (- (- (progn R2 Val(R1)) R1) (get 0.0)))) Val(R1)) Val(R2))) (progn Val(R2) R1)) (set (+ R0 Val(R0)) (- (progn (+ (progn (- R0 R1) R2) (+ (set R0 Val(R1)) (progn (get (get (get (progn (+ Val(R2) R0) Val(R1))))) Val(R0)))) (set R2 (- Val(R0) (progn (progn (- R0 (set Val(R0) (set Val(R0) 0.0))) Val(R1)) Val(R2))))) R1))))
Raw Complexity (g): 35.0

Simplified Final Program (Lisp Syntax): (- (set (+ (progn (progn Val(R2) 0.0) (progn 0.0 0.0)) (progn R1 (get Val(R2)))) (set R2 (set Val(R0) R2))) (set (+ (get (+ (progn (- (get Val(R2)) (set Val(R2) (- (- (progn R2 Val(R1)) R1) (get 0.0)))) Val(R1)) Val(R2))) (progn Val(R2) R1)) (set (+ 0.0 Val(R0)) (- (progn (+ (progn (- 0.0 R1) R2) (+ (set 0.0 Val(R1)) (progn (get (get (get (progn (+ Val(R2) 0.0) Val(R1))))) Val(R0)))) (set R2 (- Val(R0) (progn (- 0.0 (set Val(R0) (set Val(R0) 0.0))) (progn Val(R1) Val(R2)))))) R1))))
Simplified Complexity (g): 35.0
Final Fitness Error (h): 0.0000

--- Test Results ---
Input:    [5.0, 10.0]
Output:   [10.0, 5.0]
Target:   [10.0, 5.0]

Input:    [1.0, 2.0]
Output:   [2.0, 1.0]
Target:   [2.0, 1.0]

Input:    [-5.0, 3.0]
Output:   [3.0, -5.0]
Target:   [3.0, -5.0]
https://ideone.com/XWuhoE
language:
Python 3 (python  3.12)
created:
1 day 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!