Bellman–Ford shortest paths.

export const MAX_CURRENCIES = 64;
export const MAX_QUOTES = 256;
export const MIN_COST = -500;
export const MAX_COST = 5000;

// cost is the basis points a quote loses against the mid-market rate:
// 10,000 × ln(mid ÷ quoted rate), rounded. A quote better than mid costs less than 0.
// Logarithms add, so the cost of a chain of conversions is the sum of its quotes.
export type Quote = { from: string; to: string; cost: number };
export type Market = { currencies: string[]; quotes: Quote[] };
export type Relaxation = {
	from: string;
	to: string;
	oldCost: number | null;
	newCost: number;
};
export type Pass = {
	pass: number;
	updates: Relaxation[];
	costs: Record<string, number | null>;
	changed: boolean;
};
export type Paths = {
	start: string;
	currencies: string[];
	costs: Record<string, number | null>;
	via: Record<string, string | null>;
	passes: number;
};

export type ExchangeErrorCode =
	'too-big' | 'bad-currency' | 'unknown-currency' | 'bad-cost' | 'negative-cycle';

export class ExchangeError extends Error {
	readonly code: ExchangeErrorCode;
	constructor(code: ExchangeErrorCode, message: string) {
		super(message);
		this.name = 'ExchangeError';
		this.code = code;
	}
}

function validate(market: Market, start: string): void {
	if (market.currencies.length > MAX_CURRENCIES || market.quotes.length > MAX_QUOTES)
		throw new ExchangeError(
			'too-big',
			`up to ${MAX_CURRENCIES} currencies and ${MAX_QUOTES} quotes`
		);
	const known = new Set<string>();
	for (const currency of market.currencies) {
		if (!/^[a-z]{3}$/.test(currency) || known.has(currency))
			throw new ExchangeError(
				'bad-currency',
				`currencies are unique three-letter lowercase codes: ${currency}`
			);
		known.add(currency);
	}
	for (const quote of market.quotes) {
		if (!known.has(quote.from) || !known.has(quote.to))
			throw new ExchangeError(
				'unknown-currency',
				`a quote names a currency that is not in the market: ${quote.from}, ${quote.to}`
			);
		if (!Number.isInteger(quote.cost) || quote.cost < MIN_COST || quote.cost > MAX_COST)
			throw new ExchangeError(
				'bad-cost',
				`costs are whole basis points from ${MIN_COST} to ${MAX_COST}`
			);
	}
	if (!known.has(start)) throw new ExchangeError('unknown-currency', `no such currency: ${start}`);
}

function snapshot(currencies: string[], costs: Map<string, number>): Record<string, number | null> {
	return Object.fromEntries(currencies.map((currency) => [currency, costs.get(currency) ?? null]));
}

// Relax every quote up to V - 1 times. In-place updates let an improvement travel on within
// the same pass, but no currency's cost is ever treated as final.
export function traceRelaxation(market: Market, start: string): Pass[] {
	validate(market, start);
	const costs = new Map<string, number>([[start, 0]]);
	const passes: Pass[] = [];
	for (let pass = 1; pass < market.currencies.length; pass++) {
		const updates: Relaxation[] = [];
		for (const quote of market.quotes) {
			const from = costs.get(quote.from);
			if (from === undefined) continue;
			const newCost = from + quote.cost;
			const oldCost = costs.get(quote.to) ?? null;
			if (oldCost === null || newCost < oldCost) {
				costs.set(quote.to, newCost);
				updates.push({ from: quote.from, to: quote.to, oldCost, newCost });
			}
		}
		passes.push({
			pass,
			updates,
			costs: snapshot(market.currencies, costs),
			changed: updates.length > 0
		});
		if (updates.length === 0) break;
	}
	for (const quote of market.quotes) {
		const from = costs.get(quote.from);
		if (from !== undefined && from + quote.cost < (costs.get(quote.to) ?? Infinity))
			throw new ExchangeError('negative-cycle', 'a reachable negative cycle has no cheapest chain');
	}
	return passes;
}

export function shortestPaths(market: Market, start: string): Paths {
	const passes = traceRelaxation(market, start);
	const last = passes.at(-1);
	const costs = last?.costs ?? snapshot(market.currencies, new Map([[start, 0]]));
	const via: Record<string, string | null> = Object.fromEntries(
		market.currencies.map((currency) => [currency, null])
	);
	for (const pass of passes)
		for (const update of pass.updates) {
			via[update.to] = update.from;
		}
	return {
		start,
		currencies: market.currencies.slice(),
		costs,
		via,
		passes: passes.length
	};
}

const (
	MaxCurrencies = 64
	MaxQuotes     = 256
	MinCost       = -500
	MaxCost       = 5000
)

// Cost is the basis points a quote loses against the mid-market rate:
// 10,000 × ln(mid ÷ quoted rate), rounded. A quote better than mid costs less than 0.
// Logarithms add, so the cost of a chain of conversions is the sum of its quotes.
type Quote struct {
	From string
	To   string
	Cost int
}

type Market struct {
	Currencies []string
	Quotes     []Quote
}

type Relaxation struct {
	From    string
	To      string
	OldCost *int
	NewCost int
}

type Pass struct {
	Pass    int
	Updates []Relaxation
	Costs   map[string]*int
	Changed bool
}

type Paths struct {
	Start      string
	Currencies []string
	Costs      map[string]*int
	Via        map[string]string
	Passes     int
}

type ExchangeError struct {
	Code    string
	Message string
}

func (e *ExchangeError) Error() string { return e.Message }

var currencyPattern = regexp.MustCompile(`^[a-z]{3}$`)

func validate(market Market, start string) error {
	if len(market.Currencies) > MaxCurrencies || len(market.Quotes) > MaxQuotes {
		return &ExchangeError{"too-big", fmt.Sprintf("up to %d currencies and %d quotes", MaxCurrencies, MaxQuotes)}
	}
	known := map[string]bool{}
	for _, currency := range market.Currencies {
		if !currencyPattern.MatchString(currency) || known[currency] {
			return &ExchangeError{"bad-currency", "currencies are unique three-letter lowercase codes: " + currency}
		}
		known[currency] = true
	}
	for _, quote := range market.Quotes {
		if !known[quote.From] || !known[quote.To] {
			return &ExchangeError{"unknown-currency", fmt.Sprintf("a quote names a currency that is not in the market: %s, %s", quote.From, quote.To)}
		}
		if quote.Cost < MinCost || quote.Cost > MaxCost {
			return &ExchangeError{"bad-cost", fmt.Sprintf("costs are whole basis points from %d to %d", MinCost, MaxCost)}
		}
	}
	if !known[start] {
		return &ExchangeError{"unknown-currency", "no such currency: " + start}
	}
	return nil
}

func snapshot(currencies []string, costs map[string]int) map[string]*int {
	result := map[string]*int{}
	for _, currency := range currencies {
		if value, ok := costs[currency]; ok {
			copy := value
			result[currency] = &copy
		} else {
			result[currency] = nil
		}
	}
	return result
}

// Relax every quote up to V - 1 times. In-place updates let an improvement travel on within
// the same pass, but no currency's cost is ever treated as final.
func TraceRelaxation(market Market, start string) ([]Pass, error) {
	if err := validate(market, start); err != nil {
		return nil, err
	}
	costs := map[string]int{start: 0}
	passes := []Pass{}
	for pass := 1; pass < len(market.Currencies); pass++ {
		updates := []Relaxation{}
		for _, quote := range market.Quotes {
			from, ok := costs[quote.From]
			if !ok {
				continue
			}
			newCost := from + quote.Cost
			oldCost, reached := costs[quote.To]
			if !reached || newCost < oldCost {
				var old *int
				if reached {
					copy := oldCost
					old = &copy
				}
				costs[quote.To] = newCost
				updates = append(updates, Relaxation{quote.From, quote.To, old, newCost})
			}
		}
		passes = append(passes, Pass{pass, updates, snapshot(market.Currencies, costs), len(updates) > 0})
		if len(updates) == 0 {
			break
		}
	}
	for _, quote := range market.Quotes {
		from, fromReached := costs[quote.From]
		to, toReached := costs[quote.To]
		if fromReached && (!toReached || from+quote.Cost < to) {
			return nil, &ExchangeError{"negative-cycle", "a reachable negative cycle has no cheapest chain"}
		}
	}
	return passes, nil
}

func ShortestPaths(market Market, start string) (Paths, error) {
	passes, err := TraceRelaxation(market, start)
	if err != nil {
		return Paths{}, err
	}
	costs := map[string]*int{}
	if len(passes) > 0 {
		costs = passes[len(passes)-1].Costs
	} else {
		costs = snapshot(market.Currencies, map[string]int{start: 0})
	}
	via := map[string]string{}
	for _, currency := range market.Currencies {
		via[currency] = ""
	}
	for _, pass := range passes {
		for _, update := range pass.Updates {
			via[update.To] = update.From
		}
	}
	return Paths{start, append([]string(nil), market.Currencies...), costs, via, len(passes)}, nil
}