utils.py

# Board positions
BOARD_POSITIONS = {
    (0, 2): 1, (0, 3): 2, (0, 4): 3,
    (1, 2): 4, (1, 3): 5, (1, 4): 6,
    (2, 0): 7, (2, 1): 8, (2, 2): 9, (2, 3): 10, (2, 4): 11, (2, 5): 12, (2, 6): 13,
    (3, 0): 14, (3, 1): 15, (3, 2): 16, (3, 3): 17, (3, 4): 18, (3, 5): 19, (3, 6): 20,
    (4, 0): 21, (4, 1): 22, (4, 2): 23, (4, 3): 24, (4, 4): 25, (4, 5): 26, (4, 6): 27,
    (5, 2): 28, (5, 3): 29, (5, 4): 30,
    (6, 2): 31, (6, 3): 32, (6, 4): 33,
}

# Reverse mapping: hole number -> (row, column)
HOLE_TO_POS = {}
for pos, hole in BOARD_POSITIONS.items():
    HOLE_TO_POS[hole] = pos

# Valid positions
VALID_POSITIONS = set(BOARD_POSITIONS.keys())

# Movement directions (orthogonal only)
DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # right, left, down, up

# Check if a hole has a peg
def has_peg(state, hole):
    return hole in state

# Check if a hole is empty
def is_empty(state, hole):
    return hole not in state

# Find all valid moves from a state
def get_valid_moves(state):
    moves = []
    for from_hole in state:
        from_pos = HOLE_TO_POS[from_hole]
        for dr, dc in DIRECTIONS:
            # Position being jumped over
            over_pos = (from_pos[0] + dr, from_pos[1] + dc)
            # Target position
            to_pos = (from_pos[0] + 2*dr, from_pos[1] + 2*dc)
            
            # Check if positions are valid
            if over_pos not in VALID_POSITIONS or to_pos not in VALID_POSITIONS:
                continue
            
            over_hole = BOARD_POSITIONS[over_pos]
            to_hole = BOARD_POSITIONS[to_pos]
            
            # Move is valid if: jumped position has peg, target is empty
            if has_peg(state, over_hole) and is_empty(state, to_hole):
                moves.append((from_hole, over_hole, to_hole))
    
    return moves

# Apply a move and return new state
def apply_move(state, move):
    from_hole, over_hole, to_hole = move
    new_pegs = set(state)
    new_pegs.remove(from_hole)  # Remove peg from starting position
    new_pegs.remove(over_hole)  # Remove jumped peg
    new_pegs.add(to_hole)       # Add peg to target
    return frozenset(new_pegs)

# Get moves in sorted order
def get_canonical_moves(state):
    moves = get_valid_moves(state)
    # Sort by (removed, from, to) order
    moves.sort(key=lambda m: (m[1], m[0], m[2]))
    return moves

# Count remaining pegs
def count_pegs(state):
    return len(state)

# Check if goal state for Version A
def is_goal_state_version_a(state):
    return count_pegs(state) == 1 and 17 in state

# Check if terminal state for Version B
def is_terminal_state_version_b(state):
    return len(get_valid_moves(state)) == 0

# Display state as ASCII board
def to_ascii_board(state):
    board = []
    for row in range(7):
        line = []
        for col in range(7):
            pos = (row, col)
            if pos in VALID_POSITIONS:
                hole = BOARD_POSITIONS[pos]
                if has_peg(state, hole):
                    line.append('x')
                else:
                    line.append('o')
            else:
                line.append(' ')
        board.append(''.join(line))
    return '\n'.join(board)

# Get initial state
def get_initial_state():
    all_holes = set(range(1, 34))
    all_holes.remove(17)  # Center is empty
    return frozenset(all_holes)

# Reconstruct path
def reconstruct_path(state, parent_dict):
    path = []
    current = state
    while current in parent_dict:
        parent, move = parent_dict[current]
        if move:
            path.append(move)
        current = parent
    path.reverse()
    return path

# Create search result
def create_search_result(state, status, nodes_expanded, peak_nodes, parent_dict=None):
    result = {
        'state': state,
        'status': status,
        'nodes_expanded': nodes_expanded,
        'peak_nodes': peak_nodes
    }
    if parent_dict is not None:
        result['parent_dict'] = parent_dict
    return result