Here’s another one from /r/dailyprogrammer:
… Your goal is to color a map of these regions with two requirements: 1) make sure that each adjacent department do not share a color, so you can clearly distinguish each department, and 2) minimize these numbers of colors.
Essentially, graph coloring.
Here’s a quick problem from the DailyProgrammer subreddit. Basically, we want to calculate the radius of a graph:
radius(g) = \min\limits_{n_0 \in g} \max\limits_{n_1 \in g} d_g(n_0, n_1)
Another quick one, this time from /r/dailyprogrammer:
Your goal is to write a program that takes in a list of edge-node relationships, and print a directed adjacency matrix for it. Our convention will follow that rows point to columns. Follow the examples for clarification of this convention.
Yesterday’s challenge from Programming Praxis challenges us to rebuild a data structure near and dear to any Lisper’s/Schemer’s/Racketer’s1/functional programmer’s heart: lists. The idea presented in their sample solution uses two element vectors, directly mimicking the general internal structure of Scheme’s lists. How about we do something a bit stranger? 😄
On Monday we laid out a framework for converting structures into bytes. On Wednesday, we used that to enhance Racket’s UDP and DNS capabilities. Today, we’re going to take that all one step further and scan large portions of the Internet. The end goal will be to look for DNS-based on a worldwide scale.
As I mentioned on Monday, I wrote my DNS-based censorship around the world–and to do that, I need a fair bit of control over the DNS packets that I’m sending back and over parsing the ones that I get back.
Keen eyed observers may have noticed that last Friday when I posted about converting my various Racket libraries to Planet 2 packages, that there was a new package there I haven’t otherwise talked about: bit-struct. Today seems like a good time to talk about that. Theoretically, I’ll also have another post or two this week showing exactly what I’m doing with it (spoilers: it involves sending on the order of billions of DNS requests1).
In today’s post from Programming Praxis, the goal is to check if two cyclic lists are equal. So if you have the cycles ↻(1 2 3 4 5) and ↻(3 4 5 1 2), they’re equal. Likewise, ↻(1 2 2 1) and ↻(2 1 1 2) are equal. But ↻(1 2 3 4) and ↻(1 2 3 5) are not since they have different elements while ↻(1 1 1) and ↻(1 1 1 1) aren’t since they have different elements.
I did say in yesterday’s comments that I would try re-implementing splay heaps using an imperative model with an array (Scheme’s vector) as the back end rather than a functional one with trees. Well, here is is.
Yesterday’s post from Programming Praxis gives a new (or at least different) vantage point on one of the most common problems in Computer Science: sorting. Today, we’re going to implement a data structure known as a splay heap and use that to perform a heapsort.