using System;
using System.Collections.Generic;
using System.Linq;

namespace TestMHT
{
    class Program
    {
        static void Main(string[] args)
        {
            Dictionary<string, double> owes = new Dictionary<string, double>
            {
                { "Manta Ray", 84.86 },
                { "Peter", -91.15 },
                { "Dan O", -69.12 },
                { "Goose", -5.73 },
                { "Brandon", 41.11 },
                { "Big L", 40.02 }
            };

            Dictionary<string, double> peopleOwed = new Dictionary<string, double>();
            Dictionary<string, double> peopleWhoOwe = new Dictionary<string, double>();

            List<string> txnLog = new List<string>();

            foreach (var kvp in owes)
            {
                if (kvp.Value > 0)
                {
                    peopleOwed.Add(kvp.Key, kvp.Value);
                }
                else
                {
                    peopleWhoOwe.Add(kvp.Key, -kvp.Value);
                }
            }

            while (CalcFullOwes(ref peopleOwed, ref peopleWhoOwe, ref txnLog)) ;

            foreach (var s in txnLog)
            {
                Console.WriteLine(s);
            }

            foreach (var kvp in peopleOwed)
            {
                Console.WriteLine("{0} still owed {1}", kvp.Key, kvp.Value);
            }

            foreach (var kvp in peopleWhoOwe)
            {
                Console.WriteLine("{0} still owes {1}", kvp.Key, kvp.Value);
            }

            Console.ReadKey();
        }


        public static bool CalcFullOwes(ref Dictionary<string, double> peopleOwed, ref Dictionary<string, double> peopleWhoOwe, ref List<string> txnLog)
        {
            foreach (var owedKvp in peopleOwed.OrderByDescending(x => x.Value))
            {
                // Take smallest owers that can insert their full value into the current owe
                foreach (var owerKvp in peopleWhoOwe.OrderBy(x => x.Value))
                {
                    if (owerKvp.Value < owedKvp.Value)
                    {
                        txnLog.Add(string.Format("{0} pays {1} ${2}", owerKvp.Key, owedKvp.Key, owerKvp.Value));
                        peopleOwed[owedKvp.Key] = peopleOwed[owedKvp.Key] - peopleWhoOwe[owerKvp.Key];
                        peopleWhoOwe.Remove(owerKvp.Key);
                        if (peopleOwed[owedKvp.Key] < 0.001)
                        {
                            peopleOwed.Remove(owedKvp.Key);
                        }
                        return true;
                    }
                }
            }

            // Now calculate splits
            foreach (var owedKvp in peopleOwed.OrderByDescending(x => x.Value))
            {
                // Take biggest owers and split
                foreach (var owerKvp in peopleWhoOwe.OrderByDescending(x => x.Value))
                {
                    if (owerKvp.Value > owedKvp.Value)
                    {
                        double amountToPay = owedKvp.Value;
                        txnLog.Add(string.Format("{0} pays {1} ${2}", owerKvp.Key, owedKvp.Key, amountToPay));
                        peopleOwed.Remove(owedKvp.Key);
                        peopleWhoOwe[owerKvp.Key] -= amountToPay;
                        if (peopleWhoOwe[owerKvp.Key] < 0.001)
                        {
                            peopleWhoOwe.Remove(owerKvp.Key);
                        }
                        return true;
                    }
                }
            }


            return false;
        }
    }
}

// Console Output
// Goose pays Manta Ray $5.73
// Dan O pays Manta Ray $69.12
// Peter pays Brandon $41.11
// Peter pays Big L $40.02
// Peter pays Manta Ray $10.01
// Peter still owes 0.0100000000000122