:christmas_tree: Advent of Code (2019)

What is Advent of Code?

Excerpt from the Advent of Code website;

"Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets
and skill levels that can be solved in any programming language you like. People use them as a
speed contest, interview prep, company training, university coursework, practice problems, or
to challenge each other."

About

Working through the advent of code while learning Kotlin. Acts as a nice format for personal development. I'm treating the code-base a little more enterprise-esque, for lack of a better term. Meaning I'm focusing more on design, readability, and ensuring code is test-driven with full coverage etc. This doesn't mean, however, that I'm not considering performance. Any solutions that don't meet a respectable order of runtime complexity will be refactored and improved upon in a later pass of the days.

Contents

• Getting Started
  • Gradle Tasks
• The Codebase
  • Package Structure
  • Design
  • Static Code Analysis & Linting
  • Testing
  • Java Micro-Benchmarking Harness
  • JUnit5 & AssertK
  • Test Driven Development
  • VisualVM Sampling & Profiling
• The Days
  • Most Challenging
  • Mathematically Challenging
  • Most Fun
• What I Learned
  • Kotlin
  • Data Structures & Algorithms
  • Performance & Runtime Complexity
• Answer Table & Puzzle Documentation

Getting Started

If you wanted to clone the repository and run the solutions, you need only clone/download, import it as a Gradle project in your IDE, and run the respective solution file.

Annotation Processing must be enabled in your IDE for the JMH tests to run. In IntelliJ; \ Preferences -> Build, Execution, Deployment -> Compiler -> Annotation Processors

Gradle Tasks

The Codebase

Package Structure

The package structure was something that changed almost every day. My goal was "package-by-feature". For the first few days it seemed like I'd just end up having 25 different packages whose names were relevant keywords from that day. However, towards the latter half of the days, there were consistencies in the naming that started to make the language a little more ubiquitous. This allowed me to start grouping packages together and start abstracting out common code.

I created two Gradle root projects, implementation and solutions. With the former having sub-projects, common, for behaviour that is commonly used across multiple days and test-support for unit test utility classes.

-implementation
    -src
    -common
    -test-support
-solutions

Design

-Design Patterns

Static Code Analysis & Linting

I used the DeteKT Gradle plugin to perform static code analysis on the codebase. It produces a report containing all the code-smells that it found based on the set configuration. The custom configuration is defined in detekt-config.yml and can be found in the implementation resources.

Testing

JMH (Java Micro-Benchmarking Harness)

Due to the nature of the puzzle inputs, lots of the second parts scaled the input size significantly. The shear size of these inputs made the solutions impossible to brute-force or to even wait for with a runtime complexity of O(n). I used VisualVM to manually investigate crippling performance issues, but I wanted an automated solution to run across the whole codebase.

From the OpenJDK website;

"JMH is a Java harness for building, running, and analysing nano/micro/milli/macro benchmarks
written in Java and other languages targeting the JVM."

Junit5 & AssertK

The JUnit5 Jupiter API exposes some really nice functionality in the form of annotations and offers callback interfaces for each of the life-cycle events. Utilising the @ParameterizedTest can significantly reduce the quantity of test-methods in your unit tests suites while @Nested allows you to organise your tests in nested classes.

AssertK is an assertion library inspired by AssertJ but for Kotlin. I'm familiar with AssertJ and prefer the naming conventions and variety of assertions over the default JUnit offering.

Test-Driven Development

I'm a huge advocate of testing in general, but particularly test-driven development. Some days were easy to test-drive as they provided lots of examples that generally covered all branches of the algorithm and sometimes even edge cases. Given I was taking a proper object-orientated approach, and not just hacking it into a single function, I still had to write more tests than just the example inputs, but they were a nice baseline to run against while writing a solution.

VisualVM Sampling & Profiling

During the first iterations of the graphing algorithms, runtime performance was an issue. There were several cases where the first rough implementation passed all the example tests, but didn't suffice for the scaled puzzle input.

This is where VisualVM came in handy. The aforementioned desktop-client in tandem with the IntelliJ Plugin made it easy to run a given unit test with a VisualVM instance attached the JVM process. This allowed me to sample and profile classes of my choice to find the source of the performance issues.

One problem I ran into (and seemingly many others online too) was that JUnit5 bootstrapped and ran my test so quickly that it finished before VisualVM even had a chance to boot-up. A common solution I'd seen was to simply add a Thread.sleep(x) line at the start of the test method. Although this is the solution I technically went with, I abstracted it into a @WaitForVisualVM annotation and created a custom implementation of the Jupiter APIs BeforeTestExecutionCallback interface called SupportsVisualVM.kt which can be added to a test-suite class using the @ExtendWith annotation.

This kept things inline with the 'enterprise-style' aspect of my codebase as it did the following;

• Wrapped the dubious Thread.sleep() call with a self-explanatory annotation (and is also documented).
• Removed noise from the test method and ensured that it always runs before test-execution.
• Allows developers to easily disable all waiting for tests in a suite by simply removing the support extension.
• Makes it easier to refactor in the future the as implementation specifics are encapsulated in the annotation.

Although it might seem over-engineered, it's really just a trivial example to demonstrate the concept and its benefits.

The Days

Most Challenging (Day 18)

This day was an odd one. Usually the implementation is the 'easy' bit, and figuring out the theory behind the solution is the harder bit that can take a while. However, Day 18s theory was simple. It was a maze filled with doors with corresponding keys, and you had the find the shortest path to collect all keys. So it was just a case of using an exhaustive DFS (Depth First Search) Algorithm that would graph all the keys and their respective weights to any other accessible ones. Then running Dijkstra's Algorithm on the weighted graph to find the shortest path. I just couldn't figure out how to implement it. I spent so many hours trying different things until I eventually managed to get 4 of the 5 examples working. Example 5, however, just ran indefinitely and so did my puzzle input. I needed to improve the performance of my graphing algorithm, so my solution input didn't take a literal eternity to run.

Mathematically Challenging (Day 22)

Day 22, Slam Shuffle, started off in part 1 as nice and easy puzzle with some interesting card shuffling strategies that work nicely with behavioural design patterns. However, part 2 threw a spanner in the works with what some have called 'Advent of Math'. The second part increased the deck size from 1x10^5 -> 1x10^14 and the number of shuffles from 1 to an order of magnitude similar to that of the deck size. The solution in short was to;

1. Represent the shuffling algorithms as linear functions in the form f(x) = ax + b (See table below).
2. Create a single aggregate function by composing all the converted linear functions together.
3. Use exponentiation by squaring with modular arithmetic in order to reduce the number of shuffles required.

Most Fun (Day 8)

This day was the most fun because I didn't understand what was actually going on until I'd successfully implemented a solution. It was only shortly after re-reading the documentation that I understand what was happening. The output below is the result of flattening a three-dimensional array of integers that represented pixel colours. After traversing the array vertically and exposing the upper-most opaque pixels, it produced a bitmap that represented an image of the spaceships' registration number.

1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0
1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0
1 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0
1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0
1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0
1 0 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 0

After I realised what my output was, I parsed the black pixels as octothorps, and the transparent as spaces and got the below output. This was interesting to me as it meant you couldn't programmatically test your solution and therefore required human interpretation. I suppose you could use an OCR (Optical Character Recognition) software.

#     #     # #     # # #       # #     # # # #  
#     #   #     #   #     #   #     #   #        
# # # #   #         # # #     #         # # #    
#     #   #   # #   #     #   #         #        
#     #   #     #   #     #   #     #   #        
#     #     # # #   # # #       # #     #        

The moment it clicked, and I saw the ASCII style text printed out, it put a huge grin on my face as this was the first time I'd seen such a niche puzzle in Advent of Code.

What I Learned

Kotlin & Kotlin Gradle DSL

A friend of mine had been raving about Kotlin for months at work, and I finally decided to start learning it when I started the Advent of Code. Having written in nothing but Java 10 hours a day for 2 years, I was amazed by how easy it was to pick the language up. The first thing I noticed was how succinct the language was syntactically. Most simple functions could be one-liners; return types were mostly implicit; and features such as data classes removed a lot of the boilerplate code that is prevalent in enterprise Java code.

Data Structures & Algorithms

Graphs, trees and mazes were a common theme and meant that path-finding algorithms were common.

• DFS (Depth First Search)
• BFS (Breadth First Search)
• Dijkstra Algorithm
• Flooding Algorithm

Where there are Data Structures & Algorithms, there are always performance considerations...

Performance

Implementing the aforementioned data structures and algorithms means that some solutions needed refactoring for performance optimisation due to the vast puzzle input sizes. This meant that careful consideration was needed when choosing data structures and designing the algorithms. It even meant that in some cases, a brute-force approach was impossible due to it taking an eternity to run (Looking at you, Day 12... simulating the repetition of time).

For the most part, only runtime-complexity was a concern. There were few occasions where space-complexity was an issue.

Answer Table