Struct andys_morning_stroll::GraphPathCounter

pub struct GraphPathCounter {
    pub cells: RefCell<HashMap<Coord, usize>>,
    /* private fields */
}

Stores a representation of the underlying graph, tracking how many paths have reached each node at current time step self.step.

Calling next steps the KitchenFloor steps the graph representation forward by: a) introducing any new nodes to the graph which haven’t don’t already exist from previous steps b) iterating every node in the graph and setting its new value to the be the sum of the values in the surrounding nodes from the previous step (but not counting any contribution from the origin, because any paths which reached this on the previous step would have terminated there).

Fields

cells: RefCell<HashMap<Coord, usize>>

Tracks the total number of paths which can arrive at a given coord by a certain time step.

Implementations

impl GraphPathCounter

pub fn new() -> Self

Create a new graph counter.

pub fn next(&mut self)

Step the internal graph representation forward.

In summary, this function does works by: a) introducing any new nodes to the graph which haven’t don’t already exist from previous steps b) iterating every node in the graph and setting its new value to the be the sum of the values in the surrounding nodes from the previous step (but not counting any contribution from the origin, because any paths which reached this on the previous step would have terminated there).

pub fn calculate(&mut self, steps: u32)

Run the analysis for a given number of steps.

This function tracks how many paths return to the origin (0, 0) in total across all the steps. We need to be careful to upscale each such number by a factor of $3^k$ where $k$ is the number of remaining steps. This accounts for the fact that we stop counting the paths once they have returned home. If we kept counting them each one would diverge into $3^k$ paths over the remaining $k$ steps. We need to apportion the probability mass correctly in order to divide by $3^{20}$ total paths at the end.