december2022.py

import numpy as np

# 2D representation of die
"""
ex:
unreachable = B, die =
[[ 0.  D.  0.]
 [ R.  T.  L.]
 [ 0.  U.  0.]]
T is the top of the die, and represents the current value of the die.
If the die moves one space up in the grid in its current state, you get U, down you get D.
If the die moves right, you get R, left you get L.
B is on the bottom of the die.
After each move, unreachable is swapped into the matrix.

For instance if you move up, then your state will become
unreachable = D, die =
[[ 0.  T.  0.]
 [ R.  U.  L.]
 [ 0.  B.  0.]]
Note how D is now unreachable, and B is in the matrix now.
"""
class Die:
    def __init__(self):
        # inf = uninitialized value of die
        self.die = np.full((3, 3), np.inf)
        # corners give no information
        self.die[0,0] = self.die[0,2] = self.die[2,0] = self.die[2,2] = 0
        self.unreachable = np.inf # the bottom of the die
                
    def __str__(self):
        return f"unreachable = {self.unreachable}, die = \n{self.die}"
                
    @property
    def val(self):
        return self.die[1,1]
    
    @val.setter
    def val(self, value):
        self.die[1,1] = value
    
    # helper function
    def swapUnreachable(self, i, j):
        self.unreachable, self.die[i,j] = self.die[i,j], self.unreachable
        
    def up(self):
        self.die[:,1] = np.roll(self.die[:,1], -1)
        self.swapUnreachable(-1, 1)
    
    def right(self):
        self.die[1,:] = np.roll(self.die[1,:], 1)
        self.swapUnreachable(1, 0)
    
    def down(self):
        self.die[:,1] = np.roll(self.die[:,1], 1)
        self.swapUnreachable(0, 1)
    
    def left(self):
        self.die[1,:] = np.roll(self.die[1,:], -1)
        self.swapUnreachable(1, -1)

class Solver:
    def __init__(self, board, root, leaf):
        self.board = board
        self.root = root
        self.leaf = leaf
        self.die = Die()
        self.n = 0
        self.score = 0
        self.path = np.zeros_like(self.board) # grid of how many times each square was visited in final solution
        self.order = [] # list of coordinates traversed in final solution
        
    def valid(self, i, j):
        return 0 <= i < self.board.shape[0] and 0 <= j < self.board.shape[1]
    
    def dfs(self, i, j):
        wasInf = False
        newScore = self.score
        
        if not self.valid(i, j):
            return False
        if self.n > 0:
            if self.die.val == np.inf: # set the die value
                wasInf = True
                newScore = self.board[i,j]
                self.die.val = (newScore - self.score) / self.n
                #print(self.die)
                #print(f"n = {self.n}, die val = {self.die.val}, at ({i},{j})")
                #input(self.board)
            else: # check the die value works
                newScore = self.score + self.n * self.die.val
                if newScore != self.board[i,j]:
                    return False
                
        self.score, newScore = newScore, self.score # update the score and remember the old score    
        self.path[i,j] += 1
        if (i, j) == self.leaf: # reached solution
            self.order.append((i,j))
            return True
        
        self.n += 1
        
        self.die.up()
        if self.dfs(i - 1, j):
            self.order.append((i,j))
            return True
        self.die.down()
        
        self.die.down()
        if self.dfs(i + 1, j):
            self.order.append((i,j))
            return True
        self.die.up()
        
        self.die.left()
        if self.dfs(i, j - 1):
            self.order.append((i,j))
            return True
        self.die.right()
        
        self.die.right()
        if self.dfs(i, j + 1):
            self.order.append((i,j))
            return True
        self.die.left()
        
        self.n -= 1
        self.path[i,j] -= 1
        if wasInf: # reset die val to inf
            self.die.val = np.inf

        self.score, newScore = newScore, self.score # reset the score to old score            
        return False

    def solve(self):
        r = self.dfs(self.root[0], self.root[1])
        self.order.reverse()
        return r

if __name__ == "__main__":
    board = [57, 33, 132, 268, 492, 732, 81, 123, 240, 443, 353, 508, 186, 42, 195, 704, 452, 228, -7, 2, 357, 452, 317, 395, 5, 23, -4, 592, 445, 620, 0, 77, 32, 403, 337, 452]
    board = np.array(board).reshape((6, 6))
    print(board)
    
    root = (5, 0)
    leaf = (0, 5)
    print(board[root], board[leaf])
    
    s = Solver(board, root, leaf)
    print(s.solve())
    
    print(s.path)
    print(s.order)
    unvisitedSum = s.board[~s.path.astype(bool)].sum()
    print(f"sum = {unvisitedSum} with die:\n{s.die}")
    
    if 0: # print path with 9s
        temp = 9
        for o in s.order:
            print()
            temp, s.path[o] = s.path[o], temp
            print(s.path)
            temp, s.path[o] = s.path[o], temp