import java.util.*;

/*
================================================================================
WHOLE-CABIN HYBRID BOARDING SIMULATION
FIRST ATTEMPT - TWO AISLES, UNIQUE PASSENGERS, RANDOM ORDER
================================================================================

This experiment combines two execution styles:

1. TEMPORAL / TICK-DRIVEN EXECUTION
   Both physical aisles advance synchronously, one global tick at a time.

2. EVENT-DRIVEN EXECUTION
   When a passenger reaches the assigned row, a local seat-access event begins:
   blockers stand -> blockers enter aisle -> target sits -> blockers reseat.

The event phases advance at tick boundaries. The model is therefore hybrid:
globally temporal and locally event-driven.

AISLE DATASET
-1 = empty aisle tile
 0+ = passenger ID occupying the tile

SEAT DATASET
-1 = empty seat
 0+ = passenger ID seated in the seat

FIRST-ATTEMPT BOUNDARIES
- Representative 3-4-3 layout:
      A B C | LEFT AISLE | D E F G | RIGHT AISLE | H I J
- One front entrance feeding two independently shuffled queues.
- Nearly full cabin; unique seat per passenger.
- Middle-bank passengers are permanently assigned to one serving aisle.
- No cross-aisle deviation. Opposite-side arrivals to the same middle bank
  are coordinated by a deterministic row-level reservation.
- Fixed walking speed: at most one tile per tick.
- Random entry headway creates intermittent empty aisle tiles.
- No luggage, families, crew actions or airline boarding policy.
- Synchronous aisle updates prevent unrealistic multiple moves in one tick.
================================================================================
*/
public class WholeCabinHybridBoardingSimulation {

    static final int ROWS = 12;
    static final double OCCUPANCY_RATE = 0.92;
    static final long RANDOM_SEED = 4602L;
    static final int MAX_TICKS = 5000;
    static final int MIN_ENTRY_HEADWAY = 0;
    static final int MAX_ENTRY_HEADWAY = 2;
    static final boolean VERBOSE_TICK_OUTPUT = false;
    static final char[] SEAT_LETTERS = {'A','B','C','D','E','F','G','H','I','J'};
    static final int EMPTY = -1;

    enum AisleSide { LEFT, RIGHT }
    enum PassengerState { WAITING_TO_ENTER, MOVING_IN_AISLE, WAITING_AT_ROW, IN_SEAT_EVENT, SEATED }
    enum EventPhase { BLOCKERS_STAND, BLOCKERS_ENTER_AISLE, TARGET_SITS, BLOCKERS_RESEAT, COMPLETE }

    static final class Passenger {
        final int id;
        final int row;
        final char seatLetter;
        final int seatIndex;
        final AisleSide servingAisle;
        PassengerState state = PassengerState.WAITING_TO_ENTER;
        int aisleEntryTick = -1;
        int seatedTick = -1;
        int waitingTicks = 0;

        Passenger(int id, int row, char seatLetter, int seatIndex, AisleSide servingAisle) {
            this.id = id;
            this.row = row;
            this.seatLetter = seatLetter;
            this.seatIndex = seatIndex;
            this.servingAisle = servingAisle;
        }

        String seatName() { return (row + 1) + String.valueOf(seatLetter); }
        public String toString() { return "P" + id + "->" + seatName() + "(" + servingAisle + ")"; }
    }

    static final class SeatEvent {
        final Passenger target;
        final int rowIndex;
        final List<Integer> blockerPassengerIds;
        final List<Integer> blockerSeatIndices;
        final Map<Integer,Integer> blockerYieldTileByPassenger = new LinkedHashMap<>();
        EventPhase phase = EventPhase.BLOCKERS_STAND;

        SeatEvent(Passenger target, int rowIndex, List<Integer> blockerPassengerIds,
                  List<Integer> blockerSeatIndices) {
            this.target = target;
            this.rowIndex = rowIndex;
            this.blockerPassengerIds = blockerPassengerIds;
            this.blockerSeatIndices = blockerSeatIndices;
        }
    }

    static final class AisleContext {
        final AisleSide side;
        final int[] aisle = new int[ROWS + 3];
        final Deque<Integer> entryQueue = new ArrayDeque<>();
        SeatEvent activeEvent;
        int entryCooldown = 0;
        int maxOccupiedTiles = 0;
        int totalMoves = 0;
        int seatEvents = 0;
        int singleBlockerEvents = 0;
        int multipleBlockerEvents = 0;
        int temporaryAisleReoccupations = 0;

        AisleContext(AisleSide side) {
            this.side = side;
            Arrays.fill(aisle, EMPTY);
        }
    }

    final Random random = new Random(RANDOM_SEED);
    final Map<Integer,Passenger> passengers = new LinkedHashMap<>();
    final int[][] seats = new int[ROWS][SEAT_LETTERS.length];
    final AisleContext left = new AisleContext(AisleSide.LEFT);
    final AisleContext right = new AisleContext(AisleSide.RIGHT);
    int currentTick = 0;

    // Row-level reservation for the D-E-F-G middle bank.
    // EMPTY means that no passenger currently owns the local middle-bank event.
    final int[] middleBankReservedByPassenger = new int[ROWS];
    final AisleSide[] middleBankReservedByAisle = new AisleSide[ROWS];

    int middleBankReservationRequests = 0;
    int middleBankReservationGranted = 0;
    int middleBankReservationDenied = 0;
    int simultaneousMiddleBankConflicts = 0;

    public static void main(String[] args) {
        new WholeCabinHybridBoardingSimulation().run();
    }

    WholeCabinHybridBoardingSimulation() {
        for (int[] row : seats) Arrays.fill(row, EMPTY);
        Arrays.fill(middleBankReservedByPassenger, EMPTY);
    }

    void run() {
        printNotation();
        createManifest();
        buildRandomQueues();

        System.out.println("Passenger manifest size: " + passengers.size());
        System.out.println("Left aisle queue size: " + left.entryQueue.size());
        System.out.println("Right aisle queue size: " + right.entryQueue.size());
        System.out.println("Random seed: " + RANDOM_SEED + "\n");

        while (!allPassengersSeated() && currentTick < MAX_TICKS) {
            currentTick++;

            // GLOBAL TICK ORDER:
            // 1) advance local events; 2) detect new row events;
            // 3) move both aisles synchronously; 4) admit new passengers;
            // 5) update metrics and print state.
            advanceSeatEvent(left);
            advanceSeatEvent(right);
            detectAndStartSeatEventsWithMiddleBankArbitration();
            synchronousAisleMove(left);
            synchronousAisleMove(right);
            insertPassengerIfPossible(left);
            insertPassengerIfPossible(right);
            updateWaitingTicks();
            updateAisleMetrics(left);
            updateAisleMetrics(right);
            printTickSummary();
        }

        if (!allPassengersSeated()) {
            System.out.println("\nSIMULATION STOPPED: MAX_TICKS reached before completion.");
        }
        printFinalReport();
    }

    void printNotation() {
        System.out.println("============================================================");
        System.out.println("WHOLE-CABIN HYBRID BOARDING SIMULATION");
        System.out.println("============================================================");
        System.out.println("Aisle values: -1 = empty, 0+ = passenger ID");
        System.out.println("Seat values : -1 = empty, 0+ = seated passenger ID");
        System.out.println("Global movement = tick-driven");
        System.out.println("Local seating  = event-driven at tick boundaries");
        System.out.println("============================================================\n");
    }

    void createManifest() {
        List<int[]> coordinates = new ArrayList<>();
        for (int row = 0; row < ROWS; row++) {
            for (int seat = 0; seat < SEAT_LETTERS.length; seat++) {
                coordinates.add(new int[]{row, seat});
            }
        }
        Collections.shuffle(coordinates, random);
        int count = (int)Math.round(coordinates.size() * OCCUPANCY_RATE);

        for (int id = 0; id < count; id++) {
            int row = coordinates.get(id)[0];
            int seat = coordinates.get(id)[1];
            Passenger p = new Passenger(id, row, SEAT_LETTERS[seat], seat, chooseServingAisle(seat));
            passengers.put(id, p);
        }
    }

    AisleSide chooseServingAisle(int seatIndex) {
        // ABC -> LEFT, HIJ -> RIGHT, DEFG -> fixed random serving aisle.
        if (seatIndex <= 2) return AisleSide.LEFT;
        if (seatIndex >= 7) return AisleSide.RIGHT;
        return random.nextBoolean() ? AisleSide.LEFT : AisleSide.RIGHT;
    }

    void buildRandomQueues() {
        List<Integer> leftIds = new ArrayList<>();
        List<Integer> rightIds = new ArrayList<>();
        for (Passenger p : passengers.values()) {
            (p.servingAisle == AisleSide.LEFT ? leftIds : rightIds).add(p.id);
        }
        Collections.shuffle(leftIds, random);
        Collections.shuffle(rightIds, random);
        left.entryQueue.addAll(leftIds);
        right.entryQueue.addAll(rightIds);
    }

    void insertPassengerIfPossible(AisleContext c) {
        if (c.entryCooldown > 0) { c.entryCooldown--; return; }
        if (c.entryQueue.isEmpty() || c.aisle[0] != EMPTY) return;

        int id = c.entryQueue.removeFirst();
        Passenger p = passengers.get(id);
        c.aisle[0] = id;
        p.state = PassengerState.MOVING_IN_AISLE;
        p.aisleEntryTick = currentTick;
        c.entryCooldown = MIN_ENTRY_HEADWAY + random.nextInt(MAX_ENTRY_HEADWAY - MIN_ENTRY_HEADWAY + 1);

        System.out.println("Tick " + currentTick + " ENTRY " + c.side + ": " + p
                + " at tile 0 | next headway=" + c.entryCooldown);
    }

    void synchronousAisleMove(AisleContext c) {
        // First-attempt reservation rule: once a local seat event starts, this
        // aisle pauses until the event restores the row. This prevents another
        // passenger from entering a tile reserved for a yielding blocker.
        if (c.activeEvent != null) return;

        int[] snapshot = Arrays.copyOf(c.aisle, c.aisle.length);
        int[] next = Arrays.copyOf(snapshot, snapshot.length);
        for (int pos = snapshot.length - 1; pos >= 0; pos--) {
            int id = snapshot[pos];
            if (id == EMPTY) continue;
            Passenger p = passengers.get(id);
            if (p == null || p.state == PassengerState.IN_SEAT_EVENT) continue;

            if (pos == p.row || pos > p.row) {
                p.state = PassengerState.WAITING_AT_ROW;
                continue;
            }
            int nextPos = pos + 1;
            if (nextPos < snapshot.length && snapshot[nextPos] == EMPTY) {
                next[pos] = EMPTY;
                next[nextPos] = id;
                c.totalMoves++;
                if (nextPos == p.row) p.state = PassengerState.WAITING_AT_ROW;
            }
        }
        System.arraycopy(next, 0, c.aisle, 0, c.aisle.length);
    }

    void detectAndStartSeatEventsWithMiddleBankArbitration() {
        Passenger leftCandidate = findWaitingPassengerAtRow(left);
        Passenger rightCandidate = findWaitingPassengerAtRow(right);

        boolean simultaneousSameMiddleRow =
                leftCandidate != null &&
                rightCandidate != null &&
                isMiddleBankSeat(leftCandidate.seatIndex) &&
                isMiddleBankSeat(rightCandidate.seatIndex) &&
                leftCandidate.row == rightCandidate.row;

        if (simultaneousSameMiddleRow) {
            simultaneousMiddleBankConflicts++;

            // Deterministic tie-break for a true same-tick conflict:
            // the lower passenger ID receives the middle-bank reservation first.
            Passenger winner =
                    leftCandidate.id < rightCandidate.id ? leftCandidate : rightCandidate;
            AisleContext winnerContext =
                    winner.servingAisle == AisleSide.LEFT ? left : right;

            if (reserveMiddleBank(winner)) {
                startSeatEventForPassenger(winnerContext, winner);
            }
            return;
        }

        tryStartCandidate(left, leftCandidate);
        tryStartCandidate(right, rightCandidate);
    }

    void tryStartCandidate(AisleContext context, Passenger candidate) {
        if (candidate == null) {
            return;
        }

        if (isMiddleBankSeat(candidate.seatIndex) && !reserveMiddleBank(candidate)) {
            return;
        }

        if (!startSeatEventForPassenger(context, candidate)) {
            // Required yield tiles were not free. Release any reservation so the
            // request can be tried again on a later tick.
            if (isMiddleBankSeat(candidate.seatIndex)) {
                releaseMiddleBankReservation(candidate.row, candidate.id);
            }
        }
    }

    Passenger findWaitingPassengerAtRow(AisleContext context) {
        if (context.activeEvent != null) {
            return null;
        }

        for (int pos = 0; pos < context.aisle.length; pos++) {
            int id = context.aisle[pos];
            if (id == EMPTY) {
                continue;
            }

            Passenger passenger = passengers.get(id);
            if (passenger != null &&
                    pos == passenger.row &&
                    passenger.state == PassengerState.WAITING_AT_ROW) {
                return passenger;
            }
        }
        return null;
    }

    boolean isMiddleBankSeat(int seatIndex) {
        return seatIndex >= 3 && seatIndex <= 6;
    }

    boolean reserveMiddleBank(Passenger passenger) {
        middleBankReservationRequests++;

        int holder = middleBankReservedByPassenger[passenger.row];
        if (holder == EMPTY || holder == passenger.id) {
            middleBankReservedByPassenger[passenger.row] = passenger.id;
            middleBankReservedByAisle[passenger.row] = passenger.servingAisle;
            middleBankReservationGranted++;
            return true;
        }

        middleBankReservationDenied++;
        return false;
    }

    void releaseMiddleBankReservation(int row, int passengerId) {
        if (middleBankReservedByPassenger[row] == passengerId) {
            middleBankReservedByPassenger[row] = EMPTY;
            middleBankReservedByAisle[row] = null;
        }
    }

    boolean startSeatEventForPassenger(AisleContext context, Passenger passenger) {
        List<Integer> blockerSeats = findBlockingSeatIndices(passenger);
        List<Integer> blockerIds = new ArrayList<>();

        for (int seatIndex : blockerSeats) {
            int blockerId = seats[passenger.row][seatIndex];
            if (blockerId != EMPTY) {
                blockerIds.add(blockerId);
            }
        }

        // One standing/yielding person occupies one aisle tile.
        // All required temporary tiles must be free before the event starts.
        if (!hasRequiredYieldSpace(context, passenger.row, blockerIds.size())) {
            return false;
        }

        context.activeEvent =
                new SeatEvent(passenger, passenger.row, blockerIds, blockerSeats);
        context.seatEvents++;

        if (blockerIds.size() == 1) {
            context.singleBlockerEvents++;
        }
        if (blockerIds.size() > 1) {
            context.multipleBlockerEvents++;
        }

        passenger.state = PassengerState.IN_SEAT_EVENT;

        System.out.println("Tick " + currentTick + " EVENT START "
                + context.side + ": " + passenger
                + " blockers=" + blockerIds.size());

        return true;
    }

    void detectAndStartSeatEvent(AisleContext context) {
        Passenger candidate = findWaitingPassengerAtRow(context);
        tryStartCandidate(context, candidate);
    }


    boolean hasRequiredYieldSpace(AisleContext c, int rowIndex, int blockerCount) {
        for (int i = 0; i < blockerCount; i++) {
            int tile = rowIndex + (blockerCount - i);
            if (tile < 0 || tile >= c.aisle.length || c.aisle[tile] != EMPTY) {
                return false;
            }
        }
        return true;
    }

    List<Integer> findBlockingSeatIndices(Passenger p) {
        List<Integer> blockers = new ArrayList<>();
        // A B C | aisle | D E F G | aisle | H I J
        if (p.seatIndex <= 2) {
            for (int i = 2; i > p.seatIndex; i--) if (seats[p.row][i] != EMPTY) blockers.add(i);
        } else if (p.seatIndex >= 7) {
            for (int i = 7; i < p.seatIndex; i++) if (seats[p.row][i] != EMPTY) blockers.add(i);
        } else if (p.servingAisle == AisleSide.LEFT) {
            for (int i = 3; i < p.seatIndex; i++) if (seats[p.row][i] != EMPTY) blockers.add(i);
        } else {
            for (int i = 6; i > p.seatIndex; i--) if (seats[p.row][i] != EMPTY) blockers.add(i);
        }
        return blockers;
    }

    void advanceSeatEvent(AisleContext c) {
        SeatEvent e = c.activeEvent;
        if (e == null) return;

        switch (e.phase) {
            case BLOCKERS_STAND:
                System.out.println("Tick " + currentTick + " EVENT " + c.side
                        + ": blockers stand for " + e.target.seatName());
                e.phase = EventPhase.BLOCKERS_ENTER_AISLE;
                break;
            case BLOCKERS_ENTER_AISLE:
                if (placeBlockersInAisle(c, e)) {
                    System.out.println("Tick " + currentTick + " EVENT " + c.side
                            + ": blockers enter aisle for " + e.target.seatName());
                    e.phase = EventPhase.TARGET_SITS;
                }
                break;
            case TARGET_SITS:
                seatTargetPassenger(c, e);
                System.out.println("Tick " + currentTick + " EVENT " + c.side
                        + ": target seated at " + e.target.seatName());
                e.phase = EventPhase.BLOCKERS_RESEAT;
                break;
            case BLOCKERS_RESEAT:
                reseatBlockers(c, e);
                System.out.println("Tick " + currentTick + " EVENT " + c.side
                        + ": blockers reseated; flow restored at row " + (e.rowIndex + 1));
                e.phase = EventPhase.COMPLETE;
                break;
            case COMPLETE:
                if (isMiddleBankSeat(e.target.seatIndex)) {
                    releaseMiddleBankReservation(e.rowIndex, e.target.id);
                }
                c.activeEvent = null;
                break;
        }
    }

    boolean placeBlockersInAisle(AisleContext c, SeatEvent e) {
        int count = e.blockerPassengerIds.size();
        if (count == 0) return true;

        List<Integer> required = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            int tile = e.rowIndex + (count - i);
            if (tile < 0 || tile >= c.aisle.length) return false;
            required.add(tile);
        }
        for (int tile : required) if (c.aisle[tile] != EMPTY) return false;

        for (int i = 0; i < count; i++) {
            int blockerId = e.blockerPassengerIds.get(i);
            int blockerSeat = e.blockerSeatIndices.get(i);
            int tile = required.get(i);
            c.aisle[tile] = blockerId;
            e.blockerYieldTileByPassenger.put(blockerId, tile);
            seats[e.rowIndex][blockerSeat] = EMPTY;
            passengers.get(blockerId).state = PassengerState.IN_SEAT_EVENT;
            c.temporaryAisleReoccupations++;
        }
        return true;
    }

    void seatTargetPassenger(AisleContext c, SeatEvent e) {
        Passenger target = e.target;
        if (c.aisle[e.rowIndex] == target.id) c.aisle[e.rowIndex] = EMPTY;
        seats[target.row][target.seatIndex] = target.id;
        target.state = PassengerState.SEATED;
        target.seatedTick = currentTick;
    }

    void reseatBlockers(AisleContext c, SeatEvent e) {
        for (int i = e.blockerPassengerIds.size() - 1; i >= 0; i--) {
            int blockerId = e.blockerPassengerIds.get(i);
            int blockerSeat = e.blockerSeatIndices.get(i);
            Integer tile = e.blockerYieldTileByPassenger.get(blockerId);
            if (tile != null && c.aisle[tile] == blockerId) c.aisle[tile] = EMPTY;
            seats[e.rowIndex][blockerSeat] = blockerId;
            passengers.get(blockerId).state = PassengerState.SEATED;
        }
    }

    void updateWaitingTicks() {
        for (Passenger p : passengers.values()) {
            if (p.state == PassengerState.WAITING_TO_ENTER
                    || p.state == PassengerState.WAITING_AT_ROW
                    || p.state == PassengerState.IN_SEAT_EVENT) p.waitingTicks++;
        }
    }

    void updateAisleMetrics(AisleContext c) {
        c.maxOccupiedTiles = Math.max(c.maxOccupiedTiles, occupiedCount(c.aisle));
    }

    void printTickSummary() {
        if (VERBOSE_TICK_OUTPUT || currentTick <= 10 || currentTick % 25 == 0) {
            System.out.println("Tick " + currentTick + " | seated="
                    + countState(PassengerState.SEATED) + "/" + passengers.size()
                    + " | leftInAisle=" + occupiedCount(left.aisle)
                    + " | rightInAisle=" + occupiedCount(right.aisle)
                    + " | leftWaitingEntry=" + left.entryQueue.size()
                    + " | rightWaitingEntry=" + right.entryQueue.size());
            if (VERBOSE_TICK_OUTPUT) {
                System.out.println("  LEFT  " + Arrays.toString(left.aisle));
                System.out.println("  RIGHT " + Arrays.toString(right.aisle));
            }
        }
    }

    int occupiedCount(int[] aisle) {
        int n = 0;
        for (int v : aisle) if (v != EMPTY) n++;
        return n;
    }

    int countState(PassengerState state) {
        int n = 0;
        for (Passenger p : passengers.values()) if (p.state == state) n++;
        return n;
    }

    boolean allPassengersSeated() {
        return countState(PassengerState.SEATED) == passengers.size();
    }

    void printFinalReport() {
        System.out.println("\n============================================================");
        System.out.println("FINAL REPORT");
        System.out.println("============================================================");
        System.out.println("Completed ticks: " + currentTick);
        System.out.println("Passengers seated: " + countState(PassengerState.SEATED) + "/" + passengers.size());
        printAisleReport(left);
        printAisleReport(right);

        double totalWaiting = 0;
        int maxWaiting = -1;
        Passenger maxP = null;
        for (Passenger p : passengers.values()) {
            totalWaiting += p.waitingTicks;
            if (p.waitingTicks > maxWaiting) { maxWaiting = p.waitingTicks; maxP = p; }
        }
        System.out.printf(Locale.ROOT, "Average waiting ticks per passenger: %.2f%n",
                totalWaiting / passengers.size());
        if (maxP != null) System.out.println("Longest waiting passenger: " + maxP
                + " | waitingTicks=" + maxWaiting);
        System.out.println("Middle-bank reservation requests: " + middleBankReservationRequests);
        System.out.println("Middle-bank reservations granted: " + middleBankReservationGranted);
        System.out.println("Middle-bank reservations denied/waited: " + middleBankReservationDenied);
        System.out.println("Simultaneous opposite-aisle middle-bank conflicts: "
                + simultaneousMiddleBankConflicts);
        System.out.println("Final cabin occupancy by row:");
        printCabinSeats();
        System.out.println("============================================================");
    }

    void printAisleReport(AisleContext c) {
        System.out.println(c.side + " AISLE:");
        System.out.println("  total aisle moves = " + c.totalMoves);
        System.out.println("  max occupied aisle tiles = " + c.maxOccupiedTiles);
        System.out.println("  seat events = " + c.seatEvents);
        System.out.println("  single-blocker events = " + c.singleBlockerEvents);
        System.out.println("  multiple-blocker events = " + c.multipleBlockerEvents);
        System.out.println("  temporary aisle reoccupations = " + c.temporaryAisleReoccupations);
    }

    void printCabinSeats() {
        for (int row = 0; row < ROWS; row++) {
            StringBuilder sb = new StringBuilder();
            sb.append(String.format(Locale.ROOT, "Row %02d: ", row + 1));
            for (int seat = 0; seat < SEAT_LETTERS.length; seat++) {
                if (seat == 3 || seat == 7) sb.append("| ");
                int id = seats[row][seat];
                sb.append(SEAT_LETTERS[seat]).append(":")
                        .append(id == EMPTY ? "--" : "P" + id).append(" ");
            }
            System.out.println(sb);
        }
    }
}