Diary, May 2013

Sun Mon Tue Wed Thu Fri Sat
              1   2   3   4
  5   6   7   8   9  10  11
 12  13  14  15  16  17  18
 19  20  21  22  23  24  25
 26  27  28  29  30  31

Sunday, May 5, 2013

Diagonal mazes: more statistics

In the past week, I used two programs to get more statistics with respect to the chance for infinite paths in diagonal mazes. The first program calculated the number of paths with various lengths in a ten thousand by ten tousand square tiled infinitely in all directions. The results are presented in a table below. The first column contains consequtive powers of two. The second column has the number of paths with a length of given power (times two) or shorter. The third column contains the difference between the numbers in the second column. The fourth column has the factor between the numbers in the third column. The last column contains the extrapolation based on the previous columns, assuming that the values in the third column were going to develop according to the factor in the fourth column.

     1:  12.500048
     2:  18.750062   6.250013
     4:  25.170949   6.420888   1.027340
     8:  31.693743   6.522794   1.015871
    16:  37.909443   6.215700   0.952920 163.717658
    32:  43.669983   5.760540   0.926773 116.575916
    64:  48.941909   5.271926   0.915179 105.823609
   128:  53.739774   4.797865   0.910078 102.297909
   256:  58.094627   4.354853   0.907665 100.903254
   512:  62.042770   3.948143   0.906608 100.369371
  1024:  65.620563   3.577793   0.906196 100.184122
  2048:  68.862056   3.241493   0.906003 100.105789
  4096:  71.797179   2.935123   0.905485  99.916672
  8192:  74.455626   2.658447   0.905736  99.999355
 16384:  76.863716   2.408090   0.905826 100.026223
 32768:  79.045333   2.181617   0.905953 100.060856
 65536:  81.019926   1.974593   0.905105  99.853568

The second program calculates squares of size thousand and then glues these together into a larger square. The program counts all the closed loops into this larger square, all the open loops that start from the edge, and the number of loops when the larger square would tile infinitely in all directions. Below the results for the larger square of size 2,392,000.

closed loops
           1:  12.493719  12.493719
           2:  18.743736   6.250017   0.500253  25.000074
           4:  25.164570   6.420834   1.027331
           8:  31.687396   6.522826   1.015885
          16:  37.903001   6.215604   0.952900 163.654905
          32:  43.663582   5.760582   0.926793 116.592477
          64:  48.935576   5.271994   0.915184 105.821788
         128:  53.732895   4.797319   0.909963 102.217151
         256:  58.087519   4.354624   0.907720 100.922381
         512:  62.035303   3.947784   0.906573 100.342748
        1024:  65.612240   3.576937   0.906062 100.112939
        2048:  68.852944   3.240704   0.906000 100.087675
        4096:  71.787913   2.934969   0.905658  99.962758
        8192:  74.446751   2.658838   0.905917 100.048465
       16384:  76.855399   2.408648   0.905902 100.044104
       32768:  79.036567   2.181169   0.905557  99.950543
       65536:  81.011179   1.974612   0.905300  99.887785
      131072:  82.798137   1.786958   0.904967  99.814658
      262144:  84.412389   1.614252   0.903352  99.500573
      524288:  85.869983   1.457593   0.902953  99.431783
     1048576:  87.195275   1.325293   0.909234 100.471130
     2097152:  88.389223   1.193947   0.900893  99.242344
     4194304:  89.478741   1.089518   0.912534 100.845767
     8388608:  90.462942   0.984202   0.903337  99.660479
    16777216:  91.354342   0.891400   0.905708  99.916601
    33554432:  92.162496   0.808154   0.906612 100.008094
    67108864:  92.859149   0.696653   0.862030  97.211789
   134217728:  93.533627   0.674478   0.968170 114.049322
   268435456:  94.082341   0.548714   0.813539  96.476405
   536870912:  94.592299   0.509957   0.929368 101.302246
  1073741824:  95.112775   0.520476   1.020627
  2147483648:  95.357816   0.245041   0.470801  95.575816
  4294967296:  95.357816   0.000000   0.000000  95.357816
  8589934592:  95.534888   0.177072

open loops
           1:   0.000042
           2:   0.000042   0.000000
           4:   0.000081   0.000039
           8:   0.000133   0.000052   1.315765
          16:   0.000205   0.000072   1.402178
          32:   0.000304   0.000099   1.371537
          64:   0.000438   0.000133   1.344078
         128:   0.000617   0.000180   1.348334
         256:   0.000861   0.000244   1.355238
         512:   0.001188   0.000326   1.338883
        1024:   0.001625   0.000437   1.339179
        2048:   0.002213   0.000588   1.345623
        4096:   0.003003   0.000790   1.344026
        8192:   0.004066   0.001063   1.344681
       16384:   0.005509   0.001443   1.357898
       32768:   0.007415   0.001906   1.320786
       65536:   0.010008   0.002593   1.360525
      131072:   0.013572   0.003564   1.374276
      262144:   0.018348   0.004776   1.340206
      524288:   0.024735   0.006387   1.337181
     1048576:   0.033401   0.008666   1.356814
     2097152:   0.045087   0.011686   1.348511
     4194304:   0.060032   0.014945   1.278923
     8388608:   0.079870   0.019838   1.327387
    16777216:   0.107546   0.027676   1.395115
    33554432:   0.153510   0.045964   1.660766
    67108864:   0.201192   0.047681   1.037357
   134217728:   0.269990   0.068798   1.442885
   268435456:   0.355750   0.085760   1.246539
   536870912:   0.452635   0.096885   1.129728
  1073741824:   0.597440   0.144805   1.494598
  2147483648:   0.781714   0.184274   1.272567
  4294967296:   1.153069   0.371356   2.015240
  8589934592:   1.385508   0.232438   0.625918
 17179869184:   2.017776   0.632269   2.720159
 34359738368:   2.844043   0.826267   1.306828
 68719476736:   4.458862   1.614819   1.954355

tiles
           1:  12.493730  12.493730
           2:  18.743757   6.250027   0.500253  25.000116
           4:  25.164607   6.420850   1.027331
           8:  31.687457   6.522850   1.015886
          16:  37.903095   6.215639   0.952902 163.660648
          32:  43.663725   5.760630   0.926796 116.596031
          64:  48.935785   5.272060   0.915188 105.825537
         128:  53.733195   4.797410   0.909969 102.221851
         256:  58.087941   4.354746   0.907729 100.928208
         512:  62.035889   3.947948   0.906585 100.350432
        1024:  65.613054   3.577165   0.906082 100.124076
        2048:  68.854062   3.241009   0.906027 100.101847
        4096:  71.789431   2.935368   0.905696  99.980717
        8192:  74.448820   2.659389   0.905981 100.075166
       16384:  76.858192   2.409373   0.905987 100.076992
       32768:  79.040359   2.182166   0.905699  99.998619
       65536:  81.016282   1.975923   0.905487  99.946752
      131072:  82.805034   1.788752   0.905274  99.899664
      262144:  84.421823   1.616789   0.903865  99.622882
      524288:  85.883016   1.461193   0.903762  99.604916
     1048576:  87.212994   1.329977   0.910200 100.693450
     2097152:  88.413218   1.200225   0.902440  99.515405
     4194304:  89.509560   1.096342   0.913447 101.080002
     8388608:  90.506534   0.996974   0.909364 100.509278
    16777216:  91.413404   0.906870   0.909623 100.540794
    33554432:  92.238358   0.824953   0.909671 100.546177
    67108864:  92.958148   0.719790   0.872522  97.884741
   134217728:  93.678066   0.719919   1.000179
   268435456:  94.288153   0.610086   0.847438  97.676997
   536870912:  94.874533   0.586380   0.961143 109.378884
  1073741824:  95.496884   0.622352   1.061345
  2147483648:  95.965885   0.469001   0.753595  97.400257
  4294967296:  95.965885   0.000000   0.000000  95.965885
  8589934592:  96.402051   0.436165
 17179869184:  96.935889   0.533838   1.223936
 34359738368:  96.935889   0.000000   0.000000  96.935889
 68719476736:  96.935889   0.000000
137438953472:  99.993750   3.057861

Of course it is not possible to make any definite statements based on these statistics, I think it is safe to conclude that the number of infinite paths is low, below 5% and possibly even much lower. It is not unlikely that the chance of hitting a infinite path approaches zero. It is not difficult to create a tiled infinite diagonal maze with infinite paths, but that still could mean that they are very rare in a fully random infinite maze.

Tuesday, May 7, 2013

Diagonal mazes: percolation theory

When I posted some questions with respect to mathematical properties of diagonal mazes, someone mentioned percolation theory. I did some research into this, but I did not see a connection. Recently, I came across the column Percolation: Slipping through the Cracks. The page talks about square lattices. It is also the dual of a square lattice. I noticed that a square lattice and its dual are similar to diagonal mazes rotated by 45 degree. Every loop in a diagonal maze is between a cluster in the lattice and a cluster in the dual. For an infinite loop, it means that there needs to be a infinite cluster in the lattice and an infinite cluster in the dual that are touching eachother. In case of an unequal distribution there are either no infinite clusters in the lattice (when p < 0.5) or no infinite cluster in the dual (p > 0.5). But it also proven that the chance for an infinite cluster for an equal distribution (p = 0.5) is approaching to zero. (According to A lower bound for the critical probability in a certain percolation process by T.E. Harris.) So, yes, there are infinite random diagonal mazes with infinite loops, but they are extremely rare. I guess this settles the issue.

Wednesday, May 8, 2013

Lens fine art

Today, I received the booklet Peter Struycken, Ad Dekkers, Jan Schoonhoven, Carel Visser about an exhibition at Lens Fine Art held in the fall of 1972. It contains information about two works by Peter Struycken.

Thursday, May 9, 2013

Book festival

I went to a book festival (Dutch: boekenfestijn) organized by "De Centrale Boekhandel". I stayed there for a little over four hours. One hour in the morning and the rest in the afternoon. At 11:13, I bought the following books:

The Art of Avatar: James Cameron's Epic Adventure by Lisa Fitzpatrick, ISBN:9780810982864, for € 4.50.
The Making of Avatar by Jody Duncan and Lisa Fitzpatrick, ISBN:9780810997066, for € 6.95.
Ultimate Mandarin Chinese: Beginner-intermediate, ISBN:9781400009732, including 8 CD's for €17.50.
Kama Sutura by Vatsyayana with commentary by Yashodara translated by Alain Daniélou into French and by Aleid C. Swierenga and Max E. Desorgher into Dutch, ISBN:9789069638683 for € 4.95.

And at 18:11, I bought (with € 1.50 discount):

Fermat's Last Theorem by Simon Singh, ISBN:9781841157917, for € 2.99.
Coders at Work: Reflections on the Craft of Programming by Peter Seibel, ISBN:9781430219488, for € 5.99.
Complete Latin, ISBN:9780071761758 for € 2.95.

Saturday, May 11, 2013

Rainbow

When I went outside at 18:25, I was not surprised to see a rainbow, because I already had seen it rain while the sun was also shining. I took a picture while standing in our back garden. When I biked away, I saw that it was a complete rainbow. At some place the second bow could be seen, but it was much weaker than the primary rainbow, in which multiple bands were visible. This is not really visible in the picture.

Wednesday, May 22, 2013

Fermat's Last Theorem

I finished reading the book Fermat's Last Theorem by Simon Singh, which I started reading on May 9, the day I bought it a book festival. This is definitely one of the better books about a mathematic subject that I have read. For me it might have had some more mathematics, or at least a good outline of the proof by Andrew Wiles. Some part read like a page turner, at some places the author gets a little side tracked, such as the famous story about Évariste Galois.

Chinese Wooden Puzzle

Last week, I was playing the Chinese Wooden Puzzle but had an hard time to proceed from this partial solution:

I decided to use the program I developed before, to see if there were any solutions. Here is the least connected solution found by the program:

All the 79 solutions (with only the solved part showing) found by the program are:

Then I got the idea for looking for all the solutions in eight by ten square. Below the collection of unique solutions (taken into account mirroring) is given. One would expect every unique solution to occur exact four times, but this is not the case. This could possibly hint at some error in the algorithm used, meaning that there could be more solutions.

(Remark: On November 18, 2015, an extra 3 solutions were found with a different algorithm.)

Friday, May 24, 2013

Winter coat

It has been extremely cold for the time of the year. The graph here on the right shows the temperature in Celsius at 10 cm above the ground at the closest official weather station for the last night. About six hours the temperature was below the freezing point of water (light blue area). I decided to put on my winter coat this morning.

Saturday, May 25, 2013

White, orange, green and black

Yesteday evening, I worked on the various programs with respect to Chinese Wooden Puzzle problems. First of all, I wrote the program gen_CWP.cpp to generate an input file for the program gen_dpfp.c. The program takes three arguments: a width, a height, and a string where each character select a piece to be used. The output of the program gen_dpfp.c when called with the -n switch is suitable for the the program CWP.cpp, which can solve Chinese Wooden Puzzle problems. I modified the program to take three arguments: a width, a height, and a plurality. The plurality states how often each piece should be used. (Actually, this can be derived from the problem description, but I was too lazy to implement this.) I also modified the program SCWP.cpp to accept three arguments: a width, a height, and a string where each character represents a piece to be used. This program can process the output of the program CWP.cpp to find the most minimal representation taking into account mirroring using the given pieces. All the programs are implemented as pipe programs, receiving input on the stdin and producing output on stdout. I executed the following command to see if it is possible to fill a 8 by 10 rectangle with five instances of the white, orange, green and black pieces:

gen_CWP 8 10 wozg | gen_dpfp -n | CWP 8 10 5 | SCWP 8 10 wozg | sort -u

I had not expected that it would find any solution, but to my surprise it did find seven solutions, of two pairs are kind of similar, because all the green pieces are stacked in a column:

Monday, May 27, 2013

White, orange, red, and black or green

No solutions where found for trying to place five pieces of white, orange, red, and green from the Chinese Wooden Puzzle in an eight by ten frame, and only the following three solutions where found for pieces of white, orange, red, and black:

This months interesting links

Home | April 2013 | June 2013 | Random memories