Advent of Code 2023, Day 12
❄️ Back to Advent of Code 2023 solutions homepage ❄️
# Imports
from aoc23.utils import read_input
from functools import cache
input_12 = read_input(12)
Part 1
In part 1 of the day 12 puzzle, we are given a collection of arrays, representing the operational states of rows of springs. Each array is a string of varying length, consisting of a mixture of three different characters, each representing the state of the spring:
.= operational spring#= damaged spring?= spring with unknown status.
Also provided with each row of spring states is a list of integers; this represents the lengths of each contiguous group of damaged springs. Looking at a few examples from the puzzle input will help clarify this:
split_input = [line.split() for line in input_12]
for line in split_input[:5]:
print(line)
['..???.??.?', '1,1,1']
['?#?##???.????', '2,5,1,1']
['?#??????##?', '1,1,2']
['?#.#?#??#???', '1,7,1']
['?#???#?#??.#.###.?', '3,1,3,1,3,1']
For example, the first line above represents a row of 10 springs: the first 2 are operational, the next 3 are unknown, the next is operational, and so on. The list of integers 1,1,1 indicates that is row contains 3 damaged springs, all separated by at least one operational one. So, a valid configuration for this row would be ..#...#..#, along with various others. The first part of the puzzle is to find, for each of the rows in the input, the number of configurations of operational and broken springs that are compatible with both the operational state array and the contiguous integer list.
The strategy for solving this is to consider each valid position for the first integer in turn, and then use recursion to reduce to smaller but similar problem. Here is the function used to do this:
@cache
def num_possible_arrays(string: str, nums: str, base_level=True) -> int:
num = 0
# Split the nums into a list of ints
# Use of a string argument `nums` to allow caching
nums = [int(x) for x in nums.split(',')] if nums else []
# End of a recursion - empty contiguous integer list
# So return 1 if there are no further `#` characters
# in remaining string (valid solution), and return 0
# if there are `#` characters (invalid solution)
if nums == []:
return not any([c == '#' for c in string])
# The ends of the string can be fiddly to deal with.
# Padding with `.` characters does not affect the solution
# but avoids special cases for ends of original string
if base_level:
string = '.' + string + nums[-1]*'.'
# Loop from nidex 1: skip first character, as there must be
# a gap between contiguous blocks. On first iteration,
# there is an extra '.' character prepended
# Loop until len(string) - nums[0]: block of length nums[0]
# must fit into remaining string for a valid solution
for i in range(1, len(string) - nums[0]):
char = string[i]
if char in ['#', '?']:
# Conditions to check if block can start here
# First condition: all nums[0] next characters are '#' or '?'
condition_1 = all([c in ['#', '?'] for c in string[i:i+nums[0]]])
# Second condition: the character after the next nums[0]
# characters cannot be a '#' (must be a gap between blocks)
condition_2 = string[i+nums[0]] != '#'
# Third condition: Previous character cannot be a '#'
# for a similar reason
condition_3 = string[i-1] != '#'
if all([condition_1, condition_2, condition_3]):
# Convert back to string
next_nums = ','.join([str(x) for x in nums[1:]])
# Recurse on remaining string after block, with one fewer
# remaining block to consider
num += num_possible_arrays(string[i+nums[0]:], next_nums, False)
# Once a '#' character is hit, the next block must start here
if char == '#':
break
return num
As you can probably notice, this function was quite fiddly to design, with various cases and pattern variants to consider. The following test cases helped to identify errors for particular patterns and special cases: they are a mixture of small, simple arrays that are easy to debug, and longer examples provided by the puzzle designer as test cases.
assert num_possible_arrays('#', '1') == 1
assert num_possible_arrays('##', '2') == 1
assert num_possible_arrays('#?', '2') == 1
assert num_possible_arrays('?#', '2') == 1
assert num_possible_arrays('.#', '1') == 1
assert num_possible_arrays('.?', '1') == 1
assert num_possible_arrays('#.', '1') == 1
assert num_possible_arrays('?.', '1') == 1
assert num_possible_arrays('#?', '1') == 1
assert num_possible_arrays('##?', '2') == 1
assert num_possible_arrays('?#?', '2') == 2
assert num_possible_arrays('???', '2') == 2
assert num_possible_arrays('?#', '1') == 1
assert num_possible_arrays('??#', '1') == 1
assert num_possible_arrays('??#', '2') == 1
assert num_possible_arrays('???', '1,1') == 1
assert num_possible_arrays('???.###', '1,1,3') == 1
assert num_possible_arrays('..??..??...?##', '1,1,3') == 4
assert num_possible_arrays('?#?#?#?#?#?#?#?', '1,3,1,6') == 1
assert num_possible_arrays('????.#..#...', '4,1,1') == 1
assert num_possible_arrays('????.######..#####.', '1,6,5') == 4
assert num_possible_arrays('?###????????', '3,2,1') == 10
print('Success!')
Success!
Now that this works as expected, the total sum of combinations can be computed for all arrays:
sum([num_possible_arrays(array, nums) for array, nums in split_input])
8419
So the answer to part 1 is: 8419.
Part 2
In the second part, we must repeat the patterns 5 times, with additional ? characters sandwiched between the copies of the original array; the contiguous integer list is likewise repeated
def unfold_input(array: str, nums: str, factor: int = 5) -> tuple[str]:
arrays = factor*[array]
nums = factor*[nums]
return ('?'.join(arrays), ','.join(nums))
To illustrate this, take a simple example:
unfold_input('##.##', '2,2')
('##.##?##.##?##.##?##.##?##.##', '2,2,2,2,2,2,2,2,2,2')
Thankfully, the code written earlier should also be valid here, when applied to the tranformed arrays; this can be tested on the provided examples to be sure:
assert num_possible_arrays(*unfold_input('..??..??...?##','1,1,3')) == 16384
assert num_possible_arrays(*unfold_input('?#?#?#?#?#?#?#?', '1,3,1,6')) == 1
assert num_possible_arrays(*unfold_input('????.#..#...', '4,1,1')) == 16
assert num_possible_arrays(*unfold_input('????.######..#####.', '1,6,5')) == 2500
assert num_possible_arrays(*unfold_input('?###????????', '3,2,1')) == 506250
Computing the number of combinations for these larger arrays is computationally expensive, and so attempting to run the function num_possible_arrays across all the input rows would not be feasible. Thankfully, there is a simple way of speeding up the computation, that has already been included in the earlier implementation: the function is wrapped with a cache decorator. This will make a cached copy of the result computed for a particular set of inputs (string, nums, base_level), so that the value can be looked up in future when these arguments reoccur. This is particularly useful in recursion problems, where large inputs are broken down into smaller ones which end up being evaluated many times.
For this puzzle, I was unable to complete even the first row of the input file in 2 minutes of wall-clock time without caching; with caching enabled, all 1000 rows of the input file completed in 3 seconds:
combinations = 0
for array, nums in split_input:
combinations += num_possible_arrays(*unfold_input(array, nums))
combinations
160500973317706
Looking at the cache info for the function, we can see that more than 166,000 function values have been computed and cached, saving many hundreds of thousands of function calls:
num_possible_arrays.cache_info()
CacheInfo(hits=737523, misses=167677, maxsize=None, currsize=167677)
And so the answer to part 2 of the puzzle is: 160500973317706.
Comments