Dutch / Nederlands

# 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:

This text is displayed if your browser does not support HTML5 Canvas.

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.

This text is displayed if your browser does not support HTML5 Canvas.
(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:

This text is displayed if your browser does not support HTML5 Canvas.

## 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 text is displayed if your browser does not support HTML5 Canvas.

Home | April 2013 | June 2013 | Random memories
```

```