Day 6 (Advent of Code 2020)

👋 This page was last updated ~4 years ago. Just so you know.

The end of Advent of Code 2020 is fast approaching, and we're nowhere near done. Time to do Day 6!

The problem statement here is a little contrived, as uh, as the days that came before it, but that won't stop us.

Basically, the input looks like this:

abc

a
b
c

ab
ac

a
a
a
a

b

Each line represents one person, and "groups of persons" are separated by blank lines.

There's only 26 possible letters, a through z.

Bear

Ooh, are we going to make an enum with 26 variants?

Amos

Ehhh bytes are close enough for today.

So, the first part is to collect the answers for each person of a group - we don't even really need a parser to do that!

Rust code
use std::collections::HashSet;

fn main() {
    let answers: Vec<_> = include_str!("input.txt")
        .split("\n\n")
        .map(|group| {
            group
                .lines()
                .map(|line| {
                    let mut set = HashSet::new();
                    for &b in line.as_bytes() {
                        set.insert(b);
                    }
                    set
                })
                .collect::<Vec<_>>()
        })
        .collect();

    dbg!(&answers[0..3]);
}
Shell session
$ cargo run --quiet
[src/main.rs:20] &answers[0..2] = [
    [
        {
            98,
        },
        {
            98,
        },
        {
            98,
        },
        {
            98,
        },
    ],
    [
        {
            120,
        },
        {
            120,
            102,
            106,
            107,
        },
        {
            120,
            98,
        },
    ],
]
Bear

Mhh that output isn't super readable - couldn't we use a newtype so we can supply our own Debug information?

Rust code
use std::{collections::HashSet, fmt};

pub struct Answers(HashSet<u8>);

impl fmt::Debug for Answers {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for &answer in &self.0 {
            write!(f, "{}", answer as char)?;
        }
        Ok(())
    }
}

fn main() {
    let answers: Vec<_> = include_str!("input.txt")
        .split("\n\n")
        .map(|group| {
            group
                .lines()
                .map(|line| {
                    let mut set = HashSet::new();
                    for &b in line.as_bytes() {
                        set.insert(b);
                    }
                    Answers(set)
                })
                .collect::<Vec<_>>()
        })
        .collect();

    dbg!(&answers[0..2]);
}
Shell session
$ cargo run --quiet
[src/main.rs:31] &answers[0..2] = [
    [
        b,
        b,
        b,
        b,
    ],
    [
        x,
        xkfj,
        bx,
    ],
]
Bear

Better! Can we compare to the puzzle input to make sure?

b
b
b
b

x
xfkj
xb
Bear

Awesome.

Now all we have to do is, for each group, to compute the union of the set of answers for all people.

There is a union method on std::collection::HashSet:

Rust code
pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S>

...but unfortunately it only computes the union between two HashSets, and it returns an iterator.

Bear

Speaking of iterators... why are we constructing the HashSet like this?

Rust code
let mut set = HashSet::new();
for &b in line.as_bytes() {
    set.insert(b);
}
Answers(set)

We can .collect() into a Vec... can't we .collect() into a HashSet?

Amos

Sure we can!

Rust code
    let answers: Vec<_> = include_str!("input.txt")
        .split("\n\n")
        .map(|group| {
            group
                .lines()
                .map(|line| Answers(line.as_bytes().iter().copied().collect()))
                .collect::<Vec<_>>()
        })
        .collect();
Bear

Ok good! You were saying?

The standard library lets us compute the union of two HashSets and returns an iterator. That's not a big problem to be honest - we could just chain all our iterators and collect the resulting iterator into a single HashSet.

But let's do something different. Let's try the im crate.

im provides a set of immutable data structures, including a HashSet!

Shell session
$ cargo add im
      Adding im v15.0.0 to dependencies

Now we just change our imports to:

Rust code
use im::HashSet;
use std::fmt;

...and that's it! It still works the same:

Shell session
$ cargo run --quiet
[src/main.rs:26] &answers[0..2] = [
    [
        b,
        b,
        b,
        b,
    ],
    [
        x,
        kxjf,
        bx,
    ],
]
Bear

Uhhh, what about it is immtuable?

Amos

How do you mean?

Bear

Well, we still build our HashSet like that:

Rust code
    .map(|line| Answers(line.as_bytes().iter().copied().collect()))

Which means it builds an empty im::HashSet, then adds elements one by one into it, right?

Amos

Right.

Bear

Isn't that mutation?

Amos

Let's read im's docs a bit.

All of these data structures support in-place copy-on-write mutation, which means that if you're the sole user of a data structure, you can update it in place without taking the performance hit of making a copy of the data structure before modifying it (this is about an order of magnitude faster than immutable operations, almost as fast as std::collections's mutable data structures).

Bear

Ohhh, smart!

Amos

Yes, smart! Same author as smartstring, which we explored recently.

Bear

What happens when you're not the sole owner of a HashSet though?

Say, what if you hand out a clone to somebody?

Amos

It's Cows all the way down!

Thanks to Rc's reference counting, we are able to determine whether a node in a data structure is being shared with other data structures, or whether it's safe to mutate it in place. When it's shared, we'll automatically make a copy of the node before modifying it.

The consequence of this is that cloning a data structure becomes a lazy operation: the initial clone is instant, and as you modify the cloned data structure it will clone chunks only where you change them, so that if you change the entire thing you will eventually have performed a full clone.

Cool bear's hot tip

Note that all the data structures in the im crate use Arc, which means they're thread-safe, but also, we pay "approximately 20-25%" performance for that.

There's an im-rc variant, which uses Rc, and has better performance, but the data structures aren't thread-safe anymore (they're neither Send nor Sync).

Anyway - im has a union method I like:

Rust code
pub fn union(self, other: Self) -> Self

Wait, no, a unions method I like:

Rust code
pub fn unions<I>(i: I) -> Self
where
    I: IntoIterator<Item = Self>,
    S: Default,
Bear

So we just... we just map our groups using im::HashSet::unions?

Amos

Yep!

main becomes:

Rust code
fn main() {
    let answers: Vec<_> = include_str!("input.txt")
        .split("\n\n")
        .map(|group| {
            group
                .lines()
                .map(|line| Answers(line.as_bytes().iter().copied().collect()))
                .collect::<Vec<_>>()
        })
        .collect();

    let group_answers: Vec<_> = answers
        .into_iter()
        .map(|group| Answers(HashSet::unions(group.into_iter().map(|x| x.0))))
        .collect();

    dbg!(&group_answers[0..5]);
}

Or, if we skip the intermediate step:

Rust code
fn main() {
    let group_answers: Vec<_> = include_str!("input.txt")
        .split("\n\n")
        .map(|group| {
            Answers(HashSet::unions(
                group
                    .lines()
                    .map(|line| line.as_bytes().iter().copied().collect()),
            ))
        })
        .collect();

    dbg!(&group_answers[0..5]);
}
Bear

Neat! What was the question again?

Each group answers "yes" to a certain number of questions (the "yes" being indicated by the presence of a letter in the set).

We're asked to compute the sum of all the questions answered by all the groups.

Bear

Neat! We can use .sum()! Let's pull in itertools and...

Amos

Actually, as multiple readers pointed out, .sum() is available in the standard library as well.

Bear

Even better!

We can skip some more intermediate steps:

Rust code
fn main() {
    let answer: usize = include_str!("input.txt")
        .split("\n\n")
        .map(|group| {
            HashSet::<u8>::unions(
                group
                    .lines()
                    .map(|line| line.as_bytes().iter().copied().collect()),
            )
            .len()
        })
        .sum();

    dbg!(answer);
}

And get our answer for part 1:

Shell session
$ cargo run --quiet
[src/main.rs:28] answer = 6534

Part 2

In the next part, the Advent of Code authors pull the old switcheroo on us.

We didn't need to compute the unions of the answers from each member of a group, but the intersection - i.e., keep only the answers to which everyone in the group said yes.

Bear

Is there an intersections method in im?

Amos

No such luck... but we can try reduce!

Bear

Did you mean fold?

Amos

Yes, that!

Rust code
fn main() {
    let answer: usize = include_str!("input.txt")
        .split("\n\n")
        .map(|group| {
            group
                .lines()
                .map(|line| line.as_bytes().iter().copied().collect())
                .fold(HashSet::<u8>::new(), |acc, x| acc.intersection(x))
                .len()
        })
        .sum();

    dbg!(answer);
}
Shell session
$ cargo run --quiet
[src/main.rs:27] answer = 0
Bear

Mhhh. Something's fishy.

Amos

Yeah I'm not quite sure what's hap-

Bear

OH! HashSet::new() returns an empty set!

Amos

Ahhhh right the intersection of the empty set with any thing will be-

Bear

the empty set!!

Amos

Ok so we can fix this by separating the first element, and using it as the initial value for the fold() call..

Bear

Or just make the initial HashSet contain all possible answers?

Amos

Ooh, I like that idea.

Rust code
fn main() {
    let init: HashSet<u8> = (b'a'..=b'z').collect();

    let answer: usize = include_str!("input.txt")
        .split("\n\n")
        .map(|group| {
            group
                .lines()
                .map(|line| line.as_bytes().iter().copied().collect())
                .fold(init.clone(), |acc, x| acc.intersection(x))
                .len()
        })
        .sum();

    dbg!(answer);
}
Amos

Oh and you know what? This works out great, because init.clone() is (basically) free!

Bear

Ohh right, cause it's immutable?

Amos

Yup!

Bear

So using im wasn't gratuitous?

Amos

Ehhh little bit of both. It all works out in the end.

Bear

Isn't there a variant of fold that just sets init to the first element though?

Amos

As it turns out, there is! Just not in the standard library.

Shell session
$ cargo add itertools
      Adding itertools v0.9.0 to dependencies

Our solution becomes:

Rust code
use im::HashSet;
use itertools::Itertools;

fn main() {
    let answer: usize = include_str!("input.txt")
        .split("\n\n")
        .map(|group| {
            group
                .lines()
                .map(|line| line.as_bytes().iter().copied().collect())
                .fold1(|acc: HashSet<u8>, x| acc.intersection(x))
                .unwrap_or_default()
                .len()
        })
        .sum();

    dbg!(answer);
}
Bear

Wait, unwrap_or_default? Why?

Amos

Well, what if we're fold1-ing a collection of 0 items? Then there's no init value to begin with!

Bear

Ah right!

Shell session
$ cargo run --quiet
[src/main.rs:29] answer = 3402
Bear

Right again 😎 That was fun!

Amos

See you next time bear!

Bear

See ya!

If you liked what you saw, please support my work!

Github logo Donate on GitHub Patreon logo Donate on Patreon

Here's another article just for you:

The HTTP crash course nobody asked for

HTTP does a pretty good job staying out of everyone's way.

If you're reading this article, there's a solid chance it was delivered to you over HTTP. Even if you're reading this from an RSS reader or something. And you didn't even have to think about it!

"Not having to think about it" is certainly a measure of success for a given technology. By contrast, . I wish I didn't.