{"@attributes":{"version":"2.0"},"channel":{"title":"DEV Community: Eric Burden","description":"The latest articles on DEV Community by Eric Burden (@ericwburden).","link":"https:\/\/dev.to\/ericwburden","image":{"url":"https:\/\/media2.dev.to\/dynamic\/image\/width=90,height=90,fit=cover,gravity=auto,format=auto\/https:%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F538131%2Fa53a7954-5d99-4783-b473-596864e4e193.jpeg","title":"DEV Community: Eric Burden","link":"https:\/\/dev.to\/ericwburden"},"language":"en","item":[{"title":"Advent of Code 2023 - Day 12","pubDate":"Tue, 12 Dec 2023 00:00:00 +0000","link":"https:\/\/dev.to\/ericwburden\/advent-of-code-2023-day-12-3o2","guid":"https:\/\/dev.to\/ericwburden\/advent-of-code-2023-day-12-3o2","description":"

It\u2019s that time of year again! Just like last year, I\u2019ll be posting my solutions to the Advent of Code<\/a> puzzles. This year, I\u2019ll be solving the puzzles in Kotlin<\/a>. I\u2019ll post my solutions and code to GitHub<\/a> as well. If you haven\u2019t given AoC a try, I encourage you to do so along with me!<\/p>\n\n

\n \n \n Day 12 - Hot Springs\n<\/h1>\n\n

Find the problem description HERE<\/a>.<\/p>\n\n

\n \n \n The Input - Oh My Pun!\n<\/h2>\n\n

Today we have a relatively simple input for a deceptively difficult problem. Let's start with the input, though. We have multiple lines where each line is split in half (by a single space every time, thankfully). The left half depicts different spring in different conditions and the right half indicates the sizes of known sizes of damaged groups. Oh, also, \"Hot Springs\". Get it?
\n<\/p>\n\n

\n
\n\/**\n * This enum represents the different states a spring\n *\n * @property rep The character that represents this enum variant.\n *\/<\/span>\nenum<\/span> class<\/span> Condition<\/span>(<\/span>val<\/span> rep<\/span>:<\/span> Char<\/span>)<\/span> {<\/span>\n    DAMAGED<\/span>(<\/span>'#'<\/span>),<\/span> OPERATIONAL<\/span>(<\/span>'.'<\/span>),<\/span> UNKNOWN<\/span>(<\/span>'?'<\/span>);<\/span>\n\n    companion<\/span> object<\/span> {<\/span>\n        fun<\/span> fromChar<\/span>(<\/span>char<\/span>:<\/span> Char<\/span>):<\/span> Condition<\/span> {<\/span>\n            return<\/span> when<\/span> (<\/span>char<\/span>)<\/span> {<\/span>\n                '#'<\/span> -><\/span> DAMAGED<\/span>\n                '.'<\/span> -><\/span> OPERATIONAL<\/span>\n                '?'<\/span> -><\/span> UNKNOWN<\/span>\n                else<\/span> -><\/span> throw<\/span> IllegalArgumentException<\/span>(<\/span>\"Cannot represent '$char' as a [Condition]!\"<\/span>)<\/span>\n            }<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\n\n\/**\n * This class represents the condition record of a single row of springs.\n * \n * @property springs A list of the conditions of the springs.\n * @property damagedGroups A list of known sizes of damaged groups.\n *\/<\/span>\ndata class<\/span> ConditionRecord<\/span>(<\/span>\n    val<\/span> springs<\/span>:<\/span> List<\/span><<\/span>Condition<\/span>>,<\/span> val<\/span> damagedGroups<\/span>:<\/span> List<\/span><<\/span>Int<\/span>><\/span>\n)<\/span> {<\/span>\n    companion<\/span> object<\/span> {<\/span>\n        \/\/ Parse the input lines!<\/span>\n        fun<\/span> fromString<\/span>(<\/span>str<\/span>:<\/span> String<\/span>):<\/span> ConditionRecord<\/span> {<\/span>\n            val<\/span> (<\/span>conditionStr<\/span>,<\/span> groupStr<\/span>)<\/span> =<\/span> str<\/span>.<\/span>split<\/span>(<\/span>\" \"<\/span>).<\/span>map<\/span> {<\/span> it<\/span>.<\/span>trim<\/span>()<\/span> }<\/span>\n            val<\/span> conditions<\/span> =<\/span> conditionStr<\/span>.<\/span>map<\/span>(<\/span>Condition<\/span>::<\/span>fromChar<\/span>)<\/span>\n            val<\/span> groups<\/span> =<\/span> groupStr<\/span>.<\/span>split<\/span>(<\/span>\",\"<\/span>).<\/span>map<\/span> {<\/span> it<\/span>.<\/span>toInt<\/span>()<\/span> }<\/span>\n            return<\/span> ConditionRecord<\/span>(<\/span>conditions<\/span>,<\/span> groups<\/span>)<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\n\nclass<\/span> Day12<\/span>(<\/span>input<\/span>:<\/span> List<\/span><<\/span>String<\/span>>)<\/span> {<\/span>\n\n    private<\/span> val<\/span> parsed<\/span> =<\/span>\n        input<\/span>.<\/span>filter<\/span> {<\/span> it<\/span>.<\/span>isNotEmpty<\/span>()<\/span> }.<\/span>map<\/span>(<\/span>ConditionRecord<\/span>::<\/span>fromString<\/span>)<\/span>\n\n}<\/span>\n\n<\/code><\/pre>\n\n<\/div>\n\n\n\n
Not too much to say about parsing today. LOTS to say about solving the puzzle, though.<\/p>\n\n
\n  \n  \n  Part One - Novel Algorithm\n<\/h2>\n\n
In part one, our goal is to figure out which springs are damaged,
\narmed with the knowledge of which springs might<\/em> be damaged and how large all the damaged groups are. My first instinct was to try a depth-first search over the springs, and honestly, it might have taken that approach less time to run than it took me to type through my explanation for the dynamic programming approach I ended up taking. See, I had an inkling that I was dealing with overlapping sub-problems, and I was right! Now, on to the lengthy explanation!<\/p>\n
\n  \n  \n  Example 1: .???.### 1,1,3\n<\/h3>\n\n
Note, my examples trim all the '.' from the original puzzle input and prepend one '.'. I'm not sure this is 100% necessary, but it made it easier for me to think through. In this example, we have three groups of damaged springs (of lengths 1, 1, and 3) and 8 total springs, of which 2 are operational ('.'), 3 are damaged ('#'), and the remaining 3 are unknown ('?'). The essence of the DP approach here is to repeatedly calculate the number of possible combinations of springs under sets of increasing constraints, which are, in order:<\/p>\n\n