I write, therefore I am
With this variation on a famous statement by the philosopher Descartes, I would like to express that the act of writing about what happens in my life is important to me.
Street Tiling - Wang TilesIn the past week, I made some improvements with respect to the program that I wrote to generate Steet Tiling patterns. The latest version of the program can find all solutions up to an area of thirty in less than a day. I tried to add some more checks in the recursive back-tracking function, but it seemed that I hit some wall and that many simply made it slower. With each additional test to avoid parts of the search tree that are not going to find results, you also add some time to the execution of the function, adding a constant time to the total execution time. If a certain test is only effective in a rather small number of cases, this can lead to an increase in the total execution time. I thought about the idea to use Want tiles for the most restrictive case. I tried several coding methods. I came up with the idea to use the letters A to I to mark the unit squares of the tiles in the following manner:
A AB A AB ABC D DE DEF AB ABC DE DEF GH GHI
If you look at all the ways these can be layed on a square grid, than the following 86 patterns can occur on the squares made up of two by two unit squares:
AA AA AA AA AB AB AB AB AB AB AD AD AD AG AG BA BA BA BA BC BC BC BD CD DA DD AA AB BA BC CA DE AB DA DG AB DA AD CD EA ED AA AB BA BC BC BD BD BD BG BG CA CA CD CD CG DA DA DA DA DA DD DE DE DE DE CA EF AB EA EG AB EA FA FD FA FG FA AB BD CD GA GD GA AA AB BA BC DE DE DG DG EA EA EA EA EA ED EF EF EF EF EF EG EG FA FA FA FA FA CA GH AB GA AB AD CD HA HD HA AA AB BA CA HI AB HA AB AD BD IA ID FD FG FG GH GH GH GH GH HA HA HA HD HI HI HI HI IA IA IA ID IA AB IA AA AB BA BC CA AB AD CD AB AA AB BA CA AB AD BD AB
These are not exactly Wang tiles, because Wang tiles are labled on their edges, not their corners. But there are 28 different combinations of letters that occur on the edges, thus we could create an equivalent of 86 Wang tiles with 28 different 'colours' for the edges. This is a rather large number, and I thus thought about a way to create Wang tiles with less 'colours'. If one makes Wang tiles around the points where four unit squares meet, and use letters to indicate properties about the edges, I came up with the following set of 76 Wang tiles using nine 'colours' (0 and the letters 'a' to 'h'), where the order in which the 'colours' are give are top, left, right, and bottom side. Note that for every wxyz there is also a xwzy.
0000 0ada 0ae0 0bda 0bf0 0cda 0cg0 0dga 0dh0 0ega 0fga 0fj0 a00e a0ad ab0b ac0b ad0b af0b b00f b0ad bab0 bb0c bbc0 bc0c bd0c bdb0 bec0 bf0c bgb0 bhc0 c0ad cdb0 cec0 cgb0 chc0 d0ag dab0 db0b dbc0 dc0b dd0b ddb0 dec0 df0b dg0b dh0b e0ag eb0c ec0c ed0c ef0c eg0c eh0c f0ag fdb0 fec0 fgb0 fhc0 gab0 gbc0 gd0b gdb0 gec0 gf0b gg0b gh0b hab0 hbc0 hd0c hdb0 hec0 hf0c hg0c hgb0 hh0c hhc0
I did search for algorithms or programs for analyzing Wang tiles, but I failed to find any. Last week, I came across a copy of the book Shadows of the Mind in which there is some reference to tiling the plane with copies from a set of polyominos.
Thursday, April 28, 2016
Hail and wet snowAround eight in the morning, we had was a clear blue sky, which made me doubt the weather report that we would get hail and (wet) snow. But around 10:50 there was hail. The sky cleared again. But then again noon there was hail and also wet snow. And two hours later, again hail, that even covered the ground for some time. The temperature has been rather low for this time of the year. It is about 25 years ago, we had such low temperatures at the end of April. Last night the temperature drop to -0.7° Celsius. The highest temperature during the day, was just below seven degrees Celsius. The temperature graph below, clearly shows the drops in the temperature during the day that matched the periods of hail and wet snow. I read that some soccer was aborted due to snow on the field around here.
program, I make use of a simple single linked list to represent a mapping from keys to values. Sometimes, I even do not bother about the list being sorted or stored in the order the elements were added. Of course, there are containers available for this in the Standard Template Library and Boost, but these require me to import the whole library. This afternoon, I decided to implement a simple insert-only template for a program that I am working on. The template class InsertOnlyMap only has one method to find or insert a key to the map. The method will return a pointer to the value for this key, which might already have been present in the map or otherwise is added to it. Furhtermore, it defines an iterator that can be used to iterate over the values in the map. They key class should have a compare method, which return a integer representing the compare result. A negative value will indicate that the value is smaller than the one it is compared with and a positive value indicates that it is larger. The implementation is based on a binary tree that is being balanced on every insertion.
Saturday, April 23, 2016
HexagonsAn observation related to the Four colour theorem. Given two triangulations of a regular n-polygon. When these are placed inside a regular 2n-polygon such that vertices of this polygon alternatingly match with the vertices of the two n-polygons, then there can be found exactly n-2 'empty' hexagons in the pattern of lines of the triangulations of the polygons, where each hexagon consists of segments altenately taken from the two triangulations. The proof for this is rather simple. There must be a sequence of five vertices on the 2n-polygon, such that v1, v3 and v5 hava a triangle in one of the triangulations. There will also be a triangle attachted to vertices v2 and v4. The third vertice, vi of this triangle must be somewhere outside of the sequence. This is the only triangle that 'crosses' the first triangle, and also the other way around. The two 'crossing' triangles have a (irregular) hexagon with alternating segments from the two triangles. Now it is possible to construct two (n-1)-polygon with triangluations by removing the two triangles. Removing the first triangle is trivial because it is on the outside. To remove the second triangle, the edges v2 to vi and v4 to vi have to be merged. The various combinations for n equals six are shown on the top right using the colours red and blue for the two triangulations. The four hexagons are coloured white.
Street tiling patternsI calculated the number of Street tiling patterns for various restriction with latest version of the program to see if maybe some of the sequences are included in The On-Line Encyclopedia of Integer Sequences®. I did not discover any of them, which either means that they contain errors or that nobody ever looked at them. The sequences are given below, were each column gives the number of unique street tiling patterns with respect to rotation and mirroring with stated area. The first row gives all the sequences without restriction. This also contains sequences that repeat themselves, thus have the same appearance as a sequence with an area that is a fraction of the area. These are excluded in the second sequence. This sequence still do contain points where four tiles meet (indicated with 'x') and that contain H-shapes (indicated with 'H'), and where some of the vertices in the H-shape might actually have four edges instead of the three that the H-shape might suggest. The following sequences have additional restrictions on the occurences of the number of tiles that meet in a point and the occurence of H-shapes. The 's' signifies the additional restriction on the size of the tiles, restricting them to one by one, one by two, two by two, two by three, and three by three.
area 1,2,3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 -------------------------------------------------------------- all 1,4,6,24,25,98,93,386,520,1453,1749,8817,8398,30110,63789 xH 1,2,4,15,22,75,90,330,499,1375,1745,8507,8393,29825,63684 H 0,1,1, 5, 6,17,21, 59, 73, 172, 208, 633, 649, 1620, 2479 x 1,1,2, 5, 9,13,25, 39, 67, 114, 188, 401, 567, 1088, 1932 0,0,0, 1, 2, 3, 6, 9, 13, 24, 31, 59, 68, 126, 165 xH s 1,2,2, 9, 9,39,28,137,139, 447, 343,2163,1286, 5769, 8533 x s 1,1,1, 3, 4, 4, 8, 9, 17, 21, 28, 61, 63, 109, 156 H s 0,1,0, 2, 1, 4, 2, 9, 5, 14, 8, 40, 18, 49, 43 s 0,0,0, 1, 1, 0, 2, 1, 1, 2, 3, 6, 5, 5, 6
Friday, April 15, 2016
Thursday, April 14, 2016
BookAt 11:35, I bought the book The Molyneux Problem by Irene Kopelman edited by Moosje Goosen written in English published by Roma Publications on Wednesday, January 30, 2013, ISBN:9789077459881, from charity shop Het Goed for € 1.75.
Street tiling patternsThis weekend, I continued working on the program generating street tiling patterns. I have tried to eliminate double patterns, but it seems there are still some in it. Below patterns with area up to 18 unit squares can be viewed. These patterns do not have places where four tiles (possibly of different sizes) touch in a corner. Also the tiles are restricted to tiles of one by one, one by two, two by two, two by three, and three by three. Patterns which contain a H (possible rotated by 90 degrees) are also excluded, which reduces the number of patterns considerably. I also realized that some tiling patterns can be viewed as weave patterns. For this all tiles used should have at least one side with unit length one. And the one by one tiles should be assigned to either the horizontal or vertical ribbons. And each ribbon should have a ribbon in the other direction going under it. Preferable each colomn and row should have a ribbon. Under the patterns that are excluded below, there are valid weave patterns. area up to 20 unit squares can be viewed. These patterns do not have places where four tiles (possibly of different sizes) touch in a corner. Also the tiles are restricted to tiles of one by one, one by two, two by two, two by three, and three by three. Patterns which contain a H (possible rotated by 90 degrees) are also excluded, which reduces the number of patterns considerably. I also realized that some tiling patterns can be viewed as weave patterns. For this all tiles used should have at least one side with unit length one. And the one by one tiles should be assigned to either the horizontal or vertical ribbons. And each ribbon should have a ribbon in the other direction going under it. Preferable each colomn and row should have a ribbon. Under the patterns that are excluded below, there are valid weave patterns.
BookAt 17:40, I bought the book De Bosatlas van Amsterdam with Eelco Beukers as editor, ISBN:9789001120146, from V&D in Enschede for € 14.50.
BookAt 13:40:52, I bought the book Mijn generatie (in English: This Generation) by Han Han (韩寒), ISBN:9789029588423, from bookshop Broekhuis for € 5.00. Our magnolia now is full with flowers. I guess that about half of the flowers have opened. The first two flowers that opened last week have turned brown. The tree also spreads a strong fragrance in the garden.
AmsterdamI went by train to Amsterdam. Due to an accident, I was forced to take a detour through Zutphen, which incured a delay of half an hour, and forced me having to travel standing till Zutphen. I arived in Amsterdam around one o'clock. I took the free ferry to the former N.D.S.M. shipyard. There I visited two art galeries. First I went to Nieuw Dakota to see the Drawing Front. I liked a drawing by Eline Lutz. Next, I visited Francis Boeske Projects to see the Untitled, 2016 exhibition. There were large painting by Oscar van der Put using bright and low saturated colour, or in other words, almost white paintings.
I took the same ferry back to the central railway station and walked to bookshop Scheltema where they were having a sale. I walked through the whole shop and looked at hunderds of books. I bought only two books:
MagnoliaI found a pair of open flowers on our magnolia tree in the backgarden of our house. They met with some stormy weather and rain. The picture on the top right was taken slightly from above.
the TETEM art space. I first looked at the exhibition Sellfable City: Circuit Circus, but I was not very impressed. Next I looked at a part of the video Amerikan Teenager: Earthworm Jim by Sebastian Schlicher. Typical stream of consciousness, but rather clever. Next, I lookwd at the exhibition Drawing Front: Teach me a new language. I was impressed by the works Impulse I and Achy breaky heart by Henrik Kröner. Bernhard Willhelm for € 0.95 from charity shop Het Goed. The original price was € 9.50, but I on Cult Jones it is offered for sale for € 175.00. a rainbow if the hail would have been rain.
Sunday, March 27, 2016
Simple repository build on file sharing serviceI got some ideas about how to implement a simple repository on top of a file sharing service. Usually, I file sharing service only supports synchronization of files amongh locations, with the only guarantee that the files are shared without corruption. There is usually no mechanism to exclusively lock a file and most services are time-stamp based, meaning that the version of the file with the latest time-stamp overwrites earlier versions. This means that if two users at different locations save a new version of a file to a shared file location, the version with the latest time-stamp will overwrite the earlier changes applied by the user who saved with the earlier time-stamp. Usually cases of changes being overwritten are difficult to detect. One way to prevent data to be overwritten is taking sure that only new files are created. Because file sharing services usually also have no mechanism to 'claim' unique names for files, one needs to implement a scheme for generating unique files. One simple solution is to include a GUID in the name of the file. One could also use a hash function (such as SHA-1) over the contents of the file to generate a unique name, with the added bonus of defense against possible data corruption introduced by the file sharing service. To allow cooperation, we assume that the data representing the repository is stored in separate files and that social protocols are used to avoid people working on the same file. If the application has the added ability to merge two parallel versions, then there is no problem. (I argued before that merging is a complex process.) At least each file needs to have a reference to an earlier version, assuming there is one. Maybe it is beter to include the whole history of previous versions and in case the version is the result of a merge, to include both versions. We assume that each file contains a key-value store, and that the values can contain arbitrary complex structure with references to other keys. There are two type of such references, namely to keys in the file and keys stored in some other file. The second kind of references need to contain the name of the file. For efficiency reasons, it can be smart to have a table of files that are being referenced at the start of the file. They keys only need to be unique per version of the file. There also needs to be a mapping between the keys in the current version of the file and the earlier version. In case the key has not changed, it can be ommitted. In case the version is a merge between two versions, two keys may be needed, in case key-value pairs were merged. In case a file has references to another file and a new version of that file become available, then the version need to be updated with a process where the keys are replaced with keys to the new version. I described this form of 'updating' before. Note that in case there are two path along which the versions of a file can be reached (through nested references in files), it is possible that the file contains references to different versions of the key-value pairs. This is known as diamond problem. The application using such a repository needs to scan the available files on regular intervals, either controlled by the user of by some kind of timer mechanism, to discover newer versions of the files and to establish if the files are consistent. Each consistent combination of files, represents a state of the repository. Note that due to the implementation delay in the synchronisation, it is possible that states of the repository appear in different order in each location. Note that there is a cycle problem when two files contain references to each other, because each reference is always to a version of a file. In case a hash is used, there is no way to avoid it. To resolve this problem, each version of the file could also use a GUID at the start, which is used as the version identification for a version of a file. In that case it is possible to implement a procedure that writes files included in cycles, such that all references are to the latest version of the files.
Science and reportingIt is always interesting how science papers are reported in popular science. Today, I found the report Caught For The First Time: The Early Flash Of An Exploding Star, which shows a nice graph and a video animation. However, after looking at the graph, I read that Kepler makes a measurement every 30 minutes, while the graph seems to suggest that measurement was taken every minute. I searched the article to see if they had changed the measurement interval for this star, but could not find any. Next I found a link to the scientific paper Shock Breakout and Early Light Curves of Type II-P Supernovae Observed with Kepler. When I opened it, it affirms the fact that measurements were only taken every 30 minutes. Figure 4 focusses on the breakout event. One has to zoom in quite a bit to see the blue dots that represent the actual measurements. Not a stable line at all, but a lot of noise. Only when looking at the three and half hour average, one sees that the graph has a slight jump before it started to rise steadily. Here on the top right I have put the graph of the blue dots side by side with the 'nice' graph, from which I can only conclude that the 'nice' graph is just fabricated based on the assumption that the bump in graph shown in Figure 4 is actually the result of breakout event, which does seem likely. Furthermore, the video animation suggest another event, before the very bright flash, that is being suggested in the paper, but where the authors affirm there is no conclusive evidence. Although the supernova event of KSN2011d follows the predicted model, the supernova event at KSN2011a does not, because it rises more steap than expected. The authors give some suggestion how this can be explained.
Sunday, March 20, 2016
Trip to China 2010
-- contact -- Frans
My life as a hacker
The Art of Programming
HTML to LaTeX
eXtreme Programming Hamilton cycles