Junilu Lacar

Hi folks,

More Advent of Code adventures. Been working on Day 15 which asks to find the best mix of ingredients for a cookie. https://adventofcode.com/2015/day/15

I guess it's a variation of the Knapsack_problem. I couldn't figure out the algorithm without hardcoding so I resorted to stealing. Finally found a general solution but in Python. It used yield. Kotlin has a similar construct. Here's my Kotlin adaptation that worked:

fun proportions(parts: Int, total: Int): Sequence<IntArray> = sequence {    val start = if (parts == 1) total else 0    for (portionSize in (start..total)) {        if (parts <= 1) {            yield(intArrayOf(portionSize))        }  else {            for (portion in proportions(parts - 1, total - portionSize)) {                yield(intArrayOf(portionSize) + portion)            }        }    } }
I tried the code below, thinking I could treat yield like a return, but it didn't work.
fun proportions(parts: Int, total: Int): Sequence<IntArray> = sequence {    val start = if (parts == 1) total else 0    for (portionSize in (start..total)) {        if (parts <= 1) {            yield(intArrayOf(portionSize))        }          for (portion in proportions(parts - 1, total - portionSize)) {            yield(intArrayOf(portionSize) + portion)        }    } }
This version behaved like it got stuck in an endless loop in the inner for-loop. Not exactly sure why. Any help understanding what's going on here will be greatly appreciated. Thanks.

Junilu Lacar wrote:

Piet Souris wrote:My worry with these things is that if you work with immutable collections, that you get a lot of them while doing the stuff.

I'm fairly confident that with languages that have garbage collection, working with immutable collections in a function like fold() is not an issue. Immutability is a cornerstone of functional programming, so any language that supports functional programming constructs would presumably find a way to make reasonable optimizations.

By running the code through the profiler, I proved myself wrong here and confirmed Piet's fear

More lessons learned: The person who keyed me in on the problem with head also pointed out that using an immutable list for the accumulator in the fold() could impact performance significantly. So, like any responsible programmer   , I ran my code through a profiler.

The results for larger lists was quite illuminating. For smaller lists (up to 6 elements in my tests), the recursive step wasn't even flagged as the biggest bottleneck. What got flagged instead was the initial creation of the lists themselves, that is, the call to listOf(), especially the first few ones in a series of calls to listOf() I had in my main() function.

The recursive call did get flagged as the main bottleneck when I tried it with a larger list, 10 elements (3,628,800 permutations).

The version that used fold(mutableListOf()) took 508ms at the recursive call, taking 53% of the entire run time.

I had to stop the version that used fold(listOf()) { ... + acc } after 50+ seconds because it was getting ridiculous. I tried with just 9 elements (362,880 permutations) and it took the recursive part 3,398ms and 89% of the entire run time. The mutable list version with 9 elements took 70ms and 47% of the time at the recursive step, but again, the listOf in main() to create the original list was flagged as the main bottleneck, clocking in at 90ms and 60% of the time.

It looks like performance for the immutable version definitely degrades much faster (exponentially?) as the list size increases.

Based on this, I'm reverting to using a mutable accumulator for the fold().

Piet Souris wrote:The problem with java is that when you mutate a collection, you get a boolean instead of the mutated collection.

Not surprisingly, Kotlin has a very similar behavior for its add() function. Luckily, there's also the plus (+) operation, which returns a List when used with lists. This is why the last version of my code that I posted works, because the last expression in the fold() body is the result of plus-ing a list of new permutations and the permutations already in the accumulator acc.

I think I'll go with this version that keeps things immutable in the fold():
   return tail.permutations()        .fold(listOf()) { acc, perm ->            (0..perm.size).mapTo(mutableListOf()) { i ->                 perm.subList(0, i) + head + perm.subList(i, perm.size)            } + acc        }

Piet Souris wrote:My worry with these things is that if you work with immutable collections, that you get a lot of them while doing the stuff.

I'm fairly confident that with languages that have garbage collection, working with immutable collections in a function like fold() is not an issue. Immutability is a cornerstone of functional programming, so any language that supports functional programming constructs would presumably find a way to make reasonable optimizations.

Another way to do this without getting too cutesey:

fun <T> List<T>.permutations(): List<List<T>> {    if (isEmpty()) return emptyList()    if (size == 1) return listOf(this)    val allPerms = mutableListOf<List<T>>()    tail.permutations().forEach { perm ->         (0..perm.size).mapTo(allPerms) { i ->             perm.subList(0, i) + head + perm.subList(i, perm.size)         }    }    return allPerms }
But that's basically the fold()-with-mutable version with a couple extra lines.

Since the above still mutates that fold accumulator, I thought I'd try something that didn't do that at all and this is what I got:

fun <T> List<T>.permutations(): List<List<T>> {    if (isEmpty()) return emptyList()    if (size == 1) return listOf(this)    val allPerms = mutableListOf<List<T>>()    return tail.permutations()        .forEach { perm ->            (0..perm.size).mapTo(allPerms) { i ->                perm.subList(0, i) + head + perm.subList(i, perm.size)            }        }.let { allPerms } }
Doesn't seem any better to me though. To fold with a mutable or not to fold with a mutable, that is the question. What do you folks think?

I'm going with this alternative:

/** * Calculate permutations of elements in a List */ // Extension properties val <T> List<T>.head: T    get() = first() val <T> List<T>.tail: List<T>    get() = drop(1) // Extension function fun <T> List<T>.permutations(): List<List<T>> {    if (isEmpty()) return emptyList()    if (size == 1) return listOf(this)    return tail.permutations()        .fold(mutableListOf()) { acc, perm ->            (0..perm.size).mapTo(acc) { i ->                perm.subList(0, i) + head + perm.subList(i, perm.size)            }        } }
I switched back to acc for the accumulator parameter because I think it will be familiar to most readers. Should I stick with the intention-revealing name allPerms?

I posted the question on r/kotlin and someone pointed out that head binds to the nearest this and that was what was causing the different behavior with apply. Makes perfect sense now.

They also pointed out that mutating something inside a fold is not good practice... I'm seeing that now.

I think I had at one point a version that used a forEach as the same person suggested, so I'll probably go back to that, or use mapTo as a second person suggested. Those like good alternatives to the inner fold.

I'll update my gist accordingly.

I've been trying to extract some code that calculates permutations that I used in a couple of Advent of Code problems (still working AoC 2015)

I created a Gist with the details of what I learned. https://gist.github.com/jlacar/18345c1802260cd4361090be9c4cebb4 - This gist also includes some code that exercises the function.

Here's the code that worked:
val <T> List<T>.head: T    get() = first() val <T> List<T>.tail: List<T>    get() = drop(1) fun <T> List<T>.permutations(): List<List<T>> {    if (isEmpty()) return emptyList()    if (size == 1) return listOf(this)    return tail.permutations()        .fold(mutableListOf()) { allPerms, perm ->            (0..perm.size).fold(allPerms) { acc, i ->                acc.add(perm.subList(0, i) + head + perm.subList(i, perm.size))                acc            }        } }

To try to tighten up the code in the inner fold operation, I tried using the apply() scope function but was surprised to find that it didn't work (my previously working code and tests failed).

I tried using also and it worked. I don't know what the difference is with apply though because my understanding is that both also and apply return the context object. I assumed that value returned by apply was the context object after the body of apply executed but since it made previously working code fail, I guess I was wrong.

Here's the code that used `also` that worked:
fun <T> List<T>.permutations(): List<List<T>> {    if (isEmpty()) return emptyList()    if (size == 1) return listOf(this)    return tail.permutations()        .fold(mutableListOf()) { allPerms, perm ->            (0..perm.size).fold(allPerms) { acc, i ->                acc.also { it.add(perm.subList(0, i) + head + perm.subList(i, perm.size)) }            }        } }

The code that uses `apply` that DIDN'T work:
fun <T> List<T>.permutations(): List<List<T>> {    if (isEmpty()) return emptyList()    if (size == 1) return listOf(this)    return tail.permutations()        .fold(mutableListOf()) { allPerms, perm ->            (0..perm.size).fold(allPerms) { acc, i ->                acc.apply { this.add(perm.subList(0, i) + head + perm.subList(i, perm.size)) }            }        } }

Any thoughts?

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())        }    } }

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

public class Message {   private final String text;   private final MessageType type;   public Message(MessageType type, String text) {      this.type = type;      this.text = text;   }   // no setters, just getters   ... }

I concur with Lou's suggested approach, but without the setter for message type. Do it all in the constructor and make the class immutable.

Also, consider renaming the class to simply Message: I don't see any reason to name it "MessageReturn" - you're probably thinking "It's a massage that I return, so 'MessageReturn'". No. It's a message plain and simple. The fact that you return it from a method is irrelevant to the name choice.