Splitwise

import java.util.Locale;

public record Money(long cents) {
  public Money {
      if (cents < 0) {
          throw new IllegalArgumentException("Money cannot be negative");
      }
  }

  public static Money ofCents(long cents) {
      return new Money(cents);
  }

  public String format() {
      return String.format(Locale.ROOT, "$%.2f", cents / 100.0);
  }
}

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

public enum SplitType {
  EQUAL,
  EXACT,
  PERCENTAGE
}

import java.util.Map;

public record Expense(
      String id,
      String description,
      String payerId,
      Money total,
      SplitType splitType,
      Map<String, Money> shares
) {
  public Expense {
      if (id == null || id.isBlank()
              || description == null || description.isBlank()
              || payerId == null || payerId.isBlank()
              || total == null || total.cents() == 0
              || splitType == null || shares == null || shares.isEmpty()) {
          throw new IllegalArgumentException("Valid expense fields are required");
      }
      shares = Map.copyOf(shares);
  }
}

public record Debt(
      String debtorId,
      String creditorId,
      Money amount
) {
  public Debt {
      if (debtorId == null || debtorId.isBlank()
              || creditorId == null || creditorId.isBlank()
              || debtorId.equals(creditorId)
              || amount == null || amount.cents() == 0) {
          throw new IllegalArgumentException("Valid debt fields are required");
      }
  }
}

import java.util.List;
import java.util.Map;

public interface SplitStrategy {
  Map<String, Money> calculate(
          Money total,
          List<String> participantIds,
          Map<String, Long> values
  );
}

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

public final class EqualSplitStrategy implements SplitStrategy {
  @Override
  public Map<String, Money> calculate(
          Money total,
          List<String> participantIds,
          Map<String, Long> ignored
  ) {
      List<String> ordered = participantIds.stream().sorted().toList();
      if (ordered.isEmpty()) {
          throw new IllegalArgumentException("Participants are required");
      }

      long base = total.cents() / ordered.size();
      long remainder = total.cents() % ordered.size();
      Map<String, Money> shares = new LinkedHashMap<>();
      for (int index = 0; index < ordered.size(); index++) {
          long cents = base + (index < remainder ? 1 : 0);
          if (cents == 0) {
              throw new IllegalArgumentException("Every share must be positive");
          }
          shares.put(ordered.get(index), Money.ofCents(cents));
      }
      return Map.copyOf(shares);
  }
}

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

public final class ExactSplitStrategy implements SplitStrategy {
  @Override
  public Map<String, Money> calculate(
          Money total,
          List<String> participantIds,
          Map<String, Long> values
  ) {
      Set<String> expected = Set.copyOf(participantIds);
      if (expected.isEmpty() || expected.size() != participantIds.size()
              || values == null || !values.keySet().equals(expected)) {
          throw new IllegalArgumentException("One exact value per participant is required");
      }

      long sum = 0;
      Map<String, Money> shares = new LinkedHashMap<>();
      for (String id : expected.stream().sorted().toList()) {
          long cents = values.get(id);
          if (cents <= 0) {
              throw new IllegalArgumentException("Exact shares must be positive");
          }
          sum = Math.addExact(sum, cents);
          shares.put(id, Money.ofCents(cents));
      }
      if (sum != total.cents()) {
          throw new IllegalArgumentException("Exact shares must equal total");
      }
      return Map.copyOf(shares);
  }
}

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

public final class PercentageSplitStrategy implements SplitStrategy {
  private record Fraction(String userId, long remainder) {}

  @Override
  public Map<String, Money> calculate(
          Money total,
          List<String> participantIds,
          Map<String, Long> basisPointsByUser
  ) {
      Set<String> expected = Set.copyOf(participantIds);
      if (expected.isEmpty() || expected.size() != participantIds.size()
              || basisPointsByUser == null
              || !basisPointsByUser.keySet().equals(expected)) {
          throw new IllegalArgumentException("One percentage per participant is required");
      }

      long basisPointSum = 0;
      long allocated = 0;
      Map<String, Long> centsByUser = new LinkedHashMap<>();
      List<Fraction> fractions = new ArrayList<>();

      for (String id : expected.stream().sorted().toList()) {
          long basisPoints = basisPointsByUser.get(id);
          if (basisPoints <= 0) {
              throw new IllegalArgumentException("Percentages must be positive");
          }
          basisPointSum = Math.addExact(basisPointSum, basisPoints);
          long numerator = Math.multiplyExact(total.cents(), basisPoints);
          long cents = numerator / 10_000;
          centsByUser.put(id, cents);
          allocated += cents;
          fractions.add(new Fraction(id, numerator % 10_000));
      }
      if (basisPointSum != 10_000) {
          throw new IllegalArgumentException("Percentages must total 100%");
      }

      fractions.sort(Comparator.comparingLong(Fraction::remainder)
              .reversed().thenComparing(Fraction::userId));
      long leftover = total.cents() - allocated;
      for (int index = 0; index < leftover; index++) {
          String id = fractions.get(index).userId();
          centsByUser.put(id, centsByUser.get(id) + 1);
      }

      Map<String, Money> shares = new LinkedHashMap<>();
      for (String id : expected.stream().sorted().toList()) {
          long cents = centsByUser.get(id);
          if (cents == 0) {
              throw new IllegalArgumentException("Every share must be positive");
          }
          shares.put(id, Money.ofCents(cents));
      }
      return Map.copyOf(shares);
  }
}

public enum ExpenseStatus {
  RECORDED,
  INVALID_INPUT,
  UNKNOWN_USER,
  INVALID_SPLIT
}

import java.util.Optional;

public record RecordExpenseResult(
      ExpenseStatus status,
      Optional<Expense> expense
) {
  public RecordExpenseResult {
      if (status == null || expense == null) {
          throw new IllegalArgumentException("Result fields are required");
      }
  }

  public static RecordExpenseResult accepted(Expense expense) {
      return new RecordExpenseResult(
              ExpenseStatus.RECORDED,
              Optional.of(expense)
      );
  }

  public static RecordExpenseResult rejected(ExpenseStatus status) {
      return new RecordExpenseResult(status, Optional.empty());
  }
}

public enum SettlementStatus {
  SETTLED,
  INVALID_AMOUNT,
  NO_MATCHING_DEBT,
  AMOUNT_EXCEEDS_DEBT
}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public final class BalanceSheet {
  private record PairKey(String first, String second) {
      static PairKey of(String left, String right) {
          return left.compareTo(right) < 0
                  ? new PairKey(left, right)
                  : new PairKey(right, left);
      }
  }

  private final Map<PairKey, Long> signedByPair = new HashMap<>();

  public void addDebt(String debtorId, String creditorId, Money amount) {
      if (debtorId == null || creditorId == null || amount == null
              || debtorId.equals(creditorId) || amount.cents() == 0) {
          return;
      }
      PairKey key = PairKey.of(debtorId, creditorId);
      long delta = debtorId.equals(key.first())
              ? amount.cents()
              : -amount.cents();
      long combined = Math.addExact(signedByPair.getOrDefault(key, 0L), delta);
      if (combined == 0) {
          signedByPair.remove(key);
      } else {
          signedByPair.put(key, combined);
      }
  }

  public SettlementStatus settle(
          String debtorId,
          String creditorId,
          Money amount
  ) {
      if (amount == null || amount.cents() == 0
              || debtorId == null || creditorId == null
              || debtorId.equals(creditorId)) {
          return SettlementStatus.INVALID_AMOUNT;
      }
      Debt current = balances().stream()
              .filter(debt -> debt.debtorId().equals(debtorId)
                      && debt.creditorId().equals(creditorId))
              .findFirst()
              .orElse(null);
      if (current == null) {
          return SettlementStatus.NO_MATCHING_DEBT;
      }
      if (amount.cents() > current.amount().cents()) {
          return SettlementStatus.AMOUNT_EXCEEDS_DEBT;
      }
      addDebt(creditorId, debtorId, amount);
      return SettlementStatus.SETTLED;
  }

  public List<Debt> balances() {
      List<Debt> result = new ArrayList<>();
      for (Map.Entry<PairKey, Long> entry : signedByPair.entrySet()) {
          PairKey key = entry.getKey();
          long signed = entry.getValue();
          if (signed > 0) {
              result.add(new Debt(key.first(), key.second(), Money.ofCents(signed)));
          } else {
              result.add(new Debt(key.second(), key.first(), Money.ofCents(-signed)));
          }
      }
      result.sort(Comparator.comparing(Debt::debtorId)
              .thenComparing(Debt::creditorId));
      return List.copyOf(result);
  }
}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public final class DebtSimplifier {
  private record Account(String userId, long cents) {}

  public List<Debt> simplify(List<Debt> balances) {
      Map<String, Long> net = new HashMap<>();
      for (Debt debt : balances) {
          net.merge(debt.debtorId(), -debt.amount().cents(), Long::sum);
          net.merge(debt.creditorId(), debt.amount().cents(), Long::sum);
      }

      Comparator<Account> largestFirst = Comparator
              .comparingLong(Account::cents).reversed()
              .thenComparing(Account::userId);
      PriorityQueue<Account> debtors = new PriorityQueue<>(largestFirst);
      PriorityQueue<Account> creditors = new PriorityQueue<>(largestFirst);
      for (Map.Entry<String, Long> entry : net.entrySet()) {
          if (entry.getValue() < 0) {
              debtors.add(new Account(entry.getKey(), -entry.getValue()));
          } else if (entry.getValue() > 0) {
              creditors.add(new Account(entry.getKey(), entry.getValue()));
          }
      }

      List<Debt> suggestions = new ArrayList<>();
      while (!debtors.isEmpty() && !creditors.isEmpty()) {
          Account debtor = debtors.remove();
          Account creditor = creditors.remove();
          long transfer = Math.min(debtor.cents(), creditor.cents());
          suggestions.add(new Debt(
                  debtor.userId(),
                  creditor.userId(),
                  Money.ofCents(transfer)
          ));
          if (debtor.cents() > transfer) {
              debtors.add(new Account(debtor.userId(), debtor.cents() - transfer));
          }
          if (creditor.cents() > transfer) {
              creditors.add(new Account(creditor.userId(), creditor.cents() - transfer));
          }
      }
      return List.copyOf(suggestions);
  }
}

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

public final class ExpenseService {
  private final Map<String, User> usersById = new LinkedHashMap<>();
  private final Map<SplitType, SplitStrategy> strategies = new EnumMap<>(SplitType.class);
  private final List<Expense> expenses = new ArrayList<>();
  private final BalanceSheet balanceSheet = new BalanceSheet();
  private final DebtSimplifier simplifier = new DebtSimplifier();
  private int nextExpenseNumber = 1;

  public ExpenseService(List<User> users) {
      if (users == null || users.isEmpty()) {
          throw new IllegalArgumentException("Users are required");
      }
      for (User user : users) {
          if (usersById.putIfAbsent(user.id(), user) != null) {
              throw new IllegalArgumentException("Duplicate user: " + user.id());
          }
      }
      strategies.put(SplitType.EQUAL, new EqualSplitStrategy());
      strategies.put(SplitType.EXACT, new ExactSplitStrategy());
      strategies.put(SplitType.PERCENTAGE, new PercentageSplitStrategy());
  }

  public RecordExpenseResult recordExpense(
          String description,
          String payerId,
          Money total,
          List<String> participantIds,
          SplitType splitType,
          Map<String, Long> values
  ) {
      if (description == null || description.isBlank()
              || total == null || total.cents() == 0
              || participantIds == null || participantIds.isEmpty()
              || splitType == null || values == null
              || Set.copyOf(participantIds).size() != participantIds.size()) {
          return RecordExpenseResult.rejected(ExpenseStatus.INVALID_INPUT);
      }
      if (!usersById.containsKey(payerId)
              || participantIds.stream().anyMatch(id -> !usersById.containsKey(id))) {
          return RecordExpenseResult.rejected(ExpenseStatus.UNKNOWN_USER);
      }

      Map<String, Money> shares;
      try {
          shares = strategies.get(splitType)
                  .calculate(total, List.copyOf(participantIds), Map.copyOf(values));
      } catch (IllegalArgumentException | ArithmeticException error) {
          return RecordExpenseResult.rejected(ExpenseStatus.INVALID_SPLIT);
      }

      Expense expense = new Expense(
              "E" + nextExpenseNumber,
              description,
              payerId,
              total,
              splitType,
              shares
      );
      nextExpenseNumber++;
      expenses.add(expense);
      for (Map.Entry<String, Money> share : shares.entrySet()) {
          if (!share.getKey().equals(payerId)) {
              balanceSheet.addDebt(share.getKey(), payerId, share.getValue());
          }
      }
      return RecordExpenseResult.accepted(expense);
  }

  public SettlementStatus settle(
          String debtorId,
          String creditorId,
          Money amount
  ) {
      return balanceSheet.settle(debtorId, creditorId, amount);
  }

  public List<Expense> expenses() {
      return List.copyOf(expenses);
  }

  public List<Debt> balances() {
      return balanceSheet.balances();
  }

  public List<Debt> simplifiedDebts() {
      return simplifier.simplify(balanceSheet.balances());
  }
}

import java.util.List;
import java.util.Map;

public final class SplitwiseDemo {
  public static void main(String[] args) {
      ExpenseService service = new ExpenseService(List.of(
              new User("AVA", "Ava"),
              new User("BEN", "Ben"),
              new User("CARA", "Cara")
      ));

      RecordExpenseResult dinner = service.recordExpense(
              "Dinner", "AVA", Money.ofCents(12_000),
              List.of("AVA", "BEN", "CARA"),
              SplitType.EQUAL, Map.of()
      );
      System.out.println("dinner: " + dinner.status());

      RecordExpenseResult taxi = service.recordExpense(
              "Taxi", "BEN", Money.ofCents(6_000),
              List.of("BEN", "CARA"),
              SplitType.EQUAL, Map.of()
      );
      System.out.println("taxi: " + taxi.status());

      System.out.println("pairwise:");
      service.balances().forEach(debt -> System.out.println(
              debt.debtorId() + " owes " + debt.creditorId()
                      + " " + debt.amount().format()
      ));

      System.out.println("simplified:");
      service.simplifiedDebts().forEach(debt -> System.out.println(
              debt.debtorId() + " pays " + debt.creditorId()
                      + " " + debt.amount().format()
      ));

      int debtCountBefore = service.balances().size();
      RecordExpenseResult invalid = service.recordExpense(
              "Groceries", "CARA", Money.ofCents(9_000),
              List.of("AVA", "BEN", "CARA"),
              SplitType.EXACT,
              Map.of("AVA", 5_000L, "BEN", 3_000L, "CARA", 500L)
      );
      System.out.println("invalid exact: " + invalid.status());
      System.out.println("unchanged debts: "
              + (debtCountBefore == service.balances().size()));

      System.out.println("settlement: " + service.settle(
              "CARA", "BEN", Money.ofCents(3_000)
      ));
      System.out.println("remaining direct debts: "
              + service.balances().size());
  }
}