Splitwise / Expense Sharing

1import java.math.BigInteger;
2import java.util.*;
3/** One-currency in-memory obligation ledger. This records debts, not real money transfers. */
4public final class Solution {
5    private Solution() {}
6    public record Entry(String id,Map<String,Long> delta,String reverses) { public Entry { delta=Map.copyOf(delta); } }
7    private record Command(Object fingerprint,String entryId){}
8    private record ExpenseFingerprint(String payer,long amount,Map<String,Long> shares){public ExpenseFingerprint{shares=Map.copyOf(shares);}}
9    private record SettlementFingerprint(String debtor,String creditor,long amount){}
10    private record ReversalFingerprint(String entryId){}
11    public static Map<String,Long> split(long amount,Map<String,Long> weights){
12        if(amount<=0||weights.isEmpty()||weights.values().stream().anyMatch(v->v==null||v<=0))throw new IllegalArgumentException("split");
13        BigInteger sum=weights.values().stream().map(BigInteger::valueOf).reduce(BigInteger.ZERO,BigInteger::add);
14        var shares=new TreeMap<String,Long>();long allocated=0;
15        for(var e:new TreeMap<>(weights).entrySet()){
16            if(e.getKey()==null||e.getKey().isBlank())throw new IllegalArgumentException("participant");
17            long share=BigInteger.valueOf(amount).multiply(BigInteger.valueOf(e.getValue())).divide(sum).longValueExact();shares.put(e.getKey(),share);allocated=Math.addExact(allocated,share);
18        }
19        // Each floor loses less than one unit: leftover is strictly less than participant count.
20        long remainder=amount-allocated;for(String id:shares.keySet()){if(remainder--<=0)break;shares.put(id,shares.get(id)+1);}
21        return Map.copyOf(shares);
22    }
23    public static final class Ledger {
24        private final Set<String> members;
25        private final Map<String,Long> balances=new TreeMap<>();
26        private final Map<String,Entry> entries=new LinkedHashMap<>();
27        private final Map<String,Command> commands=new HashMap<>();
28        private final Map<String,String> reversed=new HashMap<>();
29        private long sequence;
30        public Ledger(Set<String> members){if(members.isEmpty()||members.stream().anyMatch(s->s==null||s.isBlank()))throw new IllegalArgumentException("members");this.members=Set.copyOf(members);members.forEach(m->balances.put(m,0L));}
31        private void member(String id){if(!members.contains(id))throw new IllegalArgumentException("member");}
32        private static String key(String value){if(value==null||value.isBlank())throw new IllegalArgumentException("key");return value;}
33        private Entry apply(String commandKey,Object fingerprint,Map<String,Long> delta,String reverseId){
34            key(commandKey);var prior=commands.get(commandKey);if(prior!=null){if(!prior.fingerprint().equals(fingerprint))throw new IllegalArgumentException("key reused");return entries.get(prior.entryId());}
35            BigInteger sum=delta.values().stream().map(BigInteger::valueOf).reduce(BigInteger.ZERO,BigInteger::add);if(sum.signum()!=0)throw new IllegalArgumentException("unbalanced");
36            var next=new TreeMap<>(balances);delta.forEach((m,value)->{member(m);next.put(m,Math.addExact(next.get(m),value));});
37            String id="E"+(++sequence);var entry=new Entry(id,delta,reverseId);balances.clear();balances.putAll(next);entries.put(id,entry);commands.put(commandKey,new Command(fingerprint,id));return entry;
38        }
39        public synchronized Entry expense(String payer,long amount,Map<String,Long> exactShares,String commandKey){
40            member(payer);if(amount<=0||exactShares.isEmpty()||exactShares.values().stream().anyMatch(v->v==null||v<0))throw new IllegalArgumentException("shares");
41            exactShares.keySet().forEach(this::member);
42            BigInteger sum=exactShares.values().stream().map(BigInteger::valueOf).reduce(BigInteger.ZERO,BigInteger::add);if(!sum.equals(BigInteger.valueOf(amount)))throw new IllegalArgumentException("sum");
43            var shares=new TreeMap<>(exactShares);var delta=new TreeMap<String,Long>();shares.forEach((m,v)->delta.put(m,-v));delta.merge(payer,amount,Math::addExact);
44            Object fingerprint=new ExpenseFingerprint(payer,amount,shares);
45            return apply(commandKey,fingerprint,delta,"");
46        }
47        public synchronized Entry settle(String debtor,String creditor,long amount,String commandKey){
48            member(debtor);member(creditor);if(debtor.equals(creditor)||amount<=0)throw new IllegalArgumentException("settlement");
49            Object fingerprint=new SettlementFingerprint(debtor,creditor,amount);
50            // Resolve repeats before balance validation, since successful settlement changes eligibility.
51            var prior=commands.get(key(commandKey));if(prior!=null){if(!prior.fingerprint().equals(fingerprint))throw new IllegalArgumentException("key reused");return entries.get(prior.entryId());}
52            if(balances.get(debtor)>=0||balances.get(creditor)<=0||BigInteger.valueOf(balances.get(debtor)).negate().compareTo(BigInteger.valueOf(amount))<0||balances.get(creditor)<amount)throw new IllegalStateException("over settlement");
53            return apply(commandKey,fingerprint,Map.of(debtor,amount,creditor,-amount),"");
54        }
55        public synchronized Entry reverse(String entryId,String commandKey){
56            var original=entries.get(entryId);if(original==null||!original.reverses().isEmpty())throw new IllegalArgumentException("original entry");
57            Object fingerprint=new ReversalFingerprint(entryId);var prior=commands.get(key(commandKey));if(prior!=null){if(!prior.fingerprint().equals(fingerprint))throw new IllegalArgumentException("key reused");return entries.get(prior.entryId());}
58            if(reversed.containsKey(entryId))throw new IllegalStateException("already reversed");
59            var inverse=new TreeMap<String,Long>();original.delta().forEach((m,v)->inverse.put(m,Math.negateExact(v)));
60            var result=apply(commandKey,fingerprint,inverse,entryId);reversed.put(entryId,result.id());return result;
61        }
62        public synchronized Map<String,Long> balances(){return Map.copyOf(balances);}
63        public synchronized List<Entry> entries(){return List.copyOf(entries.values());}
64        public synchronized Map<String,Long> rebuild(){var result=new TreeMap<String,Long>();members.forEach(m->result.put(m,0L));for(var e:entries.values())e.delta().forEach((m,v)->result.put(m,Math.addExact(result.get(m),v)));return Map.copyOf(result);}
65    }
66}
67