Advent of Clojure — Day 4

After Day 3, Day 4 brings us back to something short and easier…

— — Day 4: High-Entropy Passphrases — -

A new system policy has been put in place that requires all accounts to use a passphrase instead of simply a password. A passphrase consists of a series of words (lowercase letters) separated by spaces.

To ensure security, a valid passphrase must contain no duplicate words.

For example:

- aa bb cc dd ee is valid.
- aa bb cc dd aa is not valid - the word aa appears more than once.
- aa bb cc dd aaa is valid - aa and aaa count as different words.

The system’s full passphrase list is available as your puzzle input. How many passphrases are valid?

I put the input file into my resources directory as day4.dat. Each passphrase is a separate line, so we just need to find the file, read it, then split into lines by separating on newline characters. I usually bring in the clojure.string namespace with the alias str, and the split function needs a regular expression, which in this case need only contain the newline character:

(-> (resource “day4.dat”) slurp (str/split #"\n"))

The first part of this puzzle is straight forward: find the valid phrases, and count them. Following the principles of “Wishful thinking” (see Structure and Interpretation of Computer Programs from MIT: either the videos or the book), we can assume that we have a function called valid? that will do this. So the solution is just:

(count (filter valid? phrases))

The only trick is then writing the valid? function. The first step is converting the phrase into a sequence of words, which is done just like line splitting, only with a space instead:

(str/split phrase #” “)

At this point, we want to go through the line, comparing everything we see to the things we’ve already seen. That can be done by checking everything up to the current point, but that has a complexity of n², which is not what we want to do when there are much better options. Instead, we can remember everything in a data structure that will do the work for us: a set. This only inserts new words and ignores words that are already in the set. If the size of the resulting set is the same as the length of the sequence that filled the set, then everything is unique.

My result was 451, opening up part two:

For added security, yet another system policy has been put in place. Now, a valid passphrase must contain no two words that are anagrams of each other — that is, a passphrase is invalid if any word’s letters can be rearranged to form any other word in the passphrase.

For example:

- abcde fghij is a valid passphrase.
- abcde xyz ecdab is not valid - the letters from the third word can be rearranged to form the first word.
- a ab abc abd abf abj is a valid passphrase, because all letters need to be used when forming another word.
- iiii oiii ooii oooi oooo is valid.
- oiii ioii iioi iiio is not valid - any of these words can be rearranged to form any other word.

Under this new system policy, how many passphrases are valid?

This has an identical approach, but with a different valid? function. Now that function needs to detect anagrams.

It’s possible to check if a word is an anagram of another by going through the letters of the word, and marking off if each one appears in the other word, but there is a much easier way. Anagrams don’t care about the ordering of the letters, so we can just sort the letters of each word alphabetically, and then compare the results. After sorting, anagrams will identical to each other.

The sort function takes a sequence, and reorders it to a new sequence. If you don’t provide a function to order by (such as > or <), then it just uses natural ordering, which in the case of letters, means that it will be alphabetical. Clojure strings are already sequences, so the sort function can be applied to each word in the phrase using map:

And my answer was 223. The final file is at:

quoll/AoC2017

Next will be Day 5.