by
0
4
248
0
Top 1% !
Tagged
Specified
OpenSource
Popularity: 17729th place
Created
Modified Sep 24, 2016

Published on:

Languagepython
LicenseMIT_X11

Hackerrank Count Strings solution python

Hackerrank Count Strings solution python
post this code
Copy Embed Code
<iframe id="embedFrame" style="width:600px; height:300px;"
src="https://www.snip2code.com/Embed/1452912/Hackerrank-Count-Strings-solution-python?startLine=0"></iframe>
Click on the embed code to copy it into your clipboard Width Height
Leave empty to retrieve all the content Start End
''' 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 self.states.add(state) def addfinalstates(self, state): if isinstance(state, int): state = [state] for s in state: if s not in self.finalstates: self.finalstates.append(s) def addtransition(self, fromstate, tostate, inp): if isinstance(inp, str): inp = set([inp]) self.states.add(fromstate) self.states.add(tostate) 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} def addtransition_dict(self, transitions): for fromstate, tostates in transitions.items(): for state in tostates: self.addtransition(fromstate, state, tostates[state]) 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]: trstates.add(tns) return trstates def getEClose(self, findstate): allstates = set() states = set([findstate]) while len(states)!= 0: state = states.pop() allstates.add(state) if state in self.transitions: for tns in self.transitions[state]: if Automata.epsilon() in self.transitions[state][tns] and tns not in allstates: states.add(tns) 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]) rebuild.addfinalstates(translations[self.finalstates[0]]) for fromstate, tostates in self.transitions.items(): for state in tostates: rebuild.addtransition(translations[fromstate], translations[state], tostates[state]) return [rebuild, startnum] def newBuildFromEquivalentStates(self, equivalent, pos): # Added "sorted" next line rebuild = Automata(sorted(self.language)) for fromstate, tostates in self.transitions.items(): for state in tostates: rebuild.addtransition(pos[fromstate], pos[state], tostates[state]) rebuild.setstartstate(pos[self.startstate]) for s in self.finalstates: rebuild.addfinalstates(pos[s]) 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) basic.addfinalstates(state2) basic.addtransition(1, 2, inp) 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) plus.addfinalstates(state2) plus.addtransition(plus.startstate, a.startstate, Automata.epsilon()) plus.addtransition(plus.startstate, b.startstate, Automata.epsilon()) plus.addtransition(a.finalstates[0], plus.finalstates[0], Automata.epsilon()) plus.addtransition(b.finalstates[0], plus.finalstates[0], Automata.epsilon()) plus.addtransition_dict(a.transitions) plus.addtransition_dict(b.transitions) 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) dot.addfinalstates(state2) dot.addtransition(a.finalstates[0], b.startstate, Automata.epsilon()) dot.addtransition_dict(a.transitions) dot.addtransition_dict(b.transitions) return dot @staticmethod def starstruct(a): [a, m1] = a.newBuildFromNumber(2) state1 = 1 state2 = m1 star = Automata() star.setstartstate(state1) star.addfinalstates(state2) star.addtransition(star.startstate, a.startstate, Automata.epsilon()) star.addtransition(star.startstate, star.finalstates[0], Automata.epsilon()) star.addtransition(a.finalstates[0], star.finalstates[0], Automata.epsilon()) star.addtransition(a.finalstates[0], a.startstate, Automata.epsilon()) star.addtransition_dict(a.transitions) 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] dfa.addtransition(fromindex, toindex, char) for value, state in allstates.items(): if nfa.finalstates[0] in state: dfa.addfinalstates(value) 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 = [] # Added "sorted" next line 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: language.add(char) if previous != self.dot and (previous in self.alphabet or previous in [self.closingBracket,self.star]): self.addOperatorToStack(self.dot) 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.addOperatorToStack(self.dot) 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: self.addOperatorToStack(char) 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 def addOperatorToStack(self, char): 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()
If you want to be updated about similar snippets, Sign in and follow our Channels

blog comments powered by Disqus