path: root/oo.py

import curses
import random

class ooPuzzle:
    """Encapsulates a oo puzzle state.

    No rendering information is stored or interpreted here.

    All attributes are intended to be accessed through methods.
    If direct access is necessary, here are their explanations:

    (the following attributes are constant)

        DIRECTIONS is a dictionary mapping:
            each direction as a string
            to a direction index in range(4)
            
        DX_DY is a list mapping:
            each direction index in range(4)
            to a differential of form (dx, dy)
            
        EDGES_TO_PIECE_ORIENT is a dictionary mapping:
            each tuple of edge-filled statuses in order of direction
            to a tuple of (piece id in range(6),
                           orientation direction in range(4))
                           
        PIECE_ORIENT_TO_EDGES is an inverse of the previous mapping.
        
    (the following attributes are set by __init__)

        X is an integer for the range of x-positions

        Y is an integer for the range of y-positions

        game_id is an integer used by set_pieces_from_game_id
            It uniquely corresponds to the solution.

        toroidal is a bool indicating whether
            the border of the puzzle loops back to the opposite side

    (the following attributes are variable during normal use)

        pieces is a dictionary mapping:
            each position of form (x in range(self.X),
                                   y in range(self.Y))
            to a piece id in range(6)

        inverted_pieces is a closely related mapping to pieces,
        where all edges swap filled state
        NOT IMPLEMENTED

        not_inverted_pieces is similar, but only swaps border edges
        NOT IMPLEMENTED
            
        orients is a dictionary mapping:
            each position of form (x in range(self.X),
                                   y in range(self.Y))
            to a direction index in range(4)
    """

    def __init__(self, X, Y, game_id=None, toroidal=False):
        """Create a new ooPuzzle instance.

        Arguments.
                 X,Y : horizontal and vertical size of the puzzle
             game_id : passed to ooPuzzle.set_pieces_from_game_id
            toroidal : bool for looping around the end of the puzzle
        """
        self.X, self.Y = X, Y
        self.toroidal = toroidal
        self.pieces  = {}
        self.orients = {}
        self.set_pieces_from_game_id(game_id)

    # Changing conceptual directions into indices.
    DIRECTIONS = {'LEFT' : 0,
                  'UP'   : 1,
                  'RIGHT': 2,
                  'DOWN' : 3}

    # Changing direction indices into (dx, dy) pairs.
    DX_DY = [(-1,  0),
             ( 0, -1),
             ( 1,  0),
             ( 0,  1)]

    # Given piece id and orientation direction,
    # return edge-filled status for each direction.
    PIECE_ORIENT_TO_EDGES = { (0, 0) : (0, 0, 0, 0),
                              (0, 1) : (0, 0, 0, 0),
                              (0, 2) : (0, 0, 0, 0),
                              (0, 3) : (0, 0, 0, 0),

                              (1, 0) : (1, 0, 0, 0),
                              (1, 1) : (0, 1, 0, 0),
                              (1, 2) : (0, 0, 1, 0),
                              (1, 3) : (0, 0, 0, 1),

                              (2, 0) : (1, 1, 0, 0),
                              (2, 1) : (0, 1, 1, 0),
                              (2, 2) : (0, 0, 1, 1),
                              (2, 3) : (1, 0, 0, 1),

                              (3, 0) : (1, 0, 1, 0),
                              (3, 1) : (0, 1, 0, 1),
                              (3, 2) : (1, 0, 1, 0),
                              (3, 3) : (0, 1, 0, 1),

                              (4, 0) : (0, 1, 1, 1),
                              (4, 1) : (1, 0, 1, 1),
                              (4, 2) : (1, 1, 0, 1),
                              (4, 3) : (1, 1, 1, 0),

                              (5, 0) : (1, 1, 1, 1),
                              (5, 1) : (1, 1, 1, 1),
                              (5, 2) : (1, 1, 1, 1),
                              (5, 3) : (1, 1, 1, 1) }

    # One choice of inverse of the previous dictionary.
    EDGES_TO_PIECE_ORIENT = { (0, 0, 0, 0) : (0, 0),

                              (1, 0, 0, 0) : (1, 0),
                              (0, 1, 0, 0) : (1, 1),
                              (0, 0, 1, 0) : (1, 2),
                              (0, 0, 0, 1) : (1, 3),

                              (1, 1, 0, 0) : (2, 0),
                              (0, 1, 1, 0) : (2, 1),
                              (0, 0, 1, 1) : (2, 2),
                              (1, 0, 0, 1) : (2, 3),

                              (1, 0, 1, 0) : (3, 0),
                              (0, 1, 0, 1) : (3, 1),

                              (0, 1, 1, 1) : (4, 0),
                              (1, 0, 1, 1) : (4, 1),
                              (1, 1, 0, 1) : (4, 2),
                              (1, 1, 1, 0) : (4, 3),

                              (1, 1, 1, 1) : (5, 0) }

    ####
    #
    # The following methods are low-level,
    # and require position inputs to be forced in range.
    #
    ####

    def get_piece(self, x, y):
        x %= self.X
        y %= self.Y
        return self.pieces[x, y]

    def get_orient(self, x, y):
        x %= self.X
        y %= self.Y
        return self.orients[x, y]

    def get_piece_orient(self, x, y):
        x %= self.X
        y %= self.Y
        return self.pieces[x, y], self.orients[x, y]

    def get_adj_pos(self, x0, y0, direction,
            return_is_internal=False):
        """Returns the position adjacent to (x0, y0) in direction.
        
        direction may be any string or integer in the dictionary
            self.DIRECTIONS (case insensitive)

        If return_is_internal, then a third output is returned,
            a bool for whether both edges are internal.
            (If false, then the edges are across a border.)
        """
        x0 %= self.X
        y0 %= self.Y
        if type(direction) is str:
            direction = self.DIRECTIONS[direction.upper()]
        dx, dy = self.DX_DY[direction]
        x1 = (x0 + dx) % self.X
        y1 = (y0 + dy) % self.Y

        if return_is_internal:
            is_internal = (
                    x0 + dx == x1 and
                    y0 + dy == y1 )
            return x1, y1, is_internal

        return x1, y1

    def set_piece(self, x, y, value):
        x %= self.X
        y %= self.Y
        self.pieces[x, y] = value

    def set_orient(self, x, y, value):
        x %= self.X
        y %= self.Y
        self.orients[x, y] = value

    def set_piece_orient(self, x, y, value):
        x %= self.X
        y %= self.Y
        self.pieces[x, y], self.orients[x, y] = value

    def set_pieces_from_edges(self, horiz_edges, vert_edges):
        """Convert edge dictionaries into a puzzle state.

        Adjacent edges in a solution must be
        either both filled or both unfilled,
        and so a bit of data is assigned to each pair.
        
        vert_edges is the dictionary for vertical pairs
          key: (x, row)
            x: the usual x-coordinate of the piece
          row: the y-coordinate or y+1, depending on whether
               you want the pair above or below the piece
             : row == 0 and row == self.Y are border edges
               so it's good to think of row as 1-indexed
        
        horiz_edges is the dictionary for horizontal pairs
          key: (col, y)
          col: the x-coord or x+1, same as row but left or right
            y: the usual y-coord
        """
        for x in range(self.X):
            for y in range(self.Y):

                left  = horiz_edges[x  , y]
                right = horiz_edges[x+1, y]
                up   = vert_edges[x, y  ]
                down = vert_edges[x, y+1]

                piece, orient = \
                    self.EDGES_TO_PIECE_ORIENT[left, up, right, down]
                self.pieces [x, y] = piece
                self.orients[x, y] = orient

    def set_pieces_from_game_id(self, game_id=None):
        """Convert game_id value into a solution puzzle state.

        game_id is an integer
            if     toroidal: in range(2**( 2*X*Y ))
            if not toroidal: in range(2**( (X-1)*Y + X*(Y-1) ))
        if None, then a random game_id is generated
        """

        # compute:
        #  n_horiz, the number of horizontal edge pairs
        #  n_vert,  the number of  vertical  edge pairs

        shift = -int(not self.toroidal)
        n_col = self.X + shift
        n_row = self.Y + shift
        n_horiz =  n_col * self.Y
        n_vert  = self.X * n_row

        # generate and record game_id

        if game_id == None:
            game_id = random.randrange(0, 2**(n_horiz + n_vert))
        self.game_id = game_id

        # prepare to record edges for self.set_pieces_from_edges

        vert_edges  = {}
        horiz_edges = {}

        # set the right and bottom border edges
        # if toroidal, these will be overwritten in the next step

        for x in range(self.X):
            vert_edges[x, self.Y] = 0

        for y in range(self.Y):
            horiz_edges[self.X, y] = 0

        # set the edges determined by game_id

        for i in range(n_vert):
            row, x = divmod(i, self.X)
            game_id, bit = divmod(game_id, 2)
            vert_edges[x, row+1] = bit

        for i in range(n_horiz):
            col, y = divmod(i, self.Y)
            game_id, bit = divmod(game_id, 2)
            horiz_edges[col+1, y] = bit

        # make the left and top border edges match the opposite sides

        for y in range(self.Y):
            horiz_edges[0, y] = horiz_edges[self.X, y]

        for x in range(self.X):
            vert_edges[x, 0] = vert_edges[x, self.Y]

        # turn edges into pieces

        self.set_pieces_from_edges(horiz_edges, vert_edges)

    ####
    #
    # The following methods are high-level,
    # and no longer require position inputs to be forced in range.
    #
    # (They call the low-level functions when needed.)
    #
    ####

    def rotate_cw(self, x, y, turns=1):
        """Rotates the piece at (x, y) by clockwise turns."""
        o = self.get_orient(x, y)
        o = (o + turns) % 4
        self.set_orient(x, y, o)

    def random_orients(self):
        """Randomly rotate the current pieces."""
        for x in range(self.X):
            for y in range(self.Y):
                self.set_orient(x, y, random.randrange(4))
        
    def get_edge_pair(self, x0, y0, direction):
        """Returns the edge pair's filled status in direction and is_internal.

        direction may be any string or integer in the dictionary
            self.DIRECTIONS (case insensitive)

        The first output is the status of the edge of (x0, y0) in direction.

        The second output is the status of the adjacent edge,
            that is, of the piece adjacent to (x0, y0) in direction,
            the status of the edge in the opposite direction.

        The third output is a bool for whether both edges are internal.
            (If false, then the edges are across a border.)
        """
        if type(direction) is str:
            direction = self.DIRECTIONS[direction.upper()]

        piece, orient = self.get_piece_orient(x0, y0)
        edge0 = self.PIECE_ORIENT_TO_EDGES[piece, orient][direction]

        x1, y1, is_internal = \
                self.get_adj_pos(x0, y0, direction,
                                 return_is_internal=True)
        piece, orient = self.get_piece_orient(x1, y1)
        direction = (direction + 2) % 4
        edge1 = self.PIECE_ORIENT_TO_EDGES[piece, orient][direction]

        return edge0, edge1, is_internal

    def check_edge_pair(self, x, y, direction, if_filled=False):
        """Check the edge pair's validity around (x, y) in direction.
        
        If if_filled, then only check the edge pair if the base edge is filled.
        """
        e0, e1, is_internal = self.get_edge_pair(x, y, direction)
        if if_filled and not e0: return True
        if not is_internal and not self.toroidal:
            return not e0 and not e1
        return e0 == e1

    def check_piece(self, x, y, if_filled=True):
        """Check the validity of edge pairs around (x, y).

        if_filled is passed on to check_edge_pair
        """
        for direction in self.DIRECTIONS:
            if not self.check_edge_pair(x, y, direction, if_filled):
                return False
        return True

    def is_solved(self):
        """Check whether the puzzle is in a solved state."""
        for x in range(self.X):
            for y in range(self.Y):
                if not self.check_edge_pair(x, y, "RIGHT"):
                    return False
                if not self.check_edge_pair(x, y, "DOWN"):
                    return False
        return True

class ooPlay:
    """Encapsulates an oo game instance.
    
    Renders and interacts with an ooPuzzle instance using curses.
    """
    def __init__(self, screen):
        """Create a new ooPlay instance.

        Arguments.
            scr : curses screen object used for display
        """
        self.screen = screen
        self.Y, self.X = self.screen.getmaxyx()
        self.puzzle = ooPuzzle(self.X, self.Y-2)
        self.puzzle.random_orients()

        # set up colors
        curses.start_color()
        if curses.can_change_color():
            curses.init_color(curses.COLOR_GREEN, 0, 300, 0)
            curses.init_color(curses.COLOR_BLUE, 0, 0, 300)

        def color_pair(n):
            fg = curses.COLOR_WHITE
            bg = curses.COLOR_BLACK
            n, bit = divmod(n, 2)
            if bit: bg = curses.COLOR_GREEN  # for checkering
            n, bit = divmod(n, 2)
            if bit: fg = curses.COLOR_RED    # for showing errors
            n, bit = divmod(n, 2)
            if bit: bg = curses.COLOR_BLUE   # for cursor
            n, bit = divmod(n, 2)
            if bit: fg = curses.COLOR_YELLOW # for fixed
            return fg, bg

        for n in range(1, 2**4):
            curses.init_pair(n, *color_pair(n))

        # initialize flags
        self.help_ind = 0
        self.inverted = False
        self.toroidal = False
        self.extra_hard = False
        self.show_errors = False
        self.fixed = {}
        for position in self.puzzle.pieces:
            self.fixed[position] = False

        # draw the board state and help area
        self.screen.clear()
        self.display()
        self.write()
        curses.curs_set(0)

        # start the main loop
        self.xpos, self.ypos = 0, 0
        self.max_xpos = self.puzzle.X - 1
        self.max_ypos = self.puzzle.Y - 1
        self.keyloop()

    def new_game(self):
        """Restarts an already-running ooPlay instance.
        
        Flags are preserved, and toroidal is implemented.
        toroidal is also passed to ooPuzzle at this point,
        so self.toroidal == self.puzzle.toroidal afterwards.
        """
        self.Y, self.X = self.screen.getmaxyx()
        if self.toroidal:
            self.X = (self.X // 2) * 2
            self.Y = (self.Y // 2) * 2
            X = self.X       // 2
            Y = (self.Y - 2) // 2
        else:
            X = self.X
            Y = self.Y - 2
        self.puzzle = ooPuzzle(X, Y, toroidal = self.toroidal)
        #TODO: this implementation of extra_hard can be really slow
        if self.extra_hard:
            while True:
                for piece in self.puzzle.pieces.values():
                    if piece in [0, 5]:
                        break
                else:
                    break
                self.puzzle.set_pieces_from_game_id()
        self.puzzle.random_orients()

        # reset some flags
        self.show_errors = False
        for position in self.puzzle.pieces:
            self.fixed[position] = False

        # draw the board state and help area
        self.screen.clear()
        self.display()
        self.write()

        # return to the main loop
        self.xpos, self.ypos = 0, 0
        self.max_xpos = self.puzzle.X * (1 + self.toroidal) - 1
        self.max_ypos = self.puzzle.Y * (1 + self.toroidal) - 1

    PIECE_ORIENT_TO_STRING = \
        ["    ",
         "╸╵╺╷",
         "┙┕┍┑",
         "━│━│",
         "┝┯┥┷",
         "┿┿┿┿"]

    def is_fixed(self, x, y):
        x %= self.puzzle.X
        y %= self.puzzle.Y
        return self.fixed[x, y]

    def toggle_fixed(self, x, y):
        x %= self.puzzle.X
        y %= self.puzzle.Y
        self.fixed[x, y] = not self.fixed[x, y]

    def display_subroutine(self, x, y, recursing=False, cursor=None):
        """Update one position on the board."""
        #TODO: use inverted_pieces and not_inverted_pieces
        #      if self.inverted
        piece, orient = self.puzzle.get_piece_orient(x, y)
        string = self.PIECE_ORIENT_TO_STRING[piece][orient]
        is_error = False
        if self.show_errors:
            is_error = not self.puzzle.check_piece(x, y)
        color_val = (1*(x + y) % 2        +
                     2*is_error           +
                     4*bool(cursor)       +
                     8*self.is_fixed(x, y))
        color = curses.color_pair(color_val)
        self.screen.addstr(y, x, string, color)
        if self.puzzle.toroidal and not recursing:
            X, Y = self.puzzle.X, self.puzzle.Y
            x1 = (x + X) % (2*X)
            y1 = (y + Y) % (2*Y)
            self.display_subroutine(x1, y , recursing=True, cursor=cursor)
            self.display_subroutine(x , y1, recursing=True, cursor=cursor)
            self.display_subroutine(x1, y1, recursing=True, cursor=cursor)

    def display_pos(self, x, y, cursor=None):
        """Update one position on the board, refresh screen."""
        self.display_subroutine(x, y, cursor=cursor)
        if self.show_errors or cursor:
            for direction in self.puzzle.DIRECTIONS:
                x1, y1 = self.puzzle.get_adj_pos(x, y, direction)
                self.display_subroutine(x1, y1)
        self.screen.refresh()

    def display(self):
        """Update the state of the board, refresh screen."""
        for x in range(self.puzzle.X):
            for y in range(self.puzzle.Y):
                self.display_subroutine(x, y)
        self.screen.refresh()

    pause_length = 80
    def sleep(self, delay=1):
        """Like most sleep functions, but can be escaped with spacebar.
        
        delay is in units of self.pause_length,
            the standard delay per char for the class.
            delay may be a positive integer or float.

        Implementation is such that keypresses other than spacebar
            can shorten or lengthen the pause,
            but the pause is capped at twice the intended delay.

        Returns True if spacebar was pressed.
        """
        pause = int(self.pause_length * delay)
        self.screen.timeout(pause)
        while True:
            inp = self.screen.getch()
            if inp == -1:
                space_pressed = False
                break
            if inp == ord(" "):
                space_pressed = True
                break
            pause //= 2
            self.screen.timeout(pause)
        self.screen.timeout(-1)
        return space_pressed

    def write(self, string=None, pause=None):
        """Write string to the bottom line.
        
        if string is narrower than line:
            centers string within the line
        if string is wider than line:
            scrolls through string

        if a string is not given, then "H" is used
        if pause is True, there will be a pause for reading at the end
        if pause is not given but a string is, there will be a pause
        if neither a pause nor a string is given, there will not be a pause

        ooPlay.pause_length
            is the number of milliseconds per character to pause
        """
        if string == None:
            string = "H"
            if pause == None:
                pause = False
        if pause == None:
            pause = True
        width = self.X - 1
        color = curses.color_pair(int(pause))
        border_line = self.X * "═"
        self.screen.addstr(self.Y - 2, 0, border_line, color)

        # writing a string that fits in the width

        if len(string) <= width:
            centered_string = string.center(width, " ")
            self.screen.addstr(self.Y - 1, 0, centered_string, color)
            self.screen.refresh()
            if pause: self.sleep(2*len(string))
            return

        # scrolling through a wider string

        strings = [string[i:i + width] for i in range(len(string) - width + 1)]
        self.screen.addstr(self.Y - 1, 0, strings[0], color)
        self.screen.refresh()
        if self.sleep(width): return
        for s in strings:
            self.screen.addstr(self.Y - 1, 0, s, color)
            self.screen.refresh()
            if self.sleep(): return
        if pause: self.sleep(width)

    def write_help(self):
        """Write one of the help messages."""
        if self.help_ind == 0:
            self.write("Help on controls.")
            self.write("arrow or vi keys: move cursor")
            self.write("space bar or return: rotates piece")
            self.write("q: quit game")
            self.write("n: new game")
            self.write("f: fix rotation")
            self.write("r: randomize rotations")
            self.write("s: toggle show errors")
            self.write("t: toggle toroidal mode")
            self.write("i: toggle inverted mode")
            self.write("x: toggle extra hard mode")
            self.write("The next help is game explanation.")
            self.write()

        if self.help_ind == 1:
            self.write("Help on game.")
            self.write("If game is not inverted," +
                       " the object is to have every line connect to another.")
            self.write("If game is inverted," + 
                       " the object is to have no two lines connected.")
            self.write("If game is not toroidal," +
                       " the borders cannot have lines extending outwards.")
            self.write("If game is toroidal," +
                       " the borders loop back" +
                       " and may connect to the opposite side.")
            self.write("If game is extra hard," +
                       " then no completely (un)filled pieces are used.")
            self.write("The next help is on controls.")
            self.write()

        self.help_ind += 1
        self.help_ind %= 2

    def success(self):
        """Write and respond to the win screen."""
        self.write("You won!")
        self.write("r n q", pause=False)
        while True:
            inp = self.screen.getch()
            if inp in map(ord, 'QqNnRr'): break
        return chr(inp)

    def keyloop(self):
        """Wait for and parse keypress."""
        while True:
            self.display_pos(self.xpos, self.ypos, cursor=True)
            inp = self.screen.getch()

            # parse character input
            if 0 < inp < 256:
                inp = chr(inp)
                if inp in " \n" and not self.is_fixed(self.xpos, self.ypos):
                    self.puzzle.rotate_cw(self.xpos, self.ypos)
                    self.display_pos(self.xpos, self.ypos)
                    if self.puzzle.is_solved():
                        inp = self.success()
                # if inp is changed by self.success, we catch it here
                if inp in "Qq":
                    self.write("Quit")
                    return
                elif inp in "Rr":
                    self.write("Randomize")
                    for position in self.fixed:
                        self.fixed[position] = False
                    self.puzzle.random_orients()
                    self.display()
                    self.write()
                elif inp in "Nn":
                    self.write("New Game")
                    self.new_game()
                elif inp in "H":
                    self.write_help()
                elif inp in "Ss":
                    self.write("Do Not "*self.show_errors + "Show Errors")
                    self.show_errors = not self.show_errors
                    self.display()
                    self.write()
                #TODO: add in show solution, with undo option
                elif inp in "Ii":
                    self.write("Puzzle is now"
                             + " NOT"*self.inverted
                             + " inverted.")
                    self.inverted = not self.inverted
                    self.display()
                    self.write()
                elif inp in "Tt":
                    self.write("Next new game will"
                             + " NOT"*self.toroidal
                             + " be toroidal.")
                    self.toroidal = not self.toroidal
                    self.write()
                elif inp in "Xx":
                    self.write("Next new game will"
                             + " NOT"*self.extra_hard
                             + " be extra hard.")
                    self.extra_hard = not self.extra_hard
                    self.write()
                elif inp in "Ff":
                    self.toggle_fixed(self.xpos, self.ypos)
                    self.display_pos(self.xpos, self.ypos)

            # parse arrow/vi key input for motion
            if inp in [curses.KEY_UP, "k"]:
                if self.toroidal:
                    self.ypos = (self.ypos - 1) % (self.max_ypos + 1)
                elif self.ypos > 0:
                    self.ypos -= 1

            elif inp in [curses.KEY_DOWN, "j"]:
                if self.toroidal:
                    self.ypos = (self.ypos + 1) % (self.max_ypos + 1)
                elif self.ypos < self.max_ypos:
                    self.ypos += 1

            elif inp in [curses.KEY_LEFT, "h"]:
                if self.toroidal:
                    self.xpos = (self.xpos - 1) % (self.max_xpos + 1)
                elif self.xpos > 0:
                    self.xpos -= 1

            elif inp in [curses.KEY_RIGHT, "l"]:
                if self.toroidal:
                    self.xpos = (self.xpos + 1) % (self.max_xpos + 1)
                elif self.xpos < self.max_xpos:
                    self.xpos += 1

def main():
    curses.wrapper(ooPlay)

if __name__ == "__main__":
    main()