from abc import ABC, abstractmethod
from enum import Enum
from datetime import datetime
from typing import Optional
import uuid


# --- Enums ---
class VehicleType(Enum):
    BIKE = "bike"
    CAR = "car"
    TRUCK = "truck"

class SpotSize(Enum):
    SMALL = 1   # fits Bike
    MEDIUM = 2  # fits Bike, Car
    LARGE = 3   # fits Bike, Car, Truck


# --- Vehicle hierarchy (inheritance for type-specific behavior) ---
class Vehicle(ABC):
    def __init__(self, license_plate: str):
        self.license_plate = license_plate

    @property
    @abstractmethod
    def type(self) -> VehicleType: pass

    @property
    @abstractmethod
    def required_size(self) -> SpotSize: pass


class Bike(Vehicle):
    @property
    def type(self): return VehicleType.BIKE
    @property
    def required_size(self): return SpotSize.SMALL


class Car(Vehicle):
    @property
    def type(self): return VehicleType.CAR
    @property
    def required_size(self): return SpotSize.MEDIUM


class Truck(Vehicle):
    @property
    def type(self): return VehicleType.TRUCK
    @property
    def required_size(self): return SpotSize.LARGE


# --- Parking spot ---
class ParkingSpot:
    def __init__(self, spot_id: str, size: SpotSize):
        self.spot_id = spot_id
        self.size = size
        self.vehicle: Optional[Vehicle] = None

    @property
    def is_free(self) -> bool:
        return self.vehicle is None

    def can_fit(self, vehicle: Vehicle) -> bool:
        # A spot can fit a vehicle if it's at least as large as the vehicle needs
        return self.size.value >= vehicle.required_size.value

    def park(self, vehicle: Vehicle):
        if not self.is_free:
            raise ValueError(f"Spot {self.spot_id} is occupied")
        if not self.can_fit(vehicle):
            raise ValueError(f"Vehicle doesn't fit in spot {self.spot_id}")
        self.vehicle = vehicle

    def vacate(self):
        self.vehicle = None


# --- Observer pattern for display boards ---
class FloorObserver(ABC):
    @abstractmethod
    def update(self, floor): pass


class Floor:
    def __init__(self, floor_number: int, spots: list[ParkingSpot]):
        self.floor_number = floor_number
        self.spots = spots
        self._observers: list[FloorObserver] = []

    def attach(self, observer: FloorObserver):
        self._observers.append(observer)

    def _notify(self):
        for o in self._observers:
            o.update(self)

    def find_free_spot(self, vehicle: Vehicle) -> Optional[ParkingSpot]:
        # Best-fit: smallest spot that fits
        candidates = [s for s in self.spots if s.is_free and s.can_fit(vehicle)]
        return min(candidates, key=lambda s: s.size.value, default=None)

    def park(self, vehicle: Vehicle) -> Optional[ParkingSpot]:
        spot = self.find_free_spot(vehicle)
        if spot:
            spot.park(vehicle)
            self._notify()
        return spot

    def vacate(self, spot: ParkingSpot):
        spot.vacate()
        self._notify()

    def free_spots_by_size(self) -> dict[SpotSize, int]:
        result = {s: 0 for s in SpotSize}
        for spot in self.spots:
            if spot.is_free:
                result[spot.size] += 1
        return result


class DisplayBoard(FloorObserver):
    def update(self, floor: Floor):
        counts = floor.free_spots_by_size()
        print(f"[Floor {floor.floor_number}] Free — "
              f"Small: {counts[SpotSize.SMALL]}, "
              f"Medium: {counts[SpotSize.MEDIUM]}, "
              f"Large: {counts[SpotSize.LARGE]}")


# --- Ticket ---
class Ticket:
    def __init__(self, vehicle: Vehicle, spot: ParkingSpot, floor_number: int):
        self.id = str(uuid.uuid4())[:8]
        self.vehicle = vehicle
        self.spot = spot
        self.floor_number = floor_number
        self.entry_time = datetime.now()
        self.exit_time: Optional[datetime] = None
        self.amount: Optional[float] = None


# --- Strategy pattern for pricing ---
class PricingStrategy(ABC):
    @abstractmethod
    def calculate(self, ticket: Ticket) -> float: pass


class HourlyPricing(PricingStrategy):
    RATES = {
        VehicleType.BIKE: 10,
        VehicleType.CAR: 30,
        VehicleType.TRUCK: 60,
    }

    def calculate(self, ticket: Ticket) -> float:
        duration = ticket.exit_time - ticket.entry_time
        hours = max(1, duration.total_seconds() / 3600)   # min 1 hour
        return self.RATES[ticket.vehicle.type] * hours


class FlatRatePricing(PricingStrategy):
    RATES = {VehicleType.BIKE: 50, VehicleType.CAR: 150, VehicleType.TRUCK: 300}

    def calculate(self, ticket: Ticket) -> float:
        return self.RATES[ticket.vehicle.type]


# --- Gates ---
class EntryGate:
    def __init__(self, lot):
        self.lot = lot

    def admit(self, vehicle: Vehicle) -> Optional[Ticket]:
        return self.lot.park(vehicle)


class ExitGate:
    def __init__(self, lot, pricing: PricingStrategy):
        self.lot = lot
        self.pricing = pricing

    def process(self, ticket: Ticket) -> float:
        ticket.exit_time = datetime.now()
        ticket.amount = self.pricing.calculate(ticket)
        self.lot.vacate(ticket)
        return ticket.amount


# --- ParkingLot ---
class ParkingLot:
    def __init__(self, floors: list[Floor]):
        self.floors = floors
        self.active_tickets: dict[str, Ticket] = {}   # ticket_id -> Ticket

    def park(self, vehicle: Vehicle) -> Optional[Ticket]:
        for floor in self.floors:
            spot = floor.park(vehicle)
            if spot:
                ticket = Ticket(vehicle, spot, floor.floor_number)
                self.active_tickets[ticket.id] = ticket
                return ticket
        return None   # lot full

    def vacate(self, ticket: Ticket):
        floor = self.floors[ticket.floor_number]
        floor.vacate(ticket.spot)
        self.active_tickets.pop(ticket.id, None)


# --- Usage ---
def build_lot():
    floors = []
    for f in range(3):
        spots = (
            [ParkingSpot(f"F{f}-S{i}", SpotSize.SMALL) for i in range(5)]
            + [ParkingSpot(f"F{f}-M{i}", SpotSize.MEDIUM) for i in range(10)]
            + [ParkingSpot(f"F{f}-L{i}", SpotSize.LARGE) for i in range(3)]
        )
        floor = Floor(f, spots)
        floor.attach(DisplayBoard())
        floors.append(floor)
    return ParkingLot(floors)


lot = build_lot()
entry = EntryGate(lot)
exit_gate = ExitGate(lot, HourlyPricing())

t1 = entry.admit(Car("KA-01-1234"))
t2 = entry.admit(Bike("KA-01-5678"))
t3 = entry.admit(Truck("KA-01-9999"))

import time; time.sleep(0.1)
amount = exit_gate.process(t1)
print(f"\nCar paid: ₹{amount:.2f}")

from abc import ABC, abstractmethod
from enum import Enum
from typing import Optional
import heapq


class Direction(Enum):
    UP = 1
    DOWN = -1
    IDLE = 0


# --- Request types ---
class Request(ABC):
    @property
    @abstractmethod
    def floor(self) -> int: pass


class ExternalRequest(Request):
    def __init__(self, source_floor: int, direction: Direction):
        self._floor = source_floor
        self.direction = direction
    @property
    def floor(self): return self._floor
    def __repr__(self):
        return f"ExternalRequest(floor={self._floor}, dir={self.direction.name})"


class InternalRequest(Request):
    def __init__(self, destination: int):
        self._floor = destination
    @property
    def floor(self): return self._floor
    def __repr__(self):
        return f"InternalRequest(dest={self._floor})"


# --- State pattern for elevator ---
class ElevatorState(ABC):
    @abstractmethod
    def step(self, elevator): pass
    @abstractmethod
    def name(self) -> str: pass


class Idle(ElevatorState):
    def step(self, elevator):
        if elevator.has_pending_requests():
            target = elevator.next_target()
            if target > elevator.current_floor:
                elevator.set_state(MovingUp())
            elif target < elevator.current_floor:
                elevator.set_state(MovingDown())
            else:
                elevator.set_state(DoorOpen())
    def name(self): return "IDLE"


class MovingUp(ElevatorState):
    def step(self, elevator):
        elevator.current_floor += 1
        print(f"[Elevator {elevator.id}] Moving UP → floor {elevator.current_floor}")
        if elevator.current_floor in elevator.stops:
            elevator.set_state(DoorOpen())
    def name(self): return "MOVING_UP"


class MovingDown(ElevatorState):
    def step(self, elevator):
        elevator.current_floor -= 1
        print(f"[Elevator {elevator.id}] Moving DOWN → floor {elevator.current_floor}")
        if elevator.current_floor in elevator.stops:
            elevator.set_state(DoorOpen())
    def name(self): return "MOVING_DOWN"


class DoorOpen(ElevatorState):
    def step(self, elevator):
        print(f"[Elevator {elevator.id}] Doors open at floor {elevator.current_floor}")
        elevator.stops.discard(elevator.current_floor)
        elevator.set_state(DoorClosed())
    def name(self): return "DOOR_OPEN"


class DoorClosed(ElevatorState):
    def step(self, elevator):
        print(f"[Elevator {elevator.id}] Doors closed")
        if elevator.has_pending_requests():
            target = elevator.next_target()
            if target > elevator.current_floor:
                elevator.set_state(MovingUp())
            elif target < elevator.current_floor:
                elevator.set_state(MovingDown())
            else:
                elevator.set_state(DoorOpen())
        else:
            elevator.set_state(Idle())
    def name(self): return "DOOR_CLOSED"


# --- Elevator ---
class Elevator:
    def __init__(self, id: int, num_floors: int):
        self.id = id
        self.num_floors = num_floors
        self.current_floor = 0
        self.stops: set[int] = set()
        self._state: ElevatorState = Idle()

    def set_state(self, state: ElevatorState):
        self._state = state

    @property
    def state_name(self): return self._state.name()

    def step(self):
        self._state.step(self)

    def accept(self, request: Request):
        self.stops.add(request.floor)
        if isinstance(self._state, Idle):
            self._state.step(self)   # Wake it up

    def has_pending_requests(self):
        return bool(self.stops)

    def next_target(self) -> int:
        # Simple: go to nearest stop
        return min(self.stops, key=lambda f: abs(f - self.current_floor))

    @property
    def direction(self) -> Direction:
        if isinstance(self._state, MovingUp): return Direction.UP
        if isinstance(self._state, MovingDown): return Direction.DOWN
        return Direction.IDLE


# --- Strategy for dispatching ---
class SchedulingStrategy(ABC):
    @abstractmethod
    def select(self, elevators: list[Elevator], request: Request) -> Elevator: pass


class NearestCarStrategy(SchedulingStrategy):
    def select(self, elevators, request):
        # Idle elevators are best; else pick the one whose current trajectory matches
        def score(e: Elevator):
            distance = abs(e.current_floor - request.floor)
            # Prefer idle (bonus of 0); penalize if direction disagrees
            if e.direction == Direction.IDLE:
                return distance
            # Same direction as request is better
            moving_toward = (
                (e.direction == Direction.UP and request.floor >= e.current_floor) or
                (e.direction == Direction.DOWN and request.floor <= e.current_floor)
            )
            return distance + (0 if moving_toward else 100)
        return min(elevators, key=score)


class RoundRobinStrategy(SchedulingStrategy):
    def __init__(self):
        self._index = 0
    def select(self, elevators, request):
        chosen = elevators[self._index % len(elevators)]
        self._index += 1
        return chosen


# --- Dispatcher ---
class Dispatcher:
    def __init__(self, elevators: list[Elevator], strategy: SchedulingStrategy):
        self.elevators = elevators
        self.strategy = strategy

    def submit(self, request: Request, for_elevator: Optional[Elevator] = None):
        if isinstance(request, InternalRequest) and for_elevator:
            for_elevator.accept(request)
        else:
            chosen = self.strategy.select(self.elevators, request)
            print(f">>> Routing {request} to Elevator {chosen.id}")
            chosen.accept(request)


# --- Simulation tick ---
class Building:
    def __init__(self, num_floors: int, num_elevators: int,
                 strategy: SchedulingStrategy):
        self.num_floors = num_floors
        self.elevators = [Elevator(i, num_floors) for i in range(num_elevators)]
        self.dispatcher = Dispatcher(self.elevators, strategy)

    def tick(self):
        """One time unit — every elevator advances its state."""
        for e in self.elevators:
            e.step()


# --- Usage ---
building = Building(num_floors=10, num_elevators=2, strategy=NearestCarStrategy())

# Simulate some requests
building.dispatcher.submit(ExternalRequest(5, Direction.UP))
for _ in range(12):
    building.tick()
    # After elevator reaches floor 5, rider presses "floor 8"
    if building.elevators[0].current_floor == 5 and 8 not in building.elevators[0].stops:
        building.dispatcher.submit(InternalRequest(8), for_elevator=building.elevators[0])

from abc import ABC, abstractmethod
from enum import Enum
from datetime import datetime, timedelta
from typing import Optional
from collections import deque
import uuid


# --- Enums ---
class BookStatus(Enum):
    AVAILABLE = "available"
    BORROWED = "borrowed"
    LOST = "lost"


# --- Domain entities ---
class Book:
    """The title (abstract book)."""
    def __init__(self, isbn: str, title: str, author: str, category: str):
        self.isbn = isbn
        self.title = title
        self.author = author
        self.category = category
        self.copies: list[BookItem] = []

    def add_copy(self, copy: "BookItem"):
        self.copies.append(copy)

    def available_copy(self) -> Optional["BookItem"]:
        return next((c for c in self.copies if c.status == BookStatus.AVAILABLE), None)


class BookItem:
    """A physical copy of a book."""
    def __init__(self, book: Book, copy_id: str):
        self.book = book
        self.copy_id = copy_id
        self.status = BookStatus.AVAILABLE


# --- Strategy for membership policy ---
class MembershipPolicy(ABC):
    @property
    @abstractmethod
    def max_books(self) -> int: pass
    @property
    @abstractmethod
    def loan_days(self) -> int: pass
    @property
    @abstractmethod
    def fine_per_day(self) -> float: pass


class StudentPolicy(MembershipPolicy):
    @property
    def max_books(self): return 3
    @property
    def loan_days(self): return 14
    @property
    def fine_per_day(self): return 5.0


class FacultyPolicy(MembershipPolicy):
    @property
    def max_books(self): return 10
    @property
    def loan_days(self): return 30
    @property
    def fine_per_day(self): return 2.0


class GuestPolicy(MembershipPolicy):
    @property
    def max_books(self): return 1
    @property
    def loan_days(self): return 7
    @property
    def fine_per_day(self): return 10.0


# --- Member ---
class Member:
    def __init__(self, member_id: str, name: str, policy: MembershipPolicy):
        self.member_id = member_id
        self.name = name
        self.policy = policy
        self.active_loans: list[Loan] = []

    def can_borrow_more(self) -> bool:
        return len(self.active_loans) < self.policy.max_books


# --- Loan ---
class Loan:
    def __init__(self, member: Member, book_item: BookItem):
        self.id = str(uuid.uuid4())[:8]
        self.member = member
        self.book_item = book_item
        self.issue_date = datetime.now()
        self.due_date = self.issue_date + timedelta(days=member.policy.loan_days)
        self.return_date: Optional[datetime] = None

    @property
    def is_overdue(self) -> bool:
        return datetime.now() > self.due_date and self.return_date is None

    def calculate_fine(self) -> float:
        end_date = self.return_date or datetime.now()
        if end_date <= self.due_date:
            return 0.0
        overdue_days = (end_date - self.due_date).days + 1
        return overdue_days * self.member.policy.fine_per_day


# --- Reservation ---
class Reservation:
    def __init__(self, member: Member, book: Book):
        self.member = member
        self.book = book
        self.reserved_on = datetime.now()


# --- Search ---
class BookSearch:
    def __init__(self, books: list[Book]):
        self.books = books

    def by_title(self, title: str) -> list[Book]:
        return [b for b in self.books if title.lower() in b.title.lower()]

    def by_author(self, author: str) -> list[Book]:
        return [b for b in self.books if author.lower() in b.author.lower()]

    def by_category(self, category: str) -> list[Book]:
        return [b for b in self.books if b.category.lower() == category.lower()]


# --- Library (the facade/coordinator) ---
class Library:
    def __init__(self):
        self.books: dict[str, Book] = {}           # isbn -> Book
        self.members: dict[str, Member] = {}
        self.active_loans: dict[str, Loan] = {}    # loan_id -> Loan
        self.reservations: dict[str, deque[Reservation]] = {}  # isbn -> queue

    # Book management
    def add_book(self, book: Book):
        self.books[book.isbn] = book

    def add_member(self, member: Member):
        self.members[member.member_id] = member

    @property
    def search(self) -> BookSearch:
        return BookSearch(list(self.books.values()))

    # Core flow
    def borrow(self, member_id: str, isbn: str) -> Optional[Loan]:
        member = self.members[member_id]
        book = self.books[isbn]

        if not member.can_borrow_more():
            print(f"{member.name} has reached borrowing limit.")
            return None

        copy = book.available_copy()
        if not copy:
            print(f"No copies available for '{book.title}'. Consider reserving.")
            return None

        copy.status = BookStatus.BORROWED
        loan = Loan(member, copy)
        member.active_loans.append(loan)
        self.active_loans[loan.id] = loan
        print(f"Issued '{book.title}' to {member.name}. Due: {loan.due_date.date()}")
        return loan

    def return_book(self, loan_id: str) -> float:
        loan = self.active_loans.pop(loan_id)
        loan.return_date = datetime.now()
        fine = loan.calculate_fine()
        loan.book_item.status = BookStatus.AVAILABLE
        loan.member.active_loans.remove(loan)
        print(f"Returned '{loan.book_item.book.title}'. Fine: ₹{fine:.2f}")

        # Check reservation queue
        isbn = loan.book_item.book.isbn
        queue = self.reservations.get(isbn)
        if queue:
            next_reservation = queue.popleft()
            print(f"  Notifying {next_reservation.member.name}: "
                  f"'{loan.book_item.book.title}' is now available for you.")
        return fine

    def reserve(self, member_id: str, isbn: str):
        member = self.members[member_id]
        book = self.books[isbn]
        if book.available_copy():
            print(f"Book '{book.title}' is available — just borrow it.")
            return
        self.reservations.setdefault(isbn, deque()).append(Reservation(member, book))
        print(f"{member.name} reserved '{book.title}'.")


# --- Usage ---
library = Library()

# Add books
b1 = Book("978-001", "The Pragmatic Programmer", "Hunt & Thomas", "Tech")
b1.add_copy(BookItem(b1, "c1"))
b1.add_copy(BookItem(b1, "c2"))
library.add_book(b1)

# Add members
amit = Member("M1", "Amit", StudentPolicy())
priya = Member("M2", "Priya", FacultyPolicy())
library.add_member(amit)
library.add_member(priya)

# Flow
loan1 = library.borrow("M1", "978-001")
loan2 = library.borrow("M2", "978-001")
loan3 = library.borrow("M1", "978-001")   # No copies — should reserve
library.reserve("M1", "978-001")

library.return_book(loan1.id)   # Should notify Amit

from abc import ABC, abstractmethod
from enum import Enum
from typing import Optional


# --- Product ---
class Product:
    def __init__(self, code: str, name: str, price: int):
        self.code = code
        self.name = name
        self.price = price   # in rupees (integer for simplicity)


# --- Inventory ---
class Inventory:
    def __init__(self):
        self.products: dict[str, tuple[Product, int]] = {}   # code -> (product, qty)
        self.coins: dict[int, int] = {1: 0, 2: 0, 5: 0, 10: 0, 20: 0, 50: 0, 100: 0}

    def add_product(self, product: Product, qty: int):
        if product.code in self.products:
            p, existing = self.products[product.code]
            self.products[product.code] = (p, existing + qty)
        else:
            self.products[product.code] = (product, qty)

    def stock_coins(self, denomination: int, count: int):
        if denomination not in self.coins:
            raise ValueError(f"Invalid denomination: {denomination}")
        self.coins[denomination] += count

    def get_product(self, code: str) -> Optional[Product]:
        if code not in self.products: return None
        return self.products[code][0]

    def has_stock(self, code: str) -> bool:
        return code in self.products and self.products[code][1] > 0

    def remove_one(self, code: str):
        p, qty = self.products[code]
        if qty == 0:
            raise ValueError("Out of stock")
        self.products[code] = (p, qty - 1)

    def can_provide_change(self, amount: int) -> bool:
        # Greedy check — can we make this amount?
        remaining = amount
        for denom in sorted(self.coins.keys(), reverse=True):
            use = min(self.coins[denom], remaining // denom)
            remaining -= use * denom
        return remaining == 0

    def dispense_change(self, amount: int) -> dict[int, int]:
        dispensed = {}
        remaining = amount
        for denom in sorted(self.coins.keys(), reverse=True):
            use = min(self.coins[denom], remaining // denom)
            if use > 0:
                dispensed[denom] = use
                self.coins[denom] -= use
                remaining -= use * denom
        if remaining != 0:
            raise ValueError("Can't make exact change")
        return dispensed


# --- State pattern ---
class VendingState(ABC):
    @abstractmethod
    def insert_money(self, machine, denomination: int): pass
    @abstractmethod
    def select_product(self, machine, code: str): pass
    @abstractmethod
    def cancel(self, machine): pass


class Idle(VendingState):
    def insert_money(self, machine, denomination):
        machine.inventory.stock_coins(denomination, 1)   # machine absorbs it
        machine.balance += denomination
        print(f"[Idle → HasMoney] Balance: ₹{machine.balance}")
        machine.set_state(HasMoney())

    def select_product(self, machine, code):
        print("Insert money first.")

    def cancel(self, machine):
        print("Nothing to cancel.")


class HasMoney(VendingState):
    def insert_money(self, machine, denomination):
        machine.inventory.stock_coins(denomination, 1)
        machine.balance += denomination
        print(f"Balance: ₹{machine.balance}")

    def select_product(self, machine, code):
        product = machine.inventory.get_product(code)
        if not product:
            print(f"Unknown product code: {code}"); return
        if not machine.inventory.has_stock(code):
            print(f"'{product.name}' is out of stock"); return
        if machine.balance < product.price:
            print(f"Insufficient balance. Need ₹{product.price - machine.balance} more."); return

        change = machine.balance - product.price
        if change > 0 and not machine.inventory.can_provide_change(change):
            print(f"Can't give ₹{change} change. Please use exact amount or cancel.")
            return

        print(f"[HasMoney → Dispensing]")
        machine.set_state(Dispensing())
        machine.dispense(product, change)

    def cancel(self, machine):
        # Refund — but we've already pooled the coins. In reality we'd track separately.
        refund = machine.inventory.dispense_change(machine.balance)
        print(f"Refunding ₹{machine.balance} → {refund}")
        machine.balance = 0
        machine.set_state(Idle())


class Dispensing(VendingState):
    def insert_money(self, m, d):
        print("Busy dispensing. Please wait.")
    def select_product(self, m, code):
        print("Busy dispensing.")
    def cancel(self, m):
        print("Can't cancel during dispense.")


# --- Vending machine ---
class VendingMachine:
    def __init__(self, inventory: Inventory):
        self.inventory = inventory
        self.balance = 0
        self._state: VendingState = Idle()

    def set_state(self, state: VendingState):
        self._state = state

    def insert_money(self, denomination: int):
        self._state.insert_money(self, denomination)

    def select_product(self, code: str):
        self._state.select_product(self, code)

    def cancel(self):
        self._state.cancel(self)

    def dispense(self, product: Product, change: int):
        self.inventory.remove_one(product.code)
        print(f"Dispensed: {product.name}")
        if change > 0:
            change_dispensed = self.inventory.dispense_change(change)
            print(f"Change: ₹{change} → {change_dispensed}")
        self.balance = 0
        self.set_state(Idle())


# --- Usage ---
inv = Inventory()
inv.add_product(Product("A1", "Coke", 30), 5)
inv.add_product(Product("A2", "Chips", 20), 5)
inv.add_product(Product("A3", "Water", 15), 5)
for denom in [1, 2, 5, 10, 20]:
    inv.stock_coins(denom, 20)   # pre-stocked change

vm = VendingMachine(inv)

vm.select_product("A1")     # Error: no money
vm.insert_money(20)
vm.insert_money(10)
vm.insert_money(5)          # Balance ₹35
vm.select_product("A1")     # Dispense Coke, ₹5 change

from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from typing import Optional
import uuid


# --- User / Group ---
@dataclass
class User:
    user_id: str
    name: str
    email: str

    def __hash__(self): return hash(self.user_id)
    def __eq__(self, other): return isinstance(other, User) and self.user_id == other.user_id


@dataclass
class Group:
    group_id: str
    name: str
    members: list[User] = field(default_factory=list)

    def add_member(self, user: User):
        if user not in self.members:
            self.members.append(user)


# --- Split ---
@dataclass
class Split:
    user: User
    amount: float


# --- Strategy for splitting ---
class SplitStrategy(ABC):
    @abstractmethod
    def calculate(self, total: float, participants: list[User], **kwargs) -> list[Split]: pass


class EqualSplit(SplitStrategy):
    def calculate(self, total, participants, **kwargs):
        n = len(participants)
        share = round(total / n, 2)
        splits = [Split(u, share) for u in participants]
        # Adjust last split for rounding drift
        drift = total - share * n
        splits[-1] = Split(splits[-1].user, round(splits[-1].amount + drift, 2))
        return splits


class ExactSplit(SplitStrategy):
    def calculate(self, total, participants, *, exact_amounts: dict[User, float], **kwargs):
        if abs(sum(exact_amounts.values()) - total) > 0.01:
            raise ValueError("Exact amounts don't sum to total")
        return [Split(u, exact_amounts[u]) for u in participants]


class PercentSplit(SplitStrategy):
    def calculate(self, total, participants, *, percentages: dict[User, float], **kwargs):
        if abs(sum(percentages.values()) - 100) > 0.01:
            raise ValueError("Percentages don't sum to 100")
        return [Split(u, round(total * percentages[u] / 100, 2)) for u in participants]


# --- Expense ---
@dataclass
class Expense:
    id: str
    description: str
    amount: float
    payer: User
    splits: list[Split]
    group: Optional[Group] = None


# --- Balance sheet ---
class BalanceSheet:
    """
    Stores pairwise debts. balances[a][b] = how much a owes b.
    Invariant: balances[a][b] and balances[b][a] are not both nonzero;
    we net them out.
    """
    def __init__(self):
        self._balances: dict[User, dict[User, float]] = {}

    def _get(self, a: User, b: User) -> float:
        return self._balances.get(a, {}).get(b, 0.0)

    def _set(self, a: User, b: User, amount: float):
        self._balances.setdefault(a, {})[b] = amount

    def add_debt(self, debtor: User, creditor: User, amount: float):
        """debtor owes creditor `amount` more."""
        if debtor == creditor: return
        # Net against reverse direction
        reverse = self._get(creditor, debtor)
        if reverse >= amount:
            self._set(creditor, debtor, round(reverse - amount, 2))
        else:
            # Clear reverse, add remainder to forward
            remainder = amount - reverse
            self._set(creditor, debtor, 0.0)
            self._set(debtor, creditor, round(self._get(debtor, creditor) + remainder, 2))

    def get_balance(self, user: User) -> dict[User, float]:
        """Returns dict of other_user -> amount (positive = user owes them, negative = they owe user)."""
        result = {}
        for other, amt in self._balances.get(user, {}).items():
            if amt > 0:
                result[other] = amt
        for other, inner in self._balances.items():
            if other == user: continue
            amt = inner.get(user, 0.0)
            if amt > 0:
                result[other] = result.get(other, 0) - amt
        return result

    def all_pairwise(self) -> list[tuple[User, User, float]]:
        result = []
        for debtor, inner in self._balances.items():
            for creditor, amt in inner.items():
                if amt > 0:
                    result.append((debtor, creditor, amt))
        return result


# --- ExpenseManager (Facade) ---
class ExpenseManager:
    def __init__(self):
        self.users: dict[str, User] = {}
        self.groups: dict[str, Group] = {}
        self.expenses: list[Expense] = []
        self.balance_sheet = BalanceSheet()

    def add_user(self, user: User):
        self.users[user.user_id] = user

    def add_group(self, group: Group):
        self.groups[group.group_id] = group

    def add_expense(self, description: str, amount: float, payer: User,
                    participants: list[User], strategy: SplitStrategy,
                    group: Optional[Group] = None, **strategy_kwargs) -> Expense:
        splits = strategy.calculate(amount, participants, **strategy_kwargs)
        expense = Expense(
            id=str(uuid.uuid4())[:8],
            description=description, amount=amount,
            payer=payer, splits=splits, group=group,
        )
        self.expenses.append(expense)

        # Update balances: each non-payer participant owes the payer their split
        for s in splits:
            if s.user != payer:
                self.balance_sheet.add_debt(s.user, payer, s.amount)
        return expense

    def record_settlement(self, from_user: User, to_user: User, amount: float):
        """A direct payment reduces debt from_user → to_user."""
        self.balance_sheet.add_debt(to_user, from_user, amount)
        print(f"Settled: {from_user.name} paid {to_user.name} ₹{amount}")

    def show_balances(self, user: User):
        balances = self.balance_sheet.get_balance(user)
        if not balances:
            print(f"{user.name}: all settled!")
            return
        for other, amt in balances.items():
            if amt > 0:
                print(f"{user.name} owes {other.name}: ₹{amt:.2f}")
            else:
                print(f"{other.name} owes {user.name}: ₹{-amt:.2f}")


# --- Usage ---
mgr = ExpenseManager()
amit = User("u1", "Amit", "amit@x.com")
priya = User("u2", "Priya", "priya@x.com")
rohan = User("u3", "Rohan", "rohan@x.com")
for u in [amit, priya, rohan]:
    mgr.add_user(u)

trip = Group("g1", "Goa Trip")
for u in [amit, priya, rohan]:
    trip.add_member(u)
mgr.add_group(trip)

# Amit pays ₹1200 for dinner; split equally among all 3
mgr.add_expense("Dinner", 1200, amit, [amit, priya, rohan],
                EqualSplit(), group=trip)

# Priya pays ₹900 for cab; Amit owes 500, Rohan owes 400 (exact)
mgr.add_expense("Cab", 900, priya, [amit, priya, rohan],
                ExactSplit(), group=trip,
                exact_amounts={amit: 500, priya: 0, rohan: 400})

mgr.show_balances(amit)
mgr.show_balances(priya)
mgr.show_balances(rohan)

# Settlement
mgr.record_settlement(amit, priya, 100)
print("---")
mgr.show_balances(amit)
mgr.show_balances(priya)