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
|
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.
Wifi trackin
The city of Enschede is using the services of the Dutch company
City Traffic to measure footfall
in city center. The company claims 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.
See also: WTR a.k.a.
Sekfi: A proof of concept to monitor movement of crowds by analysing 2.4Ghz
Wifi devices over time.
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.
Go on 13×13
Some weeks ago, I met some go-player, who happens to have his lunch at the
same place as I. We have decided to play a game of go
during lunch time on a 13×13 board. This lunch was the second time we
played and explained the game to others around us.
Books
At 17:47, I bought the following two books from thrift store Het Goed:
- The Netherlands: A Guide to Recent Architecture written by Kathy
Battista and Florian Migsch, in English and published by Ellipsis London
Limited in 1998, ISBN:9783829004756, for € 3.60.
- JPod written by
Douglas
Coupland in English and published by Bloomsbury Publishing Plc in 2007,
ISBN:9780747589150, for € 1.80.
I got a reply to my inquiry to City Traffic about their method of processing
my MAC address. In the reply they state that they apply pseudonymization on the wifi-tracker and anonimization before it is
stored in the database. They did not explain the specific method that they
use for both methods. I do not see a reason why they would not publish their
pseudonymization method and provide for an API to send the pseudonymized MAC
adres for their opt-out register.
AKI open day
I attended the open day of AKI this morning. I
first had a look at the library where they were selling old books. Not any
catalogues. I talked with one of the teachers about the model drawing class
that he gives every week. Visitors were invited to do some model drawing
themselves. I also talked with a fourth year student about his work. I looked
in the various studios and workplaces. I bought a card with a drawing of a
bird by Nadie van Wijk for
€ 2.00. Near the entrance, I was invited to have my picture taken
with the Trip to the moon background together with two students.
This resulted in the picture shown
to the right. (I asked their permission to publish it here.)
Using git for file sync
It took me a long time to become a little confident with git after having used other version-control systems with a more friendly
interface. Recently, I discovered it is rather easy to push your commits to
a repository on an USB-memory stick and that such a repository can be used to
syncronize edits between different computers, without having to rely on an
external repository service, such as GitHub. Now I am just uses some directory synchronization tools for such
purposes. I am considering to also put all the data for this website in a
repository hosted on an external drive. The idea is to create a bare git
repository on the drive, with a command like:
git init --bare targetdir
Next you have to set the origin of your git repository and next you can push
it with commands like:
git remote add origin targetdir
git push
If you want to clone the repository in some other locations, you can simply
use a command like:
git clone targetdir
Overkill Festival: Day one
I went to opening of the Overkill Festival,
which is this weekend. I watched the modular synth performances by Archeface (recording on SoundCloud) and Jungle of Wires. I also tried some of the VR installations and a game:
Hana Hana Full
Bloom, False Mirror, Pastoral by Theo Triantafyllidis, The Lacuna Shifts, and VR Wizard: A magical training ground by
Power of Moo.
Overkill Festival: Day two
During the day, I helped as a volunteer at the expo with the VR installations
Hana Hana Full Bloom and False Mirror. Later, I looked around
and saw Camino Real by Fuckgamedev and Journey to Lavender Town. I also played a little with the modular
synthesizer in the synth area. At the start of the evening, I attended a VR
music performance by Sonotrope (which I did not find very interesting).
Has always been dystopia
I went to the opening of the exhibition
Has always been dystopia by Erica Ferrari at XPO.
This months interesting links
Home
| October 2019
| December 2019
| Random memories
Saturday, November 16, 2019