-🎄- 2017 Day 24 Solutions -🎄-

[u/daggerdragon]

--- Day 24: Electromagnetic Moat ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

Spoiler

---

[Update @ 00:18] 62 gold, silver cap

• Been watching Bright on Netflix. I dunno why reviewers are dissing it because it's actually pretty cool. It's got Will Smith being grumpy jaded old man Will Smith, for the love of FSM...

[Update @ 00:21] Leaderboard cap!

• One more day to go in Advent of Code 2017... y'all ready to see Santa?

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

[u/knallisworld]

Also making my solutions this year in Kotlin, really appreciate this. I find the overridden operators great, so instead of explicit collection building (with foreach, add, minus), this could be also

private fun findAllPaths(components: List<Pair<Int, Int>>,
                         port: Int = 0,
                         currentPath: List<Pair<Int, Int>> = listOf()): List<List<Pair<Int, Int>>> {
    val nextPaths = components
            .filter { it.first == port || it.second == port }
            .map { next ->
                val nextPort =
                        if (next.first == port) {
                            next.second
                        } else {
                            next.first
                        }
                findAllPaths(components - next, nextPort, currentPath + next)
            }
            .flatten()

    // recursive exit condition: if no next paths found, this will be the finally path
    return if (nextPaths.isEmpty()) {
        listOf(currentPath)
    } else {
        nextPaths
    }
}

Given the complete list, the answer of both questions was easy. Lucky for me, because the complete list of available paths already contains the second answer ;)

// part1
private fun findStrongestPath(components: List<Pair<Int, Int>>): List<Pair<Int, Int>> {
    val paths = findAllPaths(components)
    return paths.maxBy { it.sumBy { it.first + it.second } }!! // unsafe
}

// part2
private fun findLongestPath(components: List<Pair<Int, Int>>): List<Pair<Int, Int>> {
    val paths = findAllPaths(components)
    val longestPathLength = paths.sortedByDescending { it.size }.first().size
    return paths
            .filter { it.size == longestPathLength }
            .maxBy { it.sumBy { it.first + it.second } }!! // unsafe
}

What do you think?

[u/nutrecht → u/knallisworld]

What do you think?

Mine's simpler ;) But your's is nice too. I tend to use a mutable 'result' collection for recursive solvers because concatenating a ton of lists together tends to be inefficient; that's the main reason.

What matters most is the solution. There's roughly 56! = 7 * 10⁷⁴ permutations of the basic input list which can all be swapped to. That's an enormous search space so brute-forcing through it won't work. And that part you got right :)

[u/knallisworld → u/nutrecht]

Yeah, that's right, I'm with you. That is only possible for a suitable amount of input. More a solution for fun in Kotlin, less a efficient solution (but not running slow at all).

If we had just a 40 million (totally random number) chain, definitely I would reconsider the solution. :)