daily pastebin goal
11%
SHARE
TWEET

Untitled

a guest Jun 3rd, 2018 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import(
  4.         "fmt"
  5. )
  6.  
  7.  
  8. type Mealy struct{
  9.     n, m, q int
  10.     D [][]int
  11.     F [][]string
  12. }
  13.  
  14. func (machine *Mealy) initialization(){
  15.     fmt.Scan(&machine.n, &machine.m, &machine.q)
  16.     machine.D = make([][]int, machine.n)
  17.     machine.F = make([][]string, machine.n)
  18.  
  19.     for i := 0; i < machine.n; i++ {
  20.  
  21.         machine.D[i] = make([] int, machine.m)
  22.         for j := 0; j < machine.m; j++ {
  23.             fmt.Scan(&machine.D[i][j])
  24.         }
  25.     }
  26.  
  27.     for i := 0; i < machine.n; i++ {
  28.         machine.F[i] = make([] string, machine.m)
  29.         for j := 0; j < machine.m; j++ {
  30.             fmt.Scan(&machine.F[i][j])
  31.         }
  32.     }
  33. }
  34.  
  35. func (machine *Mealy) visualization(){
  36.  
  37.     fmt.Printf("digraph {\n" + "    rankdir = LR\n" + "    dummy [label = \"\", shape = none]\n" + "    dummy -> %d\n", machine.q)
  38.  
  39.     for i := 0; i < machine.n; i++ {
  40.         fmt.Printf("    %d [shape = circle]\n", i)
  41.         for j := 0; j < machine.m; j++ {
  42.             fmt.Printf("    %d -> %d [label = \"%s(%s)\"]\n",i , machine.D[i][j], string(rune(j + 'a')), machine.F[i][j])
  43.         }
  44.     }
  45.     fmt.Println("}")
  46. }
  47.  
  48. var k = 0
  49.  
  50. func (machine *Mealy) DFS(renumeration [] int, q int){
  51.     renumeration[q] = k
  52.     k++
  53.     for _, v := range machine.D[q] {
  54.         if renumeration[v] == -1 {
  55.             machine.DFS(renumeration, v)
  56.         }
  57.     }
  58. }
  59.  
  60. func (machine *Mealy) canonization(){
  61.     k = 0
  62.     renumeration := make([] int, machine.n)
  63.     oldN := machine.n
  64.     for i := 0; i < oldN; i++ {
  65.         renumeration[i] = -1
  66.     }
  67.     machine.DFS(renumeration, machine.q)
  68.     machine.n = k
  69.     newD := make([][]int, machine.n)
  70.     newF := make([][]string, machine.n)
  71.     for i := 0; i < machine.n; i++ {
  72.         newD[i] = make([] int, machine.m)
  73.         newF[i] = make([] string, machine.m)
  74.     }
  75.     for i := 0; i < oldN; i++ {
  76.         if k := renumeration[i]; k != -1{
  77.             for j := 0; j < machine.m; j++ {
  78.                 newD[k][j] = renumeration[machine.D[i][j]]
  79.                 newF[k][j] = machine.F[i][j]
  80.             }
  81.         }
  82.     }
  83.     machine.q = 0
  84.     machine.D = newD
  85.     machine.F = newF
  86. }
  87.  
  88. func (machine *Mealy) split1 (pi []int) (m int){
  89.     m = machine.n
  90.     assoc := make([] DSF, machine.n)
  91.     for i := 0; i < machine.n; i++{
  92.         assoc[i].init(i)
  93.     }
  94.     for i := 0; i < machine.n; i++{
  95.         for j := 0; j < machine.n; j++{
  96.             if assoc[i].find() != assoc[j].find(){
  97.                 eq := true
  98.                 for k := 0; k < machine.m; k++ {
  99.                     if machine.F[i][k] != machine.F[j][k]{
  100.                         eq = false
  101.                         break
  102.                     }
  103.                 }
  104.                 if eq {
  105.                     assoc[i].union(&assoc[j])
  106.                     m--
  107.                 }
  108.             }
  109.         }
  110.     }
  111.     for i := 0; i < machine.n; i++{
  112.         pi[i] = assoc[i].find().x
  113.     }
  114.     return m
  115. }
  116.  
  117. func (machine *Mealy) split (pi []int) (m int){
  118.     m = machine.n
  119.     assoc := make([] DSF, machine.n)
  120.     for i := 0; i < machine.n; i++{
  121.         assoc[i].init(i)
  122.     }
  123.     for i := 0; i < machine.n; i++{
  124.         for j := 0; j < machine.n; j++{
  125.             if pi[i] == pi[j] && assoc[i].find() != assoc[j].find(){
  126.                 eq := true
  127.                 for k := 0; k < machine.m; k++ {
  128.                     w1, w2 := machine.D[i][k], machine.D[j][k]
  129.                     if pi[w1] != pi[w2] {
  130.                         eq = false
  131.                         break
  132.                     }
  133.                 }
  134.                 if eq {
  135.                     assoc[i].union(&assoc[j])
  136.                     m--
  137.                 }
  138.             }
  139.         }
  140.     }
  141.     for i := 0; i < machine.n; i++{
  142.         pi[i] = assoc[i].find().x
  143.     }
  144.     return m
  145. }
  146.  
  147. func (machine *Mealy) AufenkampHohn(){
  148.     pi := make([] int, machine.n)
  149.     m := machine.split1(pi)
  150.     for {
  151.         ml := machine.split(pi)
  152.         if m == ml{
  153.             break
  154.         }
  155.         m = ml
  156.     }
  157.     used := make([] bool, machine.n)
  158.     newD := make([][]int, machine.n)
  159.     newF := make([][]string, machine.n)
  160.     for i := 0; i < machine.n; i++ {
  161.         newD[i] = make([] int, machine.m)
  162.         for j := 0; j < machine.m; j++{
  163.             //newD[i][j] = -1
  164.         }
  165.         newF[i] = make([] string, machine.m)
  166.     }
  167.     for i := 0; i < machine.n; i++ {
  168.         ql := pi[i]
  169.         if !used[ql] {
  170.             used[ql] = true
  171.             for j := 0; j < machine.m; j++ {
  172.                 newD[ql][j] = pi[machine.D[i][j]]
  173.                 newF[ql][j] = machine.F[i][j]
  174.             }
  175.         }
  176.     }
  177.  
  178.     for i := 0; i < machine.n; i++ {
  179.         if !used[i]{
  180.             for j := 0; j < machine.m; j++ {
  181.                 newD[i][j] = i
  182.             }
  183.         }
  184.     }
  185.  
  186.     machine.D = newD
  187.     machine.F = newF
  188. }
  189.  
  190. func (machine *Mealy) minimization(){
  191.     machine.canonization()
  192.     machine.AufenkampHohn()
  193.     machine.canonization()
  194. }
  195.  
  196. type DSF struct {
  197.     x, depth int
  198.     parent *DSF
  199. }
  200.  
  201. func (s *DSF) init (x int){
  202.     s.x = x
  203.     s.depth = 0
  204.     s.parent = s
  205. }
  206.  
  207. func (x *DSF) find () *DSF {
  208.     if x.parent == x {
  209.         return x
  210.     } else {
  211.         return x.parent.find()
  212.     }
  213. }
  214.  
  215. func (x *DSF) union (y *DSF){
  216.     rootX := x.find()
  217.     rootY := y.find()
  218.     if rootX.depth < rootY.depth {
  219.         rootX.parent = rootY
  220.     } else {
  221.         rootY.parent = rootX
  222.         if rootX.depth == rootY.depth && rootX != rootY {
  223.             rootX.depth++
  224.         }
  225.     }
  226.  
  227. }
  228.  
  229. func  main() {
  230.  
  231.     firstMachine := &Mealy{}
  232.     secondMachine := &Mealy{}
  233.  
  234.     firstMachine.initialization()
  235.     secondMachine.initialization()
  236.  
  237.     firstMachine.minimization()
  238.     secondMachine.minimization()
  239.  
  240.     fl := firstMachine.n == secondMachine.n && firstMachine.m == secondMachine.m
  241.  
  242.     for i := 0; i < firstMachine.n && fl; i++ {
  243.         for j := 0; j < firstMachine.m && fl; j++ {
  244.             if firstMachine.D[i][j] != secondMachine.D[i][j] || firstMachine.F[i][j] != secondMachine.F[i][j]{
  245.                 fl = false
  246.             }
  247.         }
  248.     }
  249.  
  250.     if fl {
  251.         fmt.Print("EQUAL")
  252.     } else {
  253.         fmt.Print("NOT EQUAL")
  254.     }
  255. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top