//Advent of Code 2020 Day 9 Parts 1 and 2 solution by Mike LeSauvage
public class XMASAttacker : MonoBehaviour
{
    [SerializeField] TextAsset XMASCode = null;   //Hooked up in the input text in the Unity editor.
    [SerializeField] int PREAMBLE_LEN = 25;       //The portion of the numbers identified in the challenge as the preamble; change for testing smaller sample sets.

    // Start is a Unity method called once per program execution.
    void Start()
    {
        string[] data = XMASCode.text.Split('\n');

        //Part One
        long invalidNum = FindInvalidNumber(data);
        Debug.Log($"The first number encountered that is not the sum of two preceeding {PREAMBLE_LEN} numbers is: {invalidNum}");

        //Part Two
        long encryptionWeakness =  FindEncryptionWeakness(data, invalidNum);
        Debug.Log($"Encryption Weakness: {encryptionWeakness}");
    }

    // Working backwards through the list *should* be faster as with smaller numbers the sums should fail faster.
    // Sum numbers until the target is met or exceeded.
    // Once the range is found, add all numbers making the sum to a list; sort the list; add the smallest and largest
    //   numbers to find the encryption weakness.
    long FindEncryptionWeakness(string[] data, long targetSum)
    {
        for(int i=data.Length-1; i>=1; i--) //Outer loop.
        {
            long sum = 0;

            for(int j=i; j>=0; j--)  //Inner loop starts where the outer loop is pointing and works from there to the start.
            {
                sum += long.Parse(data[j]);

                if(sum > targetSum) //If we exceed the target move on to the next position in the data to check.
                {
                    break;
                }
                else if (sum == targetSum) //Found the target (with one exception, see next)
                {
                    //Only one number made the sum (it was the targetSum), which is not a vlid answer.
                    if(i==j)
                    {
                        break;
                    }

                    //Add the numbers that make the sum to a list so they can be sorted.
                    List<long> numbersInSum = new List<long>();
                    int start = j;
                    int end = i;

                    for (int k=start; k<=end; k++)
                    {
                        numbersInSum.Add(long.Parse(data[k]));
                    }

                    numbersInSum.Sort();

                    return numbersInSum[0] + numbersInSum[numbersInSum.Count - 1];
                }
            }
        }

        return -1; //Error condition.
    }


    //Core of part one solution.
    long FindInvalidNumber(string[] data)
    {
        for (int i = PREAMBLE_LEN; i < data.Length; i++) //Loop through the data past the preamble.
        {
            long currentData = long.Parse(data[i]);
            bool sumFound = false;

            //Loop across a preamble-sized chunk of data prior to the current data
            //looking for two numbers that sum to the current data.
            for (int checkIndexOuter = i - PREAMBLE_LEN; checkIndexOuter < i - 1; checkIndexOuter++)
            {
                long outerNum = long.Parse(data[checkIndexOuter]);

                for (int checkIndexInner = checkIndexOuter + 1; checkIndexInner < i; checkIndexInner++)
                {
                    long innerNum = long.Parse(data[checkIndexInner]);
                    long sum = outerNum + innerNum;

                    //If the sum adds up, no need to continue the loop. Break out of the inner loop.
                    if (sum == currentData)
                    {
                        sumFound = true;
                        break;
                    }

                }

                //Sum found, break out of the outer loop so the algorithm can inspect the next piece of data.
                if(sumFound)
                {
                    break;
                }

            }

            //The outer/inner loop did not find a sum that matches the current data point, so return with its value.
            if (!sumFound)
            {
                return long.Parse(data[i]);
            }
        }

        return -1; //Error condition as we're expecting to find a match. (Assumes data set did not include negative numbers).

    }
}