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.

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.

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