Function aoc::year2022::day08::part2

pub fn part2(input: &(usize, Vec<i8>)) -> u64

Calculate the distance visible in each direction by using 10 rolling maximum values for each height packed into a single u64.

Part 2 is similar to part 1, but instead of keeping a single maximum for each direction, we need to keep an array of 10 values, one for each possible height.

For each tree its score is the current value at the same index as its height. Then we increment the value of previously seen trees greater than the current height by one and reset the values of trees less than or equal than the current height to one.

We skip processing the edge and corner trees. Strictly speaking their score should be zero, but as the maximum value will always be greater than or equal to one, it’s fine to leave them bulk initialized to one.

Using the fourth row of the sample and going left to right:

Tree	Scenic Array	Score
3	[1, 1, 1, (1), 1, 1, 1, 1, 1, 1]	1
5	[1, 1, 1, 1, 2, (2), 2, 2, 2, 2]	2
4	[1, 1, 1, 1, (1), 1, 3, 3, 3, 3]	1

Instead of using an array and iterating over it to update the values, we can achieve the same result much faster by packing the ten values into a single u64 in blocks of 6 bits. 6 bits gives a maximum value of 2^6 = 64 that’s a bit of a gamble. It’s less than the maximum possible value of 98 that could be theoretically encountered but should work for most inputs.

To obtain the current value we right shift by the current height times 6 (this is why we multiplied by 6 in the parse function) and mask only the least significant 6 bits.

To update the next value, we first use MASK left shifted to zero out all bits less than or equal to the current height then add 1 to all values in parallel using the ONES pattern.

For example going from 3 to 5 in the sample above:

  scenic:        000001_000001_000001_000001_000001_000001_000001_000001_000001_000001
  mask:          111111_111111_111111_111111_111111_111111_000000_000000_000000_000000
  scenic & mask: 000001_000001_000001_000001_000001_000001_000000_000000_000000_000000
  scenic + ones: 000010_000010_000010_000010_000010_000010_000001_000001_000001_000001