#advent of code 2024
#day 15
#could probably reduce the length of code even more
#if I were to index the part2 box 
#instead of hardcoding the left and right part of the box
#but w/e, I don't feel like doing it 
#the code is ~110 lines of code shorter after cleaning up
#explanation:
#given: picture of the grid (fg) and robots movement list (movement)
#create 2 grids: grid1 and grid2 for part 1 and part 2 respectively
#for part 2 the grid is made wider x2: the grid2 is created with
#resizing dictionary to know what to insert where
#there are 3 functions: GPS, movebox, stackbox
#GPS calculates the result required by puzzle after simulating 
#the movement of the robot
#the box variable is a list of characters that are considered a box
#for each part of a puzzle: O for part 1, [ and ] for part 2
#the thing is that by making it into a list, I don't need 
#separate functions for each part: the logic checks if 
#the current tile is equal to the last or the first element of this list
#to determine whether or not it's a box
#for list of length 1, element with index 0 and -1 are the same
#next it iterates over each step of the robot's movement in movement list
#before the robot moves, it checks what is in it's way
#if it's a floor ("."), then it takes a step 
#if it's a wall ("#"), it stands in the same spot
#if it's a box, it runs the movebox or stackbox function 
#to determine if it's viable or not
#stackbox is a function that is run only for part2 if the robot
#wants to push boxes up or down. if it's part 1 or it moves left or right
#it uses movebox function
#movebox function scans the grid in the provided direction 
#(accordingly with robots desired movement) as long as it meets
#a wall tile or floor tile. if it's a wall: can't move
#if it's a floor, then for each tile in the path, from last tile to the first
#move each tile in given direction
#stackbox function queues each tile with a box 
#and checks if something is above or below (depending on the robots direction)
#if there's another box, it queues up that tile and it's counterpart
#(left or right) to check it again recursively
#if at any moment there's a wall in the path, the robot can't move
#if the final tiles don't have only floor tiles above or below them,
#then each box tile is moved one step in correct direction,
#leaving behind a free space
#this comment is as long as solutions for days 1-13
#but I just fucking know that I'll look this up one day and will
#not remember anything 
grid1 = {};
grid2 = {};
dirs = {};
dirs["^"] = (0,-1);
dirs["v"] = (0,1);
dirs["<"] = (-1,0);
dirs[">"] = (1,0);
resizing = {};
resizing["#"] = "##";
resizing["O"] = "[]";
resizing["."] = "..";
resizing["@"] = "@."; 

f = open("15.in","r");
fg, movement = f.read().split("\n\n");
movement = movement.replace("\n","");
for y,l in enumerate(fg.split("\n")):
	for x,c in enumerate(l.strip()):
		if c == "@":
			robot1 = (x,y);
			robot2 = (2*x,y);
			c = ".";
		grid1[(x,y)] = c;
		for offset in range(2):
			grid2[(2*x+offset,y)] = resizing[c][offset];
f.close();

def movebox(BoxPos,direction,grid,box,p2):
	valid = True;
	bx, by = BoxPos; #coordinates of 1st box to push
	dirx,diry = direction; 
	distance = 1; #python ranges are exclusive on outside
	NextTile = grid.get((bx+distance*dirx,by+distance*diry),"#");
	while NextTile == box[0] or NextTile == box[-1]:
		distance += 1;
		NextTile = grid.get((bx+distance*dirx,by+distance*diry),"#");
	LastTile = grid.get((bx+distance*dirx,by+distance*diry),"#");
	if LastTile == "#": #if wall, can't move
		valid = False;
	else: #replace each box in the way step by step in reversed order
		for dist in range(distance):
			NewPosition  = (bx+distance*dirx -dist*dirx,by+distance*diry -dist*diry);
			PrevPosition = (bx+distance*dirx -dist*dirx -dirx,by + distance*diry - dist*diry - diry);
			grid[NewPosition] = grid[PrevPosition];
			grid[PrevPosition] = ".";
	return valid;

def stackbox(BoxPos,direction,grid,box,p2):
	valid = True;
	bx,by = BoxPos;
	dirx,diry = direction;
	if grid[BoxPos] == box[0]: BoxPos2 = (bx+1,by,box[-1]);
	else: BoxPos2 = (bx-1,by,box[0]);
	queue = [(bx,by,grid[BoxPos]),BoxPos2]; #each part of the box is a separate entry in queue
	BoxesToMove = queue.copy(); 
	while queue:
		PosToCheck = [];
		for queuedpos in queue:
			BX,BY,dummy = queuedpos; #dummy not needed for queue loop, needed later
			NextTile = grid[(BX,BY+diry)];
			if NextTile == box[0]:
				PosToCheck.append((BX,BY+diry,NextTile));
				PosToCheck.append((BX+1,BY+diry,grid[(BX+1,BY+diry)]));
			elif NextTile == box[-1]:
				PosToCheck.append((BX,BY+diry,NextTile));
				PosToCheck.append((BX-1,BY+diry,grid[(BX-1,BY+diry)]));
			elif NextTile == "#":
				valid = False;
				break;
		if valid: 
			queue = PosToCheck.copy();
			BoxesToMove.extend(PosToCheck);
		else:
			BoxesToMove = [];
			queue = [];
	BoxesToMove = sorted(BoxesToMove, key = lambda k: k[1],reverse=diry>0);
	for BoxToMove in BoxesToMove:
		boxx,boxy,prevtile = BoxToMove;
		grid[(boxx,boxy+diry)] = prevtile;
		grid[(boxx,boxy)] = ".";
	return valid;

def GPS(grid,robot,p2):
	box = ["O"];
	if p2: box = ["[","]"];
	for d in movement:
		dx,dy = dirs[d];
		rx,ry = robot;
		NextPos = (rx+dx,ry+dy);
		tile = grid.get(NextPos,"#");
		if tile == "#": #if wall, dont move
			ok = False;
		elif tile == box[0] or tile == box[-1]: #if boxes in the way, move boxes first
			if p2 and dy != 0:
				ok = stackbox(NextPos,dirs[d],grid,box,p2);
			else:
				ok = movebox(NextPos,dirs[d],grid,box,p2);
		else: #if nothing in the way, then move
			ok = True;
		robot = (rx+ok*dx,ry+ok*dy);
	score = 0;	
	for g in grid:
		if grid[g] == box[0]: score += 100*g[1] + g[0];
	return score;

part1 = GPS(grid1,robot1,False);
part2 = GPS(grid2,robot2,True);
print("part 1 =", part1);
print("part 2 =", part2);