Recent content on Mailund on the Internet
It is not easy writing like Neil Gaiman, and I certainly cannot. There is a certain rhythm to his prose that you don’t fully notice until you read it aloud. He has a way of blending the magical and the mundane and the childish and the deeply serious and having it all make sense, although he rarely explains a thing.
So, I returned to looking at Scala. I wanted to implement two types of lists: a regular linked list and a lazy list (i.e., a list where you don’t evaluate the tail before you need it). Both are already available in Scala, but I’m solely doing this for educational purposes.
Following on my previous post I set out to implement the Knuth-Morris-Pratt algorithm. 
 This algorithm shifts the pattern p along x , exploiting the structure in p to skip positions we know cannot match. To do this, it uses a so-called border array that we need to pre-compute.
I’ll get back to playing with Scala soon, but since I don’t know which skills to brush up on, I also decided to play with a few other things. 
 I have taught string algorithms for over a decade, so I figured that using a few simple algorithms I know very well would be an interesting way to play with how the same goal can be achieved in different languages.
Soon, I will be unemployed — the needs of Kvantify and my interests and qualifications have diverged over the last year — so it is time to brush up on my skills, so I look interesting for potential future employer. Since I don’t know what a future employer will be looking for, this mainly means finding something I’m not familiar with but interested in and playing with it. Today, the choice fell on…
I’ve been working on an algorithm for suffix array construction today. It’s called prefix doubling , but I don’t have a link, sorry. I think it comes from this paper but I don’t have access to it at home.
Today, I want to talk about continuation-passing-style (CSP). This is a general approach you can use to translate recursions into tail-calls. 
 What’s tail-calls, I (imagine hearing) you ask? 
 A tail-call is when a function calls another function as the last thing it does. Tail-recursion is when that last call is a recursive call, but that is just a special case of tail-calls.
About those slices I mentioned yesterday , here’s what’s that about. 
 I’m working on some string algorithms and more straightforward C implementations than those I put in my book . 
 I implemented all the algorithms and data structures I use in my string algorithm class in Python and Go in the spring,^[I’m toying with the idea of writing string algorithms books for…
I’ve been working on a small C library for Python- or Go-like slices the last couple of weeks. Essentially arrays, but where I can index from the end using negative numbers (like in Python) and where I can extract a sub-slice, x[i:j] , in constant time (like in Go; I implement them the same way as Go does).
The other day I was reminded of an exercises we got first or second year when I studied computer science. It is a cool little trick, that I’ve never seen outside of that exercise, so I thought I’d share it.
During lockdown and on a dare, I wrote a piece of fiction (Krofatter Egon og hjælpepakken below). That was kinda fun, so I wrote a bit more, and I guess I am writing fiction now.
Hvis nogen imod al forvendtning skulle få lyst til at læse Krofatter Egon og hjælpepakken som en samlet pakke, så har jeg lavet en EPUB og PDF version som man ganske nemt kan hente ved at klikke på de links.
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 Afsked med Hammel 
 Det var midt på eftermiddagen næste dag, at Egon vågnede ved at det bankede på døren.
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 Opgøret 
 Da de stadigvæk var langt fra skovbrynet kunne Uffe og Egon gennem forrude se en stor søjle af røg stige op fra et sted inde i skoven.
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 Rådet kommer til undsætning 
 Egon løb imod bilen mens han vinkede med begge arme efter bedste evne.
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 En smugkro i skoven 
 Egon løb.
I am supervising some projects this spring, on algorithms for read-mapping. It’s different projects that all involve implementing a working, but primitive, read mapper. 
 There is nothing new there, I have a class every year where we do that, but now it is individual projects. The content doesn’t change much; just the teaching format.
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 Bagbundet i bagagerummet 
 Æter? Hvem helvede render rundt med æter disse dage?
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 Hammels hemmelighed 
 Med Portner Jørgens nøgle i lommen stod Egon på fortovet på den anden side af vejen fra Hammel Neurocenter. Det var blevet mørkt igen—hvilket ikke siger meget i den danske vinter—og sneen faldt omkring ham.
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 Rottefængeren fra Hammel 
 “Det er den forkert type dyr” påpegede Egon. “Katte og rotter er slet ikke det samme. De ligner hinanden lidt, med en snude, fire ben, og en hale, men ellers har de ikke meget tilfældes.”
This is an attempt at another of Neil Gaiman’s exercises : write about a fairy tale character in a therapy session. 
 It is not particularly exciting because I didn’t have any story in mind, just the scene, but at least it is an attempt.
My birthday is coming up, and since I cannot do anything interesting during lockdown, I got myself a subscription to MasterClass to look at some writing classes. 
 I have written a lot over the years. More than a hundred articles and 15 textbooks , but until I started this story as a bet, I had never written fiction.
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 En stor kattepine 
 Portner Jørgens kat var løbet bort, og da portnere ikke er meget for at forlade deres bygninger, så ville han se det som en stor tjeneste—stor nok til at låne en nøgle ud—hvis Egon ville finde den og bringe den tilbage.
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 Portner Jørgen 
 Tidligt næste morgen blev Egon vækket af et voldsomt rabalder inde fra krostuen. Det lød som om nogen havde smidt en større mænge blandet metal på gulvet, og det var netop hvad Krofatter Flemming havde gjort.
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 Portner portalen 
 Egon var måske ikke den skarpeste kniv i skuffen, men selv for ham var det oplagt hvor Agnes var forsvundet hen. I sneen var der tydelige fodspor langs den første del af muren, og derefter forsvandt de ind i muren. Fodspor forsvinder…
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 Snigen i sneen 
 Det var blevet sent natten før. Og så var det blevet tidligt igen. Da de to krofætre havde sagt godnat, var det teknisk set en god morgen, for nattens sne var ophørt, og solen var netop kravlet over horisonten og oplyste det snedækkede…
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 Pitstop på Pøt Mølle 
 Næste morgen, lidt blårøjet, for der var røget mange øl ned over natten, kørte Egon nordpå mod Hammel. Det Hvide Lyn kæmpede med at komme op ad bakkerne, og han skulle da ud at skubbe et par gange, men da der ikke var noget bestemt…

 

 So, my C pointers book apparently has a cover now. Before you complain, I don’t write the titles (although I don’t disagree with the title for this book), nor the subtitles (where I do for this one). I don’t know what they mean by “modern approach to memory management”. It’s malloc() and free() and some tricks for that, like reference counting…
Is this not making any sense to you? You are not alone. If you don’t know what’s going on, or why I write in Danish, start here . 
 
 En ubehagelig opgave 
 Rådsmedlemmerne steg ud af deres respektive biler og begyndte at gå imod Østbjerg Kros hoveddør i afmålte skridt, der garanterede at de ville ankomme nøjagtigt fem minutter i syv, altså fem minutter før de skulle møde, og derfor…
This post will mostly be written in Danish, and there is a reason for that. 
 You see, at our weekly Call of Cthulhu game, I accidentally used the plural word for “innkeeper”. I did it in Danish, however, and as it turns out, there was a problem: there isn’t a plural form of innkeeper, krofatter, in Danish. I know, because we contacted Dansk Sprognævn, the organisation that tracks the Danish…
In between exams, I plan to learn Go in January. I have a book I plan to follow, but today I wanted to get started by just jumping into it, so I picked the Chinese Remainder Theorem we used for 2020’s Advent of Code Day 13 . There, I implemented it in Python (before I found out that it was already in SymPy). It is a simple numerical algorithm, so it should be easy to implement in Go. Or so I…
I wanted to get back to yesterday’s puzzle, and I have a little time before I need to run off… 

 The use of findall() I refer to in the tweet is this. You can split the input using a regular expression, and then map each input code to a direction. If you combine that with a reduce() you get a very succinct parser:
On the last day of Christmas AoC gave to me an encryption problem, that is really a modular arithmetic problem. 
 If you decode the description—that is more cryptic than the mathematics—you find that we need to find secret keys by solving equations
Unexpectedly, I was allowed to play today—it is Christmas, after all—as long as I didn’t spend too much time at the computer. So I hurried up and solved today’s and yesterday’s puzzles quickly.
This will be the last post I write before New Year. We have vacation in the house from tomorrow, and I won’t be hacking when I am supposed to be social—I am told. I will do the last three puzzles, and post them, after the holiday.
Day 20: Jurassic Jigsaw 
 Day 20 we get tiles for a puzzle, and we have to work out the puzzle from them. The tiles can be rotated or flipped, but we can connect them by identifying how edges match.
I will make this one quick, because I don’t have much time. Today, we are given some rules for what strings should look like, and we are to validate a set of strings and count how many are valid. This is a bit of a mix between the parser from yesterday and the rule-validation from other days, but leaning, by far, towards the parser. The rules are a grammar, and checking the strings means we are…
Well, today, my blogging catches up with my Advent of Code hacking. Just in time to fall behind again in the weekend. If that happens, I should be able to write up my weekend solutions on Monday. I don’t think I have that much work waiting for me then.
My posts are almost catching up to Advent of Code , which probably means that I will fall behind in the weekend. Quite likely, actually. I probably have time for solving the puzzles, but not writing about them. If that happens—and if I were a better man, it is how I would bet—then I will make sure to catch up Monday.
I don’t have a lot of time today, so I will only describe the solutions for two days. I promise that I will catch up to the day the puzzles are released, but it probably won’t be until after the weekend…
Another day, another post with solutions to 2020 Advent of Code . I am slowly catching up with the actual puzzles, and I will probably get there soon. After that, there will probably be one day per post, except that I expect that the 24th and 25th will be something I leave for after Christmas. I’m not sure I will be allowed to sit and write over Christmas. We will see.
Ok, now that today’s puzzles are solved, I can go back and look at solutions to the previous days. Today, I will show you my solutions for days six through eight. There is some fun stuff in these days, with graph algorithms, memorisation, and virtual machines, the latter which I found particularly fun to play with.
While I wait for comments on the last chapters of my upcoming C-pointers book, I have some time on my hands. And since corona keeps me at home, I have to find something to keep me entertained. So I thought I would write a little about the Advent of Code puzzles I’m solving this year, and how I am solving them.
I’m writing the chapter on function pointers in my C pointers book, and I want a nice example of how you can use them to implement rudimentary object-oriented programming with dynamic dispatch.
I was playing with reference counting garbage collection last week, for something I want to add to my C pointers book. That chapter is still far in the future, and moving further into the future as the book seems to grow in front of me, but one day I will get to it. And by then, I have to have figured out some design issues that I ran into.
I forgot to post about it when The Joys of Hashing came out, but it is never too late to blow my own horn. It is out and you should get it.
Now that I am almost done with The Joys of Hashing , I am looking at the material I made last year for our Genome-scale Algorithms class . I implemented a toy read mapper as an example for the final project. I wrote several different approaches to mapping, from generating all strings at a certain edit distance to a read and doing exact matching to branch-and-bound using BWT.

 I was a little disappointed about this. I had hoped it would give a good overview of Scipy , but instead, it is a bunch of examples that use it. It is not that the examples aren’t interesting. They are. They just drown out features of Scipy , so I didn’t learn much about that.
The purpose of the lazy lists I implemented in my previous post was to build lazy queues. Lazy lists give you constant time concatenation, which can be useful in itself, but I needed it to implement persistent functional queues.
I wanted to write about lazy lists and lazy queues today, but I spent most of the day struggling with getting lazy evaluation to work. Finally, I convinced myself that something was broken in R, and I was justified in thinking that; upgrading to the most recent version resolved the issue.