Progress

I'm isolating, which gives me some time to do things I had not scheduled, like cleaning up. Seeing all the stuff I've produced here and elsewhere, maybe I have to get ill more often!

Sometimes it's nice to try out things even if you might not want to finish themI mean, not like all my other side projects.. I played around a bit with Pelican, since I might want to add some more processing to this site at some point. Pictures, stuff like that. I don't think Pelican fits my ideas quite right, with its rather fixed structure, but there is some nice inspiration to be found there. Having played with it for a while, I'm this close to writing my own static site generator. It's not that much functionality, so it can't take that longHow hard could it be?.

I've now several times encountered situations where using a tool or a library is more effort than writing it yourself. These situations arise when the tool does not cover your use case exactly or needs a lot of configuration or plugins to do what you want it to do. This is the case for me and Pelican: I have some specific ideas that are not covered by Pelicans systems. At the same time, Pelican will automatically generate author pages, which I don't need and do not see how to configure away. Trying to make the tool conform to my needs might/will often take longer than writing a smaller one-off that does what I want.

Heron

So, I sat down on Saturday and wrote HeronA heron is related to, but not a pelican!. It's not entirely finished yet, and I definitely want to get RSS generation going before I do the switch. But, in all, it took me about 6 hours to get it working.

And then another four or so to port my old content. So now this blog is hosted on Heron. For the moment that doesn't change anything, except that I cleaned up my whole process and writing is now much easier for me. But I plan on adding a few features that will make my life much easier in the future.

It really wasn't that hard this time!

Data structures

I like data structures, always have. I have a notebook with exotic data structures that I can try in tricky situationsNot that there are many algorithmically tricky situations in my daily work.. There was a HN thread on data structures recently, so I took this opportunity to update my current list of interesting ones:

• Bloom filter: a classic. Here's a project that puts common passwords into a filter and warns users not to use them (actual project seems to be dead). This is great because the filter is small and does not contain any actual passwords.
  • Now I found also Golomb-coded sets, which are like bloom filters but smaller and slower. Would have been even better for the password-thing above. An implementation.
  • Cuckoo filter are quite similar, but have more operations than bloom filters and are slightly more space-efficient. Here's a great explanation by brilliant.This post, unfortunately, not sponsored by brilliant.org
  • And there are more: XOR filter is like bloom filter that is constructed at once, but is then smaller and faster. That would have been even better for the password thing!
  • And even better are Ribbon filters, giving us the same operations as bloom, but at smaller size and much more configurability. Amazing!
    • Here's an implementation of such a filter and its associated research paper
• Trie: A tree where items are not stored as leaf nodes but instead as paths in the tree. This by itself is a very powerful idea that turns some of the intuitions we have about trees on its head. In general, turning data-structures "sideways" yields some very surprising results.
  • Hash array mapped trie
• For example, in game-programming one often needs very fast computation on many identical objects. Instead of storing each object as a struct, games sometimes turn to tables of attributes instead of full objects. That is, instead of storing all attributes of an object next to each other, you store all identical attributes for all objects next to each other. This essentially "transposes" typical OO storage and allows fast processing of single attributes for all objects. This is more of a technique instead of a data structure, and I'll have to write more about this in a full article.
  • also called "struct of arrays" or "columnar databases" or "table-based structs".
  • Sometimes called "Entity-component system", however that word has so many meanings it's practically useless.
• Splay tree: A splay tree is also more of an idea than an actual data structure. The structure is identical to a regular unbalanced binary tree, but on each element access you rotate the accessed element into the root. This makes each access slower, but subsequent accesses faster. Interestingly, this automatically balances the tree in such a way that the most-used elements are also the ones to retrieve the fastest.
• Universal hashing: I need to look this up again, I think I mis-remember the actual word.
• Van-Emde-Boas-Tree: It's like a hash-map but as a tree. So if you need good worst-case performance, O(log n) instead of O(n), this is for you.
• Skip list: such a simple probabilistic data structure gives you access properties like a tree, without sacrificing the list properties. I love it.
• Spatial data structures
  • Quadtree/Octree
  • Binary space partition: Even though this seems to be somewhat forgotten, I assume that it's much better-suited for clustered data than a quadtree would be. The original Doom engine runs on BSPs.
  • k-d tree: well, that's actually BSPs but better.
  • Spatial hashing
  • Quadkeys: kind-of a combination of quadtrees and spatial hashing
  • Bounding volume hierarchy
• CRDTs: conflict-free replicated data types. These are a class of data types that can be replicated and edited concurrently without conflicts. They do this by converging towards a common state, no matter the operations that are performed on them. They're quite young and not well-enough developed to be in widespread use. Applications like Google Docs, where many users do concurrent editing, are trivial with CRDTs, because that's exactly what they do.

There are just so many great algorithms and data structures, so this list is far from exhaustive. In fact, here's a list of many, many more interesting topics one could look at.

Articles

• Building a Vector Map from Scratch -- Craig Kochis
• Nocturnal bottleneck - Wikipedia
• GitHub - tlalexander/large_format_laser_cutter: A laser cutter designed for cutting fabric. Because it is so large, it can hide under your rug when not in use.
• Learn MYOG (make your own outdoor gear)
• BRL-CAD - Wikipedia
• API Tokens: A Tedious Survey · Fly Most API security schemes boil down to a token that accompanies API requests. The tokens are somehow associated with access rules. The API looks takes the request, extracts the token, finds the access rules, and decides how to proceed. Here's a list of 10 known token types.
• The laws of stupidity according to economist Carlo M. Cipolla — Quartz
• Gravity Probe B - Wikipedia

Libraries, programming, etc

• How SQLite helps you do ACID · Fly: This is about how SQLite does ACID internally, not how you do acid with SQLite.
• Mollie - Accept online payments today. very nice European payment provider

Books

Backlog

• Mickey7 by Edward Ashton

Games

• Death's Door: A wonderful little indie slasher. Not too long, not too short, just right. Gets really hard at the end. 9/10
• Sweet Transit: ah, Transport Tycoon but modern. I'm not sure how finished it is, there are some rough edges and the economy is super-easy to crash without recovery options, and once you're stuck in a deadlock it might be impossible to get back out, but I guess that'll change. I've played this for about 8 hours now, and I think I've hit an economic glitch where I cannot progress with my resources. And finally, building tracks close together leads to loads of unnecessary problems. So my recommendation here is to build as wide as is possible; trains are fast and can go far. 8/10
• Hot Wheels Unleashed: Just a bit of fun. 8.5/10
• Watch Dogs: Legion: What a weird experience. The graphics are good but not great, and there are glitches from time to time. I did get stuck several times, between people and jumps. It looks a bit dated, for some reason. The characters are, well, most of them are autogenerated, so they are very generic. But even the "named" characters are pretty forgettable; Sabine, the author lady, Mary Kelley, the Albion-bad-guy, none of them are very interesting. The story is just bullshit from beginning to end and you can see all the "plot-twists" coming from a mile away. They try to do very similar things to Cyberpunk, but entirely unmotivated. For example, at one point you have to choose whether you'll allow one of the villains to upload herself. But that concept has only been introduced five minutes before that, and as far as I can see, the choice has no bearing on the story at all and uploading is never mentioned again. Also, this villains only motivation is power, she even sacrifices her own mother for it. Totally unmotivated, too, of course. The other villain on the other hand, his motive is power. And the third villain, his motive is power. And the fourth villain, his motive is, you guessed it, power. All of them are so flat and unconvincing. Well, at least all the systems work, mostly, most of the time. The city is large and mostly believable. Of course, there are also entirely pointless minigames and naturally microtransactions. There's also a very weird Assassin's Creed crossover that doesn't fit into the gameworld at all. In summary, this game is what Cyberpunk 2077 would be if CP were a normal game made by a contemporary game company. 6/10
• Moonglow Bay: an absolutely wonderful village simulator, revolving around fishing. The graphics are kind-of weird but one gets used to it. The one bad thing about this game are the controls. They are so very obviously console-adapted and keyboard/mouse is really quite bad. Still, very nice atmosphere and I played this for a day straight. 9/10
• Project Hospital: very detailed hospital management sim. Not sure how much character it has. 8/10
• Sunshine Heavy Industries: A puzzle game about building space ships. You have to place all parts so they adhere to their restrictions (heat, fuel, visibility, armor etc) while also keeping space and cost in mind. I like it. 8.5/10

Backlog

• Boiling Steel (Fanatical VR bundle)
• Catch & Release (Fanatical VR bundle)
• BoomBox (Fanatical VR bundle)
• Hyperdash (Fanatical VR bundle)
• Warplanes: WW1 Fighters (Fanatical VR bundle)
• Star Shelter (from waitlist)
• Sunshine Heavy Industries (from waitlist)
• Contractors (Humble VR Bundle)
• Budget Cuts 2 (Humble VR Bundle)
• VTOL VR (Humble VR Bundle)
• Dragon Fist: VR Kung Fu (Humble VR Bundle)
• Into the Radius VR (Humble VR Bundle)
• Hard Bullets (Humble VR Bundle)
• Takelings House Party (Humble VR Bundle)
• Summertime Madness (Humble Collection)
• Once Upon A Crime In The West (Humble Collection)

Other media

• This Old Tony: BUILD: FILING VISE!
• VSauce: Is your red the same as my red?: I slightly disagree with some of the things in here. One thing is the Theory of Mind thing, where he says that apes don't have one. I disagree, since there are experiments that show that apes and monkeys do have a theory of mind, since they tend to hide things and feelings. What they lack IMHO is a Theory of Communication, ie. a way to grasp that your hidden mind state can be transferred to my mind state by communicating. The second thing I (slightly) disagree with is that all of our experiences are unique for each of us. If that were the case, we would have no predictive power over experiences for other people. However, if you like chocolate, here's ten things I'd recommend with it that you might like. Here's something that tastes similar. Here's a color that goes well with red, and here are some that clash. While not universal and not 100% true for everyone, these predictions and "qualities" of our perceptions indicate that our minds are similar enough that we can form an understanding of each others' perceptions well enough. I don't think we're quite as alone as the video or some philosophers make out, with empathy building a bridges over that gap. For an alien, all bets are off, naturally.
• A simple human task that's insanely hard for a robot - YouTube
• Simulating an Entire Car Engine (yes, it makes noise): "I didn't like the sound racing games make so I built this accurate physical simulation of a combustion engine that runs at 80.000 fps to accurately create engine sounds."