Previous Up No next

Diary, November 2019

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

Sunday, November 3, 2019

Average distance

A property of a maze is the average distance between all the rooms, where the distances is defined as the number of passages on has to pass to arrive from one room to another room. To calculate it, you first have to calculate the (shortest) distance between all combinations of rooms, and than sum all those distances. To calculate all the distances, one could use the Floyd-Warshall algorithm, which requires a matrix of the size of the number of rooms. Because the distance is direction independent, the matrix is symmetric, and one only needs to store one half of the matrix. Still the memory consumption grows quadratic with the number of rooms. However, to calculate the average, one only needs to how often a certain distance occurs. As an alternative one could sequentially calculate the distances from each of the rooms using Dijkstra's algorithm. This would only require a memory storage linear equal to the number of rooms. If the maze is 'nice' in the sense that there is exactly one route between every two pair of rooms, one could use any recursive algorithm to visit the rooms starting from the first room. Once the distances are calculated from one room, one can count how often each distance occurs. These counts can easily be summed (using a storage equal to the number of rooms) for all the rooms. Note that each distance is counted twice, but for calculating the average distance this does not matter. This algorithm requires one to traverse the maze as many times as there are rooms. Last night, I came up with an algorithm for nice mazes that only require you to traverse the maze once, and which does not count the distances twice. While walking through the maze it keeps a list of distances from the rooms visited. When arriving in a new room, this list is used to update the global list of distances. If the room has only one passage not visited yet, the list is simply extended with room. This is done by adding the room to the front of the list and letting the position of in the list determine the distance. If there one more than one exit left that has not been visited, the current list is assigned to the room and an empty list is passed for the next step. After returning from that part of the tree, the list from there and the list kept at the room, can be used to calculate all the distances between the rooms counted by both list, and after this has been done, the two list can be added together for the remainder of the tree. (If there is still more than one passage not visited, the added list is again assigned to the room, otherwise it is passed to the next step.) This afternoon, I implemented the algorithm in the function _calcDistances in MazeGen.cpp, the maze generation program I have been developing.

Tuesday, November 5, 2019

Wifi trackin

The city of Enschede is using the services of the Dutch company City Traffic to measure footfall in city center. The company cleams that this is privacy proof. According to the Dutch GDPR laws, it is forbidden to track people using MAC addresses of their mobile phones. City Traffic defends themselves by stating that they are not storing MAC addresses but are anonymizing the addresses by applying a some hash function. They also have an opt-out register on their website. I wonder if they actually apply the same hash function to the MAC address entered there in the browser or that the MAC address is only hashed in their server. I would like to be opted-out, but not that they process my MAC adres any any form without my explicit permission. On the opt-out page, there is no mentioning of giving them the right to process the MAC address, which I think they should according to the Dutch GDPR laws. The fact that they do have an opt-out mechanism, seems to imply that they are not truely anonymizing the MAC addresses, but that they could still track my MAC address if someone would give it to them.

Saturday, November 9, 2019

Berlin Geisterbahn

Today, it is 30 years since the fall of the Berlin Wall. I went to visit Rijksmuseum Twenthe to see the exhibition Berlin Geisterbahn with pictures by Fons Brasser, which he took from ghost stations from the Berlin S-Bahn, the rapid transit railway system of Berlin. I studied the four maps, from different periods, of the S-Bahn that were on display, and tried to relate them. I took one of the information sheets, with a picture of the Schulzendorf station on the back, that had a map of all the S-Bahn stations during the period the pictures where taken in the first half of the eighties. All the ghost stations are marked with colours on this map.

This months interesting links

Home | October 2019