#include <iostream>
#include <array>
#include <cstdint>
#include <fstream>
#include <iterator>
#include <bitset>
#include <vector>
#include <print>

#define WIDTH 54
#define HEIGHT 54

using map_t = std::array<std::array<uint8_t, WIDTH>, HEIGHT>;

struct Point
{
    int_fast8_t Row;
    int_fast8_t Col;
};
std::ostream& operator<<(std::ostream& os, const Point& p)
{
    os << "{" << (int)p.Row << ", " << (int)p.Col << "}";
    return os;
}

using heads_t = std::vector<Point>;

struct sols_t
{
    std::bitset<WIDTH*HEIGHT> bits;
    void emplace(Point point)
    {
        bits.set(point.Row * WIDTH + point.Col);
    }
    int size() const
    {
        return bits.count();
    }
    void clear()
    {
        bits.reset();
    }
};

void load_map(map_t& map, heads_t& heads, const char* filepath)
{
    std::fstream in(filepath);
    std::istreambuf_iterator iter(in);
    for (int_fast8_t row = 0; row < map.size(); row++)
    {
        for (int_fast8_t col = 0; col < map[0].size(); col++)
        {
            map[row][col] = *(iter++) - '0';
            if (map[row][col] == 0)
            {
                Point p(row, col);
                heads.push_back(p);
                // heads.push_back({row, col});
            }
        }
        iter++;
    }
}

void quick_branch(const map_t& map, sols_t& terminals, Point init)
{
    std::array<int_fast8_t, 9> path;
    int_fast8_t height = 0;
    path[0] = 0;
    Point pos = init;
    while (height >= 0)
    {
        // const auto& pos = path[height].pos;
        switch (path[height]++)
        {
            case 0:
                if (pos.Row > 0 && map[pos.Row-1][pos.Col] == height+1)
                {
                    if (height == 8)
                        terminals.emplace({static_cast<int_fast8_t>(pos.Row-1), pos.Col});
                    else
                    {
                        path[++height] = 0;
                        pos.Row--;
                    }
                }
                break;
            case 1:
                if (pos.Col < WIDTH-1 && map[pos.Row][pos.Col+1] == height+1)
                {
                    if (height == 8)
                        terminals.emplace({pos.Row, static_cast<int_fast8_t>(pos.Col+1)});
                    else
                    {
                        path[++height] = 0;
                        pos.Col++;
                    }
                }
                break;
            case 2:
                if (pos.Row < HEIGHT-1 && map[pos.Row+1][pos.Col] == height+1)
                {
                    if (height == 8)
                        terminals.emplace({static_cast<int_fast8_t>(pos.Row+1), pos.Col});
                    else
                    {
                        path[++height] = 0;
                        pos.Row++;
                    }
                }
                break;
            case 3:
                if (pos.Col > 0 && map[pos.Row][pos.Col-1] == height+1)
                {
                    if (height == 8)
                        terminals.emplace({pos.Row, static_cast<int_fast8_t>(pos.Col-1)});
                    else
                    {
                        path[++height] = 0;
                        pos.Col--;
                    }
                }
                break;
            default:
                if (height > 0)
                    //remember that the previous path was already incremented
                    switch (path[height-1])
                    {
                        case 1:
                            pos.Row++;
                            break;
                        case 2:
                            pos.Col--;
                            break;
                        case 3:
                            pos.Row--;
                            break;
                        case 4:
                            pos.Col++;
                            break;
                    }
                height--;
                break;
        }
    }
}

int quick_branch2(const map_t& map, Point init)
{
    std::array<int_fast8_t, 9> path;
    int_fast8_t height = 0;
    path[0] = 0;
    int total = 0;
    Point pos = init;
    while (height >= 0)
    {
        switch (path[height]++)
        {
            case 0:
                if (pos.Row > 0 && map[pos.Row-1][pos.Col] == height+1)
                {
                    if (height == 8)
                        total++;
                    else
                    {
                        path[++height] = 0;
                        pos.Row--;
                    }
                }
                break;
            case 1:
                if (pos.Col < WIDTH-1 && map[pos.Row][pos.Col+1] == height+1)
                {
                    if (height == 8)
                        total++;
                    else
                    {
                        path[++height] = 0;
                        pos.Col++;
                    }
                }
                break;
            case 2:
                if (pos.Row < HEIGHT-1 && map[pos.Row+1][pos.Col] == height+1)
                {
                    if (height == 8)
                        total++;
                    else
                    {
                        path[++height] = 0;
                        pos.Row++;
                    }
                }
                break;
            case 3:
                if (pos.Col > 0 && map[pos.Row][pos.Col-1] == height+1)
                {
                    if (height == 8)
                        total++;
                    else
                    {
                        path[++height] = 0;
                        pos.Col--;
                    }
                }
                break;
            default:
                if (height > 0)
                    //remember that the previous path was already incremented
                    switch (path[height-1])
                    {
                        case 1:
                            pos.Row++;
                            break;
                        case 2:
                            pos.Col--;
                            break;
                        case 3:
                            pos.Row--;
                            break;
                        case 4:
                            pos.Col++;
                            break;
                    }
                height--;
                break;
        }
    }
    return total;
}

void main1(const map_t& map, const heads_t& heads)
{
    int total = 0;
    sols_t terminals;
    terminals.clear();
    // for (int8_t r = 0; r < map.size(); r++)
    // {
    //     for (int8_t c = 0; c < map[r].size(); c++)
    //     {
    //         if (map[r][c] == 0)
    //         {
    //             quick_branch(map, terminals, {r, c});
    //             total += terminals.size();
    //             terminals.clear();
    //         }
    //     }
    // }
    for (const Point& pos : heads)
    {
        quick_branch(map, terminals, pos);
        total += terminals.size();
        terminals.clear();
    }
    std::cout << "Part1 " << total << std::endl;
}

void main2(const map_t& map, const heads_t& heads)
{
    int32_t total = 0;
    // for (int8_t r = 0; r < map.size(); r++)
    // {
    //     for (int8_t c = 0; c < map[r].size(); c++)
    //     {
    //         if (map[r][c] == 0)
    //         {
    //             total += quick_branch2(map, {r, c});
    //         }
    //     }
    // }
    for (const Point& pos : heads)
    {
        total += quick_branch2(map, pos);
    }
    std::cout << "Part2 " << total << std::endl;
}

int main()
{
    map_t map;
    heads_t heads;
    load_map(map, heads, "10.txt");
    // std::print("{}", heads);
    // for (const auto& head : heads)
    //     std::cout << head << " ";
    // std::cout << std::endl;
    main1(map, heads);
    main2(map, heads);
    return 0;
}