Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
2.6 kB
2
Indexable
Never
class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

    def dfs(self, start):
        visited = set()
        self._dfs_helper(start, visited)

    def _dfs_helper(self, vertex, visited):
        visited.add(vertex)
        print(vertex, end=' ')

        if vertex in self.graph:
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    self._dfs_helper(neighbor, visited)


# Example usage
if __name__ == "__main__":
    g = Graph()
    g.add_edge('A', 'B')
    g.add_edge('A', 'C')
    g.add_edge('B', 'D')
    g.add_edge('B', 'E')
    g.add_edge('C', 'F')
    g.add_edge('C', 'G')

    print("Depth First Traversal starting from vertex 'A':")
    g.dfs('A')



water jug problem
from collections import deque

# Define the state of the jugs
class State:
    def __init__(self, jug1, jug2):
        self.jug1 = jug1
        self.jug2 = jug2

    def __eq__(self, other):
        return self.jug1 == other.jug1 and self.jug2 == other.jug2

    def __hash__(self):
        return hash((self.jug1, self.jug2))

# Define the actions possible
def actions(state, max_jug1, max_jug2):
    jug1, jug2 = state.jug1, state.jug2
    return [(max(0, jug1 - (max_jug2 - jug2)), min(max_jug2, jug2 + jug1)),
            (min(max_jug1, jug1 + jug2), max(0, jug2 - (max_jug1 - jug1))),
            (max_jug1, jug2),
            (jug1, max_jug2),
            (0, jug2),
            (jug1, 0)]

# Solve 
def water_jug(start_state, target, max_jug1, max_jug2):
    visited = set()
    queue = deque([(start_state, [])])

    while queue:
        current_state, path = queue.popleft()
        if current_state == target:
            return path + [target]
        visited.add(current_state)

        for action in actions(current_state, max_jug1, max_jug2):
            new_state = State(*action)
            if new_state not in visited:
                queue.append((new_state, path + [current_state]))
                visited.add(new_state)

    return None

# Example 
max_jug1 = 4
max_jug2 = 3
start_state = State(0, 0)
target_state = State(2, 0)

solution = water_jug(start_state, target_state, max_jug1, max_jug2)

if solution:
    print("Solution found:")
    for state in solution:
        print(f"Jug 1: {state.jug1}, Jug 2: {state.jug2}")
else:
    print("No solution found.")
Leave a Comment