#!/usr/bin/env python
# BoggleBoard.py - Module encapsulating the Boggle board.
# I tried to make this class as flexible as possible, allowing for boards of 
# arbitrary size, and searching for paths of arbitrary lengths (up to the 
# number of nodes on the board).
# 
# Copyright (c) 2009, Alan Saqui <alan.saqui@gmail.com>
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
#     * Redistributions of source code must retain the above copyright
#       notice, this list of conditions and the following disclaimer.
#     * Redistributions in binary form must reproduce the above copyright
#       notice, this list of conditions and the following disclaimer in the
#       documentation and/or other materials provided with the distribution.
#     * Neither the name of the <organization> nor the
#       names of its contributors may be used to endorse or promote products
#       derived from this software without specific prior written permission.
# 
# THIS SOFTWARE IS PROVIDED BY ALAN SAQUI ''AS IS'' AND ANY
# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL ALAN SAQUI BE LIABLE FOR ANY
# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


class BoggleBoard:
    # Constructor
    # hlen - height of board
    # vlen - width of board
    # path_lim - max path_length to search for.
    def __init__(self, hlen, vlen, path_lim):
        self.hlen = hlen
        self.vlen = vlen
        self.vertices = range(hlen * vlen)
        self.build_board()
        self.build_adj_list()
        self.build_path_list(path_lim)

    # Build a 2d array of the Boggle board
    def build_board(self):
        self.board = []
        row = []
        for x in range(self.hlen * self.vlen):
            row.append(x)
            if (x + 1) % self.vlen == 0:
                self.board.append(row)
                row = []

    # Build the adjaceny list for the Boggle board
    def build_adj_list(self):
        # Initialize adj_list with empty lists for all nodes
        self.adj_list = [ [] for x in self.vertices ]
        for i in range(self.vlen):
            for j in range(self.hlen):
                self.adj_list[self.board[i][j]] = self.find_adj_vertices(i, j)

    def build_path_list(self, limit):
        if limit <= 0:
            limit = 0
        elif limit > len(self.vertices):
            limit = self.vertices
        self.paths = []
        # Find all paths of lengths from 0 to limit
        # This can be tweaked to allow for longer paths.
        for path_len in range(limit + 1):
            self.paths.append(self.find_all_paths(path_len))

    # Find all vertices adjacent to the given vertex.
    def find_adj_vertices(self, i, j):
        adj_vertices = []
        # Check all 8 possibilities
        if (i - 1) > -1:
            if (j - 1) > -1: # -1, -1
                adj_vertices.append(self.board[i -1][j - 1])
            adj_vertices.append(self.board[i -1][j]) # -1, 0
            if (j + 1) < self.vlen: # -1, + 1
                adj_vertices.append(self.board[i -1][j + 1])

        if (i + 1) < self.hlen:
            if (j - 1) > -1: # +1, -1
                adj_vertices.append(self.board[i + 1][j - 1])
            adj_vertices.append(self.board[i + 1][j]) # +1, 0
            if (j + 1) < self.vlen: # +1, + 1
                adj_vertices.append(self.board[i + 1][j + 1])

        if (j - 1) > -1: # 0, -1
            adj_vertices.append(self.board[i][j - 1])
        if (j + 1) < self.vlen: # 0, + 1
            adj_vertices.append(self.board[i][j + 1])
        return adj_vertices

    # Find all paths of length len
    def find_all_paths(self, len):
        # Special cases of length 0 and 1
        if len <= 0:
            return []
        elif len == 1:
            return [[x, ] for x in self.vertices]
        else:
            paths = []
            for vertex in self.vertices:
                paths += self.find_paths(len - 1, vertex, [vertex, ])
            return paths

    # Find all paths of length len from the given vertex.
    # len - length of path (total # of vertices, not edges!)
    # vertex - starting vertex
    # prefix - list of vertices denoting path thus far
    def find_paths(self, len, vertex, prefix):
        paths = []
        # Find list of all _unvisited_ adjacent vertices.
        adj_vertices = [ x for x in self.adj_list[vertex] if x not in prefix ]
        for adj_vertex in adj_vertices:
            if len == 1:
                # Len of 1 -> path end on this vertex. Append vertex to prefix 
                # to make the full path, and add path to list. 
                paths.append(prefix + [adj_vertex, ])
            else:
                # Add adjacent node to prefix
                adj_prefix = prefix + [adj_vertex]
                # Add all paths from this node to path list.
                paths += self.find_paths(len - 1, adj_vertex, adj_prefix)

        return paths