7 Day 7: IPv7 ?!

Read the description of today’s puzzle. Here is my input, a list of IPv7 (ha ha) addresses.

7.1 How many of the IP addresses support TLS?

In this puzzle we must imagine someone has implemented a new version of the IP addressing scheme, in which the address itself carries information about whether a particular protocol is accepted at that address. Sort of like saying that if your street address ends in an odd number you must speak fluent French. Seems like a pretty silly design, but I guess this is where I put on my best Billy Crystal voice as I say, I’ve seen worse.

I need to find and count all the IP addresses that contain a string of the pattern abba outside any square brackets (the so-called "non-hypernet" sections of the address), and none of those patterns within brackets (the "hypernet" sections). A string like "sojjodf" counts as containing an abba pattern (the "ojjo" part), but the string "sjjjjodf" does not — the middle two characters have to be different than the surrounding two.

This is the kind of problem regular expressions were designed for. It’s likely that some crazy person might have tried, maybe even succeeded, in writing one gigantic inscrutable regexp that does all the work correctly, but I did not choose this path. Instead (after, I admit, wandering down the single-regexp path longer than I should have) I sensibly broke the problem up into three bite-sized functions.

I wrote two functions to return lists of the hypernet and non-hypernet portions of a string. The hypernets function is the simplest of the two: it returns all matches to the pattern (\[(?:[^\]]*\]), which equates to “a [ followed by any number of characters that aren’t [, followed by a ].” That middle clause excluding a second [ is necessary to keep bracketed groups of characters separate when there’s more than one of them in the same string.

The non-hypernets function is a bit more complicated, but in general it’s just using the greatest regex trick ever, the NotThis|(GetThis) pattern. A regular expression built like this will "match" cases you don’t want as well as those you do, but you can throw away all the matches except those that have something in your capture group (the part inside the parentheses). See the link above for the complete story on why this works — essentially, such a pattern will match either the left side of the | or the right side but never both. And because a regexp parser always checks left to right, you can be sure that any match in which capture group (GetThis) received a value also did not match the NotThis portion of the pattern.

In this case, non-hypernets uses the pattern \[[^\[\]]*\]|([^\[\]]*). The left side of the | in the pattern — the part we don’t want — matches any group of text contained in brackets. The right side — the one with the () capture group — matches any string of non-bracket characters. Once it has the list of matches from this pattern, non-hypernets picks through and finds only the ones that resulted in non-empty values in the capture group.

I can now combine these functions to create a supports-tls? function that checks if a given IPv7 address meets the puzzle’s criteria.

7.2 How many of the IPs support SSL?

As we might have expected, it gets worse. IPv7 addresses have an even more complicated criteria for designating SSL support. If an address has an ABA pattern (e.g. "ryr") in the non-hypernets that also has a matching BAB pattern ("yry" to continue our example) inside the hypernets, then the machine at that address is said to support SSL. Brilliant.

I got very close to doing this test with regular expressions also. The thing that prevented it working was that the regex parser would match, say, "ryr" as an ABA pattern inside the string "sdryryax", but then fail to match the "yry" within the same string — that is, it wouldn’t give me all the possible matches within a string if some of them overlapped. This might be an issue with all regular expression parsers, or with just Racket’s implementation; I didn’t take time to figure out which. Instead I ditched regular expressions entirely for this part and did the job with straight-up code.

The aba->bab function returns the BAB equivalent of any string. The aba-bab-match? function compares two strings and returns #t if inverting the second one with aba->bab results in a match with the first.

Separate from those two functions, aba-list does the work of actually finding all possible ABA patterns within a list of strings, including the overlapping ones, by stepping over each string one character at a time.

The supports-ssl? function ties all this together, using for*/list to create a list of the #t or #f results of checking every ABA match in the non-hypernets against every match in the hypernets — then using ormap to see if at least one of those was valid.

7.3 Testing Day 7