🔒 Help with BFS algorithm homework (Will join voice and stream)"

[livid trench]

Need tome help using the BFS search algorithm for a waterbucket problem
Last one got locked before I could respond

[obtuse delta]

@livid trench

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[livid trench]

from collections import deque

class SearchNode:
    def __init__(self, state, actions = [] , total_cost = 0):
        self.state = state
        self.actions = actions
        self.totalCost = total_cost

def actionMoves(node, bucketCapacities, queue, visited_states):
    #fill
    count = 0
    for bucket in node.state:
        new_node = SearchNode(node.state.copy())
        new_node.actions = node.actions.copy()
        new_node.state[count] = bucketCapacities[count]
        new_node.totalCost += bucketCapacities[count]
        new_node.actions.append("Fill %1d-gallon bucket."  % (bucketCapacities[count]))
        if tuple(new_node.state) not in visited_states:
            queue.append(new_node)
        count += 1

    #empty
    count = 0
    for bucket in node.state:
        new_node = SearchNode(node.state.copy())
        new_node.actions = node.actions.copy()
        new_node.state[count] = 0
        new_node.totalCost += bucketCapacities[count]
        new_node.actions.append("Empty %1d-gallon bucket." % (bucketCapacities[count]))
        if tuple(new_node.state) not in visited_states:
            queue.append(new_node)
        count += 1

    #transfer
    output_count = 0
    for output in node.state:
        new_node = SearchNode(node.state.copy())
        new_node.actions = node.actions.copy()
        input_count = 0
        for input in node.state:
            if output_count!= input_count:
                amount = min(new_node.state[output_count], bucketCapacities[input_count] - new_node.state[input_count])
                new_node.state[input_count] += amount
                new_node.state[output_count] -= amount
                new_node.actions.append("Pour %2d-gallon bucket to %2d-gallon bucket." % (
                bucketCapacities[output_count], bucketCapacities[input_count]))
                if tuple(new_node.state) not in visited_states:
                    queue.append(new_node)
                input_count += 1
        output_count += 1

    return None


def bfs_tree_search(bucket_capacities, goal_water_amount, action_limit):
    check_node = SearchNode([0] * len(bucket_capacities))
    visited_states = set()
    queue = deque()
    queue.append(check_node)
    while len(queue) > 0:
        if tuple(check_node.state) not in visited_states:
            actionMoves(check_node, bucket_capacities, queue, visited_states)
            count = 0
            for bucket in check_node.state:
                if check_node.state[count] == goal_water_amount:
                    return check_node
                else:
                    count += 1
                    visited_states.add(tuple(check_node.state))
        print(check_node.state)
        check_node = queue.popleft()
    return None

def main():
    bucket_capacities_text = input("Enter bucket capacities separated by spaces: ")
    bucket_capacities = [int(x) for x in bucket_capacities_text.split()]

    goal_amount = int(input("Enter the goal amount of water: "))

    action_limit = int(input("Search for plans up to how many actions? "))

    solution_node = bfs_tree_search(bucket_capacities, goal_amount, action_limit)

    if solution_node:
        print(f"You can measure out exactly {goal_amount} gallons of water with the following steps:")
        actions = solution_node.actions
        for action in actions:
            print(action)
        print("Total number of actions required: ", len(solution_node.actions))
        print("Total cost of action plan: ", solution_node.totalCost)
    else:
        print(f"No solution plan found using {action_limit} or fewer actions.")


if __name__ == "__main__":
    main()

So it is the bucket problem where you have multiple seperate sized buckets and need to get a specific amount of water

[obtuse delta]

@livid trench

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.