import java.util.*;

/** The three small algorithms that sit at the centre of project ideas 1, 2 and 6. */
public class ProjectIdeasCores {

    // BEGIN base62
    static final String ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    static String encode(long id) {
        if (id == 0) return "0";
        StringBuilder sb = new StringBuilder();
        for (long n = id; n > 0; n /= 62) sb.append(ALPHABET.charAt((int) (n % 62)));
        return sb.reverse().toString();
    }

    static long decode(String code) {
        long n = 0;
        for (char c : code.toCharArray()) n = n * 62 + ALPHABET.indexOf(c);
        return n;
    }
    // END base62

    // BEGIN bucket
    /** Token bucket: holds up to `capacity` tokens and refills `perSecond` tokens each second. */
    static class TokenBucket {
        private final double capacity, perSecond;
        private double tokens;
        private long lastNanos;

        TokenBucket(double capacity, double perSecond, long nowNanos) {
            this.capacity = capacity; this.perSecond = perSecond; this.tokens = capacity; this.lastNanos = nowNanos;
        }

        synchronized boolean tryAcquire(long nowNanos) {
            tokens = Math.min(capacity, tokens + (nowNanos - lastNanos) / 1e9 * perSecond);   // refill for the elapsed time
            lastNanos = nowNanos;
            if (tokens >= 1) { tokens -= 1; return true; }
            return false;
        }
    }
    // END bucket

    // BEGIN settle
    record Transfer(String from, String to, long amount) {}

    /** Turns "who paid what" balances into the fewest transfers the greedy method finds. */
    static List<Transfer> settle(Map<String, Long> balance) {          // positive = is owed money, negative = owes money
        PriorityQueue<Map.Entry<String, Long>> creditors = new PriorityQueue<>((x, y) -> Long.compare(y.getValue(), x.getValue()));
        PriorityQueue<Map.Entry<String, Long>> debtors = new PriorityQueue<>(Comparator.comparingLong(Map.Entry::getValue));
        for (var e : balance.entrySet()) {
            if (e.getValue() > 0) creditors.add(new AbstractMap.SimpleEntry<>(e));
            else if (e.getValue() < 0) debtors.add(new AbstractMap.SimpleEntry<>(e));
        }
        List<Transfer> out = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            var c = creditors.poll(); var d = debtors.poll();
            long pay = Math.min(c.getValue(), -d.getValue());
            out.add(new Transfer(d.getKey(), c.getKey(), pay));
            c.setValue(c.getValue() - pay); d.setValue(d.getValue() + pay);
            if (c.getValue() > 0) creditors.add(c);
            if (d.getValue() < 0) debtors.add(d);
        }
        return out;
    }
    // END settle

    public static void main(String[] args) {
        System.out.println("-- 1. URL shortener: base62 ids --");
        for (long id : new long[]{0, 61, 62, 125, 1_000_000, 3_521_614_606_207L}) System.out.println(id + " -> " + encode(id) + " -> " + decode(encode(id)));
        System.out.println("7 characters cover 62^7 = " + (long) Math.pow(62, 7) + " ids");

        System.out.println("-- 6. Rate limiter: token bucket, capacity 3, 1 token per second --");
        TokenBucket b = new TokenBucket(3, 1, 0);
        long[] atMillis = {0, 0, 0, 0, 500, 1000, 1000, 5000};
        for (long ms : atMillis) System.out.println("t=" + ms + "ms -> " + (b.tryAcquire(ms * 1_000_000L) ? "allowed" : "rejected (429)"));

        System.out.println("-- 2. Expense splitter: settle up --");
        Map<String, Long> bal = new LinkedHashMap<>();
        bal.put("Asha", 3000L); bal.put("Ravi", -1000L); bal.put("Meera", -2500L); bal.put("Kabir", 500L);
        long sum = bal.values().stream().mapToLong(Long::longValue).sum();
        System.out.println("balances " + bal + ", sum=" + sum);
        settle(bal).forEach(t -> System.out.println(t.from() + " pays " + t.to() + " " + t.amount()));
    }
}