https://kotlinlang.org logo
Join Slack
Powered by
:warning: Day 7 Solution Thread  :warning:
# advent-of-code
a
⚠️ Day 7 Solution Thread  ⚠️
b
haha you're starting that early
😂 1
ready?
a
Copy code
private val input = readInput("input7.txt")

fun main() {
    val bags = input.split("\n").map { line ->
        val bag = line.split(" bags contain")[0]
        val others = if (line.contains("contain no other bags")) listOf()
        else line.split("bags contain ")[1].removeSuffix(".").split(", ").map {
            it.split(" ")[0].toInt() to it.split(" ").subList(1, it.split(" ").size - 1).joinToString(" ")
        }
        bag to others
    }

    fun recursePart1(startingBag: String, currentBag: String = startingBag): List<String> =
        if (currentBag == "shiny gold") listOf(startingBag)
        else bags.first { it.first == currentBag }.second.map { recursePart1(startingBag, it.second) }.flatten()
    println("Part 1: ${bags.map { recursePart1(it.first) }.flatten().toSet().size - 1}")

    fun recursePart2(startingBag: String, currentBag: String = startingBag): Int =
        if (bags.first { it.first == currentBag }.second.isEmpty()) 1
        else 1 + bags.first { it.first == currentBag }.second.sumBy { it.first * recursePart2(startingBag, it.second) }
    println("Part 2: ${recursePart2("shiny gold") - 1}")
}
ugly.. but works
k
I essentially had recursion but with a mpa to cache answers. Initialized with "shiny gold" to 1 and "other" to 0.
a
cleaned up my solution
@Kroppeb mpa?
oh map 😄
k
oh, haha
e
used a queue instead of explicit recursion. probably doesn't make a big difference, but I'm so accustomed to writing breadth-first searches for various graph problems in AoC
Untitled
👍 1
a
That was a bit more difficult & fun. Went with a queue for part 1 & recursion for Part 2
Copy code
data class Luggage(val colour: String, val contents: Map<String, Int>){
    companion object {
        private val LUGGAGE_REGEX = """^([a-z ]+) bags contain (.+)\.$""".toRegex()
        private val CONTENTS_REGEX = """^(\d+) ([a-z ]+) bags?$""".toRegex()
        fun of(input: String): Luggage {
            val (colour, contents) = LUGGAGE_REGEX.matchEntire(input)!!.destructured
            val innerBags: Map<String, Int> = when (contents){
                "no other bags" -> emptyMap()
                else -> {
                    contents.split(", ").map {
                        val (count, childColour) = CONTENTS_REGEX.matchEntire(it)!!.destructured
                        Pair(childColour, count.toInt())
                    }.toMap()
                }
            }
            return Luggage(colour, innerBags)
        }
    }
}

fun main() {
    val luggageItems = resourceFile("day07/Bags.txt").readLines().map { Luggage.of(it) }

    val reverseMap = luggageItems.flatMap {
            parent -> parent.contents.keys.map { childColour -> Pair(childColour, parent.colour) }
    }.groupBy(keySelector = {it.first}){it.second}

    val luggageMap = luggageItems.map { it.colour to it.contents }.toMap()

    println("Part 1: ${findAncestors("shiny gold", reverseMap).size}")
    println("Part 2: ${countBags("shiny gold", luggageMap) - 1}")
}

fun countBags(colour: String, luggageMap : Map<String, Map<String,Int>>) : Int {
    return 1 + luggageMap[colour]!!.entries.sumBy { it.value * countBags(it.key, luggageMap) }
}

fun findAncestors(colour: String, reverseMap:Map<String,List<String>>): Set<String> {
    val visited = mutableSetOf<String>()
    val stack : Deque<String> = ArrayDeque<String>()
    reverseMap[colour]!!.forEach { stack.add(it) }
    while (!stack.isEmpty()){
        val nextParent = stack.pop()!!
        if (visited.add(nextParent)){
            reverseMap[nextParent]?.let{ it.forEach { stack.add(it) } }
        }
    }
    return visited
}
m
not a great fan of my input parsing, but I thought since it wasn't doable with a single regex anyway, I'll parse it manually. I included memoization because I thought that would matter, but it doesn't really for this input size.
Copy code
object Day7 : AdventOfCode() {
    val parsed: Map<String, List<Pair<Int, String>>> = parseInput(input)

    override fun part1() = mutableMapOf("shiny gold" to true).let { mem -> parsed.keys.count { containsShinyGold(mem, it) } - 1 }

    private fun containsShinyGold(memory: MutableMap<String, Boolean>, currentColor: String) : Boolean = memory.getOrPut(currentColor){
        parsed.getValue(currentColor).any { containsShinyGold(memory, it.second) }
    }

    override fun part2() = countBags(mutableMapOf(), "shiny gold") - 1

    private fun countBags(memory: MutableMap<String, Int>, color: String) : Int = memory.getOrPut(color){
        1 + parsed.getValue(color).sumBy { (amount, other) -> amount * countBags(memory, other) }
    }

    private fun parseInput(input: String) : Map<String, List<Pair<Int, String>>>{
        return input.lines().map { line ->
            val (main, rest) = line.split(" bags contain ")
            main to when (rest) {
                "no other bags." -> emptyList()
                else -> rest.split(", ").map {
                    it.substringBefore(" ").toInt() to it.substringAfter(" ").substringBefore(" bag")
                }
            }
        }.toMap()
    }
}
j
I struggled a lot with the parsing, I am sure somebody who knows more about regular expressions could do it more elegantly. Otherwise quite pleased with the code. The running times for NodeJS (1.7 seconds) and native (4.7 second) were dramatically slower than on Graal (84 ms). Maybe something to do with the recursion? I have no idea...
👏🏻 3
j
😂 3
n
Copy code
data class ContainedBag(val num: Int, val name: String)
data class Rule(val containing: String, val contained: List<ContainedBag>)

fun String.toRule(): Rule {
    val (containing, contained) = split(" contain ")
    val containingBag = containing.popSuffix(" bags")!!
    if (contained == "no other bags.") return Rule(containingBag, emptyList<ContainedBag>())
    val containedBags = contained.split(", ", ".").filter { it.isNotEmpty() }.map {
        val droppedSuffix = it.popSuffix(" bags") ?: it.popSuffix(" bag")!!
        val result = droppedSuffix.split(" ", limit=2)
        ContainedBag(result.first().toInt(), result.last())
    }
    return Rule(containingBag, containedBags)
}

fun getData() = (aocDataDir / "day7.txt").useLines { it.map { it.toRule() }.toList() }

fun addParents(parentGraph: Map<String, List<String>>, key: String, alreadyFound: MutableSet<String>): Unit {
    for (bag in parentGraph[key] ?: return) {
        if (bag in alreadyFound) continue
        alreadyFound.add(bag)
        addParents(parentGraph, bag, alreadyFound)
    }
}

fun part1(): Int {
    val parentMap = mutableMapOf<String, MutableList<String>>()
    getData().forEach { rule -> rule.contained.forEach {
        parentMap.getOrPut(it.name) { mutableListOf<String>() }.add(rule.containing)
    } }
    val bagSet = mutableSetOf<String>()
    addParents(parentMap, "shiny gold", bagSet)
    return bagSet.size
}

fun sumChildren(graph: Map<String, List<ContainedBag>>, key: String): Int {
    return graph[key]!!
        .map { it.num * (1 + sumChildren(graph, it.name)) }
        .sum()
}

fun part2(): Int {
    val graph = getData().associate { it.containing to it.contained }
    return sumChildren(graph, "shiny gold")
}
parsing was definitely the trickiest in the end lol. I guess I got a bit lucky with the recursive logic, when your first attempt is wrong it always takes so much longer to debug
Also, did anyone think that part2 was quite a bit easier than 1?
a
I did
t
Not happy with this, but I'm bogged down with work today.
Copy code
class Day07(input: List<String>) {

    private val bags: Map<String, Bag> = parseInput(input)

    fun solvePart1(): Int =
        bags.getValue("shiny gold").findAllParents().size

    fun solvePart2(): Int =
        bags.getValue("shiny gold").calculateCost() - 1

    private fun parseInput(input: List<String>): Map<String, Bag> {
        val relationships = input.filterNot { it.contains("no other") }.flatMap { row ->
            val parts = row.replace(unusedText, "").split(whitespace)
            val parent = parts.take(2).joinToString(" ")
            parts.drop(2).windowed(3, 3, false).map { child ->
                // Tuple = (Parent, Cost, Child)
                Triple(parent, child.first().toInt(), child.drop(1).joinToString(" "))
            }
        }
        return mutableMapOf<String, Bag>().apply {
            relationships.forEach {
                computeIfAbsent(it.first) { name -> Bag(name) }.apply {
                    val child = computeIfAbsent(it.third) { name -> Bag(name) }
                    children.add(Pair(child, it.second))
                    child.parents.add(this)
                }
            }
        }
    }

    class Bag(
        val name: String,
        val parents: MutableSet<Bag> = mutableSetOf(),
        val children: MutableSet<Pair<Bag, Int>> = mutableSetOf()
    ) {
        fun findAllParents(): Set<Bag> =
            parents.flatMap { setOf(it) + it.findAllParents() }.toSet()

        fun calculateCost(): Int =
            1 + children.sumBy { it.second * it.first.calculateCost() }

        override fun equals(other: Any?): Boolean = when {
            this === other -> true
            other is Bag && name == other.name -> true
            else -> false
        }

        override fun hashCode() = name.hashCode()
    }

    companion object {
        private val unusedText = """bags|bag|contain|,|\.""".toRegex()
        private val whitespace = """\s+""".toRegex()
    }
}
a
@todd.ginsberg I like the idea of using the Triple from the parsing of the data. That could save a lot of work.
t
I could see about just leaving it that way (as a Set of Triples) and pick through them. But I feel that it might be more work on a larger dataset. I dunno. I have to let this one sit for a while before I write it up 🙂
Oh, that looks better. Not as efficient, but looks nicer.
c
I over-engineered the crap out of this one: wrote a full recursive-descent parser combinator to parse each input line. Went with recursive+memoized solutions for both part 1 and 2
😱 1
j
took me half an hour to create decent solution, with caching etc, and then 4 hours to create visualisation... In the process, I learned how to flex and how to make ugly presentation. Although I'm not sure about that flex. And as a backend dev, I always knew how to make ugly UI. Anyway - enjoy. https://jakubgwozdz.github.io/advent-of-code-2020/day07/ (as always, I'll open the input data to edit in a few days, right now it's mine only)
👍 2
n
pretty slick!
a
Refactored solution to use the Triple as suggested by @todd.ginsberg. Much cleaner now 🙂
Copy code
fun main() {

    val LUGGAGE_REGEX = """^([a-z ]+) bags contain (.+)\.$""".toRegex()
    val CONTENTS_REGEX = """^(\d+) ([a-z ]+) bags?$""".toRegex()

    // Rules held as a Tuple ( outer bag, inner bag, number required )
    val rules : List<Triple<String, String, Int>> = resourceFile("day07/Bags.txt").readLines().flatMap {
        val (colour, contents) = LUGGAGE_REGEX.matchEntire(it)!!.destructured
        when (contents) {
            "no other bags" -> emptyList()
            else -> {
                contents.split(", ").map {
                    val (count, childColour) = CONTENTS_REGEX.matchEntire(it)!!.destructured
                    Triple(colour,childColour, count.toInt())
                }
            }
        }
    }

    fun ancestors(colour: String) : List<String> {
        val ancestors = rules.filter{it.second == colour}
        return ancestors.map { it.first } + ancestors.flatMap { ancestors(it.first) }
    }

    fun contents(colour: String) : Int {
        return 1 + rules.filter{it.first == colour}.sumBy { it.third * contents(it.second) }
    }

    println("Part 1: ${ancestors("shiny gold").toSet().size}")
    println("Part 2: ${contents("shiny gold") -1}")
}
n
Why not just define a data class one liner instead of using Triple
especially when two members of the Triple have the same type, data class is much easier to read and harder to mess up, and only costs one line
a
You could. I used a data class earlier which held the child bags in a Map but could just use a simpler class here
t
Nice work Andy! I ended up refactoring my triple out to a data class because it was easier to explain. Slammed at work today so I’ll probably not get to write this up until late. :(
a
@Nir is right. Have replaced the Triple with a Data Class but solution is still the same
n
the nice thing about dataclasses is that they're so little work to define, and don't inhibit you at all. you still get hashing and equality for free, it has basically no downside. They're fantastic.
Copy code
data class ContainedBag(val num: Int, val name: String)
data class Rule(val containing: String, val contained: List<ContainedBag>)
The first two lines in my solution. Makes signatures so much cleaner too.
a
Copy code
fun ancestors(colour: String) : List<String> {
    return rules
        .filter{it.childColour == colour}
        .flatMap { ancestors(it.parentColour) + it.parentColour }
}

fun contents(colour: String) : Int {
    return 1 + rules.filter{it.parentColour == colour}.sumBy { it.count * contents(it.childColour) }
}
b
Copy code
data class Bag(
    val name: String,
    val content: MutableMap<Bag, Int>
) {
    fun contains(name: String): Boolean = content.keys.any { it -> (it.name == name) || it.contains(name) }
    fun count(): Int = content.map { (k, v) -> v * (1 + k.count()) }.sum()
}

fun main() {
    val absoluteBags = mutableMapOf<String, Bag>()
    linesFile("data/2020/07_input.txt").forEach {
        val (bagName, rest) = it.replace("""\sbags?[\.,]?""".toRegex(), "").split(" contain ")
        absoluteBags.putIfAbsent(bagName, Bag(bagName, mutableMapOf()))
        rest.split(" ").chunked(3).filter { it[1] != "other" }.forEach {
            val name = "${it[1]} ${it[2]}"
            absoluteBags.putIfAbsent(name, Bag(name, mutableMapOf()))
            absoluteBags[bagName]!!.content[absoluteBags[name]!!] = it[0].toInt()
        }
    }
    println(absoluteBags.count { (k, v) -> v.contains("shiny gold") }) // 185
    println(absoluteBags["shiny gold"]?.count()) // 89084
}
I'm sure it can be much simpler
I couldn't find a regex to get the groups cleanly, but if I had that it would be easier
t
m
Ah, the Redddit-bag-photo was already posted here...sorry for the repost then. Anyhow, day 7: https://github.com/mickeelm/aoc2020/blob/main/src/main/kotlin/Day7.kt
3 Views
Open in Slack
PreviousNext
Powered by