using System;
using System.Collections.Generic;
using System.Linq;
namespace GAExample
{
    class Program
    {
        static void Main(string[] args)
        {
            //Generate knapsack instance with 50 items with an max item weight of 100
            KnapSackInstance knapSack = new KnapSackInstance(50, 0.5, 100);
            knapSack.Print();
            Console.WriteLine("Press enter to start the genetic algorithm and again to go to the next generation");
            Console.ReadLine();
            GeneticAlgorithm GA = new GeneticAlgorithm(knapSack, 50);

            while (true)
            {
                GA.Print();
                GA.NextGeneration();
                Console.ReadLine();
            }
        }


    }
    class GeneticAlgorithm
    {
        public List<Solution> Population;
        public Solution OptimalSolution;
        Random RNG = new Random();
        public GeneticAlgorithm(KnapSackInstance knapSack, int popSize)
        {
            //Create population with random solutions and aply hill climbing
            Population = new List<Solution>();
            for (int i = 0; i < popSize; i++)
            {
                Solution individual = new Solution(knapSack);
                individual.HillClimb();
                Population.Add(individual);
            }


            //Generate optimal solution for reference
            OptimalSolution = new Solution(knapSack);
            OptimalSolution.DynamicFill();
        }
        public void NextGeneration()
        {
            int popSize = Population.Count;

            List<Solution> Childeren = new List<Solution>();
            while (Childeren.Count < popSize)
            {
                //pick two random parents
                Solution parent1 = Population[RNG.Next(Population.Count)];
                Solution parent2 = Population[RNG.Next(Population.Count)];

                //apply uniform crossover to get offspring
                Solution child = parent1.UniformCrossover(parent2);
                Childeren.Add(child);
            }
            foreach (Solution child in Childeren)
            {
                //perform hillclimbing on offspring
                child.HillClimb();
            }

            // add offspring to population
            Population.AddRange(Childeren);

            //apply truncation selection i.e. throw worst half away
            Population = Population.OrderByDescending(x => x.GetFitness()).Take(popSize).ToList();
        }

        public void Print()
        {
            Console.WriteLine("Global Optimum/ Target Soltion:");
            OptimalSolution.Print();
            Console.WriteLine("Population:");
            foreach (var individual in Population)
            {
                individual.Print();

            }
            Console.WriteLine();
        }
    }

    class Solution
    {
        public bool[] BitString;
        public KnapSackInstance KnapSack;
        Random RNG;
        public Solution(KnapSackInstance knapSack)
        {
            KnapSack = knapSack;
            BitString = new bool[KnapSack.Items.Count];
            RNG = knapSack.RNG;
        }

        public void RandomInitialize()
        {
            //generates random soltion
            for (int i = 0; i < BitString.Length; i++)
            {
                BitString[i] = RNG.NextDouble() > 0.5;
            }
        }

        public void RandomFix()
        {
            //removes random items until the capacity contraint is met
            List<int> indices = new List<int>();
            int totalWeight = 0;
            for (int i = 0; i < BitString.Length; i++)
            {
                if (BitString[i]) { indices.Add(i); totalWeight += KnapSack.Items[i].Weight; }
            }
            while (totalWeight > KnapSack.MaxWeight)
            {
                int randomIndex = RNG.Next(indices.Count);
                int index = indices[randomIndex];
                indices.RemoveAt(randomIndex);
                BitString[index] = false;
                totalWeight -= KnapSack.Items[index].Weight;
            }
        }


        //applies bitflip unti no improving moves are made
        public void HillClimb()
        {

            while (BitFlip()) { }
        }

        //Sees if there is a bitflip possible the produces a better solution
        //This process is randomized for diversity in population
        public bool BitFlip()
        {
            List<int> indices = new List<int>();
            int totalWeight = 0;
            for (int i = 0; i < BitString.Length; i++)
            {
                indices.Add(i);
                if (BitString[i]) { totalWeight += KnapSack.Items[i].Weight; }
            }
            indices = indices.OrderBy(x => RNG.NextDouble()).ToList();
            foreach (int index in indices)
            {
                int fitness = KnapSack.GetFitness(BitString);
                BitString[index] = !BitString[index];
                if (fitness >= KnapSack.GetFitness(BitString))
                {
                    BitString[index] = !BitString[index];
                }
                else
                {
                    return true;
                }
            }
            return false;
        }

        // generates offspring with the uniform crossover
        public Solution UniformCrossover(Solution parent2)
        {
            bool[] newBitString = new bool[BitString.Length];
            for (int i = 0; i < BitString.Length; i++)
            {
                newBitString[i] = RNG.NextDouble() > 0.5 ? BitString[i] : parent2.BitString[i];
            }
            Solution child = new Solution(KnapSack);
            child.BitString = newBitString;
            child.RandomFix();
            return child;
        }

        public int GetFitness()
        {
            return KnapSack.GetFitness(BitString);
        }

        //Find optimal solution with dynamic programming
        //No comments (sorry) so probabily not easy to understand
        public void DynamicFill()
        {
            double[,] matrix = new double[BitString.Length, KnapSack.MaxWeight + 1];
            for (int i = 0; i <= KnapSack.MaxWeight; i++)
            {
                matrix[0, i] = Int32.MinValue;
            }

            bool[] bits = new bool[BitString.Length];
            matrix[0, 0] = 0;
            matrix[0, KnapSack.Items[0].Weight] = KnapSack.Items[0].Profit;

            for (int i = 1; i < BitString.Length; i++)
            {
                for (int j = 0; j <= KnapSack.MaxWeight; j++)
                {
                    double notInclude = matrix[i - 1, j];
                    double Include;
                    if (j - KnapSack.Items[i].Weight >= 0)
                    {
                        Include = matrix[i - 1, j - KnapSack.Items[i].Weight] + KnapSack.Items[i].Profit;
                    }
                    else
                    {
                        Include = Int32.MinValue;
                    }
                    matrix[i, j] = Include >= notInclude ? Include : notInclude;
                }
            }

            //find best value in last column
            double best = Int32.MinValue;
            int weight = 0;
            for (int j = 0; j <= KnapSack.MaxWeight; j++)
            {
                if (matrix[BitString.Length - 1, j] > best)
                {
                    best = matrix[BitString.Length - 1, j];
                    weight = j;
                }
            }

            //Extract the best packing plan
            {
                int j = weight;
                for (int i = BitString.Length - 1; i > 0; i--)
                {
                    double notInclude = matrix[i - 1, j];
                    double Include;
                    if (j - KnapSack.Items[i].Weight >= 0)
                    {
                        Include = matrix[i - 1, j - KnapSack.Items[i].Weight] + KnapSack.Items[i].Profit;
                    }
                    else
                    {
                        Include = Int32.MinValue;
                    }
                    if (Include >= notInclude)
                    {
                        bits[i] = true;
                        j = j - KnapSack.Items[i].Weight;
                    }
                }

                if (j > 0)
                {
                    bits[0] = true;
                }
            }
            BitString = bits;
        }
        public void Print()
        {
            string bitsRepresentation = "";
            for (int i = 0; i < BitString.Length; i++)
            {
                bitsRepresentation += BitString[i] ? 1 : 0;
            }
            Console.WriteLine(GetFitness() + " : " + bitsRepresentation);
        }

    }
    class Item
    {
        public int Weight;
        public int Profit;
        public Item(int weight, int profit)
        {
            Weight = weight;
            Profit = profit;
        }
    }
    class KnapSackInstance
    {

        public List<Item> Items;
        public int MaxWeight;
        public Random RNG = new Random();

        //creates random knapsack intance of type (weakly) correlated
        public KnapSackInstance(int maxItems, double maxWeightFactor, int maxWeightItem)
        {

            int totalWeight = 0;
            Items = new List<Item>();
            for (int i = 0; i < maxItems; i++)
            {
                int weight = RNG.Next(maxWeightItem);
                int profit = weight + RNG.Next(10);
                Items.Add(new Item(weight, profit));
                totalWeight += weight;
            }
            MaxWeight = (int)(totalWeight * maxWeightFactor);
        }

        public int GetFitness(bool[] solution)
        {
            int weight = 0;
            int profit = 0;
            for (int i = 0; i < solution.Length; i++)
            {
                if (solution[i])
                {
                    profit += Items[i].Profit;
                    weight += Items[i].Weight;
                }
            }

            return weight <= MaxWeight ? profit : int.MinValue;
        }

        public void Print()
        {
            Console.WriteLine("All items:");
            Console.WriteLine("Index\tProfit\tWeight");
            for (int i = 0; i < Items.Count; i++)
            {
                Console.WriteLine("{0}\t{1}\t{2}", i, Items[i].Profit, Items[i].Weight);
            }

        }
    }


}