[Day 12] Hot Springs // Advent of Code 2023 (Python)

Hot Springs (via DALL-E 3)

Advent of Code
You finally reach the hot springs! You can see steam rising from secluded areas attached to the primary, ornate…adventofcode.com

---

Part One

You finally reach the hot springs! You can see steam rising from secluded areas attached to the primary, ornate building.

As you turn to enter, the researcher stops you. “Wait — I thought you were looking for the hot springs, weren’t you?” You indicate that this definitely looks like hot springs to you.

“Oh, sorry, common mistake! This is actually the onsen! The hot springs are next door.”

You look in the direction the researcher is pointing and suddenly notice the massive metal helixes towering overhead. “This way!”

It only takes you a few more steps to reach the main gate of the massive fenced-off area containing the springs. You go through the gate and into a small administrative building.

“Hello! What brings you to the hot springs today? Sorry they’re not very hot right now; we’re having a lava shortage at the moment.” You ask about the missing machine parts for Desert Island.

“Oh, all of Gear Island is currently offline! Nothing is being manufactured at the moment, not until we get more lava to heat our forges. And our springs. The springs aren’t very springy unless they’re hot!”

“Say, could you go up and see why the lava stopped flowing? The springs are too cold for normal operation, but we should be able to find one springy enough to launch you up there!”

There’s just one problem — many of the springs have fallen into disrepair, so they’re not actually sure which springs would even be safe to use! Worse yet, their condition records of which springs are damaged (your puzzle input) are also damaged! You’ll need to help them repair the damaged records.

In the giant field just outside, the springs are arranged into rows. For each row, the condition records show every spring and whether it is operational (.) or damaged (#). This is the part of the condition records that is itself damaged; for some springs, it is simply unknown (?) whether the spring is operational or damaged.

However, the engineer that produced the condition records also duplicated some of this information in a different format! After the list of springs for a given row, the size of each contiguous group of damaged springs is listed in the order those groups appear in the row. This list always accounts for every damaged spring, and each number is the entire size of its contiguous group (that is, groups are always separated by at least one operational spring: #### would always be 4, never 2,2).

So, condition records with no unknown spring conditions might look like this:

#.#.### 1,1,3
.#…#…###. 1,1,3
.#.###.#.###### 1,3,1,6
####.#…#… 4,1,1
#…######..#####. 1,6,5
.###.##…# 3,2,1

However, the condition records are partially damaged; some of the springs’ conditions are actually unknown (?). For example:

???.### 1,1,3
.??..??…?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#…#… 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1

Equipped with this information, it is your job to figure out how many different arrangements of operational and broken springs fit the given criteria in each row.

In the first line (???.### 1,1,3), there is exactly one way separate groups of one, one, and three broken springs (in that order) can appear in that row: the first three unknown springs must be broken, then operational, then broken (#.#), making the whole row #.#.###.

The second line is more interesting: .??..??...?##. 1,1,3 could be a total of four different arrangements. The last ? must always be broken (to satisfy the final contiguous group of three broken springs), and each ??must hide exactly one of the two broken springs. (Neither ?? could be both broken springs or they would form a single contiguous group of two; if that were true, the numbers afterward would have been 2,3 instead.) Since each ?? can either be #. or .#, there are four possible arrangements of springs.

The last line is actually consistent with ten different arrangements! Because the first number is 3, the first and second ? must both be . (if either were #, the first number would have to be 4 or higher). However, the remaining run of unknown spring conditions have many different ways they could hold groups of two and one broken springs:

?###???????? 3,2,1
.###.##.#…
.###.##..#..
.###.##…#.
.###.##…#
.###..##.#..
.###..##..#.
.###..##…#
.###…##.#.
.###…##..#
.###…##.#

In this example, the number of possible arrangements for each row is:

???.### 1,1,3 - 1 arrangement

.??..??...?##. 1,1,3 - 4 arrangements

?#?#?#?#?#?#?#? 1,3,1,6 - 1 arrangement

????.#...#... 4,1,1 - 1 arrangement

????.######..#####. 1,6,5 - 4 arrangements

?###???????? 3,2,1 - 10 arrangements

Adding all of the possible arrangement counts together produces a total of 21 arrangements.

For each row, count all of the different arrangements of operational and broken springs that meet the given criteria. What is the sum of those counts?

---

Man! Another permutation and combination problem! It seems like Santa knows what I used to hate during my engineering days! 🤓

So..let’s break the problem down, and try not to get ahead of ourself unlike Day 11!

In an ideal world, our spring records look something like this:

But, since the condition records are partially damaged, some of the springs’ conditions are actually unknown (?):

where `?` denotes the unknown state

💡 So, before we start talking about combinations possible and all, I think we should assume the ideal case, and write a simple validator that validates the spring_state (left) with damaged_spring_record (right). And this case be our base case:

Quick prototying in REPL

Here’s our test case:

And here’s some shabby code just to validate the idea:

Let’s run this, and we can validate that it indeed works!

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_12/hot_springs.py"
✅ OK: #.#.### 1,1,3
✅ OK: .#...#....###. 1,1,3
✅ OK: .#.###.#.###### 1,3,1,6
✅ OK: ####.#...#... 4,1,1
✅ OK: #....######..#####. 1,6,5
✅ OK: .###.##....# 3,2,1

[Done] exited with code=0 in 0.097 seconds

So, now that we know the records are not ideal, but indeed damaged and has a lot of unknowns, we will expand the scope of our thinking.

Well, it’s clear that our validate_spring_record(spring_record) bool function will play a pivotal role to solve the problem as for an example row from damaged records:

We can use our validator function to help verify correct combinations

Now, to get all possible combinations, we need to consider each ? as a place where 2 choices are possible: either . or #. This is a classic problem of combinatorics where each ? represents a binary choice.

In the example row taken above: .??..??…?##. , we have a total of 5 ? present, where each can be replaced by . or # so, mathematically speaking, that yields: 2⁵ combinations == 32.

💭 We can write a function that replaces each ? in the record with either . or #, and then calls itself recursively until all ? have been replaced, using that we can generate all the combinations!

Let’s do a quick script test?

Looks good!

Now, all we need to do is:

1. For each spring_state record, generate all_combinations
2. For each combination in all_combinations, count validate_spring_record(combination) == true
3. sum(for each count of valid combination)
4. ???
5. Profit!

❗️ Disclaimer: I know this is not the most efficient way, but as always, my first approach is to match a solution to a problem and then try to find optimisations! We will probably have to do that as well, as we are currently generating 2^n combinations where the valid combinations will be super low!

So, let’s write 👆code:

And let’s run for our base test case as given in the question:

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_12/hot_springs.py"
Found 1 valid combinations for ???.### 1,1,3
Found 4 valid combinations for .??..??...?##. 1,1,3
Found 1 valid combinations for ?#?#?#?#?#?#?#? 1,3,1,6
Found 1 valid combinations for ????.#...#... 4,1,1
Found 4 valid combinations for ????.######..#####. 1,6,5
Found 10 valid combinations for ?###???????? 3,2,1
✅ OK - test_sum_spring_record_combinations

[Done] exited with code=0 in 0.066 seconds

Yes!!! Now, let’s load up the puzzle input and try to get an answer? 🤞

Ah, well….this might take some time…and…

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_12/hot_springs.py"
Found 4 valid combinations for .???#??????#. 6,1
Found 2 valid combinations for ???##???##?#??#?#..# 1,14,1
Found 2 valid combinations for #??????#????#?###?# 3,1,10,1
Found 13 valid combinations for .???????#????. 1,2,1,2
Found 4 valid combinations for ?##?.??.???.. 3,2,2
Found 1 valid combinations for #.?###?#??. 1,5
Found 12 valid combinations for ?#??#??????????.??.? 7,2,3,1
Found 1 valid combinations for ???###?#.##??? 8,3
...
1000 lines later
...
❗️ Total valid combinations: XXXX

[Done] exited with code=0 in 49.445 seconds

Not bad! An answer in 49.445 seconds shall be considered a win comapred to last few days!

Let’s see if this is the corect answers?

YASS!

Here’s my code till now:

# Day 12: Hot Springs

from enum import Enum

class SpringState(Enum):
    OPERATIONAL = "."
    DAMAGED = "#"
    UNKNOWN = "?"

def generate_spring_record_combinations(spring_record, index=0):
    if index >= len(spring_record):
        return [spring_record]

    if spring_record[index] == SpringState.UNKNOWN.value:
        # replace '?' with '.' and combine results
        with_operational = generate_spring_record_combinations(
            spring_record[:index]
            + SpringState.OPERATIONAL.value
            + spring_record[index + 1 :],
            index + 1,
        )
        # replace '?' with '#' and combine results
        with_damaged = generate_spring_record_combinations(
            spring_record[:index]
            + SpringState.DAMAGED.value
            + spring_record[index + 1 :],
            index + 1,
        )
        return with_operational + with_damaged
    else:
        # continue recursion for next index
        return generate_spring_record_combinations(spring_record, index + 1)

def validate_spring_record(spring_state, damaged_spring_record):
    damaged_spring_record = damaged_spring_record.split(",")
    spring_state = list(spring_state)

    replica_damaged_spring_record = []
    damaged_count = 0
    for spring in spring_state:
        if spring == SpringState.DAMAGED.value:
            damaged_count += 1
        else:
            if damaged_count > 0:
                replica_damaged_spring_record.append(str(damaged_count))
                damaged_count = 0

    if damaged_count > 0:
        replica_damaged_spring_record.append(str(damaged_count))

    return replica_damaged_spring_record == damaged_spring_record

def sum_spring_record_combinations(spring_condition_records):
    total_combinations = 0
    for spring_record in spring_condition_records.splitlines():
        spring_state, damaged_spring_record = spring_record.split()
        combinations = generate_spring_record_combinations(spring_state)
        valid_combinations_length = len(
            [
                c for c in combinations
                if validate_spring_record(c, damaged_spring_record)
            ]
        )
        print(f"Found {valid_combinations_length} valid combinations for {spring_record}")
        total_combinations += valid_combinations_length
    return total_combinations

def part_one():
    with open("day_12/input.txt") as f:
        spring_condition_records = f.read()
    sum = sum_spring_record_combinations(spring_condition_records)
    print(f"❗️ Total valid combinations: {sum}")

def test_sum_spring_record_combinations():
    spring_condition_records = """???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1"""
    sum = sum_spring_record_combinations(spring_condition_records)
    assert sum == 21, f"❌ Expected: 21, Actual: {sum}"
    print("✅ OK - test_sum_spring_record_combinations")

def test_validate_spring_record_ideal():
    ideal_spring_condition_records = """#.#.### 1,1,3
.#...#....###. 1,1,3
.#.###.#.###### 1,3,1,6
####.#...#... 4,1,1
#....######..#####. 1,6,5
.###.##....# 3,2,1
"""
    for spring_record in ideal_spring_condition_records.splitlines():
        spring_state, damaged_spring_record = spring_record.split()
        ok = validate_spring_record(spring_state, damaged_spring_record)
        assert ok, f"❌ Expected: True, Actual: {ok}"
        print(f"✅ OK: {spring_record}")
    print("✅ OK - test_validate_spring_record_ideal")

if __name__ == "__main__":
    # test_validate_spring_record_ideal()
    test_sum_spring_record_combinations()
    part_one()

I am aware that we have a lot of wasted compute that we can optimise here, but let’s move on to part 2 as that usually changes the requirements drastically and then we will combine refactor our code.

---

Part Two

As you look out at the field of springs, you feel like there are way more springs than the condition records list. When you examine the records, you discover that they were actually folded up this whole time!

To unfold the records, on each row, replace the list of spring conditions with five copies of itself (separated by ?) and replace the list of contiguous groups of damaged springs with five copies of itself (separated by ,).

So, this row:

.# 1

Would become:

.#?.#?.#?.#?.# 1,1,1,1,1

The first line of the above example would become:

???.###????.###????.###????.###????.### 1,1,3,1,1,3,1,1,3,1,1,3,1,1,3

In the above example, after unfolding, the number of possible arrangements for some rows is now much larger:

???.### 1,1,3 - 1 arrangement

.??..??...?##. 1,1,3 - 16384 arrangements

?#?#?#?#?#?#?#? 1,3,1,6 - 1 arrangement

????.#...#... 4,1,1 - 16 arrangements

????.######..#####. 1,6,5 - 2500 arrangements

?###???????? 3,2,1 - 506250 arrangements

After unfolding, adding all of the possible arrangement counts together produces 525152.

Unfold your condition records; what is the new sum of possible arrangement counts?

---

Aha! Told you. So, now conviniently, springs were actually folded up this whole time!

To unfold the sequence, we just need to 5x each row of the record, for example:

Clearly, our inefficient code will now not work, as our possible combinations will increase exponentially!

💡Well, one simple way I can see to reduce computations is to:

• just integrate the validation logic directly into the combination generation process

• instead of store all the combinations and then computing length, we can just return the valid number of combinations.

This way, we only generate valid combinations from the start, significantly reducing the number of combinations we need to handle.

Updating code for that, let’s run it!

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_12/hot_springs.py"
✅ OK - test_sum_spring_record_combinations
❗️ Total valid combinations: 7599

[Done] exited with code=0 in 48.915 seconds

And it saved us a grand total of 49.445–48.915 = ~530 ms 😂

Its Something Here You Go GIF - Its something Something Here you go - discover and share GIFs

~530ms

Breaking down the computation, it’s clear that we are spending a lot of time in generating “all” the possible combinations of the record. Since we already have the damaged_spring_record, we should be able to use it to basically just generate correct combinations? Or at the least, do an early return for the all incorrect ones! 🤔

The complexity of this problem lies in correctly interpreting the ‘?’ characters while adhering to the constraints set by the damaged_spring_record.

.

.

.

💡 We need to find a way to prune of our search space early when a rule from damaged_spring_record is violated in our recursive process itself! Let’s write our early return conditions using our record while navigating through all possible combinations in our recursive function:

• If the damaged_spring_record is empty,
  • if any spring is damaged: return 0
  • else, return 1.
• If the spring_state string is empty,
  • if there are no damaged spring records left to process: return 1
  • else, return 0.
• recursively check each spring state and calculate the total number of valid combinations based on whether the current spring is operational, damaged, or unknown.

And since now alot of search space will have repeated calculations, we can use @cache decorator from functools to memoize the results of the recursive function get_valid_spring_record_combinations in an LRU cache with no size limit!

Python does make caching absolutely simple with these nifty OOTB decorators! 🤌

And here, our is_valid_condition would look like:

❗️ Here, _is_valid_condition returns a boolean value that indicates whether the given spring_state and damaged_spring_record meet the following conditions:

1. The first element of damaged_spring_record (which represents the number of damaged springs in the first group) is less than or equal to the length of spring_state. This ensures that there are enough springs in spring_state to account for the first group of damaged springs.
2. All springs in spring_state up to the index equal to the first element of damaged_spring_record are not operational. This is checked by ensuring that the OPERATIONAL value of the SpringState Enum is not found in the substring of spring_state that ends at the index equal to the first element of damaged_spring_record.
3. Either the first element of damaged_spring_record is equal to the length of spring_state (which means that all springs are damaged), or the spring at the index equal to the first element of damaged_spring_record is not damaged. This ensures that there is no damaged spring immediately after the first group of damaged springs.

Let’s run this code for our base test case of part 1:

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_12/hot_springs.py"
✅ OK - test_sum_spring_record_combinations

[Done] exited with code=0 in 0.109 seconds

And puzzle input for part 1:

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_12/hot_springs.py"
❗️ Total valid combinations: XXXX

[Done] exited with code=0 in 0.134 seconds

Wow! We get the correct answer in just 0.134 seconds compare this to our previous brute force approach that took ~49 seconds 😯

Now, let’s also write our base test case for part 2, where all we need to do is, just increase our input per spring_record * 5 :

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_12/hot_springs.py"
✅ OK - test_sum_unfolded_spring_record_combinations

[Done] exited with code=0 in 0.11 seconds

Phew! And now let’s do it for part 2, puzzle input:

* 5 for unfolding ꩜

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_12/hot_springs.py"
❗️ Total valid combinations: XXXXXXXXXXXXX

[Done] exited with code=0 in 0.693 seconds

Yes! Look at that runtime! 🚀

Let’s put this answer in the text box? And…

💥

Here’s our super optimised code till now, I am not doing object oriented for this one! :P

from enum import Enum
from functools import cache

class SpringState(Enum):
    OPERATIONAL = "."
    DAMAGED = "#"
    UNKNOWN = "?"

@cache
def get_valid_spring_record_combinations(spring_state, damaged_spring_record):
    if not damaged_spring_record:
        if SpringState.DAMAGED.value in spring_state:
            return 0
        else:
            return 1

    if not spring_state:
        if not damaged_spring_record:
            return 1
        else:
            return 0

    total_combinations = 0

    # if "." or "?"
    if spring_state[0] in [SpringState.OPERATIONAL.value, SpringState.UNKNOWN.value]:
        total_combinations += get_valid_spring_record_combinations(
            spring_state[1:], damaged_spring_record
        )

    # if "#" or "?"
    if spring_state[0] in [SpringState.DAMAGED.value, SpringState.UNKNOWN.value]:
        if is_valid_condition(spring_state, damaged_spring_record):
            total_combinations += get_valid_spring_record_combinations(
                spring_state[damaged_spring_record[0] + 1 :], damaged_spring_record[1:]
            )

    return total_combinations

def is_valid_condition(spring_state, damaged_spring_record):
    return (
        damaged_spring_record[0] <= len(spring_state)
        and SpringState.OPERATIONAL.value
        not in spring_state[: damaged_spring_record[0]]
        and (
            damaged_spring_record[0] == len(spring_state)
            or spring_state[damaged_spring_record[0]] != SpringState.DAMAGED.value
        )
    )

def sum_spring_record_combinations(spring_condition_records):
    total_combinations = 0
    for spring_record in spring_condition_records.splitlines():
        spring_state, damaged_spring_record = spring_record.split()
        damaged_spring_record = tuple(map(int, damaged_spring_record.split(",")))
        total_combinations += get_valid_spring_record_combinations(
            spring_state, damaged_spring_record
        )

    return total_combinations

def part_one():
    with open("day_12/input.txt") as f:
        spring_condition_records = f.read()
    sum = sum_spring_record_combinations(spring_condition_records)
    print(f"❗️ Total valid combinations: {sum}")

def sum_spring_record_combinations_unfold(spring_condition_records):
    total_combinations = 0
    for spring_record in spring_condition_records.splitlines():
        spring_state, damaged_spring_record = spring_record.split()
        damaged_spring_record = tuple(map(int, damaged_spring_record.split(",")))
        spring_state = "?".join([spring_state] * 5)  # unfolding
        damaged_spring_record = damaged_spring_record * 5  # unfolding
        total_combinations += get_valid_spring_record_combinations(
            spring_state, damaged_spring_record
        )

    return total_combinations

def part_two():
    with open("day_12/input.txt") as f:
        spring_condition_records = f.read()
    sum = sum_spring_record_combinations_unfold(spring_condition_records)
    print(f"❗️ Total valid combinations: {sum}")

def test_sum_spring_record_combinations():
    spring_condition_records = """???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1"""
    sum = sum_spring_record_combinations(spring_condition_records)
    assert sum == 21, f"❌ Expected: 21, Actual: {sum}"
    print("✅ OK - test_sum_spring_record_combinations")

def test_sum_unfolded_spring_record_combinations():
    spring_condition_records = """???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1"""
    sum = sum_spring_record_combinations_unfold(spring_condition_records)
    assert sum == 525152, f"❌ Expected: 525152, Actual: {sum}"
    print("✅ OK - test_sum_unfolded_spring_record_combinations")

if __name__ == "__main__":
    test_sum_spring_record_combinations()
    part_one()

    test_sum_unfolded_spring_record_combinations()
    part_two()

---

Man! I am learning so much with #AdventOfCode2023, it’s beautiful that I am getting to revisit a lot of my engineering days concepts that I don’t get to use in my day to day work while building CRUD apps! 🤓

Onto the next day then?!

---

p.s: I am deliberating not adding answers here so you can actually spend some time trying to understand how we solved the problem!

Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇

GitHub - jatinkrmalik/advent-of-code-2023: Well, here’s my attempt to solve all 25 problems of…
Well, here’s my attempt to solve all 25 problems of Advent of Code 2023 with Python! 🎄 - GitHub …github.com