Hill climbing (steepest ascent) implementation in Python

hill_climbing.py

# Simple hill-climbing algorithm using the steepest-ascent variant
def perform_step(current: list, goal: list) -> (list, int):
    # Keep track of the best candidate so far (steepest-ascent)
    successor = current
    successor_weight = -1

    for i in range(0, len(current) - 1):
        # Generate a new state and calculate the weight
        candidate = swapped(current, i, i + 1)
        candidate_weight = calculate_weight(candidate, goal)

        # Compare with current best candidate
        if candidate_weight > successor_weight:
            successor = candidate
            successor_weight = candidate_weight

    return successor, successor_weight


# Calculate the weight of a state given the goal
def calculate_weight(state: list, goal: list) -> int:
    weight = 0

    for i in range(len(state)):
        block = state[i]

        # Find where we want the block to be
        goal_index = goal.index(block)

        # The block should be contained in the goal state
        assert goal_index >= 0

        # Find the block it should be above (unless it is at the bottom of the stack)
        should_be_above = None if goal_index == 0 else goal[goal_index - 1]

        # Calculate weight operator
        is_above_correct = i >= 0 if should_be_above is None else state.index(should_be_above) <= i
        is_incorrect_position = i != goal_index

        if is_above_correct:
            weight += 1

        if is_incorrect_position:
            weight -= 1

    return weight


# A simple function to generate a new list with two elements swapped
def swapped(state: list, a: int, b: int) -> list:
    new_list = []

    for i in range(len(state)):
        if i == a:
            new_list.insert(i, state[b])
        elif i == b:
            new_list.insert(i, state[a])
        else:
            new_list.insert(i, state[i])

    return new_list


if __name__ == '__main__':
    # Set up the simulation
    initial_state = ['B', 'C', 'D', 'E', 'F', 'G', 'H', 'A']
    goal_state = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']

    current_state = initial_state

    # Run until a solution is found
    current_step = 1
    while current_state != goal_state:
        # Compute the next state
        next_state, step_weight = perform_step(current_state, goal_state)

        # Common pitfalls not avoided by this implementation
        if next_state == current_state:
            print("Infinite loop detected (might be local maximum or plateau)")
            break

        # Advance the simulation
        current_state = next_state

        # Pretty logging
        print(f"Step {current_step}: {current_state}, weight: {step_weight}")
        current_step += 1

    # Announce the result
    print("Finished execution")
    print(f"Solution found: {current_state == goal_state}")
    print(f"Final state: {current_state}")