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 —
(require racket rackunit) (define test (list "abba[mnop]qrst" "abcd[bddb]xyyx" "aaaa[qwer]tyui" "ioxxoj[asdfgh]zxcvbn")) (define input-string (file->string "day07input.txt"))
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.
All of the slashes in regular expressions have to be escaped in Racket, which is why the code below has so many slashes.
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 —
In this case, non-hypernets uses the pattern \[[^\[\]]*\]|([^\[\]]*). The left side of the | in the pattern —
(define (includes-abba? str) (regexp-match? #px"(.)(?!\\1)(.)\\2\\1" str)) (define (hypernets str) (filter non-empty-string? (regexp-match* #px"(\\[(?:[^\\]]*)\\])" str))) (define (non-hypernets str) (let* ([segments (regexp-match* #px"\\[[^\\[\\]]*\\]|([^\\[\\]]*)" str #:match-select values)] [non-hyper-segments (filter (lambda(x) (and (second x) (non-empty-string? (second x)))) segments)]) (map second non-hyper-segments)))
I can now combine these functions to create a supports-tls? function that checks if a given IPv7 address meets the puzzle’s criteria.
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 —
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.
(define (aba->bab str) (let ([strchars (string->list str)]) (list->string (list (second strchars) (first strchars) (second strchars))))) (define (aba-bab-match? s1 s2) (string=? s1 (aba->bab s2))) (define (slice lst start end) (take (drop lst start) (- end start -1))) (define (aba-list strlist) (flatten (for/list ([str (in-list strlist)]) (let ([charlist (string->list str)]) (for/fold ([matches empty]) ([indx (in-range 2 (length charlist))]) (cond [(and (char=? (list-ref charlist indx) (list-ref charlist (- indx 2))) (not (char=? (list-ref charlist indx) (list-ref charlist (sub1 indx))))) (cons (list->string (slice charlist (- indx 2) indx)) matches)] [else matches]))))))
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 —
(define (supports-ssl? str) (define hypernet-bab-matches (aba-list (hypernets str))) (define nonhypernet-aba-matches (aba-list (non-hypernets str))) (ormap identity (for*/list ([nonhyper-aba (in-list nonhypernet-aba-matches)] [hyper-bab (in-list hypernet-bab-matches)]) (aba-bab-match? nonhyper-aba hyper-bab)))) (define (q2 multiline-str) (count identity (map supports-ssl? (string-split multiline-str "\n"))))
(define q2-test (list "aba[bab]xyz" "xyx[xyx]xyx" "aaa[kek]eke" "zazbz[bzb]cdb" "zazbz[dfs]cdb[dsbzb]aa" "abd[dfkgkpopos]abz[opopegkge]rrrsa" "abd[dfkgkpopos]abz[opopegkge]rrrsapop" "abd[dfkgkpopos]abz[opopegkge]rrrsapogp[ugfdtbiigi]gkgssusi")) (module+ test (check-equal? (q1 input-string) 110) (check-equal? (map supports-ssl? q2-test) '(#t #f #t #t #t #f #t #t)) (check-equal? (q2 input-string) 242))