CashFlowMinimizer.java

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Scanner;

public class CashFlowMinimizer {
    private static final Scanner SCANNER = new Scanner(System.in);

    public static void main(String[] args) {
        runMenuLoop();
    }

    private static void runMenuLoop() {
        while (true) {
            printMenu();
            String choice = SCANNER.nextLine().trim();

            switch (choice) {
                case "1":
                    runCustomInputFlow();
                    break;
                case "2":
                    runSampleScenario();
                    break;
                case "3":
                    System.out.println("Exiting Cash Flow Minimizer.");
                    return;
                default:
                    System.out.println("Invalid choice. Please enter 1, 2, or 3.");
            }
        }
    }

    private static void printMenu() {
        System.out.println();
        System.out.println("=== Cash Flow Minimizer ===");
        System.out.println("1. Run");
        System.out.println("2. Test sample");
        System.out.println("3. Exit");
        System.out.print("Choose an option: ");
    }

    private static void runCustomInputFlow() {
        System.out.println();
        System.out.print("Enter transaction count (format: \"Num txns N\" or just \"N\"): ");
        int transactionCount = readValidTransactionCount();
        List<Transaction> transactions = readTransactions(transactionCount);
        CashFlowResult result = minimizeCashFlow(transactions);
        printResult(result);
        promptCsvExport(result);
    }

    private static void runSampleScenario() {
        System.out.println();
        System.out.println("Running sample scenario:");
        System.out.println("Alice -> Bob 100");
        System.out.println("Bob -> Charlie 50");
        System.out.println("Charlie -> Alice 50");

        List<Transaction> sampleTransactions = Arrays.asList(
                new Transaction("Alice", "Bob", 100),
                new Transaction("Bob", "Charlie", 50),
                new Transaction("Charlie", "Alice", 50)
        );

        CashFlowResult result = minimizeCashFlow(sampleTransactions);
        printResult(result);
        System.out.println("Expected net balances: Alice:-50 Bob:50 Charlie:0");
        System.out.println("Expected payment: Alice pays Bob 50 (1 transaction)");
        promptCsvExport(result);
    }

    private static int readValidTransactionCount() {
        while (true) {
            String line = SCANNER.nextLine();
            Integer parsedCount = parseTransactionCount(line);

            if (parsedCount != null) {
                return parsedCount;
            }

            System.out.print("Invalid count. Enter \"Num txns N\" or \"N\" with N >= 0: ");
        }
    }

    private static List<Transaction> readTransactions(int transactionCount) {
        ArrayList<Transaction> transactions = new ArrayList<>();
        for (int i = 1; i <= transactionCount; i++) {
            while (true) {
                System.out.print("Transaction " + i + " (Payer Payee Amount): ");
                String line = SCANNER.nextLine();
                try {
                    transactions.add(parseTransactionLine(line));
                    break;
                } catch (IllegalArgumentException ex) {
                    System.out.println("Invalid transaction: " + ex.getMessage());
                }
            }
        }
        return transactions;
    }

    public static Integer parseTransactionCount(String input) {
        if (input == null) {
            return null;
        }

        String trimmed = input.trim();
        if (trimmed.isEmpty()) {
            return null;
        }

        String[] tokens = trimmed.split("\\s+");
        for (int i = tokens.length - 1; i >= 0; i--) {
            try {
                int value = Integer.parseInt(tokens[i]);
                if (value >= 0) {
                    return value;
                }
            } catch (NumberFormatException ignored) {
                // Continue searching for an integer token.
            }
        }
        return null;
    }

    public static Transaction parseTransactionLine(String line) {
        if (line == null || line.trim().isEmpty()) {
            throw new IllegalArgumentException("Input cannot be empty.");
        }

        String[] parts = line.trim().split("\\s+");
        if (parts.length != 3) {
            throw new IllegalArgumentException("Use exactly: Payer Payee Amount");
        }

        String payer = parts[0];
        String payee = parts[1];
        if (payer.equals(payee)) {
            throw new IllegalArgumentException("Payer and payee must be different.");
        }

        int amount;
        try {
            amount = Integer.parseInt(parts[2]);
        } catch (NumberFormatException ex) {
            throw new IllegalArgumentException("Amount must be an integer.");
        }

        if (amount <= 0) {
            throw new IllegalArgumentException("Amount must be greater than zero.");
        }

        return new Transaction(payer, payee, amount);
    }

    public static HashMap<String, Integer> buildBalances(List<Transaction> transactions) {
        HashMap<String, Integer> balances = new HashMap<>();

        if (transactions == null) {
            return balances;
        }

        for (Transaction transaction : transactions) {
            if (transaction == null) {
                continue;
            }

            // Net flow model: payer owes money, payee receives money.
            balances.put(
                    transaction.getPayer(),
                    balances.getOrDefault(transaction.getPayer(), 0) - transaction.getAmount()
            );
            balances.put(
                    transaction.getPayee(),
                    balances.getOrDefault(transaction.getPayee(), 0) + transaction.getAmount()
            );
        }

        return balances;
    }

    public static CashFlowResult minimizeCashFlow(List<Transaction> transactions) {
        HashMap<String, Integer> balances = buildBalances(transactions);
        ArrayList<Person> debtors = new ArrayList<>();
        ArrayList<Person> creditors = new ArrayList<>();

        for (Map.Entry<String, Integer> entry : balances.entrySet()) {
            String name = entry.getKey();
            int balance = entry.getValue();

            if (balance < 0) {
                debtors.add(new Person(name, Math.abs(balance)));
            } else if (balance > 0) {
                creditors.add(new Person(name, balance));
            }
        }

        Comparator<Person> byAmountThenName = Comparator
                .comparingInt(Person::getBalance)
                .thenComparing(Person::getName);

        // Lists are sorted ascending, then processed from the end (largest unsettled first).
        debtors.sort(byAmountThenName);
        creditors.sort(byAmountThenName);

        ArrayList<String> payments = settleDebtsGreedy(debtors, creditors);
        return new CashFlowResult(balances, payments);
    }

    private static ArrayList<String> settleDebtsGreedy(ArrayList<Person> debtors, ArrayList<Person> creditors) {
        ArrayList<String> payments = new ArrayList<>();
        int debtorPointer = debtors.size() - 1;
        int creditorPointer = creditors.size() - 1;

        while (debtorPointer >= 0 && creditorPointer >= 0) {
            Person debtor = debtors.get(debtorPointer);
            Person creditor = creditors.get(creditorPointer);

            // Greedy settlement: move as much as possible in one transfer.
            int payAmount = Math.min(debtor.getBalance(), creditor.getBalance());
            payments.add(debtor.getName() + " pays " + creditor.getName() + " " + payAmount);

            debtor.addToBalance(-payAmount);
            creditor.addToBalance(-payAmount);

            if (debtor.getBalance() == 0) {
                debtorPointer--;
            }
            if (creditor.getBalance() == 0) {
                creditorPointer--;
            }
        }

        return payments;
    }

    private static void printResult(CashFlowResult result) {
        HashMap<String, Integer> balances = result.getBalances();
        ArrayList<String> participants = new ArrayList<>(balances.keySet());
        Collections.sort(participants);

        System.out.println();
        System.out.println("Net Balances:");
        if (participants.isEmpty()) {
            System.out.println("No participants.");
        } else {
            for (String name : participants) {
                System.out.println(name + ": " + balances.get(name));
            }
        }

        ArrayList<String> payments = result.getPayments();
        System.out.println();
        System.out.println("Optimized Payments:");
        if (payments.isEmpty()) {
            System.out.println("No payments needed.");
        } else {
            for (String payment : payments) {
                System.out.println(payment);
            }
        }

        System.out.println("Total transactions after minimization: " + payments.size());
    }

    private static void promptCsvExport(CashFlowResult result) {
        ArrayList<String> payments = result.getPayments();
        if (payments.isEmpty()) {
            return;
        }

        System.out.print("Save optimized payments to CSV? (y/n): ");
        String response = SCANNER.nextLine().trim().toLowerCase(Locale.ROOT);
        if (!response.equals("y") && !response.equals("yes")) {
            return;
        }

        System.out.print("CSV file name (default: payments.csv): ");
        String fileName = SCANNER.nextLine().trim();
        if (fileName.isEmpty()) {
            fileName = "payments.csv";
        }

        try {
            savePaymentsToCsv(payments, fileName);
            System.out.println("CSV saved to " + fileName);
        } catch (IOException ex) {
            System.out.println("Failed to save CSV: " + ex.getMessage());
        }
    }

    public static void savePaymentsToCsv(List<String> payments, String fileName) throws IOException {
        try (BufferedWriter writer = new BufferedWriter(new FileWriter(fileName))) {
            writer.write("Debtor,Creditor,Amount");
            writer.newLine();

            for (String payment : payments) {
                String[] csvParts = parsePaymentLine(payment);
                writer.write(csvParts[0] + "," + csvParts[1] + "," + csvParts[2]);
                writer.newLine();
            }
        }
    }

    private static String[] parsePaymentLine(String payment) {
        String[] tokens = payment.trim().split("\\s+");
        if (tokens.length != 4 || !"pays".equals(tokens[1])) {
            throw new IllegalArgumentException("Unexpected payment format: " + payment);
        }

        return new String[]{tokens[0], tokens[2], tokens[3]};
    }

    public static final class Transaction {
        private final String payer;
        private final String payee;
        private final int amount;

        public Transaction(String payer, String payee, int amount) {
            if (payer == null || payer.trim().isEmpty()) {
                throw new IllegalArgumentException("Payer cannot be empty.");
            }
            if (payee == null || payee.trim().isEmpty()) {
                throw new IllegalArgumentException("Payee cannot be empty.");
            }
            if (payer.equals(payee)) {
                throw new IllegalArgumentException("Payer and payee must be different.");
            }
            if (amount <= 0) {
                throw new IllegalArgumentException("Amount must be greater than zero.");
            }

            this.payer = payer;
            this.payee = payee;
            this.amount = amount;
        }

        public String getPayer() {
            return payer;
        }

        public String getPayee() {
            return payee;
        }

        public int getAmount() {
            return amount;
        }

        @Override
        public String toString() {
            return payer + " -> " + payee + " " + amount;
        }
    }

    public static final class CashFlowResult {
        private final HashMap<String, Integer> balances;
        private final ArrayList<String> payments;

        public CashFlowResult(Map<String, Integer> balances, List<String> payments) {
            this.balances = new HashMap<>();
            this.payments = new ArrayList<>();

            if (balances != null) {
                this.balances.putAll(balances);
            }
            if (payments != null) {
                this.payments.addAll(payments);
            }
        }

        public HashMap<String, Integer> getBalances() {
            return new HashMap<>(balances);
        }

        public ArrayList<String> getPayments() {
            return new ArrayList<>(payments);
        }
    }
}