te777
Reputation Top 10%
Tommy English
1 Snippet  (369th place)
Published
1 Channel
Created
1 Channel
Following
Sep 24, 2016
Last Visit
Sep 24, 2016
Registered
30 points  (1594th place)
Reputation
Junior Code Generator
Junior Publisher
Junior Autobiographer
Senior Autobiographer
Junior Famous Coder

Recent Snippets See all snippets by te777

Hackerrank Count Strings solution python

Hackerrank Count Strings solution python
```'''
Created on Aug 7, 2016

AutomataTheory.py

@author: Siddharthasahu @ https://github.com/siddharthasahu/automata-from-regex

Automata build from from regex to DFA taken from there. Count Strings (Matrix class) added
'''
# You can test with input " 1 ((((ab)|a)*)|(((aa)|(bb))*)) 368046388 "

#The result of the code executed in main should be 198110437 with the test input

#import fileinput
#from os import popen
#import time
#import sys, traceback

class Automata:
"""class to represent an Automata"""

def __init__(self, language = set(['a', 'b'])):
self.states = set()
self.startstate = None
self.finalstates = []
self.transitions = dict()
self.language = language

@staticmethod
def epsilon():
return ":e:"

def setstartstate(self, state):
self.startstate = state

if isinstance(state, int):
state = [state]
for s in state:
if s not in self.finalstates:
self.finalstates.append(s)

if isinstance(inp, str):
inp = set([inp])
if fromstate in self.transitions:
if tostate in self.transitions[fromstate]:
self.transitions[fromstate][tostate] = self.transitions[fromstate][tostate].union(inp)
else:
self.transitions[fromstate][tostate] = inp
else:
self.transitions[fromstate] = {tostate : inp}

for fromstate, tostates in transitions.items():
for state in tostates:

def gettransitions(self, state, key):
if isinstance(state, int):
state = [state]
trstates = set()
for st in state:
if st in self.transitions:
for tns in self.transitions[st]:
if key in self.transitions[st][tns]:
return trstates

def getEClose(self, findstate):
allstates = set()
states = set([findstate])
while len(states)!= 0:
state = states.pop()
if state in self.transitions:
for tns in self.transitions[state]:
if Automata.epsilon() in self.transitions[state][tns] and tns not in allstates:
return allstates

def display(self):
print ("states:", self.states)
print ("start state: ", self.startstate)
print ("final states:", self.finalstates)
print ("transitions:")
for fromstate, tostates in self.transitions.items():
for state in tostates:
for char in tostates[state]:
print ("  ",fromstate, "->", state, "on '"+char+"'",)
print

def getPrintText(self):
text = "language: {" + ", ".join(self.language) + "}\n"
text += "states: {" + ", ".join(map(str,self.states)) + "}\n"
text += "start state: " + str(self.startstate) + "\n"
text += "final states: {" + ", ".join(map(str,self.finalstates)) + "}\n"
text += "transitions:\n"
linecount = 5
for fromstate, tostates in self.transitions.items():
for state in tostates:
for char in tostates[state]:
text += "    " + str(fromstate) + " -> " + str(state) + " on '" + char + "'\n"
linecount +=1
return [text, linecount]

def newBuildFromNumber(self, startnum):
translations = {}
for i in list(self.states):
translations[i] = startnum
startnum += 1
rebuild = Automata(self.language)
rebuild.setstartstate(translations[self.startstate])
for fromstate, tostates in self.transitions.items():
for state in tostates:
return [rebuild, startnum]

def newBuildFromEquivalentStates(self, equivalent, pos):
rebuild = Automata(sorted(self.language))
for fromstate, tostates in self.transitions.items():
for state in tostates:
rebuild.setstartstate(pos[self.startstate])
for s in self.finalstates:
return rebuild

def getDotFile(self):
dotFile = "digraph DFA {\nrankdir=LR\n"
if len(self.states) != 0:
dotFile += "root=s1\nstart [shape=point]\nstart->s%d\n" % self.startstate
for state in self.states:
if state in self.finalstates:
dotFile += "s%d [shape=doublecircle]\n" % state
else:
dotFile += "s%d [shape=circle]\n" % state
for fromstate, tostates in self.transitions.items():
for state in tostates:
for char in tostates[state]:
dotFile += 's%d->s%d [label="%s"]\n' % (fromstate, state, char)
dotFile += "}"
return dotFile

class BuildAutomata:
"""class for building e-nfa basic structures"""

@staticmethod
def basicstruct(inp):
state1 = 1
state2 = 2
basic = Automata()
basic.setstartstate(state1)
return basic

@staticmethod
def plusstruct(a, b):
[a, m1] = a.newBuildFromNumber(2)
[b, m2] = b.newBuildFromNumber(m1)
state1 = 1
state2 = m2
plus = Automata()
plus.setstartstate(state1)
return plus

@staticmethod
def dotstruct(a, b):
[a, m1] = a.newBuildFromNumber(1)
[b, m2] = b.newBuildFromNumber(m1)
state1 = 1
state2 = m2-1
dot = Automata()
dot.setstartstate(state1)
return dot

@staticmethod
def starstruct(a):
[a, m1] = a.newBuildFromNumber(2)
state1 = 1
state2 = m1
star = Automata()
star.setstartstate(state1)
return star

class DFAfromNFA:
"""class for building dfa from e-nfa and minimise it"""

def __init__(self, nfa):
self.buildDFA(nfa)
self.minimise()

def getDFA(self):
return self.dfa

def getAllStates(self):
return self.allstates

def getTransitions(self):
return self.trstates

def getMinimisedDFA(self):
return self.minDFA

def displayDFA(self):
self.dfa.display()

def displayMinimisedDFA(self):
self.minDFA.display()

def buildDFA(self, nfa):
allstates = dict()
eclose = dict()
count = 1
state1 = nfa.getEClose(nfa.startstate)
eclose[nfa.startstate] = state1
dfa = Automata(nfa.language)
dfa.setstartstate(count)
states = [[state1, count]]
allstates[count] = state1
count +=  1
while len(states) != 0:
[state, fromindex] = states.pop()
# Next line was originally "for char in dfa.language:"
# But returned "char" in random order, since dfa.language is a set,
# so dfa.finalstates result was not consistent
for char in sorted(dfa.language):
trstates = nfa.gettransitions(state, char)
for s in list(trstates)[:]:
if s not in eclose:
eclose[s] = nfa.getEClose(s)
trstates = trstates.union(eclose[s])
if len(trstates) != 0:
if trstates not in allstates.values():
states.append([trstates, count])
allstates[count] = trstates
toindex = count
count +=  1
else:
toindex = [k for k, v in allstates.items() if v  ==  trstates][0]

for value, state in allstates.items():
if nfa.finalstates[0] in state:

self.dfa = dfa
self.allstates = allstates
self.trstates = trstates

def acceptsString(self, string):
currentstate = self.dfa.startstate
for ch in string:
if ch==":e:":
continue
st = list(self.dfa.gettransitions(currentstate, ch))
if len(st) == 0:
return False
currentstate = st[0]
if currentstate in self.dfa.finalstates:
return True
return False

def minimise(self):
states = list(self.dfa.states)
n = len(states)
unchecked = dict()
count = 1
distinguished = []
equivalent = dict(zip(range(len(states)), [{s} for s in states]))
pos = dict(zip(states,range(len(states))))
for i in range(n-1):
for j in range(i+1, n):
if not ([states[i], states[j]] in distinguished or [states[j], states[i]] in distinguished):
eq = 1
toappend = []
for char in sorted(self.dfa.language):
s1 = self.dfa.gettransitions(states[i], char)
s2 = self.dfa.gettransitions(states[j], char)
if len(s1) != len(s2):
eq = 0
break
if len(s1) > 1:
raise BaseException("Multiple transitions detected in DFA")
elif len(s1) == 0:
continue
s1 = s1.pop()
s2 = s2.pop()
if s1 != s2:
if [s1, s2] in distinguished or [s2, s1] in distinguished:
eq = 0
break
else:
toappend.append([s1, s2, char])
eq = -1
if eq == 0:
distinguished.append([states[i], states[j]])
elif eq == -1:
s = [states[i], states[j]]
s.extend(toappend)
unchecked[count] = s
count += 1
else:
p1 = pos[states[i]]
p2 = pos[states[j]]
if p1 != p2:
st = equivalent.pop(p2)
for s in st:
pos[s] = p1
equivalent[p1] = equivalent[p1].union(st)
newFound = True
while newFound and len(unchecked) > 0:
newFound = False
toremove = set()
for p, pair in list(unchecked.items()):  #.items():
for tr in pair[2:]:
if [tr[0], tr[1]] in distinguished or [tr[1], tr[0]] in distinguished:
unchecked.pop(p)
distinguished.append([pair[0], pair[1]])
newFound = True
break
for pair in unchecked.values():
p1 = pos[pair[0]]
p2 = pos[pair[1]]
if p1 != p2:
st = equivalent.pop(p2)
for s in st:
pos[s] = p1
equivalent[p1] = equivalent[p1].union(st)
if len(equivalent) == len(states):
self.minDFA = self.dfa
else:
self.minDFA = self.dfa.newBuildFromEquivalentStates(equivalent, pos)

class NFAfromRegex:
"""class for building e-nfa from regular expressions"""

def __init__(self, regex):
self.star = '*'
# Next line was originally "self.plus = '+'
# Changed to '|' to fit aplication of regex for program
self.plus = '|'
self.dot = '.'
self.openingBracket = '('
self.closingBracket = ')'
self.operators = [self.plus, self.dot]
self.regex = regex
self.alphabet = [chr(i) for i in range(65,91)]
self.alphabet.extend([chr(i) for i in range(97,123)])
self.alphabet.extend([chr(i) for i in range(48,58)])
self.buildNFA()

def getNFA(self):
return self.nfa

def displayNFA(self):
self.nfa.display()

def buildNFA(self):
language = set()
self.stack = []
self.automata = []
previous = "::e::"
for char in self.regex:
if char in self.alphabet:
if previous != self.dot and (previous in self.alphabet or previous in [self.closingBracket,self.star]):
self.automata.append(BuildAutomata.basicstruct(char))
elif char  ==  self.openingBracket:
if previous != self.dot and (previous in self.alphabet or previous in [self.closingBracket,self.star]):
self.stack.append(char)
elif char  ==  self.closingBracket:
if previous in self.operators:
raise BaseException("Error processing '%s' after '%s'" % (char, previous))
while(1):
if len(self.stack) == 0:
raise BaseException("Error processing '%s'. Empty stack" % char)
o = self.stack.pop()
if o == self.openingBracket:
break
elif o in self.operators:
self.processOperator(o)
elif char == self.star:
if previous in self.operators or previous  == self.openingBracket or previous == self.star:
raise BaseException("Error processing '%s' after '%s'" % (char, previous))
self.processOperator(char)
elif char in self.operators:
if previous in self.operators or previous  == self.openingBracket:
raise BaseException("Error processing '%s' after '%s'" % (char, previous))
else:
else:
raise BaseException("Symbol '%s' is not allowed" % char)
previous = char
while len(self.stack) != 0:
op = self.stack.pop()
self.processOperator(op)
if len(self.automata) > 1:
print (self.automata)
raise BaseException("Regex could not be parsed successfully")
self.nfa = self.automata.pop()
self.nfa.language = language

while(1):
if len(self.stack) == 0:
break
top = self.stack[len(self.stack)-1]
if top == self.openingBracket:
break
if top == char or top == self.dot:
op = self.stack.pop()
self.processOperator(op)
else:
break
self.stack.append(char)

def processOperator(self, operator):
if len(self.automata) == 0:
raise BaseException("Error processing operator '%s'. Stack is empty" % operator)
if operator == self.star:
a = self.automata.pop()
self.automata.append(BuildAutomata.starstruct(a))
elif operator in self.operators:
if len(self.automata) < 2:
raise BaseException("Error processing operator '%s'. Inadequate operands" % operator)
a = self.automata.pop()
b = self.automata.pop()
if operator == self.plus:
self.automata.append(BuildAutomata.plusstruct(b,a))
elif operator == self.dot:
self.automata.append(BuildAutomata.dotstruct(b,a))

"""def drawGraph(automata, file = ""):
From https://github.com/max99x/automata-editor/blob/master/util.py
f = popen(r"dot -Tpng -o graph%s.png" % file, 'w')
try:
f.write(automata.getDotFile())
except:
raise BaseException("Error creating graph")
finally:
f.close()"""

def isInstalled(program):
"""From http://stackoverflow.com/questions/377017/test-if-executable-exists-in-python"""
import os
def is_exe(fpath):
return os.path.isfile(fpath) and os.access(fpath, os.X_OK)
fpath, fname = os.path.split(program)
if fpath:
if is_exe(program) or is_exe(program+".exe"):
return True
else:
for path in os.environ["PATH"].split(os.pathsep):
exe_file = os.path.join(path, program)
if is_exe(exe_file) or is_exe(exe_file+".exe"):
return True
return False

class Matrix:

def __init__(self, DFA, allstates, transitions, length):
self.length = length
self.DFA = DFA
self.allstates = allstates
dim = 0

for value, _state in allstates.items():
if value != 0:
dim += 1
dim += 1
self.dim = dim
self.matrix= self.createMatrix( self.DFA, self.allstates, transitions, self.dim)

def getDim(self):
return self.dim

def createMatrix(self, DFA, allstates, transitions, dim):

matrix = [[0]*(dim) for _ in range(dim)]
for from_state, to_state in transitions.items():
for to_state, _char in to_state.items():
matrix[from_state-1][to_state-1] = 1

return matrix

def count_paths(self, DFA, dim, length):
modulo = 1000000007
result = Matrix.pow2(self, length, self.matrix, dim, modulo)
count = 0

for i in range(dim):
for j in range(dim):
if i == 0:
for k in DFA.finalstates:
k -= 1
if j == k:
count += result[i][j]

return count % modulo

def copy(self, dim):
my_matrix = [[0]*(dim) for _ in range(dim)]
for i in range(dim):
for j in range(dim):
my_matrix[i][j] = self.matrix[i][j]

return my_matrix

def printMatrix(self, matrix, dim):
for i in range(dim):
print(matrix[i])

def pow2(self, power, matrix, dim, mod=None):

result1 = [[0]*(dim) for _ in range(dim)]
for i in range(dim):
result1[i][i] = 1
while power > 0:
if power & 1:
result1 = Matrix.mat_square_mult(self, result1, matrix, dim, mod);
power >>= 1;
if power > 0:
matrix = Matrix.mat_square_mult(self, matrix, matrix, dim, mod);
matrix = result1

return matrix

def mat_square_mult(self, matrix, other, dim, mod=None):
result = [[0]*(dim) for _ in range(dim)]
for i in range(dim):
for j in range(dim):
index = 0
for k in range(dim):
index += (matrix[i][k] * other[k][j]) % mod

result[i][j] = index
return result

def count_strings(regex, length):

nfaObj = NFAfromRegex(regex)
nfa = nfaObj.getNFA()
dfaObj = DFAfromNFA(nfa)
dfa = dfaObj.getDFA()
#minDFA = dfaObj.getMinimisedDFA()
#print ("\nNFA: ")
#nfaObj.displayNFA()
#print ("\nDFA: ")
#dfaObj.displayDFA()
#print ("\nMinimised DFA: ")
#dfaObj.displayMinimisedDFA()
#result = None
transitions = dfa.transitions
allstates = dfaObj.getAllStates()
resultObj = Matrix(dfa, allstates, transitions, length)
dim = resultObj.getDim()
result = Matrix.count_paths(resultObj, dfa, dim, length)

#The result should be 198110437 for the test input

print (result)

def main():

cases = int(input().strip())
for _i in range(cases):
in_line = input().strip().split()
regex = in_line[0]
length = int(in_line[1])
count_strings(regex, length)

if __name__  ==  '__main__':
main()```
;