AoC2022_Day24/main.cpp

#define OLC_PGE_APPLICATION
#include "pixelGameEngine.h"
#include "olcutils.h"

using namespace olc;

enum Direction{
    NORTH,
    EAST,
    SOUTH,
    WEST,
    INVALID
};

struct Blizzard{
    vi2d pos;
    Direction dir;
    bool moved=false;
};

int maxWidth=0;
vi2d playerPos={1,0};
std::vector<std::vector<std::vector<Blizzard>>>boardState;

std::vector<std::vector<Blizzard>> getBoard(int minute){
    if (minute<boardState.size()){
        return boardState[minute];
    } else {
        std::vector<std::vector<Blizzard>> prevBoardState=getBoard(minute-1);
        for (int y=0;y<prevBoardState.size();y++){
            std::vector<Blizzard>&blizzardList=prevBoardState[y];
            for (int x=0;x<blizzardList.size();x++){
                Blizzard&b=blizzardList[x];
                b.moved=false;
            }
        }
        for (int y=0;y<prevBoardState.size();y++){
            std::vector<Blizzard>&blizzardList=prevBoardState[y];
            blizzardList.reserve(100);
            for (int x=0;x<blizzardList.size();x++){
                Blizzard&b=blizzardList[x];
                if (!b.moved){
                    b.moved=true;
                    switch (b.dir){
                        case NORTH:{
                            vi2d dest={b.pos.x,b.pos.y-1};
                            if (dest.y<1){
                                dest.y=prevBoardState.size()-2;
                            }
                            b.pos=dest;
                            (&prevBoardState[dest.y])->push_back(b);
                            blizzardList.erase(blizzardList.begin()+x--);
                        }break;
                        case EAST:{
                            vi2d dest={b.pos.x+1,b.pos.y};
                            if (dest.x>=maxWidth-1){
                                dest.x=1;
                            }
                            b.pos=dest;
                        }break;
                        case SOUTH:{
                            vi2d dest={b.pos.x,b.pos.y+1};
                            if (dest.y>=prevBoardState.size()-1){
                                dest.y=1;
                            }
                            b.pos=dest;
                            (&prevBoardState[dest.y])->push_back(b);
                            blizzardList.erase(blizzardList.begin()+x--);
                        }break;
                        case WEST:{
                            vi2d dest={b.pos.x-1,b.pos.y};
                            if (dest.x<1){
                                dest.x=maxWidth-2;
                            }
                            b.pos=dest;
                        }break;
                    }
                }
            }
        }
        boardState.push_back(prevBoardState);
        return prevBoardState;
    }
}

vi2d targetPos={0,0};
int shortestDist=INFINITY;

bool spaceFree(std::vector<std::vector<Blizzard>>&board,const vi2d&pos){
    for (int i=0;i<board[pos.y].size();i++){
        Blizzard&b=board[pos.y][i];
        if (b.pos==pos){
            return false;
        }
    }
    return true;
}

void navigateToEnd(vi2d pos,int minute,std::string history){
    if (minute>shortestDist||minute>1000){
        return;//We don't care anymore.
    }
    if (pos==targetPos){
        if (shortestDist>minute){
            shortestDist=minute;
            std::cout<<"Shortest is now "<<shortestDist<<" ("<<history<<")."<<std::endl;
        }
        return;
    }
    std::vector<std::vector<Blizzard>>board=getBoard(minute);
    if (pos==vi2d{1,0}){
        if ((pos.y<board.size()-2||pos.y<board.size()-1&&pos.x==targetPos.x)&&spaceFree(board,{pos.x,pos.y+1})){
            //std::cout<<"Trying Down..."<<std::endl;
            navigateToEnd({pos.x,pos.y+1},minute+1,history+"-v");
        } else {
            navigateToEnd({pos.x,pos.y},minute+1,history+"-X");
        }
    } else {
        if (pos.x<maxWidth-2&&spaceFree(board,{pos.x+1,pos.y})){
            //std::cout<<"Trying Right..."<<std::endl;
            navigateToEnd({pos.x+1,pos.y},minute+1,history+"->");
        }
        if ((pos.y<board.size()-2||pos.y<board.size()-1&&pos.x==targetPos.x)&&spaceFree(board,{pos.x,pos.y+1})){
            //std::cout<<"Trying Down..."<<std::endl;
            navigateToEnd({pos.x,pos.y+1},minute+1,history+"-v");
        }
        if (pos.y>1&&spaceFree(board,{pos.x,pos.y-1})){
            //std::cout<<"Trying Up..."<<std::endl;
            navigateToEnd({pos.x,pos.y-1},minute+1,history+"-^");
        }
        if (pos.x>1&&spaceFree(board,{pos.x-1,pos.y})){
            //std::cout<<"Trying Left..."<<std::endl;
            navigateToEnd({pos.x-1,pos.y},minute+1,history+"-<");
        }
        navigateToEnd({pos.x,pos.y},minute+1,history+"-X");
    }
}

int main()
{
	std::ifstream file("testinput");
    std::vector<std::vector<Blizzard>>board;
    while (file.good()){
        std::string line;
        std::getline(file,line);
        if (line.length()>0){
            std::cout<<line<<std::endl;
            std::vector<Blizzard>boardRow;
            boardRow.reserve(100);
            for (int i=0;i<line.length();i++){
                if (line[i]!='#'&&line[i]!='.'){
                    boardRow.push_back({{i,(int)board.size()},line[i]=='^'?Direction::NORTH:line[i]=='>'?Direction::EAST:line[i]=='v'?Direction::SOUTH:line[i]=='<'?Direction::WEST:Direction::INVALID});
                }
            }
            maxWidth=line.length();
            board.push_back(boardRow);
        }
    }
    targetPos={maxWidth-2,(int)board.size()-1};
    std::cout<<targetPos<<std::endl;
    boardState.push_back(board);
    /*for (int d=0;d<boardState.size();d++){
        for (int y=0;y<boardState[d].size();y++){
            int prevBlizzard=-1;
            for (int x=0;x<boardState[d][y].size();x++){
                Blizzard&b=boardState[d][y][x];
                for (int k=prevBlizzard;k<b.pos.x-1;k++){
                    std::cout<<'.';
                }
                switch (b.dir){
                    case NORTH:{
                        std::cout<<'^';
                    }break;
                    case EAST:{
                        std::cout<<'>';
                    }break;
                    case SOUTH:{
                        std::cout<<'v';
                    }break;
                    case WEST:{
                        std::cout<<'<';
                    }break;
                    case INVALID:{
                        std::cout<<'?';
                    }break;
                }
                prevBlizzard=b.pos.x;
            }
            for (int k=prevBlizzard;k<maxWidth-1;k++){
                std::cout<<'.';
            }
            std::cout<<std::endl;
        }
    }*/
    for (int i=0;i<13;i++){
        std::cout<<"Board "<<i+1<<std::endl;
        std::vector<std::vector<Blizzard>>board=getBoard(i+1);
        for (int y=0;y<board.size();y++){
            int prevBlizzard=-1;
            std::vector<Blizzard>sorted=board[y];
            std::sort(sorted.begin(),sorted.end(),[](Blizzard&b1,Blizzard&b2){return b1.pos.x<b2.pos.x;});
            for (int x=0;x<sorted.size();x++){
                Blizzard&b=sorted[x];
                for (int k=prevBlizzard;k<b.pos.x-1;k++){
                    std::cout<<'.';
                }
                if (prevBlizzard<b.pos.x){
                    switch (b.dir){
                        case NORTH:{
                            std::cout<<'^';
                        }break;
                        case EAST:{
                            std::cout<<'>';
                        }break;
                        case SOUTH:{
                            std::cout<<'v';
                        }break;
                        case WEST:{
                            std::cout<<'<';
                        }break;
                        case INVALID:{
                            std::cout<<'?';
                        }break;
                    }
                    prevBlizzard=b.pos.x;
                }
            }
            for (int k=prevBlizzard;k<maxWidth-1;k++){
                std::cout<<'.';
            }
            std::cout<<std::endl;
        }
        std::cout<<"=================="<<std::endl<<std::endl;
    }
    navigateToEnd(playerPos,1,"");


	return 0;
}