In this Haskell cicada we will read the recently published Functional Pearl Knuth-Morris-Pratt illustrated. We will use the same strategy we used in understanding the cycle finding function, namely slowly deconstructing the functions and playing with them in the ghci repl (we use the Haskell setup described here).
The first function we dissect is scanl used in the paper in what looks like a convoluted way to get all possible suffixes of a string.
Since the last Haskell cicada: Electromagnet Pulse was so much fun, let’s do another one from the same chapter from “Algorithm Design” by Jon Kleinberg and Éva Tardos.
Algorithm Design by Jon Kleinberg, Éva Tardos "Algorithm Design takes a fresh approach to the algorithms course, introducing algorithmic ideas through the real-world problems that motivate them. In a clear, direct style, Jon Kleinberg and Eva Tardos teach students to analyze and define problems for themselves, and from this to recognize which ... The exercise is Exercise 12 on page 323:
This Haskell cicada came about because sometimes, when I’m bored, I pick a random exercise from a random book and try to solve it. In this case the book was “Algorithm Design” by Jon Kleinberg and Éva Tardos.
Algorithm Design by Jon Kleinberg, Éva Tardos "Algorithm Design takes a fresh approach to the algorithms course, introducing algorithmic ideas through the real-world problems that motivate them. In a clear, direct style, Jon Kleinberg and Eva Tardos teach students to analyze and define problems for themselves, and from this to recognize which ... The exercise I randomly picked from the book is Exercise 8 on page 319:
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.
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.
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
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. :
