Advent of Code 2017 in Kotlin: Days 1-3
2018-01-06
7 minutes read

I’m in the middle of learning Kotlin at the moment. I started exploring it on a whim over the 2017 holidays after talking with some freenode acquaintances about how it is being used at their places of work. After having used Scala and Groovy for a bit at previous workplaces, but never quite latching on for completely different reasons, I feel like Kotlin is worth a shot, if for no other reason than it was someone else’s take on just doing Java (the language) better.

I’ve breezed through the Kotlin Koans and am currently working my way through Kotlin in Action at present, but need to write some more actual code that does more than demonstrate language features. I figure a problem solving quest akin to Project Euler would be worth a shot. However, I have decided on doing the 2017 Advent of Code late this year instead to avoid the math heaviness of Project Euler.

The source for my code is at Github.

For the challenges, I’m going to do my best to stick to only the Java Standard API Kotlin’s additions to it unless there’s a really good library that really just makes sense to use. I’m also going to use Spek for writing tests. Though I primarily use TestNG in normal development, I’ve used a fair number of other test libraries that enable spec style test writing (ScalaTest and mocha, specifically) and I’d prefer to go with something with a bit more of a Kotlin flavor to it. Spek seems like a good idea for the purpose as it is clearly using the Kotlin builder pattern.

Day One - Part One

Problem link here

After reading the description of this, the first thing that comes to mind is to take the examples given on what the captcha does and write some spec tests based on that.

What I like about spec best testing frameworks is how non-awkward it is to loop through a set of known inputs and outputs. While I love TestNG, the @DataProvider mechanism for this is a bit clunky in comparison.

Anyway, I wrote the spec first and then came up with a solution that has the Kotlin’isms of using extension functions: map as defined on CharSequence and withIndex as defined on an Iterable. I wasn’t wild about the solution, but it works. There was another attempt to do this in a functional style with a fold instead of an explicit loop, and no var, but I think this version is even less clear to read and ultimately was less straightforward for me to write.

Day One - Part Two

Once part one was answered and part two was revealed, it appears that my attempt at using fold wasn’t going to be easily adaptable and I’d be better off introducing a stepping parameter the original imperative version. Here’s the modified function:

Here I’ve used local function, which is a feature I’ve loved in every language I’ve used that has it (basically, everything but Java). There’s nothing fancy going here, I just like the ability to name a block of code even if I only use it once because it adds to the readability of what is really happening. Also, for me the usage of a local function can often be a sign that, in order to be extensible, that local function can be popped out and accepted as a parameter to the function. I didn’t go that far with this example.

Day Two - Part One

As it turns out, using the fold method during Day One was good practice for Day Two’s problem, which was easily solvable with a fold on a List<Int> after converting each line of the input. The logic of this was pretty easily solvable, and I had a more difficult time with mapping the input String to a List<List<Int>> in a single line than I did with the actual fold method itself.

Day Two - Part Two

The modification of this problem to solve part two involves changing the behavior of how each line in the input gets converted to a single integral value. Ultimately, this means parameterizing the function we pass to the operation parameter of the fold call made on List<List<Int>>. Since we can pass around functions easily enough, this seems like a great chance to do so.

I added a second parameter to the checksum function that is responsible for mapping an integral value to each line. By default, this parameter, is the refactored function used in the fold in part one of this problem such that this solution can remain intact (and keep my specs passing). I define another function that finds all pairs of numbers, and returns the result of the division of the first pair that evenly divides.

I could have reduced the space complexity of the pair finding algorithm here by not creating a new List of all pairs when all I needed is the first pair found. However my thought process in writing this was “wait, where is combinations like I had in Scala!?“. I couldn’t find its equivalent in the standard library, but it was straightforward enough to define an ad-hoc one for exercise. As a result of writing this, I have a candidate of a function that can be refactored in to an extension function on any Collection.

Day Three - Part One

I took a bit of a week off from playing with Kotlin to focus more heavily on some work and life things going on. I squeezed in working on part one of day three during the middle of the week, but forgot to write about it.

Problem link here

My first thought when I encountered this was to write a data structure encapsulating a two dimensional grid, and given that it may grow in both directions, it would probably have looked like an prepend/append-only Deque<Deque<Int>>. Though I resisted that urge as there is a clear pattern in solving how far a number is away from the center based on what the next highest odd perfect square is and how far away that number is from said perfect square. If you consider the number 1 to be at point 0,0, then every odd perfect square form a diagonal from the center and extending down and to the right with a slope of -1. I thought I could accomplish this without writing any code attempting to populate a grid just to solve a problem and instead went with a simple algorithm that can be explained in psuedocode as follows:

  x = target number
  y = next highest odd perfect square from x, inclusive
  maxDistance = sqrt(y) - 1
  minDistance = max / 2
  f(x) = max - ((y - x) % maxDistance)
  answer = if f(x) >= min
    then maxDistance - f(x)
    else f(x)

Which I wrote in Kotlin code as follows:

I did not do much in the way of new Kotlin features here, as the main exercise was getting the algorithm right.

Day Three - Part Two

Part one took much longer to get correct than I thought and I probably would have solved it much more quickly by just brute forcing it by creating a grid. As it turns out, the twist in part two, in which the value of the next node in the spiral is derived by adding its neighboring nodes. Sounds like I could have used that grid after all…

After lamenting my earlier decision and noodling for a bit on a possible cute algorithm, I decided to just go ahead and brute force the grid creation. I didn’t however just jump right in to using a collection of collections to store the 2 grid and instead just stored all known points and their values in a Map<Point,Int> for easier lookup. As such, I wrote come code that started at the conceptual point of (0,0) and managed directional turns and took advantage of anonymous enum values in Kotlin. The solution is a bit icky and is not factored well, but again, solves the problem. Thankfully this is not project euler where I’d probably pay dearly in computational costs for writing code that doesn’t minimize complexity.


Back to posts