using System;
using System.Collections;
using System.Collections.Generic;
using System.Data.Common;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DO_Lab5
{
    struct Consumer
    {
        public int transportationCosts;
        public int metNeeds;
        public bool isHighlighted;
    }
    internal class DiffRentMethod
    {
        //----------------------------
        private void printArr()
        {
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    if (consumers[i, j].metNeeds == -1)
                    {
                        Console.Write($"{consumers[i, j].transportationCosts}".PadRight(7));
                    }
                    else
                    {
                        Console.Write($"{consumers[i, j].transportationCosts}/{consumers[i, j].metNeeds}".PadRight(7));
                    }
                }

                if (signs[i] < 0)
                {
                    Console.WriteLine($"\t-{Math.Abs(stocksBalance[i])}");
                }
                else
                {
                    Console.WriteLine($"\t+{Math.Abs(stocksBalance[i])}");
                }
            }
            Console.WriteLine("_________________________________________________");
            for (int i = 0; i < difference.Length; i++)
            {
                    Console.Write($"{difference[i]}".PadRight(7));
            }
            Console.WriteLine();
            Console.WriteLine();
        }
        //----------------------------
        private Consumer[,] consumers;
        private int[,] initialPrices;
        private int[] needs;
        private int[] stocks;
        private int[] stocksBalance;
        private int[] difference;
        private int[] signs;
        public DiffRentMethod(string path)
        {
            string[] data = File.ReadAllLines(path);
            stocks = new int[data.Length - 1];
            stocksBalance = new int[stocks.Length];
            Array.Fill(stocksBalance, int.MinValue);
            needs = new int[data.Last().Split(' ').Length];
            difference = new int[needs.Length];
            signs = new int[stocksBalance.Length];

            consumers = new Consumer[stocks.Length, needs.Length];
            initialPrices = new int[stocks.Length, needs.Length];

            for (int i = 0; i < data.Length; i++)
            {
                string[] current = data[i].Split(' ');
                if (i < data.Length - 1)
                {
                    for (int j = 0; j < current.Length; j++)
                    {
                        if (j < current.Length - 1)
                        {
                            consumers[i, j].transportationCosts = int.Parse(current[j]);
                            initialPrices[i, j] = consumers[i, j].transportationCosts;
                            consumers[i, j].metNeeds = -1;
                        }
                        else
                        {
                            stocks[i] = int.Parse(current[j]);
                        }
                    }
                }
                else
                {
                    for (int j = 0; j < current.Length; j++)
                    {
                        needs[j] = int.Parse(current[j]);
                    }
                }
            }
            if (stocks.Sum() != needs.Sum())
            {
                Console.WriteLine("Задача вiдкритого типу!");
                Console.WriteLine("Потреби " + needs.Sum());
                Console.WriteLine("Запаси " + stocks.Sum());
                Environment.Exit(0);
            }
        }
        private void findMinInColumn()
        {
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    consumers[i, j].isHighlighted = false;
                    consumers[i, j].metNeeds = -1;
                }
            }

            int row = -1, min = -1;
            for (int j = 0; j < consumers.GetLength(1); j++)
            {
                min = consumers[0, j].transportationCosts;
                row = 0;
                for (int i = 1; i < consumers.GetLength(0); i++)
                {
                    if (consumers[i, j].transportationCosts < min)
                    {
                        min = consumers[i, j].transportationCosts;
                        row = i;
                    }
                }
                for (int i = 0; i < consumers.GetLength(0); i++)
                {
                    if (consumers[i, j].transportationCosts == min)
                    {
                        consumers[i, j].isHighlighted = true;
                    }
                }
            }
        }
        private bool initHighlighted()
        {
            int[] stocksVal = (int[])stocks.Clone();
            int[] needsVal = (int[])needs.Clone();
            stocksBalance = (int[])stocks.Clone();

            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    if (consumers[i, j].isHighlighted && consumers[i, j].metNeeds == -1)
                    {
                        fillCell(i, j);
                    }
                }
            }

            if (needs.Where(p => p == 0).Count() == needs.Length)
            {
                return true;
            }
            stocks = stocksVal;
            needs = needsVal;
            return false;
        }
        private bool fillSingleInColumn()
        {
            int row = -1, column = -1, count = 0;
            for (int j = 0; j < consumers.GetLength(1); j++)
            {
                row = -1; column = -1; count = 0;
                for (int i = 0; i < consumers.GetLength(0); i++)
                {
                    if (consumers[i, j].isHighlighted && consumers[i, j].metNeeds == -1)
                    {
                        row = i; column = j; count++;
                    }
                }
                if (count == 1)
                {
                    fillCell(row, column);
                    return true;
                }
            }
            return false;
        }
        private bool fillSingleInRow()
        {
            int row = -1, column = -1, count = 0;
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                row = -1; column = -1; count = 0;
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    if (consumers[i, j].isHighlighted && consumers[i, j].metNeeds == -1)
                    {
                        row = i; column = j; count++;
                    }
                }
                if (count == 1)
                {
                    fillCell(row, column);
                    return true;
                }
            }
            return false;
        }
        private void fillCell(int row, int column)
        {
            int valueToTransport = Math.Min(stocks[row], needs[column]);
            consumers[row, column].metNeeds = valueToTransport;
            stocks[row] -= valueToTransport;
            needs[column] -= valueToTransport;
        }
        private bool isHighlightedFullyFilled()
        {
            foreach (Consumer consumer in consumers)
            {
                if (consumer.isHighlighted && consumer.metNeeds == -1)
                {
                    return false;
                }
            }
            return true;
        }
        private void CalcStockBalance()
        {
            List<int> skippedColumns = new List<int>();
            stocksBalance = (int[])stocks.Clone();
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    if (skippedColumns.Contains(j))
                    {
                        continue;
                    }

                    if (consumers[i, j].isHighlighted)
                    {
                        stocksBalance[i] -= needs[j];
                        skippedColumns.Add(j);
                    }
                }
            }
        }
        private void fillCheaperInColumn()
        {
            int row = -1, column = -1, min = int.MaxValue;
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    if (consumers[i, j].isHighlighted && consumers[i, j].metNeeds == -1)
                    {
                        if (initialPrices[i, j] < min)
                        {
                            min = initialPrices[i, j];
                            row = i;
                            column = j;
                        }
                    }
                }
                if (row != -1)
                {
                    fillCell(row, column);
                    return;
                }
            }
        }
        private bool fillHighlighted()
        {

            if (stocksBalance[0] == int.MinValue)
            {
                bool result = initHighlighted();
                CalcStockBalance();
                return result;
            }

            int[] stocksVal = (int[])stocks.Clone();
            int[] needsVal = (int[])needs.Clone();
            stocksBalance = (int[])stocks.Clone();

            bool isFilled = false;
            while (!isFilled)
            {
                bool fCol = fillSingleInColumn();
                bool fRow = fillSingleInRow();
                if (fCol == false && fRow == false)
                {
                    fillCheaperInColumn();
                }
                isFilled = isHighlightedFullyFilled();
            }
            CalcStockBalance();

            if (stocksBalance.Where(p => p == 0).Count() == stocksBalance.Length)
            {
                return true;
            }

            stocks = stocksVal;
            needs = needsVal;
            return false;
        }
        private int calcSign(int row)
        {
            if (stocksBalance[row] > 0)
            {
                return 1;
            }
            else if (stocksBalance[row] < 0)
            {
                return -1;
            }
            else
            {

                List<int> highlighted = new List<int>();
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    if (consumers[row, j].isHighlighted)
                    {
                        highlighted.Add(j);
                    }
                }
                for (int j = 0; j < highlighted.Count; j++)
                {
                    List<int> highlightedInColumn = new List<int>();
                    int column = highlighted[j];
                    for (int i = 0; i < consumers.GetLength(0); i++)
                    {
                        if (i == row) continue;
                        if (consumers[i, column].isHighlighted)
                        {
                            highlightedInColumn.Add(i);
                        }
                    }
                    if (highlightedInColumn.Count != 0)
                    {
                        bool hasNegative = false;
                        foreach (int current in highlightedInColumn)
                        {
                            if (stocksBalance[current] < 0)
                            {
                                hasNegative = true;
                                break;
                            }
                        }
                        if (hasNegative)
                        {
                            return -1;
                        }
                        else return 1;
                    }
                }
                return -1;
            }
        }
        private List<int> getHighlightedInColumnIndicies(int column)
        {
            List<int> highlighted = new List<int>();
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                if (consumers[i, column].isHighlighted)
                {
                    highlighted.Add(i);
                }
            }
            return highlighted;
        }
        private int getDifRent()
        {
            Array.Fill(difference, 0);
            for (int i = 0; i < stocksBalance.Length; i++)
            {
                signs[i] = calcSign(i);
            }
            for (int j = 0; j < consumers.GetLength(1); j++)
            {
                List<int> highlightedInRow = getHighlightedInColumnIndicies(j);
                foreach (int highlighted in highlightedInRow)
                {
                    if (signs[highlighted] > 0)
                    {
                        difference[j] = -1;
                        break;
                    }
                }
                if (difference[j] == -1)
                {
                    continue;
                }
                int minDif = int.MaxValue;
                int highlightedVal = consumers[highlightedInRow[0], j].transportationCosts;
                for (int i = 0; i < consumers.GetLength(0); i++)
                {
                    if (highlightedInRow.Contains(i) || signs[i] == -1)
                    {
                        continue;
                    }
                    if (consumers[i, j].transportationCosts - highlightedVal < minDif)
                    {
                        minDif = consumers[i, j].transportationCosts - highlightedVal;
                    }
                }
                difference[j] = minDif;
            }
            return difference.Where(i => i > 0).Min();
        }
        private void addRent(int rent)
        {
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                if (signs[i] < 0)
                {
                    for (int j = 0; j < consumers.GetLength(1); j++)
                    {
                        consumers[i, j].transportationCosts += rent;
                    }
                }
            }
        }
        public void Solve()
        {
            bool isSolved = false;
            while (!isSolved)
            {
                findMinInColumn();
                isSolved = fillHighlighted();
                if (isSolved)
                {
                    printArr();
                    break;
                }
                int diffRent = getDifRent();
                printArr();
                addRent(diffRent);
            }
            Console.WriteLine("SOLVED");
            int sum = 0;
            for (int i = 0; i < initialPrices.GetLength(0); i++)
            {
                for (int j = 0; j < initialPrices.GetLength(1); j++)
                {
                    if (consumers[i, j].isHighlighted)
                    {
                        sum += initialPrices[i, j] * consumers[i, j].metNeeds;
                    }
                }
            }
            Console.WriteLine($"Sum = {sum}");
        }
    }
}