baker.py

""" Script to find the (hopefully) least number of moves to solve a Waffle (wafflegame.net/)

The program works by greedily trying to find loops, in which N squares can be moved in a circle to where they should be,
which means we have corrected N squares in N-1 moves.

There's probably a lot of room for optimizations if you want it to run in 0.0000001 seconds instead of 0.000001.
(For example; I have never seen it need n squares in a loop and then later finding a loop with a length < n which
probably means logically it doesn't need to try shorter loops than the last loop found)

Author: Anton (@ntoonio)
Copyright: GPL-3.0-only
"""

class Square():
	def __init__(self, current: str, right: str):
		self._current = current
		self._right = right

	def isLocked(self):
		return self._current == self._right

	def getValue(self):
		return self._current

	def setValue(self, v):
		self._current = v

	def getCorrect(self):
		return self._right

class Board():
	def __init__(self, startLines, correctLines) -> None:
		self._squares = [x for x in self._bakeLines(startLines, correctLines)]

	@staticmethod
	def _bakeLines(startLines, correctLines):
		for i in range(0, 5):
			for j in range(0, len(startLines[i])):
				yield Square(startLines[i][j], correctLines[i][j])

	def iterateAll(self):
		return range(0, len(self._squares))
	
	def iterate(self):
		return [i for i in self.iterateAll() if not self.getSquare(i).isLocked()]

	def getSquare(self, i):
		return self._squares[i]

	def value(self, i):
		return self.getSquare(i).getValue()

	def correct(self, i):
		return self.getSquare(i).getCorrect()

	def move(self, a, b):
		c = self.value(a)

		self.getSquare(a).setValue(self.value(b))
		self.getSquare(b).setValue(c)

	def isCompleted(self):
		return len(self.iterate()) == 0

	def print(self):
		for i in self.iterateAll():
			s = self.getSquare(i)
			print(("\033[92m" if s.getCorrect() == s.getValue() else "") + s.getValue() + "\033[0m ", end="")

			if i in [4, 7, 12, 15, 20]:
				print()

			if i in [5, 6, 13, 14]:
				print("  ", end="")


def _findLoopFrom(board: Board, start: int, square: int, length: int, visited: list[int]):
	if length == 0:
		return False

	newVisited = visited.copy()
	newVisited.append(square)

	for i in board.iterate():
		if i in visited:
			continue

		if board.correct(square) == board.value(i):
			if length == 1 and board.correct(i) == board.value(start):
					return [i, square]
			else:
				stack = _findLoopFrom(board, start, i, length - 1, newVisited)

				if stack != False:
					stack.append(square)
					return stack
	return False

def findLoopFrom(board, start, length):
	return _findLoopFrom(board, start, start, length - 1, [])

def applyLoop(board: Board, loop: list[int]):
	lastSquare = loop[-1]

	for l in loop:
		board.move(lastSquare, l)

def solve(board):
	while not board.isCompleted():
		resetLength = False

		for l in range(2, len(board.iterate()) + 1):
			if resetLength:
				break

			for s in board.iterate():
				loop = findLoopFrom(board, s, l)

				if loop != False:
					print("Applying loop", loop, "of length", l)
					applyLoop(board, loop)
					board.print()
					resetLength = True
					break

def main():

	# DAILY WAFFLE #250
	
	#
	# 1   A P S E E
	#     U   O   S
	# 2   I D P U P
	#     R   M   H
	# 3   N S E E R
	#
	#     4   5   6
	#

	startLines = ["apsee", "uos", "idpup", "rmh", "nsere"]

	#
	# 1   A M U S E
	#     S   P   R
	# 2   H I P P O
	#     E   E   D
	# 3   N U R S E
	#
	#     4   5   6
	#

	correctLines = ["amuse", "spr", "hippo", "eed", "nurse"]

	B = Board(startLines, correctLines)
	solve(B)

if __name__ == "__main_":
	main()