2022 Day 8

[blairfrandeen]

How best to create a grid data structure? Some options:

1) Grid Crate - Seems to be the right tool for the job in that it's only useful for this type of problem -- not good for matrix algebra or grids of more than 2 dimensions. 2) Just use Vec<Vec<u8>> - Seems like a lot to have to implement. 3) Make a Point struct, and have that be the key to a HashMap 4) Implement a 1-D Vec<u8> within a struct and write a struct and some accessor functions. I think this would be a good exercise, as I'm still struggling with having the syntax for struct methods at my fingertips.

I'll go ahead with 4) and see how I do.

[blairfrandeen]

parse_input function is working, but I don't understand what's going on with mutability.

Currently function reads:

fn parse_input(contents: String) -> Vec<u8> {
    let mut grid: Vec<u8> = Vec::new(); 
    for line in contents.lines() {
        let mut l: Vec<u8> = line // why does this need to be mutable?
            .chars()
            .map(|c| c.to_digit(10).unwrap() as u8)
            .collect();
        grid.append(&mut l)
    }
    grid
}

If I try to compile this code with l as immutable, it suggests a mutable borrow for the grid.append() function. Per the Documentation:

Moves all the elements of other into self, leaving other empty. So it's modifying l as it goes. I think what I want to be doing is copying l, or more precisely I want grid to consume l as it goes. Seems like a job for nom.

[blairfrandeen]

Realizing that my parse_input function should really be returning the Grid structure, and not just a vector of u8s. This way I only have to go through the input once to find the number of rows & columns.

[blairfrandeen]

This day is complete, but I'm not super happy with my code. Generally a lot of repetitiveness, and I moved away from my regular FP tendencies.

I think it deserves a bit of a re-write before I move on. At the very least main() can be rewritten to be a couple of mappings. I'm not sure how I can shorten up the scenic_score() and is_visible() functions--a reading of other's solutions would help here.

[blairfrandeen]

Another worthy enhancement here is rewriting the parse_input() function to be Grid::from() rather than a separate function that returns a Grid.

[blairfrandeen]

Putting a pin in this one for the night. I made a build function for Grid, and I rewrote main() to use FP techniques.

Other improvements to go:

• [ ] Rewrite Grid::build() to use nom parsing techniques
• [ ] Find cleaner way to write scenic_score() and is_visible()

[blairfrandeen]

I took a crack at rewriting the Grid::build command, and I was surprised that I couldn't get it to go faster. My original build function:

    pub fn build(contents: String) -> Grid {
        let mut data: Vec<u8> = Vec::new();
        let mut num_rows: usize = 0;
        let mut num_cols: usize = 0;
        for line in contents.lines() {
            let mut l: Vec<u8> = line.chars().map(|c| c as u8).collect();
            if num_cols != 0 && line.len() != num_cols {
                panic!("Unequal number of columns in input!")
            }
            num_cols = line.len();
            data.append(&mut l);
            num_rows += 1;
        }
        Grid {
            num_rows,
            num_cols,
            data,
        }
    }
}

What I don't like about this is that it creates a new mutable l for every line, and then it appends that to the data vector after it checks that the line was the same as all previous lines. It seems as if this could be quicker. I wrote a new version (not within impl Grid, but shouldn't matter) that used more of a functional approach, and granted without the check that all rows are the same length:

fn b2(input: &str) -> Grid {
    let mut num_rows: usize = 0;
    let data: Vec<u8> = input
        .chars()
        .map(|item| item as u8)
        .filter(|c| {
            num_rows += 1;
            *c != '\n' as u8
        })
        .collect();
    let num_cols = data.len() / num_rows;
    // println!("Rows: {n_rows} Cols: {n_cols} \n{:?}", v);
    Grid {
        num_rows,
        num_cols,
        data,
    }
}

In the process of this I learned to add some benchmarking to my tests.

    #[bench]
    fn bench_grid(b: &mut Bencher) {
        b.iter(|| Grid::build(include_str!("../inputs/2022.8").to_string()));
    }

    #[bench]
    fn bench_grid2(b: &mut Bencher) {
        b.iter(|| b2(include_str!("../inputs/2022.8")));
    }

I was surprised to find the original version to still be quicker

test common::tests::bench_grid  ... bench:      18,086 ns/iter (+/- 449)
test common::tests::bench_grid2 ... bench:      26,735 ns/iter (+/- 284)

I'm not sure I'm ready to fully investigate this using profiling techniques, although it certainly points at something to be learned. I wonder if using an owned string in the first iteration has something to do with it? No, changing b2 to take a String instead of &str made it 3 us slower, so it isn't that.

What if I switch the order of map and filter? Ahah! Down to 12.5 us. The line of interest:

    let data: Vec<u8> = input
        .chars()
        .filter(|c| {
            num_rows += 1;
            *c != '\n'
        })
        .map(|item| item as u8)
        .collect();

Of course it's not correct -- it thinks there are 20 rows & zero columns. Let me try rewriting using FP techniques.

    let data: Vec<u8> = input
        .chars()
        .filter(|c| match *c == '\n' {
            true => {
                num_rows += 1;
                false
            }
            false => true,
        })
        .map(|item| item as u8)
        .collect();

Works? Check. Faster? Check. Easy to read? Fuck no. There's got to be a cleaner way. Here's the way I think it should work:

    let data: Vec<u8> = input
        .lines()
        .map(|l| {
            num_rows += 1;
            l.chars().map(|c| c as u8)
        })
        .collect();

This gives the error:

error[E0277]: a value of type `Vec<u8>` cannot be built from an iterator over elements of type `std::iter::Map<Chars<'_>, [closure@src/common.rs:100:27: 100:30]>`
   --> src/common.rs:96:25
    |
96  |       let data: Vec<u8> = input
    |  _________________________^
97  | |         .lines()
98  | |         .map(|l| {
99  | |             num_rows += 1;
100 | |             l.chars().map(|c| c as u8)
101 | |         })
    | |__________^ value of type `Vec<u8>` cannot be built from `std::iter::Iterator<Item=std::iter::Map<Chars<'_>, [closure@src/common.rs:100:27: 100:30]>>`
102 |           .collect();
    |            ------- required by a bound introduced by this call
    |
    = help: the trait `FromIterator<std::iter::Map<Chars<'_>, [closure@src/common.rs:100:27: 100:30]>>` is not implemented for `Vec<u8>`
    = help: the trait `FromIterator<T>` is implemented for `Vec<T>`
note: required by a bound in `collect`

To be continued.

[blairfrandeen]

The error above is still pretty cryptic to me; the best I can tell here is that in the first map of lines() it expects a vector with however many lines I have, and then the second map of lines().chars() gives a new number of elements that the original map() wasn't expecting.

I rewrote the faster version that worked to be this slightly-less-unclear monstrosity:

    let data: Vec<u8> = input
        .chars()
        .filter(|c| {
            let m: bool = *c != '\n';
            if !m {
                num_rows += 1;
            }
            m
        })
        .map(|c| c as u8)
        .collect();

Going to put a pin in that one for now.