Skip to Content

Advent of Code 2017 - Day 4, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 4: 'High-Entropy Passphrases'

Posted on

Day 4 of Advent of Code 2017 is here! To be honest, I thought today’s challenge was a bit easy. There are a few ways to solve this problem, most of them amount to the same thing. I actually had a different solution than the one I’ll describe below, but they were essentially the same.

I’ve challenged myself to post each day’s solution to Github and blog about it. Like last year, I’m going to be solving these problems in Kotlin. I might go back and revise solutions, but I’ll be sure to annotate that fact in these posts.

Problem Input

We are given a set of input for this problem consisting of password phrases. I’ve parsed this into a List<String> called input that each of my solutions will depend on.

Day 4, Part 1

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?

This is very straight forward. Count the number of tokens in each passphrase and then count the number of distinct tokens.

fun solvePart1(): Int =
    input
        .map { it.split(WHITESPACE) }
        .count { it.size == it.toSet().size }

Well, we get to reuse our WHITESPACE regex we defined a few days ago, that’s good. And the rest more or less speaks for itself. I like this code because it’s super clear what’s going on, and it’s a single expression. You could even replace it.toString().size with it.distinct().size, but that ends up just being syntactic sugar and amounts to the same thing. A good argument could be made that distinct is clearer, but I feel the problem is so short it really doesn’t matter. I’ll leave it but keep distinct() in mind for the future.

Like stealing stars from a baby. Let’s move on before somebody catches us.

Day 4, Part 2

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?

You know what? I really wish the puzzle author wouldn’t give people ideas. You know somewhere, some InfoSec person at Ye Olde Local MegaCorp is writing up a policy document like this right now. Let’s distract ourselves from terrible thoughts with a hasty solution.

fun solvePart2(): Int =
    input
        .map { it.split(WHITESPACE).map { it.toCharArray().sorted().joinToString("") } }
        .count { it.size == it.toSet().size }

This problem is essentially the same as the first except we have to account for anagrams. A good trick to keep in your brain is to know how to handle these during coding problems because they come up again and again. The commonly accepted way to do this is to just sort the characters in the string and see if they match. Because dcba and bdac both sort to abcd, it’s easy to see that they are anagrams of one another. In every other respect this problem is the same as the first.

The code I have for sorting the characters in a String should probably be turned into an extension function, but I’m not sure I’ll need it again so I’m going to hold off for now. But it would look like this:

fun String.sorted(): String = this.toCharArray().sorted().joinToString("")

And if I’d used distinctBy(), I probably could have got this down to one line instead of the nested map. Next time.

At any rate: Trash start nausea, I mean: “that earns us a star”!

At the end of day 4, we’ve earned 2^3 stars with 42 left to go!

Further Reading

  1. Index of All Solutions - All solutions for 2017, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 4
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - What else? Anagram by Rush!