Intro # Posts like this one don’t age well. Tooling changes all the time. And the other thing is: I do Haskell just for fun, ie silly little exercises with only pure functions. So take this setup with a grain of salt. And if you stumbled on this from the future, there’s probably better options for you.
With these disclaimers out of the way, let’s see the setup.
Imagine a 6 by 6 grid of squares, that can either be black or white. It has to fulfill the following properties: 1. Each row and column needs to have 3 white and 3 black squares. 2. All black squares have to be orthogonally connected. Prove that such a grid cannot exist. part 1: naive brute force exhaustive search part 2: smarter exhaustive search part 3: inductive graphs part 4: connected magic squares part 5: experiments Note: in our digital representation black squares are ones and white squares are zeros.
Imagine a 6 by 6 grid of squares, that can either be black or white. It has to fulfill the following properties: 1. Each row and column needs to have 3 white and 3 black squares. 2. All black squares have to be orthogonally connected. Prove that such a grid cannot exist. part 1: naive brute force exhaustive search part 2: smarter exhaustive search part 3: inductive graphs part 4: connected magic squares part 5: experiments Note: in our digital representation black squares are ones and white squares are zeros.
Imagine a 6 by 6 grid of squares, that can either be black or white. It has to fulfill the following properties: 1. Each row and column needs to have 3 white and 3 black squares. 2. All black squares have to be orthogonally connected. Prove that such a grid cannot exist. part 1: naive brute force exhaustive search part 2: smarter exhaustive search part 3: inductive graphs part 4: connected magic squares part 5: experiments Note: in our digital representation black squares are ones and white squares are zeros.
Imagine a 6 by 6 grid of squares, that can either be black or white. It has to fulfill the following properties: 1. Each row and column needs to have 3 white and 3 black squares. 2. All black squares have to be orthogonally connected. Prove that such a grid cannot exist. part 1: naive brute force exhaustive search part 2: smarter exhaustive search part 3: inductive graphs part 4: connected magic squares part 5: experiments Note: in our digital representation black squares are ones and white squares are zeros.
part 1: naive brute force exhaustive search part 2: smarter exhaustive search part 3: inductive graphs part 4: connected magic squares part 5: experiments I found this problem on one of my Mastodon feeds:
Imagine a 6 by 6 grid of squares, that can either be black or white. It has to fulfill the following properties: 1. Each row and column needs to have 3 white and 3 black squares. 2. All black squares have to be orthogonally connected. Prove that such a grid cannot exist. Note: in our digital representation black squares are ones and white squares are zeros.
I recently needed a distraction for a ten-hour flight. I cannot sleep on flights and I’m also too uncomfortable to do any real work or read. So it has to be binging a show. I chose Deadloch, a murder mystery show with eight one hour episodes, making it the ideal length for a ten hour flight assuming it is compelling enough to stick around.
Transcription by Kate Atkinson A dramatic story of WWII espionage, betrayal, and loyalty, by the #1 bestselling author of Life After Life In 1940, eighteen-year old Juliet Armstrong is reluctantly recruited into the world of espionage. Sent to an obscure department of MI5 tasked with monitoring the comings and goings of British ... Kate Atkinson’s novel Transcription is the answer to the question of what happens if you take the wicked humor of Martin Amis, John Le Carre prose elegance and the emotional honesty of Iris Murdoch and blend them all together.
Introduction # People are familiar by now with the Mastodon account verification system: if you want to prove that you own both a particular Mastodon account and a particular website By owning I mean you hold the login credentials. , you add a link with the rel="me" attribute to your website pointing back to your Mastodon profile and in the Mastodon profile you add a link to your website page that contains that rel="me" anchor. The Mastodon instance will fetch that page, find the rel="me" anchor and reward you with a green checkmark next to your website link in your Mastodon profile. This is very simple and straightforward but it does imply a certain level of trust in the Mastodon instance doing the verification.
Introduction # One of the cool things about Mastodon, Notion and RSS is great API availability and nice Go libraries covering these APIs:
Jomei Notion Mattn Mastodon MMCDole RSS Feeds Pretty early after migrating to Mastodon, I started thinking about a little project that would use these APIs: a tool that automatically toots links to new blog posts appearing in an RSS feed. Obviously as with most things something like this already exists: mastofeed. But I wanted to put my own spin on it and play with the APIs. One afternoon of hacking later and I had mastosync.
When the Nova 11 announcement appeared in one of my feeds, it was clear I wouldn’t be able to resist. I love, love, love truly polished native Mac apps and Nova completely nails it in that category. I played with previous versions of Nova before but I never had a real use case for it. I’m not a web developer and adapting it to the programming environments I use is somewhat challenging so I always slide back to specialized IDEs for those (Goland for Go, CLion for C++, Visual Studio Code for Haskell and TeXShop for LaTeX). But now I have this blog and this is all Markdown, CSS, Html, Javascript, in other words a great use case for Nova.
Counting number of ways to color some objects under the action of a group.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
This Haskell cicada was a Google Codejam competition problem way back in 2012 Codejam Round 1B 2012: Safety in Numbers. No, I did not participate. I’m not very good and I’m also not very fast, two things needed in coding competitions. I do like these competitions as a source of problems to tackle. .
Problem # There are $n$ contestants in a reality TV show. Each contestant is assigned a point value by the judges and receives votes from the audience. The point value given by the judges and the audience’s votes are combined to form a final score for the contestant, in the following way:
This Haskell cicada is another small problem from long time ago.
Given a set of marbles of different colors, find the majority color knowing it exists.
Let $M$ be the set of marbles and $|M| = n$. We know that there is a color $c$ such that
$$ |\{ m \in M: color(m) = c \}| > \frac{n}{2} $$
We prove the following lemma:
Given $x, y \in M$ with $color(x) \neq color(y)$, then the majority color in $M$ is also the majority color in $M \setminus \{x, y\}$.
For this Haskell cicada I’m dusting off a small problem that I used long time ago to practice Scala:
Given is a list of people at a party and for each person the list of people they know at the party. We want to find the celebrities at the party. A celebrity is a person that everybody at the party knows but that only knows other celebrities. At least one celebrity is present at the party.
Enigma Machines and how the internal wiring of their rotors was reverse-engineered is the topic of this note.
I pieced this together from several sources, so it is a little convoluted but it mainly follows chapter 3.8 from the book Abstract Algebra by Lawrence and Zorzitto, albeit in a perhaps simplified, less rigorous way.
Rejewski and his team of code breakers did a lot more than what is described in this note. For example, they designed and prototyped electro-mechanical computers to take over some of the tedious manual labor that was still needed to sift through possible permutations. Later, at Bletchley Park, Alan Turing and his team scaled up those prototypes and made the Bombe.
Introduction # In this Haskell cicada we dissect a clever algorithm for finding a cycle in a sequence of values generated by a function from a finite set to itself. I used this algorithm in a math note without further explaining it or its Haskell implementation.
Before we dive in, let us set the stage. Given is a finite set $S$ and a function
A Spy Among Friends # I cannot really explain why I like the John Le Carre type of content so much. If I let myself indulge in armchair psychology, maybe what appeals to me is the heightened awareness of the facade of ourselves that spies must have. These fictional I have no idea how real spies function or if there is any resemblance between fictional and real. spies are forced to distrust every aspect of their interactions and relationships, have to build intricate webs of lies and dole out information and withhold information at crucial times. There’s always this cat and mouse game, who is hunting whom. Moles have to be discovered and turned. This all makes for great fiction. There’s also the witty dialog, the posh manners, the higher moral calling, the self doubt. John Le Carre was a master chef of all this spy brew, mixing it all together into an elegant story. I consumed all of it and haven’t found a worthy successor of him yet. Well, I’m here to say, if we’re allowed to change the medium from novel to TV series, “A spy among friends” comes really close. Combine the terrific writing with fantastic performances, a strong female lead, patience to let the story unfold in six one-hour episodes and trust in the viewer to follow along and you have a very satisfying spy show. I have only one, slight complaint: does everybody in the show really have to smoke so much ?
Today I’m making Apfelstrudel again. It is one of the few desserts I know how to make and my family likes it. I’m not making my own dough. That is way beyond my capabilities. For a sense of how skilled you have to be to pull off authentic strudel dough, watch this delightful documentary:
I’m instead using puff pastry from Whole Foods:
Every so often I get the urge to dive into Haskell programming. It doesn’t happen often and the periods in between the dives are long enough that I have to start from the beginning each time because I forgot everything I learned last time. It also never lasts that long either, the urge goes away right about when Monads appear. Maybe this urge is similar to the life cycle of cicadas, so I will call the little projects coming from this current urge “Haskell cicadas”. If enough material comes out, maybe I can collect it into a little booklet with a nice cover Most likely this current urge will fizzle out before enough material accumulates. I do like the cover though. It is an image from Bill Nino on Unsplash. :