Debt reduce solution for 2015 BVI Trip

bvi_group.erl

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname bvi_group
%% escript ./bvi_group.erl

% Magic compiler directive to make reduce/1 be visible in main/1.
-mode(compile).


%% This is a variant of the debt reduce interview question that works
%% on a group of people, with persons making payments for things that
%% are for the entire group or a subgroup should reimburse them for.


%% Here's some common rounding functions we'll need.
round(Number, Precision) ->
    P = math:pow(10, Precision),
    round(Number * P) / P.

floor(X) when X < 0 ->
    T = trunc(X),
    case X - T == 0 of
	true -> T;
	false -> T - 1
    end;
floor(X) -> 
    trunc(X).

ceiling(X) when X < 0 ->
    trunc(X);
ceiling(X) ->
    T = trunc(X),
    case X - T == 0 of
	true -> T;
	false -> T + 1
    end.


%% Main entry for debt reduction.
-spec reduce(list(atom()), list(tuple())) -> list(tuple()).
reduce(_, []) ->
    [];
reduce(Group, Debts) ->
    %% First find out who is owed/owes how much.
    Balance = reduce_to_balances(Group, Debts, dict:new()),
    io:format("Balance: ~p~n", [dict:to_list(Balance)]),
    {Debtors, Creditors} = lists:partition(fun({_, Amount}) -> Amount < 0 end,
					   dict:to_list(Balance)),
    io:format("Debtors: ~p~n", [Debtors]),
    io:format("Creditors: ~p~n", [Creditors]),
    reduce_debts(lists:keysort(2, Debtors),
		 lists:reverse(lists:keysort(2, Creditors)), []).


%% Reduce to balances, where each payment is either for the entire
%% group or just a subgroup.
reduce_to_balances(Group, [{Creditor, Amount}|T], Acc) ->
    %% For entire group.
    % ceiling/1 amounts because cents are lame.
    PerHead = ceiling(Amount/length(Group)),
    Acc2 = reduce_to_balances_for_group(Group, {Creditor, PerHead}, Acc),
    reduce_to_balances(Group, T, Acc2);
reduce_to_balances(Group, [{Creditor, Amount, SubGroup}|T], Acc) ->
    %% For a subgroup only.
    % ceiling/1 amounts because cents are lame.
    PerHead = ceiling(Amount/length(SubGroup)),
    Acc2 = reduce_to_balances_for_group(SubGroup, {Creditor, PerHead}, Acc),
    reduce_to_balances(Group, T, Acc2);
reduce_to_balances(_Group, [], Acc) ->
    Acc.


%% Helper for reduce_to_balances/3 that reduces for the group.
reduce_to_balances_for_group([Creditor|T], {Creditor, Amount}, Acc) ->
    %% On a miss, dict:update_counter will set the value to the given amount.
    io:format("~w paid ~w to self~n", [Creditor, Amount]),
    reduce_to_balances_for_group(T, {Creditor, Amount}, Acc);
reduce_to_balances_for_group([Debtor|T], {Creditor, Amount}, Acc) ->
    %% On a miss, dict:update_counter will set the value to the given amount.
    io:format("~w paid ~w to ~w~n", [Creditor, Amount, Debtor]),
    D = dict:update_counter(Creditor, Amount, Acc),
    D2 = dict:update_counter(Debtor, -Amount, D),
    reduce_to_balances_for_group(T, {Creditor, Amount}, D2);
reduce_to_balances_for_group([], _, Acc) ->
    Acc.


%% Reduce payments, must be perfectly balanced.
reduce_debts([{_Debtor, Owes}|Debtors], Creditors, Acc) when Owes >= -0.01 ->
    %% If a debtor owes (close to) 0, remove from list.
    reduce_debts(Debtors, Creditors, Acc);
reduce_debts(Debtors, [{_Creditor, Owed}|Creditors], Acc) when Owed =< 0.01 ->
    %% If a creditor is owed (close to) 0, remove from list.
    reduce_debts(Debtors, Creditors, Acc);
reduce_debts([{Debtor, Owes}|Debtors], [{Creditor, Owed}|Creditors], Acc) ->
    %% Otherwise, alter their amount and create a payout from Debtor to Creditor.
    Amount = round(min(abs(Owes), Owed), 2),
    io:format("Reducing ~w from ~w to ~w, ~w from ~w to ~w by ~w~n", 
	      [Debtor, Owes, Owes + Amount, Creditor, Owed, Owed - Amount, Amount]),
    % It's important to keep the lists sorted so the most in-debt pays
    % the most-owed person.
    reduce_debts(lists:keysort(2, [{Debtor, Owes + Amount}|Debtors]),
		 lists:reverse(lists:keysort(2, [{Creditor, Owed - Amount}|Creditors])),
		 lists:append(Acc, [{Creditor, Debtor, Amount}]));
reduce_debts([], [], Acc) ->
    %% Once both lists are empty, we're done.
    Acc.


% Helper to print result "nicely".
print_result([{Creditor, Debtor, Amount}|T]) ->
    %% Fuck cents, ain't nobody got time for that. Round/1 everything to ints.
    io:format("~w pays ~w $~w~n", [Debtor, Creditor, round(Amount)]),
    print_result(T);
print_result([]) ->
    ok.


test() ->
    %% A pays 30 the group of 3, b pays 10 to b and c.
    %% A should get 20 back, 5 from b and 15 from c.
    Reduced = reduce([a, b, c], [{a, 30}, {b, 10, [b, c]}]),
    Result = sets:from_list(Reduced),
    Expected = sets:from_list([{a, b, 5.0}, {a, c, 15.0}]),
    Result = Expected.



main(_)->
    test(),
    Reduced = reduce([eskil, shelley, bran, sarah, alex, maia, john],
		     [
		      {eskil, 888}, % provisions, plus remaineder on boat
		      {eskil, 275, [eskil, shelley]}, % hotel
		      {eskil, 275, [john]}, % hotel
		      {eskil, 275, [alex, maia]}, % hotel
		      {eskil, 275, [bran, sarah]}, % hotel
		      {john, 208}, % dinner at base
		      {shelley, 334}, % groceries
		      {eskil, 630, [eskil, alex, maia, bran, sarah]}, % dive
		      {bran, 471}, % dinner at bitter end
		      {eskil, 16}, % garbage & ice
		      {bran, 84, [eskil, shelley, bran, sarah, alex, maia]}, % taxi on anegada, john paid separately
		      {bran, 220}, % lobster dinner
		      {eskil, 400}, % lobster dinner
		      {eskil, 28}, % north sound coffee
		      {maia, 197}, % bitter end groceries
		      {eskil, 41}, % foxy's taboo drinks
		      {eskil, 478}, % foxy's taboo dinner & drinks
		      {bran, 588, [eskil, alex, bran, sarah]}, % diving
		      {bran, 30}, % mooring ball at jvd
		      {john, 190}, % lunch at corsairs
		      {alex, 338}, % dinner at foxy's
		      {alex, 48}, % drinks at corsairs
		      {eskil, 40}, % fatties
		      {eskil, 173}, % groceries at rudy's
		      {eskil, 26}, % fuel & water for boat
		      {eskil, 9}, % fish
		      {eskil, 80}, % drinks at white bay
		      {eskil, 514}, % dinner at pirate's bight
		      {alex, 138}, % drinks & snacks at hotel
		      {eskil, 40, [eskil, alex]}, % cigars
		      {alex, 298}, % dinner at hotel
		      {maia, 155, [eskil, shelley, bran, sarah, alex, maia]}, % breakfast at hotel (john didn't eat)
		      {eskil, 83, [eskil, shelley, alex, maia]} % drinks at charlotte
		     ]),
    io:format("~p~n", [Reduced]),
    io:format("------------------------------------------------------------------~n"),
    print_result(Reduced).