Riding the wayback time sleigh to Advent of Code 2015 - Day 14 solution (SPOILER ALERT!)

[Junilu Lacar]

Hi folks,

Just thought I'd share. I decided to start prepping for Advent of Code early this year and have gone back to the very first AoC to get some practice. As recent years, I'm doing my solutions in Kotlin.

I'm going to skip ahead to Day 14 here. I was pleasantly surprised to solve Part 1 fairly quickly. After parsing the input and coming up with a formula to calculate the distance traveled by each reindeer, it was just a matter of getting the maximum of all those distances traveled. A one-liner, basically. Ironically, I found out in Part 2 that the formula I had used for the distance calculation was not quite right, even though it had somehow earned me a gold star for a correct answer.

Part 2, where we had to award points to reindeer for every second during the race that they had the lead, was a little trickier. I got the correct answer to my puzzle input with a very imperative-style solution. I guess I haven't quite made the transition to an FP mindset yet. I did have a sense that the imperative-style implementation could be refactored to a more functional style though. After a long, good run at refactoring,

I started with this (the code that earned my 28th gold star) and slowly refactored it to this:

import kotlin.math.min

/**
 * AoC 2015 - Day 14: Reindeer Olympics
 */
class Day14(private val reindeer: List<Reindeer>, private val raceTime: Int) : Solution<Int> {

    override fun part1() = reindeer.maxOf { it.distanceFlownAt(raceTime) }

    override fun part2() = racePoints().values.max()

    private fun racePoints(): Map<Reindeer, Int> =
        (1..raceTime).fold(reindeer.associateWith { 0 }) { points, second ->
            award(points, reindeer.associateWith { it.distanceFlownAt(second) })
        }

    private fun award(points: Map<Reindeer, Int>, distances: Map<Reindeer, Int>): Map<Reindeer, Int>
    {
        val leadersDistance = distances.values.max()
        return points.map { (reindeer, leaderPoints) ->
            reindeer to if (distances[reindeer] == leadersDistance) leaderPoints + 1 else leaderPoints
        }.toMap()
    }

    companion object {
        fun using(input: List<String>, raceTime: Int) = Day14(
            input.map { line ->
                val parts = line.split(" ")
                Reindeer(speed = parts[3].toInt(), flightTime = parts[6].toInt(), parts[13].toInt())
            },
            raceTime
        )
    }

    data class Reindeer(val speed: Int, val flightTime: Int, val restTime: Int) {
        private val cycleTime = flightTime + restTime

        fun distanceFlownAt(raceTime: Int) = speed * secondsFlyingAt(raceTime)

        private fun secondsFlyingAt(raceTime: Int) = fullFlightTime(raceTime) + partialFlightTime(raceTime)
        private fun fullFlightTime(raceTime: Int) = raceTime / cycleTime * flightTime
        private fun partialFlightTime(raceTime: Int) = min(flightTime, raceTime % cycleTime)
    }
}

I have to say, I'm quite happy with how it went. The story for Part 2 is composed and layered nicely from high-level abstract, down to more and more detail. Also, I like that the extracted functions are singular in purpose and are easy to understand. At least, that's what I think when I imagine seeing the code for the first time. I'm curious about what others think though. Appreciate any thoughts/reactions.

I also created a branch to keep a history of my refactoring steps: https://github.com/jlacar/aoc2015/blob/refactor-day14-pt2-to-functional/src/main/kotlin/lacar/junilu/Day14.kt

[Junilu Lacar]

If you know me at all, you'll probably expect that I did a bit of test-driving as I worked through my solutions. Here's the test I used for Day 14:

import org.junit.jupiter.api.Assertions.*
import org.junit.jupiter.api.Nested
import org.junit.jupiter.api.Test

private val puzzleInput = readResource("day14")

class Day14Test {
    @Nested
    inner class Samples {
        @Test
        fun `Comet wins`() {
            val sample = Day14(listOf(
                Day14.Reindeer(speed = 14, flightTime = 10, restTime = 127),
                Day14.Reindeer(speed = 16, flightTime = 11, restTime = 162)
            ), 1000)
            assertEquals(1120, sample.part1())
        }

        @Test
        fun `Dancer wins`() {
            val sample = Day14(listOf(
                Day14.Reindeer(speed = 14, flightTime = 10, restTime = 127),
                Day14.Reindeer(speed = 16, flightTime = 11, restTime = 162)
            ), 1000)
            assertEquals(689, sample.part2())
        }
    }

    @Nested
    inner class Solution {
        @Test
        fun `Part 1 - SOLVED`() {
            assertEquals(2660, Day14.using(puzzleInput, 2503).part1())
        }

        @Test
        fun `Part 2 - SOLVED`() {
            assertEquals(1256, Day14.using(puzzleInput, 2503).part2())
        }
    }
}

[Piet Souris]

Didn't know about AOC in 2015, but here's my day 14: (java, so pretty verbose as always)

public class day_14 {
    private final static int day = 14;
    private static boolean test = false;
    private static List<Reindeer> reindeers = new ArrayList<>();
    
    public static void main(String... args) throws IOException {
        getInput();
        solveA(2503);
        solveB(2503);
    }
    
    private static void getInput() throws IOException {
        var path = AOC2015.getPath(day, test);
        try (var stream = Files.lines(path)) {
            stream.forEach(line -> {
                    var arr = line.split(" ");
                    var speed = Integer.parseInt(arr[3]);
                    var flySeconds = Integer.parseInt(arr[6]);
                    var restSeconds = Integer.parseInt(arr[13]);
                    reindeers.add(new Reindeer(arr[0], speed, flySeconds, restSeconds));
            });
        }
    }
    
    private static void solveA(int totalSecs) {
        Comparator<Reindeer> comp = Comparator.comparingInt(reindeer -> reindeer.distance(totalSecs));
        var result = reindeers.stream().sorted(comp.reversed()).toList();
        System.out.format("reindeer: %s, distance: %d%n", result.get(0), result.get(0).distance(totalSecs));
    }
    
    private static void solveB(int totalSecs) {
        var points = new HashMap<Reindeer, Integer>();
        var mapReindeerListDistances = reindeers.stream()
                .collect(toMap(r -> r, r -> r.distances(totalSecs)))
        ;
        var values = mapReindeerListDistances.values();
        var maxima = IntStream.range(0, totalSecs)
            .map(i -> values.stream()
                          .map(list -> list.get(i))
                          .max(Comparator.naturalOrder())
                          .get()
                )
            .boxed()
            .toList()
        ;
        IntStream.range(0, totalSecs).forEach(i ->
            reindeers.stream()
                .filter(r -> mapReindeerListDistances.get(r).get(i).equals(maxima.get(i)))
                .forEach(r -> points.merge(r, 1, Integer::sum))
        );
        var result = points.values().stream().max(Comparator.naturalOrder()).get();
        System.out.println("max = " + result);
    }
}

record Reindeer(String name, int speed, int flySeconds, int restSeconds) {
    public int distance(int seconds) {
        int period = flySeconds + restSeconds;
        int periods = seconds / period;
        int rest = seconds % period;
        int result = periods * flySeconds * speed;
        int over = min(flySeconds, rest) * speed;
        var antwoord = result + over;
        return antwoord;
    }
    
    public List<Integer> distances(int totalSecs) {
        return IntStream.rangeClosed(1, totalSecs)
                .map(this::distance)
                .boxed()
                .toList()
        ;
    }
}

Oops: just noticed that the plural of reindeer is also reindeer. Blame the English language!

[Mike Simmons]

Piet Souris wrote:Oops: just noticed that the plural of reindeer is also reindeer. Blame the English language!

Hah!  I had the same issue, and also considered "reindeers" for a list of Reindeer.  I chose "herd" instead.

My own Kotlin code was pretty similar to what Junilu showed, with slightly fewer extracted methods with helpful names.  And no automated tests    

[Piet Souris]

A new shorter and easier version in java:

private static void solveA(int totalSecs) {
    var result = reindeers.stream().mapToInt(d -> d.distance(totalSecs)).max().getAsInt();
    System.out.format("A: %d%n", result);
}

private static void solveB(int totalSecs) {
    var points = new HashMap<Reindeer, Integer>();
    Supplier<TreeMap<Integer, List<Reindeer>>> sup = () -> new TreeMap<>(Comparator.reverseOrder());
    IntStream.rangeClosed(1, totalSecs).forEach(sec -> {
        var map = reindeers.stream().collect(groupingBy(d -> d.distance(sec), sup, toList()));
        map.firstEntry().getValue().forEach(d -> points.merge(d, 1, Integer::sum));
    ;});
    var result = points.values().stream().mapToInt(i -> i).max().getAsInt();
    System.out.format("max punten: %d%n", result);
}