shek15470

Untitled

Jun 14th, 2021
700
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.         "fmt"
  5.     "strconv"
  6. )
  7. type Transition struct {
  8.     nextState int
  9.     label     string
  10. }
  11.  
  12. type State struct {
  13.     pos         int
  14.     transitions []Transition
  15.     isFinal     bool
  16. }
  17.  
  18.  
  19. type Machine struct {
  20.     states []State
  21.     X      []string
  22.     F      []int
  23.     statesAmount int
  24. }
  25.  
  26.  
  27. type HashTable struct {
  28.     place   int
  29.     isTaken bool
  30. }
  31.  
  32.  
  33. func (m *Machine) addState(s string){
  34.     if s=="lambda"{
  35.         return
  36.     }
  37.     for _,S:=range m.X{
  38.         if s==S{
  39.             return
  40.         }
  41.     }
  42.     m.X=append(m.X,s)
  43. }
  44.  
  45. func (v *State) addEdge(e Transition){
  46.     v.transitions =append(v.transitions,e)
  47. }
  48.  
  49. var lambda string
  50.  
  51. func main() {
  52.     var n,m int
  53.     lambda="lambda"
  54.     fmt.Scan(&n,&m)
  55.     machine := Machine{}
  56.     machine.states =make([]State,n)
  57.     machine.X=make([]string,0)
  58.     machine.F=make([]int,n)
  59.     for i:=0;i<n;i++{
  60.         machine.states[i].pos =i;
  61.         machine.states[i].transitions =make([]Transition,0)
  62.     }
  63.     machine.statesAmount=m
  64.     from,to,s:=0,0,""
  65.     for i:=0;i<m;i++ {
  66.         fmt.Scan(&from, &to, &s)
  67.         machine.states[from].addEdge(Transition{to, s})
  68.         machine.addState(s)
  69.     }
  70.     for i:=0;i<n;i++{
  71.         fmt.Scan(&machine.F[i])
  72.     }
  73.     var k int
  74.     fmt.Scan(&k)
  75.     fmt.Println(Det(&machine, machine.states[k]))
  76. }
  77.  
  78.  
  79. type Set struct {
  80.     set []State
  81. }
  82.  
  83. func (set *Set) init(){
  84.     set.set=make([]State,0)
  85. }
  86. func (set *Set) add(q State)bool{
  87.     for _,elem:=range set.set{
  88.         if elem.pos ==q.pos {
  89.             return false
  90.         }
  91.     }
  92.     set.set=append(set.set,q)
  93.     return true
  94. }
  95.  
  96. func Closure(z []State, machine Machine) []State {
  97.     set:=Set{}
  98.     set.init()
  99.     for i:=0;i<len(z);i++{
  100.         dfs(z[i], machine,&set)
  101.     }
  102.     return set.set
  103. }
  104.  
  105. func dfs(q State,  machine Machine,set *Set,) {
  106.     if set.add(q) {
  107.         for _, transition := range machine.states[q.pos].transitions {
  108.             if transition.label == lambda {
  109.                 dfs(machine.states[transition.nextState], machine,set)
  110.             }
  111.         }
  112.     }
  113. }
  114.  
  115. var hashTable []HashTable
  116.  
  117. func getValue(nodes []State,size int) int{
  118.     sum, multi, sqr :=0,1,0
  119.     for _, node :=range nodes {
  120.         multi *= node.pos
  121.         sum += node.pos
  122.         sqr += node.pos * node.pos
  123.     }
  124.     sum = sum + multi + sqr
  125.     res:=sum%size
  126.     return res
  127. }
  128.  
  129.  
  130. func evalSize(machine *Machine){
  131.     if machine.statesAmount>5{
  132.         size=100
  133.     }else {
  134.         size=10
  135.     }
  136. }
  137.  
  138. var size int
  139. func Det(machine *Machine,q State) string{
  140.     evalSize(machine)
  141.     Q,q0, container,F, labels := createCapabilities(q, machine)
  142.     hashTable=make([]HashTable,size)
  143.     container = append(container,q0)
  144.     hashTable[getValue(q0,size)]= HashTable{0,true}
  145.     return DOT(determine(Q, container, machine,F, 1,labels))
  146. }
  147.  
  148. func determine(Q [][]State, container [][]State, machine *Machine,F [][]State, index int,labels [][]string) ([][]State,[][]State,[][]string){
  149.     for ;len(container)>0;{
  150.         z:= container[0]
  151.         for _, state :=range z{
  152.             if machine.F[state.pos]!=0{
  153.                 F=append(F,z)
  154.                 break
  155.             }
  156.         }
  157.         for _,a:=range machine.X{
  158.             states:=connectSets(z,machine,a)
  159.             if !hashTable[getValue(states,size)].isTaken {
  160.                 Q = append(Q, states)
  161.                 container = append(container, states)
  162.                 hashTable[getValue(states,size)] = HashTable{index,true}
  163.                 index++
  164.             }
  165.             labels[hashTable[getValue(z,size)].place][hashTable[getValue(states,size)].place]+=a
  166.             labels[hashTable[getValue(z,size)].place][hashTable[getValue(states,size)].place]+=", "
  167.         }
  168.         container1 := container[1:]
  169.         container=container1
  170.     }
  171.     return Q,F,labels
  172. }
  173.  
  174.  
  175. func connectSets(z []State,machine *Machine, lbl string) []State{
  176.     states :=make([]State,0)
  177.     for _, state :=range z{
  178.         for _, transition :=range state.transitions {
  179.             if transition.label== lbl {
  180.                 states =append(states, machine.states[transition.nextState])
  181.             }
  182.         }
  183.     }
  184.     states = Closure(states,*machine)
  185.     return states
  186. }
  187.  
  188. func createCapabilities(q State, machine *Machine)([][]State,[]State,[][]State,[][]State,[][]string){
  189.     q0:=make([]State,0)
  190.     q0=append(q0,q)
  191.     q0= Closure(q0,*machine)
  192.     Q:=make([][]State,0)
  193.     Q=append(Q,q0)
  194.     stks :=make([][]State,0)
  195.     F:=make([][]State,0)
  196.     delta_matrix :=make([][]string,size)
  197.     for i:=0;i<len(delta_matrix);i++{
  198.         delta_matrix[i]=make([]string, size)
  199.     }
  200.     return Q,q0,stks,F,delta_matrix
  201. }
  202. func DOT(states [][]State, Final [][]State, labels [][]string)string{
  203.     final:=make([]bool,len(states))
  204.     for i:=0;i<len(Final);i++ {
  205.         final[hashTable[getValue(Final[i],size)].place]=true
  206.     }
  207.     for _,z:=range states {
  208.         quickSort(z)
  209.     }
  210.     output:= composer(states,final, labels)
  211.     return output
  212. }
  213.  
  214. func composer(states [][]State, final []bool, labels [][]string)string{
  215.     output :="digraph {\nrankdir = LR\ndummy [label = \"\", shape = none]"
  216.     output +="\n"
  217.     output=DOTArticle(states,output,final)
  218.     output +="dummy -> 0"+"\n"
  219.     output=connectLabels(states,labels,output)
  220.     output +="}"
  221.     return output+"\n"
  222. }
  223.  
  224.  
  225. func connectLabels(states [][]State,labels [][]string,output string)string{
  226.     for i:=0;i<len(states);i++{
  227.         for j:=0;j<len(labels[i]);j++ {
  228.             if labels[i][j] != "" {
  229.                 output += strconv.Itoa(i) + " -> " + strconv.Itoa(j)+" [ label = \""+ labels[i][j][:len(labels[i][j])-2]+"\"]"
  230.                 output+="\n"
  231.             }
  232.         }
  233.     }
  234.     return output
  235. }
  236.  
  237. func DOTArticle(states [][]State,output string,final []bool)string{
  238.     for i:=0;i<len(states);i++{
  239.         output +=strconv.Itoa(i)+" [ label =\"["
  240.         for j:=0;j<len(states[i]);j++ {
  241.             if j == len(states[i])-1 {
  242.                 output += strconv.Itoa(states[i][j].pos)
  243.             } else {
  244.                 output += strconv.Itoa(states[i][j].pos) + " "
  245.             }
  246.         }
  247.         output +="]\", shape = "
  248.         if final[i]{
  249.             output +="doublecircle]"
  250.             output+="\n"
  251.         }else{
  252.             output +="circle]"+"\n"
  253.         }
  254.     }
  255.     return output
  256. }
  257.  
  258. func partrition(l,h int,z []State)int{
  259.     i,j:=l,l
  260.     for ;j<h;j++{
  261.         if z[j].pos<z[h].pos{
  262.             z[i],z[j]=z[j],z[i]
  263.             i++
  264.         }
  265.     }
  266.     z[i],z[h]=z[h],z[i]
  267.     return i
  268. }
  269.  
  270. func quickSort(z []State){
  271.     quickSortRec(0, len(z)-1,z)
  272. }
  273. func quickSortRec(l,h int,z []State){
  274.     if l<h{
  275.         q:=partrition(l,h,z)
  276.         quickSortRec(l,q-1,z)
  277.         quickSortRec(q+1,h,z)
  278.     }
  279. }
RAW Paste Data