Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique: Difference between revisions

Content added Content deleted

Inline

Revision as of 16:43, 7 August 2019

Section 3.3 of [Generalised 2-designs with Block Size 3(Andy L. Drizen)] describes a method of generating Latin Squares of order n attributed to Jacobson and Matthews. The purpose of this task is to produce a function which given a valid Latin Square transforms it to another using this method.

part 1

Use one of the 4 Latin Squares in reduced form of order 4 as X0 to generate 10000 Latin Squares using X(n-1) to generate X(n). Convert the resulting Latin Squares to their reduced form, display them and the number of times each is produced.

part 2

As above for order 5, but do not display the squares. Generate the 56 Latin Squares in reduced form of order 5, confirm that all 56 are produced by the Jacobson and Matthews technique and display the number of each produced.

part 3

Generate 750 Latin Squares of order 42 and display the 750th.

part 4

Generate 1000 Latin Squares of order 256. Don't display anything but confirm the approximate time taken and anything else you may find interesting

F#

The Functions

<lang fsharp> // Jacobson and Matthews technique for generating Latin Squares. Nigel Galloway: August 5th., 2019 let R=let N=System.Random() in (fun n->N.Next(n)) let jmLS α X0=

 let X0=Array2D.copy X0
 let N=let N=[|[0..α-1];[α-1..(-1)..0]|] in (fun()->N.[R 2])
 let rec randLS i j z i' j' z'=
   X0.[i,j']<-z'; X0.[i',j]<-z'
   match X0.[i',j']=z' with
    true->X0.[i',j']<-z; X0
   |false->randLS i' j' z' (List.find(fun n->X0.[n,j']=z')(N())) (List.find(fun n->X0.[i',n]=z')(N())) (if (R 2)=0 then let t=X0.[i',j'] in X0.[i',j']<-z; t else z)
 let i,j=R α,R α
 let z  =let z=1+(R (α-1)) in if z<X0.[i,j] then z else 1+(z+1)%α
 let i',j',z'=let N=[0..α-1] in (List.find(fun n->X0.[n,j]=z) N,List.find(fun n->X0.[i,n]=z) N,X0.[i,j])
 X0.[i,j]<-z; randLS i j z i' j' z'

let asNormLS α=

 let n=Array.init (Array2D.length1 α) (fun n->(α.[n,0]-1,n))|>Map.ofArray
 let g=Array.init (Array2D.length1 α) (fun g->(α.[n.[0],g]-1,g))|>Map.ofArray
 Array2D.init (Array2D.length1 α) (Array2D.length1 α) (fun i j->α.[n.[i],g.[j]])

let randLS α=Seq.unfold(fun g->Some(g,jmLS α g))(Array2D.init α α (fun n g->1+(n+g)%α)) </lang>

The Task

part 1

<lang fsharp> randLS 4 |> Seq.take 10000 |> Seq.map asNormLS |> Seq.countBy id |> Seq.iter(fun n->printf "%A was produced %d times\n\n" (fst n)(snd n)) </lang>

Output:

[[1; 2; 3; 4]
 [2; 3; 4; 1]
 [3; 4; 1; 2]
 [4; 1; 2; 3]] was produced 2920 times

[[1; 2; 3; 4]
 [2; 4; 1; 3]
 [3; 1; 4; 2]
 [4; 3; 2; 1]] was produced 2262 times

[[1; 2; 3; 4]
 [2; 1; 4; 3]
 [3; 4; 2; 1]
 [4; 3; 1; 2]] was produced 2236 times

[[1; 2; 3; 4]
 [2; 1; 4; 3]
 [3; 4; 1; 2]
 [4; 3; 2; 1]] was produced 2582 times

part 2

<lang fsharp> randLS 4 |> Seq.take 10000 |> Seq.map asNormLS |> Seq.countBy id |> Seq.iteri(fun n g->printf "%d(%d) " (n+1) (snd g)); printfn "" </lang>

Output:

1(176) 2(171) 3(174) 4(165) 5(168) 6(182) 7(138) 8(205) 9(165) 10(174) 11(157) 12(187) 13(181) 14(211) 15(184) 16(190) 17(190) 18(192) 19(146) 20(200) 21(162) 22(153) 23(193) 24(156) 25(148) 26(188) 27(186) 28(198) 29(178) 30(217) 31(185) 32(172) 33(223) 34(147) 35(203) 36(167) 37(188) 38(152) 39(165) 40(187) 41(160) 42(199) 43(140) 44(202) 45(186) 46(182) 47(175) 48(161) 49(179) 50(175) 51(201) 52(195) 53(205) 54(183) 55(155) 56(178)

part 3

<lang fsharp> let q=Seq.item 749 (randLS 42) for n in [0..41] do (for g in [0..41] do printf "%3d" q.[n,g]); printfn "" </lang>

Output:

 16  7 41 15 17 40 12  9 10  5 19 29 21 18  8 22  3 36 23 31 11 38 13 30  2 33  6 42 39 14 32 20 28 35 26  1 34 37 27 24  4 25
 38 25 36 32 40 29 35 27  8 26 31 15  9  7 16 11  4  3 12 20 23 33  5 24 41 14 30 34 42 17 39 18 37 22 21 13  1 10  6 19  2 28
  8 34 27 25 21 31  1 23 37 36 26 13 22 24 35 17 10 40 41 30 42  7 15  2 18  3 29 11 32  4 38 39  9  5 16 14 28 12 20 33 19  6
 33 35 13 34 15 24  4 29 41 27  3 17 10 26 39 23 30 32  1 38 16 25 37 14  6 28 19  9 40  5 18  7 42 11 31 20 12 22  2 21  8 36
  2 42 20  1  7 26 11 10 39 41 34 22 40 23 24 29 14 17  5 33 38 30  6 13  3 16 18 19 31 15 28 21 36 37 32 27  8  4 25  9 35 12
 25 33 14 40 28 30 31 24 29  4  8 20 26 38 12 35  2 39 16  6 13 21 18 17  5 41 23  3 36  7 34 22 27  1 10 42 11 19 15 32 37  9
 17 22 35 28 30 18 21  2 15 39  5 40 27 13  1 34 38 37 26 23 41 36  4  3 11  6 20  8  9 10 12 24 31 25  7 29 16 32 42 14 33 19
 14  9 19  7 26 15 10  4 36 25 22 23 39 16  2 40 18  1 38 13 21 37 34 31 35 24 12 27 11  3  5  6 17 20 41 33 32 29  8 30 28 42
  5 27 24 13  2 36 25 30 23  9  6 14 35 15 42 39 16 26 21 34 33 31  3  1 29 12 38 17 37 19 40  4  7  8 22 41 20 28 32 10 18 11
 19 41 28 26  8 10 30 35 18 33 15 27 25 21 29 42 23 12 17  2  5  1 38  6 20  7 34  4 13 36 24 31 14  3 11 32 39 40  9 22 16 37
 41 10  3 19 22  9 27 40  1 29 16 42 33 39 34  7 37 20 11 12  4 18 35  8 28 26 36  5 17 30 25 32  6 15 24 21 13 23 14  2 38 31
 42  3 16 36 33 21 20 14 31 22  9 38 29 19 37 13 28 10 35 18 39 26 25 27  4 30 15 23 41 24 11  1 40  7  5 17  6  2 12  8 34 32
 23 31 34 41 38 33  3 28  4  1 30 25  6  2 20 14 13 24  8 42  7 12 39 32 22 29  5 37 15  9 27 10 35 36 19 40 17 18 16 11 26 21
 37 16 30 11  4 32 42 33 13  6 14  2 15 27 18 31 20 41 39 40  9 24 36  5 10  8  1 26  3 34 22 28 38 19 29 23 21 25 35 12 17  7
  1 19 26 22 16 25 36 39  3 23 41 37 34  6 17 32 40 21 10 27 12  9 31  7 13  4 24 29  8 11  2  5 15 18 35 28 30 20 33 38 42 14
 11 13 23 30 25 41  6 31 14 32 27 36 19 17 10 33 21 15  7  5  8 28 16 35 34 42 40  2 38 39  9 26 20 24 37  4 18  3 22  1 12 29
 24 17 29 38 23 39 32  5 11 15 35 12  8 10 40  1 22 25  2 36 28  4 42 21  9 20  3 31 16 41 13 30 19 34 33 18 27  6  7 37 14 26
 36  4  6 24 12 20  2 34 40 11 32  9 28  8 38 21  5 31 42 17 14 29 19 22 25 15  7 18 30 26  1 13 16 41 23 39 37 33  3 35 10 27
 20 39  2 12 32  7 22  3 17 10 37  6 18 40 27  5 42 35 28  4 24 14 33 29 30 31 26 13 19 23 36 41  1 21  9 11 15  8 34 16 25 38
 35 18 37  6  5 13 29  8 24 19 38 34 12 31 21 10 33  7  3 41 15 42 20 11 27 40 16 14 23  1  4  2 22 32 28  9 25 30 26 39 36 17
 10 32  9 33 39 19 41 38 35 18 28 26 14 30  7  4  1 22 37 21 31 40 27 15 42 34  2 25  5 12 23 36  8  6 17  3 29 24 11 13 20 16
 13 28 39  2 31  8  9 37 21 16 40 19 42 36 41  3 12 14 20 10 17 34  1 33 32 35 25 30 18 38 15 11 24 23  6 26  4  5 29  7 27 22
  7 40 12 39 18  3 16 21 42 17  1 32  5 33 13  6 41  8 29 14 34 35 24 36 38 25 31 28 26 27 20 37 23  2 30 10 22  9 19  4 11 15
  4 21  7 17 35 34 19 25 12 42 11  1 30 28 36 26 32 23 14 29  2 20  8 41 24 27 22 15 10 18 37  9 39 38 13  6  3 16 31 40  5 33
 34 23 42 14 41 27 37  6  9 31  4  5  7  1 25 16 35 30 33 11 19  3 26 12 17 38  8 20 24 13 29 15 32 28 40 22  2 39 18 36 21 10
 30  6 21  9 20 17  5 32 38 13 12 28 16 35 22 36 34 29 40 39 25 15 14 37 33 11  4 41  1  2 19  3 26 27 42  8 10  7 23 31 24 18
  6 38  8 10 42 35 13  1 16 37 21  3 11 34 32 20 29 18 25 22 36  5 30 26 39 23 28 12  2 31  7 19 33 40 14 24  9 41 17 27 15  4
 29 15  1 21 14 11 26 17 30 38 10 33 36 20  4 18 39 16 31  3 35  2 32 28 19 13 42  7 12  8  6 40  5  9 25 37 24 27 41 23 22 34
 21 36 32  8  6 23 15 19  2 14 18  4  3 11  5 28 26 13 34 25 30 17  7 42 16 22 39 40 29 37 33 12 41 10 27 31 35 38 24 20  9  1
 39 20 31 29 19  4 38 16 27 30 24 11  2  3 33 15  8 28 18 37 10 13  9 23 36  1 17 22 25 32 26 35 12 42 34  7 40 14 21  5  6 41
 12 11 17 42  9  2 14  7 22 24 25 31 38 41 15 19 36 33 32 28  1 10 29 40 23 18 37 39  6 21 35 27  3 16  8 30  5 26  4 34 13 20
 18 29 33 16 27 42 40 26  7  8 39 24 41  5 30 38  6  9 13  1 32 22  2 34 12 37 11 10 35 20 14 17 21  4 15 19 23 36 28 25 31  3
 28  2  4 18 11  5 23 20 25 35 42 30 31 14  3  9 24 27 19  7 22  6 12 10  1 32 41 36 21 33 16 34 29 13 39 15 38 17 37 26 40  8
  3 26 11 35 24 37 17 36  6  7 13 41  4 32  9  2 31 34 22 15 29  8 40 18 21  5 27  1 14 16 10 38 25 33 20 12 19 42 39 28 30 23
 31  5 22 27 10  6  8 13 34  2 33  7 32 42 26 12 19  4 15  9 40 16 28 38 37 39 35 24 20 29 17 23 11 14  3 25 41 21 36 18  1 30
 15 24  5 37  3 28  7 22 19 34 20 18 17 12 23  8 25 11 36 16 27 41 10  4 31  2  9 32 33 42 21 14 13 29 38 35 26  1 30  6 39 40
 27 37 25  5 13 16 24 41 28  3  2 10 23  4 14 30 11 38  6 19 26 32 21 20 40  9 33 35 34 22 42  8 18 17 12 36 31 15  1 29  7 39
 26 30 10  3 36 22 33 11  5 20 29 21 13 25 31 37 17  2  9 35 18 27 23 39 14 19 32 16 28  6  8 42  4 12  1 38  7 34 40 15 41 24
 32  8 18 31  1 14 34 12 33 28 17 39 37  9 19 27  7  5 30 24 20 23 11 25 15 36 21  6 22 40 41 16 10 26  4  2 42 35 38  3 29 13
  9 14 40 23 37 38 18 15 20 12 36  8  1 22 28 24 27 42  4 32  6 11 41 19 26 10 13 21  7 25 30 29 34 39  2 16 33 31  5 17  3 35
 22 12 15  4 34  1 39 42 32 40  7 35 20 29 11 25  9  6 24 26 37 19 17 16  8 21 14 38 27 28  3 33 30 31 18  5 36 13 10 41 23  2
 40  1 38 20 29 12 28 18 26 21 23 16 24 37  6 41 15 19 27  8  3 39 22  9  7 17 10 33  4 35 31 25  2 30 36 34 14 11 13 42 32  5

Go

The J & M implementation is based on the C code here. Although this produces satisfactory results for Parts 1 and 2, it is glacial for Part 3 and could only generate 5 order 42 Latin squares in around 22 seconds. Optimizing the code somewhat gets this down to about 14 seconds which suggests that the full 750 could be generated in about 35 minutes though Part 4 is still well out of reach.

All timings are for my Celeron @1.6 GHz and will therefore be much faster on a more modern machine though probably still far too slow for the later Parts. <lang go>package main

import (

   "fmt"
   "math/rand"
   "time"

)

type (

   vector []int
   matrix []vector
   cube   []matrix

)

func toReduced(m matrix) matrix {

   n := len(m)
   r := make(matrix, n)
   for i := 0; i < n; i++ {
       r[i] = make(vector, n)
       copy(r[i], m[i])
   }
   for j := 0; j < n-1; j++ {
       if r[0][j] != j {
           for k := j + 1; k < n; k++ {
               if r[0][k] == j {
                   for i := 0; i < n; i++ {
                       r[i][j], r[i][k] = r[i][k], r[i][j]
                   }
                   break
               }
           }
       }
   }
   for i := 1; i < n-1; i++ {
       if r[i][0] != i {
           for k := i + 1; k < n; k++ {
               if r[k][0] == i {
                   for j := 0; j < n; j++ {
                       r[i][j], r[k][j] = r[k][j], r[i][j]
                   }
                   break
               }
           }
       }
   }
   return r

}

// 'm' is assumed to be 0 based func printMatrix(m matrix) {

   n := len(m)
   for i := 0; i < n; i++ {
       for j := 0; j < n; j++ {
           fmt.Printf("%2d ", m[i][j]+1) // back to 1 based
       }
       fmt.Println()
   }
   fmt.Println()

}

// converts 4 x 4 matrix to 'flat' array func asArray16(m matrix) [16]int {

   var a [16]int
   k := 0
   for i := 0; i < 4; i++ {
       for j := 0; j < 4; j++ {
           a[k] = m[i][j]
           k++
       }
   }
   return a

}

// converts 5 x 5 matrix to 'flat' array func asArray25(m matrix) [25]int {

   var a [25]int
   k := 0
   for i := 0; i < 5; i++ {
       for j := 0; j < 5; j++ {
           a[k] = m[i][j]
           k++
       }
   }
   return a

}

// 'a' is assumed to be 0 based func printArray16(a [16]int) {

   for i := 0; i < 4; i++ {
       for j := 0; j < 4; j++ {
           k := i*4 + j
           fmt.Printf("%2d ", a[k]+1) // back to 1 based
       }
       fmt.Println()
   }
   fmt.Println()

}

func shuffleCube(c cube) {

   n := len(c[0])
   proper := true
   iters := n * n * n
   for i := 0; i < iters; i++ {
       var rx, ry, rz int
       for {
           rx = rand.Intn(n)
           ry = rand.Intn(n)
           rz = rand.Intn(n)
           if c[rx][ry][rz] == 0 {
               break
           }
       }
       for {
           var ox, oy, oz int
           for ; ox < n; ox++ {
               if c[ox][ry][rz] == 1 {
                   break
               }
           }
           if !proper && rand.Intn(2) == 0 {
               for ox++; ox < n; ox++ {
                   if c[ox][ry][rz] == 1 {
                       break
                   }
               }
           }

           for ; oy < n; oy++ {
               if c[rx][oy][rz] == 1 {
                   break
               }
           }
           if !proper && rand.Intn(2) == 0 {
               for oy++; oy < n; oy++ {
                   if c[rx][oy][rz] == 1 {
                       break
                   }
               }
           }

           for ; oz < n; oz++ {
               if c[rx][ry][oz] == 1 {
                   break
               }
           }
           if !proper && rand.Intn(2) == 0 {
               for oz++; oz < n; oz++ {
                   if c[rx][ry][oz] == 1 {
                       break
                   }
               }
           }

           c[rx][ry][rz]++
           c[rx][oy][oz]++
           c[ox][ry][oz]++
           c[ox][oy][rz]++

           c[rx][ry][oz]--
           c[rx][oy][rz]--
           c[ox][ry][rz]--
           c[ox][oy][oz]--

           if c[ox][oy][oz] < 0 {
               rx, ry, rz = ox, oy, oz
               proper = false
           } else {
               proper = true
               break
           }
       }
   }

}

func toMatrix(c cube) matrix {

   n := len(c[0])
   m := make(matrix, n)
   for i := 0; i < n; i++ {
       m[i] = make(vector, n)
   }
   for i := 0; i < n; i++ {
       for j := 0; j < n; j++ {
           for k := 0; k < n; k++ {
               if c[i][j][k] != 0 {
                   m[i][j] = k
                   break
               }
           }
       }
   }
   return m

}

// 'from' matrix is assumed to be 1 based func makeCube(from matrix, n int) cube {

   c := make(cube, n)
   for i := 0; i < n; i++ {
       c[i] = make(matrix, n)
       for j := 0; j < n; j++ {
           c[i][j] = make(vector, n)
           var k int
           if from == nil {
               k = (i + j) % n
           } else {
               k = from[i][j] - 1
           }
           c[i][j][k] = 1
       }
   }
   return c

}

func main() {

   rand.Seed(time.Now().UnixNano())

   // part 1
   fmt.Println("PART 1: 10,000 latin Squares of order 4 in reduced form:\n")
   from := matrix{{1, 2, 3, 4}, {2, 1, 4, 3}, {3, 4, 1, 2}, {4, 3, 2, 1}}
   freqs4 := make(map[[16]int]int, 10000)
   c := makeCube(from, 4)
   for i := 1; i <= 10000; i++ {
       shuffleCube(c)
       m := toMatrix(c)
       rm := toReduced(m)
       a16 := asArray16(rm)
       freqs4[a16]++
   }
   for a, freq := range freqs4 {
       printArray16(a)
       fmt.Printf("Occurs %d times\n\n", freq)
   }

   // part 2
   fmt.Println("\nPART 2: 10,000 latin squares of order 5 in reduced form:")
   from = matrix{{1, 2, 3, 4, 5}, {2, 3, 4, 5, 1}, {3, 4, 5, 1, 2},
       {4, 5, 1, 2, 3}, {5, 1, 2, 3, 4}}
   freqs5 := make(map[[25]int]int, 10000)
   c = makeCube(from, 5)
   for i := 1; i <= 10000; i++ {
       shuffleCube(c)
       m := toMatrix(c)
       rm := toReduced(m)
       a25 := asArray25(rm)
       freqs5[a25]++
   }
   count := 0
   for _, freq := range freqs5 {
       count++
       if count > 1 {
           fmt.Print(", ")
       }
       if (count-1)%8 == 0 {
           fmt.Println()
       }
       fmt.Printf("%2d(%3d)", count, freq)
   }
   fmt.Println("\n")

   // part 3
   fmt.Println("\nPART 3: 5 latin squares of order 42, showing the last one:\n")
   start := time.Now()
   var m42 matrix
   c = makeCube(nil, 42)
   for i := 1; i <= 5; i++ {
       shuffleCube(c)
       m42 = toMatrix(c)
   }
   elapsed := time.Since(start)
   printMatrix(m42)
   fmt.Printf("Took %s\n", elapsed)

}</lang>

Output:

Sample run:

PART 1: 10,000 latin Squares of order 4 in reduced form:

 1  2  3  4 
 2  1  4  3 
 3  4  1  2 
 4  3  2  1 

Occurs 2509 times

 1  2  3  4 
 2  4  1  3 
 3  1  4  2 
 4  3  2  1 

Occurs 2571 times

 1  2  3  4 
 2  3  4  1 
 3  4  1  2 
 4  1  2  3 

Occurs 2446 times

 1  2  3  4 
 2  1  4  3 
 3  4  2  1 
 4  3  1  2 

Occurs 2474 times


PART 2: 10,000 latin squares of order 5 in reduced form:

 1(183),  2(189),  3(162),  4(188),  5(191),  6(171),  7(154),  8(212), 
 9(169), 10(177), 11(198), 12(174), 13(181), 14(177), 15(189), 16(162), 
17(202), 18(188), 19(167), 20(194), 21(167), 22(158), 23(157), 24(154), 
25(183), 26(160), 27(192), 28(186), 29(187), 30(171), 31(159), 32(182), 
33(156), 34(198), 35(165), 36(170), 37(166), 38(163), 39(182), 40(161), 
41(198), 42(188), 43(176), 44(190), 45(217), 46(178), 47(153), 48(199), 
49(178), 50(158), 51(192), 52(205), 53(177), 54(184), 55(183), 56(179)


PART 3: 5 latin squares of order 42, showing the last one:

18 21 11 26  2  8 25 39 38 24  3 19 33 37  5 16 30  4  9 40 32 31 36 22  1 42  7 12 27 35 23 13 17 14 15 10 41 29 20 34  6 28 
41 30  9 40 37 11 16 14  2 32 42 33  7  5 12  1 18 34 23 19 26 22 35 25 36 24  4 21 28  6 39 15 20  8 27 38 17  3 13 10 31 29 
 8 29 34  2 19  3  6  4 23 30 36 38 11 39 26 28 10  7 22 24 42 25 16 32 17 14  5  9 33 41 31 40 18 27 13  1 37 21 35 12 20 15 
30 15  8 18 28  7 31  2 16 10 38  4 26 29 17 25  9 35 14 20 41 33 39 11 24  5  3 36 21 27  1 23 37 40 42 22 12 19 34 32 13  6 
39 41 20 17 27 19 24 38 34 16  6 32 29 13 28  3 25  8  1 11 31 12 10 33 23 21 37  2 40  5 18 22 14  7 26 35  9 42 15 36  4 30 
 2  1 23 15 26 35 36 29 13  6 27 31 12 30 40  7 39 19  3 34 21 17 42 20 14 38  9  8 41 11 22 33  4  5 24 28 18 37 25 16 32 10 
28 31  7 10 40 24 30 11 35 23 33 17 32 18 22 12 42 25 13 15  8 21  9 16 41  3 27  5 38 36  6 20 19  4  1 29 39 34 26  2 14 37 
 6 26  3 12 13 40 38 30 33 17 20 29 28  9 34 15 24 32 39 14 11  8 25 21 19  1 35 23  5 16  2 41 36 31  7 37 22  4 10 18 42 27 
19  5 26 31 36 12 33  6  4  1 21 27 38 17  7 20 34 14 32 22  3  2  8 10  9 35 16 18 39 15 37 42 41 29 28 24 30 13 11 40 23 25 
 5 22 36 11 29 42 41 17 39 40  4  9  8 25  1 21  3 24  7 23 35 13 27 26 38 12 33 31 14 28 15 18  2 34 32 20 10 30  6 19 37 16 
33 36 32 28 11 17 14  9 25 21 23  7 15  3 24  2  4 22 31 26 30 10 34 41 27 19 38 29  1 40 20 35 13 18  6 39  8 16 42 37 12  5 
16 25 10  3 23 26 20 32 17  5 31 40 36  1  4 27 14 39 11 28 12  9 24 19 33  8 42 22  2 30 38 21 34 15 29  7 35  6 37 13 41 18 
40 28 17 16 39 25 37 41 22 15 30  8 42 20 11 19 35 26 10 29  7  5 13 18 21  6 36 32 12 24 27  4 33 23  9  3 38  2 31 14  1 34 
25 37  1 29  7 28  9 19 26 22 13 41 21  2  6 39 12  3 16 27 17 42 14 36 18 15 30  4 11 20 35  8 24 32 10 34 40 31 33 38  5 23 
37 34 18 33 35 38 27 23 41  8 28 10 39 40 31  5 11  1 30  9 24 29  3  7 25 32  6 16 26 13 14 19 42 17  2 15 20 36 12  4 22 21 
15  3 37 35 38 21 32 42 36 34 16 18 30 33 19 41 20  5 27 25 13  7 28  1  2 11 24 14  6 17  8 10 40 22 39 12  4  9 23 29 26 31 
10 35 13  1 42  6 34 20  9  4  5 14 22 23 38 30  7 11 28 21 27 32  2 15  8 39 29 40 37 26 25 24 12 19 41 18  3 17 16 31 36 33 
23 33 39 20 25  9 40 34 30 35 15 42 37 14  3 18 21  2  8 12 36  4 17  5 26 31 10  6 13  1 24 16 22 41 38 11 27 28 19  7 29 32 
12 27 16 39 30  4 18 15 14 20 35  1 40  8  9 23 38 36 41  2 34 11 19  6 29 17 22 10 25 37 13 28 31 33  5 42 26  7 32 21 24  3 
24  9 38 42 41 34 21 36 18 25  8 16  1 12 10 17 27 37 19 32 20 26 33 13 30  4 28 15 29 39  7 31  5  3 35 23  6 22 14 11 40  2 
22 39 19 13  9 23 11  7 20 28 10  5 18 36 41 14 40 27 15 16 38  6 31 34  3  2 17 37 35 33 30 12 29 42 25  4 24 32 21  1  8 26 
 9 40 27 36 10 20  4  1 42 14  2 13  5 41 37  8 15 18 25  7 19 23  6 35 32 29 26  3 22 12 33 30 28 21 16 31 34 11 17 24 38 39 
 3 42 25 24  8  5 17 22  1 13 14 36 20 35  2 31 26 29 37 33 18 34 11 30 15 40 19 27  7 10 28 32  9 16  4  6 23 12 38 39 21 41 
20 16 29  9  1  2 15  5 31 18 19 37 35 26 32 24  6 30  4 42 22 28 23  3 12 13 25 39 36 34 41 14 10 38 40 21 11 27  7  8 33 17 
17 32 28 41  6 30  8 37 21 29 24 34 10 38 18 35 19 16 33 31 25 14 15 40  4  9 12 42 23  7  3  5 27 26 22  2 36  1 39 20 11 13 
11  4  5 22 16 15 12 25 40 33  1 39 31  7 23 42 36 10 29  6 14 27 30 38 28 37 13 26 34  9 32  3 35 20 21 41  2 24 18 17 19  8 
32  7 35  6 22 13 28 16 37 26 17  3 24 15 25 40 33  9 18  5 10 20 12  4 11 41 14 30  8 21 29 34 38  2 31 36  1 23 27 42 39 19 
34 18 22 21 32 14 39 26  7 38 12 24 27 10 36 13 29 15 17 30 33  1 41 37 42 25 20 11 19 23  4  2 16  6  8  5 31 40  3 28 35  9 
31 23 40 27  3 41 29 24 11 39 25 21 34 32 15 38 13  6 12 10  9 16 37  8 20 28  1 17  4 18  5 26  7 36 33 19 42 35  2 22 30 14 
38  8 33 19 15 10 23 12 32 42  7  2  6  4 14 36 17 31 35 18 37 39  1 29 16 22 21 13 24 25 34 27  3 11 20  9  5 41 30 26 28 40 
13 20 42  4 17 32  3 28 15  2 37 22 14 16 29 11  1 21 26 39  6 24  5 31 40 27 34 41  9 38 12  7 30 25 19  8 33 10 36 23 18 35 
27  2 30 37 31 22 35  8 19 36 41 12  4 34 39 29 16 23 38 13 28 40 21 24  6 26 15  7 20 42  9 17 25 10 18 14 32  5  1 33  3 11 
 1 17 24 32 20 36 10 31 29 37 22 28 23 11 27 34 41 33 42 38  4  3 40  2  5  7 39 35 15 19 26  9  6 13 14 30 21 18  8 25 16 12 
26 14 15 30 24 18 42 10  8  7 32 25  3 19 33  6 31 28 40 36  5 35  4 23 34 20  2 38 16 29 21  1 11 12 37 27 13 39 41  9 17 22 
35 38 41 23  4 39 26 13 28  3 18 20 19  6 16 32  2 12  5  8  1 37 22 27 10 34 40 33 17 31 42 29 21 30 11 25  7 14 24 15  9 36 
29 24  6  7 21 16 22 33 12 31 11 23 13 27  8 26 28 38 34 35 40 41 18 14 39 10 32  1  3  4 19 37 15  9 36 17 25 20  5 30  2 42 
36 12 31 14 18 29  5 40 10 27 39 30 17 24 21 22 37 13  6  3 15 38 32  9  7 23  8 28 42  2 16 11  1 35 34 33 19 26  4 41 25 20 
14 11  4 25 34  1  7 27  5 19  9 26 41 42 30 33 22 17 21 37  2 15 20 12 35 16 18 24 31  3 40 36 32 39 23 13 29  8 28  6 10 38 
 4 19 14  5 33 37  2 35 24 41 29 15  9 21 20 10 23 42 36 17 39 18 38 28 13 30 31 34 32  8 11  6 26  1 12 40 16 25 22  3 27  7 
 7  6 21 38 14 33 13 18  3 12 40 11  2 22 35 37  5 41 20  4 29 19 26 42 31 36 23 25 10 32 17 39  8 24 30 16 28 15  9 27 34  1 
21 13  2  8 12 27 19  3  6 11 34 35 25 31 42  9 32 40 24  1 16 36  7 39 37 18 41 20 30 22 10 38 23 28 17 26 14 33 29  5 15  4 
42 10 12 34  5 31  1 21 27  9 26  6 16 28 13  4  8 20  2 41 23 30 29 17 22 33 11 19 18 14 36 25 39 37  3 32 15 38 40 35  7 24 

Took 13.714977269s