--- Day 16: Ticket Translation ---

#include <algorithm>
#include <iostream>
#include <iterator>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <numeric>

struct Field
{
    std::string name;
    std::pair<int, int> range[2];

    bool IsValid(int num) const
    {
        for (unsigned int i = 0; i < 2; i++)
        {
            if (num >= range[i].first && num <= range[i].second) //if the number fits into at least one range, it must be valid
                return true;
        }

        return false;
    }
};

int main()
{
    std::string text;
    std::ifstream ifs;
    ifs.open("data.txt", std::ifstream::in);

    unsigned long long part1Answer = 0;
    unsigned long long part2Answer = 0;

    int turn = 0;
    std::vector<Field> field;
    std::vector<int> myTicket;
    std::vector<std::vector<int>> validTicket;
    while (getline(ifs, text))
    {
        if (text == "")
        {
            turn = 0;
            continue;
        }
        else if (text == "your ticket:")
        {
            turn = 1;
            continue;
        }
        else if (text == "nearby tickets:")
        {
            turn = 2;
            continue;
        }

        if (turn == 0) //parse fields
        {
            Field f;
            f.name = text.substr(0, text.find(':'));
            text.erase(0, text.find(':') + 1);

            std::istringstream iss(text);
            std::vector<std::string> results((std::istream_iterator<std::string>(iss)), std::istream_iterator<std::string>());
            f.range[0].first = atoi(results[0].substr(0, results[0].find('-')).c_str());
            f.range[0].second = atoi(results[0].substr(results[0].find('-') + 1).c_str());
            f.range[1].first = atoi(results[2].substr(0, results[2].find('-')).c_str());
            f.range[1].second = atoi(results[2].substr(results[2].find('-') + 1).c_str());
            field.push_back(f);
        }
        else if (turn == 1) //get my ticket
        {
            std::string s;
            std::istringstream iss(text);
            while (getline(iss, s, ','))
                myTicket.push_back(atoi(s.c_str()));
        }
        else //check nearby tickets
        {
            std::string s;
            std::istringstream iss(text);

            std::vector<int> ticket;
            bool valid = true;
            int n = 0;
            while (getline(iss, s, ','))
            {
                int number = atoi(s.c_str());

                int val = 0;
                for (unsigned int i = 0; i < field.size(); i++)
                {
                    if (field[i].IsValid(number))
                    {
                        val++;
                    }
                }

                if (val == 0) //if at least one number is completely invalid, ticket is invalid
                {
                    part1Answer += number;
                    valid = false;
                }

                ticket.push_back(number);
                n++;
            }

            if (valid) //if ticket is valid, add to list.
            {
                validTicket.push_back(ticket);
            }
        }
    }

    std::cout << "Part 1 Answer: " << part1Answer << std::endl;

    //validTicket.push_back(myTicket); //add my ticket to the valid list

    std::vector<int> order(field.size());
    std::fill(order.begin(), order.end(), -1);

    bool valid;
    do
    {
        for (unsigned int i = 0; i < field.size(); i++)
        {
            int possibility = 0;
            int pos = -1;

            const Field& f = field[i];

            for (unsigned int j = 0; j < myTicket.size(); j++)
            {
                if (order[j] >= 0) //already set, so skip
                    continue;

                unsigned int k = 0;
                for (k; k < validTicket.size(); k++) //search through all valid tickets including mine
                {
                    const std::vector<int>& ticket = validTicket[k];
                    int theirs = ticket[j];
                    if (!f.IsValid(theirs))
                        break;
                }

                if (k >= validTicket.size()) //Valid Field!
                {
                    possibility++;
                    pos = j;
                }
            }

            if (possibility == 1)
                order[pos] = i;
        }

        valid = true;
        for (unsigned int i = 0; i < order.size(); i++)
        {
            if (order[i] < 0)
                valid = false;
        }

    } while (!valid);

    for (unsigned int i = 0; i < myTicket.size(); i++)
    {
        int f = order[i];
        int t = i;

        std::cout << field[f].name << ": " << myTicket[t] << std::endl;
        if (field[f].name.find("departure") != std::string::npos)
        {
            if (part2Answer == 0)
                part2Answer = myTicket[t];
            else
                part2Answer *= myTicket[t];
        }
    }

    std::cout << "Part 2 Answer: " << part2Answer << std::endl;

    return 0;
}