Ride Sharing

public record Location(String id, String name) {
  public Location {
      if (id == null || id.isBlank() || name == null || name.isBlank()) {
          throw new IllegalArgumentException("Location id and name are required");
      }
  }
}

public record Road(String fromId, String toId, int minutes) {
  public Road {
      if (fromId == null || fromId.isBlank()
              || toId == null || toId.isBlank()
              || fromId.equals(toId) || minutes <= 0) {
          throw new IllegalArgumentException("Valid directed road fields are required");
      }
  }
}

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public final class RoadGraph {
  private final Map<String, Location> locations = new LinkedHashMap<>();
  private final Map<String, List<Road>> outgoing = new LinkedHashMap<>();

  public void addLocation(Location location) {
      if (location == null) {
          throw new IllegalArgumentException("Location is required");
      }
      if (locations.putIfAbsent(location.id(), location) != null) {
          throw new IllegalArgumentException("Duplicate location: " + location.id());
      }
      outgoing.put(location.id(), new ArrayList<>());
  }

  public void addDirectedRoad(String fromId, String toId, int minutes) {
      requireLocation(fromId);
      requireLocation(toId);
      outgoing.get(fromId).add(new Road(fromId, toId, minutes));
      outgoing.get(fromId).sort((left, right) -> left.toId().compareTo(right.toId()));
  }

  public void addTwoWayRoad(String firstId, String secondId, int minutes) {
      addDirectedRoad(firstId, secondId, minutes);
      addDirectedRoad(secondId, firstId, minutes);
  }

  public boolean containsLocation(String locationId) {
      return locations.containsKey(locationId);
  }

  public List<Road> roadsFrom(String locationId) {
      requireLocation(locationId);
      return List.copyOf(outgoing.get(locationId));
  }

  private void requireLocation(String locationId) {
      if (!locations.containsKey(locationId)) {
          throw new IllegalArgumentException("Unknown location: " + locationId);
      }
  }
}

import java.util.List;

public record Route(List<String> locationIds, int totalMinutes) {
  public Route {
      if (locationIds == null || locationIds.isEmpty() || totalMinutes < 0) {
          throw new IllegalArgumentException("Valid route fields are required");
      }
      locationIds = List.copyOf(locationIds);
  }
}

import java.util.Optional;

public interface RoutingStrategy {
  Optional<Route> route(
          RoadGraph graph,
          String startId,
          String targetId
  );
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.PriorityQueue;
import java.util.Set;

public final class DijkstraRoutingStrategy implements RoutingStrategy {
  private record QueueEntry(String locationId, int minutes) {}

  @Override
  public Optional<Route> route(
          RoadGraph graph,
          String startId,
          String targetId
  ) {
      if (graph == null || !graph.containsLocation(startId)
              || !graph.containsLocation(targetId)) {
          return Optional.empty();
      }
      if (startId.equals(targetId)) {
          return Optional.of(new Route(List.of(startId), 0));
      }

      Map<String, Integer> distance = new HashMap<>();
      Map<String, String> previous = new HashMap<>();
      Set<String> settled = new HashSet<>();
      PriorityQueue<QueueEntry> frontier = new PriorityQueue<>(
              Comparator.comparingInt(QueueEntry::minutes)
                      .thenComparing(QueueEntry::locationId)
      );
      distance.put(startId, 0);
      frontier.add(new QueueEntry(startId, 0));

      while (!frontier.isEmpty()) {
          QueueEntry current = frontier.remove();
          if (current.minutes() != distance.getOrDefault(
                  current.locationId(), Integer.MAX_VALUE)) {
              continue;
          }
          if (!settled.add(current.locationId())) {
              continue;
          }
          if (current.locationId().equals(targetId)) {
              return Optional.of(new Route(
                      rebuildPath(previous, startId, targetId),
                      current.minutes()
              ));
          }

          for (Road road : graph.roadsFrom(current.locationId())) {
              if (settled.contains(road.toId())) {
                  continue;
              }
              int candidate = Math.addExact(current.minutes(), road.minutes());
              int known = distance.getOrDefault(road.toId(), Integer.MAX_VALUE);
              if (candidate < known) {
                  distance.put(road.toId(), candidate);
                  previous.put(road.toId(), current.locationId());
                  frontier.add(new QueueEntry(road.toId(), candidate));
              }
          }
      }
      return Optional.empty();
  }

  private List<String> rebuildPath(
          Map<String, String> previous,
          String startId,
          String targetId
  ) {
      List<String> reversed = new ArrayList<>();
      String current = targetId;
      reversed.add(current);
      while (!current.equals(startId)) {
          current = previous.get(current);
          if (current == null) {
              throw new IllegalStateException("Predecessor chain is incomplete");
          }
          reversed.add(current);
      }
      Collections.reverse(reversed);
      return List.copyOf(reversed);
  }
}

public enum DriverStatus {
  AVAILABLE,
  BUSY
}

public final class Driver {
  private final String id;
  private final String name;
  private String currentLocationId;
  private DriverStatus status = DriverStatus.AVAILABLE;

  public Driver(String id, String name, String currentLocationId) {
      if (id == null || id.isBlank() || name == null || name.isBlank()
              || currentLocationId == null || currentLocationId.isBlank()) {
          throw new IllegalArgumentException("Driver fields are required");
      }
      this.id = id;
      this.name = name;
      this.currentLocationId = currentLocationId;
  }

  public String id() { return id; }
  public String name() { return name; }
  public String currentLocationId() { return currentLocationId; }
  public DriverStatus status() { return status; }

  public boolean assign() {
      if (status != DriverStatus.AVAILABLE) {
          return false;
      }
      status = DriverStatus.BUSY;
      return true;
  }

  public boolean completeAt(String destinationId) {
      if (status != DriverStatus.BUSY
              || destinationId == null || destinationId.isBlank()) {
          return false;
      }
      currentLocationId = destinationId;
      status = DriverStatus.AVAILABLE;
      return true;
  }
}

public record Rider(String id, String name) {
  public Rider {
      if (id == null || id.isBlank() || name == null || name.isBlank()) {
          throw new IllegalArgumentException("Rider fields are required");
      }
  }
}

public record RideRequest(
      String riderId,
      String pickupId,
      String destinationId
) {
  public RideRequest {
      if (riderId == null || riderId.isBlank()
              || pickupId == null || pickupId.isBlank()
              || destinationId == null || destinationId.isBlank()) {
          throw new IllegalArgumentException("Ride request fields are required");
      }
  }
}

public enum RideStatus {
  MATCHED,
  IN_PROGRESS,
  COMPLETED
}

public final class Ride {
  private final String id;
  private final String riderId;
  private final Driver driver;
  private final String pickupId;
  private final String destinationId;
  private final Route pickupRoute;
  private final Route tripRoute;
  private RideStatus status = RideStatus.MATCHED;

  public Ride(
          String id,
          String riderId,
          Driver driver,
          String pickupId,
          String destinationId,
          Route pickupRoute,
          Route tripRoute
  ) {
      if (id == null || id.isBlank() || riderId == null || riderId.isBlank()
              || driver == null || pickupId == null || pickupId.isBlank()
              || destinationId == null || destinationId.isBlank()
              || pickupRoute == null || tripRoute == null) {
          throw new IllegalArgumentException("Ride fields are required");
      }
      this.id = id;
      this.riderId = riderId;
      this.driver = driver;
      this.pickupId = pickupId;
      this.destinationId = destinationId;
      this.pickupRoute = pickupRoute;
      this.tripRoute = tripRoute;
  }

  public String id() { return id; }
  public String riderId() { return riderId; }
  public Driver driver() { return driver; }
  public String pickupId() { return pickupId; }
  public String destinationId() { return destinationId; }
  public Route pickupRoute() { return pickupRoute; }
  public Route tripRoute() { return tripRoute; }
  public RideStatus status() { return status; }

  public boolean start() {
      if (status != RideStatus.MATCHED) {
          return false;
      }
      status = RideStatus.IN_PROGRESS;
      return true;
  }

  public boolean complete() {
      if (status != RideStatus.IN_PROGRESS) {
          return false;
      }
      status = RideStatus.COMPLETED;
      return true;
  }
}

public record DriverMatch(Driver driver, Route pickupRoute) {
  public DriverMatch {
      if (driver == null || pickupRoute == null) {
          throw new IllegalArgumentException("Driver and pickup route are required");
      }
  }
}

import java.util.List;
import java.util.Optional;

public interface DriverMatchingStrategy {
  Optional<DriverMatch> match(
          List<Driver> drivers,
          String pickupId,
          RoadGraph graph,
          RoutingStrategy routing
  );
}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Optional;

public final class NearestDriverMatchingStrategy
      implements DriverMatchingStrategy {

  @Override
  public Optional<DriverMatch> match(
          List<Driver> drivers,
          String pickupId,
          RoadGraph graph,
          RoutingStrategy routing
  ) {
      List<DriverMatch> candidates = new ArrayList<>();
      for (Driver driver : drivers) {
          if (driver.status() != DriverStatus.AVAILABLE) {
              continue;
          }
          routing.route(graph, driver.currentLocationId(), pickupId)
                  .ifPresent(route -> candidates.add(new DriverMatch(driver, route)));
      }
      return candidates.stream().min(
              Comparator.comparingInt(
                              (DriverMatch match) -> match.pickupRoute().totalMinutes())
                      .thenComparing(match -> match.driver().id())
      );
  }
}

public enum MatchStatus {
  MATCHED,
  UNKNOWN_RIDER,
  INVALID_REQUEST,
  UNKNOWN_LOCATION,
  UNREACHABLE_TRIP,
  NO_DRIVER_AVAILABLE
}

import java.util.Optional;

public record MatchResult(MatchStatus status, Optional<Ride> ride) {
  public MatchResult {
      if (status == null || ride == null) {
          throw new IllegalArgumentException("Result fields are required");
      }
  }

  public static MatchResult accepted(Ride ride) {
      return new MatchResult(MatchStatus.MATCHED, Optional.of(ride));
  }

  public static MatchResult rejected(MatchStatus status) {
      return new MatchResult(status, Optional.empty());
  }
}

public enum RideActionStatus {
  STARTED,
  COMPLETED,
  RIDE_NOT_FOUND,
  INVALID_STATE
}

import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;

public final class RideService {
  private final Map<String, Rider> ridersById = new LinkedHashMap<>();
  private final List<Driver> drivers;
  private final Map<String, Ride> ridesById = new LinkedHashMap<>();
  private final RoadGraph graph;
  private final RoutingStrategy routing;
  private final DriverMatchingStrategy matching;
  private int nextRideNumber = 1;

  public RideService(
          List<Rider> riders,
          List<Driver> drivers,
          RoadGraph graph,
          RoutingStrategy routing,
          DriverMatchingStrategy matching
  ) {
      if (riders == null || riders.isEmpty()
              || drivers == null || drivers.isEmpty()
              || graph == null || routing == null || matching == null) {
          throw new IllegalArgumentException("Service dependencies are required");
      }
      for (Rider rider : riders) {
          if (ridersById.putIfAbsent(rider.id(), rider) != null) {
              throw new IllegalArgumentException("Duplicate rider: " + rider.id());
          }
      }
      this.drivers = List.copyOf(drivers);
      this.graph = graph;
      this.routing = routing;
      this.matching = matching;
  }

  public MatchResult requestRide(RideRequest request) {
      if (request == null) {
          return MatchResult.rejected(MatchStatus.INVALID_REQUEST);
      }
      if (!ridersById.containsKey(request.riderId())) {
          return MatchResult.rejected(MatchStatus.UNKNOWN_RIDER);
      }
      if (!graph.containsLocation(request.pickupId())
              || !graph.containsLocation(request.destinationId())) {
          return MatchResult.rejected(MatchStatus.UNKNOWN_LOCATION);
      }
      if (request.pickupId().equals(request.destinationId())) {
          return MatchResult.rejected(MatchStatus.INVALID_REQUEST);
      }

      Optional<Route> tripRoute = routing.route(
              graph, request.pickupId(), request.destinationId());
      if (tripRoute.isEmpty()) {
          return MatchResult.rejected(MatchStatus.UNREACHABLE_TRIP);
      }
      Optional<DriverMatch> match = matching.match(
              drivers, request.pickupId(), graph, routing);
      if (match.isEmpty()) {
          return MatchResult.rejected(MatchStatus.NO_DRIVER_AVAILABLE);
      }

      DriverMatch selected = match.get();
      String rideId = "R" + nextRideNumber;
      Ride ride = new Ride(
              rideId,
              request.riderId(),
              selected.driver(),
              request.pickupId(),
              request.destinationId(),
              selected.pickupRoute(),
              tripRoute.get()
      );
      if (!selected.driver().assign()) {
          return MatchResult.rejected(MatchStatus.NO_DRIVER_AVAILABLE);
      }
      nextRideNumber++;
      ridesById.put(ride.id(), ride);
      return MatchResult.accepted(ride);
  }

  public RideActionStatus startRide(String rideId) {
      Ride ride = ridesById.get(rideId);
      if (ride == null) {
          return RideActionStatus.RIDE_NOT_FOUND;
      }
      return ride.start()
              ? RideActionStatus.STARTED
              : RideActionStatus.INVALID_STATE;
  }

  public RideActionStatus completeRide(String rideId) {
      Ride ride = ridesById.get(rideId);
      if (ride == null) {
          return RideActionStatus.RIDE_NOT_FOUND;
      }
      if (ride.status() != RideStatus.IN_PROGRESS) {
          return RideActionStatus.INVALID_STATE;
      }
      if (!ride.complete()) {
          return RideActionStatus.INVALID_STATE;
      }
      if (!ride.driver().completeAt(ride.destinationId())) {
          throw new IllegalStateException("Ride and driver state disagree");
      }
      return RideActionStatus.COMPLETED;
  }

  public Optional<Ride> ride(String rideId) {
      return Optional.ofNullable(ridesById.get(rideId));
  }

  public List<Driver> drivers() {
      return drivers;
  }
}

import java.util.List;

public final class RideSharingDemo {
  public static void main(String[] args) {
      RoadGraph graph = sampleGraph();
      Driver maya = new Driver("D1", "Maya", "B");
      Driver leo = new Driver("D2", "Leo", "E");
      Driver noor = new Driver("D3", "Noor", "A");
      RideService service = new RideService(
              List.of(new Rider("U1", "Riya")),
              List.of(maya, leo, noor),
              graph,
              new DijkstraRoutingStrategy(),
              new NearestDriverMatchingStrategy()
      );

      MatchResult matched = service.requestRide(
              new RideRequest("U1", "D", "F")
      );
      Ride ride = matched.ride().orElseThrow();
      System.out.println("match status: " + matched.status());
      System.out.println("driver: " + ride.driver().id());
      System.out.println("pickup: " + ride.pickupRoute().locationIds()
              + " = " + ride.pickupRoute().totalMinutes());
      System.out.println("trip: " + ride.tripRoute().locationIds()
              + " = " + ride.tripRoute().totalMinutes());
      System.out.println("start: " + service.startRide(ride.id()));
      System.out.println("complete: " + service.completeRide(ride.id()));
      System.out.println("driver after trip: " + leo.currentLocationId()
              + " / " + leo.status());

      boolean noSecondRideBeforeRequest = service.ride("R2").isEmpty();
      MatchResult unreachablePickup = service.requestRide(
              new RideRequest("U1", "G", "F")
      );
      System.out.println("unreachable pickup: " + unreachablePickup.status());
      System.out.println("no new ride: "
              + (noSecondRideBeforeRequest && service.ride("R2").isEmpty()));
  }

  private static RoadGraph sampleGraph() {
      RoadGraph graph = new RoadGraph();
      graph.addLocation(new Location("A", "West"));
      graph.addLocation(new Location("B", "Market"));
      graph.addLocation(new Location("C", "Park"));
      graph.addLocation(new Location("D", "Museum"));
      graph.addLocation(new Location("E", "Harbor"));
      graph.addLocation(new Location("F", "Airport"));
      graph.addLocation(new Location("G", "Hill"));
      graph.addTwoWayRoad("A", "B", 4);
      graph.addTwoWayRoad("A", "C", 2);
      graph.addTwoWayRoad("C", "B", 1);
      graph.addTwoWayRoad("B", "D", 5);
      graph.addTwoWayRoad("C", "D", 8);
      graph.addTwoWayRoad("C", "E", 10);
      graph.addTwoWayRoad("D", "E", 2);
      graph.addTwoWayRoad("D", "F", 6);
      graph.addTwoWayRoad("E", "F", 3);
      graph.addDirectedRoad("G", "F", 1);
      return graph;
  }
}