using System;

using System.Collections.Generic;

using System.Linq;

​

public enum FamilyName

{

    Young,

    Garner,

    Garlick,

    Reeves

}

​

public enum HumanType

{

    Adult,

    Child

}

​

public struct Person

{

    public string Name;

    public FamilyName Family;

    public HumanType Age;

    public List<Person> PastGiftees;

}

​

public class Program

{

    public static List<Person> People;

    public static List<string> newList;

    public static List<Person> Histories;

    public static int maxAttempts = 50000;

    public static void PopulatePeople()

    {

        People.Add(new Person() {Name = "Dana", Family = FamilyName.Young, Age = HumanType.Adult, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Emily", Family = FamilyName.Young, Age = HumanType.Adult, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Jarik", Family = FamilyName.Young, Age = HumanType.Child, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Sammy", Family = FamilyName.Young, Age = HumanType.Child, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Becca", Family = FamilyName.Young, Age = HumanType.Child, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Spencer", Family = FamilyName.Young, Age = HumanType.Child, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Jason", Family = FamilyName.Garner, Age = HumanType.Adult, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Leann", Family = FamilyName.Garner, Age = HumanType.Adult, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Nicci", Family = FamilyName.Garner, Age = HumanType.Child, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Charlie", Family = FamilyName.Garner, Age = HumanType.Child, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Candi", Family = FamilyName.Garner, Age = HumanType.Child, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Chelsea", Family = FamilyName.Garner, Age = HumanType.Child, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Corby", Family = FamilyName.Garner, Age = HumanType.Child, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Jared", Family = FamilyName.Garlick, Age = HumanType.Adult, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Carrie", Family = FamilyName.Garlick, Age = HumanType.Adult, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Hazel", Family = FamilyName.Garlick, Age = HumanType.Child, PastGiftees = new List<Person>()});

        People.Add(new Person() {Name = "Mabel", Family = FamilyName.Garlick, Age = HumanType.Child, PastGiftees = new List<Person>()});

        foreach (var person in People)

        {

            foreach (var history in HistoricOrders)

            {

                int index = history.IndexOf(person.Name);

                if (People.Any(x => x.Name.Equals(history[index+1])))

                {

                    Person personInHistory = People.First(x => x.Name.Equals(history[index+1]));

                    person.PastGiftees.Add(personInHistory);

                }

            }

        }

    }

    public static List<string> Order_2020 = new List<string>() {"Dana","Candi","Carrie","Leann","Hazel","Kodiak","Jason","Emily","Calvin","Jarik","Chelsea","Sammy","Corby","Jared","Charlie","Becca","Nicci","Spencer","Dana"};

    public static List<string> Order_2021 = new List<string>() {"Carrie","Chelsea","Emily","Nicci","Jared","Sammy","Corby","Spencer","Charlie","Dana","Calvin","Becca","Candi","Hazel","Leann","Jarik","Jason","Carrie"};

    public static List<string> Order_2022 = new List<string>() {"Mabel","Becca","Jason","Hazel","Charlie","Jared","Candi","Dana","Corby","Carrie","Jarik","Leann","Sammy","Calvin","Emily","Chelsea","Spencer","Nicci","Mabel"};

    public static List<string> Order_2023 = new List<string>() {"Candi","Carrie","Calvin","Emily","Jared","Chelsea","Mabel","Jarik","Corby","Hazel","Jason","Becca","Charlie","Spencer","Leann","Dana","Nicci","Sammy","Candi"};

    public static List<string> Order_2024 = new List<string>() {"Jared","Nicci","Hazel","Spencer","Candi","Becca","Corby","Jarik","Carrie","Charlie","Mabel","Emily","Jason","Sammy","Chelsea","Dana","Leann","Jared"};

    public static List<List<string>> HistoricOrders = new List<List<string>>() { Order_2020, Order_2021, Order_2022, Order_2023, Order_2024 };

    public static void Main()

    {

        int numberOfListsToGenerate = 5;

        int attempts = 0;

        for (int i = 0; i < numberOfListsToGenerate && attempts < maxAttempts; i++)

        {

            attempts++;

            Random randomNumberGenerator = new Random();

            InitializeLists();

            if (CreateList(randomNumberGenerator))

            {

                PrintList(newList);

            }

            else

            {

                //Console.WriteLine("(" + attempts + ") - Failed to generate list...");

                i--;

            }

        }

    }

    public static void PrintList(List<string> myList)

    {

        bool isFirst = true;

        foreach (var name in myList)

        {

            if (!isFirst)

            {

                Console.Write(" → ");

            }

            else isFirst = false;

            Console.Write(name);

        }

        Console.WriteLine();

    }

    public static void InitializeLists()

    {

        if (People != null)

        {

            People.Clear();

        }

        People = new List<Person>();

        if (newList != null)

        {

            newList.Clear();

        }

        newList = new List<string>();

    }

    public static bool CreateList(Random rand)

    {

        PopulatePeople();

        // Pick the first person at random

        Person firstPerson = PickAvailablePerson(rand);

        // Add them to the new list

        newList.Add(firstPerson.Name);

        // save them as the previous person

        Person currentPerson = firstPerson;

        Person previousPerson = currentPerson;

        int attemptCount = 0;

        // while there are still people who don't exist in the new list

        while (attemptCount++ < maxAttempts && People.Any(x => !newList.Contains(x.Name)))

        {

            // Pick a new person who isn't already in the new list

            if (!TryPickAvailablePerson(rand, previousPerson, out currentPerson))

            {

                break;

            }

            // If the previous person was an adult and this person is an adult or if this person exists in the previous person's Past Giftees, re-pick.

            if (!IsValidGiftee(previousPerson, currentPerson))

            {

                break;

            }

            // Add them to the new list

            newList.Add(currentPerson.Name);

            // save them as the previous person

            previousPerson = currentPerson;

        }

        // If the first person in the new list is in the last person's Past Giftee or if they're both adults, reject the entire list.

        if (CountAvailablePeople() == 0 && IsValidGiftee(currentPerson, firstPerson))

        {

            newList.Add(firstPerson.Name);

            return true;

        }

        return false;

    }

    public static int CountAvailablePeople()

    {

        return People.Count(x => !newList.Contains(x.Name));

    }

    public static Person PickAvailablePerson(Random rand)

    {

        // Select from people who haven't been used yet

        var availablePeople = People.Where(x => !newList.Contains(x.Name)).ToList();

        return availablePeople[rand.Next() % availablePeople.Count];

    }

    public static bool TryPickAvailablePerson(Random rand, Person Giver, out Person Receiver)

    {

        // Select from people who haven't been used yet and are not in the Giver's family

        Receiver = new Person();

        var availablePeople = People.Where(x => !newList.Contains(x.Name) && x.Family != Giver.Family)?.ToList();

        if (availablePeople == null || availablePeople.Count == 0)

        {

            return false;

        }

        else

        {

            Receiver = availablePeople[rand.Next() % availablePeople.Count];

        }

        return true;

    }

    public static bool IsValidGiftee(Person Giver, Person Receiver)

    {

        // We don't give to people in our same family

        if (Giver.Family == Receiver.Family)

        {

            // Console.WriteLine("" + Giver.Name + " shouldn't give to " + Receiver.Name);

            return false;

        }

        // Adults don't give to adults

        //if (Giver.Age == HumanType.Adult && Receiver.Age == HumanType.Adult)

        //{

        //  return false;

        //}

        // We don't give to people we've given to before

        if (Giver.PastGiftees.Contains(Receiver))

        {

            // Console.WriteLine("" + Giver.Name + " has given to " + Receiver.Name + " in the past");

            return false;

        }

        return true;

    }

}