Day 12 Notes

[blairfrandeen]

I hear this is a BFS problem. I have some idea of how to implement BFS, so I'll give it a try without any assistence and see how far I get.

The first thing I'll do is take a detour and see if I can generalize the Grid struct that I wrote for day 8. So far I've got ~50 lines of code copied, including tests, with only one line changed.

Day 8

let mut l: Vec<u8> = line
    .chars()
    .map(|c| c.to_digit(10).unwrap() as u8)
    .collect();

Day 12:

let mut l: Vec<u8> = line.chars().map(|c| c as u8).collect();

A couple ways I think I could approach this: 1) Have the Grid::build function take a closure argument or a function. 2) Consider having Grid<T> (is that a thing?) where it can be a grid of any type--I feel dubious about this. 3) Just update the day 8 implementation to match day 12 -- won't day 8 still work? Currently the grid test fails as follows:

thread 'day_12::tests::test_grid' panicked at 'assertion failed: `(left == right)`
  left: `Grid { num_rows: 2, num_cols: 5, data: [49, 50, 51, 52, 53, 54, 55, 56, 57, 48] }`,
 right: `Grid { num_rows: 2, num_cols: 5, data: [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] }`', src/day_12.rs:75:9

It seems that all that matters for day 8 is the relative values/tree heights; not absolutes. 4) Use one or the other as the basic grid, and run a conversion function on it once initialized.

I'm going to experiment with 3) first and see if day 8 will still run. If so, that seems like a clean path.

Seems to run and get the right answer, so 3) is where I'll start.

[blairfrandeen]

Started on day 12, going to give it up for the night and pretend like I'm sleeping this week.

I'm noticing that putting the Grid struct into common.rs means that it will need some better safety features. Specifically, the get function needs to return either a Result type or an Option -- I am not sure which is more appropriate, I'm erring towards option. Specifically, if I'm checking a value in the row above and I'm already in the top row, it needs to return None so I know not to do anything with it.

[blairfrandeen]

Re-thinking my previous comment. I implemented the Grid::get() and Grid::loc() functions to return Option<u8> but I think it would be more appropriate for them to return Result<u8> instead. I need to look at how to properly generate errors; in python this would be an IndexError, is there an equivalent in Rust? I'll go back and check the book.

[blairfrandeen]

Changed Grid functions to return errors. Not sure if I'm happy with it. Should they return the string slices they currently return, or a more formal error types? Further reading:

std::error::Error trait documentation Recoverable Errors with Result

Now off to my "real" job...

[blairfrandeen]

Added Grid::Error enum, although I"m still not sure this is the "right" way to handle it. Day 8 working with that framework for now, and tests are working.

Issue I'm having right now on this one is that I'm trying to write a neighbors() function for day 12. This function takes two arguments, a Grid object and an index. The expected outcome is that the function returns a vector of indices of grid.data that are neighbors above/below/left/right.

The way I'm trying to write it is like this:

fn neighbors(grid: Grid, index: usize) -> Vec<usize> {
    let mut neighbors: Vec<usize> = Vec::new();
    let (r, c) = grid.loc(index).expect("Call neighbors on invalid index.");
    let deltas = vec![(0, 1), (1, 0), (-1, 0), (0, -1)];
    for delta in deltas {
        if let Ok(location) = grid.ind(r + delta.0, c + delta.1) {
            neighbors.push(location)
        }
    }
    neighbors
}

The problem with this approach happens when the loop gets to the second half of the deltas vector:

error[E0277]: the trait bound `usize: Neg` is not satisfied
  --> src/day_12.rs:25:52
   |
25 |     let deltas = vec![(0, 1), (1, 0), (-1, 0), (0, -1)];
   |                                                    ^^ the trait `Neg` is not implemented for `usize`

It's apparent to the compiler that we could get a negative overflow of a usize by calculating 0 - 1. I had wanted to actually create an error here, but it seems like the neighbors function needs to catch this with an if row == 0 { ... }. I would like the neighbors function to be extensible to include diagonal neighbors, which makes the idea of iterating through a tuple of directions even more appealing; it's inevitable I'll need it eventually.

One of the many things I could get away with in Python that I need to re-think here in Rust.

[blairfrandeen]

I finished this one, and I'm not a big fan of how I did it. I ended up first trying to implement breadth-first-search from memory, and I feel like I got pretty close. However, I ended up following someone else's solution and getting horribly stuck.

The main problem I got into was that I my check for next available move was incorrect, due to not fully reading the puzzle instructions. I assumed incorrectly that we could only move one elevation up or down, when in fact we can go down as far as we please. This led to a lot of roundabouts and a lot of extra unit tests for impl Grid, after laying awake at night wondering where my off-by-one errors might be.

The second part of this was relatively simple, but took maybe a bit longer to run that I thought it should. I generally struggle with trying to go fast and get the puzzles done vs. going deep into a rabbit hole and learning whatever there is to learn about a certain topic. Regardless, I'm getting better at Rust and picking up more of the syntax. I'm starting to fight with the compiler slightly less, and I'm starting to anticipate problems that might arise.

I think I'm unnecessarily scared of some of Rusts' more advanced features, and I also find that I've come to an attitude of "just get it done" rather than to go deep and try to optimize things. I find this attitude to be different from some of my initial inspiration to do programming work.