Solution for ex4.

Part 2 was not too hard from a logical perspective but it took me forever to figure out a decent way to filter out the Boards while they were winning without having to keep cloning things around.

I figured out I could keep a Vec of mutable references and keep removing (the references) from that one as a given board win...

Filtering a Vec of mutable references proved to be... quite tricky...

Eventually i figured out that you can overcome all the mutability and reference issues with:

let mut bb: Vec<&mut Board> = boards.iter_mut().collect();
bb = bb
            .into_iter()
            .filter_map(|x| if x.mark(num) { None } else { Some(x) })
            .collect();

filter_map feels unnecessary here, but it's actually conveniente because it will give you a plain &mut Board in the closure and not a weird &&mut Board...

I don't know if there's any better solution to this!

Using Dijkstra algorithm to solve this one. I also used const generics to be able to generalise how data is loaded into an arbitrary grid (everything else is filled with 0s). Then there's a generic method to expand the map based on a given tile size.

⚠️ TODO:

• [x] Add README

Implemented part1 & part2 for day 18 y2021.

For part2 we have 3 different ways of calculating all the permutations:

1. nested for loops
2. our own custom iterator
3. using the crate itertools

We added benchmarks for all the 3 of them and (surprisingly) number 2 is the fastest.

Nothing too special about this implementation except a few small things I discovered:

• The Rust standard library contains a built implementation of priority queues that we can use to easily keep track of the 3 biggest basin sizes: BinaryHeap
• We have been trying many times to convert a char (containing a number) to a u8 and we have been doing ASCII maths to do that. I just discovered we can simply do: c.to_digit(10).unwrap() as u8
• When we create a wrapper type (like Space here) we can automatically proxy all the method calls to the wrapped type by implementing the Deref trait.

My impl for ex2 of 2021.

I took the opportunity to play around with the FromIterator trait. I am pretty happy with the result.

There is a bit of code duplication but I think we can reduce that a bit by creating a Movable trait and a blanket implementation for FromIterator<Istr> for T where T: Movable.

Something that could be interesting to explore together.

Let me know what you think.

Nothing particularly interesting in terms of implementation.

It was weird to see for the first time that part 2 required us to "visualize" the output to be able to give an answer.

To handle this i did change the test for part 2 to only count the dots and i left some commented piece of code to draw the grid if needed.

Let me know if you have any better idea on how we could handle this!

My implementation. Nothing particularly fancy about the solution except that i tried to reduce the number of allocations and clone/copy as much as i could.

This one was a bit tricky and I am really bad at dealing with binary parsing.

I was initially trying to use a lazy approach where I constructed an iterator of bytes (u8) and I would be using bit shifting over bytes. It proved to be a little complicated (for my skills) to manage the alignment that way. I ended up simplifying this by using a proper sequence of 1 and 0.

This is all abstracted in the BinaryString struct. So we can potentially refactor that one and come up with a more efficient approach if we want to.

Another small improvement that we could do would be to use an Enum for the packet types.

I tried 3 different approaches (strings, nested linked list, flat linked list) on this one trying to expand the string for realz without realising that it would require terabytes of memory 🙈

Thanks to a few suggestions by @gambuzzi I managed to come up with a better approach based only on segments counting.

⚠️ TODO:

• [x] Add README

• Using FromIterator to parse input
• Using Iterator to simulate the passing of days. The iterator keeps the internal state and has a method to count the current number of fishes available. The iterator is effectively implementing all the simulation business logic.

This revisited solution introduces a new struct called Game. This struct creates and retains a vector of relative neighbours which effectively acts as a cache, so we don't need to recompute all the neighbours over and over.

Moreover Game implements Iterator so you can easily compute a number of game ticks and count the active cells.

Finally Game can be initialized from an input string which provides a generalisation on parsing input.

This solution seems slightly faster (or at least on par) with the previous non-generalised solutions:

If you like this approach, I would suggest that, before merging this, we remove the non generalised solutions so we can keep the code a bit cleaner and more organised.

Solved using dijkstra.

~~Part 2 could be optimised~~

Part 2 was optimized by running a reverse Dijkstra (from the end to all possible paths). This way Dijkstra is run only once and then we look at all the paths to the possible scenic points and select the shortest.

This resulted in -99.529% performance improvement. From ~200ms in non-debug mode to about 1ms!