BVI 2016

#!/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, alex, john, chris, phil],
		     [
		      {eskil, 592}, % Boat remainder for all.
		      {eskil, 1200, [john]}, % Boat for John.
		      {eskil, 721, [alex]}, % flight
		      {eskil, 230, [phil, chris]}, % hotel
		      {eskil, 230, [shelley, eskil]}, % hotel
		      {eskil, 230, [john]}, % hotel
		      {eskil, 230, [alex]}, % hotel
		      {eskil, 438}, % provisioning
		      {alex, 133, [alex, eskil, shelley]}, % airport food
		      {alex, 90}, % Airport beers
		      {chris, 307}, % dinner at base
		      {eskil, 99}, % Phone & inverter rental
		      {eskil, 20, [alex]}, % Spending money
		      {chris, 60, [phil, chris, john, eskil]}, % Breakfast at base
		      {alex, 419}, % Provisioning at base
		      {eskil, 248, [eskil, alex]}, % diving the rhone
		      {eskil, 60, [phil]}, % not diving the rhone
		      {john, 115}, % drinks Fat Hogs Bay
		      {eskil, 30}, % Mooring Peter Island
		      {eskil, 33, [eskil, shelley, chris, john]}, % drinks Peter Island
		      {phil, 85}, % drinks at the Baths
		      {eskil, 30}, % mooring at Cooper Island
		      {john, 400}, % dinner and drinks at cooper island
		      {chris, 15}, % Ice at cooper island
		      {eskil, 40}, % Virgin Gorda mooring (20$) & trash (3 x 3$) & water (75 gallons)
		      {shelley, 120}, % Virgin Gorda Groceries
		      {chris, 341}, % bitter end dinner
		      {eskil, 93, [eskil, alex, chris, phil, john]}, % loblolly cab + drinks
		      {eskil, 10}, % Ice anegada
		      {eskil, 5}, % Anegada Trash haul
		      {eskil, 30}, % Anegada mooring
		      {phil, 470}, % Lobster at anegada
		      {eskil, 60}, % Groceries at trellis
		      {eskil, 30}, % Mooring at trellis
		      {john, 30, [eskil, shelley, chris, john]}, % Drinks at loose mongoose
		      {phil, 237}, % dinner at loose mongoose
		      {phil, 188}, % Lunch at Myetts Cane Garden Bay
		      {john, 30}, % mooring at Cane garden bay
		      {eskil, 49, [chris, eskil, phil, alex, shelley]}, % Breakfast at elm beach cafe
		      {alex, 0, [alex, eskil]}, % Diving JVD
		      {john, 30}, % Mooring at JVD Great Harbour
		      {alex, 272, [alex, eskil]}, % JVD diving
		      {eskil, 43}, % Drinks at Foxys Taboo
		      {phil, 245}, % Dinner at Corsairs
		      {john, 411}, % Dinner at Pirates Bight
		      {eskil, 100}, % Drinkts at Pirates Bight
		      {eskil, 90}, % Drinks and snacks at base
		      {john, 252}, % dinner at Charlies at base
		      {eskil, 70}, % taxi to airport
		      {chris, 32}, % stuff
		      {chris, 80, [chris, phil, shelley, alex, eskil]} % Airport snacks
		     ]),
    io:format("~p~n", [Reduced]),
    io:format("------------------------------------------------------------------~n"),
    print_result(Reduced).