path: root/oo.py

import curses
import random

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

    No rendering information is stored or interpreted here.

    The following are all the get and set methods,
        categorized with their inverses:

        DATA CALLS
        get_piece                       set_piece
        get_orient                      set_orient
        get_piece_orient                set_piece_orient

        HELPER METHODS
        get_adj_pos
        get_edge_pair

        INITIALIZATION
        set_data_from_game_id
        set_data_from_edges
        set_data_from_pieces

    The following are all the user interface methods.
        For more description, see their documentation.

        rotate_cw       : rotates a piece clockwise
        random_orients  : randomly orients all pieces
        check_edge_pair : verifies an edge pair matches properly
        check_piece     : verifies edges on a piece connect to other pieces
        is_solved       : verifies all edges on all pieces are connected

    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

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

        game_id is an integer
            It uniquely corresponds to the solution in edges.
            if     toroidal: in range(2**( 2*X*Y ))
            if not toroidal: in range(2**( (X-1)*Y + X*(Y-1) ))

        A solution is stored in vert_edges and horiz_edges knowing this:
            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

        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)
            
        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)

        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
    """

    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 : int corresponding to solution
                     : if None, a random game_id is generated
            toroidal : bool for looping around the end of the puzzle
        """
        self.X, self.Y = X, Y
        self.game_id = game_id
        self.toroidal = toroidal

        self.horiz_edges = {}
        self.vert_edges = {}
        self.pieces  = {}
        self.orients = {}
        self.set_data_from_game_id(random_game_id = (game_id == None))

    ####
    #
    # The following are constants for converting between various data sets.
    #
    ####

    # 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 get and set methods are low-level data calls,
    # and force the input positions into the appropriate 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 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

    ####
    #
    # The following two get methods are helper methods.
    #
    #   get_adj_pos is  low-level, forcing inputs into the appropriate range.
    # get_edge_pair is high-level, using low-level methods when needed.
    #
    ####

    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 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

    ####
    #
    # The following get and set methods are for initialization.
    #
    # They allow any of the following three data sets to set the other two:
    #     game_id : self.game_id                      : int
    #       edges : self.horiz_edges, self.vert_edges : dicts
    #      pieces : self.pieces, self.orients         : dicts
    #
    ####

    def set_data_from_edges(self, data='pieces and game_id'):
        """Update pieces and/or game_id from edges.

        data is an input in case you want to suppress calculation
        It should be one of ['pieces', 'game_id', 'pieces and game_id']
        """
        if 'pieces' in data:

            for x in range(self.X):
                for y in range(self.Y):

                    left  = self.horiz_edges[x  , y]
                    right = self.horiz_edges[x+1, y]
                    up   = self.vert_edges[x, y  ]
                    down = self.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

        if 'game_id' in data:

            game_id = 0
            exp = 0

            # 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

            # get the edges determined by game_id

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

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

            self.game_id = game_id

    def set_data_from_pieces(self):
        """Update edges and game_id with current pieces.
        
        pieces must be in a solution state, i.e.,
            self.is_solved() must return True
        """
        if not self.is_solved():
            raise ValueError("puzzle is not in a solved state")

        for x, y in self.pieces:

            piece  = self.pieces [x, y]
            orient = self.orients[x, y]

            left, right, up, down = \
                self.PIECE_ORIENT_TO_EDGES[piece, orient]

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

        set_data_from_edges(data='game_id')
        
    def set_data_from_game_id(self, random_game_id=False):
        """Update edges and pieces with current game_id.
        
        if random_game_id,
            then a random game_id is chosen from the appropriate range,
            and pieces are set from that
        """

        # compute:
        #  n_horiz, the number of horizontal edge pairs
        #  n_vert,  the number of  vertical  edge pairs
        #
        # generate random game_id if needed

        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

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

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

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

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

        # set the edges determined by game_id

        game_id = self.game_id

        for i in range(n_vert):
            row, x = divmod(i, self.X)
            game_id, bit = divmod(game_id, 2)
            self.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)
            self.horiz_edges[col+1, y] = bit

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

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

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

        # set the pieces from the edges

        self.set_data_from_edges(data='pieces')

    ####
    #
    # The rest of the methods are for user interface.
    #
    ####

    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 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.
            screen : 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: bg = curses.COLOR_BLUE   # for cursor
            n, bit = divmod(n, 2)
            if bit: fg = curses.COLOR_YELLOW # for fixed
            n, bit = divmod(n, 2)
            if bit: fg = curses.COLOR_RED    # for showing errors
            return fg, bg

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

        # initialize flags
        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)
        if self.extra_hard: self.make_extra_hard()
        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

    def make_extra_hard(self):
        """Returns True unless it successfully makes self.puzzle extra hard.

        TODO: This implementation of extra_hard is not uniformly random.
        TODO: This implementation is for toroidal mode only.
        """

        try_again = False
        X = self.puzzle.X
        Y = self.puzzle.Y

        for x in range(X):
            for y in range(Y):

                piece = self.puzzle.get_piece(x, y)
                if piece not in [0, 5]: continue

                bit = random.randrange(0, 2)

                if bit:
                    x += 1
                    self.puzzle.horiz_edges[x, y] = (piece == 0)
                    if x == X:
                        self.puzzle.horiz_edges[0, y] = (piece == 0)
                        try_again = True

                else:
                    y += 1
                    self.puzzle.vert_edges[x, y] = (piece == 0)
                    if y == Y:
                        self.puzzle.vert_edges[x, 0] = (piece == 0)
                        try_again = True

                self.puzzle.set_data_from_edges()

        if try_again: self.make_extra_hard()

    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

        # compute string

        piece, orient = self.puzzle.get_piece_orient(x, y)
        string = self.PIECE_ORIENT_TO_STRING[piece][orient]

        # compute color

        is_checker = (x + y) % 2
        is_cursor  = bool(cursor)
        is_fixed   = self.is_fixed(x, y)
        is_error   = False
        if self.show_errors:
            is_error = not self.puzzle.check_piece(x, y)

        color_val = (1*is_checker+
                     2*is_cursor +
                     4*is_fixed  +
                     8*is_error  )
        color = curses.color_pair(color_val)

        # add string of color

        self.screen.addstr(y, x, string, color)

        # recurse to equivalent toroidal positions if needed

        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.
        
        Updates adjacent positions when moving the cursor.
        """
        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 get_input(self, options, delay=-1):
        """Waits for input to match an option, returns matched option.

        options must be an iterable of strings and ints.

            Each character in each string and each int are checked against.

            If the input matches any character in a string,
                then the character is returned instead of the ordinal.

        delay is in units of self.pause_length,
            the standard delay per char for the class.
            
            delay may be an integer or float.

            If delay is negative, then input is blocking.

            If nonnegative, then input is non-blocking,
                but keeps waiting if the input is not in options.

            Implementation is such that keypresses other than
                those in options can shorten or lengthen the pause,
                but the pause is capped at twice the intended delay.
        """
        options = list(options)
        chars = []
        ords = []
        for option in options:
            if type(option) is str:
                chars.extend(list(option))
            if type(option) is int:
                ords.append(option)
        breaks = list(map(ord, chars)) + ords

        if delay == -1:
            while True:
                inp = self.screen.getch()
                if inp in breaks:
                    break
        else:
            breaks.append(-1)
            pause = int(self.pause_length * delay)
            self.screen.timeout(pause)
            while True:
                inp = self.screen.getch()
                if inp in breaks: break
                pause //= 2
                self.screen.timeout(pause)
            self.screen.timeout(-1)

        if inp in map(ord, chars):
            return chr(inp)
        return inp

    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:
                if -1 != self.get_input(" ", delay=2*len(string)): return
            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 -1 != self.get_input(" ", delay=width): return
        for s in strings:
            self.screen.addstr(self.Y - 1, 0, s, color)
            self.screen.refresh()
            if -1 != self.get_input(" ", delay=1): return
        if pause:
            if -1 != self.get_input(" ", delay=width): return

    def write_menu(self, string, controls=[]):
        """Writes string, waits for acceptable input, returns upper input.
        
        Inputs are allowed to be:
            any upper case character in string,
            any lower case version of those characters, or
            any element of controls.
            the spacebar (on which the text is redisplayed)

        Returns the matched input, made upper case if matched from string.

        A common setting for controls contains:
            '\n'          for exiting menu
            curses.KEY_UP for backing up one menu

        The spacebar handling can be overwritten by adding ' ' to controls.
        """
        options = [char + char.lower() for char in string if char.isupper()]
        options.extend(controls)
        options.append(' ')
        while True:
            self.write(string, pause=False)
            inp = self.get_input(options)
            if inp != ' ':
                break
        if inp in controls:
            return inp
        return inp.upper()

    def menu_system(self, string_tree, up_key=curses.KEY_UP, out_key='\n'):
        """Runs a system of menus configured by string_tree.

        string_tree must be a tuple with:
            a string to be passed to write_menu
            a dictionary with a key per upper case letter in string, where:
                the key is the upper case letter as a string
                the value is a string_tree

        A string_tree that ends a path is a tuple with:
            a string that has no upper case characters
            an empty dictionary

        Each string tree is parsed in the same way,
            where the string is written with write_menu,
            and choosing an option results in opening a submenu
            given by the corresponding dictionary item.

        Pressing up_key results in going up to the parent menu.
        Pressing out_key results in exiting the menu (return).
        """
        parents = []
        while True:
            string, responses = string_tree
            inp = self.write_menu(string, controls=[up_key, out_key])
            if inp in responses:
                parents.append(string_tree)
                string_tree = responses[inp]
            elif inp == up_key and parents:
                string_tree = parents.pop()
            elif inp == out_key or not parents:
                return

    def write_help(self):
        """Write the help menu."""
        self.write("use spacebar to skip or repeat a message")
        self.write("use the capital letter to make a selection")
        self.write("use the up key to return to a previous menu")
        self.write("use return to exit the help menu")
        help_menu = \
            ("Controls or Gameplay?",
             {"C": ("Move cursor | Rotations | Game | Toggles",
                    {"M": ("use arrow or vi keys (hjkl) to move the cursor",
                           {}),
                     "R": ("rotate Piece | Fix piece | Randomize",
                           {"P": ("use space bar or return to rotate a piece",
                                  {}),
                            "F": ("use f to fix a piece's rotation",
                                  {}),
                            "R": ("use r to randomize all pieces," +
                                  " including fixed",
                                  {})}
                           ),
                     "G": ("New | Quit | Solve",
                           {"N": ("use n to start a new game",
                                  {}),
                            "Q": ("use q to quit the program",
                                  {}),
                            "S": ("use S to show a solution",
                                  {})}
                          ),
                     "T": ("Show errors | Inverted | Toroidal | eXtra hard",
                           {"S": ("use s to show/hide errors",
                                  {}),
                            "I": ("use i to toggle inverted mode",
                                  {}),
                            "T": ("use t to toggle toroidal on next new game",
                                  {}),
                            "X": ("use x to toggle extra hard on next new game",
                                  {})}
                          )}
                    ),
              "G": ("Basic play | if Inverted | if Toroidal | if eXtra hard",
                    {"B": ("the object is to connect every line to another," +
                           " where no line should extend to a border," +
                           " and every possible piece may be in the puzzle",
                           {}),
                     "I": ("if inverted, the object changes to ensure" +
                           " every line is not connected to any other," +
                           " and border edges do not matter",
                           {}),
                     "T": ("if toroidal, the object changes so that" +
                           " the borders loop back, that is," +
                           " rightmost pieces may connect to leftmost pieces"
                           " and same with topmost and bottommost",
                           {}),
                     "X": ("if extra hard, the object is the same," +
                           " but when generating the puzzle," +
                           " no completely filled or unfilled pieces are used",
                           {})}
                   )}
             )
        self.menu_system(help_menu)
        self.write()

    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":
                    if self.is_fixed(self.xpos, self.ypos):
                        self.write("fixed piece")
                        self.write()
                        continue
                    self.puzzle.rotate_cw(self.xpos, self.ypos)
                    self.display_pos(self.xpos, self.ypos)
                    if self.puzzle.is_solved():
                        self.write("You won!")
                        menu = "Randomize | New game | Quit game"
                        inp = self.write_menu(menu)
                # if inp is changed on a solved puzzle, 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 "S":
                    self.write("show a solution")
                    for position in self.fixed:
                        self.fixed[position] = False
                    self.puzzle.set_data_from_edges(data='pieces')
                    self.display()
                    self.write()
                elif inp in "s":
                    self.write("do NOT "*self.show_errors + "show errors")
                    self.show_errors = not self.show_errors
                    self.display()
                    self.write()
                #TODO: add in an undo button
                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

class ooStudy():
    """Studies oo puzzles of a particular size.
    
    This class is not intended to be used. It is far too slow.
    Instead, it is intended to be ported to a faster language.
    """

    def __init__(self, X, Y, toroidal=False):
        self.X = X
        self.Y = Y
        self.toroidal = toroidal
        self.puzzles = []

    def __call__(self):
        """Study each possible game id."""
        X = self.X
        Y = self.Y
        if self.toroidal: upper_bound = 2**( 2*X*Y )
        else:             upper_bound = 2**( (X-1)*Y + X*(Y-1) )
        for game_id in range(upper_bound):
            new_puzzle = ooPuzzle(X, Y,
                    game_id=game_id, toroidal=self.toroidal)
            for puzzle in self.puzzles:
                if puzzle.pieces == new_puzzle.pieces:
                    puzzle.equivalent_ids.append(game_id)
                    return
            new_puzzle.equivalent_ids = []
            self.puzzles.append(new_puzzle)

def main():
    curses.wrapper(ooPlay)

if __name__ == "__main__":
    main()