Advent of Code 2023 Day 12

Day 12: Hot Springs

https://adventofcode.com/2023/day/12

You arrive at the hot springs.

They’re regular springs now, because they’re not so hot -a characteristic that is quite important for hot springs-. It’s because the lava stopped flowing, you should go take a look why.

You should be able to find a spring that is springy enough to launch you up to the place lava comes from here.

But they have fallen into disrepair, many of them are damaged. You get a map of the hotsprings condition, per hotspring it lists if it is;

# damaged
. operational

The map itself is also damaged, causing a bunch of hot springs to have an unknown condition:

? unknown

Luckily, the elf with you helps you with a different format that lists the size of contiguous groups of damaged springs for every line.

This list always accounts for every damaged spring. 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).

An example of an undamaged input would look like this:

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

An example of the real, damaged input looks like this:

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

Parsing

I represented every record as a struct with a list of springs and a list of counts:

struct Record {
    springs: Vec<Spring>,
    counts: Vec<usize>,
}

I represented each spring as an enum variant:

enum Spring {
    Unknown,
    Damaged,
    Operational,
}

The parsing function returns a list of Records:

fn parse(input: &str) -> impl Iterator<Item = Record> + '_ {
    input.lines().map(|line| {
        let (springs, counts) = line.split_once(' ').unwrap();
        let springs = springs
            .chars()
            .map(|c| match c {
                '.' => Spring::Operational,
                '#' => Spring::Damaged,
                '?' => Spring::Unknown,
                _ => panic!("at the disco"),
            })
            .collect();
        let counts = counts.split(',').map(|s| s.parse().unwrap()).collect();

        Record { springs, counts }
    })
}

Part 1

It is your job to figure out how many different arrangements of operational and broken springs fit the given criteria in each row.

The question asks for the sum of valid arrangements for each line in your input.

some skeleton/pseudo-code:

parse(input).map(/* turn record into a count of valid arrangements */).sum()

Helpers

To check the amount of valid arrangements for a record, I used recursion.

If the argument to the function (a record) has an unknown spring in its list of springs, I replace it:

As a damaged spring
As an operational spring

For those 2 options, I calculate the amount of valid arrangements and sum them.

If the argument to the function (a record) has NO unknown springs in its list of springs, I check its validity. If it’s valid, it has 1 valid arrangement (because there are no unknown springs left), if it’s invalid, it has 0.

impl Record {
    fn valid_arrangements(&self) -> usize {
        if let Some(index) = self
            .springs
            .iter()
            .position(|spring| *spring == Spring::Unknown)
        {
            // treat unknown spring as damaged
            let mut as_damaged_spring = self.springs.clone();
            as_damaged_spring[index] = Spring::Damaged;
            let as_damaged = Record {
                springs: as_damaged_spring,
                counts: self.counts.to_vec(),
            };

            // treat unknown spring as operational
            let mut as_operational_spring = self.springs.clone();
            as_operational_spring[index] = Spring::Operational;
            let as_operational = Record {
                springs: as_operational_spring,
                counts: self.counts.to_vec(),
            };

            as_damaged.valid_arrangements() + as_operational.valid_arrangements()
        } else {
            if self.is_valid() {
                1
            } else {
                0
            }
        }
    }
}

This helper checks if an arrangement of springs (one with no unknown springs in it) is valid by calculating the list of counts that arrangement would have. If the calculated counts match the given counts completely, it was a valid arrangement.

impl Record {
    fn is_valid(&self) -> bool {
        self.springs
            .iter()
            .group_by(|item| *item)
            .into_iter()
            .filter_map(|(key, group)| {
                if *key == Spring::Damaged {
                    Some(group.count())
                } else {
                    None
                }
            })
            .eq(self.counts.iter().copied())
    }
}

Putting it all together, the pseudocode works perfectly.

Code

use itertools::Itertools;

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
enum Spring {
    Unknown,
    Damaged,
    Operational,
}

struct Record {
    springs: Vec<Spring>,
    counts: Vec<usize>,
}

impl Record {
    fn is_valid(&self) -> bool {
        self.springs
            .iter()
            .group_by(|item| *item)
            .into_iter()
            .filter_map(|(key, group)| {
                if *key == Spring::Damaged {
                    Some(group.count())
                } else {
                    None
                }
            })
            .eq(self.counts.iter().copied())
    }

    fn valid_arrangements(&self) -> usize {
        if let Some(index) = self
            .springs
            .iter()
            .position(|spring| *spring == Spring::Unknown)
        {
            // treat unknown spring as damaged
            let mut as_damaged_spring = self.springs.clone();
            as_damaged_spring[index] = Spring::Damaged;
            let as_damaged = Record {
                springs: as_damaged_spring,
                counts: self.counts.to_vec(),
            };

            // treat unknown spring as operational
            let mut as_operational_spring = self.springs.clone();
            as_operational_spring[index] = Spring::Operational;
            let as_operational = Record {
                springs: as_operational_spring,
                counts: self.counts.to_vec(),
            };

            as_damaged.valid_arrangements() + as_operational.valid_arrangements()
        } else {
            if self.is_valid() {
                1
            } else {
                0
            }
        }
    }
}

fn parse(input: &str) -> impl Iterator<Item = Record> + '_ {
    input.lines().map(|line| {
        let (springs, counts) = line.split_once(' ').unwrap();
        let springs = springs
            .chars()
            .map(|c| match c {
                '.' => Spring::Operational,
                '#' => Spring::Damaged,
                '?' => Spring::Unknown,
                _ => panic!("at the disco"),
            })
            .collect();
        let counts = counts.split(',').map(|s| s.parse().unwrap()).collect();

        Record { springs, counts }
    })
}

pub fn part_1(input: &str) -> usize {
    parse(input).map(|record| record.valid_arrangements()).sum()
}

Part 2

Turns out you were holding it wrong.

The map was folded up, it is much larger.

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

This makes the runtime of the code above too large to complete in a reasonable time. I tried doing what’s called a pro gamer move and throw some memoization on it, but alas, I couldn’t get it to work before I had to do other stuff.

I fiddled a bit with some code from GitHub user crazytieguy. It completes much, much faster.

The part that was nearly identical, was the unfolding of the map:

parse(input)
    .map(|(mut springs, mut counts)| {
        springs = springs
            .iter()
            .copied()
            .chain([Spring::Unknown])
            .cycle()
            .take(springs.len() * 5 + 4)
            .collect();
        counts = counts
            .iter()
            .copied()
            .cycle()
            .take(counts.len() * 5)
            .collect();

        (springs, counts)
    })

Here it is with some minor changes.

Code

#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
enum Spring {
    Unknown,
    Damaged,
    Operational,
}

fn parse(input: &str) -> impl Iterator<Item = (Vec<Spring>, Vec<usize>)> + '_ {
    input.lines().map(|line| {
        let (springs, counts) = line.split_once(' ').unwrap();
        let springs: Vec<Spring> = springs
            .chars()
            .map(|c| match c {
                '.' => Spring::Operational,
                '#' => Spring::Damaged,
                '?' => Spring::Unknown,
                _ => panic!("at the disco"),
            })
            .collect();
        let counts: Vec<usize> = counts.split(',').filter_map(|s| s.parse().ok()).collect();

        (springs, counts)
    })
}

fn count_possible_arangements(mut springs: Vec<Spring>, counts: Vec<usize>) -> u64 {
    // to make the Damaged recursion case simpler
    springs.push(Spring::Operational);
    let mut cache = vec![vec![None; springs.len()]; counts.len()];
    count_possible_arangements_inner(&springs, &counts, &mut cache)
}

fn count_possible_arangements_inner(
    springs: &[Spring],
    counts: &[usize],
    cache: &mut [Vec<Option<u64>>],
) -> u64 {
    if counts.is_empty() {
        return if springs.contains(&Spring::Damaged) {
            // Too many previous unknowns were counted as damaged
            0
        } else {
            // All remaining unknowns are operational
            1
        };
    }
    if springs.len() < counts.iter().sum::<usize>() + counts.len() {
        // Not enough space for remaining numbers
        return 0;
    }
    if let Some(cached) = cache[counts.len() - 1][springs.len() - 1] {
        return cached;
    }
    let mut arangements = 0;
    if springs[0] != Spring::Damaged {
        // Assume operational
        arangements += count_possible_arangements_inner(&springs[1..], counts, cache);
    }
    let next_group_size = counts[0];
    if !springs[..next_group_size].contains(&Spring::Operational)
        && springs[next_group_size] != Spring::Damaged
    {
        // Assume damaged
        arangements +=
            count_possible_arangements_inner(&springs[next_group_size + 1..], &counts[1..], cache);
    }
    cache[counts.len() - 1][springs.len() - 1] = Some(arangements);
    arangements
}

pub fn part_2(input: &str) -> u64 {
    parse(input)
        .map(|(mut springs, mut counts)| {
            springs = springs
                .iter()
                .copied()
                .chain([Spring::Unknown])
                .cycle()
                .take(springs.len() * 5 + 4)
                .collect();
            counts = counts
                .iter()
                .copied()
                .cycle()
                .take(counts.len() * 5)
                .collect();

            count_possible_arangements(springs, counts)
        })
        .sum()
}

Final code

#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
enum Spring {
    Unknown,
    Damaged,
    Operational,
}

fn parse(input: &str) -> impl Iterator<Item = (Vec<Spring>, Vec<usize>)> + '_ {
    input.lines().map(|line| {
        let (springs, counts) = line.split_once(' ').unwrap();
        let springs: Vec<Spring> = springs
            .chars()
            .map(|c| match c {
                '.' => Spring::Operational,
                '#' => Spring::Damaged,
                '?' => Spring::Unknown,
                _ => panic!("at the disco"),
            })
            .collect();
        let counts: Vec<usize> = counts.split(',').filter_map(|s| s.parse().ok()).collect();

        (springs, counts)
    })
}

pub fn part_1(input: &str) -> u64 {
    parse(input)
        .map(|(springs, counts)| count_possible_arangements(springs, counts))
        .sum()
}

pub fn part_2(input: &str) -> u64 {
    parse(input)
        .map(|(mut springs, mut counts)| {
            springs = springs
                .iter()
                .copied()
                .chain([Spring::Unknown])
                .cycle()
                .take(springs.len() * 5 + 4)
                .collect();
            counts = counts
                .iter()
                .copied()
                .cycle()
                .take(counts.len() * 5)
                .collect();

            count_possible_arangements(springs, counts)
        })
        .sum()
}

fn count_possible_arangements(mut springs: Vec<Spring>, counts: Vec<usize>) -> u64 {
    // to make the Damaged recursion case simpler
    springs.push(Spring::Operational);
    let mut cache = vec![vec![None; springs.len()]; counts.len()];
    count_possible_arangements_inner(&springs, &counts, &mut cache)
}

fn count_possible_arangements_inner(
    springs: &[Spring],
    counts: &[usize],
    cache: &mut [Vec<Option<u64>>],
) -> u64 {
    if counts.is_empty() {
        return if springs.contains(&Spring::Damaged) {
            // Too many previous unknowns were counted as damaged
            0
        } else {
            // All remaining unknowns are operational
            1
        };
    }
    if springs.len() < counts.iter().sum::<usize>() + counts.len() {
        // Not enough space for remaining numbers
        return 0;
    }
    if let Some(cached) = cache[counts.len() - 1][springs.len() - 1] {
        return cached;
    }
    let mut arangements = 0;
    if springs[0] != Spring::Damaged {
        // Assume operational
        arangements += count_possible_arangements_inner(&springs[1..], counts, cache);
    }
    let next_group_size = counts[0];
    if !springs[..next_group_size].contains(&Spring::Operational)
        && springs[next_group_size] != Spring::Damaged
    {
        // Assume damaged
        arangements +=
            count_possible_arangements_inner(&springs[next_group_size + 1..], &counts[1..], cache);
    }
    cache[counts.len() - 1][springs.len() - 1] = Some(arangements);
    arangements
}

Date

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 12

Day 12: Hot Springs

Parsing

Part 1

Helpers

Code

Part 2

Code

Final code