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? 😄
JP's Blog
Large scale asynchronous DNS scans
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.
Extending Racket's DNS capabilities
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.
Extending Racket structs to bitfields
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).
Cyclic equality
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.
Splay heaps redux-imperative model
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.
Sorting via splay heap
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.
Bitvectors in Racket
A bit shorter on time today, so I’ve just got a quick library that I worked out to solve another problem (I’ll post it later this week when it’s actually working). Basically, when you need to store a heck of a lot of binary flags and don’t want to waste space, the best way to do it would be as one long list of bits. It’s really easy to do in a language like C, but how can you do it in Racket?
Memoization in Racket
Memoization is awesome!
I’ve already written one post on the subject in Python, but this time we’ll do the same in Racket. It’s particularly timely as without it, today’s post on determining the number of prime partitions of a number would take longer to run than I care to wait.
Dictionary tries in Racket
For the next few posts, we’re going to need a way to represent a dictionary. You could go with just a flat list containing all of the words in the dictionary, but the runtime doesn’t seem optimal. Instead, we want a data structure that lets you easily get all possible words that start with a given prefix. We want a trie.
