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 The exercise is Exercise 12 on page 323:
Suppose we want to replicate a file over a collection of $n$ servers, labeled $S_1, S_2, \ldots, S_n$. To place a copy of the file at server $S_i$ results in a placement cost of $c_i$, for an integer $c_i > 0$. Now, if a user requests the file from server $S_i$, and no copy of the file is present at $S_i$, then the servers $S_{i+1}, S_{i+2}, S_{i+3} \ldots$ are searched in order until a copy of the file is finally found, say at server $S_j$, where $j > i$. This results in an access cost of $j − i$. (Note that the lower-indexed servers $S_{i−1}, S_{i−2}, \ldots$ are not consulted in this search.) The access cost is $0$ if $S_i$ holds a copy of the file. We will require that a copy of the file be placed at server $S_n$, so that all such searches will terminate, at the latest, at $S_n$. We’d like to place copies of the files at the servers so as to minimize the sum of placement and access costs. Formally, we say that a configuration is a choice, for each server $S_i$ with $i = 1, 2, \ldots, n − 1$, of whether to place a copy of the file at $S_i$ or not. (Recall that a copy is always placed at $S_n$.) The total cost of a configuration is the sum of all placement costs for servers with a copy of the file, plus the sum of all access costs associated with all $n$ servers. Give a polynomial-time algorithm to find a configuration of minimum total cost.
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 The exercise I randomly picked from the book is Exercise 8 on page 319:
The residents of the underground city of Zion defend themselves through a combination of kung fu, heavy artillery, and efficient algorithms. Recently they have become interested in automated methods that can help fend off attacks by swarms of robots.
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. :
