2
\$\begingroup\$

I was given the task of making a grid peg solitaire puzzle. Here are the programs, the basic puzzle file, and the actual grid solitaire puzzle:

The puzzle software

class Puzzle:
    """"
    Snapshot of a full-information puzzle, which may be solved, unsolved,
    or even unsolvable.
    """

    def fail_fast(self):
        """
        Return True iff Puzzle self can never be extended to a solution.

        Override this in a subclass where you can determine early that
        this Puzzle can't be solved.

        @type self: Puzzle
        @rtype: bool
        """
        return False

    def is_solved(self):
        """
        Return True iff Puzzle self is solved.

        This is an abstract method that must be implemented
        in a subclass.

        @type self: Puzzle
        @rtype: bool
        """
        raise NotImplementedError

    def extensions(self):
        """
        Return list of legal extensions of Puzzle self.

        This is an abstract method that must be implemented
        in a subclass.

        @type self: Puzzle
        @rtype: list[Puzzle]
        """
        raise NotImplementedError

The grid peg solitaire puzzle with the above puzzle imported above.:

from puzzle import Puzzle


class GridPegSolitairePuzzle(Puzzle):
    """
    Snapshot of peg solitaire on a rectangular grid. May be solved,
    unsolved, or even unsolvable.
    """

    def __init__(self, marker, marker_set):
        """
        Create a new GridPegSolitairePuzzle self with
        marker indicating pegs, spaces, and unused
        and marker_set indicating allowed markers.

        @type marker: list[list[str]]
        @type marker_set: set[str]
                          "#" for unused, "*" for peg, "." for empty
        """
        assert isinstance(marker, list)
        assert len(marker) > 0
        assert all([len(x) == len(marker[0]) for x in marker[1:]])
        assert all([all(x in marker_set for x in row) for row in marker])
        assert all([x == "*" or x == "." or x == "#" for x in marker_set])
        self._marker, self._marker_set = marker, marker_set

     # TODO
    # implement __eq__, __str__ methods
    # __repr__ is up to you
    #Received help from TA Bryan
    def __eq__(self, other):
        """
        Return whether GridPegSolitairePuzzle self is equivalent to other.
        @type self: GridPegSolitairePuzzle
        @type other: GridPegSolitairePuzzle | Any
        @rtype: bool
        >>> grid = [["*", "*", "*", "*", "*"]]
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> grid.append(["*", "*", ".", "*", "*"])
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
        >>> grid = [["*", "*", "*", "*", "*"]]
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> grid.append(["*", "*", ".", "*", "*"])
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> gpsp2 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
        >>> grid = [[".", ".", ".", ".", "."]]
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> grid.append(["*", "*", ".", "*", "*"])
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> gpsp3 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
        >>> gpsp1.__eq__(gpsp2)
        True
        >>> gpsp1.__eq__(gpsp3)
        False
        """
        #TA Bryan added return (type(other) == type(self) part for me
        return (type(other) == type(self) and
                self._marker == other._marker and
                self._marker_set == other._marker_set)

    def __str__(self):
        """
        Return a human-readable string representation of GridPegSolitairePuzzle.
        @type self: GridPegSolitairePuzzle
        @rtype: str
        >>> grid = [["*", "*", "*", "*", "*"]]
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> grid.append(["*", "*", ".", "*", "*"])
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
        >>> print(gpsp1)
        * * * * *
        * * * * *
        * * * * *
        * * . * *
        * * * * *
        """
        return "\n".join([" ".join(row) for row in self._marker])

    def extensions(self):
        """
        Return list of extensions of GridPegSolitairePuzzle self.
        @type self: GridPegSolitairePuzzle
        @rtype: list[GridPegSolitairePuzzle]
        >>> grid = [[".", ".", ".", "*", "*"]]
        >>> grid.append([".", ".", ".", ".", "."])
        >>> grid.append([".", ".", ".", ".", "."])
        >>> grid.append([".", ".", ".", ".", "."])
        >>> grid.append([".", ".", ".", ".", "."])
        >>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
        >>> L1 = gpsp1.extensions()
        >>> grid[0] = [".", ".", "*", ".", "."]
        >>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
        >>> len(L1) == len(L2)
        True
        >>> all([s in L2 for s in L1])
        True
        >>> all([s in L1 for s in L2])
        True
        """
        legal = []

        # For each peg, checks whether it can be jumped up, down, left, or right
        # If so, that configuration is added to the list of legal extensions
        for r in range(len(self._marker)):
            for c in range(len(self._marker[r])):
                if self._marker[r][c] == "*":
                    legal.extend(jump_left(self._marker, r, c))
                    legal.extend(jump_right(self._marker, r, c))
                    legal.extend(jump_up(self._marker, r, c))
                    legal.extend(jump_down(self._marker, r, c))

        return legal

    def is_solved(self):
        """
        Returns true iff there is one peg, '*', remaining in the grid
        @type self: GridPegSolitairePuzzle
        @rtype: bool
        >>> grid = [[".", "*", ".", ".", "*"]]
        >>> grid.append([".", ".", "*", ".", "."])
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> grid.append(["*", "*", ".", "*", "*"])
        >>> grid.append(["*", "*", "*", "*", "*"])
        >>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
        >>> grid = [[".", ".", ".", ".", "."]]
        >>> grid.append([".", ".", ".", ".", "."])
        >>> grid.append([".", ".", ".", ".", "."])
        >>> grid.append([".", ".", "*", ".", "."])
        >>> grid.append([".", ".", ".", ".", "."])
        >>> gpsp2 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
        >>> gpsp1.is_solved()
        False
        >>> gpsp2.is_solved()
        True
        """
        # Makes a list of how many pegs are in each row
        # Checks that one row has one peg, and the rest have none
        pegs = [row.count('*') for row in self._marker]
        return pegs.count(1) == 1 and pegs.count(0) == len(pegs) - 1


def jump_left(markers, row, column):
    """
    Returns the grid that results after the marker at (row, column) jumps left
    @type markers: list[list[str]]
    @type row: int
    @type column: int
    @rtype: list[GridPegSolitairePuzzle]
    >>> grid = [["*", "*", "*", "*", "*"]]
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> grid.append(["*", "*", ".", "*", "*"])
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
    >>> L1 = jump_left(gpsp1._marker, 3, 4)
    >>> grid[3][2] = "*"
    >>> grid[3][3] = "."
    >>> grid[3][4] = "."
    >>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
    >>> L1 == L2
    True
    """
    # Checking bounds and whether the right pieces are in the positions needed
    if (column - 2) >= 0 and (markers[row][column - 2] == ".") and\
                             (markers[row][column - 1] == "*"):

        # Each row must be copied individually (since they are all lists)
        m_copy = []
        for i in range(len(markers)):
            m_copy.append(markers[i].copy())

        new_grid = GridPegSolitairePuzzle(m_copy, {"*", ".", "#"})

        # Performs the jump
        new_grid._marker[row][column] = "."
        new_grid._marker[row][column - 1] = "."
        new_grid._marker[row][column - 2] = "*"

        return [new_grid]

    else:
        return []


def jump_right(markers, row, column):
    """
    Returns the grid that results after the marker at (row, column) jumps right
    @type markers: list[list[str]]
    @type row: int
    @type column: int
    @rtype: list[GridPegSolitairePuzzle]
    >>> grid = [["*", "*", "*", "*", "*"]]
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> grid.append(["*", "*", ".", "*", "*"])
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
    >>> L1 = jump_right(gpsp1._marker, 3, 0)
    >>> grid[3][2] = "*"
    >>> grid[3][0] = "."
    >>> grid[3][1] = "."
    >>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
    >>> L1 == L2
    True
    """
    # Checking bounds and whether the right pieces are in the positions needed
    if (column + 2) < len(markers[row]) and\
       (markers[row][column + 2] == ".") and\
       (markers[row][column + 1] == "*"):

        # Each row must be copied individually (since they are all lists)
        m_copy = []
        for i in range(len(markers)):
            m_copy.append(markers[i].copy())

        new_grid = GridPegSolitairePuzzle(m_copy,
                                          {"*", ".", "#"})

        # Performs the jump
        new_grid._marker[row][column] = "."
        new_grid._marker[row][column + 1] = "."
        new_grid._marker[row][column + 2] = "*"

        return [new_grid]

    else:
        return []


def jump_up(markers, row, column):
    """
    Returns the grid that results after the marker at (row, column) jumps up
    @type markers: list[list[str]]
    @type row: int
    @type column: int
    @rtype: list[GridPegSolitairePuzzle]
    >>> grid = [["*", "*", "*", "*", "*"]]
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> grid.append(["*", "*", ".", "*", "*"])
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
    >>> L1 = jump_up(gpsp1._marker, 4, 2)
    >>> grid[2][2] = "*"
    >>> grid[3][2] = "."
    >>> grid[4][2] = "."
    >>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
    >>> L1 == L2
    True
    """
    # Checking bounds and whether the right pieces are in the positions needed
    if (row - 2) >= 0 and (markers[row - 2][column] == ".") and\
                          (markers[row - 1][column] == "*"):

        # Each row must be copied individually (since they are all lists)
        m_copy = []
        for i in range(len(markers)):
            m_copy.append(markers[i].copy())

        new_grid = GridPegSolitairePuzzle(m_copy,
                                          {"*", ".", "#"})

        # Performs the jump
        new_grid._marker[row][column] = "."
        new_grid._marker[row - 1][column] = "."
        new_grid._marker[row - 2][column] = "*"

        return [new_grid]

    else:
        return []


def jump_down(markers, row, column):
    """
    Returns the grid that results after the marker at (row, column) jumps down
    @type markers: list[list[str]]
    @type row: int
    @type column: int
    @rtype: list[GridPegSolitairePuzzle]
    >>> grid = [["*", "*", "*", "*", "*"]]
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> grid.append(["*", "*", ".", "*", "*"])
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
    >>> L1 = jump_down(gpsp1._marker, 1, 2)
    >>> grid[3][2] = "*"
    >>> grid[2][2] = "."
    >>> grid[1][2] = "."
    >>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
    >>> L1 == L2
    True
    """
    # Checking bounds and whether the right pieces are in the positions needed
    if (row + 2) < len(markers) and\
            (markers[row + 2][column] == ".") and\
            (markers[row + 1][column] == "*"):

        # Each row must be copied individually (since they are all lists)
        m_copy = []
        for i in range(len(markers)):
            m_copy.append(markers[i].copy())

        new_grid = GridPegSolitairePuzzle(m_copy,
                                          {"*", ".", "#"})

        # Performs the jump
        new_grid._marker[row][column] = "."
        new_grid._marker[row + 1][column] = "."
        new_grid._marker[row + 2][column] = "*"

        return [new_grid]

    else:
        return []

if __name__ == "__main__":
    import doctest

    doctest.testmod()
    from puzzle_tools import depth_first_solve

    grid = [["*", "*", "*", "*", "*"],
            ["*", "*", "*", "*", "*"],
            ["*", "*", "*", "*", "*"],
            ["*", "*", ".", "*", "*"],
            ["*", "*", "*", "*", "*"]]
    gpsp = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
    import time

    start = time.time()
    solution = depth_first_solve(gpsp)
    end = time.time()
    print("Solved 5x5 peg solitaire in {} seconds.".format(end - start))
    print("Using depth-first: \n{}".format(solution))

The code works entirely, but the professor does not like how I broke up the function definitions into jump_right, jump_left, jump_up, jump_down. He says I should do this all in one function called jump. What would the code be for this?

\$\endgroup\$
2
  • \$\begingroup\$ The code works entirely? The doctests fail for me. I can come up with a solution that combines them, but it has the same doctest failure that yours gets. \$\endgroup\$
    – zondo
    Mar 28 '16 at 16:43
  • \$\begingroup\$ @zondo can i see your solution? Thanks \$\endgroup\$
    – MartinK
    Mar 28 '16 at 17:05
2
\$\begingroup\$

One thing to be noticed is that the code is just about identical. When row and column are used, it is always either + 2, - 2, + 1, or - 1. What I have done below is create a dictionary for the different directions. Whenever you use row + 1 in one function, it should instead be row + rowadd because in other functions, it might be row, row + 1, or row - 1. Whenever you use row + 2 in one function, int should be row + (2 * rowadd) because in other functions, it might be row, row + 2, or row - 2. I have used constants at the beginning of the file to define what the directions are. That way I am not hard-coding values. Anyway, the code is here:

LEFT = "left"
RIGHT = "right"
UP = "up"
DOWN = "down"

def jump(markers, row, column, direction):
    """
    Returns the grid that results after the marker at (row, column) jumps in the direction of DIRECTION.
    @type markers: list[list[str]]
    @type row: int
    @type column: int
    @rtype: list[GridPegSolitairePuzzle]
    >>> grid = [["*", "*", "*", "*", "*"]]
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> grid.append(["*", "*", ".", "*", "*"])
    >>> grid.append(["*", "*", "*", "*", "*"])
    >>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
    >>> L1 = jump(gpsp1._marker, 3, 0, RIGHT)
    >>> grid[3][2] = "*"
    >>> grid[3][0] = "."
    >>> grid[3][1] = "."
    >>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
    >>> L1 == L2
    True
    """
   # Checking bounds and whether the right pieces are in the positions needed
    moves = {LEFT: (0, -1), RIGHT: (0, 1), UP: (-1, 0), DOWN: (1, 0)}
    rowadd, columnadd = moves[direction]
    if (column + (2*columnadd)) < len(markers[row + (2*rowadd)]) and\
       (markers[row + (2*rowadd)][column + (2*columnadd)] == ".") and\
       (markers[row + (2*rowadd)][column + columnadd] == "*"):

        # Each row must be copied individually (since they are all lists)
        m_copy = []
        for i in range(len(markers)):
            m_copy.append(markers[i].copy())

        new_grid = GridPegSolitairePuzzle(m_copy,
                                          {"*", ".", "#"})

        # Performs the jump
        new_grid._marker[row][column] = "."
        new_grid._marker[row + rowadd][column + columnadd] = "."
        new_grid._marker[row + (2*rowadd)][column + (2*columnadd)] = "*"

        return [new_grid]
   else:
        return []

I can't say absolutely that this works because I don't have the puzzle_tools module. I do know that the doc tests don't work, but they fail with the exact same messages as how your current program fails.

\$\endgroup\$
6
  • \$\begingroup\$ can you show me how would i adjust def extensions, and thank you so much for the example \$\endgroup\$
    – MartinK
    Mar 28 '16 at 20:15
  • \$\begingroup\$ The doc string gives that. Any time you would do jump_right(...), change it to jump(..., RIGHT). Any time you would do jump_left(...), change it to jump(..., LEFT); etc. \$\endgroup\$
    – zondo
    Mar 28 '16 at 20:49
  • \$\begingroup\$ so for something like legal.extend(jump_left(self._marker, r, c)), i should write legal.extend(jump(self._marker, r, RIGHT)) \$\endgroup\$
    – MartinK
    Mar 28 '16 at 21:26
  • \$\begingroup\$ No. It would be legal.extend(jump(self._marker, r, c, LEFT)). You use the same arguments, but just add the direction to the end. \$\endgroup\$
    – zondo
    Mar 28 '16 at 21:28
  • \$\begingroup\$ Thank you so much for taking the time to help, I appreciate it \$\endgroup\$
    – MartinK
    Mar 28 '16 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.