import copy
import numpy as np
import pandas as pd
import string
import time
#Alphabet
alpha = np.array(list(string.ascii_uppercase))
def createGraph(n) :
"""
Creates a graph from grouped points.
Parameters:
n - List of list of points that are grouped together.
Returns:
d - Dictionary of each point with valid edge endpoints.
"""
#Output dictionary.
d = {}
#Number of sides.
l = len(n)
for i in range(l):
#Current side.
cur = n[i]
#Remaining letters.
rem = n[0:i] + n[i+1:l]
flat = [letter for side in rem for letter in side]
for j in cur :
#Populate dictionary.
d[j] = flat.copy()
return(d)
def createAllFullPaths(n) :
"""
Creates all valid "letter boxed" sequences.
Parameters:
n - List of list of points that are grouped together.
Returns:
V - List of all valid paths.
"""
start = time.time()
D = createGraph(n)
#Length of final letter boxed.
BOX = len(D)
#Saved sequences.
V = []
#Current sequence.
LETTER_BOXED = ''
def getNextLetter(d, next_letters, letter_boxed, V) :
for j in next_letters :
dc = copy.deepcopy(d)
lb = copy.deepcopy(letter_boxed)
#Update letter boxed.
lb += j
#Valid!
if len(lb) == BOX :
V.append(lb)
#Short!
else :
#Next possible letters stem from current letter.
nl = dc[j]
#Delete current letter.
del dc[j]
#No more letters. Invalid!
if nl == [] :
pass
else :
#Remove letter from other nodes.
for k in nl:
dc[k].remove(j)
getNextLetter(dc, nl, lb, V)
getNextLetter(D, D.keys(), LETTER_BOXED, V)
return(time.time() - start, len(V))
createAllFullPaths(alpha[0:8].reshape(4, 2).tolist())
(0.25894784927368164, 13824)
createAllFullPaths(alpha[0:12].reshape(4, 3).tolist())
(1097.0010514259338, 53529984)