Weeknotes #88

Over Christmas, my father-in-law received a wooden puzzle we all failed to solve. The best attempts would always result in a single piece left over.

Determined to solve it, I thought of Chris’ programming language Sentient but struggled to represent the puzzle and its pieces in code. Research revealed the puzzle consists of polyominoes and is an example of the exact cover problem which is NP-complete.

Donald Knuth used an algorithm called “Algorithm X” to solve the exact cover problem and I found an online polyomino solver by Chase Meadors which let me quickly input the exact puzzle and generate a valid solution.

My use of machines to solve the problem was controversial but, as Tom put it:

It doesn’t really qualify as a puzzle in that sense does it [due to the NP-completeness]? It’s more like a game where you have to guess a number between one and a billion.

I’ve been attempting to design an API that prevents simultaneous updates of a resource from overwriting each other (“mid-air collisions”).

In researching the problem and existing solutions, Chris found “Detecting the Lost Update Problem Using Unreserved Checkout” by Henrik Nielsen and Daniel LaLiberte of the W3C 23 years ago.

The protocol interactions show how a combination of the ETag, If-None-Match and If-Match HTTP headers make it possible to implement optimistic concurrency control à la Redis’ WATCH and Consul’s KV store’s cas parameter.

I continue to listen to the songs from Bo Burnham’s “Inside” on repeat:

Here’s a tip for straining pasta, here’s a nine year old who died.

After finding the crisper drawer in our fridge full of water, I learnt that fridges have drains that get blocked. It also solved the mystery of the strange, flanged plastic wand left in the fridge door by the previous owners.

I’m now on my third attempt to fix our draughty front door having bought yet another sort of door seal.

I’m gradually approaching the point where it will have been cheaper to replace the whole door rather than keep on buying the wrong type of weatherproofing.