Neopets fast shapeshifter solver

shapeshifter.py

from pulp import *

board = '0040040400000,4434244404040,4433242322330,0040443314340,0000004010244,0004043442044,0003434302334,0444334004030,4403334004444,0333400404334,0040044440404,0040004444000,0434000403440,0404000444000'.split(',') #assuming I always want to get to 0
modulo = 5
pieces = ".X.X,XX.X,.XXX,XX.. XXX ..X,XXX,X.. XXX,X..,X.. X,X,X X.X,XXX X..,XX.,.XX XX,XX XX X.X,XXX,X.X .XXX,..X.,XXX. X.X,XXX X..,XXX,..X X XX.X,X..X,XXXX,..X. XX.,.XX X.X,XXX,X.X XX.,.XX X.X,X.X,XXX XXX,X.X,XXX .X..,XX.X,.XXX ...X,X.XX,X.X.,XXX.,X.X. XXX,X.X X.X,XXX XXXX,X...,X... X..,XX.,.XX .XX.,XX..,.XXX XXX.,..XX,XXX.,.X..".replace('.', '0').replace('X', '1').split(' ')

pieces = list(map(lambda x: x.split(','), pieces))

piecesPossiblePlacements = [] # at which x, y we can plece each piece

for idx, piece in enumerate(pieces):
	piecesPossiblePlacements.append([])
	for y in range(0, len(board) - len(piece) + 1):
		for x in range(0, len(board[0]) - len(piece[0]) + 1):
			piecesPossiblePlacements[idx].append((x, y))

usePlacement = [[LpVariable("use{0}-{1}".format(i, j), cat="Binary") for j in range(len(piecesPossiblePlacements[i]))] for i in range(len(piecesPossiblePlacements))] # whether we use the possiblePlacement or not
boardVars = [[LpVariable("board{0}-{1}".format(i, j), 0, len(pieces) + modulo, cat="Integer") for j in range(len(board[0]))] for i in range(len(board))] # how many times each cell changed shape + the initial board value 
multipliers = [[LpVariable("multiplier{0}-{1}".format(i, j), 0, len(pieces) // modulo + 1, cat="Integer") for j in range(len(board[0]))] for i in range(len(board))] # we use this to force boardVars to end up with the goal we want, modulo * some multiplier
#LpSolverDefault.msg = 1

prob = LpProblem('ShapeShipfter', LpMinimize)
prob += 0 # we don't really care about minimizing anything in this case, only care about constraints

vals = []

for y, row in enumerate(board):
	vals.append([])
	board[y] = [int(x) for x in row]
	for x, cell in enumerate(row):
		vals[y].append([board[y][x]]) # we load initial board values


for i, placements in enumerate(piecesPossiblePlacements):
	prob += lpSum([usePlacement[i][j] for j in range(len(placements))]) == 1 # we can use each piece only once + we must use it
	piece = pieces[i]
	for j, placement in enumerate(placements):
		for y in range(len(piece)):
			for x in range(len(piece[0])):
				if piece[y][x] == '1':
					vals[y + placement[1]][x + placement[0]].append(usePlacement[i][j])


for y, row in enumerate(board):
	for x, cell in enumerate(row):
		prob += boardVars[y][x] == lpSum(vals[y][x]) # boardVars[y][x] will be equal to the the initial board[y][x] + all the pieces we used that touched that spot
		prob += boardVars[y][x] == multipliers[y][x] * modulo # we further restrict it to end up as x * modulo (meaning it will end with the piece we want it to)

status = prob.solve()

print(LpStatus[status])
print("Objective value:", value(prob.objective))
print("Time taken", str(prob.solutionTime) + "s")
print ('\nThe values of the variables : \n')

for i, placements in enumerate(piecesPossiblePlacements):
	for j, placement in enumerate(placements):
		piece = pieces[i]
		if usePlacement[i][j].varValue == 1:
			print(f"place piece {i} at column {placements[j][0]}, row {placements[j][1]}")
			for y in range(len(piece)):
				for x in range(len(piece[0])):
					if piece[y][x] == '1':
						board[y + placement[1]][x + placement[0]] += 1 

print("\nboard")

for y, row in enumerate(board):
	r = ""
	for x, cell in enumerate(row):
		r += str(board[y][x] % modulo)
	print(r)