##########ci-dessous: tache 2##################### def find_valid_start(gas, cost): print("Gas: ", gas) print("Cost: ", cost) n = len(gas) #ECRIVEZ VOTRE CODE ICI return 0 #<--- il faut retourner la bonne indice ##########ci-dessus: tache 2##################### ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## import random import turtle import math import time import tkinter def generate_input(T): n = int(T/3.0) cuts = sorted(random.choices(range(T+1), k=n-1)) + [T] stations = [cuts[0]] stations.extend(cuts[i+1] - cuts[i] for i in range(n-1)) cuts = sorted(random.choices(range(T+1), k=n-1)) + [T] roads = [cuts[0]] roads.extend(cuts[i+1] - cuts[i] for i in range(n-1)) A = [] for i in range(n): A.append(["station", stations[i]]) A.append(["road", roads[i]]) return A def create_button(button_state="GO"): button = turtle.Turtle() button.hideturtle() button.speed(0) button.penup() button.goto(350, 350) button.pendown() # Change button color based on state if button_state == "GO": button.fillcolor("green") else: button.fillcolor("red") button.begin_fill() for _ in range(2): button.forward(100) button.right(90) button.forward(50) button.right(90) button.end_fill() button.penup() button.goto(400, 310) button.color("white") button.write(button_state, align="center", font=("Arial", 20, "bold")) return (350, 350, 450, 300) # (x1, y1, x2, y2) def visualize_solution(A): """Visualize the gas stations puzzle solution using turtle graphics""" screen = turtle.Screen() screen.title("Gas Stations Puzzle") screen.bgcolor("lightgray") screen.setup(width=1000, height=800) screen.tracer(0) circle_turtle = turtle.Turtle() circle_turtle.hideturtle() circle_turtle.speed(0) car_turtle = turtle.Turtle() car_turtle.shape("circle") car_turtle.color("red") car_turtle.shapesize(1.5, 1.5) car_turtle.penup() center_x, center_y = 0, 0 radius = 300 n = len(A) // 2 # Number of stations (and roads) station_positions = [] station_angles = [] for i in range(n): angle = 2 * math.pi * i / n - math.pi/2 # Start from top x = center_x + radius * math.cos(angle) y = center_y + radius * math.sin(angle) station_positions.append((x, y, angle)) station_angles.append(angle) # Draw the circular track circle_turtle.penup() circle_turtle.goto(center_x, center_y - radius) circle_turtle.setheading(0) circle_turtle.pendown() circle_turtle.pensize(3) circle_turtle.circle(radius) # Draw stations with gas values for i in range(n): # Draw station x, y, angle = station_positions[i] # Station circle circle_turtle.penup() circle_turtle.goto(x, y - 15) circle_turtle.setheading(0) circle_turtle.pendown() circle_turtle.fillcolor("lightgreen") circle_turtle.begin_fill() circle_turtle.circle(15) circle_turtle.end_fill() # Station number circle_turtle.penup() circle_turtle.goto(center_x + radius * math.cos(angle), center_y + radius * math.sin(angle)-10) circle_turtle.pendown() circle_turtle.write(f"S{i}", align="center", font=("Arial", 10, "bold")) # Gas amount circle_turtle.penup() circle_turtle.goto(center_x + 0.90*radius * math.cos(angle), center_y + 0.90*radius * math.sin(angle)-10) circle_turtle.pendown() circle_turtle.color("blue") circle_turtle.write(f"{A[2*i][1]}", align="center", font=("Arial", 14)) circle_turtle.color("black") # Draw roads with lengths (simpler, just text near the track) for i in range(n): # Position road halfway between stations road_angle = station_angles[i] + math.pi / n # Road position on the circle road_radius = radius * 0.92 road_x = center_x + road_radius * math.cos(road_angle) road_y = center_y + road_radius * math.sin(road_angle) - 10 road_cost = A[2*i+1][1] # Draw road label circle_turtle.penup() circle_turtle.goto(road_x, road_y) circle_turtle.color("gray") circle_turtle.write(f"{road_cost}", align="center", font=("Arial", 14, "bold")) circle_turtle.color("black") screen.update() screen.tracer(1) # Create a class to hold button state (to avoid nonlocal issues) class ButtonState: def __init__(self): self.state = "GO" self.animation_started = False self.button_area = None button_state = ButtonState() # Create GO button button_state.button_area = create_button(button_state.state) def on_click(x, y): """Handle mouse clicks""" # Check if GO button was clicked button_x1, button_y1, button_x2, button_y2 = button_state.button_area if (button_x1 <= x <= button_x2) and (button_y2 <= y <= button_y1): if button_state.state == "GO" and not button_state.animation_started: button_state.animation_started = True solution_index = 2 * find_valid_start( [ A[i][1] for i in range(0, len(A), 2) ], [ A[i][1] for i in range(1, len(A), 2) ] ) print("returned: ", solution_index//2) if solution_index <0 or solution_index >= len(A) or solution_index %2 != 0: print("Error! Invalid starting index.") turtle.bye() return print("Starting station: ", solution_index // 2) # Show solution info circle_turtle.goto(0, -360) circle_turtle.color("black") sol_station = solution_index // 2 circle_turtle.write(f"Start at Station {sol_station}",align="center", font=("Arial", 14, "bold")) # Clear button instruction circle_turtle.penup() circle_turtle.goto(400, 280) circle_turtle.color("lightgray") circle_turtle.write("Click GO to start", align="center", font=("Arial", 12, "bold")) circle_turtle.color("black") # Change button to EXIT button_state.state = "EXIT" # Redraw button screen.turtles().clear() # Clear previous button button_state.button_area = create_button(button_state.state) # Start animation animate_car(car_turtle, A, station_positions,center_x, center_y, radius, n, solution_index) elif button_state.state == "EXIT" and button_state.animation_started: turtle.bye() # Bind click handler screen.onclick(on_click) # Wait for user to close the window screen.mainloop() def animate_car(car_turtle, A, station_positions, center_x, center_y, radius, n, start_index): try: # Text display turtle (for gas info) text1_turtle = turtle.Turtle() text1_turtle.hideturtle() text1_turtle.penup() text1_turtle.speed(0) text2_turtle = turtle.Turtle() text2_turtle.hideturtle() text2_turtle.penup() text2_turtle.speed(0) current_gas = 0 start_station_idx = start_index // 2 text1_turtle.goto(-400, 350) # Start at the solution station start_x, start_y, start_angle = station_positions[start_station_idx] car_turtle.goto(start_x, start_y) car_turtle.showturtle() # Travel around the circle for step in range(n): # Visit n stations current_idx = (start_station_idx + step) % n next_idx = (start_station_idx + step + 1) % n # Get current station info station_x, station_y, station_angle = station_positions[current_idx] station_gas = A[2 * current_idx][1] # Move car to current station if not already there if step == 0: car_turtle.goto(station_x, station_y) # Refuel at current station current_gas += station_gas # Show refueling car_turtle.color("lime") #turtle.delay(400) car_turtle.color("red") # Update gas display update_gas_display(text1_turtle, text2_turtle, current_gas, f"At Station {current_idx+1}: +{station_gas} gas") turtle.delay(200) # Move to next station along circular arc next_x, next_y, next_angle = station_positions[next_idx] # Calculate angular distance to next station angle_diff = (next_angle - station_angle) % (2 * math.pi) # Animate movement steps = 15 for i in range(steps + 1): t = i / steps current_angle = station_angle + angle_diff * t x = center_x + radius * math.cos(current_angle) y = center_y + radius * math.sin(current_angle) car_turtle.goto(x, y) # Point car in direction of travel tangent_angle = current_angle + math.pi/2 car_turtle.setheading(tangent_angle * 180 / math.pi) turtle.delay(5) # Pay road cost road_cost = A[2 * current_idx + 1][1] current_gas -= road_cost # Show road cost car_turtle.color("orange") car_turtle.color("red") # Update gas display update_gas_display(text1_turtle, text2_turtle, current_gas, f"After Road {current_idx+1}: -{road_cost} gas") turtle.delay(400) # Check if out of gas if current_gas < 0: car_turtle.color("darkred") text1_turtle.goto(-460, 320) text1_turtle.color("red") text1_turtle.write("OUT OF GAS!", align="left", font=("Arial", 20, "bold")) break # Final message text1_turtle.goto(-460, 280) if current_gas >= 0: text1_turtle.color("blue") text1_turtle.write(f"Success! Final gas: {current_gas}", align="left", font=("Arial", 14, "bold")) else: text1_turtle.write("Failed! :(", align="left", font=("Arial", 18, "bold")) except (turtle.Terminator, tkinter.TclError): pass def update_gas_display(text1_turtle, text2_turtle, current_gas, action=""): try: text2_turtle.goto(-100, 0) text2_turtle.clear() text2_turtle.write(f"Current gas: {current_gas}", align="left", font=("Arial", 18, "bold")) except (turtle.Terminator, tkinter.TclError): pass T = 32 # Total for generation A = generate_input(T) visualize_solution(A)