tower of london puzzle generator for Kyle

tower_of_london.py

#!/usr/bin/env python 
'''
Copyright (C) 2013 Al Grant, al@algrant.ca

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
'''

from itertools import permutations
import numpy as np

# some discussion here on whether or not this is a good plan for unique permutations...
# http://stackoverflow.com/questions/6534430
def unique(iterable):
  seen = set()
  for x in iterable:
    if x in seen:
      continue
    seen.add(x)
    yield x

# this generates all potential integer lists (l = [l_1,l_2,l_3,..., l_n])
# such that sum(l) = max_sum
# and l_n < h_n for all h in heights
def iter_fill_list(heights, max_sum):
  for i in recurse_fill_list([],heights,max_sum):
    yield i

# recursive definition of a fill_list
# what is a fill_list? see above!
def recurse_fill_list(filled_list,empty_list,total_sum):
  if sum(filled_list) == total_sum:
    yield filled_list + [0]*len(empty_list)
  else:
    if len(empty_list) > 0:
      for i in range(empty_list.pop(0)+1):
        temp = filled_list + [i]
        for fl in recurse_fill_list(temp,[j for j in empty_list],total_sum):
          yield fl

# given a set of column heights and list of pieces
# will return every possible state, for the tower of london game
def tol_states (heights, pieces):
  h = heights[:]
  for i in iter_fill_list(h,len(pieces)):
    for j in unique(permutations(pieces)):
      t = []
      s=0
      for k in i:
        t.append("".join(j[s:s+k]))
        s+=k
      yield t

# given a set of columns heights and the current state
# will return every possible move, for the tower of london game, 
# from the current state
def tol_moves (heights, state):
  for e1,s1 in enumerate(state):
    if len(s1) > 0:
      for e2, s2 in enumerate(state):
        if e1 != e2 and len(s2) < heights[e2]:
          new_state = [i for i in state]
          new_state[e2] += new_state[e1][-1]
          new_state[e1] = new_state[e1][:-1]
          yield new_state

class tolState():
  def __init__(self, heights, state):
    self.heights = heights
    self.setState(state)

  def setState(self,state):
    self.state = state
    state_id = ""
    for i in range(len(self.heights)):
      state_id += state[i] + '_'*(self.heights[i] - len(state[i])) + "|"
    self.state_id = state_id[:-1]   

  def setStateId(self,state_id):
    self.state_id = state_id
    self.state = [i.strip("_") for i in state_id.split("|")]

  def getState(self):
    return self.state

  def getStateId(self):
    return self.state_id

  def sameShapeAs(self,otherState):
    if self.heights != otherState.heights:
      return False
    for e,r in enumerate(self.state):
      if len(r) != len(otherState.state[e]):
        return False
    return True

  def sameAs(self,otherState):
    if self.state_id == otherState.state_id:
      return True
    return False

  def getAlphabet(self,otherState):
    alphabet = {}
    for e,char in enumerate(self.state_id):
      alphabet[char] = otherState.state_id[e]
    return alphabet
       

class tolPuzzle():
  def __init__(self,state1,state2):
    self.heights = state1.heights
    self.state1 = state1
    self.state2 = state2

  def __str__(self):
    return self.state1.state_id + "<>" + self.state2.state_id
  def __repr__(self):
    return self.state1.state_id + "<>" + self.state2.state_id
  def sameAs(self,otherPuzzle):
    p1s1 = self.state1.state_id
    p1s2 = self.state2.state_id
    p2s1 = otherPuzzle.state1.state_id
    p2s2 = otherPuzzle.state2.state_id
    if  symmetricStringStructure(p1s1,p1s2,p2s1,p2s2) or \
        symmetricStringStructure(p1s1,p1s2,p2s2,p2s1):
      return True
    else:
      return False


def symmetricStringStructure(a1, a2, b1, b2):
  alphabet = {}
  for i in range(len(a1)):
    alphabet[a1[i]] = b1[i]

  test = ''.join([alphabet[i] for i in a2])
  if test == b2:
    return True
  else:
    return False


class tolPuzzleType():
  def __init__(self, heights, pieces):
    self.heights = heights
    self.pieces = pieces

    self.state_graph = {}
    self.numbered_graph = {}

    self.generateStates()

    self.determineDistances()

    self.generatePuzzles()

    print self.puzzles
    
  def max_moves(self):
    return self.distances.max()

  def generateStates(self):
    for e, state in enumerate(tol_states(self.heights, self.pieces)):
      state_id = self.id_from_state(state)
      self.state_graph[state_id] = {"state":tolState(self.heights,state), "number":e,"connections":[]}
      self.numbered_graph[e] = {"state_id":state_id,"state":tolState(self.heights,state), "connections":[]}
      for move in tol_moves(self.heights, state):
        m_id = self.id_from_state(move)
        self.state_graph[state_id]["connections"].append(m_id)
        self.numbered_graph[e]["connections"].append(m_id)

  def id_from_state(self,state):
    state_id = ""
    for i in range(len(self.heights)):
      state_id += state[i] + '_'*(self.heights[i] - len(state[i])) + "|"
    return state_id[:-1]

  def state_from_id(self,id):
    state = [i.strip("_") for i in id.split("|")]
    return state

  def determineDistances(self):
    # floyd warshall's algorithm to find all shortest paths:
    # http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

    # can't be further apart than going through each node...
    self.distances = np.zeros([len(self.numbered_graph), len(self.numbered_graph)])
    self.distances.fill(len(self.numbered_graph))

    # all paths to self are 0
    for i in range(len(self.numbered_graph)):
      self.distances[i][i] = 0

    # all paths to neighbour are 1
    for u in range(len(self.numbered_graph)):
      for v_state in self.numbered_graph[u]["connections"]:
        v = self.state_graph[v_state]["number"]
        self.distances[u][v] = 1

    # check wikipedia for why this works...
    for k in range(len(self.numbered_graph)):
       for i in range(len(self.numbered_graph)):
          for j in range(len(self.numbered_graph)):
             if self.distances[i][k] + self.distances[k][j] < self.distances[i][j]:
                self.distances[i][j] = self.distances[i][k] + self.distances[k][j]

    self.distances = np.vectorize(lambda x,max: x if x != max else -1)(self.distances, len(self.numbered_graph))

  def generatePuzzles(self):
    self.puzzles = {}
    for i in range(len(self.distances)):
      for j in range(i):
        dis = self.distances[i][j]
        if dis > 1:
          if not (dis in self.puzzles):
            self.puzzles[dis] = []
          newPuzz = tolPuzzle(self.numbered_graph[i]["state"],self.numbered_graph[j]["state"])
          new = True
          for puzz in self.puzzles[dis]:
            if puzz.sameAs(newPuzz):
              new = False
              break
          if new:
            self.puzzles[dis].append(newPuzz)




tol = tolPuzzleType([2,2,1],"abc")
#print tol.max_moves()

# s1 = tolState([3,2,2],['ab','c',''])
# s2 = tolState([3,2,2],['b','ac',''])
# s3 = tolState([3,2,2],['ba','c',''])
# s4 = tolState([3,2,2],['b','ac',''])

# p1 = tolPuzzle(s1,s2)
# p2 = tolPuzzle(s3,s4)

# print p1.sameAs(p2)